Optimal security proofs for PSS and other signature schemes

Jean-Sébastien Coron

Paper 2001/062

Optimal security proofs for PSS and other signature schemes

Jean-Sébastien Coron

Abstract

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, with a security level equivalent to RSA. In this paper, 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 bits suffice, where 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. Moreover, we show that this size is optimal: if less than bits of random salt are used, PSS is still provably secure but no security proof can be tight. This result is based on a new technique which shows that other signature schemes such as the Full Domain Hash scheme and Gennaro-Halevi-Rabin's scheme have optimal security proofs.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Probabilistic Signature Scheme provable security random oracle model.
Contact author(s): coron @ clipper ens fr
History: 2001-08-13: received
Short URL: https://ia.cr/2001/062
License: CC BY

BibTeX

@misc{cryptoeprint:2001/062,
      author = {Jean-Sébastien Coron},
      title = {Optimal security proofs for {PSS} and other signature schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/062},
      year = {2001},
      url = {https://eprint.iacr.org/2001/062}
}