Cryptology ePrint Archive: Report 2021/1000

A Lattice-based Provably Secure Multisignature Scheme in Quantum Random Oracle Model

Masayuki Fukumitsu and Shingo Hasegawa

Abstract: The multisignature schemes are attracted to utilize in some cryptographic applications such as the blockchain. Though the lattice-based constructions of multisignature schemes exist as quantum-secure multisignature, a multisignature scheme whose security is proven in the quantum random oracle model (QROM), rather than the classical random oracle model (CROM), is not known. In this paper, we propose a first lattice-based multisignature scheme whose security is proven in QROM. Although our proposed scheme is based on the Dilithium-QROM signature, whose security is proven in QROM, their proof technique cannot be directly applied to the multisignature setting. The difficulty of proving the security in QROM is how to program the random oracle in the security proof. To solve the problems in the security proof, we develop several proof techniques in QROM. First, we employ the searching query technique by Targi and Unruh to convert the Dilithium-QROM into the multisignature setting. For the second, we develop a new programming technique in QROM since the conventional programming techniques seem not to work in the multisignature setting of QROM. We combine the programming technique by Unruh with the one by Liu and Zhandry. The new technique enables us to program the random oracle in QROM and construct the signing oracle in the security proof.

Category / Keywords: public-key cryptography / Lattice Cryptography, Multisigature, Quantum Random Oracle Model, CRYSTALS-Dilithium

Original Publication (with minor differences): International Conference on Provable and Practical Security (ProvSec 2020)

Date: received 26 Jul 2021

Contact author: fukumitsu at do-johodai ac jp, shingo hasegawa b7 at tohoku ac jp

Available format(s): PDF | BibTeX Citation

Version: 20210728:064118 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]