Source-linked AI summary
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, Mauro Conti
TL;DR
Conventional encryption can require decryption or trust in service providers, creating privacy concerns for cloud data. This survey synthesizes HE foundations, major PHE, SWHE, and FHE families, implementations, improvements, and research directions. It concludes that bootstrapping remains a major computational cost and that unbounded or noise-free practical FHE remains unresolved.
Problem
Conventional encryption cannot operate on encrypted data without decryption, while practical FHE still requires substantial improvement for broad deployment.
Method
The survey organizes HE foundations, PHE and SWHE schemes, major FHE families, Gentry-type implementations, improvements, and research directions.
Results
The survey presents a classification and synthesis of major FHE schemes, implementations, improvements, and promising research directions.
Takeaways & Limitations
PHE and SWHE remain important foundations and alternatives because FHE schemes are costly, while practical progress continues across lattice-based families and implementations.
Takeaways & Limitations
Bootstrapping remains the main computational cost, and unbounded FHE without bootstrapping and noise-free FHE remain open problems.
Abstract
from arXiv · showhide
Legacy encryption systems depend on sharing a key (public or private) among the peers involved in exchanging an encrypted message. However, this approach poses privacy concerns. Especially with popular cloud services, the control over the privacy of the sensitive data is lost. Even when the keys are not shared, the encrypted material is shared with a third party that does not necessarily need to access the content. Moreover, untrusted servers, providers, and cloud operators can keep identifying elements of users long after users end the relationship with the services. Indeed, Homomorphic Encryption (HE), a special kind of encryption scheme, can address these concerns as it allows any third party to operate on the encrypted data without decrypting it in advance. Although this extremely useful feature of the HE scheme has been known for over 30 years, the first plausible and achievable Fully Homomorphic Encryption (FHE) scheme, which allows any computable function to perform on the encrypted data, was introduced by Craig Gentry in 2009. Even though this was a major achievement, different implementations so far demonstrated that FHE still needs to be improved significantly to be practical on every platform. First, we present the basics of HE and the details of the well-known Partially Homomorphic Encryption (PHE) and Somewhat Homomorphic Encryption (SWHE), which are important pillars of achieving FHE. Then, the main FHE families, which have become the base for the other follow-up FHE schemes are presented. Furthermore, the implementations and recent improvements in Gentry-type FHE schemes are also surveyed. Finally, further research directions are discussed. This survey is intended to give a clear knowledge and foundation to researchers and practitioners interested in knowing, applying, as well as extending the state of the art HE, PHE, SWHE, and FHE systems.
1. INTRODUCTION
Homomorphic encryption enables computation on encrypted data, addressing privacy risks that arise when conventional encryption requires decryption or trust in cloud providers. The section introduces PHE, SWHE, and FHE, motivates the survey, and outlines its organization.
- HE motivation: Homomorphic encryption preserves encrypted-data operations, allowing computation without explicitly knowing the underlying messages.For additive HE, E(m1 + m2) can be obtained from E(m1) and E(m2).
- HE motivation: Conventional encryption requires decrypting data before computation, forcing users to sacrifice privacy when using cloud services.Untrusted providers may also retain identifying user information after service relationships end.
- HE motivation: A client-server HE workflow encrypts private data, sends it to a server, submits a function, and receives an encrypted result for decryption.The server evaluates the function over ciphertexts using Eval without first decrypting the data.
- HE categories: PHE supports restricted operation types, SWHE supports addition and multiplication but has bounded depth, and FHE permits unlimited operations.PHE and SWHE limitations arise from restricted operations or ciphertext growth, motivating FHE development.
- Survey scope: The survey covers HE foundations, major PHE, SWHE, and FHE schemes, implementations, performance improvements, and future research directions.Its stated goal is to organize complex theoretical, implementation, and application perspectives for researchers and practitioners.
2. RELATED WORK
Prior surveys often emphasize theory or expert audiences, whereas this survey is positioned for a broader readership. Its scope includes researchers and practitioners interested in advances in homomorphic encryption.
- Prior surveys: Some prior surveys focus only on theoretical information about homomorphic encryption schemes.The section contrasts these theory-focused surveys with the broader scope claimed by this work.
- Prior surveys: Other surveys target expert readers and mathematicians rather than a broad research and practitioner audience.The cited comparison frames audience accessibility as a distinction among existing surveys.
- This survey: This survey adopts a broad reader perspective that includes researchers and practitioners interested in homomorphic-encryption advances.Its stated audience differs from surveys designed primarily for specialists.
3. HOMOMORPHIC ENCRYPTION SCHEMES
This section introduces HE schemes and distinguishes PHE, SWHE, and FHE by the operations and circuit classes they support. It surveys representative schemes and traces post-Gentry FHE families, implementations, and practical limitations.
- HE basics: HE evaluates functions over ciphertexts while preserving the corresponding plaintext operation, without exposing the underlying messages.The Eval operation takes ciphertexts and outputs an evaluated ciphertext that can be decrypted in the original format.
- Scheme categories: PHE supports only addition or multiplication, whereas SWHE supports both but remains limited by operation count, circuit depth, or ciphertext growth.These restrictions constrain the applications of PHE and pre-Gentry SWHE schemes.
- PHE schemes: RSA and El-Gamal are multiplicatively homomorphic, while Benaloh and Paillier provide additive homomorphic properties.RSA and El-Gamal do not support homomorphic addition; Paillier also provides additional plaintext operations.
- SWHE schemes: Boneh et al.’s construction permits one homomorphic multiplication followed by unlimited additions and gives a quadratic protocol-complexity improvement over Yao’s garbled circuit.After multiplication, the ciphertext moves to a group without a pairing, preventing another multiplication.
- FHE families: Post-Gentry FHE work is organized into ideal lattice-based, integer-based, (R)LWE-based, and NTRU-like families.The survey identifies these four families as major bases for subsequent FHE schemes.
- FHE implementations and limitations: NTRU-like FHE seeks practical efficiency, but multi-key evaluation increases noise and some parameter choices can create security or implementation problems.Noise remains decryptable under bounded conditions, while removing a nonstandard assumption can produce large evaluation keys and complicated key switching.
4. IMPLEMENTATIONS OF SWHE AND FHE SCHEMES
The survey reviews SWHE and FHE implementations, from low-depth circuits to complex real-world applications and public libraries. It finds that implementation advances have improved capability, but computational overhead, parameter complexity, and hardware costs still constrain practical deployment.
- Overview: PHE and SWHE preceded FHE as stepping stones, while bounded-level FHE is also described as SWHE.Pre-2009 PHE and SWHE remain relevant because FHE is costly.
- Low-depth circuits: Early FHE implementations targeted low-depth circuits, including isolated and composed addition and multiplication operations.The survey reports that these implementations were proof-of-concept or limited to small circuit depths.
- Real-world complex implementations: Gentry et al. implemented a leveled BGV variant to homomorphically evaluate an AES circuit, representing the first FHE implementation for a circuit complex enough for a real-life application.The construction used no bootstrapping and supported a complex application-oriented circuit.
- Public implementations: Only a few published FHE implementations are publicly available, with HElib identified as the most important and widely utilized library.HElib implements BGV with ciphertext packing and additional optimizations.
- Public implementations: HElib supports bootstrapping, multithreading, and homomorphic AES evaluation, but its low-level implementation and parameter selection make it difficult to use.Parameter selection affects both performance and security level.
- Public implementations: libScarab simplifies parameter selection relative to HElib but lacks modern noise-management and SIMD techniques.The survey specifically cites modulus reduction, re-linearization, and SIMD as unsupported techniques.
- Implementation improvements: FHEW reportedly reduces NAND-gate bootstrapping to less than a second, while SEAL emphasizes accessibility, automatic parameter selection, and noise estimation.FHEW exploits the functional completeness of NAND gates; SEAL targets both experts and non-experts.
- Hardware implementations: GPU, ASIC, and FPGA approaches target homomorphic multiplication, noise growth, modular arithmetic, FFT, and NTT to improve FHE efficiency.The survey identifies noise growth during multiplication as a major barrier to practical FHE.
5. FURTHER RESEARCH DIRECTIONS AND LESSONS LEARNED
The survey identifies security, speed, and simplicity as continuing evaluation challenges for FHE. It highlights unresolved bootstrapping, noise, semantic-security, and practical-efficiency problems while describing application-oriented research directions.
- Lessons learned: Encryption schemes are evaluated by security, speed, and simplicity, and existing FHE schemes still have substantial room for improvement, especially in speed.The survey also links usability to efficiency that does not disturb users.
- Security directions: Unbounded FHE remains subject to open security questions, including circular security and the absence of semantic-security proofs for arbitrary functions.The survey also states that no unbounded FHE scheme is IND-CCA1 secure.
- Efficiency directions: FHE efficiency limitations motivate research into SWHE schemes for real-life applications.The survey reports that homomorphic evaluation of one AES was reduced to 2 seconds.
- Efficiency directions: Bootstrapping is the main process increasing FHE computational cost because it decreases noise in evaluated ciphertexts.An unbounded practical FHE scheme without bootstrapping remains an open problem.
- Efficiency directions: Noise-free FHE and FHE without bootstrapping are identified as continuing research problems alongside frameworks proposed to address them.The survey cites proposed noise-free and bootstrapping-free approaches but presents the design problem as unresolved.
- Application directions: FHE research also connects to functional encryption, including identity-based and attribute-based encryption, by combining computation with identity- or attribute-based access control.The survey describes these as applications motivated by the existence of FHE.
6. CONCLUSION
The survey presents HE as a way to operate on encrypted data while addressing privacy concerns, and organizes foundational schemes, FHE families, implementations, improvements, and research directions.
- HE allows third parties to operate on encrypted data without decrypting it in advance.
- The survey covers foundational PHE and SWHE schemes, major FHE families, and Gentry-type implementations and improvements.
- The paper discusses promising research directions and lessons learned for researchers interested in HE, PHE, SWHE, and FHE systems.