(57)【要約】【課題】転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送するとともに、転送先ノード群内に機能不全のノードが存在したとしても秘密情報を復元する。【解決手段】分散情報生成装置が、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し、生成した第１の分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置から第１の分散情報を１つずつ入力し、入力した第１の分散情報を格納して、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。そして、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。このとき、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋・、ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐの関係にある。【選択図】図６
2012100140.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムであって、
前記分散情報生成装置が、
前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１の分散情報生成器と、
該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する配布手段と、
前記Ｌｉ個のノードがそれぞれ、
前記分散情報生成装置から第１の分散情報を１つずつ入力する入力手段と、
該入力した第１の分散情報を格納する格納手段と、
該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する分散情報生成器と、
該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する転送手段と、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送システム。
【請求項２】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムであって、
前記分散情報生成装置が、
前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１の分散情報生成器と、
該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する配布手段と、
前記Ｌｉ個のノードがそれぞれ、
前記分散情報生成装置から第１の分散情報を１つずつ入力する入力手段と、
該入力した第１の分散情報を格納する格納手段と、
該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する分散情報生成器と、
該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する転送手段と、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送システム。
【請求項３】
前記分散情報生成装置および分散情報生成器が、
有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択手段と、
該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算手段と、
を備えたことを特徴とする請求項１または請求項２に記載の分散情報転送システム。
【請求項４】
前記転送先ノード群ｊの各ノードが、
転送された第２の分散情報を受信する第１の受信手段と、
該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する算出手段と、
該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する送信手段と、
を備え、
前記秘密情報復元装置が、
前記加算値ａ（ｊ、ｌ）を受信する第２の受信手段と、
該受信した加算値ａ（ｊ、ｌ）を数１に入力して演算することにより前記秘密情報を復元する復元手段と、
を備えたことを特徴とする請求項１または請求項２に記載の分散情報転送システム。
【数１】
2012100140.tif 000005
ただし、Ｚ、・・・、Ｚｌ、・・・、・・・Ｚ＝０、・・・、ｌ、・・・、ｊ
【請求項５】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送方法であって、
前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、
前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、
前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、
前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、
前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、
前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送方法。
【請求項６】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムであって、
前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、
前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、
前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、
前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、
前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、
前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ≦ｐ、Ｙ＋ｔ＜Ｌｊ≦ｐであることを特徴とする分散情報転送方法。
【請求項７】
前記第１のステップおよび第５のステップが、
有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択ステップと、
該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算ステップと、
からなることを特徴とする請求項５または請求項６に記載の分散情報転送方法。
【請求項８】
前記転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信する第７のステップと、
前記転送先ノード群ｊの各ノードが、該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する第８のステップと、
前記転送先ノード群ｊの各ノードが、該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する第９のステップと、
前記秘密情報復元装置が、前記加算値ａ（ｊ、ｌ）を受信する第１０のステップと、
該受信した加算値ａ（ｊ、ｌ）を数２に入力して演算することにより前記秘密情報を復元する第１１のステップと、
を備えたことを特徴とする請求項５または請求項６に記載の分散情報転送方法。
【数２】
2012100140.tif 000006
ただし、Ｚ、・・・、Ｚｌ、・・・、・・・Ｚ＝０、・・・、ｌ、・・・、ｊ
【請求項９】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送方法をコンピュータに実行させるためのプログラムであって、
前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、
前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、
前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、
前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、
前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、
前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とするプログラム。
【請求項１０】
秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムをコンピュータに実行させるためのプログラムであって、
前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、
前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、
前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、
前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、
前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、
前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、
を備え、
前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐであることを特徴とするプログラム。
【請求項１１】
前記第１のステップおよび第５のステップが、
有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択ステップと、
該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算ステップと、
からなることを特徴とする請求項９または請求項１０に記載のプログラム。
【請求項１２】
前記転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信する第７のステップと、
前記転送先ノード群ｊの各ノードが、該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する第８のステップと、
前記転送先ノード群ｊの各ノードが、該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する第９のステップと、
前記秘密情報復元装置が、前記加算値ａ（ｊ、ｌ）を受信する第１０のステップと、
該受信した加算値ａ（ｊ、ｌ）を数３に入力して演算することにより前記秘密情報を復元する第１１のステップと、
を備えたことを特徴とする請求項９または請求項１０に記載のプログラム。
【数３】
2012100140.tif 000007
ただし、Ｚ、・・・、Ｚｌ、・・・、・・・Ｚ＝０、・・・、ｌ、・・・、ｊ
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全ノードペア間にフルメッシュのセキュアな通信路が存在するネットワークにおいて、秘密情報を複数のノード群に分散して保持する情報管理方法を対象とし、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送するとともに、転送先ノード群内に機能不全のノードが存在したとしても秘密情報を復元できる分散情報転送システム、分散情報転送方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。例えば、秘密情報の管理において、秘密情報を格納したノード（サーバなど）が壊れてしまうと、秘密情報が破損される。秘密情報の破損に耐性をもたせるためには、秘密情報の複製を複数のノードに格納すればよいが、秘密情報を格納したノードの数が多くなると、敵に秘密情報が漏えいする危険性が高くなる。秘密情報の複製を複数用意する場合、１つの複製からは、秘密情報が漏えいしないようにすることが望ましい。
【０００３】
このようなことから、非特許文献１に示されるような（ｔ、ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｔ、ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｔ個の分散情報が集まれば、復元できることを意味する。つまり、各分散情報をｎ台の異なるノードに持たせることにより、それらのノードのうちｔ−１台が結託して秘密を盗もうとしてもその秘密情報を守ることができる。また、ｎ−ｔ個以下の分散情報やそれを保有しているノードが破損したとしても、元の秘密情報は復元できるという効果が期待できる。
【０００４】
そのため、（ｔ、ｎ）閾値秘密分散法を用いることにより、ある秘密情報の複数の分散情報が転送元ノード群に属する各ノードに格納されているとき、転送元ノード群の各ノードが、ネットワークを介して、転送先ノード群のノードと通信を行い、転送先ノード群に属するノードへそのまま分散情報を転送することも考えられる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，  ｖｏｌ．２２  ｎｏ．１１  ｐｐ．６１２−６１３，  １９７９．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、転送元ノード群および転送先ノード群にそれぞれ敵が存在し、互いに結託する状況下において、秘密情報が漏えいする危険性がある。つまり、図１２に示すように、ノード群 ｉ およびノード群 ｊ のノード１ 台が敵に操作されている場合、（２、３） 閾値秘密分散法を用いて、ある秘密情報の３つの分散情報がノード群ｉの各ノードに格納されており、ノード群ｉの各ノードが、ネットワークを介して、ノード群ｊのそれぞれに対応したノードに分散情報をそのまま転送すると、敵は、２つの分散情報を知ることができるために、秘密情報が漏洩してしまうという問題がある。また、上記例の場合、ノード群ｊの内、２台のノードが故障すると、秘密情報が復元できなくなるという問題もある。
【０００７】
そこで、本発明は、上述の課題に鑑みてなされたものであり、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送するとともに、転送先ノード群内に機能不全のノードが存在したとしても秘密情報を復元できる分散情報転送システム、分散情報転送方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００９】
（１）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置（例えば、図１の分散情報生成装置１００に相当）と、Ｌｉ個のノードからなる情報転送元ノード群ｉ（例えば、図１のノード群ｉ２００に相当）と、Ｌｊ個のノードからなる転送先ノード群ｊ（例えば、図１のノード群ｊ３００に相当）と、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置（例えば、図８の秘密情報復元装置５００に相当）とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワーク（例えば、図１のネットワーク４００に相当）を介して、分散情報を転送する分散情報転送システムであって、前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１の分散情報生成器（例えば、図２の分散情報生成器１１０に相当）と、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する配布手段（例えば、図２の配布部１２０に相当）と、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する入力手段（例えば、図３の第１の分散情報入力部２１０に相当）と、該入力した第１の分散情報を格納する格納手段（例えば、図３の第１の分散情報格納部２２０に相当）と、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する分散情報生成器（例えば、図３の分散情報生成器２３０に相当）と、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する転送手段（例えば、図３の転送部２４０に相当）と、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送システムを提案している。
【００１０】
この発明によれば、分散情報生成装置は、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する。配布手段は、生成した分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードのそれぞれの入力手段は、転送先ノード群ｊのうちから配布された分散情報を入力する。格納手段は、入力した分散情報を格納する。分散情報生成器は、格納した分散情報から（ｋ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。転送手段は、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。そして、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｋ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐの関係にある。したがって、例えば、情報転送元ノード群ｉおよび転送先ノード群ｊのノード数Ｌｉ＝Ｌｊ＝３である場合に、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、情報転送元ノード群ｉおよび転送先ノード群ｊにそれぞれ１個ずつ不正者が操作するノードが存在しても、３個からなる第１の分散情報のうち、１個しか得られないため、秘密情報を復元することができない。つまり、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送することができる。
【００１１】
（２）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムであって、前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１の分散情報生成器と、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する配布手段と、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する入力手段と、該入力した第１の分散情報を格納する格納手段と、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する分散情報生成器と、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する転送手段と、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送システムを提案している。
【００１２】
この発明によれば、分散情報生成装置は、秘密情報から（ｋ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成する。配布手段は、生成した分散情報をＬｉ個のノードにそれぞれに１つずつ配布する。一方、Ｌｉ個のノードそれぞれの入力手段は、分散情報生成装置から配布された分散情報を入力する。格納手段は、入力した分散情報を格納する。分散情報生成器は、格納した分散情報から（ｋ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。転送手段は、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。そして、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｋ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐである。したがって、例えば、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、転送先ノード群ｊのうち２つのノードが正常であれば、その他のノードが機能不全であっても、秘密情報を復元することができる。つまり、転送先ノード群内に機能不全のノードが存在したとしても必要最低限のノードが正常であれば、秘密情報を復元できる。
【００１３】
（３）本発明は、（１）または（２）の分散情報転送システムについて、前記分散情報生成装置および分散情報生成器が、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択手段（例えば、図４の選択部１１１に相当）と、該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算手段（例えば、図４の演算部１１２に相当）と、を備えたことを特徴とする分散情報転送システムを提案している。
【００１４】
この発明によれば、選択手段は、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する。演算手段は、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する。つまり、Ｓｈａｍｉｒの提案する（ｔ、ｎ）閾値秘密分散法により、分散情報を生成できるため、特別な手法を用いることなく、簡易に分散情報を生成することができる。
【００１５】
（４）本発明は、（１）または（２）の分散情報転送システムについて、前記転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信する第１の受信手段（例えば、図９の第２の分散情報入力部３１０に相当）と、該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する算出手段（例えば、図９の第２の加算値算出部３２０に相当）と、該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する送信手段（例えば、図９の加算値送信部３３０に相当）と、を備え、前記秘密情報復元装置が、前記加算値ａ（ｊ、ｌ）を受信する第２の受信手段（例えば、図１０の加算値受信部５１０に相当）と、該受信した加算値ａ（ｊ、ｌ）を数１に入力して演算することにより前記秘密情報を復元する復元手段（例えば、図１０の秘密情報復元部５２０に相当）と、を備えたことを特徴とする分散情報転送システムを提案している。
【００１６】
この発明によれば、転送先ノード群ｊの各ノードの第１の受信手段は、転送された第２の分散情報を受信する。算出手段は、受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する。送信手段は、加算した加算値ａ（ｊ、ｌ）を秘密情報復元装置に送信する。秘密情報復元装置の第２の受信手段は、加算値ａ（ｊ、ｌ）を受信する。復元手段は、受信した加算値ａ（ｊ、ｌ）を数１に入力して演算することにより秘密情報を復元する。したがって、転送先ノード群ｊの各ノードが算出した加算値ａ（ｊ、ｌ）を所定の演算式に入力することにより、直接、秘密情報を復元することができる。
【００１７】
（５）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送方法であって、前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップ（例えば、図６のステップＳ１０１に相当）と、前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップ（例えば、図６のステップＳ１０２に相当）と、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップ（例えば、図６のステップＳ１０３に相当）と、前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップ（例えば、図６のステップＳ１０４に相当）と、前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップ（例えば、図６のステップＳ１０５に相当）と、前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップ（例えば、図６のステップＳ１０６に相当）と、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送方法を提案している。
【００１８】
この発明によれば、分散情報生成装置が、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し、生成した第１の分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置から第１の分散情報を１つずつ入力し、入力した第１の分散情報を格納して、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。そして、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。このとき、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐの関係にある。したがって、例えば、情報転送元ノード群ｉおよび転送先ノード群ｊのノード数Ｌｉ＝Ｌｊ＝３である場合に、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、情報転送元ノード群ｉおよび転送先ノード群ｊにそれぞれ１個ずつ不正者が操作するノードが存在しても、３個からなる第１の分散情報のうち、１個しか得られないため、秘密情報を復元することができない。つまり、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送することができる。
【００１９】
（６）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムであって、前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップ（例えば、図１１のステップＳ３０１に相当）と、前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップ（例えば、図１１のステップＳ３０２に相当）と、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップ（例えば、図１１のステップＳ３０３に相当）と、前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップ（例えば、図１１のステップＳ３０４に相当）と、前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップ（例えば、図１１のステップＳ３０５に相当）と、前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップ（例えば、図１１のステップＳ３０６に相当）と、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐであることを特徴とする分散情報転送方法を提案している。
【００２０】
この発明によれば、分散情報生成装置が、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し、生成した第１の分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置から第１の分散情報を１つずつ入力し、入力した第１の分散情報を格納して、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。そして、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。このとき、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐの関係にある。したがって、例えば、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、転送先ノード群ｊのうち２つのノードが正常であれば、その他のノードが機能不全であっても、秘密情報を復元することができる。つまり、転送先ノード群内に機能不全のノードが存在したとしても必要最低限のノードが正常であれば、秘密情報を復元できる。
【００２１】
（７）本発明は、（５）または（６）の分散情報転送方法について、前記第１のステップおよび第５のステップが、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択ステップ（例えば、図７のステップＳ２０１に相当）と、該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算ステップ（例えば、図７のステップＳ２０２に相当）と、からなることを特徴とする分散情報転送方法を提案している。
【００２２】
この発明によれば、第１のステップおよび第５のステップが、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択し、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する。つまり、Ｓｈａｍｉｒの提案する（ｔ、ｎ）閾値秘密分散法により、分散情報を生成できるため、特別な手法を用いることなく、簡易に分散情報を生成することができる。
【００２３】
（８）本発明は、（５）または（６）の分散情報転送方法について、前記転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信する第７のステップ（例えば、図１１のステップＳ３０７に相当）と、前記転送先ノード群ｊの各ノードが、該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する第８のステップ（例えば、図１１のステップＳ３０８に相当）と、前記転送先ノード群ｊの各ノードが、該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する第９のステップ（例えば、図１１のステップＳ３０９に相当）と、前記秘密情報復元装置が、前記加算値ａ（ｊ、ｌ）を受信する第１０のステップ（例えば、図１１のステップＳ３１０に相当）と、該受信した加算値ａ（ｊ、ｌ）を数２に入力して演算することにより前記秘密情報を復元する第１１のステップ（例えば、図１１のステップＳ３１１に相当）と、を備えたことを特徴とする分散情報転送方法を提案している。
【００２４】
この発明によれば、転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信し、受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出して、加算した加算値ａ（ｊ、ｌ）を秘密情報復元装置に送信する。そして、秘密情報復元装置が、加算値ａ（ｊ、ｌ）を受信し、受信した加算値ａ（ｊ、ｌ）を数２に入力して演算することにより前記秘密情報を復元する。したがって、転送先ノード群ｊの各ノードが算出した加算値ａ（ｊ、ｌ）を所定の演算式に入力することにより、直接、秘密情報を復元することができる。
【００２５】
（９）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送方法をコンピュータに実行させるためのプログラムであって、
前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐであることを特徴とするプログラムを提案している。
【００２６】
この発明によれば、分散情報生成装置が、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し、生成した第１の分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置から第１の分散情報を１つずつ入力し、入力した第１の分散情報を格納して、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。そして、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。このとき、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、攻撃者が操作するノードの数をＸと想定したときに、ｔ≧２、Ｘ＋ｔ＜Ｌｉ＜ｐ、Ｘ＋ｔ＜Ｌｊ＜ｐの関係にある。したがって、例えば、情報転送元ノード群ｉおよび転送先ノード群ｊのノード数Ｌｉ＝Ｌｊ＝３である場合に、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、情報転送元ノード群ｉおよび転送先ノード群ｊにそれぞれ１個ずつ不正者が操作するノードが存在しても、３個からなる第１の分散情報のうち、１個しか得られないため、秘密情報を復元することができない。つまり、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送することができる。
【００２７】
（１０）本発明は、秘密情報を保持し、該秘密情報から第１の分散情報を生成する分散情報生成装置と、Ｌｉ個のノードからなる情報転送元ノード群ｉと、Ｌｊ個のノードからなる転送先ノード群ｊと、該Ｌｊ個のノードに転送された第２の分散情報から前記秘密情報を復元する秘密情報復元装置とからなり、前記情報転送元ノード群ｉと転送先ノード群ｊとがフルメッシュのセキュアな通信路により構成されるネットワークを介して、分散情報を転送する分散情報転送システムをコンピュータに実行させるためのプログラムであって、前記分散情報生成装置が、前記秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる前記第１の分散情報を生成する第１のステップと、前記分散情報生成装置が、該生成した第１の分散情報を前記Ｌｉ個のノードにそれぞれ配布する第２のステップと、前記Ｌｉ個のノードがそれぞれ、前記分散情報生成装置から第１の分散情報を１つずつ入力する第３のステップと、前記Ｌｉ個のノードがそれぞれ、該入力した第１の分散情報を格納する第４のステップと、前記Ｌｉ個のノードがそれぞれ、該格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる前記第２の分散情報を生成する第５のステップと、前記Ｌｉ個のノードがそれぞれ、該生成した第２の分散情報を前記転送先のＬｊ個のノードに１つずつ転送する第６のステップと、を備え、前記閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐであることを特徴とするプログラムを提案している。
【００２８】
この発明によれば、分散情報生成装置が、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し、生成した第１の分散情報をＬｉ個のノードにそれぞれ配布する。一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置から第１の分散情報を１つずつ入力し、入力した第１の分散情報を格納して、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。そして、生成した第２の分散情報を転送先のＬｊ個のノードに１つずつ転送する。このとき、閾値秘密分散法の演算が行われる有限体をＧ（ｐ）とし、転送先ノード群ｊのうち機能不全のノードの数をＹと想定したときに、ｔ≧２、Ｙ＋ｔ＜Ｌｉ＜ｐ、Ｙ＋ｔ＜Ｌｊ＜ｐの関係にある。したがって、例えば、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、転送先ノード群ｊのうち２つのノードが正常であれば、その他のノードが機能不全であっても、秘密情報を復元することができる。つまり、転送先ノード群内に機能不全のノードが存在したとしても必要最低限のノードが正常であれば、秘密情報を復元できる。
【００２９】
（１１）本発明は、（９）または（１０）のプログラムについて、前記第１のステップおよび第５のステップが、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する選択ステップと、該選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する演算ステップと、からなることを特徴とするプログラムを提案している。
【００３０】
この発明によれば、第１のステップおよび第５のステップが、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択し、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する。つまり、Ｓｈａｍｉｒの提案する（ｔ、ｎ）閾値秘密分散法により、分散情報を生成できるため、特別な手法を用いることなく、簡易に分散情報を生成することができる。
【００３１】
（１２）本発明は、（９）または（１０）のプログラムについて、前記転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信する第７のステップと、前記転送先ノード群ｊの各ノードが、該受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出する第８のステップと、前記転送先ノード群ｊの各ノードが、該加算した加算値ａ（ｊ、ｌ）を前記秘密情報復元装置に送信する第９のステップと、前記秘密情報復元装置が、前記加算値ａ（ｊ、ｌ）を受信する第１０のステップと、該受信した加算値ａ（ｊ、ｌ）を数３に入力して演算することにより前記秘密情報を復元する第１１のステップと、を備えたことを特徴とするプログラムを提案している。
【００３２】
この発明によれば、転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信し、受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出して、加算した加算値ａ（ｊ、ｌ）を秘密情報復元装置に送信する。そして、秘密情報復元装置が、加算値ａ（ｊ、ｌ）を受信し、受信した加算値ａ（ｊ、ｌ）を数２に入力して演算することにより前記秘密情報を復元する。したがって、転送先ノード群ｊの各ノードが算出した加算値ａ（ｊ、ｌ）を所定の演算式に入力することにより、直接、秘密情報を復元することができる。
【発明の効果】
【００３３】
本発明によれば、秘密情報を複数ノード群に分散して保持する情報管理方法を対象とし、転送元ノード群が保持する秘密情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送することができるという効果がある。また、転送元ノード群および転送先ノード群に敵がいる場合、秘密情報の漏えいを防ぐことができるとともに、ネットワークの動的な変化（転送先ノード群のノード追加・ネットワークの到達性欠如を含む転送先ノード群の故障・転送元ノード群と転送先ノード群のノード数の違い）にも対応できるという効果がある。また、秘密情報の復元においては、１回の演算で秘密情報を復元できるため、演算負荷を軽減することができるという効果がある。
【図面の簡単な説明】
【００３４】
【図１】本発明の第１の実施形態に係る分散情報転送システムの構成を示す図である。
【図２】本発明の第１の実施形態に係る分散情報生成装置の構成を示す図である。
【図３】本発明の第１の実施形態に係る転送元ノード群の各ノードの構成を示す図である。
【図４】本発明の第１の実施形態に係る分散情報生成器の構成を示す図である。
【図５】本発明の第１の実施形態の他の例に係る転送元および転送先のノード構成を示す図である。
【図６】本発明の第１の実施形態に係る分散情報転送システムの処理を示す図である。
【図７】本発明の第１の実施形態に係る分散情報生成器の処理を示す図である。
【図８】本発明の第２の実施形態に係る分散情報転送システムの構成を示す図である。
【図９】本発明の第２の実施形態に係る転送先ノード群の各ノードの構成を示す図である。
【図１０】本発明の第２の実施形態に係る秘密情報復元装置の構成を示す図である。
【図１１】本発明の第２の実施形態に係る分散情報転送システムの処理を示す図である。
【図１２】従来例を説明するための図である。
【発明を実施するための形態】
【００３５】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３６】
＜第１の実施形態＞
以下、図１から図９を用いて、本発明の第１の実施形態に係る分散情報転送システムについて詳細に説明する。
【００３７】
＜分散情報転送システムの構成＞
図１を用いて、本実施形態に係る分散情報転送システムの構成について説明する。
本実施形態に係る分散情報転送システムは、図１に示すように、分散情報生成装置１００と、ノード群ｉ２００と、ノード群ｊ３００と、ネットワーク４００とから構成されている。なお、本実施形態においては、ノード群ｉ２００とノード群ｊ３００とを構成するノード数がそれぞれ３個の場合を例にとって、説明する。
【００３８】
ここで、以下において、Ｌiは、ノードｉを代表ノードとしたノード群ｉのメンバー数を、Ｃiは、ノード群ｉのメンバーであるノードのＩＤの集合を示す。また、ノード群ｉは、ノード群ｉのメンバー数Ｌi、各メンバーｌのＩＰアドレス、トランジットポート番号、ノード群ｉ内における任意のメンバー間の共有鍵を保持し、ノード群ｊは、ノード群ｊのメンバー数Ｌｊ、各メンバーｌ´のＩＰアドレス、トランジットポート番号、ノード群ｊ内における任意のメンバー間の共有鍵を保持している。
【００３９】
分散情報生成装置１００は、秘密情報を保持し、この秘密情報から第１の分散情報を生成して、これをノード群ｉ２００内の各ノードに配布する。ノード群ｉ２００の各ノードは、分散情報生成装置１００から第１の分散情報を入力し、この第１の分散情報から第２の分散情報を生成して、ノード群ｉ２００の各ノードが、第２の分散情報をノード群ｊ３００内の各ノードに１つずつ転送する。
【００４０】
ノード群ｊ３００は、転送されたそれぞれの第２の分散情報を受信する。なお、本実施形態においては、ノード群ｉ２００内のノードＣi3とノード群ｊ３００内のノードＣj3が不正者に操作されている場合を例にとって説明する。ネットワーク４００は、フルメッシュのセキュアな通信路により構成されている。
【００４１】
＜分散情報生成装置の構成＞
図２を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
本実施形態に係る分散情報生成装置は、図２に示すように、分散情報生成器１１０と、配布部１２０とから構成されている。
【００４２】
分散情報生成器１１０は、秘密情報から第１の分散情報を生成する。配布部１２０は、分散情報生成器１１０が生成した第１の分散情報をノード群ｉ２００内の各ノードに配布する。なお、分散情報生成器１１０による分散情報の生成方法は、Ｓｈａｍｉｒが提唱する（ｔ、ｎ）閾値秘密分散法に準じたものであり、その詳細については、後述する。
【００４３】
＜ノード群ｉの各ノードの構成＞
図３を用いて、本実施形態に係るノード群ｉの各ノードの構成について説明する。
本実施形態に係るノード群ｉの各ノードは、図３に示すように、第１の分散情報入力部２１０と、分散情報格納部２２０と、分散情報生成部２３０と、分散情報転送部２４０とから構成されている。
【００４４】
第１の分散情報入力部２１０は、分散情報生成装置１００から第１の分散情報を１つ入力する。分散情報格納部２２０は、入力した第１の分散情報を格納する。分散情報生成部２３０は、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成する。分散情報転送部２４０は、生成した第２の分散情報を転送先のノード群ｊ３００のＬｊ個のノードに１つずつ転送する。なお、分散情報生成部２３０による分散情報の生成方法は、Ｓｈａｍｉｒが提唱する（ｔ、ｎ）閾値秘密分散法に準じたものであり、その詳細については、後述する。
【００４５】
＜分散情報生成装置および分散情報生成器の構成＞
図４を用いて、本実施形態に係る分散情報生成装置および分散情報生成器の構成について説明する。本実施形態に係る分散情報生成装置および分散情報生成器は、図４に示すように、選択部１１１と、演算部１１２とから構成されている。
【００４６】
選択部１１１は、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択する。演算部１１２は、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する。ここで、本実施形態においては、攻撃者が操作するノードが２であるため、ｔ≧２、２＋ｔ＜Ｌｉ＜ｐ、２＋ｔ＜Ｌｊ＜ｐの関係となる。
【００４７】
なお、本実施形態においては、ノード群ｉ２００とノード群ｊ３００とを構成するノード数がそれぞれ３個で同数の場合を示したが、図５に示すように、ノード群ｉ２００のノード数が４、ノード群ｊ３００のノード数が３といったノード数が同数でない場合にも適用ができる。ここで、図５の左の図は、ノード群ｉ２００の４つのノードに分散情報生成装置１００から第１の分散情報が配布されたときの様子を示し、右の図は、ノード群ｊ３００の３つのノードが転送された複数の分散情報を１つの分散情報に変換して保持する様子を示している。
【００４８】
＜分散情報転送システムの処理＞
図５および図６を用いて、本実施形態に係る分散情報転送システムの処理について説明する。
【００４９】
まず、分散情報生成装置１００は、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し（ステップＳ１０１）、生成した第１の分散情報をノード群ｉのＬｉ個のノードにそれぞれ配布する（ステップＳ１０２）。
【００５０】
一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置１００から第１の分散情報を１つずつ入力し（ステップＳ１０３）、入力した第１の分散情報を格納する（ステップＳ１０４）。
【００５１】
Ｌｉ個のノードがそれぞれ、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成し（ステップＳ１０５）、生成した第２の分散情報をノード群ｊのＬｊ個のノードに１つずつ転送する（ステップＳ１０６）。
【００５２】
また、分散情報生成装置１００および分散情報生成器１１０は、図６に示すような処理を行う。具体的には、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択し（ステップＳ２０１）、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する（ステップＳ２０２）。
【００５３】
なお、本実施形態においては、攻撃者が操作するノードが２であるため、ｔ≧２、２＋ｔ＜Ｌｉ＜ｐ、２＋ｔ＜Ｌｊ＜ｐの関係となる。
【００５４】
以上、説明したように、本実施形態によれば、例えば、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、情報転送元ノード群ｉおよび転送先ノード群ｊにそれぞれ１個ずつ不正者が操作するノードが存在しても、３個からなる第１の分散情報のうち、１個しか得られないため、秘密情報を復元することができない。つまり、転送元ノード群が保持する分散情報を、情報理論的な安全性と秘密情報の復元性を保ちつつ、ネットワークを介して転送先ノード群へ分配・転送することができる。
【００５５】
＜第２の実施形態＞
以下、図８から図１１を用いて、本発明の第２の実施形態に係る分散情報転送システムについて詳細に説明する。
【００５６】
＜分散情報転送システムの構成＞
図８を用いて、本実施形態に係る分散情報転送システムの構成について説明する。
本実施形態に係る分散情報転送システムは、図８に示すように、分散情報生成装置１００と、ノード群ｉ２００と、ノード群ｊ３００と、ネットワーク４００と、秘密情報復元装置５００とから構成されている。なお、第１の実施形態と同様の符号を付す構成要素については、同一の機能を有することからその詳細な説明は省略する。なお、本実施形態においては、ノード群ｉ２００とノード群ｊ３００とを構成するノード数がそれぞれ５個の場合を例にとって、説明する。
【００５７】
ここで、以下において、Ｌiは、ノードｉを代表ノードとしたノード群ｉのメンバー数を、Ｃiは、ノード群ｉのメンバーであるノードのＩＤの集合を示す。また、ノード群ｉは、ノード群ｉのメンバー数Ｌi、各メンバーｌのＩＰアドレス、トランジットポート番号、ノード群ｉ内における任意のメンバー間の共有鍵を保持し、ノード群ｊは、ノード群ｊのメンバー数Ｌｊ、各メンバーｌ´のＩＰアドレス、トランジットポート番号、ノード群ｊ内における任意のメンバー間の共有鍵を保持している。
【００５８】
ノード群ｊの各ノードは、図９に示すように、第２の分散情報入力部３１０と、加算値算出部３２０と、加算値送信部３３０とから構成されている。なお、本実施形態においては、ノード群ｊ３００内のノードＣｊ３からＣｊ５が機能不全である場合を例にとって説明する。
【００５９】
第２の分散情報入力部３１０は、ノード群ｉの各ノードから第２の分散情報を入力する。加算値算出部３２０は、入力したＬi個の第２の分散情報ａ（ｉ、１、ｌ）、・・・、ａ（ｉ、Ｌｉ、ｌ）を以下の数１により加算して、加算値ａ（ｊ、ｌ）を算出する。加算値送信部３３０は、算出した加算値ａ（ｊ、ｌ）を秘密情報復元装置５００に送信する。
【数１】
2012100140.tif 000003
【００６０】
秘密情報復元装置５００は、図１０に示すように、加算値受信部５１０と、秘密情報復元部５２０とから構成されている。加算値受信部５１０は、ノード群ｊの各ノードから加算値ａ（ｊ、ｌ）を受信する。秘密情報復元部５２０は、受信した加算値ａ（ｊ、ｌ）を数２に入力して演算することにより秘密情報を復元する。これにより、１回の演算で秘密情報を復元できるため、演算負荷を軽減することができる。
【００６１】
【数２】
2012100140.tif 000004
ただし、Ｚ、・・・、Ｚｌ、・・・、・・・Ｚ＝０、・・・、ｌ、・・・、ｊ
【００６２】
＜分散情報転送システムの処理＞
図１１を用いて、本実施形態に係る分散情報転送システムの処理について説明する。
【００６３】
まず、分散情報生成装置１００は、秘密情報から（ｔ、Ｌｉ）閾値秘密分散法によりＬｉ個からなる第１の分散情報を生成し（ステップＳ３０１）、生成した第１の分散情報をノード群ｉのＬｉ個のノードにそれぞれ配布する（ステップＳ３０２）。
【００６４】
一方、Ｌｉ個のノードがそれぞれ、分散情報生成装置１００から第１の分散情報を１つずつ入力し（ステップＳ３０３）、入力した第１の分散情報を格納する（ステップＳ３０４）。
【００６５】
Ｌｉ個のノードがそれぞれ、格納した分散情報から（ｔ、Ｌｊ）閾値秘密分散法によりＬｊ個からなる第２の分散情報を生成し（ステップＳ３０５）、生成した第２の分散情報をノード群ｊのＬｊ個のノードに１つずつ転送する（ステップＳ３０６）。
【００６６】
転送先ノード群ｊの各ノードが、転送された第２の分散情報を受信し（ステップＳ３０７）、受信した第２の分散情報にＬｉに基づくベクトルに応じた重み係数を乗じ、さらに、これらすべて加算した加算値ａ（ｊ、ｌ）を算出して（ステップＳ３０８）、加算した加算値ａ（ｊ、ｌ）を秘密情報復元装置に送信する（ステップＳ３０９）。
【００６７】
そして、秘密情報復元装置が、加算値ａ（ｊ、ｌ）を受信し（ステップＳ３１０）、受信した加算値ａ（ｊ、ｌ）を演算することにより秘密情報を復元する（ステップＳ３１１）。
【００６８】
また、分散情報生成装置１００および分散情報生成器１１０は、図６に示すような処理を行う。具体的には、有限体ＧＦ（ｐ）上の秘密情報ａ∈｛０、・・・、ｐ−１｝に関し、各次数ｋ＝１、・・・、ｔ−１について、有限体ＧＦ（ｐ）からランダムに係数ａｋを選択し（ステップＳ２０１）、選択した係数に基づいて、有限体ＧＦ（ｐ）上のｔ−１次多項式Ａ（ｚ）＝ａｔ−１ｚｔ−１＋・・・＋ａ１ｚ＋ａを定め、分散情報を演算する（ステップＳ２０２）。
【００６９】
なお、本実施形態においては、機能不全のノードが３であるため、ｔ≧２、３＋ｔ＜Ｌｉ≦ｐ、３＋ｔ＜Ｌｊ≦ｐの関係となる。
【００７０】
以上、説明したように、本実施形態によれば、例えば、（２、３）閾値秘密分散法により、第１の分散情報を生成し、さらに、（２、５）閾値秘密分散法により、第２の分散情報を生成した場合、転送先ノード群ｊのうち２つのノードが正常であれば、その他のノードが機能不全であっても、秘密情報を復元することができる。つまり、転送先ノード群内に機能不全のノードが存在したとしても必要最低限のノードが正常であれば、秘密情報を復元できる。また、秘密情報の復元においては、１回の演算で秘密情報を復元できるため、演算負荷を軽減することができる。
【００７１】
なお、分散情報転送システムの処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置、ノード群ｉの各ノード、ノード群ｊの各ノードおよび秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報転送システムを実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７２】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７３】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００７４】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７５】
１００；分散情報生成装置
１１０；分散情報生成器
１１１；選択部
１１２；演算部
１２０；配布部
２００；ノード群ｉ
２１０；第１の分散情報入力部
２２０；分散情報格納部
２３０；分散情報生成部
２４０；分散情報転送部
３００；ノード群ｊ
３１０；第２の分散情報入力部
３２０；加算値算出部
３３０；加算値送信部
４００；ネットワーク
５００；秘密情報復元装置
５１０；加算値受信部
５２０；秘密情報復元部
【図２】
2012100140.tif 000008
【図３】
2012100140.tif 000009
【図４】
2012100140.tif 000010
【図６】
2012100140.tif 000011
【図７】
2012100140.tif 000012
【図９】
2012100140.tif 000013
【図１０】
2012100140.tif 000014
【図１１】
2012100140.tif 000015
【図１】
2012100140.tif 000016
【図５】
2012100140.tif 000017
【図８】
2012100140.tif 000018
【図１２】
2012100140.tif 000019