Paper 2022/819
Moz$\mathbb{Z}_{2^k}$arella: Efficient VectorOLE and ZeroKnowledge Proofs Over $\mathbb{Z}_{2^k}$
Abstract
Zeroknowledge 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 designatedverifier zeroknowledge 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 seedVOLE 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 nontrivially adapt to work over $\mathbb{Z}_{2^k}$. Moreover, we show that the approach taken by the QuickSilver zeroknowledge proof system (Yang et al. CCS 2021) can be generalized to support computations over $\mathbb{Z}_{2^k}$. This new VOLEbased proof system, which we call QuarkSilver, yields better efficiency than the previous zeroknowledge protocols suggested by Baum et al. Furthermore, we implement both our VOLE extension and our zeroknowledge proof system, and show that they can generate 1350 million VOLEs per second for 64 to 256 bit rings, and evaluate 1.3 million 64 bit multiplications per second in zeroknowledge.
Note: Added reference to conference version.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2022
 DOI
 10.1007/9783031159855_12
 Keywords
 zeroknowledge vector ole
 Contact author(s)

cbaum @ cs au dk
braun @ cs au dk
almun @ cs au dk
peter scholl @ cs au dk  History
 20221021: revised
 20220622: received
 See all versions
 Short URL
 https://ia.cr/2022/819
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/819, author = {Carsten Baum and Lennart Braun and Alexander MunchHansen and Peter Scholl}, title = {Moz$\mathbb{Z}_{2^k}$arella: Efficient Vector{OLE} and ZeroKnowledge Proofs Over $\mathbb{Z}_{2^k}$}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/819}, year = {2022}, doi = {10.1007/9783031159855_12}, url = {https://eprint.iacr.org/2022/819} }