From Quantum Landscape to Post-Quantum Cryptography

Relation between quantum computers and cryptography

Let’s talk about how quantum computers relate to keeping our online information safe, especially in terms of cryptography.

When Richard Feynman first suggested quantum computers, they seemed like something out of a sci-fi movie – hard to build but fascinating. Researchers thought about how to make these computers and how they could be used.

In 1994, a person named Peter Shor figured out a way to use a quantum computer to break the security of two important cryptographic algorithms: RSA and Diffie Hellman. These algorithms are like the guardians of our online secrets, helping with things like secure communication and digital signatures. Shor’s discovery was a big deal because it meant that once we have a big, working quantum computer, our current cryptographic algorithms might not be so secure anymore.

Now, there are quantum computers today that you can rent for certain tasks, but they’re still too small to be a real threat to our existing security methods.So, since our current protective algorithms might not be safe with big quantum computers around, we need new ones. That’s where post-quantum cryptography comes in. These new algorithms work on regular computers and are based on problems that are tough for both regular and quantum computers to solve. It’s like creating a new set of locks that are tricky for both old-school and super-advanced computers to pick.

Why should regular people care about something called post-quantum cryptography?

Well, cryptography is everywhere in our modern lives. For example, when you type in your credit card number online, there’s a protection system in place. It uses digital signatures to ensure you send your credit card info to the right place and public key exchange to agree on secret codes for secure communication.

Now, here’s the thing: if someone builds a super-advanced quantum computer, the usual security we rely on for online transactions might not work anymore. That means the guarantees we usually have when we see that little padlock symbol in our web browser (indicating a secure connection) might not be so reliable.

Also, think about your computer password. Some systems use similar security methods to help you recover your password if you forget it. If quantum computers become a big deal, even these recovery systems might not be as safe as they should be.

So, for the everyday person, it’s important to be aware of what systems you use that might be at risk. This is especially crucial for businesses and their tech systems, so they need to pay extra attention to keeping things secure.

Can Quantum Computers Affect Your Business?

The Mosca’s Algorithm generally answers this question.

Mosca’s Theorem provides a framework for understanding the urgency based on various factors. According to the theorem, if the combined duration of migration to a new algorithm (y) and the required period of keeping a secret (x) exceeds the time until a quantum computer capable of breaking current public key algorithms is available (z), data compromise becomes a risk before its intended usefulness expires.

The duration for which the secret needs to be kept (x) is generally determined by the application, such as a few years for online credit card transactions or potentially decades for medical data. The challenge arises from uncertainties in these values. Additionally, some entities now record TLS sessions, potentially decrypting the data in the future, adding another layer of complexity to assessing the time value of secrecy. The time to deploy the new algorithms (y) can be protracted, involving standards development and implementation, and is largely under organizational control.

The most uncertain variable in this equation is the time until quantum computers capable of breaking current algorithms emerge (z). Michael Mosca’s estimates in 2015 suggested a 1/7 chance of 2048-bit RSA vulnerability by 2026, with a 50% chance by 2031. Subsequent updates in 2017 indicated a 1/6 chance of compromise by 2027. The rapid progress in quantum computing research by companies like IBM and Google further complicates the timeline.

Public key infrastructure (PKI) is the foundation of secure communication over the internet and cloud services. Public key encryption, a widely used technique within PKI, safeguards data and traffic. However, the emergence of quantum computers poses a significant threat, as they have the potential to easily crack public key encryption without needing a decryption key.

A recent study by Deloitte predicted that 25% of Fortune 500 companies could gain a competitive advantage through quantum computing within three years. This highlights the need for organizations to be proactive and consider PQC solutions to mitigate potential risks in the future.

Why haven’t post-quantum algorithms been implemented yet?

Although the cryptographic community has been aware of the impending challenges, the introduction of new algorithms to replace current key exchange and signature methods faces significant obstacles. While there are promising alternatives, most well-studied algorithms encounter issues related to either their key size or the size of their encrypted data/signatures, often reaching megabit proportions.

Over the past decade, extensive research has focused on exploring algorithms with more manageable key and data sizes. In 2016, the National Institute of Standards and Technology (NIST) initiated the Post-Quantum Cryptography Standardization process, receiving 82 submissions, with 69 deemed complete by the end of 2017. The evaluation in 2018 led to the selection of 30 algorithms for further refinement and assessment throughout 2019.

During this period, a significant number of the original 69 algorithms were compromised, resulting in 26 progressing to the second round. By 2020, NIST narrowed down the selection to seven finalists and eight alternates. Notably, three out of these 15 algorithms have since been broken. The cautious pace of progress underscores the prudence of careful evaluation.

Conclusion

In fortifying against quantum threats, the quest for post-quantum cryptography is challenging. Balancing swift implementation with rigorous algorithm scrutiny is crucial. A decade of NIST-led research emphasizes commitment to finding alternatives. Challenges in key and data sizes, coupled with algorithm uncertainties, demand a measured approach. Cybersecurity’s evolving landscape underscores the need for awareness and adaptability. The journey to post-quantum cryptography signifies a collective effort to secure our digital future.