Cryptography basics

This document provides an overview of Fully Homomorphic Encryption (FHE) to get you started with Concrete. For more comprehensive resources about FHE, visit the awesome Zama repo or fhe.org.

Operations on encrypted values

Homomorphic encryption allows computations on ciphertexts without revealing the underlying plaintexts. A scheme is considered fully homomorphic if it supports an unlimited number of additions and multiplications.

Let $x$ represent a plaintext and $E[x]$ the corresponding ciphertext:

• Homomorphic addition: $E[x] + E[y] = E[x + y]$

• Homomorphic multiplication: $E[x] * E[y] = E[x * y]$

Noise and Bootstrap

FHE encrypts data as LWE ciphertexts, represented visually as a bit vector. The encrypted message is located in the higher-order (yellow) bits, while the lower-order (gray) bits contain random noise that ensures the security of the ciphertext.

Each operation on an encrypted value increases the noise, and if it becomes too large, it may overlap with the message and corrupt its value. To reduce the noise of a ciphertext, the Bootstrap operation generates a new ciphertext encrypting the same message, but with lower noise. This allows additional operations to be performed on the encrypted message.

In typical FHE programs, operations are followed by a bootstrap, and this sequence repeats multiple times.

Probability of Error

The amount of noise in a ciphertext is not as bounded as it may appear in the above illustration. As the errors are drawn randomly from a Gaussian distribution, they can be of varying size. This means that we need to be careful to ensure the noise terms do not affect the message bits. If the error terms do overflow into the message bits, this can cause an incorrect output (failure) when bootstrapping.

The noise in a ciphertext isn't strictly bounded, as errors are drawn from a Gaussian distribution and vary in size. If the noise grows too large, it may corrupt the message bits, causing incorrect outputs during bootstrapping.

Function evaluation

While we’ve covered arithmetic operations, typical programs also involve functions (for example, maximum, minimum, square root). In TFHE, the Bootstrap operation can be enhanced with a Table Lookup, creating a Programmable Bootstrap (PBS).

Concrete uses PBS to evaluate functions homomorphically:

For example, consider a function (or circuit) that takes a 4 bits input variable and output the maximum value between a clear constant and the encrypted input:

import numpy as np

def encrypted_max(x: uint4):
    return np.maximum(5, x)

This function could be turned into a table lookup:

def encrypted_max(x: uint4):
    lut = [5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    return lut[x]

The Lookup table lut being applied during the Programmable Bootstrap.

PBS management

You don't need to manage PBS operations manually, as they are handled automatically by Concrete during the compilation process. Each function evaluation is converted into a lookup table and evaluated via PBS.

For example, if you inspect the MLIR code generated by the frontend, you’ll see the lookup table in the 4th line of the following output:

module {
  func.func @main(%arg0: !FHE.eint<4>) -> !FHE.eint<4> {
    %cst = arith.constant dense<[5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]> : tensor<16xi64>
    %0 = "FHE.apply_lookup_table"(%arg0, %cst) : (!FHE.eint<4>, tensor<16xi64>) -> !FHE.eint<4>
    return %0 : !FHE.eint<4>
  }
}

There are 2 things to keep in mind about PBS:

• Input type constraints: PBS operations adds constraints on input type and thus limits the maximum bit-width supported in Concrete.

• PBS performance impact: PBS operations are costly, so minimizing the number of PBS can improve circuit performance. PBS cost also varies with input precision (for example, an 8-bit PBS is faster than a 16-bit PBS). To learn more about optimizing PBS, refer to the Optimization section.