Cryptography from Unstructured Hardness

Introduction

Cryptography and its basic tasks such as encryption, authentication, and key exchange are essential for ensuring privacy and security on the Internet. The question of whether unbreakable encryption methods exist has fascinated mathematicians and cryptographers for thousands of years and is closely related to the famous NP vs. P problem. This question is still wide open, and consequently, Internet security today relies on cryptographic constructions based on the conjectured hardness of some computational problems (such as the factoring problem, the discrete logarithms problem, or various noisy linear algebra problems).

Vulnerabilities in Current Cryptographic Methods

However, these conjectured hard problems all contain significant (e.g., algebraic) structure that may make them vulnerable to attacks. Furthermore, for tasks such as key exchange and public-key encryption, only a handful of candidate hard problems are known on which these tasks can be based. As a result, some unexpected algorithmic developments for structured problems could upend the whole infrastructure we rely on for communicating and transacting on the Internet.

Proposed Approach

In this project, we propose to develop an alternative approach: a foundation for provably-secure Cryptography from unstructured hardness assumptions.

Leveraging Kolmogorov Complexity

Towards resolving this long-standing challenge, we will leverage our recently-discovered connection between Cryptography and the seemingly unrelated area of Kolmogorov Complexity. Specifically, we will develop new hardness assumptions rooted in Kolmogorov Complexity on which the cryptographic tasks can be based, including:

1. Private-key encryption
2. Key exchange
3. Public-key encryption

Conclusion

Critically, these assumptions will lack algebraic and other computational structure that may make them vulnerable to attacks. Overall, KolmoCrypt will provide a new theoretical foundation for the hardness assumptions on which Cryptography is based, and ultimately, a more secure foundation for the Internet (and beyond).