LWE问题及相关密码体制的分析

The Learning with Errors problem is a new hard mathematical problem. Under some specific range of parameters, there are (quantum) reductions between LWE problem and some of the most important computational problems on lattices. The LWE problem has been used for the design of many (possible) quantum-safe cryptosystems including the well-known fully homomorphic encryption schemes. This project is dedicated to the study of efficient algorithms for solving many variants of the LWE problem and cryptanalysis of several cryptosystems based on the LWE problem using classical and quantum techniques. Specifically, it addresses several directions: (i) efficient algorithms for solving the general LWE problem by combining learning algorithms and known algorithms; (ii) efficient algorithms for some variants of the general LWE problem such as the Ring-LWE problem using tools from algebraic number theory, and the selections of weak parameters of LWE problem; (iii) investigation into the complexity of the LWE problems with different error distributions using different definitions of statistical distance; (iv) devise new model for attacking LWE-based cryptosystems using known side channel attack techniques; (v) the constructions of cryptographic schemes enjoying some optimal properties using the geometric and algebraic aspects of the LWE problem; (vi) applying fast algorithms for solving LWE problem to the security analysis of known LWE-based cryptosystems.

LWE问题是新近提出的数学问题。在特定的参数范围内，LWE问题的困难性与格上经典困难问题困难性等价。LWE问题能用来设计包括全同态加密体制在内的多种抗量子攻击的密码体制。本课题拟分别利用经典和量子的工具研究各种LWE问题的快速计算方法，以及基于LWE问题的密码体制。具体包括下面几个方面：利用经典的数学工具、学习算法结合现有的计算方法，研究LWE问题的快速计算方法；利用代数数论的理论,研究特殊LWE问题的计算方法，寻找“弱”的LWE问题的参数选择；利用不同统计距离的定义,研究不同扰动的LWE问题的困难性；利用已有的侧信道攻击工具，研究基于LWE问题上的密码体制的新的攻击模型；利用LWE问题的代数、几何性质，研究基于LWE问题的单向函数，设计满足某些“最优”性质的密码体制；利用LWE问题的计算结果，分析基于LWE问题上密码体制的安全性。

称基于数学困难问题设计的抗量子计算机攻击的密码体制为后量子密码体制。目前能用来设计抗量子攻击的密码体制的数学困难问题有：基于格理论、椭圆曲线超奇异同源、编码、多变量、哈希函数。在2020年初，NIST公布了第三轮7个后量子密码算法标准的候选算法，其中有5个密码算法是基于格上困难问题设计的。基于格上困难问题密码算法的分析与设计成为当今密码领域最核心的研究课题。现有格密码算法主要基于下面三个问题设计：LWE问题、SIS问题和NTRU问题。利用理想格上的SIS 和LWE 问题设计的密码在实现效率和存储空间上有优势。. 本课题围绕抗量子攻击的密码算法的分析与设计及困难问题的计算等相关问题展开了系列的研究，主要的研究内容包括：基于抗量子数学困难问题的密码算法的分析与设计、数学困难问题的计算、基于量子密码算法的分析设计、对称密码的算法分析与设计等。通过估计一类黎曼zate函数的界，我们将可证明安全的基于 NTRU 的加密体制推广到任意分圆域上,新体制具有不受分圆域规模的限制，体制参数对明文空间依赖性小、解密错误率更低；基于抗量子的同源困难问题，我们设计双密钥公钥加密算法，并进一步模块化设计了 2 轮的认证密钥协商协议，与 NIST 的候选方案相比，我们的方案提供了认证性，是目前抗量子安全认证密钥交换协议中通信量最小的方案，为同等安全格方案的 1/3；我们研究广义Reed-Solomon码的深洞问题，基于Newton插值对广义Reed-Solomon码的深洞树给出了一个显式的刻画，应用期望深洞树的结论给出了一个限制和集的新结果；我们通过对参数的优化，在带有自同态的椭圆曲线情形改进了 Galbraith-Ruprai 算法的算法复杂度；我们提出了第一个新的无条件安全的多方量子委托方案，该方案是无条件隐藏和无条件绑定的。