# 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?

-

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.