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.
Category / Keywords: cryptographic protocols / zero-knowledge proofs Date: received 17 Nov 2020, last revised 10 Dec 2020 Contact author: samuel dittmer at gmail com,rafail ostrovsky@gmail com,yuval ishai@gmail com Available format(s): PDF | BibTeX Citation Version: 20201210:185611 (All versions of this report) Short URL: ia.cr/2020/1446