Part 1: An Introduction to FHE, ZKPs & MPC, and The State of FHE Development Today

This post was written by 0xZoey. Special thanks to Janmajaya, Enrico, and Owen who generously gave their time and expertise to review this piece. Your valuable contributions and feedback have greatly enhanced the quality and depth of this work.

Find Part 2: Fundamental Concepts, FHE Development, Applied FHE, Challenges and Open Problems here…

What is FHE?

Present privacy technology ensures secure communication and storage, encrypting our emails during transit and safeguarding databases in storage. However, accessing data for processing requires the data to be first decrypted. What if secure processing could occur without compromising data privacy?

FHE allows computation over encrypted data

Fully Homomorphic Encryption (FHE) is a technology that allows computation over encrypted data, where only the owner of the key can decrypt the result of the computation.

This article focuses on the current state of FHE, fundamental concepts, applied FHE, and design challenges ahead. It is meant to help users understand the thought framework around applied FHE without requiring the reader to understand complex math or cryptography.

The idea for FHE was initially proposed in 1978 by Rivest, Adleman, and Dertouzous (the "R" and "A" of RSA). FHE is an extension of public key cryptography; the encryption is "homomorphic" because it works on the principle that for every function performed on unencrypted text (Plaintext), there is an equivalent function for encrypted text (Ciphertext).

Homomorphic Encryption

FHE shares fundamental components with traditional cryptography like encryption, decryption, and key generation. In addition to this, it uniquely enables arithmetic operations such as addition and multiplication on ciphertexts.

There are generally four categories of homomorphic encryption:

In the past, the difficulty in achieving FHE  was due to the "noise" that accumulated with every subsequent operation. The excess overflow in noise eventually makes decryption impossible. Craig Gentry proposed the first FHE scheme in 2009, where he solved this problem with a method called bootstrapping. Bootstrapping is used to recursively evaluate the decryption circuit to reduce and manage noise accumulation.

Why is FHE important?

Fully Homomorphic Encryption (FHE) signifies a groundbreaking shift in privacy, enabling data-centric systems to preserve privacy with minimal data exposure inherently. FHE, built using lattice-based cryptography, also offers the notable advantage of being post-quantum resistant, ensuring robust security against future potential threats from quantum computing.

Some general FHE use cases include:

General FHE Use Cases

Fully Homomorphic Encryption (FHE) holds immense significance in blockchain technology because it can perform encrypted data computations within a trustless environment. We won't dive into the importance of privacy on the blockchain and how off-chain ZKPs are not the complete solution, but Wei Dai's article Navigating Privacy on Public Blockchains is a great primer.

Here are some theoretical blockchain use cases that FHE could facilitate:

FHE: Blockchain Use Cases

The applied use cases for FHE are far-reaching, there are non-trivial technical challenges to overcome, and many are still being explored today. At its core, FHE ensures secure data processing, which, combined with other cryptographic primitives, can be incredibly powerful. In our exploration of Applied FHE, we dive deeper into real-world applications and use cases.

ZKP, MPC, & FHE

The terms ZKPs, MPC, and FHE have often been misused and interchanged and have been the source of much confusion. The post, Beyond Zero-Knowledge: What's Next in Programmable Cryptography? provides a succinct overview and comparisons of Zero-Knowledge Proofs (ZKPs), Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE) and Indistinguishability Obfuscation (iO). All fall under the broader umbrella of programmable cryptography.

To briefly summarize how the three concepts are connected:

Multi-Party Computation (MPC): MPC, when described as a general function, is any setup where mutually distrustful parties can individually provide inputs (private to others) to collaboratively compute a public outcome.  MPC can be used as the term used to describe the technology itself, where randomized data shares from each individual are delegated for compute across servers.

MPC

To add to the confusion, it is also often used to describe MPC use cases, most notably in the context of Distributed Key Generation (DKG) and Threshold Signature Schemes (TSS).

Three leading technologies form the building blocks of MPC applications: Garbled Circuits (GC), Linear Secret Sharing Schemes (LSSS), and Fully Homomorphic Encryption (FHE). These can be used both conjunctively or exclusively.

MPC & ZKPs

Zero-Knowledge Proofs (ZKPs): A method that allows a single party (prover) to prove to another party (verifier) knowledge about a piece of data without revealing the data itself. Using both public and private inputs, ZKPs enable the prover to present a true or false output to the verifier.

ZKPs

In Web 3 applications, the integration of ZKPs alongside FHE becomes crucial for constructing private and secure systems. ZKPs are vital because they can be used to generate proofs of correctly constructed FHE ciphertexts. Otherwise, users can encrypt any unverified gibberish. Hence corrupting the entire FHE circuit evaluation.

Note the difference in ZKPs, FHE, and MPCs, where the input element of each primitive is distinct when evaluating the exposure of private data.

While MPC is network bound, FHE and ZKPs are compute bound. The three primitives also differ regarding relative computation costs and interactiveness required between parties.

ZKPs, MPC, FHE, computation costs and interactiveness

In summary,

FHE is an extension of public key cryptography, not a replacement for ZKPs or MPC. Each can act as an individual building block and serve a distinct cryptographic purpose. An assessment needs to be made on where and which primitive should be applied within different applications.

The State of FHE Today

Early concepts of FHE developed in the 1970s-90s laid the theoretical groundwork for homomorphic encryption. However, the real breakthrough came with Gentry's solution for FHE in 2009. The initial construction needed to be faster to be practically applied. Performance at the time was close to 30mins per bit operation and only applicable in a single key setting. Much of the research published following Gentry's paper has been focused on performance improvements that address these issues through:

FHE is not possible with Ethereum today due to the size of ciphertexts and the cost of computation on-chain. It is estimated with the current rate of hardware acceleration, we may see applications in production by 2025.

Zama’s implementation of fhEVM is a fork of Ethereum; they have several tools available:

There are some challenges with ZAMA's fhEVM approach that are yet to be improved. Networks using ZAMA's fhEVM are limited to about 2 FHE transactions per second (tps). Compared to Ethereum's ~15 tps this is not far off; however, it will need to be greatly improved for many time-sensitive applications.

Additionally, operations on encrypted integers are much more difficult to perform than on plaintext integers. For example, on an Amazon m6i.metal machine (one of Amazon's top machines costing $2-4k per month to operate):

There are also limitations to the size of unsigned integers available in the fhEVM context. Encrypted uint32 values are the largest possible in the fhEVM, while uint256 are the largest in the standard EVM and are used frequently by many protocols on Ethereum. Due to the challenge of operating on encrypted values in the fhEVM it is currently unreasonable to run validators at home, which makes this more suitable for networks with a smaller, more trusted validator set.

Sunscreen is another project actively working on FHE; they have a Rust-based FHE compiler using the BFV scheme with a playground. They’ve deployed a blind auction proof of concept on SepoliaETH.

Fhenix, a team working on a modular “FHE blockchain extension”, plans on launching their testnet in January 2024. They also recently released their whitepaper on FHE-Rollups.

In the last five years, significant advancements have been made to make FHE more usable. Shruthi Gorantala's framework for thinking about FHE development as a hierarchy of needs is particularly helpful. The performance improvements listed above address deficiency needs and are contained in Layers 1-3 within the FHE tech stack. For FHE to realize its full potential, we also need to address the growth needs listed in Layers 4-5.

FHE Hierarchy of Needs

A critical aspect of systems integration is figuring out how to combine FHE technology with other privacy-enhancing primitives like ZKPs and MPC in a way that suits each unique trust model and protocol.