1
$\begingroup$

Since I am not able to comment under the topic, I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power? Also, what can be said about the distribution of exponents a+b modp when b is taken at random from Zp, but a is fixed?

Any help would be appreciated a lot.

$\endgroup$
2
$\begingroup$

It's easier to take the questions out of order.

what can be said about the distribution of exponents a+b mod p when b is taken at random from Zp, but a is fixed?

If $b$ is a uniform independent random value from the range $[0, p-1]$, that is, the probability of each possible value is $1/p$, and $b$ is distributed independently from $a$, then $a+b \bmod p$ is a uniform independent (of $a$) random value from the range $[0, p-1]$; that is, the probability of $a+b \bmod p$ being any possible value from the range is also $1/p$, and information about the distribution of $a$ (such as having it be a fixed value) does not change this.

The easiest way to see this (for a fixed $a$) is to note that, for any target value $c = a+b \bmod p$, there is a unique value of $b = c-a \bmod p$ that must be selected for the value $a+b \bmod p$ to be that value. The probability of $b = c-a \bmod p$ occurring is $1/p$ (because that value is in the range, and we assumed the probability of all values in that range be $1/p$), hence the probability that $c = a+b \bmod p$ is also $1/p$.

With this, your first question is easy:

I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power?

Alice sees either $g^b$ or $g^{a+b}$; an adversary with unlimited computational power can solve the discrete log, however that gives him either $b$ or $a+b$ (for random $b$); both probability distributations are identical, and so he cannot distinguish them.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thank you very much for your help. One last question. Why the value of a must be a fixed value? $\endgroup$ – user178592 Jan 6 at 6:30
  • $\begingroup$ @user178592: it doesn't - the only requirement is that b be distributed independently of a. Assuming a fixed a just make the demonstration easier.. $\endgroup$ – poncho Jan 6 at 14:43

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.