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

Abstract

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