Paper 2022/795

Efficient Generic Arithmetic for KKW Practical Linear: MPC-in-the-Head NIZK on Commodity Hardware without Trusted Setup

David Heath, Georgia Institute of Technology
Vladimir Kolesnikov, Georgia Institute of Technology
Jiahui Lu, Georgia Institute of Technology

Katz et al., CCS 2018 (KKW) is a popular and efficient MPC-in-the-head non-interactive ZKP (NIZK) scheme, which is the technical core of the post-quantum signature scheme Picnic, currently considered for standardization by NIST. The KKW approach simultaneously is concretely efficient, even on commodity hardware, and does not rely on trusted setup. Importantly, the approach scales linearly in the circuit size with low constants with respect to proof generation time, proof verification time, proof size, and RAM consumption. However, KKW works with Boolean circuits only and hence incurs significant cost for circuits that include arithmetic operations. In this work, we extend KKW with a suite of efficient arithmetic operations over arbitrary rings and Boolean conversions. Rings $\mathbb{Z}_{2^k}$ are important for NIZK as they naturally match the basic operations of modern programs and CPUs. In particular, we: * present a suitable ring representation consistent with KKW, * construct efficient conversion operators that translate between arith- metic and Boolean representations, and * demonstrate how to efficiently operate over the arithmetic representation, including a vector dot product of length-n vectors with cost equal to that of a single multiplication. These improvements substantially improve KKW for circuits with arithmetic. As one example, we can multiply 100 × 100 square matrices of 32-bit numbers using a 3200x smaller proof size than standard KKW (100x improvement from our dot product construction and 32x from moving to an arithmetic representation). We discuss in detail proof size and resource consumption and argue the practicality of running large proofs on commodity hardware.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. CSCML 2021
MPC-in-the-head Zero Knowledge
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
jlu355 @ gatech edu
2022-06-20: approved
2022-06-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov and Jiahui Lu},
      title = {Efficient Generic Arithmetic for KKW Practical Linear: MPC-in-the-Head NIZK on Commodity Hardware without Trusted Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2022/795},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.