Paper 2023/1008 Original: eprint.iacr.org/2023/1008 ↗
Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes
Abstract
In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches: - The first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes. - The second one is to rewrite it as a bilinear system over Fq. Even if Gröbner basis techniques on this second system seem infeasible, we provide a detailed analysis of the first degree fall polynomials which arise when applying such algorithms.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2023-06-29: last updated
- 2023-06-29: published
- Short URL
- https://ia.cr/2023/1008
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/1008,
author = {Pierre Briaud and Pierre Loidreau},
title = {Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1008},
year = {2023},
url = {https://eprint.iacr.org/2023/1008}
}