Summary: The probabilistic signature scheme (PSS) designed by M. Bellare and P. Rogaway [Eurocrypt 1996, Lect. Notes Comput. Sci. 1070, 399–416 (1996; Zbl 1304.94094)] 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_2 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_2 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 the Gennaro-Halevi-Rabin scheme, whose security proofs are shown to be optimal.
For the entire collection see [Zbl 0984.00084].