Cryptology ePrint Archive: Report 2020/1446

Line-Point Zero Knowledge and Its Applications

Samuel Dittmer and Yuval Ishai and Rafail Ostrovsky

Abstract: We introduce and study a simple kind of proof systems 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 {\em 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-3 times the computation of evaluating the circuit in the clear (following a ``silent'' 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.

Category / Keywords: cryptographic protocols / zero-knowledge proofs

Date: received 17 Nov 2020

Contact author: samuel dittmer at gmail com,rafail ostrovsky@gmail com,yuval ishai@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201119:094005 (All versions of this report)

Short URL: ia.cr/2020/1446