Paper 2023/1900

Proof of Compliance for Anonymous, Unlinkable Messages

Mingxun Zhou, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
Giulia Fanti, Carnegie Mellon University

Anonymous systems are susceptible to malicious activity. For instance, in anonymous payment systems, users may engage in illicit practices like money laundering. Similarly, anonymous federated learning systems decouple user updates to a central machine learning model from the user's identity; malicious users can manipulate their updates to poison the model. Today, compliance with system-generated rules in such systems can be guaranteed at the level of a single message by utilizing Zero-Knowledge Proofs (ZKP). However, it remains unclear how to prove compliance for rules that are defined over a collection of a user's messages, without compromising the unlinkability of the messages. To address this challenge, we propose an efficient protocol called Shuffle-ZKP, which enables users within an unlinkable messaging system to collectively prove their compliance. Our protocol leverages a distributed and private set equality check protocol along with generic Non-Interactive Zero-Knowledge (NIZK) proof systems. We also provide an additional attributing protocol to identify misbehaving users. We theoretically analyze the protocol's correctness and privacy properties; we then implement and test it across multiple use cases. Our empirical results show that in use cases involving thousands of users, each user is able to generate a compliance proof within 0.2-10.6 seconds, depending on the use case, while the additional communication overhead remains under 3KB. Furthermore, the protocol is computationally efficient on the server side; the verification algorithm requires a few seconds to handle thousands of users in all of our use cases.

Available format(s)
Cryptographic protocols
Publication info
Zero-knowledge ProofShuffle Model
Contact author(s)
mingxunz @ andrew cmu edu
rshi @ andrew cmu edu
gfanti @ andrew cmu edu
2024-01-26: revised
2023-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mingxun Zhou and Elaine Shi and Giulia Fanti},
      title = {Proof of Compliance for Anonymous, Unlinkable Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1900},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.