[Cfrg] EC signature: next steps

[Dan Brown <[e-mail]>]

Dear CFRG chairs,

Please clarify the initialize-update-finalize (IUF) requirements.  Below, I
found some off-list text that might be useful to clarify the issue. 

> -----Somebody once said [with my edits]-----
> 
> CFRG has decided it wants IUF. So the schemes you mention below will
> not be able to put pre-hash = identity and meet CFRG requirements.
> 
> 

Here is some context to the quoted text:

> On 30/07/2015 13:26, "Dan Brown" <[e-mail]> wrote:
> 
> >put pre-hash=identity, e.g. PureEdDSA, or Ilari's proposal.
> >
> >That option does _not_ support IUF.
> >
> >The whole message must be received to compute R, and then processed
> >again, requiring two IUF passes, or buffer a huge message.
> >
> >If CFRG is allowing these non-IUF options then I'd add one to my
> >proposal.

Here is some further discussion:

At least two of the remaining proposals, EdDSA and Ilari Liusvaara's, have
modes that fail to meet _strict_ IUF requirements: the modes in which the
pre-hash is the identity.  By _strict_ I mean that IUF that has a fixed size
memory buffer; that's the whole point of IUF, isn't it? I see these
proposals as meeting the IUF poll option #3, but fail to meet IUF option #1.
I believe the proposers think that these are IUF modes, so are working under
a _lax_ IUF requirements that permits a large buffer. But, the CFRG chairs
have not yet ruled against these modes. Coincidentally, these non-strict IUF
modes also happen to be the proposal's collision-resilient modes.

In my proposal, I would also like to have an option to place as R prefix
instead of a suffix, for _better_ collision resilience (or collision
resilience instead of collision resistance, if you prefer stricter
terminology, see below for further discussion).  I still have no idea of
whether I am allowed to have such an option, despite mentioning this a few
times on the list.  My understanding was that the IUF poll choice #3 was to
have a non-IUF mode as an option in the signature.  I recall voting for #3.
But because the chairs rule for choice #1, I understood that such a non-IUF
to be forbidden, so my proposal accordingly did not include a non-IUF
option.

Brief technical comparison: 

In the strict IUF mode (i.e. pre-hash = hash), the EdDSA and Liusvaara
proposals have the form H(R,H(M)) whereas mine has H(M,R).  Mine is simpler,
and _if_ one believes all the wide-pipe hash hype, seems securer.  Of
course, _if_ one does not want to credit wide pipes anything, then they seem
about equally secure.  

In the non-strict IUF modes, if allowed, my proposal's message hashing would
converge to a perfect unison with these proposals in the form H(R,M) but of
course the proposal vary on several other features.  

If CFRG recommends a scheme with two modes are allowed, then the users must
decide a trade-off between them, trading some efficiency IUF for some
security collision-resilience.  That's where one can argue about H(M,R)+SIUF
versus H(R,M)-SIUF (S=strict), and consider all the arguments that DJB and I
had.

Note: the verifier can do strict IUF in all the current proposals, since the
verifier does not compute the PRF (though this requires the verifier
receiving the signature before the message).  But the verifier should
probably not do IUF because of its security risks: partial verification is
unwise (see the EdDSA proposal for details).  Indeed, the verifier would
prefer signed message packets (as DJB suggested), if enough computational
resources are available. By contrast, the signer might slightly prefer IUF
over signing message packets, lest the message packets be taken out of
context.