(57)【要約】  【課題】  ランダムオラクルを利用した暗号プロトコルにおけるランダムオラクルの安全な実装を実現すること。  【解決手段】  ランダムオラクルを利用した第一の公開鍵暗号方式Π１が与えられている場合に、第一の公開鍵暗号方式Π１にΠ１で使用されていない暗号ツールを組み合わせることで、第二の公開鍵暗号方式Π２を生成して、受信者側装置１１０と送信者側装置１３０で、第二の公開鍵暗号方式Π２を利用して暗号通信を行う。【選択図】図１
2009276685.tif 000002
【特許請求の範囲】
【請求項１】
ランダム関数へのオラクルアクセス（以下、ランダムオラクル）を利用した第一の暗号プロトコルに、当該第一の暗号プロトコルに含まれない暗号ツールを組み合わせることで、当該第一の暗号プロトコルの安全性証明に必要とされるランダムオラクルの性質を特定した第二の暗号プロトコルを生成すること、
を特徴とする暗号プロトコル生成方法。
【請求項２】
請求項１に記載の暗号プロトコル生成方法であって、
前記暗号ツールは、少なくとも一つ以上の関数であること、
を特徴とする暗号プロトコル生成方法。
【請求項３】
請求項１に記載の暗号プロトコル生成方法であって、
前記暗号ツールは、一方向性置換であること、
を特徴とする暗号プロトコル生成方法。
【請求項４】
請求項１に記載の暗号プロトコル生成方法であって、
前記暗号ツールは、ＫＥＭであること、
を特徴とする暗号プロトコル生成方法。
【請求項５】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
（１）前記受信者側装置が、
ランダムオラクルモデルを利用する第一の公開鍵暗号Π１の鍵生成方法により第一の公開鍵pk及び第一の秘密鍵skを生成するステップと、
PK=（pk,π,Ｆ,Ｏ1,Ｏ2）を第二の公開鍵として公開するステップ（但し、πは、集合Ｘにおける一方向性落とし戸付き置換であり、Ｆは、
【数１】
2009276685.tif 000047
なる擬似ランダム関数であり、Ｏ1及びＯ2はハッシュ関数である）と、
SK=(sk，π-1)を第二の秘密鍵として保管するステップ（但し、π-1は、一方向性落とし戸付き置換πの落とし戸である）と、を備え、
（２）前記送信者側装置が、
メッセージ文Ｍの入力を受け付けるステップと、
ｘをランダムに選ぶステップ（但し、ｘは、
【数２】
2009276685.tif 000048
を満たすものである）と、
前記第二の公開鍵PKを用いて、
【数３】
2009276685.tif 000049
を計算するステップと、
前記ハッシュ関数Ｏ1を用いて、
【数４】
2009276685.tif 000050
を計算するステップと、
前記第一の公開鍵暗号Π１の暗号化手段を用いて、
【数５】
2009276685.tif 000051
を計算するステップと、
前記ハッシュ関数Ｏ2を用いて、
【数６】
2009276685.tif 000052
を計算するステップと、
（ｕ,ｖ,ｗ）をメッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、を備え、
（３）前記受信者側装置が、
暗号文（ｕ,ｖ,ｗ）を受信するステップと、
前記第二の秘密鍵SKを用いて、
【数７】
2009276685.tif 000053
を計算するステップと、
前記ハッシュ関数Ｏ1を用いて、
【数８】
2009276685.tif 000054
を計算するステップと、
前記第一の公開鍵暗号Π１の復号化手段を用いて、
【数９】
2009276685.tif 000055
を計算するステップと、
前記ハッシュ関数Ｏ2を用いて、
【数１０】
2009276685.tif 000056
を検査するステップと、
検査にパスした場合に、（ｕ,ｖ,ｗ）のメッセージ文として、Ｍを出力するステップと、を備えること、
を特徴とする暗号通信方法。
【請求項６】
請求項４に記載の暗号通信方法であって、
前記ハッシュ関数Ｏ1が、秘匿性及びランダム性を満たすものであり、
前記ハッシュ関数Ｏ2が、予測不能性及び秘匿性を満たすものであること、
を特徴とする暗号通信方法。
【請求項７】
請求項４に記載の暗号通信方法であって、
暗号文（ｕ，ｖ，ｗ）の一部であるｗを、
【数１１】
2009276685.tif 000057
により作成するステップと、
復号化処理において、
【数１２】
2009276685.tif 000058
を検査するステップと、
検査にパスした場合に、（ｕ,ｖ,ｗ）のメッセージ文として、Ｍを出力するステップと、を備えること、
を特徴とする暗号通信方法。
【請求項８】
署名者側装置が署名を作成して送信し、検証者側装置が前記署名の正当性を検証する署名通信方法であって、
（１）前記検証者側装置が、
πを公開鍵として公開するステップ（但し、πは、集合Ｘにおける一方向性落とし戸付き置換である）と、
π-1を秘密鍵として保管するステップ（但し、π-1は、一方向性落とし戸付き置換πの落とし戸である）と、を備え
（２）前記署名者側装置が、
ランダムオラクルモデルを利用する第三の署名方法Π３の鍵生成方法により第三の公開鍵pk及び第三の秘密鍵skを生成するステップと、
PK=（pk,Ｆ,Ｏ1,Ｏ2）を第四の公開鍵として公開するステップ（但し、Ｆは、
【数１３】
2009276685.tif 000059
なる擬似ランダム関数であり、Ｏ1及びＯ2はハッシュ関数である）と、
SK=skを第四の秘密鍵として保管するステップと、を備え、
（３）前記署名者側装置が、
メッセージＭの入力を受け付けるステップと、
ｘをランダムに選ぶステップ（但し、ｘは、
【数１４】
2009276685.tif 000060
を満たすものである）と、
前記公開鍵πと前記第四の秘密鍵SKを用いて、
【数１５】
2009276685.tif 000061
を計算するステップと、
前記ハッシュ関数Ｏ1を用いて、
【数１６】
2009276685.tif 000062
を計算するステップと、
前記第三の署名方法Π３の署名作成手段を用いて、
【数１７】
2009276685.tif 000063
を計算するステップと、
前記ハッシュ関数Ｏ2を用いて、
【数１８】
2009276685.tif 000064
を計算するステップと、
（ｕ,ｖ,ｗ）をメッセージ文Ｍの署名文として前記検証者側装置に送信するステップと、を備え、
（４）前記検証者側装置が、
署名文（ｕ,ｖ,ｗ）を受信するステップと、
前記秘密鍵π-1、および、前記第四の公開鍵PKを用いて、
【数１９】
2009276685.tif 000065
を計算するステップと、
前記ハッシュ関数Ｏ1を用いて、
【数２０】
2009276685.tif 000066
を計算するステップと、
前記第三の署名方法Π３の署名検証手段を用いて、
【数２１】
2009276685.tif 000067
を計算するステップと、
前記ハッシュ関数Ｏ2を用いて、
【数２２】
2009276685.tif 000068
を検査するステップと、
ｂ＝１かつ検査にパスすれば（ｕ,ｖ,ｗ）をＭに対する正しい署名文とするステップと、を備えること、
を特徴とする署名通信方法。
【請求項９】
請求項７に記載の署名通信方法であって、
暗号文（ｕ，ｖ，ｗ）の一部であるｗを、
【数２３】
2009276685.tif 000069
により作成するステップと、
署名検証処理において、
【数２４】
2009276685.tif 000070
を検査するステップと、を備えること、
を特徴とする署名通信方法。
【請求項１０】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
（１）前記受信者側装置が、
ランダムオラクルモデルを利用する第五の公開鍵暗号Π５の鍵生成方法により第五の公開鍵pk1及び第五の秘密鍵sk1を生成するステップと、
PK=（pk1,pk2,Ｆ）を第六の公開鍵として公開するステップ（但し、pk2は、鍵配送方法KEMの公開鍵であり、Ｆは、
【数２５】
2009276685.tif 000071
なる擬似ランダム関数である）と、
SK=(sk1，sk2)を第六の秘密鍵として保管するステップ（但し、sk2は、鍵配送方法KEMの秘密鍵である）と、を備え、
（２）前記送信者側装置が、
前記第六の公開鍵PKを用いて、
【数２６】
2009276685.tif 000072
を計算するステップと、
メッセージ文Ｍの入力を受け付けるステップと、
前記第五の公開鍵暗号Π５の暗号化手段を用いて、
【数２７】
2009276685.tif 000073
を計算するステップと、
（ｕ,ｖ）をメッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、を備え、
（３）前記受信者側装置が、
暗号文（ｕ,ｖ）を受信するステップと、
前記第六の秘密鍵SKを用いて、
【数２８】
2009276685.tif 000074
を計算するステップと、
前記第五の公開鍵暗号Π５の復号化手段を用いて、
【数２９】
2009276685.tif 000075
を計算するステップと、
暗号文（ｕ,ｖ）のメッセージ文として、Ｍを出力するステップと、を備えること、
を特徴とする暗号通信方法。
【請求項１１】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
（１）前記受信者側装置が、
ランダムオラクルモデルを利用する第一の公開鍵暗号Π１の鍵生成方法により第一の公開鍵pk及び第一の秘密鍵skを生成する処理と、
PK=（pk,π,Ｆ,Ｏ1,Ｏ2）を第二の公開鍵として公開する処理（但し、πは、集合Ｘにおける一方向性落とし戸付き置換であり、Ｆは、
【数３０】
2009276685.tif 000076
なる擬似ランダム関数であり、Ｏ1及びＯ2はハッシュ関数である）と、
SK=(sk，π-1)を第二の秘密鍵として保管する処理（但し、π-1は、一方向性落とし戸付き置換πの落とし戸である）と、を行い、
（２）前記送信者側装置が、
メッセージ文Ｍの入力を受け付ける処理と、
ｘをランダムに選ぶ処理（但し、ｘは、
【数３１】
2009276685.tif 000077
を満たすものである）と、
前記第二の公開鍵PKを用いて、
【数３２】
2009276685.tif 000078
を計算する処理と、
前記ハッシュ関数Ｏ1を用いて、
【数３３】
2009276685.tif 000079
を計算する処理と、
前記第一の公開鍵暗号Π１の暗号化手段を用いて、
【数３４】
2009276685.tif 000080
を計算する処理と、
前記ハッシュ関数Ｏ2を用いて、
【数３５】
2009276685.tif 000081
を計算する処理と、
（ｕ,ｖ,ｗ）をメッセージ文Ｍの暗号文として前記受信者側装置に送信する処理と、を行い、
（３）前記受信者側装置が、
暗号文（ｕ,ｖ,ｗ）を受信する処理と、
前記第二の秘密鍵SKを用いて、
【数３６】
2009276685.tif 000082
を計算する処理と、
前記ハッシュ関数Ｏ1を用いて、
【数３７】
2009276685.tif 000083
を計算する処理と、
前記第一の公開鍵暗号Π１の復号化手段を用いて、
【数３８】
2009276685.tif 000084
を計算する処理と、
前記ハッシュ関数Ｏ2を用いて、
【数３９】
2009276685.tif 000085
を検査する処理と、
検査にパスした場合に、（ｕ,ｖ,ｗ）のメッセージ文として、Ｍを出力する処理と、を行うこと、
を特徴とする暗号通信システム。
【請求項１２】
請求項１０に記載の暗号通信システムであって、
前記ハッシュ関数Ｏ1が、秘匿性及びランダム性を満たすものであり、
前記ハッシュ関数Ｏ2が、予測不能性及び秘匿性を満たすものであること、
を特徴とする暗号通信システム。
【請求項１３】
請求項１０に記載の暗号通信システムであって、
暗号文（ｕ，ｖ，ｗ）の一部であるｗを、
【数４０】
2009276685.tif 000086
により作成する処理と、
復号化処理において、
【数４１】
2009276685.tif 000087
を検査する処理と、
検査にパスした場合に、（ｕ,ｖ,ｗ）のメッセージ文として、Ｍを出力する処理と、を行うこと、
を特徴とする暗号通信システム。
【請求項１４】
署名者側装置が署名を作成して送信し、検証者側装置が前記署名の正当性を検証する署名通信システムであって、
（１）前記検証者側装置が、
πを公開鍵として公開する処理（但し、πは、集合Ｘにおける一方向性落とし戸付き置換である）と、
π-1を秘密鍵として保管する処理（但し、π-1は、一方向性落とし戸付き置換πの落とし戸である）と、を行い、
（２）前記署名者側装置が、
ランダムオラクルモデルを利用する第三の署名方法Π３の鍵生成方法により第三の公開鍵pk及び第三の秘密鍵skを生成する処理と、
PK=（pk,Ｆ,Ｏ1,Ｏ2）を第四の公開鍵として公開する処理（但し、Ｆは、
【数４２】
2009276685.tif 000088
なる擬似ランダム関数であり、Ｏ1及びＯ2はハッシュ関数である）と、
SK=skを第四の秘密鍵として保管する処理と、を行い、
（３）前記署名者側装置が、
メッセージＭの入力を受け付ける処理と、
ｘをランダムに選ぶ処理（但し、ｘは、
【数４３】
2009276685.tif 000089
を満たすものである）と、
前記公開鍵πと前記第四の秘密鍵SKを用いて、
【数４４】
2009276685.tif 000090
を計算する処理と、
前記ハッシュ関数Ｏ1を用いて、
【数４５】
2009276685.tif 000091
を計算する処理と、
前記第三の署名方法Π３の署名作成手段を用いて、
【数４６】
2009276685.tif 000092
を計算する処理と、
前記ハッシュ関数Ｏ2を用いて、
【数４７】
2009276685.tif 000093
を計算する処理と、
（ｕ,ｖ,ｗ）をメッセージ文Ｍの署名文として前記検証者側装置に送信する処理と、を行い、
（４）前記検証者側装置が、
署名文（ｕ,ｖ,ｗ）を受信する処理と、
前記秘密鍵π-1、および、前記第四の公開鍵PKを用いて、
【数４８】
2009276685.tif 000094
を計算する処理と、
前記ハッシュ関数Ｏ1を用いて、
【数４９】
2009276685.tif 000095
を計算する処理と、
前記第三の署名方法Π３の署名検証手段を用いて、
【数５０】
2009276685.tif 000096
を計算する処理と、
前記ハッシュ関数Ｏ2を用いて、
【数５１】
2009276685.tif 000097
を検査する処理と、
ｂ＝１かつ検査にパスすれば（ｕ,ｖ,ｗ）をＭに対する正しい署名文とする処理と、を行うこと、
を特徴とする署名通信システム。
【請求項１５】
請求項１３に記載の署名通信システムであって、
暗号文（ｕ，ｖ，ｗ）の一部であるｗを、
【数５２】
2009276685.tif 000098
により作成する処理と、
署名検証処理において、
【数５３】
2009276685.tif 000099
を検査する処理と、を行うこと、
を特徴とする署名通信システム。
【請求項１６】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
（１）前記受信者側装置が、
ランダムオラクルモデルを利用する第五の公開鍵暗号Π５の鍵生成方法により第五の公開鍵pk1及び第五の秘密鍵sk1を生成する処理と、
PK=（pk1,pk2,Ｆ）を第六の公開鍵として公開する処理（但し、pk2は、鍵配送方法KEMの公開鍵であり、Ｆは、
【数５４】
2009276685.tif 000100
なる擬似ランダム関数である）と、
SK=(sk1，sk2)を第六の秘密鍵として保管する処理（但し、sk2は、鍵配送方法KEMの秘密鍵である）と、を備え、
（２）前記送信者側装置が、
前記第六の公開鍵PKを用いて、
【数５５】
2009276685.tif 000101
を計算する処理と、
メッセージ文Ｍの入力を受け付ける処理と、
前記第五の公開鍵暗号Π５の暗号化手段を用いて、
【数５６】
2009276685.tif 000102
を計算する処理と、
（ｕ,ｖ）をメッセージ文Ｍの暗号文として前記受信者側装置に送信する処理と、を備え、
（３）前記受信者側装置が、
暗号文（ｕ,ｖ）を受信する処理と、
前記第六の秘密鍵SKを用いて、
【数５７】
2009276685.tif 000103
を計算する処理と、
前記第五の公開鍵暗号Π５の復号化手段を用いて、
【数５８】
2009276685.tif 000104
を計算する処理と、
暗号文（ｕ,ｖ）のメッセージ文として、Ｍを出力する処理と、を行うこと、
を特徴とする暗号通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ランダムオラクルモデルにおける暗号技術に関する。
【背景技術】
【０００２】
公開鍵暗号の安全性については、通常、ランダムオラクルモデル（非特許文献１）、または、標準計算機モデル、において証明される。
【０００３】
ここで、ランダムオラクルモデルでは、全てのパーティ（攻撃者を含む）がランダム関数へ（オラクルとして）アクセスすることが可能である。このように、ランダムオラクルモデルはヒューリスティックなモデルであるが、効率的な安全証明可能な暗号プロトコルの設計が比較的容易であるメリットをもつため、ランダムオラクルモデル上で安全な暗号プロトコルは多く利用されている。
【０００４】
しかし、現実のシステムにおいては、ランダムオラクルの部分は実用的なハッシュ関数に置き換えて利用されるため（非特許文献２）、現実のシステムにおける安全性は完全には保証されない。非特許文献３では、ランダムオラクルの性質の一部を満たすハッシュ関数について記載しているが、（未知の暗号プロトコルを含めて）ランダムオラクルモデル上での安全性を維持しながら実システムに適用するための方法は知られていない。
【０００５】
また、ランダムオラクルの実装に関するネガティブな結果としては、ランダムオラクルモデル上では安全であるが、ランダムオラクルのいかなる関数への置き換えに対しても安全ではなくなる暗号プロトコルが存在することが知られている（非特許文献４）。しかし、このような暗号プロトコルは非常に人為的で、実用的な暗号プロトコルに影響を与えるものではないと考えられている。
【０００６】
【非特許文献１】M. Bellare and P. Rogaway. Random Oracles are Practical: 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, http://www.shoup.net/iso/
【非特許文献３】R. Canetti. Towards realizingrandom oracles: Hash functions that hide all partial information, http://domino.research.ibm.com/comm/ research_projects.nsf/pages/security.Publications.html/
【非特許文献４】R. Canetti et al. Random Oracle Methodology, Revised, 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）等の通信装置１６８と、を備えた一般的なコンピュータ１６０で実現できる。
【００１８】
例えば、記憶部１２０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部１１２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１１１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１２２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１２１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【００１９】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【００２０】
図３は、送信者側装置１３０の概略図である。
【００２１】
図示するように、送信者側装置１３０は、情報を入力する入力部１３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置１３０の各部の制御を行う制御部１３２と、記憶部１４０と、通信回線１５０を介して受信者側装置１１０と通信を行う通信部１４１と、情報を出力する出力部１４２と、を備える。
【００２２】
また、制御部１３２は、乱数を生成する乱数生成部１３３と、一方向関数の演算を行う演算部１３４と、ハッシュ関数の演算を行う関数計算部１３５と、公開鍵暗号の暗号アルゴリズムに従った暗号化処理を行う暗号化部１３６と、暗号化部１３６からの質問に対して回答する疑似ランダム関数計算部１３７と、を有する。
【００２３】
以上に記載した送信者側装置１３０は、例えば、図４に示すような一般的なコンピュータ１６０で実現できる。
【００２４】
例えば、記憶部１４０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部１３２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１３１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１４２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１４１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【００２５】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【００２６】
図５は、第一の実施形態である通信システム１００での処理を示すシーケンス図である。
【００２７】
ここで、本実施形態は、公開鍵暗号システムに関するものであり、ランダムオラクルを利用した第一の公開鍵暗号方式Π１= (K,E,D)が与えられているものとする。ここで、K、E、DはそれぞれΠにおける鍵生成アルゴリズム、暗号化アルゴリズム、復号化アルゴリズムを表す。
【００２８】
また、２つのアルゴリズムE、Dは、ランダムオラクルに対して質問を行い、その答を利用して各々の計算を行うものとする（アルゴリズムKはランダムオラクルを利用しないものとする。）。
【００２９】
そして、本実施形態では、第一の公開鍵暗号方式Π１におけるランダムオラクルを実装することを目的として得られる第二の公開鍵暗号方式Π２を用いて通信を行うものとする。
【００３０】
［鍵生成］
受信者側装置１１０のオペレータである受信者は、受信者側装置１１０の入力部１１１を介してセキュリティパラメータｋを入力し、第一の公開鍵暗号Π１の鍵生成アルゴリズムKの実行を行う鍵生成部１１３を用いて、第一の公開鍵pkと第一の秘密鍵skを生成する（Ｓ１０）。
【００３１】
次に、受信者が入力部１２１を介して指示を入力することで、制御部１１２は、受信者側装置１１０内にある通信部１２１および出力部１２２を用いて、PK=（pk,π,Ｆ,Ｏ1,Ｏ2）を第二の公開鍵として公開し（Ｓ１１）、SK=(sk，π-1)を第二の秘密鍵として記憶部１２０に記憶する（Ｓ１２）。ここで、πは集合Ｘ上の一方向性落とし戸付き置換とし、その落とし戸をπ-1とする。また、Ｆは、
【００３２】
【数５９】
2009276685.tif 000003
【００３３】
なる擬似ランダム関数であり、Ｓｋは、ｋビットの共通鍵である。
【００３４】
また、Ｏ1,Ｏ2はハッシュ関数とする。Ｏ1,Ｏ2は関数計算部１１５で計算されるものとする。
［暗号化］
送信者側装置１３０のオペレータである送信者は、送信者側装置１３０の入力部１３１を介して、メッセージ文Ｍを入力する（Ｓ１３）。
【００３５】
次に、送信者側装置１３０の乱数生成部１３３は、ｘをランダムに選ぶ（Ｓ１４）。
【００３６】
ここで、ｘは、
【００３７】
【数６０】
2009276685.tif 000004
【００３８】
を満たす。
【００３９】
そして、送信者側装置１３０は、ステップＳ１１で公開された受信者の第二の公開鍵PKを、例えば、通信部１４１を介して取得し（Ｓ１５）、演算部１３４が、
【００４０】
【数６１】
2009276685.tif 000005
【００４１】
を計算する（Ｓ１６）。
【００４２】
さらに、関数計算部１０７が、
【００４３】
【数６２】
2009276685.tif 000006
【００４４】
を計算する（Ｓ１７）。
【００４５】
さらに、暗号化部１３６及び疑似ランダム関数計算部１３７が、
【００４６】
【数６３】
2009276685.tif 000007
【００４７】
を計算する（Ｓ１８）。
【００４８】
ここで、暗号化部１３６は、第一の公開鍵暗号方式Π１の暗号アルゴリズムEの処理を行う装置であるが、上述のようにランダムオラクルへ質問を行うことが出来る。もし、暗号化部１３６が、質問ｘを行った場合、擬似ランダム関数計算部１３７は、fs(x)をその答として暗号化部１３６に回答する。
【００４９】
さらに、関数計算部１３５が、
【００５０】
【数６４】
2009276685.tif 000008
【００５１】
を計算する（Ｓ１９）。
【００５２】
そして、送信者側装置１３０は、（ｕ,ｖ,ｗ）をメッセージ文Ｍの暗号文として、例えば、通信部１４１又は出力部１４２を介して、受信者側装置１１０に出力する（Ｓ２０）。
【００５３】
［復号化］
暗号文（ｕ,ｖ,ｗ）を取得した受信者側装置１１０では（Ｓ２１）、演算部１１４が、記憶部１２０に格納されている第二の秘密鍵SKを用いて、
【００５４】
【数６５】
2009276685.tif 000009
【００５５】
を計算する（Ｓ２２）。
【００５６】
さらに、関数計算部１１５が、
【００５７】
【数６６】
2009276685.tif 000010
【００５８】
を計算する（Ｓ２３）。
【００５９】
さらに、復号化部１１６および擬似ランダム関数計算部１１７が、
【００６０】
【数６７】
2009276685.tif 000011
【００６１】
を計算する（Ｓ２４）。
【００６２】
ここで、復号化部１１６は、第一の公開鍵暗号方式Π１の復号アルゴリズムDの処理を行うが、上述したようにランダムオラクルへ質問を行うことが出来る。もし、復号化部１１６が質問ｘを行った場合、擬似ランダム関数計算部１１７は、fs(x)をその答として復号化部１１６に回答する。
【００６３】
さらに、関数計算部１１５および検査部１１８が、
【００６４】
【数６８】
2009276685.tif 000012
【００６５】
を検査する（Ｓ２６）。
【００６６】
そして、検査部１１８は、検査にパスすれば（ｕ,ｖ,ｗ）のメッセージ文として、出力部１２２を介して、メッセージＭを出力する。
【００６７】
なお、以上に記載した公開鍵暗号方法において、暗号文（ｕ，ｖ，ｗ）の一部であるｗを、
【００６８】
【数６９】
2009276685.tif 000013
【００６９】
により作成し、復号化処理において、
【００７０】
【数７０】
2009276685.tif 000014
【００７１】
を検査し、検査にパスすれば（ｕ,ｖ,ｗ）のメッセージ文として、Ｍを出力することに変形することも可能である。
【００７２】
本発明の方法によると、第一の公開鍵暗号方式Π１が一定の安全性基準を満たし、ハッシュ関数Ｏ1が「秘匿性」および「ランダム性」を満たし、かつ、ハッシュ関数Ｏ2が「予測不能性」および「秘匿性」を満たすとき、第二の公開鍵暗号方式Π２は、安全であること証明できる。ここで、一定の安全性基準とは、下記の例外を除いてIND-CCAアタックゲーム（下記の非特許文献５を参照）により定義される安全性である。攻撃者はdecryption oracleへの質問（f,y）に限られており、その答としてDf(sk,y)を受け取ることが出来る。但し、ターゲットとなる暗号文はEＯ(pk,Mb)で与えられる（Ｏはランダムオラクルで、ｂは、
【００７３】
【数７１】
2009276685.tif 000015
【００７４】
を満たす）。
【００７５】
非特許文献５：  M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among notions of security for public-key encryption schemes, http://www.cs.ucsd.edu/users/ mihir/papers/relations.html）
関数に求められる条件のうち、「秘匿性」とは、関数値から入力値に関する一切の情報を計算することが困難であることを意味する。また、「予測不能性」とは、関数の計算を実際に行うことなく、入力値から関数値を予測することが困難であることを意味する。また、「ランダム性」とは、入力値をランダムに選んだ場合、出力値も乱数と区別することが難しい確率分布をもつことを意味する。「背景技術」で述べたように、従来では、ランダムオラクル部分を単にハッシュ関数に置き換えることにより、暗号プロトコルにおけるランダムオラクルの実装を行っていた。この方法では、ランダムオラクルに求められる安全性の条件は暗号プロトコルに依存し、また、安全性の維持のためには置き換えられるハッシュ関数がそれらの条件を満たす必要があり、安全性なランダムオラクルの実装を行うことが難しかった。本実施例の方法では、任意の公開鍵暗号プロトコルに対して、上記の変換を適用することができ、かつ、安全性のために関数Ｏ1，Ｏ2に求められる条件を明確にすることができた。このことは、ランダムオラクルがもつ性質の一部分をピックアップし、かつ、それらを部分的に２つの関数に振り分けることを意味している。これにより、従来よりも弱い（易しい）条件下でランダムオラクルの安全な実装が可能となる。
【００７６】
次に、第一の実施形態の変形例について述べる。
【００７７】
図６は、第一の実施形態である通信システム１００での処理（変形例）を示すシーケンス図である。
【００７８】
この変形例では、従来の疑似ランダム関数の安全性の条件を強化することにより、暗号プロトコルの簡素化（すなわち、高速化）を図るものである。
【００７９】
［鍵生成］
受信者側装置１１０のオペレータである受信者は、受信者側装置１１０の入力部１１１を介してセキュリティパラメータｋを入力し、第一の公開鍵暗号Π１の鍵生成アルゴリズムKの実行を行う鍵生成部１１３を用いて、第一の公開鍵pkと第一の秘密鍵skを生成する（Ｓ３０）。
【００８０】
次に、受信者が入力部１２１を介して指示を入力することで、制御部１１２は、受信者側装置１１０内にある通信部１２１および出力部１２２を用いて、PK=（pk,π,Ｆ）を第二の公開鍵として公開し（Ｓ３１）、SK=(sk，π-1)を第二の秘密鍵として記憶部１２０に記憶する（Ｓ３２）。ここで、πは集合Ｘ上の一方向性落とし戸付き置換とし、その落とし戸をπ-1とする。また、Ｆは、
【００８１】
【数７２】
2009276685.tif 000016
【００８２】
なる擬似ランダム関数であり、Ｓｋは、ｋビットの共通鍵である。
［暗号化］
送信者側装置１３０のオペレータである送信者は、送信者側装置１３０の入力部１３１を介して、メッセージ文Ｍを入力する（Ｓ３３）。
【００８３】
次に、送信者側装置１３０の乱数生成部１３３は、ｓをランダムに選ぶ（Ｓ３４）。
【００８４】
ここで、ｓは、
【００８５】
【数７３】
2009276685.tif 000017
【００８６】
を満たす。
【００８７】
そして、送信者側装置１３０は、ステップＳ３１で公開された受信者の第二の公開鍵PKを、例えば、通信部１４１を介して取得し（Ｓ３５）、演算部１３４が、
【００８８】
【数７４】
2009276685.tif 000018
【００８９】
を計算する（Ｓ３６）。
【００９０】
さらに、暗号化部１３６及び疑似ランダム関数計算部１３７が、
【００９１】
【数７５】
2009276685.tif 000019
【００９２】
を計算する（Ｓ３７）。
【００９３】
ここで、暗号化部１３６は、第一の公開鍵暗号方式Π１の暗号アルゴリズムEの処理を行う装置であるが、上述のようにランダムオラクルへ質問を行うことが出来る。もし、暗号化部１３６が、質問ｘを行った場合、擬似ランダム関数計算部１３７は、fs(x)をその答として暗号化部１３６に回答する。
【００９４】
そして、送信者側装置１３０は、（ｕ,ｖ）をメッセージ文Ｍの暗号文として、例えば、通信部１４１又は出力部１４２を介して、受信者側装置１１０に出力する（Ｓ３８）。
【００９５】
［復号化］
暗号文（ｕ,ｖ）を取得した受信者側装置１１０では（Ｓ３９）、演算部１１４が、記憶部１２０に格納されている第二の秘密鍵SKを用いて、
【００９６】
【数７６】
2009276685.tif 000020
【００９７】
を計算する（Ｓ４０）。
【００９８】
さらに、復号化部１１６および擬似ランダム関数計算部１１７が、
【００９９】
【数７７】
2009276685.tif 000021
【０１００】
を計算して（Ｓ４１）、メッセージ文の復号化を行う。
【０１０１】
ここで、復号化部１１６は、第一の公開鍵暗号方式Π１の復号アルゴリズムDの処理を行うが、上述したようにランダムオラクルへ質問を行うことが出来る。もし、復号化部１１６が質問ｘを行った場合、擬似ランダム関数計算部１１７は、fs(x)をその答として復号化部１１６に回答する。
【０１０２】
以上の変形例において、擬似ランダム関数が「攻撃者がシードｓの如何なる部分情報を得ても、真のランダム関数との区別ができない」なる安全性を満たし、πが能動的攻撃に対して安全であるとき、IND-CCA2安全であることを示すことができる．
以上に記載した第一の実施形態の変形例のさらなる変形例として、次の変形例を挙げる。
【０１０３】
ここでは、下記の非特許文献６に記載の方法のように、第一の公開鍵暗号Π１の復号化アルゴリズムDにおいて、メッセージの復号化にはランダムオラクルを必要としない（暗号文の正当性を検査するためにのみランダムオラクルを使う）ものとする。
【０１０４】
非特許文献６：E. Fujisaki and T. Okamoto, "How to enhance the security of public-key encryption at minimum cost." in Proceedings of Public Key Cryptography, PKC'99, no. 1560 in Lecture Notes in Computer Science, pp. 53--68, Springer-Verlag, 1999.
図７は、第一の実施形態である通信システム１００での処理（変形例）を示すシーケンス図である。
【０１０５】
［鍵生成］
受信者側装置１１０のオペレータである受信者は、受信者側装置１１０の入力部１１１を介してセキュリティパラメータｋを入力し、第一の公開鍵暗号Π１の鍵生成アルゴリズムKの実行を行う鍵生成部１１３を用いて、第一の公開鍵pkと第一の秘密鍵skを生成する（Ｓ５０）。
【０１０６】
次に、受信者が入力部１２１を介して指示を入力することで、制御部１１２は、受信者側装置１１０内にある通信部１２１および出力部１２２を用いて、PK=（pk,π,Ｆ）を第二の公開鍵として公開し（Ｓ５１）、SK=(sk，π-1)を第二の秘密鍵として記憶部１２０に記憶する（Ｓ５２）。ここで、πは集合Ｘ上の一方向性落とし戸付き置換とし、その落とし戸をπ-1とする。また、Ｆは、
【０１０７】
【数７８】
2009276685.tif 000022
【０１０８】
なる擬似ランダム関数であり、Ｓｋは、ｋビットの共通鍵である。
［暗号化］
送信者側装置１３０のオペレータである送信者は、送信者側装置１３０の入力部１３１を介して、メッセージ文Ｍを入力する（Ｓ５３）。
【０１０９】
次に、送信者側装置１３０の乱数生成部１３３は、ｓをランダムに選ぶ（Ｓ５４）。
【０１１０】
ここで、ｓは、
【０１１１】
【数７９】
2009276685.tif 000023
【０１１２】
を満たす。
【０１１３】
そして、送信者側装置１３０は、ステップＳ５１で公開された受信者の第二の公開鍵PKを、例えば、通信部１４１を介して取得し（Ｓ５５）、演算部１３４が、
【０１１４】
【数８０】
2009276685.tif 000024
【０１１５】
を計算する（Ｓ５６）。
【０１１６】
さらに、暗号化部１３６及び疑似ランダム関数計算部１３７が、
【０１１７】
【数８１】
2009276685.tif 000025
【０１１８】
を計算する（Ｓ５７）。
【０１１９】
ここで、暗号化部１３６は、第一の公開鍵暗号方式Π１の暗号アルゴリズムEの処理を行う装置であるが、上述のようにランダムオラクルへ質問を行うことが出来る。もし、暗号化部１３６が、質問ｘを行った場合、擬似ランダム関数計算部１３７は、fs(x)をその答として暗号化部１３６に回答する。
【０１２０】
そして、送信者側装置１３０は、（ｕ,ｖ）をメッセージ文Ｍの暗号文として、例えば、通信部１４１又は出力部１４２を介して、受信者側装置１１０に出力する（Ｓ５８）。
【０１２１】
［復号化］
暗号文（ｕ,ｖ）を取得した受信者側装置１１０では（Ｓ５９）、演算部１１４が、記憶部１２０に格納されている第二の秘密鍵SKを用いて、
【０１２２】
【数８２】
2009276685.tif 000026
【０１２３】
を計算する（Ｓ６０）。
【０１２４】
さらに、復号化部１１６および擬似ランダム関数計算部１１７が、
【０１２５】
【数８３】
2009276685.tif 000027
【０１２６】
を計算する（Ｓ６１）。
【０１２７】
ここで、復号化部１１６は、第一の公開鍵暗号方式Π１の復号アルゴリズムDの処理を行うが、上述したようにランダムオラクルへ質問を行うことが出来る。もし、復号化部１１６が質問ｘを行った場合、擬似ランダム関数計算部１１７は、fs(x)をその答として復号化部１１６に回答する。
【０１２８】
そして、検査部１１８は、
【０１２９】
【数８４】
2009276685.tif 000028
【０１３０】
が成立すれば、例えば出力部１２２を介して、メッセージＭを出力する。
【０１３１】
以上に記載した変形例において、擬似ランダム関数が「攻撃者は、シードｓを計算し、オラクルに対して質問ｘを行って得た答とfs(x)を比較する以外の方法で、真のランダム関数との区別ができない」なる安全性を満たし、πが受動的攻撃に対して安全であるとき、IND-CCA2安全であることが示すことができる。
【０１３２】
（第二の実施形態）
図８は、本発明の第二の実施形態である通信システム２００の概略図である。
【０１３３】
図示するように、通信システム２００は、検証者側装置２１０と、署名者側装置２３０と、を備えており、これらは通信回路２５０に接続されている。
【０１３４】
図９は、検証者側装置２１０の概略図である。
【０１３５】
図示するように、検証者側装置２１０は、情報を入力する入力部２１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、検証者側装置２１０の各部の制御を行う制御部２１２と、記憶部２２０と、通信回線２５０を介して署名者側装置２３０と通信を行う通信部２２１と、情報を出力する出力部２２２と、を備える。
【０１３６】
また、制御部２１２は、公開鍵及び秘密鍵を生成する鍵生成部２１３と、一方向関数の演算を行う演算部２１４と、ハッシュ関数の演算を行う関数計算部２１５と、公開鍵暗号の復号アルゴリズムに従い復号処理を行う検証部２１６と、検証部２１６からの質問に対して答えを回答する疑似ランダム関数計算部２１７と、復号結果を検査する検査部２１８と、を有する。
【０１３７】
以上に記載した検証者側装置２１０は、例えば、図４に示すような一般的なコンピュータ１６０で実現できる。
【０１３８】
例えば、記憶部２２０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部２１２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部２１１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部２２２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部２２１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０１３９】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０１４０】
図１０は、署名者側装置２３０の概略図である。
【０１４１】
図示するように、署名者側装置２３０は、情報を入力する入力部２３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、署名者側装置２３０の各部の制御を行う制御部２３２と、記憶部２４０と、通信回線２５０を介して検証者側装置２１０と通信を行う通信部２４１と、情報を出力する出力部２４２と、を備える。
【０１４２】
また、制御部２３２は、公開鍵暗号方式に従った公開鍵及び秘密鍵の生成を行う鍵生成部２３３と、乱数を生成する乱数生成部２３４と、一方向関数の演算を行う演算部２３５と、ハッシュ関数の演算を行う関数計算部２３６と、公開鍵暗号の暗号アルゴリズムに従った暗号化処理を行う署名部２３７と、暗号化部２３７からの質問に対して回答する疑似ランダム関数計算部２３８と、を有する。
【０１４３】
以上に記載した署名者側装置２３０は、例えば、図４に示すような一般的なコンピュータ１６０で実現できる。
【０１４４】
例えば、記憶部２４０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部２３２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部２３１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部２４２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部２４１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０１４５】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０１４６】
図１１は、第二の実施形態である通信システム２００での処理を示すシーケンス図である。
【０１４７】
本実施形態は、文書認証システムに関するものであり、ランダムオラクルを利用した第三の署名暗号方式Π３= (K,S,V)が与えられているものとする。ここで、K、S、VはそれぞれΠ３における鍵生成アルゴリズム、署名アルゴリズム、検証アルゴリズムを表す。また、２つのアルゴリズムS、Vは、ランダムオラクルに対して質問を行い、その答を利用して各々の計算を行うものとする（アルゴリズムKはランダムオラクルを利用しないものとする。）。
【０１４８】
また、本実施形態では、第三の署名暗号方式Π３におけるランダムオラクルを実装することを目的として得られる第四の署名暗号方式Π４を用いて署名、検証が行われる。
【０１４９】
［鍵生成］
署名者側装置２３０のオペレータである署名者は、署名者側装置２３０の入力部２３１を介して、セキュリティパラメータｋを入力し、鍵生成部２３３を用いて、第三の署名暗号方式Π３の鍵生成アルゴリズムKに従って、第三の公開鍵pkと第三の秘密鍵skを生成する（Ｓ７０）。
【０１５０】
次に、署名者は、署名者側装置２３０の通信部２４１および出力部２４２を介して、PK=（pk,Ｆ,Ｏ1,Ｏ2）を第四の公開鍵として公開し（Ｓ７１）、SK= skを第四の秘密鍵として記憶部２４０に保管する（Ｓ７２）。ここで、Ｆは、
【０１５１】
【数８５】
2009276685.tif 000029
【０１５２】
なる擬似ランダム関数であり、Ｓｋは、ｋビットの共通鍵である。
【０１５３】
また、Ｏ1,Ｏ2はハッシュ関数であり、Ｏ1,Ｏ2は関数計算部２３６で計算されるものとする。
【０１５４】
次に、検証者側装置２１０のオペレータである検証者が、入力部２１１を介して、指示を入力することで、鍵生成部２１３は、一方向性置換πを生成し、例えば、通信部２２１又は出力部２２２を介して公開鍵として公開する（Ｓ７３）。また、落とし戸であるπ-1は秘密鍵として記憶部２２０に保管する（Ｓ７４）。
【０１５５】
［署名］
署名者は、署名者側装置２３０の入力部２３１を介して、メッセージ文Ｍを入力する（Ｓ７５）。
【０１５６】
次に、乱数生成部２３４は、ｘをランダムに選ぶ（Ｓ７６）。ここで、ｘは、
【０１５７】
【数８６】
2009276685.tif 000030
【０１５８】
を満たす。
【０１５９】
さらに、公開された検証者の公開鍵πを取得する（Ｓ７７）。
【０１６０】
そして、演算部２３５が、
【０１６１】
【数８７】
2009276685.tif 000031
【０１６２】
を計算する（Ｓ７８）。
【０１６３】
さらに、関数計算部２３６が、
【０１６４】
【数８８】
2009276685.tif 000032
【０１６５】
を計算する（Ｓ７９）。
【０１６６】
さらに、署名部２３７および擬似ランダム関数計算部２３８が、
【０１６７】
【数８９】
2009276685.tif 000033
【０１６８】
を計算する（Ｓ８０）。
【０１６９】
ここで、署名部２３７は、第三の署名方式Π３の署名アルゴリズムSの処理を行うが、上述のように、ランダムオラクルへ質問を行うことが出来る。もし、署名部２３７が質問ｘを行った場合、擬似ランダム関数計算部２３８は、fs(x)をその答として署名部２３７に回答する。
【０１７０】
さらに、関数計算部２３６が、
【０１７１】
【数９０】
2009276685.tif 000034
【０１７２】
を計算する（Ｓ８１）。
【０１７３】
そして、署名部２３７は、（ｕ,ｖ,ｗ）をメッセージ文Ｍの署名文として、Ｍと共に通信部２４１または出力部２４２を介して、検証者側装置２１０に出力する（Ｓ８２）。
【０１７４】
［検証］
出力された（Ｍ，（ｕ,ｖ,ｗ））を取得した検証者側装置２１０では（Ｓ８３）、演算部２１４が、記憶部２２０に格納されている秘密鍵π-1を用いて、
【０１７５】
【数９１】
2009276685.tif 000035
【０１７６】
を計算する（Ｓ８４）。
【０１７７】
さらに、関数計算部２１５が、
【０１７８】
【数９２】
2009276685.tif 000036
【０１７９】
を計算する（Ｓ８５）。
【０１８０】
さらに、検証部２１８および擬似ランダム関数計算部２１７が、
【０１８１】
【数９３】
2009276685.tif 000037
【０１８２】
を計算する（Ｓ８６）。
【０１８３】
ここで、検証部２１６は、第三の署名方式Π３の検証アルゴリズムVの処理を行うが、上述のようにランダムオラクルへ質問を行うことが出来る。もし、検証部２１６が質問ｘを行った場合、擬似ランダム関数計算部２１７は、fs(x)をその答として検証部２１６に回答する。
【０１８４】
さらに、関数計算部２１５および検査部２１８が、
【０１８５】
【数９４】
2009276685.tif 000038
【０１８６】
を検査する（Ｓ８７）。
【０１８７】
そして、検査部２１８は、ｂ＝１であり、かつ、検査にパスすれば（ｕ,ｖ,ｗ）をメッセージ文Ｍの署名として認証し、出力部２２２を介して「１」を出力する（Ｓ８８）。
【０１８８】
以上の実施形態において、署名文（ｕ，ｖ，ｗ）の一部であるｗを、
【０１８９】
【数９５】
2009276685.tif 000039
【０１９０】
により作成し、ステップＳ４７の処理において、
【０１９１】
【数９６】
2009276685.tif 000040
【０１９２】
を検査する形に変形することも可能である。
【０１９３】
本実施形態の通信システム２００では、通常のディジタル署名による文書認証とは異なり、検証者側でも公開鍵と秘密鍵を準備する必要がある。よって、署名者が署名の検証者を制限したい場合などに適する。
【０１９４】
また、本実施形態の通信システム２００は、ランダムオラクルの実装の意味において第一の実施形態と同様の効果を得る。
【０１９５】
以上に記載した実施形態では、ユーザが各々の装置を利用して暗号通信や文書認証を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、会員用情報配信システム、コンテンツ配信システム、など、様々なシステムに適用することが可能である。
【０１９６】
また、本実施形態における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、ＣＰＵと、データのやりとりを行うものであっても良い。
【０１９７】
（第三の実施形態）
図１２は、本発明の第三の実施形態である通信システム３００の概略図である。
【０１９８】
図示するように、通信システム３００は、受信者側装置３１０と、送信者側装置３３０と、を備えており、これらは通信回路３５０に接続されている。
【０１９９】
図１３は、受信者側装置３１０の概略図である。
【０２００】
図示するように、受信者側装置３１０は、情報を入力する入力部３１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置３１０の各部の制御を行う制御部３１２と、記憶部３２０と、通信回線３５０を介して送信者側装置３３０と通信を行う通信部３２１と、情報を出力する出力部３２２と、を備える。
【０２０１】
また、制御部３１２は、公開鍵及び秘密鍵を生成する鍵生成部３１３と、鍵配送方式に従った復号化処理を行う鍵配送復号化部３１４と、公開鍵暗号の復号アルゴリズムに従い復号処理を行う復号化部３１５と、復号化部３１５からの質問に対して答えを回答する疑似ランダム関数計算部３１６と、を有する。
【０２０２】
以上に記載した受信者側装置３１０は、例えば、図４に示すような一般的なコンピュータ１６０で実現できる。
【０２０３】
例えば、記憶部３２０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部３１２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部３１１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部３２２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部３２１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０２０４】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０２０５】
図１４は、送信者側装置３３０の概略図である。
【０２０６】
図示するように、送信者側装置３３０は、情報を入力する入力部３３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置３３０の各部の制御を行う制御部３３２と、記憶部３４０と、通信回線３５０を介して受信者側装置３１０と通信を行う通信部３４１と、情報を出力する出力部３４２と、を備える。
【０２０７】
また、制御部３３２は、鍵配送方式に従った暗号化処理を行う鍵配送暗号化部３３３と、公開鍵暗号の暗号アルゴリズムに従った暗号化処理を行う暗号化部３３４と、暗号化部３３４からの質問に対して回答する疑似ランダム関数計算部３３５と、を有する。
【０２０８】
以上に記載した送信者側装置３３０は、例えば、図４に示すような一般的なコンピュータ１６０で実現できる。
【０２０９】
例えば、記憶部３４０は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、制御部３３２は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部３３１は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部３４２は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部３４１は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０２１０】
この所定のプログラムは、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読書装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０２１１】
図１５は、第三の実施形態である通信システム３００での処理を示すシーケンス図である。
【０２１２】
本実施形態は、公開鍵暗号システムに関するものであり、ランダムオラクルを利用した第五の公開鍵暗号方式Π５= (K,E,D)が与えられているものとする。
【０２１３】
ここで、K、E、Dはそれぞれ第五の公開鍵暗号方式Π５における鍵生成アルゴリズム、暗号化アルゴリズム、復号化アルゴリズムを表す。
【０２１４】
また、２つのアルゴリズムE、Dは、ランダムオラクルに対して質問を行い、その答を利用して各々の計算を行うものとする（アルゴリズムKはランダムオラクルを利用しないものとする。）。
【０２１５】
そして、本実施形態では、第五の公開鍵暗号方式Π５におけるランダムオラクルを実装することを目的として得られる第六の公開鍵暗号方式Π６を用いて通信を行う。
【０２１６】
［鍵生成］
受信者側装置３１０のオペレータである受信者は、入力部３１１を介して、セキュリティパラメータｋを入力し、第五の公開鍵暗号方式Π５の鍵生成アルゴリズムKの実行を行う鍵生成部３１３が、第五の公開鍵pk1と第五の秘密鍵sk1を生成する（Ｓ９０）。
【０２１７】
そして、受信者は、受信者側装置３１０の通信部３２１および出力部３２２を介して、PK=（pk1,pk2,Ｆ）を第六の公開鍵として公開し（Ｓ９１）、SK=(sk1，sk2)を第六の秘密鍵として記憶部３２０に保管する（Ｓ９２）。
【０２１８】
ここで、pk2およびsk2は鍵配送方式KEMの公開鍵および秘密鍵を表し、予め記憶部３２０に記憶されているものとする。
【０２１９】
また、Ｆは、
【０２２０】
【数９７】
2009276685.tif 000041
【０２２１】
なる擬似ランダム関数とする。
【０２２２】
［暗号化］
送信者側装置３３０のオペレータである送信者は、送信者側装置３３０の入力部３３１を介して、メッセージ文Ｍを入力する（Ｓ９３）。
【０２２３】
次に、送信者側装置３３０の鍵配送暗号化部３３３は、ステップＳ５１で公開された第六の公開鍵PKを取得し（Ｓ９４）、
【０２２４】
【数９８】
2009276685.tif 000042
【０２２５】
を計算する（Ｓ９５）。ここで、KEM.Enc(pk2)は該鍵配送方法KEMの暗号化方法を表し、公開鍵pk2の入力により鍵および（その鍵の）暗号文の組を出力する。
【０２２６】
さらに、暗号化部３３４および擬似ランダム関数計算部３３５が、
【０２２７】
【数９９】
2009276685.tif 000043
【０２２８】
を計算する（Ｓ９６）。
【０２２９】
ここで、暗号化部３３４は、第五の公開鍵暗号Π５の暗号アルゴリズムEの処理を行うが、上述のように、ランダムオラクルへ質問を行うことが出来る。もし、暗号化部３３４が質問ｘを行った場合、擬似ランダム関数計算部３３５は、fs(x)をその答として暗号化部３３４に回答する。
【０２３０】
そして、送信者側装置３３０は、（ｕ,ｖ）をメッセージ文Ｍの暗号文として、通信部３４１または出力部３４２を介して、受信者側装置３１０に出力する（Ｓ９７）。
【０２３１】
［復号化］
出力された暗号文（ｕ,ｖ）を受信した受信者側装置３１０では（Ｓ９８）、鍵配送復号化部３１４が、記憶部３２０に格納されている第六の秘密鍵SKを用いて、
【０２３２】
【数１００】
2009276685.tif 000044
【０２３３】
を計算する（Ｓ９９）。
【０２３４】
ここで、KEM.Dec(sk2,u)は鍵配送方式KEMの復号化方法を表し、秘密鍵sk2および暗号文の入力により対応する鍵を出力する。
【０２３５】
さらに、復号化部３１５および擬似ランダム関数計算部３１６が、
【０２３６】
【数１０１】
2009276685.tif 000045
【０２３７】
を計算する（Ｓ１００）。
【０２３８】
ここで、復号化部３１５は、第五の公開鍵暗号Π５の復号アルゴリズムDの処理を行うが、上述のように、ランダムオラクルへ質問を行うことが出来る。もし、復号化部３１５が質問ｘを行った場合、擬似ランダム関数計算部３１６はfs(x)をその答として復号化部３１５に回答する。
【０２３９】
そして、復号化部３１５は、（ｕ,ｖ）のメッセージ文として、出力部３２２を介して、Ｍを出力する。
【０２４０】
本実施形態によれば、第五の公開鍵暗号方式Π５が一定の安全性基準を満たし、鍵配送方式KEMがIND-CCA2安全でありとき、本実施形態における第六の公開鍵暗号方式Π６は、IND-CCA2安全であることを証明できる。
【０２４１】
ここで、一定の安全性基準とは、下記の例外を除いてIND-CCAアタックゲーム（上述の、非特許文献５を参照）により定義される安全性である。攻撃者はdecryption oracleに対して、質問（f,y）を行うことが許されており、その答としてDf(sk,y)を受け取ることが出来る。但し、ターゲットとなる暗号文はEＯ(pk,Mb)で与えられる（Ｏはランダムオラクルで、ｂは、
【０２４２】
【数１０２】
2009276685.tif 000046
【０２４３】
を満たす。
【図面の簡単な説明】
【０２４４】
【図１】第一の実施形態である通信システムの概略図。
【図２】受信者側装置の概略図。
【図３】送信者側装置の概略図。
【図４】コンピュータの概略図。
【図５】第一の実施形態である通信システムでの処理を示すシーケンス図。
【図６】第一の実施形態である通信システムでの処理（変形例）を示すシーケンス図。
【図７】第一の実施形態である通信システムでの処理（変形例）を示すシーケンス図。
【図８】第二の実施形態である通信システムの概略図。
【図９】検証者側装置の概略図。
【図１０】署名者側装置の概略図。
【図１１】第二の実施形態である通信システムでの処理を示すシーケンス図。
【図１２】第三の実施形態である通信システムの概略図。
【図１３】受信者側装置の概略図。
【図１４】送信者側装置の概略図。
【図１５】第三の実施形態である通信システムでの処理を示すシーケンス図。
【符号の説明】
【０２４５】
１００、２００、３００  通信システム
１１０、３１０  受信者側装置
２１０  検証者側装置
１１１、２１１、３１１  入力部
１１２、２１２、３１２  制御部
１２０、２２０、３２０  記憶部
１２１、２２１、３２１  通信部
１２２、２２２、３２２  出力部
１３０、３３０  送信者側装置
２３０  署名者側装置
１３１、２３１、３３１  入力部
１３２、２３２、３３２  制御部
１４０、２４０、３４０  記憶部
１４１、２４１、３４１  通信部
１４２、２４２、３４２  出力部
【図１】
2009276685.tif 000105
【図２】
2009276685.tif 000106
【図３】
2009276685.tif 000107
【図４】
2009276685.tif 000108
【図５】
2009276685.tif 000109
【図６】
2009276685.tif 000110
【図７】
2009276685.tif 000111
【図８】
2009276685.tif 000112
【図９】
2009276685.tif 000113
【図１０】
2009276685.tif 000114
【図１１】
2009276685.tif 000115
【図１２】
2009276685.tif 000116
【図１３】
2009276685.tif 000117
【図１４】
2009276685.tif 000118
【図１５】
2009276685.tif 000119