exponent bit-length for hard DL (128-bit security)

Question

Following up on my previous post, I thought I might get a more concrete answer if I gave a more concrete question.

I require 128-bit security so I choose a 3072-bit RSA modulus ($\ell_n=3072$). Specifically I choose $n=pq=(2p'+1)(2q'+1)$ that is a product of safe primes $p$ and $q$.

Now, I want to choose $\ell_\Lambda$ such that finding DL with $\ell_\Lambda$-bit exponents is hard in $QR_n$, for an adversary who does not know the factorization of $n$, with 128 bits of security.

Note that the order of $QR_n=\phi(n)/4=p'q'$, so each element has large order.

Is choosing $\ell_\Lambda=256$ sufficient as suggested in the answer to my previous post?

Answer 1

I second that with the factorization of $n$ remaining secret, as assumed in the paper linked in that previous question (in particular by making the strong RSA assumption), the Discrete Logarithm Problem modulo $n$ is believed no easier that if $n$ was prime. And therefore, the best methods to solve that DLP have expected cost the lowest of:

1. a few times $2^{\ell_\Lambda/2}$ multiplications modulo $n$, for methods based on collision search like Pollard's rho/kangaroo and distributed variants.
2. about the cost of (G)NFS factorization of $n$; see this paper for about the state of the art, implying that the cost of factorization of $n$ and DLP for prime $n$ have roughly similar cost.

With $\ell_\Lambda=256$ and $\ell_n=3072$, (1.) is believed to be the least infeasible, and this parametrization is believed to give 128-bit security, disregarding hypothetical CRQC.