Paper 2023/1483

Lower Bounds on Anonymous Whistleblowing

Willy Quach, Weizmann Institute of Science
LaKyah Tyner, Northeastern University
Daniel Wichs, Northeastern University, NTT Research

Anonymous transfer, recently introduced by Agrikola, Couteau and Maier [ACM22] (TCC '22), allows a sender to leak a message anonymously by participating in a public non-anonymous discussion where everyone knows who said what. This opens up the intriguing possibility of using cryptography to ensure strong anonymity guarantees in a seemingly non-anonymous environment. The work of [ACM22] presented a lower bound on anonymous transfer, ruling out constructions with strong anonymity guarantees (where the adversary's advantage in identifying the sender is negligible) against arbitrary polynomial-time adversaries. They also provided a (heuristic) upper bound, giving a scheme with weak anonymity guarantees (the adversary's advantage in identifying the sender is inverse in the number of rounds) against fine-grained adversaries whose run-time is bounded by some fixed polynomial that exceeds the run-time of the honest users. This leaves a large gap between the lower bound and the upper bound, raising the intriguing possibility that one may be able to achieve weak anonymity against arbitrary polynomial time adversaries, or strong anonymity against fine grained adversaries. In this work, we present improved lower bounds on anonymous transfer, that rule out both of the above possibilities: - We rule out the existence of anonymous transfer with any non-trivial anonymity guarantees against general polynomial time adversaries. - Even if we restrict ourselves to fine-grained adversaries whose run-time is essentially equivalent to that of the honest parties, we cannot achieve strong anonymity, or even quantitatively improve over the inverse polynomial anonymity guarantees (heuristically) achieved by [ACM22]. Consequently, constructions of anonymous transfer can only provide security against fine-grained adversaries, and even in that case they achieve at most weak quantitative forms of anonymity.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
Lower BoundsAnonymous TransferFine-grained Cryptography
Contact author(s)
willy quach @ weizmann ac il
tyner l @ northeastern edu
wichs @ ccs neu edu
2023-10-02: approved
2023-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Willy Quach and LaKyah Tyner and Daniel Wichs},
      title = {Lower Bounds on Anonymous Whistleblowing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1483},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.