An official website of the United States government
We explore Zero-Knowledge Proofs (ZKPs) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness of ZK CPUs with a large number of instructions of varying sizes. We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state of the art, where cost scales with the size of the largest CPU instruction (largest CFG node). Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK. We implemented an interactive tight arithmetic (over F261−1) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a 5-18× improvement when instructions are of varied size. Our VOLE-based tight ZK CPU (over F261−1) can execute 100K (resp. 450K) multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ 102 Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory, may be of independent interest.
more »
« less
Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
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 $$\mathcal{L}_1 \lor \cdots \lor \mathcal{L}_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, $$\mathsf{Batchman}$$, 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, $$\mathsf{Robin}$$, which is (only) communication efficient. For small fields and for statistical security parameter $$\lambda$$, this protocol's communication improves over the previous state of the art ($$\mathsf{Mac'n'Cheese}$$, Baum et al., CRYPTO'21) by up to factor $$\lambda$$. Our implementation outperforms prior state of the art. E.g., we achieve up to $$6\times$$ improvement over $$\mathsf{Mac'n'Cheese}$$ (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over $$\mathsf{QuickSilver}$$ (Yang et al., CCS'21) by up to $$70\times$$ and over $$\mathsf{AntMan}$$ (Weng et al., CCS'22) by up to $$36\times$$.
more »
« less
- PAR ID:
- 10466236
- Editor(s):
- Cas Cremers and Engin Kirda
- Date Published:
- Journal Name:
- ACM CCS 2023
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, P and V agree on B fan-in 2 circuits C0, . . . , CB−1 over a field F; each circuit has n_in inputs, n_× multiplications, and one output. P’s goal is to demonstrate the knowledge of a witness (id ∈ [B], w ∈ F^n_in ), s.t. Cid (w) = 0 where neither w nor id is revealed. Disjunctive statements are effective, for example, in implementing ZKP based on sequential execution of CPU steps. This paper studies ZKP (of knowledge) protocols over disjunctive statements based on Vector OLE. Denoting by λ the statistical security parameter and let ρ \in^\Delta max{log |F|, λ}, the previous state-of-the-art protocol Robin (Yang et al. CCS’23) required (n_in +3n_×) log |F|+O(ρB) bits of communication with O(1) rounds, and Mac'n'Cheese (Baum et al. CRYPTO’21) required (n_in +n_×) log |F|+2n×ρ+O(ρ logB) bits of communication with O(logB) rounds, both in the VOLE-hybrid model. Our novel protocol LogRobin++ achieves the same functionality at the cost of (n_in+n_×) log |F|+O(ρ logB) bits of communication with O(1) rounds in the VOLE-hybrid model. Crucially, LogRobin++ takes advantage of two new techniques – (1) an O(logB)-overhead approach to prove in ZK that an IT-MAC commitment vector contains a zero; and (2) the realization of VOLE-based ZK over a disjunctive statement, where P commits only to w and multiplication outputs of Cid (w) (as opposed to prior work where P commits to w and all three wires that are associated with each multiplication gate). We implemented LogRobin++ over Boolean (i.e., F2) and arithmetic (i.e., F_2^61−1) fields. In our experiments, including the cost of generating VOLE correlations, LogRobin++ achieved up to 170× optimization over Robin in communication, resulting in up to 7× (resp. 3×) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.more » « less
-
The fundamental problems of sorting and searching, traditionally studied in the unit-cost comparison model, have been generalized to include priced information, where different pairs of items have different comparison costs. These costs can be arbitrary (Charikar et al. STOC 2000), structured (Gupta et al. FOCS 2001), or stochastic (Angelov et al. LATIN 2008). Motivated by the database setting where the comparison cost depends on the sizes of the records, we consider the problems of sorting and batched predecessor where two non-uniform sets of items A and B are given as input. In the RAM model, pairwise comparisons (A-A, A-B and B-B) have respective comparison costs a, b and c. We give upper and lower bounds for the case a<= b <= c, which serves as a warmup for the generalization to the external-memory model. In the Disk-Access Model (DAM), where transferring elements between disk and RAM is the main bottleneck, we consider the scenario where elements in B are larger than elements in A. All items are required in their entirety for comparisons in RAM. A key observation is that the complexity of sorting depends on the interleaving of the small and large items in the final sorted order, and with a high degree of interleaving, the lower bound is dominated by an associated batched predecessor problem. We give output-sensitive bounds on the batched predecessor and sorting; our bounds are tight in most cases. Our lower bounds require novel generalizations of lower bound techniques in external memory to accommodate non-uniform keys.more » « less
-
In the unit-cost comparison model, a black box takes an input two items and outputs the result of the comparison. Problems like sorting and searching have been studied in this model, and it has been general- ized to include the concept of priced information, where different pairs of items (say database records) have different comparison costs. These comparison costs can be arbitrary (in which case no algorithm can be close to optimal (Charikar et al. STOC 2000)), structured (for exam- ple, the comparison cost may depend on the length of the databases (Gupta et al. FOCS 2001)), or stochastic (Angelov et al. LATIN 2008). Motivated by the database setting where the cost depends on the sizes of the items, we consider the problems of sorting and batched predecessor where two non-uniform sets of items A and B are given as input. (1) In the RAM setting, we consider the scenario where both sets have n keys each. The cost to compare two items in A is a, to compare an item of A to an item of B is b, and to compare two items in B is c. We give upper and lower bounds for the case a ≤ b ≤ c, the case that serves as a warmup for the generalization to the external-memory model. Notice that the case b = 1,a = c = ∞ is the famous “nuts and bolts” problem. ) In the Disk-Access Model (DAM), where transferring elements between disk and internal memory is the main bottleneck, we con- sider the scenario where elements in B are larger than elements in A. The larger items take more I/Os to be brought into memory, consume more space in internal memory, and are required in their entirety for comparisons. A key observation is that the complexity of sorting depends heavily on the interleaving of the small and large items in the final sorted order. If all large elements come after all small elements in the final sorted order, sorting each type separately and concatenating is optimal. However, if the set of predecessors of B in A has size k ≪ n, one must solve an associated batched predecessor problem in order to achieve optimality. We first give output-sensitive lower and upper bounds on the batched predecessor problem, and use these to derive bounds on the complexity of sorting in the two models. Our bounds are tight in most cases, and require novel generalizations of the classical lower bound techniques in external memory to accommodate the non-uniformity of keys.more » « less
-
A bstract We present the first measurement of the branching fraction of the singly Cabibbo-suppressed (SCS) decay $$ {\Lambda}_c^{+} $$ Λ c + → pη ′ with η ′ → ηπ + π − , using a data sample corresponding to an integrated luminosity of 981 fb − 1 , collected by the Belle detector at the KEKB e + e − asymmetric-energy collider. A significant $$ {\Lambda}_c^{+} $$ Λ c + → pη ′ signal is observed for the first time with a signal significance of 5.4 σ . The relative branching fraction with respect to the normalization mode $$ {\Lambda}_c^{+} $$ Λ c + → pK − π + is measured to be $$ \frac{\mathcal{B}\left({\Lambda}_c^{+}\to p\eta^{\prime}\right)}{\mathcal{B}\left({\Lambda}_c^{+}\to {pK}^{-}{\pi}^{+}\right)}=\left(7.54\pm 1.32\pm 0.73\right)\times {10}^{-3}, $$ B Λ c + → pη ′ B Λ c + → pK − π + = 7.54 ± 1.32 ± 0.73 × 10 − 3 , where the uncertainties are statistical and systematic, respectively. Using the world-average value of $$ \mathcal{B}\left({\Lambda}_c^{+}\to {pK}^{-}{\pi}^{+}\right) $$ B Λ c + → pK − π + = (6 . 28 ± 0 . 32) × 10 − 2 , we obtain $$ \mathcal{B}\left({\Lambda}_c^{+}\to p\eta^{\prime}\right)=\left(4.73\pm 0.82\pm 0.46\pm 0.24\right)\times {10}^{-4}, $$ B Λ c + → pη ′ = 4.73 ± 0.82 ± 0.46 ± 0.24 × 10 − 4 , where the uncertainties are statistical, systematic, and from $$ \mathcal{B}\left({\Lambda}_c^{+}\to {pK}^{-}{\pi}^{+}\right) $$ B Λ c + → pK − π + , respectively.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
