Zero-Knowledge Proofs of Proximity

Itay Berman MIT

Ron D. Rothblum MIT

Vinod Vaikuntanathan MIT

February 11, 2017

Abstract

Interactive proofs of proximity (Ergun, Kumar and Rubinfeld, Information & Computa- ¨ tion, 2004 and Rothblum, Vadhan and Wigderson, STOC 2013), or IPPs, are interactive proofs in which the verifier runs in time sub-linear in the input's length. Since the verifier cannot even read the entire input, following the property testing literature, the requirement is that she accepts inputs that are in the language and rejects ones that are far from the language. However, these proofs could (and in many cases, do) betray considerable global information about the input to the verifier.

In this work, we initiate the study of zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier while ensuring that she learns nothing more than a few locations of the input (and the fact that the input is "close" to the language).

Our main focus is the setting of statistical zero-knowledge where we show that the following hold unconditionally (where N denotes the input size):

• Statistical ZKPPs can be sub-exponentially more efficient than property testers (or even non-interactive IPPs): We show a natural property which has a statistical ZKPP with a polylog(N) time verifier, but requires Ω(^√ N) queries (and hence also runtime) for every property tester.
• Statistical ZKPPs can be sub-exponentially less efficient than IPPs: We show a property which has an IPP with a polylog(N) time verifier, but cannot have a statistical ZKPP with even an No(1) time verifier.
• Statistical ZKPPs for some graph-based properties such as promise versions of expansion and bipartiteness.

Lastly, we also consider the computational setting where we show that:

• Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a *computational* ZKPP with a (roughly) ^√ N time verifier.
• Assuming the existence of collision-resistant hash functions, every language in NP has a *statistical* zero-knowledge *argument* of proximity with a polylog(N) verifier.

1 Introduction

Interactive proofs, introduced by Goldwasser, Micali and Rackoff [GMR89] are protocols that allow for a polynomial-time verifier to check the correctness of a computational statement, typically formulated as membership of an input x in a language \mathcal{L} , using an interactive protocol.

Interactive proofs have had an incredible impact on theoretical computer science in general, and especially on cryptography and complexity theory. However, given the vast amounts of data that are available nowadays, in some applications even polynomial running time may be too much.

Ergün, Kumar and Rubinfeld [EKR04] asked whether we can obtain proof-systems in which the verifier runs in sub-linear time. In particular, this means that the verifier does not even have time to read the entire input. Since it is impossible to obtain sub-linear verification in general, to obtain a meaningful notion we settle for a suitable notion of approximation. Inspired by the property testing literature [RS96, GGR98] (see also [Gol16]) a recent line of works, initiated by Rothblum, Vadhan and Wigderson [RVW13], focuses on interactive proofs in which soundness is relaxed and the verifier is only required to reject inputs that are far (say, in Hamming distance) from being in the language. Thus, the verifier is only assured that the input x is close to the language \mathcal L and so these proof-systems are called interactive proofs of proximity, or IPPs for short. Recent results ([RVW13, GR16, FGL14, KR15, GGR15, RRR16, GG16, GR17]) have demonstrated that many languages admit very efficient IPPs.

One of the main advantages of classical interactive proofs is that they allow for proving statements in zero-knowledge [GMR89, GMW91]: amazingly, it is possible to prove that x \in \mathcal{L} without revealing anything other than that. Beyond being of intrinsic interest, zero-knowledge proofs have a multitude of applications.

In this work we initiate the study of zero-knowledge proofs of proximity, or ZKPP for short. Specifically we ask:

Is it possible to prove correctness of a computation to a sub-linear time verifier, so that the verifier does not learn more than it could have learned by reading a few bits from the input?

Loosely speaking, we say that an IPP with prover P and verifier V is a ZKPP, if for any possible cheating verifier \hat{V} that runs in time t = o(N), where here and below N denotes the input length, there exists a simulator S_{\hat{V}} that runs in time roughly t and outputs a view that is indistinguishable from the view of \hat{V} when interacting with P. Note that the bound on the running times for the verifier and the simulator also bounds their query complexity (i.e., the number of bits read from the input).

Interestingly, the notion of ZKPP has already implicitly appeared in the cryptographic literature 20 years ago. Bellare and Yung [BY96] noticed that the soundness of the [FLS99] construction of non-interactive zero-knowledge proof-system (NIZK) from trapdoor permutations breaks, if the cheating prover sends a description of a function that is not a permutation. [BY96] observed that to regain soundness in the [FLS99] protocol, it suffices to verify that the given function is close to being a permutation.

Focusing on the case that the domain of the permutation is \{0,1\}^n , [BY96] suggested the

following natural non-interactive zero-knowledge proof for certifying that a function is close to a permutation: the many random elements y1, . . . , y^k in {0, 1} ⁿ are specified as part of a common random string[2](#page-3-1) (CRS), and the prover is required to provide inverses x1, . . . , x^k to all of these elements. Soundness follows from the fact that if the function is far from a permutation then, with high probability, one of these elements will simply not have an inverse. Zero-knowledge is demonstrated by having the simulator sample the x's at random and obtain the y's by evaluating the permutation.

Since the verifier in the [\[BY96\]](#page-39-2) protocol is only assured that the function is close to a permutation, in our terminology, the [\[BY96\]](#page-39-2) protocol is a non-interactive ZKPP. Notice that the verifier runs in time poly(n), which is poly-logarithmic in the input (i.e., the truth table of f).

As is the case for standard zero-knowledge, the results that we can obtain depend heavily on the specific notion of zero-knowledge. These notions depend on what exactly it means that the output of the simulator is indistinguishable from a real interaction.

The main notion that we consider in this work is that of statistical zero knowledge proofs of proximity. Here, the requirement is that the distribution of the output of the simulator is statistically close to that of the real interaction.

Clearly not every IPP must necessarily be zero-knowledge.[4](#page-3-3) Thus, the first natural question to ask is whether this notion is meaningful - do there exist languages with non-trivial statistical ZKPPs? We answer this question affirmatively. Moreover, we show that same natural problem considered by [\[BY96\]](#page-39-2) (i.e., verifying that a function is a permutation) has a very efficient zero-knowledge proof of proximity.[5](#page-3-4)

• **Property Testing Lower Bound:** Every tester for PERMUTATION must make at least \Omega(2^{n/2}) queries to the input (and in particular must run in time \Omega(2^{n/2}) ).
• ZKPP **Upper Bound:** PERMUTATION has a 4-round statistical ZKPP in which the verifier runs in poly(n) time.

We remark that in this result, and similarly to other results in the literature on (constant-round) statistical zero-knowledge (SZK), we can only bound the expected running time of our simulator. We also remark that Gur and Rothblum [GR15] give a lower bound on the complexity of non-interactive IPPs (i.e., IPP in which the entire interaction consists of a single message from the prover to the verifier, also known as MAPs) for PERMUTATION, and using that result we obtain a sub-exponential separation between the power of statistical ZKPP vs. MAPs.

Beyond the property of permutation we also consider two additional problems, both of which are graph problems and show that they admit efficient honest-verifier ZKPP protocols.⁶ Both problems that we consider are in the bounded degree graph model, which has been widely studied in the property testing literature [GGR98, GR02].

• 1. **Promise Expansion:** Distinguish graphs with (vertex) expansion \alpha from graphs that are far from even having expansion roughly \beta = \alpha^2/\log(N) .
• 2. **Promise Bipartiteness:** Distinguish bipartite graphs from graphs that are rapidly mixing and far from being bipartite.

A few remarks are in order. We first note that the property testing complexity of both promise problems is \tilde{\Theta}(\sqrt{N}) [GR02, GR11, CS10, NS10, KS11]. Second, the IPP for promise-biparititeness that we use to prove Theorem 1.2 is due to [RVW13] and we merely point out that it is honest-verifier ZKPP. In contrast, the promise-expansion property above was not previously known to admit an (efficient) IPP (let alone an honest-verifier zero-knowledge one). We also remark that both of the problems in Theorem 1.2 refer to promise problems. In particular, we leave open the possibility of a ZKPP for bipartiteness that also handles graphs that are not rapidly mixing, and a ZKPP for expansion that accepts graphs that are \alpha -expanding and rejects graphs that are far from \alpha -expanding (rather than just those that are far from being \alpha^2/\log(N) -expanding as in Theorem 1.2). Lastly, we also leave open the possibility of extending these protocols to be statistical ZKPP against arbitrary cheating verifiers (rather than just honest verifiers).⁷

Limitations of Statistical ZKPP. Given these feasibility results, one may wonder whether statistical ZKPP are as powerful as IPPs. That is, can every IPP be converted to be statistically zero-knowledge with small overhead? We show that this is not the case:

We note that [Theorem 1.3](#page-5-0) is unconditional. Interestingly, if we do allow for assumptions, then we can even separate MAP from SZKPP:

Theorem 1.4 (MAP \ SZKPP, Informally Stated). Assuming certain circuit lower bounds, there exists a property Π that has an MAP in which the verifier runs in polylog(N) time, where N is the input length, but Π does not have a statistical ZPP in which the verifier runs even in time No(1) .*

The circuit lower bound that we use follows from the (highly plausible) assumption that the Arthur-Merlin communication complexity of disjointness is n ε , where n is the input length and ε > 0 is some constant.

1.1.2 The Computational Setting

As is the case in the classical setting, we can obtain much stronger results if we either (1) only require that the simulated view be computationally indistinguishable from the real interaction (i.e., computational zero-knowledge), or (2) only require soundness against efficient cheating provers (i.e., computational soundness or argument).

The following results show that under these relaxations, and assuming reasonable cryptographic assumptions, we can transform many of the known results from the literature of IPPs to be zero-knowledge. Focusing on computational zero-knowledge, we can derive such protocols for any language computable in bounded-depth or in bounded-space, where the verifier runs in roughly ^√ N time.

Theorem 1.6 (Computational ZKPP for Bounded Space, Informally Stated). Assume that there exist one-way functions. Then, every language computable in poly(N)-time and O(N^σ )-space, for some sufficiently small constant σ > 0, has a computational ZKPP, where the verifier (and the simulator) run in time N 1 ² +O(σ) .

Interestingly, if we only require computational soundness, we can do even better. The following result gives statistical zero-knowledge arguments of proximity for every language in NP, and with a verifier that runs in poly-logarithmic time.

We note that [Theorems 1.5](#page-5-1) to [1.7](#page-5-2) strongly rely on (1) results from the literature on IPPs [\[RVW13,](#page-42-2) [RRR16\]](#page-42-3) and interactive arguments of proximity [\[Kil92,](#page-41-5) [BGH](#page-39-6)+06, [DR06\]](#page-39-7), (2) a method introduced by [\[BGG](#page-39-8)+88] for transforming interactive proofs (and arguments) into zero-knowledge ones (while taking some additional care that is not required in the classical setting), and (3) the observation that the verifiers in many of the underlying protocols all make queries that do not depend on messages sent by the prover. See [Section 6](#page-33-0) for details.

1.2 Additional Related Works

A related notion of zero-knowledge PCPs of proximity was recently considered by Ishai and Weiss [IW14]. These are PCP systems in which, the verifier gets oracle access to both the input and to an alleged proof. Similarly to our notion of ZKPP, the verifier runs in sublinear and is assured (with high probability) that the input is close to the language. Here, zero-knowledge means that the verifier learns nothing more than what it could simulate by making few queries to the input. We emphasize that the difference between our model and that of [IW14] is that we consider interactice proofs, whereas [IW14] focus on PCP-style proofs: namely soundness is guaranteed only if the PCP proof string is written in advance.

A recent work by Ben-Sasson et-al. [BCF⁺16] studies zero-knowledge interactive oracle proofs - in a model in which the verifier receives oracle access to the communication tape, but full access to the input.⁸ Our model of ZKPP is reversed - the verifier has oracle access to the input but full access to the communication tape.

Organization. General notations and definitions used throughout the paper are given in Section 2. The model of zero-knowledge proofs of proximity (ZKPP) is defined in Section 3. Our statistical ZKPP protocols for Permutations, Expansion and Bipartiteness, are presented and analyzed in Section 4, while our lower bounds for statistical ZKPP are in Section 5. Finally, in Section 6 we present our results on computational ZK proofs of proximity and the statistical ZK arguments of proximity.

2 Preliminaries

We use calligraphic letters to denote sets, uppercase for random variables, lowercase for values and functions, boldface for vectors, and uppercase sans-serif (e.g., A) for algorithms (i.e., Turing Machines). All logarithms considered here are in base two. Given a random variable X, we write x \leftarrow X to indicate that x is selected according to X. Similarly, given a finite set S, we let S denote that S is selected according to the uniform distribution on S. For an interactive protocol (A, B), let S output in a random execution of (A, B) (usually, A will be some prover and B will be an honest verifier).

The relative distance, over alphabet \Sigma , between two strings x \in \Sigma^n and y \in \Sigma^n is defined by \Delta(x,y) := \frac{|\{x_i \neq y_i : i \in [n]\}|}{n} . If \Delta(x,y) \leq \varepsilon , we say that x is \varepsilon -close to y, and otherwise we say that x is \varepsilon -far from y. Similarly, we define the relative distance of x from a non-empty set S \subseteq \Sigma^n by \Delta(x,S) := \min_{y \in S} \Delta(x,y) . If \Delta(x,y) \leq \varepsilon , we say that x is \varepsilon -close to S, and otherwise we say that x is \varepsilon -far from S. The bitwise exclusive-or between two binary strings x,y \in \{0,1\}^n is denoted by x \oplus y . The statistical distance between two distributions P and Q over a finite set \mathcal{U} , is defined as \mathrm{SD}(P,Q) := \max_{S \subseteq \mathcal{U}} |P(S) - Q(S)| = \frac{1}{2} \sum_{u \in \mathcal{U}} |P(u) - Q(u)| and their product distribution is denoted by P \otimes B .

The image of a function f\colon \mathcal{X} \to \mathcal{Y} is defined as \mathrm{Im}(f) = \{y \in \mathcal{Y}\colon \exists x \in \mathcal{X}\,, f(x) = y\} . An additional notation that we will use is that if S = (S_k)_{k \in \mathbb{N}} and T = (T_k)_{k \in \mathbb{N}} are ensembles of sets, we denote by S \subseteq T the fact that S_k \subseteq T_k for every k \in \mathbb{N} .

2.1 Hashing and Entropy

2.1.1 Entropy

Definition 2.1 (Entropy). The entropy of a discrete random variable X is defined as

The binary entropy function h: [0,1] \to [0,1] is defined to be the entropy of X \sim \text{Bernoulli}(p) , that is, h(p) = -p \log(p) - (1-p) \log(1-p) , where we use the convention that h(0) = h(1) = 0.

Another notion of entropy that we shall use is that that of (conditional) average min-entropy.

The following fact follows immediately from the above definition.

Proof. We prove for the case that n=2. The general case follows by induction.

where the second inequality follows since the first sample from (X,Y) is independent from the second one, and thre third inequality follows since for non-negative functions f,g, it holds that \max_{x_1,x_2} f(x_1) \cdot g(x_2) = \max_{x_1} f(x_1) \cdot \max_{x_2} g(x_2) . Letting h(y) = \max_x \Pr[X = x \mid Y = y] , we write

where the second inequality follows since the first sample of Y is independent of the second one.

2.1.2 Hashing

Definition 2.4 (pairwise independent hash functions). A family of functions \mathcal{H} = \{h : [N] \to [M]\} is pairwise independent if for every x_1 \neq x_2 \in [N] and every y_1, y_2 \in [M] , it holds that

The existence of efficient pairwise independent hash functions is well known.

Dodis et-al. [DORS08], showed the following generalization of the leftover hash lemma, for sources having high conditional min-entropy.

where U_m is distributed uniformly over \{0,1\}^m .

We use standard definitions and results from the literature of statistical zero-knowledge proofs, based mainly on [Vad99].

2.2.1 Statistical Zero-Knowledge Interactive Proofs

In this section we give the (almost) standard definitions for interactive proofs and honest-verifier zero-knowledge proofs.

Definition 2.7 (interactive proofs). Let \Pi = (\Pi_{YES}, \Pi_{NO}) be a promise problem. An interactive proof system for \Pi is an interactive protocol (P, V) with completness error c \colon \mathbb{N} \to [0, 1] and soundness error s \colon \mathbb{N} \to [0, 1] if the following holds for every security parameter k \in \mathbb{N} :

• Completeness: If x \in \Pi_{YES} , then, when V(x, k) interacts with P(x, k), with probability 1 c(k) it accepts.
• Soundness: If x \in \Pi_{NO} , then for every prover strategy \widehat{P} , when V(x,k) interacts with \widehat{P} , with probability 1 s(k) it rejects.

If c(\cdot) and s(\cdot) are negligible functions, we say that (P,V) is an interactive proof system.

The above definition does not deal with the efficiency of the verifier or the prover, unlike the standard definition that requires the verifier to run in time poly(|x|,k). Jumping ahead, this is because in our settings the verifier (and also the simulator) will have only oracle-access to their inputs. We will refer to the efficiency of those algorithms within theorem statements.

Definition 2.8 (view of interactive protocol). Let (P, V) be an r-message interactive protocol. The view of V on a common input x (given as standard input or by oracle access to either of the parties) is defined by \text{view}_{P,V}(x) := (m_1, m_2, \ldots, m_r; \rho) , where m_1, m_2, \ldots, m_r are the messages sent by the parties in a random execution of the protocol, and \rho contains of all the random coins V used during this execution.

We allow probabilistic algorithms to fail by outputting \bot . An algorithm A is useful if \Pr[A(x) = \bot] \le 1/2 for every x, and let \widetilde{A}(x) denote the output distribution of A(x), conditioning on A(x) \ne \bot .

Definition 2.9 (honest-verifier zero-knowledge proofs). Let \Pi = (\Pi_{YES}, \Pi_{NO}) be a promise problem. An interactive proof (P, V) for \Pi is said to be honest-verifier statistical zero-knowledge, if there exists an algorithm S, and a negligible function \mu \colon \mathbb{N} \to [0, 1] such that for every k \in \mathbb{N} and x \in \Pi_{YES} ,

2.2.2 Statistical Distance, Entropy Difference and Sample-Access Proofs

Central in the study of statistical zero-knowledge are problems dealing with properties of distributions encoded by circuits.

Two particularly interesting problems are statistical distance and entropy difference.

Definition 2.11 (Statistical Distance). For any constants 0 \le \beta \le \alpha \le 1 , the promise problem SD^{\alpha,\beta} = (SD^{\alpha,\beta}_{YES}, SD^{\alpha,\beta}_{NO}) is given by

Above, X, Y are distributions encoded by circuits according to Definition 2.10.

Above, X, Y are distributions encoded by circuits according to Definition 2.10.

Both SD and ED are known to be complete for the class of problems that have statistical zero-knowledge proofs (see [Vad99, Theorem 3.5.1]). A fact that we will rely on heavily, is that the zero-knowledge proof-systems for SD and ED only require sample access to the distributions induced by the input circuits. That is, neither the verifier not the simulator in these proof-systems need to actually look at the circuits themselves. Rather, all that they need is the ability to generate random samples from the circuits.

Definition 2.13 (sample-access honest-verifier zero-knowledge proof). Let \Pi be a promise problem whose instances are pairs of distributions encoded by circuits. An honest-verifier zero-knowledge proof system for \Pi is sample-access if both the verifier and the simulator only require oracle access to random samples from the distributions encoded by the input circuits (in addition to explicitly getting the security parameter k).

We can now state the results regarding the zero-knowledge proof systems of SD and ED. In fact, we will not care about SD but rather about statistical closeness, the complement of SD in which the YES and NO instances are switched, namely \overline{\mathsf{SD}^{\alpha,\beta}} := \left(\mathsf{SD}^{\alpha,\beta}_{\mathsf{NO}}, \mathsf{SD}^{\alpha,\beta}_{\mathsf{YES}}\right) .

The protocol establishing Lemma 2.14 reduces, in a black-box way, an instance of \overline{\mathsf{SD}^{\alpha,\beta}} to ED (see [Vad99, Section 4.4]) and then uses the next lemma.

In this section we formally define the model of statistical zero-knowledge proofs of proximity. We follow definition choices from the literature of classical statistical zero-knowledge proofs, mainly based on [Vad99] (see Section 2.2.2). For a discussion about the computational setting, see Remark 3.7 below.

Properties will be identified as sets of functions. A propery is an ensemble \Pi = (\Pi_n, \mathcal{D}_n, \mathcal{R}_n)_{n \in \mathbb{N}} , where \Pi_n \subseteq \mathcal{F}_{\mathcal{D}_n \to \mathcal{R}_n} for every n \in \mathbb{N} , letting \mathcal{F}_{\mathcal{D} \to \mathcal{R}} denote the set of all functions from domain \mathcal{D} to range \mathcal{R} . Equivalently, we sometimes view \Pi_n as a string of length |\mathcal{D}_n| over the alphabet \mathcal{R}_n and write \Pi_n \subseteq \mathcal{R}_n^{|\mathcal{D}_n|} . For a property \Pi and n \in \mathbb{N} , let N_{\Pi}(n) := |\mathcal{D}_n| \cdot \log(|\mathcal{R}_n|) denote the inputsize of \Pi_n . Throughout this paper we remove \Pi and n from the above notation, and simply let N denote the input-size of the relevant property (this will be convenient when defining complexity classes; see ahead). We note that, depending on the context, we will sometimes refer to properties as languages. Lastly, similar to [Vad99], we use a security parameter to control our soundness and zero-knowledge guarantees (see Remark 3.6 for additional details).

Definition 3.1 (interactive proofs of proximity (IPP)). An r-message interactive proof of proximity (IPP), with respect to proximity parameter \varepsilon > 0 , (in short, \varepsilon -IPP) for the property \Pi = (\Pi_n, \mathcal{D}_n, \mathcal{R}_n)_{n \in \mathbb{N}} is an interactive protocol (P, V) between a prover P, which gets free access to an input f: \mathcal{D}_n \to \mathcal{R}_n as well as to \varepsilon , |\mathcal{D}_n| , |\mathcal{R}_n| and k, and a verifier V, which gets oracle access to f as well as free access to \varepsilon , n, |\mathcal{D}_n| , |\mathcal{R}_n| and k. The following conditions are satisfied at the end of the protocol for every k \in \mathbb{N} and large enough n \in \mathbb{N} :

• Completeness: If f \in \Pi_n , then, when V interacts with P, with probability 1 negl(k) it accepts.
• **Soundness**: If f is \varepsilon -far from \Pi_n , then for every prover strategy \widehat{P} , when V interacts with \widehat{P} , with probability 1 negl(k) it rejects.

For t = t(n, |\mathcal{D}_n|, |\mathcal{R}_n|, k, \varepsilon) , IPP[t] denotes the class of properties possessing \varepsilon -IPP in which the verifier's running time is at most O(t). Finally, for a class of functions \mathcal{C} , we denote by IPP[ \mathcal{C}(n, |\mathcal{D}_n|, |\mathcal{R}_n|, k, \varepsilon) ] the class of properties \Pi for which there exists t \in \mathcal{C} such that \Pi \in \mathsf{IPP}[t] .

The probabilities that the verifier rejects in the completeness condition and accepts in the soundness condition are called the completeness error and soundness error, respectively. If the completeness condition holds with probability 1, then we say that the IPP has perfect completeness. A public-coin IPP is an IPP in which every message from the verifier to the prover consists only of fresh random coin tosses.

An IPP is said to have query complexity q\colon \mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times(0,1]\to\mathbb{N} if for every n,k\in\mathbb{N} , \varepsilon>0 , x\in\mathcal{F}_{\mathcal{D}_n\to\mathcal{R}_n} , and any prover strategy \widehat{\mathsf{P}} , the verifier \mathsf{V} makes at most q(n,|\mathcal{D}_n|,|\mathcal{R}_n|,k,\varepsilon) queries to x when interacting with \widehat{\mathsf{P}} . The IPP is said to have communication complexity c\colon\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times(0,1]\to\mathbb{N} if for every n,k\in\mathbb{N},\varepsilon>0 , and x\in\mathcal{F}_{\mathcal{D}_n\to\mathcal{R}_n} the communication between \mathsf{V} and \mathsf{P} consists of at most c(n,|\mathcal{D}_n|,|\mathcal{R}_n|,k,\varepsilon) bits.

Our main (but not exclusive) focus in this work is on properties that have IPPs in which the verifier's running time (and thus also the communication and query complexities) is poly-logarithmic in the input size and polynomial in the security parameter k and in the reciprocal of the proximity parameter 1/\varepsilon , that is, the class IPP[poly(log(N), k, 1/\varepsilon )].

An IPP that consists of a single message sent from the prover (Merlin) to the verifier (Arthur) is called Merlin-Arthur proof of proximity (MAP). We extend all the above notations to Merlin-Arthur proofs of proximity in the natural way.

Before defining general ZKPPs, we first consider zero-knowledge with respect to honest verifiers.

Definition 3.2 (honest-verifier zero-knowledge proof of proximity (HV-SZKPP, HV-PZKPP)). Let (P, V) be an interactive proof of proximity for a property \Pi = (\Pi_n, \mathcal{D}_n, \mathcal{R}_n)_{n \in \mathbb{N}} . The protocol (P, V) is said to be honest-verifier statistical zero-knowledge with simulation overhead s, for some function s \colon \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}

If the negl(k) can be replaced with 0 in the above equation, (P, V) is said to be honest-verifier perfect zero-knowledge with simulation overhead s.

For t = t(n, |\mathcal{D}_n|, |\mathcal{R}_n|, k, \varepsilon) , HV-SZKPP[t, s] (resp., HV-PZKPP[t, s]) denotes the class of properties possessing honest-verifier statistical (resp., perfect) zero-knowledge proof of proximity with simulation overhead s in which the verifier's running time is at most O(t).

We say that the query complexity of a simulator S is q' : \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times (0,1] \to \mathbb{N} if for every n, k \in \mathbb{N} , \varepsilon > 0 , f \in \mathcal{F}_{\mathcal{D}_n \to \mathcal{R}_n} , S_n^f makes at most q'(n, |\mathcal{D}_n|, |\mathcal{R}_n|, k, \varepsilon) queries to f.

A typical setting (that we will focus on) is when the verifier's running time is \operatorname{poly}(\log(N), k, 1/\varepsilon) , namely poly-logarithmic in the input length N and polynomial in the security parameter k and in the proximity parameter 1/\varepsilon . In this setting we often allow for \operatorname{polynomial} simulation overhead, that is the simulator's running time is also \operatorname{poly}(\log(N), k, 1/\varepsilon) . Specifically, we denote by \operatorname{HV-SZKPP}[\operatorname{poly}(\log(N), k, 1/\varepsilon)] the class of properties \Pi \in \operatorname{HV-SZKPP}[t, s] for t = \operatorname{poly}(\log(N), k, 1/\varepsilon) and s = \operatorname{poly}(t, \log(N), k, 1/\varepsilon) . The class \operatorname{HV-PZKPP}[\operatorname{poly}(\log(N), k, 1/\varepsilon)] is similarly defined.

Another setting of interest is when the verifier's running time is N^{\delta} poly (k, 1/\varepsilon) , for some constant \delta \in (0,1) . In this setting, unlike the previous one, allowing the simulation overhead to be polynomial will give the simulator much greater computational power than the verifier (e.g., if \delta = 1/2 and s is quadratic in the verifier's running time, then the simulator can run in time O(N) and in particular may read the entire input). In this setting we aim for the simulation overhead to be linear in the verifier's running time (but it can be polynomial in k and 1/\varepsilon ). ¹¹

When the simulation overhead is clear from context (as it will almost always be the case) we omit it from the notation.

If the negl(k) can be replaced with 0 in the above equation, (P, V) is said to be resp., cheating-verifier perfect zero-knowledge with simulation overhead s.

For t = t(n, |\mathcal{D}_n|, |\mathcal{R}_n|, k, \varepsilon) , SZKPP[t, s] (resp., PZKPP[t, s]) denotes the class of properties possessing cheating-verifier statistical (resp., perfect) zero-knowledge proof of proximity with simulation overhead s in which the verifier's running time is at most O(t).

Expected Simulation Overhead. Definition 3.3 requires that the running time of the simulator always be bounded. Similarly to many results in the ZK literature, in some cases we can only bound the simulator's expected running time.

Definition 3.4 (cheating-verifier ZKPP with expected simulation (ESZKPP, EPZKPP)). Let (P, V) be an interactive proof of proximity for a property Π = (Πn, Dn, Rn)n∈N. The protocol (P, V) is said to be cheating-verifier statistical zero-knowledge with expected simulation overhead s if it satisfies the same requirement as in [Definition 3.3](#page-12-1) except that we only bound the expected running time of the simulator.

The classes ESZKPP[t, s] and EPZKPP[t, s] are defined analogous to SZKPP[t, s] and PZKPP[t, s] from [Definition 3.3.](#page-12-1)

Unless explicitly saying otherwise, all zero-knowledge protocols we discuss are cheatingverifier ones.

As in the honest-verifier case, a typical setting is that in which the verifier's running time is poly-logarithmic in the input size N and polynomial in the security parameter k and in 1/ε, and the simulator's (possibly only expected and not strict) running time is polynomial in the running time of the cheating-verifier that it simulates, poly-logarithmic in N and polynomial in k and 1/ε. Specifically, if we allow the cheating-verifier the same computational powers as the honestverifier, then both the honest-verifier and every simulator run in time poly(log(N), k, 1/ε). We let ESZKPPpoly(log(N), k, 1/ε) be the class of properties Π ∈ ESZKPP[t, s] fort = poly(log(N), k, 1/ε) and s = poly(t ^Vb, log(N), k, ¹/ε). The class PZKPPpoly(log(N), k, 1/ε), poly is similarly defined.

We conclude this section with a few remarks on the model and the above definitions.

In this section, we look at functions f : {0, 1} ⁿ → {0, 1} ⁿ and consider the property of being a permutation. That is, we would like to distinguish between functions that are a permutation from those that are far from being a permutation.

We define the permutation property as \mathsf{PERMUTATION} = \left(\mathsf{PERMUTATION}_n, \{0,1\}^n, \{0,1\}^n\right)_{n \in \mathbb{N}} .

It is not difficult to see that any property tester for PERMUTATION must make at least \Omega(\sqrt{N}) queries, where N=2^n . To see this, consider the following two distributions: (1) a random permutation over \{0,1\}^n ; and (2) a random function from \{0,1\}^n to \{0,1\}^n . The first distribution is supported exclusively on YES instances whereas it can be shown that the second is, with high probability, far from a permutation. However, if a tester makes q \ll \sqrt{N} queries, then in both cases, with high probability, its view will be the same: q distinct random elements. The property testing lower bound follows.

As a matter of fact, Gur and Rothblum [GR15] have shown that the verifier in every MAP (i.e., non-interactive proof of proximity, see [GR16]) for PERMUTATION must make either \Omega(N^{1/4}) queries or use a proof of length \Omega(N^{1/4}) .

In this section, we show that the PERMUTATION property has a 4-message (statistical) zero-knowledge proof of proximity with respect to cheating verifiers. We note that we only bound the expected number of queries and running time of the simulator of our protocol. We leave it as an open problem to obtain a protocol (possibly with more rounds of interaction) in which one can show a high probability bound on the query complexity and running times of the simulator.

Before stating the theorem a word on notation. In Section 3 we gave the prover and the verifier, as explicit inputs, the domain and range sizes — both, in the case of the permutation property, are 2^n . In this section, for convenience, instead of giving 2^n as an explicit input, we will simply give n. Relevant complexity measures (e.g., running time, query and communication complexity) will similarly be functions of n.

• 1. The interaction consists of four messages and the total communication is O(n^2k/\varepsilon^2) bits.
• 2. V_{perm} 's running time is poly(n, k, 1/\varepsilon) and V_{perm} 's query complexity is O(nk/\varepsilon^2) .
• 3. If f \in \mathsf{PERMUTATION}_n , then for every auxiliary input z, \mathsf{S}_{\mathsf{perm}_{[z]}} 's expected running time and query complexity, given access to a (possibly cheating) verifier \widehat{\mathsf{V}} , are O(t_{\widehat{\mathsf{V}}}(\varepsilon,n,k,z)) + \mathsf{poly}(n,k,1/\varepsilon) and O(q_{\widehat{\mathsf{V}}}(\varepsilon,n,k,z) + nk/\varepsilon^2) respectively, where t_{\widehat{\mathsf{V}}}(\varepsilon,n,k,z) and q_{\widehat{\mathsf{V}}}(\varepsilon,n,k,z) are the running time and query complexity of \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) .

(Note that the input of PERMUTATION_n has size n \cdot 2^n , so a polynomial dependence on n translates into a poly-logarithmic dependence on the input-size.)

Combined with the aforementioned MAP lower bound for PERMUTATION, we obtain that the complexity of ZKPP (with expected simulation bounds) can be sub-exponentially smaller than those of MAPs (and therefore also of property testers).

Remark 4.3. We mention that in [Item 3](#page-14-0) in the theorem statement, when the simulator simulates the view of an interaction with the honest verifier Vperm, its strict (rather than expected) query complexity is exactly equal to the query complexity of the verifier.

The rest of this section is dedicated to proving [Theorem 4.2.](#page-14-1)

Consider the following simple IPP for PERMUTATION (based on the [\[BY96\]](#page-39-2) protocol). Given oracle access to a function f : {0, 1} ⁿ → {0, 1} n , the verifier chooses a random r ∈ {0, 1} ⁿ and sends r to the prover. The prover computes z = f −1 (r) and sends it to the verifier. The verifier checks that indeed f(z) = r and if so accepts.

Clearly if f is a permutation then the verifier in this protocol accepts with probability 1, whereas if f is far from a permutation, then with some non-negligible probability the verifier chooses r which does not have a pre-image under f. In such a case the prover cannot make the verifier accept and so the protocol is sound.

It is also not hard to see that this protocol is honest-verifier zero-knowledge.[12](#page-15-0) However, it is not cheating-verifier zero-knowledge: a cheating verifier could learn the inverse of some arbitrary r of its choice.

In order to make the protocol zero-knowledge, intuitively, we would like to have a way for the prover and verifier to jointly sample the element r such that both are assured that it is uniform. For simplicity let us focus on the task of just sampling a single bit σ. The specific properties that we need are

• 1. If f is a permutation then the prover is assured that the σ is random.
• 2. If f is far from being a permutation then the verifier is assured that σ is random.

In fact, the transformation of general honest-verifier statistical zero-knowledge proofs to cheatingverifier ones (see [\[Vad99,](#page-42-6) Chapter 6]) implements a sub-routine achieving a generalization of the above task, assuming full access to the input. We give a simple solution for our specific case. That is, using only oracle access to a function that is either a permutation or far from any permutation.

We proceed to describe a simple procedure for sampling such a random bit σ. First, the verifier chooses at random x ∈ {0, 1} ⁿ and a pairwise independent hash function h : {0, 1} ⁿ → {0, 1} and sends y = f(x) and h to the prover. The prover now chooses a random bit r ∈ {0, 1} and sends r to the verifier. The verifier now sends x to the prover who checks that indeed f(x) = y. The random bit that they agree on is σ = r ⊕ h(x).

From the prover's perspective, if f is a permutation then y fully determines x and so r (which is chosen uniformly at random after y is specified) is independent of h(x). Hence, σ = r ⊕ h(x) is uniformly random bit. On the other hand, from the verifier's perspective, if f is far from being a permutation, then, intuitively, even conditioned on the value y there still remains some entropy in x (indeed, x is essentially uniform among all the pre-images of y).[13](#page-15-1) Now, using a variant of the leftover hash lemma, we can argue that h(x) is close to random. Actually, since the leftover

Pperm's Input: A function f : {0, 1} ⁿ → {0, 1} ⁿ, proximity parameter ε > 0 and security parameter k. Vperm's Input: ε, n, k and oracle access to f.

• 1. Both parties set t = d(n + 1)/εe and s = dk/εe.
• 2. Vperm samples x = (x1, x2, . . . , xt·s) ← {0, 1} n ^t·^s and h ← Hn·t·s,n·s. *[a](#page-16-0)* Vperm computes yⁱ = f(xi) for every i ∈ [t · s] (by querying f), and sends y = (y1, y2, . . . , yt·s) and h to Pperm.
• 3. Pperm samples r = (r1, r2, . . . , rs) ← {0, 1} n s and send them to Vperm.
• 4. Vperm sends x to Pperm.
• 5. Pperm checks that f(xi) = yⁱ , for every i ∈ [t · s]. If any check fails then Pperm sends ⊥ and aborts.
• 6. Pperm sends z = (z1, z2, . . . , zs) to Vperm, where zⁱ = f −1 rⁱ ⊕ h(x)ⁱ , for every i ∈ [s]. *[b](#page-16-1)*
• 7. Vperm accepts if f(zi) = rⁱ ⊕ h(x)ⁱ for every i ∈ [s], and otherwise it rejects.

``` aRecall that Hn,m = {h: {0, 1} n → {0, 1} m} is a family of pairwise independent hash functions. See Fact 2.5. bRecall that ⊕ stands for the bitwise exclusive-or. Also, we view h(x) ∈ {0, 1} n·s as h(x) = (h(x)1, h(x)2, . . . , h(x)s) such that h(x)i ∈ {0, 1} n . ```

hash lemma implies that pairwise independent hash functions are strong extractors, we have that h(x) is close to random even conditioned on h and therefore also conditioned on r (which is a randomized function of h). Thus, we obtain that σ = r⊕h(x) is close to uniformly random bit and so our procedure satisfies the desired properties.

We proceed to the description of our actual protocol, which is based on the foregoing ideas. The protocol Pperm, Vperm is given in [Fig. 1.](#page-16-2)

It is easy to verify that Pperm, Vperm has the desired round complexity, query complexity and verifier's running time, where we use the fact that O(n ²k/ε) bits suffice for describing the pairwise independent hash function in the protocol (see [Fact 2.5\)](#page-8-1).

To see that completeness holds observe that if f : {0, 1} ⁿ → {0, 1} n is a permutation, and the two parties follow the protocol, then indeed f(xi) = yⁱ and f(zi) = f(f −1 (rⁱ ⊕h(x)i)) = rⁱ ⊕h(x)ⁱ for every i ∈ [t · s], and therefore the parties complete the interaction and the verifier accepts.

It remains to show that the soundness and zero-knowledge conditions hold. Soundness follows from the following lemma, which is proved in [Section 4.1.2.](#page-17-0)

Simulator's Input: \varepsilon , n, k, auxiliary input z, oracle access to f: \{0,1\}^n \to \{0,1\}^n and access to (possibly cheating) verifier \hat{V} .

• 1. Run \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) using random coins \rho to get \overline{\mathbf{y}}=(y_1,y_2,\ldots,y_{ts}) and h.
• 2. Sample \overline{\mathbf{r}} = (r_1, r_2, \dots, r_s) \leftarrow (\{0, 1\}^n)^s and give them to \widehat{\mathbf{V}}_{[z]} as the answers from \mathsf{P}_{\mathsf{perm}} .
• 3. Continue to run \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) to get \overline{\mathbf{x}}=(x_1,x_2,\ldots,x_{ts}) , the values \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) sends to \mathsf{P}_{\mathsf{perm}} in the third message of the protocol.
• 4. If there exists i \in [t \cdot s] such that f(x_i) \neq y_i , output (\overline{\mathbf{y}}, h, \overline{\mathbf{r}}, \overline{\mathbf{x}}, \perp, \rho) .
• 5. Otherwise, repeat the following:
• (a) Sample \overline{\mathbf{r}'} = (r'_1, r'_2, \dots, r'_s) \leftarrow (\{0, 1\}^n)^s and for every i \in [s] , set r''_i = f(r'_i) \oplus h(\overline{\mathbf{x}})_i .
• (b) Rewind \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) to the point it is waiting for the second message of the protocol using \rho again as the random coins (i.e., step 3 of the protocol). Give \overline{\mathbf{r}''}=(r_1'',r_2'',\ldots,r_{ts}'') as the answers from \mathsf{P}_{\mathrm{perm}} .
• (c) Continue to run \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) to get \overline{\mathbf{x}'}=(x_1',x_2',\ldots,x_{ts}') , the values \widehat{\mathsf{V}}_{[z]}^f(\varepsilon,n,k) sends to \mathsf{P}_{\mathsf{perm}} in the third message of the protocol.
• (d) If f(x_i) = y_i for every i \in [ts] , output (\overline{\mathbf{y}}, h, \overline{\mathbf{r''}}, \overline{\mathbf{x'}}, \overline{\mathbf{r'}}, \rho) and halt. Otherwise, go back to 5a.

Lemma 4.5. Let n, k \in \mathbb{N} , let z \in \{0, 1\}^* , let f \in \mathsf{PERMUTATION}_n , let \widehat{\mathsf{V}} be some verifier strategy and let \mathsf{S}^f_{[z]}(\varepsilon, n, k, \widehat{\mathsf{V}}) be the output of \mathsf{S}_{\mathsf{perm}} when running on input \varepsilon, n, k , auxiliary input z, with oracle access to \widehat{\mathsf{V}} and access to \widehat{\mathsf{V}} . Then:

Moreover, the expected running time and query complexity of S_{[z]}^f(\varepsilon, n, k, \widehat{V}) are as in Item 3 of the theorem statement.

This concludes the proof of Theorem 4.2 (modulo the proofs of Lemma 4.4 and Lemma 4.5 which are proved next).

4.1.2 Analyzing Soundness — Proof of Lemma 4.4

Before proving Lemma 4.4 we show two basic, but useful, properties of functions that are \varepsilon -far from permutations. The first property is that the image size of such functions cannot be too large.

Proof. We prove the contrapositive. Let f: \{0,1\}^n \to \{0,1\}^n and suppose that |\text{Im}(f)| > (1-\varepsilon) \cdot 2^n . We show that f is \varepsilon -close to a permutation f': \{0,1\}^n \to \{0,1\}^n .

Start by setting f'(x) = f(x) for every x. Repeat the following process until \text{Im}(f') = \{0,1\}^n : take y \notin \text{Im}(f) ; find x \neq x' such that f'(x) = f'(x') (such x, x' must exist since at this point f' is not a permutation); set f'(x) = y.

In every iteration |\operatorname{Im}(f)| increases by one. The above process started with |\operatorname{Im}(f')| > (1-\varepsilon) \cdot 2^n , and thus takes less than \varepsilon \cdot 2^n iterations. It follows that f' and f disagree on at most \varepsilon \cdot 2^n inputs, or in other words f' is \varepsilon -close to f. Moreover, f' is a permutation, since \operatorname{Im}(f') = \{0,1\}^n .

Next we show that even after seeing a random element in the image of a function that is \varepsilon -far from permutation, its preimage still has some entropy. The specific notion of entropy we use is average min-entropy.¹⁴

Proof. For y \in \{0,1\}^n , let f^{-1}(y) = \{x \in \{0,1\}^n : f(x) = y\} . Fix y \in \text{Im}(f) . For x \in f^{-1}(y) , it holds that \Pr[X = x | Y = y] = 1/|f^{-1}(y)| , while for x \notin f^{-1}(y) , it holds that \Pr[X = x | Y = y] = 0 . Thus, \max_x \Pr[X = x | Y = y] = 1/|f^{-1}(y)| . Moreover, it holds that \Pr[Y = y] = |f^{-1}(y)|/2^n . Finally, for every y \notin \text{Im}(f) , it holds that \Pr[Y = y] = 0 . Hence,

where the inequality follows from Fact 4.6.

We are now ready to prove Lemma 4.4.

Proof of Lemma 4.4. Let \widehat{P} be a (cheating) prover strategy. We assume without loss of generality that \widehat{P} is deterministic (by fixing the best choice of random coin tosses).

Let \overline{\mathbf{X}} , H, \overline{\mathbf{Y}} , \overline{\mathbf{R}} and \overline{\mathbf{Z}} be the (jointly distributed) random variables induced by the values of \overline{\mathbf{x}} , h, \overline{\mathbf{y}} , \overline{\mathbf{r}} and \overline{\mathbf{z}} respectively, in a random execution of (\widehat{\mathsf{P}},\mathsf{V}_{perm}) and let \mathrm{out}(\widehat{\mathsf{P}},\mathsf{V}_{perm}) be the random variable induced by \mathsf{V}_{perm} 's output in the same random execution (i.e., \mathrm{out}(\widehat{\mathsf{P}},\mathsf{V}_{perm}) \in \{accept, reject\} ).

By the definition of the permutation protocol, it holds that

Note that R = (R1, . . . , Rs) is a function of Y and H, determined by Pb. It follows that

(2)

where U = (U1, U2, . . . , Us) is uniform over ({0, 1} n ) s . We bound both terms in the right-hand side of [Equation \(2\).](#page-19-1) For the first term, note that Uⁱ is independent of U^j for i 6= j, and thus

(3)

where the second equality follows from the fact that for every r ∈ {0, 1} n , r ⊕ Uⁱ is uniform over {0, 1} ⁿ and the last inequality follows from [Fact 4.6.](#page-17-3)

As for the second term of [Equation \(2\),](#page-19-1) by [Fact 2.3](#page-7-2) it holds that

(4)

where the inequality follows from [Claim 4.7.](#page-18-1) Applying the generalized leftover hash lemma [\(Lemma 2.6\)](#page-8-2) we now obtain that:

(5)

Plugging [Equations \(2\),](#page-19-1) [\(3\)](#page-19-2) and [\(5\)](#page-19-3) into [Equation \(1\),](#page-18-2) we have

where the second inequality follows from our setting of t = d(n + 1)/εe and s = dk/εe and the third inequality follows from the fact that 1 − x ≤ 2 −x for any x ≥ 0. Thus, the verifier accepts with probability that is exponentially vanishing in k, and in particular negligible.

4.1.3 Analyzing Zero-Knowledge — Proof of [Lemma 4.5](#page-16-5)

Let ^Vb be a cheating verifier strategy and fix an input ^{f ∈} PERMUTATION. For simplicity, and without loss of generality, we assume that ^Vb is deterministic.[15](#page-19-4)

Throughout this proof we fix an auxiliary input z to S_{perm} and remove it from the notation of both the simulator and the (possibly cheating) verifier (since all S_{perm} does with its auxiliary input is to provide it to \widehat{V} , both algorithms get the same auxiliary inputs).

Recall that we let S^f(\varepsilon, n, k, \widehat{V}) denote the algorithm defined by running S_{perm} on input \varepsilon, n, k , with oracle access to \widehat{V} . Note that S^f(\varepsilon, n, k, \widehat{V}) halts almost surely, namely the probability that it never halts is zero.

The following claim shows show that the output distribution of S_{perm} is identical to the view of \widehat{V} . Later, in Claim 4.9, we will bound the (expected) running time and query complexity of S_{perm} .

Proof. Let \overline{\mathbf{X}} , H, \overline{\mathbf{Y}} , \overline{\mathbf{R}} and \overline{\mathbf{Z}} be the (jointly distributed) random variables induced by the values of \overline{\mathbf{x}} , h, \overline{\mathbf{y}} , \overline{\mathbf{r}} and \overline{\mathbf{z}} respectively, in a random execution of (\mathsf{P}_{\mathsf{perm}}, \widehat{\mathsf{V}}) .

First observe that since \widehat{\mathbf{V}} is deterministic, its first message (\overline{\mathbf{y}},h) is fixed and so \overline{\mathbf{Y}}=\overline{\mathbf{y}} and H=h. Also, since the verifier is deterministic, there exists a function v such that \overline{\mathbf{X}}=v(\overline{\mathbf{R}}) . Lastly, observe that there also exists a function u such that \overline{\mathbf{Z}}=u(\overline{\mathbf{R}}) .

The view of the verifier is therefore:

(7)

Similarly, let \overline{\mathbf{X}}_{S} , H_{S} , \overline{\mathbf{Y}}_{S} , \overline{\mathbf{Z}}_{S} be the (jointly distributed) random variables induced by the output of a random execution of S^{f}(\varepsilon, n, k, \widehat{V}) . We need to show that:

(8)

First observe that by construction \overline{\mathbf{Y}_{S}} = \overline{\mathbf{y}} and H_{S} = h . Also observe that no matter what value \overline{\mathbf{R}_{S}} obtains, in all steps in which the simulator might generate an output, it holds that \overline{\mathbf{X}_{S}} = v(R_{S}) , where the function v is as defined above. Similarly it holds that \overline{\mathbf{Z}_{S}} = u(R_{S}) , where u was defined above.

Thus, Equation (8) reduces to showing that \overline{\mathbf{R}} and \overline{\mathbf{R}_S} are identically distributed. Since \overline{\mathbf{R}} is uniform all we need to show is that \overline{\mathbf{R}_S} is also uniformly distributed.

Let

where \overline{\mathbf{y}}=(y_1,\ldots,y_{ts}) (and recall that \overline{\mathbf{y}} was fixed). Namely, \mathcal{A} contains those elements in (\{0,1\}^n)^s , that had they been sent by \mathsf{P}_{\mathsf{perm}} as its second message, the verifier \widehat{\mathsf{V}} would have sent \overline{\mathbf{x}} that are not the preimages of \overline{\mathbf{y}} . Finally, let p=\Pr_{r\leftarrow(\{0,1\}^n)^s}[r\notin\mathcal{A}] and fix r^\in(\{0,1\}^n)^s . We show that \Pr[R_{\mathsf{S}}=r^]=1/(2^n)^s . The proof now splits according to r^* .

r^ \in \mathcal{A} : The only way \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) would output r^ is by choosing it in Step 2. Since \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) chooses the values in this step uniformly at random from (\{0,1\}^n)^s , it follows that \Pr[R_{\mathsf{S}} = r^*] = 1/(2^n)^s .

r^ \notin \mathcal{A} : The only way \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) would output r^ is by choosing r''=r^* in Step 5a. The probability that \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) reaches Step 5 at all is p. Having reached Step 5, and since f is a permutation, every time that \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) runs Step 5a, it samples r'' uniformly at random from (\{0,1\}^n)^s , independent of all previous messages it received from \widehat{\mathsf{V}} . In Step 5 \mathsf{S}^f(\varepsilon,n,k,\widehat{\mathsf{V}}) is performing rejection sampling until it gets r'' \notin \mathcal{A} and then sets \overline{\mathbf{R}}_{\mathsf{S}} = r'' . All in all, it holds that

(Note that we can condition on the event r'' \notin A since r^* \notin A and so \Pr[r'' \notin A] > 0 .)

Hence, \overline{\mathbf{R}}_{S} is uniform over (\{0,1\}^n)^s . This completes the proof of Claim 4.8.

Proof. We prove this part by first showing the expected number of calls it makes to \hat{V} is constant.

Let T be the number of times S^f(\varepsilon,n,k,\widehat{V}) executes Steps 3 and 5c when \widehat{V} uses the coins \rho . Note that T is equal to the number of times the simulator invokes \widehat{V} . Let \mathcal{A} be as defined in Equation (9) (recall that \mathcal{A} was defined as the set of vectors \overline{\mathbf{r}} for which the verifier \widehat{V} responds with \overline{\mathbf{x}} that do not all correspond to the respective preimages of \overline{\mathbf{y}} ). Let p = \Pr_{r \leftarrow (\{0,1\}^n)^s}[r \notin \mathcal{A}] .

Let E denote the event that S^f(\varepsilon, n, k, \widehat{V}) reaches Step 5. By construction, \Pr[T = 1] = \Pr[\neg E] = 1-p . Moreover, it holds that the random variable T|E is drawn from a geometric distribution with parameter p. Since the latter has expectation 1/p we have that:

(10)

Thus, in expectation, the simulator invokes \hat{V} at most twice.

Every time S^f(\varepsilon,n,k,\widehat{V}) calls \widehat{V} , it samples a random string in \{0,1\}^{n\cdot s} , evaluates some h\in\mathcal{H}_{n\cdot t\cdot s,n\cdot s} , and makes O(t\cdot s) calls to f. Recall that t_{\widehat{V}} and q_{\widehat{V}} denote the running time and query complexity of \widehat{V} , respectively. The expected running time of S^f(\varepsilon,n,k,\widehat{V}) is thus at most O(t_{\widehat{V}})+\operatorname{poly}(t,s,n)=O(t_{\widehat{V}})+\operatorname{poly}(n,k,1/\varepsilon) (note that by Fact 2.5, evaluation of h can be done in time \operatorname{poly}(t,s,n) ). The expected query complexity of S^f(\varepsilon,n,k,\widehat{V}) is thus at most O(q_{\widehat{V}}+t\cdot s)=O(q_{\widehat{V}}+nk/\varepsilon^2) .

4.2 Promise Expansion is in HV-SZKPP

In this section we consider the property of a graph being a "good" expander, in the bounded degree graph model (see [GGR98, GR02]). Recall that in bounded degree graph model, the input graph is represented by an adjacency list and so, using a single query, the verifier can find the i^{\rm th} neighbor of a vertex v.

The property of being a good expander was first considered by Goldreich and Ron [GR11]. They showed that any tester for the (spectral) expansion of a graph on n vertices must make at least \Omega(\sqrt{n}) queries. [GR11] also suggested a testing algorithm that matches this bound and conjectured its correctness. Czumaj and Sohler [CS10] focused on vertex expansion and proved that the [GR11] tester accepts graphs that are good expanders and rejects graphs that are far from having even much worst expansion. More specifically, [CS10] showed that the [GR11] tester accepts graphs with (vertex) expansion \alpha and rejects graphs that are far from having even (vertex) expansion \Theta\left(\frac{\alpha^2}{\log(n)}\right) . Lastly, Nachmias and Shapira [NS10] and Kale and Seshadhri[KS11] improved [CS10]'s result and showed that the tester in fact rejects graphs that are far from having expansion \Theta\left(\alpha^2\right) . We show how to apply [CS10]'s approach to get an honest-verifier statistical zero-knowledge proof of proximity with only a poly-logarithmic dependence on n, as long as we have a similar type of gap between YES and NO instances as in [CS10].

Formally, a vertex expander is defined as follows.

Definition 4.10 (Vertex expander). Let \alpha > 0 . A graph G = (\mathcal{V}, \mathcal{E}) is an \alpha -expander if for every subset \mathcal{U} \subseteq \mathcal{V} of size |\mathcal{U}| \leq |\mathcal{V}|/2 , it holds that |N(\mathcal{U})| \geq \alpha \cdot |\mathcal{U}| , where N(\mathcal{U}) := \{v \in \mathcal{V} \setminus \mathcal{U} : \exists u \in \mathcal{U} \text{ such that } (v, u) \in \mathcal{E}\} .

Throughout this section we fix a bound d on the degree of all graphs (which we think of as constant). We identify graphs on n vertices as functions G \colon [n] \times [d] \to [n] \cup \{\bot\} such that G(u,i) = v if v is the i'th neighbor of a vertex u and G(u,i) = \bot if u has less than i neighbors.

Definition 4.11. Let d \in \mathbb{N} . For n \in \mathbb{N} and \alpha = \alpha(n) > 0 , let

Let \beta = \beta(n) \in (0, \alpha(n)] . We define the expander promise problem (see Remark 3.5) as

where \mathsf{EXPANDER}_{\mathsf{YFS}\,n}^{d,\alpha,\beta} = \mathsf{EXPANDER}_n^{d,\alpha} and \mathsf{EXPANDER}_{\mathsf{NO}\,n}^{d,\alpha,\beta} = \mathsf{EXPANDER}_n^{d,\beta} .

That is, YES instances of the promise problem are graphs that are \alpha -expanders and NO instances are graphs that are far from even being \beta -expanders, for \beta \leq \alpha .

Proof of Theorem 4.12. We prove Theorem 4.12 by reducing graph expansion to the problem of testing whether two distributions are statistically close. The reduction is such that we can sample from each distribution using few queries to our original input graph. Given this reduction, we

can now use Lemma 2.14 which gives an honest-verifier statistical zero-knowledge proof for verifying whether the distribution induced by two circuits on a random input is statistically close. A crucial observation is that neither the verifier nor the simulator in the latter protocol need to actually look at their input circuits. Rather, they only need to be able to draw relatively few random samples from the distribution induced by the circuit on a random input. Intuitively, by applying our reduction we therefore obtain an honest-verifier statistical zero-knowledge proof for EXPANDER ^{d,\alpha,\beta} .

We proceed to give an overview of our reduction from EXPANDER ^{d,\alpha,\beta} to statistical closeness. The reduction, which is randomized, chooses uniformly at random a vertex u and considers two distributions: the first, denoted by P_u^\ell , outputs the last vertex in a random walk of length \ell = \Theta\left(\frac{d^2\log(n)}{\alpha^2}\right) starting at u; the second, denoted by U_{[n]} , is uniform over all vertices. Observe that both distributions can be sampled using relatively few queries to the input graph.

We observe that if the graph is an \alpha -expander (i.e., a YES instance) then for any choice of u, it holds that \mathrm{SD}\big(P_u^\ell,U_{[n]}\big)\approx 0 (and so the two distributions are close). On the other hand, [CS10] showed that if the graph is far from being a \Theta\big(\frac{\alpha^2}{d^2\log(n)}\big) -expander (i.e., a NO instance), then there exists a set of vertices \mathcal U with |\mathcal U|=\Omega(n) such that for every u\in\mathcal U , it holds that \mathrm{SD}\big(P_u^\ell,U_{[n]}\big)\gg 0 . Thus, in the NO case, with constant probability (over the choice of u), our reduction generates distributions that are statistically far. We proceed to the actual proof.

Our protocol uses the following lazy random walk on the graph G.

Assume without loss of generality that \varepsilon \leq 0.1 , where \varepsilon is the proximity parameter.¹⁶ Let h:[0,1] \to [0,1] be the binary entropy function (recall that h(p) := -p \log(p) - (1-p) \log(1-p) ). By a routine calculation, it holds that

(11)

Thus, we can apply Lemma 2.14, with respect to the constants \alpha=0.2 and \beta=0.01 to obtain an honest verifier statistical zero knowledge protocol \left(\mathsf{P}^{(\cdot,\cdot)}(k),\mathsf{V}^{(\cdot,\cdot)}(k)\right) for \overline{\mathsf{SD}^{0.2,0.01}} . Thus, \left(\mathsf{P}^{(\cdot,\cdot)}(k),\mathsf{V}^{(\cdot,\cdot)}(k)\right) is a statistical zero-knowledge protocol for distinguishing between YES instances, which are pairs of circuits that have statistical distance at most 0.01, from NO instances, which are pairs of circuits whose statistical distance is at least 0.2.¹⁷ Using the latter, we construct a protocol \left(\mathsf{P}_{\text{expan}},\mathsf{V}_{\text{expan}}\right) for verifying expansion, which is given in Fig. 3.

The next two lemmas show the completeness and soundness of the expander protocol.

Prover's Input: A graph G: [n] \times [d] \to [n] , expansion parameter \alpha > 0 , proximity parameter \varepsilon > 0 and security parameter k.

• 1. V_{\text{expan}} samples u \leftarrow [n] and sends u to P_{\text{expan}} .
• 2. The parties construct two oracle circuits: one encodes the distribution P_u^{\ell} for \ell = \left\lceil \frac{8d^2}{\alpha^2} \ln(\sqrt{n}/0.01) \right\rceil ; the other encodes U_{[n]} , the uniform distribution on the graph's vertices.
• 3. The parties run the protocol \left(\mathsf{P}^{P_u^\ell,U_{[n]}}(k),\mathsf{V}^{P_u^\ell,U_{[n]}}(k)\right) , where \left(\mathsf{P}^{(\cdot,\cdot)},\mathsf{V}^{(\cdot,\cdot)}\right) is the protocol for \overline{\mathsf{SD}^{0.2,0.01}} from Lemma 2.14.

Lemma 4.14 is proven in Section 4.2.1 via a standard analysis of random walks on expanders.

Lemma 4.15 is proven in Section 4.2.2 via a combinatorial property of graphs that are \varepsilon -far from β-expanders, shown by [CS10].

As for honest-verifier zero-knowledge, let S^{(\cdot,\cdot)} denote the simulator of the protocol for \overline{SD^{0.2,0.01}} from Lemma 2.14. Note that if G is an \alpha -expander, the same mixing argument used to establish completeness implies that SD(P_u^\ell,U_{[n]}) \leq 0.01 , for every vertex u (see Section 4.2.1). Hence, for every vertex u it holds that S^{P_u^\ell,U_{[n]}}(k) simulates \left(\mathsf{P}^{P_u^\ell,U_{[n]}}(k),\mathsf{V}^{P_u^\ell,U_{[n]}}(k)\right) with simulation deviation at most \mu(k) , for some negligible function \mu . Our simulator for the expansion protocol, denoted by S_{\text{expan}} will choose a vertex u uniformly at random, and output \left(u,\mathsf{S}^{P_u^\ell,U_{[n]}}(k)\right) . Now observe that S_{\text{expan}} 's deviation from V_{\text{expan}} 's view in (\mathsf{P}_{\text{expan}},\mathsf{V}_{\text{expan}}) is precisely equal to the expected deviation, over the choice of a random vertex u, of \mathsf{S}^{P_u^\ell,U_{[n]}}(k) from the view of \mathsf{V}^{P_u^\ell,U_{[n]}} in the protocol \left(\mathsf{P}^{P_u^\ell,U_{[n]}}(k),\mathsf{V}^{P_u^\ell,U_{[n]}}(k)\right) . Since the latter is bounded by \mu for every choice of u, the expected deviation is bounded by \mu(k) as well.

So far we have shown that the expander protocol (Fig. 3) has \operatorname{negl}(k) completeness error, 1-(\varepsilon/24-\operatorname{negl}(k)) soundness error and is honest-verifier statistical zero-knowledge. To reduce the soundness error the parties will repeat the above protocol in parallel for \operatorname{poly}(k)/\varepsilon times. Since honest-verifier statistical zero-knowledge is preserved under parallel repetition, and parallel repetition reduces the soundness errors of IPPs at an exponential rate (see, e.g., [GGR15, Appendix A]), the resulting protocol is an honest-verifier statistical zero-knowledge proof of proximity.

Finally, we argue about the efficiency of V_{\text{expan}} (the analysis of the simulator's efficiency is similar). The verifier V_{\text{expan}} needs to provide V^{P_u^\ell,U_{[n]}}(k) samples from P_u^\ell and U_{[n]} . Generating a random sample from U_{[n]} is easy and requires O(\log n) random coins. Generating a random sample from P_u^\ell is standard as well, requires \operatorname{poly}(\ell,d) = \operatorname{poly}(\log n) random coins and oracle calls

to the input graph. By Lemma 2.14, it follows the V_{\text{expan}} 's running time (accounting for the parallel repetition as well) is at most \text{poly}(\log(n), 1/\varepsilon, k) .

4.2.1 Analyzing Completeness — Proving Lemma 4.14

Lemma 4.14 is an easy implication of the following standard result regarding random walks on expanders.

Proof of Lemma 4.14. From the choice of \ell and Lemma 4.16, it holds that

for every vertex u. Let W be the random variable induced by the values of u chosen in step 1 of a random execution of the protocol It follows that

where the last inequality follows from the completeness property of (P, V) (Lemma 2.14).

4.2.2 Analyzing Soundness — Proving Lemma 4.15

The soundness of the expander protocol follows from the following combinatoral property of graphs that are far from expanders.

Recall that V_{\text{expan}} 's first steps is to choose uniformly at random a vertex u. This u will belong to the set \mathcal{U} from the Lemma 4.17 with probability at least \varepsilon/24 . Conditioned on the latter, we claim that the input to \left(\mathsf{P}^{P_u^\ell,U_{[n]}}(k),\mathsf{V}^{P_u^\ell,U_{[n]}}(k)\right) is a NO input and so soundness follows immediately from the soundness of the protocol for \overline{\mathsf{SD}} (Lemma 2.14).

from the soundness of the protocol for \overline{\mathsf{SD}} (Lemma 2.14). We argue soundness with respect to \beta = \left\lfloor \frac{\alpha^2}{20 \cdot c \cdot d^2 \cdot \log(\sqrt{n}/0.01)} \right\rfloor , where c = c(d) > 0 is the constant guaranteed to exist by Lemma 4.17.

Proof of Lemma 4.15. Let \widehat{\mathsf{P}} be any prover strategy. Let W be the random variable induced by the values of u chosen in step 1 of a random execution of the protocol and let \mathcal{U} be the set guaranteed to exist by Lemma 4.17. It holds that

We bound both terms in the right-hand side of Equation (12). Lemma 4.17 yields that \Pr[W \notin \mathcal{U}] \leq 1-\varepsilon/24 . As for the second term, Lemma 4.17 yields that \operatorname{SD}(P_w^\ell, U_{[n]}) \geq \frac{1-2\varepsilon}{4} \geq 0.2 for every w \in \mathcal{U} (note that \beta was chosen so that \ell \leq 1/(10c\beta) and that we assumed above that \varepsilon < 0.1 ). It follows that

where the last inequality follows from the soundness properties of V (Lemma 2.14).

In this section we consider the property of a graph being bipartite in the bounded degree model (we introduced this model in Section 4.2). The property of being a bipartite graph was first considered by Goldrich and Ron [GR02, GR99]. They showed a tester for bipartiteness of graphs with n vertices which makes at most \tilde{O}(\sqrt{n}) queries. They also showed a matching lower bound, namely that any such tester must make at least \Omega(\sqrt{n}) queries.

Rothblum et al. [RVW13] gave an interactive proof of proximity for the following promise version of this property in which the verifier's running time is \Theta(\log n) . In this version, YES instances are bipartite graphs. NO instances, in addition to being far from bipartite, are also well-mixing, namely that a random walk of \Theta(\log n) steps ends at each vertex with probability at least 1/2n (e.g., expanders). We denote this property by BIPARTITE. In [RVW13]'s protocol, the verifier takes a random walk of length \Theta(\log n) starting at a randomly chosen vertex (in each step it performs a self-loop with probability at least 1/2; see Definition 4.13). The verifier then sends the prover the start and end vertices of the walk and asks the prover to tell him the parity of the number of non-self-loop steps it took during the walk.

If the graph is bipartite, then the parity of the number of non-self-loops is equal to the parity of the shortest simple path from the start vertex to the end vertex. [RVW13] showed that if the graph is far from being bipartite and well-mixing, then the chance of taking a path of even non-self-loop steps is close to that of taking a path of odd non-self-loop steps. Hence, any cheating prover will fail to convince the verifier.

In fact, it is easy to see that the above protocol is also an honest-verifier perfect zero-knowledge proof of proximity. The simulator will simply act as the verifier: take a random walk and output the parity of the non-self-loop steps in this walk (which the simulator knows since it performs the walk). Since this result follows immediately from [RVW13]'s protocol, we only state an informal version of the it here, and refer the reader to [RVW13] for formal definitions and description of the protocol.

It is an interesting open question to show a cheating-verifier zero-knowledge proof of proximity for BIPARTITE.

5 Limitations of SZKPP

In light of the positive results in Section 4 an important questions rises:

Does every property that has a sub-linear IPP also have a sub-linear statistical zero-knowledge IPP?

We give a negative answer to the above question.[18](#page-27-2) Actually we show two incomparable lower bounds:

• 1. There exists a property Π that has an IPP in which the verifier runs in poly-logarithmic time, but the verifier in any zero-knowledge proof of proximity for Π cannot run in polylogarithmic time. (Actually we can even show that such a verifier cannot run in time No(1) , see [Remark 5.6\)](#page-28-0).Thus, this lower bound can be viewed as a separation between the class IPPpoly(log(N), k, 1/ε) and HV-ESZKPPpoly(log(N), k, 1/ε) .
• 2. We show an additional lower bound which separates HV-ESZKPPpoly(log(N), k, 1/ε) even from a weaker class - namely the class of languages admitting *non-interactive* proofs of proximity, also known as Merlin-Arthur proofs of proximity or MAPs [\[GR16\]](#page-41-0). However, in contrast to the previous separation from IPPs, this result is conditional: we can only prove it assuming a (very plausible) circuit lower bound. Specifically, we assume that (randomized) DNF⊕, namely DNF formulas composed with one layer of parity gates (see [\[CS16,](#page-39-10) [ABG](#page-38-3)+14] and references therein), cannot compute the disjointness function. This circuit lower bound is implied by the assumption that the Arthur-Merlin communication complexity of disjointness is n ε , for inputs of length n and some constant ε > 0.

We show that there exists a property Π ∈ IPP[poly(log(N), k, 1/ε)] but Π ∈/ HV-ESZKPP[poly(log(N), k, 1/ε)]. Namely, Π that has an efficient IPP, which unconditionally cannot have such a statistical zeroknowledge IPP. [19](#page-27-3)

The proof of [Theorem 5.1](#page-27-4) is done in two steps. The first step is to argue the existence of a property Π which has an interactive proof of proximity with a large number of rounds and polylog(N)-time verifier , but such that in every 2-message interactive proof of proximity for Π, the verifier's running time must be N^δ , for some constant δ > 0. Actually, such a result was recently established by Gur and Rothblum [\[GR17\]](#page-41-2):

The second step in proving [Theorem 5.1](#page-27-4) is a general round reduction transformation for any honest-verifier statistical zero-knowledge proof of proximity. Namely, we would like a procedure that takes any many-messages honest-verifier zero-knowledge proof of proximity and turns it into a 2-message honest-verifier zero-knowledge proof of proximity while only slightly deteriorating the verifier's and simulator's running times. Specifically, we show the following lemma.

simulator's expected running time is bounded by t_{S}(\varepsilon, N, k) = t'_{S}(\varepsilon, N) \cdot \mathsf{poly}(k) and for every value of \varepsilon , the function t'_{S}(\varepsilon, \cdot) is monotone non-decreasing.

Then, \Pi has a 2-message honest verifier statistical zero-knowledge \varepsilon -IPP such that for every input length N and security parameter k the running time of the verifier is \mathsf{poly}(t_{\mathsf{S}}(\varepsilon, N, k'), k) , for k' = \mathsf{poly}(t'_{\mathsf{S}}(\varepsilon, N)) .

For the setting of poly-logarithmic zero-knowledge proof of proximity, Lemma 5.3 can be stated as follows.

The proof of Lemma 5.3 is a direct application of the proof that the promise problem Entropy Difference (ED, see Definition 2.12) is complete for the class SZK (see [Vad99]). That proof takes an instance x of any promise problem \Pi = (\Pi_{YES}, \Pi_{NO}) \in SZK and efficiently constructs two distributions X and Y such that if x \in \Pi_{YES} then H(X) \ge H(Y) + 1 , and if x \in \Pi_{NO} then H(Y) \ge H(X) + 1 . That proof goes on to show a zero-knowledge protocol to distinguish between the case that H(X) \ge H(Y) + 1 and the case that H(Y) \ge H(X) + 1 . Two important points regarding that proof: (1) sampling from X and Y can be done by running (many times) the simulator for the original problem \Pi ; (2) the protocol for ED consists of only two messages and requires only sample access to X and Y (we stated this fact in Lemma 2.15).

In our settings, we can view a property \Pi as a promise problem where functions possessing the property are in \Pi_{NO} . Then, we can have the verifier "run" the reduction to ED and apply the sample-access protocol for ED. The unbounded prover will behave as in the protocol for ED. Recall that the original simulator (i.e., the one for the property's IPP) required only oracle access to the input function. Since sampling from the distributions only requires running the original simulator, the new verifier can implement this step with only oracle access to the input function and with only polynomial overhead to the running time of the original simulator. We defer the actual proof of Lemma 5.3 to Appendix B.1.

Using Lemmas 5.2 and 5.3 we can now prove Theorem 5.1.

Proof of Theorem 5.1. Let Π be the property guaranteed to exist by Lemma 5.2. Assume towards a contradiction that \Pi \in \mathsf{HV-ESZKPP}[\mathsf{poly}(\log(N), k, 1/\varepsilon)] . Namely, Π has an honest-verifier statistical zero-knowledge interactive proof of proximity with the simulator's expected running time being (\log(N))^{\alpha} \cdot k^{\beta} \cdot (1/\varepsilon)^{\gamma} for constants \alpha, \beta, \gamma > 0 . Applying Lemma 5.3 with respect to Π yields that Π has a 2-message \varepsilon -IPP (P, V), with V's running time being (\log(N))^{\delta_1} \cdot k^{\delta_2} \cdot (1/\varepsilon)^{\delta_3} for constants \delta_1 = \delta_1(\alpha, \beta), \delta_2, \delta_3 = \delta_3(\beta, \gamma) > 0 .

Set \varepsilon = 1/10 and k such that the soundness error of (P, V) is at most 1/3. Note that in this setting, V's running time is O(\log(N)^{\delta_1}) = \text{poly}(\log(N)) . This is a contradiction to Lemma 5.2. \square

a simulator with expected running time No(1) · ^α ·k β · (1/ε) γ , [Lemma 5.3](#page-27-1) yields that Π has a 2 ε-IPP in which the verifier runs in No(1) time, in contradiction to [Lemma 5.2.](#page-27-5)

We show that there exists a property Π ∈ MAPpoly(log(N), k, 1/ε) but, assuming certain circuit lower bounds, it holds that Π 6∈ HV-ESZKPPpoly(log(N), k, 1/ε)

Let t-DNF^⊕ refer to depth 3 circuits, whose output gate is an bounded fan-in OR gate, intermediate level are composed of fan-in t AND gates and third layer is composed of (unbounded fan-in) parity gates. The size of a t-DNF^⊕ gate is the fan-in of its top gate. A randomized t-DNF^⊕ simply refers to a distribution over t-DNF^⊕ circuits. We say that a randomized t-DNF^⊕ circuit C : {0, 1} ^k → {0, 1} computes a function f if for every x ∈ {0, 1} k it holds that Pr[C(x) = f(x)] ≥ 2/3.

For any k ∈ N and strings x, y ∈ {0, 1} k , we define DISJk(x, y) = 1 if for every i ∈ [k] it holds that either xⁱ = 0 or yⁱ = 0 and DISJk(x, y) = 0 otherwise. The following conjecture states that small randomized DNF^⊕ circuits cannot compute DISJ. [20](#page-29-1)

We remark that a randomized t-DNF^⊕ circuit of size S yields an Arthur-Merlin communication complexity with complexity log(S) + t. [21](#page-29-2) To the best of our knowledge, it is believed that the Arthur-Merlin communication complexity of disjointness is believed to be Ω(k) (which would imply [Conjecture 5.7](#page-29-3) with δ = 1). We mention that proving any non-trivial Arthur-Merlin communication complexity lower bound is a notorious open problem.

We begin by an outline of the proof. Our main tool will be a binary linear error-correcting C : {0, 1} ^k → {0, 1} n , with constant relative distance and almost-linear[22](#page-29-4) blocklength, which is also locally testable and locally decodable. A code C : {0, 1} ^k → {0, 1} n is locally testable if there exists a procedure that makes only few queries to a word w ∈ {0, 1} n , and determines with high probability if it is a codeword (i.e., if w = C(x) for some message x ∈ {0, 1} k ) or far from the code (see [Definition 5.9](#page-30-0) for the formal definition). A code is locally decodable if there exists a procedure that takes as input an index i ∈ [k] and a word w ∈ {0, 1} n close to some codeword C(x), makes only few queries to w, and outputs xⁱ with high probability (see [Definition 5.10](#page-30-1) for the formal definition).

The property that we consider is the Code Intersection (CI) property. This property consists of pairs of codewords (C(x), C(y)), coded under the foregoing code, such that DISJ(x, y) = 0 (i.e., x and y intersect). This problem was previously considered by Gur and Rothblum [\[GR16\]](#page-41-0) who showed that it has a very efficient MAP (we re-prove this fact since we use a slightly different code).

Indeed, it is easy to see that CI has a very efficient MAP. Merlin simply sends to Arthur the index i on which x and y intersect. Arthur, using the local testability, will verify that the input is close to a pair of codewords, and then locally decodes xⁱ and yⁱ . Arthur accepts iff xⁱ = yⁱ = 1. This proof of proximity, however, reveals a lot to Arthur (and in particular is not zero-knowledge). Specifically, Arthur learns the index of the intersection. As a matter of fact, this is not a coincidence. We show that, assuming that [Conjecture 5.7](#page-29-3) holds, the property CI does not have any honestverifier zero-knowledge IPP with poly-logarithmic complexity.

To see how we prove the lower bound, consider the promise problem Code Disjointness (CD), in which the YES instances are pairs of codewords (C(x), C(y)) such that DISJ(x, y) = 1, and NO instances are pairs of codewords (C(x), C(y)) such that DISJ(x, y) = 0. Note that NO instances of CD are in the property CI. Moreover, YES instances of CD are δ(C)/2-far from CI, where δ(C) is the relative distance of the code C.

Assume, toward a contradiction, that CI has an honest-verifier statistical zero-knowledge IPP with poly-logarithmic complexity. We argue that this implies that the complement promise problem of CD has a constant-round IPP. The latter fact basically follows from the fact that entropy difference (ED) is complete for the class of promise problems having a statistical zero-knowledge proof, and is itself closed under complement.

Thus, we have constructed an IPP which accepts inputs from CD and rejects inputs from CI. Using a result of Rothblum et-al. [\[RVW13\]](#page-42-2), we can derive from this IPP a quasi-polynomial size randomized DNF for the same promise problem. We further observe that since the code C is a linear code, we have obtained a circuit that computes the disjointness function on input (x, y) by first applying a linear transformation and then the aforementioned randomized DNF. Or in other words, a quasi-polynomial sized DNF^⊕ circuit. This contradicts [Conjecture 5.7.](#page-29-3)

We proceed to the formal proof of [Theorem 5.8.](#page-29-5) We begin with definitions and notations. An error-correcting code is an injective function C : {0, 1} ^k → {0, 1} n . The code C is said to have relative distance δ(C) if for any x 6= x ⁰ ∈ {0, 1} k it holds that ∆(C(x), C(x 0 )) ≥ δ(C). [23](#page-30-2) Throughout this work we deal with (uniform) algorithms, and so we will need (families of) error-correcting codes. Formally, for a parameters k = k(`) ≥ 1 and = n(`) ≥ k(`) we define an ensemble of error correcting code as an ensemble C = C` : {0, 1} ^k(`) → {0, 1} n(`) `∈N of error-correcting codes. An ensemble of error correcting codes C = (C`)`∈<sup>N</sup> is said to have relative distance δ(C) if for all sufficiently large `, each code C` in the ensemble has relative distance δ(C).

We next formally define locally testable and decodable codes.

• **Completeness:** *For every* x ∈ {0, 1} k(`) *it holds that* Pr-T C`(x) (`) = 1 = 1*.*
• **Soundness:** *For every* w ∈ {0, 1} n(`) *it holds that* Pr[T ^w(`) = 0] ≥ Ω(∆(w,Im(C`)))*, where* ∆(w,Im(C`)) *is the relative distance of* w *from the code.*[24](#page-30-3)

n ²⁴Recall that the relative distance of x ∈ {0, 1} n from a non-empty set S ⊆ {0, 1} is defined as ∆(x, S) = miny∈S ∆(x, y).

Definition 5.10 (locally decodable codes (c.f. [KT00])). Let t: \mathbb{N} \to \mathbb{N} . A ensemble of error-correcting code C = (C_{\ell}: \{0,1\}^{k(\ell)} \to \{0,1\}^{n(\ell)})_{\ell \in \mathbb{N}} is t-locally-decodable if there exists a constant \delta_{\mathsf{radius}} \in (0, \delta(C)/2) and a probabilistic algorithm (decoder) D that, given oracle access to w \in \{0,1\}^n and explicit inputs i \in [k] and \ell \in \mathbb{N} , runs in time t(\ell) and satisfies the following.

• Completeness: For every i \in [k(\ell)] and x \in \{0,1\}^{k(\ell)} , it holds that \Pr[D^{C(x)}(i) = x_i] = 1 .
• Soundness: For every i \in [k(\ell)] and every w \in \{0,1\}^{n(\ell)} with \Delta(w,C(x)) \leq \delta_{\mathsf{radius}} , it holds that \Pr[D^w(i) = x_i] \geq 2/3 .

We use the following well-known fact.

See Appendix B.3 for a sketch of the construction (which is basically the concatenation of the low degree extension code, over a field of poly-logarithmic size, with a good binary code).

Using Lemma 5.11, we can now define the property Code Intersection.

Definition 5.12 (Code Intersection). Let C = (C_{\ell})_{\ell \in \mathbb{N}} be the code guaranteed to exist by Lemma 5.11. For \ell \in \mathbb{N} , let

We define the Code Intersection property as CI = (CI_{\ell}, [2n(\ell)], \{0, 1\})_{\ell \in \mathbb{N}} .

The proof of Theorem 5.8 follows immediately from the next two lemmas, proven in Sections 5.2.1 and 5.2.2.

5.2.1 Proving Lemma 5.13

Consider the protocol (P_{CI}, V_{CI}) from Fig. 4. Perfect completeness follows from the perfect completeness in the local testing and decoding procedures. We proceed to argue that soundness holds.

Fix \varepsilon > 0 , sufficiently large \ell \in \mathbb{N} and w = (w_1, w_2) \in \{0, 1\}^{2 \cdot n(\ell)} such that w is \varepsilon -far from \text{Cl}_{\ell} . We assume without loss of generality that \varepsilon < \delta_{\text{radius}} (otherwise "reset" \varepsilon to \delta_{\text{radius}} ). We consider two cases:

\Delta(w_1, \operatorname{Im}(C_\ell)) \ge \varepsilon/2 or \Delta(w_2, \operatorname{Im}(C_\ell)) \ge \varepsilon/2 : Let j \in \{1, 2\} such that \Delta(w_j, \operatorname{Im}(C_\ell)) \ge \epsilon/2 . By the soundness condition of the tester T, it holds that

The Code Intersection Protocol (P_CI, V_CI)

Prover's Input: A pair of strings (w_1, w_2) \in \{0, 1\}^{2 \cdot n(\ell)} and proximity parameter \varepsilon > 0 . Verifier's Input: \ell , n(\ell) , \varepsilon and oracle access to (w_1, w_2) .

Let C be the code ensemble from Lemma 5.11.

Let T be the tester from Definition 5.9 with respect to C.

Let \delta_{\text{radius}}(C) and D be the decoding radius and decoder, respectively, from Definition 5.10 with respect to C.

• 1. P_{CI} finds i \in [k(\ell)] such that w = (C_{\ell}(x), C_{\ell}(y)) for some x, y \in \{0, 1\}^{k(\ell)} and x_i = y_i . Sends i to V_{CI} .
• 2. V_{CI} acts as follows:
• (a) Set \varepsilon = \min\{\varepsilon, 2\delta_{\mathsf{radius}}(C)\}.
• (b) Run \mathsf{T}^{w_1}(\ell) and \mathsf{T}^{w_2}(\ell) and reject if any of them rejects.
• (c) Accept if \mathsf{D}^{w_1}(i,\ell) = \mathsf{D}^{w_2}(i,\ell) = 1 , and otherwise reject.

\Delta(w_1,\operatorname{Im}(C_\ell)) \leq \varepsilon/2 and \Delta(w_2,\operatorname{Im}(C_\ell)) \leq \varepsilon/2 : Fix a cheating prover \widehat{\mathsf{P}} . Assume without loss of generality that \widehat{\mathsf{P}} is deterministic and let i^ be the index it sends to \mathsf{V}_{\mathsf{Cl}} in step 1. Let x,y \in \{0,1\}^{k(\ell)} such that \Delta(w_1,C_\ell(x)) \leq \varepsilon/2 and \Delta(w_2,C_\ell(y)) \leq \varepsilon/2 (such x and y are unique since \varepsilon \leq \delta_{\mathsf{radius}}(C) ). Moreover, as w is \varepsilon -far from \mathsf{Cl}_\ell , it must be that either x_{i^}=0 or y_{i^}=0 . Observe that if x_{i^}=0 , then by the soundness of the decoding procedure, with probability 2/3, the decoder will output 0 in which case our verifier rejects. The case that y_{i^*}=0 is analyzed similarly.

Combining both conditions, it holds that \Pr[V_{Cl}^{w}(\varepsilon, n(\ell)) \text{ rejects}] \ge \min\{\Omega(\varepsilon/2), 1/3\} = \Omega(\varepsilon) .

So far we have shown that the code intersection protocol (Fig. 4) has prefect completeness and soundness error 1 - O(\varepsilon) . To reduce the soundness error it suffices to have the verifier repeat its check \operatorname{poly}(k)/\varepsilon times.²⁶ As shown in [GR16] this reduces the soundness error to 2^{-k} and so the resulting protocol is an \varepsilon -MAP.

Finally, it is easy to verify that the ultimate verifier run in time \mathsf{poly}(\log(\ell), k, 1/\varepsilon) which, since the input length (i.e., 2 \cdot n(\ell) ) is \mathsf{poly}(\ell) , is \mathsf{poly}(\log(N), k, 1/\varepsilon) .

5.2.2 Proof of Lemma 5.14

We prove the contrapositive. Assume that \mathsf{CI} \in \mathsf{HV}\text{-}\mathsf{ESZKPP}\big[\mathsf{poly}(\log(N), k, 1/\varepsilon)\big] and consider the promise problem of Code Disjointness.

Definition 5.15 (Code Disjointness). For \ell \in \mathbb{N} , let

Let

.

Note that the input length here is N = 2 · n(`) = O˜(` ¹.01). Hence, the query complexity and communication complexity of the IPP are poly(log(`), k, 1/ε).

We will use the zero-knowledge proof of proximity for CI to design a randomized DNF^⊕ circuit that solves disjointness. Note that by definition CDNO,` = CI` .

Observe that every string w ∈ CDYES,` is δ(C)/2-far from CI` . Thus, an (honest-verifier) statistical zero-knowledge IPP for CI immediately yields an (honest-verifier) statistical zero-knowledge proof for the complement of CD. Recall that in [Section 5.1](#page-27-0) we used that entropy difference (ED) is complete for the class SZK. Here, we will use this fact again, plus that there is an easy reduction from ED to its complement, to show the following claim, proven in [Appendix B.2.](#page-44-2)

• *1. The verifier gets* ` *as explicit input and oracle access to* w ∈ CDYES,` ∪ CDNO,`*.*
• *2. The completeness and soundness errors are both* 1/3*.*
• *3. The verifier's running time is* poly(log(`))*.*
• *4. The parties exchange a constant number of messages.*

Using the Goldwasser-Sipser [\[GS89\]](#page-41-8) transformation from private-coin to public-coin interactive proofs and the Babai-Moran [\[BM88\]](#page-39-11) round reduction (see [\[RVW13,](#page-42-2) Section 4] for more details). We obtain a 2-message Arthur Merlin interactive proof, where the verifier runs in time polylog(`). Applying an additional transformation from such proof-systems to randomized DNFs due to [\[RVW13\]](#page-42-2) (see also [\[GR17\]](#page-41-2)), we can obtain the following:

By observing that all w ∈ CDY ES,` ∪ CDNO,` are composed of two codewords, and the the code is a binary linear error correcting code, [Claim 5.17](#page-33-2) implies that there exists a randomized polylog(`)-DNF<sup>⊕</sup> circuit of size 2 polylog(`) that computes DISJk(`) . This contradicts [Conjecture 5.7.](#page-29-3) This concludes the proof of [Section 5.2.1.](#page-31-2)

Given that, it is tempting to ask why we did not use the locally testable and (relaxed) decodable codes of Golderich et-al. [\[GGK15\]](#page-40-11). Indeed, their codes have constant-query whereas the code that we used requires poly-logarithmic query complexity. The only reason that we do not use the [\[GGK15\]](#page-40-11) code is that the computational complexity of this code was not analyzed in [\[GGK15\]](#page-40-11).

In this section we show that, assuming reasonable cryptographic assumptions (specifically, the existence of one-way or collision-resistant hash functions), a large class of IPPs and arguments of proximity²⁷ can be transformed to be zero-knowledge. As a consequence, using the results of [RVW13, RRR16, Kil92, BGH+06, DR06] we obtain computational ZK proofs of proximity for small-depth and for small-space computations, and statistical ZK arguments of proximity for all of NP.

Our transformation should be contrasted with an analogous transformation of Ben-Or etal. [BGG⁺88] for classical public-coin interactive proofs (and arguments). Indeed, our transformation is based on the main idea of [BGG⁺88]. However, in contrast to their result, our transformation does not apply to arbitrary public-coin IPPs. Rather, it only applies to such IPPs in which the queries that the verifier makes do not depend on messages sent by the prover. We say that such IPPs make prover-oblivious queries.

Definition 6.1. We say that an IPP makes prover-oblivious queries if the input locations that the verifier queries are fully determined by its random coin tosses and the answers to previous queries that it made. That is, the queries do not depend on messages sent by the prover.

Thus, an IPP with prover-oblivious queries can be thought of as a two steps process. In the first step the verifier can make queries to its input but it is not allowed to interact with the prover. In the second step, the parties are allowed to interact but the verifier is no longer allowed to query the input.²⁸

Interestingly (and crucially for our purpose), the general purpose IPPs and arguments of proximity in the literature are indeed public-coin and make only prover-oblivious queries. Using this fact, together with our transformation, we obtain general purpose ZK proofs of proximity.

Our main transformation is summarized in the following two theorems.

Furthermore, if there exist collision-resistant hash functions, then the round complexity of the foregoing argument-system can be reduced to (\ell + O(1)) .

Our proof of Theorems 6.2 and 6.3 is based on the idea, which originates in the work of Ben-Or et-al. [BGG⁺88], of having the prover commit to its messages rather than sending them in the clear. Since the protocol is public-coin the verifier can continue the interaction even though it does

not see the actual contents of the prover's messages. After all commitments have been sent, the verifier only needs to check that there exist suitable decommitments that would have made the underlying IPP verifier accept. Since the commitment hides the contents of the messages, it cannot do so by itself and we would like to use the prover. At this point, one could try to naively argue that the residual statement is an NP statement, and so we can invoke a general purpose zero-knowledge protocol for NP (e.g., the classical [GMW91] protocol or the more efficient [IKOS09] protocol).²⁹

Herein arises the main difficulty with this approach. While the statement that the verifier needs to check at the end of the interaction does consist of an existential quantifier applied to a polynomial-time computable predicate, the latter predicate makes oracle access to the input x and so we do not know how to express it as an NP statement. To resolve this difficulty, we restrict our attention to verifiers that make prover-oblivious queries. Thus, our verifier can actually make its queries before and we can construct a NP statement that refers to the actual values that it reads from the input. At this point we can indeed invoke a general purpose zero-knowledge protocol for NP and conclude the proof.

Lastly, we remark that the specific flavor of soundness and zero-knowledge that we obtain depends on the commitment scheme we use. Specifically, instantiating the above approach with a computationally hiding and statistically binding commitment scheme yields a computational zero-knowledge proof of proximity, whereas a statistically hiding and computationally binding one yields a statistical zero-knowledge argument of proximity.

As noted above, we need the following result from [IKOS09]:

Actually, since the running times are not specified in [IKOS09], we give an overview of the construction in Appendix B.4.

We proceed to give a proof sketch of Theorem 6.2 and note that Theorem 6.3 is proved similarly (using statistically hiding commitments).³⁰

Proof Sketch of Theorem 6.2. The existence of one-way functions implies the existence of the following cryptographic protocols that we will use:

• A computationally hiding and statistically binding commitment scheme [Nao91, HILL99]. Moreover, after one initial set-up message from the receiver to the sender (where this setup can be re-used for a polynomial number of commitments), the commitment scheme is non-interactive: the sender only needs to send a single message to the receiver. (This commitment scheme will be used to derive the first part of Theorem 6.2.)

• Computational zero-knowledge proofs for any language in NP in which the verifier runs in time that is almost linear in the complexity of the witness relation (see Lemma 6.4).

Let (P,V) be an \ell -round public-coin IPP for \mathcal L with prover oblivious queries. We describe the construction of a computational zero-knowledge proof of proximity for \mathcal L . As alluded to above, the construction of a statistical zero-knowledge argument of proximity is similar, except that we replace the computationally hiding and statistically binding commitment with one that is statistically hiding and computationally binding, and replace the computational zero-knowledge proof for NP with a statistical zero-knowledge argument.

We proceed to describe the computational ZKPP (P', V') for \mathcal{L} , on input x of length N, security parameter k and proximity parameter \epsilon . First, (P', V') run the setup for the commitment scheme. After this initial step, the interaction consists of two main parts. In the first part, P' and V' emulate the interaction between P and V, where P' only commits to the messages that P would have sent. Since the protocol (P, V) is a public-coin protocol, the verifier V' can continue the interaction without actually knowing the contents of the messages that it receives (since V' only needs to sample and send random coin tosses).

Then, in the second part, V' has already obtained commitments c_1, \ldots, c_\ell to some messages \alpha_1, \ldots, \alpha_\ell that P would have sent. At this point we would like P' to prove the statement:

d_i \text{ is a decommitment of } c_i \text{ with respect to message } \alpha_i \text{, for every } i \in [r] \exists d_1, \dots, d_\ell, \alpha_1, \dots, \alpha_\ell \text{ such that} \qquad \text{and} \mathsf{V}^x(N, \varepsilon, k, (\alpha_1, \beta_1, \dots, \alpha_\ell, \beta_\ell)) = 1. (14)

The problem that we encounter is that Equation (14) is not precisely an NP statement since it refers to oracle access to a given string x.³¹ To overcome this problem, we use our assumption that V makes prover oblivious queries. Hence, the queries that V makes depend only on its own random coin tosses (and answers to previous queries that it has made), but not on the messages sent by P. Denote by Q(x; \rho) the sequence of (possibly adaptive) queries that V makes on input x and random string \rho . Since Q(x, \rho) depends only on the randomness (and, possibly, on answers to previous queries to x), the verifier V' can sample \rho at random and generate this set. We can now re-state Equation (14) as:

which is in fact an NP relation, for which P' has a witness. Therefore, using our assumption that one-way functions exist, there exists a computational zero-knowledge proof for Equation (15). P'

and V' engage in this proof-system and V' accepts or rejects accordingly. (To actually run this proof-system V' first shares \rho with P' - but it does so only after they have completed the emulation of (P, V).)

Completeness of (P', V') follows from the completeness of (P, V) and the (perfect) completeness of the [IKOS09] zero-knowledge proof. The analysis of soundness and zero-knowledge is standard and we omit them from this preliminary version.

We proceed to analyze the efficiency of the proof-system. We consider the three phases of interactions separately:

• **Setup Phase:** First, the two parties set up the commitment scheme this step is done using a single round of communication and with complexity poly(k) for both parties.
• Commitment Phase: Each bit that P sends to V in the original protocol is emulated by a (non-interactive) commitment (with a poly(k) overhead). Messages sent from V to P are unchanged (recall that these refer to random coin tosses). Thus, the round complexity of this part is \ell and there is a poly(k) overhead to the running time of both parties.
• Final Phase: V' first sends the random string used by the underlying V. This introduces a t_{\mathsf{V}}(N,k,\varepsilon) overhead to both parties. Then, both parties run the [IKOS09] protocol on an NP statement that can be verified in time t=t_{\mathsf{V}}(N,\varepsilon,k)\cdot\mathsf{poly}(k) . The [IKOS09] verifier runs in time that is O(t)=t_{\mathsf{V}}(N,\varepsilon,k)\cdot\mathsf{poly}(k) whereas the [IKOS09] prover runs in time \mathsf{poly}(t)=\mathsf{poly}(t_{\mathsf{V}}(N,\varepsilon,k),k) . The number of rounds is \mathsf{poly}(k) .

To obtain our ZKPP results, we will combine Theorem 6.2 with known results from the literature. Specifically, we will use the following results: (where throughout N denotes the input length, k the security parameter, and \varepsilon the security parameter).

We remark that the fact that the verifier makes prover oblivious queries is not stated explicitly in the above works but can be verified by inspection.³² Combining Theorems 6.5 and 6.6 with Theorem 6.2, and Theorem 6.7 with Theorem 6.3 we derive the following corollaries:

Corollary 6.8 (Computational ZKPP for Bounded Depth). Assume that there exist one-way functions. Then, every language in logspace-uniform NC, has a (polylog(N) + poly(k))-round computational zeroknowledge proof of ε-proximity, for ε = n −1/2 . The verifier runs in time N ² +o(1) · poly(k) and the (honest) prover runs in time poly(N, k). The simulation overhead is s(t ^Vb, N, k, ε) = ^{t Vb} · poly(k), for (malicious) verifiers running in time t ^{Vb = t V}b(N, k, ε).

Corollary 6.10 (Statistical Zero-Knowledge Arguments). Assume that there exist collision resistant hash functions. Then, every language in NP, has a constant-round statistical zero-knowledge argument of ε-proximity, for every value of ε > 0. The verifier runs in time poly(log(N), k, 1/ε) and the (honest) prover runs in time poly(N, k).

We thank Oded Goldreich and Omer Paneth for useful discussions.

The first and third author were supported in part by NSF Grants CNS-1350619 and CNS-1414119, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship, the NEC Corporation, a Steven and Renee Finn Career Development Chair from MIT. This work was also sponsored in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226.

The second author was partially supported by NSF MACS - CNS-1413920, DARPA IBM - W911NF-15-C-0236 and SIMONS Investigator award Agreement Dated 6-5-12.

• [ABG+14] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC⁰ ◦ MOD2 . In *Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014*, pages 251–260, 2014. [2](#page-27-6)
• [AKNS00] Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular languages are testable with a constant number of queries. *SIAM J. Comput.*, 30(6):1842– 1862, 2000. [4](#page-3-3)
• [BCF+16] Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. On probabilistic checking in perfect zero knowledge. *IACR Cryptology ePrint Archive*, 2016:988, 2016. [1.2](#page-6-0)
• [BCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In *Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II*, pages 31–60, 2016. [8](#page-6-2)

• [BCY91] Gilles Brassard, Claude Crepeau, and Moti Yung. Constant-round perfect zero- ´ knowledge computationally convincing protocols. *Theor. Comput. Sci.*, 84(1):23–52, 1991. [30](#page-35-2)
• [BGG+88] Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio ˚ Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In *Advances in Cryptology - CRYPTO '88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings*, pages 37–56, 1988. [1.1.2,](#page-5-2) [6,](#page-33-0) [6](#page-34-3)
• [BGH+06] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. *SIAM J. Comput.*, 36(4):889–974, 2006. [1.1.2,](#page-5-2) [5.18,](#page-33-3) [6,](#page-33-0) [6.7,](#page-37-4) [32](#page-37-1)
• [BM88] Laszl ´ o Babai and Shlomo Moran. Arthur-Merlin games: A randomized proof system ´ and a hierarchy of complexity classes. *Journal of Computer and System Sciences*, pages 254–276, 1988. [5.5,](#page-28-2) [5.2.2](#page-33-4)
• [BY96] Mihir Bellare and Moti Yung. Certifying permutations: Noninteractive zeroknowledge based on any trapdoor permutation. *J. Cryptology*, 9(3):149–166, 1996. [1,](#page-2-0) [1.1.1,](#page-3-5) [5,](#page-3-4) [4.1.1,](#page-15-2) [12](#page-15-0)
• [CL17] Ran Canetti and Amit Lichtenberg, 2017. Unpublished manuscript. [1](#page-2-1)
• [CS10] Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. *Combinatorics, Probability & Computing*, 19(5-6):693–709, 2010. [1.1.1,](#page-4-3) [4.2,](#page-22-0) [4.2,](#page-22-1) [17,](#page-23-1) [4.2,](#page-24-1) [4.17](#page-25-3)
• [CS16] Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In *Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016*, pages 47–58, 2016. [2](#page-27-6)
• [DORS08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. *SIAM J. Comput.*, 38(1):97–139, 2008. [2.2,](#page-7-1) [2.1.2,](#page-8-1) [2.6](#page-8-2)
• [DR06] Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. *SIAM J. Comput.*, 36(4):975–1024, 2006. [1.1.2,](#page-5-2) [6,](#page-33-0) [6.7,](#page-37-4) [32](#page-37-1)
• [EKR04] Funda Ergun, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically ¨ checkable proofs. *Inf. Comput.*, 189(2):135–159, 2004. [1](#page-2-0)
• [FGL14] Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish. Partial tests, universal tests and decomposability. In *Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014*, pages 483–500, 2014. [1,](#page-2-0) [4](#page-3-3)
• [FLS99] Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs under general assumptions. *SIAM Journal on Computing*, 1999. Preliminary version in *FOCS'90*. [1](#page-2-0)

• [GG16] Oded Goldreich and Tom Gur. Universal locally testable codes. *Electronic Colloquium on Computational Complexity (ECCC)*, 23:42, 2016. [1](#page-2-0)
• [GGK15] Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. In *30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA*, pages 1–41, 2015. [5.18](#page-33-3)
• [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. *J. ACM*, 45(4):653–750, 1998. [1,](#page-2-0) [1.1.1,](#page-3-6) [4.2](#page-22-0)
• [GGR15] Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for contextfree languages and read-once branching programs - (extended abstract). In *Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I*, pages 666–677, 2015. [1,](#page-2-0) [4.2](#page-24-1)
• [GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. *SIAM Journal on Computing*, pages 186–208, 1989. Preliminary version in *STOC'85*. [1](#page-2-0)
• [GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In *Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC)*, pages 218–229, 1987. [B.4,](#page-45-0) [1](#page-45-1)
• [GMW91] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. *Journal of the ACM*, pages 691–729, 1991. Preliminary version in *FOCS'86*. [1,](#page-2-0) [6,](#page-34-3) [29](#page-35-1)
• [Gol01] Oded Goldreich. *Foundations of Cryptography: Basic Tools*. Cambridge University Press, 2001. [1,](#page-3-7) [11](#page-12-0)
• [Gol16] Oded Goldreich. *Introduction to Property Testing*. forthcoming ([http://www.](http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html) [wisdom.weizmann.ac.il/˜oded/pt-intro.html](http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html)), 2016. [1](#page-2-0)
• [GR99] Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. *Combinatorica*, 19(3):335–373, 1999. [4.3](#page-26-0)
• [GR02] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. *Algorithmica*, 32(2):302–343, 2002. [1.1.1,](#page-3-6) [1.1.1,](#page-4-3) [4.2,](#page-22-0) [4.3](#page-26-0)
• [GR11] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Oded Goldreich, editor, *Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman*, volume 6650 of *Lecture Notes in Computer Science*, pages 68–75. Springer, 2011. [1.1.1,](#page-4-3) [4.2](#page-22-0)
• [GR13] Oded Goldreich and Ron D. Rothblum. Enhancements of trapdoor permutations. *J. Cryptology*, 26(3):484–512, 2013. [1](#page-2-1)

• [GR15] Tom Gur and Ron D. Rothblum, 2015. Unpublished observation. [1.1.1,](#page-3-6) [4.1](#page-14-2)
• [GR16] Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. *Computational Complexity*, pages 1–109, 2016. [1,](#page-2-0) [4.1,](#page-14-2) [2,](#page-27-6) [5.2,](#page-29-5) [5.2.1,](#page-32-1) [5.18,](#page-33-3) [28,](#page-34-2) [31](#page-36-1)
• [GR17] Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In *Proceedings of the 2017 ACM Conference on Innovations in Theoretical Computer Science, Berkeley, CA, USA, January 9-11, 2016*, 2017. [1,](#page-2-0) [5.1,](#page-27-4) [5.2,](#page-27-5) [5.2.2](#page-33-4)
• [GS89] Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. *Advances in Computing Research: Randomness and Computation*, pages 73–90, 1989. [5.2.2](#page-33-4)
• [GS92] Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. *Inf. Process. Lett.*, 43(4):169–174, 1992. [B.3](#page-44-3)
• [GS06] Oded Goldreich and Madhu Sudan. Locally testable codes and pcps of almost-linear length. *J. ACM*, 53(4):558–655, 2006. [5.9](#page-30-0)
• [GSV98] Oded Goldreich, Amit Sahai, and Salil P. Vadhan. Honest-verifier statistical zeroknowledge equals general statistical zero-knowledge. In *Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998*, pages 399–408, 1998. [7](#page-4-2)
• [HILL99] Johan Hastad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudoran- ˚ dom generator from any one-way function. *SIAM J. Comput.*, 28(4):1364–1396, 1999. [6,](#page-35-0) [36](#page-45-2)
• [HNO+09] Iftach Haitner, Minh Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any oneway function. *SIAM Journal on Computing*, pages 1153–1218, 2009. Preliminary versions in *FOCS '06* and *STOC '07*. [30](#page-35-2)
• [IKOS09] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge proofs from secure multiparty computation. *SIAM J. Comput.*, 39(3):1121–1152, 2009. [6,](#page-34-3) [6.4,](#page-35-0) [6,](#page-35-0) [29,](#page-35-1) [6,](#page-36-2) [B.4,](#page-45-0) [35,](#page-45-3) [B.4](#page-46-0)
• [IW14] Yuval Ishai and Mor Weiss. Probabilistically checkable proofs of proximity with zeroknowledge. In *Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings*, pages 121–145, 2014. [1.2](#page-6-0)
• [Kil92] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In *Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC)*, pages 723–732, 1992. [1.1.2,](#page-5-2) [6,](#page-33-0) [6.7,](#page-37-4) [32](#page-37-1)
• [KR15] Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity [extended abstract]. In *Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II*, pages 422–442, 2015. [1,](#page-2-0) [27,](#page-34-1) [32](#page-37-1)

• [KS11] Satyen Kale and C. Seshadhri. An expansion tester for bounded degree graphs. *SIAM J. Comput.*, 40(3):709–720, 2011. 1.1.1, 4.2
• [KT00] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In *Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA*, pages 80–86, 2000. 5.10
• [Nao91] Moni Naor. Bit commitment using pseudorandomness. *J. Cryptology*, 4(2):151–158, 1991. 6, 36
• [NS10] Asaf Nachmias and Asaf Shapira. Testing the expansion of a graph. *Inf. Comput.*, 208(4):309–314, 2010. 1.1.1, 4.2, 4.16
• [NY89] Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In *Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC)*, pages 33–43, 1989. 30
• [RRR16] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In *Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016*, pages 49–62, 2016. 1, 1.1.2, 8, 6, 6.6
• [RS96] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. *SIAM J. Comput.*, 25(2):252–271, 1996. 1, B.3
• [RVW13] Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In *Symposium on Theory of Computing Conference*, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 793–802, 2013. 1, 1.1.1, 1.1.2, 4.3, 4.18, 5.5, 5.2, 5.2.2, 5.17, 6, 6.5, 32
• [Sud95] Madhu Sudan. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science. Springer, 1995. B.3
• [Vad99] Salil P. Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1999. 7, 2.2, 2.2.2, 2.2.2, 3, 3, 3.6, 3.7, 4.1.1, 5.1, A, A
• [Vad12] Salil P. Vadhan. Pseudorandomness. Now Publishers Inc., Hanover, MA, USA, 2012. 2.5

In this section we show how to reduce any property with honest-verifier zero-knowledge to an instance of Entropy Difference.

Then, there is a reduction from \Pi to ED. Specifically, the reduction is given \varepsilon and an input length N and outputs two oracle aided circuits C_0, C_1 \colon \{0,1\}^m \to \{0,1\}^n such that the following holds.

Note that the last item implies that for every x \in \{0,1\}^m and b \in \{0,1\} , computing C_b(x) requires only \operatorname{poly}(t_{\mathsf{S}}(\varepsilon,N,\operatorname{poly}(t'_{\mathsf{S}}(\varepsilon,N)))) many oracle calls. The proof of the above lemma follows from the proof that entropy difference is SZK-hard [Vad99]. We only give sufficient details to demonstrate how to apply that proof to our setting.

Proof sketch. Assume that (P,V) is the \varepsilon -IPP for \Pi and let S be the honest-verifier simulator for (P,V) whose simulation deviation is \mu(k)=\operatorname{negl}(k) . We assume for simplicity that t_S(N,k,\varepsilon) is a strict bound (and not only expected) on the running of S. The proof can be extended to handle expected bounds as well (in fact, the proof in [\operatorname{Vad99}] handles even weaker simulators). Assume without loss of generality that P and V send their messages in turns, P sends the odd messages and V the even ones. Let v(\varepsilon,N,k) be a bound on the number of messages sent by V to P for every f. In addition, let c(\varepsilon,N,k) and c(\varepsilon,N,k) be bounds on the total communication (measures in bits) between P and V and the number of random bits accessed by the verifier, respectively. We now modify the proof system so that V sends its random coins to P in an additional message just before the end of the protocol. The total communication and number of messages sent from V to P now increases to c'(\varepsilon,N,k)=c(\varepsilon,N,k)+r(\varepsilon,N,k) and c'(\varepsilon,N,k)=c(\varepsilon,N,k)+1 , respectively. S is modified to simulate the additional last message as well, without increasing its simulation deviation (this is possible since S was supposed to simulate V random coins anyway).

Fix \varepsilon and N and let k' \in \mathbb{N} such that \mu(k') \leq \min \left\{ 1/v'(\varepsilon,N,k') \cdot c'(\varepsilon,N,k'), 1/4 - 2^{-40} \right\} and the completeness and soundness errors of (\mathsf{P},\mathsf{V}) are at most 2^{-40} . Note that it suffices to take k' = \mathsf{poly}(t'_{\mathsf{S}}(\varepsilon,N)) (i.e., a fixed polynomial for all \varepsilon and N): It holds that v'(\varepsilon,N,k') \cdot c'(\varepsilon,N,k') \leq t_{\mathsf{S}}^2(\varepsilon,N,k') = t_{\mathsf{S}}'^2(\varepsilon,N) \cdot \mathsf{poly}(k') . Thus, we can take k' such that \mu'(k') \leq 1/t_{\mathsf{S}}'^2(\varepsilon,N) , for some negligible function \mu'(k') = \mu(k') \cdot \mathsf{poly}(k') . Since t_{\mathsf{S}}'(\varepsilon,N) is monotone non-decreasing in N, taking k' = \mathsf{poly}(t'_{\mathsf{S}}(\varepsilon,N)) guarantee the required condition for large enough (depending on \mu ) N (for simplicity, we ignore shorter inputs that can be solved via brute-force by the verifier).

Finally, let S_i^f be the random variable distributed according to the first i messages in the output of a random execution of S^f(\varepsilon, N, k') . In the following we remove \varepsilon , N and k' from the notation.

Constructing C_0 and C_1 . Define X = S_2^f \otimes S_4^f \otimes \cdots \otimes S_{2v'}^f . Similarly, define Y_1 to be Y_1 = S_1^f \otimes S_3^f \otimes \cdots \otimes S_{2v'-1}^f and define Y_2 to be the uniform distribution on r-7 bits. Furthermore, define Y_3 as follows: run S^f 8 \ln(c'v'+2) times independently; if the verifier rejects in the majority of the transcripts obtained, output c'v'+2 random bits; otherwise, output the empty string. Define Y = Y_1 \otimes Y_2 \otimes Y_3 . Finally, the circuits C_0 and C_1 take as input random coins to sample and output x \leftarrow X and y \leftarrow Y , respectively. Since we require that the input (resp., output) lengths of C_0 and C_1 will be equal, we pad the shorter input (resp., output) with redundant random coins (resp., zeros).

B.1 Proving Lemma 5.3

The proof of Lemma 5.3, sketch of which is given below, immediately follows from Lemmas 2.15 and A.1.

Proof sketch of Lemma 5.3. Both the verifier and the prover will run the reduction form Lemma A.1 to get two distributions encoded by oracle-aided circuits (C_0, C_1) . They will then run the protocol from Lemma 2.15 with respect to these distributions. Since the latter is a sample-access protocol the verifier can indeed run it using only oracle access to its input f.

The running time of the reduction implies that the input and outputs sizes of C_0 and C_1 are \mathsf{poly}(t_{\mathsf{S}}(\varepsilon,N,\mathsf{poly}(t_{\mathsf{S}}'(\varepsilon,N)))) . By Lemma 2.15 the running time of the verifier is thus \mathsf{poly}(t_{\mathsf{S}}(\varepsilon,N,\mathsf{poly}(t_{\mathsf{S}}'(\varepsilon,N))),k) , as required.

Zero-knowledge follows from similar arguments to the ones made above. \Box

B.2 Proving Claim 5.16

The proof of Claim 5.16 follows similar lines to that of Lemma 5.3.

Proof sketch of Claim 5.16. Both the verifier and the prover will run the reduction form Lemma A.1 with respect to the property Cl and proximity parameter \delta(C)/2 to get two distributions encoded by oracle-aided circuits (C_0,C_1) . If w\in \mathsf{CD}_{\mathsf{YES},\ell} then w is \delta(C)/2 -far from Cl and thus \mathsf{H}(C_1^w)\geq \mathsf{H}(C_0^w)+1 . However, if w\in \mathsf{CD}_{\mathsf{NO},\ell} then w\in \mathsf{Cl} and thus \mathsf{H}(C_0^w)\geq \mathsf{H}(C_1^w)+1 .

The verifier and the prover will then run the protocol from Lemma 2.15 with respect to the instance (C_1^w, C_0^w) (note that the order of the circuits has changed) and security parameter k chosen such that the completeness and soundness errors are both 1/3 for large enough \ell . Since the latter is a sample-access protocol the verifier can indeed run it using only oracle access to its input w.

Recall that we assumed that \mathsf{CI} \in \mathsf{HV}\text{-}\mathsf{ESZKPP}\big[\mathsf{poly}(\log(N), k, 1/\varepsilon)\big] . Hence, the simulator for \mathsf{CI} runs in time \mathsf{poly}(\log(\ell), k, 1/\varepsilon) , which by the choice of parameters is simply \mathsf{poly}(\log \ell) (recall the the proximity parameter \delta(C) and the security parameter k are constant). The running time of the reduction implies that the input (i.e., the number of bits need to sample from the distribution) and outputs sizes of C_0 and C_1 are \mathsf{poly}(\log \ell) as well, and by Lemma 2.15 the running time of the verifier is thus \mathsf{poly}(\log(\ell)) , as required.

B.3 Proof Sketch of Lemma 5.11

We start with a low degree extension code, over a finite field \mathbb{F} , which view messages x \in \mathbb{F}^{\ell} as functions x: H^m \to \mathbb{F} , where H \subseteq \mathbb{F} is a subset and m is a dimension, such that |H^m| = \ell . The code maps x to its low degree extension: namely, the unique individual degree |H|-1 polynomial that agrees with x on H^m . By the Shwartz-Zippel lemma this code has relative distance 1 - \frac{(|H|-1) \cdot m}{|\mathbb{F}|} .

bits and output x0^{n_y-n_x} .

Furthermore, this code is known to be locally testable [RS96] and decodable [GS92, Sud95] using O(|H| \cdot m) queries. We set |H| = (\log(\ell))^c , m = \frac{\log(\ell)}{c \cdot \log\log(\ell)} and |\mathbb{F}| = O(m \cdot |H|) for a sufficiently large constant c \geq 1 . Furthermore, we use a field \mathbb{F} which is an extension field of the binary field \mathbb{F}_2 .

We then concatenate the above low degree extension code with a good binary linear code. The overall resulting code has message length k(\ell) = |H|^m \cdot \log(F) = \tilde{O}(\ell) , blocklength n(\ell) = O(\mathbb{F}^m \cdot \mathbb{F}) = \tilde{O}(\ell^{1+1/c}) , constant relative distance and locally testable and decodable with O(|H| \cdot m) = \operatorname{polylog}(\ell) queries, which meets our desired parameters by setting c to be sufficiently large. Furthermore, since the low degree extension is linear over the large field \mathbb{F} , which is an extension field of \mathbb{F}_2 , it is also linear over \mathbb{F}_2 and therefore the resulting code is also \mathbb{F}_2 -linear.

B.4 Proof Sketch of Lemma 6.4

We use the [IKOS09] "MPC in the head" construction. More specifically, we will use their simplest variant, which is based on the [GMW87] 3-party protocol, in the OT-hybrid, with semi-honest security against 2 (semi-honest) players.³⁵ Below we refer to this as the IKOS protocol.

We first recall that the [GMW87] protocol, with 2-out-of-3 semi-honest can be implemented so that the parties, and the (semi-honest) simulator, run in time O(t') (where we count OT calls at unit cost), where t' is the circuit complexity of the function.

The IKOS protocol works in k sequential phases (in order to obtain 2^{-k} soundness), where each phase works as follows. The prover first runs the [GMW87] protocol with respect to to the function f(x, w_1, w_2, w_3) = R(x, w_1 \oplus w_2 \oplus w_3) , where w_1, w_2, w_3 are an additive secret sharing of the witness W. Observe that f is computable by a size t' = tildeO(t) circuit, where t is the complexity of R of the NP relation (an extra log factor comes from emulating Turing machines by circuits). Thus, the parties and the MPC simulator run in time \tilde{O}(t) .

After running the MPC protocol (in its "head"), the IKOS prover commits to the view of all the players.³⁶ Then, the verifier chooses two (distinct) players i, j \in \{1, 2, 3\} at random, and sends i and j to the prover. The prover decommits to these players views. The verifier rejects if the decommitments are invalid, the views are inconsistent, or if the result of the computation is not 1. Otherwise it accepts.

For the analysis of soundness and zero-knowledge of the IKOS protocol see [IKOS09]. Here we focus on the running times of the verifier and the simulator.

Observe that all that the verifier's running time in each phase is \tilde{O}(t) * \text{poly}(secp) as required.

We proceed to describe the IKOS simulator. Fix a malicious verifier \hat{V} . The simulator also runs for k phases. In each phase it repeats the following procedure at most poly(secp) times (and aborts if all fail):

• 1. Select at random a pair of (distinct) players i, j \in \{1, 2, 3\} , and runs the [GMW87] simulation on them (with respect to random strings w_i and w_j ).
• 2. The simulator generates commitments to the simulated views for these players as well as a fake simulation (e.g., all zero) for the third player. The simulator "sends" these commitments to the verifier \hat{V} .

• 3. Vb responds with a pair of distinct indices i 0 , j⁰ ∈ {1, 2, 3} (otherwise, since the IKOS prover would abort, the simulator can output its generated view so far followed by a ⊥ symbol).
• 4. If i 0 , j⁰ are not the same as i, j, then continue the loop.
• 5. Otherwise, the simulator can send decommitments to Vb and they continue to the next phase.

Overall the simulation of a single phase takes (O˜(t) + T)· poly(k) time, where T is the running time of Vb. See [\[IKOS09\]](#page-41-9) for additional details.