In the digital age, where every online interaction, from messaging to financial transactions, hinges on the assurance of security, the role of cryptography cannot be overstated. At the heart of this assurance lies the intricate dance between encryption algorithms and the underlying mathematical problems they rely on. But how does modern cryptography work, and how do we ensure its resilience in the face of ever-evolving threats?
Public-key cryptography, the cornerstone of modern secure communication, operates on the premise of leveraging hard mathematical problems to secure our data. Take, for instance, the widely-used RSA encryption, which relies on the presumed difficulty of factoring large integers. However, the efficacy of these schemes rests on the belief that these mathematical problems are indeed hard to solve. So, what if someone were to find an efficient algorithm to crack these problems tomorrow?
How does post-quantum cryptography work?
Enter the world of post-quantum cryptography (PQC), a realm where cryptographic schemes must be resistant against adversaries with quantum power. One of the most promising avenues in post-quantum cryptography revolves around lattice-based schemes. These schemes draw their strength from the complexity of problems rooted in lattice structures, offering a robust defense against quantum adversaries. Recent standardization efforts in lattice-based cryptography mark a significant stride towards fortifying our digital infrastructure against future threats.
What do we do when someone claims to have an efficient algorithm for a quantumly hard problem?
Yet, the journey towards post-quantum security is fraught with uncertainties. A recent preprint claiming an efficient quantum algorithm for lattice problems sent shockwaves through the cryptographic community. For weeks, experts painstakingly scrutinized the purported attack, grappling with the unsettling prospect of a paradigm shift in cryptographic landscape. However, a sigh of relief swept through the community as the flaw in the attack was unearthed, reaffirming the resilience of lattice-based cryptography, albeit momentarily.
But the quest for post-quantum security extends beyond lattice-based schemes. A diverse array of hard problems, from syndrome decoding to permuted kernel, stands as sentinels against quantum intrusion. Organizations like TII are at the forefront of this endeavor, spearheading the development and standardization of quantum-secure cryptographic schemes.
Diversity of post-quantum hard problems
Even if the attack on lattice-based schemes had turned out to be correct, post-quantum cryptography would still be up and running. There are a variety of hard problems believed to be quantumly hard:syndrome decoding problem, permuted kernel problem, minrank problem, to name a few. These problems provide an option for the applications to switch to using schemes based on another assumption in case some of these problems are solved using quantum (or even classical) computers in the future. Researchers at TII are actively involved in this process, HQC and BIKE coauthored by Slim Bettaieb, and Loïc Bidoux in collaboration with other experts are amongst the finalists in the quantum secure key encapsulation algorithm selection process. Also, TII cryptographers are involved in designing seven additional quantum secure signature scheme proposals, MIRA, RYDE, PERK, Biscuit, MiRitH, LESS, and SQIsign, which are being considered for standardization as well. On the cryptoanalysis side, TII researchers have also developed a tool to estimate the security level provided by the different problems mentioned above.
In the realm of cryptography, uncertainty is the only constant. Yet, it is this very uncertainty that propels us forward, driving innovation and resilience in the face of adversarial challenges. As we navigate the intricate landscape of modern cryptography, one thing remains clear: the pursuit of security is an ever-evolving journey, where every failed attempt serves as a stepping stone towards a more resilient future.