HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

An algebraic approach to the Rank Support Learning problem

Abstract : Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this paper, we propose an algebraic attack on RSL which clearly outperforms the previous attacks to solve this problem. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard Gröbner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03158460
Contributor : Magali Bardet Connect in order to contact the contributor
Submitted on : Tuesday, March 23, 2021 - 3:01:18 PM
Last modification on : Wednesday, March 2, 2022 - 10:10:12 AM

Files

arxiv-v2.pdf
Files produced by the author(s)

Identifiers

Citation

Magali Bardet, Pierre Briaud. An algebraic approach to the Rank Support Learning problem. PQCrypto 2021 - Post-Quantum Cryptography 12th International Workshop, Jul 2021, Daejeon, South Korea. pp.442-462, ⟨10.1007/978-3-030-81293-5_23⟩. ⟨hal-03158460v2⟩

Share

Metrics

Record views

146

Files downloads

351