### On the Impossibility of Instantiating PSS in the Standard Model

##### 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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2010/651

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.