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

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?

• Is the factorization of $n$ secret? With $p$ and $q$ known, we can reduce a DLP modulo $n$ to two DLP modulo $p$ and $q$, and with each 1536-bit these would not be 128-bit secure (more like 100-bit, give or take a lot).
– fgrieu
Feb 9, 2023 at 17:42
• @fgrieu: as explained in his previous post, the factorization of $n$ is secret Feb 9, 2023 at 18:32
• @fgrieu edited question to clarify $p$ and $q$ are unknown Feb 9, 2023 at 19:00

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.