IDベース暗号と準同型暗号を触るだけ

【はじめに】

　セキュリティキャンプで行ったグループワークの一環で、ブログを書くことになりました。リレー形式で一週間ごとにブログを回し、前回バトンを持っていた人が次の人のテーマを決めるというルールです。

　今回の私のテーマは「暗号」でした。暗号についてはAESとRSAくらいしか勉強したことがなかったのでとりあえず「聞いたことある単語をなんとなく知ってる程度まで理解する」ことを目標にしました。今回はIDベース暗号と準同型暗号をとりあげてみます。(間違いがあれば指摘していただければと思います。。。)

【IDベース暗号】

　公開鍵に自分の好きな文字列を入れることができる暗号をIDベース暗号といいます.
　例えばRSA暗号では,

$C = M^E　(\mod N)$

と公開鍵Eが使われますが,この公開鍵は復号鍵Dと合わせて

$M = M^{ED} (\mod N )$

となる必要があるので, $E,D,N$ はその制限に従う必要があります.一方で,IDベース暗号では任意のデータを公開鍵に設定することができます.手順は以下のようになります.

Key Generation Center が初期化をし,楕円曲線上の点 $P$ ,乱数(マスタ秘密鍵) $s$ , $T=sP$ (システムパラメータ),ハッシュ関数 $H_1$ , $H_2$ とペアリング関数 $e$ を用意します.
ユーザのIDから秘密鍵を
$k=sH_1(ID)$
と計算します.
乱数 $r$ を用意し, $g=e(H_1(ID), T)$ と $rP$ をを計算します.
$C=\langle rP, M \oplus H_2(g^r) \rangle (= \langle U, V \rangle)$
により,暗号化平文 $M$ に対して暗号化を施します.
逆に復号するときは
$M=V \oplus H_2 (e(k, U))$
とします.

復号の部分を計算してみます.

\begin{align} M&=V \oplus H_2 (e(k, U))\\ &=M \oplus H_2(g^r) \oplus H_2 (e(k, U))\\ &=M \oplus H_2(e(H_1(ID), T)^r) \oplus H_2(e(k, rP))\\ &=M \oplus H_2(e(H_1(ID), sP)^r) \oplus H_2(e(sH_1(ID), rP))\\ &=M \oplus H_2(e(H_1(ID), P)^{sr}) \oplus H_2(e(H_1(ID), P)^{sr}) \end{align}

$e$ はペアリング関数なので,双線形性から

$e(P, Q)^r = e(rP, Q) = e(P, rQ)$

が成り立つことと,排他的論理和の性質から復号ができます.

【準同型暗号】

　暗号化されたデータ同士で加算、または乗算のどちらかのみができるとき、それを準同型暗号といいます。完全準同型暗号になると、加算と乗算が両方でき、任意の演算ができるようになります。0,1で構成される世界では加算と乗算でほかの演算を構成できるため、加乗算ができれば任意の暗号回路演算を実現できるということでしょうか。
例えば,預金残高を保存しているデータベースがあるとして,残高とそれに結びついているユーザ情報は暗号化されている必要があります.このデータベースですべての預金残高合計を知りたいとき,いちいち平文に戻してから計算していると,戻した時点で漏えいすると危険なので,暗号のまま預金残高合計を計算できると便利だと思います.
参考文献では楕円ElGamal暗号でデモをしていたので,私もそれに倣ってみます.楕円曲線はトーラス上の計算で,一周するともとに戻る性質を持ちます.昔のドラクエのように,長方形のマップ上で上辺を越えると下辺に戻り,右辺を越えると左辺に戻ります.(図でも書けばよかった)
まず楕円曲線上の点Pと,秘密鍵kを用いて $Q=kP$ を計算します.このときkが秘密鍵で,(P, Q)が公開鍵ということになります.ここで, P, Q から kを求めることが困難であることを楕円曲線離散対数問題(ECDLP)と言い,これが困難であるうちは楕円曲線が安全であるということになります.
暗号化手順： $Enc(M) = (kP, M+kQ) = (C_1, C_2)$
復号化手順： $Dec(C) = C_2 - xC_1$
一応復号を確かめてみると,