Paper 2023/1900

Conan: Distributed Proofs of Compliance for Anonymous Data Collection

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

We consider how to design an anonymous data collection protocol that enforces compliance rules. Imagine that each client contributes multiple data items (e.g., votes, location crumbs, or secret shares of its input) to an anonymous network, which mixes all clients' data items so that the receiver cannot determine which data items belong to the same user. Now, each user must prove to an auditor that the set it contributed satisfies a compliance predicate, without identifying which items it contributed. For example, the auditor may want to ensure that no one voted for the same candidate twice, or that a user's location crumbs are not too far apart in a given time interval. Our main contribution is a novel anonymous, compliant data collection protocol that realizes the above goal. In comparison with naive approaches such as generic multi-party computation or earlier constructions of collaborative zero-knowledge proofs, the most compelling advantage of our approach is that each client's communication and computation overhead do not grow with respect to the number of clients $n$. In this sense, we save a factor of at least $n$ over prior work, which allows our technique to scale to applications with a large number of clients, such as anonymous voting and privacy-preserving federated learning. We first describe our protocol using generic cryptographic primitives that can be realized from standard assumptions. We then suggest a concrete instantiation called {\sc Conan} which we implement and evaluate. In this concrete instantiation, we are willing to employ SNARKs and the random oracle model for better practical efficiency. Notably, in this practical instantiation, each client's additional communication overhead (not counting the overhead of sending its data items over the anonymous network) is only $\widetilde{O}(1)$. We evaluated our technique in various application settings, including secure voting, and secure aggregation protocols for histogram, summation, and vector summation. Our evaluation results show that each client's additional communication overhead is only 2.2KB or 2.6KB, depending on which SNARK implementation we use. Further, each client's computation is only 0.2s - 0.5s for almost all cases, except for the vector summation application where the data items are high-dimensional and each client's computation is 8.5-10.6s.

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-06-04: last of 3 revisions
2023-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mingxun Zhou and Elaine Shi and Giulia Fanti},
      title = {Conan: Distributed Proofs of Compliance for Anonymous Data Collection},
      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.