"システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、前記システムパラメータ生成装置は、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成部と、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の送信装置用パラメータを生成する送信装置用パラメータ生成部と、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の受信装置用パラメータを生成する受信装置用パラメータ生成部と、前記生成元から係数群を計算する係数生成部と、前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、前記送信装置は、Waters双対署名の鍵生成アルゴリズムを実行して、Waters双対署名の鍵対を生成する鍵対生成部と、秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成部と、0以上p-1以下のランダムな整数ρ1,...,ρNを選択し、Waters双対署名の署名生成アルゴリズムを実行して、前記乱数ρ1,...,ρNに対する署名を生成する署名生成部と、文書m1,...,mNNは2以上の正の整数を入力とし、文書mjjは1以上N以下の整数と前記公開鍵と乱数ρjと前記署名と前記鍵対と前記共通参照情報から、変形Boneh-Franklin暗号の暗号文Cjを求め、暗号文C1,...,CNを生成する暗号文生成部と、前記公開鍵と前記暗号文C1,...,CNから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成部と、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムを実行して、要求Qに含まれる知識識別不可能証明を検証する知識識別不可能証明検証部と、前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号部と、前記要求Qと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成部と、前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Rを生成し、前記返信Rを前記受信装置へ送信する返信生成部と、前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録部を備え、前記受信装置は、前記暗号化データベースとインデックスξを入力とし、Waters双対署名の署名検証アルゴリズムを実行して、前記暗号文C1,...,CNに含まれる前記署名を検証し、前記暗号文Cj毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文C1,...,CN全てについて前記署名が正しい署名であると判定され、前記暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Cξを出力する署名検証部と、前記公開鍵と前記共通参照情報を用いて、前記暗号文Cξから、再ランダム化暗号文を生成する再ランダム化部と、前記暗号文Cξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成部と、前記再ランダム化暗号文と前記知識識別不可能証明から、要求Qを生成し、前記要求Qおよびインデックスξから、Qprivを生成し、前記要求Qと前記係数θを送信装置に送信する要求生成部と、前記返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証部と、前記非対話ゼロ知識証明が正しい場合に、前記Qprivと前記暗号文Cξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書mξを計算して出力する復号部と、前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Qと前記Qprivを記録する要求記録部を備えることを特徴とする紛失通信システム。システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、前記システムパラメータ生成装置は、セキュリティパラメータλを入力とし、λビットの素数pと、素数位数pの巡回乗法群GおよびGTと、前記巡回乗法群Gの生成元gと、双線形写像eを含む、双線形写像パラメータΓ:=p,G,GT,e,gを生成する双線形写像パラメータ生成部と、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の送信装置用パラメータGSSを生成する送信装置用パラメータ生成部と、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の受信装置用パラメータGSRを生成する受信装置用パラメータ生成部と、0以上p-1以下の整数からランダムに冪指数ζおよびyhを選択し、g2:=g^ζ以下、^はべき乗を意味するおよびh:=g^yhを計算する係数生成部と、前記双線形写像パラメータΓと前記送信装置用パラメータGSSと前記受信装置用パラメータGSRと前記係数g2および前記係数hから、共通参照情報crs:=Γ,GSS,GSR,g2hを生成し、前記共通参照情報crsを前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、前記送信装置は、Waters双対署名の鍵生成アルゴリズムW.GenΓを実行して、Waters双対署名の鍵対VK,SKを生成する鍵対生成部と、0以上p-1以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報crsを用いて、g1:=g^αを計算し、前記鍵対VKと前記係数g1から、公開鍵pk:=g1,VKを生成する鍵生成部と、文書m1,...,mN以下、Nは2以上の正の整数を入力とし、j=1,...,Nに対して、0以上p-1以下のランダムな整数ρjを選択し、Waters双対署名の署名生成アルゴリズムW.Signρjを実行して、前記乱数ρjに対する署名sigjを生成する署名生成部と、前記文書m1,...,mNと前記公開鍵pkと前記乱数ρjと前記署名sigjと前記鍵対VKに含まれる値uと前記共通参照情報crsから、変形Boneh-Franklin暗号の暗号文Cj=c1j,c2j,c3j,c4j,c5jをCj:=g1^ρj,h^ρj,mjeg,g2,sigj,u^ρjのように生成する暗号文生成部と、前記公開鍵pkと前記暗号文C1,...,CNから、暗号化データベースT:=pk,C1,...,CNを生成し、前記暗号化データベースTを前記受信装置に送信する暗号化データベース生成部と、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、前記要求Qに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証部と、前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報crsを用いて、前記要求Qに含まれる再ランダム化暗号文dから、a:=ed,g2^1/αを計算し、ブラインド復号結果aを生成するブラインド復号部と、前記再ランダム化暗号文dと前記ブラインド復号結果aと前記公開鍵pkと前記秘密鍵αと前記共通参照情報crsを用いて、Groth-Sahai証明の非対話ゼロ知識証明δをにより生成する非対話ゼロ知識証明生成部と、前記ブラインド復号結果aと前記非対話ゼロ知識証明δから、返信R:=a,δを生成し、前記返信Rを前記受信装置へ送信する返信生成部と、前記共通参照情報crsと前記暗号化データベースTと秘密鍵αを記録する秘密鍵記録部を備え、前記受信装置は、前記暗号化データベースTとインデックスξを入力とし、j=1,...,Nのすべてについて前記暗号文Cjに含まれる前記署名sigjを、Waters双対署名の署名検証アルゴリズムW.Vrfyを実行して、検証し、前記署名sigjのいずれかが正しい署名でないと判定されると停止し、j=1,...,Nのすべてについて前記暗号文Cjに含まれるc1jとc2jが、eh,c1j=ec2j,g1を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文C1,...,CN全てについて前記署名sigjが正しい署名であると判定され、前記暗号文C1,...,CN全てについて前記暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Cξを出力する署名検証部と、0以上p-1以下の整数からランダムに冪指数vを選択し、前記公開鍵pkと前記共通参照情報crsと前記暗号文Cξに含まれるc1ξを用いて、d:=c1ξg1^vおよびt:=g2^vを計算し、前記再ランダム化暗号文dを生成する再ランダム化部と、前記暗号文Cξに含まれる署名sigξの生成に利用された0以上p-1以下のランダムな整数tagkと、前記Waters双対署名sigξの検証に利用された0以上p-1以下のランダムな整数tagcを用いて、sigξ\{tagk}:=ρ1,...,ρKはWaters双対署名からtagkを除いたものとして、θ:=1/tagc-tagkを生成し、前記暗号文Cξと前記再ランダム化暗号文dと前記公開鍵pkと前記共通参照情報crsを用いて、前記知識識別不可能証明πをにより生成する知識識別不可能証明生成部と、前記再ランダム化暗号文dと前記知識識別不可能証明πから、前記要求Q:=d,πを生成し、前記要求Qと前記インデックスξと前記乱数vから、Qpriv:=Q,ξ,vを生成し、前記要求Qおよび前記係数θを送信装置に送信する要求生成部と、前記返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証部と、前記非対話ゼロ知識証明δが正しい場合に、前記Qprivと前記暗号文Cξと前記共通参照情報crsを用いて、mξ:=c3ξeg,g2^v/aを計算して、前記ブラインド復号結果aから文書mξを出力する復号部と、前記共通参照情報crsと前記暗号化データベースTと前記公開鍵pkと前記要求Qと前記Qprivを記録する要求記録部を備えることを特徴とする紛失通信システム。システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成ステップを実行し、システムパラメータ生成装置が、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の送信装置用パラメータを生成する送信装置用パラメータ生成ステップを実行し、システムパラメータ生成装置が、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の受信装置用パラメータを生成する受信装置用パラメータ生成ステップを実行し、システムパラメータ生成装置が、前記生成元から係数群を計算する係数生成ステップを実行し、システムパラメータ生成装置が、前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、送信装置が、Waters双対署名の鍵生成アルゴリズムを実行して、Waters双対署名の鍵対を生成する鍵対生成ステップを実行し、送信装置が、秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成ステップを実行し、送信装置が、0以上p-1以下のランダムな整数ρ1,...,ρNを選択し、Waters双対署名の署名生成アルゴリズムを実行して、前記乱数ρ1,...,ρNに対する署名を生成する署名生成ステップを実行し、送信装置が、文書m1,...,mNNは2以上の正の整数を入力とし、文書mjjは1以上N以下の整数と前記公開鍵と乱数ρjと前記署名と前記鍵対と前記共通参照情報から、変形Boneh-Franklin暗号の暗号文Cjを求め、暗号文C1,...,CNを生成する暗号文生成ステップを実行し、送信装置が、前記公開鍵と前記暗号文C1,...,CNから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成ステップを実行し、送信装置が、前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録ステップを実行し、受信装置が、前記暗号化データベースとインデックスξを入力とし、Waters双対署名の署名検証アルゴリズムを実行して、前記暗号文C1,...,CNに含まれる前記署名を検証し、前記暗号文Cj毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文C1,...,CN全てについて前記署名が正しい署名であると判定され、前記暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Cξを出力する署名検証ステップを実行し、受信装置が、前記公開鍵と前記共通参照情報を用いて、前記暗号文Cξから、再ランダム化暗号文を生成する再ランダム化ステップを実行し、受信装置が、前記暗号文Cξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成ステップを実行し、受信装置が、前記再ランダム化暗号文と前記知識識別不可能証明から、要求Qを生成し、前記要求Qおよびインデックスξから、Qprivを生成し、前記要求Qと前記係数θを送信装置に送信する要求生成ステップを実行し、受信装置が、前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Qと前記Qprivを記録する要求記録ステップを実行し、送信装置が、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムを実行して、要求Qに含まれる知識識別不可能証明を検証する知識識別不可能証明検証ステップを実行し、送信装置が、前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号ステップを実行し、送信装置が、前記要求Qと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成ステップを実行し、送信装置が、前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Rを生成し、前記返信Rを前記受信装置へ送信する返信生成ステップを実行し、受信装置が、前記返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証ステップを実行し、受信装置が、前記非対話ゼロ知識証明が正しい場合に、前記Qprivと前記暗号文Cξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書mξを計算して出力する復号ステップを実行することを特徴とする紛失通信方法。システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数pと、素数位数pの巡回乗法群GおよびGTと、前記巡回乗法群Gの生成元gと、双線形写像eを含む、双線形写像パラメータΓ:=p,G,GT,e,gを生成する双線形写像パラメータ生成ステップを実行し、システムパラメータ生成装置が、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の送信装置用パラメータGSSを生成する送信装置用パラメータ生成ステップを実行し、システムパラメータ生成装置が、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の受信装置用パラメータGSRを生成する受信装置用パラメータ生成ステップを実行し、システムパラメータ生成装置が、0以上p-1以下の整数からランダムに冪指数ζおよびyhを選択し、g2:=g^ζ以下、^はべき乗を意味するおよびh:=g^yhを計算する係数生成ステップを実行し、システムパラメータ生成装置が、前記双線形写像パラメータΓと前記送信装置用パラメータGSSと前記受信装置用パラメータGSRと前記係数g2および前記係数hから、共通参照情報crs:=Γ,GSS,GSR,g2hを生成し、前記共通参照情報crsを前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、送信装置が、Waters双対署名の鍵生成アルゴリズムW.GenΓを実行して、Waters双対署名の鍵対VK,SKを生成する鍵対生成ステップを実行し、送信装置が、0以上p-1以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報crsを用いて、g1:=g^αを計算し、前記鍵対VKと前記係数g1から、公開鍵pk:=g1,VKを生成する鍵生成ステップを実行し、送信装置が、文書m1,...,mN以下、Nは2以上の正の整数を入力とし、j=1,...,Nに対して、0以上p-1以下のランダムな整数ρjを選択し、Waters双対署名の署名生成アルゴリズムW.Signρjを実行して、前記乱数ρjに対する署名sigjを生成する署名生成ステップを実行し、送信装置が、前記文書m1,...,mNと前記公開鍵pkと前記乱数ρjと前記署名sigjと前記鍵対VKに含まれる値uと前記共通参照情報crsから、変形Boneh-Franklin暗号の暗号文Cj=c1j,c2j,c3j,c4j,c5jをCj:=g1^ρj,h^ρj,mjeg,g2,sigj,u^ρjのように生成する暗号文生成ステップを実行し、送信装置が、前記公開鍵pkと前記暗号文C1,...,CNから、暗号化データベースT:=pk,C1,...,CNを生成し、前記暗号化データベースTを前記受信装置に送信する暗号化データベース生成ステップを実行し、前記共通参照情報crsと前記暗号化データベースTと秘密鍵αを記録する秘密鍵記録ステップを実行し、受信装置が、前記暗号化データベースTとインデックスξを入力とし、j=1,...,Nのすべてについて前記暗号文Cjに含まれる前記署名sigjを、Waters双対署名の署名検証アルゴリズムW.Vrfyを実行して、検証し、前記署名sigjのいずれかが正しい署名でないと判定されると停止し、j=1,...,Nのすべてについて前記暗号文Cjに含まれるc1jとc2jが、eh,c1j=ec2j,g1を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文C1,...,CN全てについて前記署名sigjが正しい署名であると判定され、前記暗号文C1,...,CN全てについて前記暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Cξを出力する署名検証ステップを実行し、受信装置が、0以上p-1以下の整数からランダムに冪指数vを選択し、前記公開鍵pkと前記共通参照情報crsと前記暗号文Cξに含まれるc1ξを用いて、d:=c1ξg1^vおよびt:=g2^vを計算し、前記再ランダム化暗号文dを生成する再ランダム化ステップを実行し、受信装置が、前記暗号文Cξに含まれる署名sigξの生成に利用された0以上p-1以下のランダムな整数tagkと、前記Waters双対署名sigξの検証に利用された0以上p-1以下のランダムな整数tagcを用いて、sigξ\{tagk}:=ρ1,...,ρKはWaters双対署名からtagkを除いたものとして、θ:=1/tagc-tagkを生成し、前記暗号文Cξと前記再ランダム化暗号文dと前記公開鍵pkと前記共通参照情報crsを用いて、前記知識識別不可能証明πをにより生成する知識識別不可能証明生成ステップを実行し、受信装置が、前記再ランダム化暗号文dと前記知識識別不可能証明πから、前記要求Q:=d,πを生成し、前記要求Qと前記インデックスξと前記乱数vから、Qpriv:=Q,ξ,vを生成し、前記要求Qおよび前記係数θを送信装置に送信する要求生成ステップを実行し、受信装置が、前記共通参照情報crsと前記暗号化データベースTと前記公開鍵pkと前記要求Qと前記Qprivを記録する要求記録ステップを実行し、送信装置が、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、前記要求Qに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証ステップを実行し、送信装置が、前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報crsを用いて、前記要求Qに含まれる再ランダム化暗号文dから、a:=ed,g2^1/αを計算し、ブラインド復号結果aを生成するブラインド復号ステップを実行し、送信装置が、前記再ランダム化暗号文dと前記ブラインド復号結果aと前記公開鍵pkと前記秘密鍵αと前記共通参照情報crsを用いて、Groth-Sahai証明の非対話ゼロ知識証明δをにより生成する非対話ゼロ知識証明生成ステップを実行し、送信装置が、前記ブラインド復号結果aと前記非対話ゼロ知識証明δから、返信R:=a,δを生成し、前記返信Rを前記受信装置へ送信する返信生成ステップを実行し、受信装置が、前記返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証ステップを実行し、受信装置が、前記非対話ゼロ知識証明δが正しい場合に、前記Qprivと前記暗号文Cξと前記共通参照情報crsを用いて、mξ:=c3ξeg,g2^v/aを計算して、前記ブラインド復号結果aから文書mξを出力する復号ステップを実行することを特徴とする紛失通信方法。請求項3または4に記載のいずれかの紛失通信方法を実行すべき指令をコンピュータに対してするプログラム。しかしながら、非特許文献1では群の要素に対して署名が可能な署名方式を利用しているため非常に特殊な暗号学仮定を必要とし、安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。また、非特許文献2では群要素に対して署名可能な方式は利用しないが、値段付き適応的紛失通信という、機能追加した方式であり、かつ安全性を証明するために通常の署名より強い安全性をもつ署名方式を利用している。そのため、上記とは別の強い暗号学的仮定が必要になり、やはり安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。本願の出願人による未公開の先願である特願2011-96184号に記載されている方式では、特殊な暗号学的仮定を用いる問題を解決し、標準的な暗号学的仮定である判定線形仮定だけを用いることで、汎用的結合可能性を持つ適応的紛失通信を実現している。しかし、利用している暗号方式が乱数を2つ用いる方式であるため、署名の数が多く、暗号文のサイズが大きくなり非効率的であるという問題が解決されていなかった。そこで、本発明では、標準的な暗号学的仮定だけを用い、かつ汎用的結合可能性をもつことが証明可能でありながら、暗号文のサイズを削減した効率的な適応的紛失通信を実現できる紛失通信システムを提供する。本発明の紛失通信システムは、システムパラメータ生成装置、送信装置、受信装置からなる。システムパラメータ生成装置は、双線形写像パラメータ生成部と送信装置用パラメータ生成部と受信装置用パラメータ生成部と係数生成部とシステムパラメータ生成部を備える。双線形写像パラメータ生成部は、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する。送信装置用パラメータ生成部は、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の送信装置用パラメータを生成する。受信装置用パラメータ生成部は、Groth-Sahai証明のパラメータ設定アルゴリズムを実行して、Groth-Sahai証明の受信装置用パラメータを生成する。係数生成部は、生成元から係数群を計算する。システムパラメータ生成部は、双線形写像パラメータと送信装置用パラメータと受信装置用パラメータと係数群から、共通参照情報を生成し、共通参照情報を送信装置および受信装置へ送信する。送信装置は、鍵対生成部と鍵生成部と署名生成部と暗号文生成部と暗号化データベース生成部と知識識別不可能証明検証部とブラインド復号部と非対話ゼロ知識証明生成部と返信生成部と秘密鍵記録部を備える。鍵対生成部は、Waters双対署名の鍵生成アルゴリズムを実行して、Waters双対署名の鍵対を生成する。鍵生成部は、秘密鍵を生成し、鍵対と秘密鍵から計算した係数から、公開鍵を生成する。署名生成部は、0以上p-1以下のランダムな整数ρ1,...,ρNを選択し、Waters双対署名の署名生成アルゴリズムを実行して、乱数ρ1,...,ρNに対する署名を生成する。暗号文生成部は、文書m1,...,mNNは2以上の正の整数を入力とし、文書mjjは1以上N以下の整数と公開鍵と乱数ρjと署名と鍵対と共通参照情報から、変形Boneh-Franklin暗号の暗号文Cjを求め、暗号文C1,...,CNを生成する。暗号化データベース生成部は、公開鍵と暗号文C1,...,CNから、暗号化データベースを生成し、暗号化データベースを受信装置に送信する。知識識別不可能証明検証部は、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムを実行して、要求Qに含まれる知識識別不可能証明を検証する。ブラインド復号部は、知識識別不可能証明が正しい場合に、秘密鍵と共通参照情報を用いて、ブラインド復号結果を生成する。非対話ゼロ知識証明生成部は、要求Qとブラインド復号結果と公開鍵と秘密鍵と共通参照情報を用いて、Groth-Sahai証明の非対話ゼロ知識証明を生成する。返信生成部は、ブラインド復号結果と非対話ゼロ知識証明から、返信Rを生成し、返信Rを受信装置へ送信する。秘密鍵記録部は、共通参照情報と暗号化データベースと秘密鍵を記録する。受信装置は、署名検証部と再ランダム化部と知識識別不可能証明生成部と要求生成部と非対話ゼロ知識証明検証部と復号部と要求記録部を備える。署名検証部は、暗号化データベースとインデックスξを入力とし、Waters双対署名の署名検証アルゴリズムを実行して、暗号文C1,...,CNに含まれる署名を検証し、暗号文Cj毎に各要素が同一の乱数から生成されていることを検証し、暗号文C1,...,CN全てについて署名が正しい署名であると判定され、暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Cξを出力する。再ランダム化部は、公開鍵と共通参照情報を用いて、暗号文Cξから、再ランダム化暗号文を生成する。知識識別不可能証明生成部は、暗号文Cξと再ランダム化暗号文と公開鍵と共通参照情報から、知識識別不可能証明および知識識別不可能証明検証手段で利用される係数θを生成する。要求生成部は、再ランダム化暗号文と知識識別不可能証明から、要求Qを生成し、要求Qおよびインデックスξから、Qprivを生成し、要求Qと係数θを送信装置に送信する。非対話ゼロ知識証明検証部は、返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムによって、非対話ゼロ知識証明を検証する。復号部は、非対話ゼロ知識証明が正しい場合に、Qprivと暗号文Cξと共通参照情報を用いて、ブラインド復号結果から、文書mξを計算して出力する。要求記録部は、共通参照情報と暗号化データベースと公開鍵と要求QとQprivを記録する。本発明の紛失通信システムは、暗号方式として、Boneh-FranklinのIDベース暗号を変形した変形Boneh-Franklin暗号を用いることで、乱数は1つの利用でありながら汎用的結合可能性を持たせることが可能となっている。したがって、本発明の紛失通信システムによれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。本明細書では、Nを2以上の整数、^をべき乗を示す記号とする。と表記されている場合、アルゴリズム内部で乱数を発生させてランダムに出力することを意味する。また、と表記されている場合、素数pを法とする整数環Zpからランダムに値を選択することを意味する。本発明では、Groth-Sahai証明を利用する。Groth-Sahai証明のアルゴリズム、簡単な説明は付録Cを参照されたい完全な詳細は、JGrothandASahaiEfficientNoninteractiveProofSystemsforBilinearGroupsInEUROCRYPT’08volume4965ofLectureNotesinComputerSciencepages415432Springer2008参照。双線形写像については付録Aを、Waters双対署名については付録B1を、変形Boneh-Franklin暗号については付録B2を参照されたい。まず、図1、図2を参照して、本発明の実施例1に係る紛失通信システム10の動作の概略を説明する。図1は本実施例に係る紛失通信システム10の構成を示すブロック図である。図2は本実施例に係る紛失通信システム10の動作を示すシーケンス図である。本実施例の紛失通信システム10は、システムパラメータ生成装置100、送信装置200、受信装置300からなる。システムパラメータ生成装置100は、セキュリティパラメータλを入力とし、共通参照情報crsを生成し、送信装置200および受信装置300に送信するS101。送信装置200は、文書m1,...,mNを入力とし、公開鍵pkと暗号文C1,...,CNを含む暗号化データベースTを生成し、暗号化データベースTを受信装置300に送信するS201。受信装置300は、暗号化データベースTとインデックスξを入力とし、再ランダム化暗号文dと知識識別不可能証明πを含む要求Qを生成し、送信装置200へ送信するS301。送信装置200は、要求Qを入力とし、ブラインド復号結果aと非対話ゼロ知識証明δを含む返信Rを生成し、受信装置300に送信するS202。受信装置300は、返信Rを入力とし、文書mξを出力するS302。次に、図3から図7を参照して、本発明の実施例1に係る紛失通信システム10の動作をさらに詳細に説明する。図3は本実施例のシステムパラメータ生成装置がシステムパラメータを生成する動作を示すフローチャートである。図4は本実施例の送信装置が暗号化データベースを生成する動作を示すフローチャートである。図5は本実施例の受信装置が要求を生成する動作を示すフローチャートである。図6は本実施例の送信装置が返信を生成する動作を示すフローチャートである。図7は本実施例の受信装置が復号する動作を示すフローチャートである。以下、実際に行われる手続きの順に説明してゆく。前述したように本実施例の紛失通信システム10はシステムパラメータ生成装置100、送信装置200、受信装置300からなる。システムパラメータ生成装置100は、双線形写像パラメータ生成部110と送信装置用パラメータ生成部120と受信装置用パラメータ生成部130と係数生成部140とシステムパラメータ生成部150を備える。双線形写像パラメータ生成部110は、セキュリティパラメータλを入力とし、λビットの素数pと、素数位数pの巡回乗法群GおよびGTと、前記巡回乗法群Gの生成元gと、双線形写像eを含む、双線形写像パラメータΓ:=p,G,GT,e,gを生成するS110。送信装置用パラメータ生成部120は、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の送信装置用パラメータGSSを生成するS120。受信装置用パラメータ生成部130は、Groth-Sahai証明のパラメータ設定アルゴリズムGS.SetupΓを実行して、Groth-Sahai証明の受信装置用パラメータGSRを生成するS130。係数生成部140は、0以上p-1以下の整数からランダムに冪指数ζおよびyhを選択し、g2:=g^ζおよびh:=g^yhを計算するS140。システムパラメータ生成部150は、双線形写像パラメータΓと送信装置用パラメータGSSと受信装置用パラメータGSRと係数g2および係数hから、共通参照情報crs:=Γ,GSS,GSR,g2hを生成し、共通参照情報crsを送信装置200および受信装置300へ送信するS150。送信装置200は、鍵対生成部210と鍵生成部215と署名生成部220と暗号文生成部225と暗号化データベース生成部230と秘密鍵記録部290を備える。鍵対生成部210は、Waters双対署名の鍵生成アルゴリズムW.GenΓを実行して、Waters双対署名の鍵対VK,SKを生成するS210。鍵生成部215は、0以上p-1以下のランダムな秘密鍵αを生成し、秘密鍵αと共通参照情報crsを用いて、g1:=g^αを計算し、鍵対VKと係数g1から、公開鍵pk:=g1,VKを生成するS215。署名生成部220は、文書m1,...,mNを入力とし、j=1,...,Nに対して、0以上p-1以下のランダムな整数ρjを選択し、Waters双対署名の署名生成アルゴリズムW.Signρjを実行して、乱数ρjに対する署名sigjを生成するS220。暗号文生成部225は、文書m1,...,mNと公開鍵pkと乱数ρjと署名sigjと鍵対VKに含まれる値uと共通参照情報crsから、変形Boneh-Franklin暗号の暗号文Cj=c1j,c2j,c3j,c4j,c5jをCj:=g1^ρj,h^ρj,mjeg,g2,sigj,u^ρjのように生成するS225。暗号化データベース生成部230は、公開鍵pkと暗号文C1,...,CNから、暗号化データベースT:=pk,C1,...,CNを生成し、暗号化データベースTを受信装置300に送信するS230。秘密鍵記録部290は、秘密鍵αを記録するS290。受信装置300は、署名検証部310と再ランダム化部315と知識識別不可能証明生成部320と要求生成部325と要求記録部390を備える。署名検証部310は、暗号化データベースTとインデックスξを入力とし、j=1,...,Nのすべてについて暗号文Cjに含まれる署名sigjを、Waters双対署名の署名検証アルゴリズムW.Vrfyを実行して、検証するS311。署名sigjのいずれかが正しい署名でないと判定されると停止するS3904。j=1,...,Nのすべてについて暗号文Cjに含まれるc1jとc2jが、eh,c1j=ec2j,g1を満たすことを検証するS312。いずれかが満たさないと判定されると停止するS3905。暗号文C1,...,CN全てについて署名sigjが正しい署名であると判定され、暗号文C1,...,CN全てについて暗号文Cj毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Cξを出力するS313。再ランダム化部315は、0以上p-1以下の整数からランダムに冪指数vを選択し、公開鍵pkと共通参照情報crsと暗号文Cξに含まれるc1ξを用いて、d:=c1ξg1^vおよびt:=g2^vを計算し、再ランダム化暗号文dを生成するS315。知識識別不可能証明生成部320は、暗号文Cξに含まれる署名sigξの生成に利用された0以上p-1以下のランダムな整数tagkと、Waters双対署名sigξの検証に利用された0以上p-1以下のランダムな整数tagcを用いて、sigξ\{tagk}:=ρ1,...,ρKはWaters双対署名からtagkを除いたものとして、θ:=1/tagc-tagkを生成し、暗号文Cξと再ランダム化暗号文dと公開鍵pkと共通参照情報crsを用いて、知識識別不可能証明πをにより生成するS320。なお、記法は共通参照情報GSの下で、コロン以降の等式を満たす知識W=w1,w2の非対話知識識別不可能証明を表す。括弧でくくられたw1,w2以外の情報は検証者に知られているものとする。要求生成部325は、再ランダム化暗号文dと知識識別不可能証明πから、要求Q:=d,πを生成し、要求Qとインデックスξと乱数vから、Qpriv:=Q,ξ,vを生成し、要求Qおよび係数θを送信装置200に送信するS325。要求記録部390は、要求QおよびQprivを記録するS390。送信装置200は、さらに、知識識別不可能証明検証部235とブラインド復号部240と非対話ゼロ知識証明生成部245と返信生成部250を備える。知識識別不可能証明検証部235は、要求Qを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSR,πを実行して、要求Qに含まれる知識識別不可能証明πを検証するS235。正しい証明でない場合は、停止するS2911。ブラインド復号部240は、知識識別不可能証明πが正しい場合に、秘密鍵αと共通参照情報crsを用いて、要求Qに含まれる再ランダム化暗号文dから、a:=ed,g2^1/αを計算し、ブラインド復号結果aを生成するS240。非対話ゼロ知識証明生成部245は、再ランダム化暗号文dとブラインド復号結果aと公開鍵pkと秘密鍵αと共通参照情報crsを用いて、Groth-Sahai証明の非対話ゼロ知識証明δをにより生成するS245。返信生成部250は、ブラインド復号結果aと非対話ゼロ知識証明δから、返信R:=a,δを生成し、返信Rを受信装置300へ送信するS250。受信装置300は、さらに、非対話ゼロ知識証明検証部330と復号部335を備える。非対話ゼロ知識証明検証部330は、返信Rを入力とし、Groth-Sahai証明の証明検証アルゴリズムGS.VrfyGSS,δ=1によって、非対話ゼロ知識証明δを検証するS330。正しい証明でない場合は、停止するS3911。復号部335は、非対話ゼロ知識証明δが正しい場合に、Qprivと暗号文Cξと共通参照情報crsを用いて、mξ:=c3ξeg,g2^v/aを計算して、ブラインド復号結果aから文書mξを出力するS335。このように、本実施例の紛失通信システム10は、暗号方式として、Boneh-FranklinのIDベース暗号を変形した変形Boneh-Franklin暗号を用いることで、乱数は1つの利用でありながら汎用的結合可能性を持たせることが可能となっている。したがって、本実施例の紛失通信システム10によれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。<本発明と従来技術の比較>次に、図8を参照して、本発明と従来技術との比較について説明する。図8は本発明の紛失通信システムと従来技術との違いを示す表である。図8は、左隅列に本明細書における非特許文献番号を記した。また、UCとは安全性が汎用的結合可能性を満たしていることを示す。q-hiddenLRSW仮定など、q-が接頭についている仮定は、暗号の分野でq-仮定と呼ばれ、標準的な暗号学的仮定であるRSA仮定、DBDH判定双線形Diffie-Hellman仮定、DLIN判定線形仮定に比べて安全性の根拠に信頼がおけない。πは送信装置が生成する知識識別不可能証明を表しており、|π|はその群要素の数を表している。知識識別不可能証明のサイズは表では同一として扱ったが厳密にはそれぞれのサイズは異なる。しかしこのサイズは暗号文のπ以外の群要素数に比例して大きくなるので提案方式のπのサイズは他のものと比べて大きくならない。他の方式と比べてDBDH仮定が必要になっているが、DBDH仮定はごく標準的な仮定であるので、安全性は信頼できる。非特許文献1、2の紛失通信システムでは、送信装置は線形暗号方式により暗号文u1^ρ1,u2^ρ2,g1^ρ1,g2^ρ2,ζ^ρ1ρ2mを生成し、群Gの要素であるu1^ρ1とu2^ρ2への署名を生成するか非特許文献1の方式、Zpの要素ρ1とρ2への署名を生成し非特許文献2の方式はこれに近い、これらを受信装置に送信している。つまり署名が少なくとも2つ必要になる。つまり線形暗号を利用する限り、複数の署名が必要になり暗号文サイズが大きくなってしまうことは避けられない。しかし線形暗号は汎用的結合可能性を持たせるために重要な役割を果たしており、他の暗号方式で代用可能かは自明ではない。本発明では変形Boneh-Franklin暗号を用いることで乱数は1つの利用でありながら、かつ汎用的結合可能性を維持することが可能となっている。これは以下の2つの理由による。まずパラメータとして余分にhを用意し乱数ρを用いてh^ρも暗号文に含めることによって暗号文の正しさをチェック可能にしている。次に、通常の暗号方式の場合、単純なパラメータを乱数によってランダム化することが普通であるが例えばパラメータΓ=p,g,G,GT,eに対して0以上p-1以下のランダムな整数ρを用いてg^ρを計算する、変形方式では公開鍵を乱数によってランダム化している公開鍵g1=g^αを0以上p-1以下のランダムな整数ρを用いてg1^ρを計算する。よって線形暗号を利用せずとも汎用的結合可能性を持たせることが可能となっている。<本発明と従来技術の比較おわり><付録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は効率的につまり多項式時間で計算可能である。詳しくはDBonehandMKFranklinIdentityBasedEncryptionfromtheWeilPairingInCRYPTO’01volume2139ofLectureNotesinComputerSciencepages213229Springer2001や黒澤馨著現代暗号への招待サイエンス社の13章を参照されたい。<付録A:ペアリングおわり><付録B:ディジタル署名>[B1:Waters双対署名]Watersが提案した署名を説明するBWatersDualSystemEncryptionRealizingFullySecureIBEandHIBEunderSimpleAssumptionsInCRYPTO’09volume5677ofLectureNotesinComputerSciencepages619636Springer2009。本明細書ではこれをWaters双対署名と呼ぶ。鍵生成W.GenΓ:セキュリティパラメータλとΓ=p,G,GT,e,gを入力とし、生成元v,v1,v2,w,u,hを群Gからランダムに選び、0以上p-1以下のランダムな整数a1,a2,b,αを選ぶ。τ1:=vv1^a1,τ2:=vv2^a2とし、検証鍵と秘密鍵をVK:=g,g^b,g^a1,g^a2,g^ba1,g^ba2,τ1,τ2,τ1^b,τ2^b,w,u,h,eg,g^αa1b,SK:=VK,g^α,g^αa1,v,v1,v2とする。署名生成W.SignSK,M:0以上p-1以下のランダムな整数r1,r2,z1,z2,tagkを選び、r:=r1r2とする。署名をσ1:=g^αa1v^r,σ2:=g^-αv1^rg^z1,σ3:=g^b^-z1,σ4:=v2^rg^z2,σ5:=g^bg^-z2,σ6:=g^b^r2,σ7:=g^r1,σK:=u^Mw^tagkh^r1と生成し、sig:=σ1,...,σ7,σK,tagkを出力する。署名検証W.VrfyVK,M,sig:VK,Mと署名σを入力とし、0以上p-1以上のランダムな整数s1,s2,t,tagcを選び、s:=s1s2とする。次にV1:=gb^s,V2:=g^ba1^s1,V3:=g^a1^s1,V4:=g^ba2^s2,V5:=g^a2^s2,V6:=τ1^s1τ2^s2,V7:=τ1^b^s1τ2^b^s2w^-t,E1:=u^Mw^tagch^t,E2:=g^tを生成し、もしtagc-tagk≠0ならば、を確認し、これが成立するときかつそのときに限り正当な署名とする。なお、θ:=1/tagc-tagkと置き、u,q∈についてu^M,q^Mが与えられたとき、上記の検証式に加えてeu^M、q=eq^M,uを検証するアルゴリズムをと書くことにする。[B2:変形Boneh-Franklin暗号]本発明の中で用いた暗号方式はBoneh-FranklinのIDベース暗号DBonehandMKFranklinIdentityBasedEncryptionfromtheWeilPairingSIAMJComput325866152003を変形したものである。SetupΓ:0以上p-1以下のランダムな整数αを選びg1:=g^αを計算する。またg2,hを群Gからランダムに選ぶ。公開鍵をPK:=g,g1,g2,h,秘密鍵をMK:=g2^1/αとするαそのものが秘密鍵でもよい。EncPK:0以上p-1以下のランダムな整数rを選び、暗号文C:=C1,C2,C3:=eg,g2^rM,g1^r,h^rを計算する。DecPK:M:=C1/eC2,g2^1/αを計算して復号する。F-署名:選択メッセージ攻撃に対してF-セキュアと呼ばれるより強い安全性の定義を考える。Fを効率的に計算可能な全単射であるものとする。署名スキームSig=Sig.{Gen,Sign,Vrfy}は、以下のゲームによるアドバンテージが無視できるほど小さい場合には、選択メッセージ攻撃下においてF-セキュアと呼ばれる。手順1セットアップ:挑戦者は、を発生させてvkを攻撃者に送る。手順2質問:攻撃者はメッセージMi∈Mを挑戦者に送り、挑戦者はを返信する。これらの質問はi=1~Nまで適応的に挑戦者に送信される。ここでを攻撃者からの質問であるメッセージのセットM1,...,MK∈Mを表すものとする。手順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は、変数{xi}i,{yj}j∈Gi∈[m],j∈[n]と、定数{aq}q,{bq}q∈Gq∈[Q],t∈GT,{αq,i},q,i,{βq,j}q,j∈Zpと、G内の値であるコミットメント{ci}i,{dj}jにより構成される。GrothとSahaiは、非対話知識証明NIPKの構築を以下の式で表した。この証明πはコミットメントc1,...,cm,d1,...,dnを含む。GrothとSahaiは、これらのコミットメントからペアリング生成式を満足する値x1,...,xm,y1,...,ynを開くことのできる効率的な抽出機を提供する。ここで、CamenischとStadlerの記法JCamenischandMStadlerEfficientGroupSignatureSchemesforLargeGroupsInCRYPTO’97volume1294ofLectureNotesinComputerSciencepages410424Springer1997、例えば、を用いる。本システムでは、証明者は同形のコミットメントスキームと共通参照情報CRSとを用いてwitness証拠、群の元を遂行する。共通参照情報CRSには2つのタイプが存在する。1つのタイプは完全拘束コミットメントスキームを、もう1つのタイプは完全秘匿コミットメントスキームを与える。これらの2つのタイプは計算量的識別不可能である。証明システム:証明システムは以下のアルゴリズムにより構成される。GS.SetupΓ:入力を実行して、出力である証明システムの共通参照情報GSを生成する。共通参照情報GSは、コミットメントスキームの共通参照情報crsGSCを含む。GS:ProveGS,S,W:ステートメントSと、証拠W∈{xi}iとを入力とし、証明πを出力する。GS.VrfyGS,π:証明πを入力とし、照明を検証し、正当であれば1を出力し、それ以外は0を出力する。GS.ExtSetupΓ:共通参照情報GSその分布は通常の共通参照情報と一致すると、正当な証拠を導出するためのトラップドアtdextとを出力する。GS.ExtractGS,tdext,π:証明πと、トラップドアtdextとを入力とし、各コミットメントCiから抽出値xiを抽出して等式を満たす証拠W∈{xi}iを出力する。GS.SimSetupΓ:GS.SetupΓの出力である通常の共通参照情報と計算量的識別不可能な共通参照情報GS’と、トラップドアtdsimを出力する。GS.SimProveGS’,tdsim,S:共通参照情報GS’と、トラップドアtdsimとを入力とし、GS.VrfyGS’,π=1を満たすステートメントSの証明πを出力する。セキュリティ特性:本証明システムは以下の特性を満足する。正当性:全てのについて、GS.VfryGS,π→1を満たす。抽出性:および、証明πについて、GS.VfryGS,π→1である場合に、証拠W:=GS.ExtractGS,tdext,πはステートメントSを確率1で満足する。共通参照情報CRSの識別不可能性:と、について、を満たす。構成可能な証拠の識別不可能性:全てのPPT攻撃者Αについて、が成立する。Groth-Sahai証明システムは、制限されたステートメントのクラスΣZKはこのクラスを意味するにおける構成可能なゼロ知識証明を提供する。構成可能なゼロ知識:全てのPPT攻撃者Αについて、が成立する。F-抽出可能非対話知識証明:Groth-Sahai証明システムにおいては、非対話知識証明NIWIまたはNIZKから、トラップドアtdextを使うことにより証拠を抽出できる。しかしながら、この証明システムにおいては、群の元のみがコミットできるため、群Gの元を抽出できるのみである。従って、本証明システムにおいてメッセージm∈Zpを選択して、gm∈Gをコミットし、証拠であるgmを用いて、非対話証明を生成する場合には、gmのみを抽出することができるこれはm自身でなく、関数Fm:=gmの出力であることに注意する。この性質から、Groth-Sahai証明システムはF-抽出可能性を備えると言われる。定理2:DLIN仮定が成り立つならば、Groth-Sahai証明システムは効率的にインスタンス化できる。<付録C:Groth-Sahai証明おわり><付録D:暗号学的仮定>素数位数pの巡回群Gを考える。gを群Gの生成元とする。BMSetupは標準的な双線形写像についての群生成アルゴリズムで、セキュリティパラメータλを入力にとってp,G,GT,g,eを生成する。[D1:判定線形問題]判定線形問題とはG,GT,p,g,eとI:=g,f,v,g^x,f^yおよびTが与えられたときx,yは0以上p-1以下のランダムな整数、TがランダムなGの元かT=vxy∈Gであるかどうかを判定する問題である。この優位性はで定義される。定義3判定線形仮定:判定線形仮定が成立しているとは、判定線形問題が困難である。つまり、どのような攻撃者Αに対しても、が無視できる。[D2:判定双線形Diffie-Hellman問題]判定双線形Diffie-Hellman問題とはG,GT,p,g,eとI:=g,g^x,g^y,g^zおよびTが与えられたときx,y,zは0以上p-1以下のランダムな整数、TがランダムなGTの元かT=eg,gxyz∈GTであるかどうかを判定する問題である。この優位性はで定義される。定義4判定双線形Diffie-Hellman仮定:判定双線形Diffie-Hellman仮定が成立しているとは、判定双線形Diffie-Hellman問題が困難である。つまり、どのような攻撃者Αに対しても、が無視できる。<付録D:暗号学的仮定おわり>また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"