"システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、前記システムパラメータ生成装置は、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、前記巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Groth-Sahai証明の送信装置用パラメータ、受信装置用パラメータを生成し、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記生成元から設定した第1係数群から共通参照情報crsを生成するシステムパラメータ生成部と、前記共通参照情報crsを送信装置と受信装置に送信するcrs送信部とを備え、前記送信装置は、文書m1,...,mNNは2以上の正の整数と、前記共通参照情報crsとを入力とし、Waters双対署名の第1鍵対、第2鍵対を生成し、Boneh-Boyen署名の第3鍵対を生成し、秘密鍵を生成し、前記第1鍵対、前記第2鍵対、前記第3鍵対を用いて公開鍵を生成し、Waters双対署名の第1署名、第2署名を生成し、Boneh-Boyen署名の第3署名を生成し、前記文書m1,...,mN、前記第1鍵対に含まれる値、前記第2鍵対に含まれる値、前記共通参照情報crs、前記第1署名、前記第2署名、前記第3署名を用いて、暗号文C1,...,CNを生成し、前記公開鍵と、前記暗号文C1,...,CNとから暗号化データベースを生成する暗号化データベース生成部と、前記暗号化データベースを前記受信装置に送信するT送信部と、前記暗号化データベースと、前記秘密鍵とを記憶するT記憶部と、前記共通参照情報crs、前記暗号化データベース、前記秘密鍵、要求Qを入力とし、知識識別不可能証明を検証し、前記知識識別不可能証明が正しい場合に、前記秘密鍵、前記要求Qを用いてブラインド復号を実行し、前記暗号化データベース、前記共通参照情報crs、前記要求Qを用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成し、前記非対話ゼロ知識証明を含む返信Rを生成する返信生成部と、前記返信Rを前記受信装置に送信するR送信部と、を備え、前記受信装置は、前記暗号化データベースと、前記共通参照情報crsと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名を検証し、前記署名が正しい場合に、前記インデックスξに対応する暗号文Cξ、前記共通参照情報crsを用いて再ランダム化を実行し、前記暗号文Cξ、前記共通参照情報crs、前記公開鍵を用いて、Groth-Sahai証明の知識識別不可能証明を生成し、前記知識識別不可能証明を含む要求Q、と、前記要求Qおよびインデックスξを含むQprivを生成する要求生成部と、前記要求Qを前記送信装置に送信するQ送信部と、前記要求QとQprivとを記憶するQ記憶部と、前記返信Rと、前記Qprivと、前記暗号化データベースと、前記共通参照情報crsとを入力とし、前記非対話ゼロ知識証明を検証し、前記非対話ゼロ知識証明が正しい場合に、前記Qpriv、前記暗号文C1,...,CN、共通参照情報crsを用いて、前記暗号文Cξから文書mξを計算して出力する文書取得部と、を備えることを特徴とする紛失通信システム。システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、前記システムパラメータ生成装置はシステムパラメータ生成部と、crs送信部とを備え、前記システムパラメータ生成部は、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、当該巡回乗法群の生成元と、双線形写像とを組み合わせて双線形写像パラメータを生成する双線形写像パラメータ生成手段と、前記双線形写像パラメータを入力とし、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して送信装置用パラメータを生成する送信装置用パラメータ生成手段と、前記双線形写像パラメータを入力とし、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して受信装置用パラメータを生成する受信装置用パラメータ生成手段と、前記生成元から第1係数群を設定する第1係数設定手段と、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記第1係数群から共通参照情報crsを生成するシステムパラメータ生成手段と、を備え、前記crs送信部は、前記共通参照情報crsを送信装置と受信装置に送信し、前記送信装置は暗号化データベース生成部と、T送信部と、T記憶部と、返信生成部と、R送信部と、を備え、前記暗号化データベース生成部は、前記双線形写像パラメータを入力とし、Waters双対署名の鍵生成アルゴリズムを実行してWaters双対署名の第1鍵対を生成する第1Waters鍵対生成手段と、前記双線形写像パラメータを入力とし、Waters双対署名の鍵生成アルゴリズムを実行してWaters双対署名の第2鍵対を生成する第2Waters鍵対生成手段と、前記双線形写像パラメータと秘密鍵生成手段が設定した係数とを入力とし、Boneh-Boyen署名の鍵生成アルゴリズムを実行してBoneh-Boyen署名の第3鍵対を生成するBB鍵対生成手段と、秘密鍵を生成し、前記第1係数群を用いて係数を設定する秘密鍵生成手段と、前記秘密鍵生成手段が設定した係数、前記第1鍵対、前記第2鍵対、前記第3鍵対を用いて公開鍵を生成する公開鍵生成手段と、前記秘密鍵生成手段が設定した係数を用いて第2係数群を設定する第2係数設定手段と、前記第2係数群を入力とし、Waters双対署名の署名生成アルゴリズムを実行して第1署名を生成する第1Waters署名生成手段と、前記第2係数群を入力とし、Waters双対署名の署名生成アルゴリズムを実行して第2署名を生成する第2Waters署名生成手段と、前記第2係数群を入力とし、Boneh-Boyen署名の署名生成アルゴリズムを実行して第3署名を生成するBB署名生成手段と、文書m1,...,mNNは2以上の正の整数と、前記第1鍵対に含まれる値、前記第2鍵対に含まれる値、前記第1係数群、前記第2係数群、前記第1署名、前記第2署名、前記第3署名を入力とし、暗号文C1,...,CNを生成する暗号文生成手段と、前記公開鍵と、前記暗号文C1,...,CNとを入力とし、暗号化データベースを生成する暗号化データベース生成手段と、を備え、前記T送信部は、前記暗号化データベースを前記受信装置に送信し、前記T記憶部は、前記暗号化データベースと、前記秘密鍵とを記憶し、前記返信生成部は、Groth-Sahai証明の知識識別不可能証明と、前記受信装置用パラメータとを入力とし、Groth-Sahai証明の証明検証アルゴリズムを実行して、前記知識識別不可能証明を検証する知識識別不可能証明検証手段と、前記知識識別不可能証明が正しい場合に、前記秘密鍵と、再ランダム化手段が設定した係数とを入力とし、係数を設定するブラインド復号手段と、前記ブラインド復号手段が設定した係数、前記公開鍵、前記再ランダム化手段が設定した係数、前記第1係数群、前記共通参照情報crsを入力とし、Groth-Sahai証明の非対話ゼロ知識証明生成アルゴリズムを実行して、非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成手段と、前記ブラインド復号手段が設定した係数と、前記非対話ゼロ知識証明とを組にして返信Rを生成する返信生成手段と、を備え、前記R送信部は、前記返信Rを前記受信装置に送信し、前記受信装置は要求生成部と、Q送信部と、Q記憶部と、文書取得部と、を備え、前記要求生成部は、前記暗号文C1,...,CNと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名をWaters双対署名の署名検証アルゴリズムおよび、Boneh-Boyen署名の署名検証アルゴリズムを実行して検証し、前記暗号文C1,...,CNに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Cξを出力する署名検証手段と、前記暗号文Cξと、前記第1係数群とを入力とし、係数を設定する再ランダム化手段と、前記再ランダム化手段が設定した係数と、前記暗号文Cξと、前記双線形写像と、前記公開鍵と、前記第一係数群と、前記受信装置用パラメータとを入力とし、Groth-Sahai証明の知識識別不可能証明を生成する知識識別不可能証明生成手段と、前記再ランダム化手段が設定した係数と、前記知識識別不可能証明と、前記インデックスξとを入力とし、要求Q、Qprivを生成する要求生成手段と、を備え、前記Q送信部は、前記要求Qを前記送信装置に送信し、前記Q記憶部は、前記要求QとQprivとを記憶し、前記文書取得部は、前記返信Rと、前記送信装置用パラメータとを入力とし、Groth-Sahai証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証するゼロ知識証明検証手段と、前記非対話ゼロ知識証明が正しい場合に、前記Qprivと、前記第1係数群と、前記暗号文C1,...,CNと、前記ブラインド復号手段が生成した係数とを入力とし、前記暗号文Cξから文書mξを計算して出力する文書生成手段と、を備えることを特徴とする紛失通信システム。システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、前記システムパラメータ生成装置はシステムパラメータ生成部と、crs送信部とを備え、前記システムパラメータ生成部は、入力1λに対して、λビットの素数p、素数位数pの巡回乗法群であるGおよびGT、双線形写像e、群Gの生成元gよりなる双線形写像パラメータΓ:=p,G,GT,e,gを生成する双線形写像パラメータ生成手段と、共通参照情報crs:=Γ、GSS、GSR、g1、g2、ζを生成するシステムパラメータ生成手段と、を備え、前記crs送信部は、前記共通参照情報crsを送信装置と受信装置に送信し、前記送信装置は暗号化データベース生成部と、T送信部と、T記憶部と、返信生成部と、R送信部と、を備え、前記暗号化データベース生成部は、前記公開鍵pkと、前記暗号文C1,...,CNとを入力とし、暗号化データベースT:=pk,C1,...,CNを生成する暗号化データベース生成手段と、を備え、前記T送信部は、前記暗号化データベースTを前記受信装置に送信し、前記T記憶部は、前記暗号化データベースTと、前記秘密鍵sk:=x1、x2とを記憶し、前記返信生成部はGroth-Sahai証明の知識識別不可能証明πと、前記パラメータGSRとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、前記知識識別不可能証明πを検証する知識識別不可能証明検証手段と、前記R送信部は、前記返信Rを前記受信装置に送信し、前記受信装置は要求生成部と、Q送信部と、Q記憶部と、文書取得部と、を備え、前記要求生成部は、前記暗号文C1,...,CNと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名をWaters双対署名の署名検証アルゴリズムW.Vrfyおよび、Boneh-Boyen署名の署名検証アルゴリズムBB.Vrfyを実行して検証し、前記暗号文C1,...,CNに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Cξを出力する署名検証手段と、前記Q送信部は、前記要求Qを前記送信装置に送信し、前記Q記憶部は、前記要求QとQprivとを記憶し、前記文書取得部は、前記返信Rと、前記パラメータGSSとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、前記非対話ゼロ知識証明δを検証するゼロ知識証明検証手段と、を特徴とする紛失通信システム。システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、前記システムパラメータ生成装置は、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、前記巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Groth-Sahai証明の送信装置用パラメータ、受信装置用パラメータを生成し、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記生成元から設定した第1係数群から共通参照情報crsを生成するシステムパラメータ生成ステップと、前記共通参照情報crsを送信装置と受信装置に送信するcrs送信ステップとを実行し、前記送信装置は、文書m1,...,mNNは2以上の正の整数と、前記共通参照情報crsとを入力とし、Waters双対署名の第1鍵対、第2鍵対を生成し、Boneh-Boyen署名の第3鍵対を生成し、秘密鍵を生成し、前記第1鍵対、前記第2鍵対、前記第3鍵対を用いて公開鍵を生成し、Waters双対署名の第1署名、第2署名を生成し、Boneh-Boyen署名の第3署名を生成し、前記文書m1,...,mN、前記第1鍵対に含まれる値、前記第2鍵対に含まれる値、前記共通参照情報crs、前記第1署名、前記第2署名、前記第3署名を用いて、暗号文C1,...,CNを生成し、前記公開鍵と、前記暗号文C1,...,CNとから暗号化データベースを生成する暗号化データベース生成ステップと、前記暗号化データベースを前記受信装置に送信するT送信ステップと、前記暗号化データベースと、前記秘密鍵とを記憶するT記憶ステップと、前記共通参照情報crs、前記暗号化データベース、前記秘密鍵、要求Qを入力とし、知識識別不可能証明を検証し、前記知識識別不可能証明が正しい場合に、前記秘密鍵、前記要求Qを用いてブラインド復号を実行し、前記暗号化データベース、前記共通参照情報crs、前記要求Qを用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成し、前記非対話ゼロ知識証明を含む返信Rを生成する返信生成ステップと、前記返信Rを前記受信装置に送信するR送信ステップと、を実行し、前記受信装置は、前記暗号化データベースと、前記共通参照情報crsと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名を検証し、前記署名が正しい場合に、前記インデックスξに対応する暗号文Cξ、前記共通参照情報crsを用いて再ランダム化を実行し、前記暗号文Cξ、前記共通参照情報crs、前記公開鍵を用いて、Groth-Sahai証明の知識識別不可能証明を生成し、前記知識識別不可能証明を含む要求Q、と、前記要求Qおよびインデックスξを含むQprivを生成する要求生成ステップと、前記要求Qを前記送信装置に送信するQ送信ステップと、前記要求QとQprivとを記憶するQ記憶ステップと、前記返信Rと、前記Qprivと、前記暗号化データベースと、前記共通参照情報crsとを入力とし、前記非対話ゼロ知識証明を検証し、前記非対話ゼロ知識証明が正しい場合に、前記Qpriv、前記暗号文C1,...,CN、共通参照情報crsを用いて、前記暗号文Cξから文書mξを計算して出力する文書取得ステップと、を実行することを特徴とする紛失通信方法。システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、前記システムパラメータ生成装置はシステムパラメータ生成ステップと、crs送信ステップとを実行し、前記システムパラメータ生成ステップは、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、当該巡回乗法群の生成元と、双線形写像とを組み合わせて双線形写像パラメータを生成する双線形写像パラメータ生成サブステップと、前記双線形写像パラメータを入力とし、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して送信装置用パラメータを生成する送信装置用パラメータ生成サブステップと、前記双線形写像パラメータを入力とし、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して受信装置用パラメータを生成する受信装置用パラメータ生成サブステップと、前記生成元から第1係数群を設定する第1係数設定サブステップと、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記第1係数群から共通参照情報crsを生成するシステムパラメータ生成サブステップと、を有し、前記crs送信ステップは、前記共通参照情報crsを送信装置と受信装置に送信し、前記送信装置は暗号化データベース生成ステップと、T送信ステップと、T記憶ステップと、返信生成ステップと、R送信ステップと、を実行し、前記暗号化データベース生成ステップは、前記双線形写像パラメータを入力とし、Waters双対署名の鍵生成アルゴリズムを実行してWaters双対署名の第1鍵対を生成する第1Waters鍵対生成サブステップと、前記双線形写像パラメータを入力とし、Waters双対署名の鍵生成アルゴリズムを実行してWaters双対署名の第2鍵対を生成する第2Waters鍵対生成サブステップと、前記双線形写像パラメータと秘密鍵生成サブステップが設定した係数とを入力とし、Boneh-Boyen署名の鍵生成アルゴリズムを実行してBoneh-Boyen署名の第3鍵対を生成するBB鍵対生成サブステップと、秘密鍵を生成し、前記第1係数群を用いて係数を設定する秘密鍵生成サブステップと、前記秘密鍵生成サブステップが設定した係数、前記第1鍵対、前記第2鍵対、前記第3鍵対を用いて公開鍵を生成する公開鍵生成サブステップと、前記秘密鍵生成サブステップが設定した係数を用いて第2係数群を設定する第2係数設定サブステップと、前記第2係数群を入力とし、Waters双対署名の署名生成アルゴリズムを実行して第1署名を生成する第1Waters署名生成サブステップと、前記第2係数群を入力とし、Waters双対署名の署名生成アルゴリズムを実行して第2署名を生成する第2Waters署名生成サブステップと、前記第2係数群を入力とし、Boneh-Boyen署名の署名生成アルゴリズムを実行して第3署名を生成するBB署名生成サブステップと、文書m1,...,mNNは2以上の正の整数と、前記第1鍵対に含まれる値、前記第2鍵対に含まれる値、前記第1係数群、前記第2係数群、前記第1署名、前記第2署名、前記第3署名を入力とし、暗号文C1,...,CNを生成する暗号文生成サブステップと、前記公開鍵と、前記暗号文C1,...,CNとを入力とし、暗号化データベースを生成する暗号化データベース生成サブステップと、を有し、前記T送信ステップは、前記暗号化データベースを前記受信装置に送信し、前記T記憶ステップは、前記暗号化データベースと、前記秘密鍵とを記憶し、前記返信生成ステップは、Groth-Sahai証明の知識識別不可能証明と、前記受信装置用パラメータとを入力とし、Groth-Sahai証明の証明検証アルゴリズムを実行して、前記知識識別不可能証明を検証する知識識別不可能証明検証サブステップと、前記知識識別不可能証明が正しい場合に、前記秘密鍵と、再ランダム化サブステップが設定した係数とを入力とし、係数を設定するブラインド復号サブステップと、前記ブラインド復号サブステップが設定した係数、前記公開鍵、前記再ランダム化サブステップが設定した係数、前記第1係数群、前記共通参照情報crsを入力とし、Groth-Sahai証明の非対話ゼロ知識証明生成アルゴリズムを実行して、非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成サブステップと、前記ブラインド復号サブステップが設定した係数と、前記非対話ゼロ知識証明とを組にして返信Rを生成する返信生成サブステップと、を有し、前記R送信ステップは、前記返信Rを前記受信装置に送信し、前記受信装置は要求生成ステップと、Q送信ステップと、Q記憶ステップと、文書取得ステップと、を実行し、前記要求生成ステップは、前記暗号文C1,...,CNと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名をWaters双対署名の署名検証アルゴリズムおよび、Boneh-Boyen署名の署名検証アルゴリズムを実行して検証し、前記暗号文C1,...,CNに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Cξを出力する署名検証サブステップと、前記暗号文Cξと、前記第1係数群とを入力とし、係数を設定する再ランダム化サブステップと、前記再ランダム化サブステップが設定した係数と、前記暗号文Cξと、前記双線形写像と、前記公開鍵と、前記第一係数群と、前記受信装置用パラメータとを入力とし、Groth-Sahai証明の知識識別不可能証明を生成する知識識別不可能証明生成サブステップと、前記再ランダム化サブステップが設定した係数と、前記知識識別不可能証明と、前記インデックスξとを入力とし、要求Q、Qprivを生成する要求生成サブステップと、を有し、前記Q送信ステップは、前記要求Qを前記送信装置に送信し、前記Q記憶ステップは、前記要求QとQprivとを記憶し、前記文書取得ステップは、前記返信Rと、前記送信装置用パラメータとを入力とし、Groth-Sahai証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証するゼロ知識証明検証サブステップと、前記非対話ゼロ知識証明が正しい場合に、前記Qprivと、前記第1係数群と、前記暗号文C1,...,CNと、前記ブラインド復号サブステップが生成した係数とを入力とし、前記暗号文Cξから文書mξを計算して出力する文書生成サブステップと、を有することを特徴とする紛失通信方法。システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、前記システムパラメータ生成装置はシステムパラメータ生成ステップと、crs送信ステップとを実行し、前記システムパラメータ生成ステップは、入力1λに対して、λビットの素数p、素数位数pの巡回乗法群であるGおよびGT、双線形写像e、群Gの生成元gよりなる双線形写像パラメータΓ:=p,G,GT,e,gを生成する双線形写像パラメータ生成サブステップと、共通参照情報crs:=Γ、GSS、GSR、g1、g2、ζを生成するシステムパラメータ生成サブステップと、を有し、前記crs送信ステップは、前記共通参照情報crsを送信装置と受信装置に送信し、前記送信装置は暗号化データベース生成ステップと、T送信ステップと、T記憶ステップと、返信生成ステップと、R送信ステップと、を実行し、前記暗号化データベース生成ステップは、前記公開鍵pkと、前記暗号文C1,...,CNとを入力とし、暗号化データベースT:=pk,C1,...,CNを生成する暗号化データベース生成サブステップと、を有し、前記T送信ステップは、前記暗号化データベースTを前記受信装置に送信し、前記T記憶ステップは、前記暗号化データベースTと、前記秘密鍵sk:=x1、x2とを記憶し、前記返信生成ステップはGroth-Sahai証明の知識識別不可能証明πと、前記パラメータGSRとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、前記知識識別不可能証明πを検証する知識識別不可能証明検証サブステップと、前記R送信ステップは、前記返信Rを前記受信装置に送信し、前記受信装置は要求生成ステップと、Q送信ステップと、Q記憶ステップと、文書取得ステップと、を実行し、前記要求生成ステップは、前記暗号文C1,...,CNと、インデックスξとを入力とし、前記暗号文C1,...,CNに含まれる署名をWaters双対署名の署名検証アルゴリズムW.Vrfyおよび、Boneh-Boyen署名の署名検証アルゴリズムBB.Vrfyを実行して検証し、前記暗号文C1,...,CNに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Cξを出力する署名検証サブステップと、前記Q送信ステップは、前記要求Qを前記送信装置に送信し、前記Q記憶ステップは、前記要求QとQprivとを記憶し、前記文書取得ステップは、前記返信Rと、前記パラメータGSSとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、前記非対話ゼロ知識証明δを検証するゼロ知識証明検証サブステップと、を特徴とする紛失通信方法。請求項4から6の何れかに記載の紛失通信方法を実行すべき指令をコンピュータに対してするプログラム。しかしながら、非特許文献1では群の要素に対して署名が可能な署名方式を利用しているため非常に特殊な暗号学仮定を必要とし、安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。また、非特許文献2では上記のような署名方式は利用しないが、値段付き適応的紛失通信という、機能追加した方式を用いる。このため上記とは別の強い暗号学的仮定が必要になり、やはり安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。非特許文献1、2に代表される既存方式においては、汎用的結合可能性という最強の安全性を達成しているものの、適応的紛失通信のプロトコルは非標準的な強い暗号学的仮定を必要とするものしかないことが問題であった。これに対して、標準的な弱い暗号学的仮定だけを用いて汎用的結合可能性をもつ適応的紛失通信を実現するために、標準的な暗号学的仮定を用いた署名方式を組み合わせて、適応的紛失通信のプロトコルを構築することが考えられる。しかしながら、単にこれらの標準的な弱い暗号学的仮定による署名方式を組み合わせただけでは、適応的紛失通信として機能するとはいえ、汎用的結合可能性の証明が容易でないことが問題であった。また、標準的な暗号学的仮定を用いた署名方式のひとつとして、Waters署名が知られているが、Waters署名は群要素に対して署名することが出来ないため、適応的紛失通信に用いる署名としては適さないと考えられており、適応的紛失通信へのWaters署名の組み込みは困難であった。そこで、本発明では、標準的な暗号学的仮定だけを用い、かつ汎用的結合可能性をもつことが証明可能な適応的紛失通信を実現できる紛失通信システムを提供する。本発明の紛失通信システムは、システムパラメータ生成装置、送信装置、受信装置からなる。システムパラメータ生成装置は、システムパラメータ生成部と、crs送信部とを備える。システムパラメータ生成部は、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Groth-Sahai証明の送信装置用パラメータ、受信装置用パラメータを生成し、双線形写像パラメータ、送信装置用パラメータ、受信装置用パラメータ、生成元から設定した第1係数群から共通参照情報crsを生成する。crs送信部は、共通参照情報crsを送信装置と受信装置に送信する。送信装置は、暗号化データベース生成部と、T送信部と、T記憶部と、返信生成部と、R送信部と、を備える。暗号化データベース生成部は、文書m1,...,mNNは2以上の正の整数と、共通参照情報crsとを入力とし、Waters双対署名の第1鍵対、第2鍵対を生成し、Boneh-Boyen署名の第3鍵対を生成し、秘密鍵を生成し、第1鍵対、第2鍵対、第3鍵対を用いて公開鍵を生成し、Waters双対署名の第1署名、第2署名を生成し、Boneh-Boyen署名の第3署名を生成し、文書m1,...,mN、第1鍵対に含まれる値、第2鍵対に含まれる値、共通参照情報crs、第1署名、第2署名、第3署名を用いて、暗号文C1,...,CNを生成し、公開鍵と、暗号文C1,...,CNとから暗号化データベースを生成する。T送信部は、暗号化データベースを受信装置に送信する。T記憶部は、暗号化データベースと、秘密鍵とを記憶する。返信生成部は、共通参照情報crs、暗号化データベース、秘密鍵、要求Qを入力とし、知識識別不可能証明を検証し、知識識別不可能証明が正しい場合に、秘密鍵、要求Qを用いてブラインド復号を実行し、暗号化データベース、共通参照情報crs、要求Qを用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成し、非対話ゼロ知識証明を含む返信Rを生成する。R送信部は、返信Rを受信装置に送信する。受信装置は、要求生成部と、Q送信部と、Q記憶部と、文書取得部と、を備える。要求生成部は、暗号化データベースと、共通参照情報crsと、インデックスξとを入力とし、暗号文C1,...,CNに含まれる署名を検証し、署名が正しい場合に、インデックスξに対応する暗号文Cξ、共通参照情報crsを用いて再ランダム化を実行し、暗号文Cξ、共通参照情報crs、公開鍵を用いて、Groth-Sahai証明の知識識別不可能証明を生成し、知識識別不可能証明を含む要求Q、と、要求Qおよびインデックスξを含むQprivを生成する。Q送信部は、要求Qを送信装置に送信する。Q記憶部は、要求QとQprivとを記憶する。文書取得部は、返信Rと、Qprivと、暗号化データベースと、共通参照情報crsとを入力とし、非対話ゼロ知識証明を検証し、非対話ゼロ知識証明が正しい場合に、Qpriv、暗号文C1,...,CN、共通参照情報crsを用いて、暗号文Cξから文書mξを計算して出力する。本発明の紛失通信システムによれば、汎用的結合可能性を達成している従来方式と異なり,整数要素に対する署名方式で,かつF-偽造不可能性という通常の安全性より強い安全性をもつ署名方式Waters双対署名の変形版を利用することで,判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。本明細書では、λはセキュリティパラメータを表すものとする。双線形写像については付録を参照されたい。また、BMSetupを、入力1λに対して、λビットの素数p、素数位数pの巡回乗法群であるGおよびGT、双線形写像e、群Gの生成元gよりなる双線形写像パラメータΓ:=p,G,GT,e,gを出力する標準的なアルゴリズムとする。本発明では、Groth-Sahai証明を利用する。Groth-Sahai証明のアルゴリズム、簡単な説明は付録Cを参照されたい完全な詳細については参考文献7[GS08]参照。Waters双対署名については付録B1を、Boneh-Boyen署名については付録B2を参照されたい。<本明細書に登場する用語の解説>本明細書において、と表記されている場合、アルゴリズム内部で乱数を発生させてランダムに出力することを意味する。また、と表記されている場合、素数pを法とする整数環Zpからランダムに値を選択することを意味する。まず、図1、図2を参照して、本発明の実施例1に係る紛失通信システム100の動作の概略を説明する。図1は本実施例に係る紛失通信システム100の構成を示すブロック図である。図2は本実施例に係る紛失通信システム100の動作を示すシーケンス図である。本実施例の紛失通信システム100は、システムパラメータ生成装置10、送信装置20、受信装置30からなる。システムパラメータ生成装置10は、システムパラメータ生成部11と、crs送信部12とを備える。以下、実際に行われる手続きの順に説明してゆく。システムパラメータ生成部11は、入力1λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Groth-Sahai証明の送信装置用パラメータ、受信装置用パラメータを生成し、双線形写像パラメータ、送信装置用パラメータ、受信装置用パラメータ、生成元から設定した第1係数群から共通参照情報crsを生成するS11。crs送信部12は、共通参照情報crsを送信装置と受信装置に送信するS12。送信装置20は、暗号化データベース生成部21と、T送信部22と、T記憶部23と、返信生成部24と、R送信部25と、を備える。暗号化データベース生成部21は、文書m1,...,mNNは2以上の正の整数と、共通参照情報crsとを入力とし、Waters双対署名の第1鍵対、第2鍵対を生成し、Boneh-Boyen署名の第3鍵対を生成し、秘密鍵を生成し、第1鍵対、第2鍵対、第3鍵対を用いて公開鍵を生成し、Waters双対署名の第1署名、第2署名を生成し、Boneh-Boyen署名の第3署名を生成し、文書m1,...,mN、第1鍵対に含まれる値、第2鍵対に含まれる値、共通参照情報crs、第1署名、第2署名、第3署名を用いて、暗号文C1,...,CNを生成し、公開鍵と、暗号文C1,...,CNとから暗号化データベースを生成するS21。T送信部22は、暗号化データベースを受信装置に送信するS22。T記憶部23は、暗号化データベースと、秘密鍵とを記憶するS23。受信装置30は、要求生成部31と、Q送信部32と、Q記憶部33と、文書取得部34と、を備える。要求生成部31は、暗号化データベースと、共通参照情報crsと、インデックスξとを入力とし、暗号文C1,...,CNに含まれる署名を検証し、署名が正しい場合に、インデックスξに対応する暗号文Cξ、共通参照情報crsを用いて再ランダム化を実行し、暗号文Cξ、共通参照情報crs、公開鍵を用いて、Groth-Sahai証明の知識識別不可能証明を生成し、知識識別不可能証明を含む要求Q、と、要求Qおよびインデックスξを含むQprivを生成するS31。Q送信部32は、要求Qを送信装置に送信するS32。Q記憶部33は、要求QとQprivとを記憶するS33。送信装置20の返信生成部24は、共通参照情報crs、暗号化データベース、秘密鍵、要求Qを入力とし、知識識別不可能証明を検証し、知識識別不可能証明が正しい場合に、秘密鍵、要求Qを用いてブラインド復号を実行し、暗号化データベース、共通参照情報crs、要求Qを用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成し、非対話ゼロ知識証明を含む返信Rを生成するS24。R送信部25は、返信Rを受信装置に送信するS25。受信装置30の文書取得部34は、返信Rと、Qprivと、暗号化データベースと、共通参照情報crsとを入力とし、非対話ゼロ知識証明を検証し、非対話ゼロ知識証明が正しい場合に、Qpriv、暗号文C1,...,CN、共通参照情報crsを用いて、暗号文Cξから文書mξを計算して出力するS34。このように、本実施例の紛失通信システム100は、汎用的結合可能性を達成している従来方式と異なり,整数要素に対する署名方式で,かつF-偽造不可能性という通常の安全性より強い安全性をもつ署名方式Waters双対署名の変形版を利用することで,判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。次に、図3から図12を用いて、本実施例の紛失通信システムをさらに詳細に説明する。図3は本実施例のシステムパラメータ生成装置10が備えるシステムパラメータ生成部11の構成を示すブロック図である。図4は本実施例のシステムパラメータ生成装置10が備えるシステムパラメータ生成部11の動作を示すフローチャートである。図5は本実施例の送信装置20が備える暗号化データベース生成部21の構成を示すブロック図である。図6は本実施例の送信装置20が備える暗号化データベース生成部21の動作を示すフローチャートである。図7は本実施例の受信装置30が備える要求生成部31の構成を示すブロック図である。図8は本実施例の受信装置30が備える要求生成部31の動作を示すフローチャートである。図9は本実施例の送信装置20が備える返信生成部24の構成を示すブロック図である。図10は本実施例の送信装置20が備える返信生成部24の動作を示すフローチャートである。図11は本実施例の受信装置30が備える文書取得部34の構成を示すブロック図である。図12は本実施例の受信装置30が備える文書取得部34の動作を示すフローチャートである。以下、実際に行われる手続きの順に説明してゆく。前述したように本実施例の紛失通信システム100はシステムパラメータ生成装置10、送信装置20、受信装置30からなる。前述したようにシステムパラメータ生成装置10はシステムパラメータ生成部11と、crs送信部12とを備える。システムパラメータ生成部11は、双線形写像パラメータ生成手段11aと、送信装置用パラメータ生成手段11bと、受信装置用パラメータ生成手段11cと、第1係数設定手段11dと、システムパラメータ生成手段11eとを備える。双線形写像パラメータ生成手段11aは、入力1λに対して、BMSetupアルゴリズムを実行して、λビットの素数p、素数位数pの巡回乗法群であるGおよびGT、双線形写像e、群Gの生成元gよりなる双線形写像パラメータΓ:=p,G,GT,e,gを生成するSS11a。システムパラメータ生成手段11eは、共通参照情報crs:=Γ、GSS、GSR、g1、g2、ζを生成するSS11e。crs送信部12は、共通参照情報crsを送信装置20と受信装置30に送信するS12。前述したように送信装置20は暗号化データベース生成部21と、T送信部22と、T記憶部23と、返信生成部24と、R送信部25とを備える。暗号化データベース生成部21は、第1Waters鍵対生成手段21aと、第2Waters鍵対生成手段21bと、BB鍵対生成手段21cと、秘密鍵生成手段21dと、公開鍵生成手段21eと、第2係数設定手段21fと、第1Waters署名生成手段21gと、第2Waters署名生成手段21hと、BB署名生成手段21iとを備える。暗号化データベース生成手段21kは、公開鍵pkと、暗号文C1,...,CNとを入力とし、暗号化データベースT:=pk,C1,...,CNを生成するSS21k。T送信部22は、暗号化データベースTを受信装置30に送信するS22。T記憶部23は、暗号化データベースTと、秘密鍵sk:=x1、x2とを記憶するS23。前述したように受信装置30は要求生成部31と、Q送信部32と、Q記憶部33と、文書取得部34と、を備える。要求生成部31は、署名検証部31aと、再ランダム化手段31bと、知識識別不可能証明生成手段31cと、要求生成手段31dとを備える。署名検証手段31aは、暗号文C1,...,CNと、インデックスξとを入力とし、暗号文C1,...,CNに含まれる署名をWaters双対署名の署名検証アルゴリズムW.Vrfyおよび、Boneh-Boyen署名の署名検証アルゴリズムBB.Vrfyを実行して検証し、暗号文C1,...,CNに含まれる署名が正しい場合に、インデックスξに対応する暗号文Cξを出力するSS31a。Q送信部32は、要求Qを前記送信装置に送信するS32。Q記憶部33は、要求QとQprivとを記憶するS33。送信装置20の返信生成部24は、知識識別不可能証明検証手段24aと、ブラインド復号手段24bと、非対話ゼロ知識証明生成手段24cと、返信生成手段24dと、を備える。知識識別不可能証明検証手段24aは、Groth-Sahai証明の知識識別不可能証明πと、前記パラメータGSRとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、知識識別不可能証明πを検証するSS24a。R送信部25は、返信Rを受信装置30に送信するS25。受信装置30の文書取得部34は、ゼロ知識証明検証手段34aと、文書生成手段34bとを備える。ゼロ知識証明検証手段34aは、返信Rと、パラメータGSSとを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、非対話ゼロ知識証明δを検証するSS34a。このように、本実施例の紛失通信システム100は、汎用的結合可能性を達成している従来方式と異なり,整数要素に対する署名方式で,かつF-偽造不可能性という通常の安全性より強い安全性をもつ署名方式Waters双対署名の変形版を利用することで,判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。<本発明と従来技術の比較>次に、図13、図14を参照して、本発明と従来技術との比較について説明する。図13は本発明の紛失通信システムと従来技術との違いを示す表である。図14は本発明の紛失通信システムと従来技術との違いを座標軸に表した図である。図13は、左隅列に本明細書における参考文献番号を記した。また、左から2番目の列についてはこれらの文献を表す略号を表記している。また、UCとは安全性が汎用的結合可能性を満たしていることを示す。FullSimとは、fullysimultable安全性という汎用的結合性より弱い安全性を満たしていることを示す。q-hiddenLRSW仮定など、q-が接頭についている仮定は、暗号の分野でq仮定と呼ばれ、標準的な暗号学的仮定であるRSA仮定、DDH判定Differ-Hellman仮定、DLIN判定線形仮定に比べて安全性の根拠に信頼がおけない。参考文献1BB04DBonehandXBoyenEfficientSelectiveIDSecureIdentityBasedEncryptionWithoutRandomOraclesInEUROCRYPT’04volume3027ofLectureNotesinComputerSciencepages223238Springer2004参考文献2BF01DBonehandMKFranklinIdentityBasedEncryptionfromtheWeilPairingInCRYPTO’01volume2139ofLectureNotesinComputerSciencepages213229Springer2001参考文献3CNS07JCamenischGNevenandAShelatSimulatableAdaptiveObliviousTransferInEUROCRYPT’07volume4515ofLectureNotesinComputerSciencepages573590Springer2007参考文献4CS97JCamenischandMStadlerEfficientGroupSignatureSchemesforLargeGroupsInCRYPTO’97volume1294ofLectureNotesinComputerSciencepages410424Springer1997参考文献5GH08MGreenandSHohenbergerUniversallyComposableAdaptiveObliviousTransferInASIACRYPT’08volume5350ofLectureNotesinComputerSciencepages179197Springer2008参考文献6GH11MGreenandSHohenbergerPracticalAdaptiveObliviousTransferfromaSimpleAssumptionInTCC’01volume6597ofLectureNotesinComputerSciencepages347363Springer2011httpeprintiacrorg2010109参考文献7GS08JGrothandASahaiEfficientNoninteractiveProofSystemsforBilinearGroupsInEUROCRYPT’08volume4965ofLectureNotesinComputerSciencepages415432Springer2008参考文献8JL09SJareckiandXLiuEfficientObliviousPseudorandomFunctionwithApplicationstoAdaptiveOTandSecureComputationofSetIntersectionInTCCvolume5444ofLectureNotesinComputerSciencepages577594Springer2009参考文献9KN09KKurosawaandRNojimaSimpleAdaptiveObliviousTransferwithoutRandomOracleInASIACRYPT’09volume5912ofLectureNotesinComputerSciencepages334346Springer2009参考文献10KNP10KKurosawaRNojimaandLTPhongEfficiencyImprovedFullSimulatableAdaptiveOTundertheDDHAssumptionInSCNvolume6280ofLectureNotesinComputerSciencepages172181Springer2010参考文献11RKP09ARialMKohlweissandBPreneelUniversallyComposableAdaptivePricedObliviousTransferInPairingvolume5671ofLectureNotesinComputerSciencepages231247Springer2009参考文献12Wat09BWatersDualSystemEncryptionRealizingFullySecureIBEandHIBEunderSimpleAssumptionsInCRYPTO’09volume5677ofLectureNotesinComputerSciencepages619636Springer2009<本発明と従来技術の比較おわり><本発明が有する進歩性についての補足>線形暗号:本発明の方式は以下の線形暗号方式の署名からできている。この基本構造は参考文献5、11においても同じである。本発明の進歩性について:本発明では、送信装置は線形暗号方式により暗号文を生成し,群Gの要素であるへの署名を生成し、これらを受信装置に送信している。そして受信装置はインデックスξを選び、その暗号文に対して再ランダム化を行い、正しく再ランダム化を行ない、それに対応する署名を知っていることを証明する知識識別不可能証明Groth-Sahai証明によるを生成する。しかし、Groth-Sahai証明は群要素に関する証明しか生成することができない。ゆえに上記のようにρ1やρ2に対してではなくに署名する必要がある。つまりメッセージが群Gの要素となっているような署名方式が必要と一見考えられる。なおこのような署名方式で安全なものは近年になって開発されたばかりであり、提案数自体が少ない上、それらは標準的でない暗号学仮定に基づいており、信頼性が低い。本発明ではWaters双対署名を利用しているが、この方式は群要素に対して署名できない整数に対して署名可能。よって,Waters双対署名を利用することで適応的紛失通信を構成することは非自明である。しかしこのままではGroth-Sahai証明を利用できないため、Waters双対署名を変形し適応的紛失通信、明細書の暗号文のなかのという要素が追加要素である、通常の署名より高い安全性を達成することρ1やρ2に対する署名の偽造ができない、という通常の安全性ではなく、に対する署名さえも偽造できない、というより強力な安全性で、群要素に対して署名ができなくとも、Groth-Sahai証明と組み合わせることを可能にした。またGroth-Sahai証明を署名保持の証明に利用するには署名がすべて群要素である必要があるが、Waters双対署名の署名は一つだけ群要素でないものが含まれている明細書のtagkがそれである。しかし提案した適応的紛失通信の方式の中では,その群要素でない署名要素はブラインドして相手に直接送ることで署名の情報を漏らすことなくGroth-Sahai証明を可能にしている。以上のことから従来の適応的紛失通信方式にWaters双対署名を利用して改良することは非自明であり、本発明は従来技術に対して進歩性を有している。<本発明が有する進歩性についての補足おわり><付録A:ペアリング>双線型性を満たすペアリングと呼ばれる演算は楕円曲線上の二点に定義される。なお、楕円曲線上の群は普通加法群であるが、暗号理論学会での慣習に従い乗法群として記述する。GとGTを位数pの群とする。ここでpは十分大きい素数である。この二つの群の間の双線型写像e:G×G→GTは以下の性質を満たす。双線型性:任意のg,h∈Gおよび任意のa,b∈Zに対してega,hb=eg,habが成立する。非退化性:eg,g≠1を満たすgが存在する。つまり、もしgがGの生成元ならeg,gはGTの生成元である。計算可能性:任意のg,h∈Gに対して、eg,hは効率的につまり多項式時間で計算可能である。詳しくは[BF01]や現代暗号への招待黒澤馨著,サイエンス社の13章を参照されたい。<付録A:ペアリングおわり><付録B:ディジタル署名>[B1:Waters双対署名][B2:変形Boneh-Boyen署名]F-署名:選択メッセージ攻撃に対してF-セキュアと呼ばれるより強い安全性の定義を考える。Fを効率的に計算可能な全単射であるものとする。署名スキームは、以下のゲームによるアドバンテージが無視できるほど小さい場合には、選択メッセージ攻撃下においてF-セキュアと呼ばれる。手順1セットアップ:挑戦者は、を発生させてvkを敵対者に送る。手順2質問:敵対者はメッセージを挑戦者に送り、挑戦者はを返信する。これらの質問はi=1~Nまで適応的に挑戦者に送信される。ここでを敵対者からの質問であるメッセージのセットを表すものとする。手順3出力:敵対者はy,σを出力する。をとした場合に、かつ、が成り立つ場合には、敵対者がゲームに勝利したことになる。ここで、を、攻撃者がゲームに勝利する確率と定義して、全てのPPT攻撃者について、が成り立つとき、署名スキームSigは、選択メッセージ攻撃に対するF-セキュアである。<付録B:ディジタル署名おわり><付録C:Groth-Sahai証明>Groth-Sahai証明システムでは等式の充足可能性例えばペアリング生成等式に対して、効率的に非対話識別不可能NIWI証明、非対話ゼロ知識NIZK証明を行うことができる。証明システムはGroth-Sahaiコミットメントスキームに基づいている。Groth-Sahaiコミットメントスキーム:本スキームでは、まず、双線形写像パラメータを生成する。GS.ComSetupΓ:共通参照情報crsGSCを出力する。GS.CommitcrsGSC,m,d:コミットm∈Gである入力m、共通参照情報crsGSC、デコミットメントd、として出力コミットメントを生成する。GS.ExpComcrsGSC,m,b,d:入力m∈Zp、基数b∈G、共通参照情報crsGSC、デコミットメントd、cをとして、出力b,cを生成する。GS.OpeningcrsGSC,c,m,d:dがm,cに対して正当なデコミットメントである場合、1を出力する。それ以外の場合は、0を出力する。すなわち、である。b,cがmの累乗で約束される検証の場合には、となる。Groth-Sahaiコミットメントスキームの共通参照情報には2タイプの生成物が存在する。1つのタイプではコミットメントが完全拘束であり、計算量的拘束であり抽出可能である。もう1つのタイプでは、コミットメントが完全秘匿であり、計算量的拘束であり曖昧性を持つ。これらの2つのタイプは計算量的識別不可能である。本証明システムは例えばDLIN仮定などの暗号学的仮定裏付けられている以下、本説明ではDLIN仮定を用いるものとする。ステートメントSは、変数と、定数と、G内の値であるコミットメントにより構成される。GrothとSahaiは、非対話知識証明NIPKの構築を以下の式で表した。この証明πはコミットメントc1,...,cm,d1,...,dnを含む。GrothとSahaiは、これらのコミットメントからペアリング生成式を満足する値を開くことのできる効率的なエキストラクタを提供する。ここで、CamenischとStadler[CS97]の記法、例えば、を用いる。本システムでは、証明者は同形のコミットメントスキームと共通参照情報CRSとを用いてwitness証拠、群の元を遂行する。共通参照情報CRSには2つのタイプが存在する。1つのタイプは完全拘束コミットメントスキームを、もう1つのタイプは完全秘匿コミットメントスキームを与える。これらの2つのタイプは計算量的識別不可能である。証明システム:証明システムは以下のアルゴリズムにより構成される。GS.SetupΓ:入力を実行して、出力である証明システムの共通参照情報GSを生成する。共通参照情報GSは、コミットメントスキームの共通参照情報crsGSCを含む。GS:ProveGS,S,W:ステートメントSと、witness証拠とを入力とし、証明πを出力する。GS.VrfyGS,π:証明πを入力とし、照明を検証し、正当であれば1を出力し、それ以外は0を出力する。GS.ExtSetupΓ:共通参照情報GSその分布は通常の共通参照情報と一致すると、正当なwitnessを導出するためのトラップドアtdextとを出力する。GS.ExtractGS,tdext,π:証明πと、トラップドアtdextとを入力とし、各コミットメントCiから抽出値を抽出して等式を満たす証拠を出力する。GS.SimSetupΓ:GS.SetupΓの出力である通常の共通参照情報と計算量的識別不可能な模擬共通参照情報GS’と、模擬トラップドアtdsimを出力する。GS.SimProveGS’,tdsim,S:模擬共通参照情報GS’と、模擬トラップドアtdsimとを入力とし、GS.VrfyGS’,π=1を満たすステートメントSの模擬証明πを出力する。セキュリティ特性:本証明システムは以下の特性を満足する。正当性:全てのについて、を満たす。抽出性:および、証明πについて、である場合に、はステートメントSを確率1で満足する。共通参照情報CRSの識別不可能性:と、について、を満たす。構成可能なwitnessの識別不可能性:全てのPPT攻撃者について、が成立する。Groth-Sahai証明システムは、制限されたステートメントのクラスΣZKはこのクラスを意味するにおける構成可能なゼロ知識証明を提供する。構成可能なゼロ知識:全てのPPT攻撃者について、が成立する。F-抽出可能非対話知識証明:Groth-Sahai証明システムにおいては、非対話知識証明NIWIまたはNIZKから、トラップドアtdextを使うことによりwitnessを抽出できる。しかしながら、この証明システムにおいては、群の元のみがコミットできるため、群Gの元を抽出できるのみである。従って、本証明システムにおいてメッセージm∈Zpを選択して、gm∈Gをコミットし、witnessであるgmを用いて、非対話証明を生成する場合には、gmのみを抽出することができるこれはm自身でなく、関数Fm:=gmの出力であることに注意する。この性質から、Groth-Sahai証明システムはF-抽出可能性を備えると言われる。定理2[GS08]:DLIN仮定が成り立つならば、Groth-Sahai証明システム効率的にインスタンス化できる。<付録C:Groth-Sahai証明おわり><付録D:暗号学的仮定><付録D:暗号学的仮定おわり>また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"