分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラム
【課題】高速な処理で、分散情報に階層的な重み付けを行う。
【解決手段】秘密情報を入力し、分割して部分秘密情報を生成する分割器と、オールゼロからなるダミー情報を生成するダミー情報生成器と、乱数を生成する乱数生成器と、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、決定されたペアについて、排他的論理和演算を行い、レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、出力された部分分散情報を連結し、分散情報を出力する連結器と、出力された分散情報を管理者に送信する送信手段とを備える。
【解決手段】秘密情報を入力し、分割して部分秘密情報を生成する分割器と、オールゼロからなるダミー情報を生成するダミー情報生成器と、乱数を生成する乱数生成器と、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、決定されたペアについて、排他的論理和演算を行い、レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、出力された部分分散情報を連結し、分散情報を出力する連結器と、出力された分散情報を管理者に送信する送信手段とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値秘密分散法により、分散情報に階層的な重み付けを行う分散情報生成装置、分散情報生成方法、秘密情報復元装置、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。
【０００４】
これに対して、ＸＯＲを用いて、（ｋ，ｎ）閾値秘密分散法を構築することにより、高速に情報の分散および復元を可能とする方式が開示されている（例えば、非特許文献２および３参照。）。この非特許文献２および３で開示された方法は、その構造において等価なものであり、単純に高速動作を行うだけでなく、非特許文献１と同様に、完全な情報論理的安全性が保証されており、分散情報のデータ長が秘密情報のデータ長と等しいという特徴を有している。
【０００５】
また、非特許文献３に記載の方法はｋ個の分散情報から秘密情報を復元する際に、秘密情報のみならず分散情報を構成する乱数も復元可能であるという特徴があり、非特許文献２に記載の方法は、ｋが３以上の場合には、秘密情報は復元されるが、乱数に関しては、復元不可能という特徴がある。
【０００６】
ところで、非特許文献１、非特許文献２、非特許文献３では、いずれも全ての分散情報は平等に扱われるため、分散情報の重み付けを行うことは出来ない。
【０００７】
そのため、非特許文献１をベースとし、分散情報に重み付けを行う方式として、非特許文献４、非特許文献５、特許文献１に記載された手法が知られている。例えば、特許文献１に記載の手法では、分散情報をさらに何度も秘密分散法によって分散し、分散情報の木構造を構成することで階層型の重み付けを実現する。また、非特許文献４、非特許文献５の手法は、非特許文献１の分散情報を構成するためのｋ−１次の多項式を重みに応じて微分し、その結果の新たな多項式を用いて分散情報を生成することで、階層型の重み付けを実現している。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ， ｖｏｌ．２２ ｎｏ．１１ ｐｐ．６１２−６１３， １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ Ｆａｓｔ （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ Ｕｓｉｎｇ Ｅｘｃｌｕｓｉｖｅ−ＯＲ Ｏｐｅｒａｔｉｏｎ ａｎｄ ｉｔｓ Ｅｘｔｅｎｓｉｏｎ ｔｏ （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【非特許文献４】Ｔ. Ｔａｓｓａ, ‘‘Ｈｉｅｒａｒｃｈｉｃａｌ ｔｈｒｅｓｈｏｌｄ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ,’‘Ｐｒｏｃ. ＴＣＣ２００４, ＬＮＣＳ ２９５１, ｐｐ.４７３−４９０, Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ, ２００４.
【非特許文献５】Ｍ. Ｂｅｌｅｎｋｉｙ, ‘‘ＤｉｓｊｕｎｃｔｉｖｅＭｕｌｔｉ−Ｌｅｖｅｌ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ,’‘ Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ,ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００８／０１８、２００８.
【特許文献１】特開平１０−１９８２７２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に記載された手法何度も低速な非特許文献１の分散処理・復元処理を実行する必要があり、そのコストは非常に大きいという問題がある。また、非特許文献４、非特許文献５に記載された手法方式も同様に、非特許文献１をベースとしているため、分散処理・復元処理のコストが大きいという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、高速な処理で、分散情報に階層的な重み付けを行う分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１１】
（１）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置であって、秘密情報を入力し、これを分割して部分秘密情報を生成する分割器と、オールゼロからなるダミー情報を生成するダミー情報生成器と、乱数を生成する乱数生成器と、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、素数と巡回群との性質を用いて、該ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、該レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、前記レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、該出力された部分分散情報を連結し、分散情報を出力する連結器と、該出力された分散情報を管理者に送信する送信手段と、を備えたことを特徴とする分散情報生成装置を提案している。
【００１２】
この発明によれば、分割器は、秘密情報を入力し、これを分割して部分秘密情報を生成する。ダミー情報生成器は、オールゼロからなるダミー情報を生成する。乱数生成器は、乱数を生成する。第１の排他的論理和演算器は、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う。第２の排他的論理和演算器は、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う。レベル割り当て手段は、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定する。第３の排他的論理和演算器は、レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、レベルに応じた重み付けがされた部分分散情報を出力する。そして、連結器は、出力された部分分散情報を連結し、分散情報を出力し、送信手段は、出力された分散情報を管理者に送信する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。
【００１３】
（２）本発明は、（１）の分散情報生成装置について、前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成することを特徴とする分散情報生成装置を提案している。
【００１４】
この発明によれば、レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成する。したがって、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００１５】
（３）本発明は、（１）の分散情報生成装置について、前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成することを特徴とする分散情報生成装置を提案している。
【００１６】
この発明によれば、レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成する。したがって、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００１７】
（４）本発明は、（１）から（３）に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、分散情報を受信する受信手段と、該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段と、該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段と、該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部と、該復元された部分秘密情報を連結して秘密情報を出力する連結器と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１８】
この発明によれば、受信手段は、分散情報を受信し、分散情報分割手段は、その受信した分散情報を分割して部分分散情報を生成する。行列生成手段は、分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する。部分秘密情報復元部は、行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元し、連結器が、その復元された部分秘密情報を連結して秘密情報を出力する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。
【００１９】
（５）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、を有することを特徴とする分散情報生成方法を提案している。
【００２０】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２１】
（６）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、を有することを特徴とする分散情報生成方法を提案している。
【００２２】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２３】
（７）本発明は、（５）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、を有することを特徴とする秘密情報復元方法を提案している。
【００２４】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。また、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２５】
（８）本発明は、（６）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、を有することを特徴とする秘密情報復元方法を提案している。
【００２６】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２７】
（９）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００２８】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２９】
（１０）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３０】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００３１】
（１１）本発明は、（９）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。また、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００３３】
（１２）本発明は、（１０）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３４】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【発明の効果】
【００３５】
本発明によれば、分散情報に重み付けを行うことが可能となり、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることが可能となるという効果がある。また、秘密情報の復元構造をＣｏｎｊｕｎｃｔｉｖｅアクセス構造、あるいはＤｉｓｊｕｎｃｔｉｖｅアクセス構造のいずれかで構成可能となるという効果がある。
【００３６】
そのため、例えば、会社組織内部の上司・部下に分散情報を配布して管理する場合など、権限の強さや運用形態に応じた分散情報の配布が可能となる。さらに、排他的論理和のみで分散情報の生成・秘密情報の復元を行うことが出来るため、同様の構造を実現している従来の手法(非特許文献４および非特許文献５)よりも高速な演算が可能であり、省電力機器での実装や、大容量データ向けの実装などを実現することができるという効果がある。
【発明を実施するための最良の形態】
【００３７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３８】
＜分散情報生成装置の構成＞
図１および図２を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
本実施形態に係る分散情報生成装置は、図１に示すように、分割器１１と、ダミー情報生成器１２と、乱数生成器１３ａ〜１３ｄと、部分分散情報生成器１４と、連結器１５と、送信装置１８とから構成されている。
【００３９】
分割器１１は、秘密情報ｓを入力し、これを（ｎｐ−１）個の部分秘密情報ｓｑに分割する。ダミー情報生成器１２は、オールゼロからなるダミー部分秘密情報ｓ０を生成する。生成されたダミー部分秘密情報ｓ０及び部分秘密情報ｓｑは、部分分散情報生成器１３に送られる。
【００４０】
乱数生成器１３ａ〜１３ｄは、互いに独立な乱数ｒを発生している。そして、同様な乱数生成器１３ａ〜１３ｄを複数個備えている。乱数生成器１３ａ〜１３ｄからの乱数ｒは、部分分散情報生成器１４に送られる。
【００４１】
部分分散情報生成器１４は、ダミー部分秘密情報ｓ０及び（ｎｐ−１）個の部分秘密情報ｓｑと、乱数発生器１３ａ〜１３ｄからの乱数ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する。具体的には、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行い、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行い、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定し、決定されたペアについて、排他的論理和演算を行って、レベルに応じた重み付けがされた部分分散情報を出力する。なお、部分分散情報生成器１３の詳細な構成については、後述する。
【００４２】
連結器１５は、部分分散情報生成器１４から出力される部分分散情報をグループごとにバイナリ連結し、ｎ個の分散情報Ｓｉを生成する。送信装置１６は、生成されたｎ個の分散情報Ｓｉを、管理者Ｐｉにセキュアに送信する。
【００４３】
なお、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００４４】
＜部分分散情報生成器の構成＞
次に、本実施形態に係る部分分散情報生成器の構成について説明する。
本実施形態に係る部分分散情報生成器は、図２に示すように、ＸＯＲ演算器２１と、ＸＯＲ演算器２２ａ〜２２ｎと、レベル閾値割り当て器２３と、ＸＯＲ演算器２４とから構成されている。
【００４５】
ＸＯＲ演算器２１は、素数と巡回群の性質を用いて、互いに重複しない部分秘密情報のペアについてＸＯＲ演算を実行する。ＸＯＲ演算器２２ａから２２ｎは、素数と巡回群の性質を用いて、互いに重複しない乱数のペアについてＸＯＲ演算を実行する。
【００４６】
レベル閾値割り当て器２３は、生成する部分分散情報のレベル（つまり分散情報のレベル）と該当するレベルおよびそのレベル閾値に応じて、部分分散情報を構成する要素（部分秘密情報のペアおよび乱数のペアのＸＯＲ情報うち、どの要素を使用するか）を決定する。
【００４７】
なお、階層型にレベル分けする方式としては、秘密情報の復元を許す分散情報を有する管理者のグループが、「レベル０からレベルＬまでの分散情報がｋＬ以上個集まっている」という条件をＬ＝０、１、・・・、ｍの全てのレベルで満たすグループのみを対象として構成するＣｏｎｊｕｎｃｔｉｖｅアクセス構造と、秘密情報の復元を許す分散情報を有する管理者のグループが、「レベル０からレベルＬまでの分散情報がｋＬ以上個集まっている」という条件をＬ＝０、１、・・・、ｍのいずれかのレベルで満たすグループのみを対象として構成するＤｉｓｊｕｎｃｔｉｖｅアクセス構造とがあるが、本実施形態では、この両者に対応する。
【００４８】
そのため、レベル閾値割り当て器２３では、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成を用いる場合には、レベルＬの部分分散情報を生成には、ｋ−ｋＬ−１個の要素を使用する。このとき、レベル０では、部分秘密情報のＸＯＲペア１個と乱数のＸＯＲペアｋ−１個とを合せたｋ個の要素を使用するが、レベル１以上では、乱数のＸＯＲペアのみｋ−ｋＬ−１個を使用する。ここで、ｋＬ−１は、レベルＬ−１のレベル閾値であり、ｋ−１＝０である。
【００４９】
一方、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成を用いる場合には、レベルＬの部分分散情報を生成には、ｋＬ個の要素を使用する。また、全てのレベルにおいてＣｏｎｊｕｎｃｔｉｖｅアクセス構造の構成とは異なり、部分分散情報の構成に用いるペアは部分秘密情報のＸＯＲペア１個と乱数のＸＯＲペアｋＬ−１個とのｋＬ個の要素を使用する。
【００５０】
ＸＯＲ演算器２３は、ＸＯＲ演算器２１およびＸＯＲ演算器２２ａから２２ｎにおいて、ＸＯＲ演算されたものについて、さらに、素数と巡回群の性質を用いて、組み合わせを決定し、ＸＯＲ演算を実行して、部分分散情報を生成する。こうした、一連の処理により、重み付けされた複数の部分分散情報が生成される。
【００５１】
＜分散情報生成装置の処理および秘密情報復元装置の構成および処理＞
次に、分散情報生成装置の処理について、更に、詳述する。なお、本実施形態では、秘密情報ｓを（ｎｐ−１）個に等分割する必要があり、ｎｐは、分散数ｎについて、ｎｐ≧ｎ＋１を満たす素数である。そのため、希望する分散数ｎについて、ｎ＋１が合成数である場合には、ｎｐ＞ｎ＋１を満たす素数ｎｐを用いて、分散情報を（ｎｐ−１）個生成し、そのうち、ｎ個を用いることで、分散数ｎを実現する。また、ここでは、分散情報生成装置の処理および秘密情報復元装置の処理について説明する前に、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００５２】
【数１】
【００５３】
＜分散情報生成装置の処理＞
先ず、分散情報生成装置の処理について図３を用いて説明する。
【００５４】
（ステップ１）
秘密情報ｓをそれぞれｄビットの部分秘密情報（ｎｐ−１）個に分割する（ステップＳ１０１）。
【００５５】
【数２】
【００５６】
（ステップ２）
ダミーの部分秘密情報ｓｎｐ−１∈{０}ｄを生成する（ステップＳ１０２）。
【００５７】
（ステップ３）
数３に示すように、計（ｋ−１）ｎｐ個のｄビットの乱数を全て独立に生成する（ステップＳ１０３）。
【００５８】
【数３】
【００５９】
（ステップ４）
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるため、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の場合には、数４を用いて、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の場合には、数５を用いて、部分分散情報Ｓ（ｉ，ｊ）を生成する（ステップＳ１０４）。
【００６０】
【数４】
【００６１】
【数５】
【００６２】
なお、数４では、表現を簡単にするために、ｒｊ０＝ｓｊとして表わしている。また、ｋ−１＝０である。数４により、Ｐｉがレベル０の管理者として割り当てられているとき、レベル０の部分分散情報ｗ（ｉ，ｊ）は、部分秘密情報のＸＯＲペア１つと乱数のＸＯＲペアｋ−１個の計ｋ個の要素で構成される。一方、ＰｉがレベルＬ≧１の管理者として割り当てられているとき、レベルＬの部分分散情報ｗ（ｉ，ｊ）は、乱数のＸＯＲペアのみｋ−ｋＬ−１個の要素で構成される。
【００６３】
また、数５では、表現を簡単にするために、ｒｊｋ＝ｓｊとして表わしている。数５により、ＰｉがレベルＬ（Ｌ＝０、・・・、ｍ）の管理者として割り当てられているとき、レベルＬの部分分散情報ｗ（ｉ，ｊ）は、部分秘密情報のＸＯＲペア１つと乱数のＸＯＲペアｋＬ−１個の計ｋＬ個の要素で構成される。
【００６４】
Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の場合も、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の場合も、個々の要素（乱数、部分秘密情報）のインデックスは、素数ｎｐを法としているため、巡回群（加法群）を形成しており、これを利用してペアを決定しているため、ペアは互いに重複することはない。
【００６５】
（ステップ５）
部分分散情報ｗ（ｉ、０）、・・・、ｗ（ｉ，ｎｐ−２）を連結して分散情報ｗｉを生成し、管理者Ｐｉへセキュアに配付する（ステップＳ１０５）。
【００６６】
【数６】
【００６７】
ここで、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。これにより、情報理論的安全性を十分に保障する分散情報生成装置を構築することができる。
【００６８】
＜秘密情報復元装置の構成＞
上記の分散情報の生成処理を踏まえて、本発明の秘密情報復元装置について説明する。本実施形態に係る秘密情報復元装置は、図４に示すように、受信機３１と、分散情報分割部３２と、行列演算部３３と、ＸＯＲ演算部３４と、連結部３５とから構成されている。
【００６９】
受信機３１は、各管理者Ｐｉから例えば、ｋ個（ｋは正の整数）の分散情報を受信する。分散情報分割部３２は、受信機３１が受信したｋ個（ｋは正の整数）の分散情報を入力し、複数の部分分散情報を生成する。
【００７０】
行列演算部３３は、例えば、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。
【００７１】
ＸＯＲ演算部３４は、行列演算部３３から入力された組み合わせ情報に基づいて、部分分散情報を組み合わせて、ＸＯＲ演算を実行する。連結部３５は、ダミーの部分分散情報を除く、全ての部分秘密情報をバイナリ連結して、秘密情報を復元する。
【００７２】
＜秘密情報復元装置の処理＞
次に、図５を用いて、本実施形態に係る秘密情報復元装置の処理について説明する。
なお、以下では、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理と、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理とに分けて、説明する。
【００７３】
＜Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理＞
この場合は、ｋ人の相異なる管理者Ｐｉ０、・・・、Ｐｉｋ−１が集まったとして、それぞれの分散情報をｗｉ０、・・・、ｗｉｋ−１とする。（ただし、１≦ｉ０、・・・、ｉｋ−１≦ｎ、ｉ０、・・・、ｉｋ−１は、全て互いに相違するものとする）さらに、ｋ個集まった場合も「集まっている管理者のうち、レベル０からレベルＬまでに属する管理者の総数がｋＬ以上である」という条件が、Ｌ＝０、・・・、ｍの全てのレベルで満たされているとする。すなわち、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造Γについて、{Ｐｉ０、・・・、Ｐｉｋ−１}∈Γが成立しているものとする。
【００７４】
それぞれの分散情報を部分分散情報に分割する。すなわち、数７に示すようなｋ（ｎｐ−１）個の部分分散情報を得る。（ステップＳ２０１）。一方、行列演算部３３には、ｋ個の分散情報についてのインデックス番号が入力される。
【００７５】
【数７】
【００７６】
そして、行列演算部３３では、部分分散情報の構成により、数８を満たすようなｋ（ｎｐ−１）×ｋｎｐ−１のバイナリ行列Ｍが生成される（ステップＳ２０２）。このとき、ｓｎｐ−１は、オールゼロであることにより、ＸＯＲ演算しても値が一切変化しないため、ｓｎｐ−１については、考慮しない。
【００７７】
【数８】
【００７８】
次に、行列演算部３３は、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る（ステップＳ２０３）。このとき、Ｉは、ｋ（ｎｐ−１）×ｋ（ｎｐ−１）の単位行列である。
【００７９】
さらに、ＸＯＲ演算部３４は、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、数９に示す全部の部分秘密情報を復元する（ステップＳ２０４）。ここで、Ｉ´０、・・・、Ｉ´ｎｐ-２は、それぞれＩ´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ-1）行目を表す。
【００８０】
【数９】
【００８１】
そして、連結器３５において、すべての部分秘密情報を連結して、元の秘密情報Ｋを復元する（ステップＳ２０５）。
【００８２】
【数１０】
【００８３】
＜Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理＞
この場合は、ｋＤ人の相異なる管理者Ｐｉ０、・・・、ＰｉｋＤ−１が集まったとして、それぞれの分散情報をｗｉ０、・・・、ｗｉｋＤ−１とする。（ただし、１≦ｉ０、・・・、ｉｋＤ−１≦ｎ、ｉ０、・・・、ｉｋＤ−１は、全て互いに相違するものとする）このとき「集まっている管理者のうち、レベル０からレベルＬまでに属する管理者の総数がｋＬ以上である」という条件が、Ｌ＝０、・・・、ｍのいずれかのレベルで満たされているとする。すなわち、本条件がレベルＤで満たされており、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造Γについて、{Ｐｉ０、・・・、ＰｉｋＤ−１}∈Γが成立しているものとする。
【００８４】
それぞれの分散情報を部分分散情報に分割する。すなわち、数１１に示すようなｋ（ｎｐ−１）個の部分分散情報を得る。（ステップＳ２０１）。一方、行列演算部３３には、ｋ個の分散情報についてのインデックス番号が入力される。
【００８５】
【数１１】
【００８６】
そして、行列演算部３３では、部分分散情報の構成により、数１２を満たすようなｋＤ（ｎｐ−１）×ｋＤｎｐ−１のバイナリ行列Ｍが生成される（ステップＳ２０２）。このとき、ｓｎｐ−１は、オールゼロであり、レベル０からレベルＤの部分分散情報に乱数ｒ０１、・・・、ｒｎｐ−１１、・・・、ｒ０ｋ−ｋＤ、・・・ｒｎｐ−１ｋ−ｋＤが含まれていないため、それらの要素は、考慮しない。
【００８７】
【数１２】
【００８８】
次に、行列演算部３３は、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る（ステップＳ２０３）。このとき、Ｉは、ｋＤ（ｎｐ−１）×ｋＤ（ｎｐ−１）の単位行列である。
【００８９】
さらに、ＸＯＲ演算部３４は、生成したI´の第（ｋＤ−１）（ｎｐ−１）＋１行目からｋＤ（ｎｐ−１）行目を用いて、数１３に示す全部の部分秘密情報を復元する（ステップＳ２０４）。ここで、Ｉ´０、・・・、Ｉ´ｎｐ-２は、それぞれＩ´の第（ｋＤ−１）（ｎｐ−１）＋１行目からｋＤｋ（ｎｐ−１）行目を表す。
【００９０】
【数１３】
【００９１】
そして、連結器３５において、すべての部分秘密情報を連結して、元の秘密情報Ｋを復元する（ステップＳ２０５）。
【００９２】
【数１４】
【００９３】
したがって、本実施形態によれば、分散情報に重み付けを行うことが可能となり、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることが可能となる。また、秘密情報の復元構造をＣｏｎｊｕｎｃｔｉｖｅアクセス構造、あるいはＤｉｓｊｕｎｃｔｉｖｅアクセス構造のいずれかで構成可能となる。
【００９４】
＜Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成例＞
次に、具体的に、パラメータを固定して、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成を行った閾値秘密分散法の例を以下に示す。
【００９５】
なお、ここでは、（ｋ、ｎ）＝（３、６）とし、ｎｐ＝７とする。また、管理者をレベル０、１、２の３レベルに割り当てるとし、以下のように、管理者Ｐ1、・・・、Ｐ6のレベル分けを行う。
レベル０：Ｐ1、Ｐ2
レベル１：Ｐ3、Ｐ4
レベル２：Ｐ5、Ｐ6
【００９６】
このとき、各レベルにおけるレベル閾値は、それぞれｋ0＝１、ｋ1＝２、ｋ2＝ｋ＝３とする。これらのパラメータにおいて、管理者Ｐ1、Ｐ4、Ｐ5が集まり、分散情報ｗ1、ｗ4、ｗ5から復元する例をここに示す。
【００９７】
それぞれの分散情報を分割して得る部分分散情報は、以下、数１５のように表わすことができる。
【００９８】
【数１５】
【００９９】
また、復元手順におけるステップＳ２０２のＭは、以下、数１６のように表わされる。
【０１００】
【数１６】
【０１０１】
数１６のＭをガウス―ジョルダン法により変形し、Ｉ´を得る。このとき、Ｉ´の第１３行目〜１８行目を用いて、ｓ0、・・・、ｓ5、が、以下、数１７のように復元される。
【０１０２】
【数１７】
【０１０３】
最後に、以下、数１８のように、部分秘密情報を連結し、秘密情報を復元する。
【０１０４】
【数１８】
【０１０５】
＜Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成例＞
さらに、具体的に、パラメータを固定して、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成を行った閾値秘密分散法の例を以下に示す。
【０１０６】
なお、ここでは、（ｋ、ｎ）＝（３、６）とし、ｎｐ＝７とする。また、管理者をレベル０、１の２レベルに割り当てるとし、以下のように、管理者Ｐ1、・・・、Ｐ6のレベル分けを行う。
レベル０：Ｐ1、Ｐ2、Ｐ3
レベル１：Ｐ4、Ｐ5、Ｐ6
【０１０７】
このとき、各レベルにおけるレベル閾値は、それぞれｋ0＝２、ｋ1＝ｋ＝３とする。これらのパラメータにおいて、管理者Ｐ1、Ｐ2が集まり、分散情報ｗ1、ｗ2から復元する例をここに示す。
【０１０８】
それぞれの分散情報を分割して得る部分分散情報は、以下、数１９のように表わすことができる。
【０１０９】
【数１９】
【０１１０】
また、復元手順におけるステップＳ２０２のＭのサイズは、１２行１３列となり、以下、数２０のように表わされる。
【０１１１】
【数２０】
【０１１２】
数２０のＭをガウス―ジョルダン法により変形し、Ｉ´を得る。このとき、Ｉ´の第７行目〜１２行目を用いて、ｓ0、・・・、ｓ5、が、以下、数２１のように復元される。
【０１１３】
【数２１】
【０１１４】
最後に、以下、数２２のように、部分秘密情報を連結し、秘密情報を復元する。
【０１１５】
【数２２】
【０１１６】
なお、分散情報生成装置および秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置および秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報生成装置および秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【０１１７】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【０１１８】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１１９】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【０１２０】
【図１】本実施形態に係る分散情報生成装置の構成を例示した図である。
【図２】本実施形態に係る部分分散情報生成器の構成図である。
【図３】本実施形態に係る分散情報生成装置の処理フローである。
【図４】本実施形態に係る秘密情報復元装置の構成図である。
【図５】本実施形態に係る秘密情報復元処理のフローである。
【符号の説明】
【０１２１】
１１・・・分割器
１２・・・ダミー情報生成器
１３ａ〜１３ｄ・・・乱数発生器
１４・・・部分分散情報生成器
１５・・・連結器
１６・・・送信装置
２１、２２ａ〜２２ｎ、２４・・・ＸＯＲ演算器
２３・・・レベル閾値割り当て器
３１・・・受信機
３２・・・分散情報分割部
３３・・・行列演算部
３４・・・ＸＯＲ演算部
３５・・・連結部
【技術分野】
【０００１】
本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値秘密分散法により、分散情報に階層的な重み付けを行う分散情報生成装置、分散情報生成方法、秘密情報復元装置、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。
【０００４】
これに対して、ＸＯＲを用いて、（ｋ，ｎ）閾値秘密分散法を構築することにより、高速に情報の分散および復元を可能とする方式が開示されている（例えば、非特許文献２および３参照。）。この非特許文献２および３で開示された方法は、その構造において等価なものであり、単純に高速動作を行うだけでなく、非特許文献１と同様に、完全な情報論理的安全性が保証されており、分散情報のデータ長が秘密情報のデータ長と等しいという特徴を有している。
【０００５】
また、非特許文献３に記載の方法はｋ個の分散情報から秘密情報を復元する際に、秘密情報のみならず分散情報を構成する乱数も復元可能であるという特徴があり、非特許文献２に記載の方法は、ｋが３以上の場合には、秘密情報は復元されるが、乱数に関しては、復元不可能という特徴がある。
【０００６】
ところで、非特許文献１、非特許文献２、非特許文献３では、いずれも全ての分散情報は平等に扱われるため、分散情報の重み付けを行うことは出来ない。
【０００７】
そのため、非特許文献１をベースとし、分散情報に重み付けを行う方式として、非特許文献４、非特許文献５、特許文献１に記載された手法が知られている。例えば、特許文献１に記載の手法では、分散情報をさらに何度も秘密分散法によって分散し、分散情報の木構造を構成することで階層型の重み付けを実現する。また、非特許文献４、非特許文献５の手法は、非特許文献１の分散情報を構成するためのｋ−１次の多項式を重みに応じて微分し、その結果の新たな多項式を用いて分散情報を生成することで、階層型の重み付けを実現している。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ， ｖｏｌ．２２ ｎｏ．１１ ｐｐ．６１２−６１３， １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ Ｆａｓｔ （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ Ｕｓｉｎｇ Ｅｘｃｌｕｓｉｖｅ−ＯＲ Ｏｐｅｒａｔｉｏｎ ａｎｄ ｉｔｓ Ｅｘｔｅｎｓｉｏｎ ｔｏ （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【非特許文献４】Ｔ. Ｔａｓｓａ, ‘‘Ｈｉｅｒａｒｃｈｉｃａｌ ｔｈｒｅｓｈｏｌｄ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ,’‘Ｐｒｏｃ. ＴＣＣ２００４, ＬＮＣＳ ２９５１, ｐｐ.４７３−４９０, Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ, ２００４.
【非特許文献５】Ｍ. Ｂｅｌｅｎｋｉｙ, ‘‘ＤｉｓｊｕｎｃｔｉｖｅＭｕｌｔｉ−Ｌｅｖｅｌ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ,’‘ Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ,ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００８／０１８、２００８.
【特許文献１】特開平１０−１９８２７２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に記載された手法何度も低速な非特許文献１の分散処理・復元処理を実行する必要があり、そのコストは非常に大きいという問題がある。また、非特許文献４、非特許文献５に記載された手法方式も同様に、非特許文献１をベースとしているため、分散処理・復元処理のコストが大きいという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、高速な処理で、分散情報に階層的な重み付けを行う分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１１】
（１）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置であって、秘密情報を入力し、これを分割して部分秘密情報を生成する分割器と、オールゼロからなるダミー情報を生成するダミー情報生成器と、乱数を生成する乱数生成器と、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、素数と巡回群との性質を用いて、該ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、該レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、前記レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、該出力された部分分散情報を連結し、分散情報を出力する連結器と、該出力された分散情報を管理者に送信する送信手段と、を備えたことを特徴とする分散情報生成装置を提案している。
【００１２】
この発明によれば、分割器は、秘密情報を入力し、これを分割して部分秘密情報を生成する。ダミー情報生成器は、オールゼロからなるダミー情報を生成する。乱数生成器は、乱数を生成する。第１の排他的論理和演算器は、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う。第２の排他的論理和演算器は、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う。レベル割り当て手段は、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定する。第３の排他的論理和演算器は、レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、レベルに応じた重み付けがされた部分分散情報を出力する。そして、連結器は、出力された部分分散情報を連結し、分散情報を出力し、送信手段は、出力された分散情報を管理者に送信する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。
【００１３】
（２）本発明は、（１）の分散情報生成装置について、前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成することを特徴とする分散情報生成装置を提案している。
【００１４】
この発明によれば、レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成する。したがって、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００１５】
（３）本発明は、（１）の分散情報生成装置について、前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成することを特徴とする分散情報生成装置を提案している。
【００１６】
この発明によれば、レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成する。したがって、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００１７】
（４）本発明は、（１）から（３）に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、分散情報を受信する受信手段と、該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段と、該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段と、該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部と、該復元された部分秘密情報を連結して秘密情報を出力する連結器と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１８】
この発明によれば、受信手段は、分散情報を受信し、分散情報分割手段は、その受信した分散情報を分割して部分分散情報を生成する。行列生成手段は、分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する。部分秘密情報復元部は、行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元し、連結器が、その復元された部分秘密情報を連結して秘密情報を出力する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。
【００１９】
（５）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、を有することを特徴とする分散情報生成方法を提案している。
【００２０】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２１】
（６）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、を有することを特徴とする分散情報生成方法を提案している。
【００２２】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２３】
（７）本発明は、（５）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、を有することを特徴とする秘密情報復元方法を提案している。
【００２４】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。また、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２５】
（８）本発明は、（６）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、を有することを特徴とする秘密情報復元方法を提案している。
【００２６】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２７】
（９）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００２８】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００２９】
（１０）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する第４のステップと、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３０】
この発明によれば、秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割し、ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する。次に、（ｋ−１）ｎｐ個の乱数をすべて独立に生成し、ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を所定の数式を用いて生成する。そして、ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する。したがって、分散情報の管理者の権限等に応じて、分散情報に重み付けを行うことができる。また、排他的論理和演算のみを用いて処理を行うことから高速に分散処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００３１】
（１１）本発明は、（９）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。また、秘密情報の復元構造としてＣｏｎｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【００３３】
（１２）本発明は、（１０）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、前記部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３４】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得、部分分散情報の構成により、所定の数式を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する。次に、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る。そして、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報ｓを復元する。したがって、分散情報が、管理者の権限等によって、重み付けされているため、特定の分散情報が集まったときにだけ、高速に復元処理を実行することができる。さらに、秘密情報の復元構造としてＤｉｓｊｕｎｃｔｉｖｅアクセス構造を用いることができるため、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることができる。
【発明の効果】
【００３５】
本発明によれば、分散情報に重み付けを行うことが可能となり、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることが可能となるという効果がある。また、秘密情報の復元構造をＣｏｎｊｕｎｃｔｉｖｅアクセス構造、あるいはＤｉｓｊｕｎｃｔｉｖｅアクセス構造のいずれかで構成可能となるという効果がある。
【００３６】
そのため、例えば、会社組織内部の上司・部下に分散情報を配布して管理する場合など、権限の強さや運用形態に応じた分散情報の配布が可能となる。さらに、排他的論理和のみで分散情報の生成・秘密情報の復元を行うことが出来るため、同様の構造を実現している従来の手法(非特許文献４および非特許文献５)よりも高速な演算が可能であり、省電力機器での実装や、大容量データ向けの実装などを実現することができるという効果がある。
【発明を実施するための最良の形態】
【００３７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３８】
＜分散情報生成装置の構成＞
図１および図２を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
本実施形態に係る分散情報生成装置は、図１に示すように、分割器１１と、ダミー情報生成器１２と、乱数生成器１３ａ〜１３ｄと、部分分散情報生成器１４と、連結器１５と、送信装置１８とから構成されている。
【００３９】
分割器１１は、秘密情報ｓを入力し、これを（ｎｐ−１）個の部分秘密情報ｓｑに分割する。ダミー情報生成器１２は、オールゼロからなるダミー部分秘密情報ｓ０を生成する。生成されたダミー部分秘密情報ｓ０及び部分秘密情報ｓｑは、部分分散情報生成器１３に送られる。
【００４０】
乱数生成器１３ａ〜１３ｄは、互いに独立な乱数ｒを発生している。そして、同様な乱数生成器１３ａ〜１３ｄを複数個備えている。乱数生成器１３ａ〜１３ｄからの乱数ｒは、部分分散情報生成器１４に送られる。
【００４１】
部分分散情報生成器１４は、ダミー部分秘密情報ｓ０及び（ｎｐ−１）個の部分秘密情報ｓｑと、乱数発生器１３ａ〜１３ｄからの乱数ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する。具体的には、素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行い、素数と巡回群との性質を用いて、ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行い、個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定し、決定されたペアについて、排他的論理和演算を行って、レベルに応じた重み付けがされた部分分散情報を出力する。なお、部分分散情報生成器１３の詳細な構成については、後述する。
【００４２】
連結器１５は、部分分散情報生成器１４から出力される部分分散情報をグループごとにバイナリ連結し、ｎ個の分散情報Ｓｉを生成する。送信装置１６は、生成されたｎ個の分散情報Ｓｉを、管理者Ｐｉにセキュアに送信する。
【００４３】
なお、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００４４】
＜部分分散情報生成器の構成＞
次に、本実施形態に係る部分分散情報生成器の構成について説明する。
本実施形態に係る部分分散情報生成器は、図２に示すように、ＸＯＲ演算器２１と、ＸＯＲ演算器２２ａ〜２２ｎと、レベル閾値割り当て器２３と、ＸＯＲ演算器２４とから構成されている。
【００４５】
ＸＯＲ演算器２１は、素数と巡回群の性質を用いて、互いに重複しない部分秘密情報のペアについてＸＯＲ演算を実行する。ＸＯＲ演算器２２ａから２２ｎは、素数と巡回群の性質を用いて、互いに重複しない乱数のペアについてＸＯＲ演算を実行する。
【００４６】
レベル閾値割り当て器２３は、生成する部分分散情報のレベル（つまり分散情報のレベル）と該当するレベルおよびそのレベル閾値に応じて、部分分散情報を構成する要素（部分秘密情報のペアおよび乱数のペアのＸＯＲ情報うち、どの要素を使用するか）を決定する。
【００４７】
なお、階層型にレベル分けする方式としては、秘密情報の復元を許す分散情報を有する管理者のグループが、「レベル０からレベルＬまでの分散情報がｋＬ以上個集まっている」という条件をＬ＝０、１、・・・、ｍの全てのレベルで満たすグループのみを対象として構成するＣｏｎｊｕｎｃｔｉｖｅアクセス構造と、秘密情報の復元を許す分散情報を有する管理者のグループが、「レベル０からレベルＬまでの分散情報がｋＬ以上個集まっている」という条件をＬ＝０、１、・・・、ｍのいずれかのレベルで満たすグループのみを対象として構成するＤｉｓｊｕｎｃｔｉｖｅアクセス構造とがあるが、本実施形態では、この両者に対応する。
【００４８】
そのため、レベル閾値割り当て器２３では、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成を用いる場合には、レベルＬの部分分散情報を生成には、ｋ−ｋＬ−１個の要素を使用する。このとき、レベル０では、部分秘密情報のＸＯＲペア１個と乱数のＸＯＲペアｋ−１個とを合せたｋ個の要素を使用するが、レベル１以上では、乱数のＸＯＲペアのみｋ−ｋＬ−１個を使用する。ここで、ｋＬ−１は、レベルＬ−１のレベル閾値であり、ｋ−１＝０である。
【００４９】
一方、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成を用いる場合には、レベルＬの部分分散情報を生成には、ｋＬ個の要素を使用する。また、全てのレベルにおいてＣｏｎｊｕｎｃｔｉｖｅアクセス構造の構成とは異なり、部分分散情報の構成に用いるペアは部分秘密情報のＸＯＲペア１個と乱数のＸＯＲペアｋＬ−１個とのｋＬ個の要素を使用する。
【００５０】
ＸＯＲ演算器２３は、ＸＯＲ演算器２１およびＸＯＲ演算器２２ａから２２ｎにおいて、ＸＯＲ演算されたものについて、さらに、素数と巡回群の性質を用いて、組み合わせを決定し、ＸＯＲ演算を実行して、部分分散情報を生成する。こうした、一連の処理により、重み付けされた複数の部分分散情報が生成される。
【００５１】
＜分散情報生成装置の処理および秘密情報復元装置の構成および処理＞
次に、分散情報生成装置の処理について、更に、詳述する。なお、本実施形態では、秘密情報ｓを（ｎｐ−１）個に等分割する必要があり、ｎｐは、分散数ｎについて、ｎｐ≧ｎ＋１を満たす素数である。そのため、希望する分散数ｎについて、ｎ＋１が合成数である場合には、ｎｐ＞ｎ＋１を満たす素数ｎｐを用いて、分散情報を（ｎｐ−１）個生成し、そのうち、ｎ個を用いることで、分散数ｎを実現する。また、ここでは、分散情報生成装置の処理および秘密情報復元装置の処理について説明する前に、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００５２】
【数１】
【００５３】
＜分散情報生成装置の処理＞
先ず、分散情報生成装置の処理について図３を用いて説明する。
【００５４】
（ステップ１）
秘密情報ｓをそれぞれｄビットの部分秘密情報（ｎｐ−１）個に分割する（ステップＳ１０１）。
【００５５】
【数２】
【００５６】
（ステップ２）
ダミーの部分秘密情報ｓｎｐ−１∈{０}ｄを生成する（ステップＳ１０２）。
【００５７】
（ステップ３）
数３に示すように、計（ｋ−１）ｎｐ個のｄビットの乱数を全て独立に生成する（ステップＳ１０３）。
【００５８】
【数３】
【００５９】
（ステップ４）
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるため、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の場合には、数４を用いて、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の場合には、数５を用いて、部分分散情報Ｓ（ｉ，ｊ）を生成する（ステップＳ１０４）。
【００６０】
【数４】
【００６１】
【数５】
【００６２】
なお、数４では、表現を簡単にするために、ｒｊ０＝ｓｊとして表わしている。また、ｋ−１＝０である。数４により、Ｐｉがレベル０の管理者として割り当てられているとき、レベル０の部分分散情報ｗ（ｉ，ｊ）は、部分秘密情報のＸＯＲペア１つと乱数のＸＯＲペアｋ−１個の計ｋ個の要素で構成される。一方、ＰｉがレベルＬ≧１の管理者として割り当てられているとき、レベルＬの部分分散情報ｗ（ｉ，ｊ）は、乱数のＸＯＲペアのみｋ−ｋＬ−１個の要素で構成される。
【００６３】
また、数５では、表現を簡単にするために、ｒｊｋ＝ｓｊとして表わしている。数５により、ＰｉがレベルＬ（Ｌ＝０、・・・、ｍ）の管理者として割り当てられているとき、レベルＬの部分分散情報ｗ（ｉ，ｊ）は、部分秘密情報のＸＯＲペア１つと乱数のＸＯＲペアｋＬ−１個の計ｋＬ個の要素で構成される。
【００６４】
Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の場合も、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の場合も、個々の要素（乱数、部分秘密情報）のインデックスは、素数ｎｐを法としているため、巡回群（加法群）を形成しており、これを利用してペアを決定しているため、ペアは互いに重複することはない。
【００６５】
（ステップ５）
部分分散情報ｗ（ｉ、０）、・・・、ｗ（ｉ，ｎｐ−２）を連結して分散情報ｗｉを生成し、管理者Ｐｉへセキュアに配付する（ステップＳ１０５）。
【００６６】
【数６】
【００６７】
ここで、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。これにより、情報理論的安全性を十分に保障する分散情報生成装置を構築することができる。
【００６８】
＜秘密情報復元装置の構成＞
上記の分散情報の生成処理を踏まえて、本発明の秘密情報復元装置について説明する。本実施形態に係る秘密情報復元装置は、図４に示すように、受信機３１と、分散情報分割部３２と、行列演算部３３と、ＸＯＲ演算部３４と、連結部３５とから構成されている。
【００６９】
受信機３１は、各管理者Ｐｉから例えば、ｋ個（ｋは正の整数）の分散情報を受信する。分散情報分割部３２は、受信機３１が受信したｋ個（ｋは正の整数）の分散情報を入力し、複数の部分分散情報を生成する。
【００７０】
行列演算部３３は、例えば、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。
【００７１】
ＸＯＲ演算部３４は、行列演算部３３から入力された組み合わせ情報に基づいて、部分分散情報を組み合わせて、ＸＯＲ演算を実行する。連結部３５は、ダミーの部分分散情報を除く、全ての部分秘密情報をバイナリ連結して、秘密情報を復元する。
【００７２】
＜秘密情報復元装置の処理＞
次に、図５を用いて、本実施形態に係る秘密情報復元装置の処理について説明する。
なお、以下では、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理と、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理とに分けて、説明する。
【００７３】
＜Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理＞
この場合は、ｋ人の相異なる管理者Ｐｉ０、・・・、Ｐｉｋ−１が集まったとして、それぞれの分散情報をｗｉ０、・・・、ｗｉｋ−１とする。（ただし、１≦ｉ０、・・・、ｉｋ−１≦ｎ、ｉ０、・・・、ｉｋ−１は、全て互いに相違するものとする）さらに、ｋ個集まった場合も「集まっている管理者のうち、レベル０からレベルＬまでに属する管理者の総数がｋＬ以上である」という条件が、Ｌ＝０、・・・、ｍの全てのレベルで満たされているとする。すなわち、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造Γについて、{Ｐｉ０、・・・、Ｐｉｋ−１}∈Γが成立しているものとする。
【００７４】
それぞれの分散情報を部分分散情報に分割する。すなわち、数７に示すようなｋ（ｎｐ−１）個の部分分散情報を得る。（ステップＳ２０１）。一方、行列演算部３３には、ｋ個の分散情報についてのインデックス番号が入力される。
【００７５】
【数７】
【００７６】
そして、行列演算部３３では、部分分散情報の構成により、数８を満たすようなｋ（ｎｐ−１）×ｋｎｐ−１のバイナリ行列Ｍが生成される（ステップＳ２０２）。このとき、ｓｎｐ−１は、オールゼロであることにより、ＸＯＲ演算しても値が一切変化しないため、ｓｎｐ−１については、考慮しない。
【００７７】
【数８】
【００７８】
次に、行列演算部３３は、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る（ステップＳ２０３）。このとき、Ｉは、ｋ（ｎｐ−１）×ｋ（ｎｐ−１）の単位行列である。
【００７９】
さらに、ＸＯＲ演算部３４は、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、数９に示す全部の部分秘密情報を復元する（ステップＳ２０４）。ここで、Ｉ´０、・・・、Ｉ´ｎｐ-２は、それぞれＩ´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ-1）行目を表す。
【００８０】
【数９】
【００８１】
そして、連結器３５において、すべての部分秘密情報を連結して、元の秘密情報Ｋを復元する（ステップＳ２０５）。
【００８２】
【数１０】
【００８３】
＜Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造を構成した場合の復元処理＞
この場合は、ｋＤ人の相異なる管理者Ｐｉ０、・・・、ＰｉｋＤ−１が集まったとして、それぞれの分散情報をｗｉ０、・・・、ｗｉｋＤ−１とする。（ただし、１≦ｉ０、・・・、ｉｋＤ−１≦ｎ、ｉ０、・・・、ｉｋＤ−１は、全て互いに相違するものとする）このとき「集まっている管理者のうち、レベル０からレベルＬまでに属する管理者の総数がｋＬ以上である」という条件が、Ｌ＝０、・・・、ｍのいずれかのレベルで満たされているとする。すなわち、本条件がレベルＤで満たされており、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造Γについて、{Ｐｉ０、・・・、ＰｉｋＤ−１}∈Γが成立しているものとする。
【００８４】
それぞれの分散情報を部分分散情報に分割する。すなわち、数１１に示すようなｋ（ｎｐ−１）個の部分分散情報を得る。（ステップＳ２０１）。一方、行列演算部３３には、ｋ個の分散情報についてのインデックス番号が入力される。
【００８５】
【数１１】
【００８６】
そして、行列演算部３３では、部分分散情報の構成により、数１２を満たすようなｋＤ（ｎｐ−１）×ｋＤｎｐ−１のバイナリ行列Ｍが生成される（ステップＳ２０２）。このとき、ｓｎｐ−１は、オールゼロであり、レベル０からレベルＤの部分分散情報に乱数ｒ０１、・・・、ｒｎｐ−１１、・・・、ｒ０ｋ−ｋＤ、・・・ｒｎｐ−１ｋ−ｋＤが含まれていないため、それらの要素は、考慮しない。
【００８７】
【数１２】
【００８８】
次に、行列演算部３３は、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る（ステップＳ２０３）。このとき、Ｉは、ｋＤ（ｎｐ−１）×ｋＤ（ｎｐ−１）の単位行列である。
【００８９】
さらに、ＸＯＲ演算部３４は、生成したI´の第（ｋＤ−１）（ｎｐ−１）＋１行目からｋＤ（ｎｐ−１）行目を用いて、数１３に示す全部の部分秘密情報を復元する（ステップＳ２０４）。ここで、Ｉ´０、・・・、Ｉ´ｎｐ-２は、それぞれＩ´の第（ｋＤ−１）（ｎｐ−１）＋１行目からｋＤｋ（ｎｐ−１）行目を表す。
【００９０】
【数１３】
【００９１】
そして、連結器３５において、すべての部分秘密情報を連結して、元の秘密情報Ｋを復元する（ステップＳ２０５）。
【００９２】
【数１４】
【００９３】
したがって、本実施形態によれば、分散情報に重み付けを行うことが可能となり、秘密情報の復元を行うことが出来るグループを、柔軟にカスタマイズすることが可能となる。また、秘密情報の復元構造をＣｏｎｊｕｎｃｔｉｖｅアクセス構造、あるいはＤｉｓｊｕｎｃｔｉｖｅアクセス構造のいずれかで構成可能となる。
【００９４】
＜Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成例＞
次に、具体的に、パラメータを固定して、Ｃｏｎｊｕｎｃｔｉｖｅアクセス構造の構成を行った閾値秘密分散法の例を以下に示す。
【００９５】
なお、ここでは、（ｋ、ｎ）＝（３、６）とし、ｎｐ＝７とする。また、管理者をレベル０、１、２の３レベルに割り当てるとし、以下のように、管理者Ｐ1、・・・、Ｐ6のレベル分けを行う。
レベル０：Ｐ1、Ｐ2
レベル１：Ｐ3、Ｐ4
レベル２：Ｐ5、Ｐ6
【００９６】
このとき、各レベルにおけるレベル閾値は、それぞれｋ0＝１、ｋ1＝２、ｋ2＝ｋ＝３とする。これらのパラメータにおいて、管理者Ｐ1、Ｐ4、Ｐ5が集まり、分散情報ｗ1、ｗ4、ｗ5から復元する例をここに示す。
【００９７】
それぞれの分散情報を分割して得る部分分散情報は、以下、数１５のように表わすことができる。
【００９８】
【数１５】
【００９９】
また、復元手順におけるステップＳ２０２のＭは、以下、数１６のように表わされる。
【０１００】
【数１６】
【０１０１】
数１６のＭをガウス―ジョルダン法により変形し、Ｉ´を得る。このとき、Ｉ´の第１３行目〜１８行目を用いて、ｓ0、・・・、ｓ5、が、以下、数１７のように復元される。
【０１０２】
【数１７】
【０１０３】
最後に、以下、数１８のように、部分秘密情報を連結し、秘密情報を復元する。
【０１０４】
【数１８】
【０１０５】
＜Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成例＞
さらに、具体的に、パラメータを固定して、Ｄｉｓｊｕｎｃｔｉｖｅアクセス構造の構成を行った閾値秘密分散法の例を以下に示す。
【０１０６】
なお、ここでは、（ｋ、ｎ）＝（３、６）とし、ｎｐ＝７とする。また、管理者をレベル０、１の２レベルに割り当てるとし、以下のように、管理者Ｐ1、・・・、Ｐ6のレベル分けを行う。
レベル０：Ｐ1、Ｐ2、Ｐ3
レベル１：Ｐ4、Ｐ5、Ｐ6
【０１０７】
このとき、各レベルにおけるレベル閾値は、それぞれｋ0＝２、ｋ1＝ｋ＝３とする。これらのパラメータにおいて、管理者Ｐ1、Ｐ2が集まり、分散情報ｗ1、ｗ2から復元する例をここに示す。
【０１０８】
それぞれの分散情報を分割して得る部分分散情報は、以下、数１９のように表わすことができる。
【０１０９】
【数１９】
【０１１０】
また、復元手順におけるステップＳ２０２のＭのサイズは、１２行１３列となり、以下、数２０のように表わされる。
【０１１１】
【数２０】
【０１１２】
数２０のＭをガウス―ジョルダン法により変形し、Ｉ´を得る。このとき、Ｉ´の第７行目〜１２行目を用いて、ｓ0、・・・、ｓ5、が、以下、数２１のように復元される。
【０１１３】
【数２１】
【０１１４】
最後に、以下、数２２のように、部分秘密情報を連結し、秘密情報を復元する。
【０１１５】
【数２２】
【０１１６】
なお、分散情報生成装置および秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置および秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報生成装置および秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【０１１７】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【０１１８】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１１９】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【０１２０】
【図１】本実施形態に係る分散情報生成装置の構成を例示した図である。
【図２】本実施形態に係る部分分散情報生成器の構成図である。
【図３】本実施形態に係る分散情報生成装置の処理フローである。
【図４】本実施形態に係る秘密情報復元装置の構成図である。
【図５】本実施形態に係る秘密情報復元処理のフローである。
【符号の説明】
【０１２１】
１１・・・分割器
１２・・・ダミー情報生成器
１３ａ〜１３ｄ・・・乱数発生器
１４・・・部分分散情報生成器
１５・・・連結器
１６・・・送信装置
２１、２２ａ〜２２ｎ、２４・・・ＸＯＲ演算器
２３・・・レベル閾値割り当て器
３１・・・受信機
３２・・・分散情報分割部
３３・・・行列演算部
３４・・・ＸＯＲ演算部
３５・・・連結部
【特許請求の範囲】
【請求項１】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置であって、
秘密情報を入力し、これを分割して部分秘密情報を生成する分割器と、
オールゼロからなるダミー情報を生成するダミー情報生成器と、
乱数を生成する乱数生成器と、
素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、
素数と巡回群との性質を用いて、該ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、
個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、
該レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、前記レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、
該出力された部分分散情報を連結し、分散情報を出力する連結器と、
該出力された分散情報を管理者に送信する送信手段と、
を備えたことを特徴とする分散情報生成装置。
【請求項２】
前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成することを特徴とする請求項１に記載の分散情報生成装置。
【請求項３】
前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成することを特徴とする請求項１に記載の分散情報生成装置。
【請求項４】
請求項１から請求項３に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
分散情報を受信する受信手段と、
該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段と、
該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段と、
該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部と、
該復元された部分秘密情報を連結して秘密情報を出力する連結器と、
を備えたことを特徴とする秘密情報復元装置。
【請求項５】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数１を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
を有することを特徴とする分散情報生成方法。
【数１】
【請求項６】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数２を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
を有することを特徴とする分散情報生成方法。
【数２】
【請求項７】
請求項５に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数３を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
を有することを特徴とする秘密情報復元方法。
【数３】
【請求項８】
請求項６に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数４を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
を有することを特徴とする秘密情報復元方法。
【数４】
【請求項９】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数５を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数５】
【請求項１０】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数６を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数６】
【請求項１１】
請求項９に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数７を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数７】
【請求項１２】
請求項１０に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数８を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数８】
【請求項１】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置であって、
秘密情報を入力し、これを分割して部分秘密情報を生成する分割器と、
オールゼロからなるダミー情報を生成するダミー情報生成器と、
乱数を生成する乱数生成器と、
素数と巡回群との性質を用いて、互いに重複しない乱数のペアにより排他的論理和演算を行う第１の排他的論理和演算器と、
素数と巡回群との性質を用いて、該ダミー情報を含む部分秘密情報のうち、互いに重複しない情報のペアにより排他的論理和演算を行う第２の排他的論理和演算器と、
個々の部分分散情報にレベルを割り当て、各レベルの閾値に応じて、排他的論理和演算を行うペアを決定するレベル割り当て手段と、
該レベル割り当て手段において決定されたペアについて、排他的論理和演算を行い、前記レベルに応じた重み付けがされた部分分散情報を出力する第３の排他的論理和演算器と、
該出力された部分分散情報を連結し、分散情報を出力する連結器と、
該出力された分散情報を管理者に送信する送信手段と、
を備えたことを特徴とする分散情報生成装置。
【請求項２】
前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベル０の部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋ−１個とを合せたｋ個の要素を組み合わせて構成し、レベルＬ≧１の部分分散情報について、乱数の排他的論理和演算のペアｋ−ｋＬ−１個のみを組み合わせて構成することを特徴とする請求項１に記載の分散情報生成装置。
【請求項３】
前記レベル割り当て手段が、レベルＬ (Ｌ＝０、１、・・・、ｍ)の分散情報のレベル閾値をｋＬとしたときに、レベルＬの部分分散情報について、部分秘密情報の排他的論理和演算のペア１個と乱数の排他的論理和演算のペアｋＬ−１個とを合せたｋＬ個の要素を組み合わせて構成することを特徴とする請求項１に記載の分散情報生成装置。
【請求項４】
請求項１から請求項３に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
分散情報を受信する受信手段と、
該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段と、
該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段と、
該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部と、
該復元された部分秘密情報を連結して秘密情報を出力する連結器と、
を備えたことを特徴とする秘密情報復元装置。
【請求項５】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ−１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数１を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
を有することを特徴とする分散情報生成方法。
【数１】
【請求項６】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法であって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数２を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
を有することを特徴とする分散情報生成方法。
【数２】
【請求項７】
請求項５に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数３を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
を有することを特徴とする秘密情報復元方法。
【数３】
【請求項８】
請求項６に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数４を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
を有することを特徴とする秘密情報復元方法。
【数４】
【請求項９】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数５を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数５】
【請求項１０】
排他的論理和演算を用いた（ｋ、ｎ）閾値秘密分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
秘密情報ｓをそれぞれｄビットの部分秘密情報ｎｐ−１個に分割する第１のステップと、
ダミー秘密情報ｓｎｐ−１∈{0}ｄを生成する第２のステップと、
（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
ｉ番目の管理者に送付される分散情報にレベルＬを割り当てるために、部分分散情報ｗ（ｉ、ｊ）を数６を用いて生成する第４のステップと、
ｗ（ｉ，0）、・・・、ｗ（ｉ，ｎｐ-２）を連結して分散情報ｗｉを生成し、管理者Ｐｉに配布する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数６】
【請求項１１】
請求項９に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数７を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数７】
【請求項１２】
請求項１０に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
それぞれの分散情報を部分分散情報に分割し、ｋ（ｎｐ−１）個の部分分散情報を得る第１のステップと、
前記部分分散情報の構成により、数８を満たすｋ（ｎｐ−１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ Ｉ]を変形し、行列[Ｍ´ Ｉ´]を得る第３のステップと、
該生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
すべての部分秘密情報を連結し、元の秘密情報ｓを復元する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数８】
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２８８３３８（Ｐ２００９−２８８３３８Ａ）
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願番号】特願２００８−１３８４５０（Ｐ２００８−１３８４５０）
【出願日】平成２０年５月２７日（２００８．５．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願日】平成２０年５月２７日（２００８．５．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]