(57)【要約】【課題】信頼できる第三者が公開鍵からマッチング鍵を生成できるマッチング可能暗号に関する技術を提供することを目的とする。【解決手段】暗号化装置３が、m∈<α>n×nをメッセージとして、公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成する。マッチング鍵生成装置５が、落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、マッチング鍵mk=(g,y,y1)を生成する。マッチング判定装置６が、鍵生成装置２又はマッチング鍵生成装置５が生成したマッチング鍵mk=(g,y,y1)、第一の暗号文c1=(G1,M1)及び第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定する。【選択図】図１
2015215491.tif 000002
【特許請求の範囲】
【請求項１】
pを素数とし、E(Fp)を位数が素数qで割り切れるFp上の超特異楕円曲線E上定義された群をとし、E(Fp)[q]を位数がqである元により構成されるE(Fp)の部分群とし、αをE(Fp)[q]の生成元とし、<α>をαで生成される巡回群とし、nを２以上の整数とし、<α>n×nを<α>の元を要素とするn×n行列を元とする成分毎の演算を群演算とするアーベル群とし、GAをGA⊆<α>n×nとし、各GAの各成分の指数により構成される行列を元とする非可換環LNC⊆Fqn×nが正則であるとし、g0,g1,g2∈GAの各成分の指数により構成される行列をそれぞれx0,x1,x2∈LNCとし、x0=x1x2としg0=x1g2=g1x2の関係を満たすようにGAとLNCとの間の左べき乗演算及び右べき乗演算が定義されているとして、
乱数t∈LNCを選び、g=αtを生成することにより、共通参照文字列crs=(GA,LNC,g)及び落し戸情報td=tを生成するセットアップ装置と、
上記共通参照文字列crs=( GA,LNC,g)に基づいて、乱数x∈LNCを選び、y=gxを計算し、y1=xgを計算することにより、公開鍵pk=(g,y)、秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成する鍵生成装置と、
m∈<α>n×nをメッセージとして、上記公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成する暗号化装置と、
上記秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する復号装置と、
上記落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、マッチング鍵mk=(g,y,y1)を生成するマッチング鍵生成装置と、
eをペアリング関数とし、上記暗号化装置が生成した、第一の暗号文をc1=(G1,M1)とし、第二の暗号文をc2=(G2,M2)として、上記鍵生成装置又は上記マッチング鍵生成装置が生成したマッチング鍵mk=(g,y,y1)、上記第一の暗号文c1=(G1,M1)及び上記第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定するマッチング判定装置と、
を含むマッチング可能暗号システム。
【請求項２】
pを素数とし、E(Fp)を位数が素数qで割り切れるFp上の超特異楕円曲線E上定義された群をとし、E(Fp)[q]を位数がqである元により構成されるE(Fp)の部分群とし、αをE(Fp)[q]の生成元とし、<α>をαで生成される巡回群とし、nを２以上の整数とし、<α>n×nを<α>の元を要素とする
n×n行列を元とする成分毎の演算を群演算とするアーベル群とし、GAをGA⊆<α>n×nとし、各GAの各成分の指数により構成される行列を元とする非可換環LNC⊆Fqn×nが正則であるとし、g0,g1,g2∈GAの各成分の指数により構成される行列をそれぞれx0,x1,x2∈LNCとし、x0=x1x2としg0=x1g2=g1x2の関係を満たすようにGAとLNCとの間の左べき乗演算及び右べき乗演算が定義されているとして、
セットアップ装置が、乱数t∈LNCを選び、g=αtを生成することにより、共通参照文字列crs=(GA,LNC,g)及び落し戸情報td=tを生成するセットアップステップと、
鍵生成装置が、上記共通参照文字列crs=( GA,LNC,g)に基づいて、乱数x∈LNCを選び、y=gxを計算し、y1=xgを計算することにより、公開鍵pk=(g,y)、秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成する鍵生成ステップと、
暗号化装置が、m∈<α>n×nをメッセージとして、上記公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成する暗号化ステップと、
復号装置が、上記秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する復号ステップと、
マッチング鍵生成装置が、上記落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、マッチング鍵mk=(g,y,y1)を生成するマッチング鍵生成ステップと、
マッチング判定装置が、eをペアリング関数とし、上記暗号化装置が生成した、第一の暗号文をc1=(G1,M1)とし、第二の暗号文をc2=(G2,M2)として、上記鍵生成装置又は上記マッチング鍵生成装置が生成したマッチング鍵mk=(g,y,y1)、上記第一の暗号文c1=(G1,M1)及び上記第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定するマッチング判定ステップと、
を含むマッチング可能暗号方法。
【請求項３】
pを素数とし、E(Fp)を位数が素数qで割り切れるFp上の超特異楕円曲線E上定義された群をとし、E(Fp)[q]を位数がqである元により構成されるE(Fp)の部分群とし、αをE(Fp)[q]の生成元とし、<α>をαで生成される巡回群とし、nを２以上の整数とし、<α>n×nを<α>の元を要素とする
n×n行列を元とする成分毎の演算を群演算とするアーベル群とし、GAをGA⊆<α>n×nとし、各GAの各成分の指数により構成される行列を元とする非可換環LNC⊆Fqn×nが正則であるとし、g0,g1,g2∈GAの各成分の指数により構成される行列をそれぞれx0,x1,x2∈LNCとし、x0=x1x2としg0=x1g2=g1x2の関係を満たすようにGAとLNCとの間の左べき乗演算及び右べき乗演算が定義されているとして、
セットアップ装置は、乱数t∈LNCを選び、g=αtを生成することにより、共通参照文字列crs=(GA,LNC,g)及び落し戸情報td=tを生成するとし、鍵生成装置は、上記共通参照文字列crs=( GA,LNC,g)に基づいて、乱数x∈LNCを選び、y=gxを計算し、y1=xgを計算することにより、公開鍵pk=(g,y)、秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成するとし、暗号化装置が、m∈<α>n×nをメッセージとして、上記公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成するとし、復号装置が、上記秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算するとし、マッチング判定装置が、eをペアリング関数とし、上記暗号化装置が生成した、第一の暗号文をc1=(G1,M1)とし、第二の暗号文をc2=(G2,M2)として、上記マッチング鍵mk=(g,y,y1)、上記第一の暗号文c1=(G1,M1)及び上記第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定するとして、
上記落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、上記マッチング鍵mk=(g,y,y1)を生成するマッチング鍵生成装置。
【請求項４】
請求項３のマッチング鍵生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、マッチング可能暗号技術に特に関する。
【背景技術】
【０００２】
［記法の説明］
・値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 Application”, SCIS 2005 The 2005 Symposium on Cryptography and Information Security, 3D4-3, Maiko Kobe, Japan, Jan. P.25-28, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
マッチング可能暗号において、秘密鍵保有者が誰にもマッチング鍵を与えずに何らかの理由により音信不通となった場合、誰もマッチング鍵を得ることが出来なくなる。
【００１５】
この発明の目的は、信頼できる第三者が公開鍵からマッチング鍵を生成できるマッチング可能暗号システム及び方法並びにマッチング鍵生成装置及びプログラムを提供することである。
【課題を解決するための手段】
【００１６】
この発明の一態様によるマッチング可能暗号システムは、pを素数とし、E(Fp)を位数が素数qで割り切れるFp上の超特異楕円曲線E上定義された群をとし、E(Fp)[q]を位数がqである元により構成されるE(Fp)の部分群とし、αをE(Fp)[q]の生成元とし、<α>をαで生成される巡回群とし、nを２以上の整数とし、<α>n×nを<α>の元を要素とするn×n行列を元とする成分毎の演算を群演算とするアーベル群とし、GAをGA⊆<α>n×nとし、各GAの各成分の指数により構成される行列を元とする非可換環LNC⊆Fqn×nが正則であるとし、g0,g1,g2∈GAの各成分の指数により構成される行列をそれぞれx0,x1,x2∈LNCとし、x0=x1x2としg0=x1g2=g1x2の関係を満たすようにGAとLNCとの間の左べき乗演算及び右べき乗演算が定義されているとして、乱数t∈LNCを選び、g=αtを生成することにより、共通参照文字列crs=(GA,LNC,g)及び落し戸情報td=tを生成するセットアップ装置と、共通参照文字列crs=( GA,LNC,g)に基づいて、乱数x∈LNCを選び、y=gxを計算し、y1=xgを計算することにより、公開鍵pk=(g,y)、秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成する鍵生成装置と、m∈<α>n×nをメッセージとして、公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成する暗号化装置と、秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する復号装置と、落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、マッチング鍵mk=(g,y,y1)を生成するマッチング鍵生成装置と、eをペアリング関数とし、暗号化装置が生成した、第一の暗号文をc1=(G1,M1)とし、第二の暗号文をc2=(G2,M2)として、鍵生成装置又はマッチング鍵生成装置が生成したマッチング鍵mk=(g,y,y1)、第一の暗号文c1=(G1,M1)及び第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定するマッチング判定装置と、を含む。
【発明の効果】
【００１７】
信頼できる第三者が公開鍵からマッチング鍵を生成できる。
【図面の簡単な説明】
【００１８】
【図１】マッチング可能暗号システムの例を説明するためのブロック図。
【発明を実施するための形態】
【００１９】
［落し戸マッチング可能暗号］
信頼できる第三者が公開鍵からマッチング鍵を生成できるマッチング可能暗号のことを、落し戸マッチング可能暗号と呼ぶ。落し戸マッチング可能暗号ではまず信頼できる第三者は共通参照文字列及びそれに付随する落し戸情報を生成し、共通参照文字列は参加者全員が参照できるよう公開し、落し戸情報は秘密とする。その後の手順は共通参照文字列を用いる事以外は通常のマッチング可能暗号と同様である。落し戸マッチング可能暗号は、一般に以下の６つの確率的多項式時間アルゴリズム(Setup, KeyGen, Enc, Dec, Match, MkGen)より構成され、平文空間をMとして下記の構文を持つ。
【００２０】
Setup(1λ)→$(crs,td):セットアップ-セキュリティパラメータ1λを入力とし共通参照文字列crs及び落し戸情報tdを出力する確率的多項式時間アルゴリズム。
【００２１】
KeyGen(crs)→$(pk,sk,mk):鍵生成-共通参照文字列crsを入力とし公開鍵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}を出力する確率的多項式時間アルゴリズム。
【００２５】
MkGen(td,pk)→$mk:マッチング鍵生成-落し戸情報td及び公開鍵pkを入力としマッチング鍵mkを出力する確率的多項式時間アルゴリズム。
【００２６】
(crs,td)←$Setup(1λ), (pk,sk,mk)←$KeyGen(crs), (m;m1,m2)←$M3なるとき、Setup及びKeyGenのランダムテープおよびm,m1,m2を標本空間とする次の３つの確率
Pr[Dec(sk, Enc(pk,m)) = m];
Pr[Match(mk, Enc(pk,m1), Enc(pk,m2)) = (m1=?m2)];
Pr[Match(MkGen(td,pk), Enc(pk,m1), Enc(pk,m2)) = (m1=?m2)]
がいずれもλに関して圧倒的である時、その落し戸マッチング可能暗号(Setup,KeyGen,Enc,Dec,Match,MkGen) は正当であるという。
【００２７】
［trapdoor DDH群］
参考文献１にはマッチング可能暗号を構成可能な特殊なtrapdoor DDH 群の具体的構成が示されている。
【００２８】
〔参考文献１〕F. Hoshino. “A Variant of Diffie-Hellman Problem and How to Prove Independency”, SCIS 2014 The 31st Symposium on Cryptography and Information Security Kagoshima, Japan, Jan. P.21-24, 2014.
【００２９】
落し戸マッチング可能暗号を構成する為、参考文献１のtrapdoor DDH 群の具体的構成に、落し戸情報及び公開鍵からマッチング鍵を構成する方法を付加することを考える。参考文献１のtrapdoor DDH群の具体的構成を要約すると、次のようになる。
【００３０】
・pを十分大きい素数とする。
【００３１】
・EをFp上の超特異楕円曲線とし、E(Fp)を超特異楕円曲線E上の点の中のFp有理点が成す群であり、位数がqで割り切れるとする。E(Fp)[q]を位数がqである元により構成されるE(Fp)の部分群とする。
【００３２】
・αをE(Fp)[q]の生成元とする。<α>をαで生成される巡回群とする。<α>n×nを<α>の元を要素とするn×n行列を元とする成分毎の演算を群演算とするアーベル群とする。
【００３３】
・GA:=GL(n,<α>)⊆<α>n×n。すなわち、GAは<α>n×nの部分集合GL(n,<α>)である。また、GAは、各GAの各成分の指数により構成される行列を元とする非可換環LNC⊆Fqn×nが正則であるという性質を満たすとする。このようなGAをtrapdoor DDH 群とみなす。
【００３４】
・LNC=GL(n,Fq)⊆Fqn×n
・非可換環LNCをGAに関する離散対数行列とみなし、鍵交換が可能である。離散対数行列及び鍵交換が可能の意味については後述する。
【００３５】
・GA⊆<α>n×n→LNC⊆Fqn×nである以下の対応関係について考える。
【００３６】
【数１】
2015215491.tif 000003
【００３７】
h:=(αrij)に対してr:=(rij)を離散対数と呼ぶ。また、GAに対して、LNCを離散対数行列と呼ぶ。LNCは、各GAの各成分の指数により構成される行列を元とする非可換環LNCであると言える。
【００３８】
・hをαrと書く。
【００３９】
・rがn×n単位行列の時はαrをInと書く。
【００４０】
・GA⊆<α>n×nにおける演算の例は以下の通りである。以下では、演算を乗法表記している。白抜きのGはGAのことを意味する。
【００４１】
【数２】
2015215491.tif 000004
【００４２】
・GA上で自然なペアリングが定義される。ペアリングについても後述する。
【００４３】
［右冪乗・左冪乗］
・LNCとGAとの間の対応。白抜きのLはLNCのことを意味する。
g0,g1,g2∈GAの各成分の指数により構成される行列をそれぞれx0,x1,x2∈LNCとし、x0=x1x2∈LNCとしg0=x1g2=g1x2∈GAの関係を満たすようにGAとLNCとの間の左べき乗演算及び右べき乗演算が定義されているとする。
【００４４】
・LNCは非可換環であり、右冪乗・左冪乗を計算するための確率的多項式時間アルゴリズが存在するとする。
【００４５】
・以下、右冪乗・左冪乗の具体例について説明する。
【００４６】
x,gを以下のように定義する。
【００４７】
【数３】
2015215491.tif 000005
【００４８】
このとき、gx,gxを乗法表記すると以下のようになる。xIn,Inxについても以下のようになる。
【００４９】
【数４】
2015215491.tif 000006
【００５０】
［鍵交換について］
g∈GAとして、以下の関係x(gy)=(gy)xが成立するとする。
【００５１】
【数５】
2015215491.tif 000007
【００５２】
・離散対数上の行列乗算と考える(x(αy)=αxy,(αy)x=αyx)
【００５３】
［ペアリングについて］
自然なペアリングe:<α>n×n×<α>n×n→μqn×nが定義されるとする。μqは所定の巡回群である。
【００５４】
・離散対数上の行列乗算と考える(e(αx,αy)=ξxy)。ξ=e(α,α)である。
【００５５】
g,hを以下のように定義すると、e(g,h)は例えば以下のようになる。
【００５６】
【数６】
2015215491.tif 000008
【００５７】
［実施形態］
以下、図面を参照して、マッチング可能暗号システム及び方法並びにマッチング鍵生成装置の実施形態を説明する。
【００５８】
p,qのそれぞれは、素数である。例えば、p,qは、十分に大きい素数とする。要求されるセキュリティのレベルが高くない場合には、p,qは、十分に大きい素数でなくてもよい。Fp,Fqは、それぞれ素数p,qに対する有限体である。pは、セキュリティパラメータ1λに応じて例えば決定される。
【００５９】
＜セットアップ装置１＞
セットアップ装置１は、セキュリティパラメータ1λに基づいて、例えば以下のSetupの処理を行うことにより共通参照文字列crs及び落し戸情報tdを生成する。
【００６０】
Setup(1λ)→$(crs,td):
-セキュリティパラメータ1λに応じて十分大きい素数pを選び、位数が十分大きい素数qで割り切れるFp上の超特異楕円曲線Eを選び、E(Fp)[q]の適当な生成元αを選ぶ。
-適当なn⊆N,n≧2を選ぶ。Nは整数の集合である。
-GA:=GL(n,<α>)⊆<α>n×nとする。
-LNC:=GL(n,Fq)⊆Fqn×nとする。
-t←$GL(n,Fq),
-g←$αt,
-crs:=(GA,LNC,g),
-td:=t,
-(crs,td)を出力する。
【００６１】
例えばこのようにして、セットアップ装置１は、乱数t∈LNCを選び、g=αtを生成することにより、共通参照文字列crs=(GA,LNC,g)及び落し戸情報td=tを生成する（ステップＳ１）。
【００６２】
生成された共通参照文字列crs=(GA,LNC,g)は全ての装置に公開され、落し戸情報td=tはマッチング鍵生成装置５に送信される。
【００６３】
＜鍵生成装置２＞
鍵生成装置は、共通参照文字列crs=( GA,LNC,g)に基づいて、例えば以下のKeygenの処理を行うことにより秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成する。
【００６４】
KeyGen(crs)→$(pk,sk,mk):
(GA,LNC,g):=crs,
-x←$LNC,
-y:=gx,
-y1:=xg,
-sk:=x,
-pk:=(g,y),
-mk:=(g,y,y1),
-(pk,sk,mk)を出力する。
【００６５】
例えばこのようにして、鍵生成装置２は、共通参照文字列crs=(GA,LNC,g)に基づいて、乱数x∈LNCを選び、y=gxを計算し、y1=xgを計算することにより、公開鍵pk=(g,y)、秘密鍵sk=x及びマッチング鍵mk=(g,y,y1)を生成する（ステップＳ２）。
【００６６】
生成された秘密鍵sk=xは復号装置４に送信され、生成された公開鍵pk=(g,y)はマッチング鍵生成装置５に送信され、生成されたマッチング鍵mk=(g,y,y1)はマッチング判定装置６に送信される。
【００６７】
＜暗号化装置３＞
暗号化装置３は、公開鍵pk=(g,y)に基づいて、例えば以下のEncの処理を行うことにより暗号文c=(G,M)を生成する。
【００６８】
Enc(pk,m)→c:
-(g,y):=pk,
-r←$LNC,
-G:=rg,
-M:=m・ry,
-c:=(G.M)を出力する。
【００６９】
例えばこのようにして、暗号化装置３は、m∈<α>n×nをメッセージとして、公開鍵pk=(g,y)に基づいて、乱数r∈LNCを選び、G=rg計算し、M=m・ryを計算することにより、暗号文c=(G,M)を生成する（ステップＳ３）。
【００７０】
生成された暗号文c=(G,M)は、復号装置４及び必要に応じてマッチング判定装置６に送信される。
【００７１】
なお、暗号化装置３は、同じメッセージmcに基づいて異なる２個の暗号文を生成するとする。第一の暗号文をc1=(G1,M1)とし、第二の暗号文をc2=(G2,M2)とする。
【００７２】
＜復号装置４＞
復号装置４は、秘密鍵sk=x及び暗号文c=(G,M)に基づいて、例えば以下のDecの処理を行うことによりメッセージm=M/Gxを計算する暗号文c=(G,M)を生成する。
【００７３】
Dec(sk,c)→$m:
-x:=sk,
-(G;M):=c,
-m:=M/Gxを出力する。
【００７４】
例えばこのようにして、復号装置４は、秘密鍵sk=x及び暗号文c=(G,M)に基づいて、メッセージm=M/Gxを計算する（ステップＳ４）。
【００７５】
＜マッチング鍵生成装置５＞
マッチング鍵生成装置５は、落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、例えば以下のMkGenの処理を行うことによりマッチング鍵mk=(g,y,y1)を生成する。
【００７６】
MkGen(td,pk)→$mk:
-t:=td,
-(g,y):=pk,
-y1:=t^(-1)yt,
-mk:=(g,y,y1)を出力する。
【００７７】
例えばこのようにして、マッチング鍵生成装置５は、落し戸情報td=t及び公開鍵pk=(g,y)に基づいて、y1=t^(-1)ytを生成することにより、マッチング鍵mk=(g,y,y1)を生成する（ステップＳ５）。
【００７８】
生成されたマッチング鍵mk=(g,y,y1)は、マッチング判定装置６に送信される。
【００７９】
このように、マッチング判定装置６が、鍵生成装置２が生成したマッチング鍵mk=(g,y,y1)を紛失したとしても、マッチング鍵生成装置５がマッチング鍵mk=(g,y,y1)を生成することができる。ここでは説明を省略するが、鍵生成装置２が生成したマッチング鍵mk=(g,y,y1)とマッチング鍵生成装置５が生成したマッチング鍵mk=(g,y,y1)とは一致する。
【００８０】
＜マッチング判定装置６＞
マッチング判定装置６は、マッチング鍵mk=(g,y,y1)、第一の暗号文c1=(G1,M1)及び第二の暗号文c2=(G2,M2)に基づいて、例えば以下のMatchの処理を行うことによりe(M1/M2,g)とe(M1/M2,y1)とが一致するか判定する。マッチング鍵mk=(g,y,y1)は、鍵生成装置２が生成したものであってもよいし、マッチング鍵生成装置５が生成したものであってもよい。
【００８１】
Match(m,c1,c2)→b:
-(g,y,y1):=mk,
-(G1,M1):=c1,
-(G2,M2):=c2,
-e(M1/M2,g)=?e(G1/G2,y1)を出力する。
【００８２】
例えばこのようにして、マッチング判定装置６は、鍵生成装置２又はマッチング鍵生成装置５が生成したマッチング鍵mk=(g,y,y1)、第一の暗号文c1=(G1,M1)及び第二の暗号文c2=(G2,M2)に基づいて、e(M1/M2,g)とe(M1/M2,y1)とが一致するか判定する（ステップＳ６）。
【００８３】
［変形例］
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８４】
また、マッチング可能暗号システムの各装置における各処理をコンピュータによって実現する場合、その各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００８５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８６】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００８７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００８８】
１      セットアップ装置
２      鍵生成装置
３      暗号化装置
４      復号装置
５      マッチング鍵生成装置
６      マッチング判定装置
【図１】
2015215491.tif 000009