Cryptology ePrint Archive: Report 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.

Category / Keywords: PSS, Blackbox Reductions, Randomized Signature, Standard Model.

Publication Info: To appear in the proceedings of PKC 2011

Date: received 21 Dec 2010, last revised 21 Dec 2010

Contact author: rishi_r at isical ac in

Available format(s): PDF | BibTeX Citation

Note: This version contains all the proofs

Version: 20101221:170946 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]