公開鍵暗号 - Paillier暗号

この記事では比較的新しい、かつ珍しい加法準同型性を持つPaillier暗号について解説する。

Paillier暗号とは、Pascal Paillierによって1999年に発明された公開鍵暗号で、素因数分解を安全性の根拠としている。この暗号は、メッセージ\(Enc(m_1), Enc(m_2)\)からそれらを足し合わせた暗号文を作ることができるという性質を持っている。これを加法準同型性といい、暗号の中でも非常に少ない(乗法準同型性は他にもRSA, Elgamal等に見られる)、珍しい暗号である。

鍵の生成

  • 2つの大きな素数\(p, q\)をランダムに選択し、\(n = pq\)を計算する。
  • \(k\in\mathbb{Z} _ n\)をランダムに選び、\(g = (kn+1) \mod n ^ 2\)を計算する。

公開鍵を\( (n, g) \)、秘密鍵を\( (p, q) \)とする。

暗号化

暗号化関数\(Enc(m)\)を次のように定義する。 \[Enc(m) := g ^ m\cdot r ^ n\] ただし、\(r\)は\(r\in\mathbb{Z} ^ {*} _ {n ^ 2}\)で、暗号化ごとにランダムに選ばれる。

復号

復号関数\(Dec(c)\)を次のように定義する。 \[Dec(c) := \frac{L(c ^ {\lambda} \mod n ^ 2)}{L(g ^ {\lambda} \mod n ^ 2)} \mod n\] この時、\(L(u) = \frac{u-1}{n}\)で、\(\lambda = \mathrm{lcm}(p-1, q-1)\)である。

根拠

\(\lambda\)という値が出てきた。これは、実際にはカーマイケルの\(\lambda\)関数と呼ばれるもので、オイラーのトーティエント関数を更に厳密にしたようなものと言える。 この関数は、\(\lambda(n)\)として次のように定義される。

\(n=2 ^ e\)の時 \[\lambda(2 ^ e) = \begin{cases} 1 & if\ e = 1\\ 2 & if\ 2 = 2\\ 2 ^ {e-2} & if\ e \geq 3 \end{cases} \]

\(n = p ^ e\)(\(p > 2\)な素数)の時

\[\lambda(p ^ e) = p ^ {e-1}(p-1)\]

\(n = p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}\)の時

\[\lambda(p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}) = \mathrm{lcm}(\lambda(p _ 1 ^ {e _ 1}), \lambda(p _ 2 ^ {e _ 2}), \ldots, \lambda(p _ k ^ {e _ k}))\] この\( \lambda(n) \)関数を用いると、以下のカーマイケルの定理を証明できる(ここでは略する)

カーマイケルの定理

\(a, m \in \mathbb{Z}\)があり、それぞれが互いに素な時、 \[a ^ {\lambda(n)} \equiv 1 \mod n\] が成り立つ。

ここで、\(n=p _ 1 p _ 2 \ldots p _ k\)の時、もう一つ次の事実も示す事ができる。

\(a, m \in \mathbb{Z}\)があり、それぞれが互いに素かつ\(n=p _ 1 p _ 2 \ldots p _ k \)な時、 \[a ^ {n\lambda(n)} \equiv 1 \mod n ^ 2\] が成り立つ。

少し計算すれば上の事実は理解できると思うので、こちらも証明は略する。

ところで、二項定理を知っているだろうか。\((x+y) ^ n\)という式を展開するとある規則で全ての項が\(ax ^ b y ^ c\)となるような項の和に分解できる、というものだ。 ここで、その二項定理を用いて次の式を展開してみよう。

\[ (1 + n) ^ k \mod n ^ 2 \]

modがかかっていることに注意すると、以下のように簡潔な式が得られる。

\[ \begin{align} (1 + n) ^ k &= 1 + kn + \frac{k!}{2!(k-2)!} n ^ 2 + \frac{k!}{3!(k-3)!} n ^ 3 + \ldots \mod n ^ 2\\ &= 1 + kn + n ^ 2 (\frac{k!}{2!(k-2)!} + \frac{k!}{3!(k-3)!} n + \ldots) \mod n ^ 2\\ &= 1 + kn \mod n ^ 2\\ \end{align} \]

\(n\)を\(a\cdot n\)と置き換えても同様に\((1 + a\cdot n) ^ k = 1 + akn \mod n ^ 2\)が成り立つことは簡単に確かめられる。

以上を踏まえて、復号処理を追ってみよう。まず、\(c ^ \lambda\)を計算するので、これを展開すると、

\[ \begin{align} c ^ \lambda &= (g ^ m r ^ n) ^ \lambda \mod n ^ 2\\ &= g ^ {m\lambda} r ^ {n\lambda} \mod n ^ 2\\ &= g ^ {m\lambda} \mod n ^ 2\\ &= (1 + kn) ^ {m\lambda} \mod n ^ 2\\ &= 1 + m \lambda k n \mod n ^ 2 \end{align} \]

\(r ^ {n\lambda} \mod n ^ 2\)はカーマイケルの定理より1になることに注意すれば、さほど難しくはない。次に、関数Lを適用する。

\[ \begin{align} L(c ^ \lambda \mod n ^ 2) &= L(1 + m \lambda k n \mod n ^ 2)\\ &= \frac{1 + m \lambda k n - 1}{n}\\ &= m \lambda k \end{align} \]

分子は計算できた。同様に、分母の部分も計算する。

\[ \begin{align} L(g ^ \lambda \mod n ^ 2) &= L(1 + \lambda k n \mod n ^ 2) \mod n ^ 2\\ &= \frac{1 + \lambda k n - 1}{n}\\ &= \lambda k \end{align} \]

これに\(\mod n\)上の除算を適用して、

\[ \begin{align} \frac{m \lambda k}{\lambda k} &= m \mod n \end{align} \]

結果として、平文を得る事ができた。

加法順同型性

Pailier暗号には、珍しい加法順同型性が備わっていると書いた。実際にそれを追ってみよう。 最初に、公開鍵/秘密鍵\(n = pq, g, r_1, r_2\)、平文\(m_1, m_2\)とそれぞれの暗号文\(c_1, c_2\)とする。\(c = c_1 \cdot c_2 \mod n ^ 2\)として、

\[ \begin{align} c &= c_1 \cdot c_2 &= g ^ {m_1 + m_2}\cdot r_1 ^ n\cdot r_2 ^ n \mod n ^ 2\\ c ^ \lambda &= (g ^ {m_1 + m_2}\cdot r_1 ^ n\cdot r_2 ^ n) ^ \lambda \mod n ^ 2\\ &= g ^ {(m_1 + m_2)\lambda}\cdot r_1 ^ {n\lambda}\cdot r_2 ^ {n\lambda} \mod n ^ 2\\ &= g ^ {(m_1 + m_2)\lambda}\cdot 1\cdot 1\mod n ^ 2\\ &= (1 + kn) ^ {(m_1 + m_2)\lambda} \mod n ^ 2\\ &= 1 + (m_1 + m_2) \lambda k n \mod n ^ 2 \end{align} \]

見事に、\(m\)の部分が\(m_1 + m_2\)に置き換わっていることがわかると思う。後は自明な代数の演習なので、暇があれば計算してみると良いと思う。

その他

実は、加法順同型性はPaillier暗号が初めてというわけではなく、その少し前に岡本-内山暗号という暗号系がそれを達成している。そのうち取り上げるかもしれないが、とりあえずWikipediaを読んでおくと良いかと思う。

リファレンス/参考文献/参考リンク