Paper 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.