Re: [Cfrg] updated Python script for signature proposals

["D. J. Bernstein" <[e-mail]>]

Watson Ladd writes:
> I'll switch to EdDSA encoding then.

Script updated: http://ed25519.cr.yp.to/cfrg/signatures.py

Perhaps another issue where easy consensus is possible is the size of
the secret key:

   * Three schemes ('brown', 'eddsa', 'hamburg') start from a 256-bit
     secret key. Signing uses two hash/PRF calls to derive the long-term
     scalar and one-time scalars (a,k). For 'brown' and 'eddsa' this is
     structured as sk->a,seed and then seed,m->k; for 'hamburg' it's
     structured as sk->a and separately sk,m->k.

   * Two schemes ('ladd', 'liusvaara') start from a 512-bit secret key
     (a,seed). Signing uses one hash call.

One could argue that, since secret keys are rarely communicated, there's
not much performance benefit in having a short secret key. However:

   * I'm told that, for small devices (including HSMs), secure long-term
     key storage is a serious cost, and people appreciate having this
     cost chopped in half.

   * Saving a hash call is only a small signing speedup. (For larger
     curve sizes, the savings would be two SHA-512 calls, but this is
     even less noticeable compared to the larger curve computations.)

   * More importantly, if an 'eddsa' user cares more about this hash
     call than about the space for the secret key, then the user is free
     to store the sk->a,seed output, eliminating this cost from signing.
     (Similarly, Mike mentioned the option of storing sk,a.)
     
     In other words, specifying a 512-bit secret key a,seed is really
     just skipping the specification of the sk->a,seed hash function.
     Choosing this function to fit nicely with subsequent hashing steps
     is beneficial for small signing implementations.

Furthermore, this initial hashing helps protect the user if sk has less
randomness than expected. Nobody knows any attacks against, e.g., a
randomness burp that clears the first 64 bits of sk, while clearing the
first 64 bits of the long-term scalar would bring the scalar within
range of feasible "kangaroo" attacks. For DH this argument has to be
weighed against code-size/auditing arguments, since many DH applications
don't need hashing; but for signatures there's a hash function anyway,
and this particular usage of hashing has extremely low cost.

---Dan