A Duality Between One-Way Functions and Non-Robustness of Polynomial Time Dimension

One-way functions are fundamental to cryptography, as their existence is both necessary and sufficient for constructing essential cryptographic primitives such as pseudorandom generators, digital signatures, private key encryption, authentication schemes, and commitment schemes. Polynomial-time dimension provides a way to quantify the density of information in infinite sequences using polynomial-time betting algorithms known as s-gales. An alternative measure of polynomial-time information density is the rate of polynomial-time bounded Kolmogorov complexity. Hitchcock and Vinodchandran (CCC 2004) established that polynomial-time dimension is always at least the rate of polynomial-time Kolmogorov complexity.

In this talk, we explore a duality between the existence of one-way functions and the non-robustness of polynomial-time dimension. We demonstrate that these two formulations of polynomial-time dimension define distinct notions of information density if and only if one-way functions exist. Using our main results, we resolve a longstanding open problem posed by Hitchcock and Vinodchandran (CCC 2004) and Stull, assuming the existence of one-way functions.