FHE, Fully Homomorphic Encryption, the Encrypted Computation for Maximum Privacy
Special Thanks to Sputnik from THUBA DAO and Keith Chen from SNZ for the review!
Today we will be talking about FHE, Fully Homomorphic Encryption. I will cover some of the fundamental basics of FHE, and then the current snapshot of the application of FHE.
----------Enjoy!----------
0. Introduction
FHE, Fully Homomorphic Encryption is a cutting-edge cryptographic system that allows calculations on top of encrypted data, and able to decrypt the cipher text back to plain text. It is a field that only started to thrive for 10+ years, and it's still actively in development. Here’s a brief history of FHE, shared by Craig Gentry.
Some people would associate Zero Knowledge Proof with FHE thinking they are alike. But instead, they are fundamentally completely different. A zero-knowledge proof (ZKP) is a cryptographic technique that allows one party (the prover) to demonstrate to another party (the verifier) that a certain statement is true, without revealing any information about the statement itself. In other words, it's a way to prove knowledge of a piece of information without actually revealing the information itself. And it's impossible to retrieve original information from the proof.
1. FHE Definition
The term Fully Homomorphic Encryption means this encryption system can do addition, multiplication, bit operations, and more, on top of Encrypted Data.
If it doesn’t support all operations, it's Partially Homomorphic Encryption. In most cases, PHE multiplication is a bottleneck for PHE to reach FHE. Here is an example to explain why multiplication is the bigger challenge.
Trouble with Multiplication in FHE
Let’s use an example of an easy FHE system:
Encryption: y = a p + m
Decryption: m = y mod p
m is the message, a is any coefficient, and p is a random prime number, which is also the private key.
And Addition and Multiplication would be as follows, given the original message m1 and m2:
y1 = a1 p + m1
y2 = a2 p + m2
Addition:
y1 + y2 = a1 p + a2 p + m1 + m2 = (a1 + a2)p + m1 + m2
Multiplication:
y1 * y2 = (a1 p + m1)(a2 p + m2) = a1 a2 p^2 + m1 a2 p + m2 a1 p + m1 m2
A note here, in order to have multiplication work, m1 * m2 should be less than p, otherwise, the information will be lost. same with addition, m1 + m2 should be less than p
From the above example, you should be able to tell the change of value after addition and multiplication are different where the addition result, number size grows linearly, and multiplication is squared and the size grows quadratically.
This would mean, with limited hardware, and software capability, multiplication operations would lead to an overflow of the numbers.
FHE Encrypted Size
Therefore, a major issue with FHE, is that the encrypted ciphertext might get too large after rounds of calculation. Once it overflows, it will complicate the calculation, and it can grow quite large quite easily if not implemented with “linearity” in mind when doing FHE calculations. (There are ways to reduce the overhead using techniques like Relinearization, but we will skip this for this article. If you are interested, check out a lecture from Vitalik here)
How to deal with Noise in FHE
Noise/Error in FHE is essentially the unwanted bias that is created and accumulated after rounds of FHE operations (addition and multiplication). When the Noise gets too big, then it will have an impact on the original data.
The term Circuit Depth is used to describe the maximum number of operations an FHE scheme can take before the error starts to affect the correctness of ciphertext. The deeper the circuit depth, the more efficient the FHE is, otherwise you would need to perform a process called Bootstrapping to refresh the error. What does it mean?
Bootstrapping
You can think of bootstrapping a process of refreshing the ciphertext. What it does is it will refresh the current ciphertext, which has already done multiple FHE operations, with an encrypted private key/secret key and get a new equivalent ciphertext. The difference between the two ciphertexts is that the refreshed ciphertext has way less noise compared to the previous one. But it also means adding a process like this makes the FHE quite more expensive when compared to the plaintext calculation. Depending on the FHE scheme, the bootstrapping process might become extremely expensive to operate.
2. Current Stage of FHE
Latest Technologies
OpenFHE: An open-source FHE library that supports FHE schemes including BFV, BGV, CKKS, DM/FHEW, CGGI/TFHE, and LMKCDEY.
DM(FHEW)/CGGI(TFHE): A bool gate FHE scheme that can perform bootstrapping in a fraction of a second. CGGI and DM are similar in design but CGGI is more memory efficient. However, the representation bits are recommended to be set between 3-8 bits at most, otherwise, the computation cost will double beyond this point.
CKKS: A large precision FHE scheme that is optimized for float point operations. Unlike DM/CGGI where they are one scalar operation at a time. CKKS is designed to work with vectors, which means it supports parallel processing due to its extensive amount of data stored in one vector. This makes CKKS harder to bootstrap but much faster to calculate due to SIMD style design
BFV/BGV: BGV is essentially very similar to CKKS, as it is also a SIMD-style-designed vector calculation scheme. But unlike CKKS, it is not for float numbers but for integers, exact numbers.
A benchmark of all of these FHE schemes can be found here.
Fhenix is an FHE-enabled EVM protocol that provides TFHE features natively for solidity developers. It was made possible using fhEVM, a Fully Homomorphic EVM co-built by the Fhenix team and Zama. In the demo implementation of fhEVM of Zama, we could tell that FHE operations were implemented into EVM as precompiled contracts for native environment access instead of running on the original EVM. Its Encryption scheme is also designed to work with LWE(Learning With Error), which makes it quantum-resistant.
Here are some of the benchmarks of fhEVM’s TFHE operations:
fhEVM TFHE operation speed
fhEVM ciphertext and key size
You can take a look at the original EVM’s instruction set bench here. Although the hardware these two bench tests use for fhEVM and EVM is different, we can still take a rough estimation. When comparing Multiplication, normal EVM multiplication instruction would only take 10 nanoseconds as FHE multiplication takes about 10^8 nanoseconds for the operations. And size of the cipher text is also fairly larger than the original text, how to store ciphertexts in packed form and still be able to conduct FHE operations is still ongoing research for the Fhenix and Zama team.
3. Future of FHE?
There are still a lot of bottlenecks for FHE need to be solved for real-world applications:
High Computation Overload: Simple tasks like addition and multiplication can get highly resource-intensive in FHE operations, making FHE calculation unscalable.
Large Data: for simple information in plaintext, converting it into ciphertext, could potentially grow the representation size by several digits. On top of that, any operations done on it would mean potential growth of the ciphertext size, which will take up storage and memory for any operations.
Key Management: Every Encryption will be equipped with its own Key, which means the growth of encrypted information would be equivalent to the linear growth of keys, and this could be problematic and unmanageable.
Noise: As mentioned in the FHE definition section, noise is inevitable when doing FHE operations, finding efficient ways, and mechanisms to minimize the noise impact on the ciphertext is also a key direction in improving FHE efficiency.
Therefore, the future of FHE, in my opinion, especially for the blockchain space would be:
Finding more ways to reduce the size of ciphertext. It is essential as ciphertext data will be stored on-chain, and the size of the data directly affects the expense of the transactions.
Improve FHE operation speed. If FHE is implemented in EVM, then the requirements to facilitate such nodes will be even higher than now, and block-producing speed might slow down if a block has transactions with extensive FHE operations.
Apply an FHE scheme that can operate SIMD-like vector calculations for batch calculations in blockchain to accelerate the calculation.
Key Management Layer in the blockchain? Since it's impossible to share your private key, what's the best way to co-own a private key and manage it together?