One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

As mentioned, we are relying on the most classic derandomization assumption in the literature; that is, the existence of a function $f:{\{0,1\}}^n\to \{0,1\}$ computable in $2^{cn}$ time for some constant $c$, that cannot be computed in by circuits of size $2^{ϵn}$ for some constant $ϵ$. This is the assumption used by [28] to demonstrate that $\mathrm{𝖡𝖯𝖯}=𝖯$.

This assumption was first strengthened by [29] to require hardness against non-deterministic circuits. Following [4], [39], considered an even stronger version, requiring the existence of $c,ϵ$ such that for every $k$ (i.e., we require a hierarchy of hard functions), there exists a function running in time $2^{c\cdot kn}$ that is secure against non-deterministic attackers with running time $2^{ϵkn}$ but still only $2^{ϵn}$ advice. Note that compared to this assumption, ours is weaker in two respects: (a) we no longer require non-deterministic hardness, and most importantly (b) we no longer require an infinite hierarchy of hard functions over a fixed input length.

The above results still require worst-case of the boundary version of ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$. As mentioned, ideally, we would like to base OWFs on worst-case hardness of just the ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ problem. Beyond being interesting in its own right, this question is motivated by the fact that in recent years, there has been great progress (see e.g. [21, 25, 22] [23, 36, 17, 24]) towards showing that problem is $\mathrm{𝖭𝖯}$-complete. Notably, if OWFs can be based on the worst-case hardness of this problem, and the problem can be shown to be $\mathrm{𝖭𝖯}$-complete, then we would base OWFs on just the assumption that $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$ (a problem left open since the work by Diffie and Hellman [5], and referred to as the “holy-grail”).

Intriguingly, a result by Hirahara [14] shows that if we were to consider a “gap” version of the $K^t$ problem, referred to as ${\mathrm{𝖦𝖺𝗉𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}[s,s+n^{ϵ}]$, where the goal is to distinguish between $x$ such that and $K^{t_2}(x)>s+n^{ϵ}$, for all $t_2=\mathrm{𝗉𝗈𝗅𝗒}(t_1)$, then worst-case hardness of this problem implies what is referred to as errorless average-case hardness (w.r.t. deterministic algorithms). Roughly speaking, errorless average-case hardness refers to average-case hardness w.r.t. algorithms that either provide the right answer or $\perp$ (and $\perp$ should only be output with small probability). In other words, hardness holds w.r.t. algorithms that “know” when they fail. This is in contrast to the notion of two-sided error hardness where we allow the attacker to fail (without knowing it) on some small set of inputs. (Unfortunately, to apply the result of [33], we require the more standard notion of two-sided error average-case hardness, so this result is not helpful in terms of getting OWFs, at least given current machinery.) Hirahara [16], subsequently showed that under the assumption that $𝖤⊈\mathrm{𝗂𝗈𝖲𝖨𝖹𝖤}[2^{o(n)}]$, the same result can be established when the “gap” is just $\mathrm{\Omega }(\log n)$, as opposed to $n^{ϵ}$ (i.e., for ${\mathrm{𝖦𝖺𝗉𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}[s,s+O(\log n)]$).

As our final result, and using the same technique as the proof of our main theorem, we show how to strengthen Hirahara’s result to directly apply to ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ (as opposed to the gap version of this problem).

As mentioned, Hirahara [14, 15] shows (under the same derandomization assumption) a worst-case to average-case reduction for a gap version of the ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ problem, where there is a gap of $\mathrm{\Omega }(\log n)$ between the $K^{\mathrm{𝗉𝗈𝗅𝗒}}$ complexity of YES and NO instances (on top of the gap between the running times). Theorem 1.3 improves the results of [14, 15, 8] by removing the gap in the large threshold regime (i.e, when deciding whether $K^{\mathrm{𝗉𝗈𝗅𝗒}}$ is larger or smaller than $s(n)=n-O(1)$): As far as we know, Theorem 1.3 is the first worst-case to average-case reduction for simply the ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ problem (and not the ${\mathrm{𝖦𝖺𝗉𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ problem).

We mention, however, that while our proof technique is very different from the one in [14, 15], and is also significantly simpler, it has the disadvantage that it only works in the large threshold regime (i.e., $s(n)=n-O(1)$) , whereas Hirhara’s technique also works for smaller thresholds $s(n)$ (but again, only for the gap version).

Additionally, if focusing on $r{K}^t$ (as opposed to $K^t$) and only considering average-case hardness against deterministic polynomial-time algorithms (as in [14]), then we can show unconditionally obtain a worst-case to average-case reduction.

Taken together, our results provide the appealing characterization of the worst-case hardness of the time-bounded Kolmogorov complexity problem (under standard derandomization assumption) provided in Figure 1.

Roughly speaking, the results of [39] first rely on the result of [33, 38] showing that average-case hardness of $p{K}^t$ implies the existence of OWFs. In more detail, [33, 38] present a reduction for solving ${\mathrm{𝖬𝖨𝖭𝗉𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ on average given a OWF inverter (for their specific OWF) (referred to as the LP20 reduction). [39] showed that the LP20 reduction, in fact, also correctly decides ${\mathrm{𝖬𝖨𝖭𝗉𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ on all instances that “are along boundary”.

This was proved in the following two steps: (1) [39] showed that elements on which the reduction fails can be sampled with probability $\ge n^c/2^n$ for any $c$, by an algorithm running in time $T=\mathrm{𝗉𝗈𝗅𝗒}(n^c)$; and (2) relying on a so-called “Coding Theorem” [42], [39] proved the $p{K}^T$ complexity of an element is, roughly, at most the logarithm of the inverse of the probability by which it can be sampled. Taken together, the reduction only fails on the elements of small $p{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$ complexity (roughly at most $\log (2^n/n^c)=n-c\log n$), and thus will succeed on elements of either “intermediate” or “large” complexity – instances that are along the boundary.

We plan to rely on the same outline: take the LP20 reduction for $r{K}^t$ and prove that it is correct on all boundary instances. However, to make the above proof also work w.r.t. $r{K}^t$, we would need a “Coding Theorem” for $r{K}^t$ without assuming any derandomization assumptions, which is still open. A step towards such a Coding Theorem was recently taken by Hirahara et al [19], which shows that an “average-case coding theorem for $r{K}^t$” can be achieved assuming access to a OWF inverter. While in our setting, it is allowed to assume a OWF inverter (since we aim to establish the existence of OWFs), their notion unfortunately will not suffice for us – we require a coding theorem (that achieves non-trivial compression) for all strings in the support of the sampler.

While it does not apply directly, it is instructive here to recall the techniques used in [19] to achieve $r{K}^t$-type compression. [19] relied on the result of Goldberg and Sipser [7], in which they showed that all sparse languages in $\mathrm{𝖡𝖯𝖯}$ admit a so-called language compression scheme, where a language compression scheme allows to compress all instances in a language by logarithmically many bits. [19] observed that admitting a language compression also implies that every instance in the language has small $r{K}^t$ complexity (at most $n-O(\log n)$).

Thus, it would be sufficient for us to prove that the language of all the elements on which the LP20 reduction fails, denoted by the language $\mathrm{𝖡𝖺𝖽}$, admits a language compression scheme. $\mathrm{𝖡𝖺𝖽}$ is indeed a sparse language (since, as mentioned, [39] showed that any instance in $\mathrm{𝖡𝖺𝖽}$ can be sampled with probability $\ge n^c/2^n$ – there can be at most $2^n/n^c$ of them). However, it is unclear that $\mathrm{𝖡𝖺𝖽}$ is in $\mathrm{𝖡𝖯𝖯}$: to check whether the reduction fails, we would need a “$r{K}^t$-witness”, which cannot be efficiently found.

Our key observation is that instead of considering $\mathrm{𝖡𝖺𝖽}$, the set of bad instances, we can consider the set of $r{K}^t$-witnesses of bad instances, denoted as $\mathrm{𝖡𝖺𝖽𝖶𝗍𝗇𝗌}$. We first remark that as a corollary of the [33] reduction, we have that not only $\mathrm{𝖡𝖺𝖽}$ is sparse, but also $\mathrm{𝖡𝖺𝖽𝖶𝗍𝗇𝗌}$. In addition, $\mathrm{𝖡𝖺𝖽𝖶𝗍𝗇𝗌}$ is in $\mathrm{𝖡𝖯𝖯}$ since one can produce the bad instance from a bad witness (by running the witness as a program), run the reduction on the instance, and check whether it fails using the witness. Finally, notice that if all $r{K}^t$-witness of bad instances have small $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$ complexity, the instances themselves will also have small $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$-complexity, since, again, the instances can be obtained from running the witnesses. The above simple approach suffices to show that worst-case hardness of deciding whether $K^t(x)$ is large or small conditioned on $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}(t)}>n-\log n$. To obtain the full result from just boundary hardness of $r{K}^t$ we need to adjust the OWF construction from [33] to consider also randomized programs, which requires additional care – we refer the reader to the formal proof for the details.

We highlight that the only reason the above approach requires using $r{K}^t$ as opposed to $K^t$ is that the decoding (“decompression”) algorithm of [7] is randomized. However under standard derandomization assumption, we can simply derandomize this algorithm (by enumerating all seeds to a complexity-theoretic PRG and picking the most likely output) and obtain a deterministic decoding. This suffices to show the same result but starting with just boundary hardness of $K^t$.

Let us briefly mention how this contrasts with the approach in [39] (and in particular, how we are able to weaken the derandomization assumption). There, the authors established an unconditional characterization of OWFs in terms of boundary of $p{K}^t$ and next relied on a strong derandomization assumption to obtain a similar bound w.r.t. $K^t$; the fact that we can get the characterization in terms of $r{K}^t$ is what enables us to use a much weaker derandomization assumptions.⁴⁴4We highlight that it is an open problem that obtain a tight bound on the distance of $p{K}^t$ and $K^t$ based on standard derandomization assumptions.

We finally outline the idea behind our new worst-case to average-case reduction for $K^t$ under derandomization assumptions. For simplicity, we here argue that worst-case hardness implies errorless hardness against deterministic algorithms (but the argument also readily extends to the case of randomized heuristic with some care). The key point is that instances on which an errorless reduction fails are sparse and explicitly identifiable (since the heuristic needs to output $\perp$). Thus, we can again use the language compression algorithm of [7] to compress them, and thus by the above argument, their $K^t$-complexity must be bounded by $n-\log n$ (under derandomization assumptions, and unconditionally if considering $r{K}^t$). So any errorless heuristic can be turned in to a worst-case decider for $K^t$ (resp. $r{K}^t$) by simply outputting $YES$ whenever the heuristic outputs $\perp$!

The theorem follows from Theorem 4.3 (which together with Yao’s hardness amplification Theorem, Theorem 2.3), proves the “if” direction; the “only-if” direction is proved in Theorem 4.7. $◀$

Our next result extends this theorem to obtain a characterization of OWFs based on the worst-case hardness of the boundary version of ${\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$; this time, however, we will rely on a standard derandomization assumption.

The “if” direction follows from Theorem 4.6 together with Yao’s hardness amplification Theorem (Theorem 2.3); the “only-if” direction was already proved in [39] (without relying on any derandomization assumption). $◀$

Consider any polynomial $t_1(n)$, and assume that for all $t_2\ge t_1$, $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}\notin \mathrm{𝗂𝗈𝖡𝖯𝖯}$. We consider the function $f:{\{0,1\}}^{\lceil \log (n)\rceil +n+t_1(n)\cdot n^3}\to {\{0,1\}}^{\ast }$, which takes an input $\mathrm{\ell }\Vert {\mathrm{\Pi }}^{\prime }\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3}$ where $|\mathrm{\ell }|=\lceil \log (n)\rceil$, $|{\mathrm{\Pi }}^{\prime }|=n$ and $|r_i|=t_1(n)$ for each $i\in [n^3]$, computes for each $i\in [n^3]$

where $\mathrm{\Pi }$ is the $\mathrm{\ell }$-bit prefix of ${\mathrm{\Pi }}^{\prime }$ (and the bit-string $\mathrm{\ell }$ is interpreted as an integer $\in [n]$), and ${\mathrm{\Pi }}_{r_i}$ denotes the program $\mathrm{\Pi }$ with random tape $r_i$. If there exists a string $x$ such that the majority among $x_i$ equals $x$, it outputs

Otherwise (i.e., there is no majority among $x_i$) it outputs $\perp$.

This function is only defined over some input lengths, but by an easy padding trick, it can be transformed into a function $f\mathrm{’}$ defined over all input lengths, such that if $f$ is weakly one-way (over the restricted input lengths), then $f\mathrm{’}$ will be weakly one-way (over all input lengths): $f\mathrm{’}(x^{\prime })$ simply truncates its input $x^{\prime }$ (as little as possible) so that the (truncated) input $x$ now becomes of length $n^{\prime }=\lceil \log (n)\rceil +n+t_1(n)\cdot n^3$ for some $n$ and outputs $f(x)$. This will decrease the input length by a polynomial factor (since $t_1$ is a polynomial) so the padding trick can be applied here.

We show that $f$ is a weak OWF (over the restricted input length). Let $q(n)=24{(2n)}^6$. We assume for contradiction that $f$ is not $\frac{1}{q}$-weak one-way. (In the proof below, although the input length of $f$ we consider is $m=\lceil \log (n)\rceil +n+t_1(n)\cdot n^3$ for some $n$, we will view $n$ as the “security parameter”, computing the running time and the inverting success probability in terms of the security parameter $n$, but analyzing the one-wayness of $f$ on input length $m=m(n)$. Since $n$ and $m$ are polynomially related, we can still conclude that $f$ is weak one-way.) Then, there exists a $\mathrm{𝖯𝖯𝖳}$ attacker $𝒜$ that inverts $f$ with probability at least $1-\frac{1}{q(n)}$ for infinitely many $n$.

We turn to constructing a $\mathrm{𝖯𝖯𝖳}$ algorithm $M$ deciding whether an input $x$ is of $r{K}^{t_1}$-complexity . Our algorithm $M$, on input $x\in {\{0,1\}}^n$, samples $n^3$ random strings $r_1,\mathrm{\dots },r_{n^3}\in {\{0,1\}}^{t_1(n)}$. Then, it runs $𝒜(i\Vert x\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3})$ for every $i\in [n]$ where $i$ is represented as a $\lceil \log (n)\rceil$-bit string. In addition, $M(x)$ checks whether $𝒜$ successfully finds a valid pre-image of $f$ on $i\Vert x\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3}$. Finally, $M(x)$ outputs YES if and only if the shortest index $i$ on which $𝒜$ succeeds in inverting $f$ is . (Otherwise, output NO.) Since $𝒜$ runs in polynomial time, the algorithm $M$ will also terminate in polynomial time.

We will show that the algorithm $M$ decides the promise problem $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}$ for some polynomial $t_2$ (which will be fixed later). Toward this, we consider a promise problem $\mathrm{𝖥𝖺𝗂𝗅}$ defined as follows: For any $y\in {\{0,1\}}^{n+\lceil \log (n)\rceil }$, we view $y$ as $\mathrm{\ell }||{\mathrm{\Pi }}^{\prime }$ where $\mathrm{\ell }=\lceil \log (n)\rceil$ and $|{\mathrm{\Pi }}^{\prime }|=n$. Let $p_y$ denote the probability that $𝒜$ fails to invert $f$ on $f(\mathrm{\ell }\Vert {\mathrm{\Pi }}^{\prime }\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3})$ where $r_1,\mathrm{\dots },r_{n^3}\in {\{0,1\}}^{t_1(n)}$ are sampled at random. We define $y\in {\mathrm{𝖥𝖺𝗂𝗅}}_{\mathrm{𝖸𝖤𝖲}}$ if $p_y\ge 1/6$ (and $y\in {\mathrm{𝖥𝖺𝗂𝗅}}_{\mathrm{𝖭𝖮}}$ if ). Since both $f$ and $𝒜$ are efficient, we have that $\mathrm{𝖥𝖺𝗂𝗅}\in \mathrm{𝖡𝖯𝖯}$.

Pick $k=6$. By Theorem 2.5, there exists a $(1/n^{\prime 6},n^{\prime }-3\log n^{\prime })$-language-compression scheme for $\mathrm{𝖥𝖺𝗂𝗅}$ (where $n^{\prime }$ denotes the input length for $\mathrm{𝖥𝖺𝗂𝗅}$). Let $\mathrm{𝖣𝖾𝖼}$ denote the decoding (or decompressing) algorithm for the scheme.

Select $t_2(n)$ to be the runtime bound for the following algorithm $\mathrm{𝖱𝖾𝖼𝗈𝗇}$: Run the decoding algorithm $\mathrm{𝖣𝖾𝖼}$ (on some valid compression of $y$) to get an instance $y\in {\mathrm{𝖥𝖺𝗂𝗅}}_{\mathrm{𝖸𝖤𝖲}}$, $y\in {\{0,1\}}^{n+\lceil \log (n)\rceil }$. Since $y$ can be viewed in the form of $\mathrm{\ell }||{\mathrm{\Pi }}^{\prime }$, let $y=\mathrm{\ell }||{\mathrm{\Pi }}^{\prime }$ and let $\mathrm{\Pi }$ be the $\mathrm{\ell }$-bit prefix of the string ${\mathrm{\Pi }}^{\prime }$. Run $\mathrm{\Pi }$ over a random random-tape $r$ for $t_1(n)$ of steps and output the output of ${\mathrm{\Pi }}_r$.

Now we are ready to show that $M$ decides $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}$ for infinitely many input lengths $n$. Fix some sufficiently large input length $n$ where $𝒜$ inverts the function $f$ with probability $1-\frac{1}{q(n)}$ on $n$. We first show that if $x$ is a NO instance of $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}$, $M(x)$ outputs NO with probability $\ge 2/3$.

We show that $M(x)$ outputs YES with probability $\le 1/3$. Recall that $M(x)$ will output YES if there exists an index $i\le n-4$ and a program $\mathrm{\Pi }$ of length $i$ such that ${\mathrm{\Pi }}_{r_j}$ outputs $x$ for a half fraction of random-tapes $r_j$, $j\in [n^3]$. We refer to such $r_1,\mathrm{\dots },r_{n^3}$ as being “bad”.

We turn to showing that among all possible choices of random tapes, there are at most a $1/3$ fraction of them being bad. Consider any program ${\mathrm{\Pi }}^{\prime \prime }$ of length $w\le n-4$. Since $r{K}_{1/3}^{t_2}(x)\ge n-3$, by a standard Chernoff bound, there is no more than $2^{-n\sqrt{n}+O(1)}$ fraction of $r_1,\mathrm{\dots },r_{n^3}$ such that ${\mathrm{\Pi }}_{r_j}^{\prime \prime }$ outputs $x$ for a majority of $r_j$. Taking a Union bound over all possible ${\mathrm{\Pi }}^{\prime \prime }$, we conclude that the probability that $r_1,\mathrm{\dots },r_{n^3}$ is bad is at most

when $n$ is sufficiently large. $\mathrm{⊲}$

Finally, we show that if $x$ is a YES instance of $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}$, $M(x)$ will output YES with probability $\ge 2/3$. Since , it follows that there exists a program $\mathrm{\Pi }$ of length such that ${\mathrm{\Pi }}_r$ will output $x$ within $t_1(n)$ steps over at least $2/3$ fraction of random-tape $r$. Let $w$ denote $r{K}_{2/3}^{t_1}(x)$. If $𝒜$ finds a valid pre-image of $f$ on $w\Vert x\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3}$, $M(x)$ will outputs YES. We show that this will happen with high probability.

Since $\mathrm{\Pi }$ is a $r{K}_{2/3}^{t_1}$-witness of $x$ of length $w$, by the Chernoff bound, there exists a valid pre-image of $f$ on $w\Vert x\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3}$ for at least a $1-1/6$ fraction of $r_1,\mathrm{\dots },r_{n^3}$. Assume for contradiction that $𝒜$ fails to find a valid pre-image on $w\Vert x\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3}$ with probability $>1/3$. We will show that

which is a contradiction since $x$ is a YES instance of $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝗋𝖪}}^{t_1,t_2}$.

Consider any string ${\mathrm{\Pi }}^{\prime }$ of length $n$ such that its $w$-bit prefix is $\mathrm{\Pi }$. By taking a Union bound, it follows that $𝒜$ fails to invert $f$ on $f(w\Vert {\mathrm{\Pi }}^{\prime }\Vert r_1\Vert \mathrm{\dots }\Vert r_{n^3})$ with probability $\ge 1/3-1/6\ge 1/6$. Thus, the concatenation $w||{\mathrm{\Pi }}^{\prime }$ will be an YES-instance of $\mathrm{𝖥𝖺𝗂𝗅}$ (where $\mathrm{𝖥𝖺𝗂𝗅}$ is the promise problem we defined before). We next show that $\mathrm{𝖥𝖺𝗂𝗅}$ is $\frac{1}{n^{\prime 6}}$-sparse on input of length $n^{\prime }=n+\lceil \log (n)\rceil$. Suppose not. Then, it follows that the inverter $𝒜$ fails to invert $f$ with probability

which contradicts to the fact that $𝒜$ is a good inverter on $n$. Recall that $\mathrm{𝖣𝖾𝖼}$ is the decoding algorithm for the $(1/n^{\prime 6},n^{\prime }-3\log n^{\prime })$-language-compress scheme for $\mathrm{𝖥𝖺𝗂𝗅}$. Thus, there exists a string $z$ (i.e., the compression of $w||{\mathrm{\Pi }}^{\prime }$), $|z|\le n^{\prime }-3\log n^{\prime }\le n-2\log n$, such that $\mathrm{𝖣𝖾𝖼}(z)$ outputs $w||{\mathrm{\Pi }}^{\prime }$ with probability $2/3$. It follows (from our definition of algorithm $\mathrm{𝖱𝖾𝖼𝗈𝗇}$) that $\mathrm{𝖱𝖾𝖼𝗈𝗇}(z)$ outputs $x$ with probability $(2/3)\cdot (2/3)>1/3$. Note that $\mathrm{𝖱𝖾𝖼𝗈𝗇}(z)$ can be written as a program of length and it outputs $x$ with probability $>1/3$ within $t_2(n)$ steps (due to our choice of $t_2$), and therefore

which completes the proof. $\mathrm{⊲}$ $◀$

We proceed to extend this result to work also for $\mathrm{𝖻𝗈𝗎𝗇𝖽𝖺𝗋𝗒}\text{-}{\mathrm{𝖬𝖨𝖭𝖪}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ under standard derandomization assumptions.

The proof will proceed largely as the proof of Theorem 4.3, but with minor adjustments. In particular, we will go back to the original OWF construction of [33] (which is exactly the same as the one in Theorem 4.3 except that we no longer consider randomized programs $\mathrm{\Pi }$, so no longer including the random strings $r_1,\mathrm{\dots }$). Specifically, we define

where notations are as in Theorem 4.3.

With the new OWF construction, we will be needing to adapt the $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$ decider $M$ to deal with $K^{\mathrm{𝗉𝗈𝗅𝗒}}$. The new algorithm $M^{\prime }$ follows roughly $M$, except that (1) $M^{\prime }$ no longer needs to sample random strings $r_1,\mathrm{\dots }$; and (2) it replaces the threshold $n-3$ with $n-1$ (as required by the Theorem).

Finally, we need to show that Claim 4.4 and Claim 4.5 hold w.r.t. $K^{\mathrm{𝗉𝗈𝗅𝗒}}$, the new construction $f^{\prime }$, threshold $n-1$, and algorithm $M^{\prime }$. Claim 1 trivially holds since $M^{\prime }$ outputs YES only when it finds a $K^{t_1}$-witness of length . Note that $K^{t_1}\ge K^{t_2}$, so there will never be such a witness when $K^{t_2}\ge n-1$. Claim 2 is where we require some additional work. Note that to conclude Claim 2, we need to show that if $𝒜$ fails, then (as opposed to $r{K}^{t_2}$). Recall that in Claim 2, it is shown that the string $x$ can be generated w.p $2/3$ by a randomized decoding algorithm $\mathrm{𝖣𝖾𝖼}(z)$ on input a string $z$ of length $n-2\log n$. So to demonstrate the above claim, we just need to show how to derandomize $\mathrm{𝖣𝖾𝖼}$, which can be done using standard techniques. In more detail, let $C_{x,z}$ denote the circuit that receives a random-tape for $\mathrm{𝖣𝖾𝖼}$ as input, and outputs 1 if the random-tape leads $\mathrm{𝖣𝖾𝖼}(z)$ to output $x$. By [28], under the assumption of the theorem, we have that there exists a (complexity-theoretic) PRG $G$ with seed length $O(\log n)$ that fools $C_{x,z}$. Thus, $\mathrm{𝖣𝖾𝖼}$ can be derandomized by emulating $\mathrm{𝖣𝖾𝖼}$ on all (pseudo) random-tapes generated by running $G$ on all possible seeds, and outputting the string that appears the most often. $◀$

The proof for this theorem closely follows from the proofs in [39], in which they show that OWFs imply the boundary hardness of the same problem but with respect to another complexity measure ($p{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$). Their proof proceeds in two steps: First, they show that OWFs implies the existence of a so-called conditionally-secure entropy-preserving pseudorandom generator [33] (Cond-EP PRG); second, they show that a Cond-EP PRG (with certain parameters) implies the hardness of the boundary $p{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$ problem (in [39, Lemma 6.3]).

In order to prove the above theorem, the first step follows from the same proof. The following two claims are needed in the proof for the second step: (1) the output of Cond-EP PRG has “small” $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$-complexity (which follows from the fact that the output of Cond-EP PRG can be generated using a small program (without using the random tape)) and (2) for any string $x$ and runtime bound $t$, $p{K}^t(x)\le r{K}^t(x)$ (c.f., [8, Proposition 19]). Thus, the second step follows from the proof of [39, Lemma 6.3] with $p{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$ replaced by $r{K}^{\mathrm{𝗉𝗈𝗅𝗒}}$. $◀$