(57)【特許請求の範囲】
【請求項１】
情報通信網で接続された複数の復号サーバを備え、
各復号サーバはそれぞれ異なる部分復号鍵を保持し、
多重に暗号化されたｎ個（ｎは２以上の整数）の暗号文からなるリストＬ0 を入力とし、
リスト中の各入力暗号文を、各復号サーバが保持する部分復号鍵で順次復号して、ランダムに置換された平文のリストを出力して、
その出力と入力との対応関係を隠蔽する匿名通信路であって、
上記各復号サーバごとに少くとも１台の検証サーバが設けられた復号ブロックが構成され、
各復号ブロック内の検証サーバには同じブロック内の復号サーバと同じ部分復号鍵が保持され、
各復号ブロック内の復号サーバと検証サーバは秘密通信路で接続され、
復号ブロックの数をｍ（ｍは２以上の整数）として、ｉ＝１からｍに対し、
ｉ番目の復号ブロックＢiに属する復号サーバは、ｉ−１番目の復号ブロックが公開したリストＬi-1 の各暗号文をその部分復号鍵で部分的に復号する手段と、そのｎ個の部分的復号結果をランダムな置換関数πi に従って並べ替えてリストＬi として公開する手段と、上記置換関数πiを秘密通信路でそのブロック内の各検証サーバへ送信する手段とを備え、
ｉ番目の復号ブロックに属する検証サーバは、上記リストＬi-1 の各暗号文をその部分復号鍵で部分的に復号する手段と、そのｎ個の部分的復号結果を上記置換関数πi に従って並べ替えてリストＬ″i を作る手段と、上記リストＬ″i が上記リストＬi と一致するか否かを検証し、一致しない場合はその部分復号鍵を公開して動作を停止する手段とを備え、
上記ｉ番目の復号ブロックＢiから部分復号鍵が公開されると、ｉ番目以外の復号ブロックの復号サーバが、復号ブロックＢiで処理すべきＬi-1，と復号ブロックＢiの公開部分復号鍵と対応する公開情報と全ての公開部分復号鍵とを取込み、上記取込んだ公開情報を用いてこれら公開部分復号鍵中の正しい部分復号鍵を選択し、その選択した部分復号鍵を用いてリストＬi-1に対する復号処理、置換処理を行い、そのリストＬi′を公開し、置換関数πi′をその復号ブロック内の検証サーバへ送信する復号代行手段を備え、上記ｉ番目以外の復号ブロック内の検証サーバは上記復号代行手段が動作すると、上記リストＬi′と上記復号ブロックＢiの公開部分復号鍵と対応する公開情報と全ての公開部分復号鍵とを取込み、これら取込んだ公開情報を用いてこれら公開部分復号鍵中の正しい部分復号鍵を選択し、その選択した部分復号鍵及び上記置換関数πiを用いて上記リストＬi′に対する検証処理をする検証代行手段を備えていることを特徴とする匿名通信路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電気通信装置を介して、例えば電子的にアンケート調査や電子的投票を実施する場合に、そのアンケート回答者や投票者の匿名性を保持した状態で回答内容や投票内容を正しく得ることができる通信に適用される匿名通信路に関する。
【０００２】
【従来の技術】
電気通信システムによって匿名通信路を実現する手段として、ＭＩＸ−ＮＥＴが提唱されている。ＭＩＸ−ＮＥＴはｍ個の復号サーバＭ1 ，…，Ｍm が記名通信路で接続されたシステムである。ＭＩＸ−ＮＥＴについて、特願平１１−３３３７２７号に示されている技術を説明する。
公開パラメータｇ，ｐ，ｑが全ての復号サーバの記憶装置に保持されているものとする。但し、ｐ，ｑは大きな素数で、ｑはｐ−１を割り切る。ｇはＺp*（Ｚp*は１，２，…，ｐ−１の集合）における位数ｑの元とする各復号サーバＭi （ｉ＝１，２，…，ｍ）はそれぞれ秘密鍵ａi およびｘi を記憶装置に保持する。対応する公開鍵ｙi は、ｈi ＝ｈi-1ai mod ｐに対してｙi ＝ｈixi mod ｐを満たすものとする（但し、ｈ0 ＝ｇ）。Ｍｉｘ−ｎｅｔへの入力は、ｎ個のエントリーからなるリストＬ0 である。Ｌ0 の中の各エントリーは、鍵情報Ｇと暗号文Ｃの対（Ｇ，Ｃ）である。各（Ｇ，Ｃ）は、平文ｍｓｇに対して、Ｇ：＝ｇr mod ｐ，Ｃ：＝ε（ε（…（ε（ｍｓｇ，Ｋm ），Ｋm-1 ），…），Ｋ1 ）のように計算して得られた値である。ここで、ｒは｛０，…，ｑ−１｝から暗号文語毎に独立して選んだ乱数であり、Ｋi はハッシュ関数Ｈを用いてＫi ：＝Ｈ（ｙir mod p ）とした値であり、ε（α，β）はβを暗号鍵としてメッセージαを暗号化する暗号化関数である。即ち、Ｃは平文ｍｓｇを鍵Ｋm ，…，Ｋ1 で多重に暗号化して得られる暗号文である。
【０００３】
復号サーバＭ1 は入力Ｌ0 に対して以下のように動作する。Ｌ0 中の各鍵情報−暗号文対（Ｇ，Ｃ）に対して、（Ｇ′，Ｃ′）を計算する。ここで、Ｇ′＝Ｇa1 modｐ，Ｃ′＝ＤK1（Ｃ）である。但し、ＤK1は鍵Ｋ１＝Ｈ（（Ｇ′）x1 modｐ）による復号関数である。このとき、（Ｇ′）x1＝Ｇa1x1＝ｇra1x1 ＝ｙ1r modｐが成り立つので、Ｃ′＝ＤK1（Ｃ）＝ε（ε（…（ε（ｍｓｇ，Ｋm ），Ｋm-1 ），…），Ｋ2 ）となり、結局、Ｃ′は多重に暗号化された暗号文を一回分だけ復号した結果となる。復号サーバＭ1 は、この一回分の復号を実行して得られる各（Ｇ′，Ｃ′）をシャッフル（ランダムに順序を入れ換えること）し、得られたランダム順序の暗号文のリストをＬ1 として出力し、次の復号サーバＭ2 へ送付する。以下、復号サーバＭ2 ，…，Ｍm は同様の手順を繰り返す。最終的に、復号サーバＭm からの出力Ｌm は、多重に掛けられた全ての暗号化を復号して得られる平文ｍｓｇのリストとなる。
【０００４】
各復号サーバが、復号鍵や、シャッフルに用いたランダム置換を明かさない限り、どの平文がどの暗号文に対応するかを判定することは、暗号化関数の性質上、困難になる。従って、各入力暗号文の作成者は、どの平文を入力したのかを知られることがなく、ここに匿名性を保つことができる。
【０００５】
【発明が解決しようとする課題】
しかし、特願平１１−３３３７２７号に示す匿名通信路においては、復号サーバにサーバの故障、および不正入力データの書き換えなどの不正処理が発生すると、出力平文が、正しく入力暗号文を復号したものと一致しない事があり得る。この発明は、上記問題点を解決し復号サーバに不正処理が起きた場合にも最終的に正常な出力を得ることのできる匿名通信路を提供することを目的とする。
【０００６】
【課題を解決するための手段】
この発明によれば各復号サーバごとにそれが正常に機能していることを確認する少くとも１つの検証サーバを設ける。その一つの復号サーバと、検証サーバからなるサーバのグループを復号ブロックと呼び、一つの復号ブロック内で、復号サーバの出力（部分的復号結果）をそのグループに属する全ての検証サーバで検証し、それら全ての検証サーバが復号サーバの出力を正常であると認めた場合にのみ、その復号ブロックの出力を正しいものとし、一つの復号ブロックに属する各検証サーバは、その復号サーバの部分復号鍵を保持させ、所属するブロックの検証サーバが出力の正当性を認めない場合には、その検証サーバが保持している部分復号鍵を出力（公開）する。ある復号ブロックの部分的復号結果が正しくないとされた場合、その復号ブロック以外の復号ブロックが出力（公開）された部分復号鍵を用いて、復号および検証動作を代理で実行する。
【０００７】
この構成により、少なくとも一つの復号ブロックで復号サーバを含む全てのサーバが正常に動作し、かつ、全ての復号ブロックにおいて少なくとも１台のサーバが正常に動作するならば、正しい平文のリストが出力されることが保証される。
【０００８】
【発明の実施の形態】
以下にこの発明の実施例を述べる。この実施例では、全体で、どのｍ−１台のサーバが故障した場合であっても、正常に機能する匿名通信路を示す。以下、ｐはＺp （Ｚp は０，１，２，…，ｐ−１の集合）において離散対数問題が手におえなくなる素数とする。ｇ∈Ｚp*はＺp*の生成元とする。また、以下の説明中で行う算術演算は別途記述のない限り、mod ｐで行う。
【０００９】
ｙi は復号ブロックＳi の公開情報であり、秘密情報ａi ，ｘi に対して、ｈ0 ＝ｇとし、ｉ（１＜ｉ＜ｍ）に対して以下のように定義する。
ｈi ＝ｈi-1 ai                                      （１）
ｙi ＝ｈi xi                                       （２）
匿名通信路への入力は、ｎ個の暗号文からなるリストＬ0 である。Ｌ0 の中の各入力暗号文を、（Ｇ，Ｃ）と表すことにする。各入力暗号文（Ｇ，Ｃ）は、各平文ｍｓｇに対して、Ｇ：＝ｇr mod ｐ，Ｃ： ＝ε（ε（…（ε（ｍｓｇ，Ｋm ），Ｋm-1 ），…），Ｋ1 ）のように計算して得られた値である。ここで、ｒは｛０，…，ｑ−１｝から暗号文語毎に独立して選んだ乱数であり、Ｋi はハッシュ関数Ｈを用いてＫi ：＝Ｈ（ｙir mod p）とした値であり、ε（α，β）はβを暗号鍵としてメッセージαを暗号化する暗号化関数である。例えば、εとして、ＤＥＳの暗号化演算を用いてもよい。結局、Ｃは平文ｍｓｇを鍵Ｋ１，…，Ｋｍで多重に暗号化して得られる暗号文である。
・装置概要
図１に匿名通信路を示す。ｍ個の復号ブロックＢ1 ，…，Ｂm が設けられ、各復号ブロックには１台の復号サーバＭi とｍ−１台の検証サーバＶi …Ｖi,mとのｍ台のサーバが属され、各復号ブロック内の復号サーバＭiと検証サーバＶi,1−Ｖi,mとは秘密通信路１１で接続される。更に、電子的な掲示板１２が設けられ、全ての復号サーバＭi 、全ての検証サーバＶi,1…Ｖi,mが掲示板と接続されて複数の復号サーバＭ1 …Ｍm が掲示板１２で接続された情報通信網が構成されている。掲示板１２にｎ個の（Ｇ， Ｃ）からなるリストＬ0 が入力公開され、また公開情報ｙ1 ，…，ｙm 、ｈ1，…，ｈm 、パラメータｐ，ｇも掲示板１２に公開されている。各復号ブロックをｍ個のサーバで構成しているが各サーバは独立に動作するものである。なお掲示板１２の代わりに、発信者認証付きの放送型通信路を用いてもよい。つまりどのサーバが出力したかがわかり、なりすましを防止した放送型通信路でもよい。
・復号サーバＭi 
図２に復号サーバの機能構成を示す。復号サーバＭi は、入力部１１０、出力部１２０、鍵選択部１３０、復号部１４０、鍵情報と暗号文の対のリストを攪拌するシャッフル部１５０、所属する復号ブロックＢi の部分復号鍵（秘密情報）ａi およびａi ｘi を格納したメモリ１６０、これらと接続された全体の制御を行う制御部１７０とを具備する。
・検証サーバＶi,j
図３に検証サーバの機能構成を示す。検証サーバＶi,jは、入力部２１０、出力部２２０、鍵選択部２３０、復号部２４０、復号サーバから送られた置換関数に基づいて置換を行う置換部２５０、リストの比較を行うリスト比較部２６０、所属する復号ブロックＢi の復号鍵ａi およびａi ｘi を格納したメモリ２７０、これらと接続され、全体の制御を行う制御部２８０とを具備する。
・復号部
図４に復号サーバの復号部１４０、検証サーバの復号部２４０の機能構成を示す。復号ブロックＢi に属するこれら復号部はその復号ブロックに取込まれた（Ｇ，Ｃ）と秘密情報ａi ，ａi ｘi が入力され、Ｇaiを演算して変換鍵情報Ｇ′を出力するべき乗演算器４１、Ｇaixiを演算するべき乗演算器４２、そのＧaixiにハッシュ関数を適用して復号鍵Ｋi ＝Ｈ（Ｇaixi）を生成するハッシュ器４３と、生成した復号鍵Ｋi を用いて多重に暗号化された暗号文Ｃを一回分復号化して部分的復号結果Ｃ′を出力する復号演算器４４とを具備する。
・鍵選択部
図５に復号サーバの鍵選択部１３０、検証サーバの鍵選択部２３０の機能構成を示す。復号ブロックＢi に属するこれら鍵選択部は、掲示板１２に表示された、復号ブロックＢi-1 に属する検証サーバが掲示板１２へ出力した各ａi およびａi ｘiの組と対応する公開情報ｈi-1 ，ｈi ，ｙi を入力とし、ｈi-1aiを計算するべき乗演算器３１とｈi-1aixiを計算するべき乗演算器３２と、これら計算結果と復号ブロックＢi-1 の公開鍵ｈi ，ｙi とをそれぞれ比較し、それらが一致するａi およびａi ｘi を正しい秘密情報として出力する比較器３３とを備える。
・シャッフル部
図６に復号サーバのシャッフル部１５０の機能構成を示す。復号ブロックＢi に属するシャッフル部１５０は、入力リストに対する全てのリストに対応する復号部１４０より得られた暗号文と鍵情報のリストＬi′を入力とし、乱数生成器によりなる置換生成器５１より出力されたｎ個の乱数よりなる置換関数πi に基づきリストの置換（並べ替え）を置換器５２で行い、置換されたリストＬi と置換関数πi を出力する。
・置換部
図７に検証サーバの置換部２５０の機能構成を示す。復号ブロックＢi に属する置換部は、入力リストに対する全てのリストに対応する、その検証サーバの復号部より得られた暗号文と鍵情報のリストを入力とし、復号サーバＭi から送られてきた置換関数πi を基に置換器でリストの置換（並べ替え）を行い、置換されたリストＬi を出力する。
【００１０】
入力を受けた匿名通信路は、１番目の復号ブロックＢ1 からＢ1 ，Ｂ2 ，…，Ｂm の順に以下を実行する。
・復号ブロックＢi の復号サーバＭi は以下のように動作する。その処理手順を図８に示す。
入力部１１０は掲示板１２に直前の復号ブロックＢ1 の復号サーバＭi-1 からリストＬi-1 が公開（出力）されたかを常時監視しており（Ｓ１）、掲示板１２にＬi-1 が公開されると、復号ブロックＢi-1 の検証サーバから秘密情報ａi-1 ，ａi-1 ｘi-1 が掲示板１２に公開されたかを調べ（Ｓ２）、公開されていなければ、リストＬi-1 を掲示板１２から取り込み、制御部１７０内の動作用メモリに一旦記憶する（Ｓ３）。
【００１１】
メモリ１６０に格納してある秘密情報ａi ，ａi ｘi を取出し復号部１４０に入力し（Ｓ４）、リストＬi-1 中の暗号文（Ｇ，Ｃ）を１つ取り出して復号部１４０へ入力する（Ｓ５）。復号部１４０では図４に示すようにまず、Ｇ，ａi を鍵情報用べき乗演算器４１に入力し、鍵情報Ｇ′＝Ｇaiを生成する（Ｓ６）。次に、Ｇ，ａi ｘi を復号鍵用べき乗演算器４２に入力してＧaixiを演算し（Ｓ７）、その結果Ｇaixiをハッシュ器４３へ入力して、その結果Ｈ（Ｇaixi）を復号鍵Ｋi とする（Ｓ８）。得られた復号鍵Ｋi と入力されたＣとを復号演算器４４へ入力して一回分の復号処理を行い、その結果をＣ′＝ε（ε（…（ε（ｍｓｇ，Ｋm ），Ｋm-1 ），…），Ｋi-1 ）とする（Ｓ９）。
【００１２】
リストＬi-1 中にまた処理していない（Ｇ，Ｃ）があるかを調べ（Ｓ１０）、まだあればステップＳ５に戻り同様のことを繰り返す。
復号部１４０が出力した暗号文と鍵情報の対を（Ｇ′，Ｃ′）とする。リストＬi-1 中の全ての暗号文に対して同様の復号処理をして、得られた（Ｇ′，Ｃ′）のリストＬ′i とする。Ｌ′i が得られると、Ｌ′i をシャッフル部１５０へ入力する。シャッフル部１５０は、ランダム置換生成器５１（図６）を駆動して、ランダム置換関数πi を生成（Ｓ１１）、置換器５２へランダム置換関数πi 及びリストＬ′i を入力し、置換関数πi に応じて置換（並べ替え）されたリストＬi を得る（Ｓ１２）。
【００１３】
出力部１２０を駆動してＬi を掲示板１２に公開し、置換関数πi を秘密通信路１１を用いて同一復号ブロックＢi 内の各検証サーバＶi,1…Ｖi,mへ送信する（Ｓ１３）。
・復号ブロックＢi の各検証サーバＶi,1…Ｖi,mは以下のように動作する。その処理手順を図９に示す。
入力部２１０は復号サーバＬi からの受信を待ち（Ｓ１）、受信があると、代行処理か否かを調べ（Ｓ２）、代行処理でなければ受信した置換関数πi を一時記憶し、また掲示板１２から復号サーバＬi ，Ｍi-1 の出力リストＬi-1 を取り込み、動作用メモリに記憶する（Ｓ３）。
【００１４】
このＬi-1 に対し前記した復号サーバＭi の復号処理と同様の処理を実行する。つまり図８中のステップＳ４乃至Ｓ１０を実行して、リストＬ′i を得る（Ｓ４）。このＬ′i に対し、置換部２５０で復号サーバＭi から受信したπi を用いて置換（並べ替え）を行い、リストＬ″i として出力する（Ｓ５）。
掲示板１２から復号サーバＭiの出力リストＬiを取込み（Ｓ６）、このＬi とＬ″i をリスト比較部２６０へ入力し、Ｌ″i とＬi の両者が一致しているか否かを判定し（Ｓ７）、一致している場合は“１”を掲示板１２へ出力し（Ｓ８）、そうでない場合は“０”とその検証サーバが保持しているメモリ２７０内の秘密情報ａi 及びａi ｘi を掲示板１２に出力する（Ｓ９）。ステップＳ６のＬi の取込みは、ステップＳ３で同時に行っておいてもよい。あるいは復号サーバＭi からπi と共にＬi も検証サーバへ送ってもよい。なお掲示板１２へ出力（公開）する場合は、何れの復号ブロックから出力したかを示す情報を付加しておく。
【００１５】
図８中のステップＳ２において、ａi-1 ，ａi-1 ｘi-1 の組が一つでも掲示板１２に公開されている場合は、復号ブロックＢi-1 の復号サーバＭi-1 により作られ、出力されたリストＬi-1 に対する検証サーバによる検証において不一致を出力するものがあり、正しいものとして検証されなかった場合である。そこでこの実施例では、復号ブロックＢi で復号ブロックＢi-1 の処理を代行させるようにした場合である。
【００１６】
つまり、復号サーバＭi は、復号ブロックＢi-1 で処理すべきリストＬi-2 を掲示板１２から取込み、また正しい秘密情報の選択のために、公開情報ｈi-2 ，ｈi-1 ，ｙi-1 を掲示板１２から取込み、更に掲示板１２に公開されている全ての秘密情報ａi-1 ，ａi-1 ｘi-1 を取込み、これらを一時記憶する（Ｓ１４）。鍵選択部１３０で、これらを取込んだ秘密情報ａi-1 ，ａi-1 ｘi-1 と、公開情報ｈi-2 ，ｈi-1 ，ｙi-1 を入力して、図５に示した処理を、各ａi-1 ，ａi-1 ｘi-1 の組に対して行い、比較器３３で一致が得られたａi-1 ，ａi-1 ｘi-1 を正しい秘密情報として選択する（Ｓ１５）。
【００１７】
次にこの正しい秘密情報ａi-1 ，ａi-1 ｘi-1 を用いて、Ｌi-2 に対し、ステップＳ５〜Ｓ１２と同様にして復号処理を行い、更に置換処理をしたリストＬi-1 を取得する（Ｓ１６）。このリストＬi-1 を掲示板１２に公開し、リストの置換に用いた置換関数πi-1 を検証サーバＶi,1…Ｖi,mへ、代行処理であることを示す情報を付加して送信する（Ｓ１７）。
なお復号ブロックＢi-1 の復号サーバＭi-1 が故障などによる不正処理がなされても検証サーバＶi-1,1 ，…，Ｖi-1,m が全て正しい場合で、かつ復号サーバＭi が正しい処理をすれば、これに用いた秘密情報ａi-1 ，ａi-1 ｘi-1 は公開情報により正しいことが保証されたものであるから、この代行処理により得られたＬi-1 は正しいものとなる。この場合も復号サーバＭi が正しい処理を行ったかを検証するため、復号ブロックＢi の各検証サーバＶi,1,…,Ｖi,mでは、図９中のステップＳ２において代行処理であると判定されると、受信したπi-1 を記憶し、また掲示板１２からＬi-2 ，ｈi-2 ，ｈi-1 ，ｙi-1 、全てのａi-1 ，ａi-1 ｘi-1 を取込み記憶する（Ｓ１０）。
【００１８】
取込んだａi-1 ，ａi-1 ｘi-1 について鍵選択部２３０で、図５に示した鍵選択処理を行い、正しいａi-1 ，ａi-1 ｘi-1 を選択する（Ｓ１１）。その正しいａi-1 ，ａi-1 ｘi-1 を用いてＬi-2 に対し復号処理を行い、復号結果に対し、受信したπi-1 によって置換処理を行ってリストＬ″i-2 を求め、このＬ″i-2 と復号サーバＭi の代行処理により得たＬi-2 とを比較して、その比較結果に対し、ステップＳ８，Ｓ９と同様な処理を行う（Ｓ１３）。
【００１９】
この結果、各検証サーバＶi,1…Ｖi,mで全て一致が得られ、ａi-1 ，ａi-1 ｘi-1 が出力されていないため、図８中のステップＳ１で復号サーバＭi により公開されたＬi-1 を検出し、かつステップＳ２で復号ブロックＢi の検証サーバからａi-1 ，ａi-1 ｘi-1 が公開されていないため、そのＬi-1 についてステップＳ３以下の処理を実行することができる。
以上のような処理を復号ブロックＢi についてｉ＝１からｉ＝ｍまで順次行うことにより、不正処理がなければ、あるいは不正処理があっても代行処理により正しい処理がなされると、最後の復号サーバＭm から入力リストＬ0 が並べかえられ、正しく復号された平文リストＬm が得られる。つまり最終的には、例えば予め決めた最終復号ブロックＢm の何れかのサーバ又は特に設けたサーバが、上記復号ブロックＢm の処理が終了した後に、各復号ブロックＢi ごとに検証サーバが“０”を出力している場合は、その出力している秘密情報ａi ，ａi ｘi を公開情報ｈi-1 ，ｈi ，ｙi により検証して正しい秘密情報を用いて局部的復号処理を行い、復号ブロックＢi で検証サーバが全て“１”を出力していれば、その復号ブロック（復号サーバＭi ）の出力Ｌi を用いることにより、最終的な正しい復号結果Ｌm を求める。
【００２０】
なお、各復号ブロックＢ1 …Ｂm において、復号サーバ、検証サーバの少くとも１つは必ず正しく、かつ復号ブロックＢ1 …Ｂm の少くとも１つが必ず正しければ、この匿名通信路は正常に動作する。つまり、正しく動作する復号ブロック以外において、不正が行われても、復号サーバに不正があった場合には、必ず正常な少くとも１つの検証サーバからその正しい秘密情報ａi ，ａi ｘi が出力されるため、公開情報ｈi-1 ，ｈi ，ｙi とから正しい鍵Ｋi を作ることができ、復号処理を行うことができる。１つの復号ブロックは必ず正常であるため、入力リストに対しランダムな並べ替えがなされた出力リストが得られ、また復号サーバと各検証サーバとは秘密通信路１１で接続されているため置換関数πi が盗まれるおそれがないから匿名通信路として作用をする。一方、１つの復号ブロックの全ての検証サーバから秘密情報ａi ，ａi ｘi が公開され、これらの秘密情報について鍵選択処理をして、正しいものを選択することができなかった場合は、その復号ブロックの復号サーバが正しいことになり、その出力リストＬi を利用すればよい。
【００２１】
図１に示したように各復号ブロックＢi を１個の復号サーバＭi にｍ−１個の検証サーバＶi,1…Ｖi,m-1 を設け、復号ブロックの数をｍとする場合は全体で（ｍ−１）個のサーバに不正があっても、正しく動作する。上述したように復号ブロックの少くとも１つには不正がなく、かつ各復号ブロック中の復号サーバ、検証サーバ中の少くとも１つに不正がなければこの発明の匿名通信路は正常に動作し、各復号ブロックに所属させる検証サーバは少くとも１以上であればよい。
【００２２】
上述では復号ブロックＢi-1 の代行処理を次の復号ブロックＢi で行ったが、代行処理は先に述べたように、掲示板１２に公開されている情報を用いて行うのであるから、復号ブロックＢi-1 以外の復号ブロックＢi〜Ｂm の何れに行わせてもよい。この場合は、代行処理を行う復号ブロックを予め決めておき、掲示板１２に同一復号ブロックからリストＬi の他に秘密情報ａi ，ａi ｘi が公開されるか否かを監視し、Ｌi+1 が公開された状態でＬi についての代行処理を行うようにすればよい。
【００２３】
公開情報ｈi-1 ，ｈi ，ｙi を掲示板１２に公開したが、各サーバのメモリに該当するものを記憶しておいてもよい。発信者認証付きの放送型通信路を用いる場合は、各復号サーバＭi では、１つ前の復号サーバＭi-1 からのリストＬi-1 が受信されるのを待って処理し、また復号ブロックＢi-1 の検証サーバからの秘密情報ａi-1 ，ａi-1 ｘi-1 、復号サーバＭi-2 からのリストＬi-2 も受信しておくようにすればよい。
【００２４】
【発明の効果】
以上述べたように、この発明によれば、各復号サーバごとにその復号サーバが正常に機能していることを確認できる検証サーバを設け、その検証サーバが復号サーバの出力が正常と認めた場合のみ、その復号サーバの出力が正しいとし、正常に機能したと確認がとれなかった場合は、検証サーバの秘密情報を出力することにより、少くとも一つの復号ブロックが正常に動作し、かつ全復号ブロックで少くとも１回のサーバが正常に動作すれば、故障やデータ書き換えなどの不正処理があっても、匿名性が保持された正しい平文リストを出力として得られる。
【図面の簡単な説明】
【図１】この発明の実施例を示すブロック図。
【図２】図１中の復号サーバＭi の機能構成例を示す図。
【図３】図１中の検証サーバＶi,jの機能構成例を示す図。
【図４】図２及び図３中の復号部の具体例を示す図。
【図５】図２及び図３中の鍵選択部の具体例を示す図。
【図６】図２中のシャッフル部の具体例を示す図。
【図７】図３中の置換部の例を示す図。
【図８】復号サーバＭi の処理手順の例を示す流れ図。
【図９】検証サーバＶi,jの処理手順の例を示す流れ図。
【図１】
0003638501.tif 000002
【図２】
0003638501.tif 000003
【図３】
0003638501.tif 000004
【図４】
0003638501.tif 000005
【図５】
0003638501.tif 000006
【図６】
0003638501.tif 000007
【図７】
0003638501.tif 000008
【図８】
0003638501.tif 000009
【図９】
0003638501.tif 000010