Re: [Cfrg] Point format for Edwards curves

[Andrey Jivsov <[e-mail]>]

On 05/19/2015 04:24 PM, Nico Williams wrote:
> 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.

S is an integer in ECDSA.

The number of trails until the first success of generating a "compliant" 
R is 2 with a "black box" or with additions, but this is the worst case. 
Algorithms like ECDSA would only need a simple and deterministic r := 
order-r, on average for every other R=rG. This saves the check later 
regarding whether the second coordinate is to be encoded with 0 or 1 
(but order-r or order<r are tiny steps).

> 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).

I don't think there is a concern about leakage of 0.5 bit because we 
base the decision on public information, e.g. the sign of y. r and 
order-r have the same amount of entropy, or, equivalently, (x,y) is as 
strong as (x,-y).

If I only generate a key in a deterministic way (a very uncommon 
operation), the implicit encoding of y cannot work. The only case where 
this may be needed, as noted by Watson, is for batchable ECDSA# with 
deterministic r in R=rG of {R, s}. Long-term ECDSA# public keys, just as 
ECDSA keys, are not affected. (The same applies to EdDSA). The other 
example I knew about but thought it was not worth mentioning even though 
there is a software product that does this, is generation of public key 
pairs from unsalted passwords.

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