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
    $\begingroup$ This assumption in the paper looks bogus. It does not say how the hash function is used, for example. $\endgroup$ – Paŭlo Ebermann Oct 24 '11 at 19:46
  • $\begingroup$ 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. $\endgroup$ – 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".

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

  • $\begingroup$ Wow, awesome answer. Thanks! Would you mind explaining CT-CDH in terms of CDH? I understand the latter, but only vaguely understand the former. $\endgroup$ – oopsdude Oct 24 '11 at 23:18
  • $\begingroup$ 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. $\endgroup$ – Thomas Pornin Oct 25 '11 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.