几类密码方案的格分析优化技术

Homomorphic encryption schemes can solve the confidentiality problem of data and operations entrusted to the third party. Leakage-resilient encryption schemes are designed for resisting side channel attacks which threaten the security of the original cryptosystems. Nonlinear pseudo random-number generators are a kind of important generators. Homomorphic encryption schemes, leakage-resilient encryption schemes and nonlinear pseudo-random number generators are the current hot topics of cryptography. This research project is targeted to analyze the security of these three classes of cryptosystems and study lattice-based cryptanalysis about them. By utilizing the relevant theories and methods of linearization technique and variable substitutions, etc, we propose the optimized technique of lattice analysis and hopefully obtain a method of lattice analysis with low complexity. The main research contents are as follows: 1) study the optimized technique of lattice analysis of homomorphic encryption schemes based on the approximate common divisor problem and other relevant problems, 2) study the optimized technique of lattice analysis of leakage-resilient encryption schemes whose security can be reduced into solving the hidden number problem or its variants, 3) study the optimized technique of lattice analysis of the security on the inversive generator which has inner connection with the modular inversion hidden number problem, 4) study the selection of security parameters about these three classes of cryptosystems. This research project provides guidance on the design of cryptosystems. It also has important theoretical and practical significance on promoting the development of the optimized technique of lattice analysis and applying this technique to more areas.

同态加密方案可解决数据及操作委托给第三方时的保密问题；泄漏容忍加密方案是由于侧信道攻击对原密码方案安全性的威胁而设计的；非线性伪随机数生成器是一类重要的生成器。同态加密方案、泄漏容忍加密方案、非线性随机数生成器是密码学目前的研究热点。本课题以分析这三类密码方案的安全性为目标，研究它们的基于格的分析方法，结合线性化技术、变量替换等相关理论和方法提出格分析优化技术，期望得到低复杂度的格分析方法。主要研究内容包括：1）研究基于近似公因子问题及相关问题的同态加密方案的格分析优化技术；2）研究安全性可转化成求解隐藏数问题及变种的泄漏容忍加密方案的格分析优化技术； 3）研究与模逆隐藏数问题有内在联系的逆生成器的格分析优化技术； 4）研究这三类密码方案安全参数的选取。本课题的研究对于密码方案的设计提出指导性意见，对于推动格分析优化技术的发展以及将该技术应用到更多的领域具有重要的理论和现实意义。

格分析方法是公钥密码分析中的一类重要攻击方法。它可在多项式时间内求解多项式系统的小根。本项目研究格分析方法的优化技术在几类密码方案中的应用。具体来说，本项目将该技术用于以下方面：1. 分析非线性随机数生成器、泄漏容忍加密方案、同态加密方案及RSA等安全性；2. 降低求解相关核心数学困难问题的计算复杂度。 在本项目的研究过程中，我们发展出4种优化的技术。利用这些优化方法我们得到了如下重要结果：1) 将逆同余伪随机数生成器的秘密种子恢复问题与泄露容忍方案基于的模逆隐藏数困难问题求解问题转化为求解同一类多项式方程系统的小根问题，然后利用我们提出的基于线性组合选取多项式的优化技术，将逆同余伪随机数生成器的安全界从p的1/2次方改进到p的1/3次方，这里p是密码方案中的模数。最近我们利用该优化技术改进了椭圆曲线密钥交换协议的比特安全性结果。此外，我们给出更巧妙的线性组合方式得到模逆隐藏数困难问题的更好攻击结果。2）利用基于两次格基约化的优化技术，改进了经典的多素数Phi隐藏困难假设的计算复杂度结果。此外，利用该优化技术我们也改进了Dual RSA方案的安全性分析。3）项目组与日本学者合作提出了基于变量替换的优化技术，将EUROCRYPT 2017中的CRT-RSA方案小解密指数结果N的0.091次方改进为N的0.122次方，这里N表示RSA模数。该结果是RSA密码分析领域的一个里程碑。4) 利用基于线性化方法的优化技术，对一个基于中国剩余定理构造的群密钥协议实施了唯密文攻击。该攻击可以在仅知道密文的情况下恢复相应的明文, 而无需访问任何组成员的秘密解密密钥, 即使在只有两个组成员的情况下也是如此。本项目的研究对于推动格分析优化技术的发展以及将提出的各类优化技术应用到相关研究领域具有重要的研究意义。