This post will briefly introduce hard problems which are related to Paillier cryptosystem.
Mathematic basics
\(\mathbb{Z}_k \) is defined as an integer group modulo \(k\), which means it contains all integer less then \(k\), formally definition: \( \{ z z\in \mathbb{Z}, 0 \leq z < k \} \). A multiplicative group is defined as \( \mathbb{Z}_k^{*} = \{ z z\in \mathbb{Z}, 0 \leq z < k, \gcd(z,k)=1 \} \).
More about Euler phi function(Euler’s totient function)
In my RSA post, I introduced a little bit about Euler phi function, \(\phi(n)\) means the number of integers in \([1,n]\) which are relatively prime to \(n\). The easy case is that a prime number \(p\), \(\phi(p)=p1\). It has multiplicative property, however, those element must be coprime, \(\gcd(m,n)=1\), then \(\phi(mn)=\phi(m)\phi(n)\).
We know that any number can be factorized using prime numbers. Say we have a number \(n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}\). Useing multiplicative property, we can get \( \phi(n) = \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_k^{e_k}) \). To calculate \( \phi(p^e)\), we need to think about what is the meaning of \(\phi\)function. In the range of \([1, p^e1] \), those numbers, \( T = { p, p^2, p^3, \cdots, p^{e1} } \), have greatest common divisor with \(p^e\) which are not 1. Similar, for any element in set \(T\), its multipier such as \( { p, 2p, 3p, \cdots, kp} \) where \(kp \leq p^e \). So how many of those values ? It should be \( k = p^{e1} \), the rest are \( \phi(p^e) = p^e  p^{e1} = p^e (1\frac{1}{p} )\). \[ \phi(n) = n(1\frac{1}{p_1})(1\frac{1}{p_2}) \cdots (1\frac{1}{p_k}) \] If given a number \(x^2\), we know that each \(x\) can be taken as n in the previous euqation, simliarily, we have \(\phi(p^{2e}) = p^{2e}(1\frac{1}{p}) \). Thus \[ \phi(x^2) = \prod_i (p_i^{2e_i}(1\frac{1}{p_i})) = (\prod_i p_i^{e_i})(\prod_i p_i^{e_i}(1\frac{1}{p_i}) ) = x\phi(x) \]
Composite Residuosity Class
Paillier problem is based on the high degree residue.
Notations
\( n = p q\), where \(p\), \(q\) are large prime numbers. \(\lambda(n)\) is the Carmichael’s function and \(\phi(n)\) is the Euler’s totient function.
Facts:
 \(\lambda(n) = \mathbf{lcm}(p1)(q1)\)
 \(\phi(n) = (p1)(q1)\)
 \(\mathbb{Z}_{n^2}^{*} = \phi(n^2) = n \phi(n)\) .
Carmichael’s theorem
For any \(w \in \mathbb{Z}_{n^2}^{*}\), we have \[ w^{\lambda} = 1 \mod n\] \[w^{n\lambda} = 1 \mod n^2 \]
\(n\)th residues modulo \(n^2\)
A number \(z \in \mathbb{Z}^{*}_{n^2}\) is an \(n\)th residues modulo \(n^2\) if there exists a number \(y \in \mathbb{Z}^{*}_{n^2}\) such that \[ z = y^n \mod n^2 \] The problem to decide whether or not a given \(z \in \mathbb{Z}^{*}_{n^2}\) is an \(n\)th residues modulo \(n^2\) is hard in polynomial time.
Fact: The set of nth residues is a multiplicative subgroup of \(\mathbb{Z}^{*}_{n^2}\) of order \(\phi(n)\).
THis deicision problem is called Decisional Composite Residuosity Assumption (DCRA) in Paillier paper[1].
Root of unity
A \(n\)th root of unity, where \(n\) is a positive integer, is a number \(z\) satisfying \[ z^n = 1\] Furthur, we call a \(n\)th root of unity is primitive if for any \(k < n\), \[ z^k \neq 1\]
There are some facts we need to know.

\(z\) is the \(n\)th root of unity, if and only if \(a \equiv b \mod n\), then \(z^a = z^b\). This is the property of unity.

A integer power of an \(n\)th root of unity is also an \(n\)th root of unity.
\(n\)th root of unity in \( \mathbb{Z}_{n^2}^{*} \)
For, any \(x\) in \( \mathbb{Z}_{n} \), root of unity in \( (\mathbb{Z}_{n^2}^{*},\cdot) \) are in the form of \( (1+n)^x = 1+xn \mod n^2 \)
To provde the quality of above euqation, we can use inductino. To see why this is root of unity, we can calculate the \(n\)th root of unity,
Note that \( (1+n)^x \in \mathbb{Z}_{n^2}^{*} \) because, \(\gcd(1+xn ,n^2)=1\).
Next post will talk about Computing in Composite Residuosity Classes
Reference
 http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf
 http://en.wikipedia.org/wiki/Carmichael_function