(57)【要約】【課題】すべての鍵関連データを抽出できる確率を一定の値以上としつつ、暗号方式の安全性を証明することができる署名検証装置、暗号化装置、署名検証方法及び暗号化方法を提供する。【解決手段】復号サーバ４００１〜４００ｎは、所定の条件、例えば、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合において、署名対象データと署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるか否かを検証する。【選択図】図４
2008135869.tif 000002
【特許請求の範囲】
【請求項１】
所定の暗号方式にしたがった暗号システムにおいて用いられる署名検証装置であって、
署名対象データ、及び前記署名対象データに対応する署名情報を取得する取得部と、
所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるか否かを検証する検証部と
を備え、
前記所定の条件は、
前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、
前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、
出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、
のうち、少なくとも何れかである署名検証装置。
【請求項２】
所定の暗号方式にしたがった暗号システムにおいて用いられる暗号化装置であって、
署名鍵の元となる署名鍵元データを用いて、暗号化対象データの暗号化に用いられるデータ用共通鍵を暗号化した暗号データを出力する暗号データ出力部と、
署名対象データ、前記署名対象データに対応する署名情報及び前記暗号データを含む補強暗号文を出力する補強暗号文出力部と、
少なくとも前記暗号データを入力として前記署名対象データ、及び前記署名対象データの検証に用いられる検証鍵を出力する検証鍵出力部と
を備え、
前記署名情報は、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる前記検証鍵とを用いて、前記署名鍵を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるように構成され、
前記所定の条件は、
前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、
前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、
出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、
のうち、少なくとも何れかである暗号化装置。
【請求項３】
所定の暗号方式にしたがった暗号システムにおいて用いられる署名検証方法であって、
署名対象データ、及び前記署名対象データに対応する署名情報を取得するステップと、
所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるか否かを検証するステップと
を備え、
前記所定の条件は、
前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、
前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、
出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、
のうち、少なくとも何れかである署名検証方法。
【請求項４】
所定の暗号方式にしたがった暗号システムにおいて用いられる暗号化方法であって、
署名鍵の元となる署名鍵元データを用いて、暗号化対象データの暗号化に用いられるデータ用共通鍵を暗号化した暗号データを出力するステップと、
署名対象データ、前記署名対象データに対応する署名情報及び前記暗号データを含む補強暗号文を出力するステップと
を備え、
前記署名情報は、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、前記署名鍵を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるように構成され、
前記所定の条件は、
前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、
前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、
出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、
のうち、少なくとも何れかである暗号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方式など、所定の暗号方式にしたがった暗号システムにおいて用いられる署名検証装置、暗号化装置、署名検証方法及び暗号化方法に関する。
【背景技術】
【０００２】
今日、秘匿性を保ちつつ安全に情報を送受信するため、RSAなどの公開鍵暗号方式が広く用いられている。
【０００３】
公開鍵暗号方式を用いて電子署名をする場合において、一定の条件の下（例えば、ランダムオラクルの存在を仮定した場合）、署名データ（例えば、電子署名が付加された暗号文）から、電子署名に用いられる署名鍵に関連する“鍵関連データ”を抽出できる確率を一定の値以上とすることにより、当該暗号方式の安全性を示す方法が知られている（例えば、非特許文献１）。
【０００４】
なお、鍵関連データとは、署名鍵を用いれば容易に構成できるが、署名鍵を用いなければ構成が困難なデータである。すなわち、正しい鍵関連データを示すことができる場合、当該装置（ユーザ）は、当該鍵関連データに対応する署名鍵を用いて当該署名データを生成したことを示すことができる。
【非特許文献１】Yiannis Tsiounis and Moti Yung、“On the Security of ElGamal Based Encryption”、Public Key Cryptography 1998，pp.117-134、１９９８年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した鍵関連データを抽出できる確率を一定の値以上とする方法には、次のような問題があった。すなわち、署名鍵や鍵関連データを抽出できる確率を一定の値以上とする方法を暗号方式の安全性の向上に用いているため、当該暗号方式の安全性を証明することができない。
【０００６】
具体的には、選択暗号文攻撃における安全性の証明において、鍵関連データの抽出が何度も行われる。このため、すべての鍵関連データを抽出できる確率が小さくなり、当該暗号方式が安全であることを証明することができない。例えば、鍵関連データを１回のみ抽出する場合において鍵関連データを抽出できる確率が１０−９であるとすると、鍵関連データを１０９回すべて抽出できる確率は、１０−１８となり、極めて小さくなってしまう。
【０００７】
そこで、本発明は、このような状況に鑑みてなされたものであり、すべての鍵関連データを抽出できる確率を一定の値以上としつつ、暗号方式の安全性を証明することができる署名検証装置、暗号化装置、署名検証方法及び暗号化方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した問題を解決するため、本発明は、次のような特徴を有している。まず、本発明の第１の特徴は、所定の暗号方式（しきい値暗号方式）にしたがった暗号システムにおいて用いられる署名検証装置（復号サーバ４００１〜４００ｎ）であって、署名対象データ（暗号文c）、及び前記署名対象データに対応する署名情報（署名情報v）を取得する取得部（受信部４０１）と、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵（検証鍵vk）とを用いて、署名鍵（署名鍵Sgk）を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるか否かを検証する検証部（検証部４０３）とを備え、前記所定の条件は、前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータ（システムパラメータparams）を任意に決定できる場合、前記署名情報の生成に用いられるハッシュ関数（ハッシュ関数H）への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、のうち、少なくとも何れかであることを要旨とする。
【０００９】
このような署名検証装置によれば、所定の条件の下、署名対象データと、署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが署名鍵を用いなければ構成が困難な鍵関連データを抽出できるか否かが検証される。このため、選択暗号文攻撃における安全性の証明において、鍵関連データの抽出を何度も行ってもすべての鍵関連データを抽出できる確率が小さくなることを回避しつつ、署名対象データの安全性を検証することができる。
【００１０】
本発明の第２の特徴は、所定の暗号方式（しきい値暗号方式）にしたがった暗号システムにおいて用いられる暗号化装置（データ用共通鍵暗号化装置６００）であって、署名鍵（署名鍵Sgk）の元となる署名鍵元データ（署名鍵元データS）を用いて、暗号化対象データ（平文m）の暗号化に用いられるデータ用共通鍵（データ用共通鍵k）を暗号化した暗号データ（暗号データh）を出力する暗号データ出力部（暗号データ出力部６０５）と、署名対象データ、前記署名対象データに対応する署名情報及び前記暗号データを含む補強暗号文（補強暗号文C）を出力する補強暗号文出力部（補強暗号文出力部６０７）と、少なくとも前記暗号データを入力として前記署名対象データ、及び前記署名対象データの検証に用いられる検証鍵を出力する検証鍵出力部（検証鍵出力部６０９）とを備え、前記署名情報は、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、前記署名鍵を用いれば容易に構成できるが前記署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるように構成され、前記所定の条件は、前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータ（システムパラメータparams）を任意に決定できる場合、前記署名情報の生成に用いられるハッシュ関数（ハッシュ関数H）への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、のうち、少なくとも何れかであることを要旨とする。
【００１１】
本発明の第３の特徴は、所定の暗号方式にしたがった暗号システムにおいて用いられる署名検証方法であって、署名対象データ、及び前記署名対象データに対応する署名情報を取得するステップと、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるか否かを検証するステップとを備え、前記所定の条件は、前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、のうち、少なくとも何れかであることを要旨とする。
【００１２】
本発明の第４の特徴は、所定の暗号方式にしたがった暗号システムにおいて用いられる暗号化方法であって、署名鍵の元となる署名鍵元データを用いて、暗号化対象データの暗号化に用いられるデータ用共通鍵を暗号化した暗号データを出力するステップと、署名対象データ、前記署名対象データに対応する署名情報及び前記暗号データを含む補強暗号文を出力するステップとを備え、前記署名情報は、所定の条件において、前記署名対象データと前記署名対象データの検証に用いられる検証鍵とを用いて、署名鍵を用いれば容易に構成できるが署名鍵を用いなければ構成が困難な鍵関連データを略１の確率で抽出できるように構成され、前記所定の条件は、前記暗号システムにおいて用いられる少なくとも一部のシステムパラメータを任意に決定できる場合、前記署名情報の生成に用いられるハッシュ関数への入力値、及び前記入力値に対応する前記ハッシュ関数からの出力値を取得できる場合、または、出力が常に一様分布にしたがって決まり、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、のうち、少なくとも何れかであることを要旨とする。
【発明の効果】
【００１３】
本発明の特徴によれば、すべての鍵関連データを抽出できる確率を一定の値以上としつつ、暗号方式の安全性を証明する署名検証装置、暗号化装置、署名検証方法及び暗号化方法を提供することができる。
【発明を実施するための最良の形態】
【００１４】
次に、本発明の実施形態について説明する。なお、以下の図面の記載において、同一または類似の部分には、同一または類似の符号を付している。ただし、図面は模式的なものであり、各寸法の比率などは現実のものとは異なることに留意すべきである。
【００１５】
したがって、具体的な寸法などは以下の説明を参酌して判断すべきものである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。
【００１６】
（暗号システムの全体概略構成）
図１は、本実施形態に係る暗号システムの全体概略構成図である。図１に示すように、本実施形態に係る暗号システムは、情報提供サーバ１００、端末装置２００、暗号文管理サーバ３００、復号サーバ４００１〜４００ｎ、端末装置５００及びデータ用共通鍵暗号化装置６００を含む。
【００１７】
また、本実施形態に係る暗号システムは、公開鍵暗号方式における復号鍵を複数の分散鍵に分散し、当該分散鍵を有する複数の復号サーバ（復号サーバ４００１〜４００ｎ）が共同で処理を実行しなければ、平文mを復元できないようにした、いわゆる“しきい値暗号方式”（例えば、Pierre-Alain Fouque and David Pointcheval、“Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks”、ASIACRYPT 2001, pp.351-368、２００１年）にしたがった暗号システムである。しきい値暗号方式では、分散鍵を秘密の状態としつつ復号を実行することができる。
【００１８】
通信ネットワーク１０は、暗号システムに含まれる各サーバ及び端末装置を接続する通信ネットワークである。また、本実施形態では、端末装置２００及び端末装置５００は、無線基地局１１Ａ，１１Ｂとの間において無線通信を実行する無線通信端末装置である。なお、端末装置２００及び端末装置５００は、無線ではなく、有線によって通信ネットワーク１０に接続する端末装置であってもよい。
【００１９】
情報提供サーバ１００は、端末装置２００から端末装置５００に対して送信される情報（具体的には、平文m）の暗号化及び復号に必要な情報（以下、提供情報）、例えば、公開情報pkや分散鍵skなどを提供する。
【００２０】
端末装置２００は、本実施形態に係るしきい値暗号方式に基づいて、平文mを暗号化した補強暗号文Cを生成する。また、端末装置２００は、生成した補強暗号文Cを暗号文管理サーバ３００に送信する。なお、補強暗号文Cの生成方法については後述する。
【００２１】
暗号文管理サーバ３００は、端末装置２００から送信された補強暗号文Cを格納する。また、暗号文管理サーバ３００は、復号サーバ４００１〜４００ｎまたは端末装置５００からの要求に応じて、格納している補強暗号文Cを送信する。
【００２２】
復号サーバ４００１〜４００ｎは、暗号文管理サーバ３００から送信された補強暗号文Cの正当性を検証するとともに、補強暗号文Cを用いて、平文mの部分的な復号情報である部分復号情報δを生成する。また、復号サーバ４００１〜４００ｎは、生成した部分復号情報δを端末装置５００に送信する。
【００２３】
さらに、復号サーバ４００１〜４００ｎは、署名鍵Sgkを用いれば容易に構成できるが、署名鍵Sgkを用いなければ構成が困難な鍵関連データを抽出できるか否かを検証する機能を有する。本実施形態において、復号サーバ４００１〜４００ｎは、署名検証装置を構成する。
【００２４】
端末装置５００は、復号サーバ４００１〜４００ｎから送信された部分復号情報δを検証する。また、端末装置５００は、検証した部分復号情報δを用いて、平文mを復元する。
【００２５】
データ用共通鍵暗号化装置６００は、端末装置２００によって生成された署名情報vに基づいて生成されたデータ用共通鍵を用いて平文mが暗号化された補強暗号文Cを生成する。また、データ用共通鍵暗号化装置６００は、生成した補強暗号文Cを通信先（不図示）に送信する。本実施形態において、データ用共通鍵暗号化装置６００は、暗号化装置を構成する。
【００２６】
（暗号システムの機能ブロック構成）
次に、本実施形態に係る暗号システムの機能ブロック構成について説明する。なお、本実施形態では、位数qの群Gにおいて演算を実行するものとする。
【００２７】
また、本実施形態では、素数p（p-1はqを割り切る）に対して、Zp-1の部分群G（位数q）における利用方法を例として説明するが、楕円曲線上でも同様の演算を実行することができる。
【００２８】
さらに、群Gの生成元の一つをg1と定義する。また、特にただし書きがない場合、演算は、mod pにより実行されるものとする。
【００２９】
（１）情報提供サーバ１００
図２は、情報提供サーバ１００の機能ブロック構成図である。図２に示すように、情報提供サーバ１００は、提供情報生成部１０１、鍵データベース１０３及び送信部１０５を備える。
【００３０】
提供情報生成部１０１は、公開情報pkや分散鍵skなどを生成する。具体的には、提供情報生成部１０１は、定義域｛0, q-1｝の範囲内において、一様な確率で値を一つ選択し、選択した値（乱数x）を秘密情報xとする。
【００３１】
提供情報生成部１０１は、（１式）を用いて、公開鍵（h）を生成する。
【数１】
2008135869.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を生成する。
【数２】
2008135869.tif 000004
【数３】
2008135869.tif 000005
【００３５】
さらに、提供情報生成部１０１は、（４式）を用いて、複数（n個）の部分復号検証鍵share vk1,…, share vki,…, share vknを生成する。
【数４】
2008135869.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とする。
【００４６】
暗号文生成部２０７は、平文mを暗号化し、暗号文cを生成する。具体的には、暗号文生成部２０７は、（５式）及び（６式）を用いて演算を実行し、暗号文cを生成する。
【数５】
2008135869.tif 000007
【数６】
2008135869.tif 000008
【００４７】
ここで、Hは、ハッシュ関数（例えば、SHA-1）を示す。また、*は、排他的論理和を示す。
【００４８】
検証鍵生成部２０９は、乱数rを用いて、暗号文cの検証に用いられる検証鍵vkを生成する。具体的には、検証鍵生成部２０９は、（７式）を用いて検証鍵vkを生成する。
【数７】
2008135869.tif 000009
【００４９】
ここで、u1が検証鍵vkに相当する。
【００５０】
第１ハッシュ値生成部２１１は、少なくとも検証鍵vkをハッシュ関数H1（第１のハッシュ関数）に入力し、ハッシュ値hAを生成する。
【００５１】
具体的には、第１ハッシュ値生成部２１１は、（８式）を用いてハッシュ値hAを生成する。
【数８】
2008135869.tif 000010
【００５２】
ここで、g2がハッシュ値hAに相当する。
【００５３】
第２ハッシュ値生成部２１３は、少なくもハッシュ値hA及び暗号文cをハッシュ関数H2（第２のハッシュ関数）に入力し、ハッシュ値hBを生成する。
【００５４】
具体的には、第２ハッシュ値生成部２１３は、（９式）を用いてハッシュ値hBを生成する。
【数９】
2008135869.tif 000011
【００５５】
ここで、eがハッシュ値hBに相当する。また、第２ハッシュ値生成部２１３は、（１０式）〜（１２式）を用いて、w1、w2及びu2を演算する。
【数１０】
2008135869.tif 000012
【数１１】
2008135869.tif 000013
【数１２】
2008135869.tif 000014
【００５６】
署名情報生成部２１５は、乱数rを用いて、暗号文cに対応する署名情報vを生成する。具体的には、署名情報生成部２１５は、ハッシュ値hA、ハッシュ値hB及び署名鍵元データSを用いて署名情報vを生成する。
【数１３】
2008135869.tif 000015
【００５７】
本実施形態では、f及びu2が署名情報vに相当する。
【００５８】
また、署名情報生成部２１５は、暗号文cなどの生成に用いられるシードを生成する。なお、シードとは、任意の方法によって定められた数字列や文字列などである。本実施形態では、署名情報生成部２１５は、シードとして乱数rを生成する。具体的には、署名情報生成部２１５は、乱数生成部２０３と同様の方法によって、乱数rを生成する。
【００５９】
署名部２１７は、署名情報vを含む署名σを暗号文cに付加する。具体的には、署名部２１７は、署名σを（e，u2, f）として、暗号文cに付加する。
【００６０】
さらに、署名部２１７は、暗号文cに署名σが付加された補強暗号文Cを出力する。なお、補強暗号文Cは、（１４式）に示すような構成を有する。
【数１４】
2008135869.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に対応する署名情報vを取得する。本実施形態において、受信部４０１は、取得部を構成する。
【００７５】
検証部４０３は、補強暗号文Cに含まれる暗号文cが正当であることを検証する。具体的には、検証部４０３は、ハッシュ関数H1と、ハッシュ関数H2と、ハッシュ値hA及びハッシュ値hBを用いて生成され暗号文c（署名対象データ）に付加されている署名σとを用いて暗号文cが正当であることを検証する。
【００７６】
より具体的には、検証部４０３は、（１５式）を用いてg2を求める。
【数１５】
2008135869.tif 000017
【００７７】
さらに、検証部４０３は、（１６式）を用いて当該演算が成立するか否かを判定する。検証部４０３は、当該演算が成立する場合、暗号文cが正当であると判定する。
【数１６】
2008135869.tif 000018
【００７８】
すなわち、検証部４０３は、ハッシュ関数H1と、ハッシュ関数H2と、ハッシュ値hA及びハッシュ値hBを用いて生成され暗号文cに付加されている署名σと、u1（検証鍵vk）とを用いて、暗号文cが正当であることを検証する。
【００７９】
また、検証部４０３は、部分復号情報δが正当であることを検証することができる。検証部４０３は、部分復号情報δが正当であることを証明する正当性証明情報pfを端末装置５００に送信することができる。
【００８０】
さらに、検証部４０３は、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、暗号文cと、暗号文cの検証に用いられる検証鍵vkとを用いて、署名鍵Sgkを用いれば容易に構成できるが、署名鍵Sgkを用いなければ構成が困難な鍵関連データzを抽出できるか否かを検証することができる。
【００８１】
具体的には、検証部４０３は、（１６式）が成立するかによって、鍵関連データzを抽出できるか否かを検証する。
【００８２】
部分復号情報生成部４０５は、部分復号情報δを生成する。具体的には、部分復号情報生成部４０５は、検証部４０３によって暗号文cが正当であることが検証されたことに応じて、暗号文cを復号する。具体的には、部分復号情報生成部４０５は、（１７式）を用いて部分復号情報δ（δi）を生成する。
【数１７】
2008135869.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を復元する。
【数１８】
2008135869.tif 000020
【数１９】
2008135869.tif 000021
【００９１】
送信部５０７は、補強暗号文Cの送信要求を暗号文管理サーバ３００に送信する。また、送信部５０７は、補強暗号文Cの復号要求を復号サーバ４００１〜４００ｎに送信する。
【００９２】
出力部５０９は、平文復元部５０５によって復元された平文mを出力、例えば、表示部（不図示）に表示したり、文書ファイルとして生成したりすることができる。
【００９３】
記憶部５１１は、ハッシュ関数H1及びハッシュ関数H2を記憶する。なお、本実施形態では、記憶部５１１にハッシュ関数H1及びハッシュ関数H2に記憶されているが、ハッシュ関数H1及びハッシュ関数H2は、必要なときに、通信ネットワーク１０などを介して外部から取得してもよい。
【００９４】
（６）データ用共通鍵暗号化装置
図７は、データ用共通鍵暗号化装置６００の機能ブロック構成図である。図７に示すように、データ用共通鍵暗号化装置６００は、受信部６０１、暗号文生成部６０３、暗号データ出力部６０５、補強暗号文出力部６０７、検証鍵出力部６０９及び送信部６１１を備える。
【００９５】
受信部６０１は、他の装置（不図示）から暗号化される平文m（暗号化対象データ）などを受信する。
【００９６】
暗号文生成部６０３は、平文mを暗号化し、暗号文cを生成する。具体的には、暗号文生成部６０３は、暗号文生成部２０７と同様に、（５式）及び（６式）を用いて演算を実行し、暗号文cを生成する。
【００９７】
暗号データ出力部６０５は、署名鍵Sgkの元となる署名鍵元データSを生成し、暗号化対象データ（平文m）の暗号化に用いられるデータ用共通鍵kを暗号化した暗号データhを出力する。具体的には、暗号データ出力部６０５は、（５式）〜（１４式）の演算を実行する。なお、本実施形態では、署名鍵Sgkと署名鍵元データSとは、同一である。
【００９８】
補強暗号文出力部６０７は、暗号文c（署名対象データ）、暗号文cに対応する署名情報v及び暗号データhを含む補強暗号文Cを出力する。具体的には、補強暗号文出力部６０７は、（１４式）によって補強暗号文Cを出力する。
【００９９】
なお、署名情報vは、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、暗号文cと、暗号文cの検証に用いられる検証鍵vkとを用いて、署名鍵Sgkを用いれば容易に構成できるが署名鍵Sgkを用いなければ構成が困難な鍵関連データzを抽出できるように構成される。
【０１００】
検証鍵出力部６０９は、少なくとも暗号データhを入力として暗号文c（署名対象データ）、及び暗号文cの検証に用いられる検証鍵vkを出力する。なお、検証鍵出力部６０９は、暗号データh自体を検証鍵vkとして出力してもよい。
【０１０１】
送信部６１１は、補強暗号文出力部６０７が出力した補強暗号文Cを通信先（不図示）に送信する。
【０１０２】
（暗号システムの動作）
次に、上述した暗号システムの動作について説明する。具体的には、（１）鍵生成処理、（２）暗号化処理、（３）復号及び復元処理、及び（４）データ用共通鍵を用いた補強暗号文Cの生成及び送信処理の内容について説明する。
【０１０３】
（１）鍵生成処理
図８は、暗号システムの全体概略シーケンス図である。まず、鍵生成処理について説明する。図８に示すように、ステップＳ１０において、情報提供サーバ１００は、暗号システムを構成する他の装置に提供される提供情報を生成する。
【０１０４】
具体的には、情報提供サーバ１００は、公開情報pk（公開鍵）、分散鍵sk1,…, ski,…, skn及び部分復号検証鍵share vk1,…, share vki,…, share vknを生成する。
【０１０５】
ステップＳ２０において、情報提供サーバ１００は、生成した公開情報pkを端末装置２００、暗号文管理サーバ３００、復号サーバ４００１〜４００ｎ及び端末装置５００にそれぞれ送信する。
【０１０６】
ステップＳ３０において、情報提供サーバ１００は、生成した分散鍵sk1,…, ski,…, sknを復号サーバ４００１〜４００ｎに送信する。例えば、情報提供サーバ１００は、分散鍵sk1を復号サーバ４００１に送信する。
【０１０７】
ステップＳ４０において、情報提供サーバ１００は、生成した部分復号検証鍵share vk1,…, share vki,…, share vknを端末装置５００に送信する。
【０１０８】
（２）暗号化処理
次に、暗号化処理について説明する。図８に示すように、ステップＳ１００において、端末装置２００は、平文mの暗号化処理を実行する。具体的には、端末装置２００は、図９に示す暗号化処理フローにしたがって、平文mの暗号化処理を実行する。
【０１０９】
図９に示すように、ステップＳ１０１において、端末装置２００は、署名鍵元データSを選択する。
【０１１０】
ステップＳ１０３において、端末装置２００は、（５式）を用いて、べき乗演算を実行する。
【０１１１】
ステップＳ１０５において、端末装置２００は、（７式）を用いた演算を実行し、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を出力する。
【０１３２】
さらに、復号サーバ４００１〜４００ｎは、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合、暗号文cと、暗号文cの検証に用いられる検証鍵vkとを用いて、署名鍵Sgkを用いれば容易に構成できるが、署名鍵Sgkを用いなければ構成が困難な鍵関連データzを抽出できるか否かを検証することができる。具体的には、復号サーバ４００１〜４００ｎは、（１６式）が成立するかによって、鍵関連データzを抽出できるか否かを検証する。
【０１３３】
次いで、図８に示すように、ステップＳ２８０において、復号サーバ４００１〜４００ｎは、部分復号情報δ（δ1〜δn）を生成する。具体的には、復号サーバ４００１〜４００ｎのそれぞれは、（１７式）を用いて部分復号情報δを生成する。
【０１３４】
ステップＳ２９０において、復号サーバ４００１〜４００ｎは、生成した部分復号情報δ（δ1〜δn）を端末装置５００に送信する。
【０１３５】
ステップＳ３００において、端末装置５００は、受信した部分復号情報δ（δ1〜δn）の正当性を検証する。具体的には、端末装置５００は、（１８式）を用いて演算を実行し、部分復号検証鍵share vk1,…, share vki,…, share vknのそれぞれと、それらの生成元νと、正当性証明情報pfとを用いて、複数の部分復号情報δ1〜δnのそれぞれを検証する。
【０１３６】
ステップＳ３１０において、端末装置５００は、部分復号情報δ（δ1〜δn）を結合し、（１９式）を用いて平文mを復元する。
【０１３７】
（４）データ用共通鍵を用いた補強暗号文Cの生成及び送信処理
図１１は、データ用共通鍵を用いた補強暗号文Cの生成及び送信処理フローを示す。図１１に示すように、ステップＳ４１０において、データ用共通鍵暗号化装置６００は、署名鍵元データSを生成するとともに、生成した署名鍵元データSを用いて暗号データhを生成する。具体的には、データ用共通鍵暗号化装置６００は、（５式）〜（１４式）の演算を実行する。
【０１３８】
ステップＳ４２０において、データ用共通鍵暗号化装置６００は、暗号文c、暗号文cに対応する署名情報v及び暗号データhを含む補強暗号文Cを出力する。具体的には、データ用共通鍵暗号化装置６００は、（１４式）によって補強暗号文Cを出力する。
【０１３９】
ステップＳ４３０において、データ用共通鍵暗号化装置６００は、補強暗号文Cを通信先（不図示）に送信する。
【０１４０】
（変更例１）
上述した本発明の実施形態では、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により実行されるものとする。
【数２０】
2008135869.tif 000022
【０１４３】
まず、（２１式）による演算を実行する。次いで、乱数rj(j = 1, 2, . . .,Λ2)、（２２式）及び（２３式）を用いて、コミット値CTを演算する。
【数２１】
2008135869.tif 000023
【数２２】
2008135869.tif 000024
【数２３】
2008135869.tif 000025
【０１４４】
次に、（２４式）を用いて、チャレンジctを得る。
【数２４】
2008135869.tif 000026
【０１４５】
さらに、（２５式）を用いて、レスポンスRを返す。また、暗号文は、（２６式）に示すような構成となる。
【数２５】
2008135869.tif 000027
【数２６】
2008135869.tif 000028
【０１４６】
検証は以下のように実行する。まず、（２７式）による演算を実行する。
【数２７】
2008135869.tif 000029
【０１４７】
次に、（２８式）が成立するか否かを判定する。なお、sの抽出は、Hの監視により可能となることにより安全性の証明を実行する。
【数２８】
2008135869.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」において紹介されている方法を用いることができる。
【０１４９】
（変更例２）
上述した実施形態では、（１６式）が成立するか否かによって鍵関連データzを抽出できるか否かを検証したが、鍵関連データzを抽出できるか否かの検証は、以下のように変更することができる。すなわち、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合において、出力g2（式８参照）をhaと決めてもよい。ここで、aは、ランダムに選択され、第１ハッシュ値生成部２１１に記憶される。
【０１５０】
この場合、（１１式）において、u2を1/a乗することによって得られるhSを鍵関連データzとして用いる。
【０１５１】
（変更例３）
上述した実施形態では、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合を所定の条件としたが、所定の条件は、以下のように変更することができる。すなわち、ランダムオラクルの存在を仮定した場合に代えて、暗号システムにおいて用いられる少なくとも一部のシステムパラメータparamsの一部、例えば、g2を任意に決定できる場合とすることができる。
【０１５２】
この場合、（８式）及び（１５式）は用いられず、g2が固定値となる。具体的には、g2は、haと決められる。また、（９式）及び（１６式）において、ハッシュ関数H2への入力にu1が追加される。
【０１５３】
また、この場合、上述した変更例２と同様に、（１１式）において、u2を1/a乗することによって得られるhSを鍵関連データとして用いる。
【０１５４】
（変更例４）
上述した実施形態では、他の出力と無相関な関数であるランダムオラクルの存在を仮定した場合を所定の条件としたが、所定の条件は、さらに以下のように変更することができる。すなわち、ランダムオラクルの存在を仮定した場合に代えて、署名情報vの生成に用いられるハッシュ関数H（２０式及び２２式参照）への入力値、及び当該入力値に対応するハッシュ関数Hからの出力値を取得できる場合とすることができる。
【０１５５】
この場合、（２２式）において、C0j及びC1jに入力されるhと、rejとを共通とする。hと、rejとを共通とすると、rj及びRjSが得られる。RjSをrjで除算することによって得られるSを鍵関連データとして用いる。
【０１５６】
（作用・効果）
以上説明した本実施形態に係る暗号システムによれば、所定の条件の下（例えば、ランダムオラクルの存在を仮定した場合）、暗号文c（署名対象データ）と、暗号文cの検証に用いられる検証鍵vkとを用いて、署名鍵Sgkを用いれば容易に構成できるが署名鍵Sgkを用いなければ構成が困難な鍵関連データzを抽出できるか否かが検証される。このため、選択暗号文攻撃における安全性の証明において、鍵関連データzの抽出を何度も行ってもすべての鍵関連データzを抽出できる確率が小さくなることを回避しつつ、暗号文cの安全性を検証することができる。
【０１５７】
上述した非特許文献１において開示されている方法では、署名データから電子署名に用いられる署名鍵Sgkに関連する鍵関連データzを略１の確率で抽出できるという実際とは異なる仮定を用いている。しかしながら、このような仮定を満たすことは現実的には不可能である。つまり、実際には、有り得ない仮定の下で暗号方式の安全性を証明しているため、真に当該暗号方式の安全性を証明していることにはならない。
【０１５８】
本実施形態では、所定の条件の下（例えば、ランダムオラクルの存在を仮定した場合）、鍵関連データzを略１の確率で抽出できる（つまり、無視できる程度の確率でしか抽出が失敗しない）署名データを用いているため、鍵関連データの抽出が何度も行われても、すべての鍵関連データを抽出できる確率が小さくならないのである。つまり、鍵関連データの抽出が何度も行われる場合でも暗号方式の安全性を示すことができる。
【０１５９】
また、本実施形態では、署名データを他のプロトコル（暗号化、認証または二重に署名を行う場合）と併用しても鍵関連データzを略１の確率で抽出できる。このため、暗号方式の安全性を確実に示しつつ、多様な要求に柔軟に対応することができる。
【０１６０】
さらに、本実施形態では、署名データから鍵関連データzを略１の確率で抽出できる。一般的に、署名データから鍵関連データzを略１の確率で抽出できる署名は、署名データから鍵データ、つまり、署名鍵Sgkを略１の確率で抽出できる署名よりも、構成が簡単になる。構成が簡単になれば、署名に関する演算量や署名データのサイズを抑制することができる。
【０１６１】
（その他の実施形態）
上述したように、本発明の一実施形態を通じて本発明の内容を開示したが、この開示の一部をなす論述及び図面は、本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態が明らかとなろう。
【０１６２】
例えば、上述した本発明の実施形態では、端末装置２００は、無線通信端末装置としたが、端末装置２００は、携帯情報端末（ＰＤＡ）やＩＣカードであってもよい。
【０１６３】
上述した本発明の実施形態では、暗号文管理サーバ３００を介して補強暗号文Cを送受信する形態としたが、端末装置２００は、暗号文管理サーバ３００を用いずに、復号サーバ４００１〜４００ｎに直接補強暗号文Cを送信するようにしてもよい。さらに、復号サーバ４００１〜４００ｎが端末装置５００の機能を兼ね備え、平文mを復元するようにしてもよい。
【０１６４】
また、端末装置２００の機能及び端末装置５００の機能を１台の端末装置に具備してもよい。或いは、端末装置２００の機能及びデータ用共通鍵暗号化装置６００の機能を１台の端末装置に具備してもよい。さらに、上述した暗号システムを構成する各装置の機能は、コンピュータや通信端末装置において実行可能なプログラムとしても提供することもできる。
【０１６５】
上述した本発明の実施形態では、乱数rを用いて暗号化された暗号文cを署名対象データとしていて、かつ乱数rをシードとして用いているが、暗号化されていない署名対象データに署名σを付加してもよい。
【０１６６】
このように、本発明は、ここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は、上述の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１６７】
【図１】本発明の実施形態に係る暗号システムの全体概略構成図である。
【図２】本発明の実施形態に係る情報提供サーバの機能ブロック構成図である。
【図３】本発明の実施形態に係る端末装置（暗号化側）の機能ブロック構成図である。
【図４】本発明の実施形態に係る暗号文管理サーバの機能ブロック構成図である。
【図５】本発明の実施形態に係る復号サーバの機能ブロック構成図である。
【図６】本発明の実施形態に係る端末装置（復元側）の機能ブロック構成図である。
【図７】本発明の実施形態に係る暗号化装置の機能ブロック構成図である。
【図８】本発明の実施形態に係る暗号システムの全体概略シーケンス図である。
【図９】本発明の実施形態に係る端末装置（暗号化側）における暗号化処理フローである。
【図１０】本発明の実施形態に係る復号サーバにおける正当性検証処理と復号処理のフローである。
【図１１】本発明の実施形態に係る暗号化装置におけるデータ用共通鍵を用いた補強暗号文の生成及び送信処理フローである。
【符号の説明】
【０１６８】
１０…通信ネットワーク、１１Ａ，１１Ｂ…無線基地局、１００…情報提供サーバ、１０１…提供情報生成部、１０３…鍵データベース、１０５…送信部、２００…端末装置、２０１…受信部、２０５…乱数生成部、２０７…暗号文生成部、２０９…検証鍵生成部、２１１…第１ハッシュ値生成部、２１３…第２ハッシュ値生成部、２１５…署名情報生成部、２１７…署名部、２１９…送信部、３００…暗号文管理サーバ、３０１…受信部、３０３…暗号文管理部、３０５…暗号文データベース、３０７…送信部、４００１〜４００ｎ…復号サーバ、４０１…受信部、４０３…検証部、４０５…部分復号情報生成部、４０７…送信部、４０９…記憶部、５００…端末装置、５０１…受信部、５０３…検証部、５０５…平文復元部、５０７…送信部、５０９…出力部、５１１…記憶部、６００…データ用共通鍵暗号化装置、６０１…受信部、６０３…暗号文生成部、６０５…暗号データ出力部、６０７…補強暗号文出力部、６０９…検証鍵出力部、６１１…送信部
【図１】
2008135869.tif 000031
【図２】
2008135869.tif 000032
【図３】
2008135869.tif 000033
【図４】
2008135869.tif 000034
【図５】
2008135869.tif 000035
【図６】
2008135869.tif 000036
【図７】
2008135869.tif 000037
【図８】
2008135869.tif 000038
【図９】
2008135869.tif 000039
【図１０】
2008135869.tif 000040
【図１１】
2008135869.tif 000041