Paper 2024/1757
On the Sample Complexity of Linear Code Equivalence for all Code Rates
, Cryptography Research Center, Technology Innovation Institute, UAE, Department of Mathematics, University of Trento, ItalyAbstract
In parallel with the standardization of lattice-based cryptosystems, the research community in Post-quantum Cryptography focused on non-lattice-based hard problems for constructing public-key cryptographic primitives. The Linear Code Equivalence (LCE) Problem has gained attention regarding its practical applications and cryptanalysis. Recent advancements, including the LESS signature scheme and its candidacy in the NIST standardization for additional signatures, supported LCE as a foundation for post-quantum cryptographic primitives. However, recent cryptanalytic results have revealed vulnerabilities in LCE-based constructions when multiple related public keys are available for one specific code rate. In this work, we generalize the proposed attacks to cover all code rates. We show that the complexity of recovering the private key from multiple public keys is significantly reduced for any code rate scenario. Thus, we advise against constructing specific cryptographic primitives using LCE.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Sample ComplexityCode EquivalenceCryptanalysisPost-quantum Cryptography
- Contact author(s)
-
alessandro budroni @ tii ae
natalea00 @ gmail com - History
- 2024-11-05: revised
- 2024-10-28: received
- See all versions
- Short URL
- https://ia.cr/2024/1757
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/1757,
author = {Alessandro Budroni and Andrea Natale},
title = {On the Sample Complexity of Linear Code Equivalence for all Code Rates},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1757},
year = {2024},
url = {https://eprint.iacr.org/2024/1757}
}
