Subject: [Cfrg] Comparision of ECC signature proposals (version 2)

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 28 Aug 2015 19:40:16 +0300

Reposting this with some updates, as requested...

Changelog from previous:
- Dropped MH
- I don't actually know what determines prehash in DJB&et al.
- Updated hash extension in DJB&et al.
- Updated DB (inversion elimination)
- Added signature sizes (DB has larger ones than others).

(I hope I didn't miss any updates that should be done).

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). All schemes could be made to work with both
  by adjusting generation of secret scalar.
- Extras like personalization, firewalling and batchability.
- Number of non-padding bits in 255/448-bit signatures (assumed
  fixed-width fields).
- 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.

Signature size: 509/895 (64/112 octets)

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.

Signature size: 509/895 (64/112 octets)

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.

Does not use inversions nor square roots mod order. No random numbers
outside keygen&batching, Works with standard hash APIs (verification
needs triple-scalar or inversion+double-scalar).

Non-NPOT safe and extends to E-521 if generation of secret scalar is
done suitably (the width is not specified exactly).

Neither personalization nor firewalling is supported. Is batchable.

Signature size: 762/1341 (96/168 octets)

Derived from ECDSA scheme.

Proposal by Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe and Bo-Yin Yang:
---------------------------------------------------------------------------------------------
Online/Offline scheme, dictated by ???[1]. Has one online pipe, which
is a raw hash. No private 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. Hash extension updated to work with standard
API, specified basepoint for 448-bit curve different from one in cfrg-
curves I-D.

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

Neither personalization nor firewalling is supported. Is batchable.

Signature size: 509/895 (64/112 octets)

Derived from EdDSA scheme.

[1] In earlier message, I thought that prehash is dictated by the key,
but DJB posted message stating it is not so, so I don't know exactly
what determines the prehash.

If it is application on per-signature basis, mixing up online and
offline modes with the same key can create trouble (as pointed out
by AGL). And even with different hashes of the same length, no
standard assumptions imply security (even if in practice hash functions
don't interact).

-Ilari