SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Abstract

We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman assumption. Our SNARG is also unambiguous: for every (true) statement x, it is computationally hard to find any accepting proof for x other than the proof produced by the prescribed prover strategy.

We obtain our result by showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system. Our new technical contributions are (1) giving a $TC^0$ circuit family for finding roots of cubic polynomials over a special family of characteristic-2 fields (Healy-Viola, STACS 2006) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC 1990) only involve degree 3 polynomials over said fields.

Along the way, since we can instantiate the Fiat-Shamir heuristic for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) hard problems in the complexity class $\textsf{PPAD}$, assuming the sub-exponential hardness of DDH. Previous $\textsf{PPAD}$ hardness results required either bilinear maps or the learning with errors assumption.

1 Introduction

Succinct non-interactive arguments ($\textsf{SNARGs}$) [Mic94] are short, easy to verify, and computationally sound proofs that a statement x belongs to a potentially complex language L. In principle, one could hope to construct extremely efficient $\textsf{SNARG}$s for all $\textsf{NP}$ languages; indeed, in the random oracle model, there exists a non-interactive¹ argument system for any L decidable in non-deterministic time T(n) with proof size $\textsf{poly}(\lambda , \log T)$ and verification time $\textsf{poly}(\lambda , \log T) + \tilde{O}(n)$, where $n = |x|$ and $\lambda$ is a security parameter [Mic94]. Unfortunately, there are significant concerns about whether it is possible to construct such arguments based on falsifiable and preferably standard computational assumptions [Bar01, GK03, GW11, BBH+19].

In this work, we consider $\textsf{SNARGs}$ for a restricted class of languages: those computable by logspace-uniform circuit families of bounded depth D (and arbitrary polynomial size S). These were first studied in the interactive setting by Goldwasser, Kalai, and Rothblum [GKR08], who constructed (statistically sound) interactive proofs of size $D\cdot \textsf{poly}\log (S)$ and verification time $D \cdot \textsf{poly}\log (S) + \tilde{O}(n)$. (We will henceforth refer to this as the GKR protocol.) Recently, a work of Jawale, Kalai, Khurana, and Zhang [JKKZ21] showed how to convert this proof system into a $\textsf{SNARG}$ by instantiating the Fiat-Shamir heuristic [FS87, BR93] for the GKR protocol in the standard model (building upon [CCH+19]). Their $\textsf{SNARG}$ is proved secure under the sub-exponential hardness of the learning with errors ($\textsf{LWE}$) assumption. Aside from [JKKZ21], $\textsf{SNARGs}$ for (even unbounded depth) deterministic computation are now known from bilinear maps [KPY19, WW22, KLVW23], the polynomial hardness of $\textsf{LWE}$ [CJJ22], and a combination of the decisional Diffie-Hellman ($\textsf{DDH}$) and Quadratic Residuosity ($\textsf{QR}$) assumptions [HJKS22, KLVW23].

$\textsf{SNARGs}$ from $\textsf{DDH}$. In this work, we ask if $\textsf{SNARGs}$ can be built from the $\textsf{DDH}$ assumption alone. We answer this question in the affirmative for $\textsf{SNARGs}$ for bounded-depth computations.

Theorem 1.1

Assuming the sub-exponential hardness of $\textsf{DDH}$, there exist $\textsf{SNARGs}$ for logspace-uniform depth-D, size-S computations. The $\textsf{SNARGs}$ have proof size $\textsf{poly}(\lambda , \log S)\cdot D$ and verification time $\textsf{poly}(\lambda , \log S)\cdot (D + n)$. The prover runs in time $\textsf{poly}(\lambda , S)$.

As stated, our $\textsf{SNARG}$s achieve only non-adaptive soundness: that is, soundness holds for fixed inputs x to the circuit C.² By complexity leveraging (setting $\lambda = n^{1/\epsilon }$ for an appropriate constant $\epsilon$ independent of S), we can achieve soundness that is adaptive with respect to the input x, at the cost of a communication complexity and verification time that are $\textsf{poly}(n, \log S)\cdot D$.

Moreover, our $\textsf{SNARGs}$ are unambiguous [RRR16, CHK+19a], which means that they satisfy a form of soundness even for true statements: for $x\in L$, it is computationally hard to find an accepting proof for x other than the honestly generated proof guaranteed to exist by completeness. Unambiguous $\textsf{SNARGs}$ were previously constructed in [KPY20, JKKZ21] but only known using either bilinear maps or $\textsf{LWE}$.

On a slightly more technical level, we show that (unambiguous) $\textsf{SNARGs}$ for bounded depth can be built from a weaker generic primitive than was known before: (lossy) correlation-intractable hash functions [CGH98, CCH+19, JKKZ21] supporting the complexity class $\textsf{TC}^0$. Previous work relied on a stronger form of correlation intractability (CI) supporting functions in $\textsf{P}$ (or, implicitly, $\textsf{NC}$). Since CI for $\textsf{TC}^0$ was constructed based on $\textsf{DDH}$ in [JJ21], this essentially implies Theorem 1.1. We discuss this in more detail in our technical overview (Sect. 1.1).

Hardness in $\textsf{PPAD}$ from $\textsf{DDH}$. Closely tied to unambiguous $\textsf{SNARGs}$ is the problem of showing the cryptographic hardness of the complexity class $\textsf{PPAD}$ [Pap94, CHK+19a]. $\textsf{PPAD}$ is a complexity class arising from computational game theory that famously includes finding a Nash equilibrium of bimatrix games as a complete problem [DGP09, CDT09]. The work of Choudhuri et al. [CHK+19a] showed that instantiating the Fiat-Shamir heuristic for (many variants of) the sumcheck protocol [LFKN90] suffices to establish $\textsf{PPAD}$-hardness.

In this work, towards instantiating Fiat-Shamir for the GKR protocol, we show how to instantiate Fiat-Shamir for variants of the sumcheck protocol that can be plugged into the framework of [CHK+19a]. Thus, we obtain $\textsf{PPAD}$-hardness from the sub-exponential $\textsf{DDH}$ assumption.

Theorem 1.2

Assuming that $\textsf{DDH}$ is sub-exponentially hard, the complexity class $\textsf{PPAD}$ contains problems that are sub-exponentially hard on average.

Again, we prove Theorem 1.2 by showing that lossy correlation intractable hash functions for $\textsf{TC}^0$ suffice to construct the non-interactive sumcheck protocol.

In the rest of this introduction, we give a brief overview of our techniques for proving Theorem 1.1 and Theorem 1.2.

1.1 Technical Overview

We begin by discussing our contributions on applying the Fiat-Shamir heuristic to the sumcheck protocol [LFKN90]. We first recall the sumcheck protocol.

The Sumcheck Protocol. In the sumcheck protocol, the prover and verifier begin with a degree³-d polynomial $f(x_1, \ldots , x_n)$ in n variables over some finite field $\mathbb {F}$. The prover wants to convince the verifier of the value of the sum $y = \sum _{a\in \{0,1\}^n} f(a)$, where the sum is taken over $\mathbb {F}$. This is accomplished by the following interactive protocol:

• The prover sends the univariate polynomial

  $$g(x) = \sum _{a_2, \ldots , a_n \in \{0,1\}} f(x, a_2, \ldots , a_n) .$$

• The verifier checks that $g(0) + g(1) = y$. If so, it samples a uniformly random $\beta \leftarrow \mathbb {F}$ and sends $\beta$ to the prover.

• The prover and verifier recursively execute the sumcheck protocol with respect to the polynomial $f_\beta (x_2, \ldots , x_n) = f(\beta , x_2, \ldots , x_n)$ and value $y_\beta = g(\beta )$.

• In the base case, the verifier simply evaluates $f(\beta _1,\ldots , \beta _n)$, which it can do given a circuit for f.

As shown in [CCH+19, JKKZ21], this protocol satisfies what is called unambiguous round-by-round soundness. Concretely, what this means (for this protocol) is that once the polynomial g is fixed by the prover, if g is not the correct “partial sum” polynomial, then with high probability over the choice of $\beta$, the prover and verifier will recurse on a false statement. Note also that if the statement (f, y) is false but g is the correct polynomial w.r.t. f, then the verifier will immediately reject.

Removing Interaction via Fiat-Shamir. In this work, we want a non-interactive variant of the sumcheck protocol, which we obtain by instantiating the Fiat-Shamir heuristic [FS87, BR93] for the sumcheck protocol. Concretely, this means that we will have n hash functions $h_1, \ldots , h_n$ sampled from a hash family $\mathcal H$, and the i-th verifier challenge $\beta _i$ is instead computed as a hash $h_i(f,y,g_1, \beta _1, \ldots , g_i)$ of the transcript so far.

Following the bad challenge function paradigm of [CCH+19], we call a challenge $\beta _i$ bad for $(f,y,g_1,\beta _1, \ldots , g_i)$ if (1) $g_i$ is not the correct polynomial $g_i^* = \sum _{a_{i+1}, \ldots , a_n} f(\beta _1, \ldots , \beta _{i-1}, x, a_2, \ldots , a_n)$ and (2) the resulting recursive claim $(f_{\beta _1, \ldots , \beta _i}, g_i(\beta _i))$ is true. In the case of the sumcheck protocol, the set of all bad $\beta$ is precisely the set of roots of the polynomial $g_i(x) - g_i^*(x)$. Note that there are at most d such roots, as $g_i(x) - g_i^*(x)$ is a nonzero polynomial of degree at most d. Thus, letting $F_1^{(i)}, \ldots , F_d^{(i)}$ denote functions where $F_j^{(i)}$ maps $(f, \beta _1, \ldots , \beta _{i-1}, g_i )$ to the jth root of $g_i - g_i^*$ in $\mathbb {F}$ (if one exists), we know by [CCH+19] that the resulting non-interactive protocol is sound if each $h_i$ is correlation-intractable (CI) [CGH98, CCH+19] for $F_1^{(i)}, \ldots , F_d^{(i)}$.

Recall that a hash function family $\mathcal H$ is CI for a relation R (generalizing the case of a function f) if given $h \leftarrow \mathcal H$ it is computationally hard to find an input $\alpha$ such that $(\alpha , h(\alpha ))\in R$. There has been much recent progress on constructing CI hash functions based on standard cryptographic assumptions (e.g. [CCH+19, PS19, BKM20, JJ21, HLR21]). The construction relevant to us in this work is that of [JJ21], which built a CI hash function family supporting functions computable in the complexity class $\textsf{TC}^0$ (constant-depth threshold circuits) based on sub-exponential $\textsf{DDH}$.

Thus, in order to use the [JJ21] hash function family, we ask: what is the computational complexity of the bad challenge functions $F_j^{(i)}$?

Naïvely, it is not even clear that the $F_j^{(i)}$ functions are in $\textsf{P}$, because even computing the polynomial $g^*_i$ (as a function of $f, \beta _1, \ldots , \beta _{i-1}$) seems to require time $2^{n-i}$. However, following [JKKZ21], if the functions $h_1, \ldots , h_{i-1}$ are lossy [PW08], we can guess the challenges $\beta _1, \ldots , \beta _{i-1}$ in advance and non-uniformly hard-wire the polynomial $g^*_i$ in our security reduction (incurring a sub-exponential security loss from guessing $\beta _1, \ldots , \beta _{i-1})$. That is, we will actually define each $h_i$ to be the composition of a [JJ21] hash function with a lossy trapdoor function family (LTDF). The resulting composition will still be CI for $\textsf{TC}^0$ circuits provided that inversion of a LTDF can be computed in $\textsf{TC}^0$, which we observe (see Sect. 2.2) is possible for a simple modification of standard constructions [PW08, FGK+10].

1.1.1 The Circuit Complexity of Root-Finding

Finally, we arrive at the first of two main challenges in this work. With the setup so far, we have reduced the problem to achieving correlation intractability for a circuit class that has the power to find roots of univariate polynomials over a field $\mathbb {F}$ (and some additional $\textsf{TC}^0$ operations). If root-finding over finite fields were known to be in $\textsf{TC}^0$, we would be done! Unfortunately, standard root-finding algorithms [Ber70, Rab80, CZ81] are not known to be implementable in $\textsf{TC}^0$. Indeed, it is clear that some care is required: if p is a large (size $2^\lambda$) prime, finding roots of even degree 1 polynomials over $\mathbb {F}_p$ is at least as hard as computing mod p inverses $a\mapsto a^{-1} \pmod p$, which is not known to be in $\textsf{TC}^0$.

Thus, it is clear that to have any hope of root-finding in $\textsf{TC}^0$, one must carefully choose the field $\mathbb {F}$. In this work, we make use of a special characteristic-2 field ensemble $\mathbb {K}= \{\mathbb {K}_n\}$ studied by Healy and Viola, henceforth referred to as the Healy-Viola field ensemble, over which many field operations (including the inversion map $a\mapsto a^{-1}$) are known to be in $\textsf{TC}^0$ [HV06]. In this work, we show:

Lemma 1.1

(informal, see Theorem 3.4). There is a $\textsf{TC}^0$ circuit family that finds all roots of cubic (degree $d=3$) univariate polynomials over the Healy-Viola field ensemble.

We emphasize that the algorithm in Lemma 1.1 only finds roots that lie in the ground field $\mathbb {K}$, not (necessarily) roots that lie in extensions⁴ of $\mathbb {K}$. Combining Lemma 1.1 with our discussion so far, we obtain the following result:

Theorem 1.3

(informal). Fiat-Shamir for degree-3 sumcheck protocols over the Healy-Viola field ensemble is sound using hash functions that are Lossy CI for $\textsf{TC}^0$, and is therefore instantiable under sub-exponential $\textsf{DDH}$.

That is, by carefully instantiating the field ensemble and designing a special-purpose root-finding algorithm, we show how to use the Jain-Jin hash function family [JJ21] to achieve a non-interactive sumcheck for degree three polynomials. This is a very limited form of non-interactive sumcheck, but we next show how to leverage this limited form of sumcheck to prove Theorems 1.1 and 1.2. Finally, at the end of this overview we sketch a proof of Lemma 1.1, which is one of our main technical contributions.

1.1.2 $\textsf{PPAD}$ Hardness with Degree-2 Sumchecks

First, we show that $\textsf{PPAD}$-hardness can be established making use of our non-interactive sumcheck protocol for polynomials of degree as low as 2!

To employ the framework of [CHK+19a], all that we require is that our sumcheck protocol can be used to prove membership in a $\textsf{NP}$-hard language. In [CHK+19a], this is accomplished by using sumcheck over a large characteristic field as an argument system for $\#\textsf{SAT}$.

Since our non-interactive sumcheck works over a characteristic-2 field, we instead start with $\oplus \textsf{SAT}$, the computational problem of counting the parity of the number of satisfying assignments of a $\textsf{SAT}$ formula. This problem is also $\textsf{NP}$-hard under randomized reductions [VV85]. Given such a $\textsf{SAT}$ formula $\phi$, this parity can then be expressed as a sumcheck problem over $\mathbb {K}$:

$$ \oplus \textsf{SAT}(\phi ) = \sum _{a_1, \ldots , a_n \in \{0,1\}} \phi (a_1, \ldots , a_n). $$

Moreover, $\phi$ can be arithmetized so that it is represented by a polynomial-size arithmetic circuit over $\mathbb {F}_2 \subset \mathbb {K}$. In order for our non-interactive sumcheck protocol to be applicable, we would need the individual degree of this arithmetization to be at most 3. Given that we are doing a “standard” arithmetization, what is the individual degree of $\phi$? If $\phi$ is a CNF, this is nothing more than the maximum number of clauses that an individual variable appears in.

Conveniently, it is known that $\oplus \textsf{SAT}$ on arbitrary formulas reduces to $\oplus \textsf{SAT}$ on CNFs (which are not 3-regular) where each variable occurs in at most three clauses [Tov84]. This suffices to establish Theorem 1.2 by invoking Theorem 1.3 and [CHK+19a] with respect to a degree-3 sumcheck protocol.

Note on Adaptivity. In order to obtain Theorem 1.2, following [JKKZ21], we need a non-interactive sumcheck protocol satisfying a form of soundness referred to as “prefix-adaptive soundness” (an intermediate notion between non-adaptive and adaptive soundness). Our non-interactive sumcheck protocol satisfies this form of soundness exactly as in [JKKZ21].

Variable-Extended Formulations. While we have already proved Theorem 1.2, we will give a slightly different second proof, since this will be a crucial step in proving Theorem 1.1. Specifically, we will prove Theorem 1.2 by invoking a degree 2 (rather than 3) sumcheck protocol. To do this, we start with the sumcheck problem above with respect to (the standard poly-size arithmetization of) $\phi$. The individual degree of $\phi$ may be very large; nevertheless, we will show that $\oplus \textsf{SAT}(\phi )$ can be expressed as a different degree 2 sumcheck.

We accomplish this using a Cook–Levin style reduction, in which we introduce new variables $y_1, \ldots , y_m$ that are supposed to represent a wire assignment of the NAND-circuit computing $\phi$. Concretely, consider the polynomial f in $n+m$ variables defined as

$$\begin{aligned} f(&x_1,\ldots ,x_n, y_1, \ldots , y_m) \\ {}&= y_m \cdot \prod _{(i,j,k)\in \textsf{Gates}(\phi )}\left( y_i + y_j y_k\right) \prod _{i=1}^n \left( x_i\prod _{j\in S_i}y_j + (1-x_i)\prod _{j\in S_i} (1-y_{j})\right) , \end{aligned}$$

where for every $i\in [n]$, $S_i \subset [m]$ is defined to be the subset of leaf vertices in $\phi$ that are assigned the input $x_i$. In words, f (arithmetically) checks that (i) the output wire $y_m$ is 1, (ii) each NAND gate is computed correctly, and (iii) the leaf variables were all assigned with respect to a consistent $x\in \{0, 1\}^n$. For boolean inputs, $f(x_1, \ldots , x_n, y_1, \ldots , y_m)$ is thus either zero or equal to $\phi (x_1, \ldots , x_n)$ (which happens for one “consistent” assignment to y). Therefore,

$$ \sum _{a_1, \ldots , a_n \in \{0,1\}} \phi (a_1, \ldots , a_n) = \sum _{\begin{array}{c} a_1, \ldots , a_n \in \{0,1\}\\ b_1, \ldots , b_m \in \{0,1\} \end{array}} f(a_1, \ldots , a_n, b_1, \ldots , b_m), $$

so computing $\oplus \textsf{SAT}(\phi )$ reduces to an f-sumcheck. Finally, note that f has individual degree 2! Indeed, it is linear in the $x_i$, quadratic in the non-leaf $y_j$ (as they are each used in two gates of $\phi$), and quadratic in the leaf $y_j$ (each is used in one gate of $\phi$ and has a linear dependence in the “input encoding” part of f).

In general, we say that the above transformation produces a “variable-extended formulation” of a boolean formula $\phi$ (see Definition 5.1), and this is a key step in proving Theorem 1.1.

1.1.3 $\textsf{SNARGs}$ via Degree 3 Sumchecks

Armed with our new approach of constructing variable-extended formulations of sumcheck polynomials, we proceed to sketch our proof of Theorem 1.1. We prove Theorem 1.1 by choosing a suitable variant of the [GKR08] protocol, modifying it to rely only on degree 3 sumchecks, and then (essentially⁵) applying Theorem 1.3.

At a high level, the [GKR08] protocol  proves that $C(x) = y$ for a logspace-uniform depth D, size S circuit C by iteratively producing pairs of claims about a multilinear extension encoding of each layer $L_i$ of the computation tableau of the circuit (when evaluated on input x). That is, each $L_i = L_i(x) \in \{0,1\}^{S}$ is a string containing the value of all level i vertices in the evaluation of C(x), and $L_i$ is interpreted as a function $\ell _i: \{0,1\}^{\log S} \rightarrow \{0,1\}$, which can then be extended to a multilinear function $\hat{\ell }_i: \mathbb {K}^{\log S}\rightarrow \mathbb {K}$. The GKR protocol begins with an evaluation claim about $\hat{\ell }_D$ (the end of the computation) and ends with a pair of evaluation claims about $\hat{\ell }_0$; since the input layer of C has only width n (rather than, say, S/D) $\hat{\ell }_0$ can be evaluated in O(n) field operations and thus can be checked by the verifier.

The key step is to understand how to reduce claims about $\hat{\ell }_i$ to claims about $\hat{\ell }_{i-1}$; this boils down to the “sumcheck-friendly” equation which writes $\ell _i(a)$ as

$$ \sum _{b, c \in \{0,1\}^{\log S}}\Bigg [ \chi _{\textrm{add}}^{(i)}(a, b, c) \Big (\ell _{i-1}(b) + \ell _{i-1}(c)\Big ) + \chi _{\textrm{mult}}^{(i)}(a, b, c)\Big (\ell _{i-1}(b) \ell _{i-1}(c)\Big )\Bigg ],$$

where $\chi _{\textrm{add}},\chi _{\textrm{mult}}$ are the gate indicator functions that take as input three wire labels (a, b, c) for the circuit and indicates whether an addition (respectively, multiplication) gate is present at these three wires. This equation can then be extended multilinearly to a similar equation relating $\hat{\ell }_i$ to $\hat{\ell }_{i-1}$.

Given this summary of the GKR protocol, the key question for us is as follows: what is the degree of the sumcheck polynomials? By inspection, it turns out that this degree is one more than the degree of the arithmetizations of $\chi _{\textrm{add}}, \chi _{\textrm{mult}}$. Naively, their degree may be up to $O(\log S)$ (i.e., the number of leaves in the boolean formulas for $\chi _{\textrm{add}},\chi _{\textrm{mult}}$), but by using variable-extended formulations of these polynomials, we can reduce this degree to 2 (at the cost of adding $O(\log S)$ auxiliary variables to the sumcheck). Note that it is crucial for prover efficiency that we only add $O(\log S)$ (rather than $\textsf{poly}\log S$) new variables, as the prover’s running time is exponential in this number of variables. We show that an appropriate extended formulation exists making use of an analysis due to Goldreich [Gol18] of $\chi _{\textrm{add}},\chi _{\textrm{mult}}$.

In total, this results in a GKR protocol variant relying on degree 3 sumchecks over $\mathbb {K}$, and thus we can instantiate Fiat-Shamir for this protocol based on sub-exponential $\textsf{DDH}$.

1.1.4 Cubic Root Finding: Proving Lemma 1.1

Finally, we sketch a proof of Lemma 1.1, which states that roots of cubic polynomials over Healy-Viola fields $\mathbb {K}$ can be computed in $\textsf{TC}^0$. We will not resort to general-purpose root-finding algorithms [Ber70, Rab80, CZ81] (which all have a high-depth iterative nature) but instead turn to explicit formulae for roots of low degree polynomials. We show that these explicit formulae can be converted into low-depth algorithms.

First, let us consider the degenerate cases of linear and quadratic polynomials.

• Root-finding for linear polynomials is equivalent to solving a linear equation over $\mathbb {K}$, which reduces to multiplication and inversion over $\mathbb {K}$. These operations were shown to be in $\textsf{TC}^0$ in [HV06].

• Since $\mathbb {K}$ has characteristic 2, root-finding for quadratic polynomials reduces to finding roots of polynomials of the form $x^2 + c$ and $x^2 + x + c$.⁶ Then:

  • The polynomial $x^2 + c$ always has a double root of $c^{|\mathbb {K}|/2}$,⁷ which can be computed in $\textsf{TC}^0$ via low-depth exponentiation [HV06].

  • The polynomial $x^2 + x + c$ has roots given by an explicit formula as a function of c related to its orbit $\{c, c^2, c^4, \ldots , c^{2^{n-1}}\}$ under the Frobenius map $\alpha \mapsto \alpha ^2$. The form depends on the order of two dividing $\log |\mathbb K|$ (which turns out to be 1 for the Healy–Viola fields) and is given implicitly in our proof of Theorem 3.3.

Passing to a Quadratic Extension of $\mathbb {K}$. We note that [CJJ21] also proves that quadratic root-finding in $\mathbb {K}$ is in $\textsf{TC}^0$ with a different approach; however, we give a more powerful algorithm that actually finds roots of this polynomial in an explicit quadratic extension $\mathbb {L}\supset \mathbb {K}$ (even when no roots in $\mathbb {K}$ exist). This more powerful algorithm is necessary to prove the cubic case of Lemma 1.1.

In order for this to make sense, we must be able to construct $\mathbb {L}$ in a way so that operations in $\mathbb {L}$ are similarly efficient to operations in $\mathbb {K}$. Fortunately, we are able to do this with a careful construction, noting that one way to construct a quadratic extension of $\mathbb {K}$ is to add to it a solution to the equation $x^2 + x + \omega = 0$, where $\omega$ is an explicit cube root of unity in $\mathbb {K}$. Since $\omega$ alone generates a constant-size field, this greatly simplifies the problem of giving efficient algorithms for operations over $\mathbb {L}$. We show in Theorem 3.2 that all of the relevant field operations on $\mathbb {L}$ are in $\textsf{TC}^0$, which requires opening up the [HV06] construction and extending their analysis to $\mathbb {L}$.

The Cubic Case. Finally, we compute roots of cubic polynomials over $\mathbb {K}$ using an algorithmic variant of the cubic formula [Lag70] over characteristic 2 fields. At a high level, the characteristic 2 cubic formula reduces computing roots of a cubic polynomial (given its coefficients), modulo basic operations, to the following tasks:

• 1. Finding roots of a related quadratic polynomial defined over $\mathbb {K}$.

• 2. Computing the cube root map $\alpha \mapsto \alpha ^{1/3}$ (modulo cube roots of unity).

• 3. Solving a constant-size linear system involving these cube roots.

In Sect. 3, we show that all of these procedures are computable in $\textsf{TC}^0$ and thus roots of all cubic polynomials can be computed in $\textsf{TC}^0$.

One important subtlety is that the roots computed in (1) above are not necessarily in $\mathbb {K}$, but in the quadratic extension $\mathbb {L}$; relatedly, (2) requires computing cube roots of elements of $\mathbb {L}$. One must be careful to argue that (in our setting) the cubic formula algorithm does not have to pass into a degree 6 (or degree 3) extension of $\mathbb {K}$, which we have not explicitly constructed.

For a full explanation/proof of Lemma 1.1, we refer the reader to Sect. 3 (Theorem 3.4).

1.2 Related Work

Fiat-Shamir in the Standard Model. Over the last few years, a line of work including [CCR16, KRR17, CCRR18, HL18, CCH+19, PS19, BKM20, JJ21, HLR21, CJJ21, CJJ22, HJKS22] and many others has studied the instantiability of the Fiat-Shamir heuristic using concrete, efficiently computable hash function families. Starting with the work of [CCH+19], there have been instantiations based on standard cryptographic assumptions (initially the learning with errors assumption [CCH+19, PS19]). The work of [JJ21] constructed $\textsf{NIZK}$s for $\textsf{NP}$ under the sub-exponential $\textsf{DDH}$ assumption by building a hash family that is correlation-intractable for $\textsf{TC}^0$ functions from sub-exponential $\textsf{DDH}$. Beginning with the works of [CCH+19, JKKZ21], applying Fiat-Shamir to the [GKR08] protocol (to construct $\textsf{SNARG}$s in the standard model) has been explicitly studied, including a construction based on sub-exponential $\textsf{LWE}$ [JKKZ21]. Finally, more recently the Fiat-Shamir approach has been used to build succinct batch arguments for $\textsf{NP}$ [CJJ21, CJJ22, HJKS22] which in turn imply $\textsf{SNARG}$s for $\textsf{P}$ [CJJ22, KVZ21].

$\textsf{SNARGs}$ Without Fiat-Shamir. There have additionally been constructions of $\textsf{SNARG}$s for $\textsf{P}$ that do not rely on the Fiat-Shamir heuristic [KPY19, GZ21, WW22, KLVW23], all of which currently rely on some form of cryptographic bilinear maps.

Cryptographic Hardness of $\textsf{PPAD}$. Establishing hardness in $\textsf{PPAD}$ based on cryptographic assumptions has also received considerable attention, including [BPR15, GPS16, CHK+19a, CHK+19b, EFKP20, LV20, KPY20, BCH+22]. Previously, $\textsf{PPAD}$-hardness was known under the following sets of assumptions:

• Polynomially secure functional encryption [BPR15, GPS16], which can be built by a particular combination of three concrete assumptions [JLS21],

• Super-polynomial hardness of a falsifiable assumption on bilinear maps [KPY20],

• The sub-exponential $\textsf{LWE}$ assumption [JKKZ21], and

• A combination of (polynomially-secure) $\textsf{LWE}$ and the (polynomial) hardness of iterated squaring modulo a composite [BCH+22].

2 Preliminaries

2.1 Cryptographic Groups

Let $\mathbb G = \{\mathbb G_\lambda \}$ be a group ensemble, indexed by a security parameter $\lambda$, such that group operations (and testing equality) can be computed in time $\textsf{poly}(\lambda )$.

Definition 2.1

(Decisional Diffie-Hellman Assumption). We say that the decisional Diffie-Hellman ($\textsf{DDH}$) assumption with time T and advantage $\mu$ holds for $\mathbb G$ if any $T(\lambda )$-time algorithm $\mathcal A(\cdot )$ has advantage at most $\mu$ in distinguishing a random “DDH-tuple” $(g, g^x, g^y, g^{xy})$ from a tuple $(g, g^x, g^y, g^z)$ (for uniformly random x, y, z).

In this paper, we work exclusively with cryptographic groups satisfying the following conditions:⁸

• 1. Iterated group multiplication $g_1, g_2, \ldots , g_t \mapsto \prod _{i=1}^t g_i$ can be computed by a $\textsf{poly}(\lambda , t)$-size, low-depth circuit family. As in [JJ21], there are two flavors of results: one requires $\textsf{TC}^0$ circuits (which exist for, e.g., subgroups of $\mathbb Z_q^\times$), while the other requires threshold circuits (with unbounded fanin) of depth $o(\log \lambda )$ (which exist for standard elliptic curve groups [JJ21]). In the latter case, we will use complexity leveraging: re-define the group security parameter to be $\kappa = \textsf{poly}\log \lambda$, so that $\textsf{DDH}$ remains polynomially hard and iterated multiplication can be computed in depth $o(\log \log \lambda )$.

• 2. The $\textsf{DDH}$ assumption holds with inverse-subexonential $\mu = 2^{-\lambda ^\epsilon }$ for some constant $\epsilon > 0$. If iterated multiplication requires superconstant-depth threshold circuits, then we require the assumption to hold for $T = 2^{\lambda ^\epsilon }$ (so that we can complexity leverage as above), while if iterated multiplication has $\textsf{TC}^0$ circuits, then we only require the assumption to hold for $T = \textsf{poly}(\lambda )$.

• 3. Letting M denote a uniformly random $n(\lambda )\times n(\lambda )$ matrix (for $n(\lambda ) = \textsf{poly}(\lambda )$) modulo $N = |\mathbb G|$, we have that M is invertible with probability $1-\textsf{negl}(\lambda )$. This holds immediately for prime-order groups or groups with order N that have no polynomial-size prime divisors.

As discussed in [JJ21], properties (1) and (2) are satisfied (that is, $\textsf{DDH}$ is plausible) by common examples such as (subgroups of) $\mathbb Z_q^\times$ or groups of $\mathbb {F}_q$-points of elliptic curves.

2.2 Lossy Trapdoor Functions

Lossy trapdoor functions were first defined and constructed in an influential work of Peikert and Waters [PW08]. Loosely speaking, a lossy trapdoor function family contains two types of functions: injective ones and lossy ones, such that one cannot distinguish between a random injective function in the family and a random lossy function in the family. An injective function can be generated together with a trapdoor, which allows one to efficiently invert the function, whereas a lossy function “loses” most information about its preimage, since its image is much smaller than its domain.

Definition 2.2

( $(T,\omega )$ -Lossy Trapdoor Family)

A quadruple $(\textsf{InjGen},\textsf{LossyGen},\textsf{Eval}, \textsf{Inv})$ of $\textsf{PPT}$ algorithms is said to be a $(T,\omega )$-lossy trapdoor function family if there exist polynomials $n= n(\lambda )$, $n' = n'(\lambda )$, $s=s(\lambda )$ and $t=t(\lambda )$ for which the following syntax and properties are satisfied:

• Syntax.

  • $\textsf{InjGen} (1^\lambda )$ takes as input a security parameter $1^\lambda$ and outputs a pair $(\textsf{k},\textsf{td})$, where $\textsf{k}\in \{0,1\}^s$ is a key corresponding to an injective function and $\textsf{td} \in \{0,1\}^t$ is a corresponding trapdoor.

  • $\textsf{LossyGen} (1^\lambda )$ takes as input a security parameter $1^\lambda$ and outputs a key $\textsf{k}\in \{0,1\}^s$ corresponding to a lossy function.

  • $\textsf{Eval} (\textsf{k},x)$ takes as input a key $\textsf{k}\in \{0,1\}^s$ and an element $x \in \{0,1\}^{n}$ and outputs an element $y \in \{0,1\}^{n'}$.

  • $\textsf{Inv} (\textsf{k},\textsf{td},y)$ takes as input a key $\textsf{k}\in \{0,1\}^s$, a trapdoor $\textsf{td} \in \{0,1\}^t$, and an element $y\in \{0,1\}^{n'}$, and outputs an element $x \in \{0,1\}^{n}\cup \{\bot \}$.

• Properties. The following properties hold:

  • Injective Mode. For every $\lambda \in \mathbb {N}$ and every $\textsf{k}\in \textsf{InjGen} (1^\lambda )$ the function $\textsf{Eval} (\textsf{k}, \cdot )$ is injective. Furthermore, for every $x \in \{0,1\}^{n(\lambda )}$, $\Pr [\textsf{Inv} (\textsf{k},\textsf{td},\textsf{Eval} (\textsf{k}, x)) = x]=1$.⁹

  • $\omega$-Lossiness. For every $\lambda \in \mathbb {N}$ and every $\textsf{k}\in \textsf{LossyGen} (1^\lambda )$ the function $\textsf{Eval} (\textsf{k}, \cdot )$ has an image of size $2^{n(\lambda )-\omega (\lambda )}$.

  • T-Security. There exists a negligible function $\mu$ such that for every $\textsf{poly}(T)$-size adversary $\mathcal{A}$ and for every $\lambda \in \mathbb {N},$

    $$\Big |\mathop {\Pr }\limits _{\textsf{k}\leftarrow \mathcal{G}.\textsf{LossyGen} (1^\lambda )}[\mathcal{A}(\textsf{k})=1]- \mathop {\Pr }\limits _{\textsf{k}\leftarrow \mathcal{G}.\textsf{InjGen} (1^\lambda )}[\mathcal{A}(\textsf{k})=1]\Big | = \mu (T(\lambda ))$$

Theorem 2.1

 [PW08, FGK+10]. Assuming the sub-exponential hardness of $\textsf{DDH}$, for every constant $0< \delta < 1$ and every polynomial $n(\lambda )$, there exists a constant $0<\epsilon <1$ for which there exists a $(T,\omega )$-lossy trapdoor function family for $\omega (\lambda )=n(\lambda )-{\lambda ^{\delta }}$ and $T=2^{\lambda ^{\epsilon }}$.

Moreover, after a $\textsf{td}$-independent preprocessing step, inversion of this function family has threshold circuits of depth O(d), provided that large fan-in multiplication over the $\textsf{DDH}$ group can be computed in depth d.

Proof

We slightly modify the construction due to [FGK+10] in order to obtain $\textsf{TC}^0$ inversion:

• The public key is of the form $g^M$, where g is a generator for an order p group where $\textsf{DDH}$ is hard and M is a $k\times k$ matrix with entries in $\{0, 1, \ldots , p-1\}$. In injective mode, M is a uniformly random invertible matrix. In lossy mode, M is a uniformly random rank 1 matrix. Injective and lossy modes are computationally indistinguishable under the $\textsf{DDH}$ assumption.

• The input x is an element of $\{0,1\}^n$. To evaluate the function, one computes $f_{g^M}(x) = g^{Mx}$ by evaluating the matrix-vector product “in the exponent.”

• The trapdoor in injective mode is as follows:

  $$ \textsf{td} = \begin{bmatrix} a_{ij}\end{bmatrix}_{ij} = M^{-1}, $$

  To invert, we compute $f^{-1}_{\textsf{td}}(g^z) = g^{M^{-1}z}$, where the matrix-vector product

  $$ M^{-1}z = \left( \sum _{j} a_{ij} z_j\right) _i $$

  is computed by exponentiating $g^{z_j} \mapsto g^{a_{ij} z_j}$ and then computing k different k-fold products. Algorithmically, this is done as follows:

  • First compute $g_{j, \ell } = g^{2^\ell z_j}$ for all $0\le j\le \log p$. This does not require $\textsf{td}$ and is thus considered a preprocessing step.

  • Given $\{g_{j, \ell }\}, \textsf{td} = \begin{bmatrix} a_{ij}\end{bmatrix}_{ij}$, compute (for all i, in parallel)

    $$ g^{x_i} = \prod _{j,\ell } g_{j,\ell }^{a_{ij}[\ell ]}, $$

    where $a_{ij}[\ell ]$ denotes the $\ell$th bit of $a_{ij}$. $x_i$ can then be recovered by checking whether the group element is $\textsf{id}_{\mathbb G}$ or g. Since this online step consists of many parallel iterated product operations, its threshold circuit depth essentially matches that of iterated group multiplication.

• Finally, we observe that in lossy mode, $f_{g^M}$ maps a domain of size $p^k$ to a range of size p, thus achieving the desired amount of lossiness for $p = 2^\lambda$ and $k = \lambda ^{1/\delta }$.

2.3 Correlation-Intractable Hash Families

In this section, we recall the notion of a correlation-intractable ($\textsf{CI}$) hash family originally defined in [CGH98]. We start by recalling the notion of a hash family.

Definition 2.3

A hash family $\mathcal{H}$ consists of two algorithms $(\mathcal{H}.\textsf{Gen},\mathcal{H}.\textsf{Hash})$, and parameters $n=n(\lambda )$ and $m=m(\lambda )$, such that:

• $\mathcal{H}.\textsf{Gen}$ is a $\textsf{PPT}$ algorithm that takes as input a security parameter $1^\lambda$ and outputs a key k.

• $\mathcal{H}.\textsf{Hash}$ is a polynomial time computable (deterministic) algorithm that takes as input a key $k\in \mathcal{H}.\textsf{Gen} (1^\lambda )$ and an element $x\in \{0,1\}^{n(\lambda )}$ and outputs an element $y\in \{0,1\}^{m(\lambda )}$.

In what follows when we refer to a hash family, we usually do not mention the parameters n and m explicitly.

Definition 2.4

(T-Correlation Intractable [CGH98]). A hash family $\mathcal{H}=(\mathcal{H}.\textsf{Gen},\mathcal{H}.\textsf{Hash})$ is said to be T-correlation intractable (T-$\textsf{CI}$) for a function family $\mathcal{F}=\{\mathcal{F}_\lambda \}_{\lambda \in \mathbb {N}}$ if the following two properties hold:

• For every $\lambda \in \mathbb {N}$, every $f\in \mathcal{F}_\lambda$, and every $k\in \mathcal{H}.\textsf{Gen} (1^\lambda )$, the functions f and $\mathcal{H}.\textsf{Hash} (k,\cdot )$ have the same domain and the same co-domain.

• For every $\textsf{poly}(T)$-size $\mathcal{A}= \{\mathcal{A}_\lambda \}_{\lambda \in \mathbb {N}}$ there exists a negligible function $\mu$ such that for every $\lambda \in \mathbb {N}$ and every $f \in \mathcal{F}_\lambda$,

  $$\mathop {\Pr }\limits _{\begin{array}{c} k \leftarrow \mathcal{H}.\textsf{Gen} (1^\lambda ) \\ x \leftarrow \mathcal{A}(k) \end{array}}[\mathcal{H}.\textsf{Hash} (k, x) = f(x)] = \mu (T(\lambda )).$$

Theorem 2.2

[JJ21] Assuming sub-exponential hardness of $\textsf{DDH}$ against polynomial-time attackers, there exists a constant $\epsilon >0$ and a T-correlation intractable hash family for $\textsf{TC}^0$, for $T=T(\lambda )=2^{\lambda ^\epsilon }$.

2.4 Lossy $\textsf{CI}$ Hash Functions

In this section we recall the notion of a lossy $\textsf{CI}$ hash family, originally defined in [JKKZ21].

Definition 2.5

($(T, T', \omega )$-Lossy $\textsf{CI}$). A hash family

$$\mathcal{H}= (\mathcal{H}.\textsf{Gen}, \mathcal{H}.\textsf{LossyGen}, \mathcal{H}.\textsf{Hash})$$

is said to be $(T,T',\omega )$-lossy $\textsf{CI}$ for a function family $\mathcal{F}$ if the following holds:

• $(\mathcal{H}.\textsf{Gen},\mathcal{H}.\textsf{Hash})$ is a T-$\textsf{CI}$ hash family for $\mathcal{F}$ (Definition 2.4).

• The additional key generation algorithm $\mathcal{H}.\textsf{LossyGen}$ takes as input a security parameter $\lambda$ and outputs hash key k, such that the following two properties hold:

  • $T'$-Key Indistinguishability. For every $\textsf{poly}(T')$-size adversary $\mathcal{A}$, there exists a negligible function $\mu$ such that for every $\lambda \in \mathbb {N}$

    $$ \left| \mathop {\Pr }\limits _{k \leftarrow \mathcal{H}.\textsf{LossyGen} (1^\lambda )}[\mathcal{A}(k)=1]- \mathop {\Pr }\limits _{k \leftarrow \mathcal{H}.\textsf{Gen} (1^\lambda )}[\mathcal{A}(k)=1] \right| = \mu (T'(\lambda )). $$

  • $\omega$-Lossiness. For every $\lambda \in \mathbb {N}$ and every $k \in \mathcal{H}.\textsf{LossyGen} (1^\lambda )$, denoting by $n=n(\lambda )$ the length of elements in the domain of $\mathcal{H}.\textsf{Hash} (k,\cdot )$,

    $$|\{\mathcal{H}.\textsf{Hash} (k,x)\}_{x \in \{0,1\}^{n(\lambda )}}| \le 2^{n(\lambda )-\omega (\lambda )}.$$

Theorem 2.3

There exists a $(T,T',\omega )$-lossy $\textsf{CI}$ hash family for $\mathcal{F}= \{ \mathcal{F}_\lambda \}_{\lambda \in \mathbb {N}}$ (Definition 2.4) assuming the existence of the following primitives:

• A $(T',\omega )$-lossy trapdoor function family $\mathcal{G}$ (Definition 2.2), such that for every $\lambda \in \mathbb {N}$, $f \in \mathcal{F}_\lambda$, and $\textsf{k}\in \mathcal{G}.\textsf{Gen} (1^\lambda )$, the domain of $\mathcal{G}.\textsf{Eval} (\textsf{k},\cdot )$ is equal to the domain of f.

• A T-$\textsf{CI}$ hash family $\mathcal{H}$ (Definition 2.4) for the function family $\mathcal{F}'$, where the family $\mathcal{F}' = \{ \mathcal{F}'_\lambda \}_{\lambda \in \mathbb {N}}$ is defined as follows: for each $\lambda \in \mathbb {N}$, $f' \in \mathcal{F}'_\lambda$ if and only if there exists $f \in \mathcal{F}_\lambda$, and $(\textsf{k},\textsf{td})\in \mathcal{G}.\textsf{Gen} (1^\lambda )$ such that $f'_\lambda (\cdot )=f_\lambda (\mathcal{G}.\textsf{Inv} (\textsf{k},\textsf{td},\cdot ))$. In fact, this holds even when $\mathcal{G}.\textsf{Inv} (\textsf{k}, \textsf{td}, \cdot )$ is replaced by the online phase of an offline/online (with respect to $\textsf{td}$) algorithm for $\mathcal{G}.\textsf{Inv}$.

2.5 SNARGs for Bounded Depth Computations

In this section we recall the main theorem from [JKKZ21], which claims that (a variant of) the $\textsf{GKR}$ protocol has a standard model Fiat-Shamir instantiation. The $\textsf{GKR}$ protocol considered in [JKKZ21], as well as the one considered in this work, is slightly different from the original protocol proposed in [GKR08], and we elaborate on this protocol in Sect. 5.2. In what follows, when we refer to the $\textsf{GKR}$ protocol we refer to the protocol from [JKKZ21].

The $\textsf{GKR}$ protocol is a publicly verifiable interactive proof for proving the correctness of log-space uniform bounded depth computations. Let C be a log-space uniform circuit of depth d and size s. The $\textsf{GKR}$ protocol for proving that $C(x)=1$ for a given input $x\in \{0,1\}^n$, consists of $d=d(n)$ sub-protocols. Each sub-protocol is a sum-check protocol with $\log s$ variables over a finite field $\mathbb {F}$ of size $\textsf{poly}(|C|)$. In [GKR08] and [JKKZ21] the finite field $\mathbb {F}$ is taken to be an extension of $\textsf{GF}[2]$. In this work we take a particular field of size $2^\lambda$, for which computing roots of a degree-3 univariate polynomial can be done in $\textsf{TC}^0$. See Sect. 3 for details.

In what follows, for any field ensemble $\mathbb {F}= \{\mathbb {F}_n\}_{n\in \mathbb N}$ and any $c=c_n\in \mathbb {N}$ we let $\textsf{GKR}_{\mathbb {F},c}$ denote an instantiation of the $\textsf{GKR}$ protocol with the field $\mathbb {F}$ and where the degree of each variable in the underlying sum-check protocols inside the $\textsf{GKR}$ protocol is bounded by c. We let $\mathcal{F}=\mathcal{F}_{\mathbb {F},c}$ be the function family where each $f\in \mathcal{F}$ has a degree c univariate polynomial $p:\mathbb {F}\rightarrow \mathbb {F}$ hardwired into it. It takes as input a degree c polynomial $p'$ specified by $c+1$ elements in $\mathbb {F}$, and it outputs a root of $p-p'$ (which is an element in $\mathbb {F}$).

Theorem 2.4

[JKKZ21] Fix any field ensemble $\mathbb {F}=\{\mathbb {F}_n\}_{n\in \mathbb N}$ and any $c=c_n\in \mathbb {N}$. Let $\ell$ denote the number of rounds in each sum-check protocol in $\textsf{GKR}_{\mathbb {F},c}$. Fix any $T'(\lambda )\ge \lambda$. Assume there exists a constant $\epsilon >0$ for which there exists a $(T,T',\omega )$-lossy $\textsf{CI}$ hash family for the function family $\mathcal{F}_{\mathbb {F},c}$, with $T(\lambda )=2^{\ell \cdot \lambda ^\epsilon }$ and $\omega (\lambda )=n(\lambda )-\lambda ^\epsilon$. Then there exists a hash family $\mathcal{H}$ such that applying the Fiat-Shamir heuristic to the $\textsf{GKR}_{\mathbb {F},c}$ protocol with the hash family $\mathcal{H}$ results with a $T'$-sound $\textsf{SNARG}$ scheme.

In Sect. 5 we show that any log-space uniform computation has a $\textsf{GKR}_{\mathbb {F},c}$ protocol with $\mathbb {F}$ being any finite field ensemble of size $|\mathbb {F}|=2^\lambda$ and with $c=3$. Moreover, in Sect. 3 we show that computing a root of a degree 3 univariate polynomial over a specific finite field ensemble $\mathbb {F}$ (constructed by Healy and Viola [HV06])  can be done in $\textsf{TC}^0$. This, together with Theorem 2.4 and Theorems 2.1 and 2.2, yields our $\textsf{SNARG}$ construction (Theorem 5.1).

3 Root-Finding in $\textsf{TC}^0$

In this section, we recall the finite field ensemble constructed by Healy and Viola [HV06], who show that their fields admit $\textsf{TC}^0$ circuits for many basic finite field operations (addition, pairwise multiplication, large fan-in multiplication, and exponentiation). We construct explicit degree-2 extensions of all finite fields in this ensemble and prove that the same basic operations in the field extensions have $\textsf{TC}^0$ circuits. Finally, we show that there are $\textsf{TC}^0$ circuits finding all roots of a given quadratic or cubic equation in the original field ensemble of [HV06].

The results of this section will be used in later subsections to instantiate the Fiat-Shamir transform and show PPAD-hardness (Sect. 4) and delegation for bounded-depth computations (Sect. 5).

3.1 Basic Finite Field Operations

Following [HV06], we define the field ensemble $\{\mathbb {K}_n\}_{n = 2\cdot 3^\ell }$ as follows.

Definition 3.1

(Healy-Viola Fields). The Healy-Viola (HV) field $\mathbb {K}_n$, which is an extension of $\mathbb {F}_2$ of degree $n = 2\cdot 3^\ell$, is defined to be the polynomial ring $\mathbb {F}_2[x]/(x^{2\cdot 3^\ell } + x^{3^\ell } + 1)$.

Theorem 3.1

(Healy-Viola [HV06]). The field ensemble $\{\mathbb {K}_n\}$ admits a polynomial-size¹⁰ $\textsf{TC}^0$ circuit family for the following operations:

• Addition: $(\alpha _1, \ldots , \alpha _t)\mapsto \sum _{i=1}^t \alpha _i$ over $\mathbb {K}$.

• (Large fan-in) Multiplication: $(\alpha _1, \ldots , \alpha _t) \mapsto \prod _{i=1}^t \alpha _i$ over $\mathbb {K}$.

• Exponentiation: $(\alpha , T)\mapsto \alpha ^T$ over $\mathbb {K}$. The $\textsf{TC}^0$ circuit size is $\textsf{poly}(n, \log T)$.

In this work, we need to extend Theorem 3.1 to hold over not just $\mathbb {K}$ but a degree-2 extension $\mathbb {L}/\mathbb {K}$.

Definition 3.2

(Degree-2 field extension of HV fields). The degree-2 field extension $\{\mathbb {L}_n\}_{n = 2\cdot 3^\ell }$ of $\mathbb {K}_n$ is defined to be the polynomial ring $\mathbb {L}= \mathbb {K}[y]/(y^2 + y + \omega )$, where $\omega = x^{3^\ell }\in \mathbb {K}$.

We first show that the polynomial $y^2 + y + \omega$ is irreducible over $\mathbb {K}$ (so that $\mathbb {L}$ is in fact a field), which follows by the following standard algebraic argument. Since the polynomial has degree 2, it suffices to show that all the roots of $y^2 + y + \omega$ in a fixed algebraic closure $\overline{\mathbb {K}}= \overline{\mathbb {F}}_2$ are not in $\mathbb {K}$. We do so by arguing that, on the one hand, any root of $y^2 + y + \omega$ in the algebraic closure $\overline{\mathbb {K}}$ has degree exactly 4 over $\mathbb {F}_2$,¹¹ and on the other hand, $\mathbb {K}$ does not contain any degree-4 field elements. The latter follows from the fact that $\deg (\mathbb {K}) = 2\cdot 3^\ell$ is not divisible by 4, so it does not contain a subfield of degree 4 over $\mathbb {F}_2$.¹²

It remains to argue that any root of $y^2 + y + \omega$ in the algebraic closure $\overline{\mathbb {K}}$ has degree exactly 4 over $\mathbb {F}_2$. This holds by the following analysis: we know that $\omega ^2 + \omega + 1 = 0$ over $\mathbb {K}$ (but $\omega \not \in \mathbb {F}_2$), so $\mathbb {F}_2[\omega ]$ has degree 2 over $\mathbb {F}_2$. Moreover, $y^2 + y + \omega$ is irreducible over $\mathbb {F}_2[\omega ]\simeq \mathbb {F}_4$. Thus, any root of $y^2 + y + \omega$ lies in $\mathbb {F}_{16}$ (realized as a degree 2 extension of $\mathbb {F}_2[\omega ]$) but not $\mathbb {F}_4$.

Having established that $\mathbb {L}$ is well-defined, we proceed to generalize Theorem 3.1.

Theorem 3.2

The field ensemble $\{\mathbb {L}_n\}$ admits a polynomial-size $\textsf{TC}^0$ circuit family for the following operations:

• Addition: $(\alpha _1, \ldots , \alpha _t)\mapsto \sum _{i=1}^t \alpha _i$ over $\mathbb {L}$.

• (Large fan-in) Multiplication: $(\alpha _1, \ldots , \alpha _t) \mapsto \prod _{i=1}^t \alpha _i$ over $\mathbb {L}$.

• Exponentiation: $(\alpha , T)\mapsto \alpha ^T$ over $\mathbb {L}$. The $\textsf{TC}^0$ circuit size is $\textsf{poly}(n, \log T)$.

Theorem 3.2 follows by a very similar approach as the proof of Theorem 3.1, making use of some additional properties of $\mathbb {L}$.

Proof

Note that $\alpha \in \mathbb {L}$ is given as an explicit bivariate polynomial $\alpha _0(x) + \alpha _1(x) y$ for $\alpha _0(x), \alpha _1(x) \in \mathbb {K}$. An $\textsf{AC}^0[\oplus ]\subseteq \textsf{TC}^0$ circuit family for addition then follows immediately by component-wise addition. Additionally, note that since

$$\begin{aligned}&\Big (\alpha _0(x) + \alpha _1(x) y\Big ) \Big (\beta _0(x) + \beta _0(x) y\Big ) \\&= \alpha _0(x) \beta _0(x) + \Big (\alpha _1(x) \beta _0(x) + \alpha _0(x) \beta _1(x)\Big )y + \alpha _1(x) \beta _1(x) y^2 \\&= \alpha _0(x) \beta _0(x) + \Big (\alpha _1(x) \beta _0(x) + \alpha _0(x) \beta _1(x)\Big )y + \alpha _1(x) \beta _1(x) (y + \omega ) \\&= \Big ( \alpha _0(x) \beta _0(x) + \alpha _1(x) \beta _1(x) \omega \Big ) + \Big ( \alpha _1(x) \beta _0(x) + \alpha _0(x) \beta _1(x) + \alpha _1(x) \beta _1(x) \Big ) y, \end{aligned}$$

an $\textsf{AC}^0[\oplus ] \subseteq \textsf{TC}^0$ circuit for pairwise multiplication over $\mathbb {L}$ follows from the analogous circuits over $\mathbb {K}$.

Next, we consider large fan-in multiplication. Suppose we are given t field elements $\alpha ^{(1)}, \ldots , \alpha ^{(t)} \in \mathbb {L}_n$ and we want to compute $\prod \alpha ^{(i)} \in \mathbb {L}_n$. To do this, we view each $\alpha ^{(i)}$ as a bivariate polynomial over $\mathbb Z$, and compute (in $\textsf{TC}^0$) the bivariate polynomial representation of $\prod \alpha ^{(i)}$. [HAB02] argues that the analogous product for univariate polynomials can be done in (uniform) $\textsf{TC}^0$, but we can see the same holds for our bivariate polynomials via the following reduction:

• Given a bivariate polynomial $\alpha ^{(i)}(x, y)$, define the polynomial $\beta ^{(i)}(z) = \alpha ^{(i)}(z, z^{n\cdot t})$; the coefficients of $\beta ^{(i)}$ can be computed with a $\textsf{TC}^0$ circuit.

• Compute the polynomial $\prod \beta ^{(i)} \in \mathbb Z[z]$ by invoking [HAB02].

• Map the coefficients of $\prod \beta ^{(i)}$ to the coefficients of $\prod \alpha ^{(i)}(x,y)$ via the correspondence $z^k \mapsto x^{k \pmod {nt}} \cdot y^{\left\lfloor k/nt\right\rfloor }$; this map can also be computed in $\textsf{TC}^0$.

Finally, we must reduce this bivariate polynomial $\prod \alpha ^{(i)}(x,y)$ modulo $(x^{2\cdot 3^\ell } + x^{3^\ell } + 1, y^2 + y + x^{3^\ell })$; this can be done via the following process:

• Reduce each y exponent modulo 15 (since $y^{15} \equiv 1$, as $y\in \mathbb {L}$ is in a degree 4 extension of $\mathbb {F}_2$),

• Reduce each (constant) power of y modulo $(y^2 + y + x^{3^\ell }, x^{2\cdot 3^\ell } + x^{3^\ell } + 1)$,

• Group terms by power of y (either $y^0$ or $y^1$), and

• Reduce each $y^j$ coefficient modulo $x^{2\cdot 3^\ell } + x^{3^\ell } + 1$.

This completes the proof that large fan-in multiplication over $\mathbb {L}$ is in $\textsf{TC}^0$.

Finally, we consider exponentiation $(\alpha , T)\mapsto \alpha ^T \in \mathbb {L}$. T is given as input in binary; by invoking a large fan-in multiplication solver, we can reduce to the case where $T = 2^i$ is a power of 2. Now, note that in $\mathbb {L}$, we have

$$ \alpha (x,y)^{2^i} = \alpha \Big (x^{2^i}, y^{2^i}\Big ) = \alpha \Big (x^{2^i}, y + \sum _{j=0}^{i-1} \omega ^{2^j}\Big ), $$

where the first equality follows from the fact that our field has characteristic 2, and the second equality uses the defining equation $y^2 + y + \omega = 0$.  The field element $g(\omega ) = \sum _{j=0}^{i-1} \omega ^{2^j}\in \mathbb {K}$ can be computed in $\textsf{AC}^0[\oplus ]$ (e.g. invoking [HV06]), and $\alpha (\cdot , \cdot )$ is linear in its second argument, so we can compute $\alpha ^{2^i} \in \mathbb {L}$ by computing each expression $x^{2^i \cdot k}$ for $k\le n$, which by [HV06] can be done in $\textsf{AC}^0[\oplus ]$, and invoking pairwise field element multiplication and large fan-in addition circuits.

3.2 Finding Roots of $\mathbb {K}$-quadratics in $\mathbb {L}$

In this section, we give a $\textsf{TC}^0$ circuit family for solving the following computational problem:

Definition 3.3

($(\mathbb {K}, \mathbb {L})$ Quadratic Root Finding). Given a quadratic polynomial $az^2 + bz + c \in \mathbb {K}[z]$, find all zeroes of this polynomial in $\mathbb {L}$.

Theorem 3.3

$(\mathbb {K}, \mathbb {L})$ quadratic root finding admits a $\textsf{TC}^0$ circuit family.

Proof

We break into cases.

• If $a=0$, then this amounts to computing $b^{-1} \in \mathbb {K}$, which can be done because $b^{-1} = b^{2^n - 2}$ and exponentiation is in $\textsf{TC}^0$ (Theorem 3.1).

• If $a\ne 0$ and $b=0$, then this amounts to inverting a and computing a square root in $\mathbb {K}$, which can be done because $\sqrt{\alpha } = \alpha ^{2^{n-1}}$ for $\alpha \in \mathbb {K}$.

• If $a \ne 0$ and $b\ne 0$, then (by invoking standard field operations) this reduces to the case where $a=1$ and $b=1$, as

  $$ az^2 + bz + c = 0 \iff (a/b\cdot z)^2 + (a/b\cdot z) + a/b^2 \cdot c = 0. $$

Thus, for the rest of the proof, we assume that $a=1$ and $b=1$. Moreover, it suffices to find a single solution $z^*$ in $\mathbb {L}$, as the other solution will be $z^* + 1$ (since $\mathbb {L}$ has characteristic 2).

Given $z^2 + z + c = 0$, since $n = 2\cdot 3^\ell$ is 2 mod 4, solving the equation turns out (via standard theory of finite fields, see e.g. [BSS99] Chapter II) to be related to the $\mathbb {F}_4$-trace map

$$\textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha ) = \sum _{i=0}^{n/2-1} \alpha ^{2^{2i}} $$

as follows. First, we note that for any $\alpha \in \mathbb {K}$, $\textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha ) \in \mathbb {F}_2[\omega ]$, as $\textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha )$ is invariant under the map $z \mapsto z^{2^i}$ for all even i. Additionally, the formula above is computable via a $\textsf{TC}^0$ (in fact, $\textsf{AC}^0[\oplus ]$) circuit family.

Next, we give a $\textsf{TC}^0$ (in fact, $\textsf{AC}^0[\oplus ]$) circuit that on input $\alpha \in \mathbb {K}$, outputs $\beta \in \mathbb {K}$ such that $\beta ^2 + \beta = \alpha + \textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha )$. The circuit simply computes the expression

$$ \beta = \sum _{\begin{array}{c} 0\le i\le n/2-1 \\ i \text { odd } \end{array}} \alpha ^{2^{2i}} + \alpha ^{2^{2i+1}}. $$

Observe that

$$ \beta ^2 + \beta = \sum _{\begin{array}{c} 0\le i\le n/2-1 \\ i \text { odd } \end{array}} \alpha ^{2^{2i}} + \alpha ^{2^{2i+2}} = \alpha + \textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha ), $$

where the last equation uses the fact that $n/2 - 1$ is even.

Finally, in order to solve the equation $z^2 + z + \alpha = 0$, given that we can compute $\beta$ above, it suffices by additivity to be able to solve the equation $z^2 + z + c = 0$ for $c = \textrm{Tr}_{\mathbb {K}/\mathbb {F}_4}(\alpha ) \in \mathbb {F}_2[\omega ]$. But this can be done by lookup table: for $c=0$ a solution is 0, for $c=1$ a solution is $\omega$, for $c=\omega$ a solution is y, and for $c = 1 + \omega$ a solution is $\omega + y$. This completes the proof of Theorem 3.3.

3.3 Finding Roots of Cubics in $\mathbb {K}$

In this section, we give a $\textsf{TC}^0$ circuit family for solving the following computational problem:

Definition 3.4

($(\mathbb {K}, \mathbb {K})$ Cubic Root Finding). Given a cubic polynomial $az^3 + bz^2 + cz + d \in \mathbb {K}[z]$, find all zeroes of this polynomial that lie in $\mathbb {K}$.

Theorem 3.4

$(\mathbb {K}, \mathbb {K})$-cubic root finding admits a $\textsf{TC}^0$ circuit family.

Proof

If $a=0$, then by Theorem 3.3, we know that $(\mathbb {K}, \mathbb {L})$-quadratic root finding can be solved in $\textsf{TC}^0$, and it is easy to check membership in $\mathbb {K}$ (on an input $\alpha \in \mathbb {L}$), so this suffices to solve $(\mathbb {K}, \mathbb {K})$-quadratic root finding as well.

Thus, we now assume that $a=1$. Note that we only want to find all roots in $\mathbb {K}$, so we may assume without loss of generality that there is at least one root in $\mathbb {K}$ (or else the problem is vacuous). Under this promise, it follows that all three roots will lie in $\mathbb {L}$ (since the polynomial factors into linear and quadratic terms over $\mathbb {K}$). Our algorithm will find all three of these roots (and then check membership in $\mathbb {K}$).

We find these roots by invoking (a special case of) a standard characteristic 2 variant of the cubic formula (following e.g. [Lag70]). Namely, letting $\alpha _0, \alpha _1, \alpha _2$ denote the three roots in $\mathbb {L}$, we will find $\alpha _0, \alpha _1, \alpha _2$ by first solving a related quadratic equation with coefficients in $\mathbb {K}$, then taking cube roots (in $\mathbb {L}$), and then solving a linear system over $\mathbb {L}$.

By Vieta’s identities, we know that $\hat{\alpha }_0 := \alpha _0 + \alpha _1 + \alpha _2 = b$. Letting $\omega = x^{3^\ell } \in \mathbb {K}$ so that $\omega ^3 = 1$, we will eventually also compute the linear combinations

$$ \hat{\alpha }_1 = \alpha _0 + \omega \alpha _1 + \omega ^2 \alpha _2, $$

$$ \hat{\alpha }_2 =\alpha _0 + \omega ^2 \alpha _1 + \omega \alpha _2 $$

The map $(\alpha _0, \alpha _1, \alpha _2) \mapsto (\hat{\alpha }_0, \hat{\alpha }_1, \hat{\alpha }_2)$ is always (efficiently) invertible over $\mathbb {L}$, so it suffices to compute $\hat{\alpha }_1, \hat{\alpha }_2$. This is sometimes referred to as the “Lagrange resolvent method.”

The field elements $\hat{\alpha }_1$ and $\hat{\alpha }_2$ have been carefully chosen to satisfy useful symmetries when $\alpha _0, \alpha _1, \alpha _2$ are permuted as formal variables:

• Under the cyclic permutation $(\alpha _0, \alpha _1, \alpha _2)\mapsto (\alpha _i, \alpha _{i+1}, \alpha _{i+2})$, we have that $\hat{\alpha }_1 \mapsto \omega ^i \hat{\alpha }_1$ and $\hat{\alpha }_2 \mapsto \omega ^{2i} \hat{\alpha }_2$.

• Under the swap permutation $\alpha _i \leftrightarrow \alpha _j$, we have that $\hat{\alpha }_1 \mapsto \omega ^{i+j} \hat{\alpha }_2$ and $\hat{\alpha }_2 \mapsto \omega ^{2i+2j} \hat{\alpha }_1$.

The symmetries simplify even further if you consider $\hat{\alpha }_1^3$ and $\hat{\alpha }_2^3$ (since $\omega ^3 =1$): under cyclic permutation, these expressions are invariant, while under a swap permutation, they swap!

Thus, $\hat{\alpha }_1^3 + \hat{\alpha }_2^3$ and $\hat{\alpha }_1^3 \hat{\alpha }_2^3$ are symmetric under all permutations of $(\alpha _0, \alpha _1, \alpha _2)$.  The theory of symmetric polynomials therefore tells us that $\hat{\alpha }_1^3 + \hat{\alpha }_2^3$ and $\hat{\alpha }_1^3 \hat{\alpha }_2^3$ can be expressed in terms of the elementary symmetric polynomials in $\alpha _0, \alpha _1, \alpha _2$, which in our case evaluate to none other than b, c, and d by Vieta’s identities. Indeed, one can explicitly check that

$$ (\hat{\alpha }_1 \hat{\alpha }_2)^3 = (b^2 + c)^3 $$

and

$$ \hat{\alpha }_1^3 + \hat{\alpha }_2^3 = bc + d, $$

and thus $(\hat{\alpha }_1^3, \hat{\alpha }_2^3)$ are solutions to the quadratic equation

$$ z^2 + (bc + d) z + (b^2 + c)^3 = 0. $$

By Theorem 3.3, we can hence compute $\hat{\alpha }_1^3, \hat{\alpha }_2^3\in \mathbb {L}$ with a $\textsf{TC}^0$ circuit. Finally, since $\hat{\alpha }_1, \hat{\alpha }_2 \in \mathbb {L}$, we can find three candidate values for each of $\hat{\alpha }_1, \hat{\alpha }_2$, by computing cube roots over $\mathbb {L}$; this leads to nine possible root sets for our original problem, which can then be individually checked to find the correct roots.

Thus, we have reduced the problem to computing cube roots over $\mathbb {L}$. For this problem, we use a special case of the Adleman-Manders-Miller algorithm [AMM77]. Specifically, we note that $|\mathbb {L}|-1 = 2^{4\cdot 3^\ell }-1$ is congruent to $3^{\ell +1}$ modulo $3^{\ell + 2}$. Then, invoking exponentiation¹³ in $\mathbb {L}$, on any input $\alpha \in \mathbb {L}$ we can compute

$$ \beta = \alpha ^{\frac{|\mathbb {L}| - 1 - 3^{\ell + 1}}{3^{\ell + 2}}} \in \mathbb {L}. $$

Note that

$$ \beta ^{3^{\ell + 2}} = \alpha ^{3^{\ell + 1}}, $$

and thus $\beta ^3 / \alpha$ is a $3^{\ell + 1}$th root of unity, the set of which is precisely $S = \{1, x, x^2, \ldots , x^{3^{\ell +1}-1}\}$. We can then enumerate (in parallel) over this $\le n$-size set to determine (the x-exponent of) $\beta ^3/\alpha$ and thus compute a cube root of $\alpha$ provided that a cube root of $\beta ^3/\alpha$ exists (necessarily within S).

Putting everything together, we obtain the desired $\textsf{TC}^0$ circuit family for $(\mathbb {K}, \mathbb {K})$-cubic root finding.

4 PPAD-Hardness from Subexponential DDH

In this section, we prove Theorem 1.2, that $\textsf{PPAD}$ is hard under the sub-exponential $\textsf{DDH}$ assumption. We do this by instantiating the Fiat-Shamir heuristic for the sumcheck protocol executed on polynomials of individual degree 2 over the Healy-Viola field ensemble. We prove that Fiat-Shamir for this protocol is sound under $\textsf{DDH}$ by using a lossy CI hash family for $TC^0$ (Theorem 2.3) and appealing to $TC^0$ algorithms for quadratic root finding (Theorem 3.3).

Definition 4.1

($\oplus$3SAT). A 3CNF formula $\phi$ is in the language $\oplus$3SAT if the number of satisfying assignments to $\phi$ is odd.

Fact 1

([VV85]). If $\textsf{NP}$ is hard (on average) for PPT algorithms, then $\oplus$3SAT is hard (on average) for PPT algorithms.

In particular, if one-way functions exist, then $\oplus$3SAT is hard on average.

Definition 4.2

(Sumcheck Language). An instance of the sumcheck language consists of an arithmetic circuit f over some field $\mathbb {F}$, along with a target value y. The pair (f, y) is a YES-instance if

$$ \sum _{x\in \{0,1\}^n} f(x_1, \ldots , x_n) = y. $$

In this work, we observe that if $\oplus$3SAT is hard on average, then there is a hard sumcheck problem over $\mathbb {F}_2$ where the individual degree of f is at most two.

Lemma 4.1

If $\oplus$3SAT is hard-on-average, then sumcheck over $\mathbb {F}_2$ is hard-on-average with respect to a distribution of (f, y) such that the individual degree of f is at most two.

Proof

We describe a one-to-one reduction mapping $\oplus$3SAT formulas $\phi$ to sumcheck polynomials f, so that deciding whether $\phi \in \oplus$3SAT maps to checking whether (f, 1) is a valid sumcheck instance.

Suppose that $\phi$ is an n-variable, m-clause 3CNF:

$$ \phi (x_1, \ldots , x_n) = \bigwedge _{j=1}^m \phi _j(x_{j_1}, x_{j_2}, x_{j_3}) $$

where each $\phi _j$ is an OR of three variables $(x_{j_1}, x_{j_2}, x_{j_3})$ with some negation pattern (contained in the description of $\phi _j$). Then, consider the following formula in 3m variables:

$$\begin{aligned}&f(z=(z_{j,k})_{j\in [m], k\in \{1, 2, 3\}}) \\&= \prod _{j=1}^m \phi _j(z_{j,1}, z_{j,2}, z_{j,3}) \prod _{i=1}^n \left( \prod _{j, k: j_k = i} z_{j,k} + \prod _{j,k: j_k = i} (1-z_{j,k})\right) , \end{aligned}$$

where $\phi _j$ can be interpreted as a multilinear polynomial in three variables over $\mathbb {F}_2$. We observe that:

• f has individual degree at most 2. This is because the two products are individually multilinear.

• For $z \in \{0,1\}^{3m}$, $f(z) = 1$ if and only if for some $x\in \{0,1\}^n$, $\phi (x) = 1$ and $z_{j,k} = x_{j_k}$ for all (j, k). Otherwise, $f(z) = 0$.

Thus, we see that

$$ \sum _{x \in \{0,1\}^n} \phi (x_1, \ldots , x_n) = \sum _{y\in \{0,1\}^{3m}} f(y) \pmod 2. $$

This completes the reduction.

To conclude that PPAD is hard-on-average, we combine Lemma 4.1 with the unambiguous non-interactive argument system for sumcheck from [JKKZ21]. [JKKZ21] implies the following result:

Theorem 4.1

([JKKZ21], translated). Let K be a field (ensemble) of size $2^\lambda$. Then, there exists an updatable, unambiguous non-interactive argument system for $\textsf{Sumcheck}_K$ for individual degree d polynomials assuming the existence of a hash family $\mathcal H$ that is lossy CI (Definition 2.5) for a class of functions that enumerate over all roots of a given univariate degree d polynomial over K.

By Theorem 2.2, Theorem 2.3, and Theorem 2.1, we know that there exists a lossy CI hash family for $TC^0$ circuits under sub-exponential DDH. Moreover, letting $\{K_\lambda \}$ denote the field ensemble defined in Definition 3.1, we showed that roots of degree 2 polynomials over K can be enumerated in $TC^0$. Thus, by Theorem 4.1, we conclude that the claimed argument system exists under sub-exponential DDH.

Finally, it is known that an argument system satisfying the conditions of Theorem 4.1 (along with the hardness of the underlying sumcheck problem) implies the hardness of PPAD [CHK+19a], so this completes the proof of Theorem 1.2.

5 Delegation for Bounded Depth Computations from Subexponential DDH

In this section, we apply and extend our techniques to prove our main theorem on $\textsf{SNARG}$s for bounded-depth computation.

Theorem 5.1

Assuming the sub-exponential hardness of the DDH assumption, there exists a $\textsf{SNARG}$ for any logspace uniform depth d and size s computation, where the size of the $\textsf{SNARG}$ and the $\textsf{crs}$ is bounded by $d\cdot \textsf{poly}(\lambda ,\log s)$ and the verification time is $(n+d)\cdot \textsf{poly}(\lambda ,\log s)$, where n is the length of the input.

Our $\textsf{SNARG}$ is obtained by applying the Fiat-Shamir heuristic to a variant of the GKR protocol, considered in [KPY18, JKKZ21] (building on a simplification of the original GKR protocol due to [Gol18]).

5.1 Variable-Extended Formulations for Boolean Functions

In this section we show how to reduce the degree of any boolean formula down to individual degree at most 2, by adding auxiliary variables. Loosely speaking, this is done by adding a variable corresponding to each wire in the original formula, and computing the original formula by making a series of consistency checks.

Definition 5.1

Let $f(x_1, \ldots , x_m)$ be a boolean function on m variables. We say that $g(x_1,\ldots , x_m, z_1, \ldots , z_{t})$ is a variable-extended formulation of f if for every $x\in \{0,1\}^m$, there exists a unique $z(x) \in \{0,1\}^{t}$ such that $g(x, z(x)) = f(x)$, and $g(x, z) = 0$ for all $z\ne z(x)$.

Lemma 5.1

Let $f(x_1, \ldots , x_m)$ be a NAND-boolean formula of size s. Then, there exists a variable-extended formulation g of f such that (1) $t = s$, and (2) g can be computed by a $\mathbb {F}_2$-arithmetic circuit of size O(s) that defines a (formal) polynomial of individual degree at most 2.

Also, the above arithmetic circuit can be constructed in time $\textsf{poly}(s)$ given the description of f.

Proof

We use a similar strategy as in Lemma 4.1. That is, we introduce s new variables $z_1, \ldots , z_s$, one for each wire of the formula computing f. We then define

$$ g(x, z) = z_s \prod _{i=1}^s g_i(z) \prod _{j=1}^m g'_j(x, z), $$

where for every gate (i, j, k) we have $g_i(z) = z_i + z_j z_k$ and for every input index j we have $g'_j(x, z) = x_j \prod _{i \in S_j} z_i + (1-x_j)\prod _{i\in S_j} (1-z_i)$, where $S_j$ denotes the set of leaf indices corresponding to $x_j$. Note that g(x, z) has individual degree 2, since (1) $z_s$ appears only twice, (2) each intermediate (non-output, non-leaf) variable only appears twice because they have fan-in 1 and fan-out 1, and (3) the variables $\{x_j, z_i\}_{j \in [m], i \in S_j}$ have degree at most 2 (they occur at most once in the first product, while the second product is multilinear).

5.2 A GKR Protocol with Degree 3 Sumcheck Polynomials

In this section, we construct a special variant of the GKR interactive proof system for logspace-uniform depth-d computation. Our starting point is the GKR protocol variant described in [KPY18, JKKZ21], which makes use of observations from [Mei13, Gol18] to simplify the protocol. In [JKKZ21], it was shown that the Fiat-Shamir heuristic can be instantiated for this protocol using a hash function that is “lossy correlation-intractable” for circuits that (modulo basic field operations) compute roots of univarite polynomials of polylogarithmic degree. They then show how to construct such a lossy correlation-intractable hash functions from the sub-exponential LWE assumption.

By using an appropriate variable-extended formulation (Lemma 5.1), we will modify the protocol so that every sumcheck sub-protocol uses a polynomial of individual degree at most 3. Finally, working over the field ensemble from Definition 3.1 and using the correlation-intractable hash family of [JJ21] (and lossy trapdoor functions from DDH [PW08]), we will deduce Theorem 5.1.

The Protocol. Let $C = \{C_n\}_n$ denote a family of logspace-uniform circuits of depth d and width w. We assume without loss of generality that C has fan-in 2 and consists of addition (mod 2) and multiplication (mod 2) gates. The key objects of interest are the gate-indicator functions $\chi _{\textrm{add}}^{(i)}, \chi _{\textrm{mult}}^{(i)}$ for each layer (i) of the circuit. $\chi _{\textrm{add}}^{(i)}$ and $\chi _{\textrm{mult}}^{(i)}$ take as input three strings $(a, b, c)\in \{0,1\}^{\log w}$ and output whether (a, b, c) is an addition (respectively, multiplication) gate in C.

The protocol is typically defined with respect to particular low-degree extensions $\widetilde{\chi }_{\textrm{add}}^{(i)}, \widetilde{\chi }_{\textrm{mult}}^{(i)}$ of $\chi _{\textrm{add}}, \chi _{\textrm{mult}}$. For our variant, we make use of the following fact shown implicitly in [Gol18]:

Fact 2

Let $C'$ be any family of logspace-uniform circuits of depth d and size s. Then, there exists a family C of logspace-uniform circuits of depth $d \cdot \textsf{poly}\log (s)$ and size $\textsf{poly}(s)$ such that:

• C computes the same function as $C'$, and

• For all i, $\chi _{\textrm{add}}^{(i)}$, $\chi _{\textrm{mult}}^{(i)}$ (for C) are computable by boolean formulas of size $O(\log w)$ (i.e., the size is linear in the $\chi _{\textrm{add}}, \chi _{\textrm{mult}}$ input length). These formulas can be constructed (by a uniform Turing machine) in time $\textsf{poly}(\log s)$.

[Gol18] only explicitly claims that the formulas have size $\textsf{poly}\log s$, but the construction in [Gol18] Sect. 3.4.2 actually (specializing to $H = \{0,1\}$) implies Fact 2.

Thus, we assume without loss of generality that C satisfies the conclusion of Fact 2. Invoking Lemma 5.1, we conclude that $\chi _{\textrm{add}}^{(i)}, \chi _{\textrm{mult}}^{(i)}$ have variable-extended formulations $\psi _{\textrm{add}}^{(i)}, \psi _{\textrm{mult}}^{(i)}: \{0,1\}^{3\log w + O(\log s)} \rightarrow \{0,1\}$ that are computable by $\mathbb {F}_2$-arithmetic circuits of size $O(\log s)$ that define polynomials of individual degree at most 2. We let $\widetilde{\psi }_{\textrm{add}}^{(i)}, \widetilde{\psi }_{\textrm{mult}}^{(i)}$ denote the corresponding individual degree 2 polynomials.

We are finally ready to describe the protocol, which will use arithmetic over an extension K of $\mathbb {F}_2$. Our instantiation will use the field ensemble from Definition 3.1.

• The prover and verifier, given the logspace-uniform Turing machine that constructs C, both compute arithmetic circuit descriptions of each $\widetilde{\psi }_{\textrm{add}}^{(i)},\widetilde{\psi }_{\textrm{mult}}^{(i)}$.

• The prover, given the input x and circuit C, computes the following quantities:

  • For every layer i of the circuit, compute the string $L_i = L_i(C, x) \in \{0,1\}^w$ consisting of all wire values in the evaluation C(x) in the ith layer of C.

  • For each such i, define the function $\ell _i: \{0,1\}^{\log w}\rightarrow \{0,1\}$ such that $\ell _i(a) = (L_i)_a$, where a is interpreted as an integer between 0 and $w-1$. Implicitly, this defines a multi-linear extension $\hat{\ell }_i: K^{\log w} \rightarrow K$ of $\ell _i$.

• The prover and verifier recursively agree on a pair of claims of the form “$\hat{\ell }_i(u_1) = v_1$,” “$\hat{\ell }_i(u_2) = v_2$” for $u_1, u_2 \in K^{\log w}$ and $v_1, v_2 \in K$. They do so as follows:

  • The base case is $i = d$, the top (output) layer of C; the claims are (both) that $\hat{\ell }_d(0^{\log w}) = y$ (where allegedly $C(x) = y$).

  • Inductively, suppose that we have two claims “$\hat{\ell }_i(u_1) = v_1$,” “$\hat{\ell }_i(u_2) = v_2$” about layer i. The recursion uses the fact that

  $$\hat{\ell }_i(u) = \sum _{a \in \{0,1\}^{\log w}} \widehat{EQ}(u, a) \ell _i(a), $$

  which can be written as

  $$\sum _{a, b, c} \widehat{EQ}(u, a) \Big (\chi _{\textrm{add}}^{(i)}(a, b, c)\cdot (\ell _{i-1}(b) + \ell _{i-1}(c)) + \chi _{\textrm{mult}}^{(i)}(a, b, c) \ell _{i-1}(b) \cdot \ell _{i-1}(c)\Big ), $$

  which is equal to

  $$\sum _{\begin{array}{c} a, b, c\\ z\in \{0,1\}^{t} \end{array}} \widehat{EQ}(u, a) \Big (\psi _{\textrm{add}}^{(i)}(a, b, c, z)\cdot (\ell _{i-1}(b) + \ell _{i-1}(c)) + \psi _{\textrm{mult}}^{(i)}(a, b, c, z) \ell _{i-1}(b) \cdot \ell _{i-1}(c)\Big ), $$

  where $\widehat{EQ}(u, a) := \prod _j (1+ u_j + a_j)$.

  • The prover and verifier then run two simultaneous sumcheck protocols using the polynomials $g_{u_1}$, $g_{u_2}$, where

    $$g_{u}(a, b, c, z) = \widehat{EQ}(u, a) \cdot $$
    $$ \Big (\widetilde{\psi }_{\textrm{add}}^{(i)}(a, b, c, z)\cdot (\hat{\ell }_{i-1}(b) + \hat{\ell }_{i-1}(c)) + \widetilde{\psi }_{\textrm{mult}}^{(i)}(a, b, c, z) \hat{\ell }_{i-1}(b) \cdot \hat{\ell }_{i-1}(c)\Big ) $$

    and the claimed outputs $v_1, v_2$. Importantly, the same verifier randomness is used for these two sumcheck protocols.

  • At the end of the interactive phase of this protocol, the verifier has a tuple of field elements $\boldsymbol{\beta }\in K^{3\log w + O(\log s)}$ and outputs $\gamma _1, \gamma _2$ such that (allegedly) $g_{u_1}(\boldsymbol{\beta }) = \gamma _1$ and $g_{u_2}(\boldsymbol{\beta }) = \gamma _2$. Let $u_1', u_2'$ denote the part of $\beta$ corresponding to b and c.

  • Finally, the prover sends $v_1' = \hat{\ell }_{i_1}(u_1'), v_2' = \hat{\ell }_{i-1}(u_2')$ to the verifier. Since $\widehat{EQ}, \widetilde{\psi }_{\textrm{add}}^{(i)},\widetilde{\psi }_{\textrm{mult}}^{(i)}$ are all computable in time $\textsf{poly}(\log s)$, the verifier can check that $v_1'$ and $v_2'$ are consistent with the claims output by the sumcheck protocol. This completes the recursive step, which has produced two new claims $(u_1', v_1'), (u_2', v_2')$.

• After this recursive process, the verifier has obtained two final claims “$\hat{\ell }_0(u_1) = v_1$,” “$\hat{\ell }_0(u_2) = v_2$” about the multilinear extension $\hat{\ell }_0.$ Since $\hat{\ell }_0$ is nothing more than the multilinear extension of the input x (thought of as a function mapping $\{0,1\}^{\log n}\rightarrow \{0,1\})$, the verifier can check these two claims (given x) using O(n) field operations.

Crucially, $\widetilde{\psi }_{\textrm{add}}$ and $\widetilde{\psi }_{\textrm{mult}}$ have individual degree 2, which implies that every polynomial $g_u$ has individual degree at most 3. This is because $\widehat{EQ}(u, a) (\hat{\ell }_{i-1}(b) + \hat{\ell }_{i-1}(c))$ and $\widehat{EQ}(u, a) (\hat{\ell }_{i-1}(b)\hat{\ell }_{i-1}(c))$ are both multilinear polynomials.

This completes our description of our variant of the [GKR08] protocol. By combining Theorems 2.1, 2.2 and 2.4, the fact that this [GKR08] variant runs (pairs of) degree 3 sumchecks, and Theorem 3.4, we conclude Theorem 5.1.