Homomorphic Encryption

The fundamental property ensuring that decryption of the evaluated ciphertext yields the exact result of applying the intended function to the original plaintexts. Formally: Dec(sk, Eval(pk, f, Enc(pk, m1), ..., Enc(pk, mn))) = f(m1, ..., mn).

• Exact correctness: Result matches bit-for-bit
• Approximate correctness: Tolerates small bounded errors (common in CKKS scheme for floating-point)
• Failure probability must be negligible for cryptographic security

Ciphertexts must reveal no information about the underlying plaintext, even to an adversary with chosen-plaintext attack capabilities. This is achieved through probabilistic encryption where each encryption incorporates fresh randomness.

• Identical plaintexts produce different ciphertexts each time
• Adversary cannot distinguish encryptions of chosen messages
• Achieved via noise-based hardness assumptions (LWE, Ring-LWE)
• Critical for multi-user scenarios where ciphertexts are shared

The size of the evaluated ciphertext and the decryption runtime must be independent of the complexity of the function f that was computed. Without compactness, the scheme is merely a multi-use garbled circuit.

• Ciphertext size bounded by a fixed polynomial in the security parameter
• Decryption time does not grow with circuit depth
• Distinguishes fully homomorphic encryption (FHE) from somewhat homomorphic schemes
• Essential for practical outsourcing of arbitrary computation

A self-referential technique where the scheme evaluates its own decryption circuit homomorphically to reset accumulated noise. Without bootstrapping, noise grows with each multiplication and eventually corrupts the ciphertext.

• Gentry's 2009 breakthrough: first viable FHE construction
• Refreshes ciphertext to enable unlimited depth computation
• Computationally expensive: often dominates runtime
• Modern schemes use programmable bootstrapping (TFHE) to simultaneously evaluate lookup tables

Schemes are categorized by the algebraic structure of functions they can evaluate homomorphically:

• Partially HE (PHE): Single operation type, unlimited times (e.g., RSA for multiplication, Paillier for addition)
• Somewhat HE (SHE): Both addition and multiplication, but limited circuit depth
• Leveled HE: Supports circuits up to a pre-determined multiplicative depth L
• Fully HE (FHE): Arbitrary computation on ciphertexts via bootstrapping

Practical deployments often use leveled schemes to avoid bootstrapping overhead.

Security rests on the computational intractability of lattice problems that remain hard even against quantum adversaries:

• Learning With Errors (LWE): Distinguishing noisy linear equations from random
• Ring-LWE: LWE instantiated over polynomial rings for efficiency
• NTRU: Shortest vector problem in convolution polynomial rings
• Approximate-GCD: Used in early integer-based schemes (DGHV)

All major post-quantum FHE schemes rely on lattice assumptions, making them candidates for long-term security.

A mathematical framework that injects calibrated statistical noise into query results or model outputs to mask individual contributions. Parameterized by epsilon (ε), DP provides a formal, quantifiable privacy guarantee. Unlike HE, which protects data during computation, DP protects against inference attacks on the output. In synthetic data factories, DP is often layered on top of HE: HE secures the computation pipeline, while DP ensures the released synthetic dataset or model cannot leak individual records.

The mathematical foundation of all practical FHE schemes. Lattice problems like Learning With Errors (LWE) and Ring-LWE are believed to be resistant to quantum attacks, making them post-quantum secure. The security of HE relies on the hardness of finding the shortest vector in a high-dimensional lattice. NIST's post-quantum cryptography standardization process has validated lattice-based approaches, ensuring that HE-encrypted data remains secure even against future quantum adversaries.

A cryptographic primitive where a secret key allows the holder to learn a specific function of encrypted data without revealing the plaintext itself. Unlike HE, where the decryptor gets the full result, FE restricts what each key holder can compute. For example, a key might only reveal whether an encrypted salary exceeds a threshold, not the exact value. FE is more efficient than HE for targeted queries but less flexible for general-purpose computation.