Evaluating the Security of CRYSTALS-Dilithium in the Quantum Random Oracle Model

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 \(\textsf{CRYSTALS}\hbox {-}\!\textsf{Dilithium}\) . The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors ( \(\textsf{MLWE}\) ), Module Short Integer Solution ( \(\textsf{MSIS}\) ), and \(\textsf{SelfTargetMSIS}\) . \(\textsf{MLWE}\) and \(\textsf{MSIS}\) have been well-studied and are widely believed to be secure. However, \(\textsf{SelfTargetMSIS}\) is novel and, though classically as hard as \(\textsf{MSIS}\) , its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of \(\textsf{SelfTargetMSIS}\) via a reduction from \(\textsf{MLWE}\) in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the \(\textsf{MSIS}\) problem, is collapsing. From this approach, we deduce a new security proof for \(\textsf{Dilithium}\) under appropriate parameter settings. Compared to the previous work by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) that gave the only other rigorous security proof for a variant of \(\textsf{Dilithium}\) , our proof has the advantage of being applicable under the condition \(q = 1 \ \textrm{mod} \ 2n\) , where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original \(\textsf{Dilithium}\) proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for \(\textsf{Dilithium}\) under the condition \(q = 1 \ \textrm{mod} \ 2n\) , finding that our public key size and signature size are about \(2.9\times \) and \(1.3\times \) larger, respectively, than those proposed by Kiltz et al. at the same security level. [Full version: arXiv:2312.16619 ]