International Association
for Cryptologic Research

Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, while allowing arbitrary computations. Present research shows that while there are pos- sibilities of side channel exploitations on the client side targeting the encryption or key-generation processes, the encrypted data on the cloud is secure against practical attacks. 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 underlying core methodology of the attack is to exploit the dependence of the error in the ciphertexts to the timing of homomorphic computations. These correlations can lead to timing templates which when used in conjunction with the error- induced decryption errors as reported by the client can lead to an accurate estimation of the ciphertext errors. 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, where we need 7, 23 and 28 queries to the client for each error recovery respectively. We mounted full key recovery attack on TFHE (without and with bootstrapping) and FHEW with key sizes 630 and 500 bits with 1260, 703 and 1003 correct errors and 31948, 21273 and 9073 client queries respectively.