# Reduction from integer factoring to computational Diffie Hellman

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 ?

Footnotes:

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

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