Flood and Submerse: Distributed Key Generation and Robust Threshold Signature from Lattices

We propose a new framework based on random submersions—that is projection over a random subspace blinded by a small Gaussian noise—for constructing verifiable short secret sharing and showcase it to construct efficient threshold lattice-based signatures in the hash-and-sign paradigm, when based on noise flooding. This is, to our knowledge, the first hash-and-sign lattice-based threshold signature. Our threshold signature enjoys the very desirable property of robustness, including at key generation. In practice, we are able to construct a robust hash-and-sign threshold signature for threshold and provide a typical parameter set for threshold \(T=16\) and signature size 13kB. Our constructions are provably secure under standard \(\textsf{MLWE} \) assumption in the \(\textsf{ROM}\) and only require basic primitives as building blocks. In particular, we do not rely on FHE-type schemes.