(EC)DSA partial knowledge of nonces and existential forgery with with structured nonces

[Georgi Guninski]

(EC)DSA partial knowledge of nonces and existential forgery with with structured nonces 

There are attacks against the private key of (EC)DSA when partial
knowledge of the nonces $k$ is known, e.g. least significant bits [1]
or shared bits [2].

On the other hand, existential forgery with structured nonces is
possible. In DSA the public key is (p,q,g,y=g^x). To forge a
signature (r,s) of integer $h$ for all integers a,b != 0 set:
r=(g^a y^b mod p) mod q
s=r/b mod q
h=a s mod q

Since y=g^x mod p, the unknown nonce is $k=a + b x$ where $x$ is the
private key. If $b=1, a=a'+2^l a''$ and we brute force the $l$ LSBs of
$x$, we can generate efficiently many messages with known LSBs (a' + (x
mod 2^l)), which appears in the favorable case the unconditional [1].

Similar existential forgery exists for ECDSA.

Forgeries were tested in practice.

Could this approach give subexponential algorithm for breaking the
private key, possibly under other assumptions?

[1] appears to be deterministic and the abstract starts:
|We present a polynomial-time algorithm that provably recovers the
|signer's secret DSA key when a few bits of the random nonces k (used at each
|signature generation) are known for a number of DSA signatures at most linear in
|log q

[1] The Insecurity of the Digital Signature Algorithm with
Partially Known Nonces
[2] Attacking (EC)DSA Given Only an Implicit Hint