JP3540718B2 - Verifiable anonymous communication path system, method for implementing the same, and recording medium recording the method - Google Patents

Description

を計算する。
Ｓｔｅｐ３−２： べき乗演算器１２Ａの出力Ｔ_１，Ｔ_２及び、入力Ｉ_１＝（Ｍ_１， Ｇ_１），Ｉ_２＝（Ｍ_２， Ｇ_２）を剰余乗算器１２Ｂへ入力し、
【００２１】
【数２】

を計算する。このべき乗演算と剰余乗算とにより秘密情報ｔ_１，ｔ_２で入力メッセージＩ_１＝（Ｍ_１，Ｇ_１），Ｉ_２＝（Ｍ_２，Ｇ_２）がランダム化される。
Ｓｔｅｐ３−３： 剰余乗算器１２Ｂの出力Ｒ_１，Ｒ_２及び乱数ｂを順序入換器１２Ｃへ入力する。順序入換器１２Ｃは、ｂ＝１ のとき、Ｏ_１：＝Ｒ_１及びＯ_２：＝Ｒ_２を、ｂ＝２ のとき、出力Ｏ_１：＝Ｒ_２及びＯ_２：＝Ｒ_１を出力する。この出力を、Ｏ_１＝（Ｎ_１，Ｈ_１），Ｏ_２＝（Ｎ_２，Ｈ_２）とおく。このようにランダム化された入力メッセージはその順序がｂによりランダム化され、即ち、ランダム置換される。
【００２２】
Ｓｔｅｐ４：図４中の乱数生成器１３を駆動し、乱数ｗ_１， ｗ_２， ｅ_ｂ’， ｚ_１ｂ’， ｚ_２ｂ’∈Ｚｑを生成し、ｂ，ｔ_１，ｔ_２とともに置換証明部１４へ入力する。ここで、ｂ’はｂ＝１ のときｂ’＝２とし、ｂ＝２ のときｂ’＝１のように値を取るものとする。また、ｐ， ｑ， ｇ， ｙをメモリ１１から置換証明部１４へ入力する。
Ｓｔｅｐ５：置換証明部１４は以下のように動作する（図６参照）。
置換証明部１４には切換部１２の２つの入力Ｉ_１， Ｉ_２と２つの出力Ｏ_１， Ｏ_２とがそれぞれ分岐入力されている。
Ｓｔｅｐ５−１：べき乗乗算器１４Ａを駆動し、
【００２３】
【数３】

を計算する。
【００２４】
Ｓｔｅｐ５−２：ハッシュ演算器１４ＢへＩ_１，Ｉ_２，Ｏ_１，Ｏ_２，Ｓ_１１，Ｓ_１２，Ｓ_２１，Ｓ_２２を入力し、その出力をｃとする。
Ｓｔｅｐ５−３：ｃ及びｑ，ｅ_ｂ’ を剰余減算器１４Ｃへ入力し、出力
ｅ_ｂ：＝ｃ−ｅ_ｂ’ｍｏｄｑ
を得る。
Ｓｔｅｐ５−４：ｅ_ｂ及びｗ_１，ｗ_２，ｑ，ｂ，ｔ_１，ｔ_２を剰余乗減算器１４Ｄへ入力し、
ｚ_１ｂ：＝ｗ_１−ｅ_ｂ・ｔ_１ｍｏｄｑ
ｚ_２ｂ：＝ｗ_２−ｅ_ｂ・ｔ_２ｍｏｄｑ
を計算する。
【００２５】
Ｓｔｅｐ５−５：置換が正当であることをゼロ知識証明を使って証明するため
Ｐｒｏｏｆ_１：＝（ｅ_１，ｅ_２，ｚ_１１，ｚ_１２，ｚ_２１，ｚ_２２）
を出力する。
置換網１０の終端で得られる出力をＲ_１，Ｒ_２，Ｒ_３，Ｒ_４とする。このとき、各Ｒ_ｉをＲ_ｉ＝（Ｍ’_ｉ，Ｇ’_ｉ）とおくと、以下の関係が成り立つ。
Ｍ’_ｉ＝ｍＦ（ｉ）ｙ^ｔ’
Ｇ’_ｉ＝ｇ^ｔ’
ここで、Ｆ（＊）は｛１，２，３，４｝→｛１，２，３，４｝なる置換関数の一つである。即ち、Ｒ_ｉはメッセージｍＦ（ｉ）に対する通常のＥｌ Ｇａｍａｌ暗号文であり、復号は通常のＥｌ Ｇａｍａｌ復号手順で行うことができる。
【００２６】
復号装置２０は図７に示すように復号部２１と、復号証明部２２と、メモリ２３と、これらの動作を制御する制御部２４とから構成されている。復号部２１は図８に示すようにべき乗演算器２１Ａと、剰余除算器２１Ｂとから構成されている。又、復号証明部２２は図９に示すように、乱数生成部２２Ａと、べき乗演算器２２Ｂと、ハッシュ演算器２２Ｃと、剰余乗減算器２２Ｄとから構成されている。
【００２７】
復号装置２０は、Ｒ_１〜Ｒ_４を順次以下のように処理する。
Ｓｔｅｐ１：制御部２４は入力Ｒ_ｉを順次受信し、復号部２１へ入力する。また、メモリ２３からｘ，ｐを復号部２１へ入力する。
Ｓｔｅｐ２：復号部２１では、図８に示すようにべき乗演算器２１ＡへＧ’_ｉ 及びｘ，ｐを入力し、
Ｋ_ｉ：＝Ｇ’_ｉ ^ｘｍｏｄｐ
を計算する。
【００２８】
Ｓｔｅｐ３：Ｍ’_ｉ，ｐ及び、べき乗演算器２１Ａの出力を剰余除算器２１Ｂへ入力し、
ｍ_ｉ：＝Ｍ’_ｉ／Ｋ_ｉｍｏｄｐ
を計算し、復号結果として出力する。
続いて、復号装置２０は正しく復号が行われたことを証明するＰｒｏｏｆＤを、復号証明部２２により以下のように作成する。
【００２９】
Ｓｔｅｐ１：復号証明部２２は図９に示すように乱数生成器２２Ａにより乱数ｗ∈Ｚｑを生成し、べき乗演算器２２Ｂへ入力する。
Ｓｔｅｐ２：べき乗演算器２２Ｂは、まずＴ_０：＝ｇ^ｗｍｏｄｐを計算し、次に、各Ｇ’_ｉ に対してＴ_ｉ：＝Ｇ’_ｉ ^ｗｍｏｄｐを計算し、Ｔ_０，…，Ｔ_Ｎをハッシュ演算器２２Ｃへ入力する。この例ではＮ＝４ である。
Ｓｔｅｐ３：ハッシュ演算器２２Ｃは、ｃ：＝Ｈａｓｈ（ｙ，Ｔ_０，Ｋ_１，Ｔ_１，…，Ｋ_Ｎ，Ｔ_Ｎ）を計算し、ｃを剰余乗減算器２２Ｄへ入力する。
【００３０】
Ｓｔｅｐ４：剰余乗減算器２２Ｄはｚ：＝ｗ−ｃｘ（ｍｏｄｑ）を計算し、ｃ， ｚ， Ｋ_１，…， Ｋ_Ｎと共に出力する。
このとき、ＰｒｏｏｆＤ：＝（ｃ，ｚ，Ｋ_１，…，Ｋ_Ｎ）とする。
検証端末２００ は、まず、置換が正しく実行されたことを確認するため、置換検証部３０を駆動する。置換検証部３０は図１０に示すようにべき乗乗算器３１と、ハッシュ演算器３２と、比較器３３と、加算器３４とから構成されている。置換検証部３０は、ｉ番目の切換装置ＳＷｉ によるＰｒｏｏｆ_ｉを以下のように検証する。
Ｓｔｅｐ１：べき乗乗算器３１を駆動し、
【００３１】
【数４】

を計算する。
【００３２】
Ｓｔｅｐ２：Ｓ_１１，Ｓ_１２，Ｓ_２１，Ｓ_２２及びＩ_１，Ｉ_２，Ｏ_１，Ｏ_２をハッシュ演算器３２へ入力し、その出力ｃを比較器３３へ入力する。
Ｓｔｅｐ３：ｅ_１，ｅ_２を加算器３４へ入力し、ｅ_１＋ｅ_２を計算する。その結果を、比較器３３へ入力する。
Ｓｔｅｐ４：比較器３３へｑを入力し、ｅ_１＋ｅ_２＝ｃ（ｍｏｄｑ）が成り立つか否かを検査する。成り立つ場合はＯＫを、成り立たない場合はＮＧを出力する。このようにして置換が正しく行われたことは、その置換を生じさせた乱数ｂを示すことなく零知識証明により検証される。
【００３３】
上記の検証を全ての切換装置の入出力に対して行い、ＮＧとなるような証明を出力した切換装置が存在した場合はその切換装置は故障しているものと見なす。上記検証が全てＯＫの場合、次に、復号が正しく行われたこと検証するため、復号検証部４０へＲ_１， …， Ｒ_４， ｍ_１， …， ｍ_４及びＰｒｏｏｆＤを入力する。図１１に復号検証部４０のブロック図を示す。復号検証部２２０ は、剰余除算器４１と、比較器４２と、べき乗乗算器４３と、ハッシュ演算器４４と、比較器４５とから構成され、以下のように復号化の検証を行う。
【００３４】
Ｓｔｅｐ１：剰余除算器４１へＭ’_ｉ とＫ_ｉを入力してＭ’_ｉ／Ｋ_ｉを計算し、その結果をｍ_ｉと共に比較器４２へ入力して比較する。両者が等しくない場合には、比較器４２はＮＧを出力し、検証結果をＮＧとする。全てのｉ＝１， …， Ｎに対して比較結果がＯＫならば、次のステップへ進む。
Ｓｔｅｐ２：べき乗乗算器４３を駆動し、ｇ^ｚｙ^ｃ及び、Ｇ’_１ ^ｚＫ_１ ^ｃ，…，Ｇ’_Ｎ ^ｚＫ_Ｎ ^ｃを計算し、ハッシュ演算器４４へ入力する。
【００３５】
Ｓｔｅｐ３：ハッシュ演算器４４を駆動し、
ｅ：＝Ｈａｓｈ（ｙ，ｇ^ｚｙ^ｃ，Ｋ_１，Ｇ’_１ ^ｚＫ_１ ^ｃ， …，Ｋ_Ｎ， Ｇ’_１ ^ｚＫ_１ ^ｃ）
を計算する。
Ｓｔｅｐ４：ｃ及び、ハッシュ演算器４４が出力したｅを比較器４５へ入力し、両者が等しければＯＫを、等しくなければＮＧを出力する。
復号が正しく行われた場合には、
ｇ^ｚｙ^ｃ＝ｇ^ｗ−ｃｘｙ^ｃ＝ｇ^ｗ＝Ｔ_０
及び、
Ｇ’_ｉ ^ｚＫ_ｉ ^ｃ＝Ｇ’_ｉ ^ｗ−ｃｘＫ_ｉ ^ｃ＝Ｇ’_ｉ ^ｗ＝Ｔ_ｉ
が成り立つので、ハッシュ演算器４４の出力はｃと等しくなる。
【００３６】
この実施例では、各切換装置で用いたランダムな要素、即ち、ｂ， ｔ_１， ｔ_２， ｗ_１，ｗ_２が全て秘密に保たれる場合には、Ｅ_ｉ→ｍ_ｊの対応はどのようなｉ， ｊについても秘匿される。この様に、この第１実施例においては、それぞれの切り換え装置におけるランダム置換の正当性をそれぞれの切り換え装置で証明するよう構成しているため、特に匿名通信路の全入力の数Ｎが増大すると前述したＲ．Ｃｒａｍｅｒ等の方法でランダム置換の正当性を証明する場合に比べ、必要なデータ処理量が著しく少なくてすむ。
第２実施例
この実施例ではいくつかの切換装置におけるランダム要素が漏洩した場合についても全体として各入出力の対応が秘匿されるような構成について説明する。
【００３７】
この実施例では、図１２に示すようにいくつかの切換装置の仕事を順次実行する「置換サーバ」を用い、Ｖ個の置換サーバＰＳ_１，．．．，ＰＳ_４によって置換網１０を構成する。また、復号を実行する復号サーバ２０Ｓを用いる。以下では、Ｖ＝４ 個の置換サーバを用い、入力が４メッセージである場合について説明する。各置換サーバＰＳ_１〜ＰＳ_４及び検証端末２００ は掲示板４００ に接続されているものとする。掲示板４００ は、認証された利用者からの書き込みＥ_１， Ｅ_２， ．．．，Ｅ_Ｎを受け付け、一旦書き込んだ情報は消すことができないという機能を有する。また、書き込まれた情報は誰もが読み出すことができるものとする。この実施例も、第１実施例と同様に置換網１０内の各置換サーバＰＳが有する各切換装置ＳＷ（図１３）は復号を行なわず、入力暗号のランダム化（暗号の変換）とランダム置換を行ない、最後に復号サーバが復号を行なう。
【００３８】
図１３に各置換サーバＰＳのブロック図を示す。置換サーバＰＳ中の切換装置ＳＷの構成は制御部１５とメモリ１１が切換装置の外側にあることを除いて図４の切換装置ＳＷと同様である。
図１４に復号サーバ２０Ｓのブロック図を示す。復号サーバ２０Ｓは置換検証部３０Ｓ、復号部２１Ｓ、復号証明部２２Ｓを有しており、これらはそれぞれ図１０、８、９に示した置換検証部３０、復号部２１、復号証明部２２と同様である。復号サーバは更にメモリ２３Ｓと制御部２４Ｓを有している。
【００３９】
このシステムは、４つの置換サーバＰＳ_１，．．．，ＰＳ_４によって、４入力の完全置換網を２つ構成した場合である。この場合のデータの流れを図１５に示す。図中には示してないが、置換サーバ間のデータの転送は全て図１２に示したように掲示板４００ を介して行われる。即ち、各置換サーバＰＳ_ｊ は、置換出力を掲示板４００ に書き込み、次段の置換サーバＰＳ_ｊ＋１ はそのデータを掲示板４００ から読み込んで置換処理を行う。置換サーバＰＳ_１は、第１実施例における切換装置ＳＷ１ とＳＷ２ の仕事を実行し、掲示板４００ を介して処理結果を置換サーバＰＳ_２へ送出する。以下同様に、置換サーバＰＳ_２は切換装置ＳＷ３，ＳＷ４，ＳＷ５、置換サーバＰＳ_３は切換装置ＳＷ６，ＳＷ７、置換サーバＰＳ_４は切換装置ＳＷ８，ＳＷ９，ＳＷ１０の仕事を実行する。図１３に示すように、実際に各置換サーバＰＳ内に設置される切換装置ＳＷの数は１つであり、適切な入力を制御部１５が与えることによって図１５のデータの流れを実現する。あるいは、実際に複数の切換装置ＳＷを１つの置換サーバに設置しても良い。
【００４０】
図１２、１５に示すように、縦続接続された置換サーバＰＳ_１〜ＰＳ_４は少なくとも２つの縦続接続された完全置換網を形成している。各置換サーバＰＳの出力は、掲示板４００ に接続された置換検証部３０Ｓを持つ復号サーバ２０Ｓによって第１実施例の場合と同様に置換Ｐｒｏｏｆ が検証され、不正な入出力関係が検出された場合はその置換サーバを故障しているものと見なす。その場合、故障とみなした置換サーバを排除して別の置換サーバで処理を代行するか、あるいは、故障した置換サーバが１つだけならば、その置換サーバによる処理を省略してしまっても良い。
【００４１】
復号サーバ２０Ｓは、全ての置換が正しいことを検証した後、復号部２１Ｓで置換網１０の出力（最終段置換サーバＰＳ_Ｖ の出力）を復号すると共に、復号証明部２２Ｓで、復号証明ＰｒｏｏｆＤを生成し、掲示板４００ に書き込む。検証端末２００ は各置換サーバにより掲示板４００ に書き込まれている各置換Ｐｒｏｏｆ_１〜Ｐｒｏｏｌ_４からを検証し、更に復号サーバにより書き込まれた復号結果（メッセージｍ_１，．．．，ｍ_Ｎ）と復号証明ＰｒｏｏｆＤを第１実施例と同様の手順で検証する。
【００４２】
上記の構成によれば、ある置換サーバが攻撃されるなどして、ランダム要素が漏洩してしまい、その置換サーバにおける置換が第三者に明らかになってしまった場合に於いても、残りの置換サーバにおけるランダム要素の秘匿性が保たれる限りは、全体の置換関係は秘密に保たれる。例えば、置換サーバＰＳ_１の実行した置換関係が明らかになっても、置換サーバＰＳ_３、置換サーバＰＳ_４で完全な置換網を構成しているので、入出力のどのような置換関係も実現し得る。同様に、どの１つの置換サーバの置換関係が漏洩しても、必ず他の２つの置換サーバによって完全な置換網が構成されており、それによって、秘匿性を保つことが可能である。
第３実施例
図１６に示す第３実施例では、第２実施例における復号サーバ２０Ｓ を複数の復号サーバ２０Ｓ_１，…，２０Ｓ_Ｌに分割して、複数の復号サーバ全体で単一の復号サーバを用いた場合と同一の機能を実現する。この実施例によれば、あるｔ＜Ｌなるｔに対して、少なくともｔ＋１ 個の復号サーバ２０Ｓ が正常に動作すれば正しい結果を得ることができるため、耐故障性が向上する。又、図１２の復号サーバ２０Ｓ が１つの場合には、復号サーバ２０Ｓ が復号を開始すればいつでも復号結果を得ることができるので、例えば投票の集計を予め決めた時間に公表する前にその投票結果の内容を不正に洩らしてしまうことが起こりえる。これに対し、図１６の実施例では、前復号サーバ２０Ｓ_１〜２０Ｓ_Ｌが処理を終了しないと復号結果が得られないので、これらのサーバのうち少なくともｔ＋１ 個の復号サーバが協力して不正を行なわない限りどの復号サーバからも復号結果が公表前に洩れてしまうことはない。
【００４３】
復号サーバを除くシステム構成は第２実施例と同様である。各復号サーバＤ_ｉには復号鍵ｘをｔ次の多項式で秘密分散した値ｘ_ｉが格納されているものとする。即ち、Ｆ（０）＝ｘ（ｍｏｄｑ）を満たす、ｔ＜Ｌなるあるｔ次のランダム多項式Ｆ（Ｘ）∈Ｚｑ［Ｘ］ があり、各ｘ_ｉはｘ_ｉ＝Ｆ（ｉ）ｍｏｄｑ を満たす値である。各復号サーバ２０Ｓ_ｊの構成は、図１４に示した復号サーバ２０Ｓにおいてｘの代わりにｘ_ｉをメモリ２３Ｓに格納すること及び、復号部２１Ｓの内部構成を除き、図１４と同様である。この実施例の復号サーバにおける復号部２１Ｓは図１７に示すように、べき乗乗算器２１ＳＡと有し、これは図８に示したべき乗乗算器２１Ａと同様の処理を行なう。
【００４４】
置換サーバＰＳ_１，．．．，ＰＳ_Ｖの構成、動作は図１２に示した第２実施例と同様である。各復号サーバ２０Ｓ_ｔは、全ての置換サーバＰＳ_１，．．．，ＰＳ_Ｖの入出力関係を第２実施例と同様に検証する。最終段の置換サーバＰＳ_Ｖ から正しい置換出力Ｒ_１〜Ｒ_Ｎが得られ、置換検証が完了した後、各復号サーバは復号を実行する。ｊ番目の復号サーバ２０ＳｊはＲ_１〜Ｒ_Ｎを順次以下のように処理する。
Ｓｔｅｐ１：制御部は入力Ｒ_ｉを順次受信し、復号部２１Ｓ（図１４参照）へ入力する。また、メモリ２３Ｓからｘ_ｉ，ｐを復号部２１Ｓへ入力する。
【００４５】
Ｓｔｅｐ２：復号部２１Ｓ（図１７参照）では、べき乗演算器２１ＳＡへＧ’_ｉ 及びｘ_ｊ， ｐを入力し、Ｋ_ｊ，ｉ：＝Ｇ’_ｉ ^ｘｊを計算する。
続いて、復号証明部２２Ｓ（図１４参照）は正しく復号が行われたことを証明するＰｒｏｏｆＤ_ｊ を、復号証明部を駆動して作成する。実際の動作は、第１実施例の復号証明動作においてｘをｘ_ｊに、ｙをｙ_ｊに入れ換えた場合と同様である。この証明部の出力を
ＰｒｏｏｆＤ_ｊ：＝（ｃ_ｊ， ｚ_ｊ， Ｋ_ｊ，１，…，Ｋ_ｊ，ｎ）
とする。
【００４６】
検証端末２００ の構成は図２と同様である。但し、復号検証部４０は図１８に示す構成となる。この復号検証部の動作は、第１実施例における復号検証部の動作のＳｔｅｐ２〜４と同様である。ｔ＋１ 以上の復号サーバに対する検証がＯＫとなるならば、検証端末はＯＫを出力する。
この実施例では、復号サーバ２０Ｓ_ｊの出力はＫ_ｉ，ｊであり、実際に各復号結果ｍ_ｉを得るには以下の手順を実行する。まず、Ａ⊆｛１，…，Ｌ｝を、｜Ａ｜＞ｔ＋１となるように定める。ただし、ｊ∈Ａなるｊに対して、復号サーバ２０Ｓ_ｊの出力は、復号検証に合格していなければならない。今、λ_ｊ ，Ａを次式
【００４７】
【数５】

で定義される補間係数とする。すると、メッセージｍ_ｉは次式
【００４８】
【数６】

で得ることができる。これは、ｘ＝Σλ_ｊ，ＡＡｘ_ｊｍｏｄｑ（Σはｊ∈Ａについて）が成り立つため、
【００４９】
【数７】

となり、第１実施例における復号動作と等価になる為である。
上記計算手順を各復号サーバが実行することも可能である。その場合には、第１実施例と同様の検証手順で復号検証を行えばよい。
第４実施例
前述の第２及び第３実施例においては各置換サーバＰＳは入力された複数の暗号文を撹乱し、かつその入力の順番をランダムに入れ換えて次の置換サーバへ送ることを順次行ない、最終段の置換サーバが出力した暗号文を復号サーバが復号して平文を得る。得られた平文は誰れにより投票されたものであるかは不明であるが、正しく投票されたものであることを検証できる。
【００５０】
この第２及び第３実施例では、不正な処理を行なった置換サーバが検出された場合、例えばＶ個の置換サーバのうちｔ個の出力が信頼できなかった場合、不正処理を回復する為には、ｔ回の不正回復処理を行うことが考えられる。匿名通信路の信頼度が下がれば下がる程（即ち、ｔが大きくなる程）、不正回復処理に要する時間が大となり、匿名通信路としての処理能力が下がる事になる。
以下に説明する第４実施例は、匿名通信路の信頼度が、ある程度低くなっても、検証可能匿名通信路としての機能を保ちつつ、効率的に不正回復を行い、必要とされる帯域（通信速度）を確保する。
【００５１】
第１、第２及び第３実施例では、各切換装置ＳＷ，あるいは置換サーバにおいては復号化処理を行なわず、復号化装置又は復号サーバにおいて一括して復号を行なう場合を示したが、この第４実施例では、各置換サーバにおいて部分復号化を行なう場合を示す。ただし、各置換サーバでは、それぞれの置換段で入力暗号文Ｉを変換し、部分復号化は置換の最終段においてまとめて行なうことにより、各置換段において部分復号化を行なうよりは処理速度を高めている。
【００５２】
この実施例では以下、各置換サーバで行われる部分復号処理をｆとし、任意の秘密鍵Ｘを持った置換サーバの任意の入力文Ｉに対応する出力文をｆ_Ｘ（Ｉ） とする。
各置換サーバで行われる部分復号処理ｆを次のような処理に限定する。
・交換可能
任意の秘密鍵Ａ，Ｂに対してｆ_Ａ（ｆ_Ｂ（Ｉ））＝ｆ_Ｂ（ｆ_Ａ（Ｉ）） なる関係が成り立つ。
・一括復号化可能
任意で既知の秘密鍵Ａ，Ｂに対してｆ_Ａ（ｆ_Ｂ（Ｉ））＝ｆ_{ｇ（Ａ，Ｂ）}（Ｉ）なる関数ｇ（Ａ， Ｂ）が存在し、ｆ_Ａ （ｆ_Ｂ（Ｉ））の計算に対してｆ_{ｇ（Ａ，Ｂ）}（Ｉ）の計算が高速に実行可能である。
【００５３】
このような前提においてこの実施例では、ある置換サーバの出力が信頼できない場合、その置換サーバより上流で最も近くにある、不正処理がないと判定された置換サーバの信頼できる情報のみを用いてランダム置換・撹乱・部分復号処理を行ない、不正処理に対する補償動作を行わずに次の処理を進める。
各置換サーバの秘密鍵は、予め他の全ての置換サーバに検証可能に秘密分散されており、信頼できない置換サーバが検出された場合、残りの各置換サーバはそれより上流の信頼できる置換サーバの情報を使ってランダム置換・撹乱・部分復号処理を行ない、全ての信頼できる置換サーバによる処理が完了した段階で、信頼できない置換サーバの分散秘密鍵の全てを信頼できる置換サーバが集めて共同で復元する。信頼できない置換サーバが部分復号処理することになっていた情報部分についての部分復号処理（補償動作）を、信頼できない置換サーバの復元秘密鍵の全てを用いて、一括して行う。この一括処理によって、複数の置換サーバの出力が信頼できない場合でもたった１回の補償動作を行うだけで不正回復を行う事が可能である。
【００５４】
この第４実施例においては、置換サーバが用いる交換可能でかつ一括化可能な部分復号処理の一例として以下の説明ではＥｌ Ｇａｍａｌ分散復号系を挙げる。一般化されたＥｌ Ｇａｍａｌ暗号系においても、上記性質が満たされれば適用可能である（例えば楕円Ｅｌ Ｇａｍａｌ暗号）。
この第４実施例ではいくつかの置換サーバにおけるランダム要素が漏洩した場合についても全体として各入出力の対応が秘匿されるような構成について説明する。
【００５５】
この実施例では、いくつかの証明付きランダム置換・撹乱・部分復号の仕事を順次実行する置換サーバを用い、Ｖ個の置換サーバによって匿名通信路を構成する。
図１９はこの第４実施例のシステム構成例であり、図１２及び１６の実施例と同様に置換サーバＰＳ_１〜ＰＳ_Ｖは掲示板４００ に接続されている。この実施例では各置換サーバに他の置換サーバの処理に対する検証機能と入力暗号文に対する部分復号機能を持たせているため、図１２及び１６の実施例のような検証サーバ及び復号サーバは設けられてない。各置換サーバは、第２及び第３実施例における各置換サーバ内の複数の切換装置ＳＷにより構成された置換部に対応する置換部Ｐ５０ に加えて、他の置換サーバの処理に不正がないかを判定する判定部Ｐ６０ と、ランダム置換・部分復号の証明を行なう検証部Ｐ７０ を有している。置換サーバＰＳ_１〜ＰＳ_５の置換部Ｐ５０_１〜Ｐ５０_５は掲示板４００ を介して図１９に示すように縦続接続される。各置換部Ｐ５０_１〜Ｐ５０_５は置換・撹乱部分復号を行う複数の切換装置ＳＷを有している。検証端末２００ は独立して設けるのではなく、それぞれの置換サーバに設けられている。
【００５６】
図２０は図１のシステムにおける置換サーバ間の掲示板４００ を介したデータの流れを、掲示板を省略して示すため、図１９における置換サーバＰＳ_１〜ＰＳ_５内の置換部Ｐ５０_１〜Ｐ５０_５のみを示している。これら５つの置換部Ｐ５０_１〜Ｐ５０_５はこの例では縦続接続された２つの置換部Ｐ５０_１とＰ５０_２で１つの８入力完全置換網を形成し、縦続接続された２つの置換部Ｐ５０_３とＰ５０_４で同様に１つの８入力完全置換網を形成し、置換部Ｐ５０５は単独で８入力完全置換網を形成している。従って、全体で縦続接続されたこれら３つの８入力完全置換網を形成している。
【００５７】
各８入力完全置換網を形成するには４×５格子上に配列された全ての２入力２出力の単位切換装置ＳＷが切換可能である必要はなく、破線ブロックで示す切換装置ＳＷでは入出力位置関係を固定しても、残りの切換装置の切換の組み合わせて全ての組の置換が実現できる。そこで、置換サーバでの処理量を削減するため、このような入出力関係を固定してもよい切換装置では入力データに対する置換処理は行なわない。これらの固定接続切換装置をＳＷＦで示してある。しかしながら、この発明の目的とする匿名通信路を構成する置換網を通して暗号文を復号する場合、入力データに対し選択された経路によって復号処理を受ける回数が異なると復号処理が複雑になり不都合である。
【００５８】
この発明ではこのような固定接続切換装置ＳＷＦにおいても、入力データに対し置換処理以外の処理（撹乱、部分復号、証明生成など）は実施する。以下の説明では置換・撹乱・部分復号・証明生成などの全ての処理を実施する切換装置ＳＷを証明付ＰＲ部分復号器と呼び、置換を行なわない切換装置ＳＷＦを証明付固定部分復号器と呼ぶ。また置換撹乱（ｐｅｒｍｕｔａｔｉｏｎ／ｒａｎｄｏｍｉｚａｔｉｏｎ）を単にＰＲで表す。
【００５９】
図１９の実施例では、入力が８メッセージであり、５つの置換サーバＰＳ_１〜ＰＳ_５を用い、５つのうち２つの置換サーバの処理に不正である場合でも正しい置換・撹乱・部分復号を実行出来るものである。各置換サーバＰＳ_１〜ＰＳ_５の構成要素の証明付きＰＲ部分復号器ＳＷは図２１または図２８に示すように構成され、証明付き固定部分復号器ＳＷＦは図２７に示すように構成される。これらについては後で詳述する。各置換サーバＰＳ_１〜ＰＳ_５はそれぞれ検証器Ｐ７０ を備える。各検証器Ｐ７０ はＰＲ証明検証器Ｐ７０Ａと、部分復号証明検証器Ｐ７０Ｂと、及びＰＲ部分復号証明検証器Ｐ７０Ｃをもって構成される。
【００６０】
掲示板４００ は、認証された利用者からの暗号文の書き込みを受け付け、一旦書き込んだ情報は消すことができないという機能を有する。書き込まれた情報は誰もが読み出すことができるものとする。
このシステムは、５つの置換サーバＰＳ_１〜ＰＳ_５によって、それぞれ８入力の縦続接続された３つの完全置換網１０Ａ〜１０Ｃからなる匿名通信路１００ を構成している。３つの完全置換網１０Ａ〜１０Ｃのうち２つの完全置換網のランダム要素が漏洩しても残った完全置換網によって入出力の対応関係を完全に秘匿することが出来る。
【００６１】
置換サーバＰＳ_１〜ＰＳ_５は予め決めた順番でデータの処理を行ない、各置換サーバは自段より前段の置換サーバの入出力データと証明情報を掲示板４００ から読み込む。その入力の際に自身が持つ検証器Ｐ７０ によってその前段の置換サーバの信頼性をその入出力データと証明情報に基づいて検証し、不正な入出力関係が検出された場合、つまり出力の信頼性がない場合はその置換サーバは故障しているものと見なす。その場合、不正のない置換サーバが見つかるまで順番を遡り、不正でないと判断された最も近い置換サーバの出力を使って処理を行う。
【００６２】
各置換サーバは他のどの置換サーバに対しても検証可能であり、不正な入出力関係が検出されない置換サーバ同士が協力して、不正な置換サーバが担当する復号処理に対する補償動作を行う。そのために、予め全ての置換サーバのもつ秘密鍵を全ての置換サーバが秘密分散によって共有しておく。
先にも述べたように、各置換サーバは複数の証明付きＰＲ部分復号器の仕事を順次実行するものであり、置換サーバ内の各証明付ＰＲ部分復号器ＳＷは、例えば図２１に示すように、証明付き置換撹乱器１２０ と証明付き部分復号器１４０ とよりなり、証明付き置換撹乱器１２０ は例えば置換撹乱器１２１ と置換撹乱証明生成器１２２ とよりなり、証明付き部分復号器１４０ は例えば２つの証明付部分復号器１４１、１４２ よりなる。
【００６３】
図２１は、２入力のＥｌ Ｇａｍａｌ暗号文を置換撹乱処理し、秘密鍵の部分情報を用いて部分復号し、置換撹乱復号結果及びその正当性の証明を出力する証明付きＰＲ部分復号器ＳＷの構成の一例を表している。この証明付きＰＲ部分復号器ＳＷは図２０中の一括不正回復付き検証可能匿名通信路等に用いられる。
この証明付きＰＲ部分復号器ＳＷでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００６４】
Ｓｔｅｐ１：証明付き置換撹乱器１２０ は乱数情報内の各種情報を用いて入力の（Ｍ_０，Ｇ_０），（Ｍ_１， Ｇ_１）を置換撹乱処理した結果の（Ｍ_０ ^＋， Ｇ_０ ^＋），（Ｍ_１ ^＋， Ｇ_１ ^＋）及びその正当性の証明である証明情報０を出力する。
Ｓｔｅｐ２：証明付き置換撹乱部分復号器ＳＷは（Ｍ_０ ^＋， Ｇ_０ ^＋），（Ｍ_１ ^＋， Ｇ_１ ^＋）を証明情報の一部として出力する。
Ｓｔｅｐ３：証明付き固定部分復号器１４０ は乱数情報内の各種情報を用いて入力の（Ｍ_０ ^＋， Ｇ_０ ^＋），（Ｍ_１ ^＋， Ｇ_１ ^＋）を部分復号した（Ｍ’_０， Ｇ’_０ ），（Ｍ’_１， Ｇ’_１）及びその正当性の証明である証明情報１を出力する。
【００６５】
なお、この証明付き置換撹乱部分復号器ＳＷにおける置換と、撹乱と、部分復号との処理順は任意に選らべる。ただしその処理順に応じて証明情報の内容が異なるものとなる。
置換撹乱器１２１ は例えば図２２に示すように置換器１２１Ａと撹乱器１２１Ｂ，１２１Ｃとよりなる。撹乱器１２１Ｂ、１２１Ｃは同じ構造であり、図２３に示すように２つの乗算器１２１Ｂ１と１２１Ｂ２を有している。以下これらの各部の機能構成を順次説明する。
撹乱器１２１Ｂ（１２１Ｃ）
図２３は図２２に示す撹乱置換器１２１ において入出力の対応を隠蔽する為に、入力のＥｌ Ｇａｍａｌ暗号文を撹乱する撹乱器１２１Ｂ（１２１Ｃ）の構成の一例を表している。入力のＥｌ Ｇａｍａｌ暗号文を（Ｍ， Ｇ）とすると、平文ｍ及び公開鍵（Ｙ， ｇ） 及び秘密鍵Ｘ及び乱数ｗに関して次式
Ｙ＝ ｇ^Ｘ ，Ｇ＝ ｇ^ｗ ，Ｍ＝ｍＹ^ｗ
が成り立っている。入力暗号文（Ｍ， Ｇ） を撹乱するとは、撹乱処理を行う者以外には秘密の乱数ｒによりＭ及びＧの入力前に計算された秘密のパラメータｇ^−ｒ及びＹ^−ｒを用いて乗算器１２Ｂ１， １２１Ｂ２で
Ｍ’ ← Ｍ×Ｙ^−ｒ，
Ｇ’ ← Ｇ×ｇ^−ｒ
をそれぞれ計算し（Ｍ’， Ｇ’） を出力することである。出力の（Ｍ’， Ｇ’） は
Ｍ’ ＝ ｍＹ^ｗ−ｒ ，Ｇ’ ＝ ｇ^ｗ−ｒ
を満たすので、平文ｍ及び公開鍵（Ｙ， ｇ） 及び秘密鍵Ｘ及び乱数ｗ−ｒ に関するＥｌ Ｇａｍａｌ暗号文である。
【００６６】
この撹乱器１２１Ｂでは、以上の演算が実行されるが、同時実行可能な場合は、並列に実行しても良い。また実行順序が交換可能な場合は実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
置換撹乱器１２１
図２２は２入力のＥｌ Ｇａｍａｌ暗号文（Ｍ_０ ， Ｇ_０ ）及び（Ｍ_１ ，Ｇ_１ ）を撹乱置換する置換撹乱器１２１ の構成の一例を表している。Ｅｌ Ｇａｍａｌ暗号文（Ｍ， Ｇ） を乱数ｒで撹乱して出来たＥｌ Ｇａｍａｌ暗号文をＤ（Ｍ， Ｇ， ｒ）と記述する事にする。置換撹乱処理を行う者以外には秘密の置換パラメータＢ∈｛０， １｝に従って、
Ｂ＝０ のとき
（Ｍ’_０ ， Ｇ’_０ ） ← Ｄ（Ｍ_０ ， Ｇ_０ ， ｒ_０ ）
（Ｍ’_１ ， Ｇ’_１ ） ← Ｄ（Ｍ_１ ， Ｇ_１ ， ｒ_１ ）
Ｂ＝１ のとき
（Ｍ’_０ ， Ｇ’_０ ） ← Ｄ（Ｍ_１ ， Ｇ_１ ， ｒ_０ ）
（Ｍ’_１ ， Ｇ’_１ ） ← Ｄ（Ｍ_０ ， Ｇ_０ ， ｒ_１ ）
なる出力メッセージ（Ｍ’_０ ， Ｇ’_０ ）及び（Ｍ’_１ ， Ｇ’_１ ）を出力する。
【００６７】
置換撹乱器１２１ は置換器１２１Ａと、撹乱器１２１Ｂ， １２１Ｃとからなる。撹乱器１２１Ｂ及び撹乱器１２１Ｃは図２３に示したように２つの乗算器１２１Ｂ， １２１Ｂ２から構成される。この置換撹乱器１２１ では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００６８】
Ｓｔｅｐ１：置換器１２１Ａはもし置換パラメータＢがＢ＝０ ならば、
（Ｌ_０ ， Ｌ_１ ） ← （Ｍ_０ ， Ｇ_０ ）
（Ｌ_２ ， Ｌ_３ ） ← （Ｍ_１ ， Ｇ_１ ）
とし、Ｂ＝１ ならば、
（Ｌ_０ ， Ｌ_１ ） ← （Ｍ_１ ， Ｇ_１ ）
（Ｌ_２ ， Ｌ_３ ） ← （Ｍ_０ ， Ｇ_０ ）
とする。
【００６９】
Ｓｔｅｐ２：撹乱器１２１Ｂは撹乱パラメータ（Ｙ^−ｒ０ ， ｇ^−ｒ０）を用いて、入力の（Ｌ_０ ， Ｌ_１ ）を撹乱して（Ｍ’_０ ， Ｇ’_０ ）を出力する。
Ｓｔｅｐ３：撹乱器１２１Ｃは撹乱パラメータ（Ｙ^−ｒ１ ， ｇ^−ｒ１ ）を用いて、入力の（Ｌ_２ ， Ｌ_３ ）を撹乱して（Ｍ’_１ ， Ｇ’_１ ）を出力する。
つまり、Ｇ_ｉ とＧ’_ｊ の対応Ｂ＝ｉ（＋）ｊ， ただしｉ， ｊ∈｛０， １｝、を隠蔽するために出力を撹乱処理している。従ってｒ_０ ，ｒ_１ の値だけでなくｇ^−ｒ０，Ｙ^−ｒ０ ，ｇ^−ｒ１ ，Ｙ^−ｒ１ の値も秘密にする必要がある。なお図２２では置換した後に撹乱を行ったが撹乱した後に置換を行ってもよい。
置換撹乱証明生成器１２２
図２１における置換撹乱証明生成器１２２ は置換撹乱器１２１ が正しく動作している事を秘密情報（Ｂ∈｛０， １｝及び撹乱用パラメータの値）を明かさずに証明する。この証明をするためにはｂ＝ｉ（＋）ｊであるとして、
ｂ＝０なる全てのｉ， ｊ∈｛０， １｝に関して
ｌｏｇ_Ｙ （Ｍ_ｉ ／Ｍ’_ｊ）＝ ｌｏｇ_ｇ（Ｇ_ｉ ／Ｇ’_ｊ ）
またはｂ＝１なる全てのｉ， ｊ∈｛０， １｝に関して
ｌｏｇ_Ｙ （Ｍ_ｉ ／Ｍ’_ｊ ）＝ ｌｏｇ_ｇ （Ｇ_ｉ ／Ｇ’_ｊ ） ・・・（命題１）
を示さなくてはならない。そのためにこの置換撹乱証明生成器３Ａから以下に述べる証明情報Ｔ_ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ，ｅ_ｂ を演算して出力する。
【００７０】
入力のＢは置換撹乱器１２１ 中の置換器１２１Ａに入力された置換パラメータである。入力のｒ_ｊ ， （ｊ∈｛０， １｝）は置換撹乱器１２１ 中の撹乱器１２１Ｂ，１２１Ｃに入力された撹乱用の乱数である。入力のｅ， Ｒ_ｉｊ（ｉ， ｊ∈｛０， １｝）は証明用の乱数である。入力のＹ^Ｒｉｊ，ｇ^Ｒｉｊ （ｉ， ｊ∈｛０， １｝）は入力のＭ_ｉ ，Ｇ_ｉ ，Ｍ’_ｊ ，Ｇ’_ｊ （ｉ， ｊ∈｛０，１｝）が入力されるより前に計算された証明用のパラメータである。これら情報｛Ｂ， ｒ_ｊ， ｅ， Ｒ_ｉｊ， Ｙ^Ｒｉｊ， ｇ^Ｒｉｊ｝を乱数情報ＲＤＭと呼ぶことにする。
【００７１】
出力のｅ_ｂ ，Ｔ_ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ，（（ｂ， ｉ， ｊ∈｛０， １｝）はｂ＝ｉ（＋）ｊとして（Ｍ_ｉ ，Ｇ_ｉ ）と（Ｍ’_ｊ ，Ｇ’_ｊ ）の対応を証明するか、または対応を装って証明する為の情報である。
この置換撹乱証明器１２２ では、図のように演算が実行される。つまりｉ， ｊ∈｛
０，１｝に関して
ｉ（＋）ｊ＝Ｂならば
Ｔ_ｉｊ ← Ｙ^Ｒｉｊ ， Ｗ_ｉｊ ← ｇ^Ｒｉｊ
ｉ（＋）ｊ＝Ｂ’（Ｂ’はＢの反転を表す）ならば
Ｔ_ｉｊ ← （Ｍ_ｉ ／Ｍ’_ｊ ）^ｅＹ^Ｒｉｊ ，Ｗ_ｉｊ ← （Ｇ_ｉ ／Ｇ’_ｊ ）^ｅｇ^Ｒｉｊ
Ｂ＝０ならば
ｅ_０ ← −ｅ＋ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
ｅ_１ ← ｅ
Ｂ＝１ならば
ｅ_１ ← −ｅ＋ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
ｅ_０ ← ｅ
任意のｉ， ｊ∈｛０， １｝に関して、
ｉ（＋）ｊ＝Ｂならば ｚ_ｉｊ ← Ｒ_ｉｊ−ｅ_Ｂｒ_ｊ
ｉ（＋）ｊ＝Ｂ’ならば ｚ_ｉｊ ← Ｒ_ｉｊ
この演算により証明者（置換撹乱証明生成器１２１ ）は証明情報ＶＲＦ＝｛ｅ_ｂ ， Ｔ _ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ｝を出力する。
【００７２】
なおこの演算において、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行
しても良い。
ＰＲ証明検証器Ｐ７０Ａ
図１９の各置換サーバに設けられた検証器Ｐ７０ 内のＰＲ証明検証器Ｐ７０Ａ は 図２１に示した置換撹乱器１２１ が正しく動作している事を検証するため、ＰＲ 証明生成器１２２ の出力、つまり証明情報ＶＲＦ＝｛ｅ_ｂ ，Ｔ_ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ｝を検 証する。
【００７３】
入力のｅ_ｂ ，Ｔ_ｉｊ，Ｗ_ｉｊ，Ｚ_ｉｊ，（ｂ， ｉ， ｊ∈｛０， １｝）は置換撹乱証明生成 器１２２ の出力であり、ｂ＝ｉ（＋）ｊとして（Ｍ_ｉ，Ｇ_ｉ ）と（Ｍ’_ｊ，Ｇ’_ｊ ）の対応 を証明するか、または対応を装って証明する為の情報である。
この検証器Ｐ７０ＡにはＴ_ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ，ｅ_ｂ の他にＭ_０ ，Ｇ_０ ，Ｍ_１ ，Ｇ_１ ，Ｍ’_０ ，Ｇ’_０ ，Ｍ’_１ ，Ｇ’_１ が入力されて、次式
ｅ_０＋ｅ_１ ＝ ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
が成立するかを確かめ、これが成立しなければ偽を出力して終了する。関数ｈ
は一方向性関数を表わす。
【００７４】
その後、全てのｉ， ｊ∈｛０， １｝に関してｂ＝ｉ（＋）ｊであるとして、
Ｔ_ｉｊ＝ （Ｍ_ｉ ／Ｍ’_ｊ ）^ｅｂＹ^ｚｉｊ かつ
Ｗ_ｉｊ＝ （Ｇ_ｉ ／Ｇ’_ｊ ）^ｅｂｇ^ｚｉｊ
が成立するかを確かめ、これが成立しなければ偽を出力して終了する。前記両
確認が共に成立すれば真を出力する。
不正な証明者が何らかの手段で事前に用意したｅ_ｂ ，ｚ_ｉｊを使って、
Ｔ_ｉｊ ← （Ｍ_ｉ ／Ｍ’_ｊ ）^ｅｂＹ^ｚｉｊ ，
Ｗ_ｉｊ ← （Ｇ_ｉ ／Ｇ’_ｊ ）^ｅｂｇ^ｚｉｊ
を計算し出力しようとしてもｈ（ｘ_０， ｘ_１， …）の非予測性により、ｅ_０， ｅ _１ のどちらか一方は事前に計算することが困難なので命題１の証明となる。
【００７５】
出力は置換撹乱器が正しく動作したかどうかの推定であり、真理値である。
この置換撹乱証明検証器Ｐ７０Ａでは、上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数
の演算は、装置を一元化して、順次演算を実行しても良い。
【００７６】
証明付き置換撹乱器１２０
証明付置換撹乱器１２０ は２入力のＥｌ Ｇａｍａｌ暗号文（Ｍ_０， Ｇ_０），（Ｍ_１， Ｇ_１ ）を置換撹乱処理した（Ｍ’_０， Ｇ’_０），（Ｍ’_１， Ｇ’_１）及び、正しい処理が行 われた事の証明を秘密情報を明かさずに出力する（零知識証明）。この証明付 き置換撹乱器１２０ は置換撹乱器１２１ と置換撹乱証明生成器１２２ とから構成され る。
この証明付き置換撹乱器１２０ では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数
の演算は、装置を一元化して、順次演算を実行しても良い。
【００７７】
Ｓｔｅｐ１：置換撹乱器１２１ は入力の（Ｍ_０， Ｇ_０ ），（Ｍ_１， Ｇ_１）を入力のＢと 撹乱パラメータｇ^−ｒ０， Ｙ^−ｒ０， ｇ^−ｒ１， Ｙ^−ｒ１で置換撹乱処理し、（Ｍ’_０， Ｇ’_０），（Ｍ’_１， Ｇ’_１）を出力する。
Ｓｔｅｐ２：ＰＲ証明生成器１２２ は入力（Ｍ_０， Ｇ_０）， （Ｍ_１， Ｇ_１）及び出力（Ｍ ’_０， Ｇ’_０）， （Ｍ’_１， Ｇ’_１）及び乱数情報ＲＤＭ＝｛Ｂ， ｒ_ｊ， ｅ， Ｒ_ｉｊ， Ｙ^Ｒｉｊ， ｇ ^Ｒｉｊ｝を使って証明情報ＶＲＦ＝｛ｅ_ｂ， Ｔ_ｉｊ， Ｗ_ｉｊ， ｚ_ｉｊ｝を出力する。
【００７８】
証明付部分復号器１４１
図２４，２５，２６を参照して図２１の証明付部分復号器１４１， １４２を説明する。証明付部分復号器１４１ は図２４に示すように部分復号器１４１Ａと部分復号証明生成器１４１Ｂとから構成されている。部分復号器１４１Ａと部分復号証明生成器１４１Ｂは図２５及び２６に更に詳細に示されている。証明付部分復号器１４２ も１４１ と同様の構成とされているので、証明付部分復号器１４２ の説明は省略する。
【００７９】
図２５はＥｌ Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号する部分復号器１４１Ａの構成の一例を表している。入力のＥｌ Ｇａｍａｌ暗号文を（Ｍ，Ｇ）とすると、
平文ｍ及び公開鍵（Ｙ，ｇ）及び乱数に関して
Ｍ＝ｍＹ^ｗ ，Ｇ＝ｇ^ｗ
が成り立っている。
いまＹ＝ｙ×ｙ’及びｙ＝ｇ^ｘ なる秘密鍵の部分情報ｘの値を部分復号者が知って いるとする。部分復号者は入力の（Ｍ，Ｇ）に対してＭ’ ← Ｍ×Ｇ^−ｘを計算して（Ｍ ’，
Ｇ）を出力する。出力は
Ｍ’＝ ｍｙ’^ｗ ，Ｇ＝ｇ^ｗ
を満たすので、平文ｍ及び公開鍵（ｙ’， ｇ）及び乱数ｗに関するＥｌ Ｇａｍａｌ暗号文
となる。
【００８０】
部分復号器１４１Ａは冪乗器１４１Ａ１ と乗算器１４１Ａ２ からなる。この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算
を実行しても良い。
Ｓｔｅｐ１：冪乗器１４１Ａ１ は入力の−ｘ及びＧを用いてＬ_０ ← Ｇ^−ｘ を計算してＬ _０を出力する。
【００８１】
Ｓｔｅｐ２：乗算器１４１Ａ２ は入力のＭ及びＬ_０を用いてＭ’ ← Ｍ×Ｌ_０を計算し てＭ’を出力する。
Ｓｔｅｐ３：部分復号器１４１Ａは入力のＧをそのまま出力する。
部分復号証明生成器１４１Ｂ
図２６は図２５に示した部分復号器１４１Ａが正しく動作している事を秘密情報を明かさずに証明する部分復号証明生成器１４１Ｂの構成の一例を表している。こ
の証明をするためにはｙ＝ｇ^ｘ なる秘密鍵ｘの値を明かさずに、
ｘの値を知っており、かつＭ／Ｍ’＝Ｇ^ｘ が成立する（命題２）
を零知識証明で示す。証明は二つの離散対数 ｌｏｇ_ｇ ｙ及び ｌｏｇ_Ｇ （Ｍ／Ｍ’）が等し
い事を、Ｃｈａｕｍ−Ｐｅｄｅｒｓｅｎのプロトコルで示す。
【００８２】
入力のＲは証明者以外には秘密の乱数であり、ｇ^ＲはＧが入力される前に計 算されているものとする。この部分復号証明生成器１４１Ｂは冪乗器１４１Ｂ１ と、ハ ッシュ器１４１Ｂ２ と、レジスタ１４１Ｂ３ と、乗算器１４１Ｂ４ と、減算器１４１Ｂ５ とから なる。
ハッシュ演算器１４１Ｂ２ は一方向性ハッシュ関数ｈを計算する為の装置で、ハッシュ関数の仕様は公開されているものとする。この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行して
も良い。
【００８３】
Ｓｔｅｐ１：冪乗器１４１Ｂ１ は入力のＲ及びＧを用いてＴ←Ｇ^Ｒ を計算してＴを出 力する。
Ｓｔｅｐ２：ハッシュ器１４１Ｂ２ は入力のＴ及びレジスタ１４１Ｂ３ に保持されている
Ｖ＝ｇ^Ｒを用いてｅ←ｈ（Ｔ， Ｖ）を計算してｅを出力する。
Ｓｔｅｐ３：乗算器１４１Ｂ４ は入力のｅ及びｘを用いてＬ_０ ←ｅ×ｘを計算してＬ _０を出力する。
【００８４】
Ｓｔｅｐ４：減算器１４１Ｂ５ は入力のＲ及びＬ_０を用いてｓ←Ｒ−Ｌ_０ を計算して ｓを出力する。
Ｓｔｅｐ５：Ｔ，Ｖ，ｅ，ｓを証明情報ＶＲＦ として図１９の部分復号証明検証器 Ｐ７０Ｂへ出力する。
部分復号証明検証器Ｐ７０Ｂ
図２１中に示した部分復号証明生成器１４１Ｂ（１４２Ｂ）の出力を検証する部分復号証明検証器Ｐ７０Ｂは部分復号器１４１Ａ（１４２Ａ）が正しく動作していることを検証するものであって、「部分復号器１４１Ａがｘの値を知っており、かつＭ／Ｍ’＝Ｇ^ｘ が成
立する（命題２）」に対して、その真偽を判定して出力する。
【００８５】
図２６に示した部分復号証明生成器１４１Ｂの出力をＣｈａｕｍ−Ｐｅｄｅｒｓｅｎのプロトコルに従って検証する。ｈは仕様の公開された一方向性ハッシュ関数であるとす
る。ｇ，ｙは先に述べたように公開されている。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一
元化して、順次演算を実行しても良い。
【００８６】
Ｓｔｅｐ１：部分復号証明検証器Ｐ７０Ｂ（図１９）は入力のｅ， Ｔ， Ｖ に対して
ｅ＝ ｈ（Ｔ， Ｖ）
でなければ偽を出力して終了する。
Ｓｔｅｐ２：部分復号証明検証器Ｐ７０Ｂは入力のｍ， Ｍ’． Ｇ， ｅ， ｓ に対して
Ｔ＝（Ｍ／Ｍ’）^ｅＧ^ｓ
でなければ偽を出力して終了する。このことはＭ’＝ＭＧ^−ｘ，ｓ＝Ｒ−ｅｘの関係を代入してみれば、正しければ等号が成立つことから理解される。
【００８７】
Ｓｔｅｐ３：部分復号証明検証器Ｐ７０Ｂは入力のＶ， ｅ， ｓ に対してＶ＝ｙ^ｅｇ^ｓ でなければ偽を出力して終了する。このことはＶ＝ｇ^Ｒ ，ｙ＝ｇ^ｘ ，ｓ＝Ｒ−ｅｘなる関係から理解される。
Ｓｔｅｐ４：部分復号証明検証器Ｐ７０Ｂは全ての検証が成立すれば真を出力して終了する。
以上は図２０で説明した各完全置換網における切換装置としての各証明付ＰＲ部分復号器ＳＷの機能構成とそれに関連した検証器Ｐ７０Ｂの説明であった。次に、図２０に示した完全置換網における証明付固定部分復号器ＳＷＦについて説明する。
証明付き固定部分復号器ＳＷＦ
図２７は２入力のＥｌ Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号し、復号結果及び各々の復号結果の正当性の証明を出力する証明付き固定部分復号器ＳＷＦの構成の一例を表している。
【００８８】
この証明付き固定部分復号器ＳＷＦは前述のように図２０の置換網において固定した置換と証明付部分復号を行なうために用いられる。この証明付き固定部分復号器ＳＷＦは図２７に示すように証明付き部分復号器１４１Ｆと証明付き部分復号器１４２Ｆとからなる。証明付き部分復号器１４１Ｆ， １４２Ｆはそれぞれ図２４に示した証明付き部分復号器と同様に構成される。
この証明付き固定部分復号器ＳＷＦでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００８９】
Ｓｔｅｐ１：証明付き部分復号器１４１Ｆは入力の−ｘ及び（Ｍ_０， Ｇ_０）及び乱数情報０を用いて（Ｍ_０， Ｇ_０）を部分復号した結果の（Ｍ’_０， Ｇ_０）及びその正当性の証明である証明情報０を出力する。
Ｓｔｅｐ２：証明付き部分復号器１４２Ｆは入力の−ｘ及び（Ｍ_１， Ｇ_１）及び乱数情報１を用いて（Ｍ_１， Ｇ_１）を部分復号した結果の（Ｍ’_１， Ｇ_１）及びその正当性の証明である証明情報１を出力する。
証明付きＰＲ部分復号器ＳＷ
図２０における証明付きＰＲ部分復号器ＳＷとして、前述の図２１に示したものとは異なる構成例を図２８に示す。
【００９０】
図２８は２入力のＥｌ Ｇａｍａｌ暗号文（Ｍ_０， Ｇ_０），（Ｍ_１， Ｇ_１）を置換撹乱部分復号処理した（Ｍ’_０， Ｇ’_０），（Ｍ’_１， Ｇ’_１）及び、正しい処理が行われた事の証明を秘密情報を明かさずに出力する証明付きＰＲ部分復号器ＳＷの構成の図２１とは異なる例を示す。図２１の例では、置換かく乱に対する証明と部分複合に対する証明を別々に行ったが、図２８では置換撹乱部分復号した結果に対し証明を行っている点が異なる。
【００９１】
この署名付ＰＲ部分復号器ＳＷはＰＲ部分復号器１２４ とＰＲ部分復号証明生成器１２５ からなる。ＰＲ部分復号器１２４ は置換撹乱器１２４Ａと２つの部分復号器１２４Ｂ， １２４Ｃとから構成されている。
このＰＲ部分復号器ＳＷでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００９２】
Ｓｔｅｐ１：ＰＲ部分復号器１２４ は入力の（Ｍ_０， Ｇ_０），（Ｍ_１， Ｇ_１）を入力のＢ及び撹乱パラメータ、秘密鍵の部分情報で置換撹乱部分復号処理した（Ｍ’_０， Ｇ’_０），（Ｍ’_１， Ｇ’_１）を出力する。
Ｓｔｅｐ２：ＰＲ部分復号証明生成器１２５ は入力の（Ｍ_０， Ｇ_０），（Ｍ_１， Ｇ_１）及び（Ｍ’_０，Ｇ’_０）、（Ｍ’_１， Ｇ’_１）及び乱数情報を使って証明情報を出力する。
この証明付きＰＲ部分復号器ＳＷにおいても置換と、撹乱と、部分復号との順は任意に変更してもよい。
【００９３】
図２８における置換撹乱器１２４Ａは図２２に示した置換撹乱器１２１ と同様に構成され、部分復号器１２４Ｂ及び１２４Ｃはそれぞれ図２５に示した部分復号器１４１Ａ（１４１Ｂ）と同様に構成される。
この置換撹乱部分復号器１２４ では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００９４】
Ｓｔｅｐ１：置換撹乱器１２４Ａは置換撹乱用のパラメータＢ， ｇ^−ｒ０ ， Ｙ^−ｒ０， ｇ^−ｒ１， Ｙ^−ｒ１ を用いて入力の（Ｍ_０， Ｇ_０），（Ｍ_１， Ｇ_１）を置換撹乱処理した結果を示す２対の情報を出力する。
Ｓｔｅｐ２：部分復号器１２４Ｂは置換撹乱処理した結果の一方の対情報を秘密鍵の部分情報−ｘを用いて部分復号し（Ｍ’_０， Ｇ’_０）として出力する。
Ｓｔｅｐ３：部分復号器１２４Ｃは置換撹乱処理した結果の他方の対情報を秘密鍵の部分情報−ｘを用いて部分復号し（Ｍ’_１， Ｇ’_１）として出力する。
ＰＲ部分復号証明生成器１２５
図２８におけるＰＲ部分復号証明生成器１２５ はＰＲ部分復号器１２４Ａが正しく動作している事を秘密情報を明かさずに証明する構成の一例を示している。
【００９５】
入力のＢは置換撹乱器１２４Ａ中の置換器（図２２参照）に入力された置換パラメータであり、入力のｒ_ｊ （ｊ∈｛０， １｝）は置換撹乱器１２４Ａ中の撹乱器（図２２参照）に入力された撹乱用の乱数であり、入力のｘは復号鍵の部分情報であり、入力のｅ， Ｋ_０， Ｋ_１， Ｒ_ｉｊ（ｉ， ｊ∈｛０， １｝）は証明情報生成用の乱数であり、入力のｇ^Ｋ０， ｇ^{Ｋ１＋ｅｘ} ｙ’^Ｒｉｊ，ｇ^Ｒｉｊ （ｉ， ｊ∈｛０， １｝）は入力のＭ_ｉ， Ｇ _ｉ， Ｍ’_ｊ， Ｇ’_ｊ （ｉ， ｊ∈｛０， １｝）が入力されるより前に計算された証明情報生成用のパラメータである。
【００９６】
出力のＶ_ｂ， ｅ_ｂ， ｓ_ｂ， Ｔ_ｉｊ， Ｗ_ｉｊ， ｚ_ｉｊ， （ｂ， ｉ， ｊ∈｛０， １｝）はｂ＝ｉ（＋）ｊとして（Ｍ_ｉ， Ｇ_ｉ）と（Ｍ’_ｊ， Ｇ’_ｊ）の対応を証明するか、または装う為の情報である。
置換撹乱部分復号器１２４ が正しく動作していることを直接証明するためには、置換用の乱数Ｂ∈｛０， １｝及び撹乱や復号用の秘密のパラメータの値を明かさずに、ｂ＝ｉ（＋）ｊであるとして、
ｂ＝０なる全ての ｉ， ｊ∈｛０， １｝に関してＭ／Ｍ’_ｊ ＝ｙ^ｒｊＧ_ｉ ^ｘ かつＧ_ｉ ／Ｇ’_ｊ ＝ｇ^ｒｊ
ｂ＝１なる全ての ｉ， ｊ∈｛０， １｝に関してＭ／Ｍ’_ｊ ＝ｙ^ｒｊＧ_ｉ ^ｘ かつＧ_ｉ ／Ｇ’_ｊ ＝ｇ^ｒｊ
・・・（命題３）
を示さなくてはならない。このために以下に示すようにして証明情報Ｖ_ｂ ，ｅ_ｂ ，ｓ_ｂ （ｂ∈｛０， １｝），Ｔ_ｉｊ，Ｗ_ｉｊ，ｚ_ｉｊ（ｉ， ｊ∈｛０， １｝）を生成する。
【００９７】
全ての ｉ， ｊ∈｛０， １｝に関して、
ｉ（＋）ｊ＝Ｂならば
Ｔ_ｉｊ ← ｙ’^Ｒｉｊ Ｇ_ｉ ^Ｋ０，Ｗ_ｉｊ ← ｇ^Ｒｉｊ
ｉ（＋）ｊ＝Ｂ’ならば（Ｂ’はＢの反転）
Ｔ_ｉｊ ← （Ｍ_ｉ ／Ｍ’_ｊ）^ｅ ｙ’^Ｒｉｊ Ｇ_ｊ ^Ｋ１ ，Ｗ_ｉｊ ← （Ｇ_ｉ ／Ｇ’_ｊ）^ｅ ｇ^Ｒｉｊ
を演算する。
【００９８】
更に
Ｖ_Ｂ ← ｇ^Ｋ０，Ｖ_Ｂ’← ｇ^{Ｋ１＋ｅｘ}
としＢ＝０ならば
ｅ_０ ← −ｅ＋ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
を演算し、またｅ_１ ←ｅとし、
Ｂ＝１ならば
ｅ_１ ← −ｅ＋ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
を演算し、かつｅ_０ ←ｅとし
更にｉ（＋）ｊ＝Ｂなら
ｚ_ｉｊ ← Ｒ_ｉｊ− ｅ_ｂ ｒ_ｊ
を演算し、ｉ（＋）ｊ＝Ｂ’ならｚ_ｉｊ ← Ｒ_ｉｊとし
Ｂ＝０ならば
ｓ_０ ← Ｋ_０ −ｅ_０ ^ｘ
を演算し、ｓ_１ ← Ｋ_１ とし、
Ｂ＝１ならば
ｓ_１ ← Ｋ_０ −ｅ_１ｘ
を演算し、ｓ_０ ← Ｋ_１ とする。
【００９９】
この置換撹乱部分復号証明生成器１２５ は上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また、同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
ＰＲ部分復号証明検証器Ｐ７０Ｃ
図１９におけるＰＲ部分復号証明検証器Ｐ７０Ｃは図２８に示したＰＲ部分復号器１２４ が正しく動作している事を検証する。この検証器Ｐ７０Ｃは図２８中のＰＲ部分復号証明生成器１２５ の出力を検証する。
【０１００】
ＰＲ部分復号証明検証器Ｐ７０Ｃの入力はｅ_ｂ， Ｔ_ｉｊ，Ｗ_ｉｊ，Ｚ_ｉｊ，（ｂ， ｉ， ｊ∈｛０， １｝）であり、これは図２８のＰＲ部分復号証明生成器１２５ の出力であり、ｂ＝ｉ（＋）ｊとして（Ｍ_ｉ， Ｇ_ｉ）と（Ｍ’_ｊ， Ｇ’_ｊ）の対応を証明するか、または装う為の情報である。この検証器Ｐ７０Ｃは先ず
ｅ_０＋ｅ_１ ＝ｈ（Ｔ_００，Ｔ_０１，Ｔ_１０，Ｔ_１１，Ｗ_００，Ｗ_０１，Ｗ_１０，Ｗ_１１）
が成立するかを演算して確め成立しなければ偽を出力して終了し、成立すれば、全てのｂ∈｛０， １｝に関してＶ_ｂ＝ｇ^ｓｂｙ^ｅｂ が成立するかを演算して確め、成立しなければ偽を出力して終了し、成立すれば、全てのｉ， ｊ∈｛０， １｝に関してｂ＝ｉ（＋）ｊであるとして、
Ｔ_ｉｊ＝（Ｍ_ｉ ／Ｍ’_ｊ）^ｅｂｙ’^ｚｉｊ Ｇ_ｉ ^ｓｂ ，Ｗ_ｉｊ＝（Ｇ_ｉ ／Ｇ’_ｊ）^ｅｂｇ^ｚｉｊ
が成立するかを演算して確め、成立しなければ偽を出して終了し、成立すれば真を出力する。このようにして命題３の真偽が判定される。
【０１０１】
この検証器Ｐ７０Ｃでは、上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
完全置換網１０
図２９Ａ及び図２９Ｂはそれぞれ４入力及び８入力の完全置換網１０Ａ及び１０Ｂの構成の一例を表している。
【０１０２】
完全置換網とは証明付きＰＲ部分復号器ＳＷ及び証明付き固定部分復号器ＳＷＦの複数個が行列に配され、縦続的に接続され、各証明付きＰＲ部分復号器ＳＷの秘密の置換パラメータＢ_ｉ の値の組合せによって入力に対するあらゆる置換を実現できる網のことである。入力はＮ個のＥｌ Ｇａｍａｌ暗号文であり出力はＮ個のＥｌＧａｍａｌ暗号文またはＮ個の平文である。また置換の正当性を証明する情報として各証明付きＰＲ部分復号器及び各証明付き固定部分復号器の証明情報及び秘密鍵や置換撹乱パラメータや乱数情報以外の入出力情報が出力公開される。
【０１０３】
図２９Ａでは２個のＥｌ Ｇａｍａｌ暗号文が入力され、２個のＥｌ Ｇａｍａｌ暗号文を出力する処理器として前記証明付きＰＲ部分復号器ＳＷと証明付き固定部分復号器ＳＷＦが２行３列に配され、各行の部分復号器の出力が同一行の次の列の部分復号器へ供給されるものと、行が入れ替えられて次の列の部分復号器へ入力されるものとがあり、部分復号器中の実線ブロックで示しているものは証明付きＰＲ部分復号器ＳＷであって、２つのＥｌ Ｇａｍａｌ暗号文を置換撹乱処理し、秘密鍵の部分情報を用いて部分復号し、その置換撹乱結果と、その正当性を証明するための証明情報を出力し、部分復号器中の破線ブロックで示されているものは証明付き固定部分復号器ＳＷＦであって、このＥｌ Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号し、その復号結果と、その正当性を証明するための証明情報を出力する。この場合４入力の配列に対し置換可能な配列は４！＝４×３×２＝２４通りであるが、Ｂ_ｉ の数は５あれば２^５ ＝３２通りの配列が可能となり、入力配列に対し、置換可能な全ての配列の何れにも設定可能である。つまり４入力の配列の場合は、証明付きＰＲ部分復号器、換言すれば置換パラメータＢ_ｉ を設定できる処理器は５個あれば完全置換網を構成できる。一方証明付きＰＲ部分復号器と比較して証明付き固定部分復号器は構成が可成り簡単であり、つまり計算量が少なくて済むので、１行３列目の処理器は証明付き固定部分復号器としている。これをも証明付きＰＲ部分復号器としてもよい。
【０１０４】
図２９Ｂは証明付きＰＲ部分復号器ＳＷ又は証明付き固定部分復号器ＳＷＦが４行５列に配され、内側の３列間で同一行で出力が入力されるものと行が入れ替えられて出力が入力されるものとがある。この構成は図中に破線で示すように図２９Ａの４入力４出力の完全置換網を二つ組合せたものである。
秘密の置換パラメータの第ｉ列のＢ_ｉ の値が分からなければどのような置換が行われたのか推定する事は出来ない。つまりＭ’_０ ，…，Ｍ’_３ はＢ_ｉ の値の組み合わせを知らなければ誰が入力した文かは判らない。図２９Ａ、図２９Ｂの何れにおいても正しく復号するために、同じ列（第ｉ列）の各部分復号器は同じ復号鍵ｘ_ｉ を持つ。
完全置換網１０Ｃ
図３０は２Ｎ入力の完全置換網１０Ｃの構成の一例を表している。原理は Ａ．Ｗａｋｓｍａｎ． Ａ ｐｅｒｍｕｔａｔｉｏｎ ｎｅｔｗｏｒｋ． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ，１５（１）：１５９−１６３， １９６８．による。
【０１０５】
置換網１０ＣはＮ入力の完全置換網１０Ｃ１， １０Ｃ２及び２入力の完全置換網（証明付きＰＲ部分復号器）ＳＷのみから構成されているので２入力の完全置換網を用いて４入力、８入力、…、２^ｎ 入力の完全置換網を構成する事が出来る。図ではＮ入力完全置換網を２つ設け、その入力段にＮ個の２入力２出力の証明付き置換撹乱部分復号器を設け、出力段に（Ｎ−１） 個の２入力２出力の証明付きＰＲ部分復号器ＳＷと、１個の証明付き固定部分復号器ＳＷＦを設けている。図２９Ｂの構成は図３０の構成でＮ入力完全置換網として４入力完全置換網が用いられた場合となる。
【０１０６】
従って、証明付き置換撹乱部分復号器及び証明付き固定部分復号器のみを用いて部分復号処理を行う機能をもった２^ｎ 入力の完全置換網を構成する事が出来る。
Ｎ（＝２^ｎ ）入力の完全置換網に必要な部品は、証明付き置換撹乱部分復号器Ｎｌｏｇ_２ Ｎ−Ｎ＋１個及び証明付き固定部分復号器 （Ｎ−１）個であり、全体の段数（列の数）は２Ｎ ｌｏｇ_２ Ｎ−１段である。
一括不正回復付き検証可能匿名通信路１００
前述の図２０は８入力２秘密漏洩耐性２故障耐性一括不正回復付き検証可能匿名通信路の構成の一例を表している。一括不正回復付き検証可能匿名通信路１００ は置換サーバＰＳ_１〜ＰＳ_５と、置換サーバ１８Ｃと、置換サーバ１８Ｄと、置換サーバ１８Ｅと、置換サーバ１８Ｆとが縦続的に接続されて構成されている。ｔ秘密漏洩耐性とは全部でＶ（＞２ｔ）個の置換サーバのうち最大ｔ個の装置の置換秘密情報Ｂ_ｉ が攻撃などにより漏洩しても入出力の対応が完全に隠蔽されることを意味する。
【０１０７】
一括不正回復付き検証可能匿名通信路１００ は３つの完全置換網１０Ａ，１０Ｂ，１０Ｃを含んでおり、完全置換網を跨る置換サーバを持っていないので、どの２つの置換サーバの置換秘密情報Ｂ_ｉ が漏洩してもその２つの置換サーバを含まない完全置換網が必ず一つは存在し、その完全置換網の秘密情報が全て隠蔽されているのでこの完全置換網により入出力の対応が隠蔽され、この匿名通信路１００ の入出力の対応も隠蔽される。従って図２０に示した匿名通信路では５つの置換サーバＰＳ_１〜ＰＳ_５よりなるから一括不正回復付き検証可能匿名通信路１００ は２秘密漏洩耐性を持っている。
【０１０８】
一般に一括不正回復付き検証可能匿名通信路１００ が完全置換網をｔ＋１ 個直列に接続した形状の網を持ち、この網をＶ個に分割し、分割された各々の部分を置換サーバとする場合、どの置換サーバも２つの完全置換網に跨ることが無いように網の分割が行われていれば、その一括不正回復付き検証可能匿名通信路はｔ秘密漏洩耐性を持つ。
ｔ故障耐性とは全部でＶ（＞２ｔ）個の置換サーバのうち最大ｔ個の動作が正しくない時でも不正回復により最終的には正しく出力ができる一括不正回復付き検証可能匿名通信路であることを意味する。
【０１０９】
各置換サーバは自分の秘密鍵を他の置換サーバに検証可能な秘密分散法で、ｔ＋１個以上の置換サーバが集まれば秘密鍵を復元出来るように秘密分散する。例えば、０次の係数を隠蔽すべき秘密鍵ｘ_ｉ とし秘密の乱数により他の係数が決定されるｚに関するｔ次多項式ｆ_ｉ（ｚ）のｚ＝ｊの値ｘ_ｉｊ＝ｆ_ｉ（ｊ）をｊ番目の置換サーバに対して分配するとすれば、一つのｉに対してｔ＋１ 個以上のｘ_ｉｊ及び対応するｊが集まれば、その中の任意のｔ＋１ 個の互いに異なるｊの集合Ｊに関するＬａｇｒａｎｇｅ補間公式
【０１１０】
【数８】

を用いて、ｘ_ｉ＝ｆ_ｉ（０）として秘密鍵を復元できる。このような鍵秘密分散復元の手法は例えば共立出版株式会社１９９５年１２月２０日発行、岡本龍明、太田和夫編「暗号・ゼロ知識証明・数論」６２〜６３頁に示されている。
【０１１１】
図１９に示したように、各置換サーバＰＳは他の装置の入出力の正当性を検証するための検証器２１を具備している。各置換サーバＰＳで暗号文の出力が行われる度にその正当性を検査し結果を掲示板に公開する。
各置換サーバは検査の結果、正しいと認められる最後の出力を自分の入力とし、その入力に対して未だ部分復号処理に用いられていない全ての公開鍵の積を求め、これを撹乱処理に必要なパラメータとして置換撹乱部分復号処理を行う。
【０１１２】
最終出力が終った後、全ての置換サーバが正しく動作した、つまり全装置が正しかったと全員が納得し、全ての置換サーバが出力した場合は、最終出力が求める平文の列（リスト）になる。
上記以外の場合、最終出力が終った後、最終的に互いに信頼できる入出力を行った置換サーバが３個（ｔ＋１個）以上集まった時は、正しく動作していないと判断された全ての置換サーバの秘密鍵を、鍵秘密分散復元の手法により復元し、その総和をｘ’として公開する。
【０１１３】
最終的に互いに信頼できる置換サーバが各々最終的に信頼できる出力を、秘密鍵ｘ＾を用いて復号し平文の列を求め公開する。この秘密鍵ｘ’により復号可能なことは前記「一括化可能」条件にもとずく、最終的に互いに信頼できる入出力を行った置換サーバが３個（ｔ＋１個）以上集まらない時には不正回復は失敗する。
置換サーバが信頼できるものであるかはその入力と出力と証明情報を用いて、前述した証明付きＰＲ部分復号器、証明付き置換撹乱器、証明付き固定部分復号器に対する検証により、その置換サーバが構成する処理器の全てについて、検証すればよい。また置換サーバに対する処理は、その縦続接続された順に行うが、その入力としては直前の信頼できる置換サーバの出力を用いる。以下にどの置換サーバの出力を入力とすればよいかの検索手法の例を示す。なおこの検索は各置換サーバ中の判定部Ｐ６０ で行う。
【０１１４】
また匿名通信路１００ への入力リストをＬ_０とし、ｉ番目の置換サーバＰＳ_ｉ の出力リストをＬ_ｉとする時、ｊ番目の置換サーバＰＳ_ｊ の入力リストＬ_ｊを求めるには例えば図３１に示すように行えばよい。ｊ番目の置換サーバＰＳ_ｊ の、正しい処理を行なった直前の置換サーバの位置をｔで表すと、まずｔ＝０、ｉ＝１と初期化し（Ｓ１）、ｉ＜ｊかを調べ（Ｓ２）、ｉがｊより小さければｉ番目の置換サーバＰＳ_ｉ の証明情報ＶＲＦ_ｉは入力リストＬ_ｔと出力リストＬ_ｉの１対１の対応を証明しているかを調べ（Ｓ３）、証明している場合はｔ＝ｉとし（Ｓ４）、更にｉを＋１してステップＳ２に戻り（Ｓ５）、ステップＳ３で１対１の対応を証明していない場合はステップＳ５に移り、ｉがｊと等しいかそれより大きくなれば処理を終了し、その時のｔの値から置換サーバＰＳ_ｔ の出力リストＬ_ｔが求める入力リストになる。
【０１１５】
図３１に示した入力リストの探索は次のようにして処理を削減することができる。図３１において、各置換サーバが決定した入力リストがどの置換サーバからのものであるかその番号ｔを掲示板に登録し、ステップＳ２とＳ３との間において図３２に示すように置換サーバＰＳ_ｉ は信頼できる置換サーバの出力リストＬ_ｔを入力としているかを調べる（Ｓ６）。もし検証対象の置換サーバＰＳ_ｉ が信頼できる置換サーバの出力リストＬ_ｔを入力としていなかった場合は、ステップＳ３の検証を行なわないでも、その置換サーバＰＳ_ｉ が不正な処理を行なったと判断できる。そこで、図３２に示すように、置換サーバＰＳ_ｉ がリストＬ_ｔを入力としていない場合は、その置換サーバＰＳ_ｉ の入力リストＬ_ｔと出力リストＬ_ｉの対応を検証することなく、ステップＳ５に移り、リストＬ_ｔを入力としている場合は、その置換サーバＰＳ_ｉ についてステップＳ３を実行する。これにより、図３１に示した場合より処理量を減少することができる。置換サーバＰＳ_１〜ＰＳ_ｊ−１についての検証が終了すれば（ｉ≧ｊとなれば）、ステップＳ６でｔの値を掲示板に登録し、処理を終了する。
【０１１６】
更に他の例を示す。この例では、各置換サーバＰＳ_ｉ ， ｉ＝１， …，Ｖはそれより上流の前置換サーバについて、それぞれ信頼できるか否かの判定結果を掲示板に例えば図３３Ａに示すように登録するものとする。又、各置換サーバＰＳ_ｊ は、自分より上流の各置換サーバＰＳ_ｋ （１＜ｋ＜ｊ）に対する信頼性の判定結果を信頼度情報Ｒ_ｋ＝真又は偽、として記録するレジスタを有しているものとする。図３３Ｂは置換サーバＰＳ_ｊ のレジスタに記録された信頼度情報の例を示している。図３３Ａでは、すでにｊ−１番目の置換サーバまでそれぞれそれらより上流の全ての置換サーバに対する判定結果を○印は信頼性あり、×印は信頼性なしで示している。
【０１１７】
各置換サーバは自分より上流の最も近い信頼できる置換サーバの出力を入力とすることが要求されているので、ｊ番目の置換サーバＰＳ_ｊ は１番目の置換サーバＰＳ_１ から順に検査し、例えば２番目の置換サーバは信頼性がないと判定したにもかかわらず、図３３Ａに示すように掲示板を参照するとｉ番目の置換サーバは２番目の置換サーバを信頼性ありと判定している。従って、ｊ番目の置換サーバはｉ番目の置換サーバを信頼性がないと判定することができる。このような場合、ｊ番目の置換サーバはｉ番目の置換サーバについての入出力の対応関係の検証を省略することができる。同様に、ｊ番目の置換サーバが例えば３番目の置換サーバを信頼性ありと判定したにもかかわらず、もしｉ番目の置換サーバが３番目の置換サーバを信頼性なしと判定していたら（図３３Ａでは信頼性ありとなっている）、その場合も、ｊ番目の置換サーバはｉ番目の置換サーバを信頼性がないと判定でき、この場合も、ｊ番目の置換サーバはｉ番目の置換サーバに対する入出力の対応の検証を省略することができる。この方法を使ったｊ番目の置換サーバによる入力リストの探索処理を図３４を参照して説明する。
【０１１８】
図３４に示す置換サーバＰＳ_ｊ の入力リストの検索処理において、まずｔ＝０， ｉ＝０とし、置換サーバＰＳ_ｊ のレジスタの ｋ＝ １， …， ｊ−１ に対する値Ｒ_ｋ を全て真とする初期化を行い（Ｓ１）、ｉがｊより小さければ（Ｓ２）、図３３Ｂに示したレジスタを参照し、ｋ＝ｉ 番目の置換サーバの信頼度情報Ｒ_ｉ が真であるかを調べ（Ｓ３）、Ｒ_ｉ が真であれば（Ｒ_ｉの初期値は真に設定されている）、置換サーバＰＳ_ｉ の証明情報ＶＲＦ_ｉがリストＬ_ｔとリストＬ_ｉの１対１対応を証明しているかを調べ（Ｓ４）、正しく証明するものであればｔをｉに更新する（Ｓ５）。この場合、ｋ＝ ｉ＋１， …， ｊ−１ の置換サーバＰＳ_ｋ はそれぞれ置換サーバＰＳ_ｉ の出力リストＬ_ｉを正しい、即ち置換サーバＰＳｉ は信頼性がある、と判断すべきであるから、図３３Ａの掲示板を参照し、もしこの置換サーバＰＳ_ｉ を信頼性がないと判断した置換サーバＰＳ_ｋ があれば、図３３Ｂに示すように、その置換サーバに対する信頼度情報Ｒ_ｋ を偽に変更する（Ｓ７）、その後、ｉを＋１してステップＳ２に戻る（Ｓ７）。
【０１１９】
ステップＳ４でリストＬ_ｔとリストＬ_ｉが１対１で対応することを証明できない場合は、ステップＳ８に移り、掲示板を参照し、もしｋ＝１， ， ｊ−１の置換サーバＰＳ_ｋ でサーバＰＳ_ｉ を信頼できると判定している置換サーバがあれば、その置換サーバについての信頼度情報Ｒ_ｋを偽に変更し、ステップＳ７でｉを歩進してステップＳ２に戻る。従って、以降のループ処理で、ステップＳ２でｉが、先にステップＳ４又はＳ８でレジスタの信頼度情報Ｒ_ｋが偽とされた置換サーバの番号ｉ＝ｋ となった時には、ステップＳ３でレジスタにあるそのサーバの信頼度情報Ｒ_ｋが偽となっているので、ステップＳ４の検証を行なわず、ステップＳ８に移る。
【０１２０】
ステップＳ２でｉがｊを超えると、その時のリストＬ_ｔを求める入力とし、また全ての置換サーバＰＳ_ｋ についての信頼度情報Ｒ_ｋ を公開（掲示板に登録）して終了する。
このように各検査結果である信頼度情報Ｒ_ｋ を利用することにより、入力すべき出力リストの検索にかかる処理量が少なくて済む。
図２０では各置換サーバＰＳ_１〜ＰＳ_５の処理器として証明付き置換撹乱部分復号器のみ又はこれと証明付き固定部分復号器とを用いた。しかし、各置換サーバＰＳ_１〜ＰＳ_５を証明付き置換撹乱器と証明付き固定部分復号器とを用いて構成することもできる。例えば図３５に示すように、図２０中の証明付き置換撹乱部分復号器を証明付き置換撹乱器に置きかえ、図２０中の証明付き固定部分復号器の部分はその入力をそのまま出力させ、各置換サーバの最後の段（列）の後段に各行ごとに証明付き固定部分復号器をそれぞれ設けてもよい。
【０１２１】
また図２０中の例えば置換サーバＰＳ_１ の初段（第１列）の各行の処理器を全て証明付き置換撹乱器に変更してもよい。要は置換サーバは、全体として証明付き置換撹乱処理と、少なくとも１段（１列）の処理器による証明付き部分復号処理とを行うものであればよい。なおｔ故障耐性が問題とならず、ｔ秘密漏洩耐性のみを必要とする場合は置換サーバを重複することなく構成された完全置換網がｔ＋１個あればよく、Ｖ＞２ｔなる条件は必要としない。
【０１２２】
前述したこの発明の各実施例において、この発明による匿名通信路を形成している置換網は２入力２出力の単位切換装置ＳＷ（ＳＷＦ）を規則に従って接続して構成してもよいが、例えばＮ＝２^ｋ入力の場合、単位切換装置ＳＷ（ＳＷＦ）が入力側から２^ｋ−１個ずつ（２ｋ−１）段に配列された置換網において、各段で１つのデータ処理装置が前段からの処理結果を取り込み、単位切換装置ＳＷの２ｋ−１個分の処理を実行し、処理結果を順次出力するようにしてもよいし、更に、これら（２ｋ−１）段の（２ｋ−１）個のデータ処理装置が行なうべき処理を１つの処理装置が順次実行してもよい。
【０１２３】
例えば、（２ｋ−１）段のそれぞれにデータ処理装置が１つずつ設けられている場合、Ｊ段目の処理装置には前段から２^ｋ個の処理結果であるＥｌ Ｇａｍａｌ 暗号（Ｍ， Ｇ）を順次取り込み、前述したような置換、撹乱及び部分復号を行なって得た暗号（Ｍ’，Ｇ’）を予め決めた規則に従って順に出力する。この処理手順を図３６から３９を参照して説明する。
図３６はＪ段目の処理装置が１〜ｋ−１段のグループ、ｋ〜２ｋ−２段のグループ、及び最後の２ｋ−１段のどの段に属するかを判定し、処理１、処理２及び処理３のどれを実行すべきかを決定する。各段の処理装置は、Ｎ＝２^ｋ個の出力端子位置に対応してＮ個の処理結果を保持するＮ個の出力レジスタを有するものとする。
ステップＳ１：Ｊ＝２ｋ−１か否か、即ち最終段であるか否か判定し、最終段であれば処理３（図３９）の実行に移る。そうでなければステップＳ２に移る。
ステップＳ２：Ｊ−ｋ≧０ か否か、即ちＪはｋ〜２ｋ−２ の値か判定し、そうであれば処理２（図３８）の実行に移る。そうでなければステップＳ３に移る。
ステップＳ３：Ｊは１〜ｋ−１の値であり、処理１（図３７）の実行に移る。
【０１２４】
図３７，３８，３９はそれぞれ処理１、処理２、処理３を実行するフローを表す。ここで、（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）はＪ−１段目のランダム置換の対象となる２つの出力位置［２ｉ］， ［２ｉ＋１］の暗号文（Ｍ_２ｉ， Ｇ_２ｉ）， （Ｍ_２ｉ＋１， Ｇ_２ｉ＋１）を表す。ｌｒｏｔ（ｕ， ｖ）は２進表現のデータｕ中のＬＳＢ 側からｖビットのデータに対し１ビット左回転を与えることによりデータｕを変換することを意味する。例えば、２進表現でｕ＝１０１１０であり、ｖ＝３ とすると、ｌｒｏｔ（ｕ， ｖ）は、１０１１０の右側３ビット１１０を、左へ１ビット回転させて１０１とすることにより、ｕを１０１０１に変換する。同様に、ｒｏｔ（ｕ， ｖ）は２進表現されたデータｕのＬＳＢ 側からｖビットのデータを右へ１ビット回転させることによりデータｕを変換する。
【０１２５】
ｂｉｔ［ｘ， ｙ］は、２進表現されたｘの下位ｙビットの値を表す。例えばｘ＝１０００１でｙ＝４の場合、ｂｉｔ［ｘ， ｙ］＝１となる。
図３７に示す処理１はＪ＝１， …， ｋ−１ の置換段における処理であり、これらの段では以下のように全ての対の入力暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対しランダム置換、撹乱、部分復号を行う。
ステップＳ１１：ｉ＝０ に初期設定する。
ステップＳ１２：Ｊ−１ 段目からの２ｉ番目と（２ｉ＋１）番目のランダム置換対象となる２つの暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ［ｒｏｔ（２ｉ， ｋ−Ｊ＋１）］番目と、［ｒｏｔ（２ｉ＋１， ｋ−Ｊ＋１）］番目の出力レジスタに格納する。
ステップＳ１３：ｉを１増加する。
ステップＳ１４：ｉ≦２^ｋ−１ であるか判定し、そうであればまだ未処理データがあるのでステップＳ１１に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２６】
図３８に示す処理２はＪ ＝ｋ， … ， ２ｋ−２ の置換段における処理であり、対の入力暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対し以下のように処理を行なう。
ステップＳ２１：ｉ＝０ に初期設定する。
ステップＳ２２：ｂｉｔ［ｉ， Ｊ−ｋ］＝０ であるか判定し、ＹＥＳ であれば固定置換装置ＳＷＦでの処理であり、ステップＳ２３に移り、ＮＯであれば置換装置ＳＷでの処理でありステップＳ２４に移る。
ステップＳ２３：前段（Ｊ−１ 段目）からの２ｉ番目と（２ｉ＋１）番目の対の暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）をそのままそれぞれ［ｌｒｏｔ（２ｉ， Ｊ−ｋ＋２）］番目と、［ｌｒｏｔ（２ｉ＋１， Ｊ−ｋ＋２）］番目の出力レジスタに格納する。
ステップＳ２４：Ｊ−１ 段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ［ｌｒｏｔ（２ｉ， Ｊ−ｋ＋２）］番目と、［ｌｒｏｔ（２ｉ＋１， Ｊ−ｋ＋２）］番目の出力レジスタに格納する。ステップＳ２５：ｉを１増加する。
ステップＳ２６：ｉ≦２^ｋ−１ であるか判定し、そうであればまだ未処理データがあるのでステップＳ２２に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２７】
図３９に示す処理３は最終段Ｊ＝２ｋ−１ における処理であり、前段からの対の入力暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対し以下のように処理を実行する。
ステップＳ３１：ｉ＝０ に初期設定する。
ステップＳ３２：ｂｉｔ［ｉ， Ｊ−ｋ］＝０ であるか判定し、ＹＥＳ であれば固定置換装置ＳＷＦでの処理であり、ステップＳ３３に移り、ＮＯであれば置換装置ＳＷでの処理でありステップＳ３４に移る。
ステップＳ３３：Ｊ−１ 段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）をそのままそれぞれ２ｉ番目と、（２ｉ＋１）番目の出力レジスタに格納する。ステップＳ３４：Ｊ−１ 段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（Ｌ_Ｊ−１［２ｉ］， Ｌ_Ｊ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ２ｉ番目と、（２ｉ＋１）番目の出力レジスタに格納する。
ステップＳ３５：ｉを１増加する。
ステップＳ３６：ｉ≦２^ｋ−１ であるか判定し、そうであればまだ未処理データがあるのでステップＳ３２に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２８】
全（２ｋ−１）段の処理を１つの処理装置で実行する場合は、図３６〜３９の処理手順を、Ｊ＝１， ２， ．．．， ２ｋ−１について順次繰り返せばよい。
以上説明したこの発明による置換撹乱復号処理は、コンピュータプログラムとして記録媒体に記録しておき、そのプログラムを読み出して実行することにより実施してもよい。
上述した符号化装置、復号化装置は共に、その各機能をコンピュータによりプログラムを解読実行させることにより行わせることもできる。
【０１２９】
図４０はこの発明による匿名通信路を構成する置換網における証明付置換撹乱部分復号方法をコンピュータで実施する場合の構成を示す。コンピュータ８０は、バス８８を介して互いに接続されたＣＰＵ８１、ＲＡＭ８２，ＲＯＭ８３，入出力インタフェース８４、ハードディスク８５を含んでいる。ＲＯＭ８３にはコンピュータ８０を動作させる基本プログラムが書き込まれてあり、ハードディスク８５には前述した例えば１つの置換サーバがこの発明による証明付置換撹乱部分復号処理方法を実行するプログラムが予め格納されている。例えば符号化時にはＣＰＵ８１はハードディスク８５から符号化プログラムをＲＡＭ８２にロードし、掲示板４００ からインタフェース８４を介して取り込んだ暗号化投票文をプログラムに従って処理することにより匿名通信路を通して暗号投票を復号化し、インタフェース８４から掲示板４００ に出力する。
【０１３０】
この発明による証明付置換撹乱部分復号化方法を実行するプログラムは内部バス８８に駆動装置８６を介して接続された外部ディスク装置８７に記録されたものを使用してもよい。この発明による方法を実行するプログラムが記録された記録媒体としては、磁気記録媒体や、ＩＣメモリや、コンパクトディスクなどどのような形態の記録媒体であってもよい。
【０１３１】
【発明の効果】
この発明によれば、少数の入力に対する置換が比較的容易なことを利用して、少数の入力の置換を繰り返して全体の置換を構成することにより、全体の入力をＮ個としたとき、全体の置換に対する証明の為の計算量、通信量をＮｌｏｇ ２Ｎに比例する量にまで低減することが可能となり、効率的な検証可能匿名通信路を構築することができる。
【０１３２】
従来においては１つの置換サーバで不正（故障）が検出されるごとに、その補償処理を行っていた、従ってｔ個の装置で不正があればｔ回の補償処理を必要としたが、この発明によればＶ個の置換サーバのうちｔ個の出力が信頼できなくなった場合でも、その信頼できなくなった（不正、故障）装置を迂回して処理し最後に、鍵秘密分散回復法により回復した鍵を用いて平文を得ることができ、たった１回の不正回復処理を行えば不正回復が完了する。
【０１３３】
またこの発明により従来ｔ回の不正回復を行っていたのに比べてｔ倍高速に不正を回復可能になり検証可能匿名通信路における帯域保証を効率的にすることが可能となった。
更に置換サーバを重複使用することなく、完全置換網をｔ＋１個直列に構成することにより、ｔ秘密漏洩耐性が得られる。
【図面の簡単な説明】
【図１】従来の４入力の置換網を示すブロック図。
【図２】この発明が適用される装置の全体を示すブロック図。
【図３】４入力に対する匿名通信路の構成と検証端末の構成を示すブロック図。
【図４】図３中の切換装置ＳＷの構成を示すブロック図。
【図５】図４中の切換部１２の構成を示すブロック図。
【図６】図４中の置換証明部１４の構成を示すブロック図。
【図７】図３中の復号装置２０の構成を示すブロック図。
【図８】図７中の復号部２１の構成を示すブロック図。
【図９】図７中の復号証明部２２の構成を示すブロック図。
【図１０】図３中の置換検証部３０の構成を示すブロック図。
【図１１】図３中の復号検証部４０の構成を示すブロック図。
【図１２】第２実施例のシステム構成を示すブロック図。
【図１３】図１２中の置換サーバＰＳの構成を示すブロック図。
【図１４】図１２中の復号サーバ２０Ｓの構成を示すブロック図。
【図１５】第２実施例における各サーバ内のデータの流れを示す図。
【図１６】第３実施例のシステム構成を示すブロック図。
【図１７】第３実施例中の復号サーバ２０Ｓにおける復号部の構成を示すブロック図。
【図１８】第３実施例における復号検証部の構成を示すブロック図。
【図１９】この発明の匿名通信路を用いたシステム構成例を示すブロック図。
【図２０】図１９の実施例において掲示板を介して縦続接続された置換サーバにより構成された複数の完全置換網を示すブロック図。
【図２１】証明付き置換撹乱部分復号器の機能構成例を示すブロック図。
【図２２】置換撹乱器の機能構成例を示すブロック図。
【図２３】撹乱器の機能構成例を示すブロック図。
【図２４】証明付き部分復号器の機能構成例を示すブロック図。
【図２５】部分復号器の機能構成例を示すブロック図。
【図２６】部分復号証明生成器の機能構成例を示すブロック図。
【図２７】証明付き固定部分復号器の機能構成例を示すブロック図。
【図２８】証明付き置換撹乱部分復号器の機能構成例を示すブロック図。
【図２９】完全置換網の構成例を示すブロック図。
【図３０】完全置換網を拡大させる手法の例を示すブロック図。
【図３１】置換サーバの入力リストを検索する処理例を示す流れ図。
【図３２】置換サーバの入力リストを検索する他の処理例を示す流れ図。
【図３３】Ａは更に他の検索処理方法において掲示板に公開される置換サーバの信頼性の判定結果を示す表、Ｂはその検索方法において各置換サーバがレジスタに保持する信頼度情報の例を示す図。
【図３４】置換サーバの入力リストを検索する更に他の処理例を示す流れ図。
【図３５】この発明による匿名通信路の他の実施例を示すブロック図。
【図３６】置換網のＪ段目における置換処理手順のＪの値による処理の選択手順を示すフロー。
【図３７】図３６における処理１の手順を示すフロー。
【図３８】図３６における処理２の手順を示すフロー。
【図３９】図３６における処理３の手順を示すフロー。
【図４０】記録媒体からこの発明による証明付置換撹乱部分復号方法のプログラムを読み出して証明付置換撹乱部分復号を実行するコンピュータシステムの概念図。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a verifiable anonymous communication path used for performing secret balloting in a telecommunications system.systemIn particular, the present invention relates to an anonymous communication path that can be efficiently realized, a method for implementing the same, and a recording medium on which the method is recorded.
[0002]
[Prior art]
First, the anonymous communication path will be described. Generally, each server can identify the user connected to the server, so that it can know which user is transmitting which information, and there is no anonymity in the communication path between the user and the server. MIX-NET has been proposed as a means for realizing an anonymous communication path by a telecommunication system irrespective of the physical configuration. In MIX-NET, L servers U₁, ..., U_LIs a system that is serially connected by a registered communication path.
[0003]
If this is implemented using the RSA function, the i-th server will have a large prime p_i, Q_iFor n_i= P_i・ Q_iAnd e_i・ D_i= 1 (mod LCM (p_i-1, q_i-1)) is satisfied (d_i, N_i), (E_i, N_i) Are the decryption key and the encryption key, respectively. In the encryption of the message m by the RSA, first, a random number r is selected, and m and r are combined to make m‖r. Next, M: = (m‖r)^dimod n_iTo obtain an encrypted message M. In the following, the server U_iEncryption key (e_i, N_iThis encryption procedure using_iWrite (m, r).
[0004]
j-th user is the message m to be sent_jTo
M₁: = E₁(E₂(… (E_L(M_j, R_jL),…), R_j2), R_j1)
, The encryption keys (e_i, N_i), I = 1, 2,..., L and L random numbers r_j1, R_j2, ..., r_jLServer U₁Send to
Server U₁Is an encrypted message M from multiple users₁, M₂,. . . After gathering, these are keyed (d₁, N₁) To decrypt each message m_jE corresponding to₂(… (E_L(M_j, R_jL),…), R_j2) And r_j1Get. Server U₁Is the E obtained from each encrypted message₂(… (E_L(M_j, R_jL),…), R_j2), J = 1, 2,. . . Are replaced at random, and the server U₂Send to At this time, the server U₁Is each message m_jRandom number r attached to_j1Server U₂Each E sent to₂(… (E_L(M_j, R_jL),…), R_j2) Is the server U₁Encrypted message M input to₁, M₂,. . . It is possible to make it impossible to determine which of these is the decoding result.
[0005]
Hereinafter, server U₂, ..., U_LRepeats the same processing. Finally server U_LIs each message m_jPublish. At least one server U_iIs a random number r_jiAnd the order of replacement is kept secret so that each user can₁And the server U_LThe connection with the message output by is hidden and functions as an anonymous communication path.
According to the above conventional method, even if each server does not perform a given operation and outputs an incorrectly calculated result or a result that is replaced with an original one, anyone can verify that the output is incorrect. Can not.
[0006]
As a first method for enabling verification, for example, "Universally Verifiable Mix-net with Verification Work Independent of the Number of Number of Mix-servers" proposed by Masayuki Abe, and a method of "98-YR-YR" is proposed on May, 1998, and a method of "YYYYYYYYYYYYYYY", CR, YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYER | YYYYYYYYYYYYYYYYYYYYER | YYYYYYYYYYYYYYYYYYYYYA In the first method that enables the verification, for example, "Universally Verifiable Mix-net with Verification Work Independent of the Number of Number of Mix-servers" proposed by Masayuki Abe, and a method of "98-YYR", which is proposed in May, 1998, is a method of U-R. That is, the server group first executes the replacement process, and mutually proves and verifies that the output of each server is correct. After that, a decryption process is executed, and the output of the decryption process of each server is mutually proved and verified. The problem with this method is that proof and verification performed by each server require a lot of computational cost. For example, in the replacement process, the input I₁, ..., I_NIs randomized, and the result of random replacement is₁, ..., O_NThen, to prove that this output was processed in the correct procedure without showing the random element being processed, do the following: I₁, ..., I_NIs disturbed in the same manner, is replaced randomly, and the result is₁, ..., O '_NAnd At this time, if a randomization procedure that makes the isomorphism hold is used, O '₁, ..., O '_NIs O₁, ..., O_NCan be considered as the result of randomization for Here, the verifier randomly selects a challenge of 0/1 and passes it to the prover. When the challenger is 0,₁, ..., I_N｝ → ｛O ’₁, ..., O '_NDisclose all the random elements used in the replacement / randomization process of｝. Also, when the challenge is 1, $ O₁, ..., O_N｝ → ｛O ’₁, ..., O '_NPublish a random element corresponding to the randomization process of｝. If a random element is obtained, all processing procedures can be deterministically reproduced, so that the verifier can verify that the input / output relationship is correct. The probability that the prover cannot detect the fraud by the prover is equal to the probability that the prover guesses and applies the challenge, and is. 1/2)^kThe correctness of the process is proved and verified with the error probability of. Thus, the overall efficiency at N inputs is proportional to Nk. In order to secure a high degree of reliability, k is generally set to about 80.
[0007]
As a second method for enabling verification, for example, although application to an anonymous communication channel is not described, R. Cramer, I .; Damgard, B .; Schoenmakers, Proofsof Knowledge and Simplified Designed of Witness Hiding Proofs, Proc. of Crypto '94, LNCS 839, pp. According to the method shown in 174-187, Springer-Verlag, the proof for the permutation of N inputs is N²  Calculation cost. The outline is shown below. First, I₁The result of randomizing is O₁  , Then, using the zero-knowledge dialog proof,₁And O₁  Can be proved without revealing the random element used for the randomization. In such a zero-knowledge dialog proof,
1. The prover sends a random message T called a commitment to the verifier,
2. The verifier sends a random value C called a challenge to the prover,
3. The prover sends a value Z satisfying a certain verification formula to the verifier based on the commitment T and the challenge C.
The verifier executes (T, C, Z, I₁, O₁) Satisfies a predetermined verification equation,₁And O₁  Verify the validity of the relationship. In such a proof system, if the prover does not know the value of C before creating T, returning a value of Z satisfying the verification equation is₁And O₁  Can only be done if the relationship is legitimate. However, on the other hand, if the prover knows the value of C in advance, then I₁And O₁  Can be obtained even if the relationship is not valid. Using this fact, I₁Is O₁, ..., O_NCan be shown to be valid for any one or more of. First, the prover is C₂, ..., C_NAnd the corresponding Z₂, ..., Z_NIs randomly selected. Then, for i = 2,..., N, (T_i, C_i, Z_i, I₁, O_i) So that satisfies the given verification formula_iDetermine the value of Furthermore, T₁Choose randomly. After this preparation,
1. The prover gives the verifier T₁, ..., T_NSend,
2. The verifier sends a randomly selected C to the prover,
3. Prover is C₁= C (+) C₂(+) ... (+) C_NLike C₁  , And (T₁, C₁, Z₁, I₁, O₁) Is a value Z such that satisfies the validation equation₁And calculate Z₁, ..., Z_NAnd C₁, ..., C_NTo the verifier,
Perform the following procedure. Here, (+) means exclusive OR for each bit. The verifier checks (T_i, C_i, Z_i, I₁, O_i) Satisfies a predetermined verification formula, and furthermore, C = C₁(+) ... (+) C_NIt suffices to check that Since the prover does not know the value of C in advance, at least one C_iMust be a value that cannot be manipulated by the prover.₁Is at least one O_iCan be confirmed to be a legitimate relationship.
[0008]
[Problems to be solved by the invention]
According to this method, I₁→ O₁or… orO_NTo indicate₁→ O₁  N times as much proof and communication cost as the proof to show the relationship of₁, ..., O_N｝ → ｛O ’₁, ..., O '_NThe efficiency indicating｝ is N²Is proportional to Therefore, there is a problem that the data processing amount becomes enormous when the number of inputs N increases.
As described above, according to the above conventional method, Nk or N²  Is inefficient because a calculation amount and a communication amount proportional to are required.
[0009]
SUMMARY OF THE INVENTION An object of the present invention is to provide a method and apparatus for efficiently proving and verifying that the output of each server is obtained by performing an appropriate process on an input and then replacing the order with a smaller amount of computation and communication amount. It is to provide.
[0010]
[Means for Solving the Problems]
The verifiable anonymous communication channel according to the present invention is:
The input of n smaller than N, n is an integer of 2 or more is randomly permuted, and n outputs are output by disturbing using secret information, and the n inputs are output to any verifier. A unit replacement processing means for performing a process of proving that the secret information and the random permutation corresponding to the n outputs do exist by using a zero-knowledge proof without revealing the used secret information and the random permutation;
First repetition means for executing processing by the unit replacement processing means for each of n inputs by n units to obtain N outputs;
The N messages are processed as the initial input by the first repetition means to obtain the N outputs, and the N outputs are used as the N inputs to determine the first repetition means in advance. A second repetition means for obtaining N permuted and disturbed output messages corresponding to the N messages on a one-to-one basis by repeatedly executing the number of times;
And
[0011]
A verifiable anonymous communication method according to the present invention and a program recorded on a recording medium for performing the method include the following steps:
(A) n less than N, n is an integer of 2 or more, random output is replaced, and n outputs are output by disturbing using secret information, and n outputs are given to any verifier. Performing a process of proving that the secret information and the random permutation that correspond to the input of the n outputs and the random permutation do exist by zero-knowledge proof without revealing the secret information and the random permutation used;
(B) performing the processing of step (a) on n inputs for n inputs to obtain N outputs,
(C) performing the processing of step (b) on the N messages as an initial input to obtain the N outputs, and using the N outputs as the N inputs to the first repetition means; By repeating the execution a predetermined number of times, N displaced and disturbed output messages corresponding to the N messages on a one-to-one basis are obtained.
[0012]
BEST MODE FOR CARRYING OUT THE INVENTION
According to the present invention, instead of performing proof and verification for randomization and random permutation processing on the entire input, the input is divided into a small number, and the validity of the input / output relationship is verified and verified for each of the divided parts. To do.
For example, a plurality of two-input two-output selector switches (switches capable of switching between input and output or output in the same order) are arranged in a grid pattern, and the output of each stage is By connecting the input of the next stage according to the rules, 2^LIt is known that a permutation network that can cover all permutations for a number of inputs can be configured (A. Waksman, “A Permutation Network”, Journal of the ACM, Vol. 15, No. 1, January 1968, pp. 159-163). FIG. 1 shows the configuration of a permutation network 10 for four inputs. In FIG. 1, the changeover switch SW1 is connected to the (O₁₁, O₁₂) = (I₁₁, I₁₂) As input or output (O₁₁, O₁₂) = (I₁₂, I₁₁) And output the result. Similar processing is performed for the other switches SW2 to SW5. As shown in FIG. 1, by using a combination of five changeover switches, four inputs can be used.²= 16 possible permutations can be realized. Such a permutation network will be referred to as a complete permutation network. In general, Nlog for N inputs₂It is known that a complete replacement network can be configured by using NN + 1 changeover switches.
[0013]
Therefore, according to the present invention, a function of randomizing the input and proving the random replacement is added to each of the replacement switches SW1 to SW5 to constitute a unit switching device. By proving, the justification for the entire replacement is proved. The proof performed by each switching device uses the above-described second method. Thus, for example, if there are two inputs to each switching device, 2²= 4, the proof and verification can be executed, and the overall efficiency is 4 (Nlog₂(N−N + 1).
First embodiment
The verifiable anonymous communication channel according to the present invention is as shown in FIG.NCiphertext E₁, ..., E_NAnd an anonymous communication channel 100 that outputs the decrypted results by random replacement so that the correspondence relationship with the input is not known, and a verification terminal 200 that verifies the validity of the random replacement and the validity of the decryption. Have been. In this embodiment, the anonymous communication path 100 uses the input ciphertext E₁, ..., E_NIs received, replaced and decrypted to obtain a plaintext list Tp, information Proof necessary for verification of the replacement and decryption is generated, and sent to the verification terminal 200 together with the plaintext list Tp.
[0014]
The switching devices SW1 to SW5 are connected to the anonymous communication path 100 so as to form a complete replacement network. According to the present invention, each switching device SW performs random replacement and proves the validity of the replacement by zero knowledge proof. Proof to be done₁~ Proof₅Is output. In this embodiment, a case is shown in which the switching device does not perform decryption, transforms the input cipher, and performs the decryption by the decryption device 20 after processing by the permutation network 10. However, as in a fourth embodiment described later, The decoding process may be performed in each switching device SW. However, in the latter case, each switching device SW needs to perform zero-knowledge proof for decryption using the secret key, whereas in the former case (in the case of the first embodiment), the decryption by the decryption device 20 is performed. On the other hand, since zero-knowledge proof is performed collectively, there is an advantage that the processing amount can be reduced as a whole.
[0015]
It is assumed that two predetermined large prime numbers are p and q, and q divides p. Let Gq be a subgroup of order q in Zp, and let g be an element of Gq. In the following description, unless otherwise specified, all arithmetic operations are performed by modp. Let the decryption key of El Gamal encryption be x∈Zq and the encryption key be y: = g^xAnd The encryption key y, together with the predetermined p, q, and g, includes all the switching devices SW constituting the replacement network 10 in FIG. 3 described later, the memory 23 (FIG. 7) in the decryption device 20, and the verification terminal. 200 as common parameters. It is assumed that the decryption key x is stored only in the decryption device 20.
[0016]
Message m @ Gq^*Let E be a ciphertext of the El Gamal cryptography of E, E is a random number t∈Zp,
E: = (M, G) = (my^t, G^t)
It becomes. When the number N of inputs to the system is 4, the four ciphertexts encrypted by El Gamal encryption are₁, E₂, E₃, E₄And
FIG. 3 shows a block diagram of the anonymous communication path 100 and the verification terminal 200 for four inputs. FIG. 4 shows the configuration of each of the switching devices SW1 to SW5. 5 and 6 show the configurations of the switching unit 12 and the replacement proving unit 14 in each switching device SW. The anonymous communication path 100 includes a replacement network 10 and a decryption device 20, and the replacement network 10₁, E₂Is input to the switching device SW1, and the ciphertext E₃, E₄Is input to the switching device SW2, the two outputs of the switching device SW1 are input to the switching devices SW3 and SW4, and similarly, the two outputs of the switching device SW2 are input to the switching devices SW3 and SW4, respectively. One of the two outputs of SW4 is input to the switching device SW5, and the other output R₁, R₂Is input to the decoding device 20, and two outputs R of the switching device SW5₃, R₄Is input to the decoding device 20.
[0017]
Input ciphertext E₁~ E₄, Each of the two outputs of the switching devices SW1 to SW5 is branched and input to the replacement verification unit 30 of the verification terminal 200. The replacement verification unit 30 outputs the replacement certification output Proof of each of the switching devices SW1 to SW5.₁~ Proof₅Is also entered. Four inputs R of the decoding device 20₁~ R₄Is also branched and input to the decryption verification unit 40, and the decryption message m constituting the decryption proof output ProofD and the plaintext Tp of the decryption device 20₁, ..., m₄Are also input to the decryption verification unit 40. The verification terminal 200 includes a control unit 210 and a memory 220.
[0018]
The switching device SW includes, as shown in FIG. 4, a memory 11 holding p, q, g, and y, a switching unit 12 for simply replacing two inputs and two outputs, a random number generation unit 13, and a And a control unit 15 that controls the operation of each of the units 11 to 14. As shown in FIG. 5, the switching unit 12 includes a power multiplier 12A, a remainder multiplier 12B, and an order permuter 12C. The replacement proving unit 14 includes a power multiplier 14A, a hash calculator 14B, a remainder subtractor 14C, and a remainder multiplier subtracter 14D as shown in FIG.
[0019]
The following are the steps of the operation in the switching device SW1 (see FIG. 4).
Step 1: p, g, y are input from the memory 11 to the switching unit 12.
Step 2: driving the random number generator 13 to generate random numbers b {1, 2} and t_1,t₂∈Zq is generated and input to the switching unit 12.
Step 3: The switching unit 12 operates as follows (see FIG. 5).
Step 3-1: Drive the exponentiation operation unit 12A,
[0020]
(Equation 1)

Is calculated.
Step 3-2: Output T of exponentiation operation unit 12A₁, T₂And input I₁= (M₁, G₁), I₂= (M₂, G₂) Is input to the remainder multiplier 12B,
[0021]
(Equation 2)

Is calculated. By this exponentiation operation and remainder multiplication, secret information t₁, T₂Input message I₁= (M₁, G₁), I₂= (M₂, G₂) Is randomized.
Step 3-3: Output R of remainder multiplier 12B₁, R₂And the random number b are input to the order permuter 12C. When b = 1, the order permuter 12C outputs O₁: = R₁And O₂: = R₂And when b = 2, the output O₁: = R₂And O₂: = R₁Is output. This output is₁= (N₁, H₁), O₂= (N₂, H₂)far. The order of the input messages thus randomized is randomized by b, that is, they are randomly replaced.
[0022]
Step 4: driving the random number generator 13 in FIG.₁, W₂, E_{b '}, Z_{1b '}, Z_{2b '}Generate ∈Zq, b, t₁, T₂Is input to the replacement certification unit 14. Here, it is assumed that b 'takes a value such as b' = 2 when b = 1 and b '= 1 when b = 2. Also, p, q, g, and y are input from the memory 11 to the replacement proving unit 14.
Step 5: The replacement certification unit 14 operates as follows (see FIG. 6).
The replacement proof unit 14 has two inputs I of the switching unit 12.₁, I₂And two outputs O₁, O₂And are respectively branched and input.
Step 5-1: Drive the power multiplier 14A,
[0023]
(Equation 3)

Is calculated.
[0024]
Step 5-2: I to the hash calculator 14B₁, I₂, O₁, O₂, S₁₁, S₁₂, S₂₁, S₂₂And the output is c.
Step5-3: c and q, e_{b '}  Into the remainder subtractor 14C and output
e_b: = Ce_{b '}modq
Get.
Step5-4: e_bAnd w₁, W₂, Q, b, t₁, T₂Into the remainder power subtractor 14D,
z_1b: = W₁-E_b・ T₁modq
z_2b: = W₂-E_b・ T₂modq
Is calculated.
[0025]
Step 5-5: To prove that the replacement is valid using zero knowledge proof
Proof₁: = (E₁, E₂, Z₁₁, Z₁₂, Z₂₁, Z₂₂)
Is output.
The output obtained at the end of the permutation network 10 is R₁, R₂, R₃, R₄And At this time, each R_iTo R_i= (M '_i, G '_i), The following relationship holds.
M '_i= MF (i) y^{t '}
G '_i= G^{t '}
Here, F (*) is one of the permutation functions of {1,2,3,4} → {1,2,3,4}. That is, R_iIs a normal El Gamal ciphertext for the message mF (i), and the decryption can be performed by a normal El Gamal decryption procedure.
[0026]
As shown in FIG. 7, the decryption device 20 includes a decryption unit 21, a decryption proof unit 22, a memory 23, and a control unit 24 that controls these operations. As shown in FIG. 8, the decoding unit 21 includes a power calculator 21A and a remainder divider 21B. As shown in FIG. 9, the decryption proof unit 22 includes a random number generation unit 22A, a power operation unit 22B, a hash operation unit 22C, and a modular exponentiation subtractor 22D.
[0027]
The decoding device 20 calculates₁~ R₄Are sequentially processed as follows.
Step 1: The control unit 24 receives the input R_iAre sequentially received and input to the decoding unit 21. Also, x and p are input from the memory 23 to the decoding unit 21.
Step 2: The decoding unit 21 sends G 'to the exponentiation unit 21A as shown in FIG._iAnd x, p,
K_i: = G '_i ^xmodp
Is calculated.
[0028]
Step3: M '_i, P and the output of the exponentiation unit 21A are input to the remainder divider 21B,
m_i: = M '_i/ K_imodp
Is calculated and output as a decoding result.
Subsequently, the decryption device 20 creates a ProofD certifying that the decryption has been correctly performed by the decryption proof unit 22 as follows.
[0029]
Step 1: The decryption proof unit 22 generates a random number w∈Zq by the random number generator 22A as shown in FIG. 9 and inputs the generated random number w∈Zq to the exponentiation calculator 22B.
Step 2: The exponentiation operation unit 22B first sets T₀: = G^wmodp, then each G '_iFor T_i: = G '_i ^wmodp, and calculate T₀, ..., T_NIs input to the hash calculator 22C. In this example, N = 4.
Step 3: The hash calculator 22C sets c: = Hash (y, T₀, K₁, T₁, ..., K_N, T_N) Is calculated, and c is input to the modular exponentiation subtractor 22D.
[0030]
Step 4: The modular exponentiation subtractor 22D calculates z: = w−cx (modq), and calculates c, z, K₁, ..., K_NOutput with
At this time, ProofD: = (c, z, K₁, ..., K_N).
The verification terminal 200 first drives the replacement verification unit 30 to confirm that the replacement has been correctly performed. As shown in FIG. 10, the replacement verification unit 30 includes a power multiplier 31, a hash calculator 32, a comparator 33, and an adder 34. The replacement verification unit 30 performs the Proof by the i-th switching device SWi._iIs verified as follows.
Step 1: driving the power multiplier 31;
[0031]
(Equation 4)

Is calculated.
[0032]
Step2: S₁₁, S₁₂, S₂₁, S₂₂And I₁, I₂, O₁, O₂Is input to the hash calculator 32, and the output c is input to the comparator 33.
Step3: e₁, E₂Is input to the adder 34, and e₁+ E₂Is calculated. The result is input to the comparator 33.
Step 4: q is input to the comparator 33 and e₁+ E₂= C (modq) is checked. If the condition is satisfied, OK is output; otherwise, NG is output. The fact that the permutation has been performed correctly is verified by the zero knowledge proof without indicating the random number b that caused the permutation.
[0033]
The above-described verification is performed for all the inputs and outputs of the switching devices, and if there is a switching device that outputs a proof that it becomes NG, the switching device is regarded as having failed. If all of the above verifications are OK, then, to verify that the decryption was performed correctly,₁,…, R₄, M₁,…, M₄And ProofD. FIG. 11 shows a block diagram of the decryption verification unit 40. The decryption verification unit 220 includes a remainder divider 41, a comparator 42, a power multiplier 43, a hash calculator 44, and a comparator 45, and verifies the decryption as follows.
[0034]
Step 1: M ′ to the remainder divider 41_iAnd K_iAnd enter M '_i/ K_iAnd calculate the result as m_iAnd input to the comparator 42 for comparison. If they are not equal, the comparator 42 outputs NG and the verification result is NG. If the comparison result is OK for all i = 1,..., N, the process proceeds to the next step.
Step 2: driving the power multiplier 43 and g^zy^cAnd G '₁ ^zK₁ ^c, ..., G '_N ^zK_N ^cIs calculated and input to the hash calculator 44.
[0035]
Step 3: driving the hash calculator 44,
e: = Hash (y, g^zy^c, K₁, G '₁ ^zK₁ ^c,…, K_N, G '₁ ^zK₁ ^c)
Is calculated.
Step 4: c and e output from the hash calculator 44 are input to the comparator 45, and if both are equal, OK is output, and if they are not equal, NG is output.
If the decryption was successful,
g^zy^c= G^w-cxy^c= G^w= T₀
as well as,
G '_i ^zK_i ^c= G '_i ^w-cxK_i ^c= G '_i ^w= T_i
Holds, the output of the hash calculator 44 becomes equal to c.
[0036]
In this embodiment, the random elements used in each switching device, ie, b, t₁, T₂, W₁, W₂If all are kept secret, E_i→ m_jIs kept secret for any i and j. As described above, in the first embodiment, since the validity of the random permutation in each switching device is proved by each switching device, especially when the number N of all inputs of the anonymous communication path increases. R. The required amount of data processing is remarkably reduced as compared with the case where the validity of random replacement is proved by the method of Cramer et al.
Second embodiment
In this embodiment, a configuration will be described in which the correspondence of each input / output is concealed as a whole even when random elements in some switching devices are leaked.
[0037]
In this embodiment, as shown in FIG. 12, "replacement servers" which sequentially execute the tasks of several switching devices are used, and V replacement servers PS are used.₁,. . . , PS₄This constitutes the replacement network 10. In addition, a decryption server 20S that performs decryption is used. Hereinafter, a case will be described where V = 4 replacement servers are used and the input is 4 messages. Each replacement server PS₁~ PS₄And the verification terminal 200 is connected to the bulletin board 400. The bulletin board 400 contains a message E from an authenticated user.₁, E₂,. . . , E_NAnd the information once written cannot be erased. Also, it is assumed that anyone can read the written information. In this embodiment, as in the first embodiment, each switching device SW (FIG. 13) of each replacement server PS in the replacement network 10 does not perform decryption, but performs randomization (conversion of encryption) of input encryption and random replacement. And finally the decryption server performs decryption.
[0038]
FIG. 13 shows a block diagram of each replacement server PS. The configuration of the switching device SW in the replacement server PS is the same as that of the switching device SW in FIG. 4 except that the control unit 15 and the memory 11 are outside the switching device.
FIG. 14 shows a block diagram of the decryption server 20S. The decryption server 20S has a replacement verification unit 30S, a decryption unit 21S, and a decryption proof unit 22S, which are the same as the replacement verification unit 30, the decryption unit 21, and the decryption proof unit 22 shown in FIGS. It is. The decryption server further has a memory 23S and a control unit 24S.
[0039]
This system has four replacement servers PS₁,. . . , PS₄This is a case where two 4-input complete permutation networks are configured. FIG. 15 shows the data flow in this case. Although not shown in the figure, all data transfer between the replacement servers is performed via the bulletin board 400 as shown in FIG. That is, each replacement server PS_j  Writes the replacement output on the bulletin board 400 and replaces the replacement server PS in the next stage._{j + 1}  Reads the data from the bulletin board 400 and performs a replacement process. Substitution server PS₁Executes the work of the switching devices SW1 and SW2 in the first embodiment, and updates the processing result via the bulletin board 400 to the replacement server PS.₂Send to Similarly, the replacement server PS₂Are switching devices SW3, SW4, SW5, replacement server PS₃Are switching devices SW6, SW7, replacement server PS₄Performs the work of the switching devices SW8, SW9, SW10. As shown in FIG. 13, the number of switching devices SW actually installed in each replacement server PS is one, and the control unit 15 provides an appropriate input to realize the data flow of FIG. Alternatively, a plurality of switching devices SW may be actually installed in one replacement server.
[0040]
As shown in FIGS. 12 and 15, the replacement servers PS connected in cascade.₁~ PS₄Form at least two cascaded complete replacement networks. The output of each replacement server PS is verified by the decryption server 20S having the replacement verification unit 30S connected to the bulletin board 400 in the same manner as in the first embodiment, when the replacement Proof is verified, and when an incorrect input / output relationship is detected. It regards the replacement server as broken. In that case, the replacement server deemed to have failed is excluded and another replacement server performs the processing, or if only one replacement server has failed, the processing by the replacement server may be omitted. .
[0041]
After verifying that all the permutations are correct, the decoding server 20S outputs the output of the permutation network 10 (the last stage permutation server PS) by the decoding unit 21S._V  Is output, and the decryption proof unit 22S generates a decryption proof ProofD and writes it on the bulletin board 400. The verification terminal 200 transmits each replacement Proof written in the bulletin board 400 by each replacement server.₁~ Proool₄From the decryption result (message m)₁,. . . , M_N) And the decryption proof ProofD are verified in the same procedure as in the first embodiment.
[0042]
According to the above configuration, even if a certain replacement server is attacked and a random element is leaked, and the replacement in the replacement server becomes apparent to a third party, the remaining As long as the confidentiality of the random element in the replacement server is maintained, the entire replacement relationship is kept secret. For example, replacement server PS₁Even if the replacement relationship executed by₃, Replacement server PS₄Form a complete replacement network, any replacement relationship between input and output can be realized. Similarly, even if the replacement relationship of any one of the replacement servers is leaked, a complete replacement network is always formed by the other two replacement servers, thereby keeping confidentiality.
Third embodiment
In the third embodiment shown in FIG. 16, the decryption server 20S in the second embodiment is replaced with a plurality of decryption servers 20S.₁, ..., 20S_LAnd the same function as in the case where a single decryption server is used among a plurality of decryption servers is realized. According to this embodiment, a correct result can be obtained if at least t + 1 decoding servers 20S operate normally for a certain t <L, so that fault tolerance is improved. Further, in the case where there is one decryption server 20S 1 in FIG. 12, the decryption result can be obtained at any time when the decryption server 20S 1 starts decryption. It is possible that the contents of the result are illegally leaked. On the other hand, in the embodiment of FIG.₁~ 20S_LSince the decryption result cannot be obtained unless the processing is completed, the decryption result cannot be leaked from any of the decryption servers before publication unless at least t + 1 decryption servers cooperate with each other to perform an illegal operation. Absent.
[0043]
The system configuration excluding the decryption server is the same as that of the second embodiment. Each decryption server D_iIs a value x obtained by secretly sharing the decryption key x by a polynomial of degree t._iIs stored. That is, there is a certain t-order random polynomial F (X) ∈Zq [X] that satisfies F (0) = x (modq) and t <L._iIs x_i= F (i) is a value satisfying modq. Each decryption server 20S_jIs configured in the decoding server 20S shown in FIG._iIs stored in the memory 23S, and is the same as FIG. 14 except for the internal configuration of the decoding unit 21S. As shown in FIG. 17, the decoding unit 21S in the decoding server of this embodiment has a power multiplier 21SA, which performs the same processing as the power multiplier 21A shown in FIG.
[0044]
Substitution server PS₁,. . . , PS_VThe configuration and operation are the same as in the second embodiment shown in FIG. Each decryption server 20S_tMeans all replacement servers PS₁,. . . , PS_VWill be verified in the same manner as in the second embodiment. Last stage replacement server PS_V  From the correct replacement output R₁~ R_NAre obtained, and after the replacement verification is completed, each decryption server performs decryption. The j-th decryption server 20Sj is R₁~ R_NAre sequentially processed as follows.
Step 1: The control unit inputs R_iAre sequentially received and input to the decoding unit 21S (see FIG. 14). Also, x from the memory 23S_i, P are input to the decoding unit 21S.
[0045]
Step 2: In the decoding unit 21S (see FIG. 17), G ′ is supplied to the exponentiation unit 21SA._iAnd x_j, P and K_{j, i}: = G '_i ^xjIs calculated.
Subsequently, the decryption certifying unit 22S (see FIG. 14) provides a ProofD for certifying that the decryption has been correctly performed._jIs created by driving the decryption proof unit. The actual operation is as follows. In the decryption proof operation of the first embodiment, x is x_jAnd y for y_jIs the same as the case where The output of this proof
ProofD_j: = (C_j, Z_j, K_{j, 1}, ..., K_{j, n})
And
[0046]
The configuration of the verification terminal 200 is the same as that of FIG. However, the decryption verification unit 40 has the configuration shown in FIG. The operation of the decryption verification unit is the same as Steps 2 to 4 of the operation of the decryption verification unit in the first embodiment. If the verification for the decryption server of t + 1 or more is OK, the verification terminal outputs OK.
In this embodiment, the decryption server 20S_jOutput is K_{i, j}And each decryption result m_iPerform the following steps to obtain First, let A {1, ..., L} be | A |>It is determined to be t + 1. However, for j = j∈A, the decryption server 20S_jMust have passed the decryption verification. Now, λ_j, A is
[0047]
(Equation 5)

The interpolation coefficient is defined as Then the message m_iIs
[0048]
(Equation 6)

Can be obtained at This means that x = Σλ_{j, A}Ax_jSince modq (Σ is about j∈A) holds,
[0049]
(Equation 7)

, Which is equivalent to the decoding operation in the first embodiment.
Each of the decoding servers can execute the above calculation procedure. In that case, decryption verification may be performed in the same verification procedure as in the first embodiment.
Fourth embodiment
In the above-described second and third embodiments, each replacement server PS disturbs a plurality of input ciphertexts, and sequentially changes the order of the input and sends it to the next replacement server. The decryption server decrypts the ciphertext output by the replacement server of (1) to obtain a plaintext. It is unknown who obtained the plaintext, but it can be verified that it was correctly voted.
[0050]
In the second and third embodiments, if a replacement server that has performed an illegal process is detected, for example, if t outputs of V replacement servers are not reliable, it is necessary to recover the unauthorized process. Is considered to perform t times of unauthorized recovery processing. As the reliability of the anonymous communication channel decreases (i.e., as t increases), the time required for the unauthorized recovery processing increases, and the processing capability of the anonymous communication channel decreases.
In the fourth embodiment described below, even if the reliability of the anonymous communication path is reduced to some extent, the unauthorized recovery is efficiently performed while maintaining the function as the verifiable anonymous communication path, and the required band ( Communication speed).
[0051]
In the first, second, and third embodiments, the case where the decryption processing is not performed in each switching device SW or the replacement server and the decryption is performed collectively in the decryption device or the decryption server has been described. In the fourth embodiment, a case where partial decoding is performed in each replacement server will be described. However, in each replacement server, the input ciphertext I is converted in each replacement stage, and partial decryption is performed collectively in the final stage of replacement, thereby increasing the processing speed as compared with performing partial decryption in each replacement stage. ing.
[0052]
In this embodiment, a partial decryption process performed by each replacement server is hereinafter referred to as f, and an output sentence corresponding to an arbitrary input sentence I of the replacement server having an arbitrary secret key X is represented by f._X(I).
The partial decoding process f performed by each replacement server is limited to the following process.
・ Replaceable
F for any secret keys A and B_A(F_B(I)) = f_B(F_A(I)) holds.
-Batch decryption possible
F for any known secret keys A and B_A(F_B(I)) = f_{g (A, B)}There exists a function g (A, B) of (I), and f_A(F_BF for the calculation of (I))_{g (A, B)}The calculation of (I) can be executed at high speed.
[0053]
Under such a premise, in this embodiment, if the output of a certain replacement server is not reliable, randomization is performed using only the reliable information of the replacement server that is closest to the upstream and that has been determined to be free from unauthorized processing. The replacement / disturbance / partial decoding process is performed, and the next process proceeds without performing the compensation operation for the illegal process.
The secret key of each replacement server is secretly shared in a verifiable manner with all other replacement servers in advance, and if an untrusted replacement server is detected, each of the remaining replacement servers is replaced by the upstream trusted replacement server. Random permutation / disturbance / partial decryption processing is performed using the information, and when the processing by all the reliable permutation servers is completed, all the permuted secret keys of the unreliable permutation servers are collected and jointly restored by the permutation server. I do. A partial decryption process (compensation operation) for the information portion that is to be partially decrypted by the unreliable replacement server is performed collectively by using all the restored private keys of the unreliable replacement server. By this batch processing, even if the outputs of a plurality of replacement servers are unreliable, fraud recovery can be performed by performing only one compensation operation.
[0054]
In the fourth embodiment, in the following description, an El Gamal distributed decoding system will be described as an example of an exchangeable and collectible partial decoding process used by the replacement server. The generalized El Gamal cryptosystem is applicable as long as the above properties are satisfied (for example, elliptical El Gamal cryptosystem).
In the fourth embodiment, a description will be given of a configuration in which the correspondence of each input and output is concealed as a whole even when random elements in some replacement servers are leaked.
[0055]
In this embodiment, a permutation that performs several proved random permutations, perturbations and partial decryption tasks sequentiallySa, An anonymous communication path is configured by V replacement servers.
FIG. 19 shows an example of the system configuration of the fourth embodiment. As in the case of the embodiments of FIGS.₁~ PS_VIs connected to the bulletin board 400. In this embodiment, since each replacement server is provided with a verification function for the processing of another replacement server and a partial decryption function for the input ciphertext, the verification server and the decryption server as in the embodiments of FIGS. 12 and 16 are provided. Not. Each of the replacement servers, in addition to the replacement unit P50 corresponding to the replacement unit constituted by the plurality of switching devices SW in each of the replacement servers in the second and third embodiments, checks whether the processing of the other replacement servers is correct. And a verification unit P70 for certifying random permutation and partial decryption. Substitution server PS₁~ PS₅Replacement part P50₁~ P50₅Are cascaded through the bulletin board 400 as shown in FIG. Each replacement part P50₁~ P50₅Has a plurality of switching devices SW for performing replacement / disturbance partial decoding. The verification terminal 200 is not provided independently, but is provided in each replacement server.
[0056]
FIG. 20 shows the flow of data via the bulletin board 400 between the replacement servers in the system of FIG.₁~ PS₅Replacement part P50 in₁~ P50₅Only shows. These five replacement parts P50₁~ P50₅Is the two cascaded replacement parts P50 in this example.₁And P50₂To form one 8-input complete permutation network, and two cascade-connected permutation units P50₃And P50₄, Similarly forms one 8-input complete permutation network, and the substitution unit P505 forms an 8-input complete permutation network alone. Therefore, these three 8-input perfect permutation networks connected in cascade as a whole are formed.
[0057]
It is not necessary that all 2-input 2-output unit switching devices SW arranged on a 4 × 5 grid be switchable in order to form each 8-input complete permutation network. Even if the positional relationship is fixed, replacement of all sets can be realized by a combination of switching of the remaining switching devices. Therefore, in order to reduce the processing amount in the replacement server, such a switching device that may fix the input / output relationship does not perform the replacement process on the input data. These fixed connection switching devices are denoted by SWF. However, when the ciphertext is decrypted through a replacement network constituting an anonymous communication path, which is the object of the present invention, if the number of times the input data is subjected to decryption processing differs depending on the selected path, the decryption processing becomes complicated and inconvenient. .
[0058]
In the present invention, even in such a fixed connection switching device SWF, processes other than the replacement process (such as disturbance, partial decryption, and proof generation) are performed on the input data. In the following description, the switching device SW that performs all processes such as replacement, disturbance, partial decryption, and proof generation is called a PR partial decoder with proof, and the switching device SWF that does not perform replacement is called a fixed partial decoder with proof. . Further, permutation / randomization is simply represented by PR.
[0059]
In the embodiment of FIG. 19, the input is 8 messages, and 5 replacement servers PS₁~ PS₅And correct permutation / disturbance / partial decoding can be executed even when the processing of two of the five permutation servers is illegal. Each replacement server PS₁~ PS₅The proof-provided PR partial decoder SW of the constituent elements is configured as shown in FIG. 21 or FIG. 28, and the proof-provided fixed partial decoder SWF is configured as shown in FIG. These will be described later in detail. Each replacement server PS₁~ PS₅Each have a verifier P70. Each verifier P70 includes a PR proof verifier P70A, a partial decryption proof verifier P70B, and a PR partial decryption proof verifier P70C.
[0060]
The bulletin board 400 has a function of accepting the writing of ciphertext from an authenticated user, and the information once written cannot be erased. It is assumed that anyone can read the written information.
This system has five replacement servers PS₁~ PS₅Thus, an anonymous communication path 100 composed of three cascaded complete replacement networks 10A to 10C each having eight inputs is formed. Even if the random elements of two complete permutation networks out of the three complete permutation networks 10A to 10C are leaked, the input / output correspondence can be completely concealed by the remaining complete permutation network.
[0061]
Substitution server PS₁~ PS₅Performs data processing in a predetermined order, and each replacement server reads from the bulletin board 400 the input / output data and the certification information of the replacement server in the preceding stage. At the time of the input, the own server verifier P70 verifies the reliability of the preceding replacement server based on the input / output data and the proof information, and when an incorrect input / output relationship is detected, that is, the reliability of the output. If there is no replacement server, it is assumed that the replacement server has failed. In that case, the order is traced back until a non-illegal replacement server is found, and processing is performed using the output of the closest replacement server determined to be non-illegal.
[0062]
Each replacement server can be verified against any other replacement server, and replacement servers in which an unauthorized input / output relationship is not detected cooperate with each other to perform a compensation operation for a decoding process assigned to the unauthorized replacement server. For this purpose, all the replacement servers share in advance the secret keys of all the replacement servers by secret sharing.
As described above, each replacement server sequentially executes the tasks of a plurality of PR partial decoders with certification, and each PR partial decoder SW with certification in the substitution server is configured as shown in FIG. In addition, a permuted perturbation unit 120 with proof and a partial decoder 140 with proof are included, and the permutation perturbation unit 120 with proof is composed of, for example, a permutation disturber 121 and a perturbation proof generator 122. It consists of two certified partial decryptors 141 and 142.
[0063]
FIG. 21 shows a PR partial decryptor SW with proof that performs perturbation / disturbance processing on a two-input El Gamal ciphertext, partially decrypts using the partial information of a secret key, and outputs a perturbation perturbation decryption result and a proof of its validity. 1 shows an example of a configuration. This PR partial decoder SW with proof is used for a verifiable anonymous communication path with collective unauthorized recovery in FIG.
The operation is performed as follows in the PR partial decoder SW with proof, but steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of operations performed by a plurality of devices having the same function, the devices may be united and the operations may be sequentially performed.
[0064]
Step 1: The permuted disturber with proof 120 uses the various information in the random number information to input (M₀, G₀), (M₁, G₁) Was subjected to a perturbation-disturbing process,₀ ⁺, G₀ ⁺), (M₁ ⁺, G₁ ⁺) And proof information 0 as proof of its validity.
Step 2: The permutation-perturbed partial decoder SW with proof is (M₀ ⁺, G₀ ⁺), (M₁ ⁺, G₁ ⁺) Is output as part of the proof information.
Step 3: The fixed partial decryptor 140 with proof uses the various information in the random number information to input (M₀ ⁺, G₀ ⁺), (M₁ ⁺, G₁ ⁺) Is partially decrypted (M ′₀, G '₀), (M '₁, G '₁) And proof information 1 which is proof of its validity.
[0065]
In addition, the processing order of the permutation, the disturbance, and the partial decryption in the proof-permuted perturbation partial decoder SW can be arbitrarily selected. However, the contents of the proof information differ according to the processing order.
The replacement disturber 121 includes, for example, a displacer 121A and disturbers 121B and 121C as shown in FIG. The disturbers 121B and 121C have the same structure, and have two multipliers 121B1 and 121B2 as shown in FIG. Hereinafter, the functional configurations of these units will be sequentially described.
Disturber 121B (121C)
FIG. 23 shows an example of the configuration of a disturber 121B (121C) that disturbs the input El Gamal ciphertext in order to conceal the correspondence between input and output in the disturbance replacement unit 121 shown in FIG. Assuming that the input El Gamal cipher text is (M, G), the following expression is used for the plain text m, the public key (Y, g), the secret key X, and the random number w.
Y = g^X, G = g^w, M = mY^w
Holds. Disturbing the input ciphertext (M, G) means that a secret parameter g calculated before input of M and G by a secret random number r besides a person who performs the disturbing process.^-RAnd Y^-RAnd the multipliers 12B1 and 121B2
M '← M × Y^-R,
G '← G × g^-R
Is calculated, and (M ′, G ′) is output. The output (M ', G') is
M '= mY^wr, G ′ = g^wr
Therefore, this is an El Gamal ciphertext relating to the plaintext m, the public key (Y, g), the secret key X, and the random number wr.
[0066]
The above operation is executed by the disturber 121B, but may be executed in parallel if simultaneous execution is possible. If the execution order can be exchanged, the execution order may be exchanged. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
Displacement disruptor 121
FIG. 22 shows a two-input El Gamal ciphertext (M₀, G₀) And (M₁, G₁3) shows an example of the configuration of a perturbation disturber 121 for perturbing and displacing. The El Gamal cipher text (M, G, r) obtained by disturbing the El Gamal cipher text (M, G) with a random number r will be described as D (M, G, r). According to the secret substitution parameter B {0, 1},
When B = 0
(M '₀, G '₀) ← D (M₀, G₀, R₀)
(M '₁, G '₁) ← D (M₁, G₁, R₁)
When B = 1
(M '₀, G '₀) ← D (M₁, G₁, R₀)
(M '₁, G '₁) ← D (M₀, G₀, R₁)
Output message (M '₀, G '₀) And (M '₁, G '₁) Is output.
[0067]
The displacement disturber 121 includes a displacer 121A and disturbers 121B and 121C. The disturber 121B and the disturber 121C are configured by two multipliers 121B and 121B2 as shown in FIG. In the replacement disturber 121, operations are performed as follows, but steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
[0068]
Step 1: If the replacement parameter B is B = 0, the replacement unit 121A performs
(L₀, L₁) ← (M₀, G₀)
(L₂, L₃) ← (M₁, G₁)
And if B = 1, then
(L₀, L₁) ← (M₁, G₁)
(L₂, L₃) ← (M₀, G₀)
And
[0069]
Step 2: The disturber 121B outputs the disturbance parameter (Y^-R0, G^-R0), The input (L)₀, L₁) To disturb (M '₀, G '₀) Is output.
Step 3: The disturber 121C receives the disturbance parameter (Y^-R1, G^-R1), The input (L)₂, L₃) To disturb (M '₁, G '₁) Is output.
That is, G_iAnd G '_jB = i (+) j, where i, j {0, 1}, is subjected to disturbance processing of the output. Therefore r₀, R₁G as well as the value of^-R0, Y^-R0, G^-R1, Y^-R1The value of must also be kept secret. In FIG. 22, the disturbance is performed after the replacement, but the replacement may be performed after the disturbance.
Permutation disturbance proof generator 122
The permutation disturbance proof generator 122 in FIG. 21 proves that the perturbation perturbation 121 is operating correctly without revealing the secret information (B {0, 1} and the value of the perturbation parameter). To prove this, let b = i (+) j,
For all i, j {0, 1} where b = 0
log_Y(M_i/ M '_j) = Log_g(G_i/ G '_j)
Or for all i, j {0, 1} where b = 1
log_Y(M_i/ M '_j) = Log_g(G_i/ G '_j… (Proposition 1)
Must be indicated. For this purpose, the proof information T described below is generated from the replacement disturbance proof generator 3A._ij, W_ij, Z_ij, E_bIs calculated and output.
[0070]
The input B is a replacement parameter input to the replacement unit 121A in the replacement disturbance unit 121. Input r_j, (J {0, 1}) are random numbers for disturbance inputted to the disturbers 121B and 121C in the displacement disturber 121. Input e, R_ij(I, j {0, 1}) is a random number for proof. Input Y^Rij, G^Rij(I, j {0, 1}) is the input M_i, G_i, M '_j, G '_j(I, j {0, 1}) are proof parameters calculated before being input. These information {B, r_j, E, R_ij, Y^Rij, G^Rij呼 ぶ is called random number information RDM.
[0071]
Output e_b, T_ij, W_ij, Z_ij, ((B, i, j {0, 1}) is (M) as b = i (+) j_i, G_i) And (M '_j, G '_j) Is information for certifying the correspondence or masquerading as the correspondence.
The replacement disturbance proving device 122 performs an operation as shown in the figure. That is, i, j∈ ｛
About 0,1｝
If i (+) j = B
T_ij← Y^Rij, W_ij← g^Rij
If i (+) j = B '(B' represents the inversion of B)
T_ij← (M_i/ M '_j)^eY^Rij, W_ij← (G_i/ G '_j)^eg^Rij
If B = 0
e₀← -e + h (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
e₁← e
If B = 1
e₁← -e + h (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
e₀← e
For any i, j {0, 1},
If i (+) j = B then z_ij← R_ij-E_Br_j
If i (+) j = B 'then z_ij← R_ij
With this operation, the prover (the replacement disturbance proof generator 121) obtains the proof information VRF = Ｖe_b, T_ij, W_ij, Z_ijOutput｝.
[0072]
In this calculation, steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for multiple operations by multiple devices with the same function, unify the devices and execute the operations sequentially
You may.
PR proof verifier P70A
The PR proof verifier P70A in the verifier P70 provided in each of the replacement servers in FIG. 19 verifies that the replacement disturber 121 shown in FIG. 21 is operating correctly. That is, the proof information VRF = ｛e_b, T_ij, W_ij, Z_ijVerify｝.
[0073]
Input e_b, T_ij, W_ij, Z_ij, (B, i, j {0, 1}) are the outputs of the perturbation proof generator 122, and b = i (+) j as (M_i, G_i) And (M '_j, G '_jThis is information to prove the response in ()) or to disguise it as a response.
This verifier P70A has T_ij, W_ij, Z_ij, E_bBesides M₀, G₀, M₁, G₁  , M '₀, G '₀, M '₁, G '₁Is entered and
e₀+ E₁= H (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
Is established, and if this is not established, a false signal is output and the processing ends. Function h
Represents a one-way function.
[0074]
Then, assuming that b = i (+) j for all i, j {0, 1},
T_ij= (M_i/ M '_j)^ebY^zijAnd
W_ij= (G_i/ G '_j)^ebg^zij
Is established, and if this is not established, a false signal is output and the processing ends. Both
If both are satisfied, true is output.
E prepared in advance by an unauthorized certifier by some means_b, Z_ijUsing
T_ij← (M_i/ M '_j)^ebY^zij  ,
W_ij← (G_i/ G '_j)^ebg^zij
H (x₀, X₁,…)), E₀, E₁Either one of these is difficult to calculate in advance, so it proves Proposition 1.
[0075]
The output is an estimate of whether the perturbation perturber worked correctly and is a truth value.
In the permutation disturbance proof verifier P70A, the operations are executed as described above, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. Multiple devices with the same function
The calculation of (1) may be performed by unifying the apparatus and sequentially executing the calculation.
[0076]
Certified Perturbation Disturber 120
The permutation disturber with proof 120 is a two-input El Gamal ciphertext (M₀, G₀), (M₁, G₁  ) Was subjected to a displacement disturbance treatment (M ′₀, G '₀), (M '₁, G '₁) And a proof that the correct processing has been performed is output without revealing the secret information (zero-knowledge proof). The permutation perturbation unit 120 with proof includes a perturbation perturbation unit 121 and a perturbation perturbation proof generator 122.
In the permuted perturber 120 with proof, the operation is executed as follows, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. Multiple devices with the same function
The calculation of (1) may be performed by unifying the apparatus and sequentially executing the calculation.
[0077]
Step 1: The displacement disturber 121 receives the input (M₀, G₀), (M₁, G₁) Is the input B and the disturbance parameter g^-R0, Y^-R0, G^-R1, Y^-R1, And is subjected to a displacement disturbance treatment,₀, G '₀), (M '₁, G '₁) Is output.
Step 2: The PR proof generator 122 receives the input (M₀, G₀), (M₁, G₁) And output (M ')₀, G '₀), (M '₁, G '₁) And random number information RDM = ｛B, r_j, E, R_ij, Y^Rij, G^RijUsing｝, proof information VRF =｝ e_b, T_ij, W_ij, Z_ijOutput｝.
[0078]
Certified partial decryptor 141
21 will be described with reference to FIGS. 24, 25, and 26. FIG. The partial decoder with proof 141 includes a partial decoder 141A and a partial decryption proof generator 141B as shown in FIG. Partial decryptor 141A and partial decryption certificate generator 141B are shown in more detail in FIGS. Since the proof-provided partial decoder 142 has the same configuration as the proof-provided partial decoder 142, the description of the proof-provided partial decoder 142 is omitted.
[0079]
FIG. 25 illustrates an example of a configuration of a partial decoder 141A that partially decrypts an El Gamal ciphertext using partial information of a secret key. If the input El Gamal cipher text is (M, G),
Plain text m, public key (Y, g) and random number
M = mY^w, G = g^w
Holds.
Now Y = y × y ′ and y = g^xIt is assumed that the partial decryptor knows the value of partial information x of the secret key. The partial decryptor obtains M ′ ← M × G for the input (M, G).^-XTo calculate (M ′,
G) is output. The output is
M '= my'^w, G = g^w
Therefore, the El Gamal cipher text relating to the plaintext m, the public key (y ′, g), and the random number w
It becomes.
[0080]
The partial decoder 141A includes a power multiplier 141A1 and a multiplier 141A2. In this apparatus, calculations are performed as follows, but steps that can be performed simultaneously may be performed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, multiple operations performed by multiple devices with the same function can be performed by integrating
May be executed.
Step1: The power multiplier 141A1 uses the input -x and G to input L₀← G^-XAnd calculate L₀Is output.
[0081]
Step 2: The multiplier 141A2 receives the input M and L₀M ′ ← M × L₀Is calculated and M ′ is output.
Step 3: The partial decoder 141A outputs the input G as it is.
Partial decryption proof generator 141B
FIG. 26 shows an example of the configuration of a partial decryption proof generator 141B for certifying that the partial decoder 141A shown in FIG. 25 is operating correctly without revealing secret information. This
Y = g to prove^xWithout revealing the value of the secret key x
knows the value of x and M / M '= G^xHolds (Proposition 2)
Is shown by the zero-knowledge proof. The proof is two discrete logarithms log_gy and log_G(M / M ') equal
This is indicated by the Chaum-Pedersen protocol.
[0082]
The input R is a random number secret to anyone other than the prover, and g^RIs calculated before G is input. The partial decryption proof generator 141B includes a power multiplier 141B1, a hasher 141B2, a register 141B3, a multiplier 141B4, and a subtractor 141B5.
The hash calculator 141B2 is a device for calculating a one-way hash function h, and the specifications of the hash function are assumed to be public. In this apparatus, calculations are performed as follows, but steps that can be performed simultaneously may be performed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of operations performed by a plurality of devices having the same function, the devices are unified and the operations are sequentially executed.
Is also good.
[0083]
Step1: The power multiplier 141B1 uses the input R and G to make T ← G^RIs calculated and T is output.
Step 2: Hasher 141B2 is held in input T and register 141B3
V = g^RIs used to calculate e ← h (T, V), and e is output.
Step 3: The multiplier 141B4 uses the input e and x to perform L₀← Calculate exx and L₀Is output.
[0084]
Step 4: The subtractor 141B5 receives the input R and L₀Using s ← RL₀And outputs s.
Step 5: Output T, V, e, and s as proof information VRF to the partial decryption proof verifier P70B in FIG.
Partial decryption proof verifier P70B
The partial decryption proof verifier P70B that verifies the output of the partial decryption proof generator 141B (142B) shown in FIG. 21 verifies that the partial decryptor 141A (142A) is operating correctly. The partial decoder 141A knows the value of x and M / M '= G^xIs formed
(Proposition 2) "is determined and output.
[0085]
The output of the partial decryption proof generator 141B shown in FIG. 26 is verified according to the Chaum-Pedersen protocol. Let h be a published one-way hash function of the specification.
You. g and y are open to the public as described above.
In this device, calculations are performed as follows, but steps that can be performed simultaneously may be performed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, multiple operations performed by multiple devices having the same function
And may sequentially perform calculations.
[0086]
Step 1: The partial decryption proof verifier P70B (FIG. 19) outputs e, T, V
e = h (T, V)
Otherwise, output false and end.
Step 2: The partial decryption proof verifier P70B receives the input m, M '. For G, e, s
T = (M / M ')^eG^s
Otherwise, output false and end. This means that M '= MG^-X, S = R-ex, it can be understood that, if correct, the equal sign holds.
[0087]
Step 3: The partial decryption proof verifier P70B obtains V = y for the input V, e, and s.^eg^sOtherwise, output false and end. This means that V = g^R, Y = g^x, S = R-ex.
Step 4: The partial decryption proof verifier P70B outputs true if all verifications are established, and ends the processing.
The above is the description of the functional configuration of each PR partial decoder SW with certification as a switching device in each complete replacement network described in FIG. 20 and the verifier P70B associated therewith. Next, the fixed partial decryptor SWF with certification in the complete permutation network shown in FIG. 20 will be described.
Proof fixed partial decoder SWF
FIG. 27 shows an example of the configuration of a proof-fixed fixed partial decryptor SWF that partially decrypts a two-input El Gamal ciphertext using partial information of a secret key and outputs a decryption result and a proof of the validity of each decryption result. Represents.
[0088]
The fixed partial decryptor SWF with proof is used for performing fixed replacement and partial decryption with proof in the replacement network of FIG. 20 as described above. The fixed partial decoder SWF with proof includes a partial decoder with proof 141F and a partial decoder with proof 142F as shown in FIG. The proof-provided partial decoders 141F and 142F have the same configuration as the proof-provided partial decoder shown in FIG.
In the fixed partial decoder SWF with proof, the operation is executed as follows, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
[0089]
Step1: The partial decryptor with proof 141F receives -x and (M₀, G₀) And random number information 0 (M₀, G₀) Is partially decoded (M ′₀, G₀) And proof information 0 as proof of its validity.
Step 2: The proof-provided partial decoder 142F receives the -x and (M₁, G₁) And random number information 1 (M₁, G₁) Is partially decoded (M ′₁, G₁) And proof information 1 which is proof of its validity.
Certified partial decryptor SW
FIG. 28 shows a configuration example different from that shown in FIG. 21 described above as the certified PR partial decoder SW in FIG.
[0090]
FIG. 28 shows a two-input El Gamal ciphertext (M₀, G₀), (M₁, G₁) Was subjected to a perturbation partial decoding process (M ′₀, G '₀), (M '₁, G '₁21) and an example different from FIG. 21 of the configuration of the certified PR partial decoder SW that outputs a proof that correct processing has been performed without revealing secret information. Figure21In the example of the above, the proof for the perturbation perturbation and the proof for the partial compound are performed separately, but the difference is that the proof is performed on the result of perturbation partial decoding in FIG.
[0091]
The signed PR partial decoder SW includes a PR partial decoder 124 and a PR partial decryption proof generator 125. The PR partial decoder 124 includes a perturbation disturber 124A and two partial decoders 124B and 124C.
In the PR partial decoder SW, operations are performed as follows, but steps that can be performed simultaneously may be performed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
[0092]
Step 1: The PR partial decoder 124 receives (M₀, G₀), (M₁, G₁) Is subjected to a perturbation / disturbance partial decryption process using the input B, the disturbance parameter, and the partial information of the secret key (M ′₀, G '₀), (M '₁, G '₁) Is output.
Step 2: The PR partial decryption proof generator 125 receives (M₀, G₀), (M₁, G₁) And (M '₀, G '₀), (M '₁, G '₁) And random number information to output proof information.
In the PR partial decoder SW with proof, the order of replacement, disturbance, and partial decryption may be arbitrarily changed.
[0093]
28 is configured in the same manner as the perturbation disturber 121 shown in FIG. 22, and the partial decoders 124B and 124C are each configured in the same manner as the partial decoder 141A (141B) shown in FIG.
The permutation-perturbed partial decoder 124 performs the operation as follows, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
[0094]
Step 1: The displacement disturber 124A has parameters B and g for displacement disturbance.^-R0, Y^-R0, G^-R1, Y^-R1(M)₀, G₀), (M₁, G₁) Is output.
Step 2: The partial decryptor 124B partially decrypts one pair of information resulting from the perturbation perturbation processing using the partial information -x of the secret key (M '₀, G '₀).
Step 3: The partial decryptor 124C partially decrypts the other paired information of the result of the perturbation permutation process using the partial information -x of the secret key (M '₁, G '₁).
PR partial decryption proof generator 125
The PR partial decryption proof generator 125 in FIG. 28 shows an example of a configuration for certifying that the PR partial decryptor 124A is operating correctly without revealing secret information.
[0095]
The input B is a replacement parameter input to the replacement unit (see FIG. 22) in the replacement disturbance unit 124A._j(J {0, 1}) is a random number for disturbance inputted to the disturber (see FIG. 22) in the replacement disturber 124A, x of the input is partial information of the decryption key, and e, K₀, K₁, R_ij(I, j {0, 1}) is a random number for generating proof information, and the input g^K0, G^{K1 + ex}  y '^Rij, G^Rij(I, j {0, 1}) is the input M_i, G_i, M '_j, G '_j(I, j {0, 1}) are parameters for generating proof information calculated before input.
[0096]
Output V_b, E_b, S_b, T_ij, W_ij, Z_ij, (B, i, j {0, 1}) are given by b = i (+) j and (M_i, G_i) And (M '_j, G '_j) Is information to prove or disguise the response.
In order to directly prove that the perturbation-perturbation partial decoder 124 is operating correctly, b = 0, 1} and the value of the perturbation and decryption secret parameters are not disclosed. i (+) j
M / M 'for all i, j {0, 1} where b = 0_j= Y^rjG_i ^xAnd G_i/ G '_j= G^rj
M / M 'for all i, j {0, 1} where b = 1_j= Y^rjG_i ^xAnd G_i/ G '_j= G^rj
... (Proposition 3)
Must be indicated. For this purpose, the proof information V_b, E_b, S_b(B∈ ｛0, 1｝), T_ij, W_ij, Z_ij(I, j∈ ｛0, 1｝).
[0097]
For all i, j {0, 1},
If i (+) j = B
T_ij← y '^RijG_i ^K0, W_ij← g^Rij
If i (+) j = B '(B' is the inverse of B)
T_ij← (M_i/ M '_j)^ey '^RijG_j ^K1, W_ij← (G_i/ G '_j)^eg^Rij
Is calculated.
[0098]
Further
V_B← g^K0, V_{B '}← g^{K1 + ex}
And B = 0
e₀← -e + h (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
And e₁← e,
If B = 1
e₁← -e + h (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
And e₀← e
Furthermore, if i (+) j = B
z_ij← R_ij−e_br_j
And if i (+) j = B ′, z_ij← R_ijage
If B = 0
s₀← K₀-E₀ ^x
And s₁← K₁age,
If B = 1
s₁← K₀-E₁x
And s₀← K₁And
[0099]
The permutation-perturbed partial decryption proof generator 125 performs the operation as described above, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
PR partial decryption proof verifier P70C
The PR partial decryption proof verifier P70C in FIG. 19 verifies that the PR partial decryptor 124 shown in FIG. 28 is operating correctly. This verifier P70C verifies the output of the PR partial decryption proof generator 125 in FIG.
[0100]
The input of the PR partial decryption proof verifier P70C is e_b, T_ij, W_ij, Z_ij, (B, i, j {0, 1}), which is the output of the PR partial decryption proof generator 125 of FIG._i, G_i) And (M '_j, G '_j) Is information to prove or disguise the response. This verifier P70C first
e₀+ E₁= H (T₀₀, T₀₁, T₁₀, T₁₁, W₀₀, W₀₁, W₁₀, W₁₁)
Is calculated, and if it is not true, false is output and the process is terminated. If it is true, V is set for all b {0, 1}._b= G^sby^ebIs calculated and ascertained. If not, false is output and the process is terminated. If it is satisfied, it is assumed that b = i (+) j for all i, j {0, 1}.
T_ij= (M_i/ M '_j)^eby '^zijG_i ^sb  , W_ij= (G_i/ G '_j)^ebg^zij
Is determined by calculating whether or not is true. If not, false is output and the process is terminated. If true, true is output. Thus, the truth of Proposition 3 is determined.
[0101]
In the verifier P70C, the calculation is executed as described above, but the steps that can be executed simultaneously may be executed in parallel. Steps whose execution order can be exchanged may exchange the execution order. In addition, for a plurality of calculations performed by a plurality of devices having the same function, the devices may be unified and the calculations may be sequentially performed.
Complete replacement network 10
FIGS. 29A and 29B show an example of the configuration of the 4-input and 8-input complete replacement networks 10A and 10B, respectively.
[0102]
A complete permutation network is a plurality of PR partial decoders SW with proofs and fixed partial decoders SWF with proofs arranged in a matrix, connected in cascade, and a secret substitution parameter B of each PR partial decoder SW with proofs._iIs a network that can realize any permutation to the input by the combination of the values of The input is N El Gamal ciphertexts and the output is N ElGamal ciphertexts or N plaintexts. Further, as information for proving the validity of the replacement, the proof information of each PR partial decoder with proof and the fixed partial decoder with proof, and input / output information other than the secret key, the substitution disturbance parameter, and the random number information are output and disclosed.
[0103]
In FIG. 29A, two El Gamal ciphertexts are input, and the PR partial decryptor SW with certification and the fixed partial decryptor SWF with certification are arranged in two rows and three columns as a processor for outputting two El Gamal ciphertexts. The output of the partial decoder in each row is supplied to the partial decoder of the next column in the same row, and the output of the partial decoder in the same row is input to the partial decoder in the next column. What is indicated by a solid line block in the apparatus is a PR partial decryptor SW with certification, which permutates and disturbs two El Gamal ciphertexts and partially decrypts using partial information of a secret key, and the result of the perturbation disturbance And proof information for proving its validity, and what is indicated by the broken line block in the partial decryptor is a fixed partial decryptor SWF with proof, and this El Gamal ciphertext is Partial information Using partially decoded, and outputs the decoding result, the credentials to prove its validity. In this case, there are 4! = 4 × 3 × 2 = 24, but B_iIf the number is 5, then 2⁵= 32 kinds of arrangements are possible, and the input arrangement can be set to any of all replaceable arrangements. In other words, in the case of a 4-input array, the PR partial decoder with proof, in other words, the replacement parameter B_iCan be set if there are five processors that can set the total replacement network. On the other hand, compared to the PR partial decoder with proof, the fixed partial decoder with proof is considerably simple in configuration, that is, the amount of calculation is small, so the processor in the first row and the third column is a fixed partial decoder with proof. And This may also be a certified PR partial decoder.
[0104]
FIG. 29B shows a case where PR partial decoder SW with proof or fixed partial decoder SWF with proof is arranged in 4 rows and 5 columns, and the output is exchanged between the inner three columns where the output is input in the same row and the output is replaced. Some are entered. This configuration is a combination of two four-input, four-output complete permutation networks of FIG. 29A, as indicated by the broken lines in the figure.
B in column i of secret permutation parameter_iWithout knowing the value of, it is not possible to estimate what kind of substitution was performed. That is, M '₀, ..., M '₃Is B_iIf you do not know the combination of the values of, you cannot know who sent the sentence. In order to correctly decode in both of FIGS. 29A and 29B, each partial decoder in the same column (i-th column) has the same decryption key x._ihave.
Complete replacement network 10C
FIG. 30 shows an example of the configuration of a 2N-input complete permutation network 10C. The principle is A. Waksman. A permutation network. Journal of the ACM, 15 (1): 159-163, 1968. by.
[0105]
Since the permutation network 10C is composed of only the N-input perfect permutation networks 10C1 and 10C2 and the two-input perfect permutation network (PR partial decoder with certification) SW, four inputs and eight inputs are obtained by using the two-input perfect permutation network. , ... 2ⁿA complete permutation network of the input can be constructed. In the figure, two N-input perfect permutation networks are provided, and N permutation partial decoders with N 2-input / 2-output proofs are provided at the input stage, and (N-1) 2-input 2-output proofs are provided at the output stage. And a fixed partial decryptor SWF with proof. The configuration of FIG. 29B is a case where a four-input complete permutation network is used as the N-input complete permutation network in the configuration of FIG.
[0106]
Therefore, a function of performing a partial decryption process using only the permuted disturbance partial decoder with proof and the fixed partial decoder with proof is provided.ⁿA complete permutation network of the input can be constructed.
N (= 2ⁿThe components required for the complete permutation network of the input are the permutation-perturbed partial decoder Nlog with proof₂N−N + 1 and fixed partial decoders with proof (N−1), and the total number of stages (the number of columns) is 2N log₂N-1 stages.
Verifiable anonymous communication channel 100 with batch fraud recovery
FIG. 20 shows an example of the configuration of a verifiable anonymous communication path with 8 inputs, 2 secret leakage resistances, 2 failure resistances, and batch unauthorized recovery. Verifiable anonymous communication path 100 with collective fraud recovery is replaced server PS₁~ PS₅, A replacement server 18C, a replacement server 18D, a replacement server 18E, and a replacement server 18F, which are connected in cascade. The t secret leak tolerance is the replacement secret information B of at most t devices among V (> 2t) replacement servers in total._iThis means that even if is leaked due to an attack or the like, the correspondence between input and output is completely hidden.
[0107]
The verifiable anonymous communication path 100 with the collective unauthorized recovery includes three completely replaced networks 10A, 10B, and 10C, and does not have a replacement server across the completely replaced networks._iLeaks, there is always one complete replacement network that does not include the two replacement servers, and all the secret information of the complete replacement network is concealed. The correspondence of input / output of the anonymous communication channel 100 is also hidden. Therefore, in the anonymous communication path shown in FIG.₁~ PS₅Therefore, the verifiable anonymous communication path 100 with collective unauthorized recovery has two secret leakage resistance.
[0108]
In general, when the verifiable anonymous communication path 100 with collective fraud recovery has a network in which t + 1 complete replacement networks are connected in series, and this network is divided into V, and each of the divided parts is used as a replacement server, If the network is divided so that none of the replacement servers straddle the two completely replaced networks, the verifiable anonymous communication path with collective unauthorized recovery has t-secret leakage resistance.
The t failure tolerance is a verifiable anonymous communication path with a collective unauthorized recovery that can finally output correctly by unauthorized recovery even when the operation of at most t of V (> 2t) replacement servers is incorrect. Means that.
[0109]
Each replacement server performs secret sharing so that the secret key can be restored if t + 1 or more replacement servers are gathered by a secret sharing method that can verify its own secret key to other replacement servers. For example, a secret key x for hiding a coefficient of order 0_iAnd a t-order polynomial f relating to z for which another coefficient is determined by a secret random number_iThe value x of z = j in (z)_ij= F_iIf (j) is distributed to the j-th replacement server, t + 1 or more xs for one i_ijAnd the corresponding j are collected, a Lagrange interpolation formula for any t + 1 different j sets J in it
[0110]
(Equation 8)

Using x_i= F_iThe secret key can be restored as (0). Such a key secret sharing and restoring method is described in, for example, "Cryptography, Zero Knowledge Proof and Number Theory", published by Kyoritsu Shuppan Co., Ltd. on December 20, 1995, edited by Tatsuaki Okamoto and Kazuo Ota, pp. 62-63.
[0111]
As shown in FIG. 19, each replacement server PS includes a verifier 21 for verifying the validity of input / output of another device. Each time a permutation server PS outputs a ciphertext, it checks its validity and publishes the result on a bulletin board.
Each replacement server uses the last output that is found to be correct as a result of the inspection as its own input, calculates the product of all public keys not yet used for partial decryption processing for that input, and uses this for the disturbance processing A perturbation partial decoding process is performed as a parameter.
[0112]
After the final output is completed, all of the replacement servers operate correctly, that is, all the devices are convinced that all the devices are correct, and if all the replacement servers output, the final output is a plain text column (list).
In cases other than the above, when three (t + 1) or more replacement servers that have performed reliable input and output finally collect after the final output, all replacements determined to be not operating correctly are performed. The secret key of the server is restored by the key secret sharing restoration method, and the total sum is made public as x '.
[0113]
Finally, each of the mutually reliable replacement servers decrypts the finally reliable output by using the secret key x ＾ to obtain a public text string and publish it. The fact that the secret key x 'can be used for decryption is based on the "grouping possible" condition. If three (t + 1) or more replacement servers that have finally performed reliable input and output do not collect, unauthorized recovery cannot be performed. Fail.
Whether the permutation server is reliable is verified by using the input, output, and proof information of the permutation server, by verifying the above-described PR partial decoder with proof, the permutation disturber with proof, and the fixed partial decoder with proof. It is sufficient to verify all the constituent processors. The processing for the replacement server is performed in the order of the cascade connection, and the input is the output of the immediately reliable replacement server. The following is an example of a search technique for determining which replacement server's output should be used as input. This search is performed by the determination unit P60 in each replacement server.
[0114]
In addition, the input list to the anonymous communication path 100 is L₀And the i-th replacement server PS_i  Output list of L_iAnd j-th replacement server PS_j  Input list L_jCan be obtained, for example, as shown in FIG. j-th replacement server PS_j  If the position of the replacement server immediately before performing the correct processing is represented by t, first, t = 0 and i = 1 are initialized (S1), and it is checked whether i <j (S2). If i is smaller than j, i-th replacement server PS_i  Certificate information VRF_iIs the input list L_tAnd output list L_iIt is checked whether the one-to-one correspondence has been proved (S3). If it has been proved, t = i is set (S4), i is incremented by 1, and the process returns to step S2 (S5). If the correspondence of 1 has not been proved, the process proceeds to step S5. If i is equal to or greater than j, the process is terminated, and the replacement server PS is determined from the value of t at that time._t  Output list L_tBecomes the required input list.
[0115]
The search of the input list shown in FIG. 31 can reduce the processing as follows. In FIG. 31, the number t from which replacement server the input list determined by each replacement server is registered in the bulletin board, and between the steps S2 and S3, as shown in FIG._i  Is the output list L of the trusted replacement server_t(S6). If the replacement server PS to be verified_i  Output list L of the replacement server which is reliable_tIs not input, the replacement server PS can be used without performing the verification in step S3._i  Can be determined to have performed an illegal process. Therefore, as shown in FIG._i  Is the list L_tIs not entered, the replacement server PS_i  Input list L_tAnd output list L_iMove to step S5 without verifying the correspondence_t, The replacement server PS_i  Step S3 is executed for. As a result, the processing amount can be reduced as compared with the case shown in FIG. Substitution server PS₁~ PS_j-1Is completed (if i ≧ j), the value of t is registered in the bulletin board in step S6, and the process ends.
[0116]
Another example will be described. In this example, each replacement server PS_i  , I = 1, ..., V is higher than thatFlowIt is assumed that, for each of the pre-replacement servers, the result of determination as to whether or not the server is reliable is registered in the bulletin board as shown in FIG. Also, each replacement server PS_jIs above myselfFlowEach replacement server PS_k(1<k <j) is used as the reliability information R_k= Register true or false. FIG. 33B shows the replacement server PS._j  2 shows an example of the reliability information recorded in the register No. 1. In FIG. 33A, the j-1st replacement server is already above each of them.FlowIn the judgment results for all the replacement servers, the mark ○ indicates reliability, and the mark × indicates no reliability.
[0117]
Each replacement server is above itselfFlow, The output of the nearest reliable replacement server is required as input, so the j-th replacement server PS_j  Is the first replacement server PS₁  33A, the second replacement server is determined to be unreliable, but referring to the bulletin board as shown in FIG. 33A, the i-th replacement server determines that the second replacement server is reliable. Has been determined. Therefore, the j-th replacement server can determine that the i-th replacement server is not reliable. In such a case, the j-th replacement server can omit the verification of the input / output correspondence for the i-th replacement server. Similarly, if the j-th replacement server determines, for example, the third replacement server to be reliable, but the i-th replacement server determines that the third replacement server is unreliable (see FIG. 33A), the j-th replacement server can also determine that the i-th replacement server is unreliable, and also in this case, the j-th replacement server is the i-th replacement server. It is possible to omit the verification of the input / output correspondence to The search process of the input list by the j-th replacement server using this method will be described with reference to FIG.
[0118]
Replacement server PS shown in FIG._j  In the search processing of the input list, the replacement server PS is first set to t = 0 and i = 0._j  R for k = 1,..., J−1_kAre true (S1). If i is smaller than j (S2), the register shown in FIG. 33B is referred to, and the reliability information R of the k = i-th replacement server is referred to._iIs checked (S3), and R_iIs true, then (R_iIs set to true), the replacement server PS_i  Certificate information VRF_iIs the list L_tAnd list L_iIt is checked whether the one-to-one correspondence has been proved (S4), and if it is proved correctly, t is updated to i (S5). In this case, the replacement server PS of k = i + 1,..., J−1_k  Is the replacement server PS_i  Output list L_iShould be determined to be correct, that is, the replacement server PS i is reliable._i  Replacement server PS that has determined that is not reliable_k  If there is, as shown in FIG. 33B, the reliability information R for the replacement server_kIs changed to false (S7), then i is incremented by 1 and the process returns to step S2 (S7).
[0119]
List L in step S4_tAnd list L_iIf it is not possible to prove that there is a one-to-one correspondence, the process proceeds to step S8, where the bulletin board is referred to, and if k = 1,._k  Server PS_i  If there is a replacement server that is determined to be reliable, the reliability information R for that replacement server_kIs changed to false, i is stepped in step S7, and the process returns to step S2. Accordingly, in the subsequent loop processing, i is determined in step S2, and the reliability information R of the register is determined in step S4 or S8._kIs replaced with the number i = k of the replacement server, the reliability information R of the server in the register is stored in step S3._kIs false, the process proceeds to step S8 without performing the verification in step S4.
[0120]
If i exceeds j in step S2, the list L at that time_t, And all the replacement servers PS_k  Reliability information R about_kIs published (registered on the bulletin board) and the process ends.
As described above, the reliability information R, which is each inspection result,_kThe amount of processing required for searching for an output list to be input can be reduced by using.
In FIG. 20, each replacement server PS₁~ PS₅, A permutation-disturbed partial decoder with proof alone or a fixed partial decoder with proof is used. However, each replacement server PS₁~ PS₅Can be configured using a permuted perturber with proof and a fixed partial decoder with proof. For example, as shown in FIG. 35, the permutation-perturbed partial decoder with proof in FIG. 20 is replaced with a permuted perturber with proof, and the part of the fixed partial decoder with proof in FIG. After the last stage (column) of the server, a certified partial decoder may be provided for each row.
[0121]
Also, for example, the replacement server PS in FIG.₁  , The processors in the first row (first column) of each row may all be changed to the certified permutation disturbers. In short, the replacement server only needs to perform the proof replacement perturbation processing as a whole and the proof partial decryption processing by at least one stage (one column) of processors. Note that if t fault tolerance does not matter and only t secret leakage tolerance is required, t + 1 complete replacement networks configured without duplicating replacement servers are sufficient, and the condition of V> 2t is not required. .
[0122]
In each of the embodiments of the present invention described above, the replacement network forming the anonymous communication channel according to the present invention may be configured by connecting two-input / two-output unit switching devices SW (SWF) according to rules. N = 2^kIn the case of input, the unit switching device SW (SWF) is set to 2^k-1In a permutation network arranged in (2k-1) stages one by one, one data processing device takes in the processing results from the preceding stage in each stage, executes processing for 2k-1 units of the unit switching device SW, and performs processing. The results may be sequentially output, or one processor may sequentially execute the processing to be performed by the (2k-1) data processors in the (2k-1) stages.
[0123]
For example, when one data processing device is provided for each of the (2k-1) stages, the J-th processing device has two data processing devices from the preceding stage.^kEl Gamal ciphers (M, G), which are the processing results, are sequentially taken in, and the ciphers (M ′, G ′) obtained by performing the above-described replacement, disturbance, and partial decryption are sequentially output in accordance with a predetermined rule. . This processing procedure will be described with reference to FIGS.
FIG. 36 shows which one of the J-th stage processing apparatus belongs to the group of the 1st to k-1th stage, the group of the kth to 2k-2th stage, and the last 2k-1th stage. And which of process 3 is to be executed. N = 2^kIt is assumed that there are N output registers that hold N processing results corresponding to the output terminal positions.
Step S1: It is determined whether or not J = 2k−1, that is, whether or not it is the last stage. If it is the last stage, the process proceeds to the execution of the process 3 (FIG. 39). If not, the process proceeds to step S2.
Step S2: It is determined whether or not J−k ≧ 0, that is, whether J is a value of k to 2k−2, and if so, the process proceeds to the execution of the process 2 (FIG. 38). If not, the process proceeds to step S3.
Step S3: J is a value of 1 to k-1, and the processing shifts to execution of processing 1 (FIG. 37).
[0124]
FIGS. 37, 38, and 39 show flows for executing the processing 1, the processing 2, and the processing 3, respectively. Here, (L_J-1[2i], L_J-1[2i + 1]) are ciphertexts (M) of two output positions [2i] and [2i + 1] to be subjected to random replacement in the (J-1) th stage._2i, G_2i), (M_{2i + 1}, G_{2i + 1}). lrot (u, v) means that the data u is converted by giving 1 bit left rotation to the v bit data from the LSB side in the binary data u. For example, if u = 10110 in a binary representation and v = 3, lrot (u, v) rotates u the right three bits 110 of 10110 by one bit to the left to become 101, so that u becomes 10101 Convert to Similarly, rot (u, v) converts data u by rotating v-bit data to the right by one bit from the LSB side of binary-expressed data u.
[0125]
bit [x, y] represents the value of the lower y bits of x expressed in binary. For example, if x = 1001 and y = 4, bit [x, y] = 1.
Processing 1 shown in FIG. 37 is processing in the permutation stage of J = 1,..., K−1. In these stages, all pairs of input ciphers (L_J-1[2i], L_J-1[2i + 1]) is subjected to random permutation, disturbance and partial decoding.
Step S11: Initially set to i = 0.
Step S12: Two ciphers (L1) to be subjected to the 2i-th and (2i + 1) -th random replacement from the J-1st stage_J-1[2i], L_J-1[2i + 1]) is subjected to the permutation perturbation partial decryption processing with proof, and the processing results are stored in the [rot (2i, k-J + 1)] th and [rot (2i + 1, k-J + 1)] th output registers, respectively. .
Step S13: Increment i by one.
Step S14: i ≦ 2^k-1  Is determined, and if so, there is still unprocessed data, and the process returns to step S11. If not, the data processing in the J stage ends.
[0126]
Processing 2 shown in FIG.J = K, … , 2k-2  Of the input stage (L_J-1[2i], L_J-1[2i + 1]) is processed as follows.
Step S21: Initially set to i = 0.
Step S22: It is determined whether or not bit [i, J−k] = 0, and if YES, the process is performed by the fixed replacement device SWF. If NO, the process is performed by the replacement device SW. Move to step S24.
Step S23: The 2i-th and (2i + 1) -th pair of ciphers (L_J-1[2i], L_J-1[2i + 1]) are stored in the [lrot (2i, J−k + 2)] and [lrot (2i + 1, J−k + 2)] th output registers, respectively.
Step S24: The 2i-th and (2i + 1) -th pairs of ciphers (L_J-1[2i], L_J-1[2i + 1]) is subjected to the permutation-perturbed partial decryption processing with proof, and the processing results are stored in the [lrot (2i, J−k + 2)]-th and [lrot (2i + 1, J−k + 2)]-th output registers, respectively. . Step S25: Increase i by one.
Step S26: i ≦ 2^k-1  Is determined, and if so, there is still unprocessed data, and the process returns to step S22. If not, the data processing in the J stage ends.
[0127]
Processing 3 shown in FIG. 39 is processing in the last stage J = 2k−1, and the pair of input ciphers (L_J-1[2i], L_J-1[2i + 1]) is executed as follows.
Step S31: Initially set to i = 0.
Step S32: It is determined whether or not bit [i, J−k] = 0, and if YES, the process is performed by the fixed replacement device SWF. If NO, the process is performed by the replacement device SW. Move to step S34.
Step S33: The 2i-th and (2i + 1) -th pairs of ciphers (L_J-1[2i], L_J-1[2i + 1]) are stored as they are in the 2i-th and (2i + 1) -th output registers, respectively. Step S34: The 2i-th and (2i + 1) -th pairs of ciphers (L_J-1[2i], L_J-1[2i + 1]) is subjected to the perturbation partial decryption processing with proof, and the processing results are stored in the 2i-th and (2i + 1) -th output registers, respectively.
Step S35: Increase i by one.
Step S36: i ≦ 2^k-1  Is determined, and if so, there is still unprocessed data, and the process returns to step S32. If not, the data processing in the J stage ends.
[0128]
When the processing of all (2k-1) stages is executed by one processing device, the processing procedures of FIGS. . . , 2k-1.
The perturbation decoding process according to the present invention described above may be performed by recording the program on a recording medium as a computer program, and reading and executing the program.
Both of the above-described encoding device and decoding device can also perform their respective functions by causing a computer to decode and execute a program.
[0129]
FIG. 40 shows a configuration in a case where a computer performs a permutation-perturbed partial decryption method with certification in a permutation network forming an anonymous communication channel according to the present invention. The computer 80 includes a CPU 81, a RAM 82, a ROM 83, an input / output interface 84, and a hard disk 85 connected to each other via a bus 88. A basic program for operating the computer 80 is written in the ROM 83, and a program for executing, for example, the above-described substitutive perturbation partial decryption method with proof by one substitution server according to the present invention is stored in the hard disk 85 in advance. For example, at the time of encoding, the CPU 81 loads the encoding program from the hard disk 85 into the RAM 82, processes the encrypted voting sentence fetched from the bulletin board 400 via the interface 84 according to the program, and decrypts the encrypted voting via an anonymous communication path. 84 to the bulletin board 400.
[0130]
As a program for executing the permutation-perturbed partial decryption method with certification according to the present invention, a program recorded on an external disk device 87 connected to an internal bus 88 via a drive device 86 may be used. The recording medium on which the program for executing the method according to the present invention is recorded may be any form of recording medium such as a magnetic recording medium, an IC memory, and a compact disk.
[0131]
【The invention's effect】
According to the present invention, by taking advantage of the fact that the replacement of a small number of inputs is relatively easy, the replacement of a small number of inputs is repeated to form the entire replacement. , It is possible to reduce the amount of calculation and the amount of communication for the proof against the replacement to the amount proportional to Nlog 2N, and to construct an efficient verifiable anonymous communication channel.
[0132]
Conventionally, each time one fraudulent (failure) is detected by one replacement server, the compensation processing is performed. Therefore, if there is a fraud in t devices, the compensation processing must be performed t times. According to the above, even when t outputs out of V replacement servers become unreliable, processing is performed by bypassing the unreliable (illegal or faulty) device and finally recovered by the key secret sharing recovery method. Plaintext can be obtained using the key, and the fraud recovery is completed by performing the fraud recovery processing only once.
[0133]
Further, according to the present invention, it is possible to recover fraudulently t times faster than in the case where fraudulent recovery is conventionally performed t times, and it is possible to efficiently guarantee a band in a verifiable anonymous communication path.
Furthermore, by constructing t + 1 complete replacement networks in series without using replacement servers in duplicate, resistance to t secret leakage can be obtained.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a conventional 4-input permutation network.
FIG. 2 is a block diagram showing an entire apparatus to which the present invention is applied;
FIG. 3 is a block diagram showing a configuration of an anonymous communication path for four inputs and a configuration of a verification terminal.
FIG. 4 is a block diagram showing a configuration of a switching device SW in FIG. 3;
FIG. 5 is a block diagram showing a configuration of a switching unit 12 in FIG. 4;
FIG. 6 is a block diagram showing a configuration of a replacement proving unit 14 in FIG. 4;
FIG. 7 is a block diagram showing a configuration of a decoding device 20 in FIG. 3;
8 is a block diagram showing a configuration of a decoding unit 21 in FIG.
FIG. 9 is a block diagram showing a configuration of a decryption certifying unit 22 in FIG. 7;
FIG. 10 is a block diagram showing a configuration of a replacement verification unit 30 in FIG. 3;
FIG. 11 is a block diagram showing a configuration of a decryption verification unit 40 in FIG. 3;
FIG. 12 is a block diagram showing a system configuration of a second embodiment.
FIG. 13 is a block diagram showing a configuration of a replacement server PS in FIG. 12;
FIG. 14 is a block diagram showing a configuration of a decryption server 20S in FIG. 12;
FIG. 15 is a diagram showing a data flow in each server in the second embodiment.
FIG. 16 is a block diagram showing a system configuration of a third embodiment.
FIG. 17 is a block diagram illustrating a configuration of a decoding unit in the decoding server 20S according to the third embodiment.
FIG. 18 is a block diagram illustrating a configuration of a decryption verification unit according to the third embodiment.
FIG. 19 is a block diagram showing an example of a system configuration using an anonymous communication channel according to the present invention.
FIG. 20 is a block diagram showing a plurality of complete replacement networks constituted by replacement servers cascade-connected via a bulletin board in the embodiment of FIG. 19;
FIG. 21 is a block diagram showing an example of a functional configuration of a permuted partial decoder with proof.
FIG. 22 is a block diagram showing an example of a functional configuration of a replacement disturbance device.
FIG. 23 is a block diagram illustrating a functional configuration example of a disrupter.
FIG. 24 is a block diagram showing an example of a functional configuration of a partial decoder with proof.
FIG. 25 is a block diagram showing a functional configuration example of a partial decoder.
FIG. 26 is a block diagram showing a functional configuration example of a partial decryption proof generator.
FIG. 27 is a block diagram showing an example of a functional configuration of a fixed partial decoder with proof.
FIG. 28 is a block diagram showing an example of a functional configuration of a permuted partial decoder with proof.
FIG. 29 is a block diagram showing a configuration example of a complete replacement network.
FIG. 30 is a block diagram showing an example of a technique for enlarging a complete replacement network.
FIG. 31 is a flowchart showing an example of processing for searching an input list of a replacement server.
FIG. 32 is a flowchart showing another processing example of searching the input list of the replacement server.
FIG. 33A is a table showing a result of determining the reliability of a replacement server disclosed on a bulletin board in another search processing method, and B is an example of reliability information held in a register by each replacement server in the search method; FIG.
FIG. 34 is a flowchart showing still another processing example of searching the input list of the replacement server.
FIG. 35 is a block diagram showing another embodiment of the anonymous communication path according to the present invention.
FIG. 36 is a flowchart showing a procedure for selecting a process based on the value of J in the replacement process procedure at the J-th stage of the replacement network.
FIG. 37 is a flowchart showing a procedure of processing 1 in FIG. 36;
FIG. 38 is a flowchart showing the procedure of processing 2 in FIG. 36;
FIG. 39 is a flowchart showing the procedure of Process 3 in FIG. 36;
FIG. 40 is a conceptual diagram of a computer system that reads a program of a perturbation-perturbed partial decryption method with proof according to the present invention from a recording medium and executes the perturbation-perturbed partial decryption with proof.

Claims (36)

N, where N is an integer greater than 2, replaces and disturbs the encrypted input message and outputs N output messages, and it is optional that the output message and the input message correspond one-to-one. a verifiable anonymous channel system to prove to the verifier,
For N inputs, n is smaller than N, n is an integer of 2 or more, and a plurality of processing stages for performing processing by the unit replacement processing means to obtain N outputs are cascaded,
The unit replacement processing means randomly replaces the n inputs and outputs n outputs by disturbing using the secret information, and outputs the n inputs and the n outputs to an arbitrary verifier . A verification means for outputting proof information that proves that the secret information and the random permutation certainly exist by using a zero-knowledge proof without revealing the secret information and the random permutation used. Possible anonymous communication system. 2. The verifiable anonymous communication channel system according to claim 1, wherein at least one of said processing stages comprises a plurality of said unit replacement processing means. 3. The verifiable anonymous communication channel system according to claim 1, wherein the unit replacement processing unit forms a replacement network including at least one complete replacement network. 2. The verifiable anonymous communication channel system according to claim 1, wherein n = 2, and each of said unit replacement processing means generates a switching random number which randomly takes one of two values; A verifiable anonymous communication path system, comprising: switching control means for controlling whether to output two outputs in accordance with a switching random number, with their positions interchanged or output at the same position. 5. The verifiable anonymous communication channel system according to claim 1, wherein said unit replacement processing means partially decrypts each of said n replacement disturbance results using a partial decryption key to obtain said N outputs. Including partial decryption means and partial decryption proof generation means for outputting proof information for certifying the use of the partial decryption key for the partial decryption with a zero-knowledge proof without revealing the partial decryption key. A verifiable anonymous communication channel system that features. 6. The verifiable anonymous communication channel system according to claim 5, wherein the cascade connection is a cascade connection of V replacement servers including at least one of the processing stages, and V is an integer of 2 or more. All of the other replacement servers are verifiably secret-shared, and the above-mentioned verifiable anonymous channel system further outputs t, t <V / 2, outputs in a state where the outputs of the replacement servers become unreliable. Means for recovering each partial decryption key with the shared key of the reliable replacement server, and means for collectively decrypting the output of the replacement server whose output is reliable using all the recovered partial decryption keys to obtain plaintext A verifiable anonymous communication channel system characterized by the following. 6. The verifiable anonymous channel system according to claim 5 , wherein the cascade connection is a cascade connection of V replacement servers including at least one of the processing stages and V is an integer of 2 or more, and a maximum of t replacements are performed. when allowing server substitution leakage, complete replacement network can output any substitution on the N input message, is composed of t + 1 pieces you successive cascaded in the V-number of substituted server A verifiable anonymous communication channel system characterized by the following. 8. The verifiable anonymous communication path system according to claim 6, wherein each of the replacement servers verifies the reliability of the output of the other replacement server using the input, output, and certification information of the replacement server. A verifiable anonymous communication path system, comprising: a determination unit for determining which replacement server should input an output while excluding the unreliable replacement server. 9. The verifiable anonymous communication channel system according to claim 8, wherein said verification means of each of said replacement servers sequentially verifies the output of said replacement server upstream from said replacement server, and said determination means trusts based on the verification result. A verifiable anonymous communication path system, which determines whether or not there is a possibility, and uses the output of the closest replacement server determined to be reliable as the input of the replacement server. 10. The verifiable anonymous communication path system according to claim 9 , further comprising: a bulletin board means for publishing a result of the determination on the reliability of the replacement server by each of the determination means. A verifiable anonymous communication path system, which is means for referring to a judgment result published on the bulletin board. 11. The verifiable anonymous communication channel system according to claim 10, wherein the judgment result to be disclosed is information indicating a replacement server that has output input data determined to be reliable by each replacement server, and the determination unit of each replacement server performs a verification. If the replacement server to be replaced does not use the output data of the reliable replacement server disclosed on the bulletin board as input data, the verification of the input and output of the replacement server to be verified is skipped. Road system. 11. The verifiable anonymous communication path system according to claim 10, wherein the judgment result published by each replacement server is a judgment result of the reliability of each replacement server upstream from the self- replacement server, and each of said replacement servers is an upstream replacement server. Has a register for recording the reliability information for, if the reliability determination result published by the other replacement server to each upstream replacement server is different from the reliability determination result determined by the own replacement server, A verifiable anonymous communication path system characterized in that a replacement server that has published a different determination result determines that the replacement server is unreliable, records the result in the register, and skips input / output verification of the replacement server. 5. The verifiable anonymous communication path system according to claim 1, wherein the cascade connection is a cascade connection of replacement servers of V units including at least one of the processing stages, and V is an integer of 2 or more. 5. Non-rewritable bulletin board means in which n inputs are written and connected to each of the replacement servers are provided, and the replacement server reads input data from the bulletin board means and writes a processing result to the bulletin board means. Verifiable anonymous communication system. 14. The decryptable anonymous communication path system according to claim 13, wherein the replacement result of each replacement server is verified, data output from the last stage of the replacement network is decrypted, and a decryption certificate is generated and written to the bulletin board means. A verifiable anonymous communication path system, wherein server means and a verification server for verifying the replacement certificate of the replacement server and the decryption certificate of the decryption server are connected to the bulletin board means. 15. The verifiable anonymous communication channel system according to claim 14, wherein the decryption server means includes a plurality of decryption servers connected to the bulletin board means and performing partial decryption. The verifiable anonymous communication channel system according to any one of claims 1 to 15, wherein the encrypted message is based on El Gamal encryption. N, where N is an integer greater than 2, the encrypted input message is passed through two or more integer V replacement servers connected in cascade to disturb and permutate to output N output messages. A verifiable anonymous communication method for proving to an arbitrary verifier that the output message and the input message correspond one-to-one,
Each of the permutation servers performs random permutation of the input N messages by an integer n of 2 or more smaller than N, disturbs using secret information, outputs N messages, and outputs each of the n messages. Of the perturbation perturbation process (hereinafter referred to as "unit process"), reveals that the secret information and the random permutation used for associating each of the n messages before and after the process exist. A verifiable anonymous communication method characterized by outputting proof information to be proved by a zero-knowledge proof without any need. 18. The verifiable anonymous communication method according to claim 17, wherein the n messages are partially decrypted for each unit process using a partial decryption key, and the partial decryption is performed using the partial decryption key. A verifiable anonymous communication method characterized by generating and outputting a partial decryption proof that is proved by a zero-knowledge proof without revealing a key. 18. The verifiable anonymous communication method according to claim 17, wherein the partial decryption key is secretly distributed in a verifiable manner to all of the other replacement servers in advance,
In the state where the output of t replacement servers of t <V / 2 becomes unreliable, each partial decryption key is recovered with the shared key of the reliable replacement server, and the trust is recovered using all the recovered partial decryption keys. A verifiable anonymous communication method characterized by collectively decrypting the output of a possible replacement server to obtain plaintext. 18. The verifiable anonymous communication method according to claim 17, wherein the permutation network capable of outputting any permutation of the N input messages when the permutation leakage of up to t permutation servers is allowed, comprises the V cascade-connected. A verifiable anonymous communication method, comprising composing t + 1 consecutive replacement servers. 21. The verifiable anonymous communication method according to claim 19, wherein each of the replacement servers verifies the reliability of the output of the other replacement server using the input, output, and certification information of the replacement server, and there is no reliability. A verifiable anonymous communication method, characterized in that the process of the replacement server is executed without the replacement server. 22. The verifiable anonymous communication method according to claim 21, wherein each of the replacement servers sequentially verifies whether or not the output of the replacement server upstream from the replacement server is correct. A verifiable anonymous communication method, wherein an output is an input of the replacement server. 23. The verifiable anonymous communication method according to claim 22, wherein each replacement server publishes a reliability determination result of each verified replacement server on a bulletin board, and each replacement server uses the bulletin board to determine an input of another replacement server. A verifiable anonymous communication method, characterized by referring to a judgment result published in a public domain. 24. The verifiable anonymous communication method according to claim 23, wherein the determination result to be disclosed is information indicating a replacement server that has output the input data that each replacement server has determined to be reliable, and each replacement server has a replacement server to be verified. A verifiable anonymous communication method characterized by skipping input / output verification of the replacement server to be verified, when the output data of the reliable replacement server disclosed on the bulletin board is not input data. 24. The verifiable anonymous communication method according to claim 23, wherein the determination result published by each replacement server is a determination result of reliability of each replacement server upstream from the self-replacement server, and each of said replacement servers communicates with a replacement server upstream therefrom. If the reliability information is recorded and the reliability judgment result published by the other replacement server to each upstream replacement server is different from the reliability judgment result determined by the own replacement server, the different judgment result A verifiable anonymous communication method, characterized in that a replacement server that has published the information is determined to be unreliable and recorded, and input / output verification of the replacement server is skipped. 18. The verifiable anonymous communication method according to claim 17, wherein said n inputs are written to a non-rewritable bulletin board, and each of said replacement servers sequentially reads input data from said bulletin board and writes a processing result to said bulletin board. Verifiable anonymous communication method. 27. The verifiable anonymous communication method according to claim 26, further comprising: a decryption server unit and a verification server connected to the bulletin board, wherein the decryption server unit verifies the replacement result of each of the replacement servers, and outputs the replacement result from the last replacement server. Verifying anonymous communication, characterized in that the decrypted data is decrypted, decryption proof information is generated and written in the bulletin board, and the verification server verifies the proof information of the replacement server and the decryption proof information of the decryption server means. Method. 28. The verifiable anonymous communication method according to claim 27, wherein said decryption server means comprises a plurality of decryption servers each connected to a bulletin board, wherein each decryption server partially decrypts output data of a predetermined replacement server. A verifiable anonymous communication method characterized by generating decryption proof information and writing these on the bulletin board, and inputting partial data corresponding to output data of the previous replacement server except for the first replacement server. A processing stage in which two or more integers N encrypted messages are inputted, and these messages are processed by the unit replacement processing means for each of two or more integers n smaller than N to obtain N outputs. A plurality of cascade connections are performed, and N messages are output from the last processing stage,
The unit replacement processing means is a switching unit that randomly replaces n input messages, and outputs n output messages by disturbing using secret information, and that the replacement and disturbance are correctly performed. A replacement server, comprising: a replacement proof generating unit that outputs the confidential information and the disturbance proof information to be proved by a zero-knowledge proof without revealing the random replacement. 30. The server of claim 29,
The unit replacement process hand stage, its disturbed n pieces of message is input, a partial decoding unit for outputting them as the n-number of the output message by partially decoded using the partial decryption key,
A decryption proof generation unit for outputting decryption proof information for certifying that the partial decryption unit has correctly operated by the zero-knowledge proof without revealing the partial decryption key. A permutation disturber to which n or more integer n messages are input, which are randomly permuted, and disturbed using secret information to output n messages;
N input messages and n output messages of the perturbation disturber are inputted, and the random permutation and the confidential information are revealed to the effect that the output message is correctly permuted and perturbed for these input messages. A disturbance proof generator that outputs disturbance proof information that enables verification by zero-knowledge proof,
A partial decoder that receives the n messages output from the permutation disturber, partially decrypts them using a partial decryption key, and outputs them as n output messages;
A decryption proof generator that inputs an input message of the partial decryptor and outputs decryption proof information for certifying that the partial decryptor is operating correctly without revealing the partial decryption key by a zero-knowledge proof. A switching device SW comprising:
An N number of encrypted messages greater than n is input, a plurality of processing stages constituted by the switching device SW are cascaded, and N output messages of the final stage processing and each of the switching devices A replacement server for outputting disturbance proof information and decryption proof information from a SW . 2 or more integer n number of messages are entered, a substituted randomizer to the n-number of message random permutation, and outputs the n number of messages disturbance by using the secret information,
A partial decoder that receives n output messages from the permutation disturber, decodes these output messages with a partial decryption key, and outputs n output messages;
The substitution randomizer of n input message and the partial decoder of the n output message is inputted, that the replacement and disturbance is performed correctly, and was the partial decoder operates correctly, the secret information A proof generator configured to output proof information for proving with the zero-knowledge proof without revealing the random permutation and the partial decryption key .
An N number of encrypted messages greater than n is input, a plurality of processing stages constituted by the switching device SW are cascaded, and N output messages of the final stage processing and each of the switching devices A replacement server for outputting disturbance proof information and decryption proof information from a SW . The server according to claim 30 or 32,
In one of the above processing stages, n messages are input, and the message is subjected to partial decryption with a partial decryption key and output without random replacement and disturbing, and the decryption was performed correctly. that, without revealing the partial decryption key, substituted server, wherein a certified fixing partial decoding unit for outputting a certification information certifying zero knowledge proof is provided one low Do Kutomo. The server according to any one of claims 30 to 33,
A replacement server, comprising: a verifier that inputs an input / output message and proof information of another replacement server, and verifies the reliability of an output message of the other replacement server by using the input / output message and the proof information. The server of claim 34,
The replacement server upstream from the replacement server is sequentially subjected to verification by the above-described verifier, and a determination unit that sets an output message of the closest replacement server determined to be reliable as an input message of the replacement server is provided. Replacement server featuring. A computer-readable recording medium storing a program for causing a computer to function as the replacement server according to any one of claims 29 to 35.

Images