Paper 2022/819

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

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 F2 or Fp for large p, but not for computations over Z2k, which all modern CPUs operate on. Although -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 . Unfortunately, their construction requires preprocessed random vector oblivious linear evaluation (VOLE) to be instantiated over . 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 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 . 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 . 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.

Note: Added reference to conference version.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
DOI
10.1007/978-3-031-15985-5_12
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-10-21: revised
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},
      doi = {10.1007/978-3-031-15985-5_12},
      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.