請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50692完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭斯彥(Sy-Yen Kuo) | |
| dc.contributor.author | Yanlin Chen | en |
| dc.contributor.author | 陳彥霖 | zh_TW |
| dc.date.accessioned | 2021-06-15T12:52:57Z | - |
| dc.date.available | 2016-07-26 | |
| dc.date.copyright | 2016-07-26 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-07-19 | |
| dc.identifier.citation | [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. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50692 | - |
| dc.description.abstract | 最短晶格問題 最短晶格問題 (SVP)一直是晶格密碼學上重要的問題之；不論在古典 還是量子上，他都有著指數時間難解的保證。迄今最好的古典提供了一個O(2^n)的解，而這篇論文我們提出了一個O(3^{n/2})的量子演算法的去解決最短晶格問題。
我們主要貢獻首先是優化最短晶格與平滑參數(smoothing parameter) 之間的不等式，接著利用Grover亂序查找的量子演算法，讓我們可以在 讓我們可以在 O(3^{n/2})內，以極高的成功率找到晶格最短向量。 迄今，即使在量子計算上破解最短晶格問題仍然需要O(2^{1.79n})，我們提供了幾乎開根號的結果去解決這一個難題。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T12:52:57Z (GMT). No. of bitstreams: 1 ntu-105-R03921034-1.pdf: 707325 bytes, checksum: 9e9f04b5129a92035d6427c2b46f5583 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 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 | |
| dc.language.iso | en | |
| dc.title | 量子演算法在最短晶格問題上的改良解 | zh_TW |
| dc.title | A more efficient quantum algorithm for solving the shortest vector problem | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 顏嗣鈞(Hsu-Chun Yen),雷欽隆(Chin-Laung Lei),陳英一(Ing-Yi Chen),陳俊良(Jiann-Liang Chen) | |
| dc.subject.keyword | 晶格,密碼學,破密,量子演算法, | zh_TW |
| dc.subject.keyword | lattice,cryptography,decryption,quantum,computing, | en |
| dc.relation.page | 30 | |
| dc.identifier.doi | 10.6342/NTU201600976 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-07-19 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 目前未授權公開取用 | 690.75 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。