Estimating the Effectiveness of Lattice Attacks

Kotaro Abe; Makoto Ikeda

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 Attacks ECDSA Hidden Number Problem BKZ
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},
      note = {\url{https://eprint.iacr.org/2021/1489}},
      url = {https://eprint.iacr.org/2021/1489}
}