Post-Quantum Cryptography: Why? What is it?

Why Post-Quantum Cryptography?

When I wrote my first blog entry here ("Ola from Gustavo"), I gave a short description of what will happen when someone presents the first quantum computer, i.e., most of the actual cryptography (ECC, RSA) will be dead, see [1] for more details. One statement about quantum computers and cryptography is:
"Well, we don't have a quantum computer now and the expectation for one is around 15 years, why I should be worried now?"
I will give one good reason, imagine that you use some encryption (RSA, ECC or whatever) in your messages and someone starts storing these messages. Now, this agency/person/computer is not able to read your messages. However, in 15 years (around this) when a real quantum computer appears then, it will be possible to break the encryption and read everything about your past. For this reason, we need to be prepared against this threat now and we don't need to wait for the quantum computer to start to protect ourselves. For this protection, we have good guardians of the privacy that with the union of their powers started the research in Post-Quantum cryptography (PQC).

In the figure (see above), we can see that PQC divides into four big areas, i.e., Hash-based, Code-based, Multivariate-quadratic-equations-based and Lattice-based. There are other areas but these four became more important in the last 10 years. In the following, I will give a very brief explanation and examples of schemes of each area in PQC. There is a website about PQCrypto with initial recommendations and a list of publications in the area to access click here.

HASH-BASED Cryptography

In hash-based, we can see important signature schemes such as Lamport-Diffie OTS, Merkle's hash-tree, XMSS, SPHINCS and a lot of relevant work. I decided to talk about one of the newest works in the area, i.e., SPHINCS.
SPHINCS was presented in 2015 at EUROCRYPT under the title of "SPHINCS: practical stateless hash-based signatures". In order to understand better the idea behind this work, it is necessary to have a previous knowledge about hash signatures because they present two new ideas: replacement of the leaf OTS (One-time Signature) with a hash-based FTS (Few-time Signature) and Goldreich’s construction as a hyper-tree construction with h layers of trees of height 1. For more details about the implementation and construction of SPHINCS, it is possible to access here.
Also, if you have more interest in Hash-Based cryptography can be checked via pqcrypto hash-based and at this webpage of Andreas Hülsing.

CODE-BASED Cryptography

The classic name that appears in Code-based is McEliece’s hidden-Goppa-code public-key encryption system from 1978. However, there is new work in the area such as the work from Misoczki, Tillich, Sendrier, and Barreto using quasi-cyclic moderate-density-parity-check (QC-MDPC) codes for the McEliece encryption system. The principal contribution of this work for the area is the use of small key sizes.
Other relevant work, this time in the fast implementation area, came from Bernstein, Chou, and Schwabe under the name of "McBits: Fast constant-time code-based cryptography". The main contribution of this work is a constant-time in the implementation of code-based cryptography and they avoid time attacks.
The literature for code-based is very big and can be checked in this link.

MQ-BASED Cryptography

The Multivariate Cryptography schemes are based on the difficult to solve non-linear systems of equations over
finite fields. Finding a solution for these systems, in general, is considered a NP-complete/-hard problem. One of many
interesting examples is Patarin’s Hidden Fields , generalizing a proposal by Matsumoto and Imai (1988).
The original work from Paratin can be found at: Hidden Field Equations (HFE) andIsomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms.

If we want to see what happened recently in the MQ area, there is slides from the PQCrypto winter school are available online at PQCrypto . The slides from Jintai Ding gave a very nice overview of the state-of-art in the Multivariate
Public Key Cryptography (MPKC). In the slides, he gave an introduction MQ with a small example to understand
how MQ works. After that, the author gives the principal cryptosystems in MPKC.
The slides are available at this link and more material about MQ-based cryptography can be checked at PQCrypto project.

LATTICE-BASED Cryptography

The lattice area received a lot of attention in the past years, new cryptosystems, new attacks, and implementations. Everything is based on hard problems in lattices such as shortest-vector problem (SVP), Ideal Lattice, Closest-vector Problem (CVP) and others. There is a lattice challenge to show the shortest vector in a Lattice and the ideal Lattice given the dimension of it, more details about it can be checked at Lattice Challenge.

In the area of public-key cryptography, there are several schemes and mostly is based on SVP and Ideal lattices. That is the case for  the scheme described by Peikert and Stehlé et al.

Post-quantum Cryptography and ECRYPT-NET

One of the interests of the ECRYPT-NET project is in PQC and we have four fellowships working in this area. In Lattice-based, we have Marco Martinoli, Michele Minelli and Henry de Valence. In the quantum algorithms area I started work with this.

I started to read about all of the areas described before for two reasons. Firstly, I needed to understand the basic of each area to decide where I want to work. Secondly,  after all the reading I decided to work with quantum algorithms and attack each area using it. In the following months, I will start writing about quantum algorithms and the impact in the cryptography.


[1] Bernstein, Daniel J., Johannes Buchmann, and Erik Dahmen, eds. Post-quantum cryptography. Springer Science & Business Media, 2009.