Let's $\mathbb{F}_p$ be a finite field where $p$ is a large prime number(e.g. 256-bit)

I know if the probability that an element picked from the field is $\frac{1}{p-1}$ we say the element is picked uniformly at random.

Question: In security context can we say the element is uniformly at random even if its probability is $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $?

  • $\begingroup$ hint: for a field where DLP is hard you need to chose p to be of size 2048 bits and larger. $\endgroup$ – SEJPM Sep 7 '15 at 18:53
  • $\begingroup$ Are you only changing the probability of a single element? What happens to the probability of the others? $\endgroup$ – otus Sep 7 '15 at 18:53
  • $\begingroup$ Where does the $-\frac{1}{(p-1)^2}$ part come from? $\endgroup$ – SEJPM Sep 7 '15 at 18:58
  • $\begingroup$ @otus Of course the other probability would change. But the change is very small. In my scheme if a value becomes a uniformly random I can detect it. So I need to know still with this probability I can use my scheme. This probability comes from calculating distribution of an element when it is modified. See this:math.stackexchange.com/questions/1424328/… $\endgroup$ – user13676 Sep 7 '15 at 18:58
  • $\begingroup$ @SEJPM Yes, I'm not relying on DLP problem. $\endgroup$ – user13676 Sep 7 '15 at 19:07

$\mathbb{F}_p$ actually has p elements. Hence, an element would be picked uniformly at random if every element was chosen with probability $1/p$. Already if one element is chosen with probability $\frac{1}{p-1}$ this is not a uniform distribution anymore. Depending on the size of $p$ you can argue that the distribution is statistically indistinguishable from a uniformly random one.

  • $\begingroup$ Well, you need to exclude $0$ if you need some multiplicative properties meaning $\mathbb F_p^*$ would indeed "only" have $p-1$ elements... $\endgroup$ – SEJPM Sep 7 '15 at 18:57
  • 1
    $\begingroup$ True, but then you should edit the question to say $\mathbb{F}^*_p$. $\endgroup$ – mephisto Sep 7 '15 at 23:06

Let's take a set with $p$ uniquely defined elements. A uniformly random distribution is that every element has a chance $1/p$ to be picked. What if the last element is never picked and the rest are with an uniform probability of $(p-1)^{-1}$?

If you see $k$ items you expect to see the last one with probability $1-(1-1/n)^k$. When $n$ is large, that is approximately $k/n$. To have a $2^{-b}$ chance of noticing the non-uniformity you need to see about $\frac{n}{2^b}$ items.

So with a 256-bit field, you can be missing an item from the distribution and see $2^{128}$ and still have no idea with a probability of $2^{-128}$. If the probability of the element is not zero, but only slightly smaller than the uniform probability would be, it is even more difficult. Halve the probability and you need to see double the elements. Multiply by $\frac{p-1}{p}$, which is about what you are doing, and you need to see $\frac{p^2}{2^b}$ to have a $2^{-b}$ probability of detecting it.

In conclusion, you can't notice that the probability of one element is lower than the uniform probability. You can't even notice if it's zero. You need to lower the change of e.g. $2^{192}$ items to zero before it can be noticed with a realistic number of samples.


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.