Paper 2022/1563

A Practical Full Key Recovery Attack on TFHE and FHEW by Inducing Decryption Errors

Bhuvnesh Chaturvedi, Indian Institute of Technology, Kharagpur
Anirban Chakraborty, Indian Institute of Technology, Kharagpur
Ayantika Chatterjee, Indian Institute of Technology, Kharagpur
Debdeep Mukhopadhyay, Indian Institute of Technology, Kharagpur

Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, while allowing arbitrary computations. Recent research has shown two side channel attacks on the client side running a popular HE library. However, no side channel attacks have yet been reported on the server side in existing literature. The current paper shows that it is possible for adversaries to inject perturbations in the ciphertexts stored in the cloud to result in decryption errors. Most importantly, we highlight that when the client reports of such aberrations to the cloud service provider the complete secret key can be extracted in few attempts. Technically, this implies a break of the IND-CVA (Indistinguishability against Ciphertext Verification Attacks) security of the FHE schemes. The core idea of the attack is to extract the underlying error values for each homomorphically computed ciphertext and thereby construct an exact system of equations. As the security of the underlying Learning with Errors (LWE) collapse with the leakage of the errors, the adversary is capable of ascertaining the secret keys. We demonstrate this attack on two well-known FHE libraries, namely FHEW and TFHE. The objective of the server is to perform the attack in a stealthy manner, without raising any suspicion from the innocent client. Therefore in a practical scenario, the successful key retrieval from a client would require the server to perform the attack with as few queries as possible. Thus we craftily use timing information during homomorphic gate computations to optimise our attack and significantly reduce the required number of queries per ciphertext. More precisely, we need 8 and 23 queries to the client for each error recovery for FHEW and TFHE, respectively. We mount a full-key recovery attack 1 on TFHE (without and with bootstrapping) with key size of 630 bits and successfully faulted 739 and 930 ciphertexts to recover correct errors. This required a total of 19838 and 29200 client queries respectively. In case of FHEW with key size 500, we successfully faulted 766 ciphertexts to recover correct errors, which required 7565 client queries. 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.

Available format(s)
Attacks and cryptanalysis
Publication info
FHELWEIND-CVAciphertext verification attackkey recovery
Contact author(s)
bhuvneshchaturvedi2512 @ gmail com
ch anirban00727 @ gmail com
cayantika @ gmail com
debdeep mukhopadhyay @ gmail com
2023-01-23: last of 2 revisions
2022-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bhuvnesh Chaturvedi and Anirban Chakraborty and Ayantika Chatterjee and Debdeep Mukhopadhyay},
      title = {A Practical Full Key Recovery Attack on TFHE and FHEW by Inducing Decryption Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1563},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.