Subject: [CFRG] Re: FW: New Version Notification for draft-prabel-cfrg-suf-hybrid-sigs-00.txt
From: Peter C <[email-masked]>
To: "[email-masked]" <[email-masked]>
Cc: "Bellebaum, Thomas" <thomas.bellebaum=[email-masked]>, "lucas.prabel=[email-masked]" <lucas.prabel=[email-masked]>
Date: Wed, 22 Oct 2025 16:14:15 +0000
List-Id: Crypto Forum Research Group <cfrg.irtf.org>

OFFICIAL

> 3. It may even be possible to use the non-blackbox construction to cover
> some RSA signatures.

The non-blackbox construction in the draft is BoP-2 from [Jan25].  BoP-3
applies directly to (randomised) RSA-FDH and RSASSA-PSS, and it avoids
the additional Message-Bound Security and Random-Message Validity
assumptions on the post-quantum component.

Peter

> -----Original Message-----
> From: Bellebaum, Thomas
> <thomas.bellebaum=[email-masked]>
> Sent: 22 October 2025 15:40
> To: lucas.prabel=[email-masked]
> Cc: [email-masked]
> Subject: [CFRG] Re: FW: New Version Notification for draft-prabel-cfrg-suf-
> hybrid-sigs-00.txt
>
> 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

OFFICIAL