LAUSR

tence of cryptography’s most basic construct. Specifically, they constructively proved the existence of one-way functions is equivalent to the average-case hardness of computing time-bounded Kolmogorov complexity. Note that appropriately formalizing the task of computing time-bounded Kolmogorov complexity as a decisional problem positions it in the class NP. Thus, this result pins down a natural NP problem whose average-case hardness is equivalent to the existence of one-way functions. However, the task of computing time-bounded Kolmogorov complexity is not known to be complete for NP, and therefore this result falls short of characterizing the existence of one-way functions based on arbitrary average-case NP-hardness. In their second paper, the authors showed that Levin-Kolmogorov complexity does enable to reason about the possibility of basing the existence of one-way functions on general limitations of feasible computation. They proved that the question of whether one-way functions can be based on the assumption that BPP ≠ EXP is equivalent to a seemingly “minor” technical gap between two-sided error and errorless average-case hardness of computing Levin-Kolmogorov complexity. They also demonstrated that any reduction bridging this gap implies that P ≠ NP. Equipped with this fresh perspective, the cryptography community is looking forward to seeing the extent to which this work will lead to additional exciting insights. A quest for such understanding into the connections between cryptography and Kolmogorov complexity has fantastic potential in leading to fruitful cross-domain interactions and extending our ability to reason on the existence of cryptographic constructs well beyond one-way functions.