0
$\begingroup$

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!

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

from https://homepages.cwi.nl/~ducas/Thesis/thesis.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Okay I think that I somehow got it . Thank you so much for the clarification ! @LeoDucas $\endgroup$
    – abdul rahman taleb
    Oct 12, 2018 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.