1
$\begingroup$

Let $\mathbb{Z}_p$ be a prime field, $a, b$ be two random elements independently drawn from $\mathbb{Z}_p^*$, and $$ c = a* b \mod p,$$ is $c$ uniformly random? and why?

How is this question related to the discrete-log assumption? Because if $a =b$, then my understanding is that the discrete-log assumption asserts $$ c =a^n \mod p$$ is indeed uniformly random.

$\endgroup$

2 Answers 2

3
$\begingroup$

Let $\mathbb{Z}_p$ be a prime field, $a, b$ be two random elements independently drawn from $\mathbb{Z}_p^*$, and $$ c = a* b \mod p,$$ is $c$ uniformly random?

No; if either $a = 0$ or $b = 0$, then $c = 0$. Out of the $p^2$ possible pairs $(a, b)$, that gives $2p-1$ pairs that results in 0. As the probability of each possible pair is equal, that is, $p^{-2}$, that gives a probability of a 0 output to be $2/p - 1/p^2$, which is larger than the probability $1/p$ it would have if $c$ was uniformly distributed.

Now, if we modify the distribution so that $a, b$ were uniformly and independently distributed over nonzero values, then it turns out that $c$ would be uniformly distributed over nonzero values.

Because if $a =b$, then my understanding is that the discrete-log assumption asserts $$ c =a^n \mod p$$ is indeed uniformly random.

Well, I don't know what $a=b$ has to do with it, and that assertion would appear to be unrelated to the discrete-log problem. However, if $n$ (which you have not specified) is relatively prime to $p-1$, then yes, $c$ would be uniformly distributed (from the simple observation that $a^n \bmod p$ is a permutation in that case), and if $n$ is not relatively prime to $p-1$, then it is not.

$\endgroup$
5
  • 1
    $\begingroup$ $a, b$ are independently drawn from $\mathbb{Z}_p^{*}$, not $\mathbb{Z}_p$, so they are not zero. $\endgroup$
    – Jason
    Commented Sep 10 at 11:22
  • $\begingroup$ "Now, if we modify the distribution so that a,b were uniformly and independently distributed over nonzero values, then it turns out that c would be uniformly distributed over nonzero values", Why? $\endgroup$
    – Jason
    Commented Sep 10 at 11:25
  • $\begingroup$ @Jason: oops, I missed the *. And, in that case, for any value $c$, there are exactly $p-1$ pairs $(a, b)$ s.t. $ab = c \bmod p$. There are $(p-1)^2$ such pairs total, and so the probability for any such pair is exactly $(p-1) / (p-1)^2 = (p-1)^{-1}$. Actually, it holds if we assume that one of the two (say, $a$) is uniform and independent of $b$; the distribution of $b$ can be anything. $\endgroup$
    – poncho
    Commented Sep 10 at 11:34
  • $\begingroup$ Thanks, just try to visualize what you said: think of the group table of $\mathbb{Z}_p^{*}$, there is only one $c$ in each column and each row, so $c$ is uniformly random! $\endgroup$
    – Jason
    Commented Sep 10 at 11:43
  • 1
    $\begingroup$ @Jason: yup. that is exactly correct. And, it's not only true for prime fields, it is true for any finite field. $\endgroup$
    – poncho
    Commented Sep 10 at 11:46
1
$\begingroup$

No. For example, let $a$ be a uniformly sampled element and let $b=a$ in which case $c=a^2\mod p$ is a quadratic residue and only half of the elements of $\mathbb Z_p^\times$ are quadratic residues.

You may wish to rephrase the question using the word "independent".

This question is not related to whether the discrete logarithm is hard to compute.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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