Toward Basing Cryptography on the Hardness of EXP

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: center dot MKtP is not an element of Heur(neg)BPP (i.e., MKtP is two-sided error mildly average-case hard) iff infinitely-often OWFs exist. center dot MKtP is not an element of Avg(neg)BPP (i.e., MKtP is errorless mildly average-case hard) iff EXP not equal BPP. Taken together, these results show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP not equal BPP is the seemingly "minor" technical gap between two-sided error and errorless average-case hardness of the MKtP problem.