Two plaintexts map to the same ciphertext in fully homomorphic encryption?

Question

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.

Answer 1

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.