A Tightly-Secure Lattice-Based Multisignature
Masayuki Fukumitsu, Shingo Hasegawa · 2019
Multisignatures enable multiple users to sign a message in an interactive manner. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we construct a first lattice-based multisignature which has a tight security reduction. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based standard signature scheme by Abdalla, Fouque, Lyubashevsky and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Error) assumption.