Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model

Published

December 27, 2023

Author(s)

Kelsey Jackson, Carl A. Miller, Daochen Wang

Abstract

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically hard, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and extraction rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium (Kiltz et al. 2018), our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition was part of the original Dilithium proposal and it is crucial for efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, and we find that these parameter sets are comparable to (Kiltz et al. 2018) in terms of key size and signature size. Whereas (Kiltz et al. 2018) increase the public key and signature sizes of the original specification by approximately 5× and 2×, respectively, we increase the same sizes by approximately 3× and 4×, respectively.

Citation

arXiv

Pub Weblink

https://www.arxiv.org

Pub Type

Websites

Download Paper

https://doi.org/10.48550/arXiv.2312.16619

Local Download

Keywords

post-quantum cryptography, random oracle model, lattice-based cryptography

Citation

Jackson, K. , Miller, C. and Wang, D. (2023), Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model, arXiv, [online], https://doi.org/10.48550/arXiv.2312.16619, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=956883, https://www.arxiv.org (Accessed April 30, 2024)