On the Power of Computationally Sound Interactive Proofs of Proximity

We exhibit the power of cs-IPPs, both for achieving low query complexity and for achieving pre-coordination. We show that, assuming the existence of collision-resistant hashing functions (CRHFs), any public-coin cs-IPP (and hence any public-coin unconditionally sound IPP with an efficient honest prover) can be efficiently emulated by a cs-IPP that makes only $O(1/ϵ)$ queries, and is in the pre-coordinated model. The communication complexity of the resulting system is roughly $c+q$, where $c$ and $q$ are the communication and query complexity of the original system, respectively. Furthermore, the emulation adds only $2$ rounds of interaction.

We consider two types of collision-resistance: weak collision-resistance, which requires that finding collisions is hard for polynomial-size circuits, and strong collision-resistance, which requires that finding collisions is hard for sub-exponential size circuits (see Definition 2.3 in the full version).

The emulation also roughly preserves the running time of the verifier: If the running time of the original verifier is $t_{𝖵}$, then the resulting verifier runs in time $O\left(t_{𝖵}(n)+\left(q(n)+{ϵ}^{-1}\right)\cdot \tau (n)\right)$ (where $\tau (n)$ is as in the statement of Theorem 1). In addition, the running time of the resulting honest prover is $O\left(t_{𝖯}(n)+t_{𝖵}(n)+n\cdot \tau (n)\right)$, where $t_{𝖯}$ is the running time of the original honest prover.

The term $\rho (n)$ appearing in Theorem 1 actually represents only the additional coins that the verifier uses to generate its queries, beyond the coins sent during the interaction (which contribute at most $c$ coins). By standard techniques, this $\rho$ term can always be reduced to $O(\log n)$, at the cost of introducing non-uniformity; see Remark 3.9 in the full version. Alternatively, we show that the $\rho$ term can be avoided altogether, at the cost of $q(n)$ additional rounds of communication in the general case, and at no extra cost when the original verifier uses non-adaptive queries. However, the resulting system will not be public-coin (see Theorem 3.5 in the full version).

While Theorem 1 is stated for public-coin cs-IPPs, we show a similar transformation for general cs-IPPs when using a computational PIR (private information retrieval) scheme (see Theorem 3.10 in the full version).

Having shown the power of computational soundness for the pre-coordinated model, we turn to consider the isolated model. In contrast to the pre-coordinated model, we show that cs-IPPs in the isolated model can be efficiently emulated by testers, as in the unconditional soundness case. In particular, this demonstrates the necessity of pre-coordination for the result of Theorem 1.⁸⁸8In [19] we showed this necessity through a direct lower bound on cs-IPPs in the isolated model for the property PERM (the set of all permutations over $[n]$). More precisely, we showed that any isolated cs-IPP for $\mathrm{𝙿𝙴𝚁𝙼}$ with query complexity $q>0$ and communication complexity $c>0$ must satisfy $q^5\cdot c=\mathrm{\Omega }(n/\log (n))$. The emulation of isolated cs-IPPs by testers implies a similar lower bound for PERM that follows from a simpler argument. Specifically, since testing $\mathrm{𝙿𝙴𝚁𝙼}$ requires $\mathrm{\Omega }(\sqrt{n})$ queries (see [18, Apdx. A] following [11, Lem. 4.3]), it follows from Theorem 2 that any isolated cs-IPP for $\mathrm{𝙿𝙴𝚁𝙼}$ with query complexity $q>0$ and communication complexity $c>0$ must satisfy $q\cdot c=\mathrm{\Omega }(\sqrt{n})$.

While Theorem 2 rules out an emulation in the isolated model with the efficiency of Theorem 1, in Section 3.3 of the full version we show that our pre-coordinated model emulation can be transformed to the isolated model at the cost of increasing the product of the query and communication complexities by roughly $n/ϵ$. More precisely, we can get a general tradeoff between the resulting query and communication complexities, such that for any $q^{\prime }>O(1/ϵ)$, we can obtain query complexity $q^{\prime }$ while increasing the communication complexity (over that obtained in Theorem 1) by an additive $O\left(\frac{n}{ϵ\cdot q^{\prime }}\right)\cdot \tau (n)$ term, where $\tau (n)$ is as in the statement of Theorem 1. Note that this tradeoff is nearly optimal given the negative result of Theorem 2, since there exist properties that have very efficient cs-IPPs but require nearly linear query complexity for testing (see details in Section 3.3 of the full version).

Our emulation in the pre-coordinated model is based on the well-known technique of Kilian [14]. Recall that Kilian showed how to transform PCPs into computationally sound interactive proofs that have very low communication complexity, assuming the existence of collision-resistant hashing functions. Kilian’s protocol uses a special commitment scheme, called a tree commitment scheme (also known as Merkle-hashing), that allows one to commit to an $n$-bit string such that individual bits in the string can be revealed (and verified as correct) with very low communication cost (e.g., poly-logarithmic in $n$). In Kilian’s protocol, the prover commits to the PCP-proof, and the verifier asks the prover to reveal the locations that the original PCP-verifier would query in the proof oracle. The commitment scheme ensures that a computationally bounded prover must respond consistently with a fixed proof string (i.e., it cannot cheat by answering differently based on the set of queries it has received).

Our emulation of public-coin cs-IPPs uses the tree commitment scheme to have the prover commit to the input. Recall that we are given a public-coin cs-IPP for some property $\mathrm{\Pi }$, and aim to efficiently emulate it in the pre-coordinated model while making only $O(1/ϵ)$ queries. The emulation will begin by executing the commitment phase of the tree commitment scheme, where the prover commits to a string that allegedly equals to the input. Next, we emulate the original interaction with the prover. Note that this can be done without access to the input oracle since the original interaction is public-coin. The emulation is done with respect to proximity parameter $ϵ/2$ (where $ϵ$ is our target proximity parameter). At the end of the emulated interaction, instead of making the queries that the original verifier would have made to the input oracle, we ask that the prover provide the answer to these queries by revealing the corresponding locations in the alleged input via the tree-commitment scheme. We check that the original verifier would have accepted given the answers the prover provided, along with the interaction transcript generated in the emulated interaction. In addition, we query the actual input oracle on $O(1/ϵ)$ randomly chosen locations, ask the prover to reveal the same locations in the alleged (committed) input, and check for consistency. Note that the interacting and querying modules of the resulting system need only share the random consistency-check locations, and otherwise operate independently from one another.

To see why soundness holds, consider the foregoing emulation given an arbitrary input $x\in {\{0,1\}}^n$ that is $ϵ$-far from the property $\mathrm{\Pi }$, when interacting with an arbitrary computationally bounded prover. At a high level, once the tree commitment is established, the prover’s answers to the queries must be consistent with some fixed string $x^{\prime }$. If $x^{\prime }$ is $(ϵ/2)$-close to $x$, then $x^{\prime }$ is $(ϵ/2)$-far from $\mathrm{\Pi }$, and so the prover will fail to fool the original verifier with high probability. Otherwise, $x^{\prime }$ is $(ϵ/2)$-far from $x$, and then by checking for consistency between $x$ and $x^{\prime }$ on $O(1/ϵ)$ random locations, we will detect a mismatch with high probability.

Note that it is important to first emulate the original interaction and only after ask the prover to provide the answer to the queries (which is possible due to the public-coin hypothesis). This is because, by asking the prover to provide the answers to the queries, we reveal to the prover their locations, whereas the soundness of the original verifier may rely on keeping these locations secret.

To extend the emulation to general cs-IPPs that are not necessarily public-coin, we interleave the emulation of the original interaction with the query requests, since the verifier’s messages may depend on responses to its prior queries. To withhold the actual queries from the prover, we use a computational PIR scheme for providing answers to these queries.

While the technique of using the tree commitment scheme to force a computationally bounded prover to respond consistently with a fixed string is well-known, to the best of our knowledge, there is a lack of a source that presents this technique formally and in a general manner (with the exception of the concurrent [12]; see Section 4).⁹⁹9One notable source that provides a formal treatment of this technique is [2]. The setting treated in [2] is a more complex one, but it is less generic. In this work, we provide a general lemma (see Lemma 3.3 in the full version) that captures this property of the tree commitment scheme. The lemma asserts that in any interaction that uses the tree commitment scheme, with overwhelmingly high probability, at the end of the commitment phase there exists a fixed string, such that any location that is subsequently opened will either be opened consistently with this string or will be detected as faulty.

Recall that in the isolated model, the verifier’s querying and interacting activities are totally independent from one another, each operating with a separate source of randomness. Specifically, the verifier is decomposed into a querying, interacting, and deciding modules $Q$, $I$, and $D$, respectively, such that its decision when interacting with a prover strategy $P$ on input $x$ is expressed as: $D(Q^x(R_Q),⟨P,I(R_I)⟩)$, where $R_Q$ and $R_I$ are independent random variables representing the randomness of the querying and the interacting modules, respectively.

In [10] it was shown that unconditionally sound IPPs in the isolated model can be efficiently emulated by property testers: If a property $\mathrm{\Pi }$ has an IPP in the isolated model that makes $q$ queries and uses $c>0$ bits of communication, then $\mathrm{\Pi }$ has a tester with query complexity $O(c\cdot q)$. We show the same is true for computationally sound IPPs.

Roughly speaking, the reason that the emulation of [10] does not carry over to the context of cs-IPPs, is that it emulates the verifier with the optimal prover strategy. In the context of cs-IPPs, the performance of the optimal strategy (on NO-instances) is not relevant, since the optimal strategy may not be efficiently implementable.

Instead of the optimal prover, we will consider the honest prover, which is guaranteed to be efficient. Note that we cannot directly emulate the interaction with the honest prover on the actual input, because doing so requires full access to the input. Thus, instead, we emulate $2^n$ interactions, each with a different possible $n$-bit input (actually, it will suffice to use only the YES-instances). Observe that if the actual input is a YES-instance, then there exists an emulation that will lead to accepting with probability at least $2/3$. On the other hand, if the actual input is a NO-instance, then each of these emulations leads to rejection with probability at least $2/3$.

However, we do not want to take a union bound over $2^n$ events. Instead, we observe that each of these emulations can be expressed as a (different) convex combination of the probabilities that the verifier accepts given each fixed interaction transcript $\tau \in {\{0,1\}}^c$. For simplicity, assume that the interaction transcript fully determines the randomness of the interacting module. Then, for any prover strategy $P$, we have:

Thus, we can obtain an (additive constant) approximation of the acceptance probability of all $2^n$ emulations by obtaining an approximation of the $2^c$ fixed-transcripts probabilities:

As observed in [10],¹⁰¹⁰10The fixed-transcript probabilities $p_{\tau }^x$ are used in [10] to compute the acceptance probability of the optimal prover via the max-average game tree of interactive proofs (where the probabilities $p_{\tau }^x$ are viewed as the leaves of the game tree). an approximation of $p_{\tau }^x$ can be obtained by repeated invocations of the querying module $Q^x$, where the same invocations can be used towards approximating all $2^c$ values $p_{\tau }^x$ since the invocations are oblivious of the value of $\tau$. Hence, by invoking the querying module $O(c)$ times, we can obtain for each $p_{\tau }^x$ a constant additive approximation with error probability $O(2^{-c})$, and by a union bound we get an approximation of all $2^c$ values, with high constant probability. Using these values, we can obtain approximations of the success probability of the honest prover strategy on all $2^n$ inputs, by computing, for each such strategy, the corresponding coefficients (i.e., $\mathrm{Pr}\left[⟨P,I(R_I)⟩=\tau \right]$) in Eq. (3.2). Indeed, this will be computationally expensive, but the computational complexity is irrelevant to us.