1
$\begingroup$

In reading the following paper,

https://ai2-s2-pdfs.s3.amazonaws.com/35eb/afbaab34223bca50a7be2f5915fddf918fc7.pdf

Generate two primes $p$ and $q$ such that $q|p-1$. Pick a generator $g$ of $Z_p^{*}$. $g$ is declared as public.

$c_1=g^r$ where $r \in Z_q^{*}$

As far as I understand, $g$ is integer ranging from 0 to p. If there is another meaning for $Z_p^{*}$, please let me know.

Given $g,c_1$, find $r$.

Is it discrete logarithm problem? or just integer exponentiation problem?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ fgrieu. Given $g$, $c_1$, is the problem is to find $r$. $\endgroup$
    – myat
    Commented May 22, 2017 at 7:59
  • 1
    $\begingroup$ "$g$ is integer ranging from $0$ to $p$". No, $\mathbb{Z}_p^*$ is the multiplicative subgroup of the ring $(\mathbb{Z}_p,+,\cdot)$ with the usual addition and multiplication. Those are the elements which have a multiplicative inverse, never include the additive neutral element $0$, and in this case are exactly the integers less than $p$ and coprime to $p$. So it's all integers between $0$ and $p$, but neither $0$ nor $p$ are included. And a generator has to generate the entire (sub)group you're talking about. So e.g. $1$ is only a generator of the trivial subgroup $(\{1\},\cdot)$. $\endgroup$
    – tylo
    Commented May 22, 2017 at 12:48

2 Answers 2

Reset to default
1
$\begingroup$

As you can see in their abstract, they are assuming that "the standard Computational Diffie-Hellman problem is intractable", thus this means that you may necessarily break their scheme by solving the Discrete Logarithm problem, since the Computational Diffie-Hellman (CDH) problem can be solved easily if the DLP can be solved.

The CDH problem is the following: for $G$ a cyclic group of order $q$, with $g$ one of its generator, given $(g,g^a,g^b)$ with $a,b \in \{0, \ldots, q-1\}$ randomly chosen, one want to compute the value $g^{ab}$.

If computing discrete logs in $G$ were easy, then the CDH problem would be solved, since one would be able to compute:

  • $b$ by taking the discrete log of $g^b$;
  • $g^{ab}$ by exponentiation: $g^{ab} = (g^a)^b$

However, it is important to note that the CDH and DLP problem are not necessarily equivalent! Hence, it may be possible once to solve the CDH problem without being able to solve the DLP or it may also be possible that both will be proven equivalent some day, as Maurer already proved it to be true under certain conditions regarding the smoothness of integers in given intervals.

So, if you want to consider their scheme as being an instance of the DLP, you may, however it may be simpler than the DLP.

On the other hand, the problem you are stating, being given $c_1, g$, find $r$ for $c_1=g^r \mod p$ is an instance of the DLP.

So yes, you can reverse their public keys directly if the DLP is easy.

Improve this answer
$\endgroup$
1
$\begingroup$

$\mathbb Z_p^*$ is the multiplicative group modulo $p$, that is (since $p$ is prime) $\mathbb Z_p$ less the element $0$ modulo $p$.

Implied or missing in the question's statement and the paper's Setup() procedure is that $g$ is of order $q$; that is, $g$ is such that $q$ is the smallest positive integer $j$ verifying $g^j\equiv1\pmod p$.

Finding $r$ given $g$, $c_1$ is the archetypal discrete logarithm problem. It is believed hard for random parameters and large enough $p$ and $q$ (like, 2048-bit $p$ and 256-bit $q$).

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.