數位簽章可提供訊息來源的真實性與內容的完整性，但一般數位簽章會使簽署者得知被簽署的訊息。$1$-out-of-$n$ 模糊簽章允許接收者從公開訊息集合 $M$ 中選擇一個訊息並取得其有效簽章，同時不向簽署者揭露所選擇的元素。許多早期模糊簽章構造需要簽署者處理與整個訊息集合相關的簽署資料，因此其通訊量會隨著集合大小增加。

本論文首先形式化限制訊息安全性（constrained-message security），要求針對集合 $M$ 進行的簽署互動，不得使接收者取得集合外訊息的有效簽章。在此基礎上，本論文提出共用承諾（shared-commitment）與分離承諾（separate-commitment）兩種構造，將回合數最佳（round-optimal）盲簽章與非互動式零知識證明結合。共用承諾構造直接以盲簽章請求作為集合成員證明中的承諾；分離承諾構造則另外產生集合成員證明所使用的承諾，並透過等訊息證明（equal-message proof）證明該承諾與盲簽章請求對應至相同訊息。

在各項底層元件滿足本文所列安全性假設時，本論文證明上述構造具有正確性、訊息不可區分性、強式一次以上不可偽造性（sOMUF）與限制訊息安全性。簽章不可連結性則被視為由盲簽章架構所延伸的額外性質，並須以底層盲簽章的盲性（blindness）為假設；此性質並非由訊息不可區分性單獨推導而得。由於簽署者只處理一個隱藏的簽章請求，當所選集合成員證明的通訊量與 $n$ 無關時，所得協定的線上通訊量亦與 $n$ 無關。本論文最後分析古典密碼元件的具體實例，並提出一個以格基盲簽章為基礎的後量子候選構造，同時指出完整後量子安全性仍需補足 QPT 與 QROM 模型下的底層安全性、知識健全性（knowledge soundness）及 sOMUF 等條件。

Digital signatures provide authenticity and integrity, but an ordinary signature reveals the signed message to the signer. A 1-out-of-$n$ oblivious signature allows a receiver to obtain a valid signature on one message from a public set $M$ without revealing the selected element to the signer. Many earlier oblivious-signature constructions require the signer to process signing information associated with the entire message set, causing their communication to grow with the size of the set.

This thesis first formalizes constrained-message security, which requires that a signing interaction for $M$ cannot yield a valid signature on a message outside $M$. Based on this requirement, the thesis presents shared-commitment and separate-commitment constructions that combine a round-optimal blind signature with non-interactive zero-knowledge proofs. In the shared-commitment construction, the blind-signature request is used directly as the commitment in the set-membership statement. In the separate-commitment construction, the receiver creates an additional commitment for the membership proof and uses an equal-message proof to show that this commitment and the blind-signature request correspond to the same message.

Under the component assumptions stated in this thesis, the constructions are proved to satisfy correctness, message indistinguishability, strong one-more unforgeability, and constrained-message security. Signature unlinkability is treated as an additional property arising from the blind-signature-based framework and requires blindness of the underlying blind signature; it is not derived from message indistinguishability alone. Because the signer processes only one hidden request, the online communication of the resulting protocol is independent of $n$ whenever the selected set-membership proof has communication independent of $n$. The thesis also analyzes concrete classical examples and gives a lattice-based post-quantum candidate, while identifying the QPT and QROM security, knowledge-soundness, and sOMUF conditions that remain necessary for a complete post-quantum result.

[1] D. Chaum, “Blind signatures for untraceable payments,” in Advances in Cryptology: Proceedings of Crypto 82. Springer, 1983, pp. 199–203.

[2] D. Pointcheval and J. Stern, “Provably secure blind signature schemes,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 1996, pp. 252–265.

[3] M. Bellare, C. Namprempre, D. Pointcheval, and M. Semanko, “The one-more-rsa-inversion problems and the security of chaum’s blind signature scheme.” Journal of Cryptology, vol. 16, no. 3, 2003.

[4] T. Okamoto, “Efficient blind and partially blind signatures without random oracles,” in Theory of Cryptography Conference. Springer, 2006, pp. 80–99.

[5] S. Ibrahim, M. Kamat, M. Salleh, and S. R. A. Aziz, “Secure e-voting with blind signature,” in 4th National Conference of Telecommunication Technology, 2003. NCTT 2003 Proceedings. IEEE, 2003, pp. 193–197.

[6] N. Gupta, P. Kumar, and S. Chokar, “A secure blind signature application in e-voting,” in Proceedings of the 5th National Conference, Computing for National Development, pp1-4, 2011.

[7] F. Baldimtsi and A. Lysyanskaya, “Anonymous credentials light,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013, pp. 1087–1098.

[8] J. Camenisch, R. Chaabouni, and A. Shelat, “Efficient protocols for set membership and range proofs,” in Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2008, pp. 234–252.

[9] L. Chen, “Oblivious signatures,” in ESORICS, 1994, pp. 161–172.

[10] R. Tso, T. Okamoto, and E. Okamoto, “1-out-of-n oblivious signatures,” Lecture Notes in Computer Science, vol. 4991, pp. 45–55, 2008.

[11] Y. ZHOU, S. LIU, and S. HAN, “Generic construction of 1-out-of-n oblivious signatures,” IEICE TRANSACTIONS on Information and Systems, vol. 105, no. 11, pp. 1836–1844, 2022.

[12] M. Tezuka and K. Tanaka, “1-out-of-n Oblivious Signatures: Security Revisited and a Generic Construction with an Efficient Communication Cost,” in Information Security and Cryptology – ICISC 2023, ser. Lecture Notes in Computer Science. Springer, 2024, pp. 261–281. [Online]. Available: https://doi.org/10.1007/978-981-97-1235-9_14

[13] J.-H. Hoepman, “Two Faces of Blindness,” Designs, Codes and Cryptography, vol. 91, pp. 2705–2721, 2023. [Online]. Available: https://doi.org/10.1007/s10623-023-01228-2

[14] R. T. Jen-Chieh Hsu, “Oblivious signature based on blind signature and zero-knowledge set membership,” in 2021 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS), 2021, pp. 1–2.

[15] O. Goldreich, The Foundations of Cryptography. Cambridge University Press, 1998, vol. 1.

[16] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” in Annual international cryptology conference. Springer, 1991, pp. 129–140.

[17] S. Goldwasser, S. Micali, and R. L. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM Journal on Computing, vol. 17, no. 2, pp. 281–308, 1988.

[18] J. Bootle, A. Cerulli, P. Chaidos, and J. Groth, “Efficient zero-knowledge proof systems,” Foundations of Security Analysis and Design VIII: FOSAD 2014/2015/2016 Tutorial Lectures 15, pp. 1–31, 2016.

[19] J. Camenisch and A. Lysyanskaya, “Dynamic accumulators and application to efficient revocation of anonymous credentials,” in Crypto, vol. 2442. Springer, 2002, pp. 61–76.

[20] D. Benarroch, M. Campanelli, D. Fiore, K. Gurkan, and D. Kolonelos, “Zero-knowledge proofs for set membership: efficient, succinct, modular,” in Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part I. Springer, 2021, pp. 393–414.

[21] G. Amjad, K. Yeo, and M. Yung, “RSA blind signatures with public metadata,” Proceedings on Privacy Enhancing Technologies, vol. 2025, no. 1, pp. 37–57, 2025. [Online]. Available: https://www.petsymposium.org/popets/2025/popets-2025-0004.php

[22] D. Schröder and D. Unruh, “Security of blind signatures revisited,” Journal of Cryptology, vol. 30, no. 2, pp. 470–494, 2017. [Online]. Available: https://eprint.iacr.org/2011/316

[23] C. Song, X. Yin, and Y. Liu, “A practical electronic voting protocol based upon oblivious signature scheme,” in 2008 International Conference on Computational Intelligence and Security, vol. 1. IEEE, 2008, pp. 381–384.

[24] R. Tso, “Two-in-one oblivious signatures,” Future Generation Computer Systems, vol. 101, pp. 467–475, 2019.

[25] S.-Y. Chiou, T.-J. Wang, and J.-M. Chen, “Design and implementation of a mobile voting system using a novel oblivious and proxy signature,” Security and Communication Networks, vol. 2017, 2017.

[26] S.-Y. Chiou and J.-M. Chen, “Design and implementation of a multiple-choice e-voting scheme on mobile system using novel t-out-of-n oblivious signature.” Journal of Information Science & Engineering, vol. 34, no. 1, 2018.

[27] M. O. Rabin, “How to exchange secrets with oblivious transfer,” Cryptology ePrint Archive, 2005.

[28] C.-K. Chu and W.-G. Tzeng, “Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries,” in Public Key Cryptography-PKC 2005: 8th International Workshop on Theory and Practice in Public Key Cryptography, Les Diablerets, Switzerland, January 23-26, 2005. Proceedings 8. Springer, 2005, pp. 172–183.

[29] M. Naor and B. Pinkas, “Efficient oblivious transfer protocols,” in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2001, pp. 448–457.

[30] J.-S. You, Z.-Y. Liu, R. Tso, Y.-F. Tseng, and M. Mambo, “Quantum-resistant 1-out-of-n oblivious signatures from lattices,” in Advances in Information and Computer Security: 17th International Workshop on Security, IWSEC 2022, Tokyo, Japan, August 31–September 2, 2022, Proceedings. Springer, 2022, pp. 166–186.

[31] L. Hanzlik and K. Kluczniak, “Two-move and setup-free blind signatures with perfect blindness,” in Proceedings of the 4th ACM International Workshop on ASIA Public-Key Cryptography, 2017, pp. 1–11.

[32] M. Ciampi, G. Persiano, L. Siniscalchi, and I. Visconti, “A transform for nizk almost as efficient and general as the fiat-shamir transform without programmable random oracles,” in Theory of Cryptography: 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II 13. Springer, 2016, pp. 83–111.

[33] M. Chase, D. Derler, S. Goldfeder, C. Orlandi, S. Ramacher, C. Rechberger, D. Slamanig, and G. Zaverucha, “Post-quantum zero-knowledge and signatures from symmetric-key primitives,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2017, pp. 1825–1842.

[34] D. Derler, S. Ramacher, and D. Slamanig, “Post-quantum zero-knowledge proofs for accumulators with applications to ring signatures from symmetric-key primitives,” in Post-Quantum Cryptography – PQCrypto 2018, ser. Lecture Notes in Computer Science, vol. 10786. Springer, 2018, pp. 419–440.

[35] M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, “Structure-preserving signatures and commitments to group elements,” in Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30. Springer, 2010, pp. 209–236.

[36] J. Groth, “Homomorphic trapdoor commitments to group elements,” Cryptology ePrint Archive, 2009.

[37] 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. ACM, 2023, pp. 16–29. [Online]. Available: https://eprint.iacr.org/2023/077

[38] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE, 1994, pp. 124–134.

[39] M. Ajtai, “Generating hard instances of lattice problems,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 1996, pp. 99–108.

[40] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 2005, pp. 84–93.

[41] 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. ACM, 2008, pp. 197–206.

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

[43] E. Hauck, E. Kiltz, J. Loss, and N. K. Nguyen, “Lattice-based blind signatures, revisited,” in Advances in Cryptology – CRYPTO 2020, Part II, ser. Lecture Notes in Computer Science, vol. 12171. Springer, 2020, pp. 500–529.

[44] S. Agrawal, E. Kirshanova, D. Stehlé, and A. Yadav, “Practical, round-optimal lattice-based blind signatures,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2022, pp. 39–53.

[45] R. del Pino and S. Katsumata, “A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling,” in Advances in Cryptology – CRYPTO 2022, Part II, ser. Lecture Notes in Computer Science, vol. 13508. Springer, 2022, pp. 306–336. [Online]. Available: https://eprint.iacr.org/2022/834

[46] D. Unruh, “Non-interactive zero-knowledge proofs in the quantum random oracle model,” in Advances in Cryptology – ASIACRYPT 2015, Part II, ser. Lecture Notes in Computer Science, vol. 9453. Springer, 2015, pp. 755–784. [Online]. Available: https://eprint.iacr.org/2014/587

[47] E. Kiltz, V. Lyubashevsky, and C. Schaffner, “A concrete treatment of fiat–shamir signatures in the quantum random-oracle model,” in Advances in Cryptology – EUROCRYPT 2018, Part III, ser. Lecture Notes in Computer Science, vol. 10822. Springer, 2018, pp. 552–586. [Online]. Available: https://eprint.iacr.org/2017/916

[48] V. Lyubashevsky, N. K. Nguyen, and G. Seiler, “SMILE: Set membership from ideal lattices with applications to ring signatures and confidential transactions,” in Advances in Cryptology – CRYPTO 2021, Part II, ser. Lecture Notes in Computer Science, vol. 12826. Springer, 2021, pp. 611–640. [Online]. Available: https://eprint.iacr.org/2021/564

[49] V. Lyubashevsky, N. K. Nguyen, and G. Seiler, “Practical lattice-based zero-knowledge proofs for integer relations,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2020, pp. 1051–1070.

[50] V. Lyubashevsky, N. K. Nguyen, and M. Plançon, “Lattice-based zero-knowledge proofs and applications: Shorter, simpler, and more general,” in Advances in Cryptology – CRYPTO 2022, Part II, ser. Lecture Notes in Computer Science, vol. 13508. Springer, 2022, pp. 71–101. [Online]. Available: https://eprint.iacr.org/2022/284

[51] W. Beullens and G. Seiler, “LaBRADOR: Compact proofs for R1CS from module-SIS,” in Advances in Cryptology – CRYPTO 2023, Part V, ser. Lecture Notes in Computer Science, vol. 14085. Springer, 2023, pp. 518–548. [Online]. Available: https://eprint.iacr.org/2022/1341