FHE: Successor to ZK? A Brief History of FHE Technological Development

On May 5, 2024, Ethereum co-founder Vitalik Buterin posted a thread about Fully Homomorphic Encryption (FHE), reigniting the market’s enthusiasm for this new algorithm. While the tweet was a repost of an old article from 2020, it sparked genuine interest in the cryptographic community.

In his article, Vitalik delved deep into the concept, applications, technical details, and challenges of Fully Homomorphic Encryption. FHE has long been considered one of cryptography’s “holy grails,” as it allows a third party to perform computations on encrypted data and obtain an encrypted result without decrypting the data.

Since 2012, he has been discussing algorithm optimizations such as leveraging techniques like Bootstrapping and Ring Learning With Errors (RLWE) to enhance efficiency.

Depending on actual implementation, homomorphic encryption can be broadly categorized into three types:

1. Partially Homomorphic Encryption: Allows only limited operations on encrypted data, such as addition or multiplication.
2. Somewhat Homomorphic Encryption: Permits a limited number of addition and multiplication operations.
3. Fully Homomorphic Encryption: Enables an unlimited number of addition and multiplication operations, facilitating arbitrary computations on encrypted data.

When integrated with blockchain technology, FHE can deploy smart contracts on the blockchain that can perform computations without decryption, thereby safeguarding user privacy and enabling fully private transactions.

FHE’s journey can be traced back to 2009 when IBM’s Craig Gentry first proposed a fully homomorphic algorithm based on ideal lattices, marking a significant advancement in the theoretical understanding of homomorphic encryption and gradually leading to engineering implementations.

Ideal lattices are a mathematical structure that allows users to define a set of points in multidimensional space that satisfy specific linear relationships. In Gentry’s scheme, ideal lattices are used to represent keys and encrypted data, enabling encrypted data to support complex computational operations while preserving privacy.

In 2012, Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan introduced the BGV scheme, one of the second-generation FHE schemes. Its most significant contribution was modular switching, which effectively controls ciphertext noise growth, thereby constructing Leveled FHE capable of performing homomorphic computations with a given computation depth.

Modular switching involves transitioning between different moduli during homomorphic operations to manage and control ciphertext dimension expansion. In the BGV scheme, modular switching works through several steps:

1. Selecting appropriate moduli based on the encryption operation’s needs.
2. Switching moduli when reaching a certain modulus limit during homomorphic operations.
3. Adjusting dimensions after switching moduli to meet the new modulus requirements.
4. Repeating operations under the new modulus until reaching the desired depth or completing specific encryption tasks.

BGV’s modular switching technique effectively addresses the ciphertext dimension expansion issue and reduces noise growth due to dimension expansion, thereby improving the overall performance of homomorphic encryption.

Subsequently, fully homomorphic encryption technology continued to evolve, leading to improved schemes like TFHE, belonging to the GSW branch, which is currently one of the fastest fully homomorphic encryption schemes. These advancements not only enhance computational efficiency but also expand FHE’s application scope in fields like cloud computing, big data, and artificial intelligence.

Compared to second-generation FHE schemes, TFHE significantly improves encryption operation speed by introducing Bootstrapping technology. On desktop computers, TFHE’s response time can reach the millisecond level.

Furthermore, compared to zero-knowledge proofs (ZKPs), FHE offers a different approach to data privacy protection. ZKPs primarily address the consistency of data transmission in encrypted states, while FHE allows arbitrary homomorphic computations on encrypted data, making it more flexible and powerful for handling complex computational tasks.

Specifically, FHE enables direct computation on encrypted data without decryption. This capability makes FHE particularly suitable for cases requiring complex computations in encrypted states, such as large-scale data analysis and machine learning model training. In contrast, ZKPs are mainly used to prove the truthfulness of a fact without directly manipulating data, verifying information correctness through interactive or non-interactive protocols without revealing any details about the input information.

If it’s necessary to expose or analyze the data while protecting privacy, such as confirming transactions on public chains by third-party nodes while hiding specific information, FHE can organize transactions while allowing third-party nodes to fetch FHE-encrypted ciphertexts for verification, and block explorers or oracles can also index data.

ZK Leads Practicality over FHE

Currently, ZK has become the foundational infrastructure of the cryptocurrency industry. ZK technology has been explored theoretically and practically in various aspects like Rollup and Bitcoin state compression. In CoinW’s Layer2 area, nearly half are ZK-based projects.

Moreover, in the burgeoning BTC Layer 2 market, ZK is the only effective solution for compressing BTC Layer 2 data back to the Bitcoin mainnet. Bitcoin’s data storage is relatively expensive, thus any DA solution that can compress data is worth giving a shot. For example, in Vitalik’s other proposal, Binius envisions efficiently encoding ZK circuits in binary.

On Ethereum, ZK-proof systems can interact with smart contracts. However, Bitcoin’s scripting capabilities lack Turing completeness, so developers need to find alternative ways to provide security and final confirmation for transactions on BTC Layer 2.

Specifically, Binius attempts to represent program states using polynomials and transform them into mathematical equations through a series of mathematical tricks. By constructing a proof system that runs directly on 0s and 1s to improve speed, Binius takes a different implementation approach from commonly used SNARKs and STARKs. Using binary fields provides a unique advantage, as computations can be directly performed on 0s and 1s, matching the binary operation mode of computers.

Additionally, if a binary-based ZK proof system can be implemented, small fields can also improve proof generation efficiency because they allow complex computations while maintaining small values, significantly reducing the complexity of ZK generation and ultimately reducing block space consumption.

The standard draft for FHE was released in 2018 and updated to version 1.1 in November 2023, marking progress in the standardization of FHE technology. Compared to the rapid advancement of ZK, FHE’s current project ecosystem and funding levels are unsatisfactory and still in the very early stages of development.

Another aspect is hardware acceleration. From a performance perspective, ZK hardware acceleration has taken the first step towards practicality. Known GPU provers can improve computational efficiency by about 5 to 10 times. Additionally, ASIC/FPGA accelerators are also used to optimize ZK-proof programs, while dedicated hardware for FHE blockchain applications has not yet been widely promoted.

Conclusion

Looking back, ZK’s rapid development began after Ethereum established its Rollup-centric scaling system. Currently, FHE’s development is still in the early stage, and its practical application and large-scale landing methods need to find the most suitable use cases for the blockchain industry. However, its solid theoretical foundation and tremendous potential give it the ability to challenge ZK.