# How can a lattice attack be applied to ECDSA signatures?

The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria.

• Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (the random nonce $k$ used in each signature is decomposed into $k_1$and $k_2$).
• For every ECDSA signature, I can obtain few bits (least significant bits, most significant bits, ...) of the respective $k_1$ and $k_2$.

Is it possible to carry out a lattice attack to gain the value of the underlying secret key ($\alpha$)? If yes, then can you explain the attack in detail?

PS: I have a beginner level understanding of ECDSA and lattices.

• It is a theoretical question. I tried searching if it is possible to do that, and more information on the topic. I searched various research papers and the internet. For example, I have confirmed that a lattice attack can be applied when I have few bits of $k$ for every signature (this is generally the case when GLV method is not used). But in my case I have few bits of $k_1$ and $k_2$. – jsp99 Jun 26 '15 at 21:54
• Yes, this paper is exactly for your question. iacr.org/conferences/asiacrypt2014/… – user31633 Feb 18 '16 at 20:25

Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key $k$ and the private key $a$) to the signing equation $sk-ra\equiv H(m)\pmod q.$ If you have enough signatures (i.e. enough $k_i$) then you construct a linear system $\bmod q$ and then a suitable lattice and if you have enough bits from every $k_i$ and $a$ and enough messages you can solve the CVP problem. Also you can apply Coppersmith method to the signing equation.
• Thank you for the answer. But $k_1$ and $k_2$ in my question do not mean random nonces of different signature instances. Please read my comment below the question. – jsp99 Jul 22 '15 at 10:59
• As far as I know, If you have few bits ( $\ll \sqrt{q})$ from two ephemeral keys there is not any attack. – 111 Jul 22 '15 at 11:41
• it seems like you misunderstood my question/comment. $k_1$ and $k_2$ are not two ephemeral keys. They are related to a single ephemeral key ($k$) by the relation: $k \equiv (k_1 + k_2 \lambda) \mod n$. Here, $\lambda$ is the endomorphism of the curve. – jsp99 Jul 23 '15 at 16:41
• Ok, you have two blocks of contiguous bits of one ephemeral key. You can apply the attacks given by the references I wrote in my answer. But you need enough bits. Almost bits(k1)+bits(k2)$\approx bits(n)/2$ (of course with $n$ here, you mean the prime order of the subgroup generated by a point of your curve, usually in ECDSA is written $q$). – 111 Jul 23 '15 at 21:54