# 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](https://github.com/zama-ai/awesome-zama) or [fhe.org](https://fhe.org/resources/).

## Operations on encrypted values

Homomorphic encryption allows computations on ciphertexts without revealing the underlying plaintexts. A scheme is considered [fully homomorphic](https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption) 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.

![](/files/j39zlgT4NrqPDzsH8O5X)

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.

In Concrete, the default failure probability is set to $$\frac{1}{100000}$$, meaning that 1 in every 100,000 executions may result in an error. Reducing this probability requires adjusting cryptographic parameters, potentially lowering performance. Conversely, allowing a higher probability of error may improve performance.

## Function evaluation

While we’ve covered arithmetic operations, typical programs also involve functions (for example, maximum, minimum, square root). In [TFHE](/concrete/get-started/terminology.md#tfhe), the Bootstrap operation can be enhanced with a [Table Lookup](/concrete/get-started/terminology.md#table-lookup-tlu), creating a **Programmable Bootstrap (PBS)**.

Concrete uses PBS to evaluate functions homomorphically:

* **Homomorphic univariate function evaluation**: $$f(E\[x]) = E\[f(x)]$$

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:

```python
import numpy as np

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

This function could be turned into a table lookup:

```python
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:

```c++
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](/concrete/guides/self.md) section.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.zama.org/concrete/explanations/fhe_basics.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.