International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Optimal security proofs for PSS and other signature schemes

Authors:
Jean-S├ębastien Coron
Download:
URL: http://eprint.iacr.org/2001/062
Search ePrint
Search Google
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 $\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. Moreover, we show that this size is optimal: if less than $\log_2 q_{sig}$ 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.
BibTeX
@misc{eprint-2001-11474,
  title={Optimal security proofs for PSS and other signature schemes},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Probabilistic Signature Scheme, provable security, random oracle model.},
  url={http://eprint.iacr.org/2001/062},
  note={ coron@clipper.ens.fr 11540 received 6 Aug 2001},
  author={Jean-S├ębastien Coron},
  year=2001
}