はじめに
この記事は大阪工業大学 Advent Calendar 2022の21日目の記事です。
急いで書いたので怪文書になってるかもしれません。
凖同型暗号とは
凖同型暗号とは、暗号化したまま計算ができる暗号方式である。
計算をするときに、複数の事象の類似性を利用する数学的な性質を使っている。
今までは、足し算だけ、掛け算だけができる暗号は2000年までには基礎ができていた。
2009年にGentryが達成している。しかし、当時は1bitの平文の暗号文が1GBとすごく頭でっかち
環凖同型写像とは
環Aから環Bへの写像$f$は次の3つの条件を満たすとき。環凖同型写像という。
- $f(x + y) = f(x) + f(y)$
このとき$f$は加法群の凖同型写像であり、従って次が成り立つ。
$f(x - y) = f(x) - f(y), f(-x) = -f(x), f(0) = 0.$ - $f(xy) = f(x)f(y)$
- $f(1) = 1$
完全とは
0と1の世界では足し算は、xor、掛け算はandに相当している。
足し算
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
掛け算
| * | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
これらの計算の両方ができると任意の関数$f$に対して暗号を構成することが可能になる
$f(Enc(message)) = Enc(f(message))$
雰囲気
今回は二個の暗号文を考える
$c_1 = m_1 + e_1, c_2 = m_2 + e_2$
加法凖同型
$c_1 = m_1 + e_1, c_2 = m_2 + e_2$ これらを足すと
$c_1 + c_2 = (m_1 + m_2) + (e_1 + e_2)$ になる
これは$m_1 + m_2$の情報 + ノイズの形になったので
暗号文から$m_1 + m_2$が取り出すことができるい。
これが加法凖同型である。
乗法凖同型
$c_1 = m_1 + e_1, c_2 = m_2 + e_2$
$c_1c_2 = (m_1 + e_1)(m_2 + e_2)$
$ = m_1m_2 + (m_1e_2 + m_2e_1 + e_1e_2)$
$ = m_1m_2 + e' $
$e_1, e_2$が$m_1, m_2$に比べて十分に小さければ
$e' = m_1e_2 + m_2e_1 + e_1e_2$は$m_1m_2$に比べて小さい
$c_1c_2$は$m_1m_2$の情報 + ノイズの形にすることができたので
暗号文から$m_1m_2$を取り出すことができる
これが乗法凖同型である。
完全凖同型
加法凖同型 + 乗法凖同型 = 完全凖同型
ブートストラップ
ノイズが増えて大変なことになるので定期的にリセットする機構 (あとで書く)
参考文献
可換代数入門 Atiyah-MacDonald