(57)【要約】【課題】送受信者で共有する情報の安全性が保障される範囲内で、従来よりも高い鍵レートを実現する。【解決手段】送信者装置がxを用いu1を算出し、s1= u1・M1Tを算出し、受信者装置に送信する。受信者装置が、yを用いv1を算出し、t1=v1・M1Tを算出し、和s1+t1を復号してw1を生成し、v1とw1とからu1=v1+w1を算出し、w1を送信者装置に送信する。送信者装置がw1とxとを用いて各u2,Tc(2)を算出し、受信者装置がw1とyとを用いて各v2,Tc(2)を算出する。送信者装置がs2,T0=u2,T0・M2Tを算出し、受信者装置に送信する。受信者装置がt2,T0=v2,T0・M2Tを算出し、和s2,T0+t2,T0を復号してw2,T0を生成し、u2,T0=v2,T0+w2,T0を算出する。これらの過程において、送信者装置はu2,T1そのものを受信者装置に送信しない。【選択図】図４
2008288665.tif 000002
【特許請求の範囲】
【請求項１】
送信者装置と受信者装置との間で実行する情報整合化方法であって、
位数２の有限体をF2とし、κ(κ≧２)個の有限体F2の直積が成すベクトル空間をF2κとし、ベクトル空間F2κから有限体F2へ移す線形な関数をξ1とし、ベクトル空間F2κとベクトル空間F2r-1(r∈{2,...,κ})との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F2κの要素について線形な関数をξrとし、u=(u11,...,u1κ,...,un1,...,unκ)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,...,κ})とし、v=(v11,...,v1κ,...,vn1,...,vnκ)(vik∈{0,1})とし、w=(w11,...,w1κ,...,wn1,...,wnκ)(wik∈{0,1})とし、ui1=ξ1(xi1,...,xiκ)とし、vi1=ξ1(yi1,...,yiκ)とし、wi1=ui1+vi1とし、uir=ξr(xi1,...,xiκ, wi1,...,wi(r-1))とし、vir=ξr(yi1,...,yiκ, wi1,...,wi(r-1))とし、wir=uir+virとし、uj=(u1j,...,unj) (j∈{1,...,κ})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、wir-1=(wi1,...,wi(r-1))とし、c(r)∈F2r-1に対してTc(r)={i|1≦i≦n, wir-1=c(r)}とし、ur, vr, wrのうち、i∈Tc(r)を満たすビットからなる部分列をそれぞれur,Tc(r), vr,Tc(r), wr,Tc(r)とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とし、・Ｔを・の転置行列とした場合における、
(a-1)送信者装置の記憶部にx=(x11,...,x1κ,...,xn1,...,xnκ)(xik∈{0,1})を格納する過程と、
(a-2)受信者装置の記憶部にy=(y11,...,y1κ,...,yn1,...,ynκ)(yik∈{0,1})を格納する過程と、
(a-3)送信者装置のパリティ系列変換部が、x=(x11,...,x1κ,...,xn1,...,xnκ)を用い、u1=(u11,...,un1)を算出する過程と、
(a-4)送信者装置のシンドローム計算部が、u1=(u11,...,un1)のシンドロームs1=u1・M1Tを算出する過程と、
(a-5)送信者装置の通信部が、シンドロームs1を受信者装置に送信する過程と、
(a-6)受信者装置のパリティ系列変換部が、y=(y11,...,y1κ,...,yn1,...,ynκ)を用い、v1=(v11,...,vn1)を算出する過程と、
(a-7)受信者装置のシンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する過程と、
(a-8)受信者装置の加算部が、シンドロームs1とt1の和s1+t1を算出する過程と、
(a-9)受信者装置のシンドローム復号部が、シンドロームの和s1+t1を復号してw1を生成する過程と、
(a-10)受信者装置の復号部が、v1とw1とからu1=v1+w1を算出する過程と、
を実行し、
r=2からr=κまでの各整数rについて、
(b-1)受信者装置の通信部が、wr-1,Tc(r-1)(w1,Tc(1)=w1)を送信者装置に送信する過程と、
(b-2)送信者装置のビット列分類部が、wr-1,Tc(r-1)とx=(x11,...,x1κ,...,xn1,...,xnκ)とを用い、各ur,Tc(r)を算出する過程と、
(b-3)受信者装置のビット列分類部が、wr-1,Tc(r-1)とy=(y11,...,y1κ,...,yn1,...,ynκ)とを用い、各vr,Tc(r)を算出する過程と、
(b-4)送信者装置のシンドローム計算部が、各ur,Tc(r)のシンドロームsr,Tc(r)=ur,Tc(r)・MrTを算出する過程と、
(b-5)送信者装置の通信部が、シンドロームsr,Tc(r)を受信者装置に送信する過程と、
(b-6)受信者装置のシンドローム計算部が、vr,Tc(r)のシンドロームtr,Tc(r)=vr,Tc(r)・MrTを算出する過程と、
(b-7)受信者装置の加算部が、シンドロームsr,Tc(r)とtr,Tc(r)の和sr,Tc(r)+tr,Tc(r)を算出する過程と、
(b-8)受信者装置のシンドローム復号部が、シンドロームの和sr,Tc(r)+tr,Tc(r)を復号してwr,Tc(r)を生成する過程と、
(b-9)受信者装置の復号部が、vr,Tc(r)とwr,Tc(r)とからur,Tc(r)=vr,Tc(r)+wr,Tc(r)を算出する過程と、
を実行し、
送信者装置及び受信者装置の各出力部が、u1とur,Tc(r) (r∈{2,...,κ})との少なくとも一部を、共有情報として出力する過程を実行し、
送信者装置の通信部は、ur,Tc(r)そのものを受信者装置に送信しない、
ことを特徴とする情報整合化方法。
【請求項２】
請求項１に記載の情報整合化方法であって、
κ≧３であることを特徴とする情報整合化方法。
【請求項３】
送信者装置と受信者装置との間で実行する情報整合化方法であって、
位数２の有限体をF2とし、２個の有限体F2の直積が成すベクトル空間をF22とし、ベクトル空間F22から有限体F2へ移す線形な関数をξ1とし、当該関数ξ1は任意のa1,a2∈F2に対してξ1(a1,a2)=a1+a2を満たし、ベクトル空間F22とベクトル空間F2との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F22の要素について線形な関数をξ2とし、当該関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 0)=a1又はξ2(a1,a2, 0)=a2を満たし、u=(u11,u12,...,un1,un2)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,2})とし、v=(v11,v12,...,vn1,vn2)(vik∈{0,1})とし、w=(w11,w12,...,wn1,wn2)(wik∈{0,1})とし、ui1=ξ1(xi1,xi2)とし、vi1=ξ1(yi1,yi2)とし、wi1=ui1+vi1とし、ui2=ξ2(xi1,xi2, wi1)とし、vi2=ξ2(yi1,yi2, wi1)とし、wi2=ui2+vi2とし、ujをuj=(u1j,...,unj) (j∈{1,2})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、wi1=(wi1)とし、c(2)∈{0,1}に対してTc(2)={i|1≦i≦n, wi1=c(2)}とし、u2, v2, w2のうち、i∈Tc(2)を満たすビットからなる部分列をそれぞれu2,Tc(2), v2,Tc(2), w2,Tc(2)とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とし、・Ｔを・の転置行列とした場合における、
(a-1)送信者装置の記憶部にx=(x11,x12,...,xn1,xn2)(xik∈{0,1})を格納する過程と、
(a-2)受信者装置の記憶部にy=(y11,y12,...,yn1,yn2)(yik∈{0,1})を格納する過程と、
(a-3)送信者装置のパリティ系列変換部が、x=(x11,x12,...,xn1,xn2)を用い、u1=(u11,...,un1)を算出する過程と、
(a-4)送信者装置のシンドローム計算部が、u1=(u11,...,un1)のシンドロームs1= u1・M1Tを算出する過程と、
(a-5)送信者装置の通信部が、シンドロームs1を受信者装置に送信する過程と、
(a-6)受信者装置のパリティ系列変換部が、y=(y11,y12,...,yn1,yn2)を用い、v1=(v11,...,vn1)を算出する過程と、
(a-7)受信者装置のシンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する過程と、
(a-8)受信者装置の加算部が、シンドロームs1とt1の和s1+t1を算出する過程と、
(a-9)受信者装置のシンドローム復号部が、シンドロームの和s1+t1を復号してw1を生成する過程と、
(a-10)受信者装置の復号部が、v1とw1とからu1=v1+w1を算出する過程と、
(b-1)受信者装置の通信部が、w1を送信者装置に送信する過程と、
(b-2)送信者装置のビット列分類部が、w1とx=(x11,x12,...,xn1,xn2)とを用い、各u2,Tc(2)を算出する過程と、
(b-3)受信者装置のビット列分類部が、w1とy=(y11,y12,...,yn1,yn2)とを用い、各v2,Tc(2)を算出する過程と、
(b-4)送信者装置のシンドローム計算部が、u2,T0のシンドロームs2,T0=u2,T0・M2Tを算出する過程と、
(b-5)送信者装置の通信部が、シンドロームs2,T0を受信者装置に送信する過程と、
(b-6)受信者装置のシンドローム計算部が、v2,T0のシンドロームt2,T0=v2,T0・M2Tを算出する過程と、
(b-7)受信者装置の加算部が、シンドロームs2,T0とt2,T0の和s2,T0+t2,T0を算出する過程と、
(b-8)受信者装置のシンドローム復号部が、シンドロームの和s2,T0+t2,T0を復号してw2,T0を生成する過程と、
(b-9)受信者装置の復号部が、v2,T0とw2,T0とからu2,T0=v2,T0+w2,T0を算出する過程と、
送信者装置及び受信者装置の各出力部が、u1とu2,T0との少なくとも一部を共有情報として出力する過程と、を実行し、
送信者装置の通信部は、u2,T1そのものを受信者装置に送信しない、
ことを特徴とする情報整合化方法。
【請求項４】
請求項３に記載の情報整合化方法であって、
関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 1)=0又はξ2(a1,a2, 1)=1を満たし、
送信者装置の出力部がu1とu2,T0の少なくとも一部とu2,T1を共有情報として出力する過程と、
受信者装置の出力部がu1とu2,T0の少なくとも一部とv2,T1を共有情報として出力する過程と、を実行する、
ことを特徴とする情報整合化方法。
【請求項５】
請求項３に記載の情報整合化方法であって、
関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 1)=a1又はξ2(a1,a2, 1)=a2を満たし、
当該情報整合化方法では、さらに
送信者装置のビット反転部が、u2,T1の各ビット値をランダムに反転させたu2,T1'を生成する過程と、
送信者装置の通信部が、u2,T1'を受信者装置に送信する過程と、
を実行し、
送信者装置及び受信者装置の各出力部は、u1とu2,T0とu2,T1'を共有情報として出力する、
ことを特徴とする情報整合化方法。
【請求項６】
受信者装置と情報整合化を行う送信者装置であって、
位数２の有限体をF2とし、κ(κ≧３)個の有限体F2の直積が成すベクトル空間をF2κとし、ベクトル空間F2κから有限体F2へ移す線形な関数をξ1とし、ベクトル空間F2κとベクトル空間F2r-1(r∈{2,...,κ})との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F2κの要素について線形な関数をξrとし、u=(u11,...,u1κ,...,un1,...,unκ)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,...,κ})とし、v=(v11,...,v1κ,...,vn1,...,vnκ)(vik∈{0,1})とし、w=(w11,...,w1κ,...,wn1,...,wnκ)(wik∈{0,1})とし、ui1=ξ1(xi1,...,xiκ)とし、vi1=ξ1(yi1,...,yiκ)とし、wi1=ui1+vi1とし、uir=ξr(xi1,...,xiκ, wi1,...,wi(r-1))とし、vir=ξr(yi1,...,yiκ, wi1,...,wi(r-1))とし、wir=uir+virとし、uj=(u1j,...,unj) (j∈{1,...,κ})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、wir-1=(wi1,...,wi(r-1))とし、c(r)∈F2r-1に対してTc(r)={i|1≦i≦n, wir-1=c(r)}とし、ur, vr, wrのうち、i∈Tc(r)を満たすビットからなる部分列をそれぞれur,Tc(r), vr,Tc(r), wr,Tc(r)とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とし、・Ｔを・の転置行列とした場合における、
x=(x11,...,x1κ,...,xn1,...,xnκ)(xik∈{0,1})を格納する記憶部と、
x=(x11,...,x1κ,...,xn1,...,xnκ)を用い、u1=(u11,...,un1)を算出するパリティ系列変換部と、
u1=(u11,...,un1)のシンドロームs1=u1・M1Tを算出する第１シンドローム計算部と、
シンドロームs1を受信者装置に送信する第１通信部と、
受信者装置から送信されたwr-1,Tc(r-1)(w1,Tc(1)=w1)とx=(x11,...,x1κ,...,xn1,...,xnκ)とを用い、各ur,Tc(r)を算出するビット列分類部と、
各ur,Tc(r)のシンドロームsr,Tc(r)=ur,Tc(r)・MrTを算出する第２シンドローム計算部と、
シンドロームsr,Tc(r)を受信者装置に送信する第２通信部と、
u1とur,Tc(r)(r∈{2,...,κ})との少なくとも一部を、受信者装置との共有情報として出力する出力部と、を有し、
上記通信部は、ur,Tc(r)そのものを受信者装置に送信しない、
を有することを特徴とする送信者装置。
【請求項７】
請求項６の送信者装置と情報整合化を行う受信者装置であって、
y=(y11,...,y1κ,...,yn1,...,ynκ)(yik∈{0,1})を格納する記憶部と、
y=(y11,...,y1κ,...,yn1,...,ynκ)を用い、v1=(v11,...,vn1)を算出するパリティ系列変換部と、
v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する第１シンドローム計算部と、
送信者装置から送信されたシンドロームs1とt1の和s1+t1を算出する加算部と、
シンドロームの和s1+t1を復号してw1を生成する第１シンドローム復号部と、
v1とw1とからu1=v1+w1を算出する第１復号部と、
wr-1,Tc(r-1)(w1,Tc(1)=w1)を送信者装置に送信する通信部と、
wr-1,Tc(r-1)とy=(y11,...,y1κ,...,yn1,...,ynκ)とを用い、各vr,Tc(r)を算出するビット列分類部と、
vr,Tc(r)のシンドロームtr,Tc(r)=vr,Tc(r)・MrTを算出する第２シンドローム計算部と、
送信者装置から送信されたシンドロームsr,Tc(r)とtr,Tc(r)の和sr,Tc(r)+tr,Tc(r)を算出する加算部と、
シンドロームの和sr,Tc(r)+tr,Tc(r)を復号してwr,Tc(r)を生成する第２シンドローム復号部と、
vr,Tc(r)とwr,Tc(r)とからur,Tc(r)=vr,Tc(r)+wr,Tc(r)を算出する第２復号部と、
u1とur,Tc(r)(r∈{2,...,κ})との少なくとも一部を、送信者装置との共有情報として出力する出力部と、
を有することを特徴とする受信者装置。
【請求項８】
受信者装置と情報整合化を行う送信者装置であって、
位数２の有限体をF2とし、２個の有限体F2の直積が成すベクトル空間をF22とし、ベクトル空間F22から有限体F2へ移す線形な関数をξ1とし、当該関数ξ1は任意のa1,a2∈F2に対してξ1(a1,a2)=a1+a2を満たし、ベクトル空間F22とベクトル空間F2との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F22の要素について線形な関数をξ2とし、当該関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 0)=a1又はξ2(a1,a2, 0)=a2を満たし、u=(u11,u12,...,un1,un2)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,2})とし、v=(v11,v12,...,vn1,vn2)(vik∈{0,1})とし、w=(w11,w12,...,wn1,wn2)(wik∈{0,1})とし、ui1=ξ1(xi1,xi2)とし、vi1=ξ1(yi1,yi2)とし、wi1=ui1+vi1とし、ui2=ξ2(xi1,xi2, wi1)とし、vi2=ξ2(yi1,yi2, wi1)とし、wi2=ui2+vi2とし、uj=(u1j,...,unj) (j∈{1,2})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、wi1=(wi1)とし、c(2)∈{0,1}に対してTc(2)={i|1≦i≦n, wi1=c(2)}とし、u2, v2, w2のうち、i∈Tc(2)を満たすビットからなる部分列をそれぞれu2,Tc(2), v2,Tc(2), w2,Tc(2)とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とし、・Ｔを・の転置行列とした場合における、
x=(x11,x12,...,xn1,xn2)(xik∈{0,1})を格納する記憶部と、
x=(x11,x12,...,xn1,xn2)を用い、u1=(u11,...,un1)を算出するパリティ系列変換部と、
u1=(u11,...,un1)のシンドロームs1= u1・M1Tを算出する第１シンドローム計算部と、
シンドロームs1を受信者装置に送信する通信部と、
受信者装置から送信されたw1とx=(x11,x12,...,xn1,xn2)とを用い、各u2,Tc(2)を算出するビット列分類部と、
u2,T0のシンドロームs2,T0=u2,T0・M2Tを算出する第２シンドローム計算部と、
シンドロームs2,T0を受信者装置に送信する通信部と、
少なくともu1とu2,T0を、受信者装置との共有情報として出力する出力部と、を有し、
上記通信部は、u2,T1そのものを受信者装置に送信しない、
を有することを特徴とする送信者装置。
【請求項９】
請求項８の送信者装置と情報整合化を行う受信者装置であって、
y=(y11,y12,...,yn1,yn2)(yik∈{0,1})を格納する記憶部と、
y=(y11,y12,...,yn1,yn2)を用い、v1=(v11,...,vn1)を算出するパリティ系列変換部と、
v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する第１シンドローム計算部と、
送信者装置から送信されたシンドロームs1とt1の和s1+t1を算出する第１加算部と、
シンドロームs1とt1の和s1+t1を復号してw1を生成する第１シンドローム復号部と、
v1とw1とからu1=v1+w1を算出する第１復号部と、
w1を送信者装置に送信する通信部と、
w1とy=(x11,x12,...,xn1,xn2)とを用い、各v2,Tc(2)を算出するビット列分類部と、
v2,T0のシンドロームt2,T0=v2,T0・M2Tを算出する第２シンドローム計算部と、
送信者装置から送信されたシンドロームs2,T0とt2,T0の和s2,T0+t2,T0を算出する第２加算部と、
シンドロームの和s2,T0+t2,T0を復号してw2,T0を生成する第２シンドローム復号部と、
v2,T0とw2,T0とからu2,T0=v2,T0+w2,T0を算出する第２復号部と、
少なくともu1とu2,T0を、送信者装置との共有情報として出力する出力部と、
を有することを特徴とする受信者装置。
【請求項１０】
請求項６或いは８に記載の送信者装置としてコンピュータを機能させるためのプログラム。  
【請求項１１】
請求項７或いは９に記載の受信者装置としてコンピュータを機能させるためのプログラム。
【請求項１２】
請求項１０に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項１３】
請求項１１に記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子ビットを用いて情報を共有化する技術に関し、特に情報整合化技術に関する。
【背景技術】
【０００２】
現在広く使われている計算困難性に基づいた暗号方式とは異なり、量子力学の原理によって安全性が保障される鍵配送方式として量子鍵配送プロトコルが提案されており、近年注目を集めている。まず、量子鍵配送プロトコルの手順について簡単に説明する。
【０００３】
＜量子鍵配送プロトコルの手順＞
量子鍵配送では、送信者がランダムなビット列を選び、選んだビット列を光子の偏光等の量子状態に変調して受信者へ送信する。この送信過程で盗聴行為があった場合、量子力学の原理より、送信者が送信したビット列と受信者が受信したビット列の間に違いが生じる。よって、送受信者は送受信されたビット列の一部を公開して比較し、公開したビット列の間に生じている違いの割合（エラーレート）を求めることで、盗聴者が盗聴によって得ている情報量を見積もることができる。BB84プロトコル等、プロトコルごとに変調方法が異なり、情報量の見積もり方に多少差異はあるものの、このステップの目的はビット列を伝送し、そのエラーレートから盗聴者の情報量を見積もることである。
【０００４】
前述のステップを終えると、送受信者は公開せずに残ったビット列を所持している。以下送信者が所有する未公開のビット列をｘ、受信者が所有する未公開のビット列をｙと表す。盗聴行為があった場合、送受信者がそれぞれ所持するビット列ｘとｙの間には違いがあり、さらに、盗聴者はビット列ｘ，ｙに関する情報をある程度知っている。そのため、ビット列ｘ，ｙをそのまま秘密鍵として使用することはできない。そこで、送受信者は以下のような古典的な処理を行うことで、盗聴者に知られていないに等しいビット列（秘密鍵）を共有する。
【０００５】
まず送受信者は、「情報整合化」と呼ばれる誤り訂正処理を行い、等しいビット列を共有する。より詳しく述べると、送受信者は各自が所有するビット列に関する情報を、公開通信路を用いて交換し、交換した情報を利用して等しいビット列を共有する。ただし、公開通信路で送る情報は盗聴者にも知られてしまう。
【０００６】
その後、送受信者は、共有したビット列をハッシュ関数によって短くする「秘密増幅（プライバシー増幅）」と呼ばれる操作を行い、元のビット列より短い鍵（ビット列）を共有する。ここで、共有したビット列のうち盗聴者に漏洩した情報量がｍビットとした場合、共有したビット列からランダムにｍ＋ｓビットを捨てることにより、残ったビット列について盗聴者が持つ情報量を１／２ｓとできる。よって、当該秘密増幅により、送受信者は、盗聴者に知られていないに等しいビット列（秘密鍵）を共有することができる。
【０００７】
公開せずに残ったビット列ｘの長さに対する最終的に共有したビット列の長さの割合は鍵レートと呼ばれる。効率上、量子鍵配送プロトコルにおける鍵レートはできるだけ高いことが望まれる。一方、盗聴者が得ている情報量に応じた秘密増幅により、十分に鍵長を短くしないと安全性は得られない。量子鍵配送プロトコルの性能尺度として、共有した鍵の安全性が保障される範囲内で鍵レートをどこまで高くできるのかが重要である。
【０００８】
＜従来の情報整合化＞
これまで、前半に説明したビット列の伝送方法を工夫することや、後半に説明した古典的な処理方法を工夫することで、安全性が保障される鍵レートを向上させる試みがなされてきた。特に，後半の古典的な処理のコストは前半の量子通信のコストに比べ安価なため、古典的な処理を工夫することで安全な鍵レートを向上することは非常に重要であり、先行研究として様々な方法が提案されている（非特許文献１〜４）。先行研究では、当該古典的な処理のうち、送受信者が等しいビット列を共有するための処理である「情報整合化」の部分を工夫している。
【０００９】
非特許文献１では、情報整合化を行う際に公開通信路を用いた情報伝送を、送受信者間の双方向で行った方が、送信者から受信者への一方向の情報伝送だけを行った場合より、高い鍵レートで安全性が保障されることを示している。また、非特許文献２では、情報整合化を始める前に、送信者が自分の所有するビット列の各ビットの値を、ある定められた確率で反転させてから情報整合化を行うと、何もせずに情報整合化を行った場合より、高い鍵レートで安全性が保障されることを示している。また、非特許文献３と４では，量子鍵配送プロトコルと関連があるエンタングルメント蒸留プロトコルと呼ばれる技術の処理方法が（非特許文献５）、量子鍵配送プロトコルにおいて利用可能であり、安全性が保障される鍵レートを向上できることを示している。
【００１０】
図１０，１１は、非特許文献３，４の情報整合化方法を説明するためのシーケンス図である。以下、これらの図を用いて非特許文献３，４の情報整合化方法を説明する。なお、非特許文献３，４の情報整合化の説明において「(+)」は排他的論理和演算子
【００１１】
【数１】
2008288665.tif 000003
を示す。また、u=(u11,u12,...,un1,un2)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,2})とし、v=(v11,v12,...,vn1,vn2)(vik∈{0,1})とし、w=(w11,w12,...,wn1,wn2)(wik∈{0,1})とし、ui1=xi1(+)xi2とし、vi1=yi1(+)yi2とし、wi1=ui1(+)vi1とし、ui2=xi2,とし、vi2=yi2,とし、wi2=ui2+vi2とし、ujをuj=(u1j,...,unj) (j∈{1,2})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、T0={i|1≦i≦n, wi1=0}とし、T1={i|1≦i≦n, wi1=1}とし、u2, v2, w2のうち、i∈T0を満たすビットからなる部分列をそれぞれu2,T0, v2,T0, w2,T0とし、i∈T1を満たすビットからなる部分列をそれぞれu2,T1, v2,T1, w2,T1とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とする。
【００１２】
まず、送信者装置がx=(x11,x12,...,xn1,xn2)を用い、u1=(u11,...,un1)を算出し（ステップＳ１０１）、u1=(u11,...,un1)のシンドロームs1= u1・M1Tを算出し（ステップＳ１０２）、シンドロームs1を暗号化して受信者装置に送信する（ステップＳ１０３）。受信者装置は、受信した暗号文復号してシンドロームs1を抽出し（ステップＳ１０４）、y=(y11,y12,...,yn1,yn2)を用い、v1=(v11,...,vn1)を算出し（ステップＳ１０５）、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出し（ステップＳ１０６）、シンドロームs1とt1の排他的論理和s1(+)t1を算出し（ステップＳ１０７）、s1(+)t1を復号してw1を生成し（ステップＳ１０８）、w1を送信者装置に送信する（ステップＳ１０９）。
【００１３】
送信者装置は、w1とx=(x11,x12,...,xn1,xn2)とを用い、u2,Ｔ0とu2,Ｔ1算出し（ステップＳ１１０）、受信者装置は、w1とy=(y11,y12,...,yn1,yn2)とを用い、v2,T0とv2,Ｔ1を算出（ステップＳ１１１）する。送信者装置は、u2,T0のシンドロームs2,T0=u2,T0・M2Tを算出し（ステップＳ１１２）、シンドロームs2,T0を受信者装置に送信する（ステップＳ１１３）。受信者装置は、v2,T0のシンドロームt2,T0=v2,T0・M2Tを算出し（ステップＳ１１４）、シンドロームs2,T0とt2,T0の排他的論理和s2,T0(+)t2,T0を算出し（ステップＳ１１５）、s2,T0(+)t2,T0を復号してw2,T0を生成し（ステップＳ１１６）、v2,T0とw2,T0とからu2,T0=v2,T0 (+) w2,T0を算出する（ステップＳ１１７）。
【００１４】
送信者装置はu2,T1を受信者装置に送信する（ステップＳ１１８）。そして、送信者装置と受信者装置とは、u2,T0とu2,T1とを共有情報として出力する（ステップＳ１１９，１２０）。
【非特許文献１】D. Gottesman and H. -K. Lo, “Proof of security of quantum key distribution with two-way classical communications”, IEEE Trans. Inform. Theory, vol. 49, no. 2, pp. 457-474, Feb. 2003.
【非特許文献２】R. Renner, N. Gisin and B. Kraus, “Information-theoretic security proof for quantum key distribution protocols”, Phys. Rev. A, vol. 72, p. 012332. 2005.
【非特許文献３】X. Ma, C. H. F. Fung, F. Dupuis, K. Chen, K. Tamaki and H. -K. Lo, “Docoy-state quantum key distribution with two-way classical postprocessing”, Phys. Rev. A, vol. 74, p. 032330, 2006.
【非特許文献４】S. Watanabe, R. Matsumoto and T. Uyematsu, “Security of quantum key distribution protocol with two-way classical communication assisted by one-time pad encryption”, in Proc. of AQIS 2006, Beijing, China, 2006, pp. 11-12.
【非特許文献５】K. G. H. Vollbrecht and F. Vestraete, “Interpolation of reccurence and hashing entanglement distillation protocols”, Phys. Rev. A, vol. 71, no. 6, p.062325, June 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかし、従来の情報整合化方法には、鍵レート改善の余地が残されていると考えられる。
【００１６】
本発明はこのような点に鑑みてなされたものであり、送受信者で共有する情報の安全性が保障される範囲内で、従来よりも高い鍵レートを実現できる情報整合化技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明では、位数２の有限体をF2とし、κ(κ≧２)個の有限体F2の直積が成すベクトル空間をF2κとし、ベクトル空間F2κから有限体F2へ移す線形な関数をξ1とし、ベクトル空間F2κとベクトル空間F2r-1(r∈{2,...,κ})との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F2κの要素について線形な関数をξrとし、u=(u11,...,u1κ,...,un1,...,unκ)(uik∈{0,1}, i∈{1,...,n}, n≧１, k∈{1,...,κ})とし、v=(v11,...,v1κ,...,vn1,...,vnκ)(vik∈{0,1})とし、w=(w11,...,w1κ,...,wn1,...,wnκ)(wik∈{0,1})とし、ui1=ξ1(xi1,...,xiκ)とし、vi1=ξ1(yi1,...,yiκ)とし、wi1=ui1+vi1とし、uir=ξr(xi1,...,xiκ, wi1,...,wi(r-1))とし、vir=ξr(yi1,...,yiκ, wi1,...,wi(r-1))とし、wir=uir+virとし、uj=(u1j,...,unj) (j∈{1,...,κ})とし、vj=(v1j,...,vnj)とし、wj=(w1j,...,wnj)とし、wir-1=(wi1,...,wi(r-1))とし、c(r)∈F2r-1に対してTc(r)={i|1≦i≦n, wir-1=c(r)}とし、ur, vr, wrのうち、i∈Tc(r)を満たすビットからなる部分列をそれぞれur,Tc(r), vr,Tc(r), wr,Tc(r)とし、Mjを送信者装置と受信者装置との間で共有されるパリティ検査行列とし、・Ｔを・の転置行列とする。
【００１８】
そして、まず、(a-1)送信者装置の記憶部にx=(x11,...,x1κ,...,xn1,...,xnκ)(xik∈{0,1})を格納する過程と、(a-2)受信者装置の記憶部にy=(y11,...,y1κ,...,yn1,...,ynκ)(yik∈{0,1})を格納する過程と、(a-3)送信者装置のパリティ系列変換部が、x=(x11,...,x1κ,...,xn1,...,xnκ)を用い、u1=(u11,...,un1)を算出する過程と、(a-4)送信者装置のシンドローム計算部が、u1=(u11,...,un1)のシンドロームs1=u1・M1Tを算出する過程と、(a-5)送信者装置の通信部が、シンドロームs1を受信者装置に送信する過程と、(a-6)受信者装置のパリティ系列変換部が、y=(y11,...,y1κ,...,yn1,...,ynκ)を用い、v1=(v11,...,vn1)を算出する過程と、(a-7)受信者装置のシンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する過程と、(a-8)受信者装置の加算部が、シンドロームs1とt1の和s1+t1を算出する過程と、(a-9)受信者装置のシンドローム復号部が、シンドロームの和s1+t1を復号してw1を生成する過程と、 (a-10)受信者装置の復号部が、v1とw1とからu1=v1+w1を算出する過程と、を実行する。
【００１９】
その後、r=2からr=κまでの各整数rについて、(b-1)受信者装置の通信部が、wr-1,Tc(r-1)(w1,Tc(1)=w1)を送信者装置に送信する過程と、(b-2)送信者装置のビット列分類部が、wr-1,Tc(r-1)とx=(x11,...,x1κ,...,xn1,...,xnκ)とを用い、各ur,Tc(r)を算出する過程と、(b-3)受信者装置のビット列分類部が、wr-1,Tc(r-1)とy=(y11,...,y1κ,...,yn1,...,ynκ)とを用い、各vr,Tc(r)を算出する過程と、(b-4)送信者装置のシンドローム計算部が、各ur,Tc(r)のシンドロームsr,Tc(r)=ur,Tc(r)・MrTを算出する過程と、(b-5)送信者装置の通信部が、シンドロームsr,Tc(r)を受信者装置に送信する過程と、(b-6)受信者装置のシンドローム計算部が、vr,Tc(r)のシンドロームtr,Tc(r)=vr,Tc(r)・MrTを算出する過程と、(b-7)受信者装置の加算部が、シンドロームsr,Tc(r)とtr,Tc(r)の和sr,Tc(r)+tr,Tc(r)を算出する過程と、(b-8)受信者装置のシンドローム復号部が、シンドロームの和sr,Tc(r)+tr,Tc(r)を復号してwr,Tc(r)を生成する過程と、(b-9)受信者装置の復号部が、vr,Tc(r)とwr,Tc(r)とからur,Tc(r)=vr,Tc(r)+wr,Tc(r)を算出する過程とを実行する。ここで、送信者装置の通信部は、ur,Tc(r)そのものを受信者装置に送信しない。これにより、盗聴者に漏洩する情報量を低減させ、秘密増幅によって捨てられるビット数を減らし、鍵レートを向上させることができる。
その後、送信者装置及び受信者装置の各出力部が、u1とur,Tc(r) (r∈{2,...,κ})との少なくとも一部を、共有情報として出力する過程を実行する。
【００２０】
また、本発明において好ましくはκ≧３である。これにより、κ≦２の場合（例えば非特許文献３，４の場合）に比べ、u1=(u11,...,un1)に含まれるx=(x11,...,x1κ,...,xn1,...,xnκ)の情報量を低減させることができ、盗聴者に漏洩する情報量を低減させ、秘密増幅によって捨てられるビット数を減らし、鍵レートを向上させることができる。
【００２１】
また、本発明において、κ＝２とし、関数ξ1を任意のa1,a2∈F2に対してξ1(a1,a2)=a1+a2を満たすものとし、(a-1)送信者装置の記憶部にx=(x11,x12,...,xn1,xn2)(xik∈{0,1})を格納する過程と、(a-2)受信者装置の記憶部にy=(y11,y12,...,yn1,yn2)(yik∈{0,1})を格納する過程と、(a-3)送信者装置のパリティ系列変換部が、x=(x11,x12,...,xn1,xn2)を用い、u1=(u11,...,un1)を算出する過程と、(a-4)送信者装置のシンドローム計算部が、u1=(u11,...,un1)のシンドロームs1= u1・M1Tを算出する過程と、(a-5)送信者装置の通信部が、シンドロームs1を受信者装置に送信する過程と、(a-6)受信者装置のパリティ系列変換部が、y=(y11,y12,...,yn1,yn2)を用い、v1=(v11,...,vn1)を算出する過程と、(a-7)受信者装置のシンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する過程と、(a-8)受信者装置の加算部が、シンドロームs1とt1の和s1+t1を算出する過程と、(a-9)受信者装置のシンドローム復号部が、シンドロームの和s1+t1を復号してw1を生成する過程と、(a-10)受信者装置の復号部が、v1とw1とからu1=v1+w1を算出する過程と、(b-1)受信者装置の通信部が、w1を送信者装置に送信する過程と、(b-2)送信者装置のビット列分類部が、w1とx=(x11,x12,...,xn1,xn2)とを用い、各u2,Tc(2)を算出する過程と、(b-3)受信者装置のビット列分類部が、w1とy=(y11,y12,...,yn1,yn2)とを用い、各v2,Tc(2)を算出する過程と、(b-4)送信者装置のシンドローム計算部が、u2,T0のシンドロームs2,T0=u2,T0・M2Tを算出する過程と、(b-5)送信者装置の通信部が、シンドロームs2,T0を受信者装置に送信する過程と、(b-6)受信者装置のシンドローム計算部が、v2,T0のシンドロームt2,T0=v2,T0・M2Tを算出する過程と、(b-7)受信者装置の加算部が、シンドロームs2,T0とt2,T0の和s2,T0+t2,T0を算出する過程と、(b-8)受信者装置のシンドローム復号部が、シンドロームの和s2,T0+t2,T0を復号してw2,T0を生成する過程と、(b-9)受信者装置の復号部が、v2,T0とw2,T0とからu2,T0=v2,T0+w2,T0を算出する過程と、送信者装置及び受信者装置の各出力部が、u1とu2,T0との少なくとも一部を共有情報として出力する過程とを実行する。
【００２２】
ここでu2,T1は、u2,T1そのものを送ることなく誤り訂正することができない情報である（詳細は後述）。よって、送信者装置と受信者装置とでu2,T1を共有するためには、送信者装置が受信者装置へu2,T1そのものを送らなければならない。しかし、送信者装置が受信者装置へu2,T1そのものを送ったのではu2,T1の情報が全て盗聴者に漏洩してしまう可能性があるため、誤り訂正ができたとしてもu2,T1を秘密の共有情報として用いることはできない。さらに、u2,T1そのものを送った場合、u2,T1の情報が全て漏洩してしまうだけではなく、u1のビット間の関係からその他のu1に関する情報をも盗聴者に与えてしまう可能性がある。そのため、本発明ではu2,T1の誤り訂正をあきらめ、送信者装置の通信部はu2,T1そのものを受信者装置に送信しない（非特許文献３，４との相違点）。これにより、盗聴者に漏洩する情報量を低減させ、秘密増幅によって捨てられるビット数を減らし、鍵レートを向上させることができる。
【００２３】
また、この場合には、例えば、関数ξ2を任意の(a1,a2)∈F22に対してξ2(a1,a2, 1)=0又はξ2(a1,a2, 1)=1を満たすものとし、送信者装置の出力部がu1とu2,T0の少なくとも一部とu2,T1を共有情報として出力し、受信者装置の出力部がu1とu2,T0の少なくとも一部とv2,T1を共有情報として出力してもよい。この場合、u2,T1=v2,T1=0又は1となり、xのビットそのものの情報が盗聴者に漏洩することはないため、鍵レートを向上させることができる。
【００２４】
また、関数ξ2を任意の(a1,a2)∈F22に対してξ2(a1,a2, 1)=a1又はξ2(a1,a2, 1)=a2を満たすものとし、送信者装置のビット反転部が、u2,T1の各ビット値をランダムに反転させたu2,T1'を生成する過程と、送信者装置の通信部が、u2,T1'を受信者装置に送信する過程と、さらにを実行し、送信者装置及び受信者装置の各出力部が、u1とu2,T0とu2,T1'を共有情報として出力してもよい。この場合、u2,T1'を送信してもu1のその他の情報が漏洩することはないため、鍵レートを向上させることができる。
【発明の効果】
【００２５】
以上のように、本発明では、送受信者で共有する情報の安全性が保障される範囲内で、従来よりも高い鍵レートを実現できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明を実施するための最良の形態を図面を参照して説明する。以下では、まず本発明の一般化した実施形態について説明を行い、その後、各具体例について説明する。
【００２７】
〔一般化した実施形態〕
＜定義＞
まず、本形態で使用する記号を定義する。
【００２８】
F2：位数２の有限体
F2κ：κ(κ≧２)個の有限体F2の直積が成すベクトル空間（F2κ= F2×F2…×F2）
ξ1：ベクトル空間F2κから有限体F2へ移す線形な関数〔F2κ→F2：任意のベクトルa,b∈F2κに対してξ1(a+b)=ξ1(a)+ξ1(b)が成り立つ関数〕
ξr：ベクトル空間F2κとベクトル空間F2r-1(r∈{2,...,κ})との直積がなすベクトル空間から有限体F2へ移す関数であってベクトル空間F2κの要素について線形な関数〔F2κ×F2r-1→F2：任意のベクトルa,b∈F2κと任意のベクトルc∈F2と対してξ1(a+b,c)=ξ1(a,c)+ξ1(b,c)が成り立つ関数〕
x：x=(x11,...,x1κ,...,xn1,...,xnκ)(xik∈{0,1},i∈{1,...,n},n≧１,k∈{1,...,κ})
y：y=(y11,...,y1κ,...,yn1,...,ynκ)(yik∈{0,1})
u：u=(u11,...,u1κ,...,un1,...,unκ)(uik∈{0,1})
v：v=(v11,...,v1κ,...,vn1,...,vnκ)(vik∈{0,1})
w：w=(w11,...,w1κ,...,wn1,...,wnκ)(wik∈{0,1})
ui1：ui1=ξ1(xi1,...,xiκ)
vi1：vi1=ξ1(yi1,...,yiκ)
wi1：wi1=ui1+vi1
uir：uir=ξr(xi1,...,xiκ, wi1,...,wi(r-1))
vir：vir=ξr(yi1,...,yiκ, wi1,...,wi(r-1))
wir：wir=uir+vir
uj：uj=(u1j,...,unj) (j∈{1,...,κ})
vj：vj=(v1j,...,vnj)
wj：wj=(w1j,...,wnj)
wir-1：wir-1=(wi1,...,wi(r-1))
Tc(r)：Tc(r)={i|1≦i≦n, wir-1=c(r)}(c(r)∈F2r-1)
ur,Tc(r)：urのうち、i∈Tc(r)を満たすビットからなる部分列
vr,Tc(r)：vrのうち、i∈Tc(r)を満たすビットからなる部分列
wr,Tc(r)：wrのうち、i∈Tc(r)を満たすビットからなる部分列
Mj：送信者装置と受信者装置との間で共有されるパリティ検査行列
・Ｔ：・の転置行列
＜構成＞
図１は、本形態の構成を説明するためのブロック図である。以下、この図を用いて本形態の構成を説明する。
【００２９】
本形態では、図１に例示する送信者装置１０と受信者装置２０との間で情報共有化を行う。送信者装置１０及び受信者装置２０は、それぞれ、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等からなるノイマン型のコンピュータに所定のプログラムが読み込まれることにより構成される。
【００３０】
図１に例示するように、送信者装置１０は、記憶部１０ａと、パリティ系列変換部１０ｂと、シンドローム計算部１０ｃ，１０ｅと、ビット列分割部１０ｄと、通信部１０ｆと、出力部１０ｇと、制御部１０ｈと、一時メモリ１０ｉとを有する。また、図１に例示するように、受信者装置２０は、記憶部２０ａと、パリティ系列変換部２０ｂと、シンドローム計算部２０ｃ，２０ｈと、加算部２０ｄ，２０ｉと、シンドローム復号部２０ｅ，２０ｊと、復号部２０ｆ，２０ｋと、通信部２０ｍと、出力部２０ｎと、制御部２０ｐと、一時メモリ２０ｑとを有する。また、送信者装置１０と受信者装置２０とは、インターネット等の公開通信路によって接続されているが、公開通信路で通信される情報は、盗聴者に盗聴されている可能性がある。
【００３１】
なお、記憶部１０ａ，２０ａ及び一時メモリ１０ｉ，２０ｑは、例えば、ＲＡＭ、レジスタ、ハードディスク等の補助記憶装置、或いはこれらを結合した記憶領域に相当する。また、通信部１０ｆ，２０ｍは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するネットワークカード等である。また、図１のその他の構成ブロックは、例えば、それぞれの処理を実現するためのプログラムがＣＰＵに読み込まれることにより構成される。
【００３２】
＜情報整合化処理＞
図２，３は、本形態の情報整合化処理を説明するためのシーケンス図である。以下、これらの図を用いて本形態の情報整合化処理を説明する。なお、以下では説明を省略するが、送信者装置１０及び受信者装置２０は、それぞれ、制御部１０ｈ及び２０ｐの制御のもと各処理を実行する。また、特に明示しない限り、送信者装置１０は、演算過程の各データを逐一一時メモリ１０ｉに読み書きし、受信者装置２０は、演算過程の各データを逐一一時メモリ２０ｑに読み書きする。
【００３３】
＜前処理＞
シンドローム計算部１０ｃ，２０ｃ及びシンドローム復号部２０ｅは、nビットの線形符号とそのパリティ検査行列M1とを共用し、それらを利用可能に構成される。また、シンドローム計算部１０ｅ，２０ｈ及びシンドローム復号部２０ｊは、nr’ビットの線形符号とそのパリティ検査行列Mrとを共用し、それらを利用可能に構成される。なお、nr’はur,Tc(r)やvr,Tc(r) のビット長を示す。ur,Tc(r)やvr,Tc(r) のビット長は処理の出力に応じて変化する。そのため、取り得る様々のnr’の線形符号とそのパリティ検査行列Mrとを共用しておくか、或いは共用しておいたビット長の線形符号を短縮・拡張してnr’ビットの線形符号とそのパリティ検査行列Mrとを共用することにしてもよい。
【００３４】
また、共有される線形符号のレート等は、情報配信を行う量子通信路でのエラーレートに基づいて決定される。すなわち、線形符号の次元をεとし、エラーレートをｅとし、線形符号のビット長で取り得る全空間の次元をσとし、確率p(0≦p≦1)のバイナリエントロピーをh(p)=-p・logp-(1-p)・log(1-p)とした場合に、
ε/σ≦1-h(e2+(1-e)2)  …(1)
を満たすように線形符号を決定する。
【００３５】
＜量子ビットを用いた情報配送処理＞
送信者装置１０が、量子ビットを用いた情報配送処理（例えば、BB84プロトコルやsix-stateプロトコル等）によりビット列x=(x11,...,x1κ,...,xn1,...,xnκ)を受信者装置２０に送信する。これによって、受信者装置２０はビット列y=(y11,...,y1κ,...,yn1,...,ynκ)を受信する。なお、送信者装置１０から受信者装置２０に配送される情報としては、例えば共通鍵等を例示できるが、必ずしもこれに限定されるものではない。
【００３６】
＜情報整合化処理＞
情報整合化処理では、まず、送信者装置１０にビット列x=(x11,...,x1κ,...,xn1,...,xnκ)が入力され、当該ビット列xが記憶部１０ａに格納される（ステップＳ１）。また、受信者装置２０にビット列y=(y11,...,y1κ,...,yn1,...,ynκ)が入力され、当該ビット列yが記憶部２０ａに格納される（ステップＳ２）。
【００３７】
次に、送信者装置１０のパリティ系列変換部１０ｂが、記憶部１０ａから読み込んだビット列x=(x11,...,x1κ,...,xn1,...,xnκ)を用い、ui1=ξ1(xi1,...,xiκ)によってu1=(u11,...,un1)を算出する（ステップＳ３）。次に、シンドローム計算部１０ｃにu1=(u11,...,un1)が入力され、シンドローム計算部１０ｃが、u1=(u11,...,un1)のシンドロームs1=u1・M1Tを算出する（ステップＳ４）。そして、通信部１０ｆが、シンドロームs1を受信者装置２０に送信する（ステップＳ５）。送信されたシンドロームs1は受信者装置２０の通信部２０ｍで受信され、加算部２０ｄに送られる。
【００３８】
また、受信者装置２０のパリティ系列変換部２０ｂが、記憶部２０ａから読み込んだy=(y11,...,y1κ,...,yn1,...,ynκ)を用い、vi1=ξ1(yi1,...,yiκ)によってv1=(v11,...,vn1)を算出する（ステップＳ６）。次に、シンドローム計算部２０ｃにv1=(v11,...,vn1)が入力され、シンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する（ステップＳ７）。次に、加算部２０ｄにシンドロームs1とt1が入力され、加算部２０ｄがシンドロームs1とt1の和s1+t1を算出する（ステップＳ８）。シンドロームの和s1+t1はシンドローム復号部２０ｅに入力され、シンドローム復号部２０ｅは、シンドロームの和s1+t1を復号してw1を生成する（ステップＳ９）。復号方法としては、例えば最小復号法を用いる。最小復号法を用いる場合には、
A(s1+t1)={ω∈F2n|ω・M1T=s1+t1) …(2)
の集合A(s1+t1)の中から大きさが最少となる元をw1として選択する。これは、u1とv1との食い違いを最小とする元をw1として選択することに相当する。このような復号が可能なのは、u1の各ビットとv1の各ビットとが一致する確率よりも、これらが食い違う確率のほうが遙かに小さいと仮定できるからである。
【００３９】
次に、パリティ系列変換部２０ｂで算出されたv1と、シンドローム復号部２０ｅで復号されたw1とが復号部２０ｆに入力され、復号部２０ｆが、v1とw1とからu1=v1+w1を算出する（ステップＳ１０）。
【００４０】
その後、受信者装置２０の制御部２０ｐが変数ｒに２を代入し、変数r=2を一時メモリ２０ｑに格納する（ステップＳ１１）。
【００４１】
次に、通信部２０ｍにwr-1,Tc(r-1)(w1,Tc(1)=w1)が入力され、通信部２０ｍが、wr-1,Tc(r-1)(w1,Tc(1)=w1)を送信者装置１０に送信する（ステップＳ１２）。送信されたwr-1,Tc(r-1)は、送信者装置１０の通信部１０ｆで受信され、ビット列分類部１０ｄに入力される。
【００４２】
ビット列分類部１０ｄには、さらに記憶部１０ａからx=(x11,...,x1κ,...,xn1,...,xnκ)が読み込まれ、ビット列分類部１０ｄは、wr-1,Tc(r-1)(w1,Tc(1)=w1)とx=(x11,...,x1κ,...,xn1,...,xnκ)とを用い、各ur,Tc(r)を算出する。すなわち、ビット列分類部１０ｄは、wr-1,Tc(r-1)(w1,Tc(1)=w1)とx=(x11,...,x1κ,...,xn1,...,xnκ)とを用い、uir=ξr(xi1,...,xiκ, wi1,...,wi(r-1))によってur=(u1r,...,unr)を求め、urのうち、i∈Tc(r)〔Tc(r)={i|1≦i≦n, wir-1=c(r)}(c(r)∈F2r-1), wir-1=(wi1,...,wi(r-1))〕を満たすビットからなる各部分列をur,Tc(r)とする（ステップＳ１３）。
【００４３】
同様に、受信者装置２０のビット列分類部２０ｇに、シンドローム復号部２０ｊ（又は２０ｅ）で算出されたwr-1,Tc(r-1)(w1,Tc(1)=w1)と、記憶部２０ａから読み出されたy=(y11,...,y1κ,...,yn1,...,ynκ)とが入力され、ビット列分類部２０ｇは、これらを用い、各vr,Tc(r)を算出する（ステップＳ１４）。
【００４４】
また、送信者装置１０のシンドローム計算部１０ｅにur,Tc(r)が入力され、シンドローム計算部１０ｅは、各ur,Tc(r)のシンドロームsr,Tc(r)=ur,Tc(r)・MrTを算出する（ステップＳ１５）。算出されたシンドロームsr,Tc(r)は、通信部１０ｆによって受信者装置２０に送信され（ステップＳ１６）、受信者装置２０の通信部２０ｍで受信される。
【００４５】
また、受信者装置２０のシンドローム計算部２０ｈにvr,Tc(r)が入力され、シンドローム計算部２０ｈが、vr,Tc(r)のシンドロームtr,Tc(r)=vr,Tc(r)・MrTを算出する（ステップＳ１７）。その後、加算部２０ｉに、通信部２０ｍで受信されたシンドロームsr,Tc(r)と、シンドローム計算部２０ｈで算出されたシンドロームtr,Tc(r)とが入力され、加算部２０ｉが、シンドロームsr,Tc(r)とtr,Tc(r)の和sr,Tc(r)+tr,Tc(r)を算出する（ステップＳ１８）。次に、シンドローム復号部２０ｊにシンドロームの和sr,Tc(r)+tr,Tc(r)が入力され、シンドローム復号部２０ｊが、シンドロームの和sr,Tc(r)+tr,Tc(r)を復号してwr,Tc(r)を生成する（ステップＳ１９）。なお、復号できないシンドロームの和sr,Tc(r)+tr,Tc(r)が存在する場合、シンドローム復号部２０ｊはその復号を行わないこととしてもよいし、復号できないシンドロームの和sr,Tc(r)+tr,Tc(r)に対応するシンドロームsr,Tc(r)を生成・送信しないこととしてもよい。なお、シンドロームの和sr,Tc(r)+tr,Tc(r)が復号できない場合とは、ur,Tc(r)の各ビットとvr,Tc(r)の各ビットとが一致する確率とこれらが食い違う確率とが同程度のため解（復号結果）が定まらない場合を意味する（最小復号法の説明参照）。
【００４６】
その後、シンドローム復号部２０ｊで復号されたwr,Tc(r)と、ビット列分類部２０ｇで算出されたvr,Tc(r)とが復号部２０ｋに入力され、復号部２０ｋが、vr,Tc(r)とwr,Tc(r)とからur,Tc(r)=vr,Tc(r)+wr,Tc(r)を算出する（ステップＳ２０）。
【００４７】
次に、制御部２０ｐが一時メモリ２０ｑに格納された変数ｒがκであるか否かを判定する（ステップＳ２１）。ここで、変数ｒ=κでなければ、制御部２０ｐはr=r+κとした変数ｒを一時メモリ２０ｑに上書きし、処理をステップＳ１２に戻す。一方、変数ｒ=κであれば、送信者装置１０及び受信者装置２０の各出力部１０ｇ，２０ｎが、u1とur,Tc(r) (r∈{2,...,κ})を共有情報として出力する。或いは、u1とur,Tc(r) (r∈{2,...,κ})との一部のみを共有情報として出力してもよい。
なお、以上の処理において送信者装置１０の通信部１０ｆは、ur,Tc(r)そのものを受信者装置２０に送信しない。
【００４８】
＜秘密増幅処理＞
その後、送信者装置１０及び受信者装置２０からそれぞれ共有情報として出力された各情報に対し、秘密増幅処理が実行され、これにより安全性が向上された情報（例えば秘密鍵）が共有される。
【００４９】
〔κ=２の具体例〕
次に、κ=２とした場合の具体例を説明する。その他の定義は前述した〔一般化した実施形態〕の通りである。
ただし、この例では、関数ξ1は任意のa1,a2∈F2に対してξ1(a1,a2)=a1+a2を満たし、関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 0)=a1を満たし、ξ2(a1,a2, 1)=0を満たすものとする。なお、これは一例であって、関数ξ2は任意の(a1,a2)∈F22に対してξ2(a1,a2, 0)=a2を満たすものであってもよいし、ξ2(a1,a2, 1)=1を満たすものであってもよい。また、前述の関数ξ1の定義を満たし、なおかつ、任意のa1,a2∈F2に対してξ1(a1,a2)=a1+a2を満たす関数ξ1としては、例えばa1とa2との排他的論理和関数を例示できる。
【００５０】
図４は、κ=２とした場合の具体例を説明するための送信者装置１０と受信者装置２０のブロック図である。また、図５，６は、κ=２とした場合の具体例を説明するためのシーケンス図である。
【００５１】
構成、前処理、量子ビットを用いた情報配送処理、秘密増幅処理については、前述した〔一般化した実施形態〕のとおりであるため説明を省略する。以下では、κ=２とした場合の情報整合化処理のみを説明する。
【００５２】
＜κ=２とした場合の情報整合化処理＞
κ=２の場合、ビット列x=(x11,x12,...,xn1,xn2)(xik∈{0,1})となり、y=(y11,y12,...,yn1,yn2)(yik∈{0,1})となる。まず、送信者装置１０にビット列x=(x11,x12,...,xn1,xn2)が入力され、当該ビット列xが記憶部１０ａに格納される（ステップＳ３１）。また、受信者装置２０にビット列y=(y11,y12,...,yn1,yn2)が入力され、当該ビット列yが記憶部２０ａに格納される（ステップＳ３２）。例えば、n=11の場合の一例として、x=(0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,1,0,1,1,0,1,0)が記憶部１０ａに格納され、y=(0,1,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0)が記憶部２０ａに格納される。
【００５３】
次に、送信者装置１０のパリティ系列変換部１０ｂが、記憶部１０ａから読み込んだビット列x=(x11,x12,...,xn1,xn2)を用い、ui1=ξ1(xi1,xi2)によってu1=(u11,...,un1)を算出する（ステップＳ３３）。例えば、x=(0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,1,0,1,1,0,1,0)であり、関数ξ1が排他的論理和関数であった場合、u1=(1,1,0,0,1,0,0,0,1,1,1)が算出される。
【００５４】
次に、シンドローム計算部１０ｃにu1=(u11,...,un1)が入力され、シンドローム計算部１０ｃが、u1=(u11,...,un1)のシンドロームs1=u1・M1Tを算出する（ステップＳ３４）。例えば、u1=(1,1,0,0,1,0,0,0,1,1,1)であり、パリティ検査行列M1が、
【００５５】
【数２】
2008288665.tif 000004
であった場合、シンドロームs1=(0,1,0,1,1,0,0,1,0,0)が算出される。
【００５６】
算出されたシンドロームs1は、通信部１０ｆによって受信者装置２０に送信される（ステップＳ３５）。送信されたシンドロームs1は受信者装置２０の通信部２０ｍで受信され、加算部２０ｄに送られる。
【００５７】
また、受信者装置２０のパリティ系列変換部２０ｂが、記憶部２０ａから読み込んだy=(y11,y12,...,yn1,yn2)を用い、vi1=ξ1(yi1,yi2)によってv1=(v11,...,vn1)を算出する（ステップＳ３６）。例えば、y=(0,1,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0)であり、関数ξ1が排他的論理和関数であった場合、v1=(1,0,0,1,1,0,0,0,0,0,1)が算出される。
【００５８】
次に、シンドローム計算部２０ｃにv1=(v11,...,vn1)が入力され、シンドローム計算部が、v1=(v11,...,vn1)のシンドロームt1=v1・M1Tを算出する（ステップＳ３７）。例えば、v1=(1,0,0,1,1,0,0,0,0,0,1)であり、パリティ検査行列M1が式（３）の行列であった場合、シンドロームt1=(1,0,1,0,1,0,0,0,0,1)が算出される。
【００５９】
次に、加算部２０ｄにシンドロームs1とt1が入力され、加算部２０ｄがシンドロームs1とt1の和s1+t1を算出する（ステップＳ３８）。例えば、シンドロームs1=(0,1,0,1,1,0,0,1,0,0)であり、シンドロームt1=(1,0,1,0,1,0,0,0,0,1)であり、関数ξ1が排他的論理和関数であった場合、s1とt1とのビット毎の排他的論理和（1,1,1,1,0,0,0,1,0,1）が算出される。
【００６０】
シンドロームの和s1+t1はシンドローム復号部２０ｅに入力され、シンドローム復号部２０ｅは、シンドロームの和s1+t1を復号してw1を生成する（ステップＳ３９）。復号方法としては、例えば最小復号法を用いる。s1とt1とのビット毎の排他的論理和（1,1,1,1,0,0,0,1,0,1）を式（３）のパリティ検査行列M1を用いて復号した場合、w1=(0,1,0,1,0,0,0,0,1,1,0)となる。w1=(0,1,0,1,0,0,0,0,1,1,0)は、u1=(1,1,0,0,1,0,0,0,1,1,1)とv1=(1,0,0,1,1,0,0,0,0,0,1)との排他的論理和となっている。すなわち、w1の各ビットは、u1の各ビットとv1の各ビットとが同一であるか（w1のビット値「0」）異なっているか（w1のビット値「1」）を示している。つまり、w1の各ビットは、xのパリティ列u1とyのパリティ列v1との一致・不一致をパリティビット毎に示している。
【００６１】
次に、パリティ系列変換部２０ｂで算出されたv1と、シンドローム復号部２０ｅで復号されたw1とが復号部２０ｆに入力され、復号部２０ｆが、v1とw1とからu1=v1+w1を算出する（ステップＳ４０）。例えば、関数ξ1が排他的論理和関数であり、v1=(1,0,0,1,1,0,0,0,0,0,1)、w1=(0,1,0,1,0,0,0,0,1,1,0)であった場合、それらのビット毎の排他的論理和u1=(1,1,0,0,1,0,0,0,1,1,1)が算出される。
【００６２】
次に、通信部２０ｍにw1が入力され、通信部２０ｍが、w1を送信者装置１０に送信する（ステップＳ４１）。送信されたw1は、送信者装置１０の通信部１０ｆで受信され、ビット列分類部１０ｄに入力される。
【００６３】
ビット列分類部１０ｄには、さらに記憶部１０ａからx=(x11,x12,...,xn1,xn2)が読み込まれ、ビット列分類部１０ｄは、w1とx=(x11,x12,...,xn1,xn2)とを用い、各u2,Tc(2)を算出する（ステップＳ４２）。すなわち、ビット列分類部１０ｄは、w1とx=(x11,x12,...,xn1,xn2)とを用い、ui2=ξ2(xi1,xi2, wi1)によってu2=(u12,...,un2)を求め、u2のうち、i∈Tc(2)〔Tc(2)={i|1≦i≦n, wi1=c(2)}(c(2)∈F2), wi1=(wi1)〕を満たすビットからなる各部分列をu2,Tc(2)とする。例えば、w1=(0,1,0,1,0,0,0,0,1,1,0)であり、x=(0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,1,0,1,1,0,1,0)であり、ξ2(a1,a2, 0)=a1及びξ2(a1,a2, 1)=0である場合、ビット列分類部１０ｄは、まず、ui2=ξ2(xi1,xi2, wi1)によってu2=(0,0,1,0,1,0,0,1,0,0,1)を求める。次にビット列分類部１０ｄは、u2のうち、i∈T0〔T0={i|1≦i≦n, wi1=0}を満たすビットからなる部分列u2,T0=(0,1,1,0,0,1,1)と、u2のうち、i∈T1〔T1={i|1≦i≦n, wi1=1}を満たすビットからなる部分列u2,T1=(0,0,0,0)とを求める。
【００６４】
また、受信者装置２０のビット列分類部２０ｇに、シンドローム復号部２０ｅで算出されたw1と、記憶部２０ａから読み出されたy=(y11,y12,...,yn1,yn2)とが入力され、ビット列分類部２０ｇは、これらを用い、各v2,Tc(2)を算出する（ステップＳ４３）。すなわち、ビット列分類部２０ｇは、w1とy=(y11,y12,...,yn1,yn2)を用い、vi2=ξ2(yi1,yi2, wi1)によってv2=(v12,...,vn2)を求め、v2のうち、i∈Tc(2)〔Tc(2)={i|1≦i≦n, wi1=c(2)}(c(2)∈F2), wi1=(wi1)〕を満たすビットからなる各部分列をv2,Tc(2)とする。例えば、w1=(0,1,0,1,0,0,0,0,1,1,0)であり、y=(0,1,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0)であり、ξ2(a1,a2, 0)=a1及びξ2(a1,a2, 1)=0である場合、ビット列分類部２０ｇは、まず、vi2=ξ2(yi1,yi2, wi1)によってv2=(0,0,1,0,1,1,0,1,0,0,1)を求める。次にビット列分類部２０ｇは、v2のうち、i∈T0〔T0={i|1≦i≦n, wi1=0}を満たすビットからなる部分列v2,T0=(0,1,1,1,0,1,1)と、v2のうち、i∈T1〔T1={i|1≦i≦n, wi1=1}を満たすビットからなる部分列v2,T1=(0,0,0,0)とを求める。
【００６５】
なお、wi1=1の場合、ui1=ξ1(xi1,xi2)とvi1=ξ1(yi1,yi2)とは相違している（誤りが生じている）。しかし、その誤り方には偏りはない。例えば、(xi1,xi2)=(0,0)及び(yi1,yi2)=(1,0)であるためにwi1=1となる確率と、(xi1,xi2)=(1,0)及び(yi1,yi2)=(1,1)であるためにwi1=1となるとは等しい。そのため、wi1=1となるビット列(xi1,xi2)と(yi1,yi2)との誤り訂正を、シンドロームを用いて行うことはできない（最小復号法の説明参照）。これらの誤り訂正を行う場合には、ビットそのもの（例えばxi1）を送信者装置１０から受信者装置２０に送信しなければならない。しかし、ビットそのものを送信したのでは盗聴者にｘの情報の一部が漏えいしてしまう。そのため、本実施例では、wi1=1となるビット列(xi1,xi2)及び(yi1,yi2)の誤り訂正を行わず、これらを共有情報とはしない。これにより、漏えい情報量を低減させ、後段の秘密増幅によって削除されるビット数を減らし、鍵レートを向上させる。なお、本実施例ではξ2(a1,a2, 1)=0とすることによって、wi1=1となるビット列(xi1,xi2)及び(yi1,yi2)に対応するu2,T1及びv2,T1を共にゼロベクトルとしているが、u2,T1及びv2,T1を破棄するのであればξ2(a1,a2, 1)=a1であってもξ2(a1,a2, 1)=a2であってもかまわない。
【００６６】
次に、送信者装置１０のシンドローム計算部１０ｅにu2,T0が入力され、シンドローム計算部１０ｅは、u2,T0のシンドロームs2,T0=u2,T0・M2Tを算出する（ステップＳ４４）。例えば、u2,T0=(0,1,1,0,0,1,1)であり、パリティ検査行列M2が、
【００６７】
【数３】
2008288665.tif 000005
である場合、s2,T0=(0,0,0)が算出される。
【００６８】
算出されたシンドロームs2,T0は、通信部１０ｆによって受信者装置２０に送信され（ステップＳ４５）、受信者装置２０の通信部２０ｍで受信される。
【００６９】
また、受信者装置２０のシンドローム計算部２０ｈにv2,T0が入力され、シンドローム計算部２０ｈが、v2,T0のシンドロームt2,T0=v2,T0・M2Tを算出する（ステップＳ４６）。v2,T0=(0,1,1,1,0,1,1) であり、パリティ検査行列M2が式（４）に示す行列である場合、t2,T0=(0,1,1)が算出される。
【００７０】
その後、加算部２０ｉに、通信部２０ｍで受信されたシンドロームs2,T0と、シンドローム計算部２０ｈで算出されたシンドロームt2,T0とが入力され、加算部２０ｉが、シンドロームs2,T0とt2,T0の和s2,T0+t2,T0を算出する（ステップＳ４７）。例えば、s2,T0=(0,0,0)であり、t2,T0=(0,1,1)である場合、(0,1,1)が算出される。
【００７１】
次に、シンドローム復号部２０ｊにシンドロームの和s2,T0+t2,T0が入力され、シンドローム復号部２０ｊが、シンドロームの和s2,T0+t2,T0を復号してw2,T0を生成する（ステップＳ４８）。例えば、シンドロームの和が(0,1,1)である場合、w2,T0=(0,0,0,1,0,0,0)が生成される。
【００７２】
その後、シンドローム復号部２０ｊで復号されたw2,T0と、ビット列分類部２０ｇで算出されたv2,T0とが復号部２０ｋに入力され、復号部２０ｋが、v2,T0とw2,T0とからu2,T0=v2,T0+w2,T0を算出する（ステップＳ４９）。例えば、v2,T0=(0,1,1,1,0,1,1)であり、w2,T0=(0,0,0,1,0,0,0)である場合、u2,T0=(0,1,1,0,0,1,1)を算出する。
【００７３】
そして、送信者装置１０及び受信者装置２０の各出力部１０ｇ，２０ｎが、u1とu2,T0とを共有情報として出力する（ステップＳ５０、５１）。なお、送信者装置１０及び受信者装置２０の各出力部１０ｇ，２０ｎが、u1とu2,T0との一部のみを共有情報として出力することとしてもよいし、送信者装置１０の出力部１０ｇがu1とu2,T0（又それらの一部）とu2,T1=(0,...,0)を共有情報として出力し、受信者装置２０の出力部２０ｎがu1とu2,T0（又それらの一部）とv2,T1=(0,...,0)を共有情報として出力することとしてもよい。
【００７４】
また、関数ξ2を任意の(a1,a2)∈F22に対してξ2(a1,a2, 1)=a1又はξ2(a1,a2, 1)=a2を満たすものとし、送信者装置１０が、u2,T1の各ビット値をランダムに反転させたu2,T1'を生成し、これを受信者装置２０と共有する手順でもよい。
【００７５】
図７は、この変形例を説明するための送信者装置２１０と受信者装置２２０のブロック図である。また、図８は、この変形例を説明するためのシーケンス図である。
【００７６】
この変形例の送信者装置２１０は、前述の送信者装置１０にビット反転部２１０ｊを追加したものであり、その他の構成は送信者装置１０と同じである。また、受信者装置２２０は、u2,T1の各ビット値をランダムに反転させたu2,T1'を送信者装置２１０から受信し、出力する点のみが受信者装置２０と相違する。
【００７７】
この変形例の場合、前述と同様にステップＳ３１〜Ｓ４９の処理を実行した後、送信者装置のビット反転部２１０ｊが、ビット列分類部１０ｄで生成されたu2,T1の各ビット値をランダムに反転させたu2,T1'を生成し（ステップＳ７０）、通信部１０ｆと出力部１０ｇに送られる。通信部１０ｆはu2,T1'を受信者装置２２０に送信する（ステップＳ７１）。送信されたu2,T1'は受信者装置２２０の通信部２０ｍに受信され、出力部２０ｎに送られる。その後、送信者装置２１０及び受信者装置２２０の各出力部１０ｇ，２０ｎは、u1とu2,T0とu2,T1'を共有情報として出力する（ステップＳ７２，７３）。
【００７８】
〔本形態の情報整合化の性能〕
次に、非特許文献１〜４の情報整合化と比較することによって本形態の情報整合化の性能を示す。
まず、各情報整合化を行った場合において、安全性が保たれる(ε-secure)範囲内での鍵レートの最大値KRmaxは以下の式で示される。
【００７９】
＜本形態の情報整合化（κ=2）を行った場合の鍵レートの最大値KRmax＞
【数４】
2008288665.tif 000006
【００８０】
＜非特許文献１の情報整合化を行った場合の鍵レートの最大値KRmax＞
【数５】
2008288665.tif 000007
【００８１】
＜非特許文献２の情報整合化を行った場合の鍵レートの最大値KRmax＞
【数６】
2008288665.tif 000008
【００８２】
＜非特許文献３，４の情報整合化を行った場合の鍵レートの最大値KRmax＞
【数７】
2008288665.tif 000009
図９は、本形態の情報整合化を行った場合と非特許文献１〜４の情報整合化を行った場合とでの鍵レートの違いを示したグラフである。ここで、図９（ａ）は、six-stateプロトコルにおける比較であり、図９（ｂ）は、BB84プロトコルにおける比較である。また、これらのグラフの横軸はエラーレートを示し、縦軸は鍵レートを示している。
【００８３】
これらのグラフから分かるように、本形態の情報整合化を行った場合、非特許文献１〜４の情報整合化を行った場合よりも鍵レートが向上する。また、本形態の情報整合化の方法では、非特許文献３と４のように送信者装置と受信者装置とで暗号情報をやり取りする必要がないため、暗号化のための鍵を事前に共有しておく必要もない。
【００８４】
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００８６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９０】
本発明の産業上の利用分野としては、例えば、共通鍵暗号の鍵配送等を例示できる。
【図面の簡単な説明】
【００９１】
【図１】図１は、本形態の構成を説明するためのブロック図である。
【図２】図２は、本形態の情報整合化処理を説明するためのシーケンス図である。
【図３】図３は、本形態の情報整合化処理を説明するためのシーケンス図である。
【図４】図４は、κ=２とした場合の具体例を説明するための送信者装置と受信者装置のブロック図である。
【図５】図５は、κ=２とした場合の具体例を説明するためのシーケンス図である。
【図６】図６は、κ=２とした場合の具体例を説明するためのシーケンス図である。
【図７】図７は、変形例を説明するための送信者装置と受信者装置のブロック図である。
【図８】図８は、変形例を説明するためのシーケンス図である。
【図９】図９は、本形態の情報整合化を行った場合と非特許文献１〜４の情報整合化を行った場合とでの鍵レートの違いを示したグラフである。
【図１０】図１０は、非特許文献３，４の情報整合化方法を説明するためのシーケンス図である。
【図１１】図１１は、非特許文献３，４の情報整合化方法を説明するためのシーケンス図である。
【符号の説明】
【００９２】
１０，２１０  送信者装置
２０，２２０  受信者装置
【図１】
2008288665.tif 000010
【図２】
2008288665.tif 000011
【図３】
2008288665.tif 000012
【図４】
2008288665.tif 000013
【図５】
2008288665.tif 000014
【図６】
2008288665.tif 000015
【図７】
2008288665.tif 000016
【図８】
2008288665.tif 000017
【図９】
2008288665.tif 000018
【図１０】
2008288665.tif 000019
【図１１】
2008288665.tif 000020