Reductions from module lattices to free module lattices, and application to dequantizing module-LLL
Reductions from module lattices to free module lattices, and application to dequantizing module-LLL
复制标题
DOI：
10.1007/978-3-031-38554-4_27
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Gabrielle De Micheli;Daniele Micciancio;Alice Pellet-Mary;N. Tran
中科院分区：
文献类型：
--
作者：
Gabrielle De Micheli;Daniele Micciancio;Alice Pellet-Mary;N. Tran
在本文中，我们证明，在解决密码算法问题时（并且当模块的秩至少为 2 时），自由模块（即承认基础的模块）并不弱于任意模块。更准确地说，我们表明，对于密码学中使用的三个算法问题，即最短向量问题、Hermite 最短向量问题和最接近向量问题的变体，在任何阶 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} 的模块中解决问题都会有所减少\usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 2$$\end{document} 解决相同rankn的任何freemodule中的问题。作为一个应用，我们证明这可以用于对 Lee 等人提出的模块格子的 LLL 算法进行反量化。 （Asiacrypt 2019）。
In this article, we give evidence that free modules (i.e., modules which admit a basis) are no weaker than arbitrary modules, when it comes to solving cryptographic algorithmic problems (and when the rank of the module is at least 2). More precisely, we show that for three algorithmic problems used in cryptography, namely the shortest vector problem, the Hermite shortest vector problem and a variant of the closest vector problem, there is a reduction from solving the problem in any module of rank \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 2$$\end{document} to solving the problem in anyfreemodule of the same rankn. As an application, we show that this can be used to dequantize the LLL algorithm for module lattices presented by Lee et al. (Asiacrypt 2019).