Paper 2024/1574 Original: eprint.iacr.org/2024/1574 ↗

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

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).