# Discrete Logarithm in a specific group

I am considering a setting similar to the one of the Paillier cryptosystem, where we sample two distinct odd primes $p,q$, we set $n=pq$, we generate $a \leftarrow \mathbb{Z}_{n^2}^*$ and finally we set $g = (n+1) a^n \mod{n^2}$.

My question now is if the discrete log with the parameters $(g, \mathbb{Z}_{n^2}^*)$ is known to be hard, i.e. if given $(g, g^x)$, one can simply recover $x$, where let's say $x \in \mathbb{Z}_n$.

I know that we can apply Chinese Remainder Theorem in this case, but is this alone sufficient for breaking the Discrete Log?

Thank you very much!

• Are we trying to find $x$ from $(g,g^x\bmod n^2)$ with or without knowledge of the factorization of $n$? Can we choose $p$ and $g$ to maximize difficulty of finding $x$ from $(g,g^x\bmod p$), and the same for $q$? – fgrieu Jun 17 '18 at 7:13
• Hello, it is without knowing the factorization of $n$, also we could choose all parameters with whichever strategy. – Cip Baetu Jun 18 '18 at 8:05

Discrete logarithm can be hard in Paillier group. One case for example is when $p$ and $q$ are safe primes, i.e. $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are themselves prime.