2
$\begingroup$

https://en.wikipedia.org/wiki/Paillier_cryptosystem

Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily.

If I were to select $g \in \mathbb{Z}_{n^2}^*$ where $n$ divides the order of $g$, then the discrete log is easy (w.r.t base $g$) if I understand correctly.

But if I were to select any random value $r \in \mathbb{Z}_{n^2}^*$ where $n$ does not divide the order of $r$, are we then able to say anything about the difficulty of the discrete log?

$\endgroup$

1 Answer 1

0
$\begingroup$

I'll assume the typical Paillier set up that $n=pq$ with $p$ and $q$ prime numbers $(p-1)\not\!| q$ and vice-versa.

The recovery of a discrete logarithm $x$ of a general element $a$ with respect to a generator is equivalent to the recovery of three values: $$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\\ x_p\pmod p\\ x_q\pmod q}.$$

If one knows the values of $p$ and $q$ then $x_p$ and $x_q$ are easy to recover using Fermat quotients or $p$-adic version of the logarithmic Taylor series. The best known methods to recover $x_\lambda$ rely on the number field sieve and for cryptographically sized* $p$ and $q$, this should be infeasible. If one picks a generator such that the order of the generator divides $n$, this means that $x_\lambda$ can be ignored and discrete logarithms with respect to this generator can easily be computed by anyone who knows $p$ and $q$.

In your first case where $n$ divides the order of $g$, this only tells us that $x_p$ and $x_q$ cannot be ignored. It does not ensure that $x_\lambda$ can be ignored and hence our problem could still be intractable.

In your second case where $n$ does not divide the order of $r$ this tells us that either $x_p$ can be ignored or $x_q$ can be ignored (possibly both can be ignored). It does not ensure that $x_\lambda$ can be ignored and our problem could still be intractable.

In general:

  • if $p$ does not divide the order of the generator, then $x_p$ can be ignored,
  • if $q$ does not divide the order of the generator, then $x_q$ can be ignored,
  • if $\lambda(n)$ does not divide the order of the generator, then $x_\lambda$ can be taken ignored.

Also note that if we happen to know a bound on the size of $x$, then it may not be necessary to recover all three components. e.g. if we know that $x<pq$ then recovery of $x_p$ and $x_q$ allows us to uniquely recover $x$ from the Chinese remainder theorem.

*- Note that $p$ and $q$ have to be larger moduli than can be attacked with the number field sieve rather than simply $n$ being a larger modulus than can be attacked with the number field sieve.

$\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.