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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/1489}},
      url = {https://eprint.iacr.org/2021/1489}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.