(57)【特許請求の範囲】
【請求項１】
通信装置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]を出力する第１演算手段と、
演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第２演算手段と、
演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第３演算手段と、
演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第４演算手段と、
演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第５演算手段と、
演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第６演算手段と、
演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第７演算手段と、
演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第８演算手段と、
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]を出力する第９演算手段と、
m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第１０演算手段と、
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]を出力する第１１演算手段と、
m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第１２演算手段と、
４つの演算結果α[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]に送信する送信手段をさらに有し、
上記通信装置v[0]として機能する、
ことを特徴とする返信経路情報生成装置。
【請求項３】
請求項１又は２に記載の返信経路情報生成装置であって、
上記任意値設定手段は、さらに、任意の整数r[0,*,0]を設定し、設定した任意の整数r[0,*,0]を出力する手段であり、
演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]を出力する第１３演算手段と、
演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]を出力する第１４演算手段と、さらに備え、
上記返信経路情報生成手段は、２つの演算結果α[0,*,0], β[0,*,0]を含む返信内容格納用情報RB[*,0]をさらに含む返信経路情報RI[0]を生成する手段である、
ことを特徴とする返信経路情報生成装置。
【請求項４】
通信装置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の４つの元α[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]を受信する第１受信手段と、
上記第１受信手段で受信された上記返信経路情報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]を更新する第１ブロック情報更新手段と、
通信装置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]を更新する第２ブロック情報更新手段と、
通信装置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]を更新する第３ブロック情報更新手段と、
通信装置v[u]が返信を行わない場合に、少なくとも第１〜３ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+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]を更新する第４ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、少なくとも第４ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第２送信手段と、
1≦u≦n-1である場合に、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第２受信手段と、
上記返信経路情報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]を更新する第５ブロック情報更新手段と、
少なくとも第５ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第３送信手段と、を有し、
u=1の場合、上記第１受信手段で受信される上記返信経路情報RI[u-1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第１受信手段で受信される上記返信経路情報RI[u-1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第１〜３ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置v[1],...,v[c]の少なくとも各第１〜３ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第１，４ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第５ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第１〜３ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第１，４ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項５】
請求項４に記載の通信装置であって、
上記第１受信手段は、巡回群Gの２つの元α[0,*,u-1], β[0,*,u-1]を含む返信内容格納用情報RB[*,u-1]をさらに含む返信経路情報RI[u-1]を受信する手段であり、
通信装置v[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]を更新する第６ブロック情報更新手段をさらに備え、
上記第１送信手段は、少なくとも第１〜３，６ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+1]に送信する手段であり、
通信装置v[u]が返信を行う場合に、任意の整数r[0,*,u]を設定し、設定した任意の整数r[0,*,u]を出力する第１任意値設定手段と、
通信装置v[u]が返信を行う場合に、上記第１受信手段で受信された上記返信経路情報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]を更新する第７ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第１受信手段で受信された上記返信経路情報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]を更新する第８ブロック情報更新手段と、をさらに備え、
上記第２送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第１，４，７，８ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第２受信手段は、1≦u≦n-1である場合に、巡回群Gの２つの元α[0,*,u+1],β[0,*,u+1]を含む返信内容格納用情報RB[*,u+1]をさらに含む返信経路情報RI[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]を更新する第９ブロック情報更新手段をさらに備え、
上記第３送信手段は、少なくとも第５，９ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
u=1の場合、上記第１受信手段で受信される上記返信経路情報RI[u-1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第１受信手段で受信される上記返信経路情報RI[u-1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第１〜３，６ブロック情報更新手段で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置v[1],...,v[c]の少なくとも各第１〜３，６ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第１，４，７，８ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第５，９ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第１〜３，６ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第１，４，７，８ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項６】
請求項５に記載の通信装置であって、
上記第１任意値設定手段は、通信装置v[u]が返信を行う場合に、さらに任意の整数r[1,*,u]を設定し、設定した任意の整数r[1,*,u]を出力する手段であり、
通信装置v[u]が返信を行う場合に、上記第１受信手段で受信された上記返信経路情報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]を出力する第１０ブロック情報更新手段と、
通信装置v[u]が返信を行う場合に、上記第１受信手段で受信された上記返信経路情報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]を出力する第１１ブロック情報更新手段と、をさらに備え、
上記第２送信手段は、通信装置v[u]が返信を行う場合に、少なくとも第１，４，７，８，１０，１１ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する手段であり、
上記第２受信手段は、1≦u≦n-1である場合に、巡回群Gの４つの元α[0,*,u+1],β[0,*,u+1],α[1,*,u+1],β[1,*,u+1]を含む返信内容格納用情報RB[*,u+1]を含む返信経路情報RI[u+1]を受信する手段であり、
上記第２受信手段で受信された上記返信経路情報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]を更新する第１２ブロック情報更新手段と、
任意の整数r2[0,*,u],r2[1,*,u]を設定し、設定した任意の整数r2[0,*,u],r2[1,*,u]を出力する第２任意値設定手段と、
上記第５，９，１２ブロック情報更新手段で更新された返信経路情報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]を更新する第１３ブロック情報更新手段と、
上記第５，９，１２ブロック情報更新手段で更新された返信経路情報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]を更新する第１４ブロック情報更新手段と、
上記第５，９，１２ブロック情報更新手段で更新された返信経路情報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]を更新する第１５ブロック情報更新手段と、
上記第５，９，１２ブロック情報更新手段で更新された返信経路情報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]を更新する第１６ブロック情報更新手段と、をさらに備え、
上記第３送信手段は、少なくとも第５，９，１２〜１６ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する手段であり、
1≦u≦n-2の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置v[1],...,v[c]の少なくとも各第１〜３，６ブロック情報更新手段で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第１，４，７，８，１０，１１ブロック情報更新手段で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第５，９，１２〜１６ブロック情報更新手段で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第２受信手段で受信される上記返信経路情報RI[u+1]は、請求項３に記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第１〜第３，第６ブロック情報更新手段で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第１，４，７，８，１０，１１ブロック情報更新手段で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする通信装置。
【請求項７】
通信装置v[0]から送信された情報がv[1],...,v[n-1]（n≧2）の順序で通信装置v[1],...,v[n-1]で中継されて通信装置v[n]に受信される匿名通信の通信装置v[0]として機能する通信装置であって、
少なくとも、通信装置v[0]の秘密鍵x[0]と固有情報E[0]とが格納されたメモリと、
請求項５又は６に記載の通信装置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として出力する返信メッセージ復号手段と、
を有することを特徴とする通信装置。
【請求項８】
通信装置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]を出力する任意値設定過程と、
第１演算手段が、演算α[0,0,0]=y[0]E[0]・r[0,0,0]・y[1]r[0,0,0]∈Gを行い、その演算結果α[0,0,0]を出力する第１演算過程と、
第２演算手段が、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]を出力する第２演算過程と、
第３演算手段が、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]を出力する第３演算過程と、
第４演算手段が、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]を出力する第４演算過程と、
第５演算手段が、演算α[0,1,0]=y[1](e[0,1]+1)・r[0,1,0]・y[2]r[0,1,0]∈Gを行い、その演算結果α[0,1,0]を出力する第５演算過程と、
第６演算手段が、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]を出力する第６演算過程と、
第７演算手段が、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]を出力する第７演算過程と、
第８演算手段が、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]を出力する第８演算過程と、
第９演算手段が、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]を出力する第９演算過程と、
第１０演算手段が、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]を出力する第１０演算過程と、
第１１演算手段が、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]を出力する第１１演算過程と、
第１２演算手段が、m=2,...,n-1のそれぞれについて、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]を出力する第１２演算過程と、
返信経路情報生成手段が、４つの演算結果α[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]に送信する送信過程と、
を実行することを特徴とする匿名通信方法。
【請求項９】
通信装置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の４つの元α[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]を受信する第１受信過程と、
ブロック情報選択手段が、上記第１受信手段で受信された上記返信経路情報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]を更新する第１ブロック情報更新過程と、
通信装置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]を更新する第２ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第３ブロック情報更新手段が、上記ブロック情報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]を更新する第３ブロック情報更新過程と、
通信装置v[u]が返信を行わない場合に、第１送信手段が、少なくとも第１〜３ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u+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]x[u]∈Gを行い、これらの各演算結果を新たな当該各α[0,j,u-1],β[0,j,u-1]として当該ブロック情報RB[0,u-1],...,RB[n-1,u-1]を更新し、それによって返信経路情報RI[u-1]を更新する第４ブロック情報更新過程と、
通信装置v[u]が返信を行う場合に、第２送信手段が、少なくとも第４ブロック情報更新手段で更新された返信経路情報RI[u-1]を、返信経路情報RI[u]として通信装置v[u-1]に返信する第２送信過程と、
1≦u≦n-1である場合に、第２受信手段が、通信装置v[u+1]から返信された返信経路情報RI[u+1]を受信する第２受信過程と、
判定手段が、上記返信経路情報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]を更新する第５ブロック情報更新過程と、
第３送信手段が、少なくとも第５ブロック情報更新手段で更新された返信経路情報RI[u+1]を返信経路情報RI[u]として、通信路情報e[u-1,u]によって特定される通信路に対して送信する第３送信過程と、を有し、
u=1の場合、上記第１受信過程で受信される上記返信経路情報RI[u-1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]であり、
u≧2場合、上記第１受信過程で受信される上記返信経路情報RI[u-1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置v[1],...,v[u-1]の少なくとも各第１〜３ブロック情報更新過程で更新され、通信装置v[u-1]から送信された返信経路情報RI[u-1]であり、
1≦u≦n-2の場合、上記第２受信過程で受信される上記返信経路情報RI[u+1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置v[1],...,v[c]の少なくとも各第１〜３ブロック情報更新過程で更新され、返信を行う通信装置v[c+1]に送信され、通信装置v[c+1]の少なくとも第１，４ブロック情報更新過程で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置v[c],...,v[u+1]の少なくとも各第５ブロック情報更新過程で更新され、通信装置v[u+1]から返信された返信経路情報RI[u+1]であり、
u=n-1の場合、上記第２受信過程で受信される上記返信経路情報RI[u+1]は、請求項１から３の何れかに記載の返信経路情報生成装置で生成され、通信装置v[0]から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置v[1],...,v[n-1]の少なくとも各第１〜３ブロック情報更新過程で更新され、返信を行う通信装置v[n]に送信され、通信装置v[n]の少なくとも第１，４ブロック情報更新過程で更新され、通信装置v[n-1]に返信された返信経路情報RI[n]である、
ことを特徴とする匿名通信方法。
【請求項１０】
請求項１から３の何れかに記載の返信経路情報生成装置、又は、請求項４から７の何れかに記載の通信装置としてコンピュータを機能させるためのプログラム。
【請求項１１】
請求項１０に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の独立した通信装置が協調して情報の転送を行う通信技術において、情報の中継を行う各通信装置に対して通信経路情報を隠蔽する匿名通信技術に関し、特に、返信が可能な匿名通信技術に関する。
【背景技術】
【０００２】
複数の独立した通信装置が協調して情報の転送を行う形態の通信サービスを行う場合において、情報の中継を行う通信装置に対して通信経路情報を隠蔽する暗号通信技術がある。例えば電子メールの送信サービスのように、送信元の通信装置から送信された情報が複数の独立な通信装置で繰り返し中継されて送信先の通信装置に届けられる通信サービスにおいて、情報の中継に必要のない通信経路情報（送信元や送信先の通信装置など）を情報の中継を行う各通信装置に隠蔽する暗号通信技術である。このような暗号通信技術は、一般に匿名通信と呼ばれ、その実現方法としてオニオンルーティングやその改良方式等さまざまな方式が提案されている。
【０００３】
また、そのような匿名通信において、情報を中継する任意の通信装置又は送信先の通信装置から返信を行うことができれば、情報を中継する任意の通信装置から送信元の通信装置への通信エラー情報の返信や、送信先の通信装置から送信元の通信装置への応答等が可能となる。この際、中継に必要のない通信経路情報（送信元や送信先の通信装置、どの通信に対する返信であるかなど）を隠蔽したまま返信を行うことができれば、双方向の匿名通信が実現できる。
【０００４】
以下では、通信装置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)
とする。
【０００５】
ここで各通信装置v[f]（f=0,...,n）には、それぞれe[f-1,f], e[f,f+1]以外にもいくつかの通信路が接続されており、v[f-1], v[f+1]以外の通信装置との通信も可能となっている。そのため、通信装置v[0]から送信され、１以上の通信装置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)の通信経路を構成するその他の通信路情報を知ることができないという状態にしなければならない。
【０００６】
このような双方向の匿名通信を実現する方式の一つに非特許文献１の方式がある。
【０００７】
非特許文献１の方式では、送信元の通信装置v[0]から送信先の通信装置v[n]へ情報を送信する際に、以下のような多重暗号文を返信経路情報として付加して送信する。なお、Kf(・)は通信装置v[f]で復号化可能な暗号文であり、E[0]は通信装置v[0]に固有の固有情報である。
【０００８】
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]を得ることはできない。これにより、双方向の匿名通信が実現できる。
【０００９】
しかし、非特許文献１の方式では、送信情報が送信先の通信装置v[n]に到着する前に、何れかの通信装置v[m]（m=2,...,n-1）で返信を行うことができない。なぜなら、まず通信装置v[n]が復号を行わないと、他の何れの通信装置v[m]も式(2)の多重暗号文を復号できず、通信路情報e[m-1,m]を得ることができないためである。そのため、非特許文献１の方式では、例えば、通信装置v[0]と通信装置v[n]との間の通信装置v[m]の次の通信装置v[m+1]が故障している場合に、通信装置v[m]がエラー情報を通信装置v[0]に返信することができない。
【００１０】
この問題を解決するための単純な方法は、各通信装置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)と大きくなってしまう。
このような問題を解決できる方式として非特許文献２の方式がある。
【００１１】
非特許文献２の方式では、通信装置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)となる。
【非特許文献１】D. L. Chaum, “Untraceable Electronic Mail, Return Addresses,and Digital Pseudonyms,” Communications of the ACM, Vol. 24, NO.2,pp.84-88 (1981).
【非特許文献２】H. Toriyama, N. Kunihiro, and K. Ohta: “Return Message-Receivable Anonymous Routing Scheme without Reveal of Sender ID,”SCIS2007, 3B4-6 (Jan. 2007).
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、非特許文献２の方式では、完全な匿名返信を達成することができないという問題点がある。つまり、非特許文献２の方式において不正を行おうとする通信装置v[m]は、通信路情報e[m-1,m]を暗号化する際（送信情報γ送信時）に何らかの目印となる情報δを暗号化し、それを返信経路情報に含めることができる。このように生成された返信経路情報を使って送られた返信情報が当該通信装置v[m]に届いたとき、当該通信装置v[m]は情報δを復号することができる。これにより、当該通信装置v[m]は、当該返信情報が送信情報γに対する返信であるとの情報を得ることができる。
【００１３】
本発明はこのような点に鑑みてなされたものであり、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、通信装置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]へ情報送信を行うための通信路を意味する。
【００１５】
〔返信経路情報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を行う。そして、４つの演算結果α[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）が以下の処理を実行する。
【００１６】
〔通信装置v[0]の送信処理〕
まず、通信装置v[0]が、返信経路情報RI[0]を通信装置v[1]に送信する。
【００１７】
〔各通信装置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]を更新する。
【００１８】
ここで、通信装置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]に送信する。
【００１９】
一方、通信装置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]はこの返信が可能である。
【００２０】
〔各通信装置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]からその他の通信路情報を得ることはできない。これにより、匿名通信による返信が可能となる。
【発明の効果】
【００２１】
本発明では、経路を構成する通信装置数nと同じオーダーの大きさの返信経路情報を用い、各通信装置に対し、情報の中継に必要な情報以外の情報を隠蔽しつつ、双方向の匿名通信を行うことが可能となる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００２３】
〔全体構成〕
まず、本形態の全体構成について説明する。
図１（ａ）は、本形体の匿名通信システム１の全体構成を示した図である。
図１（ａ）に示すように、本形態の匿名通信システム１は、ネットワークを通じた通信が可能なn個（n≧2）の通信装置v[f]（f=0,...,n）である通信装置１０及び通信装置２０‐１〜ｎによって構成される。
【００２４】
通信装置（v[0]）１０は、この匿名通信の送信先である通信装置（v[n]）２０‐ｎとそこまでの通信経路を設定する通信装置（「返信経路情報生成装置」に相当）であり、通信装置（v[1]〜v[n]）２０‐１〜ｎは、通信装置（v[0]）１０によって選択された装置である。すなわち、図１（ａ）では省略しているが、実際のネットワーク上には、通信装置（v[0]）１０及び通信装置（v[1]〜v[n]）２０‐１〜ｎ以外にも複数の複数の通信装置が存在する。また、本形態の各通信装置は相互に独立であり、どの通信装置が匿名通信システム１を構成する通信装置であるかを知るのは、その匿名通信の送信先である通信装置（v[n]）２０‐ｎとそこまでの通信経路を設定した通信装置１０のみである。
【００２５】
また、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]のアドレス（ＩＰアドレス等）を特定するための情報を例示できる。また、通信装置v[h-1]のアドレスと通信装置v[h]のアドレスとの組を特定するための情報等を通信路情報e[h-1, h]としてもよい。なお、実際には図１（ａ）に示していない通信装置も存在し、それらの通信装置と各通信装置v[f]との間の通信路や、各通信路情報e[h-1, h]が特定する通信路以外の通信装置v[f]間の通信路も存在する。
【００２６】
また、本形態では、通信装置（v[0]）１０が、匿名通信の送信先である通信装置とそこまでの通信経路を設定して匿名通信システム１が構成される場合を例示するが、ネットワーク上のその他の通信装置も、匿名通信の送信先である通信装置とそこまでの通信経路を設定でき、ネットワーク上に複数の独立した匿名通信システムが構成され得るものとする。そして、各通信装置は、複数の独立した匿名通信の送信情報や返信情報を中継することもある。
【００２７】
〔ハードウェア構成〕
図１（ｂ）は、本形態の通信装置（v[0]）１０のハードウェア構成を例示したブロック図である。
図１（ｂ）に例示するように、本形態の通信装置１０は、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、通信部１０ｃ、ＲＡＭ（Random Access Memory）１０ｄ、ＲＯＭ（Read Only Memory）１０ｅ、補助記憶装置１０ｆ及びバス１０ｇを有している。
【００２８】
この例のＣＰＵ１０ａは、制御部１０ａａ、演算部１０ａｂ及びレジスタ１０ａｃを有し、レジスタ１０ａｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、例えば、キーボード、マウス等の入力デバイスや入力端子等である。
【００２９】
また、通信部１０ｃは、ＬＡＮカードやモデム等である。また、ＲＡＭ１０ｄは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、所定のプログラムが格納されるプログラム領域１０ｄａ及び各種データが格納されるデータ領域１０ｄｂを有している。また、補助記憶装置１０ｆは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、所定のプログラムが格納されるプログラム領域１０ｆａ及び各種データが格納されるデータ領域１０ｆｂを有している。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、通信部１０ｃ、ＲＡＭ１０ｄ、ＲＯＭ１０ｅ及び補助記憶装置１０ｆを、情報のやり取りが可能なように接続する。
【００３０】
なお、その他の通信装置（v[1]〜v[n]）２０‐１〜ｎのハードウェア構成は、通信装置（v[0]）１０のハードウェア構成と同様であるため説明を省略する。
【００３１】
〔ハードウェアとソフトウェアとの協働〕
本形態の通信装置（v[0]）１０及び各通信装置（v[1]〜v[n]）２０‐１〜ｎは、上述したハードウェアに所定のプログラムが読み込まれることによって構成される。以下、このように構成される通信装置（v[0]）１０及び各通信装置（v[1]〜v[n]）２０‐１〜ｎの機能構成を説明する。
【００３２】
＜通信装置（v[0]）１０＞
図２は、本形態の通信装置１０の機能構成を示したブロック図である。
図２に示すように、本形態の通信装置１０は、メモリ１１と、入力部１２と、送信部１３ａと、受信部１３ｂと、制御部１４と、任意値設定部１５ａと、第１演算部１５ｂと、第２演算部１５ｃと、第３演算部１５ｄと、第４演算部１５ｅと、第５演算部１５ｆと、第６演算部１５ｇと、第７演算部１５ｈと、第８演算部１５ｉと、第９演算部１５ｊと、第１０演算部１５ｋと、第１１演算部１５ｍと、第１２演算部１５ｎと、第１３演算部１５ｐと、第１４演算部１５ｑと、ダミーブロック情報生成部１５ｒと、返信経路情報生成部１５ｓと、判定部１５ｔと、返信メッセージ復号部１５ｕと、を有する。
【００３３】
ここで、メモリ１１は、例えば、補助記憶装置１０ｆ、ＲＡＭ１０ｄ、レジスタ１０ａｃ、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部１２は、例えば、所定のプログラムが読み込まれたＣＰＵ１０ａの制御のもと駆動する入力部１０ｂである。また、送信部１３ａと受信部１３ｂは、所定のプログラムが読み込まれたＣＰＵ１０ａの制御のもと駆動する通信部１０ｃである。また、制御部１４と、任意値設定部１５ａと、第１演算部１５ｂと、第２演算部１５ｃと、第３演算部１５ｄと、第４演算部１５ｅと、第５演算部１５ｆと、第６演算部１５ｇと、第７演算部１５ｈと、第８演算部１５ｉと、第９演算部１５ｊと、第１０演算部１５ｋと、第１１演算部１５ｍと、第１２演算部１５ｎと、第１３演算部１５ｐと、第１４演算部１５ｑと、ダミーブロック情報生成部１５ｒと、返信経路情報生成部１５ｓと、判定部１５ｔと、返信メッセージ復号部１５ｕとは、例えば、所定のプログラムが読み込まれたＣＰＵ１０ａである。なお、通信装置（v[0]）１０は、制御部１４の制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ１１から読み込み、その処理結果をメモリ１１に格納する。
【００３４】
＜返信経路情報RI[u-1]の受信処理を行う通信装置（v[u]）２０‐ｕ＞
図３は、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置（v[u]）２０‐ｕの機能構成を示したブロック図である。
図３に示すように、当該通信装置（v[u]）２０‐ｕは、メモリ２１‐ｕと、入力部２２‐ｕと、送信部２３ａ‐ｕ（「第１送信手段」及び「第２送信手段」に相当）と、受信部２３ｂ‐ｕ（「第１受信手段」及び「第２受信手段」に相当）と、制御部２４‐ｕと、ブロック情報選択部２５ａ‐ｕと、第１ブロック情報更新部２５ｂ‐ｕと、第２ブロック情報更新部２５ｃ‐ｕと、第３ブロック情報更新部２５ｄ‐ｕと、任意値設定部２５ｅ‐ｕと、ランダム化部２５ｆ‐ｕ，２５ｈ‐ｕと、第６ブロック情報更新部２５ｇ‐ｕと、順序入れ替え部２５ｉ‐ｕと、を有する。
【００３５】
ここで、メモリ２１‐ｕは、例えば、補助記憶装置、ＲＡＭ、レジスタ、キャッシュメモリ、その他ビット情報を物理的に保持することが可能なデバイス、又は、これらの少なくとも一部を組み合わせることによって構成される記憶領域である。また、入力部２２‐ｕは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するキーボード等の入力部である。また、送信部２３ａ‐ｕ及び受信部２３ｂ‐ｕは、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード等の通信部である。また、制御部２４‐ｕと、ブロック情報選択部２５ａ‐ｕと、第１ブロック情報更新部２５ｂ‐ｕと、第２ブロック情報更新部２５ｃ‐ｕと、第３ブロック情報更新部２５ｄ‐ｕと、任意値設定部２５ｅ‐ｕと、ランダム化部２５ｆ‐ｕ，２５ｈ‐ｕと、第６ブロック情報更新部２５ｇ‐ｕと、順序入れ替え部２５ｉ‐ｕとは、例えば、所定のプログラムが読み込まれたＣＰＵである。なお、（v[u]）２０‐ｕは、それぞれ制御部２４‐ｕの制御のもと各処理を実行する。また、各処理部は処理に必要なデータをメモリ２１‐ｕから読み込み、その処理結果をメモリ２１‐ｕに格納する。
【００３６】
＜返信開始処理を行う通信装置（v[u]）２０‐ｕ＞
図４は、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置（v[u]）２０‐ｕの機能構成を示したブロック図である。
図４に示すように、当該通信装置２０‐ｕは、メモリ２１‐ｕと、入力部２２‐ｕと、送信部２３ａ‐ｕと、受信部２３ｂ‐ｕと、制御部２４‐ｕと、ブロック情報選択部２５ａ‐ｕと、第１ブロック情報更新部２５ｂ‐ｕと、第４ブロック情報更新部２６ａ‐ｕと、削除部２６ｂ‐ｕと、任意値設定部２６ｃ‐ｕと、ランダム化部２６ｄ−ｕと、順序入れ替え部２６ｅ‐ｕと、第１任意値設定部２６ｆ‐ｕと、第７ブロック情報更新部２６ｇ‐ｕと、第８ブロック情報更新部２６ｈ‐ｕと、第１０ブロック情報更新部２６ｉ‐ｕと、第１１ブロック情報更新部２６ｊ‐ｕと、を有している。
【００３７】
ここで、第４ブロック情報更新部２６ａ‐ｕと、削除部２６ｂ‐ｕと、任意値設定部２６ｃ‐ｕと、ランダム化部２６ｄ−ｕと、順序入れ替え部２６ｅ‐ｕと、第１任意値設定部２６ｆ‐ｕと、第７ブロック情報更新部２６ｇ‐ｕと、第８ブロック情報更新部２６ｈ‐ｕと、第１０ブロック情報更新部２６ｉ‐ｕと、第１１ブロック情報更新部２６ｊ‐ｕとは、例えば、所定のプログラムが読み込まれたＣＰＵである。
【００３８】
＜返信受信処理を行う通信装置（v[u]）２０‐ｕ＞
図５は、通信装置v[u+1]（0≦u≦n-1）から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置（v[u]）２０‐ｕ（0≦u≦n-1）の機能構成を示したブロック図である。
図５に示すように、当該通信装置２０‐ｕは、入力部２２‐ｕと、送信部２３ａ−ｕ（「第３送信手段」に相当）と、受信部２３ｂ‐ｕと、制御部２４‐ｕと、判定部２７ａ‐ｕと、第５ブロック情報更新部２７ｂ‐ｕと、第９ブロック情報更新部２７ｃ‐ｕと、第１２ブロック情報更新部２７ｄ‐ｕと、第２任意値設定部２７ｅ‐ｕと、第１３ブロック情報更新部２７ｆ‐ｕと、第１４ブロック情報更新手段２７ｇ‐ｕと、第１５ブロック情報更新手段２７ｈ‐ｕと、第１６ブロック情報更新手段２７ｉ‐ｕと、任意値設定部２７ｊ‐ｕと、ランダム化部２７ｋ‐ｕと、を有する。
【００３９】
ここで、判定部２７ａ‐ｕと、第５ブロック情報更新部２７ｂ‐ｕと、第９ブロック情報更新部２７ｃ‐ｕと、第１２ブロック情報更新部２７ｄ‐ｕと、第２任意値設定部２７ｅ‐ｕと、第１３ブロック情報更新部２７ｆ‐ｕと、第１４ブロック情報更新手段２７ｇ‐ｕと、第１５ブロック情報更新手段２７ｈ‐ｕと、第１６ブロック情報更新手段２７ｉ‐ｕと、任意値設定部２７ｊ‐ｕと、ランダム化部２７ｋ‐ｕとは、例えば、所定のプログラムが読み込まれたＣＰＵである。
【００４０】
なお、図３〜図５では、通信装置２０‐ｕの機能構成を通信装置２０‐ｕの機能ごとに説明したが、実際は各通信装置２０‐ｕが図３〜図５のすべての機能構成を具備する。また、本形態の例では、通信装置１０は図３〜図５のすべての機能構成を具備し、各通信装置２０‐ｕも通信装置１０の機能構成を具備する。すなわち、本形態の例では、通信装置１０及び各通信装置２０‐ｕは同一の機能構成を具備し、必要に応じて各機能を使い分ける。
【００４１】
＜処理＞
通信装置（v[0]）１０から送信された送信情報は、v[1],...,v[n-1]（n≧2）の順序で通信装置（v[1],...,v[n-1]）２０-１〜ｎで中継されて通信装置（v[n]）２０-ｎに届けられる。この情報送信は、オニオンルーティング等の公知の匿名通信方式を利用して行われるが、それによって送信される送信情報に本形態独自の返信経路情報が付加される点が従来との相違点である。ここで、通信装置（v[0]）１０が匿名通信を開始する処理を「送信開始処理」と呼び、この送信情報を通信装置（v[1],...,v[n-1]）２０-１〜ｎで受信した際に行われる処理を「送信受信処理」と呼ぶ。また、本形態では、通信装置v[h-1]（h=1,...,n）から通信装置v[h]へ情報を送る処理を「送信」と呼び、通信装置v[h]から通信装置v[h-1]へ情報を送る処理を「返信」と呼ぶ。
【００４２】
また、本形態の匿名通信システム１では、何れかの通信装置（v[c+1]）２０-（ｃ＋１）（cはu+1≦c≦n-1の整数）が、送られた送信情報に対する返信を行う。この返信情報は、v[c],...,v[1]の順序で通信装置（v[c],...,v[1]）２０-ｃ〜１に中継され、通信装置（v[0]）１０に届けられる。ここで、通信装置（v[c+1]）２０-（ｃ＋１）が返信を開始する処理を「返信開始処理」と呼び、返信情報を通信装置（v[c],...,v[1]）２０-ｃ〜１及び通信装置（v[0]）１０が受信した際に行われる処理を「返信受信処理」と呼ぶ。
【００４３】
以下では、各処理の「前提」を説明した後、通信装置毎の「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」を説明する。
【００４４】
［前提］
「送信開始処理」「送信受信処理」「返信開始処理」「返信受信処理」の前提について説明する。
【００４５】
まず、Gを位数がq（qは大きな素数）の巡回群とし、gを巡回群Gの生成元とする。本形態では、各通信装置を構成するためのプログラムに巡回群Gとその生成元gと位数qの情報とが記述されているものとする。なお、安全性の観点から、当該巡回群Gは、そこで構成された離散対数問題を多項式時間で解くことが困難なものであることが望ましい。また、そのような巡回群Gの実現例としては、例えば、楕円曲線暗号に用いられる楕円曲線上の有理点のなす群や、エルガマル暗号等に用いられる有限体の乗法群などを用いることができる（例えば、『岡本龍明，山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X（参考文献１）』等参照）。なお、巡回群Gとして楕円曲線上の有理点のなす群を用いる場合、その元は楕円曲線上の点であり、有限体の乗法群を用いる場合、その元は整数である。また、楕円曲線上の有理点のなす群をコンピュータ上で実現するための具体的方法には様々なものが存在し、実際、楕円曲線上の有理点のなす群で構成され、コンピュータ上で実装可能な様々な楕円曲線暗号方式が存在する（例えば、参考文献１や『イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0（参考文献２）』等参照）。また、巡回群G上の演算とは、巡回群Gで定義された演算を意味する。ここで、γ・δ∈Gは、巡回群Gの元γ,δを被演算子として当該巡回群Gで定義された演算を行うことを意味する。また、γ/δ∈Gは、巡回群Gの元γと巡回群Gの元δの逆元１/δとを被演算子として当該巡回群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となる。
【００４６】
また、各通信装置v[f]（f=0,...,n）に固有な固有情報をE[f]とする。固有情報E[f]としては、例えば、各通信装置のＭＡＣアドレス、ＩＰアドレス、ユーザ名、ユーザの電話番号等を例示できる。そして、固有情報E[0]は、通信装置（v[f]）１０のメモリ１１に格納され、各固有情報E[h] （h=1,...,n）は、それぞれに対応する通信装置（v[h]）２０‐ｈのメモリ２１‐ｈに格納されているものとする。
【００４７】
また、各通信装置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]）１０の入力部１２から入力されてメモリ１１に安全に格納され、各秘密鍵x[h]（h=1,...,n）は、それぞれに対応する通信装置（v[h]）２０‐ｈの入力部２２‐ｈから入力されてメモリ２１‐ｈに安全に格納されているものとする。
【００４８】
また、通信装置（v[0]）１０の入力部１２には、匿名通信システム１を構成する各通信装置（v[f]）２０‐ｆ（f=0,...,n）の公開鍵y[f]が入力され、メモリ１１に格納されているものとする。また、通信装置（v[0]）１０の入力部１２には、匿名通信システム１を構成する各通信装置（v[h]）２０‐ｈ（h=1,...,n）にそれぞれ対応する各通信路情報e[h-1, h]が入力され、メモリ１１に格納されているものとする。
【００４９】
さらに、通信装置v[y]（yはu以外の整数）と通信装置v[u]との間の各通信路をそれぞれ特定するための通信路情報をe[y,f]と表現する。通信装置（v[0]）１０の入力部１２には、通信装置（v[0]）１０と通信可能な各通信装置v[y]に対応する通信路情報e[y,0]のリストが入力され、これらがメモリ１１に格納される。同様に、各通信装置（v[h]）２０‐ｈの入力部２２‐ｕには、それぞれ通信装置（v[h]）２０‐ｈと通信可能な各通信装置v[y]に対応する通信路情報e[y,h]のリストが入力され、これらがメモリ２１-ｈに格納されているものとする。なお、当該通信装置v[y]には、匿名通信システム１を構成しない通信装置も含まれる。
【００５０】
［送信開始処理］
次に、通信装置（v[0]）１０が行う送信開始処理について説明する。
図６及び図７は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【００５１】
まず、通信装置（v[0]）１０（図２）の任意値設定部１５ａが、n個の通信装置v[j]（j=1,...,n-1）にそれぞれ対応するr[0,j,0],r[1,j,0],r[0,*,0]∈Zqをランダムに選択し、それらをメモリ１１に格納する（ステップＳ１２）。なお、演算効率の面では、Zqからr[0,j,0],r[1,j,0],r[0,*,0]を選択することが望ましいが、これらを広く整数から選択する構成であってもかまわない。また、これらの値をランダムに選択する方法としては、例えば、疑似乱数を生成し、それをZq又は整数に写像する方法等を例示できる。これらの事項は、Zqからランダムに値を選択するその他の処理に共通する事項であるため、以下同様の説明は省略する。
【００５２】
次に、第１演算部１５ｂが、メモリ１１から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]をメモリ１１に格納する（ステップＳ１３）。また、第２演算部１５ｃが、メモリ１１からr[0,0,0]を読み込み、演算β[0,0,0]=gr[0,0,0]∈Gを行い、その演算結果β[0,0,0]をメモリ１１に格納する（ステップＳ１４）。また、第３演算部１５ｄが、メモリ１１からy[1]とr[1,0,0]を読み込み、演算α[1,0,0]=y[1]r[1,0,0]∈Gを行い、その演算結果α[1,0,0]をメモリ１１に格納する（ステップＳ１５）。さらに、第４演算部１５ｅが、メモリ１１からr[1,0,0]を読み込み、演算β[1,0,0]=gr[1,0,0]∈Gを行い、その演算結果β[1,0,0]をメモリ１１に格納する（ステップＳ１６）。ここで、ステップＳ１３〜Ｓ１６で生成されたα[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0]の４つ組みをブロック情報RB[0,0]=(α[0,0,0],β[0,0,0],α[1,0,0],β[1,0,0])と表現する。
【００５３】
また、第５演算部１５ｆが、メモリ１１から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]をメモリ１１に格納する（ステップＳ１７）。また、第６演算部１５ｇが、メモリ１１からr[0,1,0]を読み込み、演算β[0,1,0]=gr[0,1,0]∈Gを行い、その演算結果β[0,1,0]をメモリ１１に格納する（ステップＳ１８）。また、第７演算部１５ｈが、メモリ１１からy[1]とy[2]とr[1,1,0]とを読み込み、演算α[1,1,0]=(y[1]・y[2])r[1,1,0]∈Gを行い、その演算結果α[1,1,0]をメモリ１１に格納する（ステップＳ１９）。さらに、第８演算部１５ｉが、メモリ１１からr[1,1,0]を読み込み、演算β[1,1,0]=gr[1,1,0]∈Gを行い、その演算結果β[1,1,0]をメモリ１１に格納する（ステップＳ２０）。ここで、ステップＳ１７〜Ｓ２０で生成されたα[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0]の４つ組をブロック情報RB[1,0]=(α[0,1,0],β[0,1,0],α[1,1,0],β[1,1,0])と表現する。
【００５４】
また、第９演算部１５ｊが、m=2,...,n-1のそれぞれについて、メモリ１１から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]をメモリ１１に格納する（ステップＳ２１）。また、第１０演算部１５ｋが、メモリ１１からr[0,m,0]を読み込み、m=2,...,n-1のそれぞれについて、演算β[0,m,0]=gr[0,m,0]∈Gを行い、それらの演算結果β[0,m,0]をメモリ１１に格納する（ステップＳ２２）。また、第１１演算部１５ｍが、m=2,...,n-1のそれぞれについて、メモリ１１から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]をメモリ１１に格納する（ステップＳ２３）。さらに、第１２演算部１５ｎが、m=2,...,n-1のそれぞれについて、メモリ１１からr[1,m,0]を読み込み、演算β[1,m,0]=gr[1,m,0]∈Gを行い、それらの演算結果β[1,m,0]をメモリ１１に格納する（ステップＳ２４）。ここで、ステップＳ２１〜Ｓ２４で生成された各mについてのα[0,m,0],β[0,m,0],α[1,m,0],β[1,m,0]の４つ組をブロック情報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）は、匿名通信において返信経路を特定するための情報となる。
【００５５】
また、第１３演算部１５ｐが、メモリ１１からr[0,*,0]を読み込み、演算α[0,*,0]=y[0]r[0,*,0]∈Gを行い、その演算結果α[0,*,0]をメモリ１１に格納する（ステップＳ２５）。さらに、第１４演算部１５ｑが、メモリ１１からr[0,*,0]を読み込み、演算β[0,*,0]=gr[0,*,0]∈Gを行い、その演算結果β[0,*,0]をメモリ１１に格納する（ステップＳ２６）。ここで、ステップＳ２５，Ｓ２６で生成されたα[0,*,0]，β[0,*,0]の組を返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])と表現する。なお、返信内容格納用情報RB[*,0]は、返信内容を暗号化するための情報となる。
【００５６】
また、ダミーブロック情報生成部１５ｒが、巡回群Gの４個の元の組G[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]∈Gをランダムに選択し、それらをメモリ１１に格納する処理をＤ回（D≧1）行う（ステップＳ２７）。これによって生成された各dについてのG[1,d,0],G[2,d,0],G[3,d,0],G[4,d,0]の４つ組を、それぞれダミーのブロック情報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]は、返信経路情報の長さから返信通信経路が推測されることを防止する役割を果たす。
【００５７】
次に、返信経路情報生成部１５ｓが、ステップＳ１３〜Ｓ２４で生成されたn個のブロック情報RB[0,0],...,RB[n-1,0]と、ステップＳ２７で生成されたＤ個のダミーのブロック情報DB[1,0],..., DB[D,0]とをメモリ１１から読み込む。そして、返信経路情報生成部１５ｓは、各ブロック情報RB[0,0],...,RB[n-1,0], DB[1,0],..., DB[D,0]それぞれの４つ組の配列順序を維持しつつ、ブロック情報間の配列順序をランダムに並び替えたブロック情報列を生成し、それにステップＳ２５，Ｓ２６で生成された返信内容格納用情報RB[*,0]=(α[0,*,0],β[0,*,0])を特定の位置（例えば、先頭位置）に付加した返信経路情報RI[0]=(RB[j,0],DB[d,0],RB[*,0]) (j=0,...,n-1)を生成し、メモリ１１に格納する（ステップＳ２８）。
【００５８】
ここで、このように生成された返信経路情報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]ぞれぞれの４つ組の配列順序を維持しているため、他の通信装置は、ブロック情報間の区切りと、ブロック情報を構成する４つの要素間の区切り及びそれらの配列順序とを知ることはできる。
【００５９】
次に、送信部１３ａが、メモリ１１から返信経路情報RI[0]を読み込み、返信経路情報RI[0]を通信装置（v[1]）２０‐１に送信する（ステップＳ２９）。なお、返信経路情報RI[0]は、メッセージ等に付加され、オニオンルーティング等の周知の匿名通信方式を利用して送信される。以下では、返信経路情報RI[0]の送信に利用される周知の匿名通信方式の説明を省略し、返信経路情報に関する本形態独自の処理のみを説明する。また、「情報を通信装置に送信する」とは、中継装置を介さずに情報を当該通信装置に送信する処理の他、何らかの中継装置を経由して情報を当該通信装置に送信する処理をも含む概念である。
【００６０】
［送信受信処理］
次に、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]を受信した通信装置（v[u]）２０‐ｕが行う送信受信処理を説明する。
【００６１】
図８及び図９は、本形態の送信開始処理を説明するためのフローチャートである。以下、この図に従って、本形態の送信開始処理を説明する。
【００６２】
まず、通信装置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]）２０‐ｕ（図３）の受信部２３ｂ‐ｕで受信され、メモリ２１‐ｕに格納される（ステップＳ３１）。なお、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])と表現する。また、ステップＳ３１で受信される返信経路情報RI[u-1]は、u=1の場合には通信装置（v[0]）１０から送信された返信経路情報RI[0]であり、u≧2場合には、返信経路情報RI[0]が、v[1],...,v[u-1]の順序で、通信装置（v[1],...,v[u-1]）２０‐１〜（ｕ−１）で更新され、通信装置（v[u-1]）２０‐（ｕ−１）から送信された返信経路情報RI[u-1]である。
【００６３】
次に、ブロック情報選択部２５ａ‐ｕが、メモリ２１‐ｕに格納された秘密鍵x[u]を用い、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が具備するブロック情報から、α[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすブロック情報を選択し、それをブロック情報RB[+,u-1]とする（ステップＳ３２）。このブロック情報RB[+,u-1]を特定する情報Inf(RB[+,u-1])はメモリ２１‐ｕに格納される。なお、通信装置（v[u]）２０‐ｕは、ブロック情報RB[0,u-1],...,RB[n-1,u-1]とダミーのDB[1,u-1],...,DB[D,u-1]とを区別できない。そのため、ブロック情報選択部２５ａ‐ｕは、返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]以外の各ブロック情報について、その３番目の要素をα[1,j,u-1]とし、４番目の要素をβ[1,j,u-1]としてα[1,j,u-1]=β[1,j,u-1]x[u]∈Gを満たすか否かを検証し、これを満たすブロック情報RB[+,u-1]を検索する。
【００６４】
次に、第１ブロック情報更新部２５ｂ‐ｕが、メモリ２１‐ｕから情報Inf(RB[+,u-1])を読み込み、メモリ２１‐ｕに格納された返信経路情報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]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ３３）。
【００６５】
次に、制御部２４‐ｕが、当該通信装置（v[u]）２０‐ｕが返信を行うか否かを判断する（ステップＳ３４）。なお、通信装置（v[u]）２０‐ｕが返信を行う場合としては、例えば、u=nである場合や、通信装置（v[u+1]）２０‐（ｕ＋１）が故障しており、通信エラー情報を通信装置（v[0]）１０に返信する必要がある場合等を例示できる。
【００６６】
ここで、通信装置（v[u]）２０‐ｕが返信を行うと判断された場合には、後述の通信装置v[u]の返信開始処理が実行される。
【００６７】
一方、通信装置（v[u]）２０‐ｕが返信を行わないと判断された場合には、まず、第２ブロック情報更新部２５ｃ‐ｕが、メモリ２１‐ｕから情報Inf(RB[+,u-1])を読み込み、メモリ２１‐ｕに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第２ブロック情報更新部２５ｃ‐ｕは、ブロック情報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[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]を更新する。これらにより、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が更新される（ステップＳ３５）。
【００６８】
さらに、第３ブロック情報更新部２５ｄ‐ｕが、メモリ２１‐ｕから情報Inf(RB[+,u-1])を読み込み、メモリ２１‐ｕに格納された返信経路情報RI[u-1]からブロック情報RB[+,u-1]を特定する。そして、第３ブロック情報更新部２５ｄ‐ｕは、ブロック情報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]を更新する。なお、第３ブロック情報更新部２５ｄ‐ｕは、ブロック情報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]を更新する。これらにより、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が更新される（ステップＳ３６）。
【００６９】
その後、任意値設定部２５ｅ‐ｕが、n個の通信装置v[j]（j=1,...,n-1）にそれぞれ対応するr1[0,j,u],r1[1,j,u],r1[0,*,u]∈Zqをランダムに選択し、それらをメモリ２１‐ｕに格納する（ステップＳ３７）。
【００７０】
次に、ランダム化部２５ｆ‐ｕが、メモリ２１‐ｕに格納された返信経路情報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
によって更新する（ステップＳ３８）。
【００７１】
さらに、第６ブロック情報更新部２５ｇ‐ｕが、メモリ２１‐ｕに格納された秘密鍵x[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]を更新する（ステップＳ３９）。
【００７２】
次に、ランダム化部２５ｈ‐ｕが、メモリ２１‐ｕに格納された各情報を用いて、
α[0,*,u-1]=α[0,*,u-1]r1[0,*,u]∈G
β[0,*,u-1]=β[0,*,u-1]r1[0,*,u]∈G
の演算を行い、これらの演算結果によってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ４０）。
【００７３】
次に、順序入れ替え部２５ｉ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、返信経路情報RI[u-1]を更新する（ステップＳ４１）。
【００７４】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ２１‐ｕに格納される。その後、返信経路情報RI[u]は送信部２３ａ‐ｕに送られ、送信部２３ａ‐ｕは、返信経路情報RI[u]を通信装置（v[u+1]）２０‐（ｕ+１）に送信する（ステップＳ４２）。
【００７５】
〔返信開始処理〕
次に、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]に対して、通信装置（v[u]）２０‐ｕが返信開始処理を行う場合の処理を説明する。
【００７６】
図１０は、本形態の返信開始処理を説明するためのフローチャートである。以下、この図を用いて本形態の返信開始処理を説明する。
【００７７】
まず、通信装置（v[0]）１０（図４）の第４ブロック情報更新部２６ａ‐ｕが、メモリ２１‐ｕに格納された秘密鍵x[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]を更新する。なお、第４ブロック情報更新部２６ａ‐ｕは、ブロック情報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]を更新する。これらにより、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が更新される（ステップＳ５１）。
【００７８】
次に、削除部２６ｂ‐ｕが、メモリ２１‐ｕに格納された返信経路情報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])とし、メモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ５２）。なお、この更新は、返信内容格納用情報RI[u-1]から以降で使用しない情報を削除する処理である。
【００７９】
次に、任意値設定部２６ｃ‐ｕが、n個の通信装置v[j]（j=1,...,n-1）にそれぞれ対応するr3[0,j,u]∈Zqをランダムに選択し、それをメモリ２１‐ｕに格納する（ステップＳ５３）。
【００８０】
そして、ランダム化部２６ｄ‐ｕが、メモリ２１‐ｕに格納された各要素を用い、
α[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
によってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ５４）。
【００８１】
次に、順序並び替え部２６ｅ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]を構成するRB[j,u-1],DB[d,u-1]の順序をランダムに並び替え、当該信経路情報RI[u-1]を更新する（ステップＳ５５）。
【００８２】
次に、第１任意値設定部２６ｆ‐ｕが、r[0,*,u],r[1,*,u]∈Zqをランダムに設定し、設定したr[0,*,u],r[1,*,u]∈Zqをメモリ２１‐ｕに格納する（ステップＳ５６）。
【００８３】
そして、第７ブロック情報更新部２６ｇ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ２１‐ｕに格納されたr[0,*,u]を用い、返信メッセージをM∈Gとした場合における演算M・α[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ５７）。なお、返信メッセージMは、入力部２２‐ｕから入力された情報から生成されたものであってもよいし、予め定められたもの（例えば通信エラー情報等）であってもよい。
【００８４】
また、第８ブロック情報更新部２６ｈ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ２１‐ｕに格納されたr[0,*,u]を用い、演算β[0,*,u-1]r[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u-1]として当該返信内容格納用情報RB[*,u-1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ５８）。
【００８５】
次に、第１０ブロック情報更新部２６ｉ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のα[0,*,u-1]に対し、メモリ２１‐ｕに格納されたr[1,*,u]を用い、演算α[1,*,u-1]=α[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果α[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ５９）。
【００８６】
また、第１１ブロック情報更新部２６ｊ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u-1]が具備する返信内容格納用情報RB[*,u-1]のβ[0,*,u-1]に対し、メモリ２１‐ｕに格納されたr[1,*,u]を用い、演算β[1,*,u-1]=β[0,*,u-1]r[1,*,u]∈Gを行い、その演算結果β[1,*,u-1]を当該返信内容格納用情報RB[*,u-1]の要素として追加し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u-1]を更新する（ステップＳ６０）。
【００８７】
そして、以上の更新がなされた返信経路情報RI[u-1]は、返信経路情報RI[u]としてメモリ２１‐ｕに格納される。その後、返信経路情報RI[u]は送信部２３ａ‐ｕに送られ、送信部２３ａ‐ｕは、返信経路情報RI[u]を通信装置（v[u-1]）２０‐（ｕ‐１）に送信する（ステップＳ６１）。
【００８８】
〔通信装置v[u+1]（1≦u≦n-1）の返信受信処理〕
次に、通信装置v[u+1]（1≦u≦n-1）から返信された返信経路情報RI[u+1] に対して、通信装置（v[u]）２０‐ｕ（1≦u≦n-1）が返信受信処理を行う場合の処理を説明する。
【００８９】
まず、通信装置（v[u]）２０‐ｕ（図５）の受信部２２‐ｕが、通信装置（v[u+1]）２０‐（ｕ＋１）から返信された返信経路情報RI[u+1]を受信し、メモリ２１‐ｕに格納する（ステップＳ７１）。
【００９０】
なお、1≦u≦n-2の場合、ステップＳ７１で受信される返信経路情報RI[u+1]は、通信装置（v[0]）１０から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置（v[1],...,v[c]）２０‐１〜ｃで更新され、返信を行う通信装置（v[c+1]）２０‐（ｃ＋１）に送信され、通信装置（v[c+1]）２０‐（ｃ＋１）で更新され、通信装置v[c]に返信され、v[c],...,v[u+1]の順序で、通信装置（v[c],...,v[u+1]）２０‐ｃ〜（ｕ＋１）で更新され、通信装置（v[u+1]）２０‐（ｕ＋１）から返信された返信経路情報RI[u+1]である。
【００９１】
また、u=n-1の場合、ステップＳ７１で受信される返信経路情報RI[u+1]は、通信装置（v[0]）１０から送信された返信経路情報RI[0]が、v[1],...,v[n-1]の順序で、通信装置（v[1],...,v[n-1]）２０‐１〜（ｎ−１）で更新され、返信を行う通信装置（v[n]）２０‐ｎに送信され、通信装置（v[n]）２０‐ｎで更新され、通信装置（v[n-1]）２０‐（ｎ−１）に返信された返信経路情報RI[n]である。
【００９２】
次に、判定部２７ａ‐ｕが、メモリ２１‐ｕに格納されたx[u],E(u),e[y,u]を用い、(1)メモリ２１‐ｕに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]と、何れかの通信路情報e[y,u]との組合せに対してα[0,j,u+1]=β[0,j,u+1]e[y,u]∈Gを満たすか、(2) メモリ２１‐ｕに格納された返信経路情報RI[u+1]が含む何れかのブロック情報RB[j,u+1]がα[0,j,u+1]=β[0,j,u+1]x[u]・E(u)∈Gを満たすかを判定する（ステップＳ７２）。
【００９３】
ここで、u≠0の場合には(2)の条件は充足されず、(1)の条件を充足するブロック情報RB[j,u+1]と通信路情報e[y,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]とをメモリ２１‐ｕに格納する（ステップＳ７３）。
【００９４】
次に、第５ブロック情報更新部２７ｂ‐ｕが、メモリ２１‐ｕに格納された情報inf(RB[++,u+1])を用いてブロック情報RB[++,u+1]を特定し、メモリ２１‐ｕに格納された秘密鍵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]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ７４）。
【００９５】
次に、第９ブロック情報更新部２７ｃ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],β[0,*,u+1]に対し、メモリ２１‐ｕに格納された秘密鍵x[u]を用い、演算α[0,*,u+1]/β[0,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ７５）。
【００９６】
また、第１２ブロック情報更新部２７ｄが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1],β[1,*,u+1]に対し、メモリ２１‐ｕに格納された秘密鍵x[u]を用い、演算α[1,*,u+1]/β[1,*,u+1]x[u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ７６）。
【００９７】
また、第２任意値設定部２７ｅ‐ｕが、r2[0,*,u],r2[1,*,u]∈Zqをランダムに選択し、選択したr2[0,*,u],r2[1,*,u]∈Zqをメモリ２１‐ｕに格納する（ステップＳ７７）。
【００９８】
そして、以上のように更新されメモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[0,*,u+1],α[1,*,u+1]に対し、メモリ２１‐ｕに格納されたr2[0,*,u]を用いて演算α[0,*,u+1]・α[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなα[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ７８）。
【００９９】
次に、第１４ブロック情報更新部２７ｇ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[0,*,u+1],β[1,*,u+1]に対し、メモリ２１‐ｕに格納されたr2[0,*,u]を用いて演算β[0,*,u+1]・β[1,*,u+1]r2[0,*,u]∈Gを行い、その演算結果を新たなβ[0,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ７９）。
【０１００】
また、第１５ブロック情報更新部２７ｈ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のα[1,*,u+1]に対し、メモリ２１‐ｕに格納されたr2[1,*,u]を用いて演算α[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなα[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ８０）。
【０１０１】
また、第１６ブロック情報更新部２７ｉ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]が具備する返信内容格納用情報RB[*,u+1]のβ[1,*,u+1]に対し、メモリ２１‐ｕに格納されたr2[1,*,u]を用いて演算β[1,*,u+1]r2[1,*,u]∈Gを行い、その演算結果を新たなβ[1,*,u+1]として当該返信内容格納用情報RB[*,u+1]を更新し、それによってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ８１）。
【０１０２】
次に、任意値設定部２７ｊ‐ｕが、n個の通信装置v[j]（j=1,...,n-1）にそれぞれ対応するr4[0,j,u]∈Zqをランダムに選択し、それをメモリ２１‐ｕに格納する（ステップＳ８２）。  
【０１０３】
そして、ランダム化部２７ｋ‐ｕが、メモリ２１‐ｕに格納された各要素を用い、
α[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
によってメモリ２１‐ｕに格納された返信経路情報RI[u+1]を更新する（ステップＳ８３）。
【０１０４】
次に、順序並び替え部２６ｅ‐ｕが、メモリ２１‐ｕに格納された返信経路情報RI[u+1]を構成するRB[j,u+1],DB[d,u+1]の順序をランダムに並び替え、当該信経路情報RI[u+1]を更新する（ステップＳ８４）。
【０１０５】
そして、以上の更新がなされた返信経路情報RI[u+1]は、返信経路情報RI[u]としてメモリ２１+ｕに格納される。その後、返信経路情報RI[u]は送信部２３ａ‐ｕに送られ、送信部２３ａ‐ｕは、返信経路情報RI[u]を通信装置（v[u-1]）２０‐（ｕ‐１）に送信する（ステップＳ８５）。
【０１０６】
〔通信装置v[1]の返信受信処理〕
図１１及び図１２は、信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置（v[0]）１０が返信受信処理を行う場合の処理を説明するためのフローチャートである。以下、これらの図を用い、通信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置（v[0]）１０が返信受信処理を行う場合の処理を説明する。
【０１０７】
まず、通信装置（v[0]）１０（図２）の受信部１３ｂが、通信装置（v[1]）２０‐１から返信された返信経路情報RI[1]を受信し、メモリ１１に格納する（ステップＳ７１）。
【０１０８】
なお、ステップＳ７１で受信される返信経路情報RI[1]は、通信装置（v[0]）１０から送信された返信経路情報RI[0]が、v[1],...,v[c]（cはu+1≦c≦n-1の整数）の順序で、通信装置（v[1],...,v[c]）２０‐１〜ｃで更新され、返信を行う通信装置（v[c+1]）２０‐（ｃ＋１）に送信され、通信装置（v[c+1]）２０‐（ｃ＋１）で更新され、通信装置v[c]に返信され、v[c],...,v[1]の順序で、通信装置（v[c],...,v[1]）２０‐ｃ〜１で更新され、通信装置（v[1]）２０‐１から返信された返信経路情報RI[1]である。
【０１０９】
次に、判定部１５ｔが、メモリ１１に格納されたx[0],E(0),e[y,0]を用い、(1)メモリ１１に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]と、何れかの通信路情報e[y,0]との組合せに対してα[0,j, 1]=β[0,j,1]e[y,0]∈Gを満たすか、(2) メモリ１１に格納された返信経路情報RI[1]が含む何れかのブロック情報RB[j,1]がα[0,j,1]=β[0,j,1]x[0]・E(u)∈Gを満たすかを判定する（ステップＳ７２）。
【０１１０】
ここで、通信装置v[1]の場合には(1)の条件は充足されず、(2)の条件が充足される。この場合、返信メッセージ復号部１５ｕが、メモリ１１に格納された返信経路情報RI[1]が具備する返信内容格納用情報RB[*,1]のα[0,*,1],β[0,*,1]に対し、演算α[0,*,1]/β[0,*,1]x[0]∈Gを行い、その演算結果を返信メッセージM∈Gとしてメモリ１１に格納する（ステップＳ８６）。
【０１１１】
〔本形態の特徴〕
以上説明した通り、本形態の返信経路情報RI[0]の情報サイズはO(n)である。
【０１１２】
また、本形態では、通信装置v[0]から送信された返信経路情報RI[0]がv[1],...,v[c]と更新され、返信開始処理を行う任意の通信装置v[c+1]に届けられる。まず、通信装置v[c+1]は、その直前の通信装置v[c]への通信路を知っているため通信装置v[c]への返信が可能である。また、以上の処理を追っていけば分かるように、通信装置v[c],...,v[1]は、それぞれステップＳ７２の処理を行うことにより、それぞれ、次の返信先である通信装置への通信路情報を得ることができるが、当該匿名通信経路上の他の通信装置への通信路情報を得ることはできない。これは、返信経路情報を構成する各ブロック情報RBに匿名通信経路上の各通信路情報を暗号化して格納し、送信時のステップＳ３３で次の送信先への通信路情報が暗号化されたブロック情報RB[+,u-1]に対して特殊な更新処理を行い、ステップＳ３５,Ｓ３６においてRB[+,u-1]以外の各ブロック情報RBに対して更新演算を行い、返信時のステップＳ７４で更新復元処理を実行したことによる。つまり、上述の処理を逐一追っていけば明らかなように、このような処理を行った結果、各通信装置がステップＳ７２でα[0,j,u+1]=β[0,j,u+1]x[u]・e[y,u]∈Gを満たすブロック情報であると検出するのは、それぞれ次の返信先の通信装置への通信路を特定する通信路情報を暗号化したブロック情報のみとなる。そして、巡回群Gでの離散対数問題が困難であり、各通信装置が他の通信装置の秘密鍵を知らないとすると、各通信装置は、自らの返信先以外の通信装置への通信路を特定する通信路情報を得ることはできない。
【０１１３】
以上より、本形態では、少ない情報サイズの返信経路情報を用い、送信経路上の任意の通信装置において匿名通信による返信を行うことができる。
【０１１４】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、各通信装置が相互に独立である場合を例示したが、少なくとも一部の通信装置が同一の管理者に管理される構成であってもよい。
【０１１５】
また、本形態では、各通信装置２０‐ｕが図３〜図５に示したすべての機能構成を具備することとした。しかし、少なくとも一部の通信装置２０‐ｕが図３〜図５に示した機能構成の一部のみを具備する構成であってもよい。例えば、送信先の通信装置v[n]が通信装置２０‐ｎに固定されるのであれば、その通信装置２０‐ｎは、図３及び図５に示した機能構成を具備しなくてもよい。
【０１１６】
また、本形態では、通信装置１０も図３〜図５のすべての機能構成を具備し、各通信装置２０‐ｕも通信装置１０の機能構成を具備することとした。しかし、通信装置１０が図３〜図５の機能構成を具備しないか、それらの一部の機能構成を具備する構成であってもよい。また、各通信装置２０‐ｕが通信装置１０の機能構成を具備しないか、それらの一部の機能構成を具備してもよい。さらには、一部の通信装置２０‐ｕのみが、通信装置１０の少なくとも一部の機能構成をさらに具備する構成であってもよい。
【０１１７】
また、返信メッセージMを暗号化する必要がない場合、ステップＳ１２でr[0,*,0]∈Zqをランダムに選択する処理、ステップＳ２５,Ｓ２６の処理、ステップ２８において返信経路情報RI[0]にRB[*,0]を付加する処理、ステップＳ３９の処理、ステップＳ５６〜Ｓ６０の処理、ステップＳ７５〜Ｓ８１の処理等の返信内容格納用情報に関する処理や、それらの処理部を省略してもよい。
【０１１８】
また、安全性は低下するが、ステップＳ２７、ステップＳ５４、ステップＳ８３等が具備するダミーのブロック情報に関する処理や、それらの処理部を省略してもよい。また、ステップＳ２８、ステップＳ４１、ステップＳ５５、ステップＳ８４等のブロック情報の並び替え処理や、それらの処理部を省略してもよく、ステップＳ３７、ステップＳ３８、ステップＳ４０、ステップＳ５３、ステップＳ５４、ステップＳ８２、ステップＳ８３等のランダム化処理や、それらの処理部を省略してもよい。
【０１１９】
さらに、ステップＳ５２の処理は、返信内容格納用情報からそれ以降使用しない情報を削除する処理であるが、ステップＳ５２の処理やその処理部を省略してもよい。
【０１２０】
また、本形態では、匿名通信システムを構成する通信装置v[0]が返信経路情報生成装置である場合を例示したが、匿名通信システムを構成しないその他の装置（例えば、信頼できる第三者装置）が返信経路情報生成装置であってもよい。この場合、返信経路情報生成装置が返信経路情報を通信装置v[0]に送り、通信装置v[0]が当該返信経路情報を通信装置v[1]に送信する。この際、通信装置v[0]が返信経路情報をランダム化してから通信装置v[1]に送信してもよい。
【０１２１】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１２２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１２７】
本発明は、例えば、通信経路の匿名性が要求される電子投票、電子入札等の分野に利用できる。
【図面の簡単な説明】
【０１２８】
【図１】図１（ａ）は、本形体の匿名通信システムの全体構成を示した図である。図１（ｂ）は、本形態の通信装置（v[0]）のハードウェア構成を例示したブロック図である。
【図２】図２は、本形態の通信装置の機能構成を示したブロック図である。
【図３】図３は、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置（v[u]）の機能構成を示したブロック図である。
【図４】図４は、通信装置v[u-1]（u=1,...,n）から送信された返信経路情報RI[u-1]を用いて返信開始処理を行う本形態の通信装置（v[u]）の機能構成を示したブロック図である。
【図５】図５は、通信装置v[u+1]（0≦u≦n-1）から返信された返信経路情報RI[u-1]の受信処理を行う本形態の通信装置（v[u]）（0≦u≦n-1）の機能構成を示したブロック図である。
【図６】図６は、本形態の送信開始処理を説明するためのフローチャートである。
【図７】図７は、本形態の送信開始処理を説明するためのフローチャートである。
【図８】図８は、本形態の送信開始処理を説明するためのフローチャートである。
【図９】図９は、本形態の送信開始処理を説明するためのフローチャートである。
【図１０】図１０は、本形態の返信開始処理を説明するためのフローチャートである。
【図１１】図１１は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置（v[0]）が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【図１２】図１２は、送信装置v[1]から返信された返信経路情報RI[1] に対して、通信装置（v[0]）が返信受信処理を行う場合の処理を説明するためのフローチャートである。
【符号の説明】
【０１２９】
１  通信システム
【図１】
0004790736.tif 000002
【図２】
0004790736.tif 000003
【図３】
0004790736.tif 000004
【図４】
0004790736.tif 000005
【図５】
0004790736.tif 000006
【図６】
0004790736.tif 000007
【図７】
0004790736.tif 000008
【図８】
0004790736.tif 000009
【図９】
0004790736.tif 000010
【図１０】
0004790736.tif 000011
【図１１】
0004790736.tif 000012
【図１２】
0004790736.tif 000013