Paper 2025/1292
Key Attack on the ACDGV Matrix Encryption Scheme
, Technical University of Munich, Technical University of Munich, Direction Générale de l'Armement, Université de Rennes, Centre National de la Recherche Scientifique, Institut de recherche mathématique de RennesAbstract
We present an exponential-time key recovery attack on the public-key encryption scheme using matrix codes proposed by Aragon et al. at Asiacrypt 2024. The secret key is a Gabidulin code expanded using an $\mathbb{F}_q$-basis of $\mathbb{F}_{q^m}$ to obtain a matrix code, which is then hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack does not rely on the Gabidulin structure and hence applies to most $\mathbb{F}_{q^m}$-linear codes hidden by their transform. Its complexity is better than the previously best-known distinguisher and significantly better than the naive key recovery algorithm. Our attack breaks some of their proposed parameters. For example, a parameter set targeting 192-bit security is reduced to about 161 bits, and a 256-bit set to about 223 bits.
Note: Full version with appendices.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2026
- Keywords
- rank-metricmatrix codesMcEliece schemepublic-key encryptionstructural attack
- Contact author(s)
-
anmoal porwal @ tum de
antonia wachter-zeh @ tum de
pierre loidreau @ univ-rennes fr - History
- 2026-03-08: revised
- 2025-07-15: received
- See all versions
- Short URL
- https://ia.cr/2025/1292
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1292,
author = {Anmoal Porwal and Antonia Wachter-Zeh and Pierre Loidreau},
title = {Key Attack on the {ACDGV} Matrix Encryption Scheme},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1292},
year = {2025},
url = {https://eprint.iacr.org/2025/1292}
}
