計畫成員 : 楊柏因、鐘楷閔、王柏堯、倪儒本
量子計算是一項很有前途的新技術，它有可能在許多領域對我們的現代社會產生顛覆性的變化。 然而，量子計算帶來的變化之一是負面的: 配備強大的大型量子電腦的攻擊者將能夠破解當今世界上使用的主要公鑰密碼系統，我們需要準備應對它對當今密碼學的破壞性影響。
因此自 2017 年以來，美國國家標準與技術研究院 (NIST) 一直在進行新世代密碼算法的標準化的競賽，以防止未來被大型量子電腦攻擊。 能抵抗量子計算的新一代密碼學稱為後量子密碼學 (PQC)。 我們的團隊參與了這一競賽，參與了四項提案：Classic McEliece、Gui、NTRU Prime、Rainbow 和 SPHINCS+。 在 2022 年第三輪標準化進程結束時，NIST 選擇了一種密鑰建立演算法（CRYSTALS-Kyber）和三種數位簽章演算法（CRYSTALS-Dilithium、Falcon 和我們提案的 SPHINCS+）進行標準化，四種其他的密鑰建立演算法進入第四輪。 其中三種算法 （包括我們提案的 Classic McEliece）仍在被考慮中。
為了進一步使數位簽章演算法能多樣化，NIST 在 2023 年 6 月又徵求了新的數位簽章演算法提案。我們參與了 MEDS、UOV 和 WAVE 三個方案。 簽章方案 UOV 基於 MP 問題的難度（多元多項式系統的求解），是一個非常有前途的候選方案，具有悠久的密碼學傳統和眾所周知的安全特性。 WAVE 和 MEDS 方案大體上屬於基於編碼的密碼系統，相當年輕。 然而，它們提供了一些吸引人的特性，例如小的公鑰大小和高效的簽章操作。 我們是 MEDS 和 UOV 的主要實作者，並實作了 WAVE 的部分。
這三個方案在 NIST PQC 標準化競賽中前進時，我們將繼續參與它們的旅程。 此外，我們計劃致力於軟體和硬體的高效、安全和可驗證的實作。以及 NIST 和 PQC 社群考慮的其他系統的軟硬體協同設計。我們的工作涵蓋整個密碼學生態系統，從系統的設計、密碼分析和驗證開始，再到實作和優化，再到實作的安全分析和強化，以及它們與協議和 IT 系統的整合。
我們在這個主題上在國際密碼學會的密碼學硬體與嵌入式系統彙刊 (IACR Transactions on Cryptographic Hardware and Embedded Systems, TCHES) 已發表了多篇論文。例如，僅在 2022 年，我們就為 TCHES 貢獻了五篇文章。 IACR TCHES 被廣泛認為是密碼學實作和應用密碼學的最佳出版場所，我們的出版物包括與世界領先的 IIS 形式方法研究群協作的可驗證快速實作。
後量子算法實作
基於晶格的 PQC 系統系列以在計算成本以及密鑰和密文各自的簽章大小方面特別高效而著稱。 基於晶格的系統的主要作用結構是多項式環，其上最耗時的運算是乘法和除法。 我們為這些操作的快速實現的開發做出了重大貢獻，我們是使用數論變換（NTT，一種快速傅立葉變換 - FFT 的變形）來計算多項式環上的乘法的先驅，特別是在這些多項式環並非是為 NTT 設計時在 ARM 的各種嵌入式或正常系統的 CPU 實作。 我們主要的技術包括完整和不完整的 FTT（或 NTT，使用 Cooley-Tukey 和 Gentleman-Sande 蝴蝶）、Good-Thomas FFT、Rader's FFT、Schönhage-Strassen FFT 和 Nussbaumer FFT。
基於編碼的 PQC 系統系列通常在計算成本或密鑰和數據大小方面更昂貴。 然而該領域本身可以追溯到 70 年代後期 (即使一直有新的系統被提出) 因此早期經過多年密碼學家審查的編碼密碼系統 Classic McEliece 被認為是非常安全和可靠的。 我們一直致力於在硬體和軟體中有效實作基於編碼的系統，我們一直在研究這些系統的旁通道安全性，因為要在密碼學上使用，一個系統有效率和理論強度是不夠的——它還需要更安全地實作，使得攻擊者無法從旁通道中獲取秘密，不管他們量測耗時、耗能或電磁輻射。
UOV 等多元 PQC 系統系列提供了非常短的簽章和高效的驗證時間——但通常公鑰相當大。 雖然該系列的許多系統在過去都被破解，但 UOV 被認為非常可靠，並且該系統被廣泛認為是 NIST PQC 簽章系統補充輪競賽的領先者。 隨著 UOV 系統的提案，我們正在為各種平台提供優化的實現，包括 x86 CPU、一般和嵌入式 ARM 實作和 FPGA 硬體設計。 除了 UOV 提案的設計和實作工作外，多年來，我們一直致力於評估解決多元多項式系統的潛在難題，並且我們擁有多項在計算機和 FPGA 集群上解決此類系統的公共記錄 .
基於雜湊函數的 PQC 系統家族不提供加密系統，僅提供簽章系統。 我們提案的 SPHINCS+ 總結了長期研究中最著名的實踐。 雖然具有非常小的公鑰，但基於散列的簽章系統具有很大的簽章大小。 它們有兩種變體——有狀態系統（例如 XMSS 和 LMS）已經廣泛使用了一段時間，而無狀態系統（例如 SPHINCS+）。 由於密鑰生成和簽章的成本相對較高，我們對如何在記憶體受限的嵌入式設備中有效地實作這些系統以及如何使用硬體加速器提高其性能進行了研究。
NIST PQC 補充輪競賽的參與
UOV：大部分實作不平衡油醋（UOV）簽章系統的工作都是在台灣進行的。 對於 ARM Cortex-M4 和 Intel/AMD x86-64 實作，我們總結並重現了我們早期在相關 PQC 系統 Rainbow 上的工作。 我們為 ARM Neon 和 FPGA 平台提供了新的實作。
MEDS：矩陣等價數字簽章 (MEDS) 簽章系統基於 Fiat-Shamir 構造，只需要對矩陣進行相對簡單的運算，例如乘法、求逆和高斯消元法。 對於該系統的參考實作，我們以直接、等時的方式實作了所有操作。 現在接下來的步驟是為 SIMD CPU 和該系統的硬體實作提供優化的實作。
WAVE：WAVE 提案是一種基於編碼的雜湊函數和簽章系統。 簽章者需要藉助一些秘密知識來執行解決解碼問題的艱鉅任務。 WAVE 的簽章非常短——但公鑰非常大。 目前，只有 WAVE 的參考實作，我們將為各種平台上的優化實作做出貢獻。
經過驗證的後量子密碼學
我們的研究小組率先與本所優秀的形式驗證研究群合作，研究後量子密碼學的 NTT 部件的形式驗證。 我們正在推廣和增強 CryptoLine 工具鏈，這是一套分別使用解 SAT 工具和計算機代數系統（Computer Algebra System，CAS）處理算術和邏輯驗證問題的工具和機制。
通過我們的工作，我們致力於研究和開發經過驗證、高效且安全的 PQC 系統實作，從而為未來的安全數位通訊做出貢獻。