(57)【要約】【課題】安全かつ効率的なしきい値暗号方式を実現する。【解決手段】  暗号化端末１０が、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化し、暗号文Ｃを生成する。複数の復号サーバ５０１〜５０ｎがそれぞれ、暗号文Ｃと、分散鍵ｓ１〜ｓｎとを用いて複数の部分復号情報δ１〜δｎを生成する。復元端末２０が、複数の部分復号情報δ１〜δｎを用いて乱数ｒを計算し、暗号文Ｃから平文ｍを復元する。【選択図】図１
2005321719.tif 000002
【特許請求の範囲】
【請求項１】
公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、前記公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて、部分復号情報δを生成する複数の部分復号情報生成部と、
該複数の部分復号情報生成部により生成された複数の部分復号情報δを用いて、前記暗号文Ｃから前記平文ｍを復元する平文復元部と
を備えることを特徴とする通信システム。
【請求項２】
前記秘密情報ｄを複数に分散して複数の分散鍵ｓを生成する鍵生成部を備えることを特徴とする請求項１に記載の通信システム。
【請求項３】
公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、前記公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて、部分復号情報δを生成する部分復号情報生成部と、
前記部分復号情報δを、前記暗号文Ｃから前記平文ｍを復元する復元装置に送信する部分復号情報送信部と
を備えることを特徴とする復号装置。
【請求項４】
前記部分復号情報生成部は、δ＝（ＣｍｏｄＮ）２ΔｓｍｏｄＮを計算することにより、前記部分復号情報δを生成することを特徴とする請求項３に記載の復号装置。
【請求項５】
公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、前記公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて部分復号情報δを生成する複数の復号装置から、複数の部分復号情報δを受信する部分復号情報受信部と、
前記複数の部分復号情報δを用いて前記暗号文Ｃから前記平文ｍを復元する平文復元部と
を備えることを特徴とする復元装置。
【請求項６】
前記平文復元部は、前記部分復号情報δを用いて前記乱数ｒを計算し、該乱数ｒを用いて前記暗号文Ｃから前記平文ｍを復元することを特徴とする請求項５に記載の復元装置。
【請求項７】
公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃから部分復号情報δを生成するために用いる複数の分散鍵ｓを、前記公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散して生成する鍵生成部と、
前記複数の分散鍵ｓを前記部分復号情報δを生成する複数の復号装置に送信する鍵送信部と
を備えることを特徴とする鍵生成装置。
【請求項８】
公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、前記公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて部分復号情報δを複数生成し、
複数の部分復号情報δを用いて前記暗号文Ｃから前記平文ｍを復元することを特徴とする通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システム、復号装置、復元装置、鍵生成装置及び通信方法に関する。
【背景技術】
【０００２】
従来、安全な通信を行うために、公開鍵暗号方式が用いられている。公開鍵暗号方式では、公開鍵に対する復号鍵を安全に保管しておくことが大きな課題の一つになっている。この課題に対する解決方法の一つとして、種々のしきい値暗号方式が開発されている。しきい値暗号方式とは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、分散鍵を持つ複数の装置が協力しなければ、平文を復元できないようにした方式である。
【０００３】
しきい値暗号方式としては、例えば、素因数分解型の暗号方式を用いる方式（例えば、非特許文献１、非特許文献２参照）や、 離散対数型の暗号方式を用いる方式（例えば、非特許文献３参照）等がある。
【非特許文献１】P.-A. Fouque，G．Poupard and J．Stern，“Sharing Decryption in the Context of Voting or Lotteries”， Financial Cryptography 2000 Lecture Notes in Computer Science，pp．90−104，2000
【非特許文献２】J.Katz and M.Yung, “Threshold Cryptosystems Based on Factoring”, ASIACRYPT2002, Lecture Notes in Computer Science, 2501, pp.192-205, Springer-Verlag, 2002
【非特許文献３】V.Shoup and R.Gennaro, “Securing Threshold Cryptosystems against Chosen Ciphertext Attack”, Journal of Cryptology, vol.15, no.2, pp.75-96
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、素因数分解型のしきい値暗号方式において、法Ｎのもとでの計算により暗号化及び復号を行う場合は、選択平文攻撃に対する安全性を確保できない可能性があった。一方、選択平文攻撃に耐えるしきい値暗号方式を実現するためには、非特許文献１に示されるようにＮ乗の計算を行って暗号化を行い、法Ｎ２のもとでの計算を行って復号する必要があった。そのため、一定の安全性を確保するためには、法Ｎのもとでの計算ではなく、Ｎ乗や法Ｎ２のもとでの計算が必要であった。その結果、暗号化のときも、復号のときも法Ｎ２のもとで指数が高いべき乗演算を行う必要があり、暗号化から復号までの全体的な計算量が多くなってしまう問題があった。
【０００５】
又、非特許文献２に示される素因数分解型のしきい値暗号方式では、法Ｎのもとでの計算により暗号化及び復号を行い、選択平文攻撃に対する安全性を確保できるものの、１ビットしか暗号化できなかった。そのため、暗号化及び復号の効率が非常に悪く、実用的ではなかった。更に、離散対数型のしきい値暗号方式でも、指数が高いべき乗演算を行う必要があった。
【０００６】
そのため、従来のしきい値暗号方式では、暗号化と復号を安全かつ効率的に行うことができなかった。又、携帯性を重視する移動通信端末の場合には、高速のＣＰＵを搭載することが困難なため、従来のしきい値暗号方式はいずれも、その計算量の多さから実用向きではなかった。
【０００７】
そこで、本発明は、安全かつ効率的なしきい値暗号方式を実現することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る通信システムは、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて部分復号情報δを生成する複数の部分復号情報生成部と、複数の部分復号情報生成部により生成された複数の部分復号情報δを用いて、暗号文Ｃから平文ｍを復元する平文復元部とを備えることを特徴とする。
【０００９】
このようにして、通信システムによれば、ｍＮをｒｅを用いて暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、本発明の通信システムでは、複数ビットの平文ｍをｅ乗の計算により暗号化し、かつ、法Ｎのもとでの計算により復号しても安全性を確保できる。例えば、ＲＳＡ暗号方式でよく使用されている公開情報（ｅ，Ｎ）の値は、Ｎ＝１０２４ビット、ｅ＝１７ビットである。よって、ｅ乗や法Ｎのもとでの計算は、計算量を少なくできることが分かる。以上のことから、通信システムによれば、安全かつ効率的なしきい値暗号方式を実現することができる。
【００１０】
更に、通信システムは、秘密情報ｄを複数に分散して複数の分散鍵ｓを生成する鍵生成部を備える。
【００１１】
又、本発明に係る復号装置は、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて、部分復号情報δを生成する部分復号情報生成部と、部分復号情報δを、暗号文Ｃから平文ｍを復元する復元装置に送信する部分復号情報送信部とを備えることを特徴とする。
【００１２】
このような復号装置によれば、ｍＮをｒｅを用いて暗号化した暗号文Ｃを、法Ｎのもとでの計算により部分的に復号でき、生成した部分復号情報δを復元装置に提供できる。そのため、復号装置によれば、ｍＮをｒｅを用いて暗号化する方式をしきい値暗号方式に適用できる。よって、復号装置によれば、安全かつ効率的なしきい値暗号方式を実現することができる。
【００１３】
部分復号情報生成部は、δ＝（ＣｍｏｄＮ）２ΔｓｍｏｄＮを計算することにより、部分復号情報δを生成することが好ましい。Δは、Δ＝ｎ！と定義される。ｎは、分散鍵ｓの個数である。
【００１４】
本発明に係る復元装置は、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて部分復号情報δを生成する複数の復号装置から、複数の部分復号情報δを受信する部分復号情報受信部と、複数の部分復号情報δを用いて暗号文Ｃから平文ｍを復元する平文復元部とを備えることを特徴とする。
【００１５】
このような復元装置によれば、法Ｎのもとでの計算による部分的な復号により生成された部分復号情報δを受信し、ｍＮをｒｅを用いて暗号化した暗号文Ｃから平文ｍを適切に復元できる。よって、復元装置によれば、ｍＮをｒｅを用いて暗号化する方式をしきい値暗号方式に適用できる。そのため、復元装置によれば、安全かつ効率的なしきい値暗号方式を実現することができる。平文復元部は、部分復号情報δを用いて乱数ｒを計算し、その乱数ｒを用いて暗号文Ｃから平文ｍを復元することが好ましい。
【００１６】
本発明に係る鍵生成装置は、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃから部分復号情報δを生成するために用いる複数の分散鍵ｓを、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散して生成する鍵生成部と、複数の分散鍵ｓを部分復号情報δを生成する複数の復号装置に送信する鍵送信部とを備えることを特徴とする。
【００１７】
このような鍵生成装置によれば、ｍＮをｒｅを用い暗号化した暗号文Ｃを、法Ｎのもとでの計算により部分的に復号する際に必要な分散鍵ｓを生成し、復号装置に提供できる。よって、鍵生成装置によれば、ｍＮをｒｅを用いて暗号化する方式をしきい値暗号方式に適用できる。そのため、鍵生成装置によれば、安全かつ効率的なしきい値暗号方式を実現することができる。
【００１８】
本発明に係る通信方法は、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化する際に、ｍＮをｒｅを用いて暗号化した暗号文Ｃと、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを複数に分散した分散鍵ｓとを用いて部分復号情報δを生成し、複数の部分復号情報δを用いて暗号文Ｃから平文ｍを復元することを特徴とする。
【発明の効果】
【００１９】
以上説明したように、本発明によれば、安全かつ効率的なしきい値暗号方式を実現できる。
【発明を実施するための最良の形態】
【００２０】
〔通信システム〕
図１に示すように、通信システム１００は、暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０１〜５０ｎと、ネットワーク６０とを備える。暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０１〜５０ｎは、ネットワーク６０を介して、情報を送受信する。
【００２１】
鍵生成サーバ３０は、平文ｍの暗号化に用いる公開情報（ｅ，Ｎ）と、暗号文Ｃの復号に用いる秘密情報ｄとその分散鍵ｓを生成する鍵生成装置である。鍵生成サーバ３０は、鍵生成部３１と、鍵データベース３２と、送信部３３とを備える。鍵生成部３１は、公開情報（ｅ，Ｎ）と、それに対する秘密情報ｄと、秘密情報ｄを複数に分散した分散鍵ｓとを生成する。鍵生成部３１は、ｎ個の分散鍵ｓを生成する。よって、各分散鍵を区別するときには、ｉ番目の分散鍵を「ｓｉ」と表す。このように分散鍵ｓには、１〜ｎまでの番号が付与される。
【００２２】
鍵データベース３２は、公開情報（ｅ，Ｎ）を記憶する。送信部３３は、鍵成部３１が生成した公開情報（ｅ，Ｎ）や分散鍵ｓを暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０１〜５０ｎに送信する。このような鍵生成サーバ３０は、コンピュータを、鍵生成部３１と、鍵データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００２３】
暗号化端末１０は、平文ｍを暗号化して暗号文Ｃを生成する暗号化装置である。暗号化端末１０は、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４とを備える。受信部１１は、鍵生成サーバ３０から公開情報（ｅ，Ｎ）を受信する。受信部１１は、平文ｍを受信し、暗号文生成部１２に入力してもよい。入力部１４は、外部から入力される平文ｍを取得し、暗号文生成部１２に入力する。暗号文生成部１２は、公開情報（ｅ，Ｎ）と乱数ｒとを用いて平文ｍを暗号化し、暗号文Ｃを生成する際に、ｍＮをｒｅを用いて暗号化する。暗号文生成部１２は、入力部１４や受信部１１から平文ｍを取得する。暗号文生成部１２は、以下に示す（１）式又は（２）式を計算することにより、平文ｍを暗号化して暗号文Ｃを生成することが好ましい。
【００２４】
Ｃ＝ｒｅ（１＋ｍＮ）ｍｏｄＮ２    （１）式
Ｃ＝ｒｅ＋ｍＮｍｏｄＮ２          （２）式
（１）式、（２）式に示すように、ｍＮをｒｅを用いて暗号化する方法は限定されない。例えば、暗号文生成部１２は、ｍＮに対してｒｅを乗算又は加算することにより暗号化してもよく、ｍＮからｒｅを減算することにより暗号化してもよく、ｍＮをｒｅで除算することにより暗号化してもよい。又、暗号文生成部１２は、ｍＮを少なくともｒｅを用いて暗号化すればよく、ｒｅに加え、更に他の数値を用いてｍＮを暗号化しても構わない。
【００２５】
例えば、暗号文生成部１２は、（１）式に示すように、ｍＮに数値を加算又は減算したものにｒｅを乗算したり、ｍＮに数値を加算又は減算したものをｒｅで除算したりしてもよい。尚、（１）式に示すように、ｍＮに対してｒｅを乗算又は除算することにより暗号化する場合は、１からＮ２−１までの値であってＺ＊Ｎ２のいずれかの整数を、ｍＮに加えたものに対して乗算もしくは除算を行う。尚、「Ｚ＊Ｘ」とは、ＺＸかつＸと互いに素な整数の集合（Ｚ＊Ｘ＝（Ｚ／ＸＺ）＊）を表す。この場合、（１）式に示すように、ｍＮに１を加えたものに対して、ｒｅを乗算又は除算することが好ましい。又、暗号文生成部１２は、（２）式の右辺に数値、例えば、「１」を加算したり、右辺から数値を減算したりしてもよい。
【００２６】
（１）式、（２）式は、ｍＮをｒｅを用いて暗号化する暗号方式である。特に（１）式は、ＲＳＡ−Ｐａｉｌｌｉｅｒ暗号と呼ばれる。ＲＳＡ−Ｐａｉｌｌｉｅｒ暗号は、例えば、「D. Catalano, R. Gennaro, N. H. -Graham, P. Q. Nguyen,“Paillier's cryptosystem revisited”, ACM Conference on Computer and Communications Security 2001, pp.206-214」等に提案されている。
【００２７】
送信部１３は、暗号文生成部１２が生成した暗号文Ｃを、暗号文管理サーバ４０に送信する。このような暗号化端末１０は、コンピュータを、受信部１１と、暗号文生成部１２と、送信部１３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００２８】
暗号文管理サーバ４０は、暗号文Ｃを暗号化端末１０から受信し、暗号文Ｃを各装置に提供する暗号文管理装置である。暗号文管理サーバ４０は、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。受信部４１は、暗号化端末１０から暗号文Ｃを受信する。又、受信部４１は、復元端末２０や復号サーバ５０１〜５０ｎから、暗号文Ｃの要求を受信する。更に、受信部４１は、鍵生成サーバ３０から公開情報（ｅ，Ｎ）を受信する。
【００２９】
暗号文データベース４３は、暗号文Ｃを記憶する。送信部４４は、暗号文Ｃを復元端末２０、復号サーバ５０１〜５０ｎに送信する。このような暗号文管理サーバ４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００３０】
復号サーバ５０１〜５０ｎは、部分復号情報δを生成する。部分復号情報δは、暗号文Ｃから平文ｍを復元する際に用いる情報であり、復元端末２０が平文ｍの復元をするために必要な情報である。部分復号情報δは、暗号文Ｃと分散鍵ｓとを用いた計算を行うことにより、即ち、暗号文Ｃを分散鍵ｓを用いて部分的に復号することにより得られる情報である。複数の復号サーバ５０１〜５０ｎがそれぞれ異なる分散鍵ｓを用いて部分復号情報δを生成することにより、複数の部分復号情報δが生成される。分散鍵ｓｉを用いて生成された部分復号情報は、「δｉ」と表す。よって、複数の部分復号情報δとして、分散鍵ｓ１〜ｓｎを用いて部分復号情報δ１〜δｎが生成される。このように部分復号情報δには、１〜ｎまでの番号が付与される。又、復号サーバ５０１〜５０ｎにも、１〜ｎまでの番号が付与される。
【００３１】
復号サーバ５０１〜５０ｎはそれぞれ、受信部５１１〜５１ｎと、部分復号情報生成部５２１〜５２ｎと、送信部５３１〜５３ｎとを備える。受信部５１１〜５１ｎは、鍵生成サーバ３０から公開情報（ｅ，Ｎ）と分散鍵ｓとを受信する。又、受信部５１１〜５１ｎは、復元端末２０から部分復号情報δの要求（以下「復号要求」という）を受信する。更に、受信部５１１〜５１ｎは、暗号文管理サーバ４０から暗号文Ｃを受信する。
【００３２】
部分復号情報生成部５２１〜５２ｎは、暗号文Ｃと分散鍵ｓとを用いて、以下に示す（３）式を計算することにより、部分復号情報δを生成する。尚、Δ＝ｎ！と定義する。又、鍵生成サーバ３０が、公開情報（ｅ，Ｎ）の作成時に、ＧＣＤ（ｅ，Δ）＝１となるようにｅを定める。尚、「ＧＣＤ（Ｘ，Ｙ）」は、ＸとＹの最大公約数を表す。
【００３３】
δ＝（ＣｍｏｄＮ）２ΔｓｍｏｄＮ    （３）式
送信部５３１〜５３ｎは、部分復号情報生成部５２１〜５２ｎが生成した部分復号情報δを復元端末２０に送信する。又、送信部５３１〜５３ｎは、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。このような復号サーバ５０１〜５０ｎは、コンピュータを、受信部５１１〜５１ｎと、部分復号情報生成部５２１〜５２ｎと、送信部５３１〜５３ｎとして機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００３４】
復元端末２０は、暗号文Ｃから平文ｍを復元する復元装置である。復元端末２０は、受信部２１と、平文復元部２２と、送信部２３と、出力部２４とを備える。受信部２１は、複数の部分復号情報δを、複数の復号サーバ５０１〜５０ｎから受信する。又、受信部２１は、暗号文Ｃを暗号文管理サーバ４０から受信する。更に、受信部２１は、鍵生成サーバ３０から公開情報（ｅ，Ｎ）を受信する。平文復元部２２は、複数の部分復号情報δを用いて暗号文Ｃから平文ｍを復元する。平文復元部２２は、復元した平文ｍを出力部２４に出力する。送信部２３は、暗号文Ｃの要求や、復号要求を送信する。このような復元端末２０は、コンピュータを、受信部２１と、平文復元部２２と、送信部２３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００３５】
次に、図１、図２を用いて、平文ｍの暗号化から復元において通信システム１００が行う処理を詳細に説明する。通信システム１００では、（ｔ，ｎ）しきい値暗号方式により復号を行う。（ｔ，ｎ）しきい値暗号方式とは、ｎ個の分散鍵ｓ１〜ｓｎを用いて生成されるｎ個の部分復号情報δ１〜δｎのうち、ｔ個の部分復号情報を用いれば、平文ｍが復元できるしきい値暗号方式である。よって、「ｔ」は、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報δの数を表す。
【００３６】
まず、通信システム１が、ｍＮをｒｅを用いて暗号化する暗号方式を用いる場合を説明する。鍵生成サーバ３０の鍵生成部３１は、まず、２つの強い素数ｐ，ｑを選択し、その積を計算して、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【００３７】
更に、鍵生成部３１は、複数の分散鍵ｓの個数ｎよりも大きな素数をｅとして選択する。鍵生成部３１は、ｅとして、ＧＣＤ（ｅ，ｐｑ（ｐ−１）（ｑ−１））＝１と、ＧＣＤ（ｅ，２ｎ！）＝１とを満たす値を選択する。このようにして、鍵生成部３１は、公開情報（ｅ，Ｎ）を生成する。更に、ｐ’とｑ’の積を「Ｌ」と定義する。即ち、Ｌ＝ｐ’ｑ’と定義する。鍵生成部３１は、生成した公開情報（ｅ，Ｎ）を、鍵データベース３２に格納する。鍵生成部３１は、生成した公開情報（ｅ，Ｎ）を、鍵送信部３３に入力する。
【００３８】
次に、鍵生成部３１は、公開情報（ｅ，Ｎ）に対応する秘密情報ｄを生成する。鍵生成部３１は、秘密情報ｄが偶数の場合には公開情報ｅの選択をやり直す。秘密情報ｄは、（Ａｅ）ｄ＝ＡｍｏｄＮを満たす。又、Ａ∈Ｚ＊Ｎである。そのため、「Ａ」は、０からＮ―１までの整数のうち、Ｎと互いに素な整数である。このような「Ａ」であれば、全ての「Ａ」に対して、（Ａｅ）ｄ＝ＡｍｏｄＮが成立する。即ち、秘密情報ｄは、ｅｄ≡１ｍｏｄＬを満たす。更に、鍵生成部３１は、秘密情報ｄを複数に分散して複数の分散鍵ｓ、即ち、ｎ個の分散鍵ｓ１〜ｓｎを生成する。分散鍵ｓ１〜ｓｎは、相互に異なる秘密情報である。
【００３９】
本実施形態では、分散鍵ｓ１〜ｓｎの個数ｎは、復号サーバ５０１〜５０ｎの数と等しい。しかし、一つの復号サーバが複数の分散鍵を用いてもよい。よって、分散鍵ｓの個数と復号サーバの数は、必ずしも一致するとは限らない。分散鍵ｓ１〜ｓｎの個数と復号サーバ５０１〜５０ｎの数が一致する本実施形態では、復号サーバ５０ｉが、分散鍵ｓｉを用いる。例えば、鍵生成部３１は、Shamirにより提案された方法等を用いて、秘密情報ｄを複数に分散できる。
【００４０】
具体的には、鍵生成部３１は、ａｉ∈Ｚφ（Ｎ）を乱数として、秘密情報ｄ＝ａ０と定義することにより、秘密情報ｄを生成する。「φ（ｘ）」とは、Ｘのオイラー関数を表す。φ（Ｎ）＝（ｐ―１）（ｑ―１）と表すことができる。又、「ＺＸ」とは、０以上Ｘ未満の整数の集合（ＺＸ＝Ｚ／ＸＺ）を表す。この場合、鍵生成部３１は、以下に示す（４）式を計算することにより、複数の分散鍵ｓ１〜ｓｎを生成する。鍵生成部３１は、（４）式を用いて、ｓｉ＝ｆ（ｉ）ｍｏｄφ（Ｎ）を計算することにより分散鍵ｓｉを生成する。
【数１】
2005321719.tif 000003
【００４１】
あるいは、鍵生成部３１は、ａｉ∈Ｕ｛０，１，・・・，Ｌ―１｝、（ｉ＝１，２，・・・，ｔ―１）を乱数として、秘密情報ｄ＝ａ０と定義することにより、秘密情報ｄを生成する。「Ｘ∈ＵＧ」は、集合Ｇから一様な確率で要素Ｘを選択することを表す。この場合も、鍵生成部３１は、（４）式を計算することにより、複数の分散鍵ｓ１〜ｓｎを生成する。鍵生成部３１は、（４）式を用いて、ｓｉ＝ｆ（ｉ）ｍｏｄＬを計算することにより分散鍵ｓｉを生成する。鍵生成部３１は、生成した複数の分散鍵ｓ１〜ｓｎを、送信部３３に入力する。
【００４２】
更に、鍵生成部３１は、部分復号情報δが正しく暗号文Ｃを部分的に復号したものか否かを判定する際に用いる複数の検証鍵ｖｋを生成する。鍵生成部３１は、分散鍵ｓ１〜ｓｎと同数のｎ個の検証鍵ｖ１〜ｖｋｎを生成する。鍵生成部３１は、以下に示す（５）式を計算することにより検証鍵ｖｋ１〜ｖｋｎを生成する。
【数２】
2005321719.tif 000004
【００４３】
（５）式において、νはＱＮの生成元である。「ＱＸ」は、法Ｘのもとで平方余剰かつＸと互いに素な整数の集合を表す。そのため、「ＱＸ」は、Ｚ＊Ｘから要素を一つ取得し、２乗した値の集合となる。「νはＱＮの生成元」とは、νｋ（ｋは整数）によって、ＱＮのどの元も表すことができることをいう。鍵生成部３１は、生成した複数の検証鍵ｖ１〜ｖｋｎと、ＱＮの生成元νの合計ｎ＋１個の値を、送信部３３に入力する。
【００４４】
送信部３３は、図２に示すように、素数ｐ，ｑを秘密にしたまま復元端末２０に対応する公開情報（ｅ，Ｎ）だけを、暗号化端末１０、暗号文管理サーバ４０、復元端末２０に送信する。暗号化端末１０の受信部１１は、鍵生成サーバ３０から公開情報（ｅ，Ｎ）を受信し、暗号文生成部１２に入力する。暗号文管理サーバ４０の受信部４１は、鍵生成サーバ３０から公開情報（ｅ，Ｎ）を受信し、暗号文管理部４２に入力する。
【００４５】
更に、送信部３３は、公開情報（ｅ，Ｎ）と複数の分散鍵ｓ１〜ｓｎとを対応付けて、複数の復号サーバ５０１〜５０ｎに送信する。このとき、送信部３３は、複数の分散鍵ｓ１，・・・，ｓｉ，・・・，ｓｎをそれぞれ、復号サーバ５０１，・・・，５０ｉ，・・・，５０ｎに送信する。復号サーバ５０１〜５０ｎの受信部５１１〜５１ｎは、鍵生成サーバ３０から、公開情報（ｅ，Ｎ）と分散鍵ｓ１〜ｓｎを受信し、部分復号情報生成部５２１〜５２ｎに入力する。送信部３３は、このようにして、複数の分散鍵ｓを復号装置に送信する鍵送信部として機能する。
【００４６】
このように、送信部３３が、公開情報の「ｅ」に対応する秘密情報ｄを分散した分散鍵ｓ１〜ｓｎを、複数の復号サーバ５０１〜５０ｎに分散して提供する。更に、鍵生成サーバ３０自身も秘密情報ｄは、鍵データベース３２に格納しない。これにより、秘密情報ｄは一箇所に管理されず、複数の復号サーバ５０１〜５０ｎによって分散管理される。
【００４７】
又、送信部３３は、公開情報（ｅ，Ｎ）と検証鍵ｖ１〜ｖｋｎと、ＱＮの生成元νとを対応付けて、復元端末２０に送信する。復元端末２０の受信部２１は、鍵生成サーバ３０から、公開情報（ｅ，Ｎ）、検証鍵ｖｋ１〜ｖｋｎ、ＱＮの生成元νを受信し、平文復元部２２に入力する。
【００４８】
暗号化端末１０の暗号文生成部１２は、鍵生成サーバ３０から受信した公開情報（ｅ，Ｎ）を用いて暗号化する。具体的には、暗号文生成部１２は、ｍＮをｒｅを用いて暗号化することにより、平文ｍを暗号化して暗号文Ｃを生成する。例えば、暗号文生成部１２は、Ｃ＝ｒｅ（１＋ｍＮ）ｍｏｄＮ２（１）式、又は、Ｃ＝ｒｅ＋ｍＮｍｏｄＮ２（２）式を計算することにより平文ｍを暗号化し、暗号文Ｃを生成する。平文ｍは、暗号化端末１０が暗号化して秘密にしたい情報である。本実施形態における平文ｍは、複数の分散鍵ｓ１〜ｓｎを用いない限り、暗号文Ｃから平文ｍを復号できないようにすることにより、暗号化端末１０が分散管理したい情報である。
【００４９】
暗号文生成部１２は、乱数ｒを、（１）式を用いて暗号化を行う場合は、平文ｍがｍ∈ＺＮのとき、ｒ∈ＵＺ＊Ｎの中から選択する。暗号文生成部１２は、乱数ｒを、（２）式を用いて暗号化を行う場合は、平文ｍがｍ∈ＺＮのとき、ｒ∈ＵＺ＊Ｎ、もしくは、ｒ∈ＵＺＮ中から選択する。暗号文生成部１２は、生成した暗号文Ｃを送信部１３に入力する。送信部１３は、図２に示すように、暗号文Ｃを暗号文管理サーバ４０に送信する。
【００５０】
暗号文管理サーバ４０の受信部４１は、図２に示すように、暗号化端末１０から暗号文Ｃを受信する。受信部４１は、受信した暗号文Ｃを暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃを、鍵生成サーバ３０から受信した公開情報（ｅ，Ｎ）に対応付けて、暗号文データベース４３に格納する。
【００５１】
その後、復元端末２０の平文復元部２２が、公開情報（ｅ，Ｎ）をもとに作成した暗号文Ｃの要求と、公開情報（ｅ，Ｎ）と秘密情報をもとに作成した部分復号情報δを要求する復号要求を生成し、送信部２３に入力する。送信部２３は、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。暗号文管理サーバ４０の受信部４１は、復元端末２０から暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃの要求において指定されている公開情報（ｅ，Ｎ）に対応する暗号文Ｃを、暗号文データベース４３から取得し、公開情報（ｅ，Ｎ）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｅ，Ｎ）と対応付けられた暗号文Ｃを復元端末２０に送信する。このように公開情報（ｅ，Ｎ）は、暗号文Ｃを識別するための識別データとして用いることができる。
【００５２】
又、送信部２３は、復号要求を複数の復号サーバ５０１〜５０ｎに送信する。このとき、送信部２３は、復号要求を全ての復号サーバ５０１〜５０ｎにブロードキャストにより送信してもよく、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報の数ｔだけ復号サーバを選択し、送信してもよい。
【００５３】
復号サーバ５０１〜５０ｎの受信部５１１〜５１ｎは、復号要求を受信し、部分復号情報生成部５２１〜５２ｎに入力する。部分復号情報生成部５２１〜５２ｎは、復号要求を受け入れた場合、復号要求において指定されている公開情報（ｅ，Ｎ）を指定した暗号文Ｃの要求を生成し、送信部５３１〜５３ｎに入力する。送信部５３１〜５３ｎは、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。尚、部分復号情報生成部５２１〜５２ｎは、復号要求を拒否してもよい。
【００５４】
暗号文管理サーバ４０の受信部４１は、復号サーバ５０１〜５０ｎから暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、指定された公開情報（ｅ，Ｎ）に対応する暗号文Ｃを暗号文データベース４３から取得し、公開情報（ｅ，Ｎ）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｅ，Ｎ）と対応付けられた暗号文Ｃを復号サーバ５０１〜５０ｎに送信する。
【００５５】
復号サーバ５０１〜５０ｎの受信部５１１〜５１ｎは、暗号文Ｃを受信し、部分復号情報生成部５２１〜５２ｎに入力する。部分復号情報生成部５２１〜５２ｎはそれぞれ、受信した暗号文Ｃと分散鍵ｓ１〜ｓｎを用いて、（３）式、即ち、δ＝（ＣｍｏｄＮ）２ΔｓｍｏｄＮを計算することにより、暗号文Ｃを部分的に復号して部分復号情報δ１〜δｎを生成する。部分復号情報生成部５２１〜５２ｎは、復号要求において指定されている公開情報（ｅ，Ｎ）に対応する分散鍵ｓ１〜ｓｎを用いる。
【００５６】
例えば、復号サーバ５０ｉの場合、暗号文Ｃと分散鍵ｓｉを用いて、以下に示す（６）式を計算することにより、部分復号情報δｉを生成する。
【数３】
2005321719.tif 000005
【００５７】
部分復号情報生成部５２は、生成した部分復号情報δ１〜δｎを送信部５３１〜５３ｎに入力する。送信部５３１〜５３ｎはそれぞれ、図２に示すように、部分復号情報δ１〜δｎを復元端末２０に送信する。尚、全ての復号サーバ５０１〜５０ｎが、部分復号情報δ１〜δｎの生成、送信を行う必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報δの数ｔだけ部分復号情報δを生成し、復元端末２０に送信すればよい。
【００５８】
復元端末２０の受信部２１は、複数の復号サーバ５０１〜５０ｎから複数の部分復号情報δ１〜δｎを受信する。受信部２１は、受信した複数の部分復号情報δ１〜δｎを平文復元部２２に入力する。このようにして、受信部２１は、複数の復号装置から複数の部分復号情報δを受信する復号情報受信部として機能する。尚、受信部２１は、全ての復号サーバ５０１〜５０ｎから全ての部分復号情報δ１〜δｎを受信する必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要な数ｔの部分復号情報δを受信する。
【００５９】
平文復元部２２は、複数の部分復号情報δ１〜δｎを用いて、暗号文Ｃから平文ｍを復元する。平文復元部２２は、まず、部分復号情報δが正しく復号されたものか否かを判定する。平文復元部２２は、暗号文Ｃの４Δ乗「Ｃ４Δ」を底とした部分復号情報の２乗「δ２」の対数と、ＱＮの生成元のΔ乗「νΔ」を底とした検証鍵ｖｋの対数が等しいか否かを判定する。平文復元部２２は、対数が等しい場合には、部分復号情報δが正しく復号されたものであると判定し、対数が異なる場合には、部分復号情報δは正しく復号されていないと判定する。
【００６０】
平文復元部２２は、複数の部分復号情報δ１〜δｎについて、それぞれ検証鍵ｖ１〜ｖｋｎを用いて判定を行う。対数が等しいか否かの判定には、一般的な方法、例えば、文献「ＦＰＳ００：P．−A． Fouque，G．Poupard  and J．Stern，“Sharing Decryption in the Context of Voting or Lotteries”， Financial Cryptography 2000 Lecture Notes in Computer Science，pp．90−104，2000」に記載されている方法を用いることができる。
【００６１】
平文復元部２２は、正しく復号されていると判定した部分復号情報δ１〜δｎを用いて、まず、平文ｍの暗号化に用いた乱数ｒを計算する。尚、平文復元部２２は、全ての復号サーバ５０１〜５０ｎからの全ての部分復号情報δ１〜δｎを用いる必要はなく、（ｔ，ｎ）しきい値暗号方式において必要な数ｔの部分復号情報δを選択し、用いる。
【００６２】
平文復元部２２は、まず、以下に示す（７）式を計算する。平文復元部２２は、文献「ＳＨｏ００：victor Shoup， “Practical Threshold Signatures”，EUROCRYPT，Lecture Notes in Computer Science， pp.207-220，2000」と同様に、（８）式に示す条件で（７）式を計算する。
【数４】
2005321719.tif 000006
【数５】
2005321719.tif 000007
【００６３】
（７）式、（８）式において、「Ｓ」は、復元端末２０からの復号要求を受け入れた復号サーバ５０１〜５０ｎの番号の集合を表す。つまり、例えば、番号１、２、５が付与された復号サーバが復号要求を受け入れた場合には、Ｓ＝｛１，２，５｝と記述される。但し、集合Ｓに含まれる番号の数は、（ｔ，ｎ）しきい値暗号方式において部分復号情報δが必要な数ｔに限定される。又、（７）式、（８）式における「λ」は補間係数である。「λ」は、（４）式において、ｆ（０）＝ａ０を計算するために用いられ、（９）式に示す関係を持つ。
【数６】
2005321719.tif 000008
【００６４】
又、「Πｊ∈Ｓ／｛ｉ｝（ｉ−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての番号に関してｉから引き算した値を考え、それら全ての積を示す。同様に、「Πｊ∈Ｓ／｛ｉ｝（−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての数字に関して、絶対値を逆にした値の積を示す。
【００６５】
更に、公開情報の「ｅ」の選択方法から、「ｅ」と「４Δ」は互いに素である。そのため、Ｘ×４Δ２＋Ｙ×ｅ＝１を満たす整数Ｘと整数Ｙの組み合わせが存在する。よって、平文復元部２２は、次に、Ｘ×４Δ２＋Ｙ×ｅ＝１を満たす整数Ｘと整数Ｙの組み合わせを計算する。例えば、平文復元部２２は、拡張ユークリッドアルゴリズム（Euclidian algorithm）を用いて、多項式時間で整数Ｘ、Ｙを計算できる。
【００６６】
そして、平文復元部２２は、（７）式の計算結果と、求めた整数Ｘ、Ｙを用いて、以下に示す（１０）式を計算することにより、乱数ｒを計算する。尚、（１０）式は、非特許文献１に示される原理から（１１）式が成立するため、成立する。
【数７】
2005321719.tif 000009
【数８】
2005321719.tif 000010
【００６７】
次に、平文復元部２２は、計算した乱数ｒを用いて、暗号文Ｃから平文ｍを復元する。具体的には、平文復元部２２は、ｍＮをｒｅを用いて暗号化する際に用いた式、例えば、Ｃ＝ｒｅ（１＋ｍＮ）ｍｏｄＮ２（１）式、又は、Ｃ＝ｒｅ＋ｍＮｍｏｄＮ２（２）式に、受信した暗号文Ｃと、計算した乱数ｒを代入することにより、平文ｍを復元する。以上のようにして、復元端末２０は、復号サーバ５０１〜５０ｎから受信した複数の部分復号情報δ１〜δｎに基づいて、秘密の情報である平文ｍを復元できる。
【００６８】
尚、平文復元部２２は、部分復号情報δが正しく復号されていないと判定した場合には、その部分復号情報δを送信した復号サーバに対する部分復号情報の拒否通知を生成し、送信部２３に入力する。送信部２３は、拒否通知を復号サーバに送信し、処理を終了する。もしくは、平文復元部２２は、他の有効な部分復号情報をもとに秘密情報を復元する。
【００６９】
次に、通信システム１００が、（ｔ，ｎ）しきい値暗号方式として、（２，３）しきい値暗号方式を用いた場合の復元の具体例を示す。この場合、ｉ＝１の復号サーバ５０１と、ｉ＝２の復号サーバがそれぞれ、（６）式にΔ＝ｎ！＝３！を代入することにより、（１２）式、（１３）式に示すように部分復号情報δ１、δ２を計算し、得られた部分復号情報δ１、δ２を復元端末２０に送信する。
【数９】
2005321719.tif 000011
【数１０】
2005321719.tif 000012
【００７０】
復元端末２０は、受信した部分復号情報δ１、δ２を（１４）式に示すように、（７）式に代入して計算する。そして、復元端末２０は、（１４）式の計算結果を用いて乱数ｒを計算した後、乱数ｒと暗号文Ｃを用いて平文ｍを復元する。
【数１１】
2005321719.tif 000013
【００７１】
〔通信方法〕
次に、通信システム１００を用いて行う通信方法の手順を説明する。まず、鍵生成サーバ３０が、公開情報（ｅ，Ｎ）、複数の分散鍵ｓ１〜ｓｎ、複数の検証鍵ｖｋ１〜ｖｋｎを生成する（Ｓ１０１）。鍵生成サーバ３０は、公開情報（ｅ，Ｎ）を復元端末２０、復号サーバ５０１〜５０ｎ、暗号文管理サーバ４０、暗号化端末１０に送信する（Ｓ１０２〜Ｓ１０５）。鍵生成サーバ３０は、複数の分散鍵ｓ１〜ｓｎを復号サーバ５０１〜５０ｎに送信する（Ｓ１０６）。鍵生成サーバ３０は、複数の検証鍵ｖｋ１〜ｖｋｎを復元端末２０に送信する（Ｓ１０７）。
【００７２】
暗号化端末１０は、例えば、（１）式、（２）式のいずれかを用い、ｍＮをｒｅを用いて暗号化することにより、平文ｍを暗号化し、暗号文Ｃを生成する（Ｓ１０８）。暗号化端末１０は、生成した暗号文Ｃを暗号文管理サーバ４０に送信する（Ｓ１０９）。暗号文管理サーバ４０は、受信した暗号文Ｃを暗号文データベース４３に格納する（Ｓ１１０）。
【００７３】
復元端末２０は、暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ１１１）。暗号文管理サーバ４０は、復元端末２０の要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復元端末２０に送信する（Ｓ１１２）。暗号文管理サーバ４０は、復号サーバ５０１〜５０ｎの要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復号サーバ５０１〜５０ｎに送信する（Ｓ１１３）。
【００７４】
復元端末２０は、復号サーバ５０１〜５０ｎに復号要求を送信する（Ｓ１１４）。復号サーバ５０１〜５０ｎはそれぞれ、暗号文Ｃと分散鍵ｓ１〜ｓｎとを用いて、（３）式を計算することにより、部分復号情報δ１〜δｎを生成する（Ｓ１１５）。  復号サーバ５０１〜５０ｎはそれぞれ、生成した部分復号情報δ１〜δｎを復元端末２０に送信する（Ｓ１１６）。
【００７５】
復元端末２０は、受信した部分復号情報δ１〜δｎが正しく復号されたものか否かを、検証鍵ｖｋ１〜ｖｋｎを用いて判定する（Ｓ１１７）。復元端末２０は、部分復号情報δ１〜δｎが正しく復号されたものと判定した場合には、部分復号情報δ１〜δｎを用いて乱数ｒを計算する。そして、復元端末２０は、受信した暗号文Ｃと、計算した乱数ｒを、ｍＮをｒｅを用いて暗号化する際に用いた式に代入することにより、平文ｍを復元する（Ｓ１１８）。このようにして、暗号化端末１０と、複数の復号サーバ５０１〜５０ｎとの間で、秘密の情報である平文ｍを管理できる。尚、ステップ（Ｓ１０３）、（Ｓ１１３）に代えて、復元端末２０から復号サーバ５０１〜５０ｎに公開情報（ｅ，Ｎ）や暗号文Ｃを送信するようにしてもよい。
【００７６】
〔効果〕
このような通信システム１００、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０、複数の復号サーバ５０１〜５０ｎ及び通信方法によれば、ｍＮをｒｅを用いて暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、通信システム１００では、複数ビットの平文ｍを、ｅ乗の計算により暗号化し、かつ、法Ｎのもとでの計算により復号しても安全性を確保できる。
【００７７】
例えば、ＲＳＡ暗号方式でよく使用されている公開情報（ｅ，Ｎ）の値は、Ｎ＝１０２４ビット、ｅ＝１７ビットである。よって、ｅ乗や法Ｎのもとでの計算は、計算量を少なくできることが分かる。以上のことから、通信システム１００によれば、安全かつ効率的なしきい値暗号方式を実現することができる。
【００７８】
特に、暗号化端末１０や復元端末２０が、携帯性を重視する移動通信端末のように高速のＣＰＵを搭載することが困難な装置の場合や、復号サーバ５０１〜５０ｎの計算量力が低い場合、記憶容量が少ない場合においても、計算量が少ない本発明のしきい値暗号方式であれば利用可能である。このように、本発明のしきい値暗号方式は、計算能力が低い暗号化装置や復号装置、復元装置、あるいは、記憶容量が低い暗号化装置や復号装置、復元装置においても、利用可能であり、暗号化と復号を効率的に行うことができる。
【００７９】
尚、本発明は、上記実施の形態に限定されるものではなく、種々の変更が可能である。暗号化端末１０、復号サーバ５０１〜５０ｎの一部、又は、復元端末２０が、鍵生成サーバ３０の機能の一部又は全部を備え、鍵生成装置として機能してもよい。又、通信システム１００は、暗号文管理サーバ４０を複数備えてもよい。あるいは、暗号化端末１０又は復号サーバ５０１〜５０ｎの一部が、暗号文管理サーバ４０の機能の一部又は全部を備え、暗号文管理装置として機能してもよい。更に、復号サーバ５０１〜５０ｎの一部が復元端末２０の機能の一部又は全部を備え、復元装置として機能してもよい。又、端末装置は、暗号化端末１０と復元端末２０の機能の両方を備え、平文ｍの暗号化及び復元の両方を実施できるようにしてもよい。
【００８０】
又、上記実施の形態では、暗号文Ｃを識別するための識別データとして公開情報（ｅ，Ｎ）を用いているが、公開情報以外のデータを識別データとして用いることができる。又、鍵生成サーバ３０は、公開情報（ｅ，Ｎ）の暗号文管理サーバ４０への送信を省略してもよい。尚、この場合には、暗号文管理サーバ４０は、暗号文Ｃの要求と暗号文Ｃとを対応付けるための識別データとして、公開情報（ｅ，Ｎ）以外のものを暗号文Ｃに付与し、その識別データを復元端末２０へ与え、その識別データに対応付けて暗号文Ｃを暗号文データベース４３に格納する。又、鍵生成サーバ３０は、公開情報の「ｅ」の復号サーバ５０１〜５０ｎへの送信を省略してもよい。
【００８１】
あるいは、鍵生成サーバ３０は、公開情報（ｅ，Ｎ）を、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０１〜５０ｎに送信せずに、これらの装置が自由に閲覧して取得できるようにしてもよい。又、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０１〜５０ｎ等が、予め公開情報（ｅ，Ｎ）や分散鍵ｓ１〜ｓｎ、検証鍵ｖｋ１〜ｖｋｎ等を保持することにより、鍵生成サーバ３０を省略してもよい。
【００８２】
又、復号サーバ５０１〜５０ｎが完全に信用できる場合には検証鍵を用いなくてもよい。その場合には、復元端末２０は、部分復号情報δが正しいか否かの判定を行わないため、より高速に処理を行え、効率を向上できる。
【図面の簡単な説明】
【００８３】
【図１】本発明の実施の形態に係る通信システムの構成を示す図である。
【図２】本発明の実施の形態に係る情報の流れを示す図である。
【図３】本発明の実施の形態に係る通信方法の手順を示すフロー図である。
【符号の説明】
【００８４】
１００  通信システム
１０  暗号化端末
１１，２１，４１，５１１〜５１ｎ  受信部
１２  暗号文生成部
１３，２３，３３，４４，５３１〜５３ｎ  送信部
１４  入力部
２０  復元端末
２２  平文復元部
２４  出力部
３０  鍵生成サーバ
３１  鍵生成部
３２  鍵データベース
４０  暗号文管理サーバ
４２  暗号文管理部
４３  暗号文データベース
５０１〜５０ｎ  復号サーバ
５２１〜５２ｎ  部分復号情報生成部
６０  ネットワーク
【図１】
2005321719.tif 000014
【図２】
2005321719.tif 000015
【図３】
2005321719.tif 000016