### Revisiting the Concrete Hardness of SelfTargetMSIS in CRYSTALS-Dilithium

##### Abstract

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)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Lattice-based cryptography short integer solution problem concrete hardness digital signature
Contact author(s)
wanggxx @ sjtu edu cn
History
2022-11-21: approved
See all versions
Short URL
https://ia.cr/2022/1601

CC BY

BibTeX

@misc{cryptoeprint:2022/1601,
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{https://eprint.iacr.org/2022/1601}},
url = {https://eprint.iacr.org/2022/1601}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.