# cipher text only attacks on deterministic homomorphic encryption schemes

If we consider a set of numbers say a set $s=\{a,b,c,d\}$ , where $a,b,c,d>1$ and the numbers $a, b, c, d$ do not share any relation between them , i.e. for any two numbers, $n_1,n_2\in s$ the following relations are guaranteed to hold: $n_1+n_2\neq 0$ and $n_1*n_2\neq 1$.

Is it possible to break the fully homomorphic encryption scheme on these set of numbers?

Note
This is a followup to this question which does not restrict the set $s$ is at all.

• Does the attacker know the public key? – mikeazo Jun 24 '15 at 2:33
• I updated the question's formatting, etc. If I inadvertently changed the meaning of the question, please let me know. – mikeazo Jun 24 '15 at 2:38
• public key is not a secret value. It is public to everyone. – prakruti.c Jun 24 '15 at 2:46
• If they have the public key, why not just use it to encrypt 1? – mikeazo Jun 24 '15 at 3:12

This is an interesting question. If the input set does not have any identity element (for both mul and add operations) then one cannot construct a field and subsequently there cannot be homomorphic operations. More clearly, if the input plaintext elements do not form a field (and their respective ciphertext elements do not form a field either) then there cannot be homomorphisms of operations. This is by definition of Field.

So if the input set contains identity elements (and other properties needed to become a field) then while the given set members may not have any obvious relation. There would be some constant $c$ for which $enc(n_1) + c * enc(n_2) = enc(0)$ subsequently finding which attacks mentioned in previous question apply !

Also an attacker could try to find random complex relations among them. For example is $enc(a) + enc(a) = enc(b)$ or is $enc(a) *enc( b) = enc(c)$ etc. revealing inferences.

• yes the observation is correct. In all cases,for some constant c, it will satisfy the relation n1 + c * n2 = 0. so it is possible to break the scheme. – prakruti.c Jun 24 '15 at 3:34
• @sashank Do you have any reference or explanation about the impossibility of construct a homomorphic encryption scheme of a set that is not a field? I think it might be true, but, I don't know, it doesn't look a trivial assumption. – Hilder Vitor Lima Pereira Jun 24 '15 at 22:38
• @VitorLima I dont have any reference but i added more explanation in the answer hope this helps. – sashank Jun 25 '15 at 4:56

If your fully homomorphic scheme is asymmetric and deterministic, then, it is already broken.

One could just encrypt the value one, $c_1 = E(pk, 1)$, then, adds $c_1$ to itself until

$c_1 + c_1 + ... + c_1 == E(pk, a)$

or

$c_1 + c_1 + ... + c_1 == E(pk, b)$

etc...

• Yes this is valid too. – sashank Jun 25 '15 at 4:58