Paper 2020/1446
LinePoint Zero Knowledge and Its Applications
Samuel Dittmer, Yuval Ishai, and Rafail Ostrovsky
Abstract
We introduce and study a simple kind of proof system called linepoint 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 designatedverifier NIZK protocols. We construct LPZK systems for proving satisfiability of arithmetic circuits with attractive efficiency features. These give rise to designatedverifier NIZK protocols that require only 25 times the computation of evaluating the circuit in the clear (following an inputindependent 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 noninteractive 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 zeroknowledge proofs
 Contact author(s)

samuel dittmer @ gmail com
rafail ostrovsky @ gmail com
yuval ishai @ gmail com  History
 20210614: last of 2 revisions
 20201119: received
 See all versions
 Short URL
 https://ia.cr/2020/1446
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1446, author = {Samuel Dittmer and Yuval Ishai and Rafail Ostrovsky}, title = {LinePoint Zero Knowledge and Its Applications}, howpublished = {Cryptology ePrint Archive, Paper 2020/1446}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1446}}, url = {https://eprint.iacr.org/2020/1446} }