Paillier Complex Residuosity problem?

Question

Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as:

The problem of deciding n-th residuosity, i.e. distinguishing n-th residues from the non n-th residues will be denoted by CR[n]. Observe that like the problems of deciding quadratic or higher degree residuosity, CR[n] is a random-self- reducible problem that is, all of its instances are polynomially equivalent. Each case is thus an average case, and the problem is either uniformly intractable or uniformly polynomial. As for prime residuosity, deciding n-th residuosity is believed to be computationally hard. Accordingly, we will assume that :

Conjecture 2. There exists no polynomial-time distinguisher for n-th residues modulo n2, i.e. CR[n]is intractable.

So, based on what this note states given a number in $\mathbb{Z}_{n^2}^*$ I cannot determine whether this number is on the residues set or not.

My Questions are:

1. What is so difficult about this if $z=y^n\ mod\ n^2$
2. The more important thing what is so dangerous in knowing that a number in the residues set. How It can help me break the encryption?

Answer 1

1. What is so difficult about this if $z=y^n\ mod\ n^2$

We don't know of an efficient way of solving it. That's essentially what we can say about just about any hard problem in cryptography.

We also don't know a reduction to a better studied problem (for example, the factorization problem); hence it gets called out as a separate hard problem.

2. The more important thing what is so dangerous in knowing that a number in the residues set. How It can help me break the encryption?

That's easy; an Oracle that can solve the n-th residuosity problem (without knowing the factorization) allow us to determine whether a Pallier encrypted message is an encoding of 0 (because a ciphertext is an encoding of 0 if and only if it is an n-th residue).

Not only would that, in itself, be considered a break in security, we could (for example) test an encrypted message for equality with any other value (by encrypting that value, homomorphically subtracting the test ciphertext from the ciphertext of the encrypted value, and checking if that is an encoding of 0).