通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法
【課題】安全かつ効率的なしきい値暗号方式を実現する。
【解決手段】ｇ∈Ｚ*Ｎ2であるｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行って暗号文を生成する。平文ｍの復元の際には、乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める。
【解決手段】ｇ∈Ｚ*Ｎ2であるｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行って暗号文を生成する。平文ｍの復元の際には、乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法に関し、特に公開鍵暗号方式やしきい値暗号方式を採用した通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法に関する。
【背景技術】
【０００２】
従来、安全な通信を行うために、公開鍵暗号方式が用いられている。公開鍵暗号方式では、公開鍵に対する復号鍵を安全に保管しておくことが大きな課題の一つになっている。この課題に対する解決方法の一つとして、種々のしきい値暗号方式が開発されている。しきい値暗号方式とは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、分散鍵を持つ複数の装置が協力しなければ、平文を復元できないようにした方式である。
【０００３】
公開鍵暗号を用いるにあたって復号鍵を如何に安全に保管しておくかということは大きな課題の一つであり、その解決方法の一つとして種々のしきい値暗号の方式が開発されてきた。ここで、しきい値暗号とは公開鍵暗号における復号のための復号鍵をいくつかの分散鍵と呼ばれるものに分散し、分散鍵をもつ複数のセンタが協力しなければ復号ができない方式である。このようなしきい値暗号の方式としては、例えば、素因数分解型の暗号方式を用いる方法(例えば、非特許文献１、非特許文献２、非特許文献３)や、離散対数型の暗号方式を用いる方法(例えば、非特許文献４)などが知られている。
【０００４】
【非特許文献１】Pierre-Alain Fouque and David Pointcheval, Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks. ASIACRYPT 2001, pp.351-368(2001)
【非特許文献２】石原武、青野博、本郷節之、四方順司、しきい値型Paillier 暗号の改良、信学技報ISEC2004-12(2004-05)、電子情報通信学会
【非特許文献３】V.Shoup and R.Gennaro, Securing Threshold Cryptosystems against Chosen Ciphertext Attack, Journal of Cryptology, vol.15,no.2, pp.75-96(2002)
【非特許文献４】J.Katz and M.Yung, “Threshold Cryptosystems Based on Factoring”, ASIACRYPT2002, Lecture Notes in Computer Science, 2501, pp.192-205, Springer-Verlag, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記非特許文献１に記載の技術は選択暗号文攻撃に対して安全性が示せるものの、暗号化の際にべき乗演算を数多く行う必要があり、暗号化の前に事前計算できないべき乗演算が存在していた（問題点１）。
また上記非特許文献２に記載の技術は暗号化のための計算量は少ないものの、安全性が選択平文攻撃のもとでのみ示され、選択暗号文攻撃のもとでの安全性が示されないという問題があった（問題点２）。また安全性の根拠をｅ乗根判定問題という、強い仮定の元ではじめて安全性が示せていた（問題点２’）。
【０００６】
また上記非特許文献３に記載の技術は素因数分解に基づく方式に比べて大きな素数を準備する必要がある。素数定理より大きい素数は数が少ないために、大きい素数を準備するということは目的の素数が見つけにくく、使える素数も少ないという問題がある（問題点３）。
さらに、非特許文献４に示される素因数分解型のしきい値暗号方式では、法Ｎのもとでの計算により暗号化及び復号を行い、選択平文攻撃に対する安全性を確保できるものの、１ビットしか暗号化できなかった。そのため、暗号化及び復号の効率が非常に悪く、実用的ではなかった（問題点４）。
【０００７】
特に、問題点１及び問題点４については、携帯性を重視する移動通信端末は高速のＣＰＵを搭載することが困難なため上記従来技術のしきい値暗号方式は、その暗号化の際の計算が非効率なため実用向きではない。
本発明の第１の目的は、上述した問題点１，２’，３，４を解決するため、複数ビットの平文を暗号化でき、決定問題に仮定を置く、素因数分解型で、かつ、事前計算により計算能力の低い移動通信端末などにおいても実用可能な、しきい値暗号化方式又は公開鍵暗号方式を採用した、通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法を提供することである。
【０００８】
本発明の第２の目的は、上述した問題点１，２，３，４を解決するため、複数ビットの平文を暗号化でき、素因数分解型で、かつ、事前計算により計算能力の低い移動通信端末などにおいても実用可能な、しきい値暗号化方式又は公開鍵暗号方式を採用した、通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の請求項１による通信システムは、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成装置と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号装置（例えば、図１〜図３中の復号サーバ５０1〜５０nに対応）と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムを実現できる。
【００１０】
本発明の請求項２による暗号化装置は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける暗号化装置を実現できる。
【００１１】
本発明の請求項３による鍵生成装置は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成手段と、前記分散鍵生成手段によって生成された分散鍵を部分復号装置に送信する分散鍵送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１２】
本発明の請求項４による鍵生成装置は、請求項３において、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする。このように構成すれば、安全性をより高めたしきい値暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
本発明の請求項５による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した鍵生成方法を実現できる。
【００１３】
本発明の請求項６による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする。このように構成すれば、安全性をより高めたしきい値暗号方式を採用した鍵生成方法を実現できる。
【００１４】
本発明の請求項７による復元装置は、復号の際に乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける復元装置を実現できる。
【００１５】
本発明の請求項８による通信方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成するステップと、
暗号文と前記分散鍵記憶手段に記憶されている分散鍵とを用いて部分復号情報を生成するステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とするステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信方法を実現できる。
【００１６】
本発明の請求項９による通信システムは、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成装置と、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成装置によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムを実現できる。
【００１７】
本発明の請求項１０による鍵生成装置は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵生成手段によって生成された秘密鍵を復元装置に送信する秘密鍵送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１８】
本発明の請求項１１による鍵生成装置は、請求項１０において、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする。このように構成すれば、安全性をより高めた公開鍵暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１９】
本発明の請求項１２による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した鍵生成方法を実現できる。
本発明の請求項１３による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする。このように構成すれば、安全性をより高めた公開鍵値暗号方式を採用した鍵生成方法を実現できる。
【００２０】
本発明の請求項１４による通信方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する鍵生成ステップと、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信方法を実現できる。
【００２１】
本発明の請求項１５による暗号化装置は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムにおける暗号化装置を実現できる。
【００２２】
本発明の請求項１６による通信システムは、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成手段と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号手段（例えば、図１〜図３中の復号サーバ５０1〜５０nに対応）と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元手段と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムを実現できる。
【００２３】
本発明の請求項１７による通信方法は、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成ステップと、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信方法を実現できる。
【００２４】
本発明の請求項１８による通信システムは、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元手段と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムを実現できる。
【００２５】
本発明の請求項１９による通信方法は、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信方法を実現できる。
【００２６】
本発明の請求項２０による暗号化方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化することを特徴とする。このように構成すれば、平文mとは無関係に決められる乱数rをあらかじめ決めてｇrをあらかじめ計算しておくことが可能となり、効率的なしきい値暗号方式を採用した通信システムにおける暗号化方式を実現でき、また乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全なしきい値暗号方式を採用した通信システムにおける暗号化方法を実現できる。
【００２７】
本発明の請求項２１による暗号化方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加することを特徴とする。このように構成すれば、平文mとは無関係に決められる乱数rをあらかじめ決めてｇrをあらかじめ計算しておくことが可能となり、さらに検証用データも大部分を事前に計算することにより効率的なしきい値暗号方式を採用した通信システムにおける暗号化方式を実現でき、また暗号文の検証用データによって選択暗号文攻撃に対する耐性が付加され、安全なしきい値暗号方式を採用した通信システムにおける暗号化方法を実現できる。
【００２８】
本発明の請求項２２による暗号復元方法は、復号の際に乱数ｒの少なくとも一部を、しきい値暗号化方式において使用する部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全なしきい値暗号方式を採用した通信システムにおける暗号復元方法を実現できる。
【００２９】
本発明の請求項２３による暗号復元方法は、復号の前に暗号文検証用データをもとに暗号文が正しく作られたものであるか確認し、その後確認が取れた場合には復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、暗号文の検証用データによって選択暗号文攻撃に対する耐性が付加され、安全なしきい値暗号方式を採用した通信システムにおける暗号復元方法を実現できる。
【００３０】
本発明の請求項２４による復元装置は、復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全な公開鍵暗号方式を採用した通信システムにおける復元装置を実現できる。
【発明の効果】
【００３１】
本発明によれば、計算能力が低い端末においても事前計算を行うことにより暗号化できるので、効率的なしきい値暗号方式又は公開鍵暗号方式を採用した通信システムを実現できるという効果がある。
また、本発明によれば、選択暗号文攻撃に対する耐性を付加するか、又は決定問題が難しいという妥当な仮定に基づくようにしたため、安全なしきい値暗号方式又は公開鍵暗号方式を採用した通信システムを実現できるという効果がある。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施の形態を、図面を参照して説明する。なお、以下の説明において参照する各図では、他の図と同等部分は同一符号によって示されている。また、以下の説明において用いられている英文字やギリシャ文字は、各実施形態において同一に意義を有している。
本発明では、合成数ＮをＮ＝ｐｑと定義し、ｐ，ｑを相異なる奇素数とし、共にΛ／２ビットとする。また、ＺN2は、０以上Ｎ2未満の整数の集合、Ｚ*N2は、ＺN2の要素のうちＮ2と互いに素な整数の集合、ＱN2は法Ｎ2のもとで平方余剰である整数でありかつＮ2と互いに素な値の集合、とする。
【００３３】
さらに、本発明では、以下の仮定１及び仮定２を前提とする。
（仮定１）
（Ｐａｒｔｉａｌ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ａｓｓｕｍｐｔｉｏｎ）
Ｎ（＝ｐｑ），ｇ∈Ｚ*N2，ｇr（ｇのｒ乗）（ｒ∈ＺN2）（Ｎ２はＮ2を意味する）
が与えられた際に、ｒと法をＮとして合同なｒ’（当然ｒと完全に等しくてもよい）を求めることはほとんどできない。なお、「ほとんどできない」とは、この問題が何題か出題された場合、正解率が０に限りなく近いいう意味である。
ここで、ｇの位数を０でないＮの倍数とする。
【００３４】
（仮定２）
（Ｄｅｃｉｓｉｏｎａｌ Ｓｍａｌｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ Ａｓｓｕｍｐｔｉｏｎ）
Ｎ（＝ｐｑ），Ｍ（＝ｐ2ｑ2）,ｇ∈Ｚ*N2，ｇ2∈Ｚ*M2，ｇr（ｇのｒ乗）（ｒ∈ＺN2）（Ｎ２はＮ2を意味し、Ｍ２はＭ2を意味する）
が与えられた際に、さらに以下に定義するＺ0もしくはＺ1を与えた際に、その予想が当たる確率は１／２とほとんど同じである（１／２との差が限りなく０に近い）。
Ｚ0＝ｇ2rｍｏｄＭ2，Ｚ1＝Ｒ（∈Ｚ*M2）（Ｍ２はＭ2を意味する）
ここで、ｇの位数を０でないＮの倍数、ｇ2の位数を０でないＮ2の倍数とする。ただし、Ｎ＞Ｎ2とするが、その差は無視できるほどしか差が無いとする。
【００３５】
（第１実施形態）
〔通信システム〕
図１に示すように、通信システム１００は、暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０1〜５０nと、ネットワーク６０とを備える。暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０1〜５０nは、ネットワーク６０を介して、情報を送受信する。
【００３６】
鍵生成サーバ３０は、μビットの平文ｍの暗号化に用いる公開情報（ｇ，Ｎ，θ，Ｈ１）と、暗号文Ｃの復号に用いる秘密情報Ｌβとその分散鍵ｓを生成する鍵生成装置である。鍵生成サーバ３０は、鍵生成部３１と、鍵データベース３２と、送信部３３とを備える。鍵生成部３１は、公開情報（ｇ，Ｎ，θ，Ｈ１）と、それに対する秘密情報Ｌβと、秘密情報Ｌβを複数に分散した分散鍵ｓとを生成する。鍵生成部３１は、ｎ個の分散鍵ｓを生成する。さらに部分復号情報が正しいことを検証するためのｎ個の検証鍵ｖｋとその生成元ｖを生成する。各検証鍵を区別するときには、ｉ番目の検証鍵を「ｖｋｉ」と表す。よって、各分散鍵を区別するときには、ｉ番目の分散鍵を「ｓi」と表す。このように検証鍵ｖｋと分散鍵ｓには、１〜ｎまでの番号が付与される。なお、復号サーバの数である「ｎ」と、（ｔ，ｎ）しきい値暗号方式において復号のために必要な部分復号情報の数を表す「ｔ」は、公開されている情報である。これら「ｎ」及び「ｔ」は、復元端末２０に送信される。
【００３７】
鍵データベース３２は、公開情報（ｇ，Ｎ，θ，Ｈ１）を記憶する。送信部３３は、鍵生成部３１が生成した公開情報（ｇ，Ｎ，θ，Ｈ１）を暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信する。また、検証鍵ｖｋ１〜ｖｋｎを少なくとも復元端末２０に送信する。また、送信部３３は、分散鍵ｓ1〜ｓnを、復号サーバ５０1〜５０nに送信する。このような鍵生成サーバ３０は、コンピュータを、鍵生成部３１と、鍵データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００３８】
暗号化端末１０は、平文ｍを暗号化して暗号文Ｃを生成する暗号化装置である。暗号化端末１０は、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５とを備えている。
受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信する。記憶部１５は、暗号文生成部１２が事前に計算するＨ１（ｒｍｏｄＮ）とｕ＝ｇrｍｏｄＮ2とを記憶する。受信部１１は、平文ｍを受信し、暗号文生成部１２に入力してもよい。
【００３９】
入力部１４は、外部から入力される平文ｍを取得し、暗号文生成部１２に入力する。暗号文生成部１２は、事前計算され記憶部１５に記憶されているＨ１（ｒｍｏｄＮ）及びｕ＝ｇrｍｏｄＮ2を用いて平文ｍを暗号化する。暗号文生成部１２は、暗号文Ｃを生成する際に、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する。暗号文生成部１２は、入力部１４や受信部１１から平文ｍを取得する。なお、ｒ∈UＺN2（Ｎ２はＮ2を意味する）である。ここで、「Ｘ∈UＧ」は、集合Ｇから一様な確率で要素Ｘを選択することを表す。
【００４０】
暗号文生成部１２は、以下に示す式（１）及び式（２）を計算することにより、平文ｍを暗号化して暗号文Ｃ（ｃ，ｕ）を生成することが好ましい。
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ …（１）
ｕ＝ｇrｍｏｄＮ2 …（２）
ハッシュ関数Ｈ１は、ＺN→｛０，１｝μである。なお、上記の「＊」は排他的論理和を示している。以後の説明においても同様である。
【００４１】
送信部１３は、暗号文生成部１２が生成した暗号文Ｃを、暗号文管理サーバ４０に送信する。記憶部１５は、後述するように暗号化する際に部分的に事前計算した結果を、一旦記憶する。このような暗号化端末１０は、コンピュータを、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００４２】
暗号文管理サーバ４０は、暗号文Ｃを暗号化端末１０から受信し、暗号文Ｃを各装置に提供する暗号文管理装置である。暗号文管理サーバ４０は、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。受信部４１は、暗号化端末１０から暗号文Ｃを受信する。又、受信部４１は、復元端末２０や復号サーバ５０1〜５０nから、暗号文Ｃの要求を受信する。更に、受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信する。
【００４３】
暗号文データベース４３は、暗号文Ｃを記憶する。送信部４４は、暗号文Ｃを復元端末２０、復号サーバ５０1〜５０nに送信する。このような暗号文管理サーバ４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００４４】
復号サーバ５０1〜５０nは、部分復号情報σを生成する。部分復号情報σは、暗号文Ｃから平文ｍを復元する際に用いる情報であり、復元端末２０が平文ｍの復元をするために必要な情報である。部分復号情報σは、暗号文Ｃと分散鍵ｓとを用いた計算を行うことにより、即ち、暗号文Ｃを分散鍵ｓを用いて部分的に復号することにより得られる情報である。複数の復号サーバ５０1〜５０nがそれぞれ異なる分散鍵ｓを用いて部分復号情報σを生成することにより、複数の部分復号情報σが生成される。分散鍵ｓiを用いて生成された部分復号情報は、「σi」と表す。よって、複数の部分復号情報σとして、分散鍵ｓ1〜ｓnを用いて部分復号情報σ1〜σnが生成される。このように部分復号情報σには、１〜ｎまでの番号が付与される。又、復号サーバ５０1〜５０nにも、１〜ｎまでの番号が付与される。なお、Δ＝ｎ！＝ｎ・（ｎ−１）・（ｎ−２）…２・１と定義する。
【００４５】
復号サーバ５０1〜５０nはそれぞれ、受信部５１1〜５１nと、部分復号情報生成部５２1〜５２nと、送信部５３1〜５３nとを備える。受信部５１1〜５１nは、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）と分散鍵ｓとを受信する。又、受信部５１1〜５１nは、復元端末２０から部分復号情報σの要求（以下「復号要求」という）を受信する。更に、受信部５１1〜５１nは、暗号文管理サーバ４０から暗号文Ｃを受信する。
【００４６】
部分復号情報生成部５２1〜５２nのうち、暗号文Ｃを復号することに同意した部分復号情報生成部は、σi≡ｕ2ΔSiｍｏｄＮ2を復元端末２０に送信する。σi≡ｕ2ΔSiｍｏｄＮ2を受信した復元端末２０は、上記に同意した部分復号情報生成部から送られてきた情報が正しいものかどうか確認する。この確認においては、σi2とｖｋiがそれぞれｕ4Δ、ｖΔを底として同じ対数を持つかどうかを確認する。復元端末２０は、σiが正しいシェアであることを確認できなかった場合はｉｎｖａｌｉｄ ｓｙｍｂｏｌを出して処理を終了し、確認できた場合は以下の計算を行う。
【００４７】
【数１】
ただし、
【００４８】
【数２】
である。そして、ｒｍｏｄＮ並びに式（１）及び式（２）により、平文ｍが得られる。式（３）、式（４）において、「Ｓ」は、復元端末２０からの復号要求を受け入れた復号サーバ５０1〜５０nの番号の集合を表す。
【００４９】
上記のような復号サーバ５０1〜５０nは、コンピュータを、受信部５１1〜５１nと、部分復号情報生成部５２1〜５２nと、送信部５３1〜５３nとして機能させるためのプログラムを、コンピュータが実行することにより実現できる。
復元端末２０は、暗号文Ｃから平文ｍを復元する復元装置である。復元端末２０は、受信部２１と、平文復元部２２と、送信部２３と、出力部２４とを備える。
受信部２１は、複数の部分復号情報σを、複数の復号サーバ５０1〜５０nから受信する。又、受信部２１は、暗号文Ｃを暗号文管理サーバ４０から受信する。更に、受信部２１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）と検証鍵ｖｋ1〜ｖｋnを受信する。
【００５０】
平文復元部２２は、複数の部分復号情報σを用いて暗号文Ｃから平文ｍを復元する。平文復元部２２は、復元した平文ｍを出力部２４に出力する。送信部２３は、暗号文Ｃの要求や、復号要求を送信する。このような復元端末２０は、コンピュータを、受信部２１と、平文復元部２２と、送信部２３と、出力部２４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００５１】
次に、図１、図２を用いて、平文ｍの暗号化から復元において通信システム１００が行う処理を詳細に説明する。通信システム１００では、（ｔ，ｎ）しきい値暗号方式により復号を行う。（ｔ，ｎ）しきい値暗号方式とは、ｎ個の分散鍵ｓ1〜ｓnを用いて生成されるｎ個の部分復号情報σ1〜σnのうち、ｔ個の部分復号情報を用いれば、平文ｍが復元できるしきい値暗号方式である。よって、「ｔ」は、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報σの数を表す。
【００５２】
通信システム１００が、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する暗号方式を用いる場合を説明する。鍵生成サーバ３０の鍵生成部３１は、まず、２つの大きなΛ／２ビットの強い素数ｐ，ｑを選択し、その積を計算して、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【００５３】
ここで、Ｌ＝ｐ’ｑ’を計算して秘密にしておく。また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＮ2を定め、ｇを公開する。さらに、値β∈Ｚ*Nをランダムに選択し、θ＝ａＬβｍｏｄＮを計算する。θを公開し、暗号化の際用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μも公開する。
次に、鍵生成部３１は、公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する秘密情報Ｌβを生成する。秘密情報Ｌβは、
【００５４】
【数３】
を満たす。更に、鍵生成部３１は、秘密情報Ｌβを複数に分散して複数の分散鍵ｓ、即ち、ｎ個の分散鍵ｓ1〜ｓnを生成する。分散鍵ｓ1〜ｓnは、相互に異なる秘密情報である。
【００５５】
本実施形態では、分散鍵ｓ1〜ｓnの個数ｎは、復号サーバ５０1〜５０nの数と等しい。しかし、一つの復号サーバが複数の分散鍵を用いてもよい。よって、分散鍵ｓの個数と復号サーバの数は、必ずしも一致するとは限らない。分散鍵ｓ1〜ｓnの個数と復号サーバ５０1〜５０nの数が一致する本実施形態では、復号サーバ５０ｉが、分散鍵ｓiを用いる。例えば、鍵生成部３１は、Shamirにより提案された方法等を用いて、秘密情報Ｌβを複数に分散できる。
【００５６】
具体的には、鍵生成部３１は、ａi∈U｛０，１，・・・，ＬＮ−１｝、（ｉ＝１，２，・・・，ｔ−１）を乱数として選択し、さらに、ａ0＝Ｌβとして定義して分散鍵ｓiを生成する。又、「ＺX」とは、０以上Ｘ未満の整数の集合（ＺX＝Ｚ／ＸＺ）を表す。この場合、鍵生成部３１は、以下に示す式（６）を計算することにより、複数の分散鍵ｓ1〜ｓnを生成する。鍵生成部３１は、式（６）を用いて、ｓi＝ｆ（ｉ）ｍｏｄＬＮを計算することにより分散鍵ｓiを生成する。
【００５７】
【数４】
【００５８】
鍵生成部３１は、生成した複数の分散鍵ｓ1〜ｓnを、送信部３３に入力する。
更に、鍵生成部３１は、部分復号情報σが正しく暗号文Ｃを部分的に復号したものか否かを判定する際に用いる複数の検証鍵ｖｋを生成する。鍵生成部３１は、分散鍵ｓ1〜ｓnと同数のｎ個の検証鍵ｖk1〜ｖｋnを生成する。鍵生成部３１は、以下に示す式（７）を計算することにより検証鍵ｖｋ1〜ｖｋnを生成する。
【００５９】
【数５】
【００６０】
式（７）において、νはＱN2（Ｎ２はＮ2を意味する）の部分群の生成元である。「ＱX」は、法Ｘのもとで平方余剰かつＸと互いに素な整数の集合を表す。そのため、「ＱX」は、Ｚ*Xから要素を一つ取得し、２乗した値の集合となる。鍵生成部３１は、生成した複数の検証鍵ｖｋ1〜ｖｋnと、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νの合計ｎ＋１個の値を、送信部３３に入力する。
【００６１】
送信部３３は、図２に示すように、素数ｐ，ｑを秘密にしたまま復元端末２０に対応する公開情報（ｇ，Ｎ，θ，Ｈ１）だけを、暗号化端末１０、暗号文管理サーバ４０、復元端末２０に送信する。暗号化端末１０の受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信し、暗号文生成部１２に入力する。暗号文管理サーバ４０の受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信し、暗号文管理部４２に入力する。
【００６２】
更に、送信部３３は、公開情報（ｇ，Ｎ，θ，Ｈ１）と複数の分散鍵ｓ1〜ｓnとを対応付けて、複数の復号サーバ５０1〜５０nに送信する。このとき、送信部３３は、複数の分散鍵ｓ1，・・・，ｓi，・・・，ｓnをそれぞれ、復号サーバ５０1，・・・，５０i，・・・，５０nに送信する。復号サーバ５０1〜５０nの受信部５１1〜５１nは、鍵生成サーバ３０から、公開情報（ｇ，Ｎ，θ，Ｈ１）と分散鍵ｓ1〜ｓnを受信し、部分復号情報生成部５２1〜５２nに入力する。送信部３３は、このようにして、複数の分散鍵ｓを復号装置に送信する鍵送信部として機能する。
【００６３】
このように、送信部３３が、ｕからｒの少なくとも一部を取出す際必要となる秘密情報Ｌβを分散した分散鍵ｓ1〜ｓnを、複数の復号サーバ５０1〜５０nに分散して提供する。更に、鍵生成サーバ３０自身も秘密情報Ｌβは、鍵データベース３２に格納しない。これにより、秘密情報Ｌβは一箇所に管理されず、複数の復号サーバ５０1〜５０nによって分散管理される。
【００６４】
又、送信部３３は、公開情報（ｇ，Ｎ，θ，Ｈ１）と検証鍵ｖｋ1〜ｖｋnと、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νとを対応付けて、復元端末２０に送信する。復元端末２０の受信部２１は、鍵生成サーバ３０から、公開情報（ｇ，Ｎ，θ，Ｈ１）、検証鍵ｖｋ1〜ｖｋn、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νを受信し、平文復元部２２に入力する。
【００６５】
暗号化端末１０の暗号文生成部１２は、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，θ，Ｈ１）を用いて暗号化する。具体的には、暗号文生成部１２は、値ｇに対して乱数ｒをｇrｍｏｄＮ2として隠し、ｒの少なくとも一部の情報を用いて平文ｍをもとに暗号文Ｃを生成する。例えば、暗号文生成部１２は、上記式（１）及び上記式（２）を計算することにより、平文ｍを暗号化し、暗号文Ｃを生成する。平文ｍは、暗号化端末１０が暗号化して秘密にしたい情報である。本実施形態における平文ｍは、複数の分散鍵ｓ1〜ｓnを用いない限り、暗号文Ｃから平文ｍを復号できないようにすることにより、暗号化端末１０が分散管理したい情報である。
【００６６】
暗号文生成部１２は、乱数ｒを、ＺN2から選択する。暗号文生成部１２は、生成した暗号文Ｃを送信部１３に入力する。送信部１３は、図２に示すように、暗号文Ｃと暗号化に用いた公開鍵を暗号文管理サーバ４０に送信する。
暗号文管理サーバ４０の受信部４１は、図２に示すように、暗号化端末１０から暗号文Ｃを受信する。受信部４１は、受信した暗号文Ｃを暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃを、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，θ，Ｈ１）に対応付けて、暗号文データベース４３に格納する。
【００６７】
その後、復元端末２０の平文復元部２２が、公開情報（ｇ，Ｎ，θ，Ｈ１）をもとに作成した暗号文Ｃの要求と、公開情報（ｇ，Ｎ，θ，Ｈ１）と秘密情報をもとに作成した部分復号情報σを要求する復号要求を生成し、送信部２３に入力する。送信部２３は、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。暗号文管理サーバ４０の受信部４１は、復元端末２０から暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃの要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する暗号文Ｃを、暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けられた暗号文Ｃを復元端末２０に送信する。このように公開情報（ｇ，Ｎ，θ，Ｈ１）は、暗号文Ｃを識別するための識別データとして用いることができる。
【００６８】
又、送信部２３は、復号要求を複数の復号サーバ５０1〜５０nに送信する。このとき、送信部２３は、復号要求を全ての復号サーバ５０1〜５０nにブロードキャストにより送信してもよく、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報の数ｔだけ復号サーバを選択し、送信してもよい。
復号サーバ５０1〜５０nの受信部５１1〜５１nは、復号要求を受信し、部分復号情報生成部５２1〜５２nに入力する。部分復号情報生成部５２1〜５２nは、復号要求を受け入れた場合、復号要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）を指定した暗号文Ｃの要求を生成し、送信部５３1〜５３nに入力する。送信部５３1〜５３nは、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。尚、部分復号情報生成部５２1〜５２nは、復号要求を拒否してもよい。
【００６９】
暗号文管理サーバ４０の受信部４１は、復号サーバ５０1〜５０nから暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、指定された公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する暗号文Ｃを暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けられた暗号文Ｃを復号サーバ５０1〜５０nに送信する。
【００７０】
復号サーバ５０1〜５０nの受信部５１1〜５１nは、暗号文Ｃを受信し、部分復号情報生成部５２1〜５２nに入力する。部分復号情報生成部５２1〜５２nはそれぞれ、受信した暗号文Ｃと分散鍵ｓ1〜ｓnを用いて、σi≡ｕ2ΔSiｍｏｄＮ2を計算することにより、暗号文Ｃを部分的に復号して部分復号情報σ1〜σnを生成する。部分復号情報生成部５２1〜５２nは、復号要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する分散鍵ｓ1〜ｓnを用いる。
【００７１】
例えば、復号サーバ５０ｉの場合、暗号文Ｃと分散鍵ｓiを用いて、
σi＝ｕ2ΔSiｍｏｄＮ2
を計算することにより、部分復号情報σiを生成する。
部分復号情報生成部５２は、生成した部分復号情報σ1〜σnを送信部５３1〜５３nに入力する。送信部５３1〜５３nはそれぞれ、図２に示すように、部分復号情報σ1〜σnを復元端末２０に送信する。尚、全ての復号サーバ５０1〜５０nが、部分復号情報σ1〜σnの生成、送信を行う必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを生成し、復元端末２０に送信すればよい。
【００７２】
復元端末２０の受信部２１は、複数の復号サーバ５０1〜５０nから複数の部分復号情報σ1〜σnを受信する。受信部２１は、受信した複数の部分復号情報σ1〜σnを平文復元部２２に入力する。このようにして、受信部２１は、複数の復号装置から複数の部分復号情報σを受信する復号情報受信部として機能する。尚、受信部２１は、全ての復号サーバ５０1〜５０nから全ての部分復号情報σ1〜σnを受信する必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを受信する。
【００７３】
平文復元部２２は、複数の部分復号情報σ1〜σnを用いて、暗号文Ｃの一部であるｕから平文ｍを復元する。平文復元部２２は、まず、部分復号情報σが正しく復号されたものか否かを判定する。平文復元部２２は、暗号文Ｃの一部であるｕの４Δ乗「ｕ4Δ」を底とした部分復号情報の２乗「σ2」の対数と、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元のΔ乗「νΔ」を底とした検証鍵ｖｋの対数が等しいか否かを判定する。平文復元部２２は、対数が等しい場合には、部分復号情報σが正しく復号されたものであると判定し、対数が異なる場合には、部分復号情報σは正しく復号されていないと判定する。
【００７４】
平文復元部２２は、複数の部分復号情報σ1〜σnについて、それぞれ検証鍵ｖｋ1〜ｖｋnを用いて判定を行う。対数が等しいか否かの判定には、一般的な方法、例えば、文献「ＦＰＳ００：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」に記載されている方法を用いることができる。
【００７５】
平文復元部２２は、正しく復号されていると判定した部分復号情報σ1〜σnを用いて、まず、平文ｍの暗号化に用いた乱数ｒの情報の一部を計算する。尚、平文復元部２２は、全ての復号サーバ５０1〜５０nからの全ての部分復号情報σ1〜σnを用いる必要はなく、（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを選択し、用いる。
平文復元部２２は、まず、上述した式（３）を計算する。平文復元部２２は、文献「ＳＨｏ００：victor Shoup， “Practical Threshold Signatures”，EUROCRYPT，Lecture Notes in Computer Science， pp.207-220，2000」と同様に、式（４）に示す条件で式（３）を計算する。
【００７６】
式（３）、式（４）において、「Ｓ」は、復元端末２０からの復号要求を受け入れた復号サーバ５０1〜５０nの番号の集合を表す。つまり、例えば、番号１、２、５が付与された復号サーバが復号要求を受け入れた場合には、Ｓ＝｛１，２，５｝と記述される。但し、集合Ｓに含まれる番号の数は、（ｔ，ｎ）しきい値暗号方式において部分復号情報σが必要な数ｔに限定される。又、式（３）、式（４）における「λ」は補間係数である。「λ」は、式（４）において、ｆ（０）＝ａ0を計算するために用いられ、式（８）に示す関係を持つ。
【００７７】
【数６】
【００７８】
又、「Πj∈S/[i]（ｉ−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての番号に関してｉから引き算した値を考え、それら全ての積を示す。同様に、「Πj∈S/[i]（−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての数字に関して、符号の正負を逆にした値の積を示す。
次に、平文復元部２２は、計算した乱数ｒの少なくとも一部を用いて、暗号文Ｃから平文ｍを復元する。具体的には、平文復元部２２は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式、例えば、上記式（３）に基づいてｒｍｏｄを算出し、算出したｒｍｏｄと受信した暗号文Ｃとを式（１）に代入して、平文ｍを復元する。以上のようにして、復元端末２０は、復号サーバ５０1〜５０nから受信した複数の部分復号情報σ1〜σnに基づいて、秘密の情報である平文ｍを復元できる。
【００７９】
尚、平文復元部２２は、部分復号情報σが正しく復号されていないと判定した場合には、その部分復号情報σを送信した復号サーバに対する部分復号情報の拒否通知を生成し、送信部２３に入力する。送信部２３は、拒否通知を復号サーバに送信し、処理を終了する。もしくは、平文復元部２２は、他の有効な部分復号情報をもとに秘密情報を復元する。
【００８０】
〔安全性強化のための変形例〕
ところで、上記の通信システムにおいて、鍵生成部３１による鍵生成、暗号化端末１０による暗号化、復元端末２０による復号において、上記とは異なる、以下の処理を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
（１）鍵生成部３１による鍵生成においては、以下の事項が異なる。
鍵生成部３１は、公開情報（ｇ，ｇ2，Ｎ，Ｍ，θ，Ｈ１，Ｈ２）を生成する。まず、４つの大きなΛ／２ビットの強い素数ｐ，ｐ2，ｑ，ｑ2を用い、合成数Ｎ＝ｐｑ，Ｍ＝ｐ2ｑ2を作成し、ｐ，ｐ2，ｑ，ｑ2は秘密にしたままＮ，Ｍを公開情報として公開する。ここで、Ｌ＝ｐ’ｑ’，Ｌ2＝ｐ2’ｑ2’も計算して秘密にしておく。なお、Ｎ＞Ｍとする。なお、Ｎ＜Ｍの場合も同様に行える。
【００８１】
また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＭを、ａ2∈ＺM，ｂ2∈Ｚ*Mをもとにｇ2＝（１＋ａ2Ｍ）ｂ2MｍｏｄＭ2を、それぞれ定め、ｇ，ｇ2を公開する。さらに、値β, β2∈Ｚ*Nをランダムに選択し、θ＝ａＬβｍｏｄＮ, θ2＝ａ2Ｌ2β2ｍｏｄＭを計算しておく。また、暗号化の際に用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μとＨ２：｛０，１｝μ×ＺN2×ＺN2×ＺM2×ＺM2→｛０，１｝Bも公開する。ここで復号サーバ５０1〜５０nへ渡す分散鍵はそれぞれ一つとするほかに、それぞれ二つ渡す方法も考えられる。この場合には、鍵生成部３１は、Shamirにより提案された方法等を用いて、秘密情報Ｌ2β2も複数に分散する。
【００８２】
具体的には、鍵生成部３１は、bi∈U｛０，１，・・・，Ｌ2M−１｝、（ｉ＝１，２，・・・，ｔ−１）を乱数として選択し、さらに、b0＝Ｌ2β2として定義して分散鍵ｔiを生成する。この場合、鍵生成部３１は、以下に示す式（６）’を計算することにより、複数の分散鍵t1〜tnを生成する。鍵生成部３１は、式（６）’を用いて、ti＝ｆ2（ｉ）ｍｏｄＬ2Mを計算することにより分散鍵tiを生成する。
【００８３】
【数７】
【００８４】
鍵生成部３１は、生成した複数の分散鍵t1〜tnも、送信部３３に入力する。
更に、鍵生成部３１は、部分復号情報σ’≡ｕ’2ΔtiｍｏｄＭ2が正しく暗号文Ｃを部分的に復号したものか否かを判定する際に用いる複数の検証鍵ｗｋを生成する。鍵生成部３１は、分散鍵ｔ1〜tnと同数のｎ個の検証鍵wk1〜wｋnを生成する。鍵生成部３１は、以下に示す式（７）’を計算することにより検証鍵wｋ1〜wｋnを生成する。
【００８５】
【数８】
【００８６】
式（７）’において、ν2はＱM2（Ｍ２はＭ2を意味する）の部分群の生成元である。
（２）暗号化端末１０による暗号化においては、以下の事項が異なる。
式（１）及び式（２）の代わりに、次の式（９）を用いる。ただし、ｓ∈ＺN4（Ｎ４はＮ4を意味する）とする。
【００８７】
【数９】
【００８８】
（３）復号においては、以下の事項が異なる。
暗号文を復号する前に、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０nの少なくとも１箇所において暗号文の検証を行う。この場合、少なくとも復元端末２０において、暗号文の検証を行うことが望ましい。
ここで復号サーバ５０1〜５０nへ渡す分散鍵をそれぞれ二つ渡す方法の場合にはuに関して行う部分復号と結合をu’についても同様に行い、復元結果がともにrかどうかの確認をする。もしも同じにならない場合は不正な暗号文として認識する。
ただし各復号サーバが通信して納得した上であればuかu’どちらか一方だけ復号してｒを求めても構わない。
以上のように、復号を行う前に、少なくとも復元端末２０が暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【００８９】
〔通信方法〕
次に、通信システム１００を用いて行う通信方法の手順を説明する。まず、鍵生成サーバ３０が、公開情報（ｇ，Ｎ，θ，Ｈ１）、複数の分散鍵ｓ1〜ｓn、複数の検証鍵ｖｋ1〜ｖｋnを生成する（Ｓ１０１）。鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）を復元端末２０、復号サーバ５０1〜５０n、暗号文管理サーバ４０、暗号化端末１０に送信する（Ｓ１０２〜Ｓ１０５）。鍵生成サーバ３０は、複数の分散鍵ｓ1〜ｓnを復号サーバ５０1〜５０nに送信する（Ｓ１０６）。鍵生成サーバ３０は、少なくとも復元端末２，０にｖｋ1〜ｖｋn，ｖを送信する（Ｓ１０７）。
【００９０】
暗号化端末１０は、例えば、式（２）を用い、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、式（１）を用い、乱数ｒの少なくとも一部を用いて平文ｍを暗号化し、暗号文Ｃを生成する（Ｓ１０８）。暗号化端末１０は、生成した暗号文Ｃを暗号文管理サーバ４０に送信する（Ｓ１０９）。暗号文管理サーバ４０は、受信した暗号文Ｃを暗号文データベース４３に格納する（Ｓ１１０）。
【００９１】
復元端末２０は、暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ１１１）。暗号文管理サーバ４０は、復元端末２０の要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復元端末２０に送信する（Ｓ１１２）。
復元端末２０は、復号サーバ５０1〜５０nに復号要求を送信する（Ｓ１１３）。復号サーバ５０1〜５０nは暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ１１４）。
【００９２】
暗号文管理サーバ４０は、復号サーバ５０1〜５０nの要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復号サーバ５０1〜５０nに送信する（Ｓ１１５）。
復号サーバ５０1〜５０nはそれぞれ、暗号文Ｃと分散鍵ｓ1〜ｓnとを用いて、σi≡ｕ2ΔSiｍｏｄＮ2を計算することにより、部分復号情報σ1〜σnを生成する（Ｓ１１６）。 復号サーバ５０1〜５０nはそれぞれ、生成した部分復号情報σ1〜σnを復元端末２０に送信する（Ｓ１１７）。
【００９３】
復元端末２０は、受信した部分復号情報σ1〜σnが正しく復号されたものか否かを、検証鍵ｖｋ1〜ｖｋnを用いて判定する（Ｓ１１８）。復元端末２０は、部分復号情報σ1〜σnが正しく復号されたものと判定した場合には、部分復号情報σ1〜σnを用いて乱数ｒの少なくとも一部の情報を計算する。そして、復元端末２０は、受信した暗号文Ｃと、計算した乱数ｒの少なくとも一部の情報を、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式に代入することにより、平文ｍを復元する（Ｓ１１９）。このようにして、暗号化端末１０と、複数の復号サーバ５０1〜５０nとの間で、秘密の情報である平文ｍを管理できる。尚、ステップ（Ｓ１０３）、（Ｓ１１５）に代えて、復元端末２０から復号サーバ５０1〜５０nに公開情報（ｇ，Ｎ，θ，Ｈ１）や暗号文Ｃを送信するようにしてもよい。
【００９４】
なお、上述した安全性強化のための変形例の場合には、上記のステップＳ１１０、ステップＳ１１６、ステップＳ１１８のうち少なくとも１つのステップにおいて、暗号文の検証を行うことになる。この場合、少なくとも、復号サーバ５０1〜５０nが行うステップＳ１１６において、暗号文の検証を行うことが望ましい。このように、復号を行う前に、少なくとも復元端末において、暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【００９５】
〔効果〕
本実施形態の通信システム１００、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０、複数の復号サーバ５０1〜５０n及び通信方法によれば、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、通信システム１００では、複数ビットの平文ｍを、ｇrを計算し、Ｈ１（ｒｍｏｄＮ）によって暗号化し、安全性を確保できる。
【００９６】
上記の暗号化処理において、ｕ＝ｇrｍｏｄＮ2、Ｈ１（ｒｍｏｄＮ）の部分を事前に計算し、暗号化する際はｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍのみ計算すれば良いので、暗号化する際の計算量を少なくできることが分かる。つまり、通信システム１００によれば、部分的に事前計算するので、処理効率の良いしきい値暗号方式を実現することができる。
【００９７】
特に、暗号化端末１０や復元端末２０が、携帯性を重視する移動通信端末のように高速のＣＰＵを搭載することが困難な装置の場合においても、計算量が少ない本発明のしきい値暗号方式であれば利用可能である。さらに安全性強化のための変形例においては、素因数分解型のしきい値暗号ではよくあるように分散鍵を一つの復号サーバに二つ持たせるといったことが必要なく、変形例においては分散鍵の個数が減っているため記憶容量が少ない場合においても本発明のしきい値暗号方式であれば適用可能である。このように、本発明のしきい値暗号方式は、計算能力が低い暗号化装置や復号装置、復元装置、あるいは、安全性を高めた場合であっても記憶容量が低い暗号化装置や復号装置、復元装置においても、利用可能であり、暗号化と復号を効率的に行うことができる。
【００９８】
なお、上述した、安全性強化のための変形例を採用した場合、暗号文の検証を行うためのデータについてもほぼ事前計算できるので、安全性を強化してもやはり処理効率の良いしきい値暗号方式を実現することができる。
また、例えば、Ｈ１（ｒｍｏｄＮ）＊ｍとしてｍを暗号化することにより、ハッシュ関数の性質からｍを求めるためには、ｒｍｏｄＮを一意に決定する必要性がある。このため、本実施形態を採用すれば、決定問題に根拠をおくかもしくは選択暗号文攻撃に対しても安全性を確保でき、安全性を付与したしきい値暗号方式を実現することができる。
【００９９】
ところで、本実施形態の通信システム１００は、種々の変更が可能である。例えば、暗号化端末１０、復号サーバ５０1〜５０nの一部、又は、復元端末２０が、鍵生成サーバ３０の機能の一部又は全部を備え、鍵生成装置として機能してもよい。この他、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０、復号サーバ５０1〜５０nのそれぞれの全部又は一部の機能のうち、少なくとも２つの機能を有する装置を通信システム１００に備えてもよい。なお、通信システム１００は、暗号文管理サーバ４０、暗号化端末１０を複数備えてもよい。
【０１００】
又、上記実施の形態では、暗号文Ｃを識別するための識別データとして公開情報（ｇ，Ｎ，θ，Ｈ１）を用いているが、公開情報以外のデータを識別データとして用いることができる。又、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）の暗号文管理サーバ４０への送信を省略してもよい。尚、この場合には、暗号文管理サーバ４０は、暗号文Ｃの要求と暗号文Ｃとを対応付けるための識別データとして、公開情報（ｇ，Ｎ，θ，Ｈ１）以外のものを暗号文Ｃに付与し、その識別データを復元端末２０へ与え、その識別データに対応付けて暗号文Ｃを暗号文データベース４３に格納する。
【０１０１】
あるいは、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）を、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０nに送信せずに、これらの装置が自由に閲覧して取得できるようにしてもよい。又、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０n等が、予め公開情報（ｇ，Ｎ，θ，Ｈ１）や分散鍵ｓ1〜ｓn、検証鍵ｖｋ1〜ｖｋn等を保持することにより、鍵生成サーバ３０を省略してもよい。
又、復号サーバ５０1〜５０nが完全に信用できる場合には検証鍵を用いなくてもよい。その場合には、復元端末２０は、部分復号情報σが正しいか否かの判定を行わないため、より高速に処理を行え、効率を向上できる。
【０１０２】
（第２実施形態）
〔通信システム〕
図４に示すように、公開鍵通信システム２００は、暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、ネットワーク６０とを備える。暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０は、ネットワーク６０を介して、情報を送受信する。
鍵生成サーバ３０は、μビットの平文ｍの暗号化に用いる公開情報（ｇ，Ｎ，Ｈ１）と、暗号文Ｃの復号に用いる秘密鍵を生成する鍵生成装置である。鍵生成サーバ３０は、鍵生成部３１と、鍵データベース３２と、送信部３３とを備える。鍵生成部３１は、公開情報（ｇ，Ｎ，Ｈ１）と、それに対する秘密鍵とを生成する。
【０１０３】
鍵データベース３２は、公開情報（ｇ，Ｎ，Ｈ１）を記憶する。送信部３３は、鍵生成部３１が生成した公開情報（ｇ，Ｎ，Ｈ１）を暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信する。また、送信部３３は、秘密鍵２Ｌを復元端末２０に送信する。このような鍵生成サーバ３０は、コンピュータを、鍵生成部３１と、鍵データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１０４】
暗号化端末１０は、平文ｍを暗号化して暗号文Ｃを生成する暗号化装置である。暗号化端末１０は、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５とを備えている。
受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。記憶部１５は、暗号文生成部１２が事前に計算するＨ１（ｒｍｏｄＮ）とｕ＝ｇrｍｏｄＮ2とを記憶する。受信部１１は、平文ｍを受信し、暗号文生成部１２に入力してもよい。
【０１０５】
入力部１４は、外部から入力される平文ｍを取得し、暗号文生成部１２に入力する。暗号文生成部１２は、事前計算され記憶部１５に記憶されているＨ１（ｒｍｏｄＮ）及びｕ＝ｇrｍｏｄＮ2を用いて平文ｍを暗号化する。暗号文生成部１２は、暗号文Ｃを生成する際に、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する。暗号文生成部１２は、入力部１４や受信部１１から平文ｍを取得する。暗号文生成部１２は、上述した式（１）及び式（２）を計算することにより、平文ｍを暗号化して暗号文Ｃ（ｃ，ｕ）を生成することが好ましい。
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ …（１）
ｕ＝ｇrｍｏｄＮ2 …（２）
ハッシュ関数Ｈ１は、ＺN→｛０，１｝μである。なお、上記の「＊」は排他的論理和を示している。
【０１０６】
送信部１３は、暗号文生成部１２が生成した暗号文Ｃを、暗号文管理サーバ４０に送信する。記憶部１５は、後述するように暗号化する際に部分的に事前計算した結果を、一旦記憶する。このような暗号化端末１０は、コンピュータを、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１０７】
暗号文管理サーバ４０は、暗号文Ｃを暗号化端末１０から受信し、暗号文Ｃを各装置に提供する暗号文管理装置である。暗号文管理サーバ４０は、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。受信部４１は、暗号化端末１０から暗号文Ｃを受信する。又、受信部４１は、復元端末２０から、暗号文Ｃの要求を受信する。更に、受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。
【０１０８】
暗号文データベース４３は、暗号文Ｃを記憶する。送信部４４は、暗号文Ｃを復元端末２０に送信する。このような暗号文管理サーバ４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
復元端末２０では以下の式を用いて復号化処理を行う。
ｕ2LｍｏｄＮ2＝（１＋２ｒａＬＮ）
である。そして、ｒｍｏｄＮ並びに式（１）及び式（２）により、平文ｍが得られる。
【０１０９】
復元端末２０は、暗号文Ｃから平文ｍを復元する復元装置である。復元端末２０は、受信部２１と、平文復元部２２と、送信部２３と、出力部２４とを備える。
受信部２１は、秘密鍵２Ｌを、鍵生成サーバ３０から受信する。又、受信部２１は、暗号文Ｃを暗号文管理サーバ４０から受信する。更に、受信部２１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。
【０１１０】
平文復元部２２は、秘密鍵２Ｌを用いて暗号文Ｃから平文ｍを復元する。平文復元部２２は、復元した平文ｍを出力部２４に出力する。送信部２３は、暗号文Ｃの要求や、復号要求を送信する。このような復元端末２０は、コンピュータを、受信部２１と、平文復元部２２と、送信部２３と、出力部２４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１１１】
次に、図４、図５を用いて、平文ｍの暗号化から復元において公開鍵通信システム２００が行う処理を詳細に説明する。公開鍵通信システム２００では、公開鍵暗号方式により復号を行う。
公開鍵通信システム２００が、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する暗号方式を用いる場合を説明する。本例においては、鍵生成サーバ３０の鍵生成部３１は、まず、２つの大きなΛ／２ビットの強い素数ｐ，ｑを選択し、公開情報（ｇ，Ｎ，Ｈ１）を作成する。また、素数ｐ及び素数ｑを記憶しておき、秘密鍵２Ｌを生成する。また、鍵生成サーバ３０の鍵生成部３１は、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【０１１２】
鍵生成部３１は、素数ｐ’、素数ｑ’よりＬ＝ｐ’ｑ’を構成し、公開情報（ｇ，Ｎ，Ｈ１）に対応する秘密鍵２Ｌを生成する。
鍵生成部３１は、生成した複数の秘密鍵２Ｌを、送信部３３に入力する。
送信部３３は、図５に示すように、素数ｐ，ｑを秘密にしたまま復元端末２０に対応する公開情報（ｇ，Ｎ，Ｈ１）だけを、暗号化端末１０、暗号文管理サーバ４０、復元端末２０に送信する。暗号化端末１０の受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信し、暗号文生成部１２に入力する。暗号文管理サーバ４０の受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信し、暗号文管理部４２に入力する。
【０１１３】
更に、送信部３３は、秘密鍵２Ｌを復元端末２０に送信する。
暗号化端末１０の暗号文生成部１２は、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，Ｈ１）を用いて暗号化する。具体的には、暗号文生成部１２は、値ｇに対して乱数ｒをｇrｍｏｄＮ2として隠し、ｒの少なくとも一部の情報を用いて平文ｍをもとに暗号文Ｃを生成する。例えば、暗号文生成部１２は、上記式（１）及び上記式（２）を計算することにより、平文ｍを暗号化し、暗号文Ｃを生成する。平文ｍは、暗号化端末１０が暗号化して秘密にしたい情報である。本実施形態における平文ｍは、秘密鍵２Ｌを用いない限り、暗号文Ｃから平文ｍを復号できないようにすることにより、暗号化端末１０が暗号化したい情報である。
【０１１４】
暗号文生成部１２は、乱数ｒを、ＺN2から選択する。暗号文生成部１２は、生成した暗号文Ｃを送信部１３に入力する。送信部１３は、図５に示すように、暗号文Ｃを暗号文管理サーバ４０に送信する。
暗号文管理サーバ４０の受信部４１は、図５に示すように、暗号化端末１０から暗号文Ｃを受信する。受信部４１は、受信した暗号文Ｃを暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃを、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，Ｈ１）に対応付けて、暗号文データベース４３に格納する。
【０１１５】
その後、復元端末２０の平文復元部２２が、公開情報（ｇ，Ｎ，Ｈ１）をもとに作成した暗号文Ｃの要求を生成し、送信部２３に入力する。送信部２３は、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。暗号文管理サーバ４０の受信部４１は復元端末２０から暗号文Ｃの要求を受信部４１において受信し、暗号文管理部４２は、暗号文Ｃの要求において指定されている公開情報（ｇ，Ｎ，Ｈ１）に対応する暗号文Ｃを、暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，Ｈ１）と対応付けられた暗号文Ｃを復元端末２０に送信する。このように公開情報（ｇ，Ｎ，Ｈ１）は、暗号文Ｃを識別するための識別データとして用いることができる。
【０１１６】
送信部３３は、秘密鍵２Ｌを送信する。鍵生成サーバ３０の送信部３３から送信された秘密鍵２Ｌは、復元端末２０の受信部２１が受信する。
復元端末２０の受信部２１は、受信した秘密鍵２Ｌを平文復元部２２に入力する。このようにして、受信部２１は、鍵生成サーバ３０から秘密鍵２Ｌを受信する復号情報受信部として機能する。
平文復元部２２は、秘密鍵２Ｌを用いて、暗号文Ｃの一部であるｕから平文ｍを復元する。この場合、平文復元部２２は、
ｕ2L＝（１＋２ｒａＬＮ）ｍｏｄＮ2
からｒｍｏｄＮを求め、
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ
より、平文ｍを得る。
【０１１７】
〔安全性強化のための変形例〕
ところで、上記の通信システムにおいて、鍵生成部３１による鍵生成、暗号化端末１０による暗号化、復元端末２０による復号において、上記とは異なる、以下の処理を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
（１）鍵生成部３１による鍵生成においては、以下の事項が異なる。
鍵生成部３１は、公開情報（ｇ，ｇ2，Ｎ，Ｍ，Ｈ１，Ｈ２）を生成する。まず、４つの大きなΛ／２ビットの強い素数ｐ，ｐ2，ｑ，ｑ2を用い、合成数Ｎ＝ｐｑ，Ｍ＝ｐ2ｑ2を作成し、ｐ，ｐ2，ｑ，ｑ2は秘密にしたままＮ，Ｍを公開情報として公開する。ここで、Ｌ＝ｐ’ｑ’，Ｌ2＝ｐ2’ｑ2’も計算して秘密にしておく。なお、Ｎ＞Ｍとする。
【０１１８】
また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＭを、ａ2∈ＺM，ｂ2∈Ｚ*Mをもとにｇ2＝（１＋ａ2Ｍ）ｂ2MｍｏｄＭ2を、それぞれ定め、ｇ，ｇ2を公開する。また、暗号化の際に用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μとＨ２：｛０，１｝μ×ＺN2×ＺN2×ＺM2×ＺM2→｛０，１｝Bも公開する。ここで復元端末２０の持つ秘密鍵は一つとするほかに、二つにする方法も考えられる。この場合には、復元端末２０では以下の式も用いて復号化処理を行う。
u’2L2ｍｏｄＭ2＝（１＋２ｒａ2Ｌ2Ｍ）
（２）暗号化端末１０による暗号化においては、以下の事項が異なる。
式（１）及び式（２）の代わりに、上述した式（９）を用いる。
【０１１９】
【数１０】
【０１２０】
（３）復号においては、以下の事項が異なる。
暗号文を復号する前に、復元端末２０、暗号文管理サーバ４０の少なくとも１箇所において暗号文の検証を行う。この場合、少なくとも復元端末２０において、暗号文の検証を行うことが望ましい。
ここで復元端末２０のもつ秘密鍵を二つ持つ方法の場合にはuに関して行う部分復号をu’についても同様に行い、復元結果がともにrかどうかの確認をする。もしも同じにならない場合は不正な暗号文として認識する。鍵が二つある場合でも計算時間の短縮のため、uもしくはu’一方に対してのみ復元しても構わない。
以上のように、復号を行う前に、少なくとも復元端末２０が暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【０１２１】
〔通信方法〕
次に、公開鍵通信システム２００を用いて行う通信方法の手順を説明する。まず、鍵生成サーバ３０が、公開情報（ｇ，Ｎ，Ｈ１）、秘密鍵２Ｌを生成する（Ｓ２０１）。鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）を復元端末２０、暗号文管理サーバ４０、暗号化端末１０に送信する（Ｓ２０２、Ｓ２０４、Ｓ２０５）。鍵生成サーバ３０は、復元端末２０に秘密鍵を送信する（Ｓ２０７）。
【０１２２】
暗号化端末１０は、例えば、式（１）及び式（２）を用い、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化し、暗号文Ｃを生成する（Ｓ２０８）。暗号化端末１０は、生成した暗号文Ｃを暗号文管理サーバ４０に送信する（Ｓ２０９）。暗号文管理サーバ４０は、受信した暗号文Ｃを暗号文データベース４３に格納する（Ｓ２１０）。
【０１２３】
復元端末２０は、暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ２１１）。暗号文管理サーバ４０は、復元端末２０の要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復元端末２０に送信する（Ｓ２１２）。
復元端末２０は、秘密鍵２Ｌを用いて乱数ｒ mod Nを計算する。そして、復元端末２０は、受信した暗号文Ｃと、計算した乱数ｒmod Nを、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式に代入することにより、平文ｍを復元する（Ｓ２１９）。
【０１２４】
なお、上述した安全性強化のための変形例の場合には、上記のステップＳ２１０において、又は、ステップＳ２１９の処理前において、暗号文の検証を行うことになる。この場合、少なくとも、復元端末２０が行うステップＳ２１９の処理前において、暗号文の検証を行うことが望ましい。このように、復号を行う前に、少なくとも復元端末において、暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【０１２５】
〔効果〕
本実施形態の公開鍵通信システム２００、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０及び通信方法によれば、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、公開鍵通信システム２００では、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて複数ビットの平文ｍを暗号化しているので安全性を確保できる。
【０１２６】
上記の暗号化処理において、ｕ＝ｇrｍｏｄＮ2、Ｈ１（ｒｍｏｄＮ）の部分を事前に計算し、暗号化する際はｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍのみ計算すれば良いので、暗号化する際の計算量を少なくできることが分かる。つまり、公開鍵通信システム２００によれば、部分的に事前計算するので、処理効率の良い公開鍵暗号方式を実現することができる。なお、上述した、安全性強化のための変形例を採用した場合、暗号文の検証を行うためのデータについてもほぼ事前計算できるので、安全性を強化してもやはり処理効率の良い公開鍵暗号方式を実現することができる。
【０１２７】
また、例えば、Ｈ１（ｒｍｏｄＮ）＊ｍとしてｍを暗号化することにより、ハッシュ関数の性質からｍを求めるためには、ｒｍｏｄＮを一意に決定する必要性がある。このため、本実施形態を採用すれば、決定問題に根拠をおくかもしくは選択暗号文攻撃に対しても安全性を確保でき、安全性を付与した公開鍵値暗号方式を実現することができる。
特に、暗号化端末１０が、携帯性を重視する移動通信端末のように高速のＣＰＵを搭載することが困難な装置の場合においても、計算量が少ない本発明のしきい値暗号方式であれば利用可能である。このように、本発明の公開鍵暗号方式は、計算能力が低い暗号化装置においても、利用可能であり、暗号化を効率的に行うことができる。
【０１２８】
ところで、本実施形態の公開鍵通信システム２００は、種々の変更が可能である。例えば、復元端末２０又は暗号文管理サーバ４０が、鍵生成サーバ３０の機能の一部又は全部を備え、鍵生成装置として機能してもよい。この場合、復元端末２０が鍵生成サーバ３０の機能の全部を備えていることが望ましい。この他、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０のそれぞれの全部又は一部の機能のうち、少なくとも２つの機能を有する装置を公開鍵通信システム２００に備えてもよい。なお、公開鍵通信システム２００は、暗号化端末１０、暗号文管理サーバ４０を複数備えてもよい。
【０１２９】
又、上記実施の形態では、暗号文Ｃを識別するための識別データとして公開情報（ｇ，Ｎ，Ｈ１）を用いているが、公開情報以外のデータを識別データとして用いることができる。又、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）の暗号文管理サーバ４０への送信を省略してもよい。尚、この場合には、暗号文管理サーバ４０は、暗号文Ｃの要求と暗号文Ｃとを対応付けるための識別データとして、公開情報（ｇ，Ｎ，Ｈ１）以外のものを暗号文Ｃに付与し、その識別データを復元端末２０へ与え、その識別データに対応付けて暗号文Ｃを暗号文データベース４３に格納する。
あるいは、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）を、暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信せずに、これらの装置が自由に閲覧して取得できるようにしてもよい。
【０１３０】
（まとめ）
上述した第１実施形態及び第２実施形態は、ともに事前計算を行うことにより暗号化を高速に行えるという特徴を持ち、素因数分解型の方式のため素数生成時の問題も少ない。
さらに、第１実施形態では安全性が選択平文攻撃のもとでのみ示されるが決定問題という比較的弱い仮定の下で安全性を示せる利点もある。第２実施形態では選択暗号文攻撃のもとでの安全性が示されるという利点がある。
【産業上の利用可能性】
【０１３１】
本発明は、安全かつ効率的なしきい値暗号方式及び公開鍵暗号方式を採用した通信システムの構築に利用できる。
【図面の簡単な説明】
【０１３２】
【図１】本発明の第１実施形態に係る通信システムの構成を示す図である。
【図２】本発明の第１実施形態に係る情報の流れを示す図である。
【図３】本発明の第１実施形態に係る通信方法の手順を示すフロー図である。
【図４】本発明の第２実施形態に係る通信システムの構成を示す図である。
【図５】本発明の第２実施形態に係る情報の流れを示す図である。
【図６】本発明の第２実施形態に係る通信方法の手順を示すフロー図である。
【符号の説明】
【０１３３】
１０ 暗号化端末
１１ 受信部
１２ 暗号文生成部
１３ 送信部
１４ 入力部
１５ 記憶部
２０ 復元端末
２１ 受信部
２２ 平文復元部
２３ 送信部
２４ 出力部
３０ 鍵生成サーバ
３１ 鍵生成部
３２ 鍵データベース
３３ 送信部
４０ 暗号文管理サーバ
４１ 受信部
４２ 暗号文管理部
４３ 暗号文データベース
４４ 送信部
５０i 復号サーバ
６０ ネットワーク
１００ 通信システム
２００ 公開鍵通信システム
５１i 受信部
５２i 部分復号情報生成部
５３i 送信部
【技術分野】
【０００１】
本発明は通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法に関し、特に公開鍵暗号方式やしきい値暗号方式を採用した通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法に関する。
【背景技術】
【０００２】
従来、安全な通信を行うために、公開鍵暗号方式が用いられている。公開鍵暗号方式では、公開鍵に対する復号鍵を安全に保管しておくことが大きな課題の一つになっている。この課題に対する解決方法の一つとして、種々のしきい値暗号方式が開発されている。しきい値暗号方式とは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、分散鍵を持つ複数の装置が協力しなければ、平文を復元できないようにした方式である。
【０００３】
公開鍵暗号を用いるにあたって復号鍵を如何に安全に保管しておくかということは大きな課題の一つであり、その解決方法の一つとして種々のしきい値暗号の方式が開発されてきた。ここで、しきい値暗号とは公開鍵暗号における復号のための復号鍵をいくつかの分散鍵と呼ばれるものに分散し、分散鍵をもつ複数のセンタが協力しなければ復号ができない方式である。このようなしきい値暗号の方式としては、例えば、素因数分解型の暗号方式を用いる方法(例えば、非特許文献１、非特許文献２、非特許文献３)や、離散対数型の暗号方式を用いる方法(例えば、非特許文献４)などが知られている。
【０００４】
【非特許文献１】Pierre-Alain Fouque and David Pointcheval, Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks. ASIACRYPT 2001, pp.351-368(2001)
【非特許文献２】石原武、青野博、本郷節之、四方順司、しきい値型Paillier 暗号の改良、信学技報ISEC2004-12(2004-05)、電子情報通信学会
【非特許文献３】V.Shoup and R.Gennaro, Securing Threshold Cryptosystems against Chosen Ciphertext Attack, Journal of Cryptology, vol.15,no.2, pp.75-96(2002)
【非特許文献４】J.Katz and M.Yung, “Threshold Cryptosystems Based on Factoring”, ASIACRYPT2002, Lecture Notes in Computer Science, 2501, pp.192-205, Springer-Verlag, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記非特許文献１に記載の技術は選択暗号文攻撃に対して安全性が示せるものの、暗号化の際にべき乗演算を数多く行う必要があり、暗号化の前に事前計算できないべき乗演算が存在していた（問題点１）。
また上記非特許文献２に記載の技術は暗号化のための計算量は少ないものの、安全性が選択平文攻撃のもとでのみ示され、選択暗号文攻撃のもとでの安全性が示されないという問題があった（問題点２）。また安全性の根拠をｅ乗根判定問題という、強い仮定の元ではじめて安全性が示せていた（問題点２’）。
【０００６】
また上記非特許文献３に記載の技術は素因数分解に基づく方式に比べて大きな素数を準備する必要がある。素数定理より大きい素数は数が少ないために、大きい素数を準備するということは目的の素数が見つけにくく、使える素数も少ないという問題がある（問題点３）。
さらに、非特許文献４に示される素因数分解型のしきい値暗号方式では、法Ｎのもとでの計算により暗号化及び復号を行い、選択平文攻撃に対する安全性を確保できるものの、１ビットしか暗号化できなかった。そのため、暗号化及び復号の効率が非常に悪く、実用的ではなかった（問題点４）。
【０００７】
特に、問題点１及び問題点４については、携帯性を重視する移動通信端末は高速のＣＰＵを搭載することが困難なため上記従来技術のしきい値暗号方式は、その暗号化の際の計算が非効率なため実用向きではない。
本発明の第１の目的は、上述した問題点１，２’，３，４を解決するため、複数ビットの平文を暗号化でき、決定問題に仮定を置く、素因数分解型で、かつ、事前計算により計算能力の低い移動通信端末などにおいても実用可能な、しきい値暗号化方式又は公開鍵暗号方式を採用した、通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法を提供することである。
【０００８】
本発明の第２の目的は、上述した問題点１，２，３，４を解決するため、複数ビットの平文を暗号化でき、素因数分解型で、かつ、事前計算により計算能力の低い移動通信端末などにおいても実用可能な、しきい値暗号化方式又は公開鍵暗号方式を採用した、通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の請求項１による通信システムは、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成装置と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号装置（例えば、図１〜図３中の復号サーバ５０1〜５０nに対応）と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムを実現できる。
【００１０】
本発明の請求項２による暗号化装置は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける暗号化装置を実現できる。
【００１１】
本発明の請求項３による鍵生成装置は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成手段と、前記分散鍵生成手段によって生成された分散鍵を部分復号装置に送信する分散鍵送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１２】
本発明の請求項４による鍵生成装置は、請求項３において、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする。このように構成すれば、安全性をより高めたしきい値暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
本発明の請求項５による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップを含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した鍵生成方法を実現できる。
【００１３】
本発明の請求項６による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする。このように構成すれば、安全性をより高めたしきい値暗号方式を採用した鍵生成方法を実現できる。
【００１４】
本発明の請求項７による復元装置は、復号の際に乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムにおける復元装置を実現できる。
【００１５】
本発明の請求項８による通信方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成するステップと、
暗号文と前記分散鍵記憶手段に記憶されている分散鍵とを用いて部分復号情報を生成するステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とするステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信方法を実現できる。
【００１６】
本発明の請求項９による通信システムは、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成装置と、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成装置によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムを実現できる。
【００１７】
本発明の請求項１０による鍵生成装置は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵生成手段によって生成された秘密鍵を復元装置に送信する秘密鍵送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１８】
本発明の請求項１１による鍵生成装置は、請求項１０において、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする。このように構成すれば、安全性をより高めた公開鍵暗号方式を採用した通信システムにおける鍵生成装置を実現できる。
【００１９】
本発明の請求項１２による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した鍵生成方法を実現できる。
本発明の請求項１３による鍵生成方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする。このように構成すれば、安全性をより高めた公開鍵値暗号方式を採用した鍵生成方法を実現できる。
【００２０】
本発明の請求項１４による通信方法は、合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する鍵生成ステップと、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信方法を実現できる。
【００２１】
本発明の請求項１５による暗号化装置は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムにおける暗号化装置を実現できる。
【００２２】
本発明の請求項１６による通信システムは、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成手段と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号手段（例えば、図１〜図３中の復号サーバ５０1〜５０nに対応）と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元手段と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信システムを実現できる。
【００２３】
本発明の請求項１７による通信方法は、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成ステップと、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的なしきい値暗号方式を採用した通信方法を実現できる。
【００２４】
本発明の請求項１８による通信システムは、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元手段と、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信システムを実現できる。
【００２５】
本発明の請求項１９による通信方法は、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し（従来特にしきい値暗号では検証データだけではなく一つの平文に対して二度暗号化してはじめて選択暗号文攻撃に対して安全であった）、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする。このように構成すれば、安全かつ効率的な公開鍵暗号方式を採用した通信方法を実現できる。
【００２６】
本発明の請求項２０による暗号化方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化することを特徴とする。このように構成すれば、平文mとは無関係に決められる乱数rをあらかじめ決めてｇrをあらかじめ計算しておくことが可能となり、効率的なしきい値暗号方式を採用した通信システムにおける暗号化方式を実現でき、また乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全なしきい値暗号方式を採用した通信システムにおける暗号化方法を実現できる。
【００２７】
本発明の請求項２１による暗号化方法は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加することを特徴とする。このように構成すれば、平文mとは無関係に決められる乱数rをあらかじめ決めてｇrをあらかじめ計算しておくことが可能となり、さらに検証用データも大部分を事前に計算することにより効率的なしきい値暗号方式を採用した通信システムにおける暗号化方式を実現でき、また暗号文の検証用データによって選択暗号文攻撃に対する耐性が付加され、安全なしきい値暗号方式を採用した通信システムにおける暗号化方法を実現できる。
【００２８】
本発明の請求項２２による暗号復元方法は、復号の際に乱数ｒの少なくとも一部を、しきい値暗号化方式において使用する部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全なしきい値暗号方式を採用した通信システムにおける暗号復元方法を実現できる。
【００２９】
本発明の請求項２３による暗号復元方法は、復号の前に暗号文検証用データをもとに暗号文が正しく作られたものであるか確認し、その後確認が取れた場合には復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、暗号文の検証用データによって選択暗号文攻撃に対する耐性が付加され、安全なしきい値暗号方式を採用した通信システムにおける暗号復元方法を実現できる。
【００３０】
本発明の請求項２４による復元装置は、復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする。このように構成すれば、乱数rの少なくとも一部の情報を正確に求める必要性から安全性の根拠を決定問題に置くことが可能となり安全な公開鍵暗号方式を採用した通信システムにおける復元装置を実現できる。
【発明の効果】
【００３１】
本発明によれば、計算能力が低い端末においても事前計算を行うことにより暗号化できるので、効率的なしきい値暗号方式又は公開鍵暗号方式を採用した通信システムを実現できるという効果がある。
また、本発明によれば、選択暗号文攻撃に対する耐性を付加するか、又は決定問題が難しいという妥当な仮定に基づくようにしたため、安全なしきい値暗号方式又は公開鍵暗号方式を採用した通信システムを実現できるという効果がある。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施の形態を、図面を参照して説明する。なお、以下の説明において参照する各図では、他の図と同等部分は同一符号によって示されている。また、以下の説明において用いられている英文字やギリシャ文字は、各実施形態において同一に意義を有している。
本発明では、合成数ＮをＮ＝ｐｑと定義し、ｐ，ｑを相異なる奇素数とし、共にΛ／２ビットとする。また、ＺN2は、０以上Ｎ2未満の整数の集合、Ｚ*N2は、ＺN2の要素のうちＮ2と互いに素な整数の集合、ＱN2は法Ｎ2のもとで平方余剰である整数でありかつＮ2と互いに素な値の集合、とする。
【００３３】
さらに、本発明では、以下の仮定１及び仮定２を前提とする。
（仮定１）
（Ｐａｒｔｉａｌ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ａｓｓｕｍｐｔｉｏｎ）
Ｎ（＝ｐｑ），ｇ∈Ｚ*N2，ｇr（ｇのｒ乗）（ｒ∈ＺN2）（Ｎ２はＮ2を意味する）
が与えられた際に、ｒと法をＮとして合同なｒ’（当然ｒと完全に等しくてもよい）を求めることはほとんどできない。なお、「ほとんどできない」とは、この問題が何題か出題された場合、正解率が０に限りなく近いいう意味である。
ここで、ｇの位数を０でないＮの倍数とする。
【００３４】
（仮定２）
（Ｄｅｃｉｓｉｏｎａｌ Ｓｍａｌｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ Ａｓｓｕｍｐｔｉｏｎ）
Ｎ（＝ｐｑ），Ｍ（＝ｐ2ｑ2）,ｇ∈Ｚ*N2，ｇ2∈Ｚ*M2，ｇr（ｇのｒ乗）（ｒ∈ＺN2）（Ｎ２はＮ2を意味し、Ｍ２はＭ2を意味する）
が与えられた際に、さらに以下に定義するＺ0もしくはＺ1を与えた際に、その予想が当たる確率は１／２とほとんど同じである（１／２との差が限りなく０に近い）。
Ｚ0＝ｇ2rｍｏｄＭ2，Ｚ1＝Ｒ（∈Ｚ*M2）（Ｍ２はＭ2を意味する）
ここで、ｇの位数を０でないＮの倍数、ｇ2の位数を０でないＮ2の倍数とする。ただし、Ｎ＞Ｎ2とするが、その差は無視できるほどしか差が無いとする。
【００３５】
（第１実施形態）
〔通信システム〕
図１に示すように、通信システム１００は、暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０1〜５０nと、ネットワーク６０とを備える。暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、複数の復号サーバ５０1〜５０nは、ネットワーク６０を介して、情報を送受信する。
【００３６】
鍵生成サーバ３０は、μビットの平文ｍの暗号化に用いる公開情報（ｇ，Ｎ，θ，Ｈ１）と、暗号文Ｃの復号に用いる秘密情報Ｌβとその分散鍵ｓを生成する鍵生成装置である。鍵生成サーバ３０は、鍵生成部３１と、鍵データベース３２と、送信部３３とを備える。鍵生成部３１は、公開情報（ｇ，Ｎ，θ，Ｈ１）と、それに対する秘密情報Ｌβと、秘密情報Ｌβを複数に分散した分散鍵ｓとを生成する。鍵生成部３１は、ｎ個の分散鍵ｓを生成する。さらに部分復号情報が正しいことを検証するためのｎ個の検証鍵ｖｋとその生成元ｖを生成する。各検証鍵を区別するときには、ｉ番目の検証鍵を「ｖｋｉ」と表す。よって、各分散鍵を区別するときには、ｉ番目の分散鍵を「ｓi」と表す。このように検証鍵ｖｋと分散鍵ｓには、１〜ｎまでの番号が付与される。なお、復号サーバの数である「ｎ」と、（ｔ，ｎ）しきい値暗号方式において復号のために必要な部分復号情報の数を表す「ｔ」は、公開されている情報である。これら「ｎ」及び「ｔ」は、復元端末２０に送信される。
【００３７】
鍵データベース３２は、公開情報（ｇ，Ｎ，θ，Ｈ１）を記憶する。送信部３３は、鍵生成部３１が生成した公開情報（ｇ，Ｎ，θ，Ｈ１）を暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信する。また、検証鍵ｖｋ１〜ｖｋｎを少なくとも復元端末２０に送信する。また、送信部３３は、分散鍵ｓ1〜ｓnを、復号サーバ５０1〜５０nに送信する。このような鍵生成サーバ３０は、コンピュータを、鍵生成部３１と、鍵データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００３８】
暗号化端末１０は、平文ｍを暗号化して暗号文Ｃを生成する暗号化装置である。暗号化端末１０は、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５とを備えている。
受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信する。記憶部１５は、暗号文生成部１２が事前に計算するＨ１（ｒｍｏｄＮ）とｕ＝ｇrｍｏｄＮ2とを記憶する。受信部１１は、平文ｍを受信し、暗号文生成部１２に入力してもよい。
【００３９】
入力部１４は、外部から入力される平文ｍを取得し、暗号文生成部１２に入力する。暗号文生成部１２は、事前計算され記憶部１５に記憶されているＨ１（ｒｍｏｄＮ）及びｕ＝ｇrｍｏｄＮ2を用いて平文ｍを暗号化する。暗号文生成部１２は、暗号文Ｃを生成する際に、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する。暗号文生成部１２は、入力部１４や受信部１１から平文ｍを取得する。なお、ｒ∈UＺN2（Ｎ２はＮ2を意味する）である。ここで、「Ｘ∈UＧ」は、集合Ｇから一様な確率で要素Ｘを選択することを表す。
【００４０】
暗号文生成部１２は、以下に示す式（１）及び式（２）を計算することにより、平文ｍを暗号化して暗号文Ｃ（ｃ，ｕ）を生成することが好ましい。
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ …（１）
ｕ＝ｇrｍｏｄＮ2 …（２）
ハッシュ関数Ｈ１は、ＺN→｛０，１｝μである。なお、上記の「＊」は排他的論理和を示している。以後の説明においても同様である。
【００４１】
送信部１３は、暗号文生成部１２が生成した暗号文Ｃを、暗号文管理サーバ４０に送信する。記憶部１５は、後述するように暗号化する際に部分的に事前計算した結果を、一旦記憶する。このような暗号化端末１０は、コンピュータを、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００４２】
暗号文管理サーバ４０は、暗号文Ｃを暗号化端末１０から受信し、暗号文Ｃを各装置に提供する暗号文管理装置である。暗号文管理サーバ４０は、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。受信部４１は、暗号化端末１０から暗号文Ｃを受信する。又、受信部４１は、復元端末２０や復号サーバ５０1〜５０nから、暗号文Ｃの要求を受信する。更に、受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信する。
【００４３】
暗号文データベース４３は、暗号文Ｃを記憶する。送信部４４は、暗号文Ｃを復元端末２０、復号サーバ５０1〜５０nに送信する。このような暗号文管理サーバ４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００４４】
復号サーバ５０1〜５０nは、部分復号情報σを生成する。部分復号情報σは、暗号文Ｃから平文ｍを復元する際に用いる情報であり、復元端末２０が平文ｍの復元をするために必要な情報である。部分復号情報σは、暗号文Ｃと分散鍵ｓとを用いた計算を行うことにより、即ち、暗号文Ｃを分散鍵ｓを用いて部分的に復号することにより得られる情報である。複数の復号サーバ５０1〜５０nがそれぞれ異なる分散鍵ｓを用いて部分復号情報σを生成することにより、複数の部分復号情報σが生成される。分散鍵ｓiを用いて生成された部分復号情報は、「σi」と表す。よって、複数の部分復号情報σとして、分散鍵ｓ1〜ｓnを用いて部分復号情報σ1〜σnが生成される。このように部分復号情報σには、１〜ｎまでの番号が付与される。又、復号サーバ５０1〜５０nにも、１〜ｎまでの番号が付与される。なお、Δ＝ｎ！＝ｎ・（ｎ−１）・（ｎ−２）…２・１と定義する。
【００４５】
復号サーバ５０1〜５０nはそれぞれ、受信部５１1〜５１nと、部分復号情報生成部５２1〜５２nと、送信部５３1〜５３nとを備える。受信部５１1〜５１nは、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）と分散鍵ｓとを受信する。又、受信部５１1〜５１nは、復元端末２０から部分復号情報σの要求（以下「復号要求」という）を受信する。更に、受信部５１1〜５１nは、暗号文管理サーバ４０から暗号文Ｃを受信する。
【００４６】
部分復号情報生成部５２1〜５２nのうち、暗号文Ｃを復号することに同意した部分復号情報生成部は、σi≡ｕ2ΔSiｍｏｄＮ2を復元端末２０に送信する。σi≡ｕ2ΔSiｍｏｄＮ2を受信した復元端末２０は、上記に同意した部分復号情報生成部から送られてきた情報が正しいものかどうか確認する。この確認においては、σi2とｖｋiがそれぞれｕ4Δ、ｖΔを底として同じ対数を持つかどうかを確認する。復元端末２０は、σiが正しいシェアであることを確認できなかった場合はｉｎｖａｌｉｄ ｓｙｍｂｏｌを出して処理を終了し、確認できた場合は以下の計算を行う。
【００４７】
【数１】
ただし、
【００４８】
【数２】
である。そして、ｒｍｏｄＮ並びに式（１）及び式（２）により、平文ｍが得られる。式（３）、式（４）において、「Ｓ」は、復元端末２０からの復号要求を受け入れた復号サーバ５０1〜５０nの番号の集合を表す。
【００４９】
上記のような復号サーバ５０1〜５０nは、コンピュータを、受信部５１1〜５１nと、部分復号情報生成部５２1〜５２nと、送信部５３1〜５３nとして機能させるためのプログラムを、コンピュータが実行することにより実現できる。
復元端末２０は、暗号文Ｃから平文ｍを復元する復元装置である。復元端末２０は、受信部２１と、平文復元部２２と、送信部２３と、出力部２４とを備える。
受信部２１は、複数の部分復号情報σを、複数の復号サーバ５０1〜５０nから受信する。又、受信部２１は、暗号文Ｃを暗号文管理サーバ４０から受信する。更に、受信部２１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）と検証鍵ｖｋ1〜ｖｋnを受信する。
【００５０】
平文復元部２２は、複数の部分復号情報σを用いて暗号文Ｃから平文ｍを復元する。平文復元部２２は、復元した平文ｍを出力部２４に出力する。送信部２３は、暗号文Ｃの要求や、復号要求を送信する。このような復元端末２０は、コンピュータを、受信部２１と、平文復元部２２と、送信部２３と、出力部２４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００５１】
次に、図１、図２を用いて、平文ｍの暗号化から復元において通信システム１００が行う処理を詳細に説明する。通信システム１００では、（ｔ，ｎ）しきい値暗号方式により復号を行う。（ｔ，ｎ）しきい値暗号方式とは、ｎ個の分散鍵ｓ1〜ｓnを用いて生成されるｎ個の部分復号情報σ1〜σnのうち、ｔ個の部分復号情報を用いれば、平文ｍが復元できるしきい値暗号方式である。よって、「ｔ」は、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報σの数を表す。
【００５２】
通信システム１００が、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する暗号方式を用いる場合を説明する。鍵生成サーバ３０の鍵生成部３１は、まず、２つの大きなΛ／２ビットの強い素数ｐ，ｑを選択し、その積を計算して、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【００５３】
ここで、Ｌ＝ｐ’ｑ’を計算して秘密にしておく。また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＮ2を定め、ｇを公開する。さらに、値β∈Ｚ*Nをランダムに選択し、θ＝ａＬβｍｏｄＮを計算する。θを公開し、暗号化の際用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μも公開する。
次に、鍵生成部３１は、公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する秘密情報Ｌβを生成する。秘密情報Ｌβは、
【００５４】
【数３】
を満たす。更に、鍵生成部３１は、秘密情報Ｌβを複数に分散して複数の分散鍵ｓ、即ち、ｎ個の分散鍵ｓ1〜ｓnを生成する。分散鍵ｓ1〜ｓnは、相互に異なる秘密情報である。
【００５５】
本実施形態では、分散鍵ｓ1〜ｓnの個数ｎは、復号サーバ５０1〜５０nの数と等しい。しかし、一つの復号サーバが複数の分散鍵を用いてもよい。よって、分散鍵ｓの個数と復号サーバの数は、必ずしも一致するとは限らない。分散鍵ｓ1〜ｓnの個数と復号サーバ５０1〜５０nの数が一致する本実施形態では、復号サーバ５０ｉが、分散鍵ｓiを用いる。例えば、鍵生成部３１は、Shamirにより提案された方法等を用いて、秘密情報Ｌβを複数に分散できる。
【００５６】
具体的には、鍵生成部３１は、ａi∈U｛０，１，・・・，ＬＮ−１｝、（ｉ＝１，２，・・・，ｔ−１）を乱数として選択し、さらに、ａ0＝Ｌβとして定義して分散鍵ｓiを生成する。又、「ＺX」とは、０以上Ｘ未満の整数の集合（ＺX＝Ｚ／ＸＺ）を表す。この場合、鍵生成部３１は、以下に示す式（６）を計算することにより、複数の分散鍵ｓ1〜ｓnを生成する。鍵生成部３１は、式（６）を用いて、ｓi＝ｆ（ｉ）ｍｏｄＬＮを計算することにより分散鍵ｓiを生成する。
【００５７】
【数４】
【００５８】
鍵生成部３１は、生成した複数の分散鍵ｓ1〜ｓnを、送信部３３に入力する。
更に、鍵生成部３１は、部分復号情報σが正しく暗号文Ｃを部分的に復号したものか否かを判定する際に用いる複数の検証鍵ｖｋを生成する。鍵生成部３１は、分散鍵ｓ1〜ｓnと同数のｎ個の検証鍵ｖk1〜ｖｋnを生成する。鍵生成部３１は、以下に示す式（７）を計算することにより検証鍵ｖｋ1〜ｖｋnを生成する。
【００５９】
【数５】
【００６０】
式（７）において、νはＱN2（Ｎ２はＮ2を意味する）の部分群の生成元である。「ＱX」は、法Ｘのもとで平方余剰かつＸと互いに素な整数の集合を表す。そのため、「ＱX」は、Ｚ*Xから要素を一つ取得し、２乗した値の集合となる。鍵生成部３１は、生成した複数の検証鍵ｖｋ1〜ｖｋnと、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νの合計ｎ＋１個の値を、送信部３３に入力する。
【００６１】
送信部３３は、図２に示すように、素数ｐ，ｑを秘密にしたまま復元端末２０に対応する公開情報（ｇ，Ｎ，θ，Ｈ１）だけを、暗号化端末１０、暗号文管理サーバ４０、復元端末２０に送信する。暗号化端末１０の受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信し、暗号文生成部１２に入力する。暗号文管理サーバ４０の受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，θ，Ｈ１）を受信し、暗号文管理部４２に入力する。
【００６２】
更に、送信部３３は、公開情報（ｇ，Ｎ，θ，Ｈ１）と複数の分散鍵ｓ1〜ｓnとを対応付けて、複数の復号サーバ５０1〜５０nに送信する。このとき、送信部３３は、複数の分散鍵ｓ1，・・・，ｓi，・・・，ｓnをそれぞれ、復号サーバ５０1，・・・，５０i，・・・，５０nに送信する。復号サーバ５０1〜５０nの受信部５１1〜５１nは、鍵生成サーバ３０から、公開情報（ｇ，Ｎ，θ，Ｈ１）と分散鍵ｓ1〜ｓnを受信し、部分復号情報生成部５２1〜５２nに入力する。送信部３３は、このようにして、複数の分散鍵ｓを復号装置に送信する鍵送信部として機能する。
【００６３】
このように、送信部３３が、ｕからｒの少なくとも一部を取出す際必要となる秘密情報Ｌβを分散した分散鍵ｓ1〜ｓnを、複数の復号サーバ５０1〜５０nに分散して提供する。更に、鍵生成サーバ３０自身も秘密情報Ｌβは、鍵データベース３２に格納しない。これにより、秘密情報Ｌβは一箇所に管理されず、複数の復号サーバ５０1〜５０nによって分散管理される。
【００６４】
又、送信部３３は、公開情報（ｇ，Ｎ，θ，Ｈ１）と検証鍵ｖｋ1〜ｖｋnと、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νとを対応付けて、復元端末２０に送信する。復元端末２０の受信部２１は、鍵生成サーバ３０から、公開情報（ｇ，Ｎ，θ，Ｈ１）、検証鍵ｖｋ1〜ｖｋn、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元νを受信し、平文復元部２２に入力する。
【００６５】
暗号化端末１０の暗号文生成部１２は、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，θ，Ｈ１）を用いて暗号化する。具体的には、暗号文生成部１２は、値ｇに対して乱数ｒをｇrｍｏｄＮ2として隠し、ｒの少なくとも一部の情報を用いて平文ｍをもとに暗号文Ｃを生成する。例えば、暗号文生成部１２は、上記式（１）及び上記式（２）を計算することにより、平文ｍを暗号化し、暗号文Ｃを生成する。平文ｍは、暗号化端末１０が暗号化して秘密にしたい情報である。本実施形態における平文ｍは、複数の分散鍵ｓ1〜ｓnを用いない限り、暗号文Ｃから平文ｍを復号できないようにすることにより、暗号化端末１０が分散管理したい情報である。
【００６６】
暗号文生成部１２は、乱数ｒを、ＺN2から選択する。暗号文生成部１２は、生成した暗号文Ｃを送信部１３に入力する。送信部１３は、図２に示すように、暗号文Ｃと暗号化に用いた公開鍵を暗号文管理サーバ４０に送信する。
暗号文管理サーバ４０の受信部４１は、図２に示すように、暗号化端末１０から暗号文Ｃを受信する。受信部４１は、受信した暗号文Ｃを暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃを、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，θ，Ｈ１）に対応付けて、暗号文データベース４３に格納する。
【００６７】
その後、復元端末２０の平文復元部２２が、公開情報（ｇ，Ｎ，θ，Ｈ１）をもとに作成した暗号文Ｃの要求と、公開情報（ｇ，Ｎ，θ，Ｈ１）と秘密情報をもとに作成した部分復号情報σを要求する復号要求を生成し、送信部２３に入力する。送信部２３は、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。暗号文管理サーバ４０の受信部４１は、復元端末２０から暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃの要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する暗号文Ｃを、暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けられた暗号文Ｃを復元端末２０に送信する。このように公開情報（ｇ，Ｎ，θ，Ｈ１）は、暗号文Ｃを識別するための識別データとして用いることができる。
【００６８】
又、送信部２３は、復号要求を複数の復号サーバ５０1〜５０nに送信する。このとき、送信部２３は、復号要求を全ての復号サーバ５０1〜５０nにブロードキャストにより送信してもよく、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報の数ｔだけ復号サーバを選択し、送信してもよい。
復号サーバ５０1〜５０nの受信部５１1〜５１nは、復号要求を受信し、部分復号情報生成部５２1〜５２nに入力する。部分復号情報生成部５２1〜５２nは、復号要求を受け入れた場合、復号要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）を指定した暗号文Ｃの要求を生成し、送信部５３1〜５３nに入力する。送信部５３1〜５３nは、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。尚、部分復号情報生成部５２1〜５２nは、復号要求を拒否してもよい。
【００６９】
暗号文管理サーバ４０の受信部４１は、復号サーバ５０1〜５０nから暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。暗号文管理部４２は、指定された公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する暗号文Ｃを暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，θ，Ｈ１）と対応付けられた暗号文Ｃを復号サーバ５０1〜５０nに送信する。
【００７０】
復号サーバ５０1〜５０nの受信部５１1〜５１nは、暗号文Ｃを受信し、部分復号情報生成部５２1〜５２nに入力する。部分復号情報生成部５２1〜５２nはそれぞれ、受信した暗号文Ｃと分散鍵ｓ1〜ｓnを用いて、σi≡ｕ2ΔSiｍｏｄＮ2を計算することにより、暗号文Ｃを部分的に復号して部分復号情報σ1〜σnを生成する。部分復号情報生成部５２1〜５２nは、復号要求において指定されている公開情報（ｇ，Ｎ，θ，Ｈ１）に対応する分散鍵ｓ1〜ｓnを用いる。
【００７１】
例えば、復号サーバ５０ｉの場合、暗号文Ｃと分散鍵ｓiを用いて、
σi＝ｕ2ΔSiｍｏｄＮ2
を計算することにより、部分復号情報σiを生成する。
部分復号情報生成部５２は、生成した部分復号情報σ1〜σnを送信部５３1〜５３nに入力する。送信部５３1〜５３nはそれぞれ、図２に示すように、部分復号情報σ1〜σnを復元端末２０に送信する。尚、全ての復号サーバ５０1〜５０nが、部分復号情報σ1〜σnの生成、送信を行う必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを生成し、復元端末２０に送信すればよい。
【００７２】
復元端末２０の受信部２１は、複数の復号サーバ５０1〜５０nから複数の部分復号情報σ1〜σnを受信する。受信部２１は、受信した複数の部分復号情報σ1〜σnを平文復元部２２に入力する。このようにして、受信部２１は、複数の復号装置から複数の部分復号情報σを受信する復号情報受信部として機能する。尚、受信部２１は、全ての復号サーバ５０1〜５０nから全ての部分復号情報σ1〜σnを受信する必要はなく、少なくとも（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを受信する。
【００７３】
平文復元部２２は、複数の部分復号情報σ1〜σnを用いて、暗号文Ｃの一部であるｕから平文ｍを復元する。平文復元部２２は、まず、部分復号情報σが正しく復号されたものか否かを判定する。平文復元部２２は、暗号文Ｃの一部であるｕの４Δ乗「ｕ4Δ」を底とした部分復号情報の２乗「σ2」の対数と、ＱN2（Ｎ２はＮ2を意味する）の部分群の生成元のΔ乗「νΔ」を底とした検証鍵ｖｋの対数が等しいか否かを判定する。平文復元部２２は、対数が等しい場合には、部分復号情報σが正しく復号されたものであると判定し、対数が異なる場合には、部分復号情報σは正しく復号されていないと判定する。
【００７４】
平文復元部２２は、複数の部分復号情報σ1〜σnについて、それぞれ検証鍵ｖｋ1〜ｖｋnを用いて判定を行う。対数が等しいか否かの判定には、一般的な方法、例えば、文献「ＦＰＳ００：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」に記載されている方法を用いることができる。
【００７５】
平文復元部２２は、正しく復号されていると判定した部分復号情報σ1〜σnを用いて、まず、平文ｍの暗号化に用いた乱数ｒの情報の一部を計算する。尚、平文復元部２２は、全ての復号サーバ５０1〜５０nからの全ての部分復号情報σ1〜σnを用いる必要はなく、（ｔ，ｎ）しきい値暗号方式において必要なｔ個の部分復号情報σを選択し、用いる。
平文復元部２２は、まず、上述した式（３）を計算する。平文復元部２２は、文献「ＳＨｏ００：victor Shoup， “Practical Threshold Signatures”，EUROCRYPT，Lecture Notes in Computer Science， pp.207-220，2000」と同様に、式（４）に示す条件で式（３）を計算する。
【００７６】
式（３）、式（４）において、「Ｓ」は、復元端末２０からの復号要求を受け入れた復号サーバ５０1〜５０nの番号の集合を表す。つまり、例えば、番号１、２、５が付与された復号サーバが復号要求を受け入れた場合には、Ｓ＝｛１，２，５｝と記述される。但し、集合Ｓに含まれる番号の数は、（ｔ，ｎ）しきい値暗号方式において部分復号情報σが必要な数ｔに限定される。又、式（３）、式（４）における「λ」は補間係数である。「λ」は、式（４）において、ｆ（０）＝ａ0を計算するために用いられ、式（８）に示す関係を持つ。
【００７７】
【数６】
【００７８】
又、「Πj∈S/[i]（ｉ−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての番号に関してｉから引き算した値を考え、それら全ての積を示す。同様に、「Πj∈S/[i]（−ｊ）」は、集合Ｓに含まれる番号のうちｉを除く全ての数字に関して、符号の正負を逆にした値の積を示す。
次に、平文復元部２２は、計算した乱数ｒの少なくとも一部を用いて、暗号文Ｃから平文ｍを復元する。具体的には、平文復元部２２は、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式、例えば、上記式（３）に基づいてｒｍｏｄを算出し、算出したｒｍｏｄと受信した暗号文Ｃとを式（１）に代入して、平文ｍを復元する。以上のようにして、復元端末２０は、復号サーバ５０1〜５０nから受信した複数の部分復号情報σ1〜σnに基づいて、秘密の情報である平文ｍを復元できる。
【００７９】
尚、平文復元部２２は、部分復号情報σが正しく復号されていないと判定した場合には、その部分復号情報σを送信した復号サーバに対する部分復号情報の拒否通知を生成し、送信部２３に入力する。送信部２３は、拒否通知を復号サーバに送信し、処理を終了する。もしくは、平文復元部２２は、他の有効な部分復号情報をもとに秘密情報を復元する。
【００８０】
〔安全性強化のための変形例〕
ところで、上記の通信システムにおいて、鍵生成部３１による鍵生成、暗号化端末１０による暗号化、復元端末２０による復号において、上記とは異なる、以下の処理を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
（１）鍵生成部３１による鍵生成においては、以下の事項が異なる。
鍵生成部３１は、公開情報（ｇ，ｇ2，Ｎ，Ｍ，θ，Ｈ１，Ｈ２）を生成する。まず、４つの大きなΛ／２ビットの強い素数ｐ，ｐ2，ｑ，ｑ2を用い、合成数Ｎ＝ｐｑ，Ｍ＝ｐ2ｑ2を作成し、ｐ，ｐ2，ｑ，ｑ2は秘密にしたままＮ，Ｍを公開情報として公開する。ここで、Ｌ＝ｐ’ｑ’，Ｌ2＝ｐ2’ｑ2’も計算して秘密にしておく。なお、Ｎ＞Ｍとする。なお、Ｎ＜Ｍの場合も同様に行える。
【００８１】
また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＭを、ａ2∈ＺM，ｂ2∈Ｚ*Mをもとにｇ2＝（１＋ａ2Ｍ）ｂ2MｍｏｄＭ2を、それぞれ定め、ｇ，ｇ2を公開する。さらに、値β, β2∈Ｚ*Nをランダムに選択し、θ＝ａＬβｍｏｄＮ, θ2＝ａ2Ｌ2β2ｍｏｄＭを計算しておく。また、暗号化の際に用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μとＨ２：｛０，１｝μ×ＺN2×ＺN2×ＺM2×ＺM2→｛０，１｝Bも公開する。ここで復号サーバ５０1〜５０nへ渡す分散鍵はそれぞれ一つとするほかに、それぞれ二つ渡す方法も考えられる。この場合には、鍵生成部３１は、Shamirにより提案された方法等を用いて、秘密情報Ｌ2β2も複数に分散する。
【００８２】
具体的には、鍵生成部３１は、bi∈U｛０，１，・・・，Ｌ2M−１｝、（ｉ＝１，２，・・・，ｔ−１）を乱数として選択し、さらに、b0＝Ｌ2β2として定義して分散鍵ｔiを生成する。この場合、鍵生成部３１は、以下に示す式（６）’を計算することにより、複数の分散鍵t1〜tnを生成する。鍵生成部３１は、式（６）’を用いて、ti＝ｆ2（ｉ）ｍｏｄＬ2Mを計算することにより分散鍵tiを生成する。
【００８３】
【数７】
【００８４】
鍵生成部３１は、生成した複数の分散鍵t1〜tnも、送信部３３に入力する。
更に、鍵生成部３１は、部分復号情報σ’≡ｕ’2ΔtiｍｏｄＭ2が正しく暗号文Ｃを部分的に復号したものか否かを判定する際に用いる複数の検証鍵ｗｋを生成する。鍵生成部３１は、分散鍵ｔ1〜tnと同数のｎ個の検証鍵wk1〜wｋnを生成する。鍵生成部３１は、以下に示す式（７）’を計算することにより検証鍵wｋ1〜wｋnを生成する。
【００８５】
【数８】
【００８６】
式（７）’において、ν2はＱM2（Ｍ２はＭ2を意味する）の部分群の生成元である。
（２）暗号化端末１０による暗号化においては、以下の事項が異なる。
式（１）及び式（２）の代わりに、次の式（９）を用いる。ただし、ｓ∈ＺN4（Ｎ４はＮ4を意味する）とする。
【００８７】
【数９】
【００８８】
（３）復号においては、以下の事項が異なる。
暗号文を復号する前に、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０nの少なくとも１箇所において暗号文の検証を行う。この場合、少なくとも復元端末２０において、暗号文の検証を行うことが望ましい。
ここで復号サーバ５０1〜５０nへ渡す分散鍵をそれぞれ二つ渡す方法の場合にはuに関して行う部分復号と結合をu’についても同様に行い、復元結果がともにrかどうかの確認をする。もしも同じにならない場合は不正な暗号文として認識する。
ただし各復号サーバが通信して納得した上であればuかu’どちらか一方だけ復号してｒを求めても構わない。
以上のように、復号を行う前に、少なくとも復元端末２０が暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【００８９】
〔通信方法〕
次に、通信システム１００を用いて行う通信方法の手順を説明する。まず、鍵生成サーバ３０が、公開情報（ｇ，Ｎ，θ，Ｈ１）、複数の分散鍵ｓ1〜ｓn、複数の検証鍵ｖｋ1〜ｖｋnを生成する（Ｓ１０１）。鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）を復元端末２０、復号サーバ５０1〜５０n、暗号文管理サーバ４０、暗号化端末１０に送信する（Ｓ１０２〜Ｓ１０５）。鍵生成サーバ３０は、複数の分散鍵ｓ1〜ｓnを復号サーバ５０1〜５０nに送信する（Ｓ１０６）。鍵生成サーバ３０は、少なくとも復元端末２，０にｖｋ1〜ｖｋn，ｖを送信する（Ｓ１０７）。
【００９０】
暗号化端末１０は、例えば、式（２）を用い、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、式（１）を用い、乱数ｒの少なくとも一部を用いて平文ｍを暗号化し、暗号文Ｃを生成する（Ｓ１０８）。暗号化端末１０は、生成した暗号文Ｃを暗号文管理サーバ４０に送信する（Ｓ１０９）。暗号文管理サーバ４０は、受信した暗号文Ｃを暗号文データベース４３に格納する（Ｓ１１０）。
【００９１】
復元端末２０は、暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ１１１）。暗号文管理サーバ４０は、復元端末２０の要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復元端末２０に送信する（Ｓ１１２）。
復元端末２０は、復号サーバ５０1〜５０nに復号要求を送信する（Ｓ１１３）。復号サーバ５０1〜５０nは暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ１１４）。
【００９２】
暗号文管理サーバ４０は、復号サーバ５０1〜５０nの要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復号サーバ５０1〜５０nに送信する（Ｓ１１５）。
復号サーバ５０1〜５０nはそれぞれ、暗号文Ｃと分散鍵ｓ1〜ｓnとを用いて、σi≡ｕ2ΔSiｍｏｄＮ2を計算することにより、部分復号情報σ1〜σnを生成する（Ｓ１１６）。 復号サーバ５０1〜５０nはそれぞれ、生成した部分復号情報σ1〜σnを復元端末２０に送信する（Ｓ１１７）。
【００９３】
復元端末２０は、受信した部分復号情報σ1〜σnが正しく復号されたものか否かを、検証鍵ｖｋ1〜ｖｋnを用いて判定する（Ｓ１１８）。復元端末２０は、部分復号情報σ1〜σnが正しく復号されたものと判定した場合には、部分復号情報σ1〜σnを用いて乱数ｒの少なくとも一部の情報を計算する。そして、復元端末２０は、受信した暗号文Ｃと、計算した乱数ｒの少なくとも一部の情報を、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式に代入することにより、平文ｍを復元する（Ｓ１１９）。このようにして、暗号化端末１０と、複数の復号サーバ５０1〜５０nとの間で、秘密の情報である平文ｍを管理できる。尚、ステップ（Ｓ１０３）、（Ｓ１１５）に代えて、復元端末２０から復号サーバ５０1〜５０nに公開情報（ｇ，Ｎ，θ，Ｈ１）や暗号文Ｃを送信するようにしてもよい。
【００９４】
なお、上述した安全性強化のための変形例の場合には、上記のステップＳ１１０、ステップＳ１１６、ステップＳ１１８のうち少なくとも１つのステップにおいて、暗号文の検証を行うことになる。この場合、少なくとも、復号サーバ５０1〜５０nが行うステップＳ１１６において、暗号文の検証を行うことが望ましい。このように、復号を行う前に、少なくとも復元端末において、暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【００９５】
〔効果〕
本実施形態の通信システム１００、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０、複数の復号サーバ５０1〜５０n及び通信方法によれば、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、通信システム１００では、複数ビットの平文ｍを、ｇrを計算し、Ｈ１（ｒｍｏｄＮ）によって暗号化し、安全性を確保できる。
【００９６】
上記の暗号化処理において、ｕ＝ｇrｍｏｄＮ2、Ｈ１（ｒｍｏｄＮ）の部分を事前に計算し、暗号化する際はｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍのみ計算すれば良いので、暗号化する際の計算量を少なくできることが分かる。つまり、通信システム１００によれば、部分的に事前計算するので、処理効率の良いしきい値暗号方式を実現することができる。
【００９７】
特に、暗号化端末１０や復元端末２０が、携帯性を重視する移動通信端末のように高速のＣＰＵを搭載することが困難な装置の場合においても、計算量が少ない本発明のしきい値暗号方式であれば利用可能である。さらに安全性強化のための変形例においては、素因数分解型のしきい値暗号ではよくあるように分散鍵を一つの復号サーバに二つ持たせるといったことが必要なく、変形例においては分散鍵の個数が減っているため記憶容量が少ない場合においても本発明のしきい値暗号方式であれば適用可能である。このように、本発明のしきい値暗号方式は、計算能力が低い暗号化装置や復号装置、復元装置、あるいは、安全性を高めた場合であっても記憶容量が低い暗号化装置や復号装置、復元装置においても、利用可能であり、暗号化と復号を効率的に行うことができる。
【００９８】
なお、上述した、安全性強化のための変形例を採用した場合、暗号文の検証を行うためのデータについてもほぼ事前計算できるので、安全性を強化してもやはり処理効率の良いしきい値暗号方式を実現することができる。
また、例えば、Ｈ１（ｒｍｏｄＮ）＊ｍとしてｍを暗号化することにより、ハッシュ関数の性質からｍを求めるためには、ｒｍｏｄＮを一意に決定する必要性がある。このため、本実施形態を採用すれば、決定問題に根拠をおくかもしくは選択暗号文攻撃に対しても安全性を確保でき、安全性を付与したしきい値暗号方式を実現することができる。
【００９９】
ところで、本実施形態の通信システム１００は、種々の変更が可能である。例えば、暗号化端末１０、復号サーバ５０1〜５０nの一部、又は、復元端末２０が、鍵生成サーバ３０の機能の一部又は全部を備え、鍵生成装置として機能してもよい。この他、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０、復号サーバ５０1〜５０nのそれぞれの全部又は一部の機能のうち、少なくとも２つの機能を有する装置を通信システム１００に備えてもよい。なお、通信システム１００は、暗号文管理サーバ４０、暗号化端末１０を複数備えてもよい。
【０１００】
又、上記実施の形態では、暗号文Ｃを識別するための識別データとして公開情報（ｇ，Ｎ，θ，Ｈ１）を用いているが、公開情報以外のデータを識別データとして用いることができる。又、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）の暗号文管理サーバ４０への送信を省略してもよい。尚、この場合には、暗号文管理サーバ４０は、暗号文Ｃの要求と暗号文Ｃとを対応付けるための識別データとして、公開情報（ｇ，Ｎ，θ，Ｈ１）以外のものを暗号文Ｃに付与し、その識別データを復元端末２０へ与え、その識別データに対応付けて暗号文Ｃを暗号文データベース４３に格納する。
【０１０１】
あるいは、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，θ，Ｈ１）を、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０nに送信せずに、これらの装置が自由に閲覧して取得できるようにしてもよい。又、暗号化端末１０、復元端末２０、暗号文管理サーバ４０、復号サーバ５０1〜５０n等が、予め公開情報（ｇ，Ｎ，θ，Ｈ１）や分散鍵ｓ1〜ｓn、検証鍵ｖｋ1〜ｖｋn等を保持することにより、鍵生成サーバ３０を省略してもよい。
又、復号サーバ５０1〜５０nが完全に信用できる場合には検証鍵を用いなくてもよい。その場合には、復元端末２０は、部分復号情報σが正しいか否かの判定を行わないため、より高速に処理を行え、効率を向上できる。
【０１０２】
（第２実施形態）
〔通信システム〕
図４に示すように、公開鍵通信システム２００は、暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０と、ネットワーク６０とを備える。暗号化端末１０と、復元端末２０と、鍵生成サーバ３０と、暗号文管理サーバ４０は、ネットワーク６０を介して、情報を送受信する。
鍵生成サーバ３０は、μビットの平文ｍの暗号化に用いる公開情報（ｇ，Ｎ，Ｈ１）と、暗号文Ｃの復号に用いる秘密鍵を生成する鍵生成装置である。鍵生成サーバ３０は、鍵生成部３１と、鍵データベース３２と、送信部３３とを備える。鍵生成部３１は、公開情報（ｇ，Ｎ，Ｈ１）と、それに対する秘密鍵とを生成する。
【０１０３】
鍵データベース３２は、公開情報（ｇ，Ｎ，Ｈ１）を記憶する。送信部３３は、鍵生成部３１が生成した公開情報（ｇ，Ｎ，Ｈ１）を暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信する。また、送信部３３は、秘密鍵２Ｌを復元端末２０に送信する。このような鍵生成サーバ３０は、コンピュータを、鍵生成部３１と、鍵データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１０４】
暗号化端末１０は、平文ｍを暗号化して暗号文Ｃを生成する暗号化装置である。暗号化端末１０は、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５とを備えている。
受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。記憶部１５は、暗号文生成部１２が事前に計算するＨ１（ｒｍｏｄＮ）とｕ＝ｇrｍｏｄＮ2とを記憶する。受信部１１は、平文ｍを受信し、暗号文生成部１２に入力してもよい。
【０１０５】
入力部１４は、外部から入力される平文ｍを取得し、暗号文生成部１２に入力する。暗号文生成部１２は、事前計算され記憶部１５に記憶されているＨ１（ｒｍｏｄＮ）及びｕ＝ｇrｍｏｄＮ2を用いて平文ｍを暗号化する。暗号文生成部１２は、暗号文Ｃを生成する際に、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する。暗号文生成部１２は、入力部１４や受信部１１から平文ｍを取得する。暗号文生成部１２は、上述した式（１）及び式（２）を計算することにより、平文ｍを暗号化して暗号文Ｃ（ｃ，ｕ）を生成することが好ましい。
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ …（１）
ｕ＝ｇrｍｏｄＮ2 …（２）
ハッシュ関数Ｈ１は、ＺN→｛０，１｝μである。なお、上記の「＊」は排他的論理和を示している。
【０１０６】
送信部１３は、暗号文生成部１２が生成した暗号文Ｃを、暗号文管理サーバ４０に送信する。記憶部１５は、後述するように暗号化する際に部分的に事前計算した結果を、一旦記憶する。このような暗号化端末１０は、コンピュータを、受信部１１と、暗号文生成部１２と、送信部１３と、入力部１４と、記憶部１５として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１０７】
暗号文管理サーバ４０は、暗号文Ｃを暗号化端末１０から受信し、暗号文Ｃを各装置に提供する暗号文管理装置である。暗号文管理サーバ４０は、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。受信部４１は、暗号化端末１０から暗号文Ｃを受信する。又、受信部４１は、復元端末２０から、暗号文Ｃの要求を受信する。更に、受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。
【０１０８】
暗号文データベース４３は、暗号文Ｃを記憶する。送信部４４は、暗号文Ｃを復元端末２０に送信する。このような暗号文管理サーバ４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
復元端末２０では以下の式を用いて復号化処理を行う。
ｕ2LｍｏｄＮ2＝（１＋２ｒａＬＮ）
である。そして、ｒｍｏｄＮ並びに式（１）及び式（２）により、平文ｍが得られる。
【０１０９】
復元端末２０は、暗号文Ｃから平文ｍを復元する復元装置である。復元端末２０は、受信部２１と、平文復元部２２と、送信部２３と、出力部２４とを備える。
受信部２１は、秘密鍵２Ｌを、鍵生成サーバ３０から受信する。又、受信部２１は、暗号文Ｃを暗号文管理サーバ４０から受信する。更に、受信部２１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信する。
【０１１０】
平文復元部２２は、秘密鍵２Ｌを用いて暗号文Ｃから平文ｍを復元する。平文復元部２２は、復元した平文ｍを出力部２４に出力する。送信部２３は、暗号文Ｃの要求や、復号要求を送信する。このような復元端末２０は、コンピュータを、受信部２１と、平文復元部２２と、送信部２３と、出力部２４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１１１】
次に、図４、図５を用いて、平文ｍの暗号化から復元において公開鍵通信システム２００が行う処理を詳細に説明する。公開鍵通信システム２００では、公開鍵暗号方式により復号を行う。
公開鍵通信システム２００が、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する暗号方式を用いる場合を説明する。本例においては、鍵生成サーバ３０の鍵生成部３１は、まず、２つの大きなΛ／２ビットの強い素数ｐ，ｑを選択し、公開情報（ｇ，Ｎ，Ｈ１）を作成する。また、素数ｐ及び素数ｑを記憶しておき、秘密鍵２Ｌを生成する。また、鍵生成サーバ３０の鍵生成部３１は、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【０１１２】
鍵生成部３１は、素数ｐ’、素数ｑ’よりＬ＝ｐ’ｑ’を構成し、公開情報（ｇ，Ｎ，Ｈ１）に対応する秘密鍵２Ｌを生成する。
鍵生成部３１は、生成した複数の秘密鍵２Ｌを、送信部３３に入力する。
送信部３３は、図５に示すように、素数ｐ，ｑを秘密にしたまま復元端末２０に対応する公開情報（ｇ，Ｎ，Ｈ１）だけを、暗号化端末１０、暗号文管理サーバ４０、復元端末２０に送信する。暗号化端末１０の受信部１１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信し、暗号文生成部１２に入力する。暗号文管理サーバ４０の受信部４１は、鍵生成サーバ３０から公開情報（ｇ，Ｎ，Ｈ１）を受信し、暗号文管理部４２に入力する。
【０１１３】
更に、送信部３３は、秘密鍵２Ｌを復元端末２０に送信する。
暗号化端末１０の暗号文生成部１２は、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，Ｈ１）を用いて暗号化する。具体的には、暗号文生成部１２は、値ｇに対して乱数ｒをｇrｍｏｄＮ2として隠し、ｒの少なくとも一部の情報を用いて平文ｍをもとに暗号文Ｃを生成する。例えば、暗号文生成部１２は、上記式（１）及び上記式（２）を計算することにより、平文ｍを暗号化し、暗号文Ｃを生成する。平文ｍは、暗号化端末１０が暗号化して秘密にしたい情報である。本実施形態における平文ｍは、秘密鍵２Ｌを用いない限り、暗号文Ｃから平文ｍを復号できないようにすることにより、暗号化端末１０が暗号化したい情報である。
【０１１４】
暗号文生成部１２は、乱数ｒを、ＺN2から選択する。暗号文生成部１２は、生成した暗号文Ｃを送信部１３に入力する。送信部１３は、図５に示すように、暗号文Ｃを暗号文管理サーバ４０に送信する。
暗号文管理サーバ４０の受信部４１は、図５に示すように、暗号化端末１０から暗号文Ｃを受信する。受信部４１は、受信した暗号文Ｃを暗号文管理部４２に入力する。暗号文管理部４２は、暗号文Ｃを、鍵生成サーバ３０から受信した公開情報（ｇ，Ｎ，Ｈ１）に対応付けて、暗号文データベース４３に格納する。
【０１１５】
その後、復元端末２０の平文復元部２２が、公開情報（ｇ，Ｎ，Ｈ１）をもとに作成した暗号文Ｃの要求を生成し、送信部２３に入力する。送信部２３は、暗号文Ｃの要求を暗号文管理サーバ４０に送信する。暗号文管理サーバ４０の受信部４１は復元端末２０から暗号文Ｃの要求を受信部４１において受信し、暗号文管理部４２は、暗号文Ｃの要求において指定されている公開情報（ｇ，Ｎ，Ｈ１）に対応する暗号文Ｃを、暗号文データベース４３から取得し、公開情報（ｇ，Ｎ，Ｈ１）と対応付けて送信部４４に入力する。送信部４４は、図２に示すように公開情報（ｇ，Ｎ，Ｈ１）と対応付けられた暗号文Ｃを復元端末２０に送信する。このように公開情報（ｇ，Ｎ，Ｈ１）は、暗号文Ｃを識別するための識別データとして用いることができる。
【０１１６】
送信部３３は、秘密鍵２Ｌを送信する。鍵生成サーバ３０の送信部３３から送信された秘密鍵２Ｌは、復元端末２０の受信部２１が受信する。
復元端末２０の受信部２１は、受信した秘密鍵２Ｌを平文復元部２２に入力する。このようにして、受信部２１は、鍵生成サーバ３０から秘密鍵２Ｌを受信する復号情報受信部として機能する。
平文復元部２２は、秘密鍵２Ｌを用いて、暗号文Ｃの一部であるｕから平文ｍを復元する。この場合、平文復元部２２は、
ｕ2L＝（１＋２ｒａＬＮ）ｍｏｄＮ2
からｒｍｏｄＮを求め、
ｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍ
より、平文ｍを得る。
【０１１７】
〔安全性強化のための変形例〕
ところで、上記の通信システムにおいて、鍵生成部３１による鍵生成、暗号化端末１０による暗号化、復元端末２０による復号において、上記とは異なる、以下の処理を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
（１）鍵生成部３１による鍵生成においては、以下の事項が異なる。
鍵生成部３１は、公開情報（ｇ，ｇ2，Ｎ，Ｍ，Ｈ１，Ｈ２）を生成する。まず、４つの大きなΛ／２ビットの強い素数ｐ，ｐ2，ｑ，ｑ2を用い、合成数Ｎ＝ｐｑ，Ｍ＝ｐ2ｑ2を作成し、ｐ，ｐ2，ｑ，ｑ2は秘密にしたままＮ，Ｍを公開情報として公開する。ここで、Ｌ＝ｐ’ｑ’，Ｌ2＝ｐ2’ｑ2’も計算して秘密にしておく。なお、Ｎ＞Ｍとする。
【０１１８】
また、ａ∈ＺN，ｂ∈Ｚ*Nをもとにｇ＝（１＋ａＮ）ｂNｍｏｄＭを、ａ2∈ＺM，ｂ2∈Ｚ*Mをもとにｇ2＝（１＋ａ2Ｍ）ｂ2MｍｏｄＭ2を、それぞれ定め、ｇ，ｇ2を公開する。また、暗号化の際に用いるハッシュ関数Ｈ１：ＺN→｛０，１｝μとＨ２：｛０，１｝μ×ＺN2×ＺN2×ＺM2×ＺM2→｛０，１｝Bも公開する。ここで復元端末２０の持つ秘密鍵は一つとするほかに、二つにする方法も考えられる。この場合には、復元端末２０では以下の式も用いて復号化処理を行う。
u’2L2ｍｏｄＭ2＝（１＋２ｒａ2Ｌ2Ｍ）
（２）暗号化端末１０による暗号化においては、以下の事項が異なる。
式（１）及び式（２）の代わりに、上述した式（９）を用いる。
【０１１９】
【数１０】
【０１２０】
（３）復号においては、以下の事項が異なる。
暗号文を復号する前に、復元端末２０、暗号文管理サーバ４０の少なくとも１箇所において暗号文の検証を行う。この場合、少なくとも復元端末２０において、暗号文の検証を行うことが望ましい。
ここで復元端末２０のもつ秘密鍵を二つ持つ方法の場合にはuに関して行う部分復号をu’についても同様に行い、復元結果がともにrかどうかの確認をする。もしも同じにならない場合は不正な暗号文として認識する。鍵が二つある場合でも計算時間の短縮のため、uもしくはu’一方に対してのみ復元しても構わない。
以上のように、復号を行う前に、少なくとも復元端末２０が暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【０１２１】
〔通信方法〕
次に、公開鍵通信システム２００を用いて行う通信方法の手順を説明する。まず、鍵生成サーバ３０が、公開情報（ｇ，Ｎ，Ｈ１）、秘密鍵２Ｌを生成する（Ｓ２０１）。鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）を復元端末２０、暗号文管理サーバ４０、暗号化端末１０に送信する（Ｓ２０２、Ｓ２０４、Ｓ２０５）。鍵生成サーバ３０は、復元端末２０に秘密鍵を送信する（Ｓ２０７）。
【０１２２】
暗号化端末１０は、例えば、式（１）及び式（２）を用い、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化し、暗号文Ｃを生成する（Ｓ２０８）。暗号化端末１０は、生成した暗号文Ｃを暗号文管理サーバ４０に送信する（Ｓ２０９）。暗号文管理サーバ４０は、受信した暗号文Ｃを暗号文データベース４３に格納する（Ｓ２１０）。
【０１２３】
復元端末２０は、暗号文Ｃを暗号文管理サーバ４０に要求する（Ｓ２１１）。暗号文管理サーバ４０は、復元端末２０の要求に応じて、暗号文データベース４３が記憶する暗号文Ｃを復元端末２０に送信する（Ｓ２１２）。
復元端末２０は、秘密鍵２Ｌを用いて乱数ｒ mod Nを計算する。そして、復元端末２０は、受信した暗号文Ｃと、計算した乱数ｒmod Nを、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する際に用いた式に代入することにより、平文ｍを復元する（Ｓ２１９）。
【０１２４】
なお、上述した安全性強化のための変形例の場合には、上記のステップＳ２１０において、又は、ステップＳ２１９の処理前において、暗号文の検証を行うことになる。この場合、少なくとも、復元端末２０が行うステップＳ２１９の処理前において、暗号文の検証を行うことが望ましい。このように、復号を行う前に、少なくとも復元端末において、暗号文の検証を行うことにより、選択暗号文攻撃に対する安全性を持たせることができる。
【０１２５】
〔効果〕
本実施形態の公開鍵通信システム２００、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０及び通信方法によれば、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する方式をしきい値暗号方式に適用できる。そのため、安全性を確保するためには計算量が多くなってしまったり、１ビットしか暗号化できない従来のしきい値暗号方式に対して、公開鍵通信システム２００では、合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて複数ビットの平文ｍを暗号化しているので安全性を確保できる。
【０１２６】
上記の暗号化処理において、ｕ＝ｇrｍｏｄＮ2、Ｈ１（ｒｍｏｄＮ）の部分を事前に計算し、暗号化する際はｃ＝Ｈ１（ｒｍｏｄＮ）＊ｍのみ計算すれば良いので、暗号化する際の計算量を少なくできることが分かる。つまり、公開鍵通信システム２００によれば、部分的に事前計算するので、処理効率の良い公開鍵暗号方式を実現することができる。なお、上述した、安全性強化のための変形例を採用した場合、暗号文の検証を行うためのデータについてもほぼ事前計算できるので、安全性を強化してもやはり処理効率の良い公開鍵暗号方式を実現することができる。
【０１２７】
また、例えば、Ｈ１（ｒｍｏｄＮ）＊ｍとしてｍを暗号化することにより、ハッシュ関数の性質からｍを求めるためには、ｒｍｏｄＮを一意に決定する必要性がある。このため、本実施形態を採用すれば、決定問題に根拠をおくかもしくは選択暗号文攻撃に対しても安全性を確保でき、安全性を付与した公開鍵値暗号方式を実現することができる。
特に、暗号化端末１０が、携帯性を重視する移動通信端末のように高速のＣＰＵを搭載することが困難な装置の場合においても、計算量が少ない本発明のしきい値暗号方式であれば利用可能である。このように、本発明の公開鍵暗号方式は、計算能力が低い暗号化装置においても、利用可能であり、暗号化を効率的に行うことができる。
【０１２８】
ところで、本実施形態の公開鍵通信システム２００は、種々の変更が可能である。例えば、復元端末２０又は暗号文管理サーバ４０が、鍵生成サーバ３０の機能の一部又は全部を備え、鍵生成装置として機能してもよい。この場合、復元端末２０が鍵生成サーバ３０の機能の全部を備えていることが望ましい。この他、暗号化端末１０、復元端末２０、鍵生成サーバ３０、暗号文管理サーバ４０のそれぞれの全部又は一部の機能のうち、少なくとも２つの機能を有する装置を公開鍵通信システム２００に備えてもよい。なお、公開鍵通信システム２００は、暗号化端末１０、暗号文管理サーバ４０を複数備えてもよい。
【０１２９】
又、上記実施の形態では、暗号文Ｃを識別するための識別データとして公開情報（ｇ，Ｎ，Ｈ１）を用いているが、公開情報以外のデータを識別データとして用いることができる。又、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）の暗号文管理サーバ４０への送信を省略してもよい。尚、この場合には、暗号文管理サーバ４０は、暗号文Ｃの要求と暗号文Ｃとを対応付けるための識別データとして、公開情報（ｇ，Ｎ，Ｈ１）以外のものを暗号文Ｃに付与し、その識別データを復元端末２０へ与え、その識別データに対応付けて暗号文Ｃを暗号文データベース４３に格納する。
あるいは、鍵生成サーバ３０は、公開情報（ｇ，Ｎ，Ｈ１）を、暗号化端末１０、復元端末２０、暗号文管理サーバ４０に送信せずに、これらの装置が自由に閲覧して取得できるようにしてもよい。
【０１３０】
（まとめ）
上述した第１実施形態及び第２実施形態は、ともに事前計算を行うことにより暗号化を高速に行えるという特徴を持ち、素因数分解型の方式のため素数生成時の問題も少ない。
さらに、第１実施形態では安全性が選択平文攻撃のもとでのみ示されるが決定問題という比較的弱い仮定の下で安全性を示せる利点もある。第２実施形態では選択暗号文攻撃のもとでの安全性が示されるという利点がある。
【産業上の利用可能性】
【０１３１】
本発明は、安全かつ効率的なしきい値暗号方式及び公開鍵暗号方式を採用した通信システムの構築に利用できる。
【図面の簡単な説明】
【０１３２】
【図１】本発明の第１実施形態に係る通信システムの構成を示す図である。
【図２】本発明の第１実施形態に係る情報の流れを示す図である。
【図３】本発明の第１実施形態に係る通信方法の手順を示すフロー図である。
【図４】本発明の第２実施形態に係る通信システムの構成を示す図である。
【図５】本発明の第２実施形態に係る情報の流れを示す図である。
【図６】本発明の第２実施形態に係る通信方法の手順を示すフロー図である。
【符号の説明】
【０１３３】
１０ 暗号化端末
１１ 受信部
１２ 暗号文生成部
１３ 送信部
１４ 入力部
１５ 記憶部
２０ 復元端末
２１ 受信部
２２ 平文復元部
２３ 送信部
２４ 出力部
３０ 鍵生成サーバ
３１ 鍵生成部
３２ 鍵データベース
３３ 送信部
４０ 暗号文管理サーバ
４１ 受信部
４２ 暗号文管理部
４３ 暗号文データベース
４４ 送信部
５０i 復号サーバ
６０ ネットワーク
１００ 通信システム
２００ 公開鍵通信システム
５１i 受信部
５２i 部分復号情報生成部
５３i 送信部
【特許請求の範囲】
【請求項１】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成装置と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号装置と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする通信システム。
【請求項２】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする暗号化装置。
【請求項３】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成手段と、前記分散鍵生成手段によって生成された分散鍵を部分復号装置に送信する分散鍵送信手段とを含むことを特徴とする鍵生成装置。
【請求項４】
ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする請求項３記載の鍵生成装置。
【請求項５】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップを含むことを特徴とする鍵生成方法。
【請求項６】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする鍵生成方法。
【請求項７】
復号の際に乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元装置。
【請求項８】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成するステップと、
暗号文と前記分散鍵記憶手段に記憶されている分散鍵とを用いて部分復号情報を生成するステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とするステップと、
を含むことを特徴とする通信方法。
【請求項９】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成装置と、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成装置によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする通信システム。
【請求項１０】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵生成手段によって生成された秘密鍵を復元装置に送信する秘密鍵送信手段とを含むことを特徴とする鍵生成装置。
【請求項１１】
ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする請求項１０記載の鍵生成装置。
【請求項１２】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップを含むことを特徴とする鍵生成方法。
【請求項１３】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする鍵生成方法。
【請求項１４】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する鍵生成ステップと、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項１５】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする暗号化装置。
【請求項１６】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成手段と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元手段と、
を含むことを特徴とする通信システム。
【請求項１７】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成ステップと、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項１８】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元手段と、
を含むことを特徴とする通信システム。
【請求項１９】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項２０】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化することを特徴とする暗号化方法。
【請求項２１】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加することを特徴とする暗号化方法。
【請求項２２】
復号の際に乱数ｒの少なくとも一部を、しきい値暗号化方式において使用する部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする暗号復元方法。
【請求項２３】
復号の前に暗号文検証用データをもとに暗号文が正しく作られたものであるか確認し、その後確認が取れた場合には復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする暗号復元方法。
【請求項２４】
復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元装置。
【請求項１】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成装置と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号装置と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする通信システム。
【請求項２】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする暗号化装置。
【請求項３】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成手段と、前記分散鍵生成手段によって生成された分散鍵を部分復号装置に送信する分散鍵送信手段とを含むことを特徴とする鍵生成装置。
【請求項４】
ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする請求項３記載の鍵生成装置。
【請求項５】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップを含むことを特徴とする鍵生成方法。
【請求項６】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する分散鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする鍵生成方法。
【請求項７】
復号の際に乱数ｒの少なくとも一部を部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元装置。
【請求項８】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成するステップと、
暗号文と前記分散鍵記憶手段に記憶されている分散鍵とを用いて部分復号情報を生成するステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とするステップと、
を含むことを特徴とする通信方法。
【請求項９】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成装置と、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化装置と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成装置によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元装置と、
を含むことを特徴とする通信システム。
【請求項１０】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵生成手段によって生成された秘密鍵を復元装置に送信する秘密鍵送信手段とを含むことを特徴とする鍵生成装置。
【請求項１１】
ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成手段を更に含むことを特徴とする請求項１０記載の鍵生成装置。
【請求項１２】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップを含むことを特徴とする鍵生成方法。
【請求項１３】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、ｇrで定義されるｕと暗号文との関係を検証するための暗号文検証用データを、作成するために必要な公開情報を作成する公開情報作成ステップとを含むことを特徴とする鍵生成方法。
【請求項１４】
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する鍵生成ステップと、
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化する場合に、合成数を法とするもとで、暗号化のために部分的な事前計算を行うステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項１５】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、前記暗号文生成手段によって生成した暗号文を暗号文管理サーバに送信する暗号文送信手段とを含むことを特徴とする暗号化装置。
【請求項１６】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成手段と、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元手段と、
を含むことを特徴とする通信システム。
【請求項１７】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号文生成ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密情報である鍵を元に分散鍵を生成する鍵生成ステップと、
暗号文と分散鍵とを用いて部分復号情報を生成する部分復号ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を前記部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項１８】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化手段と、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成手段と、
前記検証用データを用いて暗号文について検証を行う検証手段と、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元手段と、
を含むことを特徴とする通信システム。
【請求項１９】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加して、合成数を法とするもとで、暗号化のために部分的な事前計算を行う暗号化ステップと、
合成数を法として計算できるｇrで定義されるｕから乱数ｒの少なくとも一部を取出す際に必要となる秘密鍵を生成する秘密鍵生成ステップと、
前記検証用データを用いて暗号文について検証を行う検証ステップと、
復号の際に乱数ｒの少なくとも一部を、前記秘密鍵生成手段によって生成された秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求める復元ステップと、
を含むことを特徴とする通信方法。
【請求項２０】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを暗号化することを特徴とする暗号化方法。
【請求項２１】
合成数を法とするもとで合成数とは素なｇに対して乱数ｒをｇrとして隠し、乱数ｒの少なくとも一部を用いて平文ｍを一度だけ暗号化し、更に暗号文検証用データを付加することを特徴とする暗号化方法。
【請求項２２】
復号の際に乱数ｒの少なくとも一部を、しきい値暗号化方式において使用する部分復号情報を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする暗号復元方法。
【請求項２３】
復号の前に暗号文検証用データをもとに暗号文が正しく作られたものであるか確認し、その後確認が取れた場合には復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする暗号復元方法。
【請求項２４】
復号の際に乱数ｒの少なくとも一部を、公開鍵暗号化方式において使用する秘密鍵を用いて復元し、復元した乱数ｒの少なくとも一部を用いて平文ｍを求めることを特徴とする復元装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００６−２２７４１１（Ｐ２００６−２２７４１１Ａ）
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願番号】特願２００５−４２６４６（Ｐ２００５−４２６４６）
【出願日】平成１７年２月１８日（２００５．２．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会，電子情報通信学会技術研究報告，信学技報 Ｖｏｌ．１０４，Ｎｏ．４２１，２００４年１１月１日発行
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【出願人】（５０４１８２２５５）国立大学法人横浜国立大学 (429)
【Ｆターム（参考）】
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願日】平成１７年２月１８日（２００５．２．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会，電子情報通信学会技術研究報告，信学技報 Ｖｏｌ．１０４，Ｎｏ．４２１，２００４年１１月１日発行
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【出願人】（５０４１８２２５５）国立大学法人横浜国立大学 (429)
【Ｆターム（参考）】
[ Back to top ]