Paper 2023/561

vr$^2$FHE- Securing FHE from Reaction-based Key Recovery Attacks

Abstract

Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, by allowing arbitrary computations on encrypted data. However, the malleability and flexibility provided by FHE schemes also open up arena for integrity issues where a cloud server can intentionally or accidentally perturb client’s data. Contemporary FHE schemes do not provide integrity guarantees and, thus, assume a honest-but-curious server who, although curious to glean sensitive information, performs all operations judiciously. However, in practice, a server can also be malicious as well as compromised, where it can perform crafted perturbations in the cloud-stored data and computational results to entice the client into providing feedback. While some effort has been made to protect FHE schemes against such adversaries, they do not completely stop such attacks, given the wide scope of deployment of contemporary FHE schemes in modern-day applications. In this work, we demonstrate reaction-based full-key recovery attack on two of the well-known FHE schemes, TFHE and FHEW. We first define practical scenarios where a client pursuing FHE services from a malicious server can inadvertently act as a Ciphertext Verification Oracle (CVO) by reacting to craftily perturbed computations. In particular, we propose two novel and distinct reaction attacks on both TFHE and FHEW. In the first attack, the adversary (malicious server) extracts the underlying error values to form an exact system of Learning with Errors (LWE) equations. As the security of LWE collapses with the leakage of the errors, the adversary is capable of extracting the secret key. In the second attack, we show that the attacker can directly recover the secret key in a bit-by-bit fashion by taking advantage of the key distribution of these FHE schemes. The results serve as a stark reminder that FHE schemes need to be secured at the application level apart from being secure at the primitive level so that the security of participants against realistic attacks can be ensured. As the currently available verifiable FHE schemes in literature cannot stop such attacks, we propose vr$^2$FHE (Verify - then - Repair or React) that is built on top of present implementations of TFHE and FHEW, using the concept of the Merkle tree. vr$^2$FHE first verifies the computational results at the client end and then, depending on the perturbation pattern, either repairs the message or chooses to request for recomputation. We show that such requests are benign as they do not leak exploitable information to the server, thereby thwarting both the attacks on TFHE and FHEW.