Post-Quantum Cryptography Series - Second Newsletter

In this newsletter we will provide information of the context of the international competition organized by NIST to standardize post-quantum cryptographic algorithms and how Worldline contributed to it. We will also give an update on the ongoing competition and highlight the cryptographic primitives that NIST will develop.

The NIST competition

Given the advancements in the development of the construction of a quantum computer, the National Institute of Standards and technology (NIST) has decided to launch a competition to select new cryptographic algorithms that are secure against attacks using both classical and quantum computers. The public standardization process started in December 2016, when NIST published an open call for proposals to develop new standards for Digital Signatures (DS), Public-Key Encryption (PKE) and Key-Encapsulation Mechanism (KEM). NIST has publicly stated that they expect to standardize more than one algorithm for each cryptographic functionality in order to provide different trade-offs depending on the application environments.

Worldline’s contribution and more about the competition

Worldline entered the competition in collaboration with the CNRS XLIM laboratory which is an historical partner of Worldline and four proposals of KEM/PKE have been submitted which are BIKE, HQC, RQC and Ouroboros-R. Our contribution to the standardization effort is a great way to demonstrate the strong commitment of Worldline to innovative security solutions. It is also an opportunity to us to expand our knowledge and expertise on post-quantum cryptography. This expertise enhances our ability to support Worldline and its clients in the upcoming transition to quantum-safe cryptosystems.

In December 2017, a total of 82 proposals were submitted by the start of the competition. The NIST has eliminated 13 of them before the round 1 as they did not meet some of the requirements specified in its call for proposal. During the first round, the analysis of the proposals has identified issues ranging from minor implementation errors to practical attacks breaking the security of some cryptosystems. In early 2019, NIST announced a list of cryptosystems that have been selected for the second round. Only 26 candidates were left remaining for the round 2, with all four proposals involving Worldline being among the selected schemes. During the round 2, the NIST focused mainly on performances and eliminated additional cryptosystems so that only 15 cryptosystems have been selected to move forward to round 3. Among the selected cryptosystems, two schemes proposed by Worldline and its partners have been selected. These two schemes are code-based cryptosystems named respectively BIKE and HQC. The round three candidates fall in two categories; “finalists candidates” and “alternates candidates” as NIST intend to deal with them differently. NIST expects to select  some schemes from these two categories for standardization but may do so following two different timelines. Some schemes from the finalists will be standardized at the conclusion of the round 3 while schemes from the alternates will be considered for standardization after a fourth round of competition.

Targeted cryptographic primitives

Here we will talk about the primitives being standardized because we feel it’s important for you to know them.

Digital Signatures

Digital signatures aims to provide authenticity and integrity of data, communications or documents. In other words, a signature scheme allows a signer S to provide a proof that a certain piece of data is authentic and has not been altered by a non-authorized person. The proof provided by the signer is called a signature and is computed as a function of the data to be signed and a signing key. On the other hand, using a verification key, anybody can verify the signature. The strange thing is that is not possible to find the signing key if you know the verification key. As you can probably guess, signature schemes are a public-key primitives, which means that the signature generation and verification are done using the secret key and a public key, respectively. More precisely, a signature scheme typically consists of three algorithms:

  • A key generation algorithm that generates a key pair for the signer. The key pair consists of a secret key (the signing key) and a corresponding public key (verification key) that can then be made publicly known to everyone.
  • A signing algorithm that is used by the signer, which is given a secret key and a message, generates a signature.
  • A verifying algorithm that can be used by anyone who knows the public key. Given a public key, a signature and a message, it returns success if the authenticity claim is valid, and returns error otherwise.

For example, a digital signature can be used by a software company to authenticate the updates that it can release to its customers. The goal is to provide a proof that what they will be installing on their systems is a safe and genuine software released by the company and no one else. At the beginning, the software company generates a keypair (a public and a secret key) and then sends the public key to its customers. Then when releasing a software update, the company uses the secret key to sign it and sends the obtained signature with the update package. Each customer can verify the authenticity of the update package by verifying the validity of the signature using the public key. This is particularly useful for IoT devices that do their software updates automatically without user interaction.

Nowadays, digital signatures play an important role in providing authentication and data integrity. The broad scope of real world applications ranges from Public Key Infrastructures (PKIs), Internet Security Protocols (TLS and IPsec ), security tokens, to more sophisticated protocols such as advanced Zero-Knowledge Proofs and Privacy Preserving Signatures.

Public Key Encryption

Public Key Encryption or asymmetric encryption is a way to send encrypted messages to a person without exchanging keys.

In fact, with an asymmetric encryption scheme anyone can send you an encrypted messages by simply using your public key; there is no need to share a secret key in advance.

There are two main limits to the direct use of an asymmetric encryption schemes in practice. First, public key encryption on itself is limited in the length of messages it can encrypt. It cannot encrypt messages that are larger than the size of its keys. Secondly, asymmetric encryption is quite slow compared to symmetric encryption. This is due to the fact that encryption and decryption in the asymmetric setting involves complicated math operations.

Actually, what it is used in practice is hybrid encryption: the combination of an asymmetric encryption scheme with a symmetric encryption scheme. The idea of hybrid encryption is to take advantage of the convenience of asymmetric encryption in distributing keys and the computational efficiency and bandwidth savings of symmetric encryption.

For example, the first application of public key encryption in the payment world originated from a fraud case in august 1999. At that time, small companies handled their batch payments as follows: their administration software collected the payment commands into a file in a special format. This file was saved onto a floppy disk, and sent by (physical) mail to Interpay. Interpay would read the floppy disks with an automated disk reader; the files were entered directly into the processing system. Fraudsters stole the envelopes with floppy disks at the post offices. They modified the payment files on their home computer to their advantage, making sure the payment total wasn’t modified as not to raise suspicion, and put them back into the mail bag. Millions of guilders were stolen from companies this way.

At that time, there was no way to easily handle key distribution (the Internet was barely there), and the people in the companies didn’t even know what cryptography was. The solution (which Jurjen helped design) was to use public key cryptography, based on RSA. The companies got a special floppy disk with a computer program that encrypted the payment file. The encryption was such that nobody except Interpay was able to decrypt the files.

All the companies had to know was that they had to use that program for sending payment files. The fraud immediately stopped after Interpay required all payment files to be sent in this way.

This method of encryption is called “public encryption”, which is obvious from the fact that the encryption key is not secret: only the legitimate recipient is able to receive the message. In this case, the encryption was performed as follows:

  • The encrypting program generates a random encryption key (single DES, at that time).
  • This encryption key is used to encrypt the payment file.
  • The encryption key is encrypted using a the public RSA key stored in the program.
  • The result of step 2 and 3 is stored on the floppy disk that is sent to Interpay.
Payment file encryption
  • On the receiving end, Interpay’s processing system, in possession of the corresponding RSA private key, could compute the encryption key and then decrypt the file for processing.

Post quantum public key encryption algorithms are now available, but unfortunately this is not as simple as the RSA public encryption where you can “put the signature algorithm in reverse”.

Worldline has made a few candidate public key encryption algorithms that are submitted to the NIST competition and withstood the scrutiny of cryptographers.

Key Encapsulation Mechanisms (KEMs)

As you can see from the example above, an asymmetric encryption scheme or a public key encryption (PKE) is convenient because it makes key distribution much easier.

In the jargon of a cryptographer, hybrid encryption uses a cryptographic primitive called a Key-Encapsulation Mechanism (KEM). This primitive performs the necessary computations for obtaining the symmetric key used to encrypt messages an its encryption under an asymmetric key in one step. A KEM typically consists of three algorithms:

  • A key generation algorithm that generates a key pair which consists of a secret key and a corresponding public key. The public key can be made publicly known to everyone.
  • An encapsulation algorithm that takes as input a public key and it outputs a ciphertext and a secret key used to symmetrically encrypt data.
  • A decapsulation algorithm that takes as input a secret key and a ciphertext and outputs a secret key used to symmetrically decrypt data.

KEMs are used everywhere where hybrid encryption is used: in encrypted mail, browsing the internet, but also in inter-application communication within different parts of our company, and application data transport with clients. Because KEMs use public key encryption, classic KEMs are not resistant against a quantum computer attack. Therefore, the NIST competition explicitly addresses KEMs as a primitive, inviting cryptographers to find one that will stay secure even when quantum computers would be able to break current public encryption methods.

Challenge for beginning cryptographers

The classic Vigenère system has been described in our previous newsletter . You can find more information on it in Wikipedia, if you want. We used the Vigenère cipher to encrypt a short message. The key we used is the pet of one of the authors of this article.

The ciphertext is:

Vhx foz lufrew qvxt tag omjek foz

Can you find the message?

Note: spaces are normally not encoded using Vigenère and are added for clarity.

Solution to the previous challenge: Finalists in the NIST standardiyation competitionz

References