5
$\begingroup$

If we have encryptions of additive and multiplicative identities in the corpus of cipher text of a deterministic fully homomorphic encryption (FHE) scheme, I guess we can break it.

If the FHE scheme is deterministic and works over integers and if the corpus of cipher text has $enc(1),enc(0)$ where $1$ being multiplicative identity and $0$ is additive identity for integers, I am thinking it is easy to break such scheme.

First we can verify if there any below inferences in the cipher text

if $eval(enc(x) + enc(y)) = enc(x)$ this means $enc(y)$ is encryption of $0$.

if $eval(enc(x) * enc(z)) = enc(z)$ this means $enc(z)$ is encryption of $1$.

if $eval(enc(x) + enc(a)) = enc(0)$ this means $a$ is additive inverse i.e $-x$.

if $eval(enc(x) * enc(b)) = enc(1)$ this means $b$ is multiplicative inverse i.e $1/x$.

if $eval(enc(x) + enc(c)) = enc(1)$ this means $x+c = 1$

Now it is easy to identify all the numbers without decrypting them.

if $eval(enc(w)+ n\times (enc(1)) = enc(0)$ this means $w= -n$.

Is this understanding correct ?

$\endgroup$
11
$\begingroup$

Yes, your understanding is correct.

It is well-known that homomorphic encryption schemes are vulnerable to cipher text attacks if they are deterministic. See, for example, the section 2.4 of the paper A Survey of Homomorphic Encryption for Nonspecialists

Consider that the attacker has a value $c_1$ that is known by him to be a encryption of some clear text $m$.

So, if this scheme accepts at most $L$ additions in sequence, the attacker can find the encryption of $L$ multipes of $m$ by adding $c$ to itself:

$c_2 = c_1 + c_1 \Rightarrow dec(c_2) = 2m$

$c_3 = c_1 + c_1 + c_1 \Rightarrow dec(c_3) = 3m$

...

$c_L = c_1 + c_1 + c_1 + ... + c_1 \Rightarrow dec(c_L) = L \cdot m$

Note that the attacker can combine the "intermediate" ciphertexts too (I mean, add the ciphertexts $c_2, c_3, c_4, .., c_{L-1}$ to themselves).

With just this, the attacker can learn a lot of pairs of cleartexts and correspondent ciphertexts. Then, since the scheme is deterministic, he will able to identify a lot of the ciphertext that are being sent.

$\endgroup$
  • $\begingroup$ That holds true for simplest operations. But what about encrypted universal circuits similar to crypto.stackexchange.com/a/1712/51546 ? They are Turing complete and thus not obviously malleable. Would it be a plausible construction from security standpoint? $\endgroup$ – ogggre Oct 11 at 20:09
  • $\begingroup$ I don't understand what you mean by "They are Turing complete and thus not obviously malleable", sorry. $\endgroup$ – Hilder Vítor Lima Pereira Oct 12 at 12:55
  • $\begingroup$ I mean that in a classical form, homomorphically encrypted operation is just a stateless expression, e.g. a so called pure function. For such a function, there exists an obvious way to extract the secret value by analyzing a series of equations or by exploiting the inherent malleability of operations. In case of Universal Circuits (UC), there is a state involved and the resulting function (program) is often not pure, e.g. it becomes not obviously malleable by just observing the equation. This isn't a simple question and it may not belong here; however any intuition regarding this is welcome. $\endgroup$ – ogggre Oct 13 at 16:58
  • 1
    $\begingroup$ I am not sure I am following you... We can evaluate any circuit homomorphically but we always do it using the two operations that the scheme provides us (for instance, and gates and xor gates, or addition and multiplication). So, those "simple" operations are always available for the attacker. Maybe you can ask a new question on this website to develop better what you are saying. I will be glad to answer it if I know the answer. $\endgroup$ – Hilder Vítor Lima Pereira Oct 13 at 17:45
  • $\begingroup$ You are following me perfectly, and thank you for confirming the intuition. You are awesome. The state between operations may be "entangled" but it always boils down to two primitives the scheme provide us. An attacker can select the starting point and just follow along the state thus breaking any "entanglement" step by step, thus recovering the encrypted values. $\endgroup$ – ogggre Oct 14 at 11:18

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.