(57)【要約】【課題】利用者が指定した中継サーバの経路でデータを匿名通信により送信可能とし、かつ匿名通信経路においてデータの不正処理の検出を容易にする。【解決手段】各中継サーバＭｉは秘密情報（ａｉ，  ｂｉ）を分散して複数の第三者機関ＴＰｋに登録し、対応する情報（ｈｉ，  ｚｉ）を公開し、利用者Ｕｊは自分の秘密情報ｒｊにより鍵生成情報Ｇ０，ｊを生成し、選択した各サーバの公開情報（ｈｉ，  ｚｉ）を使用して匿名送信すべき平文ｍｓｇｊを順次多重暗号化し、得られた暗号Ｅ０，ｊを検証用データｕｉ，ｊと鍵生成情報Ｇ０，ｊとともに次の中継サーバに送信し、中継サーバは受信データＣｉ−１，ｊをその鍵生成情報から生成した検証鍵Ｚ’ｉ，ｊを使って検証し、検証で不正が発見された場合は第三者機関に報告し、第三者機関は協力して各サーバＭｉの受信データをその秘密情報（ａｉ，  ｂｉ）を使って検証して不正者を特定する。【選択図】図１
2004229105.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上において送信者から少なくとも１の中継サーバを介して受信者に匿名で情報データを送る匿名通信方法において、
（ａ）  各中継サーバは予め秘密情報を第三者機関に登録し、対応する公開情報を公開するステップと、
（ｂ）  送信者は匿名通信経路を形成する中継サーバを選択し、選択した中継サーバの公開情報を使って送信すべき情報データを指定宛先とともに暗号化し、得られた暗号データと鍵生成情報と検証用データを含む送信データを選択した最初の中継サーバに送信するステップと、
（ｃ）  選択された中継サーバは受信データをその受信データ中の鍵生成情報を使って生成した検証鍵により受信した検証用データを検証し、正しければ上記受信データ中の暗号データを復号処理して次の暗号データと次の検証用データと指定宛先を得て、上記鍵生成情報を自分の秘密情報で更新して復号した暗号データ及び検証用データとともに送信データとして復号した指定宛先に送信し、検証結果が正しくなければ上記第三者機関に報告するステップと、
（ｄ）  上記第三者機関は不正の報告を受けると、中継サーバの上記秘密情報を使って上記中継サーバの送信データを検証するステップ、
とを含むことを特徴とする匿名通信方法。
【請求項２】
請求項１に記載の匿名通信方法において、上記第三者機関は複数設けられ、上記ステップ（ａ）  において各上記中継サーバは上記秘密情報を秘密分散方によりそれぞれの第三者機関に分散しており、上記ステップ（ｄ）  において上記第三者機関の複数が協力して分散した上記秘密情報を復元して検証に用いることを特徴とする匿名通信方法。
【請求項３】
請求項１に記載の匿名通信方法において、上記利用者は複数存在し、上記ステップ（ｂ）において各上記利用者はそれぞれが任意に選択した中継サーバによりそれぞれの匿名通信経路を指定し、上記ステップ（ｃ）  において各上記中継サーバはその中継サーバを指定した全ての利用者から受信した受信データの順序に対し順序を入れ替えて上記送信データをそれぞれの指定宛先に送信することを特徴とする匿名通信方法。
【請求項４】
請求項１に記載の匿名通信方法において、上記ステップ（ｂ）  において上記利用者は上記鍵生成情報についての離散対数を知っていることをゼロ知識証明するステップを含むことを特徴とする匿名通信方法。
【請求項５】
請求項１に記載の匿名通信方法において、上記ステップ（ｃ）  は上記中継サーバが上記更新した鍵生成情報について離散対数を知っていることをゼロ知識証明するステップを含むことを特徴とする匿名通信方法。
【請求項６】
請求項１に記載の匿名通信方法において、上記ステップ（ｂ）  は上記選択した中継サーバの上記公開情報から共通秘密鍵を生成し、その共通秘密鍵により暗号化を行い、上記ステップ（ｃ）  において上記中継サーバは上記利用者から受信した鍵生成情報と自己の秘密情報から生成した共通秘密鍵により復号処理を行うことを特徴とする匿名通信方法。
【請求項７】
請求項１に記載の匿名通信方法において、上記ステップ（ｂ）  の暗号化処理は、それぞれの上記中継サーバの公開情報からそれぞれの中継サーバに対応する共通秘密鍵をそれぞれ生成し、選択した中継サーバの最も受信者に近い順に上記送信データと検証用データを指定宛先とともに多重暗号化することを特徴とする匿名通信方法。
【請求項８】
請求項１に記載の匿名通信方法において、上記ステップ（ｂ）  の暗号化処理は、それぞれの上記中継サーバの公開情報からそれぞれの中継サーバに対応する共通秘密鍵を生成し、対応する公開鍵で上記共通秘密鍵を暗号化し、暗号化共通秘密鍵を上記検証用データに含め、選択した中継サーバの最も受信者に近い順に上記送信データと検証用データを指定宛先とともに上記共通秘密鍵で多重暗号化し、上記ステップ（ｃ）  の復号処理は、上記受信データ中の暗号化共通秘密鍵を事故の秘密鍵で復号して共通秘密鍵を得て、その復号した共通秘密鍵を使って上記暗号データの復号を行うことを特徴とする匿名通信方法。
【請求項９】
請求項１に記載の匿名通信方法において、上記ステップ（ｄ）  は上記ゼロ知識証明を検証するステップを含むことを特徴とする匿名通信方法。
【請求項１０】
請求項１に記載の匿名通信方法において、上記受信者は公開掲示板として機能するサーバであり、（ｅ）  上記中継サーバから受信したデータを上記公開掲示板に公開するステップと、（ｆ）  上記第三者機関が上記公開掲示板上の受信データを検証し、正しければ復号処理を行ってその復号結果を上記公開掲示板に公開するステップ、とを更に含むことを特徴とする匿名通信方法。
【請求項１１】
請求項１に記載の匿名通信方法において、上記ステップ（ｂ）  は上記利用者が上記選択した中継サーバの公開鍵暗号方式の公開鍵により上記暗号化を行い、上記ステップ（ｃ）  は上記中継サーバが公開鍵暗号方式の秘密鍵により復号処理を行うことを特徴とする匿名通信方法。
【請求項１２】
請求項１乃至１１のいずれかに記載の匿名通信方法において、上記ステップ（ｄ）  は、上記第三者機関が検証により不正な中継サーバを検出した場合にその中継サーバに成り代わって処理を行うステップを含む。
【請求項１３】
送信者から受信者へ匿名通信経路を形成するための複数の中継サーバがネットワーク上に設けられ、少なくとも１つの第三者機関がネットワークに接続された匿名通信システムにおける利用者装置であり、
乱数を生成する乱数生成器と、
上記乱数により、べき乗演算を行って鍵生成情報を生成するべき乗演算部と、
匿名通信経路を形成する選択した中継サーバの公開情報を使ってその中継サーバに対応する共通秘密鍵を生成する鍵生成部と、
匿名通信により送信すべき情報データが入力される入力部と、
上記中継サーバに対する指定宛先と上記情報データを、上記共通秘密鍵を使って暗号化し、暗号データを生成する暗号化部と、
上記暗号データと上記鍵生成情報を結合して送信データを生成し、中継サーバに送信するデータ結合送信部、
とを含むことを特徴とする利用者装置。
【請求項１４】
送信者から受信者へ匿名通信経路を形成するための複数の中継サーバがネットワーク上に設けられ、少なくとも１つの第三者機関がネットワークに接続された匿名通信システムにおける利用者装置であり、
乱数を生成する乱数生成器と、
上記乱数により、べき乗演算を行って鍵生成情報を生成するべき乗演算部と、
匿名通信により送信すべき情報データが入力される入力部と、
上記中継サーバに対する指定宛先と上記情報データを、上記中継サーバの公開鍵を使って暗号化し、暗号データを生成する暗号化部と、
上記暗号データと上記鍵生成情報を結合して送信データを生成し、中継サーバに送信するデータ結合送信部、
とを含むことを特徴とする利用者装置。
【請求項１５】
請求項１３または１４に記載の利用者装置において、上記鍵生成情報についての離散対数を知っていることのゼロ知識証明を行うゼロ知識証明部が更に設けられていることを特徴とする利用者装置。
【請求項１６】
送信者から受信者へ匿名通信経路を形成するための複数の中継サーバがネットワーク上に設けられ、少なくとも１つの第三者機関がネットワークに接続された匿名通信システムにおける中継サーバであり、
乱数を秘密情報として生成する乱数生成器と、
上記秘密情報に対応し、上記第三者機関に登録するための公開情報を生成する公開情報生成部と、
上記秘密情報と受信データ中の鍵生成情報から生成した検証鍵を使って受信データを検証する検証部と、
上記秘密情報を使って上記受信データ中の鍵生成情報を更新するとともに、上記受信データ中の暗号データを復号して暗号データと検証用データと指定宛先を得る復号部と、
上記復号された暗号データと検証用データと上記更新された鍵生成情報を含む送信データを生成し、受信データの順序と入れ替えた順序で出力するデータ結合送信部、
とを含むことを特徴とする中継サーバ装置。
【請求項１７】
請求項１６に記載の中継サーバにおいて、上記復号部は、上記受信データ中の鍵生成情報と上記秘密情報を使って上記暗号データを復号するための共通秘密鍵を生成する鍵生成部が設けられていることを特徴とする中継サーバ装置。
【請求項１８】
請求項１６または１７に記載の中継サーバにおいて、上記更新された鍵生成情報についての離散対数を知っていることのゼロ知識証明を行うゼロ知識証明部が設けられていることを特徴とする中継サーバ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネットなどのオープンなネットワーク上で匿名通信路を構成する従来のソフトウェア技術に対して、匿名通信路の利用者及び匿名通信路内の不正処理を検出可能とすることで安全な匿名通信路を構成するための情報セキュリティ技術に関するものであり、特に、匿名通信システムに使用される匿名通信方法、利用者装置及び中継サーバ装置に関する。
【０００２】
【従来の技術】
従来の匿名通信路技術として例えば非特許文献１がある。これは、通信路に１以上のサーバを中継させ、そのサーバは暗号処理などを行うことで入力データをかく乱して出力することで送信者の匿名性を実現する、ｍｉｘ−ｎｅｔと呼ばれる匿名通信路技術の一実現方式である。上記非特許文献１の方式は、中継するサーバは不特定多数とでき、かつ利用者が自由に通信経路（中継するサーバ）を決定でき、更にサーバの処理量も小さくて済む特長を持つ。
また、非特許文献２では、ＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）と秘密分散法を利用した、匿名通信路の利用者や匿名通信路内での不正を防ぐことができる技術を提案している。
【０００３】
【非特許文献１】
千田、鬼頭、「拡張Ｈｙｂｒｉｄ  Ｍｉｘとその応用」、コンピュータセキュリティシンポジウム２００１（ＣＳＳ２００１）
【非特許文献２】
Ｊａｋｏｂｓｓｏｎ，  Ｊｕｅｌｓ，  ”Ａｎ  ｏｐｔｉｍａｌｌｙ  ｒｏｂｕｓｔ  ｈｙｂｒｉｄ  ｍｉｘ  ｎｅｔｗｏｒｋ，”  ＰＯＤＣ’０１
【非特許文献３】
「現代暗号」（岡本、山本）、産業図書、１９９７年、の２１７ぺ一ジ
【非特許文献４】
「暗号・ゼロ知識証明・数論」（岡本、太田）、共立出版、１９９５年
【非特許文献５】
Ｒ．Ｇｅｎｎａｒｏ，  Ｓ．Ｊａｒｅｃｋｉ，  Ｈ．Ｋｒａｗｃｚｙｋ，  ａｎｄ  Ｔ．Ｒａｂｉｎ，  ”Ｔｈｅ  （ｉｎ）ｓｅｃｕｒｉｔｙ  ｏｆ  ｄｉｓｔｒｉｂｕｔｅｄ  ｋｅｙ  ｇｅｎｅｒａｔｉｏｎ  ｉｎ  ｄｌｏｇ−ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ，”  ＥＵＲＯＣＲＹＰＴ’９９，  ＬＮＣＳ１５９２，  Ｓｐｒｉｂｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．２９５−３１０，  １９９９
【０００４】
【発明が解決しようとする課題】
非特許文献１の方式は、匿名通信路の利用者や匿名通信路内の不正に対しては考慮されていない。そのため、利用者の送信メッセージが正しく送信されない、不正者の追跡が困難、などの問題が起こりえる。
一方、非特許文献２の方式は、匿名通信路の利用者や匿名通信路内の不正を防ぐことはできるが、利用者が利用するサーバは予め決定され、かつその利用順序が一意に決定される。
ここで、それぞれの課題を相互補完するために、単純に非特許文献１の方式に非特許文献２の提案している不正を防ぐ技術を適用しようとした場合、以下の問題が生じる。
【０００５】
・非特許文献２の提案技術では、不正者の特定を行うフェーズにおいて、中継するサーバ管理者が協力する必要があるが、非特許文献１の方式では、中継するサーバは不特定多数とすることができることが特長の一つであり、その場合中継するサーバ管理者が協力することは一般に困難となる。
・非特許文献２の提案技術では、中継するサーバが出力するデータに対してゼロ知識証明と呼ばれる技術を用いて自身の処理正当性を保証させているが、非特許文献１の方式では、そのゼロ知識証明をそのまま適用することができない。
本発明の目的は、上記に挙げた問題点を解決し、利用者が自由に１つ以上の中継サーバを選択して匿名通信経路を決定でき、匿名通信路の利用者や匿名通信路内の不正を困難とする匿名通信方法及びそれを使用する利用者装置と中継サーバを提供することである。
【０００６】
【課題を解決するための手段】
この発明によれば、ネットワーク上において送信者から少なくとも１の中継サーバを介して受信者に匿名で情報データを送る匿名通信方法において、
（ａ）  各中継サーバは予め秘密情報を第三者機関に登録し、対応する公開情報を公開し、
（ｂ）  送信者は匿名通信経路を形成する中継サーバを選択し、選択した中継サーバの公開情報を使って送信すべき情報データを指定宛先とともに暗号化し、得られた暗号データと鍵生成情報と検証用データを含む送信データを選択した最初の中継サーバに送信し、
（ｃ）  選択された中継サーバは受信データをその受信データ中の鍵生成情報を使って生成した検証鍵により受信した検証用データを検証し、正しければ上記受信データ中の暗号データを復号処理して次の暗号データと次の検証用データと指定宛先を得て、上記鍵生成情報を自分の秘密情報で更新して復号した暗号データ及び検証用データとともに送信データとして復号された指定宛先に送信し、検証結果が正しくなければ上記第三者機関に報告し、
（ｄ）  上記第三者機関は不正の報告を受けると、中継サーバの上記秘密情報を使って上記中継サーバの送信データを検証する。
【０００７】
このように、各中継サーバの秘密情報を第三者機関に与えておき、秘密情報に対応する公開情報を公開しておくことにより、送信者は任意に選択した中継サーバによる通信経路を決定し、それらの中継サーバの公開情報を使って受信データの復号処理を行うことができる。また、不正の報告に対し、第三者機関は中継サーバの秘密情報を使って中継サーバの入出力データを検証でき、不正サーバに代わって匿名通信のための処理を行うこともできる。
【０００８】
【発明の実施の形態】
次に、本発明の実施の形態について詳細に説明する。まず第１の実施形態として、匿名通信路の利用者がある端末に匿名で安全にデータを送る方法を説明する。
次に第２の実施形態として、正しい中継サーバあるいは最終受信者が、自身の入力に対して不正があるとして第三者機関にそれを申し出た場合の、第三者機関による不正者特定方法を説明する。第３の実施形態では、匿名通信路の利用者により端末に送られたデータが、通信路内で改ざんされていないかどうかを第三者機関が検証できる方法を述べる。第４の実施態様では、共通鍵暗号方式の代わりに、公開鍵暗号方式を使用する例を説明する。最後に第５の実施形態で、本発明により実現可能となる匿名通信モデルについての一例を述べる。
なお全ての実施形態において、離散対数問題を拠り所とするような大きな素数ｐ、ｑ（ｑはｐ−１の約数となるような関係をもつ）及び位数がｑとなるような乗法群（Ｚ／ｐＺ）＊の元ｇがあらかじめ公開されているものとする。また、全ての送信情報は公開される、あるいは署名が付与されるなどで誰から誰に何が送信されたかを保証する手段がとられているものとする。
第１の実施形態
【０００９】
図１はこの発明が適用される通信システムの構成を示し、匿名対通信路を形成するための複数の中継サーバＭｉ（ｉ＝１，  ２，  …）がオープンなネットワークＮＷに接続されており、また、ネットワークＮＷには複数の利用者Ｕｊ（ｊ＝１，２，…）と１つ以上の第三者機関ＴＰ１，  ＴＰ２，  …，  ＴＰｍと受信者Ｒ１，  Ｒ２，  …が接続されているものとする。このとき、匿名通信路利用者Ｕｊと中継するサーバＭｉの不正を防ぐことを目的として、第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）が存在する。ここでＵｊの不正とは、自身の不正な入力を否認し、不正の所在を不明確にすることを意味し、Ｍｉの不正とは、自身への入力に対し不正な処理を施して出力することを意味する。
まず、Ｍｉが中継サーバとして登録する場合として以下を行う。
（Ａ）．乱数ａｉ、ｂｉを生成して公開情報
【数１】
2004229105.tif 000003
を計算し、（ｈｉ，  ｚｉ）を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報ａｉ、ｂｉをＴＰｋ  （ｋ＝１，２，…，ｍ）に分散して送る。
【００１０】
上記の処理で検証可能秘密分散法とは、ＴＰｋのうち何人かが協力しない限り秘密情報は復元されない秘密分散技術に加え、正しく秘密情報が分散されていることをＴＰｋが検証できる技術のことである。秘密情報の復元には閾値が設定され、例えば（ｍ’，ｍ）秘密分散とはｍ人のうち、ｍ’人以上が集まれば秘密情報を復元できるが、ｍ’人未満であれば秘密情報は全く得られない。即ち、ｍ人のうち少なくともｍ’人は正しいと仮定した場合に有効な方式となる（ｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅと呼ばれている）。これにより、中継サーバが不正な値を分散して送ることを防ぐことができる。また、検証可能秘密分散法として例えば、非特許文献３にその方法が示されている。ＴＰｋがＭｉを正しいと判断した場合、Ｍｉは中継サーバとしてＴＰｋから証明書が発行されるなどして承認される。ここで、（ｍ，  ｍ’）秘密分散であればｍ’人以上の第三者機関からの証明書があればよい。
次に匿名通信路利用者Ｕｊは以下に図２のフローを参照して説明する処理を行う。
Ｕｊの最終的な送信先である受信者を便宜上Ｍ３、そしてＭ３の公開情報を
【数２】
2004229105.tif 000004
とする（ａ３、ｂ３は乱数）。
（Ａ）．利用する中継サーバを決定する（ここでは、Ｍ１，  Ｍ２の順に利用するものとする）。
（Ｂ）．乱数ｒｊを生成して（ステップＳ１）鍵生成情報
【数３】
2004229105.tif 000005
を計算し（ステップＳ２）、更に次式
【数４】
2004229105.tif 000006
をｉ＝１，  ２，  ３について計算する（ステップＳ３〜Ｓ６）。ここでｗ０，ｊ＝１、Ｈ、Ｌ：一方向性ハッシュ関数、とする。
（Ｃ）．ｉ＝２，  １，  ０の順に暗号データＥｉ，ｊと検証用データｕｉ，ｊを次式
【数５】
2004229105.tif 000007
により計算し（ステップＳ７〜Ｓ１０）、Ｃ０，ｊ＝（Ｅ０，ｊ，  ｕ０，ｊ、Ｇ０，ｊ）をＭ１に送る（ステップＳ１１）。ここでＥＥＫｉ＋１，ｊは鍵Ｋｉ＋１，ｊを用いた共通鍵暗号の暗号化アルゴリズム、ＨＥＤＤｉ＋２はサーバＭｉ＋２のアドレス、ＨＥＤＤ４は空の値（即ち０ビット）、‖はデータの連結、ｕ３，ｊは空の値、Ｅ３，ｊは匿名送信すべき平文ｍｓｇｊ、Ｉはイベントごとに固有な値とする。式（６），（７）をｉ＝２，１，０と繰り返し実行することにより、受信者側に近い順に中継サーバに対する鍵で平文を多重暗号化することになる。なお、式（７）  はハッシュ関数でなく、鍵をＺｉ＋１，ｊとしたＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）関数と置き換えても良い。
（Ｄ）．ｇを底としたＧ０，ｊの離散対数を知っていること、即ち式（１）  の秘密情報ｒｊを知っていることをゼロ知識証明する（ステップＳ１２）。
【００１１】
上記のゼロ知識証明については、例えば非特許文献４に紹介されており、ここではゼロ知識証明の具体的なアルゴリズムの説明は省略する。また、ゼロ知識証明を検証するのは、Ｍ１、第三者機関、あるいはその他の機関のいずれが行っても良い。そしてこの検証をはじめに行い、不正と判断された場合は即座にＵｊを除外する。
次に最初の中継サーバＭ１による処理を図３を参照して説明する。サーバＭ１はＣ０，ｊ＝（Ｅ０，ｊ，  ｕ０，ｊ，  Ｇ０，ｊ），  ｊ＝１，  ２，  …，  ｎを受け取り（ステップＳ１）、以下の処理を行う。なおここではＭ１はｎ個のデータＣ０，ｊ，（ｊ＝１，  ２，  …，  ｎ）を受け取り、処理後のｎ個のデータＣ１，ｊを全てＭ２へ送るものとする。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数６】
2004229105.tif 000008
を計算し（ステップＳ２，Ｓ３）、ｕ０，ｊ＝ｕ’０，ｊが成り立つことを確認する（ステップＳ４）。即ち、鍵生成情報Ｇ０，ｊから式（８）により検証鍵Ｚ’１，ｊを生成し、その検証鍵を使って式（９）により生成した値が受信データＣ０，ｊ中の検証用データｕ０，ｊと一致すれば受信データＣ０，ｊは正しいと判定する。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数７】
2004229105.tif 000009
により暗号データＥ０，ｊを復号処理して次の中継サーバのアドレスＨＥＤＤ２、暗号データＥ１，ｊ、検証用データｕ１，ｊを得る（ステップＳ６）。ここでＤＤＫ１，ｊは鍵Ｋ１，ｊを用いた共通鍵暗号の復号アルゴリズムとする。
（Ｃ）．ｊの順序を適当に入れ替えてＣ１，ｊ＝（Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）を式（１３）の復号結果中のアドレスＨＥＤＤ２により指定されたサーバＭ２に送る（ステップＳ７）。
（Ｄ）．式（１２）におけるＧ０，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）の積
【数８】
2004229105.tif 000010
の離散対数を知っている、即ちｊ＝１，  ２，  …，  ｎについてＬ（Ｔ１，ｊ）を知っていることをゼロ知識証明する（ステップＳ８）。
ステップＳ４でｕ０，ｊとｕ’０，ｊが一致しなかった場合は、第三者機関ＴＰｋに不正の検出を報告する（ステップＳ９）。
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれｎ個のＭ１の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、Ｍ１以外に対してはＵｊの匿名性が満たされたことになる。なお離散対数を知っていることをゼロ知識証明するアルゴリズムは公知の技術であるため省略するが、このゼロ知識証明が行われないと、Ｍ１は適当な出力をＭ２に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことなので説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、サーバＭ２、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００１２】
次にＣ１，ｊ＝（Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）を受け取ったＭ２は以下を行う。以下の式（１４）〜（１９）で示す処理手順は、式（８）〜（１３）と対応しており、図３の場合と基本的に同様なので、サーバＭ２としての処理手順の図は示さない。なおここではｎ個のデータ（ｊ＝１，  ２，  …，  ｎ）を受け取り、Ｍ２は全てＭ３へ送るものとする。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数９】
2004229105.tif 000011
を計算し、ｕ１，ｊ＝ｕ’１，ｊが成り立つことを確認する。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数１０】
2004229105.tif 000012
を計算する
（Ｃ）．ｊの順序を適当に入れ替えてＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）をＨＥＤＤ３に従ってＭ３に送る。
（Ｄ）．Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ２，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐ２の離散対数を知っている、即ち、式（１８）におけるｊ＝１，  ２，  …，  ｎについてのＬ（Ｔ２，ｊ）を知っていることをゼロ知識証明する。
【００１３】
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれＭ２のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはＭ１とＭ２が結託しない限りは全てのものに対してＵｊの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
最後にＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）を受け取ったＭ３は以下を行う。サーバＭ３の処理もＭ１，  Ｍ２の処理における式（１２），  （１８）に対応する処理を行わない点を除いてＭ１，  Ｍ２の処理とほとんど同じである。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数１１】
2004229105.tif 000013
を計算し、ｕ２，ｊ＝ｕ’２，ｊが成り立つことを確認する。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数１２】
2004229105.tif 000014
を計算する。
これにより、Ｍ３はｍｓｇｊを匿名で受け取ることになり、Ｕｊの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバＭｉの不正あるいは匿名通信路の利用者Ｕｊの不正入力も、正しい検証者（他の中継サーバ管理者、最終受信者、第三者機関）によって検出される。
【００１４】
図４は上記第１実施形態における利用者Ｕｊの装置（利用者装置と呼ぶ）の処理機能構成を示す。利用者装置は公開された情報ｈｉ，ｚｉ，ｇを格納する記憶部１１と、乱数ｒｊを生成する乱数生成器１２と、式（１）  二より鍵生成情報を計算するべき乗演算部１３と、ゼロ知識証明部１４と、データ結合送信部１５と、入力部１６と、鍵生成部２０と、暗号化部３０とから構成されている。
鍵生成部２０は式（２）  を計算するべき乗演算部２１と、式（３）  を演算する共通鍵計算部２２と、式（４）  を計算するハッシュ部２３と、前回のハッシュ結果ｗｉ−１，ｊを保持しているレジスタ２４と、式（５）  を計算するべき乗演算部２５とから構成され、ｉ＝１，  ２，  ３について順次演算を実行する。暗号化部３０は、サーバＭｉ＋１のアドレスＨＥＤＤｉ＋１と前回の暗号化結果Ｅｉ＋１，ｊと、前回のハッシュ結果ｕｉ＋１，ｊを保持するレジスタ３１と、式（６）  による暗号化を行う暗号演算部３２と、式（７）  のハッシュ演算を行うハッシュ部３３とから構成されており、Ｅｉ＋１，ｊの初期値Ｅ３，ｊとして入力部１６から匿名送信されるべき平文ｍｓｇｊが入力され、ｉ＝２，  １，  ０の順に演算を繰り返すことによりＥ０，ｊとｕ０，ｊが求まる。これらとＧ０，ｊとがデータ結合送信部１５で結合され、暗号データＣ０，ｊとしてサーバＭ１へ送信される。
【００１５】
図５は、中継サーバＭ１の機能構成を示す。サーバＭ１は値ｇ、秘密情報ａ１，  ｂ１を格納する記憶部４１と、上記秘密情報としての乱数ａ１，  ｂ１を生成する乱数生成器４２と、べき乗部４３と、検証部５０と、復号部６０と、データ結合送信部４４と、ゼロ知識証明部４５とから構成されている。
検証部５０は受信したデータＣ０，ｊから式（８），  （９）又は式（１４），  （１５）により検証鍵Ｚ’１，ｊを演算する検証鍵演算部５１と、ハッシュ部５２と、ｕ０，ｊとｕ’０，ｊが一致するか比較判定する比較部５３とから構成されている。
復号部６０は、式（１０）の計算を行うべき乗部６１と、そのべき乗演算結果を使って式（１１）により共通秘密鍵Ｋ１，ｊを生成する鍵生成部６２と、式（１２）により更新された鍵生成情報Ｇ１，ｊを計算するべき乗部６３と、受信データＣ０，ｊ中の暗号データＥ０，ｊを共通秘密鍵Ｋ１，ｊにより復号し、次にデータＣ１，ｊの送信先サーバＭ２のアドレスＨＥＤＤ２と暗号データＥ１，ｊと検証用データｕ１，ｊを得る復号処理部６４とから構成されている。
上記第１実施形態の利用者Ｕｊの処理を示す図２において、ステップＳ１２はゼロ知識証明を行うので利用者ＵｊからサーバＭ１への送信データＣ０，ｊに不正があった場合には、ゼロ知識証明の検証により容易に不正を検出できる。従って、図３における第１の中継サーバＭ１の処理ステップＳ２，Ｓ３，Ｓ４による検証鍵Ｚ’１，ｊを使った検証は省略し、ゼロ知識証明の検証を行ってもよい。その場合は、図５における検証部５０を省略できる。
【００１６】
第２の実施形態
次に第２の実施形態について説明する。ここでは、正しい中継サーバあるいは最終受信者が、自身の入力に対して不正があるとして第三者機関にそれを申し出た場合の、第三者機関による不正者特定方法を述べる。なお記号などについては第１の実施形態に従うものとする。
第１の実施形態で、Ｍｉ（ｉ＝０，  １，  ２）は、Ｚ’ｉ，ｊ＝Ｇｉ−１，ｊｂｉ及びｕ’ｉ−１，ｊ≡Ｈ（Ｚ’ｉ，ｊ‖ＨＥＤＤｉ＋１‖Ｅｉ−１，ｊ‖Ｉ）を計算し（例えば図３のステップＳ２，Ｓ３）、ｕｉ−１，ｊ＝ｕ’ｉ−１，ｊが成り立つことを確認する処理があるが、ここでは、それが成り立たないｊがあった場合に、Ｍｉはそのことを第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）に報告した場合に（ステップＳ９）、ＴＰｋが不正者を特定する手順を説明する。なお、第三者機関は半数以上が正しければ、Ｍｉの秘密情報ａｉ、ｂｉを用いた計算の復元が可能となる方式を用いるものとし、第三者機関の例えば半数以上は正しいと仮定する。この方式はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅとよばれ、例えば非特許文献５などに示されている。第三者機関がＭｉによって分散された秘密情報を用いて以下を行う処理手順を図６を参照して説明する。
【数１３】
2004229105.tif 000015
を計算し（ステップＳ１，Ｓ２）、ｕｉ−１，ｊとｕ’ｉ−１，ｊが一致し、かつＭｉ−１による、Ｇｉ−２，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇｉ−１，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐｉ−１の離散対数を知っていることのゼロ知識証明が正しいかを判定し（ステップＳ３）、正しいことが検証されれば、即ち、Ｍｉ−１が不正を行っていなければＭｉを不正サーバとして除外し、第三者機関はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅにより、Ｍｉの処理を代理する（ステップＳ４）。ｕ’ｉ−１，ｊ≠ｕｉ−１，ｊであった場合はＭｉより前のサーバが不正を行ったと判定し、以下の処理を行う。
（Ｂ）．ｉ＝１であれば（ステップＳ５の判定）、利用者Ｕｊが不正を行ったと判定し、利用者Ｕｊを排除し、Ｃ０，ｊを除去する（ステップＳ６）。
【００１７】
ｉ≠１であれば、以下の処理を行う。
（Ｃ）．サーバＭｉ−１にデータＣｉ−１，ｊと対応したデータＣｉ−２，ｊ’の公開を要求する、あるいは単にｊ’の公開を要求する（ステップＳ７）。
（Ｄ）．Ｃｉ−２，ｊ’からＣｉ−１，ｊを計算し（ステップＳ８）、Ｍｉ−１の公開情報と一致しなければ（ステップＳ９の判定）、Ｍｉ−１を不正サーバとして除外し、第三者機関はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅにより、Ｍｉ−１の処理を代理する（ステップＳ１０）。
（Ｅ）．Ｚ’ｉ−１，ｊ’とｕ’ｉ−２，ｊ’≡Ｈ（Ｚ’ｉ−１，ｊ‖ＨＥＤＤｉ‖Ｅｉ−２，ｊ’‖Ｉ）を計算し（ステップＳ１１）、ｕｉ−２，ｊ’＝ｕ’ｉ−２，ｊ’が成り立たなければ（ステップＳ１２の判定）、Ｍｉ−１を不正サーバとして除外し、第三者機関はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅにより、Ｍｉ−１の処理を代理する（ステップＳ１３）。
（Ｆ）．ステップＳ１２でｕｉ−２，ｊとｕ’ｉ−２，ｊ’が一致した場合、入力データＣｉ−１，ｊを不正な入力データと判定し、即ち、Ｍｉ−１より前のサーバまたは利用者に不正があると判定し、ｉ←ｉ−１、ｊ←ｊ’として（ステップＳ１４）、ステップＳ１の処理に戻る。
以上の操作を不正者が発見されるまでｉを１ずつ減算して繰り返すことにより不正者を特定することができる。
【００１８】
図７は上記第２実施形態における第三者機関の機能構成を示す。図６の処理手順の説明から理解されるように、第三者機関の処理は不正サーバの検出を除けばサーバと同様の処理を行っており、従って、図５に示したサーバ装置の構成とほとんど同じであるが、図６のステップＳ１０の比較を行う比較判定部７３が設けられ、ステップＳ８で要求したデータＣｉ−２，ｊ’から復号生成したデータＣｉ−１，ｊ’と受信したデータＣｉ−１，ｊが一致するか判定する。図６のステップＳ９の処理は、要求したデータＣｉ−２，ｊ’＝（Ｅｉ−２，ｊ’，  ｕｉ−２，ｊ’，  Ｇｉ−２，ｊ’）を復号部９０に入力して復号処理を行うことにより結合部７２に得られる。その他の構成の説明は省略する。
第３の実施形態
ここでは第３の実施形態として、匿名通信路の受信者は公開掲示板として機能するサーバの場合であり、利用者から送られたデータを公開する場合の構成と処理を説明する。前述の第１及び第２実施形態で説明した匿名通信では、最後の中継サーバが例えば図３のステップＳ６で復号処理を行い、例えば復号結果Ｅ３，ｊ＝ｍｓｇｊが得られ、これを受信者に送る。この最後の中継サーバが第３の実施形態に使用された場合、公開掲示板機能を果たす最終サーバはデータＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）を自分で復号処理して平文ｍｓｇｊを公開する。もしそのサーバが不正に異なる平文ｍｓｇ’ｊを公開しても発見されない恐れがある。そこでこの第３実施形態においては、公開掲示板としてのサーバは復号機能を有さず、代わりに第三者機関が復号処理を行い、復号結果を掲示板に公開する。以下の説明における記号などについては第１の実施形態に従うものとする。
【００１９】
まずＴＰｋ（ｋ＝１，  ２，  …，  ｍ）は以下を行う。
（Ａ）．乱数ｕｋ、ｖｋを生成して
【数１４】
2004229105.tif 000016
を計算し、（ｘｋ，  ｙｋ）を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報ｕｋ、ｖｋをＴＰｔ（ｔ≠ｋ）に分散して送る。
以降用いる記号として、Ｘをｘｋ（ｋ＝１，  ２，  …，  ｍ）の積、Ｙをｙｋ（ｋ＝１，  ２，  …，  ｍ）の積とする。また、第三者機関は誰もが閲覧可能な公開掲示板を提供するサーバを利用し、そこにＸ，Ｙが公開されているものとする。なおここでは簡単のため便宜上、
【数１５】
2004229105.tif 000017
即ち、
ａ３＝ｕ１＋ｕ２＋…＋ｕｍ                          （３１）
ｂ３＝ｖ１＋ｖ２＋…＋ｖｍ                          （３２）
とし、その公開掲示板を提供するサーバをＭ３とする。
一方、Ｍｉが中継サーバとして登録する場合は以下を行う。
（Ａ）．乱数ａｉ、ｂｉを生成して
【数１６】
2004229105.tif 000018
を計算し、（ｈｉ，  ｚｉ）を公開する。
（Ｂ）．検証可能秘密分散法を用いて秘密情報ａｉ、ｂｉをＴＰｋに分散して送る。
ＴＰｋがＭｉを正しいと判断した場合、Ｍｉは中継サーバとしてＴＰｋに証明書が発行されるなどして承認される。
【００２０】
次に匿名通信路利用者Ｕｊは以下を行う。Ｕｊの最終的な送信先を公開掲示板を提供するサーバＭ３とし、Ｕｊによる平文ｍｓｇｊは第三者機関によって復号され、その公開掲示板に公開されるものとする。
利用者Ｕｊの処理及び中継サーバＭ１，Ｍ２の処理は第１実施形態の場合と同様なので説明を省略する。
掲示板サーバＭ３は中継サーバＭ２からデータＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）を受信するとそれを掲示板に公開する。第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）は、まず掲示板のデータＣ２，ｊが通信路内で改ざんされていないかどうかを検証するため、ｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅを用いて以下を行う。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数１７】
2004229105.tif 000019
を計算し、ｕ２，ｊ＝ｕ’２，ｊが成り立つことを確認する。もし成り立たない場合は、第２の実施形態で示した不正者特定処理を行う。その処理方法は既に示してあるため省略する。
ここでは上記処理（Ａ）が正しいとして、次の処理を説明する。第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅを用いて以下を行う。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、復号処理を
【数１８】
2004229105.tif 000020
の計算により行う。これにより得られた復号平文ｍｓｇｊは秘密情報を除く他の中間データとともにすべて掲示板に公開する。従って、掲示板サーバＭ３はｍｓｇｊを匿名で受け取ることになり、Ｕｊの匿名性が確保される。また、中継サーバＭｉの不正あるいは匿名通信路の利用者Ｕｊの不正入力も、第三者機関によって検出される。
第４の実施形態
ここでは、第１の実施形態において暗号化及び復号化処理が共通秘密鍵方式により行われる例を示したが、公開鍵暗号方式によって行われる場合について以下に説明する。
【００２１】
中継するサーバＭｉ（ｉ＝１，  ２，  …）がオープンなネットワークに多数つながっているものとする。このとき、匿名通信路利用者と中継するサーバＭｉの不正を防ぐことを目的として、第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）が存在する。また、中継するサーバＭｉ（ｉ＝１，  ２，  …）が利用する公開鍵暗号アルゴリズムは統一され、公開されているものとする。
まず、Ｍｉが中継サーバとして登録する場合として以下を行う。
（Ａ）．公開鍵暗号アルゴリズムの公開鍵と秘密鍵のペア（ＰＫｉ，  ＳＫｉ）を生成する。
（Ｂ）．乱数ｂｉを生成し、
【数１９】
2004229105.tif 000021
を計算する。
（Ｃ）．ＰＫｉ，  ｚｉを公開する。
（Ｄ）．検証可能秘密分散法を用いて秘密情報ＳＫｉ，  ｂｉをＴＰｋに分散して送る。
【００２２】
次に匿名通信路利用者Ｕｊの処理手順を図８を参照して説明する。Ｕｊの最終的な送信先である受信者を便宜上Ｍ３、そしてＭ３の公開情報をＰＫ３，  ｚ３＝ｇｂ３とする。ＰＫ３はＵｊの秘密鍵ＳＫ３に対応する公開鍵、ｂ３は乱数である。
（Ａ）．利用する中継サーバを決定する（ここでは、Ｍ１，  Ｍ２の順に利用するものとする）。
（Ｂ）．乱数ｒｊを生成し（ステップＳ１）、
【数２０】
2004229105.tif 000022
を計算する（ステップＳ３〜Ｓ６）。ここでｗ０，ｊ＝１、Ｌ：一方向性ハッシュ関数、とする。
（Ｃ）．ｉ＝２，  １，  ０の順に
【数２１】
2004229105.tif 000023
を計算し（ステップＳ７〜Ｓ１０）、Ｃ０，ｊ＝（Ｅ０，ｊ，  ｕ０，ｊ、Ｇ０，ｊ）をＭ１に送る（ステップＳ１１）。ここでＰＥＰＫｉ＋１は鍵ＰＫｉ＋１を用いた公開鍵暗号の暗号化関数、ＨＥＤＤｉ＋２はＭｉ＋２を示すアドレス、ＨＥＤＤ４は空の値、‖はデータの連結、ｕ３，ｊは空の値、Ｅ３，ｊは平文ｍｓｇｊ、Ｉはイベントごとに固有な値とする。なお、式（４５）はハッシュ関数でなく、鍵をＺｉ＋１，ｊとしたＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）関数と置き換えても良い。また、Ｉ，  ｕ０，ｊは省略してもよい。
（Ｄ）．ｇを底としたＧ０，ｊの離散対数を知っていることをゼロ知識証明する（ステップＳ１２）。
上記のゼロ知識証明を検証するのは、Ｍ１、  第三者機関、あるいはその他の機関のいずれが行ってもよい。その検証を初めに行い、不正と判断された場合は即座にＵｊを除外する。
【００２３】
次にサーバＭ１の処理手順を図９を参照して説明する。ステップＳ１でＣ０，ｊ＝（Ｅ０，ｊ，  ｕ０，ｊ，  Ｇ０，ｊ）を受け取ったＭ１は以下を行う。なおここではＭ１は受信したｎ個のデータＣ０，ｊ（ｊ＝１，  ２，  …，  ｎ）を復号処理し、全てＭ２へ送るものとする。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数２２】
2004229105.tif 000024
を計算し（ステップＳ２，Ｓ３）、ｕ０，ｊ＝ｕ’０，ｊが成り立つことを確認する（ステップＳ４）。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数２３】
2004229105.tif 000025
を計算する（ステップＳ５，Ｓ６）。ここでＰＤＳＫ１は鍵ＳＫ１を用いた公開鍵暗号の復号関数とする。
（Ｃ）．ｊの順序を適当に入れ替えてＣ１，ｊ＝（Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）をＨＥＤＤ２に従ってＭ２に送る（ステップＳ７）。
（Ｄ）．Ｇ０，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐ１の離散対数を知っている、即ちｊ＝１，  ２，  …，  ｎについてＬ（Ｚ１，ｊ）を知っていることをゼロ知識証明する（ステップＳ８）。
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれｎ個のＭ１の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、Ｍ１以外に対してはＵｊの匿名性が満たされたことになる。ゼロ知識証明が行われないと、Ｍ１は適当な出力をＭ２に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことから説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、Ｍ２、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００２４】
次にＣ１，ｊ＝（Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）を受け取ったＭ２は以下の処理を行う。この処理は符号の添え字が異なっても基本的に図９に示したＭ１の処理と同様である。なおここではＭ２は受信したｎ個のデータＣ１，ｊ（ｊ＝１，  ２，  …，  ｎ）を復号処理して全てＭ３へ送るものとする。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数２４】
2004229105.tif 000026
を計算し（ステップＳ２，Ｓ３）、ｕ１，ｊ＝ｕ’１，ｊが成り立つことを確認する（ステップＳ４）。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数２５】
2004229105.tif 000027
を計算する（ステップＳ５，Ｓ６）。
（Ｃ）．ｊの順序を適当に入れ替えてＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）をＨＥＤＤ３に従ってＭ３に送る（ステップＳ７）。
（Ｄ）．Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ２，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐ２の離散対数を知っている、即ちｊ＝１，  ２，  …，  ｎについてＬ（Ｚ２，ｊ）を知っていることをゼロ知識証明する（ステップＳ８）。
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれＭ１のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはＭ１とＭ２が結託しない限りは、全てのものに対してＵｊの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
【００２５】
最後にＣ２，ｊ＝（Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）を受け取ったＭ３は以下を行う。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数２６】
2004229105.tif 000028
を計算し、ｕ２，ｊ＝ｕ’２，ｊが成り立つことを確認する。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、ＰＤＳＫ３（Ｅ２，ｊ）＝ｍｓｇｊを計算する。
これにより、Ｍ３はｍｓｇｊを匿名で受け取ることになり、Ｕｊの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバＭｉの不正あるいは匿名通信路の利用者Ｕｊの不正入力も、正しい検証者（他の中継サーバ管理者、最終受信者、第三者機関）によって検出される。しかし、その方法は第２実施形態から明らかなので、省略する。
【００２６】
第５の実施形態
第１の実施形態においては暗号化及び復号化処理が共通秘密鍵方式により行われる例を、第４実施形態においては暗号化及び復号化処理が公開鍵暗号方式によって行われる例を示したが、共通秘密鍵の暗号化及び復号化処理は公開鍵暗号方式で行い、その他の情報は共通秘密鍵方式によって行われる場合について以下に説明する。
中継するサーバＭｉ（ｉ＝１，  ２，  …）がオープンなネットワークに多数つながっているものとする。このとき、匿名通信路利用者と中継するサーバＭｉの不正を防ぐことを目的として、第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）が存在する。また、中継するサーバＭｉ（ｉ＝１，  ２，  …）が利用する公開鍵暗号アルゴリズムは統一され、公開されているものとする。
【００２７】
まず、Ｍｉが中継サーバとして登録する場合として以下を行う。
（Ａ）．公開鍵暗号アルゴリズムの公開鍵と秘密鍵のペア（ＰＫｉ，  ＳＫｉ）を生成する。
（Ｂ）．乱数ｂｉを生成し、
【数２７】
2004229105.tif 000029
を計算する。
（Ｃ）．検証可能秘密分散法を用いて秘密情報ＳＫｉ，  ｂｉをＴＰｋに分散して送る。
【００２８】
次に匿名通信路利用者Ｕｊの処理手順を図１０を参照して説明する。Ｕｊの最終的な送信先である受信者を便宜上Ｍ３、そしてＭ３の公開情報をＰＫ３，  ｚ３＝ｇｂ３とする。ＰＫ３はＵｊの秘密鍵ＳＫ３に対応する公開鍵、ｂ３は乱数である。
（Ａ）．利用する中継サーバを決定する（ここでは、Ｍ１，  Ｍ２の順に利用するものとする）。
（Ｂ）．乱数ｒｊを生成し（ステップＳ１）、
【数２８】
2004229105.tif 000030
を計算する（ステップＳ３〜Ｓ６）。ここでｗ０，ｊ＝１、Ｌ：一方向性ハッシュ関数、とする。
（Ｃ）．公開された共通鍵暗号アルゴリズムＥＥで用いるＭ１，  Ｍ２，  Ｍ３との共通秘密鍵Ｋ１，ｊ，  Ｋ２，ｊ，  Ｋ３，ｊ  をランダムに決定する。
（Ｄ）．ｉ＝２，  １，  ０の順に
【数２９】
2004229105.tif 000031
を計算し（ステップＳ７〜Ｓ１０）、Ｃ０，ｊ＝（ＫＫ０，ｊ，  Ｅ０，ｊ，  ｕ０，ｊ、Ｇ０，ｊ）をＭ１に送る（ステップＳ１１）。ここでＰＥＰＫｉ＋１は鍵ＰＫｉ＋１を用いた公開鍵暗号の暗号化関数、ＫＫ３，ｊは空の値、ＨＥＤＤｉ＋２はＭｉ＋２を示すアドレス、ＨＥＤＤ４は空の値、‖はデータの連結、ｕ３，ｊは空の値、Ｅ３，ｊは平文ｍｓｇｊ、Ｉはイベントごとに固有な値とする。なお、式（６２）はハッシュ関数でなく、鍵をＺｉ＋１，ｊとしたＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）関数と置き換えても良い。また、Ｉ，  ｕ０，ｊは省略してもよい。
（Ｅ）．ｇを底としたＧ０，ｊの離散対数を知っていることをゼロ知識証明する（ステップＳ１２）。
上記のゼロ知識証明を検証するのは、Ｍ１、  第三者機関、あるいはその他の機関のいずれが行ってもよい。その検証を初めに行い、不正と判断された場合は即座にＵｊを除外する。
【００２９】
次にサーバＭ１の処理手順を図１１を参照して説明する。ステップＳ１でＣ０，ｊ＝（ＫＫ０，ｊ，  Ｅ０，ｊ，  ｕ０，ｊ，  Ｇ０，ｊ）を受け取ったＭ１は以下を行う。なおここではＭ１は受信したｎ個のデータＣ０，ｊ（ｊ＝１，  ２，  …，  ｎ）を復号処理し、全てＭ２へ送るものとする。（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数３０】
2004229105.tif 000032
を計算し（ステップＳ２，Ｓ３）、ｕ０，ｊ＝ｕ’０，ｊが成り立つことを確認する（ステップＳ４）。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数３１】
2004229105.tif 000033
を計算する（ステップＳ５，Ｓ６）。ここでＰＤＳＫ１は鍵ＳＫ１を用いた公開鍵暗号の復号関数とする。
（Ｃ）．ｊの順序を適当に入れ替えてＣ１，ｊ＝（ＫＫ１，ｊ，  Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）をＨＥＤＤ２に従ってＭ２に送る（ステップＳ７）。
（Ｄ）．Ｇ０，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐ１の離散対数を知っている、即ちｊ＝１，  ２，  …，  ｎについてＬ（Ｚ１，ｊ）を知っていることをゼロ知識証明する（ステップＳ８）。
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれｎ個のＭ１の入出力の対応関係をかく乱することができる。従ってこの時点で、半数以上の第三者機関が結託しなければ、Ｍ１以外に対してはＵｊの匿名性が満たされたことになる。ゼロ知識証明が行われないと、Ｍ１は適当な出力をＭ２に渡し、その不正は検出されないことが容易に可能となる。但しそのことは明らかなことから説明は省略する。即ちこのゼロ知識証明部分が、中継サーバ管理者の不正を防ぐ技術となり、本発明の主要な技術でもある。また、このゼロ知識証明を検証するのは、Ｍ２、第三者機関、あるいはその他の機関のいずれが行っても良い。
【００３０】
次にＣ１，ｊ＝（ＫＫ１，ｊ，  Ｅ１，ｊ，  ｕ１，ｊ，  Ｇ１，ｊ）を受け取ったＭ２は以下の処理を行う。この処理は符号の添え字が異なっても基本的に図１１に示したＭ１の処理と同様なので、図１１を参照されたい。なおここではＭ２は受信したｎ個のデータＣ１，ｊ（ｊ＝１，  ２，  …，  ｎ）を復号処理して全てＭ３へ送るものとする。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数３２】
2004229105.tif 000034
を計算し（ステップＳ２，Ｓ３）、ｕ１，ｊ＝ｕ’１，ｊが成り立つことを確認する（ステップＳ４）。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数３３】
2004229105.tif 000035
を計算する（ステップＳ５，Ｓ６）。
（Ｃ）．ｊの順序を適当に入れ替えてＣ２，ｊ＝（ＫＫ２，ｊ，  Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）をＨＥＤＤ３に従ってＭ３に送る（ステップＳ７）。
（Ｄ）．Ｇ１，ｊ（ｊ＝１，  ２，  …，  ｎ）を底とした、Ｇ２，ｊ（ｊ＝１，  ２，  …，  ｎ）の積Ｐ２の離散対数を知っている、即ちｊ＝１，  ２，  …，  ｎについてＬ（Ｚ２，ｊ）を知っていることをゼロ知識証明する（ステップＳ８）。
ｊの順序を適当に入れ替え、かつ暗号処理を施しデータを変換したことで、それぞれＭ１のｎ個の入出力の対応関係をかく乱することができる。従って、半数以上の第三者機関、またはＭ１とＭ２が結託しない限りは、全てのものに対してＵｊの匿名性が満たされたことになる。ゼロ知識の証明及び検証についての説明は前述同様のため省略する。
【００３１】
最後にＣ２，ｊ＝（ＫＫ２，ｊ，  Ｅ２，ｊ，  ｕ２，ｊ，  Ｇ２，ｊ）を受け取ったＭ３は以下を行う。
（Ａ）．ｊ＝１，  ２，  …，  ｎについて、
【数３４】
2004229105.tif 000036
を計算し、ｕ２，ｊ＝ｕ’２，ｊが成り立つことを確認する。
（Ｂ）．ｊ＝１，  ２，  …，  ｎについて、
【数３５】
2004229105.tif 000037
を計算する。
これにより、Ｍ３はｍｓｇｊを匿名で受け取ることになり、Ｕｊの匿名性が確保される。また、第２の実施形態で述べるが、中継サーバＭｉの不正あるいは匿名通信路の利用者Ｕｊの不正入力も、正しい検証者（他の中継サーバ管理者、最終受信者、第三者機関）によって検出される。しかし、その方法は第２実施形態から明らかなので、省略する。
【００３２】
第６の実施形態
最後に第６の実施形態として、本発明により実現可能となる匿名通信モデルの例について図１を参照して述べる。
まずインターネットなどオープンなネットワークＮＷ上に中継サーバとしてＭｉ（ｉ＝１，  ２，  …）が不特定多数存在し、送信者としての各利用者Ｕｊは任意の１つ以上の中継サーバを選択指定することにより匿名通信路１０を構成する。図１では送信者Ｕｊと受信者Ｒｆ間に中継サーバＭ１，  Ｍ２，  Ｍ３を介した匿名通信経路１０を形成した例を示している。例えば中継サーバＭｉは匿名通信路を商用利用するような業者から料金を徴収するようなアプリケーションサービスプロバイダなどである。そして匿名通信路を利用する側として、不特定多数の送信者Ｕｊ（ｊ＝１，  ２，  …）及び受信者Ｒｆ（ｆ＝１，  ２，  …）が存在する。また匿名通信路内の不正、即ちＭｉの不正を防ぐ目的で、ある一定数の第三者機関ＴＰｋ（ｋ＝１，  ２，  …，  ｍ）が存在する。
【００３３】
第三者機関ＴＰｋは、Ｍｉあるいは受信者Ｒｆが不正入力を検出した場合に、それに対応し、第２の実施形態で示したように不正者を特定することができる。また受信者Ｒｆが受信結果を提示するような場合、その結果の正当性を第三者機関ＴＰｋが保証することができる。これについては第３の実施形態で示している。
受信者Ｒｆとして、例えば電子投票の投票所が挙げられる。この場合、送信者Ｕｊは投票者となり、自身の匿名性を守るために信頼できる経路及びＭｉを自身で選択することができる。またデータは暗号化されていることから、投票の秘密も保持される。データＣｉ−１，ｊを受け取ったＭｉは、ある程度の数のデータを受け取ったら、第１の実施形態で示したような手順で暗号処理及び出力順序の置換を施し、ＨＥＤＤで指定された送信者Ｕｊの意図したアドレスヘデータを送信する。これをいくつかのＭｉが繰り返すことにより匿名性の信頼度が増していく。ただし、送信時間を優先するならば、送信者Ｕｊはデータに時間を指定しておくことで、即座にＭｉはデータを出力することも可能である。ただしこの場合置換による匿名性はなくなる。
【００３４】
一方、データＣｉ−１，ｊを受け取ったＭｉは、入力データの正当性を検証できるため、Ｍｉの不正を防ぐことができる。また投票所Ｒｆにおいても、まず入力データの正当性が第三者機関ＴＰｋによって検証される。最終的な復号はｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅを用いて第三者機関ＴＰｋにより行われるため、正しい処理であることが保証される。また、受信者Ｒｆの例として、相談所、ギャンブル、ショッピングなどが挙げられる。特にギャンブルやショッピングなど金銭が直接伴うものは不正に対して頑強なモデルが強く求められ、第三者機関ＴＰｋは非常に重要となる。また、複数のイベントを同一匿名通信路内で同時に行い匿名通信路の利用者が増えれば、匿名性は更に強まることになる。
【００３５】
【発明の効果】
第１の効果は、本発明により実現される匿名通信路の利用者は、サイズの大きなデータを匿名かつ安全に、効果的に送信できることにある。その理由は、利用者自身が信頼できる中継サーバ及び通信経路を自由に決定することができ、データの暗号化は高速処理が実現可能な共通鍵暗号を用い、かつ不正処理を行った場合は、不正者が特定されることから不正を困難としているためである。
第２の効果は、安全かつ大規模な匿名通信が可能であり、構成された匿名通信路内で複数イベントが同時並行できることにある。その理由は、中継サーバは第三者機関に登録さえすれば誰でも運営管理でき、匿名通信路の利用者は中継サーバの決定及び最終出力先を自由に決定でき、かつその中継サーバ管理者の不正は第三者機関により特定されるためである。
【図面の簡単な説明】
【図１】発明が適用されるシステムの構成を説明するための図。
【図２】この発明の第１実施形態における利用者の処理手順を説明するためのフロー図。
【図３】上記第１実施形態における最初の中継サーバの処理手順を説明するためのフロー図。
【図４】上記第１実施形態における利用者装置の構成を説明するためのブロック図。
【図５】上記第１実施形態における中継サーバの構成を説明するためのブロック図。
【図６】この発明の第２実施形態における第三者機関の処理手順を説明するためのフロー図。
【図７】上記第２実施形態における第三者機関の構成を説明するためのブロック図。
【図８】この発明の第４実施形態における利用者の処理手順を説明するためのフロー図。
【図９】上記第４実施形態における中継サーバの処理手順を説明するためのフロー図。
【図１０】この発明の第５実施形態における利用者の処理手順を説明するためのフロー図。
【図１１】上記第５実施形態における中継サーバの処理手順を説明するためのフロー図。
【図１】
2004229105.tif 000038
【図２】
2004229105.tif 000039
【図３】
2004229105.tif 000040
【図４】
2004229105.tif 000041
【図５】
2004229105.tif 000042
【図６】
2004229105.tif 000043
【図７】
2004229105.tif 000044
【図８】
2004229105.tif 000045
【図９】
2004229105.tif 000046
【図１０】
2004229105.tif 000047
【図１１】
2004229105.tif 000048