請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38395
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 鄭振牟(Chen-Mou Cheng) | |
dc.contributor.author | Po-Chun Kuo | en |
dc.contributor.author | 郭博鈞 | zh_TW |
dc.date.accessioned | 2021-06-13T16:32:21Z | - |
dc.date.available | 2011-08-02 | |
dc.date.copyright | 2011-08-02 | |
dc.date.issued | 2011 | |
dc.date.submitted | 2011-07-19 | |
dc.identifier.citation | [AD97] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worstcase/
average-case equivalence. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, STOC '97, pages 284-293, New York, NY, USA, 1997. ACM. [Ajt96] M. Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, STOC '96, pages 99-108, New York, NY, USA, 1996. ACM. [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. [AKS01] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Annual ACM Symposium on Theory of Computing -STOC , pages 601-610, New York, NY, USA, 2001. ACM. [AR05] Dorit Aharonov and Oded Regev. Lattice problems in NP intersect coNP. J. ACM, 52(5):749-765, 2005. [BLR08] Johannes Buchmann, Richard Lindner, and Markus Rückert. Explicit hard instances of the shortest vector problem. In Johannes Buchmann and Jintai Ding, editors, PQCrypto, volume 5299 of Lecture Notes in Computer Science, pages 79-94. Springer, 2008. [CS97] Don Coppersmith and Adi Shamir. Lattice attacks on ntru. In EURO- CRYPT, pages 52-61, 1997. [DG04] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, USA, December 2004. [DHPS10] Jérémie Detrey, Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Accelerating lattice reduction with FPGAs. In LATINCRYPT, volume 6212 of LNCS, pages 124-143. Springer, 2010. [DS10] Özgür Dagdelen and Michael Schneider. Parallel enumeration of shortest lattice vectors. In Euro-Par, volume 6272 of LNCS, pages 211-222. Springer, 2010. [FP83] U. Fincke and Michael Pohst. A procedure for determining algebraic integers of given norm. In European Computer Algebra Conference, volume 162 of Lecture Notes in Computer Science, pages 194-202. Springer, 1983. [Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Annual ACM Symposium on Theory of Computing - STOC , pages 169-178. ACM, 2009. [GGH96] Collision-free hashing from lattice problems, 1996. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. oded@theory.lcs.mit.edu 10500 received July 26th, 1996. [GM03] Daniel Goldstein and Andrew Mayer. On the equidistribution of Hecke points. Forum Mathematicum 2003, 15:2, pages 165-189, 2003. [GN08] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Nigel P. Smart, editor, Eurocrypt, volume 4965 of Lecture Notes in Com- puter Science, pages 31-51. Springer, 2008. [GNR10] Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Advances in Cryptology - EURO- CRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 257 278. Springer, 2010. [Gol97] Public-key cryptosystems from lattice reduction problems. In CRYPTO, pages 112-131, 1997. [GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Annual ACM Symposium on Theory of Computing -STOC 2008, pages 197-206. ACM Press, 2008. [GS10] Nicolas Gama and Michael Schneider. SVP Challenge, 2010. available at http://www.latticechallenge.org/svp-challenge. [Her50] C. Hermite. Extraits de lettres de m. ch. hermite a m. jacobi sur di erents objects de lá théorie des nombres. Journal fur die reine und angewandte Mathematik, 1850:261-278, 1850. [HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ringbased public key cryptosystem. In ANTS, pages 267-288, 1998. [HSB+10] Jens Hermans, Michael Schneider, Johannes Buchmann, Frederik Vercauteren, and Bart Preneel. Parallel shortest lattice vector enumeration on graphics cards. In Africacrypt 2010, volume 6055 of Lecture Notes in Computer Science, pages 52-68. Springer, 2010. [Kan83] Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In Annual ACM Symposium on Theory of Computing -STOC 1983, pages 193-206. ACM Press, 1983. [KH10] David B. Kirk and Wen-mei Hwu. Programming Massively Parallel Pro- cessors: A Hands-on Approach. Morgan Kaufmann, 1 edition, February 2010. [KLPS11] T. Kleinjung, A.K. Lenstra, D. Page, and N.P. Smart. Using the cloud to determine key strengths. Cryptology ePrint Archive, Report 2011/254, 2011. http://eprint.iacr.org/. [KS01] Henrik Koy and Claus-Peter Schnorr. Segment lll-reduction of lattice bases. In Joseph H. Silverman, editor, CaLC, volume 2146 of Lecture Notes in Computer Science, pages 67-80. Springer, 2001. [KTX08] Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Concurrently secure identi cation schemes based on the worst-case hardness of lattice problems. In ASIACRYPT, pages 372 389, 2008. [Len83] H.W.jun. Lenstra. Integer programming with a xed number of variables. Math. Oper. Res., 8:538-548, 1983. [Len05] Arjen Lenstra. Key lengths. In Hossein Bidgoli, editor, Handbook of Information Security. Wiley, December 2005. [LLL82] Arjen Lenstra, Hendrik Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 4:515-534, 1982. [LM09] Vadim Lyubashevsky and Daniele Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In Shai Halevi, editor, Crypto, volume 5677 of Lecture Notes in Computer Science, pages 577-594. Springer, 2009. [LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. Swifft: A modest proposal for fft hashing. In FSE, pages 54-72, 2008. [MR07] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measure. SIAM Journal on Computing, 37(1):267-302, 2007. Preliminary version in FOCS 2004. [MV10a] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In STOC, pages 351-358. ACM, 2010. [MV10b] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In SODA 2010, pages 1468- 1480. ACM/SIAM, 2010. [Ngu99] Cryptanalysis of the goldreich-goldwasser-halevi cryptosystem from crypto '97. In CRYPTO, pages 288-304, 1999. [NS04] Phong Q. Nguyen and Damien Stehlé. Floating-Point LLL Revisited. Research Report RR-5387, INRIA, 2004. [NV08] P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. J. of Mathematical Cryptology, 2(2), 2008. [Pei08] A framework for efficient and composable oblivious transfer. In CRYPTO, volume 5157, pages 554-571, 2008. [PS08] Xavier Pujol and Damien Stehlé. Rigorous and e cient short lattice vectors enumeration. In Advances in Cryptology ASIACRYPT 2008, volume 5350 of Lecture Notes in Computer Science, pages 390 405. Springer, 2008. [PS09] Xavier Pujol and Damien Stehle. Solving the shortest lattice vector problem in time 22:465n. Cryptology ePrint Archive, Report 2009/605, 2009. http://eprint.iacr.org/. [Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84-93, 2005. [Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):1-40, 2009. [Reg10] Oded Regev. The learning with errors problem (invited survey). In IEEE Conference on Computational Complexity, pages 191-204, 2010. [Sch03] Claus-Peter Schnorr. Lattice reduction by random sampling and birthday methods. In STACS, pages 145-156, 2003. [SE94] Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming, 66:181-199, 1994. [SH95] Claus-Peter Schnorr and Horst Helmut Hörner. Attacking the chor-rivest cryptosystem by improved lattice reduction. In EUROCRYPT, volume 921 of LNCS, pages 1-12. Springer, 1995. [SHK] Michael Schneider, Jens Hermans, and Po-Chun Kuo. Shortest lattice vector enumeration on graphics cards, version 2.0. http://homes.esat. kuleuven.be/~jhermans/gpuenum/index.html. [Sho] Victor Shoup. Number theory library (NTL) for C++, version 5.5.2. http://www.shoup.net/ntl/. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38395 | - |
dc.description.abstract | 廣受使用的NTRU密碼系統和許多可証明安全性的格基密碼系統的安全性都直接和最短格向量問題有直接相關。於此研究中,我們改進數點解最短格向量問題之演算法,至今,經由這些改進,在解SVP的公開挑戰賽中我們分別拿下第一、二、三名的成績。
我們改進目前效率最高的極速列舉演算法,並分別經由MapReduce實作在雲端上和經由CUDA實作在顯示晶片上。藉由這兩個實作,可以價錢來評估一格基密碼系統的難度,意即,要花多少錢向雲端計算提供商租運算量去破解一格基密碼系統。 我們的實作使用8張nVidia顯卡即可在兩天內破解維度114,116的最短格向量問題;另外,我們也花費2300美金解出維度120的問題。 | zh_TW |
dc.description.abstract | The complexity of SVP (Shortest Vector Problem) is directly related to the security of NTRU and the provable level of security of many recently proposed lattice-based cryptosystems.
We integrate several recent algorithmic improvements for solving SVP and take rst, second, and third place repectively at dimension 120, 116, and 114 on the SVP Challenge Hall of Fame. Speci cally, our improvements to the recent Extreme Pruning in enumeration approach include a better set of pruning rules, code to take advantage of Clouds of commodity PCs (via the MapReduce framework), and the use of NVIDIA's Graphics Processing Units (GPUs). We may now reasonably estimate the cost of a wide range of SVPs in U.S. dollars, as rent paid to cloud-computing service providers, which is arguably a simpler and more practical measure of complexity. Our implementation allows us to fi nd a short vector at dimension 116 and 114 using 8 nVidia video cards in less than two days. As shown the price of security level, we spend 2300 U.S. dollar for renting machines from Amazon and solve SVP with dimension 120. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T16:32:21Z (GMT). No. of bitstreams: 1 ntu-100-R99921046-1.pdf: 1479981 bytes, checksum: cf5d825f386d31f0fbb1a217c18f573f (MD5) Previous issue date: 2011 | en |
dc.description.tableofcontents | Abstract i
1 Introduction 2 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Cloud Computing, Amazon EC2, and GPU . . . . . . . . . . . . . . . 5 1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Lattice Problem 10 2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Problem Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Related Cryptosystems and Related Problems . . . . . . . . . . . . . 12 3 Lattice Enumeration 14 3.1 Lattice Reduction Algorithm . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Enumeration using Extreme Pruning . . . . . . . . . . . . . . . . . . 16 4 Parallel, Variants and Analysis 20 4.1 Parallel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 BKZ with Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Bounding Function Selection . . . . . . . . . . . . . . . . . . . . . . . 22 5 Implementation 24 5.1 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Results 28 6.1 GPU Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.2 MapReduce Implementation . . . . . . . . . . . . . . . . . . . . . . . 32 6.3 Final Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7 Conclusion 35 | |
dc.language.iso | en | |
dc.title | 平行化最短格向量問題之極速列舉演算法 | zh_TW |
dc.title | Extreme Enumeration on GPU and in Clouds | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 楊柏因(Bo-Yin Yang),呂及人(Chi-Jen Lu),雷欽隆(Chin-Laung Lei),蘇炫榮(Hsuan-Jung Su) | |
dc.subject.keyword | 格基密碼學,最短格向量問題,顯示晶片,雲端運算,列舉演算法,極速列舉演算法, | zh_TW |
dc.subject.keyword | Lattice,lattice-based cryptography,Shortest Vector Problem,GPU,Cloud Computing,Enumeration,Extreme Pruning, | en |
dc.relation.page | 43 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2011-07-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 1.45 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。