# 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.

-

1
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

## 1 Answer

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".

As far as I know, such a group would fulfill the CT-CDH assumption -- i.e. there is no known way to break it. CT-CDH is a "weaker" assumption than standard CDH, but there is no proof that it is strictly weaker.

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$.

-

Wow, awesome answer. Thanks! Would you mind explaining CT-CDH in terms of CDH? I understand the latter, but only vaguely understand the former. – oopsdude Oct 24 '11 at 23:18
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
Now I get it. Thanks. – oopsdude Oct 25 '11 at 16:48
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 73, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9197594523429871, "perplexity_flag": "head"}