Paper 2024/244
Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems
, Technology Innovation Institute, Technology Innovation Institute, Polytechnic University of Turin, Polytechnic University of Turin, Technology Innovation InstituteAbstract
The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with additional properties, including linkable ring, group, and threshold signatures, has been proposed. These novel constructions introduce relaxed versions of LCE (and MCE), wherein multiple samples share the same secret equivalence. Despite their significance, these variations have often lacked a thorough security analysis, being assumed to be as challenging as their original counterparts. Addressing this gap, our work delves into the sample complexity of LCE and MCE --- precisely, the sufficient number of samples required for efficient recovery of the shared secret equivalence. Our findings reveal, for instance, that one shouldn't use the same secret twice in the LCE setting since this enables a polynomial time (and memory) algorithm to retrieve the secret. Consequently, our results unveil the insecurity of two advanced signatures based on variants of the LCE Problem.
Note: Updated experimental results.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Algebraic AttackCode EquivalenceCode-based CryptographyCryptanalysisPost-quantum Cryptography
- Contact author(s)
-
budroni alessandro @ gmail com
jesus dominguez @ tii ae
giuseppe dalconzo @ polito it
antonio discala @ polito it
mukul kulkarni @ tii ae - History
- 2024-03-07: revised
- 2024-02-15: received
- See all versions
- Short URL
- https://ia.cr/2024/244
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/244,
author = {Alessandro Budroni and Jesús-Javier Chi-Domínguez and Giuseppe D'Alconzo and Antonio J. Di Scala and Mukul Kulkarni},
title = {Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems},
howpublished = {Cryptology ePrint Archive, Paper 2024/244},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/244}},
url = {https://eprint.iacr.org/2024/244}
}
