Is it possible to solve the Hidden Number Problem in extension fields? In particular in $GF(2^n)$?
Let's suppose an attacker knows some least/most significant bits of $r_i = a_i \times k$ in a given field $GF(2^n)$, for many uniformly distributed and known $a_i$ and a fixed and unknown $k$. Is it possible to recover $k$ ?
This is, as far as I know, an instance of the Hidden Number Problem originally introduced by Boneh and Venkatesan, used mainly to break digital signature schemes provided several signatures and partial knowledge of the respective nonces.
As far as I know HNP has always been applied in $GF(p)$, and furthermore the technique used to solve it, through Lattices and Closest Vector Problem, can't be easily adapted, IMHO, to $GF(2^n)$.
Rationale behind the question (not required for answering it):
I was comparing the authentications of GCM and Poly1305 in a specific, purely hypothetical, scenario where the attacker gets some knowledge of bits of the result of the authentication function, prior to the final addition of the encrypted nonce.
Let's assume we have single block messages.
Poly1305 authentication (without addition of encrypted nonce) is just: $(c\times r)\mod {2^{130}-5}$ where $c$ is the message block and $r$ is the authentication key. I can see how to apply HNP to solve for $r$ in this case.
But GCM performs (I'm assuming to use an HW accelerator so that I can cheat in providing the final message with the aad and payload sizes): $ (c\times h) \mod {x^{128}+x^7+x^2+x+1}$ where $h$ is the GHASH key. I don't see how to solve for $h$, having several partial information of the result for different and known $c$.