2
$\begingroup$

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.

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

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – prakruti.c Jun 24 '15 at 3:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Hilder Vitor Lima Pereira Jun 24 '15 at 22:38
  • 1
    $\begingroup$ @VitorLima I dont have any reference but i added more explanation in the answer hope this helps. $\endgroup$ – sashank Jun 25 '15 at 4:56
1
$\begingroup$

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...

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Yes this is valid too. $\endgroup$ – sashank Jun 25 '15 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.