Interactive proofs and quantified soundness
Research context
postgraduate concept · established · As of 2026-10-10
An interactive proof lets a polynomial-time randomized verifier exchange messages with a computationally unbounded prover.
Key knowledge
An interactive proof lets a polynomial-time randomized verifier exchange messages with a computationally unbounded prover. Completeness gives a successful honest prover on yes-instances; soundness bounds acceptance for every cheating prover on no-instances. Repetition/amplification must preserve the protocol model. An argument instead bounds only computationally restricted cheating provers, so its hardness assumptions and resource bounds must be declared.
Conditions and scope
- State language/promise, number and length of messages, verifier randomness and completeness/soundness probabilities.
- A tested honest transcript does not establish the universal cheating-prover soundness condition.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: IP definition, graph non-isomorphism and verifier randomness; Encryption games chapters 2–3/9/12, authentication chapters 6–8, signatures chapter 13, reductions and identification/zero knowledge chapters 18–20. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-interactive-proof-completeness
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference