Lune

CCS2026Top-tier venue

Non-interactive Anonymous Tokens with Private Metadata Bit

Foteini Baldimtsi, Lucjan Hanzlik, Quan Nguyen, Aayush Yadav

Abstract

Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. However, all existing ATPM protocols require interaction during issuance as the client must send a blinded request and wait for the issuer to sign, introducing latency and scalability bottlenecks. In this work, we present the first Non-interactive Anonymous Token (NIAT) scheme with a private metadata bit. Our design builds on structure-preserving signatures on equivalence classes (SPS-EQ) and recent advances in non-interactive blind signatures. With NIAT, tokens can be issued without any online interaction, enabling asynchronous pre-computation and drastically reducing issuer workload. We formalize NIAT security definitions, propose an efficient construction under standard assumptions and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend a token (i.e., present the same token twice) and argue that non-interactive schemes are uniquely positioned to offer this essential feature.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Anonymous Tokens with Designated-Reader Metadata Bit cites Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACs
  • Anonymous Tokens with Designated-Reader Metadata Bit cites Anonymous Tokens with Private Metadata Bit
  • Anonymous Tokens with Designated-Reader Metadata Bit cites Non-interactive Blind Signatures for Random Messages
  • Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACs cites Anonymous Tokens with Private Metadata Bit
  • A Fast and Simple Partially Oblivious PRF, with Applications cites Anonymous Tokens with Private Metadata Bit
  • With a Little Help from My Friends: Constructing Practical Anonymous Credentials cites Anonymous Tokens with Private Metadata Bit
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Anonymous Tokens with Designated-Reader Metadata BitAisha Tu, Meng Jia, Kun He, Jing Chen et al.USENIX Security 2026

Builds on7

  1. With a Little Help from My Friends: Constructing Practical Anonymous CredentialsLucjan Hanzlik, Daniel SlamanigCCS 2021 · 52 citations
  2. Anonymous Tokens with Private Metadata BitBen Kreuter, Tancrède Lepoint, Michele Orrù, Mariana RaykovaCRYPTO 2020 · 35 citations
  3. A Fast and Simple Partially Oblivious PRF, with ApplicationsNirvan Tyagi, Sofía Celi, Thomas Ristenpart, Nick Sullivan et al.EUROCRYPT 2022 · 28 citations
  4. Non-interactive Blind Signatures for Random MessagesLucjan HanzlikEUROCRYPT 2023 · 17 citations
  5. Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACsMelissa Chase, F. Betül Durak, Serge VaudenayCRYPTO 2023 · 12 citations

Related papers

  1. Blind Multisignatures for Anonymous Tokens with Decentralized IssuanceIoanna Karantaidou, Omar Renawi, Foteini Baldimtsi, Nikolaos Kamarinakis et al.CCS 2024 · 7 citations
  2. Non-Transferable Anonymous Tokens by Secret BindingF. Betül Durak, Laurane Marco, Abdullah Talayhan, Serge VaudenayCCS 2024 · 6 citations
  3. Non-interactive Blind Signatures from RSA Assumption and MoreLucjan Hanzlik, Eugenio Paracucchi, Riccardo ZanottoEUROCRYPT 2025 · 4 citations
  4. Doubly Aggregatable SignaturesGeorg Fuchsbauer, Pranav Garimidi, Joachim Neu, Guru-Vamsi Policharla et al.CCS 2026
  5. Snowblind: A Threshold Blind Signature in Pairing-Free GroupsElizabeth C. Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro et al.CRYPTO 2023 · 36 citations
Dusk over the sea between two cliffs drawn in fine vertical lines