Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, Muthuramakrishnan Venkitasubramaniam
Abstract
Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses \mathcalL _1 łor \cdots łor \mathcalL _B. Typically, ZK requires paying the price to handle all B branches. Prior works have shown how to avoid this price in communication, but not in computation.
Topics & Concepts
Mathematical proofComputer scienceScalabilityInefficiencyComputationParallel computingTheoretical computer scienceProgramming languageMathematicsDatabaseEconomicsMicroeconomicsGeometryCryptography and Data SecurityComplexity and Algorithms in GraphsSecurity and Verification in Computing