| 引用本文： |
-
毕蕾,路献辉,罗俊杰,王鲲鹏.侧信息对偶攻击[J].信息安全学报,已采用 [点击复制]
- BI Lei,LU Xianhui,LUO Junjie,WANG Kunpeng.Dual Attack with Side Information[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 带错误学习（Learning with Errors，LWE）问题[1]是构造格密码方案最常用的困难问题，在格密码方案设计中得到了广泛的应用。 研究LWE问题的困难性对于分析这些格密码方案的安全性至关重要。原始攻击（primal attack）和对偶攻击（dual attack）是目前LWE问题实际安全性分析中最常用、效果最好的两种攻击方法[2]。 除了实际安全性分析中的攻击方法，2020年，Dachman-Soled、Ducas、Gong等人[3]提出了利用从侧信道中得到信息改进原始攻击效果的基本框架，但并未考虑对偶攻击。最近，关于混合对偶攻击的研究[4-7]结果显示，在许多情形下（混合）对偶攻击的效果比原始攻击更好，因此考虑如何在对偶攻击中利用侧信息是一个有意义的问题。本文研究了这一问题，给出了在对偶攻击中利用侧信息的方法并分析了它们的效果。具体地，本文考虑了4种类型的侧信息，结果表明，它们对于对偶攻击的影响主要体现在对于格的体积的影响上——当格的体积减小时，攻击变得容易。每种侧信息对于格的体积的影响程度不同，本文给出了在一定假设下，不同侧信息对于格体积的具体改变，据此，可分析得到它们对于对偶攻击的效果的最终影响。例如，在经典的BKZ-core-SVP模型下，每个完美提示的加入可将使用嵌入对偶攻击评估实际安全性的结果降低约0.3比特。 |
| 关键词: 格 带错误学习问题 对偶攻击 侧信息 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2023.08.23 |
| 投稿时间：2021-04-05修订日期：2021-05-31 |
| 基金项目:密码科学技术国家重点实验室开放课题项目 |
|
| Dual Attack with Side Information |
|
BI Lei1, LU Xianhui1, LUO Junjie2, WANG Kunpeng1
|
| (1.SKLOIS,Institute of Information Engineering,CAS;2.Nanyang Technological University) |
| Abstract: |
| The Learning with Errors (LWE) problem[1] is the most widely used problem in lattice-based cryptography and has been widely used in constructing lattice-based schemes. The study of the hardness of LWE is essential to analyze the security of these schemes. The primal attack and dual attack are the most common and effective attacks in the concrete security analysis of LWE[2]. In addition to the attacks in the concrete security analysis, in 2020, Dachman-Soled, Ducas, Gong et al.[3] pioneered a framework of using the information from side channel in the concrete security analysis and implemented it on primal attack, but they did not consider dual attack. Recently, the results of the studies on hybrid dual attack[4-7] show that in many cases (hybrid) dual attack is more effective than primal attack, so it is an interesting open problem to study using side information in dual attack. In this paper, we study this problem. We give approaches to exploit side information in dual attack and analyze their effectiveness. Specifically, four types of side information are considered, and their effect on the dual attack is mainly on the volume of the lattice – when the volume of the lattice decreases, the attack becomes easier. Each type of side information has a different degree of influence on the volume of the lattice, and the specific changes of the lattice volume by different side information are also given in this paper under certain assumptions. Based on the changes in the lattice volume, the final impact on the effectiveness of dual attack can be analyzed. For instance, under the classical BKZ-core-SVP cost model, the integration of each perfect hint into embedded dual attack reduces the concrete security by about 0.3 bits. |
| Key words: Lattice Learning with errors problem Dual attack Side information |
