Paper 2022/834

A New Framework For More Efficient Round-Optimal Lattice-Based (Partially) Blind Signature via Trapdoor Sampling

Rafael del Pino, PQShield SAS, France
Shuichi Katsumata, AIST, Japan, PQShield Ltd., U.K.

Blind signatures, proposed by Chaum (CRYPTO'82), are interactive protocols between a signer and a user, where a user can obtain a signature without revealing the message to be signed. Recently, Hauck et al. (EUROCRYPT'20) observed that all efficient lattice-based blind signatures following the blueprint of the original blind signature by Rükert (ASIACRYPT'10) have a flawed security proof. This puts us in a situation where all known lattice-based blind signatures have at least two of the following drawbacks: heuristic security; 1 MB or more signature size; only supporting bounded polynomially many signatures, or being based on non-standard assumptions. In this work, we construct the first round-optimal (i.e., two-round) lattice-based blind signature with a signature size of roughly 100 KB that supports unbounded polynomially many signatures and is provably secure under standard assumptions. Even if we allow non-standard assumptions and more rounds, ours provide the shortest signature size while simultaneously supporting unbounded polynomially many signatures. The main idea of our work is revisiting the generic blind signature construction by Fischlin (CRYPTO'06) and optimizing the commit-then-open proof using techniques tailored to lattices. Our blind signature is also the first to have a formal security proof in the quantum random oracle model. Finally, our blind signature extends naturally to partially blind signatures, where the user and signer can include an agreed-upon public string in the message.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
blind signature lattice trapdoor sampling
Contact author(s)
rafael del pino @ pqshield com
shuichi katsumata000 @ gmail com
2022-06-27: approved
2022-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rafael del Pino and Shuichi Katsumata},
      title = {A New Framework For More Efficient Round-Optimal Lattice-Based (Partially) Blind Signature via Trapdoor Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2022/834},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.