Cryptography in the Face of Quantum Computing

Quantum computing is slowly becoming a reality. When you consider the processing efficiency of a quantum computer, you will begin to see its impact on cybersecurity. For example, IBM postulated that if you wanted to find one item in a list of one trillion, and each item took one microsecond to check, it would take a classical computer about one week to find the item and a quantum computer about one second. Such speeds would certainly have impacts in the areas of random number generation fundamental to cryptography, but they could also have controversial applications, such as breaking public-key cryptography.

Challenges

Right now, qubits (a unit of information in quantum computing) are inherently unstable and information can degrade in microseconds and the higher the number of qubits, the higher the noise, requiring complex error correction approaches. If you could generate around 4,000 error free qubits, it would take hours, if not minutes, to defeat public-key cryptography. To get those 4,000 clean qubits would require around one million of today's nosier qubits. As of November 2022, IBM announced a new 433 qubit 'Osprey' processor and has a roadmap to 4000+ qubits by 2025. Both IBM and Google are aiming even higher, at one million qubits by the end of the decade.

IBM stated, We think that quantum computing will be the next step in computation, augmenting classical computing resources so that we can solve difficult and complex problems. While we're still at the stage of building and exploring the possibilities of quantum technology, we also understand that today's two most widely used current encryption schemes wouldn't be secure against a fault tolerant, universal quantum computer. This puts today's sensitive information at peril, as attackers could harvest present-day data for later decryption. We think this is an important lesson: even if we find a post-quantum cryptographic algorithm for future use, the currently encrypted data worldwide remain susceptible to unauthorized decryption using quantum computing. We will need to explore other strategies to maintain confidentiality of that data in a post-quantum world.

Advances in Quantum Cryptography

In 2016 participants from all over the world submitted 69 cryptographic schemes for potential standardization. NIST later whittled down the list of candidates over three stages, eventually shortlisting seven finalists for for public key encryption and three for digital signatures. According to a NIST announcement in July 2022, "After careful consideration during the third round of the NIST PQC Standardization Process, NIST has identified four candidate algorithms for standardization. NIST will recommend two primary algorithms to be implemented for most use cases: CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures). In addition, the signature schemes FALCON and SPHINCS+ will also be standardized."

NIST goes on to state, "CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures) were both selected for their strong security and excellent performance, and NIST expects them to work well in most applications. FALCON will also be standardized by NIST since there may be use cases for which CRYSTALS-Dilithium signatures are too large. SPHINCS+ will also be standardized to avoid relying only on the security of lattices for signatures."

There is a supposed spanner in the works though. There have been claims that the CRYSTALS-KYBER has been broken using side-channel techniques and recursive AI analysis. Recall that side-channel attacks exploit measurable information obtained from a device running the target implementation via channels such as timing or power consumption. The researchers claim that by measuring these side channel data points and using deep learning AI techniques on these signals, they were able to obtain cleartext data. This is a good example of a side-channel attack but note that this does not attack or bypass that cryptographic algorithm, which remains intact. To us, this research highlights the need for well-designed, protected implementations where both production of side-channel data and access to remaining side-channel data is minimized.

Conclusion

So, what are the overall takeaways? While quantum computing may need some further development waiting for it to be put on your radar is a mistake. NIST has been looking at the post-quantum world for years now, and they have made a start, but there is going to be a lot of noise around what will and won't hold up and when you will need to employ new encryption methodologies. The key is to keep aware and up to date now and not wait until it's too late because you need to account for technological leaps.

For more information contact the VikingCloud team.

Sources

https://research.ibm.com/blog/nist-quantum-safe-protocols

https://www.securityweek.com/ai-helps-crack-a-nist-recommended-post-quantum-encryption-algorithm/

https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4

https://www.insidequantumtechnology.com/news-archive/moody-researchers-didnt-break-crystals-kyber-algorithm-standards-course-unchanged/

https://blog.cloudflare.com/kyber-isnt-broken/