Skip to content

What is Gentry-Lee (GL) Homomorphic Encryption?

GL Homomorphic Encryption is a homomorphic encryption scheme designed for efficient matrix multiplication. For more details, please refer to the paper.

Encoding of the GL Scheme

GL basically encodes and encrypts multiple square matrices. For example, three 4x4 matrices can be encoded into a single 3D array as shown below. For users familiar with numpy, here is an example:

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 bundles multiple matrices and encrypts them into a single ciphertext. GL supports addition, Hadamard multiplication (or element-wise multiplication), and matrix multiplication on data encoded in this manner. It also supports matrix conjugate transposition and rotation along all three axes.

Matrix Multiplication

The most significant feature of the GL scheme is that it allows efficient matrix multiplication between ciphertexts. Unlike previously existing techniques, it performs matrix multiplication directly in the slot-encoded state without having to perform expensive transformation operations, which is usually called slot-to-coefficient. The matrix multiplication operation corresponds to numpy's np.matmul or the @ operator. Here is an example using three 2x2 matrices.

# 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]]]

Complex Matrix Operations

The GL scheme can also handle matrices with complex numbers.

# 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]]]

This matrix multiplication operation involves key-switching. By the mathematical encoding structure of GL scheme, multiplying by a complex-transposed value (Hermitian transpose) is more efficient than simple complex matrix multiplication. Specificially, evaluating \(AB\) requires one more key switching compared to \(AB^*\), where \(^*\) denotes Hermitian transpose.

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]]]

Addition and Hadamard Multiplication

Simple addition between matrices and Hadamard multiplication (Hadamard product) are also naturally supported.

Addition

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

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

Hadamard Multiplication

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

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

Rotation Operations

GL scheme uses a multivariate ring structure to support rotations along all three axes. These operations can be understood as the equivalent of np.roll in homomorphic encryption.

Rotating the example matrix (at the top of the page) by 1 in the row direction yields:

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]]]

Rotating by 1 in the column direction yields:

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]]]

Performing an inter-matrix rotation yields:

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]]]

Transposition Operations

Transposition operations, which swap the rows and columns of a matrix, are also efficiently supported.

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]]]

Complex Conjugate Transpose

The GL scheme also supports complex conjugation and complex conjugate transposition operations.

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)

Conjugation yields: 

[[[ 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 transposition yields: 

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]]]