Paper 2022/834

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

Abstract

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.