在現場可程式化邏輯閘陣列上的二鋰結晶數位簽章系統硬體實作

A Hardware Implementation of CRYSTALS-Dilithium Signature Scheme on FPGA

賴亭融(Ting-Rong Lai)

指導教授 ： 黃俊郎

共同指導教授 ： 楊柏因 ； 鄭振牟(Chen-Mou Cheng)

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202102059

摘要

隨著我們逐漸步入量子的時代，學者們開始對於量子電腦的研究產生越來越多的興趣。隨著量子電腦的發展，我們現存的密碼學系統，多數是建立在整數分解與離散對數的難題假設下，將無法抵抗量子電腦的攻擊。為了更進一步的標準化後量子密碼學系統，美國國家標準暨技術研究院(NIST)在2017年發出了後量子密碼學系統的公開徵選。CRYSTALS-Dilithium，一個晶格密碼系統中的數位簽章系統，於2020年通過第三輪的選拔，成為第三輪的七個候選人之一。
本論文中，我們提出了一個於現場可程式化邏輯閘陣列(FPGA)上的CRYSTALS-Dilithium數位簽章系統實作。最為關鍵的，我們提出了一個精簡的數論轉換(NTT)和模餘運算。藉由仔細的設計硬體架構，達到降低硬體資源的需求，我們的實作在公密鑰生產(key generation)上只需要8,696個LUT和8,753個FF；在簽章(signing)中只需要13,680個LUT和11,946個FF；在驗章(verifying)上只需要10,643個LUT和10,124個FF。

關鍵字

後量子密碼學 ； CRYSTALS-Dilithium ； FPGA

並列摘要

As we are pathing into the quantum era, quantum computers are gaining more and more interest from researchers. With the development of quantum computers, current cryptography systems, which mostly rely on the hardness of integer factorization or computing discrete logarithms, are unable to handle attacks from quantum computers. To further standardize post-quantum cryptography systems, the National Institute of Standards and Technology (NIST) has launched a public evaluation process of post-quantum cryptography (PQC) in 2017. In 2020, CRYSTALS-Dilithium, a lattice-based digital signature scheme, has been chosen as one of the finalists in the third round of the process.
In this work, we implement the CRYSTALS-Dilithium signature scheme on Field-Programmable Gate Arrays (FPGAs). The main contribution is a compact Number-Theoretic Transform (NTT) module with simplified reduction operation. With carefully designed hardware architecture to minimize the requirement of hardware resources, our work only requires 8,696 LUTs and 8,753 FFs in key generation, 13,680 LUTs and 11,946 FFs in signing process, and 10,643 LUTs and 10,124 FFs in verifying.

並列關鍵字

Post-quantum Cryptography ； CRYSTALS-Dilithium ； FPGA

參考文獻

[1] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Review, vol. 41, no. 2, pp. 303–332, 1999.

[2] Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D., “CRYSTALS-Dilithium – Submission to round 2 of the NIST post-quantum project.” Specification document (part of the round 2 submission package). 2019-03-30

[3] Zhang, N., Yang, B., Chen, C., Yin, S., Wei, S., Liu, L., “Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT,” IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(2), 49-72

[4] Basu, K., Soni, D., Nabeel, M., Karri, R. “Nist post-quantum cryptography-a hardware evaluation study.” IACR Cryptol. ePrint Arch. 2019, 47 (2019)

[5] Soni, D., Basu, K., Nabeel, M., Karri, R., “A hardware evaluation study of nist post-quantum cryptographic signature schemes,” Second PQC Standardization Conference. NIST (2019)