Finding collisions of polynomial rolling hashes

A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$).

For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the individual $c_n$ values).

Are there particular values for $c$ that make the probability of collisions between two randomly chosen $a$ greater than $k/2^n$?

I would argue that there are not. For $H(c, a)$ equals evaluating a polynomial (of degree at most $k$) at $a$. Thus, $H_c(x)$ defines a polynomial with degree at most $k$. Let $H_{c,a}(x) = H_c(x) - H_c(a)$; the zeroes of $H_{c,a}$ are precisely the points where $H_c(x) = H_c(a)$, and there can be no more than $k$ such zeroes. Thus, for any non-zero $c$, two randomly chosen $a,a'$ have $H(a) = H(a')$ with probability $\le k/2^n $.

However, this crypto CTF challenge seems to argue certain $c$ do produce collisions, and this solution explains and demonstrates it (unfortunately most of the explanation is in Chinese). Where is my mistake?

This ring has zero divisors so the answer is different than over fields.

Let $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ and let $j$ be the largest nonnegative integer such that $2^j$ divides $gcd(c_1,\ldots,c_k).$

Claim: Let $j$ be as above, then the polynomial $H(a)-H(a')$ can have $k\times 2^{j}$ roots, leading to a collision probability of $$\frac{k}{2^{n-j}}.$$

Proof: If the coefficients of the difference polynomial have a gcd divisible by $2^j$ then all values of the polynomial are in the subset (which is an ideal) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ This means that the difference polynomial is of the form $2^j g(a)$ for some polynomial with gcd equal to 1. Therefore, it is enough for $g(a)$ to take values in $2^{n-j}\mathbb{Z}_{2^n}$ for $2^j g(a)$ to take on the value zero. This means that each zero of $g(a)$ is duplicated $2^j$ times to be a zero of the difference polynomial so the probability that the difference polynomial takes on the value zero is now $$ \frac{k 2^j}{2^n}=\frac{k}{2^{n-j}}. $$

Example from [Magma Calculator][1] of a degree $k=2$ polynomial, which has 2 roots and one where $j=2,$ which has $k 2^j=8$ roots.

code:

Z2to6:=IntegerRing(2^6); Z2to6;
R<a>:=PolynomialRing(Z2to6); R;
{* Z2to6!(a^2+63*a): a in Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a in Z2to6 *};}

output:

Univariate Polynomial Ring in a over IntegerRing(64)
{* 0^^2, 2^^2, 4^^2, 6^^2, 8^^2, 10^^2, 12^^2, 14^^2, 16^^2, 18^^2, 20^^2,
22^^2, 24^^2, 26^^2, 28^^2, 30^^2, 32^^2, 34^^2, 36^^2, 38^^2, 40^^2, 42^^2,
44^^2, 46^^2, 48^^2, 50^^2, 52^^2, 54^^2, 56^^2, 58^^2, 60^^2, 62^^2 *}`
{* 0^^8, 8^^8, 16^^8, 24^^8, 32^^8, 40^^8, 48^^8, 56^^8 *}```

The second polynomial $4(a^2+63a)$ has a gcd of 4 thus it has 8 roots not 2.

The magma list notation 0^^8 means the element 0 appears 8 times in the list.




  [1]: http://magma.maths.usyd.edu.au/calc/