臺灣大學: 電機工程學研究所鄭振牟郭博鈞Kuo, Po-ChunPo-ChunKuo2013-03-272018-07-062013-03-272018-07-062011http://ntur.lib.ntu.edu.tw//handle/246246/254006廣受使用的NTRU密碼系統和許多可証明安全性的格基密碼系統的安全性都直接和最短格向量問題有直接相關。於此研究中，我們改進數點解最短格向量問題之演算法，至今，經由這些改進，在解SVP的公開挑戰賽中我們分別拿下第一、二、三名的成績。 我們改進目前效率最高的極速列舉演算法，並分別經由MapReduce實作在雲端上和經由CUDA實作在顯示晶片上。藉由這兩個實作，可以價錢來評估一格基密碼系統的難度，意即，要花多少錢向雲端計算提供商租運算量去破解一格基密碼系統。 我們的實作使用8張nVidia顯卡即可在兩天內破解維度114,116的最短格向量問題；另外，我們也花費2300美金解出維度120的問題。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.1479981 bytesapplication/pdfen-US格基密碼學最短格向量問題顯示晶片雲端運算列舉演算法極速列舉演算法Latticelattice-based cryptographyShortest Vector ProblemGPUCloud ComputingEnumerationExtreme Pruningthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/254006/1/ntu-100-R99921046-1.pdf