[go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?

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 $\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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Probabilistic Signature Schemeprovable securityrandom oracle model.
Contact author(s)
coron @ clipper ens fr
History
2001-08-13: received
Short URL
https://ia.cr/2001/062
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.