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

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

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

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