隨著量子計算技術的持續發展，建立於因式分解與離散對數等數論困難假設之上的傳統公鑰密碼系統，預期將在具備量子計算能力的攻擊者面前逐步喪失其安全性。為因應此一潛在威脅，後量子密碼學（Post-Quantum Cryptography, PQC）致力於設計在量子攻擊模型下仍被認為安全的密碼機制，並已在數位簽章等關鍵應用領域取得顯著研究成果。然而，現有後量子簽章方案多集中於傳統公鑰基礎設施（Public Key Infrastructure, PKI）架構之下，對於其他公鑰管理模型的研究仍相對有限。

在實際部署環境中，PKI 架構往往伴隨憑證發行、撤銷與管理所帶來的系統複雜度與營運成本；相對地，身分為基礎的簽章（Identity-Based Signature, IBS）雖能簡化公鑰管理流程，卻存在金鑰託管（key escrow）之固有風險。免憑證公鑰密碼學（Certificateless Public Key Cryptography, CL-PKC）作為折衷方案，雖可同時降低憑證管理負擔並避免金鑰託管問題，然而其在後量子設定下之具體建構仍具挑戰性，特別是對於基於結構化代數機制之密碼系統而言。

相較之下，基於錯誤更正碼的後量子密碼體系因其長期的安全分析歷史與對量子攻擊的天然抵抗能力，被視為極具潛力的替代方向。然而，此類 code-based 簽章方案通常依賴高度結構化之陷門解碼機制，使其難以直接適用於需額外金鑰生成或信任模型限制之密碼架構。因此，現有相關研究多集中於 PKI 架構，對於如何在不破壞其結構特性的前提下延伸至其他公鑰管理模型，仍有待進一步探討。

基於上述觀察，本論文探討後量子情境下之憑證式簽章（Certificate-Based Signature, CBS）設計，並提出一個以 Wave 簽章為基礎之後量子憑證式簽章方案。該方案以 Wave-PSA 簽章架構為基礎，採用 generalized $(U,U+V)$ codes 作為底層結構，以支援高效之陷門解碼。在系統設計上，使用者獨立產生其簽章金鑰對，而憑證機構則利用相同之 Wave 簽章機制對使用者身分與公開金鑰之綁定關係進行認證，從而在不涉及金鑰生成的情況下完成憑證發行。

在簽章與驗證流程方面，本方案延續 Wave-PSA 之 hash-and-sign 架構，並結合 Full-Domain Hashing 與 rejection sampling 技術，以確保簽章輸出之統計分佈不洩漏任何關於陷門結構的資訊。驗證過程僅需進行線性一致性與權重條件檢查，無需進行任何解碼運算，因而具備良好的驗證效率。

在安全性分析方面，本論文於隨機預言模型下，採用憑證式簽章之標準安全模型，並同時考慮 Type-I（外部攻擊者）與 Type-II（惡意憑證機構）攻擊者。透過歸約分析可證明，若底層 Wave 簽章方案在 EUF-CMA 模型下為安全，則所提出之憑證式簽章方案在多使用者存在性不可偽造（MU-EUF-CMA）模型下亦為安全，其安全性可歸約至 Decoding One-Out-of-Many（DOOM）問題之困難性。

綜合而言，本論文之主要貢獻在於提出一個具可證安全性的後量子憑證式簽章方案，並將基於錯誤更正碼之 Wave 簽章架構成功延伸至憑證式密碼模型，為後量子密碼學在非純 PKI 架構下之簽章設計提供一個兼具理論基礎與實務可行性的研究方向。

With the continuous advancement of quantum computing technologies, traditional public-key cryptographic systems based on number-theoretic hardness assumptions, such as integer factorization and discrete logarithms, are expected to become insecure against quantum-capable adversaries. To address this potential threat, post-quantum cryptography (PQC) aims to develop cryptographic mechanisms that remain secure in the presence of quantum attacks, and significant progress has been made in fundamental applications such as digital signatures. However, most existing post-quantum signature schemes are developed within the traditional Public Key Infrastructure (PKI) framework, while alternative public-key management paradigms remain relatively underexplored.

In practical deployments, PKI-based systems often incur considerable certificate management overhead and system complexity. In contrast, Identity-Based Signature (IBS) schemes simplify public-key management but inherently suffer from the key escrow problem. Certificateless Public Key Cryptography (CL-PKC), proposed as a compromise, reduces certificate management while avoiding key escrow, yet its application to post-quantum settings—particularly for structured cryptographic primitives—remains challenging.

Among post-quantum approaches, code-based cryptography is considered a promising candidate due to its long-standing security record and inherent resistance to quantum attacks. Nevertheless, existing code-based signature schemes typically rely on highly structured trapdoor decoding mechanisms, making them difficult to adapt to cryptographic models that impose additional constraints on key generation or trust assumptions. As a result, most code-based signature constructions are confined to the conventional PKI setting.

Motivated by these observations, this thesis investigates certificate-based signatures (CBS) in the post-quantum, code-based setting. We propose a post-quantum certificate-based signature scheme constructed from the Wave-PSA framework, referred to as the \emph{Certificate-Based Wave signature scheme}. In the proposed design, users independently generate their own signing key pairs, while a certification authority certifies the binding between user identities and public keys using the same Wave signature mechanism. This design preserves the structural properties of code-based signatures while avoiding key escrow and maintaining a clear separation between user key generation and certification.

The proposed scheme follows the hash-and-sign paradigm of Wave-PSA and incorporates Full-Domain Hashing and rejection sampling to ensure that the statistical distribution of signatures does not reveal information about the underlying trapdoor. Signature verification requires only linear consistency and weight checks with respect to public parity-check matrices, without performing any decoding operations, thereby achieving efficient verification.

From a security perspective, the scheme is analyzed under the standard security model for certificate-based signatures, considering both Type-I (external adversaries) and Type-II (malicious certification authorities). In the random oracle model, we show that the proposed scheme achieves existential unforgeability under adaptive chosen-message attacks in the multi-user setting (MU-EUF-CMA), and its security can be reduced to the EUF-CMA security of the underlying Wave signature scheme, which is in turn based on the hardness of the Decoding One-Out-of-Many (DOOM) problem.

Overall, this thesis presents a provably secure post-quantum certificate-based signature scheme and demonstrates how Wave-based code-based signatures can be systematically extended beyond the conventional PKI framework. The proposed construction provides a theoretically sound and practically viable approach for deploying structured post-quantum signatures in certificate-based environments.

[1] P. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134.
[2] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ser. STOC ’96, Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219.
[3] A. Shamir, “Identity-based cryptosystems and signature schemes,” in Advances in Cryptology, G. R. Blakley and D. Chaum, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 1985, pp. 47–53.
[4] S. S. Al-Riyami and K. G. Paterson, “Certificateless public key cryptography,” Advances in Cryptology – ASIACRYPT 2003, pp. 452–473, 2003.
[5] M. Tian and L. Huang, “Certificateless and certificate-based signatures from lattices,” Security and Communication Networks, vol. 8, no. 8, pp. 1575–1586, 2015. eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/sec.1105.
[6] Y.-F. Tseng, C.-I. Fan, and C.-W. Chen, “Top-level secure certificateless signature scheme in the standard model,” IEEE Systems Journal, vol. 13, no. 3, pp. 2763–2774, 2019.
[7] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich, “Wave: A new family of trapdoor one-way preimage sampleable functions based on codes,” in Advances in Cryptology – ASIACRYPT 2019, S. D. Galbraith and S. Moriai, Eds., Cham: Springer International Publishing, 2019, pp. 21–51.71 72 Bibliography
[8] R. J. McEliece, “A public-key cryptosystem based on algebraic coding theory,” Jet Propulsion Laboratory, Tech. Rep. DSN Progress Report 42–44, 1978, https://tda.jpl.nasa.gov/progress_report/42-44/44N.PDF, pp. 114–116.
[9] D. Galindo, J. Herranz, and E. Kiltz, “On the generic construction of identity-based signatures with additional properties,” in Advances in Cryptology – ASIACRYPT 2006, X. Lai and K. Chen, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 178–193.
[10] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” in CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3-5, 1993, D. E. Denning, R. Pyle, R. Ganesan, R. S. Sandhu, and V. Ashby, Eds., ACM, 1993, pp. 62–73.
[11] J.-S. Coron, “On the exact security of full domain hash,” in Advances in Cryptology — CRYPTO 2000, M. Bellare, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 229–235.
[12] V. Lyubashevsky, “Fiat-shamir with aborts: Applications to lattice and factoring-based signatures,” in Advances in Cryptology – ASIACRYPT 2009, M. Matsui, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 598–616.
[13] S. Goldwasser, S. Micali, and R. L. Rivest, “A digital signature scheme secure against adaptive chosen message attack**this research was supported by nsf grant mcs-80-06938, an ibm/mit faculty development award, and darpa contract n00014-85-k-0125.:Extended abstract,” in Discrete Algorithms and Complexity, D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, Eds., Academic Press, 1987, pp. 287–310.
[14] D. J. Bernstein, T. Lange, and C. Peters, “Attacking and defending the mceliece cryptosystem,” Post-Quantum Cryptography, pp. 31–46, 2008.
[15] R. Overbeck and N. Sendrier, “Code-based cryptography,” in Post-Quantum Cryptography, D. J. Bernstein, J. Buchmann, and E. Dahmen, Eds. Berlin, Heidelberg:Springer Berlin Heidelberg, 2009, pp. 95–145.
Bibliography 73
[16] E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (corresp.),” IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384–386, 1978.
[17] N. T. Courtois, M. Finiasz, and N. Sendrier, “How to achieve a mceliece-based digital signature scheme,” in Advances in Cryptology — ASIACRYPT 2001, C. Boyd, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 157–174.
[18] A. Becker, A. Joux, A. May, and A. Meurer, “Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding,” in Advances in Cryptology – EUROCRYPT 2012, D. Pointcheval and T. Johansson, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 520–536.
[19] N. Sendrier, “Decoding one out of many,” in Post-Quantum Cryptography, B.-Y. Yang, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 51–67.
[20] K. Hashimoto, W. Ogata, and T. Tomita, Tight reduction for generic construction of certificateless signature and its instantiation from DDH assumption, Cryptology ePrint Archive, Paper 2019/1367, 2019.
[21] L. Ducas, E. Kiltz, T. Lepoint, et al., “Crystals-dilithium: A lattice-based digital signature scheme,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 1, pp. 238–268, Feb. 2018.