JP4288341B2 - Communication method using key agreement protocol - Google Patents

Description

を計算し、それを第１通信端末の送信手段が、第２通信端末に送るステップ、
（３） 第２通信端末の演算手段が、整数j₁、j₂をランダムに選択するステップ、
（４）同じく第２通信端末の演算手段が、
【式２３】

を計算し、それを第２通信端末の送信手段が、第１通信端末に送るステップ、
（５） 第１通信端末の演算手段が、
【式２５】

と
【式２６】

を計算して乗ずることにより
【式２４】

のＫを得るステップ、
（６） 第２通信端末の演算手段が、
【式２８】

を計算しＫを得るステップ、
以上の各ステップを含み該Ｋを第１通信端末と第２通信端末との共通鍵とする。
【０００９】
【発明の実施の形態】
以下に、本発明における実施形態として、キーアグリーメントプロトコルの詳細を説述する。
まず、本発明の概要を述べる。ジェネリック・アルゴリズム(【参考文献６】、【参考文献１０】、【参考文献５】、【参考文献４】、【参考文献８】、【参考文献７】)は、群演算オラクルや他のいくつかの特別なオラクルを呼び出すことによって解を求める確率的アルゴリズムの一般的モデルである。
【００１０】
そのようなモデルにおいて、群は、ブラック・ボックス群（【参考文献１】）として与えられ、各群要素は、同じ長さの２進文字列によって表される。代表的なジェネリック・アルゴリズムは、Baby-Step-Giant-StepとPohlig-Hellmanである。
群演算、乗算および逆数の取得は、ジェネリック・アルゴリズム・モデル内のオラクルを呼び出すことによって行われる。解は、所定の条件を満たす特定の群要素、または離散対数のような情報でよい。離散対数問題(DLOG)、Diffie-Hellman問題(DH)(【参考文献１０】、【参考文献５】)および暗号システム(【参考文献４】、【参考文献７】、【参考文献８】)を解析するために、ジェネリック・アルゴリズム・モデルが使用される。
【００１１】
本発明では、ジェネリック・アルゴリズムが、オラクル・クエリの数が制限された[Z]_px[Z]_pと同形のブラック・ボックス群について正しい解を求める確率を推定する。ジェネリック・アルゴリズム・モデルにおける乗法的離散対数問題(MDLOG)を解くために、群演算に対する
【式1】

クエリと離散対数オラクル(および、提案されたキー・アグリーメント・プロトコルの基になるACTDH問題と呼ばれるアルゴリズム問題の【式1】クエリ)が必要
であることを示す。
【００１２】
次に、本発明におけるキーアグリーメントプロトコルについて詳述する。
Sを群とし、Xを非空の集合とする。Sは、必ずしも交換可能でなくてもよい。S内のsとtおよびX内のxに関してx^(st)=(x^s)^tおよびx¹=xを満たす写像σ:X x S → X(σによる(x,s) ∈ X x Sの像は、x³で示される)の場合に、SがXに作用する。
群作用は、暗号学では一般的であるが、群作用に関して、最も一般的な暗号システムのメカニズムであるDiffie-HellmanとRSAについて説明する。
【００１３】
（例１） pを素数とする。p-1が素数qで割れると仮定する。|g|=qになるような要素a∈[Z]^* _pをとる。この場合、σ(g,s) = g^sで与えられるσ:<g> x [Z]^* _p <g>は、巡回群<g>への[Z]*_pの作用である。
DLOGは、所与のgとσ(g,s)=g^sに関してsを求める問題と見なされる。この作用は、Diffie-Hellmanプロトコル（【参考文献２】）とElGamal暗号（【参考文献３】）において使用される。
【００１４】
（例２） p,qを素数とする。n = pqとする。RSA暗号システムは、σ(m, e) = m^eによって与えられる
【式2】

として定義される作用を採用する。RSAは、e乗根を求める計算処理の困難性、すなわち、所与のeに関するmとσ(m,e) = m^eを求める問題に基づく。
【００１５】
ここで、一般的な方法を示す。
群Sが集合Xに作用し、この作用が常に効率よく計算できると仮定する。fを、Xに関して効率的に計算可能な関数とする。Sが、必ずしも交換可能である必要はないことに注意されたい。S_oを、以下の条件を満たすSの部分集合とする。
仮定１：すべてのs, t ∈ S_oに関してs(t') = t(s')となるように効率よく計算可能な関数':S_o→Sがある。
仮定２：x^sとx^tが与えられたときにf(x^st')を計算する効率的なアルゴリズムがない。
Sが交換可能なとき、仮定１が機械的に真になることに注意する。これは、恒等写像を’としてとることができるためである。しかしながら、そのような関数は、一般に必ずしも存在するとは限らない。Diffie-Hellmanの仮定は、仮定２の特殊な場合であり、ここで、Sは[Z]_pであり、fは恒等写像である。
【００１７】
キー・アグリーメント・プロトコルの一般的な方式は次の通りである。
初期設定: x∈Xとなるxを選択し、それを公表する。
ステップ１：第１通信端末が、s∈S_oとなるsをランダムに選択する。第１通信端末は、x^sを計算し、それを第２通信端末に送る。
ステップ２：第２通信端末は、t∈S_oとなるtをランダムに選択する。第２通信端末は、x^tを計算し、それを第１通信端末に送る。
ステップ３：第１通信端末は、(x^t)^s' とf((x^t)^s')を計算する。第２通信端末は、(x^s)^t'とf((x^s)^t')^t'を計算する。この場合、
【式3】

は、第１通信端末と第２通信端末によって共有される共通秘密キーである。仮定１により、(x^t)^s' = (x^s)^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> = [1_G]であることを暗黙的に示し、ここで、1_Gは、Gの恒等元を示す。
【００１９】
Gのすべての要素は、i,j ∈ [Z]_pの場合に、aⁱbⁱとして一意に記述される。
【式4】

で
【式5】

の場合、
【式6】

へのGL(2,[Z]_p) の作用を定義する。x^Aが、次のように効率よく計算可能である。
【００２０】
Gの要素a^i1j1およびa^i2j2と行列Aが与えられたとして、
【式7】

を計算する。GL(2,[Z]_p)が、G x Gにこのように作用することはすぐに分かるが、以下のようにより分かりやすい説明も可能である。
要素
【式8】

と行列
【式9】

を識別する場合、x^Aは、次のような行列式で識別される。
【式10】

【００２１】
行列乗算は結合的であるため、GL(2,[Z]_p)が、G x Gに作用する。次に、[Z]*_pにおけるパラメータα、β、γ、δを、αβγδが平方非剰余になるようにランダムに選択し、次にS_oを、形
【式11】

の一組の行列になるように定義する。ここで、(i₁,i₂) ≠ (0,0)の場合、i₁,i₂ ∈ [Z]_pである。
【式12】

に関して、A'を行列
【式13】

になるように定義する。αβγδが平方非剰余であるため、A,A' ∈ GL(2,[Z]_p) である。
【式14】

でありかつ
【式15】

である場合は、A,B ∈ S_oであり、次の式となる。
【式16】

【００２２】
したがって、上記の仮定１は、成り立つ。以降では、行列
【式17】

と
【式18】

をそれぞれ、A(i₁,i₂)とA'(i₁,i₂)で表わす。したがって、すべてのi₁,i₂,j₁,j₂∈[Z]_pに関して、次の式が得られる。
【式19】

π₁ : G x G → Gを第一の軸に対する射影、すなわち
【式20】

とする。
【式21】

であることに注意する。
【００２３】
ACTDHプロトコル: x = (a, b)とする。
ステップ１：第１通信端末の演算手段が、整数i₁、i₂をランダムに選択する。同演算手段は
【式22】

を計算し、それを送信手段によって第２通信端末に送る。
ステップ２：第２通信端末の演算手段が、整数j₁、j₂をランダムに選択する。同演算手段は、
【式23】

を計算し、それを送信手段によって第１通信端末に送る。
【００２４】
ステップ３：第１通信端末の演算手段が、第２通信端末から送られた式２３の計算結果を用いて、
【式２５】

と
【式２６】

を計算して乗ずることによって
【式２４】

を得る。なお、式２１に示したように、
【式２７】

である。
ステップ４：第２通信端末の演算手段が、同様に、第１通信端末から送られた式２２の計算結果を用いて、
【式９３】

と
【式９４】

を計算して乗ずることにより
【式２４】

を計算する。なお、式２１に示したように、
【式２８】

である。この場合、Kが第１通信端末と第２通信端末の共通鍵となる。
【００２５】
ここで、一例として、素数次数の２つの巡回群の直積の例を示す。qとrを、p|q - 1でかつp| r - 1となるような大きい素数とする。
nをqrとする。g₁を、mod qにおける1のp乗根とし、g₂を、mod rにおける1のp乗根とする。いくつかのc₁ ∈ [Z]*_pおよびc₂ ∈ [Z]*_pについて、a = g₁ (mod q)、a = g^* ₂ (mod r)、b = g^* ₁(mod q)、b = g₂(mod r)となるように、a ∈ Z_nとなるaおよびb ∈ Z_nとなるbを選択する。c₁c₂ ≠ 1 mod pの場合にZ*_n =<a> x <b>であることは明らかである。
【００２６】
次に、本発明のプロトコルのセキュリティを、Diffie-Hellmanプロトコルと比較する。
ACTDHプロトコルの解読は、以下の問題を解くことと等価である。Gが、有限のアーベル群であり、a,b ∈Gであると仮定する。パラメータα、β、γ、δはそれぞれ、|a|および|b|と互いに素である。aとbに関するGにおける作用Diffie-Hellman問題(ACTDH問題)の定義は、次の通りである。
【式29】

【式30】

ここで、i₁、i₂、j₁、j₂は、無作為かつ独立に選択された整数である。
【００２７】
以下の定理とその証明により、パラメータを慎重に選択すれば、ACTDHプロトコルが、少なくともDHプロトコルと同程度のセキュアであることを保証する。
＜定理１＞ α、β、γ、δを整数とする。これらはそれぞれ、|G|と互いに素であると仮定する。Gのすべてのa、bについてアーベル群GにおけるACTDH問題(パラメータα、β、γ、δ)を解く効率のよいアルゴリズムが存在する場合は、GのすべてのaについてGにおけるDH問題を解く効率のよいアルゴリズムが存在する。
【００２８】
＜証明＞ すべてのaとbについてACTDH問題を解く効率のよいアルゴリズムがあると仮定する。DH問題を解く効率のよいアルゴリズム、すなわち入力aⁱ¹およびa^j1に関してa^i1j1を計算するアルゴリズムを作成する。ここで、aは、Gの要素である。b=1(Gの単位元)とする。|G|が|a|で割れるため、α、β、γ、δは、|a|と互いに素でなければならない。上の仮定により、aとbに関してACTDH問題を解く効率のよいアルゴリズムが得られる。i₂=j₂=0とする。aとbに関してACTDH問題を解くアルゴリズムに
【式31】

と
【式32】

を入力する。こうして、
【式33】

が得られる。aⁱ¹とa^j1が与えられ、αが公の情報であるため、(aⁱ¹)αと(a^j1)αを計算することができることが分かる。αとδが両方とも、|a|と互いに素であるため、(aαδ)^m = aとなるような整数mを求めることができる。この場合、
【式34】

であり、したがって、DH問題が効率よく解かれる。
【００２９】
Gを有限のアーベル群とし、aとbをGにおける要素とする。Hを、aとbによって生成されたGの小群になるように設定する。群H = <a, b>における複数の離散対数問題(略してMDLOG)は、次のように定義されたアルゴリズム的な問題である。
INPUT: Hの要素g。
OUTPUT: g = a^xb^yになるような負でない整数(x,y)のペア(x, y)。
Hが、aとbによって生成されるため、g = a^xb^yを満たす負でない整数のペア(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に関してg_m = gとg_i ∈ Bまたはg_i=g^-1 _jまたはg_i = g_jg_kになるようにGの要素の数列g₁,g₂,... ,g_mを列挙する。
ある段において、アルゴリズムは、同一の2進文字列を表す要素g_iおよびg_j(i≠j)を求める。次に、g_iとg_jに関する情報から得られた一次方程式を解くことによって、隠された情報を得ることができる。
【００３３】
σを、[Z]_pから大きさpの2進文字列の集合Sへのランダムな写像とする。ジェネリック・アルゴリズムは、x,y ∈ [Z]_pに関してadd(σ(x),σ(y)) = σ(x+y) と inv(σ(x))によって定義されたaddとinvを、計算上の犠牲なしに計算する群演算オラクルを呼び出すことができる。add(σ(x),σ(y)) = σ(x + y)が、乗算g^xg^y = g^x+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),σ(αi₁,βi₂),σ(γi₂,δi₁),σ(αj₁j1,βj₂),σ(γj₂,δj₁))を取得し、群演算オラクルを呼び出すことによって計算し、次に
【式35】

を出力する。入力が、群要素
【式36】

に対応し、出力が、群要素
【式37】

に対応する。群演算オラクルの他に、離散対数オラクルを呼び出すジェネリック・アルゴリズムを可能にする。[Z]_p x [Z]_pの離散対数(DLOC)オラクルは、入力として(σ(i₁,i₂), σ(j₁,j₂)) を取得し、次に、ni₁ = j₁(mod p)およびni₂ = j₂(mod p)が、そのようなnが存在する場合に、計算上の犠牲なしに成り立つように、整数nを出力する。
【００３５】
上の式を満たすnが存在しない場合は、そのような入力はイリーガルと呼ばれる。オラクルがイリーガル入力の対象でなく、かつジェネリック・アルゴリズムが進行すると仮定する。
＜定理２＞ Aを、群[Z]_p x [Z]_pにおけるACTDH問題を解くジェネリック・アルゴリズムとする。ここでpは素数である。パラメータα、β、γ、δは、上記条件１および２を満たす。Aが、群演算オラクルに対する最大でRのクエリを行い、DLOCオラクルに対する最大でLのクエリを行うとそれぞれ仮定する。
この場合、Aが正しい解を返す確率θは、最大で
【式38】

であり、ここで、この確率は、i₁、i₂、j₁、j₂および写像σで支配される。予想されるDLOCオラクルに対するクエリの数は、少なくとも
【式39】

である。
【００３６】
まず、定理２の重要性について考察する。Tを、Aの総実行時間とする。T ≧ L+Rであるため、T ≧ LおよびT ≧ Rを得る。θが定数であると仮定する。定理2によって、【式40】を得る。
したがって、Tは、
【式41】

である。これは、DLOGオラクルが許容される場合でもACTDHプロトコルを解読する確率論的多項式の時間アルゴリズムが存在しないことを暗黙的に示す。
ここで、DLOGオラクルが使用できないと仮定する。ACTDH問題を解くために群演算オラクルに対して予想されるクエリの数は、L=0にすることにより、定理2から得られる。成功確率θ
【式42】

の上界、すなわち群演算オラクルに対して予想されるクエリの数は、θが定数の場合、Ω(√p)と推定される。
【００３７】
次に、上記の定理２を証明する。次のことは、以下の証明において重要であり、【参考文献９】で証明されている。
＜補助定理１(【参考文献９】)＞ 全次数dの[Z]_p[X₁,X₂,... ,X_k](pは素数)におけるゼロでない多項式Fを仮定すると、[Z]_pの独立かつランダムに選択された要素x₁, x₂,... , x_kに関してF(x_1,x₂,... ,x_k) = 0である確率は、最大でd/pである。
【００３８】
＜定理２の証明＞ [Z]_pに関する多項式によってジェネリック・アルゴリズムをシミュレートする。最初に、環[Z]_p[X₁,X₂,Y₁,Y₂]における多項式の6つのペア (F₁, H₁) = (1,0)、(F₂,H₂) = (0,1)、(F₃,H₃) = (αX₁,βX₂,)、(F₄,H₄) = (γX₂,δX₁)、(F₅,H₅) = (αY₁,βY₂)、(F₆, H₆) = (γY₂,δY₁) がある。各ペアは、(群要素の)写像σ(1, 0)、σ(0, 1)、σ(αi₁,βi₂)、σ(γi₂,δi₁)、σ(αj₁,βj₂)、σ(γj₂,δj₁)にそれぞれ対応する。
【００３９】
I > k, lに関して、多項式Fi (X₁,X₂,Y₁,Y₂)とHi (X₁,X₂,Y₁,Y₂)を計算し、それにより多項式のペア(F_i, H₁)は、(群要素の)写像のペアσ(Fi(i₁,i₂,j₁,j₂)、Hi(i₁,i₂,j₁,j₂)) に対応する。乗算オラクルが、ペア(F_k,H_k)と(F_l,H_l)に対応する入力により呼び出されるとき、多項式F_iとH_iを、F_i = F_k + F_lおよびH_i = H_k + H_lに設定することによって計算する。ここで、i > k, lである。
【００４０】
同様に、反転オラクルが、ペア(F_k, H_k)に対応する入力によって呼び出されるときは、F_i = -F_k とH_i = -H_kを計算する。この場合は、i> k, lである。DLOGオラクルが、(F_k,H_k)と(F_l,H_l)に対応する入力で呼び出されるときは、_sF_k(i₁,i₂,j₁,j₂) = F_l(i₁,i₂,j₁,j₂) と_sH_k(i₁,i₂,j₁,j₂) = H_l(i₁,i₂,j₁,j₂)となるようなsが存在するときに、そのようなs (∈ [Z]_p)を返す。このケースでは、多項式は生成されないが、i₁,i₂,j₁,j₂ が式F_k = F_l と sH_k = H_l を満たすという情報が得られる。
【００４１】
ジェネリック・アルゴリズムは、計算のシミュレーションにおいて、i_1, i_2, j_1, j₂で満たされる自明でない式を求めるときだけ正しい解を返す可能性があると仮定する。
ジェネリック・アルゴリズムが、入力σ(F_k(i₁,i₂,j₁,j₂)、H_k(i₁,i₂,j₁,j₂))、およびσ(F_l(i₁,i₂,j₁,j₂)、H_l(i₁,i₂,j₁,j₂))に関してDLOGオラクルを呼び出すときは、3つのケースが考えられる。
【００４２】
最初に考えられるケースは、入力がイリーガルであり、すなわち第2の入力が、第1の入力の累乗でないケースである。
第２のケースは、入力がリーガルであるが、多項式F_k、H_k、F₁、H₁が、[Z]_pに関する多項式として、条件F_kH_l = H_kF_l(mod p)を満たすケースである。
第３のケースは、入力がリーガルであり、F_kH_l ≠ H_kF_l (mod p)のケースである。
【００４３】
ここで、i₁、i₂、j₁、j₂に関する情報が、最後のケースでのみ得られることを証明する。第１のケースが生じる場合、DLOGオラクルは、エラーメッセージだけを返す。第2の入力が第1の入力の累乗でない場合以外は、i₁、i₂、j₁、j₂に関する情報を獲得する可能性はない。
次に、第２のケースを考察する。F_kH_l - F_lH_k = 0 (mod p)であると仮定する。最初に、F_k、H_k、F_l、H_lが、[Z]_pに関する最大で次数1の多項式であるため、これらが、単元または既約多項式であることに注意されたい。多項式の環[Z]_p[X₁,X₂,Y₁,Y₂]が、固有の因数分解領域であるため、u ∈ [Z]_pのいくつかのuに関しては、_uF_k = F_lと_uH_k = H_lが得られ、u ∈ [Z]_pのいくつかのuに関しては、_nF_k = H_kと_uF_l = H_lが得られる。
【００４４】
_uF_k = F_lと_uH_k = H_lのケースにおいて、DLOGオラクルは、u ∈ [Z]_pを、入力σ(F_k, H_k)およびσ(F_l, H_l)に返すが、方程式_uF_k = F_lと_uH_k = H_lは、i₁、i₂、j₁、j₂だけでなく、x₁,x₂,y₁,y₂ ∈ [Z]_pのx₁、x₂、y₁、y₂のすべてによっても満たされる。
次に、_uF_k = H_kおよび_uF_l = H_lであると仮定する。F_kとH_kの定義によって、
【式43】

と記述することができ、
【式44】

は、c₁,c₂,c₃,c₄,c₅,c₆ ∈ [Z]_pであった。_uF_k = H_kであるため、uc₁ = c₂と次の式を得る。
【式45】

条件２であるため、行列
【式46】

は、正則である。
【００４５】
したがって、c₃=c₄=c₅=c₆=0(mod p)であり、それにより、F_kとH_kは、両方とも定数である。したがって、F_lとH_lも定数である。よって、オラクルは、入力σ(F_k, H_k)およびσ(F_l, H_l)で呼び出し、その結果、F_kH_l = F_lH_kは、i₁、i₂、j₁、j₂に関する情報を何も提供しない。それゆえ、第3のケースの場合にのみi₁、i₂、j₁、j₂に関する情報を得ることができ、したがって、DLOGオラクル・クエリは、第3のケースで呼び出される場合に有意味であり、その他の場合は無意味である。
【００４６】
次に、Aが正しい解を返す確率の上界を求める。ジェネリック・アルゴリズムが正しい解を返すケースは3つある。
＜ケース１＞ 少なくとも1つのDLOGオラクル・クエリが有意味である。
＜ケース２＞ すべてのDLOGオラクル・クエリが無意味であり、[Z]_pに関する多項式として(F_k,H_k)≠(F_l,H_l)であるが、
【式47】

で
【式48】

であるような(F_k,H_k)と(F_l,H_l)が存在する。
＜ケース３＞ DLOGオラクル・クエリがすべて無意味であり、いくつかの(F_k, H_k)に関して
【式49】

が得られる。
【００４７】
＜ケース１＞、＜ケース２＞、および＜ケース３＞のそれぞれにおける確率の上界を求める。
＜ケース1＞ DLOGオラクルへのクエリが有意味である確率は、
【式50】

によるいくつかのkおよびlならびに[Z]_pにおけるいくつかのsに関して、[Z]_pにおいてランダムに選択したx₁、x₂、y₁、y₂に関して
【式51】

と
【式52】

が得られる確率によって制限される。その場合、確率は、[Z]_pにおけるランダムに選択したx₁、x₂、y₁、y₂に関して以下の式が得られるため、
【式53】

を得る。
【式54】

【式55】

[Z]_pからランダムに選択されたx₁、x₂、y₁、y₂に関して、
【式56】

を得る確率は、多項式F_lH_k - F_kH_lの全次数が2を超えず、多項式として
【式57】

であるため、補助定理１によって2/pに制限される。したがって、少なくとも1つのDLOGオラクル・クエリが有意味である確率は、
【式58】

によって制限される。
【００４８】
＜ケース２＞
【式59】

であると仮定する。(i)F_k≠F_l (H_k ≠ H_lかH_k = H_lかは考慮しない)と(ii)F_k = F_lとH_k ≠ H_lの３つのケースがある。ケース(i)において、[Z]_pにおいてランダムに選択されたx₁、x₂、y₁、y₂に関して
【式60】

となる確率は、補助定理１により最大で1/pである。したがって、ケース(i)では、いくつかのk、lおよび[Z]_pにおいてランダムに選択されたx₁、x₂、y₁、y₂に関して
【式61】

と
【式62】

である確率は、
【式63】

である。
【００４９】
同様に、ケース(ii)の確率は、最大で
【式64】

である。したがって、＜ケース２＞における確率は、最大で
【式65】

である。
【００５０】
＜ケース３＞ 補助定理１によって、 [Z]_pにおいてランダムに選択されたx₁、x₂、y₁、y₂に関して、多項式F_k-αδX₁Y₁+βγX₂y₂およびH_k-βδ(X₁Y₂+X₂Y₁)の全次数が2であるため、いくつかの(F_k, H_k)に関して
【式67】

が得られる事象の確率の上界は、
【式66】

である。条件(C1)により、αδ≠0、βγ≠0およびβδ≠0(mod p)であることに注意されたい。したがって、ジェネリック・アルゴリズムが正しい解を出力する確率は、最大で
【式68】

である。
【００５１】
次に、DLOGに対するMDLOGのジェネリック帰着について考察する。以下の結果は、DLOGオラクルに対する多数のクエリなしにMDLOGを解くことができないことを示す。pが大きい素数の場合、群[Z]_p x [Z]_pに関して、MDLOGのジェネリック・アルゴリズムが、入出力(x₁,x₂)として(σ(1,0),σ(0,1),σ(x₁,x₂))を取得する。ここで、x₁、x₂は、0 ≦ x₁ ＜ pと0 ≦ x₂ ＜pの整数である。
【００５２】
＜定理３＞ Aを、GにおいてMDLOCを解くジェネリック・アルゴリズムとする。Aが、それぞれ、群演算オラクルに対する最大でRのクエリを行い、DLOCオラクルに対する最大でLのクエリを行うと仮定する。その場合、Aが正しい解を返す確率は、最大で
【式69】

であり、ここで、i₁、i₂、j₁、j₂および写像σについての確率が取得される。DLOCオラクル・クエリの予想される数は、少なくとも
【式70】

である。
【００５３】
上記で示した条件２は、きわめて重要である。αβγδが、平方剰余(mod p)の場合は、DLOGオラクルを使用することによるACTDHプロトコルに対する攻撃が存在する。
非固有パラメータによるACTDHプロトコルに対する攻撃:：
いくつかのuに関してαβγδ=u²(mod p)であると仮定する。この場合、行列
【式71】

は、特異であり、したがって、次の式は、非自明な解である。
【式72】

(s,t) = (c₃,c₄)が、非自明な解であると仮定する。群要素
【式73】

が与えられ、それにより
【式74】

を計算することができる。c₃、c₄の定義によって、
【式75】

を得、
【式76】

を得た。ab^uを計算し、次に、入力
【式77】

およびab^uによってDLOGオラクルを呼び出す。オラクルは、
【式78】

を返す。次に、別の(c'₃,c'₄)によって類似のプロセスを行い、
【式79】

を得る。この場合、i₁とi₂を得ることができる。同様に、攻撃者は、j₁とj₂を得ることができる。
【００５４】
ACTDHプロトコルは、以下のように公開鍵暗号方式を構成するために適用される。Gを直積C x Cと同形な群とし、ここで、Cは、素数次数pの巡回群である。G = <a,b>であると仮定する。G x Gに関するGL(2,[Z]_p)の作用は、上述した。A(i₁,i₂)とA'(i₁,i₂)はそれぞれ、行列
【式80】

および
【式81】

であることを想起されたい。
【００５５】
キー生成について説述する。α、β、γ、δを条件１および条件２を満たすパラメータとする。x = (a, b) ∈ G x Gとする。第２通信端末が、i₁,i₂ ∈ [Z]_pをランダムに選択する。次に、第２通信端末は、
【式82】

を計算し、キー(x,y)を公表すればよい。
【００５６】
暗号化及び復号化は次のように行う。
暗号：第１通信端末が、j₁,j₂ ∈ [Z]_pをランダムに選択する。次に、第１通信端末は、メッセージ
【式83】

を、
【式84】

として暗号化する。
【００５７】
復号化：暗号文
【式85】

を取得し、第２通信端末は、群要素
【式86】

とその逆数を計算する。次に、第２通信端末は、群要素
【式88】

が
【式89】

と一致するため、mを
【式87】

として得ることができる。
【００５８】
Gを、次数素数pの2つの巡回群の直積と同形の群とする。[a, b]が、Gの生成元の集合であると仮定する。x = (a, b)を設定する。Aが、確率的多項式の時間アルゴリズムであると仮定し、入力
【式90】

に関して、i₁、i₂、j₁、j₂がランダムに選択されかつM∈ GL(2,[Z]_p)の場合、Aは、
【式91】

の場合に1を出力し、そうでない場合は0を出力し、この確率は、十分に大きいnに関してなんらかの定数cに関して
【式92】

よりも高い。この場合、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.[0001]
BACKGROUND OF THE INVENTION
  The present invention relates to an encryption technique for data communication, and particularly proposes a key agreement protocol using an algorithm that has not been introduced conventionally.
[0002]
[Prior art]
  In recent years, with rapid progress of data communication technologies such as the Internet, opportunities to use information communication in various daily situations are increasing. Information leakage due to interception of data communications is a social problem, and in particular, leakage of privacy information from government agencies, and in the fields of trading and finance, there is a risk that enormous damage may occur due to misuse of data There is.
  Therefore, there is a strong demand for technology that enhances the confidentiality of information, and a variety of information encryption technologies have been developed. However, high-level encryption technology is gradually deciphered by attackers and is constantly exposed to information leakage.
[0003]
  As a method of ensuring the safety of data communication, there is a known method for ensuring the safety due to the difficulty of difficult algorithm problems, with the difficulty of computational processing, and attackers also require extremely high abilities. Therefore, it is considered an effective means.
  For example, in the key exchange schemes known so far (for example, Diffie-Hellman type), the security is based on the difficulty of solving the discrete logarithm problem of a finite cyclic group.
[0004]
  At present, it is considered that a high level of security is assured by the above key exchange scheme. However, as described above, in view of the reality that these technologies are just like attackers, various methods are required. It is a situation.
  However, in the conventional technology, only the Diffie-Hellman type scheme is actually considered in the key exchange scheme, and the key exchange scheme using a group other than the finite cyclic group is not known.
[0005]
  It is possible to use finite commutative groups, and although they have been proposed, they are essentially Diffie-Hellman type schemes that use finite cyclic groups, or variations thereof, and are essentially finite. No method is provided using a commutative group.
[0006]
[Problems to be solved by the invention]
  The present invention is intended to solve the above-described problems of the prior art, and an object of the present invention is to provide a highly secure protocol based on a new algorithm problem for a key agreement protocol used in data communication. It is.
[0007]
[Means for Solving the Problems]
  In order to solve the above problems, the present invention uses the following means.
  That is, the present inventionUsing a finite commutative group other than the finite cyclic group, the safety of the algorithm problem, which is more difficult than the discrete logarithm problem, is based on the safety, and the effect of the general linear group on the direct product of the two cyclic groups A communication method for performing communication between a first communication terminal and a second communication terminal using a key agreement protocol in which the difficulty and safety of a generalized discrete logarithm problem are computationally equivalent. is there.
[0008]
  In particular,Includes the following steps:
  First, G is defined as a group having the same shape as CxC (C is a cyclic group whose degree is a prime p), and a and b generate G. Parameters α, β, γ, δmodulo pRandom selection is made so that αβγδ becomes a non-square residue. Under these conditions,
(1) First communication terminalComputing meansIs an integer i₁, I₂Randomly selecting a step,
(2)Similarly, the computing means of the first communication terminal is
[Formula 22]

Calculate it andThe transmission means of the first communication terminal isSending to the second communication terminal;
(3) Second communication terminalThe computing means of, Integer j₁, J₂Randomly selecting a step,
(4)Similarly, the computing means of the second communication terminal is
[Formula 23]

Calculate it andThe transmission means of the second communication terminal isSending to the first communication terminal;
(5) First communication terminalComputing meansBut,
[Formula 25]

When
[Formula 26]

By calculating and multiplying
[Formula 24]

Obtaining K of
(6) Second communication terminalComputing meansBut,
[Formula 28]

Calculating K and obtaining K,
Including the above steps, K is used as a common key for the first communication terminal and the second communication terminal.
[0009]
DETAILED DESCRIPTION OF THE INVENTION
  Details of the key agreement protocol will be described below as an embodiment of the present invention.
First, the outline of the present invention will be described. Generic algorithms ([Ref 6], [Ref 10], [Ref 5], [Ref 4], [Ref 8], [Ref 7]) are group operation oracles and some other Is a general model of a probabilistic algorithm for finding a solution by calling a special oracle.
[0010]
In such a model, groups are given as black box groups (Reference 1), and each group element is represented by a binary string of the same length. Typical generic algorithms are Baby-Step-Giant-Step and Pohlig-Hellman.
  Group operations, multiplication, and reciprocal acquisition are performed by calling an oracle in the generic algorithm model. The solution may be a specific group element that satisfies a predetermined condition, or information such as a discrete logarithm. Discrete logarithm problem (DLOG), Diffie-Hellman problem (DH) ([10], [5]) and cryptosystem ([4], [7], [8]) A generic algorithm model is used for analysis.
[0011]
  In the present invention, the generic algorithm has a limited number of Oracle queries [Z]_px [Z]_pEstimate the probability of finding a correct solution for a group of black boxes of the same shape as. To solve the multiplicative discrete logarithm problem (MDLOG) in a generic algorithm model,
[Formula 1]

Requires a query and a discrete log oracle (and an [EQUATION 1] query for an algorithm problem called the ACTDH problem that underlies the proposed key agreement protocol)
Indicates that
[0012]
  Next, the key agreement protocol in the present invention will be described in detail.
  Let S be a group and let X be a non-empty set. S need not be interchangeable. X with respect to s and t in S and x in X^(st)= (x^s)^tAnd x¹A map satisfying = x σ: X x S → X (The image of (x, s) ∈ X x S by σ is x^ThreeIn this case, S acts on X.
  Although group actions are common in cryptography, we discuss Diffie-Hellman and RSA, which are the most common cryptographic system mechanisms for group actions.
[0013]
(Example 1) Let p be a prime number. Suppose p-1 is broken by a prime q. element a∈ [Z] such that | g | = q^* _pTake. In this case, σ (g, s) = g^sΣ: <g> x [Z] given by^* _p <g> is [Z] * for the traveling group <g>_pIt is the action of.
  DLOG is given g and σ (g, s) = g^sIs regarded as a problem seeking s. This action is used in the Diffie-Hellman protocol ([reference 2]) and the ElGamal cipher ([reference 3]).
[0014]
(Example 2) p and q are prime numbers. Let n = pq. RSA cryptosystem is σ (m, e) = m^eGiven by
[Formula 2]

Adopt the action defined as RSA is the computational difficulty of finding the e-th root, ie, m and σ (m, e) = m for a given e^eBased on the problem of seeking.
[0015]
  Here, a general method is shown.
  Suppose that the group S acts on the set X and that this action can always be calculated efficiently. Let f be a function that can be computed efficiently with respect to X. Note that S need not necessarily be interchangeable. S_oIs a subset of S that satisfies the following conditions:
Assumption 1: All s, t ∈ S_oA function ': S that can be calculated efficiently so that s (t') = t (s')_o→ There is S.
Assumption 2: x^sAnd x^tF (x^{st '}There is no efficient algorithm to calculate).
  Note that hypothesis 1 is mechanically true when S is interchangeable. This is because the identity map can be taken as'. However, such functions generally do not always exist. Diffie-Hellman's assumption is a special case of assumption 2, where S is [Z]_pAnd f is an identity map.
[0017]
  The general scheme of the key agreement protocol is as follows.
Initial setting: Select x such that x∈X and publish it.
Step 1: The first communication terminal is s∈S_oChoose s at random. The first communication terminal is x^sAnd sends it to the second communication terminal.
Step 2: The second communication terminal is t∈S_oT is selected at random. The second communication terminal is x^tAnd sends it to the first communication terminal.
Step 3: The first communication terminal (x^t)^s' And f ((x^t)^s'). The second communication terminal is (x^s)^{t '}And f ((x^s)^{t '})^{t '}Calculate in this case,
[Formula 3]

Is a common secret key shared by the first communication terminal and the second communication terminal. According to Assumption 1, (x^t)^s' = (x^s)^{t '} It becomes.
[0018]
  Next, the ACTDH protocol according to the present invention will be described.
  Let G be a group of the same shape as C x C, where C is a cyclic group of order prime p. Where GL (2, [Z] to group G x G (= (C x C) x (C x C))_p) Defines the action. Suppose a and b generate G, ie G = <a, b>. This is | a | = | b | = p and in G <a> ∩ <b> = [1_G] Implicitly, where 1_GIndicates the identity of G.
[0019]
  All elements of G are i, j ∈ [Z]_pAⁱbⁱIs uniquely described.
[Formula 4]

so
[Formula 5]

in the case of,
[Formula 6]

GL (2, [Z]_p) Defines the action. x^AHowever, it can be calculated efficiently as follows.
[0020]
  G element a^i1j1And a^i2j2And given a matrix A,
[Formula 7]

Calculate GL (2, [Z]_p), But it works immediately on G x G, but it is possible to explain it more easily as follows.
element
[Formula 8]

And matrix
[Formula 9]

X to identify^AIs identified by the following determinant.
[Formula 10]

[0021]
  Matrix multiplication is associative, so GL (2, [Z]_p) Acts on G x G. Next, [Z] *_pRandomly select the parameters α, β, γ, and δ so that αβγδ becomes the square non-remainder, then S_oThe shape
[Formula 11]

To be a set of matrices. Where (i₁, i₂) ≠ ≠ (0,0), i₁, i₂ ∈ [Z]_pIt is.
[Formula 12]

With respect to A 'matrix
[Formula 13]

Define to be Since αβγδ is a non-square residue, A, A '∈ GL (2, [Z]_p).
[Formula 14]

And
[Formula 15]

Then A, B ∈ S_oAnd the following equation is obtained.
[Formula 16]

[0022]
  Therefore, the above assumption 1 holds. In the following, the matrix
[Formula 17]

When
[Formula 18]

Respectively, A (i₁, i₂) And A '(i₁, i₂) So all i₁, i₂, j₁, j₂∈ [Z]_pFor, the following equation is obtained:
[Formula 19]

π₁ : G x G → G is projected onto the first axis, ie
[Formula 20]

And
[Formula 21]

Note that
[0023]
ACTDH protocol: x = (a, b).
Step 1: First communication terminalComputing meansIs an integer i₁, I₂Select at random.Same calculation meansIs
[Formula 22]

Calculate it andBy sending meansSend to second communication terminal.
Step 2: Second communication terminalComputing meansIs an integer j₁, J₂Select at random.Same calculation meansIs
[Formula 23]

Calculate it andBy sending meansSend to first communication terminal.
[0024]
Step 3: The computing means of the first communication terminal isUsing the calculation result of Expression 23 sent from the second communication terminal,
[Formula 25]

When
[Formula 26]

By calculating and multiplying
[Formula 24]

Get. In addition,As shown in Equation 21,
[Formula 27]

It is.
Step 4: The computing means of the second communication terminal is similarlyUsing the calculation result of Expression 22 sent from the first communication terminal,
[Formula 93]

When
[Formula 94]

By calculating and multiplying
[Formula 24]

Calculate As shown in Equation 21,
[Formula 28]

It is. In this case, K is a common key for the first communication terminal and the second communication terminal.
[0025]
  Here, as an example, an example of a direct product of two cyclic groups of prime orders is shown. Let q and r be large prime numbers such that p | q-1 and p | r-1.
  Let n be qr. g₁Is the pth root of 1 in mod q, and g₂Is the pth root of 1 in mod r. Some c₁ ∈ [Z] *_pAnd c₂ ∈ [Z] *_pAbout a = g₁ (mod q), a = g^* ₂ (mod r), b = g^* ₁(mod q), b = g₂a ∈ Z so that (mod r)_nA and b ∈ Z_nSelect b that becomes c₁c₂ Z * if ≠ 1 mod p_n It is clear that = <a> x <b>.
[0026]
  Next, the security of the protocol of the present invention is compared with the Diffie-Hellman protocol.
  Decoding the ACTDH protocol is equivalent to solving the following problem. Suppose G is a finite abelian group and a, b ∈ G. The parameters α, β, γ, and δ are relatively prime with | a | and | b |, respectively. The definition of the action Diffie-Hellman problem (ACTDH problem) in G with respect to a and b is as follows.
[Formula 29]

[Formula 30]

  Where i₁, I₂, J₁, J₂Is a randomly and independently selected integer.
[0027]
  The following theorem and its proof ensure that the ACTDH protocol is at least as secure as the DH protocol if parameters are carefully selected.
<Theorem 1> α, β, γ, and δ are integers. Each of these is assumed to be relatively prime with | G |. If there is an efficient algorithm for solving the ACTDH problem (parameters α, β, γ, δ) in the Abelian group G for all a, b of G, the efficiency of solving the DH problem in G for all a of G There is a good algorithm.
[0028]
<Proof> Assume that there is an efficient algorithm for solving the ACTDH problem for all a and b. An efficient algorithm for solving the DH problem, ie input aⁱ¹And a^j1Regarding a^i1j1Create an algorithm to calculate Here, a is an element of G. b = 1 (G unit element). Since | G | breaks at | a |, α, β, γ, and δ must be relatively prime with | a |. The above assumption gives an efficient algorithm for solving the ACTDH problem for a and b. i₂= j₂= 0. An algorithm for solving the ACTDH problem with respect to a and b
[Formula 31]

When
[Formula 32]

Enter. Thus,
[Formula 33]

Is obtained. aⁱ¹And a^j1Since α is public information, (aⁱ¹) α and (a^j1It can be seen that α can be calculated. Since α and δ are both relatively prime with | a |, (aαδ)^m An integer m such that = a can be obtained. in this case,
[Formula 34]

Therefore, the DH problem can be solved efficiently.
[0029]
  Let G be a finite abelian group and let a and b be elements in G. Set H to be a small group of G generated by a and b. Multiple discrete logarithm problems (MDLOG for short) in the group H = <a, b> are algorithmic problems defined as follows.
INPUT: Element g of H.
OUTPUT: g = a^xb^yA non-negative integer (x, y) pair (x, y) such that
  Since H is generated by a and b, g = a^xb^yThere is at least one non-negative integer pair (x, y) that satisfies. Such a pair is uniquely determined only when H is the inner direct product <a> x <b>. It is clear that the ACTDH problem is reduced to the MDLOG problem, so that the ACTDH protocol can be deciphered when MDLOG is solved efficiently.
[0030]
  We consider the security of the ACTDH protocol from the viewpoint of the generic model. The ACTDH protocol with carefully selected parameters is more secure than the DH protocol in the generic model. To simplify the discussion, [Z]_p x [Z]_pConsider only the ACTDH protocol for the multiplication group G of the same form. Where p is a large prime number in the rest of the paper. The ACTDH protocol is secure even from an attacker who can solve the DLOG when the following conditions are imposed on α, β, γ, and δ.
[0031]
<Condition 1> α, β, γ, and δ are relatively prime to p.
<Condition 2> αβγδ is a square non-residue (mod p).
  Assume that condition 1 and condition 2 are met in the rest of the paper. Condition 1 is imposed to prevent α, β, γ, and δ from reducing the elements a, b ∈ G. On the other hand, Condition 2 looks somewhat unnatural. Condition 2 will be described later.
[0032]
  The generic algorithm according to the present invention will be described in detail.
  The generic algorithm is a general-purpose algorithm that does not depend on any characteristics of the group representation ([10], [5]). The generic algorithm enumerates group elements starting from a given set of elements of G, i.e. group elements starting from the set B from which G is generated, which is g for some j, k <i of each i_m = g and g_i ∈ B or g_i= g^-1 _jOr g_i = g_jg_kA sequence of elements of G so that₁, g₂, ..., g_mIs enumerated.
  At one stage, the algorithm uses an element g that represents the same binary string._iAnd g_jFind (i ≠ j). Then g_iAnd g_jHidden information can be obtained by solving the linear equation obtained from the information regarding.
[0033]
  σ, [Z]_pLet R be a random mapping from S to a set S of binary strings of size p. The generic algorithm is x, y ∈ [Z]_pAdd (σ (x), σ (y)) = call a group operation oracle that computes add and inv defined by σ (x + y) and inv (σ (x)) without any computational cost be able to. add (σ (x), σ (y)) = σ (x + y) is the multiplication g^xg^y = g^{x + y}Inv (σ (x)) = σ (-x) is the inversion of group elements (g)^-1 = g^-1Corresponding to Tour group [Z]_pThe DLOG generic algorithm in, takes (σ (1), σ (x)) as input / output x. Where x ∈ [Z]_pIt is. [Ref 5] introduces the Diffie-Hellman oracle to study the generic consequences of DLOG to DH.
[0034]
  Next, we examine in detail the difficulty of deciphering the ACTDFI protocol compared to the DLOG problem for generic consequences. The generic algorithm for the ACTDH problem is executed as follows. Group [Z]_px [Z]_p(p is a prime number) is encoded by a set S of binary character strings. The generic algorithm takes a list (σ (1,0), σ (0, 1), σ (αi₁, βi₂), σ (γi₂, δi₁), σ (αj₁j1, βj₂), σ (γj₂, δj₁)) Is obtained and calculated by calling the group operation oracle, then
[Formula 35]

Is output. Input is a group element
[Formula 36]

And the output is a group element
[Formula 37]

Corresponding to Enables generic algorithms to call discrete logarithmic oracles in addition to group operation oracles. [Z]_p x [Z]_pThe discrete logarithm (DLOC) Oracle of (σ (i₁, i₂), σ (j₁, j₂)) And then ni₁ = j₁(mod p) and ni₂ = j₂Outputs an integer n such that (mod p) holds without such computational cost if such n exists.
[0035]
  If there is no n that satisfies the above equation, such an input is called illegal. Suppose that Oracle is not subject to illegal input and the generic algorithm proceeds.
<Theorem 2> Let A be a group [Z]_p x [Z]_pA generic algorithm for solving the ACTDH problem. Where p is a prime number. The parameters α, β, γ, and δ satisfy the above conditions 1 and 2. Assume that A performs a maximum of R queries on the group operation oracle and a maximum of L queries on the DLOC oracle.
  In this case, the probability θ that A returns the correct solution is at most
[Formula 38]

Where this probability is i₁, I₂, J₁, J₂And dominated by the map σ. The expected number of queries for DLOC Oracle is at least
[Formula 39]

It is.
[0036]
  First, consider the importance of Theorem 2. Let T be the total execution time of A. Since T ≧ L + R, T ≧ L and T ≧ R are obtained. Assume that θ is a constant. By Theorem 2, we obtain [Equation 40].
  Therefore, T
[Formula 41]

It is. This implies that there is no stochastic polynomial time algorithm to decipher the ACTDH protocol even when the DLOG oracle is allowed.
  Now assume that the DLOG Oracle cannot be used. The number of queries expected for the group operation oracle to solve the ACTDH problem can be obtained from Theorem 2 by setting L = 0. Success probability θ
[Formula 42]

The number of queries expected for the upper bound, ie, the group operation oracle, is estimated to be Ω (√p) when θ is a constant.
[0037]
Next, we prove the above Theorem 2. The following is important in the following proof and is proved in [Reference 9].
<Lemma 1 ([Reference 9])> [Z] for all orders d_p[X₁, X₂, ..., X_k] (Z is a prime number), assuming a non-zero polynomial F, [Z]_pIndependently and randomly selected elements x₁, x₂, ..., x_kWith respect to F (x_1,x₂, ..., x_kThe probability that) = 0 is at most d / p.
[0038]
<Proof of Theorem 2> [Z]_pSimulate a generic algorithm with polynomials for. First, ring [Z]_p[X₁, X₂, Y₁, Y₂] 6 pairs of polynomials in (F₁, H₁) = (1,0), (F₂, H₂) = (0,1), (F_Three, H_Three) = (αX₁, βX₂,), (F_Four, H_Four) = (γX₂, δX₁), (F_Five, H_Five) = (αY₁, βY₂), (F₆, H₆) = (γY₂, δY₁) Each pair is a mapping (of group elements) σ (1, 0), σ (0, 1), σ (αi₁, βi₂), Σ (γi₂, δi₁), Σ (αj₁, βj₂), Σ (γj₂, δj₁) Respectively.
[0039]
  For I> k, l, the polynomial Fi (X₁, X₂, Y₁, Y₂) And Hi (X₁, X₂, Y₁, Y₂) So that a pair of polynomials (F_i, H₁) Is the mapping pair σ (Fi (i₁, i₂, j₁, j₂), Hi (i₁, i₂, j₁, j₂Corresponds to)). The multiplication oracle is a pair (F_k, H_k) And (F_l, H_l) When called by the input corresponding to_iAnd H_iF_i = F_k + F_lAnd H_i = H_k + H_lCalculate by setting to. Here, i> k, l.
[0040]
  Similarly, the inverting oracle is the pair (F_k, H_k) When called by the input corresponding to_i = -F_k And H_i = -H_kCalculate In this case, i> k, l. DLOG Oracle (F_k, H_k) And (F_l, H_l) When called with the input corresponding to_sF_k(i₁, i₂, j₁, j₂) = F_l(i₁, i₂, j₁, j₂) When_sH_k(i₁, i₂, j₁, j₂) = H_l(i₁, i₂, j₁, j₂) Such that s (∈ [Z]_p)return it. In this case, no polynomial is generated, but i₁, i₂, j₁, j₂ Is the formula F_k = F_lAnd sH_k = H_lInformation that satisfies is obtained.
[0041]
  The generic algorithm_1,i_2,j_1,j₂Suppose that a correct solution may be returned only when finding a non-trivial expression satisfied by.
  The generic algorithm uses the input σ (F_k(i₁, i₂, j₁, j₂), H_k(i₁, i₂, j₁, j₂)), And σ (F_l(i₁, i₂, j₁, j₂), H_l(i₁, i₂, j₁, j₂When calling the DLOG Oracle for)), there are three possible cases.
[0042]
  The first possible case is a case where the input is illegal, ie the second input is not a power of the first input.
  In the second case, the input is legal, but the polynomial F_k, H_k, F₁, H₁But [Z]_pAs a polynomial in condition F_kH_l = H_kF_lThis is a case satisfying (mod p).
  In the third case, the input is legal and F_kH_l ≠ H_kF_l This is the case for (mod p).
[0043]
  Where i₁, I₂, J₁, J₂Prove that information about is only available in the last case. If the first case occurs, DLOG Oracle returns only an error message. I, unless the second input is not a power of the first input₁, I₂, J₁, J₂There is no possibility to get information about.
  Next, consider the second case. F_kH_l -F_lH_k Assume = 0 (mod p). First, F_k, H_k, F_l, H_lBut [Z]_pNote that these are unit or irreducible polynomials, since they are polynomials of degree 1 at most. Polynomial ring [Z]_p[X₁, X₂, Y₁, Y₂] Is an intrinsic factorization domain, so u ∈ [Z]_pAs for some u_uF_k = F_lWhen_uH_k = H_lAnd u ∈ [Z]_pAs for some u_nF_k = H_kWhen_uF_l = H_lIs obtained.
[0044]
  _uF_k = F_lWhen_uH_k = H_lIn the case of DLOG Oracle, u ∈ [Z]_p, Input σ (F_k, H_k) And σ (F_l, H_l), But the equation_uF_k = F_lWhen_uH_k = H_lI₁, I₂, J₁, J₂As well as x₁, x₂, y₁, y₂ ∈ [Z]_pX₁, X₂, Y₁, Y₂Satisfied by all of the.
  next,_uF_k = H_kand_uF_l = H_lAssume that F_kAnd H_kBy the definition of
[Formula 43]

Can be described as
[Formula 44]

C₁, c₂, c_Three, c_Four, c_Five, c₆ ∈ [Z]_pMet._uF_k = H_kBecause uc₁ = c₂And the following equation:
[Formula 45]

  Since condition 2 is satisfied, the matrix
[Formula 46]

Is regular.
[0045]
  Therefore, c_Three= c_Four= c_Five= c₆= 0 (mod p), so that F_kAnd H_kAre both constants. Therefore, F_lAnd H_lIs also a constant. Thus, the oracle_k, H_k) And σ (F_l, H_l) And the result is F_kH_l = F_lH_kI₁, I₂, J₁, J₂Provide no information about. Therefore, only in the third case i₁, I₂, J₁, J₂Information can be obtained, so the DLOG oracle query is meaningful when called in the third case, and is otherwise meaningless.
[0046]
  Next, find the upper bound of the probability that A returns the correct solution. There are three cases where the generic algorithm returns the correct solution.
<Case 1> At least one DLOG oracle query is meaningful.
<Case 2> All DLOG Oracle queries are meaningless and [Z]_pAs a polynomial in (F_k, H_k) ≠ (F_l, H_l)In Although,
[Formula 47]

so
[Formula 48]

(F_k, H_k) And (F_l, H_l) Exists.
<Case 3> All DLOG Oracle queries are meaningless and some (F_k, H_k)
[Formula 49]

Is obtained.
[0047]
The upper bound of the probability in each of <Case 1>, <Case 2>, and <Case 3> is obtained.
<Case 1> The probability that a query to DLOG Oracle is meaningful is
[Formula 50]

Some k and l and [Z] by_pFor some s in [Z]_pX randomly selected in₁, X₂, Y₁, Y₂Regarding
[Formula 51]

When
[Formula 52]

Is limited by the probability of obtaining In that case, the probability is [Z]_pRandomly selected x in₁, X₂, Y₁, Y₂Since the following formula is obtained,
[Formula 53]

Get.
[Formula 54]

[Formula 55]

  [Z]_pX randomly selected from₁, X₂, Y₁, Y₂With respect to
[Formula 56]

The probability of obtaining the polynomial F_lH_k -F_kH_lThe total order of does not exceed 2, as a polynomial
[Formula 57]

Therefore, it is limited to 2 / p by Lemma 1. Therefore, the probability that at least one DLOG oracle query is meaningful is
[Formula 58]

Limited by.
[0048]
<Case 2>
[Formula 59]

Assume that (i) F_k≠ F_l(H_k ≠ H_lOr H_k = H_lAnd (ii) F_k = F_lAnd H_k ≠ H_lThere are three cases. In case (i), [Z]_pRandomly selected x in₁, X₂, Y₁, Y₂Regarding
[Formula 60]

The maximum probability is 1 / p according to Lemma 1. Thus, in case (i), some k, l and [Z]_pRandomly selected x in₁, X₂, Y₁, Y₂Regarding
[Formula 61]

When
[Formula 62]

The probability that
[Formula 63]

It is.
[0049]
  Similarly, the probability of case (ii) is at most
[Formula 64]

It is. Therefore, the probability in <Case 2> is the maximum.
[Formula 65]

It is.
[0050]
<Case 3> According to Lemma 1, [Z]_pRandomly selected x in₁, X₂, Y₁, Y₂With respect to the polynomial F_k-αδX₁Y₁+ βγX₂y₂And H_k-βδ (X₁Y₂+ X₂Y₁) Has a total degree of 2, so some (F_k, H_k)
[Formula 67]

The upper bound of the probability of an event that yields
[Formula 66]

It is. Note that αδ ≠ 0, βγ ≠ 0, and βδ ≠ 0 (mod p), depending on condition (C1). Therefore, the probability that the generic algorithm outputs the correct solution is the maximum.
[Formula 68]

It is.
[0051]
  Next, we consider the generic consequences of MDLOG for DLOG. The following results show that MDLOG cannot be solved without a large number of queries against the DLOG oracle. If p is a large prime, the group [Z]_p x [Z]_pMDLOG's generic algorithm₁, x₂) As (σ (1,0), σ (0,1), σ (x₁, x₂)). Where x₁, X₂Is 0 ≤ x₁ <P and 0 ≤ x₂ <An integer of p.
[0052]
<Theorem 3> Let A be a generic algorithm that solves MDLOC in G. Assume that each A performs a maximum of R queries on the group operation oracle and a maximum of L queries on the DLOC oracle. In that case, the probability that A returns the correct solution is the maximum.
[Formula 69]

And where i₁, I₂, J₁, J₂And the probability for the map σ is obtained. The expected number of DLOC Oracle queries is at least
[Formula 70]

It is.
[0053]
  Condition 2 shown above is very important. If αβγδ is a square remainder (mod p), there is an attack on the ACTDH protocol by using the DLOG oracle.
Attacks against the ACTDH protocol with non-unique parameters ::
  Αβγδ = u for some u²Assume that (mod p). In this case, the matrix
[Formula 71]

Is singular, and therefore the following equation is a non-trivial solution.
[Formula 72]

(s, t) = (c_Three, c_Four) Is a non-trivial solution. Group element
[Formula 73]

Is given
[Formula 74]

Can be calculated. c_Three, C_FourBy the definition of
[Formula 75]

And
[Formula 76]

Got. ab^uAnd then enter
[Formula 77]

And ab^uCall DLOG Oracle by Oracle
[Formula 78]

return it. Then another (c '_Three, c '_Four) Perform a similar process,
[Formula 79]

Get. In this case i₁And i₂Can be obtained. Similarly, the attacker is j₁And j₂Can be obtained.
[0054]
  The ACTDH protocol is applied to configure a public key cryptosystem as follows. Let G be a group that is isomorphic to the direct product C x C, where C is a cyclic group of prime order p. Suppose G = <a, b>. GL for G x G (2, [Z]_p) Has been described above. A (i₁, i₂) And A '(i₁, i₂) Is a matrix
[Formula 80]

and
[Formula 81]

I want to recall that.
[0055]
Describes key generation. α, β, γ, and δ are parameters satisfying the conditions 1 and 2. Let x = (a, b) ∈ G x G. The second communication terminal is i₁, i₂ ∈ [Z]_pSelect at random. Next, the second communication terminal
[Formula 82]

And publicize the key (x, y).
[0056]
  Encryption and decryption are performed as follows.
  Encryption: The first communication terminal is j₁, j₂ ∈ [Z]_pSelect at random. Next, the first communication terminal sends a message
[Formula 83]

The
[Formula 84]

Encrypt as
[0057]
  Decryption: Ciphertext
[Formula 85]

The second communication terminal acquires the group element
[Formula 86]

And its reciprocal. Next, the second communication terminal is a group element
[Formula 88]

But
[Formula 89]

M to match
[Formula 87]

Can be obtained as
[0058]
  Let G be a group that is isomorphic to the direct product of two cyclic groups of order prime p. Assume that [a, b] is the set of G generators. Set x = (a, b). Assuming A is a stochastic polynomial time algorithm, input
[Formula 90]

With respect to i₁, I₂, J₁, J₂Are randomly selected and M∈ GL (2, [Z]_p), A is
[Formula 91]

Outputs 1 if, otherwise 0, and this probability is about some constant c for a sufficiently large n
[Formula 92]

Higher than. In this case, A is called the DACTDH algorithm. The assumption of DACTDH is that there is no DACTDH algorithm. The DACTDH assumption appears weaker than the DH assumption because there is no obvious use of the DLOC oracle to solve the DACTDH problem and the DDH oracle is easily solved using the DLOG oracle.
[0059]
<Theorem 4> The proposed encryption method is not secure in the sense of distinction when and only when the DACTDH algorithm exists.
  The proof of this theorem is omitted. That is, the proposed encryption scheme is semantically secure against passive attacks when and only if DACTDH processing is difficult.
[0060]
【The invention's effect】
  Since the present invention is configured as described above, the following effects can be obtained.
Play.
  That is, in the key exchange schemes known so far (for example, Diffie-Hellman type), the difficulty of solving the discrete logarithm problem of the finite cyclic group is based on the security, but in the present invention, The key agreement protocol not only in the finite cyclic group but also in other finite commutative groups, and the configuration of the communication method using the protocol are made possible.
[0061]
  Also, using a finite commutative group other than a finite cyclic group can result in an algorithm problem that is considered to be more difficult than a discrete logarithm problem. Realize a higher level of security than the discrete logarithm problem-based key exchange scheme by placing security grounds on algorithm problems that are considered to be more difficult than discrete logarithm problems from a generic algorithm model perspective I can do it.
[References]
[Reference 1]
  L.Babai and E.Szemer6di On the complexity of matrix group problems, IEEE Symp.Found. Of Computer Scienece (1984) 229-240.
[Reference 2]
  W.Difiie and M.E.Hellman, New directions in cryptography, IEEE Thansactions on InforTr ~ ation Theory, 22 (1976) 644-654.
[Reference 3]
  T.EIGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Thansactions on Information Theory, 31 (1985) 469-472.
[Reference 4]
  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.
[Reference 5]
  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.
[Reference 6]
  V # 1.Nechaev, Complexity of a deternxinate algorithm for the discrete logarithm, Math.Notes, 55 (1994) 165-172.
[Reference 7]
  C.P.Schnorr, Small generic hardcore subsets for the discrete logarithm: Short secret DLekeys, Infor.Proc. Letters, 79 (2001) 93-98.
[Reference 8]
  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.
[Reference 9]
  J.T.Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27 (4) (1980) 701-717.
[Reference 10]
  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.

Claims (1)

Using finite commutative groups other than finite cyclic groups and using the action of general linear groups on the direct product of two cyclic groups, it is safe for the difficulty of algorithm problems that are considered more difficult than the discrete logarithm problem A communication method for performing communication between a first communication terminal and a second communication terminal using a key agreement protocol based on sex ,
The following conditions, that is, G is defined as a group having the same shape as CxC (C is a cyclic group whose degree is a prime p), a and b are defined to generate G, and parameters α, β, γ, and δ are modulo p As a condition of randomly selecting such that αβγδ becomes a non-square residue,
The computing means of the first communication terminal randomly selecting integers i ₁ and i ₂ ;
The calculation means is [Equation 22]

Calculating and sending it to the second communication terminal,
The computing means of the second communication terminal randomly selecting integers j1, j2;
The calculation means is [Equation 23]

Calculating and sending it to the first communication terminal by the transmitting means ;
The computing means of the first communication terminal is
[Formula 25]

And [Formula 26]

By calculating and multiplying [Equation 24]

Obtaining K of
The computing means of the second communication terminal is
[Formula 93]

And [Formula 94]

By calculating and multiplying [Equation 24]

Each step of obtaining K of
Communication method is characterized in that a common key between the first communication terminal and the second communication terminal the K.