[BA] 1-out-of-2 Equivocal Commitments and Σ-Protocols

252 / BBB

2026-06-23

Pablo Schmeiser

15:45

Zero-knowledge-proofs of disjunctive statements are a crucial building block for privacy- preserving applications, such as anonymous credentials and ring signatures. However, constructing concretely efficient disjunctive proofs generally requires a trade-off. Existing highly efficient protocols either rely on strong, structured cryptographic assumptions like the Discrete Logarithm (DLOG) problem, which are vulnerable to quantum adversaries, or rely on idealized models like the Random Oracle Model (ROM). Conversely, protocols relying strictly on unstructured Minicrypt assumptions, such as collision-resistant hash functions (CRHFs), typically suffer from high communication overhead due to heavy, interactive cut-and-choose techniques. This thesis proposes a novel, concretely efficient compiler for Σ-protocols that relies solely on CRHFs in the standard model, successfully bridging the gap between minimal assumptions and concrete efficiency. We achieve this by replacing traditional cut-and-choose methods with a coding-theoretic approach. We construct a 1-out-of-2 bit-commitment scheme and lift it to a string-level commitment using Reed-Solomon encoding. Global consistency is enforced through the code’s minimum distance properties combined with local spot- checking. We rigorously prove via hybrid arguments that our base construction satisfies extended honest-verifier zero-knowledge (EHVZK). Through recursive composition, this yields a 1-out-of-l proof of knowledge with an asymptotic communication complexity of 𝑂 (𝜆 2 log(𝜆) log(𝑛) + CC(Π)). Furthermore, we provide a strict mathematical derivation of the protocol’s parameters, balancing hypergeometric intersection bounds against the code’s evasion bounds. Our evaluation demonstrates that the construction is practically viable, achieving a total communication size of approximately 3 Megabytes for a standard 128-bit security level.