Paper 2022/1622

Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs

F. Betül Durak, Microsoft Research
Serge Vaudenay, École Polytechnique Fédérale de Lausanne
Melissa Chase, Microsoft Research

On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish honest users from bots or attackers. In this work, we focus on designing an anonymous token protocol between a client and an issuer (also a verifier) that enables the issuer to support its fraud detection mechanisms while preserving users' privacy. This is done by allowing the issuer to embed a hidden (from the client) metadata bit into the tokens. We first study an existing protocol from CRYPTO 2020 which is an extension of Privacy Pass from PoPETs 2018; that protocol aimed to provide support for a hidden metadata bit, but provided a somewhat restricted security notion. We demonstrate a new attack, showing that this is a weakness of the protocol, not just the definition. In particular, the metadata bit hiding is weak in the setting where the attacker can redeem some tokens and get feedback on what bit is extracted. We then revisit the formalism of anonymous tokens with private metadata bit, consider the more natural notion, and design a scheme which achieves it. In order to design this new secure protocol, we base our construction on algebraic MACs instead of PRFs. Our security definitions capture a realistic threat model where adversaries could, through direct feedback or side channels, learn the embedded bit when the token is redeemed. Finally, we compare our protocol with one of the CRYPTO 2020 protocols which we obtain 20\% more efficient implementation.

Note: Fixing a typo in names.

Available format(s)
Cryptographic protocols
Publication info
one-time anonymous tokens hidden metadata bit algebraic MACs
Contact author(s)
betuldurak @ microsoft com
serge vaudenay @ epfl ch
melissac @ microsoft com
2022-12-01: revised
2022-11-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {F. Betül Durak and Serge Vaudenay and Melissa Chase},
      title = {Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1622},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.