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

David Heath, Vladimir Kolesnikov, Jiahui Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 Z2k 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 arithmetic 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 number using 3200 × smaller proof size than standard KKW (100 × improvement from our dot product construction and 32 × 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.

Original languageEnglish (US)
Title of host publicationCyber Security Cryptography and Machine Learning - 5th International Symposium, CSCML 2021, Proceedings
EditorsShlomi Dolev, Oded Margalit, Benny Pinkas, Alexander Schwarzmann
PublisherSpringer
Pages414-431
Number of pages18
ISBN (Print)9783030780852
DOIs
StatePublished - 2021
Externally publishedYes
Event5th International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2021 - Be'er Sheva, Israel
Duration: Jul 8 2021Jul 9 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12716 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2021
Country/TerritoryIsrael
CityBe'er Sheva
Period7/8/217/9/21

Keywords

  • MPC-in-the-Head
  • Zero knowledge

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Efficient Generic Arithmetic for KKW: Practical Linear MPC-in-the-Head NIZK on Commodity Hardware Without Trusted Setup'. Together they form a unique fingerprint.

Cite this