[curves] Unifying public key formats

[Trevor Perrin]

On Wed, Jan 21, 2015 at 4:09 PM, Paul Lambert <paul at marvell.com> wrote:
>
>
> On 1/21/15, 6:02 PM, "Trevor Perrin" <trevp at trevp.net> wrote:
>>
>>So the Montgomery ladder function could be modified to recover the
>>Edwards x sign bit at very low cost.
>>
>>Would you prefer this for a unified format, instead of using a
>>single-coordinate format with the sign bit implied as zero (Jivsov)
>
>  Š no extra bits, no leaks, shorter, etc., sounds like a good idea.
> So how is the bit implied?

Generate a keypair and calculate the sign bit, e.g. as explained
above.  If the sign bit is one instead of zero, negate the private
scalar.  Now the sign bit is always zero.

https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact


>>or
>>encoded into signatures (your idea)?
> Also a cute trick .. But makes you modify the signature algorithm based on
> the received point format (not everyone would be Œuniversal¹)

That's easy, though:  if your public-key format doesn't include the
sign bit, just copy it from the signature, then run existing
signature-verify code.  For example, in Ed25519:

https://github.com/trevp/ref10_extract/blob/master/ed25519/additions/curve_sigs.c

Anyways, I like the Jivsov and Ransom approaches to single-coordinate
public keys for signatures, but I'm not sure they'll work for all
protocols (?)

Trevor