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.
For a public key, the extra bit is always zero and so does not need to be sent.
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:
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.
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.
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?