(57)【要約】【課題】従来よりも演算コストが小さいハッシング可能暗号技術を提供することを目的とする。【解決手段】ハッシング可能暗号システムは、暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成する鍵生成装置１と、暗号化鍵pk及びメッセージmに基づいて暗号文cを生成する暗号化装置２と、復号鍵sk及び暗号文cに基づいてメッセージmを復号する復号装置３と、ハッシング鍵hk及び暗号文cに基づいてメッセージmのハッシュ値を計算するハッシュ値計算装置４と、を備えている。【選択図】図１
2015215490.tif 000002
【特許請求の範囲】
【請求項１】
暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成する鍵生成装置と、
上記暗号化鍵pk及びメッセージmに基づいて暗号文cを生成する暗号化装置と、
上記復号鍵sk及び上記暗号文cに基づいてメッセージmを復号する復号装置と、
上記ハッシング鍵hk及び上記暗号文cに基づいて上記メッセージmのハッシュ値を計算するハッシュ値計算装置と、
を含むハッシング可能暗号システム。
【請求項２】
請求項１のハッシング可能暗号システムであって、
p,qを素数とし、EをFp上の埋め込み次数kのペアリング親和超特異楕円曲線とし、E(Fp)[q]の生成元をgとし、E(Fp^k)[q]＼E(Fp)[q]の元をg1として、
上記鍵生成装置は、乱数x∈Fqを選び、y=gxを計算し、y1=g1xを計算することにより、暗号化鍵pk=(g,g1,y)、復号鍵sk=x及びハッシュ鍵hk=(pk,y1)を生成する鍵生成装置であり、
上記暗号化装置は、mをメッセージとして、上記暗号化鍵pk=(g,g1,y)の中のg,yに基づいて、乱数r∈Fqを選び、G=gr計算し、M=m・yrを計算することにより、暗号文c=(G,M)を生成する暗号化装置であり、
上記復号装置は、上記秘密鍵sk=x及び上記暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する復号装置であり、
上記ハッシュ値計算装置は、eをペアリング関数とし、上記ハッシュ鍵hk=(pk,y1)、上記暗号化鍵pk=(g,g1,y)の中のg1,y及び上記暗号文c=(G,M)に基づいて、ハッシュ値h=e(M,g1)/e(G,y1)を計算するハッシュ値計算装置である、
ハッシング可能暗号システム。
【請求項３】
請求項１のハッシング可能暗号システムであって、
ψ:M→HをMを入力空間Hを出力空間としたランダム写像とし、∀m∈M,φ-1(φ(m))=mなる写像φ-1:H→Mが存在するとし、ψ:R×H→CをR×Hを入力空間Cを出力空間としたランダム写像とし、∀r∈R,∀h∈H,ψ-1(ψ(r,h))=hなる写像ψ-1:C→H存在するとして、
上記鍵生成装置は、暗号化鍵pk=ψ(・,φ(・))、復号鍵sk=φ-1(ψ-1(・))及びハッシュ鍵hk=ψ-1(・)を生成する鍵生成装置であり、
上記暗号化装置は、mをメッセージとして、上記暗号化鍵pk=ψ(・,φ(・))に基づいて、乱数r∈Rを選び、暗号文c=ψ(r,φ(m))を生成する暗号化装置であり、
上記復号装置は、上記復号鍵sk=φ-1(ψ-1(・))及び上記暗号文c=ψ(r,φ(m))に基づいて、メッセージm=φ-1(ψ-1(c))を計算する復号装置であり、
ハッシュ値計算装置は、上記ハッシュ鍵hk=ψ-1(・)及び上記暗号文c=ψ(r,φ(m))に基づいて、ハッシュ値h=ψ-1(c)を計算するハッシュ値計算装置である、
ハッシング可能暗号システム。
【請求項４】
請求項１のハッシング可能暗号システムであって、
P,Qを素数とし、N=P×Qとし、e,dをe×d≡1(mod(P-1)(Q-1))の関係を満たす整数とし、素数位数qの巡回群をGとし、Gの生成元をgとして、
上記鍵生成装置は、乱数x∈Fqを選び、y=gxを計算することにより、暗号化鍵pk=(N,e,G,q,g,y)、復号鍵sk=(d,x)及びハッシュ鍵hk=xを生成する鍵生成装置であり、
上記暗号化装置は、mをメッセージとして、上記暗号化鍵pk=(N,e,G,q,g,y)の中のN,e,q,g,yに基づいて、乱数r∈Fqを選び、G1=gr計算し、Y1=(me mod N)(+)yrを計算することにより、暗号文c=(G1,Y1)を生成する暗号化装置であり、
上記復号装置は、上記復号鍵sk=(d,x)及び上記暗号文c=(G1,Y1)に基づいて、メッセージm=(Y1(+)G1x)dmod Nを計算する復号装置であり、
上記ハッシュ値計算装置は、上記ハッシュ鍵hk=x及び上記暗号文c=(G1,Y1)に基づいて、ハッシュ値h= Y1(+)G1xを計算するハッシュ値計算装置である、
ハッシング可能暗号システム。
【請求項５】
請求項１のハッシング可能暗号システムであって、
K1,K2をそれぞれ鍵空間とし、φ:K1×M→Hとし、φ-1:K1×H→Mとし、ψ:K2×R×H→Cとし、ψ-1:K2×C→Hとして、
上記鍵生成装置は、乱数k1∈K1を選び、乱数k2∈K2を選ぶことにより、暗号化鍵pk=(k1,k2)、復号鍵sk=(k1,k2)及びハッシュ鍵hk=k2を生成する鍵生成装置であり、
上記暗号化装置は、上記暗号化鍵pk=(k1,k2)に基づいて、乱数r∈Rを選ぶことにより、暗号文c=(k2,r,φ(k1,m))を生成する暗号化装置であり、
上記復号装置は、上記復号鍵sk=(k1,k2)及び上記暗号文c=(k2,r,φ(k1,m))に基づいて、メッセージm=φ(k1,ψ-1(k2,c))を計算する復号装置であり、
上記ハッシュ値計算装置は、上記ハッシュ鍵hk=k2及び上記暗号文c=(k2,r,φ(k1,m))に基づいて、ハッシュ値h=ψ-1(k2,c)を計算するハッシュ値計算装置である、
ハッシング可能暗号システム。
【請求項６】
鍵生成装置が、暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成する鍵生成ステップと、
暗号化装置が、上記暗号化鍵pk及びメッセージmに基づいて暗号文cを生成する暗号化ステップと、
復号装置が、上記復号鍵sk及び上記暗号文cに基づいてメッセージmを復号する復号ステップと、
ハッシュ値計算装置が、上記ハッシング鍵hk及び上記暗号文cに基づいて上記メッセージmのハッシュ値を計算するハッシュ値計算ステップと、
を含むハッシング可能暗号方法。
【請求項７】
鍵生成装置が暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成するとし、暗号化装置は暗号化鍵pk及びメッセージmに基づいて暗号文cを生成するとし、復号装置は上記復号鍵sk及び上記暗号文cに基づいてメッセージmを復号するとして、
上記ハッシング鍵hk及び上記暗号文cに基づいて上記メッセージmのハッシュ値を計算するハッシュ値計算装置。
【請求項８】
請求項７のハッシュ値計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、ハッシング可能暗号技術に特に関する。
【背景技術】
【０００２】
［記法の説明］
・値YをXと定義する事をX:=Yと記述する。「:」を省略して単にX=Yと記述することもある。
【０００３】
・集合χから一様ランダムに選んだ要素をXと定義する事をX←$χ又はχ→$Xと記述する。
【０００４】
・確率的多項式時間アルゴリズムAlgに一様ランダムなランダムテープを入力して得られた出力をXと定義する事をX←$Alg()又はAlg()→$Xと記述する。
【０００５】
・確率的多項式時間アルゴリズムAlgに一様ランダムなランダムテープを入力して得られる出力の集合を{Alg()}と記述する。X←$Alg()とX←${Alg()}は全く意味が違う。
【０００６】
・変数X及び変数Yに対して二項演算子X=?YをX=Yならば1、X≠Yならば0と定義する。
【０００７】
[マッチング可能暗号]
マッチング可能暗号とは確率暗号の一種で、マッチング可能暗号では暗号文の復号鍵保有者は鍵生成時に復号鍵sk、暗号化鍵pkの他にマッチング鍵と呼ばれる第三の鍵mkを生成する。マッチング鍵を用いて暗号文を復号する事は出来ないが、２つの暗号文が等しい平文を持つか否かを判定する事が出来る（例えば、非特許文献１参照。）。マッチング鍵が復号鍵から完全に分離しているので、復号鍵保有者は暗号文の内容を明かさなくてもマッチング鍵だけを誰かに預けることが出来る。マッチング可能暗号は、一般に以下の４つの確率的多項式時間アルゴリズム(KeyGen, Enc, Dec, Match)より構成され、平文空間をMとして下記の構文を持つ。
【０００８】
KeyGen(1λ)→$(pk,sk,mk):鍵生成-セキュリティパラメータ1λを入力とし暗号化鍵pk、復号鍵sk及びマッチング鍵mkを出力する確率的多項式時間アルゴリズム。
【０００９】
Enc(pk,m)→$c:暗号化-公開パラメタpk及び平文mを入力とし、暗号文cを出力する確率的多項式時間アルゴリズム。
【００１０】
Dec(sk,c)→$m:復号-復号鍵sk及び暗号文cを入力とし、平文mを出力する確率的多項式時間アルゴリズム。
【００１１】
Match(mk,c1,c2)→$b:マッチング-マッチング鍵mk及び２つの暗号文c1,c2を入力とし、暗号文に含まれる平文が等しいか否かの1 bitの情報(マッチング情報) b∈{0,1}を出力する確率的多項式時間アルゴリズム。
【００１２】
(pk,sk,mk)←$KeyGen(1λ), (m,m1,m2)←$M3なる時、KeyGenのランダムテープ及びm,m1,m2を標本空間とする次の２つの確率
Pr[Dec(sk,Enc(pk,m))=m]
Pr[Match(mk,Enc(pk,m1),Enc(pk,m2))=(m1=?m2)]
がいずれもλに関して圧倒的である時、そのマッチング可能暗号(KeyGen, Enc, Dec, Match)は正当であるという。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】F. Hoshino, K. Suzuki and T. Kobayashi. “Revocable DDH by using Pairing and It's Appli-cation”, SCIS 2005 The 2005 Symposium on Cryptography and Information Security, 3D4-3, Maiko Kobe, Japan, Jan. P.25-28, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
一般にマッチング可能暗号におけるMatch()関数は二つの暗号文が等しいか否かを判定することしか出来ない。今、Match()関数は、等しいか否かのみの1 bitの情報しか返さないとする。このときn個の暗号文から、ある暗号文と同じ平文（メッセージ）を持つ暗号文を抽出するためには n回のMatch()関数を呼び出す必要がある。従って、n個の暗号文中に平文がm種類あると仮定すると同じ平文を持つ暗号文を纏める処理を行なうためには、 平均的にはn×mに比例する回数のMatchアルゴリズムの呼び出しが必要となる。特にnが
mに比例すると仮定するとおよそΘ(m2)のMatch()関数の呼び出しが必要となる。従って暗号文および暗号文に付随する付加情報が大量にあり、同じ平文を持つ暗号文および付加情報を纏めて処理したい場合にmが大きいと必要な演算コストが非常に大きくなってしまうという可能性があった。
【００１５】
この発明の目的は、従来よりも演算コストが小さいハッシング可能暗号システム及び方法、ハッシュ値計算装置並びにプログラムを提供することである。
【課題を解決するための手段】
【００１６】
この発明の一態様によるハッシング可能暗号システムは、暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成する鍵生成装置と、暗号化鍵pk及びメッセージmに基づいて暗号文cを生成する暗号化装置と、復号鍵sk及び暗号文cに基づいてメッセージmを復号する復号装置と、ハッシング鍵hk及び暗号文cに基づいてメッセージmのハッシュ値を計算するハッシュ値計算装置と、を備えている。
【発明の効果】
【００１７】
暗号文からその暗号文に対応する平文のハッシュ値を計算可能とすることにより、そのハッシュ値の利用が可能となる。これにより、従来よりも演算コストが小さくすることができる。
【図面の簡単な説明】
【００１８】
【図１】ハッシング可能暗号システムの例を説明するためのブロック図。
【発明を実施するための形態】
【００１９】
［技術的背景］
マッチング可能暗号におけるMatch()関数が等しいか否かの1 bitの情報しか返さない事が問題の本質である。暗号文の代わりに平文あるいはそのハッシュ値が利用出来るとすると、例えば平文やハッシュ値の順序関係の情報を利用することが出来、例えば高速なソーティングやハッシュ表を用いた連想配列などを用いて、平文を纏める処理を高速に行う事が出来る。暗号学的安全性の為にマッチング可能暗号のMatch()関数に相当する関数が平文そのものを復元する事は許されないが、そのハッシュ値を利用することは可能である。従ってマッチング可能暗号の代わりに次のようなハッシング可能暗号(KeyGen, Enc, Dec, Hash)を考える。
【００２０】
KeyGen(1λ)→$(pk,sk,hk):鍵生成-セキュリティパラメータ1λを入力とし暗号化鍵pk、復号鍵sk及びハッシング鍵hkを出力する確率的多項式時間アルゴリズム。
【００２１】
Enc(pk,m)→$c:暗号化-公開パラメタである暗号化鍵pk及びメッセージである平文mを入力とし、暗号文cを出力する確率的多項式時間アルゴリズム。
【００２２】
Dec(sk,c)→$m:復号-復号鍵sk及び暗号文cを入力とし、平文mを出力する確率的多項式時間アルゴリズム。
【００２３】
Hash(hk,c)→$h:ハッシュ-ハッシング鍵hk及び暗号文cを入力とし、暗号文に含まれる平文のハッシュ値hを出力する確率的多項式時間アルゴリズム。
【００２４】
図１の鍵生成装置１が、KeyGenのアルゴリズムにより、暗号化鍵pk、復号鍵sk及びハッシング鍵hkを生成する（ステップＳ１）。暗号化装置２が、例えばEncのアルゴリズムにより、暗号化鍵pk及びメッセージmに基づいて暗号文cを生成する（ステップＳ２）。復号装置３が、復号鍵sk及び暗号文cに基づいてメッセージmを復号する（ステップＳ３）。ハッシュ値計算装置が、ハッシング鍵hk及び暗号文cに基づいてメッセージmのハッシュ値を計算する（ステップＳ４）。
【００２５】
(pk,sk,hk)←$KeyGen(1λ), (m,m1,m2)←$M3なるとき、KeyGenのランダムテープ及びm,m1,m2を標本空間とする次の2つの確率
Pr[Dec(sk, Enc(pk,m))=m],
Pr[(Hash(hk,Enc(pk,m1))=?(Hash(hk,Enc(pk,m2)))=(m1=?m2))
がいずれもλに関して圧倒的である時、そのハッシング可能暗号 (KeyGen,Enc,Dec,Hash)は正当であるという。関数(Hash(hk,c1)=?Hash(hk,c2))をマッチング可能暗号のMatch(hk,c1,c2)関数と見なすことが出来る。
【００２６】
［第一実施形態］
以下、図１を参照して、第一実施形態のハッシング可能暗号システム及び方法の説明をする。
【００２７】
ハッシング可能暗号システムは、鍵生成装置１、暗号化装置２、復号装置３及びハッシュ値計算装置４を備えている。ハッシング可能暗号方法は、以下に述べるステップＳ１からステップＳ４の処理を有する。
【００２８】
p,qのそれぞれは、素数である。例えば、p,qは、十分に大きい素数とする。要求されるセキュリティのレベルが高くない場合には、p,qは、十分に大きい素数でなくてもよい。Fp,Fqは、それぞれ素数p,qに対する有限体である。pは、セキュリティパラメータ1λに応じて例えば決定される。
【００２９】
＜鍵生成装置１＞
鍵生成装置１は、セキュリティパラメータ1λに基づいて、例えば以下のKeyGenの処理を行うことにより暗号化鍵pk=(g,g1,y)、復号鍵sk=x及びハッシュ鍵hk=(pk,y1)を生成するを生成する。
KeyGen(1λ)→$(pk,sk,hk):
-セキュリティパラメータ1λに応じて素数pを選びFp上埋め込み次数kのペアリング親和非超特異楕円曲線Eを選び、E(Fp)[q]の適当な生成元g及びE(Fp^k)[q]＼E(Fp)[q]の適当な元g1を選ぶ。kは１以上の整数である。E(Fp)はペアリング親和超特異楕円曲線E上の点の中のFp有理点が成す群であり、位数がqで割り切れるとする。E(Fp)[q]はE(Fp)の中で位数がqである元が成す群である。E(Fp^k)は、ペアリング親和超特異楕円曲線E上の点の中のFp^k有理点が成す群であり、位数がq2で割り切れるとする。E(Fp^k)[q]はE(Fp^k)の中で位数がqである元が成す群である。＼は差集合を意味する。
【００３０】
-x←$Fq,
-y:=gx,
-y1:=g1x,
-sk:=x,
-pk:=(g,g1,y),
-hk:=(pk,y1),
-(pk,sk,hk)を出力する。
【００３１】
例えばこのようにして、鍵生成装置１は、乱数x∈Fqを選び、y=gxを計算し、y1=g1xを計算することにより、暗号化鍵pk=(g,g1,y)、復号鍵sk=x及びハッシュ鍵hk=(pk,y1)を生成する（ステップＳ１）。
【００３２】
生成された暗号化鍵pk=(g,g1,y)は暗号化装置２に送信され、復号鍵sk=xは復号装置３に送信され、ハッシュ鍵hk=(pk,y1)はハッシュ値計算装置４に送信される。
【００３３】
＜暗号化装置２＞
暗号化装置２は、暗号化鍵pk=(g,g1,y)の中のg,yに基づいて、例えば以下のEncの処理を行うことにより暗号文c=(G,M)を生成する。
【００３４】
Enc(pk,m)→$c:
-(g,g1,y):=pk,
-r←$Fq,
-G:=gr,
-M:=m・yr,
c:=(G,M)を出力する。
【００３５】
例えばこのようにして、暗号化装置２は、mをメッセージとして、暗号化鍵pk=(g,g1,y)の中のg,yに基づいて、乱数r∈Fqを選び、G=gr計算し、M=m・yrを計算することにより、暗号文c=(G,M)を生成する（ステップＳ２）。
【００３６】
生成された暗号文c=(G,M)は、復号装置３及び必要に応じてハッシュ値計算装置４に送信される。
【００３７】
なお、暗号化装置２が、メッセージm1,m2にそれぞれ基づいて生成した異なる２個の暗号を第一暗号文c1=(G1,M1)及び第二暗号文c2=(G2,M2)とする。
【００３８】
＜復号装置３＞
復号装置３は、秘密鍵sk=x及び暗号文c=(G,M)に基づいて、例えば以下のDecの処理を行うことによりメッセージm=M/Gxを計算する。
【００３９】
Dec(sk,c)→$m:
-x:=sk,
-(G,M):=c,
-m:=M/Gxを出力する。
【００４０】
例えばこのようにして、復号装置３は、秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する（ステップＳ３）。
【００４１】
＜ハッシュ値計算装置４＞
ハッシュ値計算装置４は、例えば以下のHashの処理を行うことによりハッシュ鍵hk=(pk,y1)、暗号化鍵pk=(g,g1,y)の中のg1,y及び暗号文c=(G,M)に基づいて、ハッシュ値h=e(M,g1)/e(G,y1)を計算する。
【００４２】
Hash(hk,c)→$h:
-(pk,y1):=hk,
-(g,g1,y):=pk,
-(G,M):=c,
-h:=e(M,g1)/e(G,y1)を出力する。
【００４３】
例えばこのようにして、ハッシュ値計算装置４は、ハッシュ鍵hk=(pk,y1)、暗号化鍵pk=(g,g1,y)の中のg1,y及び暗号文c=(G,M)に基づいて、ハッシュ値h=e(M,g1)/e(G,y1)を計算する（ステップＳ４）。
【００４４】
ハッシュ値計算装置４は、第一の暗号文c1=(G1,M1)に基づいて生成された第一ハッシュ値と、第二の暗号文c2=(G2,M2)に基づいて生成された第二ハッシュ値とが一致するかどうかを確認することにより、メッセージm1とメッセージm2とが一致するかどかを判定することができる。第一ハッシュ値＝第二ハッシュ値であれば、メッセージm1＝メッセージm2である。
【００４５】
［第二実施形態］
以下、図１を参照して、第二実施形態のハッシング可能暗号システム及び方法の説明をする。第二実施形態のハッシング可能暗号は、ランダム写像を使ったものである。
【００４６】
第二実施形態のハッシング可能暗号システムは、第一実施形態のハッシング可能暗号システムと同様に、鍵生成装置１、暗号化装置２、復号装置３及びハッシュ値計算装置４を備えている。第二実施形態のハッシング可能暗号方法は、以下に述べるステップＳ１からステップＳ４の処理を有する。
【００４７】
＜鍵生成装置１＞
ψ:M→HをMを入力空間Hを出力空間としたランダム写像とし、∀m∈M,φ-1(φ(m))=mなる写像φ-1:H→Mが存在するとする。また、ψ:R×H→CをR×Hを入力空間Cを出力空間としたランダム写像とし、∀r∈R,∀h∈H,ψ-1(ψ(r,h))=hなる写像ψ-1:C→H存在するとする。H,M,H,Cは、有限個の元から構成される集合である。ランダム写像とは、入力空間から出力空間への有限個存在する写像の中からランダムに選択された写像のことである。
【００４８】
鍵生成装置１は、例えば以下のKeyGenの処理を行うことにより、暗号化鍵pk=ψ(・,φ(・))、復号鍵sk=φ-1(ψ-1(・))及びハッシュ鍵hk=ψ-1(・)を生成する。
【００４９】
KeyGen(1λ)→$(pk,sk,hk):
-セキュリティパラメータ1λに応じて|M|,|R|>2λなる十分大きい入力空間について上記のランダム写像φ,ψを選ぶ。
【００５０】
-sk:=φ-1(ψ-1(・)),
-pk:=ψ(・,φ(・)),
-hk:=ψ-1(・),
-(pk,sk,hk)を出力する。
【００５１】
例えばこのようにして、鍵生成装置１は、暗号化鍵pk=ψ(・,φ(・))、復号鍵sk=φ-1(ψ-1(・)及びハッシュ鍵hk=ψ-1(・)を生成する（ステップＳ１）。
【００５２】
生成された暗号化鍵pk=ψ(・,φ(・))は暗号化装置２に送信され、復号鍵sk=φ-1(ψ-1(・)は復号装置３に送信され、ハッシュ鍵hk=ψ-1(・)はハッシュ値計算装置４に送信される。
【００５３】
＜暗号化装置２＞
暗号化装置２は、暗号化鍵pk=ψ(・,φ(・))に基づいて、例えば以下のEncの処理を行うことにより、暗号文c=ψ(r,φ(m))を生成する。mはメッセージである。
【００５４】
Enc(pk,m)→$c:
-ψ(・,φ(・)):=pk,
-r←$R,
-c:=φ(r,ψ(m))を出力する。
【００５５】
例えばこのようにして、暗号化装置２は、mをメッセージとして、暗号化鍵pk=ψ(・,φ(・))に基づいて、乱数r∈Rを選び、暗号文c=ψ(r,φ(m))を生成する（ステップＳ２）。
【００５６】
生成された暗号文c=ψ(r,φ(m))は、復号装置３及び必要に応じてハッシュ値計算装置４に送信される。
【００５７】
なお、暗号化装置２が、メッセージm1,m2にそれぞれ基づいて生成した異なる２個の暗号を第一暗号文c1=(G1,M1)及び第二暗号文c2=(G2,M2)とする。
【００５８】
＜復号装置３＞
復号装置３は、復号鍵sk=φ-1(ψ-1(・))及び暗号文c=ψ(r,φ(m))に基づいて、例えば以下のDecの処理を行うことによりメッセージm=φ-1(ψ-1(c)を計算する。
【００５９】
Dec(sk,c)→$m:
-φ-1(ψ-1(・):=sk,
-m:=φ-1(ψ-1(c))を出力する。
【００６０】
例えばこのようにして、復号装置３は、復号鍵sk=φ-1(ψ-1(・))及び暗号文c=ψ(r,φ(m))に基づいて、メッセージm=φ-1(ψ-1(c))を計算する（ステップＳ３）。
【００６１】
＜ハッシュ値計算装置４＞
ハッシュ値計算装置４は、例えば以下のHashの処理を行うことによりハッシュ鍵hk=ψ-1(・)及び暗号文c=ψ(r,φ(m))に基づいて、ハッシュ値h=ψ-1(c)を計算する。
【００６２】
Hash(hk,c)→$h:
-ψ-1(・):=hk,
-h:=ψ-1(c)を出力する。
【００６３】
例えばこのようにして、ハッシュ値計算装置４は、ハッシュ鍵hk=ψ-1(・)及び暗号文c=ψ(r,φ(m))に基づいて、ハッシュ値h=ψ-1(c)を計算する。
【００６４】
ハッシュ値計算装置４は、第一の暗号文c1=(G1,M1)に基づいて生成された第一ハッシュ値と、第二の暗号文c2=(G2,M2)に基づいて生成された第二ハッシュ値とが一致するかどうかを確認することにより、メッセージm1とメッセージm2とが一致するかどかを判定することができる。第一ハッシュ値＝第二ハッシュ値であれば、メッセージm1＝メッセージm2である。
【００６５】
［第三実施形態］
以下、図１を参照して、第三実施形態のハッシング可能暗号システム及び方法の説明をする。第三実施形態のハッシング可能暗号は、φをRSA暗号の暗号化、ψをElGamal暗号の暗号化とするものである。
【００６６】
第三実施形態のハッシング可能暗号システムは、第一実施形態のハッシング可能暗号システムと同様に、鍵生成装置１、暗号化装置２、復号装置３及びハッシュ値計算装置４を備えている。第三実施形態のハッシング可能暗号システムは、ハッシング可能暗号方法は、以下に述べるステップＳ１からステップＳ４の処理を有する。
【００６７】
＜鍵生成装置１＞
P,Qを素数とし、N=P×Qとし、e,dをe×d≡1(mod(P-1)(Q-1))の関係を満たす整数とし、素数位数qの巡回群をGとし、Gの生成元をgとする。セキュリティレベルを高くする場合には、qを十分大きな素数とする。
【００６８】
鍵生成装置１は、セキュリティパラメータ1λに基づいて、例えば以下のKeyGenの処理を行うことにより、暗号化鍵pk=(N,e,G,q,g,y)、復号鍵sk=(d,x)及びハッシュ鍵hk=xを生成する。
【００６９】
KeyGen(1λ)→$(pk,sk,hk):
-セキュリティパラメータ1λに応じて十分大きい素数P,Q及び位数qの巡回群G 及びその生成元gを選ぶ。N=P×Qとし、整数e×d≡1(mod(P-1)(Q-1))なる整数e,dを選ぶ。
【００７０】
-x←$Fq,
-y←gx,
-sk:=(d,x),
-pk:=(N,e,G,q,g,y),
-hk:=x,
-(pk,sk,hk)を出力する。
【００７１】
例えばこのようにして、鍵生成装置１は、乱数x∈Fqを選び、y=gxを計算することにより、暗号化鍵pk=(N,e,G,q,g,y)、復号鍵sk=(d,x)及びハッシュ鍵hk=xを生成する（ステップS１）。
【００７２】
生成された暗号化鍵pk=(N,e,G,q,g,y)は暗号化装置２に送信され、復号鍵sk=(d,x)は復号装置３に送信され、ハッシュ鍵hk=xはハッシュ値計算装置４に送信される。
【００７３】
＜暗号化装置２＞
暗号化装置２は、暗号化鍵pk=(N,e,G,q,g,y)の中のN,e,q,g,yに基づいて、例えば以下のEncの処理を行うことにより、暗号文c=(G1,Y1)を生成する。
Enc(pk,m)→$c:
-φ(N,e,G,q,g,y):=pk,
-r←$Fq,
-G1:=gr,
-Y1:=(memod N)(+)yr,
-c:=(G1,Y1)を出力する。
【００７４】
例えばこのようにして、暗号化装置２は、mをメッセージとして、暗号化鍵pk=(N,e,G,q,g,y)の中のN,e,q,g,yに基づいて、乱数r∈Fqを選び、G1=gr計算し、Y1=(me mod N)(+)yrを計算することにより、暗号文c=(G1,Y1)を生成する（ステップS２）。
【００７５】
生成された暗号文c=(G1,Y1)は、復号装置３及び必要に応じてハッシュ値計算装置４に送信される。
【００７６】
なお、暗号化装置２が、メッセージm1,m2にそれぞれ基づいて生成した異なる２個の暗号を第一暗号文c1=(G1,M1)及び第二暗号文c2=(G2,M2)とする。
【００７７】
＜復号装置３＞
復号装置３は、復号鍵sk=(d,x)及び上記暗号文c=(G1,Y1)に基づいて、例えば以下のEncの処理を行うことにより、メッセージm=(Y1(+)G1x)dmod Nを計算する。
Dec(sk,c)→$m:
-(d,x):=sk,
-(G1,Y1):=c,
-m:=(Y1(+)G1x)dmod Nを出力する。
【００７８】
例えばこのようにして、復号装置３は、復号鍵sk=(d,x)及び暗号文c=(G1,Y1)に基づいて、メッセージm=(Y1(+)G1x)dmod Nを計算する。
【００７９】
＜ハッシュ値計算装置４＞
ハッシュ値計算装置４は、ハッシュ鍵hk=x及び暗号文c=(G1,Y1)に基づいて、例えば以下のHashの処理を行うことにより、ハッシュ値h=Y1(+)G1xを計算する。
Hash(hk,c)→$h:
-x:=hk,
-h:=Y1(+)G1xを出力する。(+)は排他的論理和である。
【００８０】
例えばこのようにして、ハッシュ値計算装置４は、ハッシュ鍵hk=x及び上記暗号文c=(G1,Y1)に基づいて、ハッシュ値h=Y1(+)G1xを計算する（ステップS４）。
【００８１】
ハッシュ値計算装置４は、第一の暗号文c1=(G1,M1)に基づいて生成された第一ハッシュ値と、第二の暗号文c2=(G2,M2)に基づいて生成された第二ハッシュ値とが一致するかどうかを確認することにより、メッセージm1とメッセージm2とが一致するかどかを判定することができる。第一ハッシュ値＝第二ハッシュ値であれば、メッセージm1＝メッセージm2である。
【００８２】
［第四実施形態］
以下、図１を参照して、第四実施形態のハッシング可能暗号システム及び方法の説明をする。第四実施形態のハッシング可能暗号は、共通鍵暗号を使った構成である。言い換えれば、φ,ψを共通鍵暗号とするものである。
【００８３】
第四実施形態のハッシング可能暗号システムは、第一実施形態のハッシング可能暗号システムと同様に、鍵生成装置１、暗号化装置２、復号装置３及びハッシュ値計算装置４を備えている。第四実施形態のハッシング可能暗号システムは、ハッシング可能暗号方法は、以下に述べるステップＳ１からステップＳ４の処理を有する。
【００８４】
＜鍵生成装置１＞
鍵生成装置１は、例えば以下のKeyGenの処理を行うことにより、暗号化鍵pk=(k1,k2)、復号鍵sk=(k1,k2)及びハッシュ鍵hk=k2を生成する。
【００８５】
K1,K2をそれぞれ鍵空間とし、Mを平文空間とし、φ:K1×M→Hとし、φ-1:K1×H→Mとし、ψ:K2×R×H→Cとし、ψ-1:K2×C→Hとする。H,M,H,C,Rは、有限個の元から構成される集合である。ランダム写像とは、入力空間から出力空間への有限個存在する写像の中からランダムに選択された写像のことである。この場合、共通鍵暗号の設定となるので、暗号化を行なう者と復号を行なう者は共に同じ鍵を共有するとする。すなわち暗号化鍵pkと復号鍵skは同じものであり、hkはそれらとは異なる。
【００８６】
KeyGen(1λ)→$(pk,sk,hk):
-セキュリティパラメータ1λに応じて十分大きいブロック暗号φ,ψを選ぶ。
-k1←$K1,
-k2←$K2,
-sk:=(k1,k2),
-pk:=(k1,k2),
-hk:=k2,
-(pk,sk,hk)を出力する。
【００８７】
例えばこのようにして、鍵生成装置１は、乱数k1∈K1を選び、乱数k2∈K2を選ぶことにより、暗号化鍵pk=(k1,k2)、復号鍵sk=(k1,k2)及びハッシュ鍵hk=k2を生成する（ステップＳ１）。
【００８８】
生成された暗号化鍵pk=(k1,k2)は暗号化装置２に送信され、復号鍵sk=(k1,k2)は復号装置３に送信され、ハッシュ鍵hk=k2はハッシュ値計算装置４に送信される。
【００８９】
＜暗号化装置２＞
暗号化装置２は、暗号化鍵pk=(k1,k2)に基づいて、例えば以下のEncの処理を行うことにより、暗号文c=(k2,r,φ(k1,m))を生成する。
Enc(pk,m)→$c:
-(k1,k2):=pk,
-r←$R,
-c:=ψ(k2,r,φ(k1,m))を出力する。
【００９０】
例えばこのようにして、暗号化装置２は、暗号化鍵pk=(k1,k2)に基づいて、乱数r∈Rを選ぶことにより、暗号文c=(k2,r,φ(k1,m))を生成する（ステップＳ２）。
【００９１】
生成された暗号文c=(k2,r,φ(k1,m))は、復号装置３及び必要に応じてハッシュ値計算装置４に送信される。
【００９２】
なお、暗号化装置２が、メッセージm1,m2にそれぞれ基づいて生成した異なる２個の暗号を第一暗号文c1=(k2,r,φ(k1,m1))及び第二暗号文c2=(k2,r,φ(k1,m2))とする。
【００９３】
＜ステップＳ３＞
復号装置３は、復号鍵sk=(k1,k2)及び上記暗号文c=(k2,r,φ(k1,m))に基づいて、例えば以下のDecの処理を行うことにより、メッセージm=φ(k1,ψ-1(k2,c))を計算する。
Dec(sk,c)→$m:
-(k1,k2):=sk,
-m:=φ(k1,ψ-1(k2,c))を出力する。
【００９４】
例えばこのようにして、復号装置３は、復号鍵sk=(k1,k2)及び暗号文c=(k2,r,φ(k1,m))に基づいて、メッセージm=φ(k1,ψ-1(k2,c))を計算する（ステップＳ３）。
【００９５】
＜ハッシュ値計算装置４＞
ハッシュ値計算装置４は、ハッシュ鍵hk=k2及び暗号文c=(k2,r,φ(k1,m))に基づいて、例えば以下のHashの処理を行うことにより、ハッシュ値h=ψ-1(k2,c)を計算する。Hash(hk,c)→$h:
-k2:=hk,
-h:=ψ-1(k2,c)を出力する。
【００９６】
例えばこのようにして、ハッシュ値計算装置４は、ハッシュ鍵hk=k2及び暗号文c=(k2,r,φ(k1,m))に基づいて、ハッシュ値h=ψ-1(k2,c)を計算する（ステップＳ４）。
【００９７】
ハッシュ値計算装置４は、第一の暗号文c1=(G1,M1)に基づいて生成された第一ハッシュ値と、第二の暗号文c2=(G2,M2)に基づいて生成された第二ハッシュ値とが一致するかどうかを確認することにより、メッセージm1とメッセージm2とが一致するかどかを判定することができる。第一ハッシュ値＝第二ハッシュ値であれば、メッセージm1＝メッセージm2である。
【００９８】
［変形例］
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９９】
また、マッチング可能暗号システムの各装置における各処理をコンピュータによって実現する場合、その各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【０１００】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０１】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１０２】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【０１０３】
本発明により、ハッシング鍵を持つ者は暗号文が復号出来なくとも平文のハッシュ値を利用出来る事となる。したがって、ハッシュ値の順序関係の情報を利用することが出来、例えば高速なソーティングやハッシュ表を用いた連想配列などを用いて、平文を纏める処理を高速に行う事が可能となる。
【符号の説明】
【０１０４】
１      鍵生成装置
２      暗号化装置
３      復号装置
４      ハッシュ値計算装置
【図１】
2015215490.tif 000003