Paper 2022/552

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

Samuel Dittmer, Yuval Ishai, Steve Lu, and Rafail Ostrovsky


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
zero-knowledge proofslinear interactive proofsvector oblivious linear evaluation
Contact author(s)
samuel dittmer @ gmail com
yuval ishai @ gmail com
steve @ stealthsoftwareinc com
rafail @ cs ucla edu
2022-05-10: received
Short URL
Creative Commons Attribution


      author = {Samuel Dittmer and Yuval Ishai and Steve Lu and Rafail Ostrovsky},
      title = {Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One},
      howpublished = {Cryptology ePrint Archive, Paper 2022/552},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.