Paper 2020/1319
On Succinct Arguments and Witness Encryption from Groups
Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu
Abstract
Succinct noninteractive 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 stateoftheart 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 concretelyefficient designatedverifier (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 1query 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 statementindependent lookup table in an offline phase; verifying proofs then only requires 2 exponentiations and a single table lookup. This makes our new designatedverifier 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 yetunproven, but highly plausible, hypothesis on the hardness of approximating the minimal distance of linear codes, we can construct a 2message 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 conceptuallysimilar but proven hardness of approximation result, there is a 2message 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)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2020
 DOI
 10.1007/9783030567842_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
 20210204: revised
 20201023: received
 See all versions
 Short URL
 https://ia.cr/2020/1319
 License

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/9783030567842_26}, url = {https://eprint.iacr.org/2020/1319} }