3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – fgrieu Jun 17 '18 at 7:13
  • 1
    $\begingroup$ Hello, it is without knowing the factorization of $n$, also we could choose all parameters with whichever strategy. $\endgroup$ – Cip Baetu Jun 18 '18 at 8:05
3
$\begingroup$

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.

You can find more information about the critieria in this paper (and from its references): On the Portability of Generalized Schnorr Proofs, by Camenisch et al, Eurocrypt 2009

$\endgroup$
1
$\begingroup$

As far, as I understand, you need lifting solutions mod n. So the article https://dl.acm.org/citation.cfm?id=57604 by H.Riesel can be useful. (The author uses Fermat quotients to lift solutions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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