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