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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

图表清单

注释表

缩略词

第一章 绪论

1.1 研究背景及意义

1.2 研究现状

1.3 论文主要工作

第二章 量子计算与隐含子群问题概述

2.1 量子计算

2.2 基本量子逻辑门

2.3 Shor算法

2.4 隐含子群问题

2.5 本章总结

第三章 二面体群隐含子群问题量子算法研究

3.1 预备知识

3.2 Kuperberg算法量子线路设计

3.3 Kuperberg算法的改进

第四章 基于DHSP的SVP量子算法研究

4.1 基础知识

4.2 基于Kuperberg的SVP量子算法模型

4.3 基于Kuperberg的SVP量子算法

4.4 基于Kuperberg的SVP量子线路设计

4.5 本章总结

第五章 总结与展望

5.1 论文研究工作总结

5.2 进一步的工作展望

致谢

在学期间的研究成果及发表的学术论文