3
$\begingroup$

There are two non-equal (different at least in one bit) messages $M_1$ and $M_2$ both encrypted with elliptic curves on public key $K_{pu}$: $E_1=\mathsf{Enc}(K_{pu}, M_1)$ and $E_2=\mathsf{Enc}(K_{pu}, M_2)$.

An attacker possesses $E_1$ and $E_2$ but does not know whether they are encrypted with the same key.

Is it somehow possible for at attacker to establish that $E_1$ and $E_2$ are encrypted with the same key, or to make such judgement with reasonable probability?

$\endgroup$
2
$\begingroup$

I suppose that you mean "encrypted with the Elliptic Curve ElGamal scheme"; an elliptic curve is a particular type of group, you do not "encrypt a message with elliptic curves", but with an encryption scheme that works over an elliptic curve.

That being said, the ElGamal encryption scheme is randomized, so the fact that $M_1$ and $M_2$ are not equal does not matter at all: encryptions of $M_1$ and $M_2$ will look random to anyone that does not hold the secret key anyway, even if they are the same.

Finally, to answer your question, no, one cannot tell whether the same public key was used to encrypt both message, as each encryption is provably indistinguishable from a pair of uniformly random group elements, whatever the public key (unless, obviously, the attacker knows one of the corresponding secret keys).

EDIT: let's extend a bit on that, as your comment seems to ask for more details. Let $g$ be a generator of some group $\mathbb{G}$. Let $h_1,h_2$ be two public keys ($h_i = g^{s_i}$ for secret keys $s_i$, $i \in \{1,2\}$). Let $(M_1,M_2)$ be any two messages (id est arbitrary group elements, possibly identical). We consider two random encryptions of $M_1$ and $M_2$, with keys $h_1$ and $h_2$:

  • $E_1 = (g^{r_1}, h_1^{r_1}M_1)$ with a random exponent $r_1$
  • $E_2 = (g^{r_2}, h_2^{r_2}M_2)$ with a random exponent $r_2$

Consider an attacker that attempts to check whether the same public key was used for both encryptions. As it can only help him, let us assume that this attacker knows $M_1$ and $M_2$. Therefore, the adversary gets $(g^{r_1}, h_1^{r_1})$ and $(g^{r_2}, h_2^{r_2})$ for uniformly random exponents $r_1,r_2$, and tries to check whether $h_1 = h_2$. Suppose that he can do that with some non-negligible probability. Then I can use this adversary to break the decisional Diffie-Hellman assumption. Indeed, suppose I receive a tuple $(u, v, u', v') \in \mathbb{G}^4$, and I have to tell wether this is a random tuple, or a Diffie-Hellman tuple (id est a tuple of the form $(u,v,u^r,v^r)$ for some $r$).

I can simply proceed as follows: I send the pair $(u,v)$ to the adversary, as well as the pair $(u',v')$, and ask him whether "the same public key is used in both pair". Indeed, observe that $u = g^x$ for some $x$, and $v = h_1^x$ for some $h_1$, so $(u,v)$ can be seen as a pair $(g^x, h_1^x)$ for some random coin $x$ and public key $h_1$. Similarly, $(u',v') = (g^{x'}, h_2^{x'})$ for some exponent $x'$, and some public-key $h_2$. Now, if $(u,v,u',v')$ is a Diffie-Hellman tuple (hence $(u',v') = (u^r, v^r)$ for some $r$), then we necessarily have $h_1 = h_2$ above (and $x' = rx$), while if it is a random pair, then we have $h_1 \neq h_2$ with overwhelming probability.

So, if the adversary tells me that the same public key was used in both pair, it means $(u,v,u',v')$ is a DH tuple, and if not, it means it's a random tuple, so I can break the DDH assumption with the same probability that the adversary finds out whether the same key was used in both pairs.

Put otherwise, this means that assuming the DDH assumption (which is equivalent to the IND-CPA security of ElGamal), it is infeasible to tell whether the same public key was used for two encryptions.

$\endgroup$
  • $\begingroup$ Thank you for your answer. 1. Correct 2. Unlike symmetric encryption that does not look so obvious. Is there any article or other source confirming that it is definitely not possible to see whether encryption key is the same? 3. No, an attacker does not know any corresponding private key otherwise an attack would be trivial. $\endgroup$ – user928374 Apr 6 '17 at 14:31
  • $\begingroup$ @user928374 Indistinguishability (e.g. in IND-CPA) is transivie. So if $Enc_{k_1}(a)$ is indisinguishable from a random element, and $Enc_{k_2}(b)$ is indisinguishable from a random elemen, then they are indistinguishable from each other. $\endgroup$ – tylo Apr 6 '17 at 14:43
  • $\begingroup$ Yes, but let's take classic example - one-time pad. Both Enc_k(a) and Enc_k(b) will be indistinguishable from a random sequence but Enc_k(a) xor Enc_k(b) will not look random and so encrypted with the same key. $\endgroup$ – user928374 Apr 6 '17 at 14:50
  • $\begingroup$ With a one-time pad, as the name suggest, the encryption is one time: $E_K(a),E_K(b)$ does not look indistinguishable from random if the size of $K$ is just the size of $a$ (resp. $b$). $\endgroup$ – Geoffroy Couteau Apr 6 '17 at 15:36
  • $\begingroup$ I added a more detailed answer, tell me whether it is clear enough :) $\endgroup$ – Geoffroy Couteau Apr 6 '17 at 15:57

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.