Batchman and Robin: Batched and Non-batched Branching for Interactive ZK

No ratings

Presented at ACM CCS 2023 by

Carmit Hazay

Muthuramakrishnan Venkitasubramaniam

Vladimir Kolesnikov

Yibin Yang

David Heath

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. Our main result, \mathsfBatchman , is asymptotically and concretely efficient VOLE-based ZK for batched disjunctions, i.e. statements containing R repetitions of the same disjunction. This is crucial for, e.g., emulating CPU steps in ZK. Our prover and verifier complexity is only \bigO(RB+R|\C|+B|\C|), where |\C| is the maximum circuit size of the B branches. Prior works' computation scales in RB|\C|. For non-batched disjunctions, we also construct a VOLE-based ZK protocol, \mathsfRobin , which is (only) communication efficient. For small fields and for statistical security parameter łambda, this protocol's communication improves over the previous state of the art (\mathsfMac'n'Cheese , Baum et al., CRYPTO'21) by up to factor łambda. Our implementation outperforms prior state of the art. E.g., we achieve up to 6× improvement over \mathsfMac'n'Cheese (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over \mathsfQuickSilver (Yang et al., CCS'21) by up to 70× and over \mathsfAntMan (Weng et al., CCS'22) by up to 36×.