Re: [Cfrg] EC signature: next steps

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Simon Josefsson
> 
> 1) Maturity.  Ed25519 was published through CHES in 2011 and has been
peer-
> reviewed since then.  I would appreciate if someone could find dates of
> publications on the other proposals and find out how much of scientific
review
> they have seen.
> 

[DB] By the way, this is what I'd call aegis, so is a good point, and I'll
try to answer.

That said, I'm not a historian, so I'll likely have some dates/names wrong
below.  Please take this as a tentative preliminary answer, so with a grain
of salt.

EdDSA

Part of the EdDSA proposal (i.e. those beyond Ed25519) seems to be quite
recent:
http://eprint.iacr.org/2015/677
by DJB, you, Lange, Schwabe and Yang.  You probably know better if these
parts were published elsewhere.

Actually, EdDSA is Schnorr-based, and Schnorr goes back to 1988.  So, saying
2011 is drastically underselling the age of the main security basis of
EdDSA.  The 2011 date applies to the various details over Schnorr.

Does the CHES 2011 publication claim some kind of provable security?  Could
you briefly synopsize?

Further to EdDSA's case, Pointcheval and Stern proved the security of
Schnorr signatures in the random oracle model.  I think that this dates from
1996 or 1997, was very well peer-reviewed at the time, has since been
extended and published in J. of Cryptology, and is very often often-cited.  

Not everybody values provable security as much as I do, but I don't think
most people here completely discount it, do they?

Neven, Smart and Warinschi published in J. of Math. Crypto 2009 a security
proof for Schnorr signatures in the generic group model.  That applies to
EdDSA, too.


ECDSA_CFRG

As I recall, in some version of Pointcheval and Stern's paper, they
mentioned both (1) using elliptic curves, and (2) amending DSA by inclusion
of R in the message hash.  This is a major part of ECDSA_CFRG proposal, so
is quite old and somewhat peer-reviewed.

ECDSA in some form was proposed quite early, maybe 1998, to IEEE P1363,
mainly by Scott Vanstone.  Of course, it is based on DSA (which is from
1991???), which is derived from ElGamal signatures (1984).  These
publications did not claim security proofs, (cf. CHES 2011?).

I wrote about the security of ECDSA in
http://eprint.iacr.org/2002/026
which was eventually published in DCC 2005:
http://link.springer.com/article/10.1007/s10623-003-6154-z
I also wrote a chapter 2 on ECDSA in the book 
Advances in Elliptic Curve Cryptography, Eds. Blake, Seroussi, Smart,
Cambridge University Press, 2005.
Of course, that chapter not fully peer-reviewed in the usual sense.

I briefly discussed some security issues for ECDSA,
http://eprint.iacr.org/2008/286
including the hashing R as a _suffix_, much like in ECDSA_CFRG, although I
don't recall submitting this to any peer-reviewed forum.  The discussion in
that paper was really an aside.

Koblitz and Menezes
http://eprint.iacr.org/2015/140
discuss some variants of ECDSA that they ECDSA* and ECDSA+, which are fairly
close to ECDSA_CFRG.  They argue that these are security improvements over
ECDSA.  I think that this paper has been accepted to a journal, DCC, but
perhaps as a special edition invitation issue.

The idea to make the signatures deterministic (pseudorandom) is old and
common to all current CFRG proposals, though some of the details vary
between schemes, and some of them are indeed quite new.