Paper Info
Title
Integer LWE with Non-subgaussian Error and Related Attacks
Abstract
This paper focuses on the security of lattice based Fiat-Shamir signatures in leakage scenarios. More specifically, how to recover the complete private key after obtaining a large number of noisy linear equations without modular about the private key. Such a set of equations can be obtained, for example, in [5], by attacking the rejecting sampling step with a side-channel attack. The paper refers to the mathematical problem of recovering the secret vector from this structure as the ILWE problem and proves that it can be solved by the least squares method. A similar mathematical structure has been obtained in [13] by leaking a single bit at certain specific locations of the randomness. However, the ILWE problem requires the error term to be subgaussian, which is not always the case in practice. This paper therefore extends the original ILWE problem by presenting the non-subgaussian ILWE problem, proving that it can be solved by the least squares method combined with a correction factor, and giving two attack scenarios: an attack with lower bits leakage of randomness than in [13], and a careless implementation attack on the randomness. In the lower bit randomness leakage case, we are able to attack successfully with 2 or 3 bits leakage lower than those in [13] experimentally, and in the careless implementation attack, we are able to recover the private key successfully when the rejection sampling partially fails.
Year
DOI
Venue
2021
10.1007/978-3-030-91356-4_1
INFORMATION SECURITY (ISC 2021)
Keywords
DocType
Volume
Lattice-based cryptography, Fiat-Shamir signature, ILWE problem, Least squares method, Statistical analysis
Conference
13118
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Tianyu Wang112030.07
Yuejun Liu200.34
Jun Xu383.51
Lei Hu469786.91
Yang Tao501.69
Yongbin Zhou601.01