Cryptology ePrint Archive: Report 2011/673

Pseudorandom Signatures

Nils Fleischhacker and Felix Günther and Franziskus Kiefer and Mark Manulis and Bertram Poettering

Abstract: We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is \emph{pseudorandomness}: signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very strong unlinkability guarantees across different signers and even different signing algorithms, and gives rise to new forms of private public-key authentication.

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 format(s): 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)

Short URL:

[ Cryptology ePrint archive ]