Source author record

Julien Lavauzelle

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Cryptography and Security math.NT math.RA

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Cryptanalysis of a System Based on Twisted Reed-Solomon Codes

Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in $O(n^4)$ field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov cryptosystems based on twisted Gabidulin codes.

preprint2020arXiv

On the privacy of a code-based single-server computational PIR scheme

We show that the single-server computational PIR protocol proposed by Holzbaur, Hollanti and Wachter-Zeh in 2020 is not private, in the sense that the server can recover in polynomial time the index of the desired file with very high probability. The attack relies on the following observation. Removing rows of the query matrix corresponding to the desired file yields a large decrease of the dimension over $\mathbb{F}_q$ of the vector space spanned by the rows of this punctured matrix. Such a dimension loss only shows up with negligible probability when rows unrelated to the requested file are deleted.

preprint2020arXiv

Rank-metric codes over arbitrary Galois extensions and rank analogues of Reed-Muller codes

This paper extends the study of rank-metric codes in extension fields $\mathbb{L}$ equipped with an arbitrary Galois group $G = \mathrm{Gal}(\mathbb{L}/\mathbb{K})$ . We propose a framework for studying these codes as subspaces of the group algebra $\mathbb{L}[G]$ , and we relate this point of view with usual notions of rank-metric codes in $\mathbb{L}^N$ or in $\mathbb{K}^{N\times N}$ , where $N = [\mathbb{L} : \mathbb{K}]$ . We then adapt the notion of error-correcting pairs to this context, in order to provide a non-trivial decoding algorithm for these codes. We then focus on the case where $G$ is abelian, which leads us to see codewords as elements of a multivariate skew polynomial ring. We prove that we can bound the dimension of the vector space of zeroes of these polynomials, depending of their degree. This result can be seen as an analogue of Alon-Füredi theorem -- and by means, of Schwartz-Zippel lemma -- in the rank metric. Finally, we construct the counterparts of Reed-Muller codes in the rank metric, and we give their parameters. We also show the connection between these codes and classical Reed-Muller codes in the case where $\mathbb{L}$ is a Kummer extension.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Julien Lavauzelle

Research overview

Is this your work?

3 publications

Cryptanalysis of a System Based on Twisted Reed-Solomon Codes

On the privacy of a code-based single-server computational PIR scheme

Rank-metric codes over arbitrary Galois extensions and rank analogues of Reed-Muller codes

See the researcher in context

Building this map preview