Three Types of Randomness.
Raczkowski, Adam.
2009
- 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 ... read moreare 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
- ID:
- ww72bp31j
- Component ID:
- tufts:UA005.036.001.00001
- To Cite:
- TARC Citation Guide EndNote
- Usage:
- Detailed Rights
