(57)【特許請求の範囲】
【請求項１】
共通鍵暗号方式の複数の共通鍵の一つを、複数の置換復号装置の一つの公開鍵により暗号化する鍵暗号化手段と、
共通鍵暗号方式の複数の共通鍵の一つで、与えられたデータを暗号化するデータ暗号化手段と、
暗号学的なハッシュ関数を用いて、与えられたデータのハッシュ値を計算し、このハッシュ値を前記複数の置換復号装置の一つの公開鍵により暗号化するハッシュ値暗号化手段と、
前記データ暗号化手段の最初の入力を平文とし、次からの、前記データ暗号化手段の入力を前回の前記データ暗号化手段，前記鍵暗号化手段，前記ハッシュ値暗号化手段の出力とする処理を、前記置換復号装置の数だけ繰り返す、繰り返し手段と、
前記繰り返し手段の処理により得られたデータを出力する出力手段と
を備えることを特徴とする参加者装置。
【請求項２】
請求項１に記載の参加者装置において、
前記鍵暗号化手段は、暗号化した前記共通鍵の知識の証明文を生成する手段を備えることを特徴とする参加者装置。
【請求項３】
請求項２に記載の参加者装置において、
前記与えられたデータを、前記複数の置換復号装置の一つの公開鍵により暗号化し、さらにこの時の暗号化に用いた秘密の乱数の知識の証明文を生成する知識の連結手段をさらに備え、
前記繰り返し手段は、前記データ暗号化手段の最初の入力を前記平文とし、次からの、前記データ暗号化手段の入力を前回の前記データ暗号化手段，前記鍵暗号化手段，前記ハッシュ値暗号化手段，前記知識の連結手段の出力とする処理を、前記置換復号装置の数だけ繰り返す手段を備え、
前記知識の連結手段による処理を繰り返すことにより最終的に得られたデータに関して、前記処理の繰り返し全てで使った秘密の乱数の和の知識の証明文を生成する全体の乱数の知識の証明手段をさらに備えることを特徴とする参加者装置。
【請求項４】
請求項１に記載の参加者装置において、
前記出力手段は、前記繰り返し手段の処理により得られた前記データと共に、このデータを作成したのが正当な参加者装置であることを証明するデータを出力する手段を備えることを特徴とする参加者装置。
【請求項５】
入力データ列の各要素を、公開鍵暗号方式により暗号化された共通鍵暗号方式の共通鍵，共通鍵暗号方式により暗号化されたデータ，公開鍵暗号方式により暗号化されたハッシュ値に分割するデータ分割手段と、
前記暗号化された共通鍵暗号方式の共通鍵を前記公開鍵暗号方式の秘密鍵により復号する、共通鍵復号手段と、
復号した前記共通鍵を用いて、前記暗号化されたデータを復号して出力データを生成するデータ復号手段と、
前記暗号化されたハッシュ値を、前記公開鍵暗号方式の秘密鍵により復号したものを出力するハッシュ値復号手段と、
前記復号されたハッシュ値と前記生成された出力データのハッシュ値とを比較し、一致すればハッシュ値受理を、異なればハッシュ値不受理を出力するハッシュ値検証手段と、
前記出力データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段において受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする、出力データ列生成手段と、
前記出力データ列の各要素のハッシュ値が、必ず前記入力データ列のある要素に含まれる前記暗号化されたハッシュ値を復号したものであり、かつ両者の対応が一対一であることの証明文であるハッシュ値復号正当性証明文を生成する、ハッシュ値復号正当性証明手段と、
前記ハッシュ値検証手段において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成するハッシュ値不受理正当性証明手段と、
前記ハッシュ値復号正当性証明文と前記ハッシュ値不受理正当性証明文とを正当性証明文とし、これと前記出力データ列生成手段の出力した前記出力データ列とを出力する出力手段と
を備えることを特徴とする置換復号装置。
【請求項６】
請求項５に記載の置換復号装置において、
前記データ分割手段は、前記入力データ列の各要素を、暗号化された前記共通鍵の知識の証明文にさらに分割する手段を備え、
前記共通鍵の知識の証明文の正当性を検証し、正当なら受理を不当なら不受理を出力する共通鍵の知識の検証手段をさらに備え、
前記出力データ列生成手段は、前記出力データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段及び前記共通鍵の知識の検証手段の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする手段を備えることを特徴とする置換復号装置。
【請求項７】
請求項６に記載の置換復号装置において、
前記データ分割手段は、前記入力データ列の各要素を、公開鍵暗号方式により暗号化された連結データ、連結データ暗号化に用いた秘密の乱数の知識の証明文にさらに分割する手段を備え、
前記秘密の乱数の知識の証明文を検証し、正当なら受理を不当なら不受理を出力する秘密の乱数の知識の検証手段と、
前記暗号化された連結データを、前記公開鍵暗号方式の秘密鍵により復号する連結データ復号手段とをさらに備え、
前記出力データ列生成手段は、前記出力データと前記復号された連結データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段、前記共通鍵の知識の検証手段、前記秘密の乱数の知識の検証手段の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする手段を備え、
前記出力データ列の各要素に含まれる前記復号された連結データが、必ず前記入力データ列のある要素に含まれる前記暗号化された連結データを復号したものであり、かつ両者の対応が一対一であることの証明文である連結データ復号正当性証明文を出力する連結データ復号正当性証明手段をさらに備え、
前記出力手段は、前記ハッシュ値復号正当性証明文と前記連結データ復号正当性証明文と前記ハッシュ値不受理正当性証明文とを前記正当性証明文とし、これと前記出力データ列生成手段の出力した前記出力データ列とを出力する手段を備えることを特徴とする置換復号装置。
【請求項８】
請求項６に記載の置換復号装置において、
前記出力データ列の中に同一の要素があった場合、以降の処理で一つを残して重複する要素を削除したものを新しく出力データとする重複データ削除手段をさらに備え、
前記ハッシュ値不受理正当性証明手段は、前記出力データ列の各要素に含まれる前記復号された連結データが、必ず前記入力データ列のある要素に含まれる前記暗号化された連結データを復号したものであり、前記ハッシュ値検証手段において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成する手段を備えることを特徴とする置換復号装置。
【請求項９】
ハッシュ値復号正当性証明文に含まれる復号されたハッシュ値が、入力データ列のある要素の暗号化されたハッシュ値を復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力するハッシュ値復号正当性検証手段と、
前記復号されたハッシュ値が、出力データ列の各要素のハッシュ値と一致すれば受理を、一致しなければ不受理を出力するハッシュ値一致検証手段と、
入力暗号文の列の要素の内、前記ハッシュ値一致検証手段において不受理が出力されたハッシュ値に対応する要素に関しては、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を検証し、この証明文が正当であれば受理を、不当であれば不受理を出力するハッシュ値不受理正当性検証手段と、
前記入力データ列の要素に関して、前記ハッシュ値復号正当性検証手段で受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記ハッシュ値一致検証手段で受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する正当性判定手段と
を備えることを特徴とする検証装置。
【請求項１０】
請求項９に記載の検証装置において、
前記入力データ列の各要素に属する共通鍵の知識の証明文の正当性を検証し、正当なら受理を不当なら不受理を出力する共通鍵の知識の検証手段をさらに備え、
前記正当性判定手段は、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段で受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記ハッシュ値一致検証手段とで受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備えることを特徴とする検証装置。
【請求項１１】
請求項１０に記載の検証装置において、
前記入力データ列の各要素に属する秘密の乱数の知識の証明文を検証し、正当なら受理を不当なら不受理を出力する秘密の乱数の知識の検証手段と、
前記出力データ列の各要素に含まれる復号された連結データが、前記入力データ列のある要素に含まれる、暗号化された連結データを復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力する連結データ復号正当性検証手段とをさらに備え、
前記正当性判定手段は、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段と前記秘密の乱数の知識の検証手段の両方において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段と前記連結データ復号正当性検証手段の両方において受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記秘密の乱数の知識の検証手段と前記ハッシュ値一致検証手段とで受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備えることを特徴とする検証装置。
【請求項１２】
請求項１０に記載の検証装置において、
前記出力データ列の各要素に重複がある場合、以降の処理でこれが削除されていることを確認したら受理を、でなければ不受理を出力する重複データ削除確認手段をさらに備え、
前記正当性判定手段は、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段と前記重複データ削除確認手段において受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記ハッシュ値一致検証手段で受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備えることを特徴とする検証装置。
【請求項１３】
複数の参加者装置と、取りまとめ装置と、複数の置換復号装置と、検証装置とを備え、
前記参加者装置のそれぞれは、
共通鍵暗号方式の複数の共通鍵の一つを、前記複数の置換復号装置の一つの公開鍵により暗号化する鍵暗号化手段と、
共通鍵暗号方式の複数の共通鍵の一つで、与えられたデータを暗号化するデータ暗号化手段と、
暗号学的なハッシュ関数を用いて、与えられたデータのハッシュ値を計算し、このハッシュ値を前記複数の置換復号装置の一つの公開鍵により暗号化するハッシュ値暗号化手段と、
前記データ暗号化手段の最初の入力を平文とし、次からの、前記データ暗号化手段の入力を前回の前記データ暗号化手段，前記鍵暗号化手段，前記ハッシュ値暗号化手段の出力とする処理を、前記置換復号装置の数だけ繰り返す、繰り返し手段と、
前記繰り返し手段の処理により得られたデータを前記取りまとめ装置へ出力する出力手段と
を備え、
前記取りまとめ装置は、前記複数の参加者装置から複数のデータが入力されて、これらのデータの正当性を検証し、正当であることが判明したものだけを前記置換復号装置のいずれかへ出力する構成を有し、
前記置換復号装置のそれぞれは、
前記取りまとめ装置及び他の置換復号装置のいずれかから入力される入力データ列の各要素を、公開鍵暗号方式により暗号化された共通鍵暗号方式の共通鍵，共通鍵暗号方式により暗号化されたデータ，公開鍵暗号方式により暗号化されたハッシュ値に分割するデータ分割手段と、
前記暗号化された共通鍵暗号方式の共通鍵を前記公開鍵暗号方式の秘密鍵により復号する、共通鍵復号手段と、
復号した前記共通鍵を用いて、前記暗号化されたデータを復号して出力データを生成するデータ復号手段と、
前記暗号化されたハッシュ値を、前記公開鍵暗号方式の秘密鍵により復号したものを出力するハッシュ値復号手段と、
前記復号されたハッシュ値と前記生成された出力データのハッシュ値とを比較し、一致すればハッシュ値受理を、異なればハッシュ値不受理を出力するハッシュ値検証手段と、
前記出力データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段において受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする、出力データ列生成手段と、
前記出力データ列の各要素のハッシュ値が、必ず前記入力データ列のある要素に含まれる前記暗号化されたハッシュ値を復号したものであり、かつ両者の対応が一対一であることの証明文であるハッシュ値復号正当性証明文を生成する、ハッシュ値復号正当性証明手段と、
前記ハッシュ値検証手段において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成するハッシュ値不受理正当性証明手段と、
前記ハッシュ値復号正当性証明文と前記ハッシュ値不受理正当性証明文とを正当性証明文とし、これと前記出力データ列生成手段の出力した前記出力データ列とを出力する出力手段と
を備え、
前記検証装置は、
前記ハッシュ値復号正当性証明文に含まれる復号されたハッシュ値が、前記置換復号装置の入力データ列のある要素の暗号化されたハッシュ値を復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力するハッシュ値復号正当性検証手段と、
前記復号されたハッシュ値が、前記置換復号装置の出力データ列の各要素のハッシュ値と一致すれば受理を、一致しなければ不受理を出力するハッシュ値一致検証手段と、
入力暗号文の列の要素の内、前記ハッシュ値一致検証手段において不受理が出力されたハッシュ値に対応する要素に関しては、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を検証し、この証明文が正当であれば受理を、不当であれば不受理を出力するハッシュ値不受理正当性検証手段と、
前記入力データ列の要素に関して、前記ハッシュ値復号正当性検証手段で受理かつ前記ハッシュ値一致検証手段で受理、及び、前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理、のいずれかであり、かつ前記出力データ列には前記ハッシュ値一致検証手段で受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する正当性判定手段と
を備え、
安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数を生成し、公開する初期設定処理と、
前記複数の置換復号装置のそれぞれの公開鍵を生成し、公開する置換復号装置の初期設定処理と、
安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数，前記複数の置換復号装置のそれぞれの公開鍵，複数の前記共通鍵暗号方式の共通鍵及び前記参加者ごとに異なる平文とが前記参加者装置のそれぞれに入力され、
前記参加者装置のそれぞれから、前記置換復号装置へ入力するデータをそれぞれ出力する参加処理と、
前記参加処理で得られた置換復号装置へ入力するデータ全てが前記取りまとめ装置に入力され、この時の前記取りまとめ装置の出力を入力データ列とする、取りまとめ処理と、
前記置換復号装置の一つに、入力データ列と公開鍵暗号方式の秘密鍵とが入力され、この置換復号装置が出力データ列、正当性証明文の列を出力する、置換復号処理と、
前記取りまとめ処理の出力である入力データ列を最初の入力データ列として前記置換復号処理を、用いる置換復号装置を交換しながら次々と繰り返し行う処理で、最初の置換復号処理における入力データ列は、前記取りまとめ処理の出力する入力データ列であり、以降の置換復号処理における入力データ列は、直前の置換復号処理における出力データの列とし、最後の置換復号処理の出力する出力データ列を復号結果とし、最後の置換復号処理を除く各置換復号処理の出力する出力データ列を復号途中結果とし、全ての置換復号処理の出力する正当性証明文を、全体の正当性証明文とし、復号結果，復号途中結果，全体の正当性証明文とを出力する統合置換復号処理と、
復号結果，復号途中結果，全体の正当性証明文から各置換復号装置の入力及び出力を分離し、各置換復号処理の入力データ列と出力データ列と正当性証明文とが前記検証装置に入力され、前記検証装置が受理または不受理を出力する検証処理と、
全ての置換復号処理に関する検証処理の出力を集めて、全てが受理であれば全体としての受理を、そうでなければ全体としての不受理を出力するミックスネット判定処理と
を行うことを特徴とするミックスネットシステム。
【請求項１４】
請求項１３のミックスネットシステムにおいて、
前記参加者装置は、
前記鍵暗号化手段が、暗号化した前記共通鍵の知識の証明文を生成する手段を備え、
前記置換復号装置は、
前記データ分割手段が、前記入力データ列の各要素を、暗号化された前記共通鍵の知識の証明文にさらに分割する手段を備え、
前記共通鍵の知識の証明文の正当性を検証し、正当なら受理を不当なら不受理を出力する共通鍵の知識の検証手段をさらに備え、
前記出力データ列生成手段が、前記出力データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段及び前記共通鍵の知識の検証手段の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする手段を備え、
前記検証装置は、
前記入力データ列の各要素に属する共通鍵の知識の証明文の正当性を検証し、正当なら受理を不当なら不受理を出力する共通鍵の知識の検証手段をさらに備え、
前記正当性判定手段が、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段で受理かつ前記ハッシュ値一致検証手段で受理、及び、前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理、のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記ハッシュ値一致検証手段とで受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備える
ことを特徴とするミックスネットシステム。
【請求項１５】
請求項１４のミックスネットシステムにおいて、
前記参加者装置は、
前記与えられたデータを、前記複数の置換復号装置の一つの公開鍵により暗号化し、さらにこの時の暗号化に用いた秘密の乱数の知識の証明文を生成する知識の連結手段をさらに備え、
前記繰り返し手段が、前記データ暗号化手段の最初の入力を前記平文とし、次からの、前記データ暗号化手段の入力を前回の前記データ暗号化手段，前記鍵暗号化手段，前記ハッシュ値暗号化手段，前記知識の連結手段の出力とする処理を、前記置換復号装置の数だけ繰り返す手段を備え、
前記知識の連結手段による処理を繰り返すことにより最終的に得られたデータに関して、前記処理の繰り返し全てで使った秘密の乱数の和の知識の証明文を生成する全体の乱数の知識の証明手段をさらに備え、
前記置換復号装置は、
前記データ分割手段が、前記入力データ列の各要素を、公開鍵暗号方式により暗号化された連結データ、連結データ暗号化に用いた秘密の乱数の知識の証明文にさらに分割する手段を備え、
前記秘密の乱数の知識の証明文を検証し、正当なら受理を不当なら不受理を出力する秘密の乱数の知識の検証手段と、
前記暗号化された連結データを、前記公開鍵暗号方式の秘密鍵により復号する連結データ復号手段とをさらに備え、
前記出力データ列生成手段が、前記出力データと前記復号された連結データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段、前記共通鍵の知識の検証手段、前記秘密の乱数の知識の検証手段の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする手段を備え、
前記出力データ列の各要素に含まれる前記復号された連結データが、必ず前記入力データ列のある要素に含まれる前記暗号化された連結データを復号したものであり、かつ両者の対応が一対一であることの証明文である連結データ復号正当性証明文を出力する連結データ復号正当性証明手段をさらに備え、
前記出力手段が、前記ハッシュ値復号正当性証明文と前記連結データ復号正当性証明文と前記ハッシュ値不受理正当性証明文とを前記正当性証明文とし、これと前記出力データ列生成手段の出力した前記出力データ列とを出力する手段を備え、
前記検証装置は、
前記入力データ列の各要素に属する秘密の乱数の知識の証明文を検証し、正当なら受理を不当なら不受理を出力する秘密の乱数の知識の検証手段と、
前記出力データ列の各要素に含まれる復号された連結データが、前記入力データ列のある要素に含まれる、暗号化された連結データを復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力する連結データ復号正当性検証手段とをさらに備え、
前記正当性判定手段が、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段と前記秘密の乱数の知識の検証手段の両方において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段と前記連結データ復号正当性検証手段の両方において受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記秘密の乱数の知識の検証手段と前記ハッシュ値一致検証手段とで受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備える
ことを特徴とするミックスネットシステム。
【請求項１６】
請求項１４のミックスネットシステムにおいて、
前記置換復号装置は、
前記出力データ列の中に同一の要素があった場合、以降の処理で一つを残して重複する要素を削除したものを新しく出力データとする重複データ削除手段をさらに備え、
前記ハッシュ値不受理正当性証明手段が、前記出力データ列の各要素に含まれる前記復号された連結データが、必ず前記入力データ列のある要素に含まれる前記暗号化された連結データを復号したものであり、前記ハッシュ値検証手段において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成する手段を備え、
前記検証装置は、
前記出力データ列の各要素に重複がある場合、以降の処理でこれが削除されていることを確認したら受理を、でなければ不受理を出力する重複データ削除確認手段をさらに備え、
前記正当性判定手段が、前記入力データ列の要素のなかで、この要素に対する前記共通鍵の知識の検証手段において受理されたもの全てに関して、前記ハッシュ値復号正当性検証手段と前記重複データ削除確認手段において受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記共通鍵の知識の検証手段と前記ハッシュ値一致検証手段で受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する手段を備える
ことを特徴とするミックスネットシステム。
【請求項１７】
請求項１３に記載のミックスネットシステムにおいて、
前記参加者装置は、
前記出力手段が、前記繰り返し手段の処理により得られた前記データと共に、このデータを作成したのが正当な参加者装置であることを証明するデータを出力する手段を備え、
前記取りまとめ装置は、
入力された前記データが正当な参加者装置によって生成されたことを検証する構成をさらに備える
ことを特徴とするミックスネットシステム。
【請求項１８】
請求項１３に記載のミックスネットシステムにおいて、
前記参加者装置は、
前記ハッシュ値暗号化手段の最初の入力として、平文と併せて、乱数，日時，ミックスネットのセッションに固有の値，及びこれらを組み合わせたデータ，のいずれかを使う
ことを特徴とするミックスネットシステム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、複数の暗号文が入力されたとき、複数の機関が共同してこれらの順番の入れ替えと復号を行い、入力された暗号文との対応が分からないようにして出力するミックスネットの技術に関し、特に、入力される暗号文の長さに制限がなく、且つ、複数の機関の中に正しく操作を行わなかったものがあったならば、第三者でもそれを特定し、その事実を証明することができる技術に関する。
【背景技術】
【０００２】  ミックスネットは入力された暗号文の列に対して要素間の置換と各要素の復号を行うことにより、出力される復号文の列の各要素と入力された暗号文の列の各要素の対応を分からなくする操作である。【０００３】［従来の技術（１）］
従来のミックスネットで、正しく操作を行わなかった機関を特定しその事実を特定できるものとして、証明装置と検証装置とを用いる方法がある（例えば、特開２００２−３４４４４５号公報（文献１）参照）。この方法を図８を用いて説明する。【０００４】  文献１の証明装置は、置換と復号を正しく行ったことを証明する装置で、文献１の検証装置は、証明装置が行った証明が正しいことを検証する装置である。この両装置の作用により、仮に証明装置が正しく操作（置換と復号）しなければ、証明に失敗し、検証装置はこの証明装置が正しく操作しなかったことを突き止めることができる。【０００５】  文献１の証明装置と検証装置とを以下に示すように用いて、全体としてミックスネットとして動かす。最初に、各置換復号装置９１２に対応して秘密鍵９０６が決まる。この秘密鍵９０６から公開鍵９０１を生成し、この公開鍵９０１を全ての参加者装置９０３に配る。長さの決まった短い平文９０２をミックスネットの参加者装置９０３が、公開鍵９０１を用いて暗号化する。【０００６】  置換復号装置９１２は、入力された暗号文の列９１３を置換復号し、次の置換復号装置９１２に渡す（処理９０７）。以下これを繰り返すと最後に平文の列９１１が得られる。置換復号装置９１２は、自分の行った置換と復号の操作が正しいことを、文献１の証明装置を用いて証明する（処理９０８）。検証装置９０９は、文献１の検証装置を用いて置換復号装置の行う証明を検証する。この検証は、検証装置さえ準備できれば第三者にも可能である。【０００７】  以上において、参加者装置９０３が暗号化できる平文９０２は、公開鍵の長さと同程度の長さのものに限られる。それゆえ、より長い暗号文を平文を扱うことはできない。【０００８】［従来の技術（２）］
従来のミックスネットで、任意長の長さの暗号文を扱うことができるものにとして、ジュール（Ｊｕｅｌｓ）とヤコブソン（Ｊａｋｏｂｓｓｏｎ）による方式がある（例えば、「Ａｎ  Ｏｐｔｉｍａｌｌｙ  Ｒｏｂｕｓｔ  ＨｙｂｒｉｄＭｉｘ  Ｎｅｔｗｏｒｋ，Ｐｒｏｃ．ｏｆ  ｔｈｅ  ２０ｔｈ  ａｎｎｕａｌ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔａｔｉｏｎ，２００１」（文献２）参照）。この方式では入力される暗号文は、任意の共通鍵暗号方式により平文を暗号化したものであるため、平文の長さに特に制限がない。その一方、この方式は、暗号文の復号と入れ替えを行う複数の機関の内、これらの操作を正しく行わなかったものがあった場合、この共同して復号と入れ替えに当っている機関はこれを特定することができる。しかし、これら複数の機関の協力の無い第三者には、暗号文の操作を正しく行わなかった機関を特定することはできない．【０００９】  上記関係を図９を用いて説明する。文献２記載のミックスネットは、従来の技術（１）のミックスネットとほぼ同様に動作するが、入力される平文が長い平文１００２であっても良い。さらに置換と復号が正しく行われたかを置換復号装置同士で互いに検証することができる（処理１０１４）。しかし、第三者がこれを検証することは、従来の技術（１）と異なりできない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】  従来の技術（１）は、暗号文の復号と入れ替えを行う複数の機関の内、これらの操作を正しく行わなかったものが存在した場合、これを第三者が特定し、特定したものが不正者であることを証明できる。一方この方式は、扱うことのできる暗号文の長さが限られているという欠点を持つ。【００１１】  従来の技術（２）は、扱うことのできる暗号文の長さに制限が無い一方、暗号文の復号と入れ替えを行う複数の機関の内これらの操作を正しく行わなかったものが存在した場合、これを第三者が単独で特定することは不可能であるという欠点を持つ。【００１２】  そこで、本発明の目的は、暗号文の復号と入れ替えを複数の機関で行なう場合に、第三者が不正者を特定できるようにすることにある。
また、他の目的は、暗号文の長さの制限をなくすことにある。
【課題を解決するための手段】
【００１３】  本発明の参加者装置は、
共通鍵暗号方式の複数の共通鍵の一つを、複数の置換復号装置の一つの公開鍵により暗号化する鍵暗号化手段と、
共通鍵暗号方式の複数の共通鍵の一つで、与えられたデータを暗号化するデータ暗号化手段と、
暗号学的なハッシュ関数を用いて、与えられたデータのハッシュ値を計算し、このハッシュ値を前記複数の置換復号装置の一つの公開鍵により暗号化するハッシュ値暗号化手段と、
前記データ暗号化手段の最初の入力を平文とし、次からの、前記データ暗号化手段の入力を前回の前記データ暗号化手段，前記鍵暗号化手段，前記ハッシュ値暗号化手段の出力とする処理を、前記置換復号装置の数だけ繰り返す、繰り返し手段と、
前記繰り返し手段の処理により得られたデータを出力する出力手段と
を備えることを特徴とする。【００１４】  本発明の取りまとめ装置は、
複数のデータが入力されて、これらのデータの正当性を検証し、正当であることが判明したものだけを出力する構成を備えることを特徴とする。【００１５】  本発明の置換復号装置は、
入力データ列の各要素を、公開鍵暗号方式により暗号化された共通鍵暗号方式の共通鍵，共通鍵暗号方式により暗号化されたデータ，公開鍵暗号方式により暗号化されたハッシュ値に分割するデータ分割手段と、
前記暗号化された共通鍵暗号方式の共通鍵を前記公開鍵暗号方式の秘密鍵により復号する、共通鍵復号手段と、
復号した前記共通鍵を用いて、前記暗号化されたデータを復号して出力データを生成するデータ復号手段と、
前記暗号化されたハッシュ値を、前記公開鍵暗号方式の秘密鍵により復号したものを出力するハッシュ値復号手段と、
前記復号されたハッシュ値と前記生成された出力データのハッシュ値とを比較し、一致すればハッシュ値受理を、異なればハッシュ値不受理を出力するハッシュ値検証手段と、
前記出力データで、前記入力データ列の同一の要素のデータから生成されたという意味において対応する、前記ハッシュ値検証手段において受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列とする、出力データ列生成手段と、
前記出力データ列の各要素のハッシュ値が、必ず前記入力データ列のある要素に含まれる前記暗号化されたハッシュ値を復号したものであり、かつ両者の対応が一対一であることの証明文であるハッシュ値復号正当性証明文を生成する、ハッシュ値復号正当性証明手段と、
前記ハッシュ値検証手段において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成するハッシュ値不受理正当性証明手段と、
前記ハッシュ値復号正当性証明文と前記ハッシュ値不受理正当性証明文とを正当性証明文とし、これと前記出力データ列生成手段の出力した前記出力データ列とを出力する出力手段と
を備えることを特徴とする。【００１６】  本発明の検証装置は、
ハッシュ値復号正当性証明文に含まれる復号されたハッシュ値が、入力データ列のある要素の暗号化されたハッシュ値を復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力するハッシュ値復号正当性検証手段と、
前記復号されたハッシュ値が、出力データ列の各要素のハッシュ値と一致すれば受理を、一致しなければ不受理を出力するハッシュ値一致検証手段と、
入力暗号文の列の要素の内、前記ハッシュ値一致検証手段において不受理が出力されたハッシュ値に対応する要素に関しては、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を検証し、この証明文が正当であれば受理を、不当であれば不受理を出力するハッシュ値不受理正当性検証手段と、
前記入力データ列の要素に関して、前記ハッシュ値復号正当性検証手段で受理され、かつ前記ハッシュ値一致検証手段で受理及び前記ハッシュ値一致検証手段で不受理かつ前記ハッシュ値不受理正当性検証手段で受理のいずれかであり、かつ前記出力データ列には前記ハッシュ値一致検証手段で受理された要素に対応するものだけで、かつそれらが全て含まれているならば受理を、そうでなければ不受理を出力する正当性判定手段と
を備えることを特徴とする。【００１７】  本発明のミックスネットシステムは、
前記参加者装置複数と、前記取りまとめ装置と、前記置換復号装置と、前記検証装置とを備え、
安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数を生成し、公開する初期設定処理と、
前記複数の置換復号装置のそれぞれの公開鍵を生成し、公開する置換復号装置の初期設定処理と、
安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数，前記複数の置換復号装置のそれぞれの公開鍵，複数の前記共通鍵暗号方式の共通鍵及び前記参加者ごとに異なる平文とが前記参加者装置のそれぞれに入力され、
前記参加者装置のそれぞれから、前記置換復号装置へ入力するデータをそれぞれ出力する参加処理と、
前記参加処理で得られた置換復号装置へ入力するデータ全てが前記取りまとめ装置に入力され、この時の前記取りまとめ装置の出力を入力データ列とする、取りまとめ処理と、
前記置換復号装置の一つに、入力データ列と公開鍵暗号方式の秘密鍵とが入力され、この置換復号装置が出力データ列、正当性証明文の列を出力する、置換復号処理と、
前記取りまとめ処理の出力である入力データ列を最初の入力データ列として前記置換復号処理を、用いる置換復号装置を交換しながら次々と繰り返し行う処理で、最初の置換復号処理における入力データ列は、前記取りまとめ処理の出力する入力データ列であり、以降の置換復号処理における入力データ列は、直前の置換復号処理における出力データの列とし、最後の置換復号処理の出力する出力データ列を復号結果とし、最後の置換復号処理を除く各置換復号処理の出力する出力データ列を復号途中結果とし、全ての置換復号処理の出力する正当性証明文を、全体の正当性証明文とし、復号結果，復号途中結果，全体の正当性証明文とを出力する統合置換復号処理と、
復号結果，復号途中結果，全体の正当性証明文から各置換復号装置の入力及び出力を分離し、各置換復号処理の入力データ列と出力データ列と正当性証明文とが前記検証装置に入力され、前記検証装置が受理または不受理を出力する検証処理と、
全ての置換復号処理に関する検証処理の出力を集めて、全てが受理であれば全体としての受理を、そうでなければ全体としての不受理を出力するミックスネット判定処理と
を行うことを特徴とする。
【発明の効果】
【００１８】  本発明では、各参加者装置が、平文を共通鍵暗号方式の共通鍵を使用して暗号化すると共に、上記暗号鍵を公開鍵により暗号化し、これらを置換復号装置へ送付する。これにより、扱うことのできる暗号文の長さに制限をなくすことができる。【００１９】  また、本発明では、各置換復号装置が行った、公開鍵を利用した検証可能な証明文を、検証装置が公開鍵を利用して検証する。これにより、暗号文の復号と入れ替えを行う複数の機関の中に操作を正しく行わなかったものが存在した場合、これを第三者が特定し、特定されたものが不正者であることを証明できる。
【図面の簡単な説明】
【００２０】［図１］本発明に係るミックスネットシステムの全体構成を示すブロック図である。
［図２］本発明の実施例１における参加者装置の構成例を示すブロック図である。
［図３］本発明の実施例１における置換復号装置の構成例を示すブロック図である。
［図４］本発明の実施例１における検証装置の構成例を示すブロック図である。
［図５］本発明の実施例２における参加者装置の構成例を示すブロック図である。
［図６］本発明の実施例２における置換復号装置の構成例を示すブロック図である。
［図７］本発明の実施例２のおける検証装置の構成例を示すブロック図である。
［図８］従来の技術１を説明するためのブロック図である。
［図９］従来の技術２を説明するためのブロック図である。
【発明を実施するための最良の形態】
【００２１】  次に本発明の実施例について図面を参照して詳細に説明する。【００２２】１  実施例１
１．１概要
実施例１の概要について、図１〜図４を参照しながら説明する。【００２３】  本実施例に係るミックスネットシステムは、図１に示すように、複数の参加者装置１０３と、取りまとめ装置１０４と、複数の置換復号装置１１２と、検証装置１０９とから構成される。【００２４】［参加者装置］
図２に示すように、参加者装置１０３は、鍵暗号化手段２０５と、データ暗号化手段２０６と、ハッシュ値暗号化手段２０７と、知識の連結手段２０８と、繰り返し手段２１３と、乱数の知識の証明手段２１０と、出力手段２１５とを有する。【００２５】  ここで、鍵暗号化手段２０５は、共通鍵暗号方式の複数の共通鍵の一つを、複数の置換復号装置１１２の一つの公開鍵１０１により暗号化し、さらにこの時暗号化した共通鍵の知識の証明文を生成する。データ暗号化手段２０６は、共通鍵暗号方式の複数の共通鍵の一つで、与えられたデータ２１４を暗号化する。ハッシュ値暗号化手段２０７は、暗号学的なハッシュ関数を用いて、与えられたデータのハッシュ値を計算し、このハッシュ値を複数の置換復号装置１１２の一つの公開鍵により暗号化する。知識の連結手段２０８は、与えられたデータ２１４を、複数の置換復号装置１１２の一つの公開鍵１０１により暗号化し、さらにこの時の暗号化に用いた秘密の乱数の知識の証明文を生成する【００２６】  繰り返し手段２１３は、データ暗号化手段２０６の最初の入力を平文１０２とし、次からの、データ暗号化手段２０６の入力を前回のデータ暗号化手段２０６，鍵暗号化手段２０５，ハッシュ値暗号化手段２０７，知識の連結手段２０８の出力とする処理を、置換復号装置１１２の数だけ繰り返す。全体の乱数の知識の証明手段２１０は、知識の連結手段２０８による処理を繰り返すことにより最終的に得られたデータに関して、処理の繰り返し全てで使った秘密の乱数の和の知識の証明文を生成して出力する。出力手段２１５は、繰り返し手段２１３の処理により得られたデータを暗号文２１１として出力すると共に、この暗号文２１１を作成したのが正当な参加者装置であることを証明するデータを出力する。【００２７】［取りまとめ装置］
取りまとめ装置１０４には、複数の参加者装置１０３のそれぞれから、暗号文２１１と、この暗号文２１１を作成したのが正当な参加者装置であることを証明するデータが入力される。そして、取りまとめ装置１０４は、入力された暗号文２１１が正当な参加者装置によって生成されたことを検証し、正当であることが判明したものだけを置換復号装置１１２の一つに出力する。【００２８】［置換復号装置］
図３に示すように、置換復号装置１１２は、データ分割手段３２２と、共通鍵の知識の検証手段３０７と、秘密の乱数の知識の検証手段３０８と、共通鍵復号手段３１０と、データ復号手段３１３と、ハッシュ値復号手段３１２と、ハッシュ値検証手段３１７と、連結データ復号手段３１４と、出力データ列生成手段３１１と、ハッシュ値復号正当性証明手段３１５と、連結データ復号正当性証明手段３１６と、ハッシュ値不受理正当性証明手段３１８と、出力手段とを有する。【００２９】  ここで、データ分割手段３２２は、取りまとめ装置１０４または他の置換復号装置から入力される入力データ列１０５の各要素を、公開鍵暗号方式により暗号化された共通鍵暗号方式の共通鍵３０２，共通鍵暗号方式により暗号化されたデータ３０３，公開鍵暗号方式により暗号化されたハッシュ値３０４，公開鍵暗号方式により暗号化された連結データ３０５，暗号化された共通鍵の知識の証明文３０１，連結データ暗号化に用いた秘密の乱数の知識の証明文３０６に分割する。【００３０】  共通鍵の知識の検証手段３０７は、共通鍵の知識の証明文３０１の正当性を検証し、正当なら受理を不当なら不受理を出力する。秘密の乱数の知識の検証手段３０８は、秘密の乱数の知識の証明文３０６を検証し、正当なら受理を不当なら不受理を出力する。共通鍵復号手段３１０は、暗号化された共通鍵暗号方式の共通鍵を、公開鍵暗号方式の秘密鍵１０６により復号する。データ復号手段３１３は、復号した共通鍵を用いて、暗号化されたデータ３０３を復号して出力データを生成する。ハッシュ値復号手段３１２は、暗号化されたハッシュ値３０４を、公開鍵暗号方式の秘密鍵１０６により復号したものを出力する。ハッシュ値検証手段３１７は、復号されたハッシュ値と生成された出力データのハッシュ値とを比較し、一致すればハッシュ値受理を、異なればハッシュ値不受理を出力する。連結データ復号手段３１４は、暗号化された連結データ３０５を、公開鍵暗号方式の秘密鍵により復号する。【００３１】  出力データ列生成手段３１１は、出力データと復号された連結データで、入力データ列１０５の同一の要素のデータから生成されたという意味において対応する、ハッシュ値検証手段３１７、共通鍵の知識の検証手段３０７、秘密の乱数の知識の検証手段３０６の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列１０７とする。【００３２】  ハッシュ値復号正当性証明手段３１５は、出力データ列１０７の各要素のハッシュ値が、必ず入力データ列１０５のある要素に含まれる暗号化されたハッシュ値を復号したものであり、かつ両者の対応が一対一であることの証明文であるハッシュ値復号正当性証明文を生成する。連結データ復号正当性証明手段３１６は、出力データ列１０７の各要素に含まれる復号された連結データが、必ず入力データ列１０５のある要素に含まれる暗号化された連結データを復号したものであり、かつ両者の対応が一対一であることの証明文である連結データ復号正当性証明文を生成する。ハッシュ値不受理正当性証明手段３１８は、ハッシュ値検証手段３１７において不受理を出力された場合、この不受理の���力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成する。【００３３】  出力手段は、ハッシュ値復号正当性証明文と連結データ復号正当性証明文とハッシュ値不受理正当性証明文とを正当性証明文１０８とし、これと出力データ列生成手段３１１の出力した出力データ列１０７とを出力する。【００３４】［検証装置］
図４に示すように、検証装置１０９は、共通鍵の知識の検証手段４０２と、秘密の乱数の知識の検証手段４０４と、ハッシュ値復号正当性検証手段４０６と、ハッシュ値一致検証手段４０８と、連結データ復号正当性検証手段４０７と、ハッシュ値不受理正当性検証手段４０９と、正当性判定手段４０５とを有する。【００３５】  共通鍵の知識の検証手段４０２は、取りまとめ装置１０４または置換復号装置１１２から入力される入力データ列１０５の各要素に属する共通鍵の知識の証明文３０１の正当性を検証し、正当なら受理を不当なら不受理を出力する。秘密の乱数の知識の検証手段４０４は、入力データ列１０５の各要素に属する秘密の乱数の知識の証明文３０６を検証し、正当なら受理を不当なら不受理を出力する。ハッシュ値復号正当性検証手段４０６は、ハッシュ値復号正当性証明文４０１に含まれる復号されたハッシュ値が、入力データ列１０５のある要素の暗号化されたハッシュ値を復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力する。【００３６】  ハッシュ値一致検証手段４０８は、復号されたハッシュ値が、置換復号装置１１２の出力データ列１０７の各要素のハッシュ値と一致すれば受理を、一致しなければ不受理を出力する。連結データ復号正当性検証手段４０７は、出力データ列１０７の各要素に含まれる復号された連結データが、入力データ列１０５のある要素に含まれる、暗号化された連結データ３０５を復号したものに一致し、両者に一対一の関係があることを検証し、両者が一致し一対一の関係があれば受理を、無ければ不受理を出力する。ハッシュ値不受理正当性検証手段４０９は、入力暗号文の列３０３の要素の内、ハッシュ値一致検証手段４０８において不受理が出力されたハッシュ値に対応する要素に関しては、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文４００を検証し、この証明文が正当であれば受理を、不当であれば不受理を出力する。【００３７】  正当性判定手段４０５は、入力データ列１０５の要素のなかで、この要素に対する共通鍵の知識の検証手段４０２と秘密の乱数の知識の検証手段４０４の両方において受理されたもの全てに関して、以下の全ての条件が満たされているならば受理を、そうでなければ不受理を出力する。
（Ａ）ハッシュ値復号正当性検証手段４０６と、連結データ復号正当性検証手段４０７との両方において受理。
（Ｂ）ハッシュ値一致検証手段４０８で受理、あるいは、ハッシュ値一致検証手段４０８で不受理かつハッシュ値不受理正当性検証手段４０９で受理。
（Ｃ）出力データ列１０７には、共通鍵の知識の検証手段４０２と秘密の乱数の知識の検証手段４０４とハッシュ値一致検証手段４０８とで受理された要素に対応するものだけで、かつそれらが全て含まれている。【００３８】［ミックスネットシステムの動作］
まず、安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数を生成し、公開する初期設定処理１００を行なう。ついで、複数の置換復号装置１１２のそれぞれの公開鍵を生成し、公開する置換復号装置の初期設定処理３２０を行なう。【００３９】  ついで、複数の参加者装置１０３のそれぞれにおいて、安全変数，公開鍵暗号方式の領域変数，暗号学的なハッシュ関数，共通鍵暗号方式の暗号化関数，複数の置換復号装置１１２のそれぞれの公開鍵，共通鍵暗号方式の複数の共通鍵及び参加者装置１０３ごとに異なる平文を入力し、取りまとめ装置１０４を介して置換復号装置へ出力するデータを生成する参加処理を行なう。ついで、参加処理で得られたデータ全てを取りまとめ装置１０４に入力し、取りまとめ処理を行ない、その結果を入力データ列１０５として置換復号装置１１２の一つに出力する。【００４０】  ついで、複数の置換復号装置１１２のそれぞれにおいて、入力データ列１０５と公開鍵暗号方式の秘密鍵１０６とを入力し、出力データ列１０７と正当性証明文１０８の列とを生成する置換復号処理を行なう。この際、最初の置換復号装置１１２における入力データ列１０５は、取りまとめ装置１０４からの入力データ列１０５とし、以降の置換復号装置１１２における入力データ列１０５は、それぞれの直前の置換復号装置１１２からの出力データ列１０７とする。最後の置換復号装置１１２における出力データ列１０７を復号結果とし、最後の置換復号装置１１２を除く各置換復号装置１１２からの出力データ列１０７を復号途中結果とする。全ての置換復号装置１１２から出力される正当性証明文１０８を、全体の正当性証明文とし、復号結果，復号途中結果，全体の正当性証明文とを出力する。以上の処理を統合置換復号処理という。【００４１】  ついで、復号結果，復号途中結果，全体の正当性証明文から各置換復号装置１１２の入力及び出力を分離し、各置換復号装置１１２における入力データ列１０５と出力データ列１０７と正当性証明文１０８とを検証装置１０９に入力し、検証装置１０９において受理または不受理を出力する検証処理を行なう。全ての置換復号処理に関する検証処理の結果を集めて、全てが受理であれば全体としての受理を、そうでなければ全体としての不受理を出力するミックスネット判定処理とを行う。【００４２】  なお、参加者装置１０３は、ハッシュ値暗号化手段２０７の最初の入力として、平文１０２と併せて、乱数，日時，ミックスネットのセッションに固有の値，及びこれらを組み合わせたデータ，のいずれかを使ってもよい。【００４３】１．２記法
以下で用いる記法の説明をする。Ｈａｓｈ（）を暗号学的なハッシュ関数、ｑを素数、Ｃを位数がｑの楕円曲線、ＧをＣ上のある点、共通鍵暗号方式の暗号化関数をｅｎｃ［ｅ］（）、復号関数をｄｅｃ［ｅ］（）とする。但ここで、ｅは暗号化または復号に使う共通鍵を表すとする。ハッシュ関数の値域のビット数をＬとし、共通鍵暗号方式の暗号化関数の鍵のビット数はＬとし、ｑのビット数はＬより５ビット以上大きいとする。Ｌを安全変数と呼ぶ。数式Ｘ＝［ｘ］ＧはＸがＧの楕円曲線上のｘ倍点であることを表す。また、加算記号「＋」は、楕円曲線上の点に対して使われた場合、これは楕円曲線上の演算を意味する。【００４４】  本発明の任意長の暗号文を扱える第三者検証可能なミックスネットシステムは、複数の置換復号装置と、複数のミックスネット参加者の参加者装置と、検証機関の検証装置と、取りまとめ機関の取りまとめ装置から構成される。置換復号装置の数をｍ、参加者装置の数をｎとし、ｊ番目の置換復号装置を，Ｓ（ｊ）、ｉ番目の参加者装置をＵと記す。【００４５】  Ψは、Ｌビットの整数値から楕円曲線Ｃ上の点への一対一の写像で、Φは、楕円曲線上の点からＬビットの整数値への全射で、Φ・Ψは恒等写像で、Φ，Ψ共に効率的に計算できるものとする。具体的なΦの例として、楕円曲線の点Ｅが与えられたときｅ＝Φ（Ｅ）として、Ｅのｘ座標の下からＬビットを採用する写像が挙げられる。この場合のΨの具体例としては、Ｌビットのビット列ｅが与えられたとき、楕円曲線上の点のｘ座標の下Ｌビットをｅとし、残りのビットに決められた０をパディングする。そしてＣ上この様なｘ座標を持つ点があるかを調べる。もしなければパディングを決められた手順で変更していき、これがＣ上の点のなｘ座標となるまで続ける。Ｃ上の点が見つかればこれをΨ（ｅ）とする。この点（Ψ（ｅ））のｘ座標の下Ｌビットは常にｅであり続けるので、明らかにΦ・Ψ（ｅ）＝ｅで、Φ・Ψは恒等写像である。【００４６】１．３  具体例
実施例１について、図１〜図４を参照しながら具体的に説明する。【００４７】［初期設定］
最初に初期設定のための初期設定機関は、コンピュータ等によって実現される初期設定装置１００を用いて、平文のビット長Ａと、安全変数Ｌと、Ｌより５そのビット長が大きい素数ｑと、位数がｑの楕円曲線Ｃと、Ｃ上の点Ｇ、出力のビット長がＬの暗号学的なハッシュ関数Ｈａｓｈ（）と、長さＬの鍵を使う共通鍵暗号方式と、上記共通鍵暗号方式の暗号化関数ｅｎｃ［ｅ］（）および復号関数ｄｅｃ［ｅ］と、Ｌビットのビット列からＣ上への点への関数Ψ（）と、Ｃ上の点からＬビットのビット列への写像Φ（）とを決定し公開する。ここで、素数ｑと、位数がｑの楕円曲線Ｃと、Ｃ上の点Ｇが、公開鍵暗号方式の領域変数となる。【００４８】［置換復号装置の初期設定］
次に全ての置換復号装置１１２は、次の初期設定処理を行う。全ての置換復号装置Ｓ（ｊ）（ｊ＝１，．．．，ｍ）内の初期設定手段３２０（図３参照）は、秘密鍵１０６ｘ（ｊ）∈Ｚ／ｑＺを一様無作為に選び、それを自置換復号装置Ｓ（ｊ）内に保存すと共に、公開鍵１０１Ｘ（ｊ）＝［ｘ（ｊ）］Ｇを生成し、公開する。【００４９】  更に、各置換復号装置Ｓ（ｊ）内の初期設定手段３２０は、ｒ（ｊ）∈Ｚ／ｑＺを一様無作為に選び、
0004687465.tif 000002
を計算し、γ（ｊ），α（ｊ）をｘ（ｊ）の知識の零知識証明文３２１として公開する。【００５０】［参加者装置の暗号文生成］
ｉ＝１，．．．，ｎに関して、参加者装置１０３Ｕｉ（図２参照）は、長さがＡビットの平文１０２Ｍｉを決定する。各参加者装置１０３Ｕｉは、最初のデータ２１４として、ｃｉ（ｍ＋１）＝Ｍｉと、Ｔ’ｉ（ｍ＋１）＝Ｇと、任意データ２０３（それぞれがＬビットの任意の文字列Ｋｉ（ｍ＋１），Ｋ’ｉ（ｍ＋１），Ｓｉ（ｍ＋１），Ｓ’ｉ（ｍ＋１），Ｐｉ（ｍ＋１））とを含むデータを生成する（処理２００）。更に、鍵生成手段２０４が、ｊ＝１，．．．，ｍに関してＺ／ｑＺの要素ｒ［１］ｉ（ｊ），ｒ［２］ｉ（ｊ），ｒ［３］ｉ（ｊ），ｒ［４］ｉ（ｊ），ｒ［５］ｉ（ｊ）及びＣ上の点Ｅｉ（ｊ）を一様無作為に選ぶ。【００５１】  その後、鍵暗号化手段２０５、データ暗号化手段２０６、ハッシュ値暗号化手段２０７、知識の連結手段２０８、証明文まとめ手段２０９、証明生成手段２１０および出力手段２１５が、ｊ＝ｍ，（ｍ−１），．．．，１の順番で繰り返し以下の処理２１３を行う。【００５２】  ここで任意の文字列としては、乱数，セッション固有の数，日時等を選ぶ場合がある。
乱数を用いれば、最終的な復号文の集合から自分の平文の存在を参加者装置が確認できる効果があり、セッション固有の数や日時を入れれば、他のセッションに使われた暗号文を再利用していないことが分かる効果がある。【００５３】・鍵暗号化手段２０５における暗号化処理
共通鍵ｅｉ（ｊ）の暗号化のため、
0004687465.tif 000003
なるＥｉ（ｊ）を求め、
0004687465.tif 000004
を計算し、計算結果を出力手段２１５に入力する。【００５４】・鍵暗号化手段２０５における共通鍵の知識の証明文の生成処理
0004687465.tif 000005
と、
0004687465.tif 000006
とを計算し、それらを証明文まとめ手段２０９に入力する。【００５５】・データ暗号化手段２０６におけるデータ暗号化処理
0004687465.tif 000007
と、
0004687465.tif 000008
とを計算し、ｃｉ（ｊ）を出力手段２１５に入力する。【００５６】・ハッシュ値暗号化手段２０７におけるハッシュ値暗号化処理
0004687465.tif 000009
を計算し、Ｓｉ（ｊ），Ｓ’ｉ（ｊ）を出力手段２１５に入力する。【００５７】・知識の連結手段２０８における知識の連結処理
0004687465.tif 000010
を計算し、Ｔｉ（ｊ），Ｔ’ｉ（ｊ）を出力手段２１５に入力する。【００５８】・知識の連結手段２０８における乱数の知識の証明文の生成処理
0004687465.tif 000011
と、
0004687465.tif 000012
とを計算し、それらを証明文まとめ手段２０９に入力する。【００５９】・証明文まとめ手段２０９における共通鍵の知識の証明文と乱数の知識の証明文とのまとめ処理
共通鍵の知識の証明文γｉ（ｊ），αｉ（ｊ）と、乱数の知識の証明文γ’ｉ（ｊ），α’ｉ（ｊ）とをまとめた証明文Ｐｉ（ｊ）＝［γｉ（ｊ），αｉ（ｊ），γ’ｉ（ｊ），α’ｉ（ｊ）を生成し、ｊ＝１であれば（Ｐｉ（１）であれば）、それを証明文２１２の一部として出力する。【００６０】・証明生成手段２１０における処理
Ｚ／ｑＺの要素ｒ［４］ｉ（０）を一様無作為に選び、以下の全体の乱数の知識の証明を計算し、Ｐｉ（０）を証明文の一部として出力する。
0004687465.tif 000013
0004687465.tif 000014
【００６１】・出力手段２１５における処理
鍵暗号化手段２０５からの入力Ｋｉ（ｊ），Ｋ’ｉ（ｊ）と、データ暗号化手段２０６からの入力ｃｉ（ｊ）と、ハッシュ値暗号化手段２０７からの入力Ｓｉ（ｊ），Ｓ’ｉ（ｊ）と、知識の連結手段２０８からの入力Ｔｉ（ｊ），Ｔ’ｉ（ｊ）とからデータ２１４’（Ｋｉ（ｊ），Ｋ’ｉ（ｊ），ｃｉ（ｊ），Ｓｉ（ｊ），Ｓ’ｉ（ｊ），Ｔｉ（ｊ），Ｔ’ｉ（ｊ））を生成し、ｊ−１でなければ、データ２１４’をデータ２１４としてフィードバックし、ｊ＝１ならば、（Ｋｉ（１），Ｋ’ｉ（１），ｃｉ（１），Ｓｉ（１），Ｓ’ｉ（１），Ｔｉ（１），Ｔ’ｉ（１））を暗号文２１１として出力する。【００６２】  つまり、参加者装置１０３Ｕｉ、暗号文２１１（Ｋｉ（１），Ｋ’ｉ（１），ｃｉ（１），Ｓｉ（１），Ｓ’ｉ（１），Ｔｉ（１），Ｔ’ｉ（１））と証明文Ｐｉ（１），Ｐｉ（０）とを取りまとめ機関の取りまとめ装置１０４へ送付する。【００６３】［取りまとめ装置による暗号文の検証］
取りまとめ装置１０４は、ｉ＝１，．．．，ｎに関して、全体に対する証明文を検証して、
0004687465.tif 000015
が成り立つことを確認する。【００６４】  また、この全体に対する証明文を検証装置１０９に送る（図１、処理１１０）。これが成り立つことを確認できたｉに関してだけ、
0004687465.tif 000016
を一番目の置換復号装置に送る（処理１０５）。図１中では取りまとめ装置１０４に入力されたデータは５個であったのが、４個になって出てきた例を表している。以下暗号文の数が減少するが、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番付ける。また、以下において、
0004687465.tif 000017
は、ｊ＝１の場合を除いて前記のそれとは一般に異なる。【００６５】［置換復号装置による暗号文の順序入れ替えと復号］
ｊ＝１，．．．，ｍに関して順番に、置換復号装置１１２Ｓ（ｊ）は、以下の計算及び検証を行う。【００６６】  置換復号装置１１２Ｓ（ｊ）には、
暗号化された共通鍵暗号方式の共通鍵３０２（図３中、共通鍵暗号文と略記）Ｋｉ（ｊ），Ｋ’ｉ（ｊ）と、
暗号化されたデータ３０３（図３中、データ暗号文と略記）
ｃｉ（ｊ）と、
暗号化されたハッシュ値３０４（図３中、ハッシュ値暗号文と略記）
Ｓｉ（ｊ），Ｓ’ｉ（ｊ）と、
暗号化された連結データ３０５（図３中、連結データ暗号文と略記）
Ｔｉ（ｊ），Ｔ’ｉ（ｊ）と、
共通鍵の知識の証明文３０１（図３中、鍵の知識証明文と略記）と秘密の乱数の知識の証明文３０６（図３中、乱数知識証明文と略記）
Ｐｉ（ｊ）
とからなる入力データ列１０５が入力される。この入力データ列１０５は、データ分割手段３２２によって上記した各要素３０１〜３０６に分解される。【００６７】  置換復号装置１１２Ｓ（ｊ）では全てのｉ（ｉ＝１，．．．，ｎ）に関して，以下の処理を行う。【００６８】  共通鍵の知識の検証手段３０７が、
0004687465.tif 000018
を確認する。【００６９】  秘密の乱数の知識の検証手段３０８が、
0004687465.tif 000019
を確認する。等式が成り立たないｉに関しては、最終的な出力データ列には加えない。
ここでも暗号文の数が減少するが、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番づける。【００７０】  共通鍵復号手段３１０が、
0004687465.tif 000020
をデータ復号手段３１３に入力する。【００７１】  データ復号手段３１３が、
0004687465.tif 000021
なる演算を行う。【００７２】  ハッシュ値復号手段３１２が、
0004687465.tif 000022
なる演算を行う。【００７３】  連結データ復号手段３１４が、
0004687465.tif 000023
なる演算を行う。【００７４】  得られたデータ列は（Ｋｉ（ｊ＋１），Ｋ’ｉ（ｊ＋１），ｃｉ（ｊ＋１），Ｓｉ（ｊ＋１），Ｓ’ｉ（ｊ＋１），Ｔ’ｉ（ｊ＋１），Ｐｉ（ｊ＋１），Ｈｉ（ｊ），Ｔ’ｉ（ｊ＋１））である。【００７５】  置換手段３１１は、一様無作為に［１，．．．，ｎ］から［１，．．．，ｎ］への置換π［ｊ］（）を選び、以下の置換処理を行う。
0004687465.tif 000024
【００７６】  次に、ハッシュ値復号正当性証明手段３１５により、上記Ｈｉ（ｊ）が正しく生成されたことの証明（ハッシュ値復号正当性証明文）を生成する。【００７７】  連結データ復号正当性証明手段３１６により、Ｔ’ｉ（ｊ＋１）が正しく生成されたことの証明（連結データ復号正当性証明文）を生成する。【００７８】  これらの証明には、例えば文献「Ａｎ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ａ  Ｕｎｉｖｅｒｓａｌｌｙ  Ｖｅｒｉｆｉａｂｌｅ  Ｅｌｅｃｔｒｏｎｉｃ  Ｖｏｔｉｎｇ  Ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  Ｓｈｕｆｆｌｉｎｇ，Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ２００２」の方法を用いれば可能である。【００７９】  次に、全てのｉ（ｉ＝１，．．．，ｎ）に関して、ハッシュ値検証手段３１７において、
0004687465.tif 000025
が成り立つことを確認する。この式が成り立たないｉが存在すれば、ハッシュ値不受理正当性証明手段３１８により、そのｉに関してπ［ｊ］（ｉ），Ｅｉ（ｊ）を明らかにして、Ｅｉ（ｊ）を正しく生成したことの零知識証明（ハッシュ値不受理正当性証明文）を生成する。ここでも暗号文の数が減少するが（処理３１９）、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番付ける。【００８０】  最後に出力データ列１０７（Ｋｉ（ｊ＋１），Ｋ’ｉ（ｊ＋１），ｃｉ（ｊ＋１），Ｓｉ（ｊ＋１），Ｓ’ｉ（ｊ＋１），Ｔｉ（ｊ＋１），Ｔ’ｉ（ｊ＋１），Ｐｉ（ｊ＋１），Ｈｉ（ｊ））を次の置換復号装置Ｓ（ｊ＋１）に送る。【００８１】  ハッシュ値復号正当性証明文と連結データ復号正当性証明文とハッシュ値不受理正当性証明文とを正当性証明文１０８とし検証装置１０９に送る。【００８２】  全ての置換復号装置Ｓ（ｊ）（ｊ＝１，．．．，ｍ）に関して処理が終わると順番が入れ替えられた平文１１１［Ｍｉ］ｉ＝１，．．．，ｎが得られる。【００８３】［検証装置の処理］
検証者の検証装置１０９には、
ハッシュ値復号正当性証明文４０１（図４中、ハッシュ値証明文と略記）、連結データ復号正当性証明文４０３（図４中、連結証明文と略記）およびハッシュ値不受理正当性証明文４００（図４中、不受理証明文と略記）からなる正当性証明文１０８と、入力データ列１０５と、
出力データ列１０７と、
全体の乱数の知識の証明文１１０とが入力される。【００８４】  最初に全てのｉに関して、全体の乱数の知識の証明文１１０を検証する検証手段５００で、
0004687465.tif 000026
が成り立つことを確認する。【００８５】  全てのｊ＝１，．．．，ｍに関して順番に以下の計算及び検証を行う。全てのｉ（ｉ＝１，．．．，ｎ）に関して、共通鍵の知識の検証処理を行う検証手段４０２により、
0004687465.tif 000027
を確認し、秘密の乱数の知識の検証処理を行う検証手段４０４により、
0004687465.tif 000028
を確認する。等式が成り立たないｉのみに関しては以降の処理を行わない。【００８６】  ハッシュ値復号正当性の検証処理を行う検証手段４０６により、［Ｈｉ（ｊ）］ｉ＝１，．．．，ｎが正しく生成されていることを検証する（証明に対応した方法で行う、例えば前出の文献の方法を使う）。【００８７】  連結データ復号正当性の検証処理を行う検証手段４０７により、｛Ｔ’ｉ（ｊ＋１）］ｉ＝１，．．．，ｎが正しく生成されていることを検証する（証明に対応した方法で行う、例えば前出の文献の方法を使う）。【００８８】  ハッシュ値一致検証処理を行う比較手段４０８において、全てのｉ（ｉ＝１，．．．，ｎ）に関して、
0004687465.tif 000029
が成り立つことを確認する。もし成り立たないｉが存在すれば、ハッシュ値不受理正当性の検証処理を行う検証手段４０９において、そのｉに関してπ［ｊ］（ｉ），Ｅｉ（ｊ）を明らかにされていること、式Ｅｉ（ｊ）か正しく生成されていることを検証し、ｃπ［ｊ］（ｉ）（ｊ）か正しく復号されていることを確認する。【００８９】  正当性判定処理を行う検証手段４０５において、共通鍵の知識の検証処理を行う検証手段４０２と秘密の乱数の知識の検証処理を行う検証手段４０４の両方において受理されたもの全てに関して、ハッシュ値復号正当性の検証処理を行う検証手段４０６と連結データ復号正当性の検証処理を行う検証手段４０７の両方において受理され、かつハッシュ値一致検証処理を行う比較手段４０８で受理あるいはハッシュ値一致検証処理を行う比較手段４０８で不受理かつハッシュ値不受理正当性検証処理を行う検証手段４０９で受理であり、かつ出力データ列には、共通鍵の知識の検証処理と、秘密の乱数の知識の検証処理と、ハッシュ値一致検証処理とで受理された要素に対応するものだけで、かつそれが全て含まれているならば受理を、そうでなければ不受理を出力する。【００９０】２  実施例２
２．１
実施例２の概要について、図１，図５，図６，図７を参照しながら説明する。【００９１】  本実施例に係るミックスネットシステムは、図１に示すように、複数の参加者装置１０３と、取りまとめ装置１０４と、複数の置換復号装置１１２と、検証装置１０９とから構成される。参加者装置１０３は、図５に示すような構成を有し、知識の連結手段２０８及び乱数の知識の証明手段２１０を有しない点を除いて、第１の実施例における参加者装置と同様である。取りまとめ装置１０４もまた、第１の実施例における取りまとめ装置と同様である。【００９２】［置換復号装置］
図６に示すように、置換復号装置１１２は、データ分割手段７２３と、共通鍵の知識の検証手段７０７と、共通鍵復号手段７１０と、データ復号手段７１３と、ハッシュ値復号手段７１２と、ハッシュ値検証手段７１７と、出力データ列生成手段７１１と、重複データ削除確認手段７２０と、ハッシュ値復号正当性証明手段７１５と、ハッシュ値不受理正当性証明手段７１８と、出力手段とを有する。【００９３】  ここで、データ分割手段７２３は、取りまとめ装置１０４または他の置換復号装置から入力される入力データ列１０５の各要素を、公開鍵暗号方式により暗号化された共通鍵暗号方式の共通鍵７０２，共通鍵暗号方式により暗号化されたデータ７０３，公開鍵暗号方式により暗号化されたハッシュ値７０４，暗号化された共通鍵の知識の証明文７０１に分割する。【００９４】  出力データ列生成手段７１１は、出力データで、入力データ列１０５の同一の要素のデータから生成されたという意味において対応する、ハッシュ値検証手段７１７及び共通鍵の知識の検証手段７０７の全てにおいて受理を出力されたものだけを列の要素とするデータ列を生成し、さらに各要素の順番を一様無作為に並び替え出力データ列１０７とする。重複データ削除確認手段７２０は、出力データ列１０７の各要素に重複がある場合、以降の処理でこれが削除されていることを確認したら受理を、でなければ不受理を出力する。【００９５】  ハッシュ値不受理正当性証明手段７１５は、出力データ列１０７の各要素に含まれる復号された連結データが、必ず入力データ列１０５のある要素に含まれる暗号化された連結データを復号したものであり、ハッシュ値検証手段７１７において不受理を出力された場合、この不受理の出力が正当であることの証明文であるハッシュ値不受理正当性証明文を生成する。出力手段は、ハッシュ値復号正当性証明文とハッシュ値不受理正当性証明文とを正当性証明文１０８とし、これと出力データ列生成手段７１１の出力した出力データ列１０７とを出力する。その他の構成は、第１の実施例における置換復号装置と同様である。【００９６】［検証装置］
図７に示すように、検証装置１０９は、共通鍵の知識の検証手段８０２と、ハッシュ値復号正当性検証手段８０６と、ハッシュ値一致検証手段８０８と、ハッシュ値不受理正当性検証手段８０９と、正当性判定手段８０５とを有する。【００９７】  正当性判定手段８０５は、入力データ列１０５の要素のなかで、この要素に対する共通鍵の知識の検証手段４０２において受理されたもの全てに関して、以下の全ての条件が満たされているならば受理を、そうでなければ不受理を出力する。
（Ａ）ハッシュ値復号正当性検証手段８０６で受理。
（Ｂ）ハッシュ値一致検証手段８０８で受理、あるいは、ハッシュ値一致検証手段８０８で不受理かつハッシュ値不受理正当性検証手段８０９で受理。
（Ｃ）出力データ列１０７には、共通鍵の知識の検証手段８０２とハッシュ値一致検証手段８０８とで受理された要素に対応するものだけで、かつそれらが全て含まれている。
その他の構成は、第２の実施例における検証装置と同様である。【００９８】  ミックスネットシステムの動作は、第１の実施例と同様であるから、その説明を省略する。【００９９】２．２具体例
実施例２について、図１，図５，図６，図７を参照しながら具体的に説明する。【０１００】［初期設定］
最初に初期設定装置１００は、平文のビット長Ａと、安全変数Ｌと、Ｌより５そのビット長が大きい素数ｑと、位数がｑの楕円曲線Ｃと、Ｃ上の点Ｇと、出力のビット長がＬの暗号学的なハッシュ関数Ｈａｓｈ（）と、長さＬの鍵を使う共通鍵暗号方式と、上記共通鍵暗号方式の暗号化関数ｅｎｃ［ｅ］（）および復号関数ｄｅｃ［ｅ］と、Ｌビットのビット列からＣ上への点への関数Ψ（）と、Ｃ上の点からＬビットのビット列への写像Φ（）とを決定し公開する。【０１０１】［置換復号装置の初期設定］
次に全ての置換復号装置Ｓ（ｊ）（ｊ＝１，．．．，ｍ）は、次の初期設定処理を行う。全ての置換復号装置Ｓ（ｊ）内の初期設定手段７２１（図６参照）は、秘密鍵１０６ｘ（ｊ）∈Ｚ／ｑＺを一様無作為に選び、それを自置換復号装置Ｓ（ｊ）内に保持すると共に、公開鍵１０１Ｘ（ｊ）＝［ｘ（ｊ）］Ｇを生成し公開する。更に、各置換復号装置Ｓ（ｊ）内の初期設定手段７２１は、ｒ（ｊ）∈Ｚ／ｑＺを一様無作為に選び、
γ（ｊ）＝Ｈａｓｈ（Ｇ，［ｒ（ｊ）］Ｘ（ｊ））と
0004687465.tif 000030
とを計算し、γ（ｊ），α（ｊ）をｘ（ｊ）の知識の零知識証明文７２２として公開する。【０１０２】［参加者装置の暗号文生成］
ｉ＝１，．．．，ｎに関して、参加者装置１０３Ｕｉ（図５参照）は、長さがＡビットの平文１０２Ｍｉを決定する。各参加者装置Ｕｉ１０３は、最初のデータ６１４として、ｃｉ（ｍ＋１）＝Ｍｉと、任意データ６０３（それぞれがＬビットの任意の文字列Ｋｉ（ｍ＋１），Ｋ’ｉ（ｍ＋１），Ｓｉ（ｍ＋１），Ｓ’ｉ（ｍ＋１），Ｐｉ（ｍ＋１））とを含むデータを生成する。更に、鍵生成手段６０４が、ｊ＝１，．．．，ｍに関してＺ／ｑＺの要素ｒ［１］ｉ（ｊ），ｒ［２］ｉ（ｊ），ｒ［３］ｉ（ｊ）及びＣ上の点Ｅｉ（ｊ）を一様無作為に選ぶ。【０１０３】  その後、鍵暗号化手段６０５、データ暗号化手段６０６、ハッシュ値暗号化手段６０７、および出力手段６１５が、ｊ＝ｍ，（ｍ−１），．．．，１の順番で繰り返し以下の処理６１３を行う。【０１０４】  実施例１と同様に、ここで任意の文字列としては、乱数，セッション固有の数，日時等を選ぶ場合がある。乱数を用いれば、最終的な復号文の集合から自分の平文の存在を参加者装置が確認できる効果があり、セッション固有の数や日時を入れれば、他のセッションに使われた暗号文を再利用していないことが分かる効果がある。【０１０５】・鍵暗号化手段６０５における共通鍵の暗号化処理
共通鍵ｅｉ（ｊ）の暗号化のため、
0004687465.tif 000031
なるＥｉ（ｊ）を求め、
0004687465.tif 000032
を計算し、計算結果Ｋｉ（ｊ），Ｋ’ｉ（ｊ）を出力手段６１５に入力する。【０１０６】・鍵暗号化手段６０５における共通鍵の知識の証明文の生成処理
0004687465.tif 000033
と、
0004687465.tif 000034
と、
0004687465.tif 000035
とを計算し、Ｐｉ（１），Ｐｉ（０）を共通鍵の知識の証明文６１２として取りまとめ装置１０４に送付する。【０１０７】・データ暗号化手段６０６におけるデータの暗号化処理
0004687465.tif 000036
と、
0004687465.tif 000037
とを計算し、ｃｉ（ｊ））を出力手段６１５に入力する。【０１０８】・ハッシュ値暗号化手段６０７におけるハッシュ値の暗号化処理
0004687465.tif 000038
を計算し、Ｓｉ（ｊ），Ｓ’ｉ（ｊ）を出力手段６１５に入力する。【０１０９】・出力手段６１５における処理
鍵暗号化手段６０５からの入力Ｋｉ（ｊ），Ｋ’ｉ（ｊ）と、データ暗号化手段６０６からの入力ｃｉ（ｊ）と、ハッシュ値暗号化手段６０７からの入力Ｓｉ（ｊ）Ｓ’ｉ（ｊ）とからデータ６１４’（Ｋｉ（ｊ），Ｋ’ｉ（ｊ），ｃｉ（ｊ），Ｓｉ（ｊ），Ｓ’ｉ（ｊ））を生成し、ｊ＝１でなければ、データ６１４’をデータ６１４としてフィードバックし、ｊ＝１ならば、（Ｋｉ（１），Ｋ’ｉ（１），ｃｉ（１），Ｓｉ（１），Ｓ’ｉ（１））を暗号文２１１として出力する。【０１１０】  つまり、参加者装置１０３Ｕｉは、暗号文６１１（Ｋｉ（１），Ｋ’ｉ（１），ｃｉ（１），Ｓｉ（１），Ｓ’ｉ（１））と証明文Ｐｉ（１），Ｐｉ（０）とを取りまとめ装置１０４へ送付する。【０１１１】［取りまとめ装置による暗号文の検証］
取りまとめ装置１０４は、参加者装置から集めたデータをまとめて一番目の置換復号装置に送る。以下において、Ｋｉ（ｊ），Ｋ’ｉ（ｊ），ｃｉ（ｊ），Ｓｉ（ｊ），Ｓ’ｉ（ｊ），Ｐｉ（ｊ）は、ｊ＝１の場合を除いて前記のそれとは一般に異なる。【０１１２】［置換復号装置による暗号文の順序入れ替えと復号］
ｊ＝１，．．．，ｍに関して順番に、置換復号装置１１２Ｓ（ｊ）は以下の計算及び検証を行う。【０１１３】  暗号化された共通鍵暗号方式の共通鍵７０２（図６中、共通鍵暗号文と略記）Ｋｉ（ｊ），Ｋ’ｉ（ｊ）と、
暗号化されたデータ７０３（図６中、データ暗号文と略記）
ｃｉ（ｊ）と、
暗号化されたハッシュ値７０４（図６中、ハッシュ値暗号文と略記）
Ｓｉ（ｊ），Ｓ’ｉ（ｊ）と、
共通鍵の知識の証明文７０１（図６中、鍵の知識証明文と略記）
Ｐｉ（ｊ）とからなる入力データ列１０５
及び
秘密鍵１０６
0004687465.tif 000039
が入力される。入力データ列１０５は、データ分割手段７２３によって上記各要素７０１〜７０４に分割される。【０１１４】  全てのｉ（ｉ＝１，．．．，ｎ）に関して、以下の処理を行う。
共通鍵の知識の検証手段７０７は、
0004687465.tif 000040
を確認する。等式が成り立たないｉに関しては、最終的な出力データ列には加えない（処理７０９）。【０１１５】  ここでは暗号文の数が減少するが、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番付ける。【０１１６】  共通鍵復号手段７１０において、Ｅｉ（ｊ）＝Ｋ’ｉ（ｊ）−［１／ｘ（ｊ）］Ｋｉ（ｊ）なる演算を行う。【０１１７】  データ復号手段７１３において、
0004687465.tif 000041
なる演算を行う。得られたデータは、
0004687465.tif 000042
である。【０１１８】  置換手段７１１は、一様無作為に［１，．．．，ｎ］から［１，．．．，ｎ］への置換π［ｊ］（）を選び、以下を計算する。
0004687465.tif 000043
0004687465.tif 000044
【０１１９】  ハッシュ値復号手段７１２及び置換手段７１１は、
0004687465.tif 000045
なる演算を行う。【０１２０】  次に、ハッシュ値復号正当性証明手段７１５により上記Ｈｉ（ｊ）か正しく生成されたことの証明（ハッシュ値復号正当性証明文）を生成する。この証明には例えば、前出の文献の方法を使用する。【０１２１】  次に、全てのｉ（ｉ＝１，．．．，ｎ）に関して、ハッシュ値検証手段７１７において、
0004687465.tif 000046
が成り立つことを確認する。【０１２２】  この式が成り立たないｉが存在すれば、ハッシュ値不受理正当性証明手段７１８により、そのｉに関してπ［ｊ］（ｉ），Ｅｉ（ｊ）を明らかにして、Ｅｉ（ｊ）を正しく生成したことの零知識証明（ハッシュ値不受理正当性証明文）を生成する。【０１２３】  ここでも暗号文の数が減少するが（処理７１９）、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番付ける。【０１２４】  重複データ削除手段７２０は、ｉ＝１，．．．，ｎに関して（Ｋｉ（ｊ＋１），Ｋ’ｉ（ｊ＋１），ｃｉ（ｊ＋１），Ｓｉ（ｊ＋１），Ｓ’ｉ（ｊ＋１），Ｐｉ（ｊ＋１）））の組の内同じものがないことを確認する。同じものがあった場合は一つの組を残して他は消去する。ここでも暗号文の数が減少するが、減った後のこの数もｎで表し、それぞれの暗号文をｉ＝１からｎまでの番号で順番づける。【０１２５】  最後に出力データ列１０７
0004687465.tif 000047
を次の置換復号装置Ｓ（ｊ＋１）に送る。【０１２６】  ハッシュ値復号正当性証明文とハッシュ値不受理正当性証明文とを正当性証明文１０８とし、検証装置１０９に送る。【０１２７】  全ての置換復号装置Ｓ（ｊ）（ｊ＝１，．．．，ｍ）に関して処理が終わると順番が入れ替えられた平文１１１［Ｍｉ］ｉ＝１，．．．，ｎが得られる。【０１２８】［検証装置の処理］
検証装置１０９には、ハッシュ値復号正当性証明文８０１（図７中、ハッシュ値証明文と略記）及びハッシュ値不受理正当性証明文８００（図７中、不受理証明文と略記）からなる正当性証明文１０８と、入力データ列１０５と、出力データ列１０７とが入力される。【０１２９】  全てのｊ＝１，．．．，ｍに関して順番に以下の計算及び検証を行う。全てのｉ（ｉ＝１，．．．，ｎ）に関して、共通鍵の知識の検証手段８０２により、
0004687465.tif 000048
を確認する。等式が成り立たないｉのみに関しては以降の処理を行わない。【０１３０】  ハッシュ値復号正当性検証手段８０６により、［Ｈｉ（ｊ）］ｉ＝１，．．．，ｎが正しく生成されていることを検証する（証明に対応した方法で行う、例えば前出の文献の方法を使う）。【０１３１】  ハッシュ値一致検証処理を行う比較手段８０８において、全てのｉ（ｉ＝１，．．．，ｎ）に関して、
0004687465.tif 000049
が成り立つことを確認する。【０１３２】  もし成り立たないｉが存在すれば、ハッシュ値不受理正当性検証手段８０９において、そのｉに関してπ［ｊ］（ｉ），Ｅｉ（ｊ）を明らかにされていること、式Ｅｉ（ｊ）が正しく生成されていることを検証し、Ｃπ［ｊ］（ｉ）（ｊ）が正しく復号されていることを確認する。【０１３３】  正当性判定処理を行う検証手段８０５において、共通鍵の知識の検証処理と秘密の乱数の知識の検証処理の両方において受理されたもの全てに関して、ハッシュ値復号正当性検証処理において受理され、かつハッシュ値一致検証処理で受理あるいはハッシュ値一致検証処理で不受理かつハッシュ値不受理正当性検証処理で受理であり、かつ出力データ列には共通鍵の知識の検証処理と秘密の乱数の知識の検証処理とハッシュ値一致検証処理とで受理された要素に対応し、［Ｋｉ（ｊ＋１），Ｋ’ｉ（ｊ＋１），ｃｉ（ｊ＋１），Ｓｉ（ｊ＋１），Ｓ’ｉ（ｊ＋１），Ｐｉ（ｊ＋１）］の集合に重複があればその重複を除いて、それらが全て含まれているならば受理を、そうでなければ不受理を出力する。【０１３４】〔発明が有効である理由〕
置換復号装置におけるデータの復号及び置換ｄｅｃ［ｅｉ（ｊ）］（ｃπ［ｊ］（ｉ）（ｊ））が正当であることを証明するために、ハッシュ値と、ｄｅｃ［ｅｉ（ｊ）］（ｃπ［ｊ］（ｉ）（ｊ））、参加者装置が生成したこれの公開鍵による暗号文の復号結果が等しいことを証明する。この証明処理が、ハッシュ値復号証明処理である。この証明処理が公開検証可能な形で行われることが、本発明が公開検証可能であることの主な理由である。【０１３５】  但し、前述の証明の効果が発揮されるのは、参加者装置が正しくハッシュ値の暗号文を生成した場合のみである。これがなされなかった場合においては、置換復号装置は自身の操作の正当性を証明する必要がある。【０１３６】  まず、参加者装置が正当な処理でハッシュ値暗号文を生成したかを、ハッシュ値検証処理により確認する。正当な処理が行われていなかった場合は、ハッシュ値不受理正当性証明処理により、参加者装置の不正を証明し、これで置換復号装置の処理の正当性を証明する。【０１３７】  ところが、参加者装置の処理が正当でないことの理由が、他の参加者装置の不正による場合がある。ある参加者装置のデータをその他の参加者装置がコピーして、その暗号文を元に適当なデータを生成するのである。この場合、置換復号装置は参加者装置が不正であるとして、参加者装置の暗号文を復号し、かつその復号の正当性を証明することになるのだが、この証明が参加者装置の暗号文の攻撃となる場合がある。【０１３８】  そもそも参加者装置が自らの暗号文を不正に処理した場合は、自らが招いた結果であるので仕方がないが、他人にコピーされた場合はこの攻撃を防ぐ必要がある。この防御策が、共通鍵の知識の証明処理である。これは、他人の暗号文から不正な暗号文を作成した場合、置換復号処理により最初に処理を拒絶される効果を持つ。【０１３９】  他人の暗号文をコピーして不正な処理を行った場合は、上述のように置換復号装置によって処理を拒絶されるが、単純にコピーしてそれをそのまま用いただけでは上述の方法では拒絶されない。このようなことを許すと、コピーした暗号文は複数復号されるといった現象が起こる。これが起これば、最終的に復号された平文から、複数あるものを見つけることにより、コピーした暗号文の内容を知ることができる。このようなプライバシーに対する攻撃を防ぐ処理が、実施例１では連結データに関する証明処理であり、実施例２では重複データを削除する処理である。【０１４０】  連結データは、自分で生成したものでなければ最後に証明を作ることができないので、単純なコピーを防止する。重複データの削除は、コピーされたものをそのまま削る処理にあたる。【０１４１】  参加者装置が、平文と併せて乱数，セッション固有の数，日時等の文字列を入力する場合があるが、これらの値は最終的に復号されることから、この復号された文字列を使って様々なことを確認できる。たとえば、乱数を用いれば、最終的な復号文の集合から自分の平文の存在を参加者装置が確認できる効果があり、セッション固有の数や日時を入れれば、他のセッションに使われた暗号文を再利用していないことが分かる効果がある。
【図１】
0004687465.tif 000050
【図２】
0004687465.tif 000051
【図３】
0004687465.tif 000052
【図４】
0004687465.tif 000053
【図５】
0004687465.tif 000054
【図６】
0004687465.tif 000055
【図７】
0004687465.tif 000056
【図８】
0004687465.tif 000057
【図９】
0004687465.tif 000058