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

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 [1], [2], Zerocoin [3], Lelantus [11], Lelantus-MW [9], Triptych [14] and Triptych-2 [15]. 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. 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.