Zero Knowledge Protocols from Succinct Constraint Detection
We study the problem of constructing proof systems that achieve both soundness and zero knowledge unconditionally (without relying on intractability assumptions). Known techniques for this goal are primarily combinatorial, despite the fact that constructi
- PDF / 529,444 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 222 Views
3
Technion, Haifa, Israel {eli,mriabzev}@cs.technion.ac.il 2 UC Berkeley, Berkeley, USA [email protected], [email protected] University of Illinois Urbana-Champaign, Champaign, USA [email protected] 4 ZcashCo, Haifa, Israel [email protected]
Abstract. We study the problem of constructing proof systems that achieve both soundness and zero knowledge unconditionally (without relying on intractability assumptions). Known techniques for this goal are primarily combinatorial, despite the fact that constructions of interactive proofs (IPs) and probabilistically checkable proofs (PCPs) heavily rely on algebraic techniques to achieve their properties. We present simple and natural modifications of well-known ‘algebraic’ IP and PCP protocols that achieve unconditional (perfect) zero knowledge in recently introduced models, overcoming limitations of known techniques. – We modify the PCP of Ben-Sasson and Sudan [BS08] to obtain zero knowledge for NEXP in the model of Interactive Oracle Proofs [BCS16, RRR16], where the verifier, in each round, receives a PCP from the prover. – We modify the IP of Lund et al. [LFKN92] to obtain zero knowledge for #P in the model of Interactive PCPs [KR08], where the verifier first receives a PCP from the prover and then interacts with him. The simulators in our zero knowledge protocols rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: – An algorithm to detect constraints for Reed–Muller codes of exponential length. This algorithm exploits the Raz–Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. M.A. Forbes—Work conducted while at Stanford. A. Gabizon—Work conducted while at Technion. N. Spooner—Work conducted while at the University of Toronto. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 172–206, 2017. https://doi.org/10.1007/978-3-319-70503-3_6
Zero Knowledge Protocols from Succinct Constraint Detection
173
– An algorithm to de tect constraints for PCPs of Proximity of Reed– Solomon codes [BS08] of exponential degree. This algorithm exploits the recursive structure of the PCPs of Proximity to show that smallsupport constraints are “locally” spanned by a small number of small-support constraints. Keywords: Probabilistically checkable proofs · Interactive proofs Sumcheck · Zero knowledge · Polynomial identity testing
1
·
Introduction
The study of interactive proofs (IPs) [BM88,GMR89] that unconditionally achieve zero knowledge [GMR89] has led to a rich theory, with connections well beyond zero knowledge. For example, the class of languages with statistical zero k
Data Loading...
