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