Communications of the ACM

Research Highlights

Toward Basing Cryptography on the Hardness of EXP

By Yanyi Liu, Rafael Pass
Communications of the ACM, May 2023, Vol. 66 No. 5, Pages 91-99
10.1145/3587167
Comments

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_negBPP (i.e., MKtP is two-sided error mildly average-case hard) iff infinitely-often OWFs exist.
• MKtP ∉ Avg_negBPP (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.

Back to Top

1. Introduction

A one-way function⁶ (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¹⁹): OWFs are both necessary¹² and sufficient for many of the most central cryptographic primitives and protocols (e.g., pseudorandom generators,^{2, 11} pseudo-random functions,⁷ private-key encryption,⁸ 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 that EXP ≠ 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.¹⁸ 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,²⁶ Kolmogorov,¹⁶ and Chaitin,⁵ 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,²⁷ the problem of efficiently determining the K^t-complexity for 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,²⁴ Ko,¹⁵ and Hartmanis⁹ from the early 1980s.

A very recent result by Liu and Pass²⁰ 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.¹⁸ 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¹⁸ 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.¹ 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³) 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_negBPP 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_negBPP, it may be useful to compare it to the class Avg_negP (languages solvable by deterministic errorless heuristics): L ∈ Avg_negP 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_negBPP is simply the natural "BPP-analog" of Avg_negP where the heuristic is allowed to be randomized.

 1.3. Our results

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

THEOREM 1.1. MKtP ∉ Heur_negBPP iff infinitely-often OWFs exist.

We highlight that whereas²⁰ 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²⁰ considered an "almost-everywhere" notion of average-case hardness of K^t, whereas the statement MKtP ∉ Heur_negBPP 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.²⁰ 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²⁰ 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}ⁿ 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ⁿ 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²⁰

Errorless average-case hardness of MKtP. We next show how to extend the result of Allender et al.¹ 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¹ 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_negBPP iff EXP ≠ BPP.

Theorem 1.2 follows a similar structure as the EXP-completeness results of Allender et al.¹ Roughly speaking, Allender et al. observe that by the result of Nisan and Wigderson²¹ and Impagliazzo and Wigderson,¹³ 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,¹⁴ 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_negBPP ⇒ MKtP ∉ Heur_negBPP). 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_negBPP ⇒ MKtP ∉ Heur_negBPP.

As a corollary of Theorem 1.1 and Theorem 1.2, we next demonstrate that the implication MKtP ∉ Avg_negBPP ⇒ MKtP ∉ Heur_negBPP implies that NP ≠ P.

THEOREM 1.3. If MKtP ∉ Avg_negBPP ⇒ MKtP ∉ Heur_negBPP, 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²³ 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.

Back to Top

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₀ 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}ⁿ. 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.⁶ 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,²² 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,²⁹ 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²⁹ 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¹⁸:

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 (²⁵). 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_negBPP 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_negBPP). For a decision problem L ⊂ {0, 1}*, we say that L ∈ Heur_negBPP 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_negBPP 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_negBPP). For a decision problem L ⊂ {0, 1}*, we say that L ∈ Avg_negBPP if for all polynomial p(·), there exists a probabilistic polynomial-time heuristic ℋ, such that for all sufficiently large n, for every x ∈ {0, 1}ⁿ,

and

We will refer to languages in Avg_negBPP as languages that admit errorless heuristics. As explained in the introduction, to better understand the class Avg_negBPP, it may be useful to compare it to the class Avg_negP (languages solvable by deterministic errorless heuristics): L ∈ Avg_negP 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_negBPP is simply the natural "BPP-analog" of Avg_negP where the heuristic is allowed to be randomized.

Computational indistinguishability. We recall the definition of (computational) indistinguishability⁸ 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₀ ∈ ℕ so that for every n ≥ n₀:

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)² and its infinitely-often variant.

DEFINITION 2.6. Let g : {0, 1}ⁿ → {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.²⁸ We refer to such PRGs (resp. ioPRGs) as inefficient PRGs (resp. inefficient ioPRGs).

Conditionally entropy-preserving PRGs. Liu and Pass²⁰ 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).²⁰ 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²⁰). Assume that OWFs (resp. ioOWFs) exist. Then, for every γ > 1, there exists a rate-1 efficient μ-condEP-PRG (resp. μ-condEP-ioPRG) G_γ : {0, 1}ⁿ → {0, 1}^{n+γlog n}, where .

Back to Top

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_negBPP 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_negBPP). On a high-level, we will be using the same proof approach as in Liu and Pass²⁰ One immediate obstacle to relying on the proof in Liu and Pass²⁰ 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}ⁿ such that there exist a Turing machine Π_x and a running time parameter t_x satisfying U(Π_x, 1^t_x)=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}ⁿ such that |S| > ε2ⁿ. For any string x∈{0,1}ⁿ, let Π_x, t_x be a pair of strings such that U(Π_x, 1^t_x) = x and |Π_x| + ⌈log t_x⌈=Kt(x); that is, (Π_x, t_x) is the optimal compression for x. Note that for any x ∈ {0, 1}ⁿ, such (Π_x, t_x) always exists due to Fact 2.1. Let 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ⁿ. However, for each machine Π in Z, it could produce only a single string in S. So |Z| ≥ |S| > ε2ⁿ, which is a contradiction. ■

We now show how to adapt the proof in Liu and Pass²⁰ by relying on the above fact.

THEOREM 3.2. If MKtP ∉ Heur_negBPP, then there exists a weak ioOWF (and thus also an ioOWF).

Proof: We start with the assumption that MKtP ∉ Heur_negBPP; 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+2p(n) such that Π (when interpreted as a Turing machine) halts in step t. (If Π does not halt in 2^c+2p(n) steps, f picks t = 2^c+2p(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+4np(n)², 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}ⁿ 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}ⁿ, 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}ⁿ, 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}ⁿ 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}ⁿ 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^t_x)=x, |Π_x| + ⌈log t_x⌉ = Kt(x), and t_x ≤ 2^cε = 2^c+2p(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_negBPP.

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}ⁿ → {0, 1}^{n+γ log n} where μ(n) = 1/n². Then, MKtP ∉ Heur_negBPP.

The proof of Theorem 3.4 closely follows the proof in Liu and Pass²⁰ 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.

Back to Top

4. Characterizing EXP

In this section, we will prove the following theorem:

THEOREM 4.1. EXP ≠ BPP if and only if MKtP ∉ Avg_negBPP.

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¹⁴ 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¹⁴ 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 (¹⁴, [²⁸, 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¹⁴ 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)ⁿ with running time O(2^nγ) (for some 0 < ε, γ < 1), then MKtP ∉ Avg_negBPP. 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_negBPP.

Proof: We assume for contradiction that MKtP ∈ Avg_negBPP, which in turn implies that there exists an errorless PPT heuristic ℋ such that for all sufficiently large n, every x ∈ {0, 1}ⁿ 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}ⁿ, 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}ⁿ is of Kt-complexity at most n – 1 is at most (since the total number of machines with description length ≤ n – 1 is 2ⁿ⁻¹). And the probability that ℋ(x, n–1) outputs ⊥ is at most (over random x ∈ {0, 1}ⁿ) 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_negBPP, 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_negBPP.
• To show that MKtP ∉ Avg_negBPP ⇒ EXP ≠ BPP, assume that MKtP ∉ Avg_negBPP; 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. ■

Back to Top

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_negBPP ⇒ MKtP ∉ Heur_negBPP fully characterizes when we can base the existence of (infinitely-often) oneway functions on EXP ≠ BPP. Formally,

THEOREM 5.1. MKtP ∉ Avg_negBPP ⇒ MKtP ∉ Heur_negBPP 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_negBPP ⇒ MKtP ∉ Heur_negBPP, then NP ≠ P.

Proof: Assume for contradiction that MKtP ∉ Avg_negBPP ⇒ MKtP ∉ Heur_negBPP holds, yet NP = P. Recall that BPP ⊆ NP^NP,24,17 so it follows that P = BPP, and thus by the time hierarchy Theorem,¹⁰ EXP ≠ BPP. Then, by Theorem 4.1, MKtP ∉ Avg^negBPP. It follows from our assumption that MKtP ∉ Avg_negBPP ⇒ MKtP ∉ Heur_negBPP 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⁴ 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_negBPP, which in turn implies that the implication trivially holds.

Back to Top

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.¹⁴ 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.).

Back to Top

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2023 ACM, Inc.

---

No entries found