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{\"o}bner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought.
翻译:以兰度计码为基础的加密法依赖于在等级标准中解码随机线性代码的严格性。 排名支持学习问题( RSL) 是一个变体, 攻击者可以使用N解码实例, 其错误具有同样的支持, 并希望解决其中的一个错误。 这个问题在杜兰达尔签名计划中使用了。 在本文中, 我们提议对RSL进行代数攻击, 这明显超过先前的攻击, 以解决这个问题。 我们以Bardet 等人( Asiacrypt 2020)为基础, 在那里, 使用类似的技术来解决MinRank 和 RD 。 然而, 我们的分析比较简单, 并且总体来说, 我们的攻击依赖于与标准 Gr@'o}bner 基地攻击相比最基本的假设。 特别是, 我们的结果表明, 对Durandal 的关键恢复攻击比以前想象的更有效。