暗号化システム、公開鍵暗号化方法、鍵生成装置、計算機および公開鍵秘密鍵生成プログラム
【課題】ランダム関数へのオラクルアクセスに基づく公開鍵暗号方法を用いて、標準計算機モデル上で適応的選択暗号文攻撃に対して安全（ＩＮＤ−ＣＣＡ２安全）な公開鍵暗号方法Π'を与えるための方法を提供する。
【解決手段】鍵生成装置、暗号化装置、および、暗号化システムであって、鍵生成装置は、鍵生成部を備え、鍵生成部は、鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数と落とし戸とから、二つの対を生成し、関数族を生成し、生成された二つの対と、関数族とを用いて、暗号化鍵ＰＫと復号化鍵ＳＫとを生成することを特徴とする。このようにして得られた公開鍵暗号において、公開鍵暗号Πおよび関数族がある一定の安全性を満たすとき、公開鍵暗号Π'はＩＮＤ−ＣＣＡ２安全であることが示される。
【解決手段】鍵生成装置、暗号化装置、および、暗号化システムであって、鍵生成装置は、鍵生成部を備え、鍵生成部は、鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数と落とし戸とから、二つの対を生成し、関数族を生成し、生成された二つの対と、関数族とを用いて、暗号化鍵ＰＫと復号化鍵ＳＫとを生成することを特徴とする。このようにして得られた公開鍵暗号において、公開鍵暗号Πおよび関数族がある一定の安全性を満たすとき、公開鍵暗号Π'はＩＮＤ−ＣＣＡ２安全であることが示される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージを暗号化して通信を行う暗号システムに関する。
【背景技術】
【０００２】
公開鍵暗号は、公開鍵と秘密鍵との異なる鍵情報を用いて、データの暗号化・復号化を行う暗号技術のひとつである。公開鍵暗号は、「鍵生成」、「暗号化」及び「復号化」の３つの手段（アルゴリズムなど）から定義される。鍵生成手段とは、セキュリティパラメータ（例えば、鍵長を指定するパラメータ）を入力として、公開鍵と秘密鍵とを出力する手段である。暗号化手段とは、メッセージ文と公開鍵を入力として暗号文を出力する手段である。復号化手段とは、暗号文と秘密鍵とを入力としてメッセージ文を出力する手段である。
【０００３】
例えば、公開鍵暗号を暗号通信に利用する場合、鍵生成は受信者が行い、公開鍵のみを公開し、秘密鍵は安全な方法によって保持する。送信者は、メッセージ文を作成し、暗号化手段を用いて暗号化を行い、暗号文を受信者に送信する。受信者は、復号化手段を用いて暗号文の復号化を行う。
【０００４】
公開鍵暗号の安全性は、通常、標準計算機モデル、または、ランダムオラクルモデル（例えば、非特許文献１）上で与えられる。
【０００５】
標準計算機モデルとは、（対話型）チューリングマシンから構成されるモデルで、現実の計算機システムに近いものと考えられている。
【０００６】
一方、ランダムオラクルモデルでは、全てのパーティ（攻撃者を含む）がランダム関数へオラクルとしてアクセスすることが許されている（以下、このようなランダム関数をランダムオラクルと呼ぶ）。
【０００７】
現実のシステムにおいては、ランダムオラクルの部分は実用的なハッシュ関数に置き換えて利用される（このような方法論は、random oracle methodologyと呼ばれる）。このとき、ランダムオラクルモデル上における安全性証明は現実のシステムにおいては通用しなくなってしまうが、安全性の何らかの根拠を示すものと考えられている。
【０００８】
前述のように、ランダムオラクルモデルは観念論的なモデルであるが、実用性に優れた暗号プロトコルの設計が容易であるため、多くの暗号プロトコルが提案されている。
【０００９】
random oracle methodologyに関するネガティブな結果として、非特許文献２では、ランダムオラクルモデル上では安全であるが、ランダムオラクルのいかなる関数への置き換えに対しても安全ではない暗号プロトコルが存在することが示されている。また、非特許文献３では、RSA full-domain hash 署名は標準計算機モデル上で安全にはならないと考えられる根拠を示している。
【００１０】
一方、random oracle methodologyに関するポジティブな結果として、非特許文献４は、ランダムオラクルの性質の一部を満たすハッシュ関数の実現方法について記載している。非特許文献５では、非特許文献７に記載のOAEPにおけるランダムオラクルの関数への置き換えを考察している。非特許文献６では、非特許文献１に記載の公開鍵暗号方法において、ランダムオラクルのadaptive perfectly one-way hash functionへの置き換えを考察している。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, http://www.cse.ucsd.edu/ ~mihir/papers/ro.html
【非特許文献２】R. Canetti, O. Goldreich, and S. Halevi. Random Oracle Methodology, Revised,http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.Publications.html/
【非特許文献３】Y. Dodis, R.Oliveira, and K. Pietrzak. On the Generic Insecurity of Full-domain Hash, Advances in Cryptography -- CRYPTO2005, pp.449-466, Springer-Verlag, 2005
【非特許文献４】R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information, http://domino.research.ibm.com/comm/ research_projects.nsf/pages/security.Publications.html/
【非特許文献５】A. Boldyreva and M. Fischlin. On the Security of OAEP, http://www.cc.gatech.edu/~aboldyre/publications.html
【非特許文献６】O. Pandey, R. Pass, and V. Vaikuntanathan. Adaptive One-way Functions and Applications, Advances in Cryptography -- CRYPTO2008, pp.57-74, Springer-Verlag, 2008
【非特許文献７】M. Bellare and P. Rogaway. Optimal asymmetric encryption -- How to encrypt with RSA,http://cseweb.ucsd.edu/~mihir/ papers/oaep.html
【発明の概要】
【発明が解決しようとする課題】
【００１２】
前述のように、公開鍵暗号の安全性は、通常、ランダムオラクルモデル、または、標準計算機モデル上で与えられる。しかし、ランダムオラクルモデル上における公開鍵暗号方法と、標準計算機モデル上における公開鍵暗号方法とはそれぞれのモデルにおいて考察されるにとどまり、これらのモデル相互間において、安全性を考察することは行われていない。
【００１３】
本発明は、第三者から情報を秘匿するための暗号方法を安全かつ効率的に実現するため、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全性証明可能であり、かつ、暗号化および復号化の高速処理に優れた公開鍵暗号方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の代表的な一例を示せば以下の通りである。すなわち、暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、前記鍵生成部は、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納し、式（１）を満たす関数族Ｆiを生成し（但し、ｆiσiは、各σ1∈S1,k，σ2∈S2,kに対して、式（２）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、前記暗号化部は、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４）を計算し、当該計算結果を前記第２の記憶部に格納し、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（５）を計算し、当該計算結果を前記第２の記憶部に格納し、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（６）に示すように生成し、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、前記復号化部は、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７）を計算して、当該計算結果を前記第３の記憶部に格納し、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、式（９）を満たすか否かを判定し、前記式（９）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする。
【００１５】
【数１】
【００１６】
【数２】
【００１７】
【数３】
【００１８】
【数４】
【００１９】
【数５】
【００２０】
【数６】
【００２１】
【数７】
【００２２】
【数８】
【００２３】
【数９】
【発明の効果】
【００２４】
本発明によれば、標準計算機モデル上において安全性証明可能であり、かつ、実用的な公開鍵暗号を提供することが可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施形態における暗号システムの構成の一例を示す説明図である。
【図２】本発明の第１の実施形態の受信者側装置の構成の一例を示す説明図である。
【図３】本発明の第１の実施形態の鍵生成部の構成の一例を示す説明図である。
【図４】本発明の第１の実施形態の復号化部の構成の一例を示す説明図である。
【図５】本発明の第１の実施形態の受信者側装置のハードウェア構成の一例を示すブロック図である。
【図６】本発明の第１の実施形態の送信者側装置の構成の一例を示す説明図である。
【図７】本発明の第１の実施形態の暗号化部の構成の一例を示す説明図である。
【図８】本発明の第１の実施形態の暗号化・復号化処理を説明するフローチャートである。
【図９】本発明の第２の実施形態の暗号化・復号化処理を説明するフローチャートである。
【図１０】本発明の第３の実施形態の暗号化・復号化処理を説明するフローチャートである。
【発明を実施するための形態】
【００２６】
以下の実施形態においては、暗号プロトコルを公開鍵暗号プロトコルとして利用し、公開鍵を暗号化鍵とし、秘密鍵を復号化鍵として利用する例を説明するが、本発明はこのような態様に限定されるわけではない。
【００２７】
［第１の実施形態］
本発明の第１の実施形態では、標準計算機モデル上で証明可能安全性をもつ公開鍵暗号方法について述べる。
【００２８】
図１は、本発明の第１の実施形態における暗号システム１０の構成の一例を示す説明図である。
【００２９】
図１に示すように、暗号システム１０は、受信者側装置１００と送信者側装置２００とを備えており、これらはネットワーク３００を介して相互に情報を送受信することができる。
【００３０】
なお、暗号システム１０は、受信者側装置１００および送信者側装置２００を、それぞれ、一以上備えていてもよい。
【００３１】
図２は、本発明の第１の実施形態の受信者側装置１００の構成の一例を示す説明図である。
【００３２】
受信者側装置１００は、入力部１１０、演算部１２０、記憶部１３０、通信部１４０および出力部１５０を備える。
【００３３】
入力部１１０は、受信者側装置１００に情報を入力する。
【００３４】
演算部１２０は、論理演算、べき乗算、剰余演算、ハッシュ関数演算およびランダム関数演算を含む各種演算の実行、並びに、受信者側装置１００の各部の制御を行う。演算部１２０は、鍵生成部１２１および復号化部１２２を備える。
【００３５】
鍵生成部１２１は、公開鍵（暗号化鍵）および秘密鍵（復号化鍵）を生成する。復号化部１２２は、秘密鍵を用いて復号化処理を実行する。
【００３６】
記憶部１３０は、入力部１１０から入力された情報および演算部１２０の処理結果等を格納する。通信部１４０は、ネットワーク３００を介して送信者側装置２００と通信する。出力部１５０は、外部に情報を出力する。
【００３７】
図３は、本発明の第１の実施形態の鍵生成部１２１の構成の一例を示す説明図である。
【００３８】
鍵生成部１２１は、落とし戸付き一方向性関数生成部１２３および関数生成部１２４を備える。
【００３９】
落とし戸付き一方向性関数生成部１２３は、落とし戸付き一方向性関数（π）と落とし戸（π-1）との対を生成する。関数生成部１２４は、関数族Ｆiを生成する。
【００４０】
図４は、本発明の第１の実施形態の復号化部１２２の構成の一例を示す説明図である。
【００４１】
復号化部１２２は、関数計算部１２５、復号化処理部１２６および検査部１２７を備える。
【００４２】
関数計算部１２５は、ハッシュ関数等の各種関数の計算を実行する。復号化処理部１２６は、秘密鍵を用いて、入力された暗号文を復号化する。検査部１２７は、復号化処理部１２６によって復号化されたメッセージを検証する。
【００４３】
図５は、本発明の第１の実施形態の受信者側装置１００のハードウェア構成の一例を示すブロック図である。
【００４４】
受信者側装置１００は、例えば、図５に示すようなハードウェア構成からなる計算機によって実現される。
【００４５】
図５に示すように、受信者側装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）４００、メモリ４０１、外部記憶装置４０３、通信装置４０４、出力装置４０５、入力装置４０６および読書装置４０７を備える。
【００４６】
ＣＰＵ４００は、メモリ４０１上に展開されたプログラムを実行する。
【００４７】
メモリ４０１は、ＣＰＵ４００によって実行されるプログラムおよびＣＰＵ４００が処理を実行するために必要となる情報を格納する。また、メモリ４０１は、ＣＰＵ４００が処理を実行するためのワークエリアとしても用いられる。
【００４８】
外部記憶装置４０３は、ＣＰＵ４００によって実行される各種プログラムが格納される。また、処理に必要となる情報および処理結果等も格納される。
【００４９】
通信装置４０４は、ネットワークを介して他の装置と通信するための装置である。通信装置は、例えばＮＩＣ（Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｃａｒｄ）等が考えられる。
【００５０】
出力装置４０５は、ＣＰＵ４００によって実行された処理の結果を出力するための装置である。出力装置４０５は、例えば、ディスプレイ等が考えられる。
【００５１】
入力装置４０６は、受信者側装置１００に情報を入力するための装置である。入力装置４０６は、例えば、キーボード又はマウスなどが考えられる。
【００５２】
読書装置４０７は、可搬性を有する記憶媒体４０８から情報を読み出したり、又は、情報を書き込んだりするための装置である。なお、記憶媒体４０８としては、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）又はＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）等が考えられる。
【００５３】
受信者側装置１００が備える各構成を実現する方法としては、例えば、入力部１１０は、ＣＰＵ４００が入力装置４０６を利用することによって実現でき、演算部１２０は、外部記憶装置４０３に格納される所定のプログラムをメモリ４０１にロードしてＣＰＵ４００が実行することによって実現でき、記憶部１３０は、ＣＰＵ４００がメモリ４０１又は外部記憶装置４０３を利用することによって実現でき、通信部１４０は、ＣＰＵ４００が通信装置４０４を利用することによって実現でき、出力部１５０は、ＣＰＵ４００が出力装置４０５を利用することによって実現できる。
【００５４】
なお、受信者側装置１００が備える各構成は、プログラムとして実現されてもよいし、ハードウェアとして実現されてもよい。
【００５５】
メモリ４０１にロードされる所定のプログラムは、読書装置４０７を介して記憶媒体４０８から、又は、通信装置４０４を介してネットワークから、外部記憶装置４０３に格納され、その後、メモリ４０１上にロードされてＣＰＵ４００によって実行されるようにしてもよい。また、読書装置４０７を介して記憶媒体４０８から、又は、通信装置４０４を介してネットワークから、メモリ４０１上に直接ロードされ、ＣＰＵ４００によって実行されるようにしてもよい。
【００５６】
図６は、本発明の第１の実施形態の送信者側装置２００の構成の一例を示す説明図である。
【００５７】
送信者側装置２００は、入力部２１０、演算部２２０、記憶部２３０、通信部２４０および出力部２５０を備える。
【００５８】
入力部２１０は、送信者側装置２００に情報を入力する。
【００５９】
演算部２２０は、論理演算、べき乗算、剰余演算、ハッシュ関数演算およびランダム関数演算を含む各種演算の実行、並びに、送信者側装置２００の各部の制御を行う。演算部２２０は、乱数生成部２２１および暗号化部２２２を備える。
【００６０】
乱数生成部２２１は、処理に必要となる乱数を生成する。暗号化部２２２は、公開鍵を用いて暗号化処理を実行する。
【００６１】
記憶部２３０は、入力部２１０から入力された情報および演算部２２０の処理結果等を格納する。通信部２４０は、ネットワーク３００を介して受信者側装置１００と通信する。出力部２５０は、外部に情報を出力する。
【００６２】
図７は、本発明の第１の実施形態の暗号化部２２２の構成の一例を示す説明図である。
【００６３】
暗号化部２２２は、関数計算部２２３および暗号化処理部２２４を備える。
【００６４】
関数計算部２２３は、ハッシュ関数等の各種関数の計算を実行する。暗号化処理部２２４は、公開鍵を用いて入力されたメッセージ文を暗号化する。
【００６５】
図８は、本発明の第１の実施形態の暗号化・復号化処理を説明するフローチャートである。
【００６６】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０を介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ５００）。当該入力を受けた演算部１２０の鍵生成部１２１が処理を開始する。
【００６７】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との二つの対（π1，π1-1）および（π2，π2-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対を記憶部１３０に格納する（Ｓ５０１）。ここで、各１≦ｉ≦２について、πiは落とし戸付き一方向性関数を示し、πi-1は落とし戸を示す。
【００６８】
次に、鍵生成部１２１の関数生成部１２４は、式（１０）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ５０２）。
【００６９】
【数１０】
【００７０】
但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１１）を満たすものとする。
【００７１】
【数１１】
【００７２】
次に、鍵生成部１２１は、記憶部１３０に格納された落とし戸付き一方向性関数と落とし戸との対（π1，π1-1）および（π2，π2-1）と、関数族Ｆiとを用いて、式（１２）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ５０３）。
【００７３】
【数１２】
【００７４】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００その他の搬送手段を介して、他の装置が取得できるように公開される。
【００７５】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは、記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【００７６】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍ∈｛０，１｝k2および公開鍵ＰＫを取得する（Ｓ５１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【００７７】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【００７８】
まず、演算部２２０の乱数生成部２２１は、ｒ∈｛０，１｝k1と、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kとをランダムに選択し、選択されたｒ、σ1およびσ2を記憶部２３０に格納する（Ｓ５１１）。
【００７９】
次に、演算部２２０の暗号化部２２２は、取得された公開鍵ＰＫと、記憶部２３０に格納されるσ1およびσ2とを用いて式（１３）を計算し、当該計算結果を記憶部２３０に格納する（Ｓ５１２）。
【００８０】
【数１３】
【００８１】
具体的には、暗号化部２２２の関数計算部２２３が、公開鍵ＰＫ、σ1およびσ2を用いて式（１３）を計算する。
【００８２】
演算部２２０の暗号化部２２２は、記憶部２３０に格納される情報を用いて、式（１４）を計算し、計算結果を記憶部２３０に格納する（Ｓ５１３）。
【００８３】
【数１４】
【００８４】
ここで、暗号化部２２２の関数計算部２２３が関数ｆ１σ１とｆ２σ２とを計算する。
【００８５】
演算部２２０の暗号化部２２２は、記憶部２３０に格納された情報を用いて、Ｃ＝（ｕ1，ｕ2，ｒ，ｖ）を生成し、メッセージ文Ｍの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ５１４）。
【００８６】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃを取得する（Ｓ５２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【００８７】
復号化部１２２は、暗号文Ｃを以下の処理によって復号化する。
【００８８】
まず、復号化部１２２の復号化処理部１２６は、暗号文Ｃに含まれるｕ1およびｕ2と、秘密鍵ＳＫに含まれる落とし戸π1-1およびπ2-2とを用いて、式（１５）を計算し、計算結果を記憶部１３０に格納する（Ｓ５２１）。
【００８９】
【数１５】
【００９０】
復号化部１２２の関数計算部１２５は、記憶部１３０に格納されたデータを用いて、Ｍ∈｛０，１｝k2およびｚ∈｛０，１｝k3を式（１６）によって計算し、計算結果を記憶部１３０に格納する（Ｓ５２２）。
【００９１】
【数１６】
【００９２】
復号化部１２２の検査部１２７は、記憶部１３０に格納される計算結果を用いて、式（１７）が成立するか否かを検査する（Ｓ５２３）。
【００９３】
【数１７】
【００９４】
式（１７）を満たす、すなわち、検査に成功したと判定された場合、復号化部１２２は、暗号文Ｃのメッセージ文として出力部１５０からＭを出力する。
【００９５】
式（１７）を満たさない、すなわち、検査に失敗したと判定された場合、復号化部１２２は、出力部１５０からエラーを示すメッセージを出力する。
【００９６】
本実施形態で説明した公開鍵暗号方法は、非特許文献１に記載のランダムオラクルモデル上の公開鍵暗号方法をベースにして、標準計算機モデル上で安全となるように変換している。
【００９７】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、関数族Ｆi（ｉ＝１，２）がそれぞれ次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される（ＩＮＤ−ＣＣＡ２安全の詳細については、非特許文献１または非特許文献７に記載されている）。
【００９８】
「攻撃者は（１k，πi（σi），Ｆi,k）を入力として、関数族Ｆiへの攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問ｘに対して、Ｈｉ（ｘ）がリターンされる。
・オラクル２：質問（ｕ，ｘ）に対して、ｕ≠πi（σi）ならばｆｉσ’（ｘ）がリターンされる。但し、σ'＝πi-1（ｕ）、ｕ＝πi（σi）ならばエラーを示すメッセージがリターンされる。
このとき、攻撃者は関数Ｈｉがランダム関数なのか関数ｆｉσｉなのかを１／２よりもよい確率で推測することが難しい。」
【００９９】
［第２の実施形態］
第２の実施形態では、ランダムオラクルＯ1，…，Ｏnを利用する公開鍵暗号Π＝（Ｋ，Ｅ，Ｄ）をベースにして、ランダムオラクルに依存しない公開鍵暗号Π'＝（Ｋ'，Ｅ'，Ｄ'）を与える一般的方法について説明する。但し、公開鍵暗号プロトコルΠの鍵生成手段Ｋはランダムオラクルに依存しないものとする。
【０１００】
第２の実施形態における暗号システムは、第１の実施形態と同一であるため説明を省略する。また、受信者側装置１００および送信者側装置２００の構成についても第１の実施形態と同一であるため説明を省略する。
【０１０１】
以下、第１の実施形態との差異を中心に説明する。
【０１０２】
図９は、本発明の第２の実施形態の暗号化・復号化処理を説明するフローチャートである。
【０１０３】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０に介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ６００）。当該入力を受け付けた演算部１２０の鍵生成部１２１が処理を開始する。
【０１０４】
鍵生成部１２１は、公開鍵暗号プロトコルΠを用いて、公開鍵ｐｋおよび秘密鍵ｓｋを生成し、記憶部１３０に格納する（Ｓ６０１）。
【０１０５】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との対（π，π-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対（π，π-1）を記憶部１３０に格納する（Ｓ６０２）。ここで、πは落とし戸付き一方向性関数を示し、π-1は落とし戸を示す。
【０１０６】
鍵生成部１２１の関数計算部１２５は、式（１８）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ６０３）。
【０１０７】
【数１８】
【０１０８】
但し、各ｆｉσｉは、ランダム関数Ｏiと同一の定義域と、値域とを持つものとする。
【０１０９】
鍵生成部１２１は、公開鍵ｐｋおよび秘密鍵ｓｋと、落とし戸付き一方向性関数と落とし戸との対（π，π-1）と、関数族Ｆiとを用いて、式（１９）によってランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ６０４）。
【０１１０】
【数１９】
【０１１１】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００その他の搬送手段を介して、他の装置が取得できるように公開される。
【０１１２】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく、秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【０１１３】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍおよび公開鍵ＰＫを取得する（Ｓ６１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【０１１４】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【０１１５】
まず、演算部２２０の乱数生成部２２１は、σi∈Si,k（１≦ｉ≦n）をランダムに選択し、選択されたσiを記憶部２３０に格納する（Ｓ６１１）。
【０１１６】
演算部２２０の暗号化部２２２は、選択されたσiおよび公開鍵ＰＫに含まれる一方向性関数πを用いて式（２０）を計算し、計算結果を記憶部２３０に格納する（Ｓ６１２）。
【０１１７】
【数２０】
【０１１８】
具体的には、暗号化処理部２２４が式（２０）を計算する。
【０１１９】
演算部２２０の暗号化部２２２は、公開鍵ＰＫおよび公開鍵暗号プロトコルΠを用いて、式（２１）を計算し、計算結果を記憶部２３０に格納する（Ｓ６１３）。
【０１２０】
【数２１】
【０１２１】
具体的には、暗号化処理部２２４が、公開鍵ＰＫおよび公開鍵暗号プロトコルΠを用いて、式（２１）を計算する。ここで、暗号化アルゴリズムＥは、各ランダムオラクルＯiの代わりに、関数計算部２２３を用いて関数ｆｉσｉ（１≦ｉ≦ｎ）による計算を実行する。
【０１２２】
演算部２２０は、記憶部２３０に格納された計算結果を用いて、Ｃ＝（ｕ，ｖ）を生成し、メッセージＭの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ６１４）。
【０１２３】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃ＝（ｕ，ｖ）取得する（Ｓ６２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【０１２４】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫに含まれるπ-1と、暗号文Ｃに含まれるｕとを用いて、式（２２）を計算し、計算結果を記憶部１３０に格納する（Ｓ６２１）。
【０１２５】
【数２２】
【０１２６】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫおよび公開鍵暗号プロトコルΠを用いて、式（２３）を計算し、計算結果を記憶部１３０に格納する（Ｓ６２２）。
【０１２７】
【数２３】
【０１２８】
ここで、復号化アルゴリズムＤは、各ランダムオラクルＯiの代わりに、関数計算部１２５を用いて関数ｆｉσｉによる計算を実行する。
【０１２９】
以上の処理によって、受信者側装置１００の演算部１２０は、Ｍを暗号文Ｃに対するメッセージ文として取得することができる。
【０１３０】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、公開鍵暗号Πおよび関数族の組（Ｆ1，…，Ｆn）が次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１３１】
Πの条件：攻撃者は、（１k,ｐｋ）を入力として、公開鍵暗号プロトコルΠへの攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている（ランダムオラクルへのアクセスは許されていない。）。
・オラクル１：質問（ｘ0，ｘ1）に対して、ランダムにｂ∈｛０，１｝が選択され、式（２４）がリターンされる。但し、このオラクルへの質問は１回のみ。
【０１３２】
【数２４】
【０１３３】
・オラクル２：質問（（ｆ1，…，ｆn），Ｃ）（ｆiはＯiと同一の定義域、値域を持つ関数）に対して、式（２５）がリターンされる。但し、この質問はオラクル１への質問を行う前のみ。
【０１３４】
【数２５】
【０１３５】
・オラクル３：質問（（ｆ1，…，ｆn），Ｃ）（ｆi＝ｂ、または、Ｏiと同一の定義域、値域を持つ関数）に対して、式（２６）がリターンされる。但し、この質問はオラクル１への質問を行った後のみ。
【０１３６】
【数２６】
【０１３７】
このとき、攻撃者は１／２よりもよい確率でｂの値を推測することが難しい。
【０１３８】
（Ｆ1，…，Ｆn）の条件：攻撃者は（１k，π（σ1||…||σn），Ｆ1,k，…，Ｆn,k）を入力として、関数族の組（Ｆ1，…，Ｆn）への攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問（ｉ，ｘ）（１≦ｉ≦ｎ）に対して、Ｈi（ｘ）がリターンされる。
・オラクル２：質問（ｉ，ｕ，ｘ）（１≦ｉ≦ｎ）に対して、σ'1||…||σ'n＝π-1（ｕ）であるとき、σ'i≠σiならばｆｉσ’ｉ（ｘ）がリターンされる。σ'i＝σiならばＨi（ｘ）がリターンされる。
このとき、攻撃者は関数（Ｈ1，…，Ｈn）がランダム関数の組なのか、関数（ｆ１σ１，…，ｆｎσｎ）の組なのかを１／２よりもよい確率で推測することが難しい。
【０１３９】
［第３の実施形態］
第３の実施形態は、第２の実施形態において説明した方法に基づく公開鍵暗号方法である。
【０１４０】
第３の実施形態における暗号システムは、第１の実施形態と同一であるため説明を省略する。また、受信者側装置１００および送信者側装置２００の構成についても第１の実施形態と同一であるため説明を省略する。
【０１４１】
図１０は、本発明の第３の実施形態の暗号化・復号化処理を説明するフローチャートである。
【０１４２】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０を介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ７００）。当該入力を受け付けた演算部１２０の鍵生成部１２１が処理を開始する。
【０１４３】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との対（π，π-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対（π，π-1）を記憶部１３０に格納する（Ｓ７０１）。ここで、πは落とし戸付き一方向性関数を示し、π-1は落とし戸を示す。
【０１４４】
鍵生成部１２１の関数計算部１２５は、式（２７）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ７０２）。
【０１４５】
【数２７】
【０１４６】
但し、ｆｉσｉは、各σ1∈S1,k、σ2∈S2,kに対して、式（２８）を満たすものとする。
【０１４７】
【数２８】
【０１４８】
鍵生成部１２１は、落とし戸付き一方向性関数と落とし戸との対（π，π-1）と、関数族Ｆiとを用いて、式（２９）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ７０３）。
【０１４９】
【数２９】
【０１５０】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００を介してその他の搬送手段を介して、他の装置が取得できるように公開される。
【０１５１】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく、秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【０１５２】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍ∈｛０，１｝k2および公開鍵ＰＫを取得する（Ｓ７１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【０１５３】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【０１５４】
演算部２２０の乱数生成部２２１は、ｒ∈｛０，１｝k1、σ1∈S1,kおよびσ2∈S2,kをランダムに選択し、選択されたｒ、σ1およびσ2を記憶部２３０に格納する（Ｓ７１１）。
【０１５５】
演算部２２０の暗号化部２２２は、選択されたσ1およびσ2と、公開鍵ＰＫに含まれる一方向性関数πとを用いて式（３０）を計算し、計算結果を記憶部２３０に格納する（Ｓ７１２）。
【０１５６】
【数３０】
【０１５７】
具体的には、暗号化処理部２２４が式（３０）を計算する。
【０１５８】
演算部２２０の暗号化部２２２は、暗号鍵ＰＫと、選択されたｒ、σ1およびσ2とを用いて、式（３１）を計算し、計算結果を記憶部２３０に格納する（Ｓ７１３）。
【０１５９】
【数３１】
【０１６０】
ここで、関数計算部２２３が関数ｆ１σ１とｆ２σ２とを計算する。
【０１６１】
演算部２２０は、記憶部２３０に格納された計算結果を用いて、Ｃ＝（ｕ，ｒ，ｖ）を生成し、メッセージＭの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ７１４）。
【０１６２】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃ＝（ｕ，ｒ，ｖ）を取得する（Ｓ７２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【０１６３】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫに含まれる落とし戸π-1と、暗号文Ｃに含まれるｕとを用いて、式（３２）を計算し、計算結果を記憶部１３０に格納する（Ｓ７２１）。
【０１６４】
【数３２】
【０１６５】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫと暗号文Ｃとを用いて、Ｍ∈｛０，１｝k2およびｚ∈｛０，１｝k3を式（３３）によって計算し、計算結果を記憶部１３０に格納する（Ｓ７２２）。
【０１６６】
【数３３】
【０１６７】
復号化部１２２の検査部１２７は、記憶部１３０に格納される計算結果を用いて、式（３４）が成立するか否かを検査する（Ｓ７２３）。
【０１６８】
【数３４】
【０１６９】
式（３４）を満たす、すなわち、検査に成功したと判定された場合、復号化部１２２は、暗号文Ｃのメッセージ文として出力部１５０からＭを出力する。
【０１７０】
式（３４）を満たさない、すなわち、検査に失敗したと判定された場合、復号化部１２２は、出力部１５０からエラーを示すメッセージを出力する。
【０１７１】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、関数族の組（Ｆ1，Ｆ2）が次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１７２】
「攻撃者は（１k，π（σ1||σ2），Ｆ1,k，Ｆ2,k）を入力として、関数族の組（Ｆ1，Ｆ2）への攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問（ｉ，ｘ）（１≦ｉ≦２）に対して、Ｈi（ｘ）がリターンされる。
・オラクル２：質問（ｉ，ｕ，ｘ）（１≦ｉ≦２）に対して、σ'1||σ'2＝π-1（ｕ）であるとき、σ'i≠σiならばｆｉσ’ｉ（ｘ）がリターンされる。σ'i＝σiならばＨi（ｘ）がリターンされる。
このとき、攻撃者は関数（Ｈ1,Ｈ2）がランダム関数の組なのか、関数（ｆ１σ１，f２σ２）の組なのかを１／２よりもよい確率で推測することが難しい。」
第１の実施形態、第２の実施形態および第３の実施形態では、受信者側装置１００と送信者側装置２００との間において暗号通信を行う例を示したが、本発明は、このような態様に限定されるわけではなく、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、その他ファイル暗号システムなど様々なシステムに適用することが可能である。
【０１７３】
また、各装置が備える構成は、ＣＰＵがメモリ上にロードされたプログラムを実行することによって実現してもよいし、独立したハードウェアとして実現してもよい。
【０１７４】
また、鍵生成部１２１、暗号化部２２２および復号化部１２２は、異なる計算機に備えられていてもよいし、一つの計算機に備えられていてもよい。
【０１７５】
また、鍵生成部１２１、暗号化部２２２および復号化部１２２のそれぞれを、一つの装置として実現してもよい。
【符号の説明】
【０１７６】
１０ 暗号システム
１００ 受信者側装置
１０５ 出力装置
１１０ 入力部
１２０ 演算部
１２１ 鍵生成部
１２２ 復号化部
１２３ 落とし戸付き一方向性関数生成部
１２４ 関数生成部
１２５ 関数計算部
１２６ 復号化処理部
１２７ 検査部
１３０ 記憶部
１４０ 通信部
１５０ 出力部
２００ 送信者側装置
２１０ 入力部
２２０ 演算部
２２１ 乱数生成部
２２２ 暗号化部
２２３ 関数計算部
２２４ 暗号化処理部
２３０ 記憶部
２４０ 通信部
２５０ 出力部
３００ ネットワーク
４００ ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）
４０１ メモリ
４０３ 外部記憶装置
４０４ 通信装置
４０５ 出力装置
４０６ 入力装置
４０７ 読書装置
４０８ 記憶媒体
【技術分野】
【０００１】
本発明は、メッセージを暗号化して通信を行う暗号システムに関する。
【背景技術】
【０００２】
公開鍵暗号は、公開鍵と秘密鍵との異なる鍵情報を用いて、データの暗号化・復号化を行う暗号技術のひとつである。公開鍵暗号は、「鍵生成」、「暗号化」及び「復号化」の３つの手段（アルゴリズムなど）から定義される。鍵生成手段とは、セキュリティパラメータ（例えば、鍵長を指定するパラメータ）を入力として、公開鍵と秘密鍵とを出力する手段である。暗号化手段とは、メッセージ文と公開鍵を入力として暗号文を出力する手段である。復号化手段とは、暗号文と秘密鍵とを入力としてメッセージ文を出力する手段である。
【０００３】
例えば、公開鍵暗号を暗号通信に利用する場合、鍵生成は受信者が行い、公開鍵のみを公開し、秘密鍵は安全な方法によって保持する。送信者は、メッセージ文を作成し、暗号化手段を用いて暗号化を行い、暗号文を受信者に送信する。受信者は、復号化手段を用いて暗号文の復号化を行う。
【０００４】
公開鍵暗号の安全性は、通常、標準計算機モデル、または、ランダムオラクルモデル（例えば、非特許文献１）上で与えられる。
【０００５】
標準計算機モデルとは、（対話型）チューリングマシンから構成されるモデルで、現実の計算機システムに近いものと考えられている。
【０００６】
一方、ランダムオラクルモデルでは、全てのパーティ（攻撃者を含む）がランダム関数へオラクルとしてアクセスすることが許されている（以下、このようなランダム関数をランダムオラクルと呼ぶ）。
【０００７】
現実のシステムにおいては、ランダムオラクルの部分は実用的なハッシュ関数に置き換えて利用される（このような方法論は、random oracle methodologyと呼ばれる）。このとき、ランダムオラクルモデル上における安全性証明は現実のシステムにおいては通用しなくなってしまうが、安全性の何らかの根拠を示すものと考えられている。
【０００８】
前述のように、ランダムオラクルモデルは観念論的なモデルであるが、実用性に優れた暗号プロトコルの設計が容易であるため、多くの暗号プロトコルが提案されている。
【０００９】
random oracle methodologyに関するネガティブな結果として、非特許文献２では、ランダムオラクルモデル上では安全であるが、ランダムオラクルのいかなる関数への置き換えに対しても安全ではない暗号プロトコルが存在することが示されている。また、非特許文献３では、RSA full-domain hash 署名は標準計算機モデル上で安全にはならないと考えられる根拠を示している。
【００１０】
一方、random oracle methodologyに関するポジティブな結果として、非特許文献４は、ランダムオラクルの性質の一部を満たすハッシュ関数の実現方法について記載している。非特許文献５では、非特許文献７に記載のOAEPにおけるランダムオラクルの関数への置き換えを考察している。非特許文献６では、非特許文献１に記載の公開鍵暗号方法において、ランダムオラクルのadaptive perfectly one-way hash functionへの置き換えを考察している。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, http://www.cse.ucsd.edu/ ~mihir/papers/ro.html
【非特許文献２】R. Canetti, O. Goldreich, and S. Halevi. Random Oracle Methodology, Revised,http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.Publications.html/
【非特許文献３】Y. Dodis, R.Oliveira, and K. Pietrzak. On the Generic Insecurity of Full-domain Hash, Advances in Cryptography -- CRYPTO2005, pp.449-466, Springer-Verlag, 2005
【非特許文献４】R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information, http://domino.research.ibm.com/comm/ research_projects.nsf/pages/security.Publications.html/
【非特許文献５】A. Boldyreva and M. Fischlin. On the Security of OAEP, http://www.cc.gatech.edu/~aboldyre/publications.html
【非特許文献６】O. Pandey, R. Pass, and V. Vaikuntanathan. Adaptive One-way Functions and Applications, Advances in Cryptography -- CRYPTO2008, pp.57-74, Springer-Verlag, 2008
【非特許文献７】M. Bellare and P. Rogaway. Optimal asymmetric encryption -- How to encrypt with RSA,http://cseweb.ucsd.edu/~mihir/ papers/oaep.html
【発明の概要】
【発明が解決しようとする課題】
【００１２】
前述のように、公開鍵暗号の安全性は、通常、ランダムオラクルモデル、または、標準計算機モデル上で与えられる。しかし、ランダムオラクルモデル上における公開鍵暗号方法と、標準計算機モデル上における公開鍵暗号方法とはそれぞれのモデルにおいて考察されるにとどまり、これらのモデル相互間において、安全性を考察することは行われていない。
【００１３】
本発明は、第三者から情報を秘匿するための暗号方法を安全かつ効率的に実現するため、ランダムオラクルモデル上の公開鍵暗号方法で一定の安全性を満たすものをベースとして、標準計算機モデル上で安全性証明可能であり、かつ、暗号化および復号化の高速処理に優れた公開鍵暗号方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の代表的な一例を示せば以下の通りである。すなわち、暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、前記鍵生成部は、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納し、式（１）を満たす関数族Ｆiを生成し（但し、ｆiσiは、各σ1∈S1,k，σ2∈S2,kに対して、式（２）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、前記暗号化部は、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４）を計算し、当該計算結果を前記第２の記憶部に格納し、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（５）を計算し、当該計算結果を前記第２の記憶部に格納し、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（６）に示すように生成し、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、前記復号化部は、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７）を計算して、当該計算結果を前記第３の記憶部に格納し、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、式（９）を満たすか否かを判定し、前記式（９）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする。
【００１５】
【数１】
【００１６】
【数２】
【００１７】
【数３】
【００１８】
【数４】
【００１９】
【数５】
【００２０】
【数６】
【００２１】
【数７】
【００２２】
【数８】
【００２３】
【数９】
【発明の効果】
【００２４】
本発明によれば、標準計算機モデル上において安全性証明可能であり、かつ、実用的な公開鍵暗号を提供することが可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施形態における暗号システムの構成の一例を示す説明図である。
【図２】本発明の第１の実施形態の受信者側装置の構成の一例を示す説明図である。
【図３】本発明の第１の実施形態の鍵生成部の構成の一例を示す説明図である。
【図４】本発明の第１の実施形態の復号化部の構成の一例を示す説明図である。
【図５】本発明の第１の実施形態の受信者側装置のハードウェア構成の一例を示すブロック図である。
【図６】本発明の第１の実施形態の送信者側装置の構成の一例を示す説明図である。
【図７】本発明の第１の実施形態の暗号化部の構成の一例を示す説明図である。
【図８】本発明の第１の実施形態の暗号化・復号化処理を説明するフローチャートである。
【図９】本発明の第２の実施形態の暗号化・復号化処理を説明するフローチャートである。
【図１０】本発明の第３の実施形態の暗号化・復号化処理を説明するフローチャートである。
【発明を実施するための形態】
【００２６】
以下の実施形態においては、暗号プロトコルを公開鍵暗号プロトコルとして利用し、公開鍵を暗号化鍵とし、秘密鍵を復号化鍵として利用する例を説明するが、本発明はこのような態様に限定されるわけではない。
【００２７】
［第１の実施形態］
本発明の第１の実施形態では、標準計算機モデル上で証明可能安全性をもつ公開鍵暗号方法について述べる。
【００２８】
図１は、本発明の第１の実施形態における暗号システム１０の構成の一例を示す説明図である。
【００２９】
図１に示すように、暗号システム１０は、受信者側装置１００と送信者側装置２００とを備えており、これらはネットワーク３００を介して相互に情報を送受信することができる。
【００３０】
なお、暗号システム１０は、受信者側装置１００および送信者側装置２００を、それぞれ、一以上備えていてもよい。
【００３１】
図２は、本発明の第１の実施形態の受信者側装置１００の構成の一例を示す説明図である。
【００３２】
受信者側装置１００は、入力部１１０、演算部１２０、記憶部１３０、通信部１４０および出力部１５０を備える。
【００３３】
入力部１１０は、受信者側装置１００に情報を入力する。
【００３４】
演算部１２０は、論理演算、べき乗算、剰余演算、ハッシュ関数演算およびランダム関数演算を含む各種演算の実行、並びに、受信者側装置１００の各部の制御を行う。演算部１２０は、鍵生成部１２１および復号化部１２２を備える。
【００３５】
鍵生成部１２１は、公開鍵（暗号化鍵）および秘密鍵（復号化鍵）を生成する。復号化部１２２は、秘密鍵を用いて復号化処理を実行する。
【００３６】
記憶部１３０は、入力部１１０から入力された情報および演算部１２０の処理結果等を格納する。通信部１４０は、ネットワーク３００を介して送信者側装置２００と通信する。出力部１５０は、外部に情報を出力する。
【００３７】
図３は、本発明の第１の実施形態の鍵生成部１２１の構成の一例を示す説明図である。
【００３８】
鍵生成部１２１は、落とし戸付き一方向性関数生成部１２３および関数生成部１２４を備える。
【００３９】
落とし戸付き一方向性関数生成部１２３は、落とし戸付き一方向性関数（π）と落とし戸（π-1）との対を生成する。関数生成部１２４は、関数族Ｆiを生成する。
【００４０】
図４は、本発明の第１の実施形態の復号化部１２２の構成の一例を示す説明図である。
【００４１】
復号化部１２２は、関数計算部１２５、復号化処理部１２６および検査部１２７を備える。
【００４２】
関数計算部１２５は、ハッシュ関数等の各種関数の計算を実行する。復号化処理部１２６は、秘密鍵を用いて、入力された暗号文を復号化する。検査部１２７は、復号化処理部１２６によって復号化されたメッセージを検証する。
【００４３】
図５は、本発明の第１の実施形態の受信者側装置１００のハードウェア構成の一例を示すブロック図である。
【００４４】
受信者側装置１００は、例えば、図５に示すようなハードウェア構成からなる計算機によって実現される。
【００４５】
図５に示すように、受信者側装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）４００、メモリ４０１、外部記憶装置４０３、通信装置４０４、出力装置４０５、入力装置４０６および読書装置４０７を備える。
【００４６】
ＣＰＵ４００は、メモリ４０１上に展開されたプログラムを実行する。
【００４７】
メモリ４０１は、ＣＰＵ４００によって実行されるプログラムおよびＣＰＵ４００が処理を実行するために必要となる情報を格納する。また、メモリ４０１は、ＣＰＵ４００が処理を実行するためのワークエリアとしても用いられる。
【００４８】
外部記憶装置４０３は、ＣＰＵ４００によって実行される各種プログラムが格納される。また、処理に必要となる情報および処理結果等も格納される。
【００４９】
通信装置４０４は、ネットワークを介して他の装置と通信するための装置である。通信装置は、例えばＮＩＣ（Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｃａｒｄ）等が考えられる。
【００５０】
出力装置４０５は、ＣＰＵ４００によって実行された処理の結果を出力するための装置である。出力装置４０５は、例えば、ディスプレイ等が考えられる。
【００５１】
入力装置４０６は、受信者側装置１００に情報を入力するための装置である。入力装置４０６は、例えば、キーボード又はマウスなどが考えられる。
【００５２】
読書装置４０７は、可搬性を有する記憶媒体４０８から情報を読み出したり、又は、情報を書き込んだりするための装置である。なお、記憶媒体４０８としては、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）又はＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）等が考えられる。
【００５３】
受信者側装置１００が備える各構成を実現する方法としては、例えば、入力部１１０は、ＣＰＵ４００が入力装置４０６を利用することによって実現でき、演算部１２０は、外部記憶装置４０３に格納される所定のプログラムをメモリ４０１にロードしてＣＰＵ４００が実行することによって実現でき、記憶部１３０は、ＣＰＵ４００がメモリ４０１又は外部記憶装置４０３を利用することによって実現でき、通信部１４０は、ＣＰＵ４００が通信装置４０４を利用することによって実現でき、出力部１５０は、ＣＰＵ４００が出力装置４０５を利用することによって実現できる。
【００５４】
なお、受信者側装置１００が備える各構成は、プログラムとして実現されてもよいし、ハードウェアとして実現されてもよい。
【００５５】
メモリ４０１にロードされる所定のプログラムは、読書装置４０７を介して記憶媒体４０８から、又は、通信装置４０４を介してネットワークから、外部記憶装置４０３に格納され、その後、メモリ４０１上にロードされてＣＰＵ４００によって実行されるようにしてもよい。また、読書装置４０７を介して記憶媒体４０８から、又は、通信装置４０４を介してネットワークから、メモリ４０１上に直接ロードされ、ＣＰＵ４００によって実行されるようにしてもよい。
【００５６】
図６は、本発明の第１の実施形態の送信者側装置２００の構成の一例を示す説明図である。
【００５７】
送信者側装置２００は、入力部２１０、演算部２２０、記憶部２３０、通信部２４０および出力部２５０を備える。
【００５８】
入力部２１０は、送信者側装置２００に情報を入力する。
【００５９】
演算部２２０は、論理演算、べき乗算、剰余演算、ハッシュ関数演算およびランダム関数演算を含む各種演算の実行、並びに、送信者側装置２００の各部の制御を行う。演算部２２０は、乱数生成部２２１および暗号化部２２２を備える。
【００６０】
乱数生成部２２１は、処理に必要となる乱数を生成する。暗号化部２２２は、公開鍵を用いて暗号化処理を実行する。
【００６１】
記憶部２３０は、入力部２１０から入力された情報および演算部２２０の処理結果等を格納する。通信部２４０は、ネットワーク３００を介して受信者側装置１００と通信する。出力部２５０は、外部に情報を出力する。
【００６２】
図７は、本発明の第１の実施形態の暗号化部２２２の構成の一例を示す説明図である。
【００６３】
暗号化部２２２は、関数計算部２２３および暗号化処理部２２４を備える。
【００６４】
関数計算部２２３は、ハッシュ関数等の各種関数の計算を実行する。暗号化処理部２２４は、公開鍵を用いて入力されたメッセージ文を暗号化する。
【００６５】
図８は、本発明の第１の実施形態の暗号化・復号化処理を説明するフローチャートである。
【００６６】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０を介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ５００）。当該入力を受けた演算部１２０の鍵生成部１２１が処理を開始する。
【００６７】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との二つの対（π1，π1-1）および（π2，π2-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対を記憶部１３０に格納する（Ｓ５０１）。ここで、各１≦ｉ≦２について、πiは落とし戸付き一方向性関数を示し、πi-1は落とし戸を示す。
【００６８】
次に、鍵生成部１２１の関数生成部１２４は、式（１０）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ５０２）。
【００６９】
【数１０】
【００７０】
但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１１）を満たすものとする。
【００７１】
【数１１】
【００７２】
次に、鍵生成部１２１は、記憶部１３０に格納された落とし戸付き一方向性関数と落とし戸との対（π1，π1-1）および（π2，π2-1）と、関数族Ｆiとを用いて、式（１２）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ５０３）。
【００７３】
【数１２】
【００７４】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００その他の搬送手段を介して、他の装置が取得できるように公開される。
【００７５】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは、記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【００７６】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍ∈｛０，１｝k2および公開鍵ＰＫを取得する（Ｓ５１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【００７７】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【００７８】
まず、演算部２２０の乱数生成部２２１は、ｒ∈｛０，１｝k1と、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kとをランダムに選択し、選択されたｒ、σ1およびσ2を記憶部２３０に格納する（Ｓ５１１）。
【００７９】
次に、演算部２２０の暗号化部２２２は、取得された公開鍵ＰＫと、記憶部２３０に格納されるσ1およびσ2とを用いて式（１３）を計算し、当該計算結果を記憶部２３０に格納する（Ｓ５１２）。
【００８０】
【数１３】
【００８１】
具体的には、暗号化部２２２の関数計算部２２３が、公開鍵ＰＫ、σ1およびσ2を用いて式（１３）を計算する。
【００８２】
演算部２２０の暗号化部２２２は、記憶部２３０に格納される情報を用いて、式（１４）を計算し、計算結果を記憶部２３０に格納する（Ｓ５１３）。
【００８３】
【数１４】
【００８４】
ここで、暗号化部２２２の関数計算部２２３が関数ｆ１σ１とｆ２σ２とを計算する。
【００８５】
演算部２２０の暗号化部２２２は、記憶部２３０に格納された情報を用いて、Ｃ＝（ｕ1，ｕ2，ｒ，ｖ）を生成し、メッセージ文Ｍの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ５１４）。
【００８６】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃを取得する（Ｓ５２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【００８７】
復号化部１２２は、暗号文Ｃを以下の処理によって復号化する。
【００８８】
まず、復号化部１２２の復号化処理部１２６は、暗号文Ｃに含まれるｕ1およびｕ2と、秘密鍵ＳＫに含まれる落とし戸π1-1およびπ2-2とを用いて、式（１５）を計算し、計算結果を記憶部１３０に格納する（Ｓ５２１）。
【００８９】
【数１５】
【００９０】
復号化部１２２の関数計算部１２５は、記憶部１３０に格納されたデータを用いて、Ｍ∈｛０，１｝k2およびｚ∈｛０，１｝k3を式（１６）によって計算し、計算結果を記憶部１３０に格納する（Ｓ５２２）。
【００９１】
【数１６】
【００９２】
復号化部１２２の検査部１２７は、記憶部１３０に格納される計算結果を用いて、式（１７）が成立するか否かを検査する（Ｓ５２３）。
【００９３】
【数１７】
【００９４】
式（１７）を満たす、すなわち、検査に成功したと判定された場合、復号化部１２２は、暗号文Ｃのメッセージ文として出力部１５０からＭを出力する。
【００９５】
式（１７）を満たさない、すなわち、検査に失敗したと判定された場合、復号化部１２２は、出力部１５０からエラーを示すメッセージを出力する。
【００９６】
本実施形態で説明した公開鍵暗号方法は、非特許文献１に記載のランダムオラクルモデル上の公開鍵暗号方法をベースにして、標準計算機モデル上で安全となるように変換している。
【００９７】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、関数族Ｆi（ｉ＝１，２）がそれぞれ次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される（ＩＮＤ−ＣＣＡ２安全の詳細については、非特許文献１または非特許文献７に記載されている）。
【００９８】
「攻撃者は（１k，πi（σi），Ｆi,k）を入力として、関数族Ｆiへの攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問ｘに対して、Ｈｉ（ｘ）がリターンされる。
・オラクル２：質問（ｕ，ｘ）に対して、ｕ≠πi（σi）ならばｆｉσ’（ｘ）がリターンされる。但し、σ'＝πi-1（ｕ）、ｕ＝πi（σi）ならばエラーを示すメッセージがリターンされる。
このとき、攻撃者は関数Ｈｉがランダム関数なのか関数ｆｉσｉなのかを１／２よりもよい確率で推測することが難しい。」
【００９９】
［第２の実施形態］
第２の実施形態では、ランダムオラクルＯ1，…，Ｏnを利用する公開鍵暗号Π＝（Ｋ，Ｅ，Ｄ）をベースにして、ランダムオラクルに依存しない公開鍵暗号Π'＝（Ｋ'，Ｅ'，Ｄ'）を与える一般的方法について説明する。但し、公開鍵暗号プロトコルΠの鍵生成手段Ｋはランダムオラクルに依存しないものとする。
【０１００】
第２の実施形態における暗号システムは、第１の実施形態と同一であるため説明を省略する。また、受信者側装置１００および送信者側装置２００の構成についても第１の実施形態と同一であるため説明を省略する。
【０１０１】
以下、第１の実施形態との差異を中心に説明する。
【０１０２】
図９は、本発明の第２の実施形態の暗号化・復号化処理を説明するフローチャートである。
【０１０３】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０に介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ６００）。当該入力を受け付けた演算部１２０の鍵生成部１２１が処理を開始する。
【０１０４】
鍵生成部１２１は、公開鍵暗号プロトコルΠを用いて、公開鍵ｐｋおよび秘密鍵ｓｋを生成し、記憶部１３０に格納する（Ｓ６０１）。
【０１０５】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との対（π，π-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対（π，π-1）を記憶部１３０に格納する（Ｓ６０２）。ここで、πは落とし戸付き一方向性関数を示し、π-1は落とし戸を示す。
【０１０６】
鍵生成部１２１の関数計算部１２５は、式（１８）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ６０３）。
【０１０７】
【数１８】
【０１０８】
但し、各ｆｉσｉは、ランダム関数Ｏiと同一の定義域と、値域とを持つものとする。
【０１０９】
鍵生成部１２１は、公開鍵ｐｋおよび秘密鍵ｓｋと、落とし戸付き一方向性関数と落とし戸との対（π，π-1）と、関数族Ｆiとを用いて、式（１９）によってランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ６０４）。
【０１１０】
【数１９】
【０１１１】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００その他の搬送手段を介して、他の装置が取得できるように公開される。
【０１１２】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく、秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【０１１３】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍおよび公開鍵ＰＫを取得する（Ｓ６１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【０１１４】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【０１１５】
まず、演算部２２０の乱数生成部２２１は、σi∈Si,k（１≦ｉ≦n）をランダムに選択し、選択されたσiを記憶部２３０に格納する（Ｓ６１１）。
【０１１６】
演算部２２０の暗号化部２２２は、選択されたσiおよび公開鍵ＰＫに含まれる一方向性関数πを用いて式（２０）を計算し、計算結果を記憶部２３０に格納する（Ｓ６１２）。
【０１１７】
【数２０】
【０１１８】
具体的には、暗号化処理部２２４が式（２０）を計算する。
【０１１９】
演算部２２０の暗号化部２２２は、公開鍵ＰＫおよび公開鍵暗号プロトコルΠを用いて、式（２１）を計算し、計算結果を記憶部２３０に格納する（Ｓ６１３）。
【０１２０】
【数２１】
【０１２１】
具体的には、暗号化処理部２２４が、公開鍵ＰＫおよび公開鍵暗号プロトコルΠを用いて、式（２１）を計算する。ここで、暗号化アルゴリズムＥは、各ランダムオラクルＯiの代わりに、関数計算部２２３を用いて関数ｆｉσｉ（１≦ｉ≦ｎ）による計算を実行する。
【０１２２】
演算部２２０は、記憶部２３０に格納された計算結果を用いて、Ｃ＝（ｕ，ｖ）を生成し、メッセージＭの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ６１４）。
【０１２３】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃ＝（ｕ，ｖ）取得する（Ｓ６２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【０１２４】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫに含まれるπ-1と、暗号文Ｃに含まれるｕとを用いて、式（２２）を計算し、計算結果を記憶部１３０に格納する（Ｓ６２１）。
【０１２５】
【数２２】
【０１２６】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫおよび公開鍵暗号プロトコルΠを用いて、式（２３）を計算し、計算結果を記憶部１３０に格納する（Ｓ６２２）。
【０１２７】
【数２３】
【０１２８】
ここで、復号化アルゴリズムＤは、各ランダムオラクルＯiの代わりに、関数計算部１２５を用いて関数ｆｉσｉによる計算を実行する。
【０１２９】
以上の処理によって、受信者側装置１００の演算部１２０は、Ｍを暗号文Ｃに対するメッセージ文として取得することができる。
【０１３０】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、公開鍵暗号Πおよび関数族の組（Ｆ1，…，Ｆn）が次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１３１】
Πの条件：攻撃者は、（１k,ｐｋ）を入力として、公開鍵暗号プロトコルΠへの攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている（ランダムオラクルへのアクセスは許されていない。）。
・オラクル１：質問（ｘ0，ｘ1）に対して、ランダムにｂ∈｛０，１｝が選択され、式（２４）がリターンされる。但し、このオラクルへの質問は１回のみ。
【０１３２】
【数２４】
【０１３３】
・オラクル２：質問（（ｆ1，…，ｆn），Ｃ）（ｆiはＯiと同一の定義域、値域を持つ関数）に対して、式（２５）がリターンされる。但し、この質問はオラクル１への質問を行う前のみ。
【０１３４】
【数２５】
【０１３５】
・オラクル３：質問（（ｆ1，…，ｆn），Ｃ）（ｆi＝ｂ、または、Ｏiと同一の定義域、値域を持つ関数）に対して、式（２６）がリターンされる。但し、この質問はオラクル１への質問を行った後のみ。
【０１３６】
【数２６】
【０１３７】
このとき、攻撃者は１／２よりもよい確率でｂの値を推測することが難しい。
【０１３８】
（Ｆ1，…，Ｆn）の条件：攻撃者は（１k，π（σ1||…||σn），Ｆ1,k，…，Ｆn,k）を入力として、関数族の組（Ｆ1，…，Ｆn）への攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問（ｉ，ｘ）（１≦ｉ≦ｎ）に対して、Ｈi（ｘ）がリターンされる。
・オラクル２：質問（ｉ，ｕ，ｘ）（１≦ｉ≦ｎ）に対して、σ'1||…||σ'n＝π-1（ｕ）であるとき、σ'i≠σiならばｆｉσ’ｉ（ｘ）がリターンされる。σ'i＝σiならばＨi（ｘ）がリターンされる。
このとき、攻撃者は関数（Ｈ1，…，Ｈn）がランダム関数の組なのか、関数（ｆ１σ１，…，ｆｎσｎ）の組なのかを１／２よりもよい確率で推測することが難しい。
【０１３９】
［第３の実施形態］
第３の実施形態は、第２の実施形態において説明した方法に基づく公開鍵暗号方法である。
【０１４０】
第３の実施形態における暗号システムは、第１の実施形態と同一であるため説明を省略する。また、受信者側装置１００および送信者側装置２００の構成についても第１の実施形態と同一であるため説明を省略する。
【０１４１】
図１０は、本発明の第３の実施形態の暗号化・復号化処理を説明するフローチャートである。
【０１４２】
［鍵生成処理］
受信者側装置１００の演算部１２０は、入力部１１０を介して、１k（ｋは、セキュリティパラメータ）の入力を受け付ける（Ｓ７００）。当該入力を受け付けた演算部１２０の鍵生成部１２１が処理を開始する。
【０１４３】
鍵生成部１２１の落とし戸付き一方向性関数生成部１２３は、入力１kに基づいて、落とし戸付き一方向性関数と落とし戸との対（π，π-1）を生成し、生成された落とし戸付き一方向性関数と落とし戸との対（π，π-1）を記憶部１３０に格納する（Ｓ７０１）。ここで、πは落とし戸付き一方向性関数を示し、π-1は落とし戸を示す。
【０１４４】
鍵生成部１２１の関数計算部１２５は、式（２７）を満たす関数族Ｆiを生成し、生成された関数族Ｆiを記憶部１３０に格納する（Ｓ７０２）。
【０１４５】
【数２７】
【０１４６】
但し、ｆｉσｉは、各σ1∈S1,k、σ2∈S2,kに対して、式（２８）を満たすものとする。
【０１４７】
【数２８】
【０１４８】
鍵生成部１２１は、落とし戸付き一方向性関数と落とし戸との対（π，π-1）と、関数族Ｆiとを用いて、式（２９）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する（Ｓ７０３）。
【０１４９】
【数２９】
【０１５０】
鍵生成部１２１は、出力装置１０５を用いて、生成された公開鍵ＰＫおよび暗号鍵ＳＫを出力する。なお、出力された公開鍵ＰＫは、ネットワーク３００を介してその他の搬送手段を介して、他の装置が取得できるように公開される。
【０１５１】
本実施形態では、受信者側装置１００が復号化部１２２を備えるため、秘密鍵ＳＫは記憶部１３０に格納されるものとするが、本発明はこれに限定されることなく、秘密鍵ＳＫを他の装置に出力又は格納してもよい。
【０１５２】
［暗号化処理］
送信者側装置２００は、入力部２１０又は通信部２４０を介して、メッセージ文Ｍ∈｛０，１｝k2および公開鍵ＰＫを取得する（Ｓ７１０）。その後、送信者側装置２００の演算部２２０が処理を開始する。
【０１５３】
演算部２２０は、メッセージ文Ｍの暗号文Ｃを以下の処理によって生成する。
【０１５４】
演算部２２０の乱数生成部２２１は、ｒ∈｛０，１｝k1、σ1∈S1,kおよびσ2∈S2,kをランダムに選択し、選択されたｒ、σ1およびσ2を記憶部２３０に格納する（Ｓ７１１）。
【０１５５】
演算部２２０の暗号化部２２２は、選択されたσ1およびσ2と、公開鍵ＰＫに含まれる一方向性関数πとを用いて式（３０）を計算し、計算結果を記憶部２３０に格納する（Ｓ７１２）。
【０１５６】
【数３０】
【０１５７】
具体的には、暗号化処理部２２４が式（３０）を計算する。
【０１５８】
演算部２２０の暗号化部２２２は、暗号鍵ＰＫと、選択されたｒ、σ1およびσ2とを用いて、式（３１）を計算し、計算結果を記憶部２３０に格納する（Ｓ７１３）。
【０１５９】
【数３１】
【０１６０】
ここで、関数計算部２２３が関数ｆ１σ１とｆ２σ２とを計算する。
【０１６１】
演算部２２０は、記憶部２３０に格納された計算結果を用いて、Ｃ＝（ｕ，ｒ，ｖ）を生成し、メッセージＭの暗号文として出力部２５０又は通信部２４０を介して、受信者側装置１００に送信する（Ｓ７１４）。
【０１６２】
［復号化処理］
受信者側装置１００の演算部１２０は、入力部１１０又は通信部１４０を介して、秘密鍵ＳＫおよび暗号文Ｃ＝（ｕ，ｒ，ｖ）を取得する（Ｓ７２０）。なお、本実施形態では、秘密鍵ＳＫは鍵生成部１２１から取得され、暗号文Ｃは送信者側装置２００から取得される。その後、受信者側装置１００の復号化部１２２が処理を開始する。
【０１６３】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫに含まれる落とし戸π-1と、暗号文Ｃに含まれるｕとを用いて、式（３２）を計算し、計算結果を記憶部１３０に格納する（Ｓ７２１）。
【０１６４】
【数３２】
【０１６５】
復号化部１２２の復号化処理部１２６は、秘密鍵ＳＫと暗号文Ｃとを用いて、Ｍ∈｛０，１｝k2およびｚ∈｛０，１｝k3を式（３３）によって計算し、計算結果を記憶部１３０に格納する（Ｓ７２２）。
【０１６６】
【数３３】
【０１６７】
復号化部１２２の検査部１２７は、記憶部１３０に格納される計算結果を用いて、式（３４）が成立するか否かを検査する（Ｓ７２３）。
【０１６８】
【数３４】
【０１６９】
式（３４）を満たす、すなわち、検査に成功したと判定された場合、復号化部１２２は、暗号文Ｃのメッセージ文として出力部１５０からＭを出力する。
【０１７０】
式（３４）を満たさない、すなわち、検査に失敗したと判定された場合、復号化部１２２は、出力部１５０からエラーを示すメッセージを出力する。
【０１７１】
本実施形態で説明した公開鍵暗号方法の安全性に関しては、関数族の組（Ｆ1，Ｆ2）が次の条件を満たすとき、ＩＮＤ−ＣＣＡ２安全であることが証明される。
【０１７２】
「攻撃者は（１k，π（σ1||σ2），Ｆ1,k，Ｆ2,k）を入力として、関数族の組（Ｆ1，Ｆ2）への攻撃を行う。攻撃者は、次のオラクルにアクセスすることが許されている。
・オラクル１：質問（ｉ，ｘ）（１≦ｉ≦２）に対して、Ｈi（ｘ）がリターンされる。
・オラクル２：質問（ｉ，ｕ，ｘ）（１≦ｉ≦２）に対して、σ'1||σ'2＝π-1（ｕ）であるとき、σ'i≠σiならばｆｉσ’ｉ（ｘ）がリターンされる。σ'i＝σiならばＨi（ｘ）がリターンされる。
このとき、攻撃者は関数（Ｈ1,Ｈ2）がランダム関数の組なのか、関数（ｆ１σ１，f２σ２）の組なのかを１／２よりもよい確率で推測することが難しい。」
第１の実施形態、第２の実施形態および第３の実施形態では、受信者側装置１００と送信者側装置２００との間において暗号通信を行う例を示したが、本発明は、このような態様に限定されるわけではなく、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、その他ファイル暗号システムなど様々なシステムに適用することが可能である。
【０１７３】
また、各装置が備える構成は、ＣＰＵがメモリ上にロードされたプログラムを実行することによって実現してもよいし、独立したハードウェアとして実現してもよい。
【０１７４】
また、鍵生成部１２１、暗号化部２２２および復号化部１２２は、異なる計算機に備えられていてもよいし、一つの計算機に備えられていてもよい。
【０１７５】
また、鍵生成部１２１、暗号化部２２２および復号化部１２２のそれぞれを、一つの装置として実現してもよい。
【符号の説明】
【０１７６】
１０ 暗号システム
１００ 受信者側装置
１０５ 出力装置
１１０ 入力部
１２０ 演算部
１２１ 鍵生成部
１２２ 復号化部
１２３ 落とし戸付き一方向性関数生成部
１２４ 関数生成部
１２５ 関数計算部
１２６ 復号化処理部
１２７ 検査部
１３０ 記憶部
１４０ 通信部
１５０ 出力部
２００ 送信者側装置
２１０ 入力部
２２０ 演算部
２２１ 乱数生成部
２２２ 暗号化部
２２３ 関数計算部
２２４ 暗号化処理部
２３０ 記憶部
２４０ 通信部
２５０ 出力部
３００ ネットワーク
４００ ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）
４０１ メモリ
４０３ 外部記憶装置
４０４ 通信装置
４０５ 出力装置
４０６ 入力装置
４０７ 読書装置
４０８ 記憶媒体
【特許請求の範囲】
【請求項１】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納し、
式（１）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（２）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４）を計算し、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（５）を計算し、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（６）に示すように生成し、
前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７）を計算して、当該計算結果を前記第３の記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、
式（９）を満たすか否かを判定し、
前記式（９）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１】
【数２】
【数３】
【数４】
【数５】
【数６】
【数７】
【数８】
【数９】
【請求項２】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記第１の記憶部に格納し、
落とし戸付き一方向性関数πと落とし戸とπ-1からの対（π，π-1）を生成して、前記生成された対（π，π-1）を前記第１の記憶部に格納し、
式（１０）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（１１）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（１２）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（１３）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（１４）に示すように生成し、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（１５）によってσiを計算して、当該計算結果を前記第３の記憶部に格納し、
前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（１６）によってＭを計算し、
前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１０】
【数１１】
【数１２】
【数１３】
【数１４】
【数１５】
【数１６】
【請求項３】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから対（π，π-1）を生成し、前記生成された対（π，π-1）を前記第１の記憶部に格納し、
式（１７）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１８）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記生成された対（π，π-1）と前記関数族Ｆiとを用いて、式（１９）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（２０）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（２１）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（２２）に示すように生成し、
前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（２３）を計算して、当該計算結果を前記第３の記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（２４）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、
式（２５）を満たすか否かを判定し、
前記式（２５）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１７】
【数１８】
【数１９】
【数２０】
【数２１】
【数２２】
【数２３】
【数２４】
【数２５】
【請求項４】
前記暗号化システムは、第１の計算機と、前記第１の計算機と接続される第２の計算機とを備え、
前記第１の計算機は、前記鍵生成装置および前記復号化装置を備え、前記第２の計算機は、前記暗号化装置を備えることを特徴とする請求項１から３のいずれかに記載の暗号化システム。
【請求項５】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（２６）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（２７）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（２８）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（２９）を計算し、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（３０）を計算し、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（３１）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（３２）を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（３３）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、式（３４）を満たすか否かを判定するステップと、
前記復号化部が、前記式（３４）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数２６】
【数２７】
【数２８】
【数２９】
【数３０】
【数３１】
【数３２】
【数３３】
【数３４】
【請求項６】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記第１の記憶部に格納するステップと、
前記鍵生成部が、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成して、前記生成された対（π，π-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（３５）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（３６）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（３７）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（３８）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（３９）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４０）によってσiを計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（４１）によってＭを計算するステップと、
前記復号化部が、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数３５】
【数３６】
【数３７】
【数３８】
【数３９】
【数４０】
【数４１】
【請求項７】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、前記生成された対（π，π-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（４２）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（４３）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記生成された対（π，π-1）と前記関数族Ｆiとを用いて、式（４４）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４５）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（４６）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（４７）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４８）を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４９）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、式（５０）を満たすか否かを判定するステップと、
前記復号化部が、前記式（５０）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数４２】
【数４３】
【数４４】
【数４５】
【数４６】
【数４７】
【数４８】
【数４９】
【数５０】
【請求項８】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、（式５１）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（５２）を満たすものとする。）、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（５３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５１】
【数５２】
【数５３】
【請求項９】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成し、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、式（５４）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（５５）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５４】
【数５５】
【請求項１０】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、式（５６）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（５７）を満たすものとする。）、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（５８）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５６】
【数５７】
【数５８】
【請求項１１】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記記憶部に格納し、
式（５９）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（６０）を満たすものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（６１）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵と、ランダムに選択されたらｒ∈｛０，１｝k1、σ1∈Ｓ1,k、およびσ2∈Ｓ2,kと用いて、式（６２）から式（６４）によってメッセージ文Ｍ∈｛０，１｝k2を暗号化した暗号文Ｃが、前記入力部を介して入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（６５）を計算して、当該計算結果を前記記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（６６）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記記憶部に格納し、
式（６７）を満たすか否かを判定し、
前記式（６７）を満たすと判定された場合は、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数５９】
【数６０】
【数６１】
【数６２】
【数６３】
【数６４】
【数６５】
【数６６】
【数６７】
【請求項１２】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記記憶部に格納し、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成して、前記生成された対（π，π-1）を前記記憶部に格納し、
式（６８）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（６９）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵と、ランダムに選択されたσi∈Ｓi,k（１≦ｉ≦ｎ）とを用いて、式（７０）から式（７２）によってメッセージ文Ｍを暗号化した暗号文Ｃが、前記入力部を介して前記復号化装置に入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７３）によってσiを計算して、当該計算結果を前記第３の記憶部に格納し、
前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（７４）によってＭを計算し、
前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数６８】
【数６９】
【数７０】
【数７１】
【数７２】
【数７３】
【数７４】
【請求項１３】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、前記生成された対（π，π-1）を前記記憶部に格納し、
式（７５）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（７６）を満たすものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（７７）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵ＰＫと、ランダムに選択されたｒ∈｛０，１｝k1、σ1∈Ｓ1,k、およびσ2∈Ｓ2,kとを用いて、式（７８）から式（８０）によってメッセージ文Ｍ∈｛０，１｝k2を暗号化した暗号文Ｃが、前記入力部を介して入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８１）を計算して、当該計算結果を前記記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８２）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記記憶部に格納し、
式（８３）を満たすか否かを判定し、
前記式（８３）を満たすと判定された場合は、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数７５】
【数７６】
【数７７】
【数７８】
【数７９】
【数８０】
【数８１】
【数８２】
【数８３】
【請求項１４】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介してメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記記憶部に格納し、
セキュリティパラメータｋと、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから生成された二つの対（π1，π1-1）および（π2，π2-1）と、暗号化鍵ＰＫと、式（８４）を満たす関数族Ｆi（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（８５）を満たすものとする。）とを用いて、式（８６）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（８７）を計算し、当該計算結果を前記記憶部に格納し、
前記取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて式（８８）を計算し、当該計算結果を前記記憶部に格納し、
前記記憶部に格納される情報を用いて、暗号文Ｃを式（８９）に示すように生成することを特徴とする計算機。
【数８４】
【数８５】
【数８６】
【数８７】
【数８８】
【数８９】
【請求項１５】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介してメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記記憶部に格納し、
セキュリティパラメータｋ、ランダム関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋと、落とし戸付き一方向性関数πと落とし戸π-1とから生成された対（π，π-1）と、式（９０）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）とを用いて、式（９１）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（９２）を計算して、当該計算結果を前記記憶部に格納し、
前記入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（９３）を計算して、当該計算結果を前記記憶部に格納し、
前記記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（９４）に示すように生成することを特徴とする計算機。
【数９０】
【数９１】
【数９２】
【数９３】
【数９４】
【請求項１６】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介して、メッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記記憶部に格納し、
セキュリティパラメータｋと、落とし戸付き一方向性関数πと落とし戸π-1とから生成された対（π，π-1）と、式（９５）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（９６）を満たすものとする。）とを用いて、式（９７）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（９８）を計算して、当該計算結果を前記記憶部に格納し、
前記取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて式（９９）を計算して、当該計算結果を前記記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（１００）に示すように生成することを特徴とする計算機。
【数９５】
【数９６】
【数９７】
【数９８】
【数９９】
【数１００】
【請求項１７】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、前記公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成する手順と、
式（１０１）を満たす関数族Ｆiを生成する処理と（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１０２）を満たすものとする。）、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（１０３）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０１】
【数１０２】
【数１０３】
【請求項１８】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、前記公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの公開鍵ｐｋと秘密鍵ｓｋとを生成する手順と、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成する手順と、
式（１０４）を満たす関数族Ｆiを生成する手順と（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、
前記公開鍵ｐｋおよび秘密鍵ｓｋと、前記落とし戸付き一方向性関数と落とし戸との対である（π，π-1）と、前記関数族Ｆiとを用いて、式（１０５）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０４】
【数１０５】
【請求項１９】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成する処理と、
式（１０６）を満たす関数族Ｆiを生成する手順と（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１０７）を満たすものとする。）、
前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（１０８）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０６】
【数１０７】
【数１０８】
【請求項１】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納し、
式（１）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（２）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４）を計算し、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（５）を計算し、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（６）に示すように生成し、
前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７）を計算して、当該計算結果を前記第３の記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、
式（９）を満たすか否かを判定し、
前記式（９）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１】
【数２】
【数３】
【数４】
【数５】
【数６】
【数７】
【数８】
【数９】
【請求項２】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記第１の記憶部に格納し、
落とし戸付き一方向性関数πと落とし戸とπ-1からの対（π，π-1）を生成して、前記生成された対（π，π-1）を前記第１の記憶部に格納し、
式（１０）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（１１）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（１２）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（１３）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（１４）に示すように生成し、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（１５）によってσiを計算して、当該計算結果を前記第３の記憶部に格納し、
前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（１６）によってＭを計算し、
前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１０】
【数１１】
【数１２】
【数１３】
【数１４】
【数１５】
【数１６】
【請求項３】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムであって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記鍵生成部は、
前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから対（π，π-1）を生成し、前記生成された対（π，π-1）を前記第１の記憶部に格納し、
式（１７）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１８）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納し、
前記生成された対（π，π-1）と前記関数族Ｆiとを用いて、式（１９）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信し、
前記暗号化部は、
前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（２０）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（２１）を計算して、当該計算結果を前記第２の記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（２２）に示すように生成し、
前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信し、
前記復号化部は、
前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（２３）を計算して、当該計算結果を前記第３の記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（２４）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納し、
式（２５）を満たすか否かを判定し、
前記式（２５）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする暗号化システム。
【数１７】
【数１８】
【数１９】
【数２０】
【数２１】
【数２２】
【数２３】
【数２４】
【数２５】
【請求項４】
前記暗号化システムは、第１の計算機と、前記第１の計算機と接続される第２の計算機とを備え、
前記第１の計算機は、前記鍵生成装置および前記復号化装置を備え、前記第２の計算機は、前記暗号化装置を備えることを特徴とする請求項１から３のいずれかに記載の暗号化システム。
【請求項５】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（２６）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（２７）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（２８）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（２９）を計算し、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（３０）を計算し、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（３１）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（３２）を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（３３）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、式（３４）を満たすか否かを判定するステップと、
前記復号化部が、前記式（３４）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数２６】
【数２７】
【数２８】
【数２９】
【数３０】
【数３１】
【数３２】
【数３３】
【数３４】
【請求項６】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記第１の記憶部に格納するステップと、
前記鍵生成部が、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成して、前記生成された対（π，π-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（３５）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（３６）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（３７）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（３８）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（３９）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４０）によってσiを計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（４１）によってＭを計算するステップと、
前記復号化部が、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数３５】
【数３６】
【数３７】
【数３８】
【数３９】
【数４０】
【数４１】
【請求項７】
暗号化鍵および復号化鍵を生成する鍵生成装置、メッセージ文を暗号化することによって暗号文を生成する暗号化装置、並びに、前記暗号文を復号化する復号化装置を備える暗号化システムにおける公開鍵暗号化方法であって、
前記鍵生成装置、前記暗号化装置、および前記復号化装置は、互いに接続され、
前記鍵生成装置は、前記暗号化鍵および前記復号化鍵を生成する鍵生成部と、他の装置から情報を取得するための第１の入力部と、他の装置に情報を出力するための第１の出力部と、情報を格納する第１の記憶部と、を備え、
前記暗号化装置は、前記暗号化鍵を用いて、メッセージ文を暗号化する暗号化部と、他の装置から情報を取得するための第２の入力部と、他の装置に情報を出力するための第２の出力部と、情報を格納する第２の記憶部と、を備え、
前記復号化装置は、前記復号化鍵を用いて、暗号文を復号化する復号化部と、他の装置から情報を取得するための第３の入力部と、他の装置に情報を出力するための第３の出力部と、情報を格納する第３の記憶部と、を備え、
前記方法は、
前記鍵生成部が、前記第１の入力部を介して前記鍵生成装置にセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、前記生成された対（π，π-1）を前記第１の記憶部に格納するステップと、
前記鍵生成部が、式（４２）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（４３）を満たすものとする。）、前記生成された関数族Ｆiを前記第１の記憶部に格納するステップと、
前記鍵生成部が、前記生成された対（π，π-1）と前記関数族Ｆiとを用いて、式（４４）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成するステップと、
前記鍵生成部が、前記第１の出力部を介して、前記生成された暗号化鍵ＰＫを前記暗号化装置に送信し、前記生成された復号化鍵ＳＫを前記復号化装置に送信するステップと、
前記暗号化部が、前記第２の入力部を介して前記暗号化装置にメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（４５）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の入力部を介して取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて、式（４６）を計算して、当該計算結果を前記第２の記憶部に格納するステップと、
前記暗号化部が、前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（４７）に示すように生成するステップと、
前記暗号化部が、前記第２の出力部を介して前記生成された暗号文Ｃを前記復号化装置に送信するステップと、
前記復号化部が、前記第３の入力部を介して前記復号化装置に前記暗号文Ｃが入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４８）を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（４９）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記第３の記憶部に格納するステップと、
前記復号化部が、式（５０）を満たすか否かを判定するステップと、
前記復号化部が、前記式（５０）を満たすと判定された場合に、前記Ｍを前記暗号文Ｃのメッセージ文として取得するステップと、を含むことを特徴とする公開鍵暗号化方法。
【数４２】
【数４３】
【数４４】
【数４５】
【数４６】
【数４７】
【数４８】
【数４９】
【数５０】
【請求項８】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、（式５１）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（５２）を満たすものとする。）、前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（５３）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５１】
【数５２】
【数５３】
【請求項９】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成し、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、式（５４）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（５５）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５４】
【数５５】
【請求項１０】
暗号化鍵および復号化鍵を生成する鍵生成装置であって、
前記鍵生成装置は、
他の装置から情報を取得するための入力部と、
他の装置に情報を出力するための出力部と、
情報を格納する記憶部と、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、式（５６）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（５７）を満たすものとする。）、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（５８）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成する鍵生成部と、を備えることを特徴とする鍵生成装置。
【数５６】
【数５７】
【数５８】
【請求項１１】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成し、前記生成された二つの対（π1，π1-1）および（π2，π2-1）を前記記憶部に格納し、
式（５９）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（６０）を満たすものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（６１）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵と、ランダムに選択されたらｒ∈｛０，１｝k1、σ1∈Ｓ1,k、およびσ2∈Ｓ2,kと用いて、式（６２）から式（６４）によってメッセージ文Ｍ∈｛０，１｝k2を暗号化した暗号文Ｃが、前記入力部を介して入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（６５）を計算して、当該計算結果を前記記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（６６）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記記憶部に格納し、
式（６７）を満たすか否かを判定し、
前記式（６７）を満たすと判定された場合は、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数５９】
【数６０】
【数６１】
【数６２】
【数６３】
【数６４】
【数６５】
【数６６】
【数６７】
【請求項１２】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの暗号化鍵ｐｋと復号化鍵ｓｋとを生成して、前記生成された暗号化鍵ｐｋと復号化鍵ｓｋとを前記記憶部に格納し、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成して、前記生成された対（π，π-1）を前記記憶部に格納し、
式（６８）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記暗号化鍵ｐｋおよび復号化鍵ｓｋと、前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（６９）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵と、ランダムに選択されたσi∈Ｓi,k（１≦ｉ≦ｎ）とを用いて、式（７０）から式（７２）によってメッセージ文Ｍを暗号化した暗号文Ｃが、前記入力部を介して前記復号化装置に入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（７３）によってσiを計算して、当該計算結果を前記第３の記憶部に格納し、
前記公開鍵暗号プロトコルΠと前記復号化鍵ＳＫとを用いて式（７４）によってＭを計算し、
前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数６８】
【数６９】
【数７０】
【数７１】
【数７２】
【数７３】
【数７４】
【請求項１３】
暗号化鍵および復号化鍵を生成する鍵生成部と、暗号文を復号化する復号化部とを備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記鍵生成部は、
前記入力部を介してセキュリティパラメータｋが入力された場合に、落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成し、前記生成された対（π，π-1）を前記記憶部に格納し、
式（７５）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（７６）を満たすものとする。）、前記生成された関数族Ｆiを前記記憶部に格納し、
前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（７７）によって暗号化鍵ＰＫと復号化鍵ＳＫとを生成し、
前記復号化部は、
前記暗号化鍵ＰＫと、ランダムに選択されたｒ∈｛０，１｝k1、σ1∈Ｓ1,k、およびσ2∈Ｓ2,kとを用いて、式（７８）から式（８０）によってメッセージ文Ｍ∈｛０，１｝k2を暗号化した暗号文Ｃが、前記入力部を介して入力された場合に、前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８１）を計算して、当該計算結果を前記記憶部に格納し、
前記暗号文Ｃと、前記復号化鍵ＳＫとを用いて、式（８２）によってＭ∈｛０，１｝k2およびｚ∈｛０，１｝k3を計算して、当該計算結果を前記記憶部に格納し、
式（８３）を満たすか否かを判定し、
前記式（８３）を満たすと判定された場合は、前記Ｍを前記暗号文Ｃのメッセージ文として取得することを特徴とする計算機。
【数７５】
【数７６】
【数７７】
【数７８】
【数７９】
【数８０】
【数８１】
【数８２】
【数８３】
【請求項１４】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介してメッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記記憶部に格納し、
セキュリティパラメータｋと、落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから生成された二つの対（π1，π1-1）および（π2，π2-1）と、暗号化鍵ＰＫと、式（８４）を満たす関数族Ｆi（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（８５）を満たすものとする。）とを用いて、式（８６）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（８７）を計算し、当該計算結果を前記記憶部に格納し、
前記取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて式（８８）を計算し、当該計算結果を前記記憶部に格納し、
前記記憶部に格納される情報を用いて、暗号文Ｃを式（８９）に示すように生成することを特徴とする計算機。
【数８４】
【数８５】
【数８６】
【数８７】
【数８８】
【数８９】
【請求項１５】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介してメッセージ文Ｍが入力された場合に、σi∈Ｓi,k（１≦ｉ≦ｎ）をランダムに選択して、前記選択されたσiを前記記憶部に格納し、
セキュリティパラメータｋ、ランダム関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋと、落とし戸付き一方向性関数πと落とし戸π-1とから生成された対（π，π-1）と、式（９０）を満たす関数族Ｆiを生成して（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）とを用いて、式（９１）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（９２）を計算して、当該計算結果を前記記憶部に格納し、
前記入力部を介して取得された暗号化鍵ＰＫと、前記選択されたσiとを用いて、式（９３）を計算して、当該計算結果を前記記憶部に格納し、
前記記憶部に格納される情報を用いて、メッセージ文Ｍの暗号文Ｃを式（９４）に示すように生成することを特徴とする計算機。
【数９０】
【数９１】
【数９２】
【数９３】
【数９４】
【請求項１６】
暗号化鍵を用いてメッセージ文を暗号化することによって暗号文を生成する暗号化部を備える計算機であって、
前記計算機は、さらに、他の装置から情報を取得するための入力部と、他の装置に情報を出力するための出力部と、情報を格納する記憶部と、を備え、
前記暗号化部は、
前記入力部を介して、メッセージ文Ｍ∈｛０，１｝k2が入力された場合に、ｒ∈｛０，１｝k1をランダムに選択し、σ1∈Ｓ1,kおよびσ2∈Ｓ2,kをランダムに選択して、前記選択されたｒと、σ1およびσ2とを前記記憶部に格納し、
セキュリティパラメータｋと、落とし戸付き一方向性関数πと落とし戸π-1とから生成された対（π，π-1）と、式（９５）を満たす関数族Ｆiを生成し（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（９６）を満たすものとする。）とを用いて、式（９７）によって生成された暗号化鍵ＰＫを、前記入力部を介して取得し、
前記取得された暗号化鍵ＰＫと、前記選択されたσ1およびσ2とを用いて、式（９８）を計算して、当該計算結果を前記記憶部に格納し、
前記取得された暗号化鍵ＰＫと、前記選択されたｒと、前記選択されたσ1およびσ2とを用いて式（９９）を計算して、当該計算結果を前記記憶部に格納し、
前記第２の記憶部に格納される情報を用いて、暗号文Ｃを式（１００）に示すように生成することを特徴とする計算機。
【数９５】
【数９６】
【数９７】
【数９８】
【数９９】
【数１００】
【請求項１７】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、前記公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
落とし戸付き一方向性関数π1およびπ2と落とし戸π1-1およびπ2-1とから、二つの対（π1，π1-1）および（π2，π2-1）を生成する手順と、
式（１０１）を満たす関数族Ｆiを生成する処理と（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１０２）を満たすものとする。）、
前記生成された二つの対（π1，π1-1）および（π2，π2-1）と、前記関数族Ｆiとを用いて、式（１０３）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０１】
【数１０２】
【数１０３】
【請求項１８】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、前記公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
ランダムオラクル関数Ｏ1，…，Ｏn（ｎは自然数）のオラクルアクセス（以下、ランダムオラクルと呼ぶ）を前提とした公開鍵暗号方法Π＝（Ｋ，Ｅ，Ｄ）（但し、鍵生成手段Ｋはランダムオラクルに依存しないものとする）の前記鍵生成手段Ｋを用いて、公開鍵暗号方法Πの公開鍵ｐｋと秘密鍵ｓｋとを生成する手順と、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成する手順と、
式（１０４）を満たす関数族Ｆiを生成する手順と（但し、ｆｉσｉは、前記ランダムオラクル関数Ｏiと同一の定義域と値域とを持つものとする。）、
前記公開鍵ｐｋおよび秘密鍵ｓｋと、前記落とし戸付き一方向性関数と落とし戸との対である（π，π-1）と、前記関数族Ｆiとを用いて、式（１０５）によって前記ランダムオラクルに依存しない新たな公開鍵暗号プロトコルΠ'の公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０４】
【数１０５】
【請求項１９】
公開鍵および秘密鍵を生成する鍵生成装置が備える公開鍵秘密鍵生成プログラムであって、
前記鍵生成装置は、プロセッサと、前記プロセッサに接続され、公開鍵秘密鍵生成プログラムを格納するメモリとを備え、
前記プログラムは、
セキュリティパラメータｋを受け付ける手順と、
落とし戸付き一方向性関数πと落とし戸π-1とから、対（π，π-1）を生成する処理と、
式（１０６）を満たす関数族Ｆiを生成する手順と（但し、ｆｉσｉは、各σ1∈S1,k，σ2∈S2,kに対して、式（１０７）を満たすものとする。）、
前記生成された対（π，π-1）と、前記関数族Ｆiとを用いて、式（１０８）によって公開鍵ＰＫと秘密鍵ＳＫとを生成する手順と、を前記プロセッサに実行させることを特徴とする公開鍵秘密鍵生成プログラム。
【数１０６】
【数１０７】
【数１０８】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−１５０００６（Ｐ２０１１−１５０００６Ａ）
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願番号】特願２０１０−９１６７（Ｐ２０１０−９１６７）
【出願日】平成２２年１月１９日（２０１０．１．１９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願日】平成２２年１月１９日（２０１０．１．１９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]