Foundations of Cryptography: Volume 1, Basic Tools by Oded Goldreich
Author:Oded Goldreich [Goldreich, Oded]
Language: eng
Format: azw3
Publisher: Cambridge University Press
Published: 2001-08-05T16:00:00+00:00
4.2. Interactive Proof Systems
In this section we introduce the notion of an interactive proof system and present a non-trivial example of such a system (specifically to claims of the form “the following two graphs are not isomorphic”). The presentation is directed toward the introduction of zero-knowledge interactive proofs. Interactive proof systems are interesting for their own sake and have important complexity-theoretic applications.3
4.2.1. Definition
The definition of an interactive proof system refers explicitly to the two computational tasks related to a proof system: “producing” a proof and verifying the validity of a proof. These tasks are performed by two different parties, called the prover and the verifier, which interact with one another. In some cases, the interaction may be very simple and, in particular, unidirectional (i.e., the prover sends a text, called the proof, to the verifier). In general, the interaction may be more complex and may take the form of the verifier interrogating the prover. We start by defining such an interrogation process.
4.2.1.1. Interaction
Interaction between two parties is defined in the natural manner. The only point worth noting is that the interaction is parameterized by a common input (given to both parties). In the context of interactive proof systems, the common input represents the statement to be proved. We first define the notion of an interactive machine and next the notion of interaction between two such machines. The reader may skip to Section 4.2.1.2, which introduces some important conventions (regarding interactive machines), with little loss (if any).
Definition 4.2.1 (An Interactive Machine):
• An interactive Turing machine (ITM) is a (deterministic) multi-tape Turing machine. The tapes are a read-only input tape, a read-only random tape, a read-and-write work tape, a write-only output tape, a pair of communication tapes, and a read-and-write switch tape consisting of a single cell. One communication tape is read-only, and the other is write-only.
• Each ITM is associated a single bit σ ∈ {0, 1}, called its identity. An ITM is said to be active, in a configuration, if the content of its switch tape equals the machine’s identity. Otherwise the machine is said to be idle. While being idle, the state of the machine, the locations of its heads on the various tapes, and the contents of the writable tapes of the ITM are not modified.
• The content of the input tape is called input, the content of the random tape is called random input, and the content of the output tape at termination is called output. The content written on the write-only communication tape during a (time) period in which the machine is active is called the message sent at that period. Likewise, the content read from the read-only communication tape during an active period is called the message received (at that period).
(Without loss of generality, the machine movements on both communication tapes are in only one direction, e.g., from left to right.)
This definition, taken by itself, seems quite non-intuitive. In particular, one may say that once being idle, the machine will never become active again. One
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Coding Theory | Localization |
Logic | Object-Oriented Design |
Performance Optimization | Quality Control |
Reengineering | Robohelp |
Software Development | Software Reuse |
Structured Design | Testing |
Tools | UML |
Deep Learning with Python by François Chollet(11814)
Hello! Python by Anthony Briggs(9344)
OCA Java SE 8 Programmer I Certification Guide by Mala Gupta(9318)
The Mikado Method by Ola Ellnestam Daniel Brolund(9279)
Dependency Injection in .NET by Mark Seemann(8825)
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(7827)
Grails in Action by Glen Smith Peter Ledbrook(7279)
Test-Driven iOS Development with Swift 4 by Dominik Hauser(7240)
The Well-Grounded Java Developer by Benjamin J. Evans Martijn Verburg(7087)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(5929)
Kotlin in Action by Dmitry Jemerov(4613)
Practical Vim (for Kathryn Amaral) by Drew Neil(3714)
Cracking the GRE Premium Edition with 6 Practice Tests, 2015 (Graduate School Test Preparation) by Princeton Review(3576)
Linux Device Driver Development Cookbook by Rodolfo Giometti(3306)
Learn Windows PowerShell in a Month of Lunches by Don Jones(3214)
Learning Java by Patrick Niemeyer & Daniel Leuck(2860)
Learning React: Functional Web Development with React and Redux by Banks Alex & Porcello Eve(2818)
Mastering Java 9 by Dr. Edward Lavieri(2561)
Learning Concurrency in Python by Elliot Forbes(2536)