# Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?

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.

• This assumption in the paper looks bogus. It does not say how the hash function is used, for example. – Paŭlo Ebermann Oct 24 '11 at 19:46
• Sorry, it says how $H_1$ is used in the paper. I don't think it's relevant for the assumption, though. The second paper I mentioned gives a definition without the hash function that is nearly identical. – oopsdude Oct 24 '11 at 20:10

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA standard.
The remaining part is: how to build $H_1$, the hash function which produces elements in the target group ? For that, you first use a hash function which produces values modulo $p$ (e.g. you use a PRNG seeded with the hashed data, and produce bit sequences of the size of $p$ until you find one which is between $0$ and $p-1$); then, you raised that value to the power $(p-1)/q$. The result is necessarily a $q$-th root of 1, and the whole is a "hash function".
For your additional question: $R$ knows the $a_j$, which are random non-zero integers modulo $q$. $R$ can thus compute each $a_j^{-1}$ modulo $q$ (that's regular modular inversion). In the expression "$(D_j)^{a_j^{-1}}$, $D_j$ is part of a group of size $q$, so any exponent can be taken modulo $q$.
• CDH is about computing $h^{xy}$ given $h$, $h^x$ and $h^y$; this is equivalent to compute $m^x$ given $g$, $m$ and $g^x$ (simply declare $m = g^y$; for any $m$ in the group there is a corresponding $y$). So CDH is about trying to raise a single given (random) $m$ to the unknown $x$-th power. With CT-CDH, we give access to a "raise to $x$-th power" machine, but we allow for strictly less than $k$ calls to that machine, and we ask for the "raised to $x$-th power" version of $k$ random values (the $w_i$). The attacker has the choice of the target, but he must still be smart at some point. – Thomas Pornin Oct 25 '11 at 0:31