(57)【特許請求の範囲】
【請求項１】
送信者側装置が，受信者の公開鍵を用いて送信データを暗号化し，受信者側装置へ送信する公開鍵暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数１】
0004284867.tif 000077
を前記受信者の秘密鍵とし，
【数２】
0004284867.tif 000078
を前記受信者の公開鍵（但し，群Gは群G'部分群とし，X1，X2は正整数からなる有限集合で，
【数３】
0004284867.tif 000079
を満たすものとする。また，Mは平文空間とする)とした場合に，
（１）前記送信者側装置は，平文m（m∈M）に対して，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数４】
0004284867.tif 000080
を計算し（但し，α＝α1||α2），計算結果(u1,u2,e,v)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，該暗号文(u1,u2,e,v)から，
【数５】
0004284867.tif 000081
なる α'1，α'2，m'（α'1∈X1，α'2∈Ｘ2，m'∈M）を計算し，
【数６】
0004284867.tif 000082
が成立すれば， m'を復号化結果とし（但し，α'＝α'1||α'2），成立しなければ該暗号文(u1,u2,e,v)を拒否する旨を復号化結果として出力する
ことを特徴とする公開鍵暗号通信方法。
【請求項２】
送信者側装置が，受信者の公開鍵を用いて送信データを暗号化し，受信者側装置へ送信する公開鍵暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数７】
0004284867.tif 000083
を前記受信者の秘密鍵とし，
【数８】
0004284867.tif 000084
を前記受信者の公開鍵とした場合に，
（１）前記送信者側装置は，平文m（|m|=k3，但し|x|はｘの桁数を表す）に対して，乱数α=α1||α2（|α1|=k1,|α2|=k2）を作成し，
【数９】
0004284867.tif 000085
を計算し，さらに乱数 r∈Zqを選び，
【数１０】
0004284867.tif 000086
を計算し，計算結果(u1,u2,e,v)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，該暗号文(u1,u2,e,v)から，
【数１１】
0004284867.tif 000087
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，|m'|=k3）を計算し，
【数１２】
0004284867.tif 000088
が成立すれば， m' を復号化結果とし（但し，α'＝α'1||α'2），成立しなければ該暗号文(u1,u2,e,v)を拒否する旨を復号化結果として出力する
ことを特徴とする公開鍵暗号通信方法。
【請求項３】
請求項２に記載の公開鍵暗号通信方法において，
該送信者側装置は該暗号文を作成するに当たり，予め，乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【数１３】
0004284867.tif 000089
を計算し，保存しておく
ことを特徴とする公開鍵暗号通信方法。
【請求項４】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数１４】
0004284867.tif 000090
を前記受信者の秘密鍵とし，
【数１５】
0004284867.tif 000091
を前記受信者の公開鍵（但し，群Gは群G'の部分群とし， X1，X2は正整数からなる有限集合で，
【数１６】
0004284867.tif 000092
を満たすものとする。また，Mは鍵空間とする)とした場合に，
（１）前記送信者側装置は，鍵データK（K∈M）に対して，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数１７】
0004284867.tif 000093
を計算し（但し，α＝α1||α2），さらに，送信データmについて，
【数１８】
0004284867.tif 000094
を計算し，計算結果(u1, u2, e, v, C)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，該暗号文(u1,u2,e,v,C)から，
【数１９】
0004284867.tif 000095
なるα'1，α'2，K'（α'1∈X1，α'2∈Ｘ2，K'∈M）を計算し，
【数２０】
0004284867.tif 000096
が成立すれば（但し，α'＝α'1||α'2），
【数２１】
0004284867.tif 000097
を計算することにより，前記暗号文(u1,u2,e,v,C)の復号化結果を出力し，成立しなければ該暗号文(u1,u2,e,v,C)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項５】
請求項４に記載の暗号通信方法において，
該送信者側装置は，
【数２２】
0004284867.tif 000098
を計算（但し，ｆはｋビットの値を出力する公開された関数）し，
該受信者側装置は，
【数２３】
0004284867.tif 000099
が成立することを検査し（但し，[x]kはxの上位kビットを表す），検査をパスした場合に
【数２４】
0004284867.tif 000100
を計算し，ｍを復号化結果（但し，[x]-k は x の上位kビットを除いたビット列を表す）として出力する
ことを特徴とする公開鍵暗号方法。
【請求項６】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数２５】
0004284867.tif 000101
を前記受信者の秘密鍵とし，
【数２６】
0004284867.tif 000102
を前記受信者の公開鍵とした場合に，
前記送信者側装置は鍵データK（|K|=k3，但し|x|はｘの桁数を表す）に対して，乱数α=α1||α2（|α1|=k1,|α2|=k2）を作成し，
【数２７】
0004284867.tif 000103
を計算し，さらに乱数 r∈Zqを選び，
【数２８】
0004284867.tif 000104
を計算し，さらに，送信データについて，
【数２９】
0004284867.tif 000105
を計算し，計算結果(u1,u2,e,v,C)を暗号文として前記受信者側装置に送信し，
前記受信者側装置は，該秘密鍵を用いて，該暗号文(u1,u2,e,v,C)から，
【数３０】
0004284867.tif 000106
なる α'1，α'2，K'（|α'1|=k1，|α'2|=k2，|K'|=k3）を計算し，
【数３１】
0004284867.tif 000107
が成立すれば（但し，α'＝α'1||α'2），
【数３２】
0004284867.tif 000108
を計算することにより，前記暗号文(u1,u2,e,v,C)の復号化結果を出力し，成立しなければ該暗号文(u1,u2,e,v,C)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項７】
請求項６に記載の暗号通信方法において，
該送信者側装置は，
【数３３】
0004284867.tif 000109
を計算（但し，ｆはｋビットの値を出力する公開された関数）し，
該受信者側装置は，
【数３４】
0004284867.tif 000110
が成立することを検査し（但し，[x]kはxの上位kビットを表す），検査をパスした場合に
【数３５】
0004284867.tif 000111
を計算し，ｍを復号化結果（但し，[x]-k は x の上位kビットを除いたビット列を表す）として出力する
ことを特徴とする暗号通信方法。
【請求項８】
請求項６または７に記載の暗号通信方法において，
該送信者側装置は該暗号文を作成するに当たり，予め，乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【数３６】
0004284867.tif 000112
を計算し，保存しておく
ことを特徴とする暗号通信方法。
【請求項９】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数３７】
0004284867.tif 000113
を前記受信者の秘密鍵とし，
【数３８】
0004284867.tif 000114
を前記受信者の公開鍵（但し，群Gは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【数３９】
0004284867.tif 000115
を満たすものとする）とした場合に，
（１）前記送信者側装置は，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数４０】
0004284867.tif 000116
を計算し（但し，α＝α1||α2），さらに，送信データmについて，
【数４１】
0004284867.tif 000117
を計算し，計算結果(u1,u2,v,C)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，
【数４２】
0004284867.tif 000118
を計算し，さらに該暗号文(u1,u2,v,C)から，
【数４３】
0004284867.tif 000119
なるα'1，α'2（α'1∈X1，α'2∈Ｘ2）を計算し，
【数４４】
0004284867.tif 000120
が成立すれば（但し，α'＝α'1||α'2），m'を復号化結果として出力し，成立しなければ該暗号文(u1,u2,v,C)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１０】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数４５】
0004284867.tif 000121
を前記受信者の秘密鍵とし，
【数４６】
0004284867.tif 000122
を前記受信者の公開鍵とした場合に，
（１）前記送信者側装置は，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を作成し，
さらに乱数 r∈Zqを選び，
【数４７】
0004284867.tif 000123
を計算し，さらに，送信データmについて，
【数４８】
0004284867.tif 000124
を計算し（但し，Ｅは（対称型）暗号化関数），計算結果(u1,u2,v,C)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，
【数４９】
0004284867.tif 000125
を計算し，さらに該暗号文(u1,u2,v,C)から，
【数５０】
0004284867.tif 000126
なる α'1，α'2（|α'1|=k1，|α'2|=k2）を計算し，
【数５１】
0004284867.tif 000127
が成立すれば（但し，α'＝α'1||α'2），m'を復号化結果として出力し，成立しなければ該暗号文(u1,u2,v,C)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１１】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数５２】
0004284867.tif 000128
を前記受信者の秘密鍵とし，
【数５３】
0004284867.tif 000129
を前記受信者の公開鍵（但し，群Gは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【数５４】
0004284867.tif 000130
を満たすものとする。Mは平文空間）とした場合に，
（１）前記送信者側装置は，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数５５】
0004284867.tif 000131
を計算し（但し，α＝α1||α2），
【数５６】
0004284867.tif 000132
を計算し（但し，ｍは送信データ， Epkは，非対称型暗号化関数），計算結果(u1,u2,e,v)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，該秘密鍵を用いて，該暗号文(u1,u2,e,v)から，
【数５７】
0004284867.tif 000133
なるα'1，α'2，ｍ'（α'1∈X1，α'2∈Ｘ2，m'∈Ｍ）を計算し，
【数５８】
0004284867.tif 000134
が成立すれば（但し，
【数５９】
0004284867.tif 000135
とする）m'を復号化結果とし，成立しなければ該暗号文(u1,u2,e,v)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１２】
送信者側装置は，受信者側装置に対して暗号化されたデータを送信する暗号通信方法であって，
前記送信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，乱数生成手段と，通信手段と，を備え，
前記受信者側装置は，演算手段と，べき乗算手段と，剰余演算手段と，メモリ手段と，通信手段と，を備え，
【数６０】
0004284867.tif 000136
を前記受信者の秘密鍵とし，
【数６１】
0004284867.tif 000137
を前記受信者の公開鍵とした場合に，
（１）送信者側装置は，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を作成し，さらに乱数 r∈Zqを選び，
【数６２】
0004284867.tif 000138
を計算し，さらに，送信データm（正整数）について，
【数６３】
0004284867.tif 000139
を計算し，計算結果(u1,u2,e,v)を暗号文として前記受信者側装置に送信し，
（２）前記受信者側装置は，前記受信者の該秘密鍵を用いて，該暗号文(u1,u2,e,v)から，
【数６４】
0004284867.tif 000140
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，m'は正整数）を計算し，
【数６５】
0004284867.tif 000141
が成立すれば（但し，
【数６６】
0004284867.tif 000142
とする），m'を復号化結果として出力し，成立しなければ該暗号文(u1,u2,e,v)を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１３】
請求項１１または１２に記載の暗号通信方法において，
前記受信者側装置は，さらに，鍵生成手段を備え，
前記受信者側装置は，前記公開鍵を生成し，公開する
ことを特徴とする暗号通信方法。
【請求項１４】
請求項１１に記載の暗号通信方法において，
該送信者側装置は該暗号文を作成するに当たり，予め，乱数α1，α2（α1∈X1,α2∈X2），r∈Zqを選び，u1,u2,v を計算し，保存しておく
ことを特徴とする暗号通信方法。
【請求項１５】
請求項１２に記載の暗号通信方法において，
該送信者側装置は該暗号文を作成するに当たり，予め乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，u1,u2,v を計算し，保存しておく
ことを特徴とする暗号通信方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，公開鍵暗号方法及び公開鍵暗号を用いた暗号通信に関する。
【０００２】
【従来の技術】
現在まで，様々な公開鍵暗号方式が提案されている。なかでも，
文献1「R. L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public-key cryptosystems, Commun. of the ACM, Vol.21, No.2, pp.120-126, 1978.」
に掲載されている方法が最も有名であり，最も実用化されている公開鍵暗号でる。その他には，
文献2「V. S. Miller: Use of Elliptic Curves in Cryptography, Proc. of Crypto'85, LNCS218, Springer-Verlag, pp.417-426 (1985)」，
文献3「N. Koblitz: Elliptic Curve Cryptosystems, Math. Comp., 48, 177, pp.203-209 (1987)」
等に記載の楕円曲線を用いた方法が効率的な公開鍵暗号として知られている。
【０００３】
安全性について証明可能な方法として，まず，選択平文攻撃を対象としたものは，
文献4「M. O. Rabin: Digital Signatures and Public-Key Encryptions as Intractable as Factorization, MIT, Technical Report, MIT/LCS/TR-212 (1979)」
に記載されている暗号方法，
文献5「T. ElGamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. On Information Theory, IT-31, 4, pp.469-472(1985)」
に記載されている暗号方法，
文献6「S. Goldwasser and S. Micali: Probabilistic Encryption, JCSS, 28, 2, pp.270-299 (1984) 」に記載されている暗号方法，
文献7「M. Blum and S. Goldwasser: An Efficient probabilistic public-key encryption scheme which hides all partial information, Proc. of Crypto'84, LNCS196, Springer-Verlag, pp.289-299 (1985)」
に記載されている暗号方法，
文献8「S. Goldwasser and M. Bellare: Lecture Notes on Cryptography, http:/www-cse.ucsd.edu/users/ mihir/ (1997)」
に記載されている暗号方法，
文献9「T. Okamoto and S. Uchiyama. A New Public-Key Cryptosystem as Secure as Factoring, Proc. of Eurocrypt'98, LNCS1403, Springer Verlag, pp.308-318 (1998)」
に記載されている暗号方法，
などが知られている。
【０００４】
また，選択暗号文攻撃に対して安全性証明可能な方法としては，
文献10「D. Dolve, C. Dwork and M. Naor.: Non-malleable cryptography, In 23rd Annual ACM Symposium on Theory of Computing, pp.542-552 (1991)」
に記載されている暗号方法，
文献11「M. Naor and M. Yung.: Public-key cryptosystems provably secure against chosen ciphertext attacks, Proc. of STOC, ACM Press, pp.427-437 (1990)」
に記載されている暗号方法，
文献12「M. Bellare and P. Rogaway,. Optimal Asymmetric Encryption  How to Encrypt with RSA, Proc. of Eurocrypt'94, LNCS950, Springer Verlag, pp.92-111 (1994)」
に記載されている暗号方法，
文献13「R. Cramer and V. Shoup: A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack, Proc. of Crypto98, LNCS1462, Springer-Verlag, pp.13-25 (1998)」
に記載されている暗号方法，などが知られている。また，
文献14「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)」
では，IND-CCA2（適応的選択暗号文攻撃に対して“強秘匿”であること）とNM-CCA2（適応的選択暗号文攻撃に対して“頑強”であること）の等価性が示され，現在，この条件を満たす公開鍵暗号が最も安全であると考えられている。
【０００５】
【発明が解決しようとする課題】
文献12に記載されている公開鍵暗号方法は，実用的ではあるが，理想的ランダム関数の存在を前提として安全性の証明が行われている。理想的ランダム関数を実システムにおいて構築することは不可能なため，文献12の方法を実システムに適用する場合には，理想的ランダム関数の部分は実用的ハッシュ関数に置き換えられる。このため，実システムでは安全性の証明ができない。
【０００６】
文献13では，理想的ランダム関数の代わりに汎用一方向性ハッシュ関数の存在を前提としてIND-CCA2であることが証明できる公開鍵暗号方法を提供している。汎用一方向性ハッシュ関数は（暗号学的仮定の下で）実際に構築可能なので，文献13に記載されている方法は標準モデル上で安全性が証明できる方法である。しかし，実システムに適用する場合，効率性を高める目的で，SHA-1などの実用的なハッシュ関数を汎用的ハッシュ関数と仮定して用いるため，安全性証明可能の条件に強い仮定が必要になる。また，文献13では，汎用的一方向性ハッシュ関数の存在を前提としない公開鍵暗号方法も提案されているが，汎用的一方向性ハッシュ関数の存在を前提とする方法に比べて効率性が悪くなる。
【０００７】
本発明の主たる目的は，標準モデル（理想的関数の存在等を仮定しない現実の計算機モデル）で，最も強力な攻撃方法である適応的選択暗号文攻撃に対して安全性の証明が可能であり（IND-CCA2），かつ，実用的な公開鍵暗号方法を提供することである。
【０００８】
本発明の他の目的は，Diffe-Hellman 決定問題の困難性のみを仮定し，実システムに適用した場合においても，安全性の証明が可能な実用的公開鍵暗号方法を提供することである。
【０００９】
また，本発明の他の目的は，本発明に依る公開鍵暗号方法を用いた暗号通信方法，さらには，これらの方法を実行するプログラム，装置またはシステムを提供することである。
【００１０】
【課題を解決するための手段】
上記目的を達成するための手段として，適応的選択暗号文攻撃に対しての安全性を確保するため，不正な暗号文が（シミュレートされた）復号化オラクルに入力された場合には拒否されるように，平文と乱数を組み合わせて暗号文を作成する。復号化オラクルが与えられた環境とは，ターゲットとなる暗号文以外の任意の暗号文に対して，その復号化結果を無条件に得られる環境を指す。  具体的な実現方法の１つとしては，
[鍵生成]
【００１１】
【数６９】
0004284867.tif 000002
【００１２】
なる秘密鍵を作成し，さらに，
【００１３】
【数７０】
0004284867.tif 000003
【００１４】
なる公開鍵を作成する。
[暗号化]
送信者は，平文m（|m|=k3，但し|x|はｘの桁数を表す）に対して，乱数α=α1||α2（|α1|=k1,|α2|=k2）を作成し，
【００１５】
【数７１】
0004284867.tif 000004
【００１６】
を計算する。さらに，乱数 r∈Zqを選び，
【００１７】
【数７２】
0004284867.tif 000005
【００１８】
を計算し，(u1,u2,e,v)を暗号文として前記受信者に送信する。
[復号化]
受信者は，自身の秘密鍵を用いて，暗号文から，
【００１９】
【数７３】
0004284867.tif 000006
【００２０】
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，|m'|=k3）を計算し，
【００２１】
【数７４】
0004284867.tif 000007
【００２２】
が成立すればm'を復号化結果として出力し（但し，α'＝α'1||α'2），成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【００２３】
【発明の実施の形態】
暗号化装置，復号化装置が新規，図４が無い，図が少ない
以下，図面を用いて，本発明の実施例について説明する。
【００２４】
図１は，本発明の実施例のシステム構成を示す図である。このシステムは，送信者側装置100と受信者側装置200から構成されている。さらに，送信者側装置100と受信者側装置200は通信回線300で接続されている。
【００２５】
図２は，実施例における送信者側装置100の内部構成を示す。送信者側装置100は，乱数生成手段101，べき乗算手段102，演算手段103，剰余演算手段104，メモリ105，通信装置106，入力装置107，暗号化装置108を備えている。暗号化対象となる平文mは，入力装置107を用いて入力するか，送信者側装置100上で作成するか，または，通信装置106あるいは図示していない記憶媒体を介して取り込む。
【００２６】
図３は，実施例における受信者側装置200の内部構成を示す。受信者側装置200は，鍵生成手段201，べき乗算手段202，剰余演算手段203，演算手段204，メモリ205，通信装置206，復号化装置108，を備えている。このほか，図示していないが，復号化結果を，表示，音などの手段により当該装置の使用者（受信者）に示すための出力装置を備える。
【００２７】
送信者側装置100，受信者側装置200は，いずれもCPUとメモリとを備えた計算機を用いて所定のプログラムを実行させることにより構成することができる。乱数生成手段101，鍵生成手段201，べき乗算手段202，剰余演算手段203はいずれも専用のハードウェアを用いて構成しても良いし，演算手段上(CPU)上で動作するプログラムとして構成しても良い。各プログラムは，可搬型記憶媒体や通信回線上の通信媒体といった計算機が読みとり可能な媒体上に具現化され，これらの媒体を介して計算機のメモリに格納される。
【００２８】
図４は，実施例２の概要を示す図である。
【００２９】
図５は，実施例４の概要を示す図である。
【００３０】
図６は，実施例６の概要を示す図である。
（実施例１）
本実施例は，公開鍵暗号方法について説明する。
【００３１】
図１は，本実施例のシステム構成を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【００３２】
【数７５】
0004284867.tif 000008
【００３３】
なる秘密情報を作成し，
【００３４】
【数７６】
0004284867.tif 000009
【００３５】
なる公開情報を作成し（但し，群Ｇは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【００３６】
【数７７】
0004284867.tif 000010
【００３７】
を満たすものとする。また，Mは平文空間とする)，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，平文m（m∈M）に対して，乱数生成手段101を用いて，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【００３８】
【数７８】
0004284867.tif 000011
【００３９】
を計算する（但し，α＝α1||α2）。さらに，送信者側装置100は，送信者Ａの操作により，(u1,u2,e,v)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
（２）受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【００４０】
【数７９】
0004284867.tif 000012
【００４１】
なる α'1，α'2，m'（α'1∈X1，α'2∈Ｘ2，m'∈M）を計算し，
【００４２】
【数８０】
0004284867.tif 000013
【００４３】
が成立すればm'を復号化結果として出力し（但し，α'＝α'1||α'2），成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【００４４】
本実施例による方法では，GにおけるDiffie-Hellman 決定問題の困難性を前提として，適応的選択暗号文攻撃に対して強秘匿であることを示すことができる。GにおけるDiffie-Hellman 決定問題とは，「g1,g2∈Gに対して，
【００４５】
【数８１】
0004284867.tif 000014
【００４６】
のいずれかの集合に属するシーケンスδが与えられたとき，δがいずれに属するかを言い当てる問題」である。Diffie-Hellman 決定問題を1/2よりも良い確率で解くことが難しいとき，Diffie-Hellman 決定問題は困難であると言う（Diffie-Hellman 決定問題については，文献13等に述べられている）。
安全性の証明方法の手順としては，本実施例の方法を破るアルゴリズムが存在すれば，そのアルゴリズムを利用して，（具体的には，文献12で述べられている方法と同様の方法にて），Diffie-Hellman 決定問題を解くアルゴリズムを構築することができることを示す。
また，Diffie-Hellman 決定問題を解くアルゴリズムが存在したとしても，本実施例の方法を破るアルゴリズムは見つかっていないため，本実施例の方法を破る事は少なくともDiffie-Hellman 決定問題を解く以上に困難である。
【００４７】
さらに，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【００４８】
【数８２】
0004284867.tif 000015
【００４９】
を前もって計算して保存しておくことが可能である。これにより，暗号化処理の負担を大幅に減らし処理時間を短縮することが可能になる。
（実施例２）
本実施例は，実施例１における公開鍵暗号方法の実現方法の１つについて述べる。
【００５０】
図１は，本実施例のシステム構成を示す。図４は本実施例の概要を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【００５１】
【数８３】
0004284867.tif 000016
【００５２】
なる秘密情報を作成し，
【００５３】
【数８４】
0004284867.tif 000017
【００５４】
なる公開情報を作成し，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，平文m（|m|=k3，但し|x|はｘの桁数を表す）に対して，乱数生成手段101を用いて，乱数α=α1||α2（|α1|=k1,|α2|=k2）を選び，
【００５５】
【数８５】
0004284867.tif 000018
【００５６】
を計算し，さらに，乱数生成手段101を用いて，乱数 r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【００５７】
【数８６】
0004284867.tif 000019
【００５８】
を計算する。さらに，送信者側装置100は，送信者Ａの操作により，(u1,u2,e,v)を暗号文として，通信装置106を用いて通信回線300を介して受信者Ｂの受信者側装置200に送信する。
【００５９】
（２）  受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【００６０】
【数８７】
0004284867.tif 000020
【００６１】
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，|m'|=k3）を計算し，
【００６２】
【数８８】
0004284867.tif 000021
【００６３】
が成立すればm' を復号結果として出力し（但し，α'＝α'1||α'2），成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【００６４】
本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【００６５】
【数８９】
0004284867.tif 000022
【００６６】
を前もって計算して保存しておくことで，暗号化処理負担を大幅に減少させることが可能である。
（実施例３）
本実施例は，共通鍵暗号（対称型暗号）を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号化し、暗号化鍵を実施例１で述べた公開鍵暗号により暗号化して鍵配送する場合について説明する。
【００６７】
図１は，本実施例のシステム構成を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【００６８】
【数９０】
0004284867.tif 000023
【００６９】
なる秘密情報を作成し，
【００７０】
【数９１】
0004284867.tif 000024
【００７１】
なる公開情報を作成し（但し，群Ｇは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【００７２】
【数９２】
0004284867.tif 000025
【００７３】
を満たすものとする。また，Mは鍵空間とする)，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，鍵データK（K∈M）に対して，乱数生成手段101を用いて，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【００７４】
【数９３】
0004284867.tif 000026
【００７５】
を計算し（但し，α＝α1||α2），送信データmの暗号文Cを（対称型）暗号化関数Eとその鍵データＫを用いて，
【００７６】
【数９４】
0004284867.tif 000027
【００７７】
にて作成する。さらに，送信者側装置100は，送信者Ａの操作により，(u1,u2,e,v,C)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
（２）受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【００７８】
【数９５】
0004284867.tif 000028
【００７９】
なる α'1，α'2，K'（α'1∈X1，α'2∈Ｘ2，K'∈M）を計算し，
【００８０】
【数９６】
0004284867.tif 000029
【００８１】
が成立すれば（但し，α'＝α'1||α'2），
【００８２】
【数９７】
0004284867.tif 000030
【００８３】
にて復号化を行い，復号化結果を出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【００８４】
暗号文Cの別なる作成方法としては，該送信者は，暗号文Cを（対称型）暗号化関数Eとその鍵データＫを用いて，
【００８５】
【数９８】
0004284867.tif 000031
【００８６】
にて作成し，該受信者は，
【００８７】
【数９９】
0004284867.tif 000032
【００８８】
が成立することを検査し（但し，[x]kはxの上位k桁を表す。），検査をパスした場合に
【００８９】
【数１００】
0004284867.tif 000033
【００９０】
により，復号化を行う。但し，[x]-kはxの上位k桁を除いた整数列を表す。
【００９１】
さらに，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【００９２】
【数１０１】
0004284867.tif 000034
【００９３】
を前もって計算して保存しておくことが可能である。これにより，暗号化処理の負担を大幅に減らし処理時間を短縮することが可能になる。
（実施例４）
本実施例は，共通鍵暗号（対称型暗号）を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号化し、暗号化鍵を実施例２で述べた公開鍵暗号により暗号化して鍵配送する場合について説明する。
【００９４】
図１は，本実施例のシステム構成を示す。また，図５は，本実施例の概要を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【００９５】
【数１０２】
0004284867.tif 000035
【００９６】
なる秘密情報を作成し，
【００９７】
【数１０３】
0004284867.tif 000036
【００９８】
なる公開情報を作成し，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，鍵データK（|K|=k3，但し|x|はｘの桁数を表す。）に対して，乱数生成手段101を用いて，乱数α=α1||α2（|α1|=k1,|α2|=k2）を選び，
【００９９】
【数１０４】
0004284867.tif 000037
【０１００】
を計算し，さらに，乱数生成手段101を用いて，乱数 r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【０１０１】
【数１０５】
0004284867.tif 000038
【０１０２】
を計算する。さらに，送信者側装置100は，送信者Ａの操作により，送信データmの暗号文Cを（対称型）暗号化関数Eとその鍵データＫを用いて，
【０１０３】
【数１０６】
0004284867.tif 000039
【０１０４】
にて作成し，(u1,u2,e,v,C)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
（２）受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【０１０５】
【数１０７】
0004284867.tif 000040
【０１０６】
なる α'1，α'2，K'（|α'1|=k1，|α'2|=k2，|K'|=k3）を計算し，
【０１０７】
【数１０８】
0004284867.tif 000041
【０１０８】
が成立すれば（但し，α'＝α'1||α'2），
【０１０９】
【数１０９】
0004284867.tif 000042
【０１１０】
にて復号化を行い，復号化結果を出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【０１１１】
暗号文Cの別なる作成方法としては，送信者は，暗号文Cを（対称型）暗号化関数Eとその鍵データＫを用いて，
【０１１２】
【数１１０】
0004284867.tif 000043
【０１１３】
にて作成し，該受信者は，
【０１１４】
【数１１１】
0004284867.tif 000044
【０１１５】
が成立することを検査し，検査をパスした場合に
【０１１６】
【数１１２】
0004284867.tif 000045
【０１１７】
により復号化を行う。但し，[x]-kはxの上位k桁を除いた整数列を表す。
【０１１８】
本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【０１１９】
【数１１３】
0004284867.tif 000046
【０１２０】
を前もって計算して保存しておくことで，暗号化処理負担を大幅に減少させることが可能である。
（実施例５）
本実施例は，実施例１で述べた公開鍵暗号をベースに対称型暗号を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号通信によって送信する場合について説明する。本実施例によれば，実施例３の方法に比べて効率性に優れ，対称型暗号が選択平文攻撃に対して頑強（IND-CPA）であるとき，最強暗号（NM-CCA2）であることが証明できる。また，本実施例による方式では，鍵Ｋ自身を送信するのではなく，各々が作成できるようにシードを共有させている。
【０１２１】
図１は，本実施例のシステム構成を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【０１２２】
【数１１４】
0004284867.tif 000047
【０１２３】
なる秘密情報を作成し，
【０１２４】
【数１１５】
0004284867.tif 000048
【０１２５】
なる公開情報を作成し（但し，群Ｇは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【０１２６】
【数１１６】
0004284867.tif 000049
【０１２７】
を満たすものとする。），公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，送信データm（m∈M，Mは平文空間）に対して，乱数生成手段101を用いて，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【０１２８】
【数１１７】
0004284867.tif 000050
【０１２９】
を計算し（但し，α＝α1||α2），送信データmの暗号文Cを（対称型）暗号化関数Eを用いて，
【０１３０】
【数１１８】
0004284867.tif 000051
【０１３１】
にて作成する。さらに，送信者側装置100は，送信者Ａの操作により，(u1,u2, ,v,C)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
（２）受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて，
【０１３２】
【数１１９】
0004284867.tif 000052
【０１３３】
を計算し，さらに暗号文から，
【０１３４】
【数１２０】
0004284867.tif 000053
【０１３５】
なる α'1，α'2（α'1∈X1，α'2∈Ｘ2）を計算し，
【０１３６】
【数１２１】
0004284867.tif 000054
【０１３７】
が成立すれば（但し，α'＝α'1||α'2），
m'を復号化結果を出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【０１３８】
さらに，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，u1,u2, ,vを前もって計算して保存しておくことが可能である。これにより，暗号化処理の負担を大幅に減らし処理時間を短縮することが可能になる。
（実施例６）
本実施例は，実施例２で述べた公開鍵暗号をベースに対称型暗号を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号通信によって送信する場合について説明する。
【０１３９】
図１は，本実施例のシステム構成を示す。また，図６は，本実施例の概要を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【０１４０】
【数１２２】
0004284867.tif 000055
【０１４１】
なる秘密情報を作成し，
【０１４２】
【数１２３】
0004284867.tif 000056
【０１４３】
なる公開情報を作成し，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
送信者側装置100は，送信者Ａの操作により，平文mに対して，乱数生成手段101を用いて，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を選び，さらに，乱数生成手段101を用いて，乱数 r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【０１４４】
【数１２４】
0004284867.tif 000057
【０１４５】
を計算する。さらに，送信者側装置100は，送信者Ａの操作により，送信データmの暗号文Cを（対称型）暗号化関数Eを用いて，
【０１４６】
【数１２５】
0004284867.tif 000058
【０１４７】
にて作成し，(u1,u2, ,v,C)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
【０１４８】
受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて，
【０１４９】
【数１２６】
0004284867.tif 000059
【０１５０】
を計算し，さらに暗号文から，
【０１５１】
【数１２７】
0004284867.tif 000060
【０１５２】
なる α'1，α'2（|α'1|=k1，|α'2|=k2）を計算し，
【０１５３】
【数１２８】
0004284867.tif 000061
【０１５４】
が成立すれば（但し，α'＝α'1||α'2），
m'を復号化結果として出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。
【０１５５】
さらに，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1，α2(|α1|=k1,|α2|=k2)，r∈Zqを選び，u1,u2, ,vを前もって計算して保存しておくことが可能である。これにより，暗号化処理の負担を大幅に減らし処理時間を短縮することが可能になる。
（実施例７）
本実施例は，実施例１で述べた公開鍵暗号と他の非対称型暗号を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号通信によって送信する場合について説明する。本実施例によれば，他の弱い非対称型暗号（NM-CPA）を最強暗号（NM-CCA2）に変換することができる。
【０１５６】
図１は，本実施例のシステム構成を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【０１５７】
【数１２９】
0004284867.tif 000062
【０１５８】
なる秘密情報を作成し，
【０１５９】
【数１３０】
0004284867.tif 000063
【０１６０】
なる公開情報を作成し（但し，群Gは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【０１６１】
【数１３１】
0004284867.tif 000064
を満たすものとする。Mは平文空間），公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
（１）送信者側装置100は，送信者Ａの操作により，乱数生成手段101を用いて，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【０１６２】
【数１３２】
0004284867.tif 000065
【０１６３】
を計算し（但し，α＝α1||α2），送信データmの暗号文Cを（非対称型）暗号化関数Epkを用いて，
【０１６４】
【数１３３】
0004284867.tif 000066
にて作成する。さらに，送信者側装置100は，送信者Ａの操作により，(u1,u2,e,v)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
（２）受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【０１６５】
【数１３４】
0004284867.tif 000067
【０１６６】
なる α'1，α'2，ｍ'（α'1∈X1，α'2∈Ｘ2，m'∈Ｍ）を計算し，
【０１６７】
【数１３５】
0004284867.tif 000068
【０１６８】
が成立すれば（但し，
【０１６９】
【数１３６】
0004284867.tif 000069
【０１７０】
とする）m'を復号化結果として出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。  さらに，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，u1,u2,vを前もって計算して保存しておくことが可能である。これにより，暗号化処理の負担を大幅に減らし処理時間を短縮することが可能になる。
（実施例８）
本実施例は，実施例７と同様に，実施例２で述べた公開鍵暗号をベースに非対称型暗号を用いて，メッセージの送信者であるＡが受信者であるＢに対して，送信データmを暗号通信によって送信する場合について説明する。
【０１７１】
図１は，本実施例のシステム構成を示す。また，図６は，本実施例の概要を示す。
１．鍵生成処理
受信者側装置200内の鍵生成手段201は，受信者Ｂの操作により，予め，
【０１７２】
【数１３７】
0004284867.tif 000070
【０１７３】
なる秘密情報を作成し，
【０１７４】
【数１３８】
0004284867.tif 000071
【０１７５】
なる公開情報を作成し，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
２．暗復号化処理
送信者側装置100は，送信者Ａの操作により，乱数生成手段101を用いて，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を選び，さらに，乱数生成手段101を用いて，乱数 r∈Zqを選び，べき乗算手段102，演算手段103，剰余演算手段104を用いて，
【０１７６】
【数１３９】
0004284867.tif 000072
【０１７７】
を計算する。さらに，送信者側装置100は，送信者Ａの操作により，送信データm（正整数）の暗号文Cを（非対称型）暗号化関数Eを用いて，
【０１７８】
【数１４０】
0004284867.tif 000073
【０１７９】
にて作成し，(u1,u2,e,v)を暗号文として，通信装置106を用いて通信回線300を介して受信者側装置200に送信する。
【０１８０】
受信者側装置200は，受信者Ｂの操作により，保持している上記秘密情報と，受信者側装置200内のべき乗算手段202，剰余演算手段203，演算手段204を用いて暗号文から，
【０１８１】
【数１４１】
0004284867.tif 000074
【０１８２】
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，m'は正整数）を計算し，
【０１８３】
【数１４２】
0004284867.tif 000075
【０１８４】
が成立すれば（但し，
【０１８５】
【数１４３】
0004284867.tif 000076
【０１８６】
とする），m'を復号化結果として出力する。成立しなければ該暗号文を拒否する旨を復号化結果として出力する。  また，本実施例による方法では，送信者側装置100は，送信者Ａの操作により暗号文を作成するに当たり，予め乱数α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，u1,u2,vを前もって計算して保存しておくことで，暗号化処理負担を大幅に減少させることが可能である。
【０１８７】
以上，各実施例では，送信者と受信者が各々の装置を利用して暗号通信を行うという一般形で述べたが，具体的には様々なシステムに適用される。
【０１８８】
例えば，電子ショッピングシステムでは，送信者はユーザであり，送信者側装置はパソコンなどの計算機であり，受信者は小売店またはその従業者，受信者側装置は小売店側装置，具体的には当該店舗におけるパソコンなどの計算機となる。このとき，ユーザが注文した商品等の注文書または注文書を暗号化した鍵は，本実施例による方法により暗号化されて小売店側装置に送信される。
【０１８９】
また，電子メール暗号化システムでは，各々の装置はパソコンなどの計算機であり，送信者のメッセージまたはメッセージを暗号化した鍵は，本実施例による方法により暗号化されて受信者の計算機に送信される。
【０１９０】
その他にも，従来の暗号化技術が使われている様々なシステムに適用することが可能である。
【０１９１】
したがって，各実施例における平文ｍまたはメッセージｍには，さまざまなディジタル化されたデータ（マルチメディアデータ）を適用することができる。
【０１９２】
なお，本実施例における各計算は，CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが，プログラムだけではなく，いずれかがハードウェア化された演算装置であって，他の演算装置や，CPUと，データのやりとりを行うものであっても良い。
【０１９３】
【発明の効果】
本発明の公開鍵暗号方法により，最も強力な攻撃法である適応的選択暗号文攻撃に対して安全であることが保証された効率的な暗号通信と，その応用装置，システムを実現することができる。
【図面の簡単な説明】
【図１】本発明の実施例のシステム構成を示す図である。
【図２】本発明の実施例における送信者側装置の内部構成を示す図である。
【図３】本発明の実施例における受信者側装置の内部構成を示す図である。
【図４】本発明の実施例２の概要を示す図である。
【図５】本発明の実施例４の概要を示す図である。
【図６】本発明の実施例６の概要を示す図である。
【符号の説明】
１００…送信者側装置，１０１…送信者側装置１００内の乱数生成手段，１０２…送信者側装置１００内のべき乗算手段，１０３…送信者側装置１００内の演算手段，１０４…送信者側装置１００内の剰余演算手段，１０５…送信者側装置１００内のメモリ，１０６…送信者側装置１００内の通信装置，１０７…送信者側装置１００内の入力装置，１０８…送信者側装置１００内の暗号化装置，２００…受信者側装置，２０１…受信者側装置２００内の鍵生成手段，２０２…受信者側装置２００内のべき乗算手段，２０３…受信者側装置２００内の剰余演算手段，２０４…受信者側装置２００内の演算手段，２０５…受信者側装置２００内のメモリ，２０６…受信者側装置２００内の通信装置，２０７…受信者側装置２００内の復号化装置，３００…通信回線。
【図１】
0004284867.tif 000143
【図２】
0004284867.tif 000144
【図３】
0004284867.tif 000145
【図４】
0004284867.tif 000146
【図５】
0004284867.tif 000147
【図６】
0004284867.tif 000148