返信経路情報生成装置、通信装置、匿名通信方法、プログラム及び記録媒体
【課題】小さい返信経路情報で双方向の匿名通信を行う。
【解決手段】巡回群G上の演算y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]、gr[0,0,0]、y[1]r[1,0,0]、gr[1,0,0]、y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]、gr[0,1,0]、 (y[1]・y[2])r[1,1,0]、gr[1,1,0]、 (y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]、gr[0,m,0]、 (y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]、gr[1,m,0](m=2,...,n-1)を行い、当該演算結果を含む返信経路情報を生成し、これを通信装置v[1]に送信する。
【解決手段】巡回群G上の演算y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]、gr[0,0,0]、y[1]r[1,0,0]、gr[1,0,0]、y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]、gr[0,1,0]、 (y[1]・y[2])r[1,1,0]、gr[1,1,0]、 (y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]、gr[0,m,0]、 (y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]、gr[1,m,0](m=2,...,n-1)を行い、当該演算結果を含む返信経路情報を生成し、これを通信装置v[1]に送信する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数の独立した通信装置が協調して情報の転送を行う通信技術において、情報の中継を行う各通信装置に対して通信経路情報を隠蔽する匿名通信技術に関し、特に、返信が可能な匿名通信技術に関する。
【背景技術】
【0002】
複数の独立した通信装置が協調して情報の転送を行う形態の通信サービスを行う場合において、情報の中継を行う通信装置に対して通信経路情報を隠蔽する暗号通信技術がある。例えば電子メールの送信サービスのように、送信元の通信装置から送信された情報が複数の独立な通信装置で繰り返し中継されて送信先の通信装置に届けられる通信サービスにおいて、情報の中継に必要のない通信経路情報(送信元や送信先の通信装置など)を情報の中継を行う各通信装置に隠蔽する暗号通信技術である。このような暗号通信技術は、一般に匿名通信と呼ばれ、その実現方法としてオニオンルーティングやその改良方式等さまざまな方式が提案されている。
【0003】
また、そのような匿名通信において、情報を中継する任意の通信装置又は送信先の通信装置から返信を行うことができれば、情報を中継する任意の通信装置から送信元の通信装置への通信エラー情報の返信や、送信先の通信装置から送信元の通信装置への応答等が可能となる。この際、中継に必要のない通信経路情報(送信元や送信先の通信装置、どの通信に対する返信であるかなど)を隠蔽したまま返信を行うことができれば、双方向の匿名通信が実現できる。
【0004】
以下では、通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信されるケースについて説明する。また、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]と示す。すなわち、送信元の通信装置v[0]から送信先の通信装置v[n]への通信経路を
v[0], e[0,1], v[1],...,v[n-1], e[n-1,n], v[n] …(1)
とする。
【0005】
ここで各通信装置v[f](f=0,...,n)には、それぞれe[f-1,f], e[f,f+1]以外にもいくつかの通信路が接続されており、v[f-1], v[f+1]以外の通信装置との通信も可能となっている。そのため、通信装置v[0]から送信され、1以上の通信装置v[h]で中継された送信情報に対して返信された情報が、通信装置v[0]に到達するためには、返信経路に位置する各通信装置v[h]がそれぞれ通信路情報e[h-1,h]を知る必要がある。すなわち、各通信装置v[h]がそれぞれ返信情報を中継するために必要とする情報は通信路情報e[h-1,h]である。そして、双方向の匿名通信を実現するためには、各通信装置v[h]はそれぞれ通信路情報e[h-1,h]及びe[h,h+1]を知ることができるが、上記(1)の通信経路を構成するその他の通信路情報を知ることができないという状態にしなければならない。
【0006】
このような双方向の匿名通信を実現する方式の一つに非特許文献1の方式がある。
【0007】
非特許文献1の方式では、送信元の通信装置v[0]から送信先の通信装置v[n]へ情報を送信する際に、以下のような多重暗号文を返信経路情報として付加して送信する。なお、Kf(・)は通信装置v[f]で復号化可能な暗号文であり、E[0]は通信装置v[0]に固有の固有情報である。
【0008】
Kn(e[n-1,n],Kn-1(e[n-2,n-1],...,K1(e[0,1],K0(E[0]))...) …(2)
この多重暗号文をv[n],...,v[0]の順序で各通信装置v[f]が復号していくと、各通信装置v[f]がKf(・)の復号を行うたびに通信路情報e[f-1,f]を得ることができる。一方、各通信装置v[f]はその他の暗号文Ki(・)(i≠k)を復号できないため、(2)の返信経路情報から他の通信路情報e[i-1,i]を得ることはできない。これにより、双方向の匿名通信が実現できる。
【0009】
しかし、非特許文献1の方式では、送信情報が送信先の通信装置v[n]に到着する前に、何れかの通信装置v[m](m=2,...,n-1)で返信を行うことができない。なぜなら、まず通信装置v[n]が復号を行わないと、他の何れの通信装置v[m]も式(2)の多重暗号文を復号できず、通信路情報e[m-1,m]を得ることができないためである。そのため、非特許文献1の方式では、例えば、通信装置v[0]と通信装置v[n]との間の通信装置v[m]の次の通信装置v[m+1]が故障している場合に、通信装置v[m]がエラー情報を通信装置v[0]に返信することができない。
【0010】
この問題を解決するための単純な方法は、各通信装置v[h](h=1,...,n)に対して、それぞれの通信装置v[h]を起点とする返信経路情報
Kn(e[n-1,n],Kn-1(e[n-2,n-1],...,K1(e[0,1],K0(E[0]))...)
Kn-1(e[n-2,n],Kn-2(e[n-3,n-2],...,K1(e[0,1],K0(E[0]))...) …(3)
Kn-2(e[n-3,n],Kn-1(e[n-4,n-2],...,K1(e[0,1],K0(E[0]))...)
. . .
K1(e[0,1],K0(E[0])
を構成して、それらすべてを送信情報に付加して送信することである。しかし、こうすると返信経路情報のサイズがO(n2)と大きくなってしまう。
このような問題を解決できる方式として非特許文献2の方式がある。
【0011】
非特許文献2の方式では、通信装置v[0]から送信された送信情報γがv[1],...,v[n-1]の順序で各通信装置v[m]で中継されて通信装置v[n]に到達するまでにおいて、各通信装置v[h] (h=1,...,n)が、それぞれ自分だけが復号できるように通信路情報e[h-1,h]を暗号化した返信経路情報を生成し、それを送信情報に添付していく。そして、返信の際には、各通信装置v[h]が自ら生成した返信経路情報を復号し、通信路情報e[h-1,h]を得ることによって匿名通信による返信が可能となる。この場合、返信経路情報の合計サイズはO(n)となる。
【非特許文献1】D. L. Chaum, “Untraceable Electronic Mail, Return Addresses,and Digital Pseudonyms,” Communications of the ACM, Vol. 24, NO.2,pp.84-88 (1981).
【非特許文献2】H. Toriyama, N. Kunihiro, and K. Ohta: “Return Message-Receivable Anonymous Routing Scheme without Reveal of Sender ID,”SCIS2007, 3B4-6 (Jan. 2007).
【発明の開示】
【発明が解決しようとする課題】
【0012】
しかし、非特許文献2の方式では、完全な匿名返信を達成することができないという問題点がある。つまり、非特許文献2の方式において不正を行おうとする通信装置v[m]は、通信路情報e[m-1,m]を暗号化する際(送信情報γ送信時)に何らかの目印となる情報δを暗号化し、それを返信経路情報に含めることができる。このように生成された返信経路情報を使って送られた返信情報が当該通信装置v[m]に届いたとき、当該通信装置v[m]は情報δを復号することができる。これにより、当該通信装置v[m]は、当該返信情報が送信情報γに対する返信であるとの情報を得ることができる。
【0013】
本発明はこのような点に鑑みてなされたものであり、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【0014】
本発明は、通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信に適用される。また、本発明では、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f](f=0,...,n)を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[j]∈Gとする。なお、通信装置v[h-1]と通信装置v[h]との間の通信路とは、少なくとも、通信装置v[h]から通信装置v[h-1]へ情報送信を行うための通信路を意味する。
【0015】
〔返信経路情報RI[0]の生成処理〕
まず、少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈G、β[0,0,0]=gr[0,0,0]∈G、α[1,0,0]=y[1]r[1,0,0]∈G、β[1,0,0]=gr[1,0,0]∈G、α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈G、β[0,1,0]=gr[0,1,0]∈G、α[1,1,0]=(y[1]・y[2])r[1,1,0]∈G、β[1,1,0]=gr[1,1,0]∈Gを行う。さらに、m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈G、β[0,m,0]=gr[0,m,0]∈G、α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈G、β[1,m,0]=gr[1,m,0]∈Gを行う。そして、4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成する。ここで、返信経路情報RI[0]のサイズはO(n)である。
そして、各通信装置v[f](f=0,...,n)が以下の処理を実行する。
【0016】
〔通信装置v[0]の送信処理〕
まず、通信装置v[0]が、返信経路情報RI[0]を通信装置v[1]に送信する。
【0017】
〔各通信装置v[u](u=1,...,n)の送信受信処理・返信開始処理〕
通信装置v[u]は、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信し、それが具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とする。そして、通信装置v[u]は、ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果をブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新する。
【0018】
ここで、通信装置v[u]が返信を行わない場合、通信装置v[u]は、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、少なくともこれらによって更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する。
【0019】
一方、通信装置v[u]が返信を行う場合、通信装置v[u]は、返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、少なくとも、これによって更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する。この返信は、通信装置v[u-1]から返信経路情報RI[u-1]が送信された通信装置v[u]が、その通信装置v[u-1]に対して行うものである。よって、任意の通信装置v[u]はこの返信が可能である。
【0020】
〔各通信装置v[u](u=1,...,n)の返信受信処理〕
また、通信装置v[u]に通信装置v[u+1]から返信経路情報RI[u+1]が返信された場合、通信装置v[u]は、その返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]とする。そして、その通信装置v[u]は、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、少なくともこれによってで更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する。ここで、返信経路情報は各通信装置で更新される情報である。そして、通信装置v[u]においてα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすのは、e[y,u]=e[u-1,u]の場合のみである。言い換えると、各通信装置v[u]は、通信装置v[u+1]から送信された返信経路情報RI[u+1]から通信路情報e[u-1,u]を得ることはできるが、この返信経路情報RI[u+1]からその他の通信路情報を得ることはできない。これにより、匿名通信による返信が可能となる。
【発明の効果】
【0021】
本発明では、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能となる。
【発明を実施するための最良の形態】
【0022】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【0023】
〔全体構成〕
まず、本形態の全体構成について説明する。
図1(a)は、本形体の匿名通信システム1の全体構成を示した図である。
図1(a)に示すように、本形態の匿名通信システム1は、ネットワークを通じた通信が可能なn個(n≧2)の通信装置v[f](f=0,...,n)である通信装置10及び通信装置20‐1〜nによって構成される。
【0024】
通信装置(v[0])10は、この匿名通信の送信先である通信装置(v[n])20‐nとそこまでの通信経路を設定する通信装置(「返信経路情報生成装置」に相当)であり、通信装置(v[1]〜v[n])20‐1〜nは、通信装置(v[0])10によって選択された装置である。すなわち、図1(a)では省略しているが、実際のネットワーク上には、通信装置(v[0])10及び通信装置(v[1]〜v[n])20‐1〜n以外にも複数の複数の通信装置が存在する。また、本形態の各通信装置は相互に独立であり、どの通信装置が匿名通信システム1を構成する通信装置であるかを知るのは、その匿名通信の送信先である通信装置(v[n])20‐nとそこまでの通信経路を設定した通信装置10のみである。
【0025】
また、e[h-1, h](h=1,...,n)は、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報である。ここで、通信装置v[h-1]と通信装置v[h]との間の通信路とは、少なくとも通信装置v[h]から通信装置v[h-1]へ情報送信を行うための通信路を意味する。また、通信装置v[h-1]と通信装置v[h]との間の通信路を特定するための通信路情報e[h-1, h]としては、例えば、通信装置v[h-1]のアドレス(IPアドレス等)を特定するための情報を例示できる。また、通信装置v[h-1]のアドレスと通信装置v[h]のアドレスとの組を特定するための情報等を通信路情報e[h-1, h]としてもよい。なお、実際には図1(a)に示していない通信装置も存在し、それらの通信装置と各通信装置v[f]との間の通信路や、各通信路情報e[h-1, h]が特定する通信路以外の通信装置v[f]間の通信路も存在する。
【0026】
また、本形態では、通信装置(v[0])10が、匿名通信の送信先である通信装置とそこまでの通信経路を設定して匿名通信システム1が構成される場合を例示するが、ネットワーク上のその他の通信装置も、匿名通信の送信先である通信装置とそこまでの通信経路を設定でき、ネットワーク上に複数の独立した匿名通信システムが構成され得るものとする。そして、各通信装置は、複数の独立した匿名通信の送信情報や返信情報を中継することもある。
【0027】
〔ハードウェア構成〕
図1(b)は、本形態の通信装置(v[0])10のハードウェア構成を例示したブロック図である。
図1(b)に例示するように、本形態の通信装置10は、CPU(Central Processing Unit)10a、入力部10b、通信部10c、RAM(Random Access Memory)10d、ROM(Read Only Memory)10e、補助記憶装置10f及びバス10gを有している。
【0028】
この例のCPU10aは、制御部10aa、演算部10ab及びレジスタ10acを有し、レジスタ10acに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部10bは、例えば、キーボード、マウス等の入力デバイスや入力端子等である。
【0029】
また、通信部10cは、LANカードやモデム等である。また、RAM10dは、SRAM (Static Random Access Memory)、DRAM (Dynamic Random Access Memory)等であり、所定のプログラムが格納されるプログラム領域10da及び各種データが格納されるデータ領域10dbを有している。また、補助記憶装置10fは、例えば、ハードディスク、MO(Magneto-Optical disc)、半導体メモリ等であり、所定のプログラムが格納されるプログラム領域10fa及び各種データが格納されるデータ領域10fbを有している。また、バス10gは、CPU10a、入力部10b、通信部10c、RAM10d、ROM10e及び補助記憶装置10fを、情報のやり取りが可能なように接続する。
【0030】
なお、その他の通信装置(v[1]〜v[n])20‐1〜nのハードウェア構成は、通信装置(v[0])10のハードウェア構成と同様であるため説明を省略する。
【0031】
〔ハードウェアとソフトウェアとの協働〕
本形態の通信装置(v[0])10及び各通信装置(v[1]〜v[n])20‐1〜nは、上述したハードウェアに所定のプログラムが読み込まれることによって構成される。以下、このように構成される通信装置(v[0])10及び各通信装置(v[1]〜v[n])20‐1〜nの機能構成を説明する。
【0032】
<通信装置(v[0])10>
図2は、本形態の通信装置10の機能構成を示したブロック図である。
図2に示すように、本形態の通信装置10は、メモリ11と、入力部12と、送信部13aと、受信部13bと、制御部14と、任意値設定部15aと、第1演算部15bと、第2演算部15cと、第3演算部15dと、第4演算部15eと、第5演算部15fと、第6演算部15gと、第7演算部15hと、第8演算部15iと、第9演算部15jと、第10演算部15kと、第11演算部15mと、第12演算部15nと、第13演算部15pと、第14演算部15qと、ダミーブロック情報生成部15rと、返信経路情報生成部15sと、判定部15tと、返信メッセージ復号部15uと、を有する。
【0033】
ここで、メモリ11は、例えば、補助記憶装置10f、RAM10d、レジスタ10ac、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部12は、例えば、所定のプログラムが読み込まれたCPU10aの制御のもと駆動する入力部10bである。また、送信部13aと受信部13bは、所定のプログラムが読み込まれたCPU10aの制御のもと駆動する通信部10cである。また、制御部14と、任意値設定部15aと、第1演算部15bと、第2演算部15cと、第3演算部15dと、第4演算部15eと、第5演算部15fと、第6演算部15gと、第7演算部15hと、第8演算部15iと、第9演算部15jと、第10演算部15kと、第11演算部15mと、第12演算部15nと、第13演算部15pと、第14演算部15qと、ダミーブロック情報生成部15rと、返信経路情報生成部15sと、判定部15tと、返信メッセージ復号部15uとは、例えば、所定のプログラムが読み込まれたCPU10aである。なお、通信装置(v[0])10は、制御部14の制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ11から読み込み、その処理結果をメモリ11に格納する。
【0034】
<返信経路情報RI[u-1]の受信処理を行う通信装置(v[u])20‐u>
図3は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])20‐uの機能構成を示したブロック図である。
図3に示すように、当該通信装置(v[u])20‐uは、メモリ21‐uと、入力部22‐uと、送信部23a‐u(「第1送信手段」及び「第2送信手段」に相当)と、受信部23b‐u(「第1受信手段」及び「第2受信手段」に相当)と、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第2ブロック情報更新部25c‐uと、第3ブロック情報更新部25d‐uと、任意値設定部25e‐uと、ランダム化部25f‐u,25h‐uと、第6ブロック情報更新部25g‐uと、順序入れ替え部25i‐uと、を有する。
【0035】
ここで、メモリ21‐uは、例えば、補助記憶装置、RAM、レジスタ、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部22‐uは、例えば、所定のプログラムが読み込まれたCPUの制御のもと駆動するキーボード等の入力部である。また、送信部23a‐u及び受信部23b‐uは、所定のプログラムが読み込まれたCPUの制御のもと駆動するLANカード等の通信部である。また、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第2ブロック情報更新部25c‐uと、第3ブロック情報更新部25d‐uと、任意値設定部25e‐uと、ランダム化部25f‐u,25h‐uと、第6ブロック情報更新部25g‐uと、順序入れ替え部25i‐uとは、例えば、所定のプログラムが読み込まれたCPUである。なお、(v[u])20‐uは、それぞれ制御部24‐uの制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ21‐uから読み込み、その処理結果をメモリ21‐uに格納する。
【0036】
<返信開始処理を行う通信装置(v[u])20‐u>
図4は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置(v[u])20‐uの機能構成を示したブロック図である。
図4に示すように、当該通信装置20‐uは、メモリ21‐uと、入力部22‐uと、送信部23a‐uと、受信部23b‐uと、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第4ブロック情報更新部26a‐uと、削除部26b‐uと、任意値設定部26c‐uと、ランダム化部26d−uと、順序入れ替え部26e‐uと、第1任意値設定部26f‐uと、第7ブロック情報更新部26g‐uと、第8ブロック情報更新部26h‐uと、第10ブロック情報更新部26i‐uと、第11ブロック情報更新部26j‐uと、を有している。
【0037】
ここで、第4ブロック情報更新部26a‐uと、削除部26b‐uと、任意値設定部26c‐uと、ランダム化部26d−uと、順序入れ替え部26e‐uと、第1任意値設定部26f‐uと、第7ブロック情報更新部26g‐uと、第8ブロック情報更新部26h‐uと、第10ブロック情報更新部26i‐uと、第11ブロック情報更新部26j‐uとは、例えば、所定のプログラムが読み込まれたCPUである。
【0038】
<返信受信処理を行う通信装置(v[u])20‐u>
図5は、通信装置v[u+1](0≦u≦n-1)から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])20‐u(0≦u≦n-1)の機能構成を示したブロック図である。
図5に示すように、当該通信装置20‐uは、入力部22‐uと、送信部23a−u(「第3送信手段」に相当)と、受信部23b‐uと、制御部24‐uと、判定部27a‐uと、第5ブロック情報更新部27b‐uと、第9ブロック情報更新部27c‐uと、第12ブロック情報更新部27d‐uと、第2任意値設定部27e‐uと、第13ブロック情報更新部27f‐uと、第14ブロック情報更新手段27g‐uと、第15ブロック情報更新手段27h‐uと、第16ブロック情報更新手段27i‐uと、任意値設定部27j‐uと、ランダム化部27k‐uと、を有する。
【0039】
ここで、判定部27a‐uと、第5ブロック情報更新部27b‐uと、第9ブロック情報更新部27c‐uと、第12ブロック情報更新部27d‐uと、第2任意値設定部27e‐uと、第13ブロック情報更新部27f‐uと、第14ブロック情報更新手段27g‐uと、第15ブロック情報更新手段27h‐uと、第16ブロック情報更新手段27i‐uと、任意値設定部27j‐uと、ランダム化部27k‐uとは、例えば、所定のプログラムが読み込まれたCPUである。
【0040】
なお、図3〜図5では、通信装置20‐uの機能構成を通信装置20‐uの機能ごとに説明したが、実際は各通信装置20‐uが図3〜図5のすべての機能構成を具備する。また、本形態の例では、通信装置10は図3〜図5のすべての機能構成を具備し、各通信装置20‐uも通信装置10の機能構成を具備する。すなわち、本形態の例では、通信装置10及び各通信装置20‐uは同一の機能構成を具備し、必要に応じて各機能を使い分ける。
【0041】
<処理>
通信装置(v[0])10から送信された送信情報は、v[1],...,v[n-1](n≧2)の順序で通信装置(v[1],...,v[n-1])20-1〜nで中継されて通信装置(v[n])20-nに届けられる。この情報送信は、オニオンルーティング等の公知の匿名通信方式を利用して行われるが、それによって送信される送信情報に本形態独自の返信経路情報が付加される点が従来との相違点である。ここで、通信装置(v[0])10が匿名通信を開始する処理を「送信開始処理」と呼び、この送信情報を通信装置(v[1],...,v[n-1])20-1〜nで受信した際に行われる処理を「送信受信処理」と呼ぶ。また、本形態では、通信装置v[h-1](h=1,...,n)から通信装置v[h]へ情報を送る処理を「送信」と呼び、通信装置v[h]から通信装置v[h-1]へ情報を送る処理を「返信」と呼ぶ。
【0042】
また、本形態の匿名通信システム1では、何れかの通信装置(v[c+1])20-(c+1)(cはu+1≦c≦n-1の整数)が、送られた送信情報に対する返信を行う。この返信情報は、v[c],...,v[1]の順序で通信装置(v[c],...,v[1])20-c〜1に中継され、通信装置(v[0])10に届けられる。ここで、通信装置(v[c+1])20-(c+1)が返信を開始する処理を「返信開始処理」と呼び、返信情報を通信装置(v[c],...,v[1])20-c〜1及び通信装置(v[0])10が受信した際に行われる処理を「返信受信処理」と呼ぶ。
【0043】
以下では、各処理の「前提」を説明した後、通信装置毎の「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」を説明する。
【0044】
[前提]
「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」の前提について説明する。
【0045】
まず、Gを位数がq(qは大きな素数)の巡回群とし、gを巡回群Gの生成元とする。本形態では、各通信装置を構成するためのプログラムに巡回群Gとその生成元gと位数qの情報とが記述されているものとする。なお、安全性の観点から、当該巡回群Gは、そこで構成された離散対数問題を多項式時間で解くことが困難なものであることが望ましい。また、そのような巡回群Gの実現例としては、例えば、楕円曲線暗号に用いられる楕円曲線上の有理点のなす群や、エルガマル暗号等に用いられる有限体の乗法群などを用いることができる(例えば、『岡本龍明,山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X(参考文献1)』等参照)。なお、巡回群Gとして楕円曲線上の有理点のなす群を用いる場合、その元は楕円曲線上の点であり、有限体の乗法群を用いる場合、その元は整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な楕円曲線暗号方式が存在する(例えば、参考文献1や『イアン・F・ブラケ、ガディエル・セロッシ、ナイジェル・P・スマート=著、鈴木治郎=訳、「楕円曲線暗号」、出版=ピアソン・エデュケーション、ISBN4-89471-431-0(参考文献2)』等参照)。また、巡回群G上の演算とは、巡回群Gで定義された演算を意味する。ここで、γ・δ∈Gは、巡回群Gの元γ,δを被演算子として当該巡回群Gで定義された演算を行うことを意味する。また、γ/δ∈Gは、巡回群Gの元γと巡回群Gの元δの逆元1/δとを被演算子として当該巡回群Gで定義された演算を行うことを意味する。さらに、γσ∈Gは、巡回群Gの元であるγに対して当該巡回群Gで定義された演算をσ回行うことを意味し、例えばγ5∈Gは、γ・γ・γ・γ・γ∈Gを意味する。巡回群Gが楕円曲線上の有理点のなす群である場合、例えば、楕円曲線上の楕円加算が「巡回群G上の演算」に相当する。この場合、γ・δ∈Gは、楕円曲線上の点γと点δとの楕円加算となり、γ/δ∈Gは、楕円曲線上の点γと楕円曲線上の点δの逆元点−δとの楕円加算となり、γσ∈Gは、楕円曲線上の点γを楕円スカラー倍(σ倍)演算となる。また、楕円曲線上の点εと楕円曲線上の点ηの逆元点−ηとの楕円加算を「巡回群G上の演算」としてもよい。この場合、γ・δ∈Gは、楕円曲線上の点γと楕円曲線上の点δの逆元点−δとの楕円加算となり、γ/δ∈Gは、楕円曲線上の点γと点δとの楕円加算となり、γσ∈Gは、楕円曲線上の点γの逆元点−γの楕円スカラー倍(σ倍)演算となる。また、巡回群Gが有限体の乗法群である場合、例えば、p(p=2q+1)を法とした積演算が「巡回群G上の演算」に相当する。この場合、γ・δ∈Gは、γ,δを整数集合の元とみた場合におけるγ・δ mod pとなり、γ/δ∈Gは、γ,δを整数集合の元とみた場合におけるγ/δ mod pとなり、γσ∈Gは、γ,δを整数集合の元とみた場合におけるγσ mod pとなる。また、例えば、ε mod pと1/η mod pとの乗算を「巡回群G上の演算」としてもよい。この場合、γ・δ∈Gは、γ,δを整数集合の元とみた場合におけるγ/δ mod pとなり、γ/δ∈Gは、γ,δを整数集合の元とみた場合におけるγ・δ mod pとなり、γσ∈Gは、γ,δを整数集合の元とみた場合における(1/γ)σ mod pとなる。
【0046】
また、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とする。固有情報E[f]としては、例えば、各通信装置のMACアドレス、IPアドレス、ユーザ名、ユーザの電話番号等を例示できる。そして、固有情報E[0]は、通信装置(v[f])10のメモリ11に格納され、各固有情報E[h] (h=1,...,n)は、それぞれに対応する通信装置(v[h])20‐hのメモリ21‐hに格納されているものとする。
【0047】
また、各通信装置v[f]の秘密鍵をx[f]∈Zqとし、各秘密鍵x[f]にそれぞれ対応する公開鍵をy[f]=gx[j]∈Gとする。ただし、Zq=(0,1...,q-1)である。なお、演算効率の面からはx[f]∈Zqとなる秘密鍵x[f]を設定することが望ましいが、その他の整数をx[f]として設定する構成であってもかまわない。秘密鍵x[0]は、通信装置(v[0])10の入力部12から入力されてメモリ11に安全に格納され、各秘密鍵x[h](h=1,...,n)は、それぞれに対応する通信装置(v[h])20‐hの入力部22‐hから入力されてメモリ21‐hに安全に格納されているものとする。
【0048】
また、通信装置(v[0])10の入力部12には、匿名通信システム1を構成する各通信装置(v[f])20‐f(f=0,...,n)の公開鍵y[f]が入力され、メモリ11に格納されているものとする。また、通信装置(v[0])10の入力部12には、匿名通信システム1を構成する各通信装置(v[h])20‐h(h=1,...,n)にそれぞれ対応する各通信路情報e[h-1, h]が入力され、メモリ11に格納されているものとする。
【0049】
さらに、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報をe[y,f]と表現する。通信装置(v[0])10の入力部12には、通信装置(v[0])10と通信可能な各通信装置v[y]に対応する通信路情報e[y,0]のリストが入力され、これらがメモリ11に格納される。同様に、各通信装置(v[h])20‐hの入力部22‐uには、それぞれ通信装置(v[h])20‐hと通信可能な各通信装置v[y]に対応する通信路情報e[y,h]のリストが入力され、これらがメモリ21-hに格納されているものとする。なお、当該通信装置v[y]には、匿名通信システム1を構成しない通信装置も含まれる。
【0050】
[送信開始処理]
次に、通信装置(v[0])10が行う送信開始処理について説明する。
図6及び図7は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【0051】
まず、通信装置(v[0])10(図2)の任意値設定部15aが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr[0,j,0],r[1,j,0],r[0,*,0]∈Zqをランダムに選択し、それらをメモリ11に格納する(ステップS12)。なお、演算効率の面では、Zqからr[0,j,0],r[1,j,0],r[0,*,0]を選択することが望ましいが、これらを広く整数から選択する構成であってもかまわない。また、これらの値をランダムに選択する方法としては、例えば、疑似乱数を生成し、それをZq又は整数に写像する方法等を例示できる。これらの事項は、Zqからランダムに値を選択するその他の処理に共通する事項であるため、以下同様の説明は省略する。
【0052】
次に、第1演算部15bが、メモリ11からE[0]とy[0]とy[1]とr[0,0,0]を読み込み、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]をメモリ11に格納する(ステップS13)。また、第2演算部15cが、メモリ11からr[0,0,0]を読み込み、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]をメモリ11に格納する(ステップS14)。また、第3演算部15dが、メモリ11からy[1]とr[1,0,0]を読み込み、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]をメモリ11に格納する(ステップS15)。さらに、第4演算部15eが、メモリ11からr[1,0,0]を読み込み、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]をメモリ11に格納する(ステップS16)。ここで、ステップS13〜S16で生成されたα[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0]の4つ組みをブロック情報RB[0,0]=(α[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0])と表現する。
【0053】
また、第5演算部15fが、メモリ11からy[1]とy[2]とe[0,1]とr[0,1,0]とを読み込み、演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]をメモリ11に格納する(ステップS17)。また、第6演算部15gが、メモリ11からr[0,1,0]を読み込み、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]をメモリ11に格納する(ステップS18)。また、第7演算部15hが、メモリ11からy[1]とy[2]とr[1,1,0]とを読み込み、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]をメモリ11に格納する(ステップS19)。さらに、第8演算部15iが、メモリ11からr[1,1,0]を読み込み、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]をメモリ11に格納する(ステップS20)。ここで、ステップS17〜S20で生成されたα[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0]の4つ組をブロック情報RB[1,0]=(α[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0])と表現する。
【0054】
また、第9演算部15jが、m=2,...,n-1のそれぞれについて、メモリ11からy[1],...,y[m-1]とy[m]とy[m+1]とr[0,m,0]とe[m-1,m]とを読み込み、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]をメモリ11に格納する(ステップS21)。また、第10演算部15kが、メモリ11からr[0,m,0]を読み込み、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]をメモリ11に格納する(ステップS22)。また、第11演算部15mが、m=2,...,n-1のそれぞれについて、メモリ11からy[1],...,y[m-1],y[m],y[m+1]とr[1,m,0]とを読み込み、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]をメモリ11に格納する(ステップS23)。さらに、第12演算部15nが、m=2,...,n-1のそれぞれについて、メモリ11からr[1,m,0]を読み込み、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]をメモリ11に格納する(ステップS24)。ここで、ステップS21〜S24で生成された各mについてのα[0,m,0],β[0,m,0],α[1,m,0],β[1,m,0]の4つ組をブロック情報RB[m,0]=(α[0,m,0],β[0,m,0],α[1,m,0],β[1,m,0]) (m=2,...,n-1)と表現する。なお、ブロック情報RB[j,0](j=0,...,n-1)は、匿名通信において返信経路を特定するための情報となる。
【0055】
また、第13演算部15pが、メモリ11からr[0,*,0]を読み込み、演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]をメモリ11に格納する(ステップS25)。さらに、第14演算部15qが、メモリ11からr[0,*,0]を読み込み、演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]をメモリ11に格納する(ステップS26)。ここで、ステップS25,S26で生成されたα[0,*,0],β[0,*,0]の組を返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])と表現する。なお、返信内容格納用情報RB[*,0]は、返信内容を暗号化するための情報となる。
【0056】
また、ダミーブロック情報生成部15rが、巡回群Gの4個の元の組G[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]∈Gをランダムに選択し、それらをメモリ11に格納する処理をD回(D≧1)行う(ステップS27)。これによって生成された各dについてのG[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]の4つ組を、それぞれダミーのブロック情報DB[d,0]=(G[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0])(d=1,...,D)と表現する。なお、ダミーのブロック情報DB[d,0]は、返信経路情報の長さから返信通信経路が推測されることを防止する役割を果たす。
【0057】
次に、返信経路情報生成部15sが、ステップS13〜S24で生成されたn個のブロック情報RB[0,0],...,RB[n-1,0]と、ステップS27で生成されたD個のダミーのブロック情報DB[1,0],..., DB[D,0]とをメモリ11から読み込む。そして、返信経路情報生成部15sは、各ブロック情報RB[0,0],...,RB[n-1,0], DB[1,0],..., DB[D,0]それぞれの4つ組の配列順序を維持しつつ、ブロック情報間の配列順序をランダムに並び替えたブロック情報列を生成し、それにステップS25,S26で生成された返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])を特定の位置(例えば、先頭位置)に付加した返信経路情報RI[0]=(RB[j,0],DB[d,0],RB[*,0]) (j=0,...,n-1)を生成し、メモリ11に格納する(ステップS28)。
【0058】
ここで、このように生成された返信経路情報RI[0]は、どの位置の情報がどのブロックRB[j,0]であり、どの位置の情報がブロックDB[d,0]であるかを示す情報を含まない。また、他の通信装置はそれらの情報を保持していない。これにより、返信経路情報RI[0]から通信経路が推測される危険性を低減できる。一方、返信内容格納用情報RB[*,0]は返信経路情報RI[0]の特定の位置に付加されるため、他の通信装置は返信経路情報RI[0]から返信内容格納用情報RB[*,0]を抽出することはできる。また、返信経路情報RI[0]は、各ブロック情報RB[0,0],...,RB[n-1,0], DB[1,0],..., DB[D,0]ぞれぞれの4つ組の配列順序を維持しているため、他の通信装置は、ブロック情報間の区切りと、ブロック情報を構成する4つの要素間の区切り及びそれらの配列順序とを知ることはできる。
【0059】
次に、送信部13aが、メモリ11から返信経路情報RI[0]を読み込み、返信経路情報RI[0]を通信装置(v[1])20‐1に送信する(ステップS29)。なお、返信経路情報RI[0]は、メッセージ等に付加され、オニオンルーティング等の周知の匿名通信方式を利用して送信される。以下では、返信経路情報RI[0]の送信に利用される周知の匿名通信方式の説明を省略し、返信経路情報に関する本形態独自の処理のみを説明する。また、「情報を通信装置に送信する」とは、中継装置を介さずに情報を当該通信装置に送信する処理の他、何らかの中継装置を経由して情報を当該通信装置に送信する処理をも含む概念である。
【0060】
[送信受信処理]
次に、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を受信した通信装置(v[u])20‐uが行う送信受信処理を説明する。
【0061】
図8及び図9は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【0062】
まず、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]=(RB[j,u-1],DB[d,u-1],RB[*,u-1]) (j=0,...,n-1)が、通信装置(v[u])20‐u(図3)の受信部23b‐uで受信され、メモリ21‐uに格納される(ステップS31)。なお、RI[u-1]=(RB[j,u-1],DB[d,u-1],RB[*,u-1])は、通信装置v[u-1](u=1,...,n)で更新(u=1のときには生成)された返信経路情報を意味する。また、RB[j,u-1]=(α[0,j,u-1],β[0,j,u-1],α[1,j,u-1],β[1,j,u-1]) (j=0,...,n-1)と表現し、DB[d,u-1]=(G[1,d,u-1],G[2,d,u-1],G[3,d,u-1],G[4,d, u-1])(d=1,...,D)と表現し、RB[*,u-1]=(α[0,*,u-1],β[0,*,u-1])と表現する。また、ステップS31で受信される返信経路情報RI[u-1]は、u=1の場合には通信装置(v[0])10から送信された返信経路情報RI[0]であり、u≧2場合には、返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置(v[1],...,v[u-1])20‐1〜(u−1)で更新され、通信装置(v[u-1])20‐(u−1)から送信された返信経路情報RI[u-1]である。
【0063】
次に、ブロック情報選択部25a‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とする(ステップS32)。このブロック情報RB[+,u-1]を特定する情報Inf(RB[+,u-1])はメモリ21‐uに格納される。なお、通信装置(v[u])20‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とダミーのDB[1,u-1],...,DB[D,u-1]とを区別できない。そのため、ブロック情報選択部25a‐uは、返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]以外の各ブロック情報について、その3番目の要素をα[1,j,u-1]とし、4番目の要素をβ[1,j,u-1]としてα[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすか否かを検証し、これを満たすブロック情報RB[+,u-1]を検索する。
【0064】
次に、第1ブロック情報更新部25b‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定し、特定したブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果をブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS33)。
【0065】
次に、制御部24‐uが、当該通信装置(v[u])20‐uが返信を行うか否かを判断する(ステップS34)。なお、通信装置(v[u])20‐uが返信を行う場合としては、例えば、u=nである場合や、通信装置(v[u+1])20‐(u+1)が故障しており、通信エラー情報を通信装置(v[0])10に返信する必要がある場合等を例示できる。
【0066】
ここで、通信装置(v[u])20‐uが返信を行うと判断された場合には、後述の通信装置v[u]の返信開始処理が実行される。
【0067】
一方、通信装置(v[u])20‐uが返信を行わないと判断された場合には、まず、第2ブロック情報更新部25c‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第2ブロック情報更新部25c‐uは、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第2ブロック情報更新部25c‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[1,d,u-1],G[2,d,u-1]に対してもそれぞれ演算G[1,d,u-1]=G[1,d,u-1]/G[2,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[1,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS35)。
【0068】
さらに、第3ブロック情報更新部25d‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第3ブロック情報更新部25d‐uは、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[1,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第3ブロック情報更新部25d‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[3,d,u-1],G[4,d,u-1]に対してもそれぞれ演算G[3,d,u-1]=G[3,d,u-1]/G[4,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[3,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS36)。
【0069】
その後、任意値設定部25e‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr1[0,j,u],r1[1,j,u],r1[0,*,u]∈Zqをランダムに選択し、それらをメモリ21‐uに格納する(ステップS37)。
【0070】
次に、ランダム化部25f‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]の各要素を
α[0,j,u-1]=α[0,j,u-1]r1[0,j,u]∈G, G[1,d,u-1]=G[1,d,u-1]r1[0,j,u]∈G
β[0,j,u-1]=β[0,j,u-1]r1[0,j,u]∈G, G[2,d,u-1]=G[2,d,u-1]r1[0,j,u]∈G
α[1,j,u-1]=α[1,j,u-1]r1[1,j,u]∈G, G[3,d,u-1]=G[3,d,u-1]r1[1,j,u]∈G
β[1,j,u-1]=β[1,j,u-1]r1[1,j,u]∈G, G[4,d,u-1]=G[4,d,u-1]r1[1,j,u]∈G
によって更新する(ステップS38)。
【0071】
さらに、第6ブロック情報更新部25g‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1], β[0,*,u-1]に対して演算α[0,*,u-1]・β[0,*,u-1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する(ステップS39)。
【0072】
次に、ランダム化部25h‐uが、メモリ21‐uに格納された各情報を用いて、
α[0,*,u-1]=α[0,*,u-1]r1[0,*,u]∈G
β[0,*,u-1]=β[0,*,u-1]r1[0,*,u]∈G
の演算を行い、これらの演算結果によってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS40)。
【0073】
次に、順序入れ替え部25i‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、返信経路情報RI[u-1]を更新する(ステップS41)。
【0074】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ21‐uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u+1])20‐(u+1)に送信する(ステップS42)。
【0075】
〔返信開始処理〕
次に、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]に対して、通信装置(v[u])20‐uが返信開始処理を行う場合の処理を説明する。
【0076】
図10は、本形態の返信開始処理を説明するためのフローチャートである。以下、この図を用いて本形態の返信開始処理を説明する。
【0077】
まず、通信装置(v[0])10(図4)の第4ブロック情報更新部26a‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第4ブロック情報更新部26a‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[1,d,u-1],G[2,d,u-1]に対してもそれぞれ演算G[1,d,u-1]=G[1,d,u-1]・G[2,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[1,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS51)。
【0078】
次に、削除部26b‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報RB[j,u-1] (j=0,...,n-1)からα[1,j,u-1],β[1,j,u-1]を削除してRB[j,u-1]=(α[0,j,u-1],β[0,j,u-1])とし、ブロック情報DB[d,u-1] (d=0,...,D)からG[3,d,u-1],G[4,d,u-1]を削除してDB[d,u-1]=(G[1,d,u-1],G[2,d,u-1])とし、メモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS52)。なお、この更新は、返信内容格納用情報RI[u-1]から以降で使用しない情報を削除する処理である。
【0079】
次に、任意値設定部26c‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr3[0,j,u]∈Zqをランダムに選択し、それをメモリ21‐uに格納する(ステップS53)。
【0080】
そして、ランダム化部26d‐uが、メモリ21‐uに格納された各要素を用い、
α[0,j,u-1]=α[0,j,u-1]r3[0,j,u]∈G, G[1,d,u-1]=G[1,d,u-1]r3[0,j,u]∈G
β[0,j,u-1]=β[0,j,u-1]r3[0,j,u]∈G, G[2,d,u-1]=G[2,d,u-1]r3[0,j,u]∈G
によってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS54)。
【0081】
次に、順序並び替え部26e‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、当該信経路情報RI[u-1]を更新する(ステップS55)。
【0082】
次に、第1任意値設定部26f‐uが、r[0,*,u],r[1,*,u]∈Zqをランダムに設定し、設定したr[0,*,u],r[1,*,u]∈Zqをメモリ21‐uに格納する(ステップS56)。
【0083】
そして、第7ブロック情報更新部26g‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ21‐uに格納されたr[0,*,u]を用い、返信メッセージをM∈Gとした場合における演算M・α[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS57)。なお、返信メッセージMは、入力部22‐uから入力された情報から生成されたものであってもよいし、予め定められたもの(例えば通信エラー情報等)であってもよい。
【0084】
また、第8ブロック情報更新部26h‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ21‐uに格納されたr[0,*,u]を用い、演算β[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS58)。
【0085】
次に、第10ブロック情報更新部26i‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ21‐uに格納されたr[1,*,u]を用い、演算α[1,*,u-1]=α[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果α[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS59)。
【0086】
また、第11ブロック情報更新部26j‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ21‐uに格納されたr[1,*,u]を用い、演算β[1,*,u-1]=β[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果β[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS60)。
【0087】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ21‐uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u-1])20‐(u‐1)に送信する(ステップS61)。
【0088】
〔通信装置v[u+1](1≦u≦n-1)の返信受信処理〕
次に、通信装置v[u+1](1≦u≦n-1)から返信された返信経路情報RI[u+1] に対して、通信装置(v[u])20‐u(1≦u≦n-1)が返信受信処理を行う場合の処理を説明する。
【0089】
まず、通信装置(v[u])20‐u(図5)の受信部22‐uが、通信装置(v[u+1])20‐(u+1)から返信された返信経路情報RI[u+1]を受信し、メモリ21‐uに格納する(ステップS71)。
【0090】
なお、1≦u≦n-2の場合、ステップS71で受信される返信経路情報RI[u+1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置(v[1],...,v[c])20‐1〜cで更新され、返信を行う通信装置(v[c+1])20‐(c+1)に送信され、通信装置(v[c+1])20‐(c+1)で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置(v[c],...,v[u+1])20‐c〜(u+1)で更新され、通信装置(v[u+1])20‐(u+1)から返信された返信経路情報RI[u+1]である。
【0091】
また、u=n-1の場合、ステップS71で受信される返信経路情報RI[u+1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置(v[1],...,v[n-1])20‐1〜(n−1)で更新され、返信を行う通信装置(v[n])20‐nに送信され、通信装置(v[n])20‐nで更新され、通信装置(v[n-1])20‐(n−1)に返信された返信経路情報RI[n]である。
【0092】
次に、判定部27a‐uが、メモリ21‐uに格納されたx[u],E(u),e[y,u]を用い、(1)メモリ21‐uに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか、(2) メモリ21‐uに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]がα[0,j,u+1]=β[0,j,u+1]x[u]・E(u)∈Gを満たすかを判定する(ステップS72)。
【0093】
ここで、u≠0の場合には(2)の条件は充足されず、(1)の条件を充足するブロック情報RB[j,u+1]と通信路情報e[y,u]との組が存在する。判定部27a‐uは、1)の条件を充足するブロック情報RB[j,u+1]と通信路情報e[y,u]とを、それぞれ
e[u-1,u]={e[y,u] |α[0,j,u+1]=β[0,j,u+1]x[u]・e[y,u]∈G}
RB[++,u+1]={RB[j,u+1] |α[0,j,u+1]=β[0,j,u+1] [u]・e[y,u]∈G}
とし、RB[++,u+1]を特定するための情報inf(RB[++,u+1])と通信路情報e[u-1,u]とをメモリ21‐uに格納する(ステップS73)。
【0094】
次に、第5ブロック情報更新部27b‐uが、メモリ21‐uに格納された情報inf(RB[++,u+1])を用いてブロック情報RB[++,u+1]を特定し、メモリ21‐uに格納された秘密鍵x[u]を用い、ブロック情報RB[++,u+1]を除く返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1],β[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS74)。
【0095】
次に、第9ブロック情報更新部27c‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],β[0,*,u+1]に対し、メモリ21‐uに格納された秘密鍵x[u]を用い、演算α[0,*,u+1]/β[0,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS75)。
【0096】
また、第12ブロック情報更新部27dが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1],β[1,*,u+1]に対し、メモリ21‐uに格納された秘密鍵x[u]を用い、演算α[1,*,u+1]/β[1,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS76)。
【0097】
また、第2任意値設定部27e‐uが、r2[0,*,u],r2[1,*,u]∈Zqをランダムに選択し、選択したr2[0,*,u],r2[1,*,u]∈Zqをメモリ21‐uに格納する(ステップS77)。
【0098】
そして、以上のように更新されメモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],α[1,*,u+1]に対し、メモリ21‐uに格納されたr2[0,*,u]を用いて演算α[0,*,u+1]・α[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS78)。
【0099】
次に、第14ブロック情報更新部27g‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[0,*,u+1],β[1,*,u+1]に対し、メモリ21‐uに格納されたr2[0,*,u]を用いて演算β[0,*,u+1]・β[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS79)。
【0100】
また、第15ブロック情報更新部27h‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1]に対し、メモリ21‐uに格納されたr2[1,*,u]を用いて演算α[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS80)。
【0101】
また、第16ブロック情報更新部27i‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[1,*,u+1]に対し、メモリ21‐uに格納されたr2[1,*,u]を用いて演算β[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなβ[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS81)。
【0102】
次に、任意値設定部27j‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr4[0,j,u]∈Zqをランダムに選択し、それをメモリ21‐uに格納する(ステップS82)。
【0103】
そして、ランダム化部27k‐uが、メモリ21‐uに格納された各要素を用い、
α[0,j,u+1]=α[0,j,u+1]r4[0,j,u]∈G,
G[1,d,u+1]=G[1,d,u+1]r4[0,j,u]∈G,
β[0,j,u+1]=β[0,j,u+1]r4[0,j,u]∈G,
G[2,d,u+1]=G[2,d,u+1]r4[0,j,u]∈G
によってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS83)。
【0104】
次に、順序並び替え部26e‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]を構成するRB[j,u+1],DB[d,u+1]の順序をランダムに並び替え、当該信経路情報RI[u+1]を更新する(ステップS84)。
【0105】
そして、以上の更新がなされた返信経路情報RI[u+1]は、返信経路情報RI[u]としてメモリ21+uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u-1])20‐(u‐1)に送信する(ステップS85)。
【0106】
〔通信装置v[1]の返信受信処理〕
図11及び図12は、信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])10が返信受信処理を行う場合の処理を説明するためのフローチャートである。以下、これらの図を用い、通信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])10が返信受信処理を行う場合の処理を説明する。
【0107】
まず、通信装置(v[0])10(図2)の受信部13bが、通信装置(v[1])20‐1から返信された返信経路情報RI[1]を受信し、メモリ11に格納する(ステップS71)。
【0108】
なお、ステップS71で受信される返信経路情報RI[1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置(v[1],...,v[c])20‐1〜cで更新され、返信を行う通信装置(v[c+1])20‐(c+1)に送信され、通信装置(v[c+1])20‐(c+1)で更新され、通信装置v[c]に返信され、v[c],...,v[1]の順序で、通信装置(v[c],...,v[1])20‐c〜1で更新され、通信装置(v[1])20‐1から返信された返信経路情報RI[1]である。
【0109】
次に、判定部15tが、メモリ11に格納されたx[0],E(0),e[y,0]を用い、(1)メモリ11に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]と、何れかの通信路情報e[y,0]との組合せに対してα[0,j, 1]=β[0,j,1]e[y,0]∈Gを満たすか、(2) メモリ11に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]がα[0,j,1]=β[0,j,1]x[0]・E(u)∈Gを満たすかを判定する(ステップS72)。
【0110】
ここで、通信装置v[1]の場合には(1)の条件は充足されず、(2)の条件が充足される。この場合、返信メッセージ復号部15uが、メモリ11に格納された返信経路情報RI[1]が具備する返信内容格納用情報RB[*,1]のα[0,*,1],β[0,*,1]に対し、演算α[0,*,1]/β[0,*,1]x[0]∈Gを行い、その演算結果を返信メッセージM∈Gとしてメモリ11に格納する(ステップS86)。
【0111】
〔本形態の特徴〕
以上説明した通り、本形態の返信経路情報RI[0]の情報サイズはO(n)である。
【0112】
また、本形態では、通信装置v[0]から送信された返信経路情報RI[0]がv[1],...,v[c]と更新され、返信開始処理を行う任意の通信装置v[c+1]に届けられる。まず、通信装置v[c+1]は、その直前の通信装置v[c]への通信路を知っているため通信装置v[c]への返信が可能である。また、以上の処理を追っていけば分かるように、通信装置v[c],...,v[1]は、それぞれステップS72の処理を行うことにより、それぞれ、次の返信先である通信装置への通信路情報を得ることができるが、当該匿名通信経路上の他の通信装置への通信路情報を得ることはできない。これは、返信経路情報を構成する各ブロック情報RBに匿名通信経路上の各通信路情報を暗号化して格納し、送信時のステップS33で次の送信先への通信路情報が暗号化されたブロック情報RB[+,u-1]に対して特殊な更新処理を行い、ステップS35,S36においてRB[+,u-1]以外の各ブロック情報RBに対して更新演算を行い、返信時のステップS74で更新復元処理を実行したことによる。つまり、上述の処理を逐一追っていけば明らかなように、このような処理を行った結果、各通信装置がステップS72でα[0,j,u+1]=β[0,j,u+1]x[u]・e[y,u]∈Gを満たすブロック情報であると検出するのは、それぞれ次の返信先の通信装置への通信路を特定する通信路情報を暗号化したブロック情報のみとなる。そして、巡回群Gでの離散対数問題が困難であり、各通信装置が他の通信装置の秘密鍵を知らないとすると、各通信装置は、自らの返信先以外の通信装置への通信路を特定する通信路情報を得ることはできない。
【0113】
以上より、本形態では、少ない情報サイズの返信経路情報を用い、送信経路上の任意の通信装置において匿名通信による返信を行うことができる。
【0114】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、各通信装置が相互に独立である場合を例示したが、少なくとも一部の通信装置が同一の管理者に管理される構成であってもよい。
【0115】
また、本形態では、各通信装置20‐uが図3〜図5に示したすべての機能構成を具備することとした。しかし、少なくとも一部の通信装置20‐uが図3〜図5に示した機能構成の一部のみを具備する構成であってもよい。例えば、送信先の通信装置v[n]が通信装置20‐nに固定されるのであれば、その通信装置20‐nは、図3及び図5に示した機能構成を具備しなくてもよい。
【0116】
また、本形態では、通信装置10も図3〜図5のすべての機能構成を具備し、各通信装置20‐uも通信装置10の機能構成を具備することとした。しかし、通信装置10が図3〜図5の機能構成を具備しないか、それらの一部の機能構成を具備する構成であってもよい。また、各通信装置20‐uが通信装置10の機能構成を具備しないか、それらの一部の機能構成を具備してもよい。さらには、一部の通信装置20‐uのみが、通信装置10の少なくとも一部の機能構成をさらに具備する構成であってもよい。
【0117】
また、返信メッセージMを暗号化する必要がない場合、ステップS12でr[0,*,0]∈Zqをランダムに選択する処理、ステップS25,S26の処理、ステップ28において返信経路情報RI[0]にRB[*,0]を付加する処理、ステップS39の処理、ステップS56〜S60の処理、ステップS75〜S81の処理等の返信内容格納用情報に関する処理や、それらの処理部を省略してもよい。
【0118】
また、安全性は低下するが、ステップS27、ステップS54、ステップS83等が具備するダミーのブロック情報に関する処理や、それらの処理部を省略してもよい。また、ステップS28、ステップS41、ステップS55、ステップS84等のブロック情報の並び替え処理や、それらの処理部を省略してもよく、ステップS37、ステップS38、ステップS40、ステップS53、ステップS54、ステップS82、ステップS83等のランダム化処理や、それらの処理部を省略してもよい。
【0119】
さらに、ステップS52の処理は、返信内容格納用情報からそれ以降使用しない情報を削除する処理であるが、ステップS52の処理やその処理部を省略してもよい。
【0120】
また、本形態では、匿名通信システムを構成する通信装置v[0]が返信経路情報生成装置である場合を例示したが、匿名通信システムを構成しないその他の装置(例えば、信頼できる第三者装置)が返信経路情報生成装置であってもよい。この場合、返信経路情報生成装置が返信経路情報を通信装置v[0]に送り、通信装置v[0]が当該返信経路情報を通信装置v[1]に送信する。この際、通信装置v[0]が返信経路情報をランダム化してから通信装置v[1]に送信してもよい。
【0121】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0122】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0123】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD(Digital Versatile Disc)、DVD−RAM(Random Access Memory)、CD−ROM(Compact Disc Read Only Memory)、CD−R(Recordable)/RW(ReWritable)等を、光磁気記録媒体として、MO(Magneto-Optical disc)等を、半導体メモリとしてEEP−ROM(Electronically Erasable and Programmable-Read Only Memory)等を用いることができる。
【0124】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0125】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0126】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0127】
本発明は、例えば、通信経路の匿名性が要求される電子投票、電子入札等の分野に利用できる。
【図面の簡単な説明】
【0128】
【図1】図1(a)は、本形体の匿名通信システムの全体構成を示した図である。図1(b)は、本形態の通信装置(v[0])のハードウェア構成を例示したブロック図である。
【図2】図2は、本形態の通信装置の機能構成を示したブロック図である。
【図3】図3は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])の機能構成を示したブロック図である。
【図4】図4は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置(v[u])の機能構成を示したブロック図である。
【図5】図5は、通信装置v[u+1](0≦u≦n-1)から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])(0≦u≦n-1)の機能構成を示したブロック図である。
【図6】図6は、本形態の送信開始処理を説明するためのフローチャートである。
【図7】図7は、本形態の送信開始処理を説明するためのフローチャートである。
【図8】図8は、本形態の送信開始処理を説明するためのフローチャートである。
【図9】図9は、本形態の送信開始処理を説明するためのフローチャートである。
【図10】図10は、本形態の返信開始処理を説明するためのフローチャートである。
【図11】図11は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【図12】図12は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【符号の説明】
【0129】
1 通信システム
【技術分野】
【0001】
本発明は、複数の独立した通信装置が協調して情報の転送を行う通信技術において、情報の中継を行う各通信装置に対して通信経路情報を隠蔽する匿名通信技術に関し、特に、返信が可能な匿名通信技術に関する。
【背景技術】
【0002】
複数の独立した通信装置が協調して情報の転送を行う形態の通信サービスを行う場合において、情報の中継を行う通信装置に対して通信経路情報を隠蔽する暗号通信技術がある。例えば電子メールの送信サービスのように、送信元の通信装置から送信された情報が複数の独立な通信装置で繰り返し中継されて送信先の通信装置に届けられる通信サービスにおいて、情報の中継に必要のない通信経路情報(送信元や送信先の通信装置など)を情報の中継を行う各通信装置に隠蔽する暗号通信技術である。このような暗号通信技術は、一般に匿名通信と呼ばれ、その実現方法としてオニオンルーティングやその改良方式等さまざまな方式が提案されている。
【0003】
また、そのような匿名通信において、情報を中継する任意の通信装置又は送信先の通信装置から返信を行うことができれば、情報を中継する任意の通信装置から送信元の通信装置への通信エラー情報の返信や、送信先の通信装置から送信元の通信装置への応答等が可能となる。この際、中継に必要のない通信経路情報(送信元や送信先の通信装置、どの通信に対する返信であるかなど)を隠蔽したまま返信を行うことができれば、双方向の匿名通信が実現できる。
【0004】
以下では、通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信されるケースについて説明する。また、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]と示す。すなわち、送信元の通信装置v[0]から送信先の通信装置v[n]への通信経路を
v[0], e[0,1], v[1],...,v[n-1], e[n-1,n], v[n] …(1)
とする。
【0005】
ここで各通信装置v[f](f=0,...,n)には、それぞれe[f-1,f], e[f,f+1]以外にもいくつかの通信路が接続されており、v[f-1], v[f+1]以外の通信装置との通信も可能となっている。そのため、通信装置v[0]から送信され、1以上の通信装置v[h]で中継された送信情報に対して返信された情報が、通信装置v[0]に到達するためには、返信経路に位置する各通信装置v[h]がそれぞれ通信路情報e[h-1,h]を知る必要がある。すなわち、各通信装置v[h]がそれぞれ返信情報を中継するために必要とする情報は通信路情報e[h-1,h]である。そして、双方向の匿名通信を実現するためには、各通信装置v[h]はそれぞれ通信路情報e[h-1,h]及びe[h,h+1]を知ることができるが、上記(1)の通信経路を構成するその他の通信路情報を知ることができないという状態にしなければならない。
【0006】
このような双方向の匿名通信を実現する方式の一つに非特許文献1の方式がある。
【0007】
非特許文献1の方式では、送信元の通信装置v[0]から送信先の通信装置v[n]へ情報を送信する際に、以下のような多重暗号文を返信経路情報として付加して送信する。なお、Kf(・)は通信装置v[f]で復号化可能な暗号文であり、E[0]は通信装置v[0]に固有の固有情報である。
【0008】
Kn(e[n-1,n],Kn-1(e[n-2,n-1],...,K1(e[0,1],K0(E[0]))...) …(2)
この多重暗号文をv[n],...,v[0]の順序で各通信装置v[f]が復号していくと、各通信装置v[f]がKf(・)の復号を行うたびに通信路情報e[f-1,f]を得ることができる。一方、各通信装置v[f]はその他の暗号文Ki(・)(i≠k)を復号できないため、(2)の返信経路情報から他の通信路情報e[i-1,i]を得ることはできない。これにより、双方向の匿名通信が実現できる。
【0009】
しかし、非特許文献1の方式では、送信情報が送信先の通信装置v[n]に到着する前に、何れかの通信装置v[m](m=2,...,n-1)で返信を行うことができない。なぜなら、まず通信装置v[n]が復号を行わないと、他の何れの通信装置v[m]も式(2)の多重暗号文を復号できず、通信路情報e[m-1,m]を得ることができないためである。そのため、非特許文献1の方式では、例えば、通信装置v[0]と通信装置v[n]との間の通信装置v[m]の次の通信装置v[m+1]が故障している場合に、通信装置v[m]がエラー情報を通信装置v[0]に返信することができない。
【0010】
この問題を解決するための単純な方法は、各通信装置v[h](h=1,...,n)に対して、それぞれの通信装置v[h]を起点とする返信経路情報
Kn(e[n-1,n],Kn-1(e[n-2,n-1],...,K1(e[0,1],K0(E[0]))...)
Kn-1(e[n-2,n],Kn-2(e[n-3,n-2],...,K1(e[0,1],K0(E[0]))...) …(3)
Kn-2(e[n-3,n],Kn-1(e[n-4,n-2],...,K1(e[0,1],K0(E[0]))...)
. . .
K1(e[0,1],K0(E[0])
を構成して、それらすべてを送信情報に付加して送信することである。しかし、こうすると返信経路情報のサイズがO(n2)と大きくなってしまう。
このような問題を解決できる方式として非特許文献2の方式がある。
【0011】
非特許文献2の方式では、通信装置v[0]から送信された送信情報γがv[1],...,v[n-1]の順序で各通信装置v[m]で中継されて通信装置v[n]に到達するまでにおいて、各通信装置v[h] (h=1,...,n)が、それぞれ自分だけが復号できるように通信路情報e[h-1,h]を暗号化した返信経路情報を生成し、それを送信情報に添付していく。そして、返信の際には、各通信装置v[h]が自ら生成した返信経路情報を復号し、通信路情報e[h-1,h]を得ることによって匿名通信による返信が可能となる。この場合、返信経路情報の合計サイズはO(n)となる。
【非特許文献1】D. L. Chaum, “Untraceable Electronic Mail, Return Addresses,and Digital Pseudonyms,” Communications of the ACM, Vol. 24, NO.2,pp.84-88 (1981).
【非特許文献2】H. Toriyama, N. Kunihiro, and K. Ohta: “Return Message-Receivable Anonymous Routing Scheme without Reveal of Sender ID,”SCIS2007, 3B4-6 (Jan. 2007).
【発明の開示】
【発明が解決しようとする課題】
【0012】
しかし、非特許文献2の方式では、完全な匿名返信を達成することができないという問題点がある。つまり、非特許文献2の方式において不正を行おうとする通信装置v[m]は、通信路情報e[m-1,m]を暗号化する際(送信情報γ送信時)に何らかの目印となる情報δを暗号化し、それを返信経路情報に含めることができる。このように生成された返信経路情報を使って送られた返信情報が当該通信装置v[m]に届いたとき、当該通信装置v[m]は情報δを復号することができる。これにより、当該通信装置v[m]は、当該返信情報が送信情報γに対する返信であるとの情報を得ることができる。
【0013】
本発明はこのような点に鑑みてなされたものであり、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【0014】
本発明は、通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信に適用される。また、本発明では、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f](f=0,...,n)を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[j]∈Gとする。なお、通信装置v[h-1]と通信装置v[h]との間の通信路とは、少なくとも、通信装置v[h]から通信装置v[h-1]へ情報送信を行うための通信路を意味する。
【0015】
〔返信経路情報RI[0]の生成処理〕
まず、少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈G、β[0,0,0]=gr[0,0,0]∈G、α[1,0,0]=y[1]r[1,0,0]∈G、β[1,0,0]=gr[1,0,0]∈G、α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈G、β[0,1,0]=gr[0,1,0]∈G、α[1,1,0]=(y[1]・y[2])r[1,1,0]∈G、β[1,1,0]=gr[1,1,0]∈Gを行う。さらに、m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈G、β[0,m,0]=gr[0,m,0]∈G、α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈G、β[1,m,0]=gr[1,m,0]∈Gを行う。そして、4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成する。ここで、返信経路情報RI[0]のサイズはO(n)である。
そして、各通信装置v[f](f=0,...,n)が以下の処理を実行する。
【0016】
〔通信装置v[0]の送信処理〕
まず、通信装置v[0]が、返信経路情報RI[0]を通信装置v[1]に送信する。
【0017】
〔各通信装置v[u](u=1,...,n)の送信受信処理・返信開始処理〕
通信装置v[u]は、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信し、それが具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とする。そして、通信装置v[u]は、ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果をブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新する。
【0018】
ここで、通信装置v[u]が返信を行わない場合、通信装置v[u]は、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、少なくともこれらによって更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する。
【0019】
一方、通信装置v[u]が返信を行う場合、通信装置v[u]は、返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、少なくとも、これによって更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する。この返信は、通信装置v[u-1]から返信経路情報RI[u-1]が送信された通信装置v[u]が、その通信装置v[u-1]に対して行うものである。よって、任意の通信装置v[u]はこの返信が可能である。
【0020】
〔各通信装置v[u](u=1,...,n)の返信受信処理〕
また、通信装置v[u]に通信装置v[u+1]から返信経路情報RI[u+1]が返信された場合、通信装置v[u]は、その返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]とする。そして、その通信装置v[u]は、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、少なくともこれによってで更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する。ここで、返信経路情報は各通信装置で更新される情報である。そして、通信装置v[u]においてα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすのは、e[y,u]=e[u-1,u]の場合のみである。言い換えると、各通信装置v[u]は、通信装置v[u+1]から送信された返信経路情報RI[u+1]から通信路情報e[u-1,u]を得ることはできるが、この返信経路情報RI[u+1]からその他の通信路情報を得ることはできない。これにより、匿名通信による返信が可能となる。
【発明の効果】
【0021】
本発明では、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能となる。
【発明を実施するための最良の形態】
【0022】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【0023】
〔全体構成〕
まず、本形態の全体構成について説明する。
図1(a)は、本形体の匿名通信システム1の全体構成を示した図である。
図1(a)に示すように、本形態の匿名通信システム1は、ネットワークを通じた通信が可能なn個(n≧2)の通信装置v[f](f=0,...,n)である通信装置10及び通信装置20‐1〜nによって構成される。
【0024】
通信装置(v[0])10は、この匿名通信の送信先である通信装置(v[n])20‐nとそこまでの通信経路を設定する通信装置(「返信経路情報生成装置」に相当)であり、通信装置(v[1]〜v[n])20‐1〜nは、通信装置(v[0])10によって選択された装置である。すなわち、図1(a)では省略しているが、実際のネットワーク上には、通信装置(v[0])10及び通信装置(v[1]〜v[n])20‐1〜n以外にも複数の複数の通信装置が存在する。また、本形態の各通信装置は相互に独立であり、どの通信装置が匿名通信システム1を構成する通信装置であるかを知るのは、その匿名通信の送信先である通信装置(v[n])20‐nとそこまでの通信経路を設定した通信装置10のみである。
【0025】
また、e[h-1, h](h=1,...,n)は、通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報である。ここで、通信装置v[h-1]と通信装置v[h]との間の通信路とは、少なくとも通信装置v[h]から通信装置v[h-1]へ情報送信を行うための通信路を意味する。また、通信装置v[h-1]と通信装置v[h]との間の通信路を特定するための通信路情報e[h-1, h]としては、例えば、通信装置v[h-1]のアドレス(IPアドレス等)を特定するための情報を例示できる。また、通信装置v[h-1]のアドレスと通信装置v[h]のアドレスとの組を特定するための情報等を通信路情報e[h-1, h]としてもよい。なお、実際には図1(a)に示していない通信装置も存在し、それらの通信装置と各通信装置v[f]との間の通信路や、各通信路情報e[h-1, h]が特定する通信路以外の通信装置v[f]間の通信路も存在する。
【0026】
また、本形態では、通信装置(v[0])10が、匿名通信の送信先である通信装置とそこまでの通信経路を設定して匿名通信システム1が構成される場合を例示するが、ネットワーク上のその他の通信装置も、匿名通信の送信先である通信装置とそこまでの通信経路を設定でき、ネットワーク上に複数の独立した匿名通信システムが構成され得るものとする。そして、各通信装置は、複数の独立した匿名通信の送信情報や返信情報を中継することもある。
【0027】
〔ハードウェア構成〕
図1(b)は、本形態の通信装置(v[0])10のハードウェア構成を例示したブロック図である。
図1(b)に例示するように、本形態の通信装置10は、CPU(Central Processing Unit)10a、入力部10b、通信部10c、RAM(Random Access Memory)10d、ROM(Read Only Memory)10e、補助記憶装置10f及びバス10gを有している。
【0028】
この例のCPU10aは、制御部10aa、演算部10ab及びレジスタ10acを有し、レジスタ10acに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部10bは、例えば、キーボード、マウス等の入力デバイスや入力端子等である。
【0029】
また、通信部10cは、LANカードやモデム等である。また、RAM10dは、SRAM (Static Random Access Memory)、DRAM (Dynamic Random Access Memory)等であり、所定のプログラムが格納されるプログラム領域10da及び各種データが格納されるデータ領域10dbを有している。また、補助記憶装置10fは、例えば、ハードディスク、MO(Magneto-Optical disc)、半導体メモリ等であり、所定のプログラムが格納されるプログラム領域10fa及び各種データが格納されるデータ領域10fbを有している。また、バス10gは、CPU10a、入力部10b、通信部10c、RAM10d、ROM10e及び補助記憶装置10fを、情報のやり取りが可能なように接続する。
【0030】
なお、その他の通信装置(v[1]〜v[n])20‐1〜nのハードウェア構成は、通信装置(v[0])10のハードウェア構成と同様であるため説明を省略する。
【0031】
〔ハードウェアとソフトウェアとの協働〕
本形態の通信装置(v[0])10及び各通信装置(v[1]〜v[n])20‐1〜nは、上述したハードウェアに所定のプログラムが読み込まれることによって構成される。以下、このように構成される通信装置(v[0])10及び各通信装置(v[1]〜v[n])20‐1〜nの機能構成を説明する。
【0032】
<通信装置(v[0])10>
図2は、本形態の通信装置10の機能構成を示したブロック図である。
図2に示すように、本形態の通信装置10は、メモリ11と、入力部12と、送信部13aと、受信部13bと、制御部14と、任意値設定部15aと、第1演算部15bと、第2演算部15cと、第3演算部15dと、第4演算部15eと、第5演算部15fと、第6演算部15gと、第7演算部15hと、第8演算部15iと、第9演算部15jと、第10演算部15kと、第11演算部15mと、第12演算部15nと、第13演算部15pと、第14演算部15qと、ダミーブロック情報生成部15rと、返信経路情報生成部15sと、判定部15tと、返信メッセージ復号部15uと、を有する。
【0033】
ここで、メモリ11は、例えば、補助記憶装置10f、RAM10d、レジスタ10ac、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部12は、例えば、所定のプログラムが読み込まれたCPU10aの制御のもと駆動する入力部10bである。また、送信部13aと受信部13bは、所定のプログラムが読み込まれたCPU10aの制御のもと駆動する通信部10cである。また、制御部14と、任意値設定部15aと、第1演算部15bと、第2演算部15cと、第3演算部15dと、第4演算部15eと、第5演算部15fと、第6演算部15gと、第7演算部15hと、第8演算部15iと、第9演算部15jと、第10演算部15kと、第11演算部15mと、第12演算部15nと、第13演算部15pと、第14演算部15qと、ダミーブロック情報生成部15rと、返信経路情報生成部15sと、判定部15tと、返信メッセージ復号部15uとは、例えば、所定のプログラムが読み込まれたCPU10aである。なお、通信装置(v[0])10は、制御部14の制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ11から読み込み、その処理結果をメモリ11に格納する。
【0034】
<返信経路情報RI[u-1]の受信処理を行う通信装置(v[u])20‐u>
図3は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])20‐uの機能構成を示したブロック図である。
図3に示すように、当該通信装置(v[u])20‐uは、メモリ21‐uと、入力部22‐uと、送信部23a‐u(「第1送信手段」及び「第2送信手段」に相当)と、受信部23b‐u(「第1受信手段」及び「第2受信手段」に相当)と、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第2ブロック情報更新部25c‐uと、第3ブロック情報更新部25d‐uと、任意値設定部25e‐uと、ランダム化部25f‐u,25h‐uと、第6ブロック情報更新部25g‐uと、順序入れ替え部25i‐uと、を有する。
【0035】
ここで、メモリ21‐uは、例えば、補助記憶装置、RAM、レジスタ、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部22‐uは、例えば、所定のプログラムが読み込まれたCPUの制御のもと駆動するキーボード等の入力部である。また、送信部23a‐u及び受信部23b‐uは、所定のプログラムが読み込まれたCPUの制御のもと駆動するLANカード等の通信部である。また、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第2ブロック情報更新部25c‐uと、第3ブロック情報更新部25d‐uと、任意値設定部25e‐uと、ランダム化部25f‐u,25h‐uと、第6ブロック情報更新部25g‐uと、順序入れ替え部25i‐uとは、例えば、所定のプログラムが読み込まれたCPUである。なお、(v[u])20‐uは、それぞれ制御部24‐uの制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ21‐uから読み込み、その処理結果をメモリ21‐uに格納する。
【0036】
<返信開始処理を行う通信装置(v[u])20‐u>
図4は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置(v[u])20‐uの機能構成を示したブロック図である。
図4に示すように、当該通信装置20‐uは、メモリ21‐uと、入力部22‐uと、送信部23a‐uと、受信部23b‐uと、制御部24‐uと、ブロック情報選択部25a‐uと、第1ブロック情報更新部25b‐uと、第4ブロック情報更新部26a‐uと、削除部26b‐uと、任意値設定部26c‐uと、ランダム化部26d−uと、順序入れ替え部26e‐uと、第1任意値設定部26f‐uと、第7ブロック情報更新部26g‐uと、第8ブロック情報更新部26h‐uと、第10ブロック情報更新部26i‐uと、第11ブロック情報更新部26j‐uと、を有している。
【0037】
ここで、第4ブロック情報更新部26a‐uと、削除部26b‐uと、任意値設定部26c‐uと、ランダム化部26d−uと、順序入れ替え部26e‐uと、第1任意値設定部26f‐uと、第7ブロック情報更新部26g‐uと、第8ブロック情報更新部26h‐uと、第10ブロック情報更新部26i‐uと、第11ブロック情報更新部26j‐uとは、例えば、所定のプログラムが読み込まれたCPUである。
【0038】
<返信受信処理を行う通信装置(v[u])20‐u>
図5は、通信装置v[u+1](0≦u≦n-1)から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])20‐u(0≦u≦n-1)の機能構成を示したブロック図である。
図5に示すように、当該通信装置20‐uは、入力部22‐uと、送信部23a−u(「第3送信手段」に相当)と、受信部23b‐uと、制御部24‐uと、判定部27a‐uと、第5ブロック情報更新部27b‐uと、第9ブロック情報更新部27c‐uと、第12ブロック情報更新部27d‐uと、第2任意値設定部27e‐uと、第13ブロック情報更新部27f‐uと、第14ブロック情報更新手段27g‐uと、第15ブロック情報更新手段27h‐uと、第16ブロック情報更新手段27i‐uと、任意値設定部27j‐uと、ランダム化部27k‐uと、を有する。
【0039】
ここで、判定部27a‐uと、第5ブロック情報更新部27b‐uと、第9ブロック情報更新部27c‐uと、第12ブロック情報更新部27d‐uと、第2任意値設定部27e‐uと、第13ブロック情報更新部27f‐uと、第14ブロック情報更新手段27g‐uと、第15ブロック情報更新手段27h‐uと、第16ブロック情報更新手段27i‐uと、任意値設定部27j‐uと、ランダム化部27k‐uとは、例えば、所定のプログラムが読み込まれたCPUである。
【0040】
なお、図3〜図5では、通信装置20‐uの機能構成を通信装置20‐uの機能ごとに説明したが、実際は各通信装置20‐uが図3〜図5のすべての機能構成を具備する。また、本形態の例では、通信装置10は図3〜図5のすべての機能構成を具備し、各通信装置20‐uも通信装置10の機能構成を具備する。すなわち、本形態の例では、通信装置10及び各通信装置20‐uは同一の機能構成を具備し、必要に応じて各機能を使い分ける。
【0041】
<処理>
通信装置(v[0])10から送信された送信情報は、v[1],...,v[n-1](n≧2)の順序で通信装置(v[1],...,v[n-1])20-1〜nで中継されて通信装置(v[n])20-nに届けられる。この情報送信は、オニオンルーティング等の公知の匿名通信方式を利用して行われるが、それによって送信される送信情報に本形態独自の返信経路情報が付加される点が従来との相違点である。ここで、通信装置(v[0])10が匿名通信を開始する処理を「送信開始処理」と呼び、この送信情報を通信装置(v[1],...,v[n-1])20-1〜nで受信した際に行われる処理を「送信受信処理」と呼ぶ。また、本形態では、通信装置v[h-1](h=1,...,n)から通信装置v[h]へ情報を送る処理を「送信」と呼び、通信装置v[h]から通信装置v[h-1]へ情報を送る処理を「返信」と呼ぶ。
【0042】
また、本形態の匿名通信システム1では、何れかの通信装置(v[c+1])20-(c+1)(cはu+1≦c≦n-1の整数)が、送られた送信情報に対する返信を行う。この返信情報は、v[c],...,v[1]の順序で通信装置(v[c],...,v[1])20-c〜1に中継され、通信装置(v[0])10に届けられる。ここで、通信装置(v[c+1])20-(c+1)が返信を開始する処理を「返信開始処理」と呼び、返信情報を通信装置(v[c],...,v[1])20-c〜1及び通信装置(v[0])10が受信した際に行われる処理を「返信受信処理」と呼ぶ。
【0043】
以下では、各処理の「前提」を説明した後、通信装置毎の「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」を説明する。
【0044】
[前提]
「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」の前提について説明する。
【0045】
まず、Gを位数がq(qは大きな素数)の巡回群とし、gを巡回群Gの生成元とする。本形態では、各通信装置を構成するためのプログラムに巡回群Gとその生成元gと位数qの情報とが記述されているものとする。なお、安全性の観点から、当該巡回群Gは、そこで構成された離散対数問題を多項式時間で解くことが困難なものであることが望ましい。また、そのような巡回群Gの実現例としては、例えば、楕円曲線暗号に用いられる楕円曲線上の有理点のなす群や、エルガマル暗号等に用いられる有限体の乗法群などを用いることができる(例えば、『岡本龍明,山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X(参考文献1)』等参照)。なお、巡回群Gとして楕円曲線上の有理点のなす群を用いる場合、その元は楕円曲線上の点であり、有限体の乗法群を用いる場合、その元は整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な楕円曲線暗号方式が存在する(例えば、参考文献1や『イアン・F・ブラケ、ガディエル・セロッシ、ナイジェル・P・スマート=著、鈴木治郎=訳、「楕円曲線暗号」、出版=ピアソン・エデュケーション、ISBN4-89471-431-0(参考文献2)』等参照)。また、巡回群G上の演算とは、巡回群Gで定義された演算を意味する。ここで、γ・δ∈Gは、巡回群Gの元γ,δを被演算子として当該巡回群Gで定義された演算を行うことを意味する。また、γ/δ∈Gは、巡回群Gの元γと巡回群Gの元δの逆元1/δとを被演算子として当該巡回群Gで定義された演算を行うことを意味する。さらに、γσ∈Gは、巡回群Gの元であるγに対して当該巡回群Gで定義された演算をσ回行うことを意味し、例えばγ5∈Gは、γ・γ・γ・γ・γ∈Gを意味する。巡回群Gが楕円曲線上の有理点のなす群である場合、例えば、楕円曲線上の楕円加算が「巡回群G上の演算」に相当する。この場合、γ・δ∈Gは、楕円曲線上の点γと点δとの楕円加算となり、γ/δ∈Gは、楕円曲線上の点γと楕円曲線上の点δの逆元点−δとの楕円加算となり、γσ∈Gは、楕円曲線上の点γを楕円スカラー倍(σ倍)演算となる。また、楕円曲線上の点εと楕円曲線上の点ηの逆元点−ηとの楕円加算を「巡回群G上の演算」としてもよい。この場合、γ・δ∈Gは、楕円曲線上の点γと楕円曲線上の点δの逆元点−δとの楕円加算となり、γ/δ∈Gは、楕円曲線上の点γと点δとの楕円加算となり、γσ∈Gは、楕円曲線上の点γの逆元点−γの楕円スカラー倍(σ倍)演算となる。また、巡回群Gが有限体の乗法群である場合、例えば、p(p=2q+1)を法とした積演算が「巡回群G上の演算」に相当する。この場合、γ・δ∈Gは、γ,δを整数集合の元とみた場合におけるγ・δ mod pとなり、γ/δ∈Gは、γ,δを整数集合の元とみた場合におけるγ/δ mod pとなり、γσ∈Gは、γ,δを整数集合の元とみた場合におけるγσ mod pとなる。また、例えば、ε mod pと1/η mod pとの乗算を「巡回群G上の演算」としてもよい。この場合、γ・δ∈Gは、γ,δを整数集合の元とみた場合におけるγ/δ mod pとなり、γ/δ∈Gは、γ,δを整数集合の元とみた場合におけるγ・δ mod pとなり、γσ∈Gは、γ,δを整数集合の元とみた場合における(1/γ)σ mod pとなる。
【0046】
また、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とする。固有情報E[f]としては、例えば、各通信装置のMACアドレス、IPアドレス、ユーザ名、ユーザの電話番号等を例示できる。そして、固有情報E[0]は、通信装置(v[f])10のメモリ11に格納され、各固有情報E[h] (h=1,...,n)は、それぞれに対応する通信装置(v[h])20‐hのメモリ21‐hに格納されているものとする。
【0047】
また、各通信装置v[f]の秘密鍵をx[f]∈Zqとし、各秘密鍵x[f]にそれぞれ対応する公開鍵をy[f]=gx[j]∈Gとする。ただし、Zq=(0,1...,q-1)である。なお、演算効率の面からはx[f]∈Zqとなる秘密鍵x[f]を設定することが望ましいが、その他の整数をx[f]として設定する構成であってもかまわない。秘密鍵x[0]は、通信装置(v[0])10の入力部12から入力されてメモリ11に安全に格納され、各秘密鍵x[h](h=1,...,n)は、それぞれに対応する通信装置(v[h])20‐hの入力部22‐hから入力されてメモリ21‐hに安全に格納されているものとする。
【0048】
また、通信装置(v[0])10の入力部12には、匿名通信システム1を構成する各通信装置(v[f])20‐f(f=0,...,n)の公開鍵y[f]が入力され、メモリ11に格納されているものとする。また、通信装置(v[0])10の入力部12には、匿名通信システム1を構成する各通信装置(v[h])20‐h(h=1,...,n)にそれぞれ対応する各通信路情報e[h-1, h]が入力され、メモリ11に格納されているものとする。
【0049】
さらに、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報をe[y,f]と表現する。通信装置(v[0])10の入力部12には、通信装置(v[0])10と通信可能な各通信装置v[y]に対応する通信路情報e[y,0]のリストが入力され、これらがメモリ11に格納される。同様に、各通信装置(v[h])20‐hの入力部22‐uには、それぞれ通信装置(v[h])20‐hと通信可能な各通信装置v[y]に対応する通信路情報e[y,h]のリストが入力され、これらがメモリ21-hに格納されているものとする。なお、当該通信装置v[y]には、匿名通信システム1を構成しない通信装置も含まれる。
【0050】
[送信開始処理]
次に、通信装置(v[0])10が行う送信開始処理について説明する。
図6及び図7は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【0051】
まず、通信装置(v[0])10(図2)の任意値設定部15aが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr[0,j,0],r[1,j,0],r[0,*,0]∈Zqをランダムに選択し、それらをメモリ11に格納する(ステップS12)。なお、演算効率の面では、Zqからr[0,j,0],r[1,j,0],r[0,*,0]を選択することが望ましいが、これらを広く整数から選択する構成であってもかまわない。また、これらの値をランダムに選択する方法としては、例えば、疑似乱数を生成し、それをZq又は整数に写像する方法等を例示できる。これらの事項は、Zqからランダムに値を選択するその他の処理に共通する事項であるため、以下同様の説明は省略する。
【0052】
次に、第1演算部15bが、メモリ11からE[0]とy[0]とy[1]とr[0,0,0]を読み込み、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]をメモリ11に格納する(ステップS13)。また、第2演算部15cが、メモリ11からr[0,0,0]を読み込み、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]をメモリ11に格納する(ステップS14)。また、第3演算部15dが、メモリ11からy[1]とr[1,0,0]を読み込み、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]をメモリ11に格納する(ステップS15)。さらに、第4演算部15eが、メモリ11からr[1,0,0]を読み込み、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]をメモリ11に格納する(ステップS16)。ここで、ステップS13〜S16で生成されたα[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0]の4つ組みをブロック情報RB[0,0]=(α[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0])と表現する。
【0053】
また、第5演算部15fが、メモリ11からy[1]とy[2]とe[0,1]とr[0,1,0]とを読み込み、演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]をメモリ11に格納する(ステップS17)。また、第6演算部15gが、メモリ11からr[0,1,0]を読み込み、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]をメモリ11に格納する(ステップS18)。また、第7演算部15hが、メモリ11からy[1]とy[2]とr[1,1,0]とを読み込み、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]をメモリ11に格納する(ステップS19)。さらに、第8演算部15iが、メモリ11からr[1,1,0]を読み込み、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]をメモリ11に格納する(ステップS20)。ここで、ステップS17〜S20で生成されたα[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0]の4つ組をブロック情報RB[1,0]=(α[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0])と表現する。
【0054】
また、第9演算部15jが、m=2,...,n-1のそれぞれについて、メモリ11からy[1],...,y[m-1]とy[m]とy[m+1]とr[0,m,0]とe[m-1,m]とを読み込み、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]をメモリ11に格納する(ステップS21)。また、第10演算部15kが、メモリ11からr[0,m,0]を読み込み、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]をメモリ11に格納する(ステップS22)。また、第11演算部15mが、m=2,...,n-1のそれぞれについて、メモリ11からy[1],...,y[m-1],y[m],y[m+1]とr[1,m,0]とを読み込み、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]をメモリ11に格納する(ステップS23)。さらに、第12演算部15nが、m=2,...,n-1のそれぞれについて、メモリ11からr[1,m,0]を読み込み、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]をメモリ11に格納する(ステップS24)。ここで、ステップS21〜S24で生成された各mについてのα[0,m,0],β[0,m,0],α[1,m,0],β[1,m,0]の4つ組をブロック情報RB[m,0]=(α[0,m,0],β[0,m,0],α[1,m,0],β[1,m,0]) (m=2,...,n-1)と表現する。なお、ブロック情報RB[j,0](j=0,...,n-1)は、匿名通信において返信経路を特定するための情報となる。
【0055】
また、第13演算部15pが、メモリ11からr[0,*,0]を読み込み、演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]をメモリ11に格納する(ステップS25)。さらに、第14演算部15qが、メモリ11からr[0,*,0]を読み込み、演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]をメモリ11に格納する(ステップS26)。ここで、ステップS25,S26で生成されたα[0,*,0],β[0,*,0]の組を返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])と表現する。なお、返信内容格納用情報RB[*,0]は、返信内容を暗号化するための情報となる。
【0056】
また、ダミーブロック情報生成部15rが、巡回群Gの4個の元の組G[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]∈Gをランダムに選択し、それらをメモリ11に格納する処理をD回(D≧1)行う(ステップS27)。これによって生成された各dについてのG[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]の4つ組を、それぞれダミーのブロック情報DB[d,0]=(G[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0])(d=1,...,D)と表現する。なお、ダミーのブロック情報DB[d,0]は、返信経路情報の長さから返信通信経路が推測されることを防止する役割を果たす。
【0057】
次に、返信経路情報生成部15sが、ステップS13〜S24で生成されたn個のブロック情報RB[0,0],...,RB[n-1,0]と、ステップS27で生成されたD個のダミーのブロック情報DB[1,0],..., DB[D,0]とをメモリ11から読み込む。そして、返信経路情報生成部15sは、各ブロック情報RB[0,0],...,RB[n-1,0], DB[1,0],..., DB[D,0]それぞれの4つ組の配列順序を維持しつつ、ブロック情報間の配列順序をランダムに並び替えたブロック情報列を生成し、それにステップS25,S26で生成された返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])を特定の位置(例えば、先頭位置)に付加した返信経路情報RI[0]=(RB[j,0],DB[d,0],RB[*,0]) (j=0,...,n-1)を生成し、メモリ11に格納する(ステップS28)。
【0058】
ここで、このように生成された返信経路情報RI[0]は、どの位置の情報がどのブロックRB[j,0]であり、どの位置の情報がブロックDB[d,0]であるかを示す情報を含まない。また、他の通信装置はそれらの情報を保持していない。これにより、返信経路情報RI[0]から通信経路が推測される危険性を低減できる。一方、返信内容格納用情報RB[*,0]は返信経路情報RI[0]の特定の位置に付加されるため、他の通信装置は返信経路情報RI[0]から返信内容格納用情報RB[*,0]を抽出することはできる。また、返信経路情報RI[0]は、各ブロック情報RB[0,0],...,RB[n-1,0], DB[1,0],..., DB[D,0]ぞれぞれの4つ組の配列順序を維持しているため、他の通信装置は、ブロック情報間の区切りと、ブロック情報を構成する4つの要素間の区切り及びそれらの配列順序とを知ることはできる。
【0059】
次に、送信部13aが、メモリ11から返信経路情報RI[0]を読み込み、返信経路情報RI[0]を通信装置(v[1])20‐1に送信する(ステップS29)。なお、返信経路情報RI[0]は、メッセージ等に付加され、オニオンルーティング等の周知の匿名通信方式を利用して送信される。以下では、返信経路情報RI[0]の送信に利用される周知の匿名通信方式の説明を省略し、返信経路情報に関する本形態独自の処理のみを説明する。また、「情報を通信装置に送信する」とは、中継装置を介さずに情報を当該通信装置に送信する処理の他、何らかの中継装置を経由して情報を当該通信装置に送信する処理をも含む概念である。
【0060】
[送信受信処理]
次に、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を受信した通信装置(v[u])20‐uが行う送信受信処理を説明する。
【0061】
図8及び図9は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【0062】
まず、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]=(RB[j,u-1],DB[d,u-1],RB[*,u-1]) (j=0,...,n-1)が、通信装置(v[u])20‐u(図3)の受信部23b‐uで受信され、メモリ21‐uに格納される(ステップS31)。なお、RI[u-1]=(RB[j,u-1],DB[d,u-1],RB[*,u-1])は、通信装置v[u-1](u=1,...,n)で更新(u=1のときには生成)された返信経路情報を意味する。また、RB[j,u-1]=(α[0,j,u-1],β[0,j,u-1],α[1,j,u-1],β[1,j,u-1]) (j=0,...,n-1)と表現し、DB[d,u-1]=(G[1,d,u-1],G[2,d,u-1],G[3,d,u-1],G[4,d, u-1])(d=1,...,D)と表現し、RB[*,u-1]=(α[0,*,u-1],β[0,*,u-1])と表現する。また、ステップS31で受信される返信経路情報RI[u-1]は、u=1の場合には通信装置(v[0])10から送信された返信経路情報RI[0]であり、u≧2場合には、返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置(v[1],...,v[u-1])20‐1〜(u−1)で更新され、通信装置(v[u-1])20‐(u−1)から送信された返信経路情報RI[u-1]である。
【0063】
次に、ブロック情報選択部25a‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とする(ステップS32)。このブロック情報RB[+,u-1]を特定する情報Inf(RB[+,u-1])はメモリ21‐uに格納される。なお、通信装置(v[u])20‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とダミーのDB[1,u-1],...,DB[D,u-1]とを区別できない。そのため、ブロック情報選択部25a‐uは、返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]以外の各ブロック情報について、その3番目の要素をα[1,j,u-1]とし、4番目の要素をβ[1,j,u-1]としてα[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすか否かを検証し、これを満たすブロック情報RB[+,u-1]を検索する。
【0064】
次に、第1ブロック情報更新部25b‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定し、特定したブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果をブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS33)。
【0065】
次に、制御部24‐uが、当該通信装置(v[u])20‐uが返信を行うか否かを判断する(ステップS34)。なお、通信装置(v[u])20‐uが返信を行う場合としては、例えば、u=nである場合や、通信装置(v[u+1])20‐(u+1)が故障しており、通信エラー情報を通信装置(v[0])10に返信する必要がある場合等を例示できる。
【0066】
ここで、通信装置(v[u])20‐uが返信を行うと判断された場合には、後述の通信装置v[u]の返信開始処理が実行される。
【0067】
一方、通信装置(v[u])20‐uが返信を行わないと判断された場合には、まず、第2ブロック情報更新部25c‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第2ブロック情報更新部25c‐uは、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第2ブロック情報更新部25c‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[1,d,u-1],G[2,d,u-1]に対してもそれぞれ演算G[1,d,u-1]=G[1,d,u-1]/G[2,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[1,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS35)。
【0068】
さらに、第3ブロック情報更新部25d‐uが、メモリ21‐uから情報Inf(RB[+,u-1])を読み込み、メモリ21‐uに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第3ブロック情報更新部25d‐uは、ブロック情報RB[+,u-1]を除く返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[1,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第3ブロック情報更新部25d‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[3,d,u-1],G[4,d,u-1]に対してもそれぞれ演算G[3,d,u-1]=G[3,d,u-1]/G[4,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[3,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS36)。
【0069】
その後、任意値設定部25e‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr1[0,j,u],r1[1,j,u],r1[0,*,u]∈Zqをランダムに選択し、それらをメモリ21‐uに格納する(ステップS37)。
【0070】
次に、ランダム化部25f‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]の各要素を
α[0,j,u-1]=α[0,j,u-1]r1[0,j,u]∈G, G[1,d,u-1]=G[1,d,u-1]r1[0,j,u]∈G
β[0,j,u-1]=β[0,j,u-1]r1[0,j,u]∈G, G[2,d,u-1]=G[2,d,u-1]r1[0,j,u]∈G
α[1,j,u-1]=α[1,j,u-1]r1[1,j,u]∈G, G[3,d,u-1]=G[3,d,u-1]r1[1,j,u]∈G
β[1,j,u-1]=β[1,j,u-1]r1[1,j,u]∈G, G[4,d,u-1]=G[4,d,u-1]r1[1,j,u]∈G
によって更新する(ステップS38)。
【0071】
さらに、第6ブロック情報更新部25g‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1], β[0,*,u-1]に対して演算α[0,*,u-1]・β[0,*,u-1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する(ステップS39)。
【0072】
次に、ランダム化部25h‐uが、メモリ21‐uに格納された各情報を用いて、
α[0,*,u-1]=α[0,*,u-1]r1[0,*,u]∈G
β[0,*,u-1]=β[0,*,u-1]r1[0,*,u]∈G
の演算を行い、これらの演算結果によってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS40)。
【0073】
次に、順序入れ替え部25i‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、返信経路情報RI[u-1]を更新する(ステップS41)。
【0074】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ21‐uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u+1])20‐(u+1)に送信する(ステップS42)。
【0075】
〔返信開始処理〕
次に、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]に対して、通信装置(v[u])20‐uが返信開始処理を行う場合の処理を説明する。
【0076】
図10は、本形態の返信開始処理を説明するためのフローチャートである。以下、この図を用いて本形態の返信開始処理を説明する。
【0077】
まず、通信装置(v[0])10(図4)の第4ブロック情報更新部26a‐uが、メモリ21‐uに格納された秘密鍵x[u]を用い、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新する。なお、第4ブロック情報更新部26a‐uは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とブロック情報DB[1,u-1],...,DB[D,u-1]とを区別できないため、返信経路情報RI[u-1]が具備するすべてのブロック情報DB[1,u-1],...,DB[D,u-1]の各G[1,d,u-1],G[2,d,u-1]に対してもそれぞれ演算G[1,d,u-1]=G[1,d,u-1]・G[2,d,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各G[1,d,u-1]として当該ブロック情報DB[1,u-1],...,DB[D,u-1]を更新する。これらにより、メモリ21‐uに格納された返信経路情報RI[u-1]が更新される(ステップS51)。
【0078】
次に、削除部26b‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備するブロック情報RB[j,u-1] (j=0,...,n-1)からα[1,j,u-1],β[1,j,u-1]を削除してRB[j,u-1]=(α[0,j,u-1],β[0,j,u-1])とし、ブロック情報DB[d,u-1] (d=0,...,D)からG[3,d,u-1],G[4,d,u-1]を削除してDB[d,u-1]=(G[1,d,u-1],G[2,d,u-1])とし、メモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS52)。なお、この更新は、返信内容格納用情報RI[u-1]から以降で使用しない情報を削除する処理である。
【0079】
次に、任意値設定部26c‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr3[0,j,u]∈Zqをランダムに選択し、それをメモリ21‐uに格納する(ステップS53)。
【0080】
そして、ランダム化部26d‐uが、メモリ21‐uに格納された各要素を用い、
α[0,j,u-1]=α[0,j,u-1]r3[0,j,u]∈G, G[1,d,u-1]=G[1,d,u-1]r3[0,j,u]∈G
β[0,j,u-1]=β[0,j,u-1]r3[0,j,u]∈G, G[2,d,u-1]=G[2,d,u-1]r3[0,j,u]∈G
によってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS54)。
【0081】
次に、順序並び替え部26e‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、当該信経路情報RI[u-1]を更新する(ステップS55)。
【0082】
次に、第1任意値設定部26f‐uが、r[0,*,u],r[1,*,u]∈Zqをランダムに設定し、設定したr[0,*,u],r[1,*,u]∈Zqをメモリ21‐uに格納する(ステップS56)。
【0083】
そして、第7ブロック情報更新部26g‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ21‐uに格納されたr[0,*,u]を用い、返信メッセージをM∈Gとした場合における演算M・α[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS57)。なお、返信メッセージMは、入力部22‐uから入力された情報から生成されたものであってもよいし、予め定められたもの(例えば通信エラー情報等)であってもよい。
【0084】
また、第8ブロック情報更新部26h‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ21‐uに格納されたr[0,*,u]を用い、演算β[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS58)。
【0085】
次に、第10ブロック情報更新部26i‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ21‐uに格納されたr[1,*,u]を用い、演算α[1,*,u-1]=α[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果α[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS59)。
【0086】
また、第11ブロック情報更新部26j‐uが、メモリ21‐uに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ21‐uに格納されたr[1,*,u]を用い、演算β[1,*,u-1]=β[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果β[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ21‐uに格納された返信経路情報RI[u-1]を更新する(ステップS60)。
【0087】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ21‐uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u-1])20‐(u‐1)に送信する(ステップS61)。
【0088】
〔通信装置v[u+1](1≦u≦n-1)の返信受信処理〕
次に、通信装置v[u+1](1≦u≦n-1)から返信された返信経路情報RI[u+1] に対して、通信装置(v[u])20‐u(1≦u≦n-1)が返信受信処理を行う場合の処理を説明する。
【0089】
まず、通信装置(v[u])20‐u(図5)の受信部22‐uが、通信装置(v[u+1])20‐(u+1)から返信された返信経路情報RI[u+1]を受信し、メモリ21‐uに格納する(ステップS71)。
【0090】
なお、1≦u≦n-2の場合、ステップS71で受信される返信経路情報RI[u+1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置(v[1],...,v[c])20‐1〜cで更新され、返信を行う通信装置(v[c+1])20‐(c+1)に送信され、通信装置(v[c+1])20‐(c+1)で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置(v[c],...,v[u+1])20‐c〜(u+1)で更新され、通信装置(v[u+1])20‐(u+1)から返信された返信経路情報RI[u+1]である。
【0091】
また、u=n-1の場合、ステップS71で受信される返信経路情報RI[u+1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置(v[1],...,v[n-1])20‐1〜(n−1)で更新され、返信を行う通信装置(v[n])20‐nに送信され、通信装置(v[n])20‐nで更新され、通信装置(v[n-1])20‐(n−1)に返信された返信経路情報RI[n]である。
【0092】
次に、判定部27a‐uが、メモリ21‐uに格納されたx[u],E(u),e[y,u]を用い、(1)メモリ21‐uに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか、(2) メモリ21‐uに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]がα[0,j,u+1]=β[0,j,u+1]x[u]・E(u)∈Gを満たすかを判定する(ステップS72)。
【0093】
ここで、u≠0の場合には(2)の条件は充足されず、(1)の条件を充足するブロック情報RB[j,u+1]と通信路情報e[y,u]との組が存在する。判定部27a‐uは、1)の条件を充足するブロック情報RB[j,u+1]と通信路情報e[y,u]とを、それぞれ
e[u-1,u]={e[y,u] |α[0,j,u+1]=β[0,j,u+1]x[u]・e[y,u]∈G}
RB[++,u+1]={RB[j,u+1] |α[0,j,u+1]=β[0,j,u+1] [u]・e[y,u]∈G}
とし、RB[++,u+1]を特定するための情報inf(RB[++,u+1])と通信路情報e[u-1,u]とをメモリ21‐uに格納する(ステップS73)。
【0094】
次に、第5ブロック情報更新部27b‐uが、メモリ21‐uに格納された情報inf(RB[++,u+1])を用いてブロック情報RB[++,u+1]を特定し、メモリ21‐uに格納された秘密鍵x[u]を用い、ブロック情報RB[++,u+1]を除く返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1],β[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS74)。
【0095】
次に、第9ブロック情報更新部27c‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],β[0,*,u+1]に対し、メモリ21‐uに格納された秘密鍵x[u]を用い、演算α[0,*,u+1]/β[0,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS75)。
【0096】
また、第12ブロック情報更新部27dが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1],β[1,*,u+1]に対し、メモリ21‐uに格納された秘密鍵x[u]を用い、演算α[1,*,u+1]/β[1,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS76)。
【0097】
また、第2任意値設定部27e‐uが、r2[0,*,u],r2[1,*,u]∈Zqをランダムに選択し、選択したr2[0,*,u],r2[1,*,u]∈Zqをメモリ21‐uに格納する(ステップS77)。
【0098】
そして、以上のように更新されメモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],α[1,*,u+1]に対し、メモリ21‐uに格納されたr2[0,*,u]を用いて演算α[0,*,u+1]・α[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS78)。
【0099】
次に、第14ブロック情報更新部27g‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[0,*,u+1],β[1,*,u+1]に対し、メモリ21‐uに格納されたr2[0,*,u]を用いて演算β[0,*,u+1]・β[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS79)。
【0100】
また、第15ブロック情報更新部27h‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1]に対し、メモリ21‐uに格納されたr2[1,*,u]を用いて演算α[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS80)。
【0101】
また、第16ブロック情報更新部27i‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[1,*,u+1]に対し、メモリ21‐uに格納されたr2[1,*,u]を用いて演算β[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなβ[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS81)。
【0102】
次に、任意値設定部27j‐uが、n個の通信装置v[j](j=1,...,n-1)にそれぞれ対応するr4[0,j,u]∈Zqをランダムに選択し、それをメモリ21‐uに格納する(ステップS82)。
【0103】
そして、ランダム化部27k‐uが、メモリ21‐uに格納された各要素を用い、
α[0,j,u+1]=α[0,j,u+1]r4[0,j,u]∈G,
G[1,d,u+1]=G[1,d,u+1]r4[0,j,u]∈G,
β[0,j,u+1]=β[0,j,u+1]r4[0,j,u]∈G,
G[2,d,u+1]=G[2,d,u+1]r4[0,j,u]∈G
によってメモリ21‐uに格納された返信経路情報RI[u+1]を更新する(ステップS83)。
【0104】
次に、順序並び替え部26e‐uが、メモリ21‐uに格納された返信経路情報RI[u+1]を構成するRB[j,u+1],DB[d,u+1]の順序をランダムに並び替え、当該信経路情報RI[u+1]を更新する(ステップS84)。
【0105】
そして、以上の更新がなされた返信経路情報RI[u+1]は、返信経路情報RI[u]としてメモリ21+uに格納される。その後、返信経路情報RI[u]は送信部23a‐uに送られ、送信部23a‐uは、返信経路情報RI[u]を通信装置(v[u-1])20‐(u‐1)に送信する(ステップS85)。
【0106】
〔通信装置v[1]の返信受信処理〕
図11及び図12は、信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])10が返信受信処理を行う場合の処理を説明するためのフローチャートである。以下、これらの図を用い、通信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])10が返信受信処理を行う場合の処理を説明する。
【0107】
まず、通信装置(v[0])10(図2)の受信部13bが、通信装置(v[1])20‐1から返信された返信経路情報RI[1]を受信し、メモリ11に格納する(ステップS71)。
【0108】
なお、ステップS71で受信される返信経路情報RI[1]は、通信装置(v[0])10から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置(v[1],...,v[c])20‐1〜cで更新され、返信を行う通信装置(v[c+1])20‐(c+1)に送信され、通信装置(v[c+1])20‐(c+1)で更新され、通信装置v[c]に返信され、v[c],...,v[1]の順序で、通信装置(v[c],...,v[1])20‐c〜1で更新され、通信装置(v[1])20‐1から返信された返信経路情報RI[1]である。
【0109】
次に、判定部15tが、メモリ11に格納されたx[0],E(0),e[y,0]を用い、(1)メモリ11に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]と、何れかの通信路情報e[y,0]との組合せに対してα[0,j, 1]=β[0,j,1]e[y,0]∈Gを満たすか、(2) メモリ11に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]がα[0,j,1]=β[0,j,1]x[0]・E(u)∈Gを満たすかを判定する(ステップS72)。
【0110】
ここで、通信装置v[1]の場合には(1)の条件は充足されず、(2)の条件が充足される。この場合、返信メッセージ復号部15uが、メモリ11に格納された返信経路情報RI[1]が具備する返信内容格納用情報RB[*,1]のα[0,*,1],β[0,*,1]に対し、演算α[0,*,1]/β[0,*,1]x[0]∈Gを行い、その演算結果を返信メッセージM∈Gとしてメモリ11に格納する(ステップS86)。
【0111】
〔本形態の特徴〕
以上説明した通り、本形態の返信経路情報RI[0]の情報サイズはO(n)である。
【0112】
また、本形態では、通信装置v[0]から送信された返信経路情報RI[0]がv[1],...,v[c]と更新され、返信開始処理を行う任意の通信装置v[c+1]に届けられる。まず、通信装置v[c+1]は、その直前の通信装置v[c]への通信路を知っているため通信装置v[c]への返信が可能である。また、以上の処理を追っていけば分かるように、通信装置v[c],...,v[1]は、それぞれステップS72の処理を行うことにより、それぞれ、次の返信先である通信装置への通信路情報を得ることができるが、当該匿名通信経路上の他の通信装置への通信路情報を得ることはできない。これは、返信経路情報を構成する各ブロック情報RBに匿名通信経路上の各通信路情報を暗号化して格納し、送信時のステップS33で次の送信先への通信路情報が暗号化されたブロック情報RB[+,u-1]に対して特殊な更新処理を行い、ステップS35,S36においてRB[+,u-1]以外の各ブロック情報RBに対して更新演算を行い、返信時のステップS74で更新復元処理を実行したことによる。つまり、上述の処理を逐一追っていけば明らかなように、このような処理を行った結果、各通信装置がステップS72でα[0,j,u+1]=β[0,j,u+1]x[u]・e[y,u]∈Gを満たすブロック情報であると検出するのは、それぞれ次の返信先の通信装置への通信路を特定する通信路情報を暗号化したブロック情報のみとなる。そして、巡回群Gでの離散対数問題が困難であり、各通信装置が他の通信装置の秘密鍵を知らないとすると、各通信装置は、自らの返信先以外の通信装置への通信路を特定する通信路情報を得ることはできない。
【0113】
以上より、本形態では、少ない情報サイズの返信経路情報を用い、送信経路上の任意の通信装置において匿名通信による返信を行うことができる。
【0114】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、各通信装置が相互に独立である場合を例示したが、少なくとも一部の通信装置が同一の管理者に管理される構成であってもよい。
【0115】
また、本形態では、各通信装置20‐uが図3〜図5に示したすべての機能構成を具備することとした。しかし、少なくとも一部の通信装置20‐uが図3〜図5に示した機能構成の一部のみを具備する構成であってもよい。例えば、送信先の通信装置v[n]が通信装置20‐nに固定されるのであれば、その通信装置20‐nは、図3及び図5に示した機能構成を具備しなくてもよい。
【0116】
また、本形態では、通信装置10も図3〜図5のすべての機能構成を具備し、各通信装置20‐uも通信装置10の機能構成を具備することとした。しかし、通信装置10が図3〜図5の機能構成を具備しないか、それらの一部の機能構成を具備する構成であってもよい。また、各通信装置20‐uが通信装置10の機能構成を具備しないか、それらの一部の機能構成を具備してもよい。さらには、一部の通信装置20‐uのみが、通信装置10の少なくとも一部の機能構成をさらに具備する構成であってもよい。
【0117】
また、返信メッセージMを暗号化する必要がない場合、ステップS12でr[0,*,0]∈Zqをランダムに選択する処理、ステップS25,S26の処理、ステップ28において返信経路情報RI[0]にRB[*,0]を付加する処理、ステップS39の処理、ステップS56〜S60の処理、ステップS75〜S81の処理等の返信内容格納用情報に関する処理や、それらの処理部を省略してもよい。
【0118】
また、安全性は低下するが、ステップS27、ステップS54、ステップS83等が具備するダミーのブロック情報に関する処理や、それらの処理部を省略してもよい。また、ステップS28、ステップS41、ステップS55、ステップS84等のブロック情報の並び替え処理や、それらの処理部を省略してもよく、ステップS37、ステップS38、ステップS40、ステップS53、ステップS54、ステップS82、ステップS83等のランダム化処理や、それらの処理部を省略してもよい。
【0119】
さらに、ステップS52の処理は、返信内容格納用情報からそれ以降使用しない情報を削除する処理であるが、ステップS52の処理やその処理部を省略してもよい。
【0120】
また、本形態では、匿名通信システムを構成する通信装置v[0]が返信経路情報生成装置である場合を例示したが、匿名通信システムを構成しないその他の装置(例えば、信頼できる第三者装置)が返信経路情報生成装置であってもよい。この場合、返信経路情報生成装置が返信経路情報を通信装置v[0]に送り、通信装置v[0]が当該返信経路情報を通信装置v[1]に送信する。この際、通信装置v[0]が返信経路情報をランダム化してから通信装置v[1]に送信してもよい。
【0121】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0122】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0123】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD(Digital Versatile Disc)、DVD−RAM(Random Access Memory)、CD−ROM(Compact Disc Read Only Memory)、CD−R(Recordable)/RW(ReWritable)等を、光磁気記録媒体として、MO(Magneto-Optical disc)等を、半導体メモリとしてEEP−ROM(Electronically Erasable and Programmable-Read Only Memory)等を用いることができる。
【0124】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0125】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0126】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0127】
本発明は、例えば、通信経路の匿名性が要求される電子投票、電子入札等の分野に利用できる。
【図面の簡単な説明】
【0128】
【図1】図1(a)は、本形体の匿名通信システムの全体構成を示した図である。図1(b)は、本形態の通信装置(v[0])のハードウェア構成を例示したブロック図である。
【図2】図2は、本形態の通信装置の機能構成を示したブロック図である。
【図3】図3は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])の機能構成を示したブロック図である。
【図4】図4は、通信装置v[u-1](u=1,...,n)から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置(v[u])の機能構成を示したブロック図である。
【図5】図5は、通信装置v[u+1](0≦u≦n-1)から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置(v[u])(0≦u≦n-1)の機能構成を示したブロック図である。
【図6】図6は、本形態の送信開始処理を説明するためのフローチャートである。
【図7】図7は、本形態の送信開始処理を説明するためのフローチャートである。
【図8】図8は、本形態の送信開始処理を説明するためのフローチャートである。
【図9】図9は、本形態の送信開始処理を説明するためのフローチャートである。
【図10】図10は、本形態の返信開始処理を説明するためのフローチャートである。
【図11】図11は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【図12】図12は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置(v[0])が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【符号の説明】
【0129】
1 通信システム
【特許請求の範囲】
【請求項1】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の返信経路情報を生成する返信経路情報生成装置であって、
通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f]を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[f]∈Gとした場合における、通信路情報e[h-1, h]と固有情報E[0]と公開鍵y[f]∈Gとが少なくとも格納されたメモリと、
少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、設定した任意の整数r[0,j,0],r[1,j,0]を出力する任意値設定手段と、
演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]を出力する第1演算手段と、
演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第2演算手段と、
演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第3演算手段と、
演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第4演算手段と、
演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第5演算手段と、
演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第6演算手段と、
演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第7演算手段と、
演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第8演算手段と、
m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]を出力する第9演算手段と、
m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第10演算手段と、
m=2,...,n-1のそれぞれについて、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]を出力する第11演算手段と、
m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第12演算手段と、
4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成し、当該返信経路情報RI[0]を出力する返信経路情報生成手段と、
を有することを特徴とする返信経路情報生成装置。
【請求項2】
請求項1に記載の返信経路情報生成装置であって、
上記返信経路情報RI[0]を通信装置v[1]に送信する送信手段をさらに有し、
上記通信装置v[0]として機能する、
ことを特徴とする返信経路情報生成装置。
【請求項3】
請求項1又は2に記載の返信経路情報生成装置であって、
上記任意値設定手段は、さらに、任意の整数r[0,*,0]を設定し、設定した任意の整数r[0,*,0]を出力する手段であり、
演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]を出力する第13演算手段と、
演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]を出力する第14演算手段と、さらに備え、
上記返信経路情報生成手段は、2つの演算結果α[0,*,0], β[0,*,0]を含む返信内容格納用情報RB[*,0]をさらに含む返信経路情報RI[0]を生成する手段である、
ことを特徴とする返信経路情報生成装置。
【請求項4】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の何れかの通信装置v[u](u=1,...,n)として機能する通信装置であって、
少なくとも、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報e[y,u]と、整数である当該通信装置v[u]の秘密鍵x[u]とを格納するメモリと、
Gを巡回群とし、巡回群Gの4つの元α[0,j,u-1], β[0,j,u-1], α[1,j,u-1], β[1,j,u-1]を含む情報をそれぞれブロック情報RB[j,u-1](j=0,...,n-1)とし、n個のブロック情報RB[0,u-1],...,RB[n-1,u-1]を含む情報を返信経路情報RI[u-1]とした場合における、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信する第1受信手段と、
上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とするブロック情報選択手段と、
上記ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果を上記ブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第1ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第2ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[1,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第3ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、少なくとも第1〜3ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する第1送信手段と、
通信装置v[u]が返信を行う場合に、上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第4ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、少なくとも第4ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第2送信手段と、
1≦u≦n-1である場合に、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第2受信手段と、
上記返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]として出力する判定手段と、
上記α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く上記返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第5ブロック情報更新手段と、
少なくとも第5ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第3送信手段と、を有し、
u=1の場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項5】
請求項4に記載の通信装置であって、
上記第1受信手段は、巡回群Gの2つの元α[0,*,u-1], β[0,*,u-1]を含む返信内容格納用情報RB[*,u-1]をさらに含む返信経路情報RI[u-1]を受信する手段であり、
通信装置v[u]が返信を行わない場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1], β[0,*,u-1]に対して演算α[0,*,u-1]・β[0,*,u-1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第6ブロック情報更新手段をさらに備え、
上記第1送信手段は、少なくとも第1〜3,6ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する手段であり、
通信装置v[u]が返信を行う場合に、任意の整数r[0,*,u]を設定し、設定した任意の整数r[0,*,u]を出力する第1任意値設定手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、返信メッセージをM∈Gとした場合における演算M・α[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第7ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、演算β[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第8ブロック情報更新手段と、をさらに備え、
上記第2送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第1,4,7,8ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第2受信手段は、1≦u≦n-1である場合に、巡回群Gの2つの元α[0,*,u+1],β[0,*,u+1]を含む返信内容格納用情報RB[*,u+1]をさらに含む返信経路情報RI[u+1]を受信する手段であり、
上記第2受信手段で受信された上記返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],β[0,*,u+1]に対し、演算α[0,*,u+1]/β[0,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第9ブロック情報更新手段をさらに備え、
上記第3送信手段は、少なくとも第5,9ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
u=1の場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4,7,8ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5,9ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4,7,8ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項6】
請求項5に記載の通信装置であって、
上記第1任意値設定手段は、通信装置v[u]が返信を行う場合に、さらに任意の整数r[1,*,u]を設定し、設定した任意の整数r[1,*,u]を出力する手段であり、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、演算α[1,*,u-1]=α[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果α[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、追加後の返信内容格納用情報RB[*,u-1]を含む返信経路情報RI[u-1]を出力する第10ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、演算β[1,*,u-1]=β[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果β[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、追加後の返信内容格納用情報RB[*,u-1]を含む返信経路情報RI[u-1]を出力する第11ブロック情報更新手段と、をさらに備え、
上記第2送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第2受信手段は、1≦u≦n-1である場合に、巡回群Gの4つの元α[0,*,u+1],β[0,*,u+1],α[1,*,u+1],β[1,*,u+1]を含む返信内容格納用情報RB[*,u+1]を含む返信経路情報RI[u+1]を受信する手段であり、
上記第2受信手段で受信された上記返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1],β[1,*,u+1]に対し、演算α[1,*,u+1]/β[1,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第12ブロック情報更新手段と、
任意の整数r2[0,*,u],r2[1,*,u]を設定し、設定した任意の整数r2[0,*,u],r2[1,*,u]を出力する第2任意値設定手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],α[1,*,u+1]に対し、演算α[0,*,u+1]・α[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第13ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[0,*,u+1],β[1,*,u+1]に対し、演算β[0,*,u+1]・β[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第14ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1]に対し、演算α[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第15ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[1,*,u+1]に対し、演算β[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなβ[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第16ブロック情報更新手段と、をさらに備え、
上記第3送信手段は、少なくとも第5,9,12〜16ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5,9,12〜16ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜第3,第6ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項7】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の通信装置v[0]として機能する通信装置であって、
少なくとも、通信装置v[0]の秘密鍵x[0]と固有情報E[0]とが格納されたメモリと、
請求項5又は6に記載の通信装置v[1]として機能する通信装置から返信された返信経路情報RI[1]を受信する受信手段と、
上記受信手段で受信された上記返信経路情報RI[1]が具備する、巡回群Gの元α[0,j,1], β[0,j,1]を含むブロック情報RB[j,1](j=0,...,n-1)に、α[0,j,1]=β[0,j,1]x[0]・E(0)∈Gを満たすブロック情報RB[j,1]が存在するか否かを判定する判定手段と、
上記判定手段でα[0,j,1]=β[0,j,1]x[0]・E(0)∈Gを満たすブロック情報RB[j,1]が存在すると判定された場合、上記受信手段で受信された上記返信経路情報RI[1]が具備する返信内容格納用情報RB[*,1]のα[0,*,1],β[0,*,1]に対し、演算α[0,*,1]/β[0,*,1]x[0]∈Gを行い、その演算結果を返信メッセージM∈Gとして出力する返信メッセージ復号手段と、
を有することを特徴とする通信装置。
【請求項8】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信を行う通信装置v[0]の匿名通信方法であって、
通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f](f=0,...,n)を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[j]∈Gとした場合における、少なくとも、通信路情報e[h-1, h]と固有情報E[0]と公開鍵y[f]∈Gとがメモリに格納されており、
少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、設定した任意の整数r[0,j,0],r[1,j,0]を出力する任意値設定過程と、
第1演算手段が、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]を出力する第1演算過程と、
第2演算手段が、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第2演算過程と、
第3演算手段が、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第3演算過程と、
第4演算手段が、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第4演算過程と、
第5演算手段が、演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第5演算過程と、
第6演算手段が、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第6演算過程と、
第7演算手段が、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第7演算過程と、
第8演算手段が、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第8演算過程と、
第9演算手段が、m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]を出力する第9演算過程と、
第10演算手段が、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第10演算過程と、
第11演算手段が、m=2,...,n-1のそれぞれについて、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]を出力する第11演算過程と、
第12演算手段が、m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第12演算過程と、
返信経路情報生成手段が、4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成し、当該返信経路情報RI[0]を出力する返信経路情報生成過程と、
送信手段が、上記返信経路情報RI[0]を通信装置v[1]に送信する送信過程と、
を実行することを特徴とする匿名通信方法。
【請求項9】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信を行う何れかの通信装置v[u](u=1,...,n)の匿名通信方法であって、
少なくとも、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報e[y,u]と、整数である当該通信装置v[u]の秘密鍵x[u]とをメモリに格納しておき、
第1受信手段が、Gを巡回群とし、巡回群Gの4つの元α[0,j,u-1], β[0,j,u-1], α[1,j,u-1], β[1,j,u-1]を含む情報をそれぞれブロック情報RB[j,u-1](j=0,...,n-1)とし、n個のブロック情報RB[0,u-1],...,RB[n-1,u-1]を含む情報を返信経路情報RI[u-1]とした場合における、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信する第1受信過程と、
ブロック情報選択手段が、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とするブロック情報選択過程と、
第1ブロック情報更新手段が、上記ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果を上記ブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第1ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第2ブロック情報更新手段が、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第2ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第3ブロック情報更新手段が、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第3ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第1送信手段が、少なくとも第1〜3ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する第1送信過程と、
通信装置v[u]が返信を行う場合に、第4ブロック情報更新手段が、上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1],β[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第4ブロック情報更新過程と、
通信装置v[u]が返信を行う場合に、第2送信手段が、少なくとも第4ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第2送信過程と、
1≦u≦n-1である場合に、第2受信手段が、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第2受信過程と、
判定手段が、上記返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]として出力する通信路情報復号過程と、
第5ブロック情報更新手段が、上記α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く上記返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第5ブロック情報更新過程と、
第3送信手段が、少なくとも第5ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第3送信過程と、を有し、
u=1の場合、上記第1受信過程で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信過程で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3ブロック情報更新過程で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信過程で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3ブロック情報更新過程で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4ブロック情報更新過程で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5ブロック情報更新過程で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信過程で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3ブロック情報更新過程で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4ブロック情報更新過程で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする匿名通信方法。
【請求項10】
請求項1から3の何れかに記載の返信経路情報生成装置、又は、請求項4から7の何れかに記載の通信装置としてコンピュータを機能させるためのプログラム。
【請求項11】
請求項10に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項1】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の返信経路情報を生成する返信経路情報生成装置であって、
通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f]を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[f]∈Gとした場合における、通信路情報e[h-1, h]と固有情報E[0]と公開鍵y[f]∈Gとが少なくとも格納されたメモリと、
少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、設定した任意の整数r[0,j,0],r[1,j,0]を出力する任意値設定手段と、
演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]を出力する第1演算手段と、
演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第2演算手段と、
演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第3演算手段と、
演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第4演算手段と、
演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第5演算手段と、
演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第6演算手段と、
演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第7演算手段と、
演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第8演算手段と、
m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]を出力する第9演算手段と、
m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第10演算手段と、
m=2,...,n-1のそれぞれについて、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]を出力する第11演算手段と、
m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第12演算手段と、
4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成し、当該返信経路情報RI[0]を出力する返信経路情報生成手段と、
を有することを特徴とする返信経路情報生成装置。
【請求項2】
請求項1に記載の返信経路情報生成装置であって、
上記返信経路情報RI[0]を通信装置v[1]に送信する送信手段をさらに有し、
上記通信装置v[0]として機能する、
ことを特徴とする返信経路情報生成装置。
【請求項3】
請求項1又は2に記載の返信経路情報生成装置であって、
上記任意値設定手段は、さらに、任意の整数r[0,*,0]を設定し、設定した任意の整数r[0,*,0]を出力する手段であり、
演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]を出力する第13演算手段と、
演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]を出力する第14演算手段と、さらに備え、
上記返信経路情報生成手段は、2つの演算結果α[0,*,0], β[0,*,0]を含む返信内容格納用情報RB[*,0]をさらに含む返信経路情報RI[0]を生成する手段である、
ことを特徴とする返信経路情報生成装置。
【請求項4】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の何れかの通信装置v[u](u=1,...,n)として機能する通信装置であって、
少なくとも、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報e[y,u]と、整数である当該通信装置v[u]の秘密鍵x[u]とを格納するメモリと、
Gを巡回群とし、巡回群Gの4つの元α[0,j,u-1], β[0,j,u-1], α[1,j,u-1], β[1,j,u-1]を含む情報をそれぞれブロック情報RB[j,u-1](j=0,...,n-1)とし、n個のブロック情報RB[0,u-1],...,RB[n-1,u-1]を含む情報を返信経路情報RI[u-1]とした場合における、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信する第1受信手段と、
上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とするブロック情報選択手段と、
上記ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果を上記ブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第1ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第2ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[1,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第3ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、少なくとも第1〜3ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する第1送信手段と、
通信装置v[u]が返信を行う場合に、上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第4ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、少なくとも第4ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第2送信手段と、
1≦u≦n-1である場合に、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第2受信手段と、
上記返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]として出力する判定手段と、
上記α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く上記返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第5ブロック情報更新手段と、
少なくとも第5ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第3送信手段と、を有し、
u=1の場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項5】
請求項4に記載の通信装置であって、
上記第1受信手段は、巡回群Gの2つの元α[0,*,u-1], β[0,*,u-1]を含む返信内容格納用情報RB[*,u-1]をさらに含む返信経路情報RI[u-1]を受信する手段であり、
通信装置v[u]が返信を行わない場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1], β[0,*,u-1]に対して演算α[0,*,u-1]・β[0,*,u-1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第6ブロック情報更新手段をさらに備え、
上記第1送信手段は、少なくとも第1〜3,6ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する手段であり、
通信装置v[u]が返信を行う場合に、任意の整数r[0,*,u]を設定し、設定した任意の整数r[0,*,u]を出力する第1任意値設定手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、返信メッセージをM∈Gとした場合における演算M・α[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第7ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、演算β[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第8ブロック情報更新手段と、をさらに備え、
上記第2送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第1,4,7,8ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第2受信手段は、1≦u≦n-1である場合に、巡回群Gの2つの元α[0,*,u+1],β[0,*,u+1]を含む返信内容格納用情報RB[*,u+1]をさらに含む返信経路情報RI[u+1]を受信する手段であり、
上記第2受信手段で受信された上記返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],β[0,*,u+1]に対し、演算α[0,*,u+1]/β[0,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第9ブロック情報更新手段をさらに備え、
上記第3送信手段は、少なくとも第5,9ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
u=1の場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信手段で受信される上記返信経路情報RI[u-1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4,7,8ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5,9ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4,7,8ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項6】
請求項5に記載の通信装置であって、
上記第1任意値設定手段は、通信装置v[u]が返信を行う場合に、さらに任意の整数r[1,*,u]を設定し、設定した任意の整数r[1,*,u]を出力する手段であり、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、演算α[1,*,u-1]=α[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果α[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、追加後の返信内容格納用情報RB[*,u-1]を含む返信経路情報RI[u-1]を出力する第10ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、演算β[1,*,u-1]=β[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果β[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、追加後の返信内容格納用情報RB[*,u-1]を含む返信経路情報RI[u-1]を出力する第11ブロック情報更新手段と、をさらに備え、
上記第2送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第2受信手段は、1≦u≦n-1である場合に、巡回群Gの4つの元α[0,*,u+1],β[0,*,u+1],α[1,*,u+1],β[1,*,u+1]を含む返信内容格納用情報RB[*,u+1]を含む返信経路情報RI[u+1]を受信する手段であり、
上記第2受信手段で受信された上記返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1],β[1,*,u+1]に対し、演算α[1,*,u+1]/β[1,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第12ブロック情報更新手段と、
任意の整数r2[0,*,u],r2[1,*,u]を設定し、設定した任意の整数r2[0,*,u],r2[1,*,u]を出力する第2任意値設定手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],α[1,*,u+1]に対し、演算α[0,*,u+1]・α[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第13ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[0,*,u+1],β[1,*,u+1]に対し、演算β[0,*,u+1]・β[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第14ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1]に対し、演算α[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第15ブロック情報更新手段と、
上記第5,9,12ブロック情報更新手段で更新された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[1,*,u+1]に対し、演算β[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなβ[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第16ブロック情報更新手段と、をさらに備え、
上記第3送信手段は、少なくとも第5,9,12〜16ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
1≦u≦n-2の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3,6ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5,9,12〜16ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信手段で受信される上記返信経路情報RI[u+1]は、請求項3に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜第3,第6ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4,7,8,10,11ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項7】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の通信装置v[0]として機能する通信装置であって、
少なくとも、通信装置v[0]の秘密鍵x[0]と固有情報E[0]とが格納されたメモリと、
請求項5又は6に記載の通信装置v[1]として機能する通信装置から返信された返信経路情報RI[1]を受信する受信手段と、
上記受信手段で受信された上記返信経路情報RI[1]が具備する、巡回群Gの元α[0,j,1], β[0,j,1]を含むブロック情報RB[j,1](j=0,...,n-1)に、α[0,j,1]=β[0,j,1]x[0]・E(0)∈Gを満たすブロック情報RB[j,1]が存在するか否かを判定する判定手段と、
上記判定手段でα[0,j,1]=β[0,j,1]x[0]・E(0)∈Gを満たすブロック情報RB[j,1]が存在すると判定された場合、上記受信手段で受信された上記返信経路情報RI[1]が具備する返信内容格納用情報RB[*,1]のα[0,*,1],β[0,*,1]に対し、演算α[0,*,1]/β[0,*,1]x[0]∈Gを行い、その演算結果を返信メッセージM∈Gとして出力する返信メッセージ復号手段と、
を有することを特徴とする通信装置。
【請求項8】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信を行う通信装置v[0]の匿名通信方法であって、
通信装置v[h-1](h=1,...,n)と通信装置v[h]との間の通信路を特定するための通信路情報をe[h-1, h]とし、各通信装置v[f](f=0,...,n)に固有な固有情報をE[f]とし、Gを巡回群とし、gを巡回群Gの生成元とし、x[f](f=0,...,n)を整数である各通信装置v[f]の秘密鍵x[f]とし、y[f]を各秘密鍵x[f]にそれぞれ対応する公開鍵y[f]=gx[j]∈Gとした場合における、少なくとも、通信路情報e[h-1, h]と固有情報E[0]と公開鍵y[f]∈Gとがメモリに格納されており、
少なくとも、n個の通信装置v[j](j=0,...,n-1)にそれぞれ対応する任意の整数r[0,j,0],r[1,j,0]を設定し、設定した任意の整数r[0,j,0],r[1,j,0]を出力する任意値設定過程と、
第1演算手段が、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]を出力する第1演算過程と、
第2演算手段が、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第2演算過程と、
第3演算手段が、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第3演算過程と、
第4演算手段が、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第4演算過程と、
第5演算手段が、演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第5演算過程と、
第6演算手段が、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第6演算過程と、
第7演算手段が、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第7演算過程と、
第8演算手段が、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第8演算過程と、
第9演算手段が、m=2,...,n-1のそれぞれについて、演算α[0,m,0]=(y[1]・...・y[m-1])r[0,m,0]・y[m](e[m-1,m]+1)・r[0,m,0]・y[m+1]r[0,m,0]∈Gを行い、それらの演算結果α[0,m,0]を出力する第9演算過程と、
第10演算手段が、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第10演算過程と、
第11演算手段が、m=2,...,n-1のそれぞれについて、演算α[1,m,0]=(y[1]・...・y[m-1]・y[m]・y[m+1])r[1,m,0]∈Gを行い、その演算結果α[1,m,0]を出力する第11演算過程と、
第12演算手段が、m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第12演算過程と、
返信経路情報生成手段が、4つの演算結果α[0,j,0], β[0,j,0], α[1,j,0], β[1,j,0](j=0,...,n-1)を含む情報をそれぞれブロック情報RB[j,0]とした場合における、n個のブロック情報RB[0,0],...,RB[n-1,0]を含む返信経路情報RI[0]を生成し、当該返信経路情報RI[0]を出力する返信経路情報生成過程と、
送信手段が、上記返信経路情報RI[0]を通信装置v[1]に送信する送信過程と、
を実行することを特徴とする匿名通信方法。
【請求項9】
通信装置v[0]から送信された情報がv[1],...,v[n-1](n≧2)の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信を行う何れかの通信装置v[u](u=1,...,n)の匿名通信方法であって、
少なくとも、通信装置v[y](yはu以外の整数)と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報e[y,u]と、整数である当該通信装置v[u]の秘密鍵x[u]とをメモリに格納しておき、
第1受信手段が、Gを巡回群とし、巡回群Gの4つの元α[0,j,u-1], β[0,j,u-1], α[1,j,u-1], β[1,j,u-1]を含む情報をそれぞれブロック情報RB[j,u-1](j=0,...,n-1)とし、n個のブロック情報RB[0,u-1],...,RB[n-1,u-1]を含む情報を返信経路情報RI[u-1]とした場合における、通信装置v[u-1]から送信された返信経路情報RI[u-1]を受信する第1受信過程と、
ブロック情報選択手段が、上記第1受信手段で受信された上記返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とするブロック情報選択過程と、
第1ブロック情報更新手段が、上記ブロック情報RB[+,u-1]のα[0,j,u-1]に対して演算α[0,j,u-1]/β[0,j,u-1]2・x[u]∈Gを行い、その演算結果を上記ブロック情報RB[+,u-1]の新たなα[0,j,u-1]としてブロック情報RB[+,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第1ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第2ブロック情報更新手段が、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]/β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第2ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第3ブロック情報更新手段が、上記ブロック情報RB[+,u-1]を除く上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[1,j,u-1],β[0,j,u-1]に対してそれぞれ演算α[1,j,u-1]/β[1,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[1,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第3ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第1送信手段が、少なくとも第1〜3ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する第1送信過程と、
通信装置v[u]が返信を行う場合に、第4ブロック情報更新手段が、上記返信経路情報RI[u-1]が具備するブロック情報RB[0,u-1],...,RB[n-1,u-1]の各α[0,j,u-1]に対してそれぞれ演算α[0,j,u-1]・β[0,j,u-1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1],β[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第4ブロック情報更新過程と、
通信装置v[u]が返信を行う場合に、第2送信手段が、少なくとも第4ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第2送信過程と、
1≦u≦n-1である場合に、第2受信手段が、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第2受信過程と、
判定手段が、上記返信経路情報RI[u+1]が含む何れかのブロック情報RB[0,u+1],...,RB[n-1,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか否かを判定し、α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たした通信路情報e[y,u]を通信路情報e[u-1,u]として出力する通信路情報復号過程と、
第5ブロック情報更新手段が、上記α[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たしたブロック情報を除く上記返信経路情報RI[u+1]が含むブロック情報RB[0,u+1],...,RB[n-1,u+1]の各α[0,j,u+1],β[0,j,u+1]に対してそれぞれ演算α[0,j,u+1]・β[0,j,u+1]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u+1]として当該ブロック情報RB[0,u+1],...,RB[n-1,u+1]を更新し、それによって返信経路情報RI[u+1]を更新する第5ブロック情報更新過程と、
第3送信手段が、少なくとも第5ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第3送信過程と、を有し、
u=1の場合、上記第1受信過程で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第1受信過程で受信される上記返信経路情報RI[u-1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第1〜3ブロック情報更新過程で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第2受信過程で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c](cはu+1≦c≦n-1の整数)の順序で、通信装置v[1],...,v[c]の少なくとも各第1〜3ブロック情報更新過程で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第1,4ブロック情報更新過程で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第5ブロック情報更新過程で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第2受信過程で受信される上記返信経路情報RI[u+1]は、請求項1から3の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第1〜3ブロック情報更新過程で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第1,4ブロック情報更新過程で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする匿名通信方法。
【請求項10】
請求項1から3の何れかに記載の返信経路情報生成装置、又は、請求項4から7の何れかに記載の通信装置としてコンピュータを機能させるためのプログラム。
【請求項11】
請求項10に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2009−171495(P2009−171495A)
【公開日】平成21年7月30日(2009.7.30)
【国際特許分類】
【出願番号】特願2008−10178(P2008−10178)
【出願日】平成20年1月21日(2008.1.21)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成21年7月30日(2009.7.30)
【国際特許分類】
【出願日】平成20年1月21日(2008.1.21)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]