(57)【要約】【課題】公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な公開鍵暗号通信技術を提供する。【解決手段】送信者側装置１００は、暗号文を作成する際に用いたランダムオラクルとしてのランダム関数への入力値（メッセージに限定されない）に関する部分情報を、暗号文から計算することが困難となるように、暗号文を作成する。また、ランダム関数への入力値を知っていることを証明する証明データを、暗号文の一部として作成する。そして暗号文を受信者側装置２００に送信する。受信者側装置２００は、受信した暗号文に含まれている証明データの正しく検証できた場合に、この暗号文の復号結果を出力する。【選択図】図１
2004126514.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置が、ランダム関数および受信者の公開鍵を用いてメッセージの暗号文を作成し、これを受信者側装置へ送信すると共に、前記受信者側装置が、前記ランダム関数および前記公開鍵と対の秘密鍵を用いて前記送信者側装置より受信した前記暗号文を復号化する公開鍵暗号通信方法であって、
前記送信者側装置は、
前記暗号文から前記ランダム関数への入力値に関する部分情報が秘匿されるように前記暗号文を作成し、前記暗号文を前記受信者側装置へ送信すること
を特徴とする公開鍵暗号通信方法。
【請求項２】
請求項１記載の公開鍵暗号通信方法であって、
前記送信者側装置は、
前記暗号文から前記ランダム関数への入力値に関する部分情報が秘匿されるように、且つ、前記入力値を知っていることを証明する証明データを含むように、前記暗号文を作成し、
前記受信者側装置は、
前記送信者側装置より受信した前記暗号文に含まれている前記証明データの正当性を確認し、前記正当性が確認された場合にのみ前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項３】
請求項２記載の公開鍵暗号通信方法であって、
前記受信者側装置は、
前記証明データを含む前記暗号文と前記ランダム関数とを用いて、前記証明データの正当性を確認すること
を特徴とする公開鍵暗号通信方法。
【請求項４】
請求項２記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数１】
2004126514.tif 000073
であり、
前記公開鍵は、
【数２】
2004126514.tif 000074
であり（但し、Ｇは有限アーベル群を表わし、Ｇの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｎは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい）、
前記送信者側装置は、
メッセージｍ∈｛０，１｝ｎに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【数３】
2004126514.tif 000075
を計算して（但し、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する）、その結果（ｕ，ｖ，ｗ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数４】
2004126514.tif 000076
なる（ｒ１’，ｒ２’）を計算して（但し、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｒ１’，ｒ２’のビット長は既知とする）、
【数５】
2004126514.tif 000077
が成立することを確認することで、前記証明データの正当性を確認し、
前記確認に成功した場合にのみ、ｍ’を、
【数６】
2004126514.tif 000078
により計算し（但し、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する）、前記暗号文（ｕ，ｖ，ｗ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項５】
請求項２記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数７】
2004126514.tif 000079
であり、
前記公開鍵は、
【数８】
2004126514.tif 000080
であり（但し、Ｚｐの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｎは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい）、
前記送信者側装置は、
メッセージｍ∈｛０，１｝ｎに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【数９】
2004126514.tif 000081
を計算して（但し、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する）、その結果（ｕ，ｖ，ｗ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数１０】
2004126514.tif 000082
なる（ｒ１’，ｒ２’）を計算して（但し、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｒ１’，ｒ２’のビット長は既知とする）、
【数１１】
2004126514.tif 000083
が成立することを確認することで、前記証明データの正当性を確認し、
前記確認に成功した場合にのみ、ｍ’を
【数１２】
2004126514.tif 000084
により計算し（但し、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する）、前記暗号文（ｕ，ｖ，ｗ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項６】
請求項１記載の公開鍵暗号通信方法であって、
前記送信者側装置は、
前記暗号文の作成に先立って、前記ランダム関数への入力値を十分に大きな集合の中から一様に選ぶこと
を特徴とする公開鍵暗号通信方法。
【請求項７】
請求項６記載の公開鍵暗号通信方法であって、
前記送信者側装置は、
前記メッセージを知ることなく前記暗号文を作成することが困難となるように前記暗号文を作成すること
を特徴とする公開鍵暗号通信方法。
【請求項８】
請求項６記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数１３】
2004126514.tif 000085
であり、
前記公開鍵は、
【数１４】
2004126514.tif 000086
であり（但し、Ｇは有限アーベル群を表わし、｛０，１｝ｋの元をＧの元とみなす１対１対応があるものとする）、
前記送信者側装置は、
メッセージｍ∈｛０，１｝ｋ０に対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【数１５】
2004126514.tif 000087
を計算して、その結果（ｕ，ｖ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数１６】
2004126514.tif 000088
なる（ｍ’，ｒ１’，ｒ２’）を計算して（但し、ｍ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｍ’，ｒ１’，ｒ２’のビット長は既知とする）、
【数１７】
2004126514.tif 000089
が成立することを確認し、
前記確認に成功した場合にのみ、ｍ’を前記暗号文（ｕ，ｖ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項９】
請求項６記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数１８】
2004126514.tif 000090
であり、
前記公開鍵は、
【数１９】
2004126514.tif 000091
であり（但し、Ｇは有限アーベル群を表わし、｛０，１｝ｋの元をＧの元とみなす１対１対応があるものとする）、
前記送信者側装置は、
メッセージｍに対して、乱数ｒ０∈｛０，１｝ｋ０、ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、Ｋ＝Ｆ（ｚ）として、
【数２０】
2004126514.tif 000092
を計算して（但し、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する）、その結果（ｕ，ｖ，ｗ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数２１】
2004126514.tif 000093
なる（ｚ’，ｒ１’，ｒ２’）を計算して（但し、ｚ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｚ’，ｒ１’，ｒ２’のビット長は既知とする）、
【数２２】
2004126514.tif 000094
が成立することを確認し、
前記確認に成功した場合にのみ、Ｋ’＝Ｆ（ｚ’）として、
【数２３】
2004126514.tif 000095
によりｍ’を計算し（但し、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する）、このｍ’を前記暗号文（ｕ，ｖ，ｗ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項１０】
請求項６記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数２４】
2004126514.tif 000096
であり、
前記公開鍵は、
【数２５】
2004126514.tif 000097
であり（但し、｜ｑ｜＝ｋ＋１とする）、
前記送信者側装置は、
メッセージｍ∈｛０，１｝ｋ０に対して、乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【数２６】
2004126514.tif 000098
を計算して、その結果（ｕ，ｖ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数２７】
2004126514.tif 000099
なる（ｍ’，ｒ１’，ｒ２’）を計算して（但し、ｍ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｍ’，ｒ１’，ｒ２’のビット長は既知とする）、
【数２８】
2004126514.tif 000100
が成立することを確認し、
前記確認に成功した場合にのみ、ｍ’を前記暗号文（ｕ，ｖ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項１１】
請求項６記載の公開鍵暗号通信方法であって、
前記秘密鍵は、
【数２９】
2004126514.tif 000101
であり、
前記公開鍵は、
【数３０】
2004126514.tif 000102
であり（但し、Ｇはｑ個の元からなる乗法群Ｚｐ＊の部分群を意味し、｜ｐ｜＝ｋとする）、
前記送信者側装置は、
メッセージｍに対して、乱数ｚ∈｛０，１｝ｋ０、ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を、ｚ‖ｒ１‖ｒ２が群Ｇの元となるように選び、Ｋ＝Ｆ（ｚ）として、
【数３１】
2004126514.tif 000103
を計算して（但し、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する）、その結果（ｕ，ｖ，ｗ）を前記暗号文とし、
前記受信者側装置は、
前記秘密鍵を用いて、
【数３２】
2004126514.tif 000104
なる（ｚ’，ｒ１’，ｒ２’）を計算して（但し、ｚ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｚ’，ｒ１’，ｒ２’のビット長は既知とする）、
【数３３】
2004126514.tif 000105
が成立することを確認し、
前記確認に成功した場合にのみ、Ｋ’＝Ｆ（ｚ’）として、
【数３４】
2004126514.tif 000106
によりｍ’を計算し（但し、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する）、このｍ’を前記暗号文（ｕ，ｖ，ｗ）のメッセージとすることで、前記暗号文の復号化結果を出力すること
を特徴とする公開鍵暗号通信方法。
【請求項１２】
送信者側装置が、ハッシュ関数および受信者の公開鍵を用いてメッセージの暗号文を作成し、これを受信者側装置へ送信すると共に、前記受信者側装置が、前記ハッシュ関数および前記公開鍵と対の秘密鍵を用いて前記送信者側装置より受信した前記暗号文を復号化する公開鍵暗号通信方法であって、
前記暗号文を作成するための用いた前記ハッシュ関数からの出力値と、前記暗号文から、前記メッセージを計算可能であること
を特徴とする公開鍵暗号通信方法。
【請求項１３】
請求項４、８または９記載の公開鍵暗号通信方法であって、
前記受信者側装置は、
前記公開鍵および前記秘密鍵を生成して、公開情報（ｇ，ｈ）を公開すること
を特徴とする公開鍵暗号通信方法。
【請求項１４】
請求項５、１０または１１記載の公開鍵暗号通信方法であって、
前記受信者側装置は、
前記公開鍵および前記秘密鍵を生成して、公開情報（ｐ，ｇ，ｈ）を公開すること
を特徴とする公開鍵暗号通信方法。
【請求項１５】
ランダム関数および受信者の公開鍵を用いてメッセージの暗号文を作成し、これを受信者側装置へ送信する送信者側装置であって、
前記暗号文から前記ランダム関数への入力値に関する部分情報が秘匿されるように前記暗号文を作成する手段と、
前記暗号文を前記受信者側装置へ送信する手段と、を有すること
を特徴とする送信者側装置。
【請求項１６】
請求項１５記載の送信者側装置より受信した暗号文を、当該暗号文の作成に用いられたランダム関数および公開鍵と対の秘密鍵を用いて復号化する手段を有すること
を特徴とする受信者側装置。
【請求項１７】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、前記コンピュータに実行されることにより、
ランダム関数および受信者の公開鍵を用いてメッセージの暗号文を作成し、これを受信者側装置へ送信する送信者側装置を、前記コンピュータ上に構築し、
前記送信者側装置は、
前記暗号文から前記ランダム関数への入力値に関する部分情報が秘匿されるように前記暗号文を作成する手段と、
前記暗号文を前記受信者側装置へ送信する手段と、を有すること
を特徴とするプログラム。
【請求項１８】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、前記コンピュータに実行されることにより、
請求項１７記載のプログラムによって実現された送信者側装置より受信した暗号文を、当該暗号文の作成に用いられたランダム関数および公開鍵と対の秘密鍵を用いて復号化する手段を有する受信者側装置を、前記コンピュータ上に構築すること
を特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号通信技術に関する。特に、強化された適応的選択暗号文攻撃に対して強秘匿であることが証明可能な公開鍵暗号を用いた暗号通信技術に関する。また、ランダムオラクル（関数）に対して、暗号の攻撃者が不正な仕掛けを設けた場合においても、安全性が証明できる公開鍵暗号を用いた暗号通信技術に関する。
【０００２】
【従来の技術】
現在、公開鍵暗号では非特許文献１で述べられているように、適応的選択暗号文攻撃に対して強秘匿（ＩＮＤ（Ｉｎｄｉｓｔｉｎｇｕｉｓｈａｂｉｌｉｔｙ）−ＣＣＡ２（Ａｄａｐｔｉｖｅ　Ｃｈｏｓｅｎ−Ｃｉｐｈｅｒｔｅｘｔ　Ａｔｔａｃｋ））であることが最も安全であると考えられている。
【０００３】
ＩＮＤ−ＣＣＡ２の意味において安全であることが証明可能な公開鍵暗号方式は、大きく２つに分類される。１つは、ランダムオラクル（入力値に対しランダムな値を正しく出力する）を前提とした計算機モデル上で安全性の証明を行うものである。ランダムオラクルという非現実的な仮定を必要とするものの、実用性に優れる公開鍵暗号方法を実現することが可能である。もう１つは、標準的計算モデル上で安全性の証明を行うものである。前者に比べると効率面で劣るが、実システム上で安全性証明が可能であるメリットを持つ。
【０００４】
ランダムオラクルを前提とした計算機モデル上でＩＮＤ−ＣＣＡ２であることが証明可能な実用的暗号方法としては、非特許文献２に記載されている暗号方法や、非特許文献３に記載されている暗号方法や、非特許文献４に記載されている暗号方法などが知られている。
【０００５】
一方、標準的計算機モデル上でＩＮＤ−ＣＣＡ２であることが証明可能な実用的暗号方法としては、非特許文献５に記載されている暗号方法が知られている。
【０００６】
【非特許文献１】
Ｍ．　Ｂｅｌｌａｒｅ，　Ａ．　Ｄｅｓａｉ，　Ｄ．　Ｐｏｉｎｔｃｈｅｖａｌ　ａｎｄ　Ｐ．　Ｒｏｇａｗａｙ　：　Ｒｅｌａｔｉｏｎｓ　Ａｍｏｎｇ　Ｎｏｔｉｏｎｓ　ｏｆ　Ｓｅｃｕｒｉｔｙ　ｆｏｒ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｃｈｅｍｅｓ，　Ｐｒｏｃ．　ｏｆ　Ｃｒｙｐｔｏ’９８，　ＬＮＣＳ１４６２，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．２６−４５　（１９９８）
【非特許文献２】
Ｍ．　Ｂｅｌｌａｒｅ　ａｎｄ　Ｐ．　Ｒｏｇａｗａｙ　：　Ｒａｎｄｏｍ　Ｏｒａｃｌｅｓ　ａｒｅ　Ｐｒａｃｔｉｃａｌ　−−　Ａ　Ｐａｒａｄｉｇｍｆｏｒ　Ｄｅｓｉｇｎｉｎｇ　Ｅｆｆｉｃｉｅｎｔ　Ｐｒｏｔｏｃｏｌ，　Ｆｉｒｓｔ　ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ，　ｐｐ．６２−−７３　（１９９３）
【非特許文献３】
Ｍ．　Ｂｅｌｌａｒｅ　ａｎｄ　Ｐ．　Ｒｏｇａｗａｙ　：　Ｏｐｔｉｍａｌ　Ａｓｙｍｍｅｔｒｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　　Ｈｏｗ　ｔｏ　Ｅｎｃｒｙｐｔ　ｗｉｔｈ　ＲＳＡ，　Ｐｒｏｃ．　ｏｆ　Ｅｕｒｏｃｒｙｐｔ’９４，　ＬＮＣＳ９５０，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．９２−１１１
（１９９４）
【非特許文献４】
Ｖ．　Ｓｈｏｕｐ　：　ＯＡＥＰ　Ｒｅｃｏｎｓｉｄｅｒｅｄ．　Ａｖａｉｌａｂｌｅ　ｏｎ　ｔｈｅ　ｅ−ｐｒｉｎｔ　ｌｉｂｒａｒｙ　（２０００／０６０），　Ｎｏｖｅｍｂｅｒ　２０００
【非特許文献５】
Ｒ．　Ｃｒａｍｅｒ　ａｎｄ　Ｖ．　Ｓｈｏｕｐ　：　Ａ　Ｐｒａｃｔｉｃａｌ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｃｒｙｐｔｏｓｙｓｔｅｍ　Ｐｒｏｖａｂｌｙ　Ｓｅｃｕｒｅ　ａｇａｉｎｓｔ　Ａｄａｐｔｉｖｅ　Ｃｈｏｓｅｎ　Ｃｉｐｈｅｒｔｅｘｔ　Ａｔｔａｃｋ，　Ｐｒｏｃ．　ｏｆ　Ｃｒｙｐｔｏ９８，　ＬＮＣＳ１４６２，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．１３−２５　（１９９８）
【０００７】
【発明が解決しようとする課題】
さて、本発明では、ランダムオラクルモデル上でＩＮＤ−ＣＣＡ２であることが証明可能な公開鍵暗号通信技術を対象とする。ＩＮＤ−ＣＣＡ２の定義では、ランダムオラクルが公正に与えられる必要がある。しかし、現実世界において、ランダムオラクルを与えるランダム関数（例えばハッシュ関数）が公正であることを示すことは難しい。
【０００８】
例えば、公開鍵暗号への攻撃者は、落し戸付きのハッシュ関数を作成し、既存システムのユーザに利用させることにより、そのシステムを破ろうとするかもしれない。また、一般に、公開鍵暗号およびハッシュ関数が別々にデザインされるため、公開鍵暗号の安全性がハッシュ関数により左右されることが起こり得る。
【０００９】
以下、このことについて簡単に説明する。
【００１０】
上記の非特許文献２には、メッセージｘに対しその暗号文（ｕ，ｖ，ｗ）が、
【００１１】
【数３５】
2004126514.tif 000003
【００１２】
により与えられる公開鍵暗号方法が記載されている。なお、数３５において、ｆは公開された落し戸付き一方向性置換であり、Ｇ、Ｈはハッシュ関数である。この公開鍵暗号方法は、ハッシュ関数Ｇ、Ｈをランダムオラクルとするとき、ＩＮＤ−ＣＣＡ２であることが同非特許文献２の中で示されている。
【００１３】
さて、ハッシュ関数Ｇのデザイナである公開鍵暗号への攻撃者は、ハッシュ関数Ｇをハッシュ関数Ｇ’に対して、Ｇ＝Ｇ’・ｆとなるように作成していたとする（但し、（ｆ・ｇ）（ｍ）＝ｆ（ｇ（ｍ））とする）。ここで、Ｇ’をランダムオラクルとすると、Ｇもランダムオラクルになる点に注意する。
【００１４】
攻撃者は、Ｇ（ｒ）＝（Ｇ’・ｆ）（ｒ）＝Ｇ’（ｆ（ｒ））＝Ｇ’（ｕ）であるので、
【００１５】
【数３６】
2004126514.tif 000004
【００１６】
により、メッセージｍを計算することができる。
【００１７】
このように、従来のＩＮＤ−ＣＣＡ２の定義では、安全である公開鍵暗号であっても、ランダムオラクルを与えるランダム関数を攻撃者が選んだ場合に、不正にメッセージを入手できる場合がある。
【００１８】
本発明は、上記事情に鑑みてなされたものであり、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な公開鍵暗号を用いた暗号通信通信技術を提供することにある。
【００１９】
具体的には、攻撃者がランダムオラクルを与えるランダム関数を選んで適応的選択暗号文攻撃を行なった場合でも、メッセージに関する部分情報を計算できないようにすることにある。
【００２０】
【課題を解決するための手段】
上記課題を解決するために本発明の公開鍵暗号通信方法では、送信者側装置が、ランダム関数および受信者の公開鍵を用いてメッセージの暗号文を作成し、これを受信者側装置へ送信する。一方、前記受信者側装置が、前記ランダム関数および前記公開鍵と対の秘密鍵を用いて前記送信者側装置より受信した前記暗号文を復号化する。
【００２１】
そして、前記送信者側装置は、前記暗号文から前記ランダム関数への入力値に関する部分情報が秘匿されるように、つまり、前記暗号文を作成する際に用いたランダムオラクルとしての前記ランダム関数への入力値（メッセージに限定されない）に関する部分情報を、前記暗号文から計算することが困難となるように前記暗号文を作成する。数３５、数３６に示す公開鍵暗号の例でいえば、ハッシュ関数Ｇに対する入力値ｒの部分情報ｆ（ｒ）を、暗号文から計算することが困難となるように当該暗号文を作成する。
【００２２】
これにより、公開鍵暗号への攻撃者が、ランダム関数を自由に選ぶことができても、メッセージに関する部分情報を暗号文から計算することができない。数３５、数３６に示す公開鍵暗号の例でいえば、ハッシュ関数Ｇ’からＧ（ｒ）を得ることができない。したがって、攻撃者による公開鍵暗号への攻撃を無効とすることができる。
【００２３】
なお、本発明において、前記送信者側装置が、前記ランダム関数への入力値を知っていることを証明する証明データを、前記暗号文の一部として作成するようにしてもうよい。この場合、前記受信者側装置は、前記送信者側装置より受信した前記暗号文に含まれている前記証明データの正当性を確認し、前記正当性が確認された場合にのみ前記暗号文の復号化結果を出力する。
【００２４】
このようにすることで、前記ランダム関数への入力値を知っていることが証明された場合にのみ、前記暗号文の復号結果が出力されるため、前記ランダム関数への入力値を知らない公開鍵暗号への攻撃者は、復号化オラクルから復号結果に関する情報を得ることができない。したがって、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全な公開鍵暗号通信を実現できる。
【００２５】
具体的には、例えば、受信者の秘密鍵を、
【００２６】
【数３７】
2004126514.tif 000005
【００２７】
とし、
前記秘密鍵と対の公開鍵を、
【００２８】
【数３８】
2004126514.tif 000006
【００２９】
とする（但し、Ｇは有限アーベル群を表わし、Ｇの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｎは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい）。
【００３０】
この場合、前記送信者側装置は、
メッセージｍ∈｛０，１｝ｎに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【００３１】
【数３９】
2004126514.tif 000007
【００３２】
を計算して（但し、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する）、その結果（ｕ，ｖ，ｗ）を前記メッセージｍの暗号文とする。
【００３３】
一方、前記受信者側装置は、
前記秘密鍵を用いて、
【００３４】
【数４０】
2004126514.tif 000008
【００３５】
なる（ｒ１’，ｒ２’）を計算して（但し、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｒ１’，ｒ２’のビット長は既知とする）、
【００３６】
【数４１】
2004126514.tif 000009
【００３７】
が成立することを確認することで、前記証明データの正当性を確認し、
前記確認に成功した場合にのみ、ｍ’を、
【００３８】
【数４２】
2004126514.tif 000010
【００３９】
により計算し（但し、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する）、前記暗号文（ｕ，ｖ，ｗ）のメッセージとして出力する。
【００４０】
また、本発明において、前記送信者側装置が、前記暗号文の作成に先立って、前記ランダム関数への入力値を十分に大きな集合の中から一様に選ぶようにしてもよい。
【００４１】
このようにすることで、公開鍵暗号への攻撃者は、前記ランダム関数への入力値を知ることがより困難になるため、復号化オラクルから復号結果に関する情報を得ることができない。したがって、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全な公開鍵暗号通信を実現できる。
【００４２】
具体的には、例えば、受信者の秘密鍵を、
【００４３】
【数４３】
2004126514.tif 000011
【００４４】
とし、
前記秘密鍵と対の公開鍵を、
【００４５】
【数４４】
2004126514.tif 000012
【００４６】
とする（但し、Ｇは有限アーベル群を表わし、｛０，１｝ｋの元をＧの元とみなす１対１対応があるものとする）。
【００４７】
この場合、前記送信者側装置は、
メッセージｍ∈｛０，１｝ｋ０に対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選び、
【００４８】
【数４５】
2004126514.tif 000013
【００４９】
を計算して、その結果（ｕ，ｖ）を前記メッセージｍの暗号文とする。
【００５０】
一方、前記受信者側装置は、
前記秘密鍵を用いて、
【００５１】
【数４６】
2004126514.tif 000014
【００５２】
なる（ｍ’，ｒ１’，ｒ２’）を計算して（但し、ｍ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｍ’，ｒ１’，ｒ２’のビット長は既知とする）、
【００５３】
【数４７】
2004126514.tif 000015
【００５４】
が成立することを確認し、
前記確認に成功した場合にのみ、ｍ’を前記暗号文（ｕ，ｖ）のメッセージとする。
【００５５】
なお、本発明において、暗号化対象となるメッセージは、文字列のみならず、画像や音、あるいは、送信データの暗号化のために使用する共通鍵など、あらゆるディジタルデータが該当する。
【００５６】
【発明の実施の形態】
以下に、本発明の実施の形態について説明する。
【００５７】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００５８】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。図示するように、公開鍵暗号通信システムは、暗号化処理を行なってメッセージの暗号文を作成する送信者側装置１００と、復号化処理を行なってメッセージを復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００５９】
図２は、図１に示す送信者側装置１００の概略構成図である。図示するように、暗号化対象のメッセージを含む各種情報の入力を受け付ける入力部１０７と、乱数生成部１０１と、べき乗算部１０２と、暗号化部１０３と、剰余演算部１０４と、記憶部１０５と、通信回線３００を介して受信者側装置２００と通信を行なう通信部１０６と、を備えている。
【００６０】
図３は、図１に示す受信者側装置２００の概略構成図である。図示するように、通信回線３００を介して送信者側装置１００と通信を行なう通信部２０６と、鍵生成部２０１と、べき乗算部２０２と、復号化部２０３と、剰余演算部２０４と、記憶部２０５と、復号結果を含む各種情報を出力する出力部２０７と、を備えている。
【００６１】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体４０４から情報を読み出す読取装置４０５と、キーボードやマウスなどの入力装置４０６と、ディスプレイなどの出力装置４０７と、通信回線３００を介して相手装置と通信を行なうための通信装置４０８と、を備えた一般的なコンピュータシステムにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１０５、２０５に利用される。
【００６２】
この所定のプログラムは、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００６３】
（第１実施形態）
次に、本発明の第１実施形態について、送信者Ａが受信者Ｂに対して、送信データとなるメッセージｍを暗号通信によって送信する場合を例にとり説明する。
図５は、本発明の第１実施形態の動作手順を説明するための図である。
【００６４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３）とを、それぞれ数４８、数４９により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１１００）。
【００６５】
【数４８】
2004126514.tif 000016
【００６６】
【数４９】
2004126514.tif 000017
【００６７】
ここで、Ｇは有限アーベル群を表わし、Ｇの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｋ３は、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【００６８】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ１１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３は、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【００６９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｋ１）の入力を受け付ける（ＳＴ１２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３）とを用いて、べき乗算部１０２を利用して数５０を計算する（ＳＴ１２０１）。
【００７０】
【数５０】
2004126514.tif 000018
【００７１】
次に、暗号化部１０３は、数５０の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１２０２）。
【００７２】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数５１を満たす（ｍ’，ｒ’）計算する（ＳＴ１３００）。
【００７３】
【数５１】
2004126514.tif 000019
【００７４】
ここで、ｍ’，ｒ’のビット長は既知とする。
【００７５】
次に、復号化部２０３は、数５１の計算結果（ｍ’，ｒ’）を用いて、べき乗算部２０２を利用して、数５２が成立するか否かを確認する（ＳＴ１３０１）。
【００７６】
【数５２】
2004126514.tif 000020
【００７７】
そして、復号化部２０３は、数５２が成立することを確認できた場合のみ、復号結果ｍ’を出力部２０７から出力する。一方、数５２が成立することを確認できなかった場合は、復号結果ｍ’の出力を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ１３０２）。
【００７８】
以上、本発明の第１実施形態について説明した。
【００７９】
本実施形態では、群Ｇ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題（定義については例えば非特許文献５を参照）の困難性を前提にして、ＩＮＤ−ＣＣＡ２であることが証明できる。
【００８０】
すなわち、ＩＮＤ−ＣＣＡ２の意味において、本実施形態による公開鍵暗号を破ろうとする攻撃者（ＩＮＤ−ＣＣＡ２の定義については、例えば、上記の文献４に記載されている）が、復号化オラクルから情報を得るためには、質問である暗号文に対する元のメッセージを知る必要がある。しかし、攻撃者は、復号化オラクルから新たな情報を得ることができない。また、上記の文献３に記載されている方法と同様の方法により、本実施形態が選択平文攻撃に対して強秘匿（ＩＮＤ−ＣＰＡ（Ｃｈｏｓｅｎ−Ｐｌａｉｎｔｅｘｔ　Ａｔｔａｃｋ））であることが証明できる。これより、本実施形態の公開鍵暗号通信は、ＩＮＤ−ＣＣＡ２であることが証明できる。
【００８１】
また、本実施形態において、乱数ｒをメッセージとみなすと（この場合、メッセージｍは秘密である）、上記の文献３に記載されている方法と同様の方法により、群Ｇ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提にして、ＩＮＤ−ＣＰＡであることが証明できる。すなわち、暗号文から乱数ｒに関する部分情報を漏らしていないことを証明できる。つまり、本実施形態では、攻撃者がランダム関数に付随する情報を第３のランダム関数から得ても、メッセージに関する部分情報を暗号文から計算することが困難である。
【００８２】
さらに、暗号文の一部であるデータｗを正しく作成するためには、データｍおよびデータｒを知る必要がある。云いかえれば、ランダム関数への入力値を知る者しかデータｍを作成することができない。本実施形態では、データｗを正しく作成できない攻撃者は、復号化オラクルから新しい情報を得ることが困難である。
【００８３】
以上のことから、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも安全な公開鍵暗号通信を実現できる。
【００８４】
（第２実施形態）
次に、本発明の第２実施形態について、送信者Ａが受信者Ｂに対して、送信データとなるメッセージｍを暗号通信によって送信する場合を例にとり説明する。図６は、本発明の第２実施形態の動作手順を説明するための図である。
【００８５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，（Ｅ，Ｄ））とを、それぞれ数５３、数５４により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１４００）。
【００８６】
【数５３】
2004126514.tif 000021
【００８７】
【数５４】
2004126514.tif 000022
【００８８】
ここで、Ｇは有限アーベル群を表わし、Ｇの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｎは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【００８９】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ１４０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３および共通鍵暗号アルゴリズム（Ｅ，Ｄ）は、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３および共通鍵暗号アルゴリズム（Ｅ，Ｄ）を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【００９０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｎ）の入力を受け付ける（ＳＴ１５００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，（Ｅ，Ｄ））とを用いて、べき乗算部１０２を利用して数５５を計算する（ＳＴ１５０１）。
【００９１】
【数５５】
2004126514.tif 000023
【００９２】
ここで、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する。
【００９３】
次に、暗号化部１０３は、数５５の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１５０２）。
【００９４】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数５６を満たす（ｒ１’、ｒ２’）計算する（ＳＴ１６００）。
【００９５】
【数５６】
2004126514.tif 000024
【００９６】
ここで、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｒ１’，ｒ２’のビット長は既知とする。
【００９７】
次に、復号化部２０３は、数５６の計算結果（ｒ１’、ｒ２’）を用いて、べき乗算部２０２を利用し数５７が成立するか否かを確認する（ＳＴ１６０１）。
【００９８】
【数５７】
2004126514.tif 000025
【００９９】
そして、復号化部２０３は、数５７が成立することを確認できた場合のみｍ’を、
【０１００】
【数５８】
2004126514.tif 000026
【０１０１】
により計算し、これを暗号文の復号結果として出力する。ここで、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する。一方、数５７が成立することを確認できなかった場合は、ｍ’の計算を拒否し、その代わりに例えばエラーメッセージなどを出力部２０７から出力する（ＳＴ１６０２）。
【０１０２】
以上、本発明の第２実施形態について説明した。
【０１０３】
本実施形態でも、上記の第１実施形態と同様の効果を奏する。
【０１０４】
（第３実施形態）
次に、本発明の第３実施形態について説明する。図７は、本発明の第３実施形態の動作手順を説明するための図である。
【０１０５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｐ，ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３）とを、それぞれ数５９、数６０により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ２１００）。
【０１０６】
【数５９】
2004126514.tif 000027
【０１０７】
【数６０】
2004126514.tif 000028
【０１０８】
ここで、Ｚ＊ｐの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｋ３は、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【０１０９】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｐ，ｇ，ｈ）を含む公開情報を、送信者Ａに知らせる（ＳＴ２１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３は、上記の第１実施形態と同様、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０１１０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｋ１）の入力を受け付ける（ＳＴ２２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｐ，ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３）とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数６１を計算する（ＳＴ２２０１）。
【０１１１】
【数６１】
2004126514.tif 000029
【０１１２】
次に、暗号化部１０３は、数６１の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ２２０２）。
【０１１３】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数６２を満たす（ｍ’，ｒ’）計算する（ＳＴ２３００）。
【０１１４】
【数６２】
2004126514.tif 000030
【０１１５】
ここで、ｍ’、ｒ’のビット長は既知とする。
【０１１６】
次に、復号化部２０３は、数６２の計算結果（ｍ’，ｒ’）を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数６３が成立するか否かを確認する（ＳＴ２３０１）。
【０１１７】
【数６３】
2004126514.tif 000031
【０１１８】
そして、復号化部２０３は、数６３が成立することを確認できた場合のみ、復号結果ｍ’を出力部２０７から出力する。一方、数６３が成立することを確認できなかった場合は、復号結果ｍ’の出力を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ２３０２）。
【０１１９】
以上、本発明の第３実施形態について説明した。
【０１２０】
本実施形態においても、上記の第１実施形態と同様の方法により、群Ｚ＊ｐ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提にして、ＩＮＤ−ＣＣＡ２であることを証明できる。
【０１２１】
また、上記の第１実施形態と同様、乱数ｒをメッセージとみなすと（この場合、メッセージｍは秘密である）、群Ｚ＊ｐ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提にして、ＩＮＤ−ＣＰＡであることが証明できる。すなわち、暗号文から乱数ｒに関する部分情報を漏らしていないことを証明できる。つまり、攻撃者がランダム関数に付随する情報を第３のランダム関数から得ても、メッセージに関する部分情報を暗号文から計算することが困難である。
【０１２２】
さらに、上記の第１実施形態と同様、暗号文の一部であるデータｗを正しく作成するためには、データｍおよびデータｒを知る必要がある。云いかえれば、ランダム関数への入力値を知る者しかデータｍを作成することができない。本実施形態では、データｗを正しく作成できない攻撃者は、復号化オラクルから新しい情報を得ることが困難である。
【０１２３】
以上のことから、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも安全な公開鍵暗号通信を実現できる。
【０１２４】
（第４実施形態）
次に、本発明の第４実施形態について説明する。図８は、本発明の第４実施形態の動作手順を説明するための図である。
【０１２５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｐ，ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，（Ｅ，Ｄ））とを、それぞれ数６４、数６５により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ２４００）。
【０１２６】
【数６４】
2004126514.tif 000032
【０１２７】
【数６５】
2004126514.tif 000033
【０１２８】
ここで、Ｚ＊ｐの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｎは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【０１２９】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｐ，ｇ，ｈ）を含む公開情報を、送信者Ａに知らせる（ＳＴ２４０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３および共通鍵暗号アルゴリズム（Ｅ，Ｄ）は、上記の第１実施形態と同様、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３および共通鍵暗号アルゴリズム（Ｅ，Ｄ）を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０１３０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｎ）の入力を受け付ける（ＳＴ２５００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，（Ｅ，Ｄ））とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数６６を計算する（ＳＴ２５０１）。
【０１３１】
【数６６】
2004126514.tif 000034
【０１３２】
ここで、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する。
【０１３３】
次に、暗号化部１０３は、数６６の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ２５０２）。
【０１３４】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２および剰余演算部１０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数６７を満たす（ｒ１’、ｒ２’）を計算する（ＳＴ２６００）。
【０１３５】
【数６７】
2004126514.tif 000035
【０１３６】
ここで、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｒ１’，ｒ２’のビット長は既知とする。
【０１３７】
次に、復号化部２０３は、数６７の計算結果（ｒ１’、ｒ２’）を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数６８が成立するか否かを確認する（ＳＴ２６０１）。
【０１３８】
【数６８】
2004126514.tif 000036
【０１３９】
そして、復号化部２０３は、数６８が成立することを確認できた場合のみｍ’を、
【０１４０】
【数６９】
2004126514.tif 000037
【０１４１】
により計算し、これを暗号文の復号結果として出力する。ここで、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する。一方、数６８が成立することを確認できなかった場合は、ｍ’の計算を拒否し、その代わりに例えばエラーメッセージなどを出力部２０７から出力する（ＳＴ２６０２）。
【０１４２】
以上、本発明の第４実施形態について説明した。
【０１４３】
本実施形態でも、上記の第１実施形態と同様の効果を奏する。
【０１４４】
（第５実施形態）
次に、本発明の第５実施形態について説明する。本実施形態は、上記の第１実施形態の変形例であり、上記の第１実施形態よりも平文空間（メッセージの長さ）を大きくできるようにしたものである。図９は、本発明の第５実施形態の動作手順を説明するための図である。
【０１４５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，Ｇ）とを、それぞれ数７０、数７１により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ３１００）。
【０１４６】
【数７０】
2004126514.tif 000038
【０１４７】
【数７１】
2004126514.tif 000039
【０１４８】
ここで、Ｇは有限アーベル群を表わし、Ｇの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｋ３，ｎのそれぞれは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【０１４９】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｇ，ｈ）を含む公開情報を、送信者Ａに知らせる（ＳＴ３１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３、Ｇは、上記の第１実施形態と同様、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３、Ｇを、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０１５０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｎ）の入力を受け付ける（ＳＴ３２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３、Ｇ）とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数７２を計算する（ＳＴ３２０１）。
【０１５１】
【数７２】
2004126514.tif 000040
【０１５２】
次に、暗号化部１０３は、数４４の計算結果（ｕ，ｖ，ｗ，ｚ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ３２０２）。
【０１５３】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ，ｚ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ，ｚ）から数７３を満たす（ｒ１’，ｒ２’）を計算する（ＳＴ３３００）。
【０１５４】
【数７３】
2004126514.tif 000041
【０１５５】
ここで、ｒ１’、ｒ２’のビット長は既知とする。
【０１５６】
次に、復号化部２０３は、数７３の計算結果（ｒ１’，ｒ２’）を用い、べき乗算部２０２を利用して、数７４が成立するか否かを確認する（ＳＴ３３０１）。
【０１５７】
【数７４】
2004126514.tif 000042
【０１５８】
そして、復号化部２０３は、数７４が成立することを確認できなかった場合、復号結果の出力を拒否して、例えばエラーメッセージなどを出力部２０７から出力する。一方、数７４が成立することを確認できた場合は、記憶部２０５に記憶されている受信者の秘密鍵ｘと、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ，ｚ）と、数７３の計算結果（ｒ１’，ｒ２’）とを用いて、数７５を計算する。
【０１５９】
【数７５】
2004126514.tif 000043
【０１６０】
そして、数７５の計算結果ｍ’を、暗号文（ｕ，ｖ，ｗ，ｚ）のメッセージとして出力する（ＳＴ３３０２）。
【０１６１】
以上、本発明の第５実施形態について説明した。
【０１６２】
本実施形態は、上記の第１実施形態と同様の効果を奏する。それに加え、本実施形態では、メッセージの長さ（ビット長）ｎを任意に選ぶことができる。このため、上記の第１実施形態に比べてより長いメッセージを暗号化することが可能である。公開鍵暗号の利用目的として、共通鍵暗号のデータ暗号化鍵の配送に利用することがある。しかし、単にデータ暗号化鍵のみを暗号化するのではなく、ユーザのＩＤ情報等の付加情報を加えて暗号化することも少なくない。このような場合において、本実施形態は有効である。
【０１６３】
（第６実施形態）
次に、本発明の第６実施形態について説明する。本実施形態は、上記の第５実施形態において有限アーベル群Ｇを体から決定される乗法群として与えている。
図１０は、本発明の第６実施形態の動作手順を説明するための図である。
【０１６４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、受信者Ｂの秘密鍵ｘと、受信者Ｂの公開鍵（ｐ，ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３，Ｇ）とを、それぞれ数７６、数７７により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ４１００）。
【０１６５】
【数７６】
2004126514.tif 000044
【０１６６】
【数７７】
2004126514.tif 000045
【０１６７】
ここで、Ｚ＊ｐの元と｛０，１｝ｋの元との間に１対１対応があるものとする。また、ｋ３，ｎのそれぞれは、ｋ１＋ｋ２以上でもよいし、あるいは未満でもよい。
【０１６８】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｐ，ｇ，ｈ）を含む公開情報を、送信者Ａに知らせる（ＳＴ４１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１〜Ｈ３、Ｇは、上記の第１実施形態と同様、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１〜Ｈ３、Ｇを、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０１６９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｎ）の入力を受け付ける（ＳＴ４２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｐ，ｇ，ｈ，Ｈ１，Ｈ２，Ｈ３、Ｇ）とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数７８を計算する（ＳＴ４２０１）。
【０１７０】
【数７８】
2004126514.tif 000046
【０１７１】
次に、暗号化部１０３は、数７８の計算結果（ｕ，ｖ，ｗ，ｚ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ４２０２）。
【０１７２】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ，ｚ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者Ｂの秘密鍵ｘを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ，ｚ）から数７９を満たす（ｒ１’，ｒ２’）を計算する（ＳＴ４３００）。
【０１７３】
【数７９】
2004126514.tif 000047
【０１７４】
ここで、ｒ１’、ｒ２’のビット長は既知とする。
【０１７５】
次に、復号化部２０３は、数７９の計算結果（ｒ１’，ｒ２’）を用い、べき乗算部２０２および剰余演算部２０４を利用して、数８０が成立するか否かを確認する（ＳＴ４３０１）。
【０１７６】
【数８０】
2004126514.tif 000048
【０１７７】
そして、復号化部２０３は、数８０が成立することを確認できなかった場合、復号結果の出力を拒否して、例えばエラーメッセージなどを出力部２０７から出力する。一方、数８０が成立することを確認できた場合は、記憶部２０５に記憶されている受信者の秘密鍵ｘと、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ，ｚ）と、数７９の計算結果（ｒ１’，ｒ２’）とを用いて、数８１を計算する。
【０１７８】
【数８１】
2004126514.tif 000049
【０１７９】
そして、数８１の計算結果ｍ’を、暗号文（ｕ，ｖ，ｗ，ｚ）のメッセージとして出力する（ＳＴ４３０２）。
【０１８０】
以上、本発明の第６実施形態について説明した。
【０１８１】
本実施形態は、上記の第３実施形態と同様の効果を奏する。それに加え、本実施形態では、メッセージの長さ（ビット長）ｎを任意に選ぶことができる。このため、上記の第３実施形態に比べてより長いメッセージを暗号化することが可能である。公開鍵暗号の利用目的として、共通鍵暗号のデータ暗号化鍵の配送に利用することがある。しかし、単にデータ暗号化鍵のみを暗号化するのではなく、ユーザのＩＤ情報等の付加情報を加えて暗号化することも少なくない。このような場合において、本実施形態は有効である。
【０１８２】
（第７実施形態）
次に、本発明の第７実施形態について、送信者Ａが受信者Ｂに対して、送信データとなるメッセージｍを暗号通信によって送信する場合を例にとり説明する。
図１１は、本発明の第７実施形態の動作手順を説明するための図である。
【０１８３】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｓと、受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２）とを、それぞれ数８２、数８３により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ５１００）。
【０１８４】
【数８２】
2004126514.tif 000050
【０１８５】
【数８３】
2004126514.tif 000051
【０１８６】
ここで、Ｇは有限アーベル群を表わし、｛０，１｝ｋの元をＧの元とみなす１対１対応があるものとする。
【０１８７】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ５１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１、Ｈ２は、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１、Ｈ２を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０１８８】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｋ０）の入力を受け付ける（ＳＴ５２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して、乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。ここで、乱数ｒ１、ｒ２は、十分に大きな集合の中から一様に、つまり、どの値が選択されたか予測できないように、選択されるものとする。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２）とを用いて、べき乗算部１０２を利用して数８４を計算する（ＳＴ５２０１）。
【０１８９】
【数８４】
2004126514.tif 000052
【０１９０】
次に、暗号化部１０３は、数８４の計算結果（ｕ，ｖ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ５２０２）。
【０１９１】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｓを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ）から数８５を満たす（ｍ’，ｒ１’，ｒ２’）計算する（ＳＴ５３００）。
【０１９２】
【数８５】
2004126514.tif 000053
【０１９３】
ここで、ｍ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｍ’，ｒ１’，ｒ２’のビット長は既知とする。
【０１９４】
次に、復号化部２０３は、数８５の計算結果（ｍ’，ｒ１’，ｒ２’）を用いて、べき乗算部２０２を利用して、数８６が成立するか否かを確認する（ＳＴ５３０１）。
【０１９５】
【数８６】
2004126514.tif 000054
【０１９６】
そして、復号化部２０３は、数８６が成立することを確認できた場合のみ、復号結果ｍ’を出力部２０７から出力する。一方、数８６が成立することを確認できなかった場合は、復号結果ｍ’の出力を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ５３０２）。
【０１９７】
以上、本発明の第７実施形態について説明した。
【０１９８】
本実施形態では、群Ｇ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提にして、攻撃者がランダムオラクル（関数）を不正に選んだ場合（以下、通常のランダムオラクルに対して攻撃的ランダムオラクルと呼ぶ）においても、安全性を証明できる。すなわち、本実施形態では、受動的攻撃に対して（攻撃者は復号化オラクルを利用しない）、メッセージのみならず、ランダムオラクルへの入力値さえ暗号文から計算することが（従来の強秘匿（ｓｅｍａｎｔｉｃ　ｓｅｃｕｒｉｔｙ）や識別不能（ＩＮＤ：Ｉｎｄｉｓｔｉｎｇｕｉｓｈａｂｉｌｉｔｙ）の概念における数学的手法と類似の手法により）困難であることが証明できる。これにより、攻撃的ランダムオラクルは、通常のランダムオラクルに対して無視できる確率でしかアドバンテージを持っていないことが証明される。
【０１９９】
以上のことから、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも安全な公開鍵暗号通信を実現できる。
【０２００】
（第８実施形態）
次に、本発明の第８実施形態について説明する。本実施形態は、上記の第７実施形態を共通鍵暗号とのハイブリッド方式にしたものである。図１２は、本発明の第８実施形態の動作手順を説明するための図である。
【０２０１】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｓと、受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，（Ｅ，Ｄ），Ｆ）とを、それぞれ数８７、数８８により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ６１００）。
【０２０２】
【数８７】
2004126514.tif 000055
【０２０３】
【数８８】
2004126514.tif 000056
【０２０４】
ここで、Ｇは有限アーベル群を表わし、｛０，１｝ｋの元をＧの元とみなす１対１対応があるものとする。
【０２０５】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ６１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１、Ｈ２、共通鍵暗号アルゴリズム（Ｅ，Ｄ）、および、鍵生成関数Ｆは、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１、Ｈ２、共通鍵暗号アルゴリズム（Ｅ，Ｄ）、および、鍵生成関数Ｆを、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０２０６】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍの入力を受け付ける（ＳＴ６２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して、乱数ｚ∈｛０，１｝ｋ０、ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。ここで、乱数ｚ、ｒ１、ｒ２は、十分に大きな集合の中から一様に、つまり、どの値が選択されたか予測できないように、選択されるものとする。それから、暗号化部１０３は、この乱数ｚと、予め記憶部１０５に記憶しておいた鍵生成関数Ｆとを用いて、鍵Ｋ＝Ｆ（ｚ）を計算する。次に、暗号化部１０３は、この鍵Ｋと、乱数ｚ、ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，（Ｅ，Ｄ））とを用いて、べき乗算部１０２を利用して数８９を計算する（ＳＴ６２０１）。
【０２０７】
【数８９】
2004126514.tif 000057
【０２０８】
ここで、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する。
【０２０９】
次に、暗号化部１０３は、数８９の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ６２０２）。
【０２１０】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｓを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数９０を満たす（ｚ’，ｒ１’，ｒ２’）計算する（ＳＴ６３００）。
【０２１１】
【数９０】
2004126514.tif 000058
【０２１２】
ここで、ｚ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｚ’，ｒ１’，ｒ２’のビット長は既知とする。
【０２１３】
次に、復号化部２０３は、数９０の計算結果（ｚ’，ｒ１’，ｒ２’）を用いて、べき乗算部２０２を利用して、数９１が成立するか否かを確認する（ＳＴ６３０１）。
【０２１４】
【数９１】
2004126514.tif 000059
【０２１５】
そして、復号化部２０３は、数９１が成立することを確認できた場合のみ、予め記憶部２０５に記憶されている鍵生成関数Ｆを用いて、鍵Ｋ’＝Ｆ（ｚ’）を計算する。それから、この鍵Ｋ’と、予め記憶部２０５に記憶されている共通鍵暗号アルゴリズム（Ｅ，Ｄ）とを用いて、数９２を計算する。次に、復号化部２０３は、数９２の計算結果ｍ’を前記暗号文（ｕ，ｖ，ｗ）のメッセージとして出力する。
【０２１６】
【数９２】
2004126514.tif 000060
【０２１７】
ここで、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する。
【０２１８】
一方、数９１が成立することを確認できなかった場合は、数９２の計算を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ６３０２）。
【０２１９】
以上、本発明の第８実施形態について説明した。
【０２２０】
本実施形態では、上記の第７実施形態を共通鍵暗号とのハイブリッド方式にしたものであるため、上記の第７実施形態の効果に加えて、任意長のメッセージを暗号通信できるという利点を有する。
【０２２１】
（第９実施形態）
次に、本発明の第９実施形態についてについて説明する。本実施形態は、上記の第７実施形態において、有限アーベル群Ｇを体Ｚｐから決定される乗法群として与えたものである。図１３は、本発明の第９実施形態の動作手順を説明するための図である。
【０２２２】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｓと、受信者Ｂの公開鍵（ｐ，ｑ，ｇ，ｈ，Ｈ１，Ｈ２）とを、それぞれ数９３、数９４により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ７１００）。
【０２２３】
【数９３】
2004126514.tif 000061
【０２２４】
【数９４】
2004126514.tif 000062
【０２２５】
ここで、｜ｐ｜＝ｋ＋１とする。
【０２２６】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｐ，ｑ，ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ７１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１、Ｈ２は、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１、Ｈ２を、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０２２７】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍ（ｍ∈｛０，１｝ｋ０）の入力を受け付ける（ＳＴ７２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して、乱数ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を選ぶ。ここで、乱数ｒ１、ｒ２は、十分に大きな集合の中から一様に、つまり、どの値が選択されたか予測できないように、選択されるものとする。それから、暗号化部１０３は、この乱数ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｐ，ｑ，ｇ，ｈ，Ｈ１，Ｈ２）とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数９５を計算する（ＳＴ７２０１）。
【０２２８】
【数９５】
2004126514.tif 000063
【０２２９】
次に、暗号化部１０３は、数９５の計算結果（ｕ，ｖ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ７２０２）。
【０２３０】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｓを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ）から数９６を満たす（ｍ’，ｒ１’，ｒ２’）計算する（ＳＴ７３００）。
【０２３１】
【数９６】
2004126514.tif 000064
【０２３２】
ここで、ｍ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｍ’，ｒ１’，ｒ２’のビット長は既知とする。
【０２３３】
次に、復号化部２０３は、数９６の計算結果（ｍ’，ｒ１’，ｒ２’）を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数９７が成立するか否かを確認する（ＳＴ７３０１）。
【０２３４】
【数９７】
2004126514.tif 000065
【０２３５】
そして、復号化部２０３は、数９７が成立することを確認できた場合のみ、復号結果ｍ’を出力部２０７から出力する。一方、数９７が成立することを確認できなかった場合は、復号結果ｍ’の出力を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ７３０２）。
【０２３６】
以上、本発明の第９実施形態について説明した。
【０２３７】
本実施形態では、上記の第７実施形態の場合と同様の方法により、群Ｚ＊ｐ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提にして、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも安全な公開鍵暗号通信を実現できる。
【０２３８】
（第１０実施形態）
次に、本発明の第１０実施形態について説明する。本実施形態は、上記の第９実施形態を共通鍵暗号とのハイブリッド方式にしたものである。図１４は、本発明の第１０実施形態の動作手順を説明するための図である。
【０２３９】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、受信者Ｂ（受信者側装置２００の操作者）よりの指示に従い、受信者Ｂの秘密鍵ｓと、受信者Ｂの公開鍵（ｐ，ｑ，ｇ，ｈ，Ｈ１，Ｈ２，（Ｅ，Ｄ），Ｆ）とを、それぞれ数９８、数９９により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ８１００）。
【０２４０】
【数９８】
2004126514.tif 000066
【０２４１】
【数９９】
2004126514.tif 000067
【０２４２】
ここで、Ｇはｑ個の元からなる乗法群Ｚｐ＊の部分群を意味し、｜ｐ｜＝ｋに対してｋ＝ｋ０＋ｋ１＋ｋ２とする。
【０２４３】
次に、受信者Ｂは、受信者側装置２００の鍵生成部２０１が生成した情報（ｐ，ｑ，ｇ，ｈ）を含む公開情報を、送信者Ａ（送信者側装置１００の操作者）に知らせる（ＳＴ８１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者Ｂよりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者Ｂは、例えば第３者（公開情報管理機関）への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。なお、公開鍵に含まれるランダム関数Ｈ１、Ｈ２、共通鍵暗号アルゴリズム（Ｅ，Ｄ）、および、鍵生成関数Ｆは、所定のものが送信者側装置１００および受信者側装置２００に予め設定されているようにしてもよい。あるいは、ランダム関数Ｈ１、Ｈ２、共通鍵暗号アルゴリズム（Ｅ，Ｄ）、および、鍵生成関数Ｆを、公開鍵の一部としてではなく、パブリックドメイン（ｐｕｂｌｉｃ　ｄｏｍａｉｎ）に置くようしてもかまわない。
【０２４４】
２．暗号化処理
送信者側装置１００において、入力部１０７は、送信者Ａよりメッセージｍの入力を受け付ける（ＳＴ８２００）。これを受けて、乱数生成部１０１は、メッセージｍに対して、乱数ｚ∈｛０，１｝ｋ０、ｒ１∈｛０，１｝ｋ１、ｒ２∈｛０，１｝ｋ２を、ｚ‖ｒ１‖ｒ２が群Ｇの元となるように選ぶ。なお、ｘ∈Ｚ＊ｐが群Ｇの元であるか否かの判断は、例えば数１００が成立するか否かを調べればよい。
【０２４５】
【数１００】
2004126514.tif 000068
【０２４６】
ここで、乱数ｚ、ｒ１、ｒ２は、十分に大きな集合の中から一様に、つまり、どの値が選択されたか予測できないように、選択されるものとする。それから、暗号化部１０３は、この乱数ｚと、予め記憶部１０５に記憶しておいた鍵生成関数Ｆとを用いて、鍵Ｋ＝Ｆ（ｚ）を計算する。次に、暗号化部１０３は、この鍵Ｋと、乱数ｚ、ｒ１、ｒ２と、予め記憶部１０５に記憶しておいた受信者Ｂの公開鍵（ｇ，ｈ，Ｈ１，Ｈ２，（Ｅ，Ｄ））とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数１０１を計算する（ＳＴ８２０１）。
【０２４７】
【数１０１】
2004126514.tif 000069
【０２４８】
ここで、ＥＫ（ｍ）は、メッセージ文ｍを鍵Ｋにより共通鍵暗号化アルゴリズムＥを用いて暗号化した結果を意味する。
【０２４９】
次に、暗号化部１０３は、数１０１の計算結果（ｕ，ｖ，ｗ）を、メッセージｍの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ８２０２）。
【０２５０】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文（ｕ，ｖ，ｗ）を受け取り、これを記憶部２０５に記憶する。さて、復号化部２０３は、受信者Ｂよりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵ｓを用いて、記憶部２０５に記憶されている暗号文（ｕ，ｖ，ｗ）から数１０２を満たす（ｚ’，ｒ１’，ｒ２’）計算する（ＳＴ８３００）。
【０２５１】
【数１０２】
2004126514.tif 000070
【０２５２】
ここで、ｚ’∈｛０，１｝ｋ０、ｒ１’∈｛０，１｝ｋ１、ｒ２’∈｛０，１｝ｋ２であり、ｚ’，ｒ１’，ｒ２’のビット長は既知とする。
【０２５３】
次に、復号化部２０３は、数１０２の計算結果（ｚ’，ｒ１’，ｒ２’）を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数１０３が成立するか否かを確認する（ＳＴ８３０１）。
【０２５４】
【数１０３】
2004126514.tif 000071
【０２５５】
そして、復号化部２０３は、数１０３が成立することを確認できた場合のみ、予め記憶部２０５に記憶されている鍵生成関数Ｆを用いて、鍵Ｋ’＝Ｆ（ｚ’）を計算する。それから、この鍵Ｋ’と、予め記憶部２０５に記憶されている共通鍵暗号アルゴリズム（Ｅ，Ｄ）とを用いて、数１０４を計算する。次に、復号化部２０３は、数１０４の計算結果ｍ’を前記暗号文（ｕ，ｖ，ｗ）のメッセージとして出力する。
【０２５６】
【数１０４】
2004126514.tif 000072
【０２５７】
ここで、ＤＫ’（ｗ）は、暗号文ｗを鍵Ｋ’により共通鍵暗号化アルゴリズムＤを用いて復号化した結果を意味する。
【０２５８】
一方、数１０３が成立することを確認できなかった場合は、数１０４の計算を拒否し、例えば代わりにエラーメッセージなどを出力部２０７から出力する（ＳＴ８３０２）。
【０２５９】
以上、本発明の第１０実施形態について説明した。
【０２６０】
本実施形態では、上記の第９実施形態を共通鍵暗号とのハイブリッド方式にしたものであるため、上記の第９実施形態の効果に加えて、任意長のメッセージを暗号通信できるという利点を有する。
【０２６１】
以上、本発明の各実施の形態について説明した。
【０２６２】
なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【０２６３】
例えば、上記の各実施形態では、送信者と受信者とが各々の装置を利用して暗号通信を行うという一般的な通信システムを例にとり説明したが、本発明は、様々なシステムに適用可能である。
【０２６４】
例えば、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店であり、受信者側装置はパソコンなどの計算機となる。この場合、ユーザの商品等の注文書は、共通鍵暗号で暗号化されることが多く、その際の暗号化鍵が本発明の公開鍵暗号通信方法により暗号化されて、受信者（小売店）側装置に送信される。
【０２６５】
また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信文（メール）は共通鍵暗号で暗号化されることが多い。この場合、共通鍵が本発明の公開鍵暗号通信方法により暗号化されて、受信者の計算機に送信される。
【０２６６】
その他にも、従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【０２６７】
また、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムだけではない。いずれかの計算を行なう装置は、ハードウエア化された演算装置であって、他の演算装置やＣＰＵとデータのやりとりを行うものでもよい。
【０２６８】
【発明の効果】
以上説明したように、本発明によれば、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な公開鍵暗号を用いた暗号通信通信技術を提供できる。
【図面の簡単な説明】
【図１】本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第１実施形態の動作手順を説明するための図である。
【図６】本発明の第２実施形態の動作手順を説明するための図である。
【図７】本発明の第３実施形態の動作手順を説明するための図である。
【図８】本発明の第４実施形態の動作手順を説明するための図である。
【図９】本発明の第５実施形態の動作手順を説明するための図である。
【図１０】本発明の第６実施形態の動作手順を説明するための図である。
【図１１】本発明の第７実施形態の動作手順を説明するための図である。
【図１２】本発明の第８実施形態の動作手順を説明するための図である。
【図１３】本発明の第９実施形態の動作手順を説明するための図である。
【図１４】本発明の第１０実施形態の動作手順を説明するための図である。
【符号の説明】
１００…送信者側装置、１０１…乱数生成部、１０２…べき乗算部、１０３…暗号化部、１０４…剰余演算部、１０５…記憶部、１０６…通信部、１０７…入力部、２００…受信者側装置、２０１…鍵生成部、２０２…べき乗算部、２０３…復号化部、２０４…剰余演算部、２０５…記憶部、２０６…通信部、２０７…出力部、３００…通信回線、４０１…ＣＰＵ、４０２…メモリ、４０３…外部記憶装置、４０４…記憶媒体、４０５…読取装置、４０６…入力装置、４０７…出力装置、４０８…通信装置、４０９…バス
【図１】
2004126514.tif 000107
【図２】
2004126514.tif 000108
【図３】
2004126514.tif 000109
【図４】
2004126514.tif 000110
【図５】
2004126514.tif 000111
【図６】
2004126514.tif 000112
【図７】
2004126514.tif 000113
【図８】
2004126514.tif 000114
【図９】
2004126514.tif 000115
【図１０】
2004126514.tif 000116
【図１１】
2004126514.tif 000117
【図１２】
2004126514.tif 000118
【図１３】
2004126514.tif 000119
【図１４】
2004126514.tif 000120