# Computational Diffie-Hellman problem over the group of quadratic residues

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 ?

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

• how large of $p$ or $q$ at least to make sure the hardness of $CDH(U,V) \pmod{p}$ or $CDH(U,V) \pmod{q}$ ? – T.B May 9 '14 at 1:58
• @Alex: Well, with the Number Field Sieve, a large and determined attacker is known to be able to compute discrete logs of 768 bits (they've factored numbers that large, and NFS can be used to compute discrete logs of the same size without too much more work), and (depending on the amount of resources available), possibly a bit more. 1024 bits may be safe for now. – poncho May 9 '14 at 2:02
• so if the CDH assumption over $\mathbb{QR}_N$ holds, then CDH assumption $\pmod{p}$ or CDH assumption $\pmod{q}$ may not hold; from other direction if CDH assumption $\pmod{p}$ or CDH assumption $\pmod{q}$ holds ,then certainly CDH assumption over $\mathbb{QR}_N$ holds. If I want to use this correctly, I'd better supposing CDH assumption $\pmod{p}$ or CDH assumption $\pmod{q}$ holds, is that right? – T.B May 9 '14 at 2:22
• @Alex: as for CDH over $N$ does not imply CDH over $p$, well, that's obvious; consider $N = 7p$ where $p$ is a large safe-prime; the CDH problem over 7 is known to be easy. Now, it's possible that CDH over $N$ might be difficult even if CDH over $p$ and $q$ is feasible; that would require that $N$ be hard to factor. Also: is there a specific reason why you're asking for CDH over a composite? CDH over a prime of the same size is much safer. – poncho May 9 '14 at 2:40