Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. International Conference on Provable and Practical Security (ProvSec 2020)
- DOI
- 10.1007/978-3-030-62576-4_3
- Keywords
- Lattice CryptographyMultisigatureQuantum Random Oracle ModelCRYSTALS-Dilithium
- Contact author(s)
-
fukumitsu @ do-johodai ac jp
shingo hasegawa b7 @ tohoku ac jp - History
- 2021-07-28: received
- Short URL
- https://ia.cr/2021/1000
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1000,
author = {Masayuki Fukumitsu and Shingo Hasegawa},
title = {A Lattice-based Provably Secure Multisignature Scheme in Quantum Random Oracle Model},
howpublished = {Cryptology ePrint Archive, Paper 2021/1000},
year = {2021},
doi = {10.1007/978-3-030-62576-4_3},
note = {\url{https://eprint.iacr.org/2021/1000}},
url = {https://eprint.iacr.org/2021/1000}
}
