Cryptology ePrint Archive: Report 2020/430

Hierarchical One-out-of-Many Proofs With Applications to Blockchain Privacy and Ring Signatures

Aram Jivanyan and Tigran Mamikonyan

Abstract: The one-out-of-many proof is a cryptographic zero-knowledge construction enabling the prover to demonstrate knowledge of a secret element among the given public list of cryptographic commitments opening to zero. This method is relying on standard Decisional Diffie-Hellman security assumptions and can result in efficient accountable ring signature schemes [4] and proofs of set memberships [5] with a signature size smaller than all existing alternative schemes relying on standard assumptions. This construction also serves as a fundamental building block for numerous recent blockchain privacy protocols including Anonymous Zether, Zerocoin, Lelantus, Lelantus-MW, Triptych and Triptych-2. One-out-of-many proofs require O(logN)-sized communication and can be implemented in O(N) time for the verifier and O(NlogN) time for the prover. In this work, we introduce a new method of instantiating one-out-of-many proofs which reduces the proof generation time by an order of magnitude. In certain practical applications our method also helps to fasten the verification process of multiple simultaneously generated proofs. Our approach still results in shorter proofs comprised of only a logarithmic number of commitments and does not compromise the highly efficient batch verification properties endemic to the original construction. We believe this work can also foster further research towards building more efficient one-out-of-many proofs which are extremely useful constructions in the blockchain privacy space and beyond.

Category / Keywords: cryptographic protocols / group signatures, ring signatures, confidential transactions, blockchain privacy, Zerocoin, Lelantus, one-out-of-many zero-knowledge proofs

Date: received 15 Apr 2020, last revised 15 Apr 2020

Contact author: aram at skycryptor com,reuben@zcoin io,poramin@zcoin io

Available format(s): PDF | BibTeX Citation

Version: 20200415:180324 (All versions of this report)

Short URL: ia.cr/2020/430


[ Cryptology ePrint archive ]