秘密情報分散装置及び秘密情報復元装置及び方法及びプログラム
【課題】安全かつ効率的な秘密情報の分散を可能にする。
【解決手段】本発明は、秘密情報分散装置側で秘密情報を分散条件に基づいて複数個に分割し、分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、複数個の係数情報を係数とする多項式関数によって任意の個数の元の秘密情報より小さい分散情報を算出し、出力する。また、秘密情報復元装置側で、秘密情報の復元に必要な個数の分散情報群を取得し、復元条件に基づいて、複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する。
【解決手段】本発明は、秘密情報分散装置側で秘密情報を分散条件に基づいて複数個に分割し、分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、複数個の係数情報を係数とする多項式関数によって任意の個数の元の秘密情報より小さい分散情報を算出し、出力する。また、秘密情報復元装置側で、秘密情報の復元に必要な個数の分散情報群を取得し、復元条件に基づいて、複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムに係り、特に、特に、パスワードや個人情報などの秘密情報を複数の情報群に分散符号化し、これらのうち、幾つか以上の分散された情報により元の秘密情報を復元可能とする秘密分散法を用いたセキュリティ技術における、秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ネットワーク上でパスワードや個人情報、暗号鍵情報といった各種情報のセキュリティ（安全性）を保つために、暗号技術が用いられる。この際、ユーザ（利用者）の認証に用いられるパスワードや個人情報、共通鍵暗号に用いられる共通鍵や公開鍵暗号に用いる秘密鍵といった秘密情報の保管に関して、秘密情報の紛失や破壊、漏洩や盗難といった恐れがあり、特に、単一の箇所に保管する場合などは、秘密情報の紛失や破壊、複数の箇所に保管する場合などは秘密情報の漏洩や盗難の可能性が高くなってしまうという問題がある。
【０００３】
これらの問題を解決し、各秘密情報を安全に保管する方法のひとつとして、秘密分散法がある。
【０００４】
秘密分散法は、元の秘密情報を複数の情報に分散して複数の箇所に保管し、この分散された情報（以下、分散情報）を全て、あるいは幾つか合わせることにより、元の秘密情報を復元可能とする方法である。
【０００５】
秘密分散法の実現方法のひとつとして（ｋ，ｎ）閾値秘密分散法がある。これは、分散情報を配布する数である２以上の整数の分散数ｎと、秘密情報Ｓの復元に必要な分散情報の最低数である２以上ｎ以下の整数の閾値ｋから、秘密情報Ｓを定数項とする（ｋ−１）次の多項式ｆ（ｘ）を、
ｆ（ｘ）＝Ｓ＋Ｒ１ｘ＋…Ｒｋ−１ｘｋ−１（mod P）
（Ｒ１，…，Ｒｋ−１：乱数、Ｐ：素数）
として作成し、元の秘密情報Ｓを所有あるいは、預託により分配する秘密情報分配者は、分配情報を保管する各分散情報保持者ｉ（ｉ＝１，２，…，ｎ）に対して、分散情報Ｗｉ＝ｆ（ｉ）を分配するものである。
【０００６】
この（ｋ，ｎ）閾値秘密分散法は、ｎ個の分散情報の内、任意のｋ個の分散情報がそろえば、ｆ（ｘ）に関する連立方程式を解くことにより元の秘密情報Ｓを復元できるが、任意の（ｋ−１）個までの分散情報が揃ってもｆ（ｘ）に関する連立方程式を解くことはできないため、元の秘密情報Ｓを復元できないという特徴を持つ。従って、（ｎ−ｋ）個までの分散情報が紛失や破壊により損なわれても元の秘密情報Ｓが復元可能であり、（k−１）個までの分散情報が漏洩や盗難により得られても元の秘密情報Ｓは復元できないという、秘密情報を安全に保管する方法が実現できる。但し、個々に生成される分散情報Ｗｉの大きさは秘密情報Ｓの大きさに等しく、分散効率が悪いことが知られている（例えば、非特許文献１参照）。
【０００７】
さらに、（ｋ，ｎ）閾値秘密分散法の拡張として、（ｄ，ｋ，ｎ）閾値秘密分散法、別名ランプ型秘密分散法がある。これは、分散情報を配布する数である２以上の整数の分散数ｎと、秘密情報Ｓの完全な復元に必要な分散情報の最低数である２位以上ｎ以下の整数の閾値ｋと、閾値ｋに対して秘密情報Ｓの部分的な復元を許容する分散情報の不足数を決定する２以上ｋ以下の整数の分散数ｄから、秘密情報Ｓを、Ｓ１，Ｓ２，…，Ｓｄに分割し、これらの分割した秘密情報（以下、分割情報）を定数項とする（ｋ−１）次の多項式ｆ（ｘ）を、
ｆ（ｘ）＝Ｓ１＋Ｓ２ｘ＋…＋Ｓｄｘｄ−１＋Ｒ１ｘｄ＋…＋Ｒｋ−ｄｘｋ−１（mod Ｐ）
（Ｒ１，…，Ｒｋ−ｄ：乱数、Ｐ：素数）
として作成し、元の秘密情報Ｓを所有あるいは預託による分配する秘密情報分配者は、分散情報を保管する各分散情報保持者ｉ（ｉ＝１，２，…，ｎ）に対して、分散情報Ｗｉ＝ｆ（ｉ）を算出して分配するものである。
【０００８】
この（ｄ，ｋ，ｎ）閾値秘密分散法は、（ｋ，ｎ）閾値秘密分散法と同様に、ｎ個の分散情報の内、任意のｋ個の分散情報が揃えば、ｆ（ｘ）に関する連立方程式を解くことにより元の秘密情報Ｓを復元できるが、任意の（ｋ−ｄ）個までの分散情報が揃ってもｆ（ｘ）に関する連立方程式を解くことはできないため、元の秘密情報Ｓは復元できないという特徴をもつ。また、ｄ個に分割した秘密情報Ｓ１，Ｓ２，…，Ｓｄを用いるため、算出した分散情報Ｗｉの大きさが、元の秘密情報Ｓに対してｄ分の１で済むため、（ｋ，ｎ）閾値秘密分散法に比べて、分散効率がよいことが知られている。但し、任意の（ｋ−ｄ＋１）個から（ｋ−１）個までの分散情報が揃った場合には、ｆ（ｘ）に関する連立方程式から分割情報Ｓ１，Ｓ２，…，Ｓｄに関する関係式が求められるため、分割情報Ｓ１，Ｓ２，…，Ｓｄとして可能な値を得ることができ、元の秘密情報Ｓを部分的に復元することができる（例えば、非特許文献２参照）。
【非特許文献１】A. Shamir, “How to Share a Secret”, Commun. of ACM Vol.22, No.11, PP.612-613, 1979
【非特許文献２】G. R. Blakley, C. Meadows, “Security of ramp schemes”, Proc. of Crypto’84, Lecure Notes on comput. Sci., 106, pp.242-268, 1984
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の（ｄ，ｋ，ｎ）閾値秘密分散法には、秘密情報をＳをｄ個の分割情報Ｓ１，Ｓ２，…，Ｓｄに分割することで、生成される分散情報Ｗｉの大きさをｄ分の１に抑え、分散効率を上げることができる一方で、任意の（ｋ−ｄ＋１）個から（ｋ−１）個までの分散情報を揃えた場合には分割情報Ｓ１，Ｓ２，…，Ｓｄに関する関係式が簡単に求められるため、分割情報Ｓ１，Ｓ２，…，Ｓｄとして可能な値が容易に推測できてしまい、秘匿した情報の安全性に問題があった。
【００１０】
例えば、ｋ＝３、ｄ＝２、とした場合に、分散関数ｆ（ｘ）は、
ｆ（ｘ）＝Ｓ１＋Ｓ２・ｘ＋Ｒ１・ｘ２ （mod Ｐ）
で表現され、この分散関数により生成される任意の２個の分散情報ＷａとＷｂ（０＜ａ，ｂ＜Ｐ，ａ≠ｂ）は、以下の連立方程式で表される。
【００１１】
Ｗａ＝Ｓ１＋Ｓ２ａ＋Ｒ１ａ２
Ｗｂ＝Ｓ１＋Ｓ２ｂ＋Ｒ１ｂ２
従って、この２個の分散情報の連立方程式を解くことで、Ｓ１とＳ２の関係式が次のような一次式の形で得られる。
【００１２】
【数１】
このような関係式があれば、Ｓ１として可能な値に対し、Ｓ２として可能な値を容易に計算できるため、結果として秘密情報Ｓが推測できてしまう恐れがある。
【００１３】
本発明は、このような中間的な復元状態における情報漏洩の問題に鑑みなされたもので、（ｄ，ｋ，ｎ）閾値秘密分散法において、ｋ個の分散情報が揃わない限り、分散情報Ｓ１，Ｓ２，…，Ｓｄを求めることも推測することもできないようにし、効率的かつ安全な秘密情報Ｓの分散を可能とする秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
図１は、本発明の原理を説明するための図である。
【００１５】
本発明（請求項１）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散方法であって、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップ（ステップ１）と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップ（ステップ２）と、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップ（ステップ３）と、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップ（ステップ４）と、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップ（ステップ５）と、を行う。
【００１６】
本発明（請求項２）は、係数情報計算ステップ（ステップ３）において、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する。
【００１７】
本発明（請求項３）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元方法であって、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップ（ステップ１０）と、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップ（ステップ１１）と、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップ（ステップ１２）と、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップ（ステップ１３）と、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップ（ステップ１４）と、を行う。
【００１８】
図２は、本発明の原理構成図である。
【００１９】
本発明（請求項４）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散装置であって、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力手段１２０と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力手段１３０と、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算手段１４０と、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算手段１５０と、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力手段１６０と、を有する。
【００２０】
また、本発明（請求項５）は、係数情報計算手段１４０が、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する手段を含む。
【００２１】
本発明（請求項６）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元装置であって、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力手段２２０と、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力手段２３０と、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元手段２４０と、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元手段２５０と、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力手段２６０と、を有する。
【００２２】
本発明（請求項７）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散プログラムであって、
コンピュータに、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、を実行させるプログラムである。
【００２３】
また、本発明（請求項８）は、係数情報計算ステップにおいて、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と、乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する。
【００２４】
本発明（請求項９）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元プログラムであって、
コンピュータに、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、を実行させるプログラムである。
【発明の効果】
【００２５】
上記のように本発明によれば、秘密情報Ｓを分散符号化する際に、ｄ（ｄ＝分割数）分の１の大きさの分散情報Ｗｉを任意の個数生成し、生成した分散情報の内、任意のｋ個が揃わない限り、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められず、従って、秘密情報Ｓが復元できないように、秘密情報Ｓを分散符号化することができる。これにより、効率的かつ、安全な秘密情報の分散符号化を実現することができる。
【発明を実施するための最良の形態】
【００２６】
以下、図面と共に本発明の実施の形態を説明する。
【００２７】
図３は、本発明の概要を説明するための図である。
【００２８】
本発明は、秘密情報Ｓを分散符号化して、任意の個数のｄ（ｄは分割数）分の１の大きさの分散情報Ｗｉを生成し、生成した分散情報の内、任意のｋ個が揃わない限り、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められないように、秘密情報Ｓの分散を可能にするものである。
【００２９】
［第１の実施の形態］
本実施の形態では、秘密情報の分散について説明する。
【００３０】
秘密情報の分散に必要な条件と秘密情報Ｓとを入力して、秘密情報Ｓをｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄを、最大の分割情報Ｓｔ（１≦ｔ≦ｄ）よりも大きな素数Ｐと、素数Ｐよりも小さく０でない（ｋ−ｄ）個の乱数Ｒｉ（１≦ｉ≦ｋ−ｄ）からなる分散関数ｆ（ｘ）として、
ｆ（ｘ）＝Ｓ１＋Ｓ２ｘ＋…＋Ｓｄｘｄ−１＋Ｒ１ｘｄ＋…＋Ｒｋ−ｄｘｋ−１ (mod Ｐ)
の形で表現される（ｋ−１）次の多項式を用いてｋ個の係数情報Ｆｉ（１≦ｉ≦ｋ）を生成し、生成したｋ個の係数情報Ｆｉと素数Ｐからなる分散関数ｇ（ｘ）として、
ｇ（ｘ）＝Ｆ１＋Ｆ２ｘ＋…＋Ｆｋｘｋ−１ （mod Ｐ）
の形で表現される式を用いて任意の個数の分散情報Ｗｉ＝ｇ（ｉ）を生成する。
【００３１】
以下に詳細に説明する。
【００３２】
図４は、本発明の第１の実施の形態における秘密情報分散装置の構成図である。
【００３３】
本装置１００は、秘密情報の分散処理の各過程の制御を行う分散制御部１１０、分散条件の入力を受け付ける分散条件入力部１２０、分散の対象とする秘密情報Ｓの入力を受け付ける秘密情報入力部１３０、係数情報Ｆｉを算出する係数情報計算部１４０、分散情報Ｗｉを算出する分散情報計算部１５０、生成された分散情報を情報番号と組にして出力する分散情報出力部１６０、入力された分散条件、秘密情報、分散情報等を記憶する情報記憶部１７０から構成される。
【００３４】
以下の例では、秘密情報Ｓを２個の分散情報Ｓ１とＳ２に分割し、４個の分散情報を分散するものとして、４個の内任意の３個の分散情報を持ち寄れば秘密情報Ｓを復元でき、２個ないし１個の分散情報からは秘密情報Ｓを一切推測できないように、秘密情報Ｓの分散情報を生成する。
【００３５】
図５は、本発明の第１の実施の形態における秘密情報分散装置の動作を示す。
【００３６】
ステップ１０１） 分散条件入力部１２０は、分散条件の入力を受け付ける。入力を受け付ける分散条件は、例えば、生成する分散情報の個数として分散数ｎ、秘密情報Ｓの復元を可能とする分散情報の個数として閾値ｋ、秘密情報を分割する個数として分割数ｄとする。例えば、本実施の形態では、４個の分散情報を生成することから分散数ｎ＝４、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また秘密情報Ｓを２個の分割情報に分割することから分割数ｄ＝２が入力されたものとする。入力された分散条件は、情報記憶部１７０や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような分散条件は入力を受け付けるのではなく、所定の分散条件として情報記憶部１７０などに予め記憶しておいてもよい。
【００３７】
ステップ１０２） 次に、秘密情報入力部１３０は、分散の対象とする秘密情報Ｓの入力を受け付ける。本実施の形態では、秘密情報Ｓとして４桁の１６進文字列Ｓ＝３ＣＡＢが入力されたものとする。
【００３８】
ステップ１０３） 秘密情報入力部１３０は、既に入力された分散条件の分散数ｄ＝２に従って、秘密情報Ｓを２個の分割情報に分割して、情報記憶部１７０や内部メモリ（図示せず）などに一時的に記憶する。本実施の形態における分散情報をＳ１＝３Ｃ，Ｓ２＝ＡＢとする。
【００３９】
なお、本実施の形態では、分散条件入力部１２０において分散条件として閾値ｋと分散数ｄの入力を受け付け、秘密情報入力部１３０において秘密情報Ｓの入力を受け付けてｄ個の分割情報に分割するものとしたが、予めｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄの入力を受け付けて分割数ｄを求めるようにしても構わない。また、本実施の形態では、秘密情報Ｓに対する分割情報を秘密情報Ｓの上位２桁と下位２桁で分割しているが、本発明は秘密情報Ｓの分割方法を規定するものではなく、例えば、奇数ビットと偶数ビットのようにビット単位で分割しても構わないし、分割情報Ｓ０とＳ１の積が秘密情報Ｓとなるように分割するなどの方法も考えられる。
【００４０】
さらに、本実施の形態では、分散の対象とする秘密情報Ｓを１６進文字列に限定するものではなく、また単なる文字列に限定するものでもない。数値情報、文字列などの分散関数による演算が可能であればどのような情報でもよく、また文書や画像データなどのマルチメディアなどを対象としてもよい。
【００４１】
また、本実施の形態は、分散条件及び秘密情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して他の装置から入力するようにしても構わない。
【００４２】
ステップ１０４） 次に、係数情報計算部１４０において、閾値ｋと分割数ｄ及び分割情報に基づいて、係数情報Ｆｉを算出するための分散関数を生成し、ｋ個の係数情報Ｆｉを算出する。まず、各分割情報Ｓｄよりも大きな素数Ｐを決定し、素数Ｐよりも小さく０でない乱数Ｒｊを（ｋ−ｄ）個生成し、ｋ−１次の多項式である分散関数ｆ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３，分割数ｄ＝２より、以下のような多項式が分散関数ｆ（ｘ）となる。
【００４３】
ｆ（ｘ）＝Ｓ１＋Ｓ２・ｘ＋Ｒ１・ｘ２（mod Ｐ）
本実施の形態では、分割情報Ｓ１＝３Ｃ，Ｓ２ＡＢより素数Ｐ＝ＦＢ（２５１）を得たものとする。また、乱数Ｒ１＝１Ｆを生成したものとする。なお、本実施の形態では、係数情報計算部１４０において、素数Ｐや乱数Ｒｊの値などを決定しているが、これらの値について分散条件入力部１２０において入力するようにしても構わない。また、特に素数Ｐについては秘密情報Ｓあるいは分割情報Ｓｄの長さなどに応じて、予め情報記憶部１７０に記憶した素数Ｐを選択して用いるようにしてもよい。
【００４４】
次に、係数情報計算部１４０は、上記の分散関数ｆ（ｘ）を用いてｋ個の係数情報を生成する。ここでは分散関数ｆ（ｘ）、に対し、ｘ＝１，２，３を順次代入して計算し、係数情報Ｆ１，Ｆ２，Ｆ３を算出して情報記憶部１７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、閾値ｋ＝３、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ及びＲ１＝１Ｆと素数Ｐ＝ＦＢより、係数情報はそれぞれＦ１＝０Ｂ，Ｆ２＝１８、Ｆ３＝６３を得る。図６に、係数情報計算部１４０における係数情報の計算例を示す。
【００４５】
なお、本実施の形態は係数情報Ｆ１，Ｆ２，Ｆ３を分散関数ｆ（ｘ）に順次情報番号ｘ＝１，２，３を代入することで算出したが、異なる情報番号としてｘ＝１，３，５を用いて算出した結果を係数情報Ｆ１，Ｆ２，Ｆ３としてもよい。但し、このような係数情報群を算出するための情報番号群については外部から参照できないように秘密情報分散装置１００内に予め格納されているものとする。また、このような情報番号群を毎回無作為に生成した上で、情報番号ｘと算出結果とを結合して、実際の係数情報Ｆ１として用いるようにすることも考えられる。
【００４６】
ステップ１０５） 次に、分散情報計算部１５０は、閾値ｋと分散数ｎ及び係数情報に基づいて、分散情報Ｗｉを算出するための分散関数を生成し、ｎ個の分散情報Ｗｉを算出する。係数情報計算部１４０において求めた素数Ｐ及び係数情報Ｆｉより、ｋ−１次の多項式である分散関数ｇ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３より、以下のような多項式が分散関数ｇ（ｘ）となる。
【００４７】
ｇ（ｘ）＝Ｆ１＋Ｆ２・ｘ＋Ｆ３・ｘ２ （mod Ｐ）
分散情報計算部１５０は、上記の分散関数ｇ（ｘ）を使ってｎ個の分散情報Ｗｉを生成する。ここでは、分散関数ｇ（ｘ）に対し、ｘ＝１，２，３，４を順次代入して計算し、分散情報Ｗ１，Ｗ２，Ｗ３，Ｗ４を算出して情報記憶部１７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、分散数ｎ＝４、係数情報Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３より、分散情報はそれぞれＷ１＝８６，Ｗ２＝ＣＣ，Ｗ３＝ＤＤ，Ｗ４＝Ｂ９を得る。図７に、分散情報計算部１５０における分散情報の計算例を示す。
【００４８】
なお、本実施の形態において、分散関数ｇ（ｘ）、から分散情報を算出する際のｘの値を１０進の数字により記述しているが、可能なｘの値を１０進数の数字に規定するものではない。分散関数ｆ（ｘ）に則って分散情報を算出できればよく、例えば、１６進数であったり文字列であったりしても構わない。また、係数情報計算部１４０における分散関数ｆ（ｘ）と、分散情報計算部１５０における分散関数ｇ（ｘ）とで、同じ素数Pの値を使用するものとして記述しているが、分散関数ｇ（ｘ）における素数Ｐを分散関数ｆ（ｘ）における素数Ｐよりも大きな値としてもよい。
【００４９】
ステップ１０６） 分散情報出力部１６０は、分散情報計算部１５０において生成した分散情報を、分散情報を算出したｘの値（以下、情報番号）と組にして情報記憶部１７０に出力する。本実施の形態における出力は、（１，８６），（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）となる。
【００５０】
なお、本実施の形態は、分散情報出力部１６０における分散情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。但し、個々の分散情報を別個に出力することが望ましい。また、分散情報は直線各分散情報保持者または各分散保持装置に出力するようにし、出力の際に個々の保持者ないしは装置に合わせて暗号化するなどの手段も考えることもできる。
【００５１】
また、本実施の形態では、情報番号ｉと分散情報Ｗｉの組を出力するものとしたが、個々の分散情報が分散関数ｇ（ｘ）に何を代入して算出したものかがわかればよく、例えば、ｉとＷｉを連結して１８６，２ＣＣ，３ＤＤ，４Ｂ９のように出力しても良いし、また、例えば、出力先によって情報番号ｉが予め指定されている場合は分散情報Ｗｉのみを出力するようにしてもよい。
【００５２】
［第２の実施の形態］
以下、上記の第１の実施の形態により生成した分散情報から、分散情報Ｓ１及びＳ２，更に、秘密情報Ｓを復元する場合について説明する。
【００５３】
図８は、本発明の第２の実施の形態における秘密情報復元装置の構成図である。
【００５４】
秘密情報復元装置２００は、秘密情報復元装置２００における秘密情報の復元処理の各過程の制御を行う復元制御部２１０、復元条件の入力を受け付ける復元条件入力部２２０、復元に必要な個数の分散情報と情報番号の入力を受け付ける分散情報入力部２３０、係数情報を算出する係数情報復元部２４０、分割情報を算出する秘密情報復元部２５０、分割情報群を結合し秘密情報を出力する秘密情報出力部２６０、復元条件、分散情報と情報番号、秘密情報等を格納する情報記憶部２７０から構成される。
【００５５】
図９は、本発明の第２の実施の形態における秘密情報復元装置の動作を示す。
【００５６】
ステップ２０１） 復元条件入力部２２０は、復元条件の入力を受け付ける。入力を受け付ける復元条件は、例えば、秘密情報Ｓの復元に必要な分散情報の個数として閾値ｋ、秘密情報の分割数ｄ、素数Ｐなどとする。例えば、本実施の形態では、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、または、秘密情報Ｓを２個の分割情報に分割したことから分割数ｄ＝２、素数ＰとしてＰ＝ＦＢが入力されたものとする。入力された復元条件は、情報記憶部２７０や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような復元条件は入力を受け付けるのではなく、所定の復元条件として情報記憶部２７０などに予め記憶しておいてもよい。
【００５７】
ステップ２０２） 次に、分散情報入力部２３０は、復元に必要な個数の分散情報Ｗｉと情報番号ｉの入力を受け付ける。本実施の形態では、分散情報として（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）が入力されたものとする。入力された分散情報は、情報記憶部２７０や内部メモリ（図示せず）などに一時的に記憶する。
【００５８】
なお、本実施の形態では、分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、予め情報番号ｉが分かっている場合、例えば、入力元毎に決まっている場合には、分散情報Ｗｉのみを受け付けるようにしてもよい。また、入力元の情報に合わせて情報記憶部２７０より入力元に対応する情報番号を取得するようにしてもよい。なお、本実施の形態は復元条件及び分散情報の入力及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して複数の他の装置から入力しても構わない。
【００５９】
ステップ２０３） 次に、係数情報復元部２４０において、閾値ｋと素数Ｐ、入力された情報番号及び分散情報群から係数情報Ｆｉを算出するための復元関数を生成し、ｋ個の係数情報Ｆｉを算出する。本実施の形態では、入力された閾値ｋ＝３、素数Ｐ＝ＦＢ、分散情報群（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）から、係数情報復元部２４０は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【００６０】
Ｗ２＝Ｆ１＋２Ｆ２＋４Ｆ３＝ＣＣ (mod ＦＢ)
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝ＤＤ (mod ＦＢ
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝Ｂ９ （mod ＦＢ）
次に、係数情報復元部２４０は、この連立方程式から計算により係数情報Ｆ１，Ｆ２，Ｆ３を求める。連立方程式を掃き出し法により展開すると、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【００６１】
Ｆ１＝６Ｗ２−８ｗ３＋３Ｗ４＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗ２＋１２Ｗ３−５Ｗ４）／２＝１８ （mod ＦＢ）
Ｆ３＝（Ｗ２−２Ｗ３＋Ｗ４）／２＝６３ （mod ＦＢ）
このように算出した係数情報Ｆ１，Ｆ２，Ｆ３を情報記憶部２７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれ、Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３であり、正しい係数情報が得られていることが分かる。図１０に、係数情報復元部２４０における係数情報の計算例を示す。
【００６２】
なお、異なる分散情報の集合として（１，８６），（３，ＤＤ），（４，Ｂ９）が入力された場合でも、同様に連立方程式を生成して掃き出し法により展開することで、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【００６３】
Ｗ１＝Ｆ１＋Ｆ２＋Ｆ３＝８６ （mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝ＤＤ (mod ＦＢ)
Ｗ４＝Ｆ１＋４Ｆ３＋１６Ｆ３＝Ｂ９ （mod ＦＢ）
この連立方程式に対する展開結果及び計算情報の算出結果は以下のようになる。
【００６４】
Ｆ１＝２Ｗ１−２Ｗ３＋Ｗ４＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗ１＋１５Ｗ３−８Ｗ４）／６＝１８ (mod ＦＢ)
Ｆ３＝（Ｗ１−３Ｗ３＋２Ｗ４）／６＝６３ （mod ＦＢ）
このように、分散情報入力部２３０においてどのような組み合わせで分散情報Ｗ１が入力されても、閾値ｋ個の分散情報があれば、係数情報復元部２４０は係数情報を全て正しく復元することができる。
【００６５】
なお、本実施例では、係数情報復元部２４０において分散情報群を表す連立方程式を生成し、掃き出し法により展開することで、各係数情報についての方程式群を生成して、各係数情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の分散情報群から同じく閾値ｋ個の係数情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７０から取得し、各係数情報を算出する方法などが考えられる。以下は、閾値ｋ＝３の場合に入力された分散情報群を（ａ，Ｗａ），（ｂ，Ｗｂ），（ｃ，Ｗｃ）とした場合の自明な方程式群の例である。
【００６６】
Ｆ１＝｛−ｂｃ（ｂ−ｃ）Ｗａ−ｃａ（ｃ−ａ）Ｗｂ−ａｂ（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
Ｆ２＝｛（ｂ＋ｃ）（ｂ−ｃ）Ｗａ＋（ｃ＋ａ）（ｃ−ａ）Ｗｂ＋（ａ＋ｂ）（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
Ｆ３＝｛−（ｂ−ｃ）Ｗａ−（ｃ−ａ）Ｗｂ−（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
上記の方程式群に、（２，ＣＣ），（３，ＤＤ）（４，Ｂ９）を代入すると、正しく各係数情報を算出でき、連立方程式を解くよりも高速に処理できる。
【００６７】
Ｆ１＝６Ｗａ−８Ｗｂ＋３Ｗｃ＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗａ＋１２Ｗｂ−５Ｗｃ）／２＝１８ (mod ＦＢ)
Ｆ３＝（Ｗａ−２Ｗｂ＋Ｗｃ）／２＝６３ （mod ＦＢ）
ステップ２０５） 次に、秘密情報復元部２５０は、閾値ｋ、分割数ｄ、素数Ｐと係数情報復元部２４０において算出した各係数情報Ｆｉから、分割情報Ｓｔ（１≦ｔ≦ｄ）を算出するための復元関数を生成し、ｄ個の分割情報Ｓｔを算出する。本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３から、秘密情報復元部２５０は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【００６８】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ (mod ＦＢ)
Ｆ２＝Ｓ１＋２Ｓ２＋４Ｒ１＝１８ (mod ＦＢ)
Ｆ３＝Ｓ１＋３Ｓ２＋９Ｒ１＝６３ (mod ＦＢ)
次に、秘密情報復元部２５０は、この連立方程式から計算により分割情報Ｓ１，Ｓ２を求める。連立方程式を掃き出し法により展開すると、各分割情報についての方程式群が生成でき、各分割情報が算出できる。
【００６９】
Ｓ１＝３Ｆ１−３Ｆ２＋Ｆ３＝３Ｃ
Ｓ２＝（−５Ｆ１＋８Ｆ２−３Ｆ３）／２＝ＡＢ （mod ＦＢ）
このように算出した分割情報Ｓ１，Ｓ２を情報記憶部２７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれＳ１＝３Ｃ，Ｓ２＝ＡＢであり、正しい分割情報が得られていることが分かる。図１１に、秘密情報復元部２５０における秘密情報の計算例を示す。
【００７０】
なお、本実施の形態では、秘密情報復元部２５０において、係数情報群を表す連立方程式を生成し、掃き出し法により展開することで、各分割情報についての方程式群を生成して、各分割情報を算出しているが、このような数学的な処理の手順を実施の形態では特に規定するものではない。閾値ｋ個の係数情報群から分割数ｄ個の分割情報群を算出できればよく、例えば、上記のような自明な方程式群を予め情報記憶部２７０から取得し、各分割情報を算出するなどの方法などが考えられる。
【００７１】
また、本実施の形態は、係数情報Ｆ１，Ｆ２，Ｆ３を分散関数ｆ（ｘ）に順次情報番号ｘ＝１，２，３を代入した連立方程式を生成した上で、分割情報Ｓ１，Ｓ２を算出したが、係数情報Ｆ１，Ｆ２，Ｆ３が異なる情報番号としてｘ＝１，３，５を代入して計算されている場合には、同様に分散関数ｆ（ｘ）にｘ＝１，３，５を代入した連立方程式を生成して算出するものとする。このような係数情報群を算出するための情報番号群については外部から参照できないように秘密情報復元装置２００内に予め格納されているものとする。また、無作為に生成した情報番号群が実際の係数情報Ｆｉに含まれている場合には、これを分割して用いるようにすることも考えられる。
【００７２】
ステップ２０６） 秘密情報出力部２６０は、秘密情報復元部２５０において算出したｄ個の分割情報群を結合し、秘密情報Ｓとして出力する。本実施の形態では、Ｓ１＝３Ｃ，Ｓ２＝ＡＢから、結合すればＳ＝３ＣＡＢであり、正しい秘密情報が得られていることが分かる。
【００７３】
なお、本実施の形態は、秘密情報出力部２６０における秘密情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。また、分類情報群を結合して秘密情報Ｓとして出力するのではなく、個々の分割情報群をそれぞれ出力しても構わない。
【００７４】
本実施の形態では、分散情報入力部２３０において閾値ｋ個の分散情報の入力を受け付けるものとしたが、仮に分割情報入力部２３０が復元に必要な個数よりも少ない数の分散情報Ｗｉと情報番号ｉの入力を受け付けたとしても、係数情報復元部２４０において生成する連立方程式の数は不足しており、各係数情報Ｆｉの関係式を得ることはできるが、計算により各係数情報群を求めることはできない。
【００７５】
例えば、閾値ｋ＝３の時に、２個の分散情報を仮にＷａ＝ｆ（ａ）、Ｗｂ（ｂ）とした場合、その分散情報群を表す連立方程式は次のようになる。
【００７６】
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
連立方程式の数が閾値ｋ＝３よりも少ないため、これらの連立方程式からは係数情報Ｆ１とＦ２，Ｆ１とＦ３、Ｆ２とＦ３についての次のような関係式しか得ることができない。
【００７７】
（ｂ＋ａ）Ｆ１＋ｂａＦ２＝（ｂ２Ｗａ−ａ２Ｗｂ）／（ｂ−ａ） (mod Ｐ)
Ｆ１−ｂａＦ３＝（ｂＷａ−ａＷｂ）／（ｂ−ａ） (mod Ｐ)
Ｆ２＋（ａ＋ｂ）Ｆ３＝（Ｗａ−Ｗｂ）／（ａ−ｂ） (mod Ｐ)
このように、入力された分散情報の数が閾値ｋよりも少ない場合には、係数情報復元部２４０において係数情報Ｆ１，Ｆ２，Ｆ３を求めることができず、よって秘密情報復元部２４０において、分割情報群Ｓ１，Ｓ２を求めることもできない。従って、秘密情報Ｓが復元されることはない。
【００７８】
以上のように、第１の実施の形態における秘密情報分散装置１００により秘密情報Ｓから生成した分散情報については、第２の実施の形態における秘密情報復元装置２００において、個々の分散情報Ｗｉの大きさは秘密情報Ｓのｄ分の１であって、ｎ個の分散情報のうち、閾値ｋ個の任意の分散情報を持ち寄れば、ｋ個の係数情報Ｆｉを復元でき、よって全ての分割情報Ｓｔを復元して、秘密情報Ｓを完全に復元することができる。
【００７９】
一方、ｋ個未満の分散情報からは係数情報Ｆ１を復元できないため、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められず、秘密情報Ｓを復元することはできない。
【００８０】
［第３の実施の形態］
《秘密情報分散装置》
図１２は、本発明の第３の実施の形態における秘密情報分散装置の構成を示す。
【００８１】
同図に示す秘密情報分散装置１０００は、当該秘密情報分散装置１０００における秘密情報分散処理の処理を制御する分散制御部１１００、秘密情報を分散するための条件の入力を受け付ける分散条件入力部１２００、分散符号化の対象とする秘密情報の入力を受け付ける秘密情報入力部１３００、複数個に分割した秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、算出した係数情報と複数個に分割した秘密情報と乱数を係数とする多項式関数によって、繰り返し複数個の係数情報を算出する係数情報計算部１４００、係数情報計算部１４００で算出した複数個の係数情報を係数とする多項式関数によって任意の個数の分散情報を算出する分散情報計算部１５００、算出した分散情報群を出力する分散情報出力部１６００、入力された条件、秘密情報、計算結果等を記憶する情報記憶部１７００から構成される。
【００８２】
以下では、秘密情報Ｓを２個の分割情報Ｓ１，Ｓ２に分割した上で、４個の分散情報に分散するものとして、４個の内、任意の３個の分散情報を持ち寄れば秘密情報Ｓを完全に復元でき、２個乃至１個の分散情報からは秘密情報Ｓを一切推測できないように、秘密情報Ｓの分散情報を生成する秘密情報分散処理について説明する。
【００８３】
図１３は、本発明の第３の実施の形態における秘密情報分散装置の動作説明図である。
【００８４】
ステップ１１０１） 分散条件入力部１２００において、分散条件の入力を受け付ける。入力された分散条件は、例えば、生成する分散情報の個数として分散数ｎ、秘密情報Ｓの復元を可能とする分散情報の個数として閾値ｋ、秘密情報を分割する個数としての分割数ｄとする。例えば、本実施の形態では、４個の分散情報を生成することから分散数ｎ＝４、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また、秘密情報Ｓを２個の分割情報に分割することから分割数ｄ＝２が入力されたものとする。入力された分散条件は、情報記憶部１７００や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような分散条件は入力を受け付けるのではなく、所定の分散条件として情報記憶部１７００などに予め記憶しておいてもよい。
【００８５】
ステップ１１０２） 次に、秘密情報入力部１３００は、分散の対象とする秘密情報Ｓの入力を受け付ける。本実施の形態では、秘密情報Ｓとして４桁の１６進文字列Ｓ＝３ＣＡＢが入力されたものとする。秘密情報入力部１３００は、既に入力された分散条件の分割数ｄ＝２に従って、秘密情報Ｓを２個の分割情報に分割して、情報記憶部１７００や内部メモリ（図示せず）などに一時的に記憶する。本実施の形態における分割情報をＳ１＝３Ｃ，Ｓ２＝ＡＢとする。
【００８６】
なお、本実施の形態では、分散条件入力部１２００において分散条件として閾値ｋと分割数ｄの入力を受け付け、秘密情報入力部１３００において秘密情報Ｓの入力を受け付けてｄ個の分割情報に分割するものとしたが、予めｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄの入力を受け付けて分散数ｄを求めるようにしても構わない。また、本実施の形態では秘密情報Ｓに対する分割情報を秘密情報Ｓの上位２桁と下位２桁で分割しているが、本発明は、秘密情報Ｓの分割方法を規定するものではなく、例えば、奇数ビットと偶数ビットのようにビット単位で分割しても構わないし、分割情報Ｓ０とＳ１の積が秘密情報Ｓとなるように分割するなどの方法も考えられる。
【００８７】
さらに、本実施の形態は、分散の対象とする秘密情報Ｓを１６進文字列に限定するものではなく、また、単なる文字列に限定するものでもない。数値情報、文字列などの分散関数による演算が可能であれば、どのような情報でもよく、また、文書や画像データなどのマルチメディアなども対象としてもよい。
【００８８】
また、本実施の形態は、分散条件及び秘密情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して他の装置から入力するようにしても構わない。
【００８９】
ステップ１１０３） 次に、係数情報計算部１４００において、閾値ｋと分割数ｄ及び分割情報に基づいて、係数情報Ｆｉを算出するための分散関数を生成し、ｋ個の係数情報Ｆｉを算出する。
【００９０】
まず、各分割情報Ｓｄよりも大きな素数Ｐを決定し、素数Ｐよりも小さく０でない乱数Ｒｊを（ｋ−ｄ）個生成し、ｋ−１次の多項式である分散関数ｆ（ｘ）を生成する。本実施の形態における分散関数ｆ（ｘ）を以下のように定義する。
【００９１】
【数２】
また、本分散関数ｆ（ｘ）による係数情報Ｆｉの算出式を以下のようにする。
【００９２】
Ｆｉ＝ｆ（Ｆｉ−１）
従って、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２より、Ｓ３＝Ｒ１として、以下のような分散関数ｆ（ｘ）により係数情報Ｆｉが算出される。
【００９３】
Ｆｉ＝ｆ（ｘ）＝Ｓ１＋Ｆｉ−１Ｓ２・ｘ＋Ｆｉ−１２・Ｒ１ （mod Ｐ）
本実施の形態では、係数情報計算部１４００において、素数Ｐや乱数Ｒｊの値などを決定しているが、これらの値について分散条件入力部１２００において入力するようにしても構わない。また、特に、素数Ｐについては秘密情報Ｓあるいは分割情報Ｓｄの長さなどに応じて予め情報記憶部１７００に記憶した素数Ｐを選択して用いるようにしてもよい。
【００９４】
ステップ１１０４） 次に、係数情報計算部１４００は、上記の分散関数ｆ（ｘ）を使ってｋ個の係数情報を生成する。本実施の形態では、初期係数情報Ｆ０＝１とおくものとして、閾値ｋ＝３、分割情報Ｓ１＝３Ｃ、Ｓ２＝ＡＢ及びＲ１＝１Ｆと素数Ｐ＝ＦＢより、まず、係数情報Ｆ１を算出する。算出の結果、Ｆ１＝０Ｂとなる。
【００９５】
次いで、順次係数情報の算出結果を用いて、繰り返し演算し、係数情報Ｆ２＝ＡＡ，Ｆ３＝５Ｆを得る。算出した係数情報Ｆ１，Ｆ２，Ｆ３は、情報記憶部１７００または、内部メモリ（図示せず）などに一時的に記憶する。図１４に係数情報計算部１４００における係数情報の計算例を示す。
【００９６】
なお、係数情報計算部１４００において生成するｋ個の係数情報については、値の重複がないようにしなければならない。例えば、本実施の形態においては、初期係数情報Ｆ０＝１からＦ１≠１でなければならず、同様にＦ２≠１，０Ｂで、Ｆ３≠１，０Ｂ，ＡＡでなければならない。係数情報計算部１４００はこのような値の重複をチェックし、重複があった場合には再度乱数Ｒ１の再生成と、係数情報の再生成を行う。
【００９７】
ステップ１１０５） 次に、分散情報計算部１５００は、閾値ｋと分散数ｎ及び係数情報に基づいて、分散情報Ｗｉを算出するための分散関数を生成し、ｎ個の分散情報Ｗｉを算出する。係数情報計算部１４００において求めた素数Ｐ及び係数情報Ｆｉより、ｋ−１次の多項式である分散関数ｇ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３より、以下のような多項式が分散関数ｇ（ｘ）となる。
【００９８】
ｇ（ｘ）＝Ｆ１＋Ｆ２・ｘ＋Ｆ３・ｘ２ （mod P）
分散情報計算部１５００は、上記の分散関数ｇ（ｘ）を使って、ｎ個の分散情報Ｗｉを生成する。ここでは、分散数ｎ＝４より、分散関数ｇ（ｘ）に対し、ｘ＝１，２，３，４を順次代入してＷｘ＝ｇ（ｘ）を計算し、分散情報Ｗ１，Ｗ２，Ｗ３，Ｗ４を算出して情報記憶部１７００または、内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、係数情報Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆより、分散情報はそれぞれＷ１＝１９，Ｗ２＝Ｅ５，Ｗ３＝７９，Ｗ４＝ＣＢを得る。図１５に分散情報計算部１５００における分散情報の計算例を示す。
【００９９】
なお、本実施の形態において、分散関数ｇ（ｘ）から分散情報を算出する際のｘの値を１０進数の数字により記述しているが、可能なｘの値を１０進数の数字に規定するものではない。分散関数ｆ（ｘ）に則って分散情報を算出できればよく、例えば、１６進数であったり、文字列であったりしても構わない。また、係数情報計算部１４００における分散関数ｆ（ｘ）と、分散情報計算部１５００における分散関数ｇ（ｘ）とで、同じ素数Ｐの値を使用するものとして記述しているが、分散関数ｇ（ｘ）における素数Ｐを分散関数ｆ（ｘ）における素数Ｐよりも大きな値としてもよい。
【０１００】
ステップ１１０６） 分散情報出力部１６００は、分散情報計算部１５００において生成した分散情報を、分散情報を算出したｘの値（以下、情報番号）とを組にして出力する。本実施の形態における出力は、（１，１９），（２，Ｅ５），（３，７９），（４，ＣＢ）となる。
【０１０１】
なお、本実施の形態は、分散情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。但し、個々の分散情報を別個に出力することが望ましい。また、分散情報は直接各分散情報保持者または、各分散情報保持装置に出力するようにし、出力の際に個々の保持者乃至は装置に合わせて暗号化するなどの手段も考えることもできる。
【０１０２】
また、本実施の形態では、情報番号ｉと分散情報Ｗｉの組を出力するものとしたが、個々の分散情報が分散関数ｇ（ｘ）に何を代入して算出したものかが分かればよく、例えば、ｉとＷｉを連結して１１９，２Ｅ５，３７９，４ＣＢのように出力してもよいし、また例えば、出力先によって情報番号ｉが予め指定されている場合は分散情報Ｗｉのみを出力するようにしてもよい。
【０１０３】
分散情報の出力をもって、秘密情報分散装置１０００の動作は終了する。
【０１０４】
なお、本実施の形態は秘密分散法による分散処理を２回使用して秘密情報から係数情報の算出と分散情報の算出をそれぞれ行ったが、本発明は、複数回の秘密分散法による分散処理を連結して繰り返すことで秘密情報の推測ができないように分散情報を算出できればよく、本実施の形態の構成に制限されない。
【０１０５】
《秘密情報復元装置》
次に、秘密情報の復元について説明する。
【０１０６】
以下、本実施の形態により生成した分散情報から、分割情報Ｓ１及びＳ２、更に秘密情報Ｓを復元する場合について説明する。
【０１０７】
図１６は、本発明の第１の実施の形態における秘密情報復元装置の構成を示す。
【０１０８】
同図に示す秘密情報復元装置２０００は、秘密情報復元装置２０００における秘密情報の復元処理の各過程の制御を行う復元制御部２１００、復元条件の入力を受け付ける復元条件入力部２２００、復元に必要な個数の分散情報と秘密情報の分割数、素数などの入力を受け付ける分散情報入力部２３００、入力された複数個の分散情報群に対応する連立方程式を解くことにより複数個の係数情報を算出する係数情報復元部２４００、係数情報復元部２４００で算出された複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元部２５００、算出した秘密情報を出力する秘密情報出力部２６００、復元条件、分散情報と情報番号、秘密情報等を格納する情報記憶部２７００から構成される。
【０１０９】
図１７は、本発明の第１の実施の形態における秘密情報復元装置の動作説明図である。
【０１１０】
ステップ２１０１） 復元条件入力部２１００は、復元条件の入力を受け付ける。受け付ける復元条件は、例えば、秘密情報Ｓの復元に必要な分散情報の個数として閾値ｋ、秘密情報の分割数ｄ、素数Ｐなどとする。例えば、本実施の形態では、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また、秘密情報Ｓを２個の分割情報に分割したことから分割数ｄ＝２、素数ＰとしてＰ＝ＦＢが入力されたものとする。入力された復元条件は、情報記憶部２７００や内部メモリ（図示せず）などに一時的に記憶するものとする。
【０１１１】
また、このような復元条件は、入力を受け付けるものではなく、所定の復元条件として情報記憶部２７００などに予め記憶しておいてもよい。
【０１１２】
ステップ２１０２） 次に、分散情報入力部２３００は、復元に必要な個数の分散情報Ｗｉと情報番号ｉの入力を受け付ける。本実施の形態では、３個の分散情報として（２，Ｅ５），（３，７９），（４，ＣＢ）が入力されたものとする。入力された分散情報は、情報記憶部２７００や内部メモリ（図示せず）などに一時的に記憶する。
【０１１３】
なお、本実施の形態では、分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、予め情報番号ｉが分かっている場合、例えば、入力元毎に決まっている場合は、分散情報Ｗｉのみを受け付けるようにしてもよい。
【０１１４】
また、入力元の情報に合わせて情報記憶部２７００より入力元に対応する情報番号を取得するようにしてもよい。
【０１１５】
なお、本実施の形態は、復元条件及び分散情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して複数の他の装置から入力するようにしても構わない。
【０１１６】
ステップ２１０３） 次に、情報係数復元部２４００において、閾値ｋと素数Ｐ、入力された情報番号及び分散情報群から、係数情報Ｆｉを算出するための復元関数を生成し、ｋ個の係数情報Ｆｉを算出する。本実施の形態では、入力された閾値ｋ＝３、素数Ｐ＝ＦＢ、分散情報群（２，Ｅ５），（３，７９），（４，ＣＢ）から、係数情報復元部２４００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１１７】
Ｗ２＝Ｆ１＋２Ｆ２＋４Ｆ３＝Ｅ５（mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝７９ （mod ＦＢ）
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝ＣＢ （mod ＦＢ）
次に、係数情報復元部２４００は、この連立方程式から計算により係数情報Ｆ１，Ｆ２，Ｆ３を求める。連立方程式を掃き出し法により展開すると、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【０１１８】
Ｆ１＝６Ｗ２−８Ｗ３＋３Ｗ４＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗ２＋１２Ｗ３−５Ｗ４）／２＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗ２−２Ｗ３＋Ｗ４）／２＝５Ｆ （mod ＦＢ）
このように算出した係数情報Ｆ１，Ｆ２，Ｆ３をそれぞれ情報記憶部２７００または、内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれ、Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆであり、正しい係数情報が得られていることが分かる。図１８に、係数情報復元部２４００における係数情報の計算例を示す。
【０１１９】
なお、異なる分散情報の集合として（１，１９），（３，７９），（４，ＣＢ）が入力された場合でも、同様に連立方程式を生成して掃き出し法により展開することで、各係数情報についての方程式が生成でき、各係数情報が算出できる。
【０１２０】
Ｗ１＝Ｆ１＋Ｆ２＋Ｆ３＝１９ （mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝７９ (mod ＦＢ)
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝ＣＢ （mod ＦＢ）
この連立方程式に対する展開結果及び計算情報の算出結果は以下のようになる。
【０１２１】
Ｆ１＝２Ｗ１−２Ｗ３＋Ｗ４＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗ１＋１５Ｗ３−８Ｗ４）／６＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗ１−３Ｗ３＋２Ｗ４）／６＝５Ｆ (mod ＦＢ)
このように、分散情報入力部２３００においてどのような組み合わせで分散情報Ｗｉが入力されても、閾値ｋ個の分散情報があれば、係数情報復元部２４００は、係数情報を全て正しく復元することができる。
【０１２２】
なお、本実施の形態では、係数情報復元部２４００において分散情報群を表す連立方程式を生成し、掃き出し法により展開することで、各係数情報についての方程式群を生成して、各係数情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の分散情報群から同じく閾値ｋ個の係数情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７００から取得し、各係数情報を算出する方法などが考えられる。
【０１２３】
以下は、閾値ｋ＝３の場合に入力された分散情報群を（ａ，Ｗａ），（ｂ，Ｗｂ），（ｃ，Ｗｃ）とした場合の自明な方程式群の例である。
【０１２４】
Ｆ１＝｛−ｂｃ（ｂ−ｃ）Ｗａ−ｃａ（ｃ−ａ）Ｗｂ−ａｂ（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
Ｆ２＝｛（ｂ＋ｃ）（ｂ−ｃ）Ｗａ＋（ｃ＋ａ）（ｃ−ａ）Ｗｂ＋（ａ＋ｂ）（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
Ｆ３＝｛−（ｂ−ｃ）Ｗａ−（ｃ−ａ）Ｗｂ−（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
上記の方程式群に（２，Ｅ５），（３，７９），（４，ＣＢ）を代入すると、正しく各係数情報を算出でき、連立方程式を解くよりも高速に処理できる。
【０１２５】
Ｆ１＝６Ｗａ−８Ｗｂ＋３Ｗｃ＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗａ＋１２Ｗｂ−５Ｗｃ）／２＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗａ＋２Ｗｂ＋Ｗｃ）／２＝５Ｆ （mod ＦＢ）
ステップ２１０４） 次に、秘密情報復元部２５００は、閾値ｋ、分割数ｄ、素数Ｐと前述の係数情報復元部２４００において算出した各係数情報Ｆｉから、分割情報Ｓｔ（１≦ｔ≦ｄ）を算出するための復元関数を生成し、ｄ個の分割情報Ｓｔを算出する。本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝Ｆより分散関数の形は、
ｆ（ｘ）＝Ｓ１＋Ｆｉ−１Ｓ２・ｘ＋Ｆｉ−１２・Ｒ１ （mod P）
であり、これと係数情報群Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆから、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１２６】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋（０Ｂ）２・Ｒ１＝ＡＡ （mod ＦＢ）
Ｆ３＝Ｓ１＋ＡＡ・Ｓ２＋（ＡＡ）２・Ｒ１＝５Ｆ （mod ＦＢ）
ステップ２１０５） 次に、秘密情報復元部２５００は、この連立方程式から計算により分割情報Ｓ１，Ｓ２を求める。連立方程式を掃き出し法により展開すると、各分割情報が算出できる。
【０１２７】
【数３】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。算出した分割情報Ｓ１，Ｓ２は情報記憶部２７００または、内部メモリ（図示せず）などに一時的に記憶する。
【０１２８】
なお、本実施の形態では、秘密情報復元部２５００において、係数情報群を表す連立方程式を生成し、掃き出し法により展開することで、各分割情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の係数情報群から分割数ｄ個の分割情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７００から取得し、各分割情報を算出する方法などが考えられる。以下は、閾値ｋ＝３の場合に係数情報群を（１，Ｆ１），（Ｆ１，Ｆ２），（Ｆ２，Ｆ３）としたときの自明な方程式群の例である。
【０１２９】
【数４】
この方程式に、係数情報群Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆと素数Ｐ＝ＦＢを代入すれば、同様に算出結果としてＳ１＝３Ｃ，Ｓ２＝ＡＢが得られる。秘密情報分散装置１０００において、秘密情報を２個に分割した分割情報はそれぞれＳ１＝３Ｃ，Ｓ２＝ＡＢであり、計算により正しい分割情報が得られていることが分かる。図１９に、後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１３０】
ステップ２１０６） 秘密情報出力部２６００は、秘密情報復元部２５００において算出したｄ個の分割情報群を結合し、秘密情報Ｓとして出力する。本実施の形態では、Ｓ１＝３Ｃ、Ｓ２＝ＡＢから、結合すればＳ＝３ＣＡＢであり、正しい秘密情報が得られていることが分かる。
【０１３１】
なお、本実施の形態では、秘密情報出力部２６００における秘密情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。また、分割情報群を結合して秘密情報Ｓとして出力するのではなく、個々の分割情報群をそれぞれ出力しても構わない。
【０１３２】
本実施の形態では、分散情報入力部２３００において、閾値ｋ個の分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、仮に、分散情報入力部２３００が復元に必要な個数よりも少ない数の分散情報Ｗｉと情報番号ｉの入力を受け付けたとしても、係数情報復元部２４００において生成する連立方程式の数が不足しており、各係数情報Ｆｉの関係式を得ることができるが、計算により各係数情報群を求めることはできない。
【０１３３】
また、仮に、各係数情報Ｆｉの関係式を得たとしても、係数情報群はｄ個の分割情報群Ｓｄと乱数Ｒｊ、及び係数情報Ｆｉ−１からなるため、分割情報群Ｓｄを求める、あるいは、推測することはできない。
【０１３４】
例えば、閾値ｋ＝３の時に、２個の分散情報を仮にＷａ＝ｆ（ｚ），Ｗｂ＝ｆ（ｂ）とした場合、その分散情報群を表す連立方程式は次のようになる。
【０１３５】
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
Ｗｂ＝ｆ（ｂ）＝Ｆ１＋ｂＦ２＋ｂ２Ｆ３ （mod Ｐ）
連立方程式の数が閾値ｋ＝３よりも少ないため、これらの連立方程式からは係数情報Ｆ１とＦ２、Ｆ１とＦ３、Ｆ２とＦ３についての次のような関係式しか得ることができない。
【０１３６】
（ｂ＋ａ）Ｆ１＋ｂａＦ２＝（ｂ２Ｗａ−ａ２Ｗｂ）／（ｂ−ａ） （mod Ｐ）
Ｆ１−ｂａＦ３＝（ｂＷａ−ａＷｂ）／（ｂ−ａ） （mod Ｐ）
Ｆ２＋（ａ＋ｂ）Ｆ３＝（Ｗａ−Ｗｂ）／（ａ−ｂ） （mod Ｐ）
このように、入力された分散情報の数が閾値ｋよりも少ない場合には、係数情報復元部２４００において係数情報Ｆ１，Ｆ２，Ｆ３を求めることができず、よって秘密情報復元部２５００において、分割情報群Ｓ１，Ｓ２を求めることもできない。従って、秘密情報Ｓが復元されることはない。
【０１３７】
なお、本実施の形態は秘密分散法による復元処理を２回使用して分散情報から係数情報の算出と秘密情報の算出をそれぞれ行ったが、本発明は複数回の秘密分散法による復元処理を連結して繰り返すことで閾値数の任意の分散情報の集合から秘密情報を算出できればよく、本実施の形態の構成に制限されない。
【０１３８】
以上のように、本実施の形態における秘密情報分散装置１０００による秘密情報Ｓから生成した分散情報については、個々の分散情報Ｗｉの大きさは秘密情報Ｓのｄ分の１であって、ｎ個の分散情報の内、閾値ｋ個の任意の分散情報を持ち寄れば、ｋ個の係数情報Ｆｉを復元でき、よって全ての分散情報Ｓｔを復元して、秘密情報Ｓを完全に復元することができる。一方、ｋ個未満の分散情報からは係数情報Ｆｉを復元できないため、分散情報Ｓ１，Ｓ２，…，Ｓｄが求められず、秘密情報Ｓを復元することはできない。
【０１３９】
［第４の実施の形態］
本実施の形態では、第３の実施の形態における係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、計算を簡略化する例を説明する。本実施の形態の秘密情報分散装置１０００、秘密情報復元装置２０００の構成は、前述の第３の実施の形態と同様である。また、動作については、以下の説明以外については、第３の実施の形態と同様である。
【０１４０】
例えば秘密情報分散装置１０００において、係数情報計算部１４００における係数情報Ｆｉの算出式を以下ようにする。
【０１４１】
Ｆｉ＝Ｓ１＋Ｆｉ−１Ｓ２＋ｉＲ１ （mod Ｐ）
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。本実施の形態では、初期係数情報Ｆ０＝１とおくものとすると、係数情報Ｆ１＝０Ｂとなる。次いで、順次係数情報算出結果を用いて、繰り返し演算し、係数情報Ｆ２＝Ｆ６，Ｆ３＝３３を得る。図２０に本実施の形態での係数情報計算部１４００における係数情報の計算例を示す。
【０１４２】
これに伴って、秘密情報復元装置２０００において、秘密情報復元部２５００における計算も簡略化することができる。
【０１４３】
例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｆ６，Ｆ３＝３３から、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１４４】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋２・Ｒ１＝Ｆ６ （mod ＦＢ）
Ｆ３＝Ｓ１＋Ｆ６・Ｓ２＋３・Ｒ１＝３３ （mod ＦＢ）
秘密情報復元部２５００は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１４５】
【数５】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１４６】
なお、閾値ｋから自明に求まる方程式群を使って各分割情報を算出する場合、式は以下のようになり、計算が簡略化される。
【０１４７】
【数６】
この方程式に、係数情報群Ｆ１＝０Ｂ、Ｆ２＝Ｆ６，Ｆ３＝３３と素数Ｐ＝ＦＢを代入すれば、同様に算出結果として正しい分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢが得られる。図２１に、後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１４８】
［第５の実施の形態］
本実施の形態では、前述の第３の実施の形態における係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、計算を簡略化することができる例を説明する。本実施の形態の秘密情報分散装置１０００、秘密情報復元装置２０００の構成は、前述の第３の実施の形態と同様である。また、動作については、以下の説明以外については、第３の実施の形態と同様である。
【０１４９】
例えば秘密情報分散装置１０００において、係数情報計算部１４００における係数情報Ｆｉの算出式を閾値ｋに対して以下のように定義する。
【０１５０】
【数７】
従って、本実施の形態の場合、閾値ｋ＝３に対し、Ｓ３＝Ｒ１として、以下の算出式を用いる。
【０１５１】
【数８】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。本実施の形態では、係数情報Ｆ１＝０Ｂとなり、次いで係数情報Ｆ１を用いて繰り返し演算し、係数情報Ｆ２＝Ｄ７，Ｆ３＝４６を得る。図２２に本実施の形態における係数情報計算部１４００の係数情報の計算例を示す。
【０１５２】
これに伴って、秘密情報復元装置２０００において、秘密情報復元部２５００における計算も簡略化することができる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｄ７，Ｆ３＝４６から、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１５３】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋Ｒ１＝Ｄ７ （mod ＦＢ）
Ｆ３＝Ｓ１＋Ｓ２＋０Ｂ・Ｒ１＝４６ （mod ＦＢ）
秘密情報復元部２５００は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１５４】
【数９】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ３＝１Ｆがそれぞれ算出結果となる。
【０１５５】
なお、閾値ｋから自明に求まる方程式群を使って各分割情報を算出する場合は、式は以下のようになり、更に計算が簡略化される。
【０１５６】
【数１０】
この方程式は、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｆ６，Ｆ３＝３３と素数Ｐ＝ＦＢを代入すれば、同様に算出結果として正しい分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢが得られる。図２３に後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１５７】
［第６の実施の形態］
本実施の形態は、第１の実施の形態の係数情報計算部１４０または、第３の実施の形態の係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、分割情報群Ｓｄの推測を更に困難にすることができる。以下では、第１の実施の形態の秘密情報分散装置１００及び秘密情報復元装置２００を用いて説明する。
【０１５８】
例えば、秘密情報分散装置１００の係数情報計算部１４０における係数情報Ｆｉの算出式を以下のようにする。
【０１５９】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１ (mod Ｐ)
Ｆｉ＝ｆ（Ｆｉ−２ xor Ｆｉ−１）
＝Ｓ１＋（Ｆｉ−２ xor Ｆｉ−１）Ｓ２＋（Ｆｉ−２ xor Ｆｉ−１）２・Ｒ１ （mod P）
（ｉ≧２）
ここで、式中のxorは排他的論理和を表す二項演算子とし、前後の値を２進数すなわちビット値で表現した上で、各ビットの位置ごとにビット値が同じ、すなわち、０と０、１と１であれば０を、ビット値が違う、すなわち、０と１，１と０であれば１を、演算結果のビット値とする演算方法を示すものとする。例えば、
８（１０００）xor ３（００１１）＝１１（１０１１）、
９（１００１）xor ３（００１１）＝１０（１０１０）
となる。
【０１６０】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。算出したＦｉが０または１または既に算出したＦｊ（ｊ＜ｉ）と一致する場合には、乱数Ｒ１を再度求めて、計算をやり直す。本実施の形態では、係数情報Ｆ１＝０Ｂとなる。初期係数情報Ｆ０＝１とおくものとして、順次係数情報の算出結果を用いて繰り返し演算すると、係数情報Ｆ２＝ｆ（１xorＦ１）＝６５，Ｆ３＝ｆ（Ｆ１xorＦ２）＝９７を得る。
【０１６１】
なお、本実施の形態における係数情報の計算時に、分散関数ｆ（ｘ）にＦｉ−２xorＦｉ−１を代入するものとしたが、本実施の形態は代入する値をこれに限定するものではない。既に生成した全ての係数情報の排他的論理和を計算して代入してもよいし、直前に生成した係数情報Ｆｉ−１と何らかの秘密の定数との排他的論理和を計算して代入しても良い。また、排他的論理和に限る必要もなく、論理和や論理積などの演算子を用いてもよい。
【０１６２】
これに伴って、秘密情報復元装置２００において、秘密情報復元部２５０における計算も排他的論理和を用いる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝６５，Ｆ３＝９７から、秘密情報復元部２５０は、１xorＦ１＝０A，F１xorF２＝６Eをそれぞれ計算し、次のような連立方程式を内部メモリ上に生成する。
【０１６３】
Ｆ１=Ｓ１+Ｓ２+Ｒ１=０Ｂ（mod FB）
Ｆ２=Ｓ１+０Ａ・Ｓ２+（０Ａ）２・Ｒ１=６５（mod FB）
Ｆ３=Ｓ１+６Ｅ・Ｓ２+（６Ｅ）２・Ｒ１=９７（mod FB）
秘密情報復元部２５０は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１６４】
【数１１】
以上のように、Ｓ１＝３Ｃ、Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１６５】
［第７の実施の形態］
本実施の形態では、第１の実施の形態の係数情報計算部１４０、第３の実施の形態の係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、分割情報群Ｓｄの推測を更に困難する例を説明する。以下では、第１の実施の形態における秘密情報分散装置１００、秘密情報復元装置２００を対象として説明する。
【０１６６】
係数情報計算部１４０における係数情報Ｆｉの算出式を以下のようにする。
【０１６７】
【数１２】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。算出したＦｉが０または１または既に算出したＦｊ（ｊ＜ｉ）と一致する場合には、乱数Ｒ１を再度求めて、計算をやり直す。本実施の形態では、係数情報Ｆ１＝０Ｂとなる。順次係数情報の算出結果を用いて繰り返し演算すると、係数情報Ｆ２＝ｆ（２Ｆ１）＝１９，Ｆ３＝ｆ（２Ｆ２）＝ＡＢを得る。
【０１６８】
なお、本実施の形態における係数情報の計算時に、分散関数ｆ（ｘ）に
【０１６９】
【数１３】
を代入するものとしたが、本実施の形態は代入する値をこれに限定するものではない。既に生成した全ての係数情報を指数として演算した値を代入してもよいし、直前に生成した係数情報Ｆｉ−１と何らかの秘密の定数との和あるいは積を指数として演算して代入してもよい。
【０１７０】
これに伴って、秘密情報復元装置２００において、秘密情報復元部２５０における計算も指数演算を用いる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝１９，Ｆ３＝ＡＢから、秘密情報復元部２５０は、２０Ｂ≡２８，２１９≡ＦＡ（mod P）をそれぞれ計算し、次のような連立方程式を内部メモリ上に生成する。
【０１７１】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋２８・Ｓ２＋（２８）２・Ｒ１＝１９ （mod ＦＢ）
Ｆ３＝Ｓ１＋ＦＡ・Ｓ２＋（ＦＡ）２・Ｒ１＝ＡＢ （mod ＦＢ）
秘密情報復元部２５０は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１７２】
【数１４】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１７３】
また、上記の各実施の形態における秘密情報分散装置及び秘密情報復元装置の各構成要素の動作をプログラムとして構築し、秘密情報分散装置及び秘密情報復元装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることも可能である。
【０１７４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１７５】
本発明は、ネットワーク上で取り扱われる各種情報のセキュリティ技術に適用可能である。
【図面の簡単な説明】
【０１７６】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の概要を説明するための図である。
【図４】本発明の第１の実施の形態における秘密情報分散装置の構成図である。
【図５】本発明の第１の実施の形態における秘密情報分散装置の動作説明図である。
【図６】本発明の第１の実施の形態における係数情報計算部の係数情報の計算例である。
【図７】本発明の第１の実施の形態における分散情報計算部の分散情報の計算例である。
【図８】本発明の第２の実施の形態における秘密情報復元装置の構成図である。
【図９】本発明の第２の実施の形態における秘密情報復元装置の動作説明図である。
【図１０】本発明の第２の実施の形態における係数情報復元部の係数情報の計算例である。
【図１１】本発明の第２の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図１２】本発明の第３の実施の形態における秘密情報分散装置の構成図である。
【図１３】本発明の第３の実施の形態における秘密情報分散装置の動作説明図である。
【図１４】本発明の第３の実施の形態における係数情報計算部の係数情報の計算例である。
【図１５】本発明の第３の実施の形態における分散情報計算部の分散情報の計算例である。
【図１６】本発明の第３の実施の形態における秘密情報復元装置の構成図である。
【図１７】本発明の第３の実施の形態における秘密情報復元装置の動作説明図である。
【図１８】本発明の第３の実施の形態における係数情報復元部の係数情報の計算例である。
【図１９】本発明の第３の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図２０】本発明の第４の実施の形態における係数情報計算部の係数情報の計算例である。
【図２１】本発明の第４の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図２２】本発明の第５の実施の形態における係数情報計算部の係数情報の計算例である。
【図２３】本発明の第５の実施の形態における秘密情報復元部の秘密情報の計算例である。
【符号の説明】
【０１７７】
１００，１０００ 秘密情報分散装置
１１０，１１００ 分散制御部
１２０，１２００ 分散条件入力手段、分散条件入力部
１３０，１３００ 秘密情報入力手段、秘密情報入力部
１４０，１４００ 係数情報計算手段、係数情報計算部
１５０，１５００ 分散情報計算手段、分散情報計算部
１６０，１６００ 出力手段、分散情報出力部
１７０，１７００ 情報記憶部
２００，２０００ 秘密情報復元装置
２１０，２１００ 復元制御部
２２０，２２００ 復元条件入力手段、復元条件入力部
２３０，２３００ 分散情報入力手段、分散情報入力部
２４０，２４００ 係数情報復元手段、係数情報復元部
２５０，２５００ 秘密情報復元手段、秘密情報復元部
２６０，２６００ 出力手段、秘密情報出力部
２７０，２７００ 情報記憶部
【技術分野】
【０００１】
本発明は、秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムに係り、特に、特に、パスワードや個人情報などの秘密情報を複数の情報群に分散符号化し、これらのうち、幾つか以上の分散された情報により元の秘密情報を復元可能とする秘密分散法を用いたセキュリティ技術における、秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ネットワーク上でパスワードや個人情報、暗号鍵情報といった各種情報のセキュリティ（安全性）を保つために、暗号技術が用いられる。この際、ユーザ（利用者）の認証に用いられるパスワードや個人情報、共通鍵暗号に用いられる共通鍵や公開鍵暗号に用いる秘密鍵といった秘密情報の保管に関して、秘密情報の紛失や破壊、漏洩や盗難といった恐れがあり、特に、単一の箇所に保管する場合などは、秘密情報の紛失や破壊、複数の箇所に保管する場合などは秘密情報の漏洩や盗難の可能性が高くなってしまうという問題がある。
【０００３】
これらの問題を解決し、各秘密情報を安全に保管する方法のひとつとして、秘密分散法がある。
【０００４】
秘密分散法は、元の秘密情報を複数の情報に分散して複数の箇所に保管し、この分散された情報（以下、分散情報）を全て、あるいは幾つか合わせることにより、元の秘密情報を復元可能とする方法である。
【０００５】
秘密分散法の実現方法のひとつとして（ｋ，ｎ）閾値秘密分散法がある。これは、分散情報を配布する数である２以上の整数の分散数ｎと、秘密情報Ｓの復元に必要な分散情報の最低数である２以上ｎ以下の整数の閾値ｋから、秘密情報Ｓを定数項とする（ｋ−１）次の多項式ｆ（ｘ）を、
ｆ（ｘ）＝Ｓ＋Ｒ１ｘ＋…Ｒｋ−１ｘｋ−１（mod P）
（Ｒ１，…，Ｒｋ−１：乱数、Ｐ：素数）
として作成し、元の秘密情報Ｓを所有あるいは、預託により分配する秘密情報分配者は、分配情報を保管する各分散情報保持者ｉ（ｉ＝１，２，…，ｎ）に対して、分散情報Ｗｉ＝ｆ（ｉ）を分配するものである。
【０００６】
この（ｋ，ｎ）閾値秘密分散法は、ｎ個の分散情報の内、任意のｋ個の分散情報がそろえば、ｆ（ｘ）に関する連立方程式を解くことにより元の秘密情報Ｓを復元できるが、任意の（ｋ−１）個までの分散情報が揃ってもｆ（ｘ）に関する連立方程式を解くことはできないため、元の秘密情報Ｓを復元できないという特徴を持つ。従って、（ｎ−ｋ）個までの分散情報が紛失や破壊により損なわれても元の秘密情報Ｓが復元可能であり、（k−１）個までの分散情報が漏洩や盗難により得られても元の秘密情報Ｓは復元できないという、秘密情報を安全に保管する方法が実現できる。但し、個々に生成される分散情報Ｗｉの大きさは秘密情報Ｓの大きさに等しく、分散効率が悪いことが知られている（例えば、非特許文献１参照）。
【０００７】
さらに、（ｋ，ｎ）閾値秘密分散法の拡張として、（ｄ，ｋ，ｎ）閾値秘密分散法、別名ランプ型秘密分散法がある。これは、分散情報を配布する数である２以上の整数の分散数ｎと、秘密情報Ｓの完全な復元に必要な分散情報の最低数である２位以上ｎ以下の整数の閾値ｋと、閾値ｋに対して秘密情報Ｓの部分的な復元を許容する分散情報の不足数を決定する２以上ｋ以下の整数の分散数ｄから、秘密情報Ｓを、Ｓ１，Ｓ２，…，Ｓｄに分割し、これらの分割した秘密情報（以下、分割情報）を定数項とする（ｋ−１）次の多項式ｆ（ｘ）を、
ｆ（ｘ）＝Ｓ１＋Ｓ２ｘ＋…＋Ｓｄｘｄ−１＋Ｒ１ｘｄ＋…＋Ｒｋ−ｄｘｋ−１（mod Ｐ）
（Ｒ１，…，Ｒｋ−ｄ：乱数、Ｐ：素数）
として作成し、元の秘密情報Ｓを所有あるいは預託による分配する秘密情報分配者は、分散情報を保管する各分散情報保持者ｉ（ｉ＝１，２，…，ｎ）に対して、分散情報Ｗｉ＝ｆ（ｉ）を算出して分配するものである。
【０００８】
この（ｄ，ｋ，ｎ）閾値秘密分散法は、（ｋ，ｎ）閾値秘密分散法と同様に、ｎ個の分散情報の内、任意のｋ個の分散情報が揃えば、ｆ（ｘ）に関する連立方程式を解くことにより元の秘密情報Ｓを復元できるが、任意の（ｋ−ｄ）個までの分散情報が揃ってもｆ（ｘ）に関する連立方程式を解くことはできないため、元の秘密情報Ｓは復元できないという特徴をもつ。また、ｄ個に分割した秘密情報Ｓ１，Ｓ２，…，Ｓｄを用いるため、算出した分散情報Ｗｉの大きさが、元の秘密情報Ｓに対してｄ分の１で済むため、（ｋ，ｎ）閾値秘密分散法に比べて、分散効率がよいことが知られている。但し、任意の（ｋ−ｄ＋１）個から（ｋ−１）個までの分散情報が揃った場合には、ｆ（ｘ）に関する連立方程式から分割情報Ｓ１，Ｓ２，…，Ｓｄに関する関係式が求められるため、分割情報Ｓ１，Ｓ２，…，Ｓｄとして可能な値を得ることができ、元の秘密情報Ｓを部分的に復元することができる（例えば、非特許文献２参照）。
【非特許文献１】A. Shamir, “How to Share a Secret”, Commun. of ACM Vol.22, No.11, PP.612-613, 1979
【非特許文献２】G. R. Blakley, C. Meadows, “Security of ramp schemes”, Proc. of Crypto’84, Lecure Notes on comput. Sci., 106, pp.242-268, 1984
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の（ｄ，ｋ，ｎ）閾値秘密分散法には、秘密情報をＳをｄ個の分割情報Ｓ１，Ｓ２，…，Ｓｄに分割することで、生成される分散情報Ｗｉの大きさをｄ分の１に抑え、分散効率を上げることができる一方で、任意の（ｋ−ｄ＋１）個から（ｋ−１）個までの分散情報を揃えた場合には分割情報Ｓ１，Ｓ２，…，Ｓｄに関する関係式が簡単に求められるため、分割情報Ｓ１，Ｓ２，…，Ｓｄとして可能な値が容易に推測できてしまい、秘匿した情報の安全性に問題があった。
【００１０】
例えば、ｋ＝３、ｄ＝２、とした場合に、分散関数ｆ（ｘ）は、
ｆ（ｘ）＝Ｓ１＋Ｓ２・ｘ＋Ｒ１・ｘ２ （mod Ｐ）
で表現され、この分散関数により生成される任意の２個の分散情報ＷａとＷｂ（０＜ａ，ｂ＜Ｐ，ａ≠ｂ）は、以下の連立方程式で表される。
【００１１】
Ｗａ＝Ｓ１＋Ｓ２ａ＋Ｒ１ａ２
Ｗｂ＝Ｓ１＋Ｓ２ｂ＋Ｒ１ｂ２
従って、この２個の分散情報の連立方程式を解くことで、Ｓ１とＳ２の関係式が次のような一次式の形で得られる。
【００１２】
【数１】
このような関係式があれば、Ｓ１として可能な値に対し、Ｓ２として可能な値を容易に計算できるため、結果として秘密情報Ｓが推測できてしまう恐れがある。
【００１３】
本発明は、このような中間的な復元状態における情報漏洩の問題に鑑みなされたもので、（ｄ，ｋ，ｎ）閾値秘密分散法において、ｋ個の分散情報が揃わない限り、分散情報Ｓ１，Ｓ２，…，Ｓｄを求めることも推測することもできないようにし、効率的かつ安全な秘密情報Ｓの分散を可能とする秘密情報分散装置及び秘密情報復元装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
図１は、本発明の原理を説明するための図である。
【００１５】
本発明（請求項１）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散方法であって、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップ（ステップ１）と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップ（ステップ２）と、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップ（ステップ３）と、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップ（ステップ４）と、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップ（ステップ５）と、を行う。
【００１６】
本発明（請求項２）は、係数情報計算ステップ（ステップ３）において、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する。
【００１７】
本発明（請求項３）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元方法であって、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップ（ステップ１０）と、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップ（ステップ１１）と、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップ（ステップ１２）と、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップ（ステップ１３）と、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップ（ステップ１４）と、を行う。
【００１８】
図２は、本発明の原理構成図である。
【００１９】
本発明（請求項４）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散装置であって、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力手段１２０と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力手段１３０と、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算手段１４０と、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算手段１５０と、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力手段１６０と、を有する。
【００２０】
また、本発明（請求項５）は、係数情報計算手段１４０が、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する手段を含む。
【００２１】
本発明（請求項６）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元装置であって、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力手段２２０と、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力手段２３０と、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元手段２４０と、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元手段２５０と、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力手段２６０と、を有する。
【００２２】
本発明（請求項７）は、秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散プログラムであって、
コンピュータに、
入力された秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、を実行させるプログラムである。
【００２３】
また、本発明（請求項８）は、係数情報計算ステップにおいて、
入力された秘密情報を分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と、乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する。
【００２４】
本発明（請求項９）は、元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元プログラムであって、
コンピュータに、
入力された元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
復元条件に基づいて複数個の分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、を実行させるプログラムである。
【発明の効果】
【００２５】
上記のように本発明によれば、秘密情報Ｓを分散符号化する際に、ｄ（ｄ＝分割数）分の１の大きさの分散情報Ｗｉを任意の個数生成し、生成した分散情報の内、任意のｋ個が揃わない限り、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められず、従って、秘密情報Ｓが復元できないように、秘密情報Ｓを分散符号化することができる。これにより、効率的かつ、安全な秘密情報の分散符号化を実現することができる。
【発明を実施するための最良の形態】
【００２６】
以下、図面と共に本発明の実施の形態を説明する。
【００２７】
図３は、本発明の概要を説明するための図である。
【００２８】
本発明は、秘密情報Ｓを分散符号化して、任意の個数のｄ（ｄは分割数）分の１の大きさの分散情報Ｗｉを生成し、生成した分散情報の内、任意のｋ個が揃わない限り、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められないように、秘密情報Ｓの分散を可能にするものである。
【００２９】
［第１の実施の形態］
本実施の形態では、秘密情報の分散について説明する。
【００３０】
秘密情報の分散に必要な条件と秘密情報Ｓとを入力して、秘密情報Ｓをｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄを、最大の分割情報Ｓｔ（１≦ｔ≦ｄ）よりも大きな素数Ｐと、素数Ｐよりも小さく０でない（ｋ−ｄ）個の乱数Ｒｉ（１≦ｉ≦ｋ−ｄ）からなる分散関数ｆ（ｘ）として、
ｆ（ｘ）＝Ｓ１＋Ｓ２ｘ＋…＋Ｓｄｘｄ−１＋Ｒ１ｘｄ＋…＋Ｒｋ−ｄｘｋ−１ (mod Ｐ)
の形で表現される（ｋ−１）次の多項式を用いてｋ個の係数情報Ｆｉ（１≦ｉ≦ｋ）を生成し、生成したｋ個の係数情報Ｆｉと素数Ｐからなる分散関数ｇ（ｘ）として、
ｇ（ｘ）＝Ｆ１＋Ｆ２ｘ＋…＋Ｆｋｘｋ−１ （mod Ｐ）
の形で表現される式を用いて任意の個数の分散情報Ｗｉ＝ｇ（ｉ）を生成する。
【００３１】
以下に詳細に説明する。
【００３２】
図４は、本発明の第１の実施の形態における秘密情報分散装置の構成図である。
【００３３】
本装置１００は、秘密情報の分散処理の各過程の制御を行う分散制御部１１０、分散条件の入力を受け付ける分散条件入力部１２０、分散の対象とする秘密情報Ｓの入力を受け付ける秘密情報入力部１３０、係数情報Ｆｉを算出する係数情報計算部１４０、分散情報Ｗｉを算出する分散情報計算部１５０、生成された分散情報を情報番号と組にして出力する分散情報出力部１６０、入力された分散条件、秘密情報、分散情報等を記憶する情報記憶部１７０から構成される。
【００３４】
以下の例では、秘密情報Ｓを２個の分散情報Ｓ１とＳ２に分割し、４個の分散情報を分散するものとして、４個の内任意の３個の分散情報を持ち寄れば秘密情報Ｓを復元でき、２個ないし１個の分散情報からは秘密情報Ｓを一切推測できないように、秘密情報Ｓの分散情報を生成する。
【００３５】
図５は、本発明の第１の実施の形態における秘密情報分散装置の動作を示す。
【００３６】
ステップ１０１） 分散条件入力部１２０は、分散条件の入力を受け付ける。入力を受け付ける分散条件は、例えば、生成する分散情報の個数として分散数ｎ、秘密情報Ｓの復元を可能とする分散情報の個数として閾値ｋ、秘密情報を分割する個数として分割数ｄとする。例えば、本実施の形態では、４個の分散情報を生成することから分散数ｎ＝４、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また秘密情報Ｓを２個の分割情報に分割することから分割数ｄ＝２が入力されたものとする。入力された分散条件は、情報記憶部１７０や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような分散条件は入力を受け付けるのではなく、所定の分散条件として情報記憶部１７０などに予め記憶しておいてもよい。
【００３７】
ステップ１０２） 次に、秘密情報入力部１３０は、分散の対象とする秘密情報Ｓの入力を受け付ける。本実施の形態では、秘密情報Ｓとして４桁の１６進文字列Ｓ＝３ＣＡＢが入力されたものとする。
【００３８】
ステップ１０３） 秘密情報入力部１３０は、既に入力された分散条件の分散数ｄ＝２に従って、秘密情報Ｓを２個の分割情報に分割して、情報記憶部１７０や内部メモリ（図示せず）などに一時的に記憶する。本実施の形態における分散情報をＳ１＝３Ｃ，Ｓ２＝ＡＢとする。
【００３９】
なお、本実施の形態では、分散条件入力部１２０において分散条件として閾値ｋと分散数ｄの入力を受け付け、秘密情報入力部１３０において秘密情報Ｓの入力を受け付けてｄ個の分割情報に分割するものとしたが、予めｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄの入力を受け付けて分割数ｄを求めるようにしても構わない。また、本実施の形態では、秘密情報Ｓに対する分割情報を秘密情報Ｓの上位２桁と下位２桁で分割しているが、本発明は秘密情報Ｓの分割方法を規定するものではなく、例えば、奇数ビットと偶数ビットのようにビット単位で分割しても構わないし、分割情報Ｓ０とＳ１の積が秘密情報Ｓとなるように分割するなどの方法も考えられる。
【００４０】
さらに、本実施の形態では、分散の対象とする秘密情報Ｓを１６進文字列に限定するものではなく、また単なる文字列に限定するものでもない。数値情報、文字列などの分散関数による演算が可能であればどのような情報でもよく、また文書や画像データなどのマルチメディアなどを対象としてもよい。
【００４１】
また、本実施の形態は、分散条件及び秘密情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して他の装置から入力するようにしても構わない。
【００４２】
ステップ１０４） 次に、係数情報計算部１４０において、閾値ｋと分割数ｄ及び分割情報に基づいて、係数情報Ｆｉを算出するための分散関数を生成し、ｋ個の係数情報Ｆｉを算出する。まず、各分割情報Ｓｄよりも大きな素数Ｐを決定し、素数Ｐよりも小さく０でない乱数Ｒｊを（ｋ−ｄ）個生成し、ｋ−１次の多項式である分散関数ｆ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３，分割数ｄ＝２より、以下のような多項式が分散関数ｆ（ｘ）となる。
【００４３】
ｆ（ｘ）＝Ｓ１＋Ｓ２・ｘ＋Ｒ１・ｘ２（mod Ｐ）
本実施の形態では、分割情報Ｓ１＝３Ｃ，Ｓ２ＡＢより素数Ｐ＝ＦＢ（２５１）を得たものとする。また、乱数Ｒ１＝１Ｆを生成したものとする。なお、本実施の形態では、係数情報計算部１４０において、素数Ｐや乱数Ｒｊの値などを決定しているが、これらの値について分散条件入力部１２０において入力するようにしても構わない。また、特に素数Ｐについては秘密情報Ｓあるいは分割情報Ｓｄの長さなどに応じて、予め情報記憶部１７０に記憶した素数Ｐを選択して用いるようにしてもよい。
【００４４】
次に、係数情報計算部１４０は、上記の分散関数ｆ（ｘ）を用いてｋ個の係数情報を生成する。ここでは分散関数ｆ（ｘ）、に対し、ｘ＝１，２，３を順次代入して計算し、係数情報Ｆ１，Ｆ２，Ｆ３を算出して情報記憶部１７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、閾値ｋ＝３、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ及びＲ１＝１Ｆと素数Ｐ＝ＦＢより、係数情報はそれぞれＦ１＝０Ｂ，Ｆ２＝１８、Ｆ３＝６３を得る。図６に、係数情報計算部１４０における係数情報の計算例を示す。
【００４５】
なお、本実施の形態は係数情報Ｆ１，Ｆ２，Ｆ３を分散関数ｆ（ｘ）に順次情報番号ｘ＝１，２，３を代入することで算出したが、異なる情報番号としてｘ＝１，３，５を用いて算出した結果を係数情報Ｆ１，Ｆ２，Ｆ３としてもよい。但し、このような係数情報群を算出するための情報番号群については外部から参照できないように秘密情報分散装置１００内に予め格納されているものとする。また、このような情報番号群を毎回無作為に生成した上で、情報番号ｘと算出結果とを結合して、実際の係数情報Ｆ１として用いるようにすることも考えられる。
【００４６】
ステップ１０５） 次に、分散情報計算部１５０は、閾値ｋと分散数ｎ及び係数情報に基づいて、分散情報Ｗｉを算出するための分散関数を生成し、ｎ個の分散情報Ｗｉを算出する。係数情報計算部１４０において求めた素数Ｐ及び係数情報Ｆｉより、ｋ−１次の多項式である分散関数ｇ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３より、以下のような多項式が分散関数ｇ（ｘ）となる。
【００４７】
ｇ（ｘ）＝Ｆ１＋Ｆ２・ｘ＋Ｆ３・ｘ２ （mod Ｐ）
分散情報計算部１５０は、上記の分散関数ｇ（ｘ）を使ってｎ個の分散情報Ｗｉを生成する。ここでは、分散関数ｇ（ｘ）に対し、ｘ＝１，２，３，４を順次代入して計算し、分散情報Ｗ１，Ｗ２，Ｗ３，Ｗ４を算出して情報記憶部１７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、分散数ｎ＝４、係数情報Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３より、分散情報はそれぞれＷ１＝８６，Ｗ２＝ＣＣ，Ｗ３＝ＤＤ，Ｗ４＝Ｂ９を得る。図７に、分散情報計算部１５０における分散情報の計算例を示す。
【００４８】
なお、本実施の形態において、分散関数ｇ（ｘ）、から分散情報を算出する際のｘの値を１０進の数字により記述しているが、可能なｘの値を１０進数の数字に規定するものではない。分散関数ｆ（ｘ）に則って分散情報を算出できればよく、例えば、１６進数であったり文字列であったりしても構わない。また、係数情報計算部１４０における分散関数ｆ（ｘ）と、分散情報計算部１５０における分散関数ｇ（ｘ）とで、同じ素数Pの値を使用するものとして記述しているが、分散関数ｇ（ｘ）における素数Ｐを分散関数ｆ（ｘ）における素数Ｐよりも大きな値としてもよい。
【００４９】
ステップ１０６） 分散情報出力部１６０は、分散情報計算部１５０において生成した分散情報を、分散情報を算出したｘの値（以下、情報番号）と組にして情報記憶部１７０に出力する。本実施の形態における出力は、（１，８６），（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）となる。
【００５０】
なお、本実施の形態は、分散情報出力部１６０における分散情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。但し、個々の分散情報を別個に出力することが望ましい。また、分散情報は直線各分散情報保持者または各分散保持装置に出力するようにし、出力の際に個々の保持者ないしは装置に合わせて暗号化するなどの手段も考えることもできる。
【００５１】
また、本実施の形態では、情報番号ｉと分散情報Ｗｉの組を出力するものとしたが、個々の分散情報が分散関数ｇ（ｘ）に何を代入して算出したものかがわかればよく、例えば、ｉとＷｉを連結して１８６，２ＣＣ，３ＤＤ，４Ｂ９のように出力しても良いし、また、例えば、出力先によって情報番号ｉが予め指定されている場合は分散情報Ｗｉのみを出力するようにしてもよい。
【００５２】
［第２の実施の形態］
以下、上記の第１の実施の形態により生成した分散情報から、分散情報Ｓ１及びＳ２，更に、秘密情報Ｓを復元する場合について説明する。
【００５３】
図８は、本発明の第２の実施の形態における秘密情報復元装置の構成図である。
【００５４】
秘密情報復元装置２００は、秘密情報復元装置２００における秘密情報の復元処理の各過程の制御を行う復元制御部２１０、復元条件の入力を受け付ける復元条件入力部２２０、復元に必要な個数の分散情報と情報番号の入力を受け付ける分散情報入力部２３０、係数情報を算出する係数情報復元部２４０、分割情報を算出する秘密情報復元部２５０、分割情報群を結合し秘密情報を出力する秘密情報出力部２６０、復元条件、分散情報と情報番号、秘密情報等を格納する情報記憶部２７０から構成される。
【００５５】
図９は、本発明の第２の実施の形態における秘密情報復元装置の動作を示す。
【００５６】
ステップ２０１） 復元条件入力部２２０は、復元条件の入力を受け付ける。入力を受け付ける復元条件は、例えば、秘密情報Ｓの復元に必要な分散情報の個数として閾値ｋ、秘密情報の分割数ｄ、素数Ｐなどとする。例えば、本実施の形態では、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、または、秘密情報Ｓを２個の分割情報に分割したことから分割数ｄ＝２、素数ＰとしてＰ＝ＦＢが入力されたものとする。入力された復元条件は、情報記憶部２７０や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような復元条件は入力を受け付けるのではなく、所定の復元条件として情報記憶部２７０などに予め記憶しておいてもよい。
【００５７】
ステップ２０２） 次に、分散情報入力部２３０は、復元に必要な個数の分散情報Ｗｉと情報番号ｉの入力を受け付ける。本実施の形態では、分散情報として（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）が入力されたものとする。入力された分散情報は、情報記憶部２７０や内部メモリ（図示せず）などに一時的に記憶する。
【００５８】
なお、本実施の形態では、分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、予め情報番号ｉが分かっている場合、例えば、入力元毎に決まっている場合には、分散情報Ｗｉのみを受け付けるようにしてもよい。また、入力元の情報に合わせて情報記憶部２７０より入力元に対応する情報番号を取得するようにしてもよい。なお、本実施の形態は復元条件及び分散情報の入力及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して複数の他の装置から入力しても構わない。
【００５９】
ステップ２０３） 次に、係数情報復元部２４０において、閾値ｋと素数Ｐ、入力された情報番号及び分散情報群から係数情報Ｆｉを算出するための復元関数を生成し、ｋ個の係数情報Ｆｉを算出する。本実施の形態では、入力された閾値ｋ＝３、素数Ｐ＝ＦＢ、分散情報群（２，ＣＣ），（３，ＤＤ），（４，Ｂ９）から、係数情報復元部２４０は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【００６０】
Ｗ２＝Ｆ１＋２Ｆ２＋４Ｆ３＝ＣＣ (mod ＦＢ)
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝ＤＤ (mod ＦＢ
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝Ｂ９ （mod ＦＢ）
次に、係数情報復元部２４０は、この連立方程式から計算により係数情報Ｆ１，Ｆ２，Ｆ３を求める。連立方程式を掃き出し法により展開すると、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【００６１】
Ｆ１＝６Ｗ２−８ｗ３＋３Ｗ４＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗ２＋１２Ｗ３−５Ｗ４）／２＝１８ （mod ＦＢ）
Ｆ３＝（Ｗ２−２Ｗ３＋Ｗ４）／２＝６３ （mod ＦＢ）
このように算出した係数情報Ｆ１，Ｆ２，Ｆ３を情報記憶部２７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれ、Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３であり、正しい係数情報が得られていることが分かる。図１０に、係数情報復元部２４０における係数情報の計算例を示す。
【００６２】
なお、異なる分散情報の集合として（１，８６），（３，ＤＤ），（４，Ｂ９）が入力された場合でも、同様に連立方程式を生成して掃き出し法により展開することで、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【００６３】
Ｗ１＝Ｆ１＋Ｆ２＋Ｆ３＝８６ （mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝ＤＤ (mod ＦＢ)
Ｗ４＝Ｆ１＋４Ｆ３＋１６Ｆ３＝Ｂ９ （mod ＦＢ）
この連立方程式に対する展開結果及び計算情報の算出結果は以下のようになる。
【００６４】
Ｆ１＝２Ｗ１−２Ｗ３＋Ｗ４＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗ１＋１５Ｗ３−８Ｗ４）／６＝１８ (mod ＦＢ)
Ｆ３＝（Ｗ１−３Ｗ３＋２Ｗ４）／６＝６３ （mod ＦＢ）
このように、分散情報入力部２３０においてどのような組み合わせで分散情報Ｗ１が入力されても、閾値ｋ個の分散情報があれば、係数情報復元部２４０は係数情報を全て正しく復元することができる。
【００６５】
なお、本実施例では、係数情報復元部２４０において分散情報群を表す連立方程式を生成し、掃き出し法により展開することで、各係数情報についての方程式群を生成して、各係数情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の分散情報群から同じく閾値ｋ個の係数情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７０から取得し、各係数情報を算出する方法などが考えられる。以下は、閾値ｋ＝３の場合に入力された分散情報群を（ａ，Ｗａ），（ｂ，Ｗｂ），（ｃ，Ｗｃ）とした場合の自明な方程式群の例である。
【００６６】
Ｆ１＝｛−ｂｃ（ｂ−ｃ）Ｗａ−ｃａ（ｃ−ａ）Ｗｂ−ａｂ（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
Ｆ２＝｛（ｂ＋ｃ）（ｂ−ｃ）Ｗａ＋（ｃ＋ａ）（ｃ−ａ）Ｗｂ＋（ａ＋ｂ）（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
Ｆ３＝｛−（ｂ−ｃ）Ｗａ−（ｃ−ａ）Ｗｂ−（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） (mod ＦＢ)
上記の方程式群に、（２，ＣＣ），（３，ＤＤ）（４，Ｂ９）を代入すると、正しく各係数情報を算出でき、連立方程式を解くよりも高速に処理できる。
【００６７】
Ｆ１＝６Ｗａ−８Ｗｂ＋３Ｗｃ＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗａ＋１２Ｗｂ−５Ｗｃ）／２＝１８ (mod ＦＢ)
Ｆ３＝（Ｗａ−２Ｗｂ＋Ｗｃ）／２＝６３ （mod ＦＢ）
ステップ２０５） 次に、秘密情報復元部２５０は、閾値ｋ、分割数ｄ、素数Ｐと係数情報復元部２４０において算出した各係数情報Ｆｉから、分割情報Ｓｔ（１≦ｔ≦ｄ）を算出するための復元関数を生成し、ｄ個の分割情報Ｓｔを算出する。本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝１８，Ｆ３＝６３から、秘密情報復元部２５０は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【００６８】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ (mod ＦＢ)
Ｆ２＝Ｓ１＋２Ｓ２＋４Ｒ１＝１８ (mod ＦＢ)
Ｆ３＝Ｓ１＋３Ｓ２＋９Ｒ１＝６３ (mod ＦＢ)
次に、秘密情報復元部２５０は、この連立方程式から計算により分割情報Ｓ１，Ｓ２を求める。連立方程式を掃き出し法により展開すると、各分割情報についての方程式群が生成でき、各分割情報が算出できる。
【００６９】
Ｓ１＝３Ｆ１−３Ｆ２＋Ｆ３＝３Ｃ
Ｓ２＝（−５Ｆ１＋８Ｆ２−３Ｆ３）／２＝ＡＢ （mod ＦＢ）
このように算出した分割情報Ｓ１，Ｓ２を情報記憶部２７０または内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれＳ１＝３Ｃ，Ｓ２＝ＡＢであり、正しい分割情報が得られていることが分かる。図１１に、秘密情報復元部２５０における秘密情報の計算例を示す。
【００７０】
なお、本実施の形態では、秘密情報復元部２５０において、係数情報群を表す連立方程式を生成し、掃き出し法により展開することで、各分割情報についての方程式群を生成して、各分割情報を算出しているが、このような数学的な処理の手順を実施の形態では特に規定するものではない。閾値ｋ個の係数情報群から分割数ｄ個の分割情報群を算出できればよく、例えば、上記のような自明な方程式群を予め情報記憶部２７０から取得し、各分割情報を算出するなどの方法などが考えられる。
【００７１】
また、本実施の形態は、係数情報Ｆ１，Ｆ２，Ｆ３を分散関数ｆ（ｘ）に順次情報番号ｘ＝１，２，３を代入した連立方程式を生成した上で、分割情報Ｓ１，Ｓ２を算出したが、係数情報Ｆ１，Ｆ２，Ｆ３が異なる情報番号としてｘ＝１，３，５を代入して計算されている場合には、同様に分散関数ｆ（ｘ）にｘ＝１，３，５を代入した連立方程式を生成して算出するものとする。このような係数情報群を算出するための情報番号群については外部から参照できないように秘密情報復元装置２００内に予め格納されているものとする。また、無作為に生成した情報番号群が実際の係数情報Ｆｉに含まれている場合には、これを分割して用いるようにすることも考えられる。
【００７２】
ステップ２０６） 秘密情報出力部２６０は、秘密情報復元部２５０において算出したｄ個の分割情報群を結合し、秘密情報Ｓとして出力する。本実施の形態では、Ｓ１＝３Ｃ，Ｓ２＝ＡＢから、結合すればＳ＝３ＣＡＢであり、正しい秘密情報が得られていることが分かる。
【００７３】
なお、本実施の形態は、秘密情報出力部２６０における秘密情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。また、分類情報群を結合して秘密情報Ｓとして出力するのではなく、個々の分割情報群をそれぞれ出力しても構わない。
【００７４】
本実施の形態では、分散情報入力部２３０において閾値ｋ個の分散情報の入力を受け付けるものとしたが、仮に分割情報入力部２３０が復元に必要な個数よりも少ない数の分散情報Ｗｉと情報番号ｉの入力を受け付けたとしても、係数情報復元部２４０において生成する連立方程式の数は不足しており、各係数情報Ｆｉの関係式を得ることはできるが、計算により各係数情報群を求めることはできない。
【００７５】
例えば、閾値ｋ＝３の時に、２個の分散情報を仮にＷａ＝ｆ（ａ）、Ｗｂ（ｂ）とした場合、その分散情報群を表す連立方程式は次のようになる。
【００７６】
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
連立方程式の数が閾値ｋ＝３よりも少ないため、これらの連立方程式からは係数情報Ｆ１とＦ２，Ｆ１とＦ３、Ｆ２とＦ３についての次のような関係式しか得ることができない。
【００７７】
（ｂ＋ａ）Ｆ１＋ｂａＦ２＝（ｂ２Ｗａ−ａ２Ｗｂ）／（ｂ−ａ） (mod Ｐ)
Ｆ１−ｂａＦ３＝（ｂＷａ−ａＷｂ）／（ｂ−ａ） (mod Ｐ)
Ｆ２＋（ａ＋ｂ）Ｆ３＝（Ｗａ−Ｗｂ）／（ａ−ｂ） (mod Ｐ)
このように、入力された分散情報の数が閾値ｋよりも少ない場合には、係数情報復元部２４０において係数情報Ｆ１，Ｆ２，Ｆ３を求めることができず、よって秘密情報復元部２４０において、分割情報群Ｓ１，Ｓ２を求めることもできない。従って、秘密情報Ｓが復元されることはない。
【００７８】
以上のように、第１の実施の形態における秘密情報分散装置１００により秘密情報Ｓから生成した分散情報については、第２の実施の形態における秘密情報復元装置２００において、個々の分散情報Ｗｉの大きさは秘密情報Ｓのｄ分の１であって、ｎ個の分散情報のうち、閾値ｋ個の任意の分散情報を持ち寄れば、ｋ個の係数情報Ｆｉを復元でき、よって全ての分割情報Ｓｔを復元して、秘密情報Ｓを完全に復元することができる。
【００７９】
一方、ｋ個未満の分散情報からは係数情報Ｆ１を復元できないため、分割情報Ｓ１，Ｓ２，…，Ｓｄが一切求められず、秘密情報Ｓを復元することはできない。
【００８０】
［第３の実施の形態］
《秘密情報分散装置》
図１２は、本発明の第３の実施の形態における秘密情報分散装置の構成を示す。
【００８１】
同図に示す秘密情報分散装置１０００は、当該秘密情報分散装置１０００における秘密情報分散処理の処理を制御する分散制御部１１００、秘密情報を分散するための条件の入力を受け付ける分散条件入力部１２００、分散符号化の対象とする秘密情報の入力を受け付ける秘密情報入力部１３００、複数個に分割した秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、算出した係数情報と複数個に分割した秘密情報と乱数を係数とする多項式関数によって、繰り返し複数個の係数情報を算出する係数情報計算部１４００、係数情報計算部１４００で算出した複数個の係数情報を係数とする多項式関数によって任意の個数の分散情報を算出する分散情報計算部１５００、算出した分散情報群を出力する分散情報出力部１６００、入力された条件、秘密情報、計算結果等を記憶する情報記憶部１７００から構成される。
【００８２】
以下では、秘密情報Ｓを２個の分割情報Ｓ１，Ｓ２に分割した上で、４個の分散情報に分散するものとして、４個の内、任意の３個の分散情報を持ち寄れば秘密情報Ｓを完全に復元でき、２個乃至１個の分散情報からは秘密情報Ｓを一切推測できないように、秘密情報Ｓの分散情報を生成する秘密情報分散処理について説明する。
【００８３】
図１３は、本発明の第３の実施の形態における秘密情報分散装置の動作説明図である。
【００８４】
ステップ１１０１） 分散条件入力部１２００において、分散条件の入力を受け付ける。入力された分散条件は、例えば、生成する分散情報の個数として分散数ｎ、秘密情報Ｓの復元を可能とする分散情報の個数として閾値ｋ、秘密情報を分割する個数としての分割数ｄとする。例えば、本実施の形態では、４個の分散情報を生成することから分散数ｎ＝４、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また、秘密情報Ｓを２個の分割情報に分割することから分割数ｄ＝２が入力されたものとする。入力された分散条件は、情報記憶部１７００や内部メモリ（図示せず）などに一時的に記憶するものとする。また、このような分散条件は入力を受け付けるのではなく、所定の分散条件として情報記憶部１７００などに予め記憶しておいてもよい。
【００８５】
ステップ１１０２） 次に、秘密情報入力部１３００は、分散の対象とする秘密情報Ｓの入力を受け付ける。本実施の形態では、秘密情報Ｓとして４桁の１６進文字列Ｓ＝３ＣＡＢが入力されたものとする。秘密情報入力部１３００は、既に入力された分散条件の分割数ｄ＝２に従って、秘密情報Ｓを２個の分割情報に分割して、情報記憶部１７００や内部メモリ（図示せず）などに一時的に記憶する。本実施の形態における分割情報をＳ１＝３Ｃ，Ｓ２＝ＡＢとする。
【００８６】
なお、本実施の形態では、分散条件入力部１２００において分散条件として閾値ｋと分割数ｄの入力を受け付け、秘密情報入力部１３００において秘密情報Ｓの入力を受け付けてｄ個の分割情報に分割するものとしたが、予めｄ個に分割した分割情報Ｓ１，Ｓ２，…，Ｓｄの入力を受け付けて分散数ｄを求めるようにしても構わない。また、本実施の形態では秘密情報Ｓに対する分割情報を秘密情報Ｓの上位２桁と下位２桁で分割しているが、本発明は、秘密情報Ｓの分割方法を規定するものではなく、例えば、奇数ビットと偶数ビットのようにビット単位で分割しても構わないし、分割情報Ｓ０とＳ１の積が秘密情報Ｓとなるように分割するなどの方法も考えられる。
【００８７】
さらに、本実施の形態は、分散の対象とする秘密情報Ｓを１６進文字列に限定するものではなく、また、単なる文字列に限定するものでもない。数値情報、文字列などの分散関数による演算が可能であれば、どのような情報でもよく、また、文書や画像データなどのマルチメディアなども対象としてもよい。
【００８８】
また、本実施の形態は、分散条件及び秘密情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して他の装置から入力するようにしても構わない。
【００８９】
ステップ１１０３） 次に、係数情報計算部１４００において、閾値ｋと分割数ｄ及び分割情報に基づいて、係数情報Ｆｉを算出するための分散関数を生成し、ｋ個の係数情報Ｆｉを算出する。
【００９０】
まず、各分割情報Ｓｄよりも大きな素数Ｐを決定し、素数Ｐよりも小さく０でない乱数Ｒｊを（ｋ−ｄ）個生成し、ｋ−１次の多項式である分散関数ｆ（ｘ）を生成する。本実施の形態における分散関数ｆ（ｘ）を以下のように定義する。
【００９１】
【数２】
また、本分散関数ｆ（ｘ）による係数情報Ｆｉの算出式を以下のようにする。
【００９２】
Ｆｉ＝ｆ（Ｆｉ−１）
従って、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２より、Ｓ３＝Ｒ１として、以下のような分散関数ｆ（ｘ）により係数情報Ｆｉが算出される。
【００９３】
Ｆｉ＝ｆ（ｘ）＝Ｓ１＋Ｆｉ−１Ｓ２・ｘ＋Ｆｉ−１２・Ｒ１ （mod Ｐ）
本実施の形態では、係数情報計算部１４００において、素数Ｐや乱数Ｒｊの値などを決定しているが、これらの値について分散条件入力部１２００において入力するようにしても構わない。また、特に、素数Ｐについては秘密情報Ｓあるいは分割情報Ｓｄの長さなどに応じて予め情報記憶部１７００に記憶した素数Ｐを選択して用いるようにしてもよい。
【００９４】
ステップ１１０４） 次に、係数情報計算部１４００は、上記の分散関数ｆ（ｘ）を使ってｋ個の係数情報を生成する。本実施の形態では、初期係数情報Ｆ０＝１とおくものとして、閾値ｋ＝３、分割情報Ｓ１＝３Ｃ、Ｓ２＝ＡＢ及びＲ１＝１Ｆと素数Ｐ＝ＦＢより、まず、係数情報Ｆ１を算出する。算出の結果、Ｆ１＝０Ｂとなる。
【００９５】
次いで、順次係数情報の算出結果を用いて、繰り返し演算し、係数情報Ｆ２＝ＡＡ，Ｆ３＝５Ｆを得る。算出した係数情報Ｆ１，Ｆ２，Ｆ３は、情報記憶部１７００または、内部メモリ（図示せず）などに一時的に記憶する。図１４に係数情報計算部１４００における係数情報の計算例を示す。
【００９６】
なお、係数情報計算部１４００において生成するｋ個の係数情報については、値の重複がないようにしなければならない。例えば、本実施の形態においては、初期係数情報Ｆ０＝１からＦ１≠１でなければならず、同様にＦ２≠１，０Ｂで、Ｆ３≠１，０Ｂ，ＡＡでなければならない。係数情報計算部１４００はこのような値の重複をチェックし、重複があった場合には再度乱数Ｒ１の再生成と、係数情報の再生成を行う。
【００９７】
ステップ１１０５） 次に、分散情報計算部１５００は、閾値ｋと分散数ｎ及び係数情報に基づいて、分散情報Ｗｉを算出するための分散関数を生成し、ｎ個の分散情報Ｗｉを算出する。係数情報計算部１４００において求めた素数Ｐ及び係数情報Ｆｉより、ｋ−１次の多項式である分散関数ｇ（ｘ）を生成する。本実施の形態では、閾値ｋ＝３より、以下のような多項式が分散関数ｇ（ｘ）となる。
【００９８】
ｇ（ｘ）＝Ｆ１＋Ｆ２・ｘ＋Ｆ３・ｘ２ （mod P）
分散情報計算部１５００は、上記の分散関数ｇ（ｘ）を使って、ｎ個の分散情報Ｗｉを生成する。ここでは、分散数ｎ＝４より、分散関数ｇ（ｘ）に対し、ｘ＝１，２，３，４を順次代入してＷｘ＝ｇ（ｘ）を計算し、分散情報Ｗ１，Ｗ２，Ｗ３，Ｗ４を算出して情報記憶部１７００または、内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、係数情報Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆより、分散情報はそれぞれＷ１＝１９，Ｗ２＝Ｅ５，Ｗ３＝７９，Ｗ４＝ＣＢを得る。図１５に分散情報計算部１５００における分散情報の計算例を示す。
【００９９】
なお、本実施の形態において、分散関数ｇ（ｘ）から分散情報を算出する際のｘの値を１０進数の数字により記述しているが、可能なｘの値を１０進数の数字に規定するものではない。分散関数ｆ（ｘ）に則って分散情報を算出できればよく、例えば、１６進数であったり、文字列であったりしても構わない。また、係数情報計算部１４００における分散関数ｆ（ｘ）と、分散情報計算部１５００における分散関数ｇ（ｘ）とで、同じ素数Ｐの値を使用するものとして記述しているが、分散関数ｇ（ｘ）における素数Ｐを分散関数ｆ（ｘ）における素数Ｐよりも大きな値としてもよい。
【０１００】
ステップ１１０６） 分散情報出力部１６００は、分散情報計算部１５００において生成した分散情報を、分散情報を算出したｘの値（以下、情報番号）とを組にして出力する。本実施の形態における出力は、（１，１９），（２，Ｅ５），（３，７９），（４，ＣＢ）となる。
【０１０１】
なお、本実施の形態は、分散情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。但し、個々の分散情報を別個に出力することが望ましい。また、分散情報は直接各分散情報保持者または、各分散情報保持装置に出力するようにし、出力の際に個々の保持者乃至は装置に合わせて暗号化するなどの手段も考えることもできる。
【０１０２】
また、本実施の形態では、情報番号ｉと分散情報Ｗｉの組を出力するものとしたが、個々の分散情報が分散関数ｇ（ｘ）に何を代入して算出したものかが分かればよく、例えば、ｉとＷｉを連結して１１９，２Ｅ５，３７９，４ＣＢのように出力してもよいし、また例えば、出力先によって情報番号ｉが予め指定されている場合は分散情報Ｗｉのみを出力するようにしてもよい。
【０１０３】
分散情報の出力をもって、秘密情報分散装置１０００の動作は終了する。
【０１０４】
なお、本実施の形態は秘密分散法による分散処理を２回使用して秘密情報から係数情報の算出と分散情報の算出をそれぞれ行ったが、本発明は、複数回の秘密分散法による分散処理を連結して繰り返すことで秘密情報の推測ができないように分散情報を算出できればよく、本実施の形態の構成に制限されない。
【０１０５】
《秘密情報復元装置》
次に、秘密情報の復元について説明する。
【０１０６】
以下、本実施の形態により生成した分散情報から、分割情報Ｓ１及びＳ２、更に秘密情報Ｓを復元する場合について説明する。
【０１０７】
図１６は、本発明の第１の実施の形態における秘密情報復元装置の構成を示す。
【０１０８】
同図に示す秘密情報復元装置２０００は、秘密情報復元装置２０００における秘密情報の復元処理の各過程の制御を行う復元制御部２１００、復元条件の入力を受け付ける復元条件入力部２２００、復元に必要な個数の分散情報と秘密情報の分割数、素数などの入力を受け付ける分散情報入力部２３００、入力された複数個の分散情報群に対応する連立方程式を解くことにより複数個の係数情報を算出する係数情報復元部２４００、係数情報復元部２４００で算出された複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元部２５００、算出した秘密情報を出力する秘密情報出力部２６００、復元条件、分散情報と情報番号、秘密情報等を格納する情報記憶部２７００から構成される。
【０１０９】
図１７は、本発明の第１の実施の形態における秘密情報復元装置の動作説明図である。
【０１１０】
ステップ２１０１） 復元条件入力部２１００は、復元条件の入力を受け付ける。受け付ける復元条件は、例えば、秘密情報Ｓの復元に必要な分散情報の個数として閾値ｋ、秘密情報の分割数ｄ、素数Ｐなどとする。例えば、本実施の形態では、３個の分散情報で完全な復元を許すことから閾値ｋ＝３、また、秘密情報Ｓを２個の分割情報に分割したことから分割数ｄ＝２、素数ＰとしてＰ＝ＦＢが入力されたものとする。入力された復元条件は、情報記憶部２７００や内部メモリ（図示せず）などに一時的に記憶するものとする。
【０１１１】
また、このような復元条件は、入力を受け付けるものではなく、所定の復元条件として情報記憶部２７００などに予め記憶しておいてもよい。
【０１１２】
ステップ２１０２） 次に、分散情報入力部２３００は、復元に必要な個数の分散情報Ｗｉと情報番号ｉの入力を受け付ける。本実施の形態では、３個の分散情報として（２，Ｅ５），（３，７９），（４，ＣＢ）が入力されたものとする。入力された分散情報は、情報記憶部２７００や内部メモリ（図示せず）などに一時的に記憶する。
【０１１３】
なお、本実施の形態では、分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、予め情報番号ｉが分かっている場合、例えば、入力元毎に決まっている場合は、分散情報Ｗｉのみを受け付けるようにしてもよい。
【０１１４】
また、入力元の情報に合わせて情報記憶部２７００より入力元に対応する情報番号を取得するようにしてもよい。
【０１１５】
なお、本実施の形態は、復元条件及び分散情報の入力の方法及び形式を規定するものではない。キーボード入力やファイル入力の他に、インターネットなどの接続回線を介して複数の他の装置から入力するようにしても構わない。
【０１１６】
ステップ２１０３） 次に、情報係数復元部２４００において、閾値ｋと素数Ｐ、入力された情報番号及び分散情報群から、係数情報Ｆｉを算出するための復元関数を生成し、ｋ個の係数情報Ｆｉを算出する。本実施の形態では、入力された閾値ｋ＝３、素数Ｐ＝ＦＢ、分散情報群（２，Ｅ５），（３，７９），（４，ＣＢ）から、係数情報復元部２４００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１１７】
Ｗ２＝Ｆ１＋２Ｆ２＋４Ｆ３＝Ｅ５（mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝７９ （mod ＦＢ）
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝ＣＢ （mod ＦＢ）
次に、係数情報復元部２４００は、この連立方程式から計算により係数情報Ｆ１，Ｆ２，Ｆ３を求める。連立方程式を掃き出し法により展開すると、各係数情報についての方程式群が生成でき、各係数情報が算出できる。
【０１１８】
Ｆ１＝６Ｗ２−８Ｗ３＋３Ｗ４＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗ２＋１２Ｗ３−５Ｗ４）／２＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗ２−２Ｗ３＋Ｗ４）／２＝５Ｆ （mod ＦＢ）
このように算出した係数情報Ｆ１，Ｆ２，Ｆ３をそれぞれ情報記憶部２７００または、内部メモリ（図示せず）などに一時的に記憶する。本実施の形態では、計算結果はそれぞれ、Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆであり、正しい係数情報が得られていることが分かる。図１８に、係数情報復元部２４００における係数情報の計算例を示す。
【０１１９】
なお、異なる分散情報の集合として（１，１９），（３，７９），（４，ＣＢ）が入力された場合でも、同様に連立方程式を生成して掃き出し法により展開することで、各係数情報についての方程式が生成でき、各係数情報が算出できる。
【０１２０】
Ｗ１＝Ｆ１＋Ｆ２＋Ｆ３＝１９ （mod ＦＢ）
Ｗ３＝Ｆ１＋３Ｆ２＋９Ｆ３＝７９ (mod ＦＢ)
Ｗ４＝Ｆ１＋４Ｆ２＋１６Ｆ３＝ＣＢ （mod ＦＢ）
この連立方程式に対する展開結果及び計算情報の算出結果は以下のようになる。
【０１２１】
Ｆ１＝２Ｗ１−２Ｗ３＋Ｗ４＝０Ｂ （mod ＦＢ）
Ｆ２＝（−７Ｗ１＋１５Ｗ３−８Ｗ４）／６＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗ１−３Ｗ３＋２Ｗ４）／６＝５Ｆ (mod ＦＢ)
このように、分散情報入力部２３００においてどのような組み合わせで分散情報Ｗｉが入力されても、閾値ｋ個の分散情報があれば、係数情報復元部２４００は、係数情報を全て正しく復元することができる。
【０１２２】
なお、本実施の形態では、係数情報復元部２４００において分散情報群を表す連立方程式を生成し、掃き出し法により展開することで、各係数情報についての方程式群を生成して、各係数情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の分散情報群から同じく閾値ｋ個の係数情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７００から取得し、各係数情報を算出する方法などが考えられる。
【０１２３】
以下は、閾値ｋ＝３の場合に入力された分散情報群を（ａ，Ｗａ），（ｂ，Ｗｂ），（ｃ，Ｗｃ）とした場合の自明な方程式群の例である。
【０１２４】
Ｆ１＝｛−ｂｃ（ｂ−ｃ）Ｗａ−ｃａ（ｃ−ａ）Ｗｂ−ａｂ（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
Ｆ２＝｛（ｂ＋ｃ）（ｂ−ｃ）Ｗａ＋（ｃ＋ａ）（ｃ−ａ）Ｗｂ＋（ａ＋ｂ）（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
Ｆ３＝｛−（ｂ−ｃ）Ｗａ−（ｃ−ａ）Ｗｂ−（ａ−ｂ）Ｗｃ｝
／（ａ−ｂ）（ｂ−ｃ）（ｃ−ａ） （mod ＦＢ）
上記の方程式群に（２，Ｅ５），（３，７９），（４，ＣＢ）を代入すると、正しく各係数情報を算出でき、連立方程式を解くよりも高速に処理できる。
【０１２５】
Ｆ１＝６Ｗａ−８Ｗｂ＋３Ｗｃ＝０Ｂ (mod ＦＢ)
Ｆ２＝（−７Ｗａ＋１２Ｗｂ−５Ｗｃ）／２＝ＡＡ （mod ＦＢ）
Ｆ３＝（Ｗａ＋２Ｗｂ＋Ｗｃ）／２＝５Ｆ （mod ＦＢ）
ステップ２１０４） 次に、秘密情報復元部２５００は、閾値ｋ、分割数ｄ、素数Ｐと前述の係数情報復元部２４００において算出した各係数情報Ｆｉから、分割情報Ｓｔ（１≦ｔ≦ｄ）を算出するための復元関数を生成し、ｄ個の分割情報Ｓｔを算出する。本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝Ｆより分散関数の形は、
ｆ（ｘ）＝Ｓ１＋Ｆｉ−１Ｓ２・ｘ＋Ｆｉ−１２・Ｒ１ （mod P）
であり、これと係数情報群Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆから、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１２６】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋（０Ｂ）２・Ｒ１＝ＡＡ （mod ＦＢ）
Ｆ３＝Ｓ１＋ＡＡ・Ｓ２＋（ＡＡ）２・Ｒ１＝５Ｆ （mod ＦＢ）
ステップ２１０５） 次に、秘密情報復元部２５００は、この連立方程式から計算により分割情報Ｓ１，Ｓ２を求める。連立方程式を掃き出し法により展開すると、各分割情報が算出できる。
【０１２７】
【数３】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。算出した分割情報Ｓ１，Ｓ２は情報記憶部２７００または、内部メモリ（図示せず）などに一時的に記憶する。
【０１２８】
なお、本実施の形態では、秘密情報復元部２５００において、係数情報群を表す連立方程式を生成し、掃き出し法により展開することで、各分割情報を算出しているが、このような数学的な処理の手順を本実施の形態では特に規定するものではない。閾値ｋ個の係数情報群から分割数ｄ個の分割情報群を算出できればよく、例えば、閾値ｋから自明に求まる方程式群を予め情報記憶部２７００から取得し、各分割情報を算出する方法などが考えられる。以下は、閾値ｋ＝３の場合に係数情報群を（１，Ｆ１），（Ｆ１，Ｆ２），（Ｆ２，Ｆ３）としたときの自明な方程式群の例である。
【０１２９】
【数４】
この方程式に、係数情報群Ｆ１＝０Ｂ，Ｆ２＝ＡＡ，Ｆ３＝５Ｆと素数Ｐ＝ＦＢを代入すれば、同様に算出結果としてＳ１＝３Ｃ，Ｓ２＝ＡＢが得られる。秘密情報分散装置１０００において、秘密情報を２個に分割した分割情報はそれぞれＳ１＝３Ｃ，Ｓ２＝ＡＢであり、計算により正しい分割情報が得られていることが分かる。図１９に、後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１３０】
ステップ２１０６） 秘密情報出力部２６００は、秘密情報復元部２５００において算出したｄ個の分割情報群を結合し、秘密情報Ｓとして出力する。本実施の形態では、Ｓ１＝３Ｃ、Ｓ２＝ＡＢから、結合すればＳ＝３ＣＡＢであり、正しい秘密情報が得られていることが分かる。
【０１３１】
なお、本実施の形態では、秘密情報出力部２６００における秘密情報の出力の方法及び形式を規定するものではない。画面出力やファイル出力の他に、インターネットなどの接続回線を介して他の装置に出力するようにしてもよい。また、分割情報群を結合して秘密情報Ｓとして出力するのではなく、個々の分割情報群をそれぞれ出力しても構わない。
【０１３２】
本実施の形態では、分散情報入力部２３００において、閾値ｋ個の分散情報Ｗｉと情報番号ｉの入力を受け付けるものとしたが、仮に、分散情報入力部２３００が復元に必要な個数よりも少ない数の分散情報Ｗｉと情報番号ｉの入力を受け付けたとしても、係数情報復元部２４００において生成する連立方程式の数が不足しており、各係数情報Ｆｉの関係式を得ることができるが、計算により各係数情報群を求めることはできない。
【０１３３】
また、仮に、各係数情報Ｆｉの関係式を得たとしても、係数情報群はｄ個の分割情報群Ｓｄと乱数Ｒｊ、及び係数情報Ｆｉ−１からなるため、分割情報群Ｓｄを求める、あるいは、推測することはできない。
【０１３４】
例えば、閾値ｋ＝３の時に、２個の分散情報を仮にＷａ＝ｆ（ｚ），Ｗｂ＝ｆ（ｂ）とした場合、その分散情報群を表す連立方程式は次のようになる。
【０１３５】
Ｗａ＝ｆ（ａ）＝Ｆ１＋ａＦ２＋ａ２Ｆ３ （mod Ｐ）
Ｗｂ＝ｆ（ｂ）＝Ｆ１＋ｂＦ２＋ｂ２Ｆ３ （mod Ｐ）
連立方程式の数が閾値ｋ＝３よりも少ないため、これらの連立方程式からは係数情報Ｆ１とＦ２、Ｆ１とＦ３、Ｆ２とＦ３についての次のような関係式しか得ることができない。
【０１３６】
（ｂ＋ａ）Ｆ１＋ｂａＦ２＝（ｂ２Ｗａ−ａ２Ｗｂ）／（ｂ−ａ） （mod Ｐ）
Ｆ１−ｂａＦ３＝（ｂＷａ−ａＷｂ）／（ｂ−ａ） （mod Ｐ）
Ｆ２＋（ａ＋ｂ）Ｆ３＝（Ｗａ−Ｗｂ）／（ａ−ｂ） （mod Ｐ）
このように、入力された分散情報の数が閾値ｋよりも少ない場合には、係数情報復元部２４００において係数情報Ｆ１，Ｆ２，Ｆ３を求めることができず、よって秘密情報復元部２５００において、分割情報群Ｓ１，Ｓ２を求めることもできない。従って、秘密情報Ｓが復元されることはない。
【０１３７】
なお、本実施の形態は秘密分散法による復元処理を２回使用して分散情報から係数情報の算出と秘密情報の算出をそれぞれ行ったが、本発明は複数回の秘密分散法による復元処理を連結して繰り返すことで閾値数の任意の分散情報の集合から秘密情報を算出できればよく、本実施の形態の構成に制限されない。
【０１３８】
以上のように、本実施の形態における秘密情報分散装置１０００による秘密情報Ｓから生成した分散情報については、個々の分散情報Ｗｉの大きさは秘密情報Ｓのｄ分の１であって、ｎ個の分散情報の内、閾値ｋ個の任意の分散情報を持ち寄れば、ｋ個の係数情報Ｆｉを復元でき、よって全ての分散情報Ｓｔを復元して、秘密情報Ｓを完全に復元することができる。一方、ｋ個未満の分散情報からは係数情報Ｆｉを復元できないため、分散情報Ｓ１，Ｓ２，…，Ｓｄが求められず、秘密情報Ｓを復元することはできない。
【０１３９】
［第４の実施の形態］
本実施の形態では、第３の実施の形態における係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、計算を簡略化する例を説明する。本実施の形態の秘密情報分散装置１０００、秘密情報復元装置２０００の構成は、前述の第３の実施の形態と同様である。また、動作については、以下の説明以外については、第３の実施の形態と同様である。
【０１４０】
例えば秘密情報分散装置１０００において、係数情報計算部１４００における係数情報Ｆｉの算出式を以下ようにする。
【０１４１】
Ｆｉ＝Ｓ１＋Ｆｉ−１Ｓ２＋ｉＲ１ （mod Ｐ）
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。本実施の形態では、初期係数情報Ｆ０＝１とおくものとすると、係数情報Ｆ１＝０Ｂとなる。次いで、順次係数情報算出結果を用いて、繰り返し演算し、係数情報Ｆ２＝Ｆ６，Ｆ３＝３３を得る。図２０に本実施の形態での係数情報計算部１４００における係数情報の計算例を示す。
【０１４２】
これに伴って、秘密情報復元装置２０００において、秘密情報復元部２５００における計算も簡略化することができる。
【０１４３】
例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｆ６，Ｆ３＝３３から、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１４４】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋２・Ｒ１＝Ｆ６ （mod ＦＢ）
Ｆ３＝Ｓ１＋Ｆ６・Ｓ２＋３・Ｒ１＝３３ （mod ＦＢ）
秘密情報復元部２５００は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１４５】
【数５】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１４６】
なお、閾値ｋから自明に求まる方程式群を使って各分割情報を算出する場合、式は以下のようになり、計算が簡略化される。
【０１４７】
【数６】
この方程式に、係数情報群Ｆ１＝０Ｂ、Ｆ２＝Ｆ６，Ｆ３＝３３と素数Ｐ＝ＦＢを代入すれば、同様に算出結果として正しい分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢが得られる。図２１に、後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１４８】
［第５の実施の形態］
本実施の形態では、前述の第３の実施の形態における係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、計算を簡略化することができる例を説明する。本実施の形態の秘密情報分散装置１０００、秘密情報復元装置２０００の構成は、前述の第３の実施の形態と同様である。また、動作については、以下の説明以外については、第３の実施の形態と同様である。
【０１４９】
例えば秘密情報分散装置１０００において、係数情報計算部１４００における係数情報Ｆｉの算出式を閾値ｋに対して以下のように定義する。
【０１５０】
【数７】
従って、本実施の形態の場合、閾値ｋ＝３に対し、Ｓ３＝Ｒ１として、以下の算出式を用いる。
【０１５１】
【数８】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。本実施の形態では、係数情報Ｆ１＝０Ｂとなり、次いで係数情報Ｆ１を用いて繰り返し演算し、係数情報Ｆ２＝Ｄ７，Ｆ３＝４６を得る。図２２に本実施の形態における係数情報計算部１４００の係数情報の計算例を示す。
【０１５２】
これに伴って、秘密情報復元装置２０００において、秘密情報復元部２５００における計算も簡略化することができる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｄ７，Ｆ３＝４６から、秘密情報復元部２５００は、次のような連立方程式を内部メモリ（図示せず）上に生成する。
【０１５３】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋０Ｂ・Ｓ２＋Ｒ１＝Ｄ７ （mod ＦＢ）
Ｆ３＝Ｓ１＋Ｓ２＋０Ｂ・Ｒ１＝４６ （mod ＦＢ）
秘密情報復元部２５００は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１５４】
【数９】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ３＝１Ｆがそれぞれ算出結果となる。
【０１５５】
なお、閾値ｋから自明に求まる方程式群を使って各分割情報を算出する場合は、式は以下のようになり、更に計算が簡略化される。
【０１５６】
【数１０】
この方程式は、係数情報群Ｆ１＝０Ｂ，Ｆ２＝Ｆ６，Ｆ３＝３３と素数Ｐ＝ＦＢを代入すれば、同様に算出結果として正しい分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢが得られる。図２３に後者の例による秘密情報復元部２５００における秘密情報の計算例を示す。
【０１５７】
［第６の実施の形態］
本実施の形態は、第１の実施の形態の係数情報計算部１４０または、第３の実施の形態の係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、分割情報群Ｓｄの推測を更に困難にすることができる。以下では、第１の実施の形態の秘密情報分散装置１００及び秘密情報復元装置２００を用いて説明する。
【０１５８】
例えば、秘密情報分散装置１００の係数情報計算部１４０における係数情報Ｆｉの算出式を以下のようにする。
【０１５９】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１ (mod Ｐ)
Ｆｉ＝ｆ（Ｆｉ−２ xor Ｆｉ−１）
＝Ｓ１＋（Ｆｉ−２ xor Ｆｉ−１）Ｓ２＋（Ｆｉ−２ xor Ｆｉ−１）２・Ｒ１ （mod P）
（ｉ≧２）
ここで、式中のxorは排他的論理和を表す二項演算子とし、前後の値を２進数すなわちビット値で表現した上で、各ビットの位置ごとにビット値が同じ、すなわち、０と０、１と１であれば０を、ビット値が違う、すなわち、０と１，１と０であれば１を、演算結果のビット値とする演算方法を示すものとする。例えば、
８（１０００）xor ３（００１１）＝１１（１０１１）、
９（１００１）xor ３（００１１）＝１０（１０１０）
となる。
【０１６０】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。算出したＦｉが０または１または既に算出したＦｊ（ｊ＜ｉ）と一致する場合には、乱数Ｒ１を再度求めて、計算をやり直す。本実施の形態では、係数情報Ｆ１＝０Ｂとなる。初期係数情報Ｆ０＝１とおくものとして、順次係数情報の算出結果を用いて繰り返し演算すると、係数情報Ｆ２＝ｆ（１xorＦ１）＝６５，Ｆ３＝ｆ（Ｆ１xorＦ２）＝９７を得る。
【０１６１】
なお、本実施の形態における係数情報の計算時に、分散関数ｆ（ｘ）にＦｉ−２xorＦｉ−１を代入するものとしたが、本実施の形態は代入する値をこれに限定するものではない。既に生成した全ての係数情報の排他的論理和を計算して代入してもよいし、直前に生成した係数情報Ｆｉ−１と何らかの秘密の定数との排他的論理和を計算して代入しても良い。また、排他的論理和に限る必要もなく、論理和や論理積などの演算子を用いてもよい。
【０１６２】
これに伴って、秘密情報復元装置２００において、秘密情報復元部２５０における計算も排他的論理和を用いる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝６５，Ｆ３＝９７から、秘密情報復元部２５０は、１xorＦ１＝０A，F１xorF２＝６Eをそれぞれ計算し、次のような連立方程式を内部メモリ上に生成する。
【０１６３】
Ｆ１=Ｓ１+Ｓ２+Ｒ１=０Ｂ（mod FB）
Ｆ２=Ｓ１+０Ａ・Ｓ２+（０Ａ）２・Ｒ１=６５（mod FB）
Ｆ３=Ｓ１+６Ｅ・Ｓ２+（６Ｅ）２・Ｒ１=９７（mod FB）
秘密情報復元部２５０は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１６４】
【数１１】
以上のように、Ｓ１＝３Ｃ、Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１６５】
［第７の実施の形態］
本実施の形態では、第１の実施の形態の係数情報計算部１４０、第３の実施の形態の係数情報計算部１４００における係数情報Ｆｉの算出方法を変えることで、分割情報群Ｓｄの推測を更に困難する例を説明する。以下では、第１の実施の形態における秘密情報分散装置１００、秘密情報復元装置２００を対象として説明する。
【０１６６】
係数情報計算部１４０における係数情報Ｆｉの算出式を以下のようにする。
【０１６７】
【数１２】
上記の算出式に、分割情報Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，乱数Ｒ１＝１Ｆ及び素数Ｐ＝ＦＢ（２５１）を代入して、係数情報Ｆ１，Ｆ２，Ｆ３を順次算出する。算出したＦｉが０または１または既に算出したＦｊ（ｊ＜ｉ）と一致する場合には、乱数Ｒ１を再度求めて、計算をやり直す。本実施の形態では、係数情報Ｆ１＝０Ｂとなる。順次係数情報の算出結果を用いて繰り返し演算すると、係数情報Ｆ２＝ｆ（２Ｆ１）＝１９，Ｆ３＝ｆ（２Ｆ２）＝ＡＢを得る。
【０１６８】
なお、本実施の形態における係数情報の計算時に、分散関数ｆ（ｘ）に
【０１６９】
【数１３】
を代入するものとしたが、本実施の形態は代入する値をこれに限定するものではない。既に生成した全ての係数情報を指数として演算した値を代入してもよいし、直前に生成した係数情報Ｆｉ−１と何らかの秘密の定数との和あるいは積を指数として演算して代入してもよい。
【０１７０】
これに伴って、秘密情報復元装置２００において、秘密情報復元部２５０における計算も指数演算を用いる。例えば、本実施の形態では、閾値ｋ＝３、分割数ｄ＝２、素数Ｐ＝ＦＢと、係数情報群Ｆ１＝０Ｂ，Ｆ２＝１９，Ｆ３＝ＡＢから、秘密情報復元部２５０は、２０Ｂ≡２８，２１９≡ＦＡ（mod P）をそれぞれ計算し、次のような連立方程式を内部メモリ上に生成する。
【０１７１】
Ｆ１＝Ｓ１＋Ｓ２＋Ｒ１＝０Ｂ （mod ＦＢ）
Ｆ２＝Ｓ１＋２８・Ｓ２＋（２８）２・Ｒ１＝１９ （mod ＦＢ）
Ｆ３＝Ｓ１＋ＦＡ・Ｓ２＋（ＦＡ）２・Ｒ１＝ＡＢ （mod ＦＢ）
秘密情報復元部２５０は、この連立方程式を掃き出し法により展開し、分割情報Ｓ１，Ｓ２を求める。
【０１７２】
【数１４】
以上のように、Ｓ１＝３Ｃ，Ｓ２＝ＡＢ，Ｒ１＝１Ｆがそれぞれ算出結果となる。
【０１７３】
また、上記の各実施の形態における秘密情報分散装置及び秘密情報復元装置の各構成要素の動作をプログラムとして構築し、秘密情報分散装置及び秘密情報復元装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることも可能である。
【０１７４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１７５】
本発明は、ネットワーク上で取り扱われる各種情報のセキュリティ技術に適用可能である。
【図面の簡単な説明】
【０１７６】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の概要を説明するための図である。
【図４】本発明の第１の実施の形態における秘密情報分散装置の構成図である。
【図５】本発明の第１の実施の形態における秘密情報分散装置の動作説明図である。
【図６】本発明の第１の実施の形態における係数情報計算部の係数情報の計算例である。
【図７】本発明の第１の実施の形態における分散情報計算部の分散情報の計算例である。
【図８】本発明の第２の実施の形態における秘密情報復元装置の構成図である。
【図９】本発明の第２の実施の形態における秘密情報復元装置の動作説明図である。
【図１０】本発明の第２の実施の形態における係数情報復元部の係数情報の計算例である。
【図１１】本発明の第２の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図１２】本発明の第３の実施の形態における秘密情報分散装置の構成図である。
【図１３】本発明の第３の実施の形態における秘密情報分散装置の動作説明図である。
【図１４】本発明の第３の実施の形態における係数情報計算部の係数情報の計算例である。
【図１５】本発明の第３の実施の形態における分散情報計算部の分散情報の計算例である。
【図１６】本発明の第３の実施の形態における秘密情報復元装置の構成図である。
【図１７】本発明の第３の実施の形態における秘密情報復元装置の動作説明図である。
【図１８】本発明の第３の実施の形態における係数情報復元部の係数情報の計算例である。
【図１９】本発明の第３の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図２０】本発明の第４の実施の形態における係数情報計算部の係数情報の計算例である。
【図２１】本発明の第４の実施の形態における秘密情報復元部の秘密情報の計算例である。
【図２２】本発明の第５の実施の形態における係数情報計算部の係数情報の計算例である。
【図２３】本発明の第５の実施の形態における秘密情報復元部の秘密情報の計算例である。
【符号の説明】
【０１７７】
１００，１０００ 秘密情報分散装置
１１０，１１００ 分散制御部
１２０，１２００ 分散条件入力手段、分散条件入力部
１３０，１３００ 秘密情報入力手段、秘密情報入力部
１４０，１４００ 係数情報計算手段、係数情報計算部
１５０，１５００ 分散情報計算手段、分散情報計算部
１６０，１６００ 出力手段、分散情報出力部
１７０，１７００ 情報記憶部
２００，２０００ 秘密情報復元装置
２１０，２１００ 復元制御部
２２０，２２００ 復元条件入力手段、復元条件入力部
２３０，２３００ 分散情報入力手段、分散情報入力部
２４０，２４００ 係数情報復元手段、係数情報復元部
２５０，２５００ 秘密情報復元手段、秘密情報復元部
２６０，２６００ 出力手段、秘密情報出力部
２７０，２７００ 情報記憶部
【特許請求の範囲】
【請求項１】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散方法であって、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、
を行うことを特徴とする秘密情報分散方法。
【請求項２】
前記係数情報計算ステップにおいて、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する
請求項１記載の秘密情報分散方法。
【請求項３】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元方法であって、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
前記復元条件に基づいて、複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、
を行うことを特徴とする秘密情報復元方法。
【請求項４】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散装置であって、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力手段と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力手段と、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算手段と、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算手段と、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力手段と、
を有することを特徴とする秘密情報分散装置。
【請求項５】
前記係数情報計算手段は、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する手段を含む請求項４記載の秘密情報分散装置。
【請求項６】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元装置であって、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力手段と、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力手段と、
前記復元条件に基づいて、複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元手段と、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元手段と、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力手段と、
を有することを特徴とする秘密情報復元装置。
【請求項７】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散プログラムであって、
コンピュータに、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、
を実行させることを特徴とする秘密情報分散プログラム。
【請求項８】
前記係数情報計算ステップにおいて、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する
請求項４記載の秘密情報分散プログラム。
【請求項９】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元プログラムであって、
コンピュータに、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
前記復元条件に基づいて複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、
を実行させることを特徴とする秘密情報復元プログラム。
【請求項１】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散方法であって、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって、複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、
を行うことを特徴とする秘密情報分散方法。
【請求項２】
前記係数情報計算ステップにおいて、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する
請求項１記載の秘密情報分散方法。
【請求項３】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元方法であって、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
前記復元条件に基づいて、複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、
を行うことを特徴とする秘密情報復元方法。
【請求項４】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散装置であって、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力手段と、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力手段と、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算手段と、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算手段と、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力手段と、
を有することを特徴とする秘密情報分散装置。
【請求項５】
前記係数情報計算手段は、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する手段を含む請求項４記載の秘密情報分散装置。
【請求項６】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元装置であって、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力手段と、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力手段と、
前記復元条件に基づいて、複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元手段と、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元手段と、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力手段と、
を有することを特徴とする秘密情報復元装置。
【請求項７】
秘密情報を、元の秘密情報より小さい複数個の分散情報に分散符号化する秘密情報分散プログラムであって、
コンピュータに、
入力された前記秘密情報を分散するための分散条件を取得し、記憶手段に一時的に格納する分散条件入力ステップと、
入力された分散符号化の対象とする秘密情報を取得し、記憶手段に一時的に格納する秘密情報入力ステップと、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と生成された乱数を係数とする多項式関数によって複数個の係数情報を算出し、記憶手段に格納する係数情報計算ステップと、
前記複数個の係数情報を係数とする多項式関数によって任意の個数の、元の秘密情報より小さい分散情報を算出する分散情報計算ステップと、
算出された前記分散情報を記憶手段、出力装置、または、ネットワークに出力する出力ステップと、
を実行させることを特徴とする秘密情報分散プログラム。
【請求項８】
前記係数情報計算ステップにおいて、
入力された前記秘密情報を前記分散条件に基づいて複数個に分割し、記憶手段に一時的に格納し、該記憶手段から読み出された分割された秘密情報と乱数を係数とする多項式関数によって係数情報を算出し、該係数情報と該分割された秘密情報と、乱数を係数とする多項式関数によって繰り返し複数個の係数情報を算出し、記憶手段に格納する
請求項４記載の秘密情報分散プログラム。
【請求項９】
元の秘密情報より小さい複数の分散情報から元の秘密情報を復元する秘密情報復元プログラムであって、
コンピュータに、
入力された前記元の秘密情報を復元するための復元条件を取得し、記憶手段に一時的に格納する復元条件入力ステップと、
入力された前記秘密情報の復元に必要な個数の分散情報群を取得し、記憶手段に一時的に格納する分散情報入力ステップと、
前記復元条件に基づいて複数個の前記分散情報群に対応する連立方程式群を解くことによって複数個の係数情報を算出し、記憶手段に格納する係数情報復元ステップと、
前記複数個の係数情報群に対応する連立方程式を解くことによって複数個の分割した秘密情報を算出して、秘密情報を復元する秘密情報復元ステップと、
前記算出した秘密情報を記憶手段、出力装置または、ネットワークに出力する出力ステップと、
を実行させることを特徴とする秘密情報復元プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２００７−１２４６１０（Ｐ２００７−１２４６１０Ａ）
【公開日】平成１９年５月１７日（２００７．５．１７）
【国際特許分類】
【出願番号】特願２００６−１２６６７９（Ｐ２００６−１２６６７９）
【出願日】平成１８年４月２８日（２００６．４．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１９年５月１７日（２００７．５．１７）
【国際特許分類】
【出願日】平成１８年４月２８日（２００６．４．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]