Three Types of Randomness.
- Three types of randomness are integral to the strength of public-key cryptography. With the techniques of Allender et al., we present an analysis of how the ability to quickly distinguish Kolmogorov randomness allows for a probabilistic attack on two of the conjectured hard problems underlying public-key cryptography: the discrete logarithm and factoring. Specifically, Kolmogorov random strings ar... read moree pertinent to inverting one-way functions and distinguishing pseudorandomness from true uniform randomness. This method provides a lens that more sharply categorizes the hardness of the discrete logarithm and factoring in the hierarchy of well-known complexity classes. An overview of public-key cryptosystems is presented alongside the traditional analysis of one-way functions and pseudorandom generators. Using this approach, we establish relationships between provably secure public-key cryptography, Kolmogorov complexity, and the essential cryptographic primitives and put forth conjectures of how these relationships may extend into methods for solving other types of problems.read less