ペアリング
昨日の安全性証明でやった範囲でペアリングを使ったGap-Diffie-Hellman署名に関してメモを残す。
まず検索から参照された時のことを考えて暗号化に関して述べると、
今の暗号は基本的に暗号化したいメッセージに対してある数学的変換を加えるものを用いています。
その数学的変換の特徴とは鍵を持つ人が暗号化するときに計算コストが少なく高速で暗号化でき、
鍵を持たない他人からその計算と逆の計算を行い鍵を割り出そうとすると非常に計算量が増え
計算理論的に一定時間（年単位？）内でそのカギを暴けないようにすることよって守られています。
そこで使われる暗号化方式にDiffie-Hellman鍵交換の方式があり、
これは各ユーザが公開する鍵と自分だけが知っている鍵の二つを使い暗号化する方法である。
詳しくはネットで調べるとほかに詳しい説明がたくさんあるので省略します。
この鍵を公開する方式を公開鍵暗号というわけですが、
これは先日http://d.hatena.ne.jp/tyouiifan/20070522で述べたように
DDH問題、CDH問題、離散対数問題の計算量の多さによって守られいています。
先週書き忘れましたが計算量の複雑さでは
離散対数問題>CHD問題>DDH問題となっていて
難易度が上の方の問題がとけると下の問題も伴って解けるが、
下の問題が解けても上の問題の計算量には影響しない。
ここでペアリング暗号に関して話すと
まず、ペアリングでは楕円曲線というものを使うが、
これは特定の関数のグラフの点からなる値の集合です。
このグラフの特徴は、グラフ上の点を二つ取るとその和は
二点をつなげた直線がグラフの曲線と接する第三点のx軸対象にある点となることである。
一点を二倍するときはその点を二回足すだけで、
その点の接線がグラフと交わる点のx軸対象にある点となる。
この楕円曲線上の点に関してペアリングと呼ばれるあるブラックボックス関数e(P,Q)が定義できて
このブラックボックスはe(aP,bQ)=e(P,Q)^ab=e(bP,aQ)となるような性質をもつ。
ここで先週書いたDDH問題という問題を応用します。
Decision Diffie Hellman(DDH)は、(g,g^a,g^b,g^c)を与えられたとき、ab=cかどうかを判定する問題であり
つまり、この問題でいうg,g^cとg^a,g^bのそれぞれをe(P,Q)にいれれば
e(g,cg)=e(g,g)^c
e(ag,bg)=e(g,g)^abとなる。
ある数を数乗することは非常に計算量が大きいが、
このペアリングのe(P,Q)を使うとこの通りDDH問題が簡単に解ける。
Gap-Diffie-Hellman署名では
メッセージ、発行者公開鍵、と発行者秘密鍵で生成した署名を公開する。
鍵生成
ランダムにZp*からxを選び、v=g^xとなるvを計算する。
このvを公開鍵とし、xを秘密鍵とする。
検証
公開鍵vと文章M、署名σを用意し、メッセージからハッシュhを計算し
(g,v,h,σ)からDiffie-Hellman tupleを解いて検証する。
ここで言っているDiffie-Hellman tupleとは要するに(g,v,h,σ)を戻して考えればわかる
GからGの単位元要素1を除いた群をG*とすると
ハッシュ関数に全値域型ハッシュ法h:{0,1}*→G*となるものを用いて、hでハッシュ化したものは
Gの元であるのでg^aと表せるようにする。
すると(g,v,h,σ)はg=g v=g^x h=g^a σ=g^axとなる。
これがGDF署名であり
ここで楕円曲線で計算するとペアリングのブラックボックスe(P,Q)に代入して
e(g,cg)=e(g,g)^c
e(ag,bg)=e(g,g)^ab
と表せるので、ただの掛け算の計算量で指数計算の検証ができることになる。
しかも、指数計算を用いているので偽装する場合の計算量はかわらず多量で安全性が保障される。
