# 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