Paper 2021/381
Towards Practical and RoundOptimal LatticeBased Threshold and Blind Signatures
Shweta Agrawal, Damien Stehle, and Anshu Yadav
Abstract
Threshold and blind signature schemes have found numerous applications in cryptocurrencies, ecash, evoting and other privacypreserving technologies. In this work, we make advances in bringing latticebased constructions for these primitives closer to practice. 1. Threshold Signatures. For round optimal threshold signatures, we improve the only known construction by Boneh et al. [CRYPTO'18] as follows: a. Efficiency. We reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease signature bitlengths from $\widetilde{O}(\lambda^3)$ to $\widetilde{O}(\lambda)$. b. Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing queries are made. We improve this in two ways: in the ROM, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker preprocessing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase. 2. Blind Signatures. For blind signatures, we improve the state of art latticebased construction by Hauck et al.[CRYPTO'20] as follows: a. Round Complexity. We improve the round complexity from three to two  this is optimal. b. Efficiency. Again, we reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of signatures and $\lambda$ is the security parameter. c. Number of Signing Queries. Unlike the scheme from Hauck et al., our construction enjoys a proof that is not restricted to a polylogarithmic number of signatures. Using lattice hardness assumptions over rings, we obtain signatures of bitlengths bounded as $\widetilde{O}(\lambda)$. In contrast, the signature bitlength in the scheme from Hauck et al. is $\Omega(\lambda^3 + Q_S \cdot \lambda)$. Concretely, we can obtain blind/threshold signatures of size $\approx 3$ KB using a variant of DilithiumG with $\approx 128$ bitsecurity, for adversaries limited to getting $256$ signatures. In contrast, parameters provided by Hauck et al. lead to blind signatures of $\approx 7.73$ MB, for adversaries limited to getting 7 signatures, while concrete parameters are not provided for the construction of threshold signatures by Boneh et al.
Metadata
 Available format(s)
  withdrawn 
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 blind signaturesthreshold signatureslatticespractical
 Contact author(s)

shweta a @ gmail com
anshu yadav06 @ gmail com
damien stehle @ enslyon fr  History
 20211202: withdrawn
 20210322: received
 See all versions
 Short URL
 https://ia.cr/2021/381
 License

CC BY