Welcome to the resource topic for 2020/1446
Title:
Line-Point Zero Knowledge and Its Applications
Authors: Samuel Dittmer, Yuval Ishai, Rafail Ostrovsky
Abstract: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.
ePrint: https://eprint.iacr.org/2020/1446
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .