# Making ECDSA public keys one bit shorter

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?

-
I've been thinking of a similar scheme, where I iterate a 256 hash function until the private key is smaller than n, and the public key has a certain extra bit. I see no issues with that approach, but I'm certainly no expert on ECC. –  CodesInChaos Mar 28 '12 at 9:54
There's a more efficient way to come up with a private key with a compressed public key with bit 0; generate the private key $d$ randomly, and if the corresponding public key $dG$ compresses with bit 1, replace $d$ with $n-d$ (where $n$ is the order of the curve); the public key $(n-d)G$ has the same x-coordinate, and the other y-coordinate (and hence it will compress with a bit of 0). Using Henrick's logic, this can be shown to be as secure as the rejection method. –  poncho Apr 12 '12 at 16:29
@poncho: The method you describe should be fine as well, but the security proof has to be slightly different, since the method is based on manipulation of the private key, and I assumed no such manipulation took place. It ought to be sufficient to assume that it is equally probable that the RNG would have returned $n-d$ as if it would have returned $d$ in the first place. –  Henrick Hellström Apr 12 '12 at 23:46
@HenrickHellström: well, the probability distribution of private keys are identical for the two methods, and hence any method of proving that the probability distribution doesn't lead to a problem should apply to both methods equally. –  poncho Apr 13 '12 at 1:41
@poncho I agree. You need the extra step of proving the private key distributions are identical, but that's not difficult to see. –  David Schwartz Apr 14 '12 at 4:05

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.

-
For a fixed generator there cannot be a significant subset of weak keypairs since you could use that to break all of them. –  CodesInChaos Oct 29 '13 at 13:57