Subject: [Cfrg] Schnorr signature encodings

From: Bryan Ford <[email-masked]>
Date: Wed, 22 Jul 2015 17:39:15 +0200

I wanted to thank Mike Hamburg again for a nice summary today of some of the tradeoffs between the (point,int) and (int,int) formats for Schnorr signatures.

The two formats appear to be - or could be defined to be - fully inter-convertible: a signature in either format can be converted to the other via a simple 1-to-1 transformation.  One format is a bit larger but amenable to batch verification; hence we might call this “Fast Format.”  The other format (challenge-response) can be ~25% shorter and requires no point parsing for verification; hence we might call this “Short Format.”

There seems to be a bit of a parallel between this choice and the two standard point encodings (“normal” versus “compressed”) that are defined for the established NIST-standard elliptic curves, and both of which are routinely used in practice.  As such, without suggesting that this is necessarily the right thing to do, it might be worth considering the possibility that any CFRG-standard signature scheme could simply specify both formats, with the simple and obvious method of converting either to the other, and leave it to the higher-level protocol or application to decide which format is used in that particular application/protocol context (or let the application protocol provide a way to select/negotiate between the two if that proves sufficiently desirable for a particular application).

Of course there are clear downsides to any standard specifying two different possible encoding formats for the same logical blob - e.g., size/complexity of the standard, accidental risk of breakage by communication parters failing to agree which format is being used, etc.  It’s not immediately clear to me whether the flexibility benefits of “providing that choice” justify the complexity cost.

Bryan