Whether secure Cryptography exists is one of the most importantopen problems in Computer Science; consequently, cryptographic schemes today rely on unproven computational hardness assumptions. We will survey a recent thread of work showing equivalences betweenthe existence of some of the most basic cryptographic primitives, and the hardness of various computational problems related to the notion of time-bounded Kolmogorov Complexity (dating back to the 1960s). These results yield the first natural computational problemscharacterizing the feasibility of central primitives and protocols in Cryptography, as well as the first unstructured computational problems enabling public-key cryptography.