Attacking ECDSA Leaking Discrete Bits with a More Efficient Lattice

A lattice attack on the Elliptic Curve Digital Signature Algorithm (ECDSA) implementation constructs a lattice related to the secret key by utilizing the information leaked and then recovers the secret key by finding a certain short lattice vector. When the information leaked is discrete bits, Fan et al. (CCS 2016) constructed an efficient lattice by translating the problem of recovering the secret key to the Extended Hidden Number Problem (EHNP). Following their works, we propose two new techniques to construct a more efficient lattice which has a lower dimension and a shorter target vector. Moreover, we further improve the success probability of the secret key recovery by adjusting the lattice. Therefore, it is much easier to recover the secret key. Specifically, injecting our techniques into the existing lattice attacks, we recover the secret key with fewer signatures or a higher success probability.