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 is also needed in creating all the other keys.

Public Key

The public key is required 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.

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 Rotation Key

The fixed rotation key is used to perform the homomorphic rotation of an encrypted ciphertext to the right by a given integer delta value. It can only be used for rotation by a fixed delta. 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 right 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.

If you want to rotate a ciphertext by 3 slots, then you have roughly 3 options.

1. rotate 3 times with a fixed rotation key of delta 1.
2. rotate 1 time with a fixed rotation key of delta 3.
3. rotate with a rotation key.

Internally, the rotation key would rotate twice, once with a rotation key of delta 1 and then again with a rotation key of delta 2. Because of this, the runtime of option 1 would be roughly 3 times slower than that of option 2, and the runtime of option 2 would be roughly 2 times slower than that of option 2. In general, using the rotation key is recommended unless there is a very limited set of delta values.

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 14GB).

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 6GB 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.

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.