Re: [Cfrg] Point format for Edwards curves

[Nico Williams <[e-mail]>]

On Mon, May 18, 2015 at 03:15:37PM -0700, Andrey Jivsov wrote:
> On 05/18/2015 09:57 AM, Watson Ladd wrote:
> >> > https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.3
> >> > describes the algorithm for the sum of points.
> >
> >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#).

If the signature scheme is deterministic and we're using something like
r = H(key1, M) then this doesn't work.  We could add a small delta input
to the derivation of r, but this then makes the system have a timing
leak.  The iterations needed to find a suitable delta could be quite a
few as first we need to derive a suitable R, then a suitable S.

Where timing leaks are unimportant (e.g., an off-line CA) this makes a
nice compression scheme, compressing public keys and signatures.  But as
a part of a general purpose deterministic signature scheme this won't
do.  It would work for a randomized signature scheme, but it would trade
off signature size for other things (e.g., signing gets slower).

Watson's proposal for point encoding for addition works for me.

Nico
--