(57)【特許請求の範囲】
【請求項１】
ネットワーク上において利用者装置から少なくとも１の中継サーバ装置を介して上記中継サーバ装置に対応する暗号鍵の情報を保有する利用者装置から受信者装置に匿名で情報データを送る匿名通信方法において、
(a) 各中継サーバ装置が予め自分の秘密情報とそれに対応する公開情報を演算により生成し、当該秘密情報と当該公開情報を第三者機関装置に登録するステップと、
(b)上記第三者機関装置が上記公開情報を上記ネットワーク上で公開するステップと、
(c) 利用者装置が、
上記第三者機関が上記ネットワーク上で公開する各中継サーバ装置の公開情報を、当該ネットワークを介して、当該第三者機関装置より取得し、
匿名通信経路を形成する中継サーバ装置を経路に沿った順に１つ以上選択し、
上記各中継サーバ装置と共有する値に対し当該利用者装置の秘密情報によりべき乗演算を行って鍵生成情報を生成し、
上記第三者機関装置より取得した各中継サーバ装置の公開情報のうち上記選択した各中継サーバ装置の公開情報に対し当該利用者装置の秘密情報によりべき乗演算を行って各中継サーバ装置のための検証鍵を生成し、
上記匿名通信経路の最後の中継サーバ装置における送信すべき暗号データは上記利用者装置が送信すべき情報データ、送信すべき検証用データとその宛先アドレスは空の値とし、中継サーバ装置ごとに、送信先である宛先アドレスと、送信すべき暗号データと、送信すべき検証用データとを含む組を当該中継サーバ装置に対応する暗号鍵で暗号化することにより当該中継サーバ装置が受信すべき暗号データを生成し、かつ当該中継サーバ装置に対応する検証鍵と、自己のアドレスと、受信すべき上記暗号データとを含む情報を演算処理することにより当該中継サーバ装置が受信すべき検証用データを生成する処理を、上記匿名通信経路の最後の中継サーバ装置から最初の中継サーバ装置まで順次繰り返すことにより多重暗号化処理を行ない、
上記多重暗号化処理によって最後に得られた暗号データと当該暗号データと当該中継サーバ装置に対応する検証鍵を含む情報を演算処理して得られた検証用データと、上記鍵生成情報と、を含む送信データを選択した最初の中継サーバ装置に送信するステップと、
(d) 選択された各中継サーバ装置が、
受信データ中の鍵生成情報に対し自分の秘密情報によりべき乗演算を行って生成した検証鍵と当該受信データ中の暗号データとを含む情報を演算処理して得られた検証用データが当該受信データ中の検証用データと一致するか判定することにより当該受信データが正しいか検証し、正しければ当該中継サーバ装置に対応する暗号鍵を使って当該受信データ中の暗号データを復号処理して次の暗号データと次の検証用データと次の送信宛先アドレスを得て、当該鍵生成情報を自分の秘密情報を用いてべき乗演算することにより更新して当該次の暗号データ及び当該次の検証用データと共に送信データとして当該次の送信宛先アドレスに送信し、検証結果が正しくなければ上記第三者機関装置に不正の報告として上記受信データを送信するステップと、
(e) 上記第三者機関装置が上記不正の報告として受信データを受けると、その中の鍵生成情報に対し不正を報告した中継サーバ装置の上記秘密情報によりべき乗演算をして生成した検証鍵と当該受信データ中の暗号データとを含む情報を演算処理して得られた検証用データが当該受信データ中の検証用データと一致するか判定することにより当該受信データが正しいかを検証するステップ、
とを含むことを特徴とする匿名通信方法。
【請求項２】
請求項１に記載の匿名通信方法において、上記第三者機関装置は複数設けられ、上記ステップ(a) において各上記中継サーバ装置は上記秘密情報を秘密分散法によりそれぞれの第三者機関装置に分散しており、上記ステップ(e) において上記第三者機関装置の複数が協力して分散した上記秘密情報を復元して検証に用いることを特徴とする匿名通信方法。
【請求項３】
請求項１に記載の匿名通信方法において、上記利用者装置は複数存在し、上記ステップ（c）において各上記利用者装置はそれぞれが任意に選択した中継サーバ装置によりそれぞれの匿名通信経路を指定し、上記ステップ(d) において各上記中継サーバ装置はその中継サーバ装置を選択した全ての利用者装置から受信した受信データの順序に対し対応する送信データの順序を入れ替えてそれぞれの送信宛先アドレスに送信することを特徴とする匿名通信方法。
【請求項４】
請求項１に記載の匿名通信方法において、上記ステップ(c) において上記利用者装置は上記鍵生成情報についての離散対数を知っていることをゼロ知識証明するステップを含むことを特徴とする匿名通信方法。
【請求項５】
請求項１に記載の匿名通信方法において、上記ステップ(d) は上記中継サーバ装置が上記次の鍵生成情報について離散対数を知っていることをゼロ知識証明するステップを含むことを特徴とする匿名通信方法。
【請求項６】
請求項１に記載の匿名通信方法において、上記ステップ(c) は上記選択した各中継サーバ装置の上記公開情報から演算により共通秘密鍵を生成し、その共通秘密鍵を上記暗号鍵として暗号化を行い、上記ステップ(d) において各上記中継サーバ装置は上記受信データ中の鍵生成情報と自己の秘密情報を用いて演算処理により共通秘密鍵を上記暗号鍵として生成し、それを使って上記暗号データの復号処理を行うことを特徴とする匿名通信方法。
【請求項７】
請求項１に記載の匿名通信方法において、上記ステップ(a) において、各中継サーバ装置は公開鍵暗号方式の公開鍵と秘密鍵のペアを演算により生成し、当該秘密鍵と当該公開鍵を上記第三者機関装置に登録し、上記ステップ(b)において、上記第三者機関装置が上記公開鍵を上記ネットワーク上で公開し、上記ステップ(c)は、上記第三者機関が上記ネットワーク上で公開する各中継サーバ装置の公開鍵を、当該ネットワークを介して、当該第三者機関より取得し、上記選択した中継サーバ装置のそれぞれに対する共通秘密鍵を上記中継サーバ装置に対応する暗号鍵としてそれぞれランダムに生成する処理を含み、上記多重暗号化処理において、上記暗号データの生成は対応する当該共通秘密鍵を暗号鍵として使用して暗号化を行い、かつ、各中継サーバ装置の共通秘密鍵と送信宛先アドレスに送信すべき暗号化共通秘密鍵の組を当該第三者機関装置より取得した各中継サーバ装置の公開鍵のうち上記選択した中継サーバ装置の公開鍵により暗号化することにより上記中継サーバ装置の直前の中継サーバ装置がその送信宛先アドレスに送信すべき暗号化共通秘密鍵を生成することを、上記最後の中継サーバ装置から最初の中継サーバ装置まで順次繰り返す処理を含み、上記送信データを送信するステップは、上記多重暗号化処理の結果として最後に得られた暗号化共通秘密鍵を上記送信データに含めて上記最初の中継サーバ装置に送信し、上記ステップ(d) の復号処理は、上記受信データ中の暗号化共通秘密鍵を自己の秘密鍵で復号して共通秘密鍵を得て、その復号した共通秘密鍵を上記暗号鍵として使って上記受信データ中の上記暗号データの復号を行うことを特徴とする匿名通信方法。
【請求項８】
請求項１に記載の匿名通信方法において、上記ステップ(e) は上記ゼロ知識証明を検証するステップを含むことを特徴とする匿名通信方法。
【請求項９】
請求項１に記載の匿名通信方法において、上記最後の中継サーバ装置は復号機能を有さない公開掲示板として機能するサーバであり、(f) 上記最後から１つ前の中継サーバ装置から受信したデータを上記公開掲示板に公開するステップと、(g) 上記第三者機関装置が上記公開掲示板上の受信データを検証し、正しければ復号処理を行ってその復号結果を上記公開掲示板に公開するステップ、とを更に含むことを特徴とする匿名通信方法。
【請求項１０】
請求項１に記載の匿名通信方法において、上記ステップ(a) において、各中継サーバ装置は公開鍵暗号方式の公開鍵と秘密鍵のペアを演算により生成し、上記秘密鍵と上記公開鍵を上記第三者機関装置に登録し、上記ステップ（b）において、上記第三者機関装置が上記公開鍵を公開し、上記ステップ(c) の暗号化処理は上記利用者装置が各上記中継サーバ装置の公開鍵を上記ネットワークを介して、第三者機関装置より取得し、当該第三者機関装置より取得した各中継サーバ装置の公開鍵のうち上記選択した中継サーバ装置の公開鍵を上記暗号鍵として使用して上記暗号化を行い、上記ステップ(d) は各上記中継サーバ装置が自分の秘密鍵により復号処理を行うことを特徴とする匿名通信方法。
【請求項１１】
請求項１乃至１０のいずれかに記載の匿名通信方法において、上記ステップ(e) は、上記第三者機関装置が検証により不正な中継サーバ装置を検出した場合にその中継サーバ装置に成り代わって処理を行うステップを含む。
【請求項１２】
利用者装置から受信者装置へ匿名通信経路を形成するための複数の中継サーバ装置がネットワーク上に設けられ、少なくとも１つの第三者機関装置が当該ネットワークに接続され、当該各中継サーバ装置は予め自分の秘密情報と秘密情報に対応する公開情報を第三者機関装置に登録し、当該第三者機関装置が当該公開情報を当該ネットワーク上で公開する匿名通信システムにおける利用者装置において、
乱数を生成する乱数生成器と、
上記ネットワークを介して、第三者機関装置より匿名通信経路を形成する選択した各中継サーバ装置の公開情報を取得して記憶する記憶部と、
上記各中継サーバ装置と共有する値に対し、上記乱数によりべき乗演算を行って鍵生成情報を生成するべき乗演算部と、
上記記憶部に記憶された公開情報のうち選択した各中継サーバ装置の公開情報と上記乱数を使って演算により当該中継サーバ装置に対応する共通秘密鍵を生成すると共に、各中継サーバ装置の公開情報に対し上記乱数を使ってべき乗演算により当該中継サーバ装置に対する検証鍵を生成する鍵生成部と、
匿名通信により送信すべき情報データが入力される入力部と、
上記匿名通信経路の最後の中継サーバ装置における送信すべき暗号データは上記利用者装置が送信すべき情報データ、送信すべき検証用データとその宛先アドレスは空の値とし、中継サーバ装置ごとに、送信先である宛先アドレスと、送信すべき暗号データと、送信すべき検証用データとを含む組を当該中継サーバ装置に対応する暗号鍵で暗号化することにより当該中継サーバ装置が受信すべき暗号データを生成し、かつ当該中継サーバ装置に対応する検証鍵と、自己のアドレスと、受信すべき上記暗号データとを含む情報を演算処理することにより当該中継サーバ装置が受信すべき検証用データを生成する処理を、上記匿名通信経路の最後の中継サーバ装置から最初の中継サーバ装置まで順次繰り返すことにより多重暗号化処理を行ない、暗号データと検証用データを生成する暗号化部と、
上記暗号化部の上記多重暗号化処理によって最後に得られた上記暗号データ及び上記検証用データと上記べき乗演算部が生成した上記鍵生成情報を結合して送信データを生成し、上記匿名通信経路の最初の中継サーバ装置に送信するデータ結合送信部、
とを含むことを特徴とする利用者装置。
【請求項１３】
利用者装置から受信者装置へ匿名通信経路を形成するための複数の中継サーバ装置がネットワーク上に設けられ、少なくとも１つの第三者機関装置がネットワークに接続され、当該各中継サーバ装置は予め自分の秘密情報と秘密情報に対応する公開情報を第三者機関装置に登録し、当該第三者機関装置が当該ネットワーク上で当該公開情報を公開する匿名通信システムにおける利用者装置において、
乱数を生成する乱数生成器と、
上記ネットワークを介して、第三者機関装置より匿名通信経路を形成する各中継サーバ装置の公開情報を取得し記憶する記憶部と、
上記各中継サーバ装置と共有する値に対し、上記乱数によりべき乗演算を行って鍵生成情報を生成するべき乗演算部と、
上記記憶部に記憶された公開情報のうち選択した各中継サーバ装置の公開情報に対し上記乱数とそれより前の中継サーバ装置に対する検証鍵を使ってべき乗演算することにより当該中継サーバ装置に対応する検証鍵を生成する鍵生成部と、ただし、上記匿名通信経路の最初の中継サーバ装置の検証鍵はその中継サーバ装置の公開情報に対し上記乱数によりべき乗演算を行なって生成し、匿名通信により送信すべき情報データが入力される入力部と、
上記匿名通信経路の最後の中継サーバ装置における送信すべき暗号データは上記利用者装置が送信すべき情報データ、送信すべき検証用データとその宛先アドレスは空の値とし、中継サーバ装置ごとに、送信先である宛先アドレスと、送信すべき暗号データと、送信すべき検証用データとを含む組を当該中継サーバ装置に対応する暗号鍵で暗号化することにより当該中継サーバ装置が受信すべき暗号データを生成し、かつ当該中継サーバ装置に対応する検証鍵と、自己のアドレスと、受信すべき上記暗号データとを含む情報を演算処理することにより当該中継サーバ装置が受信すべき検証用データを生成する処理を、当該匿名通信経路の最後の中継サーバ装置から最初の中継サーバ装置まで順次繰り返すことにより多重暗号化処理を行ない、暗号データと検証用データを生成する暗号化部と、
上記暗号化部が生成した上記暗号データ及び上記検証用データと上記べき乗演算部が生成した上記鍵生成情報を結合して送信データを生成し、上記匿名通信経路の最初の中継サーバ装置に送信するデータ結合送信部、
とを含むことを特徴とする利用者装置。
【請求項１４】
請求項１２または１３に記載の利用者装置において、上記鍵生成情報についての離散対数を知っていることのゼロ知識証明を行うゼロ知識証明部が更に設けられていることを特徴とする利用者装置。
【請求項１５】
複数の利用者装置から任意の受信者装置へ匿名通信経路を形成するための複数の中継サーバ装置がネットワーク上に設けられ、少なくとも１つの第三者機関装置がネットワークに接続され、請求項１記載の匿名通信方法を実施する匿名通信システムにおける中継サーバ装置であり、
乱数を秘密情報として生成する乱数生成器と、
上記秘密情報を使ってべき乗演算により上記第三者機関装置に登録するための公開情報を生成する公開情報生成部と、
上記秘密情報により各利用者装置に対応する受信データ中の鍵生成情報に対しべき乗演算を行って検証鍵を生成し、その検証鍵と、当該受信データ中の暗号データとを用いて生成した検証用データが当該受信データ中の検証用データと一致するか判定することにより当該受信データが正しいかを検証する検証部と、
各利用者装置に対応する上記受信データ中の鍵生成情報に対し上記秘密情報を使ってべき乗演算することにより当該鍵生成情報を更新するとともに、自己の暗号鍵を使って当該受信データ中の暗号データを復号して次の暗号データと次の検証用データと次の送信宛先アドレスを得る復号部と、
上記復号された次の暗号データと次の検証用データと上記更新された鍵生成情報を含む送信データを生成し、全ての利用者装置に対応する受信データの順序に対し対応する送信データの順序を入れ替えてそれぞれの次の送信宛先アドレスに送信するデータ結合送信部、
とを含むことを特徴とする中継サーバ装置。
【請求項１６】
請求項１５に記載の中継サーバ装置において、上記復号部は、上記受信データ中の鍵生成情報と上記秘密情報を使って演算処理により上記暗号データを復号するための共通秘密鍵を生成する鍵生成部が設けられていることを特徴とする中継サーバ装置。
【請求項１７】
請求項１５または１６に記載の中継サーバ装置において、上記更新された鍵生成情報についての離散対数を知っていることのゼロ知識証明を行うゼロ知識証明部が設けられていることを特徴とする中継サーバ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネットなどのオープンなネットワーク上で匿名通信路を構成する従来のソフトウェア技術に対して、匿名通信路の利用者及び匿名通信路内の不正処理を検出可能とすることで安全な匿名通信路を構成するための情報セキュリティ技術に関するものであり、特に、匿名通信システムに使用される匿名通信方法、利用者装置及び中継サーバ装置に関する。
【０００２】
【従来の技術】
従来の匿名通信路技術として例えば非特許文献１がある。これは、通信路に1以上のサーバを中継させ、そのサーバは暗号処理などを行うことで入力データをかく乱して出力することで送信者の匿名性を実現する、mix-netと呼ばれる匿名通信路技術の一実現方式である。上記非特許文献１の方式は、中継するサーバは不特定多数とでき、かつ利用者が自由に通信経路(中継するサーバ)を決定でき、更にサーバの処理量も小さくて済む特長を持つ。
また、非特許文献２では、MAC(Message Authentication Code)と秘密分散法を利用した、匿名通信路の利用者や匿名通信路内での不正を防ぐことができる技術を提案している。
【０００３】
【非特許文献１】
千田、鬼頭、「拡張Hybrid  Mixとその応用」、コンピュータセキュリティシンポジウム2001(CSS2001)
【非特許文献２】
Jakobsson, Juels, "An optimally robust hybrid mix network," PODC'01
【非特許文献３】
「現代暗号」(岡本、山本)、産業図書、1997年、の217ぺ一ジ
【非特許文献４】
「暗号・ゼロ知識証明・数論」(岡本、太田)、共立出版、1995年
【非特許文献５】
R.Gennaro, S.Jarecki, H.Krawczyk, and T.Rabin, "The (in)security of distributed key generation in dlog-based cryptosystems," EUROCRYPT'99, LNCS1592, Spribger-Verlag, pp.295-310, 1999
【０００４】
【発明が解決しようとする課題】
非特許文献１の方式は、匿名通信路の利用者や匿名通信路内の不正に対しては考慮されていない。そのため、利用者の送信メッセージが正しく送信されない、不正者の追跡が困難、などの問題が起こりえる。
一方、非特許文献２の方式は、匿名通信路の利用者や匿名通信路内の不正を防ぐことはできるが、利用者が利用するサーバは予め決定され、かつその利用順序が一意に決定される。
ここで、それぞれの課題を相互補完するために、単純に非特許文献１の方式に非特許文献２の提案している不正を防ぐ技術を適用しようとした場合、以下の問題が生じる。
【０００５】
・非特許文献２の提案技術では、不正者の特定を行うフェーズにおいて、中継するサーバ管理者が協力する必要があるが、非特許文献１の方式では、中継するサーバは不特定多数とすることができることが特長の一つであり、その場合中継するサーバ管理者が協力することは一般に困難となる。
・非特許文献２の提案技術では、中継するサーバが出力するデータに対してゼロ知識証明と呼ばれる技術を用いて自身の処理正当性を保証させているが、非特許文献１の方式では、そのゼロ知識証明をそのまま適用することができない。
本発明の目的は、上記に挙げた問題点を解決し、利用者が自由に１つ以上の中継サーバを選択して匿名通信経路を決定でき、匿名通信路の利用者や匿名通信路内の不正を困難とする匿名通信方法及びそれを使用する利用者装置と中継サーバを提供することである。
【０００６】
【課題を解決するための手段】
この発明によれば、ネットワーク上において送信者装置から少なくとも１の中継サーバを介して受信者装置に匿名で情報データを送る匿名通信方法において、
(a) 各中継サーバは予め秘密情報を第三者機関装置に登録し、対応する公開情報を公開し、
(b) 送信者装置は匿名通信経路を形成する中継サーバを選択し、選択した中継サーバの公開情報を使って送信すべき情報データを指定宛先とともに暗号化し、得られた暗号データと鍵生成情報と検証用データを含む送信データを選択した最初の中継サーバに送信し、
(c) 選択された中継サーバは受信データをその受信データ中の鍵生成情報を使って生成した検証鍵により受信した検証用データを検証し、正しければ上記受信データ中の暗号データを復号処理して次の暗号データと次の検証用データと指定宛先を得て、上記鍵生成情報を自分の秘密情報で更新して復号した暗号データ及び検証用データとともに送信データとして復号された指定宛先に送信し、検証結果が正しくなければ上記第三者機関装置に報告し、
(d) 上記第三者機関装置は不正の報告を受けると、中継サーバの上記秘密情報を使って上記中継サーバの送信データを検証する。
【０００７】
このように、各中継サーバの秘密情報を第三者機関装置に与えておき、秘密情報に対応する公開情報を公開しておくことにより、送信者装置は任意に選択した中継サーバによる通信経路を決定し、それらの中継サーバの公開情報を使って受信データの復号処理を行うことができる。また、不正の報告に対し、第三者機関装置は中継サーバの秘密情報を使って中継サーバの入出力データを検証でき、不正サーバに代わって匿名通信のための処理を行うこともできる。
【０００８】
【発明の実施の形態】
次に、本発明の実施の形態について詳細に説明する。まず第1の実施形態として、匿名通信路の利用者がある端末に匿名で安全にデータを送る方法を説明する。
次に第２の実施形態として、正しい中継サーバあるいは最終受信者が、自身の入力に対して不正があるとして第三者機関にそれを申し出た場合の、第三者機関による不正者特定方法を説明する。第３の実施形態では、匿名通信路の利用者により端末に送られたデータが、通信路内で改ざんされていないかどうかを第三者機関が検証できる方法を述べる。第４の実施態様では、共通鍵暗号方式の代わりに、公開鍵暗号方式を使用する例を説明する。最後に第５の実施形態で、本発明により実現可能となる匿名通信モデルについての一例を述べる。
なお全ての実施形態において、離散対数問題を拠り所とするような大きな素数p、q(qはp-1の約数となるような関係をもつ)及び位数がqとなるような乗法群(Z/pZ)*の元gがあらかじめ公開されているものとする。また、全ての送信情報は公開される、あるいは署名が付与されるなどで誰から誰に何が送信されたかを保証する手段がとられているものとする。
第1の実施形態
【０００９】
図１はこの発明が適用される通信システムの構成を示し、匿名対通信路を形成するための複数の中継サーバMi(i=1, 2, …)がオープンなネットワークNWに接続されており、また、ネットワークNWには複数の利用者Uj(j=1,2,…)と１つ以上の第三者機関TP1, TP2, …, TPmと受信者R1, R2, …が接続されているものとする。このとき、匿名通信路利用者Ujと中継するサーバMiの不正を防ぐことを目的として、第三者機関TPk(k=1, 2, …, m)が存在する。ここでUjの不正とは、自身の不正な入力を否認し、不正の所在を不明確にすることを意味し、Miの不正とは、自身への入力に対し不正な処理を施して出力することを意味する。
まず、Miが中継サーバとして登録する場合として以下を行う。
（Ａ）．乱数ai、biを生成して公開情報
【数１】
0004146252.tif 000002
を計算し、(hi, zi)を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報ai、biをTPk (k=1,2,…,m)に分散して送る。
【００１０】
上記の処理で検証可能秘密分散法とは、TPkのうち何人かが協力しない限り秘密情報は復元されない秘密分散技術に加え、正しく秘密情報が分散されていることをTPkが検証できる技術のことである。秘密情報の復元には閾値が設定され、例えば(m',m)秘密分散とはｍ人のうち、m'人以上が集まれば秘密情報を復元できるが、m'人未満であれば秘密情報は全く得られない。即ち、ｍ人のうち少なくともm'人は正しいと仮定した場合に有効な方式となる（threshold schemeと呼ばれている）。これにより、中継サーバが不正な値を分散して送ることを防ぐことができる。また、検証可能秘密分散法として例えば、非特許文献３にその方法が示されている。TPkがMiを正しいと判断した場合、Miは中継サーバとしてTPkから証明書が発行されるなどして承認される。ここで、(m', m)秘密分散であればm'人以上の第三者機関からの証明書があればよい。
次に匿名通信路利用者Ujは以下に図２のフローを参照して説明する処理を行う。
Ujの最終的な送信先である受信者を便宜上M3、そしてM3の公開情報を
【数２】
0004146252.tif 000003
とする(a3、b3は乱数)。
（Ａ）．利用する中継サーバを決定する(ここでは、M1, M2の順に利用するものとする)。
（Ｂ）．乱数rjを生成して（ステップＳ１）鍵生成情報
【数３】
0004146252.tif 000004
を計算し（ステップＳ２）、更に次式
【数４】
0004146252.tif 000005
をi=1, 2, 3について計算する（ステップＳ３〜Ｓ６）。ここでw0,j=1、H、L：一方向性ハッシュ関数、とする。
（Ｃ）．i=2, 1, 0の順に暗号データEi,jと検証用データui,jを次式
【数５】
0004146252.tif 000006
により計算し（ステップＳ７〜Ｓ１０）、C0,j=(E0,j, u0,j、G0,j)をM1に送る（ステップＳ１１）。ここでEEKi+1,jは鍵Ki+1,jを用いた共通鍵暗号の暗号化アルゴリズム、HEDDi+2はサーバMi+2のアドレス、HEDD4は空の値（即ち０ビット）、‖はデータの連結、u3,jは空の値、E3,jは匿名送信すべき平文msgj、Iはイベントごとに固有な値とする。式(6),(7)をi=2,1,0と繰り返し実行することにより、受信者側に近い順に中継サーバに対する鍵で平文を多重暗号化することになる。なお、式(7) はハッシュ関数でなく、鍵をZi+1,jとしたMAC(Message Authentication Code)関数と置き換えても良い。
（Ｄ）．gを底としたG0,jの離散対数を知っていること、即ち式(1) の秘密情報rjを知っていることをゼロ知識証明する（ステップＳ１２）。
【００１１】
上記のゼロ知識証明については、例えば非特許文献４に紹介されており、ここではゼロ知識証明の具体的なアルゴリズムの説明は省略する。また、ゼロ知識証明を検証するのは、M1、第三者機関、あるいはその他の機関のいずれが行っても良い。そしてこの検証をはじめに行い、不正と判断された場合は即座にUjを除外する。
次に最初の中継サーバM1による処理を図３を参照して説明する。サーバM1はC0,j=(E0,j, u0,j, G0,j), j=1, 2, …, nを受け取り（ステップＳ１）、以下の処理を行う。なおここではM1はn個のデータC0,j,(j=1, 2, …, n)を受け取り、処理後のｎ個のデータC1,jを全てM2へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数６】
0004146252.tif 000007
を計算し（ステップＳ２，Ｓ３）、u0,j＝u'0,jが成り立つことを確認する（ステップＳ４）。即ち、鍵生成情報G0,jから式(8)により検証鍵Z'1,jを生成し、その検証鍵を使って式(9)により生成した値が受信データC0,j中の検証用データu0,jと一致すれば受信データC0,jは正しいと判定する。
（Ｂ）．j=1, 2, …, nについて、
【数７】
0004146252.tif 000008
により暗号データE0,jを復号処理して次の中継サーバのアドレスHEDD2、暗号データE1,j、検証用データu1,jを得る（ステップＳ６）。ここでDDK1,jは鍵K1,jを用いた共通鍵暗号の復号アルゴリズムとする。
（Ｃ）．jの順序を適当に入れ替えてC1,j=(E1,j, u1,j, G1,j)を式(13)の復号結果中のアドレスHEDD2により指定されたサーバM2に送る（ステップＳ７）。
（Ｄ）．式(12)におけるG0,j(j=1, 2, …, n)を底とした、G1,j(j=1, 2, …, n)の積
【数８】
0004146252.tif 000009
の離散対数を知っている、即ちj=1, 2, …, nについてL(T1,j)を知っていることをゼロ知識証明する（ステップＳ８）。
ステップＳ４でu0,jとu'0,jが一致しなかった場合は、第三者機関TPkに不正の検出を報告する（ステップＳ９）。
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれn個のM1の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、M1以外に対してはUjの匿名性が満たされたことになる。なお離散対数を知っていることをゼロ知識証明するアルゴリズムは公知の技術であるため省略するが、このゼロ知識証明が行われないと、M1は適当な出力をM2に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことなので説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、サーバM2、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００１２】
次にC1,j=(E1,j, u1,j, G1,j)を受け取ったM2は以下を行う。以下の式(14)〜(19)で示す処理手順は、式(8)〜(13)と対応しており、図３の場合と基本的に同様なので、サーバM2としての処理手順の図は示さない。なおここではn個のデータ(j=1, 2, …, n)を受け取り、M2は全てM3へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数９】
0004146252.tif 000010
を計算し、u1,j＝u'1,jが成り立つことを確認する。
（Ｂ）．j=1, 2, …, nについて、
【数１０】
0004146252.tif 000011
を計算する
（Ｃ）．jの順序を適当に入れ替えてC2,j=(E2,j, u2,j, G2,j)をHEDD3に従ってM3に送る。
（Ｄ）．G1,j(j=1, 2, …, n)を底とした、G2,j(j=1, 2, …, n)の積P2の離散対数を知っている、即ち、式(18)におけるj=1, 2, …, nについてのL(T2,j)を知っていることをゼロ知識証明する。
【００１３】
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれM2のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはM1とM2が結託しない限りは全てのものに対してUjの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
最後にC2,j=(E2,j, u2,j, G2,j)を受け取ったM3は以下を行う。サーバM3の処理もM1, M2の処理における式(12), (18)に対応する処理を行わない点を除いてM1, M2の処理とほとんど同じである。
（Ａ）．j=1, 2, …, nについて、
【数１１】
0004146252.tif 000012
を計算し、u2,j＝u'2,jが成り立つことを確認する。
（Ｂ）．j=1, 2, …, nについて、
【数１２】
0004146252.tif 000013
を計算する。
これにより、M3はmsgjを匿名で受け取ることになり、Ujの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバMiの不正あるいは匿名通信路の利用者Ujの不正入力も、正しい検証者(他の中継サーバ管理者、最終受信者、第三者機関)によって検出される。
【００１４】
図４は上記第１実施形態における利用者Ujの装置（利用者装置と呼ぶ）の処理機能構成を示す。利用者装置は公開された情報hi,zi,gを格納する記憶部１１と、乱数rjを生成する乱数生成器１２と、式(1) 二より鍵生成情報を計算するべき乗演算部１３と、ゼロ知識証明部１４と、データ結合送信部１５と、入力部１６と、鍵生成部２０と、暗号化部３０とから構成されている。
鍵生成部２０は式(2) を計算するべき乗演算部２１と、式(3) を演算する共通鍵計算部２２と、式(4) を計算するハッシュ部２３と、前回のハッシュ結果wi-1,jを保持しているレジスタ２４と、式(5) を計算するべき乗演算部２５とから構成され、i=1, 2, 3について順次演算を実行する。暗号化部３０は、サーバMi+1のアドレスHEDDi+1と前回の暗号化結果Ei+1,jと、前回のハッシュ結果ui+1,jを保持するレジスタ３１と、式(6) による暗号化を行う暗号演算部３２と、式(7) のハッシュ演算を行うハッシュ部３３とから構成されており、Ei+1,jの初期値E3,jとして入力部１６から匿名送信されるべき平文msgjが入力され、i=2, 1, 0の順に演算を繰り返すことによりE0,jとu0,jが求まる。これらとG0,jとがデータ結合送信部１５で結合され、暗号データC0,jとしてサーバM1へ送信される。
【００１５】
図５は、中継サーバM1の機能構成を示す。サーバM1は値ｇ、秘密情報a1, b1を格納する記憶部４１と、上記秘密情報としての乱数a1, b1を生成する乱数生成器４２と、べき乗部４３と、検証部５０と、復号部６０と、データ結合送信部４４と、ゼロ知識証明部４５とから構成されている。
検証部５０は受信したデータC0,jから式(8), (9)又は式(14), (15)により検証鍵Z'1,jを演算する検証鍵演算部５１と、ハッシュ部５２と、u0,jとu'0,jが一致するか比較判定する比較部５３とから構成されている。
復号部６０は、式(10)の計算を行うべき乗部６１と、そのべき乗演算結果を使って式(11)により共通秘密鍵K1,jを生成する鍵生成部６２と、式(12)により更新された鍵生成情報G1,jを計算するべき乗部６３と、受信データC0,j中の暗号データE0,jを共通秘密鍵K1,jにより復号し、次にデータC1,jの送信先サーバM2のアドレスHEDD2と暗号データE1,jと検証用データu1,jを得る復号処理部６４とから構成されている。
上記第１実施形態の利用者Ujの処理を示す図２において、ステップＳ１２はゼロ知識証明を行うので利用者UjからサーバM1への送信データC0,jに不正があった場合には、ゼロ知識証明の検証により容易に不正を検出できる。従って、図３における第１の中継サーバM1の処理ステップＳ２，Ｓ３，Ｓ４による検証鍵Z'1,jを使った検証は省略し、ゼロ知識証明の検証を行ってもよい。その場合は、図５における検証部５０を省略できる。
【００１６】
第２の実施形態
次に第２の実施形態について説明する。ここでは、正しい中継サーバあるいは最終受信者が、自身の入力に対して不正があるとして第三者機関にそれを申し出た場合の、第三者機関による不正者特定方法を述べる。なお記号などについては第1の実施形態に従うものとする。
第1の実施形態で、Mi(i=0, 1, 2)は、Z'i,j=Gi-1,jbi及びu'i-1,j≡H(Z'i,j‖HEDDi+1‖Ei-1,j‖I)を計算し（例えば図３のステップＳ２，Ｓ３）、ui-1,j=u'i-1,jが成り立つことを確認する処理があるが、ここでは、それが成り立たないjがあった場合に、Miはそのことを第三者機関TPk(k=1, 2, …, m)に報告した場合に（ステップＳ９）、TPkが不正者を特定する手順を説明する。なお、第三者機関は半数以上が正しければ、Miの秘密情報ai、biを用いた計算の復元が可能となる方式を用いるものとし、第三者機関の例えば半数以上は正しいと仮定する。この方式はthreshold schemeとよばれ、例えば非特許文献５などに示されている。第三者機関がMiによって分散された秘密情報を用いて以下を行う処理手順を図６を参照して説明する。
【数１３】
0004146252.tif 000014
を計算し（ステップＳ１，Ｓ２）、ui-1,jとu'i-1,jが一致し、かつMi-1による、Gi-2,j(j=1, 2, …, n)を底とした、Gi-1,j(j=1, 2, …, n)の積Pi-1の離散対数を知っていることのゼロ知識証明が正しいかを判定し（ステップＳ３）、正しいことが検証されれば、即ち、Mi-1が不正を行っていなければMiを不正サーバとして除外し、第三者機関はthreshold schemeにより、Miの処理を代理する（ステップＳ４）。u'i-1,j≠ui-1,jであった場合はMiより前のサーバが不正を行ったと判定し、以下の処理を行う。
（Ｂ）．i=1であれば（ステップＳ５の判定）、利用者Ujが不正を行ったと判定し、利用者Ujを排除し、C0,jを除去する（ステップＳ６）。
【００１７】
i≠1であれば、以下の処理を行う。
（Ｃ）．サーバMi-1にデータCi-1,jと対応したデータCi-2,j'の公開を要求する、あるいは単にj'の公開を要求する（ステップＳ７）。
（Ｄ）．Ci-2,j'からCi-1,jを計算し（ステップＳ８）、Mi-1の公開情報と一致しなければ（ステップＳ９の判定）、Mi-1を不正サーバとして除外し、第三者機関はthreshold schemeにより、Mi-1の処理を代理する（ステップＳ１０）。
（Ｅ）．Z'i-1,j'とu'i-2,j'≡H(Z'i-1,j‖HEDDi‖Ei-2,j'‖I)を計算し（ステップＳ１１）、ui-2,j'＝u'i-2,j'が成り立たなければ（ステップＳ１２の判定）、Mi-1を不正サーバとして除外し、第三者機関はthreshold schemeにより、Mi-1の処理を代理する（ステップＳ１３）。
（Ｆ）．ステップＳ１２でui-2,jとu'i-2,j'が一致した場合、入力データCi-1,jを不正な入力データと判定し、即ち、Mi-1より前のサーバまたは利用者に不正があると判定し、i←i-1、j←j'として（ステップＳ１４）、ステップＳ１の処理に戻る。
以上の操作を不正者が発見されるまでｉを１ずつ減算して繰り返すことにより不正者を特定することができる。
【００１８】
図７は上記第２実施形態における第三者機関の機能構成を示す。図６の処理手順の説明から理解されるように、第三者機関の処理は不正サーバの検出を除けばサーバと同様の処理を行っており、従って、図５に示したサーバ装置の構成とほとんど同じであるが、図６のステップＳ１０の比較を行う比較判定部７３が設けられ、ステップＳ８で要求したデータCi-2,j'から復号生成したデータCi-1,j'と受信したデータCi-1,jが一致するか判定する。図６のステップＳ９の処理は、要求したデータCi-2,j'=(Ei-2,j', ui-2,j', Gi-2,j')を復号部９０に入力して復号処理を行うことにより結合部７２に得られる。その他の構成の説明は省略する。
第３の実施形態
ここでは第３の実施形態として、匿名通信路の受信者は公開掲示板として機能するサーバの場合であり、利用者から送られたデータを公開する場合の構成と処理を説明する。前述の第１及び第２実施形態で説明した匿名通信では、最後の中継サーバが例えば図３のステップＳ６で復号処理を行い、例えば復号結果E3,j=msgjが得られ、これを受信者に送る。この最後の中継サーバが第３の実施形態に使用された場合、公開掲示板機能を果たす最終サーバはデータC2,j=(E2,j, u2,j, G2,j)を自分で復号処理して平文msgjを公開する。もしそのサーバが不正に異なる平文msg'jを公開しても発見されない恐れがある。そこでこの第３実施形態においては、公開掲示板としてのサーバは復号機能を有さず、代わりに第三者機関が復号処理を行い、復号結果を掲示板に公開する。以下の説明における記号などについては第1の実施形態に従うものとする。
【００１９】
まずTPk(k=1, 2, …, m)は以下を行う。
（Ａ）．乱数uk、vkを生成して
【数１４】
0004146252.tif 000015
を計算し、(xk, yk)を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報uk、vkをTPt(t≠k)に分散して送る。
以降用いる記号として、Ｘをxk(k=1, 2, …, m)の積、Ｙをyk(k=1, 2, …, m)の積とする。また、第三者機関は誰もが閲覧可能な公開掲示板を提供するサーバを利用し、そこにＸ，Ｙが公開されているものとする。なおここでは簡単のため便宜上、
【数１５】
0004146252.tif 000016
即ち、
a3＝u1+u2+…+um                          (31)
b3＝v1+v2+…+vm                          (32)
とし、その公開掲示板を提供するサーバをM3とする。
一方、Miが中継サーバとして登録する場合は以下を行う。
（Ａ）．乱数ai、biを生成して
【数１６】
0004146252.tif 000017
を計算し、(hi, zi)を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報ai、biをTPkに分散して送る。
TPkがMiを正しいと判断した場合、Miは中継サーバとしてTPkに証明書が発行されるなどして承認される。
【００２０】
次に匿名通信路利用者Ujは以下を行う。Ujの最終的な送信先を公開掲示板を提供するサーバM3とし、Ujによる平文msgjは第三者機関によって復号され、その公開掲示板に公開されるものとする。
利用者Ujの処理及び中継サーバM1,M2の処理は第１実施形態の場合と同様なので説明を省略する。
掲示板サーバM3は中継サーバM2からデータC2,j=(E2,j, u2,j, G2,j)を受信するとそれを掲示板に公開する。第三者機関TPk(k=1, 2, …, m)は、まず掲示板のデータC2,jが通信路内で改ざんされていないかどうかを検証するため、threshold schemeを用いて以下を行う。
（Ａ）．j=1, 2, …, nについて、
【数１７】
0004146252.tif 000018
を計算し、u2,j=u'2,jが成り立つことを確認する。もし成り立たない場合は、第２の実施形態で示した不正者特定処理を行う。その処理方法は既に示してあるため省略する。
ここでは上記処理（Ａ）が正しいとして、次の処理を説明する。第三者機関TPk(k=1, 2, …, m)はthreshold schemeを用いて以下を行う。
（Ｂ）．j=1, 2, …, nについて、復号処理を
【数１８】
0004146252.tif 000019
の計算により行う。これにより得られた復号平文msgjは秘密情報を除く他の中間データとともにすべて掲示板に公開する。従って、掲示板サーバM3はmsgjを匿名で受け取ることになり、Ujの匿名性が確保される。また、中継サーバMiの不正あるいは匿名通信路の利用者Ujの不正入力も、第三者機関によって検出される。
第４の実施形態
ここでは、第１の実施形態において暗号化及び復号化処理が共通秘密鍵方式により行われる例を示したが、公開鍵暗号方式によって行われる場合について以下に説明する。
【００２１】
中継するサーバMi(i=1, 2, …)がオープンなネットワークに多数つながっているものとする。このとき、匿名通信路利用者と中継するサーバMiの不正を防ぐことを目的として、第三者機関TPk(k=1, 2, …, m)が存在する。また、中継するサーバMi(i=1, 2, …)が利用する公開鍵暗号アルゴリズムは統一され、公開されているものとする。
まず、Miが中継サーバとして登録する場合として以下を行う。
（Ａ）．公開鍵暗号アルゴリズムの公開鍵と秘密鍵のペア(PKi, SKi)を生成する。
（Ｂ）．乱数biを生成し、
【数１９】
0004146252.tif 000020
を計算する。
（Ｃ）．PKi, ziを公開する。
（Ｄ）．検証可能秘密分散法を用いて秘密情報SKi, biをTPkに分散して送る。
【００２２】
次に匿名通信路利用者Ｕｊの処理手順を図８を参照して説明する。Ｕｊの最終的な送信先である受信者を便宜上Ｍ３、そしてＭ３の公開情報をＰＫ３， ｚ３＝ｇｂ３とする。ＰＫ３はＭ３の秘密鍵ＳＫ３に対応する公開鍵、ｂ３は乱数である。
（Ａ）．利用する中継サーバを決定する（ここでは、Ｍ１， Ｍ２の順に利用するものとする）。
（Ｂ）．乱数ｒｊを生成し（ステップＳ１）、
【数２０】
0004146252.tif 000021
を計算する（ステップＳ３〜Ｓ６）。ここでｗ０，ｊ＝１、Ｌ：一方向性ハッシュ関数、とする。
（Ｃ）．ｉ＝２， １， ０の順に
【数２１】
0004146252.tif 000022
を計算し（ステップＳ７〜Ｓ１０）、Ｃ０，ｊ＝（Ｅ０，ｊ， ｕ０，ｊ、Ｇ０，ｊ）をＭ１に送る（ステップＳ１１）。ここでＰＥＰＫｉ＋１は鍵ＰＫｉ＋１を用いた公開鍵暗号の暗号化関数、ＨＥＤＤｉ＋２はＭｉ＋２を示すアドレス、ＨＥＤＤ４は空の値、‖はデータの連結、ｕ３，ｊは空の値、Ｅ３，ｊは平文ｍｓｇｊ、Ｉはイベントごとに固有な値とする。なお、式（４５）はハッシュ関数でなく、鍵をＺｉ＋１，ｊとしたＭＡＣ（Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｃｏｄｅ）関数と置き換えても良い。また、Ｉ， ｕ０，ｊは省略してもよい。
（Ｄ）．ｇを底としたＧ０，ｊの離散対数を知っていることをゼロ知識証明する（ステップＳ１２）。
上記のゼロ知識証明を検証するのは、Ｍ１、 第三者機関、あるいはその他の機関のいずれが行ってもよい。その検証を初めに行い、不正と判断された場合は即座にＵｊを除外する。
【００２３】
次にサーバM1の処理手順を図９を参照して説明する。ステップＳ１でC0,j=(E0,j, u0,j, G0,j)を受け取ったM1は以下を行う。なおここではM1は受信したn個のデータC0,j(j=1, 2, …, n)を復号処理し、全てM2へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数２２】
0004146252.tif 000023
を計算し（ステップＳ２，Ｓ３）、u0,j=u'0,jが成り立つことを確認する（ステップＳ４）。
（Ｂ）．j=1, 2, …, nについて、
【数２３】
0004146252.tif 000024
を計算する（ステップＳ５，Ｓ６）。ここでPDSK1は鍵SK1を用いた公開鍵暗号の復号関数とする。
（Ｃ）．jの順序を適当に入れ替えてC1,j=(E1,j, u1,j, G1,j)をHEDD2に従ってM2に送る（ステップＳ７）。
（Ｄ）．G0,j(j=1, 2, …, n)を底とした、G1,j(j=1, 2, …, n)の積P1の離散対数を知っている、即ちj=1, 2, …, nについてL(Z1,j)を知っていることをゼロ知識証明する（ステップＳ８）。
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれn個のM1の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、M1以外に対してはUjの匿名性が満たされたことになる。ゼロ知識証明が行われないと、M1は適当な出力をM2に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことから説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、M2、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００２４】
次にC1,j=(E1,j, u1,j, G1,j)を受け取ったM2は以下の処理を行う。この処理は符号の添え字が異なっても基本的に図９に示したM1の処理と同様である。なおここではM2は受信したn個のデータC1,j(j=1, 2, …, n)を復号処理して全てM3へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数２４】
0004146252.tif 000025
を計算し（ステップＳ２，Ｓ３）、u1,j=u'1,jが成り立つことを確認する（ステップＳ４）。
（Ｂ）．j=1, 2, …, nについて、
【数２５】
0004146252.tif 000026
を計算する（ステップＳ５，Ｓ６）。
（Ｃ）．jの順序を適当に入れ替えてC2,j=(E2,j, u2,j, G2,j)をHEDD3に従ってM3に送る（ステップＳ７）。
（Ｄ）．G1,j(j=1, 2, …, n)を底とした、G2,j(j=1, 2, …, n)の積P2の離散対数を知っている、即ちj=1, 2, …, nについてL(Z2,j)を知っていることをゼロ知識証明する（ステップＳ８）。
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれM1のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはM1とM2が結託しない限りは、全てのものに対してUjの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
【００２５】
最後にC2,j=(E2,j, u2,j, G2,j)を受け取ったM3は以下を行う。
（Ａ）．j=1, 2, …, nについて、
【数２６】
0004146252.tif 000027
を計算し、u2,j=u'2,jが成り立つことを確認する。
（Ｂ）．j=1, 2, …, nについて、PDSK3(E2,j)=msgjを計算する。
これにより、M3はmsgjを匿名で受け取ることになり、Ujの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバMiの不正あるいは匿名通信路の利用者Ujの不正入力も、正しい検証者(他の中継サーバ管理者、最終受信者、第三者機関)によって検出される。しかし、その方法は第２実施形態から明らかなので、省略する。
【００２６】
第５の実施形態
第１の実施形態においては暗号化及び復号化処理が共通秘密鍵方式により行われる例を、第４実施形態においては暗号化及び復号化処理が公開鍵暗号方式によって行われる例を示したが、共通秘密鍵の暗号化及び復号化処理は公開鍵暗号方式で行い、その他の情報は共通秘密鍵方式によって行われる場合について以下に説明する。
中継するサーバMi(i=1, 2, …)がオープンなネットワークに多数つながっているものとする。このとき、匿名通信路利用者と中継するサーバMiの不正を防ぐことを目的として、第三者機関TPk(k=1, 2, …, m)が存在する。また、中継するサーバMi(i=1, 2, …)が利用する公開鍵暗号アルゴリズムは統一され、公開されているものとする。
【００２７】
まず、Miが中継サーバとして登録する場合として以下を行う。
（Ａ）．公開鍵暗号アルゴリズムの公開鍵と秘密鍵のペア(PKi, SKi)を生成する。
（Ｂ）．乱数biを生成し、
【数２７】
0004146252.tif 000028
を計算する。
（Ｃ）．検証可能秘密分散法を用いて秘密情報SKi, biをTPkに分散して送る。
【００２８】
次に匿名通信路利用者Ujの処理手順を図１０を参照して説明する。Ujの最終的な送信先である受信者を便宜上M3、そしてM3の公開情報をPK3, z3=gb3とする。PK3はUjの秘密鍵SK3に対応する公開鍵、b3は乱数である。
（Ａ）．利用する中継サーバを決定する(ここでは、M1, M2の順に利用するものとする)。
（Ｂ）．乱数rjを生成し（ステップＳ１）、
【数２８】
0004146252.tif 000029
を計算する（ステップＳ３〜Ｓ６）。ここでw0,j=1、L：一方向性ハッシュ関数、とする。
（Ｃ）．公開された共通鍵暗号アルゴリズムEEで用いるM1, M2, M3との共通秘密鍵K1,j, K2,j, K3,j をランダムに決定する。
（Ｄ）．i=2, 1, 0の順に
【数２９】
0004146252.tif 000030
を計算し（ステップＳ７〜Ｓ１０）、C0,j=(KK0,j, E0,j, u0,j、G0,j)をM1に送る（ステップＳ１１）。ここでPEPKi+1は鍵PKi+1を用いた公開鍵暗号の暗号化関数、KK3,jは空の値、HEDDi+2はMi+2を示すアドレス、HEDD4は空の値、‖はデータの連結、u3,jは空の値、E3,jは平文msgj、Iはイベントごとに固有な値とする。なお、式(62)はハッシュ関数でなく、鍵をZi+1,jとしたMAC(Message Authentication Code)関数と置き換えても良い。また、I, u0,jは省略してもよい。
（Ｅ）．gを底としたG0,jの離散対数を知っていることをゼロ知識証明する（ステップＳ１２）。
上記のゼロ知識証明を検証するのは、M1、 第三者機関、あるいはその他の機関のいずれが行ってもよい。その検証を初めに行い、不正と判断された場合は即座にUjを除外する。
【００２９】
次にサーバM1の処理手順を図１１を参照して説明する。ステップＳ１でC0,j=(KK0,j, E0,j, u0,j, G0,j)を受け取ったM1は以下を行う。なおここではM1は受信したn個のデータC0,j(j=1, 2, …, n)を復号処理し、全てM2へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数３０】
0004146252.tif 000031
を計算し（ステップＳ２，Ｓ３）、u0,j=u'0,jが成り立つことを確認する（ステップＳ４）。
（Ｂ）．j=1, 2, …, nについて、
【数３１】
0004146252.tif 000032
を計算する（ステップＳ５，Ｓ６）。ここでPDSK1は鍵SK1を用いた公開鍵暗号の復号関数とする。
（Ｃ）．jの順序を適当に入れ替えてC1,j=(KK1,j, E1,j, u1,j, G1,j)をHEDD2に従ってM2に送る（ステップＳ７）。
（Ｄ）．G0,j(j=1, 2, …, n)を底とした、G1,j(j=1, 2, …, n)の積P1の離散対数を知っている、即ちj=1, 2, …, nについてL(Z1,j)を知っていることをゼロ知識証明する（ステップＳ８）。
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれn個のM1の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、M1以外に対してはUjの匿名性が満たされたことになる。ゼロ知識証明が行われないと、M1は適当な出力をM2に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことから説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、M2、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００３０】
次にC1,j=(KK1,j, E1,j, u1,j, G1,j)を受け取ったM2は以下の処理を行う。この処理は符号の添え字が異なっても基本的に図１１に示したM1の処理と同様なので、図１１を参照されたい。なおここではM2は受信したn個のデータC1,j(j=1, 2, …, n)を復号処理して全てM3へ送るものとする。
（Ａ）．j=1, 2, …, nについて、
【数３２】
0004146252.tif 000033
を計算し（ステップＳ２，Ｓ３）、u1,j=u'1,jが成り立つことを確認する（ステップＳ４）。
（Ｂ）．j=1, 2, …, nについて、
【数３３】
0004146252.tif 000034
を計算する（ステップＳ５，Ｓ６）。
（Ｃ）．jの順序を適当に入れ替えてC2,j=(KK2,j, E2,j, u2,j, G2,j)をHEDD3に従ってM3に送る（ステップＳ７）。
（Ｄ）．G1,j(j=1, 2, …, n)を底とした、G2,j(j=1, 2, …, n)の積P2の離散対数を知っている、即ちj=1, 2, …, nについてL(Z2,j)を知っていることをゼロ知識証明する（ステップＳ８）。
jの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれM1のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはM1とM2が結託しない限りは、全てのものに対してUjの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
【００３１】
最後にC2,j=(KK2,j, E2,j, u2,j, G2,j)を受け取ったM3は以下を行う。
（Ａ）．j=1, 2, …, nについて、
【数３４】
0004146252.tif 000035
を計算し、u2,j=u'2,jが成り立つことを確認する。
（Ｂ）．j=1, 2, …, nについて、
【数３５】
0004146252.tif 000036
を計算する。
これにより、M3はmsgjを匿名で受け取ることになり、Ujの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバMiの不正あるいは匿名通信路の利用者Ujの不正入力も、正しい検証者(他の中継サーバ管理者、最終受信者、第三者機関)によって検出される。しかし、その方法は第２実施形態から明らかなので、省略する。
【００３２】
第６の実施形態
最後に第６の実施形態として、本発明により実現可能となる匿名通信モデルの例について図１を参照して述べる。
まずインターネットなどオープンなネットワークNW上に中継サーバとしてMi(i=1, 2, …)が不特定多数存在し、送信者としての各利用者Ujは任意の１つ以上の中継サーバを選択指定することにより匿名通信路10を構成する。図１では送信者Ujと受信者Rf間に中継サーバM1, M2, M3を介した匿名通信経路１０を形成した例を示している。例えば中継サーバMiは匿名通信路を商用利用するような業者から料金を徴収するようなアプリケーションサービスプロバイダなどである。そして匿名通信路を利用する側として、不特定多数の送信者Uj(j=1, 2, …)及び受信者Rf(f=1, 2, …)が存在する。また匿名通信路内の不正、即ちMiの不正を防ぐ目的で、ある一定数の第三者機関TPk(k=1, 2, …, m)が存在する。
【００３３】
第三者機関TPkは、Miあるいは受信者Rfが不正入力を検出した場合に、それに対応し、第2の実施形態で示したように不正者を特定することができる。また受信者Rfが受信結果を提示するような場合、その結果の正当性を第三者機関TPkが保証することができる。これについては第３の実施形態で示している。
受信者Rfとして、例えば電子投票の投票所が挙げられる。この場合、送信者Ujは投票者となり、自身の匿名性を守るために信頼できる経路及びMiを自身で選択することができる。またデータは暗号化されていることから、投票の秘密も保持される。データCi-1,jを受け取ったMiは、ある程度の数のデータを受け取ったら、第1の実施形態で示したような手順で暗号処理及び出力順序の置換を施し、HEDDで指定された送信者Ujの意図したアドレスヘデータを送信する。これをいくつかのMiが繰り返すことにより匿名性の信頼度が増していく。ただし、送信時間を優先するならば、送信者Ujはデータに時間を指定しておくことで、即座にMiはデータを出力することも可能である。ただしこの場合置換による匿名性はなくなる。
【００３４】
一方、データCi-1,jを受け取ったMiは、入力データの正当性を検証できるため、Miの不正を防ぐことができる。また投票所Rfにおいても、まず入力データの正当性が第三者機関TPkによって検証される。最終的な復号はthreshold schemeを用いて第三者機関TPkにより行われるため、正しい処理であることが保証される。また、受信者Rfの例として、相談所、ギャンブル、ショッピングなどが挙げられる。特にギャンブルやショッピングなど金銭が直接伴うものは不正に対して頑強なモデルが強く求められ、第三者機関TPkは非常に重要となる。また、複数のイベントを同一匿名通信路内で同時に行い匿名通信路の利用者が増えれば、匿名性は更に強まることになる。
【００３５】
【発明の効果】
第1の効果は、本発明により実現される匿名通信路の利用者は、サイズの大きなデータを匿名かつ安全に、効果的に送信できることにある。その理由は、利用者自身が信頼できる中継サーバ及び通信経路を自由に決定することができ、データの暗号化は高速処理が実現可能な共通鍵暗号を用い、かつ不正処理を行った場合は、不正者が特定されることから不正を困難としているためである。
第２の効果は、安全かつ大規模な匿名通信が可能であり、構成された匿名通信路内で複数イベントが同時並行できることにある。その理由は、中継サーバは第三者機関に登録さえすれば誰でも運営管理でき、匿名通信路の利用者は中継サーバの決定及び最終出力先を自由に決定でき、かつその中継サーバ管理者の不正は第三者機関により特定されるためである。
【図面の簡単な説明】
【図１】発明が適用されるシステムの構成を説明するための図。
【図２】この発明の第１実施形態における利用者の処理手順を説明するためのフロー図。
【図３】上記第１実施形態における最初の中継サーバの処理手順を説明するためのフロー図。
【図４】上記第１実施形態における利用者装置の構成を説明するためのブロック図。
【図５】上記第１実施形態における中継サーバの構成を説明するためのブロック図。
【図６】この発明の第２実施形態における第三者機関の処理手順を説明するためのフロー図。
【図７】上記第２実施形態における第三者機関の構成を説明するためのブロック図。
【図８】この発明の第４実施形態における利用者の処理手順を説明するためのフロー図。
【図９】上記第４実施形態における中継サーバの処理手順を説明するためのフロー図。
【図１０】この発明の第５実施形態における利用者の処理手順を説明するためのフロー図。
【図１１】上記第５実施形態における中継サーバの処理手順を説明するためのフロー図。
【図１】
0004146252.tif 000037
【図２】
0004146252.tif 000038
【図３】
0004146252.tif 000039
【図４】
0004146252.tif 000040
【図５】
0004146252.tif 000041
【図６】
0004146252.tif 000042
【図７】
0004146252.tif 000043
【図８】
0004146252.tif 000044
【図９】
0004146252.tif 000045
【図１０】
0004146252.tif 000046
【図１１】
0004146252.tif 000047