Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model

Qiqi Lai; Feng-Hao Liu; Yang Lu; Haiyang Xue; Yong Yu; Yuan Chen

Paper 2024/1574

Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model

Qiqi Lai, Shaanxi Normal University

Feng-Hao Liu, Washington State University

Yang Lu, Shaanxi Normal University

Haiyang Xue, Singapore Management University

Yong Yu, Shaanxi Normal University

Yuan Chen, State Key Laboratory of Integrated Services Networks, Xidian University

Abstract

In this paper, we construct the first asymptotically efficient two-round $n$-out-of-$n$ and multi-signatures from lattices in the quantum random oracle model (\QROM), using the Fiat-Shamir with Aborts (\FSwA) paradigm. Our protocols can be viewed as the improvements on the two-round protocols by Damg{\aa}rd et al. (JoC 2022). From a technical perspective, the simulation of \QROM~and the efficient reduction from breaking underlying assumption to forging signatures are the essential challenges to achieving efficient $\QROM$ security for the previously related works. In order to conquer the former one, we adopt the quantum-accessible pseudorandom function (\QPRF) to simulate $\QROM$. Particularly, we show that there exists a $\QPRF$ that is both invertible and programmable, which can simulate $\QROM$ with the same properties. Moreover, we use $\QPRF$ as an intermediate tool to successfully simulate $\QROM$ whose output is separable, even against a quantum adversary. For the latter challenge, we tweak and apply the online extractability by Unruh (Eurocrypt 2015).

Note: This is the full version of paper.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in PKC 2026
Keywords: Threshold Signature Multi-Signature Two-Round QROM
Contact author(s): laiqq @ snnu edu cn
feng-hao liu @ wsu edu
luyang @ snnu edu cn
haiyangxc @ gmail com
yuyong @ snnu edu cn
History: 2026-02-13: last of 5 revisions; 2024-10-06: received; See all versions
Short URL: https://ia.cr/2024/1574
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1574,
      author = {Qiqi Lai and Feng-Hao Liu and Yang Lu and Haiyang Xue and Yong Yu and Yuan Chen},
      title = {Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1574},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1574}
}