TY - GEN
T1 - A Lattice-Based Provably Secure Multisignature Scheme in Quantum Random Oracle Model
AU - Fukumitsu, Masayuki
AU - Hasegawa, Shingo
N1 - Funding Information:
Acknowledgements. We would like to thank anonymous reviewers for their valuable comments and suggestions. We are also grateful to Akira Takahashi for his fruitful comments on the security proof. This work was supported in part by JSPS KAKENHI Grant Numbers JP18K11288 and JP19K20272.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - 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. The difficultly of proving the security in QROM than CROM is how to program the random oracle in the security proof. 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. 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 to construct the signing oracle in the security proof.
AB - 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. The difficultly of proving the security in QROM than CROM is how to program the random oracle in the security proof. 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. 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 to construct the signing oracle in the security proof.
KW - CRYSTALS-Dilithium
KW - Lattice cryptography
KW - Multisigature
KW - Quantum random oracle model
UR - http://www.scopus.com/inward/record.url?scp=85097442772&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097442772&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-62576-4_3
DO - 10.1007/978-3-030-62576-4_3
M3 - Conference contribution
AN - SCOPUS:85097442772
SN - 9783030625757
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 45
EP - 64
BT - Provable and Practical Security - 14th International Conference, ProvSec 2020, Proceedings
A2 - Nguyen, Khoa
A2 - Wu, Wenling
A2 - Lam, Kwok Yan
A2 - Wang, Huaxiong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 14th International Conference on Provable Security, ProvSec 2020
Y2 - 29 November 2020 through 1 December 2020
ER -