## CryptoDB

### Jean-Pierre Tillich

#### Affiliation: INRIA

#### Publications

**Year**

**Venue**

**Title**

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.

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.

#### Coauthors

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