秘密情報分散装置及び秘密情報復元装置
【課題】シェアの改竄を防止可能な秘密分散法を提供する。
【解決手段】秘密情報分散装置は、ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成し、秘密情報Ｓを自然数ｘｊで割った剰余αｊを求め、自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成し、自然数ｔｊを含むシェアを生成して分散する。秘密情報復元装置は、秘密情報分散装置により生成され・分散された各シェアに含まれているに自然数ｔｉを素因数分解し、分解した素因数に基づいて、自然数ｘｊと剰余αｊとを再生し、再生した自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する。
【解決手段】秘密情報分散装置は、ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成し、秘密情報Ｓを自然数ｘｊで割った剰余αｊを求め、自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成し、自然数ｔｊを含むシェアを生成して分散する。秘密情報復元装置は、秘密情報分散装置により生成され・分散された各シェアに含まれているに自然数ｔｉを素因数分解し、分解した素因数に基づいて、自然数ｘｊと剰余αｊとを再生し、再生した自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報を分散する装置および復元する装置に関する。
【背景技術】
【０００２】
情報は、その重要度に応じて対応する処置が異なっており、重要度の高い情報ほど、より強固なセキュリティ対策をとる必要がある。そのなかでも、組織の運営に支障をもたらすような機密レベルの情報を安全に管理するためには、情報の暗号化だけでは不完全で、その暗号鍵の管理も重要である。
【０００３】
秘密分散法はこのような鍵の管理を目的とした方式であり、秘密情報をシェアに分散することによってセキュリティを高める手法である。また、復元に必要なシェアの個数（ｋ：しきい値）をあらかじめ設定することにより、すべてのシェアを集めなくても元の秘密情報を復元することが可能であるという特性を有する。
【０００４】
しかし、ｋ個のシェアで元の秘密情報を復元できるため、シェアに改竄があった場合、復元時の情報が変化してしまうという問題がある。全ての組み合わせで復元を行えば改竄を発見できるが、実際の組み合わせは膨大な数に及ぶため、改竄の検出は困難なことが多い。また過半数以上のシェアに改竄があった場合、誤った結果を正しい結果と認識してしまうおそれもある。
【０００５】
この問題を解決できる秘密分散法が非特許文献１に開示されている。
【０００６】
非特許文献１には、ペル方程式を用いて、各シェアそれぞれが改竄を検知することが可能な秘密分散法が提案されている。
【０００７】
この方式により，シェアの誤りを検知することで、シェアの全ての組み合わせを試すことなく、また誤った結果を正しい結果と認織することなく情報を復元することが出来る。
【０００８】
非特許文献１に開示されている秘密分散法を説明する。
１． 前提
１−１． 中国の剰余定理
正の整数ｍ１，ｍ２が互いに素であるとき、任意の整数ａ１，ａ２に対して（１）と（２）の連立合同式には解ｘが存在し、その解はすべてＮ＝ｍ１・ｍ２を法として合同である。
ｘ≡ａ１（ｍｏｄ ｍ１）...（１）
ｘ≡ａ２（ｍｏｄ ｍ２）...（２）
【０００９】
２． ペル方程式
２−１． （３）式をペル方程式という。
ｘ２−ｄ・ｙ２＝１ ...（３）
（ｄ∈Ｎ，√ｄ∈Ｑ，Ｎ：自然数，Ｑ有理数）
この方程式を満たす解ｘ，ｙは無数に存在する。ペル方程式の解をｚ＝ｘ＋ｙ√ｄと表現したとき、全ての解で最小の解を基本解という。
【００１０】
３． ペル方程式の諸定理
（４）式をペル方程式の基本解の判別式といい、（４）式を満たし、ｚ＝ａ＋ｂ√ｄがペル方程式の解となるならば、それが基本解である。
ｄ∈Ｎ，√ｄ∈Ｑ，ａ，ｂ∈Ｎ、
ａ≧［ｂ２／２］ ...（４）
【００１１】
４． 分散フェーズ
４−１． まず、分散対象の秘密情報Ｓを、ルート部分だけは、子ノードの和、それ以外のノードは子ノードの積で計算できるように秘密情報Ｓをグループに分解し、ツリー（木）構造とすることで、シェア一つ一つのサイズを小さくする。
【００１２】
４−２． ノードグループＳｉについて、全てのｘｊ＝１＋ｕｊ・ｖｊ２が互いに素となるように、ｕｊ，ｖｊ（ｊ＝１，２，．．．ｎ）をランダムに発生させる。
４−３． ツリーのノードを構成する情報Ｓｉを、ｘj（＝１＋ｕｊ・ｖｊ２）で割った余りαｊを求める。
４−４． 自然数ｄｊ＝ｕｊ・（ｕｊ・ｖｊ２＋２）を求める。
４−５． この時の（ｉ，ｕｊ，ｖｊ，αｊ）がシェアとなる。
４−６． ４−２〜４−５の処理をすべてのノードで行う。このとき、ノードグループ毎にｎの値は異なってもよい。
【００１３】
５． 復元フェーズ
５−１． シェア１つを取り出す。
５−２． 後述する改竄の有無の判定を行う。
５−３． 改竄がなければ、復元処理を行えるシェアとして利用可能なので、保持しておく。
５−４． ５−１〜５−３の処理をすべてのシェアで行う。
５−５． 保持しておいた全てのシェアから、ノードグループ固有の番号ｉで分類を行う。
５−６． （５）式に示すように、ｉで分類されたシェアから作られた合同式を連立させ、その解ｘｉで分類されたｋ個のシェアから作られた合同式を連立させ、その解ｘｉを求める。
ｘｉ≡ αij（ｍｏｄ ｌ＋ｕij・ｖij２） ...（５）
（１≦ｉ≦ｚ）（１≦ｊ≦ｋ）ｚ：ノードグループ数、ｋ＝ノードグループの情報復元に必要なシェア数の閾値
５−７． 全てのグループで解を求め、ツリーを作る。
５−８． ツリーの部分木に注目し、計算が合うかチェックを行う。
５−９． ツリー上の計算が合えば、ツリーのルート部分が、秘密情報Ｓとなる。
【００１４】
６． 改竄判定の方法
改竄の判定はペル方程式を用いて行う。
改竄があれば、シェアはペル方程式や，ペル方程式の基本解の判別式を満たさないことから改竄の検知が可能となる。
６−１． ｘｉ＝１＋ｕｉ・ｖｉ２，ｙ＝ｖｉとして，それぞれ（３）式で示すペル
方程式に代入し，式が成立するか判定を行う。
６−２． ペル方程式が成立した場合、（４）式にａ＝ｘ，ｂ＝ｙを当てはめ、基本解であるか否か判定する。
６−３． 基本解であれば、改竄は行われていないと判定する。
【００１５】
【非特許文献１】ペル方程式を用いた改竄検知可能な秘密分散法の提案 平成２０年２月４日、広島市立大学 平成１９年度修士論文 情報メディア工学科 ソフトウエア工学講座 武田 雄人
【発明の開示】
【発明が解決しようとする課題】
【００１６】
非特許文献１に開示された手法によれば、ペル方程式を用いてシェアの改竄の有無を容易に検出することができ、さらに、ツリーを用いて復元された情報相互の関係から改竄を検出することも可能となる。
【００１７】
しかしながら、この手法によれば、ｕとｖとを公開するので、ｄ（＝ｕ・（ｕ・ｖ２＋２））を完全に復元できる。従って、新しい３つ組ｕ’，ｖ’，ｄ’を生成して、改竄を検知できないようにして、復元を困難にすることが可能となる。
【００１８】
本発明は、上記実情に鑑みてなされたものであり、シェアの改竄を防止可能な秘密分散法を提供することを目的とする。
また、本発明は、より信頼性の高いペル方程式を用いた改竄検知可能な秘密分散法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、この発明の第１の観点に係る秘密情報分散装置は、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段と、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段と、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段と、
自然数ｔｊを含むシェアを生成して分散する分散手段と、
を備えることを特徴とする。
【００２０】
秘密情報Ｓをｚ個のノードを有する木構造に分解する手段をさらに有し、
前記ｘｊ生成手段は、第ｉ（ｉ＝０，１，．．．，ｚ−１）のノードグループのそれぞれについて、複数の自然数ｘijを生成し、
前記除算手段は、各ノードの値Ｓｉを自然数ｘｉｊで割った剰余αｉｊを求め、
前記ゲーデル数化手段は、各ノードについて、前記自然数ｘｉｊと剰余αｉｊとを、素数を用いてゲーデル数化して、自然数ｔｉｊを生成し、
前記分散手段は、各ノードについて、自然数ｔｉｊを含むシェアを生成して分散する、
ように構成してもよい。
【００２１】
前記ゲーデル数化手段は、例えば、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐｚj2に代入することにより、自然数ｔｊを求める。なお、ｚｊ１とｐは互いに素、ｐは素数である。
【００２２】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄ・ｙｊ２＝１を満たす自然数ｄｊを求める手段と、
求めた「自然数」ｄｊを、正当権限を有する者に配布する手段と、
をさらに配置してもよい。
【００２３】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段をさらに備え、
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐ１ｚj2・ｐ２ｄjに代入することにより、自然数ｔｊを求めるようにしてもよい。なお、ｚｊ１とｐ１とｐ２は互いに素、ｐ１、ｐ２は素数である。
【００２４】
また、この発明の第２の観点に係る秘密情報復元装置は、
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアに含まれている自然数ｔjを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、
再生された前記自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する復元手段と、
を備えることを特徴とする。
【００２５】
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアをノードの番号ｉで分類する分類手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、ノードグループ毎に、再生された前記自然数ｘｊと剰余αｊとの連立合同式を解くことにより各ノードＳｉの値を復元する、ように構成してもよい。
【００２６】
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
外部より、自然数ｄｊを受信する受信手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと、受信したｄｊとを用いて、各シェアの改竄の有無を検証し、改竄が無いと判別したシェアに基づいて、秘密情報Ｓを復元するように構成してもよい。
【００２７】
上述の秘密情報分散装置により、生成されたシェアを記憶する手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊと自然数ｄｊを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと自然数ｄｊとを用いて各シェアの改竄の有無を検証し、改竄が無いと判別したシェアを用いて秘密情報Ｓを復元する、ように構成してもよい。
【００２８】
コンピュータを、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段、
自然数ｔｊを含むシェアを生成して分散する分散手段、
として機能させるコンピュータプログラムを生産・配布してもよい。
【発明の効果】
【００２９】
本発明によれば、秘密情報をより安全に分散させることができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の実施の形態にかかる秘密分散・復元システム１００について説明する。
【００３１】
この秘密分散・復元システム１００は、秘密情報Ｓを、ペル方程式を用いて改竄検知可能な形態で複数のシェアに秘密分散する一方、収集された複数のシェアから元の秘密情報Ｓを復元する機能を備える。
【００３２】
図１に示すように、秘密分散・復元システム１００は、制御部１０と、記憶部２０と、入力部３０と、出力部４０と、通信部５０と、から構成される。
【００３３】
制御部１０は、記憶部２０に記憶された動作プログラムに従って動作し、後述する秘密分散処理、改竄検知処理、復元処理などを行う。
【００３４】
記憶部２０は、ＲＡＭ (Random Access Memory)、ＲＯＭ (Read Only Memory)、ハードディスク装置、フラッシュメモリなどから構成され、制御部１０の動作プログラムを記憶し、また、制御部１０のワークエリアとして機能する。
【００３５】
記憶部２０は、ＲＡＭ、ＲＯＭ、ハードディスク装置、フラッシュメモリなどから構成され、記憶手段として、制御部１０の動作プログラムを記憶し、任意のデータを記憶し、また、制御部１０のワークエリアとして機能する。
【００３６】
入力部３０は、任意の入力装置から構成され、分散対象の秘密情報Ｓ、復元対象の複数のシェアなどを入力する。
【００３７】
出力部４０は、任意の出力装置から構成され、分散対象の秘密情報Ｓを秘密分散して得られた複数のシェア、複数のシェアから復元した秘密情報Ｓ等を出力する。また、出力部４０は、正当権限を有する者に、秘密情報Ｓを復元するために必要な情報（後述する自然数ｄ）を配布するための処理を行う。
【００３８】
通信部５０は、外部装置との間で通信を行い、種々のデータ、例えば、分散対象の秘密情報Ｓ、生成された複数のシェア、復元対象の複数のシェア、複数のシェアから復元した元の秘密情報Ｓ等を、送受信する。また、通信部５０は、正当権限を有する者に、秘密情報Ｓを復元するために必要な情報（後述する自然数ｄ）を配布するための処理を行う。
【００３９】
次に、上記秘密分散・復元システム１００により、秘密情報Ｓを複数のシェアに分散し、続いて、複数のシェアから秘密情報Ｓを復元する手順を図２に示すフローチャートを参照して説明する。
【００４０】
まず、制御部１０は、秘密情報Ｓを決定する（ステップＳ１０１）。秘密情報Ｓは、例えば、入力部３０から入力されたデータ、通信部５０を介し受信したデータ、或いは、これらを加工して得たデータである。
【００４１】
次に、制御部１０は、秘密情報Ｓを、ｚ個のノードを持つ木（ツリー）構造に分解する（ステップＳ１０２）。ここで、ツリー構造の第１階層のノードは、それらの値の和が秘密情報Ｓの値となる数値とし、第２階層以下のノードは、上位ノードの値が下位ノードの積となるように分解する。即ち、秘密情報Ｓを和がＳとなる素数以外の２つの数値Ｓ０，Ｓ１に分割し、さらに、値Ｓ０とＳ１をそれぞれ、積がＳ０，Ｓ１となる２つの値に分割し、同様の分割を繰り返して、ノードの数をｚ個とする。
【００４２】
例えば、ｚ＝６とすると、図１０に例示するように、秘密情報Ｓを、和がＳとなる素数以外の２つの数値Ｓ０，Ｓ１に分割する。さらに、値Ｓ０とＳ１をそれぞれ、積がＳ０，Ｓ１となる２つの値Ｓ２とＳ３、Ｓ４とＳ５に分割する。従って、Ｓ＝Ｓ０＋Ｓ１、Ｓ０＝Ｓ２・Ｓ３、Ｓ１＝Ｓ４・Ｓ５が成立する。
【００４３】
次に、ノードを特定するポインタｉに０をセットする（ステップＳ１０３）。さらに、ノードＳｉに対するシェアの番号を示すポインタｊに０をセットする（ステップＳ１０４）。
【００４４】
次に、ポインタｉで特定されるノードＳｉについて、全ての１＋ｕｊ・ｖｊ２が互いに素となり、且つ、ｋ個の１＋ｕｊ・ｖｊ２の積がノードの値Ｓｉ未満となるように、自然数ｕｉｊとｖｉｊの組をランダムに発生させる（ステップＳ１０５〜Ｓ１１０）。
【００４５】
具体的には、まず、自然数ｕｉｊと自然数ｖｉｊとを乱数で発生させる（ステップＳ１０５）。
【００４６】
次に、ｘｉｊ＝１＋ｕｉｊ・ｖｉｊ２を計算する（ステップＳ１０６）。
次に、gｃｄ（１＋ｕｉｊ・ｖｉｊ２）＝１(j=1,2,…k-1)が成立するか否かを判別する（ステップＳ１０７）。即ち、発生したk個のｘｉ（ｘｉ０〜ｘｉk）が、互いに素であるか否かを判別する。
【００４７】
発生したｘｉが互いに素の関係に無い場合（ステップＳ１０７；Ｎｏ）、ステップＳ１０５にリターンし、再度、自然数ｕｉｊと自然数ｖｉｊとを乱数で発生させる。
【００４８】
一方、ステップＳ１０７で、gｃｄ（ｘｉj）＝gｃｄ（１＋ｕｉｊ・ｖｉｊ２）＝１が成立すると判別された場合、すなわち、発生された全てのｘｉｊが互いに素であると判別された場合（ステップＳ１０７；Ｙｅｓ）、生成したｋ個のｘｉｊの積が第ｉのノードＳｉの値より大きいか否かを判別する（ステップＳ１０８）。積がノードＳｉの値に等しいか小さければ（ステップＳ１０８；Ｎｏ）、ステップＳ１０５にリターンする。
【００４９】
ステップＳ１０８で、ｋ個のｘｉｊの積がＳｉよりも大きいと判別された場合（ステップＳ１０８；Ｙｅｓ）、ノードＳｉについて、全ての１＋ｕｉｊ・ｖｉｊ２が互いに素となり、且つ、ｋ個のｘｉｊの積がＳｉより大きくなる自然数ｕｉｊとｖｉｊが揃ったことになる。
【００５０】
続いて、Ｓｉをｘｉｊで割った余りαｉｊを求める（ステップＳ１０９）。即ち、Ｓｉ≡αｉｊ（ｍｏｄ （１＋ｕｉｊ・ｖｉｊ２））が成立するαｉｊを求める。
【００５１】
さらに、αijをペル方程式の基本解とする値ｄｉｊ＝ｕｉｊ・（ｕｉｊ・ｖｉｊ２＋２）を求める（ステップＳ１１０）。
【００５２】
求めた値の組（ｉ，ｘｉｊ，αｉｊ）をシェアの１つとして記憶部２０に記憶する（ステップＳ１１１）。
【００５３】
次に、値ｊが所定値ｋ−１であるか否かを判別する（ステップＳ１１２）。
値ｊがｋ−１未満であると判別された場合（ステップＳ１１２；Ｎｏ）、ポインタｊを＋１して（ステップＳ１１３）、ステップＳ１０５にリターンし、同様の動作を繰り返す。
【００５４】
値ｊ＝ｋ−１であると判別された場合（ステップＳ１１２；Ｙｅｓ）、値ｉが所定値ｚ−１であるか否かを判別する（ステップＳ１１４）。
ｉがｚ−１未満であると判別された場合（ステップＳ１１４；Ｎｏ）、ポインタｉを＋１して（ステップＳ１１５）、ステップＳ１０４にリターンし、同様の動作を繰り返す。
【００５５】
一方、ｉ＝ｚ−１であると判別された場合（ステップＳ１１４；Ｙｅｓ）、全てのノードＳi（Ｓ０〜Ｓｚ−１）についてシェアを求める処理が終了したことになる。
【００５６】
ステップＳ１１１で格納したシェアは、そのままでは、背景技術の欄で説明したように、それ自体が改竄され、復元を不可能とされるおそれがある。
そこで、シェアの改竄を防止するため、ステップＳ１１６で、ｘｉｊとαｉｊを変換する。
【００５７】
この変換処理の詳細を図３を参照して説明する。
まず、ノードを特定するポインタｉを０に（ステップＳ２０１）、各ノードについてシェアを特定するポインタｊを０にセットする（ステップＳ２０２）。
続いて、ポインタｉとｊで特定されるシェアについて、次式により、ｘｉｊとαｉｊとをｚｉｊ１とｚｉｊ２に直交変換する（ステップＳ２０３）。
【００５８】
Ｚij1＝ｘij＋αij
Ｚij2＝ｘij−αij
【００５９】
次に、任意の素数ｐを発生させる（ステップＳ２０４）。
【００６０】
次に、ｇｃｄ（Ｚij1，ｐ）＝１が成立するか否か、すなわち、Ｚij1とｐとが互いに素であるか否かを判別する（ステップＳ２０５）。
成立しなければ（ステップＳ２０５；Ｎｏ）、ステップＳ２０４にリターンして、素数ｐを発生させる。
成立すれば（ステップＳ２０５；Ｙｅｓ）、数式（２）に従って、生成したＺij１とＺji２を素数ｐを用いてゲーデル数化して自然数ｔijを生成する（ステップＳ２０６）。
【００６１】
ｔｉｊ＝Ｚij1・ｐＺij2 ．．．．（２）
ここで、ｇｃｄ（Ｚij1，ｐ）＝１
【００６２】
次に、（ｉ，ｔｉｊ）を１つのシェアとする（ステップＳ２０７）。
【００６３】
次に、値ｊが所定値ｋ−１であるか否かを判別する（ステップＳ２０８）。
値ｊがｋ−１未満であると判別された場合（ステップＳ２０８；Ｎｏ）、ポインタｊを＋１して（ステップＳ２０９）、ステップＳ２０３にリターンし、同様の動作を繰り返す。
【００６４】
ｊ＝ｋ−１であると判別された場合（ステップＳ２０８；Ｙｅｓ）、値ｉが所定値ｚ−１であるか否かを判別する（ステップＳ２１２）。
ｉがｚ−１未満であると判別された場合（ステップＳ２１２；Ｎｏ）、ポインタｉを＋１して（ステップＳ２１１）、ステップＳ２０２にリターンし、同様の動作を繰り返す。
【００６５】
一方、ｉ＝ｚ−１であると判別された場合（ステップＳ２１２；Ｙｅｓ）、全てのノードＳi（Ｓ０〜Ｓｚ−１）についてシェアを変換する処理が終了したことになり、図２のメインフローにリターンする。
【００６６】
制御部１０は、こうして生成したシェア（ｉ，ｔｉｊ）を出力部４０又は通信部５０から出力又は送信する。
また、制御部１０は、ステップＳ１０５，Ｓ１１０で生成した値ｕｉｊ、ｖｉｊ、ｄｉｊ等のデータを記憶部２０に保存する。
また、制御部１０は、秘密情報Ｓを復元する正当権限を有する者に、出力部４０又は通信部５０を介して、自然数ｄを、シェアの改竄の有無を判定するために配布するための処理を行う。
【００６７】
次に、こうして分散されたシェアから元の秘密情報Ｓを復元する動作を説明する。
【００６８】
まず、制御部１０は、入力部３０或いは通信部５０を介し入手したシェアと自然数ｄijを記憶部２０に格納しておく。
【００６９】
制御部１０は、図４に示す改竄判定処理を適宜行い、記憶部２０に記憶しておいたシェアを取り出し（ステップＳ３０１）、改竄の有無を判定し（ステップＳ３０２）、改竄が無いと判別すると（ステップＳ３０２；Ｎｏ）、復元処理を行えるシェアとして利用可能なので、保持しておく（ステップＳ３０３）。一方、改竄があると判定すると（ステップＳ３０２；Ｙｅｓ）、そのシェアを廃棄する（ステップＳ３０４）。続いて、全てのシェアについて処理が終了したか否かを判別し（ステップＳ３０５）、全てのシェアについて改竄の判定が終了していれば（ステップＳ３０５；Ｙｅｓ）、改竄判定処理を終了し、終了していなければ（ステップＳ３０５；Ｎｏ）、ステップＳ３０１にリターンして、次のシェアについて同様の処理を行う。
【００７０】
ステップＳ３０２で実行する改竄有無の判定は、ペル方程式を用いて行う。
改竄があれば、シェアはペル方程式や、ペル方程式の基本解の判別式を満たさないことから改竄の検知が可能となる。
このペル方程式を用いた改竄有無の判定手順について、図５を参照して説明する。
【００７１】
前述のように、制御部１０は、事前に、ディーラ（シェアを配布した者）より配布された自然数ｄijを、記録媒体或いは通信により、入力部３０或いは通信部５０を介して受け取り、記憶部２０に格納しておく。
【００７２】
制御部１０は、ステップＳ３０１で選択したシェアから自然数値ｔijを抽出する（ステップＳ３２１）。
自然数ｔｉjを素因数分解し、Ｚij１・ｐＺij２（ｐは素数）の形式とし、Ｚ１とＺ２とを求める（ステップＳ３２２）。
【００７３】
次に、ｘij＝（Ｚij１＋Ｚij２）／２から、ｘijを求める（ステップＳ３２３）。
次に、ディーラより受信しておいた、自然数ｄｉｊとｘijから、xij−ｄij・ｖij2＝１に代入し、ｖijを求める（ステップＳ３２４）。
次に、ｖijが自然数か否か判別する（ステップＳ３２５）。自然数であれば（ステップＳ３２５；Ｙｅｓ）、ペル方程式が成立し、改竄検知の必要条件を満たす。
【００７４】
次に、ｕijとｖijがペル方程式の基本解の判別式を満たすか否かを判別する。すなわち、 ｕij≧［ｖij２／２］を満たすか否かを判別する（ステップ３２６）。
【００７５】
基本解の判別式を満たすと判別した場合（ステップＳ３２６；Ｙｅｓ）、改竄は行われていないと判別する（ステップ３２７）。
【００７６】
一方、基本解の判別式を満たさないと判別した場合（ステップＳ３２６；Ｎｏ）、改竄が行われていると判別する（ステップ３２８）。
【００７７】
このようにして、各シェアについて、ペル方程式を満たすか否か、更に、ペル方程式の基本解の判別式を満たすか否かを判別することにより、シェアの改竄の有無を迅速に判別することができる。さらに、改竄されていると判別されたシェアを破棄することにより、秘密情報Ｓを誤って復元する事態を防止できる。
【００７８】
次に、改竄されていないと判別されたシェアを用いて秘密情報Ｓを復元する処理を図６のフローチャートを参照して説明する。
【００７９】
制御部１０は、記憶部２０に保持しておいた全てのシェア（ｉ,ｊ，ｔｉｊ）を、ノード固有の番号ｉで分類する（ステップＳ４０１）。
ｉ＝０とおく（ステップＳ４０２）。
ｉで分類された全てのシェアから作られたｋ個の連立合同式をガウスの方法を用いて解き説き、その解Ｓｉ（≡αij (ｍｏｄ ｘij）)を求める（ステップＳ４０３）。
【００８０】
次に、ｉ＝ｚ−１であるか否か、即ち、全てのノードについて値Ｓｉが求められたか否かを判別する（ステップＳ４０４）。
【００８１】
ｉ＜ｚ−１であれば（ステップＳ４０４；Ｎｏ）、未処理のノードが残っているので、ｉ＝ｉ＋１として（ステップＳ４０５）、ステップＳ４０３にリターンし、解Ｓｉを求める。
【００８２】
一方、ｉ＝ｚ−１であれば（ステップＳ４０４；Ｙｅｓ）、全てのノードの値Ｓｉの復元が終了したので、値Ｓｉを用いて、ツリーを再生する（ステップＳ４０６）。
【００８３】
続いて、ツリーを検証する（ステップＳ４０７）。即ち、ツリーの部分木に注目し、直下の２つのノード値の積（ルートについては和）が当該ノードの値に等しいか検査を行う。全てのノードについて、直下の２つのノード値の積（ルートについては和）に等しい場合に、ツリーが正しいと判別する。
【００８４】
ツリーが正しいと判別した場合（ステップＳ４０８；Ｙｅｓ）、ツリーのルートで合成される値を秘密情報Ｓとする（ステップＳ４０９）。
一方、ツリーが正しくないと判別した場合（ステップＳ４０８；Ｎｏ）、所定のエラー処理を行い（ステップＳ４１０）、例えば、シェアの改竄を報知する等の処理を行う。
こうして、秘密情報Ｓが復元される。
【００８５】
この実施の形態によれば、シェアを構成する情報ｘｉとαｉとを素数ｐを用いてゲーデル数化し自然数ｔｉを生成し、これを分散する。
【００８６】
このため、シェアの元の情報ｘｉとαｉを推定することが困難となり、シェアの改竄をより困難とすることができる。
また、シェアの改竄をペル方程式および再生されたツリー構造から検証するので、シェアの改竄の有無を迅速に判別でき、改竄されたシェアを用いて秘密情報Ｓを復元する事態を防止できる。
【００８７】
（第２実施形態）
上記第１の実施形態においては、シェアを復元する際に、ディーラより、値ｄij（＝uij・（ｕij・ｖij２＋２））を復元先に配布する必要があったが、ｄijをシェアに含めることも可能である。
【００８８】
例えば、
ｔｉ＝ｚｉｊ１・ｐ１Ｚｉｊ２・ｐ２ｄij
ｐ１，ｐ２は素数、ｚｉｊ１、ｐ１、ｐ２は互いに素、ｐ１＞ｐ２とすれば、
自然数ｔijにｄijを含めることができる。
【００８９】
秘密情報Ｓを復元する際には、シェアに含まれている自然数ｔｉを素因数分解し、ａ・ｐ１ｎ・ｐ２ｍの形式とし、ｐ１＞ｐ２より、Ｚij1＝ａ、Ｚij2＝ｎ、ｄij＝ｍとし、さらに、ｘｉ＝（Ｚij1＋Ｚij2）／２、αｉ＝（Ｚij1−Ｚij2）／２とすることにより、シェアを復元することができる。
【００９０】
同様の手法により、ｕij、ｖijを自然数ｔijに含ませることも可能である。
【００９１】
また、上記実施の形態においては、シェアを構成する自然数ｘｉとαｉとを、直交変換によりｚｉｊ１、ｚｉｊ２に変換したが、変換後のｚｉｊ１、ｚｉｊ２から自然数ｘｉとαｉとを再生できるならば、任意の変換式を使用可能である。
【００９２】
さらに、
ｔｉ＝αｉｊ・ｐ１ｘij・ｐ２ｄij
ｔｉ＝ｘｉｊ・ｐ１αｉｊ・ｐ２ｄij
とする等してもよい。
また、シェアを（ｉ，ｊ，ｔｉｊ）としてもよい。このようにすれば、ｊの特定が容易である。
【００９３】
（応用例１）
次に、上記構成を用いた秘密分散方法の応用例について説明する。
土木・建築工事において、生コンは、必須の素材である。一方、生コンの品質物を均一に維持することは困難であり、工事完了後に、生コンの品質をチェックしたい場合が発生することがある。
【００９４】
しかしながら、建設現場における生コンのサンプル採取作業の徹底が不十分なため、生コン生還過程の追跡性が悪く、事故発生後に、生コンサンプル分析データを活用した原因究明等がなされていないという背景がある。
【００９５】
そこで、以下、生コンサンプル採取及び分析データ管理の効率化と事故後の生コンサンプル分析データ照合作業の効率化を可能とする方法を提供する。
まず、システムの全体図を図７に示す。
【００９６】
図示するように、生コンは、工場１０１で生産され、ミキサー車１０２に積載され、建設現場１０３に搬入される。
工場１０１では、生コンの生産データ１０１ａが管理されており、生産日・時間、材料・ロット、製造記録などの情報がデータベースで記録・管理されている。
【００９７】
ミキサー車１０２の担当者は、積載する生コンの生産データ１０１ａを自己の携帯端末１１１に記録する。この携帯端末は図１に示す秘密分散・復元システム１００と同様の構成を有する。なお、出力部４０はＲＦＩＤのリーダライタを含む。
【００９８】
ミキサー車１０２の担当者は、工場からの搬出時間・工事現場への搬入時間、搬入場所等のデータも自己の携帯端末１１１に入力部３０等から入力する。
【００９９】
続いて、建設現場１０３に着くと、ミキサー車１０２の担当者は、携帯端末１１１に、搬入時間、搬入場所等のデータ１０２ａを入力する。
【０１００】
次に、建設現場担当者は、搬入された生コンからサンプル１０６を取り出し、ＲＦＩＤチップ１０７を埋め込む。
【０１０１】
担当者は、携帯端末１１１にサンプル用ＲＦＩＤチップ１０７のＩＤを入力する。
【０１０２】
携帯端末１１１は、入力された情報、すなわち、生産情報、搬入記録、サンプルチップのＩＤ等から複数のシェアを生成し、これらを複数のＲＦＩＤ１０５に分散して格納する。同一のシェアを複数のＲＦＩＤ１０５に記録してもよい。
【０１０３】
続いて、ＲＦＩＤチップ１０５を生コン１０４に埋め込む。
生コン１０４は、打設され、構造物の一部を構成する。
【０１０４】
一方、ＲＦＩＤ１０７が埋め込まれた生コンサンプル１０６は、所定の試験機関１０８に搬送され、分析される。
【０１０５】
分析結果１０９は、生コンサンプル１０６に埋め込まれたＲＦＩＤ１０７のＩＤに対応付けて、ＤＢ等に格納される。
【０１０６】
建築物に問題が発生した場合、図１に示す構成を有するＲＦＩＤの読み取り装置により、問題箇所に埋め込まれているＲＦＩＤ１０５に格納されているシェアを読み取る。前述のように、ＲＦＩＤ１０５には、生コンサンプル１０６に埋め込まれたＲＦＩＤ１０７のＩＤ、生産データ、輸送・搬入データがシェアの形態で格納されている。
【０１０７】
読み取り装置は、読み取ったシェアが改竄されているか否かを、上述したように、ペル方程式に基づいて判別し、上述した手法により、各ノードの値を復元し、さらに、秘密情報を復元する。
【０１０８】
この秘密情報は、サンプル用ＲＦＩＤ１０７のＩＤを含む。
担当者は、復元した情報に含まれているサンプルＩＤをキーにＤＢを検索し、該当するＩＤに対応付けられている分析データを読み出す。
【０１０９】
これにより、問題部分のコンクリートの、生産データ、輸送・搬入データ、さらに、サンプル分析データを取得して、問題を解析することが可能となる。
なお、最終的に問題箇所に使用された生コンのサンプルが特定できるならば、ＲＦＩＤチップ１０５に格納される情報自体は任意に変更可能である。
【０１１０】
（応用例２）
この例では、電子投票を行う場面で、投票結果を集計装置に集積する場面を想定する。
【０１１１】
例えば、図８に示すように、複数の投票所２０１（２０１Ａ〜２０１Ｃ）に、それぞれ、複数台の投票端末２０２（２０２１〜２０２ｎ）と投票端末２０２に接続された蓄積装置２０３が配置されているとする。
【０１１２】
投票端末２０２は、投票が行われる度に、投票番号、投票者、時刻等の情報を含む投票情報を生成し、暗号化した上で、蓄積装置２０３に送信する。
【０１１３】
蓄積装置２０３は、各投票端末２０２から送信された投票情報を受信し、二重化などの安全処理を施した上で、ハードディスク装置２０４等に蓄積する。
【０１１４】
投票時間終了後、蓄積装置２０３は、蓄積した情報を秘密情報Ｓとして、複数のノードを形成し、各ノードから複数のシェアを生成し、複数の記憶装置２０５に分散して記憶させる。ここで、各記憶装置２０５には、互いに異なる組み合わせではあるが、個々の記憶装置に格納されているシェアのみから元の秘密情報Ｓを復元できるシェアを選択して格納する。
【０１１５】
続いて、複数の記憶装置２０５を、例えば、別々の搬送手段で、集計所に搬送する。
【０１１６】
集計所２０６に設置された集計装置２０７は、複数の記憶装置２０５に格納されたシェアを読み取り、ペル方程式に基づいて各シェアの改竄の有無を判別する。
【０１１７】
改竄が無いと判別すると、シェアから各ノードを復元し、続いて ノード同士の関係から改竄の有無を検証する。さらに、ノード相互の関係も正常であれば、ルートのノードを求め、これを元の情報とする。
【０１１８】
複数の投票所２０１から提供されたシェアから復元した投票情報を元に、投票数を集計する。
【０１１９】
このような構成とすれば、搬送の途中で一部の情報が失われたとしても、残りの情報で元の情報を再生することができ、秘密情報の搬送及び再生を安全に行うことができる。
【０１２０】
（応用例３）
一般の通信に上述の技術を応用することが可能である。
【０１２１】
ここでは、一例として、任意の音声データや画像データを安全に有線又は無線で送信する場合を想定する。
【０１２２】
図９に示すように、送信装置３０１は、送信対象のデータをバッファ等に蓄積する。送信装置３０１は、バッファ等に蓄積したデータを所定量（例えば、フレーム単位）ずつ読み出し、暗号化する。
【０１２３】
さらに、送信装置３０１は、暗号化した所定量の情報を秘密情報Ｓとして、複数のノード、例えば、ノードＳ０〜Ｓ５に分割する。続いて、各ノードについて、複数のシェアを生成する。
【０１２４】
続いて、送信装置３０１は、複数の伝送チャネルにシェアを割り振る。この際、送信装置３０１は、１つの伝送チャネルを伝送されるシェアをモニタするのみでは、元のデータを復元できないように、シェアを配分する。送信装置３０１は、分配された各シェアを各伝送チャネルを介して送信する。
【０１２５】
一方、受信装置３０２は、複数の伝送チャネルを介して送信されてきたシェアを受信し、受信したシェアの改竄の有無をペル方程式を用いて判別する。改竄を検出した場合には、シェアを廃棄し、改竄が無いと判別するとシェアを蓄積する。
【０１２６】
続いて、受信装置３０２は、受信したシェアからノードＳ０〜Ｓ５を復元する。
さらに、復元したノード相互の整合性をチェックする。整合性が取れていれば、ルート部分を秘密情報Ｓとする。この処理を、フレーム毎に行う。
【０１２７】
このような構成とすれば、秘密情報を安全に送信することが可能となる。
【０１２８】
以上、本発明の実施形態および応用例について説明したが、これらは一例であり、種々の変形、応用、他技術との組み合わせが可能であり、これらも請求項に記載されている発明や発明の実施形態に記載されている具体例に対応する発明の範囲に含まれると理解されるべきである。
【０１２９】
例えば、システムの構成、処理の手順等は任意に変更可能である。
また、専用のシステムによらず、上述の分散処理および／又は復元処理を実行するためのコンピュータプログラムをコンピュータにインストールし、上述の秘密分散処理装置および／又は復元装置を形成し、秘密分散処理および／又は復元処理を実行させてもよい。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施の形態に係る秘密分散・復元システムのブロック図である。
【図２】分散処理のフローチャートである。
【図３】図２に示す変換処理の詳細を示すフローチャートである。
【図４】シェアの改竄の有無を検証する改竄判定処理のフローチャートである。
【図５】ペル方程式を用いた改竄判定の手順の詳細を示すフローチャートである。
【図６】復元処理のフローチャートである。
【図７】応用例１として、生コンのデータを管理するシステムの例を示す図である。
【図８】応用例２として、電子投票システムに適用した例を示す図である。
【図９】応用例３として、通信システムに適用した例を示す図である。
【図１０】秘密情報を複数のノードに分割する例を示す図である。
【符号の説明】
【０１３１】
１０…制御部
２０…記憶部
３０…入力部
４０…出力部
５０…通信部
１００…秘密分散・復元システム
【技術分野】
【０００１】
本発明は、秘密情報を分散する装置および復元する装置に関する。
【背景技術】
【０００２】
情報は、その重要度に応じて対応する処置が異なっており、重要度の高い情報ほど、より強固なセキュリティ対策をとる必要がある。そのなかでも、組織の運営に支障をもたらすような機密レベルの情報を安全に管理するためには、情報の暗号化だけでは不完全で、その暗号鍵の管理も重要である。
【０００３】
秘密分散法はこのような鍵の管理を目的とした方式であり、秘密情報をシェアに分散することによってセキュリティを高める手法である。また、復元に必要なシェアの個数（ｋ：しきい値）をあらかじめ設定することにより、すべてのシェアを集めなくても元の秘密情報を復元することが可能であるという特性を有する。
【０００４】
しかし、ｋ個のシェアで元の秘密情報を復元できるため、シェアに改竄があった場合、復元時の情報が変化してしまうという問題がある。全ての組み合わせで復元を行えば改竄を発見できるが、実際の組み合わせは膨大な数に及ぶため、改竄の検出は困難なことが多い。また過半数以上のシェアに改竄があった場合、誤った結果を正しい結果と認識してしまうおそれもある。
【０００５】
この問題を解決できる秘密分散法が非特許文献１に開示されている。
【０００６】
非特許文献１には、ペル方程式を用いて、各シェアそれぞれが改竄を検知することが可能な秘密分散法が提案されている。
【０００７】
この方式により，シェアの誤りを検知することで、シェアの全ての組み合わせを試すことなく、また誤った結果を正しい結果と認織することなく情報を復元することが出来る。
【０００８】
非特許文献１に開示されている秘密分散法を説明する。
１． 前提
１−１． 中国の剰余定理
正の整数ｍ１，ｍ２が互いに素であるとき、任意の整数ａ１，ａ２に対して（１）と（２）の連立合同式には解ｘが存在し、その解はすべてＮ＝ｍ１・ｍ２を法として合同である。
ｘ≡ａ１（ｍｏｄ ｍ１）...（１）
ｘ≡ａ２（ｍｏｄ ｍ２）...（２）
【０００９】
２． ペル方程式
２−１． （３）式をペル方程式という。
ｘ２−ｄ・ｙ２＝１ ...（３）
（ｄ∈Ｎ，√ｄ∈Ｑ，Ｎ：自然数，Ｑ有理数）
この方程式を満たす解ｘ，ｙは無数に存在する。ペル方程式の解をｚ＝ｘ＋ｙ√ｄと表現したとき、全ての解で最小の解を基本解という。
【００１０】
３． ペル方程式の諸定理
（４）式をペル方程式の基本解の判別式といい、（４）式を満たし、ｚ＝ａ＋ｂ√ｄがペル方程式の解となるならば、それが基本解である。
ｄ∈Ｎ，√ｄ∈Ｑ，ａ，ｂ∈Ｎ、
ａ≧［ｂ２／２］ ...（４）
【００１１】
４． 分散フェーズ
４−１． まず、分散対象の秘密情報Ｓを、ルート部分だけは、子ノードの和、それ以外のノードは子ノードの積で計算できるように秘密情報Ｓをグループに分解し、ツリー（木）構造とすることで、シェア一つ一つのサイズを小さくする。
【００１２】
４−２． ノードグループＳｉについて、全てのｘｊ＝１＋ｕｊ・ｖｊ２が互いに素となるように、ｕｊ，ｖｊ（ｊ＝１，２，．．．ｎ）をランダムに発生させる。
４−３． ツリーのノードを構成する情報Ｓｉを、ｘj（＝１＋ｕｊ・ｖｊ２）で割った余りαｊを求める。
４−４． 自然数ｄｊ＝ｕｊ・（ｕｊ・ｖｊ２＋２）を求める。
４−５． この時の（ｉ，ｕｊ，ｖｊ，αｊ）がシェアとなる。
４−６． ４−２〜４−５の処理をすべてのノードで行う。このとき、ノードグループ毎にｎの値は異なってもよい。
【００１３】
５． 復元フェーズ
５−１． シェア１つを取り出す。
５−２． 後述する改竄の有無の判定を行う。
５−３． 改竄がなければ、復元処理を行えるシェアとして利用可能なので、保持しておく。
５−４． ５−１〜５−３の処理をすべてのシェアで行う。
５−５． 保持しておいた全てのシェアから、ノードグループ固有の番号ｉで分類を行う。
５−６． （５）式に示すように、ｉで分類されたシェアから作られた合同式を連立させ、その解ｘｉで分類されたｋ個のシェアから作られた合同式を連立させ、その解ｘｉを求める。
ｘｉ≡ αij（ｍｏｄ ｌ＋ｕij・ｖij２） ...（５）
（１≦ｉ≦ｚ）（１≦ｊ≦ｋ）ｚ：ノードグループ数、ｋ＝ノードグループの情報復元に必要なシェア数の閾値
５−７． 全てのグループで解を求め、ツリーを作る。
５−８． ツリーの部分木に注目し、計算が合うかチェックを行う。
５−９． ツリー上の計算が合えば、ツリーのルート部分が、秘密情報Ｓとなる。
【００１４】
６． 改竄判定の方法
改竄の判定はペル方程式を用いて行う。
改竄があれば、シェアはペル方程式や，ペル方程式の基本解の判別式を満たさないことから改竄の検知が可能となる。
６−１． ｘｉ＝１＋ｕｉ・ｖｉ２，ｙ＝ｖｉとして，それぞれ（３）式で示すペル
方程式に代入し，式が成立するか判定を行う。
６−２． ペル方程式が成立した場合、（４）式にａ＝ｘ，ｂ＝ｙを当てはめ、基本解であるか否か判定する。
６−３． 基本解であれば、改竄は行われていないと判定する。
【００１５】
【非特許文献１】ペル方程式を用いた改竄検知可能な秘密分散法の提案 平成２０年２月４日、広島市立大学 平成１９年度修士論文 情報メディア工学科 ソフトウエア工学講座 武田 雄人
【発明の開示】
【発明が解決しようとする課題】
【００１６】
非特許文献１に開示された手法によれば、ペル方程式を用いてシェアの改竄の有無を容易に検出することができ、さらに、ツリーを用いて復元された情報相互の関係から改竄を検出することも可能となる。
【００１７】
しかしながら、この手法によれば、ｕとｖとを公開するので、ｄ（＝ｕ・（ｕ・ｖ２＋２））を完全に復元できる。従って、新しい３つ組ｕ’，ｖ’，ｄ’を生成して、改竄を検知できないようにして、復元を困難にすることが可能となる。
【００１８】
本発明は、上記実情に鑑みてなされたものであり、シェアの改竄を防止可能な秘密分散法を提供することを目的とする。
また、本発明は、より信頼性の高いペル方程式を用いた改竄検知可能な秘密分散法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、この発明の第１の観点に係る秘密情報分散装置は、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段と、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段と、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段と、
自然数ｔｊを含むシェアを生成して分散する分散手段と、
を備えることを特徴とする。
【００２０】
秘密情報Ｓをｚ個のノードを有する木構造に分解する手段をさらに有し、
前記ｘｊ生成手段は、第ｉ（ｉ＝０，１，．．．，ｚ−１）のノードグループのそれぞれについて、複数の自然数ｘijを生成し、
前記除算手段は、各ノードの値Ｓｉを自然数ｘｉｊで割った剰余αｉｊを求め、
前記ゲーデル数化手段は、各ノードについて、前記自然数ｘｉｊと剰余αｉｊとを、素数を用いてゲーデル数化して、自然数ｔｉｊを生成し、
前記分散手段は、各ノードについて、自然数ｔｉｊを含むシェアを生成して分散する、
ように構成してもよい。
【００２１】
前記ゲーデル数化手段は、例えば、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐｚj2に代入することにより、自然数ｔｊを求める。なお、ｚｊ１とｐは互いに素、ｐは素数である。
【００２２】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄ・ｙｊ２＝１を満たす自然数ｄｊを求める手段と、
求めた「自然数」ｄｊを、正当権限を有する者に配布する手段と、
をさらに配置してもよい。
【００２３】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段をさらに備え、
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐ１ｚj2・ｐ２ｄjに代入することにより、自然数ｔｊを求めるようにしてもよい。なお、ｚｊ１とｐ１とｐ２は互いに素、ｐ１、ｐ２は素数である。
【００２４】
また、この発明の第２の観点に係る秘密情報復元装置は、
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアに含まれている自然数ｔjを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、
再生された前記自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する復元手段と、
を備えることを特徴とする。
【００２５】
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアをノードの番号ｉで分類する分類手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、ノードグループ毎に、再生された前記自然数ｘｊと剰余αｊとの連立合同式を解くことにより各ノードＳｉの値を復元する、ように構成してもよい。
【００２６】
上述の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
外部より、自然数ｄｊを受信する受信手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと、受信したｄｊとを用いて、各シェアの改竄の有無を検証し、改竄が無いと判別したシェアに基づいて、秘密情報Ｓを復元するように構成してもよい。
【００２７】
上述の秘密情報分散装置により、生成されたシェアを記憶する手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊと自然数ｄｊを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと自然数ｄｊとを用いて各シェアの改竄の有無を検証し、改竄が無いと判別したシェアを用いて秘密情報Ｓを復元する、ように構成してもよい。
【００２８】
コンピュータを、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段、
自然数ｔｊを含むシェアを生成して分散する分散手段、
として機能させるコンピュータプログラムを生産・配布してもよい。
【発明の効果】
【００２９】
本発明によれば、秘密情報をより安全に分散させることができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の実施の形態にかかる秘密分散・復元システム１００について説明する。
【００３１】
この秘密分散・復元システム１００は、秘密情報Ｓを、ペル方程式を用いて改竄検知可能な形態で複数のシェアに秘密分散する一方、収集された複数のシェアから元の秘密情報Ｓを復元する機能を備える。
【００３２】
図１に示すように、秘密分散・復元システム１００は、制御部１０と、記憶部２０と、入力部３０と、出力部４０と、通信部５０と、から構成される。
【００３３】
制御部１０は、記憶部２０に記憶された動作プログラムに従って動作し、後述する秘密分散処理、改竄検知処理、復元処理などを行う。
【００３４】
記憶部２０は、ＲＡＭ (Random Access Memory)、ＲＯＭ (Read Only Memory)、ハードディスク装置、フラッシュメモリなどから構成され、制御部１０の動作プログラムを記憶し、また、制御部１０のワークエリアとして機能する。
【００３５】
記憶部２０は、ＲＡＭ、ＲＯＭ、ハードディスク装置、フラッシュメモリなどから構成され、記憶手段として、制御部１０の動作プログラムを記憶し、任意のデータを記憶し、また、制御部１０のワークエリアとして機能する。
【００３６】
入力部３０は、任意の入力装置から構成され、分散対象の秘密情報Ｓ、復元対象の複数のシェアなどを入力する。
【００３７】
出力部４０は、任意の出力装置から構成され、分散対象の秘密情報Ｓを秘密分散して得られた複数のシェア、複数のシェアから復元した秘密情報Ｓ等を出力する。また、出力部４０は、正当権限を有する者に、秘密情報Ｓを復元するために必要な情報（後述する自然数ｄ）を配布するための処理を行う。
【００３８】
通信部５０は、外部装置との間で通信を行い、種々のデータ、例えば、分散対象の秘密情報Ｓ、生成された複数のシェア、復元対象の複数のシェア、複数のシェアから復元した元の秘密情報Ｓ等を、送受信する。また、通信部５０は、正当権限を有する者に、秘密情報Ｓを復元するために必要な情報（後述する自然数ｄ）を配布するための処理を行う。
【００３９】
次に、上記秘密分散・復元システム１００により、秘密情報Ｓを複数のシェアに分散し、続いて、複数のシェアから秘密情報Ｓを復元する手順を図２に示すフローチャートを参照して説明する。
【００４０】
まず、制御部１０は、秘密情報Ｓを決定する（ステップＳ１０１）。秘密情報Ｓは、例えば、入力部３０から入力されたデータ、通信部５０を介し受信したデータ、或いは、これらを加工して得たデータである。
【００４１】
次に、制御部１０は、秘密情報Ｓを、ｚ個のノードを持つ木（ツリー）構造に分解する（ステップＳ１０２）。ここで、ツリー構造の第１階層のノードは、それらの値の和が秘密情報Ｓの値となる数値とし、第２階層以下のノードは、上位ノードの値が下位ノードの積となるように分解する。即ち、秘密情報Ｓを和がＳとなる素数以外の２つの数値Ｓ０，Ｓ１に分割し、さらに、値Ｓ０とＳ１をそれぞれ、積がＳ０，Ｓ１となる２つの値に分割し、同様の分割を繰り返して、ノードの数をｚ個とする。
【００４２】
例えば、ｚ＝６とすると、図１０に例示するように、秘密情報Ｓを、和がＳとなる素数以外の２つの数値Ｓ０，Ｓ１に分割する。さらに、値Ｓ０とＳ１をそれぞれ、積がＳ０，Ｓ１となる２つの値Ｓ２とＳ３、Ｓ４とＳ５に分割する。従って、Ｓ＝Ｓ０＋Ｓ１、Ｓ０＝Ｓ２・Ｓ３、Ｓ１＝Ｓ４・Ｓ５が成立する。
【００４３】
次に、ノードを特定するポインタｉに０をセットする（ステップＳ１０３）。さらに、ノードＳｉに対するシェアの番号を示すポインタｊに０をセットする（ステップＳ１０４）。
【００４４】
次に、ポインタｉで特定されるノードＳｉについて、全ての１＋ｕｊ・ｖｊ２が互いに素となり、且つ、ｋ個の１＋ｕｊ・ｖｊ２の積がノードの値Ｓｉ未満となるように、自然数ｕｉｊとｖｉｊの組をランダムに発生させる（ステップＳ１０５〜Ｓ１１０）。
【００４５】
具体的には、まず、自然数ｕｉｊと自然数ｖｉｊとを乱数で発生させる（ステップＳ１０５）。
【００４６】
次に、ｘｉｊ＝１＋ｕｉｊ・ｖｉｊ２を計算する（ステップＳ１０６）。
次に、gｃｄ（１＋ｕｉｊ・ｖｉｊ２）＝１(j=1,2,…k-1)が成立するか否かを判別する（ステップＳ１０７）。即ち、発生したk個のｘｉ（ｘｉ０〜ｘｉk）が、互いに素であるか否かを判別する。
【００４７】
発生したｘｉが互いに素の関係に無い場合（ステップＳ１０７；Ｎｏ）、ステップＳ１０５にリターンし、再度、自然数ｕｉｊと自然数ｖｉｊとを乱数で発生させる。
【００４８】
一方、ステップＳ１０７で、gｃｄ（ｘｉj）＝gｃｄ（１＋ｕｉｊ・ｖｉｊ２）＝１が成立すると判別された場合、すなわち、発生された全てのｘｉｊが互いに素であると判別された場合（ステップＳ１０７；Ｙｅｓ）、生成したｋ個のｘｉｊの積が第ｉのノードＳｉの値より大きいか否かを判別する（ステップＳ１０８）。積がノードＳｉの値に等しいか小さければ（ステップＳ１０８；Ｎｏ）、ステップＳ１０５にリターンする。
【００４９】
ステップＳ１０８で、ｋ個のｘｉｊの積がＳｉよりも大きいと判別された場合（ステップＳ１０８；Ｙｅｓ）、ノードＳｉについて、全ての１＋ｕｉｊ・ｖｉｊ２が互いに素となり、且つ、ｋ個のｘｉｊの積がＳｉより大きくなる自然数ｕｉｊとｖｉｊが揃ったことになる。
【００５０】
続いて、Ｓｉをｘｉｊで割った余りαｉｊを求める（ステップＳ１０９）。即ち、Ｓｉ≡αｉｊ（ｍｏｄ （１＋ｕｉｊ・ｖｉｊ２））が成立するαｉｊを求める。
【００５１】
さらに、αijをペル方程式の基本解とする値ｄｉｊ＝ｕｉｊ・（ｕｉｊ・ｖｉｊ２＋２）を求める（ステップＳ１１０）。
【００５２】
求めた値の組（ｉ，ｘｉｊ，αｉｊ）をシェアの１つとして記憶部２０に記憶する（ステップＳ１１１）。
【００５３】
次に、値ｊが所定値ｋ−１であるか否かを判別する（ステップＳ１１２）。
値ｊがｋ−１未満であると判別された場合（ステップＳ１１２；Ｎｏ）、ポインタｊを＋１して（ステップＳ１１３）、ステップＳ１０５にリターンし、同様の動作を繰り返す。
【００５４】
値ｊ＝ｋ−１であると判別された場合（ステップＳ１１２；Ｙｅｓ）、値ｉが所定値ｚ−１であるか否かを判別する（ステップＳ１１４）。
ｉがｚ−１未満であると判別された場合（ステップＳ１１４；Ｎｏ）、ポインタｉを＋１して（ステップＳ１１５）、ステップＳ１０４にリターンし、同様の動作を繰り返す。
【００５５】
一方、ｉ＝ｚ−１であると判別された場合（ステップＳ１１４；Ｙｅｓ）、全てのノードＳi（Ｓ０〜Ｓｚ−１）についてシェアを求める処理が終了したことになる。
【００５６】
ステップＳ１１１で格納したシェアは、そのままでは、背景技術の欄で説明したように、それ自体が改竄され、復元を不可能とされるおそれがある。
そこで、シェアの改竄を防止するため、ステップＳ１１６で、ｘｉｊとαｉｊを変換する。
【００５７】
この変換処理の詳細を図３を参照して説明する。
まず、ノードを特定するポインタｉを０に（ステップＳ２０１）、各ノードについてシェアを特定するポインタｊを０にセットする（ステップＳ２０２）。
続いて、ポインタｉとｊで特定されるシェアについて、次式により、ｘｉｊとαｉｊとをｚｉｊ１とｚｉｊ２に直交変換する（ステップＳ２０３）。
【００５８】
Ｚij1＝ｘij＋αij
Ｚij2＝ｘij−αij
【００５９】
次に、任意の素数ｐを発生させる（ステップＳ２０４）。
【００６０】
次に、ｇｃｄ（Ｚij1，ｐ）＝１が成立するか否か、すなわち、Ｚij1とｐとが互いに素であるか否かを判別する（ステップＳ２０５）。
成立しなければ（ステップＳ２０５；Ｎｏ）、ステップＳ２０４にリターンして、素数ｐを発生させる。
成立すれば（ステップＳ２０５；Ｙｅｓ）、数式（２）に従って、生成したＺij１とＺji２を素数ｐを用いてゲーデル数化して自然数ｔijを生成する（ステップＳ２０６）。
【００６１】
ｔｉｊ＝Ｚij1・ｐＺij2 ．．．．（２）
ここで、ｇｃｄ（Ｚij1，ｐ）＝１
【００６２】
次に、（ｉ，ｔｉｊ）を１つのシェアとする（ステップＳ２０７）。
【００６３】
次に、値ｊが所定値ｋ−１であるか否かを判別する（ステップＳ２０８）。
値ｊがｋ−１未満であると判別された場合（ステップＳ２０８；Ｎｏ）、ポインタｊを＋１して（ステップＳ２０９）、ステップＳ２０３にリターンし、同様の動作を繰り返す。
【００６４】
ｊ＝ｋ−１であると判別された場合（ステップＳ２０８；Ｙｅｓ）、値ｉが所定値ｚ−１であるか否かを判別する（ステップＳ２１２）。
ｉがｚ−１未満であると判別された場合（ステップＳ２１２；Ｎｏ）、ポインタｉを＋１して（ステップＳ２１１）、ステップＳ２０２にリターンし、同様の動作を繰り返す。
【００６５】
一方、ｉ＝ｚ−１であると判別された場合（ステップＳ２１２；Ｙｅｓ）、全てのノードＳi（Ｓ０〜Ｓｚ−１）についてシェアを変換する処理が終了したことになり、図２のメインフローにリターンする。
【００６６】
制御部１０は、こうして生成したシェア（ｉ，ｔｉｊ）を出力部４０又は通信部５０から出力又は送信する。
また、制御部１０は、ステップＳ１０５，Ｓ１１０で生成した値ｕｉｊ、ｖｉｊ、ｄｉｊ等のデータを記憶部２０に保存する。
また、制御部１０は、秘密情報Ｓを復元する正当権限を有する者に、出力部４０又は通信部５０を介して、自然数ｄを、シェアの改竄の有無を判定するために配布するための処理を行う。
【００６７】
次に、こうして分散されたシェアから元の秘密情報Ｓを復元する動作を説明する。
【００６８】
まず、制御部１０は、入力部３０或いは通信部５０を介し入手したシェアと自然数ｄijを記憶部２０に格納しておく。
【００６９】
制御部１０は、図４に示す改竄判定処理を適宜行い、記憶部２０に記憶しておいたシェアを取り出し（ステップＳ３０１）、改竄の有無を判定し（ステップＳ３０２）、改竄が無いと判別すると（ステップＳ３０２；Ｎｏ）、復元処理を行えるシェアとして利用可能なので、保持しておく（ステップＳ３０３）。一方、改竄があると判定すると（ステップＳ３０２；Ｙｅｓ）、そのシェアを廃棄する（ステップＳ３０４）。続いて、全てのシェアについて処理が終了したか否かを判別し（ステップＳ３０５）、全てのシェアについて改竄の判定が終了していれば（ステップＳ３０５；Ｙｅｓ）、改竄判定処理を終了し、終了していなければ（ステップＳ３０５；Ｎｏ）、ステップＳ３０１にリターンして、次のシェアについて同様の処理を行う。
【００７０】
ステップＳ３０２で実行する改竄有無の判定は、ペル方程式を用いて行う。
改竄があれば、シェアはペル方程式や、ペル方程式の基本解の判別式を満たさないことから改竄の検知が可能となる。
このペル方程式を用いた改竄有無の判定手順について、図５を参照して説明する。
【００７１】
前述のように、制御部１０は、事前に、ディーラ（シェアを配布した者）より配布された自然数ｄijを、記録媒体或いは通信により、入力部３０或いは通信部５０を介して受け取り、記憶部２０に格納しておく。
【００７２】
制御部１０は、ステップＳ３０１で選択したシェアから自然数値ｔijを抽出する（ステップＳ３２１）。
自然数ｔｉjを素因数分解し、Ｚij１・ｐＺij２（ｐは素数）の形式とし、Ｚ１とＺ２とを求める（ステップＳ３２２）。
【００７３】
次に、ｘij＝（Ｚij１＋Ｚij２）／２から、ｘijを求める（ステップＳ３２３）。
次に、ディーラより受信しておいた、自然数ｄｉｊとｘijから、xij−ｄij・ｖij2＝１に代入し、ｖijを求める（ステップＳ３２４）。
次に、ｖijが自然数か否か判別する（ステップＳ３２５）。自然数であれば（ステップＳ３２５；Ｙｅｓ）、ペル方程式が成立し、改竄検知の必要条件を満たす。
【００７４】
次に、ｕijとｖijがペル方程式の基本解の判別式を満たすか否かを判別する。すなわち、 ｕij≧［ｖij２／２］を満たすか否かを判別する（ステップ３２６）。
【００７５】
基本解の判別式を満たすと判別した場合（ステップＳ３２６；Ｙｅｓ）、改竄は行われていないと判別する（ステップ３２７）。
【００７６】
一方、基本解の判別式を満たさないと判別した場合（ステップＳ３２６；Ｎｏ）、改竄が行われていると判別する（ステップ３２８）。
【００７７】
このようにして、各シェアについて、ペル方程式を満たすか否か、更に、ペル方程式の基本解の判別式を満たすか否かを判別することにより、シェアの改竄の有無を迅速に判別することができる。さらに、改竄されていると判別されたシェアを破棄することにより、秘密情報Ｓを誤って復元する事態を防止できる。
【００７８】
次に、改竄されていないと判別されたシェアを用いて秘密情報Ｓを復元する処理を図６のフローチャートを参照して説明する。
【００７９】
制御部１０は、記憶部２０に保持しておいた全てのシェア（ｉ,ｊ，ｔｉｊ）を、ノード固有の番号ｉで分類する（ステップＳ４０１）。
ｉ＝０とおく（ステップＳ４０２）。
ｉで分類された全てのシェアから作られたｋ個の連立合同式をガウスの方法を用いて解き説き、その解Ｓｉ（≡αij (ｍｏｄ ｘij）)を求める（ステップＳ４０３）。
【００８０】
次に、ｉ＝ｚ−１であるか否か、即ち、全てのノードについて値Ｓｉが求められたか否かを判別する（ステップＳ４０４）。
【００８１】
ｉ＜ｚ−１であれば（ステップＳ４０４；Ｎｏ）、未処理のノードが残っているので、ｉ＝ｉ＋１として（ステップＳ４０５）、ステップＳ４０３にリターンし、解Ｓｉを求める。
【００８２】
一方、ｉ＝ｚ−１であれば（ステップＳ４０４；Ｙｅｓ）、全てのノードの値Ｓｉの復元が終了したので、値Ｓｉを用いて、ツリーを再生する（ステップＳ４０６）。
【００８３】
続いて、ツリーを検証する（ステップＳ４０７）。即ち、ツリーの部分木に注目し、直下の２つのノード値の積（ルートについては和）が当該ノードの値に等しいか検査を行う。全てのノードについて、直下の２つのノード値の積（ルートについては和）に等しい場合に、ツリーが正しいと判別する。
【００８４】
ツリーが正しいと判別した場合（ステップＳ４０８；Ｙｅｓ）、ツリーのルートで合成される値を秘密情報Ｓとする（ステップＳ４０９）。
一方、ツリーが正しくないと判別した場合（ステップＳ４０８；Ｎｏ）、所定のエラー処理を行い（ステップＳ４１０）、例えば、シェアの改竄を報知する等の処理を行う。
こうして、秘密情報Ｓが復元される。
【００８５】
この実施の形態によれば、シェアを構成する情報ｘｉとαｉとを素数ｐを用いてゲーデル数化し自然数ｔｉを生成し、これを分散する。
【００８６】
このため、シェアの元の情報ｘｉとαｉを推定することが困難となり、シェアの改竄をより困難とすることができる。
また、シェアの改竄をペル方程式および再生されたツリー構造から検証するので、シェアの改竄の有無を迅速に判別でき、改竄されたシェアを用いて秘密情報Ｓを復元する事態を防止できる。
【００８７】
（第２実施形態）
上記第１の実施形態においては、シェアを復元する際に、ディーラより、値ｄij（＝uij・（ｕij・ｖij２＋２））を復元先に配布する必要があったが、ｄijをシェアに含めることも可能である。
【００８８】
例えば、
ｔｉ＝ｚｉｊ１・ｐ１Ｚｉｊ２・ｐ２ｄij
ｐ１，ｐ２は素数、ｚｉｊ１、ｐ１、ｐ２は互いに素、ｐ１＞ｐ２とすれば、
自然数ｔijにｄijを含めることができる。
【００８９】
秘密情報Ｓを復元する際には、シェアに含まれている自然数ｔｉを素因数分解し、ａ・ｐ１ｎ・ｐ２ｍの形式とし、ｐ１＞ｐ２より、Ｚij1＝ａ、Ｚij2＝ｎ、ｄij＝ｍとし、さらに、ｘｉ＝（Ｚij1＋Ｚij2）／２、αｉ＝（Ｚij1−Ｚij2）／２とすることにより、シェアを復元することができる。
【００９０】
同様の手法により、ｕij、ｖijを自然数ｔijに含ませることも可能である。
【００９１】
また、上記実施の形態においては、シェアを構成する自然数ｘｉとαｉとを、直交変換によりｚｉｊ１、ｚｉｊ２に変換したが、変換後のｚｉｊ１、ｚｉｊ２から自然数ｘｉとαｉとを再生できるならば、任意の変換式を使用可能である。
【００９２】
さらに、
ｔｉ＝αｉｊ・ｐ１ｘij・ｐ２ｄij
ｔｉ＝ｘｉｊ・ｐ１αｉｊ・ｐ２ｄij
とする等してもよい。
また、シェアを（ｉ，ｊ，ｔｉｊ）としてもよい。このようにすれば、ｊの特定が容易である。
【００９３】
（応用例１）
次に、上記構成を用いた秘密分散方法の応用例について説明する。
土木・建築工事において、生コンは、必須の素材である。一方、生コンの品質物を均一に維持することは困難であり、工事完了後に、生コンの品質をチェックしたい場合が発生することがある。
【００９４】
しかしながら、建設現場における生コンのサンプル採取作業の徹底が不十分なため、生コン生還過程の追跡性が悪く、事故発生後に、生コンサンプル分析データを活用した原因究明等がなされていないという背景がある。
【００９５】
そこで、以下、生コンサンプル採取及び分析データ管理の効率化と事故後の生コンサンプル分析データ照合作業の効率化を可能とする方法を提供する。
まず、システムの全体図を図７に示す。
【００９６】
図示するように、生コンは、工場１０１で生産され、ミキサー車１０２に積載され、建設現場１０３に搬入される。
工場１０１では、生コンの生産データ１０１ａが管理されており、生産日・時間、材料・ロット、製造記録などの情報がデータベースで記録・管理されている。
【００９７】
ミキサー車１０２の担当者は、積載する生コンの生産データ１０１ａを自己の携帯端末１１１に記録する。この携帯端末は図１に示す秘密分散・復元システム１００と同様の構成を有する。なお、出力部４０はＲＦＩＤのリーダライタを含む。
【００９８】
ミキサー車１０２の担当者は、工場からの搬出時間・工事現場への搬入時間、搬入場所等のデータも自己の携帯端末１１１に入力部３０等から入力する。
【００９９】
続いて、建設現場１０３に着くと、ミキサー車１０２の担当者は、携帯端末１１１に、搬入時間、搬入場所等のデータ１０２ａを入力する。
【０１００】
次に、建設現場担当者は、搬入された生コンからサンプル１０６を取り出し、ＲＦＩＤチップ１０７を埋め込む。
【０１０１】
担当者は、携帯端末１１１にサンプル用ＲＦＩＤチップ１０７のＩＤを入力する。
【０１０２】
携帯端末１１１は、入力された情報、すなわち、生産情報、搬入記録、サンプルチップのＩＤ等から複数のシェアを生成し、これらを複数のＲＦＩＤ１０５に分散して格納する。同一のシェアを複数のＲＦＩＤ１０５に記録してもよい。
【０１０３】
続いて、ＲＦＩＤチップ１０５を生コン１０４に埋め込む。
生コン１０４は、打設され、構造物の一部を構成する。
【０１０４】
一方、ＲＦＩＤ１０７が埋め込まれた生コンサンプル１０６は、所定の試験機関１０８に搬送され、分析される。
【０１０５】
分析結果１０９は、生コンサンプル１０６に埋め込まれたＲＦＩＤ１０７のＩＤに対応付けて、ＤＢ等に格納される。
【０１０６】
建築物に問題が発生した場合、図１に示す構成を有するＲＦＩＤの読み取り装置により、問題箇所に埋め込まれているＲＦＩＤ１０５に格納されているシェアを読み取る。前述のように、ＲＦＩＤ１０５には、生コンサンプル１０６に埋め込まれたＲＦＩＤ１０７のＩＤ、生産データ、輸送・搬入データがシェアの形態で格納されている。
【０１０７】
読み取り装置は、読み取ったシェアが改竄されているか否かを、上述したように、ペル方程式に基づいて判別し、上述した手法により、各ノードの値を復元し、さらに、秘密情報を復元する。
【０１０８】
この秘密情報は、サンプル用ＲＦＩＤ１０７のＩＤを含む。
担当者は、復元した情報に含まれているサンプルＩＤをキーにＤＢを検索し、該当するＩＤに対応付けられている分析データを読み出す。
【０１０９】
これにより、問題部分のコンクリートの、生産データ、輸送・搬入データ、さらに、サンプル分析データを取得して、問題を解析することが可能となる。
なお、最終的に問題箇所に使用された生コンのサンプルが特定できるならば、ＲＦＩＤチップ１０５に格納される情報自体は任意に変更可能である。
【０１１０】
（応用例２）
この例では、電子投票を行う場面で、投票結果を集計装置に集積する場面を想定する。
【０１１１】
例えば、図８に示すように、複数の投票所２０１（２０１Ａ〜２０１Ｃ）に、それぞれ、複数台の投票端末２０２（２０２１〜２０２ｎ）と投票端末２０２に接続された蓄積装置２０３が配置されているとする。
【０１１２】
投票端末２０２は、投票が行われる度に、投票番号、投票者、時刻等の情報を含む投票情報を生成し、暗号化した上で、蓄積装置２０３に送信する。
【０１１３】
蓄積装置２０３は、各投票端末２０２から送信された投票情報を受信し、二重化などの安全処理を施した上で、ハードディスク装置２０４等に蓄積する。
【０１１４】
投票時間終了後、蓄積装置２０３は、蓄積した情報を秘密情報Ｓとして、複数のノードを形成し、各ノードから複数のシェアを生成し、複数の記憶装置２０５に分散して記憶させる。ここで、各記憶装置２０５には、互いに異なる組み合わせではあるが、個々の記憶装置に格納されているシェアのみから元の秘密情報Ｓを復元できるシェアを選択して格納する。
【０１１５】
続いて、複数の記憶装置２０５を、例えば、別々の搬送手段で、集計所に搬送する。
【０１１６】
集計所２０６に設置された集計装置２０７は、複数の記憶装置２０５に格納されたシェアを読み取り、ペル方程式に基づいて各シェアの改竄の有無を判別する。
【０１１７】
改竄が無いと判別すると、シェアから各ノードを復元し、続いて ノード同士の関係から改竄の有無を検証する。さらに、ノード相互の関係も正常であれば、ルートのノードを求め、これを元の情報とする。
【０１１８】
複数の投票所２０１から提供されたシェアから復元した投票情報を元に、投票数を集計する。
【０１１９】
このような構成とすれば、搬送の途中で一部の情報が失われたとしても、残りの情報で元の情報を再生することができ、秘密情報の搬送及び再生を安全に行うことができる。
【０１２０】
（応用例３）
一般の通信に上述の技術を応用することが可能である。
【０１２１】
ここでは、一例として、任意の音声データや画像データを安全に有線又は無線で送信する場合を想定する。
【０１２２】
図９に示すように、送信装置３０１は、送信対象のデータをバッファ等に蓄積する。送信装置３０１は、バッファ等に蓄積したデータを所定量（例えば、フレーム単位）ずつ読み出し、暗号化する。
【０１２３】
さらに、送信装置３０１は、暗号化した所定量の情報を秘密情報Ｓとして、複数のノード、例えば、ノードＳ０〜Ｓ５に分割する。続いて、各ノードについて、複数のシェアを生成する。
【０１２４】
続いて、送信装置３０１は、複数の伝送チャネルにシェアを割り振る。この際、送信装置３０１は、１つの伝送チャネルを伝送されるシェアをモニタするのみでは、元のデータを復元できないように、シェアを配分する。送信装置３０１は、分配された各シェアを各伝送チャネルを介して送信する。
【０１２５】
一方、受信装置３０２は、複数の伝送チャネルを介して送信されてきたシェアを受信し、受信したシェアの改竄の有無をペル方程式を用いて判別する。改竄を検出した場合には、シェアを廃棄し、改竄が無いと判別するとシェアを蓄積する。
【０１２６】
続いて、受信装置３０２は、受信したシェアからノードＳ０〜Ｓ５を復元する。
さらに、復元したノード相互の整合性をチェックする。整合性が取れていれば、ルート部分を秘密情報Ｓとする。この処理を、フレーム毎に行う。
【０１２７】
このような構成とすれば、秘密情報を安全に送信することが可能となる。
【０１２８】
以上、本発明の実施形態および応用例について説明したが、これらは一例であり、種々の変形、応用、他技術との組み合わせが可能であり、これらも請求項に記載されている発明や発明の実施形態に記載されている具体例に対応する発明の範囲に含まれると理解されるべきである。
【０１２９】
例えば、システムの構成、処理の手順等は任意に変更可能である。
また、専用のシステムによらず、上述の分散処理および／又は復元処理を実行するためのコンピュータプログラムをコンピュータにインストールし、上述の秘密分散処理装置および／又は復元装置を形成し、秘密分散処理および／又は復元処理を実行させてもよい。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施の形態に係る秘密分散・復元システムのブロック図である。
【図２】分散処理のフローチャートである。
【図３】図２に示す変換処理の詳細を示すフローチャートである。
【図４】シェアの改竄の有無を検証する改竄判定処理のフローチャートである。
【図５】ペル方程式を用いた改竄判定の手順の詳細を示すフローチャートである。
【図６】復元処理のフローチャートである。
【図７】応用例１として、生コンのデータを管理するシステムの例を示す図である。
【図８】応用例２として、電子投票システムに適用した例を示す図である。
【図９】応用例３として、通信システムに適用した例を示す図である。
【図１０】秘密情報を複数のノードに分割する例を示す図である。
【符号の説明】
【０１３１】
１０…制御部
２０…記憶部
３０…入力部
４０…出力部
５０…通信部
１００…秘密分散・復元システム
【特許請求の範囲】
【請求項１】
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段と、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段と、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段と、
自然数ｔｊを含むシェアを生成して分散する分散手段と、
を備えることを特徴とする秘密情報分散装置。
【請求項２】
秘密情報Ｓをｚ個のノードを有する木構造に分解する手段を有し、
前記ｘｊ生成手段は、第ｉ（ｉ＝０，１，．．．，ｚ−１）のノードグループのそれぞれについて、複数の自然数ｘijを生成し、
前記除算手段は、各ノードの値Ｓｉを自然数ｘｉｊで割った剰余αｉｊを求め、
前記ゲーデル数化手段は、各ノードについて、前記自然数ｘｉｊと剰余αｉｊとを、素数を用いてゲーデル数化して、自然数ｔｉｊを生成し、
前記分散手段は、各ノードについて、自然数ｔｉｊを含むシェアを生成して分散する、
ことを特徴とする請求項１に記載の秘密情報分散装置。
【請求項３】
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐｚj2に代入することにより、自然数ｔｊを求める、なお、ｚｊ１とｐは互いに素、ｐは素数である、
ことを特徴とする請求項１又は２に記載の秘密情報分散装置。
【請求項４】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段と、
求めた自然数ｄｊを、正当権限を有する者に配布する手段と、
をさらに備えることを特徴とする請求項１乃至３のいずれか１項に記載の秘密情報分散装置。
【請求項５】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段をさらに備え、
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐ１ｚj2・ｐ２ｄjに代入することにより、自然数ｔｊを求める、なお、ｚｊ１とｐ１とｐ２は互いに素、ｐ１、ｐ２は素数である、
ことを特徴とする請求項１乃至３のいずれか１項に記載の秘密情報分散装置。
【請求項６】
請求項１乃至５のいずれか１項に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアに含まれている自然数ｔjを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、
再生された前記自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する復元手段と、
を備えることを特徴とする秘密情報復元装置。
【請求項７】
請求項１乃至５のいずれか１項に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
記憶手段に記憶されているシェアをノードグループの番号ｉで分類する分類手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、ノードグループ毎に、再生された前記自然数ｘｊと剰余αｊとの連立合同式を解くことにより各ノードＳｉの値を復元する、
ことを特徴とする秘密情報復元装置。
【請求項８】
請求項３に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
外部より、自然数ｄを受信する受信手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと、受信したｄｊとを用いて、各シェアの改竄の有無を検証し、改竄が無いと判別したシェアに基づいて、秘密情報Ｓを復元する、
ことを特徴とする秘密情報復元装置。
【請求項９】
請求項５に記載の秘密情報分散装置により、生成されたシェアを記憶する手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊと自然数ｄｊを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと自然数ｄｊとを用いて各シェアの改竄の有無を検証し、改竄が無いと判別したシェアを用いて秘密情報Ｓを復元する、
ことを特徴とする秘密情報復元装置。
【請求項１０】
コンピュータを、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段、
自然数ｔｊを含むシェアを生成して分散する分散手段、
として機能させるコンピュータプログラム。
【請求項１】
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段と、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段と、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段と、
自然数ｔｊを含むシェアを生成して分散する分散手段と、
を備えることを特徴とする秘密情報分散装置。
【請求項２】
秘密情報Ｓをｚ個のノードを有する木構造に分解する手段を有し、
前記ｘｊ生成手段は、第ｉ（ｉ＝０，１，．．．，ｚ−１）のノードグループのそれぞれについて、複数の自然数ｘijを生成し、
前記除算手段は、各ノードの値Ｓｉを自然数ｘｉｊで割った剰余αｉｊを求め、
前記ゲーデル数化手段は、各ノードについて、前記自然数ｘｉｊと剰余αｉｊとを、素数を用いてゲーデル数化して、自然数ｔｉｊを生成し、
前記分散手段は、各ノードについて、自然数ｔｉｊを含むシェアを生成して分散する、
ことを特徴とする請求項１に記載の秘密情報分散装置。
【請求項３】
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐｚj2に代入することにより、自然数ｔｊを求める、なお、ｚｊ１とｐは互いに素、ｐは素数である、
ことを特徴とする請求項１又は２に記載の秘密情報分散装置。
【請求項４】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段と、
求めた自然数ｄｊを、正当権限を有する者に配布する手段と、
をさらに備えることを特徴とする請求項１乃至３のいずれか１項に記載の秘密情報分散装置。
【請求項５】
ｙｊ＝ｖｊとしたときに、ペル方程式ｘｊ２−ｄｊ・ｙｊ２＝１を満たす自然数ｄｊを求める手段をさらに備え、
前記ゲーデル数化手段は、前記自然数ｘｊと剰余αｊとを、既知の変換式によりｚｊ１とｚｊ２とに変換し、さらに、ｔj＝ｚｊ１・ｐ１ｚj2・ｐ２ｄjに代入することにより、自然数ｔｊを求める、なお、ｚｊ１とｐ１とｐ２は互いに素、ｐ１、ｐ２は素数である、
ことを特徴とする請求項１乃至３のいずれか１項に記載の秘密情報分散装置。
【請求項６】
請求項１乃至５のいずれか１項に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
前記記憶手段に記憶されているシェアに含まれている自然数ｔjを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、
再生された前記自然数ｘｊと前記剰余αｊとに基づいて、秘密情報Ｓを復元する復元手段と、
を備えることを特徴とする秘密情報復元装置。
【請求項７】
請求項１乃至５のいずれか１項に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
記憶手段に記憶されているシェアをノードグループの番号ｉで分類する分類手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、ノードグループ毎に、再生された前記自然数ｘｊと剰余αｊとの連立合同式を解くことにより各ノードＳｉの値を復元する、
ことを特徴とする秘密情報復元装置。
【請求項８】
請求項３に記載の秘密情報分散装置により、生成されたシェアを記憶する記憶手段と、
外部より、自然数ｄを受信する受信手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊとを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと、受信したｄｊとを用いて、各シェアの改竄の有無を検証し、改竄が無いと判別したシェアに基づいて、秘密情報Ｓを復元する、
ことを特徴とする秘密情報復元装置。
【請求項９】
請求項５に記載の秘密情報分散装置により、生成されたシェアを記憶する手段と、
各シェアに含まれている自然数ｔｊを素因数分解し、分解した素因数に基づいて、前記自然数ｘｊと剰余αｊと自然数ｄｊを再生する再生手段と、を備え、
復元手段は、再生された前記自然数ｘｊと剰余αｊと自然数ｄｊとを用いて各シェアの改竄の有無を検証し、改竄が無いと判別したシェアを用いて秘密情報Ｓを復元する、
ことを特徴とする秘密情報復元装置。
【請求項１０】
コンピュータを、
ｘｊ＝１＋ｕｊ・ｖｊ２で表され、互いに素である複数の自然数ｘｊ（ｊ＝１，２，...，ｎ）の組を生成するｘｊ生成手段、
秘密情報Ｓを自然数ｘｊで割った剰余αｊを求める除算手段、
前記自然数ｘｊと剰余αｊとを、素数を用いてゲーデル数化して、自然数ｔｊを生成するゲーデル数化手段、
自然数ｔｊを含むシェアを生成して分散する分散手段、
として機能させるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−１１８９６８（Ｐ２０１０−１１８９６８Ａ）
【公開日】平成２２年５月２７日（２０１０．５．２７）
【国際特許分類】
【出願番号】特願２００８−２９１５８３（Ｐ２００８−２９１５８３）
【出願日】平成２０年１１月１３日（２００８．１１．１３）
【出願人】（５９６０５３０７９）
【Ｆターム（参考）】
【公開日】平成２２年５月２７日（２０１０．５．２７）
【国際特許分類】
【出願日】平成２０年１１月１３日（２００８．１１．１３）
【出願人】（５９６０５３０７９）
【Ｆターム（参考）】
[ Back to top ]