Paper 2011/673

Pseudorandom Signatures

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


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.

Note: Updated full version, including the complete discussion on privacy and impossibility results for deterministic signature schemes.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of the paper that appears at ASIACCS 2013.
signaturesprivacypseudorandom signaturesanonymous signaturesconfidential signatures
Contact author(s)
mark @ manulis eu
2013-03-04: last of 4 revisions
2011-12-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Felix Günther and Franziskus Kiefer and Mark Manulis and Bertram Poettering},
      title = {Pseudorandom Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2011/673},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.