Cryptology ePrint Archive: Report 2020/293

"Many-out-of-Many" Proofs with 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.

Category / Keywords: cryptographic protocols / anonymity, combinatorial cryptography, electronic commerce and payment, zero knowledge

Date: received 5 Mar 2020, last revised 4 Jun 2020

Contact author: benediamond at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200605:034538 (All versions of this report)

Short URL: ia.cr/2020/293


[ Cryptology ePrint archive ]