Introduction to FHE: What is FHE, how does FHE work, how is it connected to ZK and MPC, what are the FHE use cases in and outside of the blockchain, etc.

November 23rd, 2023

Special thanks to Leo Fan for invaluable inputs and to Tomer Solberg for feedback and review.

TL;DR

In this article, we briefly explain what FHE is and how it works, consider its use cases in and outside of blockchain, and cover open issues and constraints. Finally, we also mention some blockchain FHE projects and provide a list for further reading.

Content

Introduction
How FHE works
FHE use cases
FHE concerns
FHE technical details
- A side note on lattices
- Brief (not really brief) observation of how the TFHE works
Current FHE projects in blockchain
FHE outside blockchain
Further reading

Disclaimer: This article sometimes refers to Secret Network (FHE-based blockchain with customizable privacy) and Zama (FHE-based cryptographic tools) as illustrations. For a more extended list of the projects researching and developing FHE, check the section “Current FHE projects in blockchain.”

Introduction

FHE stands for Fully Homomorphic Encryption.
FHE was first proposed in the 1970s. However, until 2009, there hadn’t been much progress in achieving Fully Homomorphic Encryption. The best construction offered an arbitrary amount of additions but only one multiplication (while the desired result was an arbitrary amount of both additions and multiplications).
Craig Gentry made a seminal leap in 2009, showing the first construction of FHE supporting an arbitrary amount of additions and multiplications.
FHE enables encrypted data processing.

Diagram source: the workshop “Morten Dahl - Homomorphic Encryption in the EVM.”

That is, it makes computations on encrypted data.
“Fully” stands for additive and multiplicative:

Additive Homomorphism: $E(m_1) + E(m_2) = E(m_1 + m_2)$

Multiplicative homomorphism: $E(m_1) * E(m_2) = E(m_1 * m_2)$
FHE is a solved problem from a mathematical perspective. From an engineering perspective, it’s a work in progress with the core bottleneck in performance.
FHE is not considered a self-sufficient solution (at least for now) but rather one of the components to provide privacy that is expected to work with ZKP, MPC, and TEE.

For example, while FHE preserves data privacy during computation, it does not guarantee the computation authenticity. To mitigate it, FHE can be combined with ZKP to achieve both confidentiality and computation authenticity. Another example is combining FHE and MPC to handle the efficiency problem. Then, the HE is used to do linear computations over encrypted data, and MPC deals with non-linear computation.

Diagram source: the workshop “Morten Dahl - Homomorphic Encryption in the EVM.”

How FHE works

Ciphertext = encrypted data + noise. That is, random noise is added to the encrypted data to guarantee security.

Diagram source: the article “Private Smart Contracts Using Homomorphic Encryption”

However, now all the computations are done not only on data but on data together with added noise.
Furthermore, after several operations, the noise starts to grow and overflows on the bits of actual data, which might lead to incorrect results. The specific growth speed depends on which encoding is used. It can be, for example, adding noise in the Least Significant Bit (LSB) while adding the message in the Most Significant Bit (MSB) or the opposite. It can also include padding (adding zero bits):

Diagram source: the article “TFHE Deep Dive - Part II - Encodings and linear leveled operations” by zama.

Or encode the message and the error as a single thing:

Diagram source: the article “TFHE Deep Dive - Part II - Encodings and linear leveled operations” by zama.

To handle noise growth, one can just provide enough space for noise to grow. Then, it becomes pretty efficient in terms of speed, but the number of available computations is anyway limited (however large the room for noise is). And for smart contracts, it doesn’t work as sometimes they are infinitely updatable (e.g., ERC-20).
Another problem is that by adding space for noise, one can do only addition and multiplication, while comparisons and non-linear functions are approximated using polynomial approximation. It works fine for Machine Learning cases, but for a smart contract, it might not be the case (e.g., the user doesn’t have enough funds, but the transaction passed – not cool).
To reduce the noise, one can also use bootstrapping. Bootstrapping is a special operation that resets the noise to its nominal level. It enables computing forever, but it is a slow and costly (both in terms of memory consumption and computational cost) operation. That is why, very often, when we talk about FHE research, we’re, in fact, talking about bootstrapping acceleration. The “FHE technical details” section will glimpse how bootstrapping works.
Another solution is TFHE – a scheme that enables infinite computations, exact arbitrary amounts (instead of approximation), and very fast bootstrapping. With TFHE, the bootstrapping operation evaluates a homomorphic lookup table. Any function can be encoded as a lookup table. So, TFHE removes the approximation and the limit in the number of operations.

Table source: The workshop "Private Smart Contracts Using Homomorphic Encryption - Rand Hindi, ETHcc 5”

Another FHE scheme that is worth mentioning is CKKS (Homomorphic Encryption for Arithmetic of Approximate Numbers). Its performance is expected to be close to TFHE, but its strong points differ. With CKKS, one can perform more operations between bootstraps, operate on multiple data simultaneously (in SIMD, Single Instruction/Multiple Data), and work with larger bit representations of integers and floats.
CKKS supports an approximate addition and multiplication of encrypted messages and an alternative rescaling procedure for managing the magnitude of plaintext. This procedure truncates a ciphertext into a smaller modulus, leading to plaintext rounding.
The main idea is to add a noise following significant figures that contain a main message. This noise is originally added to the plaintext for security but is considered a part of an error occurring during approximate computations that are reduced along with plaintext by rescaling. As a result, the decryption structure outputs an approximate value of plaintext with a predetermined precision. The precision loss during evaluation is bounded by the depth of a circuit, and it exceeds at most one more bit compared to unencrypted approximate arithmetic such as floating-point operations.
The bit size of the ciphertext modulus grows linearly with the depth of the circuit being evaluated due to the rescaling procedure. CKKS can also be applied to efficiently evaluate transcendental functions such as multiplicative inverse, exponential function, logistic function and discrete Fourier transform.
Another example of current FHE performance provided by Ingonyama can be found in this article. It answers the question, “How much time would it take to run LLM inference with FHE?”

FHE use cases

General examples

Private on-chain computations:
- Encrypted transaction data: data included in transactions is encrypted.
- Encrypted state updates: states are updated while remaining encrypted.
- Encrypted on-chain data: data stored on-chain remains encrypted.
- Private Smart Contracts: private computation + private data
  - Instead of integers, there are encrypted integers in the smart contract. No other changes should be made to the regular smart contract writing logic.
  - The trickiest part is how the smart contract can check the balances if they are encrypted.
FHE in EVM (taking as an example the Zama’s fhEVM)
- fhEVM is not a blockchain but an encryption component that other blockchains can use. It also includes the threshold protocol optimized for FHE, a solidity library to express smart contracts operating on encrypted data and dapp SDK for building dapps to encrypt data properly and interact with the encrypted blockchain.
- Mechanism behind fhEVM
  - Everything is encrypted under a single global FHE public key.
  - The global secret key is generated using a threshold protocol (parts of the secret key are distributed among validators).
  - The inputs are encrypted using the FHE public key.
  - Computations on encrypted data are done locally by validators.
  - Values can be decrypted by validators using the threshold protocol.
  - Values can also be re-encrypted (without decryption) under another public key (let’s denote it “public key a”) using a threshold protocol. Re-encrypted values can be decrypted by the public key owner.

Specific examples

On-chain Blind Auctions
- Two phases: a bidding and a claim phase. The bidding phase consists of users bidding an encrypted amount of tokens (using the encrypted ERC20 contract). When the auction ends, the contract homomorphically determines the highest bidder.
- In the end, the contract only discloses the winning bidder while keeping the winning bid value and non-winning bid values private.
A marketplace where buy and sell orders are not visible to the public before they are filled.
Confidential ERC-20 Tokens.
Encrypted Key-value Database.
Trustless bridges: an encrypted key is used to sign bridge transactions homomorphically.
Confidential voting: encrypted choices and token amounts.

FHE concerns

In the case of the FHE blockchain, there is one key for the whole network. Who holds the decryption key? This “who” will define the security level. As suggested by Secret Network, the secret key pieces are distributed to each oracle node – that is, threshold MPC is used. There are a lot of issues about MPC security and a lot of doubts about FHE security relying on MPC security.
One way to improve the security assumption is to partially run the secret decryption inside the TEE. However, if for security TEE is optional, there is another reason to use it: problem with erasure. When Oracle nodes should be rotated, it should be guaranteed that the previous node has deleted the share of the key that it had.

However, compared to vanilla MPC, FHE is better as it outsources the bulk of the computation to totally untrusted nodes and then only has a semi-trusted quorum for threshold decryption, unlike in MPC, where that quorum does all the work.

How it works:
1. The pieces of the secret key are generated and shared among validators.
2. Each validator does a partial decryption.
3. The partial decryptions are aggregated to yield the full decrypted value.
Its security holds under an assumption of 2/3 honest validators. However, the validator set should be fixed and limited.
In the specific case of Secret Network, the network validators are required to make assertions during the consensus time. How should they access the decrypted data? It can’t be done using “vanilla oracle” as it would break the privacy. The solution is the two-round consensus mechanism. The first round is the consensus on what should be decrypted. That is, the Oracle waits until most validators send it the same request for decryption. Then, the Oracle decrypts it. Then, the validators update the chain state and append the block to the blockchain.
How to prevent users from decrypting the data of other users? What if the user just writes a contract that decrypts the inputs and provides someone else’s encrypted data as inputs for this contract?The solution is Zero-Knowledge Proof! The user should provide a ZKP of every encrypted input that they are sending to the network to prove that the user really knows the value they are sending in an encrypted way.
The key technical concern about FHE is its slowness. Its performance is much slower than known alternatives.

How much slower?

FHE performance depends on the hardware acceleration and is not expected to be cheap until ASICs are here.
According to Leo Fan, FHE overhead is approximately 10,000x over unencrypted computation. Using GPUs and FPGAs achieves 2 orders of magnitude better performance than CPUs. Designing an ASIC for FHE can achieve 3-4 orders of magnitude performance improvement (over CPU), almost closing the 10,000x gap. ”If the application requires an interaction-less solution, then ASIC seems to be the best option. Since performance and ciphertext blowup of HE for some simple computation, such as linear computation, are satisfying, GPU/FPGA-accelerated HE combined with MPC techniques can be used in some applications with a good network connection.”
If one can generate proof of correct FHE execution to avoid execution redundancy, we can have provable FHE (similar to ZK) and zk-FHE-rollups.

FHE technical details

Security

To think about FHE security, assume we have four parties: an encryptor, a decryptor, someone doing the FHE computation, and an adversary. It might be the case that an encryptor and a decryptor are the same person, then we deal with symmetric FHE. It might be the case that there are multiple encryptors. The security assumption of FHE assumes that all of these parties might be dishonest.

Cryptography

FHE is a lattice-based construction. The initially proposed FHE is based on ideal lattices that, since then, have been shown to be insecure.

A side note on what lattices are

A lattice is a periodic grid of points in n-dimensional space. There can be an infinite amount of basis. The length of the basis is the length of its longest vector. We call a “short basis” the one that minimizes the length of the longest vector.
The Short Vector Lattice Problem sounds as follows: given an arbitrary basis b, find a non-zero lattice vector that is as short as possible.

Diagram source

Another version of this problem is called the Decoding Problem. In this version, one is asked to find a target point within the defined area (not the shortest but no longer than some specific value).

Diagram source: CryptoBook

The core difference between these two problems is that the Short Vector Problem asks for a unique vector. Under the Decoding Problem, we are guaranteed that there will always be multiple points within some fixed large enough radius.

If you think about this problem in 2-dimensional space, it’s simple: a lattice is just an infinite set of dots across a plane. The dots are generated by taking integer linear combinations of two “basis vectors.” The hard mathematical problem is finding two short vectors that generate the lattice. In the diagram below, black vectors are “basic vectors,” red vectors are a solution to the “hard mathematical problem”:

Diagram source: the article “Fully Homomorphic Encryption and Post-Quantum Cryptography”

In two dimensions, this problem seems ridiculously easy. However, as we scale the number of dimensions higher, it becomes very difficult indeed. In particular, the complexity grows exponentially while the number of dimensions goes up. With a large enough number of dimensions, it becomes so difficult, that we do not believe that even a quantum computer will be able to solve this hard problem.
The important parameters of this problem are the exact dimension on which to base cryptography and the choice of initial basic vectors.
Lattices are suggested to be the core mechanism standing behind post-quantum primitives.
Many modified FHE approaches (such as FHEW, TFHE, BGV, BFV, and CKKS) are based on Learning-with-Errors (LWE), which, in its terms, is based on the lattices problem.

Brief (not really brief) observation of how the TFHE works

T in TFHE stands for Torus, a mathematical structure resembling a donut.
The scheme's security is based on a hard lattice problem called LWE (Learning With Errors).
TFHE is distinguished from the others because it proposes a special bootstrapping, which is very fast and able to evaluate a function at the same time as it reduces the noise.

Part 1: defining ciphertexts

In particular, TFHE uses three types of ciphertexts: LWE, RLWE, and RGSW, as they all have different properties that will be useful in the homomorphic operations. As a short glimpse on these ciphertexts, let’s look at the Generalized LWE (GLWE) – the generalization encompassing both LWE and RLWE. The message encryption can be represented as the following:

Diagram source: the article “TFHE Deep Dive - Part I - Ciphertext types” by zama.

Where M is the encrypted message, △ = q/p where both q and p are large integers (usually powers of 2), $S_i$ are the secret key (k polynomials of at most N power), $A_i$ are the randomly sampled coefficients (called “mask”), and E is noise error. Both the “mask” and the noise error are sampled for each encryption, meaning that even the encryption of the same message will differ.

To be able to decrypt the message, |E| should be less than △/2 (|E|<△/2). If this condition holds, the decryption will look as follows:

Diagram source: the article “TFHE Deep Dive - Part I - Ciphertext types” by zama.

Going back to the bootstrapping, a tool for noise reduction we briefly introduced in the “How FHE works” section it is applied exactly at the two-step decryption described in the previous abstract. In particular, it takes step 1 computations in the exponent of a monomial X and then uses this new monomial to rotate a Look-Up Table (LUT) that evaluates the second decryption step (rescale and rounding).
To go from GLWE to LWE, take N = 1 (N is the max possible power of polynomials in S).
To go from GLWE to RLWE, take k = 1 (number of polynomials in S) and N – a power of 2.
To briefly define GGSW, we have to briefly define GLev, that is, in fact, a vector of GLWE ciphertexts. Then, a GGSW ciphertext is a vector of GLev ciphertexts. And if GLWE ciphertext is a vector of elements from $R_q$ , then a GGSW ciphertext is a 3-dimensional matrix of elements from $R_q$ :

Diagram source: the article “TFHE Deep Dive - Part I - Ciphertext types” by zama.

Part 2: operations on ciphertexts homomorphic addition

Assume we have two GLWE ciphertexts encrypting the messages M and M’. Then, we can add every component of the two ciphertexts (in $R_q$ ), and the result will be a new GLWE ciphertext encrypting the sum M+M’.

Diagram source: the article “TFHE Deep Dive - Part II - Encodings and linear leveled operations” by zama.

To perform the homomorphic addition, we add in $R_q$ the components term wise:
$A_0^{(+)} = A_0 + A_0', A_1^{(+)} = A_1 + A_1', B^{(+)} = B + B'$

Homomorphic multiplication by unencrypted constants

Assume we have a GLWE ciphertext encrypting a message M and a small constant polynomial Λ. Then, we can multiply the polynomial Λ to every component of the ciphertext M, and the result will be a new GLWE ciphertext encrypting the product Λ⋅M.

Diagram source: the article “TFHE Deep Dive - Part II - Encodings and linear leveled operations”.

For decryption, one uses the same approach described for GLWE.
To add together two GLev ciphertexts or two GGSW ciphertexts, it will be sufficient to add together the corresponding GLWE ciphertexts composing them. Suppose we want to multiply a GLev ciphertext or a GGSW ciphertext times a small constant polynomial Λ. In that case, it will be sufficient to multiply all the GLWE ciphertexts, composing them times Λ.
However, this works only if the constant is small. If the constant is large, the noise grows proportionally with respect to its size. And if we multiply each element of ciphertext by a large constant, the noise compromises the result. To solve the issue, the large constant is decomposed into a small base:

To make the decomposition invertible, one uses GLev encryption

That was a short glimpse into what FHE and TFHE are about under the hood. For more details, check an awesome explanation by Zama (part 1, part 2, part 3, part 4).

Another option was the schemes based on the NTRU assumption. However, they were also shown to be insecure.
As for now, only the LWE approach is assumed to be applicable. One of the disadvantages is that LWE-style encryption requires each ciphertext to consist of two elements, whereas the main advantage of the NTRU-based schemes is that a ciphertext consists of simply one ring element. Another concern is that it’s, in some sense, putting all the security eggs into one basket.

Current FHE projects in blockchain

Zama – open-source cryptographic tools for privacy protection.
Secret Network – blockchain with customizable privacy.
Sunscreen – a compiler for fully homomorphic encryption and zero-knowledge proofs.
Fhenix – a blockchain powered by fully homomorphic encryption.
Ingonyama – hardware acceleration.
Cysic – hardware acceleration.
Mind Network – private rollup.

FHE outside blockchain

Disclaimer: The inputs for this section were kindly provided by Leo Fan, the co-founder at Cysic.

FHE can be applied in many cases where privacy-preserving computation is required.

Other than in blockchain, FHE is primarily used in privacy-preserving Machine Learning. In this scenario, for example, the client wants to use his private data and external AI model.

The client uses FHE to encrypt the data and then upload the ciphertext to the server. The server runs homomorphic computation of the AI model over the ciphertext. When the computation is done, the server sends back the encrypted result, and the client can decrypt it and learn the result.

Based on the security and functionality of FHE, the confidentiality of the client’s data and the correctness of the result can be guaranteed. One outstanding property of this application is that the client does not need to interact with the server during the evaluation process.

TL;DR

Introduction

How FHE works

FHE use cases

FHE concerns

FHE technical details

A side note on what lattices are

Brief (not really brief) observation of how the TFHE works

Current FHE projects in blockchain

FHE outside blockchain

Further reading

Join us 💗

Follow us 🥁

Contribute 🤓