Re: [Cfrg] Point format for Edwards curves

On 05/18/2015 09:57 AM, Watson Ladd wrote:
>
>
> On May 18, 2015 8:49 AM, "Nico Williams" <nico@cryptonector.com 
> <mailto:nico@cryptonector.com>> wrote:
> >
> > On Sun, May 17, 2015 at 08:56:20PM -0700, Andrey Jivsov wrote:
> > > On 05/16/2015 03:02 PM, Watson Ladd wrote:
> > > >I hope to upload version 02 of my SPAKE2 draft soon, however, I was
> > > >hoping to have points on Ed448Goldilocks and Ed25519 in it. This 
> can't
> > > >currently happen because we've not decided on a point format for
> > > >Edwards curves. The existing point formats in the CFRG draft will not
> > > >work because I need addition. I'm aware this has taken quite a bit of
> > > >conversation spread out, but something like a little endian y
> > > >coordinate and sign bit of x doesn't seem to be wrong enough to not
> > > >put forward.
> >
> > Sure.
> >
> > > The sign bit of T can also be implicit when T=wM+xG in your draft is
> > > required to have the positive 't_x' for T={t_x, t_y} (or
> > > "compliant" T). The "encoding" of T can be done very efficiently
> > > because the sender chooses a random x.
> >
> > Even better.
> >
> > > https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.3
> > > describes the algorithm for the sum of points.
> >
> > There's a timing variation, but it's entirely to do with the sums of
> > randomly selected points, not the fixed point derived from the password,
> > which means there's no side channel.  Very nice.
>
> And this proposal will not work with batchable signature schemes. It 
> also never gets to the byte level.
>

Can you please elaborate?

I assume that:
* these schemes include a (long-term) public key and thus 
https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.2 works.
* If you are talking about r in {r,s}, this method actually helps 
because r=(kG)_x can be made equivalent to R=kG using the same method 
(making ECDSA==ECDSA*==ECDSA#).

I also think that the "black box" method 
https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.1 
should always work, even with already deployed/written software and HSMs.

Here is the rationale for my proposal againl, at the high level:

* the value of "one bit", e.g. "sign", is determined somehow (a 
particular method to define it is not important, and sometimes it's not 
even relevant as for ECDH)
* this bit is implicitly encoded at key generation time, removing the 
need to explicitly encode it downstream
* the act of export in compressed/uncompressed forms is a non-crypto 
operation (a memcpy of x||y, x, or y); import knows what to do based on 
the size of payload (crypto APIs don't need to change to handle 
compression or sign bit -- all the work can be done internally to the API)
* other benefits are privacy, lack of covert channels, unified point 
format, compatibility with any explicit encoding, possibility to encode 
public keys as short(er) integers

> >
> > Nico
> > --
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> > http://www.irtf.org/mailman/listinfo/cfrg
>