"時刻サーバ装置と、送信者装置と、受信者装置とを含み、予め定められた時間において暗号文の復号が可能となる時限暗号システムであって、公開パラメータpkとマスター秘密鍵skが定められた暗号が、KeyGen→ski:鍵生成アルゴリズムマスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズムと、Enc→cj:暗号化アルゴリズム公開パラメータpkと情報jと暗号化対象の情報以下、平文というxを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズムと、Dec→y:復号アルゴリズム公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズムとを含み、上記情報iと上記情報jが予め定められた関係Rを満たすときに上記情報yとして上記平文xが得られるように構成されており、上記時刻サーバ装置は、定期あるいは不定期に、上記情報iを時刻tを含む情報として、上記暗号の鍵生成アルゴリズムKeyGenを実行して時刻トークンskt←KeyGenを生成する時刻トークン生成部を含み、上記送信者成装置は、上記情報jを上記復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t以下、時的制限情報tというを含む情報とし、上記平文xを平文mとして、上記暗号の暗号化アルゴリズムEncを実行して暗号文ct←Encを生成する暗号文生成部を含み、上記受信者装置は、上記秘密鍵skiを上記時刻トークンsktとし、上記暗号文cjを上記暗号文ctとして、上記暗号の復号アルゴリズムDecを実行する復号部を含む時限暗号システム。請求項1に記載の時限暗号システムにおいて、上記時的制限情報tを時刻とし、上記関係Rは、上記時刻tに対してTを述語変数とするt≧Tなる述語と当該述語変数Tに代入されうる上記時的制限情報tとの関係であり、上記時刻トークン生成部は、上記情報iを上記述語t≧Tとして、上記鍵生成アルゴリズムKeyGenを実行して時刻トークンskt←KeyGenを生成することを特徴とする時限暗号システム。請求項1に記載の時限暗号システムにおいて、上記時的制限情報tを時刻とし、上記関係Rは、上記時的制限情報tに対してTを述語変数とするT≧tなる述語と当該述語変数Tに代入されうる上記時刻tとの関係であり、上記暗号文生成部は、上記情報jを上記述語T≧tとして、上記暗号化アルゴリズムEncを実行して暗号文ct←Encを生成することを特徴とする時限暗号システム。請求項1に記載の時限暗号システムにおいて、上記時的制限情報tを時刻とし、上記関係Rは、Tを上記時的制限情報tが代入されうる述語変数として、上記時刻tが経過するn個の時間区間bieii12...nと述語変数Tとによる論理和∨∨∨で表される述語と上記時的制限情報tとの関係であり、上記時刻トークン生成部は、上記情報iを上記述語∨∨∨として、上記鍵生成アルゴリズムKeyGenを実行して時刻トークンskt←KeyGenを生成することを特徴とする時限暗号システム。請求項1に記載の時限暗号システムにおいて、上記時的制限情報tを時間とし、上記関係Rは、Tを上記時刻tが代入されうる述語変数として、上記時的制限情報tとしてのn個の時間区間bieii12...nと述語変数Tとによる論理和∨∨∨で表される述語と上記時刻tとの関係であり、上記暗号文生成部は、上記情報jを上記述語∨∨∨として、上記暗号化アルゴリズムEncを実行して暗号文ct←Encを生成することを特徴とする時限暗号システム。請求項1から請求項5のいずれかに記載の時限暗号システムにおいて、上記暗号文生成部は、上記暗号文ctが正しく生成されたことを証明可能な非対話零知識証明を上記暗号文ctに添付し、上記受信者装置は、上記非対話零知識証明によって上記暗号文ctが正しく生成されたものであるか否かを検証する検証部を含むことを特徴とする時限暗号システム。時刻サーバ装置と、送信者装置と、受信者装置とを含み、予め定められた時間において暗号文の復号が可能となる時限暗号システムにおける時限暗号方法であって、公開パラメータpkとマスター秘密鍵skが定められた暗号が、KeyGen→ski:鍵生成アルゴリズムマスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズムと、Enc→cj:暗号化アルゴリズム公開パラメータpkと情報jと暗号化対象の情報以下、平文というxを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズムと、Dec→y:復号アルゴリズム公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズムとを含み、上記情報iと上記情報jが予め定められた関係Rを満たすときに上記情報yとして上記平文xが得られるように構成されており、上記時刻サーバ装置の時刻トークン生成部が、定期あるいは不定期に、上記情報iを時刻tを含む情報として、上記暗号の鍵生成アルゴリズムKeyGenを実行して時刻トークンskt←KeyGenを生成する時刻トークン生成ステップと、上記送信者成装置の暗号文生成部が、上記情報jを上記復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報tを含む情報とし、上記平文xを平文mとして、上記暗号の暗号化アルゴリズムEncを実行して暗号文ct←Encを生成する暗号文生成ステップと、上記受信者装置の復号部が、上記秘密鍵skiを上記時刻トークンsktとし、上記暗号文cjを上記暗号文ctとして、上記暗号の復号アルゴリズムDecを実行する復号ステップとを有する時限暗号方法。請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記時刻サーバ装置。請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記送信者装置。請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記受信者装置。請求項8に記載の時刻サーバ装置、請求項9に記載の送信者装置、請求項10に記載の受信者装置のいずれかとしてコンピュータを機能させるプログラム。従来の上記構成では、時刻サーバ装置がブロードキャストした時刻トークンsktを受信者装置が取りこぼした場合、受信者装置が上記復号アルゴリズムDecを実行できないという問題がある。そこで本発明は、指定された復号基準時刻以降に生成された時刻トークンを用いて暗号文を復号できる時限暗号技術を提供することを目的とする。本発明の時限暗号技術は、次のとおりである。公開パラメータpkとマスター秘密鍵skが定められた暗号が、KeyGen→ski:鍵生成アルゴリズムマスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズムと、Enc→cj:暗号化アルゴリズム公開パラメータpkと情報jと暗号化対象の情報以下、平文というxを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズムと、Dec→y:復号アルゴリズム公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズムとを含み、情報iと情報jが予め定められた関係Rを満たすときに情報yとして平文xが得られるように構成されている。時限暗号システムを構成する時刻サーバ装置では、定期あるいは不定期に、情報iを時刻tを含む情報として、暗号の鍵生成アルゴリズムKeyGenを実行して時刻トークンskt←KeyGenを生成する時刻トークン生成処理。時限暗号システムを構成する送信者成装置では、情報jを復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t時的制限情報tを含む情報とし、平文xを平文mとして、暗号の暗号化アルゴリズムEncを実行して暗号文ct←Encを生成する暗号文生成処理。時限暗号システムを構成する受信者装置では、秘密鍵skiを時刻トークンsktとし、暗号文cjを暗号文ctとして、暗号の復号アルゴリズムDecを実行する復号処理。本発明に拠れば、暗号を利用して時限暗号を構成するので、指定された復号基準時刻以降に生成された時刻トークンを用いて暗号文を復号できる。従って、例えば復号基準時刻として指定された時刻にブロードキャストされた時刻トークンを受信者装置が取得できなかったとしても、受信者装置は、当該復号基準時刻以降に生成された時刻トークンを用いて当該暗号文を復号することができる。《原理》本発明の時限暗号は関数暗号を利用して実現される。そこでまず関数暗号について説明する。<関数暗号>近年、関数暗号と呼ばれるIDベース暗号の拡張暗号が話題となっている。関数暗号とIDベース暗号には構文の違いは全く無い。即ち、関数暗号も下記の4つのアルゴリズムから構成される。プロトコルの概略は下記のとおりである。《プロトコルFE》========================================Setup→:セットアップアルゴリズムセキュリティパラメータ1λを入力とし、公開パラメータpkとマスター秘密鍵skを出力する確率的多項式時間アルゴリズムKeyGen→ski:鍵生成アルゴリズムマスター秘密鍵skと鍵識別子iを入力とし、当該鍵識別子iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズムEnc→cj:暗号化アルゴリズム公開パラメータpkと受信者識別子jと暗号化対象の情報平文xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズムDec→y:復号アルゴリズム公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、平文yを出力する確率的多項式時間アルゴリズム========================================関数暗号では、IDベース暗号の正当性が拡張されており、暗号文の受信者は鍵識別子iを持つ秘密鍵と受信者識別子jを持つ暗号文から平文xに関する何らかの関数fijを評価することができるようになっている。即ち、或る関数fijが存在し∀i,∀j,∀x∈01polyに対して式2で表される確率Prがλに関して圧倒的であるとき、その関数暗号は正当であると云う。特に、或る関係Rが存在し、式3で表されるタイプの関数fijを持つ関数暗号は様々な暗号を包含している⊥は正常に復号できなかったことを表す記号である。例えばIDベース暗号は式4で表される関数fijを持つ関数暗号と定義することができる。より高度な関係Rを持つ様々な関数暗号が研究されている。このタイプの関数暗号のうち最も汎用性の高いものは属性ベース暗号あるいは述語暗号等と呼ばれ、よく研究されている。2010年に岡本龍明らは多項式サイズの述語および述語変数の集合に対応し、標準的な暗号学的仮定の下で適応的識別子攻撃に対してCCA安全が証明できる比較的実用的なこのタイプの関数暗号を提案した参考文献1参照。参考文献1TatsuakiOkamotoandKatsuyukiTakashimaFullySecureFunctionalEncryptionwithGeneralRelationsfromtheDecisionalLinearAssumptionInternationalCryptologyConferenceCRYPTOpp191208November2010鍵識別子iを述語、受信者識別子jを述語変数のインスタンスとして式5で表される関係Rを持つ関数暗号は鍵ポリシー属性ベース暗号と呼ばれる。鍵識別子iを述語変数、受信者識別子jを述語のインスタンスとして式6で表される関係Rを持つ関数暗号は暗号文ポリシー属性ベース暗号と呼ばれる。<関数暗号を用いた時限暗号>IDベース暗号と関数暗号の構文アルゴリズムの入出力インターフェイスは完全に一致している。従って、同じような安全性を持つならば時限暗号に関してIDベース暗号の代わりに関数暗号を利用できる。mを平文、tを時刻サーバ装置が時刻トークンを生成した時刻、tを送信者装置が暗号文に設定した時的制限情報復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報である。以下、時的制限情報を特に断りのない限り復号基準時刻と呼ぶことにするとして、式7で表される関数fttを持つ関数暗号を利用できるならば受信者装置が時刻トークンを取得できなかった場合の上記問題を克服できる。式7で表される関数fttによると、時刻tが時刻tより小さい時早い時は復号時に⊥が出力され、時刻tが時刻t以上の時時刻tが時刻t以降の時は平文mが出力される。t≧tあるいはその否定であるt<tは関係Rによって表現できるところ、このような関数暗号を属性ベース暗号に基づいて構成する方法は2通り存在する。一つは鍵ポリシー属性ベース暗号を用いる方法である。この場合、時刻サーバ装置はtを現在時刻、tを述語変数としてt≧tなる述語鍵識別子に関して時刻トークンsktを生成して、時刻トークンsktをブロードキャストする。送信者装置は目的の復号基準時刻tを属性に持つ暗号文ctを生成し、当該暗号文ctを受信者装置に送信する。もう一つは暗号文ポリシー属性ベース暗号を用いる方法である。この場合、時刻サーバ装置は、現在時刻tを属性に持つ時刻トークンsktを生成して、時刻トークンsktをブロードキャストする。送信者装置はtを述語変数、tを目的の復号基準時刻としてt≧tなる述語に関して暗号文ctを生成し、当該暗号文ctを受信者装置に送信する。いずれの場合であっても時刻トークンsktおよび暗号文ctを持つ受信者装置はt≧tなる時に暗号文ctを復号できる。述語変数現在時刻が代入されると復号基準時刻をビット表現された整数と見做せば、現在時刻と復号基準時刻との大小判定を、述語変数を用いた述語として表現できる。従って、述語の充足によって復号可能か否かが決まる関数暗号があれば、ビット表現された整数の大小判定の結果によって復号可能か否かが決定される関数暗号を構成することができる。例えば、図4と図5に示すように比較する定数のビットイメージに対応して論理積andや論理和orで述語変数を合成することによって述語を決定できる。図4では整数変数tと定数tとの間におけるt>tの関係を記述する述語を示してある。なお、t≦tの関係を記述する述語は、t>tの関係を記述する述語の否定¬によって表される。図5では整数変数tと定数tとの間におけるt≧tの関係を記述する述語を示してある。なお、t<tの関係を記述する述語は、t≧tの関係を記述する述語の否定¬によって表される。<公開検証可能関数暗号>関数暗号のうち暗号文に対してKeyGenアルゴリズムから得られる如何なる鍵を持たなくとも、その暗号文が正しく作られていることが納得できるものを公開検証可能関数暗号と呼ぶ。暗号化手続きが正しく行われたことを証明する非対話零知識証明を暗号文に付加すれば、そのような暗号を構成することができる参考文献2参照。非対話零知識証明を用いることによって、暗号文に対して復号可能な如何なる鍵を使っても同じ結果が得られることを納得できる。参考文献2JensGrothandAmitSahaiEfficientNoninteractiveProofSystemsforBilinearGroupsAdvancesinCryptologyEUROCRYPT2008LNCS4965pp415432March2010《実施形態》[時限暗号システム]実施形態の時限暗号システム1は、図1に示すように、時刻サーバ装置100と、送信者装置200と、受信者装置300とを少なくとも含んで構成される。これらの各装置は、例えばインターネットなどの通信網5を経由して、相互に通信可能とされている。本発明の時限暗号システムは、ユーザの数に応じて一つまたは複数の送信者装置200と一つまたは複数の受信者装置300を含みえるが、本発明の理解を容易にするため、後述の実施形態では、時限暗号システム1は、1個の時刻サーバ装置100と1個の送信者装置200とN個の受信者装置300-1,,300-i,,300-Nを含むとする。ただし、Nは1以上の整数とする。時限暗号システム1における時限暗号処理を、図2を参照しながら叙述する。各装置の機能構成については、図3を参照されたい。なお、N個の受信者装置300-1,,300-i,,300-Nのうちのどの受信者装置についても同じ情報処理となるから、この説明では、任意性を考慮してi番目の受信者装置300-iにおける情報処理を想定する。実施例1tを鍵識別子、tを受信者識別子として、上記式7で表される関数fttを持つ関数暗号を利用する。プロトコルの概略は下記のとおりである。なお、このような関数暗号であれば何ら限定はないので、ここでは一般的な説明をするに留めるが、実用の局面ではSetupKeyGenEncDecの各アルゴリズムが具体的に決まっているから、当然、当該各アルゴリズムを実行することになる。《プロトコルTRCFE》========================================まず、時刻サーバ装置は、《プロトコルFE》で説明したセットアップアルゴリズムSetupを実行して公開パラメータpkとマスター秘密鍵skを生成し、公開パラメータpkを公開する。時刻サーバ装置は、定期あるいは不定期に、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGenを実行して時刻トークンsktを生成し、時刻トークンsktをブロードキャストする。ただし、tはKeyGenを実行するときの時刻である。送信者装置は、復号基準時刻をt、平文をmとして、《プロトコルFE》で説明した暗号化アルゴリズムEncを実行して暗号文ctを生成し、暗号文ctを受信者装置に送信する。受信者装置は、時刻サーバ装置から時刻tの時刻トークンsktを取得して、《プロトコルFE》で説明した復号アルゴリズムDecを実行して、t≧tを満たす場合に平文mを得る。========================================まず、時刻サーバ装置100の初期設定部101が、《プロトコルFE》で説明したセットアップアルゴリズムSetupを実行して公開パラメータpkとマスター秘密鍵skを生成しステップS1、公開パラメータpkを公開するステップS1a。公開パラメータpkの公開は、例えば、送信者装置200や受信者装置300-iから時刻サーバ装置100にアクセスがあった場合に時刻サーバ装置100の送信部108が時刻サーバ装置100の記憶部図示せずに記憶されている公開パラメータpkを送信者装置200や受信者装置300-iに対して送信する手順や、送信者装置200や受信者装置300-iからのアクセスを問わず、時刻サーバ装置100の送信部108が時刻サーバ装置100の記憶部図示せずに記憶されている公開パラメータpkを送信者装置200や受信者装置300-iに対して送信する手順によって達成される。そして、時刻サーバ装置100の時刻トークン生成部102は、定期あるいは不定期に、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGenを実行して時刻トークンsktを生成するステップS2。ただし、tはKeyGenを実行するときの時刻である。この時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時UTCUniversalTimeCoordinatedや日本標準時JSTJapanStandardTimeなどであってもよい。なお、時刻サーバ装置100の内部時計から取得した時刻を時刻tとする場合、少なくとも時刻サーバ装置100と送信者装置200との間で可能な限りつまり、例えば数秒程度の誤差を許容するとしても相互の時間を同期させておくことが望ましい。同期方法としては、例えば、時刻サーバ装置100が通信網5を経由して送信者装置200に、時刻サーバ装置100の内部時計の時刻を常時提供するようにすればよい。時刻tとして協定世界時や日本標準時を利用する場合、送信者装置200も協定世界時や日本標準時を受信できる構成としておくことが望ましい。なお、このことは、他の実施例でも同様である。時刻サーバ装置100の送信部108は、時刻トークン生成部102によって生成された時刻トークンsktをブロードキャストするステップS3。ブロードキャストの対象に制限はないが、少なくとも受信者装置300-iはブロードキャストされた時刻トークンsktを受信できるシステム構成であることが必須であるただし、既述のように、受信者装置300-iがブロードキャストされた時刻トークンsktを取りこぼしてしまう可能性は否定されない。送信者装置200の暗号文生成部201は、復号基準時刻をt、平文をmとして、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEncを実行して暗号文ctを生成するステップS4。当然であるが、復号基準時刻tは、暗号文ctを生成した時刻よりも遅い時刻である。送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文ctを受信者装置300-iに対して送信するステップS5。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。受信者装置300-iの復号部301は、受信者装置300-iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文ctを用いて、《プロトコルFE》で説明した復号アルゴリズムDecを実行するステップS6。上記式7で表されるタイプの関数fttを持つ関数暗号によると、多くの場合、復号アルゴリズムDecにて、関係Rここではt≧tであるの真偽を判定するための論理式やこれと等価な演算を通して当該関数fttの出力が決せられる暗号構造が組み込まれており、当該関係Rが真となる場合、つまりt≧tを満たす場合に復号部301は平文mを得ることができる。実施例2実施例2は、実施例1における関数暗号として鍵ポリシー属性ベース暗号による場合の実施例である。実施例1を鍵ポリシー属性ベース暗号として具体化した事項について説明を加え、実施例1と同じ事項は説明を省略する。実施例2では、実施例1のステップS2の処理にて、次のような処理を行う。時刻サーバ装置100の時刻トークン生成部102が、定期あるいは不定期に、tを現在時刻KeyGenを実行するときの時刻、Tを述語変数として、t≧Tなる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGenを実行して時刻トークンskt≧Tを生成する。現在時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時UTCUniversalTimeCoordinatedや日本標準時JSTJapanStandardTimeなどであってもよい。実施例2では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300-iの復号部301は、受信者装置300-iの受信部309が受信した時刻トークンskt≧T、公開パラメータpk、暗号文ctを用いて、《プロトコルFE》で説明した復号アルゴリズムDecを実行する。上記式7で表されるタイプの関数fttを持つ関数暗号によると、多くの場合、復号アルゴリズムDecにて、式5で表される関係RここではRであるの真偽を判定するための論理式やこれと等価な演算を通して当該関数fttの出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧tを満たす場合に復号部301は平文mを得ることができる。IDベース暗号を用いた時限暗号では、時刻トークン生成に用いられた時刻tが復号基準時刻tに一致していないと復号ができない構成であった。これに対して、実施例2によると、一つの復号基準時刻tが組み込まれた暗号文が、指数的多数に及びうる復号基準時刻t以降の時刻tで生成された時刻トークンのいずれによっても復号可能となっている。ここで指数的多数に及びうる時刻tとは、時刻tが例えばnビットで表されるとすると2n通りの時刻tが考えられるというように、多項式長で表される時刻tとして指数関数的な数の種類の時刻が考えられることを意味している。IDベース暗号を用いた時限暗号は、指数関数的な数となる可能性のある処理対象に対して効率的な暗号処理が困難であるが、関数暗号を用いた時限暗号は、このような処理対象に対して効率的な暗号処理が可能である。実施例3実施例3は、実施例1における関数暗号として暗号文ポリシー属性ベース暗号による場合の実施例である。実施例1を暗号文ポリシー属性ベース暗号として具体化した事項について説明を加え、実施例1と同じ事項は説明を省略する。実施例3では、実施例1のステップS4の処理にて、次のような処理を行う。送信者装置200の暗号文生成部201は、述語変数をT、復号基準時刻をt、平文をmとして、T≧tなる述語に関して、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEncを実行して暗号文cT≧tを生成する。実施例3では、実施例1のステップS5の処理にて、次のような処理を行う。送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文cT≧tを受信者装置300-iに対して送信する。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。実施例3では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300-iの復号部301は、受信者装置300-iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文cT≧tを用いて、《プロトコルFE》で説明した復号アルゴリズムDecを実行する。上記式7で表されるタイプの関数fttを持つ関数暗号によると、多くの場合、復号アルゴリズムDecにて、式6で表される関係RここではRであるの真偽を判定するための論理式やこれと等価な演算を通して当該関数fttの出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧tを満たす場合に復号部301は平文mを得ることができる。IDベース暗号を用いた時限暗号では、時刻トークン生成に用いられた時刻tが復号基準時刻tに一致していないと復号ができない構成であった。これに対して、実施例3によると、指数的多数に及びうる復号基準時刻t以降の時刻が組み込まれた暗号文が、復号基準時刻t以降の時刻を満たす時刻tで生成された時刻トークンによって復号可能となっている。ここで指数的多数に及びうる時刻とは、時刻が例えばnビットで表されるとすると2n通りの時刻が考えられるというように、多項式長で表される時刻として指数関数的な数の種類の時刻が考えられることを意味している。ここで実施例3の有用性を理解するために、次のような事例を考える。送信者装置200が、受信者装置300-1に対しては、復号基準時刻をt1とする述語に関する暗号化アルゴリズムEncを実行して暗号文cT≧t1を生成してこれを送信し、受信者装置300-2に対しては、復号基準時刻をt2とする述語に関する暗号化アルゴリズムEncを実行して暗号文cT≧t2を生成してこれを送信し、受信者装置300-iに対しては、復号基準時刻をtiとする述語に関する暗号化アルゴリズムEncを実行して暗号文cT≧tiを生成してこれを送信する、という事例を考えるただし、t1,t2,tiは互いに異なるとする。平文mは受信者装置ごとに異なってもよいが、ここでは全ての受信者装置について同じとした。このような事例では、IDベース暗号を用いた時限暗号によると、時刻サーバ装置100は、各受信者装置で復号可能となるために、各時刻t1,t2,tiに応じた3種類の時刻トークンを作成することが必須となる。つまり、時刻サーバ装置100は、異なる3種類の時刻トークンを作成しこれらをブロードキャストするという、異なる3種類の時刻トークンに応じた資源の消費が避けられない。他方、関数暗号を用いた時限暗号によると、各時刻t1,t2,tiのうち最も遅い時刻以降の時刻tにおいて時刻トークンを作成し、この一つの時刻トークンを各受信者装置にブロードキャストすることによって、どの受信者装置でも暗号文を復号することができるのである。よって、実施例3によると、さらに強く、指数的多数に及びうる復号基準時刻t以降の時刻が組み込まれた暗号文の集合について、当該集合に含まれる暗号文ごとに復号基準時刻tが異なるような場合においても、これら異なる復号基準時刻tのうち最も遅い時刻以降の時刻を満たす時刻tで生成された一つの時刻トークンによって復号可能となっている、と云うことができる。実施例4実施例4は、実施例2の変形例である。実施例2では、時刻サーバ装置100の時刻トークン生成部102が、tを現在時刻、Tを述語変数として、t≧Tなる述語に関して鍵生成アルゴリズムKeyGenを実行して時刻トークンskt≧Tを生成していた。実施例4は、述語が拡張された例である。実施例4では、t≧Tなる述語ではなく、時刻tが経過する任意の有限個の時間区間bieii12...nと復号基準時刻tが代入されうる述語変数Tで構成される論理和∨i∈12...n∨∨∨を述語とする。なお、n個の時間区間bieii12...nのうち少なくともいずれかにおいてbieiであってもよい。従って、実施例4では、実施例1のステップS2の処理にて、次のような処理を行う。時刻サーバ装置100の時刻トークン生成部102が、定期あるいは不定期に、tを現在時刻KeyGenを実行するときの時刻、Tを復号基準時刻tが代入されうる述語変数として、∨i∈12...nなる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGenを実行して時刻トークンsktTを生成する。現在時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時UTCUniversalTimeCoordinatedや日本標準時JSTJapanStandardTimeなどであってもよい。そして、実施例4では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300-iの復号部301は、受信者装置300-iの受信部309が受信した時刻トークンsktT、公開パラメータpk、暗号文ctを用いて、《プロトコルFE》で説明した復号アルゴリズムDecを実行する。上記式7で表されるタイプの関数fttを持つ関数暗号によると、多くの場合、復号アルゴリズムDecにて、式5で表される関係RここではR,Ttであるの真偽を判定するための論理式やこれと等価な演算を通して当該関数fttの出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧tを満たす場合に復号部301は平文mを得ることができる。実施例5実施例5は、実施例3の変形例である。実施例3では、送信者装置200の暗号文生成部201が、述語変数をT、復号基準時刻をt、平文をmとして、T≧tなる述語に関して暗号化アルゴリズムEncを実行して暗号文cT≧tを生成していた。実施例5は、述語が拡張された例である。実施例5では、T≧tなる述語ではなく、時的制限情報tとしての任意の有限個の時間区間bieii12...nと時刻tが代入されうる述語変数Tで構成される論理和∨i∈12...n∨∨∨を述語とする。なお、n個の時間区間bieii12...nのうち少なくともいずれかにおいてbieiであってもよい。従って、実施例5では、実施例1のステップS4の処理にて、次のような処理を行う。送信者装置200の暗号文生成部201は、時刻tが代入されうる述語変数をT、時的制限情報tを有限個の時間区間bieii12...n、平文をmとして、∨i∈12...nなる述語に関して、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEncmを実行して暗号文cTtを生成する。実施例5では、実施例1のステップS5の処理にて、次のような処理を行う。送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文cTtを受信者装置300-iに対して送信する。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。実施例5では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300-iの復号部301は、受信者装置300-iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文cTtを用いて、《プロトコルFE》で説明した復号アルゴリズムDecを実行する。上記式7で表されるタイプの関数fttを持つ関数暗号によると、多くの場合、復号アルゴリズムDecにて、式6で表される関係RここではR,Ttであるの真偽を判定するための論理式やこれと等価な演算を通して当該関数fttの出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧tを満たす場合に復号部301は平文mを得ることができる。実施例4と実施例5は、例えば次のような事例において有用である。例えば、送信者装置200を扱うユーザの意図として、受信者装置300-iに時間またはただし、b1≦e1<b2≦e2とするのみで復号可能とさせたいという意図がある場合に、受信者装置300-iが時刻トークンを記憶可能な記憶部を持っているとすると、受信者装置300-iは、時間に時刻トークンを正しく受信し、ユーザが意図しない時間に当該時刻トークンを用いて正しく復号するということができてしまう。そこで受信者装置300-iに耐タンパー機能を持つ記憶部、つまり時刻トークンを記憶不能な記憶部を持たせることによって、送信者装置200を扱うユーザが意図した時間帯∨i∈12...nのみで復号可能とすることができる。実施例6実施例6は、実施例1から実施例5までのそれぞれの変形例に対応する。実施例6では、送信者装置200の暗号文生成部201が暗号文を正しく生成したことを証明する非対話零知識証明用の情報σが暗号文に添付される。これによって、受信者装置300-iの検証部図示しないは、非対話零知識証明用の情報σを利用して、送信者装置200から受信した暗号文が正しく生成されたものであるか否かを検証することができる。なお、非対話零知識証明用の情報σは関数暗号に応じてその実体アルゴリズムが決定され、例えばペアリングを用いて関数暗号が実装される場合、上記参考文献2に従って非対話零知識証明アルゴリズムを定めることができる。以下、関数暗号について概説する。説明に先立ち記号等を定義する。定義行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列と表現する。T:Tはの転置行列を表す。1:1はの逆行列を表す。∧:∧は論理積ANDを表す論理記号である。∨:∨は論理和ORを表す論理記号である。¬:¬は否定NOTを表す論理記号である。命題変数:命題変数は命題の真偽falsetrueを要素とする集合{真,偽}上の変数である。命題変数及び命題変数の否定を総称してリテラルliteralと呼ぶ。論理式:論理式とは数理論理学における命題を表す形式的文法を有する式を意味する。具体的には真及び偽は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Zsec0を表す。0:0は個の0からなる列を表す。1:1は個の1からなる列を表す。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。なお、有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。また、有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献1ISOIEC180332InformationtechnologySecuritytechniquesEncryptionalgorithmsPart2Asymmetricciphersに開示されている。0F:0Fは有限体Fqの加法単位元を表す。1F:1Fは有限体Fqの乗法単位元を表す。δ:δはクロネッカーのデルタ関数を表す。ijの場合にδ1Fを満たし、i≠jの場合にδ0Fを満たす。E:Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィンaffine座標版のWeierstrass方程式y2a1xya3yx3a2x2a4xa6ただし、a1a2a3a4a6∈Fqを満たすxy∈Fqからなる点の集合に無限遠点と呼ばれる特別な点Oを付加したもので定義される。楕円曲線E上の任意の2点に対して楕円加算と呼ばれる二項演算及び楕円曲線E上の任意の1点に対して楕円逆元と呼ばれる単項演算-がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている例えば、参考文献1、参考文献2RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems、参考文献3イアンFブラケ、ガディエルセロッシ、ナイジェルPスマート=著、楕円曲線暗号、出版=ピアソンエデュケーション、ISBN4894714310等参照。また、楕円曲線E上の有理点からなる有限集合は位数pの部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数をEとし、pをEを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合Epは、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値pAがpA=Oを満たす点を意味する。G1G2GT:G1G2GTは位数qの巡回群を表す。巡回群G1G2の具体例は、楕円曲線Eのp等分点からなる有限集合Epやその部分群である。G1G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。巡回群G1G2GTの位数と有限体Fqの位数とを同一とすることで安全性が向上する。なお、本形態では、巡回群G1G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχΩ∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1Ω2∈G1に対するΩ1Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχΩ∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1Ω2∈G2に対するΩ1Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1Ω2∈GTに対するΩ1Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。Ψ:Ψは1以上の整数を表す。ψ:ψは0以上Ψ以下の整数ψ0Ψを表す。λ:λは1以上Ψ以下の整数λ1Ψを表す。n:nは1以上の整数を表す。ζ:ζは0以上の整数を表す。G1nζ:G1nζはnζ個の巡回群G1の直積を表す。G2nζ:G2nζはnζ個の巡回群G2の直積を表す。g1g2gT:g1g2gTは巡回群GG1G2GTの生成元を表す。V:Vはnζ個の巡回群G1の直積からなるnζ次元のベクトル空間を表す。V:Vはnζ個の巡回群G2の直積からなるnζ次元のベクトル空間を表す。eψ:eψは直積G1nζと直積G2nζとの直積G1nζ×G2nζを巡回群GTに写す非退化な双線形写像bilinearmapを表す。双線形写像eψは、巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力とし、巡回群GTの1個の元を出力する。eψ:G1nζ×G2nζ→GT...双線形写像eψは以下の性質を満たす。[双線形性]すべてのΓ1∈G1nζ,Γ2∈G2nζ及びν,κ∈Fqについて以下の関係を満たす。eψeψνκ...[非退化性]すべてのΓ1∈G1nζ,Γ2∈G2nζを巡回群GTの単位元に写す写像ではない。[計算可能性]あらゆるΓ1∈G1nζ,Γ2∈G2nζ...についてeψを効率的に計算するアルゴリズムが存在する。本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像PairG1×G2→GT...を用いて双線形写像eψを構成する。本形態の双線形写像eψは、巡回群G1のnζ個の元γβζからなるnζ次元ベクトルζと、巡回群G2のnζ個の元γβζからなるnζ次元ベクトルζとの入力に対し、巡回群GTの1個の元を出力する。eψ:Πβ1nζPair...なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力する。双線形写像Pairは、以下の性質を満たす。[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。PairPairνκ...[非退化性]すべてのΩ1∈G1,Ω2∈G2...を巡回群GTの単位元に写す写像ではない。[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPairを効率的に計算するアルゴリズムが存在する。双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である例えば、参考文献4AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181等参照。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数eΩ1∈G1,Ω2∈G2を双線形写像Pairとして用いてもよい例えば、参考文献2等参照。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMillerのアルゴリズム参考文献5VSMillerShortProgramsforfunctionsonCurves1986,インターネット<httpcryptostanfordedumillermillerpdf>などが存在する。また、ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている例えば、参考文献2、参考文献6AMiyajiMNakabayashiSTakanoNewexplicitconditionsofellipticcurveTracesforFRReductionIEICETransFundamentalsvolE84Ano05pp12341243May2001、参考文献7PSLMBarretoBLynnMScottConstructingellipticcurveswithprescribedembeddingdegreesProcSCN2002LNCS2576pp257267SpringerVerlag2003、参考文献8RDupontAEngeFMorainBuildingcurveswitharbitrarysmallMOVdegreeoverfiniteprimefieldshttpeprintiacrorg2002094等参照。aiζ:aiは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1g1∈G1をi次元目の要素とし、残りのnζ1個の要素を巡回群G1の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、nζ次元の基底ベクトルaiζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ11Fである。基底ベクトルaiは直交基底であり、巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiは前述のベクトル空間Vを張る。aiζ:巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ2g2∈G2をi次元目の要素とし、残りのnζ1個の要素を巡回群G2の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、基底ベクトルaiζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ21Fである。基底ベクトルaiは直交基底であり、巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiは前述のベクトル空間Vを張る。なお、基底ベクトルaiと基底ベクトルaiとは、0Fを除く有限体Fqの元τκ1κ2についてeψajgTτδ...を満たす。すなわち、ijの場合には、式の関係から、eψajPairPairPairPairκ1κ2Pair00Pair00Pairκ1κ2gTτを満たす。なお、上付き添え字κ1,κ2はそれぞれκ1,κ2を表す。一方、i≠jの場合には、eψajΠi1nζPairajの右辺は、Pairを含まず、PairとPairとPairとの積になる。さらに、式の関係からPairPairPair0を満たす。そのため、i≠jの場合には、eψajeψ0gT0を満たす。特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、eajgTδ...を満たす。ここで、gT01は巡回群GTの単位元であり、gT1gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルaiとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間双対ペアリングベクトル空間DPVSDualParingVectorspaceである。A:基底ベクトルaiζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiζが式によって表現される場合、行列Aは、となる。A:基底ベクトルaiζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiζが式によって表現される場合、行列Aは、となる。X:Xは有限体Fqの元を要素とするnζ行nζ列の行列を表す。行列Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列ζj1nζの要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。X:Xと行列XとはXτ1Tの関係を満たす。ただし、τ∈Fqは有限体Fqに属する任意の定数であり、例えば、τ1Fである。Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。この場合、nζ行nζ列の単位行列をIとするとXTτIを満たす。すなわち、単位行列に対し、を満たす。ここで、nζ次元ベクトルχi→χinζ...χj→χjnζ...を定義する。すると、式の関係から、nζ次元ベクトルχi→とχj→との内積は、χi→χj→τδ...となる。bi:biは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。biは行列Xを用いて基底ベクトルaiζを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajζが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。biκ1g1χi2κ1g1χinζκ1g1...巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。bi:biは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。biは行列Xを用いて基底ベクトルaiζを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajζが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。biκ2g2χi2κ2g2χinζκ2g2...となる。巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。なお、基底ベクトルbiと基底ベクトルbiとは、0Fを除く有限体Fqの元τκ1κ2についてeψbjgTττδ...を満たす。すなわち、式の関係から、を満たす。特にτκ1κ21F例えば、κ1κ21F及びτ1Fである場合、eψbjgTδ...を満たす。この場合、基底ベクトルbiと基底ベクトルbiとは、双対ペアリングベクトル空間ベクトル空間Vとベクトル空間Vの双対正規直交基底である。なお、式の関係を満たすのであれば、式で例示したもの以外の基底ベクトルai及びaiや、式で例示したもの以外の基底ベクトルbi及びbiを用いてもよい。B:Bは基底ベクトルbiζを要素とするnζ行nζ列の行列である。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、となる。B:Bは基底ベクトルbiζを要素とするnζ行nζ列の行列を表す。BXAを満たす。例えば、基底ベクトルbiζが式によって表現される場合、行列Bは、となる。v→:v→は有限体Fqの元を要素とするn次元ベクトルを表す。v→vn∈Fqn...vμ:vμはn次元ベクトルv→のμ番目の要素を表す。w→:w→は有限体Fqの元を要素とするn次元ベクトルを表す。w→wn∈Fqn...wμ:wμはn次元ベクトルw→のμ番目の要素を表す。Enc:Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。EncK:EncKは、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。Dec:Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。DecK:DecKは、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。関数暗号方式次に、関数暗号方式の基本的な構成について説明する。関数暗号方式とは、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となる場合に暗号文が復号される方式である。第1情報と第2情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、PredicateEncryptionSupportingDisjunctionsPolynomialEquationsandInnerProductswithAmitSahaiandBrentWatersOneof4papersfromEurocrypt2008invitedtotheJournalofCryptology参考文献9に開示された述語暗号方式は関数暗号方式の一種である。これ以外にも様々な公知の関数暗号方式が存在するが、以下では未公開の新たな関数暗号方式を説明する。以下に説明する新たな関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第1情報と第2情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧,∨,¬の何れか又はすべてを含む。そして、各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が真となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。<論理式と階層的な秘密分散との関係>上述した所定の論理式と階層的な秘密分散との関係を説明する。秘密分散とは、しきい値Kt個以上のシェア情報が得られた場合にのみ秘密情報が復元されるように、秘密情報をN個のシェア情報に分散することである。KtNを満たす秘密分散の方式SSSSecretSharingSchemeをNoutofN分散方式或いはNoutofNしきい値分散方式といい、Kt<Nを満たす秘密分散の方式をKtoutofN分散方式或いはKtoutofNしきい値分散方式という例えば、参考文献10黒沢馨、尾形わかは、現代暗号の基礎数理、コロナ社、2004年3月、p116119、参考文献11AShamirHowtoShareaSecretCommunicationsoftheACMNovember1979Volume22Number11pp612613等参照。NoutofN分散方式は、すべてのシェア情報shareshareが与えられれば秘密情報SEを復元できるが、任意のN1個のシェア情報shareshareが与えられても秘密情報SEの情報はまったく得られない方式である。以下に、その一例を示す。SH1SHN1をランダムに選択する。SHNSEの計算を行う。SH1SHNを各シェア情報shareshareとする。すべてのシェア情報shareshareが与えられれば、SEshareshare...の復元処理によって秘密情報SEの復元が可能である。KtoutofN分散方式は、任意の相違なるKt個のシェア情報shareshareが与えられれば秘密情報SEを復元できるが、任意のKt1個のシェア情報shareshareが与えられても秘密情報SEの情報はまったく得られない方式である。なお、添え字のKtはKtを表す。以下にKtoutofN分散方式の一例を示す。fSEを満たすKt1次の多項式fξ0ξ1xξ2x2ξKt1xKt1をランダムに選ぶ。すなわち、ξ0SEとし、ξ1ξKt1をランダムに選ぶ。シェア情報をshareρ1Nとする。なお、はρ及びfの値をそれぞれ抽出可能な情報であり、例えばρとfとのビット結合値である。任意の相違なるKt個のシェア情報shareshare⊂が得られた場合、例えば、ラグランジェの補間公式を用い、以下のような復元処理によって秘密情報SEの復元が可能である。SEfLA1fLAKtf...は先頭からρ番目の被演算子分母の要素、分子の要素が存在しないことを意味する。すなわち、式の分母は、であり、式の分子は、である。上述した各秘密分散は体上でも実行可能である。また、これらを拡張して秘密情報SEに応じた値をシェア情報shareに秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報shareshareに応じた巡回群GTの元gTsharegTshare∈GTに秘密分散することもできる。また、上述した秘密情報SEはシェア情報shareの線形結合となる式。このように秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ドモルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧,∨の少なくとも一部とリテラルとからなる論理式これらを標準形論理式と呼ぶことにするによって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは1個以上の子ノードの親ノードとされ、親ノードの1つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散したシェア情報に応じた値が対応する。各ノードでの秘密分散形態秘密分散方式やしきい値は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値その親ノードがルートノードであれば秘密情報に応じた値は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成各ノードでの秘密分散の形態を含むとに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。そして、各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。以下に具体例を示す。図6は、命題変数PROPROと命題変数PROの否定¬PROと論理記号∧,∨とを含む標準形論理式PRO∧PRO∨¬PROを表現する木構造データを例示する図である。図6に例示する木構造データは複数のノードN1N5を含む。ノードN1はノードN2N5の親ノードとされ、ノードN2はノードN3N4の親ノードとされ、親ノードの1つノードN1がルートノードとされ、子ノードの一部であるノードN3N4N5が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2N5には、秘密情報SEに応じた値が1outof2分散方式で秘密分散された各シェア情報SESEに応じた値がそれぞれ対応する。ノードN2の子ノードN3N4には、シェア情報SEに応じた値が2outof2分散方式で秘密分散された各シェア情報SESH1SH1に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報shareSESH1に応じた値が対応し、葉ノードN4にはシェア情報shareSH1に応じた値が対応し、葉ノードN5にはシェア情報shareSEに応じた値が対応する。また、葉ノードN3N4N5には標準形論理式PRO∧PRO∨¬PROを構成する各リテラルPROPRO¬PROがそれぞれ対応し、当該各リテラルPROPRO¬PROの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式PRO∧PRO∨¬PROの真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。図7は、命題変数PROPROPROPROPROと命題変数PROPROの否定¬PRO¬PROと論理記号∧,∨とを含む標準形論理式PRO∧PRO∨PRO∧PRO∨PRO∧PRO∨¬PRO∨∧PRO∧PROを表現する木構造データを例示する図である。図7に例示する木構造データは複数のノードN1N11を含む。ノードN1はノードN2N6N7の親ノードとされ、ノードN2はノードN3N4N5の親ノードとされ、ノードN7はノードN8N11の親ノードとされ、ノードN8はノードN9N10の親ノードとされ、親ノードの1つであるノードN1がルートノードとされ、ノードN3N4N5N6N9N10N11が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2N6N7には、秘密情報SEに応じた値が1outof3分散方式で秘密分散された各シェア情報SESESEに応じた値がそれぞれ対応する。ノードN2の子ノードN3N4N5には、シェア情報SEに応じた値が2outof3分散方式で秘密分散された各シェア情報に応じた値がそれぞれ対応する。ノードN7の子ノードN8N11には、シェア情報SEに応じた値が2outof2分散方式で秘密分散された各シェア情報SH4SESH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9N10には、シェア情報SH4に応じた値が1outof2分散方式で秘密分散された各シェア情報SH4SH4に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報shareに応じた値が対応し、葉ノードN4にはシェア情報shareに応じた値が対応し、葉ノードN5にはシェア情報shareに応じた値が対応し、葉ノードN6にはシェア情報shareSEに応じた値が対応し、葉ノードN9にはシェア情報shareSH4に応じた値が対応し、葉ノードN10にはシェア情報shareSH4に応じた値が対応し、葉ノードN11にはシェア情報shareSESH4に応じた値が対応する。また、葉ノードであるノードN3N4N5N6N9N10N11には標準形論理式PRO∧PRO∨PRO∧PRO∨PRO∧PRO∨¬PRO∨∧PRO∧PROを構成する各リテラルPROPROPROPROPROPRO¬PRO¬PROPROPROがそれぞれ対応し、各リテラルPROPROPROPROPROPRO¬PRO¬PROPROPROの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式PRO∧PRO∨PRO∧PRO∨PRO∧PRO∨¬PRO∨∧PRO∧PROの真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。<アクセス構造>上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第1情報と第2情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となるか偽となるかを判定できる。以下、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となる場合に第1情報と第2情報との組み合わせを受け入れ、偽となる場合に第1情報と第2情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ1Ψとする。各葉ノードに対応するn次元ベクトルv→の集合v→λ1Ψを第1情報とし、n次元ベクトルw→の集合w→λ1Ψを第2情報とする。また、上述した木構造データをラベル付き行列LMTとして実装する。ラベル付き行列LMTは、Ψ行COL列COL≧1の行列と、行列MTの各行λ1Ψに対応付けられたラベルLABとを含む。行列MTの各要素mtλcolcol1COLは次の2つの要件を満たす。第1に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトルGV→∈FqCOL...と、秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトルCV→∈FqCOL...とに対してSEGV→T...が成立する。COL次元ベクトルGV→の具体例は、GV→∈FqCOL...であるが、GV→∈FqCOLなどのその他のCOL次元ベクトルであってもよい。第2に、識別子λに対応する葉ノードにシェア情報share∈Fqに応じた値が対応する場合、shareTMTT...が成立する。上述のように所定の論理式を表現した木構造データが定まれば、これら2つの要件を満たす行列MTを選択することは容易である。また、秘密情報SEやシェア情報shareが変数であったとしても、これら2つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報shareの値が定められてもよい。また、行列MTの各行λ1Ψに対応付けられたラベルLABは、識別子λに対応する葉ノードに対応するリテラルPRO又は¬PROに対応する。ここで、命題変数PROの真理値が真であることと第1情報VSET1λv→λ1Ψが含むv→と第2情報VSET2λw→λ1Ψが含むw→との内積v→w→が0となることとが等価であると扱い、命題変数PROの真理値が偽であることと内積v→w→が0とならないこととが等価であると扱う。そして、PROに対応するラベルLABがv→を表し、¬PROに対応するラベルLABが¬v→を表すものとする。なお、¬v→はv→の否定を表す論理式であり、¬v→からv→の特定が可能である。また、LABがv→を表すことをLABv→と表記し、LABが¬v→を表すことをLAB¬v→と表記する。また、LABλ1Ψの集合LABλ1ΨをLABと表記する。さらに、Ψ次元ベクトルTFV→tfv...を定義する。要素tfvは、内積v→w→が0のときにtfv1となり、0以外のときにtfv0となる。tfv1PROが真ifv→w→0...tfv0PROが偽ifv→w→≠0...さらに、論理式v→∧1∨¬v→∧0...の真理値が真になるときLIT1と表記し偽になるときLIT0と表記する。すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が真になるときLIT1と表記し偽になるときLIT0と表記する。すると、行列MTが含む行ベクトルのうちLIT1となる行ベクトルmtλ→のみからなる部分行列MTTFVは以下のように表記できる。MTTFVLIT1...上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報shareに応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属するか否かを判定することで、識別子λに対応するシェア情報shareに応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。なお、行ベクトルmtλ→で張られるベクトル空間とは、行ベクトルmtλ→の線形結合で表すことができるベクトル空間を意味する。ここで、上述の部分行列MTTFVの各行ベクトルmtλ→で張られるベクトル空間spanにCOL次元ベクトルGV→が属する場合に第1情報と第2情報との組み合わせが受け入れられ、そうでない場合に第1情報と第2情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMTが第1情報に対応する場合、アクセス構造が第1情報と第2情報との組み合わせを受け入れることをアクセス構造が第2情報を受け入れるといい、アクセス構造が第1情報と第2情報との組み合わせを受け入れないことをアクセス構造が第2情報を拒絶するという。受け入れifGV→∈span拒絶if¬また、GV→∈spanの場合、SEΣμ∈SETconstshare...const∈Fqμ∈SETSET⊆1λLIT1を満たす係数constが存在し、このような係数constは行列MTのサイズの多項式時間で求めることができる。<アクセス構造を用いた関数暗号方式の基本構成>以下では、アクセス構造を用いた関数暗号方式によって鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。この構成はSetupn,GenKey,Enc→λ1Ψ1F,Decを含む。また、第2情報VSET2λw→λ1Ψの1番目の要素w1が1Fとされる。[Setupn:セットアップ]-入力:1sec,n-出力:マスター鍵情報MSK,公開パラメータPKSetupでは各ψ0Ψについて以下の処理が実行される。1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1G2GT、双線形写像eψが生成されるparam。τ∈Fqが選択され、Xτ1Tを満たす行列X,Xが選択される。基底ベクトルaiζが式に従って座標変換され、nζ次元の基底ベクトルbiζが生成される。基底ベクトルbiζを要素とするnζ行nζ列の行列Bが生成される。基底ベクトルaiζが式に従って座標変換され、nζ次元の基底ベクトルbiζが生成される。基底ベクトルbiζを要素とするnζ行nζ列の行列Bが生成される。B^の集合B^ψ0Ψをマスター鍵情報MSKB^ψ0Ψとする。また、B^の集合B^ψ0Ψと1secとparamとを公開パラメータPKとする。ただし、B^は行列B又はその部分行列であり、B^は行列B又はその部分行列である。また、集合B^ψ0Ψは、少なくとも、b1b1...bnλ1Ψを含む。また、集合B^ψ0Ψは、少なくとも、b1b1...bnλ1Ψを含む。以下に一例を示す。nζ≧5ζ3nB^b3b5TB^...bnb3n1...b4nTλ1ΨB^b3b4TB^...bnb2n1...b3nTλ1Ψ[GenKey:鍵情報生成]-入力:公開パラメータPK,マスター鍵情報MSK,第1情報VSET1λv→λ1Ψに対応するラベル付き行列LMT-出力:鍵情報SKS式を満たす秘密情報SEに対して以下の処理が実行される。DSEb1Σι2Icoefιbι...ただし、Iは2以上nζ以下の定数である。coefι∈Fqは定数又は乱数である。乱数とは真性乱数や擬似乱数を意味する。以下にDの一例を示す。なお、式のcoef4は乱数である。DSEb1b3coef4b4...式を満たすshareに対して以下の処理が実行される。LABv→となるλに対してDcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι...が生成され、LAB¬v→となるλに対してDshareΣι1nvιbιΣιn1nζcoefιbι...が生成される。ただしcoefcoefι∈Fqは定数又は乱数である。以下に一例を示す。LABv→となるλに対してDcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbι...が生成され、LAB¬v→となるλに対してDshareΣι1nvιbιΣι2n13ncoefιbι...が生成される。なお、式のcoef及びcoefιは乱数である。鍵情報SKSDDD...生成される。[Enc:暗号化]-入力:公開パラメータPK,平文M,第2情報VSET2λw→λ1Ψ1F-出力:暗号文C以下の処理によって共通鍵Kの暗号文Cが生成される。Cυb1Σι2Iυιbι...CυΣι1nwιbιΣιn1nζυιbι...ただし、υυι∈Fqは定数又は乱数であり、coefIυIυ...coefιυι0F1nζ...を満たす。υの例はυ2υIの何れか1個である。例えば、υυ3υ5υ3n1υ4nが乱数であり、ζ3n、I5であり、υI0Fυ5υυ31υ3nである。共通鍵KgTττυ∈GT...が生成される。例えば、ττ1Fの場合、KgTυ∈GT...である。共通鍵Kを用いて平文Mの暗号文CEncK...が生成される。なお、共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリアCamellia登録商標やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncKを生成してもよい。ただし、式の例ではM∈GTとされる。CgTυM...暗号文CC→∈VSET2C...が生成される。ただし、下付き添え字のw→はw→を表す。[Dec:復号]-入力:公開パラメータPK,鍵情報SKS,暗号文C-出力:平文Mλ1Ψについて、鍵情報SKSが含むラベル付き行列LMTの各ラベルLABであるn次元ベクトルv→と暗号文CのVSET2が含むn次元ベクトルw→との内積v→w→が0となるか否かが判定され、これとLMTの各ラベルLABとによってGV→∈spanであるか否かが判定される式。GV→∈spanでなければ暗号文Cが拒絶され、GV→∈spanであれば暗号文Cが受け入れられる。暗号文Cが受け入れられると、SET⊆1λLIT1と式を満たす係数constとが計算される。共通鍵が生成される。ここで、式から、を満たす。また、式及びw11Fからを満たす。また、式からを満たす。よって、式からを満たす。例えば、ττ1Fの場合、KgTυ∈GT...を満たす。共通鍵Kを用いて平文MDecKDecK...が生成される。例えば、式に例示した共通鍵暗号方式の場合、MCK...によって平文Mが生成される。なお、gTをGTの生成元とする代わりにgTτやgTτやgTττをGTの生成元と扱ってもよい。また、鍵情報SKSのλと暗号文のλとを対応関係を特定する写像を用いてCとDとの組み合わせを特定し、[Dec:復号]の処理が実行されてもよい。また、第2情報VSET2λw→λ1Ψの1番目の要素w1が1Fとされるだけではなく、第1情報VSET1λv→λ1Ψのn番目の要素vnが1Fとされてもよい。また、要素w1が1Fでない場合にはw→の代わりにw→w1を用いてもよく、要素vnが1Fでない場合にはv→の代わりにv→vnを用いてもよい。また、第1情報VSET1λv→λ1Ψの代わりに第2情報VSET2λw→λ1Ψが用いられ、第2情報VSET2λw→λ1Ψの代わりに第1情報VSET1λv→λ1Ψが用いられてもよい。この場合には第1情報VSET1λv→λ1Ψの1番目の要素v1が1Fとされる。次に、関数暗号の一形態である述語暗号の一例として内積を用いた述語暗号について説明する。なお、数式の番号は本節で改めて付け直している。また、説明の都合、上述の説明で用いた文言や記号と同じ文言や記号であっても意味が異なる場合があるので注意されたい。述語暗号は1outof1分散方式を用いた関数暗号に相当する。定義次に、以下の各実施形態で使用される用語や記号を定義する。行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列と表現する。T:Tはの転置行列を表す。1:1はの逆行列を表す。∧:∧は論理積を表す。∨:∨は論理和を表す。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Zsec0を表す。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。0F:0Fは有限体Fqの加法単位元零元を表す。一般化した加法単位元を0と表す。1F:1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。δ:δはクロネッカーのデルタ関数を表す。ijの場合にδ1Fを満たし、i≠jの場合にδ0Fを満たす。E:Eは有限体Fq上で定義された楕円曲線を表す。G1G2GT:G1G2GTは位数qの巡回群を表す。巡回群G1G2の具体例は、楕円曲線Eのp等分点からなる有限集合Epやその部分群である。G1G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。なお、本形態では、巡回群G1G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχΩ∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1Ω2∈G1に対するΩ1Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχΩ∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1Ω2∈G2に対するΩ1Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1Ω2∈GTに対するΩ1Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。n:nは1以上の整数を表す。ζ:ζは1以上の整数を表す。ζの一例は2又は3である。G1nζ:G1nζはnζ個の巡回群G1の直積を表す。G2nζ:G2nζはnζ個の巡回群G2の直積を表す。g1g2gT:g1g2gTは巡回群GG1G2GTの生成元を表す。V:Vはnζ個の巡回群G1の直積からなるnζ次元のベクトル空間を表す。V:Vはnζ個の巡回群G2の直積からなるnζ次元のベクトル空間を表す。e:eは直積G1nζと直積G2nζとの直積G1nζ×G2nζを巡回群GTに写す非退化な双線形写像bilinearmapを表す。双線形写像eは、巡回群G1のnζ個の元γβと巡回群G2のnζ個の元γβとを入力とし、巡回群GTの1個の元を出力する。e:G1nζ×G2nζ→GT...双線形写像eは以下の性質を満たす。[双線形性]すべてのΓ1∈G1nζ,Γ2∈G2nζ及びν,κ∈Fqについて以下の関係を満たす。eeνκ...[非退化性]すべてのΓ1∈G1nζ,Γ2∈G2nζを巡回群GTの単位元に写すものではない。[計算可能性]あらゆるΓ1∈G1nζ,Γ2∈G2nζ...についてeを効率的に計算するアルゴリズムが存在する。本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数PairG1×G2→GT...を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のnζ個の元γβからなるnζ次元ベクトルと、巡回群G2のnζ個の元γβからなるnζ次元ベクトルとの入力に対し、巡回群GTの1個の元eΠβ1nζPair...を出力する。なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力するものであり、以下の性質を満たす。[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。PairPairνκ...[非退化性]すべてのΩ1∈G1,Ω2∈G2...を巡回群GTの単位元に写すものではない。[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPairを効率的に計算するアルゴリズムが存在する。なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである例えば、参考文献1AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181、参考文献2RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems等参照。ai:aiは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、nζ次元の基底ベクトルaiの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ11Fである。基底ベクトルaiは直交基底であり、巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。ai:巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ2g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、基底ベクトルaiの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ21Fである。基底ベクトルaiは直交基底であり、巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。なお、基底ベクトルaiと基底ベクトルaiとは、0Fを除く有限体Fqの元τκ1κ2についてegTτδ...を満たす。すなわち、ijの場合には、式の関係から、ePairPairPairPairκ1κ2Pair00Pair00Pairκ1κ2gTτを満たす。一方、i≠jの場合には、eΠi1nζPairの右辺は、Pairを含まず、PairとPairとPairとの積になる。さらに、式の関係からPairPairPair0を満たす。そのため、i≠jの場合には、ee0gT0を満たす。特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、egTδ...を満たす。ここで、gT01は巡回群GTの単位元であり、gT1gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルaiとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間双対ペアリングベクトル空間DPVSDualParingVectorspaceである。A:基底ベクトルaiを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiが式によって表現される場合、行列Aは、となる。A:基底ベクトルaiを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiが式によって表現される場合、行列Aは、となる。X:有限体Fqの元を要素とするnζ行nζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。X:Xは行列Xの逆行列の転置行列XTを表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。この場合、nζ行nζ列の単位行列をIとするとXTIを満たす。すなわち、単位行列に対し、を満たす。ここで、nζ次元ベクトルχi→...χj→...を定義する。すると、式の関係から、nζ次元ベクトルχi→とχj→との内積は、χi→χj→δ...となる。bi:biは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaiを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。bi...巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。bi:biは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaiを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。bi...となる。巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。なお、基底ベクトルbiと基底ベクトルbiとは、0Fを除く有限体Fqの元τκ1κ2についてegTτδ...を満たす。すなわち、式の関係から、を満たす。特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、egTδ...を満たす。この場合、基底ベクトルbiと基底ベクトルbiとは、双対ペアリングベクトル空間ベクトル空間Vとベクトル空間Vの双対正規直交基底である。なお、式の関係を満たすのであれば、式で例示したもの以外の基底ベクトルai及びaiや、式で例示したもの以外の基底ベクトルbi及びbiを用いてもよい。B:Bは基底ベクトルbiを要素とするnζ行nζ列の行列。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、となる。B:Bは基底ベクトルbiを要素とするnζ行nζ列の行列を表す。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、となる。内積述語暗号方式次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。[内積と論理式の真理値との関係]内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。まず、x1がη1であるという命題1とx2がη2であるという命題2との論理和∨を...という多項式で表現する。すると、各真理値と式の関数値との関係は以下のようになる。表1から分かるように、論理和∨が真である場合、式の関数値は0になり、論理和∨が偽である場合、式の関数値は0以外の値となる。すなわち、論理和∨が真であることと、式の関数値が0となることとは等価である。よって、論理和は式で表現できる。また、x1がη1であるという命題1とx2がη2であるという命題2との論理積∧をι1ι2...という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式の関数値とは以下の関係となる。表2から分かるように、論理積∧が真である場合、式の関数値は0になり、論理積∧が偽である場合、式の関数値は0以外の値となる。すなわち、論理積∧が真であることと、式の関数値が0となることとは等価である。よって、論理積は式で表現できる。以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式∨∧∧は、多項式ι1ι2ι3...で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式の述語多項式は、各項の不定元成分と1を各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw→とし、復号鍵に埋め込まれるベクトルをv→とする。[内積述語暗号方式の基本構成]内積述語暗号方式で鍵カプセル化メカニズムKEMを構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:マスター鍵情報MSK,公開パラメータPKSetupの一例では、まず、セキュリティパラメータsecをnとして、nζ次元の基底ベクトルaiを要素とするnζ行nζ列の行列Aと、基底ベクトルaiを要素とするnζ行nζ列の行列Aと、座標変換のためのnζ行nζ列の行列X,Xとが選択される。次に、式に従って座標変換されたnζ次元の基底ベクトルbiが算出され、式に従って座標変換されたnζ次元の基底ベクトルbiが算出される。そして、基底ベクトルbiを要素とするnζ行nζ列の行列Bがマスター鍵情報MSKとして出力され、ベクトル空間VV、基底ベクトルbiを要素とするnζ行nζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1G2GT、生成元g1g2gT、双線形写像eなどが公開パラメータPKとして出力される。《GenKey:復号鍵生成》-入力:マスター鍵情報MSK,ベクトルv→-出力:ベクトルv→に対応する復号鍵DGenKeyの一例では、まず、有限体Fqから元σσιn∈Fqが選択される。そして、マスター鍵情報MSKである行列Bを用い、ベクトルv→に対応する復号鍵DσΣιn1nζσιnbι∈G2nζ...が生成され、出力される。ただし、σσιnは乱数などの変数や定数などであり、ζ≦ζである例えばζ3ζ2。またΣιn1nζσιnはシステムで共有される定数値とされる。以下ではΣιn1nζσιn1F...とされた例を説明する。これは本発明を限定しない。《Enc:暗号化》-入力:公開パラメータPK,ベクトルw→,平文mes-出力:暗号文Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ0υ1υζと、ベクトルw→とを用い、暗号文C1υ0Σμn1nζυμnbμ∈G1nζ...が生成される。ただし、υ1υζ...を満たす例えばζ2のときにはυ1υ2。また、gTτυ1を共通鍵Kとし、所定の共通鍵暗号方式第2暗号方式に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、C2gTτυ1mes...である。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ1Fである。生成された暗号文は出力される。《Dec:復号》-入力:ベクトルv→に対応する復号鍵D,暗号文-出力:復号値mesDecの一例では、まず、暗号文C1と復号鍵Dとが式の双線形写像eに入力され、その演算結果を共通鍵Keとし、以下のように復号値mesが求められる。mesC2e∈GT...ここで、式の性質から、を満たす。内積w→v→0であれば、式は、を満たす。式から、内積w→v→0であればmesmesとなり、正しく復号されることがわかる。[階層的内積述語暗号方式の基本構成]階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。《前提》深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。ξ→...有限体Fqの元を要素とするξωξω1次元のベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mm≦dまでに対応するベクトルをとする。有限体Fqの元を要素とするξωξω1次元ω1dのベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mまでに対応するベクトルをとする。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:階層フォーマットξ→,マスター秘密鍵MSK,公開パラメータmpkSetupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ→が定められる。また、この例ではζ3とし、n3次元の基底ベクトルaiを要素とするn3行n3列の行列Aと、基底ベクトルaiを要素とするn3行n3列の行列Aと、座標変換のためのn3行n3列の行列X,Xとが選択される。次に、式に従って座標変換されたn3次元の基底ベクトルbiが算出され、式に従って座標変換されたn3次元の基底ベクトルbiが算出される。この例では、基底ベクトルと行列Xとがマスター秘密鍵MSKとして出力され、基底ベクトル、ベクトル空間VV、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1G2GT、生成元g1g2gT、双線形写像eなどが公開パラメータmpkとして出力される。《GenKey:鍵情報生成》-入力:マスター秘密鍵MSK,公開パラメータmpk,ベクトル-出力:ベクトルに対応する鍵情報kmGenKeyの一例では、まず、有限体Fqから元σα,ω,Ψ,Φα∈Fqが任意に選択される。この例では、これらとマスター秘密鍵MSKである基底ベクトルとベクトルとを用い、ベクトルに対応する鍵情報が生成されて出力される。ただし、である。《Delegate:鍵情報生成委譲》-入力:公開パラメータmpk,鍵情報km,ベクトルvm1→-出力:ベクトルに対応する鍵情報km1階層的内積述語暗号方式では、マスター秘密鍵MSKを用いることなく、公開パラメータmpk,鍵情報km,ベクトルvm1→からベクトルに対応する鍵情報km1を生成できる。ただし、m1d1である。Delegateの一例では、有限体Fqから元σα,ω,Ψ,Φα∈Fqが任意に選択される。この例では、これらと鍵情報kmとベクトルvm1→と用い、ベクトルに対応する鍵情報が生成されて出力される。ただし、である。《Enc:暗号化》-入力:公開パラメータmpk,ベクトル,平文mes-出力:暗号文Encの一例では、まず、有限体Fqから任意の元υ1υdυn3υが選択される。そして、これらと公開パラメータmpkとベクトルとを用い、暗号文が生成される。また、gTτυを共通鍵Kとし、所定の共通鍵暗号方式第2暗号方式に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、C2gTτυmes...である。なお、前述のように定数τの一例はτ1Fである。その後、以上のように生成された暗号文が出力される。《Dec:復号》-入力:公開パラメータmpk,ベクトルに対応する鍵情報km,暗号文-出力:復号値mesDecの一例では、mesC2e...によって復号値mesを計算する。暗号文C1と鍵情報kmのkm0とが式の双線形写像eこの例ではζ3に入力されると、式の性質から、を満たす。なお、σω及びσは有限体Fqの元である。Delegateがなされることなく鍵情報kmが生成された場合にはσωσ0,ωである。Delegateが1回以上なされた場合には、GenKeyに使用された有限体Fqの元σα,ωやDelegate時に使用された有限体Fqの元σα,ωやΦαに応じてσωの値が定まる。ここで、すべてのω1mについて内積vω→wω→0Fであれば、式は、egTτυ...と変形できる。式より、すべてのω1mについて内積vω→wω→0Fである場合にmesmesとなり、正しく復号がなされることがわかる。<補記>時限暗号システムに含まれるハードウェアエンティティ時刻サーバ装置、送信者装置、受信者装置は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置例えば通信ケーブルが接続可能な通信部、CPUCentralProcessingUnitキャッシュメモリやレジスタなどを備えていてもよい。、メモリであるRAMやROM、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、CPU、RAM、ROM、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、CD-ROMなどの記録媒体を読み書きできる装置ドライブなどを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるROMに記憶させておくなどでもよい。。また、これらのプログラムの処理によって得られるデータなどは、RAMや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するRAMやレジスタなどの記憶装置を単に記憶部とした。ハードウェアエンティティでは、外部記憶装置あるいはROMなどに記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にCPUで解釈実行処理される。その結果、CPUが所定の機能例えば、初期設定部、時刻トークン生成部、暗号文生成部、復号部などを実現する。各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略したこの点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばPARI/GP、KANT/KASHなどが挙げられる。PARI/GPについては、例えばインターネットURLhttpparimathubordeauxfr[平成23年1月13日検索]を参照のこと。KANT/KASHについては、例えばインターネットURLhttpwwwmathtuberlindealgebraやhttpwwwmathtuberlindekantkashhtml[平成23年1月13日検索]を参照のこと。。また、この点に関する文献として、参考文献Aを挙げることができる。参考文献AHCohenACourseinComputationalAlgebraicNumberTheoryGTM138SpringerVerlag1993本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVDDigitalVersatileDisc、DVD-RAMRandomAccessMemory、CD-ROMCompactDiscReadOnlyMemory、CD-RRecordable/RWReWritable等を、光磁気記録媒体として、MOMagnetoOpticaldisc等を、半導体メモリとしてEEP-ROMElectronicallyErasableandProgrammableReadOnlyMemory等を用いることができる。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"