CRYSTALS-Kyber不同參數下的失敗機率與安全性分析

Failure Probability and Security Analysis for Various Parameter Sets of CRYSTALS-Kyber

黃常勛(Chang-Hsun Huang)

指導教授 ： 陳君明

國立臺灣大學/理學院/數學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202103784

摘要

為了抵抗未來幾年內預期將出現的大規模量子電腦對現今公鑰密碼系統與數位簽章的威脅，美國國家標準暨技術研究院（National Institute of Standards and Technology）近年來推動足以抵抗量子電腦攻擊的新型密碼系統：後量子密碼學（post-quantum cryptography, PQC）的制定與標準化。其中CRYSTALS-Kyber是以晶格（lattice）為基礎的密鑰封裝機制（Key encapsulation mechanism）中，最被理論密碼學界看好的。CRYSTALS-Kyber算法的設計中，具有許多可以人為挑選的參數，設計者稱最後官方的參數選取，是為了平衡密鑰大小與安全強度，然而卻沒給出完整的論述與比較。在這篇論文中，我們將探討CRYSTALS-Kyber參數選取的合理性，研究不同的參數組對於密碼系統特性的影響，完整分析參數改變後對於公鑰大小、解密失敗率與安全強度的改變，並發掘出其他也可選用或可能更好的參數組。最後給出一個對這類晶格密碼系統的安全性分析的primal attack中，一個直接預測q型晶格BKZ約化後基底形狀的計算公式，使得在實作攻擊分析程式時有更佳的運算效率與更簡易的實作方式。

關鍵字

後量子密碼學 ； 晶格密碼學 ； 容錯學習問題 ； 模晶格 ； 密鑰封裝 ； 公鑰系統 ； 公鑰密碼學 ； 量子電腦

並列摘要

CRYSTALS-Kyber is an IND-CCA2-secure key-encapsulation mechanism based on the hardness of the learning-with-errors problem in module lattices. Besides the algorithm and design of Kyber itself, there are many parameters that can be chosen to result in a new variance of Kyber. Without further analysis, choosing these parameters as different values may seem somewhat equally reasonable. However, the specification documentation was lacking in the justification of the optimization of the parameters and only stated as a trade-off to balance the ciphertext size and security level. In this paper, we will explore the various parameter sets of Kyber and derive their features, including the failure probability of decryption, the ciphertext size, and the security level. Furthermore, we will give a new closed-form formula for predicting the shape of BKZ-$\beta$ reduced basis for a $q$-ary lattice used in the primal attack, which leads to the simpler implementation of the security analysis program.

並列關鍵字

post-quantum cryptography ； PQC ； key encapsulation mechanism ； KEM ； lattice ； CRYSTALS-Kyber ； Kyber ； module ； learning with errors ； MLWE ； primal attack ； security ； quantum

參考文獻

[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.