International Association
for Cryptologic Research

Blind signatures, originally proposed by Chaum (CRYPTO'82), are interactive protocols between a signer and a user, where the 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 Rukert (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 is 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 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 also 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 construction 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.