In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat--Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieve security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message---which can inevitably happen in the Fiat--Shamir with Aborts setting. We manage to do so using homomorphic commitments.
Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.'s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round $n$-out-of-$n$ distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
Category / Keywords: cryptographic protocols / threshold signatures, $n$-out-of-$n$ distributed signatures, multi-signatures, lattice-based cryptography, Fiat--Shamir with aborts, trapdoor commitments Date: received 14 Sep 2020, last revised 16 Nov 2020 Contact author: takahashi at cs au dk, ivan@cs au dk, orlandi@cs au dk, mehdi tibouchi br@hco ntt co jp Available format(s): PDF | BibTeX Citation Version: 20201116:104016 (All versions of this report) Short URL: ia.cr/2020/1110