Subject: [Cfrg] Brief review of signature schemes

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 11 Jul 2015 17:19:56 +0300

I thought to review the properites of the proposed schemes from
few PoVs:
- Protocol usage (how the scheme behaves as seen from outside)
- Coding (mainly "annoying" operations, e.g. inversion/sqrt
  mod order, random numbers, nonstandard hash APIs, non-
  baseline hashes or operations that seem really complex)
- If it would work with non-NPOT (even if non-NPOT Edwards
  curves are extremely rare) or E-521 curves with baseline
  hashes (max. 512 bits per shot).
- Extras like personalization, firewalling and batchability.
- Apparent starting scheme.

I might have missed some (for hashes, I assumed efficient non-
aligned processing, which good implementations of hashes seem
to do, and those that aren't good are slow anyway).

Obviously, YMMV on what properties are important and what are
not (e.g. working on curves beyond design with standard hashes
is probably not very important)...

Proposal by Watson Ladd:
------------------------
Online-only scheme. Has two online pipes, and needs the private key to
start the online pipe. Has logically one hash function.

Does not use inversions nor square roots mod order. No random numbers
outside keygen&batching. Works with standard hash APIs.

Non-NPOT safety unknown, does not extend to E-521 with baseline hashes.

Neither personalization nor firewalling is supported. Is batchable.

Derived from Schnorr scheme.

Proposal by Ilari Liusvaara:
----------------------------
Online/Offline scheme, dictated by the signer. Has one online pipe,
which is a raw hash. No information needed to start online pipe.
Has logically two hash functions.

Does not use inversions nor square roots mod order. No random numbers
outside keygen&batching, Works with standard hash APIs.

Non-NPOT safe, does not extend to E-521 with baseline hashes.

Personalization and firewalling supported, with arbitrary-length inputs.
Is batchable.

Derived from EdDSA.

Proposal by Dan Brown:
----------------------
Online-only scheme. Has two online pipes, and needs the private key to
start the online pipe. Has logically one hash function.

Has inversions mod order. Works with standard hash APIs. Specifies
blinding which in places some of which would need random numbers.

Non-NPOT safety unknown, unknown if extends to E-521 with baseline
hashes.

Neither personalization nor firewalling is supported. Is batchable.

Derived from ECDSA scheme (to me, it essentially seems like deterministic
ECDSA or something extremely close).

Proposal by Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe and Bo-Yin Yang:
---------------------------------------------------------------------------------------------
Online/Offline scheme, dictated by the key. Has one online pipe, which
is a raw hash. The inner hash specification from key is needed to
start online pipe. Has logically two hash functions.

Does not use inversions nor square roots mod order. No random numbers
outside keygen&batching. Hash extension does not seem to work with
standard APIs (and anything larger than Curve25519 will use that
extension). The specified basepoint for 448-bit curve does not look
to be Curve448-compatible[1].

Non-NPOT safe, extends to E-521 with baseline hashes.

Neither personalization nor firewalling is supported. Is batchable.

Derived from EdDSA scheme.

Proposal by Mike Hamburg:
--------------------------
Online/Offline scheme, dictated by the signer. Has one online pipe,
which is a raw hash. No information needed to start online pipe.
Has logically two hash functions.

Does not use inversions nor square roots mod order. No random numbers
outside keygen. Works with standard hash APIs.

Not Non-NPOT safe, does not extend to E-521 with baseline hashes.

Personalization and firewalling share common fixed-length 64-bit field.
Is not batchable.

Derived from Schnorr scheme.

[1] AFAICT, the Curve448-compatible basepoint is: y=
693F46716EB6BC248876203756C9C7624BEA73736CA3984087789C1E05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD9808795BF230FA14
x either valid value, as there (y/x)^2=5 mod p.

Sidenote: Why in cfrg-curves draft the isogeny is specified as (x/y)^2,
given that:
(1,0)+(1,0) = (0,-1)
(1,0) transforms to infinity
(0,-1) transforms to 0M.
infinity+infinity = infinity != 0M

Whereas (y/x)^2 transforms those as:
(1,0)+(1,0) = (0,-1)
(1,0) transforms to 0M.
(0,-1) transforms to infinity
0M+0M=infinity.

(My prototype ECC lib also uses (y/x)^2, and has fair bit of testing
with Edwards/Montgomery consistency.)

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Sat, 11 Jul 2015 13:10:32 -0700

Oop, resending to the list, sorry Ilari:

> On Jul 11, 2015, at 7:19 AM, Ilari Liusvaara <[email-masked]> wrote:

This shouldn’t be true: the +8 byte ephemeral nonce was intended to be
for non-NPOT safety, as it is not required for NPOT.  If I understand correctly,
this caps the adversary’s advantage at one bit of information per 2^64 observed
signatures with a hybrid argument, but the hybrid argument is loose and many
more signatures would be required.  Anyway, if +8 isn’t enough, then it should
be 5/4+8 or 3/2 or whatever is enough.

Also, while it’s less relevant: the proposal does extend to E-521 with baseline
hashes, but only in the short configuration, where a 264-bit hash is required.

> Sidenote: Why in cfrg-curves draft the isogeny is specified as (x/y)^2,

Yeah, that would be a bug, and my fault.  The isogeny to the JQ is x/y, but that’s because the base point of the JQ is (0,1) instead of infinity.

Thanks,
— Mike

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 11 Jul 2015 23:44:42 +0300

> be 5/4+8 or 3/2 or whatever is enough.

Hmm... Trying to calculate via entropy I get >2^128 signatures for one bit of
leakage (+3-10 bits) for a few different curves.

The apparent source of that 5/4 was extrapolating from trying to calculate
needed extra bits for brainpool curves using criteria I use (which is quite
paranoid):

Brainpool-256: 63 extra bits
Brainpool-320: 79 extra bits
Brainpool-384: 94 extra bits
Brainpool-512: 127 extra bits.

Haven't checked if 5/4 would give enough bits for criteria I use in absolute
worst case.

Hmm... It seems like calculating via entropy gives that one needs >2^(2n)
signatures to leak 1 bit where n is number of extra bits... Or thereabouts.

> hashes, but only in the short configuration, where a 264-bit hash is required.

Or one could probably also use 512-bit "public" hash even with E-521, which
would be "near full length"?

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Sat, 11 Jul 2015 13:56:00 -0700

> On Jul 11, 2015, at 1:44 PM, Ilari Liusvaara <[email-masked]> wrote:
> 

Yes.  That would work with any of the Schnorr variants proposed, in fact.  But nobody specced it.

— Mike