## CryptoDB

### Jean-Pierre Tillich

#### Publications

**Year**

**Venue**

**Title**

2023

ASIACRYPT

A new approach based on quadratic forms to attack the McEliece cryptosystem
Abstract

We introduce a novel algebraic approach for attacking the
McEliece cryptosystem which is currently at the $4$-th round of the
NIST competition. The contributions of the article are twofold.
(1) We present a new distinguisher on alternant and Goppa codes
working in a much broader range of parameters than \cite{FGOPT11}. (2) With this approach we also
provide a polynomial--time key recovery attack on
alternant codes which are distinguishable with the distinguisher
\cite{FGOPT11}.
These results are obtained by introducing a subspace of matrices
representing quadratic forms. Those are associated with quadratic
relations for the component-wise product in the dual of the Goppa
(or alternant) code of the cryptosystem. It turns out that this subspace
of matrices contains matrices of unusually small rank in the case of alternant or
Goppa codes ($2$ or $3$ depending on the field characteristic)
revealing the secret polynomial structure
of the code.
MinRank solvers can then be used to recover the
secret key of the scheme. We devise a dedicated algebraic modeling in
characteristic $2$ where the Gröbner basis techniques to solve it can be analyzed.
This computation behaves differently
when applied to the matrix space associated with a
random code rather than with a Goppa or an alternant code. This
gives a distinguisher of the latter code families, which contrarily
to the one proposed in \cite{FGOPT11} working only in a tiny parameter regime is now
able to work for code rates above $\frac{2}{3}$. It applies to most of the
instantiations of the McEliece cryptosystem in the literature. It coincides with the one of \cite{FGOPT11}
when the latter can be applied (and is therefore of polynomial complexity in this case). However, its complexity
increases significantly when \cite{FGOPT11} does not apply anymore, but stays subexponential as long as the co-dimension of the code is sublinear in the length (with an asymptotic exponent which is below those of all known key recovery or message attacks). For the concrete parameters of the McEliece NIST submission \cite{ABCCGLMMMNPPPSSSTW20}, its
complexity is way too complex to threaten the cryptosystem, but is smaller than known key recovery attacks for most
of the parameters of the submission. This subspace of quadratic forms can also be used in a different manner
to give a polynomial time attack of the McEliece cryptosystem
based on generic alternant codes or Goppa codes provided that these codes are distinguishable by the method of
\cite{FGOPT11}, and in the Goppa case we need the additional assumption that its degree is less than $q-1$, where $q$ is the
alphabet size of the code.

2023

TCC

Rigorous Foundations for Dual Attacks in Coding Theory
Abstract

Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques
which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of
the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence.
These dual attacks can actually be viewed as the code-based analogue of dual attacks in lattice based cryptography. Here too, dual attacks have been found out
those past years to be strong competitors to primal attacks and a controversy has emerged whether similar heuristics made for instance on the independence of certain
random variables really hold. We will show that the dual attacks in coding theory can be studied by providing in a first step
a simple alternative expression of the fundamental quantity used in these dual attacks. We then show that this expression can be studied without relying on independence
assumptions whatsoever. This study leads us to discover that there is indeed a problem with the latest and most powerful dual attack proposed in \cite{CDMT22} and that
for the parameters chosen in this algorithm there are indeed false candidates which are produced and which are not predicted by the analysis provided there which relies on
independence assumptions. We then suggest a slight modification of this algorithm consisting in a further verification step, analyze it thoroughly, provide experimental evidence
that our analysis is accurate and show that the complexity claims made in \cite{CDMT22} are indeed valid for this modified algorithm. This approach provides a simple methodology
for studying rigorously dual attacks which could turn out to be useful for further developing the subject.

2022

ASIACRYPT

Statistical Decoding 2.0: Reducing Decoding to LPN
📺
Abstract

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD).
A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding.
It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it
performed poorly when compared to the simplest ISD algorithm.
We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than 0.3. It gives for the first time after 60 years, a better decoding algorithm for a significant range which does not belong to the ISD family.

2020

EUROCRYPT

An Algebraic Attack on Rank Metric Code-Based Cryptosystems
📺
Abstract

The Rank metric decoding problem is the main problem considered in
cryptography based on codes in the rank metric. Very efficient schemes based
on this problem or quasi-cyclic versions of it have been proposed recently,
such as those in the submissions ROLLO and RQC currently at the second round
of the NIST Post-Quantum Cryptography Standardization Process. While
combinatorial attacks on this problem have been extensively studied and seem
now well understood, the situation is not as satisfactory for algebraic
attacks, for which previous work essentially suggested that they were
ineffective for cryptographic parameters.
In this paper, starting from Ourivski and Johansson's algebraic modelling of
the problem into a system of polynomial equations, we show how to augment
this system with easily computed equations so that the augmented system is
solved much faster via Gröbner bases. This happens because the augmented
system has solving degree $r$, $r+1$ or $r+2$ depending on the parameters,
where $r$ is the rank weight, which we show by extending results from Verbel
\emph{et al.} (PQCrypto 2019) on systems arising from the MinRank problem;
with target rank $r$, Verbel \emph{et al.} lower the solving degree to $r+2$,
and even less for some favorable instances that they call
``superdetermined''. We give complexity bounds for this approach as well as
practical timings of an implementation using \texttt{magma}. This improves
upon the previously known complexity estimates for both Gröbner basis and
(non-quantum) combinatorial approaches, and for example leads to an attack in
200 bits on ROLLO-I-256 whose claimed security was 256 bits.

2020

ASIACRYPT

Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems
📺
Abstract

In this paper, we show how to significantly improve algebraic techniques for solving the MinRank problem, which is ubiquitous in multivariate and rank metric code based cryptography. In the case of the structured MinRank instances arising in the latter, we build upon a recent breakthrough in Bardet et al. (EUROCRYPT 2020) showing that algebraic attacks outperform the combinatorial ones that were considered state of the art up until now. Through a slight modification of this approach, we completely avoid Gr\¨obner bases computations for certain parameters and are left only with solving linear systems. This does not only substantially improve the complexity, but also gives a convincing argument as to why algebraic techniques work in this case. When used against the second round NIST-PQC candidates ROLLO-I-128/192/256, our new attack has bit complexity respectively 71, 87, and 151, to be compared to 117, 144, and 197 as obtained in Bardet et al. (EUROCRYPT 2020). The linear systems arise from the nullity of the maximal minors of a certain matrix associated to the algebraic modeling. We also use a similar approach to improve the algebraic MinRank solvers for the usual MinRank problem. When applied against the second round NIST-PQC candidates GeMSS and Rainbow, our attack has a complexity that is very close to or even slightly better than those of the best known attacks so far. Note that these latter attacks did not rely on MinRank techniques since the MinRank approach used to give complexities that were far away from classical security levels.

2019

ASIACRYPT

Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
★
Abstract

We present here a new family of trapdoor one-way functions that are Preimage Sampleable on Average (PSA) based on codes, the Wave-PSA family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $$(U,U+V)$$-codes. Our proof follows the GPV strategy [28]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSA family with ternary generalized $$(U,U+V)$$-codes to design a “hash-and-sign” signature scheme which achieves existential unforgeability under adaptive chosen message attacks (EUF-CMA) in the random oracle model.

2018

ASIACRYPT

Two Attacks on Rank Metric Code-Based Schemes: RankSign and an IBE Scheme
Abstract

RankSign [30] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [5] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [26]. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [5] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rank-based cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [26] IBE scheme by the Hamming metric, then a devastating attack can be found.

#### Program Committees

- PKC 2023
- Asiacrypt 2023
- Crypto 2021

#### Coauthors

- Magali Bardet (2)
- Pierre Briaud (1)
- Maxime Bros (2)
- Daniel Cabarcas (1)
- Kevin Carrier (1)
- Alain Couvreur (3)
- Thomas Debris-Alazard (3)
- Frédéric Didier (1)
- Jean-Charles Faugère (1)
- Philippe Gaborit (3)
- Valérie Gauthier-Umaña (1)
- Adrien Hauteville (1)
- Charles Meyer-Hilfiger (2)
- Rocco Mora (1)
- Vincent Neiger (1)
- Ayoub Otmani (3)
- Ray Perlner (1)
- Ludovic Perret (1)
- Duong Hieu Phan (1)
- Olivier Ruatta (1)
- Nicolas Sendrier (1)
- Daniel Smith-Tone (1)
- Jean-Pierre Tillich (14)
- Javier Verbel (1)
- Gilles Zémor (2)