The 4th ETSI/IQC Workshop on Quantum Safe Cryptography, Toronto

Sep. 19 - Sep. 21, 2016

During Sep. 19 - Sep. 21, the European Telecommunication Standards Institute (ETSI) in collaboration with the Institute for Quantum Computing (IQC) organized the 4th ETSI/IQC Workshop on Quantum-Safe Cryptography in Toronto. If quantum-safe cryptography doesn't ring a bell to you, let's first start with some basics about cryptography.

Cryptography 101

Symmetric cryptography

From ancient times, humankind wanted to be able to communicate securely. Ciphers were invented and subsequently broken. Even the famous Enigma machine, which was believed to be unbreakable, was cracked with the help of Alan Turing during the Second World War. This period of time marked the starting point of modern cryptography, of which Claude E. Shannon put the bases in his seminal paper A mathematical theory of cryptography.

Shannon proved rigorously that what's called the one-time pad or Vernam cipher is perfectly secure. Say we have two participants, Alice and Bob, and Alice wants to send to Bob the message "hello". If Alice and Bob happen to share in advance a random string of bits (in this case numbers from 0 to 26) of length at least as long as the message, then Alice can encode the message she wants to send to Bob via adding the random string of letters to the original message modulo 26 (i.e., letters wrap around 'z'), and Bob can decode by subtracting it from the cipher text.

For example, suppose Alice and Bob happen to share "1 2 3 4 5". The encoded text will be "i g o p t", as 'h' + 1 corresponds to 'i' in the alphabet, 'e' + 2 to 'g' and so on. Bob can then decode by performing the reverse operation. This scheme is unconditionally secure as long as the random string is not used more than once. The one-time pad is an example of what is called symmetric cryptography: both Alice and Bob are sharing the same key, in this case a string of random numbers.

The problem with the one-time pad is that it requires extremely long keys, as long as the message itself, so distributing the key becomes an issue in itself: it is a chicken and egg problem. In the 1970 Data Encryption Standard (DES) was invented by IBM and further modified by the National Security Agency (NSA), which requires much smaller keys of only 56 bits. In contrast to the one-time pad, DES is computationally secure, i.e., its security is based on the fact that the best known attack against it seems to be a brute force searching over a space of 2⁵⁶ possible keys (there are slightly more evolved attacks, but the security is not decreased by much).

If in the 1970s this number seemed huge, even for the most advanced computer of the time, after 1990 it became an issue: DES was subsequently broken by faster and faster computers. In the 2000s new symmetric ciphers were invented, the most famous one being the Advanced Encryption Standard (AES), which has a security of at least 128 bits (i.e., it will take a computer at least 21282¹²⁸ operation to break).

Public-key cryptography

However all of the symmetric ciphers above suffer from the same problem: secure key exchange. Remember that Alice and Bob must share a common key. How can they establish it if they cannot meet? The field of public-key cryptography (or asymmetric cryptography) deals with this problem.

It was first officially invented in 1977 (although the British intelligence agency Government Communications Headquarters (GCHQ) had an equivalent system back in 1973) by Ron Rivest, Adi Shamir, and Leonard Adleman and called the RSA scheme. In contrast to symmetric key cryptography, now Alice and Bob each have two keys: a private one and a public one. Alice encodes to Bob using Bob's public key, and Bob decrypts using his private key, and vice-versa.

The private and public key are in a direct relationship, however it is very hard to find the private key from the public key alone. In fact, the security and the key generation of RSA are based on the factoring problem: it is easy to multiply two large numbers together but given a large product it seems to be extremely hard to find its factors. Other public-key schemes based on the hardness of given mathematical problems were invented, such as the Diffie-Hellman (DH) key exchange based on computing discrete logarithms in large cyclic groups. Most of those schemes are currently in use millions if not billions of times a day in online commerce, banking, data security, etc.

The quantum catastrophe in public-key cryptography

All of the public-key schemes described above (except the one-time pad) are based on un-proven computational assumptions about the hardness of some mathematical problem. And now comes the "quantum catastrophe" in public key cryptography: in 1994 Peter Shor [Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2] realized that both RSA and DH can be broken in polynomial time (i.e., fast) by a quantum computer.

This result shook and changed the field of cryptography dramatically. If during the next 10 years or so the community was still somehow skeptical that a quantum computer will (if ever) be built, nowadays the skepticism is decreasing with a fast pace.

The ETSI/IQC workshop

In fact, one of the main goals of the ETSI/IQC workshop was to bring awareness about those issues and to make both the scientific, as well as the industry communities, realize that the time to act is now. There are solutions to the quantum catastrophe: those constitute what is often called post-quantum cryptography - cryptographic systems that are designed to be secure against a quantum computer attack. These solutions fall into two categories:

1. based on quantum cryptography, which offers information theoretically secure cryptography, that is cryptography that cannot be mathematically cryptanalyzed with any amount of computing power; and
2. conventional schemes also known as post-quantum cryptography (since they are designed to be secure in the era after full-scale quantum computers are available), that offer security based on computational difficulty of mathematical problems (e.g., problems based on lattices, error correcting codes, multi-variate functions, and super-singular elliptic curve isogenies) that are not believed to be solvable by a quantum computer.

All of those post-quantum schemes are currently under a great deal of scrutiny.

The interesting thing about the ETSI/IQC workshop was that everyone agreed: we need to act now. In fact, I learned there that some believe that the chance of having a quantum computer built by 2026 is 1/7, and the chance of having one by 2031 increases to a mind blowing 1/2.

Given that our cybersecurity is underpinned by cryptography, even 1/7 is too large a chance to ignore. So why do we need to act now if we believe we are 10 or more years away from doomsday?

As Professor Michele Mosca (Institute for Quantum Computing (IQC), University of Waterloo) simply put it [M. Mosca, "Setting the Scene for the ETSI Quantum-safe Cryptography Workshop", e-proceedings of 1st Quantum-Safe-Crypto Workshop, Sophia Antipolis, 26-27 September 2013], "if we denote by x the amount of time our data has to be secure, by ythe migration time to post-quantum solutions and by z the time to build a quantum computer, then if x+y>z, we have a serious problem, since information protected by quantum-vulnerable tools at the end of the next y years can be broken by quantum attacks in less than x years from then".

The workshop addressed all those issues, with discussions ranging from standardization, quantum tools, classical tools to panel discussions addressing the state of progress across the world and more technical talks regarding modern developments in the area.

There was also a full day dedicated to business and security executives (Sep. 19), in which one could hear about the business perspective on the issues. The workshop also accommodated a poster session. Some software demos implementing quantum-safe solutions were presented by evolutionQ Inc. Participants ranged from government employees to business executives to scientists to industry researchers.

Scott Jones (Communications Security Establishment (CSE), Canada) and Luis J. Romero (ETSI) opened the workshop, with Scott Jones asking the question: "If we don’t address the impending reality of quantum computing, how do we maintain trust and confidence in the cyber-world upon which so much of our economic prosperity depends?". He remarked that "People use the word threat when it comes to quantum and encryption, but the fact if that at some point in my lifetime, quantum computing will be a reality. The question isn’t if quantum will force us to change how we encrypt online information. It’s when," and concluded with, "But this isn’t a government problem. It’s something we’re all facing. [...] The next three days are important. The research we share, the partnerships we develop, and the ideas we generate here could one day successfully solve the quantum challenge."

During the panel talk "Tomorrow's Security Challenges And Quantum Readiness", Brian LaMacchia, the head of security and cryptography at Microsoft, mentioned 2030 as the year he assumes quantum computers will become a reality: "The people who try to build quantum computers, who sit on the floor upstairs from me, said 15 years last year... So I said, O.K., let’s work backwards from that. And I’m out of time."

Norbert Lütkenhaus (IQC, University of Waterloo) provided a Canadian perspective on quantum key distribution (QKD), while Vadim Makarov (IQC, University of Waterloo) discussed about challenges to physical security of today's quantum technologies and the importance of standards for QKD.

In another panel discussion dedicated to standards, "The Importance Of Standardization", Lily Chen (National Institute of Standards and Technology (NIST)), Luis Jorge Romero (ETSI) and Michel Girard (Standards Council, Government of Canada) addressed the issue of standardization across the Information and Communications Technology sector. The conclusion was that standardizing quantum-safe cryptographic schemes is a challenging task, but nevertheless of extreme importance.

As some potentially quantum-safe technologies are already being tested in products, Mosca asked the industry panel "Does this mean that we are done now?" The consensus was that we are not done at all and the message was very clear: there is no time left to wait! We need standards, we need testing, we need software, we need integration into existing and future products and systems, we need rigorous security analysis and we need to work on it now!