5
$\begingroup$

There is an encryption scheme using elliptic curves given by @tylo explained here: @tylo's answer on ElGamal with elliptic curves and here: ElGamal with elliptic curves I. The encryption idea is to multiply (in the field) the message $m$ with the $x$-coordinate of a specific point on the elliptic curve (which is assumed to be hard to compute without breaking discrete log).

My question is why this is a secure encryption -- basically, only about half the $x$-coordinates are in use on an elliptic curve, so I guess it's a bit hard to say that the $x$-coordinates are really random. Is it assumed that the $x$-coordinate of a random elliptic curve point is pseudo-random? (There is no mentioned hashing)

Could anyone please supply a link to further reading or a brief explanation on the security of this scheme? Another question (also appearing in the mentioned questions) is if using addition in the field (instead of multiplication) is also secure.


EDIT: Following the discussion in the comments, I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve. A challenger receiving the cipher-text $c=x\cdot m_i$ can then compute $x_0=c/m_0$ and $x_1=c/m_1$. If only one of these is an $x$-coordinate of a point on the curve, then the other cannot be the chosen message. Can someone tell me what I missed in this "attack"?

$\endgroup$
  • 1
    $\begingroup$ Regarding the edit: You have not missed anything. The $x$-coordinate of a random point is less random. This is a valid attack. $\endgroup$ – K.G. Mar 26 '17 at 12:30
  • $\begingroup$ @K.G. When you say valid attack, do you mean that the scheme is insecure? Or is it insecure just if the message space is small? This scheme is described in many places, I'm puzzled about its security. $\endgroup$ – A.B. Mar 26 '17 at 12:58
  • 1
    $\begingroup$ The generally accepted security notion for this kind of scheme is semantic security. Your attack proves that this scheme is not semantically secure. $\endgroup$ – K.G. Mar 26 '17 at 16:21
  • $\begingroup$ @K.G. So why do people keep on suggesting this encryption (and getting reputation for doing it)? $\endgroup$ – A.B. Mar 28 '17 at 14:37
  • $\begingroup$ Because not everyone who votes on answers are experts in cryptography? And the experts aren't looking at every question and every answer. (Of the currently linked questions, two answers are inaccurate, while one is correct. Go ahead and try to get them fixed.) $\endgroup$ – K.G. Mar 28 '17 at 19:23
6
$\begingroup$

I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve.

What I highlighted is your problem; that is an invalid way of combining the point which is the result of the DH exchange with the plaintext.

In the standard El Gamal scheme, we use the 'modular multiplication' operation as the group operation within the key exchange, and hence we use that to combine the plaintext with the DH value.

So, when perform the operations on an Elliptic Curve, we do the same. So, what you need to do is (somehow) convert the plaintext into an elliptic curve point, and add it to the point derived from the DH exchange; if the plaintext point is in the same prime-sized subgroup is the DH generator, you're safe.

Alternatively, you can just do ECIES, and not have to worry about translating plaintexts into points...

$\endgroup$
  • $\begingroup$ Thank you for the answer. The scheme I describe is taken from an answer to a different question, as an alternative to standard El Gamal. I understand that either mapping the message to the curve or hashing the point to the field are the standard ways to encrypt, but unfortunately for my purposes both options are not adequate. Is there any other way, more similar to the proposed scheme? $\endgroup$ – A.B. Mar 24 '17 at 21:12
  • $\begingroup$ @A.B.: if the problem with the these proposals is that it doesn't meet some unspecified requirements, how about just doing ECIES; if you need a public key encryption system, it's simple and secure... $\endgroup$ – poncho Mar 25 '17 at 13:42
  • $\begingroup$ Actually, I don't even need a public key encryption, I just need some homomorphic properties for the encryption (I've done something similar using DDH over strong prime fields, but it doesn't seem to go over to elliptic curves). I think I've read somewhere that if you take only half the bits of the x-coordinate of a random elliptic curve point then it is pseudorandom - is this true? $\endgroup$ – A.B. Mar 25 '17 at 15:07
  • $\begingroup$ @A.B.: what homomorphic properties do you need; given $E(x)$ and $E(y)$, you need to be able to compute $E(F(x,y))$ for what function $F$? $\endgroup$ – poncho Mar 25 '17 at 15:58
  • $\begingroup$ It's a bit different, but basically I need to compute something like $E(x+y)$, where $+$ is in the field (preferably characteristic 2 [i.e., XOR]). More precisely, I need to compute something like $E_{a+b}(x+y)$. Therefore, I was hoping to do something like compute $(a+b)P$ and then use the $x$-coordinate to encrypt $x+y$ (by adding the $x$-coordinate to it). Of course, as you pointed out, this is an invalid way to encrypt... $\endgroup$ – A.B. Mar 25 '17 at 16:09

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.