Post-Quantum Cryptography Series

12 minute(s) read

As a community of cryptography experts and researchers in Worldline and as part and contributors of the NIST post-quantum cryptography standardization competition, we would be happy to share with you our experience, expertise and thoughts in cryptography and post-quantum cryptography (PQC) in an accessible way. Our intention is to publish a series of articles on various topics related to cryptography & PQC and to get you in touch with fresh news (concepts, key principles, standards, challenges, solutions.)

This series will be progressive, diverse and evolving. It will provide basic concepts to help you understand the key principles of cryptography, illustrating concrete use cases to make you aware of issues, and informing you about hot topics and fresh news to keep you up to date! “Make it simple and accessible, attractive and informative,” that’s how we’ll try to implement it. Each publication will offer a challenge in cryptography to let readers take part in the initiative (see “Challenge” section)

We hope this series of publications will help you to become more familiar and curious about this fantastic journey and we are eager to hear your feedback – Is there a specific subject you’d like to know more about? Do you have remarks on content? Do you have ideas on how we can improve? We believe this initiative is a great opportunity to prepare ourselves for the biggest cryptographic challenge to come !

Now, let’s enter this amazing world by introducing the context and by explaining some concepts…

Why should we care?

Let’s discuss few points to help us realize why this topic is so important, and why we should care now. For illustration, we will focus on the payment industry and will pay attention to the risk it implies, especially in a perspective of market and business domains.

Quantum machines are coming

It is widely known that a number of large organizations are in the race to build quantum computers; notably with Google claiming they will have a ‘useful’ quantum machine by the end of the decade. Through this series of news letters we aim to explain what are the implications of such a development, and why and how we are currently preparing for the inevitability.

Security is being threatened.

By 2029 it’s claimed we’ll see quantum machines with AI capabilities that will accelerate finding solutions to some of the world’s most pressing problems. On the one hand, this is great - of course we all want to save the world - but on the other hand, this is quite threatening. Given the openness of the internet and systems we use today, we rely heavily on cryptography to maintain availability, confidentiality, and integrity of our data. Yet, the foundations of many cryptographic systems we use will not withstand attacks from quantum machines. While Google claims it will have a ‘useful’ machine within the decade, the threat to security is a little more pressing. When we hear news about developments in quantum computing, we often think of it as a step towards a universal machine capable of doing all that we do today, and more, but, in order to break a cryptosystem, it’s enough for there to exist one single machine capable of performing a few specific computations. As such, we need to ensure that our systems are post-quantum secure, before the realization of even one such machine.

But also, we can gain extra functionality.

It’s true that security threats posed by quantum machines are grave, and should be treated as so, but beyond that, in the process of developing cryptographic solutions that withstand new attacks, we leverage new mathematical structures which extend our playground of tools and tricks. This opens doors to gain extra functionality and allows us to be more innovative in building solutions, not only with heightened security, but also with exciting and more efficient services.

Implications for the payment industry

As with most digital services, a large portion of the payment processing stack relies on cryptography that can be subject to quantum attacks. In addition, as the payment industry is one of the most heavily regulated there is an increasingly urgent need to agree on standards for post-quantum cryptography. Fortunately, NIST is in the final stages of choosing a standard suite of cryptographic protocols aiming to achieve post-quantum security. PCIDSS requirements are built on top of the recommended NIST standards. Thus, Worldline is well on the way to understanding what is needed.

What do we mean by quantum, and what do we mean post-quantum?

When people mention quantum cryptography, they are often referring to quantum key distribution. This implies that all machines in the scenario are quantum enabled. When we refer to post-quantum cryptography, we talk about cryptographic protocols that can be run on a classical machine, which, at some point in time, may face (one or more) quantum enabled adversaries. The post-quantum world is much more realistic, and means that we can already start to protect our systems against quantum attacks that may occur in future.

These ideas are nicely illustrated by this meme flowchart that appeared on Léo Ducas’s tweet.

PQC distribution

What’s the Danger?

The purpose of encrypting data is to scramble data in a manner such that someone with access to the scrambled data can’t glean any information from the encrypted data. Only people with the key can un-scramble the data are able to read it. Most encryption algorithms rely on a mathematical function that is easy to compute but incredibly difficult to reverse. Modern cryptography is concerned by more than just encryption and decryption, there are also signatures. A digital signature can be used to verify the authenticity of a document or website with out having to know a secret key. Signatures are used, for example, every time you connect to a web site. Depending on the type of data, it needs to stay protected for different time periods. Your connection to a web site might need to be safe only for today, but your card number needs to remain secure until your expiration date of your card typically 3 years.

In the image you can see Worldline’s Expert Community logo. The top portion shows the image in the clear, the middle portion shows the logo encrypted in ECB mode, while the bottom portion shows the logo encrypted in CBC mode. In the middle portion, it’s clear to see that the image data has been scrambled, but because of the encryption method used, it’s still possible to determine much of the information from the plaintext logo. In the bottom portion, the encryption method fully scrambles all data and leaves no visible similarity to the original logo. This is just one example to highlight that some encryption methods are fundamentally weaker than others. The threat posed by quantum adversaries is more grave for certain types of cryptography which we outline below.

Encryption

Generally speaking there are two types of cryptography: Asymmetric and Symmetric. Symmetric cryptography is used for the encryption and decryption of information sent between two parties who share the same key.

Asymmetric cryptography is built on two sets of keys: public keys and private keys. Due to the nature of public keys, asymmetric cryptography, albeit more user friendly, is generally considered weaker than symmetric cryptography. Cryptographers use specific ‘hard problems’ as the basis for cryptographic security.

For example, the security of one asymmetric cryptographic algorithm, RSA is based on the ‘hardness’ of factoring the product of multiplying two large prime numbers. As an example, take two random primes numbers and multiply them together. let’s say the product of these two primes is 2491. Now try and find these two primes.

2491 = ? * ?

This is hard to do.

Now try and do this in reverse take two random prime numbers and multiply them together.

47 * 53 = ?

This is easy to do.

Cryptography is used in almost all communications through out the web, even your communication with this website. If you want to see the actual RSA key being used in this communication you can find it under the padlock in the address bar.

  1. Click the padlock,
  2. Go to Details,
  3. Scroll down until you see the Public key field and there is your key! (Our keys might not be the same depending on when you are reading this)

Worldline blog certificat popup

Worldline blog certificat general information

Worldline blog certificat detailed information

The current best factoring algorithm or “lockpick” is called General Number Field Sieve (GNFS). The amount of work is takes a computer to compute a factorization grows very quickly with the number of digits if the number you are trying to factor. This means that you can make the security as strong as you want by choosing as many number of digits as you want. At the time of this writing, nobody has broken an RSA key of more than 900 bits (and published the result). Since it is hard to predict the future, it is not easy to predict what size of key can be broken in the future.

The following graph shows the factorization of the so called “RSA challenge numbers”, that were published by RSA laboratories.

Factored RSA challenge numbers by date.png

Results of the RSA Factoring Challenge put forward by RSA Laboratories on March 18, 1991 (https://en.wikipedia.org/wiki/RSA_Factoring_Challenge)

You can see that the graph is not smooth; this is because different algorithms are used, but also because some numbers have been factored using very many computers (over a 1000 in some cases). This might have been because there was a prize attached to some numbers; for example, the 768 bit factorization had a prize on it of $50 000, but the factorization was after the deadline.

As seen by the graph, encrypting data is not a fool proof way that no one without the key can access the data. Just like any normal lock, it can be picked. It’s a way of making it harder for someone to access the data, the intent is to make it so hard that few feel it’s worth trying.

There is a new “lockpick” on the horizon developed by Peter Shor, simply called Shor’s Algorithm. This Algorithm is meant to be implemented on Quantum computers. Quantum computers are good at executing many computations in parallel, if there is only one result. How convenient that’s exactly what’s needed to do prime factorization. The thing we tried earlier that was hard and took many guesses. A quantum computer can make these many guesses in parallel and come to an answer.

Shor’s algorithm converts the factoring problem to finding the length of a cycle. Finding cycles is done using a Fourier transform. As is happens, doing Fourier transforms is quite easy on a quantum computer. After the cycle length is found, the calculation of the factors can be done on a classical computer. There is a great animation of how Shor’s algorithm works on the minutephysics youtube page.

What is Post Quantum Cryptography (PQC)?

In response to the threat of quantum computers on cryptography, the international scientific community around cryptography has been exploring new class of algorithms that are not vulnerable to the types of attacks that may arise with quantum computers, and the term post-quantum cryptography was born.

One can define post-quantum cryptography as a branch of cryptography that studies and designs public key cryptographic primitives (public key encryption, digital signatures, key encapsulation mechanisms, etc) that are secure against attacks using both classical and quantum computers.

In particular, the goal of post-quantum cryptography is to provide quantum-safe alternatives to traditional public key algorithms like RSA, ECDSA, and Diffie-Hellman whose security relies on Factoring and Discrete Logarithm problems which are known to be vulnerable to quantum computers.

Such post-quantum (or quantum-resistant) primitives are based on families of mathematical hard problems which are believed to be resistant to attacks from quantum algorithms. These families include problems based on advanced mathematical structures (such as lattices, error correcting codes, multivariate polynomials), as well as cryptographic hash functions and others.

NIST standardization competition

To prepare the transition from classical to quantum-resistant cryptography, NIST (National Institute of Standards and Technology) has decided to standardize new cryptographic algorithms that are secure against attacks that use both classical and quantum computers. For this purpose, NIST has started a competition in 2017 to select secure post-quantum algorithms and the new standards are expected to be released between 2022 and 2025.

The cryptography team at Worldline Labs has been involved in the competition in collaboration with the CNRS XLIM laboratory and four schemes have been proposed, two of them (BIKE and HQC) have been selected for the third round.

PQC building blocks

There are six main categories of post-quantum cryptography.

In the next newsletters we will dive deeper into details of the aforementioned categories and focus on their building blocks, security and performance.

History / Challenge

One of the first historical types of cryptography used is called the Caesar Cipher. It works by substituting letters in the alphabet by another letter.

Using a Caesar cipher can be though of very similarly to how we use modern ciphers. Given a message, we can ‘encrypt’ the text with a key to obtain a ciphertext. Only those holding the key should be able to ‘decrypt’ the ciphertext to retrieve the original message. In designing his cipher, Caesar chose his key as a shift in the letters of the alphabet. For example, if he chose the key = 3, a left shift would send a → d,b → e,c → f, and so on. Let’s illustrate the full shifted alphabet in the table below.

Key = Left shift 3 steps

abcdefghijklmnopqrstuvwxyz!
defghijklmnopqrstuvwxyz!abc

Message = Welcome to the Engineering Blog

Ciphertext = Zhofrph wr wkh Hqjlqhhulqj Eorj

The Caesar cipher has commonly been broken using two different “lockpicks”.

  • Brute force, guessing the Key, only 26 guesses needed.
  • Frequency analysis - Counting the occurrences of letters in a given text, and mapping to the frequency of the letter occurrences in a given language. For example in English, the most frequently occurring letter is ‘e’ while the second most frequent is ‘t’. This can be leveraged to make an estimated guess to what letters have been substituted with each other.

Try and see if you can break this message:

Ilqdolvwv lq wkh QLVW vwdqgduglbdwlrq frpshwlwlrqc

We will give you the solution in the next newsletter!

References

Written by

Slim Bettaieb

Cryptography Researcher

Ais Connolly

Cryptography Researcher, member of Worldline Scientific Community

Mattias Westlund

Information Security Officer, Cyber Security Expert

Jurjen Bos

Cryptography Specialist

Nourredine Khadri

Security Officer, DevSecOps Advocate, Cyber Security Domain Leader