We present an attack against a code-based signature scheme based on the Lyubashevsky protocol that was recently proposed by Song, Huang, Mu, Wu and Wang (SHMWW). The private key in the SHMWW scheme contains columns coming in part from an identity matrix and in part from a random matrix. The existence of two types of columns leads to a strong bias in the distribution of set bits in produced signatures. Our attack exploits such a bias to recover the private key from a bunch of collected signatures. We provide a theoretical analysis of the attack along with experimental evaluations, and we show that as few as 10 signatures are enough to be collected for successfully recovering the private key. As for previous attempts of adapting Lyubashevsky's protocol to the case of code-based cryptography, the SHMWW scheme is thus proved unable to provide acceptable security. This confirms that devising secure code-based signature schemes with efficiency comparable to that of other post-quantum solutions (e.g., based on lattices) is still a challenging task.


翻译:我们根据Song、Huang、Mu、Wu和Wang(SHMWW)最近提出的基于代码的签字计划提出攻击。SHMW计划中的私人钥匙包含部分来自身份矩阵的柱子,部分来自随机矩阵的柱子。两种类型的柱子的存在导致在所制作的签名中分配设定比特的强烈偏差。我们的攻击利用这种偏差从收集的签名群中收回私人钥匙。我们提供了对攻击的理论分析,并同时进行了实验性评价,我们表明,只有10个签名足以收集到成功恢复私人钥匙。正如以往试图将Lyubashevsky的协议改写成基于代码的加密程序一样,SHMMWW计划因此证明无法提供可接受的安全。这证明,设计基于代码的安全签名计划的效率与其他区后解决方案(例如,基于拉特)的效率相当,仍是一项艰巨的任务。

0
下载
关闭预览

相关内容

专知会员服务
31+阅读 · 2021年6月12日
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
专知会员服务
50+阅读 · 2020年12月14日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
4+阅读 · 2019年5月8日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月8日
Arxiv
0+阅读 · 2021年9月7日
Arxiv
0+阅读 · 2021年9月3日
Arxiv
0+阅读 · 2021年9月3日
Arxiv
7+阅读 · 2020年3月1日
Arxiv
3+阅读 · 2018年2月20日
VIP会员
相关VIP内容
专知会员服务
31+阅读 · 2021年6月12日
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
专知会员服务
50+阅读 · 2020年12月14日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
4+阅读 · 2019年5月8日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员