I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer scheme defined in the top box on page 10(=406).
The (intimidating, to me) CT-CDH assumption is defined as follows (page 7=403):
Let $\mathbb{G}_q$ be a group of prime order $q$, $g$ be a generator of $\mathbb{G}_q$, $x\in \mathbb{Z}^*_q$. Let $H_1 : \{0, 1\}^∗ \rightarrow \mathbb{G}_q$ be a cryptographic hash function. The adversary $A$ is given input $(q, g, g^x, H_1)$ and two oracles: target oracle $TG(\cdot)$ that returns a random element $w_i \in \mathbb{G}_q$ at the $i$-th query and helper oracle $HG(\cdot)$ that returns $(\cdot)^x$. Let $q_T$ and $q_H$ be the number of queries $A$ made to the target oracle and helper oracle respectively.
Assumption: The probability that $A$ outputs $k$ pairs $((v_1, j_1), (v_2, j_2), \dots, (v_k, j_k))$, where $v_i = (w_{j_i})^x$ for $i \in \{1, 2, \dots , k\}$, $q_H \lt k \leq q_T$, is negligible.
It should be noted that this assumption is equivalent to the standard Computational Diffie-Hellman assumption when $q_T=1$, according to this paper.
Can anyone give an example of a group that fits the bill? I tried $\mathbb{Z}^*_q$ for a prime $q$ under multiplication, but that's of order $q-1$, which is clearly not prime. However, the complexity analysis on page 12 of the paper is in terms of modular exponentiations.
Additionally (I can make a new question for this, if scolded), how would one implement the $(D_j)^{a_j^{-1}}$ operation in step 5 of the protocol? I can't figure out if it's equivalent to the discrete log problem.