Paper 2022/1036

MuSig-L: Lattice-Based Multi-Signature With Single-Round Online Phase

Cecilia Boschini, Technion – Israel Institute of Technology, Reichman University
Akira Takahashi, Aarhus University
Mehdi Tibouchi, NTT (Japan)
Abstract

Multi-signatures are protocols that allow a group of signers to jointly produce a single signature on the same message. In recent years, a number of practical multi-signature schemes have been proposed in the discrete-log setting, such as MuSigT (CRYPTO'21) and DWMS (CRYPTO'21). The main technical challenge in constructing a multi-signature scheme is to achieve a set of several desirable properties, such as (1) security in the plain public-key (PPK) model, (2) concurrent security, (3) low online round complexity, and (4) key aggregation. However, previous lattice-based, post-quantum counterparts to Schnorr multi-signatures fail to satisfy these properties. In this paper, we introduce MuSigL, a lattice-based multi-signature scheme simultaneously achieving these design goals for the first time. Unlike the recent, round-efficient proposal of Damgård et al. (PKC'21), which had to rely on lattice-based trapdoor commitments, we do not require any additional primitive in the protocol, while being able to prove security from the standard module-SIS and LWE assumptions. The resulting output signature of our scheme therefore looks closer to the usual Fiat--Shamir-with-abort signatures.

Note: Full version

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
lattice multi signature
Contact author(s)
cecilia bo @ cs technion ac il
takahashi @ cs au dk
mehdi tibouchi br @ hco ntt co jp
History
2022-08-11: approved
2022-08-10: received
See all versions
Short URL
https://ia.cr/2022/1036
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1036,
      author = {Cecilia Boschini and Akira Takahashi and Mehdi Tibouchi},
      title = {{MuSig}-L: Lattice-Based Multi-Signature With Single-Round Online Phase},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1036},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1036}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.