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 preserving privacy. FHE has multiple practical applications, especially in the processing and analysis of data under privacy protection, such as finance, healthcare, cloud computing, machine learning, voting systems, Internet of Things, and blockchain privacy protection. However, commercialization still requires some time, mainly due to the extremely large computational and memory overhead brought by its algorithms, as well as 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 diagram

First, we want to be able to perform calculations on encrypted data and still obtain the same results, as visualized in the above diagram. This is our basic goal. In cryptography, polynomials are commonly used to conceal the information of the plaintext, as polynomials can be transformed into linear algebra problems and vector calculation problems, which are suitable for highly optimized modern computers for vector operations (such as parallel computing), for example, 3x2 + 2x + 1 can be represented as the vector [1, 2, 3].

Suppose we want to encrypt 2. In a simplified HE system, we might:

• Choose a key polynomial, such as s(x) = 3x2 + 2x + 1

• Generate a random polynomial, such as a(x) = 2x2 + 5x + 3

• Generate a small "error" polynomial, such as e(x) = -1x + 2

• Encrypt 2 -> c(x) = 2 + a(x)*s(x) + e(x)

Let's explain why we need to do this. Now, assuming we have obtained the ciphertext c(x), if we want to obtain the plaintext m, the formula is c(x) - e(x) - a(x)*s(x) = 2. Here, we assume that the random polynomial a(x) is public, so as long as we ensure that our key s(x) is kept secret, if we know s(x) and have a small error in c(x), we can theoretically ignore it and obtain the plaintext m.

Here we encounter the first problem: with so many polynomials, how do we choose them? What is the optimal degree for the polynomials? In fact, the degree of the polynomials is determined by the algorithm used to implement HE. It is usually a power of 2, such as 1024 / 2048, etc. The coefficients of the polynomials are randomly selected from a finite field q, such as mod 10000, then randomly selected from 0-9999. There are many algorithms for random coefficient selection, such as uniform distribution, discrete Gaussian distribution, etc. Different schemes also have different requirements for coefficient selection, usually to satisfy the principle of fast solving under that scheme.

The second problem is, what is noise? Noise is used to confuse attackers, because if all our numbers are based on s(x) and the random polynomial is in a field, then there is a certain pattern, and as long as the plaintext m is input enough times, based on the output c(x), one can determine the information of s(x) and c(x). If noise e(x) is introduced, it ensures that s(x) and c(x) cannot be obtained through simple repeated enumeration, because there is a completely random small error present. 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 grow to 2^20. At this point, there is still enough space for decryption, because 2^20 2^32.

After obtaining the polynomials, we now need to transform the operation c(x) * d(x) into a "circuit". This often appears in ZKP because the abstract concept of a circuit provides a universal computing model to represent any calculation, and the circuit model allows precise tracking and management of the noise introduced by each operation, and is also convenient for subsequent introduction into specialized hardware such as ASIC, FPGA for accelerated computing, such as the SIMD model. Any complex operation can be mapped into simple modular circuit elements, such as addition and multiplication.

Arithmetic circuit representation

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

This leads to a question: in order to not leak semantic information, we introduced e(x), which is called noise. In our computation, addition will cause two noise polynomials to become polynomials of the same degree. In multiplication, multiplying two noise polynomials will exponentially increase the degree and size of e(x), and if the noise is too large, it will cause the noise to be unable to be ignored during the result calculation, which in turn makes it impossible to recover the plaintext m. This is a major reason why the HE algorithm is limited in expressing arbitrary calculations, because noise grows exponentially, quickly reaching an unusable threshold. In the circuit, this is called the depth of the circuit, and the number of multiplication operations is also the numerical value of the circuit's depth.

The basic principle of homomorphic encryption FHE is shown in the above diagram. In order to solve the noise problem that constrains homomorphic encryption, multiple solutions have been proposed:

LHE is a very suitable algorithm, because in this algorithm, as long as the depth is determined, any function can be executed within that depth, but PHE and SHE cannot achieve Turing completeness. Therefore, based on this, cryptographers have conducted research and proposed three techniques to construct FHE fully homomorphic encryption, hoping to achieve the vision of executing arbitrary functions at infinite depth.

• Key switching: After multiplication, the size of the ciphertext grows exponentially, which places great demands on memory and computational resources for subsequent operations. Therefore, implementing key switching after each multiplication can compress the ciphertext, but it introduces some noise.

• Modulus Switching: Both multiplication and key switching cause the noise to grow exponentially. The modulus q, as mentioned earlier, is Mod 10000, and the parameter can only be taken from [0,9999]. The larger q is, the noise, after multiple calculations, will still be within q, allowing for decryption. Therefore, after multiple operations, in order to prevent the noise from exponentially increasing beyond a threshold, modulus switching is needed to reduce the noise budget, thereby lowering the noise. This gives us a basic principle: if our calculations are very complex and the circuit depth is large, then a larger modulus q noise budget is needed to accommodate the availability after multiple exponential growths.

• Bootstrap: However, to achieve infinite-depth calculations, the modulus can only limit the growth of noise. Each switch reduces the range of q, and as we know, once it is reduced, it means that the computational complexity needs to be reduced. Bootstrap is a refreshing technique that resets the noise to its original level, rather than reducing the noise. Bootstrap does not require reducing the modulus, so it can maintain the system's computational capability. However, the downside is that it requires a large amount of computational resources.

In summary, for calculations with a limited number of steps, using modulus switching can reduce noise, but at the same time, it will also reduce the modulus, which is the noise budget, leading to a compression of computational capability. Therefore, this is only suitable for calculations with a limited number of steps. Bootstrap can achieve noise reset, so based on the LHE algorithm, it can achieve true FHE, which means unlimited calculations of arbitrary functions, and this is also the meaning of "Fully" in FHE.

However, the drawback is quite obvious, as it requires a large amount of computational resources. Therefore, in general, these two noise reduction techniques are used in combination, with modulus switching used for daily noise management, delaying the need for bootstrap. When modulus switching is unable to effectively control the noise further, the higher computational cost of bootstrap is used.

The current FHE solutions have specific implementations, all using the core technology of Bootstrap:

This also leads to the circuit types that we have not discussed, in the above we mainly introduced arithmetic circuits. But there is another type of circuit—Boolean circuits. Arithmetic circuits are more abstract, such as 1+1, where the nodes are addition or division, while Boolean circuits convert all numbers to binary (0 and 1), and all nodes are boolean operations, including NOT, OR, and AND operations, similar to the circuit implementation in our computers. Arithmetic circuits are more of an abstract circuit.

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

Challenges Faced by FHE

Because our calculations need to be encrypted and then transformed into "circuits," and because simple calculations only involve computing 2+4, but after encryption, a large amount of cryptographic indirect calculations are introduced, as well as some cutting-edge technologies such as Bootstrap to solve the noise problem, resulting in the computational overhead being N orders of magnitude greater than that of normal calculations.

Let's use a real-world example to help readers understand the additional computational resources required by these cryptographic processes. Suppose a normal calculation on a 3GHz processor requires 200 clock cycles, then a typical AES-128 decryption takes about 67 nanoseconds (200/3GHz). The FHE version takes 35 seconds, which is approximately 522,388,060 times that of the normal version (35/67e-9). In other words, using the same computational resources, the computational resource requirements for the same algorithm under normal and FHE calculations are approximately 500 million times different.

DARPA's dprive program, image source: DARPA

In order to ensure data security, the U.S. DARPA specifically launched the Dprive program 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 FHE calculations more in line with the operations of unencrypted data, with the goal of achieving FHE calculation speeds of approximately 1/10 of normal calculations. 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 plaintext world."

Dprive mainly focuses on the following aspects:

• Increasing the processor word length: Modern computer systems use a 64-bit word length, meaning a number can have a maximum of 64 bits. However, in reality, q is often 1024 bits. To achieve this, we need to split our q, which will consume memory resources and speed. Therefore, to achieve a larger q, a processor with a word length of 1024 bits or more needs to be built. The finite field q is very important, as we mentioned earlier, the larger it is, the more steps can be calculated, and the operations for bootstrap can be delayed 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.

• Building an ASIC processor: As we mentioned earlier, due to ease of parallelization and other reasons, we constructed polynomials and built circuits through polynomials, which is similar to ZK. The current CPU and GPU do not have the capability (computational resources and memory resources) to run circuits, so a specialized ASIC processor needs to be built to allow for FHE algorithms.

• Building a parallel architecture MIMD: Unlike the SIMD parallel architecture, where SIMD can only execute a single instruction on multiple data, meaning the data is split and processed in parallel, MIMD can split the data and use different instructions for computation. SIMD is mainly used for data parallelism, which is the main architecture for parallel processing of most blockchain projects. MIMD can handle various types of parallel tasks. Technically, MIMD is more complex and requires special attention to handle synchronization and communication issues.

DARPA's DEPRIVE program is set to expire in just one month. Originally, Dprive was planned to start in 2021, with three phases ending in September 2024, but it seems that progress has been slow, and the goal of achieving efficiency approximately 1/10 of normal calculations has not been reached.

Although the progress of breaking through FHE technology is slow, similar to ZK technology, it faces the severe problem that the landing of hardware is the 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 sensitive data as listed in the first part. For the Department of Defense, DARPA holds a large amount of sensitive data. If it wants to unleash AI's generic capabilities in the military, it needs to train AI in a secure form. Moreover, it is also applicable to critical sensitive data in fields such as healthcare and finance. In fact, FHE is not suitable for all ordinary calculations, but is more oriented towards the computational needs of sensitive data. This level of security is particularly important for the post-quantum era.

For such cutting-edge technology, the investment cycle and the time difference for commercialization must be carefully considered. Therefore, we need to be very cautious about the landing time of FHE.

Integration with Blockchain

In blockchain, FHE is mainly used to protect the privacy of data, with applications including on-chain privacy, privacy of AI training data, on-chain privacy voting, on-chain privacy transaction review, and other directions. FHE is also referred to as one of the potential solutions for on-chain MEV schemes. According to our article on MEV, "Illuminating the Dark Forest - Unveiling the Mysterious Veil of MEV," many current MEV schemes are just ways to rebuild the MEV architecture, and have not actually solved the problem. The UX problems caused by sandwich attacks have not been resolved. Our initial solution was to directly encrypt transactions while keeping the state public.

MEV PBS Process

However, a problem arises if we completely encrypt transactions, as it will also eliminate the positive externalities brought by MEV bots. The Validator Builder needs to run FHE on a virtual machine, and the validator also needs to verify transactions to ensure the correctness of the final state, significantly increasing the requirements for running nodes and slowing down the throughput of the entire network by millions of times.

Main Projects

FHE Landscape

FHE is a relatively new technology, and most of the projects currently using FHE technology are built by Zama, such as Fhenix, Privasea, Inco Network, and Mind Network. Zama's FHE engineering capabilities have been recognized by these projects. Most of these projects are built using the library provided by Zama, with the main difference being in the business model. Fhenix aims to build a privacy-first Optimism Layer2, Privasea aims to use FHE capabilities for LLM data operations, but this is a very heavy data operation, with high requirements for FHE technology and hardware, and Zama's TFHE may not be the optimal choice. Both Inco Network and Fhenix use fhEVM, but one is building Layer1 and the other is Layer2. Arcium has built a fusion of multiple cryptographic technologies, including FHE, MPC, and ZK. Mind Network's business model is quite unique, choosing the Restaking track to solve the economic security and voting trust issues of the consensus layer by providing liquidity security and a subnet architecture based on FHE.

Zama

Zama is based on TFHE and is characterized by the use of Bootstrap technology, focusing on processing Boolean operations and low-word-length integer operations. Although it is a relatively fast technical implementation in our FHE solution, it still has a very large gap compared to normal calculations. Furthermore, it cannot achieve arbitrary calculations. When facing data-intensive tasks, these operations will cause the circuit depth to be too large to handle. It is not a data-intensive solution and is only suitable for encrypting certain critical steps.

TFHE currently has ready-made implementation code, and Zama's main work is to rewrite TFHE in Rust, which is its rs-TFHE crates. In order to lower the barrier for users to use Rust, it has also built a transcompilation tool called Concrate, which can convert Python into an equivalent rs-TFHE. Using this tool, large model languages based on Python can be transcribed into Rust language based on TFHE-rs. This allows for the execution of large models based on homomorphic encryption, but this is not suitable for data-intensive tasks. Zama's product, fhEVM, is a technology that implements confidential smart contracts using fully homomorphic encryption (FHE) on the EVM, supporting end-to-end encrypted smart contracts compiled in the Solidity language.

In summary, as a B2B product, Zama has built a relatively complete blockchain + AI development stack based on TFHE. It can help web3 projects easily build FHE infrastructure and applications.

Octra

One special aspect of Octra is that it uses a unique technology to implement FHE. It uses a technology called hypergraphs to implement Bootstrap. It is also based on Boolean circuits, but Octra believes that the technology based on hypergraphs can achieve more efficient FHE. This is Octra's original technology for implementing FHE, and the team has very strong engineering and cryptographic capabilities.

Octra has built a new smart contract language, using OCaml, AST, ReasonML (a language specifically for smart contracts and applications that interact with the Octra blockchain network), and C++ for development. Its Hypergraph FHE library is compatible with any project.

Its architecture is similar to projects such as Mind Network, Bittensor, and Allora, where it has built a mainnet and other projects become subnets, creating a mutually isolated operating environment. Similarly to these projects, it has also built a new emerging consensus protocol that is more suitable for the architecture itself. Octra has built a machine learning-based consensus protocol, ML-consensus, which is essentially based on a directed acyclic graph (DAG).

The technical principles of this consensus have not been disclosed, but we can roughly speculate. Transactions are submitted to the network, and then the SVM (Support Vector Machine) algorithm is used to determine the best processing node, mainly based on the current network load of each node. The system will judge the best path for consensus based on historical data (ML algorithm learning). As long as half of the nodes agree, consensus can be reached for the continuously growing database.

Expectations

Current status of advanced cryptographic technology development, image source: Verdict

FHE technology is a forward-looking technology, and its current development status still lags behind ZK technology. The lack of capital investment, as well as the low efficiency and high cost brought about by privacy protection, has hindered the motivation for most commercial institutions. The development of ZK technology has become faster due to the investment from Crypto VCs. FHE is still in a very early stage, and even now, there are still relatively few projects on the market due to reasons such as high cost, high engineering difficulty, and unclear prospects for commercialization. In 2021, DARPA, in collaboration with several companies such as Intel and Microsoft, initiated a 42-month FHE breakthrough plan. Although some progress has been made, the performance goals are still far from being achieved. With the attention of Crypto VCs turning to this direction, more funds will flow into this industry, and it is expected that there will be more FHE projects in the industry. Teams with strong engineering and research capabilities, such as Zama and Octra, are expected to take center stage. The combination of FHE technology with the commercialization and development of blockchain is still worth exploring. Currently, one of the better applications is the anonymization of voting for validation nodes, but the application scope is still narrow.

Similar to ZK, the landing of FHE chips is one of the prerequisites for the commercialization of FHE. Currently, multiple manufacturers such as Intel, Chain Reaction, and Optalysys are exploring this aspect. Despite facing many technical obstacles, with the landing of FHE chips, fully homomorphic encryption, as a highly promising and in-demand technology, will bring profound changes to industries such as defense, finance, and healthcare. It will unleash the potential of combining privacy data with future quantum algorithms, and will also usher in its moment of breakthrough.

We are willing to explore this early cutting-edge technology. If you are building FHE products that are truly ready for commercialization, or if you have more forward-looking technological innovations, please feel free to contact us!

免责声明：本文章仅代表作者个人观点，不代表本平台的立场和观点。本文章仅供信息分享，不构成对任何人的任何投资建议。用户与作者之间的任何争议，与本平台无关。如网页中刊载的文章或图片涉及侵权，请提供相关的权利证明和身份证明发送邮件到support@aicoin.com，本平台相关工作人员将会进行核查。