1
$\begingroup$

$G$ is a multiplicative cyclic group of a large prime order $p$ and $g$ is a generator of $G$

  • Theorem 1: Given $g^{b^{-1}}$ and $ab$, it's hard to compute $a$ or $b$, where $a$ and $b$ are randomly picked in $Z_p$
  • Theorem 2: It's hard to distinguish between the following distributions: $(g^{b^{-1}},ab)$ and $(g^{b^{-1}},z)$ where $a$, $b$, and $z$ are randomly picked in $Z_p$
Is there any proof that these two theorems hold or do not hold?
$\endgroup$
2
  • $\begingroup$ Theorem 2 holds trivially. Those distributions are identical. $\endgroup$ – Maeher Jul 13 '20 at 18:32
  • $\begingroup$ Is this homework? Note that $b^{-1}$ calculated with $\varphi(p)$. So you can consider it as $x$. $\endgroup$ – kelalaka Jul 13 '20 at 19:25
1
$\begingroup$

Theorem 1 is not true in general; consider a group where the discrete log problem is easy. On the other hand, it is true if we assume that the discrete log problem in $G$ is hard (that is, if we can recover either $a$ or $b$ given $g^{b^{-1}}, ab$, then we can use that as an Oracle to recover $x$ given $g^x$)

Theorem 2 is true; for any $b \ne 0$ (and we know $b \ne 0$ if $b^{-1}$ exists), the distributions of $ab$ and $z$ (for random $a, z$) are identical (and hence "hard to distinguish").

$\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.