秘密分散装置、方法及びプログラム
【課題】多項式補間を用いずに高速に実行可能な完全秘密分散を実現させる。
【解決手段】保存部11の秘密情報Sを分割してn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成し、ゼロ値からなる分割秘密データK(0)を生成し、各分割秘密データと例えば同一サイズのn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成し、分割秘密データK(0),…,K(n-1)及び乱数データR(0),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出し((+)は排他的論理和)、互いに同一の行番号jを有する分散部分データD(j,0)〜D(j,n-2)を有するn個の分散情報D(0),…,D(j),…,D(n-1)を個別にn個の記憶装置に配布する。このうち、任意の2個の分散情報D(i),D(j)に基づいて、秘密情報Sを復元できる。
【解決手段】保存部11の秘密情報Sを分割してn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成し、ゼロ値からなる分割秘密データK(0)を生成し、各分割秘密データと例えば同一サイズのn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成し、分割秘密データK(0),…,K(n-1)及び乱数データR(0),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出し((+)は排他的論理和)、互いに同一の行番号jを有する分散部分データD(j,0)〜D(j,n-2)を有するn個の分散情報D(0),…,D(j),…,D(n-1)を個別にn個の記憶装置に配布する。このうち、任意の2個の分散情報D(i),D(j)に基づいて、秘密情報Sを復元できる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、秘密情報を分散させた分散情報を配布し、収集した分散情報から秘密情報を復元する秘密分散装置、方法及びプログラムに係り、例えば多項式補間を用いずに高速に実行可能な完全秘密分散を実現し得る秘密分散装置、方法及びプログラムに関する。
【背景技術】
【0002】
一般に、暗号化鍵などの秘密情報を紛失した場合の対策としては、予め秘密情報のコピーを作成しておくことが有効である。しかしながら、秘密情報のコピーを作成すると、盗難のリスクが高くなるという問題が生じる。このような問題を解決する手法として、1979年にシャミア(Shamir)が(k,n)しきい値秘密分散法と呼ばれる秘密分散法を提案している(例えば、非特許文献1参照)。
【0003】
(k,n)しきい値秘密分散法では、秘密情報をn個の分散情報に分割し、n個の分散情報の中から任意のk個を集めれば元の秘密情報を復元できるが、k−1個の分散情報からでは、元の秘密情報に関する情報を全く得られない。すなわち、(k,n)しきい値秘密分散法は、しきい値kを境にした秘密情報の復元特性をもっている(なお、1<k<n)。
【0004】
このため、(k,n)しきい値秘密分散法によれば、k−1個以下の分散情報が漏洩しても元の秘密情報が安全であり、n−k個以下の分散情報を紛失しても元の秘密情報を復元できるといった管理を実現できる。
【0005】
しかしながら、シャミアの(k,n)しきい値秘密分散法では、秘密情報の分散や復元の処理を、多くの計算量を要する多項式補間により実現するので、大量のデータを秘密分散するためには、高速な計算機を必要とする不都合がある。
【0006】
一方、このような不都合を解決し、計算量を大幅に削減し得る(k,n)しきい値秘密分散法として、荻原らの方式が知られている(例えば、特許文献1参照)。ここで、荻原らの方式は、秘密情報の分散処理や復元処理を排他的論理和演算のみで実現するので、高速に実行可能となっている。しかしながら、荻原らの方式は、例えば(3,4)しきい値法においては、分散データの取り方によっては、2個の分散データで元の秘密情報を復元できるなど(例えば、第132段落参照)、完全秘密分散ではない不都合がある。ここで、完全秘密分散とは、分散データの取り方によらずに、しきい値を境にした秘密情報の復元特性を有することを意味する。
【非特許文献1】A. Shamir: “How to share a secret", Communications of the ACM, 22, 11, pp.612-613 (1979)
【特許文献1】特開2004−213650号公報
【発明の開示】
【発明が解決しようとする課題】
【0007】
以上説明したように、シャミアによる(k,n)しきい値秘密分散法では、多項式補間を用いるため、高速な計算機が必要となる不都合がある。一方、荻原らの方式は、分散データの取り方によっては、完全秘密分散ではない不都合がある。
【0008】
また、本発明者の検討によれば、従来のシステムで分散情報を追加したい場合、次のように、(A)分散情報を全メンバに再配布する手法、又は(B)分散情報を追加メンバのみに配布する手法が考えられる。具体的には、手法(A)においては、追加後の人数に基づき、全ての分散情報を作成し直して全てのメンバに再配布する。手法(B)においては、ディーラーが予め分散情報を多めに作成して保持しておき、メンバ追加時に、この多めに作成してある分散情報を追加メンバのみに配布する。または手法(B)においては、ディーラーが秘密情報を保持しておき、追加人数分の分散情報を秘密情報から作成し、追加メンバのみに配布する方式としてもよい。
【0009】
しかしながら、追加時の手法(A)は、既存のメンバにも分散情報を再配布する必要があるので、手間がかかってしまう。また、手法(B)は、秘密情報を復元可能な数の分散情報、又は秘密情報それ自体を1箇所でディーラーが保持する必要があるので、セキュリティ性を低下させてしまう。
【0010】
本発明は上記実情を考慮してなされたもので、多項式補間を用いずに高速に実行可能な完全秘密分散を実現し得る秘密分散装置、方法及びプログラムを提供することを目的とする。
【0011】
本発明の他の目的は、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上し得る秘密分散装置のプログラムを提供することにある。
【課題を解決するための手段】
【0012】
第1の発明は、秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置であって、前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段と、この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段と、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する手段と、前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段と、前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)と、前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段と、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段と、前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元手段とを備えた秘密分散装置である。
【0013】
第2の発明は、秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sをn’−1個に分割すると共に、分割結果に1からn’−1までの行番号j(但し、0≦j≦n’−1)を割り当てることにより、互いに同一サイズのn’−1個の第1分割秘密データK(1),…,K(j),…,K(n’-1)を生成する手段、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、前記各分割秘密データのサイズ以上のサイズを有するn’−1個の乱数を生成すると共に、各生成結果に0からn’−2までの列番号i(但し、0≦i≦n’−2)を割り当ててn’−1個の乱数データR(0),…,R(i),…,R(n’-2)を生成する手段、前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n’-1)及び前記乱数データR(0),…,R(i),…,R(n’-2)に基づいて、n(n’−1)個の分散部分データD(j,i)=K(j−i(mod n’))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、前記各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、前記(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する手段、前記判定結果が変更可能条件を満たすとき、前記任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する分散情報生成手段、この生成したt個の分散情報D(n),…,D(n-1+t)を前記n個の記憶装置とは異なるt個の記憶装置に個別に配布する手段、として機能させるためのプログラムである。
【0014】
第3の発明は、秘密情報Sが分散されてなる5個の分散情報D(0),…,D(4)を個別に5個の記憶装置に配布し、且つ、前記5個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,5)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(4)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する手段、前記各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する手段、前記2個の分割秘密データK(0),K(1)、前記4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する手段、 D(0,0)=R(0)、 D(0,1)=K(0)(+)R(1)(+)R(2)、 D(1,0)=R(1)、 D(1,1)=K(1)(+)R(2)(+)R(3)、 D(2,0)=R(2)、 D(2,1)=K(0)(+)R(3)(+)R(0)、 D(3,0)=R(3)、 D(3,1)=K(1)(+)R(0)(+)R(1)、 D(4,0)=K(1)(+)R(0)(+)R(2)、 D(4,1)=K(0)(+)R(1)(+)R(3)、前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に前記5個の記憶装置に配布する手段、前記配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、として機能させるためのプログラムである。
【0015】
第4の発明は、秘密情報Sが分散されてなる7個の分散情報D(0),…,D(6)を個別に7個の記憶装置に配布し、且つ、前記7個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,7)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(6)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する手段、前記各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する手段、前記3個の分割秘密データK(0)〜K(2)、前記6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する手段、 D(0,0)=R(0)、 D(0,1)=K(0)(+)R(1)(+)R(2)、 D(0,2)=K(2)(+)R(3)(+)R(5)、 D(1,0)=R(1)、 D(1,1)=K(1)(+)R(2)(+)R(3)、 D(1,2)=K(0)(+)R(0)(+)R(4)、 D(2,0)=R(2)、 D(2,1)=K(2)(+)R(3)(+)R(4)、 D(2,2)=K(1)(+)R(1)(+)R(5)、 D(3,0)=R(3)、 D(3,1)=K(0)(+)R(4)(+)R(5)、 D(3,2)=K(2)(+)R(0)(+)R(2)、 D(4,0)=R(4)、 D(4,1)=K(1)(+)R(5)(+)R(0)、 D(4,2)=K(0)(+)R(1)(+)R(3)、 D(5,0)=R(5)、 D(5,1)=K(2)(+)R(0)(+)R(1)、 D(5,2)=K(1)(+)R(2)(+)R(4)、 D(6,0)=K(1)(+)R(0)(+)R(3)、 D(6,1)=K(2)(+)R(1)(+)R(4)、 D(6,2)=K(0)(+)R(2)(+)R(5)、前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に前記7個の記憶装置に配布する手段、前記配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、として機能させるためのプログラムである。
【0016】
(作用)
第1〜第4の各発明は、排他的論理和を用いた(2,n)型、(3,5)型、又は(3,7)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0017】
これに加え、第2の発明は、メンバを追加したい場合に、配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、追加人数分のt個の分散情報D(n),…,D(n-1+t)を生成し、この分散情報D(n),…,D(n-1+t)を追加メンバに配布する。
【0018】
これにより、第2の発明は、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上させることができる。
【発明の効果】
【0019】
以上説明したように本発明によれば、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【発明を実施するための最良の形態】
【0020】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の各装置は、各装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【0021】
(第1の実施形態)
図1は本発明の第1の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、1台のクライアント装置10及びn−1台の保管サーバ装置20,30,…,n0が互いにインターネット等のネットワークNWを介して接続されている。
【0022】
これら合計n台の装置10,20,30,…,n0は、(k,n)しきい値秘密分散法におけるn人のメンバに対応する。特に、n台の装置10,20,…,n0が個別に有するn個の保存部11,21,…,n1は、n人のメンバが個別に有するn個の記憶装置に対応する。各装置10,20,30,…,n0には、それぞれ分散情報の配布順番を示すj番号(行番号)が割当てられている。例えば、クライアント装置10には、j=0番目が割り当てられており、保管サーバ装置20にはj=1番目が割り当てられている。保管サーバ装置30にはj=2番目が割り当てられ、…、保管サーバ装置n0にはj=n−1番目が割り当てられている。
【0023】
ここで、クライアント装置10は、秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn台の装置10,20,…,n0に配布し、且つ、n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置を実現するものである。なお、分散情報の個数は2個以上であればよい。例えばn=2とし、秘密情報Sをn−1(=1)個に分割して後述するK(1)とし、配布した2個の分散情報D(0),D(1)から秘密情報Sを復元してもよい。
【0024】
具体的にはクライアント装置10は、保存部11、入力部12、分散部分データ生成部13、ハッシュ値生成部14、元データ復元部15、ハッシュ値検証部16、制御部17、出力部18及び通信部19が互いにバスを介して接続されている。
【0025】
保存部11は、制御部19から読出/書込可能なハードウェア資源としての記憶装置であり、後述する分散情報D(0)〜D(n-1)が配布される前に、秘密情報Sが一時的に記憶され、分散情報D(0)〜D(n-1)が作成されると、分散情報作成情報が記憶され、分散情報が配布された後、j=0番目の分散情報D(0)が記憶されると共に、秘密情報Sが削除される。ここで、分散情報作成情報は、分散情報D(j)の識別情報jと、分散情報D(j)の配布先識別情報(装置ID、装置のアドレス情報等)とが互いに関連付けられた情報である。
【0026】
入力部12は、キーボード又はマウス等の通常の入力デバイスであり、操作者の操作により、分散処理又は復号処理の開始等の命令や、秘密情報S等の情報をクライアント装置10内に入力する機能をもっている。
【0027】
分散部分データ生成部13は、制御部17により制御され、保存部11に一時的に記憶された秘密情報Sに基づいて、図2に一例(n=5の例)を示すように、n(n−1)個の分散部分データD(j,i)を生成する機能をもっている。具体的には、分散部分データ生成部12は、以下の各機能(f12−1)〜(f12−4)をもっている。
【0028】
(f12−1) 保存部11に記憶された秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の分割秘密データK(1),…,K(j),…,K(n-1)を生成する機能。
【0029】
(f12−2) 各分割秘密データのサイズと同一サイズのゼロ値データを作成し、作成結果に行番号j=0を割り当てて分割秘密データK(0)を生成する機能。
【0030】
(f12−3) 各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する機能。なお、各乱数R(i)は、互いに異なる値である。
【0031】
(f12−4) 分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する機能(但し、(+)は排他的論理和を表す記号)。なお、K(j−i(mod n))=K(0)(=0)の場合、必ずしもK(0)の項を計算する必要は無く、例えばK(0)の項の計算無しにD(j,i)=R(i)としてもよい。このように、K(0)(=0)の場合、必ずしもK(0)の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【0032】
ハッシュ値生成部14は、制御部17により制御され、制御部17からバスを介してヘッダ情報H(j)が入力されると、ヘッダ情報H(j)のハッシュ値h(H(j))を生成し、得られたハッシュ値h(H(j))をバスに出力する機能をもっている。なお、ハッシュ値生成部14は、ヘッダ情報H(j)を検証しない場合、省略可能である。
【0033】
元データ復元部15は、制御部17に制御され、n台の装置10,…,n0に配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、秘密情報Sを復元する秘密情報復元機能をもっている。具体的には元データ復元部15は、以下の各機能(f15−1)〜(f15−8)をもっている。
【0034】
(f15−1) 2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する機能。
【0035】
(f15−2) この判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する第1の復元機能(但し、r=j−i(mod n))。なお、K(0)(=0)の項は必ずしも計算する必要が無く、例えばK(0)の項の計算無しにK(r)=D(i,i)(+)D(j,i)としてもよい。
【0036】
(f15−3) この分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する機能。
【0037】
(f15−4) この判定結果が第1終了条件を満たさないとき、分割秘密データK(r)の復元の式をrだけずらすことにより、第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する第2の復元機能(但し、K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),…,K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))。
【0038】
(f15−5) f15−3の判定結果が第1終了条件を満たすとき又はf15−1により分散情報D(i)が分散部分データD(i,i)を含まないとき、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、他の分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する第3の復元機能。なお、K(0)(=0)の項は必ずしも計算する必要が無く、例えばK(0)の項の計算無しにK(−r)=D(i,j)(+)D(j,j)としてもよい。
【0039】
(f15−6) この分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する機能。
【0040】
(f15−7) この判定結果が第2終了条件を満たさないとき、分割秘密データK(−r)の復元の式をrだけずらすことにより、第2終了条件を満たすまで、順次、残りの分割秘密データK(−r−r),…,K(−(n-1)r)を復元する第4の復元機能(但し、K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),…,K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))。
【0041】
(f15−8) 各復元機能のうち、該当する各復元機能により復元されたn−1個の分割秘密データK(1),…,K(n-1)を互いに連接することにより、秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する機能(但し、‖は連接を表す記号)。
【0042】
ハッシュ値検証部16は、制御部17により制御され、制御部17からバスを介してヘッダ情報H(j)及びそのハッシュ値h(H(j))が入力されると、ハッシュ値h(H(j))に基づいてヘッダ情報H(j)を検証し、検証結果をバスに出力する機能をもっている。検証内容は、ヘッダ情報H(j)から計算したハッシュ値と、入力されたハッシュ値h(H(j))との一致により、ヘッダ情報H(j)を正当と判定する方式である。なお、ハッシュ値検証部16は、ヘッダ情報H(j)を検証しない場合、省略可能である。
【0043】
ここで、ヘッダ情報H(j)は、図3の上方に一例を示すように、行番号jを示すデータ識別子、ヘッダのサイズを表すヘッダーサイズ、元データのサイズを表す元データサイズm、元の秘密情報Sの分割数を示す分割数n−1、分散部分データD(i,j)の処理単位ビットを示す処理単位ビット長a、乱数R(i)のデータサイズを示す乱数データサイズa、分割秘密データK(j)のサイズを表す分割データサイズa、パディングの有無やアルゴリズムを表すパディングアルゴリズム、ハッシュアルゴリズム情報(オプション)などが考えられる。ハッシュアルゴリズム情報は、ヘッダ情報のハッシュ値を算出し、ヘッダ情報の原本性を保証する場合などに追加される。すなわち、ハッシュアルゴリズム情報は、セキュリティの要件などに応じて追加又は省略される。但し、セキュリティの要件として予めシステムでハッシュアルゴリズムを決めている場合には、ハッシュアルゴリズム情報は、ヘッダ情報から省略可能である。
【0044】
なお、分散情報D(j)のデータフォーマットは、図3の下方に一例を示すように、ヘッダ情報H(j)、そのハッシュ値h(H(j))、n−1個の分散部分データD(j,0),D(j,1),…,D(j,n-2)から構成されている。ここで、ハッシュ値h(H(j))は、オプション(option)であり、ヘッダ情報H(j)内のハッシュアルゴリズム情報と同様に、セキュリティの要件に応じて省略可能となっている。
【0045】
制御部17は、入力部12から入力される命令に基づいて、後述する図4及び図5のフローチャートに基づいて、各部11,13〜16,18,19を制御する機能をもっている。また、制御部17は、例えば、以下の機能(f17−1)〜(f17−2)をもっている。
【0046】
(f17−1) 分散部分データ生成部13により生成された各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する機能。
【0047】
(f17−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を通信部19を介して個別にn台の装置10,20,…,n0に配布する機能。なお、制御部17は、分散情報D(0)〜D(n-1)の漏洩防止の観点から、分散情報D(0)〜D(n-1)を暗号化した状態で配布してもよい。
【0048】
出力部18は、ディスプレイ装置やプリンタ装置等の通常の出力デバイスであり、制御部18により制御され、命令等の入力画面や、復元後の秘密情報S等の出力画面等を出力する機能をもっている。
【0049】
通信部19は、制御部17により制御され、クライアント装置10とネットワークNWとの間の通信インターフェイス機能をもっている。
【0050】
一方、各保管サーバ装置20〜n0について説明する。
各保管サーバ装置20〜n0は、記憶する分散情報D(1)〜D(n-1)が互いに異なる他は互いに同一構成のため、ここでは保管サーバ装置20を代表例に挙げて説明する。
【0051】
保管サーバ装置20は、保存部21及び通信部22を備えている。
【0052】
保存部21は、通信部22から読出/書込可能なハードウェア資源としての記憶装置であり、クライアント装置10から配布された分散情報D(1)が記憶される。
【0053】
通信部22は、クライアント装置10から配布された分散情報D(1)を保存部21に書き込む機能と、クライアント装置10から要求された分散情報D(1)を保存部21から読み出してこの分散情報D(1)をクライアント装置10に返信する機能とをもっている。
【0054】
なお、通信部22は、分散情報D(1)の漏洩防止の観点から、クライアント装置10の認証機能を有してもよく、この場合、クライアント装置10の認証の後、分散情報D(1)を返信する構成として設けられる。
【0055】
ここで、各保管サーバ装置20,30,…,n0は、他のクライアント装置や、USB(Universal Serial Bus)メモリ、携帯電話、PDA(Personal Digital Assistants:携帯情報端末)に置き換え可能であり、あるいは外付けHDD(Hard Disc Drive: 固定磁気ディスク装置)などのように、コンピュータ以外の他の装置と置き換えることも可能である。
【0056】
なお、各保管装置20,30,…,n0は、他のクライアント装置に置き換えられる場合、前述同様に、分散部分データ生成部13や元データ復元部15などの機能を保持していてもよい。すなわち、秘密情報を復元できる装置は、クライアント装置10以外にあってもよい。例えば、各保管装置20,30,…,n0のうちの任意の台数の装置j0,…が秘密情報を復元できる構成としてもよい。なお、分散の場合も同様に、秘密情報を分散できる装置は、クライアント装置10以外にあってもよい。例えば、各保管装置20,30,…,n0のうちの任意の台数の装置j0,…が分散情報を配布できる構成としてもよい。また、各保管装置20,30,…,n0がUSBメモリや携帯電話などのように物理的な接続手段又は無線通信手段を有する装置に置き換えられる場合、ネットワークNWを省略してもよい。上述した各保管装置20,30,…,n0を他の装置に置き換えた変形例は、以下の各実施形態でも同様に適用可能である。
【0057】
次に、以上のように構成された秘密分散システムの動作を説明する。ここでは(2,n)型のしきい値秘密分散法を例に挙げて述べる。
【0058】
始めに、n人のメンバ(初期メンバ)に、秘密情報Sを(2,n)しきい値秘密分散法で分散した分散情報D(j)を配布する場合を考える。このときnは素数を選ばなければならない。従って、合成数のn人に分散情報を配布したい場合は、n<n’でありかつn’が素数となるようなn’について秘密分散法を適用することになる。以下では(2,n)秘密分散法についての一例を示す。
【0059】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(n-1)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0060】
このとき、クライアント装置10においては、図4に示すように、操作者(以下、ディーラーともいう)の操作により、分散処理の開始命令が入力部12から入力されたとする(ST1)。
【0061】
クライアント装置10は、この開始命令に基づいて、分散処理を開始する。制御部17は、秘密情報Sのビット長をm、分散数をn、処理単位ビットをaと定める(ST1)。なお、秘密情報Sのビット長mは、保存部11内の秘密情報Sから分かる。処理単位ビットaは、分散データ生成部13の仕様により予め定まっている。
【0062】
続いて、制御部17は、ビット長mの秘密情報Sをn−1個に分割した際のビット長(m/(n-1))が処理単位ビットaを超える(m/(n-1)>a)か否かを判定し(ST2)、処理単位ビットaを超える場合、nより大きい素数n’を探索し、得られた素数n’を分散数nと置き換えて(ST3)、ステップST1に戻る。
【0063】
一方、ステップST2の判定の結果が否の場合、制御部17は、秘密情報S及び分散数nを分散部分データ生成部13に入力する。
【0064】
分散部分データ生成部13は、秘密情報S及び分散数nに基づいて、ビット長mの秘密情報Sをn−1個に分割した際のビット長(m/(n-1))が処理単位ビットaと等しいか(m/(n-1)=a)か否かを判定する(ST4)。
【0065】
ステップST4の判定結果が否の場合、分散部分データ生成部13は、秘密情報Sをn−1個の分割秘密データK(0)〜K(n-2)に分割した際の末尾の分割秘密データK(n-2)をパディングする(パディング有)とし(ST5)、ステップST6に進む。
【0066】
なお、パディングは、必ずしも末尾の分割秘密データK(n-2)に行わなくても良く、他の分割秘密データK(j)に行っても良い。但し、本実施形態では、秘密情報Sは4個にちょうど分割できた場合(パディング無し)を例に挙げて述べる。また、図2に示した如き、分散数n=5,しきい値k=2の(2,5)型を例に挙げて述べる。
【0067】
ステップST4の判定の結果、処理単位ビットaと等しい場合、分散部分データ生成部13は、この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の分割秘密データK(1),…,K(j),…,K(n-1)を生成する。(2,5)型の例では、分割秘密データK(1),…,K(4)が生成される。
【0068】
また、分散部分データ生成部13は、各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて分割秘密データK(0)を生成する。
【0069】
さらに、分散部分データ生成部13は、各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する(ST6)。(2,5)型の例では、4個の乱数データR(0),…,R(3)が生成される。
【0070】
次に、分散部分データ生成部13は、分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する(ST7)。この算出は、行番号jを0からn-1まで繰り返すと共に、列番号iを0からn-2まで繰り返すことにより行う。(2,5)型の例では、図2に示したように、20個の分散部分データD(j,i)が生成される。また、K(j−i(mod n))=K(0)(=0)の場合、K(0)の項を計算せずに、D(j,i)=R(i)としてもよい。
【0071】
しかる後、分散部分データ生成部13は、得られた分散部分データn(n−1)個の分散部分データD(j,i)を制御部17に出力する。
【0072】
制御部17は、各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する(ST8)。ヘッダ情報H(j)には、K(n-1)に対するパディングの有無、元データのサイズなどの情報が含まれる。
【0073】
制御部17は、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別にn個の保存部11,21,…,n1に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(n-1)を個別に保管サーバ装置20,…,n0に配布する(ST9)。(2,5)型の例では、5個の分散情報D(0),…,D(4)が配布される。各保管サーバ装置20〜50では、配布された分散情報D(1),…,D(4)を保存部21〜51に記憶する。
【0074】
以上により、秘密情報の分散処理が完了する。
【0075】
なお、(2,5)型において、必ずしも5個の分散情報D(0)〜D(4)を配布する必要は無い。例えば4個の分散情報D(0)〜D(3)を配布しておき、残り1個の分散情報D(4)を新メンバが追加されたときに新メンバに配布してもよい。このことについては、後の第2の実施形態で述べる。
【0076】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0077】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17は、n台の装置10,…,n0に配布したn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)を収集し(ST11)、得られた分散情報D(i),D(j)を元データ復元部15に入力する。
【0078】
元データ復元部15は、分散情報D(i),D(j)を受けると、2つの分散情報D(i),D(j)のヘッダ情報H(i),H(j)から、図6及び図7に示すように、例えば、j=(i=)1番目、j=3番目の分散情報D(i),D(j)であることを解析する(ST12)。例えば分散情報D(1),D(3)であることを確認する。
【0079】
元データ復元部15は、2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する(ST13)。例えば分散情報D(1)に関し、分散部分データD(1,1)を含むかを判定する。
【0080】
ステップST13の判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき(ST13;YES)、元データ復元部15は、ステップST14を実行する。
【0081】
ステップST14においては、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する(但し、r=j−i(mod n))。
【0082】
例えば、分散部分データD(1,1)と、分割秘密データK(0)(=0)との排他的論理和に基づいて、乱数データR(1)を算出する(ST14−1)。なお、K(0)(=0)との排他的論理和を計算せずに、D(1,1)=R(1)としてもよい。続いて、乱数データR(1)と、分散部分データD(3,1)との排他的論理和に基づいて、分割秘密データK(2)を復元する(ST14−2)。
【0083】
また、この分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する。例えばK(2)の復元後、第1終了条件i−r(mod 5)=1−2(mod 5)=4が、n−1=5−1=4を満たすか否かを判定する。この場合は満たす。
【0084】
この判定結果が第1終了条件を満たさないとき、分割秘密データK(r)の復元の式をrだけずらすことにより、第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する。但し、
K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),
…,
K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))。
【0085】
一方、ステップST14中の判定結果が第1終了条件を満たすとき又はステップST13の判定結果が否のとき、元データ復元部15は、ステップST15を実行する。
【0086】
ステップST15においては、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、他の分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する。
【0087】
例えば、分散部分データD(3,3)と、分割秘密データK(0)(=0)との排他的論理和に基づいて、乱数データR(3)を算出する(ST15−1)。なお、K(0)(=0)との排他的論理和を計算せずに、D(3,3)=R(3)としてもよい。続いて、乱数データR(3)と、分散部分データD(1,3)との排他的論理和に基づいて、分割秘密データK(3)を復元する(ST15−2)。
【0088】
また、この分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する。例えばK(3)の復元後、第2終了条件j+r(mod 5)=3+2(mod 5)=5(mod 5)=0が、n−1=4を満たすか否かを判定する。この場合は満たさない。
【0089】
この判定結果が第2終了条件を満たさないとき、分割秘密データK(−r)の復元の式をrだけずらすことにより、第2終了条件を満たすまで、順次、残りの分割秘密データK(−r−r),…,K(−(n-1)r)を復元する。但し、
K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),
…,
K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))。
【0090】
例えば、図6及び図7のステップST15−3からST15−6により、残りの分割秘密データK(1),K(4)を復元する。
【0091】
ステップST15が完了すると、元データ復元部15は、復元されたn−1個の分割秘密データK(1),…,K(n-1)を制御部17に送出する。この例では、4個の分割秘密データK(1),…,K(4)が送出される。
【0092】
制御部17は、分割秘密データK(1),…,K(n-1)に対して、ヘッダ情報H(i),H(j)に基づいて、パディングなどの処理があれば除去する(ST16)。しかる後、制御部17は、分割秘密データK(1),…,K(n-1)を互いに連接することにより、秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する(ST17)。この例では、秘密情報S=K(1)‖K(2)‖…‖K(4)が復元される。
【0093】
上述したように本実施形態によれば、排他的論理和を用いた(2,n)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0094】
補足すると、本実施形態は、特許文献1記載の技術とは異なり、完全秘密分散法を実現しているため、k−1個以下の分散部分データから、元の秘密情報を復元できないだけでなく、秘密情報の部分データも復元できないという効果を得ることができる。
【0095】
これに加え、本実施形態によれば、分散部分データをK(*)+R(*)として、K(0)を擬似的に作ることで全て同じ形式となり、アルゴリズム的に分散部分データを作成することが可能である。これに対し、特許文献1での分散部分データはK(*)+R(*)、K(*)+R(*)+R(*)、R(*)など、分散部分データ毎に部分秘密データと乱数の組み合わせが異なっているため、うまくアルゴリズム的に作成できない。また、特許文献1の分散部分データでは、K(*)+R(*)+R(*)といった分散部分データから復元する際に、計算量がどうしても多くなるため、本実施形態と比べて計算量が増大している。
【0096】
(第2の実施形態)
次に、本発明の第2の実施形態について図1を参照しながら説明する。
本実施形態は、第1の実施形態の変形例であり、(2,n)型のしきい値秘密分散を(2,n’)型のしきい値秘密分散(n<n’)に拡張可能な構成により、新メンバを追加可能とした形態となっている。
【0097】
ここで、nは、第1の実施形態とは異なり、素数に限らない。nが素数でない場合はnよりも大きな素数n’を用いて(2,n’)型の秘密分散法を構築し、そのうちn人に分散情報を配布することで(2,n)型の秘密分散システムを実現する。この場合、n’−n人だけ新メンバの追加が可能である。例えば、(2,5)型の秘密分散法を構築しておき、そのうち4人に分散情報を配布することで(2,4)型の秘密分散システムを実現する。この場合、1人だけ新メンバの追加が可能である。
【0098】
新メンバ用の分散情報は、追加時にクライアント装置10が作成してもよく、あるいは、最も権限があるユーザ、前述したディーラー、又は信頼できる第三者機関(trusted third party)などのクライアント装置又は保管サーバ装置等が作成することが考えられる。これは任意のユーザがメンバーを追加可能なシステムでは、ユーザ全体を管理することが困難なためである。特定のユーザや機関によってのみ追加可能な形態が望まれる。
【0099】
次に、第2の実施形態の具体的な構成を述べる。
【0100】
クライアント装置10は、秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の保存部11,…,n0に配布し、且つ、n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置を実現している。
【0101】
ここで、制御部17は、前述した機能に加え、(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する機能と、判定結果が変更可能条件を満たすとき、任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する機能と、この生成したt個の分散情報D(n),…,D(n-1+t)をn個の保存部11,…,n0とは異なるt個の記憶装置に個別に配布する機能とをもっている。
【0102】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0103】
図8に示すように、複数のメンバーからなるあるグループで、秘密情報Sを(k,n’)しきい値秘密分散法(n<n’、k≦n)を用いて分散し、n’個の分散情報のうち、n個の分散情報をn人のメンバーに配布した状態において、新たにt人の新規メンバーがそのグループに追加される場合を考える(ST21)。
【0104】
例えば、図9に示すように、秘密情報Sを(2,5)しきい値秘密分散法を用いて分散し、n’=5個の分散情報のうち、n=4個の分散情報を4人のメンバーに配布した状態において、新たにt=1人の新規メンバーがそのグループに追加される場合である。
【0105】
まず、分散情報を既に保持しているメンバーの分散情報を用いてディーラーが新規メンバー用の分散情報を作成する場合を考える。
【0106】
このとき、クライアント装置10においては、制御部17が、保存部11内の分散情報作成情報に基づいて、配布済みの分散情報D(j)の個数nを確認し、変更可能条件t≦n’−nを満たすか否かを判定する(ST22)。
【0107】
制御部17は、ステップST22の判定結果が変更可能条件を満たすとき、任意の2個の分散情報D(i),D(j)を収集し(ST23)、この分散情報D(i),D(j)に基づいて、n+1番目の分散部分データD(n,0)〜D(n,n’-2)を生成し、以下同様に、順次、n+t番目の分散部分データD(n-1+t,0)〜D(n-1+t,n’-2)を生成する(ST24)。
【0108】
例えば、制御部17は、図10に示すように、2個の分散情報D(1),D(3)に基づいて、5番目の分散部分データD(4,0)〜D(4,3)を生成する。このとき、分散部分データD(4,0)〜D(4,3)は、次のように算出される。
【0109】
D(4,0)=D(1,0)(+)D(1,2)(+)D(3,2)、
D(4,1)=D(1,1)(+)D(1,3)(+)D(3,3)、
D(4,2)=D(1,0)(+)D(1,1)(+)D(1,3)(+)D(3,0)(+)D(3,1)(+)D(3,2)(+)D(3,3)、
D(4,3)=D(1,0)(+)D(1,3)(+)D(3,0)。
【0110】
制御部17は、各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててt個のヘッダ情報H(n),…,H(n-1+t)を生成する(ST25)。この例では、t=1なので、ヘッダ情報H(4)が生成される。
【0111】
制御部17は、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるt個の分散情報D(n),…,D(n-1+t)を生成する。この例では、t=1個の分散情報D(4)が生成される。また、制御部17は、分散情報作成情報を、t個の分散情報D(n),…,D(n-1+t)の識別情報j(=n,…,n-1+t)を含むように更新する(ST26)。この例では、分散情報作成情報は、識別情報j=4を含むように更新される。
【0112】
しかる後、制御部17は、この生成したt個の分散情報D(n),…,D(n-1+t)をn個の保存部11,…,n0とは異なるt個の記憶装置に個別に配布する(ST27)。この例では、t=1個の分散情報D(4)が1個の記憶装置に配布される。
【0113】
これにより、(2,n)型の秘密分散システムは(2,n+t)型の秘密分散システムに拡張される。この例では、(2,4)型が(2,5)型に拡張される。ここで、t=n’−nの場合、(2,n+t)型は(2,n’)型である。
【0114】
一方、ステップST22の判定結果が変更可能条件を満たさないとき、n’よりも大きな素数n”について(2,n”)型の秘密分散法を適用し、全てのメンバー(n+t人)に分散情報を配布しなおす(ST29)。この場合も(2,n)型が(2,n+t)型に拡張される。
【0115】
上述したように本実施形態によれば、第1の実施形態の効果に加え、(2,n)型の秘密分散法を(2,n+t)型又は(2,n’)型の秘密分散システムに拡張することができる(t≦n’−n、n<n’)。
【0116】
補足すると、メンバを追加したい場合に、配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、追加人数分のt個の分散情報D(n),…,D(n-1+t)を生成し、この分散情報D(n),…,D(n-1+t)を追加メンバに配布している。
【0117】
例えば(2,4)型を(2,5)型に拡張する場合、4番目の分散情報D(4)を新たなメンバーに配布することで、予め配布していた分散情報D(0)〜D(3)を更新することなく、(2,5)型の秘密分散法に拡張可能となっている。
【0118】
この際、追加する分散情報D(n),…は、2個の分散情報から元の秘密情報を復元することなく作成可能となっている。また、データ分割時にn’を大きくとっておくことでメンバーの追加に対応可能である。
【0119】
また、本実施形態によれば、初期に配布した分散情報を更新することなく新たなメンバーを追加することが可能になる。また、ディーラーが既存の分散情報を使って新たに分散情報を作成するので、元の秘密情報をディーラー又はその他のメンバーが保持している必要がなく、セキュリティ上セキュアなシステムを構築することが可能になる。すなわち、本実施形態によれば、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上させることができる。また、権限を保持している既存のメンバーが協力して新たなメンバーに分散情報を配布することも可能になる。
【0120】
(第3の実施形態)
図11は本発明の第3の実施形態に係る秘密分散システムの構成を示す模式図であり、図1と同一部分には同一符号を付し、ほぼ同一部分にはアルファベットの添字を付してその詳しい説明を省略する。なお、以下の各実施形態も同様にして重複した説明を省略する。
【0121】
本実施形態は、第1の実施形態の変形例であり、(3,5)型の秘密分散システムとなっている。これに伴い、分散部分データ生成部13a、元データ復元部15a及び制御部17aの機能が(3,5)型の秘密分散システムに対応して変更されている。また、保管サーバ装置20,30,40,50の台数は、n−1=4台と定まっている。
【0122】
ここで、分散部分データ生成部13aは、具体的には、以下の機能(f13a−1)〜(f13a−4)をもっている。
【0123】
(f13a−1) 制御部17aから受けた秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する機能。
【0124】
(f13a−2) 各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する機能。
【0125】
(f13a−3) 2個の分割秘密データK(0),K(1)、4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する機能。
【0126】
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(2,0)=R(2)、
D(2,1)=K(0)(+)R(3)(+)R(0)、
D(3,0)=R(3)、
D(3,1)=K(1)(+)R(0)(+)R(1)、
D(4,0)=K(1)(+)R(0)(+)R(2)、
D(4,1)=K(0)(+)R(1)(+)R(3)。
【0127】
(f13a−4) 算出した10個の分散部分データD(j,i)を制御部17aに送出する機能。
【0128】
元データ復元部15aは、配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)が制御部17aから入力されると、この3個の分散情報D(j)に基づいて、秘密情報Sを復元する復元機能をもっている。
【0129】
制御部17aは、入力部12から入力される命令に基づいて、後述する図12及び図14のフローチャートに基づいて、各部11,13a,14,15a,16,18,19を制御する機能をもっている。また、制御部17aは、例えば、以下の機能(17a−1)〜(17a−2)をもっている。
【0130】
(17a−1) 各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する機能。
【0131】
(17a−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に5個の保存部11〜51に配布する機能。
【0132】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0133】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(4)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0134】
このとき、クライアント装置10においては、操作者の操作により、分散処理の開始命令が入力部12から入力されると、分散処理を開始する。
【0135】
制御部17aは、保存部11内の秘密情報Sを分散部分データ生成部13aに入力する。
【0136】
分散部分データ生成部13aは、図12に示すように、秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する(ST31)。
【0137】
ここで、2個の分割秘密データK(0),K(1)は、互いに同一サイズでなければいけない。このため、秘密情報Sが奇数ビットのサイズの場合、2の倍数のビット(桁)で表現されるように、末尾に0が付加(パディング)される。その後、パディング済みの秘密情報Sを同じデータサイズになるように2個に分ける。データサイズはビット単位で扱う。2の倍数のビットとは、例えば10100110のように表現される。
【0138】
次に、分散部分データ生成部13aは、分割秘密データK(0)、K(1)と同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する(ST32)。
【0139】
分散部分データ生成部13aは、2個の分割秘密データK(0),K(1)、4個の乱数データR(0)〜R(3)に基づいて、図13に示すように、10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する。
【0140】
しかる後、分散部分データ生成部13aは、これら分散部分データを制御部17aに送出する。
【0141】
制御部17aは、各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する(ST33)。
【0142】
次に、制御部17aは、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を生成する。例えば、分散情報D(0)は、ヘッダ情報H(j)と、分散部分データD(0,0)と、分散部分データD(0,1)とをビット列単位で結合したものである。
【0143】
しかる後、制御部17aは、5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に5個の保存部11〜51に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(4)を個別に保管サーバ装置20,…,50に配布する(ST34)。各保管サーバ装置20〜50では、配布された分散情報D(1),…,D(4)を保存部21〜51に記憶する。
【0144】
以上により、秘密情報の分散処理が完了する。
【0145】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0146】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17aは、図14に示すように、5台の装置10,…,50に配布した5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報を収集し(ST35)、得られた分散情報を元データ復元部15aに入力する。この例では、5個の分散情報のうち、D(0)、D(2)、D(4)を用いることとする。
【0147】
元データ復元部15aは、分散情報D(0)、D(2)、D(4)を受けると、分散情報のヘッダ情報H(0),H(2),H(4)を参照し、分散情報D(j)毎に、分散部分データD(j,0),D(j,1)を確認する(ST36)。
【0148】
元データ復元部15aは、分散情報D(j)毎の分散部分データD(j,0),D(j,1)に基づいて、2個の分割秘密データK(0),K(1)を算出する(ST37)。
【0149】
例えば、図15に示すように、分散部分データD(0,0)、D(2,0)とD(4,0)との排他的論理和により、分割秘密データK(1)を算出する(ST37−1)。
【0150】
分散部分データD(0,0)とD(2,1)との排他的論理和により、中間データK(0)(+) R(3)を算出する(ST37−2)。
【0151】
分散部分データD(2,0)とD(0,1)との排他的論理和により、中間データK(0)(+) R(1)を算出する(ST37−3)。
【0152】
中間データK(0)(+) R(3)とK(0)(+) R(1)との排他的論理和により、中間データR(1)(+) R(3)を算出する(ST37−4)。
【0153】
中間データR(1)(+) R(3)と、分散部分データD(4,1)とにより、分割秘密データK(0)を算出する(ST37−5)。
【0154】
元データ復元部15aは、これら分割秘密データK(0),K(1)とヘッダ情報H(0),H(2),H(4)に基づいて、元の秘密情報S=K(0)‖K(1)を復元する(ST38)。
【0155】
上述したように本実施形態によれば、排他的論理和を用いた(3,5)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0156】
(第4の実施形態)
図16は本発明の第4の実施形態に係る秘密分散システムの構成を示す模式図である。
【0157】
本実施形態は、第1の実施形態の変形例であり、(3,7)型の秘密分散システムとなっている。これに伴い、分散部分データ生成部13b、元データ復元部15b及び制御部17bの機能が(3,7)型の秘密分散システムに対応して変更されている。また、保管サーバ装置20,30,40,50,60,70の台数は、n−1=6台と定まっている。
【0158】
ここで、分散部分データ生成部13bは、具体的には、以下の機能(f13b−1)〜(f13b−4)をもっている。
【0159】
(f13b−1) 制御部17bから受けた秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(1)を生成する機能。
【0160】
(f13b−2) 各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する機能。
【0161】
(f13b−3) 3個の分割秘密データK(0)〜K(2)、6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する機能。
【0162】
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(0,2)=K(2)(+)R(3)(+)R(5)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(1,2)=K(0)(+)R(0)(+)R(4)、
D(2,0)=R(2)、
D(2,1)=K(2)(+)R(3)(+)R(4)、
D(2,2)=K(1)(+)R(1)(+)R(5)、
D(3,0)=R(3)、
D(3,1)=K(0)(+)R(4)(+)R(5)、
D(3,2)=K(2)(+)R(0)(+)R(2)、
D(4,0)=R(4)、
D(4,1)=K(1)(+)R(5)(+)R(0)、
D(4,2)=K(0)(+)R(1)(+)R(3)、
D(5,0)=R(5)、
D(5,1)=K(2)(+)R(0)(+)R(1)、
D(5,2)=K(1)(+)R(2)(+)R(4)、
D(6,0)=K(1)(+)R(0)(+)R(3)、
D(6,1)=K(2)(+)R(1)(+)R(4)、
D(6,2)=K(0)(+)R(2)(+)R(5)。
【0163】
(f13b−4) 算出した21個の分散部分データD(j,i)を制御部17bに送出する機能。
【0164】
元データ復元部15bは、配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)が制御部17aから入力されると、この3個の分散情報D(j)に基づいて、秘密情報Sを復元する復元機能をもっている。
【0165】
制御部17bは、入力部12から入力される命令に基づいて、後述する図17及び図19のフローチャートに基づいて、各部11,13b,14,15b,16,18,19を制御する機能をもっている。また、制御部17bは、例えば、以下の機能(17b−1)〜(17b−2)をもっている。
【0166】
(17b−1) 各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する機能。
【0167】
(17b−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に7個の保存部11〜71に配布する機能。
【0168】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0169】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(6)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0170】
このとき、クライアント装置10においては、操作者の操作により、分散処理の開始命令が入力部12から入力されると、分散処理を開始する。
【0171】
制御部17bは、保存部11内の秘密情報Sを分散部分データ生成部13bに入力する。
【0172】
分散部分データ生成部13bは、図17に示すように、秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する(ST41)。
【0173】
ここで、3個の分割秘密データK(0),K(1),K(2)は、互いに同一サイズでなければいけない。このため、秘密情報Sが3の倍数のビット(桁)で表現されるように、末尾に0が付加(パディング)される。その後、パディング済みの秘密情報Sを同じデータサイズになるように3個に分ける。データサイズはビット単位で扱う。3の倍数のビットとは、例えば101001100のように表現される。
【0174】
次に、分散部分データ生成部13bは、分割秘密データK(0),K(1),K(2)と同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),…,R(5)を生成する(ST42)。
【0175】
分散部分データ生成部13bは、3個の分割秘密データK(0)〜K(2)、6個の乱数データR(0)〜R(5)に基づいて、図18に示すように、21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する。
【0176】
しかる後、分散部分データ生成部13bは、これら分散部分データを制御部17bに送出する。
【0177】
制御部17bは、各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),…,H(6)を生成する(ST43)。
【0178】
次に、制御部17bは、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),…,D(6)を生成する。例えば、分散情報D(0)は、ヘッダ情報H(j)、分散部分データD(0,0),D(0,1),D(0,2)を互いにビット列単位で結合したものである。
【0179】
しかる後、制御部17bは、7個の分散情報D(0),…,D(6)を個別に7個の保存部11〜71に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(6)を個別に保管サーバ装置20,…,70に配布する(ST44)。各保管サーバ装置20〜70では、配布された分散情報D(1),…,D(6)を保存部21〜71に記憶する。
【0180】
以上により、秘密情報の分散処理が完了する。
【0181】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0182】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17bは、図19に示すように、5台の装置10,…,70に配布した7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報を収集し(ST45)、得られた分散情報を元データ復元部15bに入力する。この例では、7個の分散情報のうち、D(0)、D(2)、D(6)を用いることとする。
【0183】
元データ復元部15bは、分散情報D(0)、D(2)、D(6)を受けると、分散情報のヘッダ情報H(0),H(2),H(6)を参照し、分散情報D(j)毎に、分散部分データD(j,0),D(j,1),D(j,2)を確認する(ST46)。
【0184】
元データ復元部15bは、分散情報D(j)毎の分散部分データD(j,0),D(j,1),D(j,2)に基づいて、3個の分割秘密データK(0),K(1),K(2)を算出する(ST47)。
【0185】
例えば、図20に示すように、分散部分データD(0,1)とD(6,2)との排他的論理和により、中間データR(1)(+) R(5)を算出する(ST47−1)。
【0186】
中間データR(1)+R(5)と、分散部分データD(2,2)との排他的論理和により、分割秘密データK(1)を算出する(ST47−2)。
【0187】
分割秘密データK(1)と、分散部分データD(6,0)とD(0、0)との排他的論理和により、乱数データR(3)を算出する(ST47−3)。
【0188】
分散部分データD(2,1)とD(6,1)との排他的論理和により、中間データR(1)(+) R(3)を算出する(ST47−4)。
【0189】
中間データR(1)(+) R(3)と、乱数データR(3)との排他的論理和により、乱数データR(1)を算出する(ST47−5)。
【0190】
乱数データR(1)とR(2)と、分散部分データD(0,1)との排他的論理和により、分割秘密データK(0)を算出する(ST47−6)。
【0191】
中間データR(1)(+) R(5)と、乱数データR(1)との排他的論理和により、乱数データR(5)を算出する(ST47−7)。
【0192】
分散部分データD(0,2)と、乱数データR(3)とR(5)との排他的論理和により、分割秘密データK(2)を算出する(ST57−8)。
【0193】
元データ復元部15bは、これら分割秘密データK(0)〜K(2)とヘッダ情報H(0),H(2),H(6)に基づいて、元の秘密情報S=K(0)‖K(1)‖K(2)を復元する(ST48)。
【0194】
上述したように本実施形態によれば、排他的論理和を用いた(3,7)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0195】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク(フロッピー(登録商標)ディスク、ハードディスクなど)、光ディスク(CD−ROM、DVDなど)、光磁気ディスク(MO)、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【0196】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【0197】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているOS(オペレーティングシステム)や、データベース管理ソフト、ネットワークソフト等のMW(ミドルウェア)等が上記実施形態を実現するための各処理の一部を実行しても良い。
【0198】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、LANやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【0199】
また、記憶媒体は1つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【0200】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の1つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【0201】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【0202】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【0203】
【図1】本発明の第1の実施形態に係る秘密分散システムの構成を示す模式図である。
【図2】同実施形態における分散部分データの一例を示す模式図である。
【図3】同実施形態におけるヘッダ情報及び分散情報の一例を示す模式図である。
【図4】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図5】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図6】同実施形態における復元処理の動作を説明するための模式図である。
【図7】同実施形態における復元処理の動作を説明するための参考図である。
【図8】本発明の第2の実施形態に係る秘密分散システムの動作を説明するためのフローチャートである。
【図9】同実施形態における分散部分データの一例を示す模式図である。
【図10】同実施形態における復元処理の動作を説明するための参考図である。
【図11】本発明の第3の実施形態に係る秘密分散システムの構成を示す模式図である。
【図12】同実施形態における分割処理の動作を説明するためのフローチャートである。
【図13】同実施形態における分散部分データの一例を示す模式図である。
【図14】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図15】同実施形態における復元処理の動作を説明するための模式図である。
【図16】本発明の第4の実施形態に係る秘密分散システムの構成を示す模式図である。
【図17】同実施形態における分割処理の動作を説明するためのフローチャートである。
【図18】同実施形態における分散部分データの一例を示す模式図である。
【図19】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図20】同実施形態における復元処理の動作を説明するための模式図である。
【符号の説明】
【0204】
10…クライアント装置、11〜n1…保存部、12…入力部、13,13a,13b…分散部分データ生成部、14…ハッシュ値生成部、15,15a,15b…元データ復元部、16…ハッシュ値検証部、17,17a,17b…制御部、18…出力部、19,22〜n2…通信部、20,30,…,n0…保管サーバ装置、NW…ネットワーク。
【技術分野】
【0001】
本発明は、秘密情報を分散させた分散情報を配布し、収集した分散情報から秘密情報を復元する秘密分散装置、方法及びプログラムに係り、例えば多項式補間を用いずに高速に実行可能な完全秘密分散を実現し得る秘密分散装置、方法及びプログラムに関する。
【背景技術】
【0002】
一般に、暗号化鍵などの秘密情報を紛失した場合の対策としては、予め秘密情報のコピーを作成しておくことが有効である。しかしながら、秘密情報のコピーを作成すると、盗難のリスクが高くなるという問題が生じる。このような問題を解決する手法として、1979年にシャミア(Shamir)が(k,n)しきい値秘密分散法と呼ばれる秘密分散法を提案している(例えば、非特許文献1参照)。
【0003】
(k,n)しきい値秘密分散法では、秘密情報をn個の分散情報に分割し、n個の分散情報の中から任意のk個を集めれば元の秘密情報を復元できるが、k−1個の分散情報からでは、元の秘密情報に関する情報を全く得られない。すなわち、(k,n)しきい値秘密分散法は、しきい値kを境にした秘密情報の復元特性をもっている(なお、1<k<n)。
【0004】
このため、(k,n)しきい値秘密分散法によれば、k−1個以下の分散情報が漏洩しても元の秘密情報が安全であり、n−k個以下の分散情報を紛失しても元の秘密情報を復元できるといった管理を実現できる。
【0005】
しかしながら、シャミアの(k,n)しきい値秘密分散法では、秘密情報の分散や復元の処理を、多くの計算量を要する多項式補間により実現するので、大量のデータを秘密分散するためには、高速な計算機を必要とする不都合がある。
【0006】
一方、このような不都合を解決し、計算量を大幅に削減し得る(k,n)しきい値秘密分散法として、荻原らの方式が知られている(例えば、特許文献1参照)。ここで、荻原らの方式は、秘密情報の分散処理や復元処理を排他的論理和演算のみで実現するので、高速に実行可能となっている。しかしながら、荻原らの方式は、例えば(3,4)しきい値法においては、分散データの取り方によっては、2個の分散データで元の秘密情報を復元できるなど(例えば、第132段落参照)、完全秘密分散ではない不都合がある。ここで、完全秘密分散とは、分散データの取り方によらずに、しきい値を境にした秘密情報の復元特性を有することを意味する。
【非特許文献1】A. Shamir: “How to share a secret", Communications of the ACM, 22, 11, pp.612-613 (1979)
【特許文献1】特開2004−213650号公報
【発明の開示】
【発明が解決しようとする課題】
【0007】
以上説明したように、シャミアによる(k,n)しきい値秘密分散法では、多項式補間を用いるため、高速な計算機が必要となる不都合がある。一方、荻原らの方式は、分散データの取り方によっては、完全秘密分散ではない不都合がある。
【0008】
また、本発明者の検討によれば、従来のシステムで分散情報を追加したい場合、次のように、(A)分散情報を全メンバに再配布する手法、又は(B)分散情報を追加メンバのみに配布する手法が考えられる。具体的には、手法(A)においては、追加後の人数に基づき、全ての分散情報を作成し直して全てのメンバに再配布する。手法(B)においては、ディーラーが予め分散情報を多めに作成して保持しておき、メンバ追加時に、この多めに作成してある分散情報を追加メンバのみに配布する。または手法(B)においては、ディーラーが秘密情報を保持しておき、追加人数分の分散情報を秘密情報から作成し、追加メンバのみに配布する方式としてもよい。
【0009】
しかしながら、追加時の手法(A)は、既存のメンバにも分散情報を再配布する必要があるので、手間がかかってしまう。また、手法(B)は、秘密情報を復元可能な数の分散情報、又は秘密情報それ自体を1箇所でディーラーが保持する必要があるので、セキュリティ性を低下させてしまう。
【0010】
本発明は上記実情を考慮してなされたもので、多項式補間を用いずに高速に実行可能な完全秘密分散を実現し得る秘密分散装置、方法及びプログラムを提供することを目的とする。
【0011】
本発明の他の目的は、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上し得る秘密分散装置のプログラムを提供することにある。
【課題を解決するための手段】
【0012】
第1の発明は、秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置であって、前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段と、この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段と、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する手段と、前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段と、前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)と、前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段と、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段と、前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元手段とを備えた秘密分散装置である。
【0013】
第2の発明は、秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sをn’−1個に分割すると共に、分割結果に1からn’−1までの行番号j(但し、0≦j≦n’−1)を割り当てることにより、互いに同一サイズのn’−1個の第1分割秘密データK(1),…,K(j),…,K(n’-1)を生成する手段、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、前記各分割秘密データのサイズ以上のサイズを有するn’−1個の乱数を生成すると共に、各生成結果に0からn’−2までの列番号i(但し、0≦i≦n’−2)を割り当ててn’−1個の乱数データR(0),…,R(i),…,R(n’-2)を生成する手段、前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n’-1)及び前記乱数データR(0),…,R(i),…,R(n’-2)に基づいて、n(n’−1)個の分散部分データD(j,i)=K(j−i(mod n’))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、前記各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、前記(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する手段、前記判定結果が変更可能条件を満たすとき、前記任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する分散情報生成手段、この生成したt個の分散情報D(n),…,D(n-1+t)を前記n個の記憶装置とは異なるt個の記憶装置に個別に配布する手段、として機能させるためのプログラムである。
【0014】
第3の発明は、秘密情報Sが分散されてなる5個の分散情報D(0),…,D(4)を個別に5個の記憶装置に配布し、且つ、前記5個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,5)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(4)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する手段、前記各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する手段、前記2個の分割秘密データK(0),K(1)、前記4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する手段、 D(0,0)=R(0)、 D(0,1)=K(0)(+)R(1)(+)R(2)、 D(1,0)=R(1)、 D(1,1)=K(1)(+)R(2)(+)R(3)、 D(2,0)=R(2)、 D(2,1)=K(0)(+)R(3)(+)R(0)、 D(3,0)=R(3)、 D(3,1)=K(1)(+)R(0)(+)R(1)、 D(4,0)=K(1)(+)R(0)(+)R(2)、 D(4,1)=K(0)(+)R(1)(+)R(3)、前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に前記5個の記憶装置に配布する手段、前記配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、として機能させるためのプログラムである。
【0015】
第4の発明は、秘密情報Sが分散されてなる7個の分散情報D(0),…,D(6)を個別に7個の記憶装置に配布し、且つ、前記7個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,7)型の秘密分散装置のプログラムであって、前記秘密分散装置のコンピュータを、前記分散情報D(0)〜D(6)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、この秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する手段、前記各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する手段、前記3個の分割秘密データK(0)〜K(2)、前記6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する手段、 D(0,0)=R(0)、 D(0,1)=K(0)(+)R(1)(+)R(2)、 D(0,2)=K(2)(+)R(3)(+)R(5)、 D(1,0)=R(1)、 D(1,1)=K(1)(+)R(2)(+)R(3)、 D(1,2)=K(0)(+)R(0)(+)R(4)、 D(2,0)=R(2)、 D(2,1)=K(2)(+)R(3)(+)R(4)、 D(2,2)=K(1)(+)R(1)(+)R(5)、 D(3,0)=R(3)、 D(3,1)=K(0)(+)R(4)(+)R(5)、 D(3,2)=K(2)(+)R(0)(+)R(2)、 D(4,0)=R(4)、 D(4,1)=K(1)(+)R(5)(+)R(0)、 D(4,2)=K(0)(+)R(1)(+)R(3)、 D(5,0)=R(5)、 D(5,1)=K(2)(+)R(0)(+)R(1)、 D(5,2)=K(1)(+)R(2)(+)R(4)、 D(6,0)=K(1)(+)R(0)(+)R(3)、 D(6,1)=K(2)(+)R(1)(+)R(4)、 D(6,2)=K(0)(+)R(2)(+)R(5)、前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する手段、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に前記7個の記憶装置に配布する手段、前記配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、として機能させるためのプログラムである。
【0016】
(作用)
第1〜第4の各発明は、排他的論理和を用いた(2,n)型、(3,5)型、又は(3,7)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0017】
これに加え、第2の発明は、メンバを追加したい場合に、配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、追加人数分のt個の分散情報D(n),…,D(n-1+t)を生成し、この分散情報D(n),…,D(n-1+t)を追加メンバに配布する。
【0018】
これにより、第2の発明は、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上させることができる。
【発明の効果】
【0019】
以上説明したように本発明によれば、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【発明を実施するための最良の形態】
【0020】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の各装置は、各装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【0021】
(第1の実施形態)
図1は本発明の第1の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、1台のクライアント装置10及びn−1台の保管サーバ装置20,30,…,n0が互いにインターネット等のネットワークNWを介して接続されている。
【0022】
これら合計n台の装置10,20,30,…,n0は、(k,n)しきい値秘密分散法におけるn人のメンバに対応する。特に、n台の装置10,20,…,n0が個別に有するn個の保存部11,21,…,n1は、n人のメンバが個別に有するn個の記憶装置に対応する。各装置10,20,30,…,n0には、それぞれ分散情報の配布順番を示すj番号(行番号)が割当てられている。例えば、クライアント装置10には、j=0番目が割り当てられており、保管サーバ装置20にはj=1番目が割り当てられている。保管サーバ装置30にはj=2番目が割り当てられ、…、保管サーバ装置n0にはj=n−1番目が割り当てられている。
【0023】
ここで、クライアント装置10は、秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn台の装置10,20,…,n0に配布し、且つ、n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置を実現するものである。なお、分散情報の個数は2個以上であればよい。例えばn=2とし、秘密情報Sをn−1(=1)個に分割して後述するK(1)とし、配布した2個の分散情報D(0),D(1)から秘密情報Sを復元してもよい。
【0024】
具体的にはクライアント装置10は、保存部11、入力部12、分散部分データ生成部13、ハッシュ値生成部14、元データ復元部15、ハッシュ値検証部16、制御部17、出力部18及び通信部19が互いにバスを介して接続されている。
【0025】
保存部11は、制御部19から読出/書込可能なハードウェア資源としての記憶装置であり、後述する分散情報D(0)〜D(n-1)が配布される前に、秘密情報Sが一時的に記憶され、分散情報D(0)〜D(n-1)が作成されると、分散情報作成情報が記憶され、分散情報が配布された後、j=0番目の分散情報D(0)が記憶されると共に、秘密情報Sが削除される。ここで、分散情報作成情報は、分散情報D(j)の識別情報jと、分散情報D(j)の配布先識別情報(装置ID、装置のアドレス情報等)とが互いに関連付けられた情報である。
【0026】
入力部12は、キーボード又はマウス等の通常の入力デバイスであり、操作者の操作により、分散処理又は復号処理の開始等の命令や、秘密情報S等の情報をクライアント装置10内に入力する機能をもっている。
【0027】
分散部分データ生成部13は、制御部17により制御され、保存部11に一時的に記憶された秘密情報Sに基づいて、図2に一例(n=5の例)を示すように、n(n−1)個の分散部分データD(j,i)を生成する機能をもっている。具体的には、分散部分データ生成部12は、以下の各機能(f12−1)〜(f12−4)をもっている。
【0028】
(f12−1) 保存部11に記憶された秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の分割秘密データK(1),…,K(j),…,K(n-1)を生成する機能。
【0029】
(f12−2) 各分割秘密データのサイズと同一サイズのゼロ値データを作成し、作成結果に行番号j=0を割り当てて分割秘密データK(0)を生成する機能。
【0030】
(f12−3) 各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する機能。なお、各乱数R(i)は、互いに異なる値である。
【0031】
(f12−4) 分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する機能(但し、(+)は排他的論理和を表す記号)。なお、K(j−i(mod n))=K(0)(=0)の場合、必ずしもK(0)の項を計算する必要は無く、例えばK(0)の項の計算無しにD(j,i)=R(i)としてもよい。このように、K(0)(=0)の場合、必ずしもK(0)の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【0032】
ハッシュ値生成部14は、制御部17により制御され、制御部17からバスを介してヘッダ情報H(j)が入力されると、ヘッダ情報H(j)のハッシュ値h(H(j))を生成し、得られたハッシュ値h(H(j))をバスに出力する機能をもっている。なお、ハッシュ値生成部14は、ヘッダ情報H(j)を検証しない場合、省略可能である。
【0033】
元データ復元部15は、制御部17に制御され、n台の装置10,…,n0に配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、秘密情報Sを復元する秘密情報復元機能をもっている。具体的には元データ復元部15は、以下の各機能(f15−1)〜(f15−8)をもっている。
【0034】
(f15−1) 2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する機能。
【0035】
(f15−2) この判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する第1の復元機能(但し、r=j−i(mod n))。なお、K(0)(=0)の項は必ずしも計算する必要が無く、例えばK(0)の項の計算無しにK(r)=D(i,i)(+)D(j,i)としてもよい。
【0036】
(f15−3) この分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する機能。
【0037】
(f15−4) この判定結果が第1終了条件を満たさないとき、分割秘密データK(r)の復元の式をrだけずらすことにより、第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する第2の復元機能(但し、K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),…,K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))。
【0038】
(f15−5) f15−3の判定結果が第1終了条件を満たすとき又はf15−1により分散情報D(i)が分散部分データD(i,i)を含まないとき、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、他の分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する第3の復元機能。なお、K(0)(=0)の項は必ずしも計算する必要が無く、例えばK(0)の項の計算無しにK(−r)=D(i,j)(+)D(j,j)としてもよい。
【0039】
(f15−6) この分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する機能。
【0040】
(f15−7) この判定結果が第2終了条件を満たさないとき、分割秘密データK(−r)の復元の式をrだけずらすことにより、第2終了条件を満たすまで、順次、残りの分割秘密データK(−r−r),…,K(−(n-1)r)を復元する第4の復元機能(但し、K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),…,K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))。
【0041】
(f15−8) 各復元機能のうち、該当する各復元機能により復元されたn−1個の分割秘密データK(1),…,K(n-1)を互いに連接することにより、秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する機能(但し、‖は連接を表す記号)。
【0042】
ハッシュ値検証部16は、制御部17により制御され、制御部17からバスを介してヘッダ情報H(j)及びそのハッシュ値h(H(j))が入力されると、ハッシュ値h(H(j))に基づいてヘッダ情報H(j)を検証し、検証結果をバスに出力する機能をもっている。検証内容は、ヘッダ情報H(j)から計算したハッシュ値と、入力されたハッシュ値h(H(j))との一致により、ヘッダ情報H(j)を正当と判定する方式である。なお、ハッシュ値検証部16は、ヘッダ情報H(j)を検証しない場合、省略可能である。
【0043】
ここで、ヘッダ情報H(j)は、図3の上方に一例を示すように、行番号jを示すデータ識別子、ヘッダのサイズを表すヘッダーサイズ、元データのサイズを表す元データサイズm、元の秘密情報Sの分割数を示す分割数n−1、分散部分データD(i,j)の処理単位ビットを示す処理単位ビット長a、乱数R(i)のデータサイズを示す乱数データサイズa、分割秘密データK(j)のサイズを表す分割データサイズa、パディングの有無やアルゴリズムを表すパディングアルゴリズム、ハッシュアルゴリズム情報(オプション)などが考えられる。ハッシュアルゴリズム情報は、ヘッダ情報のハッシュ値を算出し、ヘッダ情報の原本性を保証する場合などに追加される。すなわち、ハッシュアルゴリズム情報は、セキュリティの要件などに応じて追加又は省略される。但し、セキュリティの要件として予めシステムでハッシュアルゴリズムを決めている場合には、ハッシュアルゴリズム情報は、ヘッダ情報から省略可能である。
【0044】
なお、分散情報D(j)のデータフォーマットは、図3の下方に一例を示すように、ヘッダ情報H(j)、そのハッシュ値h(H(j))、n−1個の分散部分データD(j,0),D(j,1),…,D(j,n-2)から構成されている。ここで、ハッシュ値h(H(j))は、オプション(option)であり、ヘッダ情報H(j)内のハッシュアルゴリズム情報と同様に、セキュリティの要件に応じて省略可能となっている。
【0045】
制御部17は、入力部12から入力される命令に基づいて、後述する図4及び図5のフローチャートに基づいて、各部11,13〜16,18,19を制御する機能をもっている。また、制御部17は、例えば、以下の機能(f17−1)〜(f17−2)をもっている。
【0046】
(f17−1) 分散部分データ生成部13により生成された各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する機能。
【0047】
(f17−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を通信部19を介して個別にn台の装置10,20,…,n0に配布する機能。なお、制御部17は、分散情報D(0)〜D(n-1)の漏洩防止の観点から、分散情報D(0)〜D(n-1)を暗号化した状態で配布してもよい。
【0048】
出力部18は、ディスプレイ装置やプリンタ装置等の通常の出力デバイスであり、制御部18により制御され、命令等の入力画面や、復元後の秘密情報S等の出力画面等を出力する機能をもっている。
【0049】
通信部19は、制御部17により制御され、クライアント装置10とネットワークNWとの間の通信インターフェイス機能をもっている。
【0050】
一方、各保管サーバ装置20〜n0について説明する。
各保管サーバ装置20〜n0は、記憶する分散情報D(1)〜D(n-1)が互いに異なる他は互いに同一構成のため、ここでは保管サーバ装置20を代表例に挙げて説明する。
【0051】
保管サーバ装置20は、保存部21及び通信部22を備えている。
【0052】
保存部21は、通信部22から読出/書込可能なハードウェア資源としての記憶装置であり、クライアント装置10から配布された分散情報D(1)が記憶される。
【0053】
通信部22は、クライアント装置10から配布された分散情報D(1)を保存部21に書き込む機能と、クライアント装置10から要求された分散情報D(1)を保存部21から読み出してこの分散情報D(1)をクライアント装置10に返信する機能とをもっている。
【0054】
なお、通信部22は、分散情報D(1)の漏洩防止の観点から、クライアント装置10の認証機能を有してもよく、この場合、クライアント装置10の認証の後、分散情報D(1)を返信する構成として設けられる。
【0055】
ここで、各保管サーバ装置20,30,…,n0は、他のクライアント装置や、USB(Universal Serial Bus)メモリ、携帯電話、PDA(Personal Digital Assistants:携帯情報端末)に置き換え可能であり、あるいは外付けHDD(Hard Disc Drive: 固定磁気ディスク装置)などのように、コンピュータ以外の他の装置と置き換えることも可能である。
【0056】
なお、各保管装置20,30,…,n0は、他のクライアント装置に置き換えられる場合、前述同様に、分散部分データ生成部13や元データ復元部15などの機能を保持していてもよい。すなわち、秘密情報を復元できる装置は、クライアント装置10以外にあってもよい。例えば、各保管装置20,30,…,n0のうちの任意の台数の装置j0,…が秘密情報を復元できる構成としてもよい。なお、分散の場合も同様に、秘密情報を分散できる装置は、クライアント装置10以外にあってもよい。例えば、各保管装置20,30,…,n0のうちの任意の台数の装置j0,…が分散情報を配布できる構成としてもよい。また、各保管装置20,30,…,n0がUSBメモリや携帯電話などのように物理的な接続手段又は無線通信手段を有する装置に置き換えられる場合、ネットワークNWを省略してもよい。上述した各保管装置20,30,…,n0を他の装置に置き換えた変形例は、以下の各実施形態でも同様に適用可能である。
【0057】
次に、以上のように構成された秘密分散システムの動作を説明する。ここでは(2,n)型のしきい値秘密分散法を例に挙げて述べる。
【0058】
始めに、n人のメンバ(初期メンバ)に、秘密情報Sを(2,n)しきい値秘密分散法で分散した分散情報D(j)を配布する場合を考える。このときnは素数を選ばなければならない。従って、合成数のn人に分散情報を配布したい場合は、n<n’でありかつn’が素数となるようなn’について秘密分散法を適用することになる。以下では(2,n)秘密分散法についての一例を示す。
【0059】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(n-1)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0060】
このとき、クライアント装置10においては、図4に示すように、操作者(以下、ディーラーともいう)の操作により、分散処理の開始命令が入力部12から入力されたとする(ST1)。
【0061】
クライアント装置10は、この開始命令に基づいて、分散処理を開始する。制御部17は、秘密情報Sのビット長をm、分散数をn、処理単位ビットをaと定める(ST1)。なお、秘密情報Sのビット長mは、保存部11内の秘密情報Sから分かる。処理単位ビットaは、分散データ生成部13の仕様により予め定まっている。
【0062】
続いて、制御部17は、ビット長mの秘密情報Sをn−1個に分割した際のビット長(m/(n-1))が処理単位ビットaを超える(m/(n-1)>a)か否かを判定し(ST2)、処理単位ビットaを超える場合、nより大きい素数n’を探索し、得られた素数n’を分散数nと置き換えて(ST3)、ステップST1に戻る。
【0063】
一方、ステップST2の判定の結果が否の場合、制御部17は、秘密情報S及び分散数nを分散部分データ生成部13に入力する。
【0064】
分散部分データ生成部13は、秘密情報S及び分散数nに基づいて、ビット長mの秘密情報Sをn−1個に分割した際のビット長(m/(n-1))が処理単位ビットaと等しいか(m/(n-1)=a)か否かを判定する(ST4)。
【0065】
ステップST4の判定結果が否の場合、分散部分データ生成部13は、秘密情報Sをn−1個の分割秘密データK(0)〜K(n-2)に分割した際の末尾の分割秘密データK(n-2)をパディングする(パディング有)とし(ST5)、ステップST6に進む。
【0066】
なお、パディングは、必ずしも末尾の分割秘密データK(n-2)に行わなくても良く、他の分割秘密データK(j)に行っても良い。但し、本実施形態では、秘密情報Sは4個にちょうど分割できた場合(パディング無し)を例に挙げて述べる。また、図2に示した如き、分散数n=5,しきい値k=2の(2,5)型を例に挙げて述べる。
【0067】
ステップST4の判定の結果、処理単位ビットaと等しい場合、分散部分データ生成部13は、この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の分割秘密データK(1),…,K(j),…,K(n-1)を生成する。(2,5)型の例では、分割秘密データK(1),…,K(4)が生成される。
【0068】
また、分散部分データ生成部13は、各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて分割秘密データK(0)を生成する。
【0069】
さらに、分散部分データ生成部13は、各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する(ST6)。(2,5)型の例では、4個の乱数データR(0),…,R(3)が生成される。
【0070】
次に、分散部分データ生成部13は、分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する(ST7)。この算出は、行番号jを0からn-1まで繰り返すと共に、列番号iを0からn-2まで繰り返すことにより行う。(2,5)型の例では、図2に示したように、20個の分散部分データD(j,i)が生成される。また、K(j−i(mod n))=K(0)(=0)の場合、K(0)の項を計算せずに、D(j,i)=R(i)としてもよい。
【0071】
しかる後、分散部分データ生成部13は、得られた分散部分データn(n−1)個の分散部分データD(j,i)を制御部17に出力する。
【0072】
制御部17は、各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する(ST8)。ヘッダ情報H(j)には、K(n-1)に対するパディングの有無、元データのサイズなどの情報が含まれる。
【0073】
制御部17は、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別にn個の保存部11,21,…,n1に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(n-1)を個別に保管サーバ装置20,…,n0に配布する(ST9)。(2,5)型の例では、5個の分散情報D(0),…,D(4)が配布される。各保管サーバ装置20〜50では、配布された分散情報D(1),…,D(4)を保存部21〜51に記憶する。
【0074】
以上により、秘密情報の分散処理が完了する。
【0075】
なお、(2,5)型において、必ずしも5個の分散情報D(0)〜D(4)を配布する必要は無い。例えば4個の分散情報D(0)〜D(3)を配布しておき、残り1個の分散情報D(4)を新メンバが追加されたときに新メンバに配布してもよい。このことについては、後の第2の実施形態で述べる。
【0076】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0077】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17は、n台の装置10,…,n0に配布したn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)を収集し(ST11)、得られた分散情報D(i),D(j)を元データ復元部15に入力する。
【0078】
元データ復元部15は、分散情報D(i),D(j)を受けると、2つの分散情報D(i),D(j)のヘッダ情報H(i),H(j)から、図6及び図7に示すように、例えば、j=(i=)1番目、j=3番目の分散情報D(i),D(j)であることを解析する(ST12)。例えば分散情報D(1),D(3)であることを確認する。
【0079】
元データ復元部15は、2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する(ST13)。例えば分散情報D(1)に関し、分散部分データD(1,1)を含むかを判定する。
【0080】
ステップST13の判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき(ST13;YES)、元データ復元部15は、ステップST14を実行する。
【0081】
ステップST14においては、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する(但し、r=j−i(mod n))。
【0082】
例えば、分散部分データD(1,1)と、分割秘密データK(0)(=0)との排他的論理和に基づいて、乱数データR(1)を算出する(ST14−1)。なお、K(0)(=0)との排他的論理和を計算せずに、D(1,1)=R(1)としてもよい。続いて、乱数データR(1)と、分散部分データD(3,1)との排他的論理和に基づいて、分割秘密データK(2)を復元する(ST14−2)。
【0083】
また、この分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する。例えばK(2)の復元後、第1終了条件i−r(mod 5)=1−2(mod 5)=4が、n−1=5−1=4を満たすか否かを判定する。この場合は満たす。
【0084】
この判定結果が第1終了条件を満たさないとき、分割秘密データK(r)の復元の式をrだけずらすことにより、第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する。但し、
K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),
…,
K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))。
【0085】
一方、ステップST14中の判定結果が第1終了条件を満たすとき又はステップST13の判定結果が否のとき、元データ復元部15は、ステップST15を実行する。
【0086】
ステップST15においては、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、j=0番目の分割秘密データK(0)(=0)とに基づいて、他の分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する。
【0087】
例えば、分散部分データD(3,3)と、分割秘密データK(0)(=0)との排他的論理和に基づいて、乱数データR(3)を算出する(ST15−1)。なお、K(0)(=0)との排他的論理和を計算せずに、D(3,3)=R(3)としてもよい。続いて、乱数データR(3)と、分散部分データD(1,3)との排他的論理和に基づいて、分割秘密データK(3)を復元する(ST15−2)。
【0088】
また、この分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する。例えばK(3)の復元後、第2終了条件j+r(mod 5)=3+2(mod 5)=5(mod 5)=0が、n−1=4を満たすか否かを判定する。この場合は満たさない。
【0089】
この判定結果が第2終了条件を満たさないとき、分割秘密データK(−r)の復元の式をrだけずらすことにより、第2終了条件を満たすまで、順次、残りの分割秘密データK(−r−r),…,K(−(n-1)r)を復元する。但し、
K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),
…,
K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))。
【0090】
例えば、図6及び図7のステップST15−3からST15−6により、残りの分割秘密データK(1),K(4)を復元する。
【0091】
ステップST15が完了すると、元データ復元部15は、復元されたn−1個の分割秘密データK(1),…,K(n-1)を制御部17に送出する。この例では、4個の分割秘密データK(1),…,K(4)が送出される。
【0092】
制御部17は、分割秘密データK(1),…,K(n-1)に対して、ヘッダ情報H(i),H(j)に基づいて、パディングなどの処理があれば除去する(ST16)。しかる後、制御部17は、分割秘密データK(1),…,K(n-1)を互いに連接することにより、秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する(ST17)。この例では、秘密情報S=K(1)‖K(2)‖…‖K(4)が復元される。
【0093】
上述したように本実施形態によれば、排他的論理和を用いた(2,n)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0094】
補足すると、本実施形態は、特許文献1記載の技術とは異なり、完全秘密分散法を実現しているため、k−1個以下の分散部分データから、元の秘密情報を復元できないだけでなく、秘密情報の部分データも復元できないという効果を得ることができる。
【0095】
これに加え、本実施形態によれば、分散部分データをK(*)+R(*)として、K(0)を擬似的に作ることで全て同じ形式となり、アルゴリズム的に分散部分データを作成することが可能である。これに対し、特許文献1での分散部分データはK(*)+R(*)、K(*)+R(*)+R(*)、R(*)など、分散部分データ毎に部分秘密データと乱数の組み合わせが異なっているため、うまくアルゴリズム的に作成できない。また、特許文献1の分散部分データでは、K(*)+R(*)+R(*)といった分散部分データから復元する際に、計算量がどうしても多くなるため、本実施形態と比べて計算量が増大している。
【0096】
(第2の実施形態)
次に、本発明の第2の実施形態について図1を参照しながら説明する。
本実施形態は、第1の実施形態の変形例であり、(2,n)型のしきい値秘密分散を(2,n’)型のしきい値秘密分散(n<n’)に拡張可能な構成により、新メンバを追加可能とした形態となっている。
【0097】
ここで、nは、第1の実施形態とは異なり、素数に限らない。nが素数でない場合はnよりも大きな素数n’を用いて(2,n’)型の秘密分散法を構築し、そのうちn人に分散情報を配布することで(2,n)型の秘密分散システムを実現する。この場合、n’−n人だけ新メンバの追加が可能である。例えば、(2,5)型の秘密分散法を構築しておき、そのうち4人に分散情報を配布することで(2,4)型の秘密分散システムを実現する。この場合、1人だけ新メンバの追加が可能である。
【0098】
新メンバ用の分散情報は、追加時にクライアント装置10が作成してもよく、あるいは、最も権限があるユーザ、前述したディーラー、又は信頼できる第三者機関(trusted third party)などのクライアント装置又は保管サーバ装置等が作成することが考えられる。これは任意のユーザがメンバーを追加可能なシステムでは、ユーザ全体を管理することが困難なためである。特定のユーザや機関によってのみ追加可能な形態が望まれる。
【0099】
次に、第2の実施形態の具体的な構成を述べる。
【0100】
クライアント装置10は、秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の保存部11,…,n0に配布し、且つ、n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置を実現している。
【0101】
ここで、制御部17は、前述した機能に加え、(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する機能と、判定結果が変更可能条件を満たすとき、任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する機能と、この生成したt個の分散情報D(n),…,D(n-1+t)をn個の保存部11,…,n0とは異なるt個の記憶装置に個別に配布する機能とをもっている。
【0102】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0103】
図8に示すように、複数のメンバーからなるあるグループで、秘密情報Sを(k,n’)しきい値秘密分散法(n<n’、k≦n)を用いて分散し、n’個の分散情報のうち、n個の分散情報をn人のメンバーに配布した状態において、新たにt人の新規メンバーがそのグループに追加される場合を考える(ST21)。
【0104】
例えば、図9に示すように、秘密情報Sを(2,5)しきい値秘密分散法を用いて分散し、n’=5個の分散情報のうち、n=4個の分散情報を4人のメンバーに配布した状態において、新たにt=1人の新規メンバーがそのグループに追加される場合である。
【0105】
まず、分散情報を既に保持しているメンバーの分散情報を用いてディーラーが新規メンバー用の分散情報を作成する場合を考える。
【0106】
このとき、クライアント装置10においては、制御部17が、保存部11内の分散情報作成情報に基づいて、配布済みの分散情報D(j)の個数nを確認し、変更可能条件t≦n’−nを満たすか否かを判定する(ST22)。
【0107】
制御部17は、ステップST22の判定結果が変更可能条件を満たすとき、任意の2個の分散情報D(i),D(j)を収集し(ST23)、この分散情報D(i),D(j)に基づいて、n+1番目の分散部分データD(n,0)〜D(n,n’-2)を生成し、以下同様に、順次、n+t番目の分散部分データD(n-1+t,0)〜D(n-1+t,n’-2)を生成する(ST24)。
【0108】
例えば、制御部17は、図10に示すように、2個の分散情報D(1),D(3)に基づいて、5番目の分散部分データD(4,0)〜D(4,3)を生成する。このとき、分散部分データD(4,0)〜D(4,3)は、次のように算出される。
【0109】
D(4,0)=D(1,0)(+)D(1,2)(+)D(3,2)、
D(4,1)=D(1,1)(+)D(1,3)(+)D(3,3)、
D(4,2)=D(1,0)(+)D(1,1)(+)D(1,3)(+)D(3,0)(+)D(3,1)(+)D(3,2)(+)D(3,3)、
D(4,3)=D(1,0)(+)D(1,3)(+)D(3,0)。
【0110】
制御部17は、各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててt個のヘッダ情報H(n),…,H(n-1+t)を生成する(ST25)。この例では、t=1なので、ヘッダ情報H(4)が生成される。
【0111】
制御部17は、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるt個の分散情報D(n),…,D(n-1+t)を生成する。この例では、t=1個の分散情報D(4)が生成される。また、制御部17は、分散情報作成情報を、t個の分散情報D(n),…,D(n-1+t)の識別情報j(=n,…,n-1+t)を含むように更新する(ST26)。この例では、分散情報作成情報は、識別情報j=4を含むように更新される。
【0112】
しかる後、制御部17は、この生成したt個の分散情報D(n),…,D(n-1+t)をn個の保存部11,…,n0とは異なるt個の記憶装置に個別に配布する(ST27)。この例では、t=1個の分散情報D(4)が1個の記憶装置に配布される。
【0113】
これにより、(2,n)型の秘密分散システムは(2,n+t)型の秘密分散システムに拡張される。この例では、(2,4)型が(2,5)型に拡張される。ここで、t=n’−nの場合、(2,n+t)型は(2,n’)型である。
【0114】
一方、ステップST22の判定結果が変更可能条件を満たさないとき、n’よりも大きな素数n”について(2,n”)型の秘密分散法を適用し、全てのメンバー(n+t人)に分散情報を配布しなおす(ST29)。この場合も(2,n)型が(2,n+t)型に拡張される。
【0115】
上述したように本実施形態によれば、第1の実施形態の効果に加え、(2,n)型の秘密分散法を(2,n+t)型又は(2,n’)型の秘密分散システムに拡張することができる(t≦n’−n、n<n’)。
【0116】
補足すると、メンバを追加したい場合に、配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、追加人数分のt個の分散情報D(n),…,D(n-1+t)を生成し、この分散情報D(n),…,D(n-1+t)を追加メンバに配布している。
【0117】
例えば(2,4)型を(2,5)型に拡張する場合、4番目の分散情報D(4)を新たなメンバーに配布することで、予め配布していた分散情報D(0)〜D(3)を更新することなく、(2,5)型の秘密分散法に拡張可能となっている。
【0118】
この際、追加する分散情報D(n),…は、2個の分散情報から元の秘密情報を復元することなく作成可能となっている。また、データ分割時にn’を大きくとっておくことでメンバーの追加に対応可能である。
【0119】
また、本実施形態によれば、初期に配布した分散情報を更新することなく新たなメンバーを追加することが可能になる。また、ディーラーが既存の分散情報を使って新たに分散情報を作成するので、元の秘密情報をディーラー又はその他のメンバーが保持している必要がなく、セキュリティ上セキュアなシステムを構築することが可能になる。すなわち、本実施形態によれば、メンバを追加したい場合に、分散情報を既存のメンバに配布する必要がなく、また、秘密情報を復元可能な数の分散情報又は秘密情報を1箇所に保存せずに、セキュリティ性を向上させることができる。また、権限を保持している既存のメンバーが協力して新たなメンバーに分散情報を配布することも可能になる。
【0120】
(第3の実施形態)
図11は本発明の第3の実施形態に係る秘密分散システムの構成を示す模式図であり、図1と同一部分には同一符号を付し、ほぼ同一部分にはアルファベットの添字を付してその詳しい説明を省略する。なお、以下の各実施形態も同様にして重複した説明を省略する。
【0121】
本実施形態は、第1の実施形態の変形例であり、(3,5)型の秘密分散システムとなっている。これに伴い、分散部分データ生成部13a、元データ復元部15a及び制御部17aの機能が(3,5)型の秘密分散システムに対応して変更されている。また、保管サーバ装置20,30,40,50の台数は、n−1=4台と定まっている。
【0122】
ここで、分散部分データ生成部13aは、具体的には、以下の機能(f13a−1)〜(f13a−4)をもっている。
【0123】
(f13a−1) 制御部17aから受けた秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する機能。
【0124】
(f13a−2) 各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する機能。
【0125】
(f13a−3) 2個の分割秘密データK(0),K(1)、4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する機能。
【0126】
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(2,0)=R(2)、
D(2,1)=K(0)(+)R(3)(+)R(0)、
D(3,0)=R(3)、
D(3,1)=K(1)(+)R(0)(+)R(1)、
D(4,0)=K(1)(+)R(0)(+)R(2)、
D(4,1)=K(0)(+)R(1)(+)R(3)。
【0127】
(f13a−4) 算出した10個の分散部分データD(j,i)を制御部17aに送出する機能。
【0128】
元データ復元部15aは、配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)が制御部17aから入力されると、この3個の分散情報D(j)に基づいて、秘密情報Sを復元する復元機能をもっている。
【0129】
制御部17aは、入力部12から入力される命令に基づいて、後述する図12及び図14のフローチャートに基づいて、各部11,13a,14,15a,16,18,19を制御する機能をもっている。また、制御部17aは、例えば、以下の機能(17a−1)〜(17a−2)をもっている。
【0130】
(17a−1) 各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する機能。
【0131】
(17a−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に5個の保存部11〜51に配布する機能。
【0132】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0133】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(4)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0134】
このとき、クライアント装置10においては、操作者の操作により、分散処理の開始命令が入力部12から入力されると、分散処理を開始する。
【0135】
制御部17aは、保存部11内の秘密情報Sを分散部分データ生成部13aに入力する。
【0136】
分散部分データ生成部13aは、図12に示すように、秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する(ST31)。
【0137】
ここで、2個の分割秘密データK(0),K(1)は、互いに同一サイズでなければいけない。このため、秘密情報Sが奇数ビットのサイズの場合、2の倍数のビット(桁)で表現されるように、末尾に0が付加(パディング)される。その後、パディング済みの秘密情報Sを同じデータサイズになるように2個に分ける。データサイズはビット単位で扱う。2の倍数のビットとは、例えば10100110のように表現される。
【0138】
次に、分散部分データ生成部13aは、分割秘密データK(0)、K(1)と同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する(ST32)。
【0139】
分散部分データ生成部13aは、2個の分割秘密データK(0),K(1)、4個の乱数データR(0)〜R(3)に基づいて、図13に示すように、10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する。
【0140】
しかる後、分散部分データ生成部13aは、これら分散部分データを制御部17aに送出する。
【0141】
制御部17aは、各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する(ST33)。
【0142】
次に、制御部17aは、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を生成する。例えば、分散情報D(0)は、ヘッダ情報H(j)と、分散部分データD(0,0)と、分散部分データD(0,1)とをビット列単位で結合したものである。
【0143】
しかる後、制御部17aは、5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に5個の保存部11〜51に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(4)を個別に保管サーバ装置20,…,50に配布する(ST34)。各保管サーバ装置20〜50では、配布された分散情報D(1),…,D(4)を保存部21〜51に記憶する。
【0144】
以上により、秘密情報の分散処理が完了する。
【0145】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0146】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17aは、図14に示すように、5台の装置10,…,50に配布した5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報を収集し(ST35)、得られた分散情報を元データ復元部15aに入力する。この例では、5個の分散情報のうち、D(0)、D(2)、D(4)を用いることとする。
【0147】
元データ復元部15aは、分散情報D(0)、D(2)、D(4)を受けると、分散情報のヘッダ情報H(0),H(2),H(4)を参照し、分散情報D(j)毎に、分散部分データD(j,0),D(j,1)を確認する(ST36)。
【0148】
元データ復元部15aは、分散情報D(j)毎の分散部分データD(j,0),D(j,1)に基づいて、2個の分割秘密データK(0),K(1)を算出する(ST37)。
【0149】
例えば、図15に示すように、分散部分データD(0,0)、D(2,0)とD(4,0)との排他的論理和により、分割秘密データK(1)を算出する(ST37−1)。
【0150】
分散部分データD(0,0)とD(2,1)との排他的論理和により、中間データK(0)(+) R(3)を算出する(ST37−2)。
【0151】
分散部分データD(2,0)とD(0,1)との排他的論理和により、中間データK(0)(+) R(1)を算出する(ST37−3)。
【0152】
中間データK(0)(+) R(3)とK(0)(+) R(1)との排他的論理和により、中間データR(1)(+) R(3)を算出する(ST37−4)。
【0153】
中間データR(1)(+) R(3)と、分散部分データD(4,1)とにより、分割秘密データK(0)を算出する(ST37−5)。
【0154】
元データ復元部15aは、これら分割秘密データK(0),K(1)とヘッダ情報H(0),H(2),H(4)に基づいて、元の秘密情報S=K(0)‖K(1)を復元する(ST38)。
【0155】
上述したように本実施形態によれば、排他的論理和を用いた(3,5)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0156】
(第4の実施形態)
図16は本発明の第4の実施形態に係る秘密分散システムの構成を示す模式図である。
【0157】
本実施形態は、第1の実施形態の変形例であり、(3,7)型の秘密分散システムとなっている。これに伴い、分散部分データ生成部13b、元データ復元部15b及び制御部17bの機能が(3,7)型の秘密分散システムに対応して変更されている。また、保管サーバ装置20,30,40,50,60,70の台数は、n−1=6台と定まっている。
【0158】
ここで、分散部分データ生成部13bは、具体的には、以下の機能(f13b−1)〜(f13b−4)をもっている。
【0159】
(f13b−1) 制御部17bから受けた秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(1)を生成する機能。
【0160】
(f13b−2) 各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する機能。
【0161】
(f13b−3) 3個の分割秘密データK(0)〜K(2)、6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する機能。
【0162】
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(0,2)=K(2)(+)R(3)(+)R(5)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(1,2)=K(0)(+)R(0)(+)R(4)、
D(2,0)=R(2)、
D(2,1)=K(2)(+)R(3)(+)R(4)、
D(2,2)=K(1)(+)R(1)(+)R(5)、
D(3,0)=R(3)、
D(3,1)=K(0)(+)R(4)(+)R(5)、
D(3,2)=K(2)(+)R(0)(+)R(2)、
D(4,0)=R(4)、
D(4,1)=K(1)(+)R(5)(+)R(0)、
D(4,2)=K(0)(+)R(1)(+)R(3)、
D(5,0)=R(5)、
D(5,1)=K(2)(+)R(0)(+)R(1)、
D(5,2)=K(1)(+)R(2)(+)R(4)、
D(6,0)=K(1)(+)R(0)(+)R(3)、
D(6,1)=K(2)(+)R(1)(+)R(4)、
D(6,2)=K(0)(+)R(2)(+)R(5)。
【0163】
(f13b−4) 算出した21個の分散部分データD(j,i)を制御部17bに送出する機能。
【0164】
元データ復元部15bは、配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)が制御部17aから入力されると、この3個の分散情報D(j)に基づいて、秘密情報Sを復元する復元機能をもっている。
【0165】
制御部17bは、入力部12から入力される命令に基づいて、後述する図17及び図19のフローチャートに基づいて、各部11,13b,14,15b,16,18,19を制御する機能をもっている。また、制御部17bは、例えば、以下の機能(17b−1)〜(17b−2)をもっている。
【0166】
(17b−1) 各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する機能。
【0167】
(17b−2) 互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に7個の保存部11〜71に配布する機能。
【0168】
次に、以上のように構成された秘密分散システムの動作を説明する。
【0169】
(分散処理の動作)
クライアント装置10においては、分散情報D(0)〜D(6)を配布する前に、ビット長mの秘密情報Sが一時的に保存部11に記憶されているとする。
【0170】
このとき、クライアント装置10においては、操作者の操作により、分散処理の開始命令が入力部12から入力されると、分散処理を開始する。
【0171】
制御部17bは、保存部11内の秘密情報Sを分散部分データ生成部13bに入力する。
【0172】
分散部分データ生成部13bは、図17に示すように、秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する(ST41)。
【0173】
ここで、3個の分割秘密データK(0),K(1),K(2)は、互いに同一サイズでなければいけない。このため、秘密情報Sが3の倍数のビット(桁)で表現されるように、末尾に0が付加(パディング)される。その後、パディング済みの秘密情報Sを同じデータサイズになるように3個に分ける。データサイズはビット単位で扱う。3の倍数のビットとは、例えば101001100のように表現される。
【0174】
次に、分散部分データ生成部13bは、分割秘密データK(0),K(1),K(2)と同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),…,R(5)を生成する(ST42)。
【0175】
分散部分データ生成部13bは、3個の分割秘密データK(0)〜K(2)、6個の乱数データR(0)〜R(5)に基づいて、図18に示すように、21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する。
【0176】
しかる後、分散部分データ生成部13bは、これら分散部分データを制御部17bに送出する。
【0177】
制御部17bは、各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),…,H(6)を生成する(ST43)。
【0178】
次に、制御部17bは、互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),…,D(6)を生成する。例えば、分散情報D(0)は、ヘッダ情報H(j)、分散部分データD(0,0),D(0,1),D(0,2)を互いにビット列単位で結合したものである。
【0179】
しかる後、制御部17bは、7個の分散情報D(0),…,D(6)を個別に7個の保存部11〜71に配布するように、分散情報D(0)を保存部11に書き込み、分散情報D(1),…,D(6)を個別に保管サーバ装置20,…,70に配布する(ST44)。各保管サーバ装置20〜70では、配布された分散情報D(1),…,D(6)を保存部21〜71に記憶する。
【0180】
以上により、秘密情報の分散処理が完了する。
【0181】
(復元処理の動作)
クライアント装置10においては、操作者の操作により、復元処理の開始命令が入力部12から入力されたとする。
【0182】
クライアント装置10は、この開始命令に基づいて、復元処理を開始する。制御部17bは、図19に示すように、5台の装置10,…,70に配布した7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報を収集し(ST45)、得られた分散情報を元データ復元部15bに入力する。この例では、7個の分散情報のうち、D(0)、D(2)、D(6)を用いることとする。
【0183】
元データ復元部15bは、分散情報D(0)、D(2)、D(6)を受けると、分散情報のヘッダ情報H(0),H(2),H(6)を参照し、分散情報D(j)毎に、分散部分データD(j,0),D(j,1),D(j,2)を確認する(ST46)。
【0184】
元データ復元部15bは、分散情報D(j)毎の分散部分データD(j,0),D(j,1),D(j,2)に基づいて、3個の分割秘密データK(0),K(1),K(2)を算出する(ST47)。
【0185】
例えば、図20に示すように、分散部分データD(0,1)とD(6,2)との排他的論理和により、中間データR(1)(+) R(5)を算出する(ST47−1)。
【0186】
中間データR(1)+R(5)と、分散部分データD(2,2)との排他的論理和により、分割秘密データK(1)を算出する(ST47−2)。
【0187】
分割秘密データK(1)と、分散部分データD(6,0)とD(0、0)との排他的論理和により、乱数データR(3)を算出する(ST47−3)。
【0188】
分散部分データD(2,1)とD(6,1)との排他的論理和により、中間データR(1)(+) R(3)を算出する(ST47−4)。
【0189】
中間データR(1)(+) R(3)と、乱数データR(3)との排他的論理和により、乱数データR(1)を算出する(ST47−5)。
【0190】
乱数データR(1)とR(2)と、分散部分データD(0,1)との排他的論理和により、分割秘密データK(0)を算出する(ST47−6)。
【0191】
中間データR(1)(+) R(5)と、乱数データR(1)との排他的論理和により、乱数データR(5)を算出する(ST47−7)。
【0192】
分散部分データD(0,2)と、乱数データR(3)とR(5)との排他的論理和により、分割秘密データK(2)を算出する(ST57−8)。
【0193】
元データ復元部15bは、これら分割秘密データK(0)〜K(2)とヘッダ情報H(0),H(2),H(6)に基づいて、元の秘密情報S=K(0)‖K(1)‖K(2)を復元する(ST48)。
【0194】
上述したように本実施形態によれば、排他的論理和を用いた(3,7)型のしきい値秘密分散により、秘密情報の分散や復元の処理を非常に高速に実現し、多項式補間を用いずに高速に実行可能な完全秘密分散を実現することができる。
【0195】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク(フロッピー(登録商標)ディスク、ハードディスクなど)、光ディスク(CD−ROM、DVDなど)、光磁気ディスク(MO)、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【0196】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【0197】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているOS(オペレーティングシステム)や、データベース管理ソフト、ネットワークソフト等のMW(ミドルウェア)等が上記実施形態を実現するための各処理の一部を実行しても良い。
【0198】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、LANやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【0199】
また、記憶媒体は1つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【0200】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の1つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【0201】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【0202】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【0203】
【図1】本発明の第1の実施形態に係る秘密分散システムの構成を示す模式図である。
【図2】同実施形態における分散部分データの一例を示す模式図である。
【図3】同実施形態におけるヘッダ情報及び分散情報の一例を示す模式図である。
【図4】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図5】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図6】同実施形態における復元処理の動作を説明するための模式図である。
【図7】同実施形態における復元処理の動作を説明するための参考図である。
【図8】本発明の第2の実施形態に係る秘密分散システムの動作を説明するためのフローチャートである。
【図9】同実施形態における分散部分データの一例を示す模式図である。
【図10】同実施形態における復元処理の動作を説明するための参考図である。
【図11】本発明の第3の実施形態に係る秘密分散システムの構成を示す模式図である。
【図12】同実施形態における分割処理の動作を説明するためのフローチャートである。
【図13】同実施形態における分散部分データの一例を示す模式図である。
【図14】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図15】同実施形態における復元処理の動作を説明するための模式図である。
【図16】本発明の第4の実施形態に係る秘密分散システムの構成を示す模式図である。
【図17】同実施形態における分割処理の動作を説明するためのフローチャートである。
【図18】同実施形態における分散部分データの一例を示す模式図である。
【図19】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図20】同実施形態における復元処理の動作を説明するための模式図である。
【符号の説明】
【0204】
10…クライアント装置、11〜n1…保存部、12…入力部、13,13a,13b…分散部分データ生成部、14…ハッシュ値生成部、15,15a,15b…元データ復元部、16…ハッシュ値検証部、17,17a,17b…制御部、18…出力部、19,22〜n2…通信部、20,30,…,n0…保管サーバ装置、NW…ネットワーク。
【特許請求の範囲】
【請求項1】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置であって、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段と、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する手段と、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段と、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)と、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段と、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段と、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元手段と、
を備えたことを特徴とする秘密分散装置。
【請求項2】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置により実行される秘密分散方法であって、
前記分散情報D(0)〜D(n-1)を配布する前に、前記秘密情報Sを、前記秘密分散装置が有する記憶装置に一時的に記憶する記憶工程と、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する工程と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する工程と、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する工程と、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する工程(但し、(+)は排他的論理和を表す記号)と、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する工程と、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する工程と、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元工程と、
を備えたことを特徴とする秘密分散方法。
【請求項3】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、
として機能させるためのプログラム。
【請求項4】
請求項3に記載のプログラムにおいて、
前記秘密情報復元手段は、
前記2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する手段、
この判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、第2分割秘密データK(0)(=0)とに基づいて、第1分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する第1の復元手段(但し、r=j−i(mod n))、
この第1分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する手段、
この判定結果が第1終了条件を満たさないとき、前記第1分割秘密データK(r)の復元の式をrだけずらすことにより、前記第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する第2の復元手段(但し、K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),…,K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))、
前記判定結果が第1終了条件を満たすとき又は前記分散情報D(i)が分散部分データD(i,i)を含まないとき、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、前記第2分割秘密データK(0)(=0)とに基づいて、他の第1分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する第3の復元手段、
この第1分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する手段、
この判定結果が第2終了条件を満たさないとき、前記第1分割秘密データK(−r)の復元の式をrだけずらすことにより、前記第2終了条件を満たすまで、順次、残りの第1分割秘密データK(−r−r),…,K(−(n-1)r)を復元する第4の復元手段(但し、K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),…,K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))、
前記各復元手段のうち、該当する各復元手段により復元されたn−1個の第1分割秘密データK(1),…,K(n-1)を互いに連接することにより、前記秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する手段(但し、‖は連接を表す記号)、
を含んでいることを特徴とするプログラム。
【請求項5】
秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sをn’−1個に分割すると共に、分割結果に1からn’−1までの行番号j(但し、0≦j≦n’−1)を割り当てることにより、互いに同一サイズのn’−1個の第1分割秘密データK(1),…,K(j),…,K(n’-1)を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、
前記各分割秘密データのサイズ以上のサイズを有するn’−1個の乱数を生成すると共に、各生成結果に0からn’−2までの列番号i(但し、0≦i≦n’−2)を割り当ててn’−1個の乱数データR(0),…,R(i),…,R(n’-2)を生成する手段、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n’-1)及び前記乱数データR(0),…,R(i),…,R(n’-2)に基づいて、n(n’−1)個の分散部分データD(j,i)=K(j−i(mod n’))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、
前記各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、
前記(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する手段、
前記判定結果が変更可能条件を満たすとき、前記任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する分散情報生成手段、
この生成したt個の分散情報D(n),…,D(n-1+t)を前記n個の記憶装置とは異なるt個の記憶装置に個別に配布する手段、
として機能させるためのプログラム。
【請求項6】
秘密情報Sが分散されてなる5個の分散情報D(0),…,D(4)を個別に5個の記憶装置に配布し、且つ、前記5個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,5)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(4)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する手段、
前記各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する手段、
前記2個の分割秘密データK(0),K(1)、前記4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する手段、
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(2,0)=R(2)、
D(2,1)=K(0)(+)R(3)(+)R(0)、
D(3,0)=R(3)、
D(3,1)=K(1)(+)R(0)(+)R(1)、
D(4,0)=K(1)(+)R(0)(+)R(2)、
D(4,1)=K(0)(+)R(1)(+)R(3)、
前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に前記5個の記憶装置に配布する手段、
前記配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、
として機能させるためのプログラム。
【請求項7】
秘密情報Sが分散されてなる7個の分散情報D(0),…,D(6)を個別に7個の記憶装置に配布し、且つ、前記7個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,7)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(6)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する手段、
前記各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する手段、
前記3個の分割秘密データK(0)〜K(2)、前記6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する手段、
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(0,2)=K(2)(+)R(3)(+)R(5)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(1,2)=K(0)(+)R(0)(+)R(4)、
D(2,0)=R(2)、
D(2,1)=K(2)(+)R(3)(+)R(4)、
D(2,2)=K(1)(+)R(1)(+)R(5)、
D(3,0)=R(3)、
D(3,1)=K(0)(+)R(4)(+)R(5)、
D(3,2)=K(2)(+)R(0)(+)R(2)、
D(4,0)=R(4)、
D(4,1)=K(1)(+)R(5)(+)R(0)、
D(4,2)=K(0)(+)R(1)(+)R(3)、
D(5,0)=R(5)、
D(5,1)=K(2)(+)R(0)(+)R(1)、
D(5,2)=K(1)(+)R(2)(+)R(4)、
D(6,0)=K(1)(+)R(0)(+)R(3)、
D(6,1)=K(2)(+)R(1)(+)R(4)、
D(6,2)=K(0)(+)R(2)(+)R(5)、
前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に前記7個の記憶装置に配布する手段、
前記配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、
として機能させるためのプログラム。
【請求項1】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置であって、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段と、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する手段と、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段と、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)と、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段と、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段と、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元手段と、
を備えたことを特徴とする秘密分散装置。
【請求項2】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置により実行される秘密分散方法であって、
前記分散情報D(0)〜D(n-1)を配布する前に、前記秘密情報Sを、前記秘密分散装置が有する記憶装置に一時的に記憶する記憶工程と、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する工程と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)を生成する工程と、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する工程と、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する工程(但し、(+)は排他的論理和を表す記号)と、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する工程と、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する工程と、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する復元工程と、
を備えたことを特徴とする秘密分散方法。
【請求項3】
秘密情報Sが分散されてなるn個(但し、n≧2)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sをn−1個に分割すると共に、分割結果に1からn−1までの行番号j(但し、0≦j≦n−1)を割り当てることにより、互いに同一サイズのn−1個の第1分割秘密データK(1),…,K(j),…,K(n-1)を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、
前記各分割秘密データのサイズ以上のサイズを有するn−1個の乱数を生成すると共に、各生成結果に0からn−2までの列番号i(但し、0≦i≦n−2)を割り当ててn−1個の乱数データR(0),…,R(i),…,R(n-2)を生成する手段、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n-1)及び前記乱数データR(0),…,R(i),…,R(n-2)に基づいて、n(n−1)個の分散部分データD(j,i)=K(j−i(mod n))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、
前記各分散部分データのうち、同一の行番号jを有するn−1個の分散部分データD(j,0)〜D(j,n-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、
として機能させるためのプログラム。
【請求項4】
請求項3に記載のプログラムにおいて、
前記秘密情報復元手段は、
前記2個の分散情報D(i),D(j)のうち、一方の分散情報D(i)に関し、行番号iと同一の列番号iが割り当てられた分散部分データD(i,i)を含むか否かを判定する手段、
この判定の結果、分散情報D(i)が分散部分データD(i,i)を含むとき、この分散部分データD(i,i)と、他方の分散情報D(j)に含まれる同一列番号iの分散部分データD(j,i)と、第2分割秘密データK(0)(=0)とに基づいて、第1分割秘密データK(r)=D(i,i)(+)D(j,i)(+)K(0)を復元する第1の復元手段(但し、r=j−i(mod n))、
この第1分割秘密データK(r)の復元後、第1終了条件i−r=n−1を満たすか否かを判定する手段、
この判定結果が第1終了条件を満たさないとき、前記第1分割秘密データK(r)の復元の式をrだけずらすことにより、前記第1終了条件を満たすまで、順次、他の第1分割秘密データK(r+r),…,K((n-1)r)を復元する第2の復元手段(但し、K(r+r)=D(i,i−r)(+)D(j,i−r)(+)K(r),…,K((n-1)r)=D(i,i−(n-2)r)(+)D(j,i−(n-2)r)(+)K((n-2)r))、
前記判定結果が第1終了条件を満たすとき又は前記分散情報D(i)が分散部分データD(i,i)を含まないとき、他方の分散情報D(j)における行番号jと同一の列番号jが割り当てられた分散部分データD(j,j)と、一方の分散情報D(i)に含まれる同一列番号jの分散部分データD(i,j)と、前記第2分割秘密データK(0)(=0)とに基づいて、他の第1分割秘密データK(−r)=D(i,j)(+)D(j,j)(+)K(0)を復元する第3の復元手段、
この第1分割秘密データK(−r)の復元後、第2終了条件j+r=n−1を満たすか否かを判定する手段、
この判定結果が第2終了条件を満たさないとき、前記第1分割秘密データK(−r)の復元の式をrだけずらすことにより、前記第2終了条件を満たすまで、順次、残りの第1分割秘密データK(−r−r),…,K(−(n-1)r)を復元する第4の復元手段(但し、K(−r−r)=D(i,j+r)(+)D(j,j+r)(+)K(−r),…,K(−(n-1)r)=D(i,j+(n-2)r)(+)D(j,j+(n-2)r)(+)K(−(n-2)r))、
前記各復元手段のうち、該当する各復元手段により復元されたn−1個の第1分割秘密データK(1),…,K(n-1)を互いに連接することにより、前記秘密情報S=K(1)‖K(2)‖…‖K(n-1)を復元する手段(但し、‖は連接を表す記号)、
を含んでいることを特徴とするプログラム。
【請求項5】
秘密情報Sが分散されてなるn’個(但し、n’≧3)の分散情報D(0),…,D(n’-1)のうち、n個(但し、n<n’)の分散情報D(0),…,D(n-1)を個別にn個の記憶装置に配布し、且つ、前記n個の分散情報のうち、任意の2個の分散情報から秘密情報Sを復元可能な(2,n)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(n-1)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sをn’−1個に分割すると共に、分割結果に1からn’−1までの行番号j(但し、0≦j≦n’−1)を割り当てることにより、互いに同一サイズのn’−1個の第1分割秘密データK(1),…,K(j),…,K(n’-1)を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号j=0を割り当てて第2分割秘密データK(0)(=0)を生成する手段、
前記各分割秘密データのサイズ以上のサイズを有するn’−1個の乱数を生成すると共に、各生成結果に0からn’−2までの列番号i(但し、0≦i≦n’−2)を割り当ててn’−1個の乱数データR(0),…,R(i),…,R(n’-2)を生成する手段、
前記第1及び第2分割秘密データK(0),K(1),…,K(j),…,K(n’-1)及び前記乱数データR(0),…,R(i),…,R(n’-2)に基づいて、n(n’−1)個の分散部分データD(j,i)=K(j−i(mod n’))(+)R(i)を算出する手段(但し、(+)は排他的論理和を表す記号)、
前記各分散部分データのうち、同一の行番号jを有するn’−1個の分散部分データD(j,0)〜D(j,n’-2)毎に、行番号jを割り当ててn個のヘッダ情報H(0),…,H(j),…,H(n-1)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0)〜D(j,n’-2)からなるn個の分散情報D(0),…,D(j),…,D(n-1)を個別に前記n個の記憶装置に配布する手段、
前記配布されたn個の分散情報D(0)〜D(n-1)のうち、任意の2個の分散情報D(i),D(j)に基づいて、前記秘密情報Sを復元する秘密情報復元手段、
前記(2,n)型を(2,n+t)型に変更したいとき、変更可能条件t≦n’−nを満たすか否かを判定する手段、
前記判定結果が変更可能条件を満たすとき、前記任意の2個の分散情報D(i),D(j)に基づいて、t個の分散情報D(n),…,D(n-1+t)を生成する分散情報生成手段、
この生成したt個の分散情報D(n),…,D(n-1+t)を前記n個の記憶装置とは異なるt個の記憶装置に個別に配布する手段、
として機能させるためのプログラム。
【請求項6】
秘密情報Sが分散されてなる5個の分散情報D(0),…,D(4)を個別に5個の記憶装置に配布し、且つ、前記5個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,5)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(4)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sを2個に分割すると共に、分割結果に0から1までの識別番号を割り当てることにより、互いに同一サイズの2個の分割秘密データK(0),K(1)を生成する手段、
前記各分割秘密データのサイズと同一サイズを有する4個の乱数を生成すると共に、各生成結果に0から3までの識別番号を割り当てて4個の乱数データR(0),R(1),R(2),R(3)を生成する手段、
前記2個の分割秘密データK(0),K(1)、前記4個の乱数データR(0)〜R(3)及び下記10個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な10個の分散部分データD(0,0),D(0,1),D(1,0),D(1,1),D(2,0),D(2,1),D(3,0),D(3,1),D(4,0),D(4,1)を算出する手段、
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(2,0)=R(2)、
D(2,1)=K(0)(+)R(3)(+)R(0)、
D(3,0)=R(3)、
D(3,1)=K(1)(+)R(0)(+)R(1)、
D(4,0)=K(1)(+)R(0)(+)R(2)、
D(4,1)=K(0)(+)R(1)(+)R(3)、
前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する2個の分散部分データD(j,0),D(j,1)毎に、行番号jを割り当てて、5個のヘッダ情報H(0),H(1),H(2),H(3),H(4)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1)からなる5個の分散情報D(0),D(1),D(2),D(3),D(4)を個別に前記5個の記憶装置に配布する手段、
前記配布された5個の分散情報D(0)〜D(4)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、
として機能させるためのプログラム。
【請求項7】
秘密情報Sが分散されてなる7個の分散情報D(0),…,D(6)を個別に7個の記憶装置に配布し、且つ、前記7個の分散情報のうち、任意の3個の分散情報から秘密情報Sを復元可能な(3,7)型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報D(0)〜D(6)が配布される前に、前記秘密情報Sが一時的に記憶される記憶手段、
この秘密情報Sを3個に分割すると共に、分割結果に0から2までの識別番号を割り当てることにより、互いに同一サイズの3個の分割秘密データK(0),K(1),K(2)を生成する手段、
前記各分割秘密データのサイズと同一サイズを有する6個の乱数を生成すると共に、各生成結果に0から5までの識別番号を割り当てて6個の乱数データR(0),R(1),R(2),R(3),R(4),R(5)を生成する手段、
前記3個の分割秘密データK(0)〜K(2)、前記6個の乱数データR(0)〜R(5)及び下記21個の式に基づいて(但し、(+)は排他的論理和を表す記号)、互いに2つの識別番号の組合せで識別可能な21個の分散部分データD(0,0),D(0,1),D(0,2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2),D(3,0),D(3,1),D(3,2),D(4,0),D(4,1)D(4,2),D(5,0),D(5,1),D(5,2),D(6,0),D(6,1),D(6,2)を算出する手段、
D(0,0)=R(0)、
D(0,1)=K(0)(+)R(1)(+)R(2)、
D(0,2)=K(2)(+)R(3)(+)R(5)、
D(1,0)=R(1)、
D(1,1)=K(1)(+)R(2)(+)R(3)、
D(1,2)=K(0)(+)R(0)(+)R(4)、
D(2,0)=R(2)、
D(2,1)=K(2)(+)R(3)(+)R(4)、
D(2,2)=K(1)(+)R(1)(+)R(5)、
D(3,0)=R(3)、
D(3,1)=K(0)(+)R(4)(+)R(5)、
D(3,2)=K(2)(+)R(0)(+)R(2)、
D(4,0)=R(4)、
D(4,1)=K(1)(+)R(5)(+)R(0)、
D(4,2)=K(0)(+)R(1)(+)R(3)、
D(5,0)=R(5)、
D(5,1)=K(2)(+)R(0)(+)R(1)、
D(5,2)=K(1)(+)R(2)(+)R(4)、
D(6,0)=K(1)(+)R(0)(+)R(3)、
D(6,1)=K(2)(+)R(1)(+)R(4)、
D(6,2)=K(0)(+)R(2)(+)R(5)、
前記各分散部分データの2つの識別番号を行番号j,列番号iとし、各分散部分データをD(j,i)と表すとき、同一の行番号jを有する3個の分散部分データD(j,0),D(j,1),D(j,2)毎に、行番号jを割り当てて、7個のヘッダ情報H(0),H(1),H(2),H(3),H(4),H(5),H(6)を生成する手段、
互いに同一の行番号jを有するヘッダ情報H(j)及び分散部分データD(j,0),D(j,1),D(j,2)からなる7個の分散情報D(0),D(1),D(2),D(3),D(4),D(5),D(6)を個別に前記7個の記憶装置に配布する手段、
前記配布された7個の分散情報D(0)〜D(6)のうち、任意の3個の分散情報D(j)に基づいて、前記秘密情報Sを復元する復元手段、
として機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【公開番号】特開2007−124032(P2007−124032A)
【公開日】平成19年5月17日(2007.5.17)
【国際特許分類】
【出願番号】特願2005−310056(P2005−310056)
【出願日】平成17年10月25日(2005.10.25)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
【Fターム(参考)】
【公開日】平成19年5月17日(2007.5.17)
【国際特許分類】
【出願日】平成17年10月25日(2005.10.25)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
【Fターム(参考)】
[ Back to top ]