Paillier暗号(Paillier cryptosystem)

# はじめに

[Wikipedia](https://ja.wikipedia.org/wiki/Paillier%E6%9A%97%E5%8F%B7)にあるとおり、Pascal Paillierが1999年に提案した公開鍵暗号方式です。
因みに、カタカナで表すと__ペイエ__暗号と言うらしいです。（エルどこいった？）
特徴としては、__加法準同型性__という性質を持っています。
これについては別途説明しますが、簡単に言うと、暗号分の積を複合化すると暗号前のデータの和と等しくなります。

[Public-Key Cryptosystems Based on Composite Degree Residuosity Classes](http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf)
[Paillier cryptosystem - Wikipedia](https://en.wikipedia.org/wiki/Paillier_cryptosystem)
[Paillier暗号 - Wikipedia](https://ja.wikipedia.org/wiki/Paillier%E6%9A%97%E5%8F%B7)
[₍₍ (ง ˘ω˘ )ว ⁾⁾ &lt; 暗号楽しいです](http://elliptic-shiho.hatenablog.com/entry/2015/12/14/213328)

# Paillier暗号(Paillier cryptosystem)

## アルゴリズム(Algorithm)

### 鍵生成(Key generation)

2つの大きい素数$\ p,q$を求め、$\ n=p\times q$とします。
$\ \lambda$を、$\lambda=\text{lcm}(p-1,q-1)$とします。
これは、[カーマイケル定理](https://qiita.com/tnakagawa/items/54f360f144a2ba2fe0a0#%E3%82%AB%E3%83%BC%E3%83%9E%E3%82%A4%E3%82%B1%E3%83%AB%E3%81%AE%E5%AE%9A%E7%90%86carmichael-function-1)で求めた値なので、$a,n$が互いに素である場合、$a^\lambda \equiv 1 \pmod n$となります。

関数$\ \text{L}(u)\ $を以下とします。

```math
\begin{align*}
\text{L}(u) = \frac{u-1}{n}
\end{align*}
```

$\ n^2$と互いに素である、$g$を選択します。
$\gcd(\text{L}(g^\lambda \bmod n^2),n)=1$が成り立たなければ、再度$g$を選択します。
$g$が選択されたら$\ \mu$を求めます。
$\ \mu = \\{\text{L}(g^\lambda \bmod n^2)\\}^{-1} \bmod n\ $とします。

- 公開鍵（暗号化）：$\ (g,n)$
- 秘密鍵（復号化）：$\ (p,q)$

### 暗号化(Encryption)

$m$はメッセージで、$\ 0\le m < n$とします。
$n$と互いに素である、$r$を選択します。
暗号文$\ c = g^m\cdot r^n \bmod n^2$を生成します。

この公開鍵$\ (g,n)$に対する暗号化を、$c= \mathcal{E}_g(m,r)$とします。

### 復号化(Decryption)

$\ c$ は暗号文で、$0\le c < n^2$とします。
以下の計算でメッセージが復元されます。

```math
\begin{align*}
m = \frac{\text{L}(c^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n
\end{align*}
```

あらかじめ、$\mu$を求めているので、$\ m=\text{L}(c^\lambda \bmod n^2)\cdot \mu \bmod n\ $で求められます。
この秘密鍵$(p,q,\lambda,\mu)\ $に対する暗号化を、$\ m=\mathcal{D}_g(c)$とします。

## 準同型(Homomorphic properties)

このPaillier暗号の特徴的な準同型の性質をみてみます。

### 平文の準同型加法(Homomorphic addition of plaintexts)

暗号文の積を複合すると、メッセージの和になります。

```math
\begin{align*}
& \mathcal{E}_g(m_1,r_{1}) = c_1 \\
& \mathcal{E}_g(m_2,r_{2}) = c_2 \\
& \mathcal{D}_g(c_1\cdot c_2 \bmod n^2) = m_1 + m_2 \\
\end{align*}
```

### 平文の準同型乗法(Homomorphic multiplication of plaintexts)

暗号文をメッセージで冪乗すると、メッセージの積になります。

```math
\begin{align*}
& \mathcal{E}_g(m_1,r_{1}) = c_1 \\
& \mathcal{D}_g(c_1^{m_2} \bmod n^2) = m_1 \times m_2 \\
& \\
& \mathcal{E}_g(m_2,r_{2}) = c_2 \\
& \mathcal{D}_g(c_2^{m_1} \bmod n^2) = m_2 \times m_1 \\
\end{align*}
```

## 解説

詳しい説明は、はじめににあるリンク先を参照ください。ここでは、簡単に解説します。
各所に互いに素という文言が出てきますが、これは最大公約数が1である事を言います。
お互いを素因数分解した時に、同じ素数の項を持ちません。
したがって、$\ n$で互いに素であれば、$n^2$でも互いに素となります。

### 鍵生成(Key generation)

$\mu = \\{\text{L}(g^\lambda \bmod n^2)\\}^{-1}$を考えてみます。
$\ g$は、$n^2$と互いに素なので、$n$とも互いに素となります。
カーマイケルの定理により、$\ g^\lambda \equiv 1 \bmod n\ $となるので、
$\ g^\lambda = kn + 1$と表す事が出来ます。

```math
\begin{align*}
\text{L}(g^\lambda \bmod n^2) &= \text{L}(1+kn) \\
&= \frac{1+kn-1}{n} \\
&= \frac{kn}{n} \\
&= k \\
\end{align*}
```

$\ g$生成時に、$\text{L}(g^\lambda \bmod n^2)$と$n$が互いに素である事を確認しているので、$\ n,k$も互いに素となります。
[モジュラ逆数](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E9%80%86%E6%95%B0)は互いに素であれば存在するので、$\mu = k^{-1} \bmod n$も求める事が出来ます。

### 暗号化(Encryption)、復号化(Decryption)

暗号文$c$から、$\text{L}(c^\lambda \bmod n^2)$を求めます。
途中、二項定理で分解すると$n^2$が消えていきます。

```math
\begin{align*}
c^\lambda \bmod n^2 &= (g^m\cdot r^n)^\lambda \bmod n^2 \\
&= g^{\lambda m}\cdot r^{\lambda n} \bmod n^2 \\
&= (g^\lambda)^m \cdot (r^{\lambda})^n \bmod n^2 \\
&= (1 + kn)^m \cdot (1 + k'n)^n \bmod n^2 \\
&= (1 +\ _mC_1kn +\ _mC_2k^2n^2 + \cdots + k^mn^m) \\
& \quad \cdot (1 +\ _nC_1k'n +\ _nC_2k'^2n^2 + \cdots + k'^nn^n) \bmod n^2 \\
&= (1 +mkn +\ _mC_2k^2n^2 + \cdots + k^mn^m  \bmod n^2) \\
& \quad \cdot (1 + nk'n +\ _nC_2k'^2n^2 + \cdots + k_r^nn^n  \bmod n^2)  \bmod n^2 \\
&= (1 +mkn)\cdot (1) \bmod n^2 \\
&= 1 +mkn \\
& \\
\text{L}(c^\lambda \bmod n^2) &= \text{L}(1 +mkn) \\
&= \frac{1+mkn-1}{n} \\
&= \frac{mkn}{n} \\
&= mk \\
\end{align*}
```

復号化の式に当てはめると、メッセージが復元されたことがわかります。

```math
\begin{align*}
\frac{\text{L}(c^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n = \frac{mk}{k} = m
\end{align*}
```
### 平文の準同型加法(Homomorphic addition of plaintexts)

冪演算は冪の和となるので、$\ g$の$m_1+m_2$累乗となります。
したがって、メッセージの和が計算出来ます。

```math
\begin{align*}
\mathcal{E}_g(m_1,r_{1}) = c_1 &= g^{m_1}\cdot r_1^n \bmod n^2\\
\mathcal{E}_g(m_2,r_{2}) = c_2 &= g^{m_2}\cdot r_2^n \bmod n^2\\
\mathcal{E}_g(m_1,r_{1})\cdot \mathcal{E}_g(m_2,r_{2}) = c_1\cdot c_2 &= g^{m_1+m_2}\cdot r_1^n\cdot r_2^n \bmod n^2\\
\mathcal{D}_g(c_1\cdot c_2 \bmod n^2) &= \frac{\text{L}(\{c_1\cdot c_2\}^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n \\
&= \frac{(m_1+m_2)k}{k} \\
&= m_1 + m_2 \\
\end{align*}
```

### 平文の準同型乗法(Homomorphic multiplication of plaintexts)

冪の冪演算は積となるので、$\ g$の$m_1\times m_2$累乗となります。
したがって、メッセージの積が計算出来ます。

```math
\begin{align*}
 \mathcal{E}_g(m_1,r_{1}) = c_1 &= g^{m_1}\cdot r_1^n \bmod n^2\\
c_1^{m_2} &= g^{m_1\cdot m_2}\cdot r_1^{n\cdot m_2} \bmod n^2\\
 \mathcal{D}_g(c_1^{m_2} \bmod n^2) &= \frac{\text{L}(c_1^{\lambda m_2} \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n \\
&= \frac{(m_1\times m_2)k}{k}  \\
&= m_1 \times m_2 \\
\end{align*}
```

# プログラミング

go言語で実装してみました、案外簡単です。
ソースコードは[ここ(Github)](https://github.com/tnakagawa/refec/blob/master/go/samplepaillier.go)です。

### 鍵生成(Key generation)

乱数生成は、以前の投稿[「大きな素数（かもしれない）」](https://qiita.com/tnakagawa/items/a1cf27b50cbebdba69b3)を利用しています。
また、最小公倍数も以前の投稿[「最小公倍数(least common multiple)」](https://qiita.com/tnakagawa/items/1a6fd6d310561d100ca2#%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0least-common-multiple)を利用しています。

```golang
// L returns (x - 1) / n .
func L(x, n *big.Int) *big.Int {
	if new(big.Int).Mod(new(big.Int).Sub(x, ONE), n).Cmp(ZERO) != 0 {
		return nil
	}
	return new(big.Int).Div(new(big.Int).Sub(x, ONE), n)
}

// KeyGeneration returns a public and a private keys of pailliar cipher.
func KeyGeneration(bits int) (*PublicKey, *PrivateKey, error) {
	// p and q are large primes
	p := probablyPrime(bits / 2)
	q := probablyPrime(bits / 2)
	if p.Cmp(q) == 0 {
		return KeyGeneration(bits)
	}
	// n = p * q
	n := new(big.Int).Mul(p, q)
	// n^2 = n * n
	n2 := new(big.Int).Mul(n, n)
	// λ = lcm(p-1,q-1)
	lam := lcm(new(big.Int).Sub(p, ONE), new(big.Int).Sub(q, ONE))
	// randomly select a base g
	g := new(big.Int)
	// μ = 1 / L(g^λ mod n^2)
	mu := new(big.Int)
	for {
		g = Rnd(n2)
		if gcd(g, n2).Cmp(ONE) != 0 {
			continue
		}
		mu = L(new(big.Int).Exp(g, lam, n2), n)
		// gcd(L(g^λ mod n^2 ), n) = 1
		if gcd(mu, n).Cmp(ONE) != 0 {
			continue
		}
		mu = new(big.Int).ModInverse(mu, n)
		break
	}
	// public key
	pub := &PublicKey{n: n, g: g, n2: n2}
	// private key
	pri := &PrivateKey{lam: lam, mu: mu, n: n, n2: n2}
	return pub, pri, nil
}
```

### 暗号化(Encryption)

乱数$r$は、$n$と互いに素である必要があります。


```golang
// PublicKey is a pailliar public key.
type PublicKey struct {
	n  *big.Int // n
	g  *big.Int // g
	n2 *big.Int // n^2
}

// Encryption returns an encrypted data.
func (pub *PublicKey) Encryption(m *big.Int) (*big.Int, error) {
	// plaintext m < n
	if m.Cmp(ZERO) < 0 || m.Cmp(pub.n) >= 0 {
		return nil, fmt.Errorf("m is out of range")
	}
	// select a random r < n
	r := new(big.Int)
	for {
		r = Rnd(pub.n)
		if gcd(r, pub.n).Cmp(ONE) == 0 {
			break
		}
	}
	// ciphertext c = g^m * r^n mod n^2
	c := new(big.Int).Mod(new(big.Int).Mul(
		new(big.Int).Exp(pub.g, m, pub.n2),
		new(big.Int).Exp(r, pub.n, pub.n2)), pub.n2)
	return c, nil
}
```

### 復号化(Decryption)

あらかじめ計算した$\mu$を使います。

```golang
// PrivateKey is a pailliar private key.
type PrivateKey struct {
	lam *big.Int // λ = lcm(p-1,q-1)
	mu  *big.Int // μ = 1 / L(g^λ mod n^2)
	n   *big.Int // n = p * q
	n2  *big.Int // n^2
}

// Decryption returns the decrypted data.
func (pri *PrivateKey) Decryption(c *big.Int) (*big.Int, error) {
	// ciphertext c < n 2
	if c.Cmp(ZERO) <= 0 || c.Cmp(pri.n2) >= 0 {
		return nil, fmt.Errorf("c is out of range")
	}
	// plaintext m = L(c^λ mod n^2) / L(g^λ mod n^2) mod n
	//             = L(c^λ mod n^2) * μ mod n
	m := new(big.Int).Mod(new(big.Int).Mul(
		L(new(big.Int).Exp(c, pri.lam, pri.n2), pri.n), pri.mu), pri.n)
	return m, nil
}
```

### 平文の準同型加法(Homomorphic addition of plaintexts)

```golang
// Mul returns c1 * c2 mod n2
func (pub *PublicKey) Mul(c1, c2 *big.Int) *big.Int {
	// c1 * c2 -> m1 + m2
	return new(big.Int).Mod(new(big.Int).Mul(c1, c2), pub.n2)
}
```

### 平文の準同型乗法(Homomorphic multiplication of plaintexts)

```golang
// Exp returns c ^ m mod n2
func (pub *PublicKey) Exp(c, m *big.Int) *big.Int {
	// c ^ m2 -> m1 * m2
	return new(big.Int).Exp(c, m, pub.n2)
}
```

#さいごに

案外簡単なので、是非各言語で実装してみてください。
大きな素数生成は、RSAで求める必要があるのでRSAライブラリを探せばある可能性が高いと思います。