Paper 2020/1446

Line-Point Zero Knowledge and Its Applications

Samuel Dittmer, Yuval Ishai, and Rafail Ostrovsky


We introduce and study a simple kind of proof system called line-point zero knowledge (LPZK). In an LPZK proof, the prover encodes the witness as an affine line $\mathbf{v}(t) := \mathbf{a}t + \mathbf{b}$ in a vector space $\mathbb{F}^n$, and the verifier queries the line at a single random point $t=\alpha$. LPZK is motivated by recent practical protocols for vector oblivious linear evaluation (VOLE), which can be used to compile LPZK proof systems into lightweight designated-verifier NIZK protocols. We construct LPZK systems for proving satisfiability of arithmetic circuits with attractive efficiency features. These give rise to designated-verifier NIZK protocols that require only 2-5 times the computation of evaluating the circuit in the clear (following an input-independent preprocessing phase), and where the prover communicates roughly 2 field elements per multiplication gate, or roughly 1 element in the random oracle model with a modestly higher computation cost. On the theoretical side, our LPZK systems give rise to the first linear interactive proofs (Bitansky et al., TCC 2013) that are zero knowledge against a malicious verifier. We then apply LPZK towards simplifying and improving recent constructions of reusable non-interactive secure computation (NISC) from VOLE (Chase et al., Crypto 2019). As an application, we give concretely efficient and reusable NISC protocols over VOLE for bounded inner product, where the sender's input vector should have a bounded $L_2$-norm.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
zero-knowledge proofs
Contact author(s)
samuel dittmer @ gmail com
rafail ostrovsky @ gmail com
yuval ishai @ gmail com
2021-06-14: last of 2 revisions
2020-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Samuel Dittmer and Yuval Ishai and Rafail Ostrovsky},
      title = {Line-Point Zero Knowledge and Its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1446},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.