2
$\begingroup$

I'm a bit confused by the standards and some replies regarding zero (the point at infinity) in elliptic curves ElGamal.

TL;DR: Why do some people recommend excluding zero? It has nothing to do with key leakage due to insufficient order as those attacks are preventable by group membership checks (i.e. not related to zero explicitly).


Here it is argued that $0$ is a valid secret key from $\mathbb{Z}_q$. Mainly because if we exclude it, we can use the same reasoning to eliminate $1$, $2$, $42$, and virtually any key. The argument makes sense (see Pascal Junod's explanation). Plus academic publications support it.

However, when it comes to ECC, it gets blurry. Some recommend that zero (hence point-at-infinity) is excluded:

Yet there are exceptions:

  • RFC 7748 does not mention infinity check,
  • Bernstein et.al. argue that excluding weak keys (including zero) is not a way to go: enter image description here

As I get it, the main concern is a potential secret key leakage in case the public key $Y$ does not have the expected order. However, it is easily preventable by checking group membership with $q \cdot Y = \mathcal{O}$, where $q$ is the curve order and $\mathcal{O}$ is a point at infinity.

Also, ECDH seems to have an issue when a shared secret is zero. But it's a hybrid encryption concern, not applicable to ElGamal.

Another explanation might be because the point at infinity does not have a coordinate representation for all curves, so implementation tries to avoid it.


Anyway, I don't see any valid reason to avoid zero:

  • Yes, if your secret key happens to be zero then it's bad luck (check RBG); but the exact same logic applies to $1$, $2$, and so on.
  • Key leakage is due to performing math with not-group-member points rather than zero itself.
  • As for implementation, it has to deal with point-at-infinity anyway as it's a part of what makes curve points a group.

What am I missing? Why point-at-infinity is such an issue? It made its way to the NIST standard, so I assume there must be a good reason.


P.S. I think I'll settle for the "theory meets practice and adapts" answer. Guess that all crypto articles where I saw secret key derived from the entire $Z_q$ (or $GF(p)$) were studying ElGamal more from a theoretical side. While in practice, auditors probably weren't too thrilled to see zeros. Therefore zero was excluded from the standards (pure speculation on my side).

$\endgroup$

2 Answers 2

2
$\begingroup$

Among valid reasons not to use the zero private key in EC-ElGamal is that if we did:

  1. The public key is then the point at infinity, which in many implementations of Elliptic Curve Cryptography needs a special representation since it has no $(x,y)$ coordinates. That creates a special case to implement and test in the output and input of the public key, for no useful purpose. Much of that work is saved by making the zero private key invalid.
  2. The shared secret is then always the same (the point at infinity, or the output of the KDF for that, depending on how one defines the shared secret in EC-ElGamal), rather than uniformly random on the group depending on the ephemeral key; and that's undesirable.

Once it's decided not to use the zero private key, standards want to enforce it even though a correct implementation of the key generation is less likely to meet this case by accident than because of an otherwise disastrous malfunction.


Note: I could be wrong (and then hopefully would promptly be corrected), but I think

  • Bernstein's ECC does prevent the public key to be the point at infinity, by the very mapping of bitstrings to private key in key generation (specifically "the second highest bit of the last octet is set").
  • Bernstein's argument that we need not care for the point at infinity to be reached is made for intermediary results other than the public key, e.g. in EdDSA. It makes perfect sense when there is no special case needed for the point at infinity, as in the coordinate system/kind of curve that Bernstein advocates.
$\endgroup$
6
  • $\begingroup$ Huh, RFC 8032 indeed sets bits in the secret key in a way it's never a zero. So both standards are against zero. What bothers me: is that I don't see any reason other than eliminating the point at infinity representation from implementations. Cause, honestly, it seems that if the shared secret is $1$, it would not be much better than $0$. Would it? $\endgroup$
    – pintor
    Jul 25, 2022 at 16:58
  • $\begingroup$ @pintor: argument 1 in the answer is about elimination of point at infinity in the public key, and yes if the point at infinity works without a special case that argument falls apart. But argument 2 still holds: if we use a zero public key (or more precisely one multiple of the group order), then the shared secret is constant, rather than uniformly random. $\endgroup$
    – fgrieu
    Jul 25, 2022 at 17:04
  • $\begingroup$ Yes, but it feels like the same argument (argument 2) can be given for excluding zero from an ElGamal over $\mathbb{Z}_q$. If $sk=0$, then $pk=1$, then everything is basically a constant. As for argument 1, it's impossible for an implementation to NOT deal with this point at all. Chances are: it would appear in some intermediate operations at least once. So, it should deal with zeros but chooses not to when it comes to public keys. Sorry, I'm not trying to break your arguments. It's just I've been going crazy over it. Thank you for replying! $\endgroup$
    – pintor
    Jul 25, 2022 at 17:15
  • 1
    $\begingroup$ @pintor: it's a different thing to deal with the point at infinity in an intermediate computation (which can occur in the computation of the shared secret in EcElgamal, extremely rarely), and to deal with it in the public key. Only the public key must have a standard representation allowing interchange. Thus while you are correct we ideally should be prepared to deal with the point at infinity in intermediate computation, that does not invalidate argument 1. $\endgroup$
    – fgrieu
    Jul 27, 2022 at 11:17
  • $\begingroup$ It seems to me that your "Once it's decided not to use the zero private key, standards want to enforce it.." is my answer. It bothered me that F_q ElGamal accepted zero (paper, this forum) while EC one didn't. I made no sense: the reasoning should have been identical. Yet, I forgot that F_q ElGamal doesn't have a standard. I think if it did, it would have excused 0 as well. $\endgroup$
    – pintor
    Jul 29, 2022 at 13:15
3
$\begingroup$

There is a fundamental difference between $pk=1$ and $pk\not=1$, because $pk=1$ in a prime-order group $G_q$ is the only element not generating the group. The implication for ElGamal is disastrous, because if the same message is encrypted multiple times, then the right-hand side of the ciphertext will always be exactly the same, namely the message itself. In other words, the randomisation is completely turned off in such a case (note that this is not the case for $pk=g$ or $pk=g^{37}$). This means that an adversary who may not even know the public key only needs to passively watch out for ElGamal ciphertexts with identical right-hand sides to learn their actual message. In the IND experiment, with $pk=1$, the adversary can easily win the game with 100% certainty by just observing the right-hand side of the randomly selected encrypted message and comparing it with the two chosen messages. Therefore, I believe $(sk,pk)=(0,1)$ should be excluded, but excluding non-zero randomisation $r\not= 0$ is certainly not necessary.

$\endgroup$
1
  • $\begingroup$ Thank you! A point about 1 being a non-generator is a good one. $\endgroup$
    – pintor
    Jan 18, 2023 at 11:55

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.