Data Structures
Here are the data structures used for homomorphic encryption operations.
Engine
The engine is the basis of all operations. All other data structures are created through the engine, and all operations (such as addition and multiplications) are done through the engine. All file I/O is also handled by the engine.
Secret Key
The secret key is required for decryption. It can also be used for encryption. It is also needed in creating all the other keys.
Public Key
The public key can be used for encryption. It is created using a secret key. In a multiparty setting, the process for creating a public key is more complex. Please consult the multiparty document for details.
Ciphertext
The ciphertext is an encryption of a list of real or complex numbers. It is created using the public key. Many homomorphic operations such as addition, multiplication, and rotation can be performed on ciphertexts.
When a ciphertext is created, it has a fixed multiplication count called a level. When two cipehrtexts are multiplied, the resulting ciphertext will have the level reduced by one compared to the input ciphertexts. A ciphertext with level 0 can no longer be multiplied. It is possible to reset this level to a higher value by the bootstrapping operation. For details on the bootstrapping operation, please consult the bootstrap document.
When a ciphertext is encrypted, it is represented as a vector of 2 polynomials.
In homomorphic encryption, a vector of 2 polynomials are conventionally represented as (b, a).
When two ciphertexts are multiplied, the representation becomes a vector of 3 polynomials. This difference in vector size makes further operations difficult, so the vector size of the ciphertext needs to be reduced back to 2. This process is called relinearization.
Plaintext
A plaintext is an encoding of a list of real or complex numbers. No key is required to encode a plaintext. A plaintext can be used for operation with a ciphertext. This allows homomorphic operations such as addition and multiplication between encrypted data and unencrypted data.
When a plaintext is encoded, it is represented as a vector of 1 polynomial.
Light Plaintext
A light plaintext is a compact variant of the plaintext, with the sole purpose of multiplying with a ciphertext.
Due to its small size, there is a limit to the values it can store.
The recommended range of values to encode is [-1, 1].
This data structure is not available for multiparty computation.
Evaluation Key
The evaluation key can be used in the following operations: relinearization, conjugation, roll, and bootstrap. It includes all the necessary keys required for each of the operations. If memory is not a strict burden, this is the recommended key to use. For bootstrap, there are 2 sizes: small and medium. Check below for the memory requirements. It is created using a secret key. This data structure is not available for multiparty computation.
Relinearization Key
When a ciphertext is encrypted, it is represented as a vector of 2 polynomials.
In homomorphic encryption, a vector of 2 polynomials are conventionally represented as (b, a).
When two ciphertexts are multiplied, the representation becomes a vector of 3 polynomials. This difference in vector size makes further operations difficult, so the vector size of the ciphertext needs to be reduced back to 2. This process is called relinearization. The relinearization key is used for this operation, and is created using a secret key.
Conjugation Key
The conjugation key is used to perform the homomorphic conjugation of an encrypted ciphertext, which changes the sign of the imaginary part of the ciphertext. It is created using a secret key.
Fixed Roll Key
The fixed roll key is used to roll an encrypted ciphertext to the right by a given integer shift value. It can only be used to roll by a fixed shift value. It is created using a secret key.
Roll Key
The roll key is used to roll an encrypted ciphertext to the right by any given integer shift value. It is created using a secret key.
Internally a roll key is comprised of a basis of fixed roll keys so that shift by any number is possible. The shift value of the internal fixed roll keys is a power of 2.
Fixed Rotation Key
The fixed rotation key is used to rotate an encrypted ciphertext to the left by a given integer delta value. It can only be used for rotation by a fixed delta value. It is created using a secret key.
Rotation Key
The rotation key is used to perform the homomorphic rotation of an encrypted ciphertext to the left by a given integer delta value. It is created using a secret key.
Internally a rotation key is comprised of a basis of fixed rotation keys so that the rotation by any delta is possible. The delta value of the internal fixed rotation keys is a power of 2.
Bootstrap Key
The bootstrap key is used in the bootstrap operation, which restores the multiplication level of an encrypted ciphertext. It is created using a secret key.
Internally a bootstrap key incorporates every single fixed rotation key that is needed by the bootstrap operation. Because of this, the bootstrap key is quite large (about 12.3GB).
If the bootstrap key cannot fit in the memory, there is a smaller version of the bootstrap key (called the small bootstrap key) that is used in conjunction with the rotation key. Because the bootstrap key contains a fixed rotation key for all the necessary delta values the bootstrap operation can be performed in an optimized manner.
If there is not enough memory to use the bootstrap key, you can use the small bootstrap key in conjunction with the rotation key. This method will require about 3.8GB of memory. Since the bootstrap opertaion using the small bootstrap key is slower, it is recommended to use the bootstrap key whenever possible.
Small Bootstrap Key
The small bootstrap key is used in the bootstrap operation, which restores the multiplication level of a ciphertext. It is created using a secret key.
Transposition Key
The transposition key is used in the transpose operation, which swaps the rows and the columns of a matrix. It is only used by the matrix engine. It is created using a secret key.
Conjugate Transposition Key
The conjugate transposition key is used in the conjugate transpose operation, which changes the sign of the imaginary part of the ciphertext and swaps the rows and columns of a matrix. It is only used by the matrix engine. It is created using a secret key.
Matrix Multiplication Key
The matrix multiplication key is used in the matrix multiplication operation. It is only used by the matrix engine. It is created using a secret key.
Public Key A
The public_key_a can be considered a initial common public key in multiparty operations.
It is used to create individual public_key_b's.
After the public_key_b's are created, all public_key_b's and the public_key_a is combined to create the final multiparty public key.
In homomorphic encryption, a vector of 2 polynomials are conventionally represented as (b, a).
The public_key_a is the a part of the common public key which is a vector of 2 polynomials.
Therefore the initial common public key is called the public_key_a, to avoid confusion with the final multiparty public key.
Public Key B
The public_key_b can be considered an individual public key in multiparty operations.
It is used to create the final multiparty public key.
It is created using an individual secret key and a common public_key_a.
In homomorphic encryption, a vector of 2 polynomials are conventionally represented as (b, a).
The sum of public_key_b is the b part of the common public key which is a vector of 2 polynomials.
Therefore the individual public key is called the public_key_b.
Decrypted Share
The decrypted share is an intermediate value of the multiparty decryption process. In a multyparty decryption, each party decrypts a ciphertext with its own secret key, which creates a decrypted share. The final decryption can be done with the original ciphertext and every single decrypted share of the parties participating in the multiparty operation. Some error is introduced in the decrypted share to protect the secret key.
Supported Data Structures by Feature
| Data Structure | Vector | Vector Bootstrap |
Vector Multiparty |
Matrix |
|---|---|---|---|---|
| Secret Key | ✅ | ✅ | ✅ | ✅ |
| Public Key | ✅ | ✅ | ✅ | ✅ |
| Public Key A | - | - | ✅ | - |
| Public Key B | - | - | ✅ | - |
| Plaintext | ✅ | ✅ | ✅ | ✅ |
| Light Plaintext | ✅ | ✅ | - | - |
| Ciphertext | ✅ | ✅ | ✅ | ✅ |
| Decryption Share | - | - | ✅ | - |
| Relinearization Key | ✅ | ✅ | ✅ | ✅ |
| Conjugation Key | ✅ | ✅ | ✅ | ✅ |
| Fixed Roll Key | ✅ | ✅ | ✅ | ✅ |
| Roll Key | ✅ | ✅ | ✅ | ✅ |
| Fixed Rotation Key | ✅ | ✅ | ✅ | - |
| Rotation Key | ✅ | ✅ | ✅ | - |
| Small Bootstrap Key | - | ✅ | - | - |
| Bootstrap Key | - | ✅ | - | - |
| Transposition Key | - | - | - | ✅ |
| Conjugate Transposition Key | - | - | - | ✅ |
| Matrix Multiplication Key | - | - | - | ✅ |
| Evaluation Key | ✅ | ✅ | - | - |
Sizes
Here are the memory sizes of each data structure for some max_level values.
If you want to know the size of a data structure for a specific max_level, you can run the codes in Google Colab
Vector (CKKS)
| Max Level | 2 | 7 | 17 | 36 |
|---|---|---|---|---|
| Secret Key | 328.4 KB | 1.5 MB | 5.0 MB | 19.1 MB |
| Public Key | 512.4 KB | 2.3 MB | 8.0 MB | 31.0 MB |
| Plaintext | 256.4 KB | 1.1 MB | 4.0 MB | 14.5 MB |
| Light Plaintext | 64.4 KB | 128.4 KB | 256.4 KB | 512.4 KB |
| Ciphertext | 512.6 KB | 2.3 MB | 8.0 MB | 29.0 MB |
| Relinearization Key | 1.5 MB | 13.5 MB | 59.5 MB | 238.0 MB |
| Conjugation Key | 1.5 MB | 13.5 MB | 59.6 MB | 238.2 MB |
| Fixed Rotation Key | 1.5 MB | 13.5 MB | 59.6 MB | 238.2 MB |
| Rotation Key | 18.3 MB | 176.1 MB | 834.3 MB | 3.5 GB |
| Evaluation Key | 21.3 MB | 203.2 MB | 953.4 MB | 4.0 GB |
Vector Bootstrap
| Max Level | 17 |
|---|---|
| Secret Key | 19.1 MB |
| Public Key | 31.0 MB |
| Plaintext | 7.0 MB |
| Light Plaintext | 512.4 KB |
| Ciphertext | 14.0 MB |
| Relinearization Key | 245.0 MB |
| Conjugation Key | 245.2 MB |
| Fixed Rotation Key | 245.2 MB |
| Rotation Key | 3.6 GB |
| Small Bootstrap Key | 252.0 MB |
| Bootstrap Key | 14.2 GB |
| Small Evaluation Key | 4.3 GB |
| Medium Evaluation Key | 14.7 GB |
Vector Multiparty
| Max Level | 4 | 10 | 23 |
|---|---|---|---|
| Secret Key | 1.0 MB | 3.8 MB | 15.1 MB |
| Public Key A | 1.0 MB | 3.8 MB | 15.0 MB |
| Public Key B | 1.0 MB | 3.8 MB | 15.0 MB |
| Public Key | 2.0 MB | 7.5 MB | 30.0 MB |
| Plaintext | 896.4 KB | 3.3 MB | 13.0 MB |
| Ciphertext | 1.8 MB | 6.5 MB | 26.0 MB |
| Decrypted Share | 896.4 KB | 3.3 MB | 13.0 MB |
| Individual Relinearization Key | 10.5 MB | 42.0 MB | 203.0 MB |
| Multiparty Relinearization Key | 10.5 MB | 42.0 MB | 203.0 MB |
| Individual Conjugation Key | 10.5 MB | 42.1 MB | 203.2 MB |
| Multiparty Conjugation Key | 10.5 MB | 42.1 MB | 203.2 MB |
| Individual Fixed Rotation Key | 10.5 MB | 42.1 MB | 203.2 MB |
| Multiparty Fixed Rotation Key | 10.5 MB | 42.1 MB | 203.2 MB |
| Individual Rotation Key | 137.1 MB | 589.3 MB | 3.0 GB |
| Multiparty Rotation Key | 137.5 MB | 590.2 MB | 3.0 GB |
Matrix (GL) with 256 batches
| Shape | (256, 16, 16) | (256, 32, 32) | (256, 64, 64) |
|---|---|---|---|
| Max Level | 2 | 7 | 17 |
| Secret Key | 328.4 KB | 1.3 MB | 5.3 MB |
| Public Key | 512.4 KB | 2.3 MB | 9.5 MB |
| Plaintext | 4.0 MB | 36.0 MB | 304.0 MB |
| Ciphertext | 8.0 MB | 72.0 MB | 608.0 MB |
| Relinearization Key | 1.5 MB | 18.0 MB | 90.0 MB |
| Conjugation Key | 1.5 MB | 18.0 MB | 90.0 MB |
| Fixed Roll Key | 1.5 MB | 18.0 MB | 90.0 MB |
| Roll Key | 19.5 MB | 252.0 MB | 1.3 GB |
| Transposition Key | 24.0 MB | 576.0 MB | 5.6 GB |
| Conjugate Transposition Key | 24.0 MB | 576.0 MB | 5.6 GB |
| Matrix Multiplication Key | 48.0 MB | 1.1 GB | 11.3 GB |
Matrix (GL) with 162 batches
| Shape | (162, 32, 32) | (162, 64, 64) | (162, 128, 128) |
|---|---|---|---|
| Max Level | 3 | 9 | 21 |
| Secret Key | 496.5 KB | 2.1 MB | 8.3 MB |
| Public Key | 810.4 KB | 3.5 MB | 14.6 MB |
| Plaintext | 12.7 MB | 111.4 MB | 931.5 MB |
| Ciphertext | 25.3 MB | 222.8 MB | 1.8 GB |
| Relinearization Key | 3.2 MB | 19.0 MB | 126.6 MB |
| Conjugation Key | 3.2 MB | 19.0 MB | 126.6 MB |
| Fixed Roll Key | 3.2 MB | 19.0 MB | 126.6 MB |
| Roll Key | 44.3 MB | 284.8 MB | 2.0 GB |
| Transposition Key | 101.3 MB | 1.2 GB | 15.8 GB |
| Conjugate Transposition Key | 101.3 MB | 1.2 GB | 15.8 GB |
| Matrix Multiplication Key | 202.5 MB | 2.4 GB | 31.6 GB |
Matrix (GL) with 486 batches
| Shape | (486, 16, 16) | (486, 32, 32) | (486, 64, 64) |
|---|---|---|---|
| Max Level | 7 | 16 | 33 |
| Secret Key | 1.2 MB | 4.8 MB | 18.6 MB |
| Public Key | 2.1 MB | 8.5 MB | 33.2 MB |
| Plaintext | 17.1 MB | 136.7 MB | 1.0 GB |
| Ciphertext | 34.2 MB | 273.4 MB | 2.1 GB |
| Relinearization Key | 17.1 MB | 81.2 MB | 324.6 MB |
| Conjugation Key | 17.1 MB | 81.2 MB | 324.6 MB |
| Fixed Roll Key | 17.1 MB | 81.2 MB | 324.6 MB |
| Roll Key | 239.3 MB | 1.2 GB | 5.1 GB |
| Transposition Key | 273.4 MB | 2.5 GB | 20.3 GB |
| Conjugate Transposition Key | 273.4 MB | 2.5 GB | 20.3 GB |
| Matrix Multiplication Key | 546.8 MB | 5.1 GB | 40.6 GB |