We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, a<br />circuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)<br />interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication<br />of Omega(n^3 log n) bits.<br />Variations of the technique behind these protocols lead to other interesting applications.<br />We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)<br />bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.<br />As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof<br />system with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.
We present a zero-knowledge proof system [19] for any NP language L, which<br />allows showing that x in L with error probability less than 2^−k using communication<br />corresponding to O(|x|^c) + k bit commitments, where c is a constant depending only<br />on L. The proof can be based on any bit commitment scheme with a particular set<br />of properties. We suggest an efficient implementation based on factoring.<br />We also present a 4-move perfect zero-knowledge interactive argument for any NP-language<br />L. On input x in L, the communication complexity is O(|x|^c) max(k; l)<br />bits, where l is the security parameter for the prover. Again, the protocol can be<br />based on any bit commitment scheme with a particular set of properties. We suggest<br />efficient implementations based on discrete logarithms or factoring.<br />We present an application of our techniques to multiparty computations, allowing<br />for example t committed oblivious transfers with error probability 2^−k to be done<br />simultaneously using O(t+k) commitments. Results for general computations follow<br />from this.<br />As a function of the security parameters, our protocols have the smallest known<br />asymptotic communication complexity among general proofs or arguments for NP.<br />Moreover, the constants involved are small enough for the protocols to be practical in<br />a realistic situation: both protocols are based on a Boolean formula Phi containing and-<br />, or- and not-operators which verifies an NP-witness of membership in L. Let n be<br />the number of times this formula reads an input variable. Then the communication<br />complexity of the protocols when using our concrete commitment schemes can be<br />more precisely stated as at most 4n + k + 1 commitments for the interactive proof<br />and at most 5nl +5l bits for the argument (assuming k <= l). Thus, if we use k = n,<br />the number of commitments required for the proof is linear in n.<br />Both protocols are also proofs of knowledge of an NP-witness of membership in<br />the language involved.
We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that x 2 L with error probability less than 2 \\Gammak using communication corresponding to O(jxj c )+O(k) bit commitments, where c is a constant depending only on L. We also present a 4-move perfect zero knowledge interactive argument for any NP-language L. On input x 2 L, the communication complexity is O(jxj c ) \\Delta max(k; l) bits, where l is the security parameter for the prover 1 . The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: our protocols allows proving/arguing satisfiability of a Boo...
The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment.>
A proof is whatever convinces me. Shimon Even (1935–2004) The glory attached to the creativity involved in finding proofs makes us forget that it is the less glorified process of verification that gives proofs their value. Conceptually speaking, proofs are secondary to the verification process, whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure presumes the notion of computation and furthermore the notion of efficient computation. This implicit stipulation is made explicit in the definition of NP , where efficient computation is associated with deterministic polynomial-time algorithms. However, as argued next, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In this chapter, we shall study three types of probabilistic proof systems, called interactive proofs, zero-knowledge proofs , and probabilistic checkable proofs . In each of these three cases, we shall present fascinating results that cannot be obtained when considering the analogous deterministic proof systems. Summary: The association of efficient procedures with deterministic polynomial-time procedures is the basis for viewing NP-proof systems as the canonical formulation of proof systems (with efficient verification procedures). Allowing probabilistic verification procedures and, moreover, ruling by statistical evidence gives rise to various types of probabilistic proof systems. Indeed, these probabilistic proof systems carry a probability of error (which is explicitly bounded and can be reduced by successive applications of the proof system), yet they offer various advantages over the traditional (deterministic and errorless) proof systems. […]
William A. Wulf, Alec Yasinsac, Katie S. Oliver, Ramesh Peri
Distributed systems have long relied on shared secrets to ensure the authenticity of principals. Public key systems and zero knowledge proofs of identity have reduced this reliance. We offer a method of remote authentication that can be used with no advance shared knowledge by parties, and that allows parties to increase their confidence in the authenticity of a suspicious party to an arbitrary level. Note: Abstract extracted from PDF text
We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol PR for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.
The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition.
An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.
<p>Let A and B be n x n matrices the entries of which are affine combinations of the variables a_1,... ,a_m,b_1,. .. ,b_m over GF(2). Suppose that, for each i, 1&lt;= i &lt;= m, the term a_i b_i is an element of the product matrix C = A € B. What is the maximum value that <em> m </em> can have as a function of <em> n </em>? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs.</p><p>The obvious upper bound of n^2 is improved to n^2 sqrt[3] 3 + O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.</p>
We look at the question of how powerful a prover must be to give a zero-knowledge proof.We present the first unconditional bounds on the complexity of a statistical ZK prover.The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle.Previously this was only known given the existence of one-way permutations. Extendingthese techniques to protocols of knowledge complexity k(n) >0, we derive bounds on the time complexity of languages of "small" knowledge complexity.Underlying these results is a technique for efficiently generating an "almost" random element of a set S E P.Namely, we construct a probabilistic machine with an NP oracle which, on input 1" and 6 > 0 runs in time polynomial in n and lg 6-1, and outputs a random string from a distribution within distance 6 of the uniform distribution on S n {O, l}~.