(57)【特許請求の範囲】
【請求項１】
鍵発行装置と、送信者装置と、受信者装置とを含み、予め定められた時間以外において暗号文の復号が失敗する時限暗号システムであって、
公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、
Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（以下、平文という）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、
Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）と
を含み、上記情報iと上記情報jが予め定められた関係Ｒを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記鍵発行装置は、
上記情報iを上記復号アルゴリズムの実行の時的制限に係る上記予め定められた時間に関する情報t（以下、時的制限情報tという）を含む情報として、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵skt←KeyGen(sk,i)を生成する秘密鍵生成部を含み、
上記送信者成装置は、
上記情報jを暗号文に設定される時刻t'（以下、暗号化時刻t'という）を含む情報とし、上記暗号の暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文ct'←Enc(pk,j,x)を生成する暗号文生成部を含み、
上記受信者装置は、
上記秘密鍵skiを上記秘密鍵sktとし、上記暗号文cjを上記暗号文ct'として、上記暗号の復号アルゴリズムDec(pk,skt,ct')を実行する復号部を含み、
上記時的制限情報tを時刻とし、
上記関係Ｒは、上記時的制限情報tに対してTを述語変数とするt≧Tなる述語と当該述語変数Tに代入されうる上記暗号化時刻t'との関係Ｒ１と、受信者の属性を表す述語変数である第２の上記情報iと受信者の属性に対する必要条件を表す述語である第２の上記情報jとの間の関係Ｒ２とからなる関係であり、
上記秘密鍵生成部は、上記情報iを上記述語t≧Tと第２の上記情報iとの結合として、上記鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵skt←KeyGen(sk,i)を生成し、
上記暗号文生成部は、上記情報jを上記暗号化時刻t'と第２の上記情報jとの結合として、上記暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文ct'←Enc(pk,j,x)を生成し、
上記復号部は、上記時的制限情報tと上記暗号化時刻t'とが予め定められた関係Ｒ１を満たし、かつ、第２の上記情報iと第２の上記情報jとが予め定められた関係Ｒ２を満たすときに、上記平文xが得られるものである
ことを特徴とする時限暗号システム。
【請求項２】
鍵発行装置と、送信者装置と、受信者装置とを含み、予め定められた時間以外において暗号文の復号が失敗する時限暗号システムにおける時限暗号方法であって、
公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、
Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（以下、平文という）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、
Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）と
を含み、上記情報iと上記情報jが予め定められた関係Ｒを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記鍵発行装置の秘密鍵生成部が、上記情報iを上記復号アルゴリズムの実行の時的制限に係る上記予め定められた時間に関する情報tを含む情報として、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵skt←KeyGen(sk,i)を生成する秘密鍵生成ステップと、
上記送信者成装置の暗号文生成部が、上記情報jを暗号文に設定される時刻t'を含む情報とし、上記暗号の暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文ct'←Enc(pk,j,x)を生成する暗号文生成ステップと、
上記受信者装置の復号部が、上記秘密鍵skiを上記秘密鍵sktとし、上記暗号文cjを上記暗号文ct'として、上記暗号の復号アルゴリズムDec(pk,skt,ct')を実行する復号ステップとを有し、
上記時的制限情報tを時刻とし、
上記関係Ｒは、上記時的制限情報tに対してTを述語変数とするt≧Tなる述語と当該述語変数Tに代入されうる上記暗号化時刻t'との関係Ｒ１と、受信者の属性を表す述語変数である第２の上記情報iと受信者の属性に対する必要条件を表す述語である第２の上記情報jとの間の関係Ｒ２とからなる関係であり、
上記秘密鍵生成ステップは、上記情報iを上記述語t≧Tと第２の上記情報iとの結合として、上記鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵skt←KeyGen(sk,i)を生成し、
上記暗号文生成ステップは、上記情報jを上記暗号化時刻t'と第２の上記情報jとの結合として、上記暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文ct'←Enc(pk,j,x)を生成し、
上記復号ステップは、上記時的制限情報tと上記暗号化時刻t'とが予め定められた関係Ｒ１を満たし、かつ、第２の上記情報iと第２の上記情報jとが予め定められた関係Ｒ２を満たすときに、上記平文xが得られるものである
時限暗号方法。
【請求項３】
請求項１に記載の時限暗号システムにおいて用いられる上記鍵発行装置。
【請求項４】
請求項１に記載の時限暗号システムにおいて用いられる上記送信者装置。
【請求項５】
請求項１に記載の時限暗号システムにおいて用いられる上記受信者装置。
【請求項６】
請求項３に記載の鍵発行装置、請求項４に記載の送信者装置、請求項５に記載の受信者装置のいずれかとしてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は時限暗号技術に関する。
【背景技術】
【０００２】
暗号システムを運用する際、秘密鍵は運用の誤りや機器の故障などによる漏洩の危機に常に晒されている。単位時間当たりに一定の確率ε(0<ε<1)で秘密鍵の漏洩事故が発生すると仮定すると、運用開始から或る時刻ｔまでに漏洩事故が発生する確率は1-(1-ε)ｔであり、ε≠０である限り時刻ｔの進行と共に漏洩事故の発生確率は指数的に１に近づく。つまり、秘密鍵の漏洩事故の発生は事実上不可避と言える。
【０００３】
しかしながら、実際に秘密鍵の漏洩事故が発生してもユーザがその事実に気付かないことが多い。従って、暗号システムを安全に運用したい場合は、一般的に、発行の時から一定の期間を過ぎた秘密鍵を新しい秘密鍵に更新することが好ましい。
【０００４】
なお、暗号技術に係るこのような保守管理（秘密鍵の更新）は周知であるから、先行技術文献を挙げるまでもない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、秘密鍵を管理するスキルの乏しいユーザは秘密鍵の更新を怠りがちである。
【０００６】
そこで本発明は、暗号文に設定された時刻（暗号化時刻）が予め設定された時的制限情報（復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報）を満たさない場合に暗号文の復号に失敗する時限暗号技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の時限暗号技術は、次のとおりである。公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（以下、平文という）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）とを含み、情報iと情報jが予め定められた関係Ｒを満たすときに情報yとして平文xが得られるように構成されている。時限暗号システムを構成する鍵発行装置では、情報iを復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t（時的制限情報t）を含む情報として、暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵skt←KeyGen(sk,i)を生成する[秘密鍵生成処理]。時限暗号システムを構成する送信者成装置では、情報jを暗号文に設定される時刻t'（暗号化時刻t'）を含む情報とし、暗号の暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する[暗号文生成処理]。時限暗号システムを構成する受信者装置では、秘密鍵skiを秘密鍵sktとし、暗号文cjを暗号文ct'として、暗号の復号アルゴリズムDec(pk,skt,ct')を実行する[復号処理]。
【発明の効果】
【０００８】
本発明に拠れば、暗号化時刻が時的制限情報を満たさない場合に暗号文の復号に失敗するので、秘密鍵を利用するユーザ（つまり、受信者装置のユーザ）に対して秘密鍵の更新を動機付けることになる。また、仮に秘密鍵が漏洩しても、時的制限情報を満たさない時刻が設定された暗号文は、時的制限情報を満たす時刻以外の時刻において復号されないので、当該暗号文の安全性が高まる。
【図面の簡単な説明】
【０００９】
【図１】実施形態の時限暗号システムを示す図。
【図２】実施形態における時限暗号の処理手順を示す図。
【図３】実施形態に関わる時限暗号システムの構成要素である鍵発行装置、送信者装置、受信者装置の機能構成を示す図。
【図４】ビット表現された整数変数tと定数t'とを比較する述語の構成方法（t＞t'）。
【図５】ビット表現された整数変数tと定数t'とを比較する述語の構成方法（t≧t'）。
【発明を実施するための形態】
【００１０】
《原理》
本発明の時限暗号は関数型暗号を利用して実現される。そこでまず関数型暗号について説明する。
【００１１】
＜関数型暗号＞
近年、関数型暗号と呼ばれるＩＤベース暗号の拡張暗号が開発されている。関数型暗号とＩＤベース暗号には構文の違いは全く無い。即ち、関数型暗号も下記の４つのアルゴリズム(Setup,KeyGen,Enc,Dec)から構成される。プロトコルの概略は下記のとおりである。
《プロトコルFE》
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
・Setup(1λ)→(pk,sk)：セットアップアルゴリズム
セキュリティパラメータ1λを入力とし、公開パラメータpkとマスター秘密鍵skを出力する確率的多項式時間アルゴリズム
・KeyGen(sk,i)→ski：鍵生成アルゴリズム
マスター秘密鍵skと鍵識別子iを入力とし、当該鍵識別子iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム
・Enc(pk,j,x)→cj：暗号化アルゴリズム
公開パラメータpkと受信者識別子jと暗号化対象の情報（平文）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム
・Dec(pk,ski,cj)→y：復号アルゴリズム
公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、平文yを出力する確率的多項式時間アルゴリズム
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００１２】
関数型暗号では、ＩＤベース暗号の正当性が拡張されており、暗号文の受信者は鍵識別子iを持つ秘密鍵と受信者識別子jを持つ暗号文から平文xに関する何らかの関数fi,j(x)を評価することができるようになっている。即ち、或る関数fi,j(x)が存在し∀i∈{0,1}poly(λ)，∀j∈{0,1}poly(λ)，∀x∈{0,1}poly(λ)に対して式（１）で表される確率Prがλに関して圧倒的（１との差が無視しうる）であるとき、その関数型暗号(Setup,KeyGen,Enc,Dec)は正当であると云う。なお、poly(λ)はλで決まる多項式長を表している。
【数１】
0005755557.tif 000002
【００１３】
特に、或る関係Ｒ(・,・)が存在し、式（２）で表されるタイプの関数fi,j(x)を持つ関数型暗号は様々な暗号を包含している（⊥は正常に復号できなかったことを表す記号である）。
【数２】
0005755557.tif 000003
【００１４】
例えばＩＤベース暗号は式（３）で表される関数fi,j(x)を持つ関数型暗号と定義することができる。
【数３】
0005755557.tif 000004
【００１５】
より高度な関係Ｒ(・,・)を持つ様々な関数型暗号が研究されている。このタイプの関数型暗号のうち最も汎用性の高いものは属性ベース暗号(attribute-based encryption, ABE)あるいは述語暗号(predicate encryption, PE)等と呼ばれ、よく研究されている。2010年に岡本龍明らは多項式サイズの述語および述語変数の集合に対応し、標準的な暗号学的仮定の下で適応的識別子攻撃に対してＣＣＡ安全が証明できる比較的実用的なこのタイプの関数型暗号を提案した（参考文献１参照）。
（参考文献１）Tatsuaki Okamoto and Katsuyuki Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," International Cryptology Conference CRYPTO, pp.191-208, November 2010.
【００１６】
鍵識別子iを述語、受信者識別子jを述語変数のインスタンスとして式（４）で表される関係Ｒ(・,・)を持つ関数型暗号は鍵ポリシー関数型暗号(key-policy functional encryption, KP-FE)と呼ばれる。
【数４】
0005755557.tif 000005
【００１７】
鍵識別子iを述語変数、受信者識別子jを述語のインスタンスとして式（５）で表される関係Ｒ(・,・)を持つ関数型暗号は暗号文ポリシー関数型暗号(ciphertext-policy functional encryption, CP-FE)と呼ばれる。
【数５】
0005755557.tif 000006
【００１８】
鍵識別子iaと受信者識別子jaを述語変数、鍵識別子ipと受信者識別子jpを述語のインスタンスとし、i=ia‖ip，j=ja‖jpとして、式（６）で表される関係Ｒ(・,・)を持つ関数型暗号は統合ポリシー関数型暗号(unified-policy functional encryption, UP-FE)と呼ばれる（参考文献２参照）。記号‖は、識別子同士の結合（例えば、バイナリ表現された識別子同士のバイナリ結合）を表す。
（参考文献２）Nuttapong Attrapadung and Hideki Imai, "Dual-Policy Attribute Based Encryption," ACNS 2009, LNCS 5536, pp.168-185, 2009.
【数６】
0005755557.tif 000007
【００１９】
＜関数型暗号を用いた時限暗号＞
ＩＤベース暗号と関数型暗号の構文（アルゴリズムの入出力インターフェイス）は完全に一致している。従って、同じような安全性を持つならば時限暗号に関してＩＤベース暗号の代わりに関数型暗号を利用できる。
【００２０】
xを平文、tを予め設定された時的制限情報（復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報である。以下、時的制限情報を特に断りのない限り復号可能限界時刻と呼ぶことにする）、t'を暗号文に設定された暗号化時刻（通常、暗号化アルゴリズムを実行する時の時刻とされる。以下、暗号化時刻を特に断りのない限り暗号文生成時刻と呼ぶことにする）として、式（７）で表される関数ft,t'(x)を持つ関数型暗号を利用できるならば、暗号化時刻t'が時的制限情報tを満たさない場合、暗号文の復号に失敗することになる。なお、時的制限情報tを決定するイニシアティブは、通常、鍵発行装置または受信者装置を利用する者にあり、暗号化時刻t'を決定するイニシアティブは、通常、送信者装置を利用する者にある。時的制限情報tを決定するイニシアティブが受信者装置を利用する者にある場合、事前に、時的制限情報tを表す情報が受信者装置から鍵発行装置に伝達されているとする。
【数７】
0005755557.tif 000008
【００２１】
時的制限情報tが時刻を表す場合を考える。式（７）で表される関数ft,t'(x)によると、復号可能限界時刻tが暗号文生成時刻t'より小さい場合（つまり、暗号文生成時刻t'が復号可能限界時刻tより遅い時）、復号時に⊥が出力され、復号可能限界時刻tが暗号文生成時刻t'以上の場合（つまり、暗号文生成時刻t'が復号可能限界時刻tより遅くない時）、復号時に平文xが出力される。t≧t'あるいはその否定であるt＜t'は関係Ｒによって表現できるところ、このような関数型暗号を属性ベース暗号に基づいて構成する方法は３通り存在する。
【００２２】
（１）鍵ポリシー関数型暗号を用いる方法：この場合、鍵発行装置は、tを復号可能限界時刻、t'を述語変数として、t≧t'なる述語（鍵識別子i）に関して秘密鍵sktを生成する。送信者装置は、暗号文生成時刻t'を属性に持つ暗号文ct'を生成し、当該暗号文ct'を受信者装置に送信する。
【００２３】
（２）暗号文ポリシー関数型暗号を用いる方法：この場合、鍵発行装置は、復号可能限界時刻tを属性に持つ秘密鍵sktを生成する。送信者装置は、tを述語変数、t'を暗号文生成時刻として、t≧t'なる述語(受信者識別子j)に関して暗号文ct'を生成し、当該暗号文ct'を受信者装置に送信する。
【００２４】
（３）統合ポリシー関数型暗号を用いる方法：この場合、鍵発行装置は、iaを受信者の属性（「受信者の属性」として、受信者装置の属性や受信者装置を利用するユーザの属性などが挙げられ、特に限定は無い）、tを復号可能限界時刻、t'を述語変数として、t≧t'なる述語ipと受信者の属性iaに関して秘密鍵skia‖(t≧t')を生成する。送信者装置は、jaを暗号文生成時刻t'、jpを復号のための条件（以下、必要条件という）のうちの一つを表す述語として、述語jpと暗号文生成時刻t'に関して暗号文ct'‖jpを生成し、当該暗号文ct'‖jpを受信者装置に送信する。このタイプの関数型暗号に拠ると、必要条件は「述語ip」と「述語jp」の二つであり、具体的には、受信者装置は「t≧t'（受信者識別子ja=暗号文生成時刻t'が、述語ip=“t≧t'”を満たす）」且つ「鍵識別子ia=受信者の属性iaが、述語jpを満たす」場合に暗号文ct'‖jpを復号できる。必要条件を構成する述語jpは任意に定められる。
【００２５】
いずれの場合であっても秘密鍵sktおよび暗号文ct'を持つ受信者装置はt≧t'なる時に暗号文ct'を復号できる。
【００２６】
例えば、述語変数（復号可能限界時刻が代入される）と暗号文生成時刻をビット表現された整数と見做せば、復号可能限界時刻と暗号文生成時刻との大小判定を、述語変数を用いた述語として表現できる。従って、述語の充足によって復号可能か否かが決まる関数型暗号があれば、ビット表現された整数の大小判定の結果によって復号可能か否かが決定される関数型暗号を構成することができる。例えば、図４と図５に示すように比較する定数のビットイメージに対応して論理積andや論理和orで述語変数を合成することによって述語を決定できる。図４では整数変数tと定数t'との間におけるt＞t'の関係を記述する述語を示してある。なお、t≦t'の関係を記述する述語は、t＞t'の関係を記述する述語の否定（¬(t＞t')）によって表される。図５では整数変数tと定数t'との間におけるt≧t'の関係を記述する述語を示してある。なお、t＜t'の関係を記述する述語は、t≧t'の関係を記述する述語の否定（¬(t≧t')）によって表される。
【００２７】
《実施形態》
［時限暗号システム］
実施形態の時限暗号システム１は、図１に示すように、鍵発行装置１００と、送信者装置２００と、受信者装置３００とを少なくとも含んで構成される。これらの各装置は、例えばインターネットなどの通信網５を経由して、相互に通信可能とされている。
【００２８】
本発明の時限暗号システムは、ユーザの数に応じて一つまたは複数の送信者装置２００と一つまたは複数の受信者装置３００を含みえるが、本発明の理解を容易にするため、後述の実施形態では、時限暗号システム１は、１個の鍵発行装置１００と１個の送信者装置２００と１個の受信者装置３００を含むとする。
【００２９】
時限暗号システム１における時限暗号処理を、図２を参照しながら叙述する。各装置の機能構成については、図３を参照されたい。
【００３０】
[[実施例１]]
復号可能限界時刻tを鍵識別子、暗号文生成時刻t'を受信者識別子として、上記式（７）で表される関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)を利用する。プロトコルの概略は下記のとおりである。なお、このような関数型暗号であれば何ら限定はないので、ここでは一般的な説明をするに留めるが、実用の局面ではSetup,KeyGen,Enc,Decの各アルゴリズムが具体的に決まっているから、当然、当該各アルゴリズムを実行することになる。
《プロトコルTRC-FE》
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
・鍵発行装置は、《プロトコルFE》で説明したセットアップアルゴリズムSetup(1λ)を実行して公開パラメータpkとマスター秘密鍵skを生成し、公開パラメータpkを公開する。
・鍵発行装置は、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t)を実行して秘密鍵sktを生成する。ただし、tは予め設定された復号可能限界時刻である。
・送信者装置は、暗号文生成時刻をt'、平文をxとして、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,t',x)を実行して暗号文ct'を生成し、暗号文ct'を受信者装置に送信する。
・受信者装置は、鍵発行装置から秘密鍵sktを取得して、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,ct')を実行して、t≧t'を満たす場合に平文xを得る。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００３１】
まず、鍵発行装置１００の初期設定部１０１が、《プロトコルFE》で説明したセットアップアルゴリズムSetup(1λ)を実行して公開パラメータpkとマスター秘密鍵skを生成し（ステップＳ１）、公開パラメータpkを公開する（ステップＳ１ａ）。公開パラメータpkの公開は、例えば、送信者装置２００や受信者装置３００から鍵発行装置１００にアクセスがあった場合に鍵発行装置１００の送信部１０８が鍵発行装置１００の記憶部（図示せず）に記憶されている公開パラメータpkを送信者装置２００や受信者装置３００に対して送信する手順や、送信者装置２００や受信者装置３００からのアクセスを問わず、鍵発行装置１００の送信部１０８が鍵発行装置１００の記憶部（図示せず）に記憶されている公開パラメータpkを送信者装置２００や受信者装置３００に対して送信する手順によって達成される。
【００３２】
そして、鍵発行装置１００の秘密鍵生成部１０２は、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t)を実行して秘密鍵sktを生成する（ステップＳ２）。ただし、tは予め設定された復号可能限界時刻である。
【００３３】
鍵発行装置１００の送信部１０８は、秘密鍵生成部１０２によって生成された秘密鍵sktを受信者装置３００に送信し、受信者装置３００の受信部３０９が秘密鍵sktを受信する（ステップＳ３）。秘密鍵sktは受信者装置３００の記憶部（図示せず）に記憶される。なお、ステップＳ３の処理は、ステップＳ２の処理の後であって後述するステップＳ６の処理の前であれば何時でも実行されてよい。
【００３４】
送信者装置２００の暗号文生成部２０１は、暗号文生成時刻をt'、平文をxとして、送信者装置２００の受信部２０９が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,t',x)を実行して暗号文ct'を生成する（ステップＳ４）。
【００３５】
送信者装置２００は事実上、暗号文生成時刻t'を自由に設定しえる（例えば、暗号文生成時刻t'を送信者装置２００の内部時計から取得した時刻とする場合、当該内部時計が正しく設定されていない状況が想定されうる）。しかし、暗号文生成時刻t'は復号可能限界時刻tとの関係で重要な情報であるから、暗号文生成部２０１は、送信者装置２００の外部から供給される協定世界時（UTC - Universal Time, Coordinated）や日本標準時（JST - Japan Standard Time）などに基づく現在時刻に従って暗号文生成時刻t'を設定することが好ましい。具体的には、暗号文生成部２０１は、「暗号化アルゴリズムを実行する時の協定世界時や日本標準時などに基づく現在時刻」を暗号文生成時刻t'として設定するのである。協定世界時や日本標準時を利用する場合、送信者装置２００は協定世界時や日本標準時を受信できる構成としておくことが望ましい。なお、このことは、他の実施例でも同様である。
【００３６】
なお、送信者装置２００の内部時計から取得した時刻を暗号文生成時刻t'とする場合、少なくとも送信者装置２００と復号可能限界時刻tの決定に関与する装置（この場合、鍵発行装置１００または受信者装置３００）との間で可能な限り（つまり、例えば数秒程度の誤差を許容するとしても）相互の時計を同期させておくことが望ましい。同期方法としては、例えば、復号可能限界時刻tの決定に関与する装置（鍵発行装置１００または受信者装置３００）が通信網５を経由して送信者装置２００に、当該装置（鍵発行装置１００または受信者装置３００）の内部時計の時刻を常時提供するようにすればよい。厳密には、当該装置（鍵発行装置１００または受信者装置３００）の内部時計と復号可能限界時刻tとの間に直接の関連は無い。しかし、復号可能限界時刻tが当該装置（鍵発行装置１００または受信者装置３００）の内部時計を参考にして決定される場合があるから、当該装置（鍵発行装置１００または受信者装置３００）と送信者装置２００との間で相互の時計を同期させておくことに意味が無いわけではない。
【００３７】
送信者装置２００の送信部２０８は、暗号文生成部２０１によって生成された暗号文ct'を受信者装置３００に対して送信し、受信者装置３００の受信部３０９が暗号文ct'を受信する（ステップＳ５）。暗号文ct'は受信者装置３００の記憶部（図示せず）に記憶される。
【００３８】
受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skt、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,ct')を実行する（ステップＳ６）。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,ct')にて、関係Ｒ（ここではt≧t'である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係Ｒが真となる場合、つまりt≧t'を満たす場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまりt≧t'を満たさない場合に復号部３０１は平文xを得ることができない。
【００３９】
[[実施例２]]
実施例２は、実施例１における関数型暗号(Setup,KeyGen,Enc,Dec)として鍵ポリシー関数型暗号による場合の実施例である。実施例１を鍵ポリシー関数型暗号として具体化した事項について説明を加え、実施例１と同じ事項は説明を省略する。
【００４０】
実施例２では、実施例１のステップＳ２の処理にて、次のような処理を行う。鍵発行装置１００の秘密鍵生成部１０２が、tを復号可能限界時刻、Tを述語変数として、t≧Tなる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t≧T)を実行して秘密鍵skt≧Tを生成する。
【００４１】
実施例２では、実施例１のステップＳ３の処理にて、次のような処理を行う。鍵発行装置１００の送信部１０８は、秘密鍵生成部１０２によって生成された秘密鍵skt≧Tを受信者装置３００に送信し、受信者装置３００の受信部３０９が秘密鍵skt≧Tを受信する（ステップＳ３）。秘密鍵skt≧Tは受信者装置３００の記憶部（図示せず）に記憶される。
【００４２】
実施例２では、実施例１のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skt≧T、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt≧T,ct')を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt≧T,ct')にて、式（４）で表される関係Ｒ（ここではＲ(t≧T，T=t')である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまりt≧t'を満たす場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまりt≧t'を満たさない場合に復号部３０１は平文xを得ることができない。
【００４３】
[[実施例３]]
実施例３は、実施例１における関数型暗号(Setup,KeyGen,Enc,Dec)として暗号文ポリシー関数型暗号による場合の実施例である。実施例１を暗号文ポリシー関数型暗号として具体化した事項について説明を加え、実施例１と同じ事項は説明を省略する。
【００４４】
実施例３では、実施例１のステップＳ４の処理にて、次のような処理を行う。送信者装置２００の暗号文生成部２０１は、述語変数をT、暗号文生成時刻をt'、平文をxとして、T≧t'なる述語に関して、送信者装置２００の受信部２０９が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,T≧t',x)を実行して暗号文cT≧t'を生成する。
【００４５】
実施例３では、実施例１のステップＳ５の処理にて、次のような処理を行う。送信者装置２００の送信部２０８は、暗号文生成部２０１によって生成された暗号文cT≧t'を受信者装置３００に対して送信し、受信者装置３００の受信部３０９が暗号文cT≧t'を受信する（ステップＳ５）。暗号文cT≧t'は受信者装置３００の記憶部（図示せず）に記憶される。
【００４６】
実施例３では、実施例１のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skt、公開パラメータpk、暗号文cT≧t'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,cT≧t')を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,cT≧t')にて、式（５）で表される関係Ｒ（ここではＲ(T≧t'，T=t)である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまりt≧t'を満たす場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまりt≧t'を満たさない場合に復号部３０１は平文xを得ることができない。
【００４７】
[[実施例４]]
実施例４は、実施例１における関数型暗号(Setup,KeyGen,Enc,Dec)として統合ポリシー関数型暗号による場合の実施例である。実施例１を統合ポリシー関数型暗号として具体化した事項について説明を加え、実施例１と同じ事項は説明を省略する。
【００４８】
実施例４では、実施例１のステップＳ２の処理にて、次のような処理を行う。鍵発行装置１００の秘密鍵生成部１０２が、iaを受信者の属性（例えば受信者装置３００の属性）、tを復号可能限界時刻、Tを述語変数として、t≧Tなる述語ipと受信者の属性iaとの結合に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,ia‖(t≧T))を実行して秘密鍵skia‖(t≧T)を生成する。
【００４９】
実施例４では、実施例１のステップＳ３の処理にて、次のような処理を行う。鍵発行装置１００の送信部１０８は、秘密鍵生成部１０２によって生成された秘密鍵skia‖(t≧T)を受信者装置３００に送信し、受信者装置３００の受信部３０９が秘密鍵skia‖(t≧T)を受信する（ステップＳ３）。秘密鍵skia‖(t≧T)は受信者装置３００の記憶部（図示せず）に記憶される。
【００５０】
実施例４では、実施例１のステップＳ４の処理にて、次のような処理を行う。送信者装置２００の暗号文生成部２０１は、暗号文生成時刻をt'、必要条件のうちの一つを表す述語をjp、平文をxとして、述語jpと暗号文生成時刻t'との結合に関して、送信者装置２００の受信部２０９が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,t'‖jp,x)を実行して暗号文ct'‖jpを生成する。
【００５１】
実施例４では、実施例１のステップＳ５の処理にて、次のような処理を行う。送信者装置２００の送信部２０８は、暗号文生成部２０１によって生成された暗号文ct'‖jpを受信者装置３００に対して送信し、受信者装置３００の受信部３０９が暗号文ct'‖jpを受信する（ステップＳ５）。暗号文ct'‖jpは受信者装置３００の記憶部（図示せず）に記憶される。
【００５２】
実施例４では、実施例１のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skia‖(t≧T)、公開パラメータpk、暗号文ct'‖jpを用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skia‖(t≧T),ct'‖jp)を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skia‖(t≧T),ct'‖jp)にて、式（６）で表される関係Ｒ（ここではＲ(t≧T，T=t')∧Ｒ(ia，jp)である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまり「t≧t'」且つ「受信者の属性iaが述語jpを満たす」場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまり「t≧t'」且つ「受信者の属性iaが述語jpを満たす」が成立しない場合に復号部３０１は平文xを得ることができない。
【００５３】
[[実施例５]]
実施例５は、実施例２の変形例である。実施例２では、鍵発行装置１００の秘密鍵生成部１０２が、tを復号可能限界時刻、Tを述語変数として、t≧Tなる述語に関して鍵生成アルゴリズムKeyGen(sk,t≧T)を実行して秘密鍵skt≧Tを生成していた。実施例５は、述語が拡張された例である。
【００５４】
実施例５では、t≧Tなる述語ではなく、時的制限情報tとしての任意の有限個の時間区間[bi,ei]（i=1,2,…,n）と暗号化時刻t'が代入されうる述語変数Tとで構成される論理和∨(t,T)=∨i∈{1,2,…,n}(bi≦T≦ei)=(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)を述語とする。なお、n個の時間区間[bi,ei]（i=1,2,…,n）のうち少なくともいずれかにおいてbi=eiであってもよい。
【００５５】
従って、実施例５では、実施例２のステップＳ２の処理にて、次のような処理を行う。鍵発行装置１００の秘密鍵生成部１０２が、時的制限情報tを任意の有限個の時間区間[bi,ei]（i=1,2,…,n）、Tを暗号化時刻t'が代入されうる述語変数として、∨i∈{1,2,…,n}(bi≦T≦ei)なる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,∨i∈{1,2,…,n}(bi≦T≦ei))を実行して秘密鍵skt,Tを生成する。
【００５６】
そして、実施例５では、実施例２のステップＳ３の処理にて、次のような処理を行う。鍵発行装置１００の送信部１０８は、秘密鍵生成部１０２によって生成された秘密鍵skt,Tを受信者装置３００に送信し、受信者装置３００の受信部３０９が秘密鍵skt,Tを受信する（ステップＳ３）。秘密鍵skt,Tは受信者装置３００の記憶部（図示せず）に記憶される。
【００５７】
さらに、実施例５では、実施例２のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skt,T、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,T,ct')を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,T,ct')にて、式（４）で表される関係Ｒ（ここではＲ(∨i∈{1,2,…,n}(bi≦T≦ei)，T=t')である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまりt≧t'を満たす場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまりt≧t'を満たさない場合に復号部３０１は平文xを得ることができない。
【００５８】
[[実施例６]]
実施例６は、実施例３の変形例である。実施例３では、送信者装置２００の暗号文生成部２０１が、述語変数をT、暗号文生成時刻をt'、平文をxとして、T≧t'なる述語に関して暗号化アルゴリズムEnc(pk,T≧t',x)を実行して暗号文cT≧t'を生成していた。実施例６は、述語が拡張された例である。
【００５９】
実施例６では、T≧t'なる述語ではなく、暗号化時刻t'と任意の有限個の時間区間[bi,ei]（i=1,2,…,n）で表される時的制限情報tが代入されうる述語変数Tとで構成される論理和∨(T,t')=∨i∈{1,2,…,n}(bi≦t'≦ei)=(b1≦t'≦e1)∨(b2≦t'≦e2)∨・・・∨(bn≦t'≦en)を述語とする。なお、n個の時間区間[bi,ei]（i=1,2,…,n）のうち少なくともいずれかにおいてbi=eiであってもよい。
【００６０】
従って、実施例６では、実施例３のステップＳ４の処理にて、次のような処理を行う。送信者装置２００の暗号文生成部２０１は、Tを任意の有限個の時間区間[bi,ei]（i=1,2,…,n）で表される時的制限情報tが代入されうる述語変数、t'を暗号化時刻、平文をxとして、∨(T,t')=∨i∈{1,2,…,n}(bi≦t'≦ei)=(b1≦t'≦e1)∨(b2≦t'≦e2)∨・・・∨(bn≦t'≦en)なる述語に関して、送信者装置２００の受信部２０９が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,∨(T,t'),x)を実行して暗号文cT,t'を生成する。
【００６１】
実施例６では、実施例３のステップＳ５の処理にて、次のような処理を行う。送信者装置２００の送信部２０８は、暗号文生成部２０１によって生成された暗号文cT,t'を受信者装置３００に対して送信し、受信者装置３００の受信部３０９が暗号文cT,t'を受信する。暗号文cT,t'は受信者装置３００の記憶部（図示せず）に記憶される。
【００６２】
実施例６では、実施例３のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵skt、公開パラメータpk、暗号文cT,t'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,cT,t')を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,cT,t')にて、式（５）で表される関係Ｒ（ここではＲ(∨(T,t')，T=t)である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまりt≧t'を満たす場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまりt≧t'を満たさない場合に復号部３０１は平文xを得ることができない。
【００６３】
[[実施例７]]
実施例７は、実施例４の変形例である。実施例４では、鍵発行装置１００の秘密鍵生成部１０２が、iaを受信者の属性（例えば受信者装置３００の属性）、tを復号可能限界時刻、Tを述語変数として、t≧Tなる述語ipと受信者の属性iaとの結合に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,ia‖(t≧T))を実行して秘密鍵skia‖(t≧T)を生成していた。実施例７は、述語が拡張された例である。
【００６４】
実施例７では、t≧Tなる述語ではなく、時的制限情報tとしての任意の有限個の時間区間[bi,ei]（i=1,2,…,n）と暗号化時刻t'が代入されうる述語変数Tとで構成される論理和∨(t,T)=∨i∈{1,2,…,n}(bi≦T≦ei)=(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)を述語とする。なお、n個の時間区間[bi,ei]（i=1,2,…,n）のうち少なくともいずれかにおいてbi=eiであってもよい。
【００６５】
従って、実施例７では、実施例４のステップＳ２の処理にて、次のような処理を行う。鍵発行装置１００の秘密鍵生成部１０２が、iaを受信者の属性（例えば受信者装置３００の属性）、時的制限情報tを任意の有限個の時間区間[bi,ei]（i=1,2,…,n）、Tを暗号化時刻t'が代入されうる述語変数として、∨i∈{1,2,…,n}(bi≦T≦ei)なる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,ia‖∨i∈{1,2,…,n}(bi≦T≦ei))を実行して秘密鍵sk1を生成する。
【００６６】
そして、実施例７では、実施例４のステップＳ３の処理にて、次のような処理を行う。鍵発行装置１００の送信部１０８は、秘密鍵生成部１０２によって生成された秘密鍵sk1を受信者装置３００に送信し、受信者装置３００の受信部３０９が秘密鍵sk1を受信する。秘密鍵sk1は受信者装置３００の記憶部（図示せず）に記憶される。
【００６７】
さらに、実施例７では、実施例４のステップＳ６の処理にて、次のような処理を行う。受信者装置３００の復号部３０１は、受信者装置３００の受信部３０９が受信した秘密鍵sk1、公開パラメータpk、暗号文ct'‖jpを用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,sk1,ct'‖jp)を実行する。上記式（７）で表されるタイプの関数ft,t'(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,sk1,ct'‖jp)にて、式（６）で表される関係Ｒ（ここではＲ(∨i∈{1,2,…,n}(bi≦T≦ei)，T=t')∧Ｒ(ia，jp)である）の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(x)の出力が決せられる暗号構造が組み込まれており、当該関係ＲがTrueとなる場合、つまり「t≧t'」且つ「受信者の属性iaが述語jpを満たす」場合に復号部３０１は平文xを得ることができる。他方、当該関係Ｒが偽となる場合、つまり「t≧t'」且つ「受信者の属性iaが述語jpを満たす」が成立しない場合に復号部３０１は平文xを得ることができない。
【００６８】
実施例５，６，７は、例えば次のような事例において有用である。例えば、送信者装置２００を扱うユーザの意図として、受信者装置３００に時間区間[b1,e1]または[b2,e2]（ただし、b1≦e1＜b2≦e2≦tとする）のみで復号可能とさせたいという意図がある場合に、実施例２，３，４によると、受信者装置３００は、時的制限情報tで特定される復号に関する時的制限内であれば、ユーザが意図しない時間区間[e1,b2]に秘密鍵を用いて正しく復号するということができてしまう。しかしながら、実施例５，６，７によると、述語が時的制限情報tとして任意の有限個の時間区間[bi,ei]（i=1,2,…,n）を用いて記述されていることから、送信者装置２００を扱うユーザが意図した時間帯のみで復号可能とすることができる。
【００６９】
関数型暗号の実装については、例えば、下記特許文献が参考になる。
特開2011-232475号公報
特開2011-141472号公報
特開2011-128609号公報
特開2010-273317号公報
特開2010-054875号公報
【００７０】
＜補記＞
時限暗号システムに含まれるハードウェアエンティティ（鍵発行装置、送信者装置、受信者装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００７１】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【００７２】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、初期設定部、秘密鍵生成部、暗号文生成部、復号部など）を実現する。
【００７３】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成23年12月12日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/やhttp://www.math.tu-berlin.de/~kant/kash.html〉［平成23年12月12日検索］を参照のこと。）。
また、この点に関する文献として、参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００７４】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７５】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００７６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005755557.tif 000009
【図２】
0005755557.tif 000010
【図３】
0005755557.tif 000011
【図４】
0005755557.tif 000012
【図５】
0005755557.tif 000013