## CryptoDB

### Jean-Pierre Tillich

#### Publications

Year
Venue
Title
2019
ASIACRYPT
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
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.
2017
CRYPTO
2015
PKC
2014
EUROCRYPT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2010
EPRINT
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.
2010
EUROCRYPT
2008
EUROCRYPT
2006
FSE
1994
CRYPTO