We show that one way towards pseudorandom signatures leads over our mid-level notion, called \emph{indistinguishability}: such signatures can be simulated using only the public parameters of the scheme. As we reveal, indistinguishable signatures exist in different cryptographic settings (e.g. based on RSA, discrete logarithms, pairings) and can be efficiently lifted to pseudorandomness deploying general transformations using appropriate encoding techniques. We also examine a more direct way for obtaining pseudorandomness for any unforgeable signature scheme. All our transformations work in the standard model. We keep public verifiability of signatures in the setting of system-wide known public keys. Some results even hold if signing keys are disclosed to the adversary --- given that signed messages have high entropy.
Category / Keywords: public-key cryptography / signatures, privacy, pseudorandom signatures, anonymous signatures, confidential signatures Publication Info: Full version of the paper that appears at ASIACCS 2013. Date: received 11 Dec 2011, last revised 4 Mar 2013 Contact author: mark at manulis eu Available formats: PDF | BibTeX Citation Note: Updated full version, including the complete discussion on privacy and impossibility results for deterministic signature schemes. Version: 20130304:150115 (All versions of this report) Discussion forum: Show discussion | Start new discussion