FAHE: Achieving Thousand-Fold Speedups in Quantum-Resistant Homomorphic Encryption

TL;DR

The quest for processing encrypted data in the cloud often hits a performance wall. This paper introduces FAHE1 and FAHE2 (Fast Additive Homomorphic Encryption), symmetric-key schemes built on the Approximate Common Divisor (ACD) problem. They offer a rare trifecta: quantum resistance, thousand-fold speedups over the standard Paillier cryptosystem, and competitive efficiency against state-of-the-art symmetric alternatives like XPIR.

Perspective: The Efficiency vs. Utility Trade-off

In the world of Privacy-Preserving Computation, we usually choose between the flexibility of Fully Homomorphic Encryption (FHE) (which is slow) and the efficiency of Partially Homomorphic Encryption (PHE). Paillier has been the "Gold Standard" for PHE since 1999, but its reliance on number-theoretic problems (factoring/residuosity) makes it slow and vulnerable to future quantum threats. FAHE shifts the paradigm by focusing on the symmetric-key use case—perfect for cloud databases where the data owner is the only one who needs to decrypt.

The Problem & Motivation

Why is Paillier slow? It involves heavy modular exponentiations. Why is FHE slow? It involves complex "bootstrapping" or high-degree polynomial math. The authors identified that for encrypted databases (like MIT’s CryptDB), we don't actually need asymmetric properties. By using the ACD problem—where a ciphertext is essentially $c=p\cdot q+r$—we can replace slow exponentiations with simple additions and multiplications.

Methodology: The Core Mechanism

FAHE's innovation lies in how the message $m$ is packed into the noise $r$.

FAHE1: The Direct Approach

In FAHE1, the message is shifted and combined with a random noise $r$ and a "carry buffer" $\alpha$. This buffer is crucial—it prevents homomorphic additions from overflowing into the message bits or the prime boundary.

FAHE2: Optimized Density

FAHE2 improves upon this by imbuing the message inside the noise. By splitting the noise into two parts (noise1 and noise2) and placing the message between them with carry buffers, the authors reduced the total bit-length required for the modulus, leading to even smaller ciphertexts and faster math.

Performance: Beyond Incremental Gains

The benchmarks conducted on an Intel i7-7700K are startling.

• Versus Paillier: FAHE2 is 1,192x faster in encryption and 1,321x faster in decryption. Even homomorphic additions (the core "homomorphic" part) are 88x faster.
• Versus XPIR: XPIR is a highly optimized RLWE-based symmetric scheme. FAHE2 maintains faster encryption and addition while producing ciphertexts that are 7 to 8 times smaller than XPIR’s polynomials.

Note: The "Gain" column highlights the massive efficiency leap over Paillier.

Critical Analysis & Conclusion

Takeaway: FAHE provides an immediate performance boost for cloud database owners who need to sum encrypted columns. It effectively "future-proofs" systems against quantum computers by utilizing lattice-related hardness (ACD/LWE).

Limitations:

1. Malleability: Like all homomorphic schemes, it is not IND-CCA2 secure. An attacker with a decryption oracle could recover the secret key $p$ through adaptive queries.
2. Ciphertext Size: While much better than FHE or XPIR, it still produces ciphertexts 5–50x larger than Paillier. This is the "tax" paid for speed and quantum security.
3. Limited Operations: It only supports addition. For multiplications, one would still need more complex FHE schemes.

Future Outlook: The integration of FAHE into frameworks like CryptDB demonstrates its practical readiness. As data volumes in cloud SQL instances grow, FAHE’s ability to handle billions of additions per second will be vital.