Skip to content

What is Homomorphic Encryption?

Homomorphic encryption is an innovative encryption method designed to enable computations directly on encrypted data. It allows operations such as addition and multiplication to be performed on encrypted data, opening up the possibility of securely utilizing sensitive information that was previously inaccessible. However, computations on encrypted data are slower than regular operations and come with specific constraints. Having a basic understanding of homomorphic encryption is needed to use it properly.

This page is written to help anyone understand the characteristics of homomorphic encryption. If you are already familiar in homomorphic encryption, you might not need to read this.

Encryption Methods

The major encryption methods in homomorphic encryption include:

  • FHEW/TFHE: Supports bit and integer operations.
  • BFV/BGV: Supports integer operations as well as SIMD encryption.
  • CKKS: Supports operations on real and complex numbers as well as SIMD encryption.

Currently, the DESILO FHE library supports CKKS, the most widely applicable method. Other methods will be supported in the future.

Properties of Ciphertexts

Homomorphic encryption has the following properties:

  1. Batch Encryption (or Packing): Large amounts of data are encrypted at once as a vector in a ciphertext. Depending on the encryption parameters, the DESILO FHE library can encrypt vectors of length up to \(2^{12}\), \(2^{13}\), \(2^{14}\), \(2^{15}\), or \(2^{16}\). Note that increasing the maximum size of the vectors slows down the homomorphic computation.

  2. Noise and Bootstrapping: Homomorphic ciphertexts include a certain amount of noise for security purposes. With each operation, this noise increases. If the noise begins to affect the original values, bootstrapping can be used to reduce the noise and enable additional computations.

  3. Operational Characteristics: Operations such as additions and multiplications between ciphertexts follow an SIMD (Single Instruction, Multiple Data) approach, for example: (1, 2, 3) + (4, 5, 6) = (5, 7, 9), or (1, 2, 3) * (4, 5, 6) = (4, 10, 18). Such operations can also be computed between a ciphertext and some un-encrypted data as well. In addition, the library supports other homomorphic operations such as rotations and conjugation.

  4. Level and Multiplicative Depth A given ciphertext has a so-called level. The maximum level depends on the cryptographic parameters that have been selected. Every time a multiplication is done, the level of the resulting ciphertext is reduced by 1. For instance when multiplying a ciphertext at level 3 with another ciphertext at level 3, the output result is a ciphertext at level 2. This is also the case when multiplying a ciphertext at level 3 with an un-encrypted vector of data. The maximum number of chained multiplications is called multiplicative depth. For example, multiplying four ciphertext (a * b) * (c * d) would only require 2 multiplicative depths.

  5. Keys: Various types of keys are required in a homomorphic encryption system. These include:

    • Decryption Key: A secret key used for decrypting ciphertexts.
    • Encryption Key: A public key used for encryption.
    • Relinearization Key: A public key used for homomorphic multiplications.
    • Conjugation Key: A public key for the homomorphic computation of complex conjugate.
    • Rotation Key: A public key used for rotation operations.
    • Bootstrap Key: A public key used for bootstrap operations.