密码学中若干数学困难问题的量子算法研究

In recent years, quantum computing has made major breakthroughs both theoretically and experimentally. The study of quantum computing has had a profound effect on modern cryptography. On the one hand, fast quantum algorithms pose a threat to some cryptosystems and also lead to the rise of post-quantum cryptosystems research. On the other hand, research on quantum key distribution has brought new ideas to the exploration of unconditional security cryptosystems. Focusing on some mathematical difficulties in post-quantum cryptography, the project intends to study and design its quantum algorithms. The main research objectives include: based on dual quantum computing, designing elliptic curve isogeny problems more efficient sub-exponential time quantum algorithm and possible Polynomial-time quantum algorithm. Based on the Grover algorithm model, combined with the latest classical algorithms, a more efficient quantum algorithm for subsets and problems (ie, 0-1 integer knapsack problem) is designed, thus achieving further square root acceleration on the basis of classical algorithms. Based on the Grover algorithm model and the quantum walk algorithm model, an efficient quantum algorithm or sub-exponential algorithm for grid computing problems is proposed, and a general-purpose quantum algorithm for constructing NPC problems is explored. This project intends to make breakthroughs in the above-mentioned quantum algorithms for difficult mathematical problems, so as to better assess the potential threat of quantum algorithms to the post-quantum cryptosystem.

近年来，量子计算在理论和实验上都有较大的突破。量子计算的研究对现代密码学带来了深刻影响。一方面快速量子算法对一些密码体制带来威胁，也导致后量子密码研究的兴起；另一方面量子密钥分配的研究给探索无条件安全的密码体制带来了新思路。围绕后量子密码学中若干数学困难问题，本项目拟研究设计其量子算法，主要研究目标包括：基于对偶量子计算，设计椭圆曲线同种(isogeny)问题更高效的亚指数时间量子算法以及可能的多项式时间量子算法。基于Grover算法模型，结合最新的经典算法，设计子集和问题(即0-1整数背包问题)更加有效的量子算法，从而在经典算法的基础上达到进一步的平方根加速。基于Grover算法模型和量子游走算法模型，尝试设计格计算问题有效量子算法或亚指数时间算法，以及探索构造NPC问题的通用量子算法。本项目拟在上述数学困难问题的量子算法上有所突破，从而更好的评估量子算法对后量子密码系统的潜在威胁。

近年来，量子计算不断有新的进展，量子计算的研究对现代密码学带来了深刻影响。一方面规模越来越大的量子计算机的出现对一些公钥密码体制带来威胁，也导致后量子密码研究的兴起；另一方面量子密钥分配的研究给探索更多无条件安全的密码体制带来了可能。本项目围绕密码学中若干数学困难问题，探索其更有效的经典和量子求解算法，从而能更加准确的评估量子计算机及量子算法对现有密码系统以及后量子密码的潜在威胁。同时，本项目也探索和设计了更加安全和有效的量子密码方案。.具体地，本项目研究内容主要包括如下几方面：.(1)对现有Shor算法进行了深入研究和分析，基于椭圆曲线同种问题(isogeny)的特性，即是否可以转换成等价的求函数周期问题，判断出同种问题不存在多项式时间或亚指数时间的量子算法。确定了同种问题最有效的量子算法是经典与量子结合的搜索算法，其计算复杂度为指数时间。另外，基于同种问题是否能设计出安全的密码方案仍然是一大挑战。.(2)分析了Grover算法模型的特点，归纳其求解问题的适用场景。仔细分析了子集和问题的经典算法，特别是近年提出的改进算法，基于Grover算法模型，探索了子集和问题的量子算法。.(3)基于Grover算法模型及量子游走算法模型，探索了求解格最短向量及最近向量问题的量子算法。构造了NPC问题(3-SAT)的量子通用算法，从而达到在经典算法的基础上提供进一步的加速，能更加有效地评估量子算法对后量子密码的威胁。基于Grover算法模型，构造以及改进了Hash函数以及AES等经典密码的量子攻击算法，能更加有效地评估量子算法对后量子密码以及对称密码的威胁。.同时，本项目在以上研究的基础上，结合若干经典工具，设计了若干量子密码方案，并对安全性进行了系统分析。本项目的研究对于密码学数学困难问题可能存在的更加高效的量子破解算法做出了积极探索，能更加准确的评估量子算法对(后量子)密码系统的潜在威胁。