A Trace Map Attack Against Special Ring-LWE Samples
A Trace Map Attack Against Special Ring-LWE Samples
复制标题
DOI：
10.1007/978-3-030-85987-9_1
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yasuhiko Ikematsu;Satoshi Nakamura;Masaya Yasuda
中科院分区：
文献类型：
--
作者：
Yasuhiko Ikematsu;Satoshi Nakamura;Masaya Yasuda
带错学习（LWE）问题是支撑现代格密码安全性的难题之一。Ring-LWE是分圆域上整数环上LWE的类似形式，它提供了有效的密码体制。本文利用分圆域上整数环上的迹映射给出了环LWE的密码分析，而不需要对其他结构格问题进行任何简化。由于它映射到一个较小的程度的环，跟踪映射攻击预计能够降低环LWE的硬度。然而，轨迹映射不一定将环LWE样本变换为具有共同秘密的较小环上的样本。我们给出了一个充分必要条件，环LWE样本对的迹映射攻击适用。我们称这样一对样本为特殊样本。我们证明了如何有效地跟踪映射攻击可以解决环LWE时，一个特殊的样本对。具体来说，我们比较块大小的BKZ Korkine-Zolotarev（BKZ）算法所需的解决环LWE在跟踪图攻击和标准的攻击。此外，我们讨论了随机环LWE样本的迹映射攻击的可行性，以评估迹映射攻击如何在实际方面对基于环LWE的密码系统造成威胁。
The learning with errors (LWE) problem is one of the hard problems supporting the security of modern lattice-based cryptography. Ring-LWE is the analog of LWE over the ring of integers of a cyclotomic field, and it has provided efficient cryptosystems. In this paper, we give cryptanalysis against ring-LWE using the trace map over the ring of integers of a cyclotomic field, without using any reduction to other structured lattice problems. Since it maps to a ring of a smaller degree, a trace map attack is expected to be able to decrease the hardness of ring-LWE. However, the trace map does not necessarily transform ring-LWE samples to samples over the smaller ring with a common secret. We give a sufficient and necessary condition on a pair of ring-LWE samples for which the trace map attack is applicable. We call such a pair of samplesspecial. We demonstrate how efficiently the trace map attack can solve ring-LWE when a special pair of samples is given. Specifically, we compare blocksizes of the Blockwise Korkine-Zolotarev (BKZ) algorithm required for solving ring-LWE in the trace map attack and a standard attack. Moreover, we discuss the (in)feasibility of the trace map attack for random ring-LWE samples to evaluate how the trace map attack can give a threat against ring-LWE-based cryptosystems on a practical side.