基于量子计算的二面体群隐含子群问题研究

作     者：孙静 

作者单位：南京航空航天大学 

学位级别：硕士

导师姓名：袁家斌

授予年度：2012年

学科分类：11[军事学] 1105[军事学-军队指挥学] 07[理学] 0839[工学-网络空间安全] 08[工学] 070201[理学-理论物理] 110505[军事学-密码学] 110503[军事学-军事通信学] 0702[理学-物理学] 

主      题：量子计算 量子线路 隐含子群问题 DHSP SVP 

摘      要：基于格问题的公钥密码体制是目前国际密码学界公认的四种抗量子计算公钥密码体制之一，其较好的抗量子性以及实现效率，使其成为设计新型公钥密码体制的热点。目前针对最短向量问题的分析均采用经典计算的格基规约方法，无法真正评估其对抗量子计算攻击的能力，因此寻求新的量子计算分析的方法，开展量子密码格最短向量问题的安全性研究十分必要。 Shor算法可以转化为隐含子群问题的讨论，掀开了量子计算的研究热潮。Regev指出最短向量问题可以转化为二面体群隐含子群问题的研究，拓宽了量子计算的应用领域，但二面体群隐含子群问题是量子计算领域中的研究难点。 论文着重研究了Kuperberg的二面体群隐含子群问题的量子算法及其在格最短向量问题上的量子计算模型。在具体工作中，本文指出Kuperberg算法中酉变换f设计的不足，指出在实际情况中酉变换f实质是一个周期函数，引入可交换群隐含子群问题的量子算法解决此缺陷，在此基础上给出了具体解决方案，并对其进行性能分析，改进算法保持了原Kuperberg算法的良好性能。以Kuperberg算法为模型框架，结合Regev的转化思想，提出基于Kuperberg算法的SVP量子算法模型，对该算法模型进行了性能分析，并将该算法和经典的格基规约算法、量子格基规约算法进行比较，对比表明本文算法在近似因子和时间复杂度方面达到了初步平衡。同时，通过自顶而下逐步细化的方式给出了Kuperberg算法和基于Kuperberg的SVP量子算法的具体量子线路实现，为将来的仿真提供一定的理论基础，也可作为量子计算机芯片集成设计的依据。