(57)【要約】【課題】攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な公開鍵暗号をベースとする暗号通信技術を提供する。【解決手段】送信者側装置１００は、乱数情報を生成し、この乱数情報とメッセージ文とランダム関数と受信者の公開情報とを用いて、受信者の秘密鍵を知っていてもメッセージ文を復号化できない暗号文であって、当該暗号文からランダム関数への入力値に関する部分情報を計算できない暗号文１と、受信者の秘密鍵を用いて暗号文１から計算される値を与えることで、メッセージ文を復号化できる暗号文２とを作成する。そして、作成した暗号文１、２を受信者側装置２００へ送信する。受信者側装置２００は、送信者側装置１００から前記暗号文１、２を受信し、受信した暗号文２と受信者の秘密鍵とランダム関数とを用いて、受信した暗号文１を検証する。そして、検証が成立した場合に、受信した暗号文２の復号結果をメッセージ文として出力する。【選択図】図１
2006023408.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記送信者側装置が、
乱数情報を生成するステップと、
前記生成した乱数情報と、前記メッセージ文と、ランダムオラクルとしての関数であるランダム関数と、受信者の公開情報とを用いて、前記受信者の秘密鍵を知っていても前記メッセージ文を復号化することができない暗号文であって、当該暗号文から前記ランダム関数への入力値に関する部分情報を計算することができない暗号文（以下、メッセージ文を含まない暗号文１と呼ぶ）と、前記受信者の秘密鍵を用いて前記暗号文１から計算される値を与えることで、前記メッセージ文を復号化することができる暗号文（以下、メッセージ文を含む暗号文２と呼ぶ）と作成するステップと、
前記暗号文１および暗号文２を前記受信者側装置へ送信するステップと、を行い、
（２）前記受信者側装置が、
前記送信者側装置から前記暗号文１および暗号文２を受信するステップと、
前記受信者の秘密鍵、前記ランダム関数、および、前記受信した暗号文２を用いて、前記受信した暗号文１を検証するステップと、
前記検証が成立した場合に、前記受信した暗号文２の復号結果を前記メッセージ文として出力するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項２】
請求項１に記載の暗号通信方法であって、
前記送信者側装置において、前記作成するステップは、前記受信者の公開鍵と共に前記メッセージ文が正しく与えられた場合に、前記受信者の秘密鍵から前記メッセージ文を復号化できる前記暗号文１、２を作成し、前記メッセージ文が与えられていない場合は前記受信者の秘密鍵から前記メッセージ文を復号化することができないように前記暗号文１、２を作成すること
を特徴とする暗号通信方法。
【請求項３】
送信者側装置がメッセージ文ｘの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１,ｒ２∈Ｇを生成するステップと、
前記生成した乱数ｒ１、ｒ２と、前記メッセージ文ｘと、ランダムオラクルとしての関数であるランダム関数Ｇ１、Ｇ２、Ｈ１、Ｈ２と、受信者の公開情報ｇ、ｈとを用いて、
【数１】
2006023408.tif 000020
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、前記受信者の秘密情報ｓに対して、
【数２】
2006023408.tif 000021
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算するステップと、
計算結果（ｕ，ｖ，ｗ）を前記メッセージｘの暗号文として前記受信者側装置に送信するステップと、を行い、
（２）前記受信者側装置が、
前記送信者側装置から前記暗号文（ｕ，ｖ，ｗ）を受信するステップと、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記受信した暗号文（ｕ，ｖ，ｗ）と、前記ランダム関数Ｇ１、Ｇ２とを用いて、
【数３】
2006023408.tif 000022
なるｋ１ビットのｒ’１，ｒ’２∈Ｇを計算すると共に、
【数４】
2006023408.tif 000023
を計算し、計算結果ｘ’と前記ランダム関数Ｈ１、Ｈ２とを用いて、
【数５】
2006023408.tif 000024
が成立するか否かを検証するステップと、
前記検証が成立した場合に、前記計算結果ｘ’を前記メッセージ文ｘとして出力し、前記検証が成立しなかった場合に、前記計算結果ｘ’の出力を拒否するステップと、を行うこと
を特徴とする暗号通信送方法。
【請求項４】
請求項３に記載の暗号通信方法であって、
前記ランダム関数Ｇ１、Ｇ２、Ｈ１、Ｈ２と、前記乱数ｒ１、ｒ２のビット長に関する情報ｋ１とは、前記送信者側装置および前記受信者側装置のそれぞれに予め登録されていること
を特徴とする暗号通信方法。
【請求項５】
送信者側装置がメッセージ文ｘの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１,ｒ２∈Ｇを生成するステップと、
前記生成した乱数ｒ１、ｒ２と、前記メッセージ文ｘと、ランダムオラクルとしての関数であるランダム関数Ｇ１、Ｇ２、Ｈ１、Ｈ２、Ｈ３、Ｈ４と、受信者の公開情報ｇ、ｈとを用いて、
【数６】
2006023408.tif 000025
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、前記受信者の秘密情報ｓに対して、
【数７】
2006023408.tif 000026
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算するステップと、
計算結果（ｕ，ｖ，ｗ）を前記メッセージｘの暗号文として前記受信者側装置に送信するステップと、を行い、
（２）前記受信者側装置が、
前記送信者側装置から前記暗号文（ｕ，ｖ，ｗ）を受信するステップと、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記受信した暗号文（ｕ，ｖ，ｗ）と、前記ランダム関数Ｇ１、Ｇ２とを用いて、
【数８】
2006023408.tif 000027
なるｋ１ビットのｒ’１，ｒ’２∈Ｇを計算すると共に、
【数９】
2006023408.tif 000028
を計算し、計算結果ｘ’と前記ランダム関数Ｈ１、Ｈ２、Ｈ３、Ｈ４とを用いて、
【数１０】
2006023408.tif 000029
が成立するか否かを検証するステップと、
前記検証が成立した場合に、前記計算結果ｘ’を前記メッセージ文ｘとして出力し、前記検証が成立しなかった場合に、前記計算結果ｘ’の出力を拒否するステップと、を行うこと
を特徴とする暗号通信送方法。
【請求項６】
請求項５に記載の暗号通信方法であって、
前記ランダム関数Ｇ１、Ｇ２、Ｈ１、Ｈ２、Ｈ３、Ｈ４と、前記乱数ｒ１、ｒ２のビット長に関する情報ｋ１とは、前記送信者側装置および前記受信者側装置のそれぞれに予め登録されていること
を特徴とする暗号通信方法。
【請求項７】
請求項３乃至６のいずれか一項に記載の暗号通信方法であって、
前記受信者側装置が、前記公開情報（ｇ，ｈ）を生成して、前記送信者側装置に送信するステップをさらに行うこと
を特徴とする鍵配送方法。
【請求項８】
メッセージ文の暗号文を作成して受信者側装置に送信する送信者側装置であって、
乱数情報を生成する手段と、
前記生成した乱数情報と、前記メッセージ文と、ランダムオラクルとしての関数であるランダム関数と、受信者の公開情報とを用いて、前記受信者の秘密鍵を知っていても前記メッセージ文を復号化することができない暗号文であって、当該暗号文から前記ランダム関数への入力値に関する部分情報を計算することができない暗号文（以下、メッセージ文を含まない暗号文１と呼ぶ）と、前記受信者の秘密鍵を用いて前記暗号文１から計算される値を与えることで、前記メッセージ文を復号化することができる暗号文（以下、メッセージ文を含む暗号文２と呼ぶ）と作成する手段と、
前記暗号文１および暗号文２を前記受信者側装置へ送信する手段と、有すること
を特徴とする送信者側装置。
【請求項９】
請求項８記載の送信者側装置より暗号文を受信してメッセージ文を復号化する受信者側装置であって、
前記送信者側装置から前記暗号文１および暗号文２を受信する手段と、
受信者の秘密鍵、前記送信者側装置が前記暗号文１、２を作成する際に用いたランダム関数、および、前記受信した暗号文２を用いて、前記受信した暗号文１を検証する手段と、
前記検証が成立した場合に、前記受信した暗号文２の復号結果を前記メッセージ文として出力する手段と、を有すること
を特徴とする受信者側装置。
【請求項１０】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、
乱数情報を生成する手段、
前記生成した乱数情報と、前記メッセージ文と、ランダムオラクルとしての関数であるランダム関数と、受信者の公開情報とを用いて、前記受信者の秘密鍵を知っていても前記メッセージ文を復号化することができない暗号文であって、当該暗号文から前記ランダム関数への入力値に関する部分情報を計算することができない暗号文（以下、メッセージ文を含まない暗号文１と呼ぶ）と、前記受信者の秘密鍵を用いて前記暗号文１から計算される値を与えることで、前記メッセージ文を復号化することができる暗号文（以下、メッセージ文を含む暗号文２と呼ぶ）と作成する手段、および、
前記暗号文１および暗号文２を前記受信者側装置へ送信する手段として、前記コンピュータを機能させること
を特徴とするコンピュータで読み取り可能なプログラム。
【請求項１１】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、
請求項１０に記載のプログラムが作成した暗号文１および暗号文２を受信する手段、
受信者の秘密鍵と、請求項１０に記載のプログラムが前記暗号文１、２を作成する際に用いたランダム関数と、前記受信した暗号文２と、を用いて、前記受信した暗号文１を検証する手段、および、
前記検証が成立した場合に、前記受信した暗号文２の復号結果を前記メッセージ文として出力する手段として、前記コンピュータを機能させること
を特徴とするコンピュータで読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号通信技術に関し、特に、強化された適応的選択暗号文攻撃に対しても安全な公開鍵暗号通信技術に関する。
【背景技術】
【０００２】
非特許文献１で述べられているように、現在、公開鍵暗号では、適応的選択暗号文攻撃に対して強秘匿（ＩＮＤ（Indistinguishability）-ＣＣＡ２（Adaptive Chosen-Ciphertext Attack））であることが最も安全であると考えられている。
【０００３】
ＩＮＤ-ＣＣＡ２の意味において安全であることが証明可能な公開鍵暗号方式は、大きく２つに分類される。１つは、ランダムオラクル（入力値に対しランダムな値を正しく出力する）を前提とした計算機モデル上で安全性の証明を行うものである。ランダムオラクルという非現実的な仮定を必要とするものの、実用性に優れる公開鍵暗号方法を実現することが可能である。もう１つは、標準的計算モデル上で安全性の証明を行うものである。前者に比べると効率面で劣るが、実システム上で安全性証明が可能であるメリットを持つ。
【０００４】
ランダムオラクルを前提とした計算機モデル上でＩＮＤ-ＣＣＡ２であることが証明可能な実用的暗号方法としては、非特許文献２に記載されている暗号方法や、非特許文献３に記載されている暗号方法や、非特許文献４に記載されている暗号方法などが知られている。一方、標準的計算機モデル上でＩＮＤ-ＣＣＡ２であることが証明可能な実用的暗号方法としては、非特許文献５に記載されている暗号方法が知られている。
【０００５】
【非特許文献１】M. Bellare, A. Desai, D. Pointcheval and P. Rogaway : Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto'98, LNCS1462, Springer-Verlag, pp.26-45 (1998)  [平成１６年５月１１日検索］  インターネット＜URL:http://www-cse.ucsd.edu/users/mihir/papers/relations.pdf＞
【非特許文献２】M. Bellare and P. Rogaway : Random Oracles are Practical -- A Paradigm for Designing Efficient Protocol   [平成１６年５月１１日検索］  インターネット＜URL:http://www-cse.ucsd.edu/users/mihir/papers/ro.pdf＞
【非特許文献３】M. Bellare and P. Rogaway : Optimal Asymmetric Encryption  How to Encrypt with RSA,   [平成１６年５月１１日検索］  インターネット＜URL:http://www-cse.ucsd.edu/users/mihir/papers/oae.pdf＞
【非特許文献４】V. Shoup : OAEP Reconsidered. Available on the e-print library (2000/060), November 2000  [平成１６年５月１１日検索］  インターネット＜URL:http://shoup.net/papers/oaep.pdf＞
【非特許文献５】R. Cramer and V. Shoup : A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack  [平成１６年５月１１日検索］  インターネット＜URL:http://shoup.net/papers/cs.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
さて、本発明では、ランダムオラクルモデル上でＩＮＤ-ＣＣＡ２であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を対象とする。ＩＮＤ-ＣＣＡ２の定義では、ランダムオラクルが公正に与えられる必要がある。しかし、現実世界において、ランダムオラクルを与えるランダム関数（例えばハッシュ関数）が公正であることを示すことは難しい。例えば、公開鍵暗号への攻撃者は、落し戸付きのハッシュ関数を作成し、既存システムのユーザに利用させることにより、そのシステムを破ろうとするかもしれない。また、一般に、公開鍵暗号およびハッシュ関数が別々にデザインされるため、公開鍵暗号の安全性がハッシュ関数により左右されることが起こり得る。
【０００７】
以下、このことについて簡単に説明する。
【０００８】
上記の非特許文献２には、メッセージｘに対しその暗号文（ｕ，ｖ，ｗ）が、
【０００９】
【数１１】
2006023408.tif 000003
【００１０】
により与えられる公開鍵暗号方法が記載されている。なお、数１１において、ｒは乱数であり、ｆは公開された落し戸付き一方向性置換であり、Ｇ、Ｈはランダム関数（例えばハッシュ関数）である。この公開鍵暗号方法は、ハッシュ関数Ｇ、Ｈをランダムオラクルとするとき、ＩＮＤ-ＣＣＡ２であることが非特許文献２の中で示されている。
【００１１】
さて、ハッシュ関数Ｇのデザイナである公開鍵暗号への攻撃者は、ハッシュ関数Ｇをハッシュ関数Ｇ’に対して、Ｇ＝Ｇ’・ｆとなるように作成していたとする（但し、（ｆ・ｇ）（ｘ）＝ｆ（ｇ（ｘ））とする)。ここで、Ｇ’をランダムオラクルとすると、Ｇもランダムオラクルになる点に注意する。
【００１２】
攻撃者はＧ（ｒ）＝（Ｇ’・ｆ）（ｒ）＝Ｇ’（ｆ（ｒ））＝Ｇ’（ｕ）であるので、
【００１３】
【数１２】
2006023408.tif 000004
【００１４】
により、メッセージｘを計算することができる。
【００１５】
このように、従来のＩＮＤ-ＣＣＡ２の定義では、安全である公開鍵暗号であっても、ランダムオラクルを与えるランダム関数を攻撃者が選んだ場合に、不正にメッセージを入手できる場合がある。
【００１６】
本発明は、上記事情に鑑みてなされたものであり、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも安全であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を提供することにある。
【課題を解決するための手段】
【００１７】
上記課題を解決するために本発明の暗号通信方法では、送信者側装置が、乱数情報を生成し、この乱数情報と、メッセージ文と、ランダムオラクルとしての関数であるランダム関数と、受信者の公開情報とを用いて、前記受信者の秘密鍵を知っていても前記メッセージ文を復号化することができない暗号文であって、当該暗号文から前記ランダム関数への入力値に関する部分情報を計算することができない暗号文（以下、メッセージ文を含まない暗号文１と呼ぶ）と、前記受信者の秘密鍵を用いて前記暗号文１から計算される値を与えることで、前記メッセージ文を復号化することができる暗号文（以下、メッセージ文を含む暗号文２と呼ぶ）と作成する。そして、作成した暗号文１、２を受信者側装置へ送信する。一方、前記受信者側装置が、前記送信者側装置から前記暗号文１、２を受信し、受信した暗号文２と、前記受信者の秘密鍵と、前記ランダム関数とを用いて、受信した暗号文１を検証する。そして、検証が成立した場合に、受信した暗号文２の復号結果をメッセージ文として出力する。
【００１８】
例えば、送信者側装置がメッセージ文ｘの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１,ｒ２∈Ｇを生成するステップと、
前記生成した乱数ｒ１、ｒ２と、前記メッセージ文ｘと、ランダムオラクルとしての関数であるランダム関数Ｇ１、Ｇ２、Ｈ１、Ｈ２、Ｈ３、Ｈ４と、受信者の公開情報ｇ、ｈとを用いて、
【００１９】
【数１３】
2006023408.tif 000005
【００２０】
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、前記受信者の秘密情報ｓに対して、
【００２１】
【数１４】
2006023408.tif 000006
【００２２】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算するステップと、
計算結果（ｕ，ｖ，ｗ）を前記メッセージｘの暗号文として前記受信者側装置に送信するステップと、を行い、
（２）前記受信者側装置が、
前記送信者側装置から前記暗号文（ｕ，ｖ，ｗ）を受信するステップと、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記受信した暗号文（ｕ，ｖ，ｗ）と、前記ランダム関数Ｇ１、Ｇ２とを用いて、
【００２３】
【数１５】
2006023408.tif 000007
【００２４】
なるｋ１ビットのｒ’１，ｒ’２∈Ｇを計算すると共に、
【００２５】
【数１６】
2006023408.tif 000008
【００２６】
を計算し、計算結果ｘ’と前記ランダム関数Ｈ１、Ｈ２、Ｈ３、Ｈ４とを用いて、
【００２７】
【数１７】
2006023408.tif 000009
【００２８】
が成立するか否かを検証するステップと、
前記検証が成立した場合に、前記計算結果ｘ’を前記メッセージ文ｘとして出力し、前記検証が成立しなかった場合に、前記計算結果ｘ’の出力を拒否するステップとを行う。
【発明の効果】
【００２９】
本発明によれば、攻撃者がランダム関数を選んで適応的選択暗号文攻撃を行なった場合でも、送信者側装置が送信する暗号文１、２からランダム関数への入力値に関する部分情報を計算することができない。したがって、攻撃者がランダム関数を選んだ場合でも安全な、公開鍵暗号をベースとする暗号通信技術を提供できる。
【発明を実施するための最良の形態】
【００３０】
以下に、本発明の実施の形態について説明する。
【００３１】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００３２】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。図示するように、公開鍵暗号通信システムは、暗号化処理を行なってメッセージの暗号文を作成する送信者側装置１００と、復号化処理を行なってメッセージを復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００３３】
図２は、図１に示す送信者側装置１００の概略構成図である。図示するように、乱数生成部１０１と、論理演算、べき乗算、剰余演算、ランダム関数演算を含む各種演算を行う演算部１０２と、記憶部１０３と、暗号化対象のメッセージを含む各種情報の入力を受け付ける入力部１０４と、通信回線３００を介して受信者側装置２００と通信を行なう通信部１０５と、を備えている。
【００３４】
図３は、図１に示す受信者側装置２００の概略構成図である。図示するように、論理演算、べき乗算、剰余演算、ランダム関数演算を含む各種演算を行う演算部２０１と、記憶部２０２と、検査部２０３と、通信回線３００を介して送信者側装置１００と通信を行なう通信部２０４と、復号結果を含む各種情報を出力する出力部２０５と、を備えている。
【００３５】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０４から情報を読み出す読取装置４０５と、キーボードやマウスなどの入力装置４０６と、ディスプレイなどの出力装置４０７と、通信回線３００を介して相手装置と通信を行なうための通信装置４０８と、を備えた一般的なコンピュータにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１０３、２０３に利用され、通信装置４０８が通信部１０５、２０４に利用され、入力装置４０６や読取装置４０５が入力部１０４に利用され、そして、出力装置４０７が出力部２０５に利用される。
【００３６】
この所定のプログラムは、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００３７】
<<第１実施形態>>
次に、本発明の第１実施形態について説明する。図５は本発明の第１実施形態の動作手順を説明するための図である。
【００３８】
１．送信側処理
送信者側装置１００において、入力部１０４は、送信者よりメッセージｘ∈｛０，１｝ｋを受け付けて、記憶部１０３に記憶する（ステップＳ１００１）。
【００３９】
次に、乱数生成部１０１は、ｋ１ビットの乱数ｒ１，ｒ２∈Ｇを生成し、これを演算部１０２に渡す（Ｓ１００２）。
【００４０】
演算部１０２は、乱数生成部１０１から乱数ｒ１，ｒ２を受け取ると、記憶部１０８に予め記憶されている受信者の公開情報ｇ，ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｇ１，Ｇ２，Ｈ１，Ｈ２と、メッセージｘとを読み出す。さて、演算部１０２は、これらの情報を用いて、
【００４１】
【数１８】
2006023408.tif 000010
【００４２】
を計算し、その計算結果（ｕ，ｖ，ｗ）を通信部１０５に渡す（Ｓ１００３）。ここで、Ｇはアーベル群である。また、ｇ，ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００４３】
【数１９】
2006023408.tif 000011
【００４４】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。また、ｋビット列全体の集合からアーベル群Ｇへの一対一写像が存在するものとし、これによりｋビット列をＧの元とみなす。このとき、ｋ＝２ｋ１なる関係がある。
【００４５】
通信部１０５は、演算部１０２から計算結果（ｕ，ｖ，ｗ）を受け取ると、これを送信データとして、通信回線３００を介して受信側装置２００に送信する（Ｓ１００４）。
【００４６】
２．受信側処理
受信者側装置２００において、通信部２０４は、通信回線３００を介して送信者側装置１００より送信データ（ｕ，ｖ，ｗ）を受け取ると、これを演算部２０１に渡す（Ｓ２００１）。
【００４７】
演算部２０４は、通信部２０１より送信データ（ｕ，ｖ，ｗ）を受け取ると、記憶部２０７に予め記憶されている受信者の秘密情報ｓを読み出す。そして、これらの情報を用いて、
【００４８】
【数２０】
2006023408.tif 000012
【００４９】
を満足するｋ１ビットの乱数ｒ’１,ｒ’２∈Ｇを計算する（Ｓ２００２）。そして、記憶部２０７に予め記憶されているランダム関数Ｇ１，Ｇ２と、計算結果ｒ’１、ｒ’２とを用いて、
【００５０】
【数２１】
2006023408.tif 000013
【００５１】
を計算する（Ｓ２００３）。さらに、記憶部２０７に予め記憶されている受信者の公開情報ｇおよびランダム関数Ｈ１，Ｈ２と、計算結果ｘ’，ｒ’１、ｒ’２とを用いて、
【００５２】
【数２２】
2006023408.tif 000014
【００５３】
を計算する。そして、計算結果ｕ，ｘ’を、送信データ（ｕ，ｖ，ｗ）と共に検査部２０３に渡す。検査部２０３は、演算部２０１での計算結果ｕ’が送信データ（ｕ，ｖ，ｗ）に含まれている情報ｕと一致するか否かを調べる（Ｓ２００４）。一致する場合は、演算部２０１での計算結果ｘ’を送信者側装置１００が送信したメッセージ文ｘとして、出力部２０５から出力する。一致しない場合は、送信データ（ｕ，ｖ，ｗ）が不正なものであると判断して計算結果ｘ’の出力を拒否し、その旨を示すエラーメッセージなどを出力部２０５から出力する（Ｓ２００５）。
【００５４】
以上、本発明の第１実施形態について説明した。
【００５５】
本実施形態では、上記の非特許文献３に記載されている、公開鍵暗号がＩＮＤ-ＣＣＡ２であることの証明方法と同様の方法により、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも、送信データ（ｕ，ｖ，ｗ）からメッセージ文ｘおよびランダム関数Ｈ１，Ｈ２，Ｇ１，Ｇ２への入力値に関する部分情報が漏れないことを証明できる。したがって、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも、強秘匿（ＩＮＤ-ＣＰＡ（Chosen-Plaintext Attack））となる。
【００５６】
本実施形態において、メッセージｘの暗号文である送信データ（ｕ，ｖ，ｗ）は、２つの暗号文（ｕ，ｖ）（以下、暗号文１と呼ぶ）と暗号文ｗ（以下、暗号文２と呼ぶ）とに分けることができる。暗号文１では、メッセージ文ｘがランダム関数Ｈ１，Ｈ２への入力値の一部として使われている。しかし、暗号文１はメッセージ文を含まない。ここで、「メッセージ文を含まない暗号文」とは、受信者の秘密鍵を知っていてもメッセージ文を復号化できない暗号文を指す。一方、「メッセージ文を含む暗号文」とは、受信者の秘密鍵を用いて「メッセージ文を含まない暗号文」から計算される値を与えることで、メッセージ文を復号化することができる暗号文を指す。暗号文１は、送信データ（ｕ，ｖ，ｗ）からメッセージ文ｘおよびランダム関数Ｈ１，Ｈ２，Ｇ１，Ｇ２への入力値に関する部分情報が漏れないようにするための役目を担っている。これに対して、暗号文２は、メッセージ文ｘを含んでおり、このメッセージ文ｘは、暗号文１における正当性が確認された後に出力されることになっている。このように、本実施形態において、送信者側装置１００から受信者側装置２００へ送信される送信データ（暗号文）は、強化された適応的選択暗号文攻撃に対する安全性を確保するための「メッセージ文を含まない暗号文１」とメッセージを復号するための「メッセージ文を含む暗号文２」とを備えて構成される特徴を持つ。
【００５７】
なお、本実施形態では、アーベル群Ｇにおける演算を便宜上の積の形で表している。Ｇの選び方としては、例えば素数を法とする剰余体から導かれる乗法群や楕円曲線から決定される加法群など、様々なものを適用できる。
【００５８】
<<第２実施形態>>
次に、本発明の第２実施形態について説明する。本実施形態は、上記の第１実施形態の変形例であり、メッセージ文ｘの長さを任意に設定することができる。図６は本発明の第２実施形態の動作手順を説明するための図である。
【００５９】
１．送信側処理
送信者側装置１００において、入力部１０４は、送信者よりメッセージｘ∈｛０，１｝ｋを受け付けて、記憶部１０３に記憶する（ステップＳ１１０１）。
【００６０】
次に、乱数生成部１０１は、ｋ１ビットの乱数ｒ１，ｒ２∈Ｇを生成し、これを演算部１０２に渡す（Ｓ１１０２）。
【００６１】
演算部１０２は、乱数生成部１０１から乱数ｒ１，ｒ２を受け取ると、記憶部１０８に予め記憶されている受信者の公開情報ｇ，ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｇ１，Ｇ２，Ｈ１，Ｈ２，Ｈ３，Ｈ４と、メッセージｘとを読み出す。さて、演算部１０２は、これらの情報を用いて、
【００６２】
【数２３】
2006023408.tif 000015
【００６３】
を計算し、その計算結果（ｕ，ｖ，ｗ）を通信部１０５に渡す（Ｓ１１０３）。ここで、Ｇはアーベル群である。また、ｇ，ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００６４】
【数２４】
2006023408.tif 000016
【００６５】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。また、ｋビット列全体の集合からアーベル群Ｇへの一対一写像が存在するものとし、これによりｋビット列をＧの元とみなす。このとき、ｋ＝２ｋ１なる関係がある。
【００６６】
通信部１０５は、演算部１０２から計算結果（ｕ，ｖ，ｗ）を受け取ると、これを送信データとして、通信回線３００を介して受信側装置２００に送信する（Ｓ１１０４）。
【００６７】
２．受信側処理
受信者側装置２００において、通信部２０４は、通信回線３００を介して送信者側装置１００より送信データ（ｕ，ｖ，ｗ）を受け取ると、これを演算部２０１に渡す（Ｓ２１０１）。
【００６８】
演算部２０４は、通信部２０１より送信データ（ｕ，ｖ，ｗ）を受け取ると、記憶部２０７に予め記憶されている受信者の秘密情報ｓを読み出す。そして、これらの情報を用いて、
【００６９】
【数２５】
2006023408.tif 000017
【００７０】
を満足するｋ１ビットの乱数ｒ’１,ｒ’２∈Ｇを計算する（Ｓ２１０２）。そして、記憶部２０７に予め記憶されているランダム関数Ｇ１，Ｇ２と、計算結果ｒ’１、ｒ’２とを用いて、
【００７１】
【数２６】
2006023408.tif 000018
【００７２】
を計算する（Ｓ２１０３）。さらに、記憶部２０７に予め記憶されている受信者の公開情報ｇおよびランダム関数Ｈ１，Ｈ２，Ｈ３，Ｈ４と、計算結果ｘ’，ｒ’１、ｒ’２とを用いて、
【００７３】
【数２７】
2006023408.tif 000019
【００７４】
を計算する。そして、計算結果ｕ’，ｘ’を、送信データ（ｕ，ｖ，ｗ）と共に検査部２０３に渡す。検査部２０３は、演算部２０１での計算結果ｕ’が送信データ（ｕ，ｖ，ｗ）に含まれている情報ｕと一致するか否かを調べる（Ｓ２１０４）。一致する場合は、演算部２０１での計算結果ｘ’を送信者側装置１００が送信したメッセージ文ｘとして、出力部２０５から出力する。一致しない場合は、送信データ（ｕ，ｖ，ｗ）が不正なものであると判断して計算結果ｘ’の出力を拒否し、その旨を示すエラーメッセージなどを出力部２０５から出力する（Ｓ２００５）。
【００７５】
以上、本発明の第１実施形態について説明した。
【００７６】
本実施形態では、上記の第１実施形態に効果に加えて、ランダム関数Ｈ３，Ｈ４，Ｇ１，Ｇ２の出力値のビット数を変えることで、メッセージｘの長さを任意に設定することができる利点を有する。
【００７７】
なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。例えば、上記の各実施形態において、受信者の公開情報ｇ、ｈおよび秘密情報ｓは、受信者側装置２００に設けられた鍵生成部が予め生成し、記憶部２０２に記憶すると共に、公開情報ｇ、ｈを通信部２０４を介して送信者側装置１００に送信し、送信者側装置１００の記憶部１０３に記憶するようにしてもよい。
【００７８】
また、上記の各実施形態において、ランダム関数Ｈ１，Ｈ２，Ｇ１，Ｇ２（第２実施形態の場合はさらにＨ３，Ｈ４）と、乱数ｒ１、ｒ２のビット長に関する情報ｋ１とは、送信者側装置１００の記憶部１０３および受信者側装置２００の記憶部２０２のそれぞれに予め記憶されているものとしてもよい。
【００７９】
また、上記の各実施形態において、送信者側装置１００が受信者側装置２００の機能も有するものでもよい。同様に、受信者側装置２００が送信者側装置１００の機能も有するものでもよい。
【００８０】
また、上記の各実施形態では、送信者と受信者とが各々の装置を利用して鍵の共有を行い、それから暗号通信を行うという一般的な通信システムを例にとり説明したが、本発明は、様々なシステムに適用可能である。例えば、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店であり、受信者側装置はパソコンなどの計算機となる。ユーザの商品等の注文書は、共通鍵暗号で暗号化されることが多い。この場合、注文書の暗復号に用いる共通鍵（メッセージ文ｘに相当）が本発明の方法により暗号化されて、受信者（小売店）側装置に送信される。また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信文(メール)は共通鍵暗号で暗号化されることが多い。この場合、送信文の暗復号に用いる共通鍵（メッセージ文ｘに相当）が本発明の方法により暗号化されて、受信者の計算機に送信される。その他にも、従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【００８１】
また、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムだけではない。いずれかの計算を行なう装置は、ハードウエア化された演算装置であって、他の演算装置やＣＰＵとデータのやりとりを行うものでもよい。
【図面の簡単な説明】
【００８２】
【図１】本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第１実施形態の動作手順を説明するための図である。
【図６】本発明の第２実施形態の動作手順を説明するための図である。
【符号の説明】
【００８３】
１００…送信者側装置、１０１…乱数生成部、１０２…演算部、１０３…記憶部、１０４…入力部、１０５…通信部、２００…受信者側装置、２０１…演算部、２０２…記憶部、２０３…検査部、２０４…通信部、２０５…出力部、３００…通信回線、４０１…ＣＰＵ、４０２…メモリ、４０３…外部記憶装置、４０４…記憶媒体、４０５…読取装置、４０６…入力装置、４０７…出力装置、４０８…通信装置、４０９…バス
【図１】
2006023408.tif 000030
【図２】
2006023408.tif 000031
【図３】
2006023408.tif 000032
【図４】
2006023408.tif 000033
【図５】
2006023408.tif 000034
【図６】
2006023408.tif 000035