Can we solve the Hidden Number Problem in $GF(2^n)$? 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$.
Yes, it appears that it can be solved in practical time in $GF(2^n)$, if the attacker gets $n+\epsilon$ random $a_i$ values, even if he gets a single bit of the $a_i \times k$ values.

The chief observation is that the mapping from $a_i$ to bit $j$ of $a_i \times k$ (which I'll refer to as $bit_j(a_i \times k)$) is bitwise linear (for constant $j$, $k$).

So, assuming that we have $a_i$ and the corresponding $bit_m(a_i \times k)$ values (for some known $m$), our first step is to find $n$ linear independent $a_i$ values (which, given $n+\epsilon$ random $a_i$ values, we'll have with good probability); we view this as a set of $n$ linear equations, and solve them in $O(n^3)$ time, giving us the mapping between any value $a$ and $bit_m(a \times k)$

Now, for polynomial representations of $GF(2^n)$, for every $i, j$ pair, there is a constant $c_{i,j}$ where $bit_i(a) = bit_j(a \times c_{i,j})$ for all $a$.

This observation allows us to find the linear mapping of $bit_n(a \times k)$ for any $n$, as $bit_n(a \times k) = bit_m(a \times k \times c_{n,m}) = bit_m( (a \times c_{n,m} ) \times k )$; in other words, to perform this mapping, we multiply the vector by the constant $c_{n,m}$, and then apply the mapping we already know (both of which are linear operations).

The result of this are $n$ linear maps giving us all $n$ bits of the product.  Then, we can solve these $n$ linear maps for the input that gives a 1 bit for the lsbit map, and 0 for the rest; the solution for this is $k^{-1}$, which immediately gives us the value for $k$.

I suspect that there are signficantly more efficient ways to solve this; however this algorithm should be enough to answer the question.