電機資訊學院: 電機工程學研究所指導教授: 郭斯彥陳彥霖Chen, YanlinYanlinChen2017-03-062018-07-062017-03-062018-07-062016http://ntur.lib.ntu.edu.tw//handle/246246/276327最短晶格問題 最短晶格問題 (SVP)一直是晶格密碼學上重要的問題之；不論在古典 還是量子上，他都有著指數時間難解的保證。迄今最好的古典提供了一個O(2^n)的解，而這篇論文我們提出了一個O(3^{n/2})的量子演算法的去解決最短晶格問題。 我們主要貢獻首先是優化最短晶格與平滑參數(smoothing parameter) 之間的不等式，接著利用Grover亂序查找的量子演算法，讓我們可以在 讓我們可以在 O(3^{n/2})內，以極高的成功率找到晶格最短向量。 迄今，即使在量子計算上破解最短晶格問題仍然需要O(2^{1.79n})，我們提供了幾乎開根號的結果去解決這一個難題。SVP is a well known NP hard problem both for classical and quantum. The best algorithm for SVP takes O(2^n) in classical and quantum computing does not helps. In this paper we demonstrate a quantum algorithm which solves SVP in time O(3^{n/2}) and in space O(2^{n/2}). Our main contribution includes two parts: we first tighten the inequality of smoothing parameter and λ1 such that we have a better oracle for bounded decoding distance(BDD) problem. Then we apply Grover search on the Enumeration algorithm by Paul to solve SVP in time O(3^{n/2}). To date, the best quantum algorithm for SVP still costs O(2^{1.79n}) in time, we provide an almost square better result for it.707325 bytesapplication/pdf論文公開時間: 2016/7/26論文使用權限: 同意有償授權(權利金給回饋學校)晶格密碼學破密量子演算法latticecryptographydecryptionquantumcomputingthesis10.6342/NTU201600976http://ntur.lib.ntu.edu.tw/bitstream/246246/276327/1/ntu-105-R03921034-1.pdf