.png){kind=icon}
Return
A Dimension-reduction Attack on Shortest Vector Problem Using Hints
.png){kind=icon}
PRE
AI
DOI：10.11999/jeit251277.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Objective Cryptographic algorithms based on the Learning With Errors (LWE) problem and its variants are widely used, including the key encapsulation mechanism Kyber and the digital signature scheme Dilithium. In many applications, the LWE secret is a short vector. Therefore, reducing LWE to the Shortest Vector Problem (SVP) is a common approach to cryptanalysis. Traditional SVP algorithms, including enumeration, lattice sieving, and lattice basis reduction, become difficult to apply directly in high-dimensional lattices because of their high computational cost. With the use of side-channel attacks, hints about the secret vector provide a new way to solve SVP. This paper proposes a dimension-reduction attack based on such hints. The method uses hints to reduce the problem dimension, thereby extending the practical range of enumeration and sieving. Methods Two types of hints are analyzed: integer hints and modular hints. For integer hints, which provide exact inner-product information about the shortest vector, the problem is formulated as a system of integer equations. The solution space of this system is then used to represent the shortest vector in a shorter linear form. Hermite normal form and Gaussian elimination are applied to obtain a particular solution and a fundamental solution system. This representation reduces the number of unknown coefficients that must be searched in enumeration or sampled in sieving. Thus, the search space is reduced, and the original SVP instance is transformed into a lower-dimensional problem. For modular hints, which provide inner-product information about the shortest vector modulo an integer, a conversion mechanism based on Coppersmith's lemma is developed. For common-modulus modular equations, Lenstra-Lenstra-Lov & aacute;sz (LLL) lattice basis reduction is first used to reduce the norms of row vectors. Gaussian elimination is then applied to decrease the number of nonzero terms. Each resulting modular equation is screened according to Coppersmith's lemma. Equations that satisfy the conversion condition are transformed into integer equations. For non-common-modulus modular equations, the moduli are first factorized into prime-power moduli. Equations with the same modulus are grouped and processed in the same manner. The resulting integer equations are then solved using the dimension-reduction enumeration or sieving method. Results and Discussions To evaluate the proposed dimension-reduction attack, the enumeration-based and sieving-based algorithms are compared with the lattice basis reduction algorithm in Algorithm 5 in terms of runtime and solution exactness. The effect of key parameters on dimension reduction is first analyzed. These parameters include the number of screening rounds (Fig. 2), the small-root bound (Fig. 3), and the modulus size ( Fig. 4). The conversion efficiency of Algorithm 3 under different parameter settings is summarized in Table 1. The results show that more screening rounds generally improve the reduction effect, but this improvement has a saturation point. Beyond this point, additional rounds provide limited benefit. Finally, the computational efficiency of the proposed methods is compared with that of lattice basis reduction (Fig. 5). The results show that the computational cost of enumeration and sieving increases rapidly with dimension. However, up to dimension 90, the dimension-reduction attack can still use hints to reduce the dimension and obtain exact solutions more efficiently. Lattice basis reduction shows a slower increase in runtime as the dimension grows and is therefore more suitable for higher-dimensional SVP instances. Conclusions The proposed dimension-reduction attack provides a simple and effective method for solving SVP using hints. For integer hints, the solution space of the corresponding equation system is used to reduce the number of variables in enumeration and sieving. For modular hints, Coppersmith's lemma is used to convert selected modular equations into integer equations, reducing the problem to the integer-hint case. The experiments show that, when sufficient hints are available, the method can effectively reduce the lattice dimension and extend the practical range of enumeration and sieving. Compared with lattice basis reduction, enumeration and sieving after dimension reduction can provide exact solutions within their applicable dimension range. Although the reduction effect tends to saturate as the number of hints increases, a moderate number of hints is sufficient to achieve effective dimension reduction. These results indicate that hint-based dimension-reduction attacks offer a practical route for exact SVP solving and provide useful evidence for the security evaluation of lattice-based cryptographic schemes.
Keywords:
Learning With Errors (LWE)
Shortest Vector Problem (SVP)
Hints
Dimension-reduction attack
Journal
J
IF:
0
Papers:
203
Citations:
0
Organization
Cited Papers
No cited papers available