Efficient Arguments without Short PCPs

By Yuval Ishai, Eyal Kushilevitz, Rafail M. Ostrovsky. 2007

137 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, background): “Setty et al. produced a second line of PCP-based systems called Pepper [27] and Ginger [28].”
Verifying computations with state (2013, neutral): “To briefly compare the performance of Zaatar and Pinocchio, Pinocchio has superior amortization behavior (see above) but higher proving and setup costs (and hence higher cross-over points), by constant factors.”
Resolving the conflict between generality and plausibility in verified computation (2013, methodology): “Although there are many protocols for general-purpose verified computation in the literature [26, 30, 31, 33, 34] and have been for a long time [8], the theory, if implemented naively, is preposterously expensive: hundreds of trillions of CPU-years or more to verify simple computations [52].”
Full Accounting for Verifiable Outsourcing (2017, background): “In probabilistic proofs—Interactive Proofs (IPs) [12, 49, 50, 58, 76], arguments [30, 52, 54, 62], SNARGs [48], SNARKs [26, 47], and PCPs [9, 10]—a prover efficiently convinces a verifier of a claim, in such a way that the verifier is highly likely to reject a false claim.”
Verifying computations without reexecuting them (2015, methodology): “Later, Ishai et al. [29] (IKO) gave a drastic simpliﬁcation, in which the prover can commit to a proof without materializing the whole thing.”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “[46] constructed a batching argument for NP, where, to simultaneously verify that N circuits of size S are satisfiable, the verifier runs in time max{S2,N}.”
Verifiable Computation with Massively Parallel Interactive Proofs (2012, methodology): “This observation applies not just to the GKR protocol, but to any protocol that uses a circuit representation of the computation (which is a standard technique in the theory literature [13, 18]).”
A Hybrid Architecture for Interactive Verifiable Computation (2013, background): “Experimental results indicate that our system performs better and applies more widely than the best in the literature.”
Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “[69] (for the “designated verifier” case) and Groth [60] (for the “publicly verifiable” case), uses an efficient information-theoretic model called a “linear PCP” that is then “compiled” into a cryptographic system using hPKC.”
Practical verified computation with streaming interactive proofs (2011, background): “In parallel to this work, Setty et al. [31, 32] survey results on probabilistically checkable proofs (PCPs), and implement a construction originally due to Ishai et al. [21].”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Buffet allows the programmer to express programs in an expansive subset of C (disallowing only “goto” and function pointers), can handle essentially any example in the verifiable computation literature, and achieves the best performance in the area by multiple orders of magnitude.”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, methodology): “In the linear PCP model [25,60], the proof is a vector π ∈ F, for some finite field F, and the verifier can can only make a small number of “linear queries” to the proof.”