Paper 2025/1633

LastRings: Lattice-based Scalable Threshold Ring Signatures

Abstract

In this paper, we construct the first lattice-based threshold ring signature scheme with signature size scaling logarithmically in the size of the ring while supporting arbitrary thresholds. Our construction is also concretely efficient, achieving signature sizes of less than 150kB for ring sizes up to $N = 4096$ (with threshold size $T=N/2$, say). This is substantially more compact than previous work. Our approach is inspired by the recent work of Aardal et al. (CRYPTO 2024) on the compact aggregation of $\mathsf{Falcon}$ signatures, that uses the $\mathsf{LaBRADOR}$ lattice-based SNARKs to combine a collection of $\mathsf{Falcon}$ signatures into a single succinct argument of knowledge of those signatures. We proceed in a similar way to obtain compact threshold ring signatures from \falcon, but crucially require that the proof system be zero-knowledge in order to ensure the privacy of signers. Since $\mathsf{LaBRADOR}$ is not a zkSNARK, we associate it with a separate (non-succinct) lattice-based zero-knowledge proof system to achieve our desired properties.