(57)【要約】【課題】妥当な仮定の上での安全性を根拠としつつ、より迅速かつ容易に必要な処理を実行することができる署名装置、検証装置、復号装置、平文復元装置、情報提供装置、署名システム、通信システム及び署名方法を提供する。【解決手段】本発明に係る端末装置２００は、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、検証鍵から作成できない情報を、検証鍵及び署名情報を用いて抽出でき、当該検証鍵を用いて有効であると判断された有効署名と、検証鍵とのペアに基づいて、当該検証鍵と同一の検証鍵、さらには当該検証鍵と異なる他の検証鍵と、有効署名とのペアを作成することができない署名情報を生成する。【選択図】図１
2007142897.tif 000002
【特許請求の範囲】
【請求項１】
署名対象データを取得する署名対象データ取得部と、
任意の方法によって定められたシードを用いて、前記署名対象データの検証に用いられる検証鍵を生成する検証鍵生成部と、
前記シードを用いて、前記署名対象データに対応する署名情報を生成する署名情報生成部と、
前記署名情報を含む署名を前記署名対象データに付加する署名部と
を備え、
前記署名情報生成部は、
出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、前記検証鍵から作成できない情報を、前記検証鍵及び前記署名情報を用いて抽出でき、
前記検証鍵を用いて有効であると判断された有効署名と、前記検証鍵とのペアに基づいて、前記検証鍵と同一の検証鍵、さらには前記検証鍵と異なる他の検証鍵と、有効署名とのペアを作成することができない前記署名情報を生成する署名装置。
【請求項２】
少なくとも前記検証鍵を第１のハッシュ関数に入力し、第１のハッシュ値を生成する第１ハッシュ値生成部と、
少なくも前記第１のハッシュ値及び前記署名対象データを第２のハッシュ関数に入力し、第２のハッシュ値を生成する第２ハッシュ値生成部と
をさらに備え、
前記署名部は、前記第２のハッシュ値及び前記署名情報を含む署名を前記署名対象データに付加する請求項１に記載の署名装置。
【請求項３】
前記署名情報生成部は、前記第１のハッシュ値、前記第２のハッシュ値及び前記シードを用いて前記署名情報を生成し、
前記署名部は、前記第２のハッシュ値と、前記第２のハッシュ値及び前記シードを用いて生成された前記署名情報とを含む署名を、前記検証鍵とともに、前記シードを平文の暗号化における乱数として用いて暗号化された前記署名対象データに付加する請求項２に記載の署名装置。
【請求項４】
署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する検証装置側第１のハッシュ関数取得部と、
少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する検証装置側第２のハッシュ関数取得部と、
前記第１のハッシュ関数と、前記第２のハッシュ関数と、前記第１のハッシュ値及び前記第２のハッシュ値を用いて生成され、前記署名対象データに付加されている署名とを用いて前記署名対象データが正当であることを検証する検証装置側検証部と
を備える検証装置。
【請求項５】
暗号化された署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する復号装置側第１のハッシュ関数取得部と、
少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する復号装置側第２のハッシュ関数取得部と、
前記第１のハッシュ関数と、前記第２のハッシュ関数と、前記第１のハッシュ値及び前記第２のハッシュ値を用いて生成され、前記署名対象データに付加されている署名と、前記検証鍵とを用いて、前記署名対象データが正当であることを検証する復号装置側検証部と、
前記復号装置側検証部によって前記署名対象データが正当であることが検証されたことに応じて、前記署名対象データを復号する復号部と
を備える復号装置。
【請求項６】
平文が暗号化された署名対象データの少なくとも一部分を復号することによって生成された複数の部分復号情報を受信する受信部と、
前記署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する復元装置側第１のハッシュ関数取得部と、
少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する復元装置側第２のハッシュ関数取得部と、
前記受信部が受信した前記部分復号情報を結合し、平文を復元する平文復元部と
を備える平文復元装置。
【請求項７】
前記部分復号情報を検証する部分復号情報検証鍵を用いて、前記部分復号情報が正当であることを検証する復元装置側検証部をさらに備え、
前記平文復元部は、前記復元装置側検証部によって前記部分復号情報が正当であることが検証されたことに応じて、前記平文を復元する請求項６に記載の平文復元装置。
【請求項８】
暗号化された署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を記憶する情報提供装置側第１のハッシュ関数記憶部と、
少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を記憶する情報提供装置側第２のハッシュ関数記憶部と、
前記第第１のハッシュ関数及び前記第２のハッシュ関数を示す関数情報を提供する情報提供部と
を備え、
前記情報提供部は、
少なくとも前記第２のハッシュ値を含む署名を前記署名対象データに付加する署名装置、または
前記署名、前記第１のハッシュ値、前記第２のハッシュ値、前記検証鍵を用いて前記署名対象データが正当であることを検証する検証装置
の少なくとも何れかに対して、前記第第１のハッシュ関数及び前記第２のハッシュ関数を提供する情報提供装置。
【請求項９】
請求項１乃至３の何れかの署名装置と、
請求項４の検証装置と
を備える署名システム。
【請求項１０】
請求項１乃至３の何れかの署名装置と、
請求項４の検証装置と、
請求項５の復号装置と、
請求項６または７の平文復元装置と
を備える通信システム。
【請求項１１】
請求項９の署名システムにおいて用いられ、署名対象データの検証に用いられる検証鍵、及び任意の方法によって定められたシードを生成する鍵生成部と、
前記検証鍵を検証装置に送信する検証鍵送信部と、
前記シードを署名装置に送信するシード送信部と
を備える鍵生成装置。
【請求項１２】
請求項１０の通信システムにおいて用いられ、少なくとも平文の暗号処理及び暗号化された署名対象データの復号処理に用いられる公開鍵及び復号鍵を生成する鍵生成部と、
前記公開鍵を検証装置、復号装置または平文復元装置の少なくとも何れかに送信する公開鍵送信部と、
前記復号鍵を前記復号装置に送信する復号鍵送信部と
を備える鍵生成装置。
【請求項１３】
署名対象データを取得し、
任意の方法によって定められたシードを用いて、前記署名対象データの検証に用いられる検証鍵を生成し、
前記シードを用いて、前記署名対象データに対応する署名情報を生成し、
前記署名情報を含む署名を前記署名対象データに付加し、
前記署名を付加する場合には、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、前記検証鍵から作成できない情報を、前記検証鍵及び前記署名情報を用いて抽出でき、
前記検証鍵を用いて有効であると判断された有効署名に基づいて、前記検証鍵と異なる他の検証鍵を用いて前記有効署名を作成することができない前記署名を付加する署名方法。
【請求項１４】
少なくとも前記検証鍵を第１のハッシュ関数に入力し、第１のハッシュ値を生成し、
少なくも前記第１のハッシュ値及び前記署名対象データを第２のハッシュ関数に入力して、第２のハッシュ値を生成し、
前記第２のハッシュ値及び前記署名情報を含む署名を前記署名対象データに付加する請求項１３に記載の署名方法。
【請求項１５】
前記署名情報を生成する場合、前記第１のハッシュ値、前記第２のハッシュ値及び前記シードを用いて前記署名情報を生成し、
前記第２のハッシュ値と、前記第２のハッシュ値及び前記シードを用いて生成された前記署名情報とを含む署名を、前記検証鍵とともに、前記シードを平文の暗号化における乱数として用いて暗号化された前記署名対象データに付加する請求項１４に記載の署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、しきい値暗号方式にしたがった署名装置、検証装置、復号装置、平文復元装置、情報提供装置、署名システム、通信システム、鍵生成装置及び署名方法に関する。
【背景技術】
【０００２】
今日、秘匿性を保ちつつ安全に情報を送受信するため、RSAなどの公開鍵暗号方式が広く用いられている。公開鍵暗号方式では、公開鍵と対になる秘密鍵（復号鍵など）が悪意ある第三者に取得されると、情報を安全に送受信することができなくなるため、秘密鍵を安全に保管することが重要である。
【０００３】
このような点を踏まえ、いわゆる“しきい値暗号方式”が実現されている（例えば、非特許文献１及び非特許文献２）。
【０００４】
しきい値暗号方式とは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、分散鍵を有する複数の装置（復号サーバ）が共同で処理を実行しなければ、平文を復元できないようにした暗号方式である。また、しきい値暗号方式では、分散鍵を秘密の状態としつつ復号を実行することができる。
【非特許文献１】Pierre-Alain Fouque and David Pointcheval、“Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks”、ASIACRYPT 2001, pp.351-368、２００１年
【非特許文献２】V. Shoup and R. Gennaro、“Securing Threshold Cryptosystems against Chosen Ciphertext Attack”、Journal of Cryptology, vol.15, no.2, pp.75-96、２００２年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、上述した従来のしきい値暗号方式では、平文を暗号化して暗号文とするために必要な演算として、当該平文が決定するよりも前に実行できる演算と、当該平文が決定しないと実行できない演算とが存在する。
【０００６】
また、当該演算には、演算時間を要する“べき乗”の演算と、べき乗と比較して演算時間が非常に短い単なる乗算、論理和（ＯＲ）及びハッシュ値などの演算とが混在する。すなわち、べき乗の演算を当該平文が決定するよりも前に実行することができれば、より迅速かつ効率的に平文を暗号化することができる。
【０００７】
しかしながら、非特許文献１に記載されているしきい値暗号方式では、暗号化の対象となる平文が決定するよりも前に、予め実行することができる演算が極めて限られている。このため、平文の決定後に一定の時間や処理能力が必要となるといった問題あった。
【０００８】
これに対して、非特許文献２に記載されるしきい値暗号方式、具体的には、ＴＤＨ２（Threshold Diffie-Hellman 2）と称呼されているしきい値暗号方式では、平文が決定するよりも前に、平文を暗号文とするために必要な演算の大部分を実行することができる。
【０００９】
しかしながら、当該しきい値暗号方式は、非特許文献１に記載されているしきい値暗号方式が“決定問題の困難性”（hardness of the computational Diffie-Hellman problem）という妥当な仮定の上での安全性を根拠としているのに対し、“判定問題の困難性”（hardness of the decisional Diffie-Hellman problem）という、少々強引な仮定の上での安全性を根拠としているという問題あった。
【００１０】
そこで、本発明は、このような状況に鑑みてなされたものであり、妥当な仮定の上での安全性を根拠としつつ、より迅速かつ容易に必要な処理を実行することができる署名装置、検証装置、復号装置、平文復元装置、情報提供装置、署名システム、通信システム、鍵生成装置及び署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した問題を解決するため、本発明は、次のような特徴を有している。まず、本発明の第１の特徴は、署名対象データ（暗号文c）を取得する署名対象データ取得部（暗号文生成部２０７）と、任意の方法によって定められたシード（乱数r）を用いて、前記署名対象データの検証に用いられる検証鍵（検証鍵vk）を生成する検証鍵生成部（検証鍵生成部２０９）と、前記シードを用いて、前記署名対象データに対応する署署名情報（署名情報v）を生成する署名情報生成部（署名情報生成部２１５）と、前記署名情報を含む署名（署名σ）を前記署名対象データに付加する署名部（署名部２１７）とを備え、前記署名情報生成部は、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、前記検証鍵から作成できない情報（例えば、hとu1のDH問題の答えであるhr=log u1（底はg1））を、前記検証鍵及び前記署名情報を用いて抽出でき、前記検証鍵を用いて有効であると判断された有効署名と、前記検証鍵とのペアに基づいて、前記検証鍵と同一の検証鍵、さらには前記検証鍵と異なる他の検証鍵と、有効署名とのペアを作成することができない前記署名情報を生成する署名装置（端末装置２００）であることを要旨とする。
【００１２】
本発明の第２の特徴は、本発明の第１の特徴に係り、少なくとも前記検証鍵を第１のハッシュ関数（ハッシュ関数H1）に入力し、第１のハッシュ値（ハッシュ値hA）を生成する第１ハッシュ値生成部（第１ハッシュ値生成部２１１）と、少なくも前記第１のハッシュ値及び前記署名対象データを第２のハッシュ関数（ハッシュ関数H2）に入力し、第２のハッシュ値を生成する第２ハッシュ値生成部（第２ハッシュ値生成部２１３）とをさらに備え、前記署名部は、前記第２のハッシュ値及び前記署名情報を含む署名（署名σ）を前記署名対象データに付加することを要旨とする。
【００１３】
このような署名装置によれば、平文などの署名対象データが決定する前に、予め第１のハッシュ値を演算することができる。さらに、平文などの署名対象データが決定する前に、第１のハッシュ値を用いる他の演算も実行することができる。
【００１４】
また、このような署名装置によれば、すべてのべき乗の演算を当該平文が決定するよりも前に実行することができるため、平文の決定後、迅速かつ効率的に平文を暗号化することができる。
【００１５】
さらに、このような署名装置によれば、検証鍵を第１のハッシュ関数に入力すること、及び第２のハッシュ関数を用いることによって、“緊密な安全性”（詳細は後述）が達成される。
【００１６】
本発明の第３の特徴は、本発明の第２の特徴に係り、前記署名情報生成部は、前記第１のハッシュ値、前記第２のハッシュ値及び前記シードを用いて前記署名情報を生成し、前記署名部は、前記第２のハッシュ値と、前記第２のハッシュ値及び前記シードを用いて生成された前記署名情報とを含む署名を、前記検証鍵とともに、前記シードを平文の暗号化における乱数として用いて暗号化された前記署名対象データに付加することを要旨とする。
【００１７】
本発明の第４の特徴は、署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する検証装置側第１のハッシュ関数取得部（検証部４０３及び記憶部４０９）と、少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する検証装置側第２のハッシュ関数取得部（検証部４０３及び記憶部４０９）と、前記第１のハッシュ関数と、前記第２のハッシュ関数と、前記第１のハッシュ値及び前記第２のハッシュ値を用いて生成され、前記署名対象データに付加されている署名とを用いて前記署名対象データが正当であることを検証する検証装置側検証部（検証部４０３）とを備える検証装置（復号サーバ４００１〜４００ｎ）であることを要旨とする。
【００１８】
本発明の第５の特徴は、暗号化された署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する復号装置側第１のハッシュ関数取得部（検証部４０３及び記憶部４０９）と、少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する復号装置側第２のハッシュ関数取得部（検証部４０３及び記憶部４０９）と、前記第１のハッシュ関数と、前記第２のハッシュ関数と、前記第１のハッシュ値及び前記第２のハッシュ値を用いて生成され、前記署名対象データに付加されている署名と、前記検証鍵とを用いて、前記署名対象データが正当であることを検証する復号装置側検証部（検証部４０３）と、前記復号装置側検証部によって前記署名対象データが正当であることが検証されたことに応じて、前記署名対象データを復号する復号部（部分復号情報生成部４０５）とを備える復号装置（復号サーバ４００１〜４００ｎ）であることを要旨とする。
【００１９】
本発明の第６の特徴は、平文が暗号化された署名対象データの少なくとも一部分を復号することによって生成された複数の部分復号情報（部分復号情報δ）を受信する受信部（受信部５０１）と、前記署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を取得する復元装置側第１のハッシュ関数取得部（検証部５０３及び記憶部５１１）と、少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を取得する復元装置側第２のハッシュ関数取得部（検証部５０３及び記憶部５１１）と、前記受信部が受信した前記部分復号情報を結合し、平文を復元する平文復元部（平文復元部５０５）とを備える平文復元装置（端末装置５００）であることを要旨とする。
【００２０】
本発明の第７の特徴は、本発明の第６の特徴に係り、前記部分復号情報を検証する部分復号情報検証鍵（部分復号検証鍵share vk1,…, share vki,…, share vkn）を用いて、前記部分復号情報が正当であることを検証する復元装置側検証部（検証部５０３）をさらに備え、前記平文復元部は、前記復元装置側検証部によって前記部分復号情報が正当であることが検証されたことに応じて、前記平文を復元することを要旨とする。
【００２１】
本発明の第８の特徴は、暗号化された署名対象データの検証に用いられる検証鍵を少なくとも入力することによって、第１のハッシュ値を生成する第１のハッシュ関数を記憶する情報提供装置側第１のハッシュ関数記憶部（鍵データベース１０３）と、少なくとも前記第１のハッシュ値及び前記署名対象データを入力することによって、第２のハッシュ値を生成する第２のハッシュ関数を記憶する情報提供装置側第２のハッシュ関数記憶部（鍵データベース１０３）と、前記第１のハッシュ関数及び前記第２のハッシュ関数を示す関数情報を提供する情報提供部（提供情報生成部１０１及び送信部１０５）とを備え、前記情報提供部は、少なくとも前記第２のハッシュ値を含む署名を前記署名対象データに付加する署名装置、または前記署名、前記第１のハッシュ値、前記第２のハッシュ値、前記検証鍵を用いて前記署名対象データが正当であることを検証する検証装置の少なくとも何れかに対して、前記第１のハッシュ関数及び前記第２のハッシュ関数を提供する情報提供装置（情報提供サーバ１００）であることを要旨とする。
【００２２】
本発明の第９の特徴は、本発明の第１乃至第３の特徴に係る何れかの署名装置と、本発明の第４の特徴に係る検証装置とを備える署名システムであることを要旨とする。
【００２３】
本発明の第１０の特徴は、本発明の第１乃至第３の特徴に係る何れかの署名装置と、本発明の第４に係る検証装置と、本発明の第５の特徴に係る復号装置と、本発明の第６または第７に係る平文復元装置とを備える通信システムであることを要旨とする。
【００２４】
本発明の第１１の特徴は、本発明の第９の特徴に係る署名システムにおいて用いられ、署名対象データの検証に用いられる検証鍵、及び任意の方法によって定められたシードを生成する鍵生成部（提供情報生成部１０１）と、前記検証鍵を検証装置に送信する検証鍵送信部（送信部１０５）と、前記シードを署名装置に送信するシード送信部（送信部１０５）とを備える鍵生成装置であることを要旨とする。
【００２５】
本発明の第１２の特徴は、本発明の第１０の特徴に係る通信システムにおいて用いられ、少なくとも平文の暗号処理及び暗号化された署名対象データの復号処理に用いられる公開鍵及び復号鍵を生成する鍵生成部（提供情報生成部１０１）と、前記公開鍵を検証装置、復号装置または平文復元装置の少なくとも何れかに送信する公開鍵送信部（送信部１０５）と、前記復号鍵を前記復号装置に送信する復号鍵送信部（送信部１０５）とを備える鍵生成装置であることを要旨とする。
【００２６】
本発明の第１３の特徴は、署名対象データを取得し、任意の方法によって定められたシードを用いて、前記署名対象データの検証に用いられる検証鍵を生成し、前記シードを用いて、前記署名対象データに対応する署名情報を生成し、前記署名情報を含む署名を前記署名対象データに付加し、前記署名を付加する場合には、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、前記検証鍵から作成できない情報を、前記検証鍵及び前記署名情報を用いて抽出でき、前記検証鍵を用いて有効であると判断された有効署名に基づいて、前記検証鍵と異なる他の検証鍵を用いて前記有効署名を作成することができない前記署名を付加する署名方法であることを要旨とする。
【００２７】
本発明の第１４の特徴は、本発明の第１３の特徴に係り、少なくとも前記検証鍵を第１のハッシュ関数に入力し、第１のハッシュ値を生成し、少なくも前記第１のハッシュ値及び前記署名対象データを第２のハッシュ関数に入力して、第２のハッシュ値を生成し、前記第２のハッシュ値及び前記署名情報を含む署名を前記署名対象データに付加することを要旨とする。
【００２８】
本発明の第１５の特徴は、本発明の第１４の特徴に係り、前記署名情報を生成する場合、前記第１のハッシュ値、前記第２のハッシュ値及び前記シードを用いて前記署名情報を生成し、前記第２のハッシュ値と、前記第２のハッシュ値及び前記シードを用いて生成された前記署名情報とを含む署名を、前記検証鍵とともに、前記シードを平文の暗号化における乱数として用いて暗号化された前記署名対象データに付加することを要旨とする。
【発明の効果】
【００２９】
本発明の特徴によれば、妥当な仮定の上での安全性を根拠としつつ、より迅速かつ容易に必要な処理を実行することができる署名装置、検証装置、復号装置、平文復元装置、情報提供装置、署名システム、通信システム、鍵生成装置及び署名方法を提供することができる。
【発明を実施するための最良の形態】
【００３０】
次に、本発明の実施形態について説明する。なお、以下の図面の記載において、同一または類似の部分には、同一または類似の符号を付している。ただし、図面は模式的なものであり、各寸法の比率などは現実のものとは異なることに留意すべきである。
【００３１】
したがって、具体的な寸法などは以下の説明を参酌して判断すべきものである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。
【００３２】
（通信システムの全体概略構成）
図１は、本実施形態に係る通信システムの全体概略構成図である。図１に示すように、本実施形態に係る通信システムは、情報提供サーバ１００、端末装置２００、暗号文管理サーバ３００、復号サーバ４００１〜４００ｎ及び端末装置５００を含む。
【００３３】
また、本実施形態に係る通信システムは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、当該分散鍵を有する複数の復号サーバ（復号サーバ４００１〜４００ｎ）が共同で処理を実行しなければ、平文mを復元できないようにした、いわゆる“しきい値暗号方式”にしたがった通信を実行することができる。また、しきい値暗号方式では、分散鍵を秘密の状態としつつ復号を実行することができる。
【００３４】
通信ネットワーク１０は、通信システムに含まれる各サーバ及び端末装置を接続する通信ネットワークである。また、本実施形態では、端末装置２００及び端末装置５００は、無線基地局１１Ａ，１１Ｂとの間において無線通信を実行する無線通信端末装置である。なお、端末装置２００及び端末装置５００は、無線ではなく、有線によって通信ネットワーク１０に接続する端末装置であってもよい。
【００３５】
情報提供サーバ１００は、端末装置２００から端末装置５００に対して送信される情報（具体的には、平文m）の暗号化及び復号に必要な情報（以下、提供情報）、例えば、公開情報pkや分散鍵skなどを提供する。
【００３６】
端末装置２００は、本実施形態に係るしきい値暗号方式に基づいて、平文mを暗号化した補強暗号文Cを生成する。また、端末装置２００は、生成した補強暗号文Cを暗号文管理サーバ３００に送信する。なお、補強暗号文Cの生成方法については後述する。
【００３７】
暗号文管理サーバ３００は、端末装置２００から送信された補強暗号文Cを格納する。また、暗号文管理サーバ３００は、復号サーバ４００１〜４００ｎまたは端末装置５００からの要求に応じて、格納している補強暗号文Cを送信する。
【００３８】
復号サーバ４００１〜４００ｎは、暗号文管理サーバ３００から送信された補強暗号文Cの正当性を検証するとともに、補強暗号文Cを用いて、平文mの部分的な復号情報である部分復号情報δを生成する。また、復号サーバ４００１〜４００ｎは、生成した部分復号情報δを端末装置５００に送信する。
【００３９】
端末装置５００は、復号サーバ４００１〜４００ｎから送信された部分復号情報δを検証する。また、端末装置５００は、検証した部分復号情報δを用いて、平文mを復元する。
【００４０】
（通信システムの機能ブロック構成）
次に、本実施形態に係る通信システムの機能ブロック構成について説明する。なお、本実施形態では、位数qの群Gにおいて演算を実行するものとする。
【００４１】
また、本実施形態では、素数p（p-1はqを割り切る）に対して、Zp-1の部分群G（位数q）における利用方法を例として説明するが、楕円曲線上でも同様の演算を実行することができる。
【００４２】
さらに、群Gの生成元の一つをg1と定義する。また、特にただし書きがない場合、演算は、mod pにより実行されるものとする。
【００４３】
（１）情報提供サーバ１００
図２は、情報提供サーバ１００の機能ブロック構成図である。図２に示すように、情報提供サーバ１００は、提供情報生成部１０１、鍵データベース１０３及び送信部１０５を備える。本実施形態において、情報提供サーバ１００は、“情報提供装置”を構成する。
【００４４】
提供情報生成部１０１は、公開情報pkや分散鍵skなどを生成する。具体的には、提供情報生成部１０１は、定義域｛0, q-1｝の範囲内において、一様な確率で値を一つ選択し、選択した値（乱数x）を秘密情報xとする。
【００４５】
提供情報生成部１０１は、（１式）を用いて、公開鍵（h）を生成する。
【数１】
2007142897.tif 000003
【００４６】
また、提供情報生成部１０１は、所定の方式（例えば、Shamir法）に基づいて、分散鍵skを生成する。具体的には、提供情報生成部１０１は、秘密情報xを複数（n個）に分散し、複数（n個）の分散鍵sk1,…, ski,…, sknを生成する。
【００４７】
より具体的には、提供情報生成部１０１は、0<i<tに対して、ai∈UZLと定義するとともに、a0=xと定義する。なお、“ＺX”とは、０以上X未満の整数の集合（ZX=Z/XZ）を表す。また、“X∈UG”は、Gから一様な確率で要素Xを選択することを示す。
【００４８】
提供情報生成部１０１は、（２式）及び（３式）を用いて、分散鍵sk1,…, ski,…, sknを生成する。
【数２】
2007142897.tif 000004
【数３】
2007142897.tif 000005
【００４９】
さらに、提供情報生成部１０１は、（４式）を用いて、複数（n個）の部分復号検証鍵share vk1,…, share vki,…, share vknを生成する。
【数４】
2007142897.tif 000006
【００５０】
ここで、νは、群Gの生成元の一つである。
【００５１】
また、提供情報生成部１０１は、端末装置２００において用いられるハッシュ関数H1及びハッシュ関数H2（例えば、SHA-1）を選択することができる。提供情報生成部１０１は、選択したハッシュ関数H1及びハッシュ関数H2を示す情報（関数情報）を端末装置２００などに提供することができる。
【００５２】
さらに、提供情報生成部１０１は、署名対象データの検証に用いられる検証鍵vk、任意の方法によって定められたシード（例えば、乱数）、平文mの暗号処理及び暗号化された署名対象データの復号処理に用いられる公開鍵及び復号鍵を生成することができる。本実施形態において、提供情報生成部１０１は、鍵生成部を構成する。
【００５３】
鍵データベース１０３は、提供情報生成部１０１によって生成された公開情報pk（公開鍵）、分散鍵sk1,…, ski,…, skn及び部分復号検証鍵share vk1,…, share vki,…, share vknなどを格納する。
【００５４】
また、鍵データベース１０３は、端末装置２００において用いられるハッシュ関数H1及びハッシュ関数H2を格納することができる。
【００５５】
送信部１０５は、鍵データベース１０３に格納されている情報、具体的には、公開情報pk（公開鍵）、分散鍵sk1,…, ski,…, skn及び部分復号検証鍵share vk1,…, share vki,…, share vkn、シード、復号鍵などの提供情報を、通信システムを構成する他のサーバなどに送信する。本実施形態において、送信部１０５は、検証鍵送信部、シード送信部、公開鍵送信部及び復号鍵送信部を構成する。
【００５６】
また、送信部１０５は、鍵データベース１０３に格納されているハッシュ関数H1及びハッシュ関数H2を、端末装置２００（署名装置）や復号サーバ４００１〜４００ｎ（検証装置）などに送信することができる。本実施形態では、提供情報生成部１０１と送信部１０５とによって、情報提供部が構成される。
【００５７】
（２）端末装置２００
図３は、端末装置２００の機能ブロック構成図である。図３に示すように、端末装置２００は、受信部２０１、第１乱数生成部２０３、第２乱数生成部２０５、暗号文生成部２０７、検証鍵生成部２０９、第１ハッシュ値生成部２１１、第２ハッシュ値生成部２１３、署名情報生成部２１５、署名部２１７及び送信部２１９を備える。本実施形態において、端末装置２００は、“署名装置”を構成する。
【００５８】
受信部２０１は、情報提供サーバ１００から公開情報pkを受信する。また、受信部２０１は、第１ハッシュ値生成部２１１において用いられるハッシュ関数H1、及び第２ハッシュ値生成部２１３において用いられるハッシュ関数H2を、情報提供サーバ１００から受信することができる。
【００５９】
第１乱数生成部２０３は、署名情報vなどの生成に用いられる乱数sを生成する。具体的には、第１乱数生成部２０３は、定義域｛0, q-1｝の範囲内において、一様な確率で値を選択し、選択した値を乱数sとする。
【００６０】
第２乱数生成部２０５は、暗号文cなどの生成に用いられるシードを生成する。なお、シードとは、任意の方法によって定められた数字列や文字列などである。本実施形態では、第２乱数生成部２０５は、シードとして乱数rを生成する。具体的には、第２乱数生成部２０５は、第１乱数生成部２０３と同様の方法によって、乱数rを生成する。
【００６１】
暗号文生成部２０７は、平文mを暗号化し、暗号文cを生成する。具体的には、暗号文生成部２０７は、（５式）及び（６式）を用いて演算を実行し、暗号文cを生成する。本実施形態において、暗号文生成部２０７は、乱数rを用いて暗号化された暗号文c（署名対象データ）を取得する署名対象データ取得部を構成する。
【数５】
2007142897.tif 000007
【数６】
2007142897.tif 000008
【００６２】
ここで、Hは、ハッシュ関数（例えば、SHA-1）を示す。また、*は、排他的論理和を示す。
【００６３】
検証鍵生成部２０９は、乱数rを用いて、暗号文cの検証に用いられる検証鍵vkを生成する。具体的には、検証鍵生成部２０９は、（７式）を用いて検証鍵vkを生成する。
【数７】
2007142897.tif 000009
【００６４】
ここで、u1が検証鍵vkに相当する。
【００６５】
第１ハッシュ値生成部２１１は、少なくとも検証鍵vkをハッシュ関数H1（第１のハッシュ関数）に入力し、ハッシュ値hA（第１のハッシュ値）を生成する。本実施形態において、第１ハッシュ値生成部２１１は、第１ハッシュ値生成部を構成する。
【００６６】
具体的には、第１ハッシュ値生成部２１１は、（８式）を用いてハッシュ値hAを生成する。
【数８】
2007142897.tif 000010
【００６７】
ここで、g2がハッシュ値hAに相当する。
【００６８】
第２ハッシュ値生成部２１３は、少なくもハッシュ値hA及び暗号文cをハッシュ関数H2（第２のハッシュ関数）に入力し、ハッシュ値hB（第２のハッシュ値）を生成する。本実施形態において、第２ハッシュ値生成部２１３は、第２ハッシュ値生成部を構成する。
【００６９】
具体的には、第２ハッシュ値生成部２１３は、（９式）を用いてハッシュ値hBを生成する。
【数９】
2007142897.tif 000011
【００７０】
ここで、eがハッシュ値hBに相当する。また、第２ハッシュ値生成部２１３は、（１０式）〜（１２式）を用いて、w1、w2及びu2を演算する。
【数１０】
2007142897.tif 000012
【数１１】
2007142897.tif 000013
【数１２】
2007142897.tif 000014
【００７１】
署名情報生成部２１５は、乱数rを用いて、暗号文cに対応する署名情報vを生成する。具体的には、署名情報生成部２１５は、ハッシュ値hA、ハッシュ値hB及び乱数rを用いて署名情報vを生成する。
【数１３】
2007142897.tif 000015
【００７２】
本実施形態では、f及びu2が署名情報vに相当する。
【００７３】
署名部２１７は、署名情報vを含む署名σを暗号文cに付加する。具体的には、署名部２１７は、署名σを（e，u2, f）として、暗号文cに付加する。
【００７４】
さらに、署名部２１７は、暗号文cに署名σが付加された補強暗号文Cを出力する。なお、補強暗号文Cは、（１４式）に示すような構成を有する。
【数１４】
2007142897.tif 000016
【００７５】
上述した署名情報生成部２１５は、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、検証鍵vkから作成できない情報（例えば、hやu1を用いて実行したしきい値暗号方式にしたがった演算結果）を、検証鍵vk及び署名情報vを用いて抽出できる。
【００７６】
より忠実には、ランダムオラクルの存在を仮定した場合、署名部２１７は、部分復号情報δを圧倒的に高い確率で抽出できる署名σを付加することができる。
【００７７】
さらに、署名情報生成部２１５は、検証鍵vkを用いて有効であると判断された署名σ（有効署名）と、検証鍵vkとのペアに基づいて、検証鍵vkと同一の検証鍵、さらには、検証鍵vkと異なる他の検証鍵と、有効署名とのペアを作成することができない署名情報vを生成することができる。
【００７８】
例えば、通常の署名では、（vk,σ,m）から（vk,σ',m'）を得ることができない（ここで、少なくともσ≠σ'もしくはm≠m'の何れかが成立）。本実施形態に係る署名では、（vk,σ,m）から（vk',σ',m'）を得ることができない（ここで、少なくともvk', σ', m'は、σ≠σ'、m≠mもしくはvk≠vk'の何れかが成立）。
【００７９】
また、署名部２１７は、上述したように、e（ハッシュ値hB）及びf（署名情報v）を含む署名σを前記署名対象データに付加することができる。さらに、署名部２１７は、e（ハッシュ値hB）と、e（ハッシュ値hB）及び乱数rを用いて生成されたf（署名情報v）とを含む署名σを、u1（検証鍵vk）とともに、乱数rを平文mの暗号化における乱数として用いて暗号化された暗号文cに付加することができる。
【００８０】
送信部２１９は、署名部２１７によって出力された補強暗号文Cを暗号文管理サーバ３００に送信する。
【００８１】
（３）暗号文管理サーバ３００
図４は、暗号文管理サーバ３００の機能ブロック構成図である。図４に示すように、暗号文管理サーバ３００は、受信部３０１、暗号文管理部３０３、暗号文データベース３０５及び送信部３０７を備える。
【００８２】
受信部３０１は、端末装置２００から補強暗号文Cを受信する。また、受信部３０１は、復号サーバ４００１〜４００ｎから補強暗号文Cの送信要求を受信する。
【００８３】
暗号文管理部３０３は、受信部３０１が受信した補強暗号文Cを、送信元の端末装置ごとに管理する。また、暗号文管理部３０３は、受信部３０１が受信した補強暗号文Cを暗号文データベース３０５に格納する。
【００８４】
暗号文データベース３０５は、受信部３０１が受信した補強暗号文Cを格納するデータベースである。暗号文データベース３０５は、受信部３０１が受信した補強暗号文Cと、当該補強暗号文Cに対応する公開情報pkとを対応付けて格納する。
【００８５】
送信部３０７は、復号サーバ４００１〜４００ｎからの補強暗号文Cの送信要求に応じて、補強暗号文Cを復号サーバ４００１〜４００ｎに送信する。
【００８６】
（４）復号サーバ４００１〜４００ｎ
図５は、復号サーバ４００１の機能ブロック構成図である。図４に示すように、復号サーバ４００１は、受信部４０１、検証部４０３、部分復号情報生成部４０５、送信部４０７及び記憶部４０９を備える。
【００８７】
なお、本実施形態では、復号サーバは複数（４００１〜４００ｎ）設けられており、他の復号サーバも復号サーバ４００１と同一の機能ブロック構成を有する。
【００８８】
また、本実施形態において、復号サーバ４００１〜４００ｎは、“検証装置”及び“復号装置”を構成する。さらに、本実施形態では、端末装置２００と復号サーバ４００１〜４００ｎとによって、“署名システム”が構成される。
【００８９】
受信部４０１は、暗号文管理サーバ３００から分散鍵sk及び補強暗号文Cを受信する。
【００９０】
検証部４０３は、補強暗号文Cに含まれる暗号文cが正当であることを検証する。具体的には、検証部４０３は、ハッシュ関数H1と、ハッシュ関数H2と、ハッシュ値hA（第１のハッシュ値）及びハッシュ値hB（第２のハッシュ値）を用いて生成され暗号文c（署名対象データ）に付加されている署名σとを用いて暗号文cが正当であることを検証する。本実施形態において、検証部４０３は、検証装置側検証部を構成する。
【００９１】
より具体的には、検証部４０３は、（１５式）を用いてg2を求める。
【数１５】
2007142897.tif 000017
【００９２】
さらに、検証部４０３は、（１６式）を用いて当該演算が成立するか否かを判定する。検証部４０３は、当該演算が成立する場合、暗号文cが正当であると判定する。
【数１６】
2007142897.tif 000018
【００９３】
すなわち、検証部４０３は、ハッシュ関数H1と、ハッシュ関数H2と、ハッシュ値hA（第１のハッシュ値）及びハッシュ値hB（第２のハッシュ値）を用いて生成され暗号文c（署名対象データ）に付加されている署名σと、u1（検証鍵vk）とを用いて、暗号文cが正当であることを検証する。本実施形態において、検証部４０３は、復号装置側検証部を構成する。
【００９４】
また、検証部４０３は、部分復号情報δが正当であることを検証することができる。検証部４０３は、部分復号情報δが正当であることを証明する正当性証明情報pfを端末装置５００に送信することができる。
【００９５】
部分復号情報生成部４０５は、部分復号情報δを生成する。具体的には、部分復号情報生成部４０５は、検証部４０３によって暗号文cが正当であることが検証されたことに応じて、暗号文cを復号する。本実施形態において、部分復号情報生成部４０５は、復号部を構成する。
【００９６】
具体的には、部分復号情報生成部４０５は、（１７式）を用いて部分復号情報δ（δi）を生成する。
【数１７】
2007142897.tif 000019
【００９７】
送信部４０７は、部分復号情報生成部４０５によって生成された部分復号情報δを端末装置５００に送信する。
【００９８】
記憶部４０９は、ハッシュ関数H1及びハッシュ関数H2を記憶する。本実施形態では、検証部４０３と記憶部４０９とによって、検証装置側第１のハッシュ関数取得部、検証装置側第２のハッシュ関数取得部、復号装置側第１のハッシュ関数取得部、及び復号装置側第２のハッシュ関数取得部が構成される。
【００９９】
なお、本実施形態では、記憶部４０９にハッシュ関数H1及びハッシュ関数H2に記憶されているが、ハッシュ関数H1及びハッシュ関数H2は、必要なときに、通信ネットワーク１０などを介して外部から取得してもよい。
【０１００】
（５）端末装置５００
図６は、端末装置５００の機能ブロック構成図である。図６に示すように、端末装置５００は、受信部５０１、検証部５０３、平文復元部５０５、送信部５０７、出力部５０９及び記憶部５１１を備える。本実施形態において、端末装置５００は、“平文復元装置”を構成する。
【０１０１】
受信部５０１は、復号サーバ４００１〜４００ｎのそれぞれによって復号された部分復号情報δを、復号サーバ４００１〜４００ｎから受信する。すなわち、受信部５０１は、平文mが暗号化された暗号文cの少なくとも一部分を復号することによって生成された複数の部分復号情報δ（δ1〜δn）を受信する。
【０１０２】
また、受信部５０１は、部分復号情報δが正当であることを示す正当性証明情報pfを、復号サーバ４００１〜４００ｎから受信する。さらに、受信部５０１は、情報提供サーバ１００から部分復号検証鍵share vk1,…, share vki,…, share vknを受信する。
【０１０３】
検証部５０３は、部分復号情報δ（δ1〜δn）が正当であることを検証する。本実施形態において、検証部５０３は、復元装置側検証部を構成する。具体的には、検証部５０３は、ハッシュ関数H1と、ハッシュ関数H2と、ハッシュ値hA（第１のハッシュ値）及びハッシュ値hB（第２のハッシュ値）を用いて生成され暗号文c（署名対象データ）に付加されている署名σと、部分復号検証鍵share vk1,…, share vki,…, share vknとを用いて、部分復号情報δ（δ1〜δn）が正当であることを検証する。
【０１０４】
より具体的には、検証部５０３は、上述した非特許文献１に記載されている方法にしたがって、部分復号検証鍵share vk1,…, share vki,…, share vknのそれぞれと、それらの生成元νと、正当性証明情報pfとを用いて、複数の部分復号情報δ1〜δnのそれぞれを検証する。
【０１０５】
平文復元部５０５は、検証部５０３によって暗号文cが正当であることが検証されたことに応じて、受信部５０１が受信した部分復号情報δ（δ1〜δn）を結合し、平文mを復元する。具体的には、平文復元部５０５は、（１８式）及び（１９式）を用いて平文mを復元する。
【数１８】
2007142897.tif 000020
【数１９】
2007142897.tif 000021
【０１０６】
送信部５０７は、補強暗号文Cの送信要求を暗号文管理サーバ３００に送信する。また、送信部５０７は、補強暗号文Cの復号要求を復号サーバ４００１〜４００ｎに送信する。
【０１０７】
出力部５０９は、平文復元部５０５によって復元された平文mを出力、例えば、表示部（不図示）に表示したり、文書ファイルとして生成したりすることができる。
【０１０８】
記憶部５１１は、ハッシュ関数H1及びハッシュ関数H2を記憶する。本実施形態では、検証部５０３と記憶部５１１とによって、復元装置側第１のハッシュ関数取得部、及び復元装置側第２のハッシュ関数取得部が構成される。
【０１０９】
なお、本実施形態では、記憶部５１１にハッシュ関数H1及びハッシュ関数H2に記憶されているが、ハッシュ関数H1及びハッシュ関数H2は、必要なときに、通信ネットワーク１０などを介して外部から取得してもよい。
【０１１０】
（通信システムの動作）
次に、上述した通信システムの動作について説明する。具体的には、（１）鍵生成処理、（２）暗号化処理、及び（３）復号及び復元処理の内容について説明する。
【０１１１】
（１）鍵生成処理
図７は、通信システムの全体概略シーケンス図である。まず、鍵生成処理について説明する。図７に示すように、ステップＳ１０において、情報提供サーバ１００は、通信システムを構成する他の装置に提供される提供情報を生成する。
【０１１２】
具体的には、情報提供サーバ１００は、公開情報pk（公開鍵）、分散鍵sk1,…, ski,…, skn及び部分復号検証鍵share vk1,…, share vki,…, share vknを生成する。
【０１１３】
ステップＳ２０において、情報提供サーバ１００は、生成した公開情報pkを端末装置２００、暗号文管理サーバ３００、復号サーバ４００１〜４００ｎ及び端末装置５００にそれぞれ送信する。
【０１１４】
ステップＳ３０において、情報提供サーバ１００は、生成した分散鍵sk1,…, ski,…, sknを復号サーバ４００１〜４００ｎに送信する。例えば、情報提供サーバ１００は、分散鍵sk1を復号サーバ４００１に送信する。
【０１１５】
ステップＳ４０において、情報提供サーバ１００は、生成した部分復号検証鍵share vk1,…, share vki,…, share vknを端末装置５００に送信する。
【０１１６】
（２）暗号化処理
次に、暗号化処理について説明する。図７に示すように、ステップＳ１００において、端末装置２００は、平文mの暗号化処理を実行する。具体的には、端末装置２００は、図８に示す暗号化処理フローにしたがって、平文mの暗号化処理を実行する。
【０１１７】
図８に示すように、ステップＳ１０１において、端末装置２００は、乱数rを選択する。
【０１１８】
ステップＳ１０３において、端末装置２００は、（５式）を用いて、べき乗演算を実行する。
【０１１９】
ステップＳ１０５において、端末装置２００は、（７式）を用いた演算を実行し、u1（検証鍵vk）を生成する。
【０１２０】
ステップＳ１０７において、端末装置２００は、（８式）を用いた演算を実行し、g2（ハッシュ値hA）を演算する。
【０１２１】
ステップＳ１０９において、端末装置２００は、（１１式）を用いて、u2を演算する。
【０１２２】
ステップＳ１１１において、端末装置２００は、乱数sを選択する。
【０１２３】
ステップＳ１１３において、端末装置２００は、（１０式）を用いて、w1を演算する。
【０１２４】
ステップＳ１１５において、端末装置２００は、（１１式）を用いて、w2を演算する。
【０１２５】
なお、ステップＳ１０１〜Ｓ１１５の処理順序は、必ずしも図８に示したフローにしたがう必要はない。また、ステップＳ１０１〜Ｓ１１５の処理は、平文mが決定する前に、予め実行することができる。
【０１２６】
ステップＳ１１７において、端末装置２００は、（６式）を用いた演算を実行し、暗号文cを生成する。
【０１２７】
ステップＳ１１９において、端末装置２００は、（９式）を用いた演算を実行し、e（ハッシュ値hB）を生成する。
【０１２８】
ステップＳ１２１において、端末装置２００は、（１３式）を用いた演算を実行し、f（署名情報v）を生成する。
【０１２９】
ステップＳ１２３において、端末装置２００は、（１４式）を用いた演算を実行し、補強暗号文Cを生成する。
【０１３０】
次に、図７に示すように、ステップＳ２００において、端末装置２００は、生成した補強暗号文Cを暗号文管理サーバ３００に送信する。
【０１３１】
ステップＳ２１０において、暗号文管理サーバ３００は、受信した補強暗号文Cを格納する。
【０１３２】
（３）復号及び復元処理
次に、復号及び復元処理について説明する。図７に示すように、ステップＳ２２０において、端末装置５００は、補強暗号文Cの送信要求を暗号文管理サーバ３００に送信する。
【０１３３】
ステップＳ２３０において、暗号文管理サーバ３００は、当該送信要求に基づいて、格納している補強暗号文Cを端末装置５００に送信する。なお、ステップＳ２２０及びＳ２３０の処理は省略しても構わない。
【０１３４】
ステップＳ２４０において、端末装置５００は、補強暗号文Cに含まれる暗号文cの復号要求を復号サーバ４００１〜４００ｎに送信する。
【０１３５】
ステップＳ２５０において、復号サーバ４００１〜４００ｎは、当該復号要求に基づいて、補強暗号文Cの送信要求を暗号文管理サーバ３００に送信する。
【０１３６】
ステップＳ２６０において、暗号文管理サーバ３００は、当該送信要求に基づいて、格納している補強暗号文Cを端末装置５００に送信する。
【０１３７】
ステップＳ２７０において、復号サーバ４００１〜４００ｎは、補強暗号文Cに含まれる暗号文cの正当性を検証する。具体的には、復号サーバ４００１〜４００ｎは、図９に示すフローにしたがって正当性検証処理と復号処理を実行する
図９に示すように、ステップＳ２７１において、復号サーバ（例えば、復号サーバ４００１）は、（１５式）を用いてg2を求める。ステップＳ２７３において、復号サーバは、（１６式）を用いてe'を求める。
【０１３８】
ステップＳ２７５において、復号サーバは、当該演算が成立するか否かを判定する。当該演算が成立する場合（ステップＳ２７５のＹＥＳ）、ステップＳ２７７において、復号サーバは、暗号文cが正当であると判定し、暗号文cを復号する。
【０１３９】
一方、当該演算が成立しない場合（ステップＳ２７５のＮＯ）、ステップＳ２７９において、復号サーバは、暗号文cが正当でないと判定し、Invalid symbolを出力する。
【０１４０】
次いで、図８に示すように、ステップＳ２８０において、復号サーバ４００１〜４００ｎは、部分復号情報δ（δ1〜δn）を生成する。具体的には、復号サーバ４００１〜４００ｎのそれぞれは、（１７式）を用いて部分復号情報δを生成する。
【０１４１】
ステップＳ２９０において、復号サーバ４００１〜４００ｎは、生成した部分復号情報δ（δ1〜δn）を端末装置５００に送信する。
【０１４２】
ステップＳ３００において、端末装置５００は、受信した部分復号情報δ（δ1〜δn）の正当性を検証する。具体的には、端末装置５００は、（１８式）を用いて演算を実行し、部分復号検証鍵share vk1,…, share vki,…, share vknのそれぞれと、それらの生成元νと、正当性証明情報pfとを用いて、複数の部分復号情報δ1〜δnのそれぞれを検証する。
【０１４３】
ステップＳ３１０において、端末装置５００は、部分復号情報δ（δ1〜δn）を結合し、（１９式）を用いて平文mを復元する。
【０１４４】
（作用・効果）
以上説明した本実施形態に係る通信システムによれば、平文m（署名対象データ）が決定する前に、予めハッシュ値hAを演算することができる。さらに、平文mが決定する前に、ハッシュ値hAを用いる他の演算（例えば、（１１式）や（１２式））も実行することができる。
【０１４５】
また、本通信システムによれば、すべてのべき乗の演算を平文mが決定するよりも前に実行することができるため、平文mの決定後、迅速かつ効率的に平文mを暗号化することができる。
【０１４６】
すなわち、本通信システムによれば、上述した非特許文献１に記載されているしきい値暗号方式と比較して、平文mの暗号化処理を実行する端末装置２００に要求される処理能力や必要記憶容量が低減される。このため、処理能力や記憶容量が限定的な無線通信端末装置であっても迅速かつ効率的に平文mを暗号化することができる。
【０１４７】
さらに、本通信システムによれば、少なくとも検証鍵vkをハッシュ関数H1に入力すること、及びハッシュ関数H2を用いることによって、“緊密な安全性”が達成される。ここで、緊密な安全性とは、以下の議論において確率PAと、確率PBとの差が無視できるほど小さいことをいう。
【０１４８】
暗号方式や署名方式の安全性に関する議論では、当該方式の安全性を確率PAで破る攻撃者が居たときに、安全性の根拠となる仮定（ある問題が難しいという仮定）を確率PBで破れるという帰着を行う。
【０１４９】
つまり、緊密な安全性では、当該署名方式にしたがった署名をもとに、ランダムオラクルをシミュレーションした場合、安全性の根拠となる問題を圧倒的な確率で解くということになる。このとき、確率PAと確率PBとの差は、小さいほうがいい。確率PA＝1であっても、確率PB≒0.00000000000001では帰着効率が悪く、仮定の内容に飛躍があり過ぎて望ましくない。
【０１５０】
また、暗号文cに単に署名を付加すると、次の二つの問題があり、安全性の向上が保障されない。
【０１５１】
まず、選択暗号文攻撃においてターゲットとなる暗号文c、つまり、攻撃者は、解読したい暗号文（検証鍵を含む）をもとに、別な検証鍵で有効だと判断される署名を偽造する。攻撃者は、暗号文cと何らかの関連性がある暗号文c'を構成できてしまうと、暗号文c'の復号結果から暗号文cに関する情報を得られる可能性がある。このような事象は、ある検証鍵のもとで有効だと判断される署名をもとに、別な検証鍵で有効だと判断される署名を偽造できる場合に発生し得る。
【０１５２】
このような事象は、検証鍵vkをハッシュ関数H1に入力すること、及びハッシュ関数H2を用いることによって防止できる。
【０１５３】
また、“緊密な安全性”を有さない署名を用いると、選択暗号文攻撃に対する安全性の証明が行えないといった問題がある。選択暗号文攻撃を選択平文攻撃と同様にするために選択暗号文攻撃による復号結果の“シミュレーション”を実行する都度、確率PAと確率PBとの差がどんどん大きくなってしまうためである。
【０１５４】
なお、“シミュレーション”とは、安全性証明に用いる手法の一つである。具体的には、攻撃者が得た情報を攻撃者自身が構成（シミュレーション）可能な場合、攻撃者が得た情報に価値が無いと見なし、「当該情報を与えても攻撃者の攻撃は有利にならない」とする議論のことである。解読できない署名や暗号文にシミュレーションできる情報を与えてもその署名や暗号文は安全と見なす。
【０１５５】
緊密な安全性を有する署名では、ランダムオラクルモデルのもとにおいて、ある問題を署名の結果から圧倒的な確率で解くということになる。
【０１５６】
上述したように、本通信システムでは、検証鍵vkをハッシュ関数H1に入力すること、及びハッシュ関数H2を用いるため、攻撃者が署名を構成した場合、秘密鍵に関する部分情報を持っていることになるため、秘密鍵（暗号化のための乱数）に関する情報をもとに復号結果のシミュレーションを実行することができる。
【０１５７】
つまり、以上説明したように、本通信システムによれば、決定問題の困難性（hardness of the computational Diffie-Hellman problem）という妥当な仮定の上での安全性を根拠としつつ、より迅速かつ容易に暗号化などに必要な処理を実行することができる。
【０１５８】
（その他の実施形態）
上述したように、本発明の一実施形態を通じて本発明の内容を開示したが、この開示の一部をなす論述及び図面は、本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態が明らかとなろう。
【０１５９】
例えば、上述した本発明の実施形態では、Diffie-Hellman（DH）に基づくしきい値暗号方式を例として説明したが、例えば、RSAに基づくしきい値暗号方式にも本発明を適用することができる。また、これらのしきい値暗号方式に基づいて、一般的な公開鍵暗号方式において用いられる情報（秘密鍵や公開鍵）を構成することもできる。
【０１６０】
例えば、RSAの場合、鍵生成としてはじめにΛ/2ビットの素数p, qを生成する。ここで、セキュリティパラメータΛ2を導入する。また、gcd(e, φ(N)) = 1 となるような整数eを選択する。暗号文の生成は以下のように実行する。まず、0からN-1までの範囲で一様な確率で乱数sを演算し、h = seとなるhを求める。検証鍵はhになり、これらを用いて、以下の演算を実行する。
【０１６１】
署名σ = (u, v)は以下のように生成する。平文のビット数を“l”（エル）としてハッシュ関数は（２０式）のように定義する。また、特にただし書きがない場合、演算はmod Nにより実行されるものとする。
【数２０】
2007142897.tif 000022
【０１６２】
まず、（２１式）による演算を実行する。次いで、乱数rj(j = 1, 2, . . .,Λ2)、（２２式）及び（２３式）を用いて、コミット値CTを演算する。
【数２１】
2007142897.tif 000023
【数２２】
2007142897.tif 000024
【数２３】
2007142897.tif 000025
【０１６３】
次に、（２４式）を用いて、チャレンジctを得る。
【数２４】
2007142897.tif 000026
【０１６４】
さらに、（２５式）を用いて、レスポンスRを返す。また、暗号文は、（２６式）に示すような構成となる。
【数２５】
2007142897.tif 000027
【数２６】
2007142897.tif 000028
【０１６５】
検証は以下のように実行する。まず、（２７式）による演算を実行する。
【数２７】
2007142897.tif 000029
【０１６６】
次に、（２８式）が成立するか否かを判定する。なお、sの抽出は、Hの監視により可能となることにより安全性の証明を実行する。
【数２８】
2007142897.tif 000030
【０１６７】
なお、暗号文が正しい場合、hを部分復号し、部分復号情報を出力する。部分復号、部分復号情報の検証及び復号処理の方法は、「P.-A.Fouque, G.Poupard and J.Stern, "Sharing Decryption in the Context of Voting or Lotteries," Financial Cryptography 2000, pp.90--104, 2000」において紹介されている方法を用いることができる。
【０１６８】
また、上述した本発明の実施形態では、署名装置として、無線通信端末装置である端末装置２００を用いる形態としたが、本発明は、携帯情報端末（ＰＤＡ）やＩＣカードにも適用することができる。
【０１６９】
上述した本発明の実施形態では、復号サーバ４００１〜４００ｎが、検証装置及び復号装置の機能を具備する形態としたが、検証装置の機能を提供するサーバを復号サーバ４００１〜４００ｎと別個に設けても構わない。
【０１７０】
上述した本発明の実施形態では、暗号文管理サーバ３００を介して補強暗号文Cを送受信する形態としたが、端末装置２００は、暗号文管理サーバ３００を用いずに、復号サーバ４００１〜４００ｎに直接補強暗号文Cを送信するようにしてもよい。さらに、復号サーバ４００１〜４００ｎが端末装置５００の機能を兼ね備え、平文mを復元するようにしてもよい。
【０１７１】
また、端末装置２００の機能及び端末装置５００の機能を１台の端末装置に具備してもよい。さらに、上述した通信システムを構成する各装置の機能は、コンピュータや通信端末装置において実行可能なプログラムとしても提供することもできる。
【０１７２】
上述した本発明の実施形態では、乱数rを用いて暗号化された暗号文cを署名対象データとしていて、かつ乱数rをシードとして用いているが、暗号化されていない署名対象データに署名σを付加してもよい。
【０１７３】
このように、本発明は、ここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は、上述の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１７４】
【図１】本発明の実施形態に係る通信システムの全体概略構成図である。
【図２】本発明の実施形態に係る情報提供サーバの機能ブロック構成図である。
【図３】本発明の実施形態に係る端末装置（暗号化側）の機能ブロック構成図である。
【図４】本発明の実施形態に係る暗号文管理サーバの機能ブロック構成図である。
【図５】本発明の実施形態に係る復号サーバの機能ブロック構成図である。
【図６】本発明の実施形態に係る端末装置（復元側）の機能ブロック構成図である。
【図７】本発明の実施形態に係る通信システムの全体概略シーケンス図である。
【図８】本発明の実施形態に係る端末装置（暗号化側）における暗号化処理フローである。
【図９】本発明の実施形態に係る復号サーバにおける正当性検証処理と復号処理のフローである。
【符号の説明】
【０１７５】
１０…通信ネットワーク、１１Ａ，１１Ｂ…無線基地局、１００…情報提供サーバ、１０１…提供情報生成部、１０３…鍵データベース、１０５…送信部、２００…端末装置、２０１…受信部、２０３…第１乱数生成部、２０５…第２乱数生成部、２０７…暗号文生成部、２０９…検証鍵生成部、２１１…第１ハッシュ値生成部、２１３…第２ハッシュ値生成部、２１５…署名情報生成部、２１７…署名部、２１９…送信部、３００…暗号文管理サーバ、３０１…受信部、３０３…暗号文管理部、３０５…暗号文データベース、３０７…送信部、４００１〜４００ｎ…復号サーバ、４０１…受信部、４０３…検証部、４０５…部分復号情報生成部、４０７…送信部、４０９…記憶部、５００…端末装置、５０１…受信部、５０３…検証部、５０５…平文復元部、５０７…送信部、５０９…出力部、５１１…記憶部
【図１】
2007142897.tif 000031
【図２】
2007142897.tif 000032
【図３】
2007142897.tif 000033
【図４】
2007142897.tif 000034
【図５】
2007142897.tif 000035
【図６】
2007142897.tif 000036
【図７】
2007142897.tif 000037
【図８】
2007142897.tif 000038
【図９】
2007142897.tif 000039