Paper 2021/1489
Estimating the Effectiveness of Lattice Attacks
Kotaro Abe and Makoto Ikeda
Abstract
Lattice attacks are threats to (EC)DSA and have been used in cryptanalysis. In lattice attacks, a few bits of nonce leaks in multiple signatures are sufficient to recover the secret key. Currently, the BKZ algorithm is frequently used as a lattice reduction algorithm for lattice attacks, and there are many reports on the conditions for successful attacks. However, experimental attacks using the BKZ algorithm have only shown results for specific key lengths, and it is not clear how the conditions change as the key length changes. In this study, we conducted some experiments to simulate lattice attacks on P256, P384, and P521 and confirmed that attacks on P256 with 3 bits nonce leak, P384 with 4 bits nonce leak, and P521 with 5 bits nonce leak are feasible. The result for P521 is a new record. We also investigated in detail the reasons for the failure of the attacks and proposed a model to estimate the feasibility of lattice attacks using the BKZ algorithm. We believe that this model can be used to estimate the effectiveness of lattice attacks when the key length is changed.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Lattice AttacksECDSAHidden Number ProblemBKZ
- Contact author(s)
-
kabe @ silicon t u-tokyo ac jp
ikeda @ silicon u-tokyo ac jp - History
- 2021-11-15: received
- Short URL
- https://ia.cr/2021/1489
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1489, author = {Kotaro Abe and Makoto Ikeda}, title = {Estimating the Effectiveness of Lattice Attacks}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1489}, year = {2021}, url = {https://eprint.iacr.org/2021/1489} }