Challenging problems aren’t typically welcomed, but for cryptographers, they’re essential. These tough mathematical issues form the backbone of modern encryption; finding efficient solutions could compromise various cryptographic methods.
Years ago, researchers unveiled a groundbreaking encryption technique based on unusual features of quantum physics. Unlike previous quantum encryption methods designed for specific tasks, this new method covers a broader spectrum of applications and remains viable even if conventional cryptographic problems become solvable.
However, this innovative approach was based on unrealistic premises. As Fermi Ma, a cryptography expert at the Simons Institute, stated, it served more as “a proof of concept” rather than a reflection of reality.
Building the Foundation
Modern cryptography can be visualized as a tower with three key components. The foundational base consists of complex mathematical problems, the tower represents specific cryptographic protocols for secure messaging and document signing, and between them lies a foundation of one-way functions, which create an inherent asymmetry in encryption.
In the 1980s, it was established that cryptography relying on one-way functions could secure numerous tasks. Yet, the robustness of this foundation remains uncertain. The underlying NP problems are easy to verify but challenging to solve. If someone discovers a way to solve these NP problems efficiently, the entire cryptographic structure could collapse.
A New Quantum Path
To construct a cryptographic structure on harder problems, cryptographers initially believed they needed a new foundation without relying on one-way functions. This changed when researchers realized that quantum physics might offer a solution. A 2021 paper by graduate student William Kretschmer introduced a unique problem related to quantum systems. Subsequent research demonstrated that this problem could replace one-way functions and support a new range of cryptographic protocols without depending on NP problems.
In the autumn of 2022, cryptographer Dakshita Khurana and her student Kabir Tomer embarked on developing a new cryptographic tower using quantum elements instead of classical one-way functions. Their primary focus was creating a quantum version known as a one-way state generator that maintained the essential properties of traditional one-way functions.
A Breakthrough and Future Directions
After months of challenges, Khurana and Tomer achieved a breakthrough by defining a mathematical building block that linked their quantum foundation to practical cryptographic applications. They introduced “one-way puzzles,” which, despite being cumbersome, could still facilitate various cryptographic protocols, a surprising finding in the field.
As of November 2023, Khurana and Tomer’s progress led them to consider directly connecting one-way puzzles to robust mathematical problems rather than using a quantum foundation. They focused on the matrix permanent problem, known for its computational difficulty and intriguing properties, believing it could serve as an excellent basis for cryptography.
Their advancements provide a theoretical framework that could establish quantum cryptography on stronger grounds than classical methods. Despite recent progress in quantum computing, practical applications of Khurana and Tomer’s approach remain distant, as the technology is still evolving.
