Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

The range avoidance problem (Avoid) is a total search problem introduced by [43, 45, 72]. Given a Boolean circuit $G:{\{0,1\}}^n\to {\{0,1\}}^m$ with $m>n$ (usually we also require $m\le \mathrm{poly}(n)$), the goal is to find a string $y\in {\{0,1\}}^m$ such that $y\notin \mathrm{Range}(G)$. This problem has attracted considerable interest due to its connection to central problems in complexity theory such as explicit constructions [45, 72, 16, 30, 26] and circuit lower bounds [45, 13, 61, 47]. We refer the reader to [46] for a comprehensive survey on the range avoidance problem.

The range avoidance problem admits a trivial randomized algorithm: simply output a uniformly random $m$-bit string, which will lie outside the range of $G$ with high probability. On the other hand, deterministic algorithms for Avoid would imply breakthroughs in explicit constructions and circuit lower bounds [45, 72, 30, 26]. Since such breakthroughs are widely believed to be true (albeit difficult to prove), the aforementioned results only suggest that deterministic algorithms for Avoid would be difficult to obtain unconditionally, rather than that such algorithms are unlikely to exist. This raises a natural question: Is there a deterministic algorithm for Avoid?

Perhaps surprisingly, recent results suggested that the answer is likely no under plausible cryptographic assumptions. Ilango, Li, and Williams [33] showed that Avoid is hard for deterministic algorithms assuming the existence of subexponentially secure indistinguishability obfuscation ($i𝒪$) and that $\mathrm{𝐍𝐏}\ne \mathrm{𝐜𝐨𝐍𝐏}$. Chen and Li [17] extended this result and showed that Avoid is hard even for nondeterministic algorithms, under certain assumptions regarding the nondeterministic hardness of LWE (Learning with Errors) or LPN (Learning Parity with Noise). In addition to providing compelling evidence for the hardness of Avoid, these results establish a strong separation between deterministic and randomized algorithms (recall that there exists a trivial randomized algorithm for Avoid).

The hardness results in [33, 17] open up several exciting research directions:

1. 1.

   Can the hardness of Avoid be based on weaker (or alternative) assumptions?

   The assumptions used in prior work, i.e., $i𝒪$ [33] and public-key encryption [17], belong to Cryptomania in the terminology of Impagliazzo’s worlds [34]. Can we base the hardness of range avoidance on assumptions of a “Minicrypt” flavor, such as one-way functions or pseudorandom generators? Additionally, both [33] and [17] rely on subexponential indistinguishability assumptions¹¹1More precisely, the assumptions in [33, 17] assert subexponential indistinguishability against polynomial-time adversaries. This level of security is referred to as “JLS-security” in [33], where “JLS” comes from the strengths of the “well-founded” assumptions used to construct $i𝒪$ in [37].. Are such subexponential assumptions necessary?

2. 2.

   Can we obtain hardness of Avoid for instances computed by restricted circuits?

   Previously, under assumptions related to LWE, Chen and Li [17] showed that Avoid remains hard even when each output bit of $G$ is computed by a so-called “$\mathrm{𝖣𝖮𝖱}\circ \mathrm{𝖬𝖠𝖩}\circ {\mathit{and}}_{O(\log n)}$ circuit”. No such results were known for other restricted circuit classes. The related remote point problem has been shown to be hard under LPN-style assumptions for $\mathrm{𝖷𝖮𝖱}\circ {\mathit{and}}_{O(\log n)}$ circuits (i.e., $O(\log n)$-degree polynomials over ${𝔽}_2$) [17].

This paper makes progress on both fronts. We show that Avoid is hard for nondeterministic algorithms under the existence of demi-bits generators with sufficient stretch²²2The stretchability of generic demi-bits generators is only partially understood. Recent work of Tzameret and Zhang [77] shows that demi-bits generator with $1$-bit stretch $G:{\{0,1\}}^n\to {\{0,1\}}^{n+1}$ implies those with a sublinear bits of stretch $G^{\prime }:{\{0,1\}}^n\to {\{0,1\}}^{n+n^c}$ for any constant . This is the first proof that generic demi-bits generators are stretchable at all, but it still falls short of the linear or polynomial stretch assumed in our hypothesis. [73]. A formal definition of demi-bits generators is deferred to Subsection 2.1; in Appendix B of the full version of this paper, we also provide some candidate constructions supporting their existence. For the purpose of this introduction, it suffices to keep in mind that demi-bits generators are a version of cryptographic pseudorandom generators secure against nondeterministic adversaries.

We highlight three key features of our results here:

1. 1.

   Minicrypt-style assumptions against nondeterministic adversaries.

   Roughly speaking, demi-bits generators are (cryptographic) pseudorandom generators secure against nondeterministic adversaries³³3In fact, Rudich [73] introduced two ways to define pseudorandomness against nondeterministic adversaries: super-bits and demi-bits. Demi-bits are weaker than super-bits.. They are arguably a natural “Minicrypt” analog of pseudorandom generators in the context of cryptography against nondeterministic adversaries. Moreover, our results only rely on the super-polynomial hardness of these demi-bits generators, thereby completely getting rid of the subexponential (or “JLS”-style) assumptions used in prior work.

2. 2.

   Hardness for restricted circuit classes.

   Under the assumption that certain concrete demi-bits generators are secure (e.g., those based on LPN or Goldreich’s PRG), we show that the range avoidance problem remains hard for nondeterministic algorithms even when the underlying circuits belong to $\mathrm{𝖷𝖮𝖱}\circ {\mathit{and}}_{O(1)}$, i.e., constant-degree polynomials over ${𝔽}_2$.

3. 3.

   Simplicity of the proof for hardness of range avoidance.

   In contrast to [33, 17], which rely on sophisticated and delicate adaptations of high-end cryptographic assumptions, our proof of the hardness of range avoidance (Theorem 27) is based solely on the most elementary pseudorandom constructions together with the existence of demi-bits. This approach distills the arguments of [33, 17] to their essence, yielding a proof that is both conceptually cleaner and technically simpler. In fact, the proof of Theorem 27 fits in just half a page. Moreover, by isolating the core ingredients, this simplified framework opens the door to potential extensions and generalizations that may be harder to see in the more cryptographically heavy approaches.

Let $G:{\{0,1\}}^n\to {\{0,1\}}^m$ be a Boolean circuit where $m>n$, and $𝒫$ be a propositional proof system. We say that $G$ is a (secure) proof complexity generator [3, 49] against $𝒫$ if, for every string $y\in {\{0,1\}}^m$, the (properly encoded) statement “$y\notin \mathrm{Range}(G)$” does not admit short proofs in $𝒫$.⁴⁴4If $y$ is in fact in the range of $G$, then “$y\notin \mathrm{Range}(G)$” is a false statement and hence has no proof in any sound proof system. Therefore, this requirement is equivalent to that, for every $y\notin \mathrm{Range}(G)$, the tautology “$y\notin \mathrm{Range}(G)$” is hard to prove in $𝒫$. A comprehensive survey about proof complexity generators can be found in [57].

The study of proof complexity generators is motivated by at least the following themes:

1. 1.

   Pseudorandomness in proof complexity [3].

   A standard pseudorandom generator (PRG) $G:{\{0,1\}}^n\to {\{0,1\}}^m$ [78] fools a (polynomial-time) algorithm $𝒟$ if $𝒟$ cannot distinguish the outputs of $G$ from truly random $m$-bit strings; that is, $𝒟({𝒰}_m)\approx 𝒟(G({𝒰}_n))$, where ${𝒰}_{\mathrm{\ell }}$ denotes the uniform distribution over $\mathrm{\ell }$-bit strings. Analogously, one can say that $G$ fools a propositional proof system $𝒫$ if $𝒫$ cannot distinguish between the outputs of $G$ and truly random $m$-bit strings, and a natural way of formalizing this is to say that $𝒫$ cannot efficiently prove any string outside the range of $G$.

   Following the idea of pseudorandomness in proof complexity, subsequent works [53, 65, 54, 71, 42] studied the hardness of the Nisan–Wigderson generator ([63]) as a proof complexity generator in various settings. An influential conjecture of Razborov asserts that the Nisan–Wigderson generator based on any “sufficiently hard” function in $\mathrm{𝐍𝐏}\cap \mathrm{𝐜𝐨𝐍𝐏}$ is a proof complexity generator against Extended Frege [71, Conjecture 2]; that is, computational hardness can be transformed into proof complexity pseudorandomness.

2. 2.

   Candidate hard tautologies for strong proof systems.

   There are two difficulties in proving lower bounds for strong proof systems such as Frege and Extended Frege: the lack of techniques and the lack of candidate hard tautologies. The latter problem was highlighted by Bonet, Buss, and Pitassi [9], who demonstrated that many combinatorial tautologies can be proved efficiently in Frege, hence disqualifying them as hard candidates. This issue has been further discussed in [50, 53, 74, 42].

   Tautologies from proof complexity generators are among the few natural candidates that appear hard for strong proof systems. It seems plausible that for some mapping $G:{\{0,1\}}^n\to {\{0,1\}}^{n+1}$ and some (or even every) $y\in {\{0,1\}}^{n+1}\setminus \mathrm{Range}(G)$, the natural CNF encoding of the tautology “$y\notin \mathrm{Range}(G)$” requires super-polynomially long Extended Frege proofs.

3. 3.

   Unprovability of circuit lower bounds.

   Given our very limited progress in circuit complexity, it is tempting to conjecture that circuit lower bounds are hard to prove in formal proof systems. For a Boolean function $f:{\{0,1\}}^n\to \{0,1\}$ and a size parameter $s$, one can write down a propositional formula $\mathrm{𝗅𝖻}(f,s)$ (of size $2^{O(n)}$) asserting that no circuit of size at most $s$ computes $f$. The proof complexity of such formulas have been studied extensively [69, 70, 53, 71, 66, 67, 74, 68], due to its implications for the metamathematics of complexity theory.

   Consider the truth table generator $\mathrm{𝖳𝖳}:{\{0,1\}}^{\mathrm{poly}(s)}\to {\{0,1\}}^{2^n}$, which maps a size-$s$ circuit $C$ to its $2^n$-bit truth table. By definition, $\mathrm{𝖳𝖳}$ is a proof complexity generator against a proof system $𝒫$ if and only if $𝒫$ cannot efficiently prove any circuit lower bound $\mathrm{𝗅𝖻}(f,s)$. Krajíček [53] introduced the notion of pseudo-surjectivity and showed that $\mathrm{𝖳𝖳}$ is the hardest pseudo-surjective generator: The existence of any generator pseudo-surjective against $𝒫$ implies that $\mathrm{𝖳𝖳}$ is pseudo-surjective against $𝒫$ (and thus that $𝒫$ cannot prove circuit lower bounds). Razborov [71] further showed unprovability of circuit lower bounds in the proof system $\mathrm{Res}(\epsilon \log \log N)$ by exhibiting a proof complexity generator that is iterable for this system.⁵⁵5Iterability is a weaker notion than pseudo-surjectivity. Krajíček [53] also showed that $\mathrm{𝖳𝖳}$ is the “hardest” iterable generator.

Krajíček [53, 56, 51] conjectured that there exists a proof complexity generator that is secure against every propositional proof system. One could also consider a slightly weaker conjecture that for every propositional proof system $𝒫$, there is a proof complexity generator $C_{𝒫}$ (possibly depending on $𝒫$) that is hard against $𝒫$. At first glance, these conjectures may appear unrelated to standard hardness assumptions in complexity theory or cryptography, as proof complexity generators require “$y\notin \mathrm{Range}(G)$” to be hard to prove for every $y$ (i.e., the best-case $y$), while complexity-theoretic or cryptographic hardness assumptions tend to be either worst-case or average-case. We elaborate on the notion of “best-case” proof complexity in Subsection 1.4.

In this paper, we give strong evidence for the weaker conjecture by showing that it follows from the existence of demi-bits generators (with sufficiently large stretch) [73]. The latter is a natural and fundamental conjecture in the study of cryptography against nondeterministic adversaries. Furthermore, we show that our generators are even pseudo-surjective under certain regimes.⁶⁶6The parameters of our pseudo-surjectivity results fall just short of those required to apply Krajíček’s result [53], hence they do not imply the hardness of the truth table generator. This limitation is inherent; we discuss this issue in more details after presenting Theorem 7.

Theoretical computer science has traditionally focused on the worst-case complexity of problems: An algorithm $𝒜$ solves a problem if $𝒜(x)$ succeeds on every input $x$. Motivated by practical heuristics (where worst-case analysis tends to be overly pessimistic) and cryptography (where worst-case hardness is not sufficient for security), average-case complexity has emerged as an important research direction [34, 7]. In this setting, fixing a distribution $𝒟$ over inputs, an algorithm $𝒜$ solves a problem if $𝒜(x)$ succeeds with good probability over $x\sim 𝒟$. Recently, average-case complexity has received attention in proof complexity as well: For example, [64, 24, 19] proved proof complexity lower bounds for Clique and Coloring for random graphs.

An important topic in average-case complexity is worst-case to average-case reductions: reductions showing that if a problem $L$ is hard in the worst-case then a related problem $L^{\prime }$ is hard on average. Worst-case to average-case reductions are known for the Permanent [12], Discrete Logarithm [6], Quadratic Residuosity [28], certain lattice problems [2], and more recently for problems in meta-complexity [31]. On the other hand, “black-box” worst-case to average-case reductions are unlikely to exist for $\mathrm{𝐍𝐏}$-complete problems [25, 8].

In contrast, the notion of best-case complexity has received far less attention. Perhaps one reason is that this notion is often trivial in standard computational complexity: for every language $L$, either the all-zero function or the all-one function can decide $L$ on the “best” input.⁸⁸8One notable exception appears in recent derandomization results [15] based on almost-all-input hardness assumptions. In particular, it was shown that $\mathrm{pr}𝐏=\mathrm{pr}\mathrm{𝐁𝐏𝐏}$ follows from the existence of depth-efficient multi-output functions with high best-case complexity against randomized algorithms. However, in proof complexity, best-case hardness is a meaningful and natural notion, as illustrated by proof complexity generators, which are stretching functions $G$ such that the statement “$y\notin \mathrm{Range}(G)$” is hard to prove even for the best choice of $y$.

In this context, our results can be interpreted as an average-case to best-case reduction in proof complexity. Indeed, Theorem 4 transforms demi-bits generators, where statements of the form “$y\notin \mathrm{Range}(G)$” is hard to prove for an average-case $y$, to proof complexity generators, where such statements are hard for a best-case $y$.

We find the existence of such average-case to best-case reductions quite surprising. Our arguments crucially exploit the power of nondeterministic computation, and the phenomenon of average-case to best-case reductions seems unique to the setting of proof complexity and hardness against nondeterministic algorithms. We believe that further exploring the scope and limitations of average-case to best-case reductions is a promising direction for future research.

We remark that there are also worst-case to best-case reductions in proof complexity. Krajíček [52] constructed a proof complexity generator whose hardness can be based on the hardness of the pigeonhole principle, thereby reducing the best-case hardness of an entire family of tautologies to that of a single tautology. Inspired by this example, Garlik, Gryaznov, Ren, and Tzameret [27] recently showed a worst-case to best-case reduction for the rank principles. Let “$\mathrm{rank}(A)>r$” denote the collection of polynomial equations expressing that the rank of an $n\times n$ matrix $A$ is greater than $r$. If a proof system (closed under certain algebraic reductions) cannot prove “$\mathrm{rank}(I_n)>r$” where $I_n$ is the $n\times n$ identity matrix, then it also cannot prove “$\mathrm{rank}(A)>r$” for every $n\times n$ matrix $A$.

In an independent and concurrent work, Ilango [32] presented a different proof of Theorem 1 and Theorem 4. Ilango’s proof implies the average-case hardness of Avoid under a natural distribution (namely, it is hard for errorless nondeterministic heuristic algorithms to output a truth table with high $O$-oracle circuit complexity given the truth table of a random oracle $O$). Based on this result, Ilango constructed a (non-uniform) non-interactive proof system that “looks” zero knowledge to every proof system. However, Ilango did not show the pseudo-surjectivity of his generators.

This paper requires demi-bits generators with large stretch and computable with small circuit complexity. In particular, we need the following assumptions:

Our main hardness results for Avoid will be based on Assumption 9; we also need Assumption 10 to obtain hardness results for constant-degree Avoid. In Appendix B of the full version, we justify these assumptions and provide some candidate constructions.

An Arthur–Merlin protocol [5] for a language $L$ is a constant-round public-coin interactive protocol between a computationally unbounded $\mathrm{𝖯𝗋𝗈𝗏𝖾𝗋}$ (Merlin) and a randomized polynomial-time $\mathrm{𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋}$ (Arthur) that satisfies the following properties for every input $x$:

• $\mathrm{■}$

  Completeness: If $x\in L$, then there is a $\mathrm{𝖯𝗋𝗈𝗏𝖾𝗋}$ that makes the $\mathrm{𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋}$ accept w.p. $\ge 2/3$.

• $\mathrm{■}$

  Soundness: If $x\notin L$, then no $\mathrm{𝖯𝗋𝗈𝗏𝖾𝗋}$ can make the $\mathrm{𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋}$ accept w.p. $>1/3$.

Let $\mathrm{𝐀𝐌}$ denote the set of languages with an Arthur–Merlin protocol. The round-collapse theorem of Babai [5] implies that every language in $\mathrm{𝐀𝐌}$ actually has an Arthur–Merlin protocol with two rounds: $\mathrm{𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋}$ sends the first message, $\mathrm{𝖯𝗋𝗈𝗏𝖾𝗋}$ sends a proof, and $\mathrm{𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋}$ decides whether $x\in L$. Hence, $\mathrm{𝐀𝐌}$ can be seen as a randomized version of $\mathrm{𝐍𝐏}$; indeed, one can prove that $\mathrm{𝐀𝐌}=\mathrm{𝐍𝐏}$ under circuit lower bound assumptions [44, 62, 75, 76].

In this paper, we will distinguish between the two notions $\mathrm{𝐅𝐍𝐏}$ and $\mathrm{𝐒𝐞𝐚𝐫𝐜𝐡𝐍𝐏}$.

While it is clear that $\mathrm{𝐅𝐍𝐏}\subseteq \mathrm{𝐒𝐞𝐚𝐫𝐜𝐡𝐍𝐏}$, the following example suggests that this inclusion is strict.

For more knowledge about nondeterministic algorithms, readers are referred to [17, Section 2.4].

Recall that $\mathrm{TAUT}$, the set of DNF tautologies, is the canonical $\mathrm{𝐜𝐨𝐍𝐏}$-complete problem. A propositional proof system is simply a nondeterministic algorithm for $\mathrm{TAUT}$. More formally:

It is easy to see that the existence of proof complexity generators is closely related to the hardness of range avoidance. In fact we have:

Roughly speaking, ${\mathrm{𝖯𝖵}}_1$ is a theory of bounded arithmetic capturing “polynomial-time” reasoning. The language of ${\mathrm{𝖯𝖵}}_1$, $ℒ(\mathrm{𝖯𝖵})$, contains a function symbol for every polynomial-time algorithm $f:{\mathbb{N}}^k\to \mathbb{N}$, defined using Cobham’s characterization of polynomial-time functions [18]. Although Cook’s $\mathrm{𝖯𝖵}$ [20] was originally defined as an equational theory (i.e., the only relation in $\mathrm{𝖯𝖵}$ is equality and there are no quantifiers), one can define a first-order theory ${\mathrm{𝖯𝖵}}_1$ by adding suitable induction schemes [20, 59]. In the literature, the notation $\mathrm{𝖯𝖵}$ is often used to refer to the set of polynomial-time computable functions as well. The precise definition of ${\mathrm{𝖯𝖵}}_1$ is somewhat involved, and we refer the reader to the textbooks [48, 21, 58] and references [20, 40, 14, 60].

To capture reasoning in randomized polynomial time, Jeřábek [38, 39, 41] defined a theory ${\mathrm{𝖠𝖯𝖢}}_1$ by extending ${\mathrm{𝖯𝖵}}_1$ with the dual weak Pigeonhole Principle for $\mathrm{𝖯𝖵}$ functions (i.e., polynomial-time functions). Let $\mathrm{𝖤𝗏𝖺𝗅}(G,x):=G(x)$ be the circuit evaluation function. For a function $\mathrm{\ell }(n)>n$, define ${\mathrm{dwPHP}}_{\mathrm{\ell }}(\mathrm{𝖤𝗏𝖺𝗅})$ to be the following sentence
${\mathrm{dwPHP}}_{\mathrm{\ell }}(\mathrm{𝖤𝗏𝖺𝗅}):=$ $\forall n\in \mathrm{𝖫𝗈𝗀}\forall \text{circuit }G:{\{0,1\}}^n\to {\{0,1\}}^{\mathrm{\ell }(n)}\exists y\in {\{0,1\}}^{\mathrm{\ell }(n)}\forall x\in {\{0,1\}}^n[\mathrm{𝖤𝗏𝖺𝗅}(G,x)\ne y].$

Here, “$n\in \mathrm{𝖫𝗈𝗀}$” is the standard notation in bounded arithmetic, which means that $n$ is the bit-length of some object; this notation allows us to reason about objects of size $\mathrm{poly}(n)$ instead of merely size $\mathrm{polylog}(n)$. The above sentence can be interpreted as the totality of Avoid: every input $G:{\{0,1\}}^n\to {\{0,1\}}^{\mathrm{\ell }(n)}$ has at least one solution $y$.

For this paper, it suffices to think of $\mathrm{\ell }(n)$ as a large polynomial in $n$; in fact, under suitable hardness assumptions, we will be able to show that ${\mathrm{𝖯𝖵}}_1$ cannot prove ${\mathrm{dwPHP}}_{\mathrm{\ell }}$ for every polynomial $\mathrm{\ell }(n)$. This suffices to separate ${\mathrm{𝖠𝖯𝖢}}_1$ from ${\mathrm{𝖯𝖵}}_1$.

Below is the only property of strong seeded extractors that we will use:

Let $𝒫$ be a proof system and $G:{\{0,1\}}^n\to {\{0,1\}}^{\mathrm{\ell }}$ be a function computable in polynomial size where $\mathrm{\ell }>n$. (We allow $G$ to take non-uniform advice.) Let $b\in {\{0,1\}}^{\mathrm{\ell }}$, denote as ${\tau }_b(G)$ the propositional formula encoding that $b$ is not in the range of $G$. We say $G$ is a:

• $\mathrm{■}$

  demi-bits generator against $𝒫$, if for at least a $1/3$ fraction of $b\in {\{0,1\}}^{\mathrm{\ell }}$, $𝒫$ does not have polynomial-size proof of ${\tau }_b(G)$; and $G$ is a

• $\mathrm{■}$

  proof complexity generator against $𝒫$, if for every $b\in {\{0,1\}}^{\mathrm{\ell }}$, $𝒫$ does not have polynomial-size proof of ${\tau }_b(G)$.

The precise definition of ${\tau }_b(G)$ as a $3$-CNF is as follows. The variables of ${\tau }_b(G)$ consist of $x\in {\{0,1\}}^n$ and $\mathrm{𝗁𝗂𝗌𝗍}\in {\{0,1\}}^s$, where $s$ is the number of internal gates in $G$ (including the output gates but not including the input gates). The intended meaning is that $G(x)=b$ and $\mathrm{𝗁𝗂𝗌𝗍}$ represents the values of internal gates of $G$ during the computation of $G(x)$. Each gate in $G$ corresponds to a bit $v_g$; if $g$ is an input (internal) gate then $v_g$ refers to some $x_i$ (${\mathrm{𝗁𝗂𝗌𝗍}}_i$). For each internal gate $g\in G$ labeled by an operation ${\circ }_g$ (such as $\wedge$, $\vee$, or $\oplus$) and two children gates $g_l,g_r$, we have a constraint

in ${\tau }_b(G)$. Similarly, for each $i\in [\mathrm{\ell }]$ representing an output gate $g_i$, we have a constraint

in ${\tau }_b(G)$. Note that since every constraint only depends on at most $3$ variables, it can be written as a $3$-CNF of size at most $2^3=8$, and we can add every clause in this $3$-CNF into ${\tau }_b(G)$. We assume that the $\oplus$ gate of fan-in $2$ is included in our basis (looking ahead, it will be used to implement the extractor). The $3$-CNF ${\tau }_b(G)$ is simply the union of ($3$-CNFs generated from) these constraints over every internal and output gate $g\in G$.

Now we define the notion of simple parity reductions between two CNFs. This is a technical notion that we need in Claim 30.

We say a proof system $𝒫$ is closed under simple parity reductions if there is a polynomial $p$ such that the following holds. For every CNF $F$ and $G$, if there is a simple parity reduction from $F$ to $G$ and there is a length-$\mathrm{\ell }$ $𝒫$-proof of $G$, then there is a length-$p(\mathrm{\ell })$ $𝒫$-proof of $F$.

We note that this notion is weaker than that of (degree-$1$) algebraic reductions in [10, 23]. It follows from [23, Lemma 8.3] that many algebraic proof systems (such as Nullstellensatz and Polynomial Calculus) over $\mathrm{GF}(2)$ are closed under simple parity reductions when the complexity measure is degree. While we do not know if $\mathrm{𝖱𝖾𝗌}[\oplus ]$ (resolution over linear equations modulo $2$ [36]) is closed under low-degree algebraic reductions, it is straightforward to prove that $\mathrm{𝖱𝖾𝗌}[\oplus ]$ is closed under simple parity reductions (see Appendix C of the full version).

Recall that $G:{\{0,1\}}^n\to {\{0,1\}}^N$ is a purported demi-bits generator, $\mathrm{𝖤𝗑𝗍}:{\{0,1\}}^N\times {\{0,1\}}^d\to {\{0,1\}}^m$ is an extractor, and for a fixed $r\in {\{0,1\}}^d$ we define the circuit $C_r:{\{0,1\}}^n\to {\{0,1\}}^m$ as

We say that $\mathrm{𝖤𝗑𝗍}$ is linear if for every fixed randomness $r$, the function $\mathrm{𝖤𝗑𝗍}(\cdot ,r):\mathrm{GF}{(2)}^N\to \mathrm{GF}{(2)}^m$ is $\mathrm{GF}(2)$-linear. For every $r$ we fix a circuit ${\mathrm{𝖤𝗑𝗍}}_r$ for computing $\mathrm{𝖤𝗑𝗍}(\cdot ,r)$ using $\oplus$ gates of fan-in $2$ only.

First, as a sanity check, we show that ${\tau }_y(G)$ follows from ${\tau }_z(C_r)$ logically: Suppose that ${\tau }_y(G)$ is false and that $y=G(s)$ for some $s\in {\{0,1\}}^n$, then