MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.