Paper 2023/1900
Proof of Compliance for Anonymous, Unlinkable Messages
Abstract
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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Zero-knowledge ProofShuffle Model
- Contact author(s)
-
mingxunz @ andrew cmu edu
rshi @ andrew cmu edu
gfanti @ andrew cmu edu - History
- 2024-01-26: revised
- 2023-12-10: received
- See all versions
- Short URL
- https://ia.cr/2023/1900
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1900, 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{https://eprint.iacr.org/2023/1900}}, url = {https://eprint.iacr.org/2023/1900} }