Paper 2026/1248

Atlantis: Lattice-based Anonymous Tokens with Private Metadata Bit

Abstract

Anonymous tokens with private metadata bit (ATPM) allow an issuer to embed a hidden trust flag, as a single bit, within issued tokens. The bit remains hidden from the clients, but verifiers can read the bit and rate-limit or discard tokens marked suspect. A series of ATPM constructions exist in the literature, however all current constructions rely on classical hardness assumptions such as RSA groups, pairings, or elliptic-curve VRFs and do not provide any post-quantum security guarantees. In this work we present, the first ATPM scheme based on lattice assumptions. Tokens generated with our scheme are publicly verifiable, and privately bit-extractable given partial knowledge of the issuing authority's secret. Our design follows the Fischlin blind-signature paradigm and enriches it with lattice-based linearly-homomorphic encryption to carry the hidden bit. We also instantiate our scheme from Falcon-512 and the efficient LNP22 lattice NIZK proof system (Lyubashevsky et. al, Crypto '22). The resulting protocol, which we call $\textsf{Atlantis}$, requires 70 KB of client-issuer communication and yields 129 KB tokens.