Chennai Mathematical Institute

Seminars




3.30 p.m.
On the impossibility of instantiating PSS in the standard model

Rishiraj Bhattacharyya
ISI Kolkata.
28-04-11


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, 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 in standard model (the hash function is described as a circuit) 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}. 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.

The talk is self contained. All required concept of cryptography will be introduced.

joint work with Avradip Mandal. Published in Public Key Cryptography (PKC) 2011.