(57)【特許請求の範囲】
【請求項１】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置は、
入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、前記巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータ、受信装置用パラメータを生成し、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記生成元から設定した第１係数群から共通参照情報ｃｒｓを生成するシステムパラメータ生成部と、
前記共通参照情報ｃｒｓを送信装置と受信装置に送信するｃｒｓ送信部とを備え、
前記送信装置は、
文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、前記共通参照情報ｃｒｓとを入力とし、Ｗａｔｅｒｓ双対署名の第１鍵対、第２鍵対を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成し、秘密鍵を生成し、前記第１鍵対、前記第２鍵対、前記第３鍵対を用いて公開鍵を生成し、Ｗａｔｅｒｓ双対署名の第１署名、第２署名を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３署名を生成し、前記文書（ｍ１，…，ｍＮ）、前記第１鍵対に含まれる値、前記第２鍵対に含まれる値、前記共通参照情報ｃｒｓ、前記第１署名、前記第２署名、前記第３署名を用いて、暗号文Ｃ１，…，ＣＮを生成し、前記公開鍵と、前記暗号文Ｃ１，…，ＣＮとから暗号化データベースを生成する暗号化データベース生成部と、
前記暗号化データベースを前記受信装置に送信するＴ送信部と、
前記暗号化データベースと、前記秘密鍵とを記憶するＴ記憶部と、
前記共通参照情報ｃｒｓ、前記暗号化データベース、前記秘密鍵、要求Ｑを入力とし、知識識別不可能証明を検証し、前記知識識別不可能証明が正しい場合に、前記秘密鍵、前記要求Ｑを用いてブラインド復号を実行し、前記暗号化データベース、前記共通参照情報ｃｒｓ、前記要求Ｑを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成し、前記非対話ゼロ知識証明を含む返信Ｒを生成する返信生成部と、
前記返信Ｒを前記受信装置に送信するＲ送信部と、を備え、
前記受信装置は、
前記暗号化データベースと、前記共通参照情報ｃｒｓと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、前記署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξ、前記共通参照情報ｃｒｓを用いて再ランダム化を実行し、前記暗号文Ｃξ、前記共通参照情報ｃｒｓ、前記公開鍵を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成し、前記知識識別不可能証明を含む要求Ｑ、と、前記要求Ｑおよびインデックスξを含むＱｐｒｉｖを生成する要求生成部と、
前記要求Ｑを前記送信装置に送信するＱ送信部と、
前記要求ＱとＱｐｒｉｖとを記憶するＱ記憶部と、
前記返信Ｒと、前記Ｑｐｒｉｖと、前記暗号化データベースと、前記共通参照情報ｃｒｓとを入力とし、前記非対話ゼロ知識証明を検証し、前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖ、前記暗号文Ｃ１，…，ＣＮ、共通参照情報ｃｒｓを用いて、前記暗号文Ｃξから文書ｍξを計算して出力する文書取得部と、を備えること
を特徴とする紛失通信システム。
【請求項２】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置はシステムパラメータ生成部と、ｃｒｓ送信部とを備え、
前記システムパラメータ生成部は、
入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、当該巡回乗法群の生成元と、双線形写像とを組み合わせて双線形写像パラメータを生成する双線形写像パラメータ生成手段と、
前記双線形写像パラメータを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して送信装置用パラメータを生成する送信装置用パラメータ生成手段と、
前記双線形写像パラメータを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して受信装置用パラメータを生成する受信装置用パラメータ生成手段と、
前記生成元から第１係数群を設定する第１係数設定手段と、
前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記第１係数群から共通参照情報ｃｒｓを生成するシステムパラメータ生成手段と、を備え、
前記ｃｒｓ送信部は、前記共通参照情報ｃｒｓを送信装置と受信装置に送信し、
前記送信装置は暗号化データベース生成部と、Ｔ送信部と、Ｔ記憶部と、返信生成部と、Ｒ送信部と、を備え、
前記暗号化データベース生成部は、
前記双線形写像パラメータを入力とし、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行してＷａｔｅｒｓ双対署名の第１鍵対を生成する第１Ｗａｔｅｒｓ鍵対生成手段と、
前記双線形写像パラメータを入力とし、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行してＷａｔｅｒｓ双対署名の第２鍵対を生成する第２Ｗａｔｅｒｓ鍵対生成手段と、
前記双線形写像パラメータと秘密鍵生成手段が設定した係数とを入力とし、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の鍵生成アルゴリズムを実行してＢｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成するＢＢ鍵対生成手段と、
秘密鍵を生成し、前記第１係数群を用いて係数を設定する秘密鍵生成手段と、
前記秘密鍵生成手段が設定した係数、前記第１鍵対、前記第２鍵対、前記第３鍵対を用いて公開鍵を生成する公開鍵生成手段と、
前記秘密鍵生成手段が設定した係数を用いて第２係数群を設定する第２係数設定手段と、
前記第２係数群を入力とし、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して第１署名を生成する第１Ｗａｔｅｒｓ署名生成手段と、
前記第２係数群を入力とし、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して第２署名を生成する第２Ｗａｔｅｒｓ署名生成手段と、
前記第２係数群を入力とし、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名生成アルゴリズムを実行して第３署名を生成するＢＢ署名生成手段と、
文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、前記第１鍵対に含まれる値、前記第２鍵対に含まれる値、前記第１係数群、前記第２係数群、前記第１署名、前記第２署名、前記第３署名を入力とし、暗号文Ｃ１，…，ＣＮを生成する暗号文生成手段と、
前記公開鍵と、前記暗号文Ｃ１，…，ＣＮとを入力とし、暗号化データベースを生成する暗号化データベース生成手段と、を備え、
前記Ｔ送信部は、前記暗号化データベースを前記受信装置に送信し、
前記Ｔ記憶部は、前記暗号化データベースと、前記秘密鍵とを記憶し、
前記返信生成部は、
Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明と、前記受信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、前記知識識別不可能証明を検証する知識識別不可能証明検証手段と、
前記知識識別不可能証明が正しい場合に、前記秘密鍵と、再ランダム化手段が設定した係数とを入力とし、係数を設定するブラインド復号手段と、
前記ブラインド復号手段が設定した係数、前記公開鍵、前記再ランダム化手段が設定した係数、前記第１係数群、前記共通参照情報ｃｒｓを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明生成アルゴリズムを実行して、非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成手段と、
前記ブラインド復号手段が設定した係数と、前記非対話ゼロ知識証明とを組にして返信Ｒを生成する返信生成手段と、を備え、
前記Ｒ送信部は、前記返信Ｒを前記受信装置に送信し、
前記受信装置は要求生成部と、Ｑ送信部と、Ｑ記憶部と、文書取得部と、を備え、
前記要求生成部は、
前記暗号文Ｃ１，…，ＣＮと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名をＷａｔｅｒｓ双対署名の署名検証アルゴリズムおよび、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名検証アルゴリズムを実行して検証し、前記暗号文Ｃ１，…，ＣＮに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξを出力する署名検証手段と、
前記暗号文Ｃξと、前記第１係数群とを入力とし、係数を設定する再ランダム化手段と、
前記再ランダム化手段が設定した係数と、前記暗号文Ｃξと、前記双線形写像と、前記公開鍵と、前記第一係数群と、前記受信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成する知識識別不可能証明生成手段と、
前記再ランダム化手段が設定した係数と、前記知識識別不可能証明と、前記インデックスξとを入力とし、要求Ｑ、Ｑｐｒｉｖを生成する要求生成手段と、を備え、
前記Ｑ送信部は、前記要求Ｑを前記送信装置に送信し、
前記Ｑ記憶部は、前記要求ＱとＱｐｒｉｖとを記憶し、
前記文書取得部は、
前記返信Ｒと、前記送信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証するゼロ知識証明検証手段と、
前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと、前記第１係数群と、前記暗号文Ｃ１，…，ＣＮと、前記ブラインド復号手段が生成した係数とを入力とし、前記暗号文Ｃξから文書ｍξを計算して出力する文書生成手段と、を備えること
を特徴とする紛失通信システム。
【請求項３】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置はシステムパラメータ生成部と、ｃｒｓ送信部とを備え、
前記システムパラメータ生成部は、
入力１λに対して、λビットの素数ｐ、素数位数ｐの巡回乗法群であるＧおよびＧＴ、双線形写像ｅ、群Ｇの生成元ｇよりなる双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成手段と、
【数５９】
0005572580.tif 000060
共通参照情報ｃｒｓ：＝（Γ、ＧＳＳ、ＧＳＲ、ｇ１、ｇ２、ζ）を生成するシステムパラメータ生成手段と、を備え、
前記ｃｒｓ送信部は、前記共通参照情報ｃｒｓを送信装置と受信装置に送信し、
前記送信装置は暗号化データベース生成部と、Ｔ送信部と、Ｔ記憶部と、返信生成部と、Ｒ送信部と、を備え、
前記暗号化データベース生成部は、
【数６０】
0005572580.tif 000061
前記公開鍵ｐｋと、前記暗号文Ｃ１，…，ＣＮとを入力とし、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成する暗号化データベース生成手段と、を備え、
前記Ｔ送信部は、前記暗号化データベースＴを前記受信装置に送信し、
前記Ｔ記憶部は、前記暗号化データベースＴと、前記秘密鍵ｓｋ：＝（ｘ１、ｘ２）とを記憶し、
前記返信生成部は
Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明πと、前記パラメータＧＳＲとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記知識識別不可能証明πを検証する知識識別不可能証明検証手段と、
【数６１】
0005572580.tif 000062
前記Ｒ送信部は、前記返信Ｒを前記受信装置に送信し、
前記受信装置は要求生成部と、Ｑ送信部と、Ｑ記憶部と、文書取得部と、を備え、
前記要求生成部は、
前記暗号文Ｃ１，…，ＣＮと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名をＷａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙおよび、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名検証アルゴリズムＢＢ．Ｖｒｆｙを実行して検証し、前記暗号文Ｃ１，…，ＣＮに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξを出力する署名検証手段と、
【数６２】
0005572580.tif 000063
前記Ｑ送信部は、前記要求Ｑを前記送信装置に送信し、
前記Ｑ記憶部は、前記要求ＱとＱｐｒｉｖとを記憶し、
前記文書取得部は、
前記返信Ｒと、前記パラメータＧＳＳとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証するゼロ知識証明検証手段と、
【数６３】
0005572580.tif 000064
を特徴とする紛失通信システム。
【請求項４】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
前記システムパラメータ生成装置は、
入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、前記巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータ、受信装置用パラメータを生成し、前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記生成元から設定した第１係数群から共通参照情報ｃｒｓを生成するシステムパラメータ生成ステップと、
前記共通参照情報ｃｒｓを送信装置と受信装置に送信するｃｒｓ送信ステップとを実行し、
前記送信装置は、
文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、前記共通参照情報ｃｒｓとを入力とし、Ｗａｔｅｒｓ双対署名の第１鍵対、第２鍵対を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成し、秘密鍵を生成し、前記第１鍵対、前記第２鍵対、前記第３鍵対を用いて公開鍵を生成し、Ｗａｔｅｒｓ双対署名の第１署名、第２署名を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３署名を生成し、前記文書（ｍ１，…，ｍＮ）、前記第１鍵対に含まれる値、前記第２鍵対に含まれる値、前記共通参照情報ｃｒｓ、前記第１署名、前記第２署名、前記第３署名を用いて、暗号文Ｃ１，…，ＣＮを生成し、前記公開鍵と、前記暗号文Ｃ１，…，ＣＮとから暗号化データベースを生成する暗号化データベース生成ステップと、
前記暗号化データベースを前記受信装置に送信するＴ送信ステップと、
前記暗号化データベースと、前記秘密鍵とを記憶するＴ記憶ステップと、
前記共通参照情報ｃｒｓ、前記暗号化データベース、前記秘密鍵、要求Ｑを入力とし、知識識別不可能証明を検証し、前記知識識別不可能証明が正しい場合に、前記秘密鍵、前記要求Ｑを用いてブラインド復号を実行し、前記暗号化データベース、前記共通参照情報ｃｒｓ、前記要求Ｑを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成し、前記非対話ゼロ知識証明を含む返信Ｒを生成する返信生成ステップと、
前記返信Ｒを前記受信装置に送信するＲ送信ステップと、を実行し、
前記受信装置は、
前記暗号化データベースと、前記共通参照情報ｃｒｓと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、前記署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξ、前記共通参照情報ｃｒｓを用いて再ランダム化を実行し、前記暗号文Ｃξ、前記共通参照情報ｃｒｓ、前記公開鍵を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成し、前記知識識別不可能証明を含む要求Ｑ、と、前記要求Ｑおよびインデックスξを含むＱｐｒｉｖを生成する要求生成ステップと、
前記要求Ｑを前記送信装置に送信するＱ送信ステップと、
前記要求ＱとＱｐｒｉｖとを記憶するＱ記憶ステップと、
前記返信Ｒと、前記Ｑｐｒｉｖと、前記暗号化データベースと、前記共通参照情報ｃｒｓとを入力とし、前記非対話ゼロ知識証明を検証し、前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖ、前記暗号文Ｃ１，…，ＣＮ、共通参照情報ｃｒｓを用いて、前記暗号文Ｃξから文書ｍξを計算して出力する文書取得ステップと、を実行すること
を特徴とする紛失通信方法。
【請求項５】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
前記システムパラメータ生成装置はシステムパラメータ生成ステップと、ｃｒｓ送信ステップとを実行し、
前記システムパラメータ生成ステップは、
入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、当該巡回乗法群の生成元と、双線形写像とを組み合わせて双線形写像パラメータを生成する双線形写像パラメータ生成サブステップと、
前記双線形写像パラメータを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して送信装置用パラメータを生成する送信装置用パラメータ生成サブステップと、
前記双線形写像パラメータを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して受信装置用パラメータを生成する受信装置用パラメータ生成サブステップと、
前記生成元から第１係数群を設定する第１係数設定サブステップと、
前記双線形写像パラメータ、前記送信装置用パラメータ、前記受信装置用パラメータ、前記第１係数群から共通参照情報ｃｒｓを生成するシステムパラメータ生成サブステップと、を有し、
前記ｃｒｓ送信ステップは、前記共通参照情報ｃｒｓを送信装置と受信装置に送信し、
前記送信装置は暗号化データベース生成ステップと、Ｔ送信ステップと、Ｔ記憶ステップと、返信生成ステップと、Ｒ送信ステップと、を実行し、
前記暗号化データベース生成ステップは、
前記双線形写像パラメータを入力とし、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行してＷａｔｅｒｓ双対署名の第１鍵対を生成する第１Ｗａｔｅｒｓ鍵対生成サブステップと、
前記双線形写像パラメータを入力とし、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行してＷａｔｅｒｓ双対署名の第２鍵対を生成する第２Ｗａｔｅｒｓ鍵対生成サブステップと、
前記双線形写像パラメータと秘密鍵生成サブステップが設定した係数とを入力とし、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の鍵生成アルゴリズムを実行してＢｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成するＢＢ鍵対生成サブステップと、
秘密鍵を生成し、前記第１係数群を用いて係数を設定する秘密鍵生成サブステップと、
前記秘密鍵生成サブステップが設定した係数、前記第１鍵対、前記第２鍵対、前記第３鍵対を用いて公開鍵を生成する公開鍵生成サブステップと、
前記秘密鍵生成サブステップが設定した係数を用いて第２係数群を設定する第２係数設定サブステップと、
前記第２係数群を入力とし、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して第１署名を生成する第１Ｗａｔｅｒｓ署名生成サブステップと、
前記第２係数群を入力とし、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して第２署名を生成する第２Ｗａｔｅｒｓ署名生成サブステップと、
前記第２係数群を入力とし、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名生成アルゴリズムを実行して第３署名を生成するＢＢ署名生成サブステップと、
文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、前記第１鍵対に含まれる値、前記第２鍵対に含まれる値、前記第１係数群、前記第２係数群、前記第１署名、前記第２署名、前記第３署名を入力とし、暗号文Ｃ１，…，ＣＮを生成する暗号文生成サブステップと、
前記公開鍵と、前記暗号文Ｃ１，…，ＣＮとを入力とし、暗号化データベースを生成する暗号化データベース生成サブステップと、を有し、
前記Ｔ送信ステップは、前記暗号化データベースを前記受信装置に送信し、
前記Ｔ記憶ステップは、前記暗号化データベースと、前記秘密鍵とを記憶し、
前記返信生成ステップは、
Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明と、前記受信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、前記知識識別不可能証明を検証する知識識別不可能証明検証サブステップと、
前記知識識別不可能証明が正しい場合に、前記秘密鍵と、再ランダム化サブステップが設定した係数とを入力とし、係数を設定するブラインド復号サブステップと、
前記ブラインド復号サブステップが設定した係数、前記公開鍵、前記再ランダム化サブステップが設定した係数、前記第１係数群、前記共通参照情報ｃｒｓを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明生成アルゴリズムを実行して、非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成サブステップと、
前記ブラインド復号サブステップが設定した係数と、前記非対話ゼロ知識証明とを組にして返信Ｒを生成する返信生成サブステップと、を有し、
前記Ｒ送信ステップは、前記返信Ｒを前記受信装置に送信し、
前記受信装置は要求生成ステップと、Ｑ送信ステップと、Ｑ記憶ステップと、文書取得ステップと、を実行し、
前記要求生成ステップは、
前記暗号文Ｃ１，…，ＣＮと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名をＷａｔｅｒｓ双対署名の署名検証アルゴリズムおよび、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名検証アルゴリズムを実行して検証し、前記暗号文Ｃ１，…，ＣＮに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξを出力する署名検証サブステップと、
前記暗号文Ｃξと、前記第１係数群とを入力とし、係数を設定する再ランダム化サブステップと、
前記再ランダム化サブステップが設定した係数と、前記暗号文Ｃξと、前記双線形写像と、前記公開鍵と、前記第一係数群と、前記受信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成する知識識別不可能証明生成サブステップと、
前記再ランダム化サブステップが設定した係数と、前記知識識別不可能証明と、前記インデックスξとを入力とし、要求Ｑ、Ｑｐｒｉｖを生成する要求生成サブステップと、を有し、
前記Ｑ送信ステップは、前記要求Ｑを前記送信装置に送信し、
前記Ｑ記憶ステップは、前記要求ＱとＱｐｒｉｖとを記憶し、
前記文書取得ステップは、
前記返信Ｒと、前記送信装置用パラメータとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証するゼロ知識証明検証サブステップと、
前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと、前記第１係数群と、前記暗号文Ｃ１，…，ＣＮと、前記ブラインド復号サブステップが生成した係数とを入力とし、前記暗号文Ｃξから文書ｍξを計算して出力する文書生成サブステップと、を有すること
を特徴とする紛失通信方法。
【請求項６】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
前記システムパラメータ生成装置はシステムパラメータ生成ステップと、ｃｒｓ送信ステップとを実行し、
前記システムパラメータ生成ステップは、
入力１λに対して、λビットの素数ｐ、素数位数ｐの巡回乗法群であるＧおよびＧＴ、双線形写像ｅ、群Ｇの生成元ｇよりなる双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成サブステップと、
【数６４】
0005572580.tif 000065
共通参照情報ｃｒｓ：＝（Γ、ＧＳＳ、ＧＳＲ、ｇ１、ｇ２、ζ）を生成するシステムパラメータ生成サブステップと、を有し、
前記ｃｒｓ送信ステップは、前記共通参照情報ｃｒｓを送信装置と受信装置に送信し、
前記送信装置は暗号化データベース生成ステップと、Ｔ送信ステップと、Ｔ記憶ステップと、返信生成ステップと、Ｒ送信ステップと、を実行し、
前記暗号化データベース生成ステップは、
【数６５】
0005572580.tif 000066
前記公開鍵ｐｋと、前記暗号文Ｃ１，…，ＣＮとを入力とし、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成する暗号化データベース生成サブステップと、を有し、
前記Ｔ送信ステップは、前記暗号化データベースＴを前記受信装置に送信し、
前記Ｔ記憶ステップは、前記暗号化データベースＴと、前記秘密鍵ｓｋ：＝（ｘ１、ｘ２）とを記憶し、
前記返信生成ステップは
Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明πと、前記パラメータＧＳＲとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記知識識別不可能証明πを検証する知識識別不可能証明検証サブステップと、
【数６６】
0005572580.tif 000067
前記Ｒ送信ステップは、前記返信Ｒを前記受信装置に送信し、
前記受信装置は要求生成ステップと、Ｑ送信ステップと、Ｑ記憶ステップと、文書取得ステップと、を実行し、
前記要求生成ステップは、
前記暗号文Ｃ１，…，ＣＮと、インデックスξとを入力とし、前記暗号文Ｃ１，…，ＣＮに含まれる署名をＷａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙおよび、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名検証アルゴリズムＢＢ．Ｖｒｆｙを実行して検証し、前記暗号文Ｃ１，…，ＣＮに含まれる署名が正しい場合に、前記インデックスξに対応する暗号文Ｃξを出力する署名検証サブステップと、
【数６７】
0005572580.tif 000068
前記Ｑ送信ステップは、前記要求Ｑを前記送信装置に送信し、
前記Ｑ記憶ステップは、前記要求ＱとＱｐｒｉｖとを記憶し、
前記文書取得ステップは、
前記返信Ｒと、前記パラメータＧＳＳとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証するゼロ知識証明検証サブステップと、
【数６８】
0005572580.tif 000069
を特徴とする紛失通信方法。
【請求項７】
請求項４から６の何れかに記載の紛失通信方法を実行すべき指令をコンピュータに対してするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電気通信システムでデータベースにおける情報検索などに利用される紛失通信システム、紛失通信方法、およびプログラムに関する。
【背景技術】
【０００２】
適応的紛失通信とは、ある受信者が文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）を持つある送信者と通信を行い、受信者が指定した番号ｂに対応する文書ｍｂを得る方法である．送信者は番号ｂについて一切知ることができない。受信者は指定した文書以外を得ることはできない。かつ上記の通信を適応的に何度も繰り返すことができる。この技術は安全なデータベース検索（例えば特許庁データベースにおける特許文献の検索）などに応用可能である。従来、汎用的結合可能性と呼ばれる高い安全性を達成している代表的な適応的紛失通信に非特許文献１、２がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】M. Green and S. Hohenberger. Universally Composable Adaptive Oblivious Transfer. In ASIACRYPT’08, volume 5350 of Lecture Notes in Computer Science, pages 179-197. Springer, 2008.
【非特許文献２】A. Rial, M. Kohlweiss, and B. Preneel. Universally Composable Adaptive Priced Oblivious Transfer. In Pairing, volume 5671 of Lecture Notes in Computer Science, pages 231-247. Springer, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１では群の要素に対して署名が可能な署名方式を利用しているため非常に特殊な暗号学仮定を必要とし、安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。また、非特許文献２では上記のような署名方式は利用しないが、値段付き適応的紛失通信という、機能追加した方式を用いる。このため上記とは別の強い暗号学的仮定が必要になり、やはり安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。非特許文献１、２に代表される既存方式においては、汎用的結合可能性という最強の安全性を達成しているものの、適応的紛失通信のプロトコルは非標準的な（強い）暗号学的仮定を必要とするものしかないことが問題であった。
【０００５】
これに対して、標準的な（弱い）暗号学的仮定だけを用いて汎用的結合可能性をもつ適応的紛失通信を実現するために、標準的な暗号学的仮定を用いた署名方式を組み合わせて、適応的紛失通信のプロトコルを構築することが考えられる。しかしながら、単にこれらの標準的な（弱い）暗号学的仮定による署名方式を組み合わせただけでは、適応的紛失通信として機能するとはいえ、汎用的結合可能性の証明が容易でないことが問題であった。また、標準的な暗号学的仮定を用いた署名方式のひとつとして、Ｗａｔｅｒｓ署名が知られているが、Ｗａｔｅｒｓ署名は群要素に対して署名することが出来ないため、適応的紛失通信に用いる署名としては適さないと考えられており、適応的紛失通信へのＷａｔｅｒｓ署名の組み込みは困難であった。
【０００６】
そこで、本発明では、標準的な暗号学的仮定だけを用い、かつ汎用的結合可能性をもつことが証明可能な適応的紛失通信を実現できる紛失通信システムを提供する。
【課題を解決するための手段】
【０００７】
本発明の紛失通信システムは、システムパラメータ生成装置、送信装置、受信装置からなる。システムパラメータ生成装置は、システムパラメータ生成部と、ｃｒｓ送信部とを備える。
【０００８】
システムパラメータ生成部は、入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータ、受信装置用パラメータを生成し、双線形写像パラメータ、送信装置用パラメータ、受信装置用パラメータ、生成元から設定した第１係数群から共通参照情報ｃｒｓを生成する。ｃｒｓ送信部は、共通参照情報ｃｒｓを送信装置と受信装置に送信する。
【０００９】
送信装置は、暗号化データベース生成部と、Ｔ送信部と、Ｔ記憶部と、返信生成部と、Ｒ送信部と、を備える。暗号化データベース生成部は、文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、共通参照情報ｃｒｓとを入力とし、Ｗａｔｅｒｓ双対署名の第１鍵対、第２鍵対を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成し、秘密鍵を生成し、第１鍵対、第２鍵対、第３鍵対を用いて公開鍵を生成し、Ｗａｔｅｒｓ双対署名の第１署名、第２署名を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３署名を生成し、文書（ｍ１，…，ｍＮ）、第１鍵対に含まれる値、第２鍵対に含まれる値、共通参照情報ｃｒｓ、第１署名、第２署名、第３署名を用いて、暗号文Ｃ１，…，ＣＮを生成し、公開鍵と、暗号文Ｃ１，…，ＣＮとから暗号化データベースを生成する。Ｔ送信部は、暗号化データベースを受信装置に送信する。Ｔ記憶部は、暗号化データベースと、秘密鍵とを記憶する。返信生成部は、共通参照情報ｃｒｓ、暗号化データベース、秘密鍵、要求Ｑを入力とし、知識識別不可能証明を検証し、知識識別不可能証明が正しい場合に、秘密鍵、要求Ｑを用いてブラインド復号を実行し、暗号化データベース、共通参照情報ｃｒｓ、要求Ｑを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成し、非対話ゼロ知識証明を含む返信Ｒを生成する。Ｒ送信部は、返信Ｒを受信装置に送信する。
【００１０】
受信装置は、要求生成部と、Ｑ送信部と、Ｑ記憶部と、文書取得部と、を備える。要求生成部は、暗号化データベースと、共通参照情報ｃｒｓと、インデックスξとを入力とし、暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、署名が正しい場合に、インデックスξに対応する暗号文Ｃξ、共通参照情報ｃｒｓを用いて再ランダム化を実行し、暗号文Ｃξ、共通参照情報ｃｒｓ、公開鍵を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成し、知識識別不可能証明を含む要求Ｑ、と、要求Ｑおよびインデックスξを含むＱｐｒｉｖを生成する。Ｑ送信部は、要求Ｑを送信装置に送信する。Ｑ記憶部は、要求ＱとＱｐｒｉｖとを記憶する。文書取得部は、返信Ｒと、Ｑｐｒｉｖと、暗号化データベースと、共通参照情報ｃｒｓとを入力とし、非対話ゼロ知識証明を検証し、非対話ゼロ知識証明が正しい場合に、Ｑｐｒｉｖ、暗号文Ｃ１，…，ＣＮ、共通参照情報ｃｒｓを用いて、暗号文Ｃξから文書ｍξを計算して出力する。
【発明の効果】
【００１１】
本発明の紛失通信システムによれば、汎用的結合可能性を達成している従来方式と異なり，整数要素に対する署名方式で，かつＦ−偽造不可能性という通常の安全性より強い安全性をもつ署名方式（Ｗａｔｅｒｓ双対署名の変形版）を利用することで，判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。
【図面の簡単な説明】
【００１２】
【図１】実施例１に係る紛失通信システムの構成を示すブロック図。
【図２】実施例１に係る紛失通信システムの動作を示すシーケンス図。
【図３】実施例１のシステムパラメータ生成装置が備えるシステムパラメータ生成部の構成を示すブロック図。
【図４】実施例１のシステムパラメータ生成装置が備えるシステムパラメータ生成部の動作を示すフローチャート。
【図５】実施例１の送信装置が備える暗号化データベース生成部の構成を示すブロック図。
【図６】実施例１の送信装置が備える暗号化データベース生成部の動作を示すフローチャート。
【図７】実施例１の受信装置が備える要求生成部の構成を示すブロック図。
【図８】実施例１の受信装置が備える要求生成部の動作を示すフローチャート。
【図９】実施例１の送信装置が備える返信生成部の構成を示すブロック図。
【図１０】実施例１の送信装置が備える返信生成部の動作を示すフローチャート。
【図１１】実施例１の受信装置が備える文書取得部の構成を示すブロック図。
【図１２】実施例１の受信装置が備える文書取得部の動作を示すフローチャート。
【図１３】本発明の紛失通信システムと従来技術との違いを示す表。
【図１４】本発明の紛失通信システムと従来技術との違いを座標軸に表した図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
本明細書では、λはセキュリティパラメータを表すものとする。双線形写像については付録を参照されたい。また、ＢＭＳｅｔｕｐを、入力１λに対して、λビットの素数ｐ、素数位数ｐの巡回乗法群であるＧおよびＧＴ、双線形写像ｅ、群Ｇの生成元ｇよりなる双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を出力する標準的なアルゴリズムとする。本発明では、Ｇｒｏｔｈ−Ｓａｈａｉ証明を利用する。Ｇｒｏｔｈ−Ｓａｈａｉ証明のアルゴリズム、簡単な説明は付録Ｃを参照されたい（完全な詳細については参考文献７［ＧＳ０８］参照）。Ｗａｔｅｒｓ双対署名については付録Ｂ１を、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名については付録Ｂ２を参照されたい。
【００１５】
＜本明細書に登場する用語の解説＞
本明細書において、
【００１６】
【数１】
0005572580.tif 000002
【００１７】
と表記されている場合、アルゴリズム内部で乱数を発生させてランダムに出力することを意味する。また、
【００１８】
【数２】
0005572580.tif 000003
【００１９】
と表記されている場合、素数ｐを法とする整数環Ｚｐからランダムに値を選択することを意味する。
【実施例１】
【００２０】
まず、図１、図２を参照して、本発明の実施例１に係る紛失通信システム１００の動作の概略を説明する。図１は本実施例に係る紛失通信システム１００の構成を示すブロック図である。図２は本実施例に係る紛失通信システム１００の動作を示すシーケンス図である。
【００２１】
本実施例の紛失通信システム１００は、システムパラメータ生成装置１０、送信装置２０、受信装置３０からなる。システムパラメータ生成装置１０は、システムパラメータ生成部１１と、ｃｒｓ送信部１２とを備える。
【００２２】
以下、実際に行われる手続きの順に説明してゆく。システムパラメータ生成部１１は、入力１λに対して任意のλビットの素数と、当該素数位数の巡回乗法群と、双線形写像と、巡回乗法群の生成元と、を組み合わせて双線形写像パラメータを生成し、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータ、受信装置用パラメータを生成し、双線形写像パラメータ、送信装置用パラメータ、受信装置用パラメータ、生成元から設定した第１係数群から共通参照情報ｃｒｓを生成する（Ｓ１１）。ｃｒｓ送信部１２は、共通参照情報ｃｒｓを送信装置と受信装置に送信する（Ｓ１２）。
【００２３】
送信装置２０は、暗号化データベース生成部２１と、Ｔ送信部２２と、Ｔ記憶部２３と、返信生成部２４と、Ｒ送信部２５と、を備える。暗号化データベース生成部２１は、文書（ｍ１，…，ｍＮ）（Ｎは２以上の正の整数）と、共通参照情報ｃｒｓとを入力とし、Ｗａｔｅｒｓ双対署名の第１鍵対、第２鍵対を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３鍵対を生成し、秘密鍵を生成し、第１鍵対、第２鍵対、第３鍵対を用いて公開鍵を生成し、Ｗａｔｅｒｓ双対署名の第１署名、第２署名を生成し、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の第３署名を生成し、文書（ｍ１，…，ｍＮ）、第１鍵対に含まれる値、第２鍵対に含まれる値、共通参照情報ｃｒｓ、第１署名、第２署名、第３署名を用いて、暗号文Ｃ１，…，ＣＮを生成し、公開鍵と、暗号文Ｃ１，…，ＣＮとから暗号化データベースを生成する（Ｓ２１）。Ｔ送信部２２は、暗号化データベースを受信装置に送信する（Ｓ２２）。Ｔ記憶部２３は、暗号化データベースと、秘密鍵とを記憶する（Ｓ２３）。
【００２４】
受信装置３０は、要求生成部３１と、Ｑ送信部３２と、Ｑ記憶部３３と、文書取得部３４と、を備える。要求生成部３１は、暗号化データベースと、共通参照情報ｃｒｓと、インデックスξとを入力とし、暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、署名が正しい場合に、インデックスξに対応する暗号文Ｃξ、共通参照情報ｃｒｓを用いて再ランダム化を実行し、暗号文Ｃξ、共通参照情報ｃｒｓ、公開鍵を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明を生成し、知識識別不可能証明を含む要求Ｑ、と、要求Ｑおよびインデックスξを含むＱｐｒｉｖを生成する（Ｓ３１）。Ｑ送信部３２は、要求Ｑを送信装置に送信する（Ｓ３２）。Ｑ記憶部３３は、要求ＱとＱｐｒｉｖとを記憶する（Ｓ３３）。
【００２５】
送信装置２０の返信生成部２４は、共通参照情報ｃｒｓ、暗号化データベース、秘密鍵、要求Ｑを入力とし、知識識別不可能証明を検証し、知識識別不可能証明が正しい場合に、秘密鍵、要求Ｑを用いてブラインド復号を実行し、暗号化データベース、共通参照情報ｃｒｓ、要求Ｑを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成し、非対話ゼロ知識証明を含む返信Ｒを生成する（Ｓ２４）。Ｒ送信部２５は、返信Ｒを受信装置に送信する（Ｓ２５）。
【００２６】
受信装置３０の文書取得部３４は、返信Ｒと、Ｑｐｒｉｖと、暗号化データベースと、共通参照情報ｃｒｓとを入力とし、非対話ゼロ知識証明を検証し、非対話ゼロ知識証明が正しい場合に、Ｑｐｒｉｖ、暗号文Ｃ１，…，ＣＮ、共通参照情報ｃｒｓを用いて、暗号文Ｃξから文書ｍξを計算して出力する（Ｓ３４）。
【００２７】
このように、本実施例の紛失通信システム１００は、汎用的結合可能性を達成している従来方式と異なり，整数要素に対する署名方式で，かつＦ−偽造不可能性という通常の安全性より強い安全性をもつ署名方式（Ｗａｔｅｒｓ双対署名の変形版）を利用することで，判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。
【００２８】
次に、図３から図１２を用いて、本実施例の紛失通信システムをさらに詳細に説明する。図３は本実施例のシステムパラメータ生成装置１０が備えるシステムパラメータ生成部１１の構成を示すブロック図である。図４は本実施例のシステムパラメータ生成装置１０が備えるシステムパラメータ生成部１１の動作を示すフローチャートである。図５は本実施例の送信装置２０が備える暗号化データベース生成部２１の構成を示すブロック図である。図６は本実施例の送信装置２０が備える暗号化データベース生成部２１の動作を示すフローチャートである。図７は本実施例の受信装置３０が備える要求生成部３１の構成を示すブロック図である。図８は本実施例の受信装置３０が備える要求生成部３１の動作を示すフローチャートである。図９は本実施例の送信装置２０が備える返信生成部２４の構成を示すブロック図である。図１０は本実施例の送信装置２０が備える返信生成部２４の動作を示すフローチャートである。図１１は本実施例の受信装置３０が備える文書取得部３４の構成を示すブロック図である。図１２は本実施例の受信装置３０が備える文書取得部３４の動作を示すフローチャートである。
【００２９】
以下、実際に行われる手続きの順に説明してゆく。前述したように本実施例の紛失通信システム１００はシステムパラメータ生成装置１０、送信装置２０、受信装置３０からなる。前述したようにシステムパラメータ生成装置１０はシステムパラメータ生成部１１と、ｃｒｓ送信部１２とを備える。システムパラメータ生成部１１は、双線形写像パラメータ生成手段１１ａと、送信装置用パラメータ生成手段１１ｂと、受信装置用パラメータ生成手段１１ｃと、第１係数設定手段１１ｄと、システムパラメータ生成手段１１ｅとを備える。
【００３０】
双線形写像パラメータ生成手段１１ａは、入力１λに対して、ＢＭＳｅｔｕｐアルゴリズムを実行して、λビットの素数ｐ、素数位数ｐの巡回乗法群であるＧおよびＧＴ、双線形写像ｅ、群Ｇの生成元ｇよりなる双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する（ＳＳ１１ａ）。
【００３１】
【数３】
0005572580.tif 000004
【００３２】
システムパラメータ生成手段１１ｅは、共通参照情報ｃｒｓ：＝（Γ、ＧＳＳ、ＧＳＲ、ｇ１、ｇ２、ζ）を生成する（ＳＳ１１ｅ）。ｃｒｓ送信部１２は、共通参照情報ｃｒｓを送信装置２０と受信装置３０に送信する（Ｓ１２）。
【００３３】
前述したように送信装置２０は暗号化データベース生成部２１と、Ｔ送信部２２と、Ｔ記憶部２３と、返信生成部２４と、Ｒ送信部２５とを備える。暗号化データベース生成部２１は、第１Ｗａｔｅｒｓ鍵対生成手段２１ａと、第２Ｗａｔｅｒｓ鍵対生成手段２１ｂと、ＢＢ鍵対生成手段２１ｃと、秘密鍵生成手段２１ｄと、公開鍵生成手段２１ｅと、第２係数設定手段２１ｆと、第１Ｗａｔｅｒｓ署名生成手段２１ｇと、第２Ｗａｔｅｒｓ署名生成手段２１ｈと、ＢＢ署名生成手段２１ｉとを備える。
【００３４】
【数４】
0005572580.tif 000005
【００３５】
暗号化データベース生成手段２１ｋは、公開鍵ｐｋと、暗号文Ｃ１，…，ＣＮとを入力とし、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成する（ＳＳ２１ｋ）。Ｔ送信部２２は、暗号化データベースＴを受信装置３０に送信する（Ｓ２２）。Ｔ記憶部２３は、暗号化データベースＴと、秘密鍵ｓｋ：＝（ｘ１、ｘ２）とを記憶する（Ｓ２３）。
【００３６】
前述したように受信装置３０は要求生成部３１と、Ｑ送信部３２と、Ｑ記憶部３３と、文書取得部３４と、を備える。要求生成部３１は、署名検証部３１ａと、再ランダム化手段３１ｂと、知識識別不可能証明生成手段３１ｃと、要求生成手段３１ｄとを備える。
【００３７】
署名検証手段３１ａは、暗号文Ｃ１，…，ＣＮと、インデックスξとを入力とし、暗号文Ｃ１，…，ＣＮに含まれる署名をＷａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙおよび、Ｂｏｎｅｈ−Ｂｏｙｅｎ署名の署名検証アルゴリズムＢＢ．Ｖｒｆｙを実行して検証し、暗号文Ｃ１，…，ＣＮに含まれる署名が正しい場合に、インデックスξに対応する暗号文Ｃξを出力する（ＳＳ３１ａ）。
【００３８】
【数５】
0005572580.tif 000006
【００３９】
Ｑ送信部３２は、要求Ｑを前記送信装置に送信する（Ｓ３２）。Ｑ記憶部３３は、要求ＱとＱｐｒｉｖとを記憶する（Ｓ３３）。
【００４０】
送信装置２０の返信生成部２４は、知識識別不可能証明検証手段２４ａと、ブラインド復号手段２４ｂと、非対話ゼロ知識証明生成手段２４ｃと、返信生成手段２４ｄと、を備える。知識識別不可能証明検証手段２４ａは、Ｇｒｏｔｈ−Ｓａｈａｉ証明の知識識別不可能証明πと、前記パラメータＧＳＲとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、知識識別不可能証明πを検証する（ＳＳ２４ａ）。
【００４１】
【数６】
0005572580.tif 000007
【００４２】
Ｒ送信部２５は、返信Ｒを受信装置３０に送信する（Ｓ２５）。
【００４３】
受信装置３０の文書取得部３４は、ゼロ知識証明検証手段３４ａと、文書生成手段３４ｂとを備える。
【００４４】
ゼロ知識証明検証手段３４ａは、返信Ｒと、パラメータＧＳＳとを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、非対話ゼロ知識証明δを検証する（ＳＳ３４ａ）。
【００４５】
【数７】
0005572580.tif 000008
【００４６】
このように、本実施例の紛失通信システム１００は、汎用的結合可能性を達成している従来方式と異なり，整数要素に対する署名方式で，かつＦ−偽造不可能性という通常の安全性より強い安全性をもつ署名方式（Ｗａｔｅｒｓ双対署名の変形版）を利用することで，判定線形仮定というごく標準的な暗号学的仮定だけを用いて、汎用的結合可能性を実現し、さらに安全性について証明された適応的紛失通信を実現できる。
【００４７】
＜本発明と従来技術の比較＞
次に、図１３、図１４を参照して、本発明と従来技術との比較について説明する。図１３は本発明の紛失通信システムと従来技術との違いを示す表である。図１４は本発明の紛失通信システムと従来技術との違いを座標軸に表した図である。図１３は、左隅列に本明細書における参考文献番号を記した。また、左から２番目の列についてはこれらの文献を表す略号を表記している。また、ＵＣとは安全性が汎用的結合可能性を満たしていることを示す。Ｆｕｌｌ  Ｓｉｍとは、ｆｕｌｌｙ  ｓｉｍｕｌｔａｂｌｅ安全性という汎用的結合性より弱い安全性を満たしていることを示す。ｑ−ｈｉｄｄｅｎＬＲＳＷ仮定など、ｑ−が接頭についている仮定は、暗号の分野でｑ仮定と呼ばれ、標準的な暗号学的仮定であるＲＳＡ仮定、ＤＤＨ（判定Ｄｉｆｆｅｒ−Ｈｅｌｌｍａｎ）仮定、ＤＬＩＮ（判定線形）仮定に比べて安全性の根拠に信頼がおけない。
（参考文献１）[BB04] D. Boneh and X. Boyen. Efficient Selective-ID Secure Identity-
Based Encryption Without RandomOracles. In EUROCRYPT’04, volume 3027 of Lecture Notes in Computer Science, pages 223-238.Springer, 2004.
（参考文献２）[BF01] D. Boneh and M. K. Franklin. Identity-Based Encryption from the Weil Pairing. In CRYPTO’01,volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer, 2001.
（参考文献３）[CNS07] J. Camenisch, G. Neven, and A. Shelat. Simulatable Adaptive Oblivious Transfer. In EUROCRYPT’07, volume 4515 of Lecture Notes in Computer Science, pages 573-590. Springer, 2007.
（参考文献４）[CS97] J. Camenisch and M. Stadler. Efficient Group Signature Schemes for Large Groups (ExtendedAbstract). In CRYPTO’97, volume 1294 of Lecture Notes in Computer Science, pages 410-424.Springer, 1997.
（参考文献５）[GH08] M. Green and S. Hohenberger. Universally Composable Adaptive Oblivious Transfer. In ASIACRYPT’08, volume 5350 of Lecture Notes in Computer Science, pages 179-197. Springer, 2008.
（参考文献６）[GH11] M. Green and S. Hohenberger. Practical Adaptive Oblivious Transfer from a Simple Assumption.In TCC’01, volume 6597 of Lecture Notes in Computer Science, pages 347-363 Springer, 2011.http://eprint.iacr.org/2010/109.
（参考文献７）[GS08] J. Groth and A. Sahai. Efficient Non-interactive Proof Systems for Bilinear Groups. In EUROCRYPT’08, volume 4965 of Lecture Notes in Computer Science, pages 415-432. Springer, 2008.
（参考文献８）[JL09] S. Jarecki and X. Liu. Efficient Oblivious Pseudorandom Function with Applications to AdaptiveOT and Secure Computation of Set Intersection. In TCC, volume 5444 of Lecture Notes in ComputerScience, pages 577-594. Springer, 2009.
（参考文献９）[KN09] K. Kurosawa and R. Nojima. Simple Adaptive Oblivious Transfer without Random Oracle. InASIACRYPT’09, volume 5912 of Lecture Notes in Computer Science, pages 334-346. Springer, 2009.
（参考文献１０）[KNP10] K. Kurosawa, R. Nojima, and L. T. Phong. Efficiency-Improved Full Simulatable Adaptive OTunder the DDH Assumption. In SCN, volume 6280 of Lecture Notes in Computer Science, pages172-181. Springer, 2010.
（参考文献１１）[RKP09] A. Rial, M. Kohlweiss, and B. Preneel. Universally Composable Adaptive Priced ObliviousTransfer. In Pairing, volume 5671 of Lecture Notes in Computer Science, pages 231-247. Springer,2009.
（参考文献１２）[Wat09] B. Waters. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions.In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages 619-636. Springer,2009.
＜本発明と従来技術の比較おわり＞
【００４８】
＜本発明が有する進歩性についての補足＞
線形暗号：本発明の方式は以下の線形暗号方式の署名からできている。この基本構造は参考文献５、１１においても同じである。
【００４９】
【数８】
0005572580.tif 000009
【００５０】
本発明の進歩性について：本発明では、送信装置は線形暗号方式により暗号文
【００５１】
【数９】
0005572580.tif 000010
を生成し，群Ｇの要素である
【００５２】
【数１０】
0005572580.tif 000011
への署名を生成し、これらを受信装置に送信している。そして受信装置はインデックスξを選び、その暗号文に対して再ランダム化を行い、正しく再ランダム化を行ない、それに対応する署名を知っていることを証明する知識識別不可能証明（Ｇｒｏｔｈ−Ｓａｈａｉ証明による）を生成する。しかし、Ｇｒｏｔｈ−Ｓａｈａｉ証明は群要素に関する証明しか生成することができない。ゆえに上記のように（ρ１やρ２に対してではなく）
【００５３】
【数１１】
0005572580.tif 000012
に署名する必要がある。つまりメッセージが群Ｇの要素となっているような署名方式が必要と（一見）考えられる。なおこのような署名方式で安全なものは近年になって開発されたばかりであり、提案数自体が少ない上、それらは標準的でない暗号学仮定に基づいており、信頼性が低い。本発明ではＷａｔｅｒｓ双対署名を利用しているが、この方式は群要素に対して署名できない（整数に対して署名可能）。よって，Ｗａｔｅｒｓ双対署名を利用することで適応的紛失通信を構成することは非自明である。しかしこのままではＧｒｏｔｈ−Ｓａｈａｉ証明を利用できないため、Ｗａｔｅｒｓ双対署名を変形し（適応的紛失通信、明細書の暗号文のなかの
【００５４】
【数１２】
0005572580.tif 000013
という要素が追加要素である）、通常の署名より高い安全性を達成すること（ρ１やρ２に対する署名の偽造ができない、という通常の安全性ではなく、
【００５５】
【数１３】
0005572580.tif 000014
に対する署名さえも偽造できない、というより強力な安全性）で、群要素に対して署名ができなくとも、Ｇｒｏｔｈ−Ｓａｈａｉ証明と組み合わせることを可能にした。またＧｒｏｔｈ−Ｓａｈａｉ証明を署名保持の証明に利用するには署名がすべて群要素である必要があるが、Ｗａｔｅｒｓ双対署名の署名は一つだけ群要素でないものが含まれている（明細書のｔａｇｋがそれである）。しかし提案した適応的紛失通信の方式の中では，その群要素でない署名要素はブラインドして相手に直接送ることで
【００５６】
【数１４】
0005572580.tif 000015
署名の情報を漏らすことなくＧｒｏｔｈ−Ｓａｈａｉ証明を可能にしている。以上のことから従来の適応的紛失通信方式にＷａｔｅｒｓ双対署名を利用して改良することは非自明であり、本発明は従来技術に対して進歩性を有している。
＜本発明が有する進歩性についての補足おわり＞
【００５７】
＜付録Ａ：ペアリング＞
双線型性を満たすペアリングと呼ばれる演算は楕円曲線上の二点に定義される。なお、楕円曲線上の群は普通加法群であるが、暗号理論学会での慣習に従い乗法群として記述する。ＧとＧＴを位数ｐの群とする。ここでｐは十分大きい素数である。この二つの群の間の双線型写像ｅ：Ｇ×Ｇ→ＧＴは以下の性質を満たす。
双線型性：任意のｇ，ｈ∈Ｇおよび任意のａ，ｂ∈Ｚに対して
ｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂ
が成立する。
非退化性：ｅ（ｇ，ｇ）≠１を満たすｇが存在する。つまり、もしｇがＧの生成元ならｅ（ｇ，ｇ）はＧＴの生成元である。
計算可能性：任意のｇ，ｈ∈Ｇに対して、ｅ（ｇ，ｈ）は効率的に（つまり多項式時間で）計算可能である。詳しくは［ＢＦ０１］や「現代暗号への招待（黒澤馨著，サイエンス社）」の１３章を参照されたい。
＜付録Ａ：ペアリングおわり＞
【００５８】
＜付録Ｂ：ディジタル署名＞
［Ｂ１：Ｗａｔｅｒｓ双対署名］
【００５９】
【数１５】
0005572580.tif 000016
【００６０】
［Ｂ２：（変形）Ｂｏｎｅｈ−Ｂｏｙｅｎ署名］
【００６１】
【数１６】
0005572580.tif 000017
【００６２】
Ｆ−署名：選択メッセージ攻撃に対してＦ−セキュアと呼ばれるより強い安全性の定義を考える。Ｆを効率的に計算可能な全単射であるものとする。署名スキーム
【００６３】
【数１７】
0005572580.tif 000018
は、以下のゲームによるアドバンテージが無視できるほど小さい場合には、選択メッセージ攻撃下においてＦ−セキュアと呼ばれる。
手順１（セットアップ）：挑戦者は、
【００６４】
【数１８】
0005572580.tif 000019
を発生させてｖｋを敵対者に送る。
手順２（質問）：敵対者はメッセージ
【００６５】
【数１９】
0005572580.tif 000020
を挑戦者に送り、挑戦者は
【００６６】
【数２０】
0005572580.tif 000021
を返信する。これらの質問はｉ＝１〜Ｎまで適応的に挑戦者に送信される。ここで
【００６７】
【数２１】
0005572580.tif 000022
を敵対者からの質問であるメッセージのセット
【００６８】
【数２２】
0005572580.tif 000023
を表すものとする。
【００６９】
手順３（出力）：敵対者は（ｙ＊，σ＊）を出力する。
【００７０】
【数２３】
0005572580.tif 000024
を
【００７１】
【数２４】
0005572580.tif 000025
とした場合に、
【００７２】
【数２５】
0005572580.tif 000026
かつ、
【００７３】
【数２６】
0005572580.tif 000027
が成り立つ場合には、敵対者がゲームに勝利したことになる。
ここで、
【００７４】
【数２７】
0005572580.tif 000028
を、攻撃者
【００７５】
【数２８】
0005572580.tif 000029
がゲームに勝利する確率と定義して、全てのＰＰＴ攻撃者
【００７６】
【数２９】
0005572580.tif 000030
について、
【００７７】
【数３０】
0005572580.tif 000031
が成り立つとき、署名スキームＳｉｇは、選択メッセージ攻撃に対するＦ−セキュアである。
＜付録Ｂ：ディジタル署名おわり＞
【００７８】
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明＞
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムでは等式の充足可能性（例えばペアリング生成等式）に対して、効率的に非対話識別不可能（ＮＩＷＩ）証明、非対話ゼロ知識（ＮＩＺＫ）証明を行うことができる。証明システムはＧｒｏｔｈ−Ｓａｈａｉコミットメントスキームに基づいている。
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキーム：本スキームでは、まず、双線形写像パラメータ
【００７９】
【数３１】
0005572580.tif 000032
を生成する。
ＧＳ．ＣｏｍＳｅｔｕｐ（Γ）：共通参照情報ｃｒｓＧＳＣを出力する。
ＧＳ．Ｃｏｍｍｉｔ（ｃｒｓＧＳＣ，ｍ，ｄ）：コミットｍ∈Ｇである入力ｍ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、として出力コミットメント
【００８０】
【数３２】
0005572580.tif 000033
を生成する。
ＧＳ．ＥｘｐＣｏｍ（ｃｒｓＧＳＣ，ｍ，ｂ，ｄ）：入力ｍ∈Ｚｐ、基数ｂ∈Ｇ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、ｃを
【００８１】
【数３３】
0005572580.tif 000034
として、出力（ｂ，ｃ）を生成する。
ＧＳ．Ｏｐｅｎｉｎｇ（ｃｒｓＧＳＣ，ｃ，ｍ，ｄ）：ｄが（ｍ，ｃ）に対して正当なデコミットメントである場合、１を出力する。それ以外の場合は、０を出力する。すなわち、
【００８２】
【数３４】
0005572580.tif 000035
である。（ｂ，ｃ）がｍの累乗で約束される検証の場合には、
【００８３】
【数３５】
0005572580.tif 000036
となる。
【００８４】
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキームの共通参照情報には２タイプの生成物が存在する。１つのタイプではコミットメントが完全拘束であり、計算量的拘束であり抽出可能である。もう１つのタイプでは、コミットメントが完全秘匿であり、計算量的拘束であり曖昧性を持つ。これらの２つのタイプは計算量的識別不可能である。本証明システムは例えばＤＬＩＮ仮定などの暗号学的仮定裏付けられている（以下、本説明ではＤＬＩＮ仮定を用いるものとする）。ステートメントＳは、変数
【００８５】
【数３６】
0005572580.tif 000037
と、定数
【００８６】
【数３７】
0005572580.tif 000038
と、Ｇ内の値であるコミットメント
【００８７】
【数３８】
0005572580.tif 000039
により構成される。ＧｒｏｔｈとＳａｈａｉは、非対話知識証明（ＮＩＰＫ）の構築を以下の式で表した。
【００８８】
【数３９】
0005572580.tif 000040
この証明πはコミットメントｃ１，…，ｃｍ，ｄ１，…，ｄｎを含む。ＧｒｏｔｈとＳａｈａｉは、これらのコミットメントからペアリング生成式を満足する値
【００８９】
【数４０】
0005572580.tif 000041
を開くことのできる効率的なエキストラクタを提供する。ここで、ＣａｍｅｎｉｓｃｈとＳｔａｄｌｅｒ［ＣＳ９７］の記法、例えば、
【００９０】
【数４１】
0005572580.tif 000042
を用いる。
【００９１】
本システムでは、証明者は同形のコミットメントスキームと共通参照情報ＣＲＳとを用いてｗｉｔｎｅｓｓ（証拠、群の元）を遂行する。共通参照情報ＣＲＳには２つのタイプが存在する。１つのタイプは完全拘束コミットメントスキームを、もう１つのタイプは完全秘匿コミットメントスキームを与える。これらの２つのタイプは計算量的識別不可能である。
証明システム：証明システムは以下のアルゴリズムにより構成される。
ＧＳ．Ｓｅｔｕｐ（Γ）：入力
【００９２】
【数４２】
0005572580.tif 000043
を実行して、出力である証明システムの共通参照情報ＧＳを生成する。共通参照情報ＧＳは、コミットメントスキームの共通参照情報ｃｒｓＧＳＣを含む。
ＧＳ：Ｐｒｏｖｅ（ＧＳ，Ｓ，Ｗ）：ステートメントＳと、ｗｉｔｎｅｓｓ（証拠）
【００９３】
【数４３】
0005572580.tif 000044
とを入力とし、証明πを出力する。
ＧＳ．Ｖｒｆｙ（ＧＳ，π）：証明πを入力とし、照明を検証し、正当であれば１を出力し、それ以外は０を出力する。
ＧＳ．ＥｘｔＳｅｔｕｐ（Γ）：共通参照情報ＧＳ（その分布は通常の共通参照情報と一致する）と、正当なｗｉｔｎｅｓｓを導出するためのトラップドアｔｄｅｘｔとを出力する。
ＧＳ．Ｅｘｔｒａｃｔ（ＧＳ，ｔｄｅｘｔ，π）：証明πと、トラップドアｔｄｅｘｔとを入力とし、各コミットメントＣｉから抽出値
【００９４】
【数４４】
0005572580.tif 000045
を抽出して等式を満たす証拠
【００９５】
【数４５】
0005572580.tif 000046
を出力する。
ＧＳ．ＳｉｍＳｅｔｕｐ（Γ）：ＧＳ．Ｓｅｔｕｐ（Γ）の出力である通常の共通参照情報と計算量的識別不可能な模擬共通参照情報ＧＳ’と、模擬トラップドアｔｄｓｉｍを出力する。
ＧＳ．ＳｉｍＰｒｏｖｅ（ＧＳ’，ｔｄｓｉｍ，Ｓ）：模擬共通参照情報ＧＳ’と、模擬トラップドアｔｄｓｉｍとを入力とし、ＧＳ．Ｖｒｆｙ（ＧＳ’，π）＝１を満たすステートメントＳの模擬証明πを出力する。
セキュリティ特性：本証明システムは以下の特性を満足する。
正当性：全ての
【００９６】
【数４６】
0005572580.tif 000047
について、
【００９７】
【数４７】
0005572580.tif 000048
を満たす。
抽出性：
【００９８】
【数４８】
0005572580.tif 000049
および、証明πについて、
【００９９】
【数４９】
0005572580.tif 000050
である場合に、
【０１００】
【数５０】
0005572580.tif 000051
はステートメントＳを確率１で満足する。
共通参照情報ＣＲＳの識別不可能性：
【０１０１】
【数５１】
0005572580.tif 000052
と、
【０１０２】
【数５２】
0005572580.tif 000053
について、
【０１０３】
【数５３】
0005572580.tif 000054
を満たす。
構成可能なｗｉｔｎｅｓｓの識別不可能性：全てのＰＰＴ攻撃者
【０１０４】
【数５４】
0005572580.tif 000055
について、
【０１０５】
【数５５】
0005572580.tif 000056
が成立する。
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムは、制限されたステートメントのクラス（ΣＺＫはこのクラスを意味する）における構成可能なゼロ知識証明を提供する。
構成可能なゼロ知識：全てのＰＰＴ攻撃者
【０１０６】
【数５６】
0005572580.tif 000057
について、
【０１０７】
【数５７】
0005572580.tif 000058
【０１０８】
が成立する。
Ｆ−抽出可能非対話知識証明：Ｇｒｏｔｈ−Ｓａｈａｉ証明システムにおいては、非対話知識証明（ＮＩＷＩまたはＮＩＺＫ）から、トラップドアｔｄｅｘｔを使うことによりｗｉｔｎｅｓｓを抽出できる。しかしながら、この証明システムにおいては、群の元のみがコミットできるため、群Ｇの元を抽出できるのみである。従って、本証明システムにおいてメッセージｍ∈Ｚｐを選択して、ｇｍ∈Ｇをコミットし、ｗｉｔｎｅｓｓであるｇｍを用いて、非対話証明を生成する場合には、ｇｍのみを抽出することができる（これはｍ自身でなく、関数Ｆ（ｍ）：＝ｇｍの出力であることに注意する）。この性質から、Ｇｒｏｔｈ−Ｓａｈａｉ証明システムはＦ−抽出可能性を備えると言われる。
定理２［ＧＳ０８］：ＤＬＩＮ仮定が成り立つならば、Ｇｒｏｔｈ−Ｓａｈａｉ証明システム効率的にインスタンス化できる。
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明おわり＞
【０１０９】
＜付録Ｄ：暗号学的仮定＞
【０１１０】
【数５８】
0005572580.tif 000059
＜付録Ｄ：暗号学的仮定おわり＞
【０１１１】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005572580.tif 000070
【図２】
0005572580.tif 000071
【図３】
0005572580.tif 000072
【図４】
0005572580.tif 000073
【図５】
0005572580.tif 000074
【図６】
0005572580.tif 000075
【図７】
0005572580.tif 000076
【図８】
0005572580.tif 000077
【図９】
0005572580.tif 000078
【図１０】
0005572580.tif 000079
【図１１】
0005572580.tif 000080
【図１２】
0005572580.tif 000081
【図１３】
0005572580.tif 000082
【図１４】
0005572580.tif 000083