Zero secret key in EC ElGamal: standards vs theory

Question

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:

• Key validation that excludes infinity,
• ElGamal example with secret key range [1,N-1],
• ECC self-apply explanation for non-negative numbers only,
• NIST SP 800-186-draft prohibits the use of zero secret keys.

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:

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).

Answer 1

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.

Answer 2

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.

Answer 3

Can we readjust the definition of the ECC public key derivation function to transform $N$ (the set of natural numbers) into ECC points? I believe it is evident that the zero ECC point does not exist both geometrically and analytically.