紛失通信システム、紛失通信方法、およびプログラム
【課題】暗号文のサイズを削減した効率的な適応的紛失通信を提供する。
【解決手段】本発明の紛失通信システム１０は、システムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。システムパラメータ生成装置１００は、セキュリティパラメータλを入力とし、共通参照情報ｃｒｓを生成する。送信装置２００は、文書ｍ１，…，ｍＮを入力とし、暗号化データベースＴを生成する。受信装置３００は、暗号化データベースＴとインデックスを入力とし、要求Ｑを生成する。送信装置２００は、要求Ｑを入力とし、ブラインド復号結果ａと非対話ゼロ知識証明δを含む返信Ｒを生成する。受信装置３００は、返信Ｒを入力とし、文書ｍξを出力する。暗号方式として、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を維持している。
【解決手段】本発明の紛失通信システム１０は、システムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。システムパラメータ生成装置１００は、セキュリティパラメータλを入力とし、共通参照情報ｃｒｓを生成する。送信装置２００は、文書ｍ１，…，ｍＮを入力とし、暗号化データベースＴを生成する。受信装置３００は、暗号化データベースＴとインデックスを入力とし、要求Ｑを生成する。送信装置２００は、要求Ｑを入力とし、ブラインド復号結果ａと非対話ゼロ知識証明δを含む返信Ｒを生成する。受信装置３００は、返信Ｒを入力とし、文書ｍξを出力する。暗号方式として、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を維持している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電気通信システムでデータベースにおける情報検索などに利用される紛失通信システム、紛失通信方法、およびプログラムに関する。
【背景技術】
【０００２】
適応的紛失通信とは、ある受信者が文書（ｍ１，…，ｍＮ）（以下、Ｎは２以上の正の整数）を持つある送信者と通信を行い、受信者が指定した番号ｂに対応する文書ｍｂを得る方法である。送信者は番号ｂについて一切知ることができない。受信者は指定した文書以外を得ることはできない。かつ上記の通信を適応的に何度も繰り返すことができる。この技術は安全なデータベース検索などに応用可能である。従来の適応的紛失通信で、汎用的結合可能性と呼ばれる高い安全性を達成している代表的なものに非特許文献１および非特許文献２がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１では群の要素に対して署名が可能な署名方式を利用しているため非常に特殊な暗号学仮定を必要とし、安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。また、非特許文献２では群要素に対して署名可能な方式は利用しないが、値段付き適応的紛失通信という、機能追加した方式であり、かつ安全性を証明するために通常の署名より強い安全性をもつ署名方式を利用している。そのため、上記とは別の強い暗号学的仮定が必要になり、やはり安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。
【０００５】
本願の出願人による未公開の先願である特願２０１１−９６１８４号に記載されている方式では、特殊な暗号学的仮定を用いる問題を解決し、標準的な暗号学的仮定である判定線形仮定だけを用いることで、汎用的結合可能性を持つ適応的紛失通信を実現している。しかし、利用している暗号方式が乱数を２つ用いる方式であるため、署名の数が多く、暗号文のサイズが大きくなり非効率的であるという問題が解決されていなかった。
【０００６】
そこで、本発明では、標準的な暗号学的仮定だけを用い、かつ汎用的結合可能性をもつことが証明可能でありながら、暗号文のサイズを削減した効率的な適応的紛失通信を実現できる紛失通信システムを提供する。
【課題を解決するための手段】
【０００７】
本発明の紛失通信システムは、システムパラメータ生成装置、送信装置、受信装置からなる。システムパラメータ生成装置は、双線形写像パラメータ生成部と送信装置用パラメータ生成部と受信装置用パラメータ生成部と係数生成部とシステムパラメータ生成部を備える。双線形写像パラメータ生成部は、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する。送信装置用パラメータ生成部は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する。受信装置用パラメータ生成部は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する。係数生成部は、生成元から係数群を計算する。システムパラメータ生成部は、双線形写像パラメータと送信装置用パラメータと受信装置用パラメータと係数群から、共通参照情報を生成し、共通参照情報を送信装置および受信装置へ送信する。
【０００８】
送信装置は、鍵対生成部と鍵生成部と署名生成部と暗号文生成部と暗号化データベース生成部と知識識別不可能証明検証部とブラインド復号部と非対話ゼロ知識証明生成部と返信生成部と秘密鍵記録部を備える。鍵対生成部は、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する。鍵生成部は、秘密鍵を生成し、鍵対と秘密鍵から計算した係数から、公開鍵を生成する。署名生成部は、０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、乱数ρ１，…，ρＮに対する署名を生成する。暗号文生成部は、文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と公開鍵と乱数ρｊと署名と鍵対と共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する。暗号化データベース生成部は、公開鍵と暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、暗号化データベースを受信装置に送信する。知識識別不可能証明検証部は、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する。ブラインド復号部は、知識識別不可能証明が正しい場合に、秘密鍵と共通参照情報を用いて、ブラインド復号結果を生成する。非対話ゼロ知識証明生成部は、要求Ｑとブラインド復号結果と公開鍵と秘密鍵と共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する。返信生成部は、ブラインド復号結果と非対話ゼロ知識証明から、返信Ｒを生成し、返信Ｒを受信装置へ送信する。秘密鍵記録部は、共通参照情報と暗号化データベースと秘密鍵を記録する。
【０００９】
受信装置は、署名検証部と再ランダム化部と知識識別不可能証明生成部と要求生成部と非対話ゼロ知識証明検証部と復号部と要求記録部を備える。署名検証部は、暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、暗号文Ｃ１，…，ＣＮ全てについて署名が正しい署名であると判定され、暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Ｃξを出力する。再ランダム化部は、公開鍵と共通参照情報を用いて、暗号文Ｃξから、再ランダム化暗号文を生成する。知識識別不可能証明生成部は、暗号文Ｃξと再ランダム化暗号文と公開鍵と共通参照情報から、知識識別不可能証明および知識識別不可能証明検証手段で利用される係数θを生成する。要求生成部は、再ランダム化暗号文と知識識別不可能証明から、要求Ｑを生成し、要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、要求Ｑと係数θを送信装置に送信する。非対話ゼロ知識証明検証部は、返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、非対話ゼロ知識証明を検証する。復号部は、非対話ゼロ知識証明が正しい場合に、Ｑｐｒｉｖと暗号文Ｃξと共通参照情報を用いて、ブラインド復号結果から、文書ｍξを計算して出力する。要求記録部は、共通参照情報と暗号化データベースと公開鍵と要求ＱとＱｐｒｉｖを記録する。
【発明の効果】
【００１０】
本発明の紛失通信システムは、暗号方式として、Ｂｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号を変形した変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を持たせることが可能となっている。
【００１１】
したがって、本発明の紛失通信システムによれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。
【図面の簡単な説明】
【００１２】
【図１】実施例１に係る紛失通信システムの構成を示すブロック図。
【図２】実施例１に係る紛失通信システムの動作を示すシーケンス図。
【図３】実施例１のシステムパラメータ生成装置の動作を示すフローチャート。
【図４】実施例１の送信装置が暗号化データベースを生成する動作を示すフローチャート。
【図５】実施例１の受信装置が要求を生成する動作を示すフローチャート。
【図６】実施例１の送信装置が返信を生成する動作を示すフローチャート。
【図７】実施例１の受信装置が復号する動作を示すフローチャート。
【図８】本発明の紛失通信システムと従来技術との違いを示す表。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
本明細書では、Ｎを２以上の整数、＾をべき乗を示す記号とする。
【数１】
と表記されている場合、アルゴリズム内部で乱数を発生させてランダムに出力することを意味する。また、
【数２】
と表記されている場合、素数ｐを法とする整数環Ｚｐからランダムに値を選択することを意味する。
【００１５】
本発明では、Ｇｒｏｔｈ−Ｓａｈａｉ証明を利用する。Ｇｒｏｔｈ−Ｓａｈａｉ証明のアルゴリズム、簡単な説明は付録Ｃを参照されたい（完全な詳細は、「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.」参照）。双線形写像については付録Ａを、Ｗａｔｅｒｓ双対署名については付録Ｂ１を、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号については付録Ｂ２を参照されたい。
【実施例１】
【００１６】
まず、図１、図２を参照して、本発明の実施例１に係る紛失通信システム１０の動作の概略を説明する。図１は本実施例に係る紛失通信システム１０の構成を示すブロック図である。図２は本実施例に係る紛失通信システム１０の動作を示すシーケンス図である。
【００１７】
本実施例の紛失通信システム１０は、システムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。
【００１８】
システムパラメータ生成装置１００は、セキュリティパラメータλを入力とし、共通参照情報ｃｒｓを生成し、送信装置２００および受信装置３００に送信する（Ｓ１０１）。送信装置２００は、文書ｍ１，…，ｍＮを入力とし、公開鍵ｐｋと暗号文Ｃ１，…，ＣＮを含む暗号化データベースＴを生成し、暗号化データベースＴを受信装置３００に送信する（Ｓ２０１）。受信装置３００は、暗号化データベースＴとインデックスξを入力とし、再ランダム化暗号文ｄと知識識別不可能証明πを含む要求Ｑを生成し、送信装置２００へ送信する（Ｓ３０１）。送信装置２００は、要求Ｑを入力とし、ブラインド復号結果ａと非対話ゼロ知識証明δを含む返信Ｒを生成し、受信装置３００に送信する（Ｓ２０２）。受信装置３００は、返信Ｒを入力とし、文書ｍξを出力する（Ｓ３０２）。
【００１９】
次に、図３から図７を参照して、本発明の実施例１に係る紛失通信システム１０の動作をさらに詳細に説明する。図３は本実施例のシステムパラメータ生成装置がシステムパラメータを生成する動作を示すフローチャートである。図４は本実施例の送信装置が暗号化データベースを生成する動作を示すフローチャートである。図５は本実施例の受信装置が要求を生成する動作を示すフローチャートである。図６は本実施例の送信装置が返信を生成する動作を示すフローチャートである。図７は本実施例の受信装置が復号する動作を示すフローチャートである。
【００２０】
以下、実際に行われる手続きの順に説明してゆく。前述したように本実施例の紛失通信システム１０はシステムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。システムパラメータ生成装置１００は、双線形写像パラメータ生成部１１０と送信装置用パラメータ生成部１２０と受信装置用パラメータ生成部１３０と係数生成部１４０とシステムパラメータ生成部１５０を備える。
【００２１】
双線形写像パラメータ生成部１１０は、セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する（Ｓ１１０）。
【００２２】
送信装置用パラメータ生成部１２０は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する（Ｓ１２０）。
受信装置用パラメータ生成部１３０は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する（Ｓ１３０）。
【００２３】
係数生成部１４０は、０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζおよびｈ：＝ｇ＾ｙｈを計算する（Ｓ１４０）。
システムパラメータ生成部１５０は、双線形写像パラメータΓと送信装置用パラメータＧＳＳと受信装置用パラメータＧＳRと係数ｇ２および係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、共通参照情報ｃｒｓを送信装置２００および受信装置３００へ送信する（Ｓ１５０）。
【００２４】
送信装置２００は、鍵対生成部２１０と鍵生成部２１５と署名生成部２２０と暗号文生成部２２５と暗号化データベース生成部２３０と秘密鍵記録部２９０を備える。
鍵対生成部２１０は、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する（Ｓ２１０）。
【００２５】
鍵生成部２１５は、０以上ｐ−１以下のランダムな秘密鍵αを生成し、秘密鍵αと共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、鍵対ＶＫと係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する（Ｓ２１５）。
署名生成部２２０は、文書ｍ１，…，ｍＮを入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、乱数ρｊに対する署名ｓｉｇｊを生成する（Ｓ２２０）。
【００２６】
暗号文生成部２２５は、文書ｍ１，…，ｍＮと公開鍵ｐｋと乱数ρｊと署名ｓｉｇｊと鍵対ＶＫに含まれる値ｕと共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する（Ｓ２２５）。
暗号化データベース生成部２３０は、公開鍵ｐｋと暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、暗号化データベースＴを受信装置３００に送信する（Ｓ２３０）。
【００２７】
秘密鍵記録部２９０は、秘密鍵αを記録する（Ｓ２９０）。
受信装置３００は、署名検証部３１０と再ランダム化部３１５と知識識別不可能証明生成部３２０と要求生成部３２５と要求記録部３９０を備える。
【００２８】
署名検証部３１０は、暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて暗号文Ｃｊに含まれる署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証する（Ｓ３１１）。署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止する（Ｓ３９０４）。ｊ＝１，…，Ｎのすべてについて暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証する（Ｓ３１２）。いずれかが満たさないと判定されると停止する（Ｓ３９０５）。暗号文Ｃ１，…，ＣＮ全てについて署名ｓｉｇｊが正しい署名であると判定され、暗号文Ｃ１，…，ＣＮ全てについて暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Ｃξを出力する（Ｓ３１３）。
【００２９】
再ランダム化部３１５は、０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、公開鍵ｐｋと共通参照情報ｃｒｓと暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、再ランダム化暗号文ｄを生成する（Ｓ３１５）。
【００３０】
知識識別不可能証明生成部３２０は、暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、暗号文Ｃξと再ランダム化暗号文ｄと公開鍵ｐｋと共通参照情報ｃｒｓを用いて、知識識別不可能証明πを
【数３】
により生成する（Ｓ３２０）。なお、記法
【数４】
は共通参照情報ＧＳの下で、コロン以降の等式を満たす知識Ｗ＝（ｗ１，ｗ２）の非対話知識識別不可能証明を表す。括弧でくくられた（ｗ１，ｗ２）以外の情報は検証者に知られているものとする。
【００３１】
要求生成部３２５は、再ランダム化暗号文ｄと知識識別不可能証明πから、要求Ｑ：＝（ｄ，π）を生成し、要求Ｑとインデックスξと乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、要求Ｑおよび係数θを送信装置２００に送信する（Ｓ３２５）。
要求記録部３９０は、要求ＱおよびＱｐｒｉｖを記録する（Ｓ３９０）。
送信装置２００は、さらに、知識識別不可能証明検証部２３５とブラインド復号部２４０と非対話ゼロ知識証明生成部２４５と返信生成部２５０を備える。
【００３２】
知識識別不可能証明検証部２３５は、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、要求Ｑに含まれる知識識別不可能証明πを検証する（Ｓ２３５）。正しい証明でない場合は、停止する（Ｓ２９１１）。
【００３３】
ブラインド復号部２４０は、知識識別不可能証明πが正しい場合に、秘密鍵αと共通参照情報ｃｒｓを用いて、要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成する（Ｓ２４０）。
【００３４】
非対話ゼロ知識証明生成部２４５は、再ランダム化暗号文ｄとブラインド復号結果ａと公開鍵ｐｋと秘密鍵αと共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数５】
により生成する（Ｓ２４５）。
【００３５】
返信生成部２５０は、ブラインド復号結果ａと非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、返信Ｒを受信装置３００へ送信する（Ｓ２５０）。
受信装置３００は、さらに、非対話ゼロ知識証明検証部３３０と復号部３３５を備える。
【００３６】
非対話ゼロ知識証明検証部３３０は、返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、非対話ゼロ知識証明δを検証する（Ｓ３３０）。正しい証明でない場合は、停止する（Ｓ３９１１）。
復号部３３５は、非対話ゼロ知識証明δが正しい場合に、Ｑｐｒｉｖと暗号文Ｃξと共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、ブラインド復号結果ａから文書ｍξを出力する（Ｓ３３５）。
【００３７】
このように、本実施例の紛失通信システム１０は、暗号方式として、Ｂｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号を変形した変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を持たせることが可能となっている。したがって、本実施例の紛失通信システム１０によれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。
【００３８】
＜本発明と従来技術の比較＞
次に、図８を参照して、本発明と従来技術との比較について説明する。図８は本発明の紛失通信システムと従来技術との違いを示す表である。図８は、左隅列に本明細書における非特許文献番号を記した。また、ＵＣとは安全性が汎用的結合可能性を満たしていることを示す。ｑ−ｈｉｄｄｅｎＬＲＳＷ仮定など、ｑ−が接頭についている仮定は、暗号の分野でｑ−仮定と呼ばれ、標準的な暗号学的仮定であるＲＳＡ仮定、ＤＢＤＨ（判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）仮定、ＤＬＩＮ（判定線形）仮定に比べて安全性の根拠に信頼がおけない。πは送信装置が生成する知識識別不可能証明を表しており、｜π｜はその群要素の数を表している。知識識別不可能証明のサイズは表では同一として扱ったが厳密にはそれぞれのサイズは異なる。しかしこのサイズは暗号文のπ以外の群要素数に比例して大きくなるので提案方式のπのサイズは他のものと比べて大きくならない。他の方式と比べてＤＢＤＨ仮定が必要になっているが、ＤＢＤＨ仮定はごく標準的な仮定であるので、安全性は信頼できる。
【００３９】
非特許文献１、２の紛失通信システムでは、送信装置は線形暗号方式により暗号文（ｕ１＾ρ１，ｕ２＾ρ２，ｇ１＾ρ１，ｇ２＾ρ２，ζ＾ρ１＋ρ２・ｍ）を生成し、群Ｇの要素であるｕ１＾ρ１とｕ２＾ρ２への署名を生成するか（非特許文献１の方式）、Ｚｐの要素ρ１とρ２への署名を生成し（非特許文献２の方式はこれに近い）、これらを受信装置に送信している。つまり署名が少なくとも２つ必要になる。
【００４０】
つまり線形暗号を利用する限り、複数の署名が必要になり暗号文サイズが大きくなってしまうことは避けられない。しかし線形暗号は汎用的結合可能性を持たせるために重要な役割を果たしており、他の暗号方式で代用可能かは自明ではない。
【００４１】
本発明では変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで乱数は１つの利用でありながら、かつ汎用的結合可能性を維持することが可能となっている。これは以下の２つの理由による。まずパラメータとして余分にｈを用意し乱数ρを用いてｈ＾ρも暗号文に含めることによって暗号文の正しさをチェック可能にしている。次に、通常の暗号方式の場合、単純なパラメータを乱数によってランダム化することが普通であるが（例えばパラメータΓ＝（ｐ，ｇ，Ｇ，ＧＴ，ｅ）に対して０以上ｐ−１以下のランダムな整数ρを用いてｇ＾ρを計算する）、変形方式では公開鍵を乱数によってランダム化している（公開鍵ｇ１＝ｇ＾αを０以上ｐ−１以下のランダムな整数ρを用いてｇ１＾ρを計算する）。よって線形暗号を利用せずとも汎用的結合可能性を持たせることが可能となっている。
＜本発明と従来技術の比較おわり＞
【００４２】
＜付録Ａ：ペアリング＞
双線型性を満たすペアリングと呼ばれる演算は楕円曲線上の二点に定義される。なお、楕円曲線上の群は普通加法群であるが、暗号理論学会での慣習に従い乗法群として記述する。
【００４３】
ＧとＧＴを位数ｐの群とする。ここでｐは十分大きい素数である。この二つの群の間の双線型写像ｅ：Ｇ×Ｇ→ＧＴは以下の性質を満たす。
双線型性：任意のｇ，ｈ∈Ｇおよび任意のａ，ｂ∈Ｚに対してｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂが成立する。
非退化性：ｅ（ｇ，ｇ）≠１を満たすｇが存在する。つまり、もしｇがＧの生成元ならｅ（ｇ，ｇ）はＧＴの生成元である。
計算可能性：任意のｇ，ｈ∈Ｇに対して、ｅ（ｇ，ｈ）は効率的に（つまり多項式時間で）計算可能である。詳しくは「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.」や「黒澤馨著“現代暗号への招待”（サイエンス社）」の１３章を参照されたい。
＜付録Ａ：ペアリングおわり＞
【００４４】
＜付録Ｂ：ディジタル署名＞
［Ｂ１：Ｗａｔｅｒｓ双対署名］
Ｗａｔｅｒｓが提案した署名を説明する（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.）。本明細書ではこれをＷａｔｅｒｓ双対署名と呼ぶ。
【００４５】
鍵生成Ｗ．Ｇｅｎ（Γ）：セキュリティパラメータλとΓ＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を入力とし、生成元ｖ，ｖ１，ｖ２，ｗ，ｕ，ｈを群Ｇからランダムに選び、０以上ｐ−１以下のランダムな整数ａ１，ａ２，ｂ，αを選ぶ。τ１：＝ｖｖ１＾ａ１，τ２：＝ｖｖ２＾ａ２とし、検証鍵と秘密鍵をＶＫ：＝（ｇ，ｇ＾ｂ，ｇ＾ａ１，ｇ＾ａ２，ｇ＾ｂａ１，ｇ＾ｂａ２，τ１，τ２，τ１＾ｂ，τ２＾ｂ，ｗ，ｕ，ｈ，ｅ（ｇ，ｇ）＾αａ１ｂ），ＳＫ：＝（ＶＫ，ｇ＾α，ｇ＾αａ１，ｖ，ｖ１，ｖ２）とする。
【００４６】
署名生成Ｗ．Ｓｉｇｎ（ＳＫ，Ｍ）：０以上ｐ−１以下のランダムな整数ｒ１，ｒ２，ｚ１，ｚ２，ｔａｇｋを選び、ｒ：＝ｒ１＋ｒ２とする。署名をσ１：＝ｇ＾αａ１・ｖ＾ｒ，σ２：＝ｇ＾−α・ｖ１＾ｒ・ｇ＾ｚ１，σ３：＝（ｇ＾ｂ）＾−ｚ１，σ４：＝ｖ２＾ｒ・ｇ＾ｚ２，σ５：＝（ｇ＾ｂ）ｇ＾−ｚ２，σ６：＝（ｇ＾ｂ）＾ｒ２，σ７：＝ｇ＾ｒ１，σＫ：＝（ｕ＾Ｍ・ｗ＾ｔａｇｋ・ｈ）＾ｒ１と生成し、ｓｉｇ：＝（σ１，…，σ７，σＫ，ｔａｇｋ）を出力する。
【００４７】
署名検証Ｗ．Ｖｒｆｙ（ＶＫ，Ｍ，ｓｉｇ）：ＶＫ，Ｍと署名σを入力とし、０以上ｐ−１以上のランダムな整数ｓ１，ｓ２，ｔ，ｔａｇｃを選び、ｓ：＝ｓ１＋ｓ２とする。次にＶ１：＝（ｇｂ）＾ｓ，Ｖ２：＝（ｇ＾ｂａ１）＾ｓ１，Ｖ３：＝（ｇ＾ａ１）＾ｓ１，Ｖ４：＝（ｇ＾ｂａ２）＾ｓ２，Ｖ５：＝（ｇ＾ａ２）＾ｓ２，Ｖ６：＝τ１＾ｓ１・τ２＾ｓ２，Ｖ７：＝（τ１＾ｂ）＾ｓ１（τ２＾ｂ）＾ｓ２・ｗ＾−ｔ，Ｅ１：＝（ｕ＾Ｍ・ｗ＾ｔａｇｃ・ｈ）＾ｔ，Ｅ２：＝ｇ＾ｔを生成し、もしｔａｇｃ−ｔａｇｋ≠０ならば、
【数６】
を確認し、これが成立するときかつそのときに限り正当な署名とする。なお、θ：＝１／（ｔａｇｃ−ｔａｇｋ）と置き、ｕ，ｑ∈についてｕ＾Ｍ，ｑ＾Ｍが与えられたとき、上記の検証式に加えてｅ（ｕ＾Ｍ、ｑ）＝ｅ（ｑ＾Ｍ，ｕ）を検証するアルゴリズムを
【数７】
と書くことにする。
【００４８】
［Ｂ２：変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号］
本発明の中で用いた暗号方式はＢｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号（D. Boneh and M. K. Franklin. Identity-Based Encryption from the Weil Pairing. SIAM J. Comput., 32(3):586-615, 2003.）を変形したものである。
【００４９】
Ｓｅｔｕｐ（Γ）：０以上ｐ−１以下のランダムな整数αを選びｇ１：＝ｇ＾αを計算する。またｇ２，ｈを群Ｇからランダムに選ぶ。公開鍵をＰＫ：＝（ｇ，ｇ１，ｇ２，ｈ），秘密鍵をＭＫ：＝ｇ２＾１／αとする（αそのものが秘密鍵でもよい）。
ＥｎｃＰＫ： ０以上ｐ−１以下のランダムな整数ｒを選び、暗号文Ｃ：＝（Ｃ１，Ｃ２，Ｃ３）：＝（ｅ（ｇ，ｇ２）＾ｒ・Ｍ，ｇ１＾ｒ，ｈ＾ｒ）を計算する。
【００５０】
ＤｅｃＰＫ：Ｍ：＝Ｃ１／ｅ（Ｃ２，ｇ２＾１／α）を計算して復号する。
Ｆ−署名：選択メッセージ攻撃に対してＦ−セキュアと呼ばれるより強い安全性の定義を考える。Ｆを効率的に計算可能な全単射であるものとする。署名スキームＳｉｇ＝Ｓｉｇ．｛Ｇｅｎ，Ｓｉｇｎ，Ｖｒｆｙ｝は、以下のゲームによるアドバンテージが無視できるほど小さい場合には、選択メッセージ攻撃下においてＦ−セキュアと呼ばれる。
【００５１】
手順１（セットアップ）：挑戦者は、
【数８】
を発生させてｖｋを攻撃者に送る。
【００５２】
手順２（質問）：攻撃者はメッセージＭｉ∈Ｍを挑戦者に送り、挑戦者は
【数９】
を返信する。これらの質問はｉ＝１〜Ｎまで適応的に挑戦者に送信される。ここで
【数１０】
を攻撃者からの質問であるメッセージのセットＭ１，…，ＭＫ∈Ｍを表すものとする。
【００５３】
手順３（出力）：攻撃者は（ｙ＊，σ＊）を出力する。
【数１１】
を
【数１２】
とした場合に、
【数１３】
かつ、
【数１４】
が成り立つ場合には、攻撃者がゲームに勝利したことになる。
【００５４】
ここで、
【数１５】
を、攻撃者Αがゲームに勝利する確率と定義して、全てのＰＰＴ攻撃者Αについて、
【数１６】
が成り立つとき、署名スキームＳｉｇは、選択メッセージ攻撃に対するＦ−セキュアである。
＜付録Ｂ：ディジタル署名おわり＞
【００５５】
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明＞
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムでは等式の充足可能性（例えばペアリング生成等式）に対して、効率的に非対話識別不可能（ＮＩＷＩ）証明、非対話ゼロ知識（ＮＩＺＫ）証明を行うことができる。証明システムはＧｒｏｔｈ−Ｓａｈａｉコミットメントスキームに基づいている。
【００５６】
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキーム：本スキームでは、まず、双線形写像パラメータ
【数１７】
を生成する。
ＧＳ．ＣｏｍＳｅｔｕｐ（Γ）：共通参照情報ｃｒｓＧＳＣを出力する。
【００５７】
ＧＳ．Ｃｏｍｍｉｔ（ｃｒｓＧＳＣ，ｍ，ｄ）：コミットｍ∈Ｇである入力ｍ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、として出力コミットメント
【数１８】
を生成する。
【００５８】
ＧＳ．ＥｘｐＣｏｍ（ｃｒｓＧＳＣ，ｍ，ｂ，ｄ）：入力ｍ∈Ｚｐ、基数ｂ∈Ｇ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、ｃを
【数１９】
として、出力（ｂ，ｃ）を生成する。
【００５９】
ＧＳ．Ｏｐｅｎｉｎｇ（ｃｒｓＧＳＣ，ｃ，ｍ，ｄ）：ｄが（ｍ，ｃ）に対して正当なデコミットメントである場合、１を出力する。それ以外の場合は、０を出力する。すなわち、
【数２０】
である。（ｂ，ｃ）がｍの累乗で約束される検証の場合には、
【数２１】
となる。
【００６０】
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキームの共通参照情報には２タイプの生成物が存在する。１つのタイプではコミットメントが完全拘束であり、計算量的拘束であり抽出可能である。もう１つのタイプでは、コミットメントが完全秘匿であり、計算量的拘束であり曖昧性を持つ。これらの２つのタイプは計算量的識別不可能である。本証明システムは例えばＤＬＩＮ仮定などの暗号学的仮定裏付けられている（以下、本説明ではＤＬＩＮ仮定を用いるものとする）。ステートメントＳは、変数｛ｘｉ｝ｉ，｛ｙｊ｝ｊ∈Ｇ（ｉ∈［ｍ］，ｊ∈［ｎ］）と、定数｛ａｑ｝ｑ，｛ｂｑ｝ｑ∈Ｇ（ｑ∈［Ｑ］），ｔ∈ＧＴ，｛αｑ，ｉ｝，ｑ，ｉ，｛βｑ，ｊ｝ｑ，ｊ∈Ｚｐと、Ｇ内の値であるコミットメント｛ｃｉ｝ｉ，｛ｄｊ｝ｊにより構成される。ＧｒｏｔｈとＳａｈａｉは、非対話知識証明（ＮＩＰＫ）の構築を以下の式で表した。
【数２２】
【００６１】
この証明πはコミットメントｃ１，…，ｃｍ，ｄ１，…，ｄｎを含む。ＧｒｏｔｈとＳａｈａｉは、これらのコミットメントからペアリング生成式を満足する値ｘ１，…，ｘｍ，ｙ１，…，ｙｎを開くことのできる効率的な抽出機を提供する。ここで、ＣａｍｅｎｉｓｃｈとＳｔａｄｌｅｒの記法（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.）、例えば、
【数２３】
を用いる。
【００６２】
本システムでは、証明者は同形のコミットメントスキームと共通参照情報ＣＲＳとを用いてｗｉｔｎｅｓｓ（証拠、群の元）を遂行する。共通参照情報ＣＲＳには２つのタイプが存在する。１つのタイプは完全拘束コミットメントスキームを、もう１つのタイプは完全秘匿コミットメントスキームを与える。これらの２つのタイプは計算量的識別不可能である。
【００６３】
証明システム：証明システムは以下のアルゴリズムにより構成される。
ＧＳ．Ｓｅｔｕｐ（Γ）：入力
【数２４】
を実行して、出力である証明システムの共通参照情報ＧＳを生成する。共通参照情報ＧＳは、コミットメントスキームの共通参照情報ｃｒｓＧＳＣを含む。
【００６４】
ＧＳ：Ｐｒｏｖｅ（ＧＳ，Ｓ，Ｗ）：ステートメントＳと、証拠Ｗ∈｛ｘｉ｝ｉとを入力とし、証明πを出力する。
ＧＳ．Ｖｒｆｙ（ＧＳ，π）：証明πを入力とし、照明を検証し、正当であれば１を出力し、それ以外は０を出力する。
ＧＳ．ＥｘｔＳｅｔｕｐ（Γ）：共通参照情報ＧＳ（その分布は通常の共通参照情報と一致する）と、正当な証拠を導出するためのトラップドアｔｄｅｘｔとを出力する。
ＧＳ．Ｅｘｔｒａｃｔ（ＧＳ，ｔｄｅｘｔ，π）：証明πと、トラップドアｔｄｅｘｔとを入力とし、各コミットメントＣｉから抽出値ｘｉを抽出して等式を満たす証拠Ｗ∈｛ｘｉ｝ｉを出力する。
【００６５】
ＧＳ．ＳｉｍＳｅｔｕｐ（Γ）：ＧＳ．Ｓｅｔｕｐ（Γ）の出力である通常の共通参照情報と計算量的識別不可能な共通参照情報ＧＳ’と、トラップドアｔｄｓｉｍを出力する。
ＧＳ．ＳｉｍＰｒｏｖｅ（ＧＳ’，ｔｄｓｉｍ，Ｓ）：共通参照情報ＧＳ’と、トラップドアｔｄｓｉｍとを入力とし、ＧＳ．Ｖｒｆｙ（ＧＳ’，π）＝１を満たすステートメントＳの証明πを出力する。
【００６６】
セキュリティ特性：本証明システムは以下の特性を満足する。
正当性：全ての
【数２５】
について、ＧＳ．Ｖｆｒｙ（ＧＳ，π）→１を満たす。
【００６７】
抽出性：
【数２６】
および、証明πについて、ＧＳ．Ｖｆｒｙ（ＧＳ，π）→１である場合に、証拠Ｗ：＝ＧＳ．Ｅｘｔｒａｃｔ（ＧＳ，ｔｄｅｘｔ，π）はステートメントＳを確率１で満足する。
【００６８】
共通参照情報ＣＲＳの識別不可能性：
【数２７】
と、
【数２８】
について、
【数２９】
を満たす。
【００６９】
構成可能な証拠の識別不可能性：全てのＰＰＴ攻撃者Αについて、
【数３０】
が成立する。
【００７０】
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムは、制限されたステートメントのクラス（ΣＺＫはこのクラスを意味する）における構成可能なゼロ知識証明を提供する。
構成可能なゼロ知識：全てのＰＰＴ攻撃者Αについて、
【数３１】
が成立する。
【００７１】
Ｆ−抽出可能非対話知識証明：Ｇｒｏｔｈ−Ｓａｈａｉ証明システムにおいては、非対話知識証明（ＮＩＷＩまたはＮＩＺＫ）から、トラップドアｔｄｅｘｔを使うことにより証拠を抽出できる。しかしながら、この証明システムにおいては、群の元のみがコミットできるため、群Ｇの元を抽出できるのみである。従って、本証明システムにおいてメッセージｍ∈Ｚｐを選択して、ｇｍ∈Ｇをコミットし、証拠であるｇｍを用いて、非対話証明を生成する場合には、ｇｍのみを抽出することができる（これはｍ自身でなく、関数Ｆ（ｍ）：＝ｇｍの出力であることに注意する）。この性質から、Ｇｒｏｔｈ−Ｓａｈａｉ証明システムはＦ−抽出可能性を備えると言われる。
定理２：ＤＬＩＮ仮定が成り立つならば、Ｇｒｏｔｈ−Ｓａｈａｉ証明システムは効率的にインスタンス化できる。
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明おわり＞
【００７２】
＜付録Ｄ：暗号学的仮定＞
素数位数ｐの巡回群Ｇを考える。ｇを群Ｇの生成元とする。ＢＭＳｅｔｕｐは標準的な双線形写像についての群生成アルゴリズムで、セキュリティパラメータλを入力にとって（ｐ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
【００７３】
［Ｄ１：判定線形問題］
判定線形問題とは（Ｇ，ＧＴ，ｐ，ｇ，ｅ）とＩ：＝（ｇ，ｆ，ｖ，ｇ＾ｘ，ｆ＾ｙ）およびＴが与えられたとき（ｘ，ｙは０以上ｐ−１以下のランダムな整数）、ＴがランダムなＧの元かＴ＝ｖｘ＋ｙ∈Ｇであるかどうかを判定する問題である。この優位性は
【数３２】
で定義される。
【００７４】
定義３（判定線形仮定）：判定線形仮定が成立しているとは、判定線形問題が困難である。つまり、どのような攻撃者Αに対しても、
【数３３】
が無視できる。
【００７５】
［Ｄ２：判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題］
判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題とは（Ｇ，ＧＴ，ｐ，ｇ，ｅ）とＩ：＝（ｇ，ｇ＾ｘ，ｇ＾ｙ，ｇ＾ｚ）およびＴが与えられたとき（ｘ，ｙ，ｚは０以上ｐ−１以下のランダムな整数）、ＴがランダムなＧＴの元かＴ＝ｅ（ｇ，ｇ）ｘｙｚ∈ＧＴであるかどうかを判定する問題である。この優位性は
【数３４】
で定義される。
【００７６】
定義４（判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定）：判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定が成立しているとは、判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難である。つまり、どのような攻撃者Αに対しても、
【数３５】
が無視できる。
＜付録Ｄ：暗号学的仮定おわり＞
【００７７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８３】
本発明は、電子通信システムでデータベースにおける情報検索（特許検索、医療データベース検索など）に利用することができる。
【符号の説明】
【００８４】
１０ 紛失通信システム
１００ システムパラメータ生成装置
１１０ 双線形写像パラメータ生成部 １２０ 送信装置用パラメータ生成部
１３０ 受信装置用パラメータ生成部 １４０ 係数生成部
１５０ システムパラメータ生成部
２００ 送信装置
２１０ 鍵対生成部 ２１５ 鍵生成部
２２０ 署名生成部 ２２５ 暗号文生成部
２３０ 暗号化データベース生成部 ２３５ 知識識別不可能証明検証部
２４０ ブラインド復号部 ２４５ 非対話ゼロ知識証明生成部
２５０ 返信生成部 ２９０ 秘密鍵記録部
３００ 受信装置
３１０ 署名検証部 ３１５ 再ランダム化部
３２０ 知識識別不可能証明生成部 ３２５ 要求生成部
３３０ 非対話ゼロ知識証明検証部 ３３５ 復号部
３９０ 要求記録部
【技術分野】
【０００１】
本発明は電気通信システムでデータベースにおける情報検索などに利用される紛失通信システム、紛失通信方法、およびプログラムに関する。
【背景技術】
【０００２】
適応的紛失通信とは、ある受信者が文書（ｍ１，…，ｍＮ）（以下、Ｎは２以上の正の整数）を持つある送信者と通信を行い、受信者が指定した番号ｂに対応する文書ｍｂを得る方法である。送信者は番号ｂについて一切知ることができない。受信者は指定した文書以外を得ることはできない。かつ上記の通信を適応的に何度も繰り返すことができる。この技術は安全なデータベース検索などに応用可能である。従来の適応的紛失通信で、汎用的結合可能性と呼ばれる高い安全性を達成している代表的なものに非特許文献１および非特許文献２がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１では群の要素に対して署名が可能な署名方式を利用しているため非常に特殊な暗号学仮定を必要とし、安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。また、非特許文献２では群要素に対して署名可能な方式は利用しないが、値段付き適応的紛失通信という、機能追加した方式であり、かつ安全性を証明するために通常の署名より強い安全性をもつ署名方式を利用している。そのため、上記とは別の強い暗号学的仮定が必要になり、やはり安全性の根拠において通常の暗号学的仮定を用いたものと比較して信頼性が低い。
【０００５】
本願の出願人による未公開の先願である特願２０１１−９６１８４号に記載されている方式では、特殊な暗号学的仮定を用いる問題を解決し、標準的な暗号学的仮定である判定線形仮定だけを用いることで、汎用的結合可能性を持つ適応的紛失通信を実現している。しかし、利用している暗号方式が乱数を２つ用いる方式であるため、署名の数が多く、暗号文のサイズが大きくなり非効率的であるという問題が解決されていなかった。
【０００６】
そこで、本発明では、標準的な暗号学的仮定だけを用い、かつ汎用的結合可能性をもつことが証明可能でありながら、暗号文のサイズを削減した効率的な適応的紛失通信を実現できる紛失通信システムを提供する。
【課題を解決するための手段】
【０００７】
本発明の紛失通信システムは、システムパラメータ生成装置、送信装置、受信装置からなる。システムパラメータ生成装置は、双線形写像パラメータ生成部と送信装置用パラメータ生成部と受信装置用パラメータ生成部と係数生成部とシステムパラメータ生成部を備える。双線形写像パラメータ生成部は、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する。送信装置用パラメータ生成部は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する。受信装置用パラメータ生成部は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する。係数生成部は、生成元から係数群を計算する。システムパラメータ生成部は、双線形写像パラメータと送信装置用パラメータと受信装置用パラメータと係数群から、共通参照情報を生成し、共通参照情報を送信装置および受信装置へ送信する。
【０００８】
送信装置は、鍵対生成部と鍵生成部と署名生成部と暗号文生成部と暗号化データベース生成部と知識識別不可能証明検証部とブラインド復号部と非対話ゼロ知識証明生成部と返信生成部と秘密鍵記録部を備える。鍵対生成部は、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する。鍵生成部は、秘密鍵を生成し、鍵対と秘密鍵から計算した係数から、公開鍵を生成する。署名生成部は、０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、乱数ρ１，…，ρＮに対する署名を生成する。暗号文生成部は、文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と公開鍵と乱数ρｊと署名と鍵対と共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する。暗号化データベース生成部は、公開鍵と暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、暗号化データベースを受信装置に送信する。知識識別不可能証明検証部は、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する。ブラインド復号部は、知識識別不可能証明が正しい場合に、秘密鍵と共通参照情報を用いて、ブラインド復号結果を生成する。非対話ゼロ知識証明生成部は、要求Ｑとブラインド復号結果と公開鍵と秘密鍵と共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する。返信生成部は、ブラインド復号結果と非対話ゼロ知識証明から、返信Ｒを生成し、返信Ｒを受信装置へ送信する。秘密鍵記録部は、共通参照情報と暗号化データベースと秘密鍵を記録する。
【０００９】
受信装置は、署名検証部と再ランダム化部と知識識別不可能証明生成部と要求生成部と非対話ゼロ知識証明検証部と復号部と要求記録部を備える。署名検証部は、暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、暗号文Ｃ１，…，ＣＮに含まれる署名を検証し、暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、暗号文Ｃ１，…，ＣＮ全てについて署名が正しい署名であると判定され、暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Ｃξを出力する。再ランダム化部は、公開鍵と共通参照情報を用いて、暗号文Ｃξから、再ランダム化暗号文を生成する。知識識別不可能証明生成部は、暗号文Ｃξと再ランダム化暗号文と公開鍵と共通参照情報から、知識識別不可能証明および知識識別不可能証明検証手段で利用される係数θを生成する。要求生成部は、再ランダム化暗号文と知識識別不可能証明から、要求Ｑを生成し、要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、要求Ｑと係数θを送信装置に送信する。非対話ゼロ知識証明検証部は、返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、非対話ゼロ知識証明を検証する。復号部は、非対話ゼロ知識証明が正しい場合に、Ｑｐｒｉｖと暗号文Ｃξと共通参照情報を用いて、ブラインド復号結果から、文書ｍξを計算して出力する。要求記録部は、共通参照情報と暗号化データベースと公開鍵と要求ＱとＱｐｒｉｖを記録する。
【発明の効果】
【００１０】
本発明の紛失通信システムは、暗号方式として、Ｂｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号を変形した変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を持たせることが可能となっている。
【００１１】
したがって、本発明の紛失通信システムによれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。
【図面の簡単な説明】
【００１２】
【図１】実施例１に係る紛失通信システムの構成を示すブロック図。
【図２】実施例１に係る紛失通信システムの動作を示すシーケンス図。
【図３】実施例１のシステムパラメータ生成装置の動作を示すフローチャート。
【図４】実施例１の送信装置が暗号化データベースを生成する動作を示すフローチャート。
【図５】実施例１の受信装置が要求を生成する動作を示すフローチャート。
【図６】実施例１の送信装置が返信を生成する動作を示すフローチャート。
【図７】実施例１の受信装置が復号する動作を示すフローチャート。
【図８】本発明の紛失通信システムと従来技術との違いを示す表。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
本明細書では、Ｎを２以上の整数、＾をべき乗を示す記号とする。
【数１】
と表記されている場合、アルゴリズム内部で乱数を発生させてランダムに出力することを意味する。また、
【数２】
と表記されている場合、素数ｐを法とする整数環Ｚｐからランダムに値を選択することを意味する。
【００１５】
本発明では、Ｇｒｏｔｈ−Ｓａｈａｉ証明を利用する。Ｇｒｏｔｈ−Ｓａｈａｉ証明のアルゴリズム、簡単な説明は付録Ｃを参照されたい（完全な詳細は、「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.」参照）。双線形写像については付録Ａを、Ｗａｔｅｒｓ双対署名については付録Ｂ１を、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号については付録Ｂ２を参照されたい。
【実施例１】
【００１６】
まず、図１、図２を参照して、本発明の実施例１に係る紛失通信システム１０の動作の概略を説明する。図１は本実施例に係る紛失通信システム１０の構成を示すブロック図である。図２は本実施例に係る紛失通信システム１０の動作を示すシーケンス図である。
【００１７】
本実施例の紛失通信システム１０は、システムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。
【００１８】
システムパラメータ生成装置１００は、セキュリティパラメータλを入力とし、共通参照情報ｃｒｓを生成し、送信装置２００および受信装置３００に送信する（Ｓ１０１）。送信装置２００は、文書ｍ１，…，ｍＮを入力とし、公開鍵ｐｋと暗号文Ｃ１，…，ＣＮを含む暗号化データベースＴを生成し、暗号化データベースＴを受信装置３００に送信する（Ｓ２０１）。受信装置３００は、暗号化データベースＴとインデックスξを入力とし、再ランダム化暗号文ｄと知識識別不可能証明πを含む要求Ｑを生成し、送信装置２００へ送信する（Ｓ３０１）。送信装置２００は、要求Ｑを入力とし、ブラインド復号結果ａと非対話ゼロ知識証明δを含む返信Ｒを生成し、受信装置３００に送信する（Ｓ２０２）。受信装置３００は、返信Ｒを入力とし、文書ｍξを出力する（Ｓ３０２）。
【００１９】
次に、図３から図７を参照して、本発明の実施例１に係る紛失通信システム１０の動作をさらに詳細に説明する。図３は本実施例のシステムパラメータ生成装置がシステムパラメータを生成する動作を示すフローチャートである。図４は本実施例の送信装置が暗号化データベースを生成する動作を示すフローチャートである。図５は本実施例の受信装置が要求を生成する動作を示すフローチャートである。図６は本実施例の送信装置が返信を生成する動作を示すフローチャートである。図７は本実施例の受信装置が復号する動作を示すフローチャートである。
【００２０】
以下、実際に行われる手続きの順に説明してゆく。前述したように本実施例の紛失通信システム１０はシステムパラメータ生成装置１００、送信装置２００、受信装置３００からなる。システムパラメータ生成装置１００は、双線形写像パラメータ生成部１１０と送信装置用パラメータ生成部１２０と受信装置用パラメータ生成部１３０と係数生成部１４０とシステムパラメータ生成部１５０を備える。
【００２１】
双線形写像パラメータ生成部１１０は、セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する（Ｓ１１０）。
【００２２】
送信装置用パラメータ生成部１２０は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する（Ｓ１２０）。
受信装置用パラメータ生成部１３０は、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する（Ｓ１３０）。
【００２３】
係数生成部１４０は、０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζおよびｈ：＝ｇ＾ｙｈを計算する（Ｓ１４０）。
システムパラメータ生成部１５０は、双線形写像パラメータΓと送信装置用パラメータＧＳＳと受信装置用パラメータＧＳRと係数ｇ２および係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、共通参照情報ｃｒｓを送信装置２００および受信装置３００へ送信する（Ｓ１５０）。
【００２４】
送信装置２００は、鍵対生成部２１０と鍵生成部２１５と署名生成部２２０と暗号文生成部２２５と暗号化データベース生成部２３０と秘密鍵記録部２９０を備える。
鍵対生成部２１０は、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する（Ｓ２１０）。
【００２５】
鍵生成部２１５は、０以上ｐ−１以下のランダムな秘密鍵αを生成し、秘密鍵αと共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、鍵対ＶＫと係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する（Ｓ２１５）。
署名生成部２２０は、文書ｍ１，…，ｍＮを入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、乱数ρｊに対する署名ｓｉｇｊを生成する（Ｓ２２０）。
【００２６】
暗号文生成部２２５は、文書ｍ１，…，ｍＮと公開鍵ｐｋと乱数ρｊと署名ｓｉｇｊと鍵対ＶＫに含まれる値ｕと共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する（Ｓ２２５）。
暗号化データベース生成部２３０は、公開鍵ｐｋと暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、暗号化データベースＴを受信装置３００に送信する（Ｓ２３０）。
【００２７】
秘密鍵記録部２９０は、秘密鍵αを記録する（Ｓ２９０）。
受信装置３００は、署名検証部３１０と再ランダム化部３１５と知識識別不可能証明生成部３２０と要求生成部３２５と要求記録部３９０を備える。
【００２８】
署名検証部３１０は、暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて暗号文Ｃｊに含まれる署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証する（Ｓ３１１）。署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止する（Ｓ３９０４）。ｊ＝１，…，Ｎのすべてについて暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証する（Ｓ３１２）。いずれかが満たさないと判定されると停止する（Ｓ３９０５）。暗号文Ｃ１，…，ＣＮ全てについて署名ｓｉｇｊが正しい署名であると判定され、暗号文Ｃ１，…，ＣＮ全てについて暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、インデックスξで指定した暗号文Ｃξを出力する（Ｓ３１３）。
【００２９】
再ランダム化部３１５は、０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、公開鍵ｐｋと共通参照情報ｃｒｓと暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、再ランダム化暗号文ｄを生成する（Ｓ３１５）。
【００３０】
知識識別不可能証明生成部３２０は、暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、暗号文Ｃξと再ランダム化暗号文ｄと公開鍵ｐｋと共通参照情報ｃｒｓを用いて、知識識別不可能証明πを
【数３】
により生成する（Ｓ３２０）。なお、記法
【数４】
は共通参照情報ＧＳの下で、コロン以降の等式を満たす知識Ｗ＝（ｗ１，ｗ２）の非対話知識識別不可能証明を表す。括弧でくくられた（ｗ１，ｗ２）以外の情報は検証者に知られているものとする。
【００３１】
要求生成部３２５は、再ランダム化暗号文ｄと知識識別不可能証明πから、要求Ｑ：＝（ｄ，π）を生成し、要求Ｑとインデックスξと乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、要求Ｑおよび係数θを送信装置２００に送信する（Ｓ３２５）。
要求記録部３９０は、要求ＱおよびＱｐｒｉｖを記録する（Ｓ３９０）。
送信装置２００は、さらに、知識識別不可能証明検証部２３５とブラインド復号部２４０と非対話ゼロ知識証明生成部２４５と返信生成部２５０を備える。
【００３２】
知識識別不可能証明検証部２３５は、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、要求Ｑに含まれる知識識別不可能証明πを検証する（Ｓ２３５）。正しい証明でない場合は、停止する（Ｓ２９１１）。
【００３３】
ブラインド復号部２４０は、知識識別不可能証明πが正しい場合に、秘密鍵αと共通参照情報ｃｒｓを用いて、要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成する（Ｓ２４０）。
【００３４】
非対話ゼロ知識証明生成部２４５は、再ランダム化暗号文ｄとブラインド復号結果ａと公開鍵ｐｋと秘密鍵αと共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数５】
により生成する（Ｓ２４５）。
【００３５】
返信生成部２５０は、ブラインド復号結果ａと非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、返信Ｒを受信装置３００へ送信する（Ｓ２５０）。
受信装置３００は、さらに、非対話ゼロ知識証明検証部３３０と復号部３３５を備える。
【００３６】
非対話ゼロ知識証明検証部３３０は、返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、非対話ゼロ知識証明δを検証する（Ｓ３３０）。正しい証明でない場合は、停止する（Ｓ３９１１）。
復号部３３５は、非対話ゼロ知識証明δが正しい場合に、Ｑｐｒｉｖと暗号文Ｃξと共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、ブラインド復号結果ａから文書ｍξを出力する（Ｓ３３５）。
【００３７】
このように、本実施例の紛失通信システム１０は、暗号方式として、Ｂｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号を変形した変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで、乱数は１つの利用でありながら汎用的結合可能性を持たせることが可能となっている。したがって、本実施例の紛失通信システム１０によれば、安全性の根拠となる仮定が標準的であり、かつ暗号文サイズが小さい効率的な適応的紛失通信を実現できる。
【００３８】
＜本発明と従来技術の比較＞
次に、図８を参照して、本発明と従来技術との比較について説明する。図８は本発明の紛失通信システムと従来技術との違いを示す表である。図８は、左隅列に本明細書における非特許文献番号を記した。また、ＵＣとは安全性が汎用的結合可能性を満たしていることを示す。ｑ−ｈｉｄｄｅｎＬＲＳＷ仮定など、ｑ−が接頭についている仮定は、暗号の分野でｑ−仮定と呼ばれ、標準的な暗号学的仮定であるＲＳＡ仮定、ＤＢＤＨ（判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）仮定、ＤＬＩＮ（判定線形）仮定に比べて安全性の根拠に信頼がおけない。πは送信装置が生成する知識識別不可能証明を表しており、｜π｜はその群要素の数を表している。知識識別不可能証明のサイズは表では同一として扱ったが厳密にはそれぞれのサイズは異なる。しかしこのサイズは暗号文のπ以外の群要素数に比例して大きくなるので提案方式のπのサイズは他のものと比べて大きくならない。他の方式と比べてＤＢＤＨ仮定が必要になっているが、ＤＢＤＨ仮定はごく標準的な仮定であるので、安全性は信頼できる。
【００３９】
非特許文献１、２の紛失通信システムでは、送信装置は線形暗号方式により暗号文（ｕ１＾ρ１，ｕ２＾ρ２，ｇ１＾ρ１，ｇ２＾ρ２，ζ＾ρ１＋ρ２・ｍ）を生成し、群Ｇの要素であるｕ１＾ρ１とｕ２＾ρ２への署名を生成するか（非特許文献１の方式）、Ｚｐの要素ρ１とρ２への署名を生成し（非特許文献２の方式はこれに近い）、これらを受信装置に送信している。つまり署名が少なくとも２つ必要になる。
【００４０】
つまり線形暗号を利用する限り、複数の署名が必要になり暗号文サイズが大きくなってしまうことは避けられない。しかし線形暗号は汎用的結合可能性を持たせるために重要な役割を果たしており、他の暗号方式で代用可能かは自明ではない。
【００４１】
本発明では変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号を用いることで乱数は１つの利用でありながら、かつ汎用的結合可能性を維持することが可能となっている。これは以下の２つの理由による。まずパラメータとして余分にｈを用意し乱数ρを用いてｈ＾ρも暗号文に含めることによって暗号文の正しさをチェック可能にしている。次に、通常の暗号方式の場合、単純なパラメータを乱数によってランダム化することが普通であるが（例えばパラメータΓ＝（ｐ，ｇ，Ｇ，ＧＴ，ｅ）に対して０以上ｐ−１以下のランダムな整数ρを用いてｇ＾ρを計算する）、変形方式では公開鍵を乱数によってランダム化している（公開鍵ｇ１＝ｇ＾αを０以上ｐ−１以下のランダムな整数ρを用いてｇ１＾ρを計算する）。よって線形暗号を利用せずとも汎用的結合可能性を持たせることが可能となっている。
＜本発明と従来技術の比較おわり＞
【００４２】
＜付録Ａ：ペアリング＞
双線型性を満たすペアリングと呼ばれる演算は楕円曲線上の二点に定義される。なお、楕円曲線上の群は普通加法群であるが、暗号理論学会での慣習に従い乗法群として記述する。
【００４３】
ＧとＧＴを位数ｐの群とする。ここでｐは十分大きい素数である。この二つの群の間の双線型写像ｅ：Ｇ×Ｇ→ＧＴは以下の性質を満たす。
双線型性：任意のｇ，ｈ∈Ｇおよび任意のａ，ｂ∈Ｚに対してｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂが成立する。
非退化性：ｅ（ｇ，ｇ）≠１を満たすｇが存在する。つまり、もしｇがＧの生成元ならｅ（ｇ，ｇ）はＧＴの生成元である。
計算可能性：任意のｇ，ｈ∈Ｇに対して、ｅ（ｇ，ｈ）は効率的に（つまり多項式時間で）計算可能である。詳しくは「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.」や「黒澤馨著“現代暗号への招待”（サイエンス社）」の１３章を参照されたい。
＜付録Ａ：ペアリングおわり＞
【００４４】
＜付録Ｂ：ディジタル署名＞
［Ｂ１：Ｗａｔｅｒｓ双対署名］
Ｗａｔｅｒｓが提案した署名を説明する（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.）。本明細書ではこれをＷａｔｅｒｓ双対署名と呼ぶ。
【００４５】
鍵生成Ｗ．Ｇｅｎ（Γ）：セキュリティパラメータλとΓ＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を入力とし、生成元ｖ，ｖ１，ｖ２，ｗ，ｕ，ｈを群Ｇからランダムに選び、０以上ｐ−１以下のランダムな整数ａ１，ａ２，ｂ，αを選ぶ。τ１：＝ｖｖ１＾ａ１，τ２：＝ｖｖ２＾ａ２とし、検証鍵と秘密鍵をＶＫ：＝（ｇ，ｇ＾ｂ，ｇ＾ａ１，ｇ＾ａ２，ｇ＾ｂａ１，ｇ＾ｂａ２，τ１，τ２，τ１＾ｂ，τ２＾ｂ，ｗ，ｕ，ｈ，ｅ（ｇ，ｇ）＾αａ１ｂ），ＳＫ：＝（ＶＫ，ｇ＾α，ｇ＾αａ１，ｖ，ｖ１，ｖ２）とする。
【００４６】
署名生成Ｗ．Ｓｉｇｎ（ＳＫ，Ｍ）：０以上ｐ−１以下のランダムな整数ｒ１，ｒ２，ｚ１，ｚ２，ｔａｇｋを選び、ｒ：＝ｒ１＋ｒ２とする。署名をσ１：＝ｇ＾αａ１・ｖ＾ｒ，σ２：＝ｇ＾−α・ｖ１＾ｒ・ｇ＾ｚ１，σ３：＝（ｇ＾ｂ）＾−ｚ１，σ４：＝ｖ２＾ｒ・ｇ＾ｚ２，σ５：＝（ｇ＾ｂ）ｇ＾−ｚ２，σ６：＝（ｇ＾ｂ）＾ｒ２，σ７：＝ｇ＾ｒ１，σＫ：＝（ｕ＾Ｍ・ｗ＾ｔａｇｋ・ｈ）＾ｒ１と生成し、ｓｉｇ：＝（σ１，…，σ７，σＫ，ｔａｇｋ）を出力する。
【００４７】
署名検証Ｗ．Ｖｒｆｙ（ＶＫ，Ｍ，ｓｉｇ）：ＶＫ，Ｍと署名σを入力とし、０以上ｐ−１以上のランダムな整数ｓ１，ｓ２，ｔ，ｔａｇｃを選び、ｓ：＝ｓ１＋ｓ２とする。次にＶ１：＝（ｇｂ）＾ｓ，Ｖ２：＝（ｇ＾ｂａ１）＾ｓ１，Ｖ３：＝（ｇ＾ａ１）＾ｓ１，Ｖ４：＝（ｇ＾ｂａ２）＾ｓ２，Ｖ５：＝（ｇ＾ａ２）＾ｓ２，Ｖ６：＝τ１＾ｓ１・τ２＾ｓ２，Ｖ７：＝（τ１＾ｂ）＾ｓ１（τ２＾ｂ）＾ｓ２・ｗ＾−ｔ，Ｅ１：＝（ｕ＾Ｍ・ｗ＾ｔａｇｃ・ｈ）＾ｔ，Ｅ２：＝ｇ＾ｔを生成し、もしｔａｇｃ−ｔａｇｋ≠０ならば、
【数６】
を確認し、これが成立するときかつそのときに限り正当な署名とする。なお、θ：＝１／（ｔａｇｃ−ｔａｇｋ）と置き、ｕ，ｑ∈についてｕ＾Ｍ，ｑ＾Ｍが与えられたとき、上記の検証式に加えてｅ（ｕ＾Ｍ、ｑ）＝ｅ（ｑ＾Ｍ，ｕ）を検証するアルゴリズムを
【数７】
と書くことにする。
【００４８】
［Ｂ２：変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号］
本発明の中で用いた暗号方式はＢｏｎｅｈ−ＦｒａｎｋｌｉｎのＩＤベース暗号（D. Boneh and M. K. Franklin. Identity-Based Encryption from the Weil Pairing. SIAM J. Comput., 32(3):586-615, 2003.）を変形したものである。
【００４９】
Ｓｅｔｕｐ（Γ）：０以上ｐ−１以下のランダムな整数αを選びｇ１：＝ｇ＾αを計算する。またｇ２，ｈを群Ｇからランダムに選ぶ。公開鍵をＰＫ：＝（ｇ，ｇ１，ｇ２，ｈ），秘密鍵をＭＫ：＝ｇ２＾１／αとする（αそのものが秘密鍵でもよい）。
ＥｎｃＰＫ： ０以上ｐ−１以下のランダムな整数ｒを選び、暗号文Ｃ：＝（Ｃ１，Ｃ２，Ｃ３）：＝（ｅ（ｇ，ｇ２）＾ｒ・Ｍ，ｇ１＾ｒ，ｈ＾ｒ）を計算する。
【００５０】
ＤｅｃＰＫ：Ｍ：＝Ｃ１／ｅ（Ｃ２，ｇ２＾１／α）を計算して復号する。
Ｆ−署名：選択メッセージ攻撃に対してＦ−セキュアと呼ばれるより強い安全性の定義を考える。Ｆを効率的に計算可能な全単射であるものとする。署名スキームＳｉｇ＝Ｓｉｇ．｛Ｇｅｎ，Ｓｉｇｎ，Ｖｒｆｙ｝は、以下のゲームによるアドバンテージが無視できるほど小さい場合には、選択メッセージ攻撃下においてＦ−セキュアと呼ばれる。
【００５１】
手順１（セットアップ）：挑戦者は、
【数８】
を発生させてｖｋを攻撃者に送る。
【００５２】
手順２（質問）：攻撃者はメッセージＭｉ∈Ｍを挑戦者に送り、挑戦者は
【数９】
を返信する。これらの質問はｉ＝１〜Ｎまで適応的に挑戦者に送信される。ここで
【数１０】
を攻撃者からの質問であるメッセージのセットＭ１，…，ＭＫ∈Ｍを表すものとする。
【００５３】
手順３（出力）：攻撃者は（ｙ＊，σ＊）を出力する。
【数１１】
を
【数１２】
とした場合に、
【数１３】
かつ、
【数１４】
が成り立つ場合には、攻撃者がゲームに勝利したことになる。
【００５４】
ここで、
【数１５】
を、攻撃者Αがゲームに勝利する確率と定義して、全てのＰＰＴ攻撃者Αについて、
【数１６】
が成り立つとき、署名スキームＳｉｇは、選択メッセージ攻撃に対するＦ−セキュアである。
＜付録Ｂ：ディジタル署名おわり＞
【００５５】
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明＞
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムでは等式の充足可能性（例えばペアリング生成等式）に対して、効率的に非対話識別不可能（ＮＩＷＩ）証明、非対話ゼロ知識（ＮＩＺＫ）証明を行うことができる。証明システムはＧｒｏｔｈ−Ｓａｈａｉコミットメントスキームに基づいている。
【００５６】
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキーム：本スキームでは、まず、双線形写像パラメータ
【数１７】
を生成する。
ＧＳ．ＣｏｍＳｅｔｕｐ（Γ）：共通参照情報ｃｒｓＧＳＣを出力する。
【００５７】
ＧＳ．Ｃｏｍｍｉｔ（ｃｒｓＧＳＣ，ｍ，ｄ）：コミットｍ∈Ｇである入力ｍ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、として出力コミットメント
【数１８】
を生成する。
【００５８】
ＧＳ．ＥｘｐＣｏｍ（ｃｒｓＧＳＣ，ｍ，ｂ，ｄ）：入力ｍ∈Ｚｐ、基数ｂ∈Ｇ、共通参照情報ｃｒｓＧＳＣ、デコミットメントｄ、ｃを
【数１９】
として、出力（ｂ，ｃ）を生成する。
【００５９】
ＧＳ．Ｏｐｅｎｉｎｇ（ｃｒｓＧＳＣ，ｃ，ｍ，ｄ）：ｄが（ｍ，ｃ）に対して正当なデコミットメントである場合、１を出力する。それ以外の場合は、０を出力する。すなわち、
【数２０】
である。（ｂ，ｃ）がｍの累乗で約束される検証の場合には、
【数２１】
となる。
【００６０】
Ｇｒｏｔｈ−Ｓａｈａｉコミットメントスキームの共通参照情報には２タイプの生成物が存在する。１つのタイプではコミットメントが完全拘束であり、計算量的拘束であり抽出可能である。もう１つのタイプでは、コミットメントが完全秘匿であり、計算量的拘束であり曖昧性を持つ。これらの２つのタイプは計算量的識別不可能である。本証明システムは例えばＤＬＩＮ仮定などの暗号学的仮定裏付けられている（以下、本説明ではＤＬＩＮ仮定を用いるものとする）。ステートメントＳは、変数｛ｘｉ｝ｉ，｛ｙｊ｝ｊ∈Ｇ（ｉ∈［ｍ］，ｊ∈［ｎ］）と、定数｛ａｑ｝ｑ，｛ｂｑ｝ｑ∈Ｇ（ｑ∈［Ｑ］），ｔ∈ＧＴ，｛αｑ，ｉ｝，ｑ，ｉ，｛βｑ，ｊ｝ｑ，ｊ∈Ｚｐと、Ｇ内の値であるコミットメント｛ｃｉ｝ｉ，｛ｄｊ｝ｊにより構成される。ＧｒｏｔｈとＳａｈａｉは、非対話知識証明（ＮＩＰＫ）の構築を以下の式で表した。
【数２２】
【００６１】
この証明πはコミットメントｃ１，…，ｃｍ，ｄ１，…，ｄｎを含む。ＧｒｏｔｈとＳａｈａｉは、これらのコミットメントからペアリング生成式を満足する値ｘ１，…，ｘｍ，ｙ１，…，ｙｎを開くことのできる効率的な抽出機を提供する。ここで、ＣａｍｅｎｉｓｃｈとＳｔａｄｌｅｒの記法（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.）、例えば、
【数２３】
を用いる。
【００６２】
本システムでは、証明者は同形のコミットメントスキームと共通参照情報ＣＲＳとを用いてｗｉｔｎｅｓｓ（証拠、群の元）を遂行する。共通参照情報ＣＲＳには２つのタイプが存在する。１つのタイプは完全拘束コミットメントスキームを、もう１つのタイプは完全秘匿コミットメントスキームを与える。これらの２つのタイプは計算量的識別不可能である。
【００６３】
証明システム：証明システムは以下のアルゴリズムにより構成される。
ＧＳ．Ｓｅｔｕｐ（Γ）：入力
【数２４】
を実行して、出力である証明システムの共通参照情報ＧＳを生成する。共通参照情報ＧＳは、コミットメントスキームの共通参照情報ｃｒｓＧＳＣを含む。
【００６４】
ＧＳ：Ｐｒｏｖｅ（ＧＳ，Ｓ，Ｗ）：ステートメントＳと、証拠Ｗ∈｛ｘｉ｝ｉとを入力とし、証明πを出力する。
ＧＳ．Ｖｒｆｙ（ＧＳ，π）：証明πを入力とし、照明を検証し、正当であれば１を出力し、それ以外は０を出力する。
ＧＳ．ＥｘｔＳｅｔｕｐ（Γ）：共通参照情報ＧＳ（その分布は通常の共通参照情報と一致する）と、正当な証拠を導出するためのトラップドアｔｄｅｘｔとを出力する。
ＧＳ．Ｅｘｔｒａｃｔ（ＧＳ，ｔｄｅｘｔ，π）：証明πと、トラップドアｔｄｅｘｔとを入力とし、各コミットメントＣｉから抽出値ｘｉを抽出して等式を満たす証拠Ｗ∈｛ｘｉ｝ｉを出力する。
【００６５】
ＧＳ．ＳｉｍＳｅｔｕｐ（Γ）：ＧＳ．Ｓｅｔｕｐ（Γ）の出力である通常の共通参照情報と計算量的識別不可能な共通参照情報ＧＳ’と、トラップドアｔｄｓｉｍを出力する。
ＧＳ．ＳｉｍＰｒｏｖｅ（ＧＳ’，ｔｄｓｉｍ，Ｓ）：共通参照情報ＧＳ’と、トラップドアｔｄｓｉｍとを入力とし、ＧＳ．Ｖｒｆｙ（ＧＳ’，π）＝１を満たすステートメントＳの証明πを出力する。
【００６６】
セキュリティ特性：本証明システムは以下の特性を満足する。
正当性：全ての
【数２５】
について、ＧＳ．Ｖｆｒｙ（ＧＳ，π）→１を満たす。
【００６７】
抽出性：
【数２６】
および、証明πについて、ＧＳ．Ｖｆｒｙ（ＧＳ，π）→１である場合に、証拠Ｗ：＝ＧＳ．Ｅｘｔｒａｃｔ（ＧＳ，ｔｄｅｘｔ，π）はステートメントＳを確率１で満足する。
【００６８】
共通参照情報ＣＲＳの識別不可能性：
【数２７】
と、
【数２８】
について、
【数２９】
を満たす。
【００６９】
構成可能な証拠の識別不可能性：全てのＰＰＴ攻撃者Αについて、
【数３０】
が成立する。
【００７０】
Ｇｒｏｔｈ−Ｓａｈａｉ証明システムは、制限されたステートメントのクラス（ΣＺＫはこのクラスを意味する）における構成可能なゼロ知識証明を提供する。
構成可能なゼロ知識：全てのＰＰＴ攻撃者Αについて、
【数３１】
が成立する。
【００７１】
Ｆ−抽出可能非対話知識証明：Ｇｒｏｔｈ−Ｓａｈａｉ証明システムにおいては、非対話知識証明（ＮＩＷＩまたはＮＩＺＫ）から、トラップドアｔｄｅｘｔを使うことにより証拠を抽出できる。しかしながら、この証明システムにおいては、群の元のみがコミットできるため、群Ｇの元を抽出できるのみである。従って、本証明システムにおいてメッセージｍ∈Ｚｐを選択して、ｇｍ∈Ｇをコミットし、証拠であるｇｍを用いて、非対話証明を生成する場合には、ｇｍのみを抽出することができる（これはｍ自身でなく、関数Ｆ（ｍ）：＝ｇｍの出力であることに注意する）。この性質から、Ｇｒｏｔｈ−Ｓａｈａｉ証明システムはＦ−抽出可能性を備えると言われる。
定理２：ＤＬＩＮ仮定が成り立つならば、Ｇｒｏｔｈ−Ｓａｈａｉ証明システムは効率的にインスタンス化できる。
＜付録Ｃ：Ｇｒｏｔｈ−Ｓａｈａｉ証明おわり＞
【００７２】
＜付録Ｄ：暗号学的仮定＞
素数位数ｐの巡回群Ｇを考える。ｇを群Ｇの生成元とする。ＢＭＳｅｔｕｐは標準的な双線形写像についての群生成アルゴリズムで、セキュリティパラメータλを入力にとって（ｐ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
【００７３】
［Ｄ１：判定線形問題］
判定線形問題とは（Ｇ，ＧＴ，ｐ，ｇ，ｅ）とＩ：＝（ｇ，ｆ，ｖ，ｇ＾ｘ，ｆ＾ｙ）およびＴが与えられたとき（ｘ，ｙは０以上ｐ−１以下のランダムな整数）、ＴがランダムなＧの元かＴ＝ｖｘ＋ｙ∈Ｇであるかどうかを判定する問題である。この優位性は
【数３２】
で定義される。
【００７４】
定義３（判定線形仮定）：判定線形仮定が成立しているとは、判定線形問題が困難である。つまり、どのような攻撃者Αに対しても、
【数３３】
が無視できる。
【００７５】
［Ｄ２：判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題］
判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題とは（Ｇ，ＧＴ，ｐ，ｇ，ｅ）とＩ：＝（ｇ，ｇ＾ｘ，ｇ＾ｙ，ｇ＾ｚ）およびＴが与えられたとき（ｘ，ｙ，ｚは０以上ｐ−１以下のランダムな整数）、ＴがランダムなＧＴの元かＴ＝ｅ（ｇ，ｇ）ｘｙｚ∈ＧＴであるかどうかを判定する問題である。この優位性は
【数３４】
で定義される。
【００７６】
定義４（判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定）：判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定が成立しているとは、判定双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難である。つまり、どのような攻撃者Αに対しても、
【数３５】
が無視できる。
＜付録Ｄ：暗号学的仮定おわり＞
【００７７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８３】
本発明は、電子通信システムでデータベースにおける情報検索（特許検索、医療データベース検索など）に利用することができる。
【符号の説明】
【００８４】
１０ 紛失通信システム
１００ システムパラメータ生成装置
１１０ 双線形写像パラメータ生成部 １２０ 送信装置用パラメータ生成部
１３０ 受信装置用パラメータ生成部 １４０ 係数生成部
１５０ システムパラメータ生成部
２００ 送信装置
２１０ 鍵対生成部 ２１５ 鍵生成部
２２０ 署名生成部 ２２５ 暗号文生成部
２３０ 暗号化データベース生成部 ２３５ 知識識別不可能証明検証部
２４０ ブラインド復号部 ２４５ 非対話ゼロ知識証明生成部
２５０ 返信生成部 ２９０ 秘密鍵記録部
３００ 受信装置
３１０ 署名検証部 ３１５ 再ランダム化部
３２０ 知識識別不可能証明生成部 ３２５ 要求生成部
３３０ 非対話ゼロ知識証明検証部 ３３５ 復号部
３９０ 要求記録部
【特許請求の範囲】
【請求項１】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置は、
セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する送信装置用パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する受信装置用パラメータ生成部と、
前記生成元から係数群を計算する係数生成部と、
前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、
前記送信装置は、
Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する鍵対生成部と、
秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成部と、
０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、前記乱数ρ１，…，ρＮに対する署名を生成する署名生成部と、
文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と前記公開鍵と乱数ρｊと前記署名と前記鍵対と前記共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する暗号文生成部と、
前記公開鍵と前記暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成部と、
要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する知識識別不可能証明検証部と、
前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号部と、
前記要求Ｑと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成部と、
前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Ｒを生成し、前記返信Ｒを前記受信装置へ送信する返信生成部と、
前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録部を備え、
前記受信装置は、
前記暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、前記暗号文Ｃ１，…，ＣＮに含まれる前記署名を検証し、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名が正しい署名であると判定され、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証部と、
前記公開鍵と前記共通参照情報を用いて、前記暗号文Ｃξから、再ランダム化暗号文を生成する再ランダム化部と、
前記暗号文Ｃξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成部と、
前記再ランダム化暗号文と前記知識識別不可能証明から、要求Ｑを生成し、前記要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、前記要求Ｑと前記係数θを送信装置に送信する要求生成部と、
前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証部と、
前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書ｍξを計算して出力する復号部と、
前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録部を備える
ことを特徴とする紛失通信システム。
【請求項２】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置は、
セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する送信装置用パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する受信装置用パラメータ生成部と、
０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζ（以下、＾はべき乗を意味する）およびｈ：＝ｇ＾ｙｈを計算する係数生成部と、
前記双線形写像パラメータΓと前記送信装置用パラメータＧＳＳと前記受信装置用パラメータＧＳRと前記係数ｇ２および前記係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、前記共通参照情報ｃｒｓを前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、
前記送信装置は、
Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する鍵対生成部と、
０以上ｐ−１以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、前記鍵対ＶＫと前記係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する鍵生成部と、
文書ｍ１，…，ｍＮ（以下、Ｎは２以上の正の整数）を入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、前記乱数ρｊに対する署名ｓｉｇｊを生成する署名生成部と、
前記文書ｍ１，…，ｍＮと前記公開鍵ｐｋと前記乱数ρｊと前記署名ｓｉｇｊと前記鍵対ＶＫに含まれる値ｕと前記共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する暗号文生成部と、
前記公開鍵ｐｋと前記暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、前記暗号化データベースＴを前記受信装置に送信する暗号化データベース生成部と、
要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記要求Ｑに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証部と、
前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、前記要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成するブラインド復号部と、
前記再ランダム化暗号文ｄと前記ブラインド復号結果ａと前記公開鍵ｐｋと前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数３６】
により生成する非対話ゼロ知識証明生成部と、
前記ブラインド復号結果ａと前記非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、前記返信Ｒを前記受信装置へ送信する返信生成部と、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと秘密鍵αを記録する秘密鍵記録部を備え、
前記受信装置は、
前記暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれる前記署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証し、前記署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止し、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名ｓｉｇｊが正しい署名であると判定され、前記暗号文Ｃ１，…，ＣＮ全てについて前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証部と、
０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、前記公開鍵ｐｋと前記共通参照情報ｃｒｓと前記暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、前記再ランダム化暗号文ｄを生成する再ランダム化部と、
前記暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、前記Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、前記暗号文Ｃξと前記再ランダム化暗号文ｄと前記公開鍵ｐｋと前記共通参照情報ｃｒｓを用いて、前記知識識別不可能証明πを
【数３７】
により生成する知識識別不可能証明生成部と、
前記再ランダム化暗号文ｄと前記知識識別不可能証明πから、前記要求Ｑ：＝（ｄ，π）を生成し、前記要求Ｑと前記インデックスξと前記乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、前記要求Ｑおよび前記係数θを送信装置に送信する要求生成部と、
前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証部と、
前記非対話ゼロ知識証明δが正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、前記ブラインド復号結果ａから文書ｍξを出力する復号部と、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと前記公開鍵ｐｋと前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録部を備える
ことを特徴とする紛失通信システム。
【請求項３】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する送信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する受信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、前記生成元から係数群を計算する係数生成ステップを実行し、
システムパラメータ生成装置が、前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、
送信装置が、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する鍵対生成ステップを実行し、
送信装置が、秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成ステップを実行し、
送信装置が、０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、前記乱数ρ１，…，ρＮに対する署名を生成する署名生成ステップを実行し、
送信装置が、文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と前記公開鍵と乱数ρｊと前記署名と前記鍵対と前記共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する暗号文生成ステップを実行し、
送信装置が、前記公開鍵と前記暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成ステップを実行し、
送信装置が、前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録ステップを実行し、
受信装置が、前記暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、前記暗号文Ｃ１，…，ＣＮに含まれる前記署名を検証し、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名が正しい署名であると判定され、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証ステップを実行し、
受信装置が、前記公開鍵と前記共通参照情報を用いて、前記暗号文Ｃξから、再ランダム化暗号文を生成する再ランダム化ステップを実行し、
受信装置が、前記暗号文Ｃξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成ステップを実行し、
受信装置が、前記再ランダム化暗号文と前記知識識別不可能証明から、要求Ｑを生成し、前記要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、前記要求Ｑと前記係数θを送信装置に送信する要求生成ステップを実行し、
受信装置が、前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録ステップを実行し、
送信装置が、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する知識識別不可能証明検証ステップを実行し、
送信装置が、前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号ステップを実行し、
送信装置が、前記要求Ｑと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成ステップを実行し、
送信装置が、前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Ｒを生成し、前記返信Ｒを前記受信装置へ送信する返信生成ステップを実行し、
受信装置が、前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証ステップを実行し、
受信装置が、前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書ｍξを計算して出力する復号ステップを実行する
ことを特徴とする紛失通信方法。
【請求項４】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する送信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する受信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζ（以下、＾はべき乗を意味する）およびｈ：＝ｇ＾ｙｈを計算する係数生成ステップを実行し、
システムパラメータ生成装置が、前記双線形写像パラメータΓと前記送信装置用パラメータＧＳＳと前記受信装置用パラメータＧＳRと前記係数ｇ２および前記係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、前記共通参照情報ｃｒｓを前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、
送信装置が、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する鍵対生成ステップを実行し、
送信装置が、０以上ｐ−１以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、前記鍵対ＶＫと前記係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する鍵生成ステップを実行し、
送信装置が、文書ｍ１，…，ｍＮ（以下、Ｎは２以上の正の整数）を入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、前記乱数ρｊに対する署名ｓｉｇｊを生成する署名生成ステップを実行し、
送信装置が、前記文書ｍ１，…，ｍＮと前記公開鍵ｐｋと前記乱数ρｊと前記署名ｓｉｇｊと前記鍵対ＶＫに含まれる値ｕと前記共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する暗号文生成ステップを実行し、
送信装置が、前記公開鍵ｐｋと前記暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、前記暗号化データベースＴを前記受信装置に送信する暗号化データベース生成ステップを実行し、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと秘密鍵αを記録する秘密鍵記録ステップを実行し、
受信装置が、前記暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれる前記署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証し、前記署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止し、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名ｓｉｇｊが正しい署名であると判定され、前記暗号文Ｃ１，…，ＣＮ全てについて前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証ステップを実行し、
受信装置が、０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、前記公開鍵ｐｋと前記共通参照情報ｃｒｓと前記暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、前記再ランダム化暗号文ｄを生成する再ランダム化ステップを実行し、
受信装置が、前記暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、前記Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、前記暗号文Ｃξと前記再ランダム化暗号文ｄと前記公開鍵ｐｋと前記共通参照情報ｃｒｓを用いて、前記知識識別不可能証明πを
【数３８】
により生成する知識識別不可能証明生成ステップを実行し、
受信装置が、前記再ランダム化暗号文ｄと前記知識識別不可能証明πから、前記要求Ｑ：＝（ｄ，π）を生成し、前記要求Ｑと前記インデックスξと前記乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、前記要求Ｑおよび前記係数θを送信装置に送信する要求生成ステップを実行し、
受信装置が、前記共通参照情報ｃｒｓと前記暗号化データベースＴと前記公開鍵ｐｋと前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録ステップを実行し、
送信装置が、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記要求Ｑに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証ステップを実行し、
送信装置が、前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、前記要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成するブラインド復号ステップを実行し、
送信装置が、前記再ランダム化暗号文ｄと前記ブラインド復号結果ａと前記公開鍵ｐｋと前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数３９】
により生成する非対話ゼロ知識証明生成ステップを実行し、
送信装置が、前記ブラインド復号結果ａと前記非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、前記返信Ｒを前記受信装置へ送信する返信生成ステップを実行し、
受信装置が、前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証ステップを実行し、
受信装置が、前記非対話ゼロ知識証明δが正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、前記ブラインド復号結果ａから文書ｍξを出力する復号ステップを実行する
ことを特徴とする紛失通信方法。
【請求項５】
請求項３または４に記載のいずれかの紛失通信方法を実行すべき指令をコンピュータに対してするプログラム。
【請求項１】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置は、
セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する送信装置用パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する受信装置用パラメータ生成部と、
前記生成元から係数群を計算する係数生成部と、
前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、
前記送信装置は、
Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する鍵対生成部と、
秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成部と、
０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、前記乱数ρ１，…，ρＮに対する署名を生成する署名生成部と、
文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と前記公開鍵と乱数ρｊと前記署名と前記鍵対と前記共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する暗号文生成部と、
前記公開鍵と前記暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成部と、
要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する知識識別不可能証明検証部と、
前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号部と、
前記要求Ｑと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成部と、
前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Ｒを生成し、前記返信Ｒを前記受信装置へ送信する返信生成部と、
前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録部を備え、
前記受信装置は、
前記暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、前記暗号文Ｃ１，…，ＣＮに含まれる前記署名を検証し、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名が正しい署名であると判定され、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証部と、
前記公開鍵と前記共通参照情報を用いて、前記暗号文Ｃξから、再ランダム化暗号文を生成する再ランダム化部と、
前記暗号文Ｃξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成部と、
前記再ランダム化暗号文と前記知識識別不可能証明から、要求Ｑを生成し、前記要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、前記要求Ｑと前記係数θを送信装置に送信する要求生成部と、
前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証部と、
前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書ｍξを計算して出力する復号部と、
前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録部を備える
ことを特徴とする紛失通信システム。
【請求項２】
システムパラメータ生成装置、送信装置、受信装置からなる紛失通信システムであって、
前記システムパラメータ生成装置は、
セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する送信装置用パラメータ生成部と、
Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する受信装置用パラメータ生成部と、
０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζ（以下、＾はべき乗を意味する）およびｈ：＝ｇ＾ｙｈを計算する係数生成部と、
前記双線形写像パラメータΓと前記送信装置用パラメータＧＳＳと前記受信装置用パラメータＧＳRと前記係数ｇ２および前記係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、前記共通参照情報ｃｒｓを前記送信装置および前記受信装置へ送信するシステムパラメータ生成部を備え、
前記送信装置は、
Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する鍵対生成部と、
０以上ｐ−１以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、前記鍵対ＶＫと前記係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する鍵生成部と、
文書ｍ１，…，ｍＮ（以下、Ｎは２以上の正の整数）を入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、前記乱数ρｊに対する署名ｓｉｇｊを生成する署名生成部と、
前記文書ｍ１，…，ｍＮと前記公開鍵ｐｋと前記乱数ρｊと前記署名ｓｉｇｊと前記鍵対ＶＫに含まれる値ｕと前記共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する暗号文生成部と、
前記公開鍵ｐｋと前記暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、前記暗号化データベースＴを前記受信装置に送信する暗号化データベース生成部と、
要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記要求Ｑに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証部と、
前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、前記要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成するブラインド復号部と、
前記再ランダム化暗号文ｄと前記ブラインド復号結果ａと前記公開鍵ｐｋと前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数３６】
により生成する非対話ゼロ知識証明生成部と、
前記ブラインド復号結果ａと前記非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、前記返信Ｒを前記受信装置へ送信する返信生成部と、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと秘密鍵αを記録する秘密鍵記録部を備え、
前記受信装置は、
前記暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれる前記署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証し、前記署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止し、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名ｓｉｇｊが正しい署名であると判定され、前記暗号文Ｃ１，…，ＣＮ全てについて前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証部と、
０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、前記公開鍵ｐｋと前記共通参照情報ｃｒｓと前記暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、前記再ランダム化暗号文ｄを生成する再ランダム化部と、
前記暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、前記Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、前記暗号文Ｃξと前記再ランダム化暗号文ｄと前記公開鍵ｐｋと前記共通参照情報ｃｒｓを用いて、前記知識識別不可能証明πを
【数３７】
により生成する知識識別不可能証明生成部と、
前記再ランダム化暗号文ｄと前記知識識別不可能証明πから、前記要求Ｑ：＝（ｄ，π）を生成し、前記要求Ｑと前記インデックスξと前記乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、前記要求Ｑおよび前記係数θを送信装置に送信する要求生成部と、
前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証部と、
前記非対話ゼロ知識証明δが正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、前記ブラインド復号結果ａから文書ｍξを出力する復号部と、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと前記公開鍵ｐｋと前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録部を備える
ことを特徴とする紛失通信システム。
【請求項３】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数と、当該素数位数の巡回乗法群と、前記巡回乗法群の生成元と、双線形写像を含む、双線形写像パラメータを生成する双線形写像パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータを生成する送信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムを実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータを生成する受信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、前記生成元から係数群を計算する係数生成ステップを実行し、
システムパラメータ生成装置が、前記双線形写像パラメータと前記送信装置用パラメータと前記受信装置用パラメータと前記係数群から、共通参照情報を生成し、前記共通参照情報を前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、
送信装置が、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムを実行して、Ｗａｔｅｒｓ双対署名の鍵対を生成する鍵対生成ステップを実行し、
送信装置が、秘密鍵を生成し、前記鍵対と前記秘密鍵から計算した係数から、公開鍵を生成する鍵生成ステップを実行し、
送信装置が、０以上ｐ−１以下のランダムな整数ρ１，…，ρＮを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムを実行して、前記乱数ρ１，…，ρＮに対する署名を生成する署名生成ステップを実行し、
送信装置が、文書ｍ１，…，ｍＮ（Ｎは２以上の正の整数）を入力とし、文書ｍｊ（ｊは１以上Ｎ以下の整数）と前記公開鍵と乱数ρｊと前記署名と前記鍵対と前記共通参照情報から、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊを求め、暗号文Ｃ１，…，ＣＮを生成する暗号文生成ステップを実行し、
送信装置が、前記公開鍵と前記暗号文Ｃ１，…，ＣＮから、暗号化データベースを生成し、前記暗号化データベースを前記受信装置に送信する暗号化データベース生成ステップを実行し、
送信装置が、前記共通参照情報と前記暗号化データベースと前記秘密鍵を記録する秘密鍵記録ステップを実行し、
受信装置が、前記暗号化データベースとインデックスξを入力とし、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムを実行して、前記暗号文Ｃ１，…，ＣＮに含まれる前記署名を検証し、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていることを検証し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名が正しい署名であると判定され、前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証ステップを実行し、
受信装置が、前記公開鍵と前記共通参照情報を用いて、前記暗号文Ｃξから、再ランダム化暗号文を生成する再ランダム化ステップを実行し、
受信装置が、前記暗号文Ｃξと前記再ランダム化暗号文と前記公開鍵と前記共通参照情報から、前記知識識別不可能証明および前記知識識別不可能証明検証手段で利用される係数θを生成する知識識別不可能証明生成ステップを実行し、
受信装置が、前記再ランダム化暗号文と前記知識識別不可能証明から、要求Ｑを生成し、前記要求Ｑおよびインデックスξから、Ｑｐｒｉｖを生成し、前記要求Ｑと前記係数θを送信装置に送信する要求生成ステップを実行し、
受信装置が、前記共通参照情報と前記暗号化データベースと前記公開鍵と前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録ステップを実行し、
送信装置が、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムを実行して、要求Ｑに含まれる知識識別不可能証明を検証する知識識別不可能証明検証ステップを実行し、
送信装置が、前記知識識別不可能証明が正しい場合に、前記秘密鍵と前記共通参照情報を用いて、ブラインド復号結果を生成するブラインド復号ステップを実行し、
送信装置が、前記要求Ｑと前記ブラインド復号結果と前記公開鍵と前記秘密鍵と前記共通参照情報を用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明を生成する非対話ゼロ知識証明生成ステップを実行し、
送信装置が、前記ブラインド復号結果と前記非対話ゼロ知識証明から、返信Ｒを生成し、前記返信Ｒを前記受信装置へ送信する返信生成ステップを実行し、
受信装置が、前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムによって、前記非対話ゼロ知識証明を検証する非対話ゼロ知識証明検証ステップを実行し、
受信装置が、前記非対話ゼロ知識証明が正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報を用いて、前記ブラインド復号結果から、文書ｍξを計算して出力する復号ステップを実行する
ことを特徴とする紛失通信方法。
【請求項４】
システムパラメータ生成装置、送信装置、受信装置を用いる紛失通信方法であって、
システムパラメータ生成装置が、セキュリティパラメータλを入力とし、λビットの素数ｐと、素数位数ｐの巡回乗法群ＧおよびＧＴと、前記巡回乗法群Ｇの生成元ｇと、双線形写像ｅを含む、双線形写像パラメータΓ：＝（ｐ，Ｇ，ＧＴ，ｅ，ｇ）を生成する双線形写像パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の送信装置用パラメータＧＳＳを生成する送信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、Ｇｒｏｔｈ−Ｓａｈａｉ証明のパラメータ設定アルゴリズムＧＳ．Ｓｅｔｕｐ（Γ）を実行して、Ｇｒｏｔｈ−Ｓａｈａｉ証明の受信装置用パラメータＧＳRを生成する受信装置用パラメータ生成ステップを実行し、
システムパラメータ生成装置が、０以上ｐ−１以下の整数からランダムに冪指数ζおよびｙｈを選択し、ｇ２：＝ｇ＾ζ（以下、＾はべき乗を意味する）およびｈ：＝ｇ＾ｙｈを計算する係数生成ステップを実行し、
システムパラメータ生成装置が、前記双線形写像パラメータΓと前記送信装置用パラメータＧＳＳと前記受信装置用パラメータＧＳRと前記係数ｇ２および前記係数ｈから、共通参照情報ｃｒｓ：＝（Γ，ＧＳＳ，ＧＳＲ，ｇ２,ｈ）を生成し、前記共通参照情報ｃｒｓを前記送信装置および前記受信装置へ送信するシステムパラメータ生成ステップを実行し、
送信装置が、Ｗａｔｅｒｓ双対署名の鍵生成アルゴリズムＷ．Ｇｅｎ（Γ）を実行して、Ｗａｔｅｒｓ双対署名の鍵対（ＶＫ，ＳＫ）を生成する鍵対生成ステップを実行し、
送信装置が、０以上ｐ−１以下のランダムな秘密鍵αを生成し、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、ｇ１：＝ｇ＾αを計算し、前記鍵対ＶＫと前記係数ｇ１から、公開鍵ｐｋ：＝（ｇ１，ＶＫ）を生成する鍵生成ステップを実行し、
送信装置が、文書ｍ１，…，ｍＮ（以下、Ｎは２以上の正の整数）を入力とし、ｊ＝１，…，Ｎに対して、０以上ｐ−１以下のランダムな整数ρｊを選択し、Ｗａｔｅｒｓ双対署名の署名生成アルゴリズムＷ．Ｓｉｇｎ（ρｊ）を実行して、前記乱数ρｊに対する署名ｓｉｇｊを生成する署名生成ステップを実行し、
送信装置が、前記文書ｍ１，…，ｍＮと前記公開鍵ｐｋと前記乱数ρｊと前記署名ｓｉｇｊと前記鍵対ＶＫに含まれる値ｕと前記共通参照情報ｃｒｓから、変形Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ暗号の暗号文Ｃｊ＝（c1ｊ，c2ｊ，c3ｊ，c4ｊ，c5ｊ）をＣｊ：＝（ｇ１＾ρｊ，ｈ＾ρｊ，ｍｊ・ｅ（ｇ，ｇ２），ｓｉｇｊ，ｕ＾ρｊ）のように生成する暗号文生成ステップを実行し、
送信装置が、前記公開鍵ｐｋと前記暗号文Ｃ１，…，ＣＮから、暗号化データベースＴ：＝（ｐｋ，Ｃ１，…，ＣＮ）を生成し、前記暗号化データベースＴを前記受信装置に送信する暗号化データベース生成ステップを実行し、
前記共通参照情報ｃｒｓと前記暗号化データベースＴと秘密鍵αを記録する秘密鍵記録ステップを実行し、
受信装置が、前記暗号化データベースＴとインデックスξを入力とし、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれる前記署名ｓｉｇｊを、Ｗａｔｅｒｓ双対署名の署名検証アルゴリズムＷ．Ｖｒｆｙを実行して、検証し、前記署名ｓｉｇｊのいずれかが正しい署名でないと判定されると停止し、ｊ＝１，…，Ｎのすべてについて前記暗号文Ｃｊに含まれるｃ１ｊとｃ２ｊが、ｅ（ｈ，ｃ１ｊ）＝ｅ（ｃ２ｊ，ｇ１）を満たすことを検証し、いずれかが満たさないと判定されると停止し、前記暗号文Ｃ１，…，ＣＮ全てについて前記署名ｓｉｇｊが正しい署名であると判定され、前記暗号文Ｃ１，…，ＣＮ全てについて前記暗号文Ｃｊ毎に各要素が同一の乱数から生成されていると判定された場合には、前記インデックスξで指定した前記暗号文Ｃξを出力する署名検証ステップを実行し、
受信装置が、０以上ｐ−１以下の整数からランダムに冪指数ｖを選択し、前記公開鍵ｐｋと前記共通参照情報ｃｒｓと前記暗号文Ｃξに含まれるｃ１ξを用いて、ｄ：＝ｃ１ξ・ｇ１＾ｖおよびｔ：＝ｇ２＾ｖを計算し、前記再ランダム化暗号文ｄを生成する再ランダム化ステップを実行し、
受信装置が、前記暗号文Ｃξに含まれる署名ｓｉｇξの生成に利用された０以上ｐ−１以下のランダムな整数ｔａｇｋと、前記Ｗａｔｅｒｓ双対署名ｓｉｇξの検証に利用された０以上ｐ−１以下のランダムな整数ｔａｇcを用いて、ｓｉｇξ＼｛ｔａｇｋ｝：＝（ρ１，…，ρＫ）はＷａｔｅｒｓ双対署名からｔａｇｋを除いたものとして、θ：＝１／（ｔａｇｃ−ｔａｇｋ）を生成し、前記暗号文Ｃξと前記再ランダム化暗号文ｄと前記公開鍵ｐｋと前記共通参照情報ｃｒｓを用いて、前記知識識別不可能証明πを
【数３８】
により生成する知識識別不可能証明生成ステップを実行し、
受信装置が、前記再ランダム化暗号文ｄと前記知識識別不可能証明πから、前記要求Ｑ：＝（ｄ，π）を生成し、前記要求Ｑと前記インデックスξと前記乱数ｖから、Ｑｐｒｉｖ：＝（Ｑ，ξ，ｖ）を生成し、前記要求Ｑおよび前記係数θを送信装置に送信する要求生成ステップを実行し、
受信装置が、前記共通参照情報ｃｒｓと前記暗号化データベースＴと前記公開鍵ｐｋと前記要求Ｑと前記Ｑｐｒｉｖを記録する要求記録ステップを実行し、
送信装置が、要求Ｑを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＲ，π）を実行して、前記要求Ｑに含まれる知識識別不可能証明πを検証する知識識別不可能証明検証ステップを実行し、
送信装置が、前記知識識別不可能証明πが正しい場合に、前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、前記要求Ｑに含まれる再ランダム化暗号文ｄから、ａ：＝ｅ（ｄ，ｇ２＾１／α）を計算し、ブラインド復号結果ａを生成するブラインド復号ステップを実行し、
送信装置が、前記再ランダム化暗号文ｄと前記ブラインド復号結果ａと前記公開鍵ｐｋと前記秘密鍵αと前記共通参照情報ｃｒｓを用いて、Ｇｒｏｔｈ−Ｓａｈａｉ証明の非対話ゼロ知識証明δを
【数３９】
により生成する非対話ゼロ知識証明生成ステップを実行し、
送信装置が、前記ブラインド復号結果ａと前記非対話ゼロ知識証明δから、返信Ｒ：＝（ａ，δ）を生成し、前記返信Ｒを前記受信装置へ送信する返信生成ステップを実行し、
受信装置が、前記返信Ｒを入力とし、Ｇｒｏｔｈ−Ｓａｈａｉ証明の証明検証アルゴリズムＧＳ．Ｖｒｆｙ（ＧＳＳ，δ）＝１によって、前記非対話ゼロ知識証明δを検証する非対話ゼロ知識証明検証ステップを実行し、
受信装置が、前記非対話ゼロ知識証明δが正しい場合に、前記Ｑｐｒｉｖと前記暗号文Ｃξと前記共通参照情報ｃｒｓを用いて、ｍξ：＝ｃ３ξ・ｅ（ｇ，ｇ２）＾ｖ／ａを計算して、前記ブラインド復号結果ａから文書ｍξを出力する復号ステップを実行する
ことを特徴とする紛失通信方法。
【請求項５】
請求項３または４に記載のいずれかの紛失通信方法を実行すべき指令をコンピュータに対してするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−１７０１７（Ｐ２０１３−１７０１７Ａ）
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願番号】特願２０１１−１４８０５４（Ｐ２０１１−１４８０５４）
【出願日】平成２３年７月４日（２０１１．７．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願日】平成２３年７月４日（２０１１．７．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]