Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP
Authors:
- Ivan B. DamgårdIDIvan B. Damgård
- Birgit PfitzmannBPBirgit Pfitzmann
Open Access
- 20 June 1997
- journal article
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 4 (50)
Abstract
We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independentiterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relationsbetween the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using thetheory of proofs of knowledge. We also prove that in the non-uniform model of complexity the error probabilityof independent iterations of an argument does indeed decrease exponentially - to our knowledge this is the first result about a strictly exponentially small error probability in a computational cryptographic security property. As an illustration of our first result, we present a very efficient zero-knowledge argumentfor circuit satisfiability, and thus for any NP problem, based on any collision-intractable hash function. Our theory applies to show the soundness of this protocol. Using an efficient hash function such as SHA-1, the protocol can handle about 20000 binary gates per second at an error level of 2^−50.Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,efficient general primitives, multi-bit commitment, statistical zero-knowledge.Keywords
This publication has 5 references indexed in Scilit:
- Constant-round perfect zero-knowledge computationally convincing protocolsTheoretical Computer Science, 1991
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Minimum disclosure proofs of knowledgeJournal of Computer and System Sciences, 1988
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Probabilistic encryptionJournal of Computer and System Sciences, 1984