Making ECDSA public keys one bit shorter

Question

In compressed form, ECDSA public keys are one bit larger than the curve size. There are some situations where this extra bit is extremely inelegant. So I had the following idea as a way to remove it.

1. For a public key, the extra bit is always zero and so does not need to be sent.

2. If a private key produces an extra bit of one in the public key, it is not used. (In SECP256K1, some private keys have to be folded anyway, so this would just be folding more keys.) One suitable folding method would be to generate a new random private key. Another, probably slightly less optimum, would be to keep incrementing the private key until a valid one was found.

I'm interested in the security consequences of doing this. The following are my educated guesses, in order of my confidence in them:

1. This is definitely no worse than picking an equally secure curve that is one or two bits smaller. So it can't be less secure than, say, SECP224K1 unless SECP256K1 is broken or SECP224K1 is somehow unusually strong.

2. This is actually stronger than that because although only half the private keys are valid, an attacker probably can't really take advantage of that fact.

3. In fact, it doesn't weaken the algorithm at all. We could probably even force the first 4 bytes of the public key to be zero if we wanted and the only real cost would be that it would be a lot harder to find a valid private key. The private key search space is actually no smaller, only the chance of colliding keys is higher, which is still effectively zero. Only reducing the private key space in ways an attacker can take advantage of make the algorithm less secure.

Am I correct?

Answer 1

I think your question can be reduced to the question whether there is a significant subset of weak public/private key pairs in any of the EC groups you mention. I am not aware of any such weakness, but if it exists, it would put a large dent in the security of Elliptic Curve Cryptography as a whole.

If there is no significant risk you will get a key pair with less than the expected security, if you generate it uniformly at random in accordance with the relevant standard, but without discarding key pairs that have a public key with unwanted properties, the risk will still be insignificant even if you discard on average every other randomly selected key pair based solely on properties of the public key. It is important to reiterate that this argument only holds if you do not modify the private key generation in any way, but only discard key pairs based solely on properties of the public key.

This argument is based on pure logic. If you get the expected security from each of 1000 uniformly generated key pairs, and the adversary sees the public key of each one of them, you get the expected security from each ~500 of those that have a public key with the property you want. If the latter had been false, clearly the former couldn't be true either. Reduction ad absurdum.