Cryptology ePrint Archive: Report 2022/552

Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One

Samuel Dittmer and Yuval Ishai and Steve Lu and Rafail Ostrovsky

Abstract: Recent advances in fast protocols for \textit{vector oblivious linear evaluation} (VOLE) have inspired a family of new VOLE-based lightweight designated-verifier NIZK protocols (Weng et al., S\&P 2021, Baum et al., Crypto 2021, Dittmer et al., ITC 2021, Yang et al., CCS 2021). In particular, the Line-Point Zero Knowledge (LPZK) protocol of Dittmer et al.\ has the advantage of being entirely non-cryptographic given a single instance of a random VOLE correlation.

We present improvements to LPZK through the introduction of additional structure to the correlated randomness. Using an efficiently realizable variant of the VOLE correlation, we reduce the online proof size of LPZK by roughly 2x: from roughly 2 field elements per multiplication gate, or 1 element in the random oracle variant, to only 1 or $\tfrac{1}{2}$ elements respectively. In particular, we get the first practical VOLE-based NIZK that breaks the 1-element-per-multiplication barrier.

We implemented an optimized version of our protocol and compared it with other recent VOLE-based NIZK protocols. In the typical case where communication is the bottleneck, we get at least 2x performance improvement over all previous VOLE-based protocols. When prover computation is the bottleneck, we outperform all non-LPZK protocols by at least $2$-$3$x and (our optimized implementation of) LPZK by roughly 30%, obtaining a $2$-$3$x slowdown factor compared to plain circuit evaluation.

Category / Keywords: cryptographic protocols / zero-knowledge proofs, linear interactive proofs, vector oblivious linear evaluation

Date: received 5 May 2022, last revised 5 May 2022

Contact author: samuel dittmer at gmail com, yuval ishai at gmail com, steve at stealthsoftwareinc com, rafail at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20220510:081620 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]