2
$\begingroup$

A protocol I am working with requires $\ell_n$-bit RSA modulus and $\ell_\Lambda$ such that computing $\ell_\Lambda$-bit discrete logs is hard in $QR_n$ (technically $n$ is $\ell_n+2$ bits in the definition of the paper).

Note we have the additional structure that $n$ is a product of two safe-primes $p=2p'+1$ and $q=2q'+1$ so $\operatorname{Ord}(\mathrm{QR}_n)=\frac{\phi(n)}{4}=\frac{(p-1)(q-1)}{4}=p'q'\in\{0,1\}^{\ell_n}$.

Clearly $\ell_n$ will be large (in the 1000's), but from my understanding the reason RSA-moduli have to be so large has to do with factorization algorithms, not hardness of DL.

I have seen several posts relating to the lengths of RSA-moduli needed for different levels of security but I have had trouble finding anything on this. What is a reasonable choice for $\ell_\Lambda$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Clearly $\ell_n$ will be large (in the 1000's), but from my understanding the reason RSA-moduli have to be so large has to do with factorization algorithms, not hardness of DL.

Actually, it's pretty much the same for your algorithm - computing the discrete log is essentially equivalent to factoring the modulus; hence following the standard factoring recommendations for $\ell_n$ is appropriate.

For the factoring -> discrete log step: the best known algorithms for factoring and computing discrete logs have roughly the same complexity given the same sized input. Hence, one strategy an attacker might try is factoring the modulus, and then computing the discrete log modulo each prime (and then combining the results). The cost of the latter steps are much less than the cost of the factoring step; hence if your modulus is small enough to factor, it is small enough to compute the discrete log.

For the discrete log -> factoring step: if someone is able to compute the discrete log of an arbitrary value modulo your composite, they can factor the composite. One simple way would be to select a value $x > n$, and compute $z = g^x \bmod n$, and use your method to compute the discrete log of $z$, that is, the value $y$ s.t. $z = g^y \bmod n$. Because the order of the $n$ is less than $x$, we have $y < x$, and hence $x-y$ is a multiple of $(p-1)(q-1)$; deducing the factorization from that is trivial.

What is a reasonable choice for $\ell_\Lambda$

Well, the advice isn't quite as clear there.

The lower bound I know about: the generic discrete log methods (such as giant-step-baby-step) apply, and so we must have $\ell_\Lambda \ge 2 \cdot seclevel$ where the target required complexity is $O(2^{seclevel})$.

The upper bound: well, if you look at the above 'discrete log -> factorization' argument, you see that this would apply (assuming $p, q$ are the same bitlength) with $\ell_{\Lambda} = \ell_n / 2$, that is, you could factor such an $n$ given an oracle that can compute a discrete log with $\ell_{\Lambda} = \ell_n/2$; hence taking that as an upper bound seems safe.

That still leaves the open question: where in that range is the appropriate $\ell_{\Lambda}$? I do not know if any discrete log methods that would be able to take advantage of a $\ell_\Lambda > 2 \cdot seclevel$ and which would be cheaper to perform than a general discrete log.

Hence, $\ell_\Lambda = 2 \cdot seclevel$ may be sufficient; on the other hand, if increasing $\ell_\Lambda$ is cheap, I'd do so...

$\endgroup$
1
  • $\begingroup$ Thanks! Increasing $\ell_\Lambda$ is not cheap due to range proofs which is why I wanted to get an estimate. $2\cdot seclevel$ is very useful information, since for RSA $\ell_n$ won't scale linearly with $seclevel$. If I am understanding this correctly then for 128-bit security we need $\ell_n=3072$ but $\ell_\Lambda=256$. $\endgroup$ Feb 5, 2023 at 23:40

Your Answer

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

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