推しを推すだけの人生

色々書きます

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

【はじめに】

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

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

【IDベース暗号】

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

C = M^E (\mod N)

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

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

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

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

\begin{align} (M + kQ) - x(kP) = M + kxP - xkP = M \end{align}

となります.次に準同型であることも確かめます.加法準同型になるらしいので倣ってみます.

\begin{align} Enc(M_1) + Enc(M_2) &= ((k_1 + k_2)P, M_1+M_2+(k_1+k_2)Q)\\ &=(k'P, M_1+M_2+k'Q)\\ &=Enc(M_1+M_2) \end{align}

なりましたね.

【最後に】

あまり中身のある内容ではなくなってしまいました。。。リレー一週目の一番手なのでハードルは上げすぎずという言い訳をしておきます。。。 暗号技術はちゃんと触れたことがなかったのでこれを機にしっかり勉強してみたいと思っています。
次回の方は9/18に更新予定です。

【参考文献】

暗号文のままで計算しよう - 準同型暗号入門 -

楕円曲線入門トーラスと楕円曲線のつながり

クラウド時代の暗号化技術論

IDベース暗号の概観と今後の展望