大規模量子計算的發展對傳統公鑰基礎架構造成了根本性的威脅。儘管晶格
密碼學（Lattice-based cryptography）是後量子安全的主要候選者，但現有基於最短整數解（SIS）或容錯學習（LWE）問題的盲簽章機制，卻因必須依賴拒絕採樣（Rejection sampling）而受到嚴重阻礙。在盲簽章的環境下，這項技術會導致協議頻繁重啟，進而造成極高的通訊開銷與運算延遲。本論文提出一個候選的基於晶格同構問題（Lattice Isomorphism Problem, LIP）的盲簽章架構。透過利用 LIP 框架中「卓越晶格（Remarkable lattices）」的獨特幾何性質，我們解決了現有架構固有的低效問題。我們的主要貢獻包括：（1）晶格選擇的多樣性：允許使用具備高效率解碼演算法的較簡單晶格結構，以提升系統吞吐量；（2）二次型（Quadratic forms）表示法的應用：使簽章與驗證方程避免 SIS/LWE 式的 Zq 模算術，並以二次型距離與整數簽章向量表示。，並消除複雜的矩陣分解，從而簡化執行過程；以及（3）無拒絕重啟的隨機簽署流程：徹底消除了拒絕採樣的需求，確保了最少的兩步（2-pass）互動，並在 128 位元安全級別下實現了僅約 0.56 KB 的極小簽章大小。最後，我們在隨機預言機模型（ROM）下證明本機制滿足統計盲性（Statistical blindness），並透過將最終簽章層化約至 DvW22 的 EUF-CMA 安全雜湊後簽章機制，論證本機制滿足單次不可偽造性（One-more unforgeability）。

The advancement of large-scale quantum computing poses a fundamental threat to classical public-key infrastructures. While lattice-based cryptography is a leading candidate for post-quantum security, existing blind signature schemes based on the Short Integer Solution (SIS) or Learning With Errors (LWE) problems are significantly hindered by the necessity of rejection sampling. In a blind setting, this technique leads to frequent protocol restarts, resulting in high communication overhead and computational latency.

To the best of our knowledge, this thesis presents a candidate blind-signature framework based on the Lattice Isomorphism Problem (LIP). By leveraging the unique geometric properties of ``remarkable lattice'' within the LIP framework, we address the inherent inefficiencies of existing constructions. Our main contributions include: (1) versatility in lattice selection, allowing the use of simpler lattice structures with efficient decoding algorithms to enhance throughput; (2) the utilization of quadratic form representations, which simplifies protocol execution by simplifies the signing and verification equations by avoiding SIS/LWE-style Z_q-module arithmetic and using quadratic-form distances with integer signature vectors. and eliminating complex matrix decompositions; and (3) a rejection-free randomized signing process that completely removes the need for rejection sampling, ensuring a minimal 2-pass interaction while achieving a final signature estimate of approximately 0.56 KB under the chosen coordinate-encoding parameters. Finally, we provide a formal security analysis in the Random Oracle Model (ROM), proving statistical blindness and establishing one-more unforgeability by reducing the final signature layer to the EUF-CMA-secure DvW22 hash-then-sign scheme.

Bibliography
[ABB20] N. A. Alkadri, R. E. Bansarkhani, and J. Buchmann, “BLAZE: practical lattice-
based blind signatures for privacy-preserving applications,” in Financial Cryp-
tography and Data Security (FC 2020), Springer, 2020, pp. 484–502 (cit. pp. 2–
4, 37, 38).
[Ajt96] M. Ajtai, “Generating hard instances of lattice problems,” in Proceedings of
the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC),
ACM, 1996, pp. 1–9 (cit. pp. 2, 3, 7).
[BLN+23] W. Beullens, V. Lyubashevsky, N. K. Nguyen, and G. Seiler, “Lattice-based
blind signatures: Short, efficient, and round-optimal,” in Proceedings of the
2023 ACM SIGSAC Conference on Computer and Communications Security
(CCS 2023), 2023, pp. 1–15 (cit. pp. 2, 3, 37).
[BR93] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for
designing efficient protocols,” in Proceedings of the 1st ACM Conference on
Computer and Communications Security (CCS), ACM, 1993, pp. 62–73 (cit.
pp. 1, 14).
[CFN88] D. Chaum, A. Fiat, and M. Naor, “Untraceable electronic cash,” in Advances
in Cryptology — CRYPTO ’88, Springer, 1988, pp. 319–327 (cit. p. 1).
[Cha83] D. Chaum, “Blind signatures for untraceable payments,” in Advances in Cryp-
tology — CRYPTO ’82, Plenum Press, 1983, pp. 199–203 (cit. pp. 1, 13, 19,
27).
[CN11] Y. Chen and P. Q. Nguyen, “BKZ 2.0, better lattice security estimates,” in
Advances in Cryptology — ASIACRYPT 2011, Springer, 2011, pp. 1–20 (cit.
p. 35).
43
Bibliography 44
[CS99] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Grundlehren
der mathematischen Wissenschaften), 3rd. Springer, 1999, vol. 290 (cit. p. 4).
[DvW22] L. Ducas and W. van Woerden, “On the lattice isomorphism problem, quadratic
forms, remarkable lattices, and cryptography,” in Advances in Cryptology —
EUROCRYPT 2022, ser. Lecture Notes in Computer Science, vol. 13277, Springer,
2022, pp. 3–33 (cit. pp. 2–4, 8, 9, 11, 12, 15, 19, 20, 22, 26, 31, 32, 40).
[GMR89] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of in-
teractive proof systems,” SIAM Journal on Computing, vol. 18, no. 1, pp. 186–
208, 1989 (cit. p. 13).
[GPV08] C. Gentry, C. Peikert, and V. Vaikuntanathan, “Trapdoors for hard lattices and
new cryptographic constructions,” in Proceedings of the 40th annual ACM
symposium on Theory of computing (STOC), 2008, pp. 197–206 (cit. pp. 2,
10, 20).
[Gro96] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of
Computing (STOC), ACM, 1996, pp. 212–219 (cit. p. 2).
[HR14] I. Haviv and O. Regev, “On the lattice isomorphism problem,” in Proceedings
of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), SIAM, 2014, pp. 391–404 (cit. pp. 2–4, 8, 9, 19, 40).
[LPR10] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning with
errors over rings,” in Advances in Cryptology — EUROCRYPT 2010, Springer,
2010, pp. 1–23 (cit. pp. 2, 41).
[Lyu09] V. Lyubashevsky, “Fiat-shamir with aborts: Applications to lattice and factoring-
based signatures,” in Advances in Cryptology — ASIACRYPT 2009, Springer,
2009, pp. 598–616 (cit. pp. 2–4).
[MR04] D. Micciancio and O. Regev, “Worst-case to average-case reductions based
on gaussian measures,” in Proceedings of the 45th Annual IEEE Symposium
on Foundations of Computer Science (FOCS), IEEE Computer Society, 2004,
pp. 372–381 (cit. pp. 7, 10, 16, 35).
Bibliography 45
[Nat16] National Institute of Standards and Technology (NIST), “Post-quantum cryp-
tography standardization,” U.S. Department of Commerce, Tech. Rep., 2016
(cit. p. 2).
[Nat94] National Institute of Standards and Technology (NIST), “FIPS PUB 186: Dig-
ital Signature Standard (DSS),” U.S. Department of Commerce, Tech. Rep.,
1994 (cit. p. 1).
[Ped91] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable
secret sharing,” in Advances in Cryptology — CRYPTO ’91, Springer, 1991,
pp. 129–140 (cit. pp. 14, 20, 32).
[Pei16] C. Peikert, “A decade of lattice cryptography,” Foundations and Trends® in
Theoretical Computer Science, vol. 10, no. 4, pp. 283–424, 2016 (cit. pp. 2, 7,
35).
[PS00] D. Pointcheval and J. Stern, “Security arguments for digital signatures and
blind signatures,” Journal of Cryptology, vol. 13, no. 3, pp. 361–396, 2000
(cit. pp. 1, 13, 19, 27, 28, 30).
[Reg05] O. Regev, “On lattices, learning with errors, random linear codes, and cryp-
tography,” in Proceedings of the Thirty-Seventh Annual ACM Symposium on
Theory of Computing (STOC), ACM, 2005, pp. 84–93 (cit. pp. 2, 3).
[RSA78] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital sig-
natures and public-key cryptosystems,” Communications of the ACM, vol. 21,
no. 2, pp. 120–126, 1978 (cit. p. 1).
[Rüc10] M. Rückert, “Lattice-based blind signatures,” in Advances in Cryptology —
ASIACRYPT 2010, ser. Lecture Notes in Computer Science, vol. 6477, Springer,
2010, pp. 413–430 (cit. pp. 2–4, 37, 38).
[Sch91] C. Schnorr, “Efficient signature generation by smart cards,” Journal of Cryp-
tology, vol. 4, no. 3, pp. 161–174, 1991 (cit. p. 1).
[Sho94] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and
factoring,” in Proceedings 35th Annual Symposium on Foundations of Com-
puter Science (FOCS), IEEE, 1994, pp. 124–134 (cit. p. 2).