(57)【特許請求の範囲】
【請求項１】
Ｎ個，Ｎは２より大の整数、の暗号化された入力メッセージを置換撹乱してＮ個の出力メッセージを出力し、上記出力メッセージと上記入力メッセージが一対一に対応することを、任意の検証器に証明する検証可能匿名通信路システムであって、
Ｎ個の入力に対し、Ｎより小さいｎ個、ｎは２以上の整数、ずつ、単位置換処理手段により処理を実行してＮ個の出力を得る処理段の複数個が縦続接続され、
上記単位置換処理手段はｎ個の入力をランダム置換し、秘密情報を用いて撹乱することによりｎ個の出力を出力し、任意の検証器に対して上記ｎ個の入力と上記ｎ個の出力を対応付ける上記秘密情報及び上記ランダム置換が確かに存在することを、使用した上記秘密情報及び上記ランダム置換を明かすことなく零知識証明で証明する証明情報を出力する手段であることを特徴とする検証可能匿名通信路システム。
【請求項２】
請求項１の検証可能匿名通信路システムにおいて、上記処理段の少なくとも１つは複数の上記単位置換処理手段から成ることを特徴とする検証可能匿名通信路システム。
【請求項３】
請求項１又は２の検証可能匿名通信路システムにおいて、上記単位置換処理手段は少なくとも１つの完全置換網を含む置換網を形成していることを特徴とする検証可能匿名通信路システム。
【請求項４】
請求項１の検証可能匿名通信路システムにおいて、ｎ＝２であり、上記各単位置換処理手段は２つの値のいずれか一方の値をランダムにとる切換乱数を発生する切換乱数発生手段と、上記切換乱数に従って２つの出力をそれらの位置を入れ換えて出力するかそのままの位置で出力するかを制御する切換制御手段を含むことを特徴とする検証可能匿名通信路システム。
【請求項５】
請求項１〜４のいずれかの検証可能匿名通信路システムにおいて、上記単位置換処理手段は、部分復号鍵を使って上記ｎ個の置換撹乱結果をそれぞれ部分復号して上記Ｎ個の出力とする部分復号手段と、上記部分復号に上記部分復号鍵を使用したことを、上記部分復号鍵を明らかにすることなく零知識証明で証明する証明情報を出力する部分復号証明生成手段とを含むことを特徴とする検証可能匿名通信路システム。
【請求項６】
請求項５の検証可能匿名通信路システムにおいて、上記縦続接続は少なくとも上記処理段を少なくとも１つ含むＶ個、Ｖは２以上の整数、の置換サーバの縦続接続であり、上記部分復号鍵は予め他の置換サーバの全てに検証可能に秘密分散されてあり、上記検証可能匿名通信路システムは更に、ｔ個、t<V/2、の置換サーバの出力が信頼
できなくなった状態で、出力が信頼できる置換サーバの分散鍵で各部分復号鍵を回復する手段と、その回復した全ての部分復号鍵を用いて出力が信頼できる置換サーバの出力を一括復号して平文を得る手段とを含むことを特徴とする検証可能匿名通信路システム。
【請求項７】
請求項５の検証可能匿名通信路システムにおいて、上記縦続接続は少なくとも上記処理段を少なくとも１つ含むＶ個、Ｖは２以上の整数、の置換サーバの縦続接続であり、最大ｔ個の上記置換サーバの置換の漏洩を許容するとき、上記Ｎ個の入力メッセージに対するあらゆる置換を出力できる完全置換網が、縦続接続された上記Ｖ個の置換サーバ中の連続する t+1個により構成されていることを特徴とする検証可能匿名通信路システム。
【請求項８】
請求項６又は７の検証可能匿名通信路システムにおいて、各上記置換サーバは、他の置換サーバの出力の信頼性を、その置換サーバの入力、出力及び証明情報を用いて検証する検証手段と、信頼性がない置換サーバを排除してどの置換サーバの出力を入力すればよいかの判定を行う判定手段とをそれぞれ含むことを特徴とする検証可能匿名通信路システム。
【請求項９】
請求項８の検証可能匿名通信路システムにおいて、各上記置換サーバの上記検証手段は、その置換サーバより上流の上記置換サーバについて順次その出力を検証し、上記判定手段はその検証結果に基づいて信頼性があるかないかを判定し、最も近い信頼できると判定された置換サーバの出力を上記置換サーバの入力とすることを特徴とする検証可能匿名通信路システム。
【請求項１０】
請求項９の検証可能匿名通信路システムにおいて、上記各判定手段による上記置換サーバについての信頼性の判定結果を公開する掲示板手段が設けられており、上記判定手段はその置換サーバの入力判定に、上記掲示板に公開された判定結果を参照する手段であることを特徴とする検証可能匿名通信路システム。
【請求項１１】
請求項１０の検証可能匿名通信路システムにおいて、上記公開する判定結果は各置換サーバが信頼できると判定した入力データを出力した置換サーバを表す情報であり、各置換サーバの上記判定手段は、検証すべき置換サーバが上記掲示板に公開した信頼できる置換サーバの出力データを入力データとするものでない場合は、上記検証すべき置換サーバの入出力の検証をスキップすることを特徴とする検証可能匿名通信路システム。
【請求項１２】
請求項１０の検証可能匿名通信路システムにおいて、各置換サーバが公開する判定結果は自置換サーバより上流の各置換サーバに対する信頼性の判定結果であり、上記各置換サーバはそれより上流の置換サーバに対する信頼度情報を記録するレジスタを有し、他の置換サーバが上記上流の各置換サーバに対し公開している信頼性の判定結果が自置換サーバにより判定した信頼性判定結果と異なる場合、その異なる判定結果を公開した置換サーバは信頼性がないと判定して上記レジスタに記録し、その置換サーバについての入出力の検証をスキップすることを特徴とする検証可能匿名通信路システム。
【請求項１３】
請求項１〜４のいずれかの検証可能匿名通信路システムにおいて、上記縦続接続は少なくとも上記処理段を少なくとも１つ含むＶ個、Ｖは２以上の整数、の置換サーバの縦続接続であり、上記ｎ個の入力が書き込まれ、各上記置換サーバと接続された書き換え不可の掲示板手段が設けられ、上記置換サーバは入力データを上記掲示板手段から読み込み、処理結果を上記掲示板手段に書き込むことを特徴とする検証可能匿名通信路システム。
【請求項１４】
請求項１３の検証可能匿名通信路システムにおいて、各上記置換サーバの置換結果を検証し、置換網の最終段から出力されたデータを復号すると共に、復号証明を生成して上記掲示板手段に書き込む復号サーバ手段と、上記置換サーバの置換証明及び上記復号サーバの復号証明を検証する検証サーバが上記掲示板手段に接続されていることを特徴とする検証可能匿名通信路システム。
【請求項１５】
請求項１４の検証可能匿名通信路システムにおいて、上記復号サーバ手段はそれぞれ掲示板手段に接続され、部分復号を行う複数の復号サーバを含むことを特徴とする検証可能匿名通信路システム。
【請求項１６】
請求項１〜１５のいずれかの検証可能匿名通信路システムにおいて、上記暗号化されたメッセージはEl Gamal 暗号によるものであることを特徴とする検証
可能匿名通信路システム。
【請求項１７】
Ｎ個，Ｎは２より大の整数、の暗号化された入力メッセージを、縦続接続された２以上の整数Ｖ個の置換サーバに通して置換撹乱してＮ個の出力メッセージを出力し、上記出力メッセージと上記入力メッセージが一対一に対応することを、任意の検証者に証明する検証可能匿名通信方法であって、
上記各置換サーバは入力されたＮ個のメッセージを、Ｎより小さい２以上の整数ｎ個ずつランダム置換し、秘密情報を用いて撹乱してＮ個のメッセージを出力し、かつ上記各ｎ個ずつの置換撹乱処理（以下、単位処理という）についてその処理の前後の各ｎ個のメッセージを対応付ける上記秘密情報及び上記ランダム置換が確かに存在することを、使用した上記秘密情報及び上記ランダム置換を明かすことなく零知識証明で証明する証明情報をそれぞれ出力することを特徴とする検証可能匿名通信方法。
【請求項１８】
請求項１７の検証可能匿名通信方法において、上記単位処理ごとにそのｎ個のメッセージを、部分復号鍵を使って部分復号し、上記部分復号に上記部分復号鍵を使用したことを、上記部分復号鍵を明らかにすることなく零知識証明で証明する部分復号証明を生成出力することを特徴とする検証可能匿名通信方法。
【請求項１９】
請求項１７の検証可能匿名通信方法において、予め上記部分復号鍵をそれぞれ他の置換サーバの全てに検証可能に秘密分散しておき、
ｔ個、t<V/2、の置換サーバの出力が信頼できなくなった状態で、信頼できる置換サーバの分散鍵で各部分復号鍵を回復し、その回復した全ての部分復号鍵を用いて信頼できる置換サーバの出力を一括復号して平文を得ることを特徴とする検証可能匿名通信方法。
【請求項２０】
請求項１７の検証可能匿名通信方法において、最大ｔ個の上記置換サーバの置換の漏洩を許容するとき、上記Ｎ個の入力メッセージに対するあらゆる置換を出力できる完全置換網が、縦続接続された上記Ｖ個の置換サーバ中の連続する t+1個を構成することを特徴とする検証可能匿名通信方法。
【請求項２１】
請求項１９又は２０の検証可能匿名通信方法において、各上記置換サーバは、他の置換サーバの出力の信頼性を、その置換サーバの入力、出力及び証明情報を用いて検証し、信頼性がない置換サーバを排除して置換サーバの処理を実行することを特徴とする検証可能匿名通信方法。
【請求項２２】
請求項２１の検証可能匿名通信方法において、各上記置換サーバは、当該置換サーバより上流の上記置換サーバについて順次その出力が正しいか否かを検証し、最も近い信頼できると判定された置換サーバの出力を当該置換サーバの入力とすることを特徴とする検証可能匿名通信方法。
【請求項２３】
請求項２２の検証可能匿名通信方法において、各置換サーバは上記検証した各置換サーバについての信頼性の判定結果を掲示板に公開し、各置換サーバは他の置換サーバの入力の判定に、上記掲示板に公開された判定結果を参照することを特徴とする検証可能匿名通信方法。
【請求項２４】
請求項２３の検証可能匿名通信方法において、上記公開する判定結果は各置換サーバが信頼できると判定した入力データを出力した置換サーバを表す情報であり、各置換サーバは、検証すべき置換サーバが上記掲示板に公開した信頼できる置換サーバの出力データを入力データとするものでない場合は、上記検証すべき置換サーバの入出力の検証をスキップすることを特徴とする検証可能匿名通信方法。
【請求項２５】
請求項２３の検証可能匿名通信方法において、各置換サーバが公開する判定結果は自置換サーバより上流の各置換サーバに対する信頼性の判定結果であり、上記各置換サーバはそれより上流の置換サーバに対する信頼度情報を記録しておき、他の置換サーバが上記上流の各置換サーバに対し公開している信頼性の判定結果が自置換サーバにより判定した信頼性判定結果と異なる場合、その異なる判定結果を公開した置換サーバは信頼性がないと判定して記録しておき、その置換サーバについての入出力の検証をスキップすることを特徴とする検証可能匿名通信方法。
【請求項２６】
請求項１７の検証可能匿名通信方法において、上記ｎ個の入力を書き換え不可の掲示板に書き込み、上記各置換サーバは順次、入力データを上記掲示板から読み込み、処理結果を上記掲示板に書き込むことを特徴とする検証可能匿名通信方法。
【請求項２７】
請求項２６の検証可能匿名通信方法において、上記掲示板に接続された復号サーバ手段と検証サーバを設け、上記復号サーバ手段は各上記置換サーバの置換結果を検証し、最終段の置換サーバから出力されたデータを復号すると共に、復号証明情報を生成して上記掲示板に書き込み、上記検証サーバは上記置換サーバの証明情報及び上記復号サーバ手段の復号証明情報を検証することを特徴とする検証可能匿名通信方法。
【請求項２８】
請求項２７の検証可能匿名通信方法において、上記復号サーバ手段をそれぞれ掲示板に接続された複数の復号サーバで構成し、それぞれの復号サーバは予め決められた置換サーバの出力データを部分復号を行うと共に復号証明情報を生成してこれらを上記掲示板に書き込み、各初段の置換サーバ以外は前段の置換サーバの出力データに対する部分データを入力することを特徴とする検証可能匿名通信方法。
【請求項２９】
２以上の整数Ｎ個の暗号化されたメッセージが入力され、これらメッセージに対しＮより小さい２以上の整数ｎ個ずつ、単位置換処理手段により処理を実行してＮ個の出力を得る処理段が複数個縦続接続され、その終段の処理段よりＮ個のメッセージが出力され、
上記単位置換処理手段は、ｎ個の入力メッセージをランダム置換し、かつ秘密情報を用いて撹乱してｎ個の出力メッセージを出力する切換部と、上記置換と撹乱が正しく行われたことを、上記秘密情報及び上記ランダム置換を明かすことなく零知識証明で証明する撹乱証明情報を出力する置換証明生成部とを備えることを特徴とする置換サーバ。
【請求項３０】
請求項２９のサーバにおいて、
上記単位置換処理手段は、その撹乱されたｎ個のメッセージが入力され、これらを部分復号鍵を用いて部分復号してｎ個の上記出力メッセージとして出力する部分復号部と、
その部分復号部が正しく動作したことを上記部分復号鍵を明かすことなく零知識証明で証明する復号証明情報を出力する復号証明生成部とを備えることを特徴とする置換サーバ。
【請求項３１】
２以上の整数ｎ個のメッセージが入力され、これらをランダム置換し、かつ秘密情報を用いて撹乱してｎ個のメッセージを出力する置換撹乱器と、
その置換撹乱器のｎ個の入力メッセージとｎ個の出力メッセージとが入力され、これら入力メッセージに対し、出力メッセージが正しく置換撹乱処理されたものであることを上記ランダム置換及び上記秘密情報を明かすことなく、零知識証明による検証を可能とする撹乱証明情報を出力する撹乱証明生成器と、
上記置換撹乱器から出力されたｎ個のメッセージが入力され、これらを部分復号鍵を用いて部分復号してｎ個の出力メッセージとして出力する部分復号器と、
その部分復号器の入力メッセージを入力して、その部分復号器が正しく動作している事を上記部分復号鍵を明かすことなく零知識証明で証明する復号証明情報を出力する復号証明生成器とを備える切替装置ＳＷが構成され、
ｎより大きい整数Ｎ個の暗号化されたメッセージが入力され、上記切替装置ＳＷにより構成される処理段が複数個縦続接続され、その終段の処理のＮ個の出力メッセージと、上記各切替装置ＳＷよりの撹乱証明情報及び復号証明情報とを出力することを特徴とする置換サーバ。
【請求項３２】
２以上の整数ｎ個のメッセージが入力され、このｎ個のメッセージをランダム置換し、かつ秘密情報を用いて撹乱してｎ個のメッセージを出力する置換撹乱器と、
その置換撹乱器よりのｎ個の出力メッセージが入力され、これら出力メッセージを部分復号鍵で復号してｎ個の出力メッセージを出力する部分復号器と、
上記置換撹乱器のｎ個の入力メッセージ及び上記部分復号器の上記ｎ個の出力メッセージが入力され、上記置換と撹乱が正しく行われ、かつ上記部分復号器が正しく動作したことを、上記秘密情報、上記ランダム置換及び上記部分復号鍵を明かすことなく零知識証明で証明する証明情報を出力する証明生成器とを備える切替装置ＳＷが構成され、
ｎより大きい整数Ｎ個の暗号化されたメッセージが入力され、上記切替装置ＳＷにより構成される処理段が複数個縦続接続され、その終段の処理のＮ個の出力メッセージと、上記各切替装置ＳＷよりの撹乱証明情報及び復号証明情報とを出力することを特徴とする置換サーバ。
【請求項３３】
請求項３０又は３２のサーバにおいて、
上記処理段の中の１つには、ｎ個のメッセージが入力され、これに対しランダム置換、撹乱することなく、部分復号鍵による部分復号を行って出力し、かつその復号が正しく行われたことを、その部分復号鍵を明かすことなく、零知識証明で証明する証明情報を出力する証明付き固定部分復号部が少なくとも１つ設けられていることを特徴とする置換サーバ。
【請求項３４】
請求項３０〜３３の何れかのサーバにおいて、
他の置換サーバの入出力メッセージと証明情報を入力し、これらを用いて上記他の置換サーバの出力メッセージの信頼性を検証する検証器を備えることを特徴とする置換サーバ。
【請求項３５】
請求項３４のサーバにおいて、
当該置換サーバより上流の置換サーバについて順次、上記検証器による検証を実行させ、信頼性があると判定された最も近い置換サーバの出力メッセージを当該置換サーバの入力メッセージとする判定器を備えることを特徴とする置換サーバ。
【請求項３６】
請求項２９〜３５のいずれかに記載した置換サーバとしてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電気通信システムで無記名投票を実現する場合等に利用される検証可能な匿名通信路システム、特に効率的に実現可能な匿名通信路、それを実施する方法及びその方法を記録した記録媒体に関する。
【０００２】
【従来の技術】
まず、匿名通信路について説明する。一般に各サーバはそのサーバに接続した利用者を識別することができるのでどの利用者がどの情報を送信しているかを知ることができ、利用者とサーバ間の通信路には匿名性はない。匿名通信路を物理的な構成に因らず、電気通信システムにより実現する手段として、ＭＩＸ−ＮＥＴ  が提唱されている。ＭＩＸ−ＮＥＴ  ではＬ個のサーバＵ１，…，ＵＬが直列的に記名通信路で接続されたシステムである。
【０００３】
ＲＳＡ関数を用いてこれを実装する場合は、ｉ番目のサーバは、大きな素数ｐｉ，ｑｉに対し、ｎｉ＝ｐｉ・ｑｉ及びｅｉ・ｄｉ＝１（ｍｏｄ  ＬＣＭ（ｐｉ−１，  ｑｉ−１））を満たす（ｄｉ，ｎｉ），（ｅｉ，ｎｉ）  をそれぞれ復号鍵、暗号化鍵とする。ＲＳＡによるメッセージｍの暗号化は、まず、乱数ｒを選び、ｍとｒを結合してｍ‖ｒとする。次に、Ｍ：＝（ｍ‖ｒ）ｄｉｍｏｄ  ｎｉとして暗号化メッセージＭを得る。以下では、サーバＵｉの暗号化鍵（ｅｉ，ｎｉ）  を使ったこの暗号化手順をＥｉ（ｍ，ｒ）と書く。
【０００４】
ｊ番目の利用者は、送信すべきメッセージｍｊを
Ｍ１：＝Ｅ１（Ｅ２（…（ＥＬ（ｍｊ，  ｒｊＬ），  …），  ｒｊ２），  ｒｊ１）
のように、全サーバの暗号化鍵（ｅｉ，ｎｉ），ｉ＝１，２，…，ＬとＬ個の乱数ｒｊ１，ｒｊ２，…，ｒｊＬを用いて多重に暗号化し、サーバＵ１へ送付する。
サーバＵ１は、複数の利用者から暗号化されたメッセージＭ１，Ｍ２，．．．  が集まった後、これらを鍵（ｄ１，ｎ１）  で復号し、各メッセージｍｊに対応するＥ２（…（ＥＬ（ｍｊ，ｒｊＬ），…），ｒｊ２）  及びｒｊ１を得る。サーバＵ１はそれぞれの暗号化メッセージから得られたＥ２（…（ＥＬ（ｍｊ，ｒｊＬ），…），ｒｊ２），  ｊ＝１，２，．．．の順序をランダムに置換し、サーバＵ２へ送付する。この際、サーバＵ１は各メッセージｍｊに付けられた乱数ｒｊ１を秘密とすることで、サーバＵ２へ送付された各Ｅ２（…（ＥＬ（ｍｊ，  ｒｊＬ），…），ｒｊ２）がサーバＵ１へ入力された暗号化メッセージＭ１，Ｍ２，．．．  のどれに関する復号結果であるかを判別できないようにすることができる。
【０００５】
以下、サーバＵ２，…，ＵＬも同様の処理を繰り返す。最後にサーバＵＬは、各メッセージｍｊを公開する。少なくとも一つのサーバＵｉが乱数ｒｊｉ  及び置換の順序を秘密に保つことにより、各利用者からサーバＵ１に入力された暗号文と、サーバＵＬが出力したメッセージとの関連は隠蔽され、匿名通信路として機能する。
上記従来法によれば、各サーバが与えられた動作を行わず、不正に計算された、あるいは本来のものと置き換えた結果を出力してもその出力が不正であることを誰も検証することができない。
【０００６】
検証を可能とする第一の方法として、例えばＭａｓａｙｕｋｉ  Ａｂｅによる”ＵｎｉｖｅｒｓａｌｌｙＶｅｒｉｆｉａｂｌｅ  Ｍｉｘ−ｎｅｔ  ｗｉｔｈ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｗｏｒｋ  Ｉｎｄｅｐｅｎｄｅｎｔ  ｏｆ  ｔｈｅ  Ｎｕｍｂｅｒ  ｏｆ  Ｍｉｘ−ｓｅｒｖｅｒｓ”，  ＥＵＲＯＣＲＹＰＴ９８，  ５月３１日、で提案されている方法がある。即ち、サーバ群はまず置換処理を実行し、各サーバの出力が正しいことを互いに証明、検証する。その後に、復号処理を実行し、各サーバの復号処理の出力が正しいことを互いに証明、検証する。この方法の問題点は、各サーバが行う証明、検証に多くの計算コストがかかる点にある。例えば、置換処理において、入力Ｉ１，…，ＩＮをランダム化し、更にランダムに置換した結果をＯ１，…，ＯＮとすると、この出力が正しい手順で処理されたものであることを、処理中のランダムな要素を見せることなく証明するには、以下のようにする。Ｉ１，…，ＩＮを同様の手順で撹乱し、ランダムに置換し、その結果をＯ’１，…，Ｏ’Ｎとする。このとき、同型性が成り立つようなランダム化手順を用いると、Ｏ’１，…，Ｏ’Ｎは、Ｏ１，…，ＯＮに対するランダム化の結果であると見なすこともできる。ここで、検証者はランダムに０／１  のチャレンジを選択して証明者に渡す。証明者はチャレンジが０のとき、｛Ｉ１，…，ＩＮ｝→｛Ｏ’１，…，Ｏ’Ｎ｝の置換・ランダム化処理に用いたランダム要素を全て公開する。また、チャレンジが１の時には、｛Ｏ１，…，ＯＮ｝→｛Ｏ’１，…，Ｏ’Ｎ｝のランダム化処理に相当するランダム要素を公開する。ランダム要素を入手すれば、全ての処理手順は確定的に再現することができるので、検証者はその入出力関係が正しいことを検証することができる。上記手順で証明者による不正を検出できない確率は、証明者がチャレンジを推測して当てる確率と等しく、１／２  であるので、証明者と検証者は上記手順を任意のｋ回数繰り返して、（１／２）ｋの誤り確率で処理の正しさを証明、検証する。従って、Ｎ入力での全体の効率はＮｋに比例する。高度の信頼性を確保するには、ｋ＝８０程度とするのが一般的である。
【０００７】
検証を可能にする第２の方法として、例えば、匿名通信路に応用することは述べられてないが、Ｒ．Ｃｒａｍｅｒ，Ｉ．Ｄａｍｇａｒｄ  ，Ｂ．Ｓｃｈｏｅｎｍａｋｅｒｓによる文献，“Ｐｒｏｏｆｓｏｆ  Ｐａｒｔｉａｌ  Ｋｎｏｗｌｅｄｇｅ  ａｎｄ  Ｓｉｍｐｌｉｆｉｅｄ  Ｄｅｓｉｇｎ  ｏｆ  Ｗｉｔｎｅｓｓ  Ｈｉｄｉｎｇ  Ｐｒｏｏｆｓ”，Ｐｒｏｃ．  ｏｆ  Ｃｒｙｐｔｏ  ’９４  ，ＬＮＣＳ  ８３９，ｐｐ．１７４−１８７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇに示される方式によれば、Ｎ入力の置換に対する証明は、Ｎ２  の計算コストで行うことができる。以下にその概略を示す。まず、Ｉ１をランダム化した結果がＯ１  であるとすると、零知識対話証明を用いてＩ１とＯ１  の関係をそのランダム化に用いたランダム要素を明かすことなく証明することが可能である。このような零知識対話証明では、
１．証明者は検証者にコミットメントと呼ばれるランダムなメッセージＴを送付する、
２．検証者は、証明者にチャレンジと呼ばれるランダムな値Ｃを送る、
３．証明者はコミットメントＴとチャレンジＣに基づいて、ある検証式を満たす値Ｚを検証者に送る、
という手順を実行し、検証者は、（Ｔ，  Ｃ，  Ｚ，  Ｉ１，  Ｏ１）が所定の検証式を満たすか否かを検査することによって、Ｉ１とＯ１  の関係の正当性を検証する。このような証明系において、証明者がＴを作る前にＣの値を知らなければ、検証式を満たすようなＺの値を返すことは、Ｉ１とＯ１  の関係が正当なものである場合にしかできない。しかし一方で、証明者が事前にＣの値を知っていれば、Ｉ１とＯ１  の関係が正当なものでなくても、検証式を満たすようなＴ，Ｚの値を求めることができる。この事実を利用すると、Ｉ１がＯ１，…，ＯＮのいずれか１つ以上に対して正当な関係であることを示すことができる。まず、証明者は、Ｃ２，…，ＣＮ及び対応するＺ２，…，ＺＮをランダムに選択する。次に、ｉ＝２，…，Ｎに対して、（Ｔｉ，Ｃｉ，Ｚｉ，Ｉ１，Ｏｉ）  が所定の検証式を満たすようにＴｉの値を決める。さらに、Ｔ１をランダムに選ぶ。この準備の後、
１．証明者は検証者にＴ１，…，ＴＮを送る、
２．検証者は、証明者にランダムに選んだＣを送る、
３．証明者はＣ１＝Ｃ（＋）Ｃ２（＋）…（＋）ＣＮのようにＣ１  を計算し、（Ｔ１，Ｃ１，Ｚ１，Ｉ１，Ｏ１）  が検証式を満たすような値Ｚ１を計算し、Ｚ１，…，ＺＮ及び、Ｃ１，…，ＣＮを検証者に送る、
という手順を実行する。ここで、（＋）  はビット毎の排他的論理和を意味する。検証者は全てのｉ＝１，…，Ｎについて（Ｔｉ，Ｃｉ，Ｚｉ，Ｉ１，Ｏｉ）  が所定の検証式を満たすことを検証し、更に、Ｃ＝Ｃ１（＋）…（＋）ＣＮ  が成り立つことを検査すればよい。証明者は、事前にＣの値を知らないので、少なくとも一つのＣｉについては、証明者が操作できない値とならざるを得ないため、Ｉ１は少なくとも一つのＯｉ  と正当な関係であることが確認できる。
【０００８】
【発明が解決しようとする課題】
この方法に因れば、Ｉ１→Ｏ１ｏｒ…ｏｒＯＮを示すために、Ｉ１→Ｏ１  の関係を示す為の証明のＮ倍の計算、通信コストが掛かることになり、結局、｛Ｏ１，…，ＯＮ｝→｛Ｏ’１，…，Ｏ’Ｎ｝を示す効率は、Ｎ２に比例する。従って、入力数Ｎが増大するとデータ処理量が膨大になる問題がある。
このように、上記従来法によれば、各サーバが行う証明、検証にはＮｋあるいはＮ２  に比例する計算量及び通信量が掛かるため、効率が悪い。
【０００９】
この発明の目的は、各サーバの出力が入力に対して適正な処理を行った後にその順序を置換したものであることをより少ない計算量、通信量で効率的に証明、検証する方法及び装置を提供することである。
【００１０】
【課題を解決するための手段】
この発明による検証可能匿名通信路は、
Ｎより小さいｎ個、ｎは２以上の整数、の入力をランダム置換し、秘密情報を用いて撹乱することによりｎ個の出力を出力し、任意の検証者に対して上記ｎ個の入力と上記ｎ個の出力を対応付ける上記秘密情報及び上記ランダム置換が確かに存在することを、使用した上記秘密情報及び上記ランダム置換を明かすことなく零知識証明により証明する処理を行なう単位置換処理手段と、
Ｎ個の入力に対しｎ個ずつ上記単位置換処理手段による処理を実行してＮ個の出力を得る第１繰り返し手段と、
初期入力として上記Ｎ個のメッセージに対し上記第１繰り返し手段による処理を実行して上記Ｎ個の出力を得、上記Ｎ個の出力を上記Ｎ個の入力として上記第１繰り返し手段を予め決めた回数繰り返し実行することにより上記Ｎ個のメッセージに一対一に対応する置換撹乱されたＮ個の出力メッセージを得る第２繰り返し手段、
とを含む。
【００１１】
この発明による検証可能匿名通信方法及びその方法を実施する記録媒体に記録されたプログラムは、以下のステップを含む：
（ａ）    Ｎより小さいｎ個、ｎは２以上の整数、の入力をランダム置換し、秘密情報を用いて撹乱することによりｎ個の出力を出力し、任意の検証者に対して上記ｎ個の入力と上記ｎ個の出力を対応付ける上記秘密情報及び上記ランダム置換が確かに存在することを、使用した上記秘密情報及び上記ランダム置換を明かすことなく零知識証明により証明する処理を行ない、
（ｂ）    Ｎ個の入力に対しｎ個ずつ上記ステップ（ａ）  による処理を実行してＮ個の出力を得て、
（ｃ）    初期入力として上記Ｎ個のメッセージに対し上記ステップ（ｂ）  による処理を実行して上記Ｎ個の出力を得、上記Ｎ個の出力を上記Ｎ個の入力として上記第１繰り返し手段を予め決めた回数繰り返し実行することにより上記Ｎ個のメッセージに一対一に対応する置換撹乱されたＮ個の出力メッセージを得る。
【００１２】
【発明の実施の形態】
この発明によれば、入力全体に対するランダム化及びランダム置換処理に対する証明、検証を行う代わりに、入力を少数に分割し、分割された各部分に対してその入出力関係の正当性を証明、検証するようにする。
例えば、複数の２入力２出力の切換スイッチ（入力の順序を入れ換えて出力するか、又はそのままの順序で出力するかを切り替えることができるスイッチ）を格子状に配置し、それぞれの段の出力と次段の入力を規則に従って接続することにより、２Ｌ個の入力に対する全ての置換を網羅することができるような置換網を構成する事ができることが知られている（Ａ．Ｗａｋｓｍａｎ，”Ａ  Ｐｅｒｍｕｔａｔｉｏｎ  Ｎｅｔｗｏｒｋ”，  Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  ＡＣＭ，Ｖｏｌ．１５，Ｎｏ．１，Ｊａｎｕａｒｙ  １９６８，ｐｐ．１５９−１６３．を参照）。４入力に対する置換網１０の構成を図１に示す。図１において、切換スイッチＳＷ１  は、（Ｏ１１，Ｏ１２）＝（Ｉ１１，Ｉ１２）のようにそのまま入力を出力とするか、あるいは（Ｏ１１，Ｏ１２）＝（Ｉ１２，Ｉ１１）のように順序を入れ換えて出力する。他のスイッチＳＷ２〜ＳＷ５でも同様の処理を行う。図１に示すように５つの切り換えスイッチを組み合わせて使うことにより、４入力に対し、４２＝１６通りの全ての置換を実現することが可能である。このような置換網を完全置換網と呼ぶことにする。一般的に、Ｎ個の入力に対してＮｌｏｇ２Ｎ−Ｎ＋１個の切換スイッチを用いることによって完全置換網を構成できることが知られている。
【００１３】
そこで、この発明では、この各置換スイッチＳＷ１  〜ＳＷ５  に対し、入力のランダム化とランダム置換の証明を行う機能を付加して単位の切り換え装置を構成し、それぞれの切り換え装置においてランダム置換の正当性の証明を行うことで、全体の置換に対する正当性を証明する。各切り換え装置が行う証明には前述の第二の方法を用いる。よって、例えば各切り換え装置への入力が２つの場合には、２２＝４  の計算コストで証明、検証が実行でき、全体の効率を４（Ｎｌｏｇ２Ｎ−Ｎ＋１）  程度に抑制することが可能である。
第１実施例
この発明による検証可能な匿名通信路は、図２に示すようにＮ個の暗号文Ｅ１，…，ＥＮ  が入力され、それらの復号結果を入力との対応関係がわからないようにランダム置換して出力する匿名通信路１００  と、そのランダム置換の正当性と復号の正当性を検証する検証端末２００  とから構成されている。この実施例では、匿名通信路１００  は入力暗号文Ｅ１，…，ＥＮを受付け、置換及び復号化して平文のリストＴｐを得、その置換及び復号化に対する検証に必要な情報Ｐｒｏｏｆを生成し、平文リストＴｐと共に検証端末２００  へ送付する。
【００１４】
匿名通信路１００  は完全置換網を形成するよう切換装置ＳＷ１〜ＳＷ５が接続されており、この発明によれば、各切換装置ＳＷがランダム置換を行ない、その置換の正当性を零知識証明で証明する証明Ｐｒｏｏｆ１〜Ｐｒｏｏｆ５を出力する。この実施例では、切換装置は復号を行なわず、入力暗号を変形し、置換網１０による処理後に、復号装置２０により復号を行なう場合を示しているが、後述の第４実施例のように、各切換装置ＳＷにおいて復号処理を行なってもよい。しかしながら、後者の場合、各切換装置ＳＷは秘密鍵を使用した復号についての零知識証明を行なう必要があるのに対し、前者の場合（第１実施例の場合）では、復号装置２０における復号に対して一括して零知識証明をするので、全体として処理量は少なくてすむ利点がある。
【００１５】
２つの予め決めた大きな素数をｐ，ｑとし、ｑはｐを割り切るものとする。Ｚｐ中の位数ｑの部分群をＧｑとし、ｇをＧｑのある要素とする。以下の説明中では、特に断りのない限り、全ての算術演算はｍｏｄｐで行うものとする。Ｅｌ  Ｇａｍａｌ暗号の復号鍵をｘ∈Ｚｑとし、暗号化鍵をｙ：＝ｇｘとする。暗号化鍵ｙは予め定められたｐ，ｑ，ｇと共に、後述する図３における置換網１０を構成している全ての切換装置ＳＷと、復号装置２０内のメモリ２３（図７）及び検証端末２００  ないのメモリ２２０に共通パラメータとして格納されているものとする。復号鍵ｘは復号装置２０にのみ格納されているものとする。
【００１６】
メッセージｍ∈Ｇｑ＊  のＥｌ  Ｇａｍａｌ暗号による暗号文をＥとすると、Ｅはある乱数ｔ∈Ｚｐに対し、
Ｅ：＝（Ｍ，  Ｇ）＝（ｍｙｔ，  ｇｔ）
となる。システムへの入力数Ｎを４とした場合のＥｌ  Ｇａｍａｌ暗号で暗号化された４つの暗号文をＥ１，Ｅ２，Ｅ３，Ｅ４とする。
図３に、４入力における匿名通信路１００  及び、検証端末２００  のブロック図を示す。また、各切換装置ＳＷ１〜ＳＷ５の構成を図４に示す。各切換装置ＳＷ内の切換部１２、置換証明部１４の構成をそれぞれ図５及び６に示す。匿名通信路１００  は置換網１０と復号装置２０から成り置換網１０では暗号文Ｅ１，  Ｅ２が切換装置ＳＷ１  に入力され、暗号文Ｅ３，  Ｅ４が切換装置ＳＷ２  に入力され、切換装置ＳＷ１  の２つの出力はそれぞれ切換装置ＳＷ３，  ＳＷ４に入力され、同様に切換装置ＳＷ２  の２つの出力はそれぞれ切換装置ＳＷ３，  ＳＷ４に入力され、切換装置ＳＷ３，  ＳＷ４の各２つの出力の一方は切換装置ＳＷ５  に入力され、他方の出力Ｒ１，  Ｒ２は復号装置２０に入力され、切換装置ＳＷ５  の２つの出力Ｒ３，  Ｒ４は復号装置２０に入力される。
【００１７】
入力暗号文Ｅ１〜Ｅ４、切換装置ＳＷ１〜ＳＷ５の各２つの出力はそれぞれ分岐されて検証端末２００  の置換検証部３０に入力され、この置換検証部３０には各切換装置ＳＷ１〜ＳＷ５の置換証明出力Ｐｒｏｏｆ１〜Ｐｒｏｏｆ５も入力されている。復号装置２０の４つの入力Ｒ１〜Ｒ４も分岐されて復号検証部４０に入力され、復号装置２０の復号証明出力ＰｒｏｏｆＤ及び平文Ｔｐを構成する復号メッセージｍ１，…，ｍ４も復号検証部４０に入力されている。検証端末２００  は制御部２１０  、メモリ２２０  を備えている。
【００１８】
切換装置ＳＷは、図４に示すようにｐ，ｑ，ｇ，ｙを保持しているメモリ１１と、２入力２出力の単に置換を行なう切換部１２と、乱数生成部１３と、置換が正当であることを証明するための置換証明部１４と、これら各部１１〜１４の動作を制御する制御部１５とから構成されている。切換部１２は図５に示すようにべき乗演算器１２Ａと、剰余乗算器１２Ｂと、順序入換器１２Ｃとから構成されている。又、置換証明部１４は、図６に示すようにべき乗乗算器１４Ａと、ハッシュ演算器１４Ｂと、剰余減算器１４Ｃと、剰余乗減算器１４Ｄとから構成されている。
【００１９】
以下は、切換装置ＳＷ１  における動作のステップである（図４参照）。
Ｓｔｅｐ１：ｐ，ｇ，ｙをメモリ１１から切換部１２へ入力する。
Ｓｔｅｐ２：乱数生成器１３を駆動して乱数ｂ∈｛１，  ２｝及びｔ１，  ｔ２∈Ｚｑ  を生成し、切換部１２へ入力する。
Ｓｔｅｐ３：切換部１２は以下のように動作する（図５参照）。
Ｓｔｅｐ３−１：  べき乗演算器１２Ａを駆動し、
【００２０】
【数１】
0003540718.tif 000002
を計算する。
Ｓｔｅｐ３−２：  べき乗演算器１２Ａの出力Ｔ１，Ｔ２及び、入力Ｉ１＝（Ｍ１，  Ｇ１），Ｉ２＝（Ｍ２，  Ｇ２）を剰余乗算器１２Ｂへ入力し、
【００２１】
【数２】
0003540718.tif 000003
を計算する。このべき乗演算と剰余乗算とにより秘密情報ｔ１，ｔ２で入力メッセージＩ１＝（Ｍ１，Ｇ１），Ｉ２＝（Ｍ２，Ｇ２）がランダム化される。
Ｓｔｅｐ３−３：  剰余乗算器１２Ｂの出力Ｒ１，Ｒ２及び乱数ｂを順序入換器１２Ｃへ入力する。順序入換器１２Ｃは、ｂ＝１  のとき、Ｏ１：＝Ｒ１及びＯ２：＝Ｒ２を、ｂ＝２  のとき、出力Ｏ１：＝Ｒ２及びＯ２：＝Ｒ１を出力する。この出力を、Ｏ１＝（Ｎ１，Ｈ１），Ｏ２＝（Ｎ２，Ｈ２）とおく。このようにランダム化された入力メッセージはその順序がｂによりランダム化され、即ち、ランダム置換される。
【００２２】
Ｓｔｅｐ４：図４中の乱数生成器１３を駆動し、乱数ｗ１，  ｗ２，  ｅｂ’，  ｚ１ｂ’，  ｚ２ｂ’∈Ｚｑを生成し、ｂ，ｔ１，ｔ２とともに置換証明部１４へ入力する。ここで、ｂ’はｂ＝１  のときｂ’＝２とし、ｂ＝２  のときｂ’＝１のように値を取るものとする。また、ｐ，  ｑ，  ｇ，  ｙをメモリ１１から置換証明部１４へ入力する。
Ｓｔｅｐ５：置換証明部１４は以下のように動作する（図６参照）。
置換証明部１４には切換部１２の２つの入力Ｉ１，  Ｉ２と２つの出力Ｏ１，  Ｏ２とがそれぞれ分岐入力されている。
Ｓｔｅｐ５−１：べき乗乗算器１４Ａを駆動し、
【００２３】
【数３】
0003540718.tif 000004
を計算する。
【００２４】
Ｓｔｅｐ５−２：ハッシュ演算器１４ＢへＩ１，Ｉ２，Ｏ１，Ｏ２，Ｓ１１，Ｓ１２，Ｓ２１，Ｓ２２を入力し、その出力をｃとする。
Ｓｔｅｐ５−３：ｃ及びｑ，ｅｂ’  を剰余減算器１４Ｃへ入力し、出力
ｅｂ：＝ｃ−ｅｂ’ｍｏｄｑ
を得る。
Ｓｔｅｐ５−４：ｅｂ及びｗ１，ｗ２，ｑ，ｂ，ｔ１，ｔ２を剰余乗減算器１４Ｄへ入力し、
ｚ１ｂ：＝ｗ１−ｅｂ・ｔ１ｍｏｄｑ
ｚ２ｂ：＝ｗ２−ｅｂ・ｔ２ｍｏｄｑ
を計算する。
【００２５】
Ｓｔｅｐ５−５：置換が正当であることをゼロ知識証明を使って証明するため
Ｐｒｏｏｆ１：＝（ｅ１，ｅ２，ｚ１１，ｚ１２，ｚ２１，ｚ２２）
を出力する。
置換網１０の終端で得られる出力をＲ１，Ｒ２，Ｒ３，Ｒ４とする。このとき、各ＲｉをＲｉ＝（Ｍ’ｉ，Ｇ’ｉ）とおくと、以下の関係が成り立つ。
Ｍ’ｉ＝ｍＦ（ｉ）ｙｔ’
Ｇ’ｉ＝ｇｔ’
ここで、Ｆ（＊）は｛１，２，３，４｝→｛１，２，３，４｝なる置換関数の一つである。即ち、ＲｉはメッセージｍＦ（ｉ）に対する通常のＥｌ  Ｇａｍａｌ暗号文であり、復号は通常のＥｌ  Ｇａｍａｌ復号手順で行うことができる。
【００２６】
復号装置２０は図７に示すように復号部２１と、復号証明部２２と、メモリ２３と、これらの動作を制御する制御部２４とから構成されている。復号部２１は図８に示すようにべき乗演算器２１Ａと、剰余除算器２１Ｂとから構成されている。又、復号証明部２２は図９に示すように、乱数生成部２２Ａと、べき乗演算器２２Ｂと、ハッシュ演算器２２Ｃと、剰余乗減算器２２Ｄとから構成されている。
【００２７】
復号装置２０は、Ｒ１〜Ｒ４を順次以下のように処理する。
Ｓｔｅｐ１：制御部２４は入力Ｒｉを順次受信し、復号部２１へ入力する。また、メモリ２３からｘ，ｐを復号部２１へ入力する。
Ｓｔｅｐ２：復号部２１では、図８に示すようにべき乗演算器２１ＡへＧ’ｉ  及びｘ，ｐを入力し、
Ｋｉ：＝Ｇ’ｉｘｍｏｄｐ
を計算する。
【００２８】
Ｓｔｅｐ３：Ｍ’ｉ，ｐ及び、べき乗演算器２１Ａの出力を剰余除算器２１Ｂへ入力し、
ｍｉ：＝Ｍ’ｉ／Ｋｉｍｏｄｐ
を計算し、復号結果として出力する。
続いて、復号装置２０は正しく復号が行われたことを証明するＰｒｏｏｆＤを、復号証明部２２により以下のように作成する。
【００２９】
Ｓｔｅｐ１：復号証明部２２は図９に示すように乱数生成器２２Ａにより乱数ｗ∈Ｚｑを生成し、べき乗演算器２２Ｂへ入力する。
Ｓｔｅｐ２：べき乗演算器２２Ｂは、まずＴ０：＝ｇｗｍｏｄｐを計算し、次に、各Ｇ’ｉ  に対してＴｉ：＝Ｇ’ｉｗｍｏｄｐを計算し、Ｔ０，…，ＴＮをハッシュ演算器２２Ｃへ入力する。この例ではＮ＝４  である。
Ｓｔｅｐ３：ハッシュ演算器２２Ｃは、ｃ：＝Ｈａｓｈ（ｙ，Ｔ０，Ｋ１，Ｔ１，…，ＫＮ，ＴＮ）を計算し、ｃを剰余乗減算器２２Ｄへ入力する。
【００３０】
Ｓｔｅｐ４：剰余乗減算器２２Ｄはｚ：＝ｗ−ｃｘ（ｍｏｄｑ）を計算し、ｃ，  ｚ，  Ｋ１，…，  ＫＮと共に出力する。
このとき、ＰｒｏｏｆＤ：＝（ｃ，ｚ，Ｋ１，…，ＫＮ）とする。
検証端末２００  は、まず、置換が正しく実行されたことを確認するため、置換検証部３０を駆動する。置換検証部３０は図１０に示すようにべき乗乗算器３１と、ハッシュ演算器３２と、比較器３３と、加算器３４とから構成されている。置換検証部３０は、ｉ番目の切換装置ＳＷｉ  によるＰｒｏｏｆｉを以下のように検証する。
Ｓｔｅｐ１：べき乗乗算器３１を駆動し、
【００３１】
【数４】
0003540718.tif 000005
を計算する。
【００３２】
Ｓｔｅｐ２：Ｓ１１，Ｓ１２，Ｓ２１，Ｓ２２及びＩ１，Ｉ２，Ｏ１，Ｏ２をハッシュ演算器３２へ入力し、その出力ｃを比較器３３へ入力する。
Ｓｔｅｐ３：ｅ１，ｅ２を加算器３４へ入力し、ｅ１＋ｅ２を計算する。その結果を、比較器３３へ入力する。
Ｓｔｅｐ４：比較器３３へｑを入力し、ｅ１＋ｅ２＝ｃ（ｍｏｄｑ）が成り立つか否かを検査する。成り立つ場合はＯＫを、成り立たない場合はＮＧを出力する。このようにして置換が正しく行われたことは、その置換を生じさせた乱数ｂを示すことなく零知識証明により検証される。
【００３３】
上記の検証を全ての切換装置の入出力に対して行い、ＮＧとなるような証明を出力した切換装置が存在した場合はその切換装置は故障しているものと見なす。上記検証が全てＯＫの場合、次に、復号が正しく行われたこと検証するため、復号検証部４０へＲ１，  …，  Ｒ４，  ｍ１，  …，  ｍ４及びＰｒｏｏｆＤを入力する。図１１に復号検証部４０のブロック図を示す。復号検証部２２０  は、剰余除算器４１と、比較器４２と、べき乗乗算器４３と、ハッシュ演算器４４と、比較器４５とから構成され、以下のように復号化の検証を行う。
【００３４】
Ｓｔｅｐ１：剰余除算器４１へＭ’ｉ  とＫｉを入力してＭ’ｉ／Ｋｉを計算し、その結果をｍｉと共に比較器４２へ入力して比較する。両者が等しくない場合には、比較器４２はＮＧを出力し、検証結果をＮＧとする。全てのｉ＝１，  …，  Ｎに対して比較結果がＯＫならば、次のステップへ進む。
Ｓｔｅｐ２：べき乗乗算器４３を駆動し、ｇｚｙｃ及び、Ｇ’１ｚＫ１ｃ，…，Ｇ’ＮｚＫＮｃを計算し、ハッシュ演算器４４へ入力する。
【００３５】
Ｓｔｅｐ３：ハッシュ演算器４４を駆動し、
ｅ：＝Ｈａｓｈ（ｙ，ｇｚｙｃ，Ｋ１，Ｇ’１ｚＫ１ｃ，  …，ＫＮ，  Ｇ’１ｚＫ１ｃ）
を計算する。
Ｓｔｅｐ４：ｃ及び、ハッシュ演算器４４が出力したｅを比較器４５へ入力し、両者が等しければＯＫを、等しくなければＮＧを出力する。
復号が正しく行われた場合には、
ｇｚｙｃ＝ｇｗ−ｃｘｙｃ＝ｇｗ＝Ｔ０  
及び、
Ｇ’ｉｚＫｉｃ＝Ｇ’ｉｗ−ｃｘＫｉｃ＝Ｇ’ｉｗ＝Ｔｉ
が成り立つので、ハッシュ演算器４４の出力はｃと等しくなる。
【００３６】
この実施例では、各切換装置で用いたランダムな要素、即ち、ｂ，  ｔ１，  ｔ２，  ｗ１，ｗ２が全て秘密に保たれる場合には、Ｅｉ→ｍｊの対応はどのようなｉ，  ｊについても秘匿される。この様に、この第１実施例においては、それぞれの切り換え装置におけるランダム置換の正当性をそれぞれの切り換え装置で証明するよう構成しているため、特に匿名通信路の全入力の数Ｎが増大すると前述したＲ．Ｃｒａｍｅｒ等の方法でランダム置換の正当性を証明する場合に比べ、必要なデータ処理量が著しく少なくてすむ。
第２実施例
この実施例ではいくつかの切換装置におけるランダム要素が漏洩した場合についても全体として各入出力の対応が秘匿されるような構成について説明する。
【００３７】
この実施例では、図１２に示すようにいくつかの切換装置の仕事を順次実行する「置換サーバ」を用い、Ｖ個の置換サーバＰＳ１，．．．，ＰＳ４によって置換網１０を構成する。また、復号を実行する復号サーバ２０Ｓを用いる。以下では、Ｖ＝４  個の置換サーバを用い、入力が４メッセージである場合について説明する。各置換サーバＰＳ１〜ＰＳ４及び検証端末２００  は掲示板４００  に接続されているものとする。掲示板４００  は、認証された利用者からの書き込みＥ１，  Ｅ２，  ．．．，ＥＮを受け付け、一旦書き込んだ情報は消すことができないという機能を有する。また、書き込まれた情報は誰もが読み出すことができるものとする。この実施例も、第１実施例と同様に置換網１０内の各置換サーバＰＳが有する各切換装置ＳＷ（図１３）は復号を行なわず、入力暗号のランダム化（暗号の変換）とランダム置換を行ない、最後に復号サーバが復号を行なう。
【００３８】
図１３に各置換サーバＰＳのブロック図を示す。置換サーバＰＳ中の切換装置ＳＷの構成は制御部１５とメモリ１１が切換装置の外側にあることを除いて図４の切換装置ＳＷと同様である。
図１４に復号サーバ２０Ｓのブロック図を示す。復号サーバ２０Ｓは置換検証部３０Ｓ、復号部２１Ｓ、復号証明部２２Ｓを有しており、これらはそれぞれ図１０、８、９に示した置換検証部３０、復号部２１、復号証明部２２と同様である。復号サーバは更にメモリ２３Ｓと制御部２４Ｓを有している。
【００３９】
このシステムは、４つの置換サーバＰＳ１，．．．，ＰＳ４によって、４入力の完全置換網を２つ構成した場合である。この場合のデータの流れを図１５に示す。図中には示してないが、置換サーバ間のデータの転送は全て図１２に示したように掲示板４００  を介して行われる。即ち、各置換サーバＰＳｊ  は、置換出力を掲示板４００  に書き込み、次段の置換サーバＰＳｊ＋１  はそのデータを掲示板４００  から読み込んで置換処理を行う。置換サーバＰＳ１は、第１実施例における切換装置ＳＷ１  とＳＷ２  の仕事を実行し、掲示板４００  を介して処理結果を置換サーバＰＳ２へ送出する。以下同様に、置換サーバＰＳ２は切換装置ＳＷ３，ＳＷ４，ＳＷ５、置換サーバＰＳ３は切換装置ＳＷ６，ＳＷ７、置換サーバＰＳ４は切換装置ＳＷ８，ＳＷ９，ＳＷ１０の仕事を実行する。図１３に示すように、実際に各置換サーバＰＳ内に設置される切換装置ＳＷの数は１つであり、適切な入力を制御部１５が与えることによって図１５のデータの流れを実現する。あるいは、実際に複数の切換装置ＳＷを１つの置換サーバに設置しても良い。
【００４０】
図１２、１５に示すように、縦続接続された置換サーバＰＳ１〜ＰＳ４は少なくとも２つの縦続接続された完全置換網を形成している。各置換サーバＰＳの出力は、掲示板４００  に接続された置換検証部３０Ｓを持つ復号サーバ２０Ｓによって第１実施例の場合と同様に置換Ｐｒｏｏｆ  が検証され、不正な入出力関係が検出された場合はその置換サーバを故障しているものと見なす。その場合、故障とみなした置換サーバを排除して別の置換サーバで処理を代行するか、あるいは、故障した置換サーバが１つだけならば、その置換サーバによる処理を省略してしまっても良い。
【００４１】
復号サーバ２０Ｓは、全ての置換が正しいことを検証した後、復号部２１Ｓで置換網１０の出力（最終段置換サーバＰＳＶ  の出力）を復号すると共に、復号証明部２２Ｓで、復号証明ＰｒｏｏｆＤを生成し、掲示板４００  に書き込む。検証端末２００  は各置換サーバにより掲示板４００  に書き込まれている各置換Ｐｒｏｏｆ１〜Ｐｒｏｏｌ４からを検証し、更に復号サーバにより書き込まれた復号結果（メッセージｍ１，．．．，ｍＮ）と復号証明ＰｒｏｏｆＤを第１実施例と同様の手順で検証する。
【００４２】
上記の構成によれば、ある置換サーバが攻撃されるなどして、ランダム要素が漏洩してしまい、その置換サーバにおける置換が第三者に明らかになってしまった場合に於いても、残りの置換サーバにおけるランダム要素の秘匿性が保たれる限りは、全体の置換関係は秘密に保たれる。例えば、置換サーバＰＳ１の実行した置換関係が明らかになっても、置換サーバＰＳ３、置換サーバＰＳ４で完全な置換網を構成しているので、入出力のどのような置換関係も実現し得る。同様に、どの１つの置換サーバの置換関係が漏洩しても、必ず他の２つの置換サーバによって完全な置換網が構成されており、それによって、秘匿性を保つことが可能である。
第３実施例
図１６に示す第３実施例では、第２実施例における復号サーバ２０Ｓ  を複数の復号サーバ２０Ｓ１，…，２０ＳＬに分割して、複数の復号サーバ全体で単一の復号サーバを用いた場合と同一の機能を実現する。この実施例によれば、あるｔ＜Ｌなるｔに対して、少なくともｔ＋１  個の復号サーバ２０Ｓ  が正常に動作すれば正しい結果を得ることができるため、耐故障性が向上する。又、図１２の復号サーバ２０Ｓ  が１つの場合には、復号サーバ２０Ｓ  が復号を開始すればいつでも復号結果を得ることができるので、例えば投票の集計を予め決めた時間に公表する前にその投票結果の内容を不正に洩らしてしまうことが起こりえる。これに対し、図１６の実施例では、前復号サーバ２０Ｓ１〜２０ＳＬが処理を終了しないと復号結果が得られないので、これらのサーバのうち少なくともｔ＋１  個の復号サーバが協力して不正を行なわない限りどの復号サーバからも復号結果が公表前に洩れてしまうことはない。
【００４３】
復号サーバを除くシステム構成は第２実施例と同様である。各復号サーバＤｉには復号鍵ｘをｔ次の多項式で秘密分散した値ｘｉが格納されているものとする。即ち、Ｆ（０）＝ｘ（ｍｏｄｑ）を満たす、ｔ＜Ｌなるあるｔ次のランダム多項式Ｆ（Ｘ）∈Ｚｑ［Ｘ］  があり、各ｘｉはｘｉ＝Ｆ（ｉ）ｍｏｄｑ  を満たす値である。各復号サーバ２０Ｓｊの構成は、図１４に示した復号サーバ２０Ｓにおいてｘの代わりにｘｉをメモリ２３Ｓに格納すること及び、復号部２１Ｓの内部構成を除き、図１４と同様である。この実施例の復号サーバにおける復号部２１Ｓは図１７に示すように、べき乗乗算器２１ＳＡと有し、これは図８に示したべき乗乗算器２１Ａと同様の処理を行なう。
【００４４】
置換サーバＰＳ１，．．．，ＰＳＶの構成、動作は図１２に示した第２実施例と同様である。各復号サーバ２０Ｓｔは、全ての置換サーバＰＳ１，．．．，ＰＳＶの入出力関係を第２実施例と同様に検証する。最終段の置換サーバＰＳＶ  から正しい置換出力Ｒ１〜ＲＮが得られ、置換検証が完了した後、各復号サーバは復号を実行する。ｊ番目の復号サーバ２０ＳｊはＲ１〜ＲＮを順次以下のように処理する。
Ｓｔｅｐ１：制御部は入力Ｒｉを順次受信し、復号部２１Ｓ（図１４参照）へ入力する。また、メモリ２３Ｓからｘｉ，ｐを復号部２１Ｓへ入力する。
【００４５】
Ｓｔｅｐ２：復号部２１Ｓ（図１７参照）では、べき乗演算器２１ＳＡへＧ’ｉ  及びｘｊ，  ｐを入力し、Ｋｊ，ｉ：＝Ｇ’ｉｘｊを計算する。
続いて、復号証明部２２Ｓ（図１４参照）は正しく復号が行われたことを証明するＰｒｏｏｆＤｊ  を、復号証明部を駆動して作成する。実際の動作は、第１実施例の復号証明動作においてｘをｘｊに、ｙをｙｊに入れ換えた場合と同様である。この証明部の出力を
ＰｒｏｏｆＤｊ：＝（ｃｊ，  ｚｊ，  Ｋｊ，１，…，Ｋｊ，ｎ）
とする。
【００４６】
検証端末２００  の構成は図２と同様である。但し、復号検証部４０は図１８に示す構成となる。この復号検証部の動作は、第１実施例における復号検証部の動作のＳｔｅｐ２〜４と同様である。ｔ＋１  以上の復号サーバに対する検証がＯＫとなるならば、検証端末はＯＫを出力する。
この実施例では、復号サーバ２０Ｓｊの出力はＫｉ，ｊであり、実際に各復号結果ｍｉを得るには以下の手順を実行する。まず、Ａ⊆｛１，…，Ｌ｝を、｜Ａ｜＞ｔ＋１となるように定める。ただし、ｊ∈Ａなるｊに対して、復号サーバ２０Ｓｊの出力は、復号検証に合格していなければならない。今、λｊ  ，Ａを次式
【００４７】
【数５】
0003540718.tif 000006
で定義される補間係数とする。すると、メッセージｍｉは次式
【００４８】
【数６】
0003540718.tif 000007
で得ることができる。これは、ｘ＝Σλｊ，ＡＡｘｊｍｏｄｑ（Σはｊ∈Ａについて）が成り立つため、
【００４９】
【数７】
0003540718.tif 000008
となり、第１実施例における復号動作と等価になる為である。
上記計算手順を各復号サーバが実行することも可能である。その場合には、第１実施例と同様の検証手順で復号検証を行えばよい。
第４実施例
前述の第２及び第３実施例においては各置換サーバＰＳは入力された複数の暗号文を撹乱し、かつその入力の順番をランダムに入れ換えて次の置換サーバへ送ることを順次行ない、最終段の置換サーバが出力した暗号文を復号サーバが復号して平文を得る。得られた平文は誰れにより投票されたものであるかは不明であるが、正しく投票されたものであることを検証できる。
【００５０】
この第２及び第３実施例では、不正な処理を行なった置換サーバが検出された場合、例えばＶ個の置換サーバのうちｔ個の出力が信頼できなかった場合、不正処理を回復する為には、ｔ回の不正回復処理を行うことが考えられる。匿名通信路の信頼度が下がれば下がる程（即ち、ｔが大きくなる程）、不正回復処理に要する時間が大となり、匿名通信路としての処理能力が下がる事になる。
以下に説明する第４実施例は、匿名通信路の信頼度が、ある程度低くなっても、検証可能匿名通信路としての機能を保ちつつ、効率的に不正回復を行い、必要とされる帯域（通信速度）を確保する。
【００５１】
第１、第２及び第３実施例では、各切換装置ＳＷ，あるいは置換サーバにおいては復号化処理を行なわず、復号化装置又は復号サーバにおいて一括して復号を行なう場合を示したが、この第４実施例では、各置換サーバにおいて部分復号化を行なう場合を示す。ただし、各置換サーバでは、それぞれの置換段で入力暗号文Ｉを変換し、部分復号化は置換の最終段においてまとめて行なうことにより、各置換段において部分復号化を行なうよりは処理速度を高めている。
【００５２】
この実施例では以下、各置換サーバで行われる部分復号処理をｆとし、任意の秘密鍵Ｘを持った置換サーバの任意の入力文Ｉに対応する出力文をｆＸ（Ｉ）  とする。
各置換サーバで行われる部分復号処理ｆを次のような処理に限定する。
・交換可能
任意の秘密鍵Ａ，Ｂに対してｆＡ（ｆＢ（Ｉ））＝ｆＢ（ｆＡ（Ｉ））  なる関係が成り立つ。
・一括復号化可能
任意で既知の秘密鍵Ａ，Ｂに対してｆＡ（ｆＢ（Ｉ））＝ｆｇ（Ａ，Ｂ）（Ｉ）なる関数ｇ（Ａ，  Ｂ）が存在し、ｆＡ  （ｆＢ（Ｉ））の計算に対してｆｇ（Ａ，Ｂ）（Ｉ）の計算が高速に実行可能である。
【００５３】
このような前提においてこの実施例では、ある置換サーバの出力が信頼できない場合、その置換サーバより上流で最も近くにある、不正処理がないと判定された置換サーバの信頼できる情報のみを用いてランダム置換・撹乱・部分復号処理を行ない、不正処理に対する補償動作を行わずに次の処理を進める。
各置換サーバの秘密鍵は、予め他の全ての置換サーバに検証可能に秘密分散されており、信頼できない置換サーバが検出された場合、残りの各置換サーバはそれより上流の信頼できる置換サーバの情報を使ってランダム置換・撹乱・部分復号処理を行ない、全ての信頼できる置換サーバによる処理が完了した段階で、信頼できない置換サーバの分散秘密鍵の全てを信頼できる置換サーバが集めて共同で復元する。信頼できない置換サーバが部分復号処理することになっていた情報部分についての部分復号処理（補償動作）を、信頼できない置換サーバの復元秘密鍵の全てを用いて、一括して行う。この一括処理によって、複数の置換サーバの出力が信頼できない場合でもたった１回の補償動作を行うだけで不正回復を行う事が可能である。
【００５４】
この第４実施例においては、置換サーバが用いる交換可能でかつ一括化可能な部分復号処理の一例として以下の説明ではＥｌ  Ｇａｍａｌ分散復号系を挙げる。一般化されたＥｌ  Ｇａｍａｌ暗号系においても、上記性質が満たされれば適用可能である（例えば楕円Ｅｌ  Ｇａｍａｌ暗号）。
この第４実施例ではいくつかの置換サーバにおけるランダム要素が漏洩した場合についても全体として各入出力の対応が秘匿されるような構成について説明する。
【００５５】
この実施例では、いくつかの証明付きランダム置換・撹乱・部分復号の仕事を順次実行する置換サーバを用い、Ｖ個の置換サーバによって匿名通信路を構成する。
図１９はこの第４実施例のシステム構成例であり、図１２及び１６の実施例と同様に置換サーバＰＳ１〜ＰＳＶは掲示板４００  に接続されている。この実施例では各置換サーバに他の置換サーバの処理に対する検証機能と入力暗号文に対する部分復号機能を持たせているため、図１２及び１６の実施例のような検証サーバ及び復号サーバは設けられてない。各置換サーバは、第２及び第３実施例における各置換サーバ内の複数の切換装置ＳＷにより構成された置換部に対応する置換部Ｐ５０  に加えて、他の置換サーバの処理に不正がないかを判定する判定部Ｐ６０  と、ランダム置換・部分復号の証明を行なう検証部Ｐ７０  を有している。置換サーバＰＳ１〜ＰＳ５の置換部Ｐ５０１〜Ｐ５０５は掲示板４００  を介して図１９に示すように縦続接続される。各置換部Ｐ５０１〜Ｐ５０５は置換・撹乱部分復号を行う複数の切換装置ＳＷを有している。検証端末２００  は独立して設けるのではなく、それぞれの置換サーバに設けられている。
【００５６】
図２０は図１のシステムにおける置換サーバ間の掲示板４００  を介したデータの流れを、掲示板を省略して示すため、図１９における置換サーバＰＳ１〜ＰＳ５内の置換部Ｐ５０１〜Ｐ５０５のみを示している。これら５つの置換部Ｐ５０１〜Ｐ５０５はこの例では縦続接続された２つの置換部Ｐ５０１とＰ５０２で１つの８入力完全置換網を形成し、縦続接続された２つの置換部Ｐ５０３とＰ５０４で同様に１つの８入力完全置換網を形成し、置換部Ｐ５０５は単独で８入力完全置換網を形成している。従って、全体で縦続接続されたこれら３つの８入力完全置換網を形成している。
【００５７】
各８入力完全置換網を形成するには４×５格子上に配列された全ての２入力２出力の単位切換装置ＳＷが切換可能である必要はなく、破線ブロックで示す切換装置ＳＷでは入出力位置関係を固定しても、残りの切換装置の切換の組み合わせて全ての組の置換が実現できる。そこで、置換サーバでの処理量を削減するため、このような入出力関係を固定してもよい切換装置では入力データに対する置換処理は行なわない。これらの固定接続切換装置をＳＷＦで示してある。しかしながら、この発明の目的とする匿名通信路を構成する置換網を通して暗号文を復号する場合、入力データに対し選択された経路によって復号処理を受ける回数が異なると復号処理が複雑になり不都合である。
【００５８】
この発明ではこのような固定接続切換装置ＳＷＦにおいても、入力データに対し置換処理以外の処理（撹乱、部分復号、証明生成など）は実施する。以下の説明では置換・撹乱・部分復号・証明生成などの全ての処理を実施する切換装置ＳＷを証明付ＰＲ部分復号器と呼び、置換を行なわない切換装置ＳＷＦを証明付固定部分復号器と呼ぶ。また置換撹乱（ｐｅｒｍｕｔａｔｉｏｎ／ｒａｎｄｏｍｉｚａｔｉｏｎ）を単にＰＲで表す。
【００５９】
図１９の実施例では、入力が８メッセージであり、５つの置換サーバＰＳ１〜ＰＳ５を用い、５つのうち２つの置換サーバの処理に不正である場合でも正しい置換・撹乱・部分復号を実行出来るものである。各置換サーバＰＳ１〜ＰＳ５の構成要素の証明付きＰＲ部分復号器ＳＷは図２１または図２８に示すように構成され、証明付き固定部分復号器ＳＷＦは図２７に示すように構成される。これらについては後で詳述する。各置換サーバＰＳ１〜ＰＳ５はそれぞれ検証器Ｐ７０  を備える。各検証器Ｐ７０  はＰＲ証明検証器Ｐ７０Ａと、部分復号証明検証器Ｐ７０Ｂと、及びＰＲ部分復号証明検証器Ｐ７０Ｃをもって構成される。
【００６０】
掲示板４００  は、認証された利用者からの暗号文の書き込みを受け付け、一旦書き込んだ情報は消すことができないという機能を有する。書き込まれた情報は誰もが読み出すことができるものとする。
このシステムは、５つの置換サーバＰＳ１〜ＰＳ５によって、それぞれ８入力の縦続接続された３つの完全置換網１０Ａ〜１０Ｃからなる匿名通信路１００  を構成している。３つの完全置換網１０Ａ〜１０Ｃのうち２つの完全置換網のランダム要素が漏洩しても残った完全置換網によって入出力の対応関係を完全に秘匿することが出来る。
【００６１】
置換サーバＰＳ１〜ＰＳ５は予め決めた順番でデータの処理を行ない、各置換サーバは自段より前段の置換サーバの入出力データと証明情報を掲示板４００  から読み込む。その入力の際に自身が持つ検証器Ｐ７０  によってその前段の置換サーバの信頼性をその入出力データと証明情報に基づいて検証し、不正な入出力関係が検出された場合、つまり出力の信頼性がない場合はその置換サーバは故障しているものと見なす。その場合、不正のない置換サーバが見つかるまで順番を遡り、不正でないと判断された最も近い置換サーバの出力を使って処理を行う。
【００６２】
各置換サーバは他のどの置換サーバに対しても検証可能であり、不正な入出力関係が検出されない置換サーバ同士が協力して、不正な置換サーバが担当する復号処理に対する補償動作を行う。そのために、予め全ての置換サーバのもつ秘密鍵を全ての置換サーバが秘密分散によって共有しておく。
先にも述べたように、各置換サーバは複数の証明付きＰＲ部分復号器の仕事を順次実行するものであり、置換サーバ内の各証明付ＰＲ部分復号器ＳＷは、例えば図２１に示すように、証明付き置換撹乱器１２０  と証明付き部分復号器１４０  とよりなり、証明付き置換撹乱器１２０  は例えば置換撹乱器１２１  と置換撹乱証明生成器１２２  とよりなり、証明付き部分復号器１４０  は例えば２つの証明付部分復号器１４１、１４２  よりなる。
【００６３】
図２１は、２入力のＥｌ  Ｇａｍａｌ暗号文を置換撹乱処理し、秘密鍵の部分情報を用いて部分復号し、置換撹乱復号結果及びその正当性の証明を出力する証明付きＰＲ部分復号器ＳＷの構成の一例を表している。この証明付きＰＲ部分復号器ＳＷは図２０中の一括不正回復付き検証可能匿名通信路等に用いられる。
この証明付きＰＲ部分復号器ＳＷでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００６４】
Ｓｔｅｐ１：証明付き置換撹乱器１２０  は乱数情報内の各種情報を用いて入力の（Ｍ０，Ｇ０），（Ｍ１，  Ｇ１）を置換撹乱処理した結果の（Ｍ０＋，  Ｇ０＋），（Ｍ１＋，  Ｇ１＋）及びその正当性の証明である証明情報０を出力する。
Ｓｔｅｐ２：証明付き置換撹乱部分復号器ＳＷは（Ｍ０＋，  Ｇ０＋），（Ｍ１＋，  Ｇ１＋）を証明情報の一部として出力する。
Ｓｔｅｐ３：証明付き固定部分復号器１４０  は乱数情報内の各種情報を用いて入力の（Ｍ０＋，  Ｇ０＋），（Ｍ１＋，  Ｇ１＋）を部分復号した（Ｍ’０，  Ｇ’０  ），（Ｍ’１，  Ｇ’１）及びその正当性の証明である証明情報１を出力する。
【００６５】
なお、この証明付き置換撹乱部分復号器ＳＷにおける置換と、撹乱と、部分復号との処理順は任意に選らべる。ただしその処理順に応じて証明情報の内容が異なるものとなる。
置換撹乱器１２１  は例えば図２２に示すように置換器１２１Ａと撹乱器１２１Ｂ，１２１Ｃとよりなる。撹乱器１２１Ｂ、１２１Ｃは同じ構造であり、図２３に示すように２つの乗算器１２１Ｂ１と１２１Ｂ２を有している。以下これらの各部の機能構成を順次説明する。
撹乱器１２１Ｂ（１２１Ｃ）
図２３は図２２に示す撹乱置換器１２１  において入出力の対応を隠蔽する為に、入力のＥｌ  Ｇａｍａｌ暗号文を撹乱する撹乱器１２１Ｂ（１２１Ｃ）の構成の一例を表している。入力のＥｌ  Ｇａｍａｌ暗号文を（Ｍ，  Ｇ）とすると、平文ｍ及び公開鍵（Ｙ，  ｇ）  及び秘密鍵Ｘ及び乱数ｗに関して次式
Ｙ＝  ｇＸ  ，Ｇ＝  ｇｗ  ，Ｍ＝ｍＹｗ  
が成り立っている。入力暗号文（Ｍ，  Ｇ）  を撹乱するとは、撹乱処理を行う者以外には秘密の乱数ｒによりＭ及びＧの入力前に計算された秘密のパラメータｇ−ｒ及びＹ−ｒを用いて乗算器１２Ｂ１，  １２１Ｂ２で
Ｍ’  ←  Ｍ×Ｙ−ｒ，
Ｇ’  ←  Ｇ×ｇ−ｒ
をそれぞれ計算し（Ｍ’，  Ｇ’）  を出力することである。出力の（Ｍ’，  Ｇ’）  は
Ｍ’  ＝  ｍＹｗ−ｒ  ，Ｇ’  ＝  ｇｗ−ｒ  
を満たすので、平文ｍ及び公開鍵（Ｙ，  ｇ）  及び秘密鍵Ｘ及び乱数ｗ−ｒ  に関するＥｌ  Ｇａｍａｌ暗号文である。
【００６６】
この撹乱器１２１Ｂでは、以上の演算が実行されるが、同時実行可能な場合は、並列に実行しても良い。また実行順序が交換可能な場合は実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
置換撹乱器１２１
図２２は２入力のＥｌ  Ｇａｍａｌ暗号文（Ｍ０  ，  Ｇ０  ）及び（Ｍ１  ，Ｇ１  ）を撹乱置換する置換撹乱器１２１  の構成の一例を表している。Ｅｌ  Ｇａｍａｌ暗号文（Ｍ，  Ｇ）  を乱数ｒで撹乱して出来たＥｌ  Ｇａｍａｌ暗号文をＤ（Ｍ，  Ｇ，  ｒ）と記述する事にする。置換撹乱処理を行う者以外には秘密の置換パラメータＢ∈｛０，  １｝に従って、
Ｂ＝０  のとき
（Ｍ’０  ，  Ｇ’０  ）  ←  Ｄ（Ｍ０  ，  Ｇ０  ，  ｒ０  ）
（Ｍ’１  ，  Ｇ’１  ）  ←  Ｄ（Ｍ１  ，  Ｇ１  ，  ｒ１  ）
Ｂ＝１  のとき
（Ｍ’０  ，  Ｇ’０  ）  ←  Ｄ（Ｍ１  ，  Ｇ１  ，  ｒ０  ）
（Ｍ’１  ，  Ｇ’１  ）  ←  Ｄ（Ｍ０  ，  Ｇ０  ，  ｒ１  ）
なる出力メッセージ（Ｍ’０  ，  Ｇ’０  ）及び（Ｍ’１  ，  Ｇ’１  ）を出力する。
【００６７】
置換撹乱器１２１  は置換器１２１Ａと、撹乱器１２１Ｂ，  １２１Ｃとからなる。撹乱器１２１Ｂ及び撹乱器１２１Ｃは図２３に示したように２つの乗算器１２１Ｂ，  １２１Ｂ２から構成される。この置換撹乱器１２１  では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００６８】
Ｓｔｅｐ１：置換器１２１Ａはもし置換パラメータＢがＢ＝０  ならば、
（Ｌ０  ，  Ｌ１  ）  ←  （Ｍ０  ，  Ｇ０  ）
（Ｌ２  ，  Ｌ３  ）  ←  （Ｍ１  ，  Ｇ１  ）
とし、Ｂ＝１  ならば、
（Ｌ０  ，  Ｌ１  ）  ←  （Ｍ１  ，  Ｇ１  ）
（Ｌ２  ，  Ｌ３  ）  ←  （Ｍ０  ，  Ｇ０  ）
とする。
【００６９】
Ｓｔｅｐ２：撹乱器１２１Ｂは撹乱パラメータ（Ｙ−ｒ０  ，  ｇ−ｒ０）を用いて、入力の（Ｌ０  ，  Ｌ１  ）を撹乱して（Ｍ’０  ，  Ｇ’０  ）を出力する。
Ｓｔｅｐ３：撹乱器１２１Ｃは撹乱パラメータ（Ｙ−ｒ１  ，  ｇ−ｒ１  ）を用いて、入力の（Ｌ２  ，  Ｌ３  ）を撹乱して（Ｍ’１  ，  Ｇ’１  ）を出力する。
つまり、Ｇｉ  とＧ’ｊ  の対応Ｂ＝ｉ（＋）ｊ，  ただしｉ，  ｊ∈｛０，  １｝、を隠蔽するために出力を撹乱処理している。従ってｒ０  ，ｒ１  の値だけでなくｇ−ｒ０，Ｙ−ｒ０  ，ｇ−ｒ１  ，Ｙ−ｒ１  の値も秘密にする必要がある。なお図２２では置換した後に撹乱を行ったが撹乱した後に置換を行ってもよい。
置換撹乱証明生成器１２２
図２１における置換撹乱証明生成器１２２  は置換撹乱器１２１  が正しく動作している事を秘密情報（Ｂ∈｛０，  １｝及び撹乱用パラメータの値）を明かさずに証明する。この証明をするためにはｂ＝ｉ（＋）ｊであるとして、
ｂ＝０なる全てのｉ，  ｊ∈｛０，  １｝に関して
ｌｏｇＹ  （Ｍｉ  ／Ｍ’ｊ）＝  ｌｏｇｇ（Ｇｉ  ／Ｇ’ｊ  ）
またはｂ＝１なる全てのｉ，  ｊ∈｛０，  １｝に関して
ｌｏｇＹ  （Ｍｉ  ／Ｍ’ｊ  ）＝  ｌｏｇｇ  （Ｇｉ  ／Ｇ’ｊ  ）        ・・・（命題１）
を示さなくてはならない。そのためにこの置換撹乱証明生成器３Ａから以下に述べる証明情報Ｔｉｊ，Ｗｉｊ，ｚｉｊ，ｅｂ  を演算して出力する。
【００７０】
入力のＢは置換撹乱器１２１  中の置換器１２１Ａに入力された置換パラメータである。入力のｒｊ  ，  （ｊ∈｛０，  １｝）は置換撹乱器１２１  中の撹乱器１２１Ｂ，１２１Ｃに入力された撹乱用の乱数である。入力のｅ，  Ｒｉｊ（ｉ，  ｊ∈｛０，  １｝）は証明用の乱数である。入力のＹＲｉｊ，ｇＲｉｊ  （ｉ，  ｊ∈｛０，  １｝）は入力のＭｉ  ，Ｇｉ  ，Ｍ’ｊ  ，Ｇ’ｊ  （ｉ，  ｊ∈｛０，１｝）が入力されるより前に計算された証明用のパラメータである。これら情報｛Ｂ，  ｒｊ，  ｅ，  Ｒｉｊ，  ＹＲｉｊ，  ｇＲｉｊ｝を乱数情報ＲＤＭと呼ぶことにする。
【００７１】
出力のｅｂ  ，Ｔｉｊ，Ｗｉｊ，ｚｉｊ，（（ｂ，  ｉ，  ｊ∈｛０，  １｝）はｂ＝ｉ（＋）ｊとして（Ｍｉ  ，Ｇｉ  ）と（Ｍ’ｊ  ，Ｇ’ｊ  ）の対応を証明するか、または対応を装って証明する為の情報である。
この置換撹乱証明器１２２  では、図のように演算が実行される。つまりｉ，  ｊ∈｛
０，１｝に関して
ｉ（＋）ｊ＝Ｂならば
Ｔｉｊ  ←  ＹＲｉｊ  ，  Ｗｉｊ  ←  ｇＲｉｊ  
ｉ（＋）ｊ＝Ｂ’（Ｂ’はＢの反転を表す）ならば
Ｔｉｊ  ←  （Ｍｉ  ／Ｍ’ｊ  ）ｅＹＲｉｊ  ，Ｗｉｊ  ←  （Ｇｉ  ／Ｇ’ｊ  ）ｅｇＲｉｊ  
Ｂ＝０ならば
ｅ０  ←  −ｅ＋ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
ｅ１  ←  ｅ
Ｂ＝１ならば
ｅ１  ←  −ｅ＋ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
ｅ０  ←  ｅ
任意のｉ，  ｊ∈｛０，  １｝に関して、
ｉ（＋）ｊ＝Ｂならば  ｚｉｊ  ←  Ｒｉｊ−ｅＢｒｊ  
ｉ（＋）ｊ＝Ｂ’ならば  ｚｉｊ  ←  Ｒｉｊ
この演算により証明者（置換撹乱証明生成器１２１  ）は証明情報ＶＲＦ＝｛ｅｂ  ，  Ｔ  ｉｊ，Ｗｉｊ，ｚｉｊ｝を出力する。
【００７２】
なおこの演算において、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行
しても良い。
ＰＲ証明検証器Ｐ７０Ａ
図１９の各置換サーバに設けられた検証器Ｐ７０  内のＰＲ証明検証器Ｐ７０Ａ  は  図２１に示した置換撹乱器１２１  が正しく動作している事を検証するため、ＰＲ  証明生成器１２２  の出力、つまり証明情報ＶＲＦ＝｛ｅｂ  ，Ｔｉｊ，Ｗｉｊ，ｚｉｊ｝を検  証する。
【００７３】
入力のｅｂ  ，Ｔｉｊ，Ｗｉｊ，Ｚｉｊ，（ｂ，  ｉ，  ｊ∈｛０，  １｝）は置換撹乱証明生成  器１２２  の出力であり、ｂ＝ｉ（＋）ｊとして（Ｍｉ，Ｇｉ  ）と（Ｍ’ｊ，Ｇ’ｊ  ）の対応  を証明するか、または対応を装って証明する為の情報である。
この検証器Ｐ７０ＡにはＴｉｊ，Ｗｉｊ，ｚｉｊ，ｅｂ  の他にＭ０  ，Ｇ０  ，Ｍ１  ，Ｇ１    ，Ｍ’０  ，Ｇ’０  ，Ｍ’１  ，Ｇ’１  が入力されて、次式
ｅ０＋ｅ１  ＝  ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
が成立するかを確かめ、これが成立しなければ偽を出力して終了する。関数ｈ
は一方向性関数を表わす。
【００７４】
その後、全てのｉ，  ｊ∈｛０，  １｝に関してｂ＝ｉ（＋）ｊであるとして、
Ｔｉｊ＝  （Ｍｉ  ／Ｍ’ｊ  ）ｅｂＹｚｉｊ    かつ
Ｗｉｊ＝  （Ｇｉ  ／Ｇ’ｊ  ）ｅｂｇｚｉｊ  
が成立するかを確かめ、これが成立しなければ偽を出力して終了する。前記両
確認が共に成立すれば真を出力する。
不正な証明者が何らかの手段で事前に用意したｅｂ  ，ｚｉｊを使って、
Ｔｉｊ  ←  （Ｍｉ  ／Ｍ’ｊ  ）ｅｂＹｚｉｊ  ，
Ｗｉｊ  ←  （Ｇｉ  ／Ｇ’ｊ  ）ｅｂｇｚｉｊ
を計算し出力しようとしてもｈ（ｘ０，  ｘ１，  …）の非予測性により、ｅ０，  ｅ  １  のどちらか一方は事前に計算することが困難なので命題１の証明となる。
【００７５】
出力は置換撹乱器が正しく動作したかどうかの推定であり、真理値である。
この置換撹乱証明検証器Ｐ７０Ａでは、上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数
の演算は、装置を一元化して、順次演算を実行しても良い。
【００７６】
証明付き置換撹乱器１２０
証明付置換撹乱器１２０  は２入力のＥｌ  Ｇａｍａｌ暗号文（Ｍ０，  Ｇ０），（Ｍ１，  Ｇ１  ）を置換撹乱処理した（Ｍ’０，  Ｇ’０），（Ｍ’１，  Ｇ’１）及び、正しい処理が行  われた事の証明を秘密情報を明かさずに出力する（零知識証明）。この証明付  き置換撹乱器１２０  は置換撹乱器１２１  と置換撹乱証明生成器１２２  とから構成され  る。
この証明付き置換撹乱器１２０  では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数
の演算は、装置を一元化して、順次演算を実行しても良い。
【００７７】
Ｓｔｅｐ１：置換撹乱器１２１  は入力の（Ｍ０，  Ｇ０  ），（Ｍ１，  Ｇ１）を入力のＢと  撹乱パラメータｇ−ｒ０，  Ｙ−ｒ０，  ｇ−ｒ１，  Ｙ−ｒ１で置換撹乱処理し、（Ｍ’０，    Ｇ’０），（Ｍ’１，  Ｇ’１）を出力する。
Ｓｔｅｐ２：ＰＲ証明生成器１２２  は入力（Ｍ０，  Ｇ０），  （Ｍ１，  Ｇ１）及び出力（Ｍ  ’０，  Ｇ’０），  （Ｍ’１，  Ｇ’１）及び乱数情報ＲＤＭ＝｛Ｂ，  ｒｊ，  ｅ，  Ｒｉｊ，  ＹＲｉｊ，  ｇ  Ｒｉｊ｝を使って証明情報ＶＲＦ＝｛ｅｂ，  Ｔｉｊ，  Ｗｉｊ，  ｚｉｊ｝を出力する。
【００７８】
証明付部分復号器１４１
図２４，２５，２６を参照して図２１の証明付部分復号器１４１，  １４２を説明する。証明付部分復号器１４１  は図２４に示すように部分復号器１４１Ａと部分復号証明生成器１４１Ｂとから構成されている。部分復号器１４１Ａと部分復号証明生成器１４１Ｂは図２５及び２６に更に詳細に示されている。証明付部分復号器１４２  も１４１  と同様の構成とされているので、証明付部分復号器１４２  の説明は省略する。
【００７９】
図２５はＥｌ  Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号する部分復号器１４１Ａの構成の一例を表している。入力のＥｌ  Ｇａｍａｌ暗号文を（Ｍ，Ｇ）とすると、
平文ｍ及び公開鍵（Ｙ，ｇ）及び乱数に関して
Ｍ＝ｍＹｗ  ，Ｇ＝ｇｗ  
が成り立っている。
いまＹ＝ｙ×ｙ’及びｙ＝ｇｘ  なる秘密鍵の部分情報ｘの値を部分復号者が知って  いるとする。部分復号者は入力の（Ｍ，Ｇ）に対してＭ’  ←  Ｍ×Ｇ−ｘを計算して（Ｍ  ’，
Ｇ）を出力する。出力は
Ｍ’＝  ｍｙ’ｗ  ，Ｇ＝ｇｗ  
を満たすので、平文ｍ及び公開鍵（ｙ’，  ｇ）及び乱数ｗに関するＥｌ  Ｇａｍａｌ暗号文
となる。
【００８０】
部分復号器１４１Ａは冪乗器１４１Ａ１  と乗算器１４１Ａ２  からなる。この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算
を実行しても良い。
Ｓｔｅｐ１：冪乗器１４１Ａ１  は入力の−ｘ及びＧを用いてＬ０  ←  Ｇ−ｘ  を計算してＬ  ０を出力する。
【００８１】
Ｓｔｅｐ２：乗算器１４１Ａ２  は入力のＭ及びＬ０を用いてＭ’  ←  Ｍ×Ｌ０を計算し  てＭ’を出力する。
Ｓｔｅｐ３：部分復号器１４１Ａは入力のＧをそのまま出力する。
部分復号証明生成器１４１Ｂ
図２６は図２５に示した部分復号器１４１Ａが正しく動作している事を秘密情報を明かさずに証明する部分復号証明生成器１４１Ｂの構成の一例を表している。こ
の証明をするためにはｙ＝ｇｘ  なる秘密鍵ｘの値を明かさずに、
ｘの値を知っており、かつＭ／Ｍ’＝Ｇｘ  が成立する（命題２）
を零知識証明で示す。証明は二つの離散対数  ｌｏｇｇ  ｙ及び  ｌｏｇＧ  （Ｍ／Ｍ’）が等し
い事を、Ｃｈａｕｍ−Ｐｅｄｅｒｓｅｎのプロトコルで示す。
【００８２】
入力のＲは証明者以外には秘密の乱数であり、ｇＲはＧが入力される前に計  算されているものとする。この部分復号証明生成器１４１Ｂは冪乗器１４１Ｂ１  と、ハ  ッシュ器１４１Ｂ２  と、レジスタ１４１Ｂ３  と、乗算器１４１Ｂ４  と、減算器１４１Ｂ５  とから  なる。
ハッシュ演算器１４１Ｂ２  は一方向性ハッシュ関数ｈを計算する為の装置で、ハッシュ関数の仕様は公開されているものとする。この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行して
も良い。
【００８３】
Ｓｔｅｐ１：冪乗器１４１Ｂ１  は入力のＲ及びＧを用いてＴ←ＧＲ  を計算してＴを出  力する。
Ｓｔｅｐ２：ハッシュ器１４１Ｂ２  は入力のＴ及びレジスタ１４１Ｂ３  に保持されている
Ｖ＝ｇＲを用いてｅ←ｈ（Ｔ，  Ｖ）を計算してｅを出力する。
Ｓｔｅｐ３：乗算器１４１Ｂ４  は入力のｅ及びｘを用いてＬ０  ←ｅ×ｘを計算してＬ  ０を出力する。
【００８４】
Ｓｔｅｐ４：減算器１４１Ｂ５  は入力のＲ及びＬ０を用いてｓ←Ｒ−Ｌ０  を計算して  ｓを出力する。
Ｓｔｅｐ５：Ｔ，Ｖ，ｅ，ｓを証明情報ＶＲＦ  として図１９の部分復号証明検証器  Ｐ７０Ｂへ出力する。
部分復号証明検証器Ｐ７０Ｂ
図２１中に示した部分復号証明生成器１４１Ｂ（１４２Ｂ）の出力を検証する部分復号証明検証器Ｐ７０Ｂは部分復号器１４１Ａ（１４２Ａ）が正しく動作していることを検証するものであって、「部分復号器１４１Ａがｘの値を知っており、かつＭ／Ｍ’＝Ｇｘ  が成
立する（命題２）」に対して、その真偽を判定して出力する。
【００８５】
図２６に示した部分復号証明生成器１４１Ｂの出力をＣｈａｕｍ−Ｐｅｄｅｒｓｅｎのプロトコルに従って検証する。ｈは仕様の公開された一方向性ハッシュ関数であるとす
る。ｇ，ｙは先に述べたように公開されている。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一
元化して、順次演算を実行しても良い。
【００８６】
Ｓｔｅｐ１：部分復号証明検証器Ｐ７０Ｂ（図１９）は入力のｅ，  Ｔ，  Ｖ  に対して
ｅ＝  ｈ（Ｔ，  Ｖ）
でなければ偽を出力して終了する。
Ｓｔｅｐ２：部分復号証明検証器Ｐ７０Ｂは入力のｍ，  Ｍ’．  Ｇ，  ｅ，  ｓ  に対して
Ｔ＝（Ｍ／Ｍ’）ｅＧｓ  
でなければ偽を出力して終了する。このことはＭ’＝ＭＧ−ｘ，ｓ＝Ｒ−ｅｘの関係を代入してみれば、正しければ等号が成立つことから理解される。
【００８７】
Ｓｔｅｐ３：部分復号証明検証器Ｐ７０Ｂは入力のＶ，  ｅ，  ｓ  に対してＶ＝ｙｅｇｓ  でなければ偽を出力して終了する。このことはＶ＝ｇＲ  ，ｙ＝ｇｘ  ，ｓ＝Ｒ−ｅｘなる関係から理解される。
Ｓｔｅｐ４：部分復号証明検証器Ｐ７０Ｂは全ての検証が成立すれば真を出力して終了する。
以上は図２０で説明した各完全置換網における切換装置としての各証明付ＰＲ部分復号器ＳＷの機能構成とそれに関連した検証器Ｐ７０Ｂの説明であった。次に、図２０に示した完全置換網における証明付固定部分復号器ＳＷＦについて説明する。
証明付き固定部分復号器ＳＷＦ
図２７は２入力のＥｌ  Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号し、復号結果及び各々の復号結果の正当性の証明を出力する証明付き固定部分復号器ＳＷＦの構成の一例を表している。
【００８８】
この証明付き固定部分復号器ＳＷＦは前述のように図２０の置換網において固定した置換と証明付部分復号を行なうために用いられる。この証明付き固定部分復号器ＳＷＦは図２７に示すように証明付き部分復号器１４１Ｆと証明付き部分復号器１４２Ｆとからなる。証明付き部分復号器１４１Ｆ，  １４２Ｆはそれぞれ図２４に示した証明付き部分復号器と同様に構成される。
この証明付き固定部分復号器ＳＷＦでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００８９】
Ｓｔｅｐ１：証明付き部分復号器１４１Ｆは入力の−ｘ及び（Ｍ０，  Ｇ０）及び乱数情報０を用いて（Ｍ０，  Ｇ０）を部分復号した結果の（Ｍ’０，  Ｇ０）及びその正当性の証明である証明情報０を出力する。
Ｓｔｅｐ２：証明付き部分復号器１４２Ｆは入力の−ｘ及び（Ｍ１，  Ｇ１）及び乱数情報１を用いて（Ｍ１，  Ｇ１）を部分復号した結果の（Ｍ’１，  Ｇ１）及びその正当性の証明である証明情報１を出力する。
証明付きＰＲ部分復号器ＳＷ
図２０における証明付きＰＲ部分復号器ＳＷとして、前述の図２１に示したものとは異なる構成例を図２８に示す。
【００９０】
図２８は２入力のＥｌ  Ｇａｍａｌ暗号文（Ｍ０，  Ｇ０），（Ｍ１，  Ｇ１）を置換撹乱部分復号処理した（Ｍ’０，  Ｇ’０），（Ｍ’１，  Ｇ’１）及び、正しい処理が行われた事の証明を秘密情報を明かさずに出力する証明付きＰＲ部分復号器ＳＷの構成の図２１とは異なる例を示す。図２１の例では、置換かく乱に対する証明と部分複合に対する証明を別々に行ったが、図２８では置換撹乱部分復号した結果に対し証明を行っている点が異なる。
【００９１】
この署名付ＰＲ部分復号器ＳＷはＰＲ部分復号器１２４  とＰＲ部分復号証明生成器１２５  からなる。ＰＲ部分復号器１２４  は置換撹乱器１２４Ａと２つの部分復号器１２４Ｂ，  １２４Ｃとから構成されている。
このＰＲ部分復号器ＳＷでは、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００９２】
Ｓｔｅｐ１：ＰＲ部分復号器１２４  は入力の（Ｍ０，  Ｇ０），（Ｍ１，  Ｇ１）を入力のＢ及び撹乱パラメータ、秘密鍵の部分情報で置換撹乱部分復号処理した（Ｍ’０，  Ｇ’０），（Ｍ’１，  Ｇ’１）を出力する。
Ｓｔｅｐ２：ＰＲ部分復号証明生成器１２５  は入力の（Ｍ０，  Ｇ０），（Ｍ１，  Ｇ１）及び（Ｍ’０，Ｇ’０）、（Ｍ’１，  Ｇ’１）及び乱数情報を使って証明情報を出力する。
この証明付きＰＲ部分復号器ＳＷにおいても置換と、撹乱と、部分復号との順は任意に変更してもよい。
【００９３】
図２８における置換撹乱器１２４Ａは図２２に示した置換撹乱器１２１  と同様に構成され、部分復号器１２４Ｂ及び１２４Ｃはそれぞれ図２５に示した部分復号器１４１Ａ（１４１Ｂ）と同様に構成される。
この置換撹乱部分復号器１２４  では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【００９４】
Ｓｔｅｐ１：置換撹乱器１２４Ａは置換撹乱用のパラメータＢ，  ｇ−ｒ０  ，  Ｙ−ｒ０，  ｇ−ｒ１，  Ｙ−ｒ１  を用いて入力の（Ｍ０，  Ｇ０），（Ｍ１，  Ｇ１）を置換撹乱処理した結果を示す２対の情報を出力する。
Ｓｔｅｐ２：部分復号器１２４Ｂは置換撹乱処理した結果の一方の対情報を秘密鍵の部分情報−ｘを用いて部分復号し（Ｍ’０，  Ｇ’０）として出力する。
Ｓｔｅｐ３：部分復号器１２４Ｃは置換撹乱処理した結果の他方の対情報を秘密鍵の部分情報−ｘを用いて部分復号し（Ｍ’１，  Ｇ’１）として出力する。
ＰＲ部分復号証明生成器１２５
図２８におけるＰＲ部分復号証明生成器１２５  はＰＲ部分復号器１２４Ａが正しく動作している事を秘密情報を明かさずに証明する構成の一例を示している。
【００９５】
入力のＢは置換撹乱器１２４Ａ中の置換器（図２２参照）に入力された置換パラメータであり、入力のｒｊ  （ｊ∈｛０，  １｝）は置換撹乱器１２４Ａ中の撹乱器（図２２参照）に入力された撹乱用の乱数であり、入力のｘは復号鍵の部分情報であり、入力のｅ，  Ｋ０，  Ｋ１，  Ｒｉｊ（ｉ，  ｊ∈｛０，  １｝）は証明情報生成用の乱数であり、入力のｇＫ０，  ｇＫ１＋ｅｘ  ｙ’Ｒｉｊ，ｇＲｉｊ  （ｉ，  ｊ∈｛０，  １｝）は入力のＭｉ，  Ｇ  ｉ，  Ｍ’ｊ，  Ｇ’ｊ  （ｉ，  ｊ∈｛０，  １｝）が入力されるより前に計算された証明情報生成用のパラメータである。
【００９６】
出力のＶｂ，  ｅｂ，  ｓｂ，  Ｔｉｊ，  Ｗｉｊ，  ｚｉｊ，  （ｂ，  ｉ，  ｊ∈｛０，  １｝）はｂ＝ｉ（＋）ｊとして（Ｍｉ，  Ｇｉ）と（Ｍ’ｊ，  Ｇ’ｊ）の対応を証明するか、または装う為の情報である。
置換撹乱部分復号器１２４  が正しく動作していることを直接証明するためには、置換用の乱数Ｂ∈｛０，  １｝及び撹乱や復号用の秘密のパラメータの値を明かさずに、ｂ＝ｉ（＋）ｊであるとして、
ｂ＝０なる全ての  ｉ，  ｊ∈｛０，  １｝に関してＭ／Ｍ’ｊ  ＝ｙｒｊＧｉｘ  かつＧｉ  ／Ｇ’ｊ  ＝ｇｒｊ
ｂ＝１なる全ての  ｉ，  ｊ∈｛０，  １｝に関してＭ／Ｍ’ｊ  ＝ｙｒｊＧｉｘ  かつＧｉ  ／Ｇ’ｊ  ＝ｇｒｊ
・・・（命題３）
を示さなくてはならない。このために以下に示すようにして証明情報Ｖｂ  ，ｅｂ  ，ｓｂ  （ｂ∈｛０，  １｝），Ｔｉｊ，Ｗｉｊ，ｚｉｊ（ｉ，  ｊ∈｛０，  １｝）を生成する。
【００９７】
全ての  ｉ，  ｊ∈｛０，  １｝に関して、
ｉ（＋）ｊ＝Ｂならば
Ｔｉｊ  ←  ｙ’Ｒｉｊ  ＧｉＫ０，Ｗｉｊ  ←  ｇＲｉｊ  
ｉ（＋）ｊ＝Ｂ’ならば（Ｂ’はＢの反転）
Ｔｉｊ  ←  （Ｍｉ  ／Ｍ’ｊ）ｅ  ｙ’Ｒｉｊ  ＧｊＫ１  ，Ｗｉｊ  ←  （Ｇｉ  ／Ｇ’ｊ）ｅ  ｇＲｉｊ  
を演算する。
【００９８】
更に
ＶＢ  ←  ｇＫ０，ＶＢ’←  ｇＫ１＋ｅｘ
としＢ＝０ならば
ｅ０  ←  −ｅ＋ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
を演算し、またｅ１  ←ｅとし、
Ｂ＝１ならば
ｅ１  ←  −ｅ＋ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
を演算し、かつｅ０  ←ｅとし
更にｉ（＋）ｊ＝Ｂなら
ｚｉｊ  ←  Ｒｉｊ−  ｅｂ  ｒｊ  
を演算し、ｉ（＋）ｊ＝Ｂ’ならｚｉｊ  ←  Ｒｉｊとし
Ｂ＝０ならば
ｓ０  ←  Ｋ０  −ｅ０ｘ
を演算し、ｓ１  ←  Ｋ１  とし、
Ｂ＝１ならば
ｓ１  ←  Ｋ０  −ｅ１ｘ
を演算し、ｓ０  ←  Ｋ１  とする。
【００９９】
この置換撹乱部分復号証明生成器１２５  は上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また、同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
ＰＲ部分復号証明検証器Ｐ７０Ｃ
図１９におけるＰＲ部分復号証明検証器Ｐ７０Ｃは図２８に示したＰＲ部分復号器１２４  が正しく動作している事を検証する。この検証器Ｐ７０Ｃは図２８中のＰＲ部分復号証明生成器１２５  の出力を検証する。
【０１００】
ＰＲ部分復号証明検証器Ｐ７０Ｃの入力はｅｂ，  Ｔｉｊ，Ｗｉｊ，Ｚｉｊ，（ｂ，  ｉ，  ｊ∈｛０，  １｝）であり、これは図２８のＰＲ部分復号証明生成器１２５  の出力であり、ｂ＝ｉ（＋）ｊとして（Ｍｉ，  Ｇｉ）と（Ｍ’ｊ，  Ｇ’ｊ）の対応を証明するか、または装う為の情報である。この検証器Ｐ７０Ｃは先ず
ｅ０＋ｅ１  ＝ｈ（Ｔ００，Ｔ０１，Ｔ１０，Ｔ１１，Ｗ００，Ｗ０１，Ｗ１０，Ｗ１１）
が成立するかを演算して確め成立しなければ偽を出力して終了し、成立すれば、全てのｂ∈｛０，  １｝に関してＶｂ＝ｇｓｂｙｅｂ  が成立するかを演算して確め、成立しなければ偽を出力して終了し、成立すれば、全てのｉ，  ｊ∈｛０，  １｝に関してｂ＝ｉ（＋）ｊであるとして、
Ｔｉｊ＝（Ｍｉ  ／Ｍ’ｊ）ｅｂｙ’ｚｉｊ  Ｇｉｓｂ  ，Ｗｉｊ＝（Ｇｉ  ／Ｇ’ｊ）ｅｂｇｚｉｊ
が成立するかを演算して確め、成立しなければ偽を出して終了し、成立すれば真を出力する。このようにして命題３の真偽が判定される。
【０１０１】
この検証器Ｐ７０Ｃでは、上述のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
完全置換網１０
図２９Ａ及び図２９Ｂはそれぞれ４入力及び８入力の完全置換網１０Ａ及び１０Ｂの構成の一例を表している。
【０１０２】
完全置換網とは証明付きＰＲ部分復号器ＳＷ及び証明付き固定部分復号器ＳＷＦの複数個が行列に配され、縦続的に接続され、各証明付きＰＲ部分復号器ＳＷの秘密の置換パラメータＢｉ  の値の組合せによって入力に対するあらゆる置換を実現できる網のことである。入力はＮ個のＥｌ  Ｇａｍａｌ暗号文であり出力はＮ個のＥｌＧａｍａｌ暗号文またはＮ個の平文である。また置換の正当性を証明する情報として各証明付きＰＲ部分復号器及び各証明付き固定部分復号器の証明情報及び秘密鍵や置換撹乱パラメータや乱数情報以外の入出力情報が出力公開される。
【０１０３】
図２９Ａでは２個のＥｌ  Ｇａｍａｌ暗号文が入力され、２個のＥｌ  Ｇａｍａｌ暗号文を出力する処理器として前記証明付きＰＲ部分復号器ＳＷと証明付き固定部分復号器ＳＷＦが２行３列に配され、各行の部分復号器の出力が同一行の次の列の部分復号器へ供給されるものと、行が入れ替えられて次の列の部分復号器へ入力されるものとがあり、部分復号器中の実線ブロックで示しているものは証明付きＰＲ部分復号器ＳＷであって、２つのＥｌ  Ｇａｍａｌ暗号文を置換撹乱処理し、秘密鍵の部分情報を用いて部分復号し、その置換撹乱結果と、その正当性を証明するための証明情報を出力し、部分復号器中の破線ブロックで示されているものは証明付き固定部分復号器ＳＷＦであって、このＥｌ  Ｇａｍａｌ暗号文を秘密鍵の部分情報を用いて部分復号し、その復号結果と、その正当性を証明するための証明情報を出力する。この場合４入力の配列に対し置換可能な配列は４！＝４×３×２＝２４通りであるが、Ｂｉ  の数は５あれば２５  ＝３２通りの配列が可能となり、入力配列に対し、置換可能な全ての配列の何れにも設定可能である。つまり４入力の配列の場合は、証明付きＰＲ部分復号器、換言すれば置換パラメータＢｉ  を設定できる処理器は５個あれば完全置換網を構成できる。一方証明付きＰＲ部分復号器と比較して証明付き固定部分復号器は構成が可成り簡単であり、つまり計算量が少なくて済むので、１行３列目の処理器は証明付き固定部分復号器としている。これをも証明付きＰＲ部分復号器としてもよい。
【０１０４】
図２９Ｂは証明付きＰＲ部分復号器ＳＷ又は証明付き固定部分復号器ＳＷＦが４行５列に配され、内側の３列間で同一行で出力が入力されるものと行が入れ替えられて出力が入力されるものとがある。この構成は図中に破線で示すように図２９Ａの４入力４出力の完全置換網を二つ組合せたものである。
秘密の置換パラメータの第ｉ列のＢｉ  の値が分からなければどのような置換が行われたのか推定する事は出来ない。つまりＭ’０  ，…，Ｍ’３  はＢｉ  の値の組み合わせを知らなければ誰が入力した文かは判らない。図２９Ａ、図２９Ｂの何れにおいても正しく復号するために、同じ列（第ｉ列）の各部分復号器は同じ復号鍵ｘｉ  を持つ。
完全置換網１０Ｃ
図３０は２Ｎ入力の完全置換網１０Ｃの構成の一例を表している。原理は  Ａ．Ｗａｋｓｍａｎ．  Ａ  ｐｅｒｍｕｔａｔｉｏｎ  ｎｅｔｗｏｒｋ．  Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  ＡＣＭ，１５（１）：１５９−１６３，  １９６８．による。
【０１０５】
置換網１０ＣはＮ入力の完全置換網１０Ｃ１，  １０Ｃ２及び２入力の完全置換網（証明付きＰＲ部分復号器）ＳＷのみから構成されているので２入力の完全置換網を用いて４入力、８入力、…、２ｎ  入力の完全置換網を構成する事が出来る。図ではＮ入力完全置換網を２つ設け、その入力段にＮ個の２入力２出力の証明付き置換撹乱部分復号器を設け、出力段に（Ｎ−１）  個の２入力２出力の証明付きＰＲ部分復号器ＳＷと、１個の証明付き固定部分復号器ＳＷＦを設けている。図２９Ｂの構成は図３０の構成でＮ入力完全置換網として４入力完全置換網が用いられた場合となる。
【０１０６】
従って、証明付き置換撹乱部分復号器及び証明付き固定部分復号器のみを用いて部分復号処理を行う機能をもった２ｎ  入力の完全置換網を構成する事が出来る。
Ｎ（＝２ｎ  ）入力の完全置換網に必要な部品は、証明付き置換撹乱部分復号器Ｎｌｏｇ２  Ｎ−Ｎ＋１個及び証明付き固定部分復号器  （Ｎ−１）個であり、全体の段数（列の数）は２Ｎ  ｌｏｇ２  Ｎ−１段である。
一括不正回復付き検証可能匿名通信路１００
前述の図２０は８入力２秘密漏洩耐性２故障耐性一括不正回復付き検証可能匿名通信路の構成の一例を表している。一括不正回復付き検証可能匿名通信路１００  は置換サーバＰＳ１〜ＰＳ５と、置換サーバ１８Ｃと、置換サーバ１８Ｄと、置換サーバ１８Ｅと、置換サーバ１８Ｆとが縦続的に接続されて構成されている。ｔ秘密漏洩耐性とは全部でＶ（＞２ｔ）個の置換サーバのうち最大ｔ個の装置の置換秘密情報Ｂｉ  が攻撃などにより漏洩しても入出力の対応が完全に隠蔽されることを意味する。
【０１０７】
一括不正回復付き検証可能匿名通信路１００  は３つの完全置換網１０Ａ，１０Ｂ，１０Ｃを含んでおり、完全置換網を跨る置換サーバを持っていないので、どの２つの置換サーバの置換秘密情報Ｂｉ  が漏洩してもその２つの置換サーバを含まない完全置換網が必ず一つは存在し、その完全置換網の秘密情報が全て隠蔽されているのでこの完全置換網により入出力の対応が隠蔽され、この匿名通信路１００  の入出力の対応も隠蔽される。従って図２０に示した匿名通信路では５つの置換サーバＰＳ１〜ＰＳ５よりなるから一括不正回復付き検証可能匿名通信路１００  は２秘密漏洩耐性を持っている。
【０１０８】
一般に一括不正回復付き検証可能匿名通信路１００  が完全置換網をｔ＋１  個直列に接続した形状の網を持ち、この網をＶ個に分割し、分割された各々の部分を置換サーバとする場合、どの置換サーバも２つの完全置換網に跨ることが無いように網の分割が行われていれば、その一括不正回復付き検証可能匿名通信路はｔ秘密漏洩耐性を持つ。
ｔ故障耐性とは全部でＶ（＞２ｔ）個の置換サーバのうち最大ｔ個の動作が正しくない時でも不正回復により最終的には正しく出力ができる一括不正回復付き検証可能匿名通信路であることを意味する。
【０１０９】
各置換サーバは自分の秘密鍵を他の置換サーバに検証可能な秘密分散法で、ｔ＋１個以上の置換サーバが集まれば秘密鍵を復元出来るように秘密分散する。例えば、０次の係数を隠蔽すべき秘密鍵ｘｉ  とし秘密の乱数により他の係数が決定されるｚに関するｔ次多項式ｆｉ（ｚ）のｚ＝ｊの値ｘｉｊ＝ｆｉ（ｊ）をｊ番目の置換サーバに対して分配するとすれば、一つのｉに対してｔ＋１  個以上のｘｉｊ及び対応するｊが集まれば、その中の任意のｔ＋１  個の互いに異なるｊの集合Ｊに関するＬａｇｒａｎｇｅ補間公式
【０１１０】
【数８】
0003540718.tif 000009
を用いて、ｘｉ＝ｆｉ（０）として秘密鍵を復元できる。このような鍵秘密分散復元の手法は例えば共立出版株式会社１９９５年１２月２０日発行、岡本龍明、太田和夫編「暗号・ゼロ知識証明・数論」６２〜６３頁に示されている。
【０１１１】
図１９に示したように、各置換サーバＰＳは他の装置の入出力の正当性を検証するための検証器２１を具備している。各置換サーバＰＳで暗号文の出力が行われる度にその正当性を検査し結果を掲示板に公開する。
各置換サーバは検査の結果、正しいと認められる最後の出力を自分の入力とし、その入力に対して未だ部分復号処理に用いられていない全ての公開鍵の積を求め、これを撹乱処理に必要なパラメータとして置換撹乱部分復号処理を行う。
【０１１２】
最終出力が終った後、全ての置換サーバが正しく動作した、つまり全装置が正しかったと全員が納得し、全ての置換サーバが出力した場合は、最終出力が求める平文の列（リスト）になる。
上記以外の場合、最終出力が終った後、最終的に互いに信頼できる入出力を行った置換サーバが３個（ｔ＋１個）以上集まった時は、正しく動作していないと判断された全ての置換サーバの秘密鍵を、鍵秘密分散復元の手法により復元し、その総和をｘ’として公開する。
【０１１３】
最終的に互いに信頼できる置換サーバが各々最終的に信頼できる出力を、秘密鍵ｘ＾を用いて復号し平文の列を求め公開する。この秘密鍵ｘ’により復号可能なことは前記「一括化可能」条件にもとずく、最終的に互いに信頼できる入出力を行った置換サーバが３個（ｔ＋１個）以上集まらない時には不正回復は失敗する。
置換サーバが信頼できるものであるかはその入力と出力と証明情報を用いて、前述した証明付きＰＲ部分復号器、証明付き置換撹乱器、証明付き固定部分復号器に対する検証により、その置換サーバが構成する処理器の全てについて、検証すればよい。また置換サーバに対する処理は、その縦続接続された順に行うが、その入力としては直前の信頼できる置換サーバの出力を用いる。以下にどの置換サーバの出力を入力とすればよいかの検索手法の例を示す。なおこの検索は各置換サーバ中の判定部Ｐ６０  で行う。
【０１１４】
また匿名通信路１００  への入力リストをＬ０とし、ｉ番目の置換サーバＰＳｉ  の出力リストをＬｉとする時、ｊ番目の置換サーバＰＳｊ  の入力リストＬｊを求めるには例えば図３１に示すように行えばよい。ｊ番目の置換サーバＰＳｊ  の、正しい処理を行なった直前の置換サーバの位置をｔで表すと、まずｔ＝０、ｉ＝１と初期化し（Ｓ１）、ｉ＜ｊかを調べ（Ｓ２）、ｉがｊより小さければｉ番目の置換サーバＰＳｉ  の証明情報ＶＲＦｉは入力リストＬｔと出力リストＬｉの１対１の対応を証明しているかを調べ（Ｓ３）、証明している場合はｔ＝ｉとし（Ｓ４）、更にｉを＋１してステップＳ２に戻り（Ｓ５）、ステップＳ３で１対１の対応を証明していない場合はステップＳ５に移り、ｉがｊと等しいかそれより大きくなれば処理を終了し、その時のｔの値から置換サーバＰＳｔ  の出力リストＬｔが求める入力リストになる。
【０１１５】
図３１に示した入力リストの探索は次のようにして処理を削減することができる。図３１において、各置換サーバが決定した入力リストがどの置換サーバからのものであるかその番号ｔを掲示板に登録し、ステップＳ２とＳ３との間において図３２に示すように置換サーバＰＳｉ  は信頼できる置換サーバの出力リストＬｔを入力としているかを調べる（Ｓ６）。もし検証対象の置換サーバＰＳｉ  が信頼できる置換サーバの出力リストＬｔを入力としていなかった場合は、ステップＳ３の検証を行なわないでも、その置換サーバＰＳｉ  が不正な処理を行なったと判断できる。そこで、図３２に示すように、置換サーバＰＳｉ  がリストＬｔを入力としていない場合は、その置換サーバＰＳｉ  の入力リストＬｔと出力リストＬｉの対応を検証することなく、ステップＳ５に移り、リストＬｔを入力としている場合は、その置換サーバＰＳｉ  についてステップＳ３を実行する。これにより、図３１に示した場合より処理量を減少することができる。置換サーバＰＳ１〜ＰＳｊ−１についての検証が終了すれば（ｉ≧ｊとなれば）、ステップＳ６でｔの値を掲示板に登録し、処理を終了する。
【０１１６】
更に他の例を示す。この例では、各置換サーバＰＳｉ  ，  ｉ＝１，  …，Ｖはそれより上流の前置換サーバについて、それぞれ信頼できるか否かの判定結果を掲示板に例えば図３３Ａに示すように登録するものとする。又、各置換サーバＰＳｊ  は、自分より上流の各置換サーバＰＳｋ  （１＜ｋ＜ｊ）に対する信頼性の判定結果を信頼度情報Ｒｋ＝真又は偽、として記録するレジスタを有しているものとする。図３３Ｂは置換サーバＰＳｊ  のレジスタに記録された信頼度情報の例を示している。図３３Ａでは、すでにｊ−１番目の置換サーバまでそれぞれそれらより上流の全ての置換サーバに対する判定結果を○印は信頼性あり、×印は信頼性なしで示している。
【０１１７】
各置換サーバは自分より上流の最も近い信頼できる置換サーバの出力を入力とすることが要求されているので、ｊ番目の置換サーバＰＳｊ  は１番目の置換サーバＰＳ１  から順に検査し、例えば２番目の置換サーバは信頼性がないと判定したにもかかわらず、図３３Ａに示すように掲示板を参照するとｉ番目の置換サーバは２番目の置換サーバを信頼性ありと判定している。従って、ｊ番目の置換サーバはｉ番目の置換サーバを信頼性がないと判定することができる。このような場合、ｊ番目の置換サーバはｉ番目の置換サーバについての入出力の対応関係の検証を省略することができる。同様に、ｊ番目の置換サーバが例えば３番目の置換サーバを信頼性ありと判定したにもかかわらず、もしｉ番目の置換サーバが３番目の置換サーバを信頼性なしと判定していたら（図３３Ａでは信頼性ありとなっている）、その場合も、ｊ番目の置換サーバはｉ番目の置換サーバを信頼性がないと判定でき、この場合も、ｊ番目の置換サーバはｉ番目の置換サーバに対する入出力の対応の検証を省略することができる。この方法を使ったｊ番目の置換サーバによる入力リストの探索処理を図３４を参照して説明する。
【０１１８】
図３４に示す置換サーバＰＳｊ  の入力リストの検索処理において、まずｔ＝０，  ｉ＝０とし、置換サーバＰＳｊ  のレジスタの  ｋ＝  １，  …，  ｊ−１  に対する値Ｒｋ  を全て真とする初期化を行い（Ｓ１）、ｉがｊより小さければ（Ｓ２）、図３３Ｂに示したレジスタを参照し、ｋ＝ｉ  番目の置換サーバの信頼度情報Ｒｉ  が真であるかを調べ（Ｓ３）、Ｒｉ  が真であれば（Ｒｉの初期値は真に設定されている）、置換サーバＰＳｉ  の証明情報ＶＲＦｉがリストＬｔとリストＬｉの１対１対応を証明しているかを調べ（Ｓ４）、正しく証明するものであればｔをｉに更新する（Ｓ５）。この場合、ｋ＝  ｉ＋１，  …，  ｊ−１  の置換サーバＰＳｋ  はそれぞれ置換サーバＰＳｉ  の出力リストＬｉを正しい、即ち置換サーバＰＳｉ  は信頼性がある、と判断すべきであるから、図３３Ａの掲示板を参照し、もしこの置換サーバＰＳｉ  を信頼性がないと判断した置換サーバＰＳｋ  があれば、図３３Ｂに示すように、その置換サーバに対する信頼度情報Ｒｋ  を偽に変更する（Ｓ７）、その後、ｉを＋１してステップＳ２に戻る（Ｓ７）。
【０１１９】
ステップＳ４でリストＬｔとリストＬｉが１対１で対応することを証明できない場合は、ステップＳ８に移り、掲示板を参照し、もしｋ＝１，  ，  ｊ−１の置換サーバＰＳｋ  でサーバＰＳｉ  を信頼できると判定している置換サーバがあれば、その置換サーバについての信頼度情報Ｒｋを偽に変更し、ステップＳ７でｉを歩進してステップＳ２に戻る。従って、以降のループ処理で、ステップＳ２でｉが、先にステップＳ４又はＳ８でレジスタの信頼度情報Ｒｋが偽とされた置換サーバの番号ｉ＝ｋ  となった時には、ステップＳ３でレジスタにあるそのサーバの信頼度情報Ｒｋが偽となっているので、ステップＳ４の検証を行なわず、ステップＳ８に移る。
【０１２０】
ステップＳ２でｉがｊを超えると、その時のリストＬｔを求める入力とし、また全ての置換サーバＰＳｋ  についての信頼度情報Ｒｋ  を公開（掲示板に登録）して終了する。
このように各検査結果である信頼度情報Ｒｋ  を利用することにより、入力すべき出力リストの検索にかかる処理量が少なくて済む。
図２０では各置換サーバＰＳ１〜ＰＳ５の処理器として証明付き置換撹乱部分復号器のみ又はこれと証明付き固定部分復号器とを用いた。しかし、各置換サーバＰＳ１〜ＰＳ５を証明付き置換撹乱器と証明付き固定部分復号器とを用いて構成することもできる。例えば図３５に示すように、図２０中の証明付き置換撹乱部分復号器を証明付き置換撹乱器に置きかえ、図２０中の証明付き固定部分復号器の部分はその入力をそのまま出力させ、各置換サーバの最後の段（列）の後段に各行ごとに証明付き固定部分復号器をそれぞれ設けてもよい。
【０１２１】
また図２０中の例えば置換サーバＰＳ１  の初段（第１列）の各行の処理器を全て証明付き置換撹乱器に変更してもよい。要は置換サーバは、全体として証明付き置換撹乱処理と、少なくとも１段（１列）の処理器による証明付き部分復号処理とを行うものであればよい。なおｔ故障耐性が問題とならず、ｔ秘密漏洩耐性のみを必要とする場合は置換サーバを重複することなく構成された完全置換網がｔ＋１個あればよく、Ｖ＞２ｔなる条件は必要としない。
【０１２２】
前述したこの発明の各実施例において、この発明による匿名通信路を形成している置換網は２入力２出力の単位切換装置ＳＷ（ＳＷＦ）を規則に従って接続して構成してもよいが、例えばＮ＝２ｋ入力の場合、単位切換装置ＳＷ（ＳＷＦ）が入力側から２ｋ−１個ずつ（２ｋ−１）段に配列された置換網において、各段で１つのデータ処理装置が前段からの処理結果を取り込み、単位切換装置ＳＷの２ｋ−１個分の処理を実行し、処理結果を順次出力するようにしてもよいし、更に、これら（２ｋ−１）段の（２ｋ−１）個のデータ処理装置が行なうべき処理を１つの処理装置が順次実行してもよい。
【０１２３】
例えば、（２ｋ−１）段のそれぞれにデータ処理装置が１つずつ設けられている場合、Ｊ段目の処理装置には前段から２ｋ個の処理結果であるＥｌ  Ｇａｍａｌ  暗号（Ｍ，  Ｇ）を順次取り込み、前述したような置換、撹乱及び部分復号を行なって得た暗号（Ｍ’，Ｇ’）を予め決めた規則に従って順に出力する。この処理手順を図３６から３９を参照して説明する。
図３６はＪ段目の処理装置が１〜ｋ−１段のグループ、ｋ〜２ｋ−２段のグループ、及び最後の２ｋ−１段のどの段に属するかを判定し、処理１、処理２及び処理３のどれを実行すべきかを決定する。各段の処理装置は、Ｎ＝２ｋ個の出力端子位置に対応してＮ個の処理結果を保持するＮ個の出力レジスタを有するものとする。
ステップＳ１：Ｊ＝２ｋ−１か否か、即ち最終段であるか否か判定し、最終段であれば処理３（図３９）の実行に移る。そうでなければステップＳ２に移る。
ステップＳ２：Ｊ−ｋ≧０  か否か、即ちＪはｋ〜２ｋ−２  の値か判定し、そうであれば処理２（図３８）の実行に移る。そうでなければステップＳ３に移る。
ステップＳ３：Ｊは１〜ｋ−１の値であり、処理１（図３７）の実行に移る。
【０１２４】
図３７，３８，３９はそれぞれ処理１、処理２、処理３を実行するフローを表す。ここで、（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）はＪ−１段目のランダム置換の対象となる２つの出力位置［２ｉ］，  ［２ｉ＋１］の暗号文（Ｍ２ｉ，  Ｇ２ｉ），  （Ｍ２ｉ＋１，  Ｇ２ｉ＋１）を表す。ｌｒｏｔ（ｕ，  ｖ）は２進表現のデータｕ中のＬＳＢ  側からｖビットのデータに対し１ビット左回転を与えることによりデータｕを変換することを意味する。例えば、２進表現でｕ＝１０１１０であり、ｖ＝３  とすると、ｌｒｏｔ（ｕ，  ｖ）は、１０１１０の右側３ビット１１０を、左へ１ビット回転させて１０１とすることにより、ｕを１０１０１に変換する。同様に、ｒｏｔ（ｕ，  ｖ）は２進表現されたデータｕのＬＳＢ  側からｖビットのデータを右へ１ビット回転させることによりデータｕを変換する。
【０１２５】
ｂｉｔ［ｘ，  ｙ］は、２進表現されたｘの下位ｙビットの値を表す。例えばｘ＝１０００１でｙ＝４の場合、ｂｉｔ［ｘ，  ｙ］＝１となる。
図３７に示す処理１はＪ＝１，  …，  ｋ−１  の置換段における処理であり、これらの段では以下のように全ての対の入力暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対しランダム置換、撹乱、部分復号を行う。
ステップＳ１１：ｉ＝０  に初期設定する。
ステップＳ１２：Ｊ−１  段目からの２ｉ番目と（２ｉ＋１）番目のランダム置換対象となる２つの暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ［ｒｏｔ（２ｉ，  ｋ−Ｊ＋１）］番目と、［ｒｏｔ（２ｉ＋１，  ｋ−Ｊ＋１）］番目の出力レジスタに格納する。
ステップＳ１３：ｉを１増加する。
ステップＳ１４：ｉ≦２ｋ−１  であるか判定し、そうであればまだ未処理データがあるのでステップＳ１１に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２６】
図３８に示す処理２はＪ＝ｋ，  …，  ２ｋ−２  の置換段における処理であり、対の入力暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対し以下のように処理を行なう。
ステップＳ２１：ｉ＝０  に初期設定する。
ステップＳ２２：ｂｉｔ［ｉ，  Ｊ−ｋ］＝０  であるか判定し、ＹＥＳ  であれば固定置換装置ＳＷＦでの処理であり、ステップＳ２３に移り、ＮＯであれば置換装置ＳＷでの処理でありステップＳ２４に移る。
ステップＳ２３：前段（Ｊ−１  段目）からの２ｉ番目と（２ｉ＋１）番目の対の暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）をそのままそれぞれ［ｌｒｏｔ（２ｉ，  Ｊ−ｋ＋２）］番目と、［ｌｒｏｔ（２ｉ＋１，  Ｊ−ｋ＋２）］番目の出力レジスタに格納する。
ステップＳ２４：Ｊ−１  段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ［ｌｒｏｔ（２ｉ，  Ｊ−ｋ＋２）］番目と、［ｌｒｏｔ（２ｉ＋１，  Ｊ−ｋ＋２）］番目の出力レジスタに格納する。ステップＳ２５：ｉを１増加する。
ステップＳ２６：ｉ≦２ｋ−１  であるか判定し、そうであればまだ未処理データがあるのでステップＳ２２に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２７】
図３９に示す処理３は最終段Ｊ＝２ｋ−１  における処理であり、前段からの対の入力暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対し以下のように処理を実行する。
ステップＳ３１：ｉ＝０  に初期設定する。
ステップＳ３２：ｂｉｔ［ｉ，  Ｊ−ｋ］＝０  であるか判定し、ＹＥＳ  であれば固定置換装置ＳＷＦでの処理であり、ステップＳ３３に移り、ＮＯであれば置換装置ＳＷでの処理でありステップＳ３４に移る。
ステップＳ３３：Ｊ−１  段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）をそのままそれぞれ２ｉ番目と、（２ｉ＋１）番目の出力レジスタに格納する。ステップＳ３４：Ｊ−１  段目からの２ｉ番目と（２ｉ＋１）番目の対の暗号（ＬＪ−１［２ｉ］，  ＬＪ−１［２ｉ＋１］）に対し証明付置換撹乱部分復号処理を行い、処理結果をそれぞれ２ｉ番目と、（２ｉ＋１）番目の出力レジスタに格納する。
ステップＳ３５：ｉを１増加する。
ステップＳ３６：ｉ≦２ｋ−１  であるか判定し、そうであればまだ未処理データがあるのでステップＳ３２に戻る。そうでなければＪ段でのデータ処理を終了する。
【０１２８】
全（２ｋ−１）段の処理を１つの処理装置で実行する場合は、図３６〜３９の処理手順を、Ｊ＝１，  ２，  ．．．，  ２ｋ−１について順次繰り返せばよい。
以上説明したこの発明による置換撹乱復号処理は、コンピュータプログラムとして記録媒体に記録しておき、そのプログラムを読み出して実行することにより実施してもよい。
上述した符号化装置、復号化装置は共に、その各機能をコンピュータによりプログラムを解読実行させることにより行わせることもできる。
【０１２９】
図４０はこの発明による匿名通信路を構成する置換網における証明付置換撹乱部分復号方法をコンピュータで実施する場合の構成を示す。コンピュータ８０は、バス８８を介して互いに接続されたＣＰＵ８１、ＲＡＭ８２，ＲＯＭ８３，入出力インタフェース８４、ハードディスク８５を含んでいる。ＲＯＭ８３にはコンピュータ８０を動作させる基本プログラムが書き込まれてあり、ハードディスク８５には前述した例えば１つの置換サーバがこの発明による証明付置換撹乱部分復号処理方法を実行するプログラムが予め格納されている。例えば符号化時にはＣＰＵ８１はハードディスク８５から符号化プログラムをＲＡＭ８２にロードし、掲示板４００  からインタフェース８４を介して取り込んだ暗号化投票文をプログラムに従って処理することにより匿名通信路を通して暗号投票を復号化し、インタフェース８４から掲示板４００  に出力する。
【０１３０】
この発明による証明付置換撹乱部分復号化方法を実行するプログラムは内部バス８８に駆動装置８６を介して接続された外部ディスク装置８７に記録されたものを使用してもよい。この発明による方法を実行するプログラムが記録された記録媒体としては、磁気記録媒体や、ＩＣメモリや、コンパクトディスクなどどのような形態の記録媒体であってもよい。
【０１３１】
【発明の効果】
この発明によれば、少数の入力に対する置換が比較的容易なことを利用して、少数の入力の置換を繰り返して全体の置換を構成することにより、全体の入力をＮ個としたとき、全体の置換に対する証明の為の計算量、通信量をＮｌｏｇ  ２Ｎに比例する量にまで低減することが可能となり、効率的な検証可能匿名通信路を構築することができる。
【０１３２】
従来においては１つの置換サーバで不正（故障）が検出されるごとに、その補償処理を行っていた、従ってｔ個の装置で不正があればｔ回の補償処理を必要としたが、この発明によればＶ個の置換サーバのうちｔ個の出力が信頼できなくなった場合でも、その信頼できなくなった（不正、故障）装置を迂回して処理し最後に、鍵秘密分散回復法により回復した鍵を用いて平文を得ることができ、たった１回の不正回復処理を行えば不正回復が完了する。
【０１３３】
またこの発明により従来ｔ回の不正回復を行っていたのに比べてｔ倍高速に不正を回復可能になり検証可能匿名通信路における帯域保証を効率的にすることが可能となった。
更に置換サーバを重複使用することなく、完全置換網をｔ＋１個直列に構成することにより、ｔ秘密漏洩耐性が得られる。
【図面の簡単な説明】
【図１】従来の４入力の置換網を示すブロック図。
【図２】この発明が適用される装置の全体を示すブロック図。
【図３】４入力に対する匿名通信路の構成と検証端末の構成を示すブロック図。
【図４】図３中の切換装置ＳＷの構成を示すブロック図。
【図５】図４中の切換部１２の構成を示すブロック図。
【図６】図４中の置換証明部１４の構成を示すブロック図。
【図７】図３中の復号装置２０の構成を示すブロック図。
【図８】図７中の復号部２１の構成を示すブロック図。
【図９】図７中の復号証明部２２の構成を示すブロック図。
【図１０】図３中の置換検証部３０の構成を示すブロック図。
【図１１】図３中の復号検証部４０の構成を示すブロック図。
【図１２】第２実施例のシステム構成を示すブロック図。
【図１３】図１２中の置換サーバＰＳの構成を示すブロック図。
【図１４】図１２中の復号サーバ２０Ｓの構成を示すブロック図。
【図１５】第２実施例における各サーバ内のデータの流れを示す図。
【図１６】第３実施例のシステム構成を示すブロック図。
【図１７】第３実施例中の復号サーバ２０Ｓにおける復号部の構成を示すブロック図。
【図１８】第３実施例における復号検証部の構成を示すブロック図。
【図１９】この発明の匿名通信路を用いたシステム構成例を示すブロック図。
【図２０】図１９の実施例において掲示板を介して縦続接続された置換サーバにより構成された複数の完全置換網を示すブロック図。
【図２１】証明付き置換撹乱部分復号器の機能構成例を示すブロック図。
【図２２】置換撹乱器の機能構成例を示すブロック図。
【図２３】撹乱器の機能構成例を示すブロック図。
【図２４】証明付き部分復号器の機能構成例を示すブロック図。
【図２５】部分復号器の機能構成例を示すブロック図。
【図２６】部分復号証明生成器の機能構成例を示すブロック図。
【図２７】証明付き固定部分復号器の機能構成例を示すブロック図。
【図２８】証明付き置換撹乱部分復号器の機能構成例を示すブロック図。
【図２９】完全置換網の構成例を示すブロック図。
【図３０】完全置換網を拡大させる手法の例を示すブロック図。
【図３１】置換サーバの入力リストを検索する処理例を示す流れ図。
【図３２】置換サーバの入力リストを検索する他の処理例を示す流れ図。
【図３３】Ａは更に他の検索処理方法において掲示板に公開される置換サーバの信頼性の判定結果を示す表、Ｂはその検索方法において各置換サーバがレジスタに保持する信頼度情報の例を示す図。
【図３４】置換サーバの入力リストを検索する更に他の処理例を示す流れ図。
【図３５】この発明による匿名通信路の他の実施例を示すブロック図。
【図３６】置換網のＪ段目における置換処理手順のＪの値による処理の選択手順を示すフロー。
【図３７】図３６における処理１の手順を示すフロー。
【図３８】図３６における処理２の手順を示すフロー。
【図３９】図３６における処理３の手順を示すフロー。
【図４０】記録媒体からこの発明による証明付置換撹乱部分復号方法のプログラムを読み出して証明付置換撹乱部分復号を実行するコンピュータシステムの概念図。
【図１】
0003540718.tif 000010
【図２】
0003540718.tif 000011
【図３】
0003540718.tif 000012
【図４】
0003540718.tif 000013
【図５】
0003540718.tif 000014
【図６】
0003540718.tif 000015
【図７】
0003540718.tif 000016
【図８】
0003540718.tif 000017
【図９】
0003540718.tif 000018
【図１０】
0003540718.tif 000019
【図１１】
0003540718.tif 000020
【図１２】
0003540718.tif 000021
【図１３】
0003540718.tif 000022
【図１４】
0003540718.tif 000023
【図１５】
0003540718.tif 000024
【図１６】
0003540718.tif 000025
【図１７】
0003540718.tif 000026
【図１８】
0003540718.tif 000027
【図１９】
0003540718.tif 000028
【図２０】
0003540718.tif 000029
【図２１】
0003540718.tif 000030
【図２２】
0003540718.tif 000031
【図２３】
0003540718.tif 000032
【図２４】
0003540718.tif 000033
【図２５】
0003540718.tif 000034
【図２６】
0003540718.tif 000035
【図２７】
0003540718.tif 000036
【図２８】
0003540718.tif 000037
【図２９】
0003540718.tif 000038
【図３０】
0003540718.tif 000039
【図３１】
0003540718.tif 000040
【図３２】
0003540718.tif 000041
【図３３】
0003540718.tif 000042
【図３４】
0003540718.tif 000043
【図３５】
0003540718.tif 000044
【図３６】
0003540718.tif 000045
【図３７】
0003540718.tif 000046
【図３８】
0003540718.tif 000047
【図３９】
0003540718.tif 000048
【図４０】
0003540718.tif 000049