(57)【要約】【課題】  検証者の必要な計算量がミキサーの数によらず一定の大きさとなる統合シャッフル正当性証明装置を提供する。【解決手段】  順番を表す整数である順序数κに対応して設けられた統合シャッフル正当性証明装置３００であって、コミットメント用公開鍵が入力され、順序数が１からκ−１までの統合シャッフル正当性証明装置による置換証明文を含む置換蓄積コミットメントを外部から受信すると、置換蓄積コミットメントに自装置による置換証明文を付加した置換証明コミットメントをコミットメント用公開鍵で暗号化して外部に送信する置換証明コミットメント装置３１０を有する構成である。【選択図】  図１
2006333193.tif 000002
【特許請求の範囲】
【請求項１】
順番を表す整数である順序数κに対応して設けられ、自装置と該順序数の異なる統合シャッフル正当性証明装置と協調し、ミックスネット入力暗号文が入力されると、該ミックスネット入力暗号文をシャッフルした結果であるミックスネット出力暗号文とシャッフルの正当性を証明するための同一変換知識証明コミットメント及び置換証明コミットメントとを出力し、その後、認証のための挑戦値を受信すると、該挑戦値に対応するレスポンスを出力する単一のシャッフル正当性証明装置の一部を構成する複数の統合シャッフル正当性証明装置であって、
コミットメント用公開鍵が入力され、前記順序数が１からκ−１までの統合シャッフル正当性証明装置による置換証明文を含む置換蓄積コミットメントを外部から受信すると、該置換蓄積コミットメントに自装置による置換証明文を付加した置換証明コミットメントを該コミットメント用公開鍵で暗号化して外部に送信する置換証明コミットメント装置を有する統合シャッフル正当性証明装置。
【請求項２】
順番を表す整数である順序数κに対応して設けられた、複数の統合シャッフル正当性証明装置と協調することで、ミックスネット入力暗号文が入力されると、該ミックスネット入力暗号文をシャッフルした結果であるミックスネット出力暗号文とシャッフルの正当性を証明するための同一変換知識証明コミットメント及び置換証明コミットメントとを出力し、その後、認証のための挑戦値を受信すると、該挑戦値に対応するレスポンスを出力する単一のシャッフル正当性証明装置として動作する証明統合装置であって、
前記順序数が１から前記複数の統合シャッフル正当性証明装置の数である最大数まで割り振られた前記複数の統合シャッフル正当性証明装置のそれぞれとの通信手段と、
前記統合シャッフル正当性証明装置より前記順序数が１からκまでの置換証明文を含む置換証明コミットメントを受信すると、順序数がκ＋１の統合シャッフル正当性証明装置に対して、置換証明文を要求するために該置換証明コミットメントを置換蓄積コミットメントとして送信する置換証明コミットメント統合装置と、
を有する証明統合装置。
【請求項３】
請求項１に記載の統合シャッフル正当性証明装置であって、
前記置換証明コミットメント装置が１又は複数設けられ、
複数の暗号文からなる、前記順序数κが割り振られた入力暗号文列と、ミックス用公開鍵と乱数とが入力されると、該入力暗号文列をシャッフルした後、複数の暗号文からなる、該順序数κが割り振られた出力暗号分列を出力するシャッフル装置と、
共通参照基底より求められ、前記順序数κが割り振られた同一変換コミットメント基底と、該順序数κが割り振られた前記入力暗号分列と乱数とが入力されると、順序数κが割り振られた同一変換知識証明コミットメントを生成して出力する同一変換知識証明コミットメント装置と、
前記順序数κが割り振られた挑戦値と乱数とが入力されると、該順序数κが割り振られたレスポンスを出力するレスポンス生成装置と、
前記複数の統合シャッフル正当性証明装置の数である最大数が割り振られた前記置換証明コミットメントと、該最大数が割り振られた挑戦値と、前記順序数κが割り振られた、分散された秘密鍵とが入力されると、前記置換証明コミットメントを統合した統合置換証明コミットメントの暗号文を生成し、該暗号文の前記分散された秘密鍵による分散復号を出力する置換証明コミットメント統合装置とを有し、
前記１又は複数の置換証明コミットメント装置は、
前記コミットメント用公開鍵と前記順序数κが割り振られた前記置換蓄積コミットメントと乱数とが入力されると、該コミットメント用公開鍵による暗号文からなる、該順序数κが割り振られた前記置換証明コミットメントを生成して出力する、統合シャッフル正当性証明装置。
【請求項４】
請求項２に記載の証明統合装置であって、
前記置換証明コミットメント統合装置が１又は複数設けられ、
ミックス用公開鍵とコミットメント用公開鍵と擬似公開鍵と共通参照基底と、前記ミックス用の公開鍵で暗号化された複数の暗号文からなる、ミックスネット入力暗号文とが入力され、
シャッフルの正当性を検証するための統合シャッフル正当性検証装置との通信手段と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、前記ミックスネット暗号文から順序数κが割り振られた入力暗号文列を生成し、該順序数κを割り振った入力暗号文列を順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた出力暗号文列を受信すると、該出力暗号分列を順序数κ＋１が割り振られた入力暗号分列とする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信した出力暗号文列からミックスネット出力暗号文を生成するミックス装置と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、前記共通参照基底から順序数κが割り振られた同一変換コミットメントを生成し、該順序数κを割り振った同一変換コミットメントを順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた同一変換知識コミットメントを受信すると、該同一変換知識コミットメントを順序数κ＋１が割り振られた同一変換コミットメントとする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信する同一変換コミットメントを統合同一変換コミットメントとして生成する同一変換知識証明コミットメント統合装置と、
前記置換証明コミットメントが統合された統合置換証明コミットメントと前記統合同一変換コミットメントとを統合コミットメントとして前記統合シャッフル正当性検証装置に送信するコミットメント装置と、
前記統合シャッフル正当性検証装置より前記挑戦値を統合した統合挑戦値を受信すると、該統合挑戦値より、前記順序数の最大数＋１が割り振られた挑戦値を生成し、前記複数の統合シャッフル正当性証明装置の順序数κに関して前記順序数の最大数＋１から１まで、順序数κ＋１を割り振った挑戦値を順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、該順序数κが割り振られたレスポンスを受信すると、該レスポンスを順序数κが割り振られた挑戦値とする処理を行って、前記順序数１が割り振られたレスポンスから統合レスポンスを生成するレスポンス統合装置と、
前記順序数の最大数が割り振られた置換証明コミットメントと、該最大数が割り振られた挑戦値とが入力されると、該置換証明コミットメントを統合した統合置換証明コミットメントの暗号文を生成し、前記複数の統合シャッフル正当性証明装置のそれぞれと通信を行って、各統合シャッフル正当性証明装置から、順序数κが割り振られた、分散された秘密鍵による前記統合置換証明コミットメントの暗号文の分散復号結果を受信すると、該分散復号結果から統合置換証明コミットメントの暗号文の復号結果を生成し、該復号結果を対応する統合シャッフル正当性検証装置に送信する統合置換証明コミットメント復号装置とを有し、
前記１又は複数の置換証明コミットメント統合装置は、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、順序数κを割り振った置換蓄積コミットメントを生成し、該順序数κを割り振った置換蓄積コミットメントを順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた置換証明コミットメントを受信すると、該置換証明コミットメントを順序数κ＋１が割り振られた置換蓄積コミットメントとする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信する置換証明コミットメントから前記統合置換証明コミットメントを生成する、証明統合装置。
【請求項５】
順番を表す整数である順序数κに対応して設けられた、複数の統合シャッフル正当性証明装置と協調してシャッフルの正当性を証明する証明統合装置と通信する手段を有する統合シャッフル正当性検証装置であって、
ミックス用公開鍵とコミットメント用公開鍵と疑似公開鍵と共通参照基底と乱数とミックスネット入力暗号文とミックスネット出力暗号文とが入力され、
シャッフルの正当性を証明するための統合同一変換コミットメント及び統合置換証明コミットメントを前記証明統合装置より受信するコミットメント受信装置と、
ランダムな数の列である挑戦値を生成して前記証明統合装置に送信する挑戦値生成装置と、
前記複数の統合シャッフル正当性証明装置の数である最大数が前記順序数として割り振られた置換証明コミットメントと、該最大数が割り振られた挑戦値とが入力されると、前記統合置換証明コミットメントの暗号文を生成し、前記証明統合装置と通信することで、該統合置換証明コミットメントの暗号文の分散復号の結果から求められた復号統合置換証明コミットメントが正しく生成されたか否かを検証する復号統合置換証明コミットメント受信装置と、
前記証明統合装置より統合レスポンスを受信し、該証明統合装置より復号統合置換証明コミットメントを受信するレスポンス受信装置と、
前記統合同一変換コミットメントと前記統合置換証明コミットメントと前記挑戦値と前記統合レスポンスと前記復号統合置換証明コミットメントとから、前記ミックスネット出力暗号文が前記ミックスネット入力暗号文から正しく生成されているか否かを示す検証結果を出力する検証装置と、
を有する統合シャッフル正当性検証装置。
【請求項６】
請求項３に記載の統合シャッフル正当性証明装置であって、
前記置換証明コミットメント装置が複数設けられ、該置換証明コミットメント装置は、
前記コミットメント用公開鍵と順序数κが割り振られた第一置換蓄積コミットメントと乱数とが入力されると、該コミットメント用公開鍵による暗号文からなる、順序数κが割り振られた第一置換証明コミットメントを生成して出力する第一置換証明コミットメント装置と、
前記コミットメント用公開鍵と順序数κが割り振られた第一逆置換蓄積コミットメントと乱数とが入力されると、順序数κが割り振られた第一逆置換証明コミットメントを生成して出力する第一置換証明コミットメント逆送装置と、
前記コミットメント用公開鍵と順序数κが割り振られた第二置換蓄積コミットメントと乱数とが入力されると、コミットメント用公開鍵による暗号文からなる、順序数κが割り振られた第二置換証明コミットメントを生成して出力する第二置換証明コミットメント装置と、
前記コミットメント用公開鍵と順序数κが割り振られた第二逆置換蓄積コミットメンと乱数とが入力されると、順序数κが割り振られた第二逆置換証明コミットメントを生成して出力する第二置換証明コミットメント逆送装置と、
前記コミットメント用公開鍵と順序数κが割り振られた第三置換蓄積コミットメントと乱数とが入力されると、コミットメント用公開鍵による暗号文からなる、順序数κが割り振られた第三置換証明コミットメントを生成して出力する第三置換証明コミットメント装置とを含み、
乱数が入力されると、前記統合置換証明コミットメントの暗号文の前記分散された秘密鍵による分散復号の正当性を証明するためのコミットメントを出力し、該統合置換証明コミットメントの暗号文の該分散された秘密鍵による分散復号の正当性を証明するための挑戦値を受信すると、該統合置換証明コミットメントの暗号文の該分散された秘密鍵による分散復号の正当性を証明するためのレスポンスを、該分散された秘密鍵、該乱数、及び該挑戦値より生成して出力する分散復号証明装置を有する統合シャッフル正当性証明装置。
【請求項７】
請求項４記載の証明統合装置であって、
前記置換証明コミットメント統合装置が複数設けられ、該置換証明コミットメント統合装置は、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、順序数κが割り振られた第一置換蓄積コミットメントを生成し、該順序数κを割り振った第一置換蓄積コミットメントを前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた第一置換証明コミットメントを受信すると、該第一置換証明コミットメントを順序数κ＋１が割り振られた第一置換蓄積コミットメントとする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信する第一置換証明コミットメントを統合第一置換証明コミットメントとして生成する第一置換証明コミットメント統合装置と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して前記最大数から１まで、順序数κを割り振った第一逆置換蓄積コミットメントを、該順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、該順序数κが割り振られた第一逆置換証明コミットメントを受信すると、該第一逆置換証明コミットメントを順序数κ−１が割り振られた第一逆置換蓄積コミットメントとする処理を行って、順序数１が割り振られた第一逆置換証明コミットメントから統合第一逆置換証明コミットメントを生成する第一置換証明コミットメント統合逆送装置と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、順序数κが割り振られた第二置換蓄積コミットメントを生成し、該順序数κを割り振った第二置換蓄積コミットメントを前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた第二置換証明コミットメントを受信すると、該第二置換証明コミットメントを順序数κ＋１が割り振られた第二置換蓄積コミットメントとする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信する第二置換証明コミットメントを統合第二置換証明コミットメントとして生成する第二置換証明コミットメント統合装置と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して前記最大数から１まで、順序数κを割り振った第二逆置換蓄積コミットメントを、該順序数κが割り振られた前記統合シャッフル正当性証明装置に送信し、該順序数κが割り振られた第二逆置換証明コミットメントを受信すると、該第二逆置換証明コミットメントを順序数κ−１が割り振られた第二逆置換蓄積コミットメントとする処理を行って、順序数１が割り振られた第二逆置換証明コミットメントから統合第二逆置換証明コミットメントを生成する第二置換証明コミットメント統合逆送装置と、
前記複数の統合シャッフル正当性証明装置の順序数κに関して１から前記最大数まで、順序数κが割り振られた第三置換蓄積コミットメントを生成し、該順序数κを割り振った第三置換蓄積コミットメントを前記統合シャッフル正当性証明装置に送信し、順序数κが割り振られた第三置換証明コミットメントを受信すると、該第三置換証明コミットメントを順序数κ＋１が割り振られた第三置換蓄積コミットメントとする処理を行って、前記順序数が最大数の統合シャッフル正当性証明装置から受信する第三置換証明コミットメントを統合第三置換証明コミットメントとして生成する第三置換証明コミットメント統合装置とを含み、
前記複数の統合シャッフル正当性証明装置のそれぞれから前記統合置換証明コミットメントの暗号文の前記分散された秘密鍵による分散復号の正当性を証明するためのコミットメントを受信すると、該コミットメントから前記統合置換証明コミットメントの暗号文の復号の正当性を証明するためのコミットメントを生成し、該コミットメントを前記統合シャッフル正当性検証装置に送信し、前記統合置換証明コミットメントの暗号文の前記分散された秘密鍵による分散復号の正当性を証明するための挑戦値を前記統合シャッフル正当性検証装置に送信し、前記複数の統合シャッフル正当性証明装置のそれぞれから前記統合置換証明コミットメントの暗号文の前記分散された秘密鍵による分散復号の正当性を証明するためのレスポンスを受信すると、該レスポンスから前記統合置換証明コミットメントの暗号文の復号の正当性を証明するための統合レスポンスを生成し、該統合レスポンスを前記統合シャッフル正当性検証装置に送信する統合分散復号証明装置を有する証明統合装置。
【請求項８】
請求項５に記載の統合シャッフル正当性検証装置であって、
前記証明統合装置から前記統合置換証明コミットメントの暗号文の復号の正当性を証明するためのコミットメントを受信すると、該統合置換証明コミットメントの暗号文の前記分散された秘密鍵による分散復号の正当性を証明するための挑戦値を生成して該証明統合装置に送信し、該証明統合装置から該統合置換証明コミットメントの暗号文の復号の正当性を証明するための統合レスポンスを受信すると、該統合置換証明コミットメントの暗号文から前記復号統合置換証明コミットメントが正しく生成されているか否かを検証する分散復号検証装置を有する統合シャッフル正当性検証装置。
【請求項９】
請求項１、３及び６のうちいずれか１項記載の統合シャッフル正当性証明装置複数と、請求項２、４及び７のうちいずれか１項記載の証明統合装置と、請求項５及び８のうちいずれか１項記載の統合シャッフル正当性検証装置とを有するミックスネットシステムであって、
前記証明統合装置と前記複数の統合シャッフル正当性証明装置との通信手段と、
前記証明統合装置と前記統合シャッフル正当性検証装置との通信手段とを有し、
前記証明統合装置は、
ミックスネット暗号文が入力され、前記複数の統合シャッフル正当性証明装置のそれぞれと通信を行うことで、ミックスネット暗号文を取得し、該ミックスネット暗号文を前記統合シャッフル正当性検証装置に送信し、その後、シャッフルの正当性を証明するためのコミットメントを統合した統合コミットメントを生成して該統合シャッフル正当性検証装置に送信し、該統合シャッフル正当性検証装置から挑戦値を受信すると、該挑戦値に対応する統合レスポンスを生成して該統合シャッフル正当性検証装置に送信し、統合置換証明コミットメントから復号統合置換証明コミットメントを生成して該統合シャッフル正当性検証装置に送信し、該統合シャッフル正当性検証装置と通信することで、該復号統合置換証明コミットメントの正当性を証明し、
前記統合シャッフル正当性検証装置は、
前記挑戦値を生成すると、該挑戦値を前記証明統合装置に送信し、該証明統合装置との通信により取得したデータから、前記ミックスネット出力暗号文が前記ミックスネット入力暗号文の順番を入れ替えて再暗号化したものであるか否かを調べることで、ミックスネットの処理が正しく行われたか否かを判定した結果を出力する、ミックスネットシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、匿名通信路の構成などに使われる統合証明付シャッフル技術による統合シャッフル正当性証明装置、証明統合装置、統合シャッフル正当性検証装置及びミックスネットシステムに関する。
【背景技術】
【０００２】
［従来の技術（１）］
従来の証明付シャッフルの技術について、例えば、特許文献１（特開２００１−２５１２８９号公報）の記載が参照される。図５に、特許文献１に記載された構成を示す。なお、説明に用いている図面中で、合流する矢印は、矢印の元の情報が、全て集まって矢印の先へ送られることを意味し、分岐する矢印は矢印の元の情報全て又は一部が、それぞれの矢印の先へ送られることを意味する。また、特許文献１の再暗号シャッフルを、以下では、シャッフルと称する。
【０００３】
図５において、暗号文と公開鍵１００がシャッフルステップ１０１に入力されてシャッフルされる。この時入力された暗号文１００とシャッフルを特定する情報であるシャッフル情報１０２が同一変換証明ステップ１０３に送られ、シャッフル情報１０２が置換証明ステップ１０４に送られる。同一変換証明ステップ１０３は同一変換証明文１０５を生成し出力すると同時に、証明文生成に使用した乱数１０６を置換証明ステップ１０４に送る。置換証明ステップ１０４は置換証明文１０７を出力する。リスポンス生成ステップ１０８には同一変換証明文１０５と置換証明文１０４と暗号文と公開鍵１００とシャッフル済み暗号文１０９とを入力し、同一変換証明文１０５と置換証明文１０４と暗号文とにリスポンスを加えてシャッフル証明文１１０を生成し出力する。同一変換証明文１０５は、リスポンスと合さって、入力文の順番の入れ替えや暗号化である暗号文の変換内容の知識を持っていることの証明であると同時に、入力される暗号文が複数の整数の要素となる場合はそれぞれの要素が同じ順番の入れ替えと対応する暗号化の処理とを受けたことの証明でもある。置換証明文１０７は、リスポンスと合さって、入力される暗号文に対しての、順番の入れ替えが正しくなされたことの証明である。
【０００４】
図５に示されるシャッフルとは、入力された暗号文の順序を入れ替えて再び暗号化することである。この処理が正当であることを証明するために、同文献では同一変換証明ステップと置換証明ステップの二つの証明ステップを用いている。この証明対象の分割により同文献ではシャッフル証明文生成の効率化を達成している。
【０００５】
［従来の技術（２）］
従来の証明付シャッフル復号を用いたミックスネットの技術２００について、例えば、非特許文献１（Kazue Sako, Joe Kilian: Receipt-Free Mix-Type Voting Scheme - A Practical Solution to the Implementation of a Voting Booth. EUROCRYPT 1995: 393-403, Springer）の記載が参照される。
【０００６】
図６に示すように、ここでは、複数のミキサー（２０１,２０２，２０３，２０４，２０５，２０６）による証明付シャッフルを、連続して行うことにより、入力された複数の暗号文２０７の順序を入れ替えかつ再暗号化して出力２０８している。各ミキサーが独立して暗号文の順序を入れ替えるため、全てのミキサーがどのように順番を入れ替えたかを知らなければ、全体としてどのように順番が入れ替えたかが分からなくなっている。このようにして、入力された暗号文と出力された暗号文の対応は、全てのミキサーが結託して情報を漏洩しなければ分からない。このような技術は電子投票等で、投票者と投票内容の関係を秘匿したい場合に有効位である。
しかし、本方法では全てのミキサーが結託しさえすれば、入力と出力の対応関係が分かってしまう。そのため、よりこのような結託を起きにくくするために、ミキサーの数を十分に多くすることが重要である。
【０００７】
［従来の技術（３）］
従来の技術（２）以外にも、ミックスネットを用いて電子投票を実現している例が、非特許文献２（Jun Furukawa, Hiroshi Miyauchi, Kengo Mori, Satoshi Obana, Kazue Sako: An Implementation of a Universally Verifiable Electronic Voting Scheme based on Shuffling. Financial Cryptography 2002, : 16-30, LNCS 2339,Springer）に記載されている。ここでは、最初に投票を管轄するセンターが、全ての投票者より投票内容を暗号化した暗号文を受付ける。次にこのセンターが暗号文全ての集合を、複数のミキサーに順番に渡す。各ミキサーはこの暗号文の集合の順序を入れ替えかつ再暗号化した後にセンターに返還する。これをセンターが次のミキサーへ渡すと言った作業を全てのミキサーに関して繰り返す。最後のミキサーから受け取った暗号文を復号して、投票結果を集計する。
【特許文献１】特開２００１−２５１２８９号公報
【非特許文献１】Kazue Sako, Joe Kilian: Receipt-Free Mix-Type Voting Scheme - A Practical Solution to the Implementation of a Voting Booth. EUROCRYPT 1995: 393-403, Springer
【非特許文献２】Jun Furukawa, Hiroshi Miyauchi, Kengo Mori, Satoshi Obana, Kazue Sako: An Implementation of a Universally Verifiable Electronic Voting Scheme based on Shuffling. Financial Cryptography 2002, : 16-30, LNCS 2339,Springer
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記従来の技術は下記記載の問題点を有している。
従来の技術（１）を複数のミキサーで連続して行うことにより、従来の技術（２）で述べられたミックスネットを構成した場合を考える。このようなミックスネットは電子投票を行う際には有効な方法である。しかし、電子投票において、投票の十分な匿名性を求めた場合、上に記したように、ミキサーの数を増やす必要がある。一方、各ミキサーが正しく振る舞ったことを確認しなければ、投票の正当性が確認できないため、従来の技術（１）では示されたように、選挙を監視する人々がミキサーの振る舞いを検証する必要がある。この検証作業に必要な計算量は大きい。すなわち、投票に十分な匿名性を求めた場合、ミキサーの数を多くする必要があり、検証は各ミキサーに関して行う必要があることから、ミックスネット全体の検証には多大な時間がかかることになる。
【０００９】
本発明は上述したような従来の技術が有する問題点を解決するためになされたものであり、検証者の必要な計算量がミキサーの数によらず一定の大きさとなる統合シャッフル正当性証明装置、証明統合装置、統合シャッフル正当性検証装置及びミックスネットシステムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するための本発明の統合シャッフル正当性証明装置は、順番を表す整数である順序数κに対応して設けられ、自装置と該順序数の異なる統合シャッフル正当性証明装置と協調し、ミックスネット入力暗号文が入力されると、該ミックスネット入力暗号文をシャッフルした結果であるミックスネット出力暗号文とシャッフルの正当性を証明するための同一変換知識証明コミットメント及び置換証明コミットメントとを出力し、その後、認証のための挑戦値を受信すると、該挑戦値に対応するレスポンスを出力する単一のシャッフル正当性証明装置の一部を構成する複数の統合シャッフル正当性証明装置であって、
コミットメント用公開鍵が入力され、前記順序数が１からκ−１までの統合シャッフル正当性証明装置による置換証明文を含む置換蓄積コミットメントを外部から受信すると、該置換蓄積コミットメントに自装置による置換証明文を付加した置換証明コミットメントを該コミットメント用公開鍵で暗号化して外部に送信する置換証明コミットメント装置を有する構成である。
【００１１】
本発明によれば、統合シャッフル正当性証明装置は順序数が自分より前の装置から受け取る置換蓄積コミットメントに自装置の置換証明文を付加している。そのため、順序数の順に置換蓄積コミットメントに各統合シャッフル正当性証明装置の置換証明文が蓄積され、シャッフルを行う全ての装置のシャッフルの正当性を証明する情報がまとめられる。その結果、まとめられた情報から全体のシャッフルの検証を効率的に行うことが可能となる。
【００１２】
一方、上記目的を達成するための本発明の証明統合装置は、順番を表す整数である順序数κに対応して設けられた、複数の統合シャッフル正当性証明装置と協調することで、ミックスネット入力暗号文が入力されると、該ミックスネット入力暗号文をシャッフルした結果であるミックスネット出力暗号文とシャッフルの正当性を証明するための同一変換知識証明コミットメント及び置換証明コミットメントとを出力し、その後、認証のための挑戦値を受信すると、該挑戦値に対応するレスポンスを出力する単一のシャッフル正当性証明装置として動作する証明統合装置であって、
前記順序数が１から前記複数の統合シャッフル正当性証明装置の数である最大数まで割り振られた前記複数の統合シャッフル正当性証明装置のそれぞれとの通信手段と、
前記統合シャッフル正当性証明装置より前記順序数が１からκまでの置換証明文を含む置換証明コミットメントを受信すると、順序数がκ＋１の統合シャッフル正当性証明装置に対して、置換証明文を要求するために該置換証明コミットメントを置換蓄積コミットメントとして送信する置換証明コミットメント統合装置と、
を有する構成である。
【００１３】
また、上記目的を達成するための本発明の統合シャッフル正当性検証装置は、順番を表す整数である順序数κに対応して設けられた、複数の統合シャッフル正当性証明装置と協調してシャッフルの正当性を証明する証明統合装置と通信する手段を有する統合シャッフル正当性検証装置であって、
ミックス用公開鍵とコミットメント用公開鍵と疑似公開鍵と共通参照基底と乱数とミックスネット入力暗号文とミックスネット出力暗号文とが入力され、
シャッフルの正当性を証明するための統合同一変換コミットメント及び統合置換証明コミットメントを前記証明統合装置より受信するコミットメント受信装置と、
ランダムな数の列である挑戦値を生成して前記証明統合装置に送信する挑戦値生成装置と、
前記複数の統合シャッフル正当性証明装置の数である最大数が前記順序数として割り振られた置換証明コミットメントと、該最大数が割り振られた挑戦値とが入力されると、前記統合置換証明コミットメントの暗号文を生成し、前記証明統合装置と通信することで、該統合置換証明コミットメントの暗号文の分散復号の結果から求められた復号統合置換証明コミットメントが正しく生成されたか否かを検証する復号統合置換証明コミットメント受信装置と、
前記証明統合装置より統合レスポンスを受信し、該証明統合装置より復号統合置換証明コミットメントを受信するレスポンス受信装置と、
前記統合同一変換コミットメントと前記統合置換証明コミットメントと前記挑戦値と前記統合レスポンスと前記復号統合置換証明コミットメントとから、前記ミックスネット出力暗号文が前記ミックスネット入力暗号文から正しく生成されているか否かを示す検証結果を出力する検証装置と、
を有する構成である。
【００１４】
さらに、上記目的を達成するための本発明のミックスネットシステムは、上記本発明の統合シャッフル正当性証明装置複数と、上記本発明の証明統合装置と、上記本発明の統合シャッフル正当性検証装置とを有するミックスネットシステムであって、
前記証明統合装置と前記複数の統合シャッフル正当性証明装置との通信手段と、
前記証明統合装置と前記統合シャッフル正当性検証装置との通信手段とを有し、
前記証明統合装置は、
ミックスネット暗号文が入力され、前記複数の統合シャッフル正当性証明装置のそれぞれと通信を行うことで、ミックスネット暗号文を取得し、該ミックスネット暗号文を前記統合シャッフル正当性検証装置に送信し、その後、シャッフルの正当性を証明するためのコミットメントを統合した統合コミットメントを生成して該統合シャッフル正当性検証装置に送信し、該統合シャッフル正当性検証装置から挑戦値を受信すると、該挑戦値に対応する統合レスポンスを生成して該統合シャッフル正当性検証装置に送信し、統合置換証明コミットメントから復号統合置換証明コミットメントを生成して該統合シャッフル正当性検証装置に送信し、該統合シャッフル正当性検証装置と通信することで、該復号統合置換証明コミットメントの正当性を証明し、
前記統合シャッフル正当性検証装置は、
前記挑戦値を生成すると、該挑戦値を前記証明統合装置に送信し、該証明統合装置との通信により取得したデータから、前記ミックスネット出力暗号文が前記ミックスネット入力暗号文の順番を入れ替えて再暗号化したものであるか否かを調べることで、ミックスネットの処理が正しく行われたか否かを判定した結果を出力するものである。
【発明の効果】
【００１５】
本発明によれば、複数のミキサーがシャッフルを行うミックスネットの正当性の検証を行うときに、検証者の必要とする計算量がミキサーの数、すなわち、行われるシャッフルの回数に依存しなくなる。これは検証者の負担を軽くすることができるため、ミキサーの数を増やすことを容易にし、より強い匿名性を持ったミックスネットを構成できる。
【発明を実施するための最良の形態】
【００１６】
本発明のミックスネットシステムの実施例について図面を参照して説明する。以下の実施例では、楕円Elgamal暗号を使った例に即して説明する。離散対数問題の難しい巡回群であればよい。
【００１７】
はじめに、本発明にて前提となる事項から順に説明していく。
「記号」
Ｍｋ，ｎ（Ｘ）をＥ上の点のなすｋ行ｎ列の行列とする。
Ｘは楕円Ｅ、ＺｑあるいはElGamal暗号文の空間ＥＣの場合を考える。ただし、ＥＣの点はＥの点二つからなり、Ｍｋ，ｎ（ＥＣ）＝Ｍｋ，２ｎ（Ｅ）である。
今ここで、Ａ∈Ｍｋ，ｎ（Ｘ）とするとき、Ａの（ｉ，ｊ）成分をＡｉｊと記す。
また、Ｂ∈Ｍｎ，ｍ（Ｙ）とするとき、ＡＢはｋ行ｍ列の行列で、その（ｉ，ｊ）成分を、（ＡＢ）ｉｊ＝Σｇ＝１ｎＡｉｇＢｇｊと定義する。
【００１８】
この定義において、乗算は、Ｘ，Ｙが共にＺｑであればＺｑ上の乗算とし、ＸがＺｑで、ＹがＥであれば、楕円曲線のスカラー倍として定義する。一方、加算は、Ｘ，Ｙが共にＺｑであればＺｑ上の加算とし、ＸがＺｑで、ＹがＥであれば、楕円曲線の加算として定義する。
今ここで、Ａ，Ｂ∈Ｍｋ，ｎ（Ｘ）に対して、Ａ◎Ｂを（Ａ◎Ｂ）ｉｊ＝ＡｉｊＢｉｊと定義する。
【００１９】
［楕円Elgamal公開鍵暗号方式］
楕円ElGamal暗号方式は、公開鍵暗号系に属する暗号方式である。最初に、関係ｑ ｍｏｄ３＝２となる素数をｑとし、位数がｑの楕円曲線をＥとし、Ｅの生成元をＧとし、Ｅの単位元をＯとする。すなわち，任意のＥ上の点Ｐは、［ｑ］Ｐ＝Ｏを満たす。ここで、［ｘ］Ｇは、Ｇのｘ倍点を表す。
【００２０】
楕円Elgamal公開鍵暗号方式は次の三つのアルゴリズムからなる。
「鍵生成アルゴリズム」
乱数が入力され、秘密鍵ｘをＺｑの要素ランダムに選び、公開鍵ＭをＭ＝［ｘ］Ｇを計算して求め、秘密鍵ｘと公開鍵Ｍを出力する。
「暗号化アルゴリズム」
平文Ｍ∈Ｅと公開鍵Ｍと乱数とが入力され、ｓをＺｑの要素ランダムに選び、暗号文をＣ＝（Ｇ１，Ｍ１）＝（［ｓ］Ｇ，Ｍ＋［ｓ］Ｍ）と計算し、これを出力する。
「復号アルゴリズム」
暗号文Ｃと秘密鍵ｘが入力され、復号文Ｍ’＝Ｍ１−［ｘ］Ｇ１を出力する。復号アルゴリズムの出力Ｍ’が暗号化された平文Ｍに一致することは、Ｍ’＝Ｍ１−［ｘ］Ｇ１＝Ｍ＋［ｓ］Ｍ−［ｘ］［ｓ］Ｇ＝Ｍ＋［ｓ］Ｍ−［ｓ］Ｍ＝Ｍから明らかである。
「再暗号アルゴリズム」
暗号文（Ｇ１，Ｍ１）が入力され、ランダムに選ばれたＺｑの要素ｔを用いて、再暗号文（Ｇ’１，Ｍ’１）＝（［ｔ］Ｇ＋Ｇ１，［ｓ］Ｍ＋Ｍ１）
を出力する。（Ｇ’１，Ｍ’１）と（Ｇ１，Ｍ１）の復号結果は同じになる。
【００２１】
[再暗号の記号]
Ｃ∈Ｍｋ，１（ＥＣ）、ＹをElGamal暗号文の公開鍵とする。このとき、Ｙ＊Ｃ∈Ｍｋ，１（ＥＣ）を、（Ｙ＊Ｃ）ｉ，１がＣｉのＹを用いて再暗号したものとなるものとする。
また、θ∈Ｍｋ，１（Ｚｑ）である場合、Ｙ＊θ∈Ｍｋ，１（ＥＣ）は、（Ｙ＊θ）ｉが（［θ］Ｇ）ｉに対してＹを用いて再暗号したものとなるものとする。
Ｃ’∈Ｍｋ，１（ＥＣ）である場合、Ｃ＋Ｃ’∈Ｍｋ，１（ＥＣ）は、（Ｃ＋Ｃ’）ｉがＣｉとＣ’ｉの復号文のＥ上での和を暗号化したものとする。
【００２２】
「秘密鍵分散と分散復号」
秘密鍵がｙであり、公開鍵がＹ＝［ｙ］Ｇであるときに、秘密鍵ｙが分散所持されているとする。すなわち、ｙ＝Σκ＝１λｙ（κ）ｍｏｄ ｑが成り立ち、各ｙ（κ）のそれぞれが別個に所持されている。本実施例では、このｙ（κ）を分散された秘密鍵と呼ぶ。
【００２３】
このとき、公開鍵Ｙによる暗号文（Ｇ１，Ｍ１）を完全に復号するには、Ｍ１を各復号用の秘密鍵を用いて計算した値から［ｙ（κ）］Ｇ１を順に引いていく操作を、全てのκに関して行う。
［ｙ（κ）］Ｇ１を秘密鍵ｙ（κ）による分散復号の結果と呼ぶ。
【００２４】
「ミックスネットシステムとミキサー」
ミックスネットシステムは複数のミキサーを有する構成である。本発明では、ミキサーの数をλとする。ミックスネットシステムに用いるElGamal暗号方式の公開鍵をＭとし、これをミックス用の公開鍵とする。ミックスネットシステムに入力される暗号文の列がミックスネット入力暗号文を構成する。
「ミキサー」
このミキサーには１からλまでの順番が付けられている。κ番目のミキサーをＰ（κ）と記す。また、κを順序数と呼ぶ。
「ミックスネット入力暗号文」
ミックスネットに入力されるｋ個の暗号文を、（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋとする。それぞれの暗号文の各要素はＥの元である。
Ｇ（１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＧｉである列ベクトル（ｋ行１列の行列）とし、Ｍ（１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＭｉである列ベクトル（ｋ行１列の行列）とする。
【００２５】
「ミックスネット出力暗号文」
ミックスネットから出力されるｋ個の復号文を、（Ｇ’ｉ，Ｍｉ），ｉ＝１，．．．，ｋとする。それぞれの復号文の各要素はＥの元である。
Ｇ（λ＋１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＧ’ｉである列ベクトル（ｋ行１列の行列）とし、Ｍ（λ＋１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＭ’ｉである列ベクトル（ｋ行１列の行列）とする。
これらはｋ個の暗号文（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋを、ランダムに選ばれたＺｑの要素であるｓｉ（ｉ＝１，．．．，ｋ）と、ミックス用公開鍵Ｍで（［ｓｉ］Ｇ＋Ｇｉ，［ｓｉ］Ｍ＋Ｍｉ），ｉ＝１，．．．，ｋと再暗号化し、さらにそれらの順番を入れ替えたものである。この操作をシャッフルと呼ぶ。
【００２６】
「置換行列」
置換行列について説明する。「置換行列」を、各行各列に０でない成分が唯一存在し、その値がＺｑ上の１であるｋ行ｋ列の正方行列とする。このような置換行列の集合をＰＭｋ，ｋ（Ｚｑ）と表す。φ∈ＰＭｋ，ｋ（Ｚｑ）の逆行列をφ＊と表す。
【００２７】
φ∈ＰＭ４，４（Ｚｑ）の例として、
０，１，０，０
０，０，０，１
０，０，１，０
１，０，０，０
があげられる。
「各ミキサーの入出力」
各ミキサーは統合シャッフル正当性証明装置により実現される。
【００２８】
次に、本実施形態のミックスネットシステムは、入力されるデータをシャッフルする統合シャッフル正当性証明装置と、シャッフルによる同一変換知識証明及び置換証明をまとめる証明統合装置と、まとめられた証明の正当性を検証するための統合シャッフル正当性検証装置を有する構成である。統合シャッフル正当性証明装置は複数設けられている。統合シャッフル正当性証明装置の個数をλとする。統合シャッフル正当性証明装置と証明統合装置が通信回線で接続され、証明統合装置と統合シャッフル正当性検証装置が通信回線で接続されている。以下に各構成について説明する。
【実施例１】
【００２９】
本発明のミックスネットシステムの一部となる統合シャッフル正当性証明装置についての一構成例を、図１を参照して説明する。本発明におけるミックスネットシステムは、λ個のミキサーを有する構成であり、ｋ個の暗号文をシャッフルするものとする。
【００３０】
統合シャッフル正当性証明装置３００は、外部の他の装置とデータを送受信するためのインターフェース部を含む入力装置及び出力装置と、データを保存するための記憶装置と、各部を制御する制御装置とを有するサーバで構成される。制御装置には、プログラムにしたがって所定の処理を実行するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）と、プログラムを格納するためのメモリが設けられている。
【００３１】
図１に示すシャッフル装置３０１、同一変換知識証明コミットメント装置３０９、第一置換証明コミットメント装置３１０、第一置換証明コミットメント逆送装置３１１、第二置換証明コミットメント装置３１２、第二置換証明コミットメント逆送装置３１３、第三置換証明コミットメント装置３１４、レスポンス生成装置３１５、置換証明コミットメント統合装置３１６、及び分散復号証明装置３１７がサーバ内に仮想的に構成される。
【００３２】
統合シャッフル正当性証明装置３００には、自装置が実現するミキサーの順番を表す番号である順序数３０５となるκと、シャッフルする暗号文の個数ｋと、楕円曲線Ｅを表すパラメターと、Ｅの生成子Ｇ∈Ｅ＝Ｍ１，１（Ｅ）とが入力される。また、Ｅ上からランダムに選ばれた点による疑似公開鍵３０６となるＦとミックス用公開鍵３０７ａとなるＭ∈Ｅが統合シャッフル正当性証明装置３００に入力される。これらの情報は記憶装置に格納され、全てのステップのいずれにおいても利用可能となる。入力される暗号文はミックス用公開鍵３０７ａで暗号化されているものとする。
【００３３】
また、順序数３０５のκが入力された統合シャッフル装置の秘密鍵３０８をｙ（κ）∈Ｚｑとする。そして、Ｙ＝Σκ＝１λ［ｙ（κ）］Ｇ∈Ｅ＝Ｍ１，１（Ｅ）をコミットメント用公開鍵３０７ｂとする。図１に示す公開鍵３０７は、上記ミックス用公開鍵３０７ａ及びコミットメント用公開鍵３０７ｂを含むものである。順序数３０５のκが入力された統合シャッフル正当性証明装置３００にｙ（κ）とＹが入力される。統合シャッフル正当性証明装置３００には乱数３０３が入力される。これらの情報も記憶装置に格納される。
【００３４】
統合シャッフル正当性証明装置３００に入力される上述のκ，ｋ，Ｍ，Ｆ，ｙ（κ），Ｙ及び乱数３０３に関しては、その入力を明示的に書かないが、各ステップで記憶装置から自由に読み出すことが可能である。なお、ＯはＥの無限遠点Ｆ’（１）＝Ｇ’（１）＝Ｍ’（１）＝Ｏとする。
【００３５】
[シャッフル装置３０１]
二つのｋ成分列ベクトルである入力暗号文列３０２として、（Ｇ（κ），Ｍ（κ））∈（Ｍｋ，１（Ｅ），Ｍｋ，１（Ｅ））が証明統合装置４００から入力される。次に、ランダムなｋ行ｋ列の置換行列φ（κ）∈ＰＭｋ，ｋ（Ｚｑ）を、乱数３０３を用いて生成する。次に、ランダムなｋ成分列ベクトル(ｋ行１列行列)θ（κ）∈Ｍｋ，１（Ｚｑ）を、乱数３０３を用いて生成する。
【００３６】
φ(κ)、θ(κ)は入力された乱数より一意的に作られるため、入力された乱数にあらかじめ含まれていたと考える。すなわち、以下の装置において、統合シャッフル正当性証明装置３００に入力された乱数を用いれば、φ及びθのような乱数から作られたデータは、同一のものを再度生成することができる。
【００３７】
次に、二つのｋ成分列ベクトルである出力暗号文列３０４として、（Ｇ（κ＋１），Ｍ（κ＋１））∈（Ｍｋ，１（Ｅ），Ｍｋ，１（Ｅ））を（Ｇ（κ＋１），Ｍ（κ＋１））＝（[φ(κ)]Ｇ(κ)＋[θ(κ)]Ｇ，[φ(κ)]Ｍ(κ)＋[θ(κ)]Ｍ）と生成する。出力暗号文列３０４は入力暗号文列３０２の各暗号文を再暗号したうえで、それらの順番を入れ替えた(置換した)ものとなっている。統合シャッフル正当性証明装置３００は、出力暗号文列３０４として、（Ｇ（κ＋１），Ｍ（κ＋１））∈（Ｍｋ，１（Ｅ），Ｍｋ，１（Ｅ））を証明統合装置４００に出力する。
【００３８】
[シャッフル証明に関する装置（３０９〜３１７）の説明始まり]
[同一変換知識証明コミットメント装置３０９]
同一変換コミットメント基底３１８として、Ｆ(κ)∈Ｍｋ，１（Ｅ）と、Ｆ’(κ)∈Ｅ＝Ｍｋ，１（Ｅ）と、Ｇ’(κ)∈Ｅ＝Ｍｋ，１（Ｅ）と、Ｍ’(κ)∈Ｅ＝Ｍｋ，１（Ｅ）とが証明統合装置４００から入力される。次に、ランダムなｋ成分行ベクトル(１行ｋ列行列)ψ(κ)∈Ｍ１，ｋ（Ｚｑ）を、乱数３０３を用いて生成する。次に、ランダムなＺｑ上の点(１行１列行列)ρ(κ)∈Ｚｑ＝Ｍ１，１（Ｚｑ）を、乱数３０３を用いて生成する。
【００３９】
次に、Ｆ(κ＋１)∈Ｍｋ，１（Ｅ）をＦ(κ+1)＝（[φ(κ)]Ｆ(κ)＋[θ(κ)]Ｆ）と生成する。
次に、Ｆ’(κ＋１)∈Ｍ１，１（Ｚｑ）と、Ｇ’(κ＋１)∈Ｍ１，１（Ｚｑ）と、Ｍ’(κ＋１)∈Ｍ１，１（Ｚｑ）とを、
Ｆ’(κ+1)＝[ψ(κ)]Ｆ(κ)＋[ρ(κ)]Ｆ＋Ｆ’(κ)、
Ｇ’(κ+1)＝[ψ(κ)]Ｇ(κ)＋[ρ(κ)]Ｇ＋Ｇ’(κ)、
Ｍ’(κ+1)＝[ψ(κ)]Ｍ(κ)＋[ρ(κ)]Ｍ＋Ｍ’(κ)、
と生成する。統合シャッフル正当性証明装置３００は、Ｆ(κ＋１)∈Ｍｋ，１（Ｅ）と、Ｆ’(κ＋１)∈Ｅ＝Ｍ１，１（Ｅ）と、Ｇ’(κ＋１)∈Ｅ＝Ｍ１，１（Ｅ）と、Ｍ’(κ＋１)∈Ｅ＝Ｍ１，１（Ｅ）とを、同一変換知識証明コミットメント３１９として証明統合装置４００に出力する。
【００４０】
[第一置換証明コミットメント装置３１０]
Ｃ１（１）∈Ｍｋ，１（ＥＣ）は、その全ての成分０∈ＺｑのＹによる暗号文であるとする。第一置換蓄積コミットメント３２０としてＣ１（κ）∈Ｍｋ，１（ＥＣ）が証明統合装置４００から入力される。次に、Ｃ１（κ＋１）∈Ｍｋ，１（ＥＣ）を、Ｃ１(κ＋１)＝（ψ(κ)φ(κ)＊）＊Ｙ＋(Ｃ１(κ)[φ(κ)＊])＊Ｙと生成する。統合シャッフル正当性証明装置３００は、Ｃ１（κ＋１）∈Ｍｋ，１（ＥＣ）を第一置換証明コミットメント３２１として証明統合装置４００に出力する。
[第一置換証明コミットメント逆送装置３１１]
Ｃ２（λ＋１）＝Ｃ１（λ＋１）∈Ｍｋ，１（ＥＣ）とする。第一逆置換蓄積コミットメント３２２として、Ｃ２（κ＋１）∈Ｍｋ，１（ＥＣ）が証明統合装置４００から入力される。次に、Ｃ２（κ）∈Ｍｋ，１（ＥＣ）を、Ｃ２(κ)＝（Ｃ２(κ＋１)[φ(κ)]）＊Ｙと生成する。統合シャッフル正当性証明装置３００は、Ｃ２（κ）∈Ｍｋ，１（ＥＣ）を第一逆置換証明コミットメント３２３として証明統合装置４００に出力する。また、これを記憶装置に保存しておく。
[第二置換証明コミットメント装置３１２]
Ｃ３（１）＝Ｃ２（１）∈Ｍｋ，１（ＥＣ）とする。第二置換蓄積コミットメント３２４として、Ｃ３（κ）∈Ｍｋ，１（ＥＣ）が証明統合装置４００から入力される。次に、Ｃ３（κ＋１）∈Ｍｋ，１（ＥＣ）を、Ｃ３(κ＋１)＝（Ｃ２(κ)◎[ψ(κ)]）＊Ｙ＋（Ｃ３(κ)[φ(κ)]）＊Ｙと生成する。統合シャッフル正当性証明装置３００は、Ｃ３（κ＋１）∈Ｍｋ，１（ＥＣ）を第二置換証明コミットメント３２５として証明統合装置４００に出力する。
【００４１】
[第二置換証明コミットメント逆送装置３１３]
Ｃ４（λ＋１）＝Ｃ３（λ＋１）∈Ｍｋ，１（ＥＣ）とする。第二逆置換蓄積コミットメント３２６として、Ｃ４（κ＋１）∈Ｍｋ，１（ＥＣ）が証明統合装置３２６から入力される。次に、Ｃ４（κ）∈Ｍｋ，１（ＥＣ）を、Ｃ４(κ)＝（Ｃ４(κ＋１)[φ(κ)]）＊Ｙと生成する。統合シャッフル正当性証明装置３００は、Ｃ４（κ）∈Ｍｋ，１（ＥＣ）を、第二逆置換証明コミットメント３２７として証明統合装置４００に出力する。また、これを記憶装置に保存しておく。
[第三置換証明コミットメント装置３１４]
Ｃ５（１）＝Ｃ４（１）∈Ｍｋ，１（ＥＣ）とする。第三置換蓄積コミットメント３２８として、Ｃ５（κ）∈Ｍｋ，１（ＥＣ）が証明統合装置４００から入力される。次に、Ｃ５（κ＋１）∈Ｍｋ，１（ＥＣ）を、Ｃ５(κ＋１)＝（Ｃ４(κ)◎[ψ(κ)]）＊Ｙ＋（Ｃ５(κ)[φ(κ)]）＊Ｙと生成する。統合シャッフル正当性証明装置３００は、Ｃ５（κ＋１）∈Ｍｋ，１（ＥＣ）を第三置換証明コミットメント３２９として証明統合装置４００に出力する。
【００４２】
なお、同一変換知識証明コミットメントが同一変換証明文に相当し、置換証明コミットメントが置換証明文に相当する。
【００４３】
[レスポンス生成装置３１５]
挑戦値ｒ（λ＋１）∈Ｍ１，ｋ（Ｚｑ）が統合シャッフル正当性検証装置によりランダムに選ばれるとする。また、ｒ’（λ＋１）＝０とする。なお、挑戦値の生成方法については実施例２及び実施例３で詳細に説明する。挑戦値３３０として、ｒ（κ＋１）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ＋１）∈Ｍ１，１（Ｚｑ）＝Ｚｑとが証明統合装置４００から入力される。
【００４４】
次に、ｒ（κ）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ）∈Ｍ１，１（Ｚｑ）＝Ｚｑとを
ｒ（κ）＝（ｒ（κ＋１）φ（κ））＋ψ（κ）、
ｒ’（κ）＝（ｒ（κ＋１）θ（κ））＋ρ（κ）＋ｒ’（κ＋１）、
と生成する。統合シャッフル正当性証明装置３００は、ｒ（κ）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ）∈Ｍ１，１（Ｚｑ）＝Ｚｑとをレスポンス３３１として証明統合装置４００に出力する。
【００４５】
［置換証明コミットメント統合装置３１６］
λ番目の統合シャッフル正当性証明装置３００の出力した第一置換証明コミットメント３２１のＣ１（λ＋１）∈Ｍｋ，１（ＥＣ）と、第二置換証明コミットメント３２５のＣ２（λ＋１）∈Ｍｋ，１（ＥＣ）と、第三置換証明コミットメント３２９のＣ３（λ＋１）∈Ｍｋ，１（ＥＣ）とが入力される。λ番目の統合シャッフル正当性証明装置３００に入力された挑戦値としてｒ（λ＋１）∈Ｍ１，ｋ（Ｚｑ）とｒ’（λ＋１）∈Ｍ１，１（Ｚｑ）＝Ｚｑとが入力される。
【００４６】
次に、上述の第一置換証明コミットメントから第三置換証明コミットメント３２１、３２５、３２９をまとめた統合置換証明コミットメントの暗号文Ｃ６∈Ｍ１，１（ＥＣ）を、Ｃ６＝［ｒ（λ＋１）］Ｃ１（λ＋１）＋[ｒ（λ＋１）◎ｒ（λ＋１）]Ｃ２（λ＋１）＋［１］Ｃ３（λ＋１）と生成する。ただし、上式の［１］とは、Ｍ１，ｋ（Ｚｑ）の要素で、その成分が全て１∈Ｚｑであるものである。また、Ｃ６の第一成分をＣ６，１とし、第二成分をＣ６，２とする。
【００４７】
次に、秘密鍵３０８のｙ(κ)を用いて、この統合置換証明コミットメントの暗号文の分散復号を行い、分散復号の結果３３２としてＣ６，２（κ）∈Ｅを、Ｃ６，２（κ）＝［ｙ（κ）］Ｃ６，２と計算して証明統合装置４００に出力する。
【００４８】
［分散復号証明装置３１７］
ランダムなｙ’（κ）∈Ｚｑを選び、Ｃ’６，２（κ）＝［ｙ’（κ）］Ｃ６，２を生成して証明統合装置４００に出力する。復号証明の挑戦値としてｓ∈Ｚｑが証明統合装置４００から入力される。復号証明のレスポンスとしてｔ（κ）∈Ｚｑを、ｔ（κ）＝ｙ（κ）ｓ＋ｙ’（κ）と生成して証明統合装置４００に出力する。
[シャッフル証明に関する装置の説明終わり]
【００４９】
本実施例の統合シャッフル正当性証明装置は、統合シャッフル正当性証明装置は順序数が自分より前の装置から受け取る置換蓄積コミットメントに自装置の置換証明文を付加している。順序数の順に置換蓄積コミットメントに各統合シャッフル正当性証明装置の置換証明文が蓄積されることで、シャッフルを行う全ての装置のシャッフルの正当性を証明する情報がまとめられる。その結果、まとめられた情報から全体のシャッフルの検証を効率的に行うことが可能となる。
【実施例２】
【００５０】
本発明のミックスネットシステムの一部となる証明統合装置についての一構成例を図２を参照して説明する。
【００５１】
証明統合装置４００は、外部の他の装置とデータを送受信するためのインターフェース部を含む入力装置及び出力装置と、データを保存するための記憶装置と、各部を制御する制御装置とを有するサーバで構成される。制御装置には、プログラムにしたがって所定の処理を実行するＣＰＵと、プログラムを格納するためのメモリが設けられている。
【００５２】
図２に示すミックス装置４０５、同一変換知識証明コミットメント統合装置４０９、第一置換証明コミットメント統合装置４１０、第一置換証明コミットメント統合逆送装置４１１、第二置換証明コミットメント統合装置４１２、第二置換証明コミットメント統合逆送装置４１３、第三置換証明コミットメント統合装置４１４、コミットメント装置４１５、レスポンス統合装置４１６、統合置換証明コミットメント復号装置４１７、及び統合分散復号証明装置４１８がサーバ内に仮想的に構成される。
【００５３】
証明統合装置４００は、インターフェース部を介して、実施例１で説明した複数の統合シャッフル正当性証明装置３００、及び統合シャッフル正当性検証装置５００と通信可能に接続される。なお、統合シャッフル正当性証明装置３００の個数を実施例１と同様にλとする。
【００５４】
証明統合装置４００には、複数の暗号文からなる、ミックスネット入力暗号文４０１が入力される。この暗号文の個数をｋとする。証明統合装置４００は、λ個の統合シャッフル正当性証明装置３００と通信することで、ミックスネット入力暗号文４０１から、その順序を入れ替えた値に再暗号を行ったデータであるミックスネット出力暗号文４０２を生成し、これを統合シャッフル正当性検証装置５００に出力する。
【００５５】
さらに、証明統合装置４００は、λ個の統合シャッフル正当性証明装置３００と通信することで、証明のために必要なデータを準備する。そして、このデータを利用して、統合シャッフル正当性検証装置５００と通信することで、統合シャッフル正当性検証装置５００にミックスネットとして正当性を証明する。以下に各構成要素について詳細に説明する。
[入力装置]
証明統合装置４００に、楕円曲線Ｅを指定するパラメターと、Ｅの生成元Ｇ∈Ｅと、ミックス用公開鍵３０７ａのＭ∈Ｅと、疑似公開鍵３０６のＦ∈Ｅと、コミットメント用公開鍵３０７ｂのＹ∈Ｅと、ミックス用公開鍵３０７ａのＭで暗号化されたミックスネット入力暗号文４０１として（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、ランダムに選ばれる共通参照基底４０３として（Ｆ１，．．．，Ｆｋ）∈Ｅ＾ｋと、乱数４０４とが入力される。これらの情報は記憶装置に格納される。
【００５６】
[ミックス装置４０５]
１番目の入力暗号文列となる（Ｇ（１），Ｍ（１））∈（Ｍｋ，１（Ｅ））２について、Ｇ（１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＧｉである列ベクトル（ｋ行１列の行列）として生成し、Ｍ（１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＭｉである列ベクトル（ｋ行１列の行列）として生成する。そして、κ＝１からκ＝λまで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の入力暗号文列４０６として（Ｇ（κ），Ｍ（κ））∈（Ｍｋ，１（Ｅ））２を、κ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の出力暗号文列４０７として（Ｇ（κ＋１），Ｍ（κ＋１））∈（Ｍｋ，１（Ｅ））２を受信する。
κ＝λでなければ、（Ｇ（κ＋１），Ｍ（κ＋１））∈（Ｍｋ，１（Ｅ））２をκ＋１番目の入力暗号文列とする。
[繰り返し処理終わり]
λ番目の出力暗号文列（Ｇ（λ＋１），Ｍ（λ＋１））∈（Ｍｋ，１（Ｅ））２からミックスネット出力暗号文４０２となる（Ｇ’ｉ，Ｍ’ｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋを、Ｇ’ｉがＧ（λ＋１）のｉ番目の成分となり、Ｍ’ｉがＭ（λ＋１）のｉ番目の成分となるように生成する。証明統合装置はミックスネット出力暗号文４０２を出力し、出力暗号文４０２を統合シャッフル正当性検証装置に送信する（符号４０８）。
【００５７】
[証明統合に関する装置４０９〜４１８]
[同一変換知識証明コミットメント統合装置４０９]
１番目の同一変換コミットメント基底４１９の（Ｆ（１）∈Ｍｋ，１（Ｅ），Ｆ’（１）∈Ｍ１，１（Ｅ），Ｇ’（１）∈Ｍ１，１（Ｅ），Ｍ’（１）∈Ｍ１，１（Ｅ））を共通参照基底４０３から次のように生成する。Ｆ（１）∈Ｍｋ，１（Ｅ）をその（ｉ，１）成分がＦｉである列ベクトル（ｋ行１列の行列）として、Ｆ’（１）＝Ｏ∈Ｍ１，１（Ｅ），Ｇ’（１）＝Ｏ∈Ｍ１，１（Ｅ），Ｍ’（１）＝Ｏ∈Ｍ１，１（Ｅ）とする。そして、κ＝１からκ＝λまで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の同一変換コミットメント基底４１９を（Ｆ（κ）∈Ｍｋ，１（Ｅ），Ｆ’（κ）∈Ｍ１，１（Ｅ），Ｇ’（κ）∈Ｍ１，１（Ｅ），Ｍ’（κ）∈Ｍ１，１（Ｅ））として、κ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００から、κ番目の同一変換知識証明コミットメント４２０として（Ｆ（κ＋１）∈Ｍｋ，１（Ｅ），Ｆ’（κ＋１）∈Ｍ１，１（Ｅ），Ｇ’（κ＋１）∈Ｍ１，１（Ｅ），Ｍ’（κ＋１）∈Ｍ１，１（Ｅ））を受信する。
κ＝λでなければ、（Ｆ（κ＋１）∈Ｍｋ，１（Ｅ），Ｆ’（κ＋１）∈Ｍ１，１（Ｅ），Ｇ’（κ＋１）∈Ｍ１，１（Ｅ），Ｍ’（κ＋１）∈Ｍ１，１（Ｅ））をκ＋１番目の同一変換知識証明コミットメント４２０とする。
[繰り返し処理終わり]
λ番目の同一変換知識証明コミットメント４２０の（Ｆ（κ＋１）∈Ｍｋ，１（Ｅ），Ｆ’（κ＋１）∈Ｍ１，１（Ｅ），Ｇ’（κ＋１）∈Ｍ１，１（Ｅ），Ｍ’（κ＋１）∈Ｍ１，１（Ｅ））を、統合同一変換コミットメントとする。同一変換知識証明コミットメント統合装置４０９は統合同一変換コミットメント４３４をコミットメント装置４１５に出力する。
【００５８】
[第一置換証明コミットメント統合装置４１０]
１番目の第一置換蓄積コミットメント４２１となるＣ１（１）∈Ｍｋ，１（ＥＣ）を、その全ての成分が０∈ＺｑのＹによる暗号文であるとする。そして、κ＝１からκ＝λまで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の第一置換蓄積コミットメント４２１を、Ｃ１（κ）∈Ｍｋ，１（ＥＣ）として、κ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の第一置換証明コミットメント４２２のＣ１（κ＋１）∈Ｍｋ，１（ＥＣ）を受信する。
κ＝λでなければ、Ｃ１（κ＋１）∈Ｍｋ，１（ＥＣ）をκ＋１番目の第一置換証明コミットメント４２２とする。
[繰り返し処理終わり]
λ番目の第一置換証明コミットメント４２２のＣ１（κ＋１）∈Ｍｋ，１（ＥＣ）を、統合第一置換証明コミットメントとする。第一置換証明コミットメント統合装置４１０は統合第一置換証明コミットメント４３５をコミットメント装置４１５に出力する。
【００５９】
[第一置換証明コミットメント統合逆送装置４１１]
λ番目の第一逆置換蓄積コミットメント４２３をＣ２（λ＋１）＝Ｃ１（λ＋１）∈Ｍｋ，１（ＥＣ）とする。そして、κ＝λからκ＝１まで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の第一逆置換蓄積コミットメント４２３をＣ２（κ＋１）∈Ｍｋ，１（ＥＣ）としてκ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の第一逆置換証明コミットメント４２４のＣ２（κ）∈Ｍｋ，１（ＥＣ）を受信する。
κ＝１でなければ、Ｃ２（κ）∈Ｍｋ，１（ＥＣ）をκ−１番目の第一逆置換蓄積コミットメント４２４とする。
[繰り返し処理終わり]
１番目の第一逆置換証明コミットメント４２４となるＣ２（１）∈Ｍｋ，１（ＥＣ）を統合第一逆置換証明コミットメントとする。
【００６０】
[第二置換証明コミットメント統合装置４１２]
１番目の第二置換蓄積コミットメント４２５をＣ３（１）＝Ｃ２（１）∈Ｍｋ，１（ＥＣ）とする。そして、κ＝１からκ＝λまで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の第二置換蓄積コミットメント４２５をＣ３（κ）∈Ｍｋ，１（ＥＣ）としてκ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の第二置換証明コミットメント４２６のＣ３（κ＋１）∈Ｍｋ，１（ＥＣ）を受信する。
κ＝λでなければ、Ｃ３（κ＋１）∈Ｍｋ，１（ＥＣ）をκ＋１番目の第二置換証明コミットメント４２６とする。
[繰り返し処理終わり]
λ番目の第二置換証明コミットメント４２６のＣ３（κ＋１）∈Ｍｋ，１（ＥＣ）を、統合第二置換証明コミットメントとする。第二置換証明コミットメント統合装置４１２は統合第二置換証明コミットメント４３６をコミットメント装置４１５に出力する。
【００６１】
[第二置換証明コミットメント統合逆送装置４１３]
λ番目の第二逆置換蓄積コミットメント４２７をＣ４（λ＋１）＝Ｃ３（λ＋１）∈Ｍｋ，１（ＥＣ）とする。そして、κ＝λからκ＝１まで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の第二逆置換蓄積コミットメント４２７をＣ４（κ＋１）∈Ｍｋ，１（ＥＣ）としてκ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の第二逆置換証明コミットメント４２８のＣ４（κ）∈Ｍｋ，１（ＥＣ）を受信する。
κ＝１でなければ、Ｃ４（κ）∈Ｍｋ，１（ＥＣ）をκ−１番目の第二逆置換蓄積コミットメント４２８とする。
[繰り返し処理終わり]
１番目の第二逆置換証明コミットメント４２８となるＣ４（１）∈Ｍｋ，１（ＥＣ）を統合第二逆置換証明コミットメントとする。
【００６２】
[第三置換証明コミットメント統合装置４１４]
１番目の第三置換蓄積コミットメント４２９をＣ５（１）＝Ｃ４（１）∈Ｍｋ，１（ＥＣ）とする。そして、κ＝１からκ＝λまで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の第三置換蓄積コミットメント４２９をＣ５（κ）∈Ｍｋ，１（ＥＣ）としてκ番目の統合シャッフル正当性証明装置３００に送る。κ番目の統合シャッフル正当性証明装置３００からκ番目の第三置換証明コミットメント４３０のＣ５（κ＋１）∈Ｍｋ，１（ＥＣ）を受信する。
κ＝λでなければ、Ｃ５（κ＋１）∈Ｍｋ，１（ＥＣ）をκ＋１番目の第三置換証明コミットメント４３０とする。
[繰り返し処理終わり]
λ番目の第三置換証明コミットメント４３０となるＣ５（κ＋１）∈Ｍｋ，１（ＥＣ）を統合第三置換証明コミットメントとする。第三置換証明コミットメント統合装置４１４は統合第三置換証明コミットメント４３７をコミットメント装置４１５に出力する。
【００６３】
[コミットメント装置４１５]
証明統合装置４００は、統合同一変換コミットメント４３４と、統合第一置換証明コミットメント４３５と、統合第二置換証明コミットメント４３６と、統合第三置換証明コミットメント４３７とをまとめて統合コミットメント５０８を生成して、統合シャッフル正当性検証装置５００に送信する。
【００６４】
[レスポンス統合装置４１６]
統合シャッフル正当性検証装置５００から統合挑戦値５０９としてｃ（λ＋１）∈Ｍ１，ｋ（Ｚｑ）が入力される。統合挑戦値５０９を用いてλ番目の挑戦値４３１となる（ｒ（λ＋１），ｒ’（λ＋１））∈（Ｍ１，ｋ（Ｚｑ），Ｍ１，１（Ｚｑ））を以下のようにして生成する。ただし、ｒ（λ＋１）＝ｃ（λ＋１），ｒ’（λ＋１）＝０とする。κ＝λからκ＝１まで以下に示す手順を繰り返す。
[繰り返し処理始め]
κ番目の挑戦値４３１をｒ（κ＋１）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ＋１）∈Ｍ１，１（Ｚｑ）＝Ｚｑとしてκ番目の統合シャッフル正当性証明装置３００に送信する。κ番目の統合シャッフル正当性証明装置３００からκ番目のレスポンス４３２のｒ（κ）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ）∈Ｍ１，１（Ｚｑ）＝Ｚｑとを受信する。
κ＝１でなければ、ｒ（κ）∈Ｍ１，ｋ（Ｚｑ）とｒ’（κ）∈Ｍ１，１（Ｚｑ）＝Ｚｑとをκ−１番目の挑戦値４３１とする。
[繰り返し処理終わり]
１番目のレスポンス４３２のｒ（１）∈Ｍ１，ｋ（Ｚｑ）とｒ’（１）∈Ｍ１，１（Ｚｑ）＝Ｚｑとを統合レスポンス５１０とする。レスポンス統合装置４１６は統合レスポンス５１０を統合シャッフル正当性検証装置５００に送信する。
【００６５】
［統合置換証明コミットメント復号装置４１７］
統合置換証明コミットメントの暗号文Ｃ６＝［ｒ（λ＋１）］Ｃ１（λ＋１）＋[ｒ（λ＋１）◎ｒ（λ＋１）]Ｃ２（λ＋１）＋［１］Ｃ３（λ＋１）を生成する。ここで、Ｃ６の第一成分をＣ６，１とし、第二成分をＣ６，２とする。κ＝１からκ＝λまでの統合シャッフル正当性証明装置３００と通信して、それぞれのκに関するＣ６の分散復号の結果４３３としてＣ６，２（κ）∈Ｅを得る。これらを合わせて、Ｈ∈Ｅを、Ｈ＝Ｃ６，１−Σκ＝１λＣ６，２（κ）と生成する。統合置換証明コミットメント復号装置４１７は、このＨを復号統合置換証明コミットメント５１１として統合シャッフル正当性検証装置５００に送信する。
【００６６】
［統合分散復号証明装置４１８］
統合分散復号証明装置４１８は、以下のようにして、κ＝１からκ＝λまでの統合シャッフル正当性証明装置３００と通信すること（符号４４２）と、統合シャッフル正当性検証装置５００と通信すること（符号４４３）で、統合シャッフル正当性検証装置５００に対して、上記Ｈが正当な統合置換証明コミットメントの暗号文の復号文であることを証明する。
【００６７】
κ＝１からκ＝λまでの統合シャッフル正当性証明装置３００と通信して、各統合シャッフル正当性証明装置からＣ’６，２（κ）∈Ｚｑを受け取る。続いて、分散復号の証明のコミットメントＣ’６，２＝Σκ＝１λＣ’６，２（κ）を生成して、統合シャッフル正当性検証装置５００に送信する。また、統合シャッフル正当性検証装置５００より復号証明の挑戦値ｓ∈Ｚｑを受け取ると、これをκ＝１からκ＝λまでの統合シャッフル正当性証明装置３００に送信する。続いて、κ＝１からκ＝λまでの統合シャッフル正当性証明装置３００と通信して、各統合シャッフル正当性証明装置３００から復号証明のレスポンスｔ（κ）∈Ｚｑを受け取る。そして、復号証明の統合レスポンスｔ＝Σκ＝１λｔ（κ）を生成して、統合シャッフル正当性検証装置５００に送信する。
【００６８】
本実施例の証明統合装置は、複数の統合シャッフル正当性証明装置のそれぞれと通信を行って、各装置でのシャッフルの正当性の情報を一つにまとめることで、ミックスネット全体を一つのシャッフルとみなして処理することが可能となる。
【実施例３】
【００６９】
本発明のミックスネットシステムの一部となる統合シャッフル正当性検証装置についての一構成例を図３を参照して説明する。
【００７０】
統合シャッフル正当性検証装置５００は、外部の他の装置とデータを送受信するためのインターフェース部を含む入力装置及び出力装置と、データを保存するための記憶装置と、各部を制御する制御装置とを有するサーバで構成される。制御装置には、プログラムにしたがって所定の処理を実行するＣＰＵと、プログラムを格納するためのメモリが設けられている。
【００７１】
図３に示すコミットメント受信装置５０２、挑戦値生成装置５０３、レスポンス受信装置５０４、複合統合置換証明コミットメント受信装置５０５、分散復号検証装置５０６、及び検証装置５０７がサーバ内に仮想的に構成される。また、統合シャッフル正当性検証装置５００は、実施例２と同様に、インターフェース部を介して証明統合装置４００と通信可能に接続される。以下に、各構成要素について詳細に説明する。
[入力装置]
楕円曲線Ｅを指定するパラメターと、Ｅの生成元Ｇ∈Ｅと、ミックス用公開鍵３０７ａのＭ∈Ｅと、疑似公開鍵３０６のＦ∈Ｅと、コミットメント用公開鍵３０７ｂのＹ∈Ｅが入力される。また、ミックス用公開鍵３０７ａのＭで暗号化されたミックスネット入力暗号文４０１となる（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、ミックスネット出力暗号文４０２の（Ｇ’ｉ，Ｍ’ｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、共通参照基底４０３の（Ｆ１，．．．，Ｆｋ）∈Ｅ＾ｋと、乱数５０１とが入力される。これらの情報は記憶装置に格納される。
【００７２】
[コミットメント受信装置５０２]
証明統合装置４００より統合同一変換コミットメント（Ｆ（κ＋１）∈Ｍｋ，１（Ｅ），Ｆ’（κ＋１）∈Ｍ１，１（Ｅ），Ｇ’（κ＋１）∈Ｍ１，１（Ｅ），Ｍ’（κ＋１）∈Ｍ１，１（Ｅ））と、統合第一置換証明コミットメントＣ１（κ＋１）∈Ｍｋ，１（ＥＣ）と、統合第二置換証明コミットメントＣ３（κ＋１）∈Ｍｋ，１（ＥＣ）と、統合第三置換証明コミットメントＣ５（κ＋１）∈Ｍｋ，１（ＥＣ）とを含む統合コミットメント５０８を受信する。
[挑戦値生成装置５０３]
ランダムな統合挑戦値５０９としてｃ（λ＋１）∈Ｍ１，ｋ（Ｚｑ）を生成して、証明統合装置４００に送信する。
[レスポンス受信装置５０４]
証明統合装置４００より統合レスポンス５１０のｒ（１）∈Ｍ１，ｋ（Ｚｑ）とｒ’（１）∈Ｍ１，ｋ（Ｚｑ）＝Ｚｑを受信する。
[復号統合置換証明コミットメント受信装置５０５]
証明統合装置４００より復号統合置換証明コミットメント５１１のＨ∈Ｅを受信する。
【００７３】
[分散復号検証装置５０６]
証明統合装置４００と通信すること（符号４４３）で、証明統合装置４００から受信した復号統合置換証明コミットメント５１１のＨにより正当な統合置換証明コミットメントの暗号文の復号文であることを、以下のようにして証明する。
証明統合装置４００より分散復号の証明のコミットメントＣ’６，２∈Ｅを受け取る。復号証明の挑戦値としてランダムなｓ∈Ｚｑを生成して、証明統合装置４００に送信する。復号証明の統合レスポンスとしてｔ∈Ｚｑを証明統合装置４００から受信する。
【００７４】
[検証装置５０７]
暗号文Ｃ６＝［ｒ（λ＋１）］Ｃ１（λ＋１）＋[ｒ（λ＋１）◎ｒ（λ＋１）]Ｃ２（λ＋１）＋［１］Ｃ３（λ＋１）を生成する。ここで、Ｃ６の第一成分をＣ６，１とし、第二成分をＣ６，２とする。次の式が成り立つことを確認する。
［ｒ’（１）］Ｆ＋［ｒ（１）］Ｆ（１）＝Ｆ’（λ＋１）＋［ｃ（λ＋１）］Ｆ（λ＋１）、
［ｒ’（１）］Ｇ＋［ｒ（１）］Ｇ（１）＝Ｇ’（λ＋１）＋［ｃ（λ＋１）］Ｇ（λ＋１）、
［ｒ’（１）］Ｍ＋［ｒ（１）］Ｍ（１）＝Ｍ’（λ＋１）＋［ｃ（λ＋１）］Ｍ（λ＋１）、
［ｔ］Ｃ６，２＝［ｓ］（Ｃ６，１−Ｈ）＋Ｃ’６，２、
［Σｉ＝１ｋ｛（ｒｉ（１））３−（ｃｉ（１））３｝］Ｇ＝Ｈ、の５式である。
【００７５】
これらが成り立てば、ミックスネット出力暗号文がミックスネット入力暗号文から正しく生成され、「正当」であるものと判定する。一方、これらが成り立たなければ、ミックスネット出力暗号文がミックスネット入力暗号文から正しく生成されておらず、「不当」であると判定する。そして、その判定結果を検証結果５１２として出力装置から出力する。
【００７６】
本実施例の統合シャッフル正当性検証装置は、シャッフルの正当性に関する情報を証明統合装置から受信して検証すればよいため、従来のように複数の統合シャッフル正当性証明装置との間でデータをやりとりしなくてすむ。
【実施例４】
【００７７】
本発明の一実施例をなす統合シャッフル正当性証明装置、証明統合装置、及び統合シャッフル正当性検証装置がなす、検証可能なミックスネットシステム６００について、図４を参照して説明する。
【００７８】
ミックスネットシステム６００は、実施例１で説明した統合シャッフル正当性証明装置３００と、実施例２で説明した証明統合装置４００と、実施例３で説明した統合シャッフル正当性検証装置５００とを有する。統合シャッフル正当性証明装置３００は複数設けられている。ここでは、統合シャッフル正当性証明装置の個数をλとし、統合シャッフル正当性証明装置に符号３００−１〜３００−λを記す。
【００７９】
各統合シャッフル正当性証明装置３００と証明統合装置４００はインターフェース部を介して相互に通信可能である。また、証明統合装置４００と統合シャッフル正当性検証装置５００はインターフェース部を介して相互に通信可能である。
【００８０】
統合シャッフル正当性証明装置３００−１〜λのそれぞれには、自装置が実現するミキサーの順番を表す順序数κと、シャッフルする暗号文の個数ｋと、楕円曲線Ｅを表すパラメターと、Ｅの生成子Ｇ∈Ｅ＝Ｍ１，１（Ｅ）と、ミックス用公開鍵Ｍと、各統合シャッフル装置の秘密鍵ｙ(κ)∈Ｚｑと、コミットメント用公開鍵Ｙと、乱数とが入力される。
【００８１】
証明統合装置４００には、楕円曲線Ｅを指定するパラメターと、Ｅの生成元Ｇ∈Ｅと、ミックス用の公開鍵Ｍ∈Ｅと、疑似公開鍵Ｆ∈Ｅと、コミットメント用公開鍵Ｙ∈Ｅと、ミックス用公開鍵Ｍで暗号化されたミックスネット入力暗号文４０１の（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、共通参照基底の（Ｆ１，．．．，Ｆｋ）∈Ｅ＾ｋとが入力される。
【００８２】
統合シャッフル正当性検証装置５００には、楕円曲線Ｅを指定するパラメターと、Ｅの生成元Ｇ∈Ｅと、ミックス用の公開鍵Ｍ∈Ｅと、疑似公開鍵Ｆ∈Ｅと、コミットメント用公開鍵Ｙ∈Ｅと、ミックス用公開鍵Ｍで暗号化されたミックスネット入力暗号文（Ｇｉ，Ｍｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、ミックスネット出力暗号文（Ｇ’ｉ，Ｍ’ｉ），ｉ＝１，．．．，ｋ∈（Ｅ，Ｅ）ｋと、共通参照基底の（Ｆ１，．．．，Ｆｋ）∈Ｅ＾ｋと、乱数とが入力される。
【００８３】
証明統合装置４００は、全ての統合シャッフル正当性証明装置３００−１〜λと通信を行うことにより（符号６０１−１〜λ）、ミックスネット出力暗号文４０２を生成する（符号６０２）。そして、ミックスネット出力暗号文４０２を統合シャッフル正当性検証装置５００に送信する（符号６０３）。統合シャッフル正当性検証装置５００はミックスネット出力暗号文４０２を証明統合装置４００から受信する。
【００８４】
続いて、証明統合装置４００は、全ての統合シャッフル正当性証明装置３００−１〜λと通信を行うことにより（符号６０１−１〜λ）、統合コミットメントを生成する。そして、統合コミットメントを統合シャッフル正当性検証装置５００に送信する。統合シャッフル正当性検証装置５００は統合コミットメントを証明統合装置４００から受信すると、統合挑戦値を生成して証明統合装置４００に送信する。
【００８５】
証明統合装置４００は、統合シャッフル正当性検証装置５００から統合挑戦値を受信すると、統合シャッフル正当性証明装置３００−１〜λのそれぞれに挑戦値を送信し、それぞれからレスポンスを受信する（符号６０１−１〜λ）。そして、統合シャッフル正当性証明装置３００−１〜λから受信したレスポンスをまとめて統合レスポンスを生成する。続いて、証明統合装置４００は、統合レスポンスを統合シャッフル正当性検証装置５００に送信する。
【００８６】
その後、証明統合装置４００は、全ての統合シャッフル正当性証明装置３００−１〜λと通信を行うことにより（符号６０１−１〜λ）、復号統合置換証明コミットメントを生成する。そして、復号統合置換証明コミットメントを統合シャッフル正当性検証装置５００に送信する。統合シャッフル正当性検証装置５００は復号統合置換証明コミットメントを証明統合装置４００から受信する。
【００８７】
さらに、証明統合装置４００は、統合シャッフル正当性検証装置５００と通信することで（符号６０４）、復号統合置換証明コミットメントの正当性を証明する。ただし、この証明のために、証明統合装置４００は全ての統合シャッフル正当性証明装置３００−１〜λと通信を行う。
【００８８】
統合シャッフル正当性検証装置５００は、証明統合装置４００との通信で得られた全てのデータから、上記ミックスネット出力暗号文４０２が、上記ミックスネット入力暗号文４０１の順番を入れ替えて再暗号化したものであるか否かを判定する。すなわち、正しくミックスネットの処理が行われているか否かを判定した検証結果５１２を出力する。
【００８９】
本発明のミックスネットシステムは、ミックスネット全体を一つのシャッフルと見なして、この一つのシャッフルの正当性の証明を複数のミキサーが協力して検証者に対して出力することにより、検証者の必要な計算量がミキサーの数によらず一定の大きさにすることが可能となる。
【００９０】
本発明のミックスネットシステムは、ミックスネット全体を一つのシャッフルと見なして、この一つのシャッフルの正当性の証明を複数のミキサーが協力して検証者に対して出力している。そのため、複数のミキサーがシャッフルを行うミックスネットの正当性の検証を行うときに、検証者の必要とする計算量がミキサーの数、すなわち行われるシャッフルの回数に依存しなくなる。その結果、検証者の負担を軽くすることができる。そのため、ミキサーの数を増やすことを容易にし、より強い匿名性を持ったミックスネットを構成できるという効果を奏する。
【００９１】
この効果は電子投票システムに用いると効果的である。例えば、従来の技術（３）の電子投票の管理センターが証明統合装置を操作し、各ミキサーが統合シャッフル正当性検証性装置を用いる。統合シャッフル正当性検証装置は個別の検証者と通信してその電子投票の正当性を証明してもよいが、統合シャッフル正当性検証装置の出力する統合挑戦値と復号証明の挑戦値の代りに、ハッシュ関数の出力を用いることで、統合シャッフル正当性検証装置と通信を行うことなく、証明作業を完遂することができる。
【００９２】
この証明作業において、ハッシュ関数を用いずに、検証者と通信して証明していれば検証者に送ったであろうデータを、ミックスネットの証明文として出力する。このミックスネットの証明文を用いれば、誰でもミックスネットの正当性を検証することができる。よって、管理センターはこの証明文を投票の正当性を検証したい人、例えば全ての投票者、に配布し、その正当性を証明することができる。この配布した証明文の大きさは、本発明を適用した場合、ミックスネットを構成するミキサーの数に依存しない。そのため、小さな計算パワーしか所持しない多くの投票者でも、ミキサーの数が多い場合にさえ、容易に電子投票の正当性を検証することができる。
【図面の簡単な説明】
【００９３】
【図１】本実施例の統合シャッフル正当性証明装置の構成を示す図である。
【図２】本実施例の証明統合装置の構成を示す図である。
【図３】本実施例の統合シャッフル正当性検証装置の構成を示す図である。
【図４】本実施例のミックスネットシステムの構成を示すブロック図である。
【図５】従来の技術（１）の構成を説明するための図である。
【図６】従来の技術（２）の構成を説明するための図である。
【符号の説明】
【００９４】
３００    統合シャッフル正当性証明装置
４００    証明統合装置
５００    統合シャッフル正当性検証装置
６００    ミックスネットシステム
【図１】
2006333193.tif 000003
【図２】
2006333193.tif 000004
【図３】
2006333193.tif 000005
【図４】
2006333193.tif 000006
【図５】
2006333193.tif 000007
【図６】
2006333193.tif 000008