2
$\begingroup$

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 ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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}$ ? $\endgroup$
    – T.B
    May 9, 2014 at 1:58
  • $\begingroup$ @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. $\endgroup$
    – poncho
    May 9, 2014 at 2:02
  • $\begingroup$ 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? $\endgroup$
    – T.B
    May 9, 2014 at 2:22
  • $\begingroup$ @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. $\endgroup$
    – poncho
    May 9, 2014 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.