請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50692
標題: | 量子演算法在最短晶格問題上的改良解 A more efficient quantum algorithm for solving the shortest vector problem |
作者: | Yanlin Chen 陳彥霖 |
指導教授: | 郭斯彥(Sy-Yen Kuo) |
關鍵字: | 晶格,密碼學,破密,量子演算法, lattice,cryptography,decryption,quantum,computing, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 最短晶格問題 最短晶格問題 (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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50692 |
DOI: | 10.6342/NTU201600976 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 690.75 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。