Evaluating the QROM Hardness of Cryptographic Assumptions in CRYSTALS-Dilithium

Abstract. NIST intends to standardize a new generation of cryptographic schemes secure against quantum adversaries.  Their primary choice for a secure digital signature scheme is CRYSTALS-Dilithium. CRYSTALS-Dilithium is based on three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. The first two, MLWE and MSIS, are well-studied and widely held to be secure, but the latter, SelfTargetMSIS, is novel and its quantum hardness is uncertain. In this talk we will review the current security understandings for all three of these problems. Then, we will utilize a lifting theorem developed by Yamakawa and Zhandry to prove that SelfTargetMSIS is asymptotically at least as hard as MSIS in the Quantum Random Oracle Model (QROM). We also examine the resulting parameter shifts for concrete security settings.

Based on joint work with Carl Miller.

Suggested readings: ia.cr/2020/1270, ia.cr/2020/282.