LastRings: Lattice-Based Scalable Threshold Ring Signatures
摘要
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 150 kB 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 Falcon signatures, that uses the LaBRADOR lattice-based SNARKs to combine a collection of 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 LaBRADOR is not a zkSNARK, we associate it with a separate (non-succinct) lattice-based zero-knowledge proof system to achieve our desired properties.