Checking computations in polylogarithmic time

By László Babai, Lance Fortnow, L. Levin, Mario Szegedy. 1991

Motivated by Manuel Blum’s concept of inst ante checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof protocols [LFKN], [Sh], and especially the MIP = NEXP protocol from [BFL]. WJe show that every nondeterministic computational task S(Z, y), defined as a polynomial time relation between the instance x, representing the input and output combined, and the witness y can be modified to a task S such that: (i) the same instances remain accepted; (ii) each instance/witness pair becomes checkable in poly!ogariihmic Monte Carlo time; and (iii) a witness satisfying S’ can be computed in polynomial time from a witness satisfying S. Here the instance and the description of S have to be provided in error-correcting code (since the checker will not notice slight changes). A modification of the MIP proof was required to achieve polynomial time in (iii); the earlier technique yields N“(*OglOg’1 time only. This result becomes significant if software and hardware reliability are regarded aa a considerable cost factor. The polylogarithmic checker is the only part of the system that needs to be trusted; it can be hard wired. (We use just one Checker for all problems!) The checker is tiny and so presumably can be optimized and checked off-line at a modest cost. In this setup, a single reliable PC can monitor the operation of a herd of supercomputers working with possibly extremely powerful but unreliable software and untested hardware. 1Research partially supported by NSF Grant CCR-871OO78. Email: laci@cs.uchicago. edu 2Rese~& partiay supported by NSF Grant CCR-SMXI$XEK5. E-mail: fortnow@cs.uc&cago. edu 3Supported by NSF grant CCR-SJC115276. E-mail: Lnd@cs.bu.edu 4111 cummington St., Boston MA 02215. 5E-mail: mario@cs.uchicago .edu ~1100 E 58th St, Chicago IL 60637. Permission to copy without fee all or part of this msterisl is granted provided that tie copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee snd/or specific permission. @ 1991 ACM 089791-397-31911000410021 $1.50 Leonid A. Levin 3

How researchers see this paper

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

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[40] and has been studied under various terms in the literature: checking computations [40], certified computation [295], delegating computations [185], as well as verifiable computing [173].”
Private information retrieval (1995, unknown): “In this section we describe an information retrieval scheme which requires communication bits for databases, where is a constant, and bits where . The scheme is based on the method of low-degree polynomial interpolation, originating from [6] and extensively used thereafter (see for example [15, 3, ”
The Fastest and Shortest Algorithm for all Well-Defined Problems (2000, background): “ted to subclasses of problems. A more fascinating Marcus Hutter, The Fastest and Shortest Algorithm 11 (and more speculative) way may be the utilization of so called transparent or holographic proofs [1]. Under certain circumstances they allow an exponential speed up for checking proofs. This would ”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, methodology): “The celebrated result IP=PSPACE [35, 41] used arithmetization as a crucial tool and set the stage for the PCP theorem [2–4, 20], which provided a new characterization of NP that revolutionized the notion of “proof” – in particular, it shows that NP statements have probabilistically checkable proofs ”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “A ZK system based on the PCP Theorem (ZK-PCP) [74, 85, 49, 75, 71] has three additional advantages that are essential for ongoing public trust in computational integrity.”
Verifying computations without reexecuting them (2015, unknown): “1 Indeed, although the modern signiﬁcance of PCPs lies elsewhere, an original motivation was verifying the correctness of remotely executed computations: the paper quoted in our epigraph [4] was one of the seminal works that led to the PCP theorem.”
SIA: Secure information aggregation in sensor networks (2003, methodology): “If we are willing to accept (a small) non-zero probability of error, then theo retically general methods based on PCP techniques could be applied [2, 25].”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “[8, 9], offers a low-degree polynomial G(·) that fits the structure of the sum-check protocol.”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “Probabilistically checkable proof (PCP) systems(8) [4, 3, 2, 1] are a particularly efficient multi-prover interactive proof (MIP) system [8] in terms of the amount of communication between prover and verifier, verification time, the number of rounds of interaction and soundness-error.”
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “Interactive Oracle Proofs (IOP) [24, 79] is a type of proof system that combines the aspects of Interactive Proofs (IP) [6, 52] along with Probabilistic Checkable Proofs (PCP) [3, 5, 26] as well generalizes Interactive PCPs (IPCP) [71].”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “Compared to most protocols to outsource computations, known zk-SNARKs use “heavyweight” techniques, such as probabilistically-checkable proofs [6] and expensive pairing-based cryptography.”