Comparison-based Attacks against Noise-free Fully Homomorphic Encryption Schemes

Homomorphic Encryption provides one of the most promising means to delegate computation to the cloud while retaining data confidentiality. We present a plaintext recovery attack against fully homomorphic schemes which have a polynomial time distinguisher for a given fixed plaintext, and rely on the capability of homomorphically compare a pair of encrypted integer values. We improve by a constant factor the computational complexity of an exhaustive search strategy, which is linear in the recovered plaintext value, and show that it significantly increases the number of recoverable plaintexts. We successfully validate our attack against two noise-free fully homomorphic encryption schemes, which fulfill the mentioned requisite and were claimed to be secure against plaintext recovery attacks.