6
$\begingroup$

The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The latter in $P$ implies the former in $P$.

Are there groups where CDH problem is easy and in $P$ while DLOG is difficult and not known to be in $P$?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Your DH problem is the "computational" DH problem. With a suitable number of caveats, the answer is "no", see this post on the Cryptography stack exchange. $\endgroup$ Commented Feb 13, 2022 at 11:32
  • 1
    $\begingroup$ They are equivalent (non-uniformly) in the generic group model, which is the "suitable number of caveats". Iirc one can mostly remove the non-uniformity if one assumes the prime factorization of the group order is known, which is a "reasonable" assumption of DLog-type problems (due to Pollard's Rho algorithm, having an unexpectedly "bad" prime factorization implies attacks, so one typically works over groups of known order + known prime factorization). $\endgroup$ Commented Feb 14, 2022 at 19:59
  • 1
    $\begingroup$ The generic group model is a semi-strong assumption (for example, one can show that certain known $\exp(\sqrt{|G|})$ algorithms for Dlog are optimal in the generic group model), but also for certain classes of groups (elliptic curve groups), the best known Dlog algorithms (+ popular consensus) is that the groups are "generic". This is not true for multiplicative subgroups of finite fields, where index calculus gives one large speedups (in the fixed characteristic case, it can go all the way to quasi-polynomial time attacks... $\endgroup$ Commented Feb 14, 2022 at 20:03
  • 1
    $\begingroup$ ... These are efficient in practice, $\mathbb{F}_{2^{\sim 30,000}}^\times$ has been attacked by academics). $\endgroup$ Commented Feb 14, 2022 at 20:03
  • 1
    $\begingroup$ The result I linked to (discussion of) can be interpreted as evidence for the equivalence over groups of known prime factorization, which is the most common case for DL/CDH by far. This is to say that it seems unlikely you could show inequivalence for groups people care about without doing something like showing those groups are non-generic, which would be a bigger result. I imagine establishing equivalence with less caveats is open though. $\endgroup$ Commented Feb 14, 2022 at 21:29

1 Answer 1

Reset to default
2
$\begingroup$

Some background for this answer:

  1. A computation is non-uniform if, in addition to an input $x$, one gets an "advice string" that depends solely on the length of $x$. One can view this as precomputation, although this advice string need not be computable (this should not be relevant here though). In this answer, non-uniformity is used to ensure one has access to parameters of certain elliptic curves, and potentially a factorization of a certain number.

  2. The generic group model is an abstract model in cryptography where, rather working directly with group elements, one is given oracles for the relevant group operations. Algorithms in the generic group model therefore work for all groups with efficiently-computable operations, and do not exploit the particular structure of any single group. There are lower bounds in the generic group model --- solving DLOG in $\Theta(\exp(\sqrt{\log |G|}))$ operations is provably optimal iirc. The only "mainstream" groups used within cryptography that are plausibly generic are Elliptic Curve groups ($\mathbb{F}_p^\times$ and related groups admit non-generic algorithms that go broadly by the name of "index calculus" algorithms).

The paper you quote there requires $|G|$ to be $\mathsf{polylog}|G|$ smooth according to abstract. Are you sure it applies to cyclic multiplicative group mod p a prime? Please post full answer for this group.

It does not, as $\mathbb{F}_p^\times$ is not thought to be a "generic" group --- one can speed up DLog via appealing to index calculus methods. The paper works in the generic group model, so is mainly applicable to groups we think are generic, e.g. elliptic curve groups.

Still, I will include two of the papers results, as your understanding of the paper from the abstract is wrong, and it can handle the case of $|G| = p$ a large prime.

Here is corollary 5 of the paper

Corollary 5: If the smoothness assumption is true, then there exists a polynomial-time generic algorithm computing discrete logarithms in cyclic groups of order $n$, making calls to a DH oracle for the same group, if and only if all the multiple prime factors of $n$ are of order $(\log n)^{O(1)}$.

This result is non-uniform, and requires a certain number theoretic assumption. It clearly handles the case of $|G| = p$ though.

Removing the smoothness assumption (and I believe the non-uniformity assumption, but I have not carefully read), corollary 7 states that

Corollary 7. Let $P$ be a fixed polynomial, let $G$ be a cyclic group with generator $g$, and let $B := P (\log |G|)$. Then there exists a list of expressions $A(p)$ in $p$ with the following property: if every prime factor $p$ of $|G|$ greater than $B$ is single and if for every such prime factor at least one of the expressions $A(p)$ is $B$-smooth, then breaking the DH protocol in $G$ with respect to $g$ is polynomial-time equivalent to computing discrete logarithms in $G$ to the base $g$. The list contains the following expressions:

  1. $p − 1 , p + 1 , p + 1 \pm 2a$, if $p \equiv 1 (\mod 4)$, where $p = a^2 + b^2$,

  2. $p + 1 \pm 2a, p + 1 \mp a \pm 2b , p + 1 \pm(a + b)$, if $p \equiv 1 \bmod 3$, where $p = a^2 − ab + b^2, a \equiv 2 \bmod 3$, and $b \equiv 0 \bmod 3$,

  3. $\frac{(p^k)^l − 1}{p^k − 1} = (p^k)^{l−1} + · · · + p^k + 1$, where $k, l = (\log p)^{O(1)}$, and $f(p)$, where $f(x) \in \mathbb{Z}[x]$ is a nonconstant polynomial dividing $x^n − 1$ for some $n = O(1)$.

these technical conditions are related to constructions of what the authors call "auxillary groups", which are the non-uniform information the authors need for their reduction.

This is to say that the result can definitely be improved, for example

  1. removing the smoothness assumption for cor. 4, or
  2. relaxing the technical conditions with respect to the construction of auxillary groups,

Of main interest to you though, the work is in the generic group model, and the example you have mentioned in the comments is not a generic group.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oh I see $|G|=p-1$ for the case of multiplicative group mod prime $p$. So it clearly handles Sophie-Germain case of $p-1=2q$ where $q$ is a prime correct? $\endgroup$ Commented Feb 16, 2022 at 0:35
  • 1
    $\begingroup$ No, because the multiplicative group mod $p$ is not a generic group, and this is only in the generic group model. $\endgroup$ Commented Feb 16, 2022 at 0:38
  • $\begingroup$ What is a generic group? Please define it to make your answer complete. $\endgroup$ Commented Feb 16, 2022 at 10:25
  • 1
    $\begingroup$ It means the generic group model. In general, these kinds of things are things you should be able to either look up directly, or look through the papers mentioned (or their references) for. $\endgroup$ Commented Feb 16, 2022 at 19:58
  • 1
    $\begingroup$ If you explain how this generic model relates to standard Turing model of computation (since that is the only point of relevance for poly time) people here will appreciate it. People here are not cryptographers. $\endgroup$ Commented Feb 16, 2022 at 20:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.