Paper 2022/819

Moz$\mathbb{Z}_{2^k}$arella: Efficient Vector-OLE and Zero-Knowledge Proofs Over $\mathbb{Z}_{2^k}$

Carsten Baum, Aarhus University
Lennart Braun, Aarhus University
Alexander Munch-Hansen, Aarhus University
Peter Scholl, Aarhus University
Abstract

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 13-50 million VOLEs per second for 64 to 256 bit rings, and evaluate 1.3 million 64 bit multiplications per second in zero-knowledge.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
zero-knowledge vector ole
Contact author(s)
cbaum @ cs au dk
braun @ cs au dk
almun @ cs au dk
peter scholl @ cs au dk
History
2022-06-23: approved
2022-06-22: received
See all versions
Short URL
https://ia.cr/2022/819
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/819,
      author = {Carsten Baum and Lennart Braun and Alexander Munch-Hansen and Peter Scholl},
      title = {Moz$\mathbb{Z}_{2^k}$arella: Efficient Vector-OLE and Zero-Knowledge Proofs Over $\mathbb{Z}_{2^k}$},
      howpublished = {Cryptology ePrint Archive, Paper 2022/819},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/819}},
      url = {https://eprint.iacr.org/2022/819}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.