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"?

Improve this question
$\endgroup$
5
  • 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.
    Commented Mar 26, 2017 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$
    – user45323
    Commented Mar 26, 2017 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.
    Commented Mar 26, 2017 at 16:21
  • $\begingroup$ @K.G. So why do people keep on suggesting this encryption (and getting reputation for doing it)? $\endgroup$
    – user45323
    Commented Mar 28, 2017 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.
    Commented Mar 28, 2017 at 19:23

1 Answer 1

Reset to default
8
$\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...

Improve this answer
$\endgroup$
5
  • $\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$
    – user45323
    Commented Mar 24, 2017 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
    Commented Mar 25, 2017 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$
    – user45323
    Commented Mar 25, 2017 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
    Commented Mar 25, 2017 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$
    – user45323
    Commented Mar 25, 2017 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.