# «Lower Bounds for Zero Knowledge on the Internet Joe Kilian ∗ Erez Petrank † Charles Rackoff‡ arXiv:cs/0107003v1 [cs.CR] 2 Jul 2001 February 26, ...»

Lower Bounds for Zero Knowledge on the Internet

Joe Kilian ∗ Erez Petrank † Charles Rackoff‡

arXiv:cs/0107003v1 [cs.CR] 2 Jul 2001

February 26, 2008

Abstract

We consider zero knowledge interactive proofs in a richer, more realistic communication

environment. In this setting, one may simultaneously engage in many interactive proofs, and

these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is

not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.

1 Introduction Zero knowledge [20] turned out to be a useful tool for many cryptographic applications. Many works have studied the numerous uses of zero knowledge proofs, and many other works have suggested how to improve the efﬁciency of these proofs. However, most of these works considered only the case where the proof stands alone, disconnected from the computing environment. An interesting question, which naturally arises these days, is how robust the notion of zero knowledge is in a broader setting. In particular, many computers today are connected through networks (from small local area networks to the entire Internet) in which connections are maintained in parallel asynchronous sessions. It is common to ﬁnd several connections (such as FTP, Telnet, An internet browser, etc.) running together on a single workstation. Can zero knowledge protocols be trusted in such an environment?

The robustness of zero knowledge has been studied before in the “simple” case of parallel repetitions. It is often desirable to run a probabilistic protocol many times in parallel, usually in order to reduce the expected error of a single run. The alternative of running these protocols sequentially has a cost of increasing the number of rounds and is considered inefﬁcient. It had been noted by several researchers that even in the parallel repetitions case the zero knowledge

**property does not necessarily hold. Goldreich and Krawczyk [16] proved a general lower bound:**

Any language that has a three round (black-box) zero-knowledge interactive proof with a small error probability (as can be obtained by parallel repetitions) is in BPP. Thus, for example, unless ∗ Yianilos Labs, joe@pnylab.com. Work done in part while at the NEC Research Institute.

†

**Dept. of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, Israel. Email:**

erez@cs.technion.ac.il.

‡

**Dept. of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 3G4. Email:**

rackoff@cs.toronto.edu.

Graph Isomorphism is in BPP, the protocol of [17] for Graph Isomorphism does not remain zero knowledge when run many times in parallel. Several papers have dealt with this problem, usually by letting the veriﬁer commit on it’s (non-adaptive) questions in advance [1, 3, 15, 12].

Our initial feeling was that the protocols that keep their zero knowledge property when run in parallel should also remain zero knowledge even in a multi-session asynchronous environment.

However, in this paper, we give some indications that this is not always the case.

Let us say a few words about what we need to show. In order to show that a protocol is zero knowledge in a modern networking environment, one must provide a proof that even within this complicated environment the protocol is still zero knowledge. But for us matters are simpler. We don’t need to cover all facets of a networking environment. We only have to show that zero knowledge may fail in a speciﬁc setting that is part of this environment. Namely, the environment may be more hostile to the protocol than the speciﬁc case we study, but since a protocol fails even with a benign setting, it is deﬁnitely not zero knowledge when we extend the power of the environment.

In particular, a networking environment may have various protocols running, multiple sessions, more than two parties involved, asynchronous setting, etc.

We show that zero knowledge may fail for a large class of protocols, even if we only run a single protocol between only two parties. We exploit the asynchronicity and the existence of multiple sessions. Clearly, if we also add other features, such as additional parties and other protocols running in parallel, then the security problems can only be ampliﬁed.

We show that any four-round black-box zero-knowledge proof with perfect completeness is not zero knowledge even in a very benign setting: The setting in which the protocol is run many times in an asynchronous environment, and an adversary (or the veriﬁer) gets to choose which message gets to be delivered next. Actually, the setting is even more benign: We set a speciﬁc schedule, known in advance to both prover and veriﬁer. Still, if the protocol can be (black-box) simulated, then the language must be in BPP.

Theorem 1 Suppose that (P, V ) is a 4-message interactive proof or argument for L with perfect completeness and error at most 1 and suppose that (P, V ) can be black-box simulated in the asynchronous setting. Then L ∈ BP P.

The 2 in the above statement may be replaced by any constant less than 1, with essentially no change to our proofs; with slight care, any error bounded away from 1 by a non-negligible factor may be accommodated.

The above result holds for all extensions of concurrent zero-knowledge. In particular, it holds for resettable zero-knowledge [5].

Note that we get a separation between protocols that remain zero knowledge even under parallel repetition and protocols that remain zero knowledge in an asynchronous setting. Assuming the existence of one-to-one one-way functions, there exist 4-message (computational) zero knowledge arguments for all NP languages [12]. However, there are no 4-message zero knowledge arguments for languages outside of BPP that are black box simulatable in the asynchronous setting.

Some words on the terminology we are using. By zero knowledge we mean computational zero knowledge, i.e., the distribution output by the simulation is polynomial-time indistinguishable from the distribution of the views of the veriﬁer in the original interaction. (Of-course, as the result is a lower bound, it holds also for perfect and statistical zero knowledge.) The prover may be inﬁnitely powerful (i.e., an interactive proof) or it may be computationally bounded (i.e., an argument). We consider black box zero knowledge as deﬁned by Goldreich and Oren [24, 18], and reﬁned in [16].

1.1 Related work Dwork, Naor, and Sahai [10] were the ﬁrst to explore zero-knowledge in the asynchronous setting.

They denoted zero-knowledge protocols that are robust to asynchronous composition concurrent zero-knowledge protocols. It was noticed in [10] that several known zero-knowledge proofs, with a straightforward adaptation of their original simulation to the asynchronous environment, may cause the simulator to work exponential time. Thus, it seems that the zero-knowledge property does not necessarily carry over to the asynchronous setting. In order to provide a protocol that may be used in a modern environment, they presented a compromise: a protocol that is not zeroknowledge in a fully asynchronous setting, but is zero-knowledge in an environment with bounds on the asynchronisity. In particular, they present a 4 round zero-knowledge argument for NP assuming that there are two constants α and β such that the fastest message arrives within time at least α and the slowest message arrives within time at most β.

Dwork and Sahai [11] reduced the limitation on the asynchronisity. They presented a proof which has a preprocessing phase and a proof-body phase. Their proof is concurrent zero-knowledge argument for NP such that the (α, β) limitation is required only during the preprocessing stage.

Then, the body of the proofs can be run in a fully asynchronous environment.

Our result is complementary to theirs, illustrating why it is difﬁcult to achieve zero-knowledge in the asynchronous setting without using such an augmented model.

Several subsequent works have already appeared since the ﬁrst publication of this paper [23].

One question that was raised was: does there exist a fully asynchronous (concurrent) zero-knowledge proof for NP?

The answer was given by Richardson and Kilian [25] who presented concurrent zero-knowledge arguments for all languages in NP, that is robust in the fully asynchronous setting. However, this protocol is not practical. It requires a polynomial number in k of rounds, which makes it unacceptable in practice. k here is the security parameter: the length of the input and the number of proofs that may run concurrently are bounded by a polynomial in k.

The upper bound on the number of rounds has been drastically improved by Kilian and Petrank [22]. It turns out that the number of rounds that sufﬁces for constructing concurrent zero knowledge is any m satisfying m = ω(log2 k).

Rosen [26] has improved the result described in this paper, i.e., the lower bound on the number of rounds required for concurrent zero-knowledge from 5 to 8. Canetti, Kilian, Petrank and Rosen [6] have substantially improved the lower bound to Ω(logk / log log k). The parameter k is the security parameter. A polynomial in k bounds the length of the inputs, the number of proofs that may start concurrently, and the time complexity that the parties spend in the protocol.

Other researchers have concentrated on presenting efﬁcient concurrent zero-knowledge protocols for NP with weaker compromises on the asynchronisity of the environment. Crescenzo and Ostrovsky [8] presented a concurrent zero-knowledge argument for NP with a preprocessing phase. They removed the (α, β) constraint of [11], and the only requirement is that there must be a separating point in time between all preprocessing of all concurrent proofs, and all bodies of all proofs. Namely, the ﬁrst body of any proof may start only after all preprocessing phases in all the proofs have completed. D˚ mgard [9] and Canetti et. al. [5] have further reduced the limits on a asynchronisity. They require that prior to the beginning of the proofs, all veriﬁers have deposited a public key in a public database. In [9] it is required that the public key is valid, i.e., that the veriﬁer must know the secret key associated with it. In [5] this requirement is relaxed. The veriﬁer only has to have a deposited string in the public database. Thus, these proofs are efﬁcient, and make only the following compromise over full asynchronisity: all veriﬁers must be previously registered before any of them can engage in a proof. A veriﬁer that has not been registered cannot join until all proofs are completed and then it must register itself before any new proof begins.

As an extension to concurrent zero-knowledge, Canetti et. al. presented resettable zeroknowledge proofs [5]. These are zero-knowledge proofs that on top of being concurrent, they remain zero-knowledge also when the veriﬁer is allowed to run the prover repeatedly on a ﬁxed (yet, randomly chosen) random tape. Our lower bound applies, of-course, also to resettable zeroknowledge.

Feige and Shamir have suggested to give up achieving full zero-knowledge in the asynchronous setting and presented a property of proofs called witness indistinguishability. They showed that witness indistinguishability is preserved also in the asynchronous setting [13].

The basic framework of the proof in this paper uses the ideas developed by Goldreich and Krawczyk [16]. Following their technique, we use a good simulator S of an interactive proof (or argument) (P, V ) for a language L to create an efﬁcient prover PS that causes V to accept reasonably often on inputs in L.

1.2 Guide to the paper In Section 2 we discuss black-box simulatability and the framework used by Goldreich and Krawczyk.

In Section 3 we show how to convert an asynchronous simulator into an efﬁcient prover. In Sections 4 and 5 we analyze the success probability of this prover.

2.2 Black-box veriﬁers with private random functions ˆ In this paper, as in [16], we note that it is enough to consider deterministic V, i.e., even determinˆ istic (yet, cheating) veriﬁers are hard to simulate. Also, following [16], we consider veriﬁers V that have access to a private random hash function H, that is wired into them and is not directly ˆ accessible to the simulator (note that V is deterministic in that it doesn’t use an external source of randomness; its construction is randomized). That is, the simulator may gain only indirect access ˆ to H, by observing V ’s input/output behavior. For convenience, we assume that for any polynomially bounded n and m, H will take an n-bit input and return an m-bit output. In practice, H will be deﬁned for big enough n and m, and its inputs (if short) will be padded to ﬁt the length of H’s inputs. Pedantically, we can view H as a family {Hm,n } of hash functions; we suppress these subscripts for clarity.

As in [16], we will think of H as being randomly chosen from a family of hash functions [7].

And as in [16] we do not use the standard pairwise independent family. Instead we use families of hash functions that achieve p(n)-independence, for some sufﬁciently large polynomial p. A member H in this family can be described by a string of polynomial length, and it is this string that is wired into the veriﬁer. The polynomial p is set to exceed the running time of the simulator times the length of V ’s answers. Thus, even if the simulator poses to V a different query in each of its steps, and if for each query V generates the hash of the query, using H, then the simulator will face a veriﬁer that uses a completely random string for each of its (different) queries. Of course, As one slight exception, [21] proves security against space-bounded veriﬁers by considering the internal state of the veriﬁers. However, these techniques do not seem applicable to more standard classes of veriﬁers.