基于量子計算的二面體群隱含子群問題研究.pdf

1、基于格問題的公鑰密碼體制是目前國際密碼學界公認的四種抗量子計算公鑰密碼體制之一，其較好的抗量子性以及實現(xiàn)效率，使其成為設計新型公鑰密碼體制的熱點。目前針對最短向量問題的分析均采用經(jīng)典計算的格基規(guī)約方法，無法真正評估其對抗量子計算攻擊的能力，因此尋求新的量子計算分析的方法，開展量子密碼格最短向量問題的安全性研究十分必要。
　　Shor算法可以轉(zhuǎn)化為隱含子群問題的討論，掀開了量子計算的研究熱潮。Regev指出最短向量問題可以轉(zhuǎn)化為二面

2、體群隱含子群問題的研究，拓寬了量子計算的應用領域，但二面體群隱含子群問題是量子計算領域中的研究難點。
　　論文著重研究了Kuperberg的二面體群隱含子群問題的量子算法及其在格最短向量問題上的量子計算模型。在具體工作中，本文指出Kuperberg算法中酉變換f設計的不足，指出在實際情況中酉變換f實質(zhì)是一個周期函數(shù)，引入可交換群隱含子群問題的量子算法解決此缺陷，在此基礎上給出了具體解決方案，并對其進行性能分析，改進算法保持了原Ku

3、perberg算法的良好性能。以Kuperberg算法為模型框架，結(jié)合Regev的轉(zhuǎn)化思想，提出基于Kuperberg算法的SVP量子算法模型，對該算法模型進行了性能分析，并將該算法和經(jīng)典的格基規(guī)約算法、量子格基規(guī)約算法進行比較，對比表明本文算法在近似因子和時間復雜度方面達到了初步平衡。同時，通過自頂而下逐步細化的方式給出了Kuperberg算法和基于Kuperberg的SVP量子算法的具體量子線路實現(xiàn)，為將來的仿真提供一定的理論基礎，