Towards Free Lunch Derandomization from Necessary Assumptions (And OWFs)

A more relaxed notion than the one in Definition 1 was considered in several prior works, which considered derandomization that has essentially no time overhead and that succeeds on average over the uniform distribution. Previous works deduced such derandomization from OWFs and additional hardness assumptions (see [12, 11]). We observe that such derandomization actually follows from OWFs alone, without additional assumptions, as a consequence of a lemma by Klivans, van Melkebeek, and Shaltiel [27] (see [1]). Thus, throughout the paper we focus on the stronger notion of free lunch derandomization from Definition 1, wherein errors are infeasible to find.

As in previous works, our results assume the existence of one-way functions. Since this is a ubiquitous and widely believed assumption, it strikes us as more urgent to improve the ad-hoc non-batch-computability assumption from [11, 14] than to remove the OWF assumption. We stress that for free lunch derandomization (i.e., as in Definition 1), the standard OWFs we assume (secure against polynomial-time adversaries) do not seem to yield anything better than subexponential-time derandomization.³³3Alternatively, standard OWFs can yield free lunch derandomization with $n^{ϵ}$ bits of advice (see Section 2.1.3). Moreover, our results actually only need a weaker assumption, which distills what is actually used in OWFs; for details and further discussion, see Section 1.2.2 and [1].

Our first result is free lunch derandomization of $ℳ𝒜$ into $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ relying on a surprisingly clean assumption: we just need a function computable in time $n^{1+O(ϵ)}$ that is hard for $ℳ𝒜𝒯ℐℳℰ[n^{1+ϵ}]$ over all polynomial-time samplable distributions. Indeed, this assumption does not involve non-batch-computability, low-depth, time-space tradeoffs, or any other non-standard property.

The hypothesis in Theorem 5 is reminiscent of the one in [17], but they deduce worst-case derandomization with quadratic overhead (of probabilistic algorithms), whereas Theorem 5 deduces free lunch derandomization with essentially no overhead (of $ℳ𝒜$ into $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols). Indeed, we do not use their technical tools. We prove Theorem 5 using a superfast targeted generator that is suitable for the non-deterministic setting, and which is a variant of a PCP-based generator recently introduced by van Melkebeek and Sdroievski [38]. For details, see Section 2.2. Similarly to Section 1.2.2, we can remove the $\tilde{O}(\log n)$ bits of advice by replacing the OWFs assumption with an assumption about the existence of a near-linear-time PRG for a general setting of parameters (see [1] for details).

The conclusion in Theorem 5 addresses a significantly more general setting compared to prior works concerning superfast derandomization into $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols. This is since prior works studied simulating subclasses of $prℬ𝒫𝒫$, rather than simulating all of $ℳ𝒜$. Specifically, in [14] they deduced free lunch derandomization of doubly efficient interactive proof systems into $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols (and relied on a non-batch-computability and on the classical Nisan-Wigderson generator). And in [10], they simulated uniform-$𝒩𝒞$ by $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols with a near-linear-time verifier (and relied on hardness for polylogarithmic space).⁶⁶6The conclusions in both works are incomparable to the conclusion in Theorem 5. This is since in [14], the honest prover does not receive a witness in a witness-relation for the problem; whereas in [10] the $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ verifier runs in near-linear time even if the uniform $𝒩𝒞$ circuit is of large polynomial size. We also note that the main result in [10] simulates a huge class (i.e., $𝒫𝒮𝒫𝒜𝒞ℰ$) by $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols; this is again incomparable to Theorem 5, since the latter result focuses on tight time bounds (i.e., free lunch derandomization) whereas the former does not.

Note that in Theorem 5, the hard function is computable in $ℱ𝒫$ yet is hard for smaller $ℳ𝒜$ time. This was stated only for simplicity (and such an assumption also suffices to derandomize $ℬ𝒫𝒯ℐℳℰ$ into $\mathrm{𝗁𝖾𝗎𝗋}\text{-}𝒟𝒯ℐℳℰ$). As one might expect, our more refined technical result relies on a non-deterministic upper bound and on a corresponding non-deterministic lower bound.

Loosely speaking, we deduce the conclusion of Theorem 5 from the existence of a function computable in $\mathrm{𝖼𝗌}\text{-}𝒩𝒯ℐℳℰ[n^{1+O(ϵ)}]$ that is hard for $\mathrm{𝖼𝗌}\text{-}ℳ𝒜𝒯ℐℳℰ[n^{1+ϵ}]$ over all polynomial-time samplable distributions. That is, the upper bound and the lower bound are both non-deterministic, and both require only computational soundness. For formal definitions and a discussion of the assumption, see Section 2.2 and [1].

The proof of this result relies on an interesting technical contribution. Specifically, we construct a superfast targeted generator that is suitable for the non-deterministic setting, and that has properties useful for working with protocols that have computational soundness (e.g., $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocols). The construction relies on a near-linear PCP that has an efficient proof of knowledge, and specifically on the construction of Ben-Sasson et al. [5]. See Section 2.2 for details.

We use a variant of the targeted generator of van Melkebeek and Sdroievski [39]. Fix $L_0\in ℳ𝒜𝒯ℐℳℰ[T]$, decided by a verifier $V_0$. The generator is given $x\in {\{0,1\}}^n$, and it guesses a witness $w$ for $V_0$. It also guesses $f(x,w)$, and a PCP witness $\pi$ for the language $L=\left\{((x,w),f(x,w))\right\}$, which is decidable in time ${|(x,w)|}^{1+O(ϵ)}=T{(|x|)}^{1+O(ϵ)}$. The generator then verifies that $\pi$ is indeed a convincing witness (by enumerating the $(1+ϵ)\cdot \log (T)$ coins of the PCP verifier), and outputs the $\mathrm{𝖭𝖶}$ PRG with $\pi$ as the hard truth-table.

Our deterministic verifier $V$ for $L_0$ gets $x$ and a witness $\overline{w}=(w,f(x,w),\pi )$, uses this generator with $(x,w,f(x,w),\pi )$, and outputs ${\wedge }_{s\in \mathrm{𝖭𝖶}(\pi )}{V}_0(x,w,s)$.¹⁴¹⁴14Throughout the paper we assume that $ℳ𝒜$ verifiers have perfect completeness. This verifier indeed runs in time $T^{1+O(ϵ)}$, assuming that we use a fast PCP and relying on the OWF assumption.¹⁵¹⁵15Specifically, we use a PCP in which PCP proofs for $𝒟𝒯ℐℳℰ[T]$ can be computed in time $T^{1+o(1)}$. Also, relying on the OWF assumption, we can assume wlog that the $ℳ𝒜$ verifier only uses $T^{ϵ}$ random coins. Indeed, when the $ℳ𝒜$ verifier uses $T^{ϵ}$ random coins, we can instantiate $\mathrm{𝖭𝖶}$ with small output length $T^{ϵ}\approx {|\pi |}^{ϵ}$, in which case it runs in time ${|\pi |}^{1+O(ϵ)}=T^{1+O(ϵ)}$ and produces a list of size $T^{O(ϵ)}$. Now, assume that an efficient dishonest prover $\tilde{P}$ can find, with noticeable probability, an input $x\notin L_0$ and a proof $\overline{w}=(w,f(x,w),\pi )$ such that $V(x,\overline{w})=1$. We show that on the fixed input $(x,w)$, an $ℳ𝒜$ reconstruction procedure succeeds in computing $f(x,w)$ in time $T^{1+ϵ}$. We stress that $f$ is only hard over polynomial-time samplable distributions, and thus we can only use this argument to deduce that no efficient adversary can find $x$ and $\overline{w}$ that mislead the verifier; that is, we derandomize $ℳ𝒜𝒯ℐℳℰ[T]$ into $\mathrm{𝖼𝗌}\text{-}𝒩𝒯ℐℳℰ[T^{1+O(ϵ)}]$.

How does the $ℳ𝒜$ reconstruction work for such a fixed $(x,w)$? By the above, there is $\pi$ such that $D_{x,w}(r)=V_0(x,w,r)$ is a distinguisher for $\mathrm{𝖭𝖶}(\pi )$. Given $(x,w)$ as input, we run the reconstruction algorithm $R_{\mathrm{𝖭𝖶}}$ of $\mathrm{𝖭𝖶}$. Recall that when $R_{\mathrm{𝖭𝖶}}$ gets suitable advice (which consists of random coins, and bits from the “correct” $\pi$), it uses $D_{x,w}$ to build a concise version of $\pi$. We non-deterministically guess advice for $R_{\mathrm{𝖭𝖶}}$, and this determines a concise version of a PCP witness ${\pi }^{\prime }$. We then guess $f(x,w)$ and run the PCP verifier on input $((x,w),f(x,w))$, giving it oracle access to ${\pi }^{\prime }$. The point is that: (1) The running time of this entire procedure is small, and can be made $T^{1+ϵ}$; (2) There is a guess such that this procedure accepts with probability $1$, due to the perfect completeness of the PCP verifier; (3) After guessing the advice for $R_{\mathrm{𝖭𝖶}}$, it commits to a single PCP witness ${\pi }^{\prime }$, and thus if we guessed $f(x,w)$ incorrectly the PCP verifier will reject, with high probability. For precise details see [1].

Next, we would like to relax the hardness assumption, and only require that $f$ will be computable non-deterministically. Since are constructing a $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ protocol for $L\in ℳ𝒜$, we need an efficient honest prover for $f$, and we thus use a hard function $f\in \mathrm{𝖼𝗌}\text{-}𝒩𝒯ℐℳℰ[n^{1+O(ϵ)}]$.¹⁶¹⁶16As in any argument system, the notion of $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ for $L\in ℳ𝒜$ is non-trivial only when the honest prover is efficient (at least when given a witness in an arbitrary $ℳ𝒜$-relation for $L$).

The $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ verifier for $L$ is similar to the one in the “bare-bones” version above. The only difference is that now it also gets a witness $w_f$ for $f$, uses a $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$-verifier $V_f$ to compute $V_f((x,w),w_f)$ (which hopefully outputs $f(x,w)$), and applies $\mathrm{𝖭𝖶}$ to a PCP proof ${\pi }_{x,w,w_f}$ for the $T^{1+O(ϵ)}$-time computable language $\left\{((x,w,w_f),V_f((x,w),w_f))\right\}$.

The main challenge is that with this new generator, the reconstruction procedure described above is not an $ℳ𝒜$ protocol anymore. To see why, consider an efficient adversary $\tilde{P}$ that finds $x$ and $(w,w_f,\pi )$ such that $D_{x,w}(r)$ is a distinguisher for $\mathrm{𝖭𝖶}({\pi }_{x,w,w_f})$. The reconstruction procedure then quickly and non-deterministically computes $V_f((x,w),w_f)$. The key problem is that $V_f$ may err in computing $f$ on some hard-to-find inputs. Specifically, on some inputs $(x,w)$, the reconstruction procedure has several possible outputs: It may be that $D_{x,w}$ is a distinguisher for $\mathrm{𝖭𝖶}({\pi }_{x,w,w_f})$ such that $V_f((x,w),w_f)=f(x,w)$, and also for $\mathrm{𝖭𝖶}({\pi }_{x,w,w_f^{\prime }})$ such that $V_f((x,w),w_f^{\prime })\ne f(x,w)$; in this case, on different non-deterministic guesses the reconstruction procedure may output either $V_f((x,w),w_f)$ or $V_f((x,w),w_f^{\prime })$.

The issue above seems inherent to the common techniques in hardness-vs-randomness (see [1] for an explanation). Thus, as explained in Section 1.3, we will rely on a hardness assumption for stronger $ℳ𝒜$-type reconstruction procedures, in which misleading input-proof pairs do exist but are infeasible to find (i.e., for $\mathrm{𝖼𝗌}\text{-}ℳ𝒜$ protocols; see below).

It is still unclear why the protocol above should have such computationally soundness – after all, maybe an adversary can indeed find a witness for the reconstruction (i.e., non-deterministic guesseses for the protocol, and in particular a PCP witness ${\pi }_{x,w,w_f^{\prime }}$) that cause the reconstruction to output an incorrect value (i.e., output $V_f((x,w),w_f^{\prime })\ne f(x,w)$). To ensure that no efficient adversary can do this, we construct the following superfast targeted generator, which has additional properties. The primary one is “witnessable soundness”: A witnessing algorithm can efficiently map convincing witnesses for the reconstruction procedure into convincing witnesses for $V_f$. Thus, since misleading input-witness pairs for $V_f$ are infeasible to find, misleading input-witness pairs for the reconstruction of the new generator are also infeasible to find.

The construction of Theorem 8 is based on PCPs with proofs of knowledge, as defined by Ben-Sasson et al. [5]. This notion asserts that convincing PCP witnesses can be efficiently “translated back” to satisfying assignments for the original predicate that the PCP proves. We will use the specific construction from [5], since we crucially need a PCP that is both very fast (i.e., has short witnesses that can be computed by a near-linear-time prover) and that has a polynomial-time proof of knowledge. The details appear in [1].

The derandomization result itself is stated in [1]. The specific assumption that it relies on is function $f\in \mathrm{𝖼𝗌}\text{-}𝒩𝒯ℐℳℰ[n^{1+O(ϵ)},\mathrm{poly}(n)]$ that is hard for $\mathrm{𝖼𝗌}\text{-}ℳ𝒜𝒯ℐℳℰ[n^{1+ϵ},n^2]$ protocols over all polynomial-time samplable distributions, where the second quantitative term in both expressions denotes the runtime of the honest prover in the protocol.¹⁸¹⁸18The reason for bounding the running times of the honest provers is that we are computing a function $f$ that does not necessary have an underlying witness-relation. Again, this is standard when considering argument systems, and $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$ systems were also defined this way in prior work (see, e.g., [20, Section 4.8] and [14, 10]). We note that in our assumption we will allow the honest prover in the $\mathrm{𝖼𝗌}\text{-}ℳ𝒜$ protocol to get a witness in an underlying witness-relation that can be efficiently generated; see [1] for precise details. That is, for every $\mathrm{𝖼𝗌}\text{-}ℳ𝒜𝒯ℐℳℰ[n^{1+ϵ},n^2]$ protocol with a verifier $V$ and an honest prover $P$ such that the protocol is computationally sound, it is infeasible to find inputs $z$ on which $P$ manages to convince $V$ of the correct value of $f(z)$. We make this notion quantitatively precise in [1]. The rationale behind the hardness assumption is the obvious one: If we disregard randomness, the verifier in the upper bound has more power than the verifier in the lower bound. As an additional sanity check, a random function with (say) $n^{ϵ}$ output bits also attains this hardness; and indeed, it is even plausible that there is a function in $ℱ𝒫$ (rather than only $\mathrm{𝖼𝗌}\text{-}𝒩𝒫$) with such hardness.

We show that any batch-solver fails on a small constant fraction $\delta >0$ of the $k$-tuples, and later explain how to lift this to hardness over $1-\delta$ of the $k$-tuples.

Let us first attempt a naive reduction and see where it fails. Assume towards a contradiction that a batch-solver $B$ succeeds on more than $1-\delta$ of the $k$-tuples. Given a (“large”) instance $X$ to the problem, we apply downward self-reduction to obtain $k^{\prime }$ smaller instances $x_1,\mathrm{\dots },x_{k^{\prime }}$; a correct solution to all $k^{\prime }$ smaller instances can be easily combined into a solution for $X$. Since the batch-solver only succeeds on average and we need to solve all $k^{\prime }$ instances correctly, a natural idea is to use error-correction: We randomly sample a low-degree curve $C$ passing through $x_1,\mathrm{\dots },x_{k^{\prime }}$, apply the batch-solver on a set of $k=O(d\cdot k^{\prime })$ points on this curve, and uniquely decode from $\approx \delta$ errors to obtain the unique degree-$(d\cdot k^{\prime })$ polynomial $p\circ C$ that agrees with $B\circ C$.

The only problem with this idea is that the points on the curve on which we apply the batch-solver $B$ are not uniformly distributed, and hence $B$ is not guaranteed to succeed with probability $1-\delta$. The main idea to resolve this is to add additional error-correction. Specifically, assume that $x_1,\mathrm{\dots },x_{k^{\prime }}$ are embedded in points $C(1),\mathrm{\dots },C(k^{\prime })$ on the curve, and that we decode using the points $C(k^{\prime }+1),\mathrm{\dots },C(k^{\prime }+k)$ on the curve. For each $i\in \{k^{\prime }+1,\mathrm{\dots },k^{\prime }+k\}$, we sample a random line $L_i$ passing through $C(i)$ (i.e., $L_i(0)=C(i)$). Now, for each fixed $j\in [O(d)]$, consider the $k$-tuple that passes through the $j^{th}$ point in each of the $k$ lines $L_1,\mathrm{\dots },L_k$

Observe that for each $j\in [d]$ the $k$-tuple ${\overline{x}}_j$ is uniformly random (over choice of $C$ and of $L_i$’s), so we can apply the batch-solver $B$ to it. In particular, by an averaging argument, with high probability over choices of $C$ and $L_i$’s, for most of the points $C(i)$ (where $i\in \{k^{\prime }+1,\mathrm{\dots },k^{\prime }+k\}$), for most of the points $j\in [d]$ we have $B{({\overline{x}}_j)}_i=p(L_i(j))$ (i.e., $B({\overline{x}}_j)$ is correct on its $i^{th}$ coordinate).¹⁹¹⁹19Our actual argument will use Chebyshev’s inequality (rather than an averaging argument), and to get pairwise independence we will use $L_i$’s that are quadratic curves. For simplicity, we hide this in the high-level overview. Thus, we now apply the Reed-Solomon unique decoder twice:

1. 1.

   First, for every $i\in \{k^{\prime }+1,\mathrm{\dots },k\}$ we run the batch-solver $B$ on ${\overline{x}}_1,\mathrm{\dots },{\overline{x}}_{O(d)}$ and look at its $i^{th}$ coordinate. This yields a sequence of $O(d)$ values, and we uniquely decode the results, hoping to obtain the degree-$d$ polynomial $p\circ L_i$ and evaluate it on $0$ to get $p(C(i))$.

2. 2.

   Secondly, analogously to the naive attempt, we now uniquely decode the sequence of $k$ values obtained in the first step, hoping to obtain the degree-$(d\cdot k^{\prime })$ polynomial $p\circ C$.

If indeed for most $C(i)$’s it holds that for most $j\in [d]$ we have $B{({\overline{x}}_j)}_i=p(L_i(j))$, then for most $C(i)$’s we correctly obtain the value $p(C(i))$ in the first step, in which case the unique decoder outputs $p\circ C$ in the second step. Then we can compute $p\circ C(1),\mathrm{\dots },p\circ C(k^{\prime })$ and combine the results $p(x_1),\mathrm{\dots },p(x_{k^{\prime }})$ to compute the hard function at input $X$.

There are two remaining gaps in the proof above. First, the proof shows that every batch-solver fails on a small fraction $\delta >0$ of the inputs, whereas we are interested in showing that every batch-solver fails on a very large fraction $1-\delta$ of the inputs.

We bridge this gap by applying direct-product again, which increases the average-case hardness from $\delta$ to $1-\delta$, carefully adapting well-known techniques from a sequence of works by Impagliazzo et al. [23, 24]. Their techniques require a way to verify that a batch-computation is correct,²⁰²⁰20In other words, they only yield a list-decoder rather than a decoder, and we need to weed the list to find which candidate is correct. and the key observation is that in our setting, we can efficiently test whether a batch-solver correctly computes $1-ϵ$ of the bits of $f(X)$, by sampling $O(1/ϵ)$ output bits and computing $f$ at each of these bits. (Observe that this does not significantly increase the running time of the batch-solver.)

The second gap is that the proof shows hardness of batch-computing a polynomial over a large field, rather than a Boolean function; we bridge this gap via the standard approach of applying the Hadamard code to the polynomial. For precise details, see [1].