Proving as fast as computing: succinct arguments with constant prover overhead
Noga Ron‐Zewi, Ron D. Rothblum
Abstract
Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language L ∈ NP, with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness.
Topics & Concepts
Gas meter proverCorrectnessBottleneckComputer scienceAutomated theorem provingConstant (computer programming)Key (lock)Programming languageProof assistantTheoretical computer scienceOverhead (engineering)Discrete mathematicsAlgorithmMathematicsMathematical proofComputer securityEmbedded systemGeometryCryptography and Data SecurityComplexity and Algorithms in GraphsPrivacy-Preserving Technologies in Data