Classification of Homomorphic Encryption

Based on the types of operations supported and the number of operations allowed, homomorphic encryption is mainly classified into three categories: Partial Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and Fully Homomorphic Encryption (FHE).

Partial Homomorphic Encryption (PHE)
Unlike Fully Homomorphic Encryption (FHE), Partial Homomorphic Encryption only supports a limited type of operations, such as addition or multiplication, but not both simultaneously. This allows PHE to protect data privacy while enabling necessary data processing functions in certain application scenarios. For example, the RSA encryption scheme supports additive operations, while the ElGamal encryption scheme supports multiplicative operations. Although these encryption schemes possess some homomorphic properties, their limited functionality makes them difficult to apply directly to scenarios requiring multiple types of operations.

Somewhat Homomorphic Encryption (SHE)
Somewhat Homomorphic Encryption (SHE) represents an advancement over Partial Homomorphic Encryption, allowing for limited addition and multiplication operations on encrypted data. However, each homomorphic operation increases noise, and after a certain number of operations, the noise in the ciphertext becomes excessive. This can lead to decryption failure or inaccurate results. Consequently, SHE schemes are typically only suitable for scenarios involving a small number of operations.

Fully Homomorphic Encryption (FHE)
Fully Homomorphic Encryption (FHE) enables unlimited addition and multiplication operations on encrypted data without causing decryption failure, regardless of the computation volume. Considered the “Holy Grail” of homomorphic encryption research, FHE shows immense potential for wide-ranging applications—from secure cloud computing to privacy-preserving data analysis.

Development History of Homomorphic Encryption

The concept of homomorphic encryption dates back to the 1970s when researchers first envisioned performing computations directly on encrypted data. However, this intriguing idea remained theoretical for decades. It wasn’t until 2009 that IBM mathematician Craig Gentry achieved a breakthrough.

Gentry introduced the first viable fully homomorphic encryption scheme, enabling arbitrary computations on encrypted data. His method, based on complex “ideal lattices,” innovatively incorporated two key elements: noise and bootstrapping. Noise—an unavoidable byproduct of encryption that accumulates with each computation—can lead to decryption failures. To combat this, Gentry devised the “bootstrapping” technique, which “cleans” noise during computation. Through self-adjustment and cyclic encryption, Gentry’s scheme proved that fully homomorphic encryption was feasible and could support unlimited computations.

This groundbreaking work ignited enthusiasm throughout the cryptography field, transforming a once-distant concept into a tangible research direction. It also laid the foundation for future advancements in data privacy protection and cloud computing security.

Early Stage
Before Gentry’s FHE proposal, research mainly focused on partial homomorphic encryption. The RSA and ElGamal encryption schemes were typical early representatives of partial homomorphic encryption. These schemes were limited to performing only a single type of operation, making them difficult to apply to more complex computational tasks.

Gentry’s Breakthrough
Gentry’s fully homomorphic encryption scheme was based on lattice theory. This scheme introduced a concept called “noise,” which gradually increases with each operation. Gentry developed the “bootstrapping” process to prevent excessive noise, which reduces noise to a manageable level by partially decrypting and re-encrypting the ciphertext. The core idea of bootstrapping is to “refresh” the ciphertext before noise accumulates to an uncontrollable level. Specifically, bootstrapping allows the encryption system to re-encrypt and simplify the current ciphertext using fully homomorphic encryption after performing a portion of the calculations, effectively reducing noise. This process acts as a noise removal mechanism, “repackaging” ciphertexts that originally contained more noise and automatically managing noise during encrypted computations. Consequently, it enables an unlimited number of calculations on the ciphertext without excessive noise accumulation, solving the limitation of previous homomorphic encryption schemes that only supported a finite number of calculations. While this design was theoretically groundbreaking, its computational cost was prohibitively high, resulting in extremely slow early implementations.

Subsequent Developments
In 2011, Brakerski and colleagues proposed a more streamlined FHE scheme based on the Learning With Errors (LWE) problem, significantly reducing computational complexity. Subsequently, improved schemes further enhanced the efficiency of fully homomorphic encryption. Notable examples include the B/FV (Fan-Vercauteren) scheme and the CKKS scheme, which is based on ring homomorphic encryption. These advancements demonstrated significant efficiency improvements in specific application scenarios.

Concept and Mainstream Schemes of Fully Homomorphic Encryption

Homomorphic Property

The key property of homomorphic encryption is a form of homomorphism between encryption and plaintext operations. Suppose we have two plaintexts (m_1) and (m_2), with their corresponding ciphertexts (Enc(m_1)) and (Enc(m_2)). The encryption function (Enc) and operation (circ) satisfy the following property:

[ Enc(m_1) \circ Enc(m_2) = Enc(m_1 \circ m_2) ]

This relationship implies that operations performed on ciphertexts, when decrypted, yield the same result as operations performed on plaintexts.

Since Gentry proposed the first fully homomorphic encryption scheme, many researchers have improved and optimized it. Here are the technical details and pros and cons of two common fully homomorphic encryption schemes:

Gentry’s Fully Homomorphic Encryption Scheme

Gentry’s scheme is the first theoretically feasible fully homomorphic encryption scheme, innovatively proposing an encryption structure based on ideal lattices. His scheme has the following characteristics:

• Ideal Lattice Encryption: Gentry’s fully homomorphic encryption scheme is based on the complex mathematical structure of ideal lattices. Ideal lattices provide a highly secure encryption foundation that is difficult to break. Based on currently known quantum and classical algorithms, the ideal lattice problem is considered difficult to solve effectively. This mathematical structure provides sufficient security for encryption while allowing flexible operations on ciphertexts.
• Noise: Each encryption operation generates noise. If left uncontrolled, noise accumulates gradually in operations, eventually leading to incorrect decryption of ciphertexts. Gentry innovatively used bootstrapping technology, allowing noise to be “cleared” after performing calculations to a certain depth. Therefore, his proposed scheme has infinite depth and can support an unlimited number of calculations.
• Bootstrapping: In the bootstrapping process, the ciphertext itself is re-encrypted, allowing the encryption scheme to preserve the correctness of encrypted data while clearing noise. The core of bootstrapping is to recursively operate on ciphertexts in an encrypted state and manage noise accumulation during the computation process. Through this recursive operation, calculations can be performed without limitation.

Brakerski-Fan-Vercauteren Scheme (B/FV Scheme)

To overcome the computational bottleneck in Gentry’s scheme, researchers such as Brakerski, Fan, and Vercauteren proposed an improved scheme based on the Learning With Errors (LWE) problem and the Ring Learning With Errors (Ring-LWE) problem. The B/FV scheme mainly optimizes the bootstrapping process.

B/FV effectively controls and manages noise growth through a technique called “modulus switching”, thereby extending the number of operations that can be performed without bootstrapping. The B/FV scheme uses ring structures for encryption and computation operations. Specifically, messages and ciphertexts are represented as polynomials, using the Ring Learning With Errors (Ring-LWE) problem to transform computational operations into operations on polynomials. This representation greatly improves the efficiency of encryption and decryption and allows for more efficient homomorphic operations.

Compared to Gentry’s scheme, B/FV is more efficient in encryption and decryption operations, especially when performing simple homomorphic addition and multiplication, its performance is greatly optimized. The advantage of the B/FV scheme lies in its reduction of computational overhead for bootstrapping, making fully homomorphic encryption more feasible in practical applications. However, when executing complex multi-step calculations, this scheme still encounters the problem of noise accumulation and ultimately still needs to use bootstrapping technology to clear noise.

Characteristics and Challenges of Fully Homomorphic Encryption

Although fully homomorphic encryption offers advantages in secure data sharing and flexible data processing, it still faces the challenge of high computational overhead. In data-sharing scenarios, fully homomorphic encryption ensures that unauthorized third parties do not access data during transmission and processing. Data owners can confidently share encrypted data with other parties, who can process it in its encrypted state and return the results to the original data owner. Compared to other algorithmic solutions, its data processing method is more flexible and suitable for various data-intensive tasks requiring encrypted processing, such as machine learning, statistical analysis, and financial calculations.

Despite the forward-looking concept of fully homomorphic encryption, its biggest challenge is the high computational cost. Existing fully homomorphic encryption schemes consume substantial computational resources when executing complex calculations (especially multiplication or multi-step operations). Performance bottleneck is a major obstacle to its widespread application, and researchers are constantly striving to improve efficiency, aiming to make fully homomorphic encryption a mainstream technology in practical applications.

Applications of Fully Homomorphic Encryption in Traditional Fields

Application Scenarios

In the cloud computing era, privacy protection is crucial. Many businesses and individuals store data in the cloud and rely on cloud servers for various computational tasks. This is especially vital in the medical field, where patient data privacy is paramount. Fully homomorphic encryption offers robust protection for medical institutions, enabling them to conduct statistical analysis and disease modeling while keeping data encrypted. This ensures sensitive information remains secure from unauthorized access. The financial industry also handles highly sensitive data, such as customer investment portfolios and credit assessments. Fully homomorphic encryption allows financial institutions to perform risk analysis and financial modeling without decrypting data, thus providing dual protection for user privacy and data security.

Applications of Fully Homomorphic Encryption in the Blockchain Domain

Application Scenarios

Fully homomorphic encryption adds a layer of privacy to smart contracts on the blockchain, allowing users to execute contracts without revealing input data. This technology is especially valuable in the DeFi sector, where users can conceal fund balances and transaction details during lending and trading, safeguarding personal privacy. Furthermore, fully homomorphic encryption has created new avenues for privacy protection in digital currencies. While privacy coins like Monero and Zcash already employ advanced encryption, fully homomorphic encryption can further obscure transaction amounts and participant identities, enhancing transaction secrecy. In decentralized data markets or analysis scenarios, data providers can securely share encrypted data through fully homomorphic encryption, enabling other participants to conduct analysis and calculations without risking data leaks, thus improving both security and efficiency in data sharing.

Classic Examples

Zama is a company dedicated to privacy technology in the blockchain domain. It focuses on developing privacy protection tools based on fully homomorphic encryption. For a detailed analysis, please refer to another research report.

Elusiv is a privacy protection platform that combines fully homomorphic encryption and blockchain technology. It is primarily used to protect transaction privacy on the blockchain. Users can conduct anonymous transactions through Elusiv’s system, ensuring transaction details are not made public while still being able to verify the correctness of transactions on-chain.