Homomorphic encryption
Homomorphic encryption is a cryptographic technique that enables computations to be performed directly on encrypted data—known as ciphertext—such that the result, when decrypted, corresponds to the outcome of the same operations applied to the original unencrypted data, or plaintext, thereby preserving privacy without requiring decryption during processing.[1] The concept was first proposed in 1978 by Ronald Rivest, Len Adleman, and Michael Dertouzos in their paper "On Data Banks and Privacy Homomorphisms," where they envisioned privacy-preserving computations on encrypted information stored in databases.[2] Early schemes were limited to partially homomorphic encryption (PHE), supporting only specific operations like addition (e.g., the Paillier cryptosystem from 1999) or multiplication (e.g., textbook RSA encryption). In 2009, Craig Gentry introduced the first fully homomorphic encryption (FHE) scheme, capable of arbitrary computations on encrypted data, based on ideal lattices and incorporating a bootstrapping mechanism to manage noise accumulation in ciphertexts.[3] Subsequent advancements have refined FHE, including somewhat homomorphic encryption (SHE) variants that support a bounded number of operations before noise limits further computation, as demonstrated in Kristin Lauter's 2011 proof-of-concept for genomic data analysis.[1] These developments have addressed initial performance challenges, with libraries like IBM's HElib enabling practical implementations, though FHE remains computationally intensive—often millions of times slower than unencrypted processing.[1] Homomorphic encryption holds significant promise for applications in secure cloud computing, privacy-preserving machine learning, and sensitive data analysis in fields like healthcare and finance, allowing third parties to process data without accessing its contents.[4]Fundamentals
Definition and Motivation
Homomorphic encryption is a cryptographic technique that enables computations on encrypted data without requiring decryption, producing an encrypted output that, upon decryption, corresponds to the result of the same computations performed on the underlying plaintext. This property preserves the privacy of the data during processing, distinguishing it from conventional encryption schemes where data must be decrypted before any operations can be applied. The concept was originally termed "privacy homomorphisms" by Rivest, Adleman, and Dertouzos in their 1978 paper, which described encryption functions that map operations on plaintext to corresponding operations on ciphertext while maintaining secrecy.[2] Formally, in a homomorphic encryption scheme, the encryption function \text{Enc} satisfies \text{Enc}(f(m_1, \dots, m_k)) = f(\text{Enc}(m_1), \dots, \text{Enc}(m_k)) for plaintext messages m_1, \dots, m_k and some allowed function f, such as addition or multiplication, thereby permitting the evaluation of circuits or functions directly on ciphertexts.[5] This allows untrusted parties, such as cloud providers, to perform complex data analysis or machine learning tasks on sensitive information without accessing the raw data, addressing key privacy challenges in modern computing environments.[6] The primary motivation for homomorphic encryption stems from the need to outsource computations securely in scenarios like cloud computing, where users send encrypted data to third parties for processing but wish to prevent exposure of plaintexts to potential adversaries or even the service providers themselves. Unlike traditional encryption, which protects data at rest or in transit but requires decryption for computation—risking breaches during processing—homomorphic encryption maintains confidentiality throughout the entire workflow, enabling applications in healthcare, finance, and genomics where data privacy is paramount. A simple illustration of this property appears in the additive homomorphic variant of ElGamal encryption, where the addition of two ciphertexts yields a ciphertext encrypting the sum of the respective plaintexts: \text{Enc}(a) + \text{Enc}(b) = \text{Enc}(a + b).[7] The roots of homomorphic encryption trace back to the 1970s with the emergence of public-key cryptography, but practical schemes supporting arbitrary computations were not achieved until Craig Gentry's 2009 construction of fully homomorphic encryption.[5]Core Properties
Homomorphic encryption schemes are characterized by their ability to support specific algebraic operations on ciphertexts that correspond to operations on the underlying plaintexts, preserving the homomorphism between the plaintext and ciphertext spaces. These schemes can be additive, allowing homomorphic addition where the encryption of the sum of two messages equals the sum of their encryptions, denoted as \Enc(m_1 + m_2) = \Enc(m_1) + \Enc(m_2); multiplicative, supporting homomorphic multiplication such that \Enc(m_1 \cdot m_2) = \Enc(m_1) \cdot \Enc(m_2); or fully homomorphic, enabling both operations and thus arbitrary computations expressible as circuits. A core operational property in many homomorphic encryption schemes, particularly lattice-based ones, is noise growth, where each homomorphic operation—especially multiplication—increases the inherent noise in the ciphertext. This noise, introduced during encryption to ensure security, accumulates such that after sufficient operations, it may exceed a threshold, causing decryption failure unless mitigated by techniques like bootstrapping, which refreshes the ciphertext to reduce noise. Formally, a homomorphic encryption scheme is defined by algorithms \KeyGen for key generation, \Enc for encryption, \Dec for decryption, and \Eval for evaluation, satisfying correctness: for any function f supported by the scheme, \Dec(\sk, \Eval_f(\Enc(\pk, m))) = f(m) with overwhelming probability over the randomness in key generation, encryption, and evaluation. Additionally, these schemes achieve semantic security (or IND-CPA security), ensuring that no efficient adversary can distinguish encryptions of two distinct messages with non-negligible advantage, even after seeing arbitrary ciphertexts. Computations in homomorphic encryption are typically represented as boolean circuits (using gates like AND, OR, NOT for bit-level operations) or arithmetic circuits (using addition and multiplication over rings or fields), with non-fully homomorphic schemes limited to circuits of bounded depth or size to control noise growth and maintain correctness. Most practical homomorphic encryption schemes are public-key, where encryption uses a public key \pk and evaluation is performed without the secret key \sk, though symmetric variants exist that require a shared secret for both encryption and evaluation, offering efficiency trade-offs in certain settings. A desirable property is compact ciphertexts, where the size of an evaluated ciphertext remains polylogarithmic in the complexity of the computation, independent of the number of input ciphertexts or operations performed, enabling scalable evaluations.Classification of Schemes
Homomorphic encryption schemes are broadly classified according to the computational capabilities they provide over encrypted data, particularly the types and quantities of operations supported. This taxonomy distinguishes between schemes that handle limited operations and those enabling more complex computations, while also considering factors like noise management and arithmetic domains. The primary categories include partially homomorphic encryption (PHE), somewhat homomorphic encryption (SWHE), and fully homomorphic encryption (FHE), with further subdivisions into leveled and bootstrappable variants, as well as exact (integer-based) and approximate (real-number-based) schemes.[8] Partially homomorphic encryption (PHE) schemes support an unlimited number of a single operation type—either addition or multiplication—on ciphertexts, but cannot combine both indefinitely. Classic examples include the RSA cryptosystem, which enables homomorphic multiplication and relies on the hardness of the integer factorization problem, and the Paillier scheme, which supports homomorphic addition based on the composite residuosity assumption. These schemes are efficient for specific applications like secure voting or financial computations requiring only one operation, but their limitations prevent general-purpose use.[8] Somewhat homomorphic encryption (SWHE) extends PHE by allowing a limited number of both additions and multiplications, sufficient for evaluating bounded-depth circuits or polynomials of restricted degree, without the need for ciphertext refreshment. These schemes, prevalent before fully homomorphic breakthroughs, manage noise growth to support a polynomial number of operations, often based on lattice problems like the learning with errors (LWE) assumption. However, exceeding the operation limit leads to decryption failures due to excessive noise accumulation.[8] Fully homomorphic encryption (FHE) enables an unbounded number of arbitrary additions and multiplications, realizing computations on any circuit depth by incorporating bootstrapping to periodically refresh noisy ciphertexts and prevent decryption errors. Introduced by Gentry in 2009 using ideal lattices under the approximate greatest common divisor (GCD) assumption, FHE schemes typically rely on ring-LWE (RLWE) for security in modern variants. While theoretically powerful, FHE remains computationally intensive due to the overhead of bootstrapping. Within FHE, leveled homomorphic encryption provides a practical alternative by supporting a fixed number of operations (a predetermined depth) without bootstrapping, trading unbounded computation for efficiency. The BGV scheme exemplifies this, using RLWE and modulus switching to control noise for leveled operations on packed integers. Bootstrappable FHE, in contrast, achieves unbounded depth through periodic bootstrapping, as in Gentry's original construction. Schemes also differ in their arithmetic domains: exact FHE operates on integers with precise results, as in BGV and BFV, while approximate variants handle real or complex numbers with controlled precision loss, suitable for applications like machine learning. The CKKS scheme, based on RLWE, scales ciphertexts to approximate real arithmetic, introducing small errors but enabling efficient packed computations.[8] The following table summarizes key characteristics of these classifications:| Type | Supported Operations | Security Basis | Limitations |
|---|---|---|---|
| PHE | Unlimited additions or multiplications | Factoring (e.g., RSA), composite residuosity (Paillier) | Single operation type only |
| SWHE | Limited additions and multiplications (bounded depth) | LWE/RLWE | Noise limits circuit depth |
| Leveled FHE | Fixed-depth additions and multiplications | RLWE | No unbounded computation; depth preset |
| Bootstrappable FHE | Arbitrary additions and multiplications | RLWE | High computational overhead from bootstrapping |
| Approximate FHE | Real/complex arithmetic with scaling | RLWE | Precision loss in results |