(57)【特許請求の範囲】
【請求項１】
データ分散装置とデータ復元装置を含む秘密分散システムであって、
M,Nは2以上の整数であり、M’は0以上の整数であり、M’≦M<Nであるとして、
前記データ分散装置は、
秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成する暗号化部と、
前記暗号文CをM個の分割値C0,…,CM-1に分割する暗号文分割部と、
次式で定義される多項式g(x)をx=1,…,N-Mについてそれぞれ計算することで、N-M個の分散値D1,…,DN-Mを生成する暗号文分散部と、
【数１４】
0005732429.tif 000014
N個の分散値のうちM個以上の分散値を用いれば元のデータを復元でき、M個未満の分散値からは元のデータを復元できない秘密分散方式に従って、前記秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する鍵分散部と、
前記分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、前記分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とし、分散値Ti(C)(i=1,…,N)と分散値Si(SK)(i=1,…,N)を組にして分散値U1(A),…,UN(A)を生成する分散値生成部と、
を備え、
前記データ復元装置は、
M'を前記分散値T1(C),…,TN-M(C)のうち前記分散値U1(A),…,UN(A)から任意に選択されたM個の分散値U'1(A),…,U'M(A)に含まれるものの数とし、
M'>0であれば、前記分散値T1(C),…,TN-M(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM'個の分散値T'1(C),…,T'M'(C)を分散値D'1,…,D'M'として抽出し、
M-M'>0であれば、前記分散値TN-M+1(C),…,TN(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM-M'個の分散値T'M'+1(C),…,T'M(C)を分割値C'0,…,C'M-M'-1として抽出する分割暗号文抽出部と、
前記分割値C0,…,CM-1のいずれかが前記分割値C'0,…,C'M-M'-1に含まれない場合には、前記多項式g(x)を、前記分割値C'0,…,C'M-M'-1に含まれるM-M'個の分割値Ci(1≦i≦M-1)を定数とし、前記分割値C'0,…,C'M-M'-1に含まれないM'個の分割値Cj(1≦j≦M-1)を変数とし、前記分散値D'1,…,D'M'を求めたxそれぞれを代入したM'個の方程式からなる連立方程式として解くことで、前記分割値C0,…,CM-1を補間する分割暗号文補間部と、
前記分割値C0,…,CM-1を結合して前記暗号文Cを得る暗号文結合部と、
前記秘密分散方式に従って、前記分散値U'1(A),…,U'M(A)に含まれる分散値S'1(SK),…,S'M(SK)から、前記秘密鍵SKを復元する鍵復元部と、
前記秘密鍵SKを用いて前記暗号文Cを復号し、前記平文Aを得る復号部と、
を備えることを特徴とする秘密分散システム。
【請求項２】
請求項１に記載の秘密分散システムであって、
pは前記平文Aより大きいN以上の素数であるとして、
前記暗号化部は、
R1,…,RM-1は固定長の乱数であり、V(R1),…,V(RM-1)は乱数R1,…,RM-1をシードとする0以上p未満の整数である擬似乱数であり、h(x)はh(0)=Aかつh(i)=V(Ri)(i=1,…,M-1)である多項式であり、h(M) mod pを計算することで前記暗号文Cを生成し、
前記鍵分散部は、
所定の秘密分散方式に従って、前記乱数R1,…,RM-1それぞれをN個の分散値S1(Ri),…,SN(Ri)(i=1,…,M-1)に分散し、
前記分散値生成部は、
前記分散値Ti(C)(i=1,…,N)と前記分散値Si(R1),…,Si(RM-1)(i=1,…,N)を組にして前記分散値U1(A),…,UN(A)を生成し、
前記鍵復元部は、
前記秘密分散方式に従って、前記分散値U'1(A),…,U'M(A)に含まれる分散値S'1(Ri),…,S'N(Ri)(i=1,…,M-1)から、前記乱数R1,…,RM-1をそれぞれ復元し、
前記復号部は、
前記乱数R1,…,RM-1から前記擬似乱数V(R1),…,V(RM-1)を生成し、h(i)=V(Ri)(i=1,…,M-1)およびh(M)=Cよりh(0)を求めることで、前記平文Aを得る
ことを特徴とする秘密分散システム。
【請求項３】
M,Nは2以上の整数であり、M<Nであるとして、
秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成する暗号化部と、
前記暗号文CをM個の分割値C0,…,CM-1に分割する暗号文分割部と、
次式で定義される多項式g(x)をx=1,…,N-Mについてそれぞれ計算することで、N-M個の分散値D1,…,DN-Mを生成する暗号文分散部と、
【数１５】
0005732429.tif 000015
N個の分散値のうちM個以上の分散値を用いれば元のデータを復元でき、M個未満の分散値からは元のデータを復元できない秘密分散方式に従って、前記秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する鍵分散部と、
前記分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、前記分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とし、分散値Ti(C)(i=1,…,N)と分散値Si(SK)(i=1,…,N)を組にして分散値U1(A),…,UN(A)を生成する分散値生成部と、
を備えることを特徴とするデータ分散装置。
【請求項４】
M,Nは2以上の整数であり、M’は0以上の整数であり、M’≦M<Nであるとして、
秘密鍵SKを用いて平文Aを暗号化した暗号文Cを分割した分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とし、次式で定義される多項式g(x)をx=1,…,N-Mについてそれぞれ計算することで生成した分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、
【数１６】
0005732429.tif 000016
N個の分散値のうちM個以上の分散値を用いれば元のデータを復元でき、M個未満の分散値からは元のデータを復元できない秘密分散方式に従って前記秘密鍵SKを分散した値を分散値S1(SK),…,SN(SK)とし、分散値Ti(C)(i=1,…,N)と分散値Si(SK)(i=1,…,N)を組にした分散値U1(A),…,UN(A)から任意に選択されたM個の分散値を分散値U'1(A),…,U'M(A)とし、
M'を前記分散値T1(C),…,TN-M(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるものの数とし、
M'>0であれば、前記分散値T1(C),…,TN-M(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM'個の分散値T'1(C),…,T'M'(C)を分散値D'1,…,D'M'として抽出し、
M-M'>0であれば、前記分散値TN-M+1(C),…,TN(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM-M'個の分散値T'M'+1(C),…,T'M(C)を分割値C'0,…,C'M-M'-1として抽出する分割暗号文抽出部と、
前記分割値C0,…,CM-1のいずれかが前記分割値C'0,…,C'M-M'-1に含まれない場合には、前記多項式g(x)を、前記分割値C'0,…,C'M-M'-1に含まれるM-M'個の分割値Ci(1≦i≦M-1)を定数とし、前記分割値C'0,…,C'M-M'-1に含まれないM'個の分割値Cj(1≦j≦M-1)を変数とし、前記分散値D'1,…,D'M'を求めたxそれぞれを代入したM'個の方程式からなる連立方程式として解くことで、前記分割値C0,…,CM-1を補間する分割暗号文補間部と、
前記分割値C0,…,CM-1を結合して前記暗号文Cを得る暗号文結合部と、
前記秘密分散方式に従って、前記分散値U'1(A),…,U'M(A)に含まれる分散値S'1(SK),…,S'M(SK)から、前記秘密鍵SKを復元する鍵復元部と、
前記秘密鍵SKを用いて前記暗号文Cを復号し、前記平文Aを得る復号部と、
を備えることを特徴とするデータ復元装置。
【請求項５】
M,Nは2以上の整数であり、M’は0以上の整数であり、M’≦M<Nであるとして、
データ分散装置が、秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成する暗号化ステップと、
前記データ分散装置が、前記暗号文CをM個の分割値C0,…,CM-1に分割する暗号文分割ステップと、
前記データ分散装置が、次式で定義される多項式g(x)をx=1,…,N-Mについてそれぞれ計算することで、N-M個の分散値D1,…,DN-Mを生成する暗号文分散ステップと、
【数１７】
0005732429.tif 000017
前記データ分散装置が、N個の分散値のうちM個以上の分散値を用いれば元のデータを復元でき、M個未満の分散値からは元のデータを復元できない秘密分散方式に従って、前記秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する鍵分散ステップと、
前記データ分散装置が、前記分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、前記分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とし、分散値Ti(C)(i=1,…,N)と分散値Si(SK)(i=1,…,N)を組にして分散値U1(A),…,UN(A)を生成する分散値生成ステップと、
データ復元装置が、M'を前記分散値T1(C),…,TN-M(C)のうち前記分散値U1(A),…,UN(A)から任意に選択されたM個の分散値U'1(A),…,U'M(A)に含まれるものの数とし、
M'>0であれば、前記分散値T1(C),…,TN-M(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM'個の分散値T'1(C),…,T'M'(C)を分散値D'1,…,D'M'として抽出し、
M-M'>0であれば、前記分散値TN-M+1(C),…,TN(C)のうち前記分散値U'1(A),…,U'M(A)に含まれるM-M'個の分散値T'M'+1(C),…,T'M(C)を分割値C'0,…,C'M-M'-1として抽出する分割暗号文抽出ステップと、
前記データ復元装置が、前記分割値C0,…,CM-1のいずれかが前記分割値C'0,…,C'M-M'-1に含まれない場合には、前記多項式g(x)を、前記分割値C'0,…,C'M-M'-1に含まれるM-M'個の分割値Ci(1≦i≦M-1)を定数とし、前記分割値C'0,…,C'M-M'-1に含まれないM'個の分割値Cj(1≦j≦M-1)を変数とし、前記分散値D'1,…,D'M'を求めたxそれぞれを代入したM'個の方程式からなる連立方程式として解くことで、前記分割値C0,…,CM-1を補間する分割暗号文補間ステップと、
前記データ復元装置が、前記分割値C0,…,CM-1を結合して前記暗号文Cを得る暗号文結
合ステップと、
前記データ復元装置が、前記秘密分散方式に従って、前記分散値U'1(A),…,U'M(A)に含まれる分散値S'1(SK),…,S'M(SK)から、前記秘密鍵SKを復元する鍵復元ステップと、
前記データ復元装置が、前記秘密鍵SKを用いて前記暗号文Cを復号し、前記平文Aを得る復号ステップと、
を含むことを特徴とする秘密分散方法。
【請求項６】
請求項３に記載のデータ分散装置もしくは請求項４に記載のデータ復元装置としてコンピュータを記載させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関する。
【背景技術】
【０００２】
秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。分散値の総数をN、復元に必要な分散値の最小数をM（≦N）としたとき、N,Mの値に制限がない方式と制限がある方式とがある。
【０００３】
秘密分散の代表的な方式として、Shamir秘密分散方式（例えば、非特許文献１参照）がある。この方式の一例では、Aを非負整数、pをN以上かつAよりも大きな素数とし、Aの分散値をSi(A)=f(i) mod p(i=1,…,N)とする。ただし、fはf(0)=Aとなるような1変数M-1次式とする。すると、n1,…,nMを互いに異なる1以上N以下の整数として、以下の関係式により、(ni,Si(A))(i=1,…,N)からAを復元できる。
【０００４】
【数１】
0005732429.tif 000002
【０００５】
上記の例では、分散値Si(A)は0以上p未満の整数となるが、分散値のデータ長をより小さくできる方式も提案されている（例えば、非特許文献２参照）。非特許文献２に記載の秘密分散方式では、共通鍵暗号を用いた以下の方法が提案されている。
【０００６】
＜データ分散処理＞
１．秘密鍵SKを生成する。
２．秘密鍵SKを用いて平文Aを暗号化し、暗号文Cを生成する。
３．情報伝播アルゴリズム(Information Dispersal Algorithm、IDA)を用いて、暗号文CをN個の分散値T1(C),…,TN(C)に分散する。
４．任意の秘密分散方式により、秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する。
５．平文Aの分散値Ui(A)=(Ti(C),Si(SK))(i=1,…,N)を生成する。
【０００７】
＜データ復元処理＞
１．N個の分散値Ui(A)から任意のM個を選択する。
２．情報伝播アルゴリズムを用いて、M個の分散値Ti(C)から暗号文Cを復元する。
３．任意の秘密分散方式により、M個の分散値Si(SK)から秘密鍵SKを復元する。
４．秘密鍵SKを用いて暗号文Cを復号し、平文Aを得る。
【０００８】
情報伝播アルゴリズムは、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元できるようにする技術である。一定個数未満の分散値から元のデータを復元できてもよい点が、秘密分散方式とは相違する。
【０００９】
より具体的に情報伝播アルゴリズムの一例を説明する。情報伝播アルゴリズムのデータ分散処理は、暗号文CをM個の分割値C0,…,CM-1に分割し、Ti(C)=g(i) mod q(i=1,…,N)とする。ただし、C0,…,CM-1を非負整数とし、qをN以上かつC0,…,CM-1よりも大きな素数とし、g(x)(x=1,…,N)を以下の1変数M-1次式より得られる値とする。
【００１０】
【数２】
0005732429.tif 000003
【００１１】
一般にqはpよりも小さな値とすることができる。また、秘密鍵SKは例えば128ビットの小さな固定データ長とすることができる。そのため、秘密鍵SKの分散値Si(SK)は暗号文Cの分散値Ti(C)と比較して十分に小さなデータ長となるため無視することができる。したがって、非特許文献２に記載の秘密分散方式による分散値Ui(A)は、非特許文献１に記載の秘密分散方式による分散値Si(A)よりも小さなデータ長になることが期待できる。
【００１２】
情報伝播アルゴリズムのデータ復元処理は、M個の分散値Ti(C)を用いてC0,…,CM-1を変数とする以下の連立方程式を解くことで、分割値C0,…,CM-1を復元する。
【００１３】
【数３】
0005732429.tif 000004
【００１４】
そして、復元した分割値C0,…,CM-1を結合して暗号文Cを復元する。
【００１５】
マルチパーティ計算に拡張した秘密分散方式が非特許文献３に開示されている。マルチパーティ計算とは、各主体が保有するデータの分散値を他の主体に送り、その分散値を他の主体に明かすことなく意中の計算を実行させることができる秘密分散方式である。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】A.Shamir, “How to share a secret.”, Commun. ACM 22(11), pp.612-613, 1979.
【非特許文献２】H.Krawczyk, “Secret sharing made short.”, CRYPTO 1993, pp.136-146, 1993.
【非特許文献３】千田浩司,五十嵐大,濱田浩気,菊池亮,冨士仁,高橋克巳, ”マルチパーティ計算に適用可能な計算量的ショート秘密分散”, SCIS 2012.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
秘密分散されたデータから画面表示やプログラム実行などを即座に行いたい場合、秘密分散技術におけるデータ復元処理に要する時間をできるだけ短くすることが求められる。非特許文献２や非特許文献３に記載の秘密分散方式は、暗号文Cを復元するための分割値C0,…,CM-1を求めるために、分割値C0,…,CM-1のすべてを変数とする連立方程式を解く必要がある。特に、暗号文Cのデータ長が大きくなるほど計算量は増大し、結果としてデータ復元処理に要する時間も長大化することになる。
【００１８】
この発明はこのような点に鑑みてなされたものであり、秘密分散のデータ復元処理の計算量を抑えることを目的とする。
【課題を解決するための手段】
【００１９】
上記の課題を解決するために、この発明の秘密分散システムは、データ分散装置とデータ復元装置を含む。この発明では、M,Nは2以上の整数であり、M’は0以上の整数であり、M’≦M≦Nであるとする。
【００２０】
データ分散装置は、暗号化部と暗号文分割部と暗号文分散部と鍵分散部と分散値生成部とを備える。暗号化部は、秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成する。暗号文分割部は、暗号文CをM個の分割値C0,…,CM-1に分割する。暗号文分散部は、分割値C0,…,CM-1を係数とするN-M個の互いに線形独立な多項式をそれぞれ計算することで、N-M個の分散値D1,…,DN-Mを生成する。鍵分散部は、所定の秘密分散方式に従って、秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する。分散値生成部は、分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とし、分散値Ti(C)(i=1,…,N)と分散値Si(SK)(i=1,…,N)を組にして分散値U1(A),…,UN(A)を生成する。
【００２１】
データ復元装置は、分割暗号文抽出部と分割暗号文補間部と暗号文結合部と鍵復元部と復号部とを備える。分割暗号文抽出部は、分散値T1(C),…,TN-M(C)のうち分散値U1(A),…,UN(A)から任意に選択されたM個の分散値U'1(A),…,U'M(A)に含まれるM'個の分散値T'1(C),…,T'M'(C)を分散値D'1,…,D'M'として抽出し、分散値TN-M+1(C),…,TN(C)のうち分散値U'1(A),…,U'M(A)に含まれるM-M'個の分散値T'M'+1(C),…,T'M(C)を分割値C'0,…,C'M-M'-1として抽出する。分割暗号文補間部は、分割値C0,…,CM-1のいずれかが分割値C'0,…,C'M-M'-1に含まれない場合には、分散値D'1,…,D'M'と分割値C'0,…,C'M-M'-1を用いて、分割値C0,…,CM-1を補間する。暗号文結合部は、分割値C0,…,CM-1を結合して暗号文Cを得る。鍵復元部は、所定の秘密分散方式に従って、分散値U'1(A),…,U'M(A)に含まれる分散値S'1(SK),…,S'M(SK)から、秘密鍵SKを復元する。復号部は、秘密鍵SKを用いて暗号文Cを復号し、平文Aを得る。
【発明の効果】
【００２２】
この発明の秘密分散技術によれば、所定の分散値がすべて選択された場合には、選択された分散値に含まれる分割値の結合のみで暗号文Cを復元することができる。すなわち、情報伝播アルゴリズムのデータ復元処理を省略することができるため、秘密分散方式のデータ復元処理の計算量を抑えることができる。
【図面の簡単な説明】
【００２３】
【図１】従来の秘密分散方式のデータ分散処理を説明する模式図。
【図２】従来の秘密分散方式のデータ復元処理を説明する模式図。
【図３】第１実施形態に係る秘密分散システムの構成例を示すブロック図。
【図４】第１実施形態に係るデータ分散装置の構成例を示すブロック図。
【図５】第１実施形態に係るデータ復元装置の構成例を示すブロック図。
【図６】データ記憶装置の構成例を示すブロック図。
【図７】第１実施形態に係るデータ分散装置の動作例を示すフローチャート。
【図８】第１実施形態に係るデータ復元装置の動作例を示すフローチャート。
【図９】第１実施形態に係るデータ分散処理を説明する模式図。
【図１０】第１実施形態に係るデータ復元処理を説明する模式図。
【図１１】第２実施形態に係る秘密分散システムの構成例を示すブロック図。
【図１２】第２実施形態に係るデータ分散装置の構成例を示すブロック図。
【図１３】第２実施形態に係るデータ復元装置の構成例を示すブロック図。
【図１４】第２実施形態に係るデータ分散処理を説明する模式図。
【図１５】第２実施形態に係るデータ復元処理を説明する模式図。
【図１６】第３実施形態に係る秘密分散システムの構成例を示すブロック図。
【図１７】第３実施形態に係るデータ分散装置の構成例を示すブロック図。
【図１８】第３実施形態に係るデータ復元装置の構成例を示すブロック図。
【図１９】第３実施形態に係るデータ分散処理を説明する模式図。
【図２０】第３実施形態に係るデータ復元処理を説明する模式図。
【発明を実施するための形態】
【００２４】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２５】
［従来の秘密分散方式］
実施形態の説明に先立って、従来の秘密分散方式の課題について詳細に説明する。
【００２６】
＜データ分散処理＞
図１を参照して従来の秘密分散方式によるデータ分散処理の原理を説明する。
【００２７】
まず、秘密鍵SKを用いて平文Aを暗号化し、暗号文Cを生成する。ここで用いる暗号化方式は任意の共通鍵暗号方式を用いることができる。共通鍵暗号方式とは情報の送信者と受信者が同一の鍵を共有する暗号方式である。代表的な共通鍵暗号方式としては、例えばDES(Data Encryption Standard)、AES(Advanced Encryption Standard)などがある。
【００２８】
次に、暗号文CをM個の分割値C0,…,CM-1に分割する。分割の方法はすべての分割値C0,…,CM-1を所定の順番で結合する操作のみにより暗号文Cを復元できる方法であればどのような方法でもよい。例えば、暗号文Cのデータ長がsであるとして、暗号文Cの先頭からs/Mビットずつに分割することができる。もしくは、tを任意の自然数として、暗号文Cの先頭からs/tMビットずつに分割し、任意に選択したt個を組として分割値C0,…,CM-1としてもよい。
【００２９】
そして、M個の分割値C0,…,CM-1を、情報伝播アルゴリズムを用いて、N個の分散値T1(C),…,TN(C)に分散する。情報伝播アルゴリズムについての詳細は、例えば「M.O.Rabin, “Efficient dispersal of information for security, load balancing, and fault tolerance.”, J. ACM 36(2), pp.335-348, 1989.（参考文献１）」を参照されたい。
【００３０】
一方で、秘密鍵SKを、情報伝播アルゴリズムに従って分散し、分散値S1(SK),…,SN(SK)を生成する。情報伝播アルゴリズムについての詳細は、上述および参考文献１を参照されたい。情報伝播アルゴリズムは秘密分散方式を包含する概念であるので、ここでは既知の秘密分散方式を用いてもよい。例えば、Shamir秘密分散方式などが適用できる。Shamir秘密分散方式についての詳細は、上述および非特許文献１を参照されたい。
【００３１】
最後に、i=1,…,Nについて、分散値Ti(C)と分散値Si(SK)を組として分散値Ui(A)=(Ti(C),Si(SK))を生成し、N個の分散値U1(A),…,UN(A)とする。
【００３２】
＜データ復元処理＞
図２を参照して従来の秘密分散方式によるデータ復元処理の原理を説明する。
【００３３】
まず、N個の分散値U1(A),…,UN(A)から任意のM個を選択する。選択したM個の分散値を分散値U’1(A),…,U’M(A)とする。次に、M個の分散値U’1(A),…,U’M(A)に含まれる分散値T’1(C),…,T’M(C)から、情報伝播アルゴリズムを用いて、分割値C0,…,CM-1を復元する。ここで用いる情報伝播アルゴリズムは、データ分散処理において、M個の分割値C0,…,CM-1をN個の分散値T1(C),…,TN(C)に分割した際に用いた情報伝播アルゴリズムである。そして、復元された分割値C0,…,CM-1を所定の順番で結合することで暗号文Cを復元する。結合の方法はデータ分散処理において暗号文CをM個の分割値C0,…,CM-1に分割した方法に対応して決定される。
【００３４】
一方で、M個の分散値U’1(A),…,U’M(A)に含まれる分散値S’1(SK),…,S’M(SK)から、情報伝播アルゴリズムに従って秘密鍵SKを復元する。ここで用いる情報伝播アルゴリズムは、データ分散処理において、秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散した際に用いた情報伝播アルゴリズムである。
【００３５】
最後に、復元した秘密鍵SKを用いて復元した暗号文Cを復号することで平文Aを得る。復号の方法は、データ分散処理において、秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成した際に用いた暗号方式を用いる。
【００３６】
このように、従来の秘密分散方式では、暗号文Cを復元するための分割値C0,…,CM-1を求めるために、分割値C0,…,CM-1のすべてを変数とする連立方程式を解く必要があった。暗号文Cのデータ長が大きくなるほど分割数や分割値C0,…,CM-1のデータ長が大きくなるため、計算量が増大する。結果としてデータ復元処理に要する時間も長大化する。この発明は、秘密分散方式のデータ復元処理の計算量を抑えることでデータ復元処理に要する時間を低減することを目的とする。
【００３７】
［第１実施形態］
この発明の第１実施形態に係る秘密分散システム１は、非特許文献２に記載の秘密分散方式に対してこの発明を適用した場合の構成例である。
【００３８】
＜構成＞
図３を参照して、秘密分散システム１の構成例を詳細に説明する。秘密分散システム１は、データ分散装置１０とデータ復元装置２０と少なくともN台のデータ記憶装置３０1〜３０Nとネットワーク９０を含む。データ分散装置１０とデータ復元装置２０とデータ記憶装置３０1〜３０Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１０とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２０とデータ記憶装置３０1〜３０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、データ分散装置１０とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２０とデータ記憶装置３０1〜３０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１０が出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ記憶装置３０1〜３０Nへオフラインで入力するように構成してもよい。同様に、データ記憶装置３０1〜３０Nが出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ復元装置２０へオフラインで入力するように構成してもよい。
【００３９】
図４を参照して、秘密分散システム１に含まれるデータ分散装置１０の構成例を詳細に説明する。データ分散装置１０は、暗号化部１１０と暗号文分割部１２０と暗号文分散部１３０と鍵分散部１４０と分散値生成部１５０と分散値配布部１６０とを備える。
【００４０】
図５を参照して、秘密分散システム１に含まれるデータ復元装置２０の構成例を詳細に説明する。データ復元装置２０は、分散値選択部２１０と分割暗号文抽出部２２０と分割暗号文補間部２３０と暗号文結合部２４０と鍵復元部２５０と復号部２６０とを備える。
【００４１】
図６を参照して、秘密分散システム１に含まれるデータ記憶装置３０の構成例を詳細に説明する。データ記憶装置３０は、分散値記憶部３１０を備える。分散値記憶部３１０は、例えば、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００４２】
＜データ分散処理＞
図７を参照して、データ分散装置１０の動作例を、実際に行われる手続きの順に従って詳細に説明する。
【００４３】
データ分散装置１０の備える暗号化部１１０は、秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成する（Ｓ１１０）。ここで用いる暗号化方式は従来の秘密分散方式と同様に、既知のいかなる共通鍵暗号方式も用いることができる。
【００４４】
データ分散装置１０の備える暗号文分割部１２０は、暗号文CをM個の分割値C0,…,CM-1に分割する（Ｓ１２０）。ここで用いる分割方法は従来の秘密分散方式と同様に、すべての分割値C0,…,CM-1を所定の順番で結合する操作のみにより暗号文Cを復元できる方法であればどのような方法でもよい。
【００４５】
データ分散装置１０の備える暗号文分散部１３０は、分割値C0,…,CM-1を係数とするN-M個の互いに線形独立な多項式をそれぞれ計算することで、N-M個の分散値D1,…,DN-Mを生成する（Ｓ１３０）。より具体的には、以下の式で表される多項式g(x)を、x=1,…,N-Mについてそれぞれ計算することで、分散値D1,…,DN-Mを生成する。
【００４６】
【数４】
0005732429.tif 000005
【００４７】
ただし、qは分割値C0,…,CM-1のいずれより大きいN以上の素数である。
【００４８】
データ分散装置１０の備える鍵分散部１４０は、任意の秘密分散方式に従って、秘密鍵SKをN個の分散値S1(SK),…,SN(SK)に分散する（Ｓ１４０）。ここで用いる秘密分散方式は従来の秘密分散方式と同様に、既知のいかなる秘密分散方式も用いることができる。例えば、非特許文献１〜３に記載の秘密分散方式を用いることができる。
【００４９】
データ分散装置１０の備える分散値生成部１５０は、分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とする。そして、i=1,…,Nについて、分散値Ti(C)と分散値Si(SK)を組にして分散値Ui(A)=(Ti(C),Si(SK))を生成し、N個の分散値U1(A),…,UN(A)とする（Ｓ１５０）。
【００５０】
データ分散装置１０の備える分散値配布部１６０は、分散値U1(A),…,UN(A)をデータ記憶装置３０1，…，３０Nに配布する（Ｓ１６０）。データ記憶装置３０iは受信した分散値Ui(A)を分散値記憶部３１０へ記憶する。
【００５１】
＜データ復元処理＞
図８を参照して、データ復元装置２０の動作例を、実際に行われる手続きの順に従って詳細に説明する。
【００５２】
データ復元装置２０の備える分散値選択部２１０は、N台のデータ記憶装置３０1，…，３０Nから任意にM台を選択する。選択されたデータ記憶装置３０i(i=1,…,M)は、分散値記憶部３１０に記憶する分散値Ui(A)をデータ復元装置２０へ送信する。データ復元装置２０はデータ記憶装置３０iから受信した分散値Ui(A)をM個の分散値U'1(A),…,U'M(A)として取得する（Ｓ２１０）。
【００５３】
データ復元装置２０の備える分割暗号文抽出部２２０は、分散値T1(C),…,TN-M(C)のうち分散値U'1(A),…,U'M(A)に含まれるM'個の分散値T'1(C),…,T'M'(C)を、分散値D'1,…,D'M'として抽出する。また、分散値TN-M+1(C),…,TN(C)のうち分散値U'1(A),…,U'M(A)に含まれるM-M'個の分散値T'M'+1(C),…,T'M(C)を、分割値C'0,…,C'M-M'-1として抽出する（Ｓ２２０）。
【００５４】
データ復元装置２０の備える分割暗号文補間部２３０は、分割値C0,…,CM-1のいずれかが分割値C'0,…,C'M-M'-1に含まれない場合には、分散値D'1,…,D'M'と分割値C'0,…,C'M-M'-1を用いて、分割値C0,…,CM-1を補間する（Ｓ２３１、Ｓ２３２）。分割値C0,…,CM-1のすべてが分割値C'0,…,C'M-M'-1に含まれている場合には、Ｓ２３２の処理を省略し、Ｓ２４０の処理へ進む（Ｓ２３１）。より具体的には、上記の多項式g(x)を、分割値C'0,…,C'M-M'-1に含まれるM-M'個の分割値Ci(1≦i≦M-1)を定数とし、分割値C'0,…,C'M-M'-1に含まれないM'個の分割値Cj(1≦j≦M-1)を変数として、分散値D'1,…,D'M'を求めたxをそれぞれ代入したM'個の方程式を、連立方程式として解くことで、分割値C0,…,CM-1を補間する。例えば、M個の分散値Ui(A)(i=1,…,M',N-M+M'+1,…,N)が選択された場合には、C0,…,CM-M'-1を定数とし、CM-M',…,CM-1を変数として、以下の連立方程式を解くことで、分割値CM-M',…,CM-1を求める。
【００５５】
【数５】
0005732429.tif 000006
【００５６】
データ復元装置２０の備える暗号文結合部２４０は、分割値C0,…,CM-1を結合して暗号文Cを得る（Ｓ２４０）。ここで用いる結合方法は従来の秘密分散方式と同様に、データ分散処理において暗号文CをM個の分割値C0,…,CM-1に分割した際に用いた分割方法に対応して決定される。
【００５７】
データ復元装置２０の備える鍵復元部２５０は、秘密分散方式に従って、分散値U'1(A),…,U'M(A)に含まれる分散値S'1(SK),…,S'M(SK)から、秘密鍵SKを復元する（Ｓ２５０）。ここで用いる秘密分散方式は従来の秘密分散方式と同様に、データ分散処理において秘密鍵SKを分散値S1(SK),…,SN(SK)に分散した際に用いた秘密分散方式である。
【００５８】
データ復元装置２０の備える復号部２６０は、秘密鍵SKを用いて暗号文Cを復号し、平文Aを得る（Ｓ２６０）。復号の方法は従来の秘密分散方式と同様に、データ分散処理において秘密鍵SKを用いて平文Aを暗号化して暗号文Cを生成した際に用いた暗号方式を用いる。
【００５９】
＜第１実施形態の特徴＞
図９を参照して、第１実施形態に係る秘密分散システム１によるデータ分散処理の原理を説明する。従来の秘密分散方式との相違点は、M個の分割値C0,…,CM-1からN個の分散値T1(C),…,TN(C)を生成する処理である。まず、M個の分割値C0,…,CM-1を、情報伝播アルゴリズムを用いて、N-M個の分散値D1,…,DN-Mに分散する。情報伝播アルゴリズムについての詳細は、上述および参考文献１を参照されたい。次に、分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とする。また、分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とする。
【００６０】
図１０を参照して、第１実施形態に係る秘密分散システム１によるデータ復元処理の原理を説明する。従来の秘密分散方式との相違点は、M個の分散値T’1(C),…,T’M(C)からM個の分割値C0,…,CM-1を復元する処理である。分散値T’1(C),…,T’M(C)のうち分散値T1(C),…,TN-M(C)に対応する値がM'個の分散値T'1(C),…,T'M'(C)であるとして、分散値T'1(C),…,T'M'(C)を、分散値D'1,…,D'M'として抽出する。また、分散値T’1(C),…,T’M(C)のうち分散値TN-M+1(C),…,TN(C)に対応する値がM-M'個の分散値T'M'+1(C),…,T'M(C)であるとして、分散値T'M'+1(C),…,T'M(C)を、分割値C'0,…,C'M-M'-1として抽出する。
【００６１】
分割値C0,…,CM-1のすべてが分割値C'0,…,C'M-M'-1に含まれている場合には、分割値C0,…,CM-1を結合して暗号文Cを得る。分割値C0,…,CM-1のいずれかが分割値C'0,…,C'M-M'-1に含まれない場合には、分散値D'1,…,D'M'と分割値C'0,…,C'M-M'-1を用いて、分割値C0,…,CM-1を補間した上で、分割値C0,…,CM-1を結合して暗号文Cを得る。
【００６２】
このように、第１実施形態に係る秘密分散システム１では、N個の分散値U1(A),…,UN(A)の一部に暗号文Cを分割した値である分割値C0,…,CM-1を保持している。したがって、任意に選択したM個の分散値U’1(A),…,U’M(A)に分割値C0,…,CM-1がすべて含まれている場合には、分割値C0,…,CM-1を復元する処理を行う必要がない。そのため、データ復元処理における計算量を低減することができる。
【００６３】
また、分割値C0,…,CM-1から暗号文Cの一部のデータが得られても、秘密鍵SKを用いて暗号化されており、平文Aの一部が得られるわけではない。したがって、平文Aの秘匿性は損なわれない。
【００６４】
さらに、N-M個の分散値D1,…,DN-Mは、分割値C0,…,CM-1を用いて情報伝播アルゴリズムを用いて生成されるため、選択されたM個の分散値U’1(A),…,U’M(A)に分割値C0,…,CM-1のいずれかが含まれていない場合であっても、分散値D'1,…,D'M'と分割値C'0,…,C'M-M'-1を用いて、分割値C0,…,CM-1を補間することが可能となっている。したがって、N個の分散値U1(A),…,UN(A)から任意に選択したM個の分散値U’1(A),…,U’M(A)を用いて平文Aを復元することができる。
【００６５】
［第２実施形態］
この発明の第２実施形態に係る秘密分散システム２は、非特許文献３に記載の秘密分散方式に対してこの発明を適用した場合の構成例である。
【００６６】
＜構成＞
図１１を参照して、秘密分散システム２の構成例を詳細に説明する。秘密分散システム２は、データ分散装置１１とデータ復元装置２１と少なくともN台のデータ記憶装置３０とネットワーク９０を含む。データ分散装置１１とデータ復元装置２１とデータ記憶装置３０1〜３０Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１１とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２１とデータ記憶装置３０1〜３０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、データ分散装置１１とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２１とデータ記憶装置３０1〜３０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１１が出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ記憶装置３０1〜３０Nへオフラインで入力するように構成してもよい。同様に、データ記憶装置３０1〜３０Nが出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ復元装置２１へオフラインで入力するように構成してもよい。
【００６７】
図１２を参照して、秘密分散システム２に含まれるデータ分散装置１１の構成例を詳細に説明する。データ分散装置１１は、第１実施形態に係るデータ分散装置１０と同様に、暗号文分割部１２０と暗号文分散部１３０と分散値配布部１６０とを備える。暗号化部１１０の替わりに暗号化部１１１を備え、鍵分散部１４０の替わりに鍵分散部１４１を備え、分散値生成部１５０の替わりに分散値生成部１５１を備える。したがって、データ分散装置１１とデータ分散装置１０との相違点は、暗号化部と鍵分散部と分散値生成部の処理が異なる点である。
【００６８】
図１３を参照して、秘密分散システム２に含まれるデータ復元装置２１の構成例を詳細に説明する。データ復元装置２１は、第１実施形態に係るデータ復元装置２０と同様に、分散値選択部２１０と分割暗号文抽出部２２０と分割暗号文補間部２３０と暗号文結合部２４０とを備える。鍵復元部２５０の替わりに鍵復元部２５１を備え、復号部２６０の替わりに復号部２６１を備える。したがって、データ復元装置２０とデータ復元装置２１との相違点は、鍵復元部と復号部の処理が異なる点である。
【００６９】
＜データ分散処理＞
データ分散装置１１の備える暗号化部１１１は、M-1個の固定長の乱数R1,…,RM-1を生成する。次に、乱数R1,…,RM-1をシードとする0以上p未満の整数である擬似乱数V(R1),…,V(RM-1)を生成する。ただし、pは平文Aより大きいN以上の素数である。そして、多項式h(x)が、h(0)=Aでありh(i)=V(Ri)(i=1,…,M-1)である1変数M-1次式であるとして、h(M) mod pを計算することで暗号文Cを生成する。
【００７０】
データ分散装置１１の備える鍵分散部１４１は、任意の秘密分散方式に従って、乱数R1,…,RM-1それぞれをN個の分散値S1(Ri),…,SN(Ri)(i=1,…,M-1)に分散する。ここで用いる秘密分散方式は従来の秘密分散方式と同様に、既知のいかなる秘密分散方式も用いることができる。例えば、非特許文献１〜３に記載の秘密分散方式を用いることができる。
【００７１】
データ分散装置１１の備える分散値生成部１５１は、分散値D1,…,DN-Mを分散値T1(C),…,TN-M(C)とし、分割値C0,…,CM-1を分散値TN-M+1(C),…,TN(C)とする。そして、i=1,…,Nについて、分散値Ti(C)と分散値Si(R1),…,Si(RM-1)を組にして分散値Ui(A)=(Ti(C),Si(R1),…,Si(RM-1))を生成し、N個の分散値U1(A),…,UN(A)とする。
【００７２】
＜データ復元処理＞
データ復元装置２１の備える鍵復元部２５１は、秘密分散方式に従って、N個の分散値U1(A),…,UN(A)から任意に選択されたM個の分散値U'1(A),…,U'M(A)に含まれる分散値S'1(Ri),…,S'N(Ri)(i=1,…,M-1)から、乱数R1,…,RM-1をそれぞれ復元する。ここで用いる秘密分散方式は従来の秘密分散方式と同様に、データ分散処理において乱数R1,…,RM-1を分散値S1(Ri),…,SN(Ri)(i=1,…,M-1)にそれぞれ分散した際に用いた秘密分散方式である。
【００７３】
データ復元装置２１の備える復号部２６１は、乱数R1,…,RM-1から擬似乱数V(R1),…,V(RM-1)を生成する。そして、h(i)=V(Ri)(i=1,…,M-1)およびh(M)=Cより、h(0)を求めることで平文Aを得る。
【００７４】
＜第２実施形態の特徴＞
図１４を参照して、第２実施形態に係る秘密分散システム２によるデータ分散処理の原理を説明する。第１実施形態との相違点は、平文Aを暗号文Cに暗号化する処理と、分散値U1(A),…,UN(A)を生成する処理である。平文Aを暗号文Cに暗号化する処理は、M-1個の乱数R1,…,RM-1のそれぞれをシードとして擬似乱数V(R1),…,V(RM-1)を生成する。そして、擬似乱数V(R1),…,V(RM-1)を秘密鍵として平文Aを暗号化して暗号文Cを生成する。分散値U1(A),…,UN(A)を生成する処理は、乱数Ri(i=1,…,M-1)をそれぞれN個の分散値S1(Ri),…,SN(Ri)(i=1,…,M-1)に分散する。そして、乱数R1,…,RM-1の分散値を1つずつ含むM-1個の分散値Si(R1),…,Si(RM-1)を組とし、さらに暗号文Cの分散値Ti(C)と組にして、N個の分散値U1(A),…,UN(A)を生成する。
【００７５】
図１５を参照して、第２実施形態に係る秘密分散システム２によるデータ復元処理の原理を説明する。第１実施形態との相違点は、秘密鍵の復元を行う処理と、暗号文Cを復号して平文Aを得る処理である。秘密鍵の復元を行う処理は、M個の分散値U’1(A),…,U’M(A)から、乱数R1,…,RM-1の分散値S'i(R1),…,S'i(RM-1)(i=1,…,M)の組を抽出し、i=1,…,M-1について、M個の分散値S'1(Ri),…,S'M(Ri)から乱数Riを復元する。暗号文Cを復号して平文Aを得る処理は、復元したM-1個の乱数R1,…,RM-1のそれぞれをシードとして擬似乱数V(R1),…,V(RM-1)を生成する。そして、擬似乱数V(R1),…,V(RM-1)を秘密鍵として暗号文Cを復号して平文Aを得る。
【００７６】
このように、第２実施形態に係る秘密分散システム２によれば、非特許文献３に記載のマルチパーティ計算に適用可能な計算量的ショート秘密分散方式においても、第１実施形態に係る秘密分散システム１と同様に、秘密分散方式のデータ復元処理における計算量を低減することができる。
【００７７】
［第３実施形態］
この発明の第３実施形態に係る秘密分散システム３は、排他的論理和演算により線形結合された多項式を用いる構成例である。データ分散処理においては、その多項式を用いて暗号文Cの分散値を生成する。データ復元処理においては、その多項式を用いて暗号文Cの分散値を補間する。
【００７８】
＜構成＞
図１６を参照して、秘密分散システム３の構成例を詳細に説明する。秘密分散システム３は、データ分散装置１２とデータ復元装置２２と少なくともN台のデータ記憶装置３０とネットワーク９０を含む。データ分散装置１２とデータ復元装置２２とデータ記憶装置３０1〜３０Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１２とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２２とデータ記憶装置３０1〜３０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、データ分散装置１２とデータ記憶装置３０1〜３０Nそれぞれ、およびデータ復元装置２２とデータ記憶装置３０1〜３０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１２が出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ記憶装置３０1〜３０Nへオフラインで入力するように構成してもよい。同様に、データ記憶装置３０1〜３０Nが出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体からデータ復元装置２２へオフラインで入力するように構成してもよい。
【００７９】
図１７を参照して、秘密分散システム３に含まれるデータ分散装置１２の構成例を詳細に説明する。データ分散装置１２は、第１実施形態に係るデータ分散装置１０と同様に、暗号文分割部１２０と分散値配布部１６０とを備える。暗号化部１１０の替わりに暗号化部１１２を備え、暗号文分散部１３０の替わりに暗号文分散部１３１を備え、鍵分散部１４０の替わりに鍵分散部１４２を備え、分散値生成部１５０の替わりに分散値生成部１５２を備える。したがって、データ分散装置１２とデータ分散装置１０との相違点は、暗号化部と暗号文分散部と鍵分散部と分散値生成部の処理が異なる点である。
【００８０】
図１８を参照して、秘密分散システム３に含まれるデータ復元装置２２の構成例を詳細に説明する。データ復元装置２２は、第１実施形態に係るデータ復元装置２０と同様に、分散値選択部２１０と分割暗号文抽出部２２０と暗号文結合部２４０とを備える。分割暗号文補間部２３０の替わりに分割暗号文補間部２３１を備え、鍵復元部２５０の替わりに鍵復元部２５２を備え、復号部２６０の替わりに復号部２６２を備える。したがって、データ復元装置２０とデータ復元装置２２との相違点は、分割暗号文補間部と鍵復元部と復号部の処理が異なる点である。
【００８１】
＜データ分散処理＞
この実施形態では、秘密鍵SKは秘密鍵SK1,SK2であり、平文Aのビット長はnビットであるとする。秘密鍵SK1,SK2は、それぞれランダムに生成する。また、ここではN=3,M=2の場合を例として説明する。
【００８２】
データ分散装置１２の備える暗号化部１１２は、秘密鍵SK1,SK2からnビットのハッシュ値Hを生成する。ハッシュ値の生成は、既知のいかなるハッシュ関数をも用いることができる。具体的には、例えばSHA-1やMD5などを適用することができる。また例えば、H=Hash(SK1||SK2||1)||Hash(SK1||SK2||2)||…||Hash(SK1||SK2||K)としてハッシュ値を生成する。ここでKはHがnビット以上となる最小整数、Hashはハッシュ関数、||はデータ連結とする。このように、秘密鍵SK1,SK2の両方を知らない限りハッシュ値Hが計算できないようにする。そして、以下の式により、平文Aとハッシュ値Hとの排他的論理和を計算することで暗号文Cを生成する。
【００８３】
【数６】
0005732429.tif 000007
【００８４】
データ分散装置１２の備える暗号文分散部１３１は、暗号文Cの上位n/2ビットを分割値C0とし、下位n/2ビットを分割値C1とする。そして、以下の式により、分割値C0と分割値C1の排他的論理和演算を計算することで分散値D1を生成する。
【００８５】
【数７】
0005732429.tif 000008
【００８６】
データ分散装置１２の備える鍵分散部１４２は、以下の式により、秘密鍵SK1と秘密鍵SK2の排他的論理和演算を計算することでSK3を生成する。
【００８７】
【数８】
0005732429.tif 000009
【００８８】
データ分散装置１２の備える分散値生成部１５２は、以下の式に示すように分散値U1(A),…,U3(A)を生成する。
【００８９】
【数９】
0005732429.tif 000010
【００９０】
＜データ復元処理＞
データ復元装置２２の備える分割暗号文補間部２３１は、分割値C'0,…,C'M-M'-1と分散値D'1,…,D'M'との排他的論理和を計算することで、分割値C0,…,CM-1を補間する。例えば、分散値U1(A)と分散値U2(A)が選択された場合には、以下の式により分散値U1(A)に含まれる分散値D1と分散値U2(A)に含まれる分割値C0との排他的論理和を計算することで分割値C1を求めることができる。
【００９１】
【数１０】
0005732429.tif 000011
【００９２】
データ復元装置２２の備える鍵復元部２５２は、秘密鍵SK1とSK3もしくは秘密鍵SK2とSK3の排他的論理和を計算する。例えば、分散値U2(A)と分散値U3(A)が選択された場合には、以下の式により分散値U2(A)に含まれる秘密鍵SK2と分散値U3(A)に含まれるSK3との排他的論理和を計算することで秘密鍵SK1を求めることができる。
【００９３】
【数１１】
0005732429.tif 000012
【００９４】
データ復元装置２２の備える復号部２６２は、復元した秘密鍵SK1,SK2からnビットのハッシュ値Hを生成する。ハッシュ値の生成は、データ分散装置１２の備える暗号化部１１２が用いたハッシュ関数と同一のハッシュ関数により行う。そして、以下の式により、暗号文Cとハッシュ値Hとの排他的論理和を計算することで平文Aを生成する。
【００９５】
【数１２】
0005732429.tif 000013
【００９６】
上記の説明では、分散値の総数がN=3であり、復元に必要な分散値の最小数がM=2である場合を用いて説明したが、同様の考え方によりN,Mを異なる値とすることができる。
【００９７】
＜第３実施形態の特徴＞
図１９を参照して、第３実施形態に係る秘密分散システム３によるデータ分散処理の原理を説明する。ここでは、簡単のためにN=3,M=2の場合を例として表す。第１実施形態との相違点は、分割値C0,…,CM-1から分散値D1,…,DN-Mを生成する処理である。まず、暗号文Cを分割して分割値C0,C1を生成する。次に、分割値C0と分割値C1との排他的論理和を計算することで分散値D1を生成する。そして、分散値D1を分散値T1に、分割値C0を分散値T2に、分割値C1を分散値T3にそれぞれ設定する。
【００９８】
図２０を参照して、第３実施形態に係る秘密分散システム３によるデータ復元処理の原理を説明する。図２０（Ａ）は、暗号文Cを分割した分割値C0,C1がすべて選択された場合である。この場合には、分割値C0,C1を所定の順番で結合すれば暗号文Cを得ることができる。図２０（Ｂ）は、暗号文Cを分割した分割値C0,C1のうち分割値C1が得られなかった場合である。この場合には、得られなかった分割値C1の替わりに分割値C0と分割値C1の排他的論理和である分散値D1が得られる。したがって、分散値D1と分割値C0の排他的論理和を計算することで分割値C1を得ることができる。そして、分割値C0と分割値C1を所定の順番で結合することで暗号文Cを得ることができる。
【００９９】
この実施形態における平文Aの秘匿性について説明する。まず、平文Aは秘密鍵SK1,SK2を用いて暗号化されているため、暗号文Cのみでは平文Aの一部でも復元することはできない。また、暗号文Cは秘密鍵SK1,SK2から生成したハッシュ値Hを用いて暗号化されているため、秘密鍵SK1,SK2のいずれかを得ただけではハッシュ値Hを得ることができず、平文Aの一部でも復元することはできない。
【０１００】
そして、分散値U1(A),…,U3(A)は暗号文Cを分割した分割値C0,C1を含んでいるため、分割値C0,C1をすべて得ることができれば、それらを結合する操作のみで暗号文Cを得ることができる。したがって、この実施形態においても、秘密分散方式のデータ復元処理の計算量を低減することができる。
【０１０１】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１０２】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１０３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０７】
１，２，３  秘密分散システム
１０，１１，１２  データ分散装置
２０，２１，２２  データ復元装置
３０1〜３０N  データ記憶装置
９０  ネットワーク
１１０，１１１，１１２  暗号化部
１２０  暗号文分割部
１３０，１３１  暗号文分散部
１４０，１４１，１４２  鍵分散部
１５０，１５１，１５２  分散値生成部
１６０  分散値配布部
２１０  分散値選択部
２２０  分割暗号文抽出部
２３０，２３１  分割暗号文補間部
２４０  暗号文結合部
２５０，２５１，２５２  鍵復元部
２６０，２６１，２６２  復号部
３１０  分散値記憶部
【図１】
0005732429.tif 000018
【図２】
0005732429.tif 000019
【図３】
0005732429.tif 000020
【図４】
0005732429.tif 000021
【図５】
0005732429.tif 000022
【図６】
0005732429.tif 000023
【図７】
0005732429.tif 000024
【図８】
0005732429.tif 000025
【図９】
0005732429.tif 000026
【図１０】
0005732429.tif 000027
【図１１】
0005732429.tif 000028
【図１２】
0005732429.tif 000029
【図１３】
0005732429.tif 000030
【図１４】
0005732429.tif 000031
【図１５】
0005732429.tif 000032
【図１６】
0005732429.tif 000033
【図１７】
0005732429.tif 000034
【図１８】
0005732429.tif 000035
【図１９】
0005732429.tif 000036
【図２０】
0005732429.tif 000037