## CryptoDB

### Jean-Charles Faugère

#### Publications

**Year**

**Venue**

**Title**

2019

TCHES

Software Toolkit for HFE-based Multivariate Schemes
📺
Abstract

In 2017, NIST shook the cryptographic world by starting a process for standardizing post-quantum cryptography. Sixty-four submissions have been considered for the first round of the on-going NIST Post-Quantum Cryptography (PQC) process. Multivariate cryptography is a classical post-quantum candidate that turns to be the most represented in the signature category. At this stage of the process, it is of primary importance to investigate efficient implementations of the candidates. This article presents MQsoft, an efficient library which permits to implement HFE-based multivariate schemes submitted to the NIST PQC process such as GeMSS, Gui and DualModeMS. The library is implemented in C targeting Intel 64-bit processors and using avx2 set instructions. We present performance results for our library and its application to GeMSS, Gui and DualModeMS. In particular, we optimize several crucial parts for these schemes. These include root finding for HFE polynomials and evaluation of multivariate quadratic systems in F2. We propose a new method which accelerates root finding for specific HFE polynomials by a factor of two. For GeMSS and Gui, we obtain a speed-up of a factor between 2 and 19 for the keypair generation, between 1.2 and 2.5 for the signature generation, and between 1.6 and 2 for the verifying process. We have also improved the arithmetic in F2n by a factor of 4 compared to the NTL library. Moreover, a large part of our implementation is protected against timing attacks.

2014

EUROCRYPT

2014

EPRINT

2014

ASIACRYPT

2012

EUROCRYPT

2010

EPRINT

A Distinguisher for High Rate McEliece Cryptosystems
Abstract

The purpose of this paper is to study the difficulty of the so-called
Goppa Code Distinguishing (GD) problem introduced by
Courtois, Finiasz and Sendrier in Asiacrypt 2001. GD is the problem of distinguishing the public matrix in the McEliece cryptosystem from a random matrix. It is widely believed that this problem is computationally hard as proved by
the increasing number of papers using this hardness assumption.
To our point of view, disproving/mitigating this hardness assumption is a breakthrough in code-based cryptography
and may open a new direction to attack McEliece cryptosystems.
In this paper, we present an efficient distinguisher for alternant and
Goppa codes of high rate over binary/non binary fields. Our
distinguisher is based
on a recent algebraic attack against compact variants of McEliece
which reduces the key-recovery to the problem of solving an
algebraic system of equations. We exploit a defect of rank in the
(linear) system obtained by linearizing this algebraic system. It turns out that our distinguisher is highly
discriminant. Indeed, we are able to precisely quantify the defect of
rank for ``generic'' binary and non-binary random, alternant and Goppa
codes. We have verified these formulas with practical experiments,
and a theoretical explanation for such defect of rank is also
provided. We believe that this work permits to shed some light on the choice of secure parameters for McEliece cryptosystems; a
topic thoroughly investigated recently. Our technique permits to indeed
distinguish a public key of the CFS signature scheme for all parameters proposed by
Finiasz and Sendrier at Asiacrypt 2009. Moreover, some realistic parameters of McEliece scheme also fit in the
range of validity of our distinguisher.

2008

EPRINT

Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages
Abstract

In \cite{BPW}, Buchmann, Pyshkin and Weinmann have described two families of
Feistel and SPN block ciphers called Flurry and Curry
respectively. These two families of ciphers are fully parametrizable and have
a sound design strategy against basic statistical attacks; i.e. linear and
differential attacks. The encryption process can be easily described by a set
of algebraic equations. These ciphers are then targets of choices for
algebraic attacks. In particular, the key recovery problem has been reduced to
changing the order of a Groebner basis \cite{BPW,BPWext}. This attack -
although being more efficient than linear and differential attacks - remains
quite limited. The purpose of this paper is to overcome this limitation by
using a small number of suitably chosen pairs of message/ciphertext for
improving algebraic attacks. It turns out that this approach permits to go one
step further in the (algebraic) cryptanalysis of Flurry and
\textbf{Curry}. To explain the behavior of our attack, we have established an
interesting connection between algebraic attacks and high order differential
cryptanalysis \cite{Lai}. From extensive experiments, we estimate that our
approach, that we can call an ``algebraic-high order
differential" cryptanalysis, is polynomial when the Sbox is a power function.
As a proof of concept, we have been able to break Flurry -- up to
$8$ rounds -- in few hours.

2003

CRYPTO

#### Program Committees

- Eurocrypt 2016
- PKC 2015

#### Coauthors

- Martin R. Albrecht (4)
- Gwénolé Ars (1)
- Luk Bettale (1)
- Jingguo Bi (2)
- Charles Bouillaguet (1)
- Jean-Sébastien Coron (3)
- Pooya Farshim (1)
- Robert Fitzpatrick (3)
- Pierre-Alain Fouque (1)
- Pierrick Gaudry (1)
- Danilo Gligoroski (1)
- Louise Huot (2)
- Hideki Imai (1)
- Antoine Joux (2)
- Mitsuru Kawazoe (1)
- Françoise Levy-dit-Vehel (1)
- Raphaël Marinier (1)
- Phong Q. Nguyen (2)
- Ayoub Otmani (4)
- Marta Conde Pena (1)
- Ludovic Perret (19)
- Christophe Petit (1)
- Frédéric de Portzamparc (3)
- Guénaël Renault (5)
- Guénaël Renault (2)
- Jocelyn Ryckeghem (1)
- Simona Samardjiska (1)
- Pierre-Jean Spaenlehauer (1)
- Makoto Sugita (1)
- Enrico Thomae (1)
- Jean-Pierre Tillich (4)
- Yosuke Todo (1)
- Vanessa Vitse (1)
- Keita Xagawa (1)
- Rina Zeitoun (3)