2
$\begingroup$

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:

[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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.