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?
1 Answer
Dan Boneh's survey article on the decisional Diffie Hellman problem lists several candidate groups for which the DDH problem is hard, reproduced here:
- 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$.
- 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$.
- 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$.
- 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$.
- 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.