TFHE-rs
WebsiteLibrariesProduct & ServicesDevelopersSupport
0.10
0.10
  • Welcome to TFHE-rs
  • Get Started
    • What is TFHE-rs?
    • Installation
    • Quick start
    • Types & Operations
    • Benchmarks
      • CPU Benchmarks
      • GPU Benchmarks
      • Zero-knowledge proof benchmarks
    • Security and cryptography
  • Fundamentals
    • Configuration and key generation
    • Server key
    • Encryption
    • Computation on encrypted data
    • Decryption
    • Encrypted pseudo random values
    • Serialization/deserialization
    • Compressing ciphertexts/keys
    • Debugging
  • Guides
    • Rust configuration
    • GPU acceleration
    • Overflow detection
    • Data versioning
    • Public key encryption
    • Zero-knowledge proofs
    • Generic trait bounds
    • Parallelized PBS
    • High-level API in C
    • JS on WASM API
    • Multi-threading with Rayon crate
    • Trivial ciphertexts
    • PBS statistics
    • Array
  • Tutorials
    • All tutorials
    • Homomorphic parity bit
    • Homomorphic case changing on Ascii string
    • SHA256 with Boolean API
  • References
    • API references
    • Fine-grained APIs
      • Quick start
      • Boolean
        • Operations
        • Cryptographic parameters
        • Serialization/Deserialization
      • Shortint
        • Operations
        • Cryptographic parameters
        • Serialization/Deserialization
      • Integer
        • Operations
        • Cryptographic parameters
        • Serialization/Deserialization
    • Core crypto API
      • Quick start
      • Tutorial
  • Explanations
    • TFHE deep dive
  • Developers
    • Contributing
    • Release note
    • Feature request
    • Bug report
Powered by GitBook

Libraries

  • TFHE-rs
  • Concrete
  • Concrete ML
  • fhEVM

Developers

  • Blog
  • Documentation
  • Github
  • FHE resources

Company

  • About
  • Introduction to FHE
  • Media
  • Careers
On this page
  • TFHE
  • LWE ciphertexts
  • Programmable Bootstrapping, noise management, and carry bits
  • Noise
  • Programmable BootStrapping (PBS)
  • Carry
  • Security
  • Classical public key encryption.

Was this helpful?

Export as PDF
  1. Get Started

Security and cryptography

PreviousZero-knowledge proof benchmarksNextConfiguration and key generation

Last updated 6 months ago

Was this helpful?

This document introduces the cryptographic concepts of the scheme of Fully Homomorphic Encryption over the Torus (TFHE) and the security considerations of TFHE-rs.

TFHE

TFHE-rs is a cryptographic library that implements Fully Homomorphic Encryption using the TFHE scheme. You should understand the basics of TFHE to consider its limitations, such as:

  • The precision: TFHE has limitations on the number of bits used to represent plaintext values.

  • The execution time: TFHE operations are slower than native operations due to their complexity.

LWE ciphertexts

TFHE-rs primarily utilizes Learning With Errors (LWE) ciphertexts. The LWE problem forms the basis of TFHE's security and is considered resistant to quantum attacks.

An LWE Ciphertext is a collection of 32-bit or 64-bit unsigned integers. Before encrypting a message in an LWE ciphertext, you first need to encode it as a plaintext by shifting the message to the most significant bits of the unsigned integer type used.

Then, you add a small random value called noise to the least significant bits. This noise is crucial in ensuring the security of the ciphertext.

plaintext=(Δ∗m)+eplaintext = (\Delta * m) + eplaintext=(Δ∗m)+e

m∈Zpm \in \mathbb{Z}_pm∈Zp​

To get a ciphertext from a plaintext, you must encrypt the plaintext using a secret key.

An LWE secret key is a list of n random integers: S=(s0,...,sn−1)S = (s_0, ..., s_{n-1})S=(s0​,...,sn−1​). nnn is called the LweDimensionLweDimensionLweDimension

An LWE ciphertext is composed of two parts:

  • The mask (a0,...,an−1)(a_0, ..., a_{n-1})(a0​,...,an−1​)

  • The body bbb

The mask of a fresh ciphertext (the result of an encryption, and not the result of operations such as ciphertext addition) is a list of n uniformly random values.

The body is computed as follows:

b=(∑i=0n−1ai∗si)+plaintextb = (\sum_{i = 0}^{n-1}{a_i * s_i}) + plaintextb=(∑i=0n−1​ai​∗si​)+plaintext

Now that the encryption scheme is defined, let's review the example of the addition between ciphertexts to illustrate why it is slower to compute over encrypted data.

To add two ciphertexts, we must add their $mask$ and $body$:

ct0=(a0,...,an−1,b)ct1=(a0′,...,an−1′,b′)ct2=ct0+ct1ct2=(a0+a0′,...,an−1+an−1′,b+b′)b+b′=(∑i=0n−1ai∗si)+plaintext+(∑i=0n−1ai′∗si)+plaintext′b+b′=(∑i=0n−1(ai+ai′)∗si)+Δm+Δm′+e+e′ct_0 = (a_{0}, ..., a_{n-1}, b) \\ ct_1 = (a_{0}^{\prime}, ..., a_{n-1}^{\prime}, b^{\prime}) \\ ct_{2} = ct_0 + ct_1 \\ ct_{2} = (a_{0} + a_{0}^{\prime}, ..., a_{n-1} + a_{n-1}^{\prime}, b + b^{\prime})\\ b + b^{\prime} = (\sum_{i = 0}^{n-1}{a_i * s_i}) + plaintext + (\sum_{i = 0}^{n-1}{a_i^{\prime} * s_i}) + plaintext^{\prime}\\ b + b^{\prime} = (\sum_{i = 0}^{n-1}{(a_i + a_i^{\prime})* s_i}) + \Delta m + \Delta m^{\prime} + e + e^{\prime}\\ct0​=(a0​,...,an−1​,b)ct1​=(a0′​,...,an−1′​,b′)ct2​=ct0​+ct1​ct2​=(a0​+a0′​,...,an−1​+an−1′​,b+b′)b+b′=(i=0∑n−1​ai​∗si​)+plaintext+(i=0∑n−1​ai′​∗si​)+plaintext′b+b′=(i=0∑n−1​(ai​+ai′​)∗si​)+Δm+Δm′+e+e′

To add ciphertexts, it is necessary to add both their masks and bodies. The operation involves adding n+1n + 1n+1 elements, rather than just adding two integers. This is an intuitive example to show how FHE computation is slower compared to plaintext computation. However, other operations are far more expensive (for example, the computation of a lookup table using Programmable Bootstrapping).

Programmable Bootstrapping, noise management, and carry bits

In FHE, two types of operations can be applied to ciphertexts:

  • Leveled operations, which increase the noise in the ciphertext

  • Bootstrapped operations, which reduce the noise in the ciphertext

Noise is critical in FHE because it can tamper with the message if not tracked and managed properly. Bootstrapping operations decrease noise within the ciphertexts and guarantee the correctness of computation. The rest of the operations do not need bootstrapping operations, thus they are called leveled operations and are usually very fast as a result.

The following sections explain the concept of noise and padding in ciphertexts.

Noise

To ensure security, LWE requires random noise to be added to the message during encryption.

TFHE scheme draws this random noise from a Centered Normal Distribution with a standard deviation parameter. The choice of standard deviation impacts the security level: increasing the standard deviation enhances security while keeping other factors constant.

TFHE-rs encodes the noise in the least significant bits of each plaintext. Each leveled computation increases the value of the noise. If too many computations are performed, the noise will eventually overflow into the message bits and lead to an incorrect result.

The following figure illustrates how the extra bit of noise is incurred during an addition operation.

TFHE-rs enables automatic noise management by performing bootstrapping operations to reset the noise.

Programmable BootStrapping (PBS)

The bootstrapping of TFHE is programmable. This allows any function to be homomorphically computed over an encrypted input, while also reducing the noise. These functions are represented by look-up tables.

In general, the computation of a PBS is preceded or followed by a keyswitch, an operation to change the encryption key. The output ciphertext is then encrypted with the same key as the input one. To do this, two (public) evaluation keys are required: a bootstrapping key and a keyswitching key.

Carry

Since encoded values have a fixed precision, operating on them can produce results that are outside of the original interval. To avoid losing precision or wrapping around the interval, TFHE-rs uses additional bits by defining bits of padding on the most significant bits.

For example, when adding two ciphertexts, the sum could exceed the range of either ciphertext, and thus necessitate a carry that would then be transferred onto the first padding bit. In the following figure, each plaintext over 32 bits has one bit of padding on its left (the most significant bit). After the addition, the padding bit gets consumed to accommodate the carry. We refer to this process as consuming bits of padding. Without any padding-left, further additions may not produce accurate results.

Security

The default parameters for the TFHE-rs library are chosen considering the IND-CPA security model, and are selected with a bootstrapping failure probability fixed at p_error = $2^{-40}$. In particular, it is assumed that the results of decrypted computations are not shared by the secret key owner with any third parties, as such an action can lead to leakage of the secret encryption key. If you are designing an application where decryptions must be shared, you will need to craft custom encryption parameters which are chosen in consideration of the IND-CPA^D security model [1].

Classical public key encryption.

In classical public key encryption, the public key contains a given number of ciphertexts all encrypting the value 0. By setting the number of encryptions to 0 in the public key at m=⌈(n+1)log⁡(q)⌉+λm = \lceil (n+1) \log(q) \rceil + \lambdam=⌈(n+1)log(q)⌉+λ, where nnn is the LWE dimension, qqq is the ciphertext modulus, and λ\lambdaλ is the number of security bits. This construction is secure due to the leftover hash lemma, which relates to the impossibility of breaking the underlying multiple subset sum problem. This guarantees both a high-density subset sum and an exponentially large number of possible associated random vectors per LWE sample (a,b)(a,b)(a,b).

These operations are quite complex to describe in short, you can find more details about these operations (or about TFHE in general) in the .

By default, the cryptographic parameters provided by TFHE-rs ensure at least 128 bits of security. The security has been evaluated using the latest versions of the Lattice Estimator () with red_cost_model = reduction.RC.BDGL16.

[1]

TFHE Deep Dive
repository
Li, Baiyu, et al. "Securing approximate homomorphic encryption using differential privacy." Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.
Noise overtaking the plaintexts after homomorphic addition. Most significant bits are on the left.