Computationally-sound proofs
The author proposes the concept of a computationally sound proof in the attempt to capture the intuitive idea that a proof should be feasible to find and easy to check. The author argues that a realistic notion of proof involves two agents, a prover and a verifier, and needs to satisfy the following requirements: (1) Efficient Verifiability -- the complexity of verification is poly-logarithmic in the complexity of deciding, (2) Efficient Provability -- the prover's computational complexity is polynomially related to the time needed for deciding, (3) Soundness -- there may be false proofs, but the probability that the verifier is fooled by such a proof is negligibly small, (4) Universality -- any recursively enumerable language should admit a proof system. The paper displays a proof system satisfying the above requirements under the assumption that both the prover and the verifier have access to a random oracle. The paper has a foundational character and it remains to be seen to what extent the interesting ideas presented will gain the acceptance of the scientific community. For the entire collection see [Zbl 0884.00035].
- Correctness, explanation and intention
- Proving computational ability
- scientific article; zbMATH DE number 4164180 (Why is no real title available?)
- scientific article; zbMATH DE number 4092761 (Why is no real title available?)
- Computationally Sound Proofs
- Presenting machine-found proofs
- Automata, Languages and Programming
- Batch arguments for \textsf{NP} and more from standard bilinear group assumptions
- Lower bound on SNARGs in the random oracle model
- Fully succinct batch arguments for \textsf{NP} from indistinguishability obfuscation
- Non-interactive zero-knowledge from non-interactive batch arguments
This page was built for publication: Computationally-sound proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4381418)
