International Association
for Cryptologic Research

Blind signatures constitute basic cryptographic ingredients for privacy-preserving applications such as anonymous credentials, e-voting, and Bitcoin. Despite the great variety of cryptographic applications, blind signatures also found their way in real-world scenarios. Due to the expected progress in cryptanalysis using quantum computers, it remains an important research question to find practical and secure alternatives to systems based on classical security assumptions that are not future-proof. In this work we present $\mathsf{BLAZE}$, a new practical blind signature scheme from lattice assumptions. With respect to all relevant efficiency metrics $\mathsf{BLAZE}$ is much more efficient than all previous blind signature schemes based on assumptions conjectured to withstand quantum computer attacks. In particular, $\mathsf{BLAZE}$ considerably improves upon the first (and currently only secure) lattice-based proposal introduced by Rückert at ASIACRYPT 2010 ($\mathsf{RBS}$). For instance, at 128 bits of security signatures are as small as 6.6 KB, which represents an improvement factor of 13.5 compared to $\mathsf{RBS}$, 2.7 compared to all previous candidates, and an expansion factor of 2.5 compared to the NIST PQC submission $\mathsf{Dilithium}$. We also give a highly optimized implementation, which demonstrates the efficiency of $\mathsf{BLAZE}$ to be deployed in practical applications. In particular, generating a blind signature takes just 18 ms, which represents a factor improvement of 15 compared to $\mathsf{RBS}$. The running times for key generation and verification are in the same order as state-of-the-art regular signature schemes, however several orders of magnitudes faster than $\mathsf{RBS}$.