(57)【要約】【課題】署名対象データの正当性をより確実に検証する。【解決手段】署名装置１４は、検証鍵ｖｋ及び暗号文ｃをハッシュ関数Ｈ２に入力してハッシュ値ｕを生成するハッシュ値生成部１４ｃと、ハッシュ値ｕ及び暗号化に用いた乱数ｓを用いて暗号文ｃに対する署名情報ｖを生成する署名情報生成部１４ｄと、署名対象データである暗号文ｃに、ハッシュ値ｕ及び署名情報ｖを含む署名σと、検証鍵ｖｋとを付加する署名部１４ｅとを備える。【選択図】図２
2006319485.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成するハッシュ値生成部と、
前記ハッシュ値を用いて前記署名対象データに対する署名情報を生成する署名情報生成部と、
前記署名対象データに、前記ハッシュ値及び前記署名情報を含む署名を付加する署名部と
を備えることを特徴とする署名装置。
【請求項２】
平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成する暗号文生成部と、
前記乱数を用いて検証鍵を生成する検証鍵生成部と、
少なくとも前記検証鍵及び前記暗号文をハッシュ関数に入力してハッシュ値を生成するハッシュ値生成部と、
前記ハッシュ値及び前記乱数を用いて前記暗号文に対する署名情報を生成する署名情報生成部と、
前記暗号文に、前記ハッシュ値及び前記署名情報を含む署名と前記検証鍵とを付加する署名部と
を備えることを特徴とする署名暗号化装置。
【請求項３】
署名対象データに付加された、ハッシュ値及び該ハッシュ値を用いて生成された署名情報を含む署名と、検証鍵と、少なくとも前記検証鍵及び前記署名対象データの入力を受けて前記ハッシュ値を生成するハッシュ関数とを用いて、前記署名対象データの正当性を検証する検証部を備えることを特徴とする検証装置。
【請求項４】
署名対象データである暗号文に付加された、ハッシュ値及び該ハッシュ値を用いて生成された署名情報を含む署名及び検証鍵と、少なくとも前記検証鍵及び前記暗号文の入力を受けて前記ハッシュ値を生成するハッシュ関数とを用いて、前記暗号文の正当性が確認された後に、前記暗号文の復号を行う復号部を備えることを特徴とする復号装置。
【請求項５】
署名対象データである暗号文を部分的に復号して生成された複数の部分復号情報を受信する受信部と、
前記暗号文に付加された、ハッシュ値及び該ハッシュ値を用いて生成された署名情報を含む署名及び検証鍵と、少なくとも前記検証鍵及び前記暗号文の入力を受けて前記ハッシュ値を生成するハッシュ関数とを用いて、前記暗号文の正当性が確認された後に、前記複数の部分復号情報を結合し、平文を復元する復元部と
を備えることを特徴とする復元装置。
【請求項６】
署名情報を生成するためのハッシュ値を少なくとも検証鍵及び署名対象データの入力を受けて生成するハッシュ関数を、前記署名対象データに前記ハッシュ値及び前記署名情報を含む署名を付加する署名装置、及び、前記署名対象データに付加された前記署名と、前記検証鍵と、前記ハッシュ関数とを用いて前記署名対象データの正当性を検証する検証装置に指示する指示部を備えることを特徴とする情報提供装置。
【請求項７】
少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成し、該ハッシュ値を用いて前記署名対象データに対する署名情報を生成し、前記署名対象データに前記ハッシュ値及び前記署名情報を含む署名を付加する署名装置と、
前記署名と、前記検証鍵と、前記ハッシュ関数とを用いて、前記署名対象データの正当性を検証する検証装置と
を備えることを特徴とする通信システム。
【請求項８】
しきい値暗号方式を用いる通信システムであって、
平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成し、前記乱数を用いて検証鍵を生成し、少なくとも前記検証鍵及び前記暗号文をハッシュ関数に入力してハッシュ値を生成し、前記ハッシュ値及び前記乱数を用いて前記暗号文に対する署名情報を生成し、前記暗号文に、前記ハッシュ値及び前記署名情報を含む署名と前記検証鍵とを付加する署名暗号化装置と、
前記署名と、前記検証鍵と、前記ハッシュ関数とを用いて、前記暗号文の正当性を検証する検証装置と、
前記暗号文の正当性が確認された後に、前記暗号文を部分的に復号して複数の部分復号情報を生成する復号装置と、
前記複数の部分復号情報を結合し、前記平文を復元する復元装置と
を備えることを特徴とする通信システム。
【請求項９】
少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成し、
該ハッシュ値を用いて前記署名対象データに対する署名情報を生成し、
前記署名対象データに前記ハッシュ値及び前記署名情報を含む署名を付加することを特徴とする署名方法。 
【請求項１０】
平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成し、
前記乱数を用いて検証鍵を生成し、
少なくとも前記検証鍵及び前記暗号文をハッシュ関数に入力してハッシュ値を生成し、
前記ハッシュ値及び前記乱数を用いて前記暗号文に対する署名情報を生成し、
前記暗号文に、前記ハッシュ値及び前記署名情報を含む署名と前記検証鍵とを付加することを特徴とする署名暗号化方法。
【請求項１１】
署名対象データに付加された、ハッシュ値及び該ハッシュ値を用いて生成された署名情報を含む署名と、検証鍵と、少なくとも前記検証鍵及び前記署名対象データの入力を受けて前記ハッシュ値を生成するハッシュ関数とを用いて、前記署名対象データの正当性を検証することを特徴とする検証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名装置、署名暗号化装置、検証装置、復号装置、復元装置、情報提供装置、通信システム、署名方法、署名暗号化方法及び検証方法に関する。
【背景技術】
【０００２】
従来、安全な通信を行うために公開鍵暗号方式が用いられている。公開鍵暗号方式では、公開鍵に対する復号鍵を安全に保管しておくことが課題の一つになっている。この課題に対する解決方法の一つとして、しきい値暗号方式が提案されている。しきい値暗号方式とは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、分散鍵を持つ複数の装置が協力しなければ、平文を復元できないようにした方式である。
【０００３】
しきい値暗号方式として、例えば、素因数分解型の暗号方式を用いる方法(例えば、非特許文献１、非特許文献２、非特許文献３、非特許文献４参照)や、離散対数型の暗号方式を用いる方法(例えば、非特許文献５参照)などが提案されている。
【０００４】
更に、しきい値暗号方式には適用できないものの、効率良く暗号化や復号を行うことができ、安全性にも優れた公開鍵暗号方式が提案されている（例えば、非特許文献６参照）。
【０００５】
また、送信データに署名を付加して送信し、付加された署名を用いて送信データの正当性を検証することが行われている。
【非特許文献１】Pierre-Alain Fouque and David Pointcheval, “Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks”， ASIACRYPT 2001, pp.351-368, 2001年
【非特許文献２】石原武、青野博、本郷節之、四方順司、「Paillier 暗号をもとにしたしきい値暗号について」、信学技報ISEC2004-83、電子情報通信学会,2004年11月
【非特許文献３】J.Katz and M.Yung, “Threshold Cryptosystems Based on Factoring”, ASIACRYPT 2002, Lecture Notes in Computer Science, 2501, pp.192-205, Springer-Verlag, 2002年
【非特許文献４】石原武、青野博、本郷節之、四方順司、「しきい値型Paillier 暗号の改良」、信学技報ISEC2004-12、電子情報通信学会、2004年5月
【非特許文献５】V.Shoup and R.Gennaro, Securing “Threshold Cryptosystems against Chosen Ciphertext Attack”, Journal of Cryptology, vol.15,no.2, pp.75-96, 2002年
【非特許文献６】Masayuki Abe, “Combining Encryption and Proof of Knowledge in the Random Oracle Model”, The Computer Journal, Volume 47,pp.58-70, 2004年
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１〜３，５に記載の技術は選択暗号文攻撃に対して高い安全性を確保できるものの、暗号化及び復号の際に、べき乗演算を数多く行う必要があり、効率的ではなかった。
【０００７】
特に、非特許文献３に記載の素因数分解型のしきい値暗号方式では、法Ｎのもとでの計算により暗号化及び復号を行い、選択暗号文攻撃に対する安全性を確保できるものの、１ビットしか暗号化できなかった。そのため、選択暗号文攻撃に対する安全性を確保するために暗号文のサイズが大きくなり、暗号化及び復号の効率が悪く、実用的ではなかった。
【０００８】
また、非特許文献４に記載の技術は暗号化のための計算量を少なく抑えられ、選択平文攻撃に対して高い安全性を確保できるものの、選択暗号文攻撃に対しては十分な安全性を確保することができなかった。
【０００９】
更に、非特許文献６に記載の公開鍵暗号方式は、効率も良く、選択暗号文攻撃に対しても安全性が示せるものの、しきい値暗号方式に適用することができなかった。
【００１０】
また、署名対象データの正当性をより確実に検証することが可能な、より信頼性の高い署名が求められている。
【００１１】
そこで、本発明は、署名対象データの正当性をより確実に検証することを目的とする。また、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に暗号化や復号などの処理を行うことを目的とする。
【課題を解決するための手段】
【００１２】
本発明に係る署名装置は、少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成するハッシュ値生成部と、ハッシュ値を用いて署名対象データに対する署名情報を生成する署名情報生成部と、署名対象データにハッシュ値及び署名情報を含む署名を付加する署名部とを備えることを特徴とする。検証鍵は、署名の正当性の検証に用いられる鍵である。
【００１３】
このような署名装置によれば、検証鍵及び署名対象データをハッシュ関数に入力して得られたハッシュ値を用いて署名情報を生成し、署名対象データにハッシュ値及び署名情報を含む署名を付加することができる。このように検証鍵及び署名対象データをハッシュ関数に入力して得られたハッシュ値を用いた署名を付加することにより、署名対象データの偽造を従来よりも多くの場合において検出できる。よって、署名と検証鍵を用いて、署名対象データの正当性をより確実に検証することができる。「署名対象データが正当である」とは、送信側が送信した署名対象データと、受信側が受信した署名対象データが一致していることをいう。
【００１４】
本発明の署名暗号化装置は、平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成する暗号文生成部と、乱数を用いて検証鍵を生成する検証鍵生成部と、少なくとも検証鍵及び暗号文をハッシュ関数に入力してハッシュ値を生成するハッシュ値生成部と、ハッシュ値及び乱数を用いて暗号文に対する署名情報を生成する署名情報生成部と、暗号文に、ハッシュ値及び署名情報を含む署名と検証鍵とを付加する署名部とを備えることを特徴とする。
【００１５】
このような署名暗号化装置によれば、同一の乱数を用いて、平文の暗号化と検証鍵の生成を行うことができる。これにより、検証鍵を用いて検証される署名が、暗号文の正当性を証明することができる。更に、署名暗号化装置は、得られた検証鍵及び暗号文をハッシュ関数に入力してハッシュ値を生成し、ハッシュ値と乱数を用いて署名情報を生成できる。そして、署名暗号化装置は、このようにして得られたハッシュ値と署名情報を含む署名と、検証鍵を暗号文に付加することができる。これによれば、暗号文の正当性を証明する署名の安全性をより向上させることができ、署名と検証鍵を用いて暗号文の正当性をより確実に検証できる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に暗号化や復号などの処理を行うことができる。
【００１６】
本発明の検証装置は、署名対象データに付加された、ハッシュ値及びそのハッシュ値を用いて生成された署名情報を含む署名と、検証鍵と、少なくとも検証鍵及び署名対象データの入力を受けてハッシュ値を生成するハッシュ関数とを用いて、署名対象データの正当性を検証する検証部を備えることを特徴とする。
【００１７】
このような検証装置によれば、署名と、検証鍵と、検証鍵及び署名対象データの入力を受けてハッシュ値を生成するハッシュ関数とを用いることにより、署名対象データの偽造を検出できる。よって、署名対象データの正当性をより確実に検証することができる。
【００１８】
本発明に係る復号装置は、署名対象データである暗号文に付加された、ハッシュ値及びそのハッシュ値を用いて生成された署名情報を含む署名及び検証鍵と、少なくとも検証鍵及び暗号文の入力を受けてハッシュ値を生成するハッシュ関数とを用いて、暗号文の正当性が確認された後に、暗号文の復号を行う復号部を備えることを特徴とする。
【００１９】
このような復号装置によれば、暗号文の正当性が精度の高い検証により確認された後に、暗号文を復号することができる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に復号を行うことができる。
【００２０】
本発明に係る復元装置は、署名対象データである暗号文を部分的に復号して生成された複数の部分復号情報を受信する受信部と、署名対象データである暗号文に付加された、ハッシュ値及びそのハッシュ値を用いて生成された署名情報を含む署名及び検証鍵と、少なくとも検証鍵及び暗号文の入力を受けてハッシュ値を生成するハッシュ関数とを用いて、暗号文の正当性が確認された後に、複数の部分復号情報を結合し、平文を復元する復元部とを備えることを特徴とする。
【００２１】
このような復元装置によれば、暗号文の正当性が精度の高い検証により確認された後に、部分復号情報を結合して暗号文から平文を復元することができる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に復元を行うことができる。
【００２２】
情報提供装置は、署名情報を生成するためのハッシュ値を少なくとも検証鍵及び署名対象データの入力を受けて生成するハッシュ関数を、署名対象データにハッシュ値及び署名情報を含む署名を付加する署名装置、及び、署名対象データに付加された署名と、検証鍵と、ハッシュ関数とを用いて署名対象データの正当性を検証する検証装置に指示する指示部を備えることを特徴とする。
【００２３】
このような情報提供装置によれば、検証鍵及び署名対象データをハッシュ関数に入力して得られたハッシュ値を用いた署名やその検証に寄与することができる。よって、署名対象データの正当性のより確実な検証に寄与できる。
【００２４】
本発明に係る通信システムは、少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成し、そのハッシュ値を用いて署名対象データに対する署名情報を生成し、署名対象データにハッシュ値及び署名情報含む署名を付加する署名装置と、署名と、検証鍵と、ハッシュ関数とを用いて、署名対象データの正当性を検証する検証装置とを備えることを特徴とする。
【００２５】
また、本発明に係る他の通信システムは、しきい値暗号方式を用いる通信システムであって、平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成し、乱数を用いて検証鍵を生成し、少なくとも検証鍵及び暗号文をハッシュ関数に入力してハッシュ値を生成し、ハッシュ値及び乱数を用いて暗号文に対する署名情報を生成し、暗号文に、ハッシュ値及び署名情報を含む署名と検証鍵とを付加する署名暗号化装置と、署名と、検証鍵と、ハッシュ関数とを用いて、暗号文の正当性を検証する検証装置と、暗号文の正当性が確認された後に、暗号文を部分的に復号して複数の部分復号情報を生成する復号装置と、複数の部分復号情報を結合し、平文を復元する復元装置とを備えることを特徴とする。
【００２６】
本発明に係る署名方法は、少なくとも検証鍵及び署名対象データをハッシュ関数に入力してハッシュ値を生成し、そのハッシュ値を用いて署名対象データに対する署名情報を生成し、署名対象データにハッシュ値及び署名情報を含む署名を付加することを特徴とする。
【００２７】
本発明に係る署名暗号化方法は、平文を乱数を用いて暗号化し、署名対象データとして暗号文を生成し、乱数を用いて検証鍵を生成し、少なくとも検証鍵及び暗号文をハッシュ関数に入力してハッシュ値を生成し、ハッシュ値及び乱数を用いて暗号文に対する署名情報を生成し、暗号文に、ハッシュ値及び署名情報を含む署名と検証鍵とを付加することを特徴とする。
【００２８】
本発明に係る検証方法は、署名対象データに付加された、ハッシュ値及びそのハッシュ値を用いて生成された署名情報を含む署名と、検証鍵と、少なくとも検証鍵及び署名対象データの入力を受けてハッシュ値を生成するハッシュ関数とを用いて、署名対象データの正当性を検証することを特徴とする。
【発明の効果】
【００２９】
以上説明したように、本発明によれば、署名対象データの正当性をより確実に検証することができる。また、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に暗号化や復号などの処理を行うことができる。
【発明を実施するための最良の形態】
【００３０】
本実施形態では、合成数ＮをＮ＝ｐｑと定義する。ｐ，ｑは異なる奇素数とし、共にΛ／２ビットとする。ＺＮは、０以上Ｎ未満の整数の集合とする。Ｚ＊Ｎは、ＺＮの要素のうちＮと互いに素な整数の集合とする。ＱＮは、法Ｎのもとで平方余剰である整数であり、かつ、Ｎと互いに素な値の集合とする。また、べき乗演算は、特に記載がない限り、法Ｎのもとで行うものとする。
【００３１】
（通信システム）
図１に示すように、通信システム１００は、署名暗号化装置１０と、復元装置２０と、情報提供装置３０と、暗号文管理装置４０と、複数の検証復号装置５０１〜５０ｎと、ネットワーク６０とを備える。署名暗号化装置１０と、復元装置２０と、情報提供装置３０と、暗号文管理装置４０と、複数の検証復号装置５０１〜５０ｎは、ネットワーク６０を介して情報を送受信する。通信システム１００は、しきい値暗号方式を用いる。
【００３２】
次に、各装置について図１〜図３を用いてより詳細に説明する。署名暗号化装置１０は、署名対象データに署名σを付加して署名を行う。また、署名暗号化装置１０は、平文ｍを暗号化し、署名対象データとして暗号文ｃを生成する。図２に示すように、署名暗号化装置１０は、受信部１１と、乱数ｓ生成部１２と、暗号文生成部１３と、署名装置１４と、送信部１５とを備える。署名装置１４は、検証鍵生成部１４ａと、乱数ｒ生成部１４ｂと、ハッシュ値生成部１４ｃと、署名情報生成部１４ｄと、署名部１４ｅとを備える。
【００３３】
受信部１１は、情報提供装置３０から公開情報を受信する。公開情報には、例えば、公開鍵情報ｐｋと、暗号化に用いるハッシュ関数Ｈ１と、署名に用いるハッシュ関数Ｈ２などが含まれる。公開鍵情報ｐｋには、lビットの平文ｍの暗号化に用いる（Ｎ，ｅ）（Ｎ＝ｐｑ）が含まれる。受信部１１は、公開情報を、乱数ｓ生成部１２と、暗号文生成部１３と、検証鍵生成部１４ａと、乱数ｒ生成部１４ｂと、ハッシュ値生成部１４ｃと、署名情報生成部１４ｄに入力する。
【００３４】
乱数ｓ生成部１２は、平文ｍの暗号化、検証鍵ｖｋの生成に用いる乱数ｓを生成する。乱数ｓは、署名情報ｖの生成にも用いることができる。乱数ｓ生成部１２は、例えば、取得した公開鍵情報ｐｋに基づいて、乱数ｓが取り得る値の範囲、即ち、定義域を決定する。乱数ｓ生成部１２は、決定した定義域に含まれる値の中から乱数ｓとなる値を一様な確率で一つ選択し、乱数ｓを生成することができる。例えば、乱数ｓ生成部１２は、公開鍵情報ｐｋ＝（Ｎ，ｅ）に基づいて、定義域を｛０、Ｎ−１｝と決定する。そして、乱数ｓ生成部１２は、定義域｛０、Ｎ−１｝の範囲内において、一様な確率で値を一つ選択し、乱数ｓとすることができる。乱数ｓ生成部１２は、生成した乱数ｓを、暗号文生成部１３、検証鍵生成部１４ａと、署名情報生成部１４ｄに入力する。
【００３５】
暗号文生成部１３は、平文ｍを乱数ｓを用いて暗号化し、署名対象データとして暗号文ｃを生成する。暗号文生成部１３は、例えば、図３に示すように、署名暗号化装置１０に外部から入力される平文ｍや、受信部１１が受信した平文ｍなどを暗号化できる。暗号文生成部１３は、取得した公開鍵情報ｐｋ＝（ｅ，Ｎ）と乱数ｓとを用いて平文ｍを暗号化できる。例えば、暗号文生成部１３は、公開情報に含まれるハッシュ関数Ｈ１を用いて、しきい値暗号方式に従って暗号化できる。具体的には、暗号文生成部１３は、以下に示す（１）式を計算することにより、公開鍵情報ｐｋ＝（ｅ，Ｎ）と、乱数ｓと、ハッシュ関数Ｈ１を用いて平文ｍを暗号化し、暗号文ｃを生成できる。
【００３６】
ｃ＝｛ｓｅ、ｍ＊Ｈ１（ｓｅｍｏｄＮ，ｓ）｝    （１）式
（１）式において「＊」は、排他的論理和を示す。暗号文生成部１３は、生成した暗号文ｃを、ハッシュ値生成部１４ｃと、署名部１４ｅに入力する。
【００３７】
署名装置１４は、署名対象データに署名σを付加して署名を行う。そのために、署名装置１４は、署名σに含まれるハッシュ値ｕと署名情報ｖとを生成する。また、署名装置１４は、署名σの生成及び署名σの正当性の検証に用いられる検証鍵ｖｋも生成する。
【００３８】
検証鍵生成部１４ａは、暗号文ｃの生成に用いた乱数ｓを用いて検証鍵ｖｋを生成する。例えば、検証鍵生成部１４ａは、取得した公開鍵情報ｐｋ＝（Ｎ，ｅ）と乱数ｓとを用いて検証鍵ｖｋを生成する。例えば、検証鍵生成部１４ａは、以下に示す（２）式を計算することにより、検証鍵ｖｋを生成できる。
【００３９】
ｖｋ＝ｓｅ  （２）式
尚、検証鍵生成部１４ａは、（２）式以外にも、乱数ｓを入力することにより、検証鍵ｖｋを生成する種々の関数を用いることができる。検証鍵生成部１４ａは、生成した検証鍵ｖｋを、ハッシュ値生成部１４ｃと、署名部１４ｅとに入力する。
【００４０】
乱数ｒ生成部１４ｂは、署名σの生成、具体的には、ハッシュ値ｕの生成、署名情報ｖの生成に用いる乱数ｒを生成する。乱数ｒ生成部１４ｂは、例えば、取得した公開鍵情報ｐｋに基づいて乱数ｒが取り得る値の範囲、即ち、定義域を決定する。乱数ｒ生成部１４ｂは、決定した定義域に含まれる値の中から乱数ｒとなる値を一様な確率で一つ選択し、乱数ｒを生成することができる。例えば、乱数ｒ生成部１４ｂは、公開鍵情報ｐｋ＝（Ｎ，ｅ）に基づいて、定義域を｛０、Ｎ−１｝と決定する。そして、乱数ｒ生成部１４ｂは、定義域｛０、Ｎ−１｝の範囲内において、一様な確率で値を一つ選択し、乱数ｒとすることができる。乱数ｒ生成部１４ｂは、生成した乱数ｒを、ハッシュ値生成部１４ｃと、署名情報生成部１４ｄに入力する
ハッシュ値生成部１４ｃは、少なくとも検証鍵ｖｋ及び署名対象データである暗号文ｃをハッシュ関数に入力して、ハッシュ値ｕを生成する。ハッシュ値ｕは、署名σの一部となる。更に、ハッシュ値ｕは、署名情報ｖの生成に用いられる。
【００４１】
例えば、ハッシュ値生成部１４ｃは、取得した検証鍵ｖｋと、暗号文ｃと、乱数ｒと、公開鍵情報ｐｋ＝（Ｎ，ｅ）とを用いて、ハッシュ値ｕを生成できる。ハッシュ値生成部１４ｃは、ハッシュ関数として公開情報に含まれるハッシュ関数Ｈ２を用いることができる。乱数ｒは、例えば、乱数ｒと公開鍵情報ｐｋとを用いて演算を行い、その演算結果の形でハッシュ関数に入力できる。
【００４２】
具体的には、ハッシュ値生成部１４ｃは、検証鍵ｖｋ＝ｓｅと、暗号文ｃと、乱数ｒを公開鍵情報ｐｋを用いて演算した結果ｒｅとを、ハッシュ関数Ｈ２に入力し、ハッシュ値ｕを生成できる。ハッシュ値生成部１４ｃは、ハッシュ関数Ｈ２に入力する複数のデータを１つに連接し、ハッシュ関数Ｈ２に入力する。ハッシュ値生成部１４ｃは、生成したハッシュ値ｕを、署名情報生成部１４ｄと、署名部１４ｅに入力する。
【００４３】
署名情報生成部１４ｄは、ハッシュ値ｕを用いて署名対象データに対する署名情報ｖを生成する。署名対象データが暗号文の場合、署名情報生成部１４ｄは、ハッシュ値ｕと、平文ｍの暗号化及び検証鍵ｖｋの生成に用いた乱数ｓとを用いて、暗号文に対する署名情報ｖを生成する。また、ハッシュ値ｕの生成に乱数ｒを用いた場合、署名情報生成部１４ｄは、乱数ｒを用いて署名情報ｖを生成する。更に、署名情報生成部１４ｄは、公開鍵情報ｐｋも用いて署名情報ｖを生成してもよい。例えば、署名情報生成部１４ｄは、以下に示す（３）式を計算することにより、取得したハッシュ値ｕ、乱数ｓ、乱数ｒ、公開鍵情報ｐｋを用いて署名情報ｖを生成できる。
【００４４】
ｖ＝ｒｓｕ  ｍｏｄＮ  （３）式
尚、署名情報生成部１４ｄは、（３）式以外にも、少なくともハッシュ値ｕ及び乱数ｓを入力することにより、署名情報ｖを生成する種々の関数を用いることができる。署名情報生成部１４ｄは、生成した署名情報ｖを署名部１４ｅに入力する。
【００４５】
署名部１４ｅは、署名対象データにハッシュ値ｕ及び署名情報ｖを含む署名σを付加し、署名を行う。署名部１４ｅは、署名対象データである暗号文ｃに、ハッシュ値ｕ及び署名情報ｖを含む署名σ＝（ｕ，ｖ）と、検証鍵ｖｋとを付加する。即ち、署名部１４ｅは、署名σ＝（ｕ，ｖ）及び検証鍵ｖｋを暗号文ｃに付加することにより、安全性を補強した補強暗号文Ｃを生成できる。
【００４６】
補強暗号文Ｃは、暗号文ｃに、署名σ＝（ｕ，ｖ）と検証鍵ｖｋとが付加されたものであるため、Ｃ＝（ｃ,ｖｋ,σ）と表すことができる。署名部１４ｅは、補強暗号文Ｃに含まれる各要素（ｃ,ｖｋ,σ）又は各要素の一部が重複している場合には、重複している一方を省略した補強暗号文Ｃを生成することができる。
【００４７】
例えば、（１）式で表される暗号文ｃには、（２）式で表される検証鍵ｖｋ＝ｓｅが含まれている。そのため、署名部１４ｅは、検証鍵ｖｋを省略し、補強暗号文Ｃとして（ｃ，σ）を生成できる。あるいは、検証鍵ｖｋの一部のデータが、暗号文ｃに含まれている場合には、署名部１４ｅは、検証鍵ｖｋのうち暗号文ｃに含まれていないデータｖｋ’を暗号文ｃに付加し、補強暗号文Ｃとして（ｃ，ｖｋ’，σ）を生成できる。即ち、共通の要素があれば補強暗号文Ｃに含まれる要素を減らすことができる。反対に、補強暗号文Ｃは、暗号文ｃ、検証鍵ｖｋ、署名σ以外のデータを含んでも構わない。よって、補強暗号文Ｃ＝（ｃ，ｖｋ，σ）が常に成立するとは限らない。署名部１４ｅは、補強暗号文Ｃを送信部１５に入力する。
【００４８】
送信部１５は、署名σと検証鍵ｖｋを付加した暗号文ｃ、即ち、補強暗号文Ｃを、図３に示すように暗号文管理装置４０に送信する。
【００４９】
このようにして、署名装置１４は、少なくとも検証鍵ｖｋ及び署名対象データをハッシュ関数Ｈ２に入力してハッシュ値ｕを生成できる。また、署名装置１４は、そのハッシュ値ｕを用いて署名対象データに対する署名情報ｖを生成できる。そして、署名装置１４は、署名対象データである暗号文ｃにハッシュ値ｕ及び署名情報ｖを含む署名σを付加することができる。
【００５０】
そして、署名装置１４を含む署名暗号化装置１０は、平文ｍを乱数ｓを用いて暗号化し、署名対象データとして暗号文ｃを生成できる。また、署名暗号化装置１０は、乱数ｓを用いて検証鍵ｖｋを生成し、少なくとも検証鍵ｖｋ及び暗号文ｃをハッシュ関数Ｈ２に入力してハッシュ値ｕを生成できる。更に、署名暗号化装置１０は、ハッシュ値ｕ及び乱数ｓを用いて暗号文ｃに対する署名情報ｖを生成できる。そして、署名暗号化装置１０は、暗号文ｃに、ハッシュ値ｕ及び署名情報ｖを含む署名σと検証鍵ｖｋとを付加することができる。
【００５１】
このような署名暗号化装置１０は、コンピュータを、受信部１１と、乱数ｓ生成部１２と、暗号文生成部１３と、検証鍵生成部１４ａと、乱数ｒ生成部１４ｂと、ハッシュ値生成部１４ｃと、署名情報生成部１４ｄと、署名部１４ｅと、送信部１５として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００５２】
情報提供装置３０は、署名、暗号化、復号に必要な各種情報を、情報の種類に応じて各装置に提供する。情報提供装置３０は、提供情報生成部３１と、公開情報データベース３２と、送信部３３とを備える。
【００５３】
提供情報生成部３１は、公開鍵情報ｐｋ＝（Ｎ，ｅ）を生成する。提供情報生成部３１は、署名情報ｖを生成するためのハッシュ値ｕを、少なくとも検証鍵ｖｋ及び署名対象データの入力を受けて生成するハッシュ関数Ｈ２と、暗号化に用いるハッシュ関数Ｈ１を決定する。これらの情報、即ち、公開鍵情報ｐｋ＝（Ｎ，ｅ）、ハッシュ関数Ｈ１、ハッシュ関数Ｈ２は公開情報である。以下、これらの公開情報をまとめて、「公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）」と表す。更に、提供情報生成部３１は、公開鍵情報ｐｋに対する秘密情報ｄを生成する。
【００５４】
そして、提供情報生成部３１は、秘密情報ｄを複数（ｎ個）に分散した複数（ｎ個）の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎを生成する。複数の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎが暗号文ｃの復号鍵となる。また、提供情報生成部３１は、暗号文ｃを部分的に復号して得られる複数（ｎ個）の部分復号情報δ1〜δi〜δｎが、正しく復号されたか否かを検証するための複数（ｎ個）の部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎと、それらの生成元νを生成する。
【００５５】
以下、（ｔ，ｎ）しきい値暗号方式により復号を行う場合を例にとって説明する。（ｔ，ｎ）しきい値暗号方式とは、ｎ個の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎを用いて生成されるｎ個の部分復号情報δ1〜δi〜δｎのうち、ｔ個の部分復号情報を用いれば、平文ｍが復元できるしきい値暗号方式である。よって、「ｔ」は、（ｔ，ｎ）しきい値暗号方式において必要な部分復号情報の数を表す。「ｎ」は、検証復号装置５０1〜５０i〜５０ｎの数に等しい。
【００５６】
提供情報生成部３１は、例えば、既存のハッシュ関数の中から、検証鍵ｖｋや署名対象データなどの複数のデータを１つに連接して入力可能なハッシュ関数Ｈ２を決定する。また、提供情報生成部３１は、既存のハッシュ関数の中から、ハッシュ関数Ｈ１も決定する。
【００５７】
提供情報生成部３１は、公開鍵情報ｐｋを例えば以下のようにして生成できる。提供情報生成部３１は、まず、２つの強い素数ｐ，ｑを選択し、その積を計算して、合成数Ｎ＝ｐｑを生成する。強い素数ｐ，ｑとは、ｐ＝２ｐ’＋１においてｐ’が素数であり、ｑ＝２ｑ’＋１においてｑ’が素数であることをいう。
【００５８】
更に、提供情報生成部３１は、複数の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎの数ｎよりも大きな素数をｅとして選択する。鍵生成部３１は、ｅとして、ＧＣＤ（ｅ，ｐｑ（ｐ−１）（ｑ−１））＝１と、ＧＣＤ（ｅ，２ｎ！）＝１とを満たす値を選択する。「ＧＣＤ（Ｘ，Ｙ）」は、ＸとＹの最大公約数を表す。このようにして、提供情報生成部３１は、公開情報（ｅ，Ｎ）を生成する。
【００５９】
秘密情報ｄは、法Ｌのもとで、公開鍵情報の一部ｅの逆元となる。ｐ’とｑ’の積を「Ｌ」と定義する。即ち、Ｌ＝ｐ’ｑ’と定義する。秘密情報ｄは、ｅｄ≡１ｍｏｄＬを満たす。そのため、提供情報生成部３１は、例えば、ｅｄ≡１ｍｏｄＬにｅ及びＬを代入し、拡張ユークリッドアルゴリズム（Euclidian algorithm）を用いることにより、秘密情報ｄを生成できる。
【００６０】
提供情報生成部３１は、秘密情報ｄを複数（ｎ個）に分散して、複数（ｎ個）の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎを生成する。例えば、提供情報生成部３１は、Shamirにより提案された方法などを用いて、秘密情報ｄを複数に分散できる。具体的には、鍵生成部３１は、ａｉ∈ＵＺＬと定義する。尚、「ＺX」とは、０以上Ｘ未満の整数の集合（ＺX＝Ｚ／ＸＺ）を表す。また、「Ｘ∈ＵＧ」は、集合Ｇから一様な確率で要素Ｘを選択することを表す。
【００６１】
この場合、提供情報生成部３１は、以下に示す（４）式を計算することにより、複数の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎを生成できる。具体的には、提供情報生成部３１は、（４）式を用いて、ｓｋi＝ｆ（ｉ）ｍｏｄＬを計算することにより分散鍵ｓｋiを生成できる。
【数１】
2006319485.tif 000003
【００６２】
提供情報生成部３１は、複数（ｎ個）の部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎを例えば以下のようにして生成できる。提供情報生成部３１は、例えば、以下に示す（５）式を計算することにより部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎを生成できる。
【数２】
2006319485.tif 000004
【００６３】
提供情報生成部３１は、生成、決定した公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を公開情報データベース３２に格納する。公開情報データベース３２は、公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を保持する。提供情報生成部３１は、生成した複数（ｎ個）の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎ、複数（ｎ個）の部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎ、部分復号検証鍵の生成元νを送信部３３に入力する。
【００６４】
送信部３３は、公開情報データベース３２から公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を取得し、図３に示すように、署名暗号化装置１０と、検証復号装置５０1〜５０i〜５０ｎと、復元装置２０と、暗号文管理装置４０とに送信する。このようにして、送信部３３は、少なくとも署名を行う署名暗号化装置１０、及び、検証を行う検証復号装置５０1〜５０i〜５０ｎに、ハッシュ関数Ｈ２を送信して、用いるハッシュ関数Ｈ２を指示する指示部として機能する。尚、送信部３３は、復元装置２０には、「ｎ」及び「ｔ」も通知する。（ｔ，ｎ）しきい値暗号方式において、「ｎ」及び「ｔ」は公開されている。
【００６５】
また、送信部３３は、図３に示すように、複数（ｎ個）の分散鍵ｓｋ1〜ｓｋi〜ｓｋｎをそれぞれ、検証復号装置５０1〜５０i〜５０ｎに分散して送信する。情報提供装置３０自身は秘密情報ｄや分散鍵を保持しない。そのため、秘密情報ｄや分散鍵は一箇所に管理されず、複数の検証復号装置５０1〜５０i〜５０ｎによって分散管理されることになる。更に、送信部３３は、図３に示すように、複数（ｎ個）の部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎと、それらの生成元νを復元装置２０に送信する。
【００６６】
このように、情報提供装置３０は、しきい値暗号方式において、公開鍵情報ｐｋや分散鍵ｓｋ1〜ｓｋi〜ｓｋｎの生成に加え、ハッシュ関数Ｈ２を決定する。そして、情報提供装置３０は、ハッシュ関数Ｈ２を公開情報の１つとして提供し、用いるハッシュ関数Ｈ２を指示する。よって、情報提供装置３０は、検証鍵ｖｋをハッシュ関数Ｈ２に入力して得られたハッシュ値ｕを用いた署名σやその検証に寄与することができる。よって、署名対象データである暗号文ｃの正当性のより確実な検証に寄与できる。
【００６７】
このような情報提供装置３０は、コンピュータを、提供情報生成部３１と、公開情報データベース３２と、送信部３３として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００６８】
暗号文管理装置４０は、補強暗号文Ｃを署名暗号化装置１０から受信して管理し、補強暗号文Ｃを検証復号装置５０1〜５０i〜５０ｎ及び復元装置２０に送信する。暗号文管理装置４０は、図１に示すように、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４とを備える。
【００６９】
受信部４１は、図３に示すように、署名暗号化装置１０から補強暗号文Ｃを受信し、暗号文管理部４２に入力する。また、受信部４１は、検証復号装置５０1〜５０i〜５０ｎ及び復元装置２０から、補強暗号文Ｃの要求を受信し、暗号文管理部４２に入力する。更に、受信部４１は、図３に示すように、情報提供装置３０から公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を受信し、暗号文管理部４２に入力する。
【００７０】
暗号文データベース４３は、補強暗号文Ｃを公開情報と対応づけて保持する。暗号文管理部４２は、受信した補強暗号文Ｃを、受信した公開情報と対応づけて、暗号文データベース４３に格納する。暗号文管理部４２は、公開情報の指定を含む補強暗号文Ｃの要求に基づいて、対応する補強暗号文Ｃを暗号文データベース４３から取得する。暗号文管理部４２は、取得した補強暗号文Ｃを公開情報と対応づけて送信部４４に入力する。
【００７１】
送信部４４は、暗号管理部４２から入力される、公開情報に対応づけられた補強暗号文Ｃを、図３に示すように、その補強暗号文Ｃを要求した検証復号装置５０1〜５０i〜５０ｎ及び復元装置２０に送信する。
【００７２】
このような暗号文管理装置４０は、コンピュータを、受信部４１と、暗号文管理部４２と、暗号文データベース４３と、送信部４４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００７３】
検証復号装置５０1〜５０i〜５０ｎは、署名対象データである暗号文ｃの正当性を検証する。更に、検証復号装置５０1〜５０i〜５０ｎは、暗号文ｃの復号を行う。検証復号装置５０1〜５０ｎはそれぞれ、図１に示すように、受信部５１1〜５１nと、検証部５２1〜５２nと、復号部５３1〜５３nと、送信部５４1〜５４nとを備える。検証復号装置５０1〜５０i〜５０ｎには、１〜ｎまでの番号が付与されている。
【００７４】
受信部５１１〜５１ｎは、図３に示すように、情報提供装置３０から公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を受信し、検証部５２1〜５２n及び復号部５３1〜５３nに入力する。各検証復号装置５０1〜５０ｎの受信部５１１〜５１ｎはそれぞれ、図３に示すように、情報提供装置３０から分散鍵ｓｋ1〜ｓｋｎを受信し、復号部５３1〜５３nに入力する。受信部５１１〜５１ｎは、図３に示すように、復元装置２０から復号の要求を受信し、検証部５２1〜５２nに入力する。そして、受信部５１１〜５１ｎは、図３に示すように、暗号文管理装置４０から補強暗号文Ｃを受信し、検証部５２1〜５２nに入力する。
【００７５】
検証部５２1〜５２nは、署名対象データである暗号文ｃに付加された、ハッシュ値ｕ及びそのハッシュ値ｕを用いて生成された署名情報ｖを含む署名σと、検証鍵ｖｋと、少なくとも検証鍵ｖｋ及び暗号文ｃの入力を受けてハッシュ値ｕを生成するハッシュ関数Ｈ２とを用いて、暗号文ｃの正当性を検証する。
【００７６】
具体的には、検証部５２1〜５２nは、復元装置２０から復号の要求を受けると、その復号の要求を受け入れるか否かを判断する。検証部５２1〜５２nは、復号の要求を受け入れた場合（復号することに同意した場合）、送信部５４1〜５４nを介して、暗号文管理装置４０に公開情報を指定して補強暗号文Ｃを要求する。そして、検証部５２1〜５２nは、暗号文ｃに署名σと検証鍵ｖｋが付加された補強暗号文Ｃを取得する。検証部５２1〜５２nは、暗号文ｃに付加された署名σに含まれるハッシュ値ｕ及び署名情報ｖと、暗号文ｃに付加された検証鍵ｖｋと、公開情報に含まれるＮとハッシュ関数Ｈ２とを用いて、以下に示す（６）式が成立するか否かを検証する。
【００７７】
ｕ＝Ｈ２（ｃ，ｖeｈ-uｍｏｄＮ）  （６）式
但し、ｈ＝ｖｋ＝ｓe
検証部５２1〜５２nは、（６）式が成立する場合には、即ち、左辺と右辺が等しくなる場合には、署名σは正当であり、署名対象データである暗号文ｃも正当であると判断する。このようにして、暗号文ｃの正当性が確認できた場合、検証部５２1〜５２nは、暗号文ｃを復号部５３1〜５３nに入力する。
【００７８】
一方、検証部５２1〜５２nは、（６）式が成立しなければ、即ち、左辺と右辺が等しくならなければ、署名σの正当性が確認できず、暗号文ｃの正当性が確認できないと判断する。そして、検証部５２1〜５２nはinvalid symbolを出力して処理を終了する。
【００７９】
復号部５３1〜５３nは、署名対象データである暗号文ｃに付加された、ハッシュ値ｕ及びそのハッシュ値ｕを用いて生成された署名情報ｖを含む署名σと、検証鍵ｖｋと、検証鍵ｖｋ及び暗号文ｃの入力を受けてハッシュ値ｕを生成するハッシュ関数Ｈ２とを用いて、暗号文ｃの正当性が確認された後に、暗号文ｃの復号を行う。
【００８０】
具体的には、復号部５３1〜５３nは、検証部５２1〜５２nにおいて暗号文ｃの正当性が確認された場合にのみ、検証部５２1〜５２nから暗号文ｃを取得する。各復号部５３1〜５３nはそれぞれ、暗号文ｃを部分的に復号して部分復号情報δ1〜δｎを生成する（部分復号を行う）。部分復号情報δ1〜δｎは、暗号文ｃから平文ｍを復元するために用いられるものであり、復元装置２０が平文ｍを復元する際に必要な情報である。
【００８１】
復号部５３1〜５３nはそれぞれ、暗号文ｃと取得した分散鍵ｓｋ1〜ｓｋｎを用いた計算により、暗号文を分散鍵を用いて部分的に復号し、部分復号情報δ1〜δｎを生成する。複数の検証復号装置５０１〜５０ｎがそれぞれ異なる分散鍵ｓｋ1〜ｓｋｎを用いて部分復号情報δ1〜δｎを生成することにより、複数の部分復号情報δ1〜δｎが生成される。分散鍵ｓｋｉを用いて生成された部分復号情報がδｉとなる。
【００８２】
復号部５３1〜５３nはそれぞれ、以下に示す（７）式を計算することにより、暗号文ｃを分散鍵ｓｋ1〜ｓｋnを用いて部分的に復号し、部分復号情報δ1〜δｎを生成する。尚、Δ＝ｎ！＝ｎ・（ｎ−１）・（ｎ−２）…２・１と定義する。復号部５３1〜５３nは、生成した部分復号情報δ1〜δｎを送信部５４1〜５４nに入力する。
【数３】
2006319485.tif 000005
【００８３】
送信部５４１〜５４ｎはそれぞれ、図３に示すように、部分復号情報δ1〜δｎを復元装置２０に送信する。送信部５４１〜５４ｎは、補強暗号文Ｃの要求を暗号文管理装置４０に送信する。
【００８４】
尚、複数の検証復号装置５０1〜５０nのうち、復号の要求を受け入れなかった検証復号装置は、検証も部分復号も行わない。即ち、暗号文ｃの復号に同意した検証復号装置のみが検証を行えばよい。そして、結果として、少なくともｔ個の部分復号情報δが生成され、復元装置２０に送信されればよい。
【００８５】
このようにようにして、検証復号装置５０1〜５０nは、補強暗号文Ｃに含まれる署名σと、検証鍵ｖｋと、ハッシュ関数Ｈ２とを用いて、署名対象データである暗号文ｃの正当性を検証できる。更に、検証復号装置５０1〜５０nは、補強暗号文Ｃに含まれる暗号文ｃの正当性が確認された後に、暗号文ｃを部分的に復号し、部分復号情報δ1〜δｎを生成できる。このようにして、検証復号装置５０1〜５０nは、検証及び復号を行い、検証装置及び復号装置として機能することができる。
【００８６】
このような検証復号装置５０1〜５０nは、コンピュータを、受信部５１1〜５１nと、検証部５２1〜５２nと、復号部５３1〜５３nと、送信部５４1〜５４nとして機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【００８７】
復元装置２０は、複数の部分復号情報δ1〜δｎを用いて、暗号文ｃから平文ｍを復元する。復元装置２０は、図１に示すように、受信部２１と、復元部２２と、送信部２３と、出力部２４とを備える。
【００８８】
受信部２１は、図３に示すように、署名対象データである暗号文を部分的に復号して生成された複数の部分復号情報δ1〜δｎを受信する。受信部２１は、複数の部分復号情報δ1〜δｎを複数の検証復号装置５０１〜５０ｎから受信し、復元部２２に入力する。受信部２１は、補強暗号文Ｃを暗号文管理装置４０から受信し、復元部２２に入力する。受信部２１は、情報提供装置３０から公開情報（Ｎ，ｅ，Ｈ１、Ｈ２）と部分復号検証鍵shareｖｋ１〜shareｖｋｎ及びそれらの生成元νを受信し、復元部２２に入力する。
【００８９】
復元部２２は、署名対象データである暗号文ｃに付加された、ハッシュ値ｕ及びそのハッシュ値ｕを用いて生成された署名情報ｖを含む署名σと、検証鍵ｖｋと、少なくとも検証鍵ｖｋ及び暗号文ｃの入力を受けてハッシュ値ｕを生成するハッシュ関数Ｈ２とを用いて、暗号文ｃの正当性が確認された後に、複数の部分復号情報δ1〜δｎを結合し、平文ｍを復元する。
【００９０】
復元部２２は、まず、補強暗号文Ｃの復号を検証復号装置５０1〜５０ｎに要求する。その後、復元部２２は、検証復号装置５０1〜５０ｎにおいて暗号文ｃの正当性が確認された場合にのみ、検証復号装置５０1〜５０ｎから部分復号情報δ1〜δｎを取得する。
【００９１】
復元部２２は、取得した複数の部分復号情報δ1〜δｎが、正しく復号されたか否かを検証する。復元部２２は、複数の部分復号情報δ1〜δｎそれぞれについて、複数の部分復号検証鍵shareｖｋ1〜shareｖｋｎそれぞれと、それらの生成元νを用いて検証を行う。具体的には、復元部２２は、「ｈ４Δ」を底とした部分復号情報δｉの２乗「δｉ２」の対数と、「νΔ」を底とした部分復号検証鍵shareｖｋｉの対数が、等しいか否かを検証する。即ち、δｉ２と部分復号検証鍵shareｖｋｉそれぞれが、ｈ４Δ、νΔをそれぞれ底として同じ対数を持つかどうかを検証する。
【００９２】
復元部２２は、対数が等しい場合（同じ対数を持つ場合）、部分復号情報δｉが正しく復号されたものであると判断する。この場合、復元部２２は、平文ｍの復元に進む。一方、復元部２２は、対数が異なる場合、部分復号情報δｉは正しく復号されていないと判断する。そして、復元部２２はinvalid symbolを出力して処理を終了する。
【００９３】
復元部２２は、正しく復号されていることが確認できた複数の部分復号情報δ1〜δｎを用いて暗号文ｃから平文ｍを復元する（部分復号情報を結合する）。まず、復元部２２は、平文ｍの暗号化に用いた乱数ｓを、（９）式に示す条件で、（８）式を計算することにより求める。
【数４】
2006319485.tif 000006
【数５】
2006319485.tif 000007
【００９４】
尚、（８）式、（９）式において、「Ｔ」は、復元装置２０からの復号要求を受け入れた復号サーバ５０１〜５０ｎの番号の集合を表す。例えば、番号１、２、５が付与された検証復号装置が復号要求を受け入れた場合には、Ｔ＝｛１，２，５｝と記述される。但し、集合Ｔに含まれる番号の数は、（ｔ，ｎ）しきい値暗号方式において部分復号情報が必要な数ｔに限定される。また、（８）式、（９）式における「λ」は補間係数である。「λ」は、（４）式において、ｆ（０）＝ａ０を計算するために用いられ、（１０）式に示す関係を持つ。
【数６】
2006319485.tif 000008
【００９５】
また、「Πｊ∈Ｔ／｛ｉ｝（ｉ−ｊ）」は、集合Ｔに含まれる番号のうちｉを除く全ての番号に関してｉから引き算した値を考え、それら全ての積を示す。同様に、「Πｊ∈Ｔ／｛ｉ｝（−ｊ）」は、集合Ｔに含まれる番号のうちｉを除く全ての数字に関して、絶対値を逆にした値の積を示す。
【００９６】
更に、公開情報の「ｅ」の選択方法から、「ｅ」と「４Δ」は互いに素である。そのため、Ｘ×４Δ２＋Ｙ×ｅ＝１を満たす整数Ｘと整数Ｙの組み合わせが存在する。よって、復元部２２は、次に、Ｘ×４Δ２＋Ｙ×ｅ＝１を満たす整数Ｘと整数Ｙの組み合わせを計算する。例えば、復元部２２は、拡張ユークリッドアルゴリズムを用いて、多項式時間で整数Ｘ、Ｙを計算できる。
【００９７】
そして、復元部２２は、（８）式の計算結果と、求めた整数Ｘ、Ｙを用いて、以下に示す（１１）式を計算することにより、乱数ｓを計算する。尚、（１１）式は、非特許文献１に示される原理から（１２）式が成立するため、成立する。復元部２２は、補強暗号文Ｃに含まれる暗号文ｃを（１１）式に代入する。
【数７】
2006319485.tif 000009
【数８】
2006319485.tif 000010
【００９８】
次に、復元部２２は、計算した乱数ｓを用いて、暗号文ｃから平文ｍを復元する。具体的には、平文ｍを乱数ｓを用いて暗号化する際に用いた（１）式に、暗号文ｃと、求めた乱数ｓを代入することにより、平文ｍを復元できる。このようにして、復元部２２は、複数の部分復号情報δ1〜δｎを結合して平文ｍを復元できる。復元部２２は、復元した平文ｍを出力部２４に出力する。
【００９９】
送信部２３は、図３に示すように、復号の要求を検証復号装置５０1〜５０ｎに送信する。送信部２３は、補強暗号文Ｃの要求を暗号文管理装置４０に送信する。
【０１００】
このようにして、復元装置２０は、補強暗号文Ｃに含まれる暗号文ｃの正当性が確認された後に、複数の部分復号情報δ1〜δｎを結合し、平文ｍを復元できる。
【０１０１】
このような復元装置２０は、コンピュータを、受信部２１と、復元部２２と、送信部２３と、出力部２４として機能させるためのプログラムを、コンピュータが実行することにより実現できる。
【０１０２】
（通信方法）
次に、通信システム１００における通信方法の手順を説明する。通信方法には、署名方法と暗号化方法を含む署名暗号化方法、検証方法、復号方法、復元方法の各工程が含まれる。
【０１０３】
情報提供装置３０は、公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）と、複数（ｎ個）の分散鍵ｓｋ1〜ｓｋｎと、複数（ｎ個）の部分復号検証鍵shareｖｋ1〜shareｖｋｎと、部分復号検証鍵の生成元νを生成する（Ｓ１０１）。情報提供装置３０は、公開情報（Ｎ，ｅ，Ｈ１，Ｈ２）を、署名暗号化装置１０と、暗号文管理装置４０と、検証復号装置５０1〜５０ｎと、復元装置２０に送信する（Ｓ１０２〜Ｓ１０５）。更に、情報提供装置３０は、分散鍵ｓｋ1〜ｓｋｎを検証復号装置５０1〜５０ｎに送信する（Ｓ１０６）。また、情報提供装置３０は、部分復号検証鍵shareｖｋ1〜shareｖｋｎと生成元νを復元装置２０に送信する（Ｓ１０７）。
【０１０４】
署名暗号化装置１０は、少なくとも公開鍵情報ｐｋと乱数ｓを用いて平文ｍを暗号化し、署名対象データとして暗号文ｃを生成する（Ｓ１０８）。署名暗号化装置１０は、少なくとも暗号化に用いた乱数ｓを用いて検証鍵ｖｋを生成する（Ｓ１０９）。署名暗号化装置１０は、少なくとも検証鍵ｖｋと暗号文ｃをハッシュ関数Ｈ２に入力し、ハッシュ値ｕを生成する（Ｓ１１０）。
【０１０５】
署名暗号化装置１０は、少なくともハッシュ値ｕを用いて署名情報ｖを生成する（Ｓ１１１）。そして、署名暗号化装置１０は、署名対象データである暗号文ｃに、少なくともハッシュ値ｕ及び署名情報ｖを含む署名σ＝（ｕ，ｖ）と検証鍵ｖｋを付加し、安全性を補強した補強暗号文Ｃを生成する（Ｓ１１２）。署名暗号化装置１０は、補強暗号文Ｃを暗号文管理装置４０に送信する（Ｓ１１３）。暗号文管理装置４０は、補強暗号文４０を暗号文データベース４３に格納する（Ｓ１１４）。
【０１０６】
復元装置２０は、補強暗号文Ｃを暗号文管理装置４０に要求する（Ｓ１１５）。暗号文管理装置４０は、補強暗号文Ｃを復元装置２０に送信する（Ｓ１１６）。復元装置２０は、補強暗号文Ｃの復号を検証復号装置５０1〜５０ｎに要求する（Ｓ１１７）。検証復号装置５０1〜５０ｎは、復号の要求を受け入れる場合、補強暗号文Ｃを暗号文管理装置４０に要求する（Ｓ１１８）。暗号文管理装置４０は、補強暗号文Ｃを検証復号装置５０1〜５０ｎに送信する（Ｓ１１９）。
【０１０７】
検証復号装置５０1〜５０ｎは、少なくとも、補強暗号文Ｃに含まれる暗号文ｃに付加された署名σに含まれるハッシュ値ｕ及び署名情報ｖと、検証鍵ｖｋと、ハッシュ関数Ｈ２とを用いて、署名対象データである暗号文ｃの正当性を検証する（Ｓ１２０）。検証復号装置５０1〜５０ｎは、暗号文ｃの正当性が確認された場合、暗号文ｃを部分的に復号し、部分復号情報δ1〜δｎを生成する（Ｓ１２１）。検証復号装置５０1〜５０nは、生成した部分復号情報δ1〜δｎを復元装置２０に送信する（Ｓ１２２）。
【０１０８】
復元装置２０は、受信した複数の部分復号情報δ1〜δｎが、正しく復号されたか否かを検証する（Ｓ１２３）。復元装置２０は、正しく復号されたことが確認された場合、複数の部分復号情報δ1〜δｎを結合し、平文ｍを復元する（Ｓ１２４）。
【０１０９】
（効果）
このような通信システム１００、署名暗号化装置１０、復元装置２０、情報提供装置３０、暗号文管理装置４０、検証復号装置５０1〜５０ｎ、通信方法（署名暗号化方法、検証方法、復号方法、復元方法）によれば、以下に示す効果を得ることができる。
【０１１０】
署名暗号化装置１０に含まれる署名装置１４は、検証鍵ｖｋ及び署名対象データである暗号文ｃをハッシュ関数Ｈ２に入力して得られたハッシュ値ｕを用いて署名情報ｖを生成し、署名対象データである暗号文ｃにハッシュ値ｕ及び署名情報ｖを含む署名σを付加することができる。このように検証鍵ｖｋをハッシュ関数Ｈ２に入力して得られたハッシュ値ｕを用いた署名σを付加することにより、暗号文ｃの偽造を従来よりも多くの場合において検出できる。よって、署名σと検証鍵ｖｋを用いて、暗号文ｃの正当性をより確実に検証することができる。
【０１１１】
しかも、署名暗号化装置１０は、同一の乱数ｓを用いて、平文ｍの暗号化と検証鍵ｖｋの生成を行うことができる。そのため、これにより、検証鍵を用いて検証される署名が、暗号文の正当性を証明することができる。更に、署名暗号化装置１０は、得られた検証鍵ｖｋ及び暗号文ｃをハッシュ関数Ｈ２に入力してハッシュ値ｕを生成し、ハッシュ値ｕと乱数ｓを用いて署名情報ｖを生成できる。そして、署名暗号化装置１０は、このようにして得られたハッシュ値ｕと署名情報ｖを含む署名σと、検証鍵ｖｋを暗号文ｃに付加することができる。これによれば、暗号文ｃの正当性を証明する署名σの安全性をより向上させることができ、署名σと検証鍵ｖｋを用いて暗号文ｃの正当性をより確実に検証できる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に暗号化や復号などの処理を行うことができる。
【０１１２】
また、検証復号装置５０1〜５０ｎによれば、署名σと、検証鍵ｖｋと、検証鍵ｖｋの入力を受けてハッシュ値ｕを生成するハッシュ関数Ｈ２とを用いることにより、署名対象データである暗号文ｃの偽造を検出できる。よって、暗号文ｃの正当性をより確実に検証することができる。
【０１１３】
更に、検証復号装置５０1〜５０ｎによれば、暗号文ｃの正当性が精度の高い検証により確認された後に、暗号文ｃを復号することができる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に復号を行うことができる。
【０１１４】
また、復元装置２０によれば、暗号文ｃの正当性が精度の高い検証により確認された後に、複数の部分復号情報δ1〜δｎを結合して暗号文ｃから平文ｍを復元することができる。そのため、暗号方式に関わらず、より高い安全性を確保でき、かつ、効率的に復元を行うことができる。
【０１１５】
特に、しきい値暗号方式では、復号に関わる人（装置）の規定人数（規定装置数）以内の不正を予め考慮している。そのため、公開鍵暗号方式と同じ暗号化方式を用いた場合には、暗号文ｃに問題がある場合や、不正な部分復号が行われた場合に、その安全性を証明できず、安全性を確保できない場合がある。しかし、検証鍵ｖｋをハッシュ関数Ｈ２の入力の一つとして用いた署名σを暗号文ｃに付加することにより、検証鍵ｖｋが変更された場合にも暗号文ｃが一切偽造できないようにできる。よって、しきい値暗号方式においても安全な暗号化を行うことができる。
【０１１６】
従って、しきい値暗号方式において、選択暗号文攻撃に対する耐性を付加でき、選択暗号文攻撃に対してより高い安全性を確保できる。しかも、しきい値暗号方式において、効率的な暗号化や復号、復元を実現できる。そのため、しきい値暗号方式を用いる場合に、計算能力の低い移動通信端末などが復元装置となるときや、署名装置となるときにも、複数ビットの平文を暗号化でき、効率的に暗号化や復元などの処理を行うことができる。
【０１１７】
（変更例）
本発明は、上記実施形態に限定されるものではなく、種々の変更が可能である。図２に示した乱数ｓ生成部１２や乱数ｒ生成部１４ｂは、乱数ｓや乱数ｒを複数生成し、暗号文生成部１３、検証鍵生成部１４ａ、署名情報生成部１４ｄが、複数の乱数ｓを用いたり、ハッシュ値生成部１４ｃや署名情報生成部１４ｄが、複数の乱数ｒを用いても構わない。
【０１１８】
また、通信システム１００では、検証と復号の両方を行う検証復号装置５０1〜５０ｎを設けているが、検証部を備え、検証を行う検証装置と、復号部を備え、復号を行う復号装置とを分けて設けてもよい。これによれば、複数の検証復号装置が行っていた検証処理を１箇所の検証装置にまとめられる利点がある。但し、検証装置の安全性は非常に高いものが要求される。例えば、暗号文管理装置４０が検証部を備え、検証装置として機能してもよい。この場合、情報提供装置３０は、少なくとも、署名を行う装置と暗号文管理装置４０に、ハッシュ関数Ｈ２を提供する必要がある。
【０１１９】
また、情報提供装置３０において、送信部３３は、ｎ個の部分復号検証鍵shareｖｋ1〜shareｖｋi〜shareｖｋｎ全てを送信しているが、ｔ個以上の部分復号検証鍵shareｖｋを、ｔ個以上の検証復号装置に送信してもよい。
【０１２０】
通信システム１００では、しきい値暗号方式を用いているが、公開鍵暗号方式を用いてもよい。公開鍵方式の場合、検証復号装置（復号装置）は１つでよい。情報提供装置３０の提供情報生成部３１は、復号鍵として秘密情報ｄ’（但し、ｄ’は、ｅｄ’≡１ｍｏｄ２Ｌを満たす。）を生成する。送信部３３は、秘密情報ｄ’を復号鍵として検証復号装置（復号装置）に送信する。そして、検証復号装置（復号装置）は、補強暗号文Ｃに含まれる暗号文ｃの正当性が確認された後に、暗号文ｃを復号鍵（秘密情報ｄ’）で復号し、平文ｍを得る。これらの点以外は、しきい値暗号方式とほぼ同様である。
【０１２１】
これによれば、公開鍵暗号方式において、より正確に暗号文を検証できるため、選択暗号文攻撃に対してより高い安全性を確保できる。しかも、公開鍵暗号方式において、効率的な暗号化や復号、復元を実現できる。そのため、公開鍵暗号方式を用いる場合に、計算能力の低い移動通信端末などが復元装置となるときや、署名装置となるときにも、複数ビットの平文を暗号化でき、効率的に暗号化や復元などの処理を行うことができる。
【０１２２】
また、暗号化せずに署名だけを行う場合、検証鍵ｖｋは、署名対象データに付加して送信してもよく、署名対象データの送受信前に検証を行う装置に予め提供しておいてもよく、情報提供装置３０の公開情報データベース３２に登録しておき、公開情報として提供するようにしてもよい。
【０１２３】
また、上記実施形態では、暗号文の検証が行われた後に、暗号文を部分的に復号（部分復号）し、得られた複数の部分復号情報を結合して復元を行っているが、検証と部分復号の順番は限定されない。例えば、暗号文の正当性の検証は、暗号文の部分復号により部分復号情報が生成された後に行ってもよい。この場合、例えば、検証復号装置が備えていた検証部を復元装置が備えることにより、検証復元装置として機能することができる。検証復元装置は、部分復号情報を復号装置から受信した後に、暗号文を検証し、正当性が確認できた場合にのみ復元を行うことができる。
【０１２４】
また、検証装置と復号装置が別々で設けられている場合には、復元装置は、検証装置に暗号文の検証を要求し、検証結果が正当性を示す場合にだけ、復号装置に復号を要求することができる。また、復元装置は、検証装置と復号装置に検証と復号を並行して要求し、検証結果と部分復号情報を受信し、検証結果が正当性を示す場合にだけ、復元を行ってもよい。あるいは、復元装置は、部分復号情報を受信した後に、検証装置に検証を要求し、検証結果が正当性を示す場合にだけ、復元を行ってもよい。
【０１２５】
また、上記実施形態では、送信部３３は提供情報生成部３１が決定したハッシュ関数Ｈ２を送信したが、予め用いるハッシュ関数Ｈ２が決まっている場合には、公開情報データベース場合にハッシュ関数Ｈ２を予め格納しておくことができる。この場合、送信部３３は予め決まっているハッシュ関数Ｈ２を送信して、用いるハッシュ関数Ｈ２を指示することができる。また、署名や検証を行う装置が、予め複数のハッシュ関数Ｈ２を保持している場合には、提供情報生成部３１がその中から用いるハッシュ関数Ｈ２を決定することができる。この場合、例えば、公開情報としてハッシュ関数Ｈ２を特定可能な番号やＩＤ、フラグなどの情報を公開情報データベース３２に格納しておくことができる。そして、送信部３３は、ハッシュ関数Ｈ２を特定する情報を送信することにより、用いるハッシュ関数Ｈ２を指示することができる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の実施形態に係る通信システムの構成を示すブロック図である。
【図２】本発明の実施形態に係る署名装置の構成を示すブロック図である。
【図３】本発明の実施形態に係るデータの流れを示す図である。
【図４】本発明の実施形態に係る通信方法の手順を示すフロー図である。
【符号の説明】
【０１２７】
１０  署名暗号化装置
１１  受信部
１２  乱数ｓ生成部
１３  暗号文生成部
１４  署名装置
１４ａ  検証鍵生成部
１４ｂ  乱数ｒ生成部
１４ｃ  ハッシュ値生成部
１４ｄ  署名情報生成部
１４ｅ  署名部
１５  送信部
２０  復元装置
２１  受信部
２２  復元部
２３  送信部
２４  出力部
３０  情報提供装置
３１  提供情報生成部
３２  公開情報データベース
３３  送信部
４０  暗号文管理装置
４１  受信部
４２  暗号文管理部
４３  暗号文データベース
４４  送信部
５０1〜５０ｎ  検証復号装置
５１1〜５１ｎ  受信部
５２1〜５２ｎ  検証部
５３1〜５３ｎ  復号部
５４1〜５４ｎ  送信部
６０  ネットワーク
１００  通信システム
【図１】
2006319485.tif 000011
【図２】
2006319485.tif 000012
【図３】
2006319485.tif 000013
【図４】
2006319485.tif 000014