Non-interactive Anonymous Tokens with Private Metadata Bit

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. CCS Concepts • Security and privacy → Privacy-preserving protocols; Public key (asymmetric) techniques.