콘텐츠로 이동

Gentry-Lee(GL) 동형암호란?

GL 동형암호는 효율적인 행렬 곱 연산을 위해 설계된 동형암호 기법입니다. 보다 자세한 내용이 궁금하시면 논문를 참고하세요.

GL의 인코딩 방식

GL에서는 기본적으로 여러 개의 정사각 행렬을 인코딩하고, 암호화합니다. 예를 들어, 다음과 같이 4x4 행렬 3개를 하나의 3차원 배열로 인코딩할 수 있습니다. numpy에 익숙한 사용자를 위해 예를 들자면 다음과 같습니다.

message = np.array(
    [[[ 1,  2,  3,  4],
      [ 5,  6,  7,  8],
      [ 9, 10, 11, 12],
      [13, 14, 15, 16]],
     [[17, 18, 19, 20],
      [21, 22, 23, 24],
      [25, 26, 27, 28],
      [29, 30, 31, 32]],
     [[33, 34, 35, 36],
      [37, 38, 39, 40],
      [41, 42, 43, 44],
      [45, 46, 47, 48]]]
)

이와 같이 여러 개의 행렬을 하나의 배열로 묶어 암호화합니다. GL에서는 위와 같이 인코딩된 데이터에 대해 덧셈, 아다마르 곱셈 (Hadamard multiplication 혹은 element-wise 곱셈), 행렬 곱셈을 지원합니다. 또한, 행렬의 전치 연산과, 행렬 내부의 회전, 그리고 행렬 간 회전 연산을 지원합니다.

행렬 곱셈

GL 스킴의 가장 큰 특징은 암호화된 상태에서 효율적인 행렬 곱셈을 지원한다는 점입니다. 기존 기법들과 달리 값비싼 변환 연산(Slot-to-coefficient) 없이, 슬롯(Slot) 인코딩된 상태에서 바로 행렬 곱을 수행하며, numpy의 np.matmul 혹은 @연산에 대응합니다. 3개의 2x2 행렬을 예시로 들자면 다음과 같습니다. 

# Input matrices
m0 = np.array(
  [[[ 0,  1],
    [ 2,  3]],
   [[ 4,  5],
    [ 6,  7]],
   [[ 8,  9],
    [10, 11]]]
  )
m1 = np.array(
  [[[ 0,  1],
    [ 2,  3]],
   [[ 4,  5],
    [ 6,  7]],
   [[ 8,  9],
    [10, 11]]]
  )

multiplied = np.matmul(m0, m1)
print(multiplied)


[[[  2   3]
  [  6  11]]
 [[ 46  55]
  [ 66  79]]
 [[154 171]
  [190 211]]]

복소 행렬 연산

GL 동형암호는 기본적으로 복소수 행렬간 연산을 지원하도록 설계되어 있습니다. 즉, 다음과 같은 형태의 행렬 연산을 지원합니다. 

# Input matrices
m0 = np.array(
  [[[ 0. +0.j,  1. +1.j],
    [ 2. +2.j,  3. +3.j]],
   [[ 4. +4.j,  5. +5.j],
    [ 6. +6.j,  7. +7.j]],
   [[ 8. +8.j,  9. +9.j],
    [10.+10.j, 11.+11.j]]]
  )
m1 = np.array(
  [[[ 0. +0.j,  1. +1.j],
    [ 2. +2.j,  3. +3.j]],
   [[ 4. +4.j,  5. +5.j],
    [ 6. +6.j,  7. +7.j]],
   [[ 8. +8.j,  9. +9.j],
    [10.+10.j, 11.+11.j]]]
  )

complex_multiplied = np.matmul(m0, m1)
print(complex_multiplied)


[[[0.  +4.j 0.  +6.j]
  [0. +12.j 0. +22.j]]

 [[0. +92.j 0.+110.j]
  [0.+132.j 0.+158.j]]

 [[0.+308.j 0.+342.j]
  [0.+380.j 0.+422.j]]]

이러한 행렬 곱셈 연산은 키 스위칭 (Key-switching)을 포함하며, GL의 수학적인 정의상 복소 행렬의 단순 곱 보다, 하나의 값을 복소 전치한 곱셈이 더 효율적입니다. 

transposed_multiplied = np.matmul(m0, m1.conjugate().transpose(0, 2, 1))
print(transposed_multiplied)


[[[  2.+0.j   6.+0.j]
  [  6.+0.j  26.+0.j]]

 [[ 82.+0.j 118.+0.j]
  [118.+0.j 170.+0.j]]

 [[290.+0.j 358.+0.j]
  [358.+0.j 442.+0.j]]]

덧셈, 아다마르 (Hadamard) 곱셈

행렬 간의 단순 덧셈과 각 원소끼리의 곱셈(아다마르 곱)도 자연스럽게 지원합니다. 예를 들면 다음과 같습니다.

덧셈

added = np.add(m0, m1)
print(added)

[[[ 0  2]
  [ 4  6]]
 [[ 8 10]
  [12 14]]
 [[16 18]
  [20 22]]]

아다마르 곱셈

hadamard_multiplied = np.multiply(m0, m1)
print(hadamard_multiplied)

[[[  0   1]
  [  4   9]]
 [[ 16  25]
  [ 36  49]]
 [[ 64  81]
  [100 121]]]

회전 연산

GL은 다변수 다항식환(Multivariate Ring) 구조를 사용하여 세 가지 차원의 회전을 모두 지원합니다. 이 연산들은 동형암호상의 np.roll과 같은 역할로 이해할 수 있습니다.

최상단의 예시 행렬을 행 방향으로 1만큼 회전하면 다음과 같습니다. 

row_rotate = np.roll(message, axis=1, shift=1)
print(row_rotate)


[[[13 14 15 16]
  [ 1  2  3  4]
  [ 5  6  7  8]
  [ 9 10 11 12]]

 [[29 30 31 32]
  [17 18 19 20]
  [21 22 23 24]
  [25 26 27 28]]

 [[45 46 47 48]
  [33 34 35 36]
  [37 38 39 40]
  [41 42 43 44]]]

열 방향으로 1만큼 회전하면 다음과 같습니다. 

col_rotate = np.roll(message, axis=2, shift=1)
print(col_rotate)


[[[ 4  1  2  3]
  [ 8  5  6  7]
  [12  9 10 11]
  [16 13 14 15]]

 [[20 17 18 19]
  [24 21 22 23]
  [28 25 26 27]
  [32 29 30 31]]

 [[36 33 34 35]
  [40 37 38 39]
  [44 41 42 43]
  [48 45 46 47]]]

행렬 간 회전 연산을 하면 다음과 같습니다. 

inter_matrix_rotate = np.roll(message, axis=0, shift=1)
print(inter_matrix_rotate)


[[[33 34 35 36]
  [37 38 39 40]
  [41 42 43 44]
  [45 46 47 48]]

 [[ 1  2  3  4]
  [ 5  6  7  8]
  [ 9 10 11 12]
  [13 14 15 16]]

 [[17 18 19 20]
  [21 22 23 24]
  [25 26 27 28]
  [29 30 31 32]]]

전치 연산

행렬의 행과 열을 뒤바꾸는 전치(Transpose) 연산도 효율적으로 지원합니다. 

transposed = np.transpose(message, (0, 2, 1))
print(transposed)

[[[ 1  5  9 13]
  [ 2  6 10 14]
  [ 3  7 11 15]
  [ 4  8 12 16]]

 [[17 21 25 29]
  [18 22 26 30]
  [19 23 27 31]
  [20 24 28 32]]

 [[33 37 41 45]
  [34 38 42 46]
  [35 39 43 47]
  [36 40 44 48]]]

복소 켤레 전치

위 예시에선 간단한 실수로 표현하였으나, GL은 효율적인 복소수 벡터 연산을 위하여 설계되었습니다. 따라서 단순 전치 연산뿐 아니라, 복소 켤레 연산과 복소 켤레 전치 연산을 지원합니다.

message = np.array(
      [[[ 0. +0.j,  1. +1.j,  2. +2.j,  3. +3.j],
        [ 4. +4.j,  5. +5.j,  6. +6.j,  7. +7.j],
        [ 8. +8.j,  9. +9.j, 10.+10.j, 11.+11.j],
        [12.+12.j, 13.+13.j, 14.+14.j, 15.+15.j]],

       [[16.+16.j, 17.+17.j, 18.+18.j, 19.+19.j],
        [20.+20.j, 21.+21.j, 22.+22.j, 23.+23.j],
        [24.+24.j, 25.+25.j, 26.+26.j, 27.+27.j],
        [28.+28.j, 29.+29.j, 30.+30.j, 31.+31.j]],

       [[32.+32.j, 33.+33.j, 34.+34.j, 35.+35.j],
        [36.+36.j, 37.+37.j, 38.+38.j, 39.+39.j],
        [40.+40.j, 41.+41.j, 42.+42.j, 43.+43.j],
        [44.+44.j, 45.+45.j, 46.+46.j, 47.+47.j]]]
)

conjugated = message.conjugate()
print(conjugated)

켤레 복소수: 

[[[ 0. -0.j  1. -1.j  2. -2.j  3. -3.j]
  [ 4. -4.j  5. -5.j  6. -6.j  7. -7.j]
  [ 8. -8.j  9. -9.j 10.-10.j 11.-11.j]
  [12.-12.j 13.-13.j 14.-14.j 15.-15.j]]

 [[16.-16.j 17.-17.j 18.-18.j 19.-19.j]
  [20.-20.j 21.-21.j 22.-22.j 23.-23.j]
  [24.-24.j 25.-25.j 26.-26.j 27.-27.j]
  [28.-28.j 29.-29.j 30.-30.j 31.-31.j]]

 [[32.-32.j 33.-33.j 34.-34.j 35.-35.j]
  [36.-36.j 37.-37.j 38.-38.j 39.-39.j]
  [40.-40.j 41.-41.j 42.-42.j 43.-43.j]
  [44.-44.j 45.-45.j 46.-46.j 47.-47.j]]]

켤레전치: 

conjugate_transposed = np.transpose(message.conjugate(), (0, 2, 1))
print(conjugate_transposed)


[[[ 0. -0.j  4. -4.j  8. -8.j 12.-12.j]
  [ 1. -1.j  5. -5.j  9. -9.j 13.-13.j]
  [ 2. -2.j  6. -6.j 10.-10.j 14.-14.j]
  [ 3. -3.j  7. -7.j 11.-11.j 15.-15.j]]

 [[16.-16.j 20.-20.j 24.-24.j 28.-28.j]
  [17.-17.j 21.-21.j 25.-25.j 29.-29.j]
  [18.-18.j 22.-22.j 26.-26.j 30.-30.j]
  [19.-19.j 23.-23.j 27.-27.j 31.-31.j]]

 [[32.-32.j 36.-36.j 40.-40.j 44.-44.j]
  [33.-33.j 37.-37.j 41.-41.j 45.-45.j]
  [34.-34.j 38.-38.j 42.-42.j 46.-46.j]
  [35.-35.j 39.-39.j 43.-43.j 47.-47.j]]]