請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52370完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 鄭振牟(Chen-Mou Cheng) | |
| dc.contributor.author | Wen-Ding Li | en |
| dc.contributor.author | 李文鼎 | zh_TW |
| dc.date.accessioned | 2021-06-15T16:13:01Z | - |
| dc.date.available | 2015-08-20 | |
| dc.date.copyright | 2015-08-20 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2015-08-18 | |
| dc.identifier.citation | [Ajt98] Miklós Ajtai. The shortest vector problem in l2 is NP-hard for randomized reductions (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 10–19, New York, NY, USA, 1998. ACM.
[CL] Jung Hee Cheon and Changmin Lee. Cryptanalysis of the multilinear map on the ideal lattices. [DM13] Daniel Dadush and Daniele Micciancio. Algorithms for the densest sub- lattice problem. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1103–1122. SIAM, 2013. [GM03] Daniel Goldstein and Andrew Mayer. On the equidistribution of hecke points. In Forum Mathematicum, volume 15, pages 165–190. Berlin; New York: De Gruyter, c1989-, 2003. [GN08] Nicolas Gama and Phong Q Nguyen. Predicting lattice reduction. In Advances in Cryptology–EUROCRYPT 2008, pages 31–51. Springer, 2008. [LLL82] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Fac- toring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. [LN13] Mingjie Liu and Phong Q Nguyen. Solving bdd by enumeration: An update. In Topics in Cryptology–CT-RSA 2013, pages 293–309. Springer, 2013. [MR09] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post-Quantum Cryptography, pages 147–191. Springer Berlin Heidelberg, 2009. [NS06] Phong Q. Nguyen and Damien Stehlé. LLL on the average. In Algorithmic Number Theory, pages 238–256. Springer, 2006. [PS13] Thomas Plantard and Michael Schneider. Creating a challenge for ideal lattices. IACR Cryptology ePrint Archive, 2013:39, 2013. [Reg06] Oded Regev. Lattice-based cryptography. In Advances in Cryptology- CRYPTO 2006, pages 131–141. Springer, 2006. [Sch11] Patrick Schmidt. Fully homomorphic encryption: Overview and cryptanal- ysis. PhD thesis, Diploma Thesis, University of Dortmund, Dortmund, Germany, 2011. [SVP] Svp challenge. http://www.latticechallenge.org/svp-challenge/. [vdPS13] Joop van de Pol and Nigel P Smart. Estimating key sizes for high dimen- sional lattice-based systems. In Cryptography and Coding, pages 290–303. Springer, 2013. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52370 | - |
| dc.description.abstract | 格規約是目前被認為是對最短向量問題最實際的演算法，因此估計格規約實際上能產生的短向量長度是重要的問題。子格攻擊是在格的行列式值較小時，將輸入經過處理再使用格規約，能產生比直接使用格規約得到的向量更短的方法。本文將對子格攻擊做一完整的介紹以及用實驗驗證結果。 | zh_TW |
| dc.description.abstract | Lattice basis reduction is a common and perhaps the most practical method today to solve the approximate shortest vector problem. It is important to estimate the length of the short vectors output by lattice basis reduction. However, accurate estimation is difficult to obtain, and people often rely on empirical heuristics. Based on the asymptotic behavior of the lengths of the short vectors, there is a well-known sublattice attack if the determinant of the lattice is relatively small. Here we provide detailed exposition of the cause of the sublattice attack and verify with experimentation on Goldstein-Mayer lattices. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T16:13:01Z (GMT). No. of bitstreams: 1 ntu-104-R02921047-1.pdf: 960082 bytes, checksum: 744405a5128a99c765e76f4984145856 (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Preliminaries ............................... 1 1.1.1 Definition ............................. 1 1.1.2 Determinant ............................ 2 1.1.3 Orthogonalization..................... 2 1.1.4 Shortest Vector Problem.............. 2 1.1.5 Lattice Reduction Algorithm........ 3 2 Shortest Vector Problems 4 2.1 Problem Statement......................... 4 2.1.1 Successive Minima ...................... 4 2.1.2 Shortest Vector Problem............... 4 2.2 Problem Property............................. 5 3 Lattice Reduction 6 3.1 LLL .............................................. 6 3.1.1 ReducedBasus .......................... 6 3.1.2 Algorithm.................................. 6 3.1.3 Property.................................... 8 3.2 BKZ............................................... 9 4 Sublattice Attack 10 4.1 Heuristic Estimation ...................... 10 4.2 Sublattice Attack ............................ 11 4.3 Lattice with Small Determinant ......... 12 4.4 Heuristic Estimation for GM Lattice with Small Determinant ... 15 4.5 SublatticeAttackforGeneralLattice ....... 18 5 Conclusion 20 | |
| dc.language.iso | en | |
| dc.title | 子格攻擊的反思 | zh_TW |
| dc.title | Reflections on the Sublattice Attack | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 103-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 洪維志(Wei-Chih Hong),楊柏因(Bo-Yin Yang),陳君明(Jiun-Ming Chen) | |
| dc.subject.keyword | 格基,格規約,最短格向量問題,子格攻擊, | zh_TW |
| dc.subject.keyword | Lattice,Lattice Basis Reduction,Shortest Vector Problem,Sublattice Attack, | en |
| dc.relation.page | 22 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2015-08-18 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf 目前未授權公開取用 | 937.58 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。