In lattice-based HE, each ciphertext carries a 'noise' term that grows with each operation. What happens if the noise exceeds a threshold, and how does bootstrapping solve this?
Think about your answer, then reveal below.
Model answer: If noise exceeds the threshold, decryption fails — the noisy ciphertext no longer decodes to the correct plaintext. Addition increases noise linearly; multiplication increases it quadratically (multiplying errors). After enough operations, the noise budget is exhausted. Bootstrapping solves this by homomorphically evaluating the decryption circuit: encrypt the secret key, feed the noisy ciphertext and encrypted key into a homomorphic decryption, producing a fresh ciphertext with reset noise. This requires the scheme to evaluate its own decryption circuit, which Gentry showed is achievable using 'squashing' and modular arithmetic tricks.
Bootstrapping is the conceptual breakthrough of FHE. Without it, you can only perform a limited number of operations (leveled HE). With it, you can evaluate arbitrary circuits by periodically refreshing ciphertexts. The cost is significant: bootstrapping is the most expensive operation, often taking seconds per gate. Optimizing bootstrapping speed is the central challenge in practical FHE research.
Question 2 Multiple Choice
RSA is multiplicatively homomorphic: E(m1) * E(m2) = E(m1 * m2). Why doesn't this make RSA a useful homomorphic encryption scheme?
ARSA multiplication is too slow for practical use
BRSA supports only multiplication, not addition. Without both operations, you cannot compute arbitrary functions — you're limited to multiplication chains. Fully homomorphic encryption requires both addition and multiplication (since any Boolean circuit can be built from AND and XOR/OR). Additionally, textbook RSA lacks semantic security, making even its multiplicative homomorphism a vulnerability rather than a feature
CRSA's homomorphic property only works for prime plaintexts
DThe homomorphic property disappears when RSA uses padding
Partially homomorphic schemes (RSA for multiplication, Paillier for addition, ElGamal for multiplication) each support one operation. The 30-year quest for FHE sought a scheme supporting both, because addition + multiplication computes any function (any Boolean circuit can be expressed as arithmetic operations). Gentry's 2009 construction finally achieved this using ideal lattices. The observation that RSA's multiplicative homomorphism is actually a textbook RSA vulnerability (enabling chosen-ciphertext attacks) highlights the tension between homomorphic properties and standard encryption security.
Question 3 Multiple Choice
CKKS is an HE scheme designed for approximate arithmetic on real numbers. Unlike BFV/BGV (which compute on integers exactly), CKKS treats the noise as part of the computation, allowing some precision loss. Why is this useful?
ACKKS is faster because it uses smaller parameters
BMachine learning and statistical computations inherently involve floating-point approximations. CKKS encodes real numbers and performs additions and multiplications that preserve values up to a controllable precision, matching the natural error tolerance of these applications. Exact schemes waste resources maintaining precision that the application doesn't need
CCKKS provides stronger security guarantees than exact schemes
DCKKS supports division while exact schemes do not
CKKS is tailored for machine learning inference, statistical analysis, and scientific computation — domains where results with 10-15 decimal digits of precision are perfectly acceptable. By embracing approximate arithmetic, CKKS can encode real numbers directly (rather than mapping them to integers), pack multiple values into one ciphertext via SIMD-style batching, and treat unavoidable noise as rounding error rather than a correctness failure. This makes it significantly more practical for applications like encrypted neural network inference.
Question 4 True / False
FHE allows a cloud server to compute on encrypted data without learning anything about the data or the result. The client sends encrypted inputs and receives an encrypted result.
TTrue
FFalse
Answer: True
This is the canonical FHE use case. The client encrypts their data, sends it to the cloud, and the cloud evaluates a function homomorphically — each operation on ciphertexts corresponds to the same operation on the underlying plaintexts. The cloud sees only ciphertexts throughout and returns an encrypted result that only the client can decrypt. The cloud learns nothing about the data, the intermediate values, or the final result. This enables outsourced computation with full privacy.
Question 5 Short Answer
Current FHE schemes are roughly 10,000-1,000,000x slower than computing on plaintext. What is the main source of this overhead?
Think about your answer, then reveal below.
Model answer: The primary overhead comes from operating on large mathematical objects rather than native machine integers. LWE/RLWE ciphertexts are polynomials with coefficients in large moduli, and each homomorphic operation involves polynomial multiplication, modular reduction, and noise management. Bootstrapping (refreshing noise) is particularly expensive, involving homomorphic evaluation of the decryption circuit. Ciphertexts are also much larger than plaintexts (thousands of bits per encrypted bit), creating memory bandwidth bottlenecks. Hardware acceleration (GPU, FPGA, ASIC) and algorithmic improvements are steadily reducing this gap.
The overhead is inherent to the approach: computing on encrypted data requires working in a larger algebraic structure that encodes both the data and the encryption. Each plaintext bit becomes a polynomial ring element, and each logical operation becomes polynomial arithmetic. The 10,000x figure is for optimized implementations of specific applications (like neural network inference); unoptimized or complex computations can be much worse. The trajectory is improving: 2009 FHE was millions of times slower; practical applications are now emerging for specific use cases.