4
$\begingroup$

In one proof I show that, given a cyclic group $Z_{p}^{*}$ where $p$ is prime, and a set of information $X$ computing $y\in Z_{p}^{*}$ is as difficult as solving Computational Diffie Hellman (CDH) problem.

In another proof can I make the argument that as transformation $X \rightarrow y$ is proven to be CDH, given $X$, distinguishing between any random $r\in Z_{p}^{*}$ from $y$ is as difficult as Decisional Diffie Hellman (DDH).

$\endgroup$

1 Answer 1

1
$\begingroup$

First, it might be that CDH is hard, yet the corresponding DDH is easy. In fact, this is generally the case in $\mathbb{Z}_p^*$, so you should be careful about that. See the footnote.

Second, there is a trivial counter example to your question: let $g$ be a generator of the subgroup of squares modulo $p$ (assume for simplicity that $p$ is a safe prime). Then, computing $g^{ab} \bmod p$ given $X = {g^a, g^b}$, for random $a,b$, is infeasible assuming the hardness of CDH over the subgroup of squares (which is implied by the hardness of CDH over $\mathbb{Z}_p^*$). Now, define $y$ as the value obtained by replacing the least significant bit of $g^{ab}\bmod p$ with zero. Computing $y$ from $X = {g^a, g^b}$ is as hard as CDH over the subgroup of squares (the reduction looses a factor 2). Yet, distinguishing $y$ from a random element is obviously not implied by DDH over this group (I focused on the subgroup of squares because DDH is broken over $\mathbb{Z}_p^*$, see below).

== Footnote ==

It is easy to distinguish $g^{ab} = y \bmod p$ from a random element $r$ of $\mathbb{Z}_p^*$: with probability 1/2, $r$ is not a square, and this is easy to check by computing the Legendre symbol (in contrast, $y$ is always a square).

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