Paper 2022/1601

Revisiting the Concrete Hardness of SelfTargetMSIS in CRYSTALS-Dilithium

Geng Wang, Shanghai Jiao Tong University
Wenwen Xia, Xidian University
Gongyu Shi, Shanghai Jiao Tong University
Ming Wan, Shanghai Jiao Tong University
Yuncong Zhang, Shanghai Jiao Tong University
Dawu Gu, Shanghai Jiao Tong University

In this paper, we reconsider the security for CRYSTALS-Dilithium, a lattice-based post-quantum signature scheme standardized by NIST. In their documentation, the authors proved that the security of the signature scheme can be based on the hardness of the following three assumptions: MLWE, MSIS and SelfTargetMSIS. While the first two are standard lattice assumptions with hardness well studied, the authors claimed that the third assumption SelfTargetMSIS can be estimated by the hardness of MSIS (and further into SIS). However, we point out that this is in fact not the case. We give a new algorithm for solving SelfTargetMSIS, by both experimental results and asymptotic complexities, we prove that under specific parameters, solving SelfTargetMSIS might be faster than MSIS. Although our algorithm does not propose a real threat to parameters used in Dilithium, we successfully show that solving SelfTargetMSIS cannot be turned into solving MSIS or MISIS. Furthermore, we define a new variant of MISIS, called sel-MISIS, and show that solving SelfTargetMSIS can only be turned into solving sel-MISIS. We believe that in order to fully understand the concrete hardness of SelfTargetMSIS and prevent potential attacks to Dilithium, the hardness of this new problem needs to be further studied.

Available format(s)
Public-key cryptography
Publication info
Lattice-based cryptography short integer solution problem concrete hardness digital signature
Contact author(s)
wanggxx @ sjtu edu cn
2022-11-21: approved
2022-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Geng Wang and Wenwen Xia and Gongyu Shi and Ming Wan and Yuncong Zhang and Dawu Gu},
      title = {Revisiting the Concrete Hardness of {SelfTargetMSIS} in {CRYSTALS}-Dilithium},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1601},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.