Paper 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.
Note: Long version of a paper presented at The Twelfth International Workshop on Coding and Cryptography (WCC 2022) which contains additional results
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. PQCrypto 2023
- Keywords
- Post-quantum cryptographyrank metric code-based cryptographyLoidreau schemecryptanalysis
- Contact author(s)
-
pierre briaud @ inria fr
pierre loidreau @ univ-rennes fr - History
- 2023-06-29: approved
- 2023-06-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1008
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2023/1008}},
url = {https://eprint.iacr.org/2023/1008}
}
