量子演算法在最短晶格問題上的改良解

A more efficient quantum algorithm for solving the shortest vector problem

陳彥霖(Yanlin Chen)

指導教授 ： 郭斯彥

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201600976

摘要

最短晶格問題 最短晶格問題 (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.

並列關鍵字

lattice ； cryptography ； decryption ； quantum ； computing

參考文獻

[1] Divesh Aggarwal,Daniel Dadush,and Noah Stephens-Davidowitz.Solving the closest vector problem in $2^n$ time-the discrete gaussian strikes again! CoRR, abs/1504.01995, 2015.

[2] W.Banaszczyk.New bounds in some transference theorems in th egeometry of numbers.296(4):625{635,1993.

[3] D.Dadush,O.Regev,and N.Stephens-Davidowitz. On the Closest Vector Problem with a Distance Guarantee. ArXive-prints, September2014.

[4] Lov K.Grover. A Fast quantum mechanical algorithm for database search.1996.

[5] Wassily Hoefflding. Probability inequalities for sums of bounded random variables.