Recent rank-based attacks have reduced the security of Rainbow below the security requirements set out by NIST by speeding up repeated kernel finding operations using classical mathematics techniques. If quantum algorithms are applied to perform these repeated operations, the rank-based attacks may be more threatening and could dramatically lower the security level of Rainbow. In this paper, we propose a novel MinRank attack called Q-rMinRank attack, the first quantum approach to the key recovery attacks on Rainbow. By designing quantum circuits that can find the kernel, we achieved quadratic speedup for the MinRank attack to recover the private keys of Rainbow. We show that even the parameter set V of Rainbow does not meet the 128-bit security level, the minimum security requirement through our Q-rMinRank attack. It means that Rainbow is no longer secure in quantum computing environments.


翻译:最近以等级为基础的袭击使彩虹的安保低于NIST规定的安保要求,加快了使用古典数学技术的反复内核查找操作。如果应用量子算法来进行这些重复操作,那么按级进行的攻击可能更具有威胁性,并可能大大降低彩虹的安全水平。在本文中,我们提议了名为Q-rMinRank攻击的新型MinRank攻击,这是对彩虹进行关键回收攻击的第一个量子方法。通过设计能够找到内核的量子电路,我们实现了MinRank攻击的二次加速,以收回彩虹的私人钥匙。我们证明即使彩虹的参数五也达不到128位安全水平,也就是我们Q-rMinRank攻击的最低安全要求。这意味着彩虹在量计算环境中不再安全。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2022年12月16日
Arxiv
0+阅读 · 2022年12月16日
Arxiv
12+阅读 · 2020年12月10日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员