Computational Diffie-Hellman problem over the group of quadratic residues

Question

Suppose that $N=pq$ where $p$ and $q$ are safe primes. $\mathbb{QR}_N$ is the group of quadratic residues which is a cyclic group with order $\frac{\phi(N)}{4}$. Let $g$ be the generator of $\mathbb{QR}_N$.

The computational Diffie-Hellman problem is defined as : given $U=g^u\in\mathbb{QR}_N$ and $V=g^v\in\mathbb{QR}_N$ where $u,v$ are chosen uniformly at random from $\mathbb{Z}_{\frac{\phi(N)}{4}}$, compute $CDH(U,V)=g^{uv}$.

Now, if $N$ can be efficiently factored, then computing $CDH(U,V)=g^{uv}$ is still hard ?

Answer 1

That depends entirely on the size of $p$ and $q$.

Given a factorization of $N = pq$, an attacker can compute $g^u \bmod p$ and $g^v \bmod p$, and then attempt to solve the CDH problem modulo $p$, giving him $g^{uv} \bmod p$.

Then, he can then compute $g^u \bmod q$ and $g^v \bmod q$, and then attempt to solve the CDH problem modulo $q$, giving him $g^{uv} \bmod q$.

Then, he can combine them to form $g^{uv} \bmod pq$.

The only parts that might not be straightforward is the CDH problem modulo $p$ and $q$ -- if one if the two primes is large enough to make this infeasible, then he cannot do that (and conversely, if he cannot solve the CDH problem modulo $p$, he obviously cannot solve it modulo $pq$.