Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Lattice Attacks, ECDSA, Hidden Number Problem, BKZ

Date: received 9 Nov 2021

Contact author: kabe at silicon t u-tokyo ac jp, ikeda at silicon u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20211115:124824 (All versions of this report)

Short URL: ia.cr/2021/1489


[ Cryptology ePrint archive ]