[CFRG] Re: FW: New Version Notification for draft-prabel-cfrg-suf-hybrid-sigs-00.txt

["Bellebaum, Thomas" <[e-mail]>]

Nice, thank you, especially for the non-blackbox analysis :)

I do have some initial comments:

1. You might want to be more specific when stating that RSA is not SUF-CMA. There are multiple RSA-derived signature schemes, and some of them are indeed SUF-CMA. See also below.

2. Some of the PQ-requirements for the non-blackbox variant are easily covered using simple transformations such as adding a hash of message m'' and public key pk2 to the signature s2. The overhead in the signature size seems negligable compared to most PQ signature sizes and to the time required for researchers to analyze each possible signature scheme for these properties individually. The same goes for many of the additional defenses present in e.g. draft-josefsson-cfrg-mothma.

3. It may even be possible to use the non-blackbox construction to cover some RSA signatures.
This would ease the transition for some people with hardware without ECC support. (That said, if one is investing in PQ-algorithms, one might as well invest in ECC hardware.)
Specifically, think of the following ID-scheme for RSA public key (n,e) and private key d:

- The prover outputs the empty commitment ""
- The verifier outputs a random challenge y in [0,n-1]
- The prover outputs the (unique; easy to check) response x := y^d mod n

This simple ID-scheme is of course secure against direct attacks (assuming RSA is a trapdoor permutation) and zero knowledge (Simulator picks x at random, and given the public key calculates y).

Compiling this down using Fiat Shamir yields basically the Full Domain Hash, although the lack of an unpredictable commitment scheme means that the usual generic proof needs to be reworked slightly: Instead of arguing that the FS-transform never evaluates the Challenge-hash at a point previously queried to the random oracle, one argues that even if that happens the random oracle could have generated its outputs using the simulator. Note that this is basically what the standard FDH proof does.

Alternatively, one can send a random string as commitment and rely on the more standard FS transform. If you pull some trickery in the challenge generation such that the random commitment can be recovered from y, you get RSA-PSS after a more standard FS transform. Again, this is very much along the lines of the RSA-PSS security argument.

Best,

-- TBB