Paper 2026/1084

BRaccoon: Concurrently Secure Blind Lattice Signatures from Raccoon

Abstract

Blind signatures are a central primitive for privacy-preserving applications such as e-cash, anonymous credentials, and e-voting. Classical constructions such as blind Schnorr adapt an ordinary signature scheme while producing signatures that follow the same format and distribution as those generated by the ordinary signing algorithm. This property is particularly relevant in settings where blind and non-blind signatures coexist within the same infrastructure. Achieving an analogous result for lattice-based Fiat--Shamir signatures, with security based on the underlying ordinary signature scheme, has remained open. We present $\mathsf{BRaccoon}$, the first concurrently secure lattice-based realization of the ``blind signatures from a signature assumption'' paradigm of Fuchsbauer and Wolf (EUROCRYPT~2024). Our construction builds on the rejection-free lattice signature scheme $\mathsf{Raccoon}$, yielding signatures that retain the algebraic format and verification relation of $\mathsf{Raccoon}$. At a high level, we introduce blinding at the commitment stage and enforce correct challenge and response generation via linearly homomorphic encryption combined with $\mathsf{NIZK}$ proofs. Since these proofs already bind the hidden message to the resulting signature, their relation can naturally incorporate predicates on that message, providing a direct route toward predicate blind signatures. A central technical challenge stems from discrete Gaussian sampling, where blinding induces a non-trivial distributional shift that precludes direct security reductions. To overcome this, we introduce a modified scheme $\mathsf{Raccoon}^\star$ that explicitly captures this shift. We analyze one-more unforgeability through non-rounded versions of $\mathsf{Raccoon}^\star$ and $\mathsf{Raccoon}$. The deployed blind-signing protocol retains rounding. For a concrete instantiation, we encode the lattice relations and the non-linear challenge computation in a common mixed Boolean and arithmetic relation. Our instantiation retains SHA3-256 and SHAKE256 and proves both protocol statements using the ZK-LaBRADOR toolkit. For up to $2^{32}$ signing queries, its total communication is estimated at approximately $862$ KB.