“Ask and Thou Shall Receive”: Reaction-Based Full Key Recovery Attacks on FHE

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 arenas for integrity issues where a cloud server can intentionally perturb clients’ data. Contemporary FHE schemes assume an honest-but-curious server who, although curious to glean sensitive information, performs all operations judiciously. However, this assumption does not capture a practical scenario where a server can be malicious, which can perform crafted perturbations in the cloud-stored data and computational results to entice the client into providing feedback. In this work, we demonstrate reaction-based full-key recovery attack on four state-of-the-art (R)LWE-based exact FHE schemes: TFHE, FHEW, B/FV, and BGV. We first define practical scenarios where a client pursuing FHE services from a malicious server can inadvertently act as a Ciphertext Verification Oracle (CVO) when it reacts due to decryption errors. Next, we propose a novel reaction attack where the attacker can recover the secret key in a bit-by-bit fashion by taking advantage of the key distribution of these FHE schemes. We first provide the details of our attack on LWE-based FHE schemes, namely TFHE and FHEW. We further show an extension of our attack on RLWE-based FHE schemes, namely BGV and B/FV, since the LWE-based attack does not directly translate to the RLWE setting due to the differences in their underlying operations. These attacks are deemed practical in literature as a new line of work, called verifiable FHE, has recently gained traction that focuses on protecting FHE schemes from these reaction attacks.