Subject: [Cfrg] EC signature: next steps

From: Alexey Melnikov <[email-masked]>
Date: Mon, 31 Aug 2015 10:53:24 +0100

Dear CFRG participants,

Many thanks to Ilari for posting this updated summary of where things
currently stand. Kenny and I would now like to run a short discussion
focusing on this summary, with our intention being to flush out any last
issues or additional points of comparison between the different schemes
that everyone should be aware of.

Once everyone has kicked the tires, so to speak, we plan to move to a
poll to decide which scheme CFRG should focus on writing up and formally
recommending. We, as chairs, are hoping these steps will get us to the
finishing line.

So:

- are there important characteristics or points of comparison that
Ilari's summary does not cover?

- are there errors of fact or omission that need to be corrected?

- anything else?

We'll let this discussion run for exactly one week, but we might extend
the time if the discussion is still going strong and new arguments or
points of comparison are brought up. After that, if no major new
information is brought up, we will start the Quaker poll for selecting a
single CFRG-recommended signature scheme.

Best Regards,
Kenny and Alexey

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 31 Aug 2015 15:06:43 +0200

> Ilari's summary does not cover?

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.

2) Implementation status.  There are many Ed25519 implementations
around, many are freely available with source code under liberal
licenses.  Understanding the status of the other proposals would be
useful too.

3) Deployment.  Ed25519 is implemented and deployed by two IETF
protocols (SSH and OpenPGP), with more on their way.  There are many
libraries around for implementation, see
<http://ianix.com/pub/ed25519-deployment.html>.

> - are there errors of fact or omission that need to be corrected?

1) I don't understand by this part of Ilari's writeup: 'dictated by
???'.

2) I disagree with 'Neither personalization nor firewalling is
supported.'.  As far as I understand what Ilari intend, both are
supported in the sense that they can be added by a higher-level
abstraction, which I believe is a more appropriate approach than jamming
this into the signature primitive.

3) What is NPOT?

/Simon

---

From: Watson Ladd <[email-masked]>
Date: Mon, 31 Aug 2015 09:41:57 -0400

> this into the signature primitive.

At this point I see no reason not to recommend EdDSA as the result.
>
> /Simon
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 31 Aug 2015 19:28:32 +0300

> 1) I don't understand by this part of Ilari's writeup: 'dictated by

I earlier tought that the prehash comes from the key, but then
read comment by DJB stating that this is not the case.
 
> this into the signature primitive.

I fully agree that putting firewalling into higher layers is better
idea than putting it into signature primitive. However, apparently
the signature primitive is to support signature-level online operation
(which I think is rather bad idea) as opposed to protocol-level online
operation.

As for personalization, the problem is that protocols A and B (or
even just different versions of the same protocol!) can interpret the
same message in rather different ways.

(Personalization does create some issues with application interface).

> 3) What is NPOT?

(Order) Near Power Of Two. The difference of order and nearest power
of two is on order of sqrt(l).

Such orders produce even distributions of x mod l, where x is n bits
long with smaller n than usual.

Both Curve25519 and Curve448 are NPOT. 

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 31 Aug 2015 18:05:11 +0100

Hi Alexey,

> Ilari's summary does not cover?

IPR. There have been a few modifications to the schemes compared to
when those were initially proposed during the process. One of the
things that IETF working groups (well, document shepherds) do these
days is to get authors of documents to re-confirm that yes, they have
in fact ensured that all required IPR declarations have been made.
That does catch some errors and omissions that would otherwise cause
issues later in the process.

While we don't yet have a draft here, I think it would be a valuable
input if each of the authors commented in the next week as to whether
or not they are personally aware of any IPR that affects their
proposal. (Of course, if they know of IPR that affects someone else's
proposal then our IPR process also does ask that they tell us about
that too.) And again, as with the document shepherd case, it'd be
fine if they just sent mails to the chairs who then summarised to the
list before you start that poll, e.g. saying who had (or had not) sent
you such a mail and what they said. (On list would be fine but might
get fractious, hence my suggestion that the chairs summarise.)

And just to be very clear, the information that I would find useful
in that aspect of the evaluation is whether or not some IPR declaration
will be needed should CFRG select the proposal concerned. The actual
declaration would of course follow in due course but knowing now that
the proponents do not expect to have to make such a declaration would
be good input for me. So simply saying "this is the same as <<that>>"
is not a useful answer for me for any value of <<that>>.

Hopefully, the answer is that nobody has an issue saying that they
will not need to make an IPR declaration for their scheme, but
confirming that, or folks inability to state that, would be useful
as there is history in this space and that kind of problem could
also ensure that CFRG is delayed to the point where the chosen scheme
is overtaken by events.

Thanks,
S.

---

From: Dan Brown <[email-masked]>
Date: Mon, 31 Aug 2015 17:27:10 +0000

> -----Original Message-----
> From: Simon Josefsson
> 
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.