Paper 2010/651

On the Impossibility of Instantiating PSS in the Standard Model

Rishiraj Bhattacharyya and Avradip Mandal

Abstract

In this paper we consider the problem of securely instantiating Probabilistic Signature Scheme (PSS) in the standard model. PSS, proposed by Bellare and Rogaway \cite{BellareR96} is a widely deployed randomized signature scheme, provably secure (\emph{unforgeable under adaptively chosen message attacks}) in Random Oracle Model. \\ Our main result is a black-box impossibility result showing that one can not prove unforgeability of PSS against chosen message attacks using blackbox techniques even assuming existence of \emph{ideal trapdoor permutations} (a strong abstraction of trapdoor permutations which inherits all security properties of a random permutation, introduced by Kiltz and Pietrzak in Eurocrypt 2009) or the \emph{lossy trapdoor permutations} \cite{PeikertW08}. Moreover, we show \emph{onewayness}, the most common security property of a trapdoor permutation does not suffice to prove even the weakest security criteria, namely \emph{unforgeability under zero message attack}. Our negative results can easily be extended to any randomized signature scheme where one can recover the random string from a valid signature.

Note: This version contains all the proofs

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. To appear in the proceedings of PKC 2011
Keywords
PSSBlackbox ReductionsRandomized SignatureStandard Model.
Contact author(s)
rishi_r @ isical ac in
History
2010-12-21: revised
2010-12-21: received
See all versions
Short URL
https://ia.cr/2010/651
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/651,
      author = {Rishiraj Bhattacharyya and Avradip Mandal},
      title = {On the Impossibility of Instantiating PSS in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2010/651},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/651}},
      url = {https://eprint.iacr.org/2010/651}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.