# Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$.

# Problem

Let $q$ be some prime number. Let $k$ be some positive integer and $n = 2^k$, such that $2n$ divides $q-1$. Let $z$ be a $n$-root of $-1$ in $\mathbb{F}_q$ ($z^{n} = -1$). The $n$-roots of $-1$ are $z,z^3,\dotsc,z^{2n-1}$.

We would like to prove or disprove that, if $c_0,\dotsc,c_{n-1}$ are drawn independently and uniformly at random in $\{0,1\}$ (or $\{-1,0,1\}$, or more generally any "small" set), then $c_0 + c_1 z + \dotsb + c_{n-1} z^{n-1}$ is close to uniform. Let us write $\vec{z} = (1,z,\dotsb,z^{n-1})$ and $\vec{c} = (c_0,\dotsb,c_{n-1})$. Then $c_0 + c_1 z + \dotsb + c_{n-1} z^{n-1} = \vec{c} \cdot \vec{z}$

More precisely, we would like to get a concrete bound on the bias of the distribution. Given some concrete $n$ and $q$ (in practice, $n=512$ and $q$ is a prime of about 128 bits), we would like to check whether: $$\Pr_{\vec{c}}(\vec{c} \cdot \vec{z} = x) \le \frac{1}{q} + \varepsilon,$$ for all $x \in \mathbb{F}_q$ and all roots $z$ of $-1$, and with $\varepsilon = 2^{-128}$ in practice. Ideally, we would like to prove that this holds for any $q$ and $n$ verifying some properties easy to check (for a computer).

# What we have found

We manage to prove this result if $c_i \in \{-1,0,1\}$ and if $3$ is a root of $-1$. We also show that if $1,z,\dotsb,z^n$ is "uniform" in $\mathbb{F}_q$, then the result is also true.

## Solution when 3 is a $n$-root and $c_i \in \{-1,0,1\}$

This result is easy to prove, if $c_i \in \{-1,0,1\}$ and if $3$ is a root of $-1$. For $z=3$, $\vec{c} \cdot \vec{z} + (1+z+\dotsb+z^{n-1})$ (without reduction modulo $q$) is a random integer between $0$ and $3^n-1$, because $(c_0 \dotsb c_{n-1})$ represents this number in base $3$. Therefore, modulo $q$, this number is very close to uniform. This prove the property for $z=3$. Then, let $z$ be an arbitrary $n$-root of $-1$. $z$ can be written $z = 3^{2\ell+1}$. Since $z^{n+j} = -z^j$, $(z^{n+j})^2 = (z^{j})^2$ and $j \mapsto j \cdot (2\ell+1) \bmod n$ is a permutation, the sets $\{1^2,z^2,\dotsb,(z^{n-1})^2\}$ and $\{1^2,3^2,\dotsb,(3^{n-1})^2\}$ are equal. Finally, we get that the sets $\{1,z,\dotsb,(z^{n-1})\}$ and $\{1,3,\dotsb,(3^{n-1})\}$ are equal up to the sign of the values, which proves that the distribution of $c_0 + c_1 z + \dotsb + c_{n-1} z^{n-1}$ is equal to the one of $c_0 + c_1 3 + \dotsb + c_{n-1} 3^{n-1}$.

## Link with the uniformity of $\{1,z,\dots,z^{n-1}\}$

Let us now consider the case $c_i \in \{0,1\}$. In this case, for all $x \in \mathbb{F}_q$, we have:

$$2^n \Pr_{\vec{c} \in \{0,1\}^n}(\vec{c}\cdot\vec{z} = x) = \sum_{\substack{\vec{c}\in \{0,1\}^n \\ \vec{c} \cdot \vec{z} = x}} 1 = \sum_{\vec{c} \in \{0,1\}^n} \frac{1}{q} \sum_{r \in \mathbb{F}_q} e^{2i\pi r \frac{\vec{c} \cdot \vec{z} - x}{q}} = \sum_{r \in \mathbb{F}_q} f(r) e^{\frac{-2i\pi rx}{q}},$$ with $f(r) = \frac{1}{q} \sum_{\vec{c}} e^{2i \pi r \frac{\vec{c} \cdot \vec{z}}{q}}$. Therefore: $$2^n \Pr_{\vec{c} \in \{0,1\}^n}(\vec{c}\cdot\vec{z} = x) \le \sum_{r \in \mathbb{F}^*_q} |f(r)| + \frac{2^n}{q}.$$

$f(r)$ can be seen as the Fourier transform of the multi-set containing the $\vec{c} \cdot \vec{z}$'s.

And we just need to bound $|f(r)|$ for all $r \neq 0$. More precisely, we would like to have $|f(r)| \le 2^{-128} / q$.

Unfortunately, we did not manage to bound $|f(r)|$. We only got: $$f(r) = \frac{1}{q} \sum_{c_0 \in \{0,1\}} e^{2i \pi r \frac{c_0 \cdot z^0}{q}} \sum_{c_1 \in \{0,1\}} e^{2i \pi r \frac{c_1 \cdot z^1}{q}} \dotsb = \frac{1}{q} \prod_{j=0}^{n-1} (1+e^{2i \pi r \frac{z^j}{q}}),$$ so $$f(r) = \frac{2^n}{q} e^{2i\pi r \frac{1+z+\dotsb+z^{n-1}}{2}} \prod_{j=0}^{n-1} \cos\left(\pi \frac{r z^j}{q}\right),$$ and $$|f(r)| = \frac{2^n}{q} \prod_{j=0}^{n-1} \left|\cos\left(\pi \frac{r z^j}{q}\right)\right|.$$

We remark that $|f(r)|$ does not depend on $z$, since, as we have seen before, the sets $\{1,\dotsc,z^{n-1}\}$ (for each $z$ which is a $n$-root of $-1$) are equal up to the sign of the values.

Intuitively, if, for all $r\neq 0$, not too many $r z^j$ (for $j=0,\dots,n-1$) are close to $0$ (modulo $q$, where values modulo $q$ are supposed to be between $-q/2$ and $q/2$), there will be enough small $\left|\cos\left(\pi \frac{r z^j}{q}\right)\right|$ in the big product to make $|f(r)|$ small enough.

Unfortunately, we did not manage to get a concrete bound. We found some articles on the uniformity of the distribution of subgroups of $\mathbb{F}_q$ such as:

Bourgain, J. (2009). On the distribution of the residues of small multiplicative subgroups of $\mathbb {F} _p$. Israel Journal of Mathematics, 172(1), 61-74.

If such a bound were concrete, this would help us to bound $|f(r)|$, since $\{1,z,\dots,z^{2n-1}\}$ is a multiplicative subgroup of $\mathbb{F}_q$.

We also notice that computing $|f(r)|$ can be done for small $q$. We have done it for some cases, and we always got very small $|f(r)|$ (i.e., $<2^{-400}$) for $n=512$ and $q \approx 10000$. But for big $q$ ($128$ bits), it is not possible to compute $|f(r)|$ directly.

-