Optimal Security Proofs for PSS and Other Signature Schemes

The Probabilistic Signature Scheme (PSS) designed by Bellare and Rogaway is a signature scheme provably secure against chosen message attacks in the random oracle model, whose security can be tightly related to the security of RSA. We derive a new security proof for PSS in which a much shorter random salt is used to achieve the same security level, namely we show that log₂q_sig bits suffice, where q _sig is the number of signature queries made by the attacker. When PSS is used with message recovery, a better bandwidth is obtained because longer messages can now be recovered. In this paper, we also introduce a new technique for proving that the security proof of a signature scheme is optimal. In particular, we show that the size of the random salt that we have obtained for PSS is optimal: if less than log₂q_sig bits are used, then PSS is still provably secure but it cannot have a tight security proof. Our technique applies to other signature schemes such as the Full Domain Hash scheme and Gennaro-Halevi-Rabin’s scheme, whose security proofs are shown to be optimal.