breaking fully homomorphic encryption schemes

Question

Fully homomorphic encryption schemes allow one to evaluate any arbitrary computation over encrypted data. Intuitively this seems to be too weak, irrespective of how we achieve this.

An adversary who has access to the cipher text only could do variety of operations. For example, duplicates in the cipher text could be found easily. No separate trapdoors are required apart from Public Key. Variety of further operations could be performed on the given corpus of cipher text, so identifying prefixes, suffixes etc. among the cipher words by simply running their respective circuits.

Also with additional information like if an adversary could guess if the column in the encrypted database is an integer. He can do operations like $<$ or $>$ among the encrypted values to further deduce interesting information.

Is this true with homomorphic schemes ? or am i missing some thing ?

Answer 1

Even though all the operations you described can be performed homomorphically, the result remains encrypted, i.e., the attacker cannot "see" it. So homomorphic computation is not useful (on its own) as an attack, because the results remain unknown to the attacker.

For example, given two ciphertexts $c, c'$, an attacker can homomorphically compute whether they encrypt the same message. The result is a ciphertext $c''$ that is an encryption of either 1 ("same message") or 0 ("different messages"). But the attacker cannot decrypt $c''$, so the 0/1 answer remains hidden to him.

Answer 2

There are several known attack techniques on homomorphic computation. Google's first paper describes an attack involving a modified secret key.

In this paper we present an attack on this fully homomorphic encryption scheme. In fact, our attack only aims at its “somewhat homomorphic encryption algorithm”. We construct a modified secret key, a modified decryption algorithm and a subset of the ciphertext space. Whenever the ciphertext is from the subset, we can correctly decrypt it by our modified secret key and modified decryption algorithm. We also discuss when our modified decryption algorithm is efficient, and when the subset is not negligible. Our attack implies that it should be careful for designing fully homomorphic encryption over the integers.

-An Attack on a Fully Homomorphic Encryption Scheme

My favorite and what came to mind first was the sociotype attack which uses the response as a means of weakness.

Essentially, our attack is based on the users’ reaction towards the output generated by the cloud.

-Reaction Attack on Outsourced Computing with Fully Homomorphic Encryption Schemes