Round 3 Signature schemes’ guarantees beyond unforgeability? Exclusive ownership, message-bound security, and non re-signability

[Cas Cremers]

Dear all,

We just completed an analysis of the round 3 PQC signature schemes with respect to the properties of exclusive ownership, message-bound security, and non re-signability. These relate to providing guarantees even in the presence of maliciously generated keys (such as  the absence of duplicate signature key selection attacks), and other subtle issues that are not guaranteed by unforgeability. The full details of these properties and our analysis can be found here:

https://eprint.iacr.org/2020/1525

Until now, these properties have not been part of the requirements for the NIST competition. Thus, while we find that several candidates do not provide these properties, our findings do not violate any stated claims, but they do indicate that some schemes would be harder to misuse by implementers than others. Historically, the absence of these properties has led to attacks. We also show in our paper that it is easy to adapt all current schemes to provably provide these properties.

We feel that the situation is similar to the length-extension behavior for hash functions: while the absence of length-extension attacks is not part of the standard notion for hash functions, it seems prudent to choose hash functions that don’t allow such behavior. This is explicitly stated as a guarantee in the NIST SHA-3 documentation.

In the same vein, we would like to argue that when proposing the next standardized signature schemes, these signature schemes should provide stronger properties than (just) unforgeability, such as security in the presence of maliciously generated keys. Notably, we don’t know of any argument against providing these properties, and since achieving them is “cheap”, we think that not strictly requiring them would be a missed opportunity for NIST.

Opinions and suggestions welcome!

Best wishes,

Cas & Samed & Rune & Marc & Christian