FORT MEADE, Md. — Today, the National Security Agency announced the winning paper in the 9th annual “Best Cybersecurity Research Paper Competition.” Established in 2013, the competition encourages the development of scientific foundations in cybersecurity and supports cybersecurity improvements within devices, computers, and systems through rigorous research, solid scientific methodology, documentation and publishing.
This year’s winning paper was chosen by the Chief of NSA’s Laboratory for Advanced Cybersecurity Research. The decision was informed by reviews from 10 international cybersecurity distinguished experts who independently reviewed the best papers among 34 nominations.
This year’s winning paper advances a theorem that relates the existence of one-way functions (OWF) by relating them to the problem of computing “Time-bound Kolmogorov complexity, which is a way to measure the complexity of a string of text. Written by Yanyi Liu from Cornell University and Rafael Pass from Cornell Tech, the paper titled “On One-way Functions and Kolmogorov Complexity” was published at the 2020 IEEE Symposium on Foundations of Computer Science.
One-way functions 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, authentic 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.
Receiving honorable mention was the paper “Retrofitting Fine Grain Isolation in the Firefox Renderer” written by Shravan Narayan, Craig Disselhoen, Tal Garfinkel, Nathan Froyd, Sorin Lerner Hovav Shacham and Deian Stefan. This paper was originally published at the USENIX Security Conference 2020 and provides a security solution for use in the Firefox web browser while also demonstrating that that technology can be utilized for other situations. The solution, RLBox, is a culmination of many advances that enable software to securely use software components, such as libraries, which have not been verified as trustworthy. RLBox has been incorporated into Firefox 95.
NSA congratulates the winners, and recently opened the nomination process for the 10th Annual Best Scientific Cybersecurity Paper Competition on 15 January 2022. NSA welcomes nominations of papers published during 2021 in peer-reviewed journals, magazines, or technical conferences that show an outstanding contribution to cybersecurity science. The nomination period closes on 15 April 2022.
Visit the Best Scientific Cybersecurity Paper webpage for more information on the paper competition and to nominate a paper for the 10th completion.