Anonymous Tokens with Private Metadata Bit
Ben Kreuter, Tancrède Lepoint, Michele Orrù, Mariana Raykova
Abstract
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.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
16 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers16
- With a Little Help from My Friends: Constructing Practical Anonymous CredentialsLucjan Hanzlik, Daniel SlamanigCCS 2021 · 52 citations
- Aggregate Signatures with Versatile Randomization and Issuer-Hiding Multi-Authority Anonymous CredentialsOmid Mir, Balthazar Bauer, Scott Griffy, Anna Lysyanskaya et al.CCS 2023 · 29 citations
- A Fast and Simple Partially Oblivious PRF, with ApplicationsNirvan Tyagi, Sofía Celi, Thomas Ristenpart, Nick Sullivan et al.EUROCRYPT 2022 · 28 citations
- STAR: Secret Sharing for Private Threshold Aggregation ReportingAlex Davidson, Peter Snyder, E. B. Quirk, Joseph Genereux et al.CCS 2022 · 14 citations
- Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACsMelissa Chase, F. Betül Durak, Serge VaudenayCRYPTO 2023 · 12 citations
Related papers
- Security Analysis of Privately Verifiable Privacy PassKonrad Hanff, Anja Lehmann, Cavit ÖzbayCCS 2025
- Blind Multisignatures for Anonymous Tokens with Decentralized IssuanceIoanna Karantaidou, Omar Renawi, Foteini Baldimtsi, Nikolaos Kamarinakis et al.CCS 2024 · 7 citations
- Anonymous Tokens with Designated-Reader Metadata BitAisha Tu, Meng Jia, Kun He, Jing Chen et al.USENIX Security 2026
- Non-interactive Anonymous Tokens with Private Metadata BitFoteini Baldimtsi, Lucjan Hanzlik, Quan Nguyen, Aayush YadavCCS 2026 · 5 citations
- Non-interactive Blind Signatures from RSA Assumption and MoreLucjan Hanzlik, Eugenio Paracucchi, Riccardo ZanottoEUROCRYPT 2025 · 4 citations
