The computational Diffie Hellman (CDH) problem for ${\mathbb{Z}}^*_p$ is given a prime $p$, a generator $g$ of ${\mathbb{Z}}^*_p$, and a pair $(g^i, g^j)$ to compute $g^{ij}$. The value $g$ is called the base. In cryptographic protocols the base is usually fixed in advance.

This problem generalizes to other groups. For fixed $n$ a product of two primes ($n$ will always be a product of two primes) the composite CDH function is defined $$ CDH: {\mathbb{Z}}^*_n \times {\mathbb{Z}}^*_n \times {\mathbb{Z}}^*_n \to\ {\mathbb{Z}}^*_n $$ $$ CDH(g,a,b) = \left\{g^{ij} : a = g^i \text{ and } b = g^j \text{ for } i,j \text{ in } \mathbb{Z}\right\}. $$ The composite CDH problem is to compute a value of this function.

One difference from CDH for prime moduli is that ${\mathbb{Z}}^*_n$ is not a cyclic group. I have called the first argument $g$ as an analogy to the prime case but it cannot be a generator of ${\mathbb{Z}}^*_n$.

It is known that factoring integers reduces to computational Diffie Hellman in the sense that if any instance of the CDH in ${\mathbb{Z}}^*_n$ be solved then the modulus can be factored1.

The algorithm is simple so I will summarize it. The only tool that's needed is a reduction from integer factoring to finding roots of quadratic binomials2. Of course factoring binomials is equivalent to finding $\sqrt{x}$ for $x \in {\mathbb{Z}}^*_n$.

Let $Q(n)$ be the set $\left\{a : a \in {\mathbb{Z}}^*_n \text{ and the multiplicative order of } a \text{ is odd} \right\}$.

The main idea for reducing factoring to CDH is that if we choose random $c$ in $Q(n)$, and a pair of integers $x_0, x_1$ and compute $c^{2x_0x_1}$ then two square roots can often be found using CDH. Let $$ y = c^{x_0x_1} $$ $$ z = CDH\left(c^4, c^{2x_0}, c^{2x_1}\right) $$ then $y^2 = z^2 = c^{2x_0x_1}$. Since the choice of $c$ was random, $gcd(y - z, n)$ has a $1/2$ probability of splitting $n$.

One way to think about this reduction is if the CDH function can be computed on a non-negligible proportion of bases then we can quickly factor $n$.

Another way is that if the base $d$ used in CDH is fixed in advance then to use this reduction to factor we need to find a root of the polynomial $f = X^4 - d$. As I said above, integer factoring reduces to finding (several) roots of a polynomial. So it is not surprising that knowing a single root of $f$ in addition to a CDH algorithm is enough to let us factor $n$.

It would be better to have a reduction that works independently of the base. Are any reductions like this known ?


[1] Let $f = X^2 - a^2$ for random $a$ in ${\mathbb{Z}}^*_n$. By the Chinese remainder theorem $f$ has $4$ roots. Suppose we can find two roots $r_0, r_1$ with $r_0 \neq \pm r_1$ of in ${\mathbb{Z}}^*_n$. Then $r_0^2 = r_1^2 \bmod{n}$ so $\gcd(r_0 - r_1, n)$ is a factor of $n$.

[2] McCurley, K.S. A key distribution system equivalent to factoring. http://mccurley.org/papers/equiv.pdf


Your Answer

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

Browse other questions tagged or ask your own question.