MozZ2karella: Efficient Vector-OLE and Zero-Knowledge Proofs over Z2k

TY - GEN

T1 - MozZ2karella

T2 - 42nd Annual International Cryptology Conference, CRYPTO 2022

AU - Baum, Carsten

AU - Braun, Lennart

AU - Munch-Hansen, Alexander

AU - Scholl, Peter

PY - 2022/10

Y1 - 2022/10

N2 - Zero-knowledge proof systems are usually designed to support computations for circuits over $\mathbb{F}_2$ or $\mathbb{F}_p$ for large $p$, but not for computations over $\mathbb{Z}_{2^k}$, which all modern CPUs operate on. Although $\mathbb{Z}_{2^k}$-arithmetic can be emulated using prime moduli, this comes with an unavoidable overhead. Recently, Baum et al.\ (CCS 2021) suggested a candidate construction for a designated-verifier zero-knowledge proof system that natively runs over $\mathbb{Z}_{2^k}$. Unfortunately, their construction requires preprocessed random vector oblivious linear evaluation (VOLE) to be instantiated over $\mathbb{Z}_{2^k}$. Currently, it is not known how to efficiently generate such random VOLE in large quantities. In this work, we present a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over $\mathbb{Z}_{2^k}$ into a much longer, pseudorandom VOLE over the same ring. Our construction borrows ideas from recent protocols over finite fields, which we non-trivially adapt to work over $\mathbb{Z}_{2^k}$. Moreover, we show that the approach taken by the QuickSilver zero-knowledge proof system (Yang et al.\ CCS 2021) can be generalized to support computations over $\mathbb{Z}_{2^k}$. This new VOLE-based proof system, which we call \Quarksilver, yields better efficiency than the previous zero-knowledge protocols suggested by Baum et al. Furthermore, we implement both our VOLE extension and our zero-knowledge proof system, and show that they can generate \numrange[range-phrase=--]{13}{50} million VOLEs per second for \SIrange{64}{256}{\bit} rings, and evaluate \num{1.3}~million \SI{64}{\bit} multiplications per second in zero-knowledge.

AB - Zero-knowledge proof systems are usually designed to support computations for circuits over $\mathbb{F}_2$ or $\mathbb{F}_p$ for large $p$, but not for computations over $\mathbb{Z}_{2^k}$, which all modern CPUs operate on. Although $\mathbb{Z}_{2^k}$-arithmetic can be emulated using prime moduli, this comes with an unavoidable overhead. Recently, Baum et al.\ (CCS 2021) suggested a candidate construction for a designated-verifier zero-knowledge proof system that natively runs over $\mathbb{Z}_{2^k}$. Unfortunately, their construction requires preprocessed random vector oblivious linear evaluation (VOLE) to be instantiated over $\mathbb{Z}_{2^k}$. Currently, it is not known how to efficiently generate such random VOLE in large quantities. In this work, we present a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over $\mathbb{Z}_{2^k}$ into a much longer, pseudorandom VOLE over the same ring. Our construction borrows ideas from recent protocols over finite fields, which we non-trivially adapt to work over $\mathbb{Z}_{2^k}$. Moreover, we show that the approach taken by the QuickSilver zero-knowledge proof system (Yang et al.\ CCS 2021) can be generalized to support computations over $\mathbb{Z}_{2^k}$. This new VOLE-based proof system, which we call \Quarksilver, yields better efficiency than the previous zero-knowledge protocols suggested by Baum et al. Furthermore, we implement both our VOLE extension and our zero-knowledge proof system, and show that they can generate \numrange[range-phrase=--]{13}{50} million VOLEs per second for \SIrange{64}{256}{\bit} rings, and evaluate \num{1.3}~million \SI{64}{\bit} multiplications per second in zero-knowledge.

KW - zero-knowledge

KW - vector ole

U2 - 10.1007/978-3-031-15985-5_12

DO - 10.1007/978-3-031-15985-5_12

M3 - Article in proceedings

SN - 978-3-031-15984-8

T3 - Lecture Notes in Computer Science

SP - 329

EP - 358

BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings

A2 - Dodis, Yevgeniy

A2 - Shrimpton, Thomas

PB - Springer

Y2 - 15 August 2022 through 18 August 2022

ER -