Abstract
Zero-knowledge (ZK) proofs have recently attracted much attention. Typically, these are defined with respect to statements that are fomulated as circuits over a fixed finite field F2 or Fp for a large prime p and they are evaluated gate-by-gate. This causes the running time of these protocols to scale linearly with the number of gates. A third domain they can be defined over is the ring Z2^k. These fit what CPUs operate on, thus allows for easier porting of programs to ZK protocols, but little research has been done in ZK over this domain.
This thesis pushes forward the study of circuit-based ZK protocols in two major ways; by providing gadgets that lower the overall gate-count and by building new efficient protocols for circuits defined over the ring Z2^k. In addition to this, this thesis also provides a new result in the random-access-memory (RAM) model where we provide a novel ZK proof system. The RAM model allows a prover to evaluate a function represented as a RAM program while revealing no information of the private input. This uses a different computational model (random-access-machines) compared to circuits. Certain programs run much faster in this model versus when represented as a circuit.
Our first contribution presents a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over
Z2^k into a much longer, pseudorandom VOLE over the same ring. We use these to build additively homomorphic commitments over Z2^k.
Moreover, we show that the approach taken by the QuickSilver ZK proof system (CCS 2021) can be generalized to support computations over Z2^k. This new VOLE-based proof system, which we call Quarksilver, yields better efficiency than
previous ZK protocols over Z2^k, at 1.3 million 64bit multiplications per
second in zero-knowledge.
Our second contribution is twofold; two efficient ZK protocols over Z2^k based on VOLE and a new efficient check of consistency between secret values from the domains of Fp or Z2^k and F2. This allows the prover and verifier to swap domains of the circuit based on which operations are performed, thus avoiding computing functions in an inefficient domain.
Our third contribution is three new protocols for efficiently evaluating range proofs. These are specialized gadgets for proving that the prover knows some x such that a≤x≤b for some public pair (a, b). Each of the provided protocols is efficient in its own right. These are based on either square decomposition or n-ary decomposition, making them better at handling larger or smaller values as well as larger or smaller batches of range proofs.
Our final contribution is a novel ZK proof system for RAM programs compatible with VOLE-based ZK systems such as Quicksilver and Mac'n'Cheese (CRYPTO 2021) that (1) supports arbitrary fields and (2) has linear overhead in both the word size and circuit complexity. This new ZK proof system achieves similar asymptotics are other works, but this approach requires significantly less computation and communication in settings where the number of RAM operations is larger than the RAM.
This thesis pushes forward the study of circuit-based ZK protocols in two major ways; by providing gadgets that lower the overall gate-count and by building new efficient protocols for circuits defined over the ring Z2^k. In addition to this, this thesis also provides a new result in the random-access-memory (RAM) model where we provide a novel ZK proof system. The RAM model allows a prover to evaluate a function represented as a RAM program while revealing no information of the private input. This uses a different computational model (random-access-machines) compared to circuits. Certain programs run much faster in this model versus when represented as a circuit.
Our first contribution presents a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over
Z2^k into a much longer, pseudorandom VOLE over the same ring. We use these to build additively homomorphic commitments over Z2^k.
Moreover, we show that the approach taken by the QuickSilver ZK proof system (CCS 2021) can be generalized to support computations over Z2^k. This new VOLE-based proof system, which we call Quarksilver, yields better efficiency than
previous ZK protocols over Z2^k, at 1.3 million 64bit multiplications per
second in zero-knowledge.
Our second contribution is twofold; two efficient ZK protocols over Z2^k based on VOLE and a new efficient check of consistency between secret values from the domains of Fp or Z2^k and F2. This allows the prover and verifier to swap domains of the circuit based on which operations are performed, thus avoiding computing functions in an inefficient domain.
Our third contribution is three new protocols for efficiently evaluating range proofs. These are specialized gadgets for proving that the prover knows some x such that a≤x≤b for some public pair (a, b). Each of the provided protocols is efficient in its own right. These are based on either square decomposition or n-ary decomposition, making them better at handling larger or smaller values as well as larger or smaller batches of range proofs.
Our final contribution is a novel ZK proof system for RAM programs compatible with VOLE-based ZK systems such as Quicksilver and Mac'n'Cheese (CRYPTO 2021) that (1) supports arbitrary fields and (2) has linear overhead in both the word size and circuit complexity. This new ZK proof system achieves similar asymptotics are other works, but this approach requires significantly less computation and communication in settings where the number of RAM operations is larger than the RAM.
| Translated title of the contribution | Quattro Formaggi: Zero-Knowledge via VOLE |
|---|---|
| Original language | English |
| Publisher | Århus Universitet |
|---|---|
| Number of pages | 219 |
| Publication status | Published - Nov 2023 |