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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Does the attacker know the public key? $\endgroup$
    – mikeazo
    Jun 24, 2015 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, 2015 at 2:38
  • $\begingroup$ public key is not a secret value. It is public to everyone. $\endgroup$
    – prakruti.c
    Jun 24, 2015 at 2:46
  • 1
    $\begingroup$ If they have the public key, why not just use it to encrypt 1? $\endgroup$
    – mikeazo
    Jun 24, 2015 at 3:12

2 Answers 2

Reset to default
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$
3
  • $\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, 2015 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, 2015 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, 2015 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$
1
  • $\begingroup$ Yes this is valid too. $\endgroup$
    – sashank
    Jun 25, 2015 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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