License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.5
URN: urn:nbn:de:0030-drops-143249
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14324/
Go to the corresponding LIPIcs Volume Portal

Dittmer, Samuel ; Ishai, Yuval ; Ostrovsky, Rafail

Line-Point Zero Knowledge and Its Applications

pdf-format:
LIPIcs-ITC-2021-5.pdf (0.8 MB)

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 ?(t) : = at + ? in a vector space ?ⁿ, and the verifier queries the line at a single random point t = α. 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₂-norm.

BibTeX - Entry

@InProceedings{dittmer_et_al:LIPIcs.ITC.2021.5,
  author =	{Dittmer, Samuel and Ishai, Yuval and Ostrovsky, Rafail},
  title =	{{Line-Point Zero Knowledge and Its Applications}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14324},
  URN =		{urn:nbn:de:0030-drops-143249},
  doi =		{10.4230/LIPIcs.ITC.2021.5},
  annote =	{Keywords: Zero-knowledge proofs, NIZK, correlated randomness, vector oblivious linear evaluation, non-interactive secure computation}
}

Keywords: Zero-knowledge proofs, NIZK, correlated randomness, vector oblivious linear evaluation, non-interactive secure computation
Collection: 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Issue Date: 2021
Date of publication: 19.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI