臺灣博碩士論文加值系統

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

Acknowledgment ii
Abstract(Chinese) iii
Abstract iv
Chpater 1 Introduction 1
1.1 Our Contribution 2
Chpater 2 Preliminaries 5
2.1 Lattice 5
2.2 The discrete Gaussian and the smoothing parameter 5
2.3 Behavior of √ln(1ε)/ηε(L∗) 8
2.4 Tail bounds 9
2.5 δ-net and the spectral norm 10
Chpater 3 Enumeration Algorithm and BDD oracle 12
3.1 Enumeration Algorithm 12
3.2 Solver to Bounded Decoding Distance 14
Chapter 4 Improvement on Enumeration in quantum 20
4.1 Bound for ∇fW(t)/fW(t) 21
4.2 Bound for ∇fW(t) and fW(t) 23
4.3 Concluding the Approximation Procedure 25
Chpater 5 Conclusion 29
Reference 29

[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.
Journal ofthe American Statistical Association.
[6] Paul Kirchner and Pierre-Alain Fouque.Time-memory trade-off for lattice enumeration in a ball. Cryptologye Print Archive,Report2016/222,2016.
[7] A.K.Lenstra,H.W.jun.Lenstra,and L aszloLov asz. Factoring polynomials with rational coefficients. Math. Ann.
[8] Daniele Micciancio and Chris Peikert. Trapdoors for lattices:Simpler,tighter, faster, smaller. Cryptologye Print Archive, Report2011/501,2011.
[9] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J.Comput.
[10] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In
Proceedings of the Forty-second ACM Symposiumon Theory of Computing, STOC''10, pages351
[11] P.Q.NguyenandT.Vidick.Sieve algorithms for the shortest vector problem are practical. J.of Mathematical Cryptology,2(2),2008.
[12] Oded Regev.New lattice-based cryptographic constructions. J. ACM, November2004.
[13] Oded Regev. On lattices,learning with errors, random linear codes, and cryptography.In Proceedings of the Thirty-seventh Annual ACM Symposiumon Theory of Computing, STOC''05,pages84.
[14] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, 2010.