Gate Ventures Research Institute: FHE, Wearing Harry Potter's Invisibility Cloak

What is FHE

FHE process, image source: Data Privacy Made Easy

FHE (Fully Homomorphic Encryption) is an advanced encryption technology that supports direct computation on encrypted data. This means that data can be processed while protecting privacy. FHE has multiple applicable scenarios, especially in the fields of data processing and analysis under privacy protection, such as finance, healthcare, cloud computing, machine learning, voting systems, internet of things, blockchain privacy protection, etc. However, commercialization still requires some time, and the main issue lies in the enormous computation and memory overhead brought by its algorithm, which has poor scalability. Next, we will briefly walk through the basic principles of the algorithm and focus on the problems faced by this cryptographic algorithm.

Basic Principles

Homomorphic Encryption Illustration

First of all, we need to perform calculations on the encrypted data and still get the same result, as visualized in the above figure. This is our basic goal. In cryptography, polynomials are commonly used to hide the information of the plaintext, because polynomials can be transformed into linear algebra problems and vector calculation problems, which are convenient for highly optimized modern computers (such as parallel computing) to perform calculations on vectors. For example, 3 x 2 + 2 x + 1 can be represented as the vector [1, 2, 3].

Assuming that we want to encryption 2, in a simplified HE system, we might:

• Choose a Secret Key polynomial, such as s(x) = 3 x 2 + 2 x + 1
• Generate a random polynomial, such as a(x) = 2 x 2 + 5 x + 3
• Generate a small ‘error’ polynomial, such as e(x) = -1 x + 2 c(x) = 2 + a(x)*s(x) + e(x)

Let’s talk about why we need to do this. Now, let’s assume we have obtained the Ciphertext c(x). If we want to get the Plaintext m, the formula is c(x) - e(x) - a(x)*s(x) = 2. Here, let’s assume the random polynomial a(x) is public. As long as we keep our Secret Key s(x) confidential, if we know s(x) and add it to c(x) as a small error, theoretically we can ignore it and obtain the Plaintext m.

Here is the first question, there are so many polynomials, how to choose the polynomial? How large should the degree of the polynomial be? In fact, the degree of the polynomial is determined by the implementation of the HE Algorithm. It is usually a power of 2, such as 1024 / 2048, etc. The coefficients of the polynomial are randomly selected from a finite field q, such as mod 10000, then randomly selected from 0-9999. There are many Algorithms that follow the random selection of coefficients, such as uniform distribution, discrete Gaussian distribution, and so on. Different schemes also have different requirements for coefficient selection, usually to meet the principle of fast solution under that scheme.

The second question, what is noise? Noise is used to confuse attackers, because assuming all our numbers are taken s(x), and random polynomials are in a field, then there is a certain rule, as long as enough Plaintext m is inputted for multiple times, according to the output c(x), it is possible to determine the information of both s(x) and c(x). If noise e(x) is introduced, it can ensure that s(x) and c(x) cannot be obtained by simple repetition, because there is a completely random small error. This parameter is also known as the Noise Budget. Assuming q = 2 ^ 32, the initial noise may be around 2 ^ 3. After some operations, the noise may rise to 2 ^ 20. At this time, there is still enough space for decryption, because 2 ^ 20 << 2 ^ 32.

After obtaining the polynomials, we now want to convert the operation c(x) * d(x) into a ‘circuit,’ which often appears in ZKP, mainly because the abstract concept of a circuit provides a universal computational model for any calculation, and the circuit model allows precise tracking and management of the noise introduced by each operation. It is also convenient to introduce it into professional hardware such as ASIC, FPGA for accelerated computation, such as the SIMD model. Any complex operation can be mapped to simple modular circuit elements, such as addition and multiplication.

Arithmetic circuit representation

Addition and multiplication can express subtraction and division, so they can express any calculation. The coefficients of the polynomial are represented in binary, called the input of the circuit. Each Node of the circuit represents the execution of addition or multiplication. Each (*) represents a multiplication gate, and each (+) represents an addition gate. This is the Algorithm circuit.

This leads to a question: in order to prevent leakage of semantic information, we introduce e(x), which is called noise. In our computation, addition turns two e(x) polynomials into polynomials of the same degree. In multiplication, multiplying two noise polynomials increases the degree and text size of e(x) exponentially. If the noise is too large, it will cause the noise to be unable to be ignored during the calculation of the result, resulting in the inability to recover the original text m. This is a major limitation of the HE Algorithm in expressing arbitrary computation, because the noise rises exponentially, quickly reaching an unusable threshold. In circuits, this is called the Depth of the circuit, which is the number of multiplication operations in the circuit.

The basic principle of Homomorphic Encryption HE is as shown in the above figure, in order to solve the noise problem constraining Homomorphic Encryption, so multiple solutions have been proposed:

LHE is a very suitable Algorithm, because under this Algorithm, as long as the Depth is determined, any function can be executed within the Depth. However, PHE and SHE cannot achieve Turing Complete. Therefore, based on this, cryptographers conducted research and proposed three techniques to construct FHE fully Homomorphic Encryption, hoping to achieve the vision of executing any function in infinite Depth.

• Key switching（密钥切换）: After multiplication, the size of the Ciphertext will rise exponentially, which will greatly demand memory and computing resources for subsequent operations. Therefore, implementing Key switching after each multiplication can compress the Ciphertext, but it will introduce some noise.
• Modulus Switching: Whether it is multiplication or key switching, the noise will increase exponentially. The modulus q is the Mod 10000 we mentioned earlier, and the parameter can only be chosen from [0, 9999]. If the noise remains within q after multiple computations, it can be decrypted. Therefore, after multiple operations, in order to avoid the noise increasing exponentially beyond the threshold, Modulus Switching is needed to reduce the noise budget and suppress the noise. Here we can derive a basic principle: if our calculations are complex and the circuit depth is large, a larger modulus q noise budget is needed to accommodate the usability after multiple exponential rises.
• Bootstrap: However, in order to achieve infinite Depth calculation, Modulus can only limit the rise of noise, but each switch will make the q range smaller. We know that once it is reduced, it means that the complexity of the calculation needs to drop. Bootstrap is a refresh technology, which resets the noise to the original level, rather than reducing the noise. Bootstrap does not need to reduce the modulus, so it can maintain the system’s computing power. But its downside is that it requires a lot of Computing Power resources.

In general, for computations with a limited number of steps, using Modulus Switching can drop the noise, but at the same time, it will also drop the modulus, which is the noise budget, leading to compressed computing capability. Therefore, this is only applicable to computations with a limited number of steps. As for Bootstrap, it can achieve noise reset, so on top of the LHE Algorithm, it can achieve truly fully homomorphic encryption (FHE), which means unlimited computations of any function, and this is also the meaning of ‘Fully’ in FHE.

However, the obvious disadvantage is the need to consume a large amount of Computing Power resources, so in general, these two denoising techniques will be used in combination. Modulus switching is used for daily noise management, and the latency requires bootstrap time. When modulus switching cannot further effectively control the noise, the higher computational cost of bootstrap is used.

Currently, there are the following specific implementations of FHE, all using the Bootstrap core technology:

This also brings us to the type of circuit that we have not discussed, which is the Boolean circuit. The main focus of our previous discussion was arithmetic circuits. Arithmetic circuits involve operations like addition and division, and the Node represents these operations. On the other hand, Boolean circuits represent all numbers in binary form (01), and the Node represents boolean operations such as NOT, OR, and AND, similar to the circuit implementation in our computers. Arithmetic circuits are more abstract in nature.

Therefore, we can very roughly consider Boolean operations as less data-intensive and flexible processing, while arithmetic operations are solutions for data-intensive applications.

Problems FHE faces

Due to our computation needs encryption and then converts to ‘circuit’, and because simple computation only calculates 2+ 4, but after encryption, it introduces a lot of cryptographically indirect computation processes, as well as cutting-edge technologies such as Bootstrap to solve noise problems, which results in its computational overhead being N orders of magnitude larger than ordinary computation.

We use a real-world example to let readers feel the additional cryptographic process for the consumption of computing resources. Assuming that ordinary computation requires 200 clock cycles on a 3 GHz processor, then a typical AES-128 decryption takes about 67 nanoseconds (200/3 GHz). The FHE version takes 35 seconds, which is approximately 522,388,060 times the normal version (35/67 e-9). That is, using the same computing resources, the requirements for computing resources for the same ordinary Algorithm and FHE computing Algorithm are roughly 5 billion times.

DARPA dprive program, Image source: DARPA

The DARPA in the United States, for data security, therefore specifically constructed a Dprive plan in 2021, inviting multiple research teams including Microsoft, Intel, etc. Their goal is to create an FHE accelerator and a corresponding software stack to make the FHE calculation speed more consistent with the operations on unencryption data, aiming to achieve a target where the FHE calculation speed is about 1/10 of the ordinary calculation. DARPA project manager Tom Rondeau pointed out: ‘It is estimated that in the FHE world, our calculation speed is about a million times slower than in the pure text world.’

Dprive mainly focuses on the following aspects:

• Increase the word length of the processor: Modern computer systems use a 64-bit word length, which means a number can have up to 64 bits. However, in reality, q is often 1024 bits. If we want to achieve this, we need to split our q, which will consume memory resources and affect speed. Therefore, to achieve a larger q, we need to build a processor with a word length of 1024 bits or larger. The finite field q is very important, as mentioned earlier. The larger q is, the more computational steps can be performed, and the operations of bootstrap can be postponed as much as possible, reducing the overall computational resource consumption. q plays a core role in FHE, affecting almost all aspects of the scheme, including security, performance, the amount of computation that can be performed, and the required memory resources.
• Build an ASIC processor: As we mentioned earlier, we built polynomials for circuit construction due to parallelism and other reasons, which is similar to ZK. The current CPU and GPU do not have the computing power and memory resources to run the circuit, so it is necessary to build dedicated ASIC processors to enable FHE Algorithm.
• Building parallel architecture MIMD, unlike SIMD parallel architecture, SIMD can only execute a single instruction on multiple data, that is, the data is split and processed in parallel, but MIMD can split the data and use different instructions for computation. SIMD is mainly used for data parallelism, which is also the main architecture for parallel processing of transactions in most blockchain projects. MIMD can handle various types of parallel tasks. MIMD is technically more complex and requires special attention to handling synchronization and communication issues.

The DEPRIVE plan of DARPA is only one month away from expiration. The original plan was to start Dprvie in 2021 and end in three stages in September 2024, but it seems to be progressing slowly and has not yet achieved the expected goal of 1/10 efficiency compared to ordinary computing.

Although the progress of FHE technology is slow, similar to ZK technology, the landing of hardware is a prerequisite for the landing of technology. However, we still believe that in the long run, FHE technology still has its unique significance, especially in protecting the privacy of the security data listed in the first part. For DARPA, which has a large amount of sensitive data, if they want to release the generic AI capability to the military, they need to train AI in a secure form. Not only that, it also applies to key sensitive data in areas such as medical and finance. In fact, FHE is not suitable for all ordinary calculations, but is more oriented towards computing needs under sensitive data, and this security is particularly important for the post-quantum era.

For this cutting-edge technology, it is necessary to consider the time difference between the investment cycle and the commercialization. Therefore, we need to be very cautious about the landing time of FHE.

The combination of blockchain

In the block chain, FHE is also mainly used to protect the privacy of data, and the application fields include on-chain privacy, AI training data privacy, on-chain voting privacy, on-chainshielded transaction review, etc. Among them, FHE is also known as one of the potential solutions of on-chain MEV solutions. According to our MEV article, “Illuminating the Dark Forest – Demystifying MEV”, many current MEV scenarios are simply ways to rearchitect MEVs, not solutions, and in fact the UX problems posed by sandwich attacks remain unsolved. The solution we came up with at the beginning was to encrypt the transaction directly, while keeping the state public.

MEV PBS Process

But there is also a problem that if we encrypt the transactions completely, the positive externality brought by the MEV bots will also disappear. Validators Builder needs to run FHE on the basis of Virtual Machine, and validators also need to verify transactions to determine the correctness of the final state, which will significantly increase the requirements for running Node and slow down the throughput of the entire network by millions of times.

Main Projects

FHE Landscape

FHE is a relatively new technology. Currently, most projects that use FHE technology are built by Zama, such as Fhenix, Privasea, Inco Network, and Mind Network. The FHE engineering capability of Zama has been recognized by these projects. Most of these projects are built based on the libraries provided by Zama, with the main difference lying in their business models. Fhenix aims to build a privacy-first Optimism Layer 2, while Privasea aims to use the power of FHE for LLM data computation. However, this is a very heavy data operation, with special requirements for FHE technology and hardware. It’s possible that Zama’s based TFHE is not the optimal choice. Both Inco Network and Fhenix use fhEVM, but one is for building Layer 1 and the other is for Layer 2. Arcium integrates various cryptographic technologies, including FHE, MPC, and ZK. Mind Network has a unique business model, choosing the Restaking track to solve economic security and voting trust issues at the consensus layer by providing liquidity security and a subnet architecture based on FHE.

Zama

Zama is a scheme based on TFHE, which features the use of Bootstrap technology, focusing on Boolean operations and low-bit-length integer operations. Although it is a faster technical implementation in our FHE scheme, it still has a significant gap compared to ordinary computing. Additionally, it cannot achieve arbitrary calculations. When facing data-intensive tasks, these operations can cause the circuit’s Depth to be too large to handle. It is not a data-intensive scheme and is only suitable for encryption processing of certain critical steps.

TFHE currently has ready-made implementation code. Zama’s main work is to rewrite TFHE using Rust language, which is its rs-TFHE crates. At the same time, in order to lower the threshold for users to use Rust, it also built a transcompilation tool called Concrate, which can convert Python into equivalent rs-TFHE. Using this tool, you can transcompile Python-based large model languages into TFHE-rs based Rust language. This enables the execution of large models based on Homomorphic Encryption, but data-intensive tasks are not actually suitable for the TFHE scenario. Zama’s product fhEVM is a technology that uses fully Homomorphic Encryption (FHE) to implement confidential Smart Contracts on EVM, supporting end-to-end encryption of Smart Contracts compiled based on the Solidity language.

Overall, as a To B product, Zama has built a relatively complete blockchain+AI development stack based on TFHE. It can help web3 projects easily build the infrastructure and applications for FHE.

Octra

Octra’s unique point is the use of a novel technology to achieve FHE. It utilizes a technique called hypergraphs to achieve bootstrap. Based on Boolean circuits, Octra believes that the use of hypergraphs can achieve more efficient FHE. This is the original technology for achieving FHE by Octra, and the team possesses very strong engineering and cryptographic capabilities.

Octra has built a new Smart Contract language, which uses OCaml, AST, ReasonML (a language specifically for interacting with the Octra Blockchain network for Smart Contracts and applications), and C++ for development. Its built Hyperghraph FHE library is compatible with any project.

Its architecture is similar to projects such as Mind Network, Bittensor, and Allora. It builds a Mainnet, with other projects becoming subnets, creating a mutually isolated operating environment. Similarly to these projects, it also constructs a new emerging Consensusprotocol that is more suitable for the architecture itself. Octra builds a machine learning-based Consensusprotocol called ML-consensus, which is essentially based on a Directed Acyclic Graph (DAG).

The technical principles of this Consensus have not yet been disclosed, but we can make a rough speculation. Basically, transactions are submitted to the network and then the SVM (Support Vector Machine) Algorithm is used to determine the optimal processing Node, mainly based on the current network load of each Node. The system will use historical data (ML Algorithm learning) to determine the best path for the parent Node Consensus. As long as 1/2 of the Nodes are met, the Consensus of the continuously rising database can be achieved.

Looking forward to it

The current development status of advanced cryptography technology, image source: Verdict

FHE technology is a forward-looking technology, and its development status is still not as good as ZK technology, lacking capital investment, because the low efficiency and high cost brought by privacy protection are not enough for most commercial institutions. The development of ZK technology has become faster because of the investment of Crypto VC. FHE is still in a very early stage. Even now, there are still few projects on the market because of its high cost, high engineering difficulty, and uncertain prospects for commercial landing. In 2021, DAPRA, together with many companies such as Intel and Microsoft, launched a 42-month FHE conquering plan, although some progress has been made, it is still far from achieving the performance goals. With the attention of Crypto VC to this direction, more funds will flow into this industry. It is expected that there will be more FHE projects in the industry, and more teams with strong engineering and research capabilities, such as Zama and Octra, will stand in the center of the stage. The combination of FHE technology with the commercialization and development status of blockchain is still worth exploring. Currently, the best application is the anonymization of verification Node voting, but the application scope is still narrow.

Like ZK, the landing of FHE chips is one of the prerequisites for the commercialization of FHE. Currently, multiple vendors such as Intel, Chain Reaction, Optalysys, etc. are exploring this aspect. Even though FHE faces many technical resistances, with the landing of FHE chips, fully Homomorphic Encryption, as a highly promising and necessary technology, will bring profound changes to industries such as national defense, finance, and healthcare. It will also unleash the potential of combining these privacy data with future Quantum Algorithms and usher in its moment of outbreak.

We are willing to explore this early frontier technology. If you are building FHE products that can truly be commercialized, or have more cutting-edge technological innovations, please contact us!