Estimated Cost for Solving Generalized Learning with Errors Problem via Embedding Techniques
Estimated Cost for Solving Generalized Learning with Errors Problem via Embedding Techniques
复制标题
通过嵌入技术解决广义学习错误问题的估计成本
DOI：
10.1007/978-3-319-97916-8_6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Takagi Tsuyoshi
中科院分区：
文献类型：
--
作者：
Wang Weiyao;Wang Yuntao;Takayasu Atsushi;Takagi Tsuyoshi
估计解决误差学习（LWE）问题的计算成本是基于格的密码学实践中不可或缺的研究课题。为此，通常采用嵌入方法。该技术首先通过嵌入 LWE 实例来构造基础矩阵。在这个阶段，Kannan 和 Bai-Galbraith 的嵌入被认为是分别对于标准 LWE 和具有秘密向量 in 和 的二进制 LWE 最有效的方法。事实上，这两种方法对于足够多的 LWE 样本都适用。嵌入阶段之后，求解基矩阵所跨越的晶格中的唯一最短向量问题 (uSVP) 即可求解 LWE。最近，已经提出了几种基于格的方案，其秘密向量具有特殊分布，例如小元素和/或稀疏向量，以实现有效的实现。在本文中，为了捕获此类设置以及更多信息，我们研究了一般设置中的 LWE 问题。我们分析了 LWE 问题，其秘密向量是从任意分布中采样的。此外，我们还研究了样本数量受到限制时的问题。我们相信我们的工作可以让人们对 LWE 的硬度有更全面的了解。此外，我们提出了一种半扭曲嵌入，其中包含现有的两种嵌入方法作为特殊情况。该提案使我们能够以通用方式分析 LWE 的硬度，有时还提供改进的攻击。
Estimating for the computational cost of solvinglearning with errors (LWE)problem is an indispensable research topic to the lattice-based cryptography in practice. For this purpose, theembeddingapproach is usually employed. The technique first constructs a basis matrix by embedding an LWE instance. At this stage, Kannan’s and Bai-Galbraith’s embeddings are believed to be the most efficient approaches for the standard and the binary LWE with secret vectors inand, respectively. Indeed, both methods work well with sufficiently many LWE samples. After the embedding phase, solving the unique shortest vector problem (uSVP) in the lattice spanned by the basis matrix results in solving the LWE. Recently, there are several lattice-based schemes whose secret vectors have special distributions, e.g., small elements and/or sparse vectors, have been proposed to realize efficient implementations. In this paper, to capture such settings and more, we study the LWE problem in a general setting. We analyze the LWE problem whose secret vectors are sampled from arbitrary distributions. Furthermore, we also study the problem when the number of samples is restricted. We believe that our work provides more general understanding of the hardness of LWE. Moreover, we propose ahalf-twisted embeddingthat contains the existing two embedding methods as special cases. This proposal enables us to analyze the hardness of LWE in a generic manner and sometimes provides improved attacks.
影响因子：
1.6
作者：
Albrecht, Martin R.;Cid, Carlos;Perret, Ludovic
通讯作者：
Perret, Ludovic