Cryptology ePrint Archive: Report 2020/293

"Many-out-of-Many" Proofs with Applications to Anonymous Zether

Benjamin E. Diamond

Abstract: We introduce a family of extensions to the one-out-of-many proofs of Groth and Kohlweiss (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of the list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. Our work introduces a new "circular rotation" technique, and a novel instantiation of the number-theoretic transform.

Applying these techniques, we construct a protocol for the Anonymous Zether payment system—as proposed in Bünz, Agrawal, Zamani, and Boneh (FC'20)—which improves upon the communication complexity attained by existing efforts. We describe an open-source, Ethereum-based implementation of our protocol.

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

Date: received 5 Mar 2020

Contact author: benediamond at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200306:085346 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]