Explain fully homomorphic encryption computing on encrypted data. It supports addition…
- User
Explain fully homomorphic encryption computing on encrypted data. It supports addition and multiplication on ciphertexts. Explain noise growth in lattice-based FHE and bootstrapping to reduce noise.
- Assistant
Explaining fully homomorphic encryption with noise and bootstrapping
Fully homomorphic encryption (FHE) enables arbitrary computation on encrypted data without decrypting it, producing ciphertexts that decrypt to the function’s output. It supports homomorphic addition and multiplication corresponding to operations on plaintexts, forming ring operations that allow evaluating polynomial circuits. Lattice-based FHE schemes (e.g., BGV, BFV) represent ciphertexts as noisy samples (like LWE/RLWE), where noise masks the plaintext but grows with each operation—adding linearly under addition and multiplicatively under multiplication. If noise grows too large, decryption fails because the noise surpasses a threshold tied to the modulus. To manage this, leveled FHE selects parameters to handle a fixed computation depth, while bootstrapping refreshes ciphertexts by homomorphically evaluating the decryption circuit on them, effectively resetting noise to a small value and enabling unlimited-depth computation. Bootstrapping involves using encrypted secret keys and often modulus switching to control noise. This process, though computationally costly, is essential for maintaining ciphertext correctness in deep computations. Underlying security stems from hard lattice problems like Ring-LWE, where operations correspond to polynomial convolutions and noise norms track error growth. What makes an encryption scheme “fully homomorphic” is the existence of an additional evaluation algorithm alongside the usual key generation, encryption and decryption:
- (\mathsf{KeyGen}(1^\lambda)) produces a public/secret key pair ((pk,sk)).
- (\mathsf{Enc}_{pk}(m)) encrypts a message (m) to a ciphertext (c).
- (\mathsf{Dec}_{sk}(c)) recovers (m) from a ciphertext.
- (\mathsf{Eval}_{pk}(C,c_1,\dots,c_n)) takes a description of a Boolean or arithmetic circuit (C) and ciphertexts (c_1,\dots,c_n) and produces a new ciphertext (c').
The correctness requirement is that for any efficiently computable function (f) (represented as a circuit built from additions and multiplications), decrypting the evaluated ciphertext gives the same result as applying (f) in the clear:
[ \mathsf{Dec}{sk}(\mathsf{Eval}{pk}(C,\mathsf{Enc}{pk}(m_1),\dots,\mathsf{Enc}{pk}(m_n))) = C(m_1,\dots,m_n). ]
Most lattice‑based constructions work over a ring (\mathbb{Z}_q[x]/(x^n+1)) and have the property that “ciphertexts add like plaintexts and multiply like plaintexts.” If (c_1=\mathsf{Enc}(m_1)) and (c_2=\mathsf{Enc}(m_2)), then (c_1+c_2) decrypts to (m_1+m_2) and (c_1\cdot c_2) decrypts to (m_1\cdot m_2), modulo the plaintext modulus. Since addition and multiplication generate all polynomial functions, this suffices to evaluate arbitrary circuits of additions and multiplications.
A crucial technical detail in these schemes is the presence of an “error” or “noise” term in every ciphertext. In a simple Learning‑With‑Errors encryption, for example, a ciphertext is an LWE sample ((\mathbf{a},b)) with (b=\langle\mathbf{a},\mathbf{s}\rangle+m+e \pmod q); the small error (e) hides the message (m). Decryption computes (b-\langle\mathbf{a},\mathbf{s}\rangle) and recovers (m) as long as (|e|) is smaller than, say, (q/2).
Performing homomorphic operations transforms these error terms:
-
Under homomorphic addition, the errors just add. If you add two ciphertexts with errors (e_1,e_2), the new error is (e_1+e_2), so its magnitude grows linearly in the number of additions.
-
Under homomorphic multiplication, not only do the messages multiply, the errors convolve as well. The new error term contains products like (m_1 e_2+m_2 e_1) and (e_1 e_2). As a result, its magnitude grows much faster—roughly multiplicatively with the circuit depth.
If the noise ever grows too large, (b-\langle\mathbf{a},\mathbf{s}\rangle) wraps around modulo (q) and decryption fails. One way to cope is to choose very large moduli and only evaluate circuits of limited depth; this gives a so‑called leveled homomorphic scheme.
Gentry’s original blueprint, and modern schemes such as BGV, BFV and CKKS, go further and support arbitrary depth by periodically “refreshing” ciphertexts. The refresh procedure, called bootstrapping, consists of homomorphically evaluating the decryption circuit itself. If you encrypt the secret key under its own public key, (\mathsf{Enc}(sk)), then given a noisy ciphertext (c) you can use (\mathsf{Eval}) to compute
[ c' := \mathsf{Eval}(\text{Dec},\mathsf{Enc}(sk),c). ]
Because (\text{Dec}) is a low–depth circuit, (\mathsf{Eval}) can still handle it before the noise blows up. The output (c') decrypts to the same plaintext as (c), but the noise in (c') is “as fresh” as an initial encryption. In many lattice schemes bootstrapping is combined with other noise‑management techniques such as modulus switching and key switching, which scale down the modulus and transform ciphertexts to keep the error term within bounds. Together, these mechanisms allow you to compute on encrypted data indefinitely while keeping decryption correct.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.