SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

cCopyright ⃝2022
The Institute of Electronics,
Information and Communication Engineers

A Practical Lattice-Based Threshold Signature
Yi Xu ∗Yuntao Wang ∗Eiichiro Fujisaki ∗Keywords: threshold signatures, lattice, Fiat-Shamir Signature Scheme―References[AASA+ 20] Gorjan Alagic, Jacob Alperin-Sheriﬀ,
Daniel Apon, David Cooper, QuynhDang, John Kelsey, Yi-Kai Liu, CarlMiller, Dustin Moody, Rene Peralta, et al.
Status report on the second round of
the nist post-quantum cryptography standardization process. US Department ofCommerce, NIST, 2020.

Abstract

Threshold cryptography schemes can be applied tomany areas, and a well-known example is Bitcoin. Bitcoin was invented in 2008 by Satoshi Nakamoto andhas gained much intention in recent years. Research
produced by the University of Cambridge estimatedthat in 2017, there were 2.9 to 5.8 million unique users
using a cryptocurrency wallet, most of them using Bit[ASY21]
coin. To use Bitcoin, everyone should own a walletthat stores the collections of one’s public key and private key. If the wallet is compromised, the Bitcoin will
be stolen. Correspondently, an alternative countermeasure is to split keys into several shares. Only a threshold set of shares can sign a transaction in this situation.
[BGG+ 18]
Bitcoin is currently signed with an ECDSA, which isvulnerable to quantum computers, so it prefers to bereplaced by signatures with Post-Quantum Cryptography (PQC) properties. The NIST is holding a PQC
standardization project [AASA+ 20], and nine signature schemes are selected for the second round in 2019.
It includes three lattice-based signature schemes, andtwo of them are Fiat-Shamir based, which suggests thelattice-based Fiat-Shamir signatures are promising.
In this paper, we propose a practical (k, n) thresholdsignature by adapting the {0, 1}-Linear Secret Shar[Lyu09]
ing Scheme technique [BGG+ 18] to a without rejection
variant of Lyubashevsky’s signature scheme [Lyu09, Lyu12,ASY21], so a threshold of parties can produce a valid
signature. The security of our scheme is based on thehardness of finding an approximate shortest vector andthe Learning With Errors problem in the random oracle
model, and its security is not deteriorated compared tothe n-out-of-n threshold signatures. When creating apartial signature, since it is a Fiat-Shamir type, a pub[Lyu12]
lic channel between signers is required. Although it is
not round optimal, partial signature generation always
ends in three rounds of Multi-Party Communications.

∗ Japan Advanced Institute of Science and Technology (JAIST)

1Shweta Agrawal, Damien Stehlé, and Anshu Yadav. Towards practical and roundoptimal lattice-based threshold and blindsignatures. IACR Cryptol. ePrint Arch.,
2021:381, 2021.
Dan Boneh, Rosario Gennaro, Steven
Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai.
Threshold cryptosystems fromthreshold fully homomorphic encryption. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part I, volume10991 of Lecture Notes in Computer Science, pages 565–596. Springer, Heidelberg,
August 2018.
Vadim Lyubashevsky. Fiat-Shamir withaborts:
Applications to lattice andfactoring-based signatures. In Mitsuru
Matsui, editor, Advances in Cryptology –ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages598–616. Springer, Heidelberg, December
2009.
Vadim Lyubashevsky. Lattice signatures
without trapdoors. In David Pointcheval
and Thomas Johansson, editors, Advancesin Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in ComputerScience, pages 738–755. Springer, Heidelberg, April 2012.