(57)【要約】【課題】標準計算機モデル上で選択暗号文攻撃に対して強秘匿であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を提供する。【解決手段】送信者側装置１００がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置２００が暗号文を受信してメッセージ文を復号化する。送信者側装置１００および受信者側装置２００間の暗号通信には、変形されたＤＨＫ（Diffie-Hellman Knowledge）問題が計算量的に困難であることの暗号学的仮定に基づいて、安全性が証明された公開鍵暗号を用いる。【選択図】図１
2006337867.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数１】
2006337867.tif 000061
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数２】
2006337867.tif 000062
なるｕ１，ｕ２∈Ｇをランダムに生成するステップと、
前記公開鍵および数２の計算結果を用いて、
【数３】
2006337867.tif 000063
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数４】
2006337867.tif 000064
を計算するステップと、
前記暗号文と、前記公開鍵と、数４の計算結果とを用いて、
【数５】
2006337867.tif 000065
を検査するステップと、
検証が成立した場合に、数４の計算結果を用いて、
【数６】
2006337867.tif 000066
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項２】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数７】
2006337867.tif 000067
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数８】
2006337867.tif 000068
なるｕ１，ｕ２∈Ｇをランダムに生成するステップと、
前記公開鍵および数８の計算結果を用いて、
【数９】
2006337867.tif 000069
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数１０】
2006337867.tif 000070
を計算するステップと、
前記暗号文と、前記公開鍵と、数１０の計算結果とを用いて、
【数１１】
2006337867.tif 000071
を検査するステップと、
検証が成立した場合に、数１０の計算結果を用いて、
【数１２】
2006337867.tif 000072
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項３】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数１３】
2006337867.tif 000073
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数１４】
2006337867.tif 000074
なるｕ１，ｕ２∈Ｇをランダムに生成するステップと、
前記公開鍵および数１４の計算結果を用いて、
【数１５】
2006337867.tif 000075
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数１６】
2006337867.tif 000076
および
【数１７】
2006337867.tif 000077
を計算するステップと、
前記暗号文と、前記公開鍵と、数１６および数１７の計算結果とを用いて、
【数１８】
2006337867.tif 000078
を検査するステップと、
検証が成立した場合に、数１６あるいは数１７の計算結果を用いて、
【数１９】
2006337867.tif 000079
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項４】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数２０】
2006337867.tif 000080
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成するステップと、
ｕ１，ｕ２を用いて、
【数２１】
2006337867.tif 000081
を計算するステップと、
数２１の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数２２】
2006337867.tif 000082
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数２３】
2006337867.tif 000083
を計算するステップと、
前記公開鍵と、数２３の計算結果とを用いて、
【数２４】
2006337867.tif 000084
を検査するステップと、
検証が成立した場合に、数２３の計算結果を用いて、
【数２５】
2006337867.tif 000085
を計算し、さらに、数２５の計算結果と、受信した暗号文とを用いて、
【数２６】
2006337867.tif 000086
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項５】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数２７】
2006337867.tif 000087
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成するステップと、
ｕ１，ｕ２を用いて、
【数２８】
2006337867.tif 000088
を計算するステップと、
数２８の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数２９】
2006337867.tif 000089
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数３０】
2006337867.tif 000090
を計算するステップと、
前記公開鍵と、数３０の計算結果とを用いて、
【数３１】
2006337867.tif 000091
を検査するステップと、
検証が成立した場合に、数３０の計算結果を用いて、
【数３２】
2006337867.tif 000092
を計算し、さらに、数３２の計算結果と、受信した暗号文とを用いて、
【数３３】
2006337867.tif 000093
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項６】
送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【数３４】
2006337867.tif 000094
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成するステップと、
ｕ１，ｕ２を用いて、
【数３５】
2006337867.tif 000095
を計算するステップと、
数３５の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数３６】
2006337867.tif 000096
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【数３７】
2006337867.tif 000097
および
【数３８】
2006337867.tif 000098
を計算するステップと、
数３７および数３８の計算結果を用いて、
【数３９】
2006337867.tif 000099
を検査するステップと、
検証が成立した場合に、数３７または数３８の計算結果を用いて、
【数４０】
2006337867.tif 000100
を計算し、さらに、数４０の計算結果と、受信した暗号文とを用いて、
【数４１】
2006337867.tif 000101
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行うこと
を特徴とする暗号通信方法。
【請求項７】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数４２】
2006337867.tif 000102
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数４３】
2006337867.tif 000103
なるｕ１，ｕ２∈Ｇをランダムに生成する手段と、
前記公開鍵および数４３の計算結果を用いて、
【数４４】
2006337867.tif 000104
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、さらに、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数４５】
2006337867.tif 000105
を計算する手段と、
前記暗号文と、前記公開鍵と、数４５の計算結果とを用いて、
【数４６】
2006337867.tif 000106
を検査する手段と、
検証が成立した場合に、数４５の計算結果を用いて、
【数４７】
2006337867.tif 000107
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項８】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数４８】
2006337867.tif 000108
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数４９】
2006337867.tif 000109
なるｕ１，ｕ２∈Ｇをランダムに生成する手段と、
前記公開鍵および数４９の計算結果を用いて、
【数５０】
2006337867.tif 000110
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、さらに、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数５１】
2006337867.tif 000111
を計算する手段と、
前記暗号文と、前記公開鍵と、数５１の計算結果とを用いて、
【数５２】
2006337867.tif 000112
を検査する手段と、
検証が成立した場合に、数５１の計算結果を用いて、
【数５３】
2006337867.tif 000113
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項９】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数５４】
2006337867.tif 000114
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【数５５】
2006337867.tif 000115
なるｕ１，ｕ２∈Ｇをランダムに生成する手段と、
前記公開鍵および数５５の計算結果を用いて、
【数５６】
2006337867.tif 000116
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、さらに、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数５７】
2006337867.tif 000117
および
【数５８】
2006337867.tif 000118
を計算する手段と、
前記暗号文と、前記公開鍵と、数５７および数５８の計算結果とを用いて、
【数５９】
2006337867.tif 000119
を検査する手段と、
検証が成立した場合に、数５７あるいは数５９の計算結果を用いて、
【数６０】
2006337867.tif 000120
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項１０】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数６１】
2006337867.tif 000121
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成する手段と、
ｕ１，ｕ２を用いて、
【数６２】
2006337867.tif 000122
を計算する手段と、
数６２の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数６３】
2006337867.tif 000123
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、さらに、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数６４】
2006337867.tif 000124
を計算する手段と、
前記公開鍵と、数６４の計算結果とを用いて、
【数６５】
2006337867.tif 000125
を検査する手段と、
検証が成立した場合に、数６４の計算結果を用いて、
【数６６】
2006337867.tif 000126
を計算し、さらに、数６６の計算結果と、受信した暗号文とを用いて、
【数６７】
2006337867.tif 000127
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項１１】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数６８】
2006337867.tif 000128
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成する手段と、
ｕ１，ｕ２を用いて、
【数６９】
2006337867.tif 000129
を計算する手段と、
数６９の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数７０】
2006337867.tif 000130
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、さらに、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数７１】
2006337867.tif 000131
を計算する手段と、
前記公開鍵と、数７１の計算結果とを用いて、
【数７２】
2006337867.tif 000132
を検査する手段と、
検証が成立した場合に、数７１の計算結果を用いて、
【数７３】
2006337867.tif 000133
を計算し、さらに、数７３の計算結果と、受信した暗号文とを用いて、
【数７４】
2006337867.tif 000134
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項１２】
メッセージ文Ｍの暗号文を作成して送信する送信者側装置と、前記暗号文を受信して前記メッセージ文を復号化する受信者側装置とを有する暗号通信送システムであって、
（１）前記受信者側装置は、
素数ｐ、ｑを生成する手段（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する手段と、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する手段と、
【数７５】
2006337867.tif 000135
を計算する手段と、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力する手段と、
（ｘ１，ｘ２）を秘密鍵として記憶する手段と、を有し、
（２）前記送信者側装置は、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成する手段と、
ｕ１，ｕ２を用いて、
【数７６】
2006337867.tif 000136
を計算する手段と、
数７６の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【数７７】
2006337867.tif 000137
を計算する手段（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信する手段と、を有し、
（３）前記受信者側装置は、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信する手段と、
受信した暗号文と、前記秘密鍵とを用いて、
【数７８】
2006337867.tif 000138
および
【数７９】
2006337867.tif 000139
を計算する手段と、
数７８および数７９の計算結果を用いて、
【数８０】
2006337867.tif 000140
を検査する手段と、
検証が成立した場合に、数７９または数８０の計算結果を用いて、
【数８１】
2006337867.tif 000141
を計算し、さらに、数８１の計算結果と、受信した暗号文とを用いて、
【数８２】
2006337867.tif 000142
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否する手段と、を有すること
を特徴とする暗号通信システム。
【請求項１３】
請求項７乃至１２のいずれか一項に記載の暗号通信システムで用いられる送信者側装置。
【請求項１４】
請求項７乃至１２のいずれか一項に記載の暗号通信システムで用いられる受信者側装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号通信技術に関し、特に、標準計算機モデル上で選択暗号文攻撃に対して安全な公開鍵暗号通信技術に関する。
【背景技術】
【０００２】
非特許文献１で述べられているように、現在、公開鍵暗号では、適応的選択暗号文攻撃に対して強秘匿（ＩＮＤ（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 : 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＞
【非特許文献５】M. Bellare and A. Palacio : Towards Plaintext Aware Public-Key Encryption without Random Oracles  [平成１７年５月１３日検索］  インターネット＜URL:http://www-cse.ucsd.edu/users/mihir/papers/pa.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
さて、本発明では、標準計算機モデル上で選択暗号文攻撃に対して強秘匿であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を対象とする。標準計算機モデル上で安全性を証明可能な公開鍵暗号を設計することは、ランダムオラクルモデル上で安全性を証明可能な公開鍵暗号を設計することよりも困難であると考えられている。これは、ランダムオラクルモデル上で安全性を証明可能な公開鍵暗号を設計するために便利な条件ＰＡ（Plaintext Awareness）が、上記の非特許文献１などで明確になっているためである。これに対して、上記の非特許文献５では、ＰＡに似せた標準計算機モデル上で安全性を証明可能な公開鍵暗号を設計するための条件が提案されている。しかし、非特許文献５では、ＩＮＤ-ＣＣＡ２の意味において安全であることが証明可能な公開鍵暗号が提案されていない。
【０００７】
本発明は、上記事情に鑑みてなされたものであり、本発明の目的は、標準計算機モデル上で選択暗号文攻撃に対して強秘匿であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために本発明の暗号通信方法では、上記の非特許文献５等により知られているＤＨＫ（Diffie-Hellman Knowledge）を暗号学的仮定として証明するのではなく、ＤＨＫを変形させた暗号学的仮定を用いる。ここで、ＤＨＫとは、簡単に言うと、「与えられたＡ＝ｇａに対して、Ｂ＝ｇｂ，Ｗ＝ｇａｂなる（Ｂ，Ｗ）を生成するには、ｂの値を知っている必要がある」ことを意味する（すなわち、ｂの値を知ることなく、（Ｂ，Ｗ）を効率良く計算することは難しい。）。これに対して、本発明で用いる変形ＤＨＫは、簡単に言うと、「与えられたＡ＝ｇａに対して、Ｂ＝ｂ・ｇｂ，Ｗ＝ｂ・ｇａｂなる（Ｂ，Ｗ）を生成するには、ｂの値を知っている必要がある」ことを意味する（すなわち、ｂの値を知ることなく、（Ｂ，Ｗ）を効率良く計算することは難しい。）。
【０００９】
例えば、本発明の第１の態様は、送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【００１０】
【数８３】
2006337867.tif 000003
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍ∈Ｇに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、
【００１１】
【数８４】
2006337867.tif 000004
なるｕ１，ｕ２∈Ｇをランダムに生成するステップと、
前記公開鍵および数８４の計算結果を用いて、
【００１２】
【数８５】
2006337867.tif 000005
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００１３】
【数８６】
2006337867.tif 000006
を計算するステップと、
前記暗号文と、前記公開鍵と、数８６の計算結果とを用いて、
【００１４】
【数８７】
2006337867.tif 000007
を検査するステップと、
検証が成立した場合に、数８６の計算結果を用いて、
【００１５】
【数８８】
2006337867.tif 000008
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【００１６】
ここで、「（３）前記受信者側装置」の処理は、次のように変形してもよい。すなわち、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００１７】
【数８９】
2006337867.tif 000009
を計算するステップと、
前記暗号文と、前記公開鍵と、数８９の計算結果とを用いて、
【００１８】
【数９０】
2006337867.tif 000010
を検査するステップと、
検証が成立した場合に、数８９の計算結果を用いて、
【００１９】
【数９１】
2006337867.tif 000011
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【００２０】
あるいは、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００２１】
【数９２】
2006337867.tif 000012
および
【００２２】
【数９３】
2006337867.tif 000013
を計算するステップと、
前記暗号文と、前記公開鍵と、数９２および数９３の計算結果とを用いて、
【００２３】
【数９４】
2006337867.tif 000014
を検査するステップと、
検証が成立した場合に、数９２あるいは数９３の計算結果を用いて、
【００２４】
【数９５】
2006337867.tif 000015
を計算し、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【００２５】
また、本発明の第２の態様は、送信者側装置がメッセージ文Ｍの暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記メッセージ文を復号化する暗号通信送方法であって、
（１）前記受信者側装置が、
素数ｐ、ｑを生成するステップ（但し、２ｑ＝ｐ−１）と、
位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成するステップと、
１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成するステップと、
【００２６】
【数９６】
2006337867.tif 000016
を計算するステップと、
（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力すると共に、（ｘ１，ｘ２）を秘密鍵として記憶するステップと、を行い、
（２）前記送信者側装置が、
前記メッセージ文Ｍに対して、前記送信者側装置より出力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を用いて、ｕ１，ｕ２∈Ｇをランダムに生成するステップと、
ｕ１，ｕ２を用いて、
【００２７】
【数９７】
2006337867.tif 000017
を計算するステップと、
数９７の計算結果と、前記公開鍵と、ｕ１，ｕ２とを用いて、
【００２８】
【数９８】
2006337867.tif 000018
を計算するステップ（但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表し、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。）と、
（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を暗号文として前記受信者側装置に送信するステップと、を行い、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００２９】
【数９９】
2006337867.tif 000019
を計算するステップと、
前記公開鍵と、数９９の計算結果とを用いて、
【００３０】
【数１００】
2006337867.tif 000020
を検査するステップと、
検証が成立した場合に、数９９の計算結果を用いて、
【００３１】
【数１０１】
2006337867.tif 000021
を計算し、さらに、数１０１の計算結果と、受信した暗号文とを用いて、
【００３２】
【数１０２】
2006337867.tif 000022
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【００３３】
ここで、「（３）前記受信者側装置」の処理は、次のように変形してもよい。すなわち、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００３４】
【数１０３】
2006337867.tif 000023
を計算するステップと、
前記公開鍵と、数１０３の計算結果とを用いて、
【００３５】
【数１０４】
2006337867.tif 000024
を検査するステップと、
検証が成立した場合に、数１０３の計算結果を用いて、
【００３６】
【数１０５】
2006337867.tif 000025
を計算し、さらに、数１０５の計算結果と、受信した暗号文とを用いて、
【００３７】
【数１０６】
2006337867.tif 000026
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【００３８】
あるいは、
（３）前記受信者側装置が、
前記送信者側装置が送信した暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信するステップと、
受信した暗号文と、前記秘密鍵とを用いて、
【００３９】
【数１０７】
2006337867.tif 000027
および
【００４０】
【数１０８】
2006337867.tif 000028
を計算するステップと、
数１０７および数１０８の計算結果を用いて、
【００４１】
【数１０９】
2006337867.tif 000029
を検査するステップと、
検証が成立した場合に、数１０７または数１０９の計算結果を用いて、
【００４２】
【数１１０】
2006337867.tif 000030
を計算し、さらに、数１１０の計算結果と、受信した暗号文とを用いて、
【００４３】
【数１１１】
2006337867.tif 000031
を計算し（但し、ＤＫ'（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。）、該計算結果をメッセージ文として出力し、検証が成立しなかった場合に、メッセージ文の出力を拒否するステップと、を行う。
【発明の効果】
【００４４】
本発明によれば、標準計算機モデル上で選択暗号文攻撃に対して強秘匿であることが証明可能な、公開鍵暗号をベースとする暗号通信技術を提供できる。
【発明を実施するための最良の形態】
【００４５】
以下に、本発明の実施の形態について説明する。
【００４６】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００４７】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。図示するように、公開鍵暗号通信システムは、暗号化処理を行なってメッセージの暗号文を作成する送信者側装置１００と、復号化処理を行なってメッセージを復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００４８】
図２は図１に示す送信者側装置１００の概略構成図である。図示するように、送信者側装置１００は、情報を入力する入力部１０１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算および送信者側装置１００の各部の制御を行う演算部１０２と、記憶部１０３と、通信回線３００を介して受信者側装置２００と通信を行なう通信部１０４と、情報を出力する出力部１０５と、を備えている。また、演算部１０２は、暗復号化処理を行う暗復号化部１０６と、乱数を生成する乱数生成部１０７と、を有する。
【００４９】
図３は図１に示す受信者側装置２００の概略構成図である。図示するように、情報を入力する入力部２０１と、論理演算、べき乗算、剰余演算、ランダム関数演算を含む各種演算を行う演算部２０２と、記憶部２０３と、通信回線３００を介して送信者側装置１００と通信を行なう通信部２０４と、復号結果を含む各種情報を出力する出力部２０５と、を備えている。また、演算部２０２は、暗復号化処理を行う暗復号化部２０６と、乱数を生成する乱数生成部２０７と、鍵生成部２０８と、を有する。
【００５０】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１０３、２０３に利用され、通信装置４０８が通信部１０４、２０４に利用され、入力装置４０６や読取装置４０５が入力部１０１、２０１に利用され、そして、出力装置４０７が出力部１０５、２０５に利用される。
【００５１】
この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００５２】
<<第１実施形態>>
本発明の第１実施形態について説明する。本実施形態では、送信者側装置１００および受信者側装置２００が、通信回線３００を介して共通の鍵情報を共有する場合を例にとり説明する。図５は本発明の第１実施形態の動作手順を説明するための図である。
【００５３】
１．鍵生成処理
１-１．受信者側装置２００において、演算部２０２は、鍵生成部２０８を用いて、素数ｐ、ｑを生成する（Ｓ２００１）。但し、２ｑ＝ｐ−１とする。
【００５４】
次に、演算部２０２は、乱数生成部２０７を用いて、位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する。また、１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する（Ｓ２００２）。ここで、乗法群Ｚｑ*は乗法群Ｚｑから０元を除いた群であり、乗法群Ｚｑはｑで割った余りの集合｛０，１，２，...，ｑ-１｝でもある。
【００５５】
次に、演算部２０２は、Ｓ１００２で生成したｇ，ｘ１，ｘ２を用いて、
【００５６】
【数１１２】
2006337867.tif 000032
を計算する（Ｓ２００３）。
【００５７】
それから、演算部２０２は、（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力部２０５から出力する。また、（ｘ１，ｘ２）を秘密鍵として記憶部２０３に記憶する（Ｓ２００４）。
【００５８】
１-２．送信者側装置１００において、演算部１０２は、入力部１０１に入力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を記憶部１０３に記憶する（Ｓ１００１）。
【００５９】
２．送信側処理
送信者側装置１００において、演算部１０２は、入力部１０１を介して送信者より、メッセージｘ∈Ｇを受け付けて、記憶部１０３に記憶する（Ｓ１００２）。
【００６０】
次に、演算部１０２は、乱数生成部１０７を用いて、
【００６１】
【数１１３】
2006337867.tif 000033
なるｕ１，ｕ２∈Ｇをランダムに生成する（Ｓ１００３）。
【００６２】
それから、演算部１０２は、このｕ１，ｕ２と、記憶部１０３に記憶されている公開鍵とを用いて、
【００６３】
【数１１４】
2006337867.tif 000034
を計算する。但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。そして、演算部１０２は、（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）をメッセージＭの暗号文として、通信部１０４を介して受信者側装置２００に送信する（Ｓ１００４）。
【００６４】
３．受信側処理
受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信すると、これを記憶部２０３に記憶する（Ｓ２００５）。
【００６５】
次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）および秘密鍵（ｘ１，ｘ２）を用いて、
【００６６】
【数１１５】
2006337867.tif 000035
を計算する（Ｓ２００６）。それから、演算部２００６は、このｕ′１，ｕ′２と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）および秘密鍵（ｘ１，ｘ２）とを用いて、
【００６７】
【数１１６】
2006337867.tif 000036
が成立するか否かを検査する（Ｓ２００７）。成立する場合は、
【００６８】
【数１１７】
2006337867.tif 000037
を計算し、これをメッセージ文として出力部２０５から出力する（Ｓ２００８）。一方、成立したい場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する（Ｓ２００９）。
【００６９】
以上、本発明の第１実施形態について説明した。
【００７０】
上記の非特許文献５において、標準計算機モデル上で安全性を証明可能な公開鍵暗号を設計するための条件が提案されている。これは、ランダムオラクルモデル上で安全性を証明可能な公開鍵暗号を設計するための条件の一つであるＰＡのアイデアを標準計算機モデル上に移行させたものである。非特許文献５では、ＤＨＫを暗号学的仮定、すなわち、ＤＨＫを解く効率的なアルゴリズムが存在しないことを仮定として、ＩＮＤ−ＣＣＡ１の意味で安全な公開鍵暗号が示されている。ここで、ＤＨＫとは、簡単に言うと、「与えられたＡ＝ｇａに対して、Ｂ＝ｇｂ，Ｗ＝ｇａｂなる（Ｂ，Ｗ）を生成するには、ｂの値を知っている必要がある」ことを意味する（すなわち、ｂの値を知ることなく、（Ｂ，Ｗ）を効率良く計算することは難しい。）。
【００７１】
本実施形態で用いた公開鍵暗号通信方法は、上述の非特許文献５に記載の方法と同様にして、変形ＤＨＫを暗号学的仮定として、ＩＮＤ−ＣＣＡ２の意味で安全であることを証明できる。ここで、変形ＤＨＫとは、簡単に言うと、「与えられたＡ＝ｇａに対して、Ｂ＝ｂ・ｇｂ，Ｗ＝ｂ・ｇａｂなる（Ｂ，Ｗ）を生成するには、ｂの値を知っている必要がある」ことを意味する（すなわち、ｂの値を知ることなく、（Ｂ，Ｗ）を効率良く計算することは難しい。）。
【００７２】
なお、本実施形態において、「３．受信側処理」は、次のように修正することも可能である。
【００７３】
すなわち、受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信すると、これを記憶部２０３に記憶する。次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）および秘密鍵（ｘ１，ｘ２）を用いて、
【００７４】
【数１１８】
2006337867.tif 000038
を計算する。それから、演算部２０２は、このｕ′１，ｕ′２と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）および秘密鍵（ｘ１，ｘ２）とを用いて、
【００７５】
【数１１９】
2006337867.tif 000039
が成立するか否かを検査する。成立する場合は、
【００７６】
【数１２０】
2006337867.tif 000040
を計算し、これをメッセージ文として出力部２０５から出力する。一方、成立しない場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する。
【００７７】
あるいは、上記の「３．受信側処理」を、次のように修正してもかまわない。
【００７８】
すなわち、受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）を受信すると、これを記憶部２０３に記憶する。次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）および秘密鍵（ｘ１，ｘ２）を用いて、
【００７９】
【数１２１】
2006337867.tif 000041
および
【００８０】
【数１２２】
2006337867.tif 000042
を計算する。それから、演算部２０２は、
【００８１】
【数１２３】
2006337867.tif 000043
が成立するか否かを検査する。成立する場合は、数１２１あるいは数１２２の計算結果を用いて、
【００８２】
【数１２４】
2006337867.tif 000044
を計算する。そして、計算結果Ｍ′をメッセージ文として出力部２０５から出力する。一方、成立しない場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する。
【００８３】
<<第２実施形態>>
次に、本発明の第２実施形態について説明する。本実施形態では、上記の第１実施形態に係る公開鍵暗号通信方法を、共有鍵暗号通信方法における鍵配送処理に適用した場合を例にとり説明する。図６は本発明の第２実施形態の動作手順を説明するための図である。
【００８４】
１．鍵生成処理
１-１．受信者側装置２００において、演算部２０２は、鍵生成部２０８を用いて、素数ｐ、ｑを生成する（Ｓ２１０１）。但し、２ｑ＝ｐ−１とする。
【００８５】
次に、演算部２０２は、乱数生成部２０７を用いて、位数ｑの元からなる乗法群Ｚｐ*の部分群Ｇの元ｇをランダムに生成する。また、１≦ｘ１，ｘ２＜ｑなる整数ｘ１，ｘ２をランダムに生成する（Ｓ２１０２）。ここで、乗法群Ｚｑ*は乗法群Ｚｑから０元を除いた群であり、乗法群Ｚｑはｑで割った余りの集合｛０，１，２，...，ｑ-１｝でもある。
【００８６】
次に、演算部２０２は、Ｓ１００２で生成したｇ，ｘ１，ｘ２を用いて、
【００８７】
【数１２５】
2006337867.tif 000045
を計算する（Ｓ２１０３）。
【００８８】
それから、演算部２０２は、（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を公開鍵として出力部２０５から出力する。また、（ｘ１，ｘ２）を秘密鍵として記憶部２０３に記憶する（Ｓ２１０４）。
【００８９】
１-２．送信者側装置１００において、演算部１０２は、入力部１０１に入力された公開鍵（ｐ，ｑ，ｇ，Ｘ１，Ｘ２）を記憶部１０３に記憶する（Ｓ１１０１）。
【００９０】
２．送信側処理
送信者側装置１００において、演算部１０２は、入力部１０１を介して送信者より、メッセージｘ∈Ｇを受け付けて、記憶部１０３に記憶する（Ｓ１１０２）。
【００９１】
次に、演算部１０２は、乱数生成部１０７を用いて、ｕ１，ｕ２∈Ｇをランダムに生成する（Ｓ１１０３）。また、このｕ１，ｕ２を用いて、
【００９２】
【数１２６】
2006337867.tif 000046
を計算する（Ｓ１１０４）。それから、演算部１０２は、このｕ１，ｕ２およびＫと、記憶部１０３に記憶されている公開鍵とを用いて、暗復号化部１０６により、
【００９３】
【数１２７】
2006337867.tif 000047
を計算する。但し、ξ（ｕ）（ｕ∈Ｇ）は、ｕの平方根でｑの値よりも小さい値を表す。また、ＥＫ（Ｍ）はメッセージ文Ｍを鍵Ｋを用いて共通鍵暗号により暗号化した暗号文を意味する。そして、演算部１０２は、（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）をメッセージＭの暗号文として、通信部１０４を介して受信者側装置２００に送信する（Ｓ１１０５）。
【００９４】
３．受信側処理
受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信すると、これを記憶部２０３に記憶する（Ｓ２１０５）。
【００９５】
次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）および秘密鍵（ｘ１，ｘ２）を用いて、
【００９６】
【数１２８】
2006337867.tif 000048
を計算する（Ｓ２１０６）。それから、演算部２００６は、このｕ′１，ｕ′２と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）および秘密鍵（ｘ１，ｘ２）とを用いて、
【００９７】
【数１２９】
2006337867.tif 000049
が成立するか否かを検査する（Ｓ２１０７）。成立する場合は、ｕ′１，ｕ′２を用いて、
【００９８】
【数１３０】
2006337867.tif 000050
を計算し（Ｓ２１０８）、さらに、このＫ′と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）とを用いて、暗復号化部２０６により、
【００９９】
【数１３１】
2006337867.tif 000051
を計算する。ここで、ＤＫ’（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。そして、この復号結果をメッセージ文として出力部２０５から出力する（Ｓ２１０９）。一方、成立したい場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する（Ｓ２１１０）。
【０１００】
以上、本発明の第２実施形態について説明した。本実施形態も上記の第１実施形態と同様の効果を有する。
【０１０１】
なお、本実施形態において、「３．受信側処理」は、次のように修正することも可能である。
【０１０２】
すなわち、受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信すると、これを記憶部２０３に記憶する。次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）および秘密鍵（ｘ１，ｘ２）を用いて、
【０１０３】
【数１３２】
2006337867.tif 000052
を計算する。それから、演算部２０２は、このｕ′１，ｕ′２と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）とを用いて、
【０１０４】
【数１３３】
2006337867.tif 000053
が成立するか否かを検査する。成立する場合は、数１３２の計算結果ｕ′１，ｕ′２を用いて、
【０１０５】
【数１３４】
2006337867.tif 000054
を計算し、この計算結果Ｋ′と、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）とを用いて、暗復号化部２０６により、
【０１０６】
【数１３５】
2006337867.tif 000055
を計算する。ここで、ＤＫ’（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。そして、この復号結果をメッセージ文として出力部２０５から出力する。一方、成立したい場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する。
【０１０７】
あるいは、上記の「３．受信側処理」を、次のように修正してもかまわない。
【０１０８】
すなわち、受信者側装置２００において、演算部２０２は、通信部２０４を介して送信者側装置１００より暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）を受信すると、これを記憶部２０３に記憶する。次に、演算部２０２は、記憶部２０３に記憶されている暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）および秘密鍵（ｘ１，ｘ２）を用いて、
【０１０９】
【数１３６】
2006337867.tif 000056
および
【０１１０】
【数１３７】
2006337867.tif 000057
を計算する。次に、演算部２０２は、数１３６および数１３７の計算結果を用いて、
【０１１１】
【数１３８】
2006337867.tif 000058
が成立するか否かを検査する。成立する場合は、数１３６あるいは数１３７の計算結果を用いて、
【０１１２】
【数１３９】
2006337867.tif 000059
を計算し、さらに、数１３９の計算結果と、受信した暗号文とを用いて、
【０１１３】
【数１４０】
2006337867.tif 000060
を計算する。ここで、ＤＫ’（Ｚ）は暗号文Ｚを鍵Ｋ′を用いて共通鍵暗号により復号化した結果を意味する。そして、この復号結果をメッセージ文として出力部２０５から出力する。一方、成立したい場合は、暗号文（Ｕ１，Ｕ２，Ｖ１，Ｖ２，Ｗ１，Ｗ２，Ｚ）が不正なものであると判断し、その旨を示すエラーメッセージなどを出力部２０５から出力する。
【０１１４】
なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。例えば、上記の各実施形態において、送信者側装置１００が受信者側装置２００の機能も有するものでもよい。同様に、受信者側装置２００が送信者側装置１００の機能も有するものでもよい。
【０１１５】
また、上記の各実施形態では、送信者と受信者とが各々の装置を利用して鍵の共有を行い、それから暗号通信を行うという一般的な通信システムを例にとり説明したが、本発明は、様々なシステムに適用可能である。例えば、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店であり、受信者側装置はパソコンなどの計算機となる。ユーザの商品等の注文書は、共通鍵暗号で暗号化されることが多い。この場合、注文書の暗復号に用いる共通鍵（メッセージ文ｘに相当）が本発明の方法により暗号化されて、受信者（小売店）側装置に送信される。また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信文(メール)は共通鍵暗号で暗号化されることが多い。この場合、送信文の暗復号に用いる共通鍵（メッセージ文ｘに相当）が本発明の方法により暗号化されて、受信者の計算機に送信される。その他にも、従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【０１１６】
また、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムだけではない。いずれかの計算を行なう装置は、ハードウエア化された演算装置であって、他の演算装置やＣＰＵとデータのやりとりを行うものでもよい。
【図面の簡単な説明】
【０１１７】
【図１】本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第１実施形態の動作手順を説明するための図である。
【図６】本発明の第２実施形態の動作手順を説明するための図である。
【符号の説明】
【０１１８】
１００…送信者側装置、１０１…入力部、１０２…演算部、１０３…記憶部、１０４…通信部、１０５…出力部、１０６…暗復号化部、１０７…乱数生成部、２００…受信者側装置、２０１…入力部、２０２…演算部、２０３…記憶部、２０４…通信部、２０５…出力部、２０６…暗復号化部、３００…通信回線
【図１】
2006337867.tif 000143
【図２】
2006337867.tif 000144
【図３】
2006337867.tif 000145
【図４】
2006337867.tif 000146
【図５】
2006337867.tif 000147
【図６】
2006337867.tif 000148