© International Association for Cryptologic Research 2020
R. Pass, K. Pietrzak (eds.)Theory of CryptographyLecture Notes in Computer Science12552https://doi.org/10.1007/978-3-030-64381-2_22

On Average-Case Hardness in $$\mathsf {TFNP}$$ from One-Way Functions

Pavel Hubáček1  , Chethan Kamath2  , Karel Král1   and Veronika Slívová1  
(1)
Charles University, Prague, Czech Republic
(2)
Northeastern University, Boston, USA
 
 
Pavel Hubáček (Corresponding author)
Email: hubacek@iuuk.mff.cuni.cz
 
Chethan Kamath
Email: ckamath@protonmail.com
 
Karel Král
Email: kralka@iuuk.mff.cuni.cz
 
Veronika Slívová
Email: slivova@iuuk.mff.cuni.cz

Abstract

The complexity class $$\mathsf {TFNP}$$ consists of all $$\mathsf {NP}$$ search problems that are total in the sense that a solution is guaranteed to exist for all instances. Over the years, this class has proved to illuminate surprising connections among several diverse subfields of mathematics like combinatorics, computational topology, and algorithmic game theory. More recently, we are starting to better understand its interplay with cryptography.

We know that certain cryptographic primitives (e.g. one-way permutations, collision-resistant hash functions, or indistinguishability obfuscation) imply average-case hardness in $$\mathsf {TFNP}$$ and its important subclasses. However, its relationship with the most basic cryptographic primitive –  i.e., one-way functions (OWFs) – still remains unresolved. Under an additional complexity theoretic assumption, OWFs imply hardness in $$\mathsf {TFNP}$$ (Hubáček, Naor, and Yogev, ITCS 2017). It is also known that average-case hardness in most structured subclasses of $$\mathsf {TFNP}$$ does not imply any form of cryptographic hardness in a black-box way (Rosen, Segev, and Shahaf, TCC 2017) and, thus, one-way functions might be sufficient. Specifically, no negative result which would rule out basing average-case hardness in $$\mathsf {TFNP}$$ solely on OWFs is currently known. In this work, we further explore the interplay between $$\mathsf {TFNP}$$ and OWFs and give the first negative results.

As our main result, we show that there cannot exist constructions of average-case (and, in fact, even worst-case) hard $$\mathsf {TFNP}$$ problem from OWFs with a certain type of simple black-box security reductions. The class of reductions we rule out is, however, rich enough to capture many of the currently known cryptographic hardness results for $$\mathsf {TFNP}$$. Our results are established using the framework of black-box separations (Impagliazzo and Rudich, STOC 1989) and involve a novel application of the reconstruction paradigm (Gennaro and Trevisan, FOCS 2000).

Keywords
TFNPPPADAverage-case hardnessOne-way functionsBlack-box separations.

1 Introduction

The complexity class $$\mathsf {TFNP}$$ ofî total search problems [41], i.e., with syntactically guaranteed existence of a solution for all instances, holds a perplexing place in the hierarchy of computational complexity classes. The standard method for arguing computational hardness in $$\mathsf {TFNP}$$ is via clustering these problems into subclasses characterised by the existential argument guaranteeing their totality [42]. This approach was particularly successful in illuminating the connections between search problems in seemingly distant domains such as combinatorics, computational topology, and algorithmic game theory (see, for example, [14, 17, 18, 23, 37] and the references therein). However, all results of this type ultimately leave open the possibility of the existence of polynomial time algorithms for all of $$\mathsf {TFNP}$$.

An orthogonal line of work, which can be traced to Papadimitriou [42], shows the existence of hard problems in subclasses of $$\mathsf {TFNP}$$ under cryptographic assumptions. Such conditional lower bounds for structured subclasses of $$\mathsf {TFNP}$$ were recently given under increasingly more plausible cryptographic assumptions [6, 7, 11, 12, 16, 20, 28, 33, 38]. The end of the line in this sequence of results would correspond to a “dream theorem” establishing average-case hardness in one of the lower classes in the $$\mathsf {TFNP}$$ hierarchy (e.g. $$\mathsf {CLS}$$ [15]) under some weak general cryptographic assumptions (e.g. the existence of one-way functions).

An informative parallel for the limits of this methodology can be drawn by considering average-case hardness of decision problems (i.e., languages) in $$\mathsf {NP} \cap \mathsf {coNP} $$. The existence of a hard-on-average decision problem in $$\mathsf {NP} \cap \mathsf {coNP} $$ follows from the existence of hard-core predicates for any one-way permutation [24]. However, the existence of injective one-way functions is insufficient for black-box constructions of hard-on-average distributions for languages in $$\mathsf {NP} \cap \mathsf {coNP} $$ even assuming indistinguishability obfuscation [5] (in fact, [5] ruled out even black-box constructions of worst-case hardness in $$\mathsf {NP} \cap \mathsf {coNP} $$ using these cryptographic primitives).

For total search problems, the existence of hard-on-average $$\mathsf {TFNP}$$ distributions is straightforward either from one-way permutations or collision-resistant hash functions. Moreover, there exist constructions of hard-on-average $$\mathsf {TFNP}$$ distributions either assuming indistinguishability obfuscation and one-way functions [7, 20] or under derandomization-style assumptions and one-way functions [27]. On the other hand, no analogue of the impossibility result for basing average-case hardness in $$ \mathsf {NP} \cap \mathsf {coNP} $$ on (injective) one-way functions [5] is currently known for $$\mathsf {TFNP}$$. Rosen, Segev, and Shahaf [47] showed that most of the known structured subclasses of $$\mathsf {TFNP}$$ do not imply (in a black-box way) any form of cryptographic hardness; thus, it is plausible that hard-on-average distributions in $$\mathsf {TFNP}$$ can be based solely on the existence of one-way functions.

Rosen et al. [47] also provided some insight into the structure of hard-on-average distributions in $$\mathsf {TFNP}$$. They showed that any hard-on-average distribution of a $$\mathsf {TFNP}$$ problem from any primitive which exists relative to a random injective trapdoor function oracle (e.g. one-way functions, injective trapdoor functions, or collision-resistant hash functions) must result in instances with a nearly exponential number of solutions. Even though the [47] result restricts the structure of hard-on-average distributions in $$\mathsf {TFNP}$$ constructed from these cryptographic primitives, it certainly does not rule out their existence. Indeed, a collision-resistant hash function constitutes a hard-on-average $$\mathsf {TFNP}$$ distribution, albeit with an exponential number of solutions.

Motivated by the significant gap between negative and positive results, we revisit the problem of existence of average-case hardness in $$\mathsf {TFNP}$$ under weak general cryptographic assumptions and address the following question:
$$\begin{aligned} \begin{array}{c} Are~(injective)~one \text {-}{} way~functions~sufficiently~structured~to~imply \\ hard \text {-}{} on \text {-}{} average~total~search~problems? \end{array} \end{aligned}$$
Towards answering this question, we provide negative results and show that simple fully black-box constructions of hard-on-average $$\mathsf {TFNP}$$ distributions from injective one-way functions do not exist.

1.1 Our Results

We recall the details of the construction of a hard-on-average distribution in $$\mathsf {TFNP}$$ from one-way permutations to highlight the restrictions on the type of reductions considered in our results.

Consider the total search problem $$\textsc {Pigeon}$$, in which you are given a length-preserving n-bit function represented by a Boolean circuit $$\mathsf {C}$$ and are asked to find either a preimage of the all-zero string (i.e., $$x\in \{0,1\}^n:\mathsf {C}(x)=0^n$$) or a non-trivial collision (i.e., $$x\ne x'\in \{0,1\}^n:\mathsf {C}(x)=\mathsf {C}(x')$$). $$\textsc {Pigeon}$$ is complete for a subclass of $$\mathsf {TFNP}$$ known as $$\mathsf {PPP}$$, and Papadimitriou [42] gave the following construction of a hard $$\textsc {Pigeon}$$ problem from one-way permutations. Given a (one-way) permutation $$f:\{0,1\}^n\rightarrow \{0,1\}^n$$ and a challenge $$y\in \{0,1\}^n$$ for inversion under f, the reduction algorithm defines an instance of $$\textsc {Pigeon}$$ by the oracle-aided circuit $$\mathsf {C}^f_y$$ computing the function $$\mathsf {C}^f_y(x)=f(x)\oplus y$$. It is not hard to see that the instance of $$\textsc {Pigeon}$$ $$\mathsf {C}^f_y$$ has a unique solution corresponding to the preimage of y under f and, therefore, any algorithm solving it breaks the one-wayness of f.

Note that the above construction of a hard (on average) $$\mathsf {TFNP}$$ problem is extremely simple in various aspects:

  • The construction is fully black-box, i.e., the $$\textsc {Pigeon}$$ instance can be implemented via an oracle-aided circuit treating the one-way permutation as a black-box and the reduction inverts when given oracle access to an arbitrary solver for $$\textsc {Pigeon}$$.

  • The reduction is many-one, i.e., a single call to a $$\textsc {Pigeon}$$-solving oracle suffices for finding the preimage of y.

  • The reduction is f-oblivious, i.e., the oracle-aided circuit $$\mathsf {C}^f_y$$ defining the $$\textsc {Pigeon}$$ instance depends only on the challenge y and does not depend on the one-way permutation f in the sense that $$\mathsf {C}^f_y$$ itself can be fully specified without querying f. In other words, given the challenge y, the instance $$\mathsf {C}^f_y$$ submitted to the $$\textsc {Pigeon} $$ oracle by the reduction is, as an oracle-aided circuit, identical for all permutations f.

  • The reduction is deterministic, i.e., it simply passes y to specify the $$\textsc {Pigeon}$$ instance.

Such a fully black-box construction of $$\textsc {Pigeon}$$ with a deterministic f-oblivious many-one reduction exists also assuming collision-resistant hash functions exist (folklore). Specifically, for any hash function $$h:\{0,1\}^n\rightarrow \{0,1\}^{n-1}$$ from the collision-resistant family, the $$\textsc {Pigeon}$$ instance is defined as $$\mathsf {C}^h(x)=h(x)\mathbin {\parallel }1$$, where $$\parallel $$ represents the operation of string concatenation. Since $$\mathsf {C}^h$$ concatenates the value h(x) with 1 for any input x, it never maps to the all-zero string and, therefore, has the same collisions as h. Note that, unlike in the above construction from one-way permutations, the instances resulting from collision-resistant hash functions do not have a unique solution. In fact, there are always at least $$2^{n-1}$$ nontrivial collisions (even in two-to-one functions where each $$y\in \{0,1\}^{n-1}$$ has exactly two preimages) and this structural property is inherent as shown by Rosen et al. [47]. Importantly, the property of having nearly exponentially many solutions is not in contradiction with the resulting distribution being hard-on-average. Currently, there is no actual evidence suggesting that average-case hardness in $$\mathsf {TFNP}$$ cannot be based on the existence of injective one-way functions.

The above constructions motivate us to study whether there exist such “simple” constructions of an average-case hard $$\mathsf {TFNP}$$ problem under weaker cryptographic assumptions such as the existence of injective one-way functions, and we answer this question in negative (see Sect. 3.2 for the formal statement of Theorem 1).

Theorem 1

(Main Theorem - Informal). There is no efficient fully black-box construction of a worst-case hard $$\mathsf {TFNP}$$ problem from injective one-way functions with a randomized f-oblivious non-adaptive reduction.

Thus, we actually rule out a larger class of fully black-box constructions with reductions to injective one-way functions than the deterministic f-oblivious many-one reductions from the motivating examples of average-case hardness of $$\textsc {Pigeon}$$ from one-way permutations, respectively collision-resistant hash functions. We rule out even constructions of worst-case hard $$\mathsf {TFNP} $$ problems using randomized f-oblivious non-adaptive1 reductions. The formal definitions of fully black-box constructions with f-oblivious non-adaptive reductions are given in Sect. 3.1 (see Definition 2 and Definition 3).

Even though restricted, our results are the first step towards the full-fledged black-box separation of $$\mathsf {TFNP} $$ and (injective) one-way functions. We note that the full-fledged separation would necessarily subsume the known separation of collision-resistant hash functions and injective one-way functions [49], for which, despite the recent progress, there are only non-trivial proofs [4, 25, 40].

1.2 Our Techniques

Our results employ the framework of black-box separations [19, 30, 45]. The approach suggested in [30] for demonstrating that there is no fully black-box construction of a primitive P from another primitive Q is to come up with an oracle O relative to which Q exists, but every black-box implementation $$C^Q$$ of P is broken. However, as explained in [40, 45], this approach actually rules out a larger class of constructions (so-called “relativized” constructions), and to rule out just fully black-box constructions it suffices to use the so-called two-oracle technique [26]. Here, the oracle O usually consists of two parts: an idealised implementation of the primitive Q and a “breaker” oracle for primitive P. In our context, P corresponds to a $$\mathsf {TFNP}$$ problem and the oracle O comprises of a random injective function (which yields an injective one-way function) and a procedure $$\textsc {Solve}$$ which provides a solution for any instance of a $$\mathsf {TFNP}$$ problem. To rule out the existence of fully black-box constructions of hard-on-average $$\mathsf {TFNP}$$ problems from injective one-way functions, one then has to argue that access to such a “breaker” oracle $$\textsc {Solve}$$ for $$\mathsf {TFNP}$$ does not help any reduction R in inverting injective one-way functions. Designing such a $$\textsc {Solve}$$ oracle and then arguing that it does not help inverting injective one-way function, which we carry out using the reconstruction paradigm of Gennaro ond Trevisan [21], constitute the main technical challenges. Before giving an overview of these two steps, we explain the structural insight that is key to our separation, and guided us in the design of the two steps.

The Existence of a “Useless” Solution. At the core of our negative result is a new structural insight about $$\mathsf {TFNP}$$ instances constructed from (injective) one-way functions. Observe that any one-way function gives rise to a search problem with a hard-on-average distribution which is total over its support (but all instances outside its support have no solution). Specifically, for any one-way function $$f:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$$, an instance is any $$y\in \{0,1\}^{n+1}$$ and the solution for y is any $$x\in \{0,1\}^n$$ such that $$f(x)=y$$. The hard-on-average distribution then corresponds to sampling x uniformly from $$\{0,1\}^n$$ and outputting the instance $$y=f(x)$$ (as in the standard security experiment for one-way functions). When attempting to construct a hard search problem which is truly total and has a solution for all instances (not only for the support of the hard distribution), one has to face the frustrating obstacle in the form of “useless” solutions which do not help the reduction in inverting its challenge y. Note that, as the resulting $$\mathsf {TFNP}$$ problem must be total for all oracles f, there must exist a solution even for oracles with no preimage for the challenge y. By a simple probabilistic argument, it follows that for a random oracle f and a random challenge y, with overwhelming probability, there exists a solution to any $$\mathsf {TFNP}$$ instance which does not query a preimage of y, i.e., a “useless” solution from the perspective of the reduction.2

Thus, demonstrating a black-box separation would be straightforward if the $$\mathsf {TFNP}$$ solver knew which challenge y is the reduction attempting to invert. Our solver would simply output such a “useless” solution and we could argue via the reconstruction paradigm that no reduction can succeed in inverting y given access to our solver. In this work, we show that it is possible to construct a $$\mathsf {TFNP}$$ solver which returns such a “useless” solution with overwhelming probability even though the solver does not know the input challenge of the reduction.

Reduction-Specific $$\textsc {Solve}$$. Note that a reduction in a fully black-box construction must succeed in breaking the primitive P when given access to any oracle $$\textsc {Solve}$$ (see Definition 2). In other words, to rule out the existence of constructions with a fully black-box reduction, it is sufficient to show that for every reduction there exists a $$\textsc {Solve}$$ which is not helpful in inverting; in particular, $$\textsc {Solve}$$ may depend on the reduction. To enable $$\textsc {Solve}$$ to answer the reduction’s query with a “useless” solution with overwhelming probability, we take exactly this approach and construct a reduction-specific $$\textsc {Solve}$$ for any construction of a $$\mathsf {TFNP}$$ problem from injective one-way functions. We significantly differ in this respect from the previous works which relied on the reconstruction paradigm of Gennaro and Trevisan [21], e.g., the works which employed the collision-finding oracle of Simon [8, 25, 43, 46, 49]. We note that the possibility of designing a breaker oracle which depends on the fully black-box construction was exploited already by Gertner, Malkin, and Reingold [22], who considered $$\textsc {Solve}$$ which depends on the implementation rather than the reduction algorithm (as in our case). That is, to rule out the construction of a primitive P from a primitive Q, they considered an oracle $$\textsc {Solve}$$ that depends on the implementation $$C^Q$$ of the primitive P, whereas in our case $$\textsc {Solve}$$ depends on the reduction algorithm R that is supposed to break Q given access to an algorithm that breaks $$C^Q$$. The possibility of proving black-box separations via reduction-specific oracles was also observed in the work of Hsiao and Reyzin [26] who, nevertheless, did not have to leverage this observation in their proofs.

On a high level, given that $$\textsc {Solve}$$ can use the code of the reduction R, $$\textsc {Solve} $$ can simulate R on all possible challenges y to identify the set of challenges on which R outputs the present instance that $$\textsc {Solve}$$ needs to solve. As we show, the solution then can be chosen adversarially so that it avoids such solutions of interest to the reduction. To turn this intuition into a formal proof, one needs to show that our $$\textsc {Solve}$$ indeed does not help in inverting injective one-way functions and we do so along the lines of the reconstruction paradigm of [21].

Applying the Compression Argument. Two important subtleties arise in the proof when we try to turn the reduction into a pair of compression and decompression algorithms, which we explain next. First, the reconstruction paradigm is conventionally applied to random permutations [21, 25], whereas the reduction R and the algorithm $$\textsc {Solve} $$ are designed for random injective functions. The natural approach is to simply proceed with the same style of proof even in our setting. Specifically, one would presume that a similar incompressibility argument can be leveraged if we manage to somehow encode the image of the random injective function. While this intuition is correct in the sense that it allows correct compression and reconstruction, it turns out that the space required to encode the image is too prohibitive for reaching the desired contradiction with known information-theoretic lower bounds on the expected length of encoding for a random injective function. To resolve this issue, we construct compressor and decompressor algorithms for a random permutation, but we equip the algorithms with shared randomness in the form of a random injective function $$h:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$$ independent of the random permutation $$\pi :\{0,1\}^n\rightarrow \{0,1\}^{n}$$ to be compressed. Whenever the compressor and decompressor need to provide the reduction or $$\textsc {Solve} $$ with access to the injective function $$f:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$$, they compose the permutation $$\pi $$ with the shared injective function h and then pass off the composed injective function $$f=h\circ \pi $$ to the reduction. With this modification, we are able to show that any reduction which succeeds in inverting injective one-way functions given access to our $$\textsc {Solve}$$ can be used to compress a random permutation on $$\{0,1\}^n$$ below a standard information-theoretic lower bound on the size of a prefix-free encoding of such random variable. We note that this is reminiscent of the approach used in [40] for separating injective one-way functions from one-way permutations.

Second, we cannot employ the actual oracle $$\textsc {Solve}$$ in our compression and decompression algorithms: even though we can use the reduction when compressing and decompressing the random permutation, we must be able to consistently simulate $$\textsc {Solve}$$ without accessing the whole permutation. In general, the choice of the “breaker” oracle that can be simulated efficiently without too many queries to the permutation (e.g., the collision finding oracle of Simon [2, 49]) is a crucial part of the whole proof, and, a priori, it is unclear how to design a $$\mathsf {TFNP}$$ solver which also has such a property. Nevertheless, we show that there exists a $$\textsc {Solve}$$ which can be efficiently simulated given only (sufficiently small) partial information about the permutation.

f-Oblivious Reductions. As our $$\textsc {Solve}$$ simulates the reduction on possible challenges y, we need for technical reasons that the reduction is f-oblivious (namely, for correctness of our encoding and decoding algorithms). However, we believe that f-obliviousness is not overly restrictive as it is a natural property of security reductions. Besides the two fully black-box constructions of $$\textsc {Pigeon}$$ with f-oblivious reductions described in Sect. 1.1, f-oblivious security reductions appear also in the cryptographic literature – see for example the standard security reduction in the Goldreich-Levin theorem establishing the existence of hard-core predicate for any one-way function (note that this particular security reduction is also non-adaptive). An orthogonal notion of a $$\pi $$-oblivious construction appears in the work of Wee [50]. However, it is the implementation of the constructed primitive which is “oblivious” to the one-way permutation $$\pi $$ in his work.

1.3 Related Work

$$\mathsf {TFNP}$$ and its Subclasses. The systematic study of total search problems was initiated by Megiddo and Papadimitriou [41] with the definition of complexity class $$\mathsf {TFNP}$$. They observed that a “semantic” class such as $$\mathsf {TFNP}$$ is unlikely to have complete problems, unless $$\mathsf {NP} = \mathsf {coNP} $$. As a resolution, Papadimitriou [42] defined “syntactic” subclasses of $$\mathsf {TFNP}$$ with the goal of clustering search problems based on the various existence theorems used to argue their totality. Perhaps the best known such class is $$\mathsf {PPAD}$$ [42], which captures the computational complexity of finding Nash equilibria in bimatrix games [10, 14]. Other subclasses of $$\mathsf {TFNP}$$ include:

  • $$\mathsf {PPA}$$  [42], which captures computational problems related to the parity argument like Borsuk-Ulam theorem or fair division [18];

  • $$\mathsf {PLS}$$ [34], defined to capture the computational complexity of problems amenable to local search and its “continuous” counterpart $$\mathsf {CLS} \subseteq \mathsf {PLS} $$ [15] (in fact $$\mathsf {CLS} \subseteq \mathsf {PLS} \cap \mathsf {PPAD} $$), which captures finding the computational complexity of finding (approximate) local optima of continuous functions and contains interesting problems from game theory (e.g., solving the simple stochastic games of Condon or Shapley); and

  • $$\mathsf {PPP}$$ [42] and $$\mathsf {PWPP} \subseteq \mathsf {PPP} $$ [33], motivated by the pigeonhole principle and contain important problems related to finding collisions in functions.

The relative complexity of some of these classes was studied in [3] as it was shown using (worst-case) oracle separations that many of these classes are distinct.

Cryptographic hardness in $$\mathsf {TFNP}$$. Hardness from standard cryptographic primitives was long known for the “higher” classes in $$\mathsf {TFNP}$$ like $$\mathsf {PPP}$$ and $$\mathsf {PPA}$$. We have already mentioned that one-way permutations imply average-case hardness in $$\mathsf {PPP}$$ [42] and existence of collision-resistant hashing (e.g. hardness of integer factoring or discrete-logarithm problem in prime-order groups) implies average-case hardness in $$\mathsf {PPP}$$ (as well as in $$\mathsf {PWPP}$$). In addition, Jeřábek [33], building on the work of Buresh-Oppenheim [9], showed that $$\mathsf {PPA}$$ is no easier than integer factoring.

However, it is only recently that we are better understanding the cryptographic hardness of the lower classes in $$\mathsf {TFNP} $$. This was catalysed by the result of Bitansky et al. [7] who reduced hardness in $$\mathsf {PPAD}$$ to indistinguishability obfuscation (and injective OWFs) expanding on Abbot, Kane, and Valiant [1]; Hubáček and Yogev [28] extended this result to $$\mathsf {CLS} \subseteq \mathsf {PLS} \cap \mathsf {PPAD} $$. The underlying assumption was relaxed further to cryptographic assumptions that are more plausible than indistinguishability obfuscation in  [11, 12, 16]. Using similar ideas, Bitansky and Gerichter [6] presented a construction for hard-on-average distributions in the complexity class $$\mathsf {PLS}$$ in the random oracle model. Building on these results, a flurry of recent works [31, 32, 35, 36, 39] further weakened the assumptions required for proving average-case hardness in $$\mathsf {CLS} $$ to sub-exponential hardness of learning with errors, bringing us closer to proving average-case hardness in $$\mathsf {CLS} $$ under a standard concrete cryptographic assumption.

One-Way Functions and $$\mathsf {TFNP}$$. Hubáček et al. [27] showed that average-case hardness in $$\mathsf {NP}$$ (which is implied by OWFs) implies average-case hardness in $$\mathsf {TFNP}$$ under complexity theoretical assumptions related to derandomization. Pass and Venkitasubramaniam [44] recently complemented the [27] result by showing that when OWFs do not exist, average-case hardness in $$\mathsf {NP}$$ implies average-case hardness in $$\mathsf {TFNP}$$. However, a definitive relationship between OWFs and $$\mathsf {TFNP}$$ has remained elusive. This prompted Rosen et al. [47] to explore impossibility of reducing $$\mathsf {TFNP}$$ hardness to OWFs. They gave a partial answer by showing that there do not exist hard-on-average distributions of $$\mathsf {TFNP}$$ instances over $$\{0,1\}^n$$ with $$2^{n^{o(1)}}$$ solutions from any primitive which exists relative to a random injective trapdoor function oracle (e.g. one-way functions). Their main observation was that the argument in [48], which separates one-way functions from one-way permutations, can be strengthened to separate other unstructured primitives from structured primitives (such as problems in $$\mathsf {TFNP}$$). However, it seems that the [48] argument has been exploited to its limits in [47], and, therefore, it is not clear whether their approach can be extended to fully separate one-way functions and $$\mathsf {TFNP}$$. Thus, the situation is contrasting to $$\mathsf {NP} \cap \mathsf {coNP} $$, the decision counterpart of $$\mathsf {TFNP}$$, whose relationship with (injective) OWFs is much better studied. In particular, we know that hardness is implied by one way permutations but injective OWFs, even with indistinguishability obfuscation, (and, therefore, public-key encryption) cannot imply hardness in $$\mathsf {NP} \cap \mathsf {coNP} $$ in a black-box way [5].

2 Preliminaries

Unless stated otherwise, all logarithms are base two. For $$X\subseteq \{0,1\}^*$$, we use $$\overline{X}$$ to denote the set $$\{0,1\}^* \setminus X$$. For strings $$x,y\in \{0,1\}^*$$, we use $$x <_{\text {lex}} y$$ or $$y >_{\text {lex}} x$$ to denote that x is lexicographically strictly smaller than y.

Notation 2

(Functions) Let $$X,Y \subseteq \{0,1\}^*$$, $$f :X\rightarrow Y$$ be a function and $$X' \subseteq X$$ be a set.

  1. 1.

    $$f \upharpoonright X'$$ denotes the restriction of f on $$X'$$, i.e., the function $$f' :X' \rightarrow Y$$ such that $$\forall x \in X' :f'(x) = f(x)$$.

     
  2. 2.

    $$\text {Dom} (f)$$ denotes the domain of f, i.e., the set X.

     
  3. 3.

    $$\text {Im} (f)$$ denotes the image of f, i.e., the set $$\{ f(x) \mid x \in X \} \subseteq Y$$.

     
  4. 4.

    $$f[X']$$ denotes the image of the restriction of f on $$X'$$, i.e., the set $$\text {Im} (f \upharpoonright X')$$.

     
Notation 3

(Injective functions) We denote by $$\text {Inj}_{n}^{m} $$ the set of all injective functions from $$\left\{ 0,1 \right\} ^n$$ to $$\left\{ 0,1 \right\} ^m$$. For the special case when $$n = m$$ we get the set of all permutations on $$\{0,1\}^n$$.

The set $$\text {Inj}_{}^{} $$ is the set of all functions $$f:\{0,1\}^* \rightarrow \{0,1\}^*$$, such that f can be interpreted as a sequence $$f = \left\{ f_n \mid f_n \in \text {Inj}_{n}^{m(n)} \right\} _{n \in \mathbb {N}}$$ of injective functions, where $$m:\mathbb {N} \rightarrow \mathbb {N}$$ is an injective function such that for all $$n \in \mathbb {N}:m(n) > n$$ and $$m(n) \le 100n^{\log n}$$.

We say that the function m is the type of f and we define the corresponding type operator $$\tau :\text {Inj}_{}^{} \rightarrow (\mathbb {N} \rightarrow \mathbb {N})$$ such that $$\tau (f) = m$$.

We denote the set of all possible types by $$\mathrm {T}$$, i.e.,
$$\begin{aligned} \mathrm {T} = \{\mu :\mathbb {N} \rightarrow \mathbb {N} \mid \exists f \in \text {Inj}_{}^{} \text { such that } \tau (f) = \mu \}. \end{aligned}$$
Through the paper $$f_n$$ denotes the function $$f \upharpoonright \{0,1\}^n$$ (i.e., restriction of f to the domain $$\{0,1\}^n$$.), where $$f \in \text {Inj}_{}^{} $$.

In our proofs, we often compose a function defined on all binary strings with a function defined only for binary strings of certain length; namely, we often want to compose a function from $$\text {Inj}_{}^{} $$ with a permutation of n-bit strings. The desired resulting function should always be a function from all binary strings. For the ease of exposition, we extend the standard notation for function composition as follows.

Notation 4
(Function composition). Let X, Y, Z be any sets such that $$X \subseteq Y$$ and let $$f:X \rightarrow Y$$ and $$g:Y \rightarrow Z$$. We define the function $$g \circ f :Y \rightarrow Z$$ as:
$$\begin{aligned} (g \circ f)(x) = {\left\{ \begin{array}{ll} g(f(x)) \text { if } x \in X, \\ g(x) \text { if } x \in Y \setminus X. \end{array}\right. } \end{aligned}$$

Finally, we recall some basic information-theoretic results about prefix-free codes.

Definition 1

(Prefix-free code). A set of code-words $$C \subseteq \{0,1\}^*$$ is a prefix-free code if there are no two distinct $$c_1, c_2 \in C$$ such that $$c_1$$ is a prefix (initial segment) of $$c_2$$, i.e., for any two distinct $$c_1, c_2 \in C$$ there exists $$0 \le j < \min (|c_1|, |c_2|)$$ such that $$(c_1)_j \ne (c_2)_j$$.

Proposition 1

(Theorem 5.3.1 in [13]). The expected length L of any prefix-free binary code for a random variable X is greater than or equal to the entropy H(X).

Corollary 1

To encode a uniformly random permutation $$\pi \in \text {Inj}_{n}^{n} $$ using prefix-free encoding it takes at least $$\log (2^n!)$$ bits in expectation.

Proof

The entropy of a uniformly randomly chosen permutation from $$\text {Inj}_{n}^{n} $$ is $$\log \left( 2^n!\right) $$ as we choose uniformly at random from $$2^n!$$ distinct permutations. By Theorem 1, we get that the expected size of the encoding is at least $$\log \left( 2^n!\right) $$. $$\square $$

3 Separating $$\mathsf {TFNP}$$ and Injective One-Way Functions

3.1 Fully Black-Box Construction of Hard $$\mathsf {TFNP}$$ Problem from iOWF

Below, we give a definition of fully black-box construction of a (worst-case) hard $$\mathsf {TFNP}$$ problem from an injective one-way function.

Definition 2
(Fully black-box construction of a worst-case hard $$\mathsf {TFNP}$$ problem from iOWF ). A fully black-box construction of a worst-case hard $$\mathsf {TFNP}$$ problem from injective one-way function is a tuple $$(R, T_R, C, T_C, p)$$ of oracle-aided algorithms R, C, functions $$T_R, T_C$$, and a polynomial p satisfying the following properties:
  1. 1.

    R and C halt on all inputs: For all $$f \in \text {Inj}_{}^{} $$, $$n \in \mathbb {N}$$, and $$ y, i, s \in \{ 0,1 \}^*$$, the algorithm $$R^f(1^n, y)$$ halts in time $$T_R(|y|)$$, and the algorithm $$C^f(i, s)$$ halts in time $$T_C(|i| + |s|)$$.

     
  2. 2.

    Correctness: For all $$f \in \text {Inj}_{}^{} $$ and for all $$i \in \{ 0,1 \}^*$$, there exists $$s \in \{ 0,1 \}^*$$ such that $$|s| \le p(|i|)$$ and $$C^f(i, s) = 1$$, i.e., for any instance of the $$\mathsf {TFNP}$$ problem there exists a solution of polynomial length.

     
  3. 3.
    Fully black-box proof of security: There exists a polynomial $$p'$$ such that for all $$f \in \text {Inj}_{}^{} $$ and any oracle-aided algorithm $$\textsc {Solve} $$, if
    $$\begin{aligned} \forall i \in \{0,1\}^* :\textsc {Solve} ^f(i) \text { returns } s \text { such that } C^f(i, s) = 1 \end{aligned}$$
    then for infinitely many $$n \in \mathbb {N}$$,
    $$\begin{aligned} \Pr _{x \leftarrow \{ 0,1 \}^n, R}\left[ R^{f, \textsc {Solve}}(1^n, f(x)) = x \right] \ge \frac{1}{p'(n)}\ . \end{aligned}$$
     

Definition 2 has the following semantics. The deterministic algorithm C specifies the $$\mathsf {TFNP}$$ problem and the algorithm R is the (security) reduction which, given access to any $$\mathsf {TFNP}$$ solver, breaks the security of any injective one-way function. For example in the case of the hard $$\textsc {Pigeon}$$ problem from one-way permutations discussed in Sect. 1.1, C would be an algorithm which on input $$(\mathsf {C}^f_y,x)$$, respectively $$(\mathsf {C}^f_y,x,x')$$, outputs 1 if and only if $$\mathsf {C}^f_y(x)=0^n$$, respectively $$\mathsf {C}^f_y(x)=\mathsf {C}^f_y(x')$$. The reduction algorithm $$R(1^n,y)$$ simply queries the $$\mathsf {TFNP}$$ solver $$\textsc {Solve}$$ with the instance $$i=\mathsf {C}^f_y$$, i.e., a circuit computing the function $$\mathsf {C}^f_y(x)=f(x)\oplus y$$, and outputs the solution s returned by $$\textsc {Solve}$$ for which, by construction, $$f(s)=y$$.

Below, we provide some additional remarks on important points in the above definition.

Reduction-Specific $$\textsc {Solve}$$. Let us emphasize the order of quantifiers restricting the security reduction in Definition 2:
$$\begin{aligned}&\exists (R, T_R, C, T_C, p) \ \forall f \ \forall \textsc {Solve} :\ \\&\qquad \qquad \qquad \textsc {Solve} ^{f} \text { solves the }\mathsf {TFNP} \text { problem } C \implies R^{f, \textsc {Solve}} \text { inverts } f\ . \end{aligned}$$
Importantly, the reduction must invert when given access to any oracle $$\textsc {Solve}$$. As a consequence, in order to establish a separation, the above statement is negated and it suffices to show that for every reduction there exists a solver (see proof of [26, Proposition 1] for more details). Thus, in the proof an oracle separation, the oracle $$\textsc {Solve}$$ may even depend on the behaviour of the reduction R, and, in particular, $$\textsc {Solve}$$ can simulate the security reduction R on an arbitrary input. We exploit these properties in establishing our results.

Constructions of Worst-Case vs. Average-Case Hardness in $$\mathsf {TFNP} $$. Our Definition 2 considers constructions of a worst-case hard $$\mathsf {TFNP} $$ problem – the reduction has access to $$\textsc {Solve}$$ which is promised to return a solution to any instance of the $$\mathsf {TFNP} $$ problem. To capture constructions of average-case hardness in $$\mathsf {TFNP} $$, we would need to extend the construction with an efficiently sampleable distribution D of instances of the $$\mathsf {TFNP} $$ problem and require the reduction to invert when given access to any $$\textsc {Solve}$$ that returns solutions for instances coming from the specific distribution D (see Definition 5.1 in [47]). However, given that we are proving a black-box separation, showing impossibility for worst-case hardness is a stronger result.

The Quality of $$\textsc {Solve} $$. Note that we consider security reductions which invert given access to $$\textsc {Solve} $$ which outputs a solution with probability 1, whereas some definitions in the literature allow the reduction to work only with some non-negligible probability. This also makes our negative result stronger – it is potentially easier to give a reduction when given access to $$\textsc {Solve} $$ which is guaranteed to always return a solution.

Direct and Indirect Queries to f. The security reduction R can learn something about f in various ways. It may query f directly or the information might be deduced from the solution of some queried instance of the $$\mathsf {TFNP}$$ problem returned by $$\textsc {Solve}$$. We introduce the following notation in order to distinguish where queries originate, which allows us to reason about the view the security reduction has over the function f in our proof of Theorem 1.

Notation 5

(Query sets Q) We distinguish the following sets of queries to oracles depending on where these queries originated and which oracle is queried.

  • Let $$Q(C^f(i,s))$$ denote the set of all preimages $$x \in \left\{ 0,1 \right\} ^*$$ on which the oracle f has been queried by C running on an input (i, s).

  • Let $$Q_{\textsc {Solve}}(R^{f, \textsc {Solve}}(1^n, y))$$ denote the set of all instances $$i \in \left\{ 0,1 \right\} ^{*}$$ on which the oracle $$\textsc {Solve} $$ has been queried by R running on a security parameter n and challenge y.

  • Let $$Q^{\text {dir}}_f(R^{f, \textsc {Solve}}(1^n, y))$$ denote the set of preimages $$x \in \left\{ 0,1 \right\} ^*$$ on which the oracle f has been queried by R running on an input y and security parameter n.

  • Let $$Q^{\text {indir}}_f(R^{f, \textsc {Solve}}(1^n, y))$$ denote the set of all preimages $$x \in \left\{ 0,1 \right\} ^*$$ on which the oracle f has been queried indirectly, i.e., it has been queried by C running on an input (i, s) where $$i \in Q_\textsc {Solve} (R^{f,\textsc {Solve}}(1^n, y))$$ and $$s = \textsc {Solve} ^f(i)$$.

  • Let $$Q_f(R^{f, \textsc {Solve}}(1^n, y)) = Q^{\text {dir}}_f(R^{f, \textsc {Solve}}(1^n, y)) \cup Q^{\text {indir}}_f(R^{f, \textsc {Solve}}(1^n, y))$$.

Note that these sets may not be disjoint. When f is a partial function (i.e., when f is not defined on all inputs) the query set contains all queries queried up to the point of the first undefined answer and the query with the undefined answer is included as well.

Restrictions on the power of the reduction. We consider various restricted classes of security reductions as defined below.

Definition 3

(Deterministic/randomized, many-one/non-adaptive, f-oblivious reductions) Let $$(R, T_R, C, T_C, p)$$ be a fully black-box construction of a hard $$\mathsf {TFNP}$$ problem from injective one-way functions.

We distinguish deterministic / randomized reductions. For a randomized security reduction, we extend the input of R to a triple $$(1^n, y; r)$$, where the meaning of n, resp. y, remains unchanged (i.e., n is the security parameter, y is the challenge), and $$r \in \{0,1\}^*$$ is the randomness of the security reduction.

The security reduction R is many-one if for all $$f \in \text {Inj}_{}^{} $$, for any oracle $$\textsc {Solve}$$ and for all $$y \in \{0,1\}^*$$, $$R^{f, \textsc {Solve}}(1^n, y)$$ makes a single query to the oracle $$\textsc {Solve}$$.

The security reduction R is non-adaptive if for all $$f \in \text {Inj}_{}^{} $$, for any oracle $$\textsc {Solve}$$ and for all $$y \in \{0,1\}^*$$, all the queries of $$R^{f, \textsc {Solve}}(1^n, y)$$ to the oracle $$\textsc {Solve}$$ are submitted in parallel (i.e., the queries to $$\textsc {Solve}$$ do not depend on the answers received from $$\textsc {Solve}$$).

The security reduction R is f-oblivious if for all $$y \in \{0,1\}^*$$, for any oracle $$\textsc {Solve}$$, and any pair of functions $$f,f' \in \text {Inj}_{}^{} $$, the distributions of queries $$Q_{\textsc {Solve}}(R^{f,\textsc {Solve}}(1^n, y))$$ and $$Q_{\textsc {Solve}}(R^{f', \textsc {Solve}}(1^n, y))$$ are identical (i.e., the queries to $$\textsc {Solve}$$ depend only on the input y and are independent of the oracle f).

3.2 Impossibility for a Deterministic f-Oblivious Many-One Reduction

In this section, we show that there is no fully black-box construction of a hard $$\mathsf {TFNP}$$ problem from injective one-way functions with a deterministic f-oblivious many-one reduction. The proof of this result is already non-trivial and highlights our main technical contributions. In Sect. 3.3, we explain how to extend this result to rule out fully black-box constructions even with a randomized f-oblivious non-adaptive reduction. For lack of space, we omit the proofs of the technical lemmata and instead, for interested readers, provide pointers to the appropriate part of full version [29].

Theorem 1

There is no fully black-box construction $$(R, T_R, C, T_C, p)$$ of a worst-case hard $$\mathsf {TFNP}$$ problem from injective one-way functions with deterministic f-oblivious many-one reduction with success probability at least $$2^{-0.1n}$$ such that both running times $$T_R, T_C \in O(n^{\text {polylog}(n)})$$.

In the above theorem, the running time of both R and C is restricted to quasi-polynomial. Note that the standard notion of cryptographic constructions requires R, C to run in polynomial time in order to be considered efficient. We are ruling out a broader class of potentially less efficient reductions.

The proof of Theorem 1 uses, on a high level, a similar template as other black-box separations in the literature. That is, we design an oracle O relative to which (injective) one-way functions exist but $$\mathsf {TFNP}$$ is broken (even in the worst case). We follow the two-oracle approach [26], and, therefore, our oracle $$O=(f,\textsc {Solve})$$ consist of:
  1. 1.

    $$f\in \text {Inj}_{}^{} $$: a sequence of random injective functions which implements injective one-way functions; and

     
  2. 2.

    $$\textsc {Solve} $$: a reduction-specific oracle that solves $$\mathsf {TFNP}$$ instances.

     
That a random injective function is one-way is a well-established result (see, e.g., Claim 5.3 in [47] for the more general case of random functions). The bulk of technical work revolves around showing that f remains one-way even in the presence of $$\textsc {Solve} $$. For any fully black-box construction with a deterministic f-oblivious many-one reduction, we provide an oracle $$\textsc {Solve}$$ which finds a solution for any $$\mathsf {TFNP}$$ instance (i.e., $$\mathsf {TFNP}$$ is easy in the presence of $$\textsc {Solve}$$) and argue that it does not help the reduction in inverting injective one-way functions. The description of our oracle $$\textsc {Solve}$$ is given in Algorithm 1 and it is explained below.
../images/508076_1_En_22_Chapter/508076_1_En_22_Figa_HTML.png

Oracle $$\textsc {Solve}$$: Let $$(R, T_R, C, T_C, p)$$ be the construction of a hard $$\mathsf {TFNP}$$ problem from injective one-way function with a deterministic f-oblivious many-one security reduction which is hardwired in the oracle $$\textsc {Solve}$$. Ideally, $$\textsc {Solve}$$ should output a solution i which gives the reduction R no information about the inversion of its challenge y. Unfortunately, $$\textsc {Solve}$$ is unaware of the particular challenge y on which $$R^f(1^n,y)$$ queried $$\textsc {Solve}$$ with the instance i. Nevertheless, $$\textsc {Solve}$$ can compute the set $$Y_i$$ of all challenges y on which the reduction would query the instance i.3 The challenges in $$Y_i$$ become “protected” and $$\textsc {Solve}$$ will attempt to provide a solution which does not reveal a preimage of any $$y \in Y_i$$, i.e., s such that $$C^f(i,s)$$ does not make an f-query on a preimage of any $$y\in Y_i$$.

Note that we could run into a potential technical issue when defining $$Y_i$$, as the set of all challenges y on which R queries the instance i might be infinite. However when the instance i is queried by the security reduction R on some very long challenge y then C contributes no indirect query to $$f^{-1}(y)$$ as the running time of C depends only on the length of the instance i. More formally: the running time of C is bounded by $$T_C(|i|+p(|i|))$$ thus C cannot query f on longer inputs. Therefore, we can consider only possible challenges y from $$\text {Im} (f_n)$$ for $$n \le T_C(|i|+p(|i|))$$.

On lines 2–6, $$\textsc {Solve}$$ computes the following auxiliary sets $$N_i$$, $$Y_{i,n}$$, and $$S_{i,f}$$. The set $$N_i$$ contains all the input lengths for the preimages x such that the reduction $$R^{f,\textsc {Solve}}(1^n, f(x))$$ queries the instance i. $$\textsc {Solve}$$ then splits $$Y_i$$ into subsets $$Y_{i,n}$$ using the input lengths of interest in $$N_i$$. Finally, $$\textsc {Solve}$$ computes the set $$S_{i,f}$$ which is the set of all possible solutions for the instance i.

The strategy of $$\textsc {Solve}$$ is to return a solution from the set of “benign” solutions $$B_{i,f}$$, which do not induce any query to preimages of the protected challenges in $$Y_i$$. If there is any such benign solution then $$\textsc {Solve}$$ simply halts and returns the lexicographically smallest one. Unfortunately, it might be the case that every solution queries a preimage of some $$y \in Y_i$$, e.g., if the instance i is queried for all challenges y of a given preimage length n and on each solution s at least one x of length n is queried (i.e., $$B_{i,f} = \emptyset $$ unless we remove $$Y_{i,n}$$ from $$Y_i$$). Since $$\textsc {Solve}$$ in general cannot output a solution while protecting the whole set $$Y_i$$, it will proceed to gradually relax the condition on the set of protected challenges.

Note that we might allow $$\textsc {Solve}$$ to return a solution even though it induces queries to preimages of protected challenges, as long as the reduction queries the instance i on the corresponding image length often enough, as any fixed solution induces only a bounded number of queries to f (bounded by $$T_C$$). Therefore, if the set of challenges on which R queries i is dense enough w.r.t. some image length then, with overwhelming probability, an arbitrary solution will be benign for the random challenge y given to the reduction. Thus, we allow $$\textsc {Solve}$$ to return a solution revealing preimages of challenges from the auxiliary set $$Y_{i,n}$$ maximizing $$\frac{|Y_{i,n}|}{2^n}$$. If the fraction $$\frac{|Y_{i,n}|}{2^n}$$ is small then $$\textsc {Solve}$$ is able to find a benign solution which protects the preimages of length n (see [29, Claim 13]). Whereas, if the fraction $$\frac{|Y_{i,n}|}{2^n}$$ is large enough then any fixed solution will be benign w.r.t. the actual challenge of R with overwhelming probability as each solution can induce queries to only a small number of preimages of challenges from the set $$Y_{i,n}$$ (see [29, Claim 12]).

In order to show formally that $$\textsc {Solve}$$ does not help in inverting the injective one-way function, we employ an incompressibility argument similar to [21]. Specifically, we present algorithms $$\textsc {Encode}_n$$ (given in Algorithm 2) and $$\textsc {Decode}_n$$ (given in Algorithm 3) which utilize the reduction R to allow compression of a random permutation more succinctly than what is information-theoretically possible. When compressing the random permutation by $$\textsc {Encode}_n$$, we have access to the whole permutation and we can effectively provide the reduction with access to $$\textsc {Solve}$$. However, to be able to use the reduction also in the $$\textsc {Decode}_n$$, we have to be able to simulate access to our $$\textsc {Solve}$$ oracle given access only to a partially defined oracle f (as we are reconstructing f). For the description of the algorithm $$\textsc {SolveSim}$$, which simulates the $$\textsc {Solve}$$ oracle for the purpose of decoding in $$\textsc {Decode}_n$$, see Algorithm 4.
../images/508076_1_En_22_Chapter/508076_1_En_22_Figb_HTML.png

$$\textsc {Encode}_n$$ Algorithm: The algorithm $$\textsc {Encode}_n$$ (Algorithm 2) uses the reduction R to compress a random permutation $$\pi $$ on bit strings of length n. Note that even though R succeeds in inverting an injective function, for technical reasons, we leverage its power in order to compress a permutation. One particular issue we would run into when trying to compress an injective function f which is not surjective is that the encoding would have to comprise also of the encoding of the image of f which might render the encoding inefficient.

Nevertheless, in order to use the reduction for compressing, we must provide it with oracle access to an injective function which is not a bijection. Thus, we equip $$\textsc {Encode}_n$$ (as well as $$\textsc {Decode}_n$$) with an injective function h. $$\textsc {Encode}_n$$ then computes the function f as a composition of the functions $$h \circ \pi $$ and uses the reduction with respect to the composed oracle f. We emphasize that h is independent of $$\pi $$, therefore it cannot be used in order to compress $$\pi $$ on its own.

First, $$\textsc {Encode}_n$$ computes the set $$\text {INV} _f$$ which is the set of all challenges y on which the reduction successfully inverts (i.e., the reduction returns $$f^{-1}(y)$$). Then $$\textsc {Encode}_n$$ computes the set $$G_f$$, which is the set of “good” challenges y, on which the reduction successfully inverts even though $$\textsc {Solve}$$ returns a solution which does not induce a query to any preimage of y. This set is used to reduce the size of the trivial encoding of f – the part of f corresponding to the challenges in $$G_f$$ will be algorithmically reconstructed by $$\textsc {Decode}_n$$ using the security reduction R.

Specifically, $$\textsc {Encode}_n$$ computes $$Y_f$$, the subset of $$G_f$$ for which the preimages will be algorithmically reconstructed, as follows: $$\textsc {Encode}_n$$ processes the challenges y in $$G_f$$ one by one in lexicographically increasing order and stores all f-queries needed for reconstruction by R (i.e, for any x such that there was an f-query x, the element f(x) is removed from the “good” set $$G_f$$ as we cannot reconstruct the preimage of y using R without knowing the image of x under f).

$$\textsc {Encode}_n$$ outputs an encoding $$\mathcal {M}$$ which describes the size of $$X_f$$, the sets $$Y_f$$ and $$X_f$$ (where $$X_f$$ is the set of preimages corresponding to $$Y_f$$), and the partial function representing the function f on inputs of length n outside of $$X_f$$. Thus, the encoding saves bits by not revealing the bijection between $$X_f$$ and $$Y_f$$ which is algorithmically reconstructed instead (Lemma 4). Specifically, the size of $$X_f$$ (equal to the size of $$Y_f$$) can be encoded using $$\log 2^n = n$$ bits. $$Y_f$$ is a subset of $$\text {Im} (f_n) = \text {Im} (h_n)$$ and it is encoded using $$\lceil \log \left( {\begin{array}{c}2^n\\ |Y_f|\end{array}}\right) \rceil $$ bits as the index of the corresponding subset of size $$|Y_f|$$ (the set $$X_f$$ is encoded in a similar manner). Finally, the bijection between $$\{0,1\}^n \setminus X_f$$ and $$\text {Im} (f) \setminus Y_f$$ is encoded as the index of the corresponding permutation on a set of size $$|\left\{ 0,1 \right\} ^n \setminus X_f|$$ using $$\left\lceil \log \left( |\left\{ 0,1 \right\} ^n \setminus X_f|! \right) \right\rceil $$ bits.

A small technicality arises when the set $$X_f$$, respectively the set $$Y_f$$, is not large enough, the above mentioned encoding would be inefficient as the trivial encoding outputting the whole description of the permutation $$\pi $$ would use fewer bits. Thus, $$\textsc {Encode}_n$$ simply outputs the trivial encoding when $$X_f$$ is too small. The first bit of the encoding distinguishes between the two cases.
../images/508076_1_En_22_Chapter/508076_1_En_22_Figc_HTML.png

$$\textsc {Decode}_n$$ Algorithm: The encoding returned by $$\textsc {Encode}_n$$ is uniquely decodable by $$\textsc {Decode}_n$$ given in Algorithm 3 (see [29, Section 4.2]). When the output of $$\textsc {Encode}_n$$ starts with 0, the rest of the encoding is an explicit encoding of $$\pi $$ and we are immediately done with its reconstruction. If the output starts with bit 1, the following n bits represent $$|X_f| = |Y_f|$$. $$\textsc {Decode}_n$$ then reads the following $$\left\lceil \log \left( {\begin{array}{c}2^n\\ |X_f|\end{array}}\right) \right\rceil $$ bits of the encoding to reconstruct the set $$Y_f$$ (as the j-th subset of $$2^n$$ of size $$|X_f|$$). Similarly, $$\textsc {Decode}_n$$ reconstructs the set $$X_f$$ using the following $$\left\lceil \log \left( {\begin{array}{c}2^n\\ |X_f|\end{array}}\right) \right\rceil $$ bits. The remaining bits represent $$\sigma $$, a restriction of f on all the n-bit inputs outside of $$X_f$$, given by the index of the corresponding bijection between $$\{0,1\}^n \setminus X_f$$ and $$\text {Im} (f) \setminus Y_f$$. Note that such encoding of $$\sigma $$ does preserve the structure of the restriction but it looses the information about the domain and image of $$\sigma $$. However, both are easy to reconstruct. The domain is simply $$\{0,1\}^n \setminus X_f$$ and the image of $$\sigma $$ can be computed from $$Y_f$$ and the common input h as $$\text {Im} (\sigma )=\text {Im} (f)\setminus Y_f=\text {Im} (h\circ \pi )\setminus Y_f=\text {Im} (h)\setminus Y_f$$.

$$\textsc {Decode}_n$$ then computes the remaining preimages one by one in lexicographic order using the security reduction R, adding the reconstructed mapping into a partial function $$f'$$. Note that during the computation of the preimage of y, the reduction might make an f-query on x which has no defined output. But as $$\textsc {Decode}_n$$ takes $$y \in Y_f$$ in the same order as $$\textsc {Encode}_n$$ added them to the set $$Y_f$$, this happens if and only if the preimage of y is being queried. Thus, we answer any such query by y (it is crucial that this happens only for f-queries made directly by R) which is captured in the definition of the auxiliary function $$f''$$ defined by $$\textsc {Decode}_n$$ and used as the oracle for the security reduction R.

Once $$\textsc {Encode}_n$$ finds the preimages of all challenges y from $$Y_f$$, the function $$f'$$ is defined everywhere. To reconstruct the permutation $$\pi $$ on $$\{0,1\}^n$$, $$\textsc {Decode}_n$$ can simply compose the inverse of h with the reconstructed function $$f'$$.

$$\textsc {SolveSim}$$ Algorithm: For the ease of presentation we usually do not explicitly mention the oracle h as it is given by context (we run $$\textsc {Decode}_n$$ and $$\textsc {SolveSim}$$) with respect to only one h at a time.

The computation of the algorithm $$\textsc {SolveSim}$$ (Algorithm 4) is similar to the computation of $$\textsc {Solve}$$ (Algorithm 1). First, $$\textsc {SolveSim}$$ computes the sets $$Y_i$$. There is one big difference between $$\textsc {Solve}$$ and $$\textsc {SolveSim}$$. As $$\textsc {SolveSim}$$ does not have access to the whole f it uses h or the partial knowledge of f, namely the partial function $$f'$$ everywhere f is used in the $$\textsc {Solve}$$ algorithm.

  • We use h whenever we need to determine the image of $$f_n$$ for some n. As $$\forall n \in \mathbb {N} :\text {Im} (h_n) = \text {Im} (f_n)$$ using $$\text {Im} (h_n)$$ instead of $$\text {Im} (f_n)$$ makes no difference to the computation.

  • The second place where h is used instead of f is when $$\textsc {SolveSim}$$ computes the set $$Y_i$$. Specifically, when determining images y for which the security reduction R queries the given instance i, the algorithm $$\textsc {SolveSim}$$ computes the same $$Y_i$$ as if it used f by the f-obliviousness of the security reduction.

  • In all other places, $$\textsc {SolveSim}$$ uses the partial knowledge of f (i.e., the partial function $$f'$$). This causes a real difference in the computation. In particular, the set $$S_{i, f'}$$ (as computed by $$\textsc {SolveSim}$$) may differ a lot from $$S_{i, f}$$ (as computed by $$\textsc {Solve}$$) as some solutions from $$S_{i, f}$$ potentially query some unknown parts of f. Thus, the set $$S_{i, f'}$$ computed by $$\textsc {SolveSim}$$ is just a subset of the whole $$S_{i, f}$$. The set $$S_{i, f'}$$ contains only the solutions $$\textsc {SolveSim}$$ is “aware of” ($$f'$$ is defined for all queries and thus $$\textsc {SolveSim}$$ may verify the solution). The rest of the computation is practically the same, except that $$\textsc {SolveSim}$$ is restricted just to the set of solutions $$S_{i, f'}$$. The main trick is that we make sure that $$\textsc {SolveSim}$$ is aware of the solution which should be returned and it does not matter that it ignores other solutions of the instance.

../images/508076_1_En_22_Chapter/508076_1_En_22_Figd_HTML.png

Structure of the Proof of Theorem 1. For ease of presentation and understanding, we divide the proof into four lemmata, Lemma 1 through 4. Lemma 1 shows that given an instance i of the $$\mathsf {TFNP}$$ problem represented by the algorithm $$C^f$$, our $$\textsc {Solve}$$ always returns a solution, i.e., an s such that $$C^f(i,s)=1$$ (formal proof is given in [29, Section 4.1]). Thus, any distribution of instances of the $$\mathsf {TFNP}$$ problem is easy in the presence of $$\textsc {Solve}$$.

Lemma 1

For any instance $$i \in \{0,1\}^*$$ and any $$f \in \text {Inj}_{}^{} $$, the algorithm $$\textsc {Solve} ^f(i)$$ halts and returns a solution, i.e., it returns a string $$s \in \{0,1\}^*$$ such that $$|s| \le p(|i|)$$ and $$C^f(i,s) = 1$$.

To argue that $$\textsc {Solve}$$ does not help in inverting injective functions, we analyze the joint properties of the algorithms $$\textsc {Encode}_n$$ and $$\textsc {Decode}_n$$. First, we show that $$\textsc {Decode}_n$$ always returns the correct permutation encoded by $$\textsc {Encode}_n$$ (see [29, Section 4.2] for the formal proof).

Lemma 2
For all $$n \in \mathbb {N}$$, $$\pi \in \text {Inj}_{n}^{n} $$, and $$h \in \text {Inj}_{}^{} $$,
$$\textsc {Decode}_n ^h(\textsc {Encode}_n ^h(\pi )) = \pi ,$$
where $$\textsc {Encode}_n$$, respectively $$\textsc {Decode}_n$$, is given in Algorithm 2, respectively Algorithm 3.

We crutialy rely on f-obliviousness of the reduction for the proof of Lemma 2. It is the property which allows us to simulate the algorithm $$\textsc {Solve}$$ during the decoding phase, as $$\textsc {SolveSim}$$ needs to be able to compute the same set $$Y_i$$ as $$\textsc {Solve}$$ does. Moreover, $$\textsc {SolveSim}$$ cannot query f on all preimages as $$\textsc {Solve}$$ does when computing $$Y_i$$. Due to f-obliviousness of the reduction, we may substitute f by h in the computation of $$Y_i$$ in $$\textsc {SolveSim}$$ as the resulting set depends only on the image of the function given to R as an oracle (and $$\text {Im} (f) = \text {Im} (h)$$).

Second, we show that the encoding output by $$\textsc {Encode}_n$$ is prefix-free (see [29, Section 4.3]).

Lemma 3
Let $$h \in \text {Inj}_{}^{} $$ be any injective function and $$n \in \mathbb {N}$$, then the encoding given by the algorithm $$\textsc {Encode}_n$$ (Algorithm 2) is prefix-free, i.e.,
$$\begin{aligned} \forall \pi , \pi ' \in \text {Inj}_{n}^{n} \text { such that } \pi \ne \pi ':\textsc {Encode}_n ^{h}(\pi ) \text { is not a prefix of } \textsc {Encode}_n ^{h}(\pi '). \end{aligned}$$

Finally, we bound the expected size of the encoding given by $$\textsc {Encode}_n$$ (see [29, Section 4.4]) which contradicts the information-theoretic bound implied by Corollary 1.

Lemma 4
Let $$(R, T_R, C, T_C, p)$$ be a fully black-box construction of a hard $$\mathsf {TFNP}$$ problem from an injective one-way function. Assume $$n \in \mathbb {N}$$ is large enough so that $$n \ge 50$$ and $$2q(n)+1 \le 2^{0.2n}$$, where q(n) is the maximal number of f-queries made by C on the queried instance Let the success probability of R be $$\beta \ge 2^{-0.1n}$$, i.e., for any f we have
$$\begin{aligned} \Pr _{x \leftarrow \{0,1\}^n}[R^{f,\textsc {Solve}}(1^n,f(x)) = x] = \beta \ge 2^{-0.1n}. \end{aligned}$$
Then
$$\begin{aligned} \exists h \in \text {Inj}_{}^{} :\mathbb {E}_{\pi \leftarrow \text {Inj}_{n}^{n}, h \leftarrow \text {Inj}_{}^{}}[|\textsc {Encode}_n ^h(\pi )|] \le \log {2^n!} - \frac{8}{10} n 2^{0.1n}. \end{aligned}$$

We claim (see [29, Claim 10]) that the upper bound $$2q(n)+1 \le 2^{0.2n}$$ used in the statement of the lemma is without loss of generality for large enough n and for all quasi-polynomial (and, hence, also for efficient) algorithms R, C. We use this fact again in the proof of the main theorem (Theorem 1), and refer the readers to [29, Section 4.4] for the precise statement and its proof.

Equipped with the above lemmata, we next prove Theorem 1.

Proof
(of Theorem 1). Suppose to the contrary that there is such a reduction $$(R, T_R, C, T_C, p)$$. By Lemma 1, the algorithm $$\textsc {Solve}$$ (Algorithm 1) returns a valid solution with probability one. Thus, the reduction R must invert f with high probability when given access to any oracle $$f \in \text {Inj}_{}^{} $$ and our oracle $$\textsc {Solve}$$, i.e.,
$$\begin{aligned} \Pr _{x \leftarrow \{ 0,1 \}^n}\left[ R^{f, \textsc {Solve}}(1^n,f(x)) = x \right] \ge \frac{1}{p'(n)} \end{aligned}$$
for some polynomial $$p'$$ and infinitely many $$n \in \mathbb {N}$$.
Let $$n \in \mathbb {N}$$ be large enough such that
  1. 1.

    $$2q(n) + 1 \le 2^{0.2n}$$,

     
  2. 2.

    $$\Pr _{x \leftarrow \{ 0,1 \}^n}\left[ R^{f, \textsc {Solve}}(1^n, f(x)) \in f^{-1}(f(x)) \right] \ge \frac{1}{p'(n)},$$

     
where q(n) is the maximal number of f-queries made by C on the queried instance As already pointed out, the quasi-polynomial bounds on running times $$T_C, T_R \in O(n^{\text {polylog}(n)})$$ imply that $$q(n) \in o(2^{0.2n})$$ (see [29, Claim 10]). Thus, for large enough n, the upper bound $$2q(n) + 1 \le 2^{0.2n}$$ holds without loss of generality.

For any $$h \in \text {Inj}_{}^{} $$, we can use the algorithm $$\textsc {Encode}_n ^h$$ (Algorithm 2) to encode a given permutation $$\pi \in \text {Inj}_{n}^{n} $$. Decodability of the encoding follows from Lemma 2. Moreover, by Lemma 3, the encoding is a prefix-free code. By Lemma 4, there is a function $$h \in \text {Inj}_{}^{} $$ such that the pair of algorithms $$\textsc {Encode}_n ^h$$ and $$\textsc {Decode}_n ^h$$ defines an encoding of $$\pi \leftarrow \text {Inj}_{n}^{n} $$ with expected length at most $$\log (2^n!) - \frac{8}{10} n 2^{0.1n}$$. This contradicts the information-theoretic bound on the expected length of any prefix-free encoding of a random permutation on $$\{0,1\}^n$$ given by Corollary 1. $$\square $$

3.3 Extensions

In this section, we state some extensions to the result in the previous section. We refrain from providing the details and refer the readers to [29, Section 5].

First, it is possible to extend our proof from Sect. 3.2 to rule out even non-adaptive security reductions which submit multiple queries to the oracle $$\textsc {Solve}$$ in parallel, though still f-obliviously, as defined in Definition 3. The description of the algorithms $$\textsc {Solve}$$, $$\textsc {Encode}_n$$, $$\textsc {Decode}_n$$, and $$\textsc {SolveSim}$$ remain unchanged, but we require a slightly different analysis tailored for non-adaptive reductions. We refer the readers to [29, Section 5.2] for the details.

Second, we can extend our results to randomised reductions with additional changes to our algorithm $$\textsc {Solve}$$. One could imagine that the construction has some instance i created for a concrete challenge y, on which R queries i with high probability. But R might also query the instance i for many other challenges $$y'$$ (on each of them with small probability) to hide the real challenge y. Thus we need to take the probability of querying the instance i into account. Roughly speaking, the $$\textsc {Solve}$$ for randomised reductions is an extension of the $$\textsc {Solve}$$ given in Algorithm 1 taking this probability into account. $$\textsc {SolveSim}$$ is designed accordingly and thanks to f-obliviousness we are still able to show that the simulation is faithful. The rest of the changes involve modifying the existing argument taking into account the changes to $$\textsc {Solve}$$ and $$\textsc {SolveSim}$$. We refer the readers to [29, Section 5.3] for the details.

4 Conclusions

In this work, we have shown that there are intrinsic barriers preventing simple fully black-box constructions of hard $$\mathsf {TFNP}$$ problems from injective one-way functions. The main technical contribution of our work is the technique of designing a “$$\mathsf {TFNP}$$-breaker” oracle $$\textsc {Solve}$$ which depends on the reduction.

The natural direction towards extending our results would be attempting to lift the restriction to f-oblivious and non-adaptive reductions. One reason for why this might be challenging is that a black-box separation of $$\mathsf {TFNP}$$ and injective one-way functions would subsume the separation of collision-resistant hash functions and one-way functions [49], for which, despite the recent progress, there are only non-trivial proofs [4, 25, 40].

Acknowledgements

We wish to thank the anonymous reviewers for their comments which helped us to clarify the presentations of our results.