Chris Brzuska
email: chris.brzuska@aalto.fi

Geoffroy Couteau
email: geoffroy.couteau@ens.fr

On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness

Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo '95) and establish a highly desirable win-win situation: either (symmetric) cryptography exists unconditionally, or all NP problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results of the following type: either there are fine-grained one-way functions (FGOWF), or nontrivial speedups can be obtained for all NP problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an NP language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF, and obtain two negative results: Separation I. We provide a strong oracle separation for the implication (∃ exponentially average-case hard language =⇒ ∃ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win-win result. Namely, we rule out a black-box proof for the implication (∃ exponentially average-case hard language whose hardness amplifies optimally through parallel repetitions =⇒ ∃ FGOWF). This separation forms the core technical contribution of our work.

Introduction

In his celebrated 1995 position paper [START_REF] Impagliazzo | A personal view of average-case complexity[END_REF], Impagliazzo describes his personal view of the study of average-case complexity, an emergent (at the time) and fundamental area of computational complexity initiated in a seminal work of Levin [START_REF] Levin | Average case complete problems[END_REF], which aims to characterize NP problems which are not only hard for a worst-case choice of inputs, but also for natural distributions over the inputs. In Impagliazzo's view, our current understanding of the landscape of complexity theory is best described by considering five possible worlds we might live in, which are now commonly known as the five worlds of Impagliazzo, corresponding to the five possible outcomes regarding the existence of worst-case hardness in NP, average-case hardness in NP, one-way function, and public-key cryptography. The corresponding five worlds, Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania, and their relations are summarized on Fig. 1. Algorithmica and Heuristica correspond to the "algorithmist's wonderland", where all NP languages can be decided efficiently on the average. Cryptomania and Minicrypt correspond to the "cryptographer's wonderland",1 where one-way functions (and therefore, stream ciphers, signatures, pseudorandom functions, etc.) exist. Eventually, Pessiland is what Impagliazzo describes as "the worst of all possible worlds": a world in which many NP problems might be untractable (even on natural instances), yet no one-way function (and thus no cryptography) exists.

One-Way Functions Based on Average-Case Hardness.

In this article, we study whether (the existence of) average-case hard NP problems imply (the existence of) one-way functions. Conceptually, a positive answer to this question rules out Pessiland, i.e., it constitutes a win-win result: Either all NP problems can be solved efficiently, on the average, or cryptographic one-way functions exist. Little progress has been made on this question in the past two-and-a-half decades. There is a partial explanation for this lack of success: we know that any construction of one-way functions from average-case hard NP problems must rely on non-black-box techniques (Wee [Wee06] attributes this simple observation to Impagliazzo and Rudich). Indeed, similar separations [IR90,FF93,BT03,AGGM06,BB15] are known between any two of Impagliazzo's worlds. However, there, the situation is much more satisfying: At the bottom of the hierarchy, we know that stronger exponential worst-case assumptions imply that avgP = DistNP [Yao82, [START_REF] Welch | Error correction for algebraic block codes[END_REF][START_REF] Sudan | Decoding of Reed Solomon codes beyond the error-correction bound[END_REF][START_REF] Levin | One way functions and pseudorandom generators[END_REF][START_REF] Sudan | Pseudorandom generators without the XOR lemma[END_REF]. At the top of the hierarchy, we know that exponentially secure one-way functions imply a weak, but useful notion of public-key cryptography, namely fine-grained public-key cryptography where there is a polynomial (rather than superpolynomial) gap between the time to encrypt and the time needed to break the cryptosystem [START_REF] Merkle | Secure communications over insecure channels[END_REF]BGI08]. Interestingly, the very first publicly-known work on public-key cryptography, the 1974 project proposal of Merkle2 (published much later in [START_REF] Merkle | Secure communications over insecure channels[END_REF]) achieves exactly such a weak notion of security: Merkle shows that an ideal OWF (modeled as a random oracle) can be used to construct a key agreement protocol where the honest parties run in time n, while the best attack requires time n 2 . The assumption of an ideal OWF was later relaxed to the existence of exponentially hard OWFs by Biham, Goren and Ishai [BGI08]. Hence, in essence, Merkle establishes a weak exclusion of Minicrypt, by showing that strong hardness in Minicrypt already implies some nontrivial form of publickey cryptography, with a quadratic gap between the attacker's runtime and the honest parties' runtime.

Our Contribution: Inbetween Heuristica and Pessiland

The above result suggests a natural relaxation of Impagliazzo's program: rather than ruling out Pessiland entirely, one could hope to show that sufficiently strong forms of average-case hardness suffice to construct weak forms of cryptography. Such a result would still have a very desirable win-win flavor. For example, if one shows that exponential average-case hardness implies fine-grained one-way functions, it would show that either all NP problems admit nontrivial (subexponential) algorithms on the average, or there must exist some form of cryptography, with a polynomial security gap. As the computational power increases, such a gap translates to an increasingly larger runtime gap on concrete instances and thus a larger concrete security margin in realistic situations.

We can also consider starting from even stronger forms of average-case hardness. A very natural target is non-amortizing average-case hardness, which states (in essence) that deciding whether k words (x 1 , • • • , x k ) belong to a language L is k times harder (on average) than deciding membership of a single word. This stronger form of average-case hardness is closely related to the widely studied notion of proofs of work [START_REF] Ball | Proofs of work from worstcase assumptions[END_REF]. Building fine-grained one-way functions from this strong form of average-case hardness would still be a very meaningful win-win: it would show that either we can obtain nontrivial savings on average for all NP problems when amortizing over many instances (which would be an algorithmic breakthrough), or there must exist some weak form of cryptography.

In this work, we initiate the study of these intermediate layers between Heuristica and Pessiland, obtaining both positive and negative results.

Fine-Grained OWFs from Block-Finding Hardness. We mentioned above two natural strengthenings of average-case hardness: exponential average-case hardness, and non-amortizable average-case hardness (deciding whether k words (x 1 , • • • , x k ) belong to L is k times harder that deciding membership of a single word). Here, we consider even stronger notions: we assume that there is a language where it is already hard to decide, given k random words (x 1 , • • • , x k ), whether their language membership satisfies some local structure. As a simple example of such a notion, consider the following (average-case) block-finding hardness notion: given k random words x = (x 1 , • • • , x k ) and a t ≈ log k-bit string s, computed as the t language membership bits of a randomly chosen sequence of t consecutive words in x, find these consecutive words. The notion states (informally) that finding such a sequence (when it exists, and with probability significantly better than the random guess) cannot be done much faster than by brute-forcing a significant fraction of all the language membership.

To get an intuition of this problem, it is helpful to consider an even simpler formulation: given k random words (x 1 , • • • , x k ) with the promise that t consecutive words are not in the language, find these t consecutive words (with probability significantly better than 1/k). For a very hard language, it is not clear how to do this without naively brute-forcing the language membership of Ω(k/t) words. We show that this (very strong) average-case hardness notion already gets us outside of Pessiland: if there is a block-finding hard language, then there exists fine-grained one-way functions (with a quadratic hardness gap).

Heuristically Evaluating the Assumption on Random Languages. Given that this strong form of average-case hardness is new, we provide some heuristic analysis to support the intuition that it plausibly holds for some hard languages. To do so, we introduce a convenient tool for this heuristic analysis, a random language model (RLM), analogous to how the random oracle model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF] is used to heuristically study the security of constructions when instantiated with a sufficiently strong hash function. The RLM provides oracle access to a truly random NP-language L. In the RLM, each bitstring x ∈ {0, 1} n belongs to L with probability exactly 1/2, and the membership witness for a word x ∈ L ∩ {0, 1} n is a uniformly random bitstring from {0, 1} n . 3 To check membership to the language, the parties have access to an oracle Chk which, on input a pair (x, w) ∈ {0, 1} n × {0, 1} n , returns 1 if x ∈ L and w is the right corresponding witness, and 0 otherwise. Finding out whether a random bitstring x ∈ {0, 1} n belongs to L requires 2 n-1 calls to Chk on the average. 4The RLM captures idealized hard language where it is not only (exponentially) hard to decide language membership, but also hard to sample an element of the language with probability significantly better than 1/2 (hence, in particular, it is also hard to generate a word together with the corresponding witness). This captures hard languages where no further structure is assumed beyond the ability to efficiently check a candidate witness; note that the ability to sample instances together with their witness is exactly the additional structure which implies the existence of one-way functions [START_REF] Impagliazzo | A personal view of average-case complexity[END_REF], hence the question of building one-way functions from average-case hardness asks precisely about whether this can be done without assuming this additional structure to start with.

In this work, we prove that a random language satisfies block-finding hardness, providing some heuristic support for this strong form of average-case hardness. Hence, we get as a corollary:

Corollary 1 (Informal). In the Random Language model, there exists a finegrained one-way function which can be evaluated with n oracle calls, but cannot be inverted with o(n 2 ) calls to the random language.

Constructing a FGOWF from Block-Finding Hardness. At a (very) high level, the construction proceeds as follows: suppose that there exists hard puzzles where sampling a random puzzle p is easy (it takes time, say, O(1)), but finding the unique solution s = s(p) to the puzzle, and verifying that a candidate solution s to the puzzle is correct, are comparatively harder (they take some much larger respective times N 1 and N 2 with N 1 ≈ N 2 ). For example, such puzzles can be constructed by sampling |s| words (x 1 , • • • , x |s| ), and asking for the length-|s| bitstring of the bits indicating for each word x i whether it belongs to a given hard language L. Then we construct a fine-grained OWF as follows: an input to the function is a list of n puzzles (p 1 , • • • , p n ) for some bound n, and an integer i ≤ n. The function F (p 1 , • • • , p n , i) first solves the puzzle p i , and outputs the solution s(p i ) together with (p 1 , • • • , p n ). Evaluating F takes time O(n)+N 1 ; on the other hand, when L is an ideally hard language, inverting F requires bruteforcing many of the p i , which takes time O(n • N 2 ). Setting n ≈ N 1 ≈ N 2 gives a quadratic hardness gap. We refer to Sect. 3 for a technical overview and the full version of this work [START_REF] Brzuska | Towards fine-grained one-way functions from strong average-case hardness[END_REF] for a formal proof and analysis of block-finding hardness in the RLM.

Average-Case Hard Languages and Fine-Grained OWF.

With the above, we know that a sufficiently strong form of average-case hardness suffices to construct fine-grained one-way functions. The natural next question is whether weaker forms of average-case hardness could possibly suffice. We consider the two natural notions we mentioned previously: exponential average-case hardness, and the stronger non-amortizing exponential average-case hardness. For both, our main results are negative and rule out relativizing (black-box) constructions.

For exponential average-case hard languages, we show that any construction of fine-grained OWF from an (even exponentially) average-case hard language, even with an arbitrarily small polynomial security gap N 1+ε (for any absolute constant ε > 0), must make a non-black-box use of the language. We prove this by exhibiting an oracle relative to which there exists an exponentially hard language, but no fine-grained one-way functions:

Theorem 2 (Informal).

There is an oracle relative to which there exists an exponentially secure average-case hard language, but any candidate fine-grained OWF f can be inverted with probability O(1) and Õ(N ) calls to the oracle, where N denotes the number of oracle calls to compute f in the forward direction.

Black-Box Separation Between Non-Amortizable Average-Case Hard

Languages and Fine-Grained OWF. We then investigate whether nonamortizability (which states, roughly, that deciding membership of k random instances to L should take O(k) times longer than deciding membership of a single instance to L) suffices to construct fine-grained OWFs. As we explained, this would still constitute a very interesting win-win result: it would show that either weak forms of cryptography exist unconditionally, or nontrivial speedups can be achieved for all NP problems when amortizing over many random instances. Below, we sketch another motivation for studying this setting.

Non-Amortizability Helps Circumvent Black-Box Impossibilities. Non-amortizability features have proven to be a key approach to overcoming black-box impossibility results for cryptographic primitives. For example, the Biham-Goren-Ishai construction [BGI08] of fine-grained key agreement from exponential OWFs only provides an inverse-polynomial bound on the probability that an attacker retrieves the shared key when relying on Yao's XOR Lemma. In turn, when relying on a (plausible) version of the XOR Lemma stating that success probability decreases exponentially fast in the number of XORed instances, the adversary's success probability can be brought down to negligible. Yet, this "Dream XOR Lemma" cannot be proven under black-box reductions [BGI08]. An even more striking example is given by Simon's celebrated black-box separation between one-way functions and collision-resistant hash functions [START_REF] Simon | Finding collisions on a one-way street: can secure hash functions be based on general assumptions?[END_REF]: Holmgren and Lombardi [START_REF] Holmgren | Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications)[END_REF] recently showed that a one-way product function (i.e., a OWF that amplifies twice, meaning that inverting f on two random images (y 1 , y 2 ) takes twice the time of inverting f on a single random image) suffices to circumvent Simon's impossibility result and build a collision-resistant hash function (in a black-box way).

A Black-Box Separation. Motivated by the above, we investigate the possibility of building fine-grained OWFs from non-amortizable average-case hard languages (i.e., languages whose average-case hardness amplifies through parallel repetitions). Unfortunately, our result turns out to be negative: we prove that there is no black-box construction of an N 1+ε -hard OWF (where N is the time it takes to evaluate the function in the forward direction), for an arbitrary constant ε > 0, even from an exponentially average-case hard language whose hardness amplifies at an exponential rate through parallel repetition. Conceptually, our second negative result separates fine-grained one-way functions from a much stronger primitive and can thus be seen as a much stronger result. Note, however, that technically, the two negative results are incomparable since the first one rules out relativizing reductions whereas the latter rules out black-box reductions, see the beginning of Sect. 3 for a discussion.

Theorem 3 (Informal).

There is no black-box construction of an N 1+ε -hard OWF f , for an arbitrary constant ε > 0, from exponentially average-case hard languages L whose hardness amplifies at an exponential rate through parallel repetition.

In the nomenclature of Reingold, Vadhan and Trevisan [RTV04], we rule out a ∀∃-weakly-reduction, a slightly weaker notion than a relativizing reduction. Namely, the reduction can access the adversary. Our result becomes a full oracle separation if the fine-grained one-way function f would be given black-box access to the adversary A as well. Reingold, Vadhan and Trevisan point out that in some cases, the adversary A can be embedded into the oracle O, but doing so did not seem straightforward for our case and is left as an open question. In the CAP nomenclature of Baecher, Brzuska and Fischlin [START_REF] Baecher | Notions of black-box reductions, revisited[END_REF], we rule out NNN reductions, since the construction f can depend on the language L, and the reduction C can depend on both, the adversary and the primitive, i.e., each of these dependencies can be seen as non-black-box, thus NNN.

Why Study Non-amortizability?

In the past, non-amortizability proved key to overcome related limitations. For example, if one wants to build fine-grained key exchange with overwhelming security from (exponential) OWFs, a strong non-amortizability property (dubbed dream XOR lemma) is known to be necessary [BGI08]. Non-amortizability also allows bridging the gap between OWF and CRHFs [START_REF] Holmgren | Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications)[END_REF]. Moreover, a very natural and-initially-promising-looking approach towards fine-grained cryptography from weaker-than-usual assumptions inherently goes through (and stops at) non-amortizable languages. Finally, a positive result (non-amortizable languages give FGOWF) would give a really nice win-win (algorithms efficiency vs cryptographic security) result.

Let us elaborate on the approach being natural and looking promising. The goal (FGOWFs from "weaker" assumptions) was set forth in [START_REF] Ball | Average-case fine-grained hardness[END_REF], with a promising path: starting from a worst-case assumption (the exponential time hypothesis (ETH)), one gets structured average-case hardness (through the orthogonal vector problem (OV)); furthermore, this was pushed to nonamortizable hardness in follow-up work [START_REF] Ball | Proofs of work from worstcase assumptions[END_REF]. Then, [START_REF] Ball | Average-case fine-grained hardness[END_REF] asked: can we push this OV-based construction further, up to FGOWFs?

One way to read our contributions is the following: our positive result can easily be framed as an OV-based construction (solving a block becomes finding x such that F (x) = 1, where F is an explicit low-degree polynomial). The key technique in [START_REF] Ball | Average-case fine-grained hardness[END_REF][START_REF] Ball | Proofs of work from worstcase assumptions[END_REF] are a worst-case to average-case reduction and an average-case to non-amortizability reductions using the Berlekamp-Welch algorithm, which inherently only works for search OV. Block-finding hardness, on the other hand, formalizes what we would need to prove to achieve FG-OWF from ETH through this approach. Then, our last separation says: the further the Berlekamp-Welch techniques seems to get us (i.e., to non-amortizing hardness) won't suffice (in a black-box way) to achieve what we need, with any candidate construction. In other words, we need new non-black-box techniques that go beyond the Berlekamp-Welch algorithm. Since non-amortizability proved key to overcome related limitations in the past, we actually attempted to prove security of our construction from non-amortizing hardness for a long time.

A Core Abstract Lemma: The Hitting Lemma

At the heart of both our positive result and our black-box separations is an abstract lemma, which we call the Hitting Lemma. While the statement of the lemma is very intuitive, its proof is quite technical, and forms one of the core technical contributions of this work. In its abstract form, the Hitting Lemma is a very general probability statement about a simple two-player game between a challenger and an adversary. It shows up naturally on three seemingly unrelated occasions in our work, hence it seems likely that it can have other applications, and we believe it to be of independent interest. At a high level, the Hitting Lemma provides a strong Chernoff-style bound on the number of witnesses which an adversary can possibly find given oracle access to the relation of a hard language. More precisely, we state the Hitting Lemma in an abstract way, as a game with the following structure:

-First, the game chooses a list of sets V i . Each set V i has size bounded by some value 2 n and can be thought of as the set of candidate witnesses for a size-n word. -In each set V i , the game chooses a uniformly random witness r i . The sets V i are allowed to have different sizes, to capture the more general setting where the adversary already obtained preliminary information excluding candidate witnesses. -Eventually, the adversary interacts with an oracle Guess r1•••r which, on input (i, x), returns 1 if x = r i and ⊥ otherwise.

We call a query (i, x) such that Guess r1•••r (i, x) = 1 a hitting query (or a hit).

The goal of the adversary is to get as many distinct hits as possible within a bounded number of queries. Intuitively, the most natural strategy to maximize the number of hits is to proceed as follows: first pick the smallest set V i , and query arbitrary positions one by one, until a hit is obtained. Then, pick the second smallest set V j and keep proceeding the same way, until all of the r i are found or the query budget is exhausted.

In essence, the Hitting Lemma states that the above natural strategy is really the best possible strategy, in a strong sense. Namely, denoting m Q the average number of hits obtained by a Q-query adversary following the above strategy, the Hitting Lemma shows that for any possible adversarial strategy, the probability of getting O(m Q ) + c distinct hits using Q queries decreases exponentially with c (for some explicit constant in the O(•)). The proof combines a reduction to a simpler probabilistic statement, proven by induction over Q, with a tight concentration bound on the winning probability of the above natural strategy.

Interestingly, the Hitting Lemma extends directly to the non-uniform setting, where the adversary is allowed to receive an arbitrary k-bit advice about the Guess oracle; this properties turns out to be crucial in some of our results. Our bound shows that this advice cannot provide more than k additional hits. More precisely, for any possible adversarial strategy where the adversary receives an arbitrary k-bit advice about the oracle, the probability of getting O(m Q ) + k + c hits decreases exponentially with c. We refer to Sect. 6 for the full statement and analysis of the Hitting Lemma.

Analogy with the ROM. In the Random Oracle Model, a long line of work (see for example [Hel80,Unr07,DGK17,CDGS18] and references therein) has established the hardness of inverting an idealized random function in a non-uniform setting, given a bounded-length advice about the oracle. These results have proven to be important and powerful tools to reason about the Random Oracle Model. At a high level, the hitting lemma provides a comparable tool in the Random Language Model, and captures the hardness of deciding language membership for an idealized hard language, even given a non-uniform advice, and even when the adversary tries to amortize over many instances.

On the Significance of Our Results

We now address some points about how our results should be interpreted, and what they imply.

On Basing FGOWF on the Average-Case Hardness of a Concrete NPcomplete Language. Our impossibility results rule out constructions of finegrained one-way function that would work using black-box access to an arbitrary average-case hard language. However, it seems plausible that a construction of FGOWFs from the average-case hardness of an arbitrary language could proceed differently. Typically, such a construction could first reduce the language to a SAT instance (or any other NP-complete problem) using a non-black-box (e.g. Karp) reduction. Then, the construction of FGOWF would build upon the concrete structure of SAT; such a construction would not be ruled out by our results.

Implications of our Negative Results

. In this setting, our negative results should be interpreted as saying that if such a construction is possible, then it must crucially rely on specific structural hardness properties of the chosen language, and not solely on natural properties such as its exponential hardness, or its nonamortizability. As it turns out, this has implications to previous attempts of basing cryptography on weaker hardness assumptions. The work of [START_REF] Ball | Average-case fine-grained hardness[END_REF] showed constructions of fine-grained average-case hard languages from the strong exponential-time hypothesis (SETH), using a worst-case to average-case reduction based on the orthogonal vector problem. A major open problem left in their work, which they discuss at length, is whether their construction could be strenghtened to give FGOWFs. In a subsequent work [START_REF] Ball | Proofs of work from worstcase assumptions[END_REF], the authors made a step in the right direction, building proofs of work from SETH (building upon their result in [START_REF] Ball | Average-case fine-grained hardness[END_REF]). Their construction precisely exploits that due to the specific structure of the orthogonal vector problem, it is possible to show non-amortizability of their fine-grained average-case hard language, which suffices to build proofs of work. Our result shows that this non-amortizability does not suffice to build FGOWFs: if there is a construction, it must rely on a different structural hardness property.

In fact, we initially designed the construction of FGOWF from block-finding hardness as a construction based on the average-case hard puzzles of [START_REF] Ball | Proofs of work from worstcase assumptions[END_REF], and dedicated an important effort to trying to reduce its security to the nonamortizable average-case hardness of this puzzle, viewing this approach as the most promising direction to based FGOWFs on a worst-case hardness assumption such as SETH. After failing to prove it secure, we realized that our lack of success might be inherent, and turned this realization into a proof by demonstrating the impossibility of basing a FGOWF on non-amortizing hardness in a blackbox way. We hope and believe that our negative results will therefore guide future attempts of basing FGOWFs on weaker assumptions, even attempts that do not ultimately aim at building them from arbitrary hard languages.

Implications of our Positive Results

. Furthermore, our positive result hints precisely at the type of hardness which could suffice to build FGOWFs: intuitively, what is needed is that the concrete language satisfies some form of pattern finding hardness, where given a list of words (x 1 , • • • , x n ), finding whether there is a sub-vector of words whose membership bits (i.e. the vector of bits indicating for each word whether it is in the language) satisfy a given pattern should require deciding membership of a large fraction of all words. This is formalized as block-finding hardness in our work (see Sect. 3.1 and the full version of this work [START_REF] Brzuska | Towards fine-grained one-way functions from strong average-case hardness[END_REF]). We note that other related forms of hardness -where one must decide whether the membership bits of a vector of words satisfy some locally testable property -can also be shown to imply FGOWFs. We note that actually, a very similar type of structural hardness has been used in [START_REF] Lavigne | Public-key cryptography in the fine-grained setting[END_REF] to build fine-grained one-way functions from concrete average-case hard problems.

Related Work

Fine-Grained Cryptography. We already pointed out that Merkle's construction [START_REF] Merkle | Secure communications over insecure channels[END_REF] provides the first example of fine-grained cryptography (as well as the first known example of public-key cryptography). It was further studied in [BGI08,BM09], and generalized to the quantum setting in [START_REF] Brassard | Quantum Merkle puzzles[END_REF][START_REF] Brassard | Merkle puzzles in a quantum world[END_REF]. Fine-grained cryptography has only become an explicit subject of study recently. The work of [START_REF] Ball | Average-case fine-grained hardness[END_REF][START_REF] Ball | Proofs of work from worstcase assumptions[END_REF] constructs proofs of work from explicit fine-grained average-case hard languages which can be based on the strong exponential-time hypothesis (SETH), and explicitly poses the problem of building fine-grained one-way functions (while showing some barriers for basing them on SETH via natural approaches). The work of [START_REF] Degwekar | Fine-grained cryptography[END_REF] studies a different form of fine-grained cryptography, showing cryptosystems secure against resourcebounded adversaries, such as adversaries in NC 1 , under a worst-case hardness assumption. Eventually, the work of [START_REF] Lavigne | Public-key cryptography in the fine-grained setting[END_REF] is the most closely related to ours: it shows constructions of fine-grained one-way functions and fine-grained encryption schemes from the average-case hardness of concrete problems, such as the Zero-k-Clique problem.

Hardness in Pessiland. While building one-way functions from average-case hardness has remained elusive, some works have investigated other useful forms of hardness which could possibly reside in Pessiland. In particular, in [START_REF] Wee | Finding Pessiland[END_REF], Wee shows that the existence of non-trivial succinct 2-round argument systems for some languages in NP cannot be excluded from Pessiland in a black-box way.

Oracle Techniques. Besides new ideas, our oracle separation relies on several established techniques. We use the two-oracle technique of [START_REF] Simon | Finding collisions on a one-way street: can secure hash functions be based on general assumptions?[END_REF]HR04] where one oracle implements the base primitive and the second oracle breaks constructions built from this primitive. As we argue about the efficiency of the constructed one-way function, we use similar techniques to Gennaro and Trevisan [START_REF] Gennaro | Lower bounds on the efficiency of generic cryptographic constructions[END_REF] who describe the emulation of a random oracle based on a boundedlength string, implicitly applying a compression argument. We use Borel-Cantelli to extract a single oracle from a distribution of random oracles as the seminal work on black-box separations by Impagliazzo and Rudich [START_REF] Impagliazzo | Limits on the provable consequences of oneway permutations[END_REF]. In order to make our oracle deterministic, we use the hashing trick of Valiant-Vazirani [START_REF] Valiant | NP is as easy as detecting unique solutions[END_REF] to obtain a unique value out of many pre-image for a one-way function.

In particular, we hash evaluation paths similar to Bogdanov and Brzuska [BB15] who separate size-verifiable one-way functions from NP-hardness.

On the Relation to Two Recent Works. In a recent work [START_REF] Pass | Is it easier to prove statements that are guaranteed to be true?[END_REF], Pass and Venkitasubramaniam show that TFNP (the class of total NP search problems) is unconditionally hard in Pessiland. More precisely, they show the following: if there exists average-case hard languages, then either there exists average-case hard TFNP problems, or there exists one-way functions. We note that, since their constructions are black-box, combining their result with our work further implies the following result stating that proving that total search average-case hardness suffices to construct fine-grained one-way functions is likely to be hard, since any such black-box proof would unconditionally imply the existence of (full-fledged) one-way functions: Theorem 4 (this work + [START_REF] Pass | Is it easier to prove statements that are guaranteed to be true?[END_REF], informal). If there is a black-box construction of N 1+ε -hard one-way function, for an arbitrary constant ε > 0, from average-case TFNP hardness, then one-way functions exist unconditionally.

In another recent work [START_REF] Pass | On one-way functions and Kolmogorov complexity[END_REF], Pass and Liu showed that mild average-case hardness of computing time-bounded Kolmogorov complexity already suffices to establish (in a black-box way) the existence of one-way functions. In particular, we note that, combined with our results, this implies that even exponentiallystrong, self-amplifiable average-case hardness in NP does not imply (in a blackbox way) mild average-case hardness of time-bounded Kolmogorov complexity.

Theorem 5 (this work + [PL20], informal).

There is no black-box reduction from the mild average-case hardness of computing time-bounded Kolmogorov complexity to the existence of exponentially average-case hard languages whose hardness amplifies at an exponential rate via parallel repetition.

Preliminaries

Notation, Computational Models and Oracles

For any n ∈ N, [n] denotes the set {1, • • • , n}. Throughout this paper, we represent algorithms as families of boolean circuits (one for each input length), and use circuit size (i.e., the number of wires) as the main measure of efficiency. We model oracle access by allowing circuits to have oracle gates. We measure the size of such an oracle circuit as for a standard circuit, as the number of its wires. Typically, if an oracle takes an n-bit entry as input and outputs an m-bit response, this will be modeled by a fan-in-n fan-out-m oracle gate (hence this gate will contribute n + m to the total circuit size).

As in the standard model for boolean circuits, the wires typically carry bit values. For simplicity and readability, we will generally allow the wires to directly carry other special symbols, such as ⊥ and err (converting a circuit in this model to a "purely boolean" circuit only introduces some constant blowup which has no impact on our asymptotic results). By default, even when we do not mention it explicitly, we allow all (standard and oracle) gates to receive the symbol err as one of their inputs. If a gate receives err as one of its inputs, it returns the err on all of its output wires. We use pseudo-code as a description language and only argue about the size of the corresponding circuit informally.

Fine-Grained One-Way Functions

We start by introducing the notion of a fine-grained one-way function (FG-OWF). At a high level, an (ε, δ)-FG-OWF is a function f (modeled as a family {f m } m of circuits, one for each input size) such that all circuits of size o(|f | 1+δ ) have probability at most ε to find a preimage of f (x) for a random input x.

Pr z←${0,1} m C m (f (z), 1 m ) ∈ f -1 (f (z)) ≤ ε(m).
One can also consider a slightly weaker notion, namely a fine-grained oneway function distribution (FG-OWFD), were the hardness of inversion should hold with respect to a randomly sampled function f from a distribution D.

Pr z←${0,1} m ,f ←$D C m (f, f (z), 1 m ) ∈ f -1 (f (z)) ≤ ε(m).
Any distribution over FG-OWFs induces a FG-OWFD, but the converse need not hold in general.

Languages

The class NP contains all languages L of the form L = {x | ∃w, (|w| = poly(|x|))∧ (R(x, w) = 1)}, where R is a relation computable by a polysize uniform circuit. This definition naturally extends to the case where an oracle O is available; in this case, we say that the oracle language L O is in NP O if it is of the above form, where R is computable by a uniform oracle circuit with |R| = poly(|x|). When the oracle O is clear from the context, we will sometimes abuse this notation and simply say that the oracle language L O is in NP. For a string x, we will denote by L(x) the bit which is 1 if x ∈ L, and 0 otherwise. We will also extend this definition to vectors of strings x in a natural way.

Average-Case Hard Languages. We now define (exponentially) average-case hard languages (EACHLs). Note that the exponential hardness in the following definition refers to the success probability of the algorithm.

Definition 8 (Exponential Average-Case Hardness).

A language L is exponentially average-case hard if for any circuit family C = {C n } n∈N and all large enough n,

Pr x←${0,1} n [C n (x) = L(x)] ≤ 1 2 + |C n | 2 n .
Note that in the most common definition of EACHLs, one does usually not consider an exact bound |C n |, and instead define a language to be exponentially hard if a polytime algorithm C n finds L(x) with probability at most 1/2 + poly(n)/2 n for a random word x ∈ {0, 1} n . However, since we will work in the fine-grained setting, we settle for a stricter definition, with an explicit relation between the running time of C n and the probability of finding L(x). Similarly as for FG-OWFs, we can also define a weaker notion of exponential average-case hard language distributions (EACHLD):

Definition 9 (Exponential Average-Case Hard Language Distribution). A distribution D over languages L is exponentially average-case hard if for any circuit family C = {C n } n∈N and all large enough n,

Pr x←${0,1} n ,L←$D [C n (x, L) = L(x)] ≤ 1 2 + |C n | 2 n .
Note that any distribution over EACHLs induces an EACHLD, but the converse need not hold in general.

Pairwise Independent Hash-Functions

Definition 10. For all j, i ∈ N, we call a distribution H j,i over functions h : {0, 1} j → {0, 1} i+2 a distribution of pairwise independent hash-functions, if for all p, p ∈ {0, 1} j with p = p , it holds that

Pr h←$Hj,i+2 h(p) = 0 i+2 = 2 -i-2 Pr h←$Hj,i+2 h(p ) = 0 i+2 = 2 -i-2 Pr h←$Hj,i+2 h(p) = h(p ) = 0 i+2 = 2 -2i-4
The following fact is used, e.g., by Valiant and Vazirani in their randomized reduction which solves SAT given a UniqueSAT oracle [START_REF] Valiant | NP is as easy as detecting unique solutions[END_REF].

Claim 1. For all sets S ⊆ {0, 1} j such that 2 i ≤ |S| ≤ 2 i+1 , it holds that

Pr h←$Hj,i+2 ∃!p ∈ S : h(p) = 0 i+2 ≥ 1 8 .

Technical Overview: FGOWFs from Block-Finding Hardness

We first introduce the Random Language Model (RLM), which captures idealized average-case hard languages, in the same way that random oracles capture idealized one-way functions. 5 We will use this model as a heuristic tool to analyze the new form of average-case hardness which we will introduce next. We note that this model has limitations: it is a simplified model, and it is actually not too hard to directly build a fine-grained OWF in this model (e.g. one can define the function F which maps x to the list of language memberships of the words x||1, x • • • , x||n , for an appropriate choice of n 6 ). However, such simplified constructions do not correspond to any natural form of average-case hardness that could be formulated on standard NP languages. Rather, our goal is only to use the RLM as a heuristic rule of thumb to evaluate the plausibility of our new average-case hardness notion. We define a random language L as follows: for each integer n and each word x ∈ {0, 1} n , sample a uniformly random bit B[x]. Then the elements of L are all x with B[x] = 1. For notational convenience, we extend this notation to vectors: given a vector x of words, B( x) denotes the vector of the bits B[x i ]. For each x ∈ {0, 1} n , we also sample a uniformly random witness W [x] ←$ {0, 1} n . To check membership to the language, we introduce an oracle Chk defined as follows: on input a pair (x, w), the oracle checks whether B[x] = 0 or w = W [x]. If one of these conditions hold, it outputs ⊥; otherwise, it outputs 1 (See Fig. 2). It is relatively easy to see that to check membership of a candidate word x to L given access to Chk, the best possible strategy is to query (x, w) for all possible values w ∈ {0, 1} n , hoping to hit the uniformly random value W [x]. Hence, deciding membership of a word x to L requires on the average 2 n-1 queries to Chk, which shows that L is (exponentially) average-case hard.

Distribution T

for n ∈ N : We now define the notion of block-finding hardness. We will show that (1) block-finding hardness holds for a random language, and (2) if there is a block-finding hard language, then there is an explicit construction of a FG-OWF f such that every adversary running in time N (n) 2-ν for an arbitrarily small constant ν has only a negligible probability of inverting f (in n) -id est, there exists a (negl(n), 1 -ν)-FG-OWF, where negl(n) denotes some negligible function of n.

for x ∈ {0, 1} n : W [x] ←$ {0, 1} n B[x] ←$ {0, 1} return (W, B) Chk[W, B](x, w) if W [x] = w ∧ B[x] = 1 return 1 else return ⊥

Block-Finding Hardness of L

Informally, we say that a language satisfies block-finding hardness if for any adversary A and any large enough n, the following holds: The adversary A is given N ≤ 2 n /k many length-k vectors x i of distinct words x i,j ∈ {0, 1} n together with the string s = B[ x i ] (the vector of language membership bits for the words in x i ) for a uniformly random block index i ←$ [N ]. If A finds the block index i with probability significantly better than guessing, it must run in time Ω(N • 2 n ) (in the RLM, this corresponds to making Ω(N • 2 n ) queries to Chk). Intuitively, this means that (up to polylogarithmic factors) the best strategy to find i is to find out the language membership bits of some of the words in each of the blocks, by brute-forcing every possible witness for these words, until one finds membership bits that are consistent with s. Slightly more formally, we show the following: Lemma 11 (Block-Finding Hardness of L -Informal Version). For any adversary C, n ∈ N, block size k, and number of blocks N (with k • N ≤ 2 n ), and any tuple of blocks

( x i ) i≤N = (x i,1 , • • • , x i,k
) i≤N such that all the x i,j are distinct:

Pr i←$[N ] [C n (( x j ) j , B[ x i ]) = i] ≤ 1 Õ(N ) • |C n | 2 n + 1 • 2 O(k) .
In the RLM, the language L satisfies block-finding hardness essentially because distinct words have truly independent witnesses and language membership bits. More formally, the above lemma will follow from a strong and generic concentration bound, the hitting lemma. We state and formally prove the hitting lemma separately in Sect. 6, Lemma 19, since it turns out that this lemma provides a very and versatile tool to bound the success probability of an adversary which attempts to decide membership of words in an oracle language (the hitting lemma will be needed on three different occasions in this paper). In the context of proving the block-finding hardness of L, we will need a variant of the hitting lemma of the following form:

Lemma 12 (Simplified Hitting Lemma with Advice -Informal Version). For every integers n, N, k ∈ N with kN ≤ 2 n , vector y of kN words, adversary A getting y and B[ y i ] for a random i (where y i is a vector of k words), and for every integer c ≥ 1,

Pr (W,B)←T #Hit ≥ O(|A|) 2 n + k + c ≤ 2 -O(c) ,
where #Hit counts the number of witnesses found by A for distinct words of length n among the entries of y.

At the same time, conditioned on making less than M hits in different blocks, it is straightforward to show that A can find i with probability M/N : intuitively, this is because if i belongs to one of the N -M blocks where no hits were made, then the indices of all these blocks are perfectly equiprobable conditioned on the view of A. Applying Bayes rule to combine the above bounds, the probability that A finds i is upper bounded by the probability that A finds i conditioned on making less than M hits, plus the probability of making more than M hits. Therefore, for any M , the probability that A finds i is upper bounded by

M N + 2 -O(M -|A|/2 n -k) .
From there, an appropriate choice of M (depending on |A|, N, and n) suffices to conclude that A finds i with probability at most 1 Õ(N ) k) , which concludes the proof.

• |Cn| 2 n + 1 • 2 O(
From Block-Finding Hardness to Fine-Grained One-Way Function. A block-finding hard language immediately leads to a FG-OWF with a quadratic hardness gap: the input to the function is a list of N = 2 n /k blocks x of distinct words x i together with an index i. Evaluating the function is done by bruteforcing the languages membership bits of the words in x i , which takes at most k•2 n queries to Chk, and outputting ( x, s = B[ x i ]). By the block hardness of L, inverting the function on a random input, on the other hand, requires Õ(N • 2 n ) = Õ(2 2n /k) queries to Chk to succeed with constant probability when the index i is uniquely defined (i.e., there is a unique index i such that the block x i satisfies s = B[ x i ]). This can be guaranteed to hold except with negligible probability, by choosing k = ω(log n). Overall, this leads to a FG-OWF with quadratic hardness gap (up to polylogarithmic factors), with some small but non-negligible inversion probability ε. Parallel amplification can then be used to make the inversion probability negligible, leading to the following corollary:

Corollary 13. For any ε > 0, there exists a (negl(m), 1 -ε)-fine-grained oneway function distribution in the Random Language Model.

Overview: No FGOWFs from Average-Case Hardness

Next, we study the possibility of instantiating the above construction using an average-case hard language, instead of a block-finding hard language. At first sight, it is not clear that average-case hardness suffices, since our construction crucially relies on the block-finding hardness of the language, a seemingly much stronger property. Indeed, we show that there exists no construction of essentially any non-trivial FG-OWF making a black-box use of an exponentially averagecase hard language. To do so, we exhibit an oracle distribution relative to which there is an exponentially average-case hard language, but no FG-OWF, even with arbitrarily small hardness gap. This proof is the only part of our paper that does not require the hitting lemma.

Language Description. We start by introducing our language. Our oracle defines a somewhat exotic language: for each integer k, we let all words x ∈ {0, 1} n such that k = log n have the same random witness w ←$ {0, 1} 2 k , and we put either all these words simultaneously inside or outside the language, by picking the same random membership bit b k for all of them. Intuitively, this provides an extreme example of a language which is still hard to decide (since given a word x ∈ {0, 1} n , one must still enumerate over 2 2 log n > 2 n candidate witnesses to find out whether x ∈ L), but whose hardness does not amplify at all (since finding a witness for a single word x gives the witness for all words whose bitlength is close to that of x). This aims at capturing the intuition that any candidate FG-OWF built from an average-case hard language L must somehow leverage some amplification properties of the hardness of L. Then, the oracle Chk is similar as before: on input (x, w), it returns ⊥ if x / ∈ L or w is not the right witness for x, and 1 otherwise. We will show that any oracle adversary A requires O(2 n ) queries to decide membership of a word x ∈ {0, 1} n to L. The proof is relatively straightforward and relies on the fact that the membership of x to L remains random conditioned on the view of A as long as A did not make any hit, i.e., a query with the right witness for x.

Inexistence of FG-OWF Relative to Chk. Next, we show that for any constant δ, there exists an oracle algorithm A such that for any candidate FG-OWF f , A (given access to Chk) of size bounded by |f | 1+δ which inverts f with probability 0.99. The adversary works as follows: for any integer k, it checks whether the function will make "too many" queries of the form (x, w) with x of length n such that k = log n (we call this a k-query), where "too many" is defined as (2 2 k ) ε for a value ε = (1+δ/2) -1 . Intuitively, making more than this number of queries ensures that f will have a noticeable probability of making a hitting query. For all such "heavy queries", A makes all possible (2 2 k ) queries to Chk with respect to some fixed word x, until he finds the witness. A also does the same for all k-queries with k ≤ B(ε) for some bound B(ε) to be determined later, even when they do not correspond to heavy query (this is to avoid some "border effects" of small queries in the probability calculations). Note that this allows A to find the witness for all words of length n such that k = log n , since they all share the same witness. A defines the following oracle-less function f that contains all the hardcoded witnesses that A recovered. Now, on input x, f runs exactly as f and if f makes a k-query (x, w) for some k, then f proceeds as follows:

-If k corresponds to a heavy query, then, using (2 2 k ) queries, A already computed the witness for all k-queries and thus f contains the hardcoded witness to correctly answer the query. -If k does not correspond to a heavy query, f simulates the answer of the oracle as ⊥.

We prove that with high probability (at least 0.999), the function f agrees with f on a random input x; this is because f disagrees with f only if there is a k-query with k > 10 where f makes less than (2 2 k ) ε queries, yet hits a witness (for all other types of queries, A finds the witness by brute-force, hence it can always simulate correctly the answer of the oracle). But this happens only with probability 1 -

∞ k=B(ε)+1 (2 2 k ) ε • 2 -2 k ,
which is bounded by 0.999 by picking a sufficiently large bound B(ε) such that (1 -ε)2 B(ε) > B(ε). Then, by a straightforward probability calculation, the probability that inverting f (which A can easily do locally since f is oracle-less) corresponds to successfully inverting f on a random input x can be lower-bounded by 0.999 2 > 0.99, which concludes the proof.

Overview: No FG-OWF from Non-Amortizable Hardness

Note that the techniques from our simpler oracle separation crucially exploit that the hardness of the average-case hard language implemented by Chk does not amplify well (in fact, this is the reason why the hitting lemma is not needed in the analysis). We are thus interested in understanding whether we can still provide a black-box impossibility result even when the underlying average-case hard language satisfies non-amortizable exponential hardness, or whether nonamortizable average-case hard languages suffice to construct a fine-grained oneway function.

We call a language L (exponentially) self-amplifiable average-case hard if for any superlogarithmic (computable, total) function (•), for any circuit family

C = {C n : {0, 1} (n)•n → {0, 1} n } n∈N of size at most 2 O(n) • (n),
and for all large enough n ∈ N,

Pr x←${0,1} •n [C n ( x) = L( x)] ≤ poly(n) • 2 -(n)- Õ(|Cn|) 2 O(n) .
Informally, this means that to find the language membership bits of (n) challenge words, the best an adversary C n can do (up to polylogarithmic factors in |C n | and constant factors in n) is to brute-force as many membership bits as it can (roughly, Õ(|C n |)/2 n since brute-forcing a single membership bit requires O(2 n ) queries), and guessing the (n) -Õ(|C n |)/2 n missing membership bits at random. Note that self-amplifiable average-case hardness is especially interesting when the circuit C n is allowed to run in time larger than 2 n (for small circuits, of size much smaller than 2 n , the standard average-case hardness notion already bounds their probability of guessing correctly a single entry of L( x)). In this range, the poly(n) factor in our definition is absorbed in the Õ(|C n |) term in the exponent (note also that adversaries of size larger than 2 O(n) • (n) can solve the full challenge by brute-force).

Our main result rules out black-box reductions from any exponentially selfamplifiable average-case hard language to fine-grained one-way functions, with arbitrarily small hardness gap. Slightly more formally, we prove the following theorem:

Theorem 14 (Informal).

There exists an oracle O and an oracle language L O such that for any fine-grained one-way function f , there exists an (inefficient) adversary A that inverts f with probability close to 1 such that L remains exponentially self-amplifiable average-case hard against any candidate reduction C given oracle access to both O and A.

We prove Theorem 14 which is phrased in terms of reductions by establishing Theorem 15 which is phrased in terms of oracle worlds.

Theorem 15 (Language Hardness and Good Inversion, Informal).

There exists an oracle O and an oracle Inv such that for all oracle functions f , there exists an inverter A of size |A| = Õ(|f |) which, given oracle access to (O, Inv) and input (f, y), outputs a preimage of y with respect to f O with probability close to 1. Moreover, there exists an oracle language L O which is exponentially self-amplifiable average case hard against any candidate reduction C given oracle access to (O, Inv).

Theorem 15 is slightly different from our main theorem: the inverter A is now required to be efficient, but gets the help of an additional oracle Inv. Furthermore, the reduction C is now given oracle access to (O, Inv) instead of (O, A); the implication follows from the fact that the code of A is linear in its input size, and thus, its code can be hardcoded into the code of C, hence the reduction C O,A in our main theorem can be emulated by a reduction C O,Inv A in Theorem 15, where |C A | ≈ |C|. To prove Theorem 15, we rely on a standard method in oracle separations: we first prove a variant of Theorem 15 with respect to a distribution over oracles O, Inv (where both the success probability of the inverter and the probability of breaking the self-amplifiable average-case hardness of L will be over the random choice of O, Inv as well). Then, we apply the Borel-Cantelli lemma to show that with measure 1 over the choice of the oracle, the oracle is "good" and thus, in particular, a single good oracle exists as required by Theorem 15. In summary, to prove Theorem 15 we prove two theorems relative to an explicit distribution T over oracles O, Inv:

Theorem 16 (Language Hardness, Informal). For any : N → N, circuit family C = {C n } n , and for all large enough n ∈ N,

Pr x←${0,1} •n ,(O,Inv)←$T C O,Inv n ( x) = L O ( x) ≤ poly(n) • 2 -(n)- Õ(|Cn |) 2 O(n) .
Theorem 17 (Efficient Inversion, Informal). Let f : {0, 1} * → {0, 1} * be an oracle function. There exists an efficient inverter A O,Inv (f, .) for f . More precisely, A is of size |A| = Õ(|f |) and for sufficiently large m ∈ N, it holds that

Pr z←${0,1} m ,(O,Inv)←$T f O (A O,Inv (f, f O (z))) = f O (z) ≈ 1.

Defining the Oracle Distribution T

The distribution T samples a triple (W, B, H) where:

-B defines a random language L: for every x ∈ {0, 1} * , B[x] is set to 0 or 1 with probability 1/2; -W defines a set of random witnesses: for any n ∈ N and x ∈ {0, 1} n , W [x] is set to a uniformly random bitstring w x of length n. -H contains a pairwise independent hash-function for each triple (i, C, y), where i ∈ N, C is an encoding of a circuit and y is a bitstring.

A sample (W, B, H) from T defines a pair of oracles (O, Inv), where the oracle O = (Chk, Pspace) is defined as follows:

-Chk is a membership checking oracle: on input (x, w), it returns ⊥ if W [x] = w, and B[x] otherwise. Note that this means that relative to Chk, L is a random language in NP ∩ co-NP, since Chk allows to check both membership and non-membership in L, given the appropriate witness. A hit is a query to Chk which does not output ⊥. To emphasize the dependency of L on O, we use the notation L O .

-Pspace is a PSPACE oracle which allows the caller to efficiently perform computations that do not involve calls to the oracles Chk, Inv.

We now turn our attention to the oracle Inv, which is the most involved component: Inv must be defined such that there is an efficient oracle algorithm A which can, given access to O, Inv, invert any candidate one-way function f O , yet no algorithm (reduction) can break the self-amplifiable average-case hardness of the language L O given access to O, Inv. Hence, the goal of Inv is, given an input (f, y), to help compute preimages z of y with respect to the oracle function f O , but with carefully chosen safeguards to guarantee that Inv cannot be abused to decide the language L O . Our solution relies on two crucial safeguards, which we describe below.

First Safeguard: Removing Heavy Paths. The oracle Inv refuses to invert functions f on outputs y if the query-path from the preimage z to y in f O is "too lucky" with respect to O. To understand this, consider the following folklore construction of a worst-case one-way function f : on input (x, w), it queries Chk(x, w) and outputs (x, 1) if the check succeeds, and (x, 0) otherwise. Then, querying Inv on input (f, (x, 1)) allows the adversary to find the witness w associated to x efficiently, since the function f makes only a single query and thus the inversion query Inv(f, (x, 1)) has small cost for A.

But since f O is a normal (average-case) one-way function, we can allow the oracle to not invert on a too lucky evaluation path, if we can show that it still inverts sufficiently often. Concretely, on input (f, y), the oracle Inv computes the set S of all paths from an input z to y = f O (z), defined as the sequence of input-output pairs. Then, for all k ≤ |f |, Inv discards from this set S all k-heavy paths, i.e., the paths along which the number of Chk hits on k-bit inputs is much higher7 than expected, i.e., N (k)/2 k-1 , where N (k) is the number of Chk gates with k-bit inputs in f .

If S is not empty, then Inv samples a uniformly random element from S and returns the set of queries made on the path to the adversary. Since oracles need to be deterministic, we derandomize the sampling via the use of the pairwise independent hash-function stored in the third output H of T at H[log|S|, f, y] by the Valiant-Vazirani [START_REF] Valiant | NP is as easy as detecting unique solutions[END_REF] trick that ensures that with probability 1 8 , there is only a unique value in S that hashes to 0 log(|S|-1) . Note that it suffices to return the set of query-answer pairs, as the adversary can use the Pspace oracle to find an input z that leads to y with this set of query-answer pairs produced by f O . I.e., the Pspace uses the set to emulate the answers to queries made by f and discards a candidate z as soon as it makes a query not in the set.

Let us return to the issue of k-lightness. Firstly, note that we need to check for lightness for all values k, since the oracle Inv accepts functions that make queries to Chk on different k-values, and the Inv-oracle does not "know" the length of the x i -values for which C tries to decide membership. Secondly, we now need to clarify that we consider the number of hits as too high above its expected value if there are more than O(N (k))/2 k + log 2 (|f |) k-hits on the evaluation path. In this case, if |f | = O(2 k ), then on input length k, the adversary could essentially get the same number of hits without Inv queries by using a circuit of slightly bigger size Õ(|f |) that only makes Chk queries. The point of the additive log 2 |f | term is to ensure (via a concentration bound) that on a uniformly random input z, the probability that the path on z is light is at least 1 -1 superpoly|f | (while at the same time, the language hardness is maintained).

In turn, when |f | is smaller than, say, 2 k 6 , then the additive log 2 |f | term turns out to allow for too many hits. In this case, the probability of making even a single hit is 2 -5(k-1) 6 and thus exponentially small in k whereas O(N (k))/2 k + log 2 |f | might potentially allow for many hits. Thus, before performing all steps described in the first saveguard, we first replace f by a shaved function f s , described below.

Second Safeguard: Shaving High Levels. We shave all Chk-gates of |f | that are for large input length k, i.e., for all Chk-gates with input length k such that |f | ≤ 2 k 6 . To do so, we replace f by a shaved function f s where the answers of such Chk queries are hardcoded to be ⊥. The probability (over O and z) that this changes the behaviour of f is equal to the probability of making a hit on one of these high levels and thus 2 -5(k-1) 6 for the smallest k such that |f | ≤ 2 k 6 , i.e., k ≥ 6 log(|f |). Thus, 2 -5(k-1) 6 ≤ m -3 , where m = |z|. Note that later, in the Borel-Cantelli Lemma, we need to sum over these bad events, and thus, it is important that the sum of m -3 over all m is a constant.

Putting Everything Together. Finally, with the above two safeguards, our oracle Inv works as follows: on input (f, y), it first shaves f of its higher-level Chk gates, computing f s ← shave(f ). Then, it constructs the set S of all paths from some input z to y = f O s (z), where a path is defined to be the set of all query pairs to O made during the evaluation of f s on z. Afterwards, it removes from S all paths which are too heavy, where a path is called heavy if there is a k such that it contains a number N (k) k-Chk queries, out of which more than O(N (k))/2 k + log 2 |f | are hits. Eventually, it returns a path from this set S of light paths using the hashing trick to derandomize the sampling.

As we already outlined, the last output H of T is therefore a set which contains, for every possible triple (i, f, y) where i is an integer, f is an oracle function, and y is a bitstring, a hash function h = H[i, f, y]. The guarantee offered by h is that for any set S of size 2 i-1 ≤ |S | ≤ 2 i , the probability of the random choice of h = H[i, f, y] that S contains exactly one entry s such that h(s) = 0 is at least 1/8. Hence, after it computes the set S of light paths, Inv compute the unique integer i such that 2 i-1 ≤ |S| ≤ 2 i , retrieves h ← H[i, f, y], and output the unique path p ∈ S such that h(p) = 0, or ⊥ if there is no unique such path. Note that this oracle Inv can fail to return a valid path from an input z to the target output y in f for three reasons: because shaving caused f s to differ from f on input z (we show that this is uniquely for a random z), because the path from z to y is heavy (again, we show that this is unlikely), and because there is not a unique p ∈ S such that h(p) = 0 (but with probability at least 1/8, there will be a unique such p). This last source of failure can be later removed by a straightforward parallel amplification, by querying Inv on many pairs (f k , y) where the f i are functionally equivalent variants of f (in which case the corresponding h k = H[i, f k , y] are independently random by construction). Note that we could have also hardcoded "true" randomness into Inv instead of using the hashing trick. However, as we will see, the hashing trick enables a compression argument since (a) the hash-functions are sampled independently from W and B and (b) the sampling can be emulated when only knowing a single element in the set as well as the size of the set S. Details follow in the next section.

Proving Theorem 16

Fix a function : N → N, a circuit family C, and an integer n ∈ N. We want to bound the probability, over the choice of x ←$ {0, 1} (n)•n and (O,

Inv) ←$ T , that C O,Inv n ( x) = L O ( x).
We proceed in two steps:

-First, we prove an emulation lemma which states that there is an explicit After trying all inputs to f , Emu has a set S of candidate inputs z, with a corresponding path. Then, it retrieves the index i from I and selects h ← H[i, f, y], and sets the output of Inv on (f, y) to be the unique path p associated to some z ∈ S such that h(p) = 0; by construction, there will be a unique such path. The correctness of the emulation follows by construction and by definition of the sets (W¯ x , B¯ x , W Hit , B Hit , W Hit ) which Emu gets as input.

This emulation highlights the rationale behind the design of Inv: the use of a hash function h to select the output guarantees that, on top of the sets (W¯ x , B¯ x , W Hit , B Hit , W Hit ), Emu will only need to receive a relatively small amount of additional "leakage", corresponding to the list of all values i for each query to Inv. Now, by definition, i is at most log |S|, where S is a set of paths in f , hence |S| ≤ 2 |f | . Therefore, i ≤ |f |, hence i can be represented using at most log |f | bits. By construction, a query (f, y) to Inv can leak information about x only if |f | ≥ 2 n/C , because otherwise all n-Chk gates gets removed by shave(f ). Hence, our emulator gets a total amount of leakage about x bounded by |C n |/2 O(n) . From there, we want to prove that

Pr x←${0,1} •n ,(O,Inv)←$T C O,Inv n ( x) = L O ( x) ≤ poly(n) • 2 -(n)- Õ(|Cn |) 2 O(n) .
We will do so by proving that

Pr x←${0,1} •n ,(O,Inv)←$T Emu O (L, x, C n ) = L O ( x) ≤ poly(n) • 2 -(n)- Õ(|Cn|) 2 O(n)
.

(1) Bounding Eq. 1 is the goal of the hitting lemma.

Applying the Hitting Lemma. The hitting lemma states that for any circuit C n , any algorithm A having only access to the inputs and oracles of C n 's emulator (i.e., B has only access to the oracle O and L) cannot possibly make too many hit, even though the emulator gets |C n |/2 O(n) bits of leakage about the oracle. Let Hit O B (L, x, C n ) be the random variable that counts the number of hits on x made by A on input (L, x, C n ).

Lemma 18 (Hitting Lemma with Advice, Informal). For every (•), positive integers q, large enough n, challenge x, L with |W Hit | = q and list I represented by a string length |I| = |C n |/2 O(n) , adversaries C n , B, and for every integer c ≥ 1,

Pr (W,B,H)←T |L Ī Hit O B (L, x, C n ) ≥ O(|C n |) + q 2 n + c + |I| ≤ 1 2 γ•c ,
where γ > 1, and where the probability is taken over the random sampling of (W, B, H) ←$ T , conditioned on L.

We first explain how the hitting lemma implies Eq. 1. First, if Emu O got a total number of hits t on x, either through queries to O or through the hits contained in W Hit , then conditioned on all observation seen by Emu, (n) -t bits of L O ( x) are truly undetermined. Hence,

Pr x←${0,1} •n ,(O,Inv)←$T Emu O (LĪ , x, C n ) = L O ( x) Emu gets ≤ t hits on x ≤ 2 -( -t) .
Now, the number of hits seen by Emu is bounded by

Hit O Emu (LĪ , x, C n )+|W Hit |, where |W Hit | is at most poly(n)• Õ(|Cn|)
2 n : this follows from the fact that the number of hits in W Hit is bounded by design by the fact that Inv on input (f, y) only returns light paths, which cannot contain more than poly(n)

• Õ(|f |) 2 n
hits. The result follows by relying on the fact that

Pr x←${0,1} •n ,(O,Inv)←$T Emu O (LĪ , x, C n ) = L O ( x) = t Pr[Emu gets ≤ t hits on x] • Pr Emu O (LĪ , x, C n ) = L O ( x) | Emu gets t hits ≤ t 2 -( -t) • Pr[Emu gets ≤ t hits on x].
Now, the bound of Eq. 1 will be obtained by plugging the bound on

Pr[Emu gets ≤ t hits on x] ≤ Hit O Emu (L, x, C n ) + |W Hit |,
by using the hitting lemma to bound Hit O Emu (L, x, C n ). The proof then follows from the hitting lemma, to which we devote Sect. 6.

Proving Theorem 17

Let f : {0, 1} * → {0, 1} * be an oracle function. We exhibit an efficient inverter A Inv (f, .) for f , such that

Pr z←${0,1} m ,(O,Inv)←$T f O (A O,Inv (f, f O (z))) = f O (z) ≈ 1.
A works as follows: to invert a function f : {0, 1} m → {0, 1} * given an image y, it queries Inv log 3 m times on independent inputs (f k , y), where each f k are syntactically different but functionally equivalent to f (this guarantees that the failure probabilities introduced by the choice of the hash function h are independent). Then, it takes a path p returned by any successful query to Inv (if any), and returns a uniformly random preimage z consistent with this path (this requires a single query to the PSPACE oracle). The proof that A is a successful inverter proceeds by a sequence of lemmas. First, we define f approx as f s = shave(f ), except that it outputs ⊥ on any input z such that the path in f O s (z) is not light. When A makes a single query to Inv, its overall success probability is approximately 1/8. Since all queries have independent probability of failing due to an unfortunate choice of h, we will show that A inverts successfully with probability

The Hitting Lemma

For any r = r 1 • • • r , we define an oracle Guess r (i, r * ) as taking an input r * and an index i and checking whether r i = r * . If so, the oracle returns 1. Else, the oracle returns ⊥. We define Hit Guess r (A) as the number of distinct queries A makes which returns something different than ⊥.

Lemma 19 (Abstract Hitting Lemma). For every positive integer q, large enough n,

= (n), sets V 1 , • • • , V of size 1 ≤ |V i | ≤ 2 n such that q = • 2 n - i=1 |V i |,
for every adversary A, and for every integer c ≥ 1, ∃α > 0, ∃γ > 1:

Pr r←$V1ו••×V Hit Guess r (A) ≥ 16 • qry A + q 2 n + c ≤ α 2 γc .
The hitting lemma gives a strong Chernoff-style bound on the number of distinct hits which an arbitrary adversary A can make using qry A queries. The strength of this bound allows to show that the bound degrades gracefully even if A is additionally given an arbitrary advice string of bounded size about the truth table of the Guess oracle. We discuss applications and variants of the Hitting Lemma in the full version of this work [START_REF] Brzuska | Towards fine-grained one-way functions from strong average-case hardness[END_REF], and now turn to its proof. The goal of A is to find as many distinct r i 's as possible, where each r i is sampled randomly from a set V i of size |V i | ≤ 2 n , given access to an oracle which indicates whether a guess is correct or not. Intuitively, A's best possible strategy is to first choose the smallest set V i1 , query its elements to Guess (in arbitrary order) until it finds r i1 , then move on to the second smallest set V i2 , and so on. The proof of the abstract hitting lemma closely follows this intuition: we first show that this strategy is indeed the best possible strategy, then bound it's success probability using a second moment concentration bound. Formally, for any Q ≥ 1, let B Q be a Q-query adversary that implements the following simple strategy: order V 1 , • • • , V by increasing size, as V σ(1) , • • • , V σ( ) for some fixed permutation σ such that |V σ(1) | ≤ • • • ≤ |V σ( ) |. For every i ≤ , let v i ← |V σ(i) |, and let f i be an arbitrary bijection between [v i ] and V σ(i) . The algorithm B Q is given on Fig. 3. The adversary B Q sequentially queries the values of the sets V i ordered by increasing size, following an arbitrary ordering of the values inside each V i , until it finds r i (after which it moves to the next smallest larger set) or exhausts its budget of Q queries. To simplify notations, for any vector u ∈

Proof of the Hitting Lemma -Proof Structure

[v 1 ] × • • • × [v ],
we write π( u) = f -1 1 (u σ -1 (1) ), • • • , f -1 (u σ -1 ( ) ). Observe that for any t ∈ N,

Pr r←$V1ו••×V Hit Guess r (B Q ) ≥ t = Pr u←$[v1]ו••×[v ] Hit Guess π( u) (B Q ) ≥ t = Pr u←$[v1]ו••×[v ] t i=1 u i ≤ Q ,
where the last equality follows from the fact that B Q queries the positions one by one in a fixed order, and needs exactly u i queries to find r σ(i) = f σ(i) (u i ) for i = 1 to t. The proof of the hitting lemma derives directly from two claims. The first claim states that no Q-query adversary can make t distinct hits with probably better than that of B Q :

Claim 2 (B Q 's strategy is the best possible strategy). For every integers n, Q, = (n), sets V 1 , .., V of size 1 ≤ |V i | ≤ 2 n , and for any Q-query algorithm A and integer t,

Pr r←$V1ו••×V Hit Guess r (A) ≥ t ≤ Pr u←$[v1]ו••×[v ] t i=1 u i ≤ Q .
By construction, the average number of hits E r [Hit Guess r (B Q )] made by B Q is the largest value m such that m i=1 vi+1 2 ≤ Q. Recall that q = • 2 n -i=1 |V i | = •2 n -i=1 v i and v i ≤ 2 n for every i, which implies in particular that m i=1 v i ≥ m • 2 nq. We thus bound m as a function of Q, q, and 2 n :

m i=1 v i + 1 2 ≤ Q ⇐⇒ m + m i=1 v i ≤ 2Q =⇒ m + m • 2 n -q ≤ 2Q ⇐⇒ m ≤ 2Q + q 2 n + 1 .
The second claim states, in essence, that the probability over r that B Q does t hits decreases exponentially with the distance of t to the mean m (up to some multiplicative constant).

Claim 3 (Bounding B Q 's number of hits). There exists constants α > 0 and γ > 1 such that for every (•), positive integers q, Q, large enough n, integers v 1 , • • • , v with 1 ≤ v i ≤ 2 n such that q = • 2 n -i=1 v i , and for every integer c ≥ 1,

Pr u←$[v1]ו••×[v ] t i=1 u i ≤ Q ≤ α 2 γc , where t = 16 • Q + q 2 n + c.
We prove Claim 2 and Claim 3 in the full version of this work [START_REF] Brzuska | Towards fine-grained one-way functions from strong average-case hardness[END_REF].

Fig. 1 .

 1 Fig. 1. Impagliazzo's five worlds

Definition 6 (

 6 Fine-Grained One-Way Function). Let ε : N → R + be a positive function and δ > 0 be a constant. A function f : {0, 1} * → {0, 1} * is an (ε, δ)-fine-grained one-way function if for all circuit families C = {C m } m∈N and all large enough m, if |C m | < |f m | 1+δ , then we have

Definition 7 (

 7 Fine-Grained One-Way Function Distribution). Let ε : N → R + be a positive function and δ > 0 be a constant. A distribution D over functions f : {0, 1} * → {0, 1} * is an (ε, δ)-fine-grained one-way function distribution if for all circuit families C = {C m } m∈N and all large enough m, if |C m | < |f m | 1+δ for all f in the support of D, then it holds that

Fig. 2 .

 2 Fig. 2. Distribution T for sampling a random language L O = {x ∈ {0, 1} * | B[x] = 1} with associated list of witnesses W . The oracle O = Chk[W, B] allows to check membership of a word x ∈ L O given witness W [x].

First Lemma.

  The first lemma states thatPr O,z←${0,1} m f O approx (z) = f O s (z) ≈ 1.This lemma will follow again from the Hitting lemma, which provides a strong concentration bound on the probability that the path of f O s (z) is light: by this concentration bound, it follows that the path is light with probability at least 1log |f | • 2 -O(log 2 |f |) (recall that a path is heavy if, for some k, it contains N (k) k-Chk queries, and more than O(N (k)) + log 2 |f | hits).Second Lemma. The second lemma states thatPr O,z←${0,1} m f O s (z) = f O (z) ≈ 1.This lemma follows from the definition of shaving: since only Chk gates with k ≥ 6 log |f | are shaved, the probability thatf O s (z) = f O (z) is bounded by the sum k≥6 log(|f |) 2 -5k6 ≤ 4/m 3 . Combining the above lemmas with an averaging argument, we will show that Pr z←${0,1} m f (f -1 approx (f (z), 1 m )) = f (z) ≈ 1.

Pr.

  z←${0,1} m ,(O,Inv)←$T f O (A O,Inv (f, f O (x))) = f O (x) ≈ 1 -Note that A, on input f , sends log 3 m ≤ log 3 |f | queries to Inv,selects one of the path from the successful queries, and queries it to the PSPACE oracle to select the preimage z it outputs. Therefore, the size of A is |A| = Õ(|f |).

Fig. 3 .

 3 Fig. 3. Q-query adversary BQ

  algorithm Emu O which emulates C O,Inv n without calling the oracle Inv, but using instead some partial information g(W, B, H) about (W, B, H). By emulating, we mean that Emu O ( x, g(W, B, H)) = C O,Inv Emu makes the same number of queries to O as C n . -Second, we use the hitting lemma, which we already mentioned in Sect. 3 (in the technical overview about the existence of FG-OWFs in the RLM), to bound the number of hits on x that Emu can possibly make (where a hit on x is a query of the form (x Emu makes the same queries to O as C n , where the leakage string L contains the following information: -The sets H and (W¯ x , B¯ x ) of all witnesses and membership bits except for those corresponding to the entries of x (intuitively, this corresponds to giving to Emu all information about Inv which is sampled independently of the W [x i ], B[x i ] and does not help with finding L O ( x)). -The sets (W Hit , B Hit ) which contains all Chk-hits on x in paths obtained by C n through queries to Inv. -The set W Hit which contains all other (non-hitting) Chk-query pairs in paths obtained by C n through queries to Inv. -A list I which for each query (f, y) of C n to Inv indicates whether this query returned ⊥ or not, and if it did not, the value i which was used to select the hash function h = H[i, f, y]. Emu runs f O (z) by retrieving the answers of O from the sets (W¯ x , B¯ x , W Hit , B Hit , W Hit ). If f O (z) makes a query whose answer is not contained in these sets or if f O (z), Emu discards candidate z.

n ( x), and i , W [x i ]) to Chk, from which Emu learns whether

x i ∈ L O ).

The Emulation Lemma. Concretely, we give an explicit algorithm

Emu such that Emu O (L, x, C n ) = C O,Inv n ( x) and

The emulation proceeds by using its information: Emu runs C n internally on input x, forwarding its queries to O. Each time C n makes a query (f, y) to Inv, Emu first retrieves from I the information whether Inv outputs ⊥ or not. If it does not, Emu tries all possible inputs z to f O , but without actually querying O: for each possible input z,

Though we heard that lately, some cryptographers have been found dreaming of an even higher heaven, the mysterious land of Obfustopia.

Ralph Merkle, 1974 project proposal for CS 244 at U.C. Berkeley, http://www. merkle.com/1974/.

Of course, this heuristic is simplified: most real languages can have more than a single witness, and the choice of having |w| = |x| is a somewhat arbitrary way of tuning the hardness to make it exactly 2 n . Still, we believe that there is value in using a simple model to heuristically analyze the plausibility of an assumptioneven though, as any heuristic model, it must fail on artificial counter examples

.4 More precisely, it requires 2 n-1 calls to Chk on the average to find a witness of language membership if x is indeed in the language. In turn, it requires 2 n calls to confirm that there is indeed no witness if x is not in the language.

More formally, since we consider an oracle sampled from a distribution over oracles, as for the Random Oracle Model, this captures average-case hard language distributions. I.e., the hardness of a language is averaged over the choice of the instance and the sampling of the oracle.

 6 We thank an anonymous reviewer for pointing out this construction.

Determining an appropriate bound on much higher is crucial to avoid that deciding L O becomes too easy. We return to this issue shortly.

Acknowledgements. We thank Félix Richart for help with the experimental verification of some probability claims, and the anonymous Eurocrypt reviewers for their careful proofreading of the paper. C. Brzuska supported by the academy of Finland. G. Couteau supported by the ANR SCENE.