請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38395
標題: | 平行化最短格向量問題之極速列舉演算法 Extreme Enumeration on GPU and in Clouds |
作者: | Po-Chun Kuo 郭博鈞 |
指導教授: | 鄭振牟(Chen-Mou Cheng) |
關鍵字: | 格基密碼學,最短格向量問題,顯示晶片,雲端運算,列舉演算法,極速列舉演算法, Lattice,lattice-based cryptography,Shortest Vector Problem,GPU,Cloud Computing,Enumeration,Extreme Pruning, |
出版年 : | 2011 |
學位: | 碩士 |
摘要: | 廣受使用的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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38395 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 1.45 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。