# Regarding Lattice atttacks on ECDSA with a portion of known bits of the nonce k

I am new in the field of cryptography, and I am having some troubles understanding a concept regarding the lattice dimension needed in the attack on ECDSA using several messages with L known bits of each nonce. In the paper "Recovering Secrets from Prefix-Dependant Leakage"

In Section 5 "Application to ECDSA", the authors stated that if we have a group of size n, and we are able to know k bits of the nonce of each signature, then the number of messages that we need (which is also the dimension of the lattice) is given by: d = n / (k - c), where c = log2(sqrt(πe/2)).

I am not understanding where did they get this relation from, neither where did the constant c come from. I have read many papers but couldn't really identify the origin.

I could be really thankful for your help. Thank you!

• I believe it to be an heuristic bound, see appendix D of this paper – Ruggero Oct 12 '18 at 8:14
• Thank you so much ! This is exactly what I have been looking for ! @Ruggero – abdul rahman taleb Oct 12 '18 at 11:10

## 1 Answer

The constant is derived from the so-called Gaussian Heuristic, which is used to predict the expected length of the shortest vector of a random lattice. For the attack to work, one must ensure that the special vector that he is looking for will be the shortest, so that it can be found. We therefore compare the length of that to-be-found vector with the expected length of the shortest lattice vector. • Okay I think that I somehow got it . Thank you so much for the clarification ! @LeoDucas – abdul rahman taleb Oct 12 '18 at 11:12