7
$\begingroup$

In standard symmetric encryption, we can create an encryption scheme, in which two plaintexts $x_1, x_2$ map to the same ciphertext $y$, by choosing appropriate keys $k_1,k_2$ (!). The most simple example is the one-time pad: For any plaintext $x$ and any ciphertext $y$, we can choose a one-time pad key $k$ such that $E(x,k)=y$. Therefore,

(*) we can for any $x_1,x_2$ choose two one-time pad keys $k_1,k_2$ such that $E(x_1,k_1)=E(x_2,k_2)$.

(Note, I'm not claiming that finding $k_1,k_2$ is computationally tractable!)

This in itself is not interesting, but now consider fully homomorphic encryption.


In a fully homomorphic encryption scheme, we have a plaintext $x$ and key $k$, and an encrpytion function $E(x,k)=y$, but where it is now possible for an (untrusted) party for a given arbitrary computation $f$, to do computations $\tilde f$ on ciphertext $y$ without knowing the plaintext $x$, such that by decrypting $\tilde f(y)$, we get $f(x)$.

I am wondering, whether there is a similar result as (*) for fully homomorphic encryption. That is, does there exist some fully homomorphic encryption scheme that has the following property:

given two plaintexts $x_1,x_2$, there exists two keys $k_1,k_2$, such that $E(x_1,k_1)=E(x_2,k_2)=y$, and where this encryption is fully homomorphic, i.e. we can do any arbitrary computation $f$ (actually I only care about invertible computations) on $y$, and then decrypt this such that $D(f(y),k_1)=f(x_1)$ and $D(f(y),k_2)=f(x_2)$.

Note:

  • I am not claiming that this is practically useful in any way.

  • It is ok if actually finding these keys $k_1,k_2$ is computationally intractable.

  • I am interested in this for theoretical purposes only.

EDIT: random (and based-on-nothing) thought: If such an encryption scheme exists, then P=NP?

EDIT2: Here is an informal argument for why it shouldn't be possible:

  • a fully homomorphic scheme can by definition compute any computable function $f$. so it should also be able to compute a famliy of functions $f(x,n)$ where $x$ is the plaintext, and $f$ has EXPTIME complexity w.r.t. $n\in \mathbb N$.

  • Denote by $T(f(x,n))$ the amount of computational steps required to compute $f(x,n)$, and by $T(key)$ the amount of steps to find the right key $k$ for $x$ such that $Enc(x,k)=y$.

  • Then if we want to compute $T(f(x_i,n))$ "directly" for a set $X=\{x_i\}$, then it will take $T(f(x_i,n))\cdot |X|$ steps (simply the time required to compute an instance, multiplied by the amount of instances).

  • But if we want to compute it by using homomorphic encryption, then it will take $T(f(x_i,n)) + T(key)\cdot |X|$.

  • Therefore, as we increase $n$, the computation time of the first method (direct computation) increases faster by a factor of $|X|$. We, therefore, get "free computation" in the fully homomorphic case.

  • Therefore, no matter what the computational complexity is of computing the keys for the $x_i$'s, there always exists a $n$ such that computing it with the fully homomorphic method is more efficient.

This conclusion does not seem to follow the "laws of computer science", (though I haven't proved it's impossible), because it seems like a general-purpose method of improving the efficiency of such problems.

$\endgroup$
  • $\begingroup$ So you are asking: is there a homomorphic encryption scheme where for any specific set $x_1, k_1, x_2, k_2$ it is true that $E(x_1,k_1)=E(x_2,k_2)=y$, i.e. the same ciphertext can be generated using different keys. Otherwise it is just reiterating the common properties of homomorphic encryption. Or am I missing something? $\endgroup$ – Maarten Bodewes Nov 22 '18 at 13:06
  • $\begingroup$ @MaartenBodewes, not for any set $x_1,k_1,x_2,k_2$, but rather, for any set $x_1,x_2$, there exist $k_1,k_2$ such that that equation holds. (I'd also be interested if this can work for a restricted set of $x_i$) actually. $\endgroup$ – user63704 Nov 22 '18 at 13:08
  • $\begingroup$ Alright. Do you want to make a distinction between determinstic and probabalistic schemes? That seems important for the question - or at least for the answers. Are you after some form of deniability? $\endgroup$ – Maarten Bodewes Nov 22 '18 at 13:21
  • 1
    $\begingroup$ your answer really depends on the scheme. It cannot be done on LWE since it will not IND-CPA secure $\endgroup$ – kelalaka Nov 22 '18 at 17:08
  • $\begingroup$ @MaartenBodewes, I am very forgiving to the scheme in every respect other than it satisfyting the basic requirements I gave. That is, if you can give me an encryption scheme that has all kinds of terrible problems but it's still (1) fully homomorphic and (2) allows you to map two plaintexts to the same ciphertext with the right keys, then I will be happy. $\endgroup$ – user63704 Nov 22 '18 at 17:43
0
$\begingroup$

Same ciphertext from different keys

Since deterministic Homomorphic encryption schemes are insecure, all the proposed HE schemes randomize the ciphertexts in some way, i.e., during the encryption, some random value $r$ is sampled and combined with the ciphertext.

Hence, given two different keys $k_1$ and $k_2$ and two messages $m_1$ and $m_2$, we usually can find two possible random values $r_1$ and $r_2$ that make $Enc(m_1, k_1; r_1) = Enc(m_2, k_2; r_2)$, therefore, the answer for your question is yes.

For example, in schemes based on the Approximate-GCD problem, such as DGHV10, a message $m_i$ is encrypted as $pq_i + r_i + m_i$, where $p \in \mathbb{Z}$ is the secret key and $q_i$ and $r_i$ are random integers.

So, given two keys $p_1$ and $p_2$ and two messages $m_1$ and $m_2$, it is sufficient to take $q_1 = p_2k$, $q_2 = p_1k$ (for any $k$) and $r_1 = r_2 + m_2 - m_1$.

Then we see that $$Enc(m_1, p_1; q_1, r_1) = p_1q_1 + r_1 + m_1 = p_1p_2k + r_2 + m_2 = p_2q_2 + r_2 + m_2$$ which corresponds to $Enc(m_2, p_2; q_2, r_2)$.

For the BGV scheme, it is a bit more complicated, but you can still choose keys such that it holds. Namely, let $s_1, s_2 \in R := \mathbb{Z}[x]/\langle f(x) \rangle$ be two secret keys and use the same $\vec e$ in the corresponding public keys. Than, we can set

$$m_1 + s_1\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle = m_2 + s_2\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle \mod q$$ where $\langle \vec a, \vec r \rangle $ denotes the inner-product and it is a polynomial in $R$.

This equality is satisfied if $s_1 = m_2\langle \vec a, \vec r \rangle^{-1} + s_2 \mod q$.

Computational "paradox"

First of all, you are not modeling the running times correctly, because finding four keys that produce the same ciphertext is more than two times slower than finding two keys, that is, you cannot simply use $T(key)\cdot|X|$, you should use $T(key, n)$ and $T$ is most probably not linear in $n$, since you have to solve systems with more than $n$ variables to find the keys.

Furthermore, that apparent contradiction with the "laws" of computation is not implied by the ability of finding such keys. Actually, what you need is not only to create equal ciphertexts but also two find a way that their evaluation yield the same ciphertext. It might be the case that $c_1 := Enc(x_1, k_1) = c_2 := Enc(x_2, k_2)$, but $Eval_1(f, c_1) \not = Eval_2(f, c_2)$, and therefore, you could not evaluate $f$ homomorphically a single time and decrypt it with two different keys.

$\endgroup$

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.