請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80720完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳君明(Jiun-Ming Chen) | |
| dc.contributor.author | Chang-Hsun Huang | en |
| dc.contributor.author | 黃常勛 | zh_TW |
| dc.date.accessioned | 2022-11-24T03:14:02Z | - |
| dc.date.available | 2021-11-04 | |
| dc.date.available | 2022-11-24T03:14:02Z | - |
| dc.date.copyright | 2021-11-04 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-10-24 | |
| dc.identifier.citation | [AD21] Martin Albrecht and Léo Ducas. Lattice attacks on ntru and lwe: A history of refinements. Cryptology ePrint Archive, Report 2021/799, 2021. https://ia.cr/2021/799. [ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange—a new hope. In 25Th {USENIX} security symposium ({USENIX} security 16), pages 327–343, 2016. [AGVW17] Martin R Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected cost of solving usvp and applications to lwe. In International Conference on the Theory and Application of Cryptology and Information Security, pages 297–322. Springer, 2017. [Ajt98] Miklós Ajtai. The shortest vector problem in l2 is np-hard for randomized reductions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 10–19, 1998. [BDK + 18] Joppe Bos, Léo Ducas, EikeKiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals-kyber: a cca-secure module-lattice-based kem. In 2018 IEEE European Symposium on Security and Privacy (EuroS P), pages 353–367. IEEE, 2018. [BG14] Shi Bai and Steven D Galbraith. Lattice decoding attacks on binary lwe. In Australasian Conference on Information Security and Privacy, pages 322–337. Springer, 2014. [CN11] Yuanmi Chen and Phong Q Nguyen. Bkz 2.0: Better lattice security estimates. In International Conference on the Theory and Application of Cryptology and Information Security, pages 1–20. Springer, 2011. [GMSS99] Oded Goldreich, Daniele Micciancio, Shmuel Safra, and J-P Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters, 71(2): 55–61, 1999. 2.2.1 [HG07] Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against ntru. In Annual International Cryptology Conference, pages 150–169. Springer, 2007. [HPS11] Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Algorithms for the shortest and closest lattice vector problems. In International Conference on Coding and Cryptology, pages 159–190. Springer, 2011. [HPS14] Jeffrey Hoffstein, Jill Pipher, and Joseph H Silverman. An Introduction to Mathematical Cryptography. Springer, 2014. [Kan87] Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of operations research, 12(3):415–440, 1987. [Laa15] Thijs Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In Annual Cryptology Conference, pages 3–22. Springer, 2015. [LLL82] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematischeannalen, 261(ARTICLE):515–534, 1982. [LMVDP15] Thijs Laarhoven, Michele Mosca, and Joop Van De Pol. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 77(2):375–400, 2015. [LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Annual international conference on the theory and applications of cryptographic techniques, pages 1–23. Springer, 2010. [LS19] Vadim Lyubashevsky and Gregor Seiler. Nttru: truly fast ntru using ntt. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 180–201, 2019. [PV21] Eamonn W Postlethwaite and Fernando Virdia. On the success probability of solving unique svp via bkz. In Public Key Cryptography (1), pages 68–98, 2021. [Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC’05, page84–93, New York, NY, USA, 2005. Association for Computing Machinery. [SE94] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66(1):181–199, 1994. [Wun19] Thomas Wunderer. A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack. Journal of Mathematical Cryptology, 13(1):1–26, 2019. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80720 | - |
| dc.description.abstract | "為了抵抗未來幾年內預期將出現的大規模量子電腦對現今公鑰密碼系統與數位簽章的威脅，美國國家標準暨技術研究院（National Institute of Standards and Technology）近年來推動足以抵抗量子電腦攻擊的新型密碼系統：後量子密碼學（post-quantum cryptography, PQC）的制定與標準化。其中CRYSTALS-Kyber是以晶格（lattice）為基礎的密鑰封裝機制（Key encapsulation mechanism）中，最被理論密碼學界看好的。CRYSTALS-Kyber算法的設計中，具有許多可以人為挑選的參數，設計者稱最後官方的參數選取，是為了平衡密鑰大小與安全強度，然而卻沒給出完整的論述與比較。在這篇論文中，我們將探討CRYSTALS-Kyber參數選取的合理性，研究不同的參數組對於密碼系統特性的影響，完整分析參數改變後對於公鑰大小、解密失敗率與安全強度的改變，並發掘出其他也可選用或可能更好的參數組。最後給出一個對這類晶格密碼系統的安全性分析的primal attack中，一個直接預測q型晶格BKZ約化後基底形狀的計算公式，使得在實作攻擊分析程式時有更佳的運算效率與更簡易的實作方式。" | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-24T03:14:02Z (GMT). No. of bitstreams: 1 U0001-1610202122003700.pdf: 1593509 bytes, checksum: 39dfec4d21cbef516652d6a2ea37b312 (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | 摘要i Abstract ii 1 Introduction 1 2 Preliminaries 3 2.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Definiton of lattices . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Gram-Schmidt process . . . . . . . . . . . . . . . . . . . 3 2.1.3 Fundamental parallelepipeds . . . . . . . . . . . . . . . . 4 2.1.4 Determinant of lattices . . . . . . . . . . . . . . . . . . . 4 2.1.5 Minimum distance . . . . . . . . . . . . . . . . . . . . . 4 2.1.6 Minkowski's convex body theorem . . . . . . . . . . . . . 5 2.1.7 Hermite's Constant . . . . . . . . . . . . . . . . . . . . . 5 2.1.8 Gaussian Heuristic . . . . . . . . . . . . . . . . . . . . . 5 2.2 Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 SVP and CVP . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Lattice reduction . . . . . . . . . . . . . . . . . . . . . . 6 2.2.3 LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.4 BKZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.5 Geometric Series Assumption . . . . . . . . . . . . . . . 7 2.3 Learning with Errors . . . . . . . . . . . . . . . . . . . . . . . . 9 3 CRYSTALS-Kyber 10 3.1 Kyber Key-Encapsulation Mechanism . . . . . . . . . . . . . . . 10 3.2 Preliminaries and Notation . . . . . . . . . . . . . . . . . . . . . 10 3.3 High-Level View of the Algorithms . . . . . . . . . . . . . . . . 12 3.4 Low-Level Implementations of the Algorithms . . . . . . . . . . . 14 4 Variance of Kyber 19 4.1 Correctness Proof of Kyber . . . . . . . . . . . . . . . . . . . . . 19 4.2 The Algorithm to Compute the Failure Probability . . . . . . . . . 20 4.3 Analysis of the Different Parameter Sets of Kyber . . . . . . . . . 23 4.4 Analysis of the Different Parameter Sets of Kyber for Prime 7681 . 24 4.5 Analysis of the Different Parameter Sets of Kyber for Other Six Layers NTT Primes . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.6 Different Parameter Sets Suggestions for Kyber . . . . . . . . . . 25 5 Security analysis of Kyber 27 5.1 Primal Attack of the Lattice of Kyber . . . . . . . . . . . . . . . . 27 5.1.1 q-ary lattices . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1.2 Introduction to the primal attack . . . . . . . . . . . . . . 27 5.1.3 Previous work on modifying GSA for q-ary lattices . . . . 29 5.1.4 Modifying GSA for q-ary lattices . . . . . . . . . . . . . 30 5.2 Security Analysis of the Variant Parameter Sets of Kyber . . . . . 32 6 Conclusion 35 A Kyber Analysis for Prime 3329 39 A.1 Prime q=3329 and dimension k=2 . . . . . . . . . . . . . . . 39 A.2 Prime q=3329 and dimension k=3 . . . . . . . . . . . . . . . 46 A.3 Prime q=3329 and dimension k=4 . . . . . . . . . . . . . . . 51 B Kyber Analysis for Prime 7681 56 B.1 Prime q=7681 and dimension k=2 . . . . . . . . . . . . . . . 56 B.2 Prime q=7681 and dimension k=3 . . . . . . . . . . . . . . . 67 B.3 Prime q=7681 and dimension k=4 . . . . . . . . . . . . . . . 78 C Kyber Analysis for other Six Layer NTT Primes 88 C.1 Prime q=3457 . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 C.2 Prime q=4481 . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 C.3 Prime q=4993 . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 C.4 Prime q=6529 . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 C.5 Prime q=7297 . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 | |
| dc.language.iso | en | |
| dc.subject | 量子電腦 | zh_TW |
| dc.subject | 後量子密碼學 | zh_TW |
| dc.subject | 晶格密碼學 | zh_TW |
| dc.subject | 容錯學習問題 | zh_TW |
| dc.subject | 模晶格 | zh_TW |
| dc.subject | 密鑰封裝 | zh_TW |
| dc.subject | 公鑰系統 | zh_TW |
| dc.subject | 公鑰密碼學 | zh_TW |
| dc.subject | MLWE | en |
| dc.subject | KEM | en |
| dc.subject | lattice | en |
| dc.subject | CRYSTALS-Kyber | en |
| dc.subject | Kyber | en |
| dc.subject | module | en |
| dc.subject | learning with errors | en |
| dc.subject | primal attack | en |
| dc.subject | quantum | en |
| dc.subject | security | en |
| dc.subject | post-quantum cryptography | en |
| dc.subject | PQC | en |
| dc.subject | key encapsulation mechanism | en |
| dc.title | CRYSTALS-Kyber不同參數下的失敗機率與安全性分析 | zh_TW |
| dc.title | Failure Probability and Security Analysis for Various Parameter Sets of CRYSTALS-Kyber | en |
| dc.date.schoolyear | 109-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳君朋(Hsin-Tsai Liu),楊柏因(Chih-Yang Tseng),謝致仁,陳榮傑 | |
| dc.subject.keyword | 後量子密碼學,晶格密碼學,容錯學習問題,模晶格,密鑰封裝,公鑰系統,公鑰密碼學,量子電腦, | zh_TW |
| dc.subject.keyword | post-quantum cryptography,PQC,key encapsulation mechanism,KEM,lattice,CRYSTALS-Kyber,Kyber,module,learning with errors,MLWE,primal attack,security,quantum, | en |
| dc.relation.page | 97 | |
| dc.identifier.doi | 10.6342/NTU202103784 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2021-10-25 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-1610202122003700.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 1.56 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。