Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Nico Williams <[e-mail]>]

On Wed, May 06, 2015 at 03:39:51PM +0000, Dan Brown wrote:
> Accordingly, I now amend my proposal to 
> k = F(m,a,t) 
> where 
> F is some to-be-specified cryptographically strong deterministic function,
> m is the message, 
> a is the actual long-term (signing) key, and 
> t is a temporal value (tweak/nonce), preferably secret and unpredictable, or at least non-repeating, optionally fixed (including empty: reducing the signature scheme to an outright deterministic signature scheme), and not under any influence from an adversary.  

The signature scheme just must be deterministic as to all inputs, and it
must be state-less.  I suppose one could have OPTIONAL inputs like t
above, or cached pre-computations (a cache is not the same as state),
but those warrant extreme caution (see Watson Ladd's response).

The issue here is partly about what the API looks like.  The signature
API has to be an interface to a deterministic function with no hidden
inputs nor hidden state: so it can be tested.

It's also about state: some (most!) systems can't keep it; the scheme
simply must be state-less.  Certainly we need a state-less signature
scheme.  An explicit-state scheme might later prove useful, but first we
urgently need a state-less one.

Given a deterministic, state-less function, implementations can be
tested via test vectors.  This should be a priority.  Batch verification
is also quite desirable, but can be had anyways (EdDSA has it).

An API with explicit state (e.g., a bag of one-time-use nonces, a
counter-based nonce generator) might be a nice optimizations for some
cases, but the price to pay is extreme difficulty keeping the required
state.

Nico
--