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