Refining security assessments of quantum-resistant asymmetric encryption standards taking into account the structure of q-ary lattices

Abstract

The article provides a comprehensive analysis of modern quantum-resistant cryptographic standards security based on lattice theory, such as DSTU 8961:2019 ("Skelya"), CRYSTALS-Kyber, and CRYSTALS-Dilithium. These standards are becoming increasingly popular for solving various practical tasks due to their resistance to attacks that can be implemented on quantum computers. As quantum computing gradually transitions from the theoretical to the practical realm, there is an urgent need for the development and improvement of security models capable of addressing these new challenges. This article focuses on applying the cryptanalysis model developed in previous works to specific cryptographic standards based on lattices. Special attention is given to refining security estimates by considering the algebraic structure of q-ary lattices, which form the foundation of the cryptographic problems underlying these standards. It was found that when considering the algebraic structure of q-ary lattices, security estimates differ significantly from those obtained using the GSA model. In particular, for the key encapsulation mechanisms of DSTU 8961:2019 and CRYSTALS-Kyber, the difference between the estimates in these two models can range from 20 to 30 bits of security, with the refined estimates indicating that existing attacks are less effective than previously thought. It was also revealed that for NIST Level 1 security, decoding attacks show better performance compared to embedding attacks, whereas for NIST Level 5 security, the effectiveness of decoding attacks decreases significantly, falling behind embedding attacks. Thus, the results highlight the importance of accounting for the algebraic structure of lattices in obtaining more accurate security assessments. This allows for a better understanding of potential threats and the optimization of existing lattice-based cryptographic transformations.