(57)【要約】【課題】  タイムサーバの計算量が暗号文受信者の数に依存しない暗号化復号化を行うこと。【解決手段】  タイム装置は、エクストラクト・アルゴリズムを、現在時刻をビット列として表現したもので、上から数ビット連結してできるビット列で構成された複数のＩＤに対して施し、前記複数のＩＤに対して前記アルゴリズムを実施して得られた複数の復号化鍵を出力する。暗号化装置は、指定時刻データをビット列として表現したもので、上から数ビット連結してできるビット列で構成される複数のＩＤを指定し、前記タイム装置から出力された暗号鍵及び前記複数のＩＤを読み込んで同一平文を暗号化して複数の暗号文を出力する。復号化手段は、入力された複数の復号化鍵から一つの復号化鍵を選択し、前記入力された複数の暗号文から一つの暗号文を選択し、選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化する。【選択図】    図１
2007036364.tif 000002
【特許請求の範囲】
【請求項１】
ＩＤベース暗号方式のセットアップを行うセットアップ手段と、ＩＤベース暗号方式のエクストラクト・アルゴリズムを複数のＩＤに対して施す復号化鍵計算手段と、出力手段とを有するタイム装置において、
前記複数のＩＤは、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成され、
前記出力手段は、指定された前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力することを特徴とするタイム装置。
【請求項２】
前記セットアップ手段は、ランダムに有限群の元を選択し、ランダムにマスター鍵を選択し、前記元を底とし前記マスター鍵を指数とするべき乗剰余を計算し、前記元と前記べき乗剰余の計算結果との組である暗号鍵を出力し、
前記復号化鍵計算手段は、
前記複数のＩＤをセットするタイム装置用鍵選択手段と、
前記入力された現在時刻にあらかじめ配布された有限群の元を対応させ、当該元を底とし、マスター鍵を指数とするべき乗剰余を計算し、複数の復号化鍵を生成するＩＢＥエクストラクト手段とを有することを特徴とする請求項１記載のタイム装置。
【請求項３】
ｉを１にセットし、対数上限値τが１以上でない場合に現在時刻と復号鍵との対を出力する連結手段を有することを特徴とする請求項２記載のタイム装置。
【請求項４】
暗号文を復号する事が可能になる時刻である指定時刻データが入力される入力手段と、
前記入力された指定時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定する前記鍵選択手段と、
前記複数のＩＤを使って同一平文を複数回暗号化する暗号化手段と、
前記暗号化手段の計算結果である複数の暗号文を出力する出力手段を
有することを特徴とする暗号化装置。
【請求項５】
前記暗号化手段は、前記ＩＤに有限群の元を対応させた上で、任意の乱数を選択し、前記元と公開鍵の一成分とのペアリングを前記乱数のべき乗計算をして、その計算結果に平分を乗じた第１の計算結果を得、前記公開鍵の一成分を前記乱数のべき乗計算をして第２の計算結果を得、前記第１の計算結果と前記第２の計算結果とからなる組を暗号文としてセットすることを特徴とする請求項４記載の暗号化装置。
【請求項６】
複数の暗号文と指定時刻と複数の復号化鍵と復号化鍵の生成時刻とが入力される受信手段と、
前記入力された複数の復号化鍵から一つの復号化鍵を選択する鍵選択手段と、
前記入力された複数の暗号文から一つの暗号文を選択する暗号文選択手段と、
選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化する復号手段とを有し、
前記鍵選択手段は第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択し、
前記暗号文選択手段は前記選択された第１のビット列に対応する暗号文を選択し、
前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列である
ことを特徴とする復号化装置。
【請求項７】
前記復号手段は、前記選択された暗号文を第１及び第２の成分に分け、前記いずれかの成分と有限群の元とのペアリングを計算し、前記他方の成分を、前記計算結果で除することを特徴とする請求項６記載の復号化装置。
【請求項８】
ＩＤベース暗号方式のセットアップを行うステップと、
ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数ＩＤに対して施すステップと、
指定した前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するステップを
を有することを特徴とする復号化鍵生成方法。
【請求項９】
前記セットアップを行うステップは、ランダムに有限群の元を選択し、ランダムにマスター鍵を選択し、前記元を底とし前記マスター鍵を指数とするべき乗剰余を計算し、前記元と前記べき乗剰余の計算結果との組である暗号鍵を出力するステップを有し、
前記エクストラクト・アルゴリズムを行うステップは、前記複数のＩＤをセットするステップと、前記入力された現在時刻にあらかじめ配布された有限群の元を対応させ、当該元を底とし、マスター鍵を指数とするべき乗剰余を計算し、複数の復号化鍵を生成するステップを有する
ことを特徴とする請求項８記載の復号化鍵生成方法。
【請求項１０】
ｉを１にセットし、対数上限値τが１以上でない場合に現在時刻と復号鍵との対を出力するステップを有することを特徴とする請求項９記載の復号化鍵生成方法。
【請求項１１】
暗号文を復号する事が可能になる時刻である指定時刻データを入力するステップと、
前記入力された指定時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定するステップと、
前記複数のＩＤを使って同一平文を複数回暗号化するステップと、
前記暗号化手段の計算結果である複数の暗号文を出力するステップを
有することを特徴とする暗号化方法。
【請求項１２】
前記暗号化するステップは、
前記ＩＤに有限群の元を対応させた上で、任意の乱数を選択し、前記元と公開鍵の一成分とのペアリングを前記乱数のべき乗計算をして、その計算結果に平分を乗じて第１の計算結果を得るステップと、
前記公開鍵の一成分を前記乱数のべき乗計算をして第２の計算結果を得るステップと、
前記第１の計算結果と前記第２の計算結果とからなる組を暗号文としてセットするステップを有することを特徴とする請求項１１記載の暗号化方法。
【請求項１３】
複数の暗号文と指定時刻と複数の復号化鍵と復号化鍵の生成時刻を入力するステップと、
前記入力された複数の復号化鍵から一つの復号化鍵を選択するステップと、
前記入力された複数の暗号文から一つの暗号文を選択するステップと、
選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化するステップとを有し、
前記鍵選択ステップは、第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択するステップを有し、
前記暗号文選択ステップは前記選択された第１のビット列に対応する暗号文を選択するステップを有し、
前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列である
ことを特徴とする復号化方法。
【請求項１４】
前記選択された暗号文を第１及び第２の成分に分け、前記いずれかの成分と有限群の元とのペアリングを計算し、前記他方の成分を、前記計算結果で除するステップを有することを特徴とする請求項１３記載の復号化方法。
【請求項１５】
コンピュータに、
ＩＤベース暗号方式のセットアップを行うステップと、
ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数ＩＤに対して施すステップと、
指定した前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するステップを
を実行させることを特徴とするプログラム。
【請求項１６】
コンピュータに、
暗号文を復号する事が可能になる時刻である指定時刻データを入力するステップと、
前記入力された指定時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定するステップと、
前記複数のＩＤを使って同一平文を複数回暗号化するステップと、
前記暗号化手段の計算結果である複数の暗号文を出力するステップを
を実行させることを特徴とするプログラム。
【請求項１７】
コンピュータに、
複数の暗号文と指定時刻と複数の復号化鍵と復号化鍵の生成時刻を入力するステップと、
前記入力された複数の復号化鍵から一つの復号化鍵を選択するステップと、
前記入力された複数の暗号文から一つの暗号文を選択するステップと、
選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化するステップとを実行させるプログラムであって、
前記鍵選択ステップは、前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列である第２のビット列に１をつなげてなる第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択するステップを有し、前記暗号文選択ステップは前記選択された第１のビット列に対応する暗号文を選択するステップを有することを特徴とするプログラム。
【請求項１８】
請求項１５〜１７のいずれかに記載のプログラムを記録したことを特徴とするコンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）。
【請求項１９】
ＩＤベース暗号方式のセットアップを行い、ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成された複数のＩＤに対して施し、指定された前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するタイム装置と、
暗号文を復号する事が可能になる時刻である指定時刻データをビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定し、前記タイム装置から出力されたシステムパラメータとしての暗号鍵及び前記複数のＩＤを読み込んで同一平文を複数回暗号化し、複数の暗号文を出力する暗号化装置と、
前記暗号化装置から出力された複数の暗号文及び指定時刻と、前記タイム装置から出力された複数の復号化鍵及び復号化鍵の生成時刻とを入力し、前記入力された複数の復号化鍵から一つの復号化鍵を選択し、前記入力された複数の暗号文から一つの暗号文を選択し、選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化する復号手段とを有する
ことを特徴とする暗号化／復号化システム。
【請求項２０】
前記選択された復号鍵は、第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵であり、
前記選択された暗号文は、前記選択された第１のビット列に対応する暗号文であり、
前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であることを特徴とする請求項１９記載の暗号化／復号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間開放型暗号化／復号化に関し、とくにタイムサーバの計算量が暗号文受信者の数に依存しない暗号化復号化を行う事ができるタイム装置、暗号化装置、復号化装置、暗号化／復号化システム、方法、プログラム、情報記録媒体に関する。
【背景技術】
【０００２】
以下の非特許文献１から非特許文献６に開示されているように、時間開放型暗号方式は、暗号文を復号できる時刻を暗号文送信者が指定できる暗号方式である。暗号文送信者は復号時刻を定めて暗号文を作成し、受信者に送る。受信者は定められた時刻以前に暗号文を解く事はできない。しかし定められた時刻が来ると受信者は、暗号文送信者と通信することなく暗号文を復号する事ができる。この暗号方式を使えば秘密情報を開示する時刻をコントロールできるので、例えば電子投票や電子入札の開票や電子抽選の抽選結果発表といったものに応用できる。
【０００３】
【非特許文献１】Ian F. Blake, Vladimir Kolesnikov.  Strong Conditional Oblivious Transfer and Computing on Intervals.  In Advances in Cryptology - ASIACRYPT 2004, vol.3329 of LNCS, pp.515-529, Springer-Verlag, 2004.
【非特許文献２】D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003.
【非特許文献３】Dan Boneh, Xavier Boyen.  Secure Identity Based Encryption Without Random Oracles.  In Advances in Cryptology (CRYPTO 2004), vol. 3152 of LNCS, pp. 443-459, Springer, 2004.
【非特許文献４】Clifford Cocks.  An Identity Based Encryption Scheme Based on Quadratic ResiduesIn Proceedings of the 8th IMA International Conference on Cryptography and Coding. vol. 2260 of LNCS, pp. 360-363, Springer, 2001.
【非特許文献５】P. S. L. M. Barreto, H. Y. Kim, B. Lynn, M. Scott.  Efficient Algorithms for Pairing-Based Cryptosystems.  In Advances in Cryptology - Crypto'2002, Lecture Notes on Computer Science 2442, Springer-Verlag (2002), pp. 354-368.
【非特許文献６】Ronald L. Rivest, Adi Shamir, and David A. Wagner.Time-lock puzzles and timed-release Crypto.LCS technical memo MIT/LCS/TR-684. 1996.http://theory.lcs.mit.edu/~rivest/publications.html
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記非特許文献１で提案されている時間開放型暗号方式の場合、暗号文受信者は暗号文を復号する際タイムサーバと呼ばれる第三者機関と相互通信を行わねばならない。この為タイムサーバに付加が集中してしまい、タイムサーバは暗号文受信者の数に比例した量の計算を行わねばならない。効率の観点から言えば、タイムサーバの計算量が暗号文受信者の数に依存しない事が望ましい。
【０００５】
また、上記非特許文献６で提案されている時間開放型暗号方式の場合、暗号文受信者は指定時刻にタイムサーバが送信したデータを受信し損ねてはならない。受信し損ねると暗号文を復号できなくなってしまう。
【０００６】
もちろんタイムサーバがデータを送信し直せば復号が可能になるが、タイムサーバがデータを送信し直す方式だと、タイムサーバのデータ回数が増えてしまう為、やはりタイムサーバに負荷が集中する。
【０００７】
本発明は、タイムサーバの計算量が暗号文受信者の数に依存しない暗号化復号化を行う事を目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明は、以下の特徴を有する課題を解決するための手段を採用している。
【０００９】
第１の態様によれば、本発明に係るタイム装置は、ＩＤベース暗号方式のセットアップを行うセットアップ手段と、ＩＤベース暗号方式のエクストラクト・アルゴリズムを複数のＩＤに対して施す復号化鍵計算手段と、出力手段とを有し、
前記複数のＩＤは、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成され、
前記出力手段は、指定された前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力することを特徴とする。
【００１０】
第２の態様によれば、本発明に係る暗号化装置は、暗号文を復号する事が可能になる時刻である指定時刻データが入力される入力手段と、前記入力された指定時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定する前記鍵選択手段と、前記複数のＩＤを使って同一平文を複数回暗号化する暗号化手段と、前記暗号化手段の計算結果である複数の暗号文を出力する出力手段を有することを特徴とする。
【００１１】
第３の態様によれば、本発明に係る復号化装置は、複数の暗号文と指定時刻と複数の復号化鍵と復号化鍵の生成時刻とが入力される受信手段と、前記入力された複数の復号化鍵から一つの復号化鍵を選択する鍵選択手段と、前記入力された複数の暗号文から一つの暗号文を選択する暗号文選択手段と、選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化する復号手段とを有し、
前記鍵選択手段は第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択し、
前記暗号文選択手段は前記選択された第１のビット列に対応する暗号文を選択し、
前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であることを特徴とする。
【００１２】
第４の態様によれば、本発明に係る復号化鍵生成方法は、
ＩＤベース暗号方式のセットアップを行うステップと、
ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数ＩＤに対して施すステップと、
指定した前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するステップを有することを特徴とする。
【００１３】
第５の態様によれば、本発明に係る暗号化方法は、
暗号文を復号する事が可能になる時刻である指定時刻データを入力するステップと、
前記入力された指定時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定するステップと、
前記複数のＩＤを使って同一平文を複数回暗号化するステップと、
前記暗号化手段の計算結果である複数の暗号文を出力するステップを
有することを特徴とする。
【００１４】
第６の態様によれば、本発明に係る復号化方法は、
複数の暗号文と指定時刻と複数の復号化鍵と復号化鍵の生成時刻を入力するステップと、
前記入力された複数の復号化鍵から一つの復号化鍵を選択するステップと、
前記入力された複数の暗号文から一つの暗号文を選択するステップと、
選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化するステップとを有し、
前記鍵選択ステップは、第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択するステップを有し、
前記暗号文選択ステップは前記選択された第１のビット列に対応する暗号文を選択するステップを有し、
前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であることを特徴とする。
【００１５】
第７の態様によれば、本発明に係るプログラムは、
コンピュータに、
ＩＤベース暗号方式のセットアップを行うステップと、
ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数ＩＤに対して施すステップと、
指定した前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するステップをを実行させることを特徴とする。
【００１６】
第８の態様によれば、本発明に係るコンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）は、前記プログラムを記録したことを特徴とする。
【００１７】
第９の態様によれば、本発明に係る暗号化／復号化システムは、
ＩＤベース暗号方式のセットアップを行い、ＩＤベース暗号方式のエクストラクト・アルゴリズムを、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成された複数のＩＤに対して施し、指定された前記複数のＩＤに対してエクストラクト・アルゴリズムを実施した結果得られた複数の復号化鍵を出力するタイム装置と、
暗号文を復号する事が可能になる時刻である指定時刻データをビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成される複数のＩＤを指定し、前記タイム装置から出力されたシステムパラメータとしての暗号鍵及び前記複数のＩＤを読み込んで同一平文を複数回暗号化し、複数の暗号文を出力する暗号化装置と、
前記暗号化装置から出力された複数の暗号文及び指定時刻と、前記タイム装置から出力された複数の復号化鍵及び復号化鍵の生成時刻とを入力し、前記入力された複数の復号化鍵から一つの復号化鍵を選択し、前記入力された複数の暗号文から一つの暗号文を選択し、選択された前記復号鍵を使って前記選択された暗号文をＩＤベース暗号方式に基づいて復号化する復号手段とを有することを特徴とする。
【発明の効果】
【００１８】
本発明によれば、タイムサーバの計算量が暗号文受信者の数に依存しないという効果を有する。これは以下の２つの理由による。
【００１９】
第１の理由は、従来の方式とは異なり本発明ではタイムサーバは暗号文受信者と相互通信を行なう必要がなく、よってタイムサーバは暗号文受信者毎に依存したデータを作成する必要がないからである。
【００２０】
第２の理由は、本発明ではタイムサーバは各時刻につき一つだけ作成し、それを同報通信路を使って全ての暗号文受信者に送信し、タイムサーバが作成するデータは各時刻につき一つだけであり、暗号文受信者の数とは無関係であるからである。
【００２１】
また本発明によれば、暗号文送信者が指定した復号時刻にタイムサーバが作成した復号鍵を暗号文受信者が受信し損ねたとしても、暗号文受信者は暗号文を復号できるという効果を有する。しかもタイムサーバは復号鍵を再送信する必要はない。その理由は復号時刻以後の時刻にタイムサーバが作成した復号鍵からも、
復号に必要な鍵を復元できるからである。
【発明を実施するための最良の形態】
【００２２】
以下、図面を参照して本発明の実施の形態について説明する。
【００２３】
本発明に係る暗号化／復号化システムではＩＤベース（Ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ）暗号方式が採用されている。従来、複数のＩＤベース暗号方式が知られている。尚、このＩＤベース暗号方式としては例えば上記した非特許文献２、非特許文献３、非特許文献４に開示されたものを用いる事ができるがその他のものでもかまわない。以下、ＩＤベース暗号方式の四つのプロシージャをそれぞれセットアップ、エクストラクト、暗号化、復号化と呼ぶことにする。
【００２４】
図１は本発明に係る時間開放型暗号化／復号化システムの構成を示したブロック図である。本システムは、タイム装置１、暗号化装置２、復号化装置３の３種類の装置で構成されている。タイム装置１、暗号化装置２、復号化装置３はそれぞれ複数台あってもかまわないし、一台の装置が二種類の装置の機能を持ち合わせていてもかまわないが、図１には、もっとも簡単な場合としてこれらの装置が一台ずつある場合が示されている。
【００２５】
タイム装置１、暗号化装置２はそれぞれ送信装置ＴＢ０、送信装置ＥＢ０を持っており、暗号化装置２、復号化装置３はそれぞれ受信装置ＥＢ１、受信装置ＤＢ０を持っている。タイム装置１は電波を使ってデータを復号化装置に送信する。暗号化装置２と復号化装置３とはインターネットを使ってデータの送受信を行う。通信手段に用いる媒体として例えばインターネット、電波、電話線といった様々なものを用いる事ができるが、どのような方法を使って送受信を行ってもかまわない。
【００２６】
図１において、セキュリティ・パラメータｋ、対数上限値τはあらかじめタイム装置１、暗号化装置２、復号化装置３に配布されている。セキュリティ・パラメータｋは、例えば有限群の元の数のｌｏｇ等である。また各装置１，２，３にはペアリング組(G_1,G_2,H,q,＜・,・＞)が事前に配布されている。ペアリング組(G_1,G_2,H,,＜・,・＞)とはG_1,G_2,Hが同じ位数qを持つ有限群であり、＜・,・＞がG_1×G_2からHへの写像で、任意のg,h,x,yに対し＜g^x,h^y＞=＜g,h＞^{xy}が成立するものである。ペアリング組は例えば非特許文献５の方法で生成する事ができる。尚、以下の説明で位数qの巡回群をZ_qと表す。
【００２７】
図１でセキュリティ・パラメータｋ、対数上限値τ、平文Ｍ、指定時刻ｔをどのような方法で入力してもかまわない。入力方法として例えば、人間がコンピュータを使って手で入力してもよいし、コンピュータが内部で生成してもよいし、インターネット経由でデータを取得してもよい。
【００２８】
タイム装置１はその動作に現在時刻の入力を必要とする。図１に示すようにタイム装置１は、内部に現在時刻を知るためのクロックＴＢ３を有している。尚、外部クロック装置をタイム装置１に接続して外部から現在時刻を得てもよい。
【００２９】
以下、タイム装置１の動作について図１〜図３を参照して説明する。はじめにタイム装置１は図２のフローチャートに従って動作する。まずタイム装置１のＩＢＥセットアップ手段ＴＢ１にセキュリティ・パラメータｋが入力され、読み込まれる(ステップＳＦ１)。次にタイム装置１はＩＢＥセットアップ手段ＴＢ１を実施する（ステップＳＦ２)。具体的にセキュリティ・パラメータｋを読み込んだＩＢＥセットアップ手段ＴＢ１は、以下で詳細に説明するＩＤベース暗号方式のセットアップ・アルゴリズムを動作させ、システム・パラメータである暗号化鍵EncKey（Encryption Key）とマスター秘密鍵MasterSkを生成する。
【００３０】
ここで、ＩＢＥセットアップする手段について図６を参照して説明する。タイム装置１はまず有限群G_2の元g_2をランダムに選ぶ(ステップFSET1)。次にタイム装置１は前記Z_qの元MasterSkをランダムに選ぶ(ステップFSET2)。次にタイム装置１はh_2=g_2^{MasterSk}を計算する(ステップFSET3)。次にタイム装置１はEncKey=(g_1,g_2,h_2)を満たす暗号化鍵EncKeyを設定する(ステップFSET4)。すなわち、ＩＢＥセットアップ手段ＴＢ１は、ランダムに有限群G_2の元g_2を選択し、ランダムにマスター鍵MasterSkを選択し、前記元g_2を底とし前記マスター鍵MasterSkを指数とするべき乗剰余を計算し、前記元g_2と前記べき乗剰余の計算結果との組である暗号鍵(g_1,g_2,h_2)を出力する。尚、前記g_1は前記g_2から生成する場合と新たに生成する場合があり、いずれであってもよい。
【００３１】
ステップＳＦ２の処理後、タイム装置１は、前記暗号化鍵EncKeyを暗号化鍵記憶装置ＴＢ８に、前記マスター秘密鍵MasterSkをマスター秘密鍵記憶装置ＴＢ２に記憶する(ステップＳＦ３)。
【００３２】
以上の処理ステップが終了したら、次にタイム装置１は図３のフローチャートに従って動作する。まずタイム装置１は前記セキュリティ・パラメータｋ、対数上限値τ、暗号化鍵EncKey、マスター秘密鍵MasterSkを読み込む(ステップＴＦ１)。具体的には前記セキュリティ・パラメータｋはＩＢＥセットアップ手段に書き込まれ、対数上限値τはタイム装置用鍵選択手段ＴＢ５に書き込まれ、マスター秘密鍵MasterSkはマスター秘密鍵記憶装置に書き込まれる。
【００３３】
次にタイム装置１はｉを１にセットする(ステップＴＦ２)。次にタイム装置１はクロックＴＢ３から現在の時刻ｔを読みこみ、その現在時刻ｔが２^τ以下かどうかを判定し(ステップＴＦ３)、現在時刻ｔが２^２τ以下ならステップＴＦ４に進み、そうでなければ終了する。
【００３４】
次にタイム装置１はタイム装置用鍵選択手段を実施する(ステップＴＦ４)。タイム装置用鍵選択手段ＴＢ５では、ＩＤをｔ_ｉ=a_1||a_2||…||a_{i}とする。ここで、ａ_ｊはｔを二進数展開したときの上からｊ桁目のビットである。前記ＩＤは、入力された現在の時刻をビット列として表現したものの中で、かつ位が上から数ビット連結してできるビット列で構成されている。
【００３５】
次にタイム装置１はＩＢＥエクストラクト手段ＴＢ６を実施する(ステップＴＦ５)。ＩＢＥエクストラクト手段ＴＢ６では、ＩＤとして前記ｔ_ｉを、システムパラメータとして暗号鍵EncKey及びマスター秘密鍵MasterSkをそれぞれエクストラクト・アルゴリズムに入力し、DecKey（Decryption Key）_{ｔ，ｉ}を生成する。
【００３６】
ここで、エクストラクト・アルゴリズムについて図６を参照して説明する。タイム装置１はEncKeyを(g_1,g_2,h_2)とパース（構文解析）する(ステップFEXT1)。Hash_{G_1}をG_1に値を取るハッシュ関数として、タイム装置１はg_{t_i}=Hash_{G_1}(t_i)を計算する(ステップFEXT2)。次にタイム装置１は、DecKey_{t,1}=g_{t_i}^{MasketSk)を計算する(ステップFEXT3)。すなわちＩＢＥエクストラクト手段ＴＢ６は、前記入力された現在時刻ｔにあらかじめ配布された有限群の元g_{t_i}を対応させ、当該元g_{t_i}を底とし、マスター鍵MasketSkを指数とするべき乗剰余を計算し、複数の復号化鍵を生成する。
【００３７】
ステップＴＦ５の処理後、ＩＢＥエクストラクト手段ＴＢ６はｉに１を加える(ステップＴＦ６)。次にｉ≦τかどうかを判定し(ステップＴＦ７)、ｉ≦τであればステップＴＦ３に戻り、そうでなければステップＴＦ８に進む。次にタイム装置１は連結手段ＴＢ７を実施する(ステップＴＦ８)を行う。
【００３８】
連結手段ＴＢ７では、DecKey_ｔ=(DecKey_{ｔ，１}，…，DecKey_{ｔ，τ})の関係式を満たすようにDecKey_ｔを設定する。連結手段ＴＢ７は、現在の時刻ｔと前記DecKey_ｔとの組(ｔ，DecKey_ｔ)を以下で説明する復号装置３に送信装置ＴＢ０を介して出力し(ステップＴＦ９)、ステップＴＦ３に戻る。
【００３９】
次に暗号化装置２の動作を図１及び図４を参照して説明する。暗号化装置２にはまずセキュリティ・パラメータｋ、暗号化鍵EncKey、指定時刻Ｔ、および平文Ｍが入力され、それらが読み込まれる(ステップＥＦ１)。次に暗号化装置２は、ｉを１にセットする(ステップＥＦ２)。
【００４０】
次に暗号化装置２は暗号装置用鍵選択手段ＥＢ２を実施する（ステップＥＦ３)。暗号装置用鍵選択手段ＥＢ２では、ＩＤをT_i=b_1||b_2||…||b_{i-1}||1とする。ただしここでb_jはtを二進数展開したときの上からj桁目のビットであり、Tは指定時刻である。次に暗号化装置２はＩＢＥ暗号化手段ＥＢ３を実施する(ステップＥＦ４)。具体的にＩＢＥ暗号化手段ＥＢ３では、ＩＤとしてＴ_ｉを、システム・パラメータとして暗号鍵EncKeyを、平文としてＭをＩＤベース暗号の暗号化アルゴリズムに入力する。その暗号化アルゴリズムを前記入力データに施して、当該暗号文（Ciphertext_i）が生成される。
【００４１】
ここで、前記暗号化アルゴリズムについて図６を参照して説明する。まず暗号化装置２はg_{T_i}=Hash_{G_1}(T_i)を計算する(ステップFENC1)。暗号化装置２は次にｚ_ｑの元rをランダムに選ぶ(ステップFENC2)。暗号化装置２は、次にCiphertext_i =(M＜g_{T_i},g_2＞^r,g_2^ｒ)を計算する(ステップFENC3)。次に暗号化装置２はｉ=ｉ+１とする(ステップＥＦ５)。すなわち、ＩＢＥ暗号化手段ＥＢ３は、前記ＩＤに有限群の元g_{T_i}を対応させた上で、任意の乱数ｒを選択し、前記元g_{T_i}と公開鍵の一成分g_2とのペアリングを前記乱数ｒのべき乗計算をし、その計算結果に平分Ｍを乗じた第１の計算結果を得る。公開鍵の一成分g_2を前記乱数ｒのべき乗計算をして第２の計算結果を得る。前記第１の計算結果と前記第２の計算結果とからなる組(M＜g_{T_i},g_2＞^r,g_2^ｒ)を暗号文としてセットする。尚、g_{T_i}は有限群の元であり、g_2は有限群G_2の元であって、公開鍵の一成分である。
【００４２】
次にｉ=ｉ＋１にセットする(ステップＥＦ５)。次にＩＢＥ暗号化手段ＥＢ３は前記ｉがτ以下であるかどうかを判定し(ステップＥＦ６)、もしそうならステップＥＦ２へ進み、そうでないならステップＥＦ７へ進む。
【００４３】
次に暗号化装置２は連結手段ＥＢ４を実施する(ステップＥＦ７)。連結手段ＥＢ４では、暗号文Ciphertext=(Ciphertext_１，…，Ciphertext_τ)とし、指定時刻ｔと暗号文の組(T,Ciphertext)を送信装置ＥＢ０を介して復号装置３に出力する(ステップＥＦ８)。
【００４４】
以下、復号化装置３の動作について図１及び図５を参照して説明する。まず復号化装置３は暗号化鍵EncKey、指定時刻と暗号文の組(T，Ciphertext)、時刻tと復号化鍵との組(t，DecKey_t)を読み込む(ステップＤＦ１)。次に復号化装置３はＴ＜ｔかどうかを判定し(ステップＤＦ２)、もしそうならステップＤＦ３に進み、そうでなければ終了する。
【００４５】
次に復号化装置３は復号装置用鍵選択手段ＤＢ１を実施する(ステップＤＦ３)。復号装置用鍵選択手段ＤＢ１は、Ｔを二進数展開した時の上からｊ桁目のビットをａ_ｊとし、ｔを二進数展開した時の上からｊ桁目のビットをｂ_ｊとし、ａ_ｊ=ｂ_ｊとなる最大のｊをｊ_０として、t_0=a_1||…||a_{j_0}||1、D＝DecKey_{t_0}とするよう設定する。すなわち、鍵選択手段ＤＢ１は第１のビット列を選択し、選択された前記第１のビット列をＩＤとみなしたときのこのＩＤに対応する復号鍵を選択する。暗号文選択手段ＤＢ２は前記選択された第１のビット列に対応する暗号文を選択する。ここで、前記第１のビット列は第２のビット列に１をつなげたものであり、前記第２のビット列は前記指定時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列であって、同時に前記生成時刻をビット列として表現したものの中の位が上から数ビット連結してできるビット列である。
【００４６】
次に復号化装置３は暗号文選択手段ＤＢ２を実施する(ステップＤＦ３)。暗号文選択手段では、復号すべき暗号文Ｃを、関係式C=Ciphertext_{t_0}を満たすように設定する。次に復号化装置３はＩＢＥ復号手段ＤＢ３を実施する（ステップＤＦ４)。ＩＢＥ復号手段ＤＢ３では、システムパラメータとして暗号鍵EncKeyを、暗号文として前記Cを、秘密鍵としてＤを入力してＩＤベース暗号の復号化アルゴリズムを行い、平文Ｍを生成する。最後に平文Ｍは出力手段ＤＢ４より出力される(ステップＤＦ５)。
【００４７】
ここで、復号化アルゴリズムについて図６を参照して説明する。
【００４８】
まず復号化装置３はC=(X,Y)とパースする(ステップFDEC1)。次に復号化装置３はｇ_{t_0}=Hash_{G_1}(T_i)を計算する(ステップFDEC2)。次に復号化装置３はM=X/＜g_{t_0}、Y＞を計算する(ステップFDEC3)。最後に復号化装置３は平文Mを出力する(ステップDF5)。すなわち、ＩＢＥ復号手段ＤＢ３は、前記選択された暗号文を第１の成分Ｘと第２の成分Ｙに分け、本実施の形態ではＹ成分と有限群の元g_{t_0}とのペアリングを計算し、他方のＸ成分を、前記計算結果で除する。
【００４９】
また、発明対象としては、上記復号化鍵生成方法、暗号化方法、復号化方法における各ステップをコンピュータに実行させるプログラムも含み、このプログラムはプログラムそのものであってもよいし、このプログラムがコンピュータで読み取り可能な記録媒体に格納されているものであってもよい。
【００５０】
本発明では、この記録媒体として、マイクロコンピュータで処理が行なわれるために必要なメモリ、例えばＲＯＭのようなものそのものがプログラムメディアであってもよいし、また、図示していない外部記憶装置としてプログラム読み取り装置が設けられ、そこに記録媒体を挿入することで読み取り可能なプログラムメディアであってもよい。いずれの場合においても、格納されているプログラムはマイクロコンピュータがアクセスして実行させる構成であってもよいし、あるいはいずれの場合もプログラムを読み出し、読み出されたプログラムは、マイクロコンピュータのプログラム記憶エリアにロードされて、そのプログラムが実行される方式であってもよい。このロード用のプログラムは予め本体装置に格納されているものとする。
【００５１】
ここで、上記プログラムメディアは、本体と分離可能に構成される記録媒体であり、磁気テープやカセットテープ等のテープ系、ＦＤ（フレキシブルディスク）やＨＤ（ハードディスク）等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ等の光ディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＲＯＭ等による半導体メモリを含めた固定的にプログラムを担持する媒体であってもよい。
【００５２】
また、本発明においては、インターネットを含む通信ネットワークと接続可能なシステム構成であることから、通信ネットワークからプログラムをダウンロードするように流動的にプログラムを担持する媒体であってもよい。なお、このように通信ネットワークからプログラムをダウンロードする場合には、そのダウンロード用プログラムは予め装置本体に格納しておくか、あるいは別の記録媒体からインストールされるものであってもよい。
【００５３】
さらに、本発明では、プログラム自体として、マイクロコンピュータで実行される処理そのものであってもよいし、あるいはインターネットを含む通信ネットワークとアクセスすることで取り込める、あるいは取り込めたものであってもよいし、こちらから送り出すものであってもよい。
【００５４】
また、上記した各実施の形態は、本発明を好適に実施した形態の一例に過ぎず、本発明は、その主旨を逸脱しない限り、種々変形して実施することが可能なものである。
【図面の簡単な説明】
【００５５】
【図１】本発明に係る暗号化／復号化システムの構成を示したブロック図である。
【図２】タイム装置の処理手順を示すフローチャートである。
【図３】タイム装置の処理手順を示すフローチャートである。
【図４】暗号化装置の処理手順を示すフローチャートである。
【図５】復号化装置の処理手順を示すフローチャートである。
【図６】本発明に係る暗号化／復号化システムに適用される各アルゴリズム処理手順を示したフローチャートである。
【符号の説明】
【００５６】
ＴＢ０    送信装置
ＴＢ１    ＩＢＥセットアップ手段
ＴＢ２    マスター秘密鍵記憶装置
ＴＢ３    クロック
ＴＢ４    復号化鍵計算手段
ＴＢ５    タイム装置用鍵選択手段
ＴＢ６    ＩＢＥエクストラ手段
ＴＢ７    連結手段
ＴＢ８    暗号化鍵記憶手段
ＥＢ０    送信装置
ＥＢ１    受信装置
ＥＢ２    暗号装置用鍵選択手段
ＥＢ３    ＩＢＥ暗号化手段
ＥＢ４    連結手段
ＥＢ５    入力手段
ＤＢ０    受信装置
ＤＢ１    復号装置用鍵選択手段
ＤＢ２    暗号文選択手段
ＤＢ３    ＩＢＥ復号手段
ＤＢ４    出力手段
【図１】
2007036364.tif 000003
【図２】
2007036364.tif 000004
【図３】
2007036364.tif 000005
【図４】
2007036364.tif 000006
【図５】
2007036364.tif 000007
【図６】
2007036364.tif 000008