Paper 2022/1622

Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs

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

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 whether the bit extraction succeeded. 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. We obtain 20% more efficient performance.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
one-time anonymous tokenshidden metadata bitalgebraic MACs
Contact author(s)
melissac @ microsoft com
betuldurak @ microsoft com
serge vaudenay @ epfl ch
History
2023-06-13: last of 2 revisions
2022-11-21: received
See all versions
Short URL
https://ia.cr/2022/1622
License
Creative Commons Attribution
CC BY

BibTeX

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