Introduction

Fully Homomorphic Encryption (FHE) Explained:

FHE, an acronym for Fully Homomorphic Encryption, originated as a concept in the 1970s. For decades, significant advancement in FHE was elusive. Prior to 2009, the most advanced models allowed limitless additions but restricted to just a single multiplication, falling short of the ideal, which would permit unlimited operations of both kinds.

In a groundbreaking development in 2009, Craig Gentry demonstrated the first model of FHE that could handle an unlimited number of both additions and multiplications.

The core functionality of FHE lies in its ability to process data while it remains encrypted.

Fully Homomorphic Encryption (FHE) allows for calculations on data while it remains encrypted. The term "Fully" in FHE refers to its capability to perform both additive and multiplicative operations on encrypted data.

Additive Homomorphism is represented as:

E(m1) + E(m2) = E(m1 + m2)

Multiplicative Homomorphism is described as:

E(m1) E(m2) = E(m1*m2)

From a mathematical standpoint, FHE is essentially a resolved issue. However, in practical engineering applications, it is still evolving, mainly hindered by performance limitations.

FHE is not currently seen as a standalone solution. It is instead considered a component in a suite of privacy-preserving technologies, expected to be used alongside Zero-Knowledge Proofs (ZKP), Multi-Party Computation (MPC), and Trusted Execution Environments (TEE).

For instance, while FHE ensures data privacy during processing, it does not inherently verify the authenticity of the computation. This gap can be bridged by integrating FHE with ZKP, thereby ensuring both data confidentiality and computation authenticity. Another approach involves combining FHE with MPC to improve efficiency. In this setup, Homomorphic Encryption is employed for linear calculations on encrypted data, while MPC handles non-linear computations.

HOW FHE WORKS?

Ciphertext in the context of Fully Homomorphic Encryption (FHE) comprises encrypted data augmented with random noise. This addition of random noise is a critical aspect, serving to ensure the security of the encrypted data.

In Fully Homomorphic Encryption (FHE), computations are performed on both the data and the noise that has been added for security purposes.

As operations are carried out, this noise progressively accumulates and can potentially spill over into the bits containing the actual data, potentially leading to inaccurate outcomes. The rate at which this noise grows varies depending on the encoding method used. For instance, noise might be inserted at the Least Significant Bit (LSB) level, while the actual message is encoded in the Most Significant Bit (MSB), or vice versa. Additionally, encoding strategies may incorporate padding, which involves the addition of zero bits:

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

In managing noise growth within Fully Homomorphic Encryption (FHE), one approach is to allocate sufficient space for noise expansion. This can enhance speed efficiency, but it inherently limits the number of computations possible, regardless of how much room is provided for noise. This limitation is particularly problematic in contexts like smart contracts, which may require infinite updatability (e.g., ERC-20 contracts).

A further complication arises when space is added for noise growth, restricting operations to only addition and multiplication. Comparisons and non-linear functions in this scenario must be approximated using polynomial approximation. While this may be suitable for machine learning applications, it's less effective for smart contracts. For example, a smart contract might erroneously approve a transaction if a user’s funds are insufficient, due to the limitations in handling non-linear functions like comparisons.

To counteract noise accumulation, bootstrapping can be employed. This process resets the noise level back to a base state, theoretically allowing for indefinite computation. However, bootstrapping is a resource-intensive operation, demanding significant memory and computational power. Therefore, much of FHE research focuses on optimizing and accelerating the bootstrapping process. The detailed technical section on FHE will provide further insights into how bootstrapping functions.

An alternative approach to managing the challenges in Fully Homomorphic Encryption (FHE) is through the use of TFHE, or Torus Fully Homomorphic Encryption. This scheme allows for unlimited computations, precise calculation of arbitrary amounts (as opposed to relying on approximations), and significantly faster bootstrapping compared to traditional FHE methods.

In TFHE, the bootstrapping process involves evaluating a homomorphic lookup table. This capability is crucial because virtually any function can be represented as a lookup table. As a result, TFHE overcomes the limitations related to approximations and the finite number of operations that are typical in standard FHE approaches. By leveraging this method, TFHE enhances both the efficiency and the scope of computations that can be securely performed on encrypted data.

CKKS (Homomorphic Encryption for Arithmetic of Approximate Numbers) is a key Fully Homomorphic Encryption (FHE) scheme known for its ability to perform more operations between bootstraps and handle multiple data points simultaneously using SIMD (Single Instruction/Multiple Data) techniques. This scheme excels in working with large bit representations of integers and floats.

Key Features of CKKS:

1. Approximate Arithmetic: CKKS supports approximate addition and multiplication of encrypted messages.

2. Rescaling Procedure: Manages plaintext magnitude by truncating ciphertext to a smaller modulus, leading to rounding of plaintext.

3. Noise Management: Integrates noise that's considered part of the error in approximate computations, reduced during rescaling.

4. Precision Control: Outputs approximate plaintext values with controlled precision loss.

5. Modulus Growth: Ciphertext modulus size grows linearly with the circuit depth due to rescaling.

6. Evaluating Complex Functions: Efficiently handles functions like exponential, logistic functions, and discrete Fourier transform.

CKKS stands out for its precision and efficiency in handling complex arithmetic operations in FHE.

FHE Use Cases

General Examples

Private On-Chain Computations:

1. Encrypted Transaction Data: All data involved in transactions is encrypted, enhancing the privacy of the transaction details.

2. Encrypted State Updates: When updates to the state of the blockchain are made, they are executed while the data remains encrypted, ensuring continuous privacy.

3. Encrypted On-Chain Data: Any data stored directly on the blockchain is kept in encrypted form, safeguarding it from unauthorized access or visibility.

4. Private Smart Contracts: These contracts operate with both private computation and private data. They use encrypted integers in place of regular integers within the contract, while the rest of the smart contract logic remains unchanged.

FHE in EVM (Example: Zama’s fhEVM)

Zama's fhEVM is an encryption component for blockchain systems, not a standalone blockchain. It includes a threshold protocol for FHE, a Solidity library for smart contracts handling encrypted data, and a dapp SDK for building apps that interact with encrypted blockchain data.

Key Aspects of fhEVM:

1. Global Encryption: Uses a single global FHE public key for encrypting all data.

2. Threshold Protocol for Key Generation: Distributes parts of the global secret key among validators for enhanced security.

3. Encrypted Inputs and Outputs: Inputs are encrypted with the global public key; computations are done on encrypted data by validators.

4. Decryption and Re-encryption: Decryption is possible through the threshold protocol. Data can also be re-encrypted under a different public key without initial decryption.

Special 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.

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.

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

• 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.

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

nft://undefined/undefined/undefined?showBuying=true&showMeta=true

• 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.

• 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).

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”:

• 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:

Where M is the encrypted message, △ = q/p where both q and p are large integers (usually powers of 2), �� are the secret key (k polynomials of at most N power), �� 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:

• 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 Rq, then a GGSW ciphertext is a 3-dimensional matrix of elements from Rq:

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 Rq), and the result will be a new GLWE ciphertext encrypting the sum M+M’.

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.

• 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.

  Further reading

  • zeroknowledge.fm podcast Episode 248: Revisiting FHE with Rand Hindi from Zama.

  • A paper “TFHE: Fast Fully Homomorphic Encryption over the Torus” by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene.

  • A paper “smartFHE: Privacy-Preserving Smart Contracts from Fully Homomorphic Encryption” by Ravital Solomon, Rick Weber, and Ghada Almashaqbeh.

  For immortal

  • 200 pages dissertation about a fully homomorphic encryption scheme by Craig Gentry for those who are excited by the FHE for real (note: it’s from 2009, might be outdated to some extend but fun is promised).

  Sources

  • A workshop “Private Smart Contracts Using Homomorphic Encryption - Rand Hindi, ETHcc 5.”

  • A workshop “Morten Dahl - Homomorphic Encryption in the EVM.”

  • An article “On-chain Blind Auctions Using Homomorphic Encryption and the fhEVM.”

  • An article “Encrypted Key-value Database Using Homomorphic Encryption.”

  • An article “Fully Homomorphic Encryption and Post-Quantum Cryptography.”

  • An article “Private Smart Contracts Using Homomorphic Encryption.”

  • A workshop “Fully Homomorphic Breakfast with Secret Network & Zama.”

  • A twitter thread by Andrew Miller & Co.

  • An article “Solving LLM Privacy with FHE” by Ingonyama

You could donate to Taiko Swap Team by minting this entry, all the fund will be sent back to the community

Join us now 👇👇👇

Twitter | Discord