準同型暗号(秘密計算)を最短距離で理解する

- 個人的理解としてまとめています。暗号化の専門家ではないので、もし間違っていたらごめんなさい。ご指摘ください。
- また今回は完全準同型暗号については触れません。加法準同型暗号と乗法準同型暗号について取り扱います。

# 準備としてはじめにElGamal暗号を学ぶ

準同型暗号はElGamal暗号を理解する必要があります。そのため公開鍵暗号の一つであるElGamal暗号をはじめに理解します。

## 一般的な公開鍵暗号方式の簡単な数式で表現してみる

これは表現方法で考える必要はありません。こんなふうに抽象化できるんだ、こんなふうに表現できるんだと知っていればOK

### 暗号化 `Enc`

Aさんに平文 $m$ を送りたいときAさんの公開鍵 $K_A$ を使って暗号化し暗号文 $c$ を作る.

```math
\begin{align}
&c:= Enc\left(K_A, m\right). \\
\end{align}
```


### 復号 `Dec`

Aさんは自分の秘密鍵 $K^{'}_A$ を使って暗号文 $c$ から元の平文 $m$ を復号する.

```math 
\begin{align}
&m:=Dec\left(K^{'}_A, c\right). 
\end{align}
```

### 公開鍵暗号の特徴


- 公開鍵 $K_A$ を使って暗号化された暗号文は秘密鍵 $K^{'}_A$ を知っている人Aさんしか復号できません
- 一方、$K_A$を知っている人は誰でも$K_A$を使って暗号化できます


## ElGamal暗号 (公開鍵暗号方式の一つ)

ElGamalを準同型暗号で使用するため、次にElGamal暗号を学びましょう。

### 公開鍵生成

- 鍵生成に用いる `g`と`p`を固定しこれらは公開される。つまり既知の値となる。
    - pは素数であること
    - gは 1<g<p−1を満たす[原始根](https://blog.thetheorier.com/entry/primitiveroot-list)であること
- 整数`x`をランダムに選び、秘密鍵を生成する (1<x<p−1を満たす自然数であること)
- `x`: 秘密鍵であり整数`x`をランダムに選び生成される
- `y`: 公開鍵であり、以下の式で生成される

```math
\begin{align}
&y := g^x\bmod p 
\end{align}
```

#### 公開鍵の簡単な生成例

- p = 499 (素数)
- g = 10	(1<g<p−1を満たす原始根)
- x = 8 (秘密鍵, 1<x<p−1を満たす自然数)
- r = 3 (暗号化のための乱数, 1<r<p−1を満たす自然数)

よって公開鍵は、

`y = 10^8 mod 499 = 400` (10^8を素数499で割ったあまり)



### 暗号化

- 公開鍵 `y` を持つ人に対して平文 `m` を暗号化するには整数`r`をランダムに選び以下のように表現できる
- ここで`r`は 1<r<p−1を満たす自然数であること. 乱数rを使う理由はAppendix参照

```math
\begin{align}
&c:= Enc\left(g^r\bmod p, my^r \bmod p\right). 
\end{align}
```

### 復号化 

暗号文 `(c1, c2) := Enc(m)` を受け取った人は自身の秘密鍵`x`を用いて以下で複合可能。
平文`m`を公開鍵`y`で暗号化して秘密鍵`x`で復号すると以下のように計算できる。

```math
\begin{align}
&Dec\left(Enc\left(m\right)\right)=Dec\left(c_1, c_2\right): = \frac{c_2}{{c_1}^x}\\
\end{align}
```

### 証明

ここで、確かに復号化可能か確かめてみよう, c1とc2を式展開すると

```math
\begin{align}
&c_1 =g^{r}\bmod p \\
&c_2 =my^r \bmod p = m\left(g^x \bmod p\right)^r \bmod p = mg^{rx} \bmod p\\
\end{align}
```

また`c1^x`はmodの世界で以下のように式変形できる。

```math
\begin{align}
&{c_1}^x = \left(g^{r}\bmod p\right)^x \bmod p = g^{rx} \bmod p  \\
\end{align}
```

よって確かに復号化可能。

```math
\begin{align}
&Dec\left(c_1, c_2\right): = \frac{c_2}{{c_1}^x} = \frac{mg^{rx}\bmod p}{g^{rx}\bmod p} = m 
\end{align}
```

## 電卓でElGamal暗号の手触り感を見てみよう

- p = 499 (素数)
- g = 10	(1<g<p−1を満たす原始根)
- x = 8 (秘密鍵, 1<x<p−1を満たす自然数)
- r = 3 (暗号化のための乱数, 1<r<p−1を満たす自然数)
- m = 77 (送りたいメッセージ何でも良い)

### 暗号化してみよう

- y = 400 (公開鍵, y=g^x mod p)
- c1 = 2	(送信情報: g^r mod p)
- c2 = 19712	(送信情報: my^r mod p)

### 復号化してみよう

- c1^x = 256 (=2^8)
- c2 = 19712
- m = 77 (=19712/256)

こうして見てみると、確かに, c1(2)とc2(19712)の情報から77の情報を取り出すのは難しそう・・・

# 準同型暗号

## 乗法準同型暗号

2個の平文とそれぞれ別の乱数を用意し、ElGamal暗号を記載すると

```math
\begin{align}
& Enc\left(m_1\right):=\left(g^{r1}\bmod p, m_1y^{r1} \bmod p\right) \\
& Enc\left(m_2\right):=\left(g^{r2}\bmod p, m_2y^{r2} \bmod p\right) \\
\end{align}
```

それぞれの要素をかけ合わせると各要素は以下のように式変形できる。
ここで重要なことは２つめの式に **m1とm2の掛け算**`m1m2`が見て取れること。

```math
\begin{align}
& \left\{\left(g^{r_1}\bmod p\right)\left(g^{r_2}\bmod p\right)\right\}\bmod p = g^{r_1+r_2}\bmod p \\
& \left\{\left(m_1y^{r_1}\bmod p\right)\left(m_2y^{r_2}\bmod p\right)\right\}\bmod p = m_1m_2\left(y^{r_1+r_2}\bmod p\right)
\end{align}
```

ここで各要素の掛け算を以下のように表現することにする。


```math
\begin{align}
& Enc\left(m_1\right)Enc\left(m_2\right)= Enc\left(m_1m_2\right)\\
\end{align}
```

このように**２つの平文m1,m2を暗号化したまま平文の積m1m2を得られた**ので、これを乗法準同型暗号という。

## 加法準同型暗号 (lifted-ElGamal暗号)

適当な整数 h をとり m の代 わりに h^m を暗号化してみる

```math
\begin{align}
& Enc^{\prime}\left(m_1\right)=Enc\left(h^{m_1}\right):=\left(g^{r_1}\bmod p, h^{m_1}y^{r_1} \bmod p\right) \\
& Enc^{\prime}\left(m_2\right)=Enc\left(h^{m_1}\right):=\left(g^{r_2}\bmod p, h^{m_2}y^{r_2} \bmod p\right) \\
\end{align}
```

乗法準同型暗号と同じく、要素どうしの積を考える。ここで重要なことはhのべき乗に`m1+m2` が見て取れることである。

```math
\begin{align}
& \left\{\left(g^{r_1}\bmod p\right)\left(g^{r_2}\bmod p\right)\right\}\bmod p = g^{r_1+r_2}\bmod p \\
& \left\{\left(h^{m_1}y^{r_1}\bmod p\right)\left(h^{m_2}y^{r_2}\bmod p\right)\right\}\bmod p = h^{m_1+m_2}\left(y^{r_1+r_2}\bmod p\right)
\end{align}
```

ここで各要素の掛け算を以下のように表現することにする。

```math
\begin{align}
& Enc^{\prime}\left(m_1\right)Enc^{\prime}\left(m_2\right)= Enc\left(h^{m_1}\right)Enc\left(h^{m_2}\right)= Enc\left(h^{m_1+m_2}\right)=Enc^{\prime}\left(m_1+m_2\right)\\
\end{align}
```

これは**暗号化したまま2つの平文の和m1+m2を得られた**ので、Enc′は加法準同型暗号という。

上記の議論により、以下も成立する。

- m1=m2=mとすると Enc′(2m) = 2Enc′(m) が成立する
- 一般に任意の整数 nに対して Enc′(nm)= nEnc′(m)も成立する


この平文mをhのm乗として乗っけたElGamal暗号方式をlifted-ElGamal暗号と呼びます.

## lifted-ElGamal暗号の注意点

- 復号する場合，ElGamal 暗号と同様に $h^m$　までは求められる
- しかし今 $h$ がわからないので、ここから $m$ を求めるのはほぼ不可能
- ただし $m$ がたとえば 0 以上 1 万以下の数値であるという制限があれば秘密鍵を知っている人だけが総当たりなどの手法を使うことで復号可能

# Appendix

## 選択平文攻撃から守るため乱数を使う

同じ秘密鍵 $K_A$ と同じ平文 $m$ を使っても $Enc(K_A , m)$ は毎回異なる値になる必要がある。

なぜか・・・

もし、Encがいつも同じ値を出力する決定的アルゴリズムだったら，以下平文を特定されるリスクがあるため

- A さんが "田中" か "鈴木" のどちらかを暗号化して暗号文cを作ったことがわかっているとします.
- 攻撃者は公開鍵$K_A$を使って以下を作成できます
    - `Enc(KA, 田中)`
    - `Enc(KA, 鈴木)`
- いつも同じ値を出力するということは、作った暗号文のどちらがcに等しいかを確認することで平文を当てることができてしまう。

このような、攻撃者が自分の好きな平文に対してその暗号文を入手できる状況での攻撃を選択平文攻撃CPA(Chosen Plaintext Attack)という。これを防ぐため、乱数rを使った。

ちなみに

- 共通鍵暗号: CPAが可能な状況はそれほど多くない
- 公開鍵暗号: 常にCPAを想定しなければならない。そのため公開鍵暗号は少なくとも確率的アルゴリズムである必要がある


# 参考文献

- [クラウドを支えるこれからの暗号技術](https://herumi.github.io/ango/)
- [Mathlog ElGamal暗号](https://mathlog.info/articles/88)
- [【数表】500以下の素数の原始根一覧](https://blog.thetheorier.com/entry/primitiveroot-list)