# How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$

Use the notations form the Wikipedia article Paillier Cryptosystem , assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?

-

## 1 Answer

No, it is not possible to compute $\lambda$ easily. Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability. Hence, if we believe the factorization problem is hard, we must also believe that this modified discrete log problem is hard.

One way to arrive at that is "if you can find $\lambda$ given a random instance, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using the black box, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $pq(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^\lambda = r \bmod n^2$; once you know $\lambda$, you also know that $r^{k\lambda-1} = 1 \bmod n$ (because if $(r^k)^\lambda = r \bmod n^2$, then $(r^k)^\lambda = r \bmod n$ as well). That is, the order of $r$ is a divisor of $k\lambda-1$.

Once you have that multiple of an order $x = k\lambda-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$. If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$. And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.

-
Thank you very much! BTW, if I want to use this conclusion in a paper, how should I acknowledge you, and how to make the reference? – phan Feb 24 '13 at 18:35
@phan: I don't know if the result is novel enough to merit a citation; it's taking the standard 'DLOG modulo a composite -> Factor the composite' reduction, and applying that to 'DLOG modulo the square of a composite'. However, if you believe it is warrented, why don't you acknowledge Scott Fluhrer, and this StackExchange question (I've seen sci.crypt posting cited before; I see no reason why StackExchange can't be similarly cited). – poncho Feb 24 '13 at 22:32
Thank you again! – phan Feb 26 '13 at 4:13