Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
复制标题
DOI：
10.1145/3576915.3623169
复制
发表时间：
2023-11
期刊：
影响因子：
--
通讯作者：
Yibin Yang;David Heath;Carmit Hazay;V. Kolesnikov;Muthuramakrishnan Venkitasubramaniam
中科院分区：
文献类型：
--
作者：
Yibin Yang;David Heath;Carmit Hazay;V. Kolesnikov;Muthuramakrishnan Venkitasubramaniam
向量不经意线性求值（VOLE）支持快速和可扩展的交互式零知识（ZK）证明。尽管最近对基于VOLE的ZK进行了改进，但将证明语句编译为控制流不经意的形式（例如，电路）继续导致昂贵的证明。这种低效性突出的一个有用的设置是当语句是子句\mathcalL_1或\cdots或\mathcalL _B的析取时。通常，ZK需要支付处理所有B分支的费用。以前的作品已经展示了如何在通信中避免这种代价，但不是在计算中。我们的主要结果，\mathsfBatchman，是渐近和具体有效的VOLE为基础的ZK分批析取，即语句包含R重复相同的析取。这对于以下方面至关重要：在ZK中模拟CPU步骤。我们的证明器和验证器复杂度仅为\bigO（RB+R|\C| +B|\C|），其中|\C|是B分支的最大电路大小。RB中先前工程的计算比例|\C|.对于非批量析取，我们还构造了一个基于VOLE的ZK协议，\mathsfRobin，这是（唯一）通信有效的。对于小字段和统计安全参数λ，该协议的通信比现有技术的先前状态有所改进（\mathsfMac'n'Cheese，Baum等人，1921年），最高可达因数λ。我们的实现优于现有技术。例如，我们实现了比\mathsfMac'n'Cheese（布尔，单析取）高6倍的改进，并且对于算术批处理析取，我们的实验表明我们比\mathsfQuickSilver（Yang et al.，CCS'21）高达70×和超过\mathsfAntMan（Weng等人，CCS'22）高达36倍。
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×.