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. In the post-quantum setting, existing constructions typically follow one of two paradigms: either signatures are realized as non-interactive zero-knowledge ($\mathsf{NIZK}$) proofs of valid underlying signatures, or they are obtained from identification schemes via the Fiat--Shamir transform. In both approaches, the resulting signatures deviate syntactically from standard signatures, incurring additional verification overhead and limiting compatibility with existing infrastructures. In contrast, classical constructions such as blind Schnorr yield signatures that are indistinguishable from ordinary ones. Achieving this property in the lattice setting has remained an open problem. We present $\mathsf{BRaccoon}$, the first lattice-based blind signature scheme that achieves concurrent security while producing signatures that are syntactically identical to those of a standard signature scheme. Our construction builds on the rejection-free lattice signature scheme $\mathsf{Raccoon}$, and extends the ``blind signatures from a signature assumption'' paradigm of Fuchsbauer and Wolf (EUROCRYPT~2024) to lattices. 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. As a result, $\mathsf{BRaccoon}$ signatures preserve the algebraic structure of $\mathsf{Raccoon}$ signatures while remaining compact: in an optimized instantiation, signatures are $32$ KB, public keys are $10$ KB, and total communication is $847$ KB for up to $2^{32}$ 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 prove that one-more unforgeability of $\mathsf{BRaccoon}$ tightly reduces to the unforgeability of $\mathsf{Raccoon}^\star$, which in turn reduces to that of $\mathsf{Raccoon}$. For a concrete instantiation, we develop a hybrid proof framework that combines lattice-based zero-knowledge arguments for linear relations with arithmetic zk-SNARKs for hash computations, linked via structured commitments. Our work demonstrates that concurrently secure blind signatures with standard-signature syntax can be achieved in the lattice setting, providing a viable path toward practical and interoperable post-quantum privacy-preserving systems.