Paper 2020/072

Anonymous Tokens with Private Metadata Bit

Ben Kreuter, Tancrède Lepoint, Michele Orrù, and Mariana Raykova


We present a cryptographic construction for anonymous tokens with private metadata bit, called PMBTokens. This primitive enables an issuer to provide a user with a lightweight, single-use anonymous trust token that can embed a single private bit, which is accessible only to the party who holds the secret authority key and is private with respect to anyone else. Our construction generalizes and extends the functionality of Privacy Pass (PETS’18) with this private metadata bit capability. It is based on the DDH and CTDH assumptions in the random oracle model and provides unforgeability, unlinkability, and privacy for the metadata bit. Both Privacy Pass and PMBTokens rely on non-interactive zero-knowledge proofs (NIZKs). We present new techniques to remove the need for NIZKs, while still achieving unlinkability. We implement our constructions and we report their efficiency costs.

Note: This version corrects typos/errors in Construction 6 reported by Serge Vaudenay; we revert to the construction described in the 2020-03-24 version.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.CRYPTO 2020
Contact author(s)
benkreuter @ google com
crypto @ tancre de
michele orru @ ens fr
marianar @ google com
2022-04-21: last of 4 revisions
2020-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ben Kreuter and Tancrède Lepoint and Michele Orrù and Mariana Raykova},
      title = {Anonymous Tokens with Private Metadata Bit},
      howpublished = {Cryptology ePrint Archive, Paper 2020/072},
      year = {2020},
      doi = {10.1007/978-3-030-56784-2_11},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.