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?
Improve this question
$\endgroup$
2
  • $\begingroup$ Theorem 2 holds trivially. Those distributions are identical. $\endgroup$
    – Maeher
    Commented Jul 13, 2020 at 18:32
  • $\begingroup$ Is this homework? Note that $b^{-1}$ calculated with $\varphi(p)$. So you can consider it as $x$. $\endgroup$
    – kelalaka
    Commented Jul 13, 2020 at 19:25

1 Answer 1

Reset to default
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").

Improve this answer
$\endgroup$

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.