Impossibilities in Succinct Arguments:

Black-box Extraction and More

Matteo Campanelli¹, Chaya Ganesh², Hamidreza Khoshakhlagh³, and Janno Siim⁴

¹ Protocol Labs, matteo@protocol.ai

² Indian Institute of Science, India, chaya@iisc.ac.in

³ Aarhus University, Denmark, hamidreza@cs.au.dk

⁴ Simula UiB, Bergen, Norway, janno@simula.no

Abstract. The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages we must rely on non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to extractability and to the preprocessing model. 1.We first ask the question “are there further barriers to SNARGs that are knowledge-sound (SNARKs) and with a black-box extractor?”. We show it is impossible to have such SNARKs in the standard model. This separates SNARKs in the random oracle model (which can have black-box extraction) and those in the standard model. 2.We find positive results about knowledge soundness in the non-adaptive setting. Under the existence of SNARGs (without extractability) and from standard assumptions, it is possible to build SNARKs with black-box extractability for a non-trivial subset of NP. 3.On the other hand, we show that (under some mild assumptions) all of NP cannot have SNARKs with black-box extractability even in the non-adaptive setting. 4.The Gentry-Wichs result does not account for the preprocessing model, under which fall several efficient constructions. We show that it is impossible to construct SNARGs that rely on falsifiable assumptions in a black-box way, even in the preprocessing model. Along the way, we identify a class of non-trivial languages, which we dub “trapdoor languages”, that bypass some of these impossibility results.

1 Introduction

• Proof systems have been studied extensively both in cryptography and in theory of computation [BGG 90, For87, GMW86], and are a fundamental building block in various cryptographic constructions today, includ-
• • • ing delegating computation [BCG 13, BCTV14, CFH 15] and privacy-preserving cryptocurrencies [BCG 14] to name a few. In a succinct proof, it is additionally required that the communication be sublinear (ideally polylogarithmic) in the size of the non-deterministic witness used to verify the relation (proof succinctness). This requirement is often extended to verification complexity (verification succinctness).

Statistically-sound proofs are unlikely to allow for significant improvements in proof size [GH98, GVW02, Wee05], that is, for NP, statistical soundness requires the prover to communicate, roughly, as much information as the size of the witness. If we restrict ourselves to argument systems [BCC88] where soundness is computational, then, proofs can be shorter than the length of the witness.

Succinct arguments. Succinct arguments were first studied by Kilian [Kil92], who gave an interactive construction based on probabilistically checkable proofs (PCP) and collision-resistant hash function. Kilian’s construction was turned into a non-interactive argument in the random oracle model using the Fiat-Shamir heuristic [FS87] by Micali [Mic94]. In the standard model (i.e., without idealized primitives), non-interactivity is achieved by generating a Common Reference String (CRS) during a setup phase. A Succinct Non-interactive ARGument (SNARG) for a language L is a triple of algorithms (Setup*,* P*,V) where Setup is a generator algorithm that takes a security parameter and samples a common reference string crs and a verification string td; the prover P(crs,* x*,w) outputs a proof π for x ∈L; the verifier V(td,* x*,π*) output 0*/*1 indicating the validity of the proof. The notion of adaptive soundness requires soundness to hold even if a malicious prover chooses x depending on crs.

$$ \mathsf{V}(\mathsf{t d},\times,\pi) $$

$$ {\mathsf{X}}\in{\mathcal{L}}; $$

$$ \mathsf{P}(\mathsf{c r s},\mathsf{x},\mathsf{w}) $$

In this work we are concerned with the theoretical limitations for building efficient succinct non-interactive arguments in the standard model⁵. One of the best-known impossibility results on SNARGs is that of Gentry and Wichs [GW11] (we will occasionally refer to it as “GW”), which shows that in the standard model, adaptively-sound⁶ SNARGs for (hard enough) NP languages cannot be proven secure via a black-box reduction to a falsifiable assumption [Nao03]. A falsifiable assumption is an assumption we can empirically falsify⁷.

$$ ^{\ !}\mathrm{G W}^{\prime\prime} $$

A folklore way to interpret GW has been “we cannot escape non-falsifiable assumptions to build SNARGs for NP”. While this is essentially true, there are several caveats to this interpretation (which we discuss later in this work in Section 6 and some of which have already been noticed in prior work). We formally explore the boundaries of this simplifying interpretations, especially motivated by the focus on (compos- + able) extractability [BS21, KZM 15] and the popular model of “preprocessing SNARGs” in recent works, e.g. [Gro16]. We strive to provide a modern view of these topics, for example by adopting the language of + indexed relations from [CHM 20] (we later argue why this is a meaningful switch).

$$ \mathbf{N P}^{\ \ } $$

$$ \mathrm{S N A R G s} $$

(Black-box) knowledge soundness. A strengthening of the soundness property is knowledge soundness. It requires that, whenever the verifier is convinced by an efficient prover, not only can we conclude that x ∈L, but also that a witness w can be extracted efficiently from the prover such that (x*,*w) ∈R_L. This useful property is satisfied by many proof system constructions, and sometimes, necessary, in a lot of applications of succinct arguments. A Succinct Non-interactive ARgument of Knowledge (SNARK) is a SNARG with the knowledge soundness property.

$$ x\in\mathcal{L} $$

$$ \ \ (\mathsf{x},\mathsf{w}),\in,\mathcal{R}_{\mathcal{L}} $$

Constructions of SNARKs for NP in the standard model all rely on a type of non-falsifiable assumptions that are knowledge-type assumptions related to some algebraic problem (e.g., guaranteeing the existence of an extractor algorithm that can output a discrete log “from” a specific adversary). This example also hints to why these assumptions are non-falsifiable—they are non-black-box, that is they require knowledge of the internal state of the adversary and an extractor aware of the concrete adversarial algorithm. This is in contrast to the milder black-box extraction, namely the ability to extract a witness from an adversarial prover only using its input/output interface.

Understanding whether we can build SNARKs with black-box extraction in the standard model is still an elusive problem. In addition to being a theoretical curiosity, if answered in the positive, it would also allow us to construct more robust cryptographic protocols using SNARKs. Black-box extraction is required in strong notions of composition security, e.g. in universal composability (or UC-security [Can01]) where the “idealworld” simulator must extract a witness without knowledge of the environment’s algorithm. (See [KKK21] for an attempt to combine composability and knowledge-type assumptions.) If answered in the negative, it would confirm the seeming incompatibility of SNARKs in the standard model and UC. In this work, we then ask the question:

Is non-black-box extraction inherent to SNARKs?

Addressing this question is, we believe, even more pressing because prior works [BKSV21, BS21, CKLM13, ⁺ KZM 15] have used as motivation the fact that succinctness must be sacrificed for black-box extraction,

⁵ There exist efficient SNARKs (SNARGs of knowledge) in idealized models like ROM (random oracle model), GGM (generic group model), or AGM (algebraic group model), including constructions like Groth16 [Gro1⁶], + Bulletproofs [BBB 18]. We later discuss implications of our results for different models.

$$ \left\lbrack\mathrm{B}\bar{\mathrm{B}}\bar{\mathrm{B}}^{+}\bar{18}\right\rbrack $$

⁶ An adaptively-secure scheme is one where the adversary can “decide” on the false statement (the one for which it will present a convincing proof) after seeing the reference string crs. A non-adaptively secure scheme will offer guarantees only against adversaries presenting this input to the challenger before crs is sampled. This distinction can be extended to knowledge-soundness.

⁷ For example, DLOG is a falsifiable assumption since the challenger can efficiently test if the adversary has found the correct discrete logarithm.

implying that the question had been settled (see also section 1.2). However, to the best of our knowledge, there was no formal treatment for this question prior to our work.

Our First Contribution: We formally confirm the folklore belief that black-box extraction is impossible for adaptive knowledge soundness in the standard model if one requires proof-succinctness. As a consequence, this result separates the standard model and other idealized models in terms of what is possible for blackbox extraction (for example, in the ROM and through the Fiat-Shamir transform, there exist black-box + extractable proof-succinct non-interactive arguments [BBB 18]).

Our Second Contribution: We explore whether the impossibility extends to the non-adaptive case. We find out that non-adaptive black-box extractability is possible for a non-trivial subset of NP—which encompasses distributionally hard problems such as knowledge of a discrete logarithm—through standard assumptions (FHE and CRHF) under the existence of SNARGs for a slightly augmented subset of languages. In particular, we show that a SNARG can be lifted to a SNARK with the features above for the class of languages FewP (roughly, NP statements with at most a polynomial number of valid witnesses). If the starting SNARG is based on falsifiable assumptions and in the standard model then so is the resulting SNARK. There exist currently known SNARGs that plausibly satisfy this requirement, specifically the NIZK 8 construction based on iO in [SW14]. The latter is actually a proof-succinct NIZK since the proof consists only of the output of a PRF. There is recent accumulation of evidence that iO may be based on falsifiable assumptions [GJLS21, JLS21, WW21a].

Our Third Contribution: A natural question is whether the previous construction for FewP can be extended to NP. We answer this in the negative under some mild assumptions. In particular, we show that if the relation is y = f (w) where f is a L-continuous leakage-resilient one-way function (CLR-OWF, a oneway function where L bits may leak multiple times given that preimage w is updated), then the proof size must be more than L bits. There exist a CLR-OWF under the discrete logarithm assumption [ADVW13] where L is linear in the size of w. Thus, the proof cannot be succinct.

$$ y=f(w) $$

Preprocessing and the Gentry-Wichs impossibility result. In many applications we want to look beyond proof-succinctness and keep the verifier as efficient as possible. Ideally, we would like verification to run sublinearly in the size/time of the computation. It may seem counterintuitive that this is even possible: naturally, in circuit-based⁹ arguments for general computations the verifier should at least read the statement being proven. The latter includes both the description of the computation (i.e., the circuit) and its input (i.e., the deterministic input for an NP statement). There exists, however, a (commonly used) way around this problem: a preprocessing phase. In a preprocessing SNARG, one generates a common reference string, or CRS, usually depending on a specific circuit C, which is constructed once and for all and can later be used to prove/verify an unbounded number of proofs for the computation of C. This CRS is actually structured as a pair of CRS’s, the prover’s CRS and the verifier’s CRS, used by the each respective party. The verifier’s CRS is morally a digest of the circuit; the prover’s CRS is paired to it. If the verifier’s CRS is “short enough”, then the online verification stage can be fast, requiring to read only the SNARG proof and a partial input description (the deterministic input to the circuit, without its description); thus the verifier can run in time sublinear in |C| (and in the witness size).

• This preprocessing model encompasses a rich line of work constructing efficient SNARGs [BCI 13, GGPR13, Gro10, Lip12, Lip13, PHGR13]. The fact that it is a practically interesting model, as it achieves verifier-succinct SNARGs, further motivates a deeper theoretical understanding of it. A fundamental question is:

Can we construct preprocessing SNARGs based on falsifiable assumptions?

⁸ It is still an open problem how to obtain non-adaptive secure SNARGs from falsifiable assumptions without iO. The only candidate, the recent construction in [LP21], was recently shown to have a fundamentally flawed proof of security (see discussion in [WW22]).

⁹ There are other models of computation that have a succinct description, for instance, machine computations. However, in general, the description of a computation could be as large as the computation itself.

We argue this question has not been settled. First, none of the known preprocessing constructions rely on falsifiable assumptions. Also, known impossibility results do not inform us on the matter either. The Gentry-Wichs impossibility—which separates SNARGs and falsifiable assumptions—has long served as a justification to SNARGs for NP on non-falsifiable assumptions, but it fails to shed light on the preprocessing setting. The reason is that the GW results presumes a SNARG with a CRS with a specific pattern (we mean “prover’s CRS” when we just say CRS from now on): their CRS cannot grow with the size of the instance, but should instead be bounded by a polynomial in the security parameter. In principle the question is then still open, more so because all existing preprocessing constructions, do have a CRS with the opposite pattern: it is usually as long as the instance¹⁰.

Besides GW, other existing works also fail to provide an answer. For example, the work of [BCCT13] shows how to “bootstrap” a preprocessing SNARK into one without preprocessing to obtain a complexity-preserving SNARK, i.e., one without expensive preprocessing. The transformation can be applied to known SNARKs with expensive preprocessing to obtain a SNARK without the expensive preprocessing. This complexitypreserving compilation, informally, establishes that preprocessing does not give any additional power; if preprocessing SNARKs were possible from falsifiable assumptions, one could apply the bootstrapping transformation and obtain short CRS SNARKs from falsifiable assumptions. Thus, any impossibility for SNARKs holds even for SNARKs that rely on expensive preprocessing. However, this bootstrapping crucially requires the knowledge soundness property and therefore only applies to SNARKs. The question of whether allowing a preprocessing phase allows constructing SNARGs based on falsifiable assumptions still remains.

Our Fourth Contribution: We fill the gap left by the GW result and show that even preprocessing SNARGs with a loosely-bounded CRS cannot be constructed from falsifiable assumptions in the standard model.

The landscape of impossibilities for non-interactive arguments. In order for our work to be as selfcontained as possible, we complement the results above with an overarching view of impossibilities on noninteractive arguments (section 6). This discussion strives to give a complete picture of existing impossibility results, related key properties of positive results and gaps between positive and negative results. Motivated by the observation that preprocessing SNARGs do not come under the GW impossibility (nor in our extension for preprocessing), we articulate the assumptions behind the impossibilities, and identify settings that would bypass them (in the spirit of recent attempts such as [LP21]). Along the way, we formalize a class of languages that does not come under the Gentry-Wichs impossibility result. We dub them trapdoor languages (where there exists a “trapdoor” that makes the problem feasible) and exemplify several application settings that fall under the same category. Trapdoor languages can be thought as a generalization of witness-sampleable (algebraic) languages in the work of [CH20].

1.1 Technical Overview

BB extraction is impossible for any hard language (adaptive case). We show impossibility of black-box extraction for non-interactive succinct arguments following the intuition that if an argument is too “small”, it cannot contain information about a “long” witness. This makes extraction impossible since the extractor does not have any additional power, like access to the prover’s randomness (as in non-blackbox extractors for popular SNARKs) or the ability to rewind the prover (as in interactive arguments, for example, in Kilian’s protocol).

Our result gives a precise characterization between hardness of guessing the witness and the size of the proof. We show that if an efficient adversary can guess the witness at most with probability ε(λ) and the knowledge soundness error of the argument system is ε_ks(λ), then the proof size is at least *−log(ε(λ)+ε_ks(λ)) δ|w(λ)| bits. If we consider for simplicity that ε_ks(λ) = 0 and for example ε(λ⁾ = 1/*2 for some δ > 0 and the witness size |w(λ)|, then the proof size will be at least δ|w(λ)|. In appendix B, we show how to obtain a similar result based on hardness of leakage-resilient OWFs.

$$ \varepsilon(\lambda) $$

$$ \varepsilon_{k s}(\lambda) $$

$$ -\operatorname{l o g}\bigl(\varepsilon(\lambda){+}\varepsilon_{k s}(\lambda)\bigr) $$

$$ \varepsilon_{k s}(\lambda)=0 $$

$$ \varepsilon(\lambda)=1/2^{\delta|\mathsf{w}(\lambda)|} $$

$$ |w(\lambda)| $$

$$ \delta>0 $$

$$ \delta|mathsf w!{(\lambda)} $$

¹⁰ For example, in pairing-based constructions such as [GGPR13] it consists of at least one group element per wire in the circuit to be proven.

BB extraction is possible for FewP (non-adaptive case). We then ask if the impossibility holds if we weaken the knowledge soundness requirement to be non-adaptive. Indeed, the non-adaptive case escapes the GW impossibility for SNARGs as we discuss in Section 6.1, and it is natural to hope for a positive result for extraction as well. In the non-adaptive knowledge soundness definition, the adversary chooses the statement before seeing the CRS, and then outputs a proof for the chosen statement. Intuitively, an extractor for such an adversary does have additional power – the extractor can rewind the prover to the point after the statement is chosen, sample different CRS’es and obtain multiple proofs for the same statement. Thus, non-adaptivity makes the prover stateful allowing for rewinding to be useful for an extractor¹¹. We give a positive result in the non-adaptive case by showing a SNARK with black-box non-adaptive extraction (for a subset of NP). In the construction, we take advantage of our observation that the extractor can obtain more information by seeing multiple proofs corresponding to cleverly crafted CRS’es. At a high level, we ask the prover to encrypt a bit of the witness as part of the proof, in addition to proving the underlying relation. Given the secret key of the encryption scheme as the CRS trapdoor, the extractor can recover this witness bit. Now, the crafted CRS’es are such that they ask for different bits of the witness to be encrypted so that with every rewinding, the extractor learns a new bit until it can completely recover the witness.

While this works for valid statements with a unique witness, there are some subtleties that we need to address in order to show extraction for languages that have polynomially many witnesses, that is, class FewP. Here, the problem is that the adversary can choose to use a different witness each time, and there is no guarantee that the extractor can collect enough bits for any one witness. We now provide an overview of our construction. Let R be the relation for the language. We start with an existing SNARG for R and lift it to a SNARK. We use a Fully Homomorphic Encryption (FHE) scheme in order to hide the index of the bit the prover is asked to encrypt. Intuitively this is to hide the index so that the prover cannot adversarially choose a different witness for different indices. We augment the relation the SNARG proves to include a hash of the witness. Now the extractor keeps track of which witness it is extracting by using the hash to fingerprint. The extractor still needs to collect all bits of one witness. Here, we rely on the semantic security of the FHE scheme to show that the prover cannot consistently use witness w₁ for index i, and witness w₂, for index j. Since there are only polynomially many witnesses, assuming collision resistance of the hash function, the extractor succeeds in recovering all bits of some witness.

$$ \ _{W} $$

BB extraction is impossible for all NP (non-adaptive case). The previous result however cannot be extended to all NP languages. We show this by relating the existence of an extractor to breaking the leakage-resilience of the relation. A SNARK proof can be thought of as leakage on the witness. When this leakage is small, no extractor can succeed if the NP relation is leakage resilient. This impossibility as a consequence of leakage resilience is easy to see in the adaptive case. In non-adaptive extraction, an extractor can potentially rewind the adversary and obtain multiple proofs; this is akin to a leakage resilience adversary obtaining leakage multiple times. We formalize this connection using continuous leakage resilience. In L-leakage-resilient OWF (LR-OWF), one-wayness holds even if L bits of the preimage are leaked. In L- continuous LR-OWF (CLR-OWF), L bits can be leaked multiple times with the caveat that the preimage has to be updated before each leakage. Moreover, if for an OWF f we have y = f (w) and w is updated to ′ ^′ w then also y = f (w).

$$ y=f(w) $$

$$ w^{\prime} $$

$$ y=f(w^{\prime}) $$

We connect this primitive to the impossibility of non-adaptive black-box knowledge soundness of SNARKs. Suppose that we have a SNARK for the relation y = f (w) where f,y are public and w is the witness. We view the proof as a leakage on the witness given to the adversary. If the proof is at most L bits long, then with each rewinding the extractor can learn at most L bits of information about the witness. Now if the adversary also updates its witness w between queries, L-CLR of f implies that the extractor is unable to recover the witness. Thus, it follows that the SNARK proof is at least L bits long.

$$ y=f(w) $$

$$ f,y $$

2 We can instantiate this result with (1*−)|w|-CLR-OWF from [ADVW13] which is based on the discrete n logarithm assumption. The witness size |w| = nlogq* and q is the size of the discrete logarithm group. Thus, the proof size will be asymptotically linear in |w|.

$$ \big(1-\frac{2}{n}\big)|w|\mathrm{_C L R_O W F} $$

$$ |w|=n\log q $$

$$ q $$

¹¹ Contrast this with the adaptive case, where the prover is stateless and rewinding is not useful.

Extending GW to preprocessing SNARGs. The central idea in the GW proof is to show that every SNARG for an NP language has a simulatable adversary. That is, an unbounded adversarial prover that breaks soundness comes with an efficient simulator such that no efficient machine can tell whether it is interacting with the prover or the simulator. A black-box reduction is an efficient oracle-access machine which, when given access to a successful adversary, breaks some falsifiable assumption. But if the reduction given oracle access to the prover breaks the assumption, then the efficient machine with oracle access to the efficient simulator also breaks it since the efficient challenger of the falsifiable assumption cannot distinguish the prover from the simulator. Thus, assuming a simulatable adversary, the theorem follows.

Our proof extending the GW impossibility to preprocessing SNARGs follows the GW template. We observe that the GW proof needs the CRS to be short in constructing a simulatable adversary: the reduction that has oracle access to either the computationally unbounded prover or the efficient simulator can query m the oracle with 1 where m is different from the security parameter n. If m is small enough compared to the actual security parameter n, then the reduction can distinguish the adversary from the simulator. Therefore, the proof modifies the simulator to behave differently in answering queries with a sufficiently small m; this is done by hardcoding a table of responses as non-uniform advice. The table has hardcoded entries (x,π) for every m and every CRS. Therefore, the CRS size is bounded by a polynomial in the security parameter, and cannot grow with the size of the instance.

$$ 1^{m} $$

When considering security-parameter preserving reductions, the reduction queries its oracle with the same security parameter. Therefore, a hardcoded table is not needed, and we show how the proof goes through when the size of the CRS depends on the instance as in indexed relations. We note that a BB reduction from soundness of a preprocessing SNARG to a falsifiable assumption where the reduction is not restricted to making parameter-preserving queries remains open.

1.2 Related Work

Succinctness vs black-box extraction. Here we discuss works that trade succinctness for black-box + extraction. Recent works (C*∅C∅* [KZM 15] and Tiramisu [BS21]) aim at compiling a SNARK into a UCsecure scheme. However, this transformation results in NIZK arguments whose proof size and verification time is (quasi-)linear in the witness size. This degradation in succinctness is claimed to be unavoidable if one demands black-box extraction. In [BKSV21], Baghery et al. add black-box extraction to [Gro16] SNARK. Although the proof size is again asymptotically linear in the witness size, the authors’ goal is to strive for concrete efficiency. In [CKLM13], Chase et al. construct controlled malleable proofs that crucially require the stronger black-box version of extractability. Even though their starting point is a SNARG, in order to obtain black-box extraction of the controlled malleable proof, they give up succinctness and achieve controlled malleable NIZKs.

What is common in all the aforementioned works as an idea is to perform a form of verifiable encryption by encrypting the witness and then proving knowledge of the value inside the ciphertext in addition to original relation. The black-box extractor works by decrypting. This is the reason why the black-box extractor comes at the cost of succinctness: the proof includes a ciphertext and a proof of correct encryption.

Other works. The work in [KKK21] proposes an alternative composability model to the UC model, which can (at least to some extent) use non-black-box extractability and knowledge-type assumptions. In this case, one can still obtain succinct UC SNARKs (under some restrictions) without needing black-box extraction.

2 Preliminaries

PPT stands for probabilistic polynomial time. We use λ to denote the security parameter. We write x ←✩ X to denote that x is sampled from a distribution X. If X is a set, then x ←✩ X denotes uniform sampling. We write f (λ) = negl(λ) when f is negligible in λ and f (λ) = poly(λ) when f is polynomial in λ.

$$ x\gets\S X $$

$$ x\gets\S X $$

$$ f(\lambda)={\mathsf{n e g l}}(\lambda) $$

$$ f(\lambda)={\mathsf{p o l y}}(\lambda) $$

Indistinguishability. We say that two distributions X₁ and X₂ are (s(λ),ϵ(λ))-indistinguishable if for any circuit D of size s(λ), we have |Pr[D(X₁) = 1] − Pr[D(X₂) = 1]|≤ ϵ(λ).

$$ X_{1} $$

$$ X_{2} $$

$$ (s(\lambda),\epsilon(\lambda)) $$

$$ |\operatorname*{P r}[\mathcal{D}(X_{1})=1]-\operatorname*{P r}[\mathcal{D}(X_{2})=1]|\leq\epsilon(\lambda) $$

Hard-on-average problems. We define a language L∈ NP to be a hard-on-average problem if

$$ \mathcal{L}\in\mathbf{N P} $$

λ – It has an efficient instance sampler Samp_L(1) that outputs x ∈L together with a NP witness w.

$$ \mathsf{p}_{\mathcal{L}}(1^{\lambda}) $$

$$ x\in\mathcal{L} $$

λ – There is an efficient sampler SampL¯(1) that with an overwhelming probability outputs x ̸∈L.

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{\lambda}) $$

$$ \times\not\in\mathcal{L} $$

λ λ – It is computationally hard to distinguish outputs of SampL(1) and SampL¯(1).

$$ \mathsf{S a m p}_{\mathcal{L}}(1^{\lambda}) $$

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{\lambda}) $$

λ λ We say that L is (s(λ),ϵ(λ))-hard if distributions of x from SampL(1) and SampL¯(1) are (s(λ),ϵ(λ))- indistinguishable. It is sub-exponentially hard if there exits some constant δ > 0 such that previous distri- δ δ Ω(λ) Ω(λ) butions are (s(λ),ϵ(λ))-indistinguishable for s(λ) = 2 and ϵ⁽λ⁾ = 1*/2. Lastly, L is exponentially δ λ hard if the above holds and moreover |x| + |w| = O(λ) for (x,*w) ←✩ Samp_L(1).

$$ (s(\lambda),\epsilon(\lambda)) $$

$$ \mathsf{S a m p}_{\mathcal{L}}(1^{\lambda}) $$

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{\lambda}) $$

$$ (s(\lambda),\epsilon(\lambda))\cdot $$

$$ \delta>0 $$

$$ \ s(\lambda),\epsilon(\lambda), $$

$$ s(\lambda)=2^{\varOmega(\lambda^{\delta})} $$

$$ \epsilon(\lambda)=1/2^{\varOmega(\lambda^{\delta})} $$

$$ |\mathsf{x}|+|\mathsf{w}|=O(\lambda^{\delta}) $$

$$ (\mathsf{x},\mathsf{w})\leftarrow\mathsf{S m p}_{\mathcal{L}}(1^{\lambda}) $$

a b ab Simple example is the DDH language where Samp_Loutputs group elements g,g,g, where a,b are chosen uniformly at random and g is a group generator, and Samp^L¯ outputs 3 random group elements _{a b c} g,g,g. More generally, hard-on-average problem is implied by the existence of one-way-functions since it is possible to construct a PRG from a one-way function [HILL99].

$$ \mathsf{S a m p}_{\mathcal{L}} $$

$$ g^{a},g^{b},g^{a b} $$

$$ a,b $$

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}} $$

$$ g^{a},g^{b},g^{c} $$

2.1 Continuous Leakage-Resilient OWFs

A leakage-resilient OWF (LR-OWF) f is a function that is one-way even when the adversary is allowed to learn arbitrary functions of f (x)’s preimage as long as this leakage is restricted to L bits. Continuous LR-OWF (CLR-OWF) in the floppy model [ADVW13, ADW09] is a generalization of this where leakages can happen multiple times. In short, it assumes a master secret key which is kept in a leakage free server (e.g., on a floppy disk) and then can be used to securely update the preimage x. L bits of leakage on the preimage can occur after each update. Importantly however, updates have to preserve the output of the ′ ′ OWF, that is f (x) = f (x) when x is an update of x.

$$ f(x)^{\prime} $$

$$ f(x)=f(x^{\prime}) $$

$$ x^{\prime} $$

λ More formally, a CLR-OWF consists of the following PPT algorithms: (1) KGen(1) that outputs a public parameter pp and an update key uk. (2) Sample(pp) takes as input the parameter pp and outputs a random OWF input x. (3) Eval(pp*,x*) is a deterministic algorithm that produces the OWF output y. (4) Update(uk*,x*) ′ takes in the update key uk and x, and outputs an updated OWF input x.

$$ {mathsf{K G e n}(1^{\lambda})} $$

$$ x.:(3):\mathsf{E v a l}(\mathsf{p p},x) $$

$$ x^{\prime} $$

We assume that a CLR-OWF satisfies the following properties.

λ ∗ Correctness. For any (pp*,uk) ∈ KGen(1) and x ∈{0,1}, we have Eval(pp,Update(uk,x*)) = Eval(pp*,x*). L-Continuous leakage-resilience. Let L = L(λ). For any PPT A,

$$ (\mathsf{p p},\mathsf{u k})\in\mathsf{K G e n}(1^{\lambda}) $$

$$ x\in{0,1}^{*} $$

$$ \mathsf{E v a l}(\mathsf{p p},\mathsf{U p d a t e}(\mathsf{u k},x))=\mathsf{E v a l}(\mathsf{p p},x) $$

$$ L=L(\lambda) $$

$$ \Pr \left[ \begin{array}{c} (\mathrm {p p}, \mathrm {u k}) \leftarrow \mathrm {K G e n} \left(1 ^ {\lambda}\right), x \leftarrow \mathrm {S a m p l e} (\mathrm {p p}), \ y \leftarrow \operatorname {E v a l} (\mathrm {p p}, x), x ^ {\prime} \leftarrow \mathcal {A} ^ {\mathrm {O} _ {L} (\cdot)} (\mathrm {p p}, y) \end{array} : y = \operatorname {E v a l} (\mathrm {p p}, x ^ {\prime}) \right] = \operatorname {n e g l} (\lambda), $$

∗ L where O_L(·) is an oracle that takes as an input a leakage function h : {0,1} →{0,1}, on which O_L(h) sets x ← Update(uk*,x*) and then returns h(x).

$$ \ mathrm O{}_{L}(\cdot) $$

$$ h:{0,1}^{*}\rightarrow{0,1}^{L} $$

$$ x\leftarrow\mathsf{U p d a t e}(\mathsf{u k},x) $$

$$ \mathrm{O}_{L}(h) $$

$$ h(x) $$

λ Agrawal et al. [ADVW13] propose and prove the security of the following CLR-OWF. KGen(1) picks a n discrete logarithm secure group G of order p with a generator g. It samples ⃗α = (α₁,...,αⁿ) ←✩ Z^paⁿd sets _αi gi*← g* for i = 1*,...,n*. The public parameter is pp = (G*,g,g₁,...,gn) and the update key is uk = ⃗α. The Qn n i sampling algorithm Sample(pp) outputs ⃗x ←_✩ Z_p. Eval(pp,⃗x*) retur_ns y ← g_ix. Update(uk*,⃗x*) chooses a i=1 ′ random vector β⃗ that is orthogonal to ⃗α and returns ⃗x ← ⃗x + β⃗. Q_{P P P}Q

$$ g_{i}\leftarrow g^{\alpha_{i}} $$

$$ {\vec{\alpha}}=\left(\alpha_{1},\ldots,\alpha_{n}\right)\leftarrow\Re\mathbb{Z}_{p}^{n} $$

$$ i=1,\ldots,n $$

$$ {\mathfrak{p p}}=({\mathbb{G}},g,g_{1},\ldots,g_{n}) $$

$$ \vec{x}\leftrightarrow\Re\mathbb{Z}_{p}^{n} $$

$$ =\vec{\alpha} $$

$$ \mathsf{S a m p l e(p p)} $$

$$ \vec{\beta} $$

$$ \textstyle{textstyle y leftarrowleftarrow\prod_{i=1}^{n}g_{i}^{x_{i}}} $$

$$ \vec{x}^{\prime}\leftarrow\vec{x}+\vec{\beta} $$

$$ \vec{\alpha} $$

′ n n n n xi αi xi + αi βi αi xini The correctness holds si_nce g = gi₌₁ i=1= gi=1= g. ⁱ=1 ⁱ i_{=1 ix}

$$ \textstyle{\prod_{i=1}^{n}g_{i}^{x_{i}^{\prime}}=g^{\sum_{i=1}^{n}\alpha_{i}x_{i}+\sum_{i=1}^{n}\alpha_{i}\beta_{i}}=g^{\sum_{i=1}^{n}\alpha_{i}x_{i}}=\prod_{i=1}^{n}g_{i}^{x_{i}}.} $$

Theorem 1([ADVW13]). If the discrete logarithm assumption holds in group G*, then there exists a* L-CLR-OWF in the floppy model, with L(λ) < (n − 2) log p − ω(logλ).

$$ L(\lambda)<(n-2)\log{p}-\omega(\log{\lambda}) $$

3 On Adaptively-Secure Black-Box Extraction

There is a folklore understanding that if an argument has black-box knowledge soundness (i.e., there is an efficient algorithm Ext that can recover a witness from a proof by using a trapdoor and Ext is independent of adversary’s code), then the proof has to be “as long as the witness”. It is easy to see that such a statement is not entirely accurate. Consider an argument system for some relation R_Lwhere L is an NP-language. ′L k The same argument system works for a modified relation R = {(x*,* w*∥0) : (x,w) ∈R_L}* where the witness ′L k is padded with k zeroes for an arbitrary number k. An extractor Ext for R needs to append 0 to the ′L witness it extracts for R_L. Importantly, the proof length for R remains the same as for R_Lindependently of witness padding length. This section correctly formalizes the folklore result about proof size and witness length by associating hardness of finding the witness to the size of the argument.

$$ \mathcal{R}_{\mathcal{L}} $$

$$ \mathcal{R}{\mathcal{L}}^{\prime}=\left{\left(\mathsf{x},\mathsf{w}\middle|\ ^{k}\right):\left(\mathsf{x},\mathsf{w}\right)\in\mathcal{R}{\mathcal{L}}\right} $$

$$ k $$

$$ 0^{k} $$

$$ \mathcal{R}_{\mathcal{L}} $$

$$ \mathcal{R}_{\mathcal{L}}^{\prime} $$

$$ \mathcal{R}_{\mathcal{L}} $$

$$ \mathcal{R}_{\mathcal{L}}^{\prime} $$

We begin by recalling the definition of black-box knowledge soundness.

Black-box knowledge soundness. An argument system is black-box ε_ks(λ)-knowledge sound for a relation R if there exists a PPT extractor Ext, such that for any PPT adversary A, " #

$$ \varepsilon_{k s}(\lambda) $$

$$ \Pr \left[ \begin{array}{c c} (\mathrm {c r s}, \mathrm {t d}) \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}\right), (\mathrm {x}, \pi) \leftarrow \mathcal {A} (\mathrm {c r s}) \ \mathrm {w} \leftarrow \operatorname {E x t} (\mathrm {c r s}, \mathrm {t d}, \mathrm {x}, \pi) & : \quad \mathrm {V} (\mathrm {c r s}, \mathrm {x}, \pi) = 1 \wedge \ & (\mathrm {x}, \mathrm {w}) \notin \mathcal {R} \end{array} \right] \leq \varepsilon_ {k s} (\lambda). $$

We say the argument system is black-box knowledge sound if ε_ks(λ) = negl(λ).

$$ \varepsilon_{k s}(\lambda)={\mathsf{n e g l}}(\lambda) $$

We prove that if a witness of the language can be guessed with probability ε, then the proof size must be at least *−*log(ε + ε_ks) bits long. We start by formalizing the witness guessing probability.

$$ \varepsilon, $$

$$ -\log(\varepsilon+\varepsilon_{k s}) $$

Definition 1. Let L be an NP language and R_La corresponding relation. We say that an efficiently sam- pleable distribution D_Lover L is ε(λ)-witness-hard for a relation R_Lif for any PPT guesser M, and any security parameter λ ∈ N*,*

$$ \mathcal{R}_{\mathcal{L}} $$

$$ \mathcal{D}_{\mathcal{L}} $$

$$ \varepsilon(\lambda) $$

$$ \mathcal{R}_{\mathcal{L}}\ i j $$

$$ \lambda\in\mathbb{N} $$

$$ \operatorname*{P r}[\mathsf{x}\leftarrow\mathcal{D}(1^{\lambda}),\mathsf{w}\leftarrow\mathcal{M}(1^{\lambda},\mathsf{x})\ \ (\mathsf{x},\mathsf{w})\in\mathcal{R}_{\mathcal{L}}]\leq\varepsilon(1^{\lambda}). $$

Theorem 2. Suppose an efficiently sampleable distribution D_Lover some NP language is ε(λ)-witness- hard for a relation R_L. Let Π be an argument system that has (perfect) completeness and black-box ε_ks(λ)- knowledge soundness. Then the argument size of Π is at least − log(ε(λ) + ε_ks(λ)) bits.

$$ \mathcal{D}_{\mathcal{L}} $$

$$ \varepsilon(\lambda) $$

$$ \mathcal{R}_{\mathcal{L}} $$

$$ (p e r f e c t) $$

$$ \varepsilon_{s}(\lambda). $$

$$ -\log\bigl(\varepsilon\bigl(\lambda\bigr)+\varepsilon_{k s}\bigl(\lambda\bigr)\bigr) $$

Proof. Suppose that Π is an argument system with black-box extractor Ext and the argument size is bounded ∗ by p(λ) bits. We construct a witness-guesser M (see Figure 1), which picks a crs and an extraction key td and guesses a uniformly randomly a proof π of size p(λ) bits. It then returns the output of the black-box witness extractor Ext(crs*,td,* x*,π*).

$$ p(\lambda) $$

$$ {\mathcal{M}}^{*} $$

$$ \pi $$

$$ p(\lambda) $$

$$ \mathsf{E x t}(\mathsf{c r s},\mathsf{t d},\mathsf{x},\pi) $$

∗ Let us analyze the success probability ε_M∗ of M in the witness-hardness game against D_L. Let E be λ ∗ λ the distribution (x*,* w*,crs,π*) obtained by running x ←D(1) and w ←M (1*,*x) (crs and π are generated ∗ inside M). Then,

$$ \varepsilon_{\mathcal{M}}{}^{*} $$

$$ \mathcal{D}_{\mathcal{L}} $$

$$ \mathcal{E} $$

$$ {\mathcal M}^{*} $$

$$ (\mathsf{x},\mathsf{w},\mathsf{c r s},\pi) $$

$$ \ \ times mathcal D1^{\lambda}) $$

$$ \pi $$

$$ \mathsf{w}\leftarrow\mathcal{M}^{*}(1^{\lambda},\mathsf{x}) $$

$$ \begin{aligned}{\varepsilon_{\mathcal{M}^{}}}&{{}=\operatorname{P r}[(\mathsf,x\mathsf,\mathsf w{,c r s},\pi)\leftarrow\mathcal{E}(1^{\lambda}):(\mathsf x,\mathsf w)\in\mathcal{R}{\mathcal{L}}]}\ {}&{{}\geq\operatorname*{P r}[(\mathsf x,\mathsf w,\mathsf c{r r s},\pi)\leftarrow\mathcal{E}(1^{\lambda}):(\mathsf x,\mathsf w)\in\mathcal{R}{\mathcal{L}}\wedge\mathsf{V}(\mathsf c{{r r s}},\mathsf x,\pi)=1]}\ {}&{{}=\operatorname*{P r}[(\mathsf x,\mathsf w,\mathsf{r r s},\pi)\leftarrow\mathcal{E}(1^{\lambda}):(\mathsf x,\mathsf w)\in\mathcal{R}_{\mathcal{L}}\wedge\mathsf{V}(\mathsf{c s},\mathsf x,\pi)=1]}\ {}&{{}\quad\quad}\end{aligned} $$

Let us now look separately at probabilities ε₁ := Pr[(x*,* w*,crs,π*) ← E : V(crs*,* x*,π*) = 1] and ε₂ := Pr[(x*,* w*,crs,π*) ← E : (x*,w) ∈ R_L|* V(crs*,* x*,π*) = 1]. Starting with ε₁, (x*,w) ∈ R_Lobviously implies that x ∈ L and by perfect completeness there exists at least one proof of size at most p(λ) bits that p(λ) is accepted by the verifier. Thus, ε₁ ≥ 1/2. In order to lower bound ε₂, we construct an adversary B against black-box knowledge soundness. The adversary B, described in fig. 1, outputs x ← D_Land a p(λ) randomly sampled proof π ←{0,1}. By inlining B into the black-box knowledge soundness game, we get λ Pr[(x,* w*,crs,π*) ←E(1) : V(crs*,* x*,π*) = 1 ∧ (x*,*w) ̸∈R_L] ≤ ε_ks(λ). That is

$$ \varepsilon_{1};:=;\operatorname*{P r}[(\mathsf{x},\mathsf{w},\mathsf{c r s},\pi);\leftarrow;\mathcal{E};:;\mathsf{V}(\mathsf{c r s},\mathsf{x},\pi);=;1] $$

$$ {{\varepsilon}_{2}}\ := $$

$$ \varepsilon_ {1}, (\mathrm {x}, \mathrm {w}) \in \mathcal {R} _ {\mathcal {L}} $$

$$ \operatorname*{P r}[(\mathsf{x},\mathsf{w},\mathsf{c r s},\pi);\leftarrow;\mathcal{E};:;(\mathsf{x},\mathsf{w});\in;\mathcal{R}_{\mathcal{L}};\mid;\mathsf{V}(\mathsf{c r s},\mathsf{x},\pi);=;1] $$

$$ \varepsilon_{1},\geq,1/2^{p(\lambda)} $$

$$ p(\lambda) $$

$$ \varepsilon_{2} $$

$$ \mathcal {B}, $$

$$ \ {boldsymbol x\leftrightarrow\mathcal{D}_{\mathcal{L}}} $$

$$ \operatorname*{P r}[(\mathsf{x},\mathsf{w},\mathsf{c r s},\pi)\leftarrow\mathcal{E}(1^{\lambda}):\mathsf{V}(\mathsf{c r s},\mathsf{x},\pi)=1\wedge(\mathsf{x},\mathsf{w})\not\in\mathcal{R}{\mathcal{L}}]\leq\varepsilon{k s}(\lambda) $$

$$ \begin{array}{l} \Pr [ (\mathrm {x}, \mathrm {w}, \mathrm {c r s}, \pi) \leftarrow \mathcal {E} \left(1 ^ {\lambda}\right): V (\mathrm {c r s}, \mathrm {x}, \pi) = 1 \wedge (\mathrm {x}, \mathrm {w}) \notin \mathcal {R} _ {\mathcal {L}} ] \ = \Pr [ (\mathrm {x}, \mathrm {w}, \mathrm {c r s}, \pi) \leftarrow \mathcal {E} \left(1 ^ {\lambda}\right): (\mathrm {x}, \mathrm {w}) \notin \mathcal {R} _ {\mathcal {L}} | V (\mathrm {c r s}, \mathrm {x}, \pi) = 1 ] \ \cdot \Pr [ (\mathrm {x}, \mathrm {w}, \mathrm {c r s}, \pi) \leftarrow \mathcal {E} \left(1 ^ {\lambda}\right): V (\mathrm {c r s}, \mathrm {x}, \pi) = 1 ] \ \geq \Pr [ (\mathrm {x}, \mathrm {w}, \mathrm {c r s}, \pi) \leftarrow \mathcal {E} \left(1 ^ {\lambda}\right): (\mathrm {x}, \mathrm {w}) \notin \mathcal {R} _ {\mathcal {L}} | V (\mathrm {c r s}, \mathrm {x}, \pi) = 1 ] \cdot \frac {1}{2 ^ {p (\lambda)}}. \ \end{array} $$

∗ Fig. 1: A witness guessing algorithm M for R_Land a knowledge soundness adversary B

$$ {\mathcal{M}}^{*} $$

$$ \mathcal{R}_{\mathcal{L}} $$

λ p(λ) Thus, Pr[(x*,* w*,crs,π*) ← E(1) : (x*,w) ̸∈ R_L|* V(crs*,* x*,π*) = 1] ≤ ε_ks⁽λ⁾ · 2, which means that ε₂ > p(λ) 1 − ε_ks(λ) · 2. 1 ^p(λ) 1 By combining those results, we get that ε(λ) ≥ ε^M∗ >^p(λ)· (¹ − ε^ks(λ) · ₂) =^p(λ)− ε_ks. It follows 2 2 1 that ε(λ) + ε_ks>_p(λ), which we can rewrite as p(λ) > − log(ε(λ) + ε_ks(λ)). ⊓⊔ 2

$$ \operatorname*{P r}[(\mathsf{x},\mathsf{w},\mathsf{c r s},\pi);\leftarrow;\mathcal{E}(1^{\lambda});:;(\mathsf{x},\mathsf{w});\not\in;\mathcal{R}{\mathcal{L}};\mid;\mathsf{V}(\mathsf{c r s},\mathsf{x},\pi);=;1];\leq;\varepsilon{s}(\lambda);\cdot2;^{{(lambda)}} $$

$$ \varepsilon_{2}\ > $$

$$ 1-\varepsilon_{k s}(\lambda)\cdot2^{p(\lambda)} $$

$$ \begin{array}{l}{\varepsilon(\lambda)\geq\varepsilon_{\mathcal{M}^{*}}>\frac{1}{2p^{(\lambda)}}\cdot(1-\varepsilon_{k s}(\lambda)\cdot2^{p(\lambda)})=\frac{1}{2^{p(\lambda)}}-\varepsilon_{k s}}\ \end{array} $$

$$ \textstyle{\varepsilon(\lambda)+\varepsilon_{k s}>\frac{1}{2^{p(\lambda)}}} $$

$$ p\big(\lambda\big)>-\log\big(\varepsilon\big(\lambda\big)+\varepsilon_{k s}\big(\lambda\big)\big) $$

1 To understand this claim better, let us consider for simplicity that ε^ks(λ) = 0. Then if ε =^k(λ), we 2 1 obtain the lower bound p(λ) ≥− log(_k(λ)+ 0) = k(λ). In one extreme case, we can imagine that the best 2 PPT witness guesser is no better than an algorithm that guesses witness at random, i.e., ε(λ) = 1*/|w|*. Then we would get the folklore result that p(λ) = |π| ≥ |w|. In the other extreme, suppose that the language is in P, in which case ε(λ) = 1. Then we get that *−*log(ε) = 0, which fits the intuition that there is no need to communicate a proof for languages in P. However, in a typical situation (where we have some hard language), the lower bound falls somewhere between those extremes.

$$ \varepsilon_{k s}(\lambda),=,0 $$

$$ \textstyle\ \operatorname{f}\varepsilon={\frac{1}{2^{k(\lambda)}}} $$

$$ \textstyle{p\big(\lambda\big)\geq-\operatorname{l o g}\big(\frac{1}{2k(\lambda)}+0\big)=k\big(\lambda\big)} $$

$$ \varepsilon(\lambda)=1/|\mathsf{w}| $$

$$ p(\lambda),=,|\pi|,\geq,|\mathsf{w}| $$

$$ \varepsilon(\lambda)=1 $$

$$ -\log(\varepsilon),=,0 $$

The above impossibility can be interpreted as a consequence of leakage-resilience (LR). A SNARK proof is leakage on the witness; for an NP relation that is leakage resilient, recovering the entire witness is impossible for an extractor even given the leakage, if this leakage is small. We show the proof of this impossibility using LR-OWFs in Appendix B.

4 Non-Adaptive Black-Box Knowledge Soundness

In this section we define non-adaptive black-box knowledge soundness, show our positive results for FewP and our negative result for NP.

Below we define non-adaptive black-box knowledge-soundness. To the best of our knowledge it has not appeared in prior literature.

Definition 2(Non-adaptive Black-box Knowledge Soundness.). An argument system is non-adaptive black-box ε_ks(λ)-knowledge sound for a relation R if there exists a PPT extractor Ext*, such that for any PPT* adversary A = (A_inp, A_prf),  

$$ \varepsilon_{\mathrm{}{k s}}(\lambda) $$

$$ \mathcal{A}=(\mathcal{A}{i n p},\mathcal{A}{p rmathit{\ }}) $$

$$ \operatorname*{P r}\left[\begin{matrix}{(\mathsf{x},\mathsf{s t})\leftarrow\mathcal{A}{\mathrm{}{i n p}}(\mathsf{1}^{\lambda}),(\mathsf{c r s},\mathsf{t d})\leftarrow\mathsf{S e t u p}(\mathsf{1}^{\lambda})}\ {\pi\leftarrow\mathsf{A}{\mathrm{}{p r r}}(\mathsf{s t},\mathsf{c r s})}\ {\mathsf{w}\leftarrow\mathsf{E x t}^{\mathsf{A}{\mathrm{}{p r f}}(\mathsf{t t},,\mathsf{c r s})}(\mathsf{c r s},\mathsf{t t},\mathsf{x},\pi)}\ \end{matrix}:\begin{matrix}{\mathsf{V}r,\mathsf{x},\mathsf{x},\pi)=1}\ {\wedge(\mathsf{x},\mathsf{w})\not\in\mathcal{R}}\ \end{matrix}\right]\leq\varepsilon{\mathrm{}{k s}}(\lambda). $$

We say that the argument system is (non-adaptively) black-box knowledge sound if ε_ks(λ) = negl(λ).

$$ f,\varepsilon_{k s}(\lambda)={\mathsf{n e g l}}(\lambda) $$

Remark 1. The adversary in Definition 2 is stateful only between the input-challenge stage and the proofchallenge stage (through st), but not otherwise. We also assume that on each query A_prf(st*, ·*) gets fresh random coins.

$$ \mathcal{A}_{p r f}(\mathsf{s t},\cdot) $$

4.1 A Construction for FewP

In this section we show that, under the existence of fully homomorphic encryption, collision-resistant hash functions and SNARGs (not necessarily of knowledge) for a certain complexity class K, there exists a nonadaptively secure SNARK with black-box extraction for K¹². We are able to obtain non-adaptive black-box

$$ K^{12} $$

¹² This class should include FHE encryption and CRHF and should be closed under conjunction. In our theorem statement we simply require a SNARG for NP.

λ Setup(1) ˆ)^λ (crsˆ*,td ← Π∃.Setup(1) ∗ i ←✩ [Nw] λ (pkFHE,skFHE) ← FHE.KG(1) ∗ cti∗ ←* FHE*.Enc(pk,i*) hk ←✩ KCRHF return (crs := (crsˆ*,ct,hk,pk),td := (sk,tdˆ)) i∗ FHE FHE P(crs,* R*,* x*,w) h ← Hhk(w) ctbit←* _FHE.Eval(pkFHE,fproj*,cti∗,w) where fproj(i,w) := wi ′ π ← Π∃.P(crsˆ, R,(x,hk,pk_FHE,h,* cti∗,ctbit),w) ′ where R (x,hk,pk_FHE,h, cti∗,ctbit; w) ⇐⇒ R(x,w) ∧ h = Hhk(w) ∧ ctbit= _FHE.Eval(pk_FHE,fproj*,cti∗,w) ∗ return π := (π,h, ctbit) ∗ V(crs,* R*,* x*,π*) ^∗ Parse π as (π,h, ctbit) ′ return Π∃.V crsˆ, R*,(x,hk,pk_FHE,h,* ct*i∗,*ctbit) ′ where R is defined like above

$$ i ^ {*} \leftarrow $ [ N _ {w} ] $$

$$ \left(\mathrm {p k} _ {\mathrm {F H E}}, \mathrm {s k} _ {\mathrm {F H E}}\right) \leftarrow \mathrm {F H E}. \mathrm {K G} \left(1 ^ {\lambda}\right) $$

$$ \mathsf{c t}_{i^{}}\leftarrow\mathsf{F H E.E n c}(\mathsf{p k},i^{}) $$

$$ \big(\mathsf{c r s}:=\big(\mathsf{c r s},\mathsf{c t}{i^{*}},\mathsf{h k},\mathsf{p k}{\mathsf{F H E}}\big),\mathsf{t d}:=\big(\mathsf{s k}_{\mathsf{F H E}},\hat{\mathsf{t d}}\big)\big) $$

$$ \mathrm {c t} _ {\mathrm {b i t}} \leftarrow \mathrm {F H E}. \mathrm {E v a l} \left(\mathrm {p k} _ {\mathrm {F H E}}, f _ {\mathrm {p r o j}}, \mathrm {c t} _ {i ^ {*}}, w\right) $$

$$ f_{\mathrm{p r o j}}(i,w):=w_{i} $$

$$ \pi \leftarrow \Pi_ {\exists}. \mathrm {P} (\mathrm {c r i s}, \mathrm {R} ^ {\prime}, (\mathrm {x}, \mathrm {h k}, \mathrm {p k} _ {\mathrm {F H E}}, h, \mathrm {c t} _ {i *}, \mathrm {c t} _ {\mathrm {b i t}}), \mathrm {w}) $$

$$ \mathsf{R}^{\prime}(\mathsf{x},\mathsf{h k},\mathsf{p k}{\mathsf{F H E}},h,\mathsf{c t}{i^{*}},\mathsf{c t}_{\mathsf{b i t}};\mathsf{w})\Longleftrightarrow $$

$$ \tt{R}(x,w)\ \wedge\ h=\ H{}tt_{h k}(w)\ \wedge\ {t}{h i t}=F H E\ E v v l(p k{F H E},f_{F r o j},c t_{t^{*}},w) $$

$$ \pi^{*}:=(\pi,h,\mathsf{c t}_{\mathrm{b i t}}) $$

$$ \pi^{*} $$

$$ (\pi,h,\mathsf{c t_{b i t}}) $$

Fig. 2: Non-adaptively secure black-box extractable construction for FewP. N_wis a bound on the witness size. Π_∃is the SNARG scheme.

$$ N_{w} $$

knowledge soundness for a non-trivial subset of NP called FewP. The class FewP can be described as the class of languages admitting at most a polynomial number of witnesses. We remark that if one-way permutations exist then P ̸= FewP¹³. One example of a natural application of a SNARK for FewP is proving knowledge of w such that R(w) is satisfied (for arbitrary relation R) and w opens a perfectly binding commitment.

$$ \mathbf{P},\neq,\mathbf{F e w P}^{13} $$

Further preliminaries for this section can be found in Appendix A where we define non-adaptive soundness of SNARG (which simply adapts Definition 2 to the non-extractable case) and the standard definitions of fully homomorphic encryption (FHE) and collision-resistant hash-functions (CRHF) which will be tools in our construction.

14 We present our extractable construction in Figure 2. As discussed in the introduction, its main intuition is that the prover provides a (ciphertext containing a) bit of the witness together with the proof. The index for which it is providing such bit must be somehow hidden. This is intuitively to prevent the adversary to act differently for different bits (e.g., using different valid witnesses). This allows us to extract because by repeatedly asking the prover for a proof referring to a different index. To achieve the latter, we use an FHE scheme (see also Remark 3). When extracting, we will need to keep track of what witness we are extracting for (since there could be several). We do this using a fingerprint through a collision-resistant hash function.

In the construction, we denote encryptions of a message x (with an implicit public-key that should be clear from the context) through double brackets JxK.

¹³ More generally, if poly-to-one one-way functions exist then P ̸= FewP [All86].

$$ \mathbf{P\ F e w P\ [A l l86]} $$

¹⁴ A slightly simpler construction for the case of UP (NP statements with a unique witness) is in Appendix C.

$$ \mathcal{E}(\mathsf{c r s},\mathsf{t d},\mathsf{x},\pi) $$

$$ [j]\leftarrow\mathsf{F H E.E n c}(\mathsf{p k},j) $$

$$ \left(\hat {\mathrm {c r s}}, \mathrm {p k} _ {\mathrm {F H E}}, \mathrm {s k} _ {\mathrm {F H E}}, \mathrm {h k}\right) $$

$$ \mathsf{c r s}{j}:=(\mathsf{c r s},[j],\mathsf{h k},\mathsf{p k}{\mathsf{F H E}}) $$

$$ \mathcal{A}_{\mathrm{p r f}} $$

$$ (\mathsf{c r s}_{j},\mathsf{x}) $$

$$ j^{*}=1,\ldots,N_{w} $$

$$ k=1,\ldots,N_{q}={\sf p o l y}(\lambda) $$

$$ \mathsf{Q l d x}(x,j^{*}) $$

$$ W[h^{*}][j]\neq\bot $$

$$ \pi^{*}=(h,\pi,\mathsf{c t}_{\mathrm{b i t}}) $$

$$ W[h^{}][1]\ldots W[h^{}][N_{w}] $$

$$ b\gets\bot $$

$$ b\gets\mathsf{F H E}D e c(\mathsf{s k}{\operatorname{F H E}},\mathsf{c t}{\operatorname{b i t}}); $$

$$ W[h][j]\leftarrow b $$

Fig. 3: Extractor for the case for FewP

Remark 2(On Zero-Knowledge of Our Construction). We observe that the construction in Figure 2 is zeroknowledge if the underlying SNARG is zero-knowledge. We do not prove since our main focus is on the knowledge soundness of the (succinct) proof system.

The extractor for FewP. The extractor is presented in Figure 3. It works by collecting different bits of the witness by decrypting ct_b(the ciphertext returned by the prover) and storing it in some table indexed by the corresponding hash. The crucial point is that there is only a polynomial number of witnesses and thus the extractor can (in the worst-case) “fingerprint” them all. Hashing the witness (through a collision-resistant hash function) keeps the proof succinct.

$$ c t_{b} $$

Theorem 3. If Π_∃is a non-adaptively sound SNARG scheme for NP*,* FHE is a semantically secure FHE scheme and H is a family of CRHFs, then the construction in Figure 2 is a SNARK for FewP satisfying Definition 2.

Proof. We use the extractor in fig. 3. The extractor can have embedded N_w, a bound on the number of witnesses, since it is non-uniform. In the remainder, we define S(j), for index j, as the set of strings h for which W [h][j] ̸= ⊥ after running QIdx(x*,j*). That is

$$ N_{w} $$

$$ S(j) $$

$$ j, $$

$$ W[h][j]\neq\bot $$

$$ S(j):=\left{h:[W][j]\neq\bot\mathrm{afaerrunning\mathsf Id}(\times,j)\right} $$

Later in lemma 1 we show that for j ∈ S(h) there exists w such that R(x*,*w) ∧ H(w) = h (with high probability). Therefore h ∈ S(j) intuitively means “the extractor holds the bit j of an actual witness w and H(w) = h”.

$$ j\ \in\ S(h) $$

$$ \mathsf{R}(\mathsf{x},\mathsf{w})\wedge\mathsf{H}(\mathsf{w}):=:h $$

$$ h\in S(j) $$

$$ j $$

$$ \mathsf{H}(\mathsf{w})=h $$

In order to argue black-box knowledge soundness, we should be able to successfully extract from an adversary with noticeable probability of returning an accepting proof¹⁵. We show that for this type of TN w adversary it holds with noticeable probability that ∃h ∈_j=1S(j) (this is key for extraction; see last line in extractor definition). We argue this is the case by combining two facts:

$$ \mathrm{f}^{15} $$

$$ \exists h \in \bigcap_ {j = 1} ^ {N _ {w}} S (j) $$

′ ′ – S(j) = S(j) with overwhelming probability for all j,j (lemma 3);

$$ -\ S(j)=S(j^{\prime}) $$

$$ j,j^{\prime} $$

– If Pr [adversary returns an accepting proof] is non-negligible then Pr [S(j) ̸= ∅] is non-negligible (lemma 4);

$$ -\operatorname{I f f r r} $$

$$ \operatorname*{P r}\left[S(j)\neq\emptyset\right] $$

T^{N w} If ∃h ∈^j=1S(j), then the string returned by the extractor is a witness with overwhelming probability because W [h][j] is a bit of a witness for the relation with overwhelming probability (by lemma 1) and because, except with negligible probability, there exists a unique w such that H_hk(w) = h (by lemma 5). This concludes the proof. ⊓⊔

$$ \exists h\in\bigcap_{j=1}^{N_{w}}S(j) $$

$$ \ \dot{W}[h][j] $$

$$ H_{h k}(w)=h $$

¹⁵ This simplifies the proof, but we can argue with minor modifications the case for an adversary returning an accepting proof with only non-negligible probability

The following auxiliary lemma shows that an element in the table constructed by the extractor actually captures a bit of the witness with high probability.

Lemma 1. For any PPT adversary A, for each j ∈ N_w, for each h ∈ S(j) (where S is defined in the proof of theorem 3) the following probability p is overwhelming:

$$ j\in N_{w} $$

$$ h\in S(j) $$

$$ p := \Pr \left[ \exists w: \mathcal {R} (x, w) \wedge H _ {\mathrm {h k}} (w) = h \wedge W [ h ] [ j ] = w _ {j} \right] $$

Proof. Consider h ∈ S(j). Notice that the event above is implied by the event R(x*,w) ∧ h = H_hk(w) ∧ ct_bit= FHE.Eval(pk_FHE,f*_proj*,ct_i∗,*w) (this is because the extractor in fig. 3 sets W [h][j] to the decryption of ct_bit). We can argue that the probability of such event is overwhelming because by definition of the extractor if ′ h ∈ S(j) then the adversary provided a corresponding SNARG proof for the relation R (which is equivalent to the event). Invoking soundness of the SNARG concludes the proof. ⊓⊔

$$ h\in S(j) $$

$$ R(x,W)\wedge h=H mathsf{H}{h}(W)\wedge\mathsf{C t}{b i t}= $$

$$ \mathsf{c t}_{\mathrm{b i t}} $$

$$ \ \mathsf{I}(\mathsf{p k}{\mathrm{F H E}},f{\mathrm{p r o j}},\mathsf{c t}_{i^{*}},\mathsf{w}) $$

$$ W[h][j] $$

$$ h\in S(j) $$

The following auxiliary lemma observes that the probability of an adversary returning a valid proof with ∗ good probability for a CRS containing a randomly sampled index i should also hold when we provide them ∗ with a CRS “referring to” an arbitrary index i. This is useful to ensure that we can apply our extraction strategy. Otherwise we could for example conceive an adversary returning a valid proof for all indices except a few. Such an adversary would return a valid proof with high probability for a honestly generated CRS but we would not be able to extract from it.

$$ i^{*} $$

$$ \ {{\sf t}}0{}^{73} $$

$$ i^{*} $$

Lemma 2. For any PPT adversary A, if Pr [A returns an accepting proof] in the black-box knowledge- ∗ soundness experiment (definition 2) is non-negligible then for any i ∈ [N_w] the following probability is non-negligible:

$$ \ {dot imath^{{*}}}\in\left[N_{w}\right] $$

$$ p_{a c c}^{(i^{})}:=\operatorname{P r}\left[(\sf{c r s},t\ {d\sf{\ d}})\leftarrow\overline{{\sf{S e t u p}}}_{i^{*}}(1^{\lambda}),(\sf{x},\pi)\leftarrow\mathcal{A}(\sf{c r s}),:,\mathbb{V}(\sf{c r s},\sf{x},\pi)=1\right] $$

where Setupi*∗ is defined in fig. 4.*

$$ \overline {{\mathrm {S e t u p}}} _ {i} $$

$$ f g.~4. $$

′ ′ (j) (j) Proof. First observe that for any adversary A, for any j,j ∈ [Nw]. The probabilities paccand paccmust be negligibly close. If they were not then we could build an adversary breaking IND-CPA of the FHE since ′ intuitively we could distinguish ciphertexts of j from those of j (a formal description of this adversary would be a simpler variant of the one we build in the proof of lemma 3).

$$ {\mathcal A}, $$

$$ p_{\mathrm{a c c}}^{(j)} $$

$$ p_{\mathrm{a c c}}^{({j}{'})} $$

$$ j,j^{\prime},\in,[N_{w}] $$

$$ j $$

$$ j^{\prime} $$

(avg) Next, we observe that we can write paccPr [A returns an accepting proof] in the black-box knowledge- ∗ (i) ∗ soundness experiment (definition 2) as a function of paccfor i = 1*,...,N*wthrough a simple marginalization and bound it as follows 1 X_{∗ ∗} (avg) (acc i) (acc i) p = p ≤ min p + ϵ

$$ p _ {\mathrm {a c c}} ^ {(\mathrm {a v g})} \Pr [ \mathcal {A} $$

$$ p_{\mathrm{a c c}}^{(i^{*})} $$

$$ i^{*}=1,\ldots,N_{w} $$

$$ p_{\mathrm{a c c}}^{\mathrm{(a v g)}}=\frac{1}{|N_{w}|}\sum_{i^{}\in|N_{w}|}p_{\mathrm{a c c}}^{(i^{})}\leq\operatorname*{m i n}{i^{*}\in|N{w}|}p_{\mathrm{a c c}}^{(i^{*})}+\epsilon $$

where ϵ is a negligible. We can argue the bound by simple algebra and by applying our previous observation. ∗ (avg) (i) As a consequence of the above, it is easy to see that, if paccis non-negligible, so must be each pacc. ⊓⊔

$$ p_{\mathrm{a c c}}^{\mathrm{(a v g)}} $$

$$ p_{\mathrm{a c c}}^{(i^{*})} $$

′ ′ Lemma 3. For any PPT adversary A_ksnd= (A_inp, A_prf), for all j ̸= j the sets S(j),S(j) are equal except with negligible probability (where S is defined in the proof of theorem 3).

$$ \mathcal{A}{k s n d}=\left(\mathcal{A}{i n p},\mathcal{A}_{p rmathit{\ }}\right) $$

$$ j\neq j^{\prime} $$

$$ S(j),S(j^{\prime}) $$

Proof. Assume by contradiction that it is not the case. We show we can break semantic security of FHE (appendix A.2) with the adversary A_CPAin fig. 5.

Intuitively the adversary A_CPAdoes the following. After receiving a public key pk_FHEfrom the FHE challenger, it uses it to “emulate” the extractor invoking a variant of QIdx in fig. 3 (QIdx in fig. 5). That is, A_CPAconstructs set S(j) exactly as the extractor (implicitly) does, but without storing the decrypted bits in W [h][j] (which it cannot do not having the secret key). More precisely, after receiving a valid proof for ∗ ∗ index j which includes hash h, A_CPAwill simply set W [h][j] to a dummy “check” value (✓ in fig. 5). This is enough to define the sets S(j) which are our concern below. By hypothesis there exist with non-negligible

$$ {\mathfrak{p k}}_{\mathrm{F H E}} $$

$$ \mathcal{A}_{\mathrm{C P A}} $$

$$ S(j) $$

$$ W[h][j] $$

$$ h^{*},\mathcal{A}_{\mathrm{C P A}} $$

$$ W[h^{*}][j] $$

$$ j $$

$$ S(j) $$

$$ \overline{{\mathsf{S e t u p}}}_{i^{*}}(1^{\lambda}) $$

$$ (\hat {\mathrm {c r s}}, \hat {\mathrm {t d}}) \leftarrow \Pi_ {\exists}. \operatorname {S e t u p} \left(1 ^ {\lambda}\right) $$

$$ (\mathsf{p k}{\mathrm{F H E}},\mathsf{s k}{\mathrm{F H E}})\gets\mathsf{F H E.K G(1}^{\lambda}) $$

$$ \mathsf{c t}_{i^{}}\leftarrow\mathsf{F H E.E n c}(\mathsf{p k},i^{}) $$

$$ \leftarrow\mathfrak{s},{\mathcal{}},{mathcal K K}_{\mathrm{C R H F}} $$

Fig. 4: Modified setup with fixed index in lemma 2.

probability indices j₀,j₁ such that S(j₀) ̸= S(j₁). Adversary A¹_CPAfinds such indices and returns j₀ and j₁ to the FHE challenger as challenge plaintexts. Once received a ciphertext ct_?A²_CPAwill query polynomially many times A_prfwith a CRS that uses ct_?as encrypted index. Call the set of response hash ciphertexts from these queries S^?. ^′

$$ j_{0},j_{1} $$

$$ S(j_{0})\neq S(j_{1}) $$

$$ \mathcal{A}_{\mathrm{C P A}}^{1} $$

$$ j_{0} $$

$$ j_{1} $$

$$ \mathrm {c t} _ {?} \mathcal {A} _ {\mathrm {C P A}} ^ {2} $$

$$ \mathcal{A}_{\mathrm{p r f}} $$

$$ \mathrm {c t} _ {2} $$

$$ S{\ } $$

By setting N_q—the number of queries—to an appropriately high value in QIdx and QIdx we can claim 16 the following fact. By invoking lemma 6, except with non negligible probability, the set S_?is equal to either S(j₀) or S(j₁). A_CPAcompares S_?to them and outputs the bit corresponding to which one it is equal to. From this we can conclude that the advantage of A_CPAin breaking semantic security is negligibly close to ′ ′ Pr[∃j,j : S(j) ̸= S(j)]. If the latter is non-negligible so is the advantage of A_CPA. Absurd. ⊓⊔

$$ N_{q} $$

$$ \overline{{\mathrm{Q i d d}}}^{\prime} $$

$$ 6^{16} $$

$$ S_{?} $$

$$ S(j_{0}) $$

$$ S(j_{1}).:\mathcal{A}_{\mathrm{C P A}} $$

$$ S7 $$

$$ \mathcal{A}_{\mathrm{C P A}} $$

$$ \operatorname*{P r}[\exists j,j^{\prime}:S(j)\neq S(j^{\prime})] $$

$$ \mathcal{A}_{\mathrm{C P A}} $$

Lemma 4. For any PPT adversary A, if Pr [A returns an accepting proof] in the black-box knowledge- soundness experiment (definition 2) is non-negligible then j ∈ [N_w] Pr [S(j) ̸= ∅] is non-negligible.

$$ j\in[N_{w}],\operatorname*{P r}\left[S(j)\neq\emptyset\right] $$

Proof. This follows easily by the definition of set S and how QIdx works (fig. 3). In fact, by inspecting the last two lines in the loop of QIdx and the definition of S (see proof of theorem 3) we can see that S(j) becomes is non empty set as long as the adversary returns at least one accepting proof referring to index j. (j) This can be bounded by the probability paccas defined in lemma 2. Applying that same lemma concludes the proof. ⊓⊔

$$ S(j) $$

$$ j. $$

$$ p_{\mathrm{a c c}}^{(j)} $$

The following fact is useful in the proofs of the lemmas above. It states that we should not expect hash collisions among witnesses.

′ ′ Lemma 5. For any PPT adversary, for all witnesses w*,* w such that R(x*,w) and R(x,* w) it holds that ′ Pr [H_hk(w) = H_hk(w)] is negligible, where the probability is over the randomness of the adversary and the sampling of hk*.*

$$ \ {mathsf w},{\mathsf w}^{\prime} $$

$$ \mathsf{R}(\mathsf{x},\mathsf{w}) $$

$$ \mathsf{R}(\mathsf{x},\mathsf{w}^{\prime}) $$

$$ \operatorname*{P r}\left[\sf{H}{h k}(w)=H sf{H}{h k}(w^{\prime})\right] $$

Proof. The statement follows directly from the collision-resistance of the hash function (appendix A.3) and from the fact that the instance x is selected independently of the hash key (this is implied by non-adaptive security, i.e. definition 2). ⊓⊔

The following lemma essentially states that the set S(j) “converges” after sufficiently many queries N_q= poly(λ).

$$ S(j) $$

$$ N_{q}= $$

Lemma 6. For any PPT adversary, for each index j, there exists constant c such that for all constants c c^′ ′ (λ) (λ) (t) c > c the sets S ⁽j⁾ = S ⁽j⁾ except with negligible probability, where S ⁽j) denotes the set S(j) after t queries to QIdx(x*,j*).

$$ c^{\prime}>c $$

$$ S^{(\lambda^{c})}(j)=S^{(\lambda^{c^{\prime}})}(j) $$

$$ j $$

$$ \ |d x(x,j) $$

$$ S^{(t)}(j) $$

$$ S(j) $$

Proof. For an adversary returning a valid proof with negligible probability, the result follows immediately. Let us then consider the case of an adversary returning a valid proof with non-negligible probability. We proceed by contradiction: assume that for any polynomial number of invocations t to QIdx(x*,j*), the size

$$ Q\vert d x(x,j) $$

¹⁶ Which guarantees that Nq = poly(λ) is sufficient.

$$ N_{q}={\mathsf{p o l y}}(\lambda) $$

A¹_CPA(pk_FHE) Initialize empty table W ˆ)λ (crsˆ*,td ← Π∃.Setup(1) Run Ainp to obtain input x hk ←✩ KCRHF ^∗ for j ∈ [|Nw |] ∗ Run QIdx(x,j*) endfor For each j let S(j) := h : W [h][j] ̸= ⊥} Find j₀,j₁ ∈ [|Nw |] such that S(j₀) ̸= S(j₁) (o.w. abort) Save all computed values in state st return (st*,m₀* = j₀,m₁ = j₁) A²_CPA(st*,ct_j?) ′ Initialize empty table W ^′ Run QIdx (x,ctj*?) ′ Let S?:= h : W [h] ̸= ⊥} Let b = 1 if S?= S(1); o.w. let b = 0 return b QIdx(x*,j*) JjK ← FHE*.Enc(pk,j*) Let crsj := (crsˆ*,* JjK*,hk,pkFHE) for k = 1,...,Nq* ∗ query Aprfon (crsj,x) obtaining π = (h,π, ctbit) If proof π accepts, then set W [h][j] ← ✓ endfor ^′ QIdx (x,ct_j?) Let crs?:= (crsˆ,ctj_?,hk,pk_FHE) for k = 1,...,Nq ∗ query Aprfon (crs?*,*x) obtaining π = (h,π, ctbit) ′ If proof π accepts, then set W [h] ← ✓ endfor

$$ \mathcal{A}{\operatorname{C P A}}^{1}(\mathsf{p k}{\operatorname{F H E}}) $$

$$ ,\hat{\mathsf{t d}})\leftarrow\varPi_{\exists}.\mathsf{S e t u p}(1^{\lambda}) $$

$$ \mathcal{A}_{\mathrm{i n p}} $$

$$ \overline{{Q mathbb d I x}}(mathsf\boldsymbol x j j^{*}) $$

$$ jboldsymbol{}^{*}\in\left[\left|N_{w}\right|\right] $$

$$ S(j):={\big{}h:W[h][j]\neq\bot} $$

$$ j_{0},j_{1}\in[|N_{w}|] $$

$$ S(j_{0})\neq S(j_{1}) $$

$$ \left(\mathsf{s t},m_{0}=j_{0},m_{1}=j_{1}\right) $$

$$ \mathcal{A}{\operatorname{C P A}}^{2}(\mathsf{s t},\mathsf{c t}{j_{?}}) $$

$$ W^{\prime} $$

$$ \overline{{Q(d d x}}^{\prime}(\mathsf{x},\mathsf{c t}{j{?}}) $$

$$ S_{?}:=\left{h:W^{\prime}[h]\neq\bot\right} $$

$$ S_{?}=S(1);\mathrm{o{.l} $$

$$ \mathsf{c r s}{j}:=(\mathsf{c r s},[j],\mathsf{h k},\mathsf{p k}{\mathrm{F H E}}) $$

$$ k=1,\ldots,N_{q} $$

$$ \ {\mathcal A}_{\mathrm{p r f}} $$

$$ \pi^{*}=(h,\pi,\mathsf{c t}_{\mathrm{b i t}}) $$

$$ (\mathsf{c r s}_{j},\mathsf{x}) $$

$$ W [ h ] [ j ] \leftarrow \checkmark $$

$$ (\mathsf{x},\mathsf{c t}{j{?}}) $$

$$ \mathsf{c r s}{?}:=(\mathsf{\hat{c r s}},\mathsf{c t}{j_{?}},\mathsf{h k},\mathsf{p k}_{\mathrm{F H E}}) $$

$$ k=1,\ldots,N_{q} $$

$$ \mathcal{A}_{\mathrm{p r f}} $$

$$ \pi^{*}=(h,\pi,\mathsf{c t}_{\mathrm{b i t}}) $$

$$ (\mathsf{c r s}_{?},\mathsf{x}) $$

$$ W^{\prime}[h]\leftarrow\sqrt{} $$

Fig. 5: IND-CPA adversary and auxiliary algorithms for proof in lemma 3.

of the set S(j) increases with non-negligible probability after a polynomial number of steps. Call N the number of witnesses of x and recall that N = poly(|x|) = poly(λ) since the language is in FewP. Denote by ∗ ^∗ (t) t the number of steps after which |S ⁽j⁾| = N with non-negligible probability. By our hypothesis, after a polynomial number of steps, at least one hash image will be added to S(j) with non-negligible probability. However, this implies either there is a hash collision among the set of witnesses with non-negligible probability (contradicting lemma 5), or that the number of witnesses is greater than N. Absurd. ⊓⊔

$$ S(j) $$

$$ N=p o1y(|x|)=p o l y(\lambda) $$

$$ |S^{(t^{*})}(j)|=N $$

$$ t^{*} $$

$$ S(j) $$

Fig. 6: Non-adaptive black-box knowledge soundness adversary

Fig. 7: Continuous leakage-resilience adversary B

Remark 3(On replacing FHE with PIR). While we express our construction through the language of FHE, we observe that the assumption of FHE can easily be replaced by the milder existence of Private Information Retrieval (or PIR) [CGKS95].

4.2 Impossibility for All NP

We now ask if the result from above could be extended to all NP. We answer this in the negative under mild assumptions. Our proof relies on the LR view of impossibility of BB extraction in the adaptive case (Appendix B). For the non-adaptive case, we can no longer view the SNARK proof as a one-time leakage since the extractor (LR adversary) has the ability to rewind the prover and obtain multiple proofs (leakages). Using continuous leakage resilience, we extend the impossibility to non-adaptive extraction.

Consider a L-CLR-OWF Σ = (KGen*,Sample,Eval,Update). We define a relation R_Σ= {((pp,y*),w) : λ pp ∈ KGen(1),w ∈ Sample(pp),Eval(pp,w) = y}. Suppose there is a non-adaptive black-box extractable SNARK for R_Σ. Let us further assume that the proof size of this SNARK is less than L bits.

$$ \mathcal{R}_{\varSigma}={((\mathsf{p p},y),w) $$

$$ \ {sf p p}:\in:{\sf K G e n}(1^{\lambda}),w:\in:{\sf S a m p l e}({\sf p p}),{\sf E v a l}({\sf p p},w):=:y} $$

$$ \mathcal{R}_{\Sigma} $$

λ We construct the following adversary A. First, A samples (pp*,uk) ← KGen(1), a random w, and outputs ((pp,y* = Eval(pp*,w*)),st = (pp,uk,w)). Next, the extractor can query A(st*, ·) with different CRSs and get proofs for the statement (pp,y*) ∈L^Rleak. Here we define A’s behavior as follows: on each query, A updates w, ′ ′ ′ that is it computes w ← Update(uk*,w*). Then it creates a proof with w, π ← P(crs*,(pp,y*),w), and returns ′ π. This proof is at most size L, thus at most L bits of information about w gets leaked. By L-CLR property it is not possible to recover a witness for (pp*,y*) from this amount of information. Hence, the extractor cannot extract the witness and such a SNARK cannot exist. We show this formally.

$$ ((\mathsf{p p},y{\ =\ }\mathsf{E v a l}(\mathsf{p p},w)),\mathsf{s t}=(\mathsf{p p},\mathsf{u k},w)). $$

$$ w, $$

$$ (\mathsf{p p},\mathsf{u k})\leftarrow\mathsf{K G e n}(1^{\lambda}) $$

$$ \mathcal{A}(\mathsf{s t},\cdot) $$

$$ (\mathsf{p p},y)\in\mathcal{L}{\mathcal{R}{emathrm{{l e k}}}} $$

$$ w^{\prime}\leftarrow\mathsf{U p d a t e}(\mathsf{u k},w) $$

$$ w^{\prime},\pi\gets\mathsf{P}(\mathsf{c r s},(\mathsf{p p},y),w^{\prime}) $$

$$ \pi. $$

$$ w^{\prime} $$

Theorem 4. Let Σ = (KGen*,Sample,Eval,Update) be an L-CLR-OWF and let Π be a non-adaptive black- box ε_ks(λ)-knowledge sound argument for R*_Σas defined above. If the proof size is less than L(λ) bits, then L-CLR-OWF can be broken with probability 1 − ε_ks(λ).

$$ \mathcal{R}_{\Sigma} $$

$$ \varepsilon_{k s}(\lambda) $$

$$ 1-\varepsilon_{k s}(\lambda) $$

Proof. Assume that the proof size of Π is upper bounded by L(λ). We show that in this case it is possible to break L-continuous leakage-resilient one-wayness of Σ. Firstly, we describe an adversary A = (A_inp, A_prf) for non-adaptive black-box knowledge soundness in Figure 6. This exactly follows the intuition we discussed above.

$$ \mathcal{A}=(\mathcal{A}{i n p},\mathcal{A}{p r f}) $$

Next, we construct an adversary B against CLR in Figure 7. Idea is that we want to use the extractor Ext of Π to recover the OWF preimage. To do so, B must provide Ext with proofs which are created by crs chosen by Ext. Since proofs depend on the OWF preimage w, B can use the leakage query oracle O_Lwith

$$ \ _L L $$

$$ \mathsf{G a m e}_{1}(1^{\lambda}) $$

$$ \mathsf{G a m e}_{2}(1^{\lambda}) $$

$$ (\mathsf{p p},\mathsf{u k})\leftarrow\mathsf{K G e n}(1^{\lambda}); $$

$$ (\mathsf{x}=(\mathsf{p p},y),\mathsf{s t}=(\mathsf{p p},\mathsf{u k},y,w))\leftarrow\mathcal{A}_{\mathrm{}{i n p}}(\mathsf{1^{\lambda}}); $$

$$ w\leftarrow{\sf S a m p l e}({\sf p p}); $$

$$ (\mathsf{c r s},\mathsf{t d})\leftarrow\mathsf{K G e n}(1^{\lambda}); $$

$$ \pi\leftarrow\mathsf{S i m}{\mathsf{p p},y}^{\mathsf{0}{L}(\cdot)}(\mathsf{c r s}); $$

$$ y\leftarrow\mathsf{E v a l}(\mathsf{p p},w); $$

$$ \pi\leftarrow\mathcal{A}_{\mathrm{}{p r f}}(\mathsf{s t},\mathsf{c r s}); $$

$$ x^{\prime}\leftarrow\mathsf{E x t}^{\mathcal{A}_{\ f r f}(\mathsf{s t},\mathsf{c r s})}(\mathsf{c r s},\mathsf{t d},(\mathsf{p p},y),\pi); $$

$$ x^{\prime}\leftarrow\mathsf{E x t}^{\mathsf{S i m}{\mathsf{p p},y}^{\mathsf{0}{}_L(\cdot)}(\cdot)}(\mathsf{c r s},\mathsf{t d},(\mathsf{p p},y),\pi);} $$

$$ {\mathrm{r e t u r n~}}y={\mathsf{E v a l}}({\mathsf{p p}},x^{\prime}); $$

$$ y=\mathsf{E v a l}(\mathsf{p p},x^{\prime}) $$

Fig. 8: Security games for Theorem 4

a function h_crs,y,pp(X) := P(crs*,(pp,y*),X). This is possible only because the proof size is ≤ L(λ) bits. In OL(·) Figure 7, B runs a subroutine Sim_pp,y⁽crs⁾ for creating proofs.

$$ h_{\mathsf{c l s},y,\mathsf{p p}}(X):=\mathsf{P}(\mathsf{c r s},(\mathsf{p p},y),X) $$

$$ \operatorname{l s}\leq L(\lambda) $$

$$ \ \mathsf{S i m}{\mathsf{p p},y}^{\mathsf{O}{L}(\cdot)}(\mathsf{c r s}) $$

In the following, we will analyze the success probability of B. Essentially, we show that if Ext succeeds in extracting with high probability, then also B will succeed in breaking L-continuous leakage-resilience of OWF with high probability.

Game₀. This is the original L-CLR game with the adversary B from Section 2.1.

Game₁. This is the same game with B being in-lined. See fig. 8. Obviously the probability that y = ′ Eval(pp*,x*) is the same in both games.

$$ y= $$

$$ \mathsf{E v a l(p,x^{\prime})} $$

Game₂. This game is again just a slight rewrite of the previous Game₁. Note that the first three lines of λ λ Game₁ in Figure 8 are equivalent to A_inp(1). So we instead write (x = (pp*,y*),st = (pp,uk,y,w)) ←A_inp(1) OL(·) OL(·) in Game₂. Moreover, Sim^pp,y(crs⁾ and A^prf(st*,crs) produce the exact same proof π. We change Sim_pp,y⁽crs⁾ ′ to A_prf(st,crs) in Game₂. Clearly again the probability of y = Eval(pp,x*) is the same as before.

$$ \mathcal{A}_{i n p}(1^{\lambda}) $$

$$ (\mathsf{x}=(\mathsf{p p},y),\mathsf{s t}=(\mathsf{p p},\mathsf{u k},y,w))\leftarrow\mathcal{A}_{\ p p}(1^{\lambda}) $$

$$ {\mathsf{S i m}}{\mathsf{p p},y}^{0{L}(\cdot)}(\mathsf{C r s}) $$

$$ \mathcal{A}_{\mathrm{}{p r f}}(\mathsf{s t},\mathsf{c r s}) $$

$$ \ {\mathfrak{S i m}}{{\mathfrak{p p}},y}^{0{L}(\cdot)}({\mathfrak{C r s}}) $$

$$ \mathcal{A}_{\mathrm{}{p r f}}(\mathsf{s t},\mathsf{c r s}) $$

$$ y={\mathsf E v}l({\mathsf p p},x^{\prime}) $$

′ Note that Game₂ with the winning condition V(crs*,(pp,y*),π) = 1 ∧ y ̸= Eval(pp*,x*) is the non-adaptive black-box knowledge soundness game. We know that this probability is bounded by ε_ks(λ). Thus, V(crs*,(pp,y*),π) ̸= ′ 1 ∨ y = Eval(pp*,x*) happens with a probability > 1 − ε_ks(λ). However, V(crs*,(pp,y*),π) ̸= 1 is not possible ′ ′ given the construction of A_prf. Thus, V(crs*,(pp,y*),π) ̸= 1*∨ y* = Eval(pp*,x*) is equivalent to y = Eval(pp*,x*), which is the Game₂ winning condition. It follows that B can break L-CLR with the probability 1*− ε*_ks(λ). ⊓⊔

$$ \mathsf{V}(\mathsf{c r s},(\mathsf{p p},y),\pi)=\mathsf{1}\land y\neq\mathsf{E v a l}(\mathsf{p p},x^{\prime}) $$

$$ \varepsilon_{\ \ {{k}}\ }(\lambda) $$

$$ \mathsf{V}(\mathsf{c r s},(\mathsf{p p},y),\pi)\neq $$

$$ 1\vee y={\mathsf{E v a l}}({\mathsf{p p}},x^{\prime}) $$

$$

1-\varepsilon_{k s}(\lambda) $$

$$ \mathsf{V}(\mathsf{c r s},(\mathsf{p p},y),\pi)\neq $$

$$ \mathcal{A}_{p r f} $$

$$ \mathsf{V}(\mathsf{c r s},(\mathsf{p p},y),\pi)\neq\mathtt{1}\vee y=\mathsf{E v a l}(\mathsf{p p},x^{\prime}) $$

$$ y={\mathsf E v}l({\mathsf p p},x^{\prime}) $$

$$ 1 - \varepsilon_ {k s} (\lambda) $$

By combining Theorem 4 and Theorem 1, we obtain the following result.

Theorem 5. There exists an NP*-language L such that any non-adaptive black-box knowledge sound argu-* ment system for R_Lhas a proof size Ω(|w|) where |w| is the witness size.

$$ \mathcal{R}_{\mathcal{L}} $$

5 GW Impossibility for Preprocessing SNARGs

Careful observation of [GW11] reveals that the CRS generation algorithm of a SNARG in their definition depends only on the security parameter. In other words, the proof separating SNARGs from falsifiable assumptions assumes that the SNARG is CRS succinct and they do not allow preprocessing. Many modern SNARGs however have a relatively large CRS which depends on the size of the index i (e.g., a circuit

• • description) in some way [CFF 20, CHM 20, GWC19, GGPR13, Gro16, RZ21]. This makes it questionable if the original impossibility result of Gentry and Wichs extends to such SNARGs.

$$ \mathrm{(C F F^{+}20,\ C H M^{+}20} $$

5.1 Additional Preliminaries For This Section

Succinct non-interactive arguments. Here we recall the notion of non-interactive arguments for indexed relations.

• Definition 3(Indexed relation [CHM 20]). An indexed relation R is a set of triples (i*,* x*,w) where i is the index, x is the instance, and w is the NP-witness; the corresponding* indexed language L(R) is the set of pairs (i*,x) for which there exists a witness w such that (i,* x*,w) ∈R. Indexed relation is associated with an λ efficient index sampling algorithm I that outputs an index i on input 1.*

$$ \bf{[C H M^{+}20])} $$

$$ {\mathcal{L}}({\mathcal{R}}) $$

$$ (\mathsf{i},\mathsf{x},\mathsf{w})\in\mathcal{R} $$

$$ 1^{\lambda} $$

For example, i can be an arithmetic circuit, x a public input to the circuit and w a private input to the circuit such that the circuit outputs 1. We say that an indexed language is hard-on-average problem if it is λ defined like in section 2, but additionally SampLand SampL¯ take i ←I(1) as an input.

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}} $$

$$ \mathsf{S a m p}_{\mathcal{L}} $$

A succinct non-interactive argument (SNARG) for an indexed relation R is a tuple of PPT algorithms λ Π = (Setup*,* P*,V). The setup algorithm Setup(1,i) produces a common reference string crs. The prover algorithm P(crs,* x*,w) produces a proof π for the statement (i,x) ∈ L. The verifier algorithm V(crs,* x*,π*) decides if π is a valid proof for a statement (i*,*x) by outputting either 0 or 1. Notice that P and V are not directly given i as an input and instead get a crs which depends on i. This allows to potentially compress the index description by preprocessing.

$$ \mathsf{S e t u p}(1^{\lambda},\mathsf{i}) $$

$$ \mathit{\Pi}=(\mathsf{S e t u p},\mathsf{P},\mathsf{V}) $$

$$ \pi $$

$$ \mathsf{P}(\mathsf{c r s},\mathsf{x},\mathsf{w}) $$

$$ \mathrm{i f}\ pi $$

$$ (\mathsf{i},\mathsf{X})\in\mathcal{L} $$

$$ \mathsf{V}(\mathsf{c r s},\mathsf{x},\pi) $$

We require that Π satisfies the following three properties.

λ Completeness. For all (i*,* x*,w) ∈R, Pr[crs ← Setup(1,i),π ←* P(crs*,* x*,w) : V(crs,* x*,π*) = 1] = 1. Soundness. For all non-uniform PPT adversaries A,

$$ {\mathcal A}, $$

$$ \Pr \left[ \begin{array}{c c} \mathrm {i} \leftarrow \mathcal {I} \left(1 ^ {\lambda}\right), \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}, \mathrm {i}\right) \ (\mathrm {x}, \pi) \leftarrow \mathcal {A} \left(1 ^ {\lambda}, \mathrm {i}, \mathrm {c r s}\right) & : \quad \mathrm {V} \left(\mathrm {c r s}, \mathrm {x}, \pi\right) = 1 \wedge \ & (\mathrm {i}, \mathrm {x}) \notin \mathcal {L} \end{array} \right] = \operatorname {n e g l} (\lambda). $$

Proof succinctness. Exists a constant c < 1 such that the length of the proof π is bounded by succ(λ, |x|, |w|) := c poly(λ) · (|x| + |w|).

$$ c<1 $$

$$ \ {sf{s u c}}_{c}(\lambda,|{\sf{x}}|,|{\sf{w}}|):= $$

$$ \ {sf p o l y}(\lambda)\cdot(|{\sf x x}|+|{\sf w}|)^{c} $$

We note that this is the original definition of (proof) succinctness from [GW11] and various other definitions can be found from the literature. Moreover, we occasionally discuss two other forms of succinctness.

Verifier succinctness. Exists a constant c < 1 such that the verifier’s running time is bounded by poly(|x|+ suc_c(λ, |x|, |w|)).

$$ c<1 $$

$$ _{(}\lambda,|\mathsf{x}|,|\mathsf{w}|), $$

CRS succinctness. CRS size is poly(λ). Importantly, CRS size is independent of |i|.

$$ ||\ \ |, $$

• • For example, [CFF 20, CHM 20, Gro16, PHGR13, RZ21] are proof and verifier succinct but not CRS succinct.

$$ \mathrm{[C F F^{+}20,,C H M^{+}20} $$

Falsifiable assumptions. Below we recall the notion of falsifiable assumptions.

Definition 4([GW11]). A falsifiable cryptographic assumption (C,c) consists of a PPT challenger C and λ λ a constant c ∈ [0*,1). We say that A wins* (C,c) if A(1) and C(1) interact and finally C outputs 1*. The* assumption (C,c) holds if for all efficient non-uniform A, Pr[A wins (C,c)] ≤ c + negl(λ). Otherwise we say that (C,c) is false.

$$ (\mathcal{C},c) $$

$$ c\in[0,1) $$

$$ (left\mathcal{C},c):\mathit f:\mathcal{A}(1^{\lambda}) $$

$$ \mathcal{C}(1^{\lambda}) $$

$$ (\mathcal{C},c) $$

$$ (\mathcal{C},c) $$

$$ (\mathcal{C},c)]\leq c+\mathsf{n e g l}(\lambda) $$

Definition 4 captures most used cryptographic assumptions in the literature. For example, many search assumptions such as discrete-logarithm (DL), computational Diffie-Hellman (CDH), etc can be captured by this definition with c = 0. Moreover, the definition captures many decisional assumptions such as decisional Diffie-Hellman (DDH), decisional Learning with Errors (LWE), etc as (C,c = 1*/2) assumptions since the adversary in this case can win with probability 1/*2 by random guessing. An example of assumptions that are not falsifiable are “Knowledge” assumptions [Dam92, HT98] that assume the existence of some non-black-box extractor.

$$ c=0 $$

$$ (\mathcal{C},c=1/2) $$

Black-box reductions. We recall the definition of black-box reduction from [GW11] adapted to the indexed relations. Similarly to [GW11], the definition is for the concrete case of showing soundness of some SNARG proof system Π = (Setup*,* P*,*V) based on some falsifiable assumption (C,c).

$$ \mathit{\Pi}=(\mathsf{S e t u p},\mathsf{P},\mathsf{V}) $$

$$ (\mathcal{C},c) $$

Definition 5. We say that a (possibly inefficient) machine P is a Π -adversary if there exists a polynomial p(·) and infinitely many λ ∈ N such that

$$ \overline{{}P}} $$

$$ p(\cdot) $$

$$ \lambda\in\mathbb{N} $$

$$ \Pr [ \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}, \mathrm {i}\right), (\mathrm {x}, \pi) \leftarrow \bar {\mathrm {P}} (\mathrm {c r s}, \mathrm {i}): (\mathrm {i}, \mathrm {x}) \notin \mathcal {L} \wedge \mathrm {V} (\mathrm {c r s}, \mathrm {x}, \pi) = 1 ] \geq 1 / p (n) $$

Definition 6. A black-box reduction that shows the soundness of Π based on a falsifiable assumption (C,c) (·) P is an efficient oracle machine R such that, for every (possibly inefficient) Π -adversary P*, the machine R* breaks the assumption.

$$ R^{(\cdot)} $$

$$ (mathcal C c c) $$

$$ R^{\overline{{P}}} $$

O(·) Definition 7([Pas13]). We say that an oracle machine R is a security-parameter preserving black-box O(·) λ λ ∗ reduction if there exist a polynomial q such that R (1⁾ queries O(·) with inputs of the form (1*,x ∈{0,1}*) and at most q(λ) times.

$$ R^{0(\cdot)} $$

$$ R^{0(\cdot)}(1^{\lambda}) $$

$$ (1^{\lambda},x\in{0,1}^{*}) $$

$$ \ (\ \cdot) $$

5.2 Our Result

We reprove the impossibility theorem for SNARGs that are not necessarily CRS-succinct.

Firstly, let us recall the leakage lemma from [GW11]. We say that a distribution A over tuples (x,π) is an augmented distribution of X if x is distributed according to X and π is some arbitrary information, possibly correlated to x. More formally, we may write A is the distribution over (x,π) such that x ←✩ X and π ← f(x) where f is some (randomized and possibly inefficiently computable) function.

$$ (x,\pi) $$

$$ (x,\pi) $$

$$ x\gets\S X $$

$$ \pi\gets f(x) $$

Lemma 7(Leakage lemma [GW11]). There exists a polynomial p for which the following holds. Let X and X¯ be two distributions that are (s(λ),ε(λ))-indistinguishable. Let A over (x,π) be an augmented λ λ λ distribution of X where |π| = ℓ(λ). Then there exist an augmented distribution A¯ of X¯ such that A and _λ λ λ λ ¯∗ ∗ ∗ ℓ(λ) ∗ A_λare (s (λ),ε (λ))-indistinguishable where s (λ) = s(λ)p(ε(λ)/2) and ε ₍λ₎ = 2ε(λ).

$$ X_{\lambda} $$

$$ A_{\lambda} $$

$$ {\bar{X}}_{\lambda} $$

$$ \ s(\lambda),\varepsilon(\lambda), $$

$$ (x,\pi) $$

$$ X_{\lambda} $$

$$ |\pi|=\ell(\lambda) $$

$$ \bar{A}_{\lambda} $$

$$ A_{\lambda} $$

$$ \bar{A}_{\lambda} $$

$$ {\bar{X}}_{\lambda} $$

$$ \ s^{}(\lambda),\varepsilon^{}(\lambda)_{\ } $$

$$ s^{*}(\lambda)=s(\lambda)p(\varepsilon(\lambda)/2^{\ell(\lambda)}) $$

$$ \varepsilon^{*}(\lambda)=2\varepsilon(\lambda) $$

We also present some definitions which help to prove the main result.

Definition 8(Breaking Adaptive Soundness [Pas13]). We say that an algorithm A breaks adaptive soundness of a SNARG Π for a relation R with probability ε(·) if there exists an index i ∈I such that for every λ ∈ N*,*

$$ W e_{}, $$

$$ \ !inin\mathcal{I} $$

$$ \lambda\in\mathbb{N} $$

$$ \operatorname*{P r}[\sf{c r s}\leftarrow\tt{S e t u p}(1^{\lambda},i),(x,\pi)\leftarrow\cal{A}(1^{\lambda},c r s)\colon(i,x)\not\in\cal{L}\wedge\tt{V e r i f y}(c r s,x,,\pi)=1]\geq\varepsilon(\lambda). $$

Note that if ε(λ) is non-negligible, then adaptive soundness cannot be satisfied.

$$ \operatorname*{i f}\varepsilon(\lambda) $$

Definition 9(Soundness Reduction [Pas13]). We say that a PPT machine R is a black-box reduction for adaptive soundness of an argument Π based on a falsifiable assumption (C,c) if R is a security-parameter preserving black-box reduction and there exists a polynomial p(·, ·) such that for every A that breaks adaptive A λ soundness with probability ε(·), for every λ ∈ N*, R* (1) wins (C,c) with a probability at least p(ε(λ),1/λ).

$$ p(\cdot,\cdot) $$

$$ \varepsilon(\cdot) $$

$$ \lambda\in\mathbb{N},,R^{\mathcal{A}}(1^{\lambda}) $$

$$ (mathcal C c c) $$

$$ p(\varepsilon(\lambda),1/\lambda) $$

We start by stating two technical lemmas.

Lemma 8. If an indexed languages L∈ NP has a sub-exponentially hard-on-average problem, then for any d d λ λ d > 0*, L also has a hard-on-average problem with* (2*,1/2)-indistinguishability.*

$$ \ {\mathcal{L}}\in\mathbf{N P} $$

$$ (2^{\lambda^{d}},\dot{1/2^{\lambda^{d}}}) $$

$$ d>0,,\mathcal{L} $$

Proof. Let us recall that X and X¯ are said to be sub-exponentially indistinguishable if there exists a λ λ δ δ ¯Ω(λ) Ω(λ))-indistinguishable. Let us define _d/δ δ > 0 such that X_λand X_λare (2*,1/2 n(λ) = ⌈λ ⌉. Then δ d/δ _δ ¯ ¯_Ω(n) _Ω(⌈_λ ⌉) and Y_λ:= X_n(λ)and Y_λ:= X_n(λ)are (s(λ),ε*(λ))-indistinguishable, where s(λ)=2 = 2 δ d/δ δ d/δ δ Ω(n) = 1 ^Ω(⌈λ ⌉). Firstly, since the circuit of size ^Ω(⌈λ ⌉) grows faster than the ε(λ) = 1*/*2 /2 s(λ) = 2

$$ X_{\lambda} $$

$$ \ {\bar{X}}_{\lambda} $$

$$ X_{\lambda} $$

$$ \delta,>,0 $$

$$ (2^{\varOmega\left(\lambda^{\delta}\right)},1/2^{\varOmega\left(\lambda^{\delta}\right)} $$

$$ n(\lambda),=,\lceil\lambda^{d/\delta}\rceil $$

$$ {\bar{X}}_{\lambda} $$

$$ Y_{\lambda},:=,X_{n(\lambda)} $$

$$ \bar{Y}{\lambda},:=,\bar{X}{n(\lambda)} $$

$$ s (\lambda) = 2 ^ {\Omega \left(n ^ {\delta}\right)} = 2 ^ {\Omega \left(\lceil \lambda^ {d / \delta} \rceil^ {\delta}\right)} $$

$$ \ s(\lambda),\varepsilon(\lambda), $$

$$ \varepsilon(\lambda)=1/2^{\varOmega\left(n^{\delta}\right)}=1/2^{\varOmega\left(\lceil\lambda^{d/\delta}\rceil^{\delta}\right)} $$

$$ s(\lambda)=2^{\varOmega\left(\lceil\lambda^{d/\delta}\rceil^{\delta}\right)} $$ d d λ¯λ circuit of size 2, then, for a sufficiently large λ, Y_λand Yλare also (2,ε(λ))-indistinguishable. Conversely, d d ¯_λ ′ ′ ′ λ Y_λand Yλare(2*,ε* (λ))-indistinguishable if ε (λ) ≥ ε(λ). This is the case for ε (λ) = 1*/2 if λ is again d d ¯_λ λ sufficiently large. It follows that for a large enough λ, exists Y_λand Y_λthat are (2,1/*2)-in^distinguishable.

$$ (2^{\lambda^{d}},\varepsilon(\lambda)) $$

$$ 2^{\lambda^{d}} $$

$$ Y_{\lambda} $$

$$ \bar{Y_{\lambda}} $$

$$ \lambda,Y_{\lambda} $$

$$ \bar{Y}_{\lambda},\operatorname{a r e}(2^{\lambda^{d}},\varepsilon^{\prime}(\lambda)) $$

$$ \varepsilon^{\prime}(\lambda),\geq,\varepsilon(\lambda) $$

$$ \varepsilon^{\prime}(\lambda)=1/2^{\lambda^{d}} $$

$$ \lambda $$

$$ Y_{\lambda} $$

$$ \lambda, $$

$$ \bar{Y}_{\lambda} $$

$$ (2^{\lambda^{d}},1/2^{\lambda^{d}}) $$

Let i be the index sampler and (Samp^L*,Samp^L¯) instance samplers for sub-exponentially hard-on-average ′ λ n(λ) ′L λ ′L n(λ) λ problem. Then we can always define I (1) as I(1), Samp ₍1,i₎ as Samp (1,i), a_nd Samp_L¯(1,i₎ as d d n(λ) λ λ SampL¯⁽1,i⁾, which gives the desired hard-on-average problem with (2,1/*2)-in^distinguishability. ⊓⊔

$$ (\mathsf{S a m p}{\mathcal{L}},\mathsf{S a m p}{\bar{\mathcal{L}}}) $$

$$ \mathcal{I}(\tilde{1}^{n(\lambda)}),\mathsf{S a m p}_{\mathcal{L}}^{\prime}(\tilde{1^{\lambda}},\mathsf{i}) $$

$$ \mathcal{I}^{\prime}(1^{\lambda}) $$

$$ \mathsf{S a m p}_{\mathcal{L}}^{\prime}(1^{n(\lambda)},\mathsf{i}) $$

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{\lambda},\mathsf{i}) $$

$$ \mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{n(\lambda)},\dot{\mathsf{I}}) $$

$$ (2^{\lambda^{d}},1/2^{\lambda^{d}}) $$

d d ¯λ λ Lemma 9. Let X_λand Xλbe (2,1/2)-indistinguishable distributions for some integer d ≥ 2*. Let A*_λ d over (x,π) be an augmented distribution of X^λ, where |π| = ℓ(λ) = o λ. Then there exists an augmented distribution A¯ of X¯ such that A and A¯ are (poly(λ),negl(λ))-indistinguishable. λ λ λ λ

$$ X_{\lambda} $$

$$ {\bar{X}}_{\lambda} $$

$$ \geq2 $$

$$ A_{\lambda} $$

$$ (2^{\lambda^{d}},1/2^{\lambda^{d}}) $$

$$ X_{\lambda} $$

$$ \ \left|\pi\right|=\ell\ \big(\lambda\big)=o\big(\lambda^{d}\big) $$

$$ \bar{A}_{\lambda} $$

$$ \bar{X}_{\lambda} $$

$$ A_{\lambda} $$

$$ \bar{A}_{\lambda} $$

$$ (\mathsf{p o l y}(\lambda),\mathsf{n e g l}(\lambda)) $$

d d ¯λ λ Proof. Let X_λand Xλbe (s(λ),ε(λ))-indistinguishable, where s(λ) = 2 and ε(λ) = 1*/2. Then X_λand d d−1 ¯′ ′ _λ ′ λ Xλare (s(λ),ε (λ))-indistinguishable for any ε (λ) ≥ 1/2. Let us take ε (λ) = 1/2. According to the leakage lemma, there exists a polynomial p and an augmented distribution A¯ of X¯ such that A and A¯ _λ λ λ λ ∗ ∗ ∗ ′ ℓ(^λ) ∗ ′ are (s (λ),ε* (λ))-indistinguishable where s (λ) = s(λ)p(ε (λ)/2) and ε ⁽λ⁾ = 2ε (λ).

$$ X_{\lambda} $$

$$ {bar{X}}_{\lambda} $$

$$ s(\lambda)=2^{\lambda^{d}} $$

$$ (s(\lambda),\varepsilon(\lambda)) $$

$$ \varepsilon(\lambda)=1/2^{\lambda^{d}} $$

$$ X_{\lambda} $$

$$ \bar{X}_{\lambda} $$

$$ \varepsilon^{\prime}(\lambda)\geq1/2^{\lambda^{d}} $$

$$ (s(\lambda),\varepsilon^{\prime}(\lambda)) $$

$$ \varepsilon^{\prime}(\lambda)=1/2^{\lambda^{d-1}} $$

$$ A_{\lambda} $$

$$ s^{*}(\lambda)=s(\lambda)p(\varepsilon^{\prime}(\lambda)/2^{\ell(\lambda)}) $$

$$ A_{\lambda} $$

$$ \left(s^{}(\lambda),\varepsilon^{}(\lambda)\right) $$

$$ \ bar\cal{A}_{\lambda} $$

$$ \varepsilon^{*}(\lambda)=2\varepsilon^{\prime}(\lambda) $$

d−1 d−1 ∗ ∗ ′ λ λ −1 Clearly ε (λ) is negligible since ε (λ)=2ε (λ)=2*/2 = ¹/2 = negl(λ). The distinguisher d d−1 d d−1 d d−1 ∗ ∗ ′ ℓ(λ) λ −λ −o(λ)). Here, ^−λ −o(λ)) = 2−o(λ) and circuit size s (λ) is s (λ) = s(λ)p(ε (λ)/*2) = 2 p(2 p⁽2 ^{d d−1} d ∗ λ −o(λ) = 2Ω(λ). This means that indistinguishability holds also for all polynomial therefore s (λ) = 2 ∗ size circuits, as s (λ) grows faster than any polynomial. ⊓⊔

$$ \varepsilon^{*}(\lambda):=:2\varepsilon^{\prime}(\lambda):=:2/2^{\lambda^{d-1}}:=:1/2^{\lambda^{d-1}-1}:=:\mathsf{n e g l}(\lambda) $$

$$ \varepsilon^{*}(\lambda) $$

$$ s^{*}(\lambda) $$

$$ s^{*}(\lambda){\ =\ }s(\lambda)p(\varepsilon^{\prime}(\lambda)/2^{\ell(\lambda)}){\ =\ }2^{\lambda^{d}}p(2^{-\lambda^{d-1}-\operatorname{o}\left(\lambda^{d}\right)}). $$

$$ p(2^{-\lambda^{d-1}-0\left(\dot{\lambda}^{d}\right)})=2^{-0\left(\lambda^{d-1}\right)} $$

$$ s^{*}(\lambda)=2^{\lambda^{d}-0\left(\lambda^{d-1}\right)}=2^{\Omega\left(\lambda^{d}\right)} $$

$$ s^{*}(\lambda) $$

Remark 4. Note that (s(λ),ε(λ)) = (poly(λ)*,*negl(λ))-indistinguishability is not enough in the previous lemma because

$$ (s(\lambda),\varepsilon(\lambda))=(p o1y(\lambda),n e g(\lambda)) $$

$$ \begin{aligned}{s^{*}(\lambda)=}&{{}s(\lambda)p(\varepsilon(\lambda)/2^{\mathsf{p o l y}(\lambda)})=\mathsf{p o l y}(\lambda)p(\mathsf{n e g l}(\lambda)/2^{\mathsf{p o l y}(\lambda)})}\ {=}&{{}\mathsf{p o l y}(\lambda)p(2^{-\omega(\mathsf{p o l y}(\lambda))})=2^{-\omega(\mathsf{p o l y}(\lambda))},}\ \end{aligned} $$

given that p is not a constant polynomial.

Now we are ready to restate the Gentry-Wich’s impossibility result respect to preprocessing SNARGs from section 5.1.

Theorem 6. Assume that,

– L is an indexed language with a sub-exponentially hard-on-average problem (see section 2).

– Π is a SNARG for L, i.e., it is complete, sound, and proof-succinct (but not necessarily verifier-succinct or CRS-succinct).

$$ \mathcal{L},,i.e $$

Then, for any falsifiable assumption (C,c) either:

– (C,c) is false or,

– there is no black-box reduction for adaptive soundness of Π based on (C,c).

Proof. Suppose there exists a PPT black-box reduction R for adaptive soundness of Π based on a falsifiable λ assumption (C,c) and that R makes at most q(1) queries to its oracle, where q is some polynomial. The ∗ proof idea is that we construct a computationally unbounded adversary A that is able to break adaptive soundness. Then we show using lemma 7 that there is an efficient emulator Emul that gives outputs which ∗ ∗ A λ are indistinguishable from outputs of A. Thus, if R (1) is able to break the assumption (C,c), then so is ^{Emul λ} R (1) and it follows that (C,c) must be false.

$$ (mathcal C c c) $$

$$ (\mathcal{C},c) $$

$$ q(1^{\lambda}) $$

$$ \mathcal{A}^{*} $$

$$ R^{\mathcal{A}^{*}}(1^{\lambda}) $$

$$ R^{\mathsf{E m u l}}(1^{\lambda}) $$

$$ \mathcal{A}^{*} $$

$$ (mathcal C c c) $$

$$ (\mathcal{C},c) $$

n o(1) Since Π is proof-succinct there exists some n such that the proof size ℓ is bounded by λ · (|x| + |w|). Moreover by lemma 8, since we assume that some sub-exponentially hard-on-average problem exist for L, n+2 n+2 λ λ there also exist a sub-exponentially hard-on-average problem with (2*,1/2)-iⁿdistinguishability. Let it be defined by an index sampler I and instance samplers Samp^Land Samp^L¯. It is more convenient to start ∗ λ from describing the emulator Emul before we describe A. The emulator (see also fig. 9) on input (1,crs,i) _λ checks that i is well-formed, samples (x,w) ← Samp_L(1,i), creates a proof π ← P(crs,* x*,w) and returns (x,π*).

$$ \lambda^{n}\cdot(|left|\mathsf{x}|+|\mathsf{w}|)^{\operatorname{o}(1)} $$

$$ \left(2 ^ {\lambda^ {n + 2}}, 1 / 2 ^ {\lambda^ {n + 2}}\right) $$

$$ \mathcal{A}^{*} $$

$$ (1^{\lambda},\mathsf{c r s,i}) $$

$$ (\mathsf{x},\mathsf{w})\leftarrow\mathsf{S a m p}_{\mathcal{L}}(1^{\lambda},\mathsf{i}) $$

$$ \pi\leftarrow\ {sf P P}(\sf{c r s},\sf{x},\sf{w}) $$

$$ (\mathsf x\pi) $$

$$ 0_{i}(1^{\lambda},\mathsf{c r s,i})//\mathrm{I n i t i a l l y}\ j=1 $$

$$ \mathsf{E m u l}(1^{\lambda},\mathsf{c r s},\mathsf{i}) $$

$$ \mathcal{A}^{*}(1^{\lambda},\mathsf{c r s,}mathsf i $$

$$ \mathbf{i f}\ j\leq i $$

$$ \ \ {\mathrm{i f},\ \ !{\mathsf{i}}\not\in{\mathcal{I}}(1^{\lambda}) $$

$$ (\mathsf{x},\pi)\leftarrow\mathsf{E m u l}(1^{\lambda},\mathsf{c r s,}\mathsf{i}); $$

$$ \pi\leftarrow\mathbf{P}(\mathsf{c r s},\mathsf{x},\mathsf{w}); $$

$$ (\bar{\mathsf{x}},\bar{\pi})\xleftarrow{}\bar{A}{\lambda,\mathsf{i},\mathsf{c r s}};;;(\mathsf{x},\mathsf{w})\xleftarrow{}\mathsf{S a m p}{\mathcal{L}}(\mathbf{1}^{\lambda},\mathsf{i}). $$

$$ (\mathsf{x},\pi)\leftarrow\mathcal{A}^{*}(1^{\lambda},\mathsf{c r s},\mathsf{i}); $$

$$ j\gets j+1; $$

$$ (\mathsf{x},\pi): $$

∗ Fig. 9: Soundness adversary A, its efficient emulator Emul, and hybrid adversaries O_i

$$ \mathcal{A}^{*} $$

$$ \ _i, $$

Notice that since Samp^Lruns in polynomial time in λ, then |x| = poly(λ) and |w| = poly(λ). Therefore, d+2 o(n). the proof size is ℓ(λ) = λ

$$ \mathsf{S a m p}_{\mathcal{L}} $$

$$ \lambda, $$

$$ |{\mathsf{x}}|={\mathsf{p o l y}}(\lambda) $$

$$ |\mathsf{w}|=\mathsf{p o l y}(\lambda) $$

$$ \ell(\lambda)=\lambda^{\mathrm{o}\left(n^{d+2}\right)} $$

λ Let us fix some arbitrary oracle input (1*,crs,i). Let X^λ,ibe the distribution of x that we get from sampling λ¯λ (x,w) ← Samp_L(1,i) and Xλ,ithe distribution of ¯x we get by sampling ¯x ← SampL¯(1,i). As we established, n+2 n+2 λ λ these distributions are (2,1/2)-iⁿdistinguishable. Let A^λ,i,crsbe the augmented distribution of X^λ,i λ¯ ¯ defined as (x,π*) ← Emul(1*,crs,i). By lemma 9, there exists an augmented distribution Aλ,i,_crsof X_λ,isuch that A and A¯ are (poly(λ),negl(λ))-indistinguishable. _λ,i,crs λ,*i,crs

$$ (1^{\lambda},\mathsf{c r s},\mathfrak{i}) $$

$$ X_{\lambda,i} $$

$$ \bar{X}_{\lambda,i} $$

$$ (\mathsf{x},\mathsf{w})\leftarrow\mathsf{S a m p}_{\mathcal{L}}(1^{\lambda},\mathsf{i}) $$

$$ \bar{\mathsf{x}}\leftarrow\mathsf{S a m p}_{\bar{\mathcal{L}}}(1^{\lambda},\mathsf{i}) $$

$$ (2^{\lambda^{n+2}},1/2^{\lambda^{n+2}} $$

$$ A_{\lambda,\mathsf{i},\mathsf{c r s}} $$

$$ \bar{A}_{\lambda,\mathsf{i,c r s}} $$

$$ X_{\lambda}, $$

$$ (\mathsf{x},\pi)\gets\mathsf{E m u l}(1^{\lambda},\mathsf{c r s},\mathsf{i}) $$

$$ \bar{X}_{\lambda,i} $$

$$ A_{\lambda,\mathsf{i,c r s}} $$

$$ \bar{A}_{\lambda,\mathsf{i,c r s}} $$

$$ (p0y(\lambda) $$

∗ λ¯ Now we can describe the adversary A. On the query input (1*,crs,*i) it simply returns (¯x, π¯) ←✩ Aλ,i,crs. ¯∗ S_ince A_λ,i,crsis not necessarily efficiently sampleable, A may be inefficient.

$$ \mathcal {A} ^ {*}. \mathrm {O n} $$

$$ (\mathsf{l}^{\lambda},\mathsf{c r s},\mathsf{i}) $$

$$ \left(\bar{x},\bar{\pi}\right)\leftarrow\S;\bar{A}_{\lambda,\mathsf{i}c r s} $$

$$ \bar{A}_{\lambda,\mathsf{i},\mathsf{c r s}} $$

$$ \mathcal{A}^{*} $$

Our goal is to show that the assumption (C,c) is false if R exists, i.e.,

$$ (\mathcal{C},c) $$

$$ \operatorname*{P r}[R^{\mathsf{E m u l}}(1^{\lambda})\mathrm{}{w i n s}(\mathcal{C},c)]>c+\mathsf{n e g l}(\lambda). $$

We show this in two parts.

^{∗ A} 1) R wins (C,c).

$$ (\mathcal{C},c) $$

$$ R^{\mathcal{A}^{*}} $$

λ ∗ Firstly, let ε_A∗ (1) be the probability that A breaks adaptive soundness of Π, "

$$ \mathcal{A}^{*} $$

$$ \varepsilon_{\mathcal{A}^{*}}(1^{\lambda}) $$

$$ {\scriptstyle mathrm{I}}.{} $$

$$ \varepsilon_ {\mathcal {A} ^ {}} (\lambda) := \Pr \left[ \begin{array}{c c} \mathrm {i} \leftarrow \mathcal {I} \left(1 ^ {\lambda}\right), \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}, \mathrm {i}\right) \ (\mathrm {x}, \pi) \leftarrow \mathcal {A} ^ {} \left(1 ^ {\lambda}, \mathrm {c r s}, \mathrm {i}\right) \end{array} : (\mathrm {i}, \mathrm {x}) \notin \mathcal {L} \wedge \mathrm {V} (\mathrm {c r s}, \mathrm {x}, \pi) = 1 \right]. $$

Let us first only consider the probability of the verifier accepting a proof, "

$$ \varepsilon_{\mathsf{v f}=1}(\lambda):=\operatorname*{P r}\left[\begin{matrix}{\mathsf{i}\leftarrow\mathcal{I}(1^{\lambda}),\mathsf{c r s}\leftarrow\mathsf{S e t u p}(1^{\lambda},\mathsf{i}),}\ {(\mathsf{x},\pi)\leftarrow\mathcal{A}^{*}(1^{\lambda},\mathsf{c r s},\mathsf{i})}\\ {\mathsf{V}(\mathsf{c r s},\mathsf{x},\pi)=1}\ \end{matrix}\right]. $$

Due to completeness, we know that ε_Emul(λ) = 1, where

$$ \varepsilon_{\mathsf{E m u l}}(\lambda)=1 $$

$$ \varepsilon_{\mathsf{E m u t}}(\lambda):=\operatorname{P r}[\mathtt{i}\leftarrow\mathcal{I}(1^{\lambda}),\mathsf{c r s}\leftarrow\mathsf{S e t u p}(1^{\lambda},\mathtt{i}),(\mathtt{x},\pi)\leftarrow\mathsf{E m u l}(1^{\lambda},\mathsf{c r s},\mathtt{i}):\mathsf{V}(\mathsf{c r s},\mathtt{x},\pi)=1]. $$

Since V can be seen as a polynomial size distinguisher for A and A¯_, we get from before that λ,i,crs λ,i,crs λ λ |ε_Emul(λ)−ε_Vf=1(λ)|≤ negl(λ). Therefore, 1*−negl(λ) ≤ ε_Vf=1. Since Pr[i ←I(1),crs ← Setup(1,i),(x,π*) ← ∗ ^∗ A (crs*,i) : (i,x) ̸∈ L] = 1, ε_A∗* = ε_Vf=1≥ 1 − negl(λ). Thus, A breaks adaptive soundness with an overwhelming probability. Since we assumed a black-box reduction R, there must exist a polynomial p(·, ·) ∗ A λ such that R (1) breaks (C,c) with probability at least p(1 − negl(λ),1/λ).

$$ A_{\lambda,\mathsf{i,c r s}} $$

$$ \bar{A}_{\lambda,\mathsf{i,c r s}} $$

$$ |\varepsilon_{E m u l}(\lambda)-\varepsilon_{V f=1}(\lambda)|\leq n e g g(\lambda) $$

$$ \mathcal{A}^{}({\sf c r s},{\sf i})\ :\ ({\sf i},{\sf x})\ \not\in\ \mathcal{L}]\ =\ 1,\ \varepsilon_{\mathcal{A}^{}}\ =\ \varepsilon_{{\sf v f}=1}\ \geq\ 1\ -\ {\sf n e g l}(\lambda_{\cdot}^{\cdot} $$

$$ \Pr [ \mathrm {i} \leftarrow \mathcal {I} \left(1 ^ {\lambda}\right), \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}, \mathrm {i}\right), (\mathrm {x}, \pi) \leftarrow $$

$$ \mathcal{A}^{*} $$

$$ R^{\mathcal{A}^{*}}(1^{\lambda}) $$

$$ p\big(1-\mathsf{n e g l}(\lambda),1/\lambda\big) $$

$$ (mathcal C c c) $$

$$ p(\cdot,\cdot) $$

$$ R^{\mathcal{A}^{*}} $$

∗ A Emul 2) R is indistinguishable from R.

$$ R^{\mathsf{E m u l}} $$

Let q be the number of queries that R makes to its oracle. Let O_ifor i ∈{0,...,q(λ)} denote a stateful algorithm that we describe in the following. The machine O_ifor the first i queries responds as Emul and λ ∗ ∗ for the rest of the queries (1*,crs,*i) responds as A (see fig. 9). In particular O₀ = A and O_q(λ)= Emul.

$$ \mathsf{O}_{i} $$

$$ R $$

$$ q $$

$$ i\in{0,\ldots,q(\lambda)} $$

$$ \Theta_{i} $$

$$ (1^{\lambda},\mathsf{c r s,i}) $$

$$ \mathcal{A}^{*} $$

$$ 0_{0}=\mathcal{A}^{*} $$

$$ \mathsf{O}_{q(\lambda)}=\mathsf{E m u l} $$

Oi λ¯ We denote ε_i:= Pr[R (1) wⁱns (C,c)]. We can again use indistinguishability of A_λ,i,crsand A_λ,i,crsto show that |ε_i− ε_i+1|≤ negl(λ). Therefore, by triangle inequality |ε₀ − ε_q(λ)|≤ q(λ)negl(λ) = negl(λ).

$$ \varepsilon_{i}:=\operatorname*{P r}[R^{0_{i}}(1^{\lambda}) $$

$$ A_{\lambda,\mathsf{i,c r s}} $$

$$ (\mathcal{C},c) $$

$$ \bar{A}_{\lambda,\mathsf{i,c r s}} $$

$$ \left\vert{\varepsilon_{i}-\varepsilon_{i+1}}\right\vert\leq\ \mathsf{n e g l}(\lambda) $$

$$ |\varepsilon_{0}-\varepsilon_{q(\lambda)}|\leq q(\lambda)n e g l(\lambda)=n e g l(\lambda) $$

Emul λ Since ε₀ = ε_A, we get that Pr[R (1) wins (C,c)] = ε_q(λ)≥ ϵ_A−negl(λ) = p(1−negl(λ),1/λ)*−*negl(λ). Emul λ Thus, R (1) can break the assumption (C,c) with an overwhelming probability. ⊓⊔

$$ \varepsilon_{0}=\varepsilon_{\mathcal{A}} $$

$$ (\mathcal{C},c)]=\varepsilon_{q(\lambda)}\geq\epsilon_{\mathcal{A}}\mathrm{-}\mathsf{n e g l}(\lambda)=p(\ \ {\mathsf{1}}\mathrm{-}\mathsf{n e g l}(\lambda),\ /\lambda)\mathrm{-}\mathsf{n e g l}(\lambda). $$

$$ \operatorname*{P r}[R^{\mathsf m m u!((1^{{lambda}})}) $$

$$ R^{\mathsf{E m u l}}(1^{\lambda}) $$

6 Understanding SNARG Impossibilities

In this section, we provide a view of known impossibilities in literature for non-interactive arguments in an attempt to provide a complete picture. This illustrates the precise assumptions behind these impossibilities in order to identify avenues for further research. The following are some of the major impossibility results.

1.Gentry-Wichs [GW11]: Adaptive soundness of a SNARG cannot be proven via a black-box reduction to a falsifiable assumption.

2.Pass [Pas13]: Adaptive soundness of a statistical NIZK argument cannot be proven via a black-box reduction to a falsifiable assumption.

3.Groth [Gro16]: Any pairing-based SNARK obtained from a NILP (a non-interactive linear proof) must contain at least 2 group elements, one in each of the pairing source groups.

Since [Gro16] is relevant only in a very specific setting, and [Pas13] is about general NIZKs, we will not focus on it in the rest of the paper. We recall the proof idea of [Pas13] in Appendix E and the proof idea of [GW11] in Appendix D. In the following, we discuss the impossibility result of [GW11] and then outline the landscape of positive and negative results in Table 1.

6.1 Impossibility of Gentry-Wichs

We recall the main result of [GW11].

Theorem 7. Let L be a sub-exponentially hard NP language and let Π be a SNARG for L, satisfying completeness and succinctness properties. Then, for any falsifiable assumption (C,c), either (C,c) is false, or there is no black-box reduction showing the (adaptive) soundness of Π based on (C,c).

$$ (\mathcal{C},c) $$

$$ (\mathcal{C},c) $$

$$ (mathcal C c c) $$

Understanding Gentry-Wichs impossibility. We now look closely at the assumptions behind the Gentry-Wichs impossibility and enumerate the scenarios to which it does not apply. While some of these are known results, they are all scattered in literature. Here, we provide a comprehensive view of the applicability of Gentry-Wichs.

–Non-adaptive soundness: The impossibility holds only for adaptive soundness. The proof technique used in GW to rule out a black-box reduction uses a stateless adversary that outputs an instance proof pair (x,π) in input a CRS. In particular, this does not rule our reductions that can rewind the prover and obtain different proofs for the same x and CRS, which is possible in the case of non-adaptive soundness. If we are able to fully base iO on falsifiable assumption, this impossibility is indeed tight [SW14] Recent work attempted to show tightness from new albeit falsifiable assumptions rather than iO [LP21], but have recently been shown to have flaws in their security proof [WW22].

$$ (x,\pi) $$

–Low-space non-deterministic computation: The high-level idea of the GW impossibility result is a ℓ “leakage lemma” that says the following: assuming the underlying NP language is 2-hard, a reduction that breaks the assumption, cannot distinguish between pairs (x,π) generated by a (possibly inefficient) cheating prover, where x ̸∈ L and π is a proof of length ℓ, and a pair (˜x, π˜) where ˜x ∈ L and ˜π is an efficiently generated proof. Therefore, for computations in NTISP(poly(n),S(n)), the GW result does not rule out the possibility of a SNARG with proofs of length poly(λ)(S(n)), since a computation in NTISP(poly(n),S(n)) S(n) O(S(n)) + is in DTIME(poly⁽n⁾ · 2) which is not poly⁽n) · 2-hard. The work of [BKK 18] construct a delegation scheme for non-deterministic computations with proof length that grows only with the space of the computation.

$$ (x,\pi) $$

$$ x\not\in L $$

$$ \ell, $$

$$ (\tilde{x},\tilde{\pi}, $$

$$ \pi $$

$$ \tilde{x}\in L $$

$$ \tilde{\pi} $$

$$ N T I S P(\mathfrak{p o l y}(n),S(n)) $$

$$ N T I S P(\mathsf{p o l y}(n),S(n)) $$

$$ \vee(\lambda)(S(n)) $$

$$ D T I M E(\mathfrak{p o l y}(n)!\cdot!2^{S(n)}) $$

$$ {\mathsf{p o l y}}(n)\cdot2^{O(S(n))} $$

$$ [\mathrm{B K K^{+}18}] $$

–Preprocessing SNARGs: The GW separation result holds for SNARGs that have a “short” CRS. More precisely, the impossibility proof requires that the size of the CRS depends only on the security parameter, and not grow with the size of the instance. Preprocessing SNARGs do not satisfy this condition: the preprocessing phase depends on the instance (the circuit) and produces a CRS that is as long as the size of the circuit¹⁷. In Section 5, we extend the original GW result to the preprocessing setting.

–Trapdoor languages: Groth-Sahai techniques have been used to construct NIZKs for algebraic relations. For a subset of the languages supported by Groth-Sahai, there are efficient proofs [JR13, LPJY14] in the quasi-adaptive setting (QA-NIZK). These proofs have a constant number group elements – regardless of the number of equations or the number of variables. The construction of [KW15] for languages consisting of linear subspaces of a vector space, have constant sized proofs, achieve adaptive soundness (based on a falsifiable assumption) and perfect zero-knowledge. This is seemingly contradicting the GW impossibility 18 result (as well as the impossibility on perfect zero-knowledge in [Pas13]). We note that these results in the quasi-adaptive setting do not contradict the GW impossibility because the CRS hides a trapdoor that allows deciding membership in the language. The proof of GW rules out reductions that cannot efficiently detect when the soundness property is broken. We formalize this notion of trapdoor languages for which the impossibility results in [GW11] and [Pas13] do not apply.

6.2 Bypassing GW: Trapdoor Languages

At a high level, a trapdoor language allows verifying membership in the language if one knows a certain trapdoor, and the impossibility proof of GW will not go through if the reduction can check membership efficiently. Towards formalizing such languages, we illustrate this by taking the linear subspace language as an example. We begin by recalling the language of linear subspaces from [KW15]. We have a distribution n×m D that outputs a language parameter lpar = [M]₁∈ G₁aⁿd the respective linear subspace language is defined as n m L = {[⃗x] ∈ G |∃w⃗ ∈ Z : ⃗x = M · w⃗}.

$$ =[M]{1}\in\mathbb{G}{1}^{n\times m} $$

$$ \mathcal{L}{[M]{1}}={[\vec{x}]{1}\in\mathbb{G}{1}^{n};\big|;\exists\vec{\mathsf{w}}\in\mathbb{Z}_{p}^{m}:\vec{x}=M\cdot\vec{\mathsf{w}}}. $$

It is essential in the proof of [GW11] that the reduction algorithm R that picks the CRS, (and in case of the linear subspace language, also picks the language parameter lpar), cannot efficiently distinguish elements x ∈L from x ∈ L. The latter condition, however, does not hold for linear subspace languages. In particular, we now argue that it is possible to efficiently decide if [⃗x]¹∈L^[M]1by knowing M.

$$ x\in\mathcal{L} $$

$$ {\overline{{\mathbb X}}}\in{\overline{{\mathbb L}}} $$

$$ [ \vec {x} ] _ {1} \in \mathcal {L} _ {[ M ] _ {1}} $$

m Observe that given both M and ⃗x as integers, by Kronecker–Capelli theorem there exists ⃗w ∈ Z_psuch that ⃗x = M⃗w (i.e., [⃗x]¹∈L^[M]1) if and only if rank(M) = rank(M | ⃗x). Turns out a similar test can be used even when given only [x]₁and M, but some extra care needs to be taken to compute rank(M | ⃗x). Firstly, ′ ′ d consider a submatrix A = (M | x) ∈ Zp×^dof (M | ⃗x) which includes the last column ⃗x. By using Laplace Pd i+d ′i expansion, we are able to compute [det(A)]₁=_i=1(*−*1) [x]₁D_i,_dwhere D_i,dis a determinant of the submatrix that we get by removing i-th row and d-th column from A. We still do not know det(A), but by comparing [det(A)]₁to [0]₁, we can tell if A is a singular or a non-singular matrix. Considering that rank of a matrix is the largest order of any of its non-zero minors, we obtain the algorithm in fig. 10 for deciding elements of L^[M]1.

$$ \vec{w}\in\mathbb{Z}_{p}^{m} $$

$$ \vec{x}=M\vec{w};(\mathrm{i.e.},[\vec{x}]{1}\in\mathcal{L}{[M]_{1}}) $$

$$ (M)=\mathsf{r a n k}(M\mid\vec{x}) $$

$$ [x]_{1} $$

$$ \overset{\cdot}{A}=\left(M^{\prime};\middle|;x^{\prime}\right)\in\mathbb{Z}_{p}^{d\times d} $$

$$ \vec{x}. $$

$$ (M\mid\vec{x}) $$

$$ \operatorname{{t e t}(A)]{1}=\textstyle\sum{i=1}^{d}(-1)^{i+d}[x_{i}^{\prime}]{1}D{i,d}} $$

$$ D_{i,d} $$

$$ \mathcal{L}{[M]{1}} $$

In more detail, we first compute rank r of M, which can be done efficiently. The rank of (M | ⃗x) can be at most r + 1 since it includes only one extra column. To test this, we iterate over all the (r + 1) × (r + 1) submatrices A of (M | ⃗x) that contain the ⃗x column and compute [det(A)]₁. If one of the determinants is non-zero, then rank(M | ⃗x) = r + 1 and it follows that [⃗x]¹̸∈L^[M]1. Otherwise, rank(M | ⃗x) = r = rank(M) and [⃗x]₁∈L_[M]1. In order for D_L[M]1to be efficient, we assume that n and m are small constants.

$$ (M\mid\vec{x}) $$

$$ (M\mid\vec{x}) $$

$$ (r+1)\times(r+1) $$

$$ {\left[\operatorname*{d e t}(A)\right]}. $$

$$ \vec{x} $$

$$ (M\mid{\vec{x}})=r+1 $$

$$ [\vec{x}]{1}\notin\mathcal{L}{[M]_{1}} $$

$$ [ \vec {x} ] _ {1} \in \mathcal {L} _ {[ M ] _ {1}} $$

$$ \ M\mid{\vec{x}})=r={\mathsf{r a n k}}(M) $$

$$ \mathcal{D}{\mathcal{L}{[M]_{1}}} $$

As we saw above, the linear subspace language has a trapdoor M which allows to efficiently recognize language elements and this sufficient to avoid the [GW11] impossibility. We now generalize this observation by defining a trapdoor language.

¹⁷ The verifier does not need this long CRS, a short verification CRS suffices.

¹⁸ The proof of [KW15] contains 1 group element and bypasses the [Gro16] impossibility as well. This is not contradictory because the [Gro16] impossibility only applies to pairing-based NIZKs that are compiled from NILPs

D_L[M]1(M,[⃗x]₁) r ← rank(M); ′ ′ (r+1)×(r+1) for A = (M | ⃗x) ∈ Z_psubmat^rix of ⁽M | ⃗x) Xd i+d ′i [det(A)]1 ← (*−*1) [x]1Dⁱ,^d; i=1 if [det(A)]1 ̸= [0]1 : return false; return true;

Fig. 10: Efficient decision algorithm for L_[M]1, given access to trapdoor M

$$ \mathcal{L}{[M]{1}} $$

λ Definition 10. Let D(1) be an efficiently sampleable distribution that outputs (lpar*,td) and each lpar is associated with a language Llpar. We say that {Llpar}(lpar,td)∈D(1λ*),λ∈Nis a family of trapdoor languages if λ there exists a PPT decider M such that for all λ ∈ N and all (lpar*,td) ∈D(1),*

$$ \mathcal{D}(1^{\lambda}) $$

$$ \mathcal{L}_{\mathsf{l p a r}} $$

$$ {\mathcal{L}{\ \ mathsf{|p p r}}_{\ \mathsf{|p a r,t d)\in\ {\mathcal{D}}(1^{\lambda}),\lambda\in\mathbb{N}}}} $$

$$ \lambda\in\mathbb{N} $$

$$ (\mathsf{I p a r},\mathsf{t d})\in\mathcal{D}(1^{\lambda}) $$

$$ \mathsf{x}\in\mathcal{L}\Leftrightarrow\mathcal{M}(1^{\lambda},|\mathsf{p a r},\mathsf{t d},\mathsf{x})=1. $$

The security definitions from section 5.1 for non-interactive arguments slightly change in that the Setup additionally takes the language parameter as input and outputs a CRS.

The soundness definition in general is not efficiently falsifiable because checking x ̸∈ L is usually not efficient. However, with trapdoor languages it is falsifiable since M is efficient. In particular, this means that even a tautological assumption “Π is sound” becomes a falsifiable assumption.

$$ \ \ \ \ times
$$

Examples of useful trapdoor languages. In general, we are interested in “hard” trapdoor languages, that is, trapdoor languages that are hard to decide without knowledge of td. We illustrate a few examples below.

– Linear subspace language. Firstly, let us observe that the linear subspace languages fits into the trapdoor λ language definition. We let D(1) pick a pairing description bp and sample a matrix M according to λ some distribution. D(1) outputs lpar = (bp*,* [M]¹) and td = M. Deciding if x ∈L^[M]1can be decided efficiently given td as we argued before. For many distributions of M, L_[M]1is considered to be a hard ⊤ language on average. For example, if M = (1*,x*) and x,w ←✩ Z_p, then [Mw]₁= (w, wx), which is ⊤ indistinguishable from a random tuple [u,v]₁←✩ G²₁under the decisional Diffie-Hellman assumption. More generally, hardness of such distributions is characterized by the matrix decisional Diffie-Hellman + (MDDH) assumption [EHK 13].

$$ \mathcal{D}(1^{\lambda}) $$

$$ =(\mathsf{b}\mathsf{p},[M]_{1}) $$

$$ \mathcal{D}(1^{\lambda}) $$

$$ \mathsf{t}\mathsf{d}=M $$

$$ \ \mathsf{X}\in\ {\mathcal{L}}{[M]{1}} $$

$$ \mathcal{L}{[M]{1}} $$

$$ M,=,(1,x)^{\top} $$

$$ x, \mathrm {w} \leftarrow $ \mathbb {Z} _ {p}, $$

$$ [M\mathsf{w}]_{1},=,(\mathsf{w},\mathsf{w}x boldsymbol{} $$

$$ [u,v]{1}^{\top}\leftarrow\S\ \mathbb{G}{1}^{2} $$

– Statements about encrypted values. Many statements about ciphertexts can be naturally formalized as a trapdoor language by using the public key as lpar and the secret key as td. Consider the following example.

ℓ Let (KGen*,Enc,Dec) be a public key cryptosystem for encrypting ℓ-bit messages and let C : {0,1} → λ λ {0,1} be an efficiently computable boolean circuit. We set D(1) = KGen(1), that is lpar = pk is the C public key and td = sk is the corresponding secret. We define the language as L_pk= {c | C(Dec(sk,c*)) = C 1*}.* In other words, L^pkcontains ciphertexts that encrypt a message m which satisfy some property characterized by the circuit C. For example, in range proofs we have C which checks that k₁ ≤ m ≤ k₂ C for some constants k₁ and k₂. Clearly, L^pkis a trapdoor language since given sk it is possible to decrypt c and efficiently check that the plaintext satisfies C.

$$ C:{0,1}^{\ell}\rightarrow $$

$$ {\mathcal{D}}(1^{\lambda})={\mathsf{K G e n}}(1^{\lambda}) $$

$$ \cdot={\mathfrak{p k}} $$

$$ \mathcal{L}_{\mathfrak{p}\mathbf{k}}^{C} $$

$$ \mathcal{L}_{\mathsf{p k}}^{C}={c\mid C(\mathsf{D e c}(\mathsf{s k},c))= $$

$$ k_{1}\leq m\leq k_{2} $$

$$ k_{1} $$

$$ k_{2} $$

$$ \mathcal{L}_{\ {mathfrak p p k}^{C}} $$

– Shuffle. Popular ciphertext-based language that fits into the trapdoor language mould is the ciphertext shuffle. We set D = KGen. Let Σ_nbe the set of permutations on n elements. The shuffle language for n

$$ {\mathcal{D}}={\mathsf{K G e n}} $$

$$ \Sigma_{n} $$ ciphertexts is

$$ \begin{array}{l} \mathcal {L} _ {\mathrm {p k}} ^ {n - s h u f} = \left{\left(\left(c _ {1}, \dots , c _ {n}\right), \left(c _ {1} ^ {\prime}, \dots , c _ {n} ^ {\prime}\right)\right) \mid \right. \ \exists \sigma \in \Sigma_ {n} \forall i \in {1, \dots , n }: \operatorname {D e c} (\mathrm {s k}, c _ {i}) = \operatorname {D e c} (\mathrm {s k}, c _ {\sigma (i)} ^ {\prime}) } \ \end{array} $$

With the secret key as the trapdoor, statements are easy to verify since one can decrypt both ciphertext vectors, sort the resulting plaintext vectors, and then check their equality. Shuffle proofs are often used to prove correct behaviour of mix-networks, which have for instance found application in e-voting systems to anonymize ciphertexts of voters [SK95].

– Set membership. Let us consider a public set S and a public key cryptosystem. A set membership language S for S is defined as L^pk= {c : Dec(sk*,c*) ∈ S}. This is clearly a trapdoor language where again sk plays the role of a trapdoor. Gonz´alez and R´afols [GR16] show that an argument for this language (and its aggregated version for multiple ciphertexts) can be used to obtain, for example, shuffle arguments and range arguments. Of course, there are also more direct application like showing that c encrypts a valid candidate in an e-voting system, where S is the set of all candidates.

$$ \mathcal{L}_{\mathfrak{p k}}^{S}=\left{c:\mathsf{D e c}(\mathsf{s k},c)\in\mathcal{S}\right} $$

We note that trapdoor languages are interesting, arise frequently in practice and GW impossibility does not apply. Can we construct SNARGs from falsifiable assumptions for trapdoor languages? We leave resolving this as an interesting open question, and believe that our formalization is a first step in identifying the middle ground where GW does not apply but the language remains interesting.

6.3 A Complete Picture

In Table 1, we give an overview of the impossibility results for non-interactive arguments, and positive results known under various relaxations. As already highlighted above, there are two major impossibility results. Firstly, there is no adaptively sound succinct argument for all non-deterministic computations with a black-box reduction to a falsifiable assumption [GW11]. This holds even with a designated verifier (a verifier that holds a private verification key). Secondly, there is no statistical zero-knowledge argument (succinct or not) for all non-deterministic computations with a black-box reduction to a falsifiable assumption [Pas13]. Although not mentioned in the original paper, this impossibility result also extends to the designated verifier. 19

On the other hand, by relaxing some of the requirements, it is possible to achieve succinct arguments and also statistical zero-knowledge arguments. Delegation schemes are adaptively sound succinct arguments for deterministic computation and they are achievable under falsifiable pairing-based and lattice-based assumptions as was shown by [CJJ21b, GZ21, KPY19]. Recently Lipmaa and Pavlyk [LP21] showed that non-adaptivity is another possible relaxation. They construct a non-adaptively sound SNARG for nondeterministic computation that has perfect zero-knowledge based on a new, but falsifiable assumption. A non-adaptively sound SNARG under a falsifiable assumption was known even prior to [LP21]. Namely, Sahai and Waters [SW14] constructed a succinct perfect NIZK argument with non-adaptive soundness from iO. Subsequent to their work, constructions of iO have been proposed which are secure under falsifiable assumption, e.g. [WW21b]. We give a brief overview of this SNARG construction in Appendix F.

¹⁹ As can be seen in Appendix E, neither the inefficient soundness adversary Aslownor its emulator Afastneed to run the verifier internally and thus the same impossibility proof applies for the designated verifier setting.

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{\mathrm{}{f a s t}} $$

Table 1: (Im)possibility results for non-interactive arguments under falsifiable assumptions. BB stands for black-box. adaptive public succinct language class statistical notes/citation

Acknowledgement. We thank the reviewers of CRYPTO 2022 for constructive feedback, in particular, for pointing out the connection between black-box extractability and leakage-resilient cryptography.

References

ADVW13.Shweta Agrawal, Yevgeniy Dodis, Vinod Vaikuntanathan, and Daniel Wichs. On continual leakage of discrete log representations. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 401–420. Springer, Heidelberg, December 2013. ADW09.Jo¨el Alwen, Yevgeniy Dodis, and Daniel Wichs. Leakage-resilient public-key cryptography in the boundedretrieval model. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 36–54. Springer, Heidelberg, August 2009. All86.Eric W Allender. The complexity of sparse sets in p. In Structure in Complexity Theory, pages 1–11. Springer, 1986. ⁺ BBB 18.Benedikt B¨unz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. IEEE Computer Society Press, May 2018. BCC88.Gilles Brassard, David Chaum, and Claude Cr´epeau. Minimum disclosure proofs of knowledge. Journal of computer and system sciences, 37(2):156–189, 1988. BCCT13.Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 111–120. ACM Press, June 2013. ⁺ BCG 13.Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 90–108. Springer, Heidelberg, August 2013. ⁺ BCG 14.Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 459–474. IEEE Computer Society Press, May 2014. ⁺ BCI 13.Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct noninteractive arguments via linear interactive proofs. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 315–333. Springer, Heidelberg, March 2013. BCTV14.Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct non-interactive zero knowledge for a von neumann architecture. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, pages 781–796. USENIX Association, August 2014.

⁺ BGG 90.Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H˚astad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Shafi Goldwasser, editor, CRYPTO’88, volume 403 of LNCS, pages 37–56. Springer, Heidelberg, August 1990. BIOW20.Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu. On succinct arguments and witness encryption from groups. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 776–806. Springer, Heidelberg, August 2020. ⁺ BKK 18.Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs. Succinct delegation for low-space non-deterministic computation. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, 50th ACM STOC, pages 709–721. ACM Press, June 2018. BKSV21.Karim Baghery, Markulf Kohlweiss, Janno Siim, and Mikhail Volkhov. Another look at extraction and randomization of groth’s zk-snark. In Nikita Borisov and Claudia Diaz, editors, Financial Cryptography and Data Security, pages 457–475, Berlin, Heidelberg, 2021. Springer Berlin Heidelberg. BS21.Karim Baghery and Mahdi Sedaghat. Tiramisu: black-box simulation extractable nizks in the updatable crs model. In International Conference on Cryptology and Network Security, pages 531–551. Springer, 2021. Can01.Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136–145. IEEE Computer Society Press, October 2001. ⁺ CFF 20.Matteo Campanelli, Antonio Faonio, Dario Fiore, Ana¨ıs Querol, and Hadri´an Rodr´ıguez. Lunar: a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions. Cryptology ePrint Archive, Report 2020/1069, 2020. https://eprint.iacr.org/2020/1069. ⁺ CFH 15.Craig Costello, C´edric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur. Geppetto: Versatile verifiable computation. In 2015 IEEE Symposium on Security and Privacy, pages 253–270. IEEE Computer Society Press, May 2015. CGKS95.Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In 36th FOCS, pages 41–50. IEEE Computer Society Press, October 1995. CH20.Geoffroy Couteau and Dominik Hartmann. Shorter non-interactive zero-knowledge arguments and ZAPs for algebraic languages. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 768–798. Springer, Heidelberg, August 2020. ⁺ CHM 20.Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 738–768. Springer, Heidelberg, May 2020. CJJ21a.Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Non-interactive batch arguments for NP from standard assumptions. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 394–423, Virtual Event, August 2021. Springer, Heidelberg. CJJ21b.Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Snargs for P from lwe. Cryptology ePrint Archive, Report 2021/808, 2021. https://ia.cr/2021/808. CKLM13.Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn. Succinct malleable NIZKs and an application to compact shuffles. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 100–119. Springer, Heidelberg, March 2013. Dam92.Ivan Damg˚ard. Towards practical public key systems secure against chosen ciphertext attacks. In Joan Feigenbaum, editor, CRYPTO’91, volume 576 of LNCS, pages 445–456. Springer, Heidelberg, August 1992. ⁺ EHK 13.Alex Escala, Gottfried Herold, Eike Kiltz, Carla R`afols, and Jorge Villar. An algebraic framework for Diffie-Hellman assumptions. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 129–147. Springer, Heidelberg, August 2013. For87.Lance Fortnow. The complexity of perfect zero-knowledge (extended abstract). In Alfred Aho, editor, 19th ACM STOC, pages 204–209. ACM Press, May 1987. FS87.Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages 186–194. Springer, Heidelberg, August 1987. GGPR13.Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 626–645. Springer, Heidelberg, May 2013. GH98.Oded Goldreich and Johan H˚astad. On the complexity of interactive proofs with bounded communication. Inf. Process. Lett., 67(4):205–214, 1998.

Archive, Report 2021/808, 2021. https://ia.cr/2021/808. https://ia.cr/2021/808

GJLS21.Romain Gay, Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from simpleto-state hard problems: New assumptions, new techniques, and simplification. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 97–126. Springer, 2021. GMW86.Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th FOCS, pages 174–187. IEEE Computer Society Press, October 1986. GR16.Alonso Gonz´alez and Carla R`afols. New techniques for non-interactive shuffle and range arguments. In Mark Manulis, Ahmad-Reza Sadeghi, and Steve Schneider, editors, ACNS 16, volume 9696 of LNCS, pages 427–444. Springer, Heidelberg, June 2016. Gro10.Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 321–340. Springer, Heidelberg, December 2010. Gro16.Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-S´ebastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. Springer, Heidelberg, May 2016. GVW02.Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Compu- tational Complexity, 11(1):1–53, 2002. GW11.Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99–108. ACM Press, June 2011. GWC19.Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953, 2019. https://eprint.iacr.org/2019/953. GZ21.Alonso Gonz´alez and Alexandros Zacharakis. Fully-succinct publicly verifiable delegation from constantsize assumptions. Cryptology ePrint Archive, Report 2021/353, 2021. https://eprint.iacr.org/2021/ 353. HILL99.Johan H˚Astad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, March 1999. HT98.Satoshi Hada and Toshiaki Tanaka. On the existence of 3-round zero-knowledge protocols. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 408–423. Springer, Heidelberg, August 1998. JLS21.Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 60–73, 2021. JR13.Charanjit S. Jutla and Arnab Roy. Shorter quasi-adaptive NIZK proofs for linear subspaces. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part I, volume 8269 of LNCS, pages 1–20. Springer, Heidelberg, December 2013. Kil92.Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 723–732, 1992. KKK21.Thomas Kerber, Aggelos Kiayias, and Markulf Kohlweiss. Composition with knowledge assumptions. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 364–393, Virtual Event, August 2021. Springer, Heidelberg. KPY19.Yael Tauman Kalai, Omer Paneth, and Lisa Yang. How to delegate computations publicly. In Moses Charikar and Edith Cohen, editors, 51st ACM STOC, pages 1115–1124. ACM Press, June 2019. KVZ21.Yael Tauman Kalai, Vinod Vaikuntanathan, and Rachel Yun Zhang. Somewhere statistical soundness, post-quantum security, and SNARGs. Cryptology ePrint Archive, Report 2021/788, 2021. https:// eprint.iacr.org/2021/788. KW15.Eike Kiltz and Hoeteck Wee. Quasi-adaptive NIZK for linear subspaces revisited. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 101–128. Springer, Heidelberg, April 2015. ⁺ KZM 15.Ahmed Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, Hubert Chan, Charalampos Papamanthou, Rafael Pass, abhi shelat, and Elaine Shi. C*∅C∅*: A framework for building composable zero-knowledge proofs. Cryptology ePrint Archive, Report 2015/1093, 2015. https://ia.cr/2015/1093. Lip12.Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 169–189. Springer, Heidelberg, March 2012. Lip13.Helger Lipmaa. Succinct non-interactive zero knowledge arguments from span programs and linear errorcorrecting codes. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part I, volume 8269 of LNCS, pages 41–60. Springer, Heidelberg, December 2013.

LP21.Helger Lipmaa and Kateryna Pavlyk. Gentry-wichs is tight: a falsifiable non-adaptively sound snarg. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, pages 34–64, Cham, 2021. Springer International Publishing. LPJY14.Benoˆıt Libert, Thomas Peters, Marc Joye, and Moti Yung. Non-malleability from malleability: Simulationsound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 514–532. Springer, Heidelberg, May 2014. Mic94.Silvio Micali. CS proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 436–453. IEEE, 1994. Nao03.Moni Naor. On cryptographic assumptions and challenges (invited talk). In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 96–109. Springer, Heidelberg, August 2003. Pas13.Rafael Pass. Unprovable security of perfect NIZK and non-interactive non-malleable commitments. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 334–354. Springer, Heidelberg, March 2013. PHGR13.Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238–252. IEEE Computer Society Press, May 2013. RZ21.Carla R`afols and Arantxa Zapico. An algebraic framework for universal and updatable SNARKs. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 774–804, Virtual Event, August 2021. Springer, Heidelberg. SK95.Kazue Sako and Joe Kilian. Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth. In Louis C. Guillou and Jean-Jacques Quisquater, editors, EUROCRYPT’95, volume 921 of LNCS, pages 393–403. Springer, Heidelberg, May 1995. SW14.Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC, pages 475–484. ACM Press, May / June 2014. Wee05.Hoeteck Wee. On round-efficient argument systems. In Lu´ıs Caires, Giuseppe F. Italiano, Lu´ıs Monteiro, Catuscia Palamidessi, and Moti Yung, editors, ICALP 2005, volume 3580 of LNCS, pages 140–152. Springer, Heidelberg, July 2005. WW21a.Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious lwe sampling. In Annual Interna- tional Conference on the Theory and Applications of Cryptographic Techniques, pages 127–156. Springer, 2021. WW21b.Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious LWE sampling. In Anne Canteaut and Fran¸cois-Xavier Standaert, editors, EUROCRYPT 2021, Part III, volume 12698 of LNCS, pages 127–156. Springer, Heidelberg, October 2021. WW22.Brent Waters and David J. Wu. Batch arguments for np and more from standard bilinear group assumptions. Cryptology ePrint Archive, Paper 2022/336, 2022. https://eprint.iacr.org/2022/336.

A Further Preliminaries

A.1 Non-Adaptive Soundness

We say an argument system satisfies non-adaptive soundness for a relation R if for any PPT adversary A = (A_inp, A_prf),

$$ \mathcal{A}=(\mathcal{A}{\mathrm{i n p}},\mathcal{A}{\mathrm{p r f}}) $$

$$ \Pr \left[ \begin{array}{c c} (\mathrm {x}, \mathrm {s t}) \leftarrow \mathcal {A} _ {\mathrm {i n p}} \left(1 ^ {\lambda}\right) \ (\mathrm {c r s}, \mathrm {t d}) \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}\right) : & \mathrm {V} (\mathrm {c r s}, \mathrm {x}, \pi) = 1 \ \pi \leftarrow \mathcal {A} _ {\mathrm {p r f}} (\mathrm {s t}, \mathrm {c r s}) & \wedge \forall w (\mathrm {x}, \mathrm {w}) \notin \mathcal {R} \end{array} \right] = \operatorname {n e g l} (\lambda). $$

A.2 Fully Homomorphic Encryption (FHE)

An FHE scheme consists of a tuple of algorithms (KG*,Enc,Dec,*Eval) with the following syntax:

^λ KG(1) → (pk*,*sk): generates a key pair (the algorithm is randomized).

$$ {\mathsf{K G}}(1^{\lambda})\to({\mathsf{p k}},{\mathsf{s k}}) $$

Enc(pk*,m*) → ct: produces a ciphertext corresponding to a message m through the public key (the algorithm is randomized).

$$ \mathsf{E n c}(\mathsf{p k},m)\to\mathsf{c t}\mathrm{:} $$

Dec(sk*,*ct) → m: decrypts a ciphertext through the secret key (the algorithm is deterministic).

Eval(pk*,ct_m,F*) → ct_F: produces an encryption of F (m) from an encryption of m through the public key. Occasionally we will overload this notation for functions with arity higher than 1 or that take as input plaintexts, which can be seen as dummy ciphertexts (the algorithm is deterministic).

$$ \mathsf{D e c}(\mathsf{s k},\mathsf{c t})\to $$

$$ (\mathsf{p k},\mathsf{c t}{m},F)\to\mathsf{c t}{F}; $$

$$ F(m) $$

An FHE scheme should satisfy correctness and semantic security.

Correctness. For any λ, plaintext m and function F

$$ \lambda, $$

$$ \operatorname*{P r}\left[{\mathsf{D e c}}({mathsf\mathsf s{}},{\mathsf{c t}})=m\right]=1 $$

and

$$ \operatorname*{P r}\left[\mathsf{D e c}(\mathsf{s k},\mathsf{E v a l}(\mathsf{p k},\mathsf{c t},F))=F(m)\right]=1 $$

λ where (pk*,sk) ← KG(1) and ct ← Enc(pk,m*).

$$ (\mathsf{p}\mathsf{k},\mathsf{s}\mathsf{k})\leftarrow\mathsf{K}\mathsf{G}(1^{\lambda}) $$

$$ \ {mathsf c t t}\leftarrow\ {mathsf E n n}(\mathsf{p k},m) $$

Semantic security. For all λ, for any PPT adversary A = (A¹, A²)

$$ \lambda, $$

$$ \mathcal{A}=(\mathcal{A}^{1},\mathcal{A}^{2}) $$

$$ \operatorname*{P r}\left[\begin{matrix}{(\mathsf{p k},\mathsf{s k})\leftarrow\mathsf{K G}(1^{\lambda}),(\mathsf{s t},m_{0},m_{1})\leftarrow\mathcal{A}^{1}(\mathsf{p k})}\ {b\leftrightarrow{0,1},\mathsf{c t}\leftarrow\mathsf{E n c}(m_{b}),b^{\prime}\leftarrow\mathcal{A}^{2}(\mathsf{s t},\mathsf{c t})}\ \end{matrix}\right.:;b=b^{\prime}\Bigg]=\mathsf{n e g l}(\lambda) $$

A.3 Collision-Resistant Hash Functions (CRHF)

We say that a family of function H is collision-resistant if for all λ, for all PPT adversary A " #

$$ \lambda, $$

$$ \Pr \left[ \begin{array}{c c} \mathrm {h k} \leftarrow $ \mathcal {K} _ {\lambda} \ (x, y) \leftarrow \mathcal {A} (\mathrm {h k}) & : \quad \mathrm {H} _ {\mathrm {h k}} (x) = \mathrm {H} _ {\mathrm {h k}} (y) \ & \wedge x \neq y \end{array} \right] = \operatorname {n e g l} (\lambda) $$

where K_λis the key space corresponding to parameter λ.

$$ K_{\lambda} $$

We also require the hash function to be computable in polynomial time and to satisfy a shrinkage property, ∗ that is, for every input x ∈{0,1} the output size is bounded by a fixed polynomial in λ.

$$ x\in{0,1}^{*} $$

$$ \lambda $$

B Impossibility of Adaptive BB Extraction Using LR-OWF

The impossibility shown in Theorem 2 can be interpreted as a consequence of leakage-resilience; a SNARK proof is leakage on the witness. For an NP-relation that is leakage-resilient, recovering the entire witness is impossible for an extractor even given the leakage, if this leakage is small.

Definition 11((ℓ,ε)-LR-OWF). A function family F = {f_i: D_i→ R_i} is (ℓ,ε)-LR one-way if:

$$ \mathcal{F}=\left{f_{i}:D_{i}\to R_{i}\right} $$

$$ (\ell,\varepsilon){\cdot,}L R $$

$$ i f. $$

λ – There exists efficient algorithms (i) KGen(1) to sample an index i (ii) Sample(i) for sampling an input x ←✩ D_i(iii) Eval(i,x) for computing y = f_i(x). " #

$$ x\gets\flat D_i(\stackrel{\cdot}{i i});;\mathsf{E v a l}(i,x) $$

$$ y=f_{i}(x) $$

– For any PPT A,

$$ \Pr \left[ \begin{array}{c c} i \leftarrow \mathrm {K G e n} \left(1 ^ {\lambda}\right), x \leftarrow \mathrm {S a m p l e} (i), \ y \leftarrow \mathrm {E v a l} (i, x), x ^ {\prime} \leftarrow \mathcal {A} ^ {\mathrm {O} _ {\ell} (\cdot)} (i, y) \end{array} : y = \mathrm {E v a l} \left(i, x ^ {\prime}\right) \right] \leq \varepsilon $$

∗ ℓ where O_ℓ(·) is an oracle that takes as an input a leakage function h : {0,1} →{0,1}, on which O_ℓ(h) returns h(x). Adversary can query O_ℓ(·) only once.

$$ \ mathrm O O_\ell(\cdot) $$

$$ h:{0,1}^{*}\rightarrow{0,1}^{\ell} $$

$$ \ \mathrm{O}_{\ell}(h) $$

$$ h(x) $$

λ Let F be a family of (ℓ,ε)-LR OWFs. For f ∈F, consider the relation R_F:= {((x*,i*),w) | i ∈ KGen(1), w ∈ Sample(i),x = Eval(i, w)}.

$$ \mathrm{O}_{\ell}(\cdot) $$

$$ \mathcal{R}_{\mathcal{F}}:={((\mathsf{x},i),\mathsf{w})\ |\ i\in\mathsf{K G e n}(1^{\lambda}),\mathsf{w}\in $$

$$ f\in{\mathcal{F}} $$

$$ (\ell , \varepsilon) - \mathrm {L R} $$

$$ \mathsf{p l e}(i),\mathsf{x}=\mathsf{E v a l}(i,\mathsf{w})] $$

Theorem 8. A non-interactive argument system Π for R_Fwith argument size at most ℓ bits, has black-box knowledge soundness error ε_ks≥ 1 − ε.

$$ \mathcal{R}_{\mathcal{F}} $$

$$ \varepsilon_{k s}\geq1-\varepsilon $$

Proof. By LR one-wayness of f, we have

$$ f, $$

$$ \operatorname*{P r}[i\leftarrow\mathsf{K G e n}(1^{\lambda}),\mathsf{x}\leftarrow\ \vdash D_{i},\mathsf{w}\leftarrow\mathcal{A}^{\mathsf{O}{\ell}(\cdot)}(1^{\lambda},\mathsf{x}):\left((\mathsf{x},i),\mathsf{w}\right)\in\mathcal{R}{\mathcal{F}}]\leq\varepsilon. $$

Consider an argument system Π for R_Fwith argument size bounded by ℓ bits. Let Ext be the black-box Oℓ(·) extractor guaranteed by Π. We construct an adversary A that breaks the ℓ-leakage resilience of f. A receives as challenge x, picks a crs together with an extraction key td, sets h(X) := P(crs*,* x*,X*), and receives π ← O_ℓ(h) = P(crs*,* x*,w). It then invokes the black-box witness extractor Ext(crs,td,* x*,π*) to receive w, and returns w as preimage. Assuming perfect correctness, we have that A succeeds in breaking one-wayness of f with the probability that the extractor succeeds. Pr[A succeeds ] ≥ 1 − ε_ks(λ). Thus, ε_ks≥ 1 − ε. ⊓⊔

$$ \mathcal{R}_{\mathcal{F}} $$

$$ \mathcal{A}^{\mathsf{O}_{\ell}}(\cdot) $$

$$ h(X):=\mathsf{P}(\mathsf{c r s},\mathsf{x},X) $$

$$ \mathsf{E x t}(\mathsf{c r s},\mathsf{t d},\mathsf{x},\pi) $$

$$ \pi\leftarrow\ {mathsf0}_{\ell}(h)={\mathsf P}({\mathsf{c r s}},{\mathsf X},{\mathsf W}) $$

$$ w, $$

$$ \mathrm{P r}[{\mathcal{A}} $$

$$ ]\geq1-\varepsilon_{k s}(\lambda) $$

$$ \varepsilon_{k s}\geq1-\varepsilon $$

ℓ Since an adversary can always guess the correct leakage with probability 1*/2, all OWFs are LR with ℓ = O(log|w|*). We therefore obtain as a corollary, that an argument for R_Fmust be at least of logarithmic size.

$$ 1/2^{\ell} $$

$$ \ell=O{\bigl(}\log|\mathsf{w}|\bigr) $$

$$ \mathcal{R}_{\mathcal{F}} $$

Corollary 1. Assuming the existence of OWFs, a SNARK with negligible black-box knowledge soundness error must have argument size at least Ω(log*|w|).*

With concrete LR-OWFs even better lower bounds can be achieved. Consider for example the discrete logarithm based (C)LR-OWF from Theorem 1. We obtain the following result.

Corollary 2. If the discrete logarithm assumption holds, then there exist a LR-OWF family F such that any non-interactive black-box knowledge sound argument for the relation R_Fmust have size Ω(|w|).

$$ \mathcal{R}_{\mathcal{F}} $$

$$ \varOmega(|\boldsymbol{w}|) $$

The latter also shows that black-box extractable SNARKs for all NP do not exist.

C Non-Adaptive BB Extractable SNARK for UP

In Figure 11 we show a slightly simpler version of the construction in Figure 2. The following constructs a SNARK for a language in UP (restriction of NP where a statement in the language has exactly one accepting witness). In this variant, we do not need hashing to fingerprint the witnesses. Our SNARK works as follows.

λ Setup(1) ˆ)^λ (crsˆ*,td ← Π∃.Setup(1) ^∗ i ←✩ [Nw] λ (pk_FHE,sk_FHE) ← FHE.KG(1) ∗ cti∗ ← FHE.Enc(pk,i*)

return (crs := (crsˆ*,ct,pk),td := (sk,*tdˆ)) i∗ FHE FHE

P(crs*,* R*,* x*,*w)

ctbit*←* _FHE.Eval(pkFHE,fproj*,cti∗,*w)

where fproj(i,w) := wi

′ π ← Π∃.P(crsˆ, R*,(x,pk_FHE,cti∗,ctbit),w) ′ where R (x,pk_FHE,cti∗,ctbit; w) ⇐⇒ R(x,w) ∧ ctbit= _FHE.Eval(pkFHE,fproj,cti∗,*w) ∗ return π := (π, ct)

bit ∗ V(crs*,* R*,* x*,π*) ^∗

Parse π as (π, ctbit) ′ return Π∃.V crsˆ, R*,(x,pk_FHE,cti∗,*ctbit) ′ where R is defined like above

$$ (\hat {\mathrm {c r s}}, \hat {\mathrm {t d}}) \leftarrow \Pi_ {\exists}. \operatorname {S e t u p} \left(1 ^ {\lambda}\right) $$

$$ \ {{i}}^{*}\gets!\left[N_{w}\right] $$

$$ (\mathsf{p k}{\mathrm{F H E}},\mathsf{s k}{\mathrm{F H E}})\leftarrow\mathsf{F H E.K G(1}^{\lambda}) $$

$$ \mathsf{c t}_{i^{}}\leftarrow\mathsf{F H E.E n c}(\mathsf{p k},i^{}) $$

$$ \mathbf {r e t u r n} \left(\mathrm {c r s}: = \left(\hat {\mathrm {c r s}}, \mathrm {c t} _ {i ^ {*}}, \mathrm {p k} _ {\mathrm {F H E}}\right), \mathrm {t d}: = \left(\mathrm {s k} _ {\mathrm {F H E}}, \hat {\mathrm {t d}}\right)\right) $$

$$ f_{\mathrm{p r o j}}(i,w):=w_{i} $$

$$ R ^ {\prime} \left(x, p k _ {\mathrm {F H E}}, c t _ {i ^ {*}}, c t _ {\mathrm {b i t}}; w\right) \Longleftrightarrow $$

$$ \pi^{*}:=(\pi,\mathsf{c t}_{\mathrm{b i t}}) $$

$$ \pi^{*} $$

$$ \left(\pi,\mathsf{c t}_{\mathrm{b i t}}\right) $$

$$ \mathit{\Pi}{\exists}.\mathsf{V}\left(\mathsf{c f s},\mathsf{R}^{\prime},(\mathsf{x},\mathsf{p k}{\mathtt{F H E}},\mathsf{c t}{i^{*}},\mathsf{c t}{\operatorname{b i t}})\right) $$

Fig. 11: Non-adaptively secure black-box extractable construction for UP. N_wis a bound on the witness size. Π_∃is the SNARG scheme.

$$ N_{w} $$

$$ \mathcal{A}_{f a s t}\ !{\big(}\mathsf{c r s}\ \ ) $$

$$ \mathcal{A}_{s l o w}(\mathsf{c r s}) $$

$$ (\mathsf{x},\mathsf{w})\leftarrow\mathsf{S a m p}_{\mathcal{L}}; $$

$$ \mathsf{c r s}\in\operatorname{i m g}(\mathsf{S e t u p}) $$

$$ \pi\leftarrow\mathbf{P}(\mathsf{c r s},\mathsf{x},\mathsf{w}); $$

$$ (\mathbf,\pi)\colon $$

$$ \mathsf{x}\leftarrow\mathsf{S a m p}_{\bar{\mathcal{L}}}; $$

$$ \pi\leftarrow\mathcal{S}(\mathsf{c r s},\mathsf{t d},\mathsf{x}); $$

$$ (\mathsf{x},\mathsf{w})\leftarrow\mathsf{S a m p}_{\mathcal{L}}; $$

$$ \pi\leftarrow\mathbf{P}(\mathsf{c r s},\mathsf{x},\pi); $$

Fig. 12: Inefficient adversary A_slowagainst adaptive soundness and its efficient emulator A_fast

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{f a s t} $$

D A Summary of the GW Impossibility Proof [GW11]

The main technique used in the proof is showing the existence of a simulatable adversary P for any SNARG for an NP complete language. A simulatable adversary is an inefficient adversary that, given a CRS, outputs a false statement x ̸∈L with a valid proof π for it. While the existence of such adversary is trivial for any SNARG, a simulatable adversary also comes with an efficient simulator S such that no efficient distinguisher can distinguish them. To show the existence of a simulatable adversary, a lemma in [GW11] shows that for any two computationally indistinguishable distributions respectively over a set L and its complement ∗ L = {0,1} \L, and for any leakage information π on x ∈L, there exists some leakage information π on x ∈ L such that (x*,π*) and (x*, π*) are also computationally indistinguishable. What is important in this lemma is that the security degrades exponentially with the size of the leakage π and this is the reason why the underlying SNARG Π should have succinctness property.

$$ \overline{{\overline{{\rho}}}} $$

$$ \pi $$

$$ \times\not\in\mathcal{L} $$

$$ \mathbb{S N A R G}, $$

$$ \mathcal{S} $$

$$ \mathcal{L} $$

$$ \overline{{\mathcal{L}}}={0,1}^{*}\backslash\mathcal{L} $$

$$ x\in\mathcal{L} $$

$$ \overline{{\pi}} $$

$$ {\overline{{\ X}}}\in{\overline{{\cal L}}} $$

$$ (\mathsf{x},\pi) $$

$$ (\overline{{\mathbf{x}}},\overline{{\pi}}) $$

Now, given this simulatable adversary, the result can be concluded as follows. Assume there exists a black-box reduction R that shows the soundness of π based on (C,c). This means that the efficient reduction P ^P R, given black-box access to successful adversary P can break (C,c). But if (inefficient) R can break (C,c), S then (efficient) R can also break it since no efficient distinguisher (including the challenger of (C,c)) can distinguish P from S. Thus, if this black-box reduction exists, then the assumption (C,c) should be false.

$$ R^{\overline{{\mathbf{P}}}} $$

$$ (\mathcal{C},c) $$

$$ \overline{{\mathbf{P}}} $$

$$ R^{\overline{{\mathbf{P}}}} $$

$$ (mathcal C c c) $$

$$ (mathcal C c c) $$

$$ R^{s} $$

$$ (\mathcal{C},c)) $$

$$ \overline{{\mathbf{P}}} $$

E A Summary of the Pass Impossibility Proof [Pas13]

We briefly summarize the impossibility result of [Pas13]. Let L be a hard-on-average language as defined in section 2. Now we can give an informal statement for the result in [Pas13].

Theorem 9. Let Π be an adaptively sound and perfectly zero-knowledge non-interactive argument for an hard-on-average problem L. Suppose that there exists an efficient black-box reduction R that can reduce adaptive soundness of Π to some falsifiable assumption C. Then C can be broken in polynomial time.

The intuition behind the result is as follows. First, we construct an inefficient adversary A_slow(the first algorithm in fig. 12) that can break adaptive soundness. If A_slowgets a valid CRS as an input (crs is in the image of Setup), then it brute-force computes a trapdoor td, samples a false statement x, and runs the simulator with td to produce a proof π. If the CRS is invalid (outside of the image of Setup), then it just tries to compute a proof for an honest statement x. Note that in the adaptive soundness game the CRS will always be valid and thus only the first branch will matter. Since L is a hard-on-average language, then false and true statements are indistinguishable, and therefore S will produce a proof which is accepted by a verifier with an overwhelming probability. So indeed A_slowdoes break adaptive soundness.

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{s l o w} $$

$$ \pi $$

$$ \mathcal{A}_{s l o w} $$

Let us suppose that there exists an efficient reduction R that given black-box access to any adaptive soundness adversary A, can break some falsifiable assumption C. The problem is that although A_slowdoes

$$ \mathcal{A}_{s l o w} $$

$$ (\mathsf{x},\mathsf{w})\in\mathcal{R} $$

$$ f(\pi)=f(\mathsf{P R F}_{K}(\mathsf{x})) $$

′ ′ Fig. 13: Programs P and V

$$ \mathsf{P}{}^{\prime} $$

$$ {v V{{}'{}}} $$

Aslow break adaptive soundness, it is not efficient. Therefore also the reduction R will be inefficient. We solve this issue be constructing an efficient emulator A_fast(the second algorithm in fig. 12) for A_slow.

$$ R^{\mathcal{A}_{s l o w}} $$

$$ \mathcal{A}_{f a s t} $$

The emulator A_fastsimply samples an honest (x*,*w) and generates an honest proof π. Now let us compare A_fastand A_slow. If CRS is invalid, then A_slowand A_fastare identical. However, if the CRS is valid, then it needs a bit more work to show that outputs are indistinguishable. Intuitively, x is indistinguishable due to the hard-on-average property and π is indistinguishable due to zero-knowledge. However, here it is important that zero-knowledge property holds even with respect to a fixed CRS since we do not know how the distinguishing adversary may pick the valid CRS. Moreover, with computational zero-knowledge it may be even possible to extract the witness from a proof π which would make distinguishing A_slowand A_fasttrivial. This is the reason why zero-knowledge has to be perfect (or statistical). It follows now that outputs of A_fastand A_slow are computationally indistinguishable.

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{f a s t} $$

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{f a s t} $$

$$ \mathcal{A}_{s l o w}. $$

$$ \mathcal{A}_{f a s t} $$

$$ \mathcal{A}_{s l o w} $$

$$ \mathcal{A}_{f a s t} $$

$$ \mathcal{A}_{f a s t} $$

$$ \mathcal{A}_{s l o w} $$

$$ R^{\mathcal{A}_{\mathrm{}{s l o w}}} $$

AslowAfast Since R can break the assumption C, then so does R which means that the assumption C is insecure. Hence, it is impossible to base adaptively sound perfect zero-knowledge argument on a falsifiable assumption using a black-box reduction.

$$ R^{\mathcal{A}_{f a s t}} $$

F Non-Adaptive SNARGs With Perfect ZK Based on iO

We show how for the non-adaptive case, none of [Pas13] and [GW11] results hold. We do so by the following observation: assuming that indistinguishability obfuscation (iO) can be build from falsifiable assumptions (see [WW21b]), the perfect NIZK arguments of Sahai and Waters [SW14], instantiated with a puncturable PRF (PPRF) that satisfies succinctness property, is a non-adaptive SNARG with perfect ZK for all NP languages in the CRS model. While this can be seen as a feasibility result, proposing a construction with more standard assumptions (i.e., without iO) is still an interesting open question.

We now recall the NIZK arguments of Sahai and Waters [SW14].

NIZK arguments of Sahai and Waters. The idea is very simple: the proof system consists of two obfuscated programs put in the CRS. The first program is the proving algorithm that inputs a statement x and witness w and outputs a signature on x if (x*,*w) ∈ R. The signature is realized by a PRF in the construction. The second program is the verification algorithm that is just the signature verification and verifies the proof by checking the validity of the signature on x.

$$ {\mathfrak{m}}{textsf x{\mathrm{i f}}}({\mathsf{x}},{\mathsf{w}})\in{\mathcal{R}} $$

Let PRF be a puncturable PRF that inputs ℓ-bit long strings and outputs λ bits (where λ is the security parameter). Let f (·) be a one way function. The NIZK argument Π = (Setup*,* P*,*V) for language L with relation R is as follows:

$$ f(\cdot) $$

$$ \ \mathit\Pi=({mathsf\mathsf S e t u p},\mathsf{P},\mathsf{V}) $$

λ ′ – Setup(1) first selects a puncturable PRF key K for PRF. Next, it creates an obfuscation of programs P ^′ and V as depicted in Figure 13. The CRS crs consists of the two obfuscated programs.

$$

• \operatorname {S e t u p} \left(1 ^ {\lambda}\right) $$

$$ \mathsf{P}{}^{\prime} $$

′ – P(crs*,* x*,w) runs the obfuscated program P on input (x,w) and returns the proof π if (x,*w) ∈R.

$$ -\ {mathsf textsf{P}}(\ {mathsf c}{\mathsf r{r}},{\mathsf x},{\mathsf w}) $$

$$ \mathsf{P{'} $$

$$ (x,w) $$

$$ (\mathsf{x},\mathsf{w})\in\mathcal{R} $$

′ – V(crs*,* x*,π*) runs the obfuscated program V on input (x*,π*) and returns a bit indicating accept or reject.

$$

• \mathrm {V} (\mathrm {c r s}, x, \pi) $$

$$ V ^ {\prime} $$

$$ (\mathsf{x},\pi) $$

Theorem 10. [SW14] The argument system Π is perfectly zero-knowledge. Moreover, if the obfuscation scheme is indistingishuably secure, PRF is a secure punctured PRF with succinctness property, and f(·) is an injective one way function, then Π is a non-adaptive SNARG.

Remark 5. While SNARGs with non-adaptive security can be seen as interactive two-message arguments by thinking of the CRS as the verifier’s message, the type of non-adaptivity in the resulting argument is still “strong” in the sense that the verifier’s message does not depend on the prover’s (fixed) statement. One can also define a weaker notion of non-adaptivity for two-message arguments where the first message is statement-dependent (See [BIOW20] for example). We note that while the above iO-based construction satisfies the stronger notion, giving a construction for the weaker notion of non-adaptivity based on seemingly weaker tools is not a hard task. Namely, the verifier can use a witness encryption scheme to encrypt a succinct random value r under the prover’s statement and ask the prover to return r.