(57)【要約】【課題】攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な、公開鍵暗号をベースとする鍵配送技術を提供する。【解決手段】送信者側装置１００は、ランダム関数への入力値をランダムに選択し、このランダム関数および受信者の公開鍵を用いて入力値の暗号文を作成し、これを送信データとして受信者側装置２００へ送信する。この際、ランダム関数への入力値に関する部分情報を送信データから計算することが困難となるように、当該送信データを作成する。また、送信者側装置１００が、入力値を所定の関数に入力して鍵情報を計算する。一方、受信者側装置２００は、ランダム関数および受信者の秘密鍵を用いて送信者側装置１００より受信した送信データを復号化する。そして、この復号結果を所定の関数に入力し鍵情報を計算する。【選択図】図１
2005354164.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置および受信者側装置間で暗号通信に用いる鍵情報を共有するための鍵配送方法であって、
（１）前記送信者側装置が、
乱数情報を生成するステップと、
生成した乱数情報を入力値とするランダム関数および受信者の公開情報を用いて、前記入力値に対する暗号化データを、当該暗号化データから前記ランダム関数への入力値に関する部分情報が秘匿されるように作成し、これを送信データとして前記受信者側装置へ送信するステップと、
前記ランダム関数への入力値を所定の関数に入力して鍵情報を計算するステップと、を行い、
（２）前記受信者側装置が、
前記ランダム関数および前記公開情報と対の秘密情報を用いて、前記送信者側装置より受信した送信データを復号化するステップと、
前記送信データの復号結果を前記所定の関数に入力して前記鍵情報を計算するステップと、を行うこと
を特徴とする鍵配送方法。
【請求項２】
送信者側装置および受信者側装置間で暗号通信に用いる鍵情報を共有するための鍵配送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成するステップと、
生成した乱数ｒ１、ｒ２と、受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを用いて、
【数１】
2005354164.tif 000030
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【数２】
2005354164.tif 000031
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算し、計算結果（ｕ、ｖ）を送信データとして前記受信者側装置に送信するステップと、
生成した乱数ｒ１、ｒ２と所定の鍵生成関数Ｆとを用いて、
【数３】
2005354164.tif 000032
を送信者および受信者間で共有する鍵情報Ｋとして計算するステップと、を行い、
（２）前記受信者側装置が、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記送信者側装置より受信した送信データ（ｕ，ｖ）と、前記ランダム関数Ｈ１、Ｈ２とを用いて、
【数４】
2005354164.tif 000033
なるｋ１ビットのｒ’１∈Ｇおよびｋ２ビットのｒ’２∈Ｇを計算すると共に、
【数５】
2005354164.tif 000034
が成立するか否かを検査するステップと、
前記検査をパスした場合に、前記鍵生成関数Ｆを用いて、
【数６】
2005354164.tif 000035
を送信者および受信者間で共有する鍵情報Ｋ’として計算し、前記検査をパスしなかった場合に、前記受信した送信データ（ｕ，ｖ）が不正なものと判断して、鍵情報の計算を拒否するステップと、を行うこと
を特徴とする鍵配送方法。
【請求項３】
送信者側装置および受信者側装置間で暗号通信に用いる鍵情報を共有するための鍵配送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成するステップと、
生成した乱数ｒ１、ｒ２と、受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを用いて、
【数７】
2005354164.tif 000036
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【数８】
2005354164.tif 000037
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算し、情報ｕ，ｖを生成するステップと、
生成した乱数ｒ１、ｒ２と所定の鍵生成関数Ｆとを用いて、
【数９】
2005354164.tif 000038
を送信者および受信者間で共有する鍵情報Ｋとして計算するステップと、
計算した鍵情報Ｋを用いてメッセージｍを暗号化して、暗号文Ｃを作成するステップと、
情報ｕ、ｖおよび暗号文Ｃを送信データ（ｕ，ｖ，Ｃ）として前記受信者側装置に送信するステップと、を行い、
（２）前記受信者側装置が、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記送信者側装置より受信した送信データ（ｕ，ｖ，Ｃ）に含まれている情報ｕ、ｖと、前記ランダム関数Ｈ１、Ｈ２とを用いて、
【数１０】
2005354164.tif 000039
なるｋ１ビットのｒ’１∈Ｇおよびｋ２ビットのｒ’２∈Ｇを計算すると共に、
【数１１】
2005354164.tif 000040
が成立するか否かを検査するステップと、
前記検査をパスした場合に、前記鍵生成関数Ｆを用いて、
【数１２】
2005354164.tif 000041
を送信者および受信者間で共有する鍵情報Ｋ’として計算し、計算した鍵情報Ｋ’を用いて、前記受信した送信データ（ｕ，ｖ，Ｃ）に含まれている暗号文Ｃから前記メッセージｍ’を復号化し、前記検査をパスしなかった場合に、前記受信した送信データ（ｕ，ｖ，Ｃ）が不正なものと判断して、鍵情報の計算を拒否するステップと、を行うこと
を特徴とする鍵配送方法。
【請求項４】
送信者側装置および受信者側装置間で暗号通信に用いる鍵情報を共有するための鍵配送方法であって、
（１）前記送信者側装置が、
ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成するステップと、
生成した乱数ｒ１、ｒ２と、受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを用いて、
【数１３】
2005354164.tif 000042
（但し、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【数１４】
2005354164.tif 000043
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。）を計算し、情報ｕ，ｖを生成するステップと、
生成した乱数ｒ１、ｒ２と所定の鍵生成関数Ｆとを用いて、
【数１５】
2005354164.tif 000044
を送信者および受信者間で共有する鍵情報Ｋとして計算するステップと、
計算した鍵情報Ｋを用いてメッセージｍを暗号化して、暗号文Ｃを作成するステップと、
生成した乱数ｒ１、ｒ２と、送信者および受信者の両方に対して公開されたランダム関数Ｈ３と、前記メッセージｍとを用いて、
【数１６】
2005354164.tif 000045
を計算し、情報ｗを生成するステップと、
生成した情報ｕ、ｖ、ｗおよび暗号文Ｃを送信データ（ｕ，ｖ，ｗ，Ｃ）として前記受信者側装置に送信するステップと、を行い、
（２）前記受信者側装置が、
前記公開情報ｇ、ｈと対の秘密情報ｓと、前記送信者側装置より受信した送信データ（ｕ，ｖ，ｗ，Ｃ）に含まれている情報ｕ、ｖと、前記ランダム関数Ｈ１、Ｈ２とを用いて、
【数１７】
2005354164.tif 000046
なるｋ１ビットのｒ’１∈Ｇおよびｋ２ビットのｒ’２∈Ｇを計算するステップと、
計算したｒ’１、ｒ’２と、前記鍵生成関数Ｆとを用いて、
【数１８】
2005354164.tif 000047
を送信者および受信者間で共有する鍵情報Ｋ’し、計算した鍵情報Ｋ’を用いて、前記受信した送信データ（ｕ，ｖ，ｗ，Ｃ）に含まれている暗号文Ｃを復号化し、メッセージｍ’を得るステップと、
前記メッセージｍ’と、計算したｒ’１、ｒ’２と、前記公開情報ｇと、前記送信者側装置より受信した送信データ（ｕ，ｖ，ｗ，Ｃ）に含まれている情報ｕ、ｗと、前記ランダム関数Ｈ１、Ｈ２、Ｈ３と、を用いて、
【数１９】
2005354164.tif 000048
が成立するか否かを検査し、前記検査をパスした場合に、前記メッセージｍ’を出力し、前記検査をパスしなかった場合に、前記受信した送信データ（ｕ，ｖ，ｗ，Ｃ）が不正なものと判断して、前記メッセージｍ’の出力を拒否するステップと、を行うこと
を特徴とする鍵配送方法。
【請求項５】
請求項２乃至４のいずれか１項に記載の鍵配送方法であって、
前記受信者側装置が、前記公開情報（ｇ，ｈ）を生成して、前記送信者側装置に送信するステップをさらに行うこと
を特徴とする鍵配送方法。
【請求項６】
請求項２又は３に記載の鍵配送方法であって、
前記ランダム関数Ｈ１、Ｈ２と、前記乱数ｒ１、ｒ２のビット長に関する情報ｋ１、ｋ２と、前記鍵生成関数Ｆとは、前記送信者側装置および前記受信者側装置のそれぞれに予め登録されていること
を特徴とする鍵配送方法。
【請求項７】
請求項４に記載の鍵配送方法であって、
前記ランダム関数Ｈ１、Ｈ２、Ｈ３と、前記乱数ｒ１、ｒ２のビット長に関する情報ｋ１、ｋ２と、前記鍵生成関数Ｆとは、前記送信者側装置および前記受信者側装置のそれぞれに予め登録されていること
を特徴とする鍵配送方法。
【請求項８】
暗号通信に用いる鍵情報を受信者側装置に配送する送信者側装置であって、
乱数情報を生成する手段と、
生成した乱数情報を入力値とするランダム関数および受信者の公開情報を用いて、前記入力値に対する暗号化データを、当該暗号化データから前記ランダム関数への入力値に関する部分情報が秘匿されるように作成する手段と、
作成した暗号化データを送信データとして前記受信者側装置へ送信する手段と、
前記ランダム関数への入力値から鍵情報を計算する手段と、を有すること
を特徴とする送信者側装置。
【請求項９】
請求項８記載の送信者側装置より受信した送信データから暗号通信に用いる鍵情報を入手する受信者側装置であって、
前記送信データの作成に用いられたランダム関数および公開情報と対の秘密情報を用いて、前記送信データを復号化する手段と、
前記送信データの復号結果から前記鍵情報を計算する手段と、を有すること
を特徴とする受信者側装置。
【請求項１０】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、
乱数情報を生成する手段、
生成した乱数情報を入力値とするランダム関数および受信者の公開情報を用いて、前記入力値に対する暗号化データを、当該暗号化データから前記ランダム関数への入力値に関する部分情報が秘匿されるように作成する手段、および、
作成した暗号化データを送信データとして前記受信者側装置へ送信する手段と、
前記ランダム関数への入力値から鍵情報を計算する手段として、前記コンピュータを機能させること
を特徴とするコンピュータで読み取り可能なプログラム。
【請求項１１】
コンピュータで読み取り可能なプログラムであって、
前記プログラムは、
請求項１０に記載のプログラムが送信データを作成する際に用いたランダム関数および公開情報と対の秘密情報を用いて、前記送信データを復号化する手段、および、
前記送信データの復号結果から鍵情報を計算する手段として、前記コンピュータを機能させること
を特徴とするコンピュータで読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号通信に用いる鍵の配送技術に関する。特に、強化された適応的選択暗号文攻撃に対しても安全な鍵の配送技術に関する。
【背景技術】
【０００２】
非特許文献１で述べられているように、現在、公開鍵暗号では、適応的選択暗号文攻撃に対して強秘匿（ＩＮＤ（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＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
さて、本発明では、ランダムオラクルモデル上でＩＮＤ-ＣＣＡ２であることが証明可能な、公開鍵暗号をベースとする鍵配送技術を対象とする。ＩＮＤ-ＣＣＡ２の定義では、ランダムオラクルが公正に与えられる必要がある。しかし、現実世界において、ランダムオラクルを与えるランダム関数（例えばハッシュ関数）が公正であることを示すことは難しい。例えば、公開鍵暗号への攻撃者は、落し戸付きのハッシュ関数を作成し、既存システムのユーザに利用させることにより、そのシステムを破ろうとするかもしれない。また、一般に、公開鍵暗号およびハッシュ関数が別々にデザインされるため、公開鍵暗号の安全性がハッシュ関数により左右されることが起こり得る。
【０００７】
以下、このことについて簡単に説明する。
【０００８】
上記の非特許文献２には、メッセージｘに対しその暗号文（ｕ，ｖ，ｗ）が、
【０００９】
【数２０】
2005354164.tif 000003
【００１０】
により与えられる公開鍵暗号方法が記載されている。なお、数２０において、ｆは公開された落し戸付き一方向性置換であり、Ｇ、Ｈはランダム関数（例えばハッシュ関数）である。この公開鍵暗号方法は、ハッシュ関数Ｇ、Ｈをランダムオラクルとするとき、ＩＮＤ-ＣＣＡ２であることが非特許文献２の中で示されている。
【００１１】
さて、ハッシュ関数Ｇのデザイナである公開鍵暗号への攻撃者は、ハッシュ関数Ｇをハッシュ関数Ｇ’に対して、Ｇ＝Ｇ’・ｆとなるように作成していたとする（但し、（ｆ・ｇ）（ｘ）＝ｆ（ｇ（ｘ））とする)。ここで、Ｇ’をランダムオラクルとすると、Ｇもランダムオラクルになる点に注意する。
【００１２】
攻撃者はＧ（ｒ）＝（Ｇ’・ｆ）（ｒ）＝Ｇ’（ｆ（ｒ））＝Ｇ’（ｕ）であるので、
【００１３】
【数２１】
2005354164.tif 000004
【００１４】
により、メッセージｘを計算することができる。
【００１５】
このように、従来のＩＮＤ-ＣＣＡ２の定義では、安全である公開鍵暗号であっても、ランダムオラクルを与えるランダム関数を攻撃者が選んだ場合に、不正にメッセージを入手できる場合がある。したがって、従来のＩＮＤ-ＣＣＡ２の定義において安全である公開鍵暗号を用いて暗号通信に用いる鍵を配送した場合も、同様に不正に鍵を入手できる場合がある。
【００１６】
本発明は、上記事情に鑑みてなされたものであり、公開鍵暗号への攻撃者がランダムオラクルを与えるランダム関数を選んだ場合でも、安全であることが証明可能な、公開鍵暗号をベースとする鍵配送技術を提供することにある。
【課題を解決するための手段】
【００１７】
上記課題を解決するために本発明の鍵配送方法では、送信者側装置が、ランダム関数への入力値をランダムに選択し、このランダム関数および受信者の公開鍵を用いて前記入力値の暗号データを作成し、これを送信データとして受信者側装置へ送信する。この際、前記送信データから前記入力値に関する部分情報が秘匿されるように、つまり、前記送信データを作成する際に用いたランダムオラクルとしての前記ランダム関数への入力値に関する部分情報を、前記送信データから計算することが困難となるように前記送信データを作成する。また、前記送信者側装置が、前記入力値を所定の関数に入力し、共通の鍵情報を計算する。一方、前記受信者側装置が、前記ランダム関数および前記公開鍵と対の秘密鍵を用いて前記送信者側装置より受信した前記送信データを復号化する。そして、この復号結果を前記所定の関数に入力して、前記共通の鍵情報を計算する。
【００１８】
例えば、送信者側装置が、ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを選ぶ。次に、受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダムオラクル（以下、ランダム関数という）Ｈ１、Ｈ２を用いて、
【００１９】
【数２２】
2005354164.tif 000005
【００２０】
を計算する。ここで、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００２１】
【数２３】
2005354164.tif 000006
【００２２】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。
【００２３】
次に、送信者側装置が、鍵生成関数Ｆを用いて、
【００２４】
【数２４】
2005354164.tif 000007
【００２５】
を送信者および受信者間で共有する鍵情報Ｋとして計算する。また、送信者側装置に送信データ（ｕ，ｖ）を送信する。
【００２６】
一方、受信者側装置は、受信者の秘密鍵情報ｓ、送信者側装置より受信した送信データ（ｕ，ｖ）、および、ランダム関数Ｈ１、Ｈ２を用いて、
【００２７】
【数２５】
2005354164.tif 000008
【００２８】
なるｋ１ビットのｒ’１∈Ｇおよびｋ２ビットのｒ’２∈Ｇを計算する。そして、
【００２９】
【数２６】
2005354164.tif 000009
【００３０】
が成立するか否かを検査する。この検査をパスした場合、受信者側装置は鍵生成関数Ｆを用いて、
【００３１】
【数２７】
2005354164.tif 000010
【００３２】
を計算し、このＫ’を送信者および受信者間で共有する鍵情報とする。一方、検査にパスしなかった場合、受信者側装置は送信データ（ｕ，ｖ）が不正なものと判断し、鍵情報の計算を拒否する。
【発明の効果】
【００３３】
本発明によれば、攻撃者がランダム関数を選んで適応的選択暗号文攻撃を行なった場合でも、送信者側装置の送信データからランダム関数への入力値に関する部分情報を計算することができない。したがって、攻撃者がランダム関数を選んだ場合でも安全な、公開鍵暗号をベースとする鍵配送技術を提供できる。
【発明を実施するための最良の形態】
【００３４】
以下に、本発明の実施の形態について説明する。
【００３５】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００３６】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。図示するように、公開鍵暗号通信システムは、暗号化処理を行なってメッセージの暗号文を作成する送信者側装置１００と、復号化処理を行なってメッセージを復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００３７】
図２は、図１に示す送信者側装置１００の概略構成図である。図示するように、暗号化対象のメッセージを含む各種情報の入力を受け付ける入力部１０７と、乱数生成部１０１と、演算部１０２と、暗号化部１０６と、記憶部１０８と、鍵生成部１０３と、通信回線３００を介して受信者側装置２００と通信を行なう通信部１０５と、鍵情報を含む各種情報を出力する出力部１０４と、を備えている。
【００３８】
図３は、図１に示す受信者側装置２００の概略構成図である。図示するように、通信回線３００を介して送信者側装置１００と通信を行なう通信部２０１と、鍵生成部２０４と、演算部２０２と、復号化部２０６と、記憶部２０７と、検査部２０３と、復号結果を含む各種情報を出力する出力部２０５と、を備えている。
【００３９】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０４から情報を読み出す読取装置４０５と、キーボードやマウスなどの入力装置４０６と、ディスプレイなどの出力装置４０７と、通信回線３００を介して相手装置と通信を行なうための通信装置４０８と、を備えた一般的なコンピュータにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１０８、２０７に利用され、通信装置４０８が通信部１０５、２０１に利用され、入力装置４０６が入力部１０７に利用され、そして、出力装置４０７が出力部１０４、２０５に利用される。
【００４０】
この所定のプログラムは、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００４１】
<<第１実施形態>>
次に、本発明の第１実施形態について説明する。図５は本発明の第１実施形態の動作手順を説明するための図である。
【００４２】
１．送信側処理
送信者側装置１００において、乱数生成部１０１は、ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成し、これを演算部１０２および鍵生成部１０３に渡す（Ｓ１００１）。
【００４３】
演算部１０２は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、記憶部１０８に予め記憶されている受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを読み出す。そして、これらの情報を用いて、
【００４４】
【数２８】
2005354164.tif 000011
【００４５】
を計算し、その計算結果（ｕ，ｖ）を通信部１０５に渡す（Ｓ１００２）。ここで、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００４６】
【数２９】
2005354164.tif 000012
【００４７】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。
【００４８】
また、鍵生成部１０３は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、所定の鍵生成関数Ｆを用いて、
【００４９】
【数３０】
2005354164.tif 000013
【００５０】
を送信者および受信者間で共有する鍵情報Ｋとして計算する。そして、この鍵情報Ｋを記憶部１０８に記憶すると共に、出力部１０４から出力する（Ｓ１００３）。
【００５１】
また、通信部１０５は、演算部１０２から計算結果（ｕ，ｖ）を受け取ると、これを送信データとして、通信回線３００を介して受信側装置２００に送信する（Ｓ１００４）。
【００５２】
２．受信側処理
受信者側装置２００において、通信部２０１は、通信回線３００を介して送信者側装置１００より送信データ（ｕ，ｖ）を受け取ると、これを演算部２０２および検査部２０３に渡す（Ｓ２００１）。
【００５３】
演算部２０２は、通信部２０１より送信データ（ｕ，ｖ）を受け取ると、記憶部２０７に予め記憶されている受信者の秘密情報ｓを読み出す。そして、これらの情報を用いて、
【００５４】
【数３１】
2005354164.tif 000014
【００５５】
を満足するｋ１ビットの乱数ｒ’１∈Ｇおよびｋ２ビットの乱数ｒ’２∈Ｇを計算する。そして、計算結果ｒ’１、ｒ’２を検査部２０３に渡す（Ｓ２００２）。
【００５６】
また、検査部２０３は、演算部２０２から計算結果ｒ’１、ｒ’２を受け取ると、記憶部２０７に予め記憶されている受信者の公開情報ｇと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを読み出す。そして、これらの情報と通信部２０１より受け取った送信データ（ｕ，ｖ）とを用いて、
【００５７】
【数３２】
2005354164.tif 000015
【００５８】
が成立するか否かを検査する（Ｓ２００３）。そして、成立しない場合は、送信データ（ｕ，ｖ）が不正なものと判断し、鍵情報の計算を拒否し、その旨を示すエラーメッセージなどを出力部２０５から出力する。一方、成立する場合、計算結果ｒ’１、ｒ’２を鍵生成部２０４に出力する。これを受けて、鍵生成部２０４は、前記所定の鍵生成関数Ｆを用いて、
【００５９】
【数３３】
2005354164.tif 000016
【００６０】
を送信者および受信者間で共有する鍵情報Ｋ’として計算する。そして、この鍵情報Ｋ’を記憶部２０７に記憶すると共に、出力部２０５から出力する（Ｓ２００４）。
【００６１】
以上、本発明の第１実施形態について説明した。
【００６２】
本実施形態では、上記の非特許文献３に記載されている、公開鍵暗号がＩＮＤ-ＣＣＡ２であることの証明方法と同様の方法により、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも、本実施形態の鍵配送が安全であることを証明できる。すなわち、ＩＮＤ-ＣＣＡ２の意味において、本実施形態による鍵配送を破ろうとする攻撃者が鍵情報を得るためには、送信データ（ｕ，ｖ）に対する元の情報（ランダム関数への入力値つまり乱数ｒ１、ｒ２）を知る必要がある。しかし、攻撃者は乱数ｒ１、ｒ２のいかなる部分情報も得ることができない。したがって、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも、強秘匿（ＩＮＤ-ＣＰＡ（Chosen-Plaintext Attack））となる。
【００６３】
なお、本実施形態では、アーベル群Ｇにおける演算を便宜上の積の形で表している。Ｇの選び方としては、例えば素数を法とする剰余体から導かれる乗法群や楕円曲線から決定される加法群など、様々なものを適用できる。
【００６４】
<<第２実施形態>>
上記の第１実施形態では、送信者および受信者が鍵情報を共有するまでの動作を説明した。本発明の第２実施形態では、送信者および受信者間で鍵の共有を行い、共有した鍵を用いて暗号通信を行なう場合を例にとり説明する。図６は本発明の第２実施形態の動作手順を説明するための図である。
【００６５】
１．送信側処理
送信者側装置１００において、入力部１０７は、送信メッセージｍを受信すると、これを記憶部１０８に記憶する（Ｓ１１０１）。次に、乱数生成部１０１は、ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成し、これを演算部１０２および鍵生成部１０３に渡す（Ｓ１１０２）。
【００６６】
演算部１０２は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、記憶部１０８に予め記憶されている受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを読み出す。そして、これらの情報を用いて、
【００６７】
【数３４】
2005354164.tif 000017
【００６８】
を計算し、その計算結果（ｕ，ｖ）を通信部１０５に渡す（Ｓ１１０３）。ここで、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００６９】
【数３５】
2005354164.tif 000018
【００７０】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。
【００７１】
また、鍵生成部１０３は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、所定の鍵生成関数Ｆを用いて、
【００７２】
【数３６】
2005354164.tif 000019
【００７３】
を送信者および受信者間で共有する鍵情報Ｋとして計算する。そして、この鍵情報Ｋを記憶部１０８に記憶すると共に、暗号化部１０６に渡す（Ｓ１１０４）。
【００７４】
暗号化部１０６は、鍵生成部１０３から鍵情報Ｋを受け取ると、記憶部１０８に記憶されているメッセージｍを読み出す。そして、鍵情報Ｋを用いたメッセージｍに対する暗号文Ｃ＝Ｅｋ（ｍ）を計算し、通信部１０５に渡す（Ｓ１１０５）。ここで、Ｅｋ（ｍ）は、メッセージｍを鍵情報Ｋを用いて共通鍵暗号により暗号化することを意味する。
【００７５】
さて、通信部１０５は、演算部１０２から計算結果（ｕ，ｖ）を受け取ると共に、暗号化部１０６から暗号文Ｃを受け取ると、これらを送信データ（ｕ，ｖ，Ｃ）として、通信回線３００を介して受信側装置２００に送信する（Ｓ１１０６）。
【００７６】
２．受信側処理
受信者側装置２００において、通信部２０１は、通信回線３００を介して送信者側装置１００より送信データ（ｕ，ｖ，Ｃ）を受け取ると、そのうちの暗号文Ｃを記憶部２０７に記憶すると共に、情報ｕ、ｖを演算部２０２および検査部２０３に渡す（Ｓ２１０１）。
【００７７】
演算部２０２は、通信部２０１より情報ｕ、ｖを受け取ると、記憶部２０７に予め記憶されている受信者の秘密情報ｓを読み出す。そして、これらの情報を用いて、
【００７８】
【数３７】
2005354164.tif 000020
【００７９】
を満足するｋ１ビットの乱数ｒ’１∈Ｇおよびｋ２ビットの乱数ｒ’２∈Ｇを計算する。そして、計算結果ｒ’１、ｒ’２を検査部２０３に渡す（Ｓ２１０２）。
【００８０】
また、検査部２０３は、演算部２０２から計算結果ｒ’１、ｒ’２を受け取ると、記憶部２０７に予め記憶されている受信者の公開情報ｇと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを読み出す。そして、これらの情報と通信部２０１より受け取った情報ｕ、ｖとを用いて、
【００８１】
【数３８】
2005354164.tif 000021
【００８２】
が成立するか否かを検査する（Ｓ２１０３）。成立しない場合は、送信データ（ｕ，ｖ，Ｃ）が不正なものと判断し、鍵情報の計算を拒否し、その旨を示すエラーメッセージなどを出力部２０５から出力する。一方、成立する場合、計算結果ｒ’１、ｒ’２を鍵生成部２０４に出力する。これを受けて、鍵生成部２０４は、前記所定の鍵生成関数Ｆを用いて、
【００８３】
【数３９】
2005354164.tif 000022
【００８４】
を送信者および受信者間で共有する鍵情報Ｋ’として計算する。そして、この鍵情報Ｋ’を記憶部２０７に記憶すると共に、復号化部２０６に渡す（Ｓ２１０４）。
【００８５】
復号化部２０６は、鍵生成部２０４から鍵情報Ｋ’を受け取ると、記憶部２０７に記憶されている暗号文Ｃを読み出す。そして、鍵情報Ｋ’を用いて暗号文Ｃに対する平文ｍ’＝Ｄｋ’（Ｃ）を計算し、出力部２０５から出力する（Ｓ２１０５）。ここで、Ｄｋ’（Ｃ）は、暗号文Ｃを鍵情報Ｋ’を用いて上記共通鍵暗号により復号化することを意味する。
【００８６】
以上、本発明の第２実施形態について説明した。本実施形態でも、上記の第１実施形態と同様の効果を奏する。したがって、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも安全な暗号通信を実現できる。
【００８７】
<<第３実施形態>>
次に、本発明の第３実施形態について説明する。本実施形態も上記の第２実施形態と同様に、送信者および受信者間で鍵の共有を行い、共有した鍵を用いて暗号通信を行なうものである。図７は本発明の第３実施形態の動作手順を説明するための図である。
【００８８】
１．送信側処理
送信者側装置１００において、入力部１０７は、送信メッセージｍを受信すると、これを記憶部１０８に記憶する（Ｓ１２０１）。次に、乱数生成部１０１は、ｋ１ビットの乱数ｒ１∈Ｇおよびｋ２ビットの乱数ｒ２∈Ｇを生成し、これを演算部１０２および鍵生成部１０３に渡す（Ｓ１２０２）。
【００８９】
演算部１０２は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、記憶部１０８に予め記憶されている受信者の公開情報ｇ、ｈと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２とを読み出す。そして、これらの情報を用いて、
【００９０】
【数４０】
2005354164.tif 000023
【００９１】
を計算し、その計算結果（ｕ，ｖ）を通信部１０５に渡す（Ｓ１２０３）。ここで、Ｇはアーベル群である。また、ｇ、ｈはＧの元であり、受信者の秘密情報ｓに対して、
【００９２】
【数４１】
2005354164.tif 000024
【００９３】
なる関係がある。また、Ｇにおける演算を便宜上の積の形で表している。さらに、ａ||ｂはａとｂの連接を意味する。
【００９４】
また、鍵生成部１０３は、乱数生成部１０１から乱数ｒ１、ｒ２を受け取ると、所定の鍵生成関数Ｆを用いて、
【００９５】
【数４２】
2005354164.tif 000025
【００９６】
を送信者および受信者間で共有する鍵情報Ｋとして計算する。そして、この鍵情報Ｋを記憶部１０８に記憶すると共に、暗号化部１０６に渡す（Ｓ１２０４）。
【００９７】
暗号化部１０６は、鍵生成部１０３から鍵情報Ｋを受け取ると、記憶部１０８に記憶されているメッセージｍと、送信者および受信者の両方に対して公開されたランダム関数Ｈ３とを読み出す。そして、鍵情報Ｋを用いたメッセージｍに対する暗号文Ｃ＝Ｅｋ（ｍ）を計算する。ここで、Ｅｋ（ｍ）は、メッセージｍを鍵情報Ｋを用いて共通鍵暗号により暗号化することを意味する。また、
【００９８】
【数４３】
2005354164.tif 000026
【００９９】
を計算し、計算結果ｗおよび暗号文Ｃを通信部１０５に渡す（Ｓ１２０５）。
【０１００】
さて、通信部１０５は、演算部１０２から計算結果（ｕ，ｖ）を受け取ると共に、暗号化部１０６から計算結果ｗ、暗号文Ｃを受け取ると、これらを送信データ（ｕ，ｖ，ｗ，Ｃ）として、通信回線３００を介して受信側装置２００に送信する（Ｓ１２０６）。
【０１０１】
２．受信側処理
受信者側装置２００において、通信部２０１は、通信回線３００を介して送信者側装置１００より送信データ（ｕ，ｖ，ｗ，Ｃ）を受け取ると、そのうちの暗号文Ｃを記憶部２０７に記憶すると共に、情報ｕ、ｖを演算部２０２に、そして、情報ｕ、ｗを検査部２０３に渡す（Ｓ２２０１）。
【０１０２】
演算部２０２は、通信部２０１より情報ｕ、ｖを受け取ると、記憶部２０７に予め記憶されている受信者の秘密情報ｓを読み出す。そして、これらの情報を用いて、
【０１０３】
【数４４】
2005354164.tif 000027
【０１０４】
を満足するｋ１ビットの乱数ｒ’１∈Ｇおよびｋ２ビットの乱数ｒ’２∈Ｇを計算する。そして、計算結果ｒ’１、ｒ’２を鍵生成部２０４および検査部２０３に渡す（Ｓ２２０２）。
【０１０５】
鍵生成部２０４は、演算部２０２から計算結果ｒ’１、ｒ’２を受け取ると、前記所定の鍵生成関数Ｆを用いて、
【０１０６】
【数４５】
2005354164.tif 000028
【０１０７】
を送信者および受信者間で共有する鍵情報Ｋ’として計算する。そして、この鍵情報Ｋ’を記憶部２０７に記憶すると共に、復号化部２０６に渡す（Ｓ２２０３）。
【０１０８】
復号化部２０６は、鍵生成部２０４から鍵情報Ｋ’を受け取ると、記憶部２０７に記憶されている暗号文Ｃを読み出す。そして、鍵情報Ｋ’を用いて暗号文Ｃに対する平文ｍ’＝Ｄｋ’（Ｃ）を計算し、検査部２０３に渡す（Ｓ２２０４）。ここで、Ｄｋ’（Ｃ）は、暗号文Ｃを鍵情報Ｋ’を用いて上記共通鍵暗号により復号化することを意味する。
【０１０９】
さて、検査部２０３は、演算部２０２から計算結果ｒ’１、ｒ’２を受け取ると共に、復号化部２０６から平文ｍ’を受け取ると、記憶部２０７に予め記憶されている受信者の公開情報ｇと、送信者および受信者の両方に対して公開されたランダム関数Ｈ１、Ｈ２、Ｈ３とを読み出す。そして、これらの情報と通信部２０１より受け取った情報ｕ、ｗとを用いて、
【０１１０】
【数４６】
2005354164.tif 000029
【０１１１】
が成立するか否かを検査する（Ｓ２２０５）。成立しない場合は、送信データ（ｕ，ｖ，ｗ，Ｃ）が不正なものと判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する。一方、成立する場合、平文ｍ’を復号化されたメッセージとして出力部２０５から出力する（Ｓ２２０６）。
【０１１２】
以上、本発明の第３実施形態について説明した。本実施形態でも、上記の第２実施形態と同様、攻撃者がランダムオラクルを選んで適応的選択暗号文攻撃を行った場合でも安全な暗号通信を実現できる。
【０１１３】
以上、本発明の各実施の形態について説明した。
【０１１４】
なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【０１１５】
例えば、上記の各実施形態において、受信者の公開情報ｇ、ｈおよび秘密情報ｓは、受信者側装置２００の鍵生成部２０４が予め生成して、記憶部２０７に記憶すると共に、公開情報ｇ、ｈを通信部２０１を介して送信者側装置１００に送信し、送信者側装置１００の記憶部１０８に記憶するようにしてもよい。
【０１１６】
また、上記の各実施形態において、ランダム関数Ｈ１、Ｈ２（第３実施形態の場合はさらにＨ３）と、乱数ｒ１、ｒ２のビット長に関する情報ｋ１、ｋ２と、鍵生成関数Ｆとは、送信者側装置１００の記憶部１０８および受信者側装置２００の記憶部２０７のそれぞれに予め記憶されているものとしてもよい。
【０１１７】
また、上記の各実施形態において、送信者側装置１００が受信者側装置２００の機能も有するものでもよい。同様に、受信者側装置２００が送信者側装置１００の機能も有するものでもよい。
【０１１８】
また、上記の各実施形態では、送信者と受信者とが各々の装置を利用して鍵の共有を行い、それから暗号通信を行うという一般的な通信システムを例にとり説明したが、本発明は、様々なシステムに適用可能である。例えば、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店であり、受信者側装置はパソコンなどの計算機となる。ユーザの商品等の注文書は、共通鍵暗号で暗号化されることが多い。この場合、注文書の暗復号に用いる共通鍵が本発明の方法により暗号化されて、受信者（小売店）側装置に送信される。また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信文(メール)は共通鍵暗号で暗号化されることが多い。この場合、送信文の暗復号に用いる共通鍵が本発明の方法により暗号化されて、受信者の計算機に送信される。その他にも、従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【０１１９】
また、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムだけではない。いずれかの計算を行なう装置は、ハードウエア化された演算装置であって、他の演算装置やＣＰＵとデータのやりとりを行うものでもよい。
【図面の簡単な説明】
【０１２０】
【図１】本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第１実施形態の動作手順を説明するための図である。
【図６】本発明の第２実施形態の動作手順を説明するための図である。
【図７】本発明の第３実施形態の動作手順を説明するための図である。
【符号の説明】
【０１２１】
１００…送信者側装置、１０１…乱数生成部、１０２…演算部、１０３…鍵生成部、１０４…出力部、１０５…通信部、１０６…暗号化部、１０７…入力部、１０８…記憶部、２００…受信者側装置、２０１…鍵生成部、２０２…演算部、２０３…検査部、２０４…鍵生成部、２０５…出力部、２０６…復号化部、２０７…記憶部、３００…通信回線、４０１…ＣＰＵ、４０２…メモリ、４０３…外部記憶装置、４０４…記憶媒体、４０５…読取装置、４０６…入力装置、４０７…出力装置、４０８…通信装置、４０９…バス
【図１】
2005354164.tif 000049
【図２】
2005354164.tif 000050
【図３】
2005354164.tif 000051
【図４】
2005354164.tif 000052
【図５】
2005354164.tif 000053
【図６】
2005354164.tif 000054
【図７】
2005354164.tif 000055