Authors Maya Leshkowitz,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65
www.theoryofcomputing.org
S PECIAL ISSUE : RANDOM 2018
Round Complexity Versus Randomness
Complexity in Interactive Proofs
Maya Leshkowitzβ
Received September 19, 2018; Revised January 15, 2022; Published June 7, 2022
Abstract. Consider an interactive proof system for some set π that has randomness
complexity π(π) for instances of length π, and arbitrary round complexity. We show
a public coin interactive proof system for π of round complexity π(π(π)/log π(π)).
Furthermore, the randomness complexity is preserved up to a constant factor, and
the resulting interactive proof system has perfect completeness.
An extended abstract of this paper appeared in the Proceedings of Proceedings of the 22nd International
Conference on Randomization and Computation (RANDOMβ18) [11].
β Work done while the author was at Weizmann Institute of Science
ACM Classification: F.1.3
AMS Classification: 68Q10, 68Q15, 68Q87
Key words and phrases: complexity theory, interactive proofs
Β© 2022 Maya Leshkowitz
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a013
M AYA L ESHKOWITZ
Contents
1 Introduction 4
1.1 Round complexity versus randomness complexity . . . . . . . . . . . . . . . . . . 5
1.1.1 Conditional tightness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 On the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Private coin emulation protocol . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Public coin emulation protocol . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Relation to previous public coin emulation protocols . . . . . . . . . . . . . . . . . 9
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Preliminaries 10
3 The protocol tree 11
4 The emulation tree 12
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1.1 The protocol tree is of height π π(π)/log π(π) and degree poly(π) . . . . 13
4.1.2 The degree of the protocol tree is bounded by poly(π) . . . . . . . . . . . . 13
4.1.3 The general case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 The Build_Tree procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Properties of the emulation tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Public coin emulation 19
5.1 Emulation preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Emulation construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 The number of rounds and randomness complexity . . . . . . . . . . . . . . . . . 24
5.4 Approximate sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Analysis of the emulation 25
6.1 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.2.1 Deriving a prover strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.2.2 Actual weight of a node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2.3 Bounding the gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.2.4 Concluding the soundness proof . . . . . . . . . . . . . . . . . . . . . . . . 40
Appendix A Private coin emulation 42
A.1 The protocol tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
A.2 The emulation tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.3 Emulation protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.3.1 Protocol preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.3.2 Protocol construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.3.3 Number of rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 2
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
A.4 Proof of correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A.4.1 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A.4.2 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Appendix B Alternative public coin emulation 56
B.1 Concluding the main Theorem 1.1 using the alternative emulation . . . . . . . . . 57
B.2 Proof Sketch of Theorem B.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
B.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
B.2.2 The Build_Tree procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
B.2.3 Properties of the emulation tree . . . . . . . . . . . . . . . . . . . . . . . . 60
B.2.4 Public Coin Emulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 3
M AYA L ESHKOWITZ
1 Introduction
The notion of interactive proof systems, put forward by Goldwasser, Micali, Rackoff [8] and
Babai [1], and the demonstration of their power by Lund, Fortnow, Karloff, Nisan [12] and
Shamir [14] are among the most celebrated achievements of complexity theory.
Loosely speaking, interactive proof systems capture the most general way in which one party
can efficiently verify claims made by another, more powerful, party. The definition of interactive
proof systems generalizes the traditional notion of a proof system (indeed, an NP-proof system),
by allowing both interaction and randomness.
It is well known that both interaction and randomness are inherent to the power of
interactive proof systems, where here we mean the extra power above that of NP-proof systems.
Interactive proofs with no randomness can be easily transformed into NP-proof systems,
whereas randomized non-interactive proofs, captured by the class MA (defined by Babai [1]), are
essentially the randomized version of NP.
Both interaction and randomness are quantitative notions; that is, one talks of the βamount
of interaction,β which is commonly associated with the (total) number of messages exchanged
(a. k. a. number of rounds), and of the amount of randomness (a. k. a. randomness complexity).
While the previous paragraph refers to the qualitative question and asserts that both interaction
and randomness are essential, a finer study of the quantitative question is called for; that is, it is
natural to ask about the necessary amount of interaction and randomness in various interactive
proof systems.
The study of round complexity in interactive proof systems has some well-known results:
Babai introduced public coin interactive proofs (a. k. a. ArthurβMerlin proofs) in [1], and showed
that the round complexity of any bounded-round ArthurβMerlin proof can be reduced to AM (a
two-message ArthurβMerlin proof). Babai and Moran extended this result in [2] and showed
that the round complexity of ArthurβMerlin proofs for instances of length π can be reduced
by any constant factor [2], assuming we keep at least one AM alternation. The public coin
transformation of Goldwasser and Sipser [9] (which essentially preserves the number of rounds)
extends this result to private-coin interactive proof systems. It is also known that a stronger
round reduction is quite unlikely. This is the case due to a combination of results reviewed
below in the paragraph titled βconditional tightness.β
In contrast, we are only aware of one study that focuses on the randomness complexity of
interactive proof systems.1 Specifically, Bellare et al. [3] studied the randomness complexity of
error reduction in the context of interactive proof systems. (We mention that the randomness
complexity is also of interest in [5], which provides an alternative transformation of general
interactive proof systems to public coin ones.)
Regarding the completeness in interactive proofs, the fact that every interactive proof system
can be transformed into one with perfect completeness was shown in [4].
1We refer to unconditional results and not to the long line of research on randomness versus hardness trade-offs
that relies on uniform or non-uniform assumptions, see, e. g., [10],[13].
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 4
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
1.1 Round complexity versus randomness complexity
A natural question, which to the best of our knowledge has not been considered before, is what is
the relation between the two foregoing complexity measures. We do suspect that there are cases
when the randomness complexity cannot be made smaller than the round complexity without
trivially increasing the number of rounds. This is because constant-round interactive proof
systems seem more powerful than NP-proof systems (see, e. g., the Graph Non-Isomorphism
proof of [6]), whereas a logarithmic amount of randomness is clearly useless (since this reduces
to P). But can the round complexity be greater than the randomness complexity?
The answer is definitely negative if we consider public coin interactive proof systems. Recall
that in these proof systems, in each round, the verifier sends the outcome of fresh coins that it
has tossed at the beginning of the current round, and so by definition, the number of coin tosses
is at least as large as the number of rounds.2 However, it is not clear what happens in the case of
general interactive proofs. (In particular, the transformation of [9] significantly increases the
randomness complexity by a factor depending on the number of rounds.)
Recall that in a general interactive proof system, the verifier may toss all coins at the very
beginning, but its message in each round may be a complex function of the outcome of these
coins (and the messages it has received from the prover). In particular, the verifierβs messages
may have very little information content (from the proverβs point of view), and so in principle
we could have many more rounds than the number of coins tossed. Furthermore, it is not clear
how to collapse rounds that yield verifier messages of low information content. These are the
issues we deal with when showing that even in general interactive proof systems, randomness
complexity π(π) yields round complexity π π(π)/log π(π) . Hence, in interactive proof systems,
the round complexity is smaller than the randomness complexity.
Theorem 1.1 (Main Theorem). Suppose that π has an interactive proof system of randomness complexity
π(π) for instances of length π. Then, π has a public coin interactive proof system of round complexity
π(π(π)/log π(π)) and randomness complexity π(π(π)). Furthermore, the resulting interactive proof
system has perfect completeness.
Note that, in addition to obtaining the public coin feature, we obtain perfect completeness
for free. That is, even if the original system does not have perfect completeness, the new one has
this feature.
1.1.1 Conditional tightness
The round complexity obtained by Theorem 1.1 is the best one may hope for at this time, since
a result asserting round complexity π(π(π)/log π(π)) for any set that has an interactive proof
system of randomness complexity π(π) would yield an unexpected result that seems currently
out of reach. Specifically, it would place SAT in coAM-TIME(2π(π) ), which contradicts common
beliefs. The full reasoning is as follows:
2This presumes that the definition requires the verifier to send a non-empty message in each round. But otherwise
(i. e., if the definition allows empty messages), rounds in which the verifier sends nothing can be collapsed.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 5
M AYA L ESHKOWITZ
1. A variant of the celebrated interactive proof system for SAT [14] yields an interactive proof
system of randomness complexity π(π) for unsatisfiable CNFs with π variables. (This
interactive proof consists of π/log π rounds such that in each round we strip a single
variable in the sum-check that sums over π/log π variables with values in [π], while using
a finite field of order poly(π). See [7, Sec 8].)3
2. On the other hand, any set having an π-round interactive proof system is in AM-TIME(π π(π) ),
see [7, Apdx B]. Hence, if unsatisfiable CNFs have an interactive proof of round complexity
π(π/log π), then such instances can be refuted in AM-TIME(2π(π) ), whereas AM-TIME(π)
may equal NTIME(poly(π)).
1.2 On the proof of Theorem 1.1
We start by giving an overview of a proof of a weaker result, in which we show how to transform
any interactive proof, of randomness complexity π(π), to a private coin interactive proof for the
same set that uses π(π(π)/log π(π)) rounds, while maintaining the randomness complexity of
π(π). This proof gives a flavor of the proof of the main theorem, but is significantly simpler.
1.2.1 Private coin emulation protocol
We describe the strategies of the new prover π and verifier π in iterations, where each iteration
may correspond to several rounds of the original protocol of prover π0 and verifier π0 . The
idea of the emulation protocol is that, in every iteration, we would like π to send possible
continuations of the current transcript (each possibly describing execution segments of several
rounds) that reveal much information about the verifierβs random coins. Hence, π sends
maximal transcripts such that each account for a noticeable fraction of the residual probability
mass.4 The verifier π then checks if one of these transcripts is consistent with the strategy of
π0 determined by the values of its random coins, which were tossed upfront. (That is, does the
transcript contain the messages that π0 would send using the private coin tosses of π and the
previous messages.) If so, π picks a maximum transcript consistent with the strategy of π0 , and
they continue their interaction from that point. Otherwise, π sends its next message (based on
the aforementioned coins) without using the continuations suggested by π. We stress that the
3This is done by packing a sequence of log π bits of the boolean variables into a symbol of π» = [π] β πΉ where
πΉ is some field. For π β β , where β = log π, denote by ππ (π₯) : πΉ β πΉ the polynomial of degree π β 1 that maps
each element in π» to the value of its πth boolean variable. Now, take the standard arithmetization of the CNF and
replace each occurrence of the variable indexed π Β· β + π by the polynomial ππ (π₯ π ), where π₯ π is the πΉ variable that
represents the πth block of boolean variables. The resulting polynomial is a polynomial in π/β variables, of total
degree π(π Β· π), where π is the number of clauses. Finally, the number of satisfying assignments is given by the
sum over all (π¦1 , ...., π¦π/β ) β π» π/β of the polynomial derived above. Furthermore, we do not execute the sum-check
protocol over an exponentially large finite field but rather over a finite field of prime cardinality π = poly(π), where π
is selected by the verifier at random among such primes.
4Note that in the eyes of an observer, a verifier that samples its random coins at the beginning of the interaction and
proceeds accordingly, is equivalent to a verifier that on each round samples a message with probability proportional
to its residual probability mass.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 6
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
only source of πβs randomness is its private coins tossed upfront, which are used to determine
the continuation of the transcript in each subsequent iteration.
We elaborate on how the prover π determines the continuations of the transcripts. Fixing
an iteration, we denote the current transcript by πΎ and its residual probability mass by π(πΎ).
Each transcript the prover sends on this iteration is a maximal continuation of πΎ that is a βheavy
continuation.β By a heavy continuation πΎ0, we mean that πΎ0 has probability mass greater than
π(πΎ)/π(π), when subtracting from it the probability mass of the continuations of πΎ that were
either sent by π in previous iterations, or previously in this iteration. A heavy continuation is
maximal in the sense that all its continuations are not heavy (probability mass not greater than
π(πΎ)/π(π)). Note that there are at most π(π) heavy continuations of πΎ, so the prover can send
them to the verifier (who is computationally bounded).
This conditioning allows π to send several continuations of the transcript, some of which
may also be continuations of the others. Consider for example the case that the prover sends
πΎπΌ 1 π½1 πΌ2 π½ 2 and πΎπΌ 1 π½ 1 . In this case if the verifier chooses πΎπΌ1 π½1 it means that in the next iteration
the continuation of this transcript cannot begin with πΌ2 π½2 .
The benefit of this method of determining transcript-continuations is that we guarantee
that in the next iteration the probability mass of the new transcript is lower than π(πΎ)/π(π). The
reasoning is as follows. If the verifier π chooses one of the transcripts suggested by the prover
π, then on the next iteration the residual probability mass of each of its continuations is lower
than π(πΎ)/π(π). Otherwise, this continuation should have been suggested by the prover on
the previous iteration. If π did not choose any of the transcripts, and instead continued the
transcript with its own message f πΌ1 , then it follows that the residual probability mass of the
transcript πΎ f
πΌ1 (under the conditioning of the appropriate events) is also lower than π(πΎ)/π(π),
otherwise the continuation πΎ f πΌ1 should have been suggested by π.
It follows that after π(π(π)/log π(π)) iterations the probability of the transcript generated is
at most (1/π(π))π(π)/log π(π) = 1/2π(π) , which means that there is a unique value of the coin tosses
consistent with the transcript. Hence, a complete transcript is generated and π can reject or
accept at this point. It is easy to show that if π follows the prescribed emulation, then the
verifier π accepts with the same probability as in the original interactive proof system, and
hence completeness is maintained.
Note that the above emulation per se does not suffice for proving soundness. It is essential
to include validation checks that guarantee that the transcripts provided by π are consistent
with some legal prover π0 strategy for the original protocol.5 This means that if π provides
two transcripts that share a prefix, this common prefix must end with a proverβs message and
diverge only depending on the verifierβs response. This implies that the prover π0 answers in
the same way to the same verifier π0 βs messages, which means that πβs strategy is consistent
with some prover π0 of the original proof system and so the soundness of the original proof
system is maintained.
5Otherwise π can provide different transcripts tailored to the verifierβs private coin tosses, whereas the original
prover could not have employed such a strategy since it is not exposed to the private coin tosses.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 7
M AYA L ESHKOWITZ
1.2.2 Public coin emulation protocol
The simplified private coin emulation protocol captures one of the key ideas of our public coin
emulation protocol. The difficulty that we face when seeking a public coin emulation is that
we cannot rely on hidden coins tossed upfront by the verifier. Thus, when presented with a
list of heavy continuations, it is unclear how the verifier should select one at random, since
the selection probability should be determined by the residual probability masses that are
unknown to it. Our solution is to have the prover provide these probabilities, but this raises
the need to verify these claimed values (and have the verifier reject right away if the sum of
these probabilities does not match the claimed probability of the transcript as determined before
the current iteration). In the last iteration of the emulation, a complete transcript is sampled,
containing the verifierβs private coins, hence the validity of the transcript and the claim can be
checked.
The foregoing description raises a few issues. Firstly, the prover should find a way to
communicate all the transcripts to the verifier, and not only the ones with high residual
probability mass as before. Second, it is not clear what happens to the soundness when the
prover provides wrong values for the residual probabilities. As for the second issue, note that
maliciously raising the claimed probability of a transcript does contribute towards having the
sum of probabilities meet the prior claim, but it makes the probability that this transcript is
selected higher, and so puts the prover in greater difficulties in the next iteration. Indeed, a
careful analysis shows that actually, the prover gains nothing by such behaviour, since when the
transcript is complete, false claims about its residual probability are easily detected.
Turning back to the first issue, we note that the issue is that there may be too many short
transcripts, that each account for a small fraction of the residual probability mass. To deal
with this case, we have the prover pack many transcripts into a single auxiliary message. We
use a succinct representation of a sequence that contains many of the transcripts but not all of
them (since otherwise, we would have made no progress at the current iteration). The succinct
representation should support the verification that the corresponding sequences are disjoint.
Now, each such βpackβ of transcripts will be assigned the corresponding probability mass, and
will be treated as if it were an actual transcript.
Needless to say, the foregoing is but a very rough sketch of the structure of the derived
proof system. The actual proof system uses a carefully designed verification procedure that
ensures that its executions can be mapped to executions in the original proof system (in order to
guarantee soundness).
We note that while the above description of the public coin emulation refers to the probability
that various transcripts appear in the original proof system (when the prover uses an optimal
strategy), our actual construction refers only to accepting transcripts (i. e., transcripts that lead
the original verifier to accept). Consequently, we obtain a proof system of perfect completeness,
even if the original proof system had two-sided error probability.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 8
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
1.3 Relation to previous public coin emulation protocols
The basic idea used in emulating a private coin interactive proof by a public coin one is having
the prover assist the verifier in generating its next message using public coins, instead of relying
on private coins to generate the messages. Goldwasser and Sipser, who first suggested this
emulation strategy [9], cluster the potential messages that the original verifier could have sent
on the next round into clusters according to the (approximate) number of coin sequences
that support each message. A constant-round, public-coin sampling protocol is utilized in
order to sample from the cluster of messages that have the largest number of coin sequences.
This emulation succeeds assuming a sufficiently large initial gap between completeness and
soundness, which is obtained at a cost of blowup of poly(π) factor in randomness complexity.
Thus, the original public coin emulation preserves the round complexity of the private coin
interactive proof but not the randomness complexity.
An alternative public coin emulation, suggested by Goldreich and Leshkowitz [5], is similar
to the original emulation but differs in the way the chosen cluster of messages (from which
the sampling is performed) is determined. Whereas in the original emulation the chosen
cluster is deterministically determined as the one with the largest number of coins, in the
alternative emulation the chosen cluster is selected probabilistically according to its weight (i. e.,
the number of coin tosses in the cluster). Therefore, the alternative emulation gets closer to
sampling from the actual distribution of prover verifier transcripts. Consequently, it requires a
smaller initial gap between completeness and soundness. Similarly to the original emulation,
the alternative emulation preserves the round complexity but not the randomness complexity,
although the blowup in randomness complexity is slightly reduced due to the decrease in the
completeness/soundness gap.
Our emulation protocol was designed with the goal of giving an upper bound on the
round complexity in terms of the randomness complexity, while preserving the randomness
complexity. To this end, the way the prover assists the verifier in generating its next message is
different from the method used in the aforementioned emulations. The prover supplies the
verifier with heavy continuations, which may correspond to multiple interaction rounds, that
account for a noticeable fraction of the residual weight. In addition to the heavy continuations,
the prover clusters the messages that each account for a small fraction of the residual weight
using a succinct representation that supports the verification that messages in each cluster are
disjoint. The method from the alternative emulation is then used to probabilistically select from
the joint set of clusters and heavy continuations. When a cluster is selected, instead of using
a sampling protocol to sample a message from the cluster, the emulation protocol is executed
iteratively until reaching a heavy continuation (which corresponds to a message of the original
interactive proof system). For this reason, the emulation protocol does not preserve the round
complexity, which may increase by a poly(π) factor. However, addressing our initial concern,
the combination of message generation and selection methods ensure that the randomness
complexity π(π) is preserved up to a constant factor and the new round complexity is at most
π(π(π)/log π(π)).
The original and alternative public coin emulations did not obtain perfect completeness
since they used a sampling protocol for sampling a message from a cluster, which may fail even
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 9
M AYA L ESHKOWITZ
when the prover is honest. Since our emulation does not utilize such a protocol, we obtain
perfect completeness for free.
An additional known public coin emulation is obtained using the LFKNβShamir protocol
[12, 14] to derive a public coin interactive proof system with perfect completeness to any set
in PSPACE, and applying the protocol on the trivial PSPACE emulation of the private coin
interactive proof system. This public coin emulation with perfect completeness is derived at a
cost of polynomial round complexity and randomness complexity.
1.4 Organization
Towards proving the main theorem we shall show how to emulate an existing interactive proof
system with a public coin emulation protocol that has π π(π)/log π(π) rounds. We begin by
introducing the notion of βprotocol treesβ in Section 3, which we use to describe the interaction
of the verifier and prover of the original interactive proof system. In Section 4, we shall show
how to transform the protocol tree into an βemulation tree,β that contains the continuations
of the transcripts that the prover sends on each iteration along with their probability masses.
Using this emulation tree, we then turn to describing the public coin emulation protocol for the
new prover and verifier, in Section 5. The analysis of the emulation, which is given in Section 6,
is partitioned into completeness (Subsection 6.1) and soundness (Subsection 6.2).
In Appendix A, we show how to emulate the existing interactive proof system with a private
coin emulation protocol that has π π(π)/log π(π) rounds. The organization of this section is
similar to the organization of the main part of the paper, although most sections of it are less
involved. Appendix A is written so it can be read independently of the rest of the paper, and
the decision if to read it before or after the other parts of the paper is left to the reader.
We provide notes that point out the main differences and similarities between the
private and public coin emulation protocols. These notes are typeset as this one.
In Appendix B, we show an additional way to emulate the existing proof system with a
public coin one that has perfect completeness. We stress that this is emulation is weaker than
the one in the main theorem since it does not reduce the round complexity.
The two emulations in Appendix A and Appendix B together can be used to derive an
alternative proof of the main theorem. This alternative proof of the main theorem is more
modular, splitting the transformation into two simpler independent steps. We show how this
can be done in Appendix B.
2 Preliminaries
Let us start by formally defining interactive proof systems, where the completeness and
soundness bounds are parameters.
Definition 2.1 (Interactive Proof Systems). Let π, π : β β [0, 1] such that π(|π₯|) β₯ π (|π₯|) +
1/poly(|π₯|). An interactive proof system for a set π is a two-party game, between a verifier,
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 10
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
denoted π, executing a probabilistic polynomial-time strategy, and a prover, denoted π, executing
a (computationally unbounded) strategy, satisfying the following two conditions:
β’ Completeness with bound π: For every π₯ β π, the verifier π accepts with probability at
least π(|π₯|) after interacting with the prover π on common input π₯.
β’ Soundness with bound π : For every π₯ β π and every prover π e strategy, the verifier π
accepts with probability at most π (|π₯|) after interacting with π
e on common input π₯.
When π and π are not specified, we mean π β‘ 2/3 and π β‘ 1/3. We denote by IP the class of sets
having interactive proof systems. When π β‘ 1, we say that the system has perfect completeness.
3 The protocol tree of the original proof system
Note that the protocol tree for the private coin emulation described in Section A.1
is similar to the one described here, except for the definition of weights.
Fixing an interactive proof between a prover π and a verifier π, and an instance π₯ of
length π, we describe the possible prover-verifier interactions on common input π₯ using a tree
ππ,π whose height corresponds to the number of rounds of interaction. For some β = β (π),
we assume without loss of generality that in round π the verifier sends a message πΌ π β {0, 1}β ,
and the prover responds with a message π½ π β {0, 1}β . We can also assume, without loss of
generality, that the proverβs strategy is deterministic and fixed. Each node π£ on level π represents
a possible prover-verifier transcript for the first π rounds of the interaction. The branching of
ππ,π represents the possible ways to extend the transcript to the next round. The number of
ways to extend the transcript is the number of possible messages of the verifier in the next round
since the prover is deterministic. Hence, each node has at most π· B 2β children, corresponding
to the 2β possible verifier messages for the next round. The proverβs response to each such
message is included in the description of the corresponding node.
The description of a node π’ on level π contains the partial transcript πΎ (π’) = πΌ1 π½ 1 , . . . , πΌ π π½ π
of the interaction up to the πβth round. The root (at level zero) has an empty transcript, whereas
a leaf in ππ,π represents a complete prover-verifier interaction. We can assume, without loss
of generality, that the verifier sends its private coins on the last round, and hence every leaf is
associated with a sequence of coin tosses which leads the verifier either to accept or to reject.
Hence, we can represent the possible interactions generated by the interactive proof system
using a tree of height π which has 2π(π) leaves, where π is the number of rounds and π(π) is the
number of coin tosses. Using a constant number of repetitions of an interactive proof system
with standard completeness and soundness parameters, we can assume that the interactive proof
system has completeness parameter 9/10 and soundness parameter 1/10.6 Note that this blows
up the randomness complexity only by a constant factor (as compared to our interactive proof
6The new interactive proof system will work by performing multiple invocations of the original interactive proof
system. The verifier will accept if the majority of the original runs are accepting.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 11
M AYA L ESHKOWITZ
for the standard 1/3, 2/3 parameters). Therefore, if π₯ is a yes-instance then at least 9/10 Β· 2π(π) of
its leaves represent accepting runs, and if π₯ is a no-instance then at most 1/10 Β· 2π(π) of its leaves
represent accepting runs.
The description of a node also contains its weight, denoted π€(π’). The weight of the node is
the number of coin sequences that are consistent with the node and lead the verifier to accept at
the end of the interaction. That is,
Definition 3.1 (Weight of a leaf). Let π’ be a leaf in ππ,π with transcript πΎ(π’) which corresponds
to the full transcript of the interaction of π and π on input π₯, when π uses coin sequence π; that
is,
πΎ (π’) = (πΌ1 , π½ 1 , . . . , πΌ π , π½ π , (π, π)) (3.1)
where π = π (π₯, π, π½ 1 , . . . , π½ π ) β {0, 1} is πβs final verdict and for every π = 1, . . . , π it holds that
πΌ π = π (π₯, π, π½1 , . . . , π½ πβ1 ) and π½ π = π (π₯, πΌ1 , . . . , πΌ π ). We define the weight π€(π’) of π’ to be πβs
final verdict π.
Definition 3.2 (Weight of a node). The weight π€(π’) of a node π’ in ππ,π is the sum of the weights
of the leaves that are descendants of π’.
Note that π€(π’) is proportional to the probability that πΎ(π’) is generated and the verifier
accepts at the end of the interaction.
In the private coin emulation the weight of all the leaves is defined as 1. Hence, in
the private coin emulation the weight of a node is the number of coin sequences
that are consistent with the corresponding transcript.
4 The emulation tree
4.1 Overview
So far we have explained how to represent the possible executions of an π-round interactive
proof system between prover π0 and verifier π0 on some instance π₯, where the protocol utilizes
π(π) coins. This results in a protocol tree ππ0 ,π0 of height π with 2π(π) leaves. Our goal is to
transform this protocol tree to an emulation tree, denoted by πΈπ0 ,π0 , that defines a prover strategy
for a π π(π)/log π(π) -round public coin emulation protocol. This transformation is done
using the Build_Tree procedure. First, we describe how the emulation tree is used in the very
restricted case where the protocol tree is already suitable for our proposed public coin protocol
and the Build_Tree procedure is not required. Next, we explain how the transformation works
in a restricted case when the degree of the protocol tree is bounded by poly(π), and finally in
the case of a general protocol tree.
The procedure for constructing the private coin emulation tree described in
Section A.2 is similar to the one described here for the restricted case that the
degree of the protocol tree is bounded by poly(π). Those familiar with the
construction of the emulation tree for the private coin protocol can skip to the
βgeneral caseβ paragraph.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 12
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
The protocol tree is of height π π(π)/log π(π) and degree poly(π)
4.1.1
In order to convince the verifier that π₯ is a yes-instance the prover makes an initial claim that
the weight of the root of the protocol tree ππ0 ,π0 is at least π Β· 2π(π) (where π is the completeness
bound). The emulation is initiated at the root of ππ0 ,π0 and on each round of the emulation the
prover assists the verifier at progressing one step down the ππ0 ,π0 . (This assistance is required
because the verifier does not have access to ππ0 ,π0 .) Each round consists of the prover providing
the verifier with the descriptions of the children of the current node π’ that was sampled on
the previous round, where these descriptions contain the weights of the various children. The
verifier performs validations to check that according to the descriptions these are legal children
of π’, and that their claimed weights sum up to π€(π’). Then, the verifier samples a child with
probability that is approximately proportional to its weight, up to a multiplicative factor of
1 + 1/π(π) using π log π(π) public coins. On the last round, a leaf is sampled, whose description
contains the complete prover-verifier interaction along with the coins tossed by the verifier. The
new verifier accepts if and only if the transcript sampled is consistent with the original verifierβs
strategy according to the coin tosses revealed, and leads the original verifier to accept.
To see why this is indeed an interactive proof system for the original language, note that
an honest prover can always convince the verifier of the correctness of a true claim using this
emulation. Hence, the interactive proof system we described has perfect completeness. On the
other hand, for no-instances, a prover that wants to make the verifier accept must make an initial
claim that the weight of the empty transcript is much larger than its actual weight. Namely,
the actual weight of the empty transcript is at most π Β· 2π(π) , whereas the prover claims that the
weight is at least π Β· 2π(π) , where π > π are the completeness and soundness bounds of the original
interactive proof system. Thus, there is a multiplicative gap of π /π between the actual weight
and the one claimed. We can show that, in expectation, this gap is maintained throughout
the emulation, up to a factor of (1 + 1/π(π))π(π) < e that comes from the approximation factor.
Therefore, the probability that a leaf that corresponds to an accepting run is sampled on the last
round (and hence the verifier accepts) is at most eπ /π which is smaller than 1/3 for a suitable
choice of π and π.
4.1.2 The degree of the protocol tree is bounded by poly(π)
In this case the height of the protocol tree ππ0 ,π0 may be asymptotically larger than π(π)/log π(π).
We create a new tree of height π π(π)/log π(π) to guide the proverβs strategy, which we use in
a way similar to how we used the protocol tree in the previous paragraph. We call this tree the
emulation tree, which we denote by πΈπ0 ,π0 . The nodes in the πΈπ0 ,π0 are nodes in ππ0 ,π0 . However,
the children of a node π’ in πΈπ0 ,π0 may be non-immediate descendants of π’ in ππ0 ,π0 .
We start with a protocol tree ππ0 ,π0 rooted at π whose weight is π€(π), and on each step we
modify this tree towards creating an emulation tree πΈπ0 ,π0 . We define a heavy descendant of
node π to be a node whose weight is at least π€(π)/π(π) and the weight of each of its children is
smaller than π€(π)/π(π). Note that there are at most π(π) heavy descendants for each node in the
tree.
We modify ππ0 ,π0 so that the children of π in the emulation tree are its original children
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 13
M AYA L ESHKOWITZ
as well as the heavy descendants that we lift upwards to make them new children of π. This
modification is performed using the Build_Tree(r) procedure, which when invoked on a node
π identifies the nodes that will be children of π in the new tree, sets them as children of π, and
then initiates recursive invocations on the (original and new) children of π, creating the new
emulation tree rooted at π. Details follow.
The Build_Tree(r) begins by identifying the heavy descendants of π (they can also be
children of π in πππ0 ,π0 ), which will become heavy children of π. Denote by πππ’0 ,π0 the intermediate
tree after we identify and set π’ as a heavy descendant of π. This way we have a notation for every
transformation of the tree in which we set an additional child in the tree. That is, if the next tree
after πππ’0 ,π0 is πππ€0 ,π0 then in πππ€0 ,π0 both π’ and π€ are heavy children of π. After we identified the
children of π in the new emulation tree, we call the Build_Tree procedure recursively on each
child of π, which creates an emulation tree rooted at that node.
Observe that in the final emulation tree πΈπ0 ,π0 , for each node π’, the weight of each grandchild
of π’ is at most π€(π’)/π(π). This is because if π£ is a heavy child of π’ in πΈπ0 ,π0 , then the weight of
each descendant of π£ in πππ’0 ,π0 is at most π€(π’)/π(π). Since the children of π£ in the emulation tree
are descendants of π£ in πππ’0 ,π0 the claim holds. Otherwise, π£ is a non-heavy child of π’, so its
weight is smaller than π€(π’)/π(π) and hence the weight of each child of π£ is also smaller than
π€(π’)/π(π).
It follows that the height of πΈπ0 ,π0 is π π(π)/log π(π) . The number of children of each node
is at most poly(π), because we add at most π(π) heavy children to the original children of each
node, and π(π) is at most polynomial in π. Hence, the emulation tree has properties similar
to the protocol tree in the previous paragraph, so it is suitable for our public coin emulation
described in the previous subsection.
4.1.3 The general case
In general, the degree of the protocol tree ππ0 ,π0 may be exponential in π. Lifting the heavy
children as we did in the case of unbounded height guarantees that the height of the new
emulation tree πΈπ0 ,π0 is π π(π)/log π(π) , but its degree may be super-polynomial in π (due to
the original children). Hence, we will not be able to perform the emulation by having the prover
provide the verifier with the descriptions of the children of the current node. Thus, we also
need to make sure we create πΈπ0 ,π0 so that its degree is poly(π).
In order to reduce the degree when it is too large, we group the non-heavy children of π
under new children, which we call interval children. This is done in addition to handling the
heavy children of π as before. In general, children of π in ππ0 ,π0 may become non-immediate
descendants in the next intermediate tree, and non-immediate descendants of π may become
immediate children of π in the next intermediate tree (due to lifting).
Determining the children of π is done in two steps, as part of the Build_Tree(r) procedure.
The first step is identifying the heavy descendants π£ 1 , . . . , π£ π of π and lifting them to be children
π£
of π, creating heavy children. This is done by creating intermediate trees πππ£01,π0 ,. . . ,ππ0π,π0 , through
a sequence of editing steps. On each step, we create a new intermediate tree and edit it on the
next step, by identifying and moving the next heavy descendant. Next, we unite the non-heavy
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 14
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
children of π into groups. We unite the children by lexicographic order of their transcript field,
such that the weight of each group is larger than π€(π)/π(π) and at most 2π€(π)/π(π) (except for,
possibly, the last group which is only required to have weight smaller than 2π€(π)/π(π)). We
create a new interval child π£ for each such group, where the children of π£ are the nodes in the
group.
After creating all the interval children of π, the children of π in the final emulation tree
πΈπ0 ,π0 are exactly the children of π in πππ§0 ,π0 , where π§ is the last interval child of π created. The
number of children π has is at most π(π), since the weight of each child of π (except for possibly
the last interval child) is at least π€(π)/π(π). Next, the procedure is called recursively on the
children of π in πππ§0 ,π0 in order to create the final emulation tree.
The description of a node π’ in the emulation tree is composed of the transcript field
πΎ (π’) = πΌ1 π½ 1 . . . πΌ π π½ π and a weight field π€(π’) as in the original protocol tree, with an additional
range field π
(π’). The range of a node represents the possible range of its childrenβs transcripts.
After determining the heavy children of π’, and before grouping the non-heavy children
under interval children, the non-heavy children of π’ are all children of π’ in ππ0 ,π0 .
Hence, the transcripts of the children of each interval child are the same up to the last
verifierβs message on which they differ, which corresponds to the branching of the intermediate
tree for the next round. Thus, we can label the range π
(π’) = [π , π] where π < π β {0, 1}β
according to the range of the last verifier message in the transcript field of the children of π’.
Heavy children have full range 0β , 1β , whereas the range of interval children is a subinterval
of 0β , 1β such that this subinterval corresponds to the transcripts of the descendants that are
grouped under this node.
We show in the analysis that the height of πΈπ0 ,π0 is π π(π)/log π(π) . The degree of nodes
in πΈπ0 ,π0 is at most π(π), hence it is suitable for public coin emulation like in the previous
subsection.
(The running time of this algorithm is at least the size of the protocol tree, which is exponential
in π(π), and thus it may be exponential in |π₯|. However, the prover is the one that runs this
algorithm and the prover is computationally unbounded. Therefore, the running time is not an
issue.)
4.2 The Build_Tree procedure
Denote the designated prover and verifier of the original interactive proof system by π0 and
π0 respectively, and the protocol tree of π0 and π0 for a yes-instance π₯ by ππ0 ,π0 . The Build_Tree
procedure is a recursive procedure that reads and updates a tree π, which is initially set to
equal the protocol tree ππ0 ,π0 until obtaining the final emulation tree, denoted by πΈπ0 ,π0 . When
invoked on a node π’ in π, the procedure determines the children of π’, updates the global tree
and invokes the procedure recursively on the children of π’.
We denote by π(π’) the subtree of π rooted at π’.
Initialization. The tree π is initialized to be the original protocol tree, where each node has a
description that contains the weight and transcript like in the original tree, and an additional
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 15
M AYA L ESHKOWITZ
range field which is initially left empty. We set the range of the root, denoted π, to be full range
π
(π) = [0β , 1β ]. If the weight of π is zero we terminate the process. Otherwise, we invoke the
Build_Tree procedure on π.
The main procedure: Build_Tree . If π’ is a leaf, the procedure returns without updat-
ing the global tree π. Otherwise, the Build_Tree procedure invokes two sub-procedures,
Build_Heavy(u) and Build_Interval(u), in order to identify and update the children of π’ in
π and place them as children of π’. Finally, the Build_Tree procedure is invoked recursively on
all the children of π’ in π.
Build_Heavy. The Build_Heavy procedure identifies the heavy descendants of π’ in π(π’),
which are descendants of large weight that have no children of large weight, and modifies the
tree by lifting them to become heavy children of π’.
Definition 4.1 (Heavy descendants). We call π£ a heavy descendant of π’ if π£ is a descendant of π’
in π and the following conditions hold:
1. π€(π£) β₯ π€(π’)/π(π)
2. Either π£ is a leaf, or for each child π§ of π£ it holds that π€(π§) < π€(π’)/π(π).
For each heavy descendant π£ of π’ we perform the following process:
1. Update π£βs description: Set the range field of π£ to be full range π
(π£) = [0β , 1β ].
2. Modify the protocol tree if π£ is not already a child of π’:
(a) Subtract π€(π£) from the weight of the ancestors of π£ in π(π’), except for π’ whose weight
stays the same.
(b) Move π£ (along with the subtree rooted at π£) so it is placed directly under π’.
See Figure 1.
Figure 1: Build_Heavy: In the first step, π£ is identified as a heavy descendant of π’ and moved to
be a heavy child of π’. In the second step, π§ is identified and moved to be a heavy child of π’. The
triangles represent subtrees of the original tree.
After we finish identifying and moving the heavy children of π’ we perform a clean up stage
where we erase all the nodes in π with weight zero.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 16
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Build_Interval(u). This procedure groups the non-heavy children of π’ under interval
children. Denote the range field of π’ by π
(π’) = [π (π’), π(π’)]. (Note that π (π’) = 0β and π(π’) = 1β
unless π’ is an interval node, in which case its range is partial.) We partition the range of π’ into a
sequence of consecutive intervals, each one representing the range of a new child of π’. As long
as we have not partitioned all of the range [π (π’), π(π’)] we perform the following procedure.
1. Determine π 0, the starting point of the interval childβs range: Initially, for the first interval
child of π’ we set π 0 = π (π’). For the next interval children, if the end of the range of the
previously created interval child is πΛ , then we set π 0 = πΛ + 1.
2. Determine π 0, the ending point of the interval childβs range: For each π β {0, 1}β , denote by
πππ_βπ ππ£ π¦(π 0 , π) the set of children of π’ in π(π’) whose weights are smaller than π€(π’)/π(π)
and their last verifier message πΌ (in the transcript field) is in the range [π 0 , π]. Note that
when [π 0 , π] β [π (π’), π(π’)] the set πππ_βπ ππ£ π¦(π 0 , π) can be a proper subset of the non-heavy
children of π’. We define the weight of the set πππ_βπ ππ£ π¦(π 0 , π), which we denote by
π(π 0 , π), as the sum of the weights of nodes in πππ_βπ ππ£ π¦(π 0 , π).
We set π 0, to be the minimal π β {0, 1}β that satisfies π(π 0 , π) β₯ π€(π’)/π(π) If no such π
exists and π(π 0 , π(π’)) > 0, we set π 0 = π(π’). If π(π 0 , π(π’)) = 0 there is no need to create
another interval child so we return to the Build_Tree procedure. (This guarantees that
the weight of an interval child is at least 1).
3. Create a new node π£: We set the transcript of π£ to be like the transcript of π’, πΎ(π£) = πΎ(π’),
its range to be π
(π£) = [π 0 , π 0] and its weight to be π€(π£) = π(π 0 , π 0).
4. Place π£ in the tree: disconnect π’ from the nodes in πππ_βπ ππ£ π¦(π 0 , π 0). Set π’ as a parent of
π£ and let π£ be the parent of all nodes that are in πππ_βπ ππ£ π¦(π 0 , π 0).
See Figure 2. Note that the weight of an interval child of π’ is at most 2π€(π’)/π(π) and at least
π€(π’)/π(π), except possibly for the last interval child, whose weight is at least 1.
Figure 2: Build_Interval: The left diagram represents the tree before the Build_Interval
procedure. The nodes to the left of the dashed line are heavy children of π’. The group of nodes
inside each dashed circle are united under an interval node. The tree on the right is the result of
applying the Build_Interval procedure.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 17
M AYA L ESHKOWITZ
4.3 Properties of the emulation tree
Recall that in the original protocol tree, π£ was a child of π’ if and only if πΎ(π£) = πΎ(π’)πΌπ½, where
πΌ, π½ β {0, 1}β denote the next verifier message and the proverβs response to it. However, in the new
emulation tree, πΈπ0 ,π0 , this is not the case. Namely, if π£ is a child of π’ in πΈπ0 ,π0 , then it could be that
π£ is a heavy child of π’ and hence πΎ(π£) = πΎ(π’)πΌ1 π½ 1 , . . . , πΌ π π½ π for some πΌ1 , π½ 1 , . . . , πΌ π , π½ π β {0, 1}β ,
or π£ is an interval child hence πΎ(π£) = πΎ(π’) and π
(π£) β π
(π’). Nevertheless, the following
properties of the final emulation tree πΈπ0 ,π0 are readily verified.
Claim 4.2 (Node degree). Each node π’ in the final emulation tree πΈπ0 ,π0 has at most π(π) children.
Proof. Note that we call Build_Tree on every node in πΈπ0 ,π0 . By definition, the weight of each
heavy child of π’ is at least π€(π’)/π(π). The weight of each interval child is also at least π€(π’)/π(π)
except for possibly the last interval child whose weight is non zero. Therefore, the number of
children is at most π(π). (If there were π(π) + 1 children or more, then the π(π) first children
would have weight of at least π€(π’)/π(π), and the last child has positive weight, which means
that in total the sum of the weights of the children is greater than π€(π’), in contradiction.)
Claim 4.3 (Weight reduction). For every node π’ in the final emulation tree πΈπ0 ,π0 the weight of each
grandchild of π’ in πΈπ0 ,π0 is at most 2π€(π’)/π(π).
Proof. Let π£ be a child of π’ in the emulation tree. First, consider the case that π£ is a heavy child
of π’. Denote by ππ’ the intermediate tree in the process of construction, after we determine the
new children of π’ and before the recursive invocations of the procedure on the children of π’. By
the definition of heavy children, the weight of each child of π£ in ππ’ is at most π€(π’)/π(π). Thus,
the weights of the children of π£ in ππ’ is also at most π€(π’)/π(π). Now, if π§ is a heavy child of π£
(i. e., heavy with respect to π€(π£)) in the final emulation tree πΈπ0 ,π0 , then it is a descendant of π£ in
ππ’ , so its weight is at most π€(π’)/π(π). Otherwise, π§ is an interval child of π£ so its weight is at
most 2π€(π£)/π(π), which is at most 2π€(π’)/π(π).
In case π£ is an interval child of π’, its weight is at most 2π€(π’)/π(π). Hence, the weight of each
grandchild of π’ which is a child of π£, is also at most 2π€(π’)/π(π).
Corollary 4.4 (Corollary to Claim 4.3)). The height of the final emulation tree πΈπ0 ,π0 is π π(π)/log π(π) .
Proof. The weight of the root of the protocol tree is at most the number of leaves in the tree,
which is 2π(π) . When we start constructing the emulation tree, the weight of the root is the same
as in the protocol tree. Moreover, the weight of a node does not change from the point that we
call Build_Tree on it. Hence, the weight of the root in πΈπ0 ,π0 is also at most 2π(π) . By Claim 4.3,
π
the weight of a node in level 2π of the emulation tree is at most 2π(π) / π(π)
2 . Taking
π = π(π)/log (π(π)/2) we get that the weight of a node in level 2π of the emulation tree is
at most 1. Lastly note that a node with weight 1 cannot have grandchildren, else by Claim 4.3
their weight is smaller than 1. This cannot happen since the weights of nodes in the emulation
tree are positive integers. We conclude that the height of the emulation tree is at most
2 Β· dπ(π)/(log(π(π)) β 1)e + 1.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 18
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Claim 4.5 (Leaves). The leaves of πΈπ0 ,π0 are exactly the leaves of protocol tree ππ0 ,π0 whose weights are
1.
Proof. The construction does not create nodes whose weights are zero. Hence, all the leaves in
πΈπ0 ,π0 have positive weight. Following the construction of the emulation tree we can see that,
during each step, the weight of a leaf from the original protocol tree stays the same, whereas the
weight of a non-leaf is the sum of the weights of the leaves that are descendants of it. Hence, a
leaf in πΈπ0 ,π0 must be a leaf in ππ0 ,π0 whose weight is 1.
On the other hand, if π£ is a leaf whose weight is 1 in ππ0 ,π0 , then π£ appears in the emulation
tree. This is because the only way nodes from the protocol tree are erased throughout the
construction is if their weight is 0 (possibly after truncations in the middle of the construction). A
leaf from ππ0 ,π0 that appears in πΈπ0 ,π0 must appear as a leaf. This is because the only way we add
descendants to a node is when we add interval children, but we do not invoke Build_Interval
on a leaf.
5 Public coin emulation
5.1 Emulation preliminaries
Next, we describe the strategy of the designated prover π and verifier π in the new protocol
(βemulationβ). The strategy of the designated prover π for a yes-instance π₯ uses the emulation
tree πΈπ0 ,π0 of π₯ constructed in the previous section. The prover assists the verifier π in
progressing down the emulation tree. On each iteration, the prover provides the descriptions
of the children π£ 1 , . . . , π£ π of the current node π’, which was sampled in the previous iteration.
The verifier performs validations on the list supplied by the prover (to be detailed below), and
then samples one of the children for the next iteration according to its weight. The verifier does
not have access to the emulation tree, and its validations consist of structural requirements on
the part of the emulation tree seen so far. On the last iteration, the verifier checks that the full
transcript, along with the sequence of coin tosses, leads the original verifier π0 to accept.
The main difference between the public coin emulation and the private coin one
is in the way a child of a node is chosen in each iteration. In the private coin
emulation, the values of the verifierβs private coin tosses determine which child is
chosen. In contrast, in the public coin emulation, π does not have private coins.
Hence, it must choose a continuation based on the transcripts and the probability
distributions suggested by π.
One of the structural validations that the verifier makes is that the nodes provided by the
prover are possibly children of π’ in the emulation tree. For nodes in the original protocol tree, π£
is possibly a child of π’ if and only if the transcript of π£ extends the transcript of π’ by one pair of
messages, and thus π£ is possibly a descendant of π’ if and only if the transcript of π’ is a proper
prefix of the transcript of π£. For nodes in the emulation tree the situation is more complex. If
the transcript of π£ equals the transcript of π’ and the range of π£ is a partial range of the range of
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 19
M AYA L ESHKOWITZ
π’, then π£ is possibly a child of π’ which the verifier regards as an interval child. If the transcript
of π’ is a proper prefix of the transcript of π£ and if πΎ(π’) = πΌ1π’ π½1π’ , . . . , πΌ π’π π½ π’π , and πΌ π£π+1 (the π + 1
verifierβs message in the transcript of π£) is in the range of π’ then π£ is possibly a child of π’, which
the verifier regards as a heavy child.
With these two cases in mind, we define the conditions required of the descriptions of two
nodes π’ and π£ in order for π£ to be a descendant (not necessarily a child) of π’ in the emulation
tree. We say that π£ is a transcript descendant of π’ if these required conditions hold.
Definition 5.1 (Transcript Descendant). Denote by π’ and π£ nodes in the emulation tree with
transcripts πΎ (π’) = πΌ1π’ π½ 1π’ , . . . , πΌ π’π π½ π’π and πΎ (π£) = πΌ1π£ π½1π£ . . . πΌ π£π π½ π£π and with range field π
(π’) and
π
(π£), respectively. We say that π£ is a transcript descendant of π’ if one of the following conditions
hold:
i πΎ(π£) = πΎ(π’) and π
(π£) β π
(π’)
ii πΎ (π’) is a proper prefix of πΎ (π£) and πΌ π£π+1 β π
(π’)
Figure 3: Truncation during Build_Tree. The node π£ is identified as a heavy descendant of π§,
so it is moved (along with the subtree that is rooted at it) to be a heavy child of π§.
It is easy to show that for every node π’ in πΈπ0 ,π0 , every descendant of π’ is a transcript
descendant of π’. The proof is similar to the proof of validation (c) in the completeness part of
the analysis.
We state the following claim regarding the transitivity property of transcript descendancy, which
we use in the analysis of the emulation.
Claim 5.2 (Transitivity). For nodes π’, π£ and π§ in the emulation tree such that π§ is a transcript descendant
of π£ and π£ is a transcript descendant of π’, π§ is a transcript descendant of π’.
Proof. Denote the length of πΎ (π’) by π. Recall that if π£ is a transcript descendant of π’ then one of
the following conditions hold:
1. πΎ(π£) = πΎ(π’) and π
(π£) β π
(π’), in this case, we say that π£ is a transcript descendant of π’ of
type (i).
2. πΎ (π’) is a proper prefix of πΎ (π£) and πΌ π£π+1 β π
(π’), in this case, we say that π£ is a transcript
descendant of π’ of type (ii).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 20
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
We proceed by case analysis according to the descendancy types between π’, π£ and π§ and show
that in each case π§ is a transcript descendant of π’.
β’ If π§ is a transcript descendant of π£ of type (i) and π£ is a transcript descendant of π’ of type
(i) then πΎ (π’) = πΎ (π£) = πΎ (π§), and π
(π§) β π
(π£) β π
(π’), so π§ is a transcript descendant of π’
of type (i).
β’ If π§ is a transcript descendant of π£ of type (i) and π£ is a transcript descendant of π’ of type
(ii) then πΎ(π’) is a proper prefix of πΎ(π£) = πΎ(π§). Since the transcripts of π£ and π§ are equal it
follows that πΌ π§π+1 = πΌ π£π+1 . Because πΌ π£π+1 β π
(π’) we get that πΌ π§π+1 β π
(π’), so π§ is a transcript
descendant of π’ of type (ii).
β’ If π§ is a transcript descendant of π£ of type (ii) and π£ is a transcript descendant of π’ of type
(i) then πΎ(π£) is a proper prefix of πΎ(π§) and πΎ(π’) = πΎ(π£), so πΎ(π’) is a proper prefix of πΎ(π§).
Furthermore, πΌ π§π+1 β π
(π£) β π
(π’) so π§ is a transcript descendant of π’ of type (ii).
β’ If π§ is a transcript descendant of π£ of type (ii) and π£ is a transcript descendant of π’ of type
(ii) then πΎ(π’) is a proper prefix of πΎ(π§). Furthermore, because the transcript of π£ is a prefix
of the transcript of π§ then πΌ π§π+1 = πΌ π£π+1 . Since π£ is a transcript descendant of π’ of type (ii),
we know that πΌ π£π+1 β π
(π’) and so πΌ π§π+1 β π
(π’). Hence, π§ is a transcript descendant of π’ of
type (ii).
The condition of π£ being a transcript descendant of π’ is not sufficient to guarantee that π£ is
possibly a descendant of π’ in the emulation tree πΈπ0 ,π0 . For example, suppose that π£ was a child
of π’ in ππ0 ,π0 , and is a heavy descendant of a node π§ that is an ancestor of π’ in πΈπ0 ,π0 . Then, π£
becomes a heavy child of π§ in πΈπ0 ,π0 , which means that the subtree rooted at π£ was truncated
and moved up to be a direct descendant of π§. Therefore, in order to check if π£ is possibly a legal
descendant of π’ in the emulation tree, the verifier needs to check that π£ does not belong to a
part of the tree that was truncated and moved to a different part of the emulation tree (such
as nodes π£ and π€ in Figure 3). For this reason, the verifier keeps a seen-list π of nodes that
were seen during the emulation, and updates the list at every iteration with the new nodes seen.
Note that the nodes in π(π’), which the verifier sees up to the iteration that the input node is
π’, are a subtree of the emulation tree that is composed of a path from the root of the tree to π’,
augmented with the children of the nodes in the path. See Figure 4.
Another structural validation requires the transcripts that the verifier sees during the
execution to be consistent with a deterministic prover strategy.
Definition 5.3 (Prover consistent). We say that two transcripts πΎ(π’) and πΎ(π£) are prover consistent
if the maximal prefix they agree on is either empty or ends with a proverβs message. That is, the
prover should respond in the same way on the same prefix of the transcripts (i. e., for every π
smaller or equal to the length of the shorter transcript, if (πΌ1π’ π½ 1π’ , . . . , πΌ π’π ) = (πΌ 1π£ π½ 1π£ , . . . , πΌ π£π ) then
π½ π’π = π½ π£π ).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 21
M AYA L ESHKOWITZ
Figure 4: The nodes in the seen-list, π, in the iteration that the input node is π’.
This condition will allow for extracting a proverβs strategy for the original protocol from the
transcripts in πΈπ0 ,π0 , and then to claim that since the original prover cannot fool the verifier with
high probability, the new prover cannot either.
We stress that we give an honest-prover centric description of the emulation protocol. This
means that Step 1 describes the intended behaviour from an honest prover to provide the
descriptions of the heavy children. A dishonest prover may deviate from this step, and the
purpose of the verifierβs checks to see that even if there was a deviation the prover can not
succeed in claiming that a no-instance is a yes-instance with high probability.
5.2 Emulation construction
Initially, for the first iteration, the transcript of the root π is the empty transcript and the range
is full, [0β , 1β ]. The prover provides the weight of the root π and the verifier checks that the
claimed weight is at least 9/10 Β· 2π(π) . The verifier adds the description of π to the seen-list π
(which is initially empty). The rest of the first iteration, as well as subsequent iterations, proceed
as follows.
Construction 5.4. (the πth iteration) On input a non-leaf node π’ and seen-list π.
1. The prover provides the descriptions of the children π£ 1 , . . . , π£ π of π’:
(πΎ (π£ 1 ) , π
(π£ 1 ) , π€(π£ 1 )) , . . . , (πΎ (π£ π ) , π
(π£ π ) , π€(π£ π ))
2. The verifier performs the following validations and rejects if any of them fails:
(a) The verifier checks that all nodes are different (according to their descriptions). That
is, for each distinct π, π β [π], if πΎ(π£ π ) = πΎ(π£ π ), then π
(π£ π ) β π
(π£ π ).
(b) The verifier checks that the weights of the children of π’ sum up to π€(π’); that is,
π
Γ
π€(π’) = π€(π£ π ) (5.1)
π=1
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 22
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
(c) For each π β [π], the verifier checks that π£ π is a transcript descendant of π’.
(d) For each interval child π£ π , the verifier checks that πΎ π£ π = πΎ(π’); that is, if π
π£ π β
[0β , 1β ], then πΎ π£ π = πΎ(π’) must hold.
(e) For each π β [π], the verifier checks that π£ π is not in a part of the emulation tree that
was truncated. (See discussion following Definition 5.1.) Specifically, for π£ β π then
if π£ is a transcript descendant of π’, then π£ π should not be a transcript descendant of π£.
For illustration consider Figure 3, where π’, π‘, π§, π£ β π. In that case, the verifier checks
that π£ π is not a transcript descendant of π£, where π£ is a transcript descendant of π’
since it was a descendant of π’ in the original protocol tree. (In particular, π£ π should
not be equal to π€ shown in the figure.)
(Note that it can be that π£ π is a transcript descendant of some node in π that is not a
transcript descendant of π’, and this is not considered a violation. For example, all
the nodes are transcript descendants of the root π, which is in π.)
(f) The verifier checks that the ranges of all the interval children are disjoint; that is, for
every two interval children π£ π and π£ π , the verifier checks that π
π£ π β© π
(π£ π ) = β
.
(g) For each π β [π] the verifier checks that πΎ(π£ π ) is prover consistent (see Definition 5.3)
with respect to the other transcripts of nodes in π and with regarding to the transcripts
of the other children πΎ(π£ π ), where π β π.
3. The verifier chooses a child according to the probability distribution π½ that assigns each
π β [π] probability approximately proportional to π€(π£ π ) using π(log π(π)) coin tosses. That
is, π½ is such that
π€(π£ π )
1
Pr [π½ = π] β€ Γπ Β· 1+ (5.1)
π(π)
π=1 π€(π£ π )
We can only afford to use π(log π(π)) public coins per iteration since the height of the
em-
ulation tree, and hence the number of iterations of the emulation, is π π(π)/log π(π) and
we want the total number of public coins to be π(π(π)). Hence, we compromise on
sampling each child with probability proportional to π€(π£ π ), and instead sample with
approximate probability. See the explanation for approximate sampling in Subsection 5.4.
4. The verifier adds all the children of π’ to the seen-list π; that is π β π βͺ {π£1 , . . . , π£ π }.
Denote by π the index the verifier choose in 3. Unless πΎ(π£ π ) is the complete transcript
(which contains the last message), the next iteration will start with node π£ π and the set π.
Otherwise, we proceed to the final checks.
By our conventions, the last message the verifier π0 sends, denoted πΌ π , contains the
outcomes π β {0, 1} π(π) of the π(π) coins tossed. Thus, if the last node chosen is π£, then π can be
easily extracted from πΎ (π£) = πΌ1 π½ 1 , . . . , πΌ π π½ π . After the last iteration, the verifier performs final
checks and accepts if all of them hold:
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 23
M AYA L ESHKOWITZ
(i) Check that π is accepting for πΎ (π£) and consistent with it: It checks that π0 (π₯, π, π½ 1 , . . . , π½ π ) =
1, and that for every π = 1, . . . , π it holds that πΌ π = π0 (π₯, π, π½1 , . . . , π½ πβ1 ). Note that the
verifier needs π in order to verify these conditions, so this check can only be done after the
last iteration.
(ii) Check that π€(π£) = 1; in other words the proverβs last claim should be that the weight of
the last node chosen is 1 (and not more than 1).
5.3 The number of rounds and randomness complexity
Clearly, the number of iterations (and hence rounds) of the emulation is π π(π)/log π(π) because
the height of the emulation tree is π π(π)/log π(π) , and the prover and verifier proceed one
step down the tree in each iteration. Since the verifier uses π(log π(π)) public coins in each
iteration, the randomness complexity of the emulation is π(π(π)).
5.4 Approximate sampling
Let π· = (π 1 , . . . , π π ) be the probability distribution that assigns each π β [π] probability
proportional to π€(π£ π ); that is, π π = π€(π£ π )/ ππ=1 π€(π£ π ). Our goal is to approximate the probability
Γ
distribution π· with a probability distribution π½ = (π 10 , . . . , π 0π ) in the sense that for each π β [π]
it holds that π 0π β€ π π Β· (1 + 1/π(π)). Moreover, the probability distribution π½ should be one
that the verifier can sample from using π = π log π(π) coin tosses. Note that our method of
approximation also satisfies π 0π > π π β 1/(π(π))3 for every π β [π], although the lower bound is
not used in our work.
Let π β β such that 2 πβ1 < (π(π))3 β€ 2 π . Assume, without loss of generality, that π π is the
largest probability and thus π π β₯ 1/π β₯ 1/π(π). For π < π define π 0π by rounding down π π to the
closest integer multiple of 2βπ , whereas we add the residual probability mass to π 0π . That is,
( bπ Β·2π c
π
2π
for π < π
π 0π = Γπβ1 bπ π Β·2π c
1β π=1 2π
for π = π
Clearly for π < π it holds that π 0π β€ π π . For π = π,
πβ1
Γ bπ π Β· 2 π c
π 0π = 1 β
π=1
2π
πβ1
Γ π π Β· 2π β 1
β€ 1β
π=1
2π
πβ1
Γ
=1β π π + (π β 1) Β· 2βπ . (5.2)
π=1
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 24
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Recall that the number of children the prover supplies, π, is upper bounded by π(π), and
that 2βπ β€ (π(π))β3 . Thus,
(π β 1) Β· 2βπ β€ π(π) Β· (π(π))β3 = (π(π))β2 . (5.3)
Because π· is a probability distribution we get that π π = 1 β πβ1 π=1 π π and so plugging Eq. (5.3)
Γ
in Eq. (5.2) we get that π π β€ π π + 1/(π(π)) .
0 2
Using the fact that π π β₯ 1/π(π) it follows that 1/(π(π))2 β€ π π /π(π) and hence
π 0π β€ π π Β· (1 + 1/π(π))
6 Analysis of the emulation
We show that the interactive proof system is transformed by the emulation protocol of Con-
struction 5.4, which uses the emulation tree πΈπ0 ,π0 constructed in Section 4.2, into a public coin
interactive proof system with perfect completeness and soundness 1/3.
6.1 Completeness
We claim that the emulation protocol of Construction 5.4 has perfect completeness. That is, if π₯
is a yes-instance, then π will accept at the end of the interaction with π.
Recall that π builds an emulation tree πΈπ0 ,π0 from the protocol tree ππ0 ,π0 . Since π₯ is a
yes-instance at least 9/10 Β· 2π(π) of the coin tosses lead the verifier to accept and hence the weight
of the root of ππ0 ,π0 is at least 9/10 Β· 2π(π) . The weight of the root does not change during the
construction of the emulation tree. Thus, the weight of the root of πΈπ0 ,π0 is at least 9/10 Β· 2π(π) as
well. Hence, π can make a valid initial claim of weight at least 9/10 Β· 2π(π)
Next, we wish to show that the validations on Step 2 are satisfied for every iteration. This is
equivalent to showing that validations are satisfied for every node in the final emulation tree
πΈπ0 ,π0 . The general framework of the proof consists of going over every validation performed
and showing that the property being checked holds for every node in the original protocol
tree ππ0 ,π0 , and continues to hold with every modification of the tree as part of the Build_Tree
procedure.
We denote by πππ£0 ,π0 the tree during construction, after the step that π£ is identified either as
a heavy child, or created as an interval child in the tree. We can list the intermediate trees
according to the order the nodes are placed starting from the root π and until the protocol tree is
transformed to an emulation tree: πΏ =ππ0 ,π0 = πππ0 ,π0 , πππ’01,π0 , . . . , πππ’0π,π0 = πΈπ0 ,π0 . For every tree in
this list, we show that for every node π’ in the tree the validations when π’ is the input node of
the iteration pass. Therefore, it will follow that the validations also pass for every node in the
final emulation tree πΈπ0 ,π0 .
When we say that a validation passes relative to a (possibly intermediate) tree πππ§0 ,π0 and node
π’ in πππ§0 ,π0 , we mean that if the tree πππ§0 ,π0 had been used as an emulation tree then in the iteration
which π’ is the input node, the validation would have passed. Note that possibly the degree
of π’ in πππ§0 ,π0 is not polynomial in π, and hence we can not use πππ§0 ,π0 to define the emulation
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 25
M AYA L ESHKOWITZ
protocol, since the verifier should run in polynomial time. However, we can still prove that each
validation passes for the intermediate trees assuming that the verifier was not polynomially
bounded. Recall that the nodes in πππ§0 ,π0 , on which we did not invoke the Build_Tree procedure
yet, do not have a range field. We regard the nodes that do not have a range field as having a
full range [0β , 1β ].
Let πππ§0 ,π0 be an intermediate tree from the list above, created when assigning the node π§
(either as an interval child or heavy child) as part of the Build_Tree procedure. We assume
that the validation we are currently checking holds for every node in πππ§0 ,π0 , and show that it
also holds in the next step of the construction, that is the next tree in the list πΏ. Recall that the
next step can either be identifying a heavy child for π§ as part of the Build_Heavy procedure,
or creating an interval child for π§ as part of the Build_Interval procedure. Denote the child
being created or identified by π£, and the intermediate tree after this modification by πππ£0 ,π0 .
Note that, it is not sufficient to show that after the creation or identification of π£, the property
being checked is maintained for π£. This is because the procedure might affect the descendants
and ancestors of π£ in πππ£0 ,π0 , as well as nodes whose seen-list changes. Exactly which nodes are
affected depends on the validation.
Remark 6.1. Let π£ be a node in some tree πππ§0 ,π0 that the Build_Tree procedure has not been
invoked on yet. Recall that the children of π£ in πππ§0 ,π0 are children of the node π£ 0 in ππ0 ,π0 that
satisfies πΎ(π£ 0) = πΎ(π£). Hence, like in the tree ππ0 ,π0 , the transcripts of the children of π£ in
πππ§0 ,π0 extend the transcript of π£ by one pair of messages. Furthermore, if we did not invoke
Build_Tree on π£ yet, then we also did not invoke it on the descendants of π£ in πππ§0 ,π0 . Thus, the
subtree of πππ§0 ,π0 rooted at π£, denoted by πππ§0 ,π0 (π£), is a subtree of ππ0 ,π0 . (This is true up to the
point that π£ might be an interval node and thus not in ππ0 ,π0 . In this case changing just the node
π£ to the node π£ 0 defined above we get a subtree of ππ0 ,π0 .)
Now, we go over the validations in Step 2 , which are stated for a node π’ and its children
π£ 1 , . . . , π£ π provided by the prover as part of the emulation. The validations are numbered as in
Construction 5.4. Assuming that the validations hold for every node in πππ§0 ,π0 , we shall prove
that these validations hold for every node in πππ£0 ,π0 (the next intermediate tree in the list).
Showing that the validations in Step 2 of the public coin emulation are satisfied
is similar in spirit to the proof that the validations in Step 2 of the private coin
emulation are satisfied, which is given in Subsection A.4.1.
(a) In this validation, the verifier checks that the descriptions of all the children of π’ are
distinct, i. e., if π£ π and
π£ π are two children of π’ provided by the prover and πΎ (π£ π ) = πΎ π£ π
then π
(π£ π ) β π
π£ π .
First, note that in ππ0 ,π0 all the nodes have distinct transcripts, and in particular for every
node all of its children have distinct descriptions. Let πππ£0 ,π0 be an intermediate tree in the
list. We assume that this validation passes for all the trees prior to πππ£0 ,π0 in the list and we
show it also holds in πππ£0 ,π0 . Denote the parent of π£ in πππ£0 ,π0 by π§. The only node in πππ£0 ,π0
that may have new children relative to the ones in the proceeding tree in the list πΏ is π§,
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 26
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
and hence from the assumption, it sufficed to show that the validation holds for π§. If π£
is an interval child of π§ then its description is distinct from the other children of π§ since
the ranges of the interval children are distinct. If π£ is determined as a heavy child of π§,
then it is a descendant of π§ in πππ§0 ,π0 . By Remark 6.1, πππ§0 ,π0 (π§) is a subtree of ππ0 ,π0 . Hence,
each node in πππ§0 ,π0 (π§) has a different description. All the heavy children of π§ in πππ£0 ,π0 are
in πππ§0 ,π0 (π§), and hence they have distinct descriptions. To conclude note that the heavy
children have full range, and interval children have partial range, and hence in particular
the heavy and interval children of π§ are distinct from each other.
(b) In this validation the verifier checks that the weights of the children π£ 1 , . . . , π£ π of π’ sum
up to π€(π’); that is,
π
Γ
π€(π’) = π€(π£ π ) (6.1)
π=1
We shall show that this property holds in every step of the construction of the emulation
tree πΈπ0 ,π0 , for every node in the tree. Starting from the protocol tree ππ0 ,π0 , we know that
by definition it satisfies the property that the weight of each node is the sum of the weights
of its children. (Recall that π§ is a node that we are invoking the Build_Tree procedure
on, and π£ is a node that we determine as a child for π§.) Assuming that Eq. (6.1) holds
for every node in πππ§0 ,π0 , we shall show that it holds for every node in πππ£0 ,π0 as well. We
consider two cases, according to if π£ is a heavy child or interval child of π§. (Recall that
these are the only cases since after invoking Build_Tree(z) every child of π§ is either a
heavy or interval child.)
β’ If π£ is a new heavy child determined for π§, denote by π§, π§1 , . . . , π§ π = π£ the path from
π§ to π£ in πππ§0 ,π0 (π§) before π£ is moved to be a child of π§. In this case, after moving π£ we
subtract π€(π£) off the weight of π§ 1 , . . . , π§ πβ1 . Hence, Eq. (6.1) holds for these nodes (we
subtract π€(π£) both from their weight and from the weight of one of their children).
Eq. (6.1) also holds for π§, since its weight stays the same because we subtract π€(π£) off
the weight of π§ 1 , and we add an additional child π£ with weight π€(π£). For the other
nodes in πππ£0 ,π0 we neither change their weight nor the weights of their children.
β’ If π£ is a new interval child of π§, then the weight of π£ is the sum of the weights of its
children. Eq. (6.1) also holds for π§ since its weight stays the same and the sum of the
weights of its children also stays the same, this is also true of all the other nodes in
πππ£0 ,π0 .
Lastly, we note that the clean-up stage, in which we remove nodes whose weights are 0,
does not affect this validation.
(c) In this validation, for each π β [π], the verifier checks that the child π£ π provided by the
prover is a transcript descendant of π’.
Recall that we consider nodes in the protocol tree that do not have a range field (yet) as
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 27
M AYA L ESHKOWITZ
having a full range. In the protocol tree ππ0 ,π0 the transcript of each node is a proper
prefix of the transcript of its children. Hence, every node in the protocol tree is a transcript
descendant of type ii (see Definition 5.1) of its parent. As before, we shall assume that
every node in πππ§0 ,π0 maintains the property that it is a transcript descendant of its parent,
and show that this property is maintained in the tree πππ£0 ,π0 , after the assignment of π£ as a
child of π§. We only need to show this validation holds for π§, which possibly has a new
child π£, and for π£ itself, which might not have been a node in πππ§0 ,π0 . The property holds
for all the other nodes in πππ£0 ,π0 from our assumption on πππ§0 ,π0 . We consider two cases:
β’ If π£ is a heavy child of π§, then π£ was a descendant of π§ in πππ§0 ,π0 that we move to be
a child of π§ (along with its descendants) and set its range to be full range. By our
assumption, each node in the path from π§ to π£ in πππ§0 ,π0 is a transcript descendant of
its parent, so by transitivity (see Claim 5.2), π£ is a transcript descendant of π§.
β’ If π£ is an interval child of π§ then after the creation of π£ the transcript of π£ is equal to
the transcript of π§, and by the construction we know that π
(π’) β π
(π§). Thus, π£ is a
transcript descendant of π§ of type i.
In addition, the children of π£ in πππ£0 ,π0 are transcript descendants of π£. This is because
the children of π£ are all children of π§ in πππ§0 ,π0 , such that their next verifier message is
in the range of π£. Hence, the children of π£ are transcript descendants of type ii of π£ .
(d) In this validation the verifier checks, for each interval child π£ π of π’, that the transcript of π£ π
is equal to the transcript of π’; that is, if π
π£ π β [0β , 1β ] then πΎ π£ π = πΎ (π’) must hold.
β β
This holds because the only case where π
π£ π β [0 , 1 ] is if π£ π is an interval child of π’, and
in this case πΎ π£ π = πΎ (π’) because of how we create interval children. Note that once we
create an interval child in some intermediate tree it stays a child of its parent throughout
the subsequent tree transformations, and hence also in the final emulation tree.
(e) In this validation the verifier checks, for each child π£ π of π’, that π£ π is not in a part of
the emulation tree that was truncated. For every π¦ β π, the verifier checks that if π¦ is a
transcript descendant of π’, then π£ π should not be a transcript descendant of π¦. Note that if
π¦ is a transcript descendant of π’ then by validation (c) we know that π¦ is not an ancestor
of π’.
In order to show that the validation is satisfied, we shall first define the notation of seen-list
of a node, and then prove that the following claim holds for every node in the emulation
tree πΈπ0 ,π0 .
Definition 6.2 (Seen-list of a node.). When we consider a tree π that is not the final
emulation tree, and a node π£ β π, then we regard the seen-list of π£, denoted by π(π£), as the
list containing the nodes that are ancestors of π£, augmented with their children.
Claim 6.3. Let π’ β πΈπ0 ,π0 and π¦ β π(π’) that is not an ancestor of π’ in πΈπ0 ,π0 . If π¦ is a transcript
descendant of π’, then each descendant π£ π of π’ in πΈπ0 ,π0 is not a transcript descendant of π¦.
Note this is a stronger claim then what we need to show because we only need to show it
for the children of π’ in πΈπ0 ,π0 and not for each descendant of π’.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 28
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
First, we shall show that the claim holds in the initial protocol tree ππ0 ,π0 . Each node in
ππ0 ,π0 is a transcript descendant only of its ancestors in the tree. However, each node π’ is
not an ancestor of any node in π(π’), so the nodes in π(π’) cannot be transcript descendants
of π’. Thus, the claim holds vacuously. Next, we shall assume that the claim holds in the
tree πππ§0 ,π0 before creating a child π£ of π§, and we show that it holds in the tree πππ£0 ,π0 after
the identification π£ as a heavy child of π§, or creation of π£ as an interval child.
β’ If π£ is identified as a heavy descendant of π§, then π£ is moved to be a child of π§ along
with the subtree under it. In order to show that the claim holds in πππ£0 ,π0 , it is enough
to consider the nodes π β πππ£0 ,π0 who have new descendants or new nodes in π(π)
relative to the ones they had in πππ§0 ,π0 . The descendants of the nodes in πππ£0 ,π0 are
descendants of it in πππ§0 ,π0 . The only nodes in πππ£0 ,π0 that have new nodes in their
seen-list are the descendants of π§, since now π£ is in their seen-list, whereas π£ may not
have been in their seen-list before the move. Determining the heavy descendants of π§
is done by searching the tree from bottom to top (this is implied by the definition
of heavy descendants, 4.1). It follows that the ancestors of π£ in πππ§0 ,π0 which are
transcript descendants of π§ have not been identified as heavy descendants of π§ (or
any other node) at this point yet, and so in πππ§0 ,π0 the node π£ is only a transcript
descendant of its ancestors. Thus, if π is a node in πππ£0 ,π0 such that π£ β π(π) and π£ is a
transcript descendant of π, then π is an ancestor of π£ in πππ§0 ,π0 . It is left to check that
the descendants of π in πππ£0 ,π0 are not transcript descendants of π£. From Note 6.1, it
follows that the subtree of πππ£0 ,π0 rooted at π, denoted by πππ£0 ,π0 (π), is a subtree of ππ0 ,π0 .
Thus, because π£ β πππ£0 ,π0 (π) (recall that π£ was lifted to be a heavy child of π§, and π is a
descendant of π§) it follows that the descendants of π are not transcript descendants of
π£. (See Figure 5.)
( ) ( )
0, 0 0, 0
z z
v
c c
v
Figure 5: π£ is identified as a heavy child of π§, and π is a descendant of π§.
β’ Let π£ be an interval child created for π§. We shall assume that the claim holds in the
tree πππ§0 ,π0 before the assignment of π£, and show that it holds in πππ£0 ,π0 . It is enough
to show that the claim holds when the node π’ is one of the following: either a new
interval child π£ or a node in πππ£0 ,π0 that has new descendants or a node in πππ£0 ,π0 that
has new nodes in their seen-list (relative to the ones in πππ§0 ,π0 ). (For the other nodes in
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 29
M AYA L ESHKOWITZ
πππ£0 ,π0 the claim follows from our assumption regarding πππ§0 ,π0 .)
The only nodes in πππ£0 ,π0 that have new descendants that they did not have in πππ§0 ,π0
are the ancestors of π£ in πππ£0 ,π0 , which now have π£ as their descendant. Let π be some
ancestor of π£ in πππ£0 ,π0 , and let π β π(π) be a transcript descendant of π. We need to
show that π£ is not a transcript descendant of π. We know that π£ has children in πππ£0 ,π0
otherwise it would not been created as an interval node, so let π‘ be a child of π£ in
πππ£0 ,π0 (see Figure 6). It follows that π‘ is a transcript descendant of π£. Assume by
contradiction that π£ is a transcript descendant of π. Hence, by transitivity, π‘ is also
transcript descendants of π. In addition, π‘ is a descendant of π in πππ§0 ,π0 . This is in
contradiction to our hypothesis that the claim holds in πππ§0 ,π0 .
( ) ( )
0, 0 0, 0
d c d c
z z
t y v y
Figure 6: π£ is an interval child created by uniting 3 children of π§.
The nodes whose seen-list π increases in πππ£0 ,π0 relative to πππ§0 ,π0 are the descendants
of π§, because π£ is added to their list. However, π£ cannot be a transcript descendant of
any descendant of π§. This is because the heavy children of π§ have longer transcripts
than π£, so π£ cannot be a transcript descendant of them, or of their descendants (this
follows from validation 2c and transitivity). The other interval children of π§ have a
range that is disjoint from the range of π£. Thus, they and their descendants cannot be
transcript descendants of π£.
Lastly, we show that the claim holds for π£ as well. Let there be a some node π β π(π£)
which is a transcript descendant of π£. We need to show that the descendants of π£ in
πππ£0 ,π0 are not transcript descendants of π. There are two different options.
β Either π β π(π§) in πππ§0 ,π0 , like node π in Figure 6. The node π is a transcript
descendant of π£ which is a transcript descendant of π§, so by transitivity π is a
transcript descendant of π§. Every descendant of π£ in πππ£0 ,π0 is a descendant of π§ in
ππ0 ,π0 z. Hence, from the fact that the claim is true for π§ in πππ§0 ,π0 we know that the
descendants of π£ in πππ£0 ,π0 are not transcript descendants of π.
β If π β π(π£) but π β π(π§) then π must be a child of π§, like node π¦ in Figure 6. Since
π is a transcript descendant of π£ then π must be a heavy child of π§. (If π is an
interval child of π§, like π£ is, then π cannot be a transcript descendant of π£ since
their ranges are disjoint.) We did not invoke Build_Tree on π£ yet, so by Note 6.1,
it follows that πππ£0 ,π0 (π£) is a subtree of ππ0 ,π0 . Hence, from the fact that π is not in
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 30
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
πππ£0 ,π0 (π£) it follows that the transcript descendants of π are not in πππ£0 ,π0 (π£) either.
In other words, the descendants of π£ in πππ£0 ,π0 are not transcript descendants of π.
(f) In this validation, the verifier checks that the ranges of all the interval children of π’ are
that is, for every two interval children π£ π and π£ π of π’, the verifier checks that
disjoint;
π
π£ π β© π
(π£ π ) = β
.
By the way we create the interval children it holds that the start of the range of each
interval child is after the end of the range of the previous child created.
(g) In this validation, the verifier checks, for each child π£ π of π’, that πΎ(π£ π ) is prover consistent
(see Definition 5.3) with respect to the other transcripts of nodes in π(π’) and with regarding
to the transcripts of the other children of π’.
In the original protocol tree, ππ0 ,π0 , every two nodes are prover consistent since π0 is
deterministic. (If there were two partial transcripts in ππ0 ,π0 whose maximal common
prefix ends with a verifier message it would mean that the prover can responds in different
ways to the same partial transcripts.) The transcripts of the nodes in πΈπ0 ,π0 all appear in
ππ0 ,π0 , so every two transcripts in πΈπ0 ,π0 are prover consistent as well.
The final checks are satisfied because according to Claim 4.5 the leaves of the emulation tree
πΈπ0 ,π0 are the leaves of the protocol tree whose weights are 1. Hence, π0 (π₯, π, πΌ1 , . . . , πΌ π ) = 1,
and for every π = 1, . . . , π it holds that πΌ π = π0 (π₯, π, π½ 1 , . . . , π½ πβ1 ). In addition π€(π£) = 1.
6.2 Soundness
We show that if π₯ is a no-instance, then when interacting with any prover π e for the public coin
emulation protocol, the new public coin verifier π accepts with probability at most 1/3. We do
so by showing that on each iteration there is a gap (in expectation) between the weight of the
node claimed by the prover, and the actual weight of the node. Starting from the root, if π₯ is a
no-instance, then the initial proverβs claim is that the weight of the node sampled should be
at least 9/10 Β· 2π(π) (or else the verifier rejects upfront), but the number of coin sequences that
lead the verifier to accept at the end of the interaction, and hence the actual weight of the node,
is at most 1/10 Β· 2π(π) . We want to show that this gap is approximately maintained with high
probability at least until the last iteration, and hence the verifier rejects.
In order to proceed with this analysis, we need to define the notion of βactual weight of a
nodeβ in the emulation tree. We do this by considering the weight relative to the protocol tree of
the original interactive proof system. The verifier of the original protocol system which we refer
to is of course π0 , the verifier of the original proof system being emulated. However, choosing
the prover of the original system is less straightforward. We shall show that a proverβs strategy
for the emulation protocol yields a prover strategy for the original protocol.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 31
M AYA L ESHKOWITZ
Subsection 6.2.1 is a more involved version of the private coin proof of soundness
in Section A.4.2. The other two components of the soundness analysis of the
public coin system (which define the notion of actual weight of a node, and bound
the gap between the claimed and actual weight) are not required for the private
coin soundness analysis.
6.2.1 Deriving a prover strategy for the original proof system
We can assume without loss of generality that π e is deterministic since for every probabilistic
prover there is a deterministic prover for which the verifierβs acceptance probability is at least
as high. (Recall that we want to show that the verifier rejects with high probability. Hence, it
suffices to take a deterministic prover which the verifier rejects with lower probability when
interacting with, and showing that this probability is still high enough).
We can also assume, without loss of generality, that the strategy of π e is such that the verifier
does not abort until the final checks. This is because every prover strategy in which the verifier
aborts in one of the intermediate checks can be modified to a prover strategy such that the
verifier does not abort until the final checks and the verifierβs acceptance probability is at least
as large. (The prover can compute the transcripts of the children such that they are different
continuations of their parent and prover consistent with the list π instead of every node where
the verifier would have aborted in the intermediate checks.) Since π e is deterministic and the
verifier doesnβt abort until the final checks, the proverβs strategy can be represented using an
emulation tree which we denote by πΈπe.
We show that we can extract a deterministic strategy πe0 for the original prover using the
strategy of π.e We define a strategy for πe0 by using the transcripts in πΈ e. That is, for each
π
π’ β πΈπe with transcript πΎ (π’) = πΌ1 π½ 1 . . . , πΌ π π½ π we define πe0 (π₯, πΌ 1 , . . . , πΌ π ) B π½ π for all π β€ π. We
extend πe0 βs strategy to transcripts that do not appear in πΈπe in an arbitrary way.
In order to show that the strategy of πe0 is well defined we need to show that no two nodes
π’, π£ β πΈπe share the prefix of prover-verifier interaction but differ on the proverβs response. That
is, we show that every two nodes π’, π£ β πΈπe are prover consistent (see Definition 5.3).
For a node π’ β πΈπe provided during the emulation, recall that we denote by π (π’) the seen-list
(see Definition 6.2) the list of nodes from πΈπe at the beginning of the iteration in which π’ was
the input node (i. e., was the node handled on that iteration). That is, the nodes in π(π’) are the
ancestors of π’ in πΈπe and their children.
To show that every two nodes π’, π£ β πΈπe are prover consistent, as well as for other parts of
the soundness proof, we rely on the following claim.
Claim 6.4 (Transcript descendancy forms a tree). Let π€ β πΈπe and π’, π§ β π(π€). Assume that the
strategy of π
e is such that the verifier does not abort until the final checks. Let β be a node with a range and
a transcript field that is a transcript descendant of both π§ and π’. Then either π’ is a transcript descendant
of π§ or π§ is a transcript descendant of π’.
Proof. First, note that this claim is not true if the proverβs strategy is not one in which the verifier
does not abort until the final checks. For example, if β is a transcript descendant of type (i)
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 32
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
of both π’ and π§, then πΎ (π’) = πΎ (π§) = πΎ (β ), and π
(β ) is contained in both π
(π’) and in π
(π§).
However, π
(π’) and π
(π§) may not be contained one in the other, and hence π’ is not a transcript
descendant of π§ and π§ is not a transcript descendant of π’.
Since β is a transcript descendant of π’ and of π§, then both πΎ (π’) and πΎ (π§) are prefixes of πΎ (β ).
Assume, without loss of generality, that |πΎ (π§)| β₯ |πΎ (π’)|. It follows that πΎ (π’) is a prefix of πΎ (π§).
(See Figure 7.)
Figure 7: The transcripts of π’,π§ and β when |πΎ (π§)| β₯ |πΎ (π’)|
The first case is that πΎ (π’) is a strict prefix of πΎ (π§). In this case πΎ (π’) is also a strict prefix of
πΎ (β ) and hence β is a transcript descendant of type (ii) of π’ . Denote the transcripts of π’ and π§ by
πΎ (π’) = πΌ1 π½1 . . . πΌ π π½ π and πΎ (π§) = πΌ 1 π½1 . . . πΌ π π½ π , for π > π. For an index π and a node π’ denote by
πΌ π’π the πth verifierβs message in the transcript of π’. Because πΎ (π§) is a prefix of πΎ (β ) it follows
that πΌ π§π+1 = πΌβπ+1 . From the fact that β is a transcript descendant of type (ii) of π’ we know that
πΌβπ+1 β π
(π’). Thus, πΌ π§π+1 β π
(π’) and πΎ (π’) is a strict prefix of πΎ(π§), so π§ is a transcript descendant
of π’ (of type (ii)).
The second case is that the transcripts of π’ and π§ are equal; that is, πΎ (π’) = πΎ (π§) = πΌ1 π½ 1 . . . πΌ π π½ π .
In this case we need to show that π
(π’) β π
(π§) or π
(π§) β π
(π’). If π
(π’) = 0β , 1β then
π
(π§) β π
(π’), so π§ is a transcript descendant of π’ of type (i). Similarly, if π
(π§) = 0β , 1β then π’
is a transcript descendant of π§ of type (i).
We are left with the case that πΎ(π’) = πΎ(π§) and both π’ and π§ do not have a full range. In this
part we consider the relation between π’ and π§ in πΈπe. Recall that π(π€) contains the nodes in the
path from the root to π€, augmented with their children.
Denote the least common ancestor of π’ and π§ in πΈπe by π£. If π£ = π’ then there is a path from
π£ to π§. Since validation 2c passes for every node in πΈπe, each node in the path is a transcript
descendant of its predecessor, so from transitivity π§ is a transcript descendant of π£. Similarly, if
π£ = π§ then π’ is a transcript descendant of π§.
Otherwise, π£ is neither equal to π’ nor to π§. However, at least one of the nodes π’ or π§ is a
child of π£ in πΈπe (because of the structure of π(π€), see Figure 8 for illustration). Assume, without
loss of generality, that π§ is a child of π£. The range of π§ is not full so π§ must be an interval child
of π£ and πΎ(π£) = πΎ(π§). It follows that πΎ(π’) = πΎ(π£) so π’ is either another interval child of π£ or
a descendant of an interval child of π£. Thus, the ranges of π’ and π§ are disjoint because they
belong to different branches of interval children of π£, and the ranges of the interval children are
disjoint from validation 2f. This is in contradiction to the assumption in the claim that πΎ(β ) is a
transcript descendant of both πΎ(π’) and πΎ(π§). To see why this is a contradiction consider two
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 33
M AYA L ESHKOWITZ
Figure 8: π§ and π’ are two nodes in π(π€) whose least common ancestor is π£.
cases. If πΎ(β ) = πΎ(π’) = πΎ(π§) then β is a transcript descendant of type (i) of both π’ and π§ and
hence π
(β ) β π
(π’) and π
(β ) β π
(π§), and so π
(π’) and π
(π§) cannot be disjoint. If πΎ(π’) = πΎ(π§) are
strict prefixes of πΎ(β ) then β is a transcript descendant of π’ and π§ of type (ii). Hence, πΌβπ+1 β π
(π’)
and πΌβπ+1 β π
(π§), so also in this case π
(π’) and π
(π§) cannot be disjoint.
We are ready to prove the prover consistency property of the emulation tree.
Note that the following proof is a more involved version of the proof of Lemma A.9
in Section A.4.
Lemma 6.5 (Prover consistency of the emulation tree). If the strategy of the prover π e for the new
emulation is such that the verifier π does not abort until the final checks then every two transcripts of
nodes in the emulation tree πΈπe are prover consistent.
Proof. Let π’ and π£ be two nodes in the emulation tree πΈπe, we wish to show that their transcripts
πΎ(π’) and πΎ(π£) are prover-consistent. If one of the nodes is a descendant of the other node in the
emulation tree, with out loss of generality, we assume that π£ is a descendant of π’. We denote by
π0(π£) the seen-list of the parent of π£. That is, if π’ is the parent of π£ in πΈπe then π0(π£) = π(π’). In
the general case that π£ is a descendant of π’ then π’ β π0(π£) and validation 2g is satisfied so πΎ(π’)
and πΎ(π£) are prover-consistent. Otherwise, denote by π§ the least common ancestor of π’ and π£,
and π and π the children of π§ that are ancestors of π’ and π£ respectively. (It is possible that π = π’
or π = π£.) See Figure 9 for illustration.
Consider the case that at least one of the transcripts of π’ and π£ equals the transcript of π
or π, respectively (this also covers the case that π’ or π£ are children of π§). Assume, without
loss of generality, that πΎ(π) = πΎ(π’). We know that πΎ(π£) and πΎ(π) are prover consistent, because
π β π0(π£) and validation 2g is satisfied. (If π£ = π then π β π0(π£) but then πΎ(π£) and πΎ(π) are prover
consistent also from validation 2g because they are both children of π§.) Hence, πΎ(π£) and πΎ(π’)
are also prover consistent.
Otherwise, πΎ(π) is a proper prefix of πΎ(π’), and πΎ(π) is a proper prefix of πΎ(π£). We consider
three cases according to the relation between πΎ(π) and πΎ(π).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 34
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Figure 9: The subtree of πΈπe that contains π’ and π£
First, consider the case that πΎ(π) is not a prefix of πΎ(π) and πΎ(π) is not a prefix of πΎ(π). It
follows that the maximal prefix on which πΎ(π) and πΎ(π) agree upon is a proper prefix of both.
This common prefix equals the maximal prefix on which πΎ(π’) and πΎ(π£) agree. We know that
πΎ(π) and πΎ(π) are prover-consistent because the prover provides π along with π as children of π§
and we assume that validation 2g is satisfied. Since the maximal prefix that πΎ(π’) and πΎ(π£) agree
on is equal to the maximal prefix that πΎ(π) and πΎ(π) agree on, it follows that πΎ(π£) and πΎ(π’) are
also prover-consistent. See Figure 10 for illustration.
Figure 10: πΎ(π) and πΎ(π) agree on the prefix in white, while πΎ(π) is a prefix of πΎ(π’) and πΎ(π) is a
prefix of πΎ(π£).
Next, consider the case when πΎ(π) = πΎ(π), and assume that the transcript of π and π contain
messages from π rounds. In this case both π and π are interval children of π§. This is because at
least one of them needs to have a partial transcript, otherwise validation 2a would be violated.
Assume without loss of generality that π has a partial transcript. Because π has a partial
transcript, from validation 2d the transcript of π§ is equal to the transcript of π and π, and
the range of π§ is full. Hence, if the range of π is full then the description of π and π§ are the
same, and in particular π is not a transcript descendant of π§, which violates validation 2c. We
have established that π and π are interval children of π§ and from validation 2f it follows that
π
(π) β© π
(π) = β
. Note that π’ is a transcript descendant of π, and π£ is a transcript descendant of π
of type ii, since the transcripts πΎ(π) and πΎ(π) are proper prefixes of πΎ(π’) and πΎ(π£) respectively.
As a result, πΌ π£π+1 β π
(π) and πΌ π’π+1 β π
(π). It follows that πΌ π£π+1 β πΌ π’π+1 , which means that the
maximal prefix that πΎ(π’) and πΎ(π£) agree on is equal to πΎ(π) = πΎ(π). Hence, the maximal prefix
ends with a prover message and so πΎ(π’) and πΎ(π£) are prover consistent.
We are left with the case that one of the transcripts πΎ(π) and πΎ(π) is a proper prefix of the
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 35
M AYA L ESHKOWITZ
other, and assume, without loss of generality, that πΎ(π) is a proper prefix of πΎ(π). Denote the
transcript of π by πΎ(π) = πΌ1 π½1 , . . . , πΌ π π½ π . Since πΎ(π) is a proper prefix of πΎ(π), and πΎ(π§) is a prefix
of both πΎ(π) and πΎ(π) (since they are transcript descendants of π§) it follows that πΎ(π) β πΎ(π§) and
so π is not an interval child of π§ by validation 2d and hence π
(π) = [0β , 1β ].
We claim that π’ is not a transcript descendant of π. Assume, by contradiction, that π’
is a transcript descendant of π. Note that π is not a transcript descendant of π, since we
assumed that πΎ(π) is a proper prefix of πΎ(π). Denote the nodes in the path from π to π’ in
πΈπe by π = π 0 , π1 , . . . , π π = π’ and by π π the first node in the path such that π π is not a transcript
descendant of π and π π+1 is a transcript descendant of π. Since π π+1 is a transcript descendant of
both π π and π, which are in π(π π+1 ), and since π π is not a transcript descendant of π, it follows by
Claim 6.4 that π is a transcript descendant of π π (see Figure 11). Hence, in the iteration where
the prover provides node π π+1 as a child of π π there is a violation to validation 2e, because π π+1 is
a transcript descendant of π β π(π π ) and π is a transcript descendant of π π . Put differently, π π+1 is
part of a truncation from π π . Hence, we reached a contradiction to the hypothesis that π does
not abort in the intermediate validations, and so π’ cannot be a transcript descendant of π.
Figure 11: The dashed arrow pointing from π to π π+1 represent the fact that π π+1 is a transcript
descendant of π, and similarly that π is a transcript descendant of π π .
We showed that π’ is not a transcript descendant of π and π
(π) = [0β , 1β ], so πΎ(π) is not a
prefix of πΎ(π’). (If πΎ(π) is a proper prefix of πΎ(π’) then π’ is a transcript descendant of π of type ii
since π
(π) = [0β , 1β ], whereas if πΎ(π) = πΎ(π’) then π
(π’) β [0β , 1β ] = π
(π), which means that π’ is a
transcript descendant of type i of π.) Let π’ 0 be the parent of π’ in πΈπe. We know that π β π(π’ 0)
because π is a child of π§, which is an ancestor of π’ 0. Hence, by validation 2g the transcript of
π’, which is a child of π’ 0 and the transcript of π β π(π’ 0) are prover consistent. It follows that
the maximal common prefix of πΎ(π’) and πΎ(π) is a proper prefix of πΎ(π) that ends with a prover
message.
Lastly, note that from validation 2c each node in the path from π to π£ is a transcript descendant
of its parent, so from transitivity π£ is a transcript descendant of π. Thus, πΎ(π) is a prefix of
πΎ(π£). It follows that the maximal common prefix of πΎ(π£) and πΎ(π’) is contained in the maximal
common prefix of πΎ(π’) and πΎ(π), so it ends with a prover message (See Figure 12).
6.2.2 Actual weight of a node in πΈπe
We want to introduce the notion of the βactual weightβ of a node in πΈπe. This βactual weightβ
should be proportional to the probability that the node represents a partial interaction of the
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 36
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Figure 12: The maximal common prefix between πΎ(π’) and πΎ(π) appears in white. Since πΎ(π) is a
prefix of πΎ(π£) the maximal common prefix of πΎ(π’) and πΎ(π£) is the same as the former.
verifier π0 with the prover πe0 , which was extracted in the previous subsection, and that this
partial interaction leads π0 to accept. Hence, it is natural to use the weights in πf
π0 ,π0 for this
value. However, the weights in πf π0 ,π0 do not reflect the truncations the prover πmakes, and so
e
they are not specific to the emulation tree and the way which it was constructed. Thus, we
also need to use the tree πΈπe, which contains the information about the truncations. Another
difficulty that arises is that the nodes in πf π0 ,π0 are only heavy nodes. Hence, instead of using
the weight of a node in πf π0 ,π0 we consider the number of leaves whose weights are 1 and are
transcript descendants of it.
Definition 6.6 (Actual weight of π’ β πΈπe relative to protocol tree πf π0 ,π0 ). For a node π’ β πΈπ
e denote
by πΏ (π’) the set of leaves in πf
1
π0 ,π0 that are transcript descendants of π’ and whose weight is 1.
(The definition of transcript descendants relates to nodes that have a transcript and range field,
so we consider the nodes in πf β β
π0 ,π0 as if they have full range [0 , 1 ].)
Denote by πππ’ππ (π’) the non-ancestors of π’ in π (π’) (relative to the emulation tree πΈπ0 ,π0 ) that
are transcript descendants of π’. (In particular, π’ β πππ’ππ(π’).)
We define πΏπ (π’) as
e
ο£±
 à 

π
ο£² 1
 

πΏ (π’) = πΏ (π’) πΏ (π§)
1
e
π§βπππ’ππ(π’)

 

ο£³ ο£Ύ
We define the actual weight of π’, denoted by π π (π’), to be the size of the set πΏπ (π’). That is,
e e
π π (π’) = πΏπ (π’)
e e
For the soundness proof, we use the following claim regarding the actual weight of a node
in the emulation tree πΈπe, which asserts that the actual weight of a node is at least as large as the
sum of the weights of its children.
Claim 6.7. Assume that the strategy of the prover π e is such that the verifier does not abort until the final
checks. Let π’ β πΈπe and π£ 1 , . . . , π£ π children of π’ in πΈπe. Then
π
Γ
π π (π£ π ) β€ π π (π’) .
e e
π=1
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 37
M AYA L ESHKOWITZ
Proof. The proof follows from the following two facts:
Fact 6.8. For each distinct π, π β [π], it holds that πΏπ (π£ π ) β© πΏπ (π£ π ) = β
.
e e
Fact 6.9. For each π β [π], it holds that πΏπ (π£ π ) β πΏπ (π’).
e e
We start with the proof of Fact 6.8. Consider two different cases. The first case is if π£ π and
π£ π are not transcript descendants of each other (π£ π is not a transcript descendant of π£ π and vice
versa). If β β πΏπ (π£ π ), then β is a transcript descendant of π£ π . Assume by contradiction that
e
β β πΏπ (π£ π ). Hence, β is also a transcript descendant of π£ π , and π£ π and π£ π are in π(π£ π ). From
e
Claim 6.4 one of π£ π and π£ π is a transcript descendant of the other, in contradiction to the our
assumption for this case.
The second case is that π£ π (respectively π£ π ) is a transcript descendant of π£ π (respectively
π£ π ). Without loss of generality, assume that π£ π is a transcript descendant of π£ π . In this case
π£ π β πππ’ππ (π£ π ), since π£ π β π(π£ π ) and π£ π is not an ancestor of π£ π . From the fact that β β πΏπ (π£ π ) it
e
follows that β β πΏ1 π£ π . By the definition of πΏπ the leaves in πΏ1 (π£ π ) are removed from the set
e
πΏπ (π£ π ), and hence β β πΏπ (π£ π ). This completes the proof of Fact 6.8.
e e
Turning to the proof of Fact 6.9, let β β πΏπ (π£ π ). Therefore, the leaf β is a transcript descendant
e
of π£ π . From validation 2c it follows that π£ π is a transcript descendant of π’. Therefore, by
transitivity, β is a transcript descendant of π’ so β β πΏ1 (π’). Assume by contradiction that there
exists π§ β πππ’ππ (π’) such that β β πΏ1 (π§) and hence β β πΏπ (π’). Recall that π§ β πππ’ππ(π’) means
e
that π§ is a transcript descendant of π’ and π§ β π(π’) (See Figure 13). This also means that π§ β π(π£ π )
since π(π’) β π(π£ π ). It follows that β is a transcript descendant of both π§ and π£ π which are in π(π£ π ).
Hence, from Claim 6.4 there are two options:
β’ The first option is that π£ π is a transcript descendant of π§. However, this cannot happen
since in the iteration where π’ is the input node, by validation 2e it cannot be that π£ π is a
transcript descendant of π§ β π(π’) and π§ is a transcript descendant of π’.
β’ The second option is that π§ is a transcript descendant of
π£ π . This cannot be the case because
π§ β π(π’) implies that π§ β π π£ π and so π§ β πππ’ππ π£ π . But because β β πΏ (π§) we get that
1
β β πΏπ (π£ π ), in contradiction to our hypothesis.
e
Figure 13: The emulation tree after π§ has been truncated and moved to be a chid of π.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 38
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Thus, we reach a contradiction in both options, so in particular there does not exist
π§ β πππ’ππ(π’) such that β β πΏ1 (π§). Hence, β β πΏπ (π’).
e
6.2.3 Bounding the gap
Next, we define the gap between the actual weight and the claimed weight, which we use for
the analysis.
Definition 6.10 (Gaps). The gap for node π’ β πΈπe denoted by π(π’), is the ratio between π π (π’),
e
the actual weight of node π’ according to the strategy of π,
e and the claimed weight π€ 0(π’).
π (π’) = π π (π’)/π€ 0(π’)
e
Note that we can assume without loss of generality that π€ 0(π’) > 0 since the prover can omit
the nodes with claimed weight equal to 0.
Let π£ be a node chosen on the πth iteration of a random execution of the emulation protocol
by π
e and π. We denote the value of the gap on the πth iteration by π π = π (π£), and by π0 the value
of the gap of the root π.
We consider the π 0 iteration emulation protocol defined in Construction 5.4, and fix an
iteration π β [π 0] as well as the values of the coin tosses, denoted by π1 , . . . , π πβ1 , obtained during
the emulation of the first π β 1 iterations. Denote by π’ the node sampled on iteration π β 1. If
π = 1 then π’ is the root of the emulation tree. The description of the node π’ and π πβ1 = π (π’) are
fixed. Denote by πΊ π the random variable that represents π π at the end of the πth iteration, which
depends on the child of π’ chosen on the πth iteration. Towards proving Claim 6.11 below, we
analyze the change in the gap on the πth iteration, and show that it does not increase too much
in expectation.
Claim 6.11. Consider a prover strategy for the proposed public coin emulation in which the verifier does
not abort until the final checks. For any sequence of values of the coin tosses π1 , . . . , π πβ1 , it holds that
πΌππ [πΊ π | π1 , . . . , π πβ1 ] β€ π πβ1 Β· (1 + 1/π(π))
Proof. Let π£ 1 , . . . , π£ π be the children of π’, that were provided by the prover in the emulation.
Since πΊ π is the gap after the πth iteration, its value dependents on the child of π’ that was chosen
π
Γ
πΌ [πΊ π | π1 , . . . , π πβ1 ] = Pr π£ π chosen Β· π π£ π .
(6.2)
π=1
By the definition of the gap for node π£ π ,
π π (π£ π )
e
π π£π =
. (6.3)
π€ 0(π£ π )
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 39
M AYA L ESHKOWITZ
According to Step 3 of the emulation protocol,
π€ 0(π£ π )
Pr π£ π chosen β€ Γπ
Β· (1 + 1/π(π)) . (6.4)
π=1 π€ 0 (π£ )
π
Plugging in Eq. (6.3) and Eq. (6.4) in Eq. (6.2) we have
π
π€ 0(π£ π ) π π (π£ π )
Γ e
πΌ [πΊ π | π1 , . . . , π πβ1 ] β€ Β· (1 + 1/π(π)) Β·
π€ 0(π£ π )
Γπ
π=1 π€ (π£ π )
0
π=1
π
π π (π£ π )
Γ e
= Γπ Β· (1 + 1/π(π)) . (6.5)
π=1 π€ (π£ π )
0
π=1
From validation 2b it holds that
π
Γ
π€ 0(π’) = π€ 0(π£ π ) . (6.6)
π=1
Hence, combining Eq. (6.6) and Claim 6.7 in Eq. (6.5) we get
π π (π’)
e
πΌ [πΊ π | π1 , . . . , π πβ1 ] β€ Β· (1 + 1/π(π))
π€ 0(π’)
= π (π’) Β· (1 + 1/π(π)) = π πβ1 Β· (1 + 1/π(π)) .
The claim follows.
6.2.4 Concluding the soundness proof
Denote by π the root of the protocol tree. Recall that π π (π’) is defined based on the protocol
e
tree πf
π0 ,π0 of a prover π0 and verifier π0 for the original interactive proof of π₯. Hence, for the
e
root of the protocol tree π we know that π π (π) is bounded above by the number of leaves with
e
weight 1 in πf
π0 ,π0 , which is the number of sequences of coin tosses that lead the verifier to accept
π₯. Thus, if π₯ is a no-instance, then π π (π) β€ 1/10 Β· 2π(π) . Hence, if the prover claims that some
e
no-instance is a yes-instance, then at the beginning of the emulation π€ 0(π) β₯ 9/10 Β· 2π(π) whereas
π π (π) β€ 1/10 Β· 2π(π) , thus π0 β€ 1/9. Denote by π£ the leaf sampled at the end of the emulation. If
e
the verifier accepts the complete emulation, then (in particular) the final checks pass and so
π π (π£) = π€ 0(π£) = 1 and so π π0 = π (π£) = π π (π£)/π€ 0(π£) = 1.
e e
Therefore, in order to upper bound the probability that the verifier accepts, it suffices to
upper bound the probability that the gap after the last iteration, πΊ π0 , is greater than or equal to
1. Clearly,
Pr [πΊ π0 β₯ 1] β€ πΌ [πΊ π0 ] .
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 40
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
From Claim 6.11 we know that for every sequence of coin tosses π1 , . . . , π πβ1 that determine π πβ1
πΌππ [πΊ π | π1 , . . . , π πβ1 ] β€ π πβ1 Β· (1 + 1/π(π)) .
Hence,
πΌπ1 ,...,ππ [πΊ π ] β€ (1 + 1/π(π)) Β· πΌπ1 ,...,ππβ1 [πΊ πβ1 ] . (6.7)
Applying the bound from Eq. (6.7) iteratively it follows that
πΌπ1 ,...,ππ0 [πΊ π0 ] β€ (1 + 1/π(π))π Β· π0 .
0
From property 4.4, the height of the emulation tree and hence the number of iterations of the
new emulation is at most π 0 = 2 Β· dπ(π)/log π(π)e + 1. For π β₯ 8 the value of π 0 is at most π(π)
and thus,
πΌπ1 ,...,ππ0 [πΊ π0 ] β€ (1 + 1/π(π))π(π) Β· π0
β€ e Β· π0 < 1/3 .
where the last equality follows from the fact that π0 β€ 1/9. Hence, the verifier accepts with
probability of at most 1/3.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 41
M AYA L ESHKOWITZ
Appendix A Private coin emulation
In the following appendix, we prove a weaker version of the main theorem, which gives an
upper-bound on the round complexity in terms of the randomness complexity, for private
coin interactive proof systems. The point in doing so is that the proof is significantly simpler.
Moreover, we can use this weaker version as a component of an alternative proof of the main
theorem, which we show in Appendix B.
Theorem A.1. Suppose that π has an interactive proof system of randomness complexity π(π) for instances
of length π. Then, π has a private coin interactive proof system of round complexity π(π(π)/log π(π))
and randomness complexity π(π). Furthermore, the soundness and completeness of the original interactive
proof system are preserved.
This appendix can also be read independently from the proof of the main theorem. The
general structure of the proof is similar to the one of the main theorem. In Section A.1 we
describe the protocol tree of the original proof system. The protocol tree is used to construct
an emulation tree in Section A.2. In Section A.3 we describe the private coin emulation, which
uses the emulation tree constructed in the previous section. The analysis of the private coin
emulation is performed in Section (A.4).
We provide notes that point out the main differences and similarities between the
private and public coin emulation protocols. These notes are typeset as this one.
A.1 The protocol tree of the original proof system
Note that the protocol tree for the public coin emulation described in Section 3 is
similar to the one described here, except for the definition of weights.
Fixing an interactive proof between prover π and verifier π and an instance π₯ of length π, we
describe the possible prover-verifier interactions of the system on common input π₯ using a tree
ππ,π whose height corresponds to the number of rounds of interaction. For some β = β (π), we
assume without loss of generality that in each iteration the verifier sends a message πΌ β {0, 1}β ,
and the proverβs responds with a message π½ β {0, 1}β . We can also assume, without loss of
generality, that the proverβs strategy is deterministic and fixed. Each node π£ in level π represents
a possible prover-verifier transcript for the first π rounds of the interaction. The branching of
ππ,π represents the possible ways to extend the transcript to the next round. The number of
ways to extend the transcript depends only on the verifierβs message, since we fixed the proverβs
strategy. Hence, each node has at most π· B 2β children, corresponding to the 2β possible verifier
messages for the next round. The proverβs response to each such message is included in the
description of the corresponding node.
The description of a node π’ on level π contains the partial transcript πΎ (π’) = πΌ1 π½ 1 , . . . , πΌ π π½ π
of the interaction up to the πβth round. The root (at level zero) has an empty transcript, whereas
a leaf of ππ,π represents a complete prover-verifier interaction. We can assume, without loss
of generality, that the verifier sends its private coins on the last round, and hence every leaf is
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 42
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
associated with a sequence of coin tosses which either leads the verifier to accept or to reject.
Hence, we can represent the possible interactions generated by the interactive proof system
using a tree ππ,π of height π that has 2π(π) leaves, where π is the number of rounds and π(π) is
the number of coin tosses.
The description of a node also contains its weight, denoted π€(π’). The weight of the node is
the number of coin sequences that are consistent with the node and lead the verifier to accept at
the end of the interaction. That is,
Definition A.2 (Weight of a leaf). The weight of a leaf is defined to be 1. Recall that a leaf π’
corresponds to a full transcript of the interaction of π and π on input π₯, when π uses a sequence
of coin tosses π.
Definition A.3 (Weight of a node). The weight of a node π’ in the protocol tree ππ,π is the sum
of the weights of the leaves that are descendants of π’.
Note that the weight of node in ππ,π , which corresponds to a possibly partial transcript, is
proportional to the probability that a sequence of coin tosses is consistent with that transcript.
In the public coin emulation, the weight of a leaf is defined as 1 if the verifier
accepts at the end of the interaction, otherwise the weight is 0. Hence, in the
public coin emulation the weight of the node is the number of coin sequences that
are consistent with the corresponding transcript and lead the verifier to accept at
the end of the interaction.
A.2 The emulation tree
Using the protocol tree ππ0 ,π0 , we create a new tree of height π π(π)/log π(π) to guide the
proverβs strategy. We call this tree the emulation tree and we denote it by πΈπ0 ,π0 . The nodes in
πΈπ0 ,π0 are nodes from ππ0 ,π0 , however the children of a node π’ in πΈπ0 ,π0 may be non-immediate
descendants of π’ in ππ0 ,π0 .
The procedure for constructing the private coin emulation tree πΈπ0 ,π0 is similar
to the one described for the the main public coin emulation, provided that the
degree of ππ0 ,π0 is πππ π¦(π). In the foregoing private coin emulation we only care
about the height of πΈπ0 ,π0 , and we do not mind if the degree of the tree is not
polynomially bounded. Hence, unlike in the public coin emulation, we do not
group the nodes under interval children in order to reduce the degree.
The Build_Tree procedure is a recursive procedure that reads and updates a tree π, which is
initially set to equal the protocol tree ππ0 ,π0 , until obtaining the final emulation tree πΈπ0 ,π0 . We
start with a protocol tree ππ0 ,π0 rooted at π’ whose weight is π€(π’) = 2π(π) , and on each step we
modify this tree towards creating πΈπ0 ,π0 . We define a heavy descendant of π’ in π to be a node in
π whose weight is at least π€(π’)
π(π)
, such that this descendant is either a leaf, or the weight of each of
its children is smaller than π€(π’)
π(π)
. Note that there are at most π(π) such nodes.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 43
M AYA L ESHKOWITZ
We modify π so that the children of π’ in the emulation tree are its original children as well as
the heavy descendants that we lift upwards to make them new children of π’. This modification
is performed using the Build_Tree(u) procedure, which when invoked on a node π’ identifies
the nodes that will be children of π’ in the new tree, sets them as children of π’, and then initiates
recursive invocations on the (original and new) children of π’, creating the new emulation tree
rooted at π’. Details follow.
Let ππ’ denote the intermediate tree after the stage that we identify the heavy descendants of
π’ and raise them to be children of π’. The Build_Tree(u) procedure begins by identifying a
heavy descendant π£ of π’ (π£ can also be a child of π’ in π), which will become a heavy child of π’
in ππ’ . We move π£ to be a direct child of π’, along with the subtree rooted at π£ (see Figure 14). We
update the weights of the ancestors of π£ that are descendants of π’ by subtracting π€(π£) off their
weight. We then proceed to the next heavy descendant of π’. When we finish identifying all the
heavy children, the children of π’ in ππ’ consist of the heavy children of π’ along with the original
children of π’ in π. Next, we erase any nodes whose weights are 0 from the tree. The weight of
a descendant of π’ may become zero, for example, if all its children were identified as heavy
descendants of π’.
Figure 14: In the first step, π£ is identified as a heavy descendant of π’ and moved to be a heavy
child of π’. In the second step, π§ is identified and moved to be a heavy child of π’. The triangles
represent subtrees of the original tree.
Lastly, we invoke the Build_Tree procedure on each child of π’ in ππ’ , which creates an
emulation tree rooted at that node.
Observe that in the final emulation tree, for each node π’, the weight of each grandchild of π’ is
at most π€(π’)
π(π)
. If π£ is a heavy child of π’ in the emulation tree, then the weight of each descendants
of π£ in ππ’ is at most π€(π’)
π(π)
. Since the children of π£ in the emulation tree are descendants of π£ in ππ’
the claim holds. Otherwise, π£ is a non-heavy child of π’, so its weight is smaller than π€(π’)
π(π)
and
hence the weight of the children of π£ is also smaller than π€(π’)
π(π)
.
π(π)
It follows that the weight of a node in level 2π(π)/log π(π) is at most (π(π))2π(π)/log π(π) = 1. Recall
that we perform a clean up stage to delete nodes with weight equal to zero, and hence we
guarantee that the weights of all the nodes in the emulation tree are positive integers. It follows
that the height of the final emulation tree is π π(π)/log π(π) . We note that the number of
heavy children of each node is at most π(π), whereas the number of non-heavy children may be
exponential in π.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 44
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
A.3 Emulation protocol
A.3.1 Protocol preliminaries
Next, we describe the strategy of the designated prover π and verifier π in the new protocol
(βemulationβ). Denote the designated prover and verifier of the original proof system by π0 and
π0 respectively, and by πΈπ0 ,π0 the emulation tree constructed in the previous subsection. The
verifier π does not have access to the emulation tree, but it has access to the original verifier
π0 strategy. The emulation starts with the verifier sampling private coins π β {0, 1} π(π) . Starting
from the root of the emulation tree, in each iteration, the prover and the verifier progress one
step down the emulation tree, until reaching a leaf that represents a possible complete transcript
of the original interaction.
The main difference between the public coin emulation and the private coin one
is in the way a child of a node is chosen in each iteration. In the public coin
emulation π does not have private coins, hence it must choose a continuation
based on the transcripts and the probability distributions suggested by π. In
contrast, in the foregoing emulation the values of the verifierβs private coin tosses
determine which child is chosen.
In each iteration, the prover should provide the transcripts of the heavy children π£1 , . . . , π£ π
of the current node π’, which was reached in the previous iteration. The verifier performs
validations on the list supplied by the prover (to be detailed below), and aborts if any of these
validations fail. If one of the transcripts provided by the prover is consistent with the verifierβs
private coins, then the verifier chooses this transcript, and the next iteration proceeds from this
heavy child. Otherwise, the verifier sends its next message, according to the strategy of π0 and
to the values of its private coins π. The prover then answers with its response to the verifierβs
message. In this case, the continuation of the transcript corresponds to one of the non-heavy
children of π’ in the emulation tree. Towards the next iteration, the prover and verifier proceed
from the new node. On the last iteration, the verifier checks that the full transcript, along with
the sequence of coin tosses, leads the original verifier π0 to accept.
The validations that the verifier performs are meant to ensure that the transcripts that the
prover provides for the new emulation are consistent with a deterministic prover strategy for
the original interactive proof system. In such a case, we can claim that, since the original prover
cannot fool the verifier with high probability, the new prover cannot do so either.
Definition A.4 (Prover consistent). We say that two transcripts πΎ(π’) and πΎ(π£) are prover
consistent if the maximal prefix they agree on is either empty or ends with a proverβs message.
That is, the prover should respond in the same way on the same prefix of the transcripts.
The verifier is able to check prover consistency only between previous transcripts seen so
far in the emulation. For this reason, the verifier keeps a seen-list π of the nodes that were
seen during the emulation, and at each iteration, it checks prover consistency between the new
transcripts and the transcripts of the nodes in π.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 45
M AYA L ESHKOWITZ
Note that the nodes in π, which the verifier has seen up to some iteration, are a subtree of
the emulation tree that consists of a path from the root of the tree to the current input node,
augmented with the children of the nodes on the path. See Figure 15.
Figure 15: The nodes in the seen-list, π, in the iteration that the input node is π’.
We want to claim that all the transcripts in the emulation tree of an untrusted prover are
prover consistent, whereas the verifier can only check the prover consistency between the
transcripts of the seen nodes, which consist of a very partial portion of the emulation tree. In
order to guarantee that consistency between the nodes in π is enough to ensure that all the
transcripts in the emulation tree are prover consistent, we add additional validations that check
the structure of the emulation tree. The goal of these checks is to make sure that the emulation
tree was constructed using a protocol tree where the only changes done to the protocol tree are
"raising" parts of the tree (as done with the heavy children in the designated construction).
A.3.2 Protocol construction
We stress that we give an honest prover centric description of the emulation protocol. This
means that Step 1 describes the intended behaviour from an honest prover to provide the
transcripts of the heavy children. A dishonest prover may deviate from this description, and
the purpose of the verifierβs checks to see that even if there was a deviation the prover can not
succeed in claiming that a no-instance is a yes-instance with high probability.
Initially, for the first iteration, the verifier samples its private coins π β {0, 1} π(π) . The input
node is the root. The verifier sets the seen-list π to contain the transcript of the root, which is the
empty string. The rest of the first iteration, as well as subsequent iterations, proceed as follows.
Construction A.5. (the πth iteration) On input a node π’ and seen-list π.
1. The prover provides the transcripts of the heavy children π£ 1 , . . . , π£ π of π’: πΎ(π£ 1 ), . . . , πΎ(π£ π ).
2. The verifier performs the following validations and rejects if any of them fails:
(a) For each π β [π] the verifier checks that πΎ(π’) is a proper prefix of πΎ(π£ π ).
(b) For each π β [π] the verifier checks that the transcript πΎ(π£ π ) is prover consistent with
the other transcripts in π and with the other transcripts πΎ(π£ π ).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 46
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
(c) For each π β [π] the verifier checks that πΎ(π£ π ) is not part of the emulation tree that
was truncated from πΎ(π’); that is, if πΎ(π’) is a proper prefix of a transcript e πΎ β π, then
πΎ should not be a prefix of πΎ(π£ π ). (Note that this also implies that πΎ(π£ π ) is different
e
from the other transcripts in π.)
(d) The verifier checks that all the nodes are different (according to their transcripts),
that is, for each distinct π, π β [π] the verifier checks that πΎ(π£ π ) β πΎ(π£ π ).
3. The verifier checks if any of the transcripts the prover provided are consistent with the
values of its private coins π, where a transcript πΎ π = πΌ1 π½ 1 , . . . , πΌ π π½ π is consistent with a
sequence of private coins π, if for every π β [π] it holds that π0 (π₯, π, π½ 1 , . . . , π½ πβ1 ) = πΌ π .
There are two options according to whether or not there exists a suggested transcript that
is consistent with π.
(a) If there exists a transcript that is consistent with π, the verifier sends the prover the
maximal transcript πΎ(π£ π ) that is consistent with its coins. The prover and the verifier
update the input node π’ for the next iteration to be π£ π . The verifier updates the set π
of seen transcripts π β π βͺ {πΎ(π£ 1 ), . . . , πΎ(π£ π )}.
(b) Otherwise, the verifier sends its next message πΌ according to the value of its private
coins π. That is, if the current transcript is πΎ(π’) = πΌ 1 π½ 1 , . . . , πΌ π π½ π , then the verifier
sends πΌ such that π0 (π₯, π, π½1 , . . . , π½ π ) = πΌ. The prover answers with a message π½ such
that πΎ(π’)πΌπ½ is a transcript of a child of π’ in the emulation tree. (The assumption
that there exists such a child in the emulation tree is justified in the completeness
part of the analysis.) The verifier updates the set π of seen transcripts; that is,
π β π βͺ {πΎ(π£ 1 ), . . . , πΎ(π£ π ), πΎ(π’)πΌπ½}. Towards the next iteration the prover and the
verifier update the input node for the next iteration to be the node in the emulation
tree whose transcript is πΎ(π’)πΌπ½.
Unless πΎ(π’) is the complete transcript (which contains the last message), the next iteration will
start with transcript πΎ(π’) and the set π. Otherwise, we proceed to the final checks.
Final check. After the complete transcript πΎ = πΌ 1 π½ 1 , . . . , πΌ π π½ π has been determined, the
verifier π accepts if and only if π is accepting for πΎ; that is, if π0 (π₯, π, π½1 , . . . , π½ π ) = 1.
A.3.3 Number of rounds
In the proposed emulation each iteration consists of a prover message in Step 1, followed by a
verifier message in Step 3, and then possibly another prover message in Step 3b. Hence, each
iteration takes two rounds of communication. However, we can augment the last prover message
in Step 3b with the prover message in Step 1 of the next iteration. Thus, the number of rounds
of communication is the number of iterations of the emulation protocol plus one. The number
of iterations is equal to the height of the emulation tree, which is equal to π π(π)/log π(π) .
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 47
M AYA L ESHKOWITZ
A.4 Proof of correctness
A.4.1 Completeness
We claim that if π₯ is a yes-instance, then the new verifier π accepts with probability at least π(π),
the completeness parameter of the original interactive proof system. The proof of completeness
is partitioned into three parts. First, we shall show that the strategy of honest prover π, as
specified in Subsection A.3, is indeed well defined; specifically, we shall show that if the verifier
does not choose one of the continuations suggested by the prover, but rather sends its next
message according to the value of its coin tosses, then there is an unique node in the emulation
tree that corresponds to the new transcript. Next, we show that the strategy of π is such that
π does not abort until the final check. Finally, we show that this implies that the probability
that π accepts at the end of the interaction with π is equal to the probability that π0 accepts at
the end of the interaction with π0 , which is at least π(π).
The proverβs strategy is well defined. We begin by showing that the strategy of π in Step 3b
is well defined. That is, we have to show that if the verifier does not choose one of the suggested
continuations of π’ provided by the prover, but rather sends its next message πΌ in Step 3b
according to the value of its coin tosses π, then π’ has an unique child in the emulation tree
πΈπ0 ,π0 whose transcript is πΎ(π’)πΌπ½ for some π½ β {0, 1}β .
Let π½ be the message π0 sends in response to the transcript πΎ(π’)πΌ. All the nodes in
πΈπ0 ,π0 appear in ππ0 ,π0 , and thus all the transcripts must be consistent with the strategy of π0 .
Thus, every transcript in πΈπ0 ,π0 whose prefix is πΎ(π’)πΌ must proceed with π½. Note that π’ cannot
have two children whose transcripts are πΎ(π’)πΌπ½ since all the transcripts in ππ0 ,π0 are distinct,
and the same must hold in πΈπ0 ,π0 . The reason that π’ has a child whose transcript is πΎ(π’)πΌπ½ is as
follows. We know that continuations of πΎ(π’) that are consistent with the values of πβs private
coin tosses were not suggested by the prover π in this iteration or a previous one, otherwise
π would have chosen this continuation and not have reached π’. Hence, πΎ(π’)πΌπ½ was not raised
to be a heavy child of an ancestor of π’, and hence it is a child of π’ in πΈπ0 ,π0 . Similarly, the leaf
whose transcript is the complete interaction with private coins π was not not raised to be a heavy
child of π’ or of its ancestors, and hence it is a descendant of πΎ(π’)πΌπ½ in πΈπ0 ,π0 . Thus, the weight
of the node whose transcript is πΎ(π’)πΌπ½ is non-zero, so it was not erased from the tree, and it is a
child of π’.
The validations in Step 2 are satisfied. We shall show that the validations in Step 2 are
satisfied in every iteration. This is equivalent to showing that validations are satisfied for every
non-leaf node π’ in the final emulation tree πΈπ0 ,π0 , in the iteration that π’ was the input node (i. e.,
the node handled on that iteration).
Showing that the validations in Step 2 are satisfied is a simplified version of the
completeness proof of the public coin protocol, which is given in Subsection 6.1.
The general framework of the proof consists of going over every validation performed, and
showing that the property being checked holds for every node in the original protocol tree ππ0 ,π0 ,
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 48
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
and continues to hold with every modification of the tree as part of the Build_Tree procedure.
We denote by πππ£0 ,π0 the tree during construction, after π£ is identified as a heavy child and placed
as a child of π§ in the tree. We can list the intermediate trees according to the order the nodes are
identified starting from the root π and until the protocol tree is transformed to an emulation tree:
πΏ =ππ0 ,π0 = πππ0 ,π0 , πππ’01,π0 , . . . , πππ’0π,π0 = πΈπ0 ,π0 . For every tree in this list, we show that for every
node π’ in the tree the validations when π’ is the input node of the iteration pass. Therefore, it
will follow that the validations also pass for every node in the final emulation tree πΈπ0 ,π0 .
Let π be an intermediate tree, and π’ a node in π. When we say that a validation passes
relative to π and π’, we mean that if the tree π had been used as an emulation tree, then in the
iteration on which π’ is the input node, the validation would have passed. The children of π’ that
are considered in the validation are the children of π’ in π, and the seen-list π consists of the
ancestors of π’ and their children in π. Recall that the emulation protocol does not use π as an
emulation tree, since it is an intermediate tree so its height has not been reduced enough to
satisfy the bound required by the theorem. However, if π had been used the validations would
have passed.
Let πππ§0 ,π0 be an intermediate tree from the list above, created when identifying the node π§
as a heavy child of some other node. We assume that the validation we are currently checking
holds for every node in πππ§0 ,π0 , and show that it also holds in the next step of the construction,
that is the next tree in the list πΏ. Recall that the next step is identifying a heavy child for π§ (or if
π§ doesnβt have heavy children then identifying the next heavy child for the next node in the
traversal of the intermediate tree πππ§0 ,π0 ). Denote the next heavy child being identified by π£, and
the intermediate tree after this modification by πππ£0 ,π0 .
Note that it is not sufficient to show that after the creation or identification of π£ the property
being checked is maintained for π£. This is because the procedure might affect the descendants
and ancestors of π£ in πππ£0 ,π0 , as well as nodes whose seen-list changes. Exactly which nodes are
affected depends on the validation.
Remark A.6. Let π£ be a node in πππ§0 ,π0 that the Build_Tree procedure has not been invoked on
yet. Recall that the children of π£ in πππ§0 ,π0 are children of the node π£ in ππ0 ,π0 . Hence, like in the
tree ππ0 ,π0 , the transcripts of the children of π£ in πππ§0 ,π0 extend the transcript of π£ by one pair of
messages. Furthermore, if we did not invoke Build_Tree on π£ yet, then we also did not invoke
it on the descendants of π£ in πππ§0 ,π0 . Thus, the subtree of πππ§0 ,π0 rooted at π£, denoted by πππ§0 ,π0 (π£),
is a subtree of ππ0 ,π0 .
Now, we go over the validations, which are stated for a node π’ and its children π£1 , . . . , π£ π
provided by the prover as part of the emulation. The validations are numbered as in Construc-
tion A.5. Assuming that the validations hold for every node in πππ§0 ,π0 , we shall prove that these
validations hold for every node in πππ£0 ,π0 (the next intermediate tree in the list).
(a) In this validation, for each π β [π] the verifier checks that πΎ(π’) is a proper prefix of πΎ(π£ π ).
In the original protocol tree ππ0 ,π0 the transcript of each node extends the transcript of its
parent by a pair of messages and thus the property holds. Assume that every node in
πππ§0 ,π0 maintains the property that its parentβs transcript is a proper prefix of its transcript.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 49
M AYA L ESHKOWITZ
Let π£ be a heavy descendant identified for π§ and moved to be a child of π§ along with the
subtree under it. The only node in πππ£0 ,π0 that has a child it did not have in πππ§0 ,π0 is π§, which
now has π£ as a child. Since π£ is a descendant of π§ in π, and the transcript of every node in
πππ§0 ,π0 is a proper prefix of the transcripts of its children, then the transcript of π§ is a proper
prefix of the transcript of π£. Hence, in the new tree πππ£0 ,π0 , the transcript of each node is a
proper prefix of the transcript of its children as well.
(b) In this validation, the verifier checks, for each child π£ π of π’, that πΎ(π£ π ) is prover consistent
with respect to the other transcripts of nodes in π and with respect to the transcripts of the
other children of π’.
In the original protocol tree, ππ0 ,π0 , every two nodes are prover consistent since π0 is
deterministic. (If there were two partial transcripts in ππ0 ,π0 whose maximal common
prefix ends with a verifier message it would mean that that the prover can respond in
different ways to the same partial transcript). The transcripts of the nodes in πΈπ0 ,π0 all
appear in ππ0 ,π0 , so every two transcripts in πΈπ0 ,π0 are prover consistent as well.
(c) In this validation the verifier checks, for each child π£ π of π’, that π£ π is not part of the
emulation tree that was truncated from πΎ(π’); that is, if πΎ(π’) is a prefix of a transcript eπΎ β π,
then eπΎ should not be a prefix of πΎ(π£ π ). (Note that this also implies together with validation
πΎ β π that e
(a) that for each transcript e πΎ β πΎ(π£ π ).)
The main idea is that the changes we make to the emulation tree in every step of the
construction are identifying a heavy descendant and moving it to be a direct child along
with the subtree under it. Hence, if some node π£ whose transcript is e πΎ = πΎ(π£) and is a
descendant of π’, is identified as a heavy child of an ancestor of π’, denoted by π§, then
π£ is moved, along with the subtree rooted at π£, to be a descendant of π§. Hence, all the
nodes that πΎ(π£) is a prefix of and are descendants of π£ cannot be descendants of π’, and in
particular they cannot be children of π’ after the move. However, it is not clear that after
moving π£ to be a heavy child of π§ the only potential nodes that we need to check that the
claim holds for are the ancestors of π£ (note that above we assumed that π’ is an ancestor of
π£). Moreover, it is not true that all the nodes that πΎ(π£) is a prefix of are descendants of π£ in
the emulation tree, since some of these nodes might have been lifted to be heavy children
of ancestors of π£ in a previous iteration. Hence, a detailed proof follows.
Definition A.7 (Seen-list of a node). When we consider an intermediate tree πππ§0 ,π0 , which
may not be the final emulation tree, and some node π£ β π, then we denote by π(π£) the
seen-list π in the beginning of the iteration where π£ is the input node handled. That is,
π(π£) is the list containing the nodes that are ancestors of π£ in πππ§0 ,π0 , augmented with their
children.
Let π’ β πΈπ0 ,π0 and e πΎ β π(π’) such that πΎ(π’) is a prefix of e πΎ. We prove that for each
descendant π of π’ in πΈπ0 ,π0 the transcript e
πΎ is not a prefix of πΎ(π).
Note this is a stronger claim than what we need to show, because we only need to show it
for the children of π’ in πΈπ0 ,π0 and not for each descendant of π’.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 50
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
First, we shall show that the claim holds in the initial protocol tree ππ0 ,π0 . The transcript
of each node is ππ0 ,π0 is a prefix only of its descendants in the tree. However, π’ is not an
ancestor of any node in π(π’), so πΎ(π’) cannot be a prefix of any e πΎ β π(π’). Next, we shall
π§
assume that the claim holds in the intermediate tree ππ0 ,π0 before identifying and moving
the child π£ of π§, and we show that it holds in the tree πππ£0 ,π0 after the identification of π£ as a
heavy child of π§.
When π£ is identified as a heavy descendant of π§, node π£ is moved to be a child of π§ along
with the subtree under it. In order to show that the claim holds in πππ£0 ,π0 , it is enough to
consider the nodes π’ β πππ£0 ,π0 that have new descendants or new nodes in π(π’) relative to
the ones they had in πππ§0 ,π0 . The descendants of every node in πππ£0 ,π0 are all descendants of
it in πππ§0 ,π0 .
The only nodes in πππ£0 ,π0 that have new nodes in their seen-list are the descendants of π§,
since now πΎ(π£) is in their seen-list (recall definition in Remark A.6 ), whereas πΎ(π£) may
not have been in their seen-list before the move. By Remark A.6, before the invocation of
Build_Tree(z) the subtree rooted at π§ is a subtree of ππ0 ,π0 . Let π’ be a descendant of π§ in
πππ£0 ,π0 . Since determining the heavy descendants of π§ is done bottom up (this is implied by
the definition of heavy descendants in Subsection A.2), if πΎ(π’) is a prefix of πΎ(π£) then π’ is
an ancestor of π£ in πππ§0 ,π0 . It is left to check that πΎ(π£) is not a prefix of the transcripts of the
descendants of π’ in πππ£0 ,π0 . By Remark A.6, it follows that the subtree of πππ£0 ,π0 rooted at π’,
denoted by πππ£0 ,π0 (π’), is a subtree of ππ0 ,π0 . Thus, because π£ β πππ£0 ,π0 (π’) (recall that π£ was
lifted to be a heavy child of π§, and π’ is a descendant of π§) it follows that πΎ(π£) is not a prefix
of the transcripts of the nodes in πππ£0 ,π0 (π’), which are the descendants of π’ in πππ£0 ,π0 . (See
Figure 16.)
( ) ( )
0, 0 0, 0
z z
v
u u
v
Figure 16: π£ is identified as a heavy child of π§, and π’ is a descendant of π§, which was an ancestor
of π£ in πππ§0 ,π0 .
(d) In this check the verifier checks that all the children of π’ have different transcripts; that is,
for every two distinct children π£ π and π£ π of π’, the verifier checks that πΎ(π£ π ) β πΎ(π£ π ).
In the original protocol tree ππ0 ,π0 every two nodes have different transcripts. The nodes
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 51
M AYA L ESHKOWITZ
in πΈπ0 ,π0 all appear in ππ0 ,π0 , so every two nodes in πΈπ0 ,π0 also have different transcripts,
and in particular every two children of π’ have different transcripts.
Concluding the proof of completeness. In order to conclude the proof of completeness we
use the following claim, which shows that the probability that π accepts at the end of the
interaction with π is equal to the probability that π0 accepts at the end of the interaction with
π0 . The claim is stated in a more general way than needed for the proof of completeness, so that
we shall also be able to use it in the soundness part of the analysis.
Claim A.8 (Relating leaves in the two trees). Let π e be a prover for the emulation of input π₯ with
emulation tree πΈπe, using a strategy such that the verifier π does not abort until the final checks. Let
πe0 be a prover strategy for the original interactive proof system that is consistent with all the transcripts
in πΈπe; that is, for every π’ β πΈπe with transcript πΎ(π’) = πΌ1 π½1 , . . . , πΌ π π½ π , the strategy of πe0 satisfies
πe0 (π₯, πΌ1 , . . . , πΌ π ) = π½ π for every π β€ π. Then, the transcript πΎ created by the end of the emulation of
π
e and π when using coins π is equal to the transcript interacted between πe0 and π0 when using coins
π. Thus, the probability that π accepts at the end of the interaction with π e is equal to the probability that
π0 accepts at the end of the interaction with π0 . e
The proof of completeness follows by using in Claim A.8, π as π e and π0 as πe0 . Indeed,
we can do so because as showed previously it holds that π does not abort until the final
checks when interacting with π. In addition, since the emulation tree was constructed using the
protocol tree ππ0 ,π0 , for every node π’ in the emulation tree with transcript πΎ(π’) = πΌ1 π½ 1 , . . . , πΌ π π½ π
it holds that π0 (π₯, πΌ1 , . . . , πΌ π ) = π½ π for every π β€ π. Applying Claim A.8, the probability that
π accepts at the end of the interaction with π is equal to the probability that π0 accepts at the
end of the interaction with π0 . Thus, the completeness of the original interactive proof system is
maintained.
Proof. Let π be the value of the coins of π. By the assumption, all the transcripts in the emulation
tree πΈπe are consistent with the strategy of πe0 . Recall that, in each iteration of the emulation of
π and π, e a new node in πΈ e is chosen, and the continuation of the transcript is according to
π
the transcript of the new node. Hence, in each iteration the continuation of the transcript must
be consistent with the transcript of πe0 . The proof follows by noting that the continuations of
the transcript are also consistent with the strategy of π0 with coins π. That is, if the verifier
π chooses a continuation of the transcript suggested by π, then this transcript must be consistent
with the strategy of π0 with coins π. Otherwise, the verifier sends its next message based on
the strategy of π0 with coin tosses π. It follows that in every iteration the current transcript is
consistent with the strategy of πe0 and π0 with coins π.
From the assumption that π does not abort until the final checks, we know that after the
last iteration the complete transcript had been interacted. Hence, this complete transcript is
equal to the transcript of the interaction between πe0 and π0 with coins π.
The final check of the emulation of π e and π with random coin π pass if and only if π0 with
coins π accepts the complete transcript that has been interacted. Recall that the private coins in
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 52
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
the original and new emulation are sampled using the same probability distribution. Thus, the
probability that π accepts at the end of the interaction with π
e is equal to the probability that
π0 accepts at the end of the interaction with πe0 .
A.4.2 Soundness
Let π₯ be a no-instance. We shall show that π rejects π₯ with probability at least π (π), the original
soundness parameter.
The main part of the soundness proof here is Lemma A.9, which is a slightly
simplified version of Lemma 6.5 in Section 6.2.1. The other two components of
the soundness analysis of the public coin system (which are defining the notion
of actual weight of a node, and bounding the gap between the claimed and actual
weight) are not required for the private coin soundness analysis.
The crux of the proof is extracting a deterministic strategy for the original prover πe0 using
the strategy of π. e We can assume, without loss of generality, that π e is deterministic since for
every probabilistic prover there is a deterministic prover for which the verifierβs acceptance
probability is at least as high. Hence, if we show soundness holds with deterministic provers
it implies soundness is maintained also with non-deterministic provers. Because the prover
is deterministic we know that there is an emulation tree underlying the strategy of prover π. e
In an emulation tree every node contains a transcript that extends the transcript of its parent.
Hence, the protocol tree of πe0 and π can be used to define an emulation tree, which we denote
by πΈπe. We define a strategy for πe0 by using the transcripts in πΈπe. That is, for each π’ β πΈπe with
transcript πΎ (π’) = πΌ1 π½ 1 . . . , πΌ π π½ π , we define πe0 (π₯, πΌ1 , . . . , πΌ π ) B π½ π for all π β€ π. We extend πe0 βs
strategy to transcripts that do not appear in πΈπe in an arbitrary way. The main part of the analysis
consists of showing that the transcripts of every two nodes in πΈπe are prover consistent, i. e., that
their maximal common prefix ends with a prover message, and thus the strategy of πe0 is well
defined.
We can assume, without loss of generality, that the strategy of π e is such that the verifier does
not abort until the final checks. This is because every prover strategy in which the verifier aborts
in one of the intermediate checks can be modified to a prover strategy in which the verifier does
not abort until the final check and the verifierβs acceptance probability is at least as large. (The
prover can compute the transcripts of the children such that they are different continuations
of their parent and prover consistent with the list π instead of every node where the verifier
would have aborted in the intermediate checks.) In Lemma A.9 we show that this implies that
all the transcripts in πΈπe are prover consistent, and thus the strategy of πe0 is well defined. The
proof of soundness then follows by applying Claim A.8 (provided in Subsection A.4.1), that
implies that the probability that π accepts when interacting with π e is equal to the probability
that π0 accepts when interacting with πe0 , which is at most the soundness parameter π (π).
It is left to show that the strategy of πe0 is well defined, i. e., that no two nodes π’, π£ β πΈπe share
the prefix of prover-verifier interaction but differ on the proverβs response. That is, we show
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 53
M AYA L ESHKOWITZ
that every two nodes π’, π£ β πΈπe are prover consistent (see Definition A.4).
For a node π’ β πΈπe provided during the emulation, denote by π (π’) the seen-list from πΈπe at
the beginning of the iteration in which π’ was the input node (i. e., was the node handled on that
iteration). That is, the nodes in π(π’) are the ancestors of π’ in πΈπe and their children. Validation 2b
implies that each node π’ in the emulation tree is prover consistent with the transcripts of the
nodes in π(π’). We show that using validations 2a,2c and 2d it follows that every two transcripts
in the emulation tree are prover consistent.
Lemma A.9 (Prover consistency of the emulation tree). If π e is a prover for the new emulation
protocol using a strategy such that the verifier π does not abort until the final checks (for every verifier
randomness), then every two transcripts of nodes in the emulation tree πΈπe are prover consistent.
Note that the following proof is a slightly simplified version of the proof of
Lemma 6.5 in Section 6.
Proof. Let π’ and π£ be two nodes in the emulation tree πΈπe, we wish to show that their transcripts
πΎ(π’) and πΎ(π£) are prover-consistent. If one of the nodes is in the seen-list π of the other node
(that is, if π’ β π(π£) or π£ β π(π’)) then the transcripts of π’ and π£ must be prover consistent by
validation 2b. Otherwise, the intersection between the seen-list of nodes of π’ and π£ is non-empty,
and particular it contains the least common ancestor of π’ and π£, denoted by π§, as well as the
children of π§ that are ancestors of π’ and π£, denoted by π and π respectively, see Figure 17 for
illustration. (Note that π§ is not equal to π’ or to π£, otherwise π’ β π(π£) or π£ β π(π’). Similarly
π β π’ and π β π£.) Hence, by using the prover consistency between the transcripts of π, π, π§ and
the transcript of π’, as well as between the transcript of π£, and by using structural validations
between the nodes in the emulation tree (validations 2a, 2c and 2d) we are able to show that the
transcripts of π’ and π£ are also prover consistent. Details follow.
Figure 17: The subtree of πΈπe that contains π’ and π£
Since π is an ancestor of π’ and π is an ancestor of π£, then πΎ(π) is a proper prefix of πΎ(π’), and
πΎ(π) is a proper prefix of πΎ(π£). We consider two cases according to the relation between πΎ(π)
and πΎ(π).
First, consider the case that πΎ(π) is not a prefix of πΎ(π) and πΎ(π) is not a prefix of πΎ(π). By
validation 2a we know that each node in this path from π’ to π is a prefix of its children. Thus,
πΎ(π) is a prefix of πΎ(π’). Similarly, πΎ(π) is a prefix of πΎ(π£). Recall that we are in the case that πΎ(π)
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 54
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
is not a prefix of πΎ(π) and πΎ(π) is not a prefix of πΎ(π), and so the maximal prefix on which πΎ(π)
and πΎ(π) agree upon is a proper prefix of both. This common prefix equals the maximal prefix
on which πΎ(π’) and πΎ(π£) agree. We know that πΎ(π) and πΎ(π) are prover-consistent because the
prover provides π along with π as children of π§ and we assume that validation 2b is satisfied.
Since the maximal prefix that πΎ(π’) and πΎ(π£) agree on is equal to the maximal prefix that πΎ(π)
and πΎ(π) agree on, it follows that πΎ(π£) and πΎ(π’) are also prover-consistent. See Figure 18 for
illustration.
Figure 18: πΎ(π) and πΎ(π) agree on the prefix in white, while πΎ(π) is a prefix of πΎ(π’) and πΎ(π) is a
prefix of πΎ(π£).
Note that πΎ(π) cannot be equal to πΎ(π) since that would be a violation of validation 2d. We
are left with the case that one of the transcripts πΎ(π) and πΎ(π) is a proper prefix of the other, and
assume, without loss of generality, that πΎ(π) is a proper prefix of πΎ(π). Denote the transcript of π
by πΎ(π) = πΌ 1 π½ 1 , . . . , πΌ π π½ π .
We claim that πΎ(π) is not a prefix of πΎ(π’). Assume by contradiction that πΎ(π) is a prefix of
πΎ(π’). Note that π β π(π’), so by validation 2c (which passed for the parent of π’) πΎ(π) β πΎ(π’),
so πΎ(π) must be a proper prefix of πΎ(π’). Denote the nodes in the path from π to π’ in πΈπe by
π = π 0 , π1 , . . . , π π = π’ and by π π the first node in the path such that πΎ(π π ) is a prefix of πΎ(π) and
πΎ(π π+1 ) is not a prefix of πΎ(π). There must exist such node π π since πΎ(π) is a prefix of πΎ(π), and
πΎ(π’) is not a prefix of πΎ(π). Note that since π π+1 is an ancestor of π’ in πΈπe, then by validation 2a it
follows that πΎ(π π+1 ) is a proper prefix of πΎ(π’). Hence, πΎ(π) and πΎ(π π+1 ) are both prefixes of πΎ(π’).
Thus, one of them must be a prefix of the other, and so in this case πΎ(π) is a prefix of πΎ(π π+1 ).
It follows that we have a violation to validation 2c, since π β π(π π ) where πΎ(π π ) is a prefix of
πΎ(π) and πΎ(π) is a prefix of πΎ(π π+1 ) (see Figure 19). Hence, we reached a contradiction to the
hypothesis that π does not abort in the intermediate validations, and so πΎ(π) cannot be a prefix
of πΎ(π’).
Because πΎ(π) is not a prefix of πΎ(π’), the maximal common prefix of πΎ(π’) and πΎ(π) is a proper
prefix of πΎ(π). We know that π β π(π’) because π is a child of π§, which is an ancestor of π’. Hence,
by validation 2b, the transcript of π’ and the transcript of π β π(π’) are prover consistent. It
follows that the maximal common prefix of πΎ(π’) and πΎ(π), which is a proper prefix of πΎ(π), ends
with a prover message.
Lastly, note that from validation 2a the transcript of each node in the path from π to π£ is a
prefix of the transcript of its parent. Thus, πΎ(π) is a prefix of πΎ(π£). It follows that the maximal
common prefix of πΎ(π£) and πΎ(π’) is contained in the maximal common prefix of πΎ(π’) and πΎ(π),
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 55
M AYA L ESHKOWITZ
Figure 19: The dashed arrow pointing from π to π π+1 represent the fact that πΎ(π) is a prefix of
πΎ(π π+1 ), and similarly that πΎ(π π ) is a prefix of πΎ(π).
Figure 20: The maximal common prefix between πΎ(π’) and πΎ(π) appears in white. Since πΎ(π) is a
prefix of πΎ(π£) the maximal common prefix of πΎ(π’) and πΎ(π£) is the same as the former.
so it ends with a prover message (See Figure 20).
Appendix B Alternative public coin emulation
In this Appendix we sketch a proof for an additional weaker version of the main theorem,
one which transforms a private coin interactive proof system to a public coin interactive proof
system. This transformation does not reduce the round complexity, and it does not preserve
the randomness complexity, but it also does not blow up the randomness complexity by much.
Recall that this is indeed weaker than the main theorem, because this transformation does not
yield a public coin interactive proof where the round complexity is bounded by the randomness
complexity. Moreover, the randomness complexity is not preserved.
The contribution of this theorem is also due to the fact that we can derive the main Theorem 1.1
from Theorem B.1 and Theorem A.1. In this way, we obtain a modular proof of the main
theorem in which the creation of the protocol tree and its emulation are separated into two
stages. We would like to thank an anonymous reviewer for suggesting the idea of proving
theorem Theorem B.1.
Theorem B.1 (Randomness Efficient Public Coin Emulation). Suppose that π has an inter-
active proof system of randomness complexity π(π) and round complexity π(π) for instances of
length π. Then, π has a public coin interactive proof system of round complexity π(π 0(π)), where
π 0(π) =max{π(π)/log π(π), π(π)}, and randomness complexity π(log π(π) Β· π 0). Furthermore, the
resulting interactive proof system has perfect completeness.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 56
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
The section is organized as follows, first we show how to conclude the main theorem from
the two weaker theorems. Next, we sketch a proof for Theorem B.1.
B.1 Concluding the main Theorem 1.1 using the alternative emulation
For clarity, we begin by restating the main Theorem.
Theorem 1.1 (Main Theorem). Suppose that π has an interactive proof system of randomness
complexity π(π) for instances of length π. Then, π has a public coin interactive proof system
of round complexity π(π(π)/log π(π)) and randomness complexity π(π(π)). Furthermore, the
resulting interactive proof system has perfect completeness.
Next, we give an alternative proof of the main theorem. See the main sections of the paper
for the standard proof.
Proof. Fix an interactive proof for the set π, that has randomness complexity π(π) for instances of
length π. From Theorem A.1, it follows that π has a private coin interactive proof system of round
complexity π(π(π)/log π(π)) and randomness complexity π(π). Applying Theorem B.1 on the
new interactive proof system for π, if follows that π has a public coin interactive proof system
of
round complexity π(π(π)/log π(π)), and randomness complexity π log π(π) Β· π(π)/log π(π) =
π(π(π)). Furthermore, the resulting interactive proof system has perfect completeness.
Reflection. In this alternative proof, we first use Theorem A.1 to reduce the number of rounds
of the private coin interactive proof system to π π(π)/log π(π) . We then apply Theorem B.1
on the new interactive proof system and convert it to a public coin interactive proof system
that does not increase the round complexity to above π π(π)/log π(π) , and has randomness
complexity of π(log π(π)) times the number of rounds, so randomness complexity is π(π(π)). In
particular, using other known transformations of private coin to public coin interactive proofs,
instead of Theorem B.1, would not have worked in deriving the main theorem since these
transformations blow up the randomness complexity by too much.
The main difference between the standard proof in the main section of this paper and the
alternative proof, is that in the standard proof the transformation is done in one shoot. That
is, there is one transformation of the protocol tree of the original interactive proof system
to an emulation tree that both has degree bounded polynomially and height bounded by
π π(π)/log π(π) . Then this emulation tree is used to perform a public coin emulation and
the verifer has to perform on every round both validations concerning the degree reduction
and validations concerning the height reduction. In contrast, in the alternative proof the
transformation of the protocol tree is separated to two parts: first, reduce the height of the tree
(which will reduce the number of rounds to π π(π)/log π(π) ), and then reduce the degree of
the tree (which will enable emulating with public coins). The emulation itself is also separated
into two parts. Since we are using the private coin transformation we derived with Theorem A.1,
and then emulating it using the emulation of Theorem B.1, it follows that all the validations
defined in the private coin emulation protocol are postponed to after the last iteration of public
coin emulation Construction B.6 (see the protocol in the following sections).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 57
M AYA L ESHKOWITZ
B.2 Proof Sketch of Theorem B.1
We sketch the proof of Theorem B.1, beginning by giving an overview in Section B.2.1. Next,
we describe the construction of the emulation tree and its properties in Section B.2.2 and
Section B.2.3, and finally describe the emulation protocol in Section B.2.4 . We omit the analysis
of the emulation protocol. We refer the interested reader to the analysis in Section 6, which
includes the ideas required for the analysis of this theorem.
B.2.1 Overview
Fixing an interactive proof between a prover π and a verifier π, and an instance π₯ of length
π, we describe the possible prover-verifier interactions on common input π₯ using the protocol
tree ππ,π defined in Section 3. The height of ππ,π corresponds to the number of rounds π(π)
of interaction, and the number of leaves is 2π(π) , where π(π) is the randomness complexity. As
in the proof of the main theorem, our goal is to transform the protocol tree to an emulation
tree, denoted by πΈπ0 ,π0 , that defines a prover strategy for a public coin emulation. Recall that
the way we use the emulation tree to define a prover strategy for the public coin emulation
is by initiating the emulation at the tree root, and on each round having the prover assist the
verifier at progressing one step down the emulation tree. (This assistance is required because
the verifier does not have access to πΈπ0 ,π0 .) Each round consists of the prover providing the
verifier with the descriptions of the children of the current node π’ that was sampled on the
previous round, where these descriptions contain the weights of the various children. Hence, in
order to apply this emulation strategy, the prover should use an emulation tree with a degree
that is bounded by poly(π), whereas the degree of ππ,π can be exponential in π. Thus, our goal
is to transform the protocol tree ππ,π to an emulation tree πΈπ0 ,π0 , with a degree bounded by
poly(π), and the height of the tree (which corresponds to the number of rounds) should be
π(π 0), for π 0(π) =max{π(π)/log π(π), π(π)}. This is done using the Build_Tree(r) procedure.
In order to reduce the degree when it is too large, we group the children of π under new
children, which we call interval children. (Note that here we donβt need to first lift the heavy
descendants of π as we did in the proofs of the other theorems, because we are not trying
to reduce the number of rounds, unlike in the other theorems.) In general, children of π in
ππ0 ,π0 may become non-immediate descendants during the procedure.
The Build_Tree(r) procedure unites the children of π into groups. We unite the children of
π by lexicographic order of their transcript field, such that the weight of each group is larger than
π€(π)/π(π) and at most 2π€(π)/π(π) (except for, possibly, the last group which is only required to
have weight smaller than 2π€(π)/π(π)). We create a new interval child π£ for each such group,
where the children of π£ are the nodes in the group. If π has only one child π’, then instead of
creating an interval child for π, we leave π’ as an original child of π.
Denote by πππ’0 ,π0 the intermediate tree after we identify and set π’ as an interval or original
child of π. This way we have a notation for every transformation of the tree in which we create
an additional child.
After creating all the interval children of π (or identifying the original child), the children
of π in the final emulation tree πΈπ0 ,π0 are exactly the children of π in πππ§0 ,π0 , where π§ is the last
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 58
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
interval child of π created. The number of children π has is at most π(π), since the weight of
each interval child of π (except for possibly the last interval child) is at least π€(π)/π(π). Next, the
procedure is called recursively on the children of π in πππ§0 ,π0 in order to create the final emulation
tree.
The description of a node π’ in the emulation tree is composed of the transcript field
πΎ (π’) = πΌ1 π½ 1 . . . πΌ π π½ π and a weight field π€(π’) as in the original protocol tree, with an additional
range field π
(π’). The range of a node represents the possible range of its childrenβs transcripts.
Hence, the transcripts of the children of each interval child are the same up to the last verifierβs
message on which they differ, which corresponds to the branching of the intermediate tree for
the next round. Thus, we can label the range π
(π’) = [π , π] where π < π β {0, 1}β according to the
range of the last verifier message in the transcript field of the children of π’. Original
children
have full range 0β , 1β , whereas the range of interval children is a subinterval of 0β , 1β such
that this subinterval corresponds to the transcripts of the descendants that are grouped under
this node.
We show in the analysis that the height of πΈπ0 ,π0 is π(π 0(π)), where
π (π) =max{π(π)/log π(π), π(π)}. The degree of nodes in πΈπ0 ,π0 is at most π(π), hence it is
0
suitable for public coin emulation.
(The running time of this algorithm is at least the size of the protocol tree, which is exponential
in π(π), and thus it may be exponential in |π₯|. However, the prover is the one that runs this
algorithm and the prover is computationally unbounded. Therefore the running time is not an
issue.)
B.2.2 The Build_Tree procedure
Denote the designated prover and verifier of the original interactive proof system by π0 and
π0 respectively, and the protocol tree of π0 and π0 for a yes-instance π₯ by ππ0 ,π0 . The Build_Tree
procedure is a recursive procedure that reads and updates a tree π, which is initially set to
equal the protocol tree ππ0 ,π0 until obtaining the final emulation tree, denoted by πΈπ0 ,π0 . When
invoked on a node π’ in π, the procedure determines the children of π’, updates the global tree
and invokes the procedure recursively on the children of π’.
We denote by π(π’) the subtree of π rooted at π’.
Initialization. The tree π is initialized to be the original protocol tree, where each node has a
description that contains the weight and transcript like in the original tree, and an additional
range field which is initially left empty. We set the range of the root, denoted π, to be full range
π
(π) = [0β , 1β ]. If the weight of π is zero we terminate the process. Otherwise, we invoke the
Build_Tree procedure on π.
The main procedure: Build_Tree . If π’ is a leaf, the procedure returns without updating the
global tree π. If π’ has only one child π£ with non zero weight, then the procedure deletes the
children of π’ whose weights are equal to zero, identifies π£ as an original child of π’, and sets the
range of π£ to be full range π
(π) = [0β , 1β ]. Otherwise, the Build_Tree procedure invokes the
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 59
M AYA L ESHKOWITZ
Build_Interval(u) procedure, in order to create and update the children of π’ in π. Finally, the
Build_Tree procedure is invoked recursively on all the children of π’ in π.
Build_Interval(u). This procedure groups the children of π’ under interval children. Denote
the range field of π’ by π
(π’) = [π (π’), π(π’)]. (Note that π (π’) = 0β and π(π’) = 1β unless π’ is an
interval node, in which case its range is partial.) We partition the range of π’ into a sequence of
consecutive intervals, each one representing the range of a new child of π’. As long as we have
not partitioned all of the range [π (π’), π(π’)] we perform the following procedure.
1. Determine π 0, the starting point of the interval childβs range: Initially, for the first interval
child of π’ we set π 0 = π (π’). For the next interval children, if the end of the range of the
previously created interval child is πΛ , then we set π 0 = πΛ + 1.
2. Determine π 0, the ending point of the interval childβs range: For each π β {0, 1}β , denote by
πΌππ‘πππ£ππ(π 0 , π) the set of children of π’ in π(π’) whose last verifier message πΌ (in the transcript
field) is in the range [π 0 , π]. Note that when [π 0 , π] β [π (π’), π(π’)] the set πΌππ‘πππ£ππ(π 0 , π)
can be a proper subset of the non-heavy children of π’. We define the weight of the
set πΌππ‘πππ£ππ(π 0 , π), which we denote by π(π 0 , π), as the sum of the weights of nodes in
πΌππ‘πππ£ππ(π 0 , π).
We set π 0, to be the minimal π β {0, 1}β that satisfies π(π 0 , π) β₯ π€(π’)/π(π). If no such π
exists and π(π 0 , π(π’)) > 0, we set π 0 = π(π’). If π(π 0 , π(π’)) = 0 there is no need to create
another interval child so we return to the Build_Tree procedure. (This guarantees that
the weight of an interval child is at least 1).
3. Create a new node π£: We set the transcript of π£ to be like the transcript of π’, πΎ(π£) = πΎ(π’),
its range to be π
(π£) = [π 0 , π 0] and its weight to be π€(π£) = π(π 0 , π 0).
4. Place π£ in the tree: disconnect π’ from the nodes in πΌππ‘πππ£ππ(π 0 , π 0). Set π’ as a parent of π£
and let π£ be the parent of all nodes that are in πΌππ‘πππ£ππ(π 0 , π 0).
Note that the weight of an interval child of π’ is at most 2π€(π’)/π(π) and at least π€(π’)/π(π), except
possibly for the last interval child, whose weight is at least 1.
B.2.3 Properties of the emulation tree
Recall that in the original protocol tree, π£ was a child of π’ if and only if πΎ(π£) = πΎ(π’)πΌπ½ where
πΌ, π½ β {0, 1}β denote the next verifier message and the proverβs response to it. However, in the
new emulation tree, πΈπ0 ,π0 , this is not the case. Namely, if π£ is a child of π’ in πΈπ0 ,π0 , then it could
be that π£ is an original child of π’ and hence πΎ(π£) = πΎ(π’)πΌπ½ for some πΌ, π½ β {0, 1}β , or π£ is an
interval child hence πΎ(π£) = πΎ(π’) and π
(π£) β π
(π’). Nevertheless, the following properties of the
final emulation tree πΈπ0 ,π0 are readily verified. We omit the proofs for most of these properties
and we refer the reader to the proofs in Section 4.3, which are a slightly more complex version
of the corresponding claims here. We only include the proof of Corollary B.4 since it is different
from the one in Section 4.3.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 60
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
Claim B.2 (Node degree). Each node π’ in the final emulation tree πΈπ0 ,π0 has at most π(π) children.
Claim B.3 (Weight reduction). For every node π’ in the final emulation tree πΈπ0 ,π0 , and each grandchild
π§ of π’, either π§ is a child of an interval child of π’, and the weight of π§ is at most 2π€(π’)/π(π), or π§ is an
original child of π’.
Corollary B.4 (Corollary to Claim B.3). The height of the final emulation tree πΈπ0 ,π0 is π(π 0(π)),
where π 0(π) =max{π(π)/log π(π), π(π)}.
Proof. Fixing an iteration that begins with input node π’, the prover helps the verifier go one
step down πΈπ0 ,π0 . Hence, two iterations later the chosen node π§ is a grandchild of π’, so from
Claim B.3 either π§ is a child of an interval child of π’ and the weight of π§ is at most 2π€(π’)/π(π),
or π§ is a child of an original child of π’. Note that after visiting π original children while going
down the tree we have reached a leaf of πΈπ0 ,π0 . In addition, after visiting 3π(π)/log π(π) interval
children the weight of the node we reached is at most 2π(π) /(π(π)/2)3(π(π)/log π(π)) < 1, so we
have reached a leaf. It follows that after 2(π + 3π(π)/log π(π)) iterations we have reached a leaf
(either by visiting π original children or having the weight reduced with interval children). The
multiplication by two comes from the fact that we have a guarantee of visiting an original child
or reducing the weight only after two iterations.
Claim B.5 (Leaves). The leaves of πΈπ0 ,π0 are exactly the leaves of protocol tree ππ0 ,π0 whose weights are
1.
B.2.4 Public Coin Emulation
Next, we describe the strategy of the designated prover π and verifier π in the new protocol
(βemulationβ). The strategy of the designated prover π for a yes-instance π₯ uses the emulation
tree πΈπ0 ,π0 of π₯ constructed in the previous section. The prover assists the verifier π in
progressing down the emulation tree. On each iteration, the prover provides the descriptions
of the children π£ 1 , . . . , π£ π of the current node π’, which was sampled in the previous iteration.
The verifier performs validations on the list supplied by the prover (to be detailed below), and
then samples one of the children for the next iteration according to its weight. The verifier does
not have access to the emulation tree, and its validations consist of structural requirements on
the part of the emulation tree seen so far. On the last iteration, the verifier checks that the full
transcript, along with the sequence of coin tosses, leads the original verifier π0 to accept.
The exposition and definitions for this section are identical to the ones in Section 5,
with the minor change of having original children in this emulation, instead
of the heavy children in the other Section. Hence, we will not repeat the
exposition here, and the reader is referred to read the exposition in Section 5,
which includes transcript descendant Definition 5.1, transitivity Definition 5.2
and prover consistency Definition 5.3. Note that what is stated about heavy
children in Section 5 holds for original children in this emulation (although the
creation of the two types of children is different, the claims we make about them
in this section are identical).
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 61
M AYA L ESHKOWITZ
Construction B.6. (the πth iteration) On input a non-leaf node π’.
1. The prover provides the descriptions of the children π£ 1 , . . . , π£ π of π’:
(πΎ (π£ 1 ) , π
(π£ 1 ) , π€(π£ 1 )) , . . . , (πΎ (π£ π ) , π
(π£ π ) , π€(π£ π ))
2. If π = 1, then π’ has a single child π£ 1 , and the verifier performs the following validations
and rejects if any of them fails:
(a) The verifier checks that the weight of π£1 is equal to the weight of π’.
(b) The verifier checks that π£ 1 is a transcript descendant of π’.
3. Otherwise, if π > 1 the verifier performs the following validations and rejects if any of
them fails:
(a) The verifier checks that all nodes are different (according to their descriptions). That
is, for each distinct π, π β [π], if πΎ(π£ π ) = πΎ(π£ π ), then π
(π£ π ) β π
(π£ π ).
(b) The verifier checks that the weights of the children of π’ sum up to π€(π’); that is,
π
Γ
π€(π’) = π€(π£ π ) (B.1)
π=1
(c) For each π β [π], the verifier checks that π£ π is a transcript descendant of π’.
(d) For each child π£ π , the verifier checks that πΎ π£ π = πΎ(π’).
(e) The verifier checks that the ranges of all the children are disjoint; that is, for every
two children π£ π and π£ π , the verifier checks that π
π£ π β© π
(π£ π ) = β
.
4. The verifier chooses a child according to the probability distribution π½ that assigns each
π β [π] probability approximately proportional to π€(π£ π ) using π(log π(π)) coin tosses. That
is, π½ is such that
π€(π£ π )
Pr [π½ = π] β€ Γπ Β· (1 + 1/π(π)) (B.1)
π=1 π€(π£ π )
We only utilize π(log π(π)) public coins per iteration since we want this emulation to be as
efficient as possible in terms of randomness complexity, without sacrificing soundness by
more than a constant factor in total. Hence, we compromise on sampling each child with
probability proportional to π€(π£ π ), and instead sample with approximate probability. See
the explanation for approximate sampling in Appendix 5.4.
By our conventions, the last message the verifier π0 sends, denoted πΌ π , contains the
outcomes π β {0, 1} π(π) of the π(π) coins tossed. Thus, if the last node chosen is π£, then π can be
easily extracted from πΎ (π£) = πΌ1 π½ 1 , . . . , πΌ π π½ π . After the last iteration, the verifier performs final
checks and accepts if all of them hold:
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 62
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
(i) Check that π is accepting for πΎ (π£) and consistent with it: It checks that π0 (π₯, π, π½ 1 , . . . , π½ π ) =
1, and that for every π = 1, . . . , π it holds that πΌ π = π0 (π₯, π, π½1 , . . . , π½ πβ1 ). Note that the
verifier needs π in order to verify these conditions, so this check can only be done after the
last iteration. Also note that if these checks pass then π€(π£) = 1 (rather than π€(π£) = 0).
(ii) Check that π€(π£) = 1; in other words the proverβs last claim should be that the weight of
the last node chosen is 1 (and not more than 1).
Acknowledgments.
I would like to thank my advisor, Prof. Oded Goldreich, for his encouragement to approach the
problem studied in this paper, and for his guidance, support and contribution in the research
and the writing process. I thank Dr. Guy Rothblum for useful discussions. I also thank the
anonymous reviewers for providing useful comments and suggestions.
References
[1] LΓ‘szlΓ³ Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421β429.
ACM Press, 1985. [doi:10.1145/22145.22192] 4
[2] LΓ‘szlΓ³ Babai and Shlomo Moran: ArthurβMerlin games: A randomized proof sys-
tem and a hierarchy of complexity classes. J. Comput. System Sci., 36(2):254β276, 1988.
[doi:10.1016/0022-0000(88)90028-1] 4
[3] Mihir Bellare, Oded Goldreich, and Shafi Goldwasser: Randomness in interactive proofs.
Comput. Complexity, 3(4):319β354, 1993. [doi:10.1007/BF01275487] 4
[4] Martin FΓΌrer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos:
On completeness and soundness in interactive proof systems. In Silvio Micali, editor,
Randomness and Computation, volume 5 of Adv. Comput. Res., pp. 429β442. JAI Press, 1989.
Authorβs website. 4
[5] Oded Goldreich and Maya Leshkowitz: On emulating interactive proofs with public coins.
In Oded Goldreich, editor, Computational Complexity and Property Testing: On the Interplay
Between Randomness and Computation, pp. 178β198. Springer, 2020. [doi:10.1007/978-3-030-
43662-9_12, ECCC:TR16-066] 4, 9
[6] Oded Goldreich, Silvio Micali, and Avi Wigderson: Proofs that yield nothing but their
validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):690β728,
1991. Preliminary version in FOCSβ86. [doi:10.1145/116825.116852] 5
[7] Oded Goldreich, Salil P. Vadhan, and Avi Wigderson: On interactive proofs with a laconic
prover. Comput. Complexity, 11(1β2):1β53, 2002. [doi:10.1007/s00037-002-0169-0] 6
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 63
M AYA L ESHKOWITZ
[8] Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of
interactive proof systems. SIAM J. Comput., 18(1):186β208, 1989. Preliminary version in
STOCβ85. [doi:10.1137/0218012] 4
[9] Shafi Goldwasser and Michael Sipser: Private coins versus public coins in interactive
proof systems. In Silvio Micali, editor, Randomness and Computation, volume 5 of Adv.
Comput. Res., pp. 73β90. JAI Press, 1989. Preliminary version in STOCβ86. 4, 5, 9
[10] Adam R. Klivans and Dieter van Melkebeek: Graph nonisomorphism has subexponential
size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501β
1526, 2002. [doi:10.1137/S0097539700389652] 4
[11] Maya Leshkowitz: Round complexity versus randomness complexity in interactive proofs.
In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOMβ18), pp. 49:1β16.
Schloss DagstuhlβLeibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-
RANDOM.2018.49] 1
[12] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods
for interactive proof systems. J. ACM, 39(4):859β868, 1992. Preliminary version in FOCSβ90.
[doi:10.1145/146585.146605] 4, 10
[13] Ronen Shaltiel and Christopher Umans: Low-end uniform hardness versus randomness
tradeoffs for AM. SIAM J. Comput., 39(3):1006β1037, 2009. [doi:10.1137/070698348] 4
[14] Adi Shamir: IP = PSPACE. J. ACM, 39(4):869β877, 1992. Preliminary version in FOCSβ90.
[doi:10.1145/146585.146609] 4, 6, 10
AUTHOR
Maya Leshkowitz
Ph. D. student
The Hebrew University of Jerusalem
Jerusalem, Israel
mleshkowitz gmail com
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 64
ROUND C OMPLEXITY V ERSUS R ANDOMNESS C OMPLEXITY IN I NTERACTIVE P ROOFS
ABOUT THE AUTHOR
Maya Leshkowitz received her M. Sc. from Weizmann Institute of Science, under the
supervision of Oded Goldreich.
Maya discovered her love for solving mathematical questions as a child when
she played and solved riddles together with her grandfather, Shimon Even. In
graduate school, although she was interested in Cognitive Science and human
behavior, the Math and Computer Science courses at the Hebrew University
sparked her old passion and led her to pursue a M. Sc. in Computer Science.
Currently, she is a Ph. D student in the Cognitive Science department at the
Hebrew University, under the supervision of Ran R. Hassin. She is interested in
how people group information into chunks (such as by event or category) and
how these chunks later influence attitudes and evaluations.
When she is not doing research, she enjoys drawing, dancing, and traveling.
T HEORY OF C OMPUTING, Volume 18 (13), 2022, pp. 1β65 65