4
$\begingroup$

I need my code to generate random elements from $GF(p)$ ($F_p$ or $Z_p$, if you will).

The Crypto API I have available provides one with random bit strings. To tailor that to my needs, I can think of two possible solutions, each with its downside.

Solution 1: Sample $\lceil\log_2p\rceil$ bits, and reduce its corresponding integer modulo $p$ or $2^{\lfloor\log_2p\rfloor}$. This is efficient and easy but the resulting distribution is not uniform.

Solution 2: Repeatedly sample $\lceil\log_2p\rceil$ bits until the output integer is less than $p$. This gives a nice uniform distribution but is not constant time and may leak something about the internals of the random generator.

Is either of these a good idea, or is another method commonly practiced?


Edit: The accepted answer works for any set of elements (not necessarily a field) of any size (not necessarily prime).

$\endgroup$
5
$\begingroup$

is another method commonly practiced?

Sample $\lceil \log_2p \rceil+64$ bits, and reduce its corresponding integer modulo $p$.

There will still be a bias, but it is tiny. And, assuming that you use a constant time modulo operation, it's constant time...

$\endgroup$
  • 1
    $\begingroup$ Thanks. Is there a formal analysis of this method? $\endgroup$ – Arya Pourtabatabaie Sep 13 '18 at 20:58
  • 1
    $\begingroup$ @AryaPourtabatabaie: I'm not sure if anyone bothered publishing anything, but it's fairly straightforward to show that someone looking at the outputs cannot distinguish it from a random unbiased output stream with much less than $2^{128}$ outputs $\endgroup$ – poncho Sep 13 '18 at 21:03
  • $\begingroup$ One could say for $n=r \mod p$, $x\in_RZ_n$ and $t=x \mod p$ we have: $P\{t=t_0|t_0<r\}=\frac{n-r}n\times \frac 1 p + \frac 1 n$ and $P\{t=t_0|t_0\geq r\}=\frac{n-r}n\times \frac 1 p$. These probabilities converge to each other and to $\frac 1 p$ as $n$ grows, giving us statistical indistinguishability. $\endgroup$ – Arya Pourtabatabaie Sep 13 '18 at 21:33
1
$\begingroup$

Hi @AryaPourtabatabaie

I've been having the exact same problem and would like to find a way to generate a distribution statistically close to uniform on $F_p$. This is my analysis of the above scheme.

I have a prime $p$ and random strings with length $n$. Let $S = \{0,1\}^n$ and define the function

$H : S \rightarrow F_p, ~~~ H(x) \mapsto x \bmod p$

Define $U_p$ to be the uniform distribution over $F_p$, and let $H_p$ mean the distribution of the output of $H$ when its inputs are uniformly distributed.

I want to compute the statistical distance between $U_p$ and $H_p$, $\Delta(U_p, H_p)$.

Observe that if $p$ evenly divided $S$, then all residue classes would have the same number of elements, that is, $|S|/p$. But because $p$ is a large prime and $S$ is a power of $2$, this will never be the case. There will be a set of residues that will be hit once more than the others, namely those less than $|S| \bmod p$. To compute the statistical distance, it is enough to compute the probability difference of these residues in both distributions.

Define: $m = |S| \bmod p$

$k = \lfloor ~|S|/p~ \rfloor$

We can partition $F_p$ in two sets:

$A = \{0, \ldots, m-1\}$

$B = \{m, \ldots, p-1\}$

The residues in $A$ are each generated by $k+1$ elements of $S$, while the residues in $B$ are generated by $k$ elements. You can see that

$U_p(x) < H_p(x), \mbox{ for } x \in A$

$U_p(x) > H_p(x), \mbox{ for } x \in B$

Specifically:

$U_p(x) = 1/p$

$H_p(x | x \in A) = (k+1)/|S|$

$H_p(x | x \in B) = k/|S|$

Then,

$\Delta(U_p, H_p) = \Pr_{H_p}(A) - \Pr_{U_p}(A) = m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right)$

The crucial part is this:

$m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right) \leq$

$m \cdot \left(\frac{|S|/p + 1}{|S|} - \frac{1}{p} \right) = $

$(|S| \bmod p) \cdot \frac{1}{|S|} <$

$ \frac{p}{|S|} $

And now you can see, that if you fix your $p$, you can play around with the length of the bit strings that you need. If you use random strings of a similar size to $p$, you'll likely not get a decently small distance. But @poncho's suggestion will guarantee that you have at most $2^{-64}$ statistical distance, and you can control how low you can get.

If you go, for example, for standard hash lengths, you have 224, 256, 384, 512. For a prime around 256 bits, for example, take the next hash length at 384 and you get a statistical distance of at most $2^{-128}$ which is comfortably safe for today's standards.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.