Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: D. J. Bernstein
> 
> Watson Ladd writes:
> > It seems as though determinism, one pass schemes, and avoiding
> > collision resistance are at odds, unfortunately
> 
> Probably one can split a message into
> 
>    * packet p0 plus a signature s0 of ("start",p0);
>    * packet p1 plus a signature s1 of ("middle",s0,p1);
>    * packet p2 plus a signature s2 of ("middle",s1,p2);
>    * ...;
>    * last packet pn plus a signature of ("end",previous s,pn).
> 

That's quite interesting!

---

I interpreted the chairs' #3 proposal to be something like this:

final_signature(m) 
= 
"0"|raw_signature("1pass", hash(message))
 or
"1"|raw-signature("2pass", message)
                    
The initial bit can be conveyed within the signature, or in the signer's
certificate if the signer is going to stick to one mode.

---

The goal of avoiding collision resistance seems worthwhile: at least, it
does when I think of MD5.

To reduce the reliance on collision-resistance in the 1pass case, the signer
can serialize the message, which we can codify, as in the example below.  

---

During initialization of the signature, the signer selects an unpredictable
value, such as

serializer=PRF(serializer_key, time | counter) 

The signer prepends serializer to the message, and then proceeds to sign as
usual.  

The signer either makes sure that every message it signs is serialized, or
else embeds an initial bit indicator prefix into the message to distinguish
between serialized and non-serialized signatures.

The verifier treats the serializer as part of the message, and does nothing
differently, except ignore the serializer.

The message suffers from some expansion, but the signature does not.  

The signature is still a deterministic function of the serialized message:
the signer has not touched any secret in the log space of the discrete
group, so we needn't worry about the usual repeated-ephemerals or
leak-and-lattice attacks, etc.

If the signer fails to implement the message serialization correctly, then
collision resistance is again needed, but not much else goes wrong.

---

Message serialization should not be confused with the signature's internal
ephemeral key/per-message secret/secret nonce, hence I've used a different
term.