Rafael Pass and Yanyi Liu Win NSA Best Cybersecurity Research Paper Competition

Rafael Pass, professor of Computer Science at Cornell Tech, and CS doctoral candidate and coauthor, Yanyi Liu, recently won the National Security Agency's Best Cybersecurity Research Paper competition for their paper “On One-way Functions and Kolmogorov Complexity.” The award is presented annually to researchers whose papers show “an outstanding contribution to cybersecurity science,” with the goal of encouraging the development of the scientific foundations of cybersecurity.

The paper addresses an important question in the world of cryptography: Does an unbreakable code exist? The paper advances a theorem that relates the existence of one-way functions (OWF) to the problem of computing “Time-bounded Kolmogorov Complexity”, which is a way to measure the complexity of a string of text.

One-way functions (OWFs) are a key underpinning in many modern cryptography systems, and were first proposed in 1976 by Whitfield Diffie and Martin Hellman. These functions can be efficiently computed but are difficult to reverse, as determining the input based on the output is computationally expensive. OWFs are vital components of modern symmetric encryptions, digital signatures, authentication schemes and more. Until now, it has been assumed that OWF functions exist even though research shows that they are both necessary and sufficient for much of the security provided by cryptography. The theorem in the winning paper shows that whether OWF exist can be distilled down to a single problem that dates back to the 1960s: whether we can efficiently compute time-bounded Kolmogorov complexity for random strings.

The paper was originally presented at the 2020 IEEE Symposium on Foundations of Computer Science (FOCS). More on the paper can be read here and on the NSA site.

See also coverage of another collaboration between Pass and doctoral candidate Liu, “On the Possibility of Basing Cryptography on EXP ≠ BPP,” which won a Best Paper award at CRYPTO ’21.

The research was funded in part by the National Science Foundation and the Air Force Office of Scientific Research, and was based on research funded by the Intelligence Advanced Research Projects Activity in the Office of the Director of National Intelligence.