Quantum Security of a Compact Multi-Signature
Open Access
- 28 October 2024
- journal article
- research article
- Published by MDPI AG in Cryptography
- Vol. 8 (4) , 50
Abstract
With the rapid advances in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry’s compressed random oracle (CStO), called a compressed quantum random oracle with adaptive special points (CStOs). Then, we extend the on-line extraction technique of Don et al. (EUROCRYPT’22) from CStO to . We also extend the random experiment technique of Liu and Zhandry (CRYPTO’19) for extracting the query that witnesses the future adversarial output. With these preparations, a systematic security proof in the quantum random oracle model can start with a random CStO experiment (that extracts the witness for the future adversarial output) and then converts this game to one involving . Next, the online extraction technique for can be applied to extract the witness for any online commitment. With this strategy, we give a security proof of our recent compact multi-signature framework that is converted from any weakly secure linear ID scheme. We also prove the quantum security of our recent lattice realization of this linear ID scheme by iteratively applying the weakly collapsing protocol technique of Liu and Zhandry (CRYPTO 2019). Combining these two results, we obtain the first quantum security proof for a compact multi-signature.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- A Lattice-Based Provably Secure Multisignature Scheme in Quantum Random Oracle Model2020
- Round Optimal Secure Multisignature Schemes from Lattice with Public Key Aggregation and Signature Compression2020
- How to Record Quantum Queries, and Applications to Quantum Indifferentiability2019
- Revisiting Post-quantum Fiat-Shamir2019
- Sequential Aggregate Signatures and Multisignatures Without Random Oracles2006
- Generalized Compact Knapsacks Are Collision Resistant2006
- Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices2006
- Advances in Cryptology — EUROCRYPT 20032003
- Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme2002
- Algebra2002