Quantum-Safe Cryptography: what, why, and for whom?

Nowadays, we rely more and more on cryptography, from common email to government service, from online shopping to operation of power plant, car key, medical record, military operation, the list goes on. Most of these cryptosystems based their security on a ‘presumably’ hard-to-solve mathematical problem. One of the widely used encryption algorithm is the RSA protocol [1], which based the security on the factorization of large number;. The idea is that it is easy to multiply two large primed number together, but it is hard (for today’s computer with the best known algorithm) to find those two numbers when looking at the multiplication result only.

The security based on such assumptions will fail if the encryption can be broken faster via (1) a better understanding of mathematics that raise a better algorithm, or (2) a development of new technology that provide new tools to solve the problem The latter case has been mathematically-provenshown by Peter Shor that a scalable quantum computer will crack the factorization problem in a faster scale than today’s computing assumption [2].

Quantum-Safe Cryptography

Quantum-safe Cryptography is a collective term for studies of cryptographic tools that is safe against quantum computer and quantum algorithm. This field of study consists of two branches:

– Post-Quantum Cryptography: The name means (classical) cryptography after quantum computer. PQC focuses on finding new mathematical problems that are also hard-to-solve for quantum computer. This approach is implementable with existing infrastructure. However, the security assumption is only suit for a short-term security. The possibility of emerging better (quantum) algorithm is a risk to consider.

– Quantum Cryptography: The name means cryptography based on quantum mechanics. This field focuses on cryptography with provable security based on physical properties and rules of quantum mechanics. This approach promises information theoretic secure, but requires upgrading and retooling existing infrastructures. One of the most active topics in this field and quantum technology research in general is Quantum Key Distribution, which tackle the problem of generating and distributing symmetric secret keys.

Over the years, many protocols and proving techniques havehas been developed. We will explore variations of protocols, security analysis, and implementations of quantum-safe cryptosystems in our upcoming articles

Why now, quantum computer is not here yet?

One of the frequently received questions about this technology is its urgency. In cryptography, we need to consider security of the encrypted message, not only at the time of the encryption, but also consider probability of message being cracked before it is expired. We need to have a cryptographic tools that is secured against foreseeable threat. To elaborate this point, Prof. Michele Mosca, a co-founder of Institute for Quantum Computing provided a simple equation:

Let X be the time we need to develop and retool our cryptographic infrastructures, Y be the time we need for the encrypted data to be secure, Z be the time until we build a large-scale quantum computer,

if X+Y > Z, we might be too late.

Based on information in other articles in this website (which is highly recommended for all reader to read), we might need to act now.

State-of-the-art

Our understanding of his technology has been growing rapidly each passing year. The following are some notable recent discovery and activities in this field.National Institute of Standard and Technology (NIST) has announced their requirement to update all cryptographic systems to quantum-safe level. Selection of candidates for PQC protocol to be implemented is in progress [4].Quantum cryptography links and networks are being deployed and demonstrated in many countries around the world. One of the most famous demonstrations of quantum communication is the intercontinental secure communication between China and Austria using keys from QKD satellite [5].In 2016, researchers in Vienna demonstrated loophole-free Bell inequality test [6], which would open the path to device-independent QKD; a QKD system that is secure even if the device is fully controlled by the adversary.Method of testing and certifying the physical implementation of Quantum cryptography is being developed. This is done in order to guarantee the security level promised in theory.On the industry front, there are many companies developing and commercializing quantum cryptosystems both for quantum cryptography and for post-quantum cryptography.There are many research groups and institutes in many other countries around the world that contributing their effort on this development. Yet, many questions are left unanswered, many problems are still waiting for a solution. As the interesting in this field grows, the collaboration at an international level is wide open.

International activities

In the national and international level, many countries have been committing their resources to develop new cryptographic tools for quantum-safe cryptography. Canada has been promoting this field of study since early 2000 [7]. China has been developing satellite QKD systems for space-based and backbone-link for land-based communication [8]. USA is known for major support on post-quantum cryptography. EU is putting quantum-safe crypto as one of the major topics in their flagship project [9]. The quantum key distribution industry specification group (QKD-ISG) [10], which is part of the European Telecommunications Standards Institute (ETSI) has also been working on standardization of quantum cryptosystems and quantum network. As important as developing the device, promoting awareness and raising understanding on information security to their people is one of the activities many leading countries concern.

Reference

[1] R. L. Rivest, A. Shamir, and L. Adleman, Commun. ACM 21, 120 (1978).
[2] P. W. Shor, SIAM J. Comput. 26, 1484 (1997).
[3] https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum -world/documents/presentations/session8-mosca-michele.pdf
[4] https://www.nist.gov/news-events/news/2017/12/candidate-quantum-resistant-cryptographic- algorithms-publicly-available
[5] https://phys.org/news/2018-01-real-world-intercontinental-quantum-enabled-micius.html
[6] Marissa Giustina, et.al., Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons , Phys. Rev. Lett. 115, 250401
[7] https://www.investinontario.com/spotlights/creating-quantum-valley-8-quantum- leaders-watch
[8] Sheng-Kai Liao et al., Satellite-Relayed Intercontinental Quantum Network, Phys. Rev. Lett. 120, 030501
[9] ec.europa.eu/newsroom/document.cfm?doc_id=46979
[10] https://www.etsi.org/technologies-clusters/technologies/quantum-key-distribution