(57)【要約】      （修正有）【課題】ランダムオラクルを用いずにユニバーサル比率が最適なＩＤベースハッシュ証明系構成装置を提供する。【解決手段】ＩＤベースハッシュ証明系構成装置は、内積値暗号のセットアップアルゴリズムと、疑似ランダム関数ＰＲＦの鍵空間からランダムに選択された鍵とを用いて、公開パラメータとマスター秘密鍵とを出力するセットアップ部と、｛０，１｝からｎ個のビット値をランダムに選択した上で、選択されたビット値と、内積値暗号の鍵生成アルゴリズムと、疑似ランダム関数とを用いて、鍵生成アルゴリズムの出力とビット値とによって構成される秘密鍵を出力する鍵生成部と、内積値暗号の暗号化アルゴリズムを用いて、暗号文と鍵とを出力するカプセル化部と、暗号化アルゴリズムを用いて不正暗号文を出力する不正カプセル化部と、内積値暗号の復号アルゴリズムを用いて、鍵を出力する復号部と、を有する。【選択図】図１
2020034662.tif 000002
【特許請求の範囲】
【請求項１】
セキュリティパラメータ１λを入力として、内積値暗号のセットアップアルゴリズムＳｅｔｕｐＩＰＥが含まれるセットアップアルゴリズムＳｅｔｕｐＭＩＢＥと、疑似ランダム関数ＰＲＦの鍵空間からランダムに選択された鍵Ｋとを用いて、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）とを出力するセットアップ手段と、
前記公開パラメータｐｐと、前記マスター秘密鍵（ｍｓｋ，Ｋ）と、識別子ｉｄとを入力として、｛０，１｝からｎ個のビット値ｒｉ（１≦ｉ≦ｎ）をランダムに選択した上で、選択されたビット値ｒｉ（１≦ｉ≦ｎ）と、前記内積値暗号の鍵生成アルゴリズムＫｅｙＧｅｎＩＰＥが含まれる鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥと、前記疑似ランダム関数ＰＲＦとを用いて、前記鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥの出力ｓｋｉｄ´と前記ビット値ｒｉ（１≦ｉ≦ｎ）とによって構成される秘密鍵ｓｋｉｄ＝（ｓｋｉｄ´，｛ｒｉ｝ｉ∈［ｎ］）を出力する鍵生成手段と、
前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記内積値暗号の暗号化アルゴリズムＥｎｃＩＰＥが含まれる暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、暗号文ｃｔと鍵ｋとを出力するカプセル化手段と、
前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、不正暗号文ｃｔ´を出力する不正カプセル化手段と、
前記公開パラメータｐｐと、前記秘密鍵ｓｋｉｄと、前記識別子ｉｄと、前記暗号文ｃｔとを入力として、前記内積値暗号の復号アルゴリズムＤｅｃＩＰＥが含まれる復号アルゴリズムＤｅｃＭＩＢＥを用いて、鍵ｋを出力する復号手段と、
を有することを特徴とするＩＤベースハッシュ証明系構成装置。
【請求項２】
前記セットアップアルゴリズムＳｅｔｕｐＭＩＢＥは、
セキュリティパラメータ１λとＩＤ多重度１ｎとを前記セットアップアルゴリズムＳｅｔｕｐＩＰＥに入力して、ｎ＋１次元のベクトル空間を指定する公開パラメータｐｐと、前記マスター秘密鍵（ｍｓｋ，Ｋ）に含まれる部分鍵ｍｓｋとを生成する、ことを特徴とする請求項１に記載のＩＤベースハッシュ証明系構成装置。
【請求項３】
前記鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥは、
不定変数Ｘに関して前記ビット値ｒｉ（１≦ｉ≦ｎ）と前記識別子ｉｄとから決定される所定の式が成り立つようなｎ＋１次元のベクトルｙを計算し、前記ベクトルｙと、前記公開パラメータｐｐと、前記マスター秘密鍵（ｍｓｋ，Ｋ）に含まれる部分鍵ｍｓｋと、前記疑似ランダム関数ＰＲＦの関数値とを前記鍵生成アルゴリズムＫｅｙＧｅｎＩＰＥに入力して、前記ｓｋｉｄ´を生成する、ことを特徴とする請求項１又は２に記載のＩＤベースハッシュ証明系構成装置。
【請求項４】
前記暗号化アルゴリズムＥｎｃＭＩＢＥは、
前記公開パラメータｐｐと、前記識別子ｉｄから決定されるｎ次元のベクトルとを前記暗号化アルゴリズムＥｎｃＩＰＥに入力して、前記暗号文ｃｔを生成する、ことを特徴とする請求項１乃至３の何れか一項に記載のＩＤベースハッシュ証明系構成装置。
【請求項５】
前記復号アルゴリズムＤｅｃＭＩＢＥは、
前記秘密鍵ｓｋｉｄを（ｓｋｉｄ´，｛ｒｉ｝ｉ∈［ｎ］）と分解すると共に、前記暗号文ｃｔを｛ｃｔｉ，ｂ｝ｉ∈［ｎ］，ｂ∈｛０，１｝と分解した上で、不定変数Ｘに関して前記ビット値ｒｉ（１≦ｉ≦ｎ）と前記識別子ｉｄとから決定される所定の式が成り立つようなｎ＋１次元のベクトルｙを計算し、前記ｓｋｉｄ´と、前記ベクトルｙと、前記公開パラメータｐｐと、前記ｃｔｉ，ｂとを前記復号アルゴリズムＤｅｃＩＰＥに入力して、前記鍵ｋを生成する、ことを特徴とする請求項１乃至４の何れか一項に記載のＩＤベースハッシュ証明系構成装置。
【請求項６】
ＩＤベース暗号により暗号化及び復号を行うＩＤベース暗号装置であって、請求項１乃至５の何れか一項に記載のＩＤベースハッシュ証明系構成装置における各手段を有することを特徴とするＩＤベース暗号装置。
【請求項７】
セキュリティパラメータ１λを入力として、内積値暗号のセットアップアルゴリズムＳｅｔｕｐＩＰＥが含まれるセットアップアルゴリズムＳｅｔｕｐＭＩＢＥと、疑似ランダム関数ＰＲＦの鍵空間からランダムに選択された鍵Ｋとを用いて、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）とを出力するセットアップ手順と、
前記公開パラメータｐｐと、前記マスター秘密鍵（ｍｓｋ，Ｋ）と、識別子ｉｄとを入力として、｛０，１｝からｎ個のビット値ｒｉ（１≦ｉ≦ｎ）をランダムに選択した上で、選択されたビット値ｒｉ（１≦ｉ≦ｎ）と、前記内積値暗号の鍵生成アルゴリズムＫｅｙＧｅｎＩＰＥが含まれる鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥと、前記疑似ランダム関数ＰＲＦとを用いて、前記鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥの出力ｓｋｉｄ´と前記ビット値ｒｉ（１≦ｉ≦ｎ）とによって構成される秘密鍵ｓｋｉｄ＝（ｓｋｉｄ´，｛ｒｉ｝ｉ∈［ｎ］）を出力する鍵生成手順と、
前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記内積値暗号の暗号化アルゴリズムＥｎｃＩＰＥが含まれる暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、暗号文ｃｔと鍵ｋとを出力するカプセル化手順と、
前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、不正暗号文ｃｔ´を出力する不正カプセル化手順と、
前記公開パラメータｐｐと、前記秘密鍵ｓｋｉｄと、前記識別子ｉｄと、前記暗号文ｃｔとを入力として、前記内積値暗号の復号アルゴリズムＤｅｃＩＰＥが含まれる復号アルゴリズムＤｅｃＭＩＢＥを用いて、鍵ｋを出力する復号手順と、
をコンピュータが実行することを特徴とするＩＤベースハッシュ証明系構成方法。
【請求項８】
コンピュータを、請求項１乃至５の何れか一項に記載のＩＤベースハッシュ証明系構成装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＤベースハッシュ証明系構成装置、ＩＤベース暗号装置、ＩＤベースハッシュ証明系構成方法及びプログラムに関する。
【背景技術】
【０００２】
ＩＤベースハッシュ証明系（以降、ＩＢ−ＨＰＳ（Identity-based hash proof system）とも表す。）と呼ばれる概念が知られている（例えば非特許文献１参照）。非特許文献１では、ＩＢ−ＨＰＳを用いるとＩＤベース暗号を構成することでき、その構成は鍵漏洩耐性（leakage-resilience）を満たすことが示されている。鍵漏洩耐性とは、秘密鍵の一部分が漏洩したとしても、安全性が脅かされないという通常より強い安全性のことである。現実世界においては秘密鍵を完全に秘密にしたまま保存しておくことは困難であるため、鍵漏洩耐性を達成していることが望ましい。
【０００３】
非特許文献１には、鍵漏洩比率（leakage-ratio）、すなわち秘密鍵のうちで漏洩しても安全性が脅かされない比率は、部品となるＩＢ−ＨＰＳのユニバーサル比率（universality-ratio）と呼ばれるパラメータとほぼ同等であることが開示されている。
【０００４】
ここで、従来のＩＢ−ＨＰＳの構成方法のうち、ユニバーサル比率が最適、すなわちユニバーサル比率がほぼ１となるものは、安全性の証明にランダムオラクルと呼ばれるヒューリスティックなモデルを用いている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jo¨el Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and Daniel Wichs. Public-key encryption in the bounded-retrieval model. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 113-134. Springer, Heidelberg, May 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、ランダムオラクルは現実のハッシュ関数を真ランダム関数であると見做すというヒューリスティックなモデルであり、そのモデルでの安全性の証明は必ずしも現実世界での安全性を保証しない場合がある。したがって、現実世界において十分な安全性を保証するためには、ランダムオラクルを用いずに安全性の証明が可能であることが望ましい。
【０００７】
本発明の実施の形態は、上記の点に鑑みてなされたもので、ランダムオラクルを用いずにユニバーサル比率が最適なＩＤベースハッシュ証明系を構成することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の実施の形態は、セキュリティパラメータ１λを入力として、内積値暗号のセットアップアルゴリズムＳｅｔｕｐＩＰＥが含まれるセットアップアルゴリズムＳｅｔｕｐＭＩＢＥと、疑似ランダム関数ＰＲＦの鍵空間からランダムに選択された鍵Ｋとを用いて、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）とを出力するセットアップ手段と、前記公開パラメータｐｐと、前記マスター秘密鍵（ｍｓｋ，Ｋ）と、識別子ｉｄとを入力として、｛０，１｝からｎ個のビット値ｒｉ（１≦ｉ≦ｎ）をランダムに選択した上で、選択されたビット値ｒｉ（１≦ｉ≦ｎ）と、前記内積値暗号の鍵生成アルゴリズムＫｅｙＧｅｎＩＰＥが含まれる鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥと、前記疑似ランダム関数ＰＲＦとを用いて、前記鍵生成アルゴリズムＫｅｙＧｅｎＭＩＢＥの出力ｓｋｉｄ´と前記ビット値ｒｉ（１≦ｉ≦ｎ）とによって構成される秘密鍵ｓｋｉｄ＝（ｓｋｉｄ´，｛ｒｉ｝ｉ∈［ｎ］）を出力する鍵生成手段と、前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記内積値暗号の暗号化アルゴリズムＥｎｃＩＰＥが含まれる暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、暗号文ｃｔと鍵ｋとを出力するカプセル化手段と、前記公開パラメータｐｐと、前記識別子ｉｄとを入力として、前記暗号化アルゴリズムＥｎｃＭＩＢＥを用いて、不正暗号文ｃｔ´を出力する不正カプセル化手段と、前記公開パラメータｐｐと、前記秘密鍵ｓｋｉｄと、前記識別子ｉｄと、前記暗号文ｃｔとを入力として、前記内積値暗号の復号アルゴリズムＤｅｃＩＰＥが含まれる復号アルゴリズムＤｅｃＭＩＢＥを用いて、鍵ｋを出力する復号手段と、を有することを特徴とする。
【発明の効果】
【０００９】
ランダムオラクルを用いずにユニバーサル比率が最適なＩＤベースハッシュ証明系を構成することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置の機能構成の一例を示す図である。
【図２】本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置が実行する処理の流れの一例を説明するための図である。
【図３】本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、ランダムオラクルを用いずに、ユニバーサル比率が最適なＩＤベースハッシュ証明系を構成するＩＤベースハッシュ証明系構成装置１０について説明する。
【００１２】
ここで、本発明の実施の形態では、内積値暗号（以降、ＩＰＥ（Inner-product encryption）とも表す。）を用いてＩＢ−ＨＰＳを構成する場合について説明する。このとき、その中間生成物として、多重ＩＤベース暗号（以降、ＭＩＢＥ（Multi identity-based encryption）とも表す。）を構成する。そこで、まずは、ＩＢ−ＨＰＳ、ＩＰＥ及びＭＩＢＥの定義について説明する。
【００１３】
＜１．定義＞
≪１−１．ＩＢ−ＨＰＳ≫
ＩＢ−ＨＰＳはアルゴリズムの組（Ｓｅｔｕｐ，ＫｅｙＧｅｎ，Ｅｎｃａｐ，Ｅｎｃａｐ＊，Ｄｅｃａｐ）からなる。なお、ＩＢ−ＨＰＳの詳細については、例えば、上記の非特許文献１を参照されたい。
【００１４】
Ｓｅｔｕｐ（１λ）：これはセットアップアルゴリズムであり、セキュリティパラメータ１λを入力として、公開パラメータｐｐとマスター秘密鍵ｍｓｋとを出力する。なお、表記を簡単にするため、以下のアルゴリズムＫｅｙＧｅｎ、Ｅｎｃａｐ、Ｅｎｃａｐ＊及びＤｅｃａｐは、公開パラメータｐｐを暗黙に入力としているものとする。
【００１５】
ＫｅｙＧｅｎ（ｍｓｋ，ｉｄ）：これは鍵生成アルゴリズムであり、マスター秘密鍵ｍｓｋとＩＤ（以降、識別子とも表す。）ｉｄとを入力として、秘密鍵ｓｋｉｄを出力する。
【００１６】
Ｅｎｃａｐ（ｉｄ）：これはカプセル化アルゴリズムであり、識別子ｉｄを入力として、暗号文ｃｔと鍵ｋとを出力する。
【００１７】
Ｅｎｃａｐ＊（ｉｄ）：これは不正カプセル化アルゴリズムであり、識別子ｉｄを入力として、不正暗号文ｃｔ´を出力する。
【００１８】
Ｄｅｃａｐ（ｓｋｉｄ，ｉｄ，ｃｔ）：これは復号アルゴリズムであり、秘密鍵ｓｋｉｄと、識別子ｉｄと、暗号文ｃｔとを入力として、鍵ｋを出力する。
【００１９】
ここで、ＩＢ−ＨＰＳは、以下の正当性、暗号文識別不能性及びユニバーサル性の３つの性質を満たすことが要求される。
【００２０】
正当性：カプセル化アルゴリズムＥｎｃａｐにより識別子ｉｄに対して生成された暗号文ｃｔを、このｉｄに対応する秘密鍵ｓｋｉｄで復号すると正しい鍵ｋが得られる。
【００２１】
暗号文識別不能性：カプセル化アルゴリズムＥｎｃａｐにより生成された暗号文と、不正カプセル化アルゴリズムＥｎｃａｐ＊により生成された暗号文とは計量的識別不能である。
【００２２】
ユニバーサル性：１つの識別子ｉｄに対応する秘密鍵ｓｋｉｄの候補は多数存在し、不正カプセル化アルゴリズムＥｎｃａｐ＊により生成された不正暗号文ｃｔ´の復号結果は、どの秘密鍵ｓｋｉｄを使って復号したかに依存する。
【００２３】
≪１−２．ＩＰＥ≫
ＩＰＥはアルゴリズムの組（Ｓｅｔｕｐ，ＫｅｙＧｅｎ，Ｅｎｃ，Ｄｅｃ）からなる。なお、ＩＰＥの詳細については、例えば、以下の参考文献１を参照されたい。
【００２４】
［参考文献１］
Jonathan Katz, Amit Sahai, and Brent Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 146-162. Springer, Heidelberg, April 2008.
【００２５】
Ｓｅｔｕｐ（１λ，１ｎ）：これはセットアップアルゴリズムであり、セキュリティパラメータ１λと次元数１ｎとを入力として、公開パラメータｐｐとマスター秘密鍵ｍｓｋとを出力する。公開パラメータｐｐは、ベクトル空間
【００２６】
【数１】
2020034662.tif 000003
を指定する（すなわち、公開パラメータｐｐには、自然数ｑが含まれる。）。なお、表記を簡単にするため、以下のアルゴリズムＫｅｙＧｅｎ、Ｅｎｃ及びＤｅｃは、公開パラメータｐｐを暗黙に入力としているものとする。
【００２７】
ＫｅｙＧｅｎ（ｍｓｋ，ｙ）：これは鍵生成アルゴリズムであり、マスター秘密鍵ｍｓｋとベクトルｙ∈Ｖｎとを入力として、このベクトルｙに対応する秘密鍵ｓｋｙを出力する。
【００２８】
Ｅｎｃ（ｘ，ｍ）：これは暗号化アルゴリズムであり、ベクトルｘ∈Ｖｎと平文ｍとを入力として、暗号文ｃｔを出力する。
【００２９】
Ｄｅｃ（ｓｋｙ，ｙ，ｃｔ）：これは復号アルゴリズムであり、秘密鍵ｓｋｙと、ベクトルｙ∈Ｖｎと、暗号文ｃｔとを入力として、平文ｍを出力する。
【００３０】
ここで、ＩＰＥは、以下の正当性及び安全性の２つの性質を満たすことが要求される。
【００３１】
正当性：内積値＜ｘ，ｙ＞＝０である場合、ベクトルｘに対する暗号文（すなわち、Ｅｎｃ（ｘ，ｍ）により生成された暗号文ｃｔ）は、ベクトルｙに対する秘密鍵ｓｋｙを用いて正しく平文ｍに復号することができる。
【００３２】
安全性：内積値＜ｘ，ｙ＞＝０でない場合、ベクトルｘに対する暗号文とベクトルｙに対する秘密鍵ｓｋｙとは平文を秘匿する。
【００３３】
≪１−３．ＭＩＢＥ≫
ＭＩＢＥはアルゴリズムの組（Ｓｅｔｕｐ，ＫｅｙＧｅｎ，Ｅｎｃ，Ｄｅｃ）からなる。なお、ＭＩＢＥは本発明の実施の形態で導入する定式化である。
【００３４】
Ｓｅｔｕｐ（１λ，１ｎ）：これはセットアップアルゴリズムであり、セキュリティパラメータ１λとＩＤ多重度１ｎとを入力として、公開パラメータｐｐとマスター秘密鍵ｍｓｋとを出力する。なお、表記を簡単にするため、以下のアルゴリズムＫｅｙＧｅｎ、Ｅｎｃ及びＤｅｃは、公開パラメータｐｐを暗黙に入力としているものとする。
【００３５】
ここで、Ｓｅｔｕｐは乱択アルゴリズム（又は確率的アルゴリズムとも称される。）である。乱択アルゴリズムＡｌｇ（）が或る値ａを入力として、或る値ｂを出力することを
【００３６】
【数２】
2020034662.tif 000004
と表す。これを以降の明細書のテキスト中では、「Ａｌｇ（ａ）Ｒ→ｂ」又は「ｂ←ＲＡｌｇ（ａ）」と表す。一方で、確定的アルゴリズムがＡｌｇ（）が或る値ａを入力として、或る値ｂを出力することを、「Ａｌｇ（ａ）→ｂ」又は「ｂ←Ａｌｇ（ａ）」と表す。
【００３７】
したがって、上記のセットアップアルゴリズムは、Ｓｅｔｕｐ（１λ，１ｎ）Ｒ→（ｐｐ，ｍｓｋ）と表される。
【００３８】
ＫｅｙＧｅｎ（ｍｓｋ，（ｉｄ１，・・・，ｉｄｎ））：これは鍵生成アルゴリズムであり、マスター鍵ｍｓｋと識別子の組（ｉｄ１，・・・，ｉｄｎ）とを入力として、秘密鍵
【００３９】
【数３】
2020034662.tif 000005
を出力する。なお、明細書のテキスト中では、この秘密鍵の添字である識別子の組（ｉｄ１，・・・，ｉｄｎ）に含まれる各ｉｄｊ（ｊ＝１，・・・，ｎ）を「ｉｄｊ」と表す。したがって、明細書のテキスト中では、鍵生成アルゴリズムＫｅｙＧｅｎにより生成される上記の秘密鍵をｓｋ（ｉｄ１，・・・，ｉｄｎ）と表す。
【００４０】
ここで、ＫｅｙＧｅｎは乱択アルゴリズムであり、
【００４１】
【数４】
2020034662.tif 000006
と表される。
【００４２】
Ｅｎｃ（ｉｄ，ｍ）：これは暗号化アルゴリズムであり、識別子ｉｄと平文ｍとを入力として、暗号文ｃｔを出力する。ここで、Ｅｎｃは乱択アルゴリズムであり、Ｅｎｃ（ｉｄ，ｍ）Ｒ→ｃｔと表される。
【００４３】
Ｄｅｃ（ｓｋ（ｉｄ１，・・・，ｉｄｎ），（ｉｄ１，・・・，ｉｄｎ），ｃｔ）：これは復号アルゴリズムであり、秘密鍵ｓｋ（ｉｄ１，・・・，ｉｄｎ）と、識別子の組（ｉｄ１，・・・，ｉｄｎ）と、暗号文ｃｔとを入力として、平文ｍを出力する。ここで、Ｄｅｃは確定的アルゴリズムであり、Ｄｅｃ（ｓｋ（ｉｄ１，・・・，ｉｄｎ），（ｉｄ１，・・・，ｉｄｎ），ｃｔ）→ｍと表される。
【００４４】
ここで、ＭＩＢＥは、以下の正当性及び安全性の２つの性質を満たすことが要求されるものとする。
【００４５】
正当性：ｉｄ∈｛ｉｄ１，・・・，ｉｄｎ｝である場合、識別子ｉｄに対する暗号文（すなわち、Ｅｎｃ（ｉｄ，ｍ）により生成された暗号文ｃｔ）は、識別子の組（ｉｄ１，・・・，ｉｄｎ）に対する秘密鍵ｓｋ（ｉｄ１，・・・，ｉｄｎ）を用いて正しく平文に復号することができる。
【００４６】
安全性：ｉｄ∈｛ｉｄ１，・・・，ｉｄｎ｝でない場合、識別子ｉｄに対する暗号文と、識別子の組（ｉｄ１，・・・，ｉｄｎ）に対する秘密鍵ｓｋ（ｉｄ１，・・・，ｉｄｎ）とは平文を秘匿する。
【００４７】
＜２．ＩＰＥを用いたＭＩＢＥの構成＞
次に、ＭＩＢＥを用いてＩＢ−ＨＰＳを構成する前段階として、上記の１−２で定義したＩＰＥを用いて、上記の１−３で定義したＭＩＢＥを構成する方法について説明する。以降では、上記の１−２で定義したＩＰＥのアルゴリズムの組を（ＳｅｔｕｐＩＰＥ，ＫｅｙＧｅｎＩＰＥ，ＥｎｃＩＰＥ，ＤｅｃＩＰＥ）と表し、このＩＰＥを用いて構成されるＭＩＢＥのアルゴリズムの組を（ＳｅｔｕｐＭＩＢＥ，ＫｅｙＧｅｎＭＩＢＥ，ＥｎｃＭＩＢＥ，ＤｅｃＭＩＢＥ）と表す。
【００４８】
ＩＰＥのアルゴリズムの組（ＳｅｔｕｐＩＰＥ，ＫｅｙＧｅｎＩＰＥ，ＥｎｃＩＰＥ，ＤｅｃＩＰＥ）を用いて、ＭＩＢＥのアルゴリズムの組（ＳｅｔｕｐＭＩＢＥ，ＫｅｙＧｅｎＭＩＢＥ，ＥｎｃＭＩＢＥ，ＤｅｃＭＩＢＥ）を以下のように構成する。
【００４９】
ＳｅｔｕｐＭＩＢＥ（１λ，１ｎ）：（ｐｐ，ｍｓｋ）←ＲＳｅｔｕｐＩＰＥ（１λ，１ｎ＋１）を生成し、（ｐｐ，ｍｓｋ）を出力する。ＩＰＥとして公開パラメータｐｐがベクトル空間Ｖｎ＋１を指定する場合、ＭＩＢＥのＩＤ空間を
【００５０】
【数５】
2020034662.tif 000007
とする。
【００５１】
ＫｅｙＧｅｎＭＩＢＥ（ｍｓｋ，（ｉｄ１，・・・，ｉｄｎ）∈Ｖｎ）：まず、不定変数Ｘについて
【００５２】
【数６】
2020034662.tif 000008
が成り立つような｛ｙｉ∈Ｖ｝ｉ∈｛０，・・・，ｎ｝を計算し、ｙ：＝（ｙ０，・・・，ｙｎ）∈Ｖｎ＋１とする。そして、ｓｋｙ←ＲＫｅｙＧｅｎＩＰＥ（ｍｓｋ，ｙ）を生成し、ｓｋ（ｉｄ１，・・・，ｉｄｎ）：＝ｓｋｙを出力する。
【００５３】
ＥｎｃＭＩＢＥ（ｉｄ，ｍ）：ｉｄｉをｉｄのｉビット目として、ｘ：＝（１，ｉｄ，ｉｄ２，・・・，ｉｄｎ）とし、ｃｔ←ＲＥｎｃＩＰＥ（ｘ，ｍ）を生成し、暗号文ｃｔを出力する。
【００５４】
ＤｅｃＭＩＢＥ（ｓｋ（ｉｄ１，・・・，ｉｄｎ），（ｉｄ１，・・・，ｉｄｎ），ｃｔ）：ＫｅｙＧｅｎＭＩＢＥと同様にしてｙ∈Ｖｎ＋１を生成し、ｍ←ＲＤｅｃＩＰＥ（ｓｋ（ｉｄ１，・・・，ｉｄｎ），ｙ，ｃｔ）を計算し、平文ｍを出力する。
【００５５】
＜３．ＭＩＢＥを用いたＩＢ−ＨＰＳの構成＞
次に、ＭＩＢＥを用いてＩＢ−ＨＰＳを構成する方法について説明する。以降では、上記の１−１で定義したＩＢ−ＨＰＳのアルゴリズムの組を（ＳｅｔｕｐＨＰＳ，ＫｅｙＧｅｎＨＰＳ，ＥｎｃａｐＨＰＳ，ＥｎｃａｐＨＰＳ＊，ＤｅｃａｐＨＰＳ）と表し、このアルゴリズムの組を上記の２で構成したＭＩＢＥを用いて構成する。
【００５６】
ＭＩＢＥのアルゴリズムの組（ＳｅｔｕｐＭＩＢＥ，ＫｅｙＧｅｎＭＩＢＥ，ＥｎｃＭＩＢＥ，ＤｅｃＭＩＢＥ）を用いて、ＩＢ−ＨＰＳのアルゴリズムの組（ＳｅｔｕｐＨＰＳ，ＫｅｙＧｅｎＨＰＳ，ＥｎｃａｐＨＰＳ，ＥｎｃａｐＨＰＳ＊，ＤｅｃａｐＨＰＳ）を以下のように構成する。ここで、ＭＩＢＥのメッセージ空間は、ＥｎｃａｐＨＰＳ及びＤｅｃａｐＨＰＳが出力する鍵ｋの長さをＬとして、｛０，１｝Ｌを含むものとする。また、ＰＲＦを疑似ランダム関数、ｎを整数値のパラメータとする。なお、以降では、ａ｜｜ｂはビット列ａとｂとの連結を表し、整数ｃに対してｂｉｎ（ｃ）はｃのビット列を表すものとする。
【００５７】
ＳｅｔｕｐＨＰＳ（１λ）：（ｐｐ，ｍｓｋ）←ＲＳｅｔｕｐＭＩＢＥ（１λ，１ｎ）と、
【００５８】
【数７】
2020034662.tif 000009
とを生成して、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）とを出力する。ここで、任意の集合をＳとして、この集合Ｓからランダムに元ｓを選択することを
【００５９】
【数８】
2020034662.tif 000010
と表す。これを以降の明細書のテキスト中では、「ＳＲ→ｓ」又は「ｓ←ＲＳ」と表す。なお、表記を簡単にするため、以下のアルゴリズムＫｅｙＧｅｎＨＰＳ、ＥｎｃａｐＨＰＳ、ＥｎｃａｐＨＰＳ＊及びＤｅｃａｐＨＰＳは、公開パラメータｐｐを暗黙に入力としているものとする。
【００６０】
ＫｅｙＧｅｎＨＰＳ（（ｍｓｋ，Ｋ），ｉｄ）：ｉ∈［ｎ］に対してｒｉ←Ｒ｛０，１｝として、
【００６１】
【数９】
2020034662.tif 000011
を生成し、
【００６２】
【数１０】
2020034662.tif 000012
を出力する。なお、［ｎ］＝｛１，・・・，ｎ｝である。
【００６３】
ＥｎｃａｐＨＰＳ（ｉｄ）：ｉ∈［ｎ］に対してｋｉ∈｛０，１｝Ｌを生成すると共に、ｉ∈［ｎ］及びｂ∈｛０，１｝に対してｃｔｉ，ｂ←ＲＥｎｃＭＩＢＥ（ｉｄ｜｜ｂｉｎ（ｉ）｜｜ｂ，ｋｉ）を生成し、
【００６４】
【数１１】
2020034662.tif 000013
として、（ｃｔ，ｋ）を出力する。なお、
【００６５】
【数１２】
2020034662.tif 000014
はビット毎の排他的論理和を表す。
【００６６】
ＥｎｃａｐＨＰＳ＊（ｉｄ）：ｉ∈［ｎ］及びｂ∈｛０，１｝に対してｋｉ，ｂ∈｛０，１｝Ｌ及びｃｔｉ，ｂ←ＲＥｎｃＭＩＢＥ（ｉｄ｜｜ｂｉｎ（ｉ）｜｜ｂ，ｋｉ，ｂ）を生成し、ｃｔ´：＝｛ｃｔｉ，ｂ｝ｉ∈［ｎ］，ｂ∈｛０，１｝として、ｃｔ´を出力する。
【００６７】
ＤｅｃａｐＨＰＳ（ｓｋｉｄ，ｉｄ，ｃｔ）：（ｓｋｉｄ´，｛ｒｉ｝ｉ∈［ｎ］）←ｓｋｉｄと分解すると共に、｛ｃｔｉ，ｂ｝ｉ∈［ｎ］，ｂ∈｛０，１｝←ｃｔと分解して、
【００６８】
【数１３】
2020034662.tif 000015
を生成し、
【００６９】
【数１４】
2020034662.tif 000016
を出力する。
【００７０】
以上により、ユニバーサル比率が最適なＩＢ−ＨＰＳ（すなわち、ユニバーサル比率がほぼ１となるＩＢ−ＨＰＳ）が構成される。
【００７１】
ここで、ユニバーサル比率は、ユニバーサル性と秘密鍵のサイズとの比で表される。上記の３でＭＩＢＥを用いて構成したＩＢ−ＨＰＳでは、ＫｅｙＧｅｎＨＰＳにより出力される秘密鍵ｓｋｉｄは（ｓｋｉｄ，｛ｒｉ｝ｎ∈［ｎ］）であるため、１つの識別子ｉｄに対して秘密鍵ｓｋｉｄの候補は２ｎ通りとなる。このため、ユニバーサル性はｌｏｇ２２ｎ＝ｎである。また、秘密鍵ｓｋｉｄのサイズはｓｋｉｄ´のサイズと｛ｒｉ｝ｎ∈［ｎ］のサイズとの和であるため、ｓｋｉｄ´のサイズを｜ｓｋｉｄ´｜として、秘密鍵ｓｋｉｄのサイズ＝｜ｓｋｉｄ´｜＋ｎである。
【００７２】
したがって、上記の３でＭＩＢＥを用いて構成したＩＢ−ＨＰＳのユニバーサル比率はｎ／（｜ｓｋｉｄ´｜＋ｎ）で表され、パラメータｎを十分に大きくすれば、ユニバーサル比率はほぼ１となる。これにより、上記の３でＭＩＢＥを用いて構成したＩＢ−ＨＰＳにより、ランダムオラクルを用いずに、鍵漏洩比率が最適なＩＤベース暗号を構成することができるようになる。
【００７３】
＜４．ＩＤベースハッシュ証明系構成装置１０の機能構成＞
以降では、上記の３でＭＩＢＥを用いて構成したＩＢ−ＨＰＳの各アルゴリズムを実行することで、ユニバーサル比率が最適なＩＤベースハッシュ証明系（ＩＢ−ＨＰＳ）を構成するＩＤベースハッシュ証明系構成装置１０の機能構成について、図１を参照しながら説明する。図１は、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０の機能構成の一例を示す図である。
【００７４】
図１に示すように、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０は、セットアップ部１０１と、鍵生成部１０２と、カプセル化部１０３と、不正カプセル化部１０４と、復号部１０５とを有する。
【００７５】
セットアップ部１０１は、セキュリティパラメータ１λを入力としてＳｅｔｕｐＨＰＳを実行し、公開パラメータｐｐとマスター秘密鍵（ｍｓｋ，Ｋ）とを出力する。
【００７６】
鍵生成部１０２は、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）と、識別子ｉｄとを入力としてＫｅｙＧｅｎＨＰＳを実行し、秘密鍵ｓｋｉｄを出力する。
【００７７】
カプセル化部１０３は、公開パラメータｐｐと識別子ｉｄとを入力としてＥｎｃａｐＨＰＳを実行し、（ｃｔ，ｋ）を出力する。なお、ｃｔは暗号文、ｋは鍵である。
【００７８】
不正カプセル化部１０４は、公開パラメータｐｐと識別子ｉｄとを入力としてＥｎｃａｐＨＰＳ＊を実行し、不正暗号文ｃｔ´を出力する。
【００７９】
復号部１０５は、公開パラメータｐｐと、秘密鍵ｓｋｉｄと、識別子ｉｄと、暗号文ｃｔとを入力としてＤｅｃａｐＨＰＳを実行し、鍵ｋを出力する。
【００８０】
＜５．ＩＤベースハッシュ証明系構成装置１０が実行する処理の流れ＞
以降では、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０が実行する処理の流れについて、図２を参照しながら説明する。図２は、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０が実行する処理の流れの一例を説明するための図である。なお、後述するステップＳ１０１の処理（セットアップ処理）は、例えば、ＩＢ−ＨＰＳを構成する際の初期処理として１回のみ実行される。また、後述するステップＳ１０２の処理（鍵生成処理）は、例えば、秘密鍵ｓｋｉｄの生成を行う度に実行される。また、後述するステップＳ１０２の処理（カプセル化処理）は、例えば、カプセル化（又は不正カプセル化）を行う度に実行される。同様に、後述するステップＳ１０３の処理（復号処理）は、例えば、復号を行う度に実行される。
【００８１】
ステップＳ１０１（セットアップ処理）：セットアップ部１０１は、セキュリティパラメータ１λを入力としてＳｅｔｕｐＨＰＳを実行し、公開パラメータｐｐとマスター秘密鍵（ｍｓｋ，Ｋ）とを出力する。
【００８２】
ステップＳ１０２（鍵生成処理）：鍵生成部１０２は、公開パラメータｐｐと、マスター秘密鍵（ｍｓｋ，Ｋ）と、識別子ｉｄとを入力としてＫｅｙＧｅｎＨＰＳを実行し、秘密鍵ｓｋｉｄを出力する。
【００８３】
ステップＳ１０３（カプセル化処理）：カプセル化部１０３は、公開パラメータｐｐと識別子ｉｄとを入力としてＥｎｃａｐＨＰＳを実行し、（ｃｔ，ｋ）を出力する。又は、不正カプセル化部１０４は、公開パラメータｐｐと識別子ｉｄとを入力としてＥｎｃａｐＨＰＳ＊を実行し、不正暗号文ｃｔ´を出力する。
【００８４】
ステップＳ１０４（復号処理）：復号部１０５は、公開パラメータｐｐと、秘密鍵ｓｋｉｄと、識別子ｉｄと、暗号文ｃｔとを入力としてＤｅｃａｐＨＰＳを実行し、鍵ｋを出力する。
【００８５】
＜６．ＩＤベースハッシュ証明系構成装置１０のハードウェア構成＞
次に、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０のハードウェア構成について、図３を参照しながら説明する。図３は、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０のハードウェア構成の一例を示す図である。
【００８６】
図３に示すように、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、通信Ｉ／Ｆ２０４と、ＲＡＭ（Random access memory）２０５と、ＲＯＭ（Read only memory）２０６と、ＣＰＵ（Central processing unit）２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバス２０９を介して通信可能に接続されている。
【００８７】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、ＩＤベースハッシュ証明系構成装置１０の処理結果を表示する。なお、ＩＤベースハッシュ証明系構成装置１０は、入力装置２０１及び表示装置２０２のうちの少なくとも一方を有していなくても良い。
【００８８】
外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。ＩＤベースハッシュ証明系構成装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａ等の読み取りや書き込みを行うことができる。記録媒体２０３ａには、ＩＤベースハッシュ証明系構成装置１０が有する各機能部（例えば、セットアップ部１０１、鍵生成部１０２、カプセル化部１０３、不正カプセル化部１０４及び復号部１０５）を実現する１以上のプログラム等が記憶されていても良い。
【００８９】
記録媒体２０３ａとしては、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。
【００９０】
通信Ｉ／Ｆ２０４は、ＩＤベースハッシュ証明系構成装置１０を通信ネットワークに接続するためのインタフェースである。ＩＤベースハッシュ証明系構成装置１０が有する各機能部を実現する１以上のプログラムは、通信Ｉ／Ｆ２０４を介して、所定のサーバ等から取得（ダウンロード）されても良い。
【００９１】
ＲＡＭ２０５は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０６は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０６には、例えば、ＯＳ（Operating System）に関する設定情報や通信ネットワークに関する設定情報等が格納されている。
【００９２】
ＣＰＵ２０７は、ＲＯＭ２０６や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０５上に読み出して処理を実行する演算装置である。ＩＤベースハッシュ証明系構成装置１０が有する各機能部は、例えば補助記憶装置２０８に格納されている１以上のプログラムがＣＰＵ２０７に実行させる処理により実現される。
【００９３】
補助記憶装置２０８は、例えばＨＤＤ（Hard disk drive）やＳＳＤ（Solid state drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、ＯＳ、アプリケーションプログラム、ＩＤベースハッシュ証明系構成装置１０が有する各機能部を実現する１以上のプログラム等が挙げられる。
【００９４】
本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０は、図３に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図３では、ＩＤベースハッシュ証明系構成装置１０が１台のコンピュータで実現されている場合のハードウェア構成例を示したが、これに限られず、ＩＤベースハッシュ証明系構成装置１０は複数台のコンピュータで実現されていても良い。
【００９５】
＜７．まとめ＞
以上のように、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０は、ＩＰＥを用いて構成されたＭＩＢＥにより、ＩＢ−ＨＰＳを構成する。これにより、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０は、ランダムオラクルを用いずに、ユニバーサル比率が最適なＩＢ−ＨＰＳを構成することができる。
【００９６】
このため、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０によれば、ランダムオラクルを用いずに、鍵漏洩比率が最適なＩＤベース暗号を構成することができるようになる。すなわち、本発明の実施の形態におけるＩＤベースハッシュ証明系構成装置１０により構成されたＩＢ−ＨＰＳによりＩＤベース暗号を構成した上で、このＩＤベース暗号を実現する装置（ＩＤベース暗号装置）を構成することができる。なお、このとき、ＩＤベースハッシュ証明系構成装置１０とＩＤベース暗号装置とが異なる装置であっても良いし、同一の装置であっても良い。
【００９７】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００９８】
１０        ＩＤベースハッシュ証明系構成装置
１０１      セットアップ部
１０２      鍵生成部
１０３      カプセル化部
１０４      不正カプセル化部
１０５      復号部
【図１】
2020034662.tif 000017
【図２】
2020034662.tif 000018
【図３】
2020034662.tif 000019