(57)【特許請求の範囲】
【請求項１】
有限巡回群以外の有限可換群を利用し、２つの巡回群の直積への一般線形群の作用を使用して、離散対数問題よりも困難性の高いと考えられるアルゴリズム問題の困難性に安全性の根拠をおいたキーアグリーメントプロトコルを用いて第１通信端末と第２通信端末との間で通信を行う通信方法であって、
次の条件、すなわちＧをＣｘＣ（Ｃは次数が素数ｐの巡回群）と同形の群とし、ａとｂがＧを生成すると定義すると共に、パラメータα、β、γ、δを、ｐを法としてαβγδが平方非剰余になるようにランダムに選択する条件において、
第１通信端末の演算手段が、整数i1、i2をランダムに選択するステップ、
該演算手段が
【式２２】
0004288341.tif 000102
を計算し、それを送信手段が第２通信端末に送るステップ、
第２通信端末の演算手段が、整数j1、j2をランダムに選択するステップ、
該演算手段が
【式２３】
0004288341.tif 000103
を計算し、それを送信手段が第１通信端末に送るステップ、
第１通信端末の演算手段が、
【式２５】
0004288341.tif 000104
と
【式２６】
0004288341.tif 000105
を計算して乗ずることにより
【式２４】
0004288341.tif 000106
のＫを得るステップ、
第２通信端末の演算手段が、
【式９３】
0004288341.tif 000107
と
【式９４】
0004288341.tif 000108
を計算して乗ずることにより
【式２４】
0004288341.tif 000109
のＫを得るステップ
の各ステップを含み、
該Ｋを第１通信端末と第２通信端末との共通鍵とする
ことを特徴とする通信方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ通信の暗号化技術に関わり、特に従来導入されていなかったアルゴリズムを用いたキーアグリーメントプロトコルを提案するものである。
【０００２】
【従来の技術】
近年、インターネットなどのデータ通信技術の急速な進歩に伴い、日常さまざまな場面で情報通信を利用する機会が増えている。その中でデータ通信の傍受による情報の漏洩が社会問題となっており、特に、行政機関からのプライバシー情報の漏洩や、売買取り引きや金融などの分野ではデータの悪用によって莫大な損害が発生する恐れがある。
そこで、社会的にも情報の秘匿性を高める技術が強く求められており、多種多様な情報の暗号化技術が開発されてきた。しかし、高い技術による暗号化技術も、攻撃者によって徐々に解読され、常に情報漏洩の危険にさらされているのが現状である。
【０００３】
データ通信の安全性を図る方法として、計算処理の困難性を逆手にとって、難解なアルゴリズム問題の困難性から、安全性を担保する手法が知られており、攻撃者にも極めて高度な能力が要求されるため、有効な手段と考えられる。
例えば、現在までに知られている鍵交換スキーム（例えばDiffie-Hellman型）においては有限巡回群の離散対数問題を解くことの難しさにその安全性の基礎をおいている。
【０００４】
現時点では、上記鍵交換スキームによって、高度な安全性が保証されていると考えられるが、上述したように、これらの技術は攻撃者とのいたちごっこである現実に鑑みると、多様な手法が求められている状況である。
しかしながら、これまでの技術では、鍵交換スキームにおいては現実的にはDiffie-Hellman型のスキームしか考えてられておらず、有限巡回群以外の群を利用する鍵交換スキームは知られていない。
【０００５】
また、有限可換群を利用することは可能であり、提案されてもいるが本質的にはそれらは有限巡回群を利用するDiffie-Hellman型のスキームまたは、その変形であり、本質的に有限可換群を用いる方法は提供されていない。
【０００６】
【発明が解決しようとする課題】
本発明は上記従来技術の有する問題点の解決を図るものであって、その目的は、データ通信で用いられるキーアグリーメントプロトコルについて、新しいアルゴリズム問題に基づき、高い安全性を備えたプロトコルを提供することである。
【０００７】
【課題を解決するための手段】
上記課題の解決を図るため、本発明では次の手段を用いる。
すなわち、本発明は有限巡回群以外の有限可換群を利用し、離散対数問題よりも困難性の高いアルゴリズム問題の困難性に安全性の根拠をおくと共に、２つの巡回群の直積への一般線形群の作用を使用して、一般化された離散対数問題の困難性と安全性が計算量的に等価であるキーアグリーメントプロトコルを用いて第１通信端末と第２通信端末との間で通信を行う通信方法である。
【０００８】
具体的には、次の各ステップを含む。
まず、ＧをＣｘＣ（Ｃは次数が素数ｐの巡回群）と同形の群とし、ａとｂがＧを生成すると定義する。パラメータα、β、γ、δを、ｐを法としてαβγδが平方非剰余になるようにランダムに選択する。このような条件のもとで、
（１）  第１通信端末の演算手段が、整数i1、i2をランダムに選択するステップ、
（２）同じく第１通信端末の演算手段が、
【式２２】
0004288341.tif 000002
を計算し、それを第１通信端末の送信手段が、第２通信端末に送るステップ、
（３）  第２通信端末の演算手段が、整数j1、j2をランダムに選択するステップ、
（４）同じく第２通信端末の演算手段が、
【式２３】
0004288341.tif 000003
を計算し、それを第２通信端末の送信手段が、第１通信端末に送るステップ、
（５）  第１通信端末の演算手段が、
【式２５】
0004288341.tif 000004
と
【式２６】
0004288341.tif 000005
を計算して乗ずることにより
【式２４】
0004288341.tif 000006
のＫを得るステップ、
（６）  第２通信端末の演算手段が、
【式２８】
0004288341.tif 000007
を計算しＫを得るステップ、
以上の各ステップを含み該Ｋを第１通信端末と第２通信端末との共通鍵とする。
【０００９】
【発明の実施の形態】
以下に、本発明における実施形態として、キーアグリーメントプロトコルの詳細を説述する。
まず、本発明の概要を述べる。ジェネリック・アルゴリズム(【参考文献６】、【参考文献１０】、【参考文献５】、【参考文献４】、【参考文献８】、【参考文献７】)は、群演算オラクルや他のいくつかの特別なオラクルを呼び出すことによって解を求める確率的アルゴリズムの一般的モデルである。
【００１０】
そのようなモデルにおいて、群は、ブラック・ボックス群（【参考文献１】）として与えられ、各群要素は、同じ長さの２進文字列によって表される。代表的なジェネリック・アルゴリズムは、Baby-Step-Giant-StepとPohlig-Hellmanである。
群演算、乗算および逆数の取得は、ジェネリック・アルゴリズム・モデル内のオラクルを呼び出すことによって行われる。解は、所定の条件を満たす特定の群要素、または離散対数のような情報でよい。離散対数問題(DLOG)、Diffie-Hellman問題(DH)(【参考文献１０】、【参考文献５】)および暗号システム(【参考文献４】、【参考文献７】、【参考文献８】)を解析するために、ジェネリック・アルゴリズム・モデルが使用される。
【００１１】
本発明では、ジェネリック・アルゴリズムが、オラクル・クエリの数が制限された[Z]px[Z]pと同形のブラック・ボックス群について正しい解を求める確率を推定する。ジェネリック・アルゴリズム・モデルにおける乗法的離散対数問題(MDLOG)を解くために、群演算に対する
【式1】
0004288341.tif 000008
クエリと離散対数オラクル(および、提案されたキー・アグリーメント・プロトコルの基になるACTDH問題と呼ばれるアルゴリズム問題の【式1】クエリ)が必要
であることを示す。
【００１２】
次に、本発明におけるキーアグリーメントプロトコルについて詳述する。
Sを群とし、Xを非空の集合とする。Sは、必ずしも交換可能でなくてもよい。S内のsとtおよびX内のxに関してx(st)=(xs)tおよびx1=xを満たす写像σ:X x S → X(σによる(x,s) ∈ X x Sの像は、x3で示される)の場合に、SがXに作用する。
群作用は、暗号学では一般的であるが、群作用に関して、最も一般的な暗号システムのメカニズムであるDiffie-HellmanとRSAについて説明する。
【００１３】
（例１）  pを素数とする。p-1が素数qで割れると仮定する。|g|=qになるような要素a∈[Z]*pをとる。この場合、σ(g,s) = gsで与えられるσ:<g> x [Z]*p <g>は、巡回群<g>への[Z]*pの作用である。
DLOGは、所与のgとσ(g,s)=gsに関してsを求める問題と見なされる。この作用は、Diffie-Hellmanプロトコル（【参考文献２】）とElGamal暗号（【参考文献３】）において使用される。
【００１４】
（例２）  p,qを素数とする。n = pqとする。RSA暗号システムは、σ(m, e) = meによって与えられる
【式2】
0004288341.tif 000009
として定義される作用を採用する。RSAは、e乗根を求める計算処理の困難性、すなわち、所与のeに関するmとσ(m,e) = meを求める問題に基づく。
【００１５】
ここで、一般的な方法を示す。
群Sが集合Xに作用し、この作用が常に効率よく計算できると仮定する。fを、Xに関して効率的に計算可能な関数とする。Sが、必ずしも交換可能である必要はないことに注意されたい。Soを、以下の条件を満たすSの部分集合とする。
仮定１：すべてのs, t ∈ Soに関してs(t') = t(s')となるように効率よく計算可能な関数':So→Sがある。
仮定２：xsとxtが与えられたときにf(xst')を計算する効率的なアルゴリズムがない。
Sが交換可能なとき、仮定１が機械的に真になることに注意する。これは、恒等写像を’としてとることができるためである。しかしながら、そのような関数は、一般に必ずしも存在するとは限らない。Diffie-Hellmanの仮定は、仮定２の特殊な場合であり、ここで、Sは[Z]pであり、fは恒等写像である。
【００１７】
キー・アグリーメント・プロトコルの一般的な方式は次の通りである。
初期設定:  x∈Xとなるxを選択し、それを公表する。
ステップ１：第１通信端末が、s∈Soとなるsをランダムに選択する。第１通信端末は、xsを計算し、それを第２通信端末に送る。
ステップ２：第２通信端末は、t∈Soとなるtをランダムに選択する。第２通信端末は、xtを計算し、それを第１通信端末に送る。
ステップ３：第１通信端末は、(xt)s' とf((xt)s')を計算する。第２通信端末は、(xs)t'とf((xs)t')t'を計算する。この場合、
【式3】
0004288341.tif 000010
は、第１通信端末と第２通信端末によって共有される共通秘密キーである。仮定１により、(xt)s' = (xs)t' となる。
【００１８】
次に、本発明に係るACTDHプロトコルを説述する。
Gを、C x Cと同形の群とし、Cは、次数が素数pの巡回群である。ここで、群G x G(=(C x C)x(C x C))へのGL(2,[Z]p)の作用を定義する。aとbがGを生成すること、すなわちG = <a,b>である仮定する。これは、|a| = |b| = pでありGにおいて<a> ∩ <b> = [1G]であることを暗黙的に示し、ここで、1Gは、Gの恒等元を示す。
【００１９】
Gのすべての要素は、i,j ∈ [Z]pの場合に、aibiとして一意に記述される。
【式4】
0004288341.tif 000011
で
【式5】
0004288341.tif 000012
の場合、
【式6】
0004288341.tif 000013
へのGL(2,[Z]p) の作用を定義する。xAが、次のように効率よく計算可能である。
【００２０】
Gの要素ai1j1およびai2j2と行列Aが与えられたとして、
【式7】
0004288341.tif 000014
を計算する。GL(2,[Z]p)が、G x Gにこのように作用することはすぐに分かるが、以下のようにより分かりやすい説明も可能である。
要素
【式8】
0004288341.tif 000015
と行列
【式9】
0004288341.tif 000016
を識別する場合、xAは、次のような行列式で識別される。
【式10】
0004288341.tif 000017
【００２１】
行列乗算は結合的であるため、GL(2,[Z]p)が、G x Gに作用する。次に、[Z]*pにおけるパラメータα、β、γ、δを、αβγδが平方非剰余になるようにランダムに選択し、次にSoを、形
【式11】
0004288341.tif 000018
の一組の行列になるように定義する。ここで、(i1,i2) ≠ (0,0)の場合、i1,i2 ∈ [Z]pである。
【式12】
0004288341.tif 000019
に関して、A'を行列
【式13】
0004288341.tif 000020
になるように定義する。αβγδが平方非剰余であるため、A,A' ∈ GL(2,[Z]p) である。
【式14】
0004288341.tif 000021
でありかつ
【式15】
0004288341.tif 000022
である場合は、A,B ∈ Soであり、次の式となる。
【式16】
0004288341.tif 000023
【００２２】
したがって、上記の仮定１は、成り立つ。以降では、行列
【式17】
0004288341.tif 000024
と
【式18】
0004288341.tif 000025
をそれぞれ、A(i1,i2)とA'(i1,i2)で表わす。したがって、すべてのi1,i2,j1,j2∈[Z]pに関して、次の式が得られる。
【式19】
0004288341.tif 000026
π1 : G x G → Gを第一の軸に対する射影、すなわち
【式20】
0004288341.tif 000027
とする。
【式21】
0004288341.tif 000028
であることに注意する。
【００２３】
ACTDHプロトコル:  x = (a, b)とする。
ステップ１：第１通信端末の演算手段が、整数i1、i2をランダムに選択する。同演算手段は
【式22】
0004288341.tif 000029
を計算し、それを送信手段によって第２通信端末に送る。
ステップ２：第２通信端末の演算手段が、整数j1、j2をランダムに選択する。同演算手段は、
【式23】
0004288341.tif 000030
を計算し、それを送信手段によって第１通信端末に送る。
【００２４】
ステップ３：第１通信端末の演算手段が、第２通信端末から送られた式２３の計算結果を用いて、
【式２５】
0004288341.tif 000031
と
【式２６】
0004288341.tif 000032
を計算して乗ずることによって
【式２４】
0004288341.tif 000033
を得る。なお、式２１に示したように、
【式２７】
0004288341.tif 000034
である。
ステップ４：第２通信端末の演算手段が、同様に、第１通信端末から送られた式２２の計算結果を用いて、
【式９３】
0004288341.tif 000035
と
【式９４】
0004288341.tif 000036
を計算して乗ずることにより
【式２４】
0004288341.tif 000037
を計算する。なお、式２１に示したように、
【式２８】
0004288341.tif 000038
である。この場合、Kが第１通信端末と第２通信端末の共通鍵となる。
【００２５】
ここで、一例として、素数次数の２つの巡回群の直積の例を示す。qとrを、p|q - 1でかつp| r - 1となるような大きい素数とする。
nをqrとする。g1を、mod qにおける1のp乗根とし、g2を、mod rにおける1のp乗根とする。いくつかのc1 ∈ [Z]*pおよびc2 ∈ [Z]*pについて、a = g1 (mod q)、a = g*2 (mod r)、b = g*1(mod q)、b = g2(mod r)となるように、a ∈ Znとなるaおよびb ∈ Znとなるbを選択する。c1c2 ≠ 1 mod pの場合にZ*n =<a> x <b>であることは明らかである。
【００２６】
次に、本発明のプロトコルのセキュリティを、Diffie-Hellmanプロトコルと比較する。
ACTDHプロトコルの解読は、以下の問題を解くことと等価である。Gが、有限のアーベル群であり、a,b ∈Gであると仮定する。パラメータα、β、γ、δはそれぞれ、|a|および|b|と互いに素である。aとbに関するGにおける作用Diffie-Hellman問題(ACTDH問題)の定義は、次の通りである。
【式29】
0004288341.tif 000039
【式30】
0004288341.tif 000040
ここで、i1、i2、j1、j2は、無作為かつ独立に選択された整数である。
【００２７】
以下の定理とその証明により、パラメータを慎重に選択すれば、ACTDHプロトコルが、少なくともDHプロトコルと同程度のセキュアであることを保証する。
＜定理１＞  α、β、γ、δを整数とする。これらはそれぞれ、|G|と互いに素であると仮定する。Gのすべてのa、bについてアーベル群GにおけるACTDH問題(パラメータα、β、γ、δ)を解く効率のよいアルゴリズムが存在する場合は、GのすべてのaについてGにおけるDH問題を解く効率のよいアルゴリズムが存在する。
【００２８】
＜証明＞  すべてのaとbについてACTDH問題を解く効率のよいアルゴリズムがあると仮定する。DH問題を解く効率のよいアルゴリズム、すなわち入力ai1およびaj1に関してai1j1を計算するアルゴリズムを作成する。ここで、aは、Gの要素である。b=1(Gの単位元)とする。|G|が|a|で割れるため、α、β、γ、δは、|a|と互いに素でなければならない。上の仮定により、aとbに関してACTDH問題を解く効率のよいアルゴリズムが得られる。i2=j2=0とする。aとbに関してACTDH問題を解くアルゴリズムに
【式31】
0004288341.tif 000041
と
【式32】
0004288341.tif 000042
を入力する。こうして、
【式33】
0004288341.tif 000043
が得られる。ai1とaj1が与えられ、αが公の情報であるため、(ai1)αと(aj1)αを計算することができることが分かる。αとδが両方とも、|a|と互いに素であるため、(aαδ)m = aとなるような整数mを求めることができる。この場合、
【式34】
0004288341.tif 000044
であり、したがって、DH問題が効率よく解かれる。
【００２９】
Gを有限のアーベル群とし、aとbをGにおける要素とする。Hを、aとbによって生成されたGの小群になるように設定する。群H = <a, b>における複数の離散対数問題(略してMDLOG)は、次のように定義されたアルゴリズム的な問題である。
INPUT:  Hの要素g。
OUTPUT:  g = axbyになるような負でない整数(x,y)のペア(x, y)。
Hが、aとbによって生成されるため、g = axbyを満たす負でない整数のペア(x,y)が少なくとも1つ存在する。そのようなペアは、Hが、内部直積<a> x <b>であるときだけ一意に決定される。ACTDH問題がMDLOG問題に縮小されることは明らかであり、それにより、MDLOGが効率よく解かれる場合にACTDHプロトコルを解読することができる。
【００３０】
ACTDHプロトコルのセキュリティをジェネリック・モデルの視点から考察する。パラメータを慎重に選択したACTDHプロトコルは、ジェネリック・モデルにおけるDHプロトコルよりもセキュアである。議論を簡素化するために、[Z]p x [Z]pと同形の乗算群G に関するACTDHプロトコルだけを検討する。ここで、pは、本論文の残りの部分において大きい素数である。ACTDHプロトコルは、α、β、γ、δに以下のような条件を課す場合にDLOGを解くことができる攻撃者からさえもセキュアである。
【００３１】
＜条件１＞  α、β、γ、δは、pと互いに素である。
＜条件２＞  αβγδは、平方非剰余である(mod p)。
条件１および条件２は、本論文の残りの部分で満たされると仮定する。条件１は、α、β、γ、δが、要素a,b ∈ Gを縮小させるのを防ぐために課される。一方、条件２は、多少不自然のように見える。条件２については、後述する。
【００３２】
本発明に係るジェネリック・アルゴリズムにつき、詳述する。
ジェネリック・アルゴリズムは、群の表現のどの特性にも依存しない汎用アルゴリズムである(【参考文献１０】、【参考文献５】)。ジェネリック・アルゴリズムは、Gの要素の所与の集合から始まる群要素、すなわちGの生成元の集合Bから始まる群要素を列挙し、これは、各iのいくつかのj,k < iに関してgm = gとgi ∈ Bまたはgi=g-1jまたはgi = gjgkになるようにGの要素の数列g1,g2,... ,gmを列挙する。
ある段において、アルゴリズムは、同一の2進文字列を表す要素giおよびgj(i≠j)を求める。次に、giとgjに関する情報から得られた一次方程式を解くことによって、隠された情報を得ることができる。
【００３３】
σを、[Z]pから大きさpの2進文字列の集合Sへのランダムな写像とする。ジェネリック・アルゴリズムは、x,y ∈ [Z]pに関してadd(σ(x),σ(y)) = σ(x+y) と inv(σ(x))によって定義されたaddとinvを、計算上の犠牲なしに計算する群演算オラクルを呼び出すことができる。add(σ(x),σ(y)) = σ(x + y)が、乗算gxgy = gx+yに対応し、inv(σ(x)) = σ(-x)が、群要素の反転(g)-1 = g-1に対応する。巡回群[Z]pにおけるDLOGのジェネリック・アルゴリズムは、入出力xとして(σ(1), σ(x))をとる。ここで、x ∈ [Z]pである。【参考文献５】において、DHへのDLOGのジェネリック帰着を研究するためにDiffie-Hellmanオラクルが導入されている。
【００３４】
次に、ジェネリック帰着に関してDLOG問題と比較したACTDFIプロトコルの解読の困難さについて詳細に調べる。ACTDH問題のジェネリック・アルゴリズムは、以下のように実行される。群[Z]px[Z]p(pは素数)が、2進文字列の集合Sによって符号化される。ジェネリック・アルゴリズムは、入力としてリスト(σ(1,0),σ(0, 1),σ(αi1,βi2),σ(γi2,δi1),σ(αj1j1,βj2),σ(γj2,δj1))を取得し、群演算オラクルを呼び出すことによって計算し、次に
【式35】
0004288341.tif 000045
を出力する。入力が、群要素
【式36】
0004288341.tif 000046
に対応し、出力が、群要素
【式37】
0004288341.tif 000047
に対応する。群演算オラクルの他に、離散対数オラクルを呼び出すジェネリック・アルゴリズムを可能にする。[Z]p x [Z]pの離散対数(DLOC)オラクルは、入力として(σ(i1,i2), σ(j1,j2)) を取得し、次に、ni1 = j1(mod p)およびni2 = j2(mod p)が、そのようなnが存在する場合に、計算上の犠牲なしに成り立つように、整数nを出力する。
【００３５】
上の式を満たすnが存在しない場合は、そのような入力はイリーガルと呼ばれる。オラクルがイリーガル入力の対象でなく、かつジェネリック・アルゴリズムが進行すると仮定する。
＜定理２＞  Aを、群[Z]p x [Z]pにおけるACTDH問題を解くジェネリック・アルゴリズムとする。ここでpは素数である。パラメータα、β、γ、δは、上記条件１および２を満たす。Aが、群演算オラクルに対する最大でRのクエリを行い、DLOCオラクルに対する最大でLのクエリを行うとそれぞれ仮定する。
この場合、Aが正しい解を返す確率θは、最大で
【式38】
0004288341.tif 000048
であり、ここで、この確率は、i1、i2、j1、j2および写像σで支配される。予想されるDLOCオラクルに対するクエリの数は、少なくとも
【式39】
0004288341.tif 000049
である。
【００３６】
まず、定理２の重要性について考察する。Tを、Aの総実行時間とする。T ≧ L+Rであるため、T ≧ LおよびT ≧ Rを得る。θが定数であると仮定する。定理2によって、【式40】を得る。
したがって、Tは、
【式41】
0004288341.tif 000050
である。これは、DLOGオラクルが許容される場合でもACTDHプロトコルを解読する確率論的多項式の時間アルゴリズムが存在しないことを暗黙的に示す。
ここで、DLOGオラクルが使用できないと仮定する。ACTDH問題を解くために群演算オラクルに対して予想されるクエリの数は、L=0にすることにより、定理2から得られる。成功確率θ
【式42】
0004288341.tif 000051
の上界、すなわち群演算オラクルに対して予想されるクエリの数は、θが定数の場合、Ω(√p)と推定される。
【００３７】
次に、上記の定理２を証明する。次のことは、以下の証明において重要であり、【参考文献９】で証明されている。
＜補助定理１(【参考文献９】)＞  全次数dの[Z]p[X1,X2,... ,Xk](pは素数)におけるゼロでない多項式Fを仮定すると、[Z]pの独立かつランダムに選択された要素x1, x2,... , xkに関してF(x1,x2,... ,xk) = 0である確率は、最大でd/pである。
【００３８】
＜定理２の証明＞  [Z]pに関する多項式によってジェネリック・アルゴリズムをシミュレートする。最初に、環[Z]p[X1,X2,Y1,Y2]における多項式の6つのペア (F1, H1) = (1,0)、(F2,H2) = (0,1)、(F3,H3) = (αX1,βX2,)、(F4,H4) = (γX2,δX1)、(F5,H5) = (αY1,βY2)、(F6, H6) = (γY2,δY1) がある。各ペアは、(群要素の)写像σ(1, 0)、σ(0, 1)、σ(αi1,βi2)、σ(γi2,δi1)、σ(αj1,βj2)、σ(γj2,δj1)にそれぞれ対応する。
【００３９】
I > k, lに関して、多項式Fi (X1,X2,Y1,Y2)とHi (X1,X2,Y1,Y2)を計算し、それにより多項式のペア(Fi, H1)は、(群要素の)写像のペアσ(Fi(i1,i2,j1,j2)、Hi(i1,i2,j1,j2)) に対応する。乗算オラクルが、ペア(Fk,Hk)と(Fl,Hl)に対応する入力により呼び出されるとき、多項式FiとHiを、Fi = Fk + FlおよびHi = Hk + Hlに設定することによって計算する。ここで、i > k, lである。
【００４０】
同様に、反転オラクルが、ペア(Fk, Hk)に対応する入力によって呼び出されるときは、Fi = -Fk とHi = -Hkを計算する。この場合は、i> k, lである。DLOGオラクルが、(Fk,Hk)と(Fl,Hl)に対応する入力で呼び出されるときは、sFk(i1,i2,j1,j2) = Fl(i1,i2,j1,j2) とsHk(i1,i2,j1,j2) = Hl(i1,i2,j1,j2)となるようなsが存在するときに、そのようなs (∈ [Z]p)を返す。このケースでは、多項式は生成されないが、i1,i2,j1,j2 が式Fk = Fl と sHk = Hl を満たすという情報が得られる。
【００４１】
ジェネリック・アルゴリズムは、計算のシミュレーションにおいて、i1, i2, j1, j2で満たされる自明でない式を求めるときだけ正しい解を返す可能性があると仮定する。
ジェネリック・アルゴリズムが、入力σ(Fk(i1,i2,j1,j2)、Hk(i1,i2,j1,j2))、およびσ(Fl(i1,i2,j1,j2)、Hl(i1,i2,j1,j2))に関してDLOGオラクルを呼び出すときは、3つのケースが考えられる。
【００４２】
最初に考えられるケースは、入力がイリーガルであり、すなわち第2の入力が、第1の入力の累乗でないケースである。
第２のケースは、入力がリーガルであるが、多項式Fk、Hk、F1、H1が、[Z]pに関する多項式として、条件FkHl = HkFl(mod p)を満たすケースである。
第３のケースは、入力がリーガルであり、FkHl ≠ HkFl (mod p)のケースである。
【００４３】
ここで、i1、i2、j1、j2に関する情報が、最後のケースでのみ得られることを証明する。第１のケースが生じる場合、DLOGオラクルは、エラーメッセージだけを返す。第2の入力が第1の入力の累乗でない場合以外は、i1、i2、j1、j2に関する情報を獲得する可能性はない。
次に、第２のケースを考察する。FkHl - FlHk = 0 (mod p)であると仮定する。最初に、Fk、Hk、Fl、Hlが、[Z]pに関する最大で次数1の多項式であるため、これらが、単元または既約多項式であることに注意されたい。多項式の環[Z]p[X1,X2,Y1,Y2]が、固有の因数分解領域であるため、u ∈ [Z]pのいくつかのuに関しては、uFk = FlとuHk = Hlが得られ、u ∈ [Z]pのいくつかのuに関しては、nFk = HkとuFl = Hlが得られる。
【００４４】
uFk = FlとuHk = Hlのケースにおいて、DLOGオラクルは、u ∈ [Z]pを、入力σ(Fk, Hk)およびσ(Fl, Hl)に返すが、方程式uFk = FlとuHk = Hlは、i1、i2、j1、j2だけでなく、x1,x2,y1,y2 ∈ [Z]pのx1、x2、y1、y2のすべてによっても満たされる。
次に、uFk = HkおよびuFl = Hlであると仮定する。FkとHkの定義によって、
【式43】
0004288341.tif 000052
と記述することができ、
【式44】
0004288341.tif 000053
は、c1,c2,c3,c4,c5,c6 ∈ [Z]pであった。uFk = Hkであるため、uc1 = c2と次の式を得る。
【式45】
0004288341.tif 000054
条件２であるため、行列
【式46】
0004288341.tif 000055
は、正則である。
【００４５】
したがって、c3=c4=c5=c6=0(mod p)であり、それにより、FkとHkは、両方とも定数である。したがって、FlとHlも定数である。よって、オラクルは、入力σ(Fk, Hk)およびσ(Fl, Hl)で呼び出し、その結果、FkHl = FlHkは、i1、i2、j1、j2に関する情報を何も提供しない。それゆえ、第3のケースの場合にのみi1、i2、j1、j2に関する情報を得ることができ、したがって、DLOGオラクル・クエリは、第3のケースで呼び出される場合に有意味であり、その他の場合は無意味である。
【００４６】
次に、Aが正しい解を返す確率の上界を求める。ジェネリック・アルゴリズムが正しい解を返すケースは3つある。
＜ケース１＞  少なくとも1つのDLOGオラクル・クエリが有意味である。
＜ケース２＞  すべてのDLOGオラクル・クエリが無意味であり、[Z]pに関する多項式として(Fk,Hk)≠(Fl,Hl)であるが、
【式47】
0004288341.tif 000056
で
【式48】
0004288341.tif 000057
であるような(Fk,Hk)と(Fl,Hl)が存在する。
＜ケース３＞  DLOGオラクル・クエリがすべて無意味であり、いくつかの(Fk, Hk)に関して
【式49】
0004288341.tif 000058
が得られる。
【００４７】
＜ケース１＞、＜ケース２＞、および＜ケース３＞のそれぞれにおける確率の上界を求める。
＜ケース1＞   DLOGオラクルへのクエリが有意味である確率は、
【式50】
0004288341.tif 000059
によるいくつかのkおよびlならびに[Z]pにおけるいくつかのsに関して、[Z]pにおいてランダムに選択したx1、x2、y1、y2に関して
【式51】
0004288341.tif 000060
と
【式52】
0004288341.tif 000061
が得られる確率によって制限される。その場合、確率は、[Z]pにおけるランダムに選択したx1、x2、y1、y2に関して以下の式が得られるため、
【式53】
0004288341.tif 000062
を得る。
【式54】
0004288341.tif 000063
【式55】
0004288341.tif 000064
[Z]pからランダムに選択されたx1、x2、y1、y2に関して、
【式56】
0004288341.tif 000065
を得る確率は、多項式FlHk - FkHlの全次数が2を超えず、多項式として
【式57】
0004288341.tif 000066
であるため、補助定理１によって2/pに制限される。したがって、少なくとも1つのDLOGオラクル・クエリが有意味である確率は、
【式58】
0004288341.tif 000067
によって制限される。
【００４８】
＜ケース２＞
【式59】
0004288341.tif 000068
であると仮定する。(i)Fk≠Fl (Hk ≠ HlかHk = Hlかは考慮しない)と(ii)Fk = FlとHk ≠ Hlの３つのケースがある。ケース(i)において、[Z]pにおいてランダムに選択されたx1、x2、y1、y2に関して
【式60】
0004288341.tif 000069
となる確率は、補助定理１により最大で1/pである。したがって、ケース(i)では、いくつかのk、lおよび[Z]pにおいてランダムに選択されたx1、x2、y1、y2に関して
【式61】
0004288341.tif 000070
と
【式62】
0004288341.tif 000071
である確率は、
【式63】
0004288341.tif 000072
である。
【００４９】
同様に、ケース(ii)の確率は、最大で
【式64】
0004288341.tif 000073
である。したがって、＜ケース２＞における確率は、最大で
【式65】
0004288341.tif 000074
である。
【００５０】
＜ケース３＞   補助定理１によって、 [Z]pにおいてランダムに選択されたx1、x2、y1、y2に関して、多項式Fk-αδX1Y1+βγX2y2およびHk-βδ(X1Y2+X2Y1)の全次数が2であるため、いくつかの(Fk, Hk)に関して
【式67】
0004288341.tif 000075
が得られる事象の確率の上界は、
【式66】
0004288341.tif 000076
である。条件(C1)により、αδ≠0、βγ≠0およびβδ≠0(mod p)であることに注意されたい。したがって、ジェネリック・アルゴリズムが正しい解を出力する確率は、最大で
【式68】
0004288341.tif 000077
である。
【００５１】
次に、DLOGに対するMDLOGのジェネリック帰着について考察する。以下の結果は、DLOGオラクルに対する多数のクエリなしにMDLOGを解くことができないことを示す。pが大きい素数の場合、群[Z]p x [Z]pに関して、MDLOGのジェネリック・アルゴリズムが、入出力(x1,x2)として(σ(1,0),σ(0,1),σ(x1,x2))を取得する。ここで、x1、x2は、0 ≦ x1 ＜ pと0 ≦ x2 ＜pの整数である。
【００５２】
＜定理３＞  Aを、GにおいてMDLOCを解くジェネリック・アルゴリズムとする。Aが、それぞれ、群演算オラクルに対する最大でRのクエリを行い、DLOCオラクルに対する最大でLのクエリを行うと仮定する。その場合、Aが正しい解を返す確率は、最大で
【式69】
0004288341.tif 000078
であり、ここで、i1、i2、j1、j2および写像σについての確率が取得される。DLOCオラクル・クエリの予想される数は、少なくとも
【式70】
0004288341.tif 000079
である。
【００５３】
上記で示した条件２は、きわめて重要である。αβγδが、平方剰余(mod p)の場合は、DLOGオラクルを使用することによるACTDHプロトコルに対する攻撃が存在する。
非固有パラメータによるACTDHプロトコルに対する攻撃:：
いくつかのuに関してαβγδ=u2(mod p)であると仮定する。この場合、行列
【式71】
0004288341.tif 000080
は、特異であり、したがって、次の式は、非自明な解である。
【式72】
0004288341.tif 000081
(s,t) = (c3,c4)が、非自明な解であると仮定する。群要素
【式73】
0004288341.tif 000082
が与えられ、それにより
【式74】
0004288341.tif 000083
を計算することができる。c3、c4の定義によって、
【式75】
0004288341.tif 000084
を得、
【式76】
0004288341.tif 000085
を得た。abuを計算し、次に、入力
【式77】
0004288341.tif 000086
およびabuによってDLOGオラクルを呼び出す。オラクルは、
【式78】
0004288341.tif 000087
を返す。次に、別の(c'3,c'4)によって類似のプロセスを行い、
【式79】
0004288341.tif 000088
を得る。この場合、i1とi2を得ることができる。同様に、攻撃者は、j1とj2を得ることができる。
【００５４】
ACTDHプロトコルは、以下のように公開鍵暗号方式を構成するために適用される。Gを直積C x Cと同形な群とし、ここで、Cは、素数次数pの巡回群である。G = <a,b>であると仮定する。G x Gに関するGL(2,[Z]p)の作用は、上述した。A(i1,i2)とA'(i1,i2)はそれぞれ、行列
【式80】
0004288341.tif 000089
および
【式81】
0004288341.tif 000090
であることを想起されたい。
【００５５】
キー生成について説述する。α、β、γ、δを条件１および条件２を満たすパラメータとする。x = (a, b) ∈ G x Gとする。第２通信端末が、i1,i2 ∈ [Z]pをランダムに選択する。次に、第２通信端末は、
【式82】
0004288341.tif 000091
を計算し、キー(x,y)を公表すればよい。
【００５６】
暗号化及び復号化は次のように行う。
暗号：第１通信端末が、j1,j2 ∈ [Z]pをランダムに選択する。次に、第１通信端末は、メッセージ
【式83】
0004288341.tif 000092
を、
【式84】
0004288341.tif 000093
として暗号化する。
【００５７】
復号化：暗号文
【式85】
0004288341.tif 000094
を取得し、第２通信端末は、群要素
【式86】
0004288341.tif 000095
とその逆数を計算する。次に、第２通信端末は、群要素
【式88】
0004288341.tif 000096
が
【式89】
0004288341.tif 000097
と一致するため、mを
【式87】
0004288341.tif 000098
として得ることができる。
【００５８】
Gを、次数素数pの2つの巡回群の直積と同形の群とする。[a, b]が、Gの生成元の集合であると仮定する。x = (a, b)を設定する。Aが、確率的多項式の時間アルゴリズムであると仮定し、入力
【式90】
0004288341.tif 000099
に関して、i1、i2、j1、j2がランダムに選択されかつM∈ GL(2,[Z]p)の場合、Aは、
【式91】
0004288341.tif 000100
の場合に1を出力し、そうでない場合は0を出力し、この確率は、十分に大きいnに関してなんらかの定数cに関して
【式92】
0004288341.tif 000101
よりも高い。この場合、Aは、DACTDHアルゴリズムと呼ばれる。DACTDHの仮定とは、DACTDHアルゴリズムが存在しないと仮定することである。DACTDH問題を解くためのDLOCオラクルの自明な利用がなく、またDLOGオラクルを使用してDDH問題が容易に解かれるため、DACTDHの仮定は、DHの仮定よりも弱いように見える。
【００５９】
＜定理４＞  提案された暗号方式は、DACTDHアルゴリズムが存在する場合、かつその場合のみにおいて、区別性の意味でセキュアでない。
この定理の証明は省略する。すなわち、提案された暗号方式は、DACTDHの処理が困難な場合、かつその場合のみ受動的な攻撃に対して意味論的にセキュアである。
【００６０】
【発明の効果】
本発明は、以上説明したように構成されているので、次に記載されるような効果を
奏する。
すなわち、現在までに知られている鍵交換スキーム（例えばDiffie-Hellman型）においては有限巡回群の離散対数問題を解くことの難しさにその安全性の基礎をおいているが、本発明において、有限巡回群だけではなく、それ以外の有限可換群におけるキーアグリーメントプロトコルと、それを用いた通信方法の構成を可能にする。
【００６１】
また、有限巡回群以外の有限可換群を利用することは、安全性を離散対数問題よりも難しいと考えられるアルゴリズム問題に帰着させることが出来る。ジェネリック・アルゴリズムのモデルの観点から離散対数問題よりも難しいと考えられるアルゴリズム問題に安全性の根拠を置くことで、安全性について離散対数問題ベースの鍵交換スキームよりも高いレベルの安全性を実現することが出来る。
【参考文献】
【参考文献１】
L.Babai and E.Szemer6di On the complexity of matrix group problems, IEEE Symp. Found. of Computer Scienece (1984) 229-240.
【参考文献２】
W.Difiie and M.E.Hellman, New directions in cryptography, IEEE Thansactions on InforTr~ation Theory, 22 (1976) 644-654.
【参考文献３】
T.EIGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Thansactions on Information Theory, 31 (1985) 469-472.
【参考文献４】
M.Fischlin, A note on security proofs in the generic model, Advances in Cryptology (Asiacrypt'OO) Lecture Notes in Computer Science, vol 1976 Springer-Verlag (2000) 458469.
【参考文献５】
U.M.Maurer and S.Wolf, Lower bounds on generic algorithms in groups, Ad-vances in Cryptology (Eurocrypt'98) Lecture Notes in Computer Science, vol 1403 Springer-Verlag (1998) 72-84.
【参考文献６】
V#1.Nechaev, Complexity of a deternxinate algorithm for the discrete logarithm, Math. Notes, 55 (1994) 165-172.
【参考文献７】
C.P.Schnorr, Small generic hardcore subsets for the discrete logarithm: Short secret DLekeys, Infor. Proc. Letters, 79 (2001) 93-98.
【参考文献８】
C.P.Schnorr and M.Jakobsson, Security of signed EIGamal encryption, Advances in Cryptology (Asiacrypt'OO) Lecture Notes in Computer Science, vol 1976 Springer-Verlag (20CO) 73-89.
【参考文献９】
J.T.Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27(4) (1980) 701-717.
【参考文献１０】
V.Shoup, Lower bounds for discrete logarithms and related problems, Advances in Cryptology (Eurocrypt'97) Lecture Notes in Conrputer Science, vol 1233 Springer-Verlag (1997) 256-266.