請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63994
標題: | 邁向實際的格密碼學 Towards Practical Lattice-based Cryptography |
作者: | Po-Chun Kuo 郭博鈞 |
指導教授: | 鄭振牟(Chen-Mou Cheng) |
關鍵字: | 密碼學,後量子密碼學,格密碼學,金鑰交換,平行計算,最短格向量問題,最短理想格向量問題,顯示晶片,雲端運算,格列舉演算法,格極速列舉演算法,格篩演算法,格高斯篩演算法,硬體實作,現場可程式化邏輯閘陣列, Cryptography,Lattice,lattice-based cryptography,Shortest Vector Problem,LWE,RLWE,GPU,Cloud Computing,Enumeration,Extreme Pruning,Sieve algorithm,Gauss Sieve,hardware implementation,FPGA, |
出版年 : | 2020 |
學位: | 博士 |
摘要: | 在近年,量子電腦的技術蓬勃發展,其潛在計算能力威脅了古典密碼學的系統安全性;因此,後量子密碼學應運而生,旨在發展可抵抗量子電腦攻擊的密碼系統。格密碼學是後量子密碼學中最有潛力的一個子領域,而本論文探討格密碼系統的中兩個最重要的面向:安全與效率。對於一個格密碼系統,其安全性基於格問題,而最常見的格問題是—最短格向量問題,和它的變形—最短理想格向量問題。在本文中,我們分別對這兩個問題進行計算量的估計;也就是對格密碼系統的安全參數給出更好的下界。更仔細地說,我們分別以GPU實作格列舉演算法(lattice enumeration algorithm)和格篩演算法(lattice sieve algorithm),我們的實作中,都達到了該演算法的最高效率實作的記錄,因此,可以更合理的推估格問題的實際複雜度,以提供格密碼系統在參數選取時的依據。另一方面,在密碼系統效率的角度上,我們提出第一個硬體實作的格金鑰交換系統,瞭解在實務上格密碼系統的效率和成本。更詳細地說,我們實作於Usenix Security 2016由Alkim, Ducas, Pöpplemann和Schwabe提出的Newhope格金鑰交換系統,並達到目前時間面積乘積最佳之格金鑰交換系統硬體實作。因此,在可接受的加密時間內,可推知合理之實際可用的格密碼系統參數上界。 The threat of the quantum computer is a huge problem for modern cryptography, and post-quantum cryptography aims to develop the cryptosystem, which may potentially resist attacks from quantum computers. Lattice-based cryptography is one of the most promising areas of post-quantum cryptography. In this thesis, we focus on the two aspects of lattice-based cryptography: security and efficiency, which are the most important properties for a practical cryptosystem. The security of lattice-based cryptosystems is based on lattice problems. The shortest vector problem is the central problem of lattice problems, and its variant, the shortest vector problem over the ideal lattice, also is one of the most important problems for a lattice-based cryptosystem. We estimate the respective hardness for these two problems, that is, we give a concrete lower bound for the security parameters of the lattice-based cryptosystem. More precisely, we improve and implement the lattice enumeration algorithm for the shortest vector problem and the sieve algorithm for the shortest vector problem over the ideal lattice, respectively. In our results, we achieve the best efficiency for the implementation of these two algorithms. Thus, we can estimate the computation cost for these two problems in order to provide a way to select the parameters of lattice-based cryptosystems. On the other hand, with regard to efficiency, we begin by executing the first hardware implementation of lattice-based key exchange protocol—Newhope, which is proposed by Alkim, Ducas, Pöpplemann, and Schwabe in Usenix Security 2016. We achieve the best time-area product implementation of post-quantum key exchanges in a state-of-the-art environment. Therefore, our results provide a way to estimate the upper bound of the security parameters of lattice-based cryptosystems within an acceptable encryption time. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63994 |
DOI: | 10.6342/NTU202000678 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-109-1.pdf 目前未授權公開取用 | 8.2 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。