### Abstract

Let *Kt*(*x*) denote the Levin-Kolmogorov Complexity of the string *x*, and let MKtP denote the language of pairs (*x*, *k*) having the property that *Kt*(*x*) ≤ *k.* We demonstrate that:

- MKtP ∉ Heur
_{neg}BPP (i.e., MKtP is*two-sided error*mildly average-case hard) iff infinitely-often OWFs exist. - MKtP ∉ Avg
_{neg}BPP (i.e., MKtP is*errorless*mildly average-case hard) iff EXP ≠ BPP.

Taken together, these results show that the only “gap” toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly “minor” technical gap between two-sided error and errorless average-case hardness of the MKtP problem.

### 1. Introduction

A *one-way function*^{6} (OWF) is a function *f* that can be efficiently computed (in polynomial time), yet no probabilistic polynomial-time (PPT) algorithm can invert *f* with inverse polynomial probability for infinitely many input lengths *n.* Whether one-way functions exist is unequivocally the most important open problem in cryptography (and arguably the most important open problem in the theory of computation, see e.g., Levin^{19}): OWFs are both necessary^{12} and sufficient for many of the most central cryptographic primitives and protocols (e.g., pseudorandom generators,^{2, 11} pseudo-random functions,^{7} private-key encryption,^{8} etc.)

While many candidate constructions of OWFs are known, the question of whether OWFs can be based on some “standard” complexity-theoretic assumption is mostly wide open.

In this work, we focus on the question of whether cryptography can be based on the “super-weak” complexity-theoretic assumption that computations cannot be exponentially speedup using randomness:

Can the existence of OWFs be based on the assumption thatEXP ≠ BPP?

While we are not able to provide a full positive answer to this problem (which as we shall see later on, would imply that NP ≠ P), we are able to show that the task of basing OWFs on the assumption that EXP ≠ BPP is equivalent to a seemingly minor technical problem regarding different notions of average-case hardness w.r.t. Levin’s notion of Kolmogorov complexity.^{18} Toward explaining our main result, let us first review some recent connections between cryptography and Kolmogorov complexity.

**1.1. On OWFs and Kolmogorov complexity**

What makes the string 12121212121212121 less “random” than 60484850668340357492? The notion of *Kolmogorov complexity* (*K*-complexity), introduced by Solomonoff,^{26} Kolmogorov,^{16} and Chaitin,^{5} provides an elegant method for measuring the amount of “randomness” in individual strings: The *K*-complexity of a string is the length of the shortest program (to be run on some fixed universal Turing machine *U*) that outputs the string *x.* From a computational point of view, however, this notion is unappealing as there is no efficiency requirement on the program. The notion of *t*(·)-*time-bounded Kolmogorov Complexity (K ^{t}-complexity)* overcomes this issue:

*K*(

^{t}*x*) is defined as the length of the shortest program that outputs the string

*x*within time

*t*(|

*x*|). As surveyed by Trakhtenbrot,

^{27}the problem of efficiently determining the

*K*-complexity for

^{t}*t*(

*n*) = poly(

*n*) has been studied in the Soviet Union since the 60s as a candidate for a problem that requires “brute-force search.” The modern complexity-theoretic study of this problem goes back to Sipser,

^{24}Ko,

^{15}and Hartmanis

^{9}from the early 1980s.

A very recent result by Liu and Pass^{20} shows that “mild” average-case hardness of the time-bounded Kolmogorov complexity problem (when the time bound is some polynomial) is *equivalent* to the existence of OWFs. In this work, we will extend their work to consider a different variant of the notion of “resource-bounded” Kolmogorov complexity due to Levin.^{18} The central advantage of doing so will be that we will be able to base OWFs on the average-case hardness of a problem that is average-case complete for EXP! The only reason that this result falls short of basing OWF on EXP ≠ BPP is that the notion of average-case hardness in the EXP-completeness result is slightly different from the notion of average-case hardness for the “OWF-completeness” result. However, “morally,” this result can be interpreted as an indication that the existence of OWFs is equivalent to EXP ≠ BPP (since trivially, the existence of OWFs implies that EXP ≠ BPP).

**1.2. Levin-Kolmogorov complexity**

While the definition of time-bounded Kolmogorov complexity, *K ^{t}* is simple and clean, as noted by Leonid Levin

^{18}in 1973, an annoying aspect of this notion is that it needs to be parametrized by the time-bound

*t.*To overcome this issue, Levin proposed an elegant “non-parametrized” version of Kolmogorov complexity that directly incorporates the running time as a

*cost.*To capture the idea that polynomial-time computations are “cheap,” Levin’s definition only charges logarithmically for running time. More precisely, let the Levin-Kolmogorov complexity of the string,

*Kt*(

*x*), be defined as follows:

where *U* is a universal Turing machine, and we let *U*(Π, 1^{t}) denote the output of the program Π after *t* steps. Note that, just like the standard notion of Kolmogorov complexity, *Kt*(*x*) is bounded by |*x*| + *O*(1)—we can simply consider a program that has the string *x* hard-coded and directly halts.

Let MKtP denote the decisional Levin-Kolmogorov complexity problem; namely, the language of pairs (*x*, *k*) where *k* ∈ {0, 1}^{⌈log |x|⌉} having the property that *Kt*(*x*) ≤ *k.* MKtP no longer seems to be in NP, as there may be strings *x* that can be described by a short program Π (with description size, e.g., *n*/10) but with a “largish” running time (e.g., 2^{n/10}); the resulting string *x* thus would have small *Kt*-complexity (*n*/5), yet verifying that the witness program Π indeed outputs *x* would require executing it which would take exponential time. In fact, Allender et al.^{1} show that MKtP actually is EXP-complete w.r.t. P/poly reductions; in other words, MKtP ∈ P/poly if and only if EXP ⊆ P/poly.

We will be studying (mild) average-case hardness of the MKtP problem, and consider two standard (see e.g., Bogdanov^{3}) notions of average-case tractability for a language *L* with respect to the uniform distribution over instances:

**two-sided error average-case heuristics:**We say that*L*∈ Heur_{neg}BPP if for every polynomial*p*(·), there exists some PPT heuristic ℋ that decides*L*(w.r.t. uniform*n*-bit strings) with probability .**errorless average-case heuristics:**We say that*L*∈ Avg_{neg}BPP if for every polynomial*p*(·), there exists some PPT heuristic ℋ such that (a) for every instance*x*, with probability 0.9, ℋ(*x*) either outputs*L*(*x*) or ⊥, and (b), ℋ(*x*) outputs ⊥ with probability at most given uniform*n*-bit strings*x.*

In other words, the difference between an errorless and a two-sided error heuristic ℋ is that an errorless heuristic needs to (with probability 0.9 over its own randomness but not the instance *x*) output either ⊥ (for “I don’t know”) or the correct answer *L*(*x*), whereas a two-sided error heuristic may simply make mistakes without “knowing it”.

To better understand the class Avg_{neg}BPP, it may be useful to compare it to the class Avg_{neg}P (languages solvable by deterministic errorless heuristics): *L* ∈ Avg_{neg}P if for every polynomial *p*(·), there exists some deterministic polynomial-time heuristic ℋ such that (a) for every input *x*, ℋ(*x*) outputs either *L*(*x*) or H, and (b) the probability over uniform *n*-bit inputs *x* that ℋ outputs ⊥ is bounded by
. In other words, the *only* way an errorless heuristic may make a “mistake” is by saying ⊥ (“I don’t know”); if it ever outputs a non-⊥ response, this response needs to be correct. (Compare this to a two-sided error heuristic that only makes mistakes with a small probability, but we do not know when they happen.) Avg_{neg}BPP is simply the natural “BPP-analog” of Avg_{neg}P where the heuristic is allowed to be randomized.

**Two-sided error average-case hardness of MKtP:** Our first result shows that the characterization of Liu and Pass^{20} can be extended to work also w.r.t. MKtP. More precisely,

THEOREM 1.1. MKtP ∉ Heur_{neg}BPP *iff infinitely-often OWFs exist.*

We highlight that whereas^{20} characterized “standard” OWF, the above theorem only characterizes *infinitely-often* OWFs—that is, functions that are hard to invert for infinitely many inputs lengths (as opposed to all input lengths). The reason for this is that^{20} considered an “almost-everywhere” notion of average-case hardness of *K ^{t}*, whereas the statement MKtP ∉ Heur

_{neg}BPP only considers an infinitely-often notion of average-case hardness. (As we demonstrate in the full version, we can also obtain a characterization of standard “almost-everywhere” OWFs by assuming that MKtP is “almost-everywhere” mildly average-case hard, but for simplicity, in the this paper, we focus our attention on the more standard complexity-theoretic setting of infinitely-often hardness.)

On a high level, the proof of Theorem 1.1 follows the same structure as the characterization of Liu and Pass.^{20} The key obstacle to deal with is that since MKtP is not known to be in NP, there may not exist some polynomial time bound that bounds the running time of a program Π that “witnesses” the *Kt*-complexity of a string *x*; this is a serious issue as the OWF construction in Liu and Pass^{20} requires knowing such a running time bound (and indeed, the running time of the OWF depends on it). To overcome this issue, we rely on a new insight about Levin-Kolmogorov complexity.

We say that the program Π is a *Kt-witness* for the string *x* if Π generates *x* within *t* steps while minimizing |Π| + log *t* among all other programs (i.e., Π is a witness for the *Kt*-complexity of *x*). The crucial observation (see Fact 3.1) is that for every 0 < ε < 1, except for an ε fraction of *n*-bit strings *x*, *x* has a *Kt*-witness Π that runs in time
. That is, “most” strings have a *Kt*-witness that has a “short” running time. To see this, recall that as aforesaid, for every string *x*, *Kt*(*x*) ≤ |*x*| + *O*(1); thus, every string *x* ∈ {0, 1}^{n} with a *Kt*-witness Π with running time exceeding
, must satisfy that
. Since the length of Π is bounded by *n* + *O*(1) + log ε, it follows that we can have at most *O*(ε)2^{n} strings *x* where the *Kt*-witness for *x* has a “long” running time.

We can next use this observation to consider a more computationally tractable version of *Kt*-complexity where we cut off the machine’s running time after
steps (where ε is selected as an appropriate polynomial) and next follow a similar paradigm as in Liu and Pass^{20}

**Errorless average-case hardness of MKtP.** We next show how to extend the result of Allender et al.^{1} to show that MKtP is not just EXP complete in the worst case, but also EXP-average-case complete; furthermore, we are able to show completeness w.r.t. BPP (as opposed to P/poly) reductions. We highlight, however, that completeness is shown in a “non-black box” way (whereas^{1} presented a P/poly truth table reduction). By non-black box, we here mean that we are not able to show how to use any algorithm that solves MKtP (on average) as an oracle (i.e., as a black box) to decide EXP (in probabilistic polynomial time); rather, we directly show that if MKtP ∈ Avg_{neg} BPP, then EXP ⊆ BPP.

THEOREM 1.2. MKtP ∉ Avg_{neg}BPP *iff* EXP ≠ BPP.

Theorem 1.2 follows a similar structure as the EXP-completeness results of Allender et al.^{1} Roughly speaking, Allender et al. observe that by the result of Nisan and Wigderson^{21} and Impagliazzo and Wigderson,^{13} the assumption that EXP ⊈ P/poly implies the existence of a (subexponential-time computable) pseudorandom generator that fools polynomial-size circuits. But using a *Kt*-oracle, it is easy to break the PRG (as outputs of the PRG have small *Kt*-complexity since its running time is “small”). We first observe that the same approach can be extended to show that MKtP is (errorless) average-case hard w.r.t. polynomial-size circuits (under the assumption that EXP ⊈ P/poly). We next show that if we instead rely on a PRG construction of Impagliazzo and Wigderson,^{14} it suffices to rely on the assumption that EXP ≠ BPP to show average-case hardness of MKtP w.r.t. PPT algorithms.

**Interpreting Thm 1.1 and Thm 1.2.** By combining Theorem 1.1 and Theorem 1.2, we get that the only “gap” toward getting (infinitely-often) one-way functions from the assumption that EXP ≠ BPP is the seemingly “minor” technical gap between two-sided error and errorless average-case hardness of the MKtP problem (i.e., proving MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP). Furthermore, note that this “gap” *fully characterizes* the possibility of basing (infinitely-often) OWFs on the assumption that EXP ≠ BPP: Any proof that EXP ≠ BPP implies infinitely-often OWFs also shows the implication MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP.

As a corollary of Theorem 1.1 and Theorem 1.2, we next demonstrate that the implication MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP implies that NP ≠ P.

THEOREM 1.3. *If* MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP, *then* NP ≠ P.

This result can be interpreted in two ways. The pessimistic way is that closing this gap between two-sided error, and errorless, heuristics will be very hard. The optimistic way, however, is to view it as a new and algorithmic approach toward proving that NP ≠ P: To demonstrate that NP ≠ P, it suffices to demonstrate that MKtP can be solved by an errorless heuristic, given access to a two-sided error heuristic for the same problem.

**Concurrent work.** A concurrent and independent work by Ren and Santhanam^{23} presents related but orthogonal characterizations of MKtP. Both works essentially show an equivalence between mild average-case hardness of MKtP and the existence of OWFs; we next show that errorless average-case hardness of MKtP is equivalent to EXP ≠ BPP, whereas they instead consider an incomparable notion of two-sided error hardness with a “tiny” error and show that such average-case hardness of MKtP w.r.t. non-uniform polynomial-time adversaries is equivalent to the assumption that EXP ∉ P/poly.

### 2. Preliminaries

We assume familiarity with basic concepts and computational classes such as Turing machines, polynomial-time algorithms, probabilistic polynomial-time (PPT) algorithms, NP, EXP, BPP, and P/poly. A function *μ* is said to be *negligible* if for every polynomial *p*(·) there exists some *n*_{0} such that for all
. A *probability ensemble* is a sequence of random variables *A* = {*A*_{n}}_{n∈ℕ}. We let *U*_{n} denote the uniform distribution over {0, 1}^{n}. Given a string *x*, we let [*x*]_{j} denote the first *j* bits of *x.*

**One-way functions.** We recall the definition of one-way functions.^{6} Roughly speaking, a function *f* is one way if it is polynomial-time computable, but hard to invert for PPT attackers. The standard cryptographic definition of a one-way function requires that for every PPT attacker *A*, there exists some negligible function *μ*(·) such that *A* only succeeds in inverting the function with probability *μ*(*n*) for *all* input lengths *n.* (That is, hardness holds “almost-everywhere.”) We will also consider a weaker notion of an *infinitely-often* one-way function,^{22} which only requires that the success probability is bounded by *μ*(*n*) for *infinitely many* input lengths *n.* (That is, hardness only holds “infinitely-often,” analogously to complexity-theoretic notions of hardness).

DEFINITION 2.1. *Let f*: {0, 1}* → {0, 1}* *be a polynomial-time computable function. f is said to be a* one-way function (OWF) *if for every* PPT *algorithm A, there exists a negligible function μ such that for all n* ∈ ℕ,

*f is said to be an* infinitely-often one-way function (ioOWF) *if the above condition holds for infinitely many n* ∈ ℕ *(as opposed to all).*

We may also consider a weaker notion of a *weak one-way function*,^{29} where we only require all PPT attackers to fail with probability noticeably bounded away from 1:

DEFINITION 2.2. *Let f*: {0, 1}* → {0, 1}* *be a polynomial-time computable function. f is said to be a* *α*-weak one-way function (α-weak OWF) *if for every* PPT *algorithm A, for all sufficiently large n* ∈ *N*,

*We say that f is simply a* weak one-way function (weak OWF) *if there exists some polynomial q* > 0 *such that f is a*
–*weak OWF. f is said to be an* weak infinitely-often one-way function (weak ioOWF) *if the above condition holds for infinitely many n* ∈ ℕ *(as opposed to all).*

Yao’s hardness amplification theorem^{29} shows that any weak (io) OWF can be turned into a “strong” (io) OWF.

**Levin-Kolmogorov complexity.** Let *U* be some fixed universal Turing machine that can emulate any Turing machine *M* with polynomial overhead. Given a description Π ∈ {0, 1}* which encodes a pair (*M*, *w*) where *M* is a (single-tape) Turing machine and *w* ∈ {0, 1}* is an input, let *U*(Π, 1^{t}) denote the output of *M*(*w*), when emulated on *U* for *t* steps. Note that (by assumption that *U* only has polynomial overhead) *U*(Π, 1^{t}) can be computed in time poly(|Π|, *t*). We turn to defining Levin’s notion of Kolmogorov complexity^{18}:

Let MKtP denote the decisional Levin-Kolmogorov complexity problem; namely, the language of pairs (*x*, *k*) where *k* ∈ {0, 1}^{⌈log|x|⌉} having the property that *Kt*(*x*) ≤ *k.* As is well known, we can always produce a string by hardwiring the string in (the tape of) a machine that does nothing and just halts, which yields the following central fact about (Levin)-Kolmogorov complexity.

FACT 2.1 (^{25}). *There exists a constant c such that for every x* ∈ {0, 1}* *it holds that Kt*(*x*) ≤ |*x*| + *c.*

**Average-case complexity.** We will consider average-case complexity of languages *L* with respect to the *uniform* distribution of instances. Let Heur_{neg}BPP denote the class of languages that can be decided by PPT heuristics that only make mistakes on an inverse polynomial fraction of instances. More formally:

DEFINITION 2.3 (Heur_{neg}BPP). *For a decision problem L* ⊂ {0, 1}*, *we say that L* ∈ Heur_{neg}BPP *if for all polynomial p*(·), *there exists a probabilistic polynomial-time heuristic ℋ*, *such that for all sufficiently large n,*

We will refer to languages in Heur_{neg}BPP as languages that admit *two-sided error* heuristics. We will also consider a more restrictive type of *errorless* heuristics ℋ: for every instance *x*, with probability 0.9 (over the randomness of only ℋ), ℋ(*x*) either outputs *L*(*x*) or ⊥ (for “I don’t know”). More formally:

DEFINITION 2.4 (Avg_{neg}BPP). *For a decision problem L* ⊂ {0, 1}*, *we say that L* ∈ Avg_{neg}BPP *if for all polynomial p*(·), *there exists a probabilistic polynomial-time heuristic ℋ, such that for all sufficiently large n, for every x* ∈ {0, 1}^{n},

*and*

We will refer to languages in Avg_{neg}BPP as languages that admit *errorless* heuristics. As explained in the introduction, to better understand the class Avg_{neg}BPP, it may be useful to compare it to the class Avg_{neg}P (languages solvable by *deterministic* errorless heuristics): *L* ∈ Avg_{neg}P if for every polynomial *p*(·), there exists some deterministic polynomial-time heuristic ℋ such that (a) for every input *x*, ℋ(*x*) outputs either *L*(*x*) or ⊥, and (b) the probability over uniform *n*-bit inputs *x* that ℋ outputs ⊥ is bounded by
. In other words, the *only* way an errorless heuristic may make a “mistake” is by saying ⊥ (“I don’t know”), whereas for a two-sided error heuristic we do not know when mistakes happen. Avg_{neg}BPP is simply the natural “BPP-analog” of Avg_{neg}P where the heuristic is allowed to be randomized.

**Computational indistinguishability.** We recall the definition of (computational) indistinguishability^{8} along with its infinitely-often variant.

DEFINITION 2.5. *Two ensembles* {*A*_{n}}_{n∈ℕ} *and* {*B*_{n}}_{n∈ℕ} *are said to be* ε(·)-*indistinguishable, if for every* PPT *machine D (the “distinguisher”) whose running time is polynomial in the length of its first input, there exists some n*_{0} ∈ ℕ *so that for every n* ≥ *n*_{0}*:*

*We say that* {*A*_{n}}_{n∈ℕ} *and* {*B*_{n}}_{n∈ℕ} *are* infintely-often ε(·)-indistinguishable (io-ε-indistinguishable) *if the above condition holds for infinitely many n* ∈ ℕ *(as opposed to all sufficiently large ones).*

**Pseudorandom generators.** We recall the standard definition of pseudorandom generators (PRGs)^{2} and its infinitely-often variant.

DEFINITION 2.6. *Let g* : {0, 1}^{n} → {0, 1}^{m(n)} *be a polynomial-time computable function. g is said to be a ε*(·)-pseudorandom generator (*ε*-PRG) *if for any* PPT *algorithm A (whose running time is polynomial in the length of its first input), for all sufficiently large n,*

*g is said to be an* infinitely-often *ε*(·)-pseudorandom generator (io-*ε*-PRG) *if the above condition holds for infinitely many n* ∈ ℕ *(as opposed to all).*

Although the standard cryptographic definition of a PRG *g* requires that *g* runs in polynomial time, when used for the other purposes (e.g., for derandomizing BPP), we allow the PRG *g* to have an exponential running time.^{28} We refer to such PRGs (resp. ioPRGs) as *inefficient* PRGs (resp. *inefficient* ioPRGs).

**Conditionally entropy-preserving PRGs.** Liu and Pass^{20} introduced variant of a PRG referred to as an *entropy-preserving* pseudorandom generator (EP-PRG). Roughly speaking, an EP-PRG is a pseudorandom generator that expands *n*-bits to *n* + *O*(log *n*) bits, having the property that the output of the PRG is not only pseudorandom, but also preserves the entropy of the input (i.e., the seed): The Shannon entropy of the output is *n* – *O*(log *n*).^{20} did not manage to construct an EP-PRG from OWFs, but rather constructed a relaxed form of an EP-PRG, called a *conditionally-secure* entropy-preserving PRG (condEP-PRG), which relaxes both the pseudorandomness and entropy-preserving properties of the PRG, to hold only conditioned on some event *E.* We will here consider also an infinitely-often variant:

DEFINITION 2.7. *An efficiently computable function G* : {0, 1}^{n+γ log n} *is a μ*(·)-conditionally secure entropy-preserving pseudorandom generator (*μ*-condEP-PRG) *if there exist a sequence of events* = {*E _{n}*}

_{n∈ℕ}

*and a constant*∝

*(referred to as the*entropy-loss constant)

*such that the following conditions hold:*

**(pseudorandomness):**{*G*(*U*_{n}|*E*_{n})}_{n∈ℕ}*and*{*U*^{n+γ log n}}_{n∈ℕ}*are μ(n)-indistinguishable*;**(entropy-preserving):***For all sufficiently large n*∈ ℕ,*H(G(U*|_{n}*E*_{n}))≥ n –∝log*n*.

*G is referred to as an μ*(·)-conditionally secure entropy-preserving infinitely-often pseudorandom generator (*μ*-condEP-ioPRG) *if it satisfies the above definition except that we replace μ*(*n*)-*indistinguishability with io-μ*(*n*)-*indistinguishability.*

We say that *G* has *rate-1 efficiency* if its running time on inputs of length *n* is bounded by *n* + *O*(*n ^{ε}*) for some constant

*ε*< 1. We recall that the existence of rate-1 efficient condEP-PRGs can be based on the existence of OWFs, and that the same theorem holds in the infinitely-often setting.

THEOREM 2.8 (Implicit in Liu and Pass^{20}). *Assume that OWFs (resp. ioOWFs) exist. Then, for every γ* > 1, *there exists a rate-1 efficient μ-condEP-PRG (resp. μ-condEP-ioPRG) G _{γ}* : {0, 1}

^{n}→ {0, 1}

^{n+γlog n},

*where*.

### 3. Characterizing OWFS

In this section, we prove our main characterization of OWFs through two-sided error average-case hardness of MKtP.

THEOREM 3.1. MKtP ∉ Heur_{neg}BPP *iff infinitely-often OWFs exist.*

We remark that, in full version, we also characterize “standard” (as opposed to infinitely-often) OWFs through (almost-everywhere) mild average-case hardness of MKtP.

Below, we prove each direction of Theorem 3.1 separately (in Theorem 3.2 and Theorem 3.3).

**OWFs from Avg-case hardness of MKtP.** We first show that if weak ioOWFs do not exists, then we can compute the *Kt*-complexity of random strings with high probability (and thus, MKtP is in Heur_{neg}BPP). On a high-level, we will be using the same proof approach as in Liu and Pass^{20} One immediate obstacle to relying on the proof in Liu and Pass^{20} is that it relies on the fact that the program Π (which we refer to as the “witness”) that certifies the time-bounded Kolmogorov complexity *K ^{t}* of a string

*x*has some

*a priori polynomial*running time, namely

*t*(·); this polynomial bound gets translated into the running time of the constructed OWF. Unfortunately, this fact no longer holds when it comes to

*Kt*-complexity: We say that the program Π is a

*Kt-witness*for the string

*x*if Π generates

*x*within

*t*steps while minimizing |Π| + log

*t*among all other programs (i.e., Π is a witness for the

*Kt*-complexity of

*x*). Note that given a

*Kt*-witness of a string

*x*, there is no

*a priori*polynomial time bound on the running time of Π, since only the

*logarithm*of the running time gets included in the complexity measure. For instance, it could be that the

*Kt*-witness is a program Π of length

*n*/10 that requires running time 2

^{n/10}, for a total

*Kt*-complexity of

*n*/5. Nevertheless, the crucial observation we make is that

*for most strings x*, the running time of the

*Kt*-witness actually is small: For every 0 < ε < 1, except for an ε fraction of

*n*-bit strings

*x*,

*x*has a

*Kt*-witness Π that runs in time . More formally:

FACT 3.1. *For all n* ∈ ℕ, 0 < *ε* < 1, *there exists* 1 – *ε fraction of strings x* ∈ {0, 1}^{n} *such that there exist a Turing machine* Π_{x} *and a running time parameter t _{x} satisfying*

*U*(Π

_{x}, 1

^{tx})=

*x*, |Π

_{x}| + ⌈log

*t*⌉=

_{x}*Kt*(

*x*), and

*t*

_{x}≤2

^{c}/

*ε (where c is as in Fact 2.1).*

**Proof:** Consider some *n* ∈ ℕ, 0 < *ε* < 1, and some set *S* ⊂ {0, 1}^{n} such that |*S*| > *ε*2^{n}. For any string *x*∈{0,1}^{n}, let Π_{x}, *t _{x}* be a pair of strings such that

*U*(Π

_{x}, 1

^{tx}) =

*x*and |Π

_{x}| + ⌈log

*t*⌈=

_{x}*Kt*(

*x*); that is, (Π

_{x},

*t*) is the optimal compression for

_{x}*x.*Note that for any

*x*∈ {0, 1}

^{n}, such (Π

_{x},

*t*) always exists due to Fact 2.1. Let

_{x}*c*be the constant from Fact 2.1.

We assume for contradiction that for any *x* ∈ *S*, *t*_{x} > 2^{c}/*ε*. Note that by Fact 2.1, it holds that *Kt*(*x*)≤ |x| + *c*. Thus, |Π_{x}|=*Kt*(*x*)−⌈log *t _{x}*⌉≤

*n*+

*c*−⌈log 2

^{c}/

*ε*⌉≤

*n*−log 1/

*ε*. Consider the set

*Z*= {Π

_{x}:

*x*∈

*S*} of all (descriptions of) Turing machines Π

_{x}. Since |Π

_{x}|≤

*n*−log 1/

*ε*, it follows that |

*Z*|≤2

^{n−log 1/ε}=

*ε*2

^{n}. However, for each machine Π in

*Z*, it could produce only a single string in

*S.*So |

*Z*| ≥ |

*S*| >

*ε*2

^{n}, which is a contradiction. ■

We now show how to adapt the proof in Liu and Pass^{20} by relying on the above fact.

THEOREM 3.2. *If* MKtP ∉ Heur_{neg}BPP, *then there exists a weak ioOWF (and thus also an ioOWF).*

**Proof:** We start with the assumption that MKtP ∉ Heur_{neg}BPP; that is, there exists a polynomial *p*(·) such that for all PPT heuristics ℋ′ and infinitely many *n*,

Let *c* be the constant from Fact 2.1. Consider the function *f*:{0,1}^{n+c+⌈log(n+c)⌉} → {0,1}*, which given an input *ℓ*||Π’ where |*ℓ*| = ⌈log(*n*+*c*)⌉ and |Π’| = *n* + *c*, outputs *ℓ* + ⌈log *t*⌉||*U*(Π, 1^{t}) where Π is the *ℓ*-bit prefix of Π’, *t* is the (smallest) integer ≤ 2^{c+2}*p*(*n*) such that Π (when interpreted as a Turing machine) halts in step *t.* (If Π does not halt in 2^{c+2}*p*(*n*) steps, *f* picks *t* = 2^{c+2}*p*(*n*).) That is,

Observe that *f* is only defined over some input lengths, but by an easy padding trick, it can be transformed into a function *f’* defined over all input lengths, such that if *f* is (weakly) oneway (over the restricted input lengths), then *f’* will be (weakly) one-way (over all input lengths): *f’*(*x’*) simply truncates its input *x’* (as little as possible) so that the (truncated) input *x* now becomes of length *m* = *n* + *c* + ⌈log(*n* + *c*)⌉ for some *n* and outputs *f*(*x*).

We now show that *f* is a
-weak ioOWF where *q*(*n*) = 2^{2c+4}*np*(*n*)^{2}, which concludes the proof of the theorem. Assume for contradiction that *f* is not a
-weak ioOWF; that is, there exists some PPT attacker *A* that inverts *f* with probability at least
for all sufficiently large input lengths *m* = *n* + *c* + ⌈log(*n*+*c*)⌉. We first claim that we can use *A* to construct a PPT heuristic ℋ* such that

If this is true, consider the heuristic ℋ which given a string *x* ∈ {0, 1}^{n} and a size parameter *k* ∈ {0, 1}^{⌈log n⌉}, outputs 1 if ℋ*(*x*)≤*k*, and outputs 0 otherwise. Note that if ℋ* succeeds on some string *x*, ℋ will also succeed. Thus,

which is a contradiction.

It remains to construct the heuristic ℋ* that computes *Kt*(*x*) with high probability over random inputs *x* ∈ {0, 1}^{n}, using *A*. By an averaging argument, except for a fraction
of random tapes *r* for *A*, the *deterministic* machine *A*_{r} (i.e., machine *A* with randomness fixed to *r*) fails to invert *f* with probability at most
. Consider some such “good” randomness *r* for which *A*_{r} succeeds to invert *f* with probability
.

On input *x* {0, 1}^{n}, our heuristic ℋ*_{r} runs *A*_{r}(*i*||*x*) for all *i* ∈ [*n* + *c*] where *i* is represented as a ⌈log(*n*+*c*)⌉-bit string and outputs the smallest *i* where the inversion on (*i*||*x*) succeeds. Let
, and *S* be the set of strings *x* ∈ {0, 1}^{n} for which ℋ*_{r} (*x*) fails to compute *Kt*(*x*) and *x* satisfies the requirements in Fact 3.1. Note that the probability that a random *x* ∈ {0, 1}^{n} does not satisfy the requirements in Fact 3.1 is at most *ε*. Thus, ℋ*_{r} fails with probability at most (by a union bound)

Consider any string *x* ∈ *S* and let *w*=*Kt*(*x*) be its *Kt*-complexity. Note that *x* satisfies the requirements in Fact 3.1; that is, there exist a Turing machine Π_{x} and a running time parameter *t _{x}* such that

*U*(Π

_{x}, 1

^{tx})=

*x*, |Π

_{x}| + ⌈log

*t*

_{x}⌉ =

*Kt*(

*x*), and

*t*≤ 2

_{x}^{c}ε = 2

^{c+2}

*p*(

*n*). By Fact 2.1, we have that |Π

_{x}| ≤

*w*≤

*n*+

*c*. Thus, for all strings (

*ℓ*||Π’) ∈ {0,1}

^{n+c+⌈log(n+c)⌉}such that

*ℓ*= |Π

_{x}|, [Π’]

_{|ℓ|}= Π

_{x}, it holds that

*f*(

*ℓ*||Π’)=(

*w*||

*x*). Since ℋ*

_{r}(

*x*) fails to compute

*Kt*(

*x*),

*A*

_{r}must fail to invert (

*w*||

*x*). But, since |Π

_{x}| ≤

*n*+

*c*, the output (

*w*||

*x*) is sampled with probability at least

in the one-way function experiment, so *A*_{r} must fail with probability at least

which by assumption (that *A*_{r} is a good inverter) is at most that
. We thus conclude that

Finally, by a union bound, we have that ℋ* (using a uniform random tape *r*) fails in computing *Kt* with probability at most

Thus, ℋ* computes *Kt* with probability
for all sufficiently large *n* ∈ ℕ, which is a contradiction. ■

**Avg-case Hardness of MKtP from OWFs.** We additionally show the converse of Theorem 3.2:

THEOREM 3.3. *If ioOWFs exist, then* MKtP ∉ Heur_{neg}BPP.

Theorem 3.3 follows immediately from Theorem 2.8 and the following theorem:

THEOREM 3.4. *Assume that for some* γ ≥ 4, *there exists a rate-1 efficient μ-condEP-ioPRG G* : {0, 1}^{n} → {0, 1}^{n+γ log n} *where μ*(*n*) = 1/*n*^{2}. *Then*, MKtP ∉ Heur_{neg}BPP.

The proof of Theorem 3.4 closely follows the proof in Liu and Pass^{20} and relies only on relatively minor modifications to observe that the properties used of the time-bounded Kolmogorov complexity function *K ^{t}* actually also hold for

*Kt*—namely that random strings have “high”

*Kt*-complexity, whereas outputs of a PRG have “low”

*Kt*-complexity. We refer the reader to the full version for the actual proof.

### 4. Characterizing EXP

In this section, we will prove the following theorem:

THEOREM 4.1. EXP ≠ BPP *if and only if* MKtP ∉ Avg_{neg}BPP.

Roughly speaking, the above theorem is proved in two steps:

- We first observe that, assuming EXP ≠ BPP, there exists an (inefficient, infinitely-often) pseudorandom generator
^{14}that maps a*n*-bit seed to a^{ε}*n*-bit string in time*O*(2^{nγ}) (for some 0 <*ε, γ*< 1). - We will next show that an errorless heuristic for MKtP can be used to break such PRGs (since the
*Kt*-complexity of the output of the PRG is at most*n*+^{ε}*n*+^{γ}*O*(1) ≤*n*–1), which is a contradiction and concludes the proof.

Recall that Impagliazzo and Wigderson^{14} showed that BPP can be derandomized (on average) in subexponential time by assuming EXP ≠ BPP. The central technical contribution in their work can be stated as proving the existence of an inefficient PRG assuming EXP ≠ BPP:

THEOREM 4.2 (^{14}, [^{28}, THEOREM 3.9]). *Assume that* EXP ≠ BPP. *Then, for all ε* > 0, *there exists an inefficient*
*that runs in time* 2^{O(nε)}.

We note that the proof in Impagliazzo and Wigderson^{14} is non-black box. In particular, it does not show how to solve EXP in probabilistic polynomial-time having black box access to an attacker that breaks the PRG.

It remains to show that if there exists an (inefficient) io-PRG *G* : {0, 1)^{nε} → ® {0, 1)^{n} with running time *O*(2^{nγ}) (for some 0 < *ε*, *γ* < 1), then MKtP ∉ Avg_{neg}BPP. We recall that a string’s *Kt*-complexity is the minimal sum of (1) the description length of a Turing machine that prints the string and (2) the logarithm of its running time. Note that the output of *G* could be printed by a machine with the code of *G* (of constant length) and the seed (of length *n*^{ε}) hardwired in it within *O*(2^{nγ}) time. Thus, strings output by *G* have *Kt*-complexity less than or equal to *O*(1)+*n ^{ε}*+

*n*≤

^{γ}*n*− 1. On the other hand, random strings have high

*Kt*-complexity (e.g., >

*n*– 1) with high probability (e.g., ). It follows that an errorless heuristic for MKtP can be used to break

*G.*Let us highlight why it is important that we have an

*errorless*heuristic (as opposed to a two-sided error heuristic): while a two-sided error heuristic would still work well on random strings, we do not have any guarantees on its success probability given pseudorandom strings (as they are sparse); an errorless heuristics, however, will either correctly decide those strings, or output ⊥ (in which case, we can also guess that the string is pseudorandom).

We proceed to a formal statement of the theorem, and its proof.

THEOREM 4.3. *Assume that there exist constants* 0 < *ε, γ* < 1 *and an inefficient*
*with running time* *O*(2^{nγ}). *Then*, MKtP ∉ Avg_{neg}BPP.

**Proof:** We assume for contradiction that MKtP ∈ Avg_{neg}BPP, which in turn implies that there exists an errorless PPT heuristic ℋ such that for all sufficiently large *n*, every *x* ∈ {0, 1}^{n} and *k* ∈ {0, 1}^{⌈log n⌉},

and

Fix some sufficiently large *n*, and let *k* = *n* – 1. It follows by an averaging argument that

We next show that we can use ℋ to break the PRG *G.* On input *x* ∈ {0, 1}^{n}, our distinguisher *A*(1^{nε}, *x*) outputs 1 if ℋ(*x*, *n*−1)=1 or ℋ(*x*, n-1)=⊥. *A* outputs 0 if and only if ℋ(*x*, *n* – 1) = 0. The following two claims conclude that *A* distinguishes *U*_{n} and *G* (*U*_{nε}) with probability at least 0.2.

CLAIM 1. *A*(1^{nε}, *U _{n}*)

*will output 0 with probability at least*.

**Proof:** Note that the probability that a randorn string *x* ∈ {0, 1}^{n} is of *Kt*-complexity at most *n* – 1 is at most
(since the total number of machines with description length ≤ *n* – 1 is 2^{n−1}). And the probability that ℋ(*x*, *n*–1) outputs ⊥ is at most
(over random *x* ∈ {0, 1}^{n}) by Equation 2. In addition, the probability that ℋ(*x*, *n* – 1) fails to output either MKtP(*x*, *n* – 1) or ⊥ is at most 0.1 by Equation 1. Thus, by a union bound,

CLAIM 2. *A*(1^{nε}, *G*(*U _{nε}*))

*will output 0 with probability at most*0.1.

**Proof:** We first show that for all *Z* ∈ {0, 1}* ^{nε}*,

*Kt*(

*G*(

*z*)) ≤

*n*

^{ε}+

*n*

^{γ}+

*O*(1)≤n − 1. Note that the string

*G*(

*z*) could be produced by a machine with the code of

*G*(of length

*O*(1)) and the seed

*z*(of length

*n*

^{ε}) in time

*O*(2

^{nγ}) (which adds log

*O*(2

^{nγ}) =

*n*

^{γ}+

*O*(1) to its

*Kt*-complexity). In addition, recall that ℋ is a probabilistic errorless heuristics. Thus, ℋ(

*G*(

*z*),

*n*– 1) will output 0 with probability at most 0.1 (by Equation 1), and the claim follows. ■

This conclude the proof of Theorem 4.3. ■

We are now ready to conclude the proof of Theorem 4.1.

**Proof:** [of Theorem 4.1] We show each direction separately:

- To show that EXP ≠ BPP ⇒ MKtP ∉ Avg
_{neg}BPP, assume that EXP ≠ BPP and let , and . By Theorem 4.2, there exists an with running time 2^{O(nε)}≤*O*(2^{nγ}). We conclude by Theorem 4.3 that MKtP ∉ Avg_{neg}BPP. - To show that MKtP ∉ Avg
_{neg}BPP ⇒ EXP ≠ BPP, assume that MKtP ∉ Avg_{neg}BPP; this trivially implies that MKtP ∈ BPP. We observe that MKtP ∈ EXP as by Fact 2.1,*Kt*(*x*) ≤ |*x*| +*O*(1) and thus the running time for a*Kt*-witness, Π, for*x*is bounded by 2^{|x|+O(1)}. Thus, EXP ⊈ BPP, which in particular means that EXP ≠ BPP. ■

### 5. Conclusions and Barriers

Recall that in Theorem 4.1, we showed that if we assume that EXP ≠ BPP, then MKtP is hard-on-average for errorless heuristics. Furthermore, in Theorem 3.2, we showed that if MKtP is hard-on-average for two-sided error heuristics, then (infinitely-often) one-way functions exist. Combining the two theorems together, we have that the implication MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP fully characterizes when we can base the existence of (infinitely-often) oneway functions on EXP ≠ BPP. Formally,

THEOREM 5.1. MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP *holds iff* EXP ≠ BPP *implies the existence of ioOWFs.*

Perhaps surprisingly, we observe that the implication by itself (without any assumptions) implies that NP ≠ P:

THEOREM 5.2. *If it holds that* MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP, *then* NP ≠ P.

**Proof:** Assume for contradiction that MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP holds, yet NP = P. Recall that BPP ⊆ NP^{NP,24,17} so it follows that P = BPP, and thus by the time hierarchy Theorem,^{10} EXP ≠ BPP. Then, by Theorem 4.1, MKtP ∉ Avg^{neg}BPP. It follows from our assumption that MKtP ∉ Avg_{neg}BPP ⇒ MKtP ∉ Heur_{neg}BPP and from Theorem 5.1 that ioOWFs exist, which contradicts the assumption that NP = P. ■

We remark that the above theorem could be strengthened to show even that NP is average-case hard (w.r.t. deterministic errorless heuristics), since Buhrman, Fortnow, and Pavan^{4} have showed that unless this is the case, P = BPP, which suffices to complete the rest of the proof.

The pessimistic way to interpret Theorem 5.2 is that closing the gap between two-sided error, and errorless, heuristics for MKtP will be very hard as it requires proving that NP ≠ P. The optimistic way to interpret it, however, is as a new and algorithmic approach toward proving that NP ≠ P: To demonstrate that NP ≠ P, it suffices to demonstrate that MKtP can be solved by an errorless heuristic, given access to a two-sided error heuristic for the same problem. Additionally, note that approach also does not “overshoot” the NP vs. P problem by too much. In fact, any proof of the existence of infinitely often one-way functions needs to also show this implication since by Theorem 3.3, the existence of ioOWFs implies MKtP ∉ Heur_{neg}BPP, which in turn implies that the implication trivially holds.

### Acknowledgments

This work is supported in part by NSF Award SATC-1704788, NSF Award RI-1703846, AFOSR Award FA9550-18-1-0267, and a JP Morgan Faculty Award. This material is based upon work supported by DARPA under Agreement No. HR00110C0086. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the U.S. Government or DARPA. We are very grateful to Salil Vadhan for helpful discussions about the PRG construction of Impagliazzo and Wigderson.^{14} The first author also wishes to thank Hanlin Ren for helpful discussions about Levin’s notion of Kolmogorov Complexity. Finally, we are grateful to the CRYPTO’21 PC for their helpful comments (Y.V. and R.P.).

## Join the Discussion (0)

## Become a Member or Sign In to Post a Comment