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 的关键恢复攻击比以前想象的更有效。

0
下载
关闭预览

相关内容

【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Zero-Shot Learning相关资源大列表
专知
52+阅读 · 2019年1月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年4月27日
Arxiv
14+阅读 · 2019年9月11日
Learning to Weight for Text Classification
Arxiv
8+阅读 · 2019年3月28日
One-Shot Federated Learning
Arxiv
9+阅读 · 2019年3月5日
Arxiv
6+阅读 · 2018年12月10日
Meta-Transfer Learning for Few-Shot Learning
Arxiv
8+阅读 · 2018年12月6日
The Matrix Calculus You Need For Deep Learning
Arxiv
12+阅读 · 2018年7月2日
Arxiv
8+阅读 · 2018年4月8日
VIP会员
相关VIP内容
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Zero-Shot Learning相关资源大列表
专知
52+阅读 · 2019年1月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关论文
Arxiv
0+阅读 · 2021年4月27日
Arxiv
14+阅读 · 2019年9月11日
Learning to Weight for Text Classification
Arxiv
8+阅读 · 2019年3月28日
One-Shot Federated Learning
Arxiv
9+阅读 · 2019年3月5日
Arxiv
6+阅读 · 2018年12月10日
Meta-Transfer Learning for Few-Shot Learning
Arxiv
8+阅读 · 2018年12月6日
The Matrix Calculus You Need For Deep Learning
Arxiv
12+阅读 · 2018年7月2日
Arxiv
8+阅读 · 2018年4月8日
Top
微信扫码咨询专知VIP会员