Many-out-of-Many Proofs and Applications to Anonymous Zether

Benjamin E.  Diamond

Paper 2020/293

Many-out-of-Many Proofs and Applications to Anonymous Zether

Benjamin E. Diamond

Abstract

Anonymous Zether, proposed by Bünz, Agrawal, Zamani, and Boneh (FC'20), is a private payment design whose wallets demand little bandwidth and need not remain online; this unique property makes it a compelling choice for resource-constrained devices. In this work, we describe an efficient construction of Anonymous Zether. Our protocol features proofs which grow only logarithmically in the size of the "anonymity sets" used, improving upon the linear growth attained by prior efforts. It also features competitive transaction sizes in practice (on the order of 3 kilobytes). Our central tool is a new family of extensions to Groth and Kohlweiss's one-out-of-many proofs (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of a public list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Remarkably, our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. This technique is likely to be of independent interest. We present an open-source, Ethereum-based implementation of our Anonymous Zether construction.

Note: Full version of conference paper.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. IEEE Symposium on Security and Privacy 2021
DOI: 10.1109/SP40001.2021.00026
Keywords: anonymity combinatorial cryptography electronic commerce and payment zero knowledge
Contact author(s): benjamin e diamond @ jpmchase com
History: 2020-10-26: last of 2 revisions; 2020-03-06: received; See all versions
Short URL: https://ia.cr/2020/293
License: CC BY

BibTeX

@misc{cryptoeprint:2020/293,
      author = {Benjamin E.  Diamond},
      title = {Many-out-of-Many Proofs and Applications to Anonymous Zether},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/293},
      year = {2020},
      doi = {10.1109/SP40001.2021.00026},
      url = {https://eprint.iacr.org/2020/293}
}