暗号システム、鍵生成装置、受信者側装置、送信者側装置、プログラム及び暗号通信方法
【課題】 ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全な公開鍵暗号方法を与えることを目的とする。
【解決手段】 受信者側装置１１０の鍵情報生成部１１３は、セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）をベースとし、第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）を利用して、第三暗号プロトコルΠ’における暗号化鍵及び復号鍵を生成する。
【解決手段】 受信者側装置１１０の鍵情報生成部１１３は、セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）をベースとし、第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）を利用して、第三暗号プロトコルΠ’における暗号化鍵及び復号鍵を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージを暗号化して通信を行う暗号システムに関する。
【背景技術】
【０００２】
暗号方法の一つである公開鍵暗号の安全性は、通常、ランダムオラクルモデル（例えば、非特許文献１参照）、または、標準計算機モデル上で与えられる。
【０００３】
ランダムオラクルモデルでは、全てのパーティ（攻撃者を含む）がランダム関数へオラクルとしてアクセスすることが許されている（以下、このようなランダム関数をランダムオラクルと呼ぶ）。一般にランダムオラクルは現実世界では存在しないため、ランダムオラクルモデルはヒューリスティックなモデルであるが、効率的で安全証明可能な暗号プロトコルの設計が比較的容易であるメリットをもつため、ランダムオラクルモデル上で安全な暗号プロトコルは多く利用されている（例えば、非特許文献２参照）。現実のシステムにおいては、ランダムオラクルの部分は実用的なハッシュ関数に置き換えて利用されるため（非特許文献２参照）、実システムにおける安全性は完全には保証されない。
【０００４】
非特許文献３には、ランダムオラクルの性質の一部を満たすハッシュ関数について記載されているが、確率的性質を持っているため、公開鍵暗号や署名などのシステムへの適用は知られていない。また、ランダムオラクルの実装に関するネガティブな結果として、ランダムオラクルモデル上では安全であるが、ランダムオラクルのいかなる関数への置き換えに対しても安全ではなくなる暗号プロトコルが存在することが知られている（例えば、非特許文献４参照）。
【０００５】
【非特許文献１】M. Bellare and P. Rogaway. “Ｒandom Oracles are Practical”, October 20, 1995: A Paradigm for Designing Efficient Protocols, http://www.cse.ucsd.edu/ ~mihir/papers/ro.html
【非特許文献２】V. Shoup. ISO 18033-2: An Emerging Standard for Public-Key Encryption, December 6, 2004, http://www.shoup.net/iso/
【非特許文献３】R. Canetti. Towards realizingrandom oracles: “Hash functions that hide all partial information”, March 10, 2000, http://domino.research.ibm.com/comm/ research_projects.nsf/pages/security.Publications.html/
【非特許文献４】R. Canetti et al. "Random Oracle Methodology”, Revised, August 6, 2002, http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.Publications.html/
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述のように、公開鍵暗号の安全性は、通常、ランダムオラクルモデル、または、標準計算機モデル上で与えられ、従来技術では、ランダムオラクルモデル上での公開鍵暗号方法と、標準計算機モデル上での公開鍵暗号方法と、はそれぞれのモデルにおいて考察されるにとどまり、これらのモデル相互間において、安全性を考察することは行われていない。
【０００７】
そこで、本発明では、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全な公開鍵暗号方法を与えることを目的とする。
【課題を解決するための手段】
【０００８】
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）をベースとし、第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）を利用して、第三暗号プロトコルΠ’における暗号化鍵及び復号鍵を生成する。
【０００９】
例えば、本発明は、送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【００１０】
【数１】
【００１１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【００１２】
【数２】
【００１３】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【００１４】
【数３】
【００１５】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【００１６】
【数４】
【００１７】
なる関数族とする。）と、を有する鍵生成処理を行い、
前記送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【００１８】
【数５】
【００１９】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【００２０】
【数６】
【００２１】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【００２２】
【数７】
【００２３】
を作成する処理と、
【００２４】
【数８】
【００２５】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【００２６】
【数９】
【００２７】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【００２８】
【数１０】
【００２９】
を計算する処理と、を有する復号化処理を行うこと、を特徴とする。
【発明の効果】
【００３０】
以上のように、本発明によれば、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全な公開鍵暗号方法を与えることができる。
【発明を実施するための最良の形態】
【００３１】
以下の実施形態においては、暗号プロトコルを公開鍵暗号プロトコルとして利用し、公開鍵を暗号化鍵とし、秘密鍵を復号化鍵として利用する例を説明するが、このような態様に限定されるわけではない。
【００３２】
＜第１の実施形態＞
本発明の第１の実施形態では、ランダムオラクルＯ１，・・・，Ｏｎを利用する第１公開鍵暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）をベースにして、ランダムオラクルに依存しない第２公開鍵暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ)（１≦ｉ≦ｎ）を利用して、ランダムオラクルに依存しない第３公開鍵暗号プロトコルΠ’＝（Ｋ’，Ｅ’，Ｄ’）を与える方法について述べる。但し、第１公開鍵暗号プロトコルΠの鍵生成手段Ｋはランダムオラクルに依存しないものとする。
【００３３】
図１は、本発明の第１の実施形態における暗号システム１００の概略図である。図示するように、暗号システム１００は、受信者側装置１１０と、送信者側装置１５０と、を備えており、これらはネットワーク１９０を介して相互に情報を送受信することができるようにされている。
【００３４】
図２は、受信者側装置１１０の概略図である。図示するように、受信者側装置１１０は、情報を入力する入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置１１０の各部の制御を行う演算部１１２と、記憶部１３０と、ネットワーク１９０を介して送信者側装置１５０と通信を行う通信部１３１と、情報を出力する出力部１３２と、を備える。
【００３５】
演算部１１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部１１３と、復号化処理を行う復号化部１１７と、を有する。
【００３６】
図３は、鍵情報生成部１１３の概略図である。図示するように、鍵情報生成部１１３は、第１鍵生成部１１４と、第２鍵生成部１１６と、を備える。
【００３７】
第１鍵生成部１１４は、ランダムオラクルＯ１，・・・，Ｏｎを利用する第１公開鍵暗号プロトコルΠ（鍵生成手段Ｋ，暗号化手段Ｅ，復号化手段Ｄ）により、公開鍵と秘密鍵を生成する。ここで、ｎは、第１公開鍵暗号プロトコルΠに依存して定まる自然数である。
【００３８】
第２鍵生成部１１５は、ランダムオラクルに依存しない第１公開鍵暗号プロトコルΠとは別の第２公開鍵暗号プロトコルＰＫＥｉ（鍵生成手段Ｋｇｉ，暗号化手段Ｅｎｃｉ，復号化手段Ｄｅｃｉ）を利用して、公開鍵と秘密鍵を生成する。ここで、ｉは１≦ｉ≦ｎを満たす自然数である。
【００３９】
なお、第２鍵生成部１１５は、ｎに対応する鍵生成実行部１１６−１，・・・，１１６ｎを有し、ｉに対応する鍵生成実行部１１６−ｉを用いて公開鍵及び秘密鍵を生成する。
【００４０】
図４は、復号化部１１７の概略図である。図示するように、復号化部１１７は、第１復号化部１１８と、第２復号化部１１９と、関数計算部１２１と、を備える。
【００４１】
第１復号化部１１８は、第１公開鍵暗号プロトコルΠにより、当該第１公開鍵暗号プロトコルΠで生成された秘密鍵を用いて、復号化する処理を行う。
【００４２】
第２復号化部１１９は、第２公開鍵暗号プロトコルＰＫＥｉにより、当該第２公開鍵暗号プロトコルＰＫＥｉの秘密鍵を用いて、復号化する処理を行う。
【００４３】
なお、第２復号化部１１９は、ｎ個の復号化実行部１２０−１，・・・，１２０ｎを有し、ｉに対応する復号化実行部１２０−ｉが、ｉに対応する秘密鍵を用いて復号化処理を行う。
【００４４】
関数計算部１２１は、ハッシュ関数等の各種関数の計算を行う。
【００４５】
以上に記載した受信者側装置１１０は、例えば、図５（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【００４６】
例えば、入力部１１１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、演算部１１２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１３０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１３１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１３２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４７】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４８】
図６は、送信者側装置１５０の概略図である。図示するように、送信者側装置１５０は、情報を入力する入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置１５０の各部の制御を行う演算部１５２と、記憶部１６０と、ネットワーク１９０を介して受信者側装置１１０と通信を行う通信部１６１と、情報を出力する出力部１６２と、を備える。
【００４９】
演算部１５２は、乱数を生成する乱数生成部１５３と、暗号化処理を行う暗号化部１５４と、を備える。
【００５０】
図７は、暗号化部１５４の概略図である。図示するように、暗号化部１５４は、第１暗号化部１５５と、第２暗号化部１５６と、関数計算部１５８と、を備える。
【００５１】
第１暗号化部１５５は、第１公開鍵暗号プロトコルΠにより、当該第１公開鍵暗号プロトコルΠで生成された公開鍵を用いて、暗号化する処理を行う。
【００５２】
第２暗号化部１５６は、第２公開鍵暗号プロトコルＰＫＥｉにより、当該第２公開鍵暗号プロトコルＰＫＥｉの公開鍵を用いて、暗号化する処理を行う。
【００５３】
なお、第２暗号化部１５６は、ｎ個の暗号化実行部１５７−１，・・・，１５７ｎを有し、ｉに対応する暗号化実行部１５７−ｉが、ｉに対応する公開鍵を用いて暗号化処理を行う。
【００５４】
関数計算部１５８は、ハッシュ関数等の各種関数の計算を行う。
【００５５】
以上に記載した送信者側装置１５０は、例えば、図５に示すような一般的なコンピュータ９００で実現できる。
【００５６】
例えば、入力部１５１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、演算部１５２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１６０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１６１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１６２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００５７】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００５８】
図８は、第一の実施形態における暗号処理を示すフロー図である。
【００５９】
［受信者側装置１１０での鍵生成処理］
受信者側装置１１０は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付ける（Ｓ１０）。
【００６０】
次に、鍵情報生成部１１３の第１鍵生成部１１４が、第１公開鍵暗号プロトコルΠの鍵生成手段Ｋを用いて、
【００６１】
【数１１】
【００６２】
により公開鍵ｐｋ及び秘密鍵ｓｋを生成する（Ｓ１１）。
【００６３】
次に、鍵情報生成部１１３の第２鍵生成部１１５が、ｉに対応する鍵生成実行部１１６−ｉを用いて、
【００６４】
【数１２】
【００６５】
により公開鍵ＰＫｉ及び秘密鍵ＳＫｉを各々生成する（Ｓ１２）。
【００６６】
そして、鍵情報生成部１１３は、
【００６７】
【数１３】
【００６８】
とする公開鍵ＰＫ及び秘密鍵ＳＫを生成する（Ｓ１３）。但し、Ｆｉ（１≦ｉ≦ｎ）は、
【００６９】
【数１４】
【００７０】
なる関数族とする。なお、Ｎは自然数である。
【００７１】
また、受信者側装置１１０の演算部１１２は、公開鍵ＰＫを、ネットワーク１９０その他の搬送手段を介して取得できるように公開する（Ｓ１４）。
【００７２】
［送信者側装置１５０での暗号化処理］
まず、送信者側装置１５０の演算部１５２は、入力部１５１又は通信部１６１を介して、受信者側装置１１０より公開鍵ＰＫを取得する（Ｓ１５）。
【００７３】
また、演算部１５２は、入力部１５１又は通信部１６１を介して、メッセージ文Ｍの入力を受け付ける（Ｓ１６）。
【００７４】
そして、演算部１５２の乱数生成部１５３が、
【００７５】
【数１５】
【００７６】
をランダムに選ぶ（Ｓ１７）。
【００７７】
さらに、演算部１５２の第２暗号化部１５２が、ｉに対応する暗号化実行部１５７−ｉを用いて、公開鍵ＰＫｉより、
【００７８】
【数１６】
【００７９】
を生成する（Ｓ１８）。
【００８０】
さらに、演算部１５２の第１暗号化部１５５が、公開鍵ｐｋ及び第１公開鍵暗号プロトコルΠの暗号化手段Ｅを用いて、
【００８１】
【数１７】
【００８２】
を生成する（Ｓ１９）。ここで、第１暗号化部１５５は、ランダムオラクルＯ１，・・・，Ｏｎの代わりに、関数計算部１５８を用いることにより、
【００８３】
【数１８】
【００８４】
の関数による計算を行う。
【００８５】
そして、送信者側装置１５０の演算部１５２は、
【００８６】
【数１９】
【００８７】
をメッセージ文Ｍに対する暗号文として、通信部１６１又は出力部１６２を介して、受信者側装置１１０に出力する（Ｓ２０）。
【００８８】
［受信者側装置１１０での復号化処理］
受信者側装置１１０の演算部１１２は、入力部１１１又は通信部１３１を介して、送信者側装置１５０より暗号文Ｃを取得する（Ｓ２１）。
【００８９】
次に、復号化部１１７の第２復号化部１１９が、ｉに対応する復号化実行部１２０−ｉを用いて、秘密鍵ＳＫｉより、
【００９０】
【数２０】
【００９１】
を計算する（Ｓ２２）。
【００９２】
さらに、復号化部１１７の第１復号化部１１８が、第１公開鍵暗号プロトコルΠの復号化手段Ｄを用いて、秘密鍵ｓｋより、
【００９３】
【数２１】
【００９４】
を計算する（Ｓ２３）。ここで、第１復号化部１１８は、ランダムオラクルＯ１，・・・，Ｏｎの代わりに、関数計算部１２１を用いることにより、
【００９５】
【数２２】
【００９６】
の関数による計算を行う。
【００９７】
そして、受信者側装置１１０の演算部１１２は、Ｍ’を暗号文Ｃに対するメッセージ文として取得する。
【００９８】
本第１の実施形態において、関数族Ｆｉが条件「いかなる攻撃者も、シードσｉ自体を得ることなく、真のランダム関数とｆσｉｉを区別することが難しい」を満たし、かつ、第１公開鍵暗号プロトコルΠが条件「任意の関数を利用した復号オラクルへアクセスすることができるが、ランダムオラクルへの直接的アクセスを許されない如何なる攻撃者に対しても識別不能性が満たされる」を満たすとき、第３公開鍵暗号プロトコルΠ’はＩＮＤ−ＣＣＡ２安全であることが証明される。
【００９９】
なお、識別不能性やIND-CCA2安全の定義・詳細については、下記の非特許文献５に詳細に記載されている。
【０１００】
非特許文献５：M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. “Ｒelations among notions of security for public-key encryption schemes”, June 2001, http://www.cs.ucsd.edu/users/ mihir/papers/relations.html
＜第２の実施形態＞
次に、第２の実施形態について説明する。本発明の第２の実施形態は、第１の実施形態と比較して、受信者側装置２１０及び送信者側装置２５０が異なっているため、以下、これらの異なっている点に関連する事項について説明する。
【０１０１】
図９は、受信者側装置２１０の概略図である。図示するように、受信者側装置２１０は、入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置２１０の各部の制御を行う演算部２１２と、記憶部１３０と、ネットワーク１９０を介して送信者側装置２５０と通信を行う通信部１３１と、情報を出力する出力部１３２と、を備え、第一の実施形態と比較して演算部２１２が異なるため、以下、演算部２１２について説明する。
【０１０２】
演算部２１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部２１３と、復号化処理を行う復号化部２１７と、を有する。
【０１０３】
図１０は、鍵情報生成部２１３の概略図である。図示するように、鍵情報生成部２１３は、第１落とし戸付き一方向性関数生成部２１４と、第２落とし戸付き一方向性関数生成部２１５と、を備える。
【０１０４】
第１落とし戸付き一方向性関数生成部２１４は、一方向性関数と落とし戸の対を生成する。
【０１０５】
第２落とし戸付き一方向性関数生成部２１５は、第１落とし戸付き一方向性関数生成部２１４とは異なる一方向性関数と落とし戸の対を生成する。
【０１０６】
図１１は、復号化部２１７の概略図である。図示するように、復号化部２１７は、第１復号化部２１８と、第２復号化部２１９と、関数計算部２２０と、検査部２２１と、を備える。
【０１０７】
第１復号化部２１８は、第１落とし戸付き一方向性関数生成部２１４で生成された落とし戸π−１１を用いた演算を行う。
【０１０８】
第２復号化部２１９は、第２落とし戸付き一方向性関数生成部２１５で生成された落とし戸π−１２を用いた演算を行う。
【０１０９】
関数計算部２２０は、ハッシュ関数等の各種関数の計算を行う。
【０１１０】
検査部２２１は、復号化部２１７で復号されたメッセージの検証を行う。
【０１１１】
図１２は、送信者側装置１５０の概略図である。図示するように、送信者側装置２５０は、情報を入力する入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置２５０の各部の制御を行う演算部２５２と、記憶部１６０と、ネットワーク１９０を介して受信者側装置１１０と通信を行う通信部１６１と、情報を出力する出力部１６２と、を備え、第１の実施形態と比較して、演算部２５２が異なっているため、以下、演算部２５２に関連する事項について説明する。
【０１１２】
演算部２５２は、乱数を生成する乱数生成部２５３と、暗号化処理を行う暗号化部２５４と、を備える。
【０１１３】
図１３は、暗号化部２５４の概略図である。図示するように、暗号化部２５４は、第１暗号化部２５５と、第２暗号化部２５６と、関数計算部２５８と、を備える。
【０１１４】
第１暗号化部１５５は、受信者側装置２１０の第１落とし戸付き一方向性関数生成部２１４で生成された一方向性関数π１を用いた演算を行う。
【０１１５】
第２暗号化部１５６は、受信者側装置２１０の第２落とし戸付き一方向性関数生成部２１５で生成された一方向性関数π２を用いた演算を行う。
【０１１６】
関数計算部２５７は、ハッシュ関数等の各種関数の計算を行う。
【０１１７】
図１４は、第２の実施形態における暗号処理を示すフロー図である。
【０１１８】
［受信者側装置２１０での鍵生成処理］
受信者側装置２１０は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付ける（Ｓ３０）。
【０１１９】
次に、鍵情報生成部２１３の第１落とし戸付き一方向性関数生成部２１４及び第２落とし戸付き一方向性関数生成部２１５が、
【０１２０】
【数２３】
【０１２１】
により一方向性関数と落とし戸の対（π１，π−１１）、（π２，π−１２）を生成する（Ｓ３１）。ここで、Ｇは確率的アルゴリズムである。
【０１２２】
そして、鍵情報生成部２１３は、
【０１２３】
【数２４】
【０１２４】
とする公開鍵ＰＫ及び秘密鍵ＳＫを生成する（Ｓ３２）。但し、Ｒは、有限集合、Ｆｉ（１≦ｉ≦２）は、
【０１２５】
【数２５】
【０１２６】
なる関数族とする。なお、Ｎは自然数である。
【０１２７】
また、受信者側装置２１０の演算部２１２は、公開鍵ＰＫを、ネットワーク１９０その他の搬送手段を介して取得できるように公開する（Ｓ３３）。
【０１２８】
［送信者側装置２５０での暗号化処理］
まず、送信者側装置２５０の演算部２５２は、入力部１５１又は通信部１６１を介して、受信者側装置３１０より公開鍵ＰＫを取得する（Ｓ３４）。
【０１２９】
また、演算部２５２は、入力部２５１又は通信部２６１を介して、メッセージ文Ｍの入力を受け付ける（Ｓ３５）。
【０１３０】
そして、演算部２５２の乱数生成部２５３が、
【０１３１】
【数２６】
【０１３２】
をランダムに選ぶ（Ｓ３６）。
【０１３３】
さらに、演算部２５２の第１暗号化部２５５及び第２暗号化部２５６が、公開鍵ＰＫの一方向性関数π１、π２をそれぞれ用いて、
【０１３４】
【数２７】
【０１３５】
を生成する（Ｓ３７）。
【０１３６】
さらに、暗号化部２５４が、関数計算部２５７を用いて、
【０１３７】
【数２８】
【０１３８】
を生成する（Ｓ３８）。
【０１３９】
そして、送信者側装置２５０の演算部２５２は、
【０１４０】
【数２９】
【０１４１】
をメッセージ文Ｍに対する暗号文として、通信部１６１又は出力部１６２を介して、受信者側装置２１０に出力する（Ｓ３９）。
【０１４２】
［受信者側装置２１０での復号化処理］
受信者側装置２１０の演算部２１２は、入力部１１１又は通信部１３１を介して、送信者側装置２５０より暗号文Ｃを取得する（Ｓ４０）。
【０１４３】
次に、復号化部２１７の第１復号化部２１８及び第２復号化部１１９が、秘密鍵ＳＫの落とし戸π１−１、π２−１をそれぞれ用いて、
【０１４４】
【数３０】
【０１４５】
を計算する（Ｓ４１）。
【０１４６】
さらに、復号化部２１７が関数計算部２２０を用いて、
【０１４７】
【数３１】
【０１４８】
を計算する（Ｓ４２）。
【０１４９】
また、復号化部２１７が関数計算部２２０を用いて、
【０１５０】
【数３２】
【０１５１】
を計算する（Ｓ４３）。
【０１５２】
そして、復号化部２１７の検査部２２１が、ステップＳ４３で計算したｖ２を検査する（Ｓ４４）。そして、検査に成功すれば、演算部２１２は、ステップＳ３１で算出されたＭを暗号文Ｃに対するメッセージ文として取得する。
【０１５３】
第二の実施形態の方法は、非特許文献１に記載の公開鍵暗号方法をベースに変形した後、第一の実施形態の方法を適用した。本発明の方法によると、関数族Ｆｉ（１≦ｉ≦２）が条件「いかなる攻撃者も、シードσｉ自体を得ることなく、真のランダム関数とｆσｉｉを区別することが難しい」を満たすとき、上記公開鍵暗号はＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１５４】
以上の第一の実施形態及び第二の実施形態では、受信者側装置１１０、２１０及び送信者側装置１５０、２５０の間で暗号通信を行う例を示したが、このような態様に限定されるわけではなく、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、の他、ファイル暗号システムなど様々なシステムに適用することが可能である。
【０１５５】
また、第一の実施形態及び第二の実施形態における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われる他、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。
【０１５６】
さらに、上述した実施形態においては、受信者側装置１１０、２１０で公開鍵及び秘密鍵を生成したが、このような態様に限定されず、他の装置（例えば、鍵生成装置）の演算部が、入力部を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付けて、第３公開鍵暗号プロトコルΠ’における公開鍵ＰＫ及び秘密鍵ＳＫを生成し、公開鍵ＰＫを送信者側装置１５０、２５０に出力し（公開し）、秘密鍵ＳＫを受信者側装置１１０、２１０に（安全な方法で）出力するようにしてもよい。
【図面の簡単な説明】
【０１５７】
【図１】暗号システムの概略図。
【図２】受信者側装置の概略図。
【図３】鍵情報生成部の概略図。
【図４】復号化部の概略図。
【図５】コンピュータの概略図。
【図６】送信者側装置の概略図。
【図７】暗号化部の概略図。
【図８】暗号通信を示すフロー図。
【図９】受信者側装置の概略図。
【図１０】鍵情報生成部の概略図。
【図１１】復号化部の概略図。
【図１２】送信者側装置の概略図。
【図１３】暗号化部の概略図。
【図１４】暗号通信を示すフロー図。
【符号の説明】
【０１５８】
１００ 暗号システム
１１０、２１０ 受信者側装置
１１１ 入力部
１１２、２１２ 演算部
１１３、２１３ 鍵情報生成部
１１７、２１７ 復号化部
１３０ 記憶部
１３１ 通信部
１３２ 出力部
１５０、２５０ 送信者側装置
１５１ 入力部
１５２、２５２ 演算部
１５３、２５３ 乱数生成部
１５４、２５４ 暗号化部
１６０ 記憶部
１６１ 通信部
１６２ 出力部
【技術分野】
【０００１】
本発明は、メッセージを暗号化して通信を行う暗号システムに関する。
【背景技術】
【０００２】
暗号方法の一つである公開鍵暗号の安全性は、通常、ランダムオラクルモデル（例えば、非特許文献１参照）、または、標準計算機モデル上で与えられる。
【０００３】
ランダムオラクルモデルでは、全てのパーティ（攻撃者を含む）がランダム関数へオラクルとしてアクセスすることが許されている（以下、このようなランダム関数をランダムオラクルと呼ぶ）。一般にランダムオラクルは現実世界では存在しないため、ランダムオラクルモデルはヒューリスティックなモデルであるが、効率的で安全証明可能な暗号プロトコルの設計が比較的容易であるメリットをもつため、ランダムオラクルモデル上で安全な暗号プロトコルは多く利用されている（例えば、非特許文献２参照）。現実のシステムにおいては、ランダムオラクルの部分は実用的なハッシュ関数に置き換えて利用されるため（非特許文献２参照）、実システムにおける安全性は完全には保証されない。
【０００４】
非特許文献３には、ランダムオラクルの性質の一部を満たすハッシュ関数について記載されているが、確率的性質を持っているため、公開鍵暗号や署名などのシステムへの適用は知られていない。また、ランダムオラクルの実装に関するネガティブな結果として、ランダムオラクルモデル上では安全であるが、ランダムオラクルのいかなる関数への置き換えに対しても安全ではなくなる暗号プロトコルが存在することが知られている（例えば、非特許文献４参照）。
【０００５】
【非特許文献１】M. Bellare and P. Rogaway. “Ｒandom Oracles are Practical”, October 20, 1995: A Paradigm for Designing Efficient Protocols, http://www.cse.ucsd.edu/ ~mihir/papers/ro.html
【非特許文献２】V. Shoup. ISO 18033-2: An Emerging Standard for Public-Key Encryption, December 6, 2004, http://www.shoup.net/iso/
【非特許文献３】R. Canetti. Towards realizingrandom oracles: “Hash functions that hide all partial information”, March 10, 2000, http://domino.research.ibm.com/comm/ research_projects.nsf/pages/security.Publications.html/
【非特許文献４】R. Canetti et al. "Random Oracle Methodology”, Revised, August 6, 2002, http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.Publications.html/
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述のように、公開鍵暗号の安全性は、通常、ランダムオラクルモデル、または、標準計算機モデル上で与えられ、従来技術では、ランダムオラクルモデル上での公開鍵暗号方法と、標準計算機モデル上での公開鍵暗号方法と、はそれぞれのモデルにおいて考察されるにとどまり、これらのモデル相互間において、安全性を考察することは行われていない。
【０００７】
そこで、本発明では、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全な公開鍵暗号方法を与えることを目的とする。
【課題を解決するための手段】
【０００８】
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）をベースとし、第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）を利用して、第三暗号プロトコルΠ’における暗号化鍵及び復号鍵を生成する。
【０００９】
例えば、本発明は、送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【００１０】
【数１】
【００１１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【００１２】
【数２】
【００１３】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【００１４】
【数３】
【００１５】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【００１６】
【数４】
【００１７】
なる関数族とする。）と、を有する鍵生成処理を行い、
前記送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【００１８】
【数５】
【００１９】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【００２０】
【数６】
【００２１】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【００２２】
【数７】
【００２３】
を作成する処理と、
【００２４】
【数８】
【００２５】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【００２６】
【数９】
【００２７】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【００２８】
【数１０】
【００２９】
を計算する処理と、を有する復号化処理を行うこと、を特徴とする。
【発明の効果】
【００３０】
以上のように、本発明によれば、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全な公開鍵暗号方法を与えることができる。
【発明を実施するための最良の形態】
【００３１】
以下の実施形態においては、暗号プロトコルを公開鍵暗号プロトコルとして利用し、公開鍵を暗号化鍵とし、秘密鍵を復号化鍵として利用する例を説明するが、このような態様に限定されるわけではない。
【００３２】
＜第１の実施形態＞
本発明の第１の実施形態では、ランダムオラクルＯ１，・・・，Ｏｎを利用する第１公開鍵暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）をベースにして、ランダムオラクルに依存しない第２公開鍵暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ)（１≦ｉ≦ｎ）を利用して、ランダムオラクルに依存しない第３公開鍵暗号プロトコルΠ’＝（Ｋ’，Ｅ’，Ｄ’）を与える方法について述べる。但し、第１公開鍵暗号プロトコルΠの鍵生成手段Ｋはランダムオラクルに依存しないものとする。
【００３３】
図１は、本発明の第１の実施形態における暗号システム１００の概略図である。図示するように、暗号システム１００は、受信者側装置１１０と、送信者側装置１５０と、を備えており、これらはネットワーク１９０を介して相互に情報を送受信することができるようにされている。
【００３４】
図２は、受信者側装置１１０の概略図である。図示するように、受信者側装置１１０は、情報を入力する入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置１１０の各部の制御を行う演算部１１２と、記憶部１３０と、ネットワーク１９０を介して送信者側装置１５０と通信を行う通信部１３１と、情報を出力する出力部１３２と、を備える。
【００３５】
演算部１１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部１１３と、復号化処理を行う復号化部１１７と、を有する。
【００３６】
図３は、鍵情報生成部１１３の概略図である。図示するように、鍵情報生成部１１３は、第１鍵生成部１１４と、第２鍵生成部１１６と、を備える。
【００３７】
第１鍵生成部１１４は、ランダムオラクルＯ１，・・・，Ｏｎを利用する第１公開鍵暗号プロトコルΠ（鍵生成手段Ｋ，暗号化手段Ｅ，復号化手段Ｄ）により、公開鍵と秘密鍵を生成する。ここで、ｎは、第１公開鍵暗号プロトコルΠに依存して定まる自然数である。
【００３８】
第２鍵生成部１１５は、ランダムオラクルに依存しない第１公開鍵暗号プロトコルΠとは別の第２公開鍵暗号プロトコルＰＫＥｉ（鍵生成手段Ｋｇｉ，暗号化手段Ｅｎｃｉ，復号化手段Ｄｅｃｉ）を利用して、公開鍵と秘密鍵を生成する。ここで、ｉは１≦ｉ≦ｎを満たす自然数である。
【００３９】
なお、第２鍵生成部１１５は、ｎに対応する鍵生成実行部１１６−１，・・・，１１６ｎを有し、ｉに対応する鍵生成実行部１１６−ｉを用いて公開鍵及び秘密鍵を生成する。
【００４０】
図４は、復号化部１１７の概略図である。図示するように、復号化部１１７は、第１復号化部１１８と、第２復号化部１１９と、関数計算部１２１と、を備える。
【００４１】
第１復号化部１１８は、第１公開鍵暗号プロトコルΠにより、当該第１公開鍵暗号プロトコルΠで生成された秘密鍵を用いて、復号化する処理を行う。
【００４２】
第２復号化部１１９は、第２公開鍵暗号プロトコルＰＫＥｉにより、当該第２公開鍵暗号プロトコルＰＫＥｉの秘密鍵を用いて、復号化する処理を行う。
【００４３】
なお、第２復号化部１１９は、ｎ個の復号化実行部１２０−１，・・・，１２０ｎを有し、ｉに対応する復号化実行部１２０−ｉが、ｉに対応する秘密鍵を用いて復号化処理を行う。
【００４４】
関数計算部１２１は、ハッシュ関数等の各種関数の計算を行う。
【００４５】
以上に記載した受信者側装置１１０は、例えば、図５（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【００４６】
例えば、入力部１１１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、演算部１１２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１３０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１３１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１３２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４７】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４８】
図６は、送信者側装置１５０の概略図である。図示するように、送信者側装置１５０は、情報を入力する入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置１５０の各部の制御を行う演算部１５２と、記憶部１６０と、ネットワーク１９０を介して受信者側装置１１０と通信を行う通信部１６１と、情報を出力する出力部１６２と、を備える。
【００４９】
演算部１５２は、乱数を生成する乱数生成部１５３と、暗号化処理を行う暗号化部１５４と、を備える。
【００５０】
図７は、暗号化部１５４の概略図である。図示するように、暗号化部１５４は、第１暗号化部１５５と、第２暗号化部１５６と、関数計算部１５８と、を備える。
【００５１】
第１暗号化部１５５は、第１公開鍵暗号プロトコルΠにより、当該第１公開鍵暗号プロトコルΠで生成された公開鍵を用いて、暗号化する処理を行う。
【００５２】
第２暗号化部１５６は、第２公開鍵暗号プロトコルＰＫＥｉにより、当該第２公開鍵暗号プロトコルＰＫＥｉの公開鍵を用いて、暗号化する処理を行う。
【００５３】
なお、第２暗号化部１５６は、ｎ個の暗号化実行部１５７−１，・・・，１５７ｎを有し、ｉに対応する暗号化実行部１５７−ｉが、ｉに対応する公開鍵を用いて暗号化処理を行う。
【００５４】
関数計算部１５８は、ハッシュ関数等の各種関数の計算を行う。
【００５５】
以上に記載した送信者側装置１５０は、例えば、図５に示すような一般的なコンピュータ９００で実現できる。
【００５６】
例えば、入力部１５１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、演算部１５２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１６０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１６１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１６２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００５７】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００５８】
図８は、第一の実施形態における暗号処理を示すフロー図である。
【００５９】
［受信者側装置１１０での鍵生成処理］
受信者側装置１１０は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付ける（Ｓ１０）。
【００６０】
次に、鍵情報生成部１１３の第１鍵生成部１１４が、第１公開鍵暗号プロトコルΠの鍵生成手段Ｋを用いて、
【００６１】
【数１１】
【００６２】
により公開鍵ｐｋ及び秘密鍵ｓｋを生成する（Ｓ１１）。
【００６３】
次に、鍵情報生成部１１３の第２鍵生成部１１５が、ｉに対応する鍵生成実行部１１６−ｉを用いて、
【００６４】
【数１２】
【００６５】
により公開鍵ＰＫｉ及び秘密鍵ＳＫｉを各々生成する（Ｓ１２）。
【００６６】
そして、鍵情報生成部１１３は、
【００６７】
【数１３】
【００６８】
とする公開鍵ＰＫ及び秘密鍵ＳＫを生成する（Ｓ１３）。但し、Ｆｉ（１≦ｉ≦ｎ）は、
【００６９】
【数１４】
【００７０】
なる関数族とする。なお、Ｎは自然数である。
【００７１】
また、受信者側装置１１０の演算部１１２は、公開鍵ＰＫを、ネットワーク１９０その他の搬送手段を介して取得できるように公開する（Ｓ１４）。
【００７２】
［送信者側装置１５０での暗号化処理］
まず、送信者側装置１５０の演算部１５２は、入力部１５１又は通信部１６１を介して、受信者側装置１１０より公開鍵ＰＫを取得する（Ｓ１５）。
【００７３】
また、演算部１５２は、入力部１５１又は通信部１６１を介して、メッセージ文Ｍの入力を受け付ける（Ｓ１６）。
【００７４】
そして、演算部１５２の乱数生成部１５３が、
【００７５】
【数１５】
【００７６】
をランダムに選ぶ（Ｓ１７）。
【００７７】
さらに、演算部１５２の第２暗号化部１５２が、ｉに対応する暗号化実行部１５７−ｉを用いて、公開鍵ＰＫｉより、
【００７８】
【数１６】
【００７９】
を生成する（Ｓ１８）。
【００８０】
さらに、演算部１５２の第１暗号化部１５５が、公開鍵ｐｋ及び第１公開鍵暗号プロトコルΠの暗号化手段Ｅを用いて、
【００８１】
【数１７】
【００８２】
を生成する（Ｓ１９）。ここで、第１暗号化部１５５は、ランダムオラクルＯ１，・・・，Ｏｎの代わりに、関数計算部１５８を用いることにより、
【００８３】
【数１８】
【００８４】
の関数による計算を行う。
【００８５】
そして、送信者側装置１５０の演算部１５２は、
【００８６】
【数１９】
【００８７】
をメッセージ文Ｍに対する暗号文として、通信部１６１又は出力部１６２を介して、受信者側装置１１０に出力する（Ｓ２０）。
【００８８】
［受信者側装置１１０での復号化処理］
受信者側装置１１０の演算部１１２は、入力部１１１又は通信部１３１を介して、送信者側装置１５０より暗号文Ｃを取得する（Ｓ２１）。
【００８９】
次に、復号化部１１７の第２復号化部１１９が、ｉに対応する復号化実行部１２０−ｉを用いて、秘密鍵ＳＫｉより、
【００９０】
【数２０】
【００９１】
を計算する（Ｓ２２）。
【００９２】
さらに、復号化部１１７の第１復号化部１１８が、第１公開鍵暗号プロトコルΠの復号化手段Ｄを用いて、秘密鍵ｓｋより、
【００９３】
【数２１】
【００９４】
を計算する（Ｓ２３）。ここで、第１復号化部１１８は、ランダムオラクルＯ１，・・・，Ｏｎの代わりに、関数計算部１２１を用いることにより、
【００９５】
【数２２】
【００９６】
の関数による計算を行う。
【００９７】
そして、受信者側装置１１０の演算部１１２は、Ｍ’を暗号文Ｃに対するメッセージ文として取得する。
【００９８】
本第１の実施形態において、関数族Ｆｉが条件「いかなる攻撃者も、シードσｉ自体を得ることなく、真のランダム関数とｆσｉｉを区別することが難しい」を満たし、かつ、第１公開鍵暗号プロトコルΠが条件「任意の関数を利用した復号オラクルへアクセスすることができるが、ランダムオラクルへの直接的アクセスを許されない如何なる攻撃者に対しても識別不能性が満たされる」を満たすとき、第３公開鍵暗号プロトコルΠ’はＩＮＤ−ＣＣＡ２安全であることが証明される。
【００９９】
なお、識別不能性やIND-CCA2安全の定義・詳細については、下記の非特許文献５に詳細に記載されている。
【０１００】
非特許文献５：M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. “Ｒelations among notions of security for public-key encryption schemes”, June 2001, http://www.cs.ucsd.edu/users/ mihir/papers/relations.html
＜第２の実施形態＞
次に、第２の実施形態について説明する。本発明の第２の実施形態は、第１の実施形態と比較して、受信者側装置２１０及び送信者側装置２５０が異なっているため、以下、これらの異なっている点に関連する事項について説明する。
【０１０１】
図９は、受信者側装置２１０の概略図である。図示するように、受信者側装置２１０は、入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置２１０の各部の制御を行う演算部２１２と、記憶部１３０と、ネットワーク１９０を介して送信者側装置２５０と通信を行う通信部１３１と、情報を出力する出力部１３２と、を備え、第一の実施形態と比較して演算部２１２が異なるため、以下、演算部２１２について説明する。
【０１０２】
演算部２１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部２１３と、復号化処理を行う復号化部２１７と、を有する。
【０１０３】
図１０は、鍵情報生成部２１３の概略図である。図示するように、鍵情報生成部２１３は、第１落とし戸付き一方向性関数生成部２１４と、第２落とし戸付き一方向性関数生成部２１５と、を備える。
【０１０４】
第１落とし戸付き一方向性関数生成部２１４は、一方向性関数と落とし戸の対を生成する。
【０１０５】
第２落とし戸付き一方向性関数生成部２１５は、第１落とし戸付き一方向性関数生成部２１４とは異なる一方向性関数と落とし戸の対を生成する。
【０１０６】
図１１は、復号化部２１７の概略図である。図示するように、復号化部２１７は、第１復号化部２１８と、第２復号化部２１９と、関数計算部２２０と、検査部２２１と、を備える。
【０１０７】
第１復号化部２１８は、第１落とし戸付き一方向性関数生成部２１４で生成された落とし戸π−１１を用いた演算を行う。
【０１０８】
第２復号化部２１９は、第２落とし戸付き一方向性関数生成部２１５で生成された落とし戸π−１２を用いた演算を行う。
【０１０９】
関数計算部２２０は、ハッシュ関数等の各種関数の計算を行う。
【０１１０】
検査部２２１は、復号化部２１７で復号されたメッセージの検証を行う。
【０１１１】
図１２は、送信者側装置１５０の概略図である。図示するように、送信者側装置２５０は、情報を入力する入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置２５０の各部の制御を行う演算部２５２と、記憶部１６０と、ネットワーク１９０を介して受信者側装置１１０と通信を行う通信部１６１と、情報を出力する出力部１６２と、を備え、第１の実施形態と比較して、演算部２５２が異なっているため、以下、演算部２５２に関連する事項について説明する。
【０１１２】
演算部２５２は、乱数を生成する乱数生成部２５３と、暗号化処理を行う暗号化部２５４と、を備える。
【０１１３】
図１３は、暗号化部２５４の概略図である。図示するように、暗号化部２５４は、第１暗号化部２５５と、第２暗号化部２５６と、関数計算部２５８と、を備える。
【０１１４】
第１暗号化部１５５は、受信者側装置２１０の第１落とし戸付き一方向性関数生成部２１４で生成された一方向性関数π１を用いた演算を行う。
【０１１５】
第２暗号化部１５６は、受信者側装置２１０の第２落とし戸付き一方向性関数生成部２１５で生成された一方向性関数π２を用いた演算を行う。
【０１１６】
関数計算部２５７は、ハッシュ関数等の各種関数の計算を行う。
【０１１７】
図１４は、第２の実施形態における暗号処理を示すフロー図である。
【０１１８】
［受信者側装置２１０での鍵生成処理］
受信者側装置２１０は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付ける（Ｓ３０）。
【０１１９】
次に、鍵情報生成部２１３の第１落とし戸付き一方向性関数生成部２１４及び第２落とし戸付き一方向性関数生成部２１５が、
【０１２０】
【数２３】
【０１２１】
により一方向性関数と落とし戸の対（π１，π−１１）、（π２，π−１２）を生成する（Ｓ３１）。ここで、Ｇは確率的アルゴリズムである。
【０１２２】
そして、鍵情報生成部２１３は、
【０１２３】
【数２４】
【０１２４】
とする公開鍵ＰＫ及び秘密鍵ＳＫを生成する（Ｓ３２）。但し、Ｒは、有限集合、Ｆｉ（１≦ｉ≦２）は、
【０１２５】
【数２５】
【０１２６】
なる関数族とする。なお、Ｎは自然数である。
【０１２７】
また、受信者側装置２１０の演算部２１２は、公開鍵ＰＫを、ネットワーク１９０その他の搬送手段を介して取得できるように公開する（Ｓ３３）。
【０１２８】
［送信者側装置２５０での暗号化処理］
まず、送信者側装置２５０の演算部２５２は、入力部１５１又は通信部１６１を介して、受信者側装置３１０より公開鍵ＰＫを取得する（Ｓ３４）。
【０１２９】
また、演算部２５２は、入力部２５１又は通信部２６１を介して、メッセージ文Ｍの入力を受け付ける（Ｓ３５）。
【０１３０】
そして、演算部２５２の乱数生成部２５３が、
【０１３１】
【数２６】
【０１３２】
をランダムに選ぶ（Ｓ３６）。
【０１３３】
さらに、演算部２５２の第１暗号化部２５５及び第２暗号化部２５６が、公開鍵ＰＫの一方向性関数π１、π２をそれぞれ用いて、
【０１３４】
【数２７】
【０１３５】
を生成する（Ｓ３７）。
【０１３６】
さらに、暗号化部２５４が、関数計算部２５７を用いて、
【０１３７】
【数２８】
【０１３８】
を生成する（Ｓ３８）。
【０１３９】
そして、送信者側装置２５０の演算部２５２は、
【０１４０】
【数２９】
【０１４１】
をメッセージ文Ｍに対する暗号文として、通信部１６１又は出力部１６２を介して、受信者側装置２１０に出力する（Ｓ３９）。
【０１４２】
［受信者側装置２１０での復号化処理］
受信者側装置２１０の演算部２１２は、入力部１１１又は通信部１３１を介して、送信者側装置２５０より暗号文Ｃを取得する（Ｓ４０）。
【０１４３】
次に、復号化部２１７の第１復号化部２１８及び第２復号化部１１９が、秘密鍵ＳＫの落とし戸π１−１、π２−１をそれぞれ用いて、
【０１４４】
【数３０】
【０１４５】
を計算する（Ｓ４１）。
【０１４６】
さらに、復号化部２１７が関数計算部２２０を用いて、
【０１４７】
【数３１】
【０１４８】
を計算する（Ｓ４２）。
【０１４９】
また、復号化部２１７が関数計算部２２０を用いて、
【０１５０】
【数３２】
【０１５１】
を計算する（Ｓ４３）。
【０１５２】
そして、復号化部２１７の検査部２２１が、ステップＳ４３で計算したｖ２を検査する（Ｓ４４）。そして、検査に成功すれば、演算部２１２は、ステップＳ３１で算出されたＭを暗号文Ｃに対するメッセージ文として取得する。
【０１５３】
第二の実施形態の方法は、非特許文献１に記載の公開鍵暗号方法をベースに変形した後、第一の実施形態の方法を適用した。本発明の方法によると、関数族Ｆｉ（１≦ｉ≦２）が条件「いかなる攻撃者も、シードσｉ自体を得ることなく、真のランダム関数とｆσｉｉを区別することが難しい」を満たすとき、上記公開鍵暗号はＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１５４】
以上の第一の実施形態及び第二の実施形態では、受信者側装置１１０、２１０及び送信者側装置１５０、２５０の間で暗号通信を行う例を示したが、このような態様に限定されるわけではなく、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、の他、ファイル暗号システムなど様々なシステムに適用することが可能である。
【０１５５】
また、第一の実施形態及び第二の実施形態における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われる他、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。
【０１５６】
さらに、上述した実施形態においては、受信者側装置１１０、２１０で公開鍵及び秘密鍵を生成したが、このような態様に限定されず、他の装置（例えば、鍵生成装置）の演算部が、入力部を介して、１ｋ（ｋはセキュリティパラメータ）の入力を受け付けて、第３公開鍵暗号プロトコルΠ’における公開鍵ＰＫ及び秘密鍵ＳＫを生成し、公開鍵ＰＫを送信者側装置１５０、２５０に出力し（公開し）、秘密鍵ＳＫを受信者側装置１１０、２１０に（安全な方法で）出力するようにしてもよい。
【図面の簡単な説明】
【０１５７】
【図１】暗号システムの概略図。
【図２】受信者側装置の概略図。
【図３】鍵情報生成部の概略図。
【図４】復号化部の概略図。
【図５】コンピュータの概略図。
【図６】送信者側装置の概略図。
【図７】暗号化部の概略図。
【図８】暗号通信を示すフロー図。
【図９】受信者側装置の概略図。
【図１０】鍵情報生成部の概略図。
【図１１】復号化部の概略図。
【図１２】送信者側装置の概略図。
【図１３】暗号化部の概略図。
【図１４】暗号通信を示すフロー図。
【符号の説明】
【０１５８】
１００ 暗号システム
１１０、２１０ 受信者側装置
１１１ 入力部
１１２、２１２ 演算部
１１３、２１３ 鍵情報生成部
１１７、２１７ 復号化部
１３０ 記憶部
１３１ 通信部
１３２ 出力部
１５０、２５０ 送信者側装置
１５１ 入力部
１５２、２５２ 演算部
１５３、２５３ 乱数生成部
１５４、２５４ 暗号化部
１６０ 記憶部
１６１ 通信部
１６２ 出力部
【特許請求の範囲】
【請求項１】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数３】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数４】
なる関数族とする。）と、を有する鍵生成処理を行い、
前記送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【数５】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数６】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数７】
を作成する処理と、
【数８】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数９】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数１０】
を計算する処理と、を有する復号化処理を行うこと、
を特徴とする暗号システム。
【請求項２】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数１１】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数１２】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数１３】
なる関数族とする。）と、を有する鍵生成処理を行い、
送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【数１４】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数１５】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数１６】
を計算する処理と、
【数１７】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数１８】
を計算する処理と、
前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数１９】
を計算する処理と、を有する復号化処理を行うこと、
を特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
前記受信者側装置の演算部は、
【数２０】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とすること、
を特徴とする暗号システム。
【請求項４】
請求項１又は２に記載の暗号システムであって、
鍵生成装置を備え、
前記鍵生成処理を、前記受信者側装置に代わって、前記鍵生成装置の演算部が行うこと、
を特徴とする暗号システム。
【請求項５】
暗号化鍵及び復号化鍵を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数２１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２２】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数２３】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数２４】
なる関数族とする。）と、を行う演算部を備えること、
を特徴とする鍵生成装置。
【請求項６】
暗号化鍵及び復号化鍵を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数２５】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数２６】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数２７】
なる関数族とする。）と、を行う演算部を備えること、
を特徴とする鍵生成装置。
【請求項７】
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数２８】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２９】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数３０】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数３１】
なる関数族とする。）と、
前記送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（３２）〜（３５）式を用いて生成された暗号文Ｃを取得する処理と、
【数３２】
【数３３】
【数３４】
【数３５】
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数３６】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数３７】
を計算する処理と、を行う演算部を備えること、
を特徴とする受信者側装置。
【請求項８】
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数３８】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数３９】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数４０】
なる関数族とする。）と、を行い、
送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（４１）〜（４４）式を用いて生成された暗号文Ｃを取得する処理と、
【数４１】
【数４２】
【数４３】
【数４４】
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数４５】
を計算する処理と、
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数４６】
を計算する処理と、を行う演算部を備えること、
を特徴とする受信者側装置。
【請求項９】
請求項８に記載の受信者側装置であって、
前記演算部は、
【数４７】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とすること、
を特徴とする受信者側装置。
【請求項１０】
暗号化鍵を用いてメッセージを暗号化する送信者側装置であって、
セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋ、および、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、下記の（４８）〜（５１）式により生成された暗号化鍵ＰＫを取得する処理と、
【数４８】
【数４９】
【数５０】
【数５１】
メッセージ文Ｍの入力を受け付ける処理と、
【数５２】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数５３】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数５４】
を作成する処理と、
【数５５】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算部を備えること、
を特徴とする送信者側装置。
【請求項１１】
暗号化鍵を用いてメッセージを暗号化する送信者側装置であって、
セキュリティパラメータｋの入力を受け付け、落し戸付き一方向性関数生成手段Ｇ1，Ｇ2、および、有限集合Ｒを用いて、下記の（５６）〜（５８）式により生成された暗号化鍵ＰＫを取得する処理と、
【数５６】
【数５７】
【数５８】
メッセージ文Ｍの入力を受け付ける処理と、
【数５９】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数６０】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数６１】
を計算する処理と、
【数６２】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算部を備えること、
を特徴とする送信者側装置。
【請求項１２】
コンピュータを、
暗号化鍵及び復号化鍵を生成する鍵生成装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数６３】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数６４】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数６５】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数６６】
なる関数族とする。）と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１３】
コンピュータを、
暗号化鍵及び復号化鍵を生成する鍵生成装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数６７】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数６８】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数６９】
なる関数族とする。）と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１４】
コンピュータを、
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数７０】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数７１】
により、前記第２暗号プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数７２】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数７３】
なる関数族とする。）と、
前記送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（７４）〜（７７）式を用いて生成された暗号文Ｃを取得する処理と、
【数７４】
【数７５】
【数７６】
【数７７】
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数７８】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数７９】
を計算する処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１５】
コンピュータを、
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数８０】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数８１】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数８２】
なる関数族とする。）と、を行い、
送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（８３）〜（８６）式を用いて生成された暗号文Ｃを取得する処理と、
【数８３】
【数８４】
【数８５】
【数８６】
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数８７】
を計算する処理と、
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数８８】
を計算する処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１６】
請求項１５に記載のプログラムであって、
前記演算手段に、
【数８９】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とさせること、
を特徴とするプログラム。
【請求項１７】
コンピュータを、
暗号化鍵を用いてメッセージを暗号化して生成した暗号文を受信者側装置に送信する送信者側装置として機能させるプログラムであって、
前記コンピュータを、
前記受信者側装置において、セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋ、および、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、下記の（９０）〜（９３）式により生成された暗号化鍵ＰＫを取得する処理と、
【数９０】
【数９１】
【数９２】
【数９３】
メッセージ文Ｍの入力を受け付ける処理と、
【数９４】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数９５】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数９６】
を作成する処理と、
【数９７】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１８】
コンピュータを、
暗号化鍵を用いてメッセージを暗号化する送信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付け、落し戸付き一方向性関数生成手段Ｇ1，Ｇ2、および、有限集合Ｒを用いて、下記の（９８）〜（１００）式により生成された暗号化鍵ＰＫを取得する処理と、
【数９８】
【数９９】
【数１００】
メッセージ文Ｍの入力を受け付ける処理と、
【数１０１】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数１０２】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数１０３】
を計算する処理と、
【数１０４】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１９】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムにおける暗号通信方法であって、
前記受信者側装置の演算部が、セキュリティパラメータｋの入力を受け付ける処理を行う過程と、
前記受信者側装置の演算部が、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数１０５】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理を行う過程と、
前記受信者側装置の演算部が、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数１０６】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理を行う過程と、
前記受信者側装置の演算部が、
【数１０７】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理を行う過程（但し、Ｆｉは、
【数１０８】
なる関数族とする。）と、
前記送信者側装置の演算部が、メッセージ文Ｍの入力を受け付ける処理を行う過程と、
前記送信者側装置の演算部が、
【数１０９】
をランダムに選ぶ処理を行う過程と、
前記送信者側装置の演算部が、前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数１１０】
を作成する処理を行う過程と、
前記送信者側装置の演算部が、前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数１１１】
を作成する処理を行う過程と、
前記送信者側装置の演算部が、
【数１１２】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理を行う過程と、
前記受信者側装置の演算部が、取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数１１３】
を計算する処理を行う過程と、
前記受信者側装置の演算部が、前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数１１４】
を計算する処理を行う過程と、を備えること、
を特徴とする暗号通信方法。
【請求項１】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数３】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数４】
なる関数族とする。）と、を有する鍵生成処理を行い、
前記送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【数５】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数６】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数７】
を作成する処理と、
【数８】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数９】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数１０】
を計算する処理と、を有する復号化処理を行うこと、
を特徴とする暗号システム。
【請求項２】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムであって、
前記受信者側装置の演算部が、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数１１】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数１２】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数１３】
なる関数族とする。）と、を有する鍵生成処理を行い、
送信者側装置の演算部が、
メッセージ文Ｍの入力を受け付ける処理と、
【数１４】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数１５】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数１６】
を計算する処理と、
【数１７】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を有する暗号化処理を行い、
前記受信者側装置の演算部が、
前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数１８】
を計算する処理と、
前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数１９】
を計算する処理と、を有する復号化処理を行うこと、
を特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
前記受信者側装置の演算部は、
【数２０】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とすること、
を特徴とする暗号システム。
【請求項４】
請求項１又は２に記載の暗号システムであって、
鍵生成装置を備え、
前記鍵生成処理を、前記受信者側装置に代わって、前記鍵生成装置の演算部が行うこと、
を特徴とする暗号システム。
【請求項５】
暗号化鍵及び復号化鍵を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数２１】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２２】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数２３】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数２４】
なる関数族とする。）と、を行う演算部を備えること、
を特徴とする鍵生成装置。
【請求項６】
暗号化鍵及び復号化鍵を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数２５】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数２６】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数２７】
なる関数族とする。）と、を行う演算部を備えること、
を特徴とする鍵生成装置。
【請求項７】
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数２８】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数２９】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数３０】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数３１】
なる関数族とする。）と、
前記送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（３２）〜（３５）式を用いて生成された暗号文Ｃを取得する処理と、
【数３２】
【数３３】
【数３４】
【数３５】
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数３６】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数３７】
を計算する処理と、を行う演算部を備えること、
を特徴とする受信者側装置。
【請求項８】
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数３８】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数３９】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数４０】
なる関数族とする。）と、を行い、
送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（４１）〜（４４）式を用いて生成された暗号文Ｃを取得する処理と、
【数４１】
【数４２】
【数４３】
【数４４】
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数４５】
を計算する処理と、
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数４６】
を計算する処理と、を行う演算部を備えること、
を特徴とする受信者側装置。
【請求項９】
請求項８に記載の受信者側装置であって、
前記演算部は、
【数４７】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とすること、
を特徴とする受信者側装置。
【請求項１０】
暗号化鍵を用いてメッセージを暗号化する送信者側装置であって、
セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋ、および、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、下記の（４８）〜（５１）式により生成された暗号化鍵ＰＫを取得する処理と、
【数４８】
【数４９】
【数５０】
【数５１】
メッセージ文Ｍの入力を受け付ける処理と、
【数５２】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数５３】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数５４】
を作成する処理と、
【数５５】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算部を備えること、
を特徴とする送信者側装置。
【請求項１１】
暗号化鍵を用いてメッセージを暗号化する送信者側装置であって、
セキュリティパラメータｋの入力を受け付け、落し戸付き一方向性関数生成手段Ｇ1，Ｇ2、および、有限集合Ｒを用いて、下記の（５６）〜（５８）式により生成された暗号化鍵ＰＫを取得する処理と、
【数５６】
【数５７】
【数５８】
メッセージ文Ｍの入力を受け付ける処理と、
【数５９】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数６０】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数６１】
を計算する処理と、
【数６２】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算部を備えること、
を特徴とする送信者側装置。
【請求項１２】
コンピュータを、
暗号化鍵及び復号化鍵を生成する鍵生成装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数６３】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数６４】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数６５】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数６６】
なる関数族とする。）と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１３】
コンピュータを、
暗号化鍵及び復号化鍵を生成する鍵生成装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数６７】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数６８】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数６９】
なる関数族とする。）と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１４】
コンピュータを、
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数７０】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理と、
前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数７１】
により、前記第２暗号プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理と、
【数７２】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｆｉは、
【数７３】
なる関数族とする。）と、
前記送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（７４）〜（７７）式を用いて生成された暗号文Ｃを取得する処理と、
【数７４】
【数７５】
【数７６】
【数７７】
取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数７８】
を計算する処理と、
前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数７９】
を計算する処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１５】
コンピュータを、
送信者側装置が暗号化鍵を用いてメッセージを暗号化した暗号文を受信し、復号する受信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付ける処理と、
落し戸付き一方向性関数生成手段Ｇ1，Ｇ2を用いて、
【数８０】
により一方向性関数および落し戸の対（π１,π−１１）、（π２,π−１２）を作成する処理と、
【数８１】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理（但し、Ｒは有限集合、Ｆ１、Ｆ２は、
【数８２】
なる関数族とする。）と、を行い、
送信者側装置において、前記暗号化鍵ＰＫ、前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉ、および、前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、メッセージ文Ｍから下記の（８３）〜（８６）式を用いて生成された暗号文Ｃを取得する処理と、
【数８３】
【数８４】
【数８５】
【数８６】
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数８７】
を計算する処理と、
取得した前記暗号文Ｃ及び前記復号化鍵ＳＫを用いて、
【数８８】
を計算する処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１６】
請求項１５に記載のプログラムであって、
前記演算手段に、
【数８９】
が成立すれば、前記Ｍ’を暗号文Ｃに対するメッセージ文とさせること、
を特徴とするプログラム。
【請求項１７】
コンピュータを、
暗号化鍵を用いてメッセージを暗号化して生成した暗号文を受信者側装置に送信する送信者側装置として機能させるプログラムであって、
前記コンピュータを、
前記受信者側装置において、セキュリティパラメータｋの入力を受け付け、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋ、および、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、下記の（９０）〜（９３）式により生成された暗号化鍵ＰＫを取得する処理と、
【数９０】
【数９１】
【数９２】
【数９３】
メッセージ文Ｍの入力を受け付ける処理と、
【数９４】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数９５】
を作成する処理と、
前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数９６】
を作成する処理と、
【数９７】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１８】
コンピュータを、
暗号化鍵を用いてメッセージを暗号化する送信者側装置として機能させるプログラムであって、
前記コンピュータを、
セキュリティパラメータｋの入力を受け付け、落し戸付き一方向性関数生成手段Ｇ1，Ｇ2、および、有限集合Ｒを用いて、下記の（９８）〜（１００）式により生成された暗号化鍵ＰＫを取得する処理と、
【数９８】
【数９９】
【数１００】
メッセージ文Ｍの入力を受け付ける処理と、
【数１０１】
をランダムに選ぶ処理と、
前記暗号化鍵ＰＫを用いて、
【数１０２】
を計算する処理と、
前記暗号化鍵ＰＫを用いて、
【数１０３】
を計算する処理と、
【数１０４】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理と、を行う演算手段として機能させること、
を特徴とするプログラム。
【請求項１９】
送信者側装置が暗号化鍵を用いてメッセージを暗号化して暗号文を生成し、受信者側装置が復号化鍵を用いて当該暗号文を復号する暗号システムにおける暗号通信方法であって、
前記受信者側装置の演算部が、セキュリティパラメータｋの入力を受け付ける処理を行う過程と、
前記受信者側装置の演算部が、ランダム関数Ｏ１，・・・，Ｏｎ（ｎは自然数）のオラクルアクセス(以下、ランダムオラクルと呼ぶ)の利用を前提とした第１暗号プロトコルΠ＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の鍵生成手段Ｋを用いて、
【数１０５】
により、第１暗号プロトコルΠの暗号化鍵ｐｋ及び復号化鍵ｓｋを作成する処理を行う過程と、
前記受信者側装置の演算部が、前記第１暗号プロトコルΠとは異なり、ランダムオラクルに依存しない第２暗号プロトコルＰＫＥｉ＝（Ｋｇｉ，Ｅｎｃｉ，Ｄｅｃｉ）（ｉは、１≦ｉ≦ｎなる自然数）の鍵生成手段Ｋｇｉを用いて、
【数１０６】
により、前記第２暗号方法プロトコルＰＫＥｉの暗号化鍵ＰＫｉ及び復号化鍵ＳＫｉを作成する処理を行う過程と、
前記受信者側装置の演算部が、
【数１０７】
により生成された暗号化鍵ＰＫ及び復号化鍵ＳＫを第３暗号プロトコルΠ’の暗号化鍵及び復号化鍵とする処理を行う過程（但し、Ｆｉは、
【数１０８】
なる関数族とする。）と、
前記送信者側装置の演算部が、メッセージ文Ｍの入力を受け付ける処理を行う過程と、
前記送信者側装置の演算部が、
【数１０９】
をランダムに選ぶ処理を行う過程と、
前記送信者側装置の演算部が、前記暗号化鍵ＰＫ及び前記第２暗号プロトコルＰＫＥｉの暗号化手段Ｅｎｃｉを用いて、
【数１１０】
を作成する処理を行う過程と、
前記送信者側装置の演算部が、前記暗号化鍵ＰＫ及び前記第１暗号プロトコルΠの暗号化手段Ｅを用いて、
【数１１１】
を作成する処理を行う過程と、
前記送信者側装置の演算部が、
【数１１２】
を前記メッセージ文Ｍに対する暗号文Ｃとする処理を行う過程と、
前記受信者側装置の演算部が、取得した前記暗号文Ｃ、前記復号化鍵ＳＫ、および、前記第２暗号プロトコルＰＫＥｉの復号手段Ｄｅｃｉを用いて、
【数１１３】
を計算する処理を行う過程と、
前記受信者側装置の演算部が、前記第１暗号プロトコルΠの復号手段Ｄを用いて、
【数１１４】
を計算する処理を行う過程と、を備えること、
を特徴とする暗号通信方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−７４６８６（Ｐ２０１０−７４６８６Ａ）
【公開日】平成２２年４月２日（２０１０．４．２）
【国際特許分類】
【出願番号】特願２００８−２４１９３０（Ｐ２００８−２４１９３０）
【出願日】平成２０年９月２２日（２００８．９．２２）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２２年４月２日（２０１０．４．２）
【国際特許分類】
【出願日】平成２０年９月２２日（２００８．９．２２）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]