Paper 2020/1319

On Succinct Arguments and Witness Encryption from Groups

Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu

Abstract

Succinct non-interactive arguments (SNARGs) enable proofs of NP statements with very low communication. Recently, there has been significant work in both theory and practice on constructing SNARGs with very short proofs. Currently, the state-of-the-art in succinctness is due to Groth (Eurocrypt 2016) who constructed a SNARG from bilinear maps where the proof consists of just 3 group elements. In this work, we first construct a concretely-efficient designated-verifier (preprocessing) SNARG with inverse polynomial soundness, where the proof consists of just 2 group elements in a standard (generic) group. This leads to a 50% reduction in concrete proof size compared to Groth's construction. We follow the approach of Bitansky et al. (TCC 2013) who describe a compiler from linear PCPs to SNARGs in the preprocessing model. Our improvement is based on a new linear PCP packing technique that allows us to construct 1-query linear PCPs which can then be compiled into a SNARG (using ElGamal encryption over a generic group). An appealing feature of our new SNARG is that the verifier can precompute a statement-independent lookup table in an offline phase; verifying proofs then only requires 2 exponentiations and a single table lookup. This makes our new designated-verifier SNARG appealing in settings that demand fast verification and minimal communication. We then turn to the question of constructing arguments where the proof consists of a single group element. Here, we first show that any (possibly interactive) argument for a language L where the verification algorithm is "generic" (i.e., only performs generic group operations) and the proof consists of a single group element, implies a witness encryption scheme for L. We then show that under a yet-unproven, but highly plausible, hypothesis on the hardness of approximating the minimal distance of linear codes, we can construct a 2-message laconic argument for NP where the proof consists of a single group element. Under the same hypothesis, we obtain a witness encryption scheme for NP in the generic group model. Along the way, we show that under a conceptually-similar but proven hardness of approximation result, there is a 2-message laconic argument for NP with negligible soundness error where the prover's message consists of just 2 group elements. In both settings, we obtain laconic arguments (and linear PCPs) with linear decision procedures. Our constructions circumvent a previous lower bound by Groth on such argument systems with linear decision procedures by relying on imperfect completeness. Namely, our constructions have vanishing but not negligible completeness error, while the lower bound of Groth implicitly assumes negligible completeness error of the underlying argument. Our techniques thus highlight new avenues for designing linear PCPs, succinct arguments, and witness encryption schemes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2020
DOI
10.1007/978-3-030-56784-2_26
Keywords
succinct argumentsSNARKswitness encryption
Contact author(s)
ohadba @ cs technion ac il
yuvali @ cs technion ac il
rafail @ cs ucla edu
dwu4 @ virginia edu
History
2021-02-04: revised
2020-10-23: received
See all versions
Short URL
https://ia.cr/2020/1319
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1319,
      author = {Ohad Barta and Yuval Ishai and Rafail Ostrovsky and David J.  Wu},
      title = {On Succinct Arguments and Witness Encryption from Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1319},
      year = {2020},
      doi = {10.1007/978-3-030-56784-2_26},
      url = {https://eprint.iacr.org/2020/1319}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.