(57)【特許請求の範囲】
【請求項１】
所定の基底Ｂ及び所定の基底Ｂ＊を用いて処理を行う暗号システムであり、
複数のインデックスｊのうちの１つ以上のインデックスｊについての送信側ベクトルｔｊであって、前記基底Ｂにおける所定の基底ベクトルｂｉｎｄｅｘの係数に、インデックスｊに予め割り当てられた情報Ｊを設定し、前記基底Ｂにおける他の基底ベクトルｂａｔｔの係数に、インデックスｊについてのパラメータΦｊを設定した送信側ベクトルｔｊを生成する送信装置と、
複数のインデックスｊ’のうちの１つ以上のインデックスｊ’についての受信側ベクトルｒｊ’であって、前記基底ベクトルｂｉｎｄｅｘに対応する前記基底Ｂ＊における基底ベクトルｂ＊ｉｎｄｅｘの係数に、インデックスｊ’に対応するインデックスｊに予め割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂａｔｔに対応する前記基底Ｂ＊における基底ベクトルｂ＊ａｔｔの係数に、インデックスｊ’についてのパラメータΨｊ’を設定した受信側ベクトルｒｊ’を用いて、インデックスｊについての前記送信側ベクトルｔｊと前記インデックスｊに対応するインデックスｊ’についての前記受信側ベクトルｒｊ’とに対して、対応する基底ベクトル毎のペアリング演算の積を計算する受信装置と
を備えることを特徴とする暗号システム。
【請求項２】
前記送信装置は、暗号文ｃｔを生成する暗号化装置であり、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の整数ｔを前記インデックスｊとし、整数ｔについての属性情報ｘｔを前記インデックスｊについての前記パラメータΦｊとして、１つ以上の整数ｔについて、前記基底ベクトルｂｉｎｄｅｘの係数に、整数ｔに割り当てられた情報Ｊを設定し、前記基底ベクトルｂａｔｔの係数に、整数ｔについての属性情報ｘｔを設定した暗号ベクトルｃｔを前記送信側ベクトルｔｊとして含む暗号文ｃｔを生成し、
前記受信装置は、前記暗号文ｃｔを復号する復号装置であり、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の整数ｉを前記インデックスｊ’とし、整数ｉについての述語情報ｖｉを前記インデックスｊ’についての前記パラメータΨｊ’として、各整数ｉについて、前記基底ベクトルｂ＊ｉｎｄｅｘの係数に、整数ｉに対応する整数ｔに割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂ＊ａｔｔの係数に、整数ｉについての述語情報ｖｉを設定した鍵ベクトルｋ＊ｉを前記受信側ベクトルｒｊ’として用いて、前記各整数ｉについて、その整数ｉについての鍵ベクトルｋ＊ｉと、その整数ｉに対応する整数ｔについての暗号ベクトルｃｔとに対して、対応する基底ベクトル毎のペアリング演算の積を計算する
ことを特徴とする請求項１に記載の暗号システム。
【請求項３】
前記暗号システムは、所定の基底Ｂ０及び所定の基底Ｂ＊０と、所定の基底Ｂ及び所定の基底Ｂ＊とを用いて処理を行い、
前記送信装置は、暗号ベクトルｃ０及びｔ＝１，．．．，ｄの１つ以上の整数ｔについての暗号ベクトルｃｔであって、数１に示す暗号ベクトルｃ０及び暗号ベクトルｃｔを含む暗号文ｃｔを生成し、
前記受信装置は、ｉ＝０，．．．，Ｌの各整数ｉについての鍵ベクトルｋ＊ｉであって、数２に示す鍵ベクトルｋ＊ｉと、前記暗号ベクトルｃｔとについて、数３を計算する
ことを特徴とする請求項２に記載の暗号システム。
【数１】
0005680007.tif 000125
【数２】
0005680007.tif 000126
【数３】
0005680007.tif 000127
【請求項４】
前記送信装置は、暗号文ｃｔを生成する暗号化装置であり、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の整数ｉを前記インデックスｊとし、整数ｉについての述語情報ｖｉを前記インデックスｊについての前記パラメータΦｊとして、各整数ｉについて、前記基底ベクトルｂｉｎｄｅｘの係数に、整数ｉに割り当てられた情報Ｊを設定し、前記基底ベクトルｂａｔｔの係数に、整数ｉについての述語情報ｖｉを設定した暗号ベクトルｃｉを前記送信側ベクトルｔｊとして含む暗号文ｃｔを生成し、
前記受信装置は、前記暗号文ｃｔを復号する復号装置であり、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の整数ｔを前記インデックスｊ’とし、整数ｔについての属性情報ｘｔを前記インデックスｊ’についての前記パラメータΨｊ’として、１つ以上の整数ｔについて、前記基底ベクトルｂ＊ｉｎｄｅｘの係数に、整数ｔに対応する整数ｉに割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂ＊ａｔｔの係数に、整数ｔについての属性情報ｘｔを設定した鍵ベクトルｋ＊ｔを前記受信側ベクトルｒｊ’として用いて、前記各整数ｉについて、その整数ｉについての暗号ベクトルｃｉと、その整数ｉに対応する整数ｔについての鍵ベクトルｋ＊ｔとに対して、対応する基底ベクトル毎のペアリング演算の積を計算する
ことを特徴とする請求項１に記載の暗号システム。
【請求項５】
前記暗号システムは、所定の基底Ｂ０及び所定の基底Ｂ＊０と、所定の基底Ｂ及び所定の基底Ｂ＊とを用いて処理を行い、
前記送信装置は、ｉ＝０，．．．，Ｌの各整数ｉについての暗号ベクトルｃｉであって、数４に示す暗号ベクトルｃｉを含む暗号文ｃｔを生成し、
前記受信装置は、鍵ベクトルｋ＊０及びｔ＝１，．．．，ｄの１つ以上の整数ｔについての鍵ベクトルｋ＊ｔであって、数５に示す鍵ベクトルｋ＊０及び鍵ベクトルｋ＊ｔと、前記暗号ベクトルｃｉとについて、数６を計算する
ことを特徴とする請求項４に記載の暗号システム。
【数４】
0005680007.tif 000128
【数５】
0005680007.tif 000129
【数６】
0005680007.tif 000130
【請求項６】
前記送信装置は、暗号文ｃｔを生成する暗号化装置であり、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の整数ｉを前記インデックスｊとし、整数ｉについての属性情報ｘｉを前記インデックスｊについての前記パラメータΦｊとして、各整数ｉについて、前記基底ベクトルｂｉｎｄｅｘの係数に、整数ｉに割り当てられた情報Ｊを設定し、前記基底ベクトルｂａｔｔの係数に、整数ｉについての属性情報ｘｉを設定した暗号ベクトルｃｉを前記送信側ベクトルｔｊとして含む暗号文ｃｔを生成し、
前記受信装置は、前記暗号文ｃｔを復号する復号装置であり、前記整数ｉを前記インデックスｊ’とし、整数ｉについての述語情報ｖｉを前記インデックスｊ’についての前記パラメータΨｊ’として、各整数ｉについて、前記基底ベクトルｂ＊ｉｎｄｅｘの係数に、整数ｉに割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂ＊ａｔｔの係数に、整数ｉについての述語情報ｖｉを設定した鍵ベクトルｋ＊ｉを前記受信側ベクトルｒｊ’として用いて、前記各整数ｉについて、その整数ｉについての鍵ベクトルｋ＊ｉと暗号ベクトルｃｔとに対して、対応する基底ベクトル毎のペアリング演算の積を計算する
ことを特徴とする請求項１に記載の暗号システム。
【請求項７】
前記暗号システムは、所定の基底Ｂ０及び所定の基底Ｂ＊０と、所定の基底Ｂ及び所定の基底Ｂ＊とを用いて処理を行い、
前記送信装置は、ｉ＝０，．．．，Ｌの各整数ｉについての暗号ベクトルｃｉの和である暗号ベクトルｃ１であって、数７に示す暗号ベクトルｃ１を含む暗号文ｃｔを生成し、
前記受信装置は、前記各整数ｉについての鍵ベクトルｋ＊ｉの和である鍵ベクトルｋ＊Ｌ，ｄｅｃであって、数８に示す鍵ベクトルｋ＊Ｌ，ｄｅｃと、前記暗号ベクトルｃ１とについて、対応する基底ベクトル毎のペアリング演算の積を計算する
ことを特徴とする請求項６に記載の暗号システム。
【数７】
0005680007.tif 000131
【数８】
0005680007.tif 000132
【請求項８】
前記送信装置は、署名データｓｉｇを生成する署名装置であり、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の整数ｔを前記インデックスｊとし、整数ｔについての属性情報ｘｔを前記インデックスｊについての前記パラメータΦｊとして、１つ以上の整数ｔについて、前記基底ベクトルｂｉｎｄｅｘの係数に、整数ｔに割り当てられた情報Ｊを設定し、前記基底ベクトルｂａｔｔの係数に、整数ｔについての属性情報ｘｔを設定した鍵ベクトルｋ＊ｔを用いて、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについて、整数ｉに対応する整数ｔについての鍵ベクトルｋ＊ｔを含めた署名要素ｓｉを前記送信側ベクトルｔｊとして含む署名データｓｉｇを生成し、
前記受信装置は、前記署名データｓｉｇを検証する検証装置であり、前記整数ｉを前記インデックスｊ’とし、整数ｉについての述語情報ｖｉを前記インデックスｊ’についての前記パラメータΨｊ’として、各整数ｉについて、前記基底ベクトルｂ＊ｉｎｄｅｘの係数に、整数ｉに対応する整数ｔに割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂ＊ａｔｔの係数に、整数ｉについての述語情報ｖｉを設定した検証要素ｃｉを前記受信側ベクトルｒｊ’として用いて、前記各整数ｉについて、その整数ｉについての署名要素ｓｉと検証要素ｃｉとに対して、対応する基底ベクトル毎のペアリング演算の積を計算する
ことを特徴とする請求項１に記載の暗号システム。
【請求項９】
前記暗号システムは、所定の基底Ｂ０及び所定の基底Ｂ＊０と、所定の基底Ｂ及び所定の基底Ｂ＊と、所定の基底Ｂｄ＋１及び所定の基底Ｂ＊ｄ＋１とを用いて処理を行い、
前記送信装置は、鍵ベクトルｋ＊０とｔ＝１，．．．，ｄの１つ以上の整数ｔについての鍵ベクトルｋ＊ｔと鍵ベクトルｄ＋１，１と鍵ベクトルｄ＋１，２とであって、数９に示す鍵ベクトルｋ＊０と鍵ベクトルｋ＊ｔと鍵ベクトルｄ＋１，１と鍵ベクトルｄ＋１，２とを用いて、ｉ＝０，．．．，Ｌ＋１の各整数ｉについての署名要素ｓｉであって、数１０に示す署名要素ｓｉを含む署名データｓｉｇを生成し、
前記受信装置は、前記各整数ｉについての検証要素ｃｉであって、数１１に示す検証要素ｃｉと、前記署名要素ｓｉとについて、数１２を計算する
ことを特徴とする請求項８に記載の暗号システム。
【数９】
0005680007.tif 000133
【数１０】
0005680007.tif 000134
【数１１】
0005680007.tif 000135
【数１２】
0005680007.tif 000136
【請求項１０】
所定の基底Ｂ及び所定の基底Ｂ＊を用いて処理を行う暗号方法であり、
送信装置が、複数のインデックスｊのうちの１つ以上のインデックスｊについての送信側ベクトルｔｊであって、前記基底Ｂにおける所定の基底ベクトルｂｉｎｄｅｘの係数に、インデックスｊに予め割り当てられた情報Ｊを設定し、前記基底Ｂにおける他の基底ベクトルｂａｔｔの係数に、インデックスｊについてのパラメータΦｊを設定した送信側ベクトルｔｊを生成する送信工程と、
受信装置が、複数のインデックスｊ’のうちの１つ以上のインデックスｊ’についての受信側ベクトルｒｊ’であって、前記基底ベクトルｂｉｎｄｅｘに対応する前記基底Ｂ＊における基底ベクトルｂ＊ｉｎｄｅｘの係数に、インデックスｊ’に対応するインデックスｊに予め割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂａｔｔに対応する前記基底Ｂ＊における基底ベクトルｂ＊ａｔｔの係数に、インデックスｊ’についてのパラメータΨｊ’を設定した受信側ベクトルｒｊ’を用いて、インデックスｊについての前記送信側ベクトルｔｊと前記インデックスｊに対応するインデックスｊ’についての前記受信側ベクトルｒｊ’とに対して、対応する基底ベクトル毎のペアリング演算の積を計算する受信工程と
を備えることを特徴とする暗号方法。
【請求項１１】
所定の基底Ｂ及び所定の基底Ｂ＊を用いて処理を行う暗号プログラムであり、
複数のインデックスｊのうちの１つ以上のインデックスｊについての送信側ベクトルｔｊであって、前記基底Ｂにおける所定の基底ベクトルｂｉｎｄｅｘの係数に、インデックスｊに予め割り当てられた情報Ｊを設定し、前記基底Ｂにおける他の基底ベクトルｂａｔｔの係数に、インデックスｊについてのパラメータΦｊを設定した送信側ベクトルｔｊを生成する送信装置、
又は
複数のインデックスｊ’のうちの１つ以上のインデックスｊ’についての受信側ベクトルｒｊ’であって、前記基底ベクトルｂｉｎｄｅｘに対応する前記基底Ｂ＊における基底ベクトルｂ＊ｉｎｄｅｘの係数に、インデックスｊ’に対応するインデックスｊに予め割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂａｔｔに対応する前記基底Ｂ＊における基底ベクトルｂ＊ａｔｔの係数に、インデックスｊ’についてのパラメータΨｊ’を設定した受信側ベクトルｒｊ’を用いて、インデックスｊについての前記送信側ベクトルｔｊと前記インデックスｊに対応するインデックスｊ’についての前記受信側ベクトルｒｊ’とに対して、対応する基底ベクトル毎のペアリング演算の積を計算する受信装置
としてコンピュータを機能させることを特徴とする暗号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開パラメータの再発行をすることなく、属性カテゴリの追加が可能な暗号システムに関するものである。
【背景技術】
【０００２】
非特許文献２９には、関数型暗号方式についての記載がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｂｅｉｍｅｌ，  Ａ．，  Ｓｅｃｕｒｅ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ  ａｎｄ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ．  ＰｈＤ  Ｔｈｅｓｉｓ，  Ｉｓｒａｅｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ，Ｔｅｃｈｎｉｏｎ，  Ｈａｉｆａ，  Ｉｓｒａｅｌ，  １９９６．
【非特許文献２】Ｂｅｔｈｅｎｃｏｕｒｔ，  Ｊ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ：  ２００７  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，  ｐｐ．  ３２１−３３４．  ＩＥＥＥ  Ｐｒｅｓｓ  （２００７）
【非特許文献３】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．：  Ｅｆｆｉｃｉｅｎｔ  ｓｅｌｅｃｔｉｖｅ−ＩＤ  ｓｅｃｕｒｅ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．  Ｉｎ：  Ｃａｃｈｉｎ，Ｃ．，  Ｃａｍｅｎｉｓｃｈ，  Ｊ．  （ｅｄｓ．）  ＥＵＲＯＣＲＹＰＴ  ２００４．  ＬＮＣＳ，  ｖｏｌ．  ３０２７，  ｐｐ．  ２２３−２３８．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献４】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．：  Ｓｅｃｕｒｅ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．  Ｉｎ：  Ｆｒａｎｋｌｉｎ，  Ｍ．Ｋ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００４．  ＬＮＣＳ，  ｖｏｌ．  ３１５２，  ｐｐ．  ４４３−４５９．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献５】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．，  Ｇｏｈ，  Ｅ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｃｏｎｓｔａｎｔ  ｓｉｚｅ  ｃｉｐｈｅｒｔｅｘｔ．  Ｉｎ：  Ｃｒａｍｅｒ，Ｒ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００５．  ＬＮＣＳ，  ｖｏｌ．  ３４９４，  ｐｐ．  ４４０−４５６．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００５）
【非特許文献６】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．，  Ｓｈａｃｈａｍ，  Ｈ．：  Ｓｈｏｒｔ  ｇｒｏｕｐ  ｓｉｇｎａｔｕｒｅｓ．  Ｉｎ：  Ｆｒａｎｋｌｉｎ，  Ｍ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００４．  ＬＮＣＳ，  ｖｏｌ．３１５２，  ｐｐ．  ４１−５５．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献７】Ｂｏｎｅｈ，  Ｄ．，  Ｆｒａｎｋｌｉｎ，  Ｍ．：  Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ．  Ｉｎ：  Ｋｉｌｉａｎ，  Ｊ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００１．ＬＮＣＳ，  ｖｏｌ．  ２１３９，  ｐｐ．  ２１３−２２９．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００１）
【非特許文献８】Ｂｏｎｅｈ，  Ｄ．，  Ｈａｍｂｕｒｇ，  Ｍ．：  Ｇｅｎｅｒａｌｉｚｅｄ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ａｎｄ  ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ．  Ｉｎ：  Ｐｉｅｐｒｚｙｋ，  Ｊ．  （ｅｄ．）  ＡＳＩＡＣＲＹＰＴ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５３５０，  ｐｐ．  ４５５−４７０．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献９】Ｂｏｎｅｈ，  Ｄ．，  Ｋａｔｚ，  Ｊ．，  Ｉｍｐｒｏｖｅｄ  ｅｆｆｉｃｉｅｎｃｙ  ｆｏｒ  ＣＣＡ−ｓｅｃｕｒｅ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｂｕｉｌｔ  ｕｓｉｎｇ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  ＲＳＡ−ＣＴ  ２００５，  ＬＮＣＳ，  Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ  （２００５）
【非特許文献１０】Ｂｏｎｅｈ，  Ｄ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｃｏｎｊｕｎｃｔｉｖｅ，  ｓｕｂｓｅｔ，  ａｎｄ  ｒａｎｇｅ  ｑｕｅｒｉｅｓ  ｏｎ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ．  Ｉｎ：  Ｖａｄｈａｎ，  Ｓ．Ｐ．  （ｅｄ．）  ＴＣＣ  ２００７．  ＬＮＣＳ，  ｖｏｌ．  ４３９２，  ｐｐ．  ５３５−５５４．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００７）
【非特許文献１１】Ｂｏｙｅｎ，  Ｘ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ａｎｏｎｙｍｏｕｓ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  （ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ）．  Ｉｎ：  Ｄｗｏｒｋ，  Ｃ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００６．  ＬＮＣＳ，  ｖｏｌ．  ４１１７，  ｐｐ．  ２９０−３０７．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００６）
【非特許文献１２】Ｃａｎｅｔｔｉ，  Ｒ．，  Ｈａｌｅｖｉ  Ｓ．，  Ｋａｔｚ  Ｊ．：  Ｃｈｏｓｅｎ−ｃｉｐｈｅｒｔｅｘｔ  ｓｅｃｕｒｉｔｙ  ｆｒｏｍ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  ＥＵＲＯＣＲＹＰＴ  ２００４，  ＬＮＣＳ，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献１３】Ｃｈａｓｅ，  Ｍ．：  Ｍｕｌｔｉ−ａｕｔｈｏｒｉｔｙ  ａｔｔｒｉｂｕｔｅ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  ＴＣＣ，  ＬＮＣＳ，  ｐｐ．  ５１５−５３４，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００７）．
【非特許文献１４】Ｃｈａｓｅ，  Ｍ．  ａｎｄ  Ｃｈｏｗ，  Ｓ．：  Ｉｍｐｒｏｖｉｎｇ  ｐｒｉｖａｃｙ  ａｎｄ  ｓｅｃｕｒｉｔｙ  ｉｎ  ｍｕｌｔｉ−ａｕｔｈｏｒｉｔｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ，  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ，  ｐｐ．  １２１−１３０，  ＡＣＭ  （２００９）．
【非特許文献１５】Ｃｏｃｋｓ，  Ｃ．：  Ａｎ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｑｕａｄｒａｔｉｃ  ｒｅｓｉｄｕｅｓ．  Ｉｎ：  Ｈｏｎａｒｙ，  Ｂ．  （ｅｄ．）  ＩＭＡ  Ｉｎｔ．  Ｃｏｎｆ．  ＬＮＣＳ，  ｖｏｌ．  ２２６０，  ｐｐ．  ３６０−３６３．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００１）
【非特許文献１６】Ｇｅｎｔｒｙ，  Ｃ．：  Ｐｒａｃｔｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．  Ｉｎ：  Ｖａｕｄｅｎａｙ，  Ｓ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００６．  ＬＮＣＳ，  ｖｏｌ．  ４００４，  ｐｐ．  ４４５−４６４．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００６）
【非特許文献１７】Ｇｅｎｔｒｙ，  Ｃ．，  Ｈａｌｅｖｉ，  Ｓ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｐｏｌｙｎｏｍｉａｌｌｙ  ｍａｎｙ  ｌｅｖｅｌｓ．  Ｉｎ：  Ｒｅｉｎｇｏｌｄ，  Ｏ．  （ｅｄ．）  ＴＣＣ  ２００９．  ＬＮＣＳ，  ｖｏｌ．  ５４４４，  ｐｐ．  ４３７−４５６．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００９）
【非特許文献１８】Ｇｅｎｔｒｙ，  Ｃ．，  Ｓｉｌｖｅｒｂｅｒｇ，  Ａ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ＩＤ−ｂａｓｅｄ  ｃｒｙｐｔｏｇｒａｐｈｙ．  Ｉｎ：  Ｚｈｅｎｇ，  Ｙ．  （ｅｄ．）  ＡＳＩＡＣＲＹＰＴ  ２００２．  ＬＮＣＳ，ｖｏｌ．  ２５０１，  ｐｐ．  ５４８−５６６．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００２）
【非特許文献１９】Ｇｏｙａｌ，  Ｖ．，  Ｐａｎｄｅｙ，  Ｏ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｆｉｎｅ−ｇｒａｉｎｅｄ  ａｃｃｅｓｓ  ｃｏｎｔｒｏｌ  ｏｆ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ．  Ｉｎ：  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００６，  ｐｐ．  ８９−９８，  ＡＣＭ  （２００６）
【非特許文献２０】Ｋａｔｚ，  Ｊ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｓｕｐｐｏｒｔｉｎｇ  ｄｉｓｊｕｎｃｔｉｏｎｓ，  ｐｏｌｙｎｏｍｉａｌ  ｅｑｕａｔｉｏｎｓ，  ａｎｄ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔｓ．  Ｉｎ：  Ｓｍａｒｔ，  Ｎ．Ｐ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ４９６５，  ｐｐ．  １４６−１６２．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献２１】Ｌｅｗｋｏ，  Ａ．，  Ｏｋａｍｏｔｏ，  Ｔ．，  Ｓａｈａｉ，  Ａ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｆｕｌｌｙ  ｓｅｃｕｒｅ  ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ：  Ａｔｔｒｉｂｕｔｅｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  （ｈｉｅｒａｒｃｈｉｃａｌ）  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ  ｅｎｃｒｙｐｔｉｏｎ，  ＥＵＲＯＣＲＹＰＴ  ２０１０．  ＬＮＣＳ，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１０）
【非特許文献２２】Ｌｅｗｋｏ，  Ａ．Ｂ．，Ｗａｔｅｒｓ，  Ｂ．：  Ｎｅｗ  ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ｄｕａｌ  ｓｙｓｔｅｍ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｆｕｌｌｙ  ｓｅｃｕｒｅ  ＨＩＢＥ  ｗｉｔｈ  ｓｈｏｒｔ  ｃｉｐｈｅｒｔｅｘｔｓ．  Ｉｎ：  Ｍｉｃｃｉａｎｃｉｏ，  Ｄ．  （ｅｄ．）  ＴＣＣ  ２０１０．  ＬＮＣＳ，  ｖｏｌ．  ５９７８，  ｐｐ．  ４５５−４７９．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１０）
【非特許文献２３】Ｌｅｗｋｏ，  Ａ．Ｂ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｄｅｃｅｎｔｒａｌｉｚｉｎｇ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ，  ｔｈｅ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｅｕｒｏｃｒｙｐｔ  ２０１１，  ＬＮＣＳ，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）．
【非特許文献２４】Ｌｅｗｋｏ，  Ａ．Ｂ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｕｎｂｏｕｎｄｅｄ  ＨＩＢＥ  ａｎｄ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ，  ｔｈｅ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｅｕｒｏｃｒｙｐｔ  ２０１１，  ＬＮＣＳ，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）．
【非特許文献２５】Ｈ．  Ｌｉｎ，  Ｚ．  Ｃａｏ，  Ｘ．  Ｌｉａｎｇ，  ａｎｄ  Ｊ．  Ｓｈａｏ．：  Ｓｅｃｕｒｅ  ｔｈｒｅｓｈｏｌｄ  ｍｕｌｔｉ  ａｕｔｈｏｒｉｔｙ  ａｔｔｒｉｂｕｔｅ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ａ  ｃｅｎｔｒａｌ  ａｕｔｈｏｒｉｔｙ，  ＩＮＤＯＣＲＹＰＴ，  ＬＮＣＳ，  ｖｏｌ．  ５３６５，  ｐｐ．  ４２６−４３６，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）．
【非特許文献２６】Ｓ．  Ｍ¨ｕｌｌｅｒ，  Ｓ．  Ｋａｔｚｅｎｂｅｉｓｓｅｒ，  ａｎｄ  Ｃ．  Ｅｃｋｅｒｔ．；  Ｏｎ  ｍｕｌｔｉ−ａｕｔｈｏｒｉｔｙ  ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ，  Ｂｕｌｌ．  Ｋｏｒｅａｎ  Ｍａｔｈ  Ｓｏｃ．  ４６，  Ｎｏ．４，  ｐｐ．  ８０３−８１９  （２００９）．
【非特許文献２７】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ．  Ｉｎ：  Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｐａｔｅｒｓｏｎ，  Ｋ．Ｇ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５２０９，  ｐｐ．  ５７−７４，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献２８】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ，  Ｉｎ：  ＡＳＩＡＣＲＹＰＴ  ２００９，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００９）
【非特許文献２９】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｆｕｌｌｙ  ｓｅｃｕｒｅ  ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｇｅｎｅｒａｌ  ｒｅｌａｔｉｏｎｓ  ｆｒｏｍ  ｔｈｅ  ｄｅｃｉｓｉｏｎａｌ  ｌｉｎｅａｒ  ａｓｓｕｍｐｔｉｏｎ．  Ｉｎ：  Ｒａｂｉｎ，  Ｔ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２０１０．  ＬＮＣＳ，  ｖｏｌ．  ６２２３，  ｐｐ．  １９１−２０８．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１０）．  Ｆｕｌｌ  ｖｅｒｓｉｏｎ  ｉｓ  ａｖａｉｌａｂｌｅ  ａｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／５６３
【非特許文献３０】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｅｆｆｉｃｉｅｎｔ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｎｏｎ−ｍｏｎｏｔｏｎｅ  ｐｒｅｄｉｃａｔｅｓ  ｉｎ  ｔｈｅ  ｓｔａｎｄａｒｄ  ｍｏｄｅｌ，  Ｉｎ：  ＰＫＣ  ２０１１，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）
【非特許文献３１】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｓｉｇｎａｔｕｒｅｓ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／７０１
【非特許文献３２】Ｏｓｔｒｏｖｓｋｙ，  Ｒ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｎｏｎ−ｍｏｎｏｔｏｎｉｃ  ａｃｃｅｓｓ  ｓｔｒｕｃｔｕｒｅｓ．  Ｉｎ：  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００７，  ｐｐ．  １９５−２０３，  ＡＣＭ  （２００７）
【非特許文献３３】Ｐｉｒｒｅｔｔｉ，  Ｍ．，  Ｔｒａｙｎｏｒ，  Ｐ．，  ＭｃＤａｎｉｅｌ，  Ｐ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｓｅｃｕｒｅ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｓｙｓｔｅｍｓ．  Ｉｎ：  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００６，  ｐｐ．  ９９−１１２，  ＡＣＭ，  （２００６）
【非特許文献３４】Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｆｕｚｚｙ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ：  Ｃｒａｍｅｒ，  Ｒ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００５．  ＬＮＣＳ，  ｖｏｌ．  ３４９４，  ｐｐ．  ４５７−４７３．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００５）
【非特許文献３５】Ｓｈｉ，  Ｅ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｄｅｌｅｇａｔｉｎｇ  ｃａｐａｂｉｌｉｔｙ  ｉｎ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｓｙｓｔｅｍｓ．  Ｉｎ：  Ａｃｅｔｏ，  Ｌ．，  Ｄａｍｇ「ェａｒｄ，  Ｉ．，  Ｇｏｌｄｂｅｒｇ，  Ｌ．Ａ．，  Ｈａｌｌｄゥェｒｓｓｏｎ，  Ｍ．Ｍ．，  Ｉｎｇゥェｌｆｓｄゥェｔｔｉｒ，  Ａ．，  Ｗａｌｕｋｉｅｗｉｃｚ，  Ｉ．  （ｅｄｓ．）  ＩＣＡＬＰ  （２）  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５１２６，  ｐｐ．  ５６０−５７８．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献３６】Ｗａｔｅｒｓ，  Ｂ．：  Ｅｆｆｉｃｉｅｎｔ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．  Ｅｕｒｏｃｒｙｐｔ  ２００５，  ＬＮＣＳ，  ｖｏｌ．  ３１５２，  ｐｐ．４４３−４５９．  Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，  （２００５）
【非特許文献３７】Ｗａｔｅｒｓ，  Ｂ．：  Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ：  ａｎ  ｅｘｐｒｅｓｓｉｖｅ，  ｅｆｆｉｃｉｅｎｔ，  ａｎｄ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｒｅａｌｉｚａｔｉｏｎ．ｅＰｒｉｎｔ，  ＩＡＣＲ，  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００８／２９０
【非特許文献３８】Ｗａｔｅｒｓ，  Ｂ．：  Ｄｕａｌ  ｓｙｓｔｅｍ  ｅｎｃｒｙｐｔｉｏｎ：  ｒｅａｌｉｚｉｎｇ  ｆｕｌｌｙ  ｓｅｃｕｒｅ  ＩＢＥ  ａｎｄ  ＨＩＢＥ  ｕｎｄｅｒ  ｓｉｍｐｌｅ  ａｓｓｕｍｐｔｉｏｎｓ．  Ｉｎ：  Ｈａｌｅｖｉ，  Ｓ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００９．  ＬＮＣＳ，  ｖｏｌ．  ５６７７，  ｐｐ．  ６１９−６３６．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００９）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献２９に記載された関数型暗号方式では、属性カテゴリ毎に基底Ｂｔ及び基底Ｂ＊ｔのペアが必要であり、属性カテゴリを追加する場合、新たな基底Ｂｔ及び基底Ｂ＊ｔのペアを生成する必要がある。そして、基底Ｂｔは、公開パラメータに含まれているため、公開パラメータを再発行する必要がある。
この発明は、公開パラメータの再発行をすることなく、属性カテゴリの追加を可能とすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号システムは、
所定の基底Ｂ及び所定の基底Ｂ＊を用いて処理を行う暗号システムであり、
複数のインデックスｊのうちの１つ以上のインデックスｊについての送信側ベクトルｔｊであって、前記基底Ｂにおける所定の基底ベクトルｂｉｎｄｅｘの係数に、インデックスｊに予め割り当てられた情報Ｊを設定し、前記基底Ｂにおける他の基底ベクトルｂａｔｔの係数に、インデックスｊについてのパラメータΦｊを設定した送信側ベクトルｔｊを生成する送信装置と、
複数のインデックスｊ’のうちの１つ以上のインデックスｊ’についての受信側ベクトルｒｊ’であって、前記基底ベクトルｂｉｎｄｅｘに対応する前記基底Ｂ＊における基底ベクトルｂ＊ｉｎｄｅｘの係数に、インデックスｊ’に対応するインデックスｊに予め割り当てられた情報Ｊとの内積が０になる情報Ｊ’を設定し、前記基底ベクトルｂａｔｔに対応する前記基底Ｂ＊における基底ベクトルｂ＊ａｔｔの係数に、インデックスｊ’についてのパラメータΨｊ’を設定した受信側ベクトルｒｊ’を用いて、インデックスｊについての前記送信側ベクトルｔｊと前記インデックスｊに対応するインデックスｊ’についての前記受信側ベクトルｒｊ’とに対して、対応する基底ベクトル毎のペアリング演算の積を計算する受信装置と
を備えることを特徴とする。
【発明の効果】
【０００６】
この発明に係る暗号システムでは、送信側ベクトルｔｊにはインデックスｊに予め割り当てられた情報Ｊが設定され、受信側ベクトルｒｊ’には、情報Ｊとの内積が０になる情報Ｊ’が設定される。これにより、安全性を維持したまま、全ての属性カテゴリに共通の基底Ｂ及び基底Ｂ＊を用いることができ、属性カテゴリ毎に基底Ｂｔ及び基底Ｂ＊ｔを用いる必要がなくなる。その結果、属性カテゴリを追加する場合、新たな基底Ｂｔ及び基底Ｂ＊ｔを生成する必要がなく、公開パラメータの再発行をすることなく、属性カテゴリの追加を可能とすることができる。
【図面の簡単な説明】
【０００７】
【図１】行列Ｍ＾の説明図。
【図２】行列Ｍδの説明図。
【図３】ｓ０の説明図。
【図４】ｓ→Ｔの説明図。
【図５】実施の形態２に係るＫＰ−ＦＥ方式を実行する暗号システム１０の構成図。
【図６】実施の形態２に係る鍵生成装置１００の構成図。
【図７】実施の形態２に係る暗号化装置２００の構成図。
【図８】実施の形態２に係る復号装置３００の構成図。
【図９】実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１０】実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１１】実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１２】実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１３】実施の形態３に係るＣＰ−ＦＥ方式を実行する暗号システム１０の構成図。
【図１４】実施の形態３に係る鍵生成装置１００の構成図。
【図１５】実施の形態３に係る暗号化装置２００の構成図。
【図１６】実施の形態３に係る復号装置３００の構成図。
【図１７】実施の形態３に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１８】実施の形態３に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１９】実施の形態３に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図２０】実施の形態４に係るＨＩＰＥ方式を実行する暗号システム１０の構成図。
【図２１】実施の形態４に係る鍵生成装置１００の構成図。
【図２２】実施の形態４に係る暗号化装置２００の構成図。
【図２３】実施の形態４に係る復号装置３００の構成図。
【図２４】実施の形態４に係る鍵委譲装置４００の構成図。
【図２５】実施の形態４に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図２６】実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図２７】実施の形態４に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図２８】実施の形態４に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図２９】実施の形態４に係るＤｅｌｅｇａｔｅＬアルゴリズムの処理を示すフローチャート。
【図３０】実施の形態５に係る署名方式を実行する暗号システム１０の構成図。
【図３１】実施の形態５に係る鍵生成装置１００の構成図。
【図３２】実施の形態５に係る署名装置５００の構成図。
【図３３】実施の形態５に係る検証装置６００の構成図。
【図３４】実施の形態５に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図３５】実施の形態５に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図３６】実施の形態５に係るＳｉｇアルゴリズムの処理を示すフローチャート。
【図３７】実施の形態５に係るＶｅｒアルゴリズムの処理を示すフローチャート。
【図３８】多管理者の説明図。
【図３９】多管理者の場合における属性カテゴリを追加可能な関数型暗号方式の説明図。
【図４０】鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００、署名装置５００、検証装置６００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【０００８】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。つまり、処理装置、記憶装置、通信装置、入力装置はハードウェアである。
【０００９】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
0005680007.tif 000002
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
0005680007.tif 000003
数１０３は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。
【数１０３】
0005680007.tif 000004
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
0005680007.tif 000005
数１０５、つまりＦｑは、位数ｑの有限体を示す。
【数１０５】
0005680007.tif 000006
ベクトル表記は、有限体Ｆｑにおけるベクトル表示を表す。つまり、数１０６である。
【数１０６】
0005680007.tif 000007
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
0005680007.tif 000008
【数１０８】
0005680007.tif 000009
【数１０９】
0005680007.tif 000010
ＸＴは、行列Ｘの転置行列を表す。
ｂｉ（ｉ＝１，．．．，ｎ）が空間Ｖのベクトルの要素であるとき、つまり、数１１０であるとき、数１１１は、数１１２によって生成される部分空間を表す。
【数１１０】
0005680007.tif 000011
【数１１１】
0005680007.tif 000012
【数１１２】
0005680007.tif 000013
数１１３に示す基底Ｂと基底Ｂ＊とに対して、数１１４である。
【数１１３】
0005680007.tif 000014
【数１１４】
0005680007.tif 000015
ｅ→ｊは、数１１５に示す正規基底ベクトルを示す。
【数１１５】
0005680007.tif 000016
【００１０】
また、以下の説明において、“Ｖｔ”が下付き又は上付きで示されている場合、このＶｔはＶｔを意味する。同様に、“δｉ，ｊ”が上付きで示されている場合、このδｉ，ｊは、δｉ，ｊを意味する。
また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
【００１１】
また、以下の説明において、暗号プリミティブの処理は、情報を第三者から秘匿するための狭義の暗号処理だけでなく、署名処理をも含むものであり、鍵生成処理、暗号化処理、復号処理、鍵委譲処理、署名処理、検証処理を含む。
【００１２】
実施の形態１．
この実施の形態では、以下の実施の形態で説明する、公開パラメータを再発行することなく、属性カテゴリの追加が可能な暗号プリミティブの処理を実現する基礎となる概念をする。
第１に、属性カテゴリの追加について説明する。
第２に、関数型暗号方式と、関数型暗号方式の基本構成とについて簡単に説明する。
第３に、公開パラメータを再発行することなく、属性カテゴリの追加を可能とするキーテクニックについて説明する。
第４に、関数型暗号方式を実現するための空間である「双対ペアリングベクトル空間（Ｄｕａｌ  Ｐａｉｒｉｎｇ  Ｖｅｃｔｏｒ  Ｓｐａｃｅｓ，ＤＰＶＳ）」という豊かな数学的構造を有する空間を説明する。
第５に、関数型暗号方式を実現するための概念を説明する。ここでは、スパンプログラム（Ｓｐａｎ  Ｐｒｏｇｒａｍ）」、「属性情報の内積とアクセスストラクチャ」、「秘密分散方式（秘密共有方式）」について説明する。
【００１３】
＜第１．属性カテゴリの追加＞
属性カテゴリとは、例えば、所属機関、所属部署、役職、年齢、性別等、各ユーザの属性の分類のことである。
【００１４】
以下の実施の形態で説明する暗号プリミティブの処理は、ユーザの属性に基づくアクセスコントロールを実現する。例えば、情報を第三者から秘匿するための狭義の暗号処理であれば、ユーザの属性に基づき、暗号文を復号できるか否かを制御する。
通常、アクセスコントロールに使用する属性カテゴリは、システム設計時に予め決定される。しかし、後にシステムの運用が変更され、アクセスコントロールに使用する属性カテゴリの追加が必要になる場合がある。
例えば、Ａ会社内のみで使用することを想定して暗号システムを構築したとする。この場合、使用する属性カテゴリとしては、所属部署、役職、個人のＩＤ等が想定される。しかし、後に、Ａ会社だけでなく、Ａ会社の関連会社でも暗号システムを使用するように運用が変更されたとする。この場合、使用する属性カテゴリとして、新たに所属会社を追加する必要がある。
【００１５】
アクセスコントロールに使用する属性カテゴリが、公開パラメータにより規定されている場合、後に属性カテゴリを追加するには、公開パラメータを再発行し、ユーザへ配布し直さなければならない。そのため、後に属性カテゴリを追加することは容易でなく、システム設計時に想定していなかった運用形態を柔軟に採用することができない。
そのため、公開パラメータを再発行することなく、属性カテゴリを追加できることは重要である。
【００１６】
＜第２．関数型暗号方式＞
関数型暗号方式は、暗号化鍵ｅｋと、復号鍵ｄｋとの間の関係をより高度化し、より柔軟にした暗号方式である。
関数型暗号方式において、暗号化鍵ｅｋと復号鍵ｄｋとには、それぞれ、パラメータΦとパラメータΨとが設定される。そして、関係Ｒ（Φ，Ψ）が成立する場合に限り、復号鍵ｄｋは暗号化鍵ｅｋで暗号化された暗号文を復号することができる。
関数型暗号方式には、属性ベース暗号方式やＩＤベース暗号方式が含まれる。
【００１７】
関数型暗号方式の構成を簡単に説明する。
関数型暗号方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、公開パラメータｐｋと、マスター鍵ｓｋとを出力するアルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター鍵ｓｋと、パラメータΨとを入力として、復号鍵ｓｋΨを出力するアルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、パラメータΦと、メッセージｍとを入力として、暗号文ｃｔΦを出力するアルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、復号鍵ｓｋΨと、暗号文ｃｔΦとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
なお、パラメータΨとパラメータΦとが関係Ｒを満たす場合（Ｒ（Φ，Ψ）が成立する場合）に限り、暗号文ｃｔΦを復号鍵ｓｋΨで復号して、メッセージｍを得ることができる。
【００１８】
なお、Ｓｅｔｕｐアルゴリズムは、通常、システムのセットアップ時に１度だけ実行される。ＫｅｙＧｅｎアルゴリズムは、ユーザの復号鍵ｓｋΨを生成する度に実行される。Ｅｎｃアルゴリズムは、メッセージｍを暗号化する度に実行される。Ｄｅｃアルゴリズムは、暗号文ｃｔΦを復号する度に実行される。
【００１９】
＜第３．キーテクニック＞
公開パラメータを再発行することなく、属性カテゴリの追加を可能とするキーテクニックは、双対ペアリングベクトル空間における双対システム暗号に、インデックス付けの技法を適用することである。
【００２０】
双対ペアリングベクトル空間における双対システム暗号では、双対基底である基底Ｂと基底Ｂ＊とがランダムに生成される。そして、基底Ｂの一部（基底Ｂ＾）が公開パラメータとされる。
【００２１】
非特許文献２９に記載された関数型暗号方式では、基底Ｂ＾１，．．．，基底Ｂ＾ｄが公開パラメータとして生成される。そして、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＾ｔに、１つの属性カテゴリが割り当てられる。つまり、ｄ個の属性カテゴリを扱うことができる。
ここで、基底Ｂ＾１，．．．，基底Ｂ＾ｄが公開パラメータであることから明らかなように、後に基底Ｂ＾を追加する場合、すなわちｄの値を増やす場合には、公開パラメータを再発行しなければならない。つまり、ｄの値は公開パラメータによって制限されている。
【００２２】
以下の実施の形態で説明する関数型暗号方式では、基底Ｂ＾が公開パラメータとして生成される。そして、ｔ＝１，．．．，ｄの各整数ｔについて、σｔ（１，ｔ）とμｉ（ｔ，−１）との２次元のインデックスベクトルが暗号文ｃと秘密鍵ｋ＊とに設定され、各整数ｔに対して１つの属性カテゴリが割り当てられる。つまり、ｄ個の属性カテゴリを扱うことができる。
ここで、公開パラメータには、基底Ｂ＾は含まれているものの、インデックスベクトルは含まれていない。そのため、後にインデックスベクトルを追加し、ｄの値を増やす場合、公開パラメータを再発行する必要はない。つまり、ｄの値は公開パラメータによって制限されていない。
【００２３】
＜第４．双対ペアリングベクトル空間＞
まず、対称双線形ペアリング群について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ  Ｂｉｌｉｎｅａｒ  Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００２４】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１６に示すＦｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１７に示す通りである。
【数１１６】
0005680007.tif 000017
【数１１７】
0005680007.tif 000018
【００２５】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１８によって定義される。
【数１１８】
0005680007.tif 000019
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００２６】
演算（２）：ディストーション写像
数１１９に示す空間Ｖにおける線形変換φｉ，ｊは、数１２０を行うことができる。
【数１１９】
0005680007.tif 000020
【数１２０】
0005680007.tif 000021
ここで、線形変換φｉ，ｊをディストーション写像と呼ぶ。
【００２７】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２８】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２９】
＜第５．関数型暗号を実現するための概念＞
＜第５−１．スパンプログラム＞
図１は、行列Ｍ＾の説明図である。
｛ｐ１，．．．，ｐｎ｝を変数の集合とする。Ｍ＾：＝（Ｍ，ρ）は、ラベル付けされた行列である。ここで、行列Ｍは、Ｆｑ上の（Ｌ行×ｒ列）の行列である。また、ρは、行列Ｍの各列に付されたラベルであり、｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝のいずれか１つのリテラルへ対応付けられる。なお、Ｍの全ての行に付されたラベルρi（ｉ＝１，．．．，Ｌ）がいずれか１つのリテラルへ対応付けられる。つまり、ρ：｛１，．．．，Ｌ｝→｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝である。
【００３０】
全ての入力列δ∈｛０，１｝ｎに対して、行列Ｍの部分行列Ｍδは定義される。行列Ｍδは、入力列δによってラベルρに値“１”が対応付けられた行列Ｍの行から構成される部分行列である。つまり、行列Ｍδは、δｉ＝１であるようなｐｉに対応付けられた行列Ｍの行と、δｉ＝０であるような¬ｐｉに対応付けられた行列Ｍの行とからなる部分行列である。
図２は、行列Ｍδの説明図である。なお、図２では、ｎ＝７，Ｌ＝６，ｒ＝５としている。つまり、変数の集合は、｛ｐ１，．．．，ｐ７｝であり、行列Ｍは（６行×５列）の行列である。また、図２において、ラベルρは、ρ１が¬ｐ２に、ρ２がｐ１に、ρ３がｐ４に、ρ４が¬ｐ５に、ρ５が¬ｐ３に、ρ６がｐ５にそれぞれ対応付けられているとする。
ここで、入力列δ∈｛０，１｝７が、δ１＝１，δ２＝０，δ３＝１，δ４＝０，δ５＝０，δ６＝１，δ７＝１であるとする。この場合、破線で囲んだリテラル（ｐ１，ｐ３，ｐ６，ｐ７，¬ｐ２，¬ｐ４，¬ｐ５）に対応付けられている行列Ｍの行からなる部分行列が行列Ｍδである。つまり、行列Ｍの１行目（Ｍ１），２行目（Ｍ２），４行目（Ｍ４）からなる部分行列が行列Ｍδである。
【００３１】
言い替えると、写像γ：｛１，．．．，Ｌ｝→｛０，１｝が、［ρ（ｊ）＝ｐｉ］∧［δｉ＝１］又は［ρ（ｊ）＝¬ｐｉ］∧［δｉ＝０］である場合、γ（ｊ）＝１であり、他の場合、γ（ｊ）＝０であるとする。この場合に、Ｍδ：＝（Ｍｊ）γ（ｊ）＝１である。ここで、Ｍｊは、行列Ｍのｊ番目の行である。
つまり、図２では、写像γ（ｊ）＝１（ｊ＝１，２，４）であり、写像γ（ｊ）＝０（ｊ＝３，５，６）である。したがって、（Ｍｊ）γ（ｊ）＝１は、Ｍ１，Ｍ２，Ｍ４であり、行列Ｍδである。
すなわち、写像γ（ｊ）の値が“０”であるか“１”であるかによって、行列Ｍのｊ番目の行が行列Ｍδに含まれるか否かが決定される。
【００３２】
１→∈ｓｐａｎ＜Ｍδ＞である場合に限り、スパンプログラムＭ＾は入力列δを受理し、他の場合には入力列δを拒絶する。つまり、入力列δによって行列Ｍ＾から得られる行列Ｍδの行を線形結合して１→が得られる場合に限り、スパンプログラムＭ＾は入力列δを受理する。なお、１→とは、各要素が値“１”である行ベクトルである。
例えば、図２の例であれば、行列Ｍの１，２，４行目からなる行列Ｍδの各行を線形結合して１→が得られる場合に限り、スパンプログラムＭ＾は入力列δを受理する。つまり、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾は入力列δを受理する。
【００３３】
ここで、ラベルρが正のリテラル｛ｐ１，．．．，ｐｎ｝にのみ対応付けられている場合、スパンプログラムはモノトーンと呼ばれる。一方、ラベルρがリテラル｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝に対応付けられている場合、スパンプログラムはノンモノトーンと呼ばれる。ここでは、スパンプログラムはノンモノトーンとする。そして、ノンモノトーンスパンプログラムを用いて、アクセスストラクチャ（ノンモノトーンアクセスストラクチャ）を構成する。アクセスストラクチャとは、簡単に言うと暗号へのアクセス制御を行うものである。つまり、暗号文を復号できるか否かの制御を行うものである。
詳しくは後述するが、スパンプログラムがモノトーンではなく、ノンモノトーンであることにより、スパンプログラムを利用して構成する関数型暗号方式の利用範囲が広がる。
【００３４】
＜第５−２．属性情報の内積とアクセスストラクチャ＞
ここでは、属性情報の内積を用いて上述した写像γ（ｊ）を計算する。つまり、属性情報の内積を用いて、行列Ｍのどの行を行列Ｍδに含めるかを決定する。
【００３５】
Ｕｔ（ｔ＝１，．．．，ｄでありＵｔ⊂｛０，１｝＊）は、部分全集合（ｓｕｂ−ｕｎｉｖｅｒｓｅ）であり、属性の集合である。そして、Ｕｔは、それぞれ部分全集合の識別情報（ｔ）と、ｎ次元ベクトル（ｖ→）とを含む。つまり、Ｕｔは、（ｔ，ｖ→）である。ここで、ｔ∈｛１，．．．，ｄ｝であり、ｖ→∈Ｆｑｎである。
【００３６】
Ｕｔ：＝（ｔ，ｖ→）をスパンプログラムＭ＾：＝（Ｍ，ρ）における変数ｐとする。つまり、ｐ：＝（ｔ，ｖ→）である。そして、変数（ｐ：＝（ｔ，ｖ→），（ｔ’，ｖ’→），．．．）としたスパンプログラムＭ＾：＝（Ｍ，ρ）をアクセスストラクチャＳとする。
つまり、アクセスストラクチャＳ：＝（Ｍ，ρ）であり、ρ：｛１，．．．，Ｌ｝→｛（ｔ，ｖ→），（ｔ’，ｖ’→），．．．，¬（ｔ，ｖ→），¬（ｔ’，ｖ’→），．．．｝である。
【００３７】
次に、Γを属性の集合とする。つまり、Γ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝である。
アクセスストラクチャＳにΓが与えられた場合、スパンプログラムＭ＾：＝（Ｍ，ρ）に対する写像γ：｛１，．．．，Ｌ｝→｛０，１｝は、以下のように定義される。ｉ＝１，．．．，Ｌの各整数ｉについて、［ρ（ｉ）＝（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ＝０］、又は、［ρ（ｉ）＝¬（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ≠０］である場合、γ（ｊ）＝１であり、他の場合、γ（ｊ）＝０とする。
つまり、属性情報ｖ→とｘ→との内積に基づき、写像γが計算される。そして、上述したように、写像γにより、行列Ｍのどの行を行列Ｍδに含めるかが決定される。すなわち、属性情報ｖ→とｘ→との内積により、行列Ｍのどの行を行列Ｍδに含めるかが決定され、１→∈ｓｐａｎ＜（Ｍｉ）γ（ｉ）＝１＞である場合に限り、アクセスストラクチャＳ：＝（Ｍ，ρ）はΓを受理する。
【００３８】
＜第５−３．秘密分散方式＞
アクセスストラクチャＳ：＝（Ｍ，ρ）に対する秘密分散方式について説明する。
なお、秘密分散方式とは、秘密情報を分散させ、意味のない分散情報にすることである。例えば、秘密情報ｓを１０個に分散させ、１０個の分散情報を生成する。ここで、１０個の分散情報それぞれは、秘密情報ｓの情報を有していない。したがって、ある１個の分散情報を手に入れても秘密情報ｓに関して何ら情報を得ることはできない。一方、１０個の分散情報を全て手に入れれば、秘密情報ｓを復元できる。
また、１０個の分散情報を全て手に入れなくても、一部だけ（例えば、８個）手に入れれば秘密情報ｓを復元できる秘密分散方式もある。このように、１０個の分散情報のうち８個で秘密情報ｓを復元できる場合を、８−ｏｕｔ−ｏｆ−１０と呼ぶ。つまり、ｎ個の分散情報のうちｔ個で秘密情報ｓを復元できる場合を、ｔ−ｏｕｔ−ｏｆ−ｎと呼ぶ。このｔを閾値と呼ぶ。
また、ｄ１，．．．，ｄ１０の１０個の分散情報を生成した場合に、ｄ１，．．．，ｄ８までの８個の分散情報であれば秘密情報ｓを復元できるが、ｄ３，．．．，ｄ１０までの８個の分散情報であれば秘密情報ｓを復元できないというような秘密分散方式もある。つまり、手に入れた分散情報の数だけでなく、分散情報の組合せに応じて秘密情報ｓを復元できるか否かを制御する秘密分散方式もある。
【００３９】
図３は、ｓ０の説明図である。図４は、ｓ→Ｔの説明図である。
行列Ｍを（Ｌ行×ｒ列）の行列とする。ｆ→Ｔを数１２１に示す列ベクトルとする。
【数１２１】
0005680007.tif 000022
数１２２に示すｓ０を共有される秘密情報とする。
【数１２２】
0005680007.tif 000023
また、数１２３に示すｓ→Ｔをｓ０のＬ個の分散情報のベクトルとする。
【数１２３】
0005680007.tif 000024
そして、分散情報ｓｉをρ（ｉ）に属するものとする。
【００４０】
アクセスストラクチャＳ：＝（Ｍ，ρ）がΓを受理する場合、つまりγ：｛１，．．．，Ｌ｝→｛０，１｝について１→∈ｓｐａｎ＜（Ｍｉ）γ（ｉ）＝１＞である場合、Ｉ⊆｛ｉ∈｛１，．．．，Ｌ｝｜γ（ｉ）-＝１｝である定数｛αｉ∈Ｆｑ｜ｉ∈Ｉ｝が存在する。
これは、図２の例で、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾は入力列δを受理すると説明したことからも明らかである。つまり、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾が入力列δを受理するのであれば、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する。
そして、数１２４である。
【数１２４】
0005680007.tif 000025
なお、定数｛αｉ｝は、行列Ｍのサイズにおける多項式時間で計算可能である。
【００４１】
以下の実施の形態に係る関数型暗号方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Ｍや、内積述語における属性情報ｘ及び属性情報ｖ（述語情報）を設計するにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Ｍの設計は、秘密分散方式の閾値等の条件設計に相当する。
例えば、上述した属性ベース暗号方式は、以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャにおいて、内積述語の設計をある条件に限定した場合に相当する。つまり、以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、属性ベース暗号方式におけるアクセスストラクチャは、内積述語における属性情報ｘ及び属性情報ｖ（述語情報）を設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、属性ベース暗号方式は、属性情報｛ｘ→ｔ｝ｔ∈｛１，．．．，ｄ｝と｛ｖ→ｔ｝ｔ∈｛１，．．．，ｄ｝とを、等号関係に対する２次元ベクトル、例えばｘ→ｔ：＝（１，ｘｔ）とｖ→ｔ：＝（ｖｔ，−１）とに限定した場合に相当する。
また、内積述語暗号方式は、以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャにおいて、スパンプログラムにおける行列Ｍの設計をある条件に限定した場合に相当する。つまり、以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、内積述語暗号方式におけるアクセスストラクチャは、スパンプログラムにおける行列Ｍの設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、内積述語暗号方式は、秘密分散方式を１−ｏｕｔ−ｏｆ−１（あるいは、ｄ−ｏｕｔ−ｏｆ−ｄ）に限定した場合である。
【００４２】
特に、以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。そのため、アクセス制御の設計の自由度がより高くなる。
具体的には、ノンモノトーンスパンプログラムには、否定形のリテラル（¬ｐ）を含むため、否定形の条件を設定できる。例えば、第１会社には、Ａ部とＢ部とＣ部とＤ部との４つの部署があったとする。ここで、第１会社のＢ部以外の部署の属するユーザにのみアクセス可能（復号可能）というアクセス制御をしたいとする。この場合に、否定形の条件の設定ができないとすると、「第１会社のＡ部とＣ部とＤ部とのいずれかに属すること」という条件を設定する必要がある。一方、否定形の条件の設定ができるとすると、「第１会社の社員であって、Ｂ部以外に属すること」という条件を設定することができる。つまり、否定形の条件が設定できることで、自然な条件設定が可能となる。なお、ここでは部署の数が少ないが、部署の数が多い場合等は非常に有効であることが分かる。
【００４３】
実施の形態２．
この実施の形態では、狭義の暗号処理方式について説明する。特に、この実施の形態では、Ｋｅｙ−Ｐｏｌｉｃｙ関数型暗号（ＫＰ−ＦＥ）方式について説明する。
なお、Ｋｅｙ−Ｐｏｌｉｃｙとは、復号鍵にＰｏｌｉｃｙが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
【００４４】
第１に、ＫＰ−ＦＥ方式の構成について説明する。
第２に、ＫＰ−ＦＥ方式を実現する暗号システム１０の構成について説明する。
第３に、ＫＰ−ＦＥ方式について詳細に説明する。
【００４５】
＜第１．ＫＰ−ＦＥ方式の構成＞
ＫＰ−ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、アクセスストラクチャＳ：＝（Ｍ，ρ）と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋＳを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、属性の集合であるΓ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋとを入力として、暗号文ｃｔΓを出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、属性の集合であるΓの下で暗号化された暗号文ｃｔΓと、アクセスストラクチャＳに対する復号鍵ｓｋＳと、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
【００４６】
＜第２．ＫＰ−ＦＥ方式を実現する暗号システム１０の構成＞
図５は、実施の形態２に係るＫＰ−ＦＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、アクセスストラクチャＳを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍと、属性の集合Γと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。暗号化装置２００は、生成した暗号文ｃｔΓを復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋＳと、暗号文ｃｔΓとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【００４７】
＜第３．ＫＰ−ＦＥ方式の詳細＞
図６から図１２に基づき、ＫＰ−ＦＥ方式、及び、ＫＰ−ＦＥ方式を実行する暗号システム１０の機能と動作とについて説明する。
図６は、実施の形態２に係る鍵生成装置１００の構成図である。図７は、実施の形態２に係る暗号化装置２００の構成図である。図８は、実施の形態２に係る復号装置３００の構成図である。
図９と図１０とは、鍵生成装置１００の動作を示すフローチャートである。なお、図９はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１０はＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１１は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図１２は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃアルゴリズムの処理を示すフローチャートである。
なお、以下の説明では、ｘｔ，１：＝１であるとする。
【００４８】
鍵生成装置１００の機能と動作とについて説明する。
鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、ｆベクトル生成部１４１、ｓベクトル生成部１４２、乱数生成部１４３、鍵要素生成部１４４を備える。
【００４９】
まず、図９に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１２５を計算して、パラメータｐａｒａｍと、基底Ｂ０及び基底Ｂ＊０と、基底Ｂ１（基底Ｂ）及び基底Ｂ＊１（基底Ｂ＊）とを生成する。
【数１２５】
0005680007.tif 000026
【００５０】
つまり、マスター鍵生成部１１０は以下の処理を実行する。
（１）マスター鍵生成部１１０は、入力装置により、セキュリティパラメータλ（１λ）を入力する。
（２）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλ（１λ）を入力としてアルゴリズムＧｂｐｇを実行して、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を生成する。
（３）マスター鍵生成部１１０は、処理装置により、乱数ψを生成するとともに、Ｎ０に１＋ｕ０＋１＋ｗ０＋ｚ０を、Ｎ１に２＋ｎ＋ｕ＋ｗ＋ｚを設定する。なお、ｎは１以上の整数であり、ｕ０，ｗ０，ｚ０，ｕ，ｗ，ｚはそれぞれ０以上の整数である。
【００５１】
続いて、マスター鍵生成部１１０は、ｔ＝０，１の各ｔについて以下の（４）から（８）までの処理を実行する。
（４）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλ（１λ）と、（３）で設定したＮｔと、（２）で生成したｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値とを入力としてアルゴリズムＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）の値を生成する。
（５）マスター鍵生成部１１０は、処理装置により、（３）で設定したＮｔと、Ｆｑとを入力として、線形変換Ｘｔ：＝（χｔ，ｉ，ｊ）ｉ，ｊをランダムに生成する。なお、ＧＬは、Ｇｅｎｅｒａｌ  Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。また、（χｔ，ｉ，ｊ）ｉ，ｊは、行列χｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
（６）マスター鍵生成部１１０は、処理装置により、乱数ψと線形変換Ｘｔとに基づき、（νｔ，ｉ，ｊ）ｉ，ｊ：＝ψ・（ＸｔＴ）−１を生成する。なお、（νｔ，ｉ，ｊ）ｉ，ｊも（χｔ，ｉ，ｊ）ｉ，ｊと同様に、行列νｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
（７）マスター鍵生成部１１０は、処理装置により、（５）で生成した線形変換Ｘｔに基づき、（４）で生成した標準基底Ａｔから基底Ｂｔを生成する。なお、ｘ→ｔ，ｉとは、線形変換Ｘｔのｉ行目を示す。
（８）マスター鍵生成部１１０は、処理装置により、（６）で生成した（νｔ，ｉ，ｊ）ｉ，ｊに基づき、（４）で生成した標準基底Ａｔから基底Ｂ＊ｔを生成する。なお、ｖ→ｔ，ｉとは、線形変換Ｘ＊ｔのｉ行目を示す。
（９）マスター鍵生成部１１０は、処理装置により、ｇＴにｅ（ｇ，ｇ）ψを設定する。また、マスター鍵生成部１１０は、ｐａｒａｍに（４）で生成した｛ｐａｒａｍＶｔ｝ｔ＝０，１と、ｇＴとを設定する。
【００５２】
すなわち、（Ｓ１０１）で、マスター鍵生成部１１０は、数１２６に示すアルゴリズムＧｏｂを実行して、ｐａｒａｍと、基底Ｂ０及び基底Ｂ＊０と、基底Ｂ１（基底Ｂ）及び基底Ｂ＊１（基底Ｂ＊）とを生成する。
【数１２６】
0005680007.tif 000027
【００５３】
なお、以下の説明では、簡単のため、基底Ｂ１及び基底Ｂ＊１を基底Ｂ及び基底Ｂ＊とする。
【００５４】
（Ｓ１０２：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ０の部分基底Ｂ＾０と、基底Ｂの部分基底Ｂ＾とを数１２７に示すように生成する。
【数１２７】
0005680007.tif 000028
マスター鍵生成部１１０は、生成した部分基底Ｂ＾０及び部分基底Ｂ＾と、（Ｓ１０１）で入力されたセキュリティパラメータλ（１λ）と、（Ｓ１０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。
【００５５】
（Ｓ１０３：マスター鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ＊０の部分基底Ｂ＾＊０と、基底Ｂ＊の部分基底Ｂ＾＊とを数１２８に示すように生成する。
【数１２８】
0005680007.tif 000029
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊０と部分基底Ｂ＾＊とをマスター鍵ｓｋとする。
【００５６】
（Ｓ１０４：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ１０２）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ１０３）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【００５７】
つまり、（Ｓ１０１）から（Ｓ１０３）において、鍵生成装置１００は、数１２９に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【数１２９】
0005680007.tif 000030
【００５８】
次に、図１０に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ２０１：情報入力ステップ）
情報入力部１３０は、入力装置により、上述したアクセスストラクチャＳ：＝（Ｍ，ρ）を入力する。なお、アクセスストラクチャＳの行列Ｍの設定については、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャＳのρは、例えば、復号鍵ｓｋＳの使用者の属性情報が設定されている。
【００５９】
（Ｓ２０２：ｆベクトル生成ステップ）
ｆベクトル生成部１４１は、処理装置により、ｒ個の要素を有するベクトルｆ→を数１３０に示すようにランダムに生成する。
【数１３０】
0005680007.tif 000031
【００６０】
（Ｓ２０３：ｓベクトル生成ステップ）
ｓベクトル生成部１４２は、処理装置により、（Ｓ２０１）で入力したアクセスストラクチャＳに含まれる（Ｌ行×ｒ列）の行列Ｍと、（Ｓ２０２）で生成したベクトルｆ→とに基づき、ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔを数１３１に示すように生成する。
【数１３１】
0005680007.tif 000032
また、ｓベクトル生成部１４２は、処理装置により、（Ｓ２０２）で生成したベクトルｆ→に基づき、値ｓ０を数１３２に示すように生成する。
【数１３２】
0005680007.tif 000033
【００６１】
（Ｓ２０４：乱数生成ステップ）
乱数生成部１４３は、処理装置により、乱数を数１３３に示すように生成する。
【数１３３】
0005680007.tif 000034
【００６２】
（Ｓ２０５：鍵要素生成ステップ）
鍵要素生成部１４４は、処理装置により、復号鍵ｓｋＳの要素ｋ＊０を数１３４に示すように生成する。
【数１３４】
0005680007.tif 000035
なお、上述したように、数１１３に基底Ｂと基底Ｂ＊とに対して、数１１４である。したがって、数１３４は、基底Ｂ＊０の基底ベクトルｂ＊０，１の係数として−ｓ０を設定し、基底ベクトルｂ＊０，１＋１，．．．，ｂ＊０，１＋ｕ０の係数として０を設定し、基底ベクトルｂ＊０，１＋ｕ０＋１の係数として１を設定し、基底ベクトルｂ＊０，１＋ｕ０＋１＋１，．．．，ｂ＊０，１＋ｕ０＋１＋ｗ０の係数としてη０，１，．．．，η０，ｗ０を設定し、基底ベクトルｂ＊０，１＋ｕ０＋１＋ｗ０＋１，．．．，ｂ＊０，１＋ｕ０＋１＋ｗ０＋ｚ０の係数として０を設定することを意味する。ここで、ｕ０，ｗ０，ｚ０はそれぞれｕ０，ｗ０，ｚ０のことである。
また、鍵要素生成部１４４は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、復号鍵ｓｋＳの要素ｋ＊ｉを数１３５に示すように生成する。
【数１３５】
0005680007.tif 000036
つまり、数１３５は、数１３４と同様に、ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、基底Ｂ＊の基底ベクトルｂ＊１の係数としてμｉｔを設定し、基底ベクトルｂ＊２の係数として−μｉを設定し、基底ベクトルｂ＊２＋１の係数としてｓｉ＋θｉｖｉ，１を設定し、基底ベクトルｂ＊２＋２，．．．，ｂ＊２＋ｎの係数としてθｉｖｉ，２，．．．，θｉｖｉ，ｎを設定し、基底ベクトルｂ＊２＋ｎ＋１，．．．，ｂ＊２＋ｎ＋ｕの係数として０を設定し、基底ベクトルｂ＊２＋ｎ＋ｕ＋１，．．．，ｂ＊２＋ｎ＋ｕ＋ｗの係数としてηｉ，１，．．．，ηｉ，ｗを設定し、基底ベクトルｂ＊２＋ｎ＋ｕ＋ｗ＋１，．．．，ｂ＊２＋ｎ＋ｕ＋ｗ＋ｚの係数として０を設定することを意味する。
一方、ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、基底Ｂ＊の基底ベクトルｂ＊１，の係数としてμｉｔを設定し、基底ベクトルｂ＊２の係数として−μｉを設定し、基底ベクトルｂ＊２＋１，．．．，ｂ＊２＋ｎの係数としてｓｉｖｉ，１，．．．，ｓｉｖｉ，ｎを設定し、基底ベクトルｂ＊２＋ｎ＋１，．．．，ｂ＊２＋ｎ＋ｕの係数として０を設定し、基底ベクトルｂ＊２＋ｎ＋ｕ＋１，．．．，ｂ＊２＋ｎ＋ｕ＋ｗの係数としてηｉ，１，．．．，ηｉ，ｗを設定し、基底ベクトルｂ＊２＋ｎ＋ｕ＋ｗ＋１，．．．，ｂ＊２＋ｎ＋ｕ＋ｗ＋ｚの係数として０を設定することを意味する。
【００６３】
（Ｓ２０６：鍵配布ステップ）
鍵配布部１５０は、（Ｓ２０１）で入力したアクセスストラクチャＳと、（Ｓ２０５）で生成されたｋ＊０，ｋ＊１，．．．，ｋ＊Ｌとを要素とする復号鍵ｓｋＳを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋＳは、他の方法により復号装置３００へ配布されてもよい。
【００６４】
つまり、（Ｓ２０１）から（Ｓ２０５）において、鍵生成装置１００は、数１３６に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。そして、（Ｓ２０６）で、鍵生成装置１００は、生成した復号鍵ｓｋＳを復号装置３００へ配布する。
【数１３６】
0005680007.tif 000037
【００６５】
暗号化装置２００の機能と動作とについて説明する。
暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号化データ生成部２３０、データ送信部２４０を備える。また、暗号化データ生成部２３０は、乱数生成部２３１、暗号要素生成部２３２を備える。
【００６６】
図１１に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１：公開パラメータ取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００６７】
（Ｓ３０２：情報入力ステップ）
情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍを入力する。また、情報入力部２２０は、入力装置により、属性の集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ，１，．．．，ｘｔ，ｎ∈Ｆｑｎ））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性の集合Γは、例えば、復号可能なユーザの属性情報が設定されている。
【００６８】
（Ｓ３０３：乱数生成ステップ）
乱数生成部２３１は、処理装置により、乱数を数１３７に示すように生成する。
【数１３７】
0005680007.tif 000038
【００６９】
（Ｓ３０４：暗号要素生成ステップ）
暗号要素生成部２３２は、処理装置により、暗号文ｃｔΓの要素ｃ０を数１３８に示すように生成する。
【数１３８】
0005680007.tif 000039
また、暗号要素生成部２３２は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔΓの要素ｃｔを数１３９に示すように生成する。
【数１３９】
0005680007.tif 000040
また、暗号要素生成部２３２は、処理装置により、暗号文ｃｔΓの要素ｃｄ＋１を数１４０に示すように生成する。
【数１４０】
0005680007.tif 000041
【００７０】
（Ｓ３０５：データ送信ステップ）
データ送信部２４０は、（Ｓ３０２）で入力した属性の集合Γと、（Ｓ３０４）で生成されたｃ０，ｃｔ，ｃｄ＋１とを要素とする暗号文ｃｔΓを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔΓは、他の方法により復号装置３００へ送信されてもよい。
【００７１】
つまり、（Ｓ３０１）から（Ｓ３０４）において、暗号化装置２００は、数１４１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。そして、（Ｓ３０５）で、暗号化装置２００は生成した暗号文ｃｔΓを復号装置３００へ送信する。
【数１４１】
0005680007.tif 000042
【００７２】
復号装置３００の機能と動作とについて説明する。
復号装置３００は、復号鍵取得部３１０、データ受信部３２０、スパンプログラム計算部３３０、補完係数計算部３４０、ペアリング演算部３５０、メッセージ計算部３６０を備える。
【００７３】
図１２に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ４０１：復号鍵取得ステップ）
復号鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布された復号鍵ｓｋＳ：＝（Ｓ，ｋ＊０，ｋ＊１，．．．，ｋ＊Ｌ）を取得する。また、復号鍵取得部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００７４】
（Ｓ４０２：データ受信ステップ）
データ受信部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔΓを受信する。
【００７５】
（Ｓ４０３：スパンプログラム計算ステップ）
スパンプログラム計算部３３０は、処理装置により、（Ｓ４０１）で取得した復号鍵ｓｋＳに含まれるアクセスストラクチャＳが、（Ｓ４０２）で受信した暗号文ｃｔΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、「実施の形態１における第５．関数型暗号を実現するための概念」で説明した通りである。
スパンプログラム計算部３３０は、アクセスストラクチャＳがΓを受理する場合（Ｓ４０３で受理）、処理を（Ｓ４０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ４０３で拒絶）、暗号文ｃｔΓを復号鍵ｓｋＳで復号できないとして処理を終了する。
【００７６】
（Ｓ４０４：補完係数計算ステップ）
補完係数計算部３４０は、処理装置により、数１４２となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１４２】
0005680007.tif 000043
【００７７】
（Ｓ４０５：ペアリング演算ステップ）
ペアリング演算部３５０は、処理装置により、数１４３を計算して、セッション鍵Ｋ＝ｇＴζを生成する。
【数１４３】
0005680007.tif 000044
なお、数１４４に示すように、数１４３を計算することにより鍵Ｋ＝ｇＴζが得られる。
【数１４４】
0005680007.tif 000045
【００７８】
（Ｓ４０６：メッセージ計算ステップ）
メッセージ計算部３６０は、処理装置により、ｍ’＝ｃｄ＋１／Ｋを計算して、メッセージｍ’（＝ｍ）を生成する。なお、ｃｄ＋１は数１４２に示す通りｇＴζｍであり、ＫはｇＴζであるから、ｍ’＝ｃｄ＋１／Ｋを計算すればメッセージｍが得られる。
【００７９】
つまり、（Ｓ４０１）から（Ｓ４０６）において、復号装置３００は、数１４５に示すＤｅｃアルゴリズムを実行して、メッセージｍ’（＝ｍ）を生成する。
【数１４５】
0005680007.tif 000046
【００８０】
以上のように、実施の形態２に係る暗号システム１０は、復号鍵ｓｋＳの要素ｋ＊ｉについて、基底ベクトルｂ＊１，ｂ＊２の係数として、μｉｔと−μｉとをそれぞれ設定した。また、暗号システム１０は、暗号文ｃｔΓの要素ｃｔについて、基底ベクトルｂ１，ｂ２の係数として、σｔとσｔｔとをそれぞれ設定した。
そのため、対応するインデックスｔについての要素ｋ＊ｉと要素ｃｔとのペアリング演算を行うと、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との部分については、内積が０となり、キャンセルされる。つまり、対応するインデックスｔについての要素ｋ＊ｉと要素ｃｔとのペアリング演算を行うと、基底ベクトルの係数として設定したインデックス部（基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との部分）はキャンセルされ、残りの部分についてのペアリング演算の結果が得られる。
【００８１】
実施の形態２に係る暗号システム１０は、インデックス部を設けることにより、各属性カテゴリで使用する基底を共通の基底（基底Ｂ及び基底Ｂ＊）とすることができる。その結果、公開パラメータには、基底Ｂ及び基底Ｂ＊だけを含めておけばよく、後に属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない。
【００８２】
また、実施の形態２に係る暗号システム１０は、非特許文献２９に記載された関数型暗号方式と比べ、公開パラメータやマスター秘密鍵のサイズが小さい。そのため、公開パラメータやマスター秘密鍵を用いた各演算を効率的に行うことができる。
【００８３】
なお、インデックス部については、内積した結果が０となればよい。そのため、上記説明では、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との２次元をインデックス部としが、これに限らず、３次元以上をインデックス部としてもよい。また、インデックス部への値の割り当ても上記説明のものに限らず、他の割り当てであってもよい。
【００８４】
また、上記説明では、関数型暗号方式について説明した。しかし、数１４６から数１４９に示すように、上記関数型暗号方式を属性ベース暗号方式に変更することもできる。なお、数１４６から数１４９では、Ｎ０を１＋１＋１＋１＋１＝５とし、Ｎ１を２＋２＋８＋２＋２＝１６としている。つまり、ｕ０＝１，ｗ０＝１，ｚ０＝１，ｎ＝２，ｕ＝８，ｗ＝２，ｚ＝２としている。この場合であっても、安全性を証明することが可能である。
【数１４６】
0005680007.tif 000047
【数１４７】
0005680007.tif 000048
【数１４８】
0005680007.tif 000049
【数１４９】
0005680007.tif 000050
【００８５】
実施の形態３．
この実施の形態では、実施の形態２と同様に、狭義の暗号処理方式について説明する。特に、この実施の形態では、Ｃｉｐｈｅｒｔｅｘｔ−Ｐｏｌｉｃｙ関数型暗号（ＣＰ−ＦＥ）方式について説明する。
なお、Ｃｉｐｈｅｒｔｅｘｔ−Ｐｏｌｉｃｙとは、暗号文にＰｏｌｉｃｙが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
【００８６】
第１に、ＣＰ−ＦＥ方式の構成について説明する。
第２に、ＣＰ−ＦＥ方式を実現する暗号システム１０の構成について説明する。
第３に、ＣＰ−ＦＥ方式について詳細に説明する。
【００８７】
＜第１．ＣＰ−ＦＥ方式の構成＞
ＣＰ−ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、属性の集合であるΓ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋΓを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、アクセスストラクチャＳ：＝（Ｍ，ρ）と、公開パラメータｐｋとを入力として、暗号文ｃｔＳを出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、アクセスストラクチャＳの下で暗号化された暗号文ｃｔＳと、属性の集合であるΓに対する復号鍵ｓｋΓと、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
【００８８】
＜第２．ＣＰ−ＦＥ方式を実現する暗号システム１０の構成＞
図１３は、実施の形態３に係るＣＰ−ＦＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、属性の集合Γを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋΓを生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍと、アクセスストラクチャＳと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔＳを生成する。暗号化装置２００は、生成した暗号文ｃｔＳを復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋＳと、暗号文ｃｔＳとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【００８９】
＜第３．ＣＰ−ＦＥ方式の詳細＞
図１４から図１９に基づき、ＣＰ−ＦＥ方式、及び、ＣＰ−ＦＥ方式を実行する暗号システム１０の機能と動作とについて説明する。
図１４は、実施の形態３に係る鍵生成装置１００の構成図である。図１５は、実施の形態３に係る暗号化装置２００の構成図である。図１６は、実施の形態３に係る復号装置３００の構成図である。
図１７は、鍵生成装置１００の動作を示すフローチャートであり、ＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１８は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図１９は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃアルゴリズムの処理を示すフローチャートである。
なお、以下の説明では、ｘｔ，１：＝１であるとする。
【００９０】
Ｓｅｔｕｐアルゴリズムの処理は、実施の形態２で説明した処理と同じであるため、説明を省略する。
【００９１】
鍵生成装置１００の機能と動作とについて説明する。
鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、乱数生成部１４３、鍵要素生成部１４４を備える。
【００９２】
図１７に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ５０１：情報入力ステップ）
情報入力部１３０は、入力装置により、属性の集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ，１，．．．，ｘｔ，ｎ∈Ｆｑｎ））｜１≦ｔ≦ｄ｝を入力する。なお、属性の集合Γは、例えば、復号鍵ｓｋΓの使用者の属性情報が設定されている。
【００９３】
（Ｓ５０２：乱数生成ステップ）
乱数生成部１４３は、処理装置により、乱数を数１５０に示すように生成する。
【数１５０】
0005680007.tif 000051
【００９４】
（Ｓ５０３：鍵要素生成ステップ）
鍵要素生成部１４４は、処理装置により、復号鍵ｓｋΓの要素ｋ＊０を数１５１に示すように生成する。
【数１５１】
0005680007.tif 000052
また、鍵要素生成部１４４は、処理装置により、属性の集合Γに含まれる各整数ｔについて、復号鍵ｓｋΓの要素ｋ＊ｔを数１５２に示すように生成する。
【数１５２】
0005680007.tif 000053
【００９５】
（Ｓ５０４：鍵配布ステップ）
鍵配布部１５０は、（Ｓ５０１）で入力した属性の集合Γと、（Ｓ５０３）で生成されたｋ＊０，ｋ＊ｔとを要素とする復号鍵ｓｋΓを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋΓは、他の方法により復号装置３００へ配布されてもよい。
【００９６】
つまり、（Ｓ５０１）から（Ｓ５０３）において、鍵生成装置１００は、数１５３に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋΓを生成する。そして、（Ｓ５０４）で、鍵生成装置１００は、生成した復号鍵ｓｋΓを復号装置３００へ配布する。
【数１５３】
0005680007.tif 000054
【００９７】
暗号化装置２００の機能と動作とについて説明する。
暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号化データ生成部２３０、データ送信部２４０を備える。また、暗号化データ生成部２３０は、乱数生成部２３１、暗号要素生成部２３２、ｆベクトル生成部２３３、ｓベクトル生成部２３４を備える。
【００９８】
図１８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ６０１：公開パラメータ取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００９９】
（Ｓ６０２：情報入力ステップ）
情報入力部２２０は、入力装置により、アクセスストラクチャＳ：＝（Ｍ，ρ）を入力する。なお、アクセスストラクチャＳの設定については、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャＳのρは、例えば、復号可能なユーザの属性情報が設定されている。
また、情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍを入力する。
【０１００】
（Ｓ６０３：ｆベクトル生成ステップ）
ｆベクトル生成部２３３は、処理装置により、ｒ個の要素を有するベクトルｆ→を数１５４に示すようにランダムに生成する。
【数１５４】
0005680007.tif 000055
【０１０１】
（Ｓ６０４：ｓベクトル生成ステップ）
ｓベクトル生成部２３４は、処理装置により、（Ｓ６０２）で入力したアクセスストラクチャＳに含まれる（Ｌ行×ｒ列）の行列Ｍと、（Ｓ６０３）で生成したベクトルｆ→とに基づき、ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔを数１５５に示すように生成する。
【数１５５】
0005680007.tif 000056
また、ｓベクトル生成部２３４は、処理装置により、（Ｓ６０３）で生成したベクトルｆ→に基づき、値ｓ０を数１５６に示すように生成する。
【数１５６】
0005680007.tif 000057
【０１０２】
（Ｓ６０５：乱数生成ステップ）
乱数生成部２３１は、処理装置により、乱数を数１５７に示すように生成する。
【数１５７】
0005680007.tif 000058
【０１０３】
（Ｓ６０６：暗号要素生成ステップ）
暗号要素生成部２３２は、処理装置により、暗号化データｃの要素ｃ０を数１５８に示すように生成する。
【数１５８】
0005680007.tif 000059
また、暗号要素生成部２３２は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、暗号化データｃの要素ｃｉを数１５９に示すように生成する。
【数１５９】
0005680007.tif 000060
また、暗号要素生成部２３２は、処理装置により、暗号化データｃの要素ｃｄ＋１を数１６０に示すように生成する。
【数１６０】
0005680007.tif 000061
【０１０４】
（Ｓ６０７：データ送信ステップ）
データ送信部２４０は、（Ｓ６０２）で入力したアクセスストラクチャＳと、（Ｓ６０６）で生成されたｃ０，ｃ１，．．．，ｃＬ，ｃｄ＋１とを要素とする暗号文ｃｔＳを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔＳは、他の方法により復号装置３００へ送信されてもよい。
【０１０５】
つまり、（Ｓ６０１）から（Ｓ６０６）において、暗号化装置２００は、数１６１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＳを生成する。そして、（Ｓ６０７）で、暗号化装置２００は生成した暗号文ｃｔＳを復号装置３００へ送信する。
【数１６１】
0005680007.tif 000062
【０１０６】
復号装置３００の機能と動作とについて説明する。
復号装置３００は、復号鍵取得部３１０、データ受信部３２０、スパンプログラム計算部３３０、補完係数計算部３４０、ペアリング演算部３５０、メッセージ計算部３６０を備える。
【０１０７】
図１５に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ７０１：復号鍵取得ステップ）
復号鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布された復号鍵ｓｋΓを取得する。また、復号鍵取得部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１０８】
（Ｓ７０２：データ受信ステップ）
データ受信部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔＳを受信する。
【０１０９】
（Ｓ７０３：スパンプログラム計算ステップ）
スパンプログラム計算部３３０は、処理装置により、（Ｓ７０２）で取得した暗号文ｃｔＳに含まれるアクセスストラクチャＳが、（Ｓ７０１）で受信した復号鍵ｓｋΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、「実施の形態１における第５．関数型暗号を実現するための概念」で説明した通りである。
スパンプログラム計算部３３０は、アクセスストラクチャＳがΓを受理する場合（Ｓ７０３で受理）、処理を（Ｓ７０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ７０３で拒絶）、暗号文ｃｔＳを復号鍵ｓｋΓで復号できないとして処理を終了する。
【０１１０】
（Ｓ７０４）から（Ｓ７０６）は、実施の形態２における図１２に示す（Ｓ４０４）と（Ｓ４０６）と同様である。
【０１１１】
つまり、（Ｓ７０１）から（Ｓ７０６）において、暗号化装置２００は、数１６２に示すＤｅｃアルゴリズムを実行して、メッセージｍ’（＝ｍ）を生成する。
【数１６２】
0005680007.tif 000063
【０１１２】
以上のように、実施の形態３に係る暗号システム１０は、実施の形態２に係る暗号システム１０と同様に、インデックス部を設けることにより、各属性カテゴリで使用する基底を共通の基底（基底Ｂ及び基底Ｂ＊）とすることができる。その結果、公開パラメータには、基底Ｂ及び基底Ｂ＊だけを含めておけばよく、後に属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない。
【０１１３】
なお、実施の形態２と同様に、インデックス部については、内積した結果が０となればよい。そのため、上記説明では、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との２次元をインデックス部としが、これに限らず、３次元以上をインデックス部としてもよい。また、インデックス部への値の割り当ても上記説明のものに限らず、他の割り当てであってもよい。
【０１１４】
また、上記説明では、関数型暗号方式について説明した。しかし、数１６３から数１６７に示すように、上記関数型暗号方式を属性ベース暗号方式に変更することもできる。なお、数１６３から数１６７では、Ｎ０を１＋１＋１＋１＋１＝５とし、Ｎ１を２＋２＋８＋２＋２＝１６としている。つまり、ｕ０＝１，ｗ０＝１，ｚ０＝１，ｎ＝２，ｕ＝８，ｗ＝２，ｚ＝２としている。この場合であっても、安全性を証明することが可能である。
【数１６３】
0005680007.tif 000064
【数１６４】
0005680007.tif 000065
【数１６５】
0005680007.tif 000066
【数１６６】
0005680007.tif 000067
【０１１５】
また、実施の形態２ではＫＰ−ＦＥ方式について説明し、実施の形態３ではＣＰ−ＦＥ方式について説明した。これらと同様に、非特許文献３０に記載されたＵｎｉｆｉｅｄ−Ｐｏｌｉｃｙ  ＦＥ（ＵＰ−ＦＥ）も、属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない構成とすることができる。
【０１１６】
実施の形態４．
この実施の形態では、実施の形態２，３と同様に、狭義の暗号処理方式について説明する。特に、この実施の形態では、階層的内積述語暗号（ＨＩＰＥ）方式について説明する。
なお、ＨＩＰＥ方式とは、権限委譲可能な内積述語暗号方式である。権限委譲とは、上位の鍵を有する利用者が、その鍵（上位の鍵）よりも機能が制限された下位の鍵を生成することである。機能が制限されたとは、上位の鍵で復号可能な暗号文のうち、一部の暗号文のみ下位の鍵で復号可能であるという意味である。内積述語暗号方式は、実施の形態１で説明した通り、関数型暗号方式におけるアクセスストラクチャの設計を限定した場合に相当する。
ＨＩＰＥ方式には、効率的な第１方式と、効率は第１方式よりも劣るが、暗号文に設定された属性情報の秘匿性まで保証される第２方式とがある（非特許文献２９参照）。ここでは、一例として、第２方式について、公開パラメータを再発行することなく、属性カテゴリの追加を可能とした方式を説明する。しかし、非特許文献２９に記載されたアルゴリズムに対して同様の変更を加えることにより、第１方式についても、公開パラメータを再発行することなく、属性カテゴリの追加を可能とすることができる。
【０１１７】
第１に、ＨＩＰＥ方式の構成について説明する。
第２に、ＨＩＰＥ方式を実現する暗号システム１０の構成について説明する。
第３に、ＨＩＰＥ方式について詳細に説明する。
【０１１８】
＜第１．ＨＩＰＥ方式の構成＞
ＨＩＰＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃ、ＤｅｌｅｇａｔｅＬの５つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとを出力する確率的アルゴリズムである。マスター秘密鍵ｓｋは最も上位の鍵である。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと述語情報（ｖ→１，．．．，ｖ→Ｌ）（１≦Ｌ≦ｄ）とを入力として、第Ｌ層目の秘密鍵ｓｋＬを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、マスター公開鍵ｐｋと属性情報（ｘ→１，．．．，ｘ→ｈ）（１≦ｈ≦ｄ）とメッセージｍとを入力として、暗号文ｃｔを出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵ｓｋＬと暗号文ｃｔとを入力として、メッセージｍ又は識別情報⊥を出力する確率的アルゴリズムである。
（ＤｅｌｅｇａｔｅＬ）
ＤｅｌｅｇａｔｅＬは、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵ｓｋＬと第Ｌ＋１層目の述語情報ｖ→Ｌ＋１（Ｌ＋１≦ｄ）とを入力として、第Ｌ＋１層目の秘密鍵ｓｋＬ＋１を出力する確率的アルゴリズムである。つまり、ＤｅｌｅｇａｔｅＬアルゴリズムでは、下位の秘密鍵が出力される。
【０１１９】
＜第２．ＨＩＰＥ方式を実現する暗号システム１０の構成＞
図２０は、実施の形態４に係るＨＩＰＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００を備える。なお、ここでは、復号装置３００が、鍵委譲装置４００を備えるものとして説明するが、鍵委譲装置４００は、復号装置３００とは別に設けられていてもよい。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成したマスター公開鍵ｐｋを公開する。また、鍵生成装置１００は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと述語情報（ｖ→１，．．．，ｖ→Ｌ）（１≦Ｌ≦ｄ）とを入力としてＫｅｙＧｅｎアルゴリズムを実行して、第Ｌ層目の秘密鍵ｓｋＬを生成して第Ｌ層目の復号装置３００へ秘密裡に配布する。
暗号化装置２００は、マスター公開鍵ｐｋと属性情報（ｘ→１，．．．，ｘ→ｈ）（１≦ｈ≦ｄ）とメッセージｍとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔを生成する。暗号化装置２００は、生成した暗号文ｃｔを復号装置３００へ送信する。
復号装置３００は、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵ｓｋＬと暗号文ｃｔとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
鍵委譲装置４００は、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵ｓｋＬと第Ｌ＋１層目の述語情報ｖ→Ｌ＋１（Ｌ＋１≦ｄ）とを入力としてＤｅｌｅｇａｔｅＬアルゴリズムを実行して、第Ｌ＋１層目の秘密鍵ｓｋＬ＋１を生成して第Ｌ＋１層目の復号装置３００へ秘密裡に配布する。
【０１２０】
＜第３．ＨＩＰＥ方式の詳細＞
図２１から図２９に基づき、実施の形態４に係るＨＩＰＥ方式、及び、ＨＩＰＥ方式を実行する暗号システム１０の機能と動作とについて説明する。
図２１は、実施の形態４に係る鍵生成装置１００の構成図である。図２２は、実施の形態４に係る暗号化装置２００の構成図である。図２３は、実施の形態４に係る復号装置３００の構成図である。図２４は、実施の形態４に係る鍵委譲装置４００の構成図である。
図２５と図２６とは、鍵生成装置１００の動作を示すフローチャートである。なお、図２５はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図２６はＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図２７は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図２８は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃアルゴリズムの処理を示すフローチャートである。図２９は、鍵委譲装置４００の動作を示すフローチャートであり、ＤｅｌｅｇａｔｅＬアルゴリズムの処理を示すフローチャートである。
【０１２１】
鍵生成装置１００の機能と動作とについて説明する。
鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、乱数生成部１４３、鍵要素生成部１４４、ランダム化要素生成部１４５、委譲要素生成部１４６を備える。
【０１２２】
まず、図２５に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
Ｓ８０１は、実施の形態２における図９に示す（Ｓ１０１）と同様である。
【０１２３】
（Ｓ８０２：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ８０１）で生成した基底Ｂ０の部分基底Ｂ＾０と、基底Ｂの部分基底Ｂ＾と、基底Ｂ＊０の部分基底Ｂ＾＊０，ｐｋと、基底Ｂ＊の部分基底Ｂ＾＊ｐｋとを数１６７に示すように生成する。
【数１６７】
0005680007.tif 000068
マスター鍵生成部１１０は、生成した部分基底Ｂ＾０と部分基底Ｂ＾と部分基底Ｂ＾＊０，ｐｋと部分基底Ｂ＾＊ｐｋと、（Ｓ８０１）で入力されたセキュリティパラメータλ（１λ）と、（Ｓ８０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。
【０１２４】
（Ｓ８０３：マスター鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ８０１）で生成した基底Ｂ＊０の部分基底Ｂ＾＊０，ｓｋと、基底Ｂ＊の部分基底Ｂ＾＊ｓｋとを数１６８に示すように生成する。
【数１６８】
0005680007.tif 000069
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊０と部分基底Ｂ＾＊とをマスター鍵ｓｋとする。
【０１２５】
（Ｓ８０４：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ８０２）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ８０３）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【０１２６】
つまり、（Ｓ８０１）から（Ｓ８０３）において、鍵生成装置１００は、数１６９に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ８０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【数１６９】
0005680007.tif 000070
【０１２７】
次に、図２６に基づき、鍵生成装置１００が実行するＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ９０１：情報入力ステップ）
情報入力部１３０は、入力装置により、述語情報（ｖ→１，．．．，ｖ→Ｌ）を入力する。ｉ＝１，．．．，Ｌの各整数について、ｖ→ｉ：＝ｖｉ，１，．．．，ｖｉ，ｎである。なお、述語情報としては、鍵を使用する者の属性が入力される。
【０１２８】
（Ｓ９０２：乱数生成ステップ）
乱数生成部１４３は、処理装置により、乱数を数１７０に示すように生成する。
【数１７０】
0005680007.tif 000071
また、ｓｄｅｃ，０と、ｓｒａｎ，１，ｊ，０と、ｓｒａｎ，２，τ，０と、ｓｄｅｌ，（τ，ι），０とを数１７１に示すように設定する。
【数１７１】
0005680007.tif 000072
【０１２９】
（Ｓ９０３：鍵要素生成ステップ）
鍵要素生成部１４４は、処理装置により、復号鍵ｓｋＬの要素である鍵要素ｋ＊Ｌ，ｄｅｃを数１７２に示すように生成する。
【数１７２】
0005680007.tif 000073
【０１３０】
（Ｓ９０４：第１ランダム化要素生成ステップ）
ランダム化要素生成部１４５は、処理装置により、ｊ＝１，．．．，２Ｌの各整数ｊについて、復号鍵ｓｋＬの要素である第１ランダム化要素ｋ＊Ｌ，ｒａｎ，１，ｊを数１７３に示すように生成する。
【数１７３】
0005680007.tif 000074
【０１３１】
（Ｓ９０５：第２ランダム化要素生成ステップ）
ランダム化要素生成部１４５は、処理装置により、τ＝Ｌ＋１，．．．，ｄの各整数τについて、復号鍵ｓｋＬの要素である第２ランダム化要素ｋ＊Ｌ，ｒａｎ，２，τを数１７４に示すように生成する。
【数１７４】
0005680007.tif 000075
【０１３２】
（Ｓ９０６：委譲要素生成ステップ）
委譲要素生成部１４６は、処理装置により、τ＝Ｌ＋１，．．．，ｄの各整数τと、各整数τについてι＝１，２の各整数ιとについて、復号鍵ｓｋＬの要素である委譲要素ｋ＊Ｌ，ｄｅｌ，（τ，ι）を数１７５に示すように生成する。
【数１７５】
0005680007.tif 000076
【０１３３】
（Ｓ９０７：鍵配布ステップ）
鍵配布部１５０は、鍵要素ｋ＊Ｌ，ｄｅｃと、第１ランダム化要素ｋ＊Ｌ，ｒａｎ，１，ｊと、第２ランダム化要素ｋ＊Ｌ，ｒａｎ，２，τと、委譲要素ｋ＊Ｌ，ｄｅｌ，（τ，ι）とを要素とする復号鍵ｓｋＬを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋＬは、他の方法により復号装置３００へ配布されてもよい。
【０１３４】
つまり、（Ｓ９０１）から（Ｓ９０６）において、鍵生成装置１００は、数１７６、数１７７に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＬを生成する。そして、（Ｓ９０７）で、鍵生成装置１００は、生成された復号鍵ｓｋＬを復号装置３００へ配布する。
【数１７６】
0005680007.tif 000077
【数１７７】
0005680007.tif 000078
【０１３５】
暗号化装置２００の機能と動作とについて説明する。
暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号化データ生成部２３０、データ送信部２４０を備える。また、暗号化データ生成部２３０は、乱数生成部２３１、暗号要素生成部２３２を備える。
【０１３６】
図２７に基づき、暗号化装置２００が実行するＥｎｃアルゴリズムの処理について説明する。
（Ｓ１００１：マスター公開鍵取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成したマスター公開鍵ｐｋを取得する。
【０１３７】
（Ｓ１００２：情報入力ステップ）
情報入力部２２０は、入力装置により、属性情報（ｘ→１，．．．，ｘ→Ｌ）を入力する。ｉ＝１，．．．，Ｌの各整数について、ｘ→ｉ：＝ｘｉ，１，．．．，ｘｉ，Ｌである。なお、属性情報としては、暗号化したメッセージを復号可能な者の属性が入力される。
また、情報入力部２２０は、入力装置により、暗号化するメッセージｍを入力する。
【０１３８】
（Ｓ１００３：乱数生成ステップ）
乱数生成部２３１は、処理装置により、乱数を数１７８に示すように生成する。
【数１７８】
0005680007.tif 000079
【０１３９】
（Ｓ１００４：暗号要素ｃ１生成ステップ）
暗号要素生成部２３２は、処理装置により、暗号文ｃｔの要素である暗号要素ｃ１を数１７９に示すように生成する。
【数１７９】
0005680007.tif 000080
【０１４０】
（Ｓ１００５：暗号要素ｃ２生成ステップ）
暗号要素生成部２３２は、処理装置により、暗号文ｃｔの要素である暗号要素ｃ２を数１８０に示すように生成する。
【数１８０】
0005680007.tif 000081
【０１４１】
（Ｓ１００６：データ送信ステップ）
データ送信部２４０は、暗号要素ｃ１と、暗号要素ｃ２とを含む暗号文ｃｔを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔは、他の方法により復号装置３００へ送信されてもよい。
【０１４２】
つまり、（Ｓ１００１）から（Ｓ１００５）において、暗号化装置２００は、数１８１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔを生成する。そして、（Ｓ１００６）で、暗号化装置２００は、生成された暗号文ｃｔを復号装置３００へ送信する。
【数１８１】
0005680007.tif 000082
【０１４３】
復号装置３００の機能と動作とについて説明する。
復号装置３００は、復号鍵取得部３１０、データ受信部３２０、ペアリング演算部３５０、メッセージ計算部３６０を備える。
【０１４４】
図２８に基づき、復号装置３００が実行するＤｅｃアルゴリズムの処理について説明する。
（Ｓ１１０１：復号鍵取得ステップ）
復号鍵取得部３１０は、例えば、通信装置によりネットワークを介して、復号鍵ｓｋＬを取得する。また、復号鍵取得部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１４５】
（Ｓ１１０２：データ受信ステップ）
データ受信部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔを受信する。
【０１４６】
（Ｓ１１０３：ペアリング演算ステップ）
ペアリング演算部３５０は、処理装置により、数１８２に示すペアリング演算を行い、セッション鍵Ｋ＝ｇＴζを計算する。
【数１８２】
0005680007.tif 000083
【０１４７】
（Ｓ１１０４：メッセージ計算ステップ）
メッセージ計算部３６０は、処理装置により、暗号要素ｃ２をセッション鍵Ｋで割ることにより、メッセージｍ’（＝ｍ）を計算する。
【０１４８】
つまり、（Ｓ１１０１）から（Ｓ１１０４）において、復号装置３００は、数１８３に示すＤｅｃアルゴリズムを実行して、メッセージｍ’（＝ｍ）を計算する。
【数１８３】
0005680007.tif 000084
【０１４９】
鍵委譲装置４００の機能と動作とについて説明する。
鍵委譲装置４００は、復号鍵取得部４１０、情報入力部４２０、委譲鍵生成部４３０、鍵配布部４４０を備える。また、委譲鍵生成部４３０は、乱数生成部４３１、下位鍵要素生成部４３２、下位ランダム化要素生成部４３３、下位委譲要素生成部４３４を備える。
【０１５０】
図２９に基づき、鍵委譲装置４００が実行するＤｅｌｅｇａｔｅＬアルゴリズムの処理について説明する。
（Ｓ１２０１：復号鍵取得ステップ）
復号鍵取得部４１０は、例えば、通信装置によりネットワークを介して、復号鍵ｓｋＬを取得する。また、復号鍵取得部４１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１５１】
（Ｓ１２０２：情報入力ステップ）
情報入力部４２０は、入力装置により、述語情報ｖ→Ｌ＋１：＝（ｖＬ＋１，ｉ（ｉ＝１，．．．，ｎＬ＋１））を入力する。なお、述語情報としては、鍵を委譲される者の属性が入力される。
【０１５２】
（Ｓ１２０３：乱数生成ステップ）
乱数生成部４３１は、処理装置により、乱数を数１８４に示すように生成する。
【数１８４】
0005680007.tif 000085
【０１５３】
（Ｓ１２０４：下位鍵要素生成ステップ）
下位鍵要素生成部４３２は、処理装置により、委譲鍵ｓｋＬ＋１の要素である下位鍵要素ｋ＊Ｌ＋１，ｄｅｃを数１８５に示すように生成する。
【数１８５】
0005680007.tif 000086
【０１５４】
（Ｓ１２０５：第１下位ランダム化要素生成ステップ）
下位ランダム化要素生成部４３３は、処理装置により、ｊ’＝１，．．．，２（Ｌ＋１）の各整数ｊ’について、委譲鍵ｓｋＬ＋１の要素である第１下位ランダム化要素ｋ＊Ｌ＋１，ｒａｎ，１，ｊ’を数１８６に示すように生成する。
【数１８６】
0005680007.tif 000087
【０１５５】
（Ｓ１２０６：第２下位ランダム化要素生成ステップ）
下位ランダム化要素生成部４３３は、処理装置により、τ＝Ｌ＋２，．．．，ｄの各整数τについて、委譲鍵ｓｋＬ＋１の要素である第２下位ランダム化要素ｋ＊Ｌ＋１，ｒａｎ，２，τを数１８７に示すように生成する。
【数１８７】
0005680007.tif 000088
【０１５６】
（Ｓ１２０７：下位委譲要素生成ステップ）
下位委譲要素生成部４３４は、処理装置により、τ＝Ｌ＋２，．．．，ｄの各整数τと、各整数τについてι＝１，．．．，ｎの各整数ιとについて、委譲鍵ｓｋＬ＋１の要素である下位委譲要素ｋ＊Ｌ＋１，ｄｅｌ，（τ，ι）を数１８８に示すように生成する。
【数１８８】
0005680007.tif 000089
【０１５７】
（Ｓ１２０８：鍵配布ステップ）
鍵配布部１５０は、下位鍵要素ｋ＊Ｌ＋１，ｄｅｃと、第１下位ランダム化要素ｋ＊Ｌ＋１，ｒａｎ，１，ｊ’と、第２下位ランダム化要素ｋ＊Ｌ＋１，ｒａｎ，２，τと、下位委譲要素ｋ＊Ｌ＋１，ｄｅｌ，（τ，ι）とを要素とする委譲鍵ｓｋＬ＋１（下位の復号鍵）を、例えば通信装置によりネットワークを介して秘密裡に下位の復号装置３００へ配布する。もちろん、委譲鍵ｓｋＬ＋１は、他の方法により下位の復号装置３００へ配布されてもよい。
【０１５８】
つまり、（Ｓ１２０１）から（Ｓ１２０７）において、鍵委譲装置４００は、数１８９に示すＤｅｌｅｇａｔｅＬアルゴリズムを実行して、委譲鍵ｓｋＬ＋１を生成する。そして、（Ｓ１２０８）で、鍵委譲装置４００は、生成された委譲鍵ｓｋＬ＋１を下位の復号装置３００へ配布する。
【数１８９】
0005680007.tif 000090
【０１５９】
以上のように、実施の形態４に係る暗号システム１０は、実施の形態２，３に係る暗号システム１０と同様に、インデックス部を設けることにより、各属性カテゴリで使用する基底を共通の基底（基底Ｂ及び基底Ｂ＊）とすることができる。その結果、公開パラメータには、基底Ｂ及び基底Ｂ＊だけを含めておけばよく、後に属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない。
【０１６０】
なお、実施の形態２，３と同様に、インデックス部については、内積した結果が０となればよい。そのため、上記説明では、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との２次元をインデックス部としが、これに限らず、３次元以上をインデックス部としてもよい。また、インデックス部への値の割り当ても上記説明のものに限らず、他の割り当てであってもよい。
【０１６１】
また、上記説明では、関数型暗号方式を元にしたＨＩＰＥ方式について説明した。しかし、数１９０から数１９５に示すように、属性ベース暗号方式を元にしたＨＩＰＥ方式に変更することもできる。なお、数１９０から数１９５では、Ｎ０を１＋１＋１＋１＋１＝５とし、Ｎ１を２＋２＋８＋２＋２＝１６としている。つまり、ｕ０＝１，ｗ０＝１，ｚ０＝１，ｎ＝２，ｕ＝８，ｗ＝２，ｚ＝２としている。この場合であっても、安全性を証明することが可能である。
【数１９０】
0005680007.tif 000091
【数１９１】
0005680007.tif 000092
【数１９２】
0005680007.tif 000093
【数１９３】
0005680007.tif 000094
【数１９４】
0005680007.tif 000095
【数１９５】
0005680007.tif 000096
【０１６２】
実施の形態５．
この実施の形態では、署名方式について説明する。特に、この実施の形態では、実施の形態３で説明したＣＰ−ＦＥ方式に基づく、署名方式について説明する。
【０１６３】
第１に、署名方式の構成について説明する。
第２に、署名方式を実現する暗号システム１０の構成について説明する。
第３に、署名方式について詳細に説明する。
【０１６４】
＜第１．署名方式の構成＞
署名方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｓｉｇ、Ｖｅｒの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、属性の集合であるΓ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、署名鍵ｓｋΓを出力する確率的アルゴリズムである。
（Ｓｉｇ）
Ｓｉｇアルゴリズムは、メッセージｍと、署名鍵ｓｋΓと、アクセスストラクチャＳ：＝（Ｍ，ρ）と、公開パラメータｐｋとを入力として、署名データｓｉｇを出力する確率的アルゴリズムである。
（Ｖｅｒ）
Ｖｅｒアルゴリズムは、メッセージｍと、アクセスストラクチャＳ：＝（Ｍ，ρ）と、署名データｓｉｇと、公開パラメータｐｋとを入力として、署名の検証に成功したことを示す値“１”、又は、署名の検証に失敗したことを示す値“０”を出力するアルゴリズムである。
【０１６５】
＜第２．署名方式を実現する暗号システム１０の構成＞
図３０は、実施の形態５に係る署名方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、署名装置５００、検証装置６００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、属性の集合Γを入力としてＫｅｙＧｅｎアルゴリズムを実行して、署名鍵ｓｋΓを生成して署名装置５００へ秘密裡に配布する。
署名装置５００は、メッセージｍと、アクセスストラクチャＳと、公開パラメータｐｋと、署名鍵ｓｋΓとを入力としてＳｉｇアルゴリズムを実行して、署名情報ｓ→＊を生成する。署名装置５００は、生成した署名情報ｓ→＊と、メッセージｍと、アクセスストラクチャＳとを検証装置６００へ送信する。
検証装置６００は、署名情報ｓ→＊と、メッセージｍと、アクセスストラクチャＳと、公開パラメータｐｋとを入力としてＶｅｒアルゴリズムを実行して、値“１”、又は、値“０”を出力する。
【０１６６】
＜第３．署名方式の詳細＞
図３１から図３７に基づき、署名方式、及び、署名方式を実行する暗号システム１０の機能と動作とについて説明する。
図３１は、実施の形態５に係る鍵生成装置１００の構成図である。図３２は、実施の形態５に係る署名装置５００の構成図である。図３３は、実施の形態５に係る検証装置６００の構成図である。
図３４と図３５とは、鍵生成装置１００の動作を示すフローチャートである。なお、図３４はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図３５はＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図３６は、署名装置５００の動作を示すフローチャートであり、Ｓｉｇアルゴリズムの処理を示すフローチャートである。図３７は、検証装置６００の動作を示すフローチャートであり、Ｖｅｒアルゴリズムの処理を示すフローチャートである。
【０１６７】
なお、以下の説明において、Ｈ：＝（ＫＨλ，Ｈｈｋλ，Ｄ）は、衝突困難ハッシュ関数である（非特許文献３０参照）。衝突困難ハッシュ関数とは、出力が同じになる２つの入力を見つけることが困難なハッシュ関数である。
具体的には、アルゴリズムＧｂｐｇに関する衝突困難ハッシュ関数系Ｈと、多項式ｐｏｌｙ（λ）とについて以下の２つのことが言える。
１．鍵空間系は、λによって索引付けされる。各鍵空間は、ＫＨλによって示されるビット列における確率空間である。１λを入力とした場合の出力分布がＫＨλと等しい確率的多項式時間アルゴリズムが存在する。
２．ハッシュ関数系は、λと、ＫＨλからランダムに選択されたｈｋと、Ｄ：＝｛０，１｝ｐｏｌｙ（λ）とによって索引付けされる。ここで、各関数Ｈｈｋλ，Ｄは、Ｄの要素からＦｑＸへの写像である。なお、ｑは、アルゴリズムＧｂｐｇ（１λ）の出力ｐａｒａｍＧの最初の要素である。１λとｈｋとｄ∈Ｄとを入力として、Ｈｈｋλ，Ｄ（ｄ）を出力する決定的多項式時間アルゴリズムがある。
【０１６８】
鍵生成装置１００の機能と動作とについて説明する。
鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、乱数生成部１４３、鍵要素生成部１４４を備える。
【０１６９】
まず、図３４に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１３０１）は、実施の形態２における図９に示す（Ｓ１０１）と原則として同様である。但し、ｔ＝０，１，ｄ＋１について、（４）から（８）までの処理を実行する点と、Ｎ０が１＋ｕ０＋ｗ０＋ｚ０である点とが異なる。なお、Ｎｄ＋１は、２＋ｕｄ＋１＋ｗｄ＋１＋ｚｄ＋１であり、ｕｄ＋１，ｗｄ＋１，ｚｄ＋１はそれぞれ１以上の整数である。
【０１７０】
（Ｓ１３０２：ハッシュキー生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１９６を計算して、ハッシュキーｈｋをランダムに生成する。
【数１９６】
0005680007.tif 000097
【０１７１】
（Ｓ１３０３：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１３０１）で生成した基底Ｂ０の部分基底Ｂ＾０と、基底Ｂの部分基底Ｂ＾と、基底Ｂｄ＋１の部分基底Ｂ＾ｄ＋１と、基底Ｂ＊０の部分基底Ｂ＾＊０と、基底Ｂ＊の部分基底Ｂ＾＊と、基底Ｂ＊ｄ＋１の部分基底Ｂ＾＊ｄ＋１とを数１９７に示すように生成する。
【数１９７】
0005680007.tif 000098
マスター鍵生成部１１０は、生成した部分基底Ｂ＾０と部分基底Ｂ＾と部分基底Ｂ＾ｄ＋１と部分基底Ｂ＾＊０と部分基底Ｂ＾＊と部分基底Ｂ＾＊ｄ＋１と、（Ｓ１３０１）で入力されたセキュリティパラメータλ（１λ）と、（Ｓ１３０１）で生成したｐａｒａｍと、（Ｓ１３０２）で生成したハッシュキーｈｋとを合わせて、公開パラメータｐｋとする。
【０１７２】
（Ｓ１３０４：マスター鍵生成ステップ）
マスター鍵生成部１１０は、基底Ｂ＾＊０の基底ベクトルｂ＊０，１をマスター鍵ｓｋとする。
【０１７３】
（Ｓ１３０５：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ１３０３）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ１３０４）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【０１７４】
つまり、（Ｓ１３０１）から（Ｓ１３０４）において、鍵生成装置１００は、数１９８に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１３０５）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、署名装置５００や検証装置６００が取得可能な状態にされる。
【数１９８】
0005680007.tif 000099
【０１７５】
図３５に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ１４０１：情報入力ステップ）
情報入力部１３０は、入力装置により、属性の集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ，１，．．．，ｘｔ，ｎ∈Ｆｑｎ））｜１≦ｔ≦ｄ｝を入力する。なお、属性の集合Γは、例えば、署名鍵ｓｋΓの使用者の属性情報が設定されている。
【０１７６】
（Ｓ１４０２：乱数生成ステップ）
乱数生成部１４３は、処理装置により、乱数を数１９９に示すように生成する。
【数１９９】
0005680007.tif 000100
【０１７７】
（Ｓ１４０３：鍵要素生成ステップ）
鍵要素生成部１４４は、処理装置により、署名鍵ｓｋΓの要素ｋ＊０を数２００に示すように生成する。
【数２００】
0005680007.tif 000101
また、鍵要素生成部１４４は、処理装置により、属性の集合Γに含まれる各整数ｔについて、署名鍵ｓｋΓの要素ｋ＊ｔを数２０１に示すように生成する。
【数２０１】
0005680007.tif 000102
また、鍵要素生成部１４４は、処理装置により、署名鍵ｓｋΓの要素ｋ＊ｄ＋１，ｋ＊ｄ＋２を数２０２に示すように生成する。
【数２０２】
0005680007.tif 000103
【０１７８】
（Ｓ１４０４：鍵配布ステップ）
鍵配布部１５０は、（Ｓ１４０１）で入力した属性の集合Γと、（Ｓ１４０３）で生成されたｋ＊０，ｋ＊ｔ，ｋ＊ｄ＋１，ｋ＊ｄ＋２とを要素とする署名鍵ｓｋΓを、例えば通信装置によりネットワークを介して秘密裡に署名装置５００へ配布する。もちろん、署名鍵ｓｋΓは、他の方法により署名装置５００へ配布されてもよい。
【０１７９】
つまり、（Ｓ１４０１）から（Ｓ１４０３）において、鍵生成装置１００は、数２０３に示すＫｅｙＧｅｎアルゴリズムを実行して、署名鍵ｓｋΓを生成する。そして、（Ｓ１４０４）で、鍵生成装置１００は、生成した署名鍵ｓｋΓを署名装置５００へ配布する。
【数２０３】
0005680007.tif 000104
【０１８０】
署名装置５００の機能と動作とについて説明する。
署名装置５００は、署名鍵取得部５１０、情報入力部５２０、補完係数計算部５３０、署名データ生成部５４０、データ送信部５５０を備える。また、署名データ生成部５４０は、乱数生成部５４１、署名要素生成部５４２を備える。
【０１８１】
図３６に基づき、Ｓｉｇアルゴリズムの処理について説明する。
（Ｓ１５０１：署名鍵取得ステップ）
署名鍵取得部５１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した署名鍵ｓｋΓを取得する。また、署名鍵取得部５１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１８２】
（Ｓ１５０２：情報入力ステップ）
情報入力部５２０は、入力装置により、アクセスストラクチャＳ：＝（Ｍ，ρ）を入力する。なお、アクセスストラクチャＳの行列Ｍの設定については、実現したいシステムの条件に応じて設定されるものである。
また、情報入力部５２０は、入力装置により、署名を付すメッセージｍを入力する。
【０１８３】
（Ｓ１５０３：スパンプログラム計算ステップ）
補完係数計算部５３０は、処理装置により、（Ｓ１５０２）で入力したアクセスストラクチャＳが、（Ｓ１５０１）で取得した署名鍵ｓｋΓに含まれる属性の集合Γを受理するか否かを判定する。
なお、アクセスストラクチャが属性の集合を受理するか否かの判定方法は、「実施の形態１における第５．関数型暗号を実現するための概念」で説明した通りである。
補完係数計算部５３０は、アクセスストラクチャＳが属性の集合Γを受理する場合（Ｓ１５０３で受理）、処理を（Ｓ１５０４）へ進める。一方、アクセスストラクチャＳが属性の集合Γを拒絶する場合（Ｓ１５０３で拒絶）、処理を終了する。
【０１８４】
（Ｓ１５０４：補完係数計算ステップ）
補完係数計算部５３０は、処理装置により、数２０４となるＩと、Ｉに含まれる各整数ｉについて定数（補完係数）αｉとを計算する。
【数２０４】
0005680007.tif 000105
【０１８５】
（Ｓ１５０５：乱数生成ステップ）
乱数生成部５４１は、処理装置により、乱数を数２０５に示すように生成する。
【数２０５】
0005680007.tif 000106
【０１８６】
（Ｓ１５０６：署名要素生成ステップ）
署名要素生成部５４２は、処理装置により、署名データｓｉｇの要素である署名要素ｓ＊０を数２０６に示すように生成する。
【数２０６】
0005680007.tif 000107
ここで、ｒ＊０は、数２０７（数１１０から数１１２及びこれらの数式の説明を参照）である。
【数２０７】
0005680007.tif 000108
また、署名要素生成部５４２は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、署名データｓｉｇの要素である署名要素ｓ＊ｉを数２０８に示すように生成する。
【数２０８】
0005680007.tif 000109
ここで、ｒ＊ｉは、数２０９である。
【数２０９】
0005680007.tif 000110
また、γｉとｙ→ｉ：＝（ｙｉ，ｉ’（ｉ’＝１，．．．，ｎ）とは、数２１０である。
【数２１０】
0005680007.tif 000111
また、署名要素生成部５４２は、処理装置により、署名データｓｉｇの要素である署名要素ｓ＊Ｌ＋１を数２１１に示すように生成する。
【数２１１】
0005680007.tif 000112
ここで、ｒ＊Ｌ＋１は、数２１２である。
【数２１２】
0005680007.tif 000113
【０１８７】
（Ｓ１５０７：データ送信ステップ）
データ送信部５５０は、署名要素ｓ＊０と、署名要素ｓ＊ｉ（ｉ＝１，．．．，Ｌ）と、署名要素ｓ＊Ｌ＋１と、メッセージｍと、アクセスストラクチャＳ：＝（Ｍ，ρ）とを含む署名データｓｉｇを、例えば通信装置によりネットワークを介して検証装置６００へ送信する。もちろん、署名データｓｉｇは、他の方法により検証装置６００へ送信されてもよい。
【０１８８】
つまり、（Ｓ１５０１）から（Ｓ１５０６）において、署名装置５００は、数２１３に示すＳｉｇアルゴリズムを実行して、署名データｓｉｇを生成する。そして、（Ｓ１５０７）で、署名装置５００は、生成した署名データｓｉｇを検証装置６００へ送信する。
【数２１３】
0005680007.tif 000114
【０１８９】
検証装置６００の機能と動作とについて説明する。
検証装置６００は、公開パラメータ取得部６１０、データ受信部６２０、検証データ生成部６３０、ペアリング演算部６４０を備える。また、検証データ生成部６３０は、ｆベクトル生成部６３１、ｓベクトル生成部６３２、乱数生成部６３３、検証要素生成部６３４を備える。
【０１９０】
図３７に基づき、Ｖｅｒアルゴリズムの処理について説明する。
（Ｓ１６０１：公開パラメータ取得ステップ）
公開パラメータ取得部６１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１９１】
（Ｓ１６０２：署名データ受信ステップ）
データ受信部６２０は、例えば、通信装置によりネットワークを介して、署名装置５００が送信した署名データｓｉｇを受信する。
【０１９２】
（Ｓ１６０３：ｆベクトル生成ステップ）
ｆベクトル生成部６３１は、処理装置により、ｒ個の要素を有するベクトルｆ→を数２１４に示すようにランダムに生成する。
【数２１４】
0005680007.tif 000115
【０１９３】
（Ｓ１６０４：ｓベクトル生成ステップ）
ｓベクトル生成部６３２は、処理装置により、（Ｓ１６０２）で受信した署名データｓｉｇに含まれるアクセスストラクチャＳの（Ｌ行×ｒ列）の行列Ｍと、（Ｓ１６０３）で生成したｒ個の要素を有するベクトルｆ→とに基づき、ベクトルｓ→Ｔを数２１５に示すように生成する。
【数２１５】
0005680007.tif 000116
また、ｓベクトル生成部６３２は、処理装置により、（Ｓ１６０３）で生成したベクトルｆ→に基づき、値ｓ０を数２１６に示すように生成する。なお、１→は、全ての要素が値１のベクトルである。
【数２１６】
0005680007.tif 000117
【０１９４】
（Ｓ１６０５：乱数生成ステップ）
乱数生成部６３３は、処理装置により、乱数を数２１７に示すように生成する。
【数２１７】
0005680007.tif 000118
【０１９５】
（Ｓ１６０６：検証要素生成ステップ）
検証要素生成部６３４は、処理装置により、検証鍵の要素である検証要素ｃ０を数２１８に示すように生成する。
【数２１８】
0005680007.tif 000119
また、検証要素生成部６３４は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、検証鍵の要素である検証要素ｃｉを数２１９に示すように生成する。
【数２１９】
0005680007.tif 000120
また、検証要素生成部６３４は、処理装置により、検証鍵の要素である検証要素ｃＬ＋１を数２２０に示すように生成する。
【数２２０】
0005680007.tif 000121
【０１９６】
（Ｓ１６０７：第１ペアリング演算ステップ）
ペアリング演算部６４０は、処理装置により、ペアリング演算ｅ（ｂ０，１，ｓ＊０）を計算する。
ペアリング演算ｅ（ｂ０，１，ｓ＊０）を計算した結果が値１であれば、ペアリング演算部６４０は、署名の検証に失敗したことを示す値０を出力して、処理を終了する。一方、ペアリング演算ｅ（ｂ０，１，ｓ＊０）を計算した結果が値１でなければ、ペアリング演算部６４０は、処理をＳ１６０８へ進める。
【０１９７】
（Ｓ１６０８：第２ペアリング演算ステップ）
ペアリング演算部６４０は、処理装置により、数２２１に示すペアリング演算を計算する。
【数２２１】
0005680007.tif 000122
数２２１に示すペアリング演算を計算した結果が値１であれば、ペアリング演算部６４０は、署名の検証に成功したことを示す値１を出力する。一方、その他の値であれば、ペアリング演算部６４０は、署名の検証に失敗したことを示す値０を出力する。
【０１９８】
つまり、（Ｓ１６０１）から（Ｓ１６０８）において、検証装置６００は、数２２２に示すＶｅｒアルゴリズムを実行して、署名データｓｉｇを検証する。
【数２２２】
0005680007.tif 000123
【０１９９】
以上のように、実施の形態５に係る暗号システム１０は、実施の形態２−４に係る暗号システム１０と同様に、インデックス部を設けることにより、各属性カテゴリで使用する基底を共通の基底（基底Ｂ及び基底Ｂ＊）とすることができる。その結果、公開パラメータには、基底Ｂ及び基底Ｂ＊だけを含めておけばよく、後に属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない。
【０２００】
なお、実施の形態２−４と同様に、インデックス部については、内積した結果が０となればよい。そのため、上記説明では、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との２次元をインデックス部としが、これに限らず、３次元以上をインデックス部としてもよい。また、インデックス部への値の割り当ても上記説明のものに限らず、他の割り当てであってもよい。
【０２０１】
また、上記説明では、関数型暗号方式に基づく署名方式について説明した。しかし、実施の形態３で関数型暗号方式を属性ベース暗号方式に変更したのと同様に、属性ベース暗号方式に基づく署名方式に変更することもできる。
【０２０２】
実施の形態６．
この実施の形態では、多管理者関数型暗号方式及び多管理者署名方式について説明する。
【０２０３】
多管理者（Ｍｕｌｔｉ−Ａｕｔｈｏｒｉｔｙ）とは、ユーザの復号鍵（あるいは署名鍵）を生成する管理者が複数存在するという意味である。
通常の関数型暗号では、システム全体のセキュリティが１つの機関（管理者）に依存している。例えば、実施の形態２，３で説明した暗号システム１０では、システム全体のセキュリティが鍵生成装置１００に依存している。鍵生成装置１００の秘密鍵であるマスター秘密鍵ｓｋが漏洩した場合、システム全体のセキュリティが破られてしまう。
しかし、多管理者とすることで、一部の管理者のセキュリティが破られたり、一部の管理者の秘密鍵（マスター鍵）が漏洩した場合であっても、システムの一部だけが機能しなくなるだけであり、他の部分については正常に機能する状態とすることができる。
【０２０４】
図３８は、多管理者の説明図である。なお、図３８では、狭義の暗号処理を例としている。
図３８では、役所が、住所、電話番号、年齢等の属性について管理する。また、警察が、運転免許の種別等の属性について管理する。また、会社Ａが、会社Ａにおける役職、会社Ａにおける所属等の属性について管理する。そして、役所が管理する属性に関連付けられた復号鍵１は役所が発行し、警察が管理する属性に関連付けられた復号鍵２は警察が発行し、会社Ａが管理する属性に関連付けられた復号鍵３は会社Ａが発行する。
暗号文を復号する復号者は、役所、警察、会社Ａ等の各管理者が発行した復号鍵１，２，３を合わせた復号鍵を用い、暗号文を復号する。つまり、復号者から見た場合、各管理者から発行された復号鍵を合わせたものが、自分に発行された１つの復号鍵となる。
例えば、会社Ａのマスター鍵が漏洩した場合、暗号処理システムは、会社Ａの属性に関しては機能しなくなるが、他の管理者が管理する属性に関しては機能する。つまり、会社Ａが管理する属性については、指定した属性以外の属性のユーザによって復号されてしまう虞があるが、他の属性については、指定した属性のユーザによってのみ復号可能である。
【０２０５】
また、図３８の例からも分かるように、関数型暗号では、複数の管理者が存在し、各管理者が属性におけるあるカテゴリー（部分空間）又は定義域を管理し、そのカテゴリーにおけるユーザの属性についての復号鍵（の一片）を発行することが自然である
【０２０６】
どの機関でも管理者となることができ、他の機関とやりとりすることなく、復号鍵（の一片）を発行することができ、各ユーザが他の機関とやりとりすることなく、管理者から復号鍵（の一片）を取得できる場合、その方式を分散多管理者（Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ｍｕｌｔｉ−Ａｕｔｈｏｒｉｔｙ）方式と呼ぶ。
例えば、中央管理者がいる場合、分散多管理者とは言えない。中央管理者とは、他の管理者よりも上位の管理者である。中央管理者のセキュリティが破られた場合、全ての管理者のセキュリティが破られてしまう。
【０２０７】
非特許文献３１には、分散多管理者関数型暗号方式について記載されており、非特許文献３０には、分散ではない多管理者署名方式について記載されている。上記実施の形態の説明した暗号方式や署名方式と同様に、非特許文献３０，３１に記載された方式も、属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない構成とすることができる。
【０２０８】
図３９は、多管理者の場合における属性カテゴリを追加可能な関数型暗号方式の説明図である。
図３９では、図３８と同様に、役所が、住所、電話番号、年齢等の属性について管理する。また、警察が、運転免許の種別等の属性について管理する。また、会社Ａが、会社Ａにおける役職、会社Ａにおける所属等の属性について管理する。そして、役所が管理する属性に関連付けられた復号鍵１は役所が発行し、警察が管理する属性に関連付けられた復号鍵２は警察が発行し、会社Ａが管理する属性に関連付けられた復号鍵３は会社Ａが発行する。
ここで、役所は、基底Ｂ＾１と基底Ｂ＾＊１とをそれぞれ公開パラメータｐｋとマスター秘密鍵ｓｋとして生成する。そして、基底Ｂ＾＊１を用いて、住所、電話番号、年齢等の属性についての復号鍵１を生成する。同様に、警察は、基底Ｂ＾２と基底Ｂ＾＊２とをそれぞれ公開パラメータｐｋとマスター秘密鍵ｓｋとして生成する。そして、基底Ｂ＾＊２を用いて、運転免許の種別等の属性についての復号鍵２を生成する。同様に、会社Ａは、基底Ｂ＾３と基底Ｂ＾＊３とをそれぞれ公開パラメータｐｋとマスター秘密鍵ｓｋとして生成する。そして、基底Ｂ＾＊３を用いて、会社Ａにおける役職、会社Ａにおける所属等の属性についての復号鍵３を生成する。
送信者は、基底Ｂ＾１を用いて住所、電話番号、年齢等の属性を設定し、基底Ｂ＾２を用いて運転免許の種別等の属性を設定し、基底Ｂ＾３を用いて会社Ａにおける役職、会社Ａにおける所属等の属性を設定して、暗号文を生成する。そして、復号者は、復号鍵１−３を用いて、暗号文を復号する。
例えば、役所で管理する属性カテゴリに追加をする場合、役所の公開パラメータｐｋを再発行することなく、属性カテゴリを追加することが可能である。
【０２０９】
なお、ここでは、属性カテゴリを追加可能な関数型暗号方式について説明した。しかし、関数型暗号方式を応用した署名方式についても、原則として関数型暗号方式と同様の考え方になる。
【０２１０】
実施の形態７．
以上の実施の形態では、双対ベクトル空間において暗号プリミティブの処理を実現する方法について説明した。実施の形態７では、双対加群において暗号プリミティブの処理を実現する方法について説明する。
【０２１１】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号プリミティブの処理を実現した。しかし、合成数Ｍを用いて数２２３のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号プリミティブの処理を適用することができる。
【数２２３】
0005680007.tif 000124
【０２１２】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号プリミティブの処理を実現することができる。
【０２１３】
なお、以上の実施の形態において、安全性の証明の観点から、ｉ＝１，．．．，Ｌの各整数ｉについてのρ（ｉ）は、それぞれ異なる識別情報ｔについての肯定形の組（ｔ，ｖ→）又は否定形の組¬（ｔ，ｖ→）であると限定してもよい。
言い替えると、ρ（ｉ）＝（ｔ，ｖ→）又はρ（ｉ）＝¬（ｔ，ｖ→）である場合に、関数ρ~を、ρ~（ｉ）＝ｔである｛１，．．．，Ｌ｝→｛１，．．．ｄ｝の写像であるとする。この場合、ρ~が単射であると限定してもよい。なお、ρ（ｉ）は、上述したアクセスストラクチャＳ：＝（Ｍ，ρ（ｉ））のρ（ｉ）である。
【０２１４】
次に、実施の形態における暗号システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００、署名装置５００、検証装置６００）のハードウェア構成について説明する。
図４０は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００、署名装置５００、検証装置６００のハードウェア構成の一例を示す図である。
図４０に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００、署名装置５００、検証装置６００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０２１５】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０２１６】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０２１７】
プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「情報入力部１３０」、「復号鍵生成部１４０」、「鍵配布部１５０」、「公開パラメータ取得部２１０」、「情報入力部２２０」、「暗号化データ生成部２３０」、「データ送信部２４０」、「復号鍵取得部３１０」、「データ受信部３２０」、「スパンプログラム計算部３３０」、「補完係数計算部３４０」、「ペアリング演算部３５０」、「メッセージ計算部３６０」、「復号鍵取得部４１０」、「情報入力部４２０」、「委譲鍵生成部４３０」、「鍵配布部４４０」、「署名鍵取得部５１０」、「情報入力部５２０」、「補完係数計算部５３０」、「署名データ生成部５４０」、「データ送信部５５０」、「公開パラメータ取得部６１０」、「データ受信部６２０」、「検証データ生成部６３０」、「ペアリング演算部６４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋＳ，ｓｋΓ」、「暗号文ｃｔΓ，ｃｔＳ」、「アクセスストラクチャＳ」、「属性情報」、「メッセージｍ」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０２１８】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０２１９】
１０  暗号システム、１００  鍵生成装置、１１０  マスター鍵生成部、１２０  マスター鍵記憶部、１３０  情報入力部、１４０  復号鍵生成部、１４１  ｆベクトル生成部、１４２  ｓベクトル生成部、１４３  乱数生成部、１４４  鍵要素生成部、１４５  ランダム化要素生成部、１４６  委譲要素生成部、１５０  鍵配布部、２００  暗号化装置、２１０  公開パラメータ取得部、２２０  情報入力部、２３０  暗号化データ生成部、２３１  乱数生成部、２３２  暗号要素生成部、２４０  データ送信部、３００  復号装置、３１０  復号鍵取得部、３２０  データ受信部、３３０  スパンプログラム計算部、３４０  補完係数計算部、３５０  ペアリング演算部、３６０  メッセージ計算部、４００  鍵委譲装置、４１０  復号鍵取得部、４２０  情報入力部、４３０  委譲鍵生成部、４３１  乱数生成部、４３２  下位鍵要素生成部、４３３  下位ランダム化要素生成部、４３４  下位委譲要素生成部、４４０  鍵配布部、５００  署名装置、５１０  署名鍵取得部、５２０  情報入力部、５３０  補完係数計算部、５４０  署名データ生成部、５４１  乱数生成部、５４２  署名要素生成部、５５０  データ送信部、６００  検証装置、６１０  公開パラメータ取得部、６２０  データ受信部、６３０  検証データ生成部、６３１  ｆベクトル生成部、６３２  ｓベクトル生成部、６３３  乱数生成部、６３４  検証要素生成部、６４０  ペアリング演算部。
【図１】
0005680007.tif 000137
【図２】
0005680007.tif 000138
【図３】
0005680007.tif 000139
【図４】
0005680007.tif 000140
【図５】
0005680007.tif 000141
【図６】
0005680007.tif 000142
【図７】
0005680007.tif 000143
【図８】
0005680007.tif 000144
【図９】
0005680007.tif 000145
【図１０】
0005680007.tif 000146
【図１１】
0005680007.tif 000147
【図１２】
0005680007.tif 000148
【図１３】
0005680007.tif 000149
【図１４】
0005680007.tif 000150
【図１５】
0005680007.tif 000151
【図１６】
0005680007.tif 000152
【図１７】
0005680007.tif 000153
【図１８】
0005680007.tif 000154
【図１９】
0005680007.tif 000155
【図２０】
0005680007.tif 000156
【図２１】
0005680007.tif 000157
【図２２】
0005680007.tif 000158
【図２３】
0005680007.tif 000159
【図２４】
0005680007.tif 000160
【図２５】
0005680007.tif 000161
【図２６】
0005680007.tif 000162
【図２７】
0005680007.tif 000163
【図２８】
0005680007.tif 000164
【図２９】
0005680007.tif 000165
【図３０】
0005680007.tif 000166
【図３１】
0005680007.tif 000167
【図３２】
0005680007.tif 000168
【図３３】
0005680007.tif 000169
【図３４】
0005680007.tif 000170
【図３５】
0005680007.tif 000171
【図３６】
0005680007.tif 000172
【図３７】
0005680007.tif 000173
【図３８】
0005680007.tif 000174
【図３９】
0005680007.tif 000175
【図４０】
0005680007.tif 000176