2. Pallier PKC¶

The trapdoor function generalizes \(QR_n\) to \(QR_{n^2}\), which is called composite residuosity problem.

Pick up 2 primes \(p\) and \(q\) and \(N = pq\).

Uses 2 functions: 1) Euler’s Totient function \(\Phi(N) = (p-1)(q-1)\); 2) Carmichael’s function \(\lambda(N) = lcm(p-1, q-1)\).

Note that \(\Phi(N^2) = N\Phi(N) = N(p-1)(q-1)\) and \(|\mathbb{Z}_{N^2}^*| = \Phi(N^2)\).

For any \(w \in \mathbb{Z}_{N^2}^*\), \(w^{\lambda(N)} \equiv 1~mod~N\) and \(w^{N\lambda(N)} \equiv 1~mod~N^2\).

A number \(Z\) is \(n^{th}\) residue modulo \(n^2\) if \(\exists y \in \mathbb{Z}_{n^2}^*\) such that \(Z = y^n~mod~n^2\).

The problem of deciding \(n^{th}\) residuosity is distinguishing \(n^{th}\) residues from non \(n^{th}\) residues. (\(CR_N\) problem)

Conjecture: \(\nexists\) polynomial time distinguisher for \(CR_n\) problem \(\Rightarrow\) intractable.

Pallier algorithm enjoys: Semantically Secure, trapdoor function under \(CR_n\) and homomorphic properties.

\(n = pq\), \(g\) has order \(v\) where \(v \equiv 0~mod~n\).

public key: \((n, g)\), private key: \(\lambda(n)\).

Message \(M\) is an integer smaller than \(n\).

Choose a value \(u\) uniformly from \(\mathbb{Z}_{n^2}^*\).

Ciphertext \(c = g^Mu^n~mod~n^2\).

Define a function \(L(x) = \frac{x-1~mod~n^2}{n}\)

\[M = \frac{L(c^{\lambda(n)}~mod~n^2)}{L(g^{\lambda(n)}~mod~n^2)}~mod~n.\]

Verify that:

\[M = \frac{c^{\lambda(n)}-1~mod~n^2}{g^{\lambda(n)}-1~mod~n^2}~mod~n.\]

\[\begin{split}&E(M_1) = g^{M_1}X_1^N~mod~N^2\\&E(M_2) = g^{M_2}X_2^N~mod~N^2\\&E(M_1)E(M_2)=g^{M_1+M_2}(X_1X_2)^N~mod~N^2=E(M_1+M_2)\end{split}\]

Furthermore, \(\forall M_1. M_2 \in \mathbb{Z}_N\) and integer \(k\)