<p>Dan Boneh's <a href="http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf">survey article on the decisional Diffie Hellman problem</a> lists several candidate groups for which the DDH problem is hard, reproduced here:</p>

<blockquote>
  <ol>
  <li>Let $p=2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z}^*_p$. It is a cyclic group of prime order. This family of groups is parameterized by $p$.</li>
  <li>More generally, let $p = aq+1$ where both $p$ and $q$ are prime and $q &gt; p^{1/10}$. Let $Q_{p,q}$ be the subgroup of $\mathbb{Z}_p^*$ of order $q$. This family of groups is parameterized by both $p$ and $q$.</li>
  <li>Let $N=pq$ where $p,q,\frac{p-1}2,\frac{q-1}2$ are prime. Let $T$ be the cyclic subgroup of order $(p-1)(q-1)$. Although $T$ does not have prime order, DDH is believed to be intractable. The group is parameterized by $N$.</li>
  <li>Let $p$ be a prime and $E_{a,b}/\mathbb{F}_p$ be an elliptic curve where $|E_{a,b}|$ is prime. The group is parameterized by $p,a,b$.</li>
  <li>Let $p$ be a prime and $J$ be a Jacobian of a hyper elliptic curve over $\mathbb{F}_p$ with a prime number of reduced divisors. The group is parameterized by $p$ and the coefficients of the defining equation.</li>
  </ol>
</blockquote>

<p>In particular, #3 is not among the flavors listed in your question.</p>

CC BY-SA 3.0
2012-02-09T16:55:56.863Z
2012-02-09T16:55:56.863Z
mikero
<p>I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}_p$ and Elliptic Curves. Are there any other explored choices?</p>

CC BY-SA 3.0
2012-02-09T15:45:23.810Z
See also: http://crypto.stackexchange.com/q/228/77
Sadeq Dousti
<cr.crypto-security><gr.group-theory>
Choices for the group in Public Key Cryptography
aelguindy
# Choices for the group in Public Key Cryptography

(Asked by: username_0 on 2012-02-09)

I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}\_p$ and Elliptic Curves. Are there any other explored choices?

**Tags:** cr.crypto-security, gr.group-theory

> **Comments:**
> **username_1**: See also: http://crypto.stackexchange.com/q/228/77  

---

## 1 answers

### Answer by username_2 on 2012-02-09. Score: 8 | Accepted answer

Dan Boneh's [survey article on the decisional Diffie Hellman problem](http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf) lists several candidate groups for which the DDH problem is hard, reproduced here:

> 1. Let $p=2p\_1 + 1$ where both $p$ and $p\_1$ are prime. Let $Q\_p$ be the subgroup of quadratic residues in $\mathbb{Z}^\*\_p$. It is a cyclic group of prime order. This family of groups is parameterized by $p$.
> 2. More generally, let $p = aq+1$ where both $p$ and $q$ are prime and $q > p^{1/10}$. Let $Q\_{p,q}$ be the subgroup of $\mathbb{Z}\_p^\*$ of order $q$. This family of groups is parameterized by both $p$ and $q$.
> 3. Let $N=pq$ where $p,q,\frac{p-1}2,\frac{q-1}2$ are prime. Let $T$ be the cyclic subgroup of order $(p-1)(q-1)$. Although $T$ does not have prime order, DDH is believed to be intractable. The group is parameterized by $N$.
> 4. Let $p$ be a prime and $E\_{a,b}/\mathbb{F}\_p$ be an elliptic curve where $|E\_{a,b}|$ is prime. The group is parameterized by $p,a,b$.
> 5. Let $p$ be a prime and $J$ be a Jacobian of a hyper elliptic curve over $\mathbb{F}\_p$ with a prime number of reduced divisors. The group is parameterized by $p$ and the coefficients of the defining equation.

In particular, #3 is not among the flavors listed in your question.


---

