Industrial Transfert: Post-Quantum Cryptography

The security of public-key cryptosystems is based on the hardness of solving hard mathematical problems. From a practical point of view, the hard problems mostly considered in practice are the problem of factoring integers (FACT) and the discrete logarithm problem (DLOG) over finite fields or elliptic curves. In the classical setting, it is believed that these problems are indeed computationally hard, i.e. no polynomial-time algorithm exists for solving these problems. This basic assumption is no longer valid in a quantum setting. Shor's algorithm from the 90's allows to solve (FACT) and (DLOG) in polynomial-time on a quantum computer. This milestone result motivated the design of new public-key cryptosystems which are secure in the classical and quantum setting. This area of cryptography is called post-quantum cryptography or quantum-resistant cryptography.

The most promising quantum-resistant cryptosystems include multivariate crytography which is based on the problem of solving a system of non-linear equations over a finite field (PoSSo problem), code-based crytography which is related to the difficulty of decoding a random linear code, lattice-based cryptography which is based on the hardness of finding a short vector in a lattice and hash-based cryptosystems that use hash functions.

The effort to develop quantum-resistant techniques is now intensifying. NIST, which has the authority to establish US standards, released in January 2016 a call for proposals to standardize some quantum-resistant cryptosystems within 2020. With historical perspective, it seems likely that the quantum-resistant standards derived from this process will be widely endorsed around the world. This is a game changer for public-key cryptography. This will induce an intense activity in quantum-resistant cryptography in the next years from both from an academic and industrial point of view. For example, PolSys is involved in the RISQ project which is a large industrial project whose goal is to prepare the french security industry the upcoming shift of classical cryptography to quantum-safe cryptography.

PolSys is also involved in the quantum-safe security working group of the Cloud Security Alliance (CSA) and in the quantum-safe cryptography specification group of the European Telecommunications Standards Institute (ETSI).

A challenge of quantum-resistant cryptography is now to show that it can be used at large scale on various devices. The team has developped, together with a french startup WASSA, an Android application which allows to encrypt and decrypt documents. The project was funded by SATT-LUTECH; an accelerating technology transfer unit from UPMC.

The particularity of this application is to use a multivariate encryption scheme to perform the key-exchange. It is not so difficult to find a good multivariate signature scheme. However, the design of a secure and efficient multivariate encryption scheme is much more challenging. We have then designed a variant of the classical Patarin's HFE- scheme (Hidden Field Equations with minus, [P96]) that we have called HFEBoost. We have a good cryptanalytic record against HFE-. We know that there is essentially one parameter which governs the efficiency and security [FJ03,BFP13]. HFEBoost is a careful choice of the parameters with a particular, somewhat sparse, secret polynomial (few more details here) The Android application has been tested during real experiments performed by French army. The goal was to test the next generation of communication systems. Our application was only a small part of these experiments. The application has been deployed on the smartphones (Samsung Galaxy S5) of around 100 participants (military, national security, DGA,...) and experimented in various operational scenarios. The experiments were performed through a home-made 4G network deployed on a dedicated site.

For a security level of 80 bits, HFEBoost has a public-key of 130 Kbytes. The first lesson learned is that no problem has been reported regarding the size of the public-key and its transmission on the 4G channel. The time for performing a key-exchange is around 0.7 seconds. The application is still a proof-of-concept and performances could be improved. Still, the second lesson learned is that smartphones are today very powerful. As a side remark, the application could be easily extended to perform electronic signatures. In this case, the signature size is 128 bits and the verification will take few milliseconds.

The morality of this experiment is that multivariate cryptography can be used in real-life.

The RISQ project is a natural extension of the HFEBoost project; at a much larger scale.

If your are interested to test HFEBoost; please contact us (J.-C. Faugère or L. Perret).