Biased nonce lattice attack (hidden number problem)

Nonce reuse is broken by two equations. Nonce bias - where each nonce is merely a bit short, or shares a few known high bits - leaks nothing to algebra but everything to lattices. This is the attack behind several real-world wallet key recoveries, where signing devices produced nonces with a handful of predictable bits.

From signatures to a lattice

Each signature gives s = k^-1(h + r*d) mod n, which rearranges into k = s^-1*h + s^-1*r*d. If k is known to be small - say under 2^248 on a 256-bit curve because the top 8 bits are zero - then each signature is a statement that a particular linear function of the unknown d is unusually small. Stack many such statements as rows of a matrix and the true d corresponds to a short vector in the resulting lattice. LLL finds it.

• Bits leaked versus signatures needed - roughly, the fewer bits you know, the more signatures. 8 known bits needs a few dozen; 4 bits needs low hundreds; 1 bit needs thousands and careful lattice construction.
• All signatures must use the same private key - the whole point is that d is the shared unknown.
• Scaling matters. The lattice basis must be weighted so the target vector is genuinely the shortest; a badly scaled basis returns a short vector that is not your key.