### Composite Residuosity Classes of Paillier Encryption

##### Crypto

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)=p-1$. It has multiplicative property, however, those element must be co-prime, $\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^e-1]$, those numbers, $T = { p, p^2, p^3, \cdots, p^{e-1} }$, 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^{e-1}$, the rest are $\phi(p^e) = p^e - p^{e-1} = 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:

1. $\lambda(n) = \mathbf{lcm}(p-1)(q-1)$
2. $\phi(n) = (p-1)(q-1)$
3. $|\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 n-th 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.

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

2. 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,

$$((1+n)^x)^n = 1+(xn)n \mod n^2 = 1 \mod n^2$$

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

1. http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf
2. http://en.wikipedia.org/wiki/Carmichael_function