(57)【要約】【課題】この発明は、量子計算機ができた場合にも有効な属性ベース暗号といった暗号を構成可能とすることを目的とする。【解決手段】暗号システムは、ｔ∈［ｄ］の整数ｔについての同種写像φｔと、ｔ∈［０，ｄ］の整数ｔについてのペアリング演算ｅｔとによって対応付けられた複数の群を用いる。暗号システムは、複数の群のうちのある群の暗号要素を含む暗号文を生成する暗号化装置と、複数の群のうちの前記ある群とは異なる群の鍵要素を含む復号鍵を用いて、暗号化装置によって生成された暗号文を復号する復号装置とを備える。【選択図】図１
2017212699.tif 000002
【特許請求の範囲】
【請求項１】
同種写像とペアリング演算とによって対応付けられた複数の群を用いた暗号システムにおける暗号化装置であり、
前記複数の群のうちのある群の暗号要素を含む暗号文を生成する暗号文生成部を備える暗号化装置。
【請求項２】
前記暗号システムは、群Ｇ０と、前記群Ｇ０と同種写像φｔによって対応付けられた群Ｇｔと、前記群Ｇ０及び群Ｇ＾０とペアリング演算ｅ０によって対応付られるとともに、前記群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔによって対応付られた群ＧＴとを用いる
請求項１に記載の暗号化装置。
【請求項３】
前記暗号文は、前記群Ｇ０の要素と前記群Ｇ＾０の要素とについて前記ペアリング演算ｅ０を行うことにより生成された前記群ＧＴの要素ｚを含む暗号要素ｃＴと、前記群Ｇ＾ｔの要素である暗号要素ｃとを含む請求項２に記載の暗号化装置。
【請求項４】
前記暗号システムは、ｔ＝１の整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数１に示す要素ｃ，ｃＴを含む請求項３に記載の暗号化装置。
【数１】
2017212699.tif 000061
【請求項５】
前記暗号システムは、２以上の整数ｄに関してｔ＝０，．．．，ｄの整数ｔについての群Ｇｔ及び群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数２に示す要素ｃｔ，ｃＴを含む請求項３に記載の暗号化装置。
【数２】
2017212699.tif 000062
【請求項６】
前記暗号システムは、１以上の整数ｄ及び１以上の整数ｎに関してｔ＝０，．．．，ｄの整数ｔとｊ＝０，．．．，ｎの整数ｎとι＝０，１の整数ιとについての群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数３に示す要素ｃｔ，ｊ，ｃＴを含む請求項３に記載の暗号化装置。
【数３】
2017212699.tif 000063
【請求項７】
前記暗号システムは、ｔ＝１の整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数９に示す要素ｃ＾０，ｃｉ，ｃＴを含む請求項３に記載の暗号化装置。
【数４】
2017212699.tif 000064
【請求項８】
同種写像とペアリング演算とによって対応付けられた複数の群を用いた暗号システムにおける復号装置であり、
前記複数の群のうちのある群の暗号要素を含む暗号文を、前記複数の群のうちの前記ある群とは異なる群の鍵要素を含む復号鍵を用いて復号する復号部
を備える復号装置。
【請求項９】
前記暗号システムは、群Ｇ０と、前記群Ｇ０と同種写像φｔによって対応付けられた群Ｇｔと、前記群Ｇ０及び群Ｇ＾０とペアリング演算ｅ０によって対応付られるとともに、前記群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔによって対応付られた群ＧＴとを用いる
請求項８に記載の復号装置。
【請求項１０】
前記暗号文は、前記群Ｇ０の要素と前記群Ｇ＾０の要素とについて前記ペアリング演算ｅ０を行うことにより生成された前記群ＧＴの要素ｚを含む暗号要素ｃＴと、前記群Ｇ＾ｔの要素である暗号要素ｃとを含み、
前記復号鍵は、前記群Ｇｔの鍵要素ｋを含み、
前記復号部は、前記鍵要素ｋと前記暗号要素ｃとについて前記ペアリング演算ｅｔを行い要素ｚ’を計算し、計算された前記要素ｚ’と前記暗号要素ｃＴとを用いて前記暗号文を復号する
請求項９に記載の復号装置。
【請求項１１】
前記暗号システムは、ｔ＝１の整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数５に示す要素ｃ，ｃＴを含み、
前記復号鍵は、前記鍵要素ｋとして、数６に示す要素ｈ１を含み、
前記復号部は、前記要素ｈ１と前記要素ｃとについて、ペアリング演算ｅ１を行い、前記暗号文を復号する
請求項１０に記載の復号装置。
【数５】
2017212699.tif 000065
【数６】
2017212699.tif 000066
【請求項１２】
前記暗号システムは、２以上の整数ｄに関してｔ＝０，．．．，ｄの整数ｔについての群Ｇｔ及び群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数７に示す要素ｃｔ，ｃＴを含み、
前記復号鍵は、前記鍵要素ｋとして、数８に示す要素ｋｉを含み、
前記復号部は、前記要素ｃｔと前記要素ｋｉについて、数９に示すペアリング演算を行い、前記暗号文を復号する
請求項１０に記載の復号装置。
【数７】
2017212699.tif 000067
【数８】
2017212699.tif 000068
【数９】
2017212699.tif 000069
【請求項１３】
前記暗号システムは、１以上の整数ｄ及び１以上の整数ｎに関してｔ＝０，．．．，ｄの整数ｔとｊ＝０，．．．，ｎの整数ｎとι＝０，１の整数ιとについての群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数１０に示す要素ｃｔ，ｊ，ｃＴを含み、
前記復号鍵は、前記鍵要素ｋとして、数１１に示す要素ｋｉ，ｊを含み、
前記復号部は、前記要素ｃｔ，ｊと前記要素ｋｉ，ｊについて、数１２に示すペアリング演算を行い、前記暗号文を復号する
請求項１０に記載の復号装置。
【数１０】
2017212699.tif 000070
【数１１】
2017212699.tif 000071
【数１２】
2017212699.tif 000072
【請求項１４】
前記暗号システムは、ｔ＝１の整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号文は、前記暗号要素ｃ及び前記暗号要素ｃＴとして、数１３に示す要素ｃ＾０，ｃｉ，ｃＴを含み、
前記復号鍵は、前記鍵要素ｋとして数１４に示す要素ｄ＾ｉ，ｄｊを含み、
前記復号部は、前記要素ｃ＾０，ｃｉと前記要素ｄ＾ｉ，ｄｊについて、数１５に示すペアリング演算を行い、前記暗号文を復号する
請求項１０に記載の復号装置。
【数１３】
2017212699.tif 000073
【数１４】
2017212699.tif 000074
【数１５】
2017212699.tif 000075
【請求項１５】
同種写像とペアリング演算とによって対応付けられた複数の群を用いた暗号システムであり、
前記複数の群のうちのある群の暗号要素を含む暗号文を生成する暗号化装置と、
前記複数の群のうちの前記ある群とは異なる群の鍵要素を含む復号鍵を用いて、前記暗号化装置によって生成された暗号文を復号する復号装置と
を備える暗号システム。
【請求項１６】
群Ｇ０と、前記群Ｇ０と準同型写像φｔによって対応付けられた群Ｇｔと、前記群Ｇ０及び群Ｇ＾０とペアリング演算ｅ０によって対応付られるとともに、前記群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔによって対応付られた群ＧＴとを用いた暗号システムであり、
前記群Ｇ０の要素と、前記群Ｇ＾０の要素とについて前記ペアリング演算ｅ０を行うことにより生成された前記群ＧＴの要素ｚを含む前記暗号要素ｃＴと、前記群Ｇ＾ｔの要素である暗号要素ｃとを含む暗号文を生成する暗号化装置と、
前記群Ｇｔの鍵要素ｋを含む復号鍵を用いて、前記鍵要素ｋと前記暗号要素ｃとについて前記ペアリング演算ｅｔを行い要素ｚ’を計算し、計算された前記要素ｚ’と前記暗号要素ｃＴとを用いて前記暗号文を復号する復号装置と
を備える暗号システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、耐量子暗号方式に関する。
【背景技術】
【０００２】
量子計算機の開発が世界的に進められている。量子計算機に対しても安全性を維持できる、すなわち耐量子性を有する、格子暗号をはじめとした暗号方式の研究も進められている。しかし、格子暗号には、的確なデータサイズ設定が未だ困難であるという指摘があり、他の数学原理に基づいた構成法が望まれていた。
【０００３】
楕円曲線におけるペアリング演算を用いた属性ベース暗号（以下、ＡＢＥ）が数多く提案されている。非特許文献１には、楕円曲線におけるペアリング演算を用いた属性ベース暗号の１つの方式が記載されている。
【０００４】
また、非特許文献２には、同種写像を用いた、耐量子性を有する公開鍵暗号方式が記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｖ．Ｇｏｙａｌ，  Ｏ．Ｐａｎｄｅｙ，  Ａ．Ｓａｈａｉ，  Ｂ．Ｗａｔｅｒｓ，  Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｃｉｒｃｕｉｔｓ
【非特許文献２】Ｌ．Ｄｅ  Ｆｅｏ，  Ｄ．Ｊａｏ，  Ｊ．Ｐｌｕｔ，  Ｔｏｗａｒｄｓ  ｑｕａｎｔｕｍ−ｒｅｓｉｓｔａｎｔ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｆｒｏｍ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｉｓｏｇｅｎｉｅｓ
【非特許文献３】Ｄｅ  Ｆｅｏ，  Ｌ．，  Ｊａｏ，  Ｄ．，  Ｐｌｕｔ，  Ｊ．：  Ｔｏｗａｒｄｓ  ｑｕａｎｔｕｍ−ｒｅｓｉｓｔａｎｔ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｆｒｏｍ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｉｓｏｇｅｎｉｅｓ．  Ｊ．  Ｍａｔｈ．  Ｃｒｙｐｔ．  ８（３），  ２０９−２４７  （２０１４），  ｐｒｅｌｉｍｉｎａｒｙ  ｖｅｒｓｉｏｎ：  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅｐｒｉｎｔ  Ａｒｃｈｉｖ，  ２０１１：５０６，  ２０１１
【非特許文献４】Ｃｈａｒｌｅｓ，  Ｄ．，  Ｌａｕｔｅｒ，  Ｋ．，  Ｇｏｒｅｎ，  Ｅ．：  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ  ｆｒｏｍ  ｅｘｐａｎｄｅｒ  ｇｒａｐｈｓ．  Ｊ．  Ｃｒｙｐｔ．  ２２（１），  ９３−１１３  （２００９），  ｐｒｅｌｉｍｉｎａｒｙ  ｖｅｒｓｉｏｎ：  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅｐｒｉｎｔ  Ａｒｃｈｉｖ，  ２００６：０２１，  ２００６
【非特許文献５】Ｙｏｓｈｉｄａ，  Ｒ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｃｏｍｐｕｔｉｎｇ  ａ  ｓｅｑｕｅｎｃｅ  ｏｆ  ２−ｉｓｏｇｅｎｉｅｓ  ｏｎ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ．  ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｆｕｎｄａｍｅｎｔａｌｓ  ９６−Ａ（１），  １５８−１６５  （２０１３），  ｐｒｅｌｉｍｉｎａｒｙ  ｖｅｒｓｉｏｎ  ｉｓ  ａｖａｉｌａｂｌｅ  ｉｎ  ＩＣＩＳＣ  ２００８，  ＬＮＣＳ，  ｖｏｌ．５４６１，  ｐｐ．５２−６５  （２００８）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、楕円曲線ペアリングを用いた属性ベース暗号は全て、量子計算機によりマスター秘密鍵が暴かれ壊滅的な被害を受けることがわかっている。また、耐量子性を有する属性ベース暗号はなかった。
この発明は、量子計算機ができた場合にも有効な属性ベース暗号といった暗号方式を構成可能とすることを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る暗号化装置は、
同種写像とペアリング演算とによって対応付けられた複数の群を用いた暗号システムにおける暗号化装置であり、
前記複数の群のうちのある群の暗号要素を含む暗号文を生成する暗号文生成部を備える。
【発明の効果】
【０００８】
この発明では、同種写像とペアリング演算とによって対応付けられた複数の群を用いることにより、量子計算機ができた場合にも有効な属性ベース暗号といった暗号を構成可能となる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１に係るＩＢＥ方式で用いられる同種ペアリンググループの説明図。
【図２】実施の形態１に係る暗号システム１の構成図。
【図３】実施の形態１に係る鍵生成装置１０の構成図。
【図４】実施の形態１に係る暗号化装置２０の構成図。
【図５】実施の形態１に係る復号装置３０の構成図。
【図６】実施の形態１に係るＳｅｔｕｐアルゴリズムのフローチャート。
【図７】実施の形態１に係る同種ペアリンググループの説明図。
【図８】実施の形態１に係るＫｅｙＧｅｎアルゴリズムのフローチャート。
【図９】実施の形態１に係るＥｎｃアルゴリズムのフローチャート。
【図１０】実施の形態１に係るＤｅｃアルゴリズムのフローチャート。
【図１１】実施の形態１に係るＩＢＥ方式に対する攻撃法の説明図。
【図１２】変形例１に係る鍵生成装置１０の構成図。
【図１３】変形例１に係る暗号化装置２０の構成図。
【図１４】変形例１に係る復号装置３０の構成図。
【図１５】実施の形態２に係る暗号システム１の構成図。
【図１６】実施の形態２に係る鍵生成装置１０の構成図。
【図１７】実施の形態２に係る暗号化装置２０の構成図。
【図１８】実施の形態２に係る復号装置３０の構成図。
【図１９】実施の形態５に係るＩＰＧ生成アルゴリズムのフローチャート。
【図２０】実施の形態５に係るアルゴリズムＩｓｏｇＬ〜，κ（Ｅ０）の説明図。
【図２１】実施の形態５に係るアルゴリズムＩｓｏｇＬ〜，κ（Ｅ０）の説明図。
【発明を実施するための形態】
【００１０】
実施の形態１．
実施の形態１では、耐量子性を有するＩＤベース暗号（以下、ＩＢＥ）方式について説明する。
【００１１】
＊＊＊記法の説明＊＊＊
実施の形態１で用いられる記法について説明する。
【００１２】
Ａがランダムな値または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
2017212699.tif 000003
【００１３】
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
2017212699.tif 000004
【００１４】
数１０３は、位数ｑの体を表す。
【数１０３】
2017212699.tif 000005
また、位数ｑの体を文中では単にＦｑと記載する。
【００１５】
［ｎ］：＝｛１，．．．，ｎ｝とし、［０，ｎ］：＝｛０｝∪［ｎ］：＝｛０，．．．，ｎ｝とする。ｎは、０以上の整数である。
【００１６】
数１０４に示す２つのベクトルｙ→及びｖ→について、ｙ→・ｖ→は、数１０５に示す内積を示す。
【数１０４】
2017212699.tif 000006
【数１０５】
2017212699.tif 000007
【００１７】
＊＊＊概念の説明＊＊＊
図１を参照して、実施の形態１に係るＩＢＥ方式で用いられる同種ペアリンググループ（以下、ＩＰＧ）について説明する。
【００１８】
ＩＰＧは、同種写像とペアリング演算とによって対応付けられた複数の群を有する。
具体的には、ＩＰＧは、群Ｇ０と、群Ｇ０と同種写像φｔによって対応付けられたｔ＝１，．．．，ｄの各群Ｇｔと、ｔ＝０，．．．，ｄの各群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔによって対応付られた群ＧＴとを有する。そして、ＩＰＧでは、群Ｇ０×群Ｇ＾０からペアリング演算ｅ０で変換された場合と、ｔ＝１，．．．，ｄのいずれの整数ｔについての同種写像φｔによって群Ｇ０×群Ｇ＾０から群Ｇｔ×群Ｇ＾ｔに変換された上で、ペアリング演算ｅｔによって変換された場合とで、結果は等しくなる。
【００１９】
より正確には、ＩＰＧは以下のように定義される。
ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）では、数１０６に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｓｋＩＰＧとのマスター鍵ペアがランダムに生成される。
【数１０６】
2017212699.tif 000008
ここで、（Ｇｔ，Ｇ＾ｔ，ｅｔ，ＧＴ）は、ペアリング演算ｅｔ：Ｇｔ×Ｇ＾ｔ→ＧＴを有する素数位数ｑの非対称ペアリング群である。ｇ＾ｔ∈Ｇ＾ｔである。同種写像φｔ：Ｇ０→Ｇｔであり、異なる楕円曲線間の同種によって与えられる。ｇｔ＝φｔ（ｇ０）∈Ｇｔである。
ＩＰＧは、数１０７に示す両立性を有する。
【数１０７】
2017212699.tif 000009
ここで、ｇＴ＝ｅ０（ｇ０，ｇ＾０）≠１である。また、Ｇｔ≠Ｇ＾ｔである。
【００２０】
＊＊＊構成の説明＊＊＊
実施の形態１に係るＩＢＥ方式の構成を説明する。
ＩＢＥ方式は、Ｓｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとを備える。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｋと、マスター秘密鍵ｓｋとを出力する。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター秘密鍵ｓｋと、識別子ＩＤとを入力として、識別子ＩＤに対応した復号鍵ｓｋＩＤを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、メッセージ空間ｍｓｇにおけるメッセージｍと、識別子ＩＤ’とを入力として、暗号文ｃｔＩＤ’を出力する。
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、識別子ＩＤに対応した復号鍵ｓｋＩＤと、識別子ＩＤ’の下で暗号化された暗号文ｃｔＩＤ’とを入力として、メッセージｍ’∈ｍｓｇ、又は、復号に失敗したことを示す識別情報⊥を出力する。
【００２１】
図２を参照して、実施の形態１に係る暗号システム１の構成を説明する。
暗号システム１は、鍵生成装置１０と、暗号化装置２０と、復号装置３０とを備える。
鍵生成装置１０と暗号化装置２０と復号装置３０とは、コンピュータである。鍵生成装置１０と暗号化装置２０と復号装置３０とは、ネットワークを介して接続されている。
【００２２】
鍵生成装置１０は、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋと、マスター秘密鍵ｓｋとを生成する。また、鍵生成装置１０は、公開パラメータｐｋと、マスター秘密鍵ｓｋと、識別子ＩＤとを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
鍵生成装置１０は、公開パラメータｐｋを公開し、復号鍵ｓｋＩＤを識別子ＩＤに対応する復号装置３０に出力する。鍵生成装置１０は、マスター秘密鍵ｓｋを保管する。
【００２３】
暗号化装置２０は、公開パラメータｐｋと、メッセージｍと、識別子ＩＤ’とを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。暗号化装置２０は、暗号文ｃｔＩＤ’を復号装置３０に出力する。
【００２４】
復号装置３０は、公開パラメータｐｋと、復号鍵ｓｋＩＤと、暗号文ｃｔＩＤ’とを入力として、Ｄｅｃアルゴリズムを実行して、メッセージｍ’、又は、復号に失敗したことを示す識別情報⊥を生成する。
【００２５】
図３を参照して、実施の形態１に係る鍵生成装置１０の構成を説明する。
鍵生成装置１０は、プロセッサ１１と、記憶装置１２と、入出力インタフェース１３とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２６】
鍵生成装置１０は、機能構成要素として、マスター鍵生成部１４と、復号鍵生成部１５と、鍵出力部１６とを備える。マスター鍵生成部１４と、復号鍵生成部１５と、鍵出力部１６との各部の機能はソフトウェアにより実現される。
記憶装置１２には、鍵生成装置１０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ１１により読み込まれ、プロセッサ１１によって実行される。これにより、鍵生成装置１０の各部の機能が実現される。
【００２７】
図４を参照して、実施の形態１に係る暗号化装置２０の構成を説明する。
暗号化装置２０は、プロセッサ２１と、記憶装置２２と、入出力インタフェース２３とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２８】
暗号化装置２０は、機能構成要素として、入力受付部２４と、暗号文生成部２５と、暗号文出力部２６とを備える。入力受付部２４と、暗号文生成部２５と、暗号文出力部２６との各部の機能はソフトウェアにより実現される。
記憶装置２２には、暗号化装置２０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ２１により読み込まれ、プロセッサ２１によって実行される。これにより、暗号化装置２０の各部の機能が実現される。
【００２９】
図５を参照して、実施の形態１に係る復号装置３０の構成を説明する。
復号装置３０は、プロセッサ３１と、記憶装置３２と、入出力インタフェース３３とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００３０】
復号装置３０は、機能構成要素として、入力受付部３４と、復号部３５と、メッセージ出力部３６とを備える。入力受付部３４と、復号部３５と、メッセージ出力部３６との各部の機能はソフトウェアにより実現される。
記憶装置３２には、復号装置３０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ３１により読み込まれ、プロセッサ３１によって実行される。これにより、復号装置３０の各部の機能が実現される。
【００３１】
プロセッサ１１，２１，３１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１，２１，３１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００３２】
記憶装置１２，２２，３２は、具体例としては、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、記憶装置１２，２２，３２は、は、ＳＤ（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体であってもよい。
【００３３】
入出力インタフェース１３，２３，３３は、外部からデータの入力を受け付け、外部へデータを出力するためのインタフェースである。入出力インタフェース１３，２３，３３は、具体例としては、キーボードといった入力装置と、ディスプレイといった出力装置とを接続するＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＰＳ／２、ＨＤＭＩ（登録商標、Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）といったコネクタである。また、入出力インタフェース１３，２３，３３は、具体例としては、外部からネットワークを介してデータを送受信するＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）であってもよい。
【００３４】
プロセッサ１１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置１２、又は、プロセッサ１１内のレジスタ又はキャッシュメモリに記憶される。同様に、プロセッサ２１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置２２、又は、プロセッサ２１内のレジスタ又はキャッシュメモリに記憶される。同様に、プロセッサ３１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置３２、又は、プロセッサ３１内のレジスタ又はキャッシュメモリに記憶される。
【００３５】
プロセッサ１１によって実現される各機能を実現するプログラムは、記憶装置１２に記憶されているとした。同様に、プロセッサ２１によって実現される各機能を実現するプログラムは、記憶装置２２に記憶されているとした。同様に、プロセッサ３１によって実現される各機能を実現するプログラムは、記憶装置３２に記憶されているとした。しかし、このプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体に記憶されてもよい。
【００３６】
図３では、プロセッサ１１は、１つだけ示されていた。しかし、鍵生成装置１０は、プロセッサ１１を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、鍵生成装置１０の各部の機能を実現するプログラムの実行を分担する。それぞれのプロセッサは、プロセッサ１１と同じように、プロセッシングを行うＩＣである。同様に、暗号化装置２０は、プロセッサ２１を代替する複数のプロセッサを備えていてもよい。また、復号装置３０は、プロセッサ３１を代替する複数のプロセッサを備えていてもよい。
【００３７】
＊＊＊動作の説明＊＊＊
図３から図９を参照して、実施の形態１に係る暗号システム１の動作を説明する。
実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号プログラムの処理に相当する。
【００３８】
図３及び図６を参照して、実施の形態１に係るＳｅｔｕｐアルゴリズムを説明する。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１０によって実行される。
【００３９】
（ステップＳ１１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、ｄ＝１とを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実行して、数１０８に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１０８】
2017212699.tif 000010
【００４０】
つまり、図７に示すように、実施の形態１では、ｔ＝０，１についての群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔと、群ＧＴと、同種写像φ１とが生成される。
なお、図７に示されるように、Ｇ０からＧ１への変換が“復号鍵生成（ＫｅｙＧｅｎ）”に、Ｇ０×Ｇ＾０からＧＴへの変換が“暗号化（Ｅｎｃ）”に、Ｇ１×Ｇ＾１からＧＴへの変換が“復号（Ｄｅｃ）”に大まかに対応している。
【００４１】
（ステップＳ１２：ハッシュ関数生成処理）
マスター鍵生成部１４は、識別子の空間である体Ｆｑの要素を、群Ｇ０の要素に変換するランダムなハッシュ関数Ｈを生成する。
【００４２】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ１１で生成された公開パラメータｐｋＩＰＧと、ステップＳ１２で生成されたハッシュ関数Ｈとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｇ＾ｔ，ｅｔ）ｔ＝０，１，ＧＴ，Ｈ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ１１で生成されたマスター秘密鍵ｓｋＩＰＧを用いて、マスター秘密鍵ｓｋ：＝φ１を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｓｋを記憶装置１２に書き込む。
【００４３】
つまり、マスター鍵生成部１４は、数１０９に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１０９】
2017212699.tif 000011
【００４４】
図３及び図８を参照して、実施の形態１に係るＫｅｙＧｅｎアルゴリズムを説明する。
ＫｅｙＧｅｎアルゴリズムは、鍵生成装置１０によって実行される。
【００４５】
（ステップＳ２１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。
【００４６】
（ステップＳ２２：鍵要素生成処理）
復号鍵生成部１５は、ステップＳ２１で受け付けられた識別子ＩＤを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。復号鍵生成部１５は、マスター秘密鍵ｓｋに含まれる同種写像φ１で要素ｈ０を変換して、要素ｈ１を生成する。
【００４７】
（ステップＳ２３：鍵要素出力処理）
鍵出力部１６は、ステップＳ２１で受け付けられた識別子ＩＤと、ステップＳ２２で生成された要素ｈ１とを鍵要素とする復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。この際、鍵出力部１６は、何らかの暗号方式で暗号化するといった方法により、復号鍵ｓｋＩＤが第三者に漏えいしないようにする。
【００４８】
つまり、復号鍵生成部１５は、数１１０に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数１１０】
2017212699.tif 000012
【００４９】
図４及び図９を参照して、実施の形態１に係るＥｎｃアルゴリズムを説明する。
Ｅｎｃアルゴリズムは、暗号化装置２０によって実行される。
【００５０】
（ステップＳ３１：入力受付処理）
入力受付部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋと、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。
【００５１】
（ステップＳ３２：暗号文生成処理）
暗号文生成部２５は、ステップＳ３１で受け付けられた識別子ＩＤ’を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。また、暗号文生成部２５は、一様乱数ζを生成する。
暗号文生成部２５は、一様乱数ζを用いて、数１１１に示す要素ｃを生成する。
【数１１１】
2017212699.tif 000013
また、暗号文生成部２５は、要素ｈ０及び一様乱数ζを用いて、数１１２に示す要素ｚを生成する。そして、暗号文生成部２５は、ステップＳ３１で受け付けられたメッセージｍと、要素ｚを用いて要素ｃＴ：＝ｚ・ｍを生成する。
【数１１２】
2017212699.tif 000014
【００５２】
（ステップＳ３３：暗号文出力処理）
暗号文出力部２６は、ステップＳ３１で受け付けられた識別子ＩＤ’と、ステップＳ３２で生成された要素ｃ，ｃＴとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【００５３】
つまり、暗号化装置２０は、数１１３に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数１１３】
2017212699.tif 000015
【００５４】
図５及び図１０を参照して、実施の形態１に係るＤｅｃアルゴリズムを説明する。
Ｄｅｃアルゴリズムは、復号装置３０によって実行される。
【００５５】
（ステップＳ４１：入力受付処理）
入力受付部３４は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋＩＤと、暗号化装置２０によって生成された暗号文ｃｔＩＤ’との入力を受け付ける。
【００５６】
（ステップＳ４２：復号判定処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤに含まれる識別子ＩＤと、暗号文ｃｔＩＤ’に含まれる識別子ＩＤ’とが等しいか否かを判定する。これにより、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤで復号可能かが判定される。
復号部３５は、等しいと判定された場合、つまり復号可能と判定された場合、処理をステップＳ４３に進め、そうでない場合、処理をステップＳ４５に進める。
【００５７】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤに含まれる要素ｈ１と、暗号文ｃｔＩＤ’に含まれる暗号要素ｃとについてペアリング演算ｅ１を行い、要素ｚ’を計算する。復号部３５は、計算された要素ｚ’を用いて、メッセージｍ’：＝ｃＴ・（ｚ’）−１を計算する。
【００５８】
（ステップＳ４４：メッセージ出力処理）
メッセージ出力部３６は、ステップＳ４２で計算されたメッセージｍ’を、入出力インタフェース３３を介して出力する。
【００５９】
（ステップＳ４５：識別情報出力処理）
メッセージ出力部３６は、識別情報⊥を、入出力インタフェース３３を介して出力する。
【００６０】
つまり、復号装置３０は、数１１４に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１１４】
2017212699.tif 000016
【００６１】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号システム１は、ＩＰＧを用いてＩＢＥ方式を実現する。ここで、鍵生成装置１０によって生成されるマスター秘密鍵ｓｋ：＝φ１は、耐量子性を有している。そのため、量子計算機によってでも、マスター秘密鍵ｓｋが破られることがない。
【００６２】
図１１を参照して、実施の形態１の効果を詳しく説明する。
実施の形態１に係るＩＢＥ方式は、秘密鍵が２階層の階層的な構造となっている。つまり、実施の形態１に係るＩＢＥ方式は、秘密鍵が、上位階層のマスター秘密鍵と、下位階層の復号鍵との２階層の構造となっている。
もし、マスター秘密鍵が明らかになると、どんな識別子ＩＤについての復号鍵も、従来の確率的多項式時間マシンを用いて生成可能になる。そのため、攻撃者は、効率的に攻撃するために、初めにマスター秘密鍵を明らかにしようとする。もしマスター秘密鍵が守られると、攻撃者は暗号文を１つ１つ破る必要がある。マスター秘密鍵を攻撃する方法を“マスター鍵レベルアタック”と呼び、暗号文を１つ１つ攻撃する方法を“ユーザレベルアタック”と呼ぶ。
量子計算機が開発された場合、実施の形態１に係る暗号システム１では、ユーザレベルアタックは可能になってしまうものの、マスター鍵レベルアタックは防ぐことができる。
仮に量子計算機が完成したとしても、初期の段階では、既存のコンピュータの場合と同様に、開発速度は比較的遅いものと考えられる。そして、少なくとも、初期の段階では、持ち運び可能なハンディタイプの量子計算機は広まらないし、そのような量子計算機は高額であると考えられる。そのため、ユーザレベルアタックは非常に非効率となると考えられる。実施の形態１に係る暗号システム１では、効率的なＩＢＥ方式を実現しつつ、マスター鍵レベルアタックは防ぐことができる。したがって、実施の形態１に係る暗号システム１で実現されるＩＢＥ方式は、仮に量子計算機が完成したとしても、しばらくの間は効率的かつ有用なものと考えられる。
【００６３】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能がソフトウェアで実現された。変形例１として、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００６４】
図１２から図１４を参照して、変形例１に係る鍵生成装置１０、暗号化装置２０、復号装置３０の構成を説明する。
各部の機能がハードウェアで実現される場合、鍵生成装置１０、暗号化装置２０、復号装置３０は、プロセッサ１１，２１，３１と記憶装置１２，２２，３２とに代えて、処理回路１７，２７，３７を備える。処理回路１７，２７，３７は、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能と、記憶装置１２，２２，３２の機能とを実現する専用の電子回路である。
【００６５】
処理回路１７，２７，３７は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
鍵生成装置１０、暗号化装置２０、復号装置３０は、処理回路１７，２７，３７を代替する複数の処理回路を備えていてもよい。これら複数の処理回路により、全体として各部の機能が実現される。それぞれの処理回路は、処理回路１７，２７，３７と同じように、専用の電子回路である。
【００６６】
＜変形例２＞
変形例２として、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、鍵生成装置１０、暗号化装置２０、復号装置３０の各部のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。
【００６７】
プロセッサ１１，２１，３１と記憶装置１２，２２，３２と処理回路１７，２７，３７とを、総称して「プロセッシングサーキットリー」という。つまり、各部の機能は、プロセッシングサーキットリーにより実現される。
【００６８】
実施の形態２．
実施の形態２では、耐量子性を有するＡＢＥ方式について説明する。実施の形態２では、実施の形態１と異なる点を説明する。
実施の形態２では、ｔ∈［ｄ］について（ｔ，１）∈［ｄ］×［１］＝［ｄ］×Ｕで特定される、多項式サイズのユニバース［ｄ］の要素として属性が与えられる場合を説明する。つまり、後述する属性集合Γ⊂［ｄ］の場合を説明する。
【００６９】
＊＊＊概念の説明＊＊＊
実施の形態２に係るＡＢＥ方式で用いられる概念について説明する。
スパンプログラムについて説明する。スパンプログラムは既存の概念であるため、ここでは以下の説明で必要な範囲だけ簡単に説明する。
【００７０】
体Ｆｑ上のスパンプログラムは、ラベル付けされた行列Ｓ：＝（Ｍ，ρ）である。ここで、行列Ｍは、体Ｆｑ上の（Ｌ行×ｒ列）の行列である。ラベルρは、｛（ｔ，ｖ），（ｔ’，ｖ’），．．．｝から属性に応じて行列Ｍの行に対して付されたラベルである。なお、全ての行が１つの属性にラベル付けされる。つまり、ρ：｛１，．．．，Ｌ｝→｛（ｔ，ｖ），（ｔ’，ｖ’），．．．｝である。
スパンプログラムは、以下の基準に従い、入力を受理又は拒絶する。Γを属性集合とする。つまり、Γ：＝｛（ｔｊ，ｘｊ）｝１≦ｊ≦ｄ’（ｘｊ∈Ｕｔｊ）である。１→∈ｓｐａｎ＜（Ｍｉ）ρ（ｉ）∈Γ＞の場合に限り、スパンプログラムＳは属性集合Γを受理する。スパンプログラムＳが属性集合Γを受理することを、Ｒ（Ｓ，Γ）＝１と表す。つまり、行列Ｍの行（Ｍｉ）ρ（ｉ）∈Γの線形結合によって全ての要素が１のベクトルが得られる場合に限り、スパンプログラムＳは属性集合Γを受理する。行列Ｓをアクセスストラクチャと呼ぶ。
【００７１】
＊＊＊構成の説明＊＊＊
実施の形態２では、復号鍵に復号条件であるポリシーが設定される鍵ポリシー型のＡＢＥ（以下、ＫＰ−ＡＢＥ）方式について説明する。なお、同様の考え方により、暗号文にポリシーが設定される暗号文ポリシー型のＡＢＥを実現することも可能である。
特に、実施の形態２では、タグ付されたＫＰ−ＡＢＥ方式について説明する。タグ付けされたＫＰ−ＡＢＥ方式では、復号鍵のパラメータ（ｔａｇ，Ｓ）と、暗号文のパラメータ（ｔａｇ’，Γ）とに対して、関係Ｒ＋（（ｔａｇ，Ｓ），（ｔａｇ’，Γ））：＝Ｅｑ（ｔａｇ，ｔａｇ’）∧Ｒ（Ｓ，Γ）と定義される。ここで、ｔａｇ＝ｔａｇ’の場合に限り、Ｅｑ（ｔａｇ，ｔａｇ’）＝１である。そして、Ｅｑ（ｔａｇ，ｔａｇ’）＝１∧Ｒ（Ｓ，Γ）＝１の場合に、暗号文を復号鍵で復号できる。
【００７２】
ＫＰ−ＡＢＥ方式は、Ｓｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとを備える。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｋと、マスター秘密鍵ｓｋとを出力する。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター秘密鍵ｓｋと、入力タグｔａｇと、アクセスストラクチャＳ：＝（Ｍ，ρ）とを入力として、入力タグｔａｇ及びアクセスストラクチャＳに対応した復号鍵ｓｋｔａｇ，Ｓを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、メッセージ空間ｍｓｇにおけるメッセージｍと、入力タグｔａｇ’と、属性集合Γ：＝｛（ｔｊ，ｘｊ）｝１≦ｊ≦ｄ’を入力として、暗号文ｃｔｔａｇ’，Γを出力する。
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、入力タグｔａｇ及びアクセスストラクチャＳに対応した復号鍵ｓｋｔａｇ，Ｓと、入力タグｔａｇ’及び属性集合Γの下で暗号化された暗号文ｃｔｔａｇ’，Γとを入力として、メッセージｍ’∈ｍｓｇ、又は、復号に失敗したことを示す識別情報⊥を出力する。
【００７３】
図１５を参照して、実施の形態２に係る暗号システム１の構成を説明する。
暗号システム１は、鍵生成装置１０と、暗号化装置２０と、復号装置３０とを備える。
鍵生成装置１０と暗号化装置２０と復号装置３０とは、コンピュータである。鍵生成装置１０と暗号化装置２０と復号装置３０とは、ネットワークを介して接続されている。
【００７４】
鍵生成装置１０は、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋと、マスター秘密鍵ｓｋとを生成する。また、鍵生成装置１０は、公開パラメータｐｋと、マスター秘密鍵ｓｋと、入力タグｔａｇと、アクセスストラクチャＳ：＝（Ｍ，ρ）とを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｔａｇ，Ｓを生成する。
鍵生成装置１０は、公開パラメータｐｋを公開し、復号鍵ｓｋｔａｇ，Ｓを入力タグｔａｇ及びアクセスストラクチャＳに対応する復号装置３０に出力する。鍵生成装置１０は、マスター秘密鍵ｓｋを保管する。
【００７５】
暗号化装置２０は、公開パラメータｐｋと、メッセージｍと、入力タグｔａｇ’と、属性集合Γとを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ｃｔｔａｇ’，Γを生成する。暗号化装置２０は、暗号文ｃｔｔａｇ’，Γを復号装置３０に出力する。
【００７６】
復号装置３０は、公開パラメータｐｋと、復号鍵ｓｋｔａｇ，Ｓと、暗号文ｃｔｔａｇ’，Γとを入力として、Ｄｅｃアルゴリズムを実行して、メッセージｍ’、又は、復号に失敗したことを示す識別情報⊥を生成する。
【００７７】
図１６に示す鍵生成装置１０と、図１７に示す暗号化装置２０と、図１８に示す復号装置３０との構成は、それぞれ図３に示す鍵生成装置１０と、図４に示す暗号化装置２０と、図５に示す復号装置３０との構成と同じである。但し、各構成要素で入出力される情報が異なる。
【００７８】
＊＊＊動作の説明＊＊＊
図１６から図１８と、図６から図１０とを参照して、実施の形態２に係る暗号システム１の動作を説明する。
実施の形態２に係る暗号システム１の動作は、実施の形態２に係る暗号方法に相当する。また、実施の形態２に係る暗号システム１の動作は、実施の形態２に係る暗号プログラムの処理に相当する。
【００７９】
図１６及び図６を参照して、実施の形態２に係るＳｅｔｕｐアルゴリズムを説明する。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１０によって実行される。
【００８０】
（ステップＳ１１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、１以上の整数ｄとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実行して、数１１５に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１１５】
2017212699.tif 000017
【００８１】
つまり、図１に示すように、実施の形態１では、ｔ＝０，１，．．．，ｄについての群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔと、群ＧＴと、ｔ＝１，．．．，ｄについての同種写像φｔとが生成される。つまり、ｄ＋１個のペアリング群が用いられる。
ここで、ｔ＝１，．．．，ｄの群Ｇｔ及び群Ｇ＾ｔに属性が設定される。したがって、整数ｄの値は、設定したい属性の数に応じて決定される。
【００８２】
（ステップＳ１２：ハッシュ関数生成処理）
実施の形態１と同様に、マスター鍵生成部１４は、ハッシュ関数Ｈを生成する。
【００８３】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ１１で生成された公開パラメータｐｋＩＰＧと、ステップＳ１２で生成されたハッシュ関数Ｈとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｇ＾ｔ，ｅｔ）ｔ∈［０，ｄ］，ＧＴ，Ｈ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ１１で生成されたマスター秘密鍵ｓｋＩＰＧを用いて、マスター秘密鍵ｓｋ：＝（φｔ）ｔ∈［ｄ］を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｓｋを記憶装置１２に書き込む。
【００８４】
つまり、マスター鍵生成部１４は、数１１６に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１１６】
2017212699.tif 000018
【００８５】
図１６及び図８を参照して、実施の形態２に係るＫｅｙＧｅｎアルゴリズムを説明する。
ＫｅｙＧｅｎアルゴリズムは、鍵生成装置１０によって実行される。
【００８６】
（ステップＳ２１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋｔａｇ，Ｓを使用するユーザの入力タグｔａｇ及びアクセスストラクチャＳ：＝（Ｍ，ρ）の入力を受け付ける。アクセスストラクチャＳは、復号鍵ｓｋｔａｇ，Ｓで復号可能な範囲を示すものである。
【００８７】
（ステップＳ２２：鍵要素生成処理）
復号鍵生成部１５は、ステップＳ２１で受け付けられた入力タグｔａｇを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。
復号鍵生成部１５は、１→・ｕ→＝１であるベクトルｕ→をランダムに選択する。復号鍵生成部１５は、ｉ∈［Ｌ］に対して、ｓｉ：＝Ｍｉ・ｕ→とし、ｔ：＝ρ（ｉ）として、数１１７に示すように、マスター秘密鍵ｓｋに含まれる同種写像φｔで要素ｈ０を変換して、要素ｋｉを生成する。
【数１１７】
2017212699.tif 000019
【００８８】
（ステップＳ２３：鍵要素出力処理）
鍵出力部１６は、ステップＳ２１で受け付けられた入力タグｔａｇ及びアクセスストラクチャＳと、ステップＳ２２で生成されたｉ∈［Ｌ］についての要素ｋｉとを鍵要素とする復号鍵ｓｋｔａｇ，Ｓを、入出力インタフェース１３を介して復号装置３０に出力する。この際、鍵出力部１６は、何らかの暗号方式で暗号化するといった方法により、復号鍵ｓｋｔａｇ，Ｓが第三者に漏えいしないようにする。
【００８９】
つまり、復号鍵生成部１５は、数１１８に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｔａｇ，Ｓを生成する。
【数１１８】
2017212699.tif 000020
【００９０】
図１７及び図９を参照して、実施の形態２に係るＥｎｃアルゴリズムを説明する。
Ｅｎｃアルゴリズムは、暗号化装置２０によって実行される。
【００９１】
（ステップＳ３１：入力受付処理）
入力受付部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋと、暗号化対象のメッセージｍと、復号条件となる入力タグｔａｇ’及び属性集合Γとの入力を受け付ける。
【００９２】
（ステップＳ３２：暗号文生成処理）
暗号文生成部２５は、ステップＳ３１で受け付けられた入力タグｔａｇ’を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。また、暗号文生成部２５は、一様乱数ζを生成する。
暗号文生成部２５は、属性集合Γに含まれる各整数ｔについて、一様乱数ζを用いて、数１１９に示す要素ｃｔを生成する。
【数１１９】
2017212699.tif 000021
また、暗号文生成部２５は、要素ｈ０及び一様乱数ζを用いて、数１２０に示す要素ｚを生成する。そして、暗号文生成部２５は、ステップＳ３１で受け付けられたメッセージｍと、要素ｚを用いて要素ｃＴ：＝ｚ・ｍを生成する。
【数１２０】
2017212699.tif 000022
【００９３】
（ステップＳ３３：暗号文出力処理）
暗号文出力部２６は、ステップＳ３１で受け付けられた入力タグｔａｇ’及び属性集合Γと、ステップＳ３２で生成された属性集合Γに含まれる各整数ｔについての要素ｃｔ及び要素ｃＴとを暗号要素とする暗号文ｃｔｔａｇ’，Γを、入出力インタフェース２３を介して復号装置３０に出力する。
【００９４】
つまり、暗号化装置２０は、数１２１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｔａｇ’，Γを生成する。
【数１２１】
2017212699.tif 000023
【００９５】
図１８及び図１０を参照して、実施の形態２に係るＤｅｃアルゴリズムを説明する。
Ｄｅｃアルゴリズムは、復号装置３０によって実行される。
【００９６】
（ステップＳ４１：入力受付処理）
入力受付部３４は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋｔａｇ，Ｓと、暗号化装置２０によって生成された暗号文ｃｔｔａｇ’，Γとの入力を受け付ける。
【００９７】
（ステップＳ４２：復号判定処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋｔａｇ，Ｓに含まれる入力タグｔａｇと、暗号文ｃｔｔａｇ’，Γに含まれる入力タグｔａｇ’とが等しいか否かを判定する。また、復号部３５は、復号鍵ｓｋｔａｇ，Ｓに含まれるアクセスストラクチャＳが、暗号文ｃｔｔａｇ’，Γに含まれる属性集合Γを受理するか否かを判定する。これにより、暗号文ｃｔｔａｇ’，Γを復号鍵ｓｋｔａｇ，Ｓで復号可能かが判定される。
復号部３５は、入力タグｔａｇと入力タグｔａｇ’とが等しいと判定され、かつ、アクセスストラクチャＳが属性集合Γを受理すると判定された場合、処理をステップＳ４３に進め、そうでない場合、処理をステップＳ４５に進める。
【００９８】
（ステップＳ４３：復号処理）
復号部３５は、ρ（ｉ）∈Γについて、数１２２を満たす補完係数αｉを計算する。なお、Ｍｉは、行列Ｍのｉ行目である。
【数１２２】
2017212699.tif 000024
復号部３５は、計算された補完係数αｉを用いて、ステップＳ４１で受け付けられた復号鍵ｓｋｔａｇ，Ｓに含まれる要素ｋｉと、暗号文ｃｔｔａｇ’，Γに含まれる暗号要素ｃｔとについて数１２３に示すペアリング演算を行い、要素ｚ’を計算する。
【数１２３】
2017212699.tif 000025
復号部３５は、計算された要素ｚ’を用いて、メッセージｍ’：＝ｃＴ・（ｚ’）−１を計算する。
【００９９】
ステップＳ４４からステップＳ４５の処理は、実施の形態１と同じである。
【０１００】
つまり、復号装置３０は、数１２４に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１２４】
2017212699.tif 000026
【０１０１】
数１２５に示すように、ステップＳ４３で暗号文ｃｔｔａｇ’，Γを復号鍵ｓｋｔａｇ，Ｓで復号可能である。
【数１２５】
2017212699.tif 000027
【０１０２】
＊＊＊実施の形態２の効果＊＊＊
以上のように、実施の形態２に係る暗号システム１は、ＩＰＧを用いてＡＢＥ方式を実現する。ここで、鍵生成装置１０によって生成されるマスター秘密鍵ｓｋ：＝φｔは、実施の形態１と同様に耐量子性を有している。そのため、量子計算機によってでも、マスター秘密鍵ｓｋが破られることがない。
【０１０３】
実施の形態３．
実施の形態３では、どの部分ユニバース識別子ｔについても属性ｘｔ：＝（ｘｔ，ｊ）ｊ∈［ｎ］がユニバースＵ：＝｛０，１｝ｎの要素である場合におけるＡＢＥ方式について説明する。実施の形態３では、実施の形態２と異なる点を説明する。
【０１０４】
実施の形態３では、ＡＢＥの小さなユニバースの２つのインスタンスｔ∈［ｄ］及びｊ∈［ｎ］についての階層的な構造が用いられる。そして、実施の形態３では、下位の階層のインスタンスにおいて、ｎ−ｏｕｔ−ｏｆ−２ｎの秘密共有述語の特別な形態が、長さｎの２値の識別子ｘｔに対する識別子マッチングに用いられる。
【０１０５】
＊＊＊動作の説明＊＊＊
図１６から図１８と、図６から図１０とを参照して、実施の形態３に係る暗号システム１の動作を説明する。
実施の形態３に係る暗号システム１の動作は、実施の形態３に係る暗号方法に相当する。また、実施の形態３に係る暗号システム１の動作は、実施の形態３に係る暗号プログラムの処理に相当する。
【０１０６】
図１６及び図６を参照して、実施の形態３に係るＳｅｔｕｐアルゴリズムを説明する。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１０によって実行される。
【０１０７】
（ステップＳ１１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、１以上の整数ｄ及び１以上の整数ｎについての整数２ｄｎとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，２ｄｎ）を実行して、数１２６に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１２６】
2017212699.tif 000028
【０１０８】
つまり、実施の形態１では、ｔ＝０，１，．．．，ｄとｊ＝１，．．．，ｎとι＝０，１とについての群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιとペアリング演算ｅｔと、群ＧＴと、ｔ＝１，．．．，ｄとｊ＝１，．．．，ｎとι＝０，１とについての同種写像φｔ，ｊ，ιとが生成される。つまり、２ｄｎ＋１個のペアリング群が用いられる。
ここで、ｔ＝１，．．．，ｄとｊ＝１，．．．，ｎとι＝０，１の群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιに属性が設定される。したがって、整数ｄ，ｎの値は、設定したい属性の数に応じて決定される。
【０１０９】
（ステップＳ１２：ハッシュ関数生成処理）
実施の形態１と同様に、マスター鍵生成部１４は、ハッシュ関数Ｈを生成する。
【０１１０】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ１１で生成された公開パラメータｐｋＩＰＧと、ステップＳ１２で生成されたハッシュ関数Ｈとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｇ＾ｔ，ｅｔ）ｔ∈［０，ｄ］，ｊ∈［ｎ］，ι∈［０，１］，ＧＴ，Ｈ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ１１で生成されたマスター秘密鍵ｓｋＩＰＧを用いて、マスター秘密鍵ｓｋ：＝（φｔ，ｊ，ι）ｔ∈［ｄ］，ｊ∈［ｎ］，ι∈［０，１］を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｓｋを記憶装置１２に書き込む。
【０１１１】
つまり、マスター鍵生成部１４は、数１２７に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１２７】
2017212699.tif 000029
【０１１２】
図１６及び図８を参照して、実施の形態２に係るＫｅｙＧｅｎアルゴリズムを説明する。
ＫｅｙＧｅｎアルゴリズムは、鍵生成装置１０によって実行される。
【０１１３】
ステップＳ２１の処理は、実施の形態２と同じである。
【０１１４】
（ステップＳ２２：鍵要素生成処理）
復号鍵生成部１５は、ステップＳ２１で受け付けられた入力タグｔａｇを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。
復号鍵生成部１５は、１→・ｕ→＝１であるベクトルｕ→をランダムに選択する。復号鍵生成部１５は、ｉ∈［Ｌ］に対して、ｓｉ：＝Ｍｉ・ｕ→とし、ｓｉ＝Σｊ＝１ｎτｉ，ｊである乱数τ→：＝（τｉ，ｊ）を選択する。復号鍵生成部１５は、乱数τ→を用いて、数１２８に示すように、マスター秘密鍵ｓｋに含まれる同種写像φｔ，ｊ，ιで要素ｈ０を変換して、要素ｋｉ，ｊを生成する。
【数１２８】
2017212699.tif 000030
【０１１５】
（ステップＳ２３：鍵要素出力処理）
鍵出力部１６は、ステップＳ２１で受け付けられた入力タグｔａｇ及びアクセスストラクチャＳと、ステップＳ２２で生成されたｉ∈［Ｌ］及びｊ∈［ｎ］についての要素ｋｉ，ｊとを鍵要素とする復号鍵ｓｋｔａｇ，Ｓを、入出力インタフェース１３を介して復号装置３０に出力する。この際、鍵出力部１６は、何らかの暗号方式で暗号化するといった方法により、復号鍵ｓｋｔａｇ，Ｓが第三者に漏えいしないようにする。
【０１１６】
つまり、復号鍵生成部１５は、数１２９に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｔａｇ，Ｓを生成する。
【数１２９】
2017212699.tif 000031
【０１１７】
図１７及び図９を参照して、実施の形態２に係るＥｎｃアルゴリズムを説明する。
Ｅｎｃアルゴリズムは、暗号化装置２０によって実行される。
【０１１８】
ステップＳ３１の処理は、実施の形態２と同じである。
【０１１９】
（ステップＳ３２：暗号文生成処理）
暗号文生成部２５は、ステップＳ３１で受け付けられた入力タグｔａｇ’を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。また、暗号文生成部２５は、一様乱数ζを生成する。
暗号文生成部２５は、属性集合Γに含まれる（ｔ，ｘｔ：＝（ｘｔ，ｊ）∈｛０，１｝ｎ）∈Γの各整数ｔ及び各整数ｊについて、一様乱数ζを用いて、数１３０に示す要素ｃｔ，ｊを生成する。
【数１３０】
2017212699.tif 000032
また、暗号文生成部２５は、要素ｈ０及び一様乱数ζを用いて、数１３１に示す要素ｚを生成する。そして、暗号文生成部２５は、ステップＳ３１で受け付けられたメッセージｍと、要素ｚを用いて要素ｃＴ：＝ｚ・ｍを生成する。
【数１３１】
2017212699.tif 000033
【０１２０】
（ステップＳ３３：暗号文出力処理）
暗号文出力部２６は、ステップＳ３１で受け付けられた入力タグｔａｇ’及び属性集合Γと、ステップＳ３２で生成された属性集合Γに含まれる各整数ｔ及びｊ∈［ｎ］についての要素ｃｔ，ｊ及び要素ｃＴとを暗号要素とする暗号文ｃｔｔａｇ’，Γを、入出力インタフェース２３を介して復号装置３０に出力する。
【０１２１】
つまり、暗号化装置２０は、数１３２に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｔａｇ’，Γを生成する。
【数１３２】
2017212699.tif 000034
【０１２２】
図１８及び図１０を参照して、実施の形態２に係るＤｅｃアルゴリズムを説明する。
Ｄｅｃアルゴリズムは、復号装置３０によって実行される。
【０１２３】
ステップＳ４１からステップＳ４２の処理は、実施の形態２と同じである。
【０１２４】
（ステップＳ４３：復号処理）
復号部３５は、数１３３を満たす補完係数αｉを計算する。
【数１３３】
2017212699.tif 000035
復号部３５は、計算された補完係数αｉを用いて、ステップＳ４１で受け付けられた復号鍵ｓｋｔａｇ，Ｓに含まれる要素ｋｉ，ｊと、暗号文ｃｔｔａｇ’，Γに含まれる暗号要素ｃｔ，ｊとについて数１３４に示すペアリング演算を行い、要素ｚ’を計算する。
【数１３４】
2017212699.tif 000036
復号部３５は、計算された要素ｚ’を用いて、メッセージｍ’：＝ｃＴ・（ｚ’）−１を計算する。
【０１２５】
ステップＳ４４からステップＳ４５の処理は、実施の形態２と同じである。
【０１２６】
つまり、復号装置３０は、数１３５に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１３５】
2017212699.tif 000037
【０１２７】
数１３６に示すように、ステップＳ４３で暗号文ｃｔｔａｇ’，Γを復号鍵ｓｋｔａｇ，Ｓで復号可能である。
【数１３６】
2017212699.tif 000038
【０１２８】
＊＊＊実施の形態３の効果＊＊＊
以上のように、実施の形態３に係る暗号システム１は、ＩＰＧを用いて大きいユニバースについてのＡＢＥ方式を実現する。ここで、鍵生成装置１０によって生成されるマスター秘密鍵ｓｋ：＝φｔは、実施の形態２と同様に耐量子性を有している。そのため、量子計算機によってでも、マスター秘密鍵ｓｋが破られることがない。
【０１２９】
実施の形態４．
実施の形態４では、階層的なＩＢＥ（以下、ＨＩＢＥ）方式について説明する。実施の形態４では、実施の形態１と異なる点を説明する。
【０１３０】
＊＊＊動作の説明＊＊＊
図３から図９を参照して、実施の形態４に係る暗号システム１の動作を説明する。
実施の形態４に係る暗号システム１の動作は、実施の形態４に係る暗号方法に相当する。また、実施の形態４に係る暗号システム１の動作は、実施の形態４に係る暗号プログラムの処理に相当する。
【０１３１】
図３及び図６を参照して、実施の形態１に係るＳｅｔｕｐアルゴリズムを説明する。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１０によって実行される。
【０１３２】
ステップＳ１１の処理は、実施の形態１と同じである。
【０１３３】
（ステップＳ１２：ハッシュ関数生成処理）
マスター鍵生成部１４は、ｔ＝０，１について、識別子の空間である体Ｆｑの要素を、群Ｇｔの要素に変換するランダムなハッシュ関数Ｈｔを生成する。
【０１３４】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ１１で生成された公開パラメータｐｋＩＰＧと、ステップＳ１２で生成されたハッシュ関数Ｈとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｇ＾ｔ，ｅｔ，Ｈｔ）ｔ＝０，１，ＧＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ１１で生成されたマスター秘密鍵ｓｋＩＰＧを用いて、マスター秘密鍵ｓｋ：＝φ１を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｓｋを記憶装置１２に書き込む。
【０１３５】
つまり、マスター鍵生成部１４は、数１３７に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１３７】
2017212699.tif 000039
【０１３６】
図３及び図８を参照して、実施の形態４に係るＫｅｙＧｅｎアルゴリズムを説明する。
ＫｅｙＧｅｎアルゴリズムは、鍵生成装置１０によって実行される。
【０１３７】
（ステップＳ２１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。ここでは、識別子ＩＤは、ｉ∈［ｊ］についてのＩＤｉから構成される。ｊは、２以上の整数である。
【０１３８】
（ステップＳ２２：鍵要素生成処理）
復号鍵生成部１５は、ｉ∈［ｊ−１］について、数１３８に示すように、要素ｄ＾ｉを生成する。
【数１３８】
2017212699.tif 000040
復号鍵生成部１５は、ステップＳ２１で受け付けられた識別子ＩＤを構成するＩＤ１を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈ０を計算して、群Ｇ０の要素である要素ｈ１を生成する。また、復号鍵生成部１５は、ｉ∈［２，ｊ］について、識別子ＩＤを構成するＩＤ１，．．．，ＩＤｉを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈ１を計算して、群Ｇ１の要素である要素ｈｉを生成する。そして、復号鍵生成部１５は、数１３９に示すように、マスター秘密鍵ｓｋに含まれる同種写像φ１で要素ｈ１を変換した要素ｄｊを生成する。
【数１３９】
2017212699.tif 000041
【０１３９】
（ステップＳ２３：鍵要素出力処理）
鍵出力部１６は、ステップＳ２１で受け付けられた識別子ＩＤと、ステップＳ２２で生成された、ｉ∈［ｊ−１］についての要素ｄ＾ｊ及び要素ｄｊとを鍵要素とする復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。この際、鍵出力部１６は、何らかの暗号方式で暗号化するといった方法により、復号鍵ｓｋＩＤが第三者に漏えいしないようにする。
【０１４０】
つまり、復号鍵生成部１５は、数１４０に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数１４０】
2017212699.tif 000042
【０１４１】
図４及び図９を参照して、実施の形態１に係るＥｎｃアルゴリズムを説明する。
Ｅｎｃアルゴリズムは、暗号化装置２０によって実行される。
【０１４２】
（ステップＳ３１：入力受付処理）
入力受付部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋと、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。ここでは、識別子ＩＤ’は、ｉ∈［ｊ］についてのＩＤ’ｉから構成される。
【０１４３】
（ステップＳ３２：暗号文生成処理）
暗号文生成部２５は、一様乱数ζを生成する。暗号文生成部２５は、一様乱数ζを用いて、数１４１に示す要素ｃ＾０を生成する。
【数１４１】
2017212699.tif 000043
暗号文生成部２５は、ｉ∈［２，ｊ］について、識別子ＩＤを構成するＩＤ’１，．．．，ＩＤ’ｉを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈ１を計算して、群Ｇ１の要素である要素ｈｉを生成する。暗号文生成部２５は、要素ｈｉを用いて、数１４２に示す要素ｃｉを生成する。
【数１４２】
2017212699.tif 000044
暗号文生成部２５は、ステップＳ３１で受け付けられた識別子ＩＤ’を構成するＩＤ’１を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈ０を計算して、群Ｇ０の要素である要素ｈ１を生成する。また、暗号文生成部２５は、要素ｈ１及び一様乱数ζを用いて、数１４３に示す要素ｚを生成する。そして、暗号文生成部２５は、ステップＳ３１で受け付けられたメッセージｍと、要素ｚを用いて要素ｃＴ：＝ｚ・ｍを生成する。
【数１４３】
2017212699.tif 000045
【０１４４】
（ステップＳ３３：暗号文出力処理）
暗号文出力部２６は、ステップＳ３１で受け付けられた識別子ＩＤ’と、ステップＳ３２で生成された要素ｃ＾０，（ｃｉ）ｉ∈［２，ｊ］，ｃＴとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【０１４５】
つまり、暗号化装置２０は、数１４４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数１４４】
2017212699.tif 000046
【０１４６】
図５及び図１０を参照して、実施の形態１に係るＤｅｃアルゴリズムを説明する。
Ｄｅｃアルゴリズムは、復号装置３０によって実行される。
【０１４７】
ステップＳ４１からステップＳ４２の処理は、実施の形態１と同じである。
【０１４８】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤに含まれる要素ｄ＾ｊ及び要素ｄｊと、暗号文ｃｔＩＤ’に含まれる要素ｃ＾０及び要素ｃｉとについて数１４５に示す演算を行い、要素ｚ’を計算する。復号部３５は、計算された要素ｚ’を用いて、メッセージｍ’：＝ｃＴ・（ｚ’）−１を計算する。
【数１４５】
2017212699.tif 000047
【０１４９】
ステップＳ４４からステップＳ４５の処理は、実施の形態１と同じである。
【０１５０】
つまり、復号装置３０は、数１４６に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１４６】
2017212699.tif 000048
【０１５１】
数１４７に示すように、ステップＳ４３で暗号文ｃｔｔａｇ’，Γを復号鍵ｓｋｔａｇ，Ｓで復号可能である。
【数１４７】
2017212699.tif 000049
【０１５２】
＊＊＊実施の形態４の効果＊＊＊
以上のように、実施の形態４に係る暗号システム１は、ＩＰＧを用いてＨＩＢＥ方式を実現する。ここで、鍵生成装置１０によって生成されるマスター秘密鍵ｓｋ：＝φｔは、実施の形態１と同様に耐量子性を有している。そのため、量子計算機によってでも、マスター秘密鍵ｓｋが破られることがない。
【０１５３】
実施の形態５．
実施の形態５では、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）について、楕円曲線を用いて具体的に説明する。
【０１５４】
＊＊＊動作の説明＊＊＊
図１９を参照して、実施の形態５に係るＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）の処理を説明する。
【０１５５】
（ステップＳ５１：要素生成処理）
マスター鍵生成部１４は、十分に大きい、奇素数ｐについての超楕円曲線Ｅ０／Ｆｐ２（ここで、ｐ２はｐ２）をランダムに生成する。
マスター鍵生成部１４は、適切な（Ｌ〜，κ）と、楕円曲線Ｅ０の部分群から構成される位数ｒの非対称ペアリング群（Ｇ０，Ｇ＾０，ＧＴ；ｅ０）を生成する。ｅ０は、楕円曲線Ｅ０におけるヴェイユペアリングｅｗｅｉｌ，０から、どのｈ０∈Ｇ０及びｈ＾０∈Ｇ＾０に対してもｅ０（ｈ０，ｈ＾０）：＝ｅｗｅｉｌ，０（ｈ０，ｈ＾０）Ψと定義される。Ψ＝（Ｌ〜）κである。
マスター鍵生成部１４は、群Ｇ０から要素ｇ０を一様に選択し、群Ｇ＾０から要素ｇ＾０を一様に選択する。
【０１５６】
（ステップＳ５２：同種生成処理）
マスター鍵生成部１４は、アルゴリズムＩｓｏｇＬ〜，κ（Ｅ０）を実行して、ｔ∈［ｄ］について、楕円曲線Ｅ０と同種となる楕円曲線Ｅｔと、楕円曲線Ｅ０から楕円曲線Ｅｔへの同種写像を計算するためのトラップドアξｔとをランダムに生成する。アルゴリズムＩｓｏｇＬ〜，κ（Ｅ０）として、図２０に示す非特許文献３に記載されたＩｓｏｇＬ〜，κｄｊｐアルゴリズムを用いることができる。また、アルゴリズムＩｓｏｇＬ〜，κ（Ｅ０）として、図２１に示す非特許文献４，５に記載されたＩｓｏｇＬ〜，κｃｌｇアルゴリズムを用いることができる。
【０１５７】
（ステップＳ５３：同種要素生成処理）
マスター鍵生成部１４は、ステップＳ５２で生成された楕円曲線Ｅｔ及びトラップドアξｔを用いて、φｔ：＝φξｔと、Ｇｔ：＝φｔ（Ｇ０）及びＧ＾ｔ：＝φｔ（Ｇ＾０）と、ｇｔ：＝φｔ（ｇ０）及びｇ＾ｔ：＝φｔ（ｇ＾０）と、ｈｔ∈Ｇｔ及びｈ＾ｔ∈Ｇ＾ｔに対してｅｔ（ｈｔ，ｈ＾ｔ）：＝ｅｗｅｉｌ，ｔ（ｈｔ，ｈ＾ｔ）と設定する。ここで、ｅｗｅｉｌ，ｔは、楕円曲線Ｅｔにおけるヴェイユペアリングである。
【０１５８】
（ステップＳ５４：要素出力処理）
マスター鍵生成部１４は、ステップＳ５１及びステップＳ５３で生成された（Ｇｔ，Ｇ＾ｔ，ｇｔ，ｇ＾ｔ，ｅｔ）ｔ∈［０，ｄ］，ＧＴを公開パラメータｐｋＩＰＧとし、（φｔ）ｔ∈［ｄ］に対する（ξｔ）ｔ∈［ｄ］をマスター秘密鍵ｓｋＩＰＧとして出力する。
【０１５９】
つまり、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）は、数１４８に示す通りである。
【数１４８】
2017212699.tif 000050
【０１６０】
＊＊＊実施の形態５の効果＊＊＊
以上のように、実施の形態５に係る暗号システム１では、楕円曲線を用いてＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実現できる。
【０１６１】
実施の形態６．
実施の形態１〜４では、記載を単純化し、理解を容易にするために、楕円曲線を用いた詳細な記載を省略した。実施の形態６では、楕円曲線を用いた具体的な構成について説明する。実施の形態６では、実施の形態１で説明したＩＢＥ方式と、実施の形態２で説明したＡＢＥ方式とについて説明する。
実施の形態３で説明したＡＢＥ方式と、実施の形態４で説明したＨＩＢＥ方式とについても、同様の方法により、楕円曲線を用いた具体的な構成とすることが可能である。
【０１６２】
＊＊＊動作の説明＊＊＊
実施の形態１で説明したＩＢＥ方式について説明する。
Ｓｅｔｕｐアルゴリズムは、数１４９のようになる。
【数１４９】
2017212699.tif 000051
【０１６３】
ＫｅｙＧｅｎアルゴリズムは、数１５０のようになる。
【数１５０】
2017212699.tif 000052
【０１６４】
Ｅｎｃアルゴリズムは、数１５１のようになる。
【数１５１】
2017212699.tif 000053
【０１６５】
Ｄｅｃアルゴリズムは、数１５２のようになる。
【数１５２】
2017212699.tif 000054
【０１６６】
数１５３に示すように、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤで復号可能である。ここで、ｄｅｇ（φ１）＝Ｌ〜κである。
【数１５３】
2017212699.tif 000055
【０１６７】
実施の形態２で説明したＡＢＥ方式について説明する。
Ｓｅｔｕｐアルゴリズムは、数１５４のようになる。
【数１５４】
2017212699.tif 000056
【０１６８】
ＫｅｙＧｅｎアルゴリズムは、数１５５のようになる。
【数１５５】
2017212699.tif 000057
【０１６９】
Ｅｎｃアルゴリズムは、数１５６のようになる。
【数１５６】
2017212699.tif 000058
【０１７０】
Ｄｅｃアルゴリズムは、数１５７のようになる。
【数１５７】
2017212699.tif 000059
【０１７１】
数１５８に示すように、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤで復号可能である。
【数１５８】
2017212699.tif 000060
【０１７２】
＊＊＊実施の形態６の効果＊＊＊
以上のように、実施の形態６に係る暗号システム１では、楕円曲線を用いた具体的にＩＢＥ方式及びＡＢＥ方式を構成することができる。
【０１７３】
実施の形態７．
実施の形態１〜６では、同種写像とペアリング演算とを用いて、ＩＰＧを構成した。しかし、同種写像に代えて、トラップドア準同型写像（以下、ＴＨ）を用いてＩＰＧを構成してもよい。
【０１７４】
以下の３つの条件を満たす場合、素数位数ｑの２つのランダムに選択された巡回群Ｇ０，Ｇ１についての写像φ：＝φξ：Ｇ０→Ｇ１がＴＨである。
（条件１：準同型写像）
写像φが自明でない準同型写像であること。自明でないとは、例えば、加法群に対して非ゼロであることである。
（条件２：ＴＨ−ＤＨ（ＴＨ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）の難治性仮定）
ランダムに選択された写像φと群Ｇ０から一様に選択されたｇ０，ｇについて、（ｇ０，φ（ｇ０），ｇ）が与えられた場合に、どんな確率的多項式時間マシンＢも無視し得る確率でしかφ（ｇ）を計算しないこと。
（条件３：多項式サイズのトラップドア）
φ：＝φξについての多項式サイズのトラップドアξが与えられると、どんなｇ∈Ｇ０に対してもφ（ｇ）を計算する確率的多項式時間マシンＢが存在すること。
【０１７５】
楕円曲線を用いたＴＨの例として以下の３つがある。以下の３つの例において、群の肩に“〜”が付されている場合、その群はペアリング群である。
（例１：累乗法）
Ｇ０：＝Ｇ１：＝Ｇ〜は、楕円曲線巡回群である。φ：＝φξは、群Ｇにおける累乗法、つまり曲線上のスカラー乗法である。つまり、φξ：ｇ→ｇξである。ここで、ξはスカラーである。
（例２：ペアリング）
Ｇ０：＝Ｇ〜，Ｇ１：＝Ｇ〜Ｔは、ペアリング群である。φ：＝φξは、Ｇ〜上のペアリング演算である。つまり、φξ：ｇ→ｅ（ｇ，ξ）である。ここで、ξは、対称ペアリングの場合の群Ｇ、又は、非対称ペアリングの場合の群Ｇ＾の要素である。
（例３：同種写像）
Ｇ０：＝Ｇ〜０，Ｇ１：＝Ｇ〜１は、それぞれ２つの曲線Ｅ，Ｅ’から得られる２つの異なる楕円曲線巡回群である。φ：＝φξは、群Ｇ〜０から群Ｇ〜１への同種写像である。つまり、φξ：Ｅ→Ｅ’：＝Ｅ／Ｃである。ここで、ξ：＝Ｃは、曲線Ｅの巡回部分群である。
【符号の説明】
【０１７６】
１  暗号システム、１０  鍵生成装置、１１  プロセッサ、１２  記憶装置、１３  入出力インタフェース、１４  マスター鍵生成部、１５  復号鍵生成部、１６  鍵出力部、２０  暗号化装置、２１  プロセッサ、２２  記憶装置、２３  入出力インタフェース、２４  入力受付部、２５  暗号文生成部、２６  暗号文出力部、３０  復号装置、３１  プロセッサ、３２  記憶装置、３３  入出力インタフェース、３４  入力受付部、３５  復号部、３６  メッセージ出力部。
【図１】
2017212699.tif 000076
【図２】
2017212699.tif 000077
【図３】
2017212699.tif 000078
【図４】
2017212699.tif 000079
【図５】
2017212699.tif 000080
【図６】
2017212699.tif 000081
【図７】
2017212699.tif 000082
【図８】
2017212699.tif 000083
【図９】
2017212699.tif 000084
【図１０】
2017212699.tif 000085
【図１１】
2017212699.tif 000086
【図１２】
2017212699.tif 000087
【図１３】
2017212699.tif 000088
【図１４】
2017212699.tif 000089
【図１５】
2017212699.tif 000090
【図１６】
2017212699.tif 000091
【図１７】
2017212699.tif 000092
【図１８】
2017212699.tif 000093
【図１９】
2017212699.tif 000094
【図２０】
2017212699.tif 000095
【図２１】
2017212699.tif 000096