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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.