近年来，计算机技术和通信技术的迅猛发展，使得社会信息化速度加快，数据交互速度和通信规模出现前所未有的增长。然而，信息高速发展在为社会生活带来极大便利的同时，也对用户的隐私权益产生了巨大威胁。数字签名是一种广泛应用于隐私保护领域的技术，同样也是密码学研究的热点话题，在如今这个信息化时代扮演着重要的角色。然而，量子计算的飞速发展，使得基于数论体制的数字签名方案的安全性受到威胁，构造能够抵御量子攻击的密码学方案成为当今时代的迫切要求。目前，格上的一些困难问题还未发现多项式时间内的求解方法，因此基于格上的困难假设构造的密码学方案被认为是可以抵御量子攻击的。盲签名和群签名是数字签名的两个重要分支，部分盲签名方案是盲签名的一种扩展方案。本文针对现有部分盲签名和群签名方案开销较大、实用性不高的问题，提出了格上的部分盲签名方案和群签名优化方案，具体工作如下： 

（1）针对现有盲签名方案存在的安全漏洞和部分盲签名实用性不高的问题，提出一种基于格的部分盲签名方案。盲签名方案允许在不泄露待签名消息的任何信息的情况下对消息签名，这使得签名者对所签信息一无所知。针对上述问题，部分盲签名方案被提出。本文在Agrawal等人于2022年提出的盲签名方案基础上进行改进，提出了一种基于格假设的部分盲签名方案，签名者和用户在签名交互开始之前协商关于待签名消息的公共信息，如消息的有效期限等。该公共信息一经商定不能非法篡改，一定程度上赋予了签名者鉴别消息合法性的能力。此外，分析了部分盲签名方案的正确性，同时证明了方案满足部分盲性和不可伪造性。最后，对所提出的方案从通信开销、计算开销和签名尺寸三个方面进行了性能分析，并从整体性能上与其他相关工作对比分析，证明本文提出的方案在实现轮数最优的同时，优化了签名尺寸。

（2）针对现有群签名方案签名尺寸较大、实用性不高的问题，提出了一种基于格的群签名优化方案。现有的基于格的群签名方案性能大多受到群成员数量限制，且签名尺寸较大，实用性不强。本方案利用新的采样技术——两阶段采样技术对群成员私钥采样，代替了Lyubashevsky等人于2021年提出的群签名方案中的格陷门采样技术，消除了因安全性证明带来的额外签名开销。此外，本文分析了零知识证明的交互过程满足完备性、正确性和零知识性，同时证明了签名方案的匿名性和可追踪性。最后，对签名算法进行性能分析，计算得出签名尺寸和密钥尺寸，相比于现有的基于格的群签名方案，本文的方案支持更短尺寸的签名和密钥，且签名、验证算法皆不受群成员数量的影响，在实用性方面更具优势。

In recent years, the rapid development of computer technology and communication technology accelerated the speed of informatization, which made the speed of data interaction and the scale of communication grow unprecedentedly. However, the rapid development of information not only brings great convenience to social life, but also poses great threat on users’ privacy rights and interests. Digital signature, as a hot topic in cryptography research, is a technology widely used in the field of privacy protection, which plays an important role in the information age. However, most of the known constructions rely the security on number-theoretic intractability assumptions and hence turns out to suffer from quantum attacks. To overcome the quantum security vulnerability, some cryptographic schemes that can resist quantum attacks has been proposed. The cryptographic schemes based on the difficult lattice assumptions are considered to be able to resist quantum attacks. Blind signature and group signature are two important branches of digital signature. Partially blind signature is an extension version of blind signature. To improve the performance in application of the existing partially blind signature and group signature schemes, this thesis proposes a partially blind signature scheme and group signature scheme on lattice. The contributions in this thesis are as follows.

 

(1) We proposed a lattice-based partially blind signature scheme to overcome the drawbacks of security vulnerabilities and low practicability in blind signatures. Blind signature schemes allow messages to be signed without leaking any information about the message to be signed. In blind signatures, the signer cannot get anything about the signed message. To solve this problem, the partially blind signature scheme is proposed. In this thesis, we proposed a partially blind signature scheme based on lattice assumption based on the existing blind signature scheme. The signer and the user publish the common information about the message to be signed together before signing, such as the validity period of the message. Once the common information is published, it cannot be modified illegally. The common information gives the signer the ability to identify the legitimacy of the message to some extent. In addition, we analyzed the correctness of the partially blind signature scheme. At the same time, we proved the partially blindness and unforgeability of proposed scheme. Finally, we analyzed the performance of the proposed scheme from the aspects of communication cost, calculation cost and signature size, and compared the overall performance with other related work. Our scheme enjoys the optimal round complexity and supports a shorter signature.

 

(2) We proposed a lattice-based group signature scheme to optimize the performance of large group signature size of existing group signature schemes. The performance of most existing lattice-based group signature schemes is limited by the number of group members, and the signature size of these scheme is large. In our construction, we use a new sampling method called Two-Stage Sampling to sample group members’ private keys, which replaces the trapdoor sampling technology in the existing schemes and eliminates the extra signature cost caused by security proof. We analyzed the interactive process of zero-knowledge proof to satisfy the completeness, correctness and zero-knowledge. What’s more, we proved the anonymity and traceability of the group signature scheme. Finally, we discussed the performance of the group signature and calculated the signature size. Compared with the existing lattice-based group signature schemes, our scheme supports shorter signature and the running times of our scheme are independent of the group size.

[1] CHAUM D. Blind signatures for untraceable payments[C]//Advances in Cryptology: Proceedings of Crypto 82. Springer, 1983: 199-203.
[2] CHAUM D. Elections with unconditionally-secret ballots and disruption equivalent to breaking rsa. [C]//Eurocrypt: Vol. 98. Springer, 1988: 177-182.
[3] FUJIOKA A, OKAMOTO T, OHTA K. A practical secret voting scheme for large scale elections [C]//Advances in Cryptology—AUSCRYPT’92: Workshop on the Theory and Application of Cryptographic Techniques Gold Coast, Queensland, Australia, December 13–16, 1992 Proceedings 3. Springer, 1993: 244-251.
[4] CHAUM D, FIAT A, NAOR M. Untraceable electronic cash[C]//Advances in Cryptology— CRYPTO’ 88: Proceedings 8. Springer, 1990: 319-327.
[5] LYUBASHEVSKY V, NGUYEN N K, PLANCON M, et al. Shorter lattice-based group signatures via “almost free” encryption and other optimizations[C]//Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part IV 27. Springer, 2021:218-248.
[6] BRANDS S. Untraceable off-line cash in wallet with observers[C]//Advances in Cryptology— CRYPTO’ 93: 13th Annual International Cryptology Conference Santa Barbara, California, USA August 22–26, 1993 Proceedings 13. Springer, 1994: 302-318.
[7] CAMENISCH J, LYSYANSKAYA A. An efficient system for non-transferable anonymous credentials with optional anonymity revocation[C]//Advances in Cryptology—EUROCRYPT 2001: International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings 20. Springer, 2001: 93-118.
[8] FISCHLIN M. Round-optimal composable blind signatures in the common reference string model [C]//Crypto: Vol. 4117. Springer, 2006: 60-77.
[9] DEL PINO R, LYUBASHEVSKY V, SEILER G. Lattice-based group signatures and zeroknowledge proofs of automorphism stability[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 574-591.
[10] BELLARE M, MICCIANCIO D, WARINSCHI B. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[C]//Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22. Springer, 2003: 614-629.
[11] LYUBASHEVSKY V, NGUYEN N K, PLANCON M. Efficient lattice-based blind signatures via
gaussian one-time signatures[C]//Public-Key Cryptography–PKC 2022: 25th IACR International
Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022,
Proceedings, Part II. Springer, 2022: 498-527.
[12] DIFFIE W, HELLMAN M E. New directions in cryptography[M]//Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman. 2022: 365-390.
[13] RÜCKERT M. Lattice-based blind signatures.[C]//Asiacrypt: Vol. 6477. Springer, 2010: 413-430.
[14] SCHNORR C P. Security of blind discrete log signatures against interactive attacks[C]//Information and Communications Security: Third International Conference, ICICS 2001 Xian, China, November 13–16, 2001 Proceedings 3. Springer, 2001: 1-12.
[15] POINTCHEVAL D, STERN J. Security arguments for digital signatures and blind signatures[J]. Journal of Cryptology, 2000, 13: 361-396.
[16] PAPACHRISTOUDIS D, HRISTU-VARSAKELIS D, BALDIMTSI F, et al. Leakage-resilient lattice-based partially blind signatures[J]. IET Information Security, 2019, 13(6): 670-684.
[17] ALKEILANI ALKADRI N, EL BANSARKHANI R, BUCHMANN J. Blaze: practical lattice-based blind signatures for privacy-preserving applications[C]//Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers 24. Springer, 2020: 484-502.
[18] ALKEILANI ALKADRI N, EL BANSARKHANI R, BUCHMANN J. On lattice-based interactive protocols: an approach with less or no aborts[C]//Information Security and Privacy: 25th Australasian Conference, ACISP 2020, Perth, WA, Australia, November 30–December 2, 2020, Proceedings. Springer, 2020: 41-61.
[19] HAUCK E, KILTZ E, LOSS J, et al. Lattice-based blind signatures, revisited[C]//Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40. Springer, 2020: 500-529.
[20] AGRAWAL S, KIRSHANOVA E, STEHLÉ D, et al. Practical, round-optimal lattice-based blind signatures[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 39-53.
[21] DEL PINO R, KATSUMATA S. A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling[C]//Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15– 18, 2022, Proceedings, Part II. Springer, 2022: 306-336.
[22] ABE M, FUJISAKI E. How to date blind signatures[C]//Advances in Cryptology—ASIACRYPT’96: International Conference on the Theory and Applications of Cryptology and Information Security Kyongju, Korea, November 3–7, 1996 Proceedings. Springer, 1996: 244-251.
[23] ABE M, OKAMOTO T. Provably secure partially blind signatures[C]//Advances in Cryptology— CRYPTO 2000: 20th Annual International Cryptology Conference Santa Barbara, California, USA, August 20–24, 2000 Proceedings 20. Springer, 2000: 271-286.
[24] TIAN H, ZHANG F, WEI B. A lattice-based partially blind signature[J]. Security and Communication Networks, 2016, 9(12): 1820-1828.
[25] BOUAZIZ-ERMANN S, CANARD S, EBERHART G, et al. Lattice-based (partially) blind signature without restart[J]. Cryptology ePrint Archive, 2020.
[26] CHAUM D, VAN HEYST E. Group signatures[C]//Advances in Cryptology—EUROCRYPT’ 91: Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991 Proceedings 10. Springer, 1991: 257-265.
[27] GORDON S D, KATZ J, VAIKUNTANATHAN V. A group signature scheme from lattice assumptions[C]//Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. Springer, 2010: 395-412.
[28] LAGUILLAUMIE F, LANGLOIS A, LIBERT B, et al. Lattice-based group signatures with logarithmic signature size[C]//Advances in Cryptology-ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II 19. Springer, 2013: 41-61.
[29] GORDON S D, KATZ J, VAIKUNTANATHAN V. A group signature scheme from lattice assumptions[C]//Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. Springer, 2010: 395-412.
[30] LIBERT B, LING S, NGUYEN K, et al. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer, 2016: 1-31.
[31] BOSCHINI C, CAMENISCH J, NEVEN G. Floppy-sized group signatures from lattices[C]// Applied Cryptography and Network Security: 16th International Conference, ACNS 2018, Leuven, Belgium, July 2-4, 2018, Proceedings 16. Springer, 2018: 163-182.
[32] KATSUMATA S, YAMADA S. Group signatures without nizk: from lattices in the standard model [C]//Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019 Proceedings, Part III 38. Springer, 2019: 312-344.
[33] YANG R, AU M H, ZHANG Z, et al. Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part I 39. Springer, 2019: 147-175.
[34] BOOTLE J, LYUBASHEVSKY V, SEILER G. Algebraic techniques for short (er) exact latticebased zero-knowledge proofs[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part I. Springer, 2019: 176-202.
[35] ESGIN M F, STEINFELD R, LIU J K, et al. Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part I. Springer, 2019: 115-146.
[36] ATTEMA T, LYUBASHEVSKY V, SEILER G. Practical product proofs for lattice commitments [C]//Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II. Springer, 2020: 470-499.
[37] ESGIN M F, NGUYEN N K, SEILER G. Practical exact proofs from lattices: New techniques to exploit fully-splitting rings[C]//Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26. Springer, 2020: 259-288.
[38] ESGIN M F, ZHAO R K, STEINFELD R, et al. Matrict: efficient, scalable and post-quantum confidential transactions protocol[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 567-584.
[39] ESGIN M F, STEINFELD R, ZHAO R K. Matrict+: More efficient post-quantum private blockchain payments[C]//2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022: 1281-1298.
[40] BEULLENS W, DOBSON S, KATSUMATA S, et al. Group signatures and more from isogenies and lattices: generic, simple, and efficient[J]. Designs, Codes and Cryptography, 2023: 1-60.
[41] LAI Q, LIU F H, WANG Z. New lattice two-stage sampling technique and its applications to functional encryption–stronger security and smaller ciphertexts[C]//Advances in Cryptology– EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I. Springer, 2021: 498-527.
[42] AJTAI M. Generating hard instances of lattice problems[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 99-108.
[43] MICCIANCIO D, REGEV O. Worst-case to average-case reductions based on gaussian measures [J]. SIAM Journal on Computing, 2007, 37(1): 267-302.
[44] MICCIANCIO D, PEIKERT C. Hardness of sis and lwe with small parameters[C]//Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I. Springer, 2013: 21-39.
[45] BRAKERSKI Z, VAIKUNTANATHAN V. Constrained key-homomorphic prfs from standard lattice assumptions: Or: How to secretly embed a circuit in your prf[C]//Theory of Cryptography: 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II 12. Springer, 2015: 1-30.
[46] GAMA N, IZABACHENE M, NGUYEN P Q, et al. Structural lattice reduction: generalized worstcase to average-case reductions and homomorphic cryptosystems[C]//Advances in Cryptology– EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer, 2016: 528-558.
[47] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.
[48] MICCIANCIO D. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions[C]//The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. IEEE, 2002: 356-365.
[49] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings [J]. Journal of the ACM (JACM), 2013, 60(6): 1-35.
[50] LANGLOIS A, STEHLÉ D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565-599.
[51] BELLARE M, NAMPREMPRE C, POINTCHEVAL D, et al. The one-more-rsa-inversion problems and the security of chaum’s blind signature scheme.[J]. Journal of Cryptology, 2003, 16(3).
[52] ALWEN J, PEIKERT C. Generating shorter bases for hard random lattices[J]. Cryptology ePrint Archive, 2008.
[53] CASH D, HOFHEINZ D, KILTZ E, et al. Bonsai trees, or how to delegate a lattice basis[J]. Journal of Cryptology, 2012, 25: 601-639.
[54] AGRAWAL S, BONEH D, BOYEN X. Efficient lattice (h) ibe in the standard model.[C]//Eurocrypt: Vol. 6110. Springer, 2010: 553-572.
[55] GOLDWASSER S, MICALI S, RACKOFF C. The knowledge complexity of interactive proofsystems[M]//Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. 2019: 203-225.
[56] LYUBASHEVSKY V. Lattice signatures without trapdoors[C]//Advances in Cryptology– EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings 31. Springer, 2012: 738-755.
[57] BLUM M. Coin flipping by telephone a protocol for solving impossible problems[J]. ACM SIGACT News, 1983, 15(1): 23-27.
[58] RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.
[59] ESGIN M F, STEINFELD R, LIU D, et al. Efficient hybrid exact/relaxed lattice proofs and applications to rounding and vrfs[J]. Cryptology ePrint Archive, 2022.
[60] R. AVANZI L D E K T L V L J M S P S G S, J. Bos, STEHL´E D. Crystals-kyber: Algorithm specifications and supporting documentation[J]. https://csrc.nist.gov/Projects/post quantumcryptography/post-quantum-cryptography-standardization/Round-1-Submissions.
[61] LYUBASHEVSKY V, NGUYEN N K, SEILER G. Practical lattice-based zero-knowledge proofs for integer relations[C]//Proceedings of the 2020 ACM SIGSAC conference on computer and communications security. 2020: 1051-1070.
[62] P.-A. FOUQUE P K V L T P T P T R G S W W, J. Hoffstein, ZHANG Z. Falcon: Fast-fourier lattice-based compact signatures over ntru[C]//Proceedings of the 2020 ACM SIGSAC conference on computer and communications security. https://falcon-sign.info/.
[63] LYUBASHEVSKY V, NGUYEN N K, PLANÇON M. Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general[C]//Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part II. Springer, 2022: 71-101.
[64] DUCAS L, KILTZ E, LEPOINT T, et al. Crystals-dilithium: A lattice-based digital signature scheme [J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018: 238-268.
[65] FIAT A, SHAMIR A. How to prove yourself: Practical solutions to identification and signature problems.[C]//Crypto: Vol. 86. Springer, 1986: 186-194.
[66] LIBERT B, LING S, NGUYEN K, et al. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors [C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer, 2016: 1-31.
[67] BOSCHINI C, CAMENISCH J, NEVEN G. Floppy-sized group signatures from lattices[C]// Applied Cryptography and Network Security: 16th International Conference, ACNS 2018, Leuven, Belgium, July 2-4, 2018, Proceedings 16. Springer, 2018: 163-182.