(57)【要約】【課題】秘密分散されたシェアを、秘密情報を復元することなく再生成するデータ再生成装置、データ再生成方法およびプログラムを提供する。【解決手段】秘密分散されたシェアを再生成するデータ再生成装置であって、シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、前記シェアのうち、あるシェアが消失した場合、消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成する。【選択図】図１
2014238546.tif 000002
【特許請求の範囲】
【請求項１】
秘密分散されたシェアを再生成するデータ再生成装置であって、
シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、
前記シェアのうち、あるシェアが消失した場合、
消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成する、
ことを特徴とするデータ再生成装置。
【請求項２】
消失シェアのシェア部分データの生成に用いられた秘密部分データを用いて生成された、消失シェア以外のシェアのシェア部分データと、乱数部分データで構成されるシェア部分データとの排他的論理和によって、消失シェアのシェア部分データを再生成する、
ことを特徴とする請求項１に記載のデータ再生成装置。
【請求項３】
消失シェアのシェア部分データの生成に用いられた秘密部分データを用いて生成された、消失シェア以外のシェアのシェア部分データは、
消失シェアのシェア部分データと比較して乱数部分データの排他的論理和の演算回数の差が１である、
ことを特徴とする請求項２に記載のデータ再生成装置。
【請求項４】
消失シェアのシェア部分データが乱数部分データで構成される場合には、
該乱数部分データを用いて生成されたシェア部分データと、該乱数部分データを用いずに生成されたシェア部分データとの排他的論理和によって、消失シェアのシェア部分データを再生成する、
ことを特徴とする請求項１から３のいずれか一項に記載のデータ再生成装置。
【請求項５】
消失シェア以外のシェアに含まれる２個のシェア部分データの排他的論理和によって、消失シェアのシェア部分データを再生成することを特徴とする請求項１から４のいずれか一項に記載のデータ再生成装置。
【請求項６】
シェアＤｉ（ｉ＝１〜３）は、秘密情報Ｓを２個に区分した秘密部分データＳ１、Ｓ２と、乱数Ｒを２個に区分した乱数部分データＲ１、Ｒ２とを用いて、
【数１】
2014238546.tif 000047
によって生成され、
シェアＤｐが消失した場合、シェアＤｉ（ｉ≠ｐ）を２個に区分したシェア部分データＤｉ，１、Ｄｉ，２を用いて、
【数２】
2014238546.tif 000048
によって再生成することを特徴とする請求項１から５のいずれか一項に記載のデータ再生成装置。
【請求項７】
シェアＤｉ（ｉ＝１〜ｎ，ｎ≧３）を区分したシェア部分データＤｉ，ｊ（ｉ＝１〜ｎ，ｊ＝１〜ｎ−１）は、ｊが同じ値であって、シェア部分データ内での排他的論理和の演算回数の差が１である２個のシェア部分データ同士の排他的論理和によって、秘密部分データまたは乱数部分データが復元される排他的論理和の定義式に従って生成され、
Ｄｎ，ｊ（ｊ＝１〜ｎ−１）は乱数部分データで構成され、
シェアＤｐが消失した場合、
ｐ≠ｎのとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊをＤｉ，ｊ（ｉ≠ｐ，ｉ≠ｎ）とＤｎ，ｑ（ｑ≠ｊ）との排他的論理和によって再生成し、
ｐ＝ｎのとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊをＤｉ，ｑ（ｉ≠ｎ，ｑ≠ｊ）とＤｒ，ｑ（ｒ≠ｎ，ｒ≠ｉ）との排他的論理和によって再生成する、
ことを特徴とする請求項１から５のいずれか一項に記載のデータ再生成装置。
【請求項８】
シェア部分データＤｉ，ｊは、秘密情報をｎ−１個に区分した秘密部分データＳｊ（ｊ＝１〜ｎ−１）と、乱数をｎ−１個に区分した乱数部分データＲｋ（ｋ＝１〜ｎ−１）とを用いて、ｉ＝１〜ｎ−１，ｊ＝１〜ｎ−１の各ｉ，ｊについてＤｉ，ｊが、第ｍ列（ｍ＝１〜ｎ−ｉ）の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｓｊとの排他的論理和で構成され、ｊ＝１〜ｎ−１の各ｊについてＤｎ，ｊがＲｊで構成され、
シェアＤｐが消失した場合、
ｐ＝１のとき、ｊ＝１〜ｎ−１の各ｊについてＤ１，ｊを、第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄ２，ｊとの排他的論理和によって再生成し、
１＜ｐ＜ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊを、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ＋１，ｊとの排他的論理和によって再生成するか、または、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ−１，ｊとの排他的論理和によって再生成し、
ｐ＝ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｎ−１，ｊを、第２列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｎ−２，ｊとの排他的論理和によって再生成し、
ｐ＝ｎのとき、ｊ＝１〜ｎ−１の各ｊについて第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応するＤｎのシェア部分データを、Ｄ１，ｊとＤ２，ｊとの排他的論理和によって再生成する、
ことを特徴とする請求項７に記載のデータ再生成装置。
【請求項９】
秘密分散されたシェアを再生成するデータ再生成方法であって、
シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、
前記シェアのうち、あるシェアが消失した場合、
消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成するステップを有することを特徴とするデータ再生成方法。
【請求項１０】
秘密分散されたシェアを再生成するためのプログラムであって、
シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、
前記シェアのうち、あるシェアが消失した場合、
消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成する処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ再生成装置、データ再生成方法およびプログラムに関する。
【背景技術】
【０００２】
情報の電子化が進展し、電子データを長期かつ安全に保管することが重要になっている。暗号や電子署名を用いると、これらの安全性は第三者が暗号鍵あるいは署名鍵を解読する計算の困難さに基づくので（計算量的安全性）、時間とともにコンピュータの性能が向上してアルゴリズムが危殆化する。そのため、機器の障害や災害に備えてバックアップを用意するコストに加えて、新たなアルゴリズムで暗号化や電子署名をやり直すなどのコストを要する。
【０００３】
上記のような計算量的安全性とは異なる情報量的安全性を有するものとして、秘密分散法がある。（ｋ，ｎ）しきい値秘密分散法は、秘密情報をｎ個の分散情報（以下、シェア）に分散し、ｎ個のシェアの中から任意のｋ個を組み合わせれば、元の秘密情報が復元できるが、ｋ−１個以下のシェアの組み合わせからでは、元の秘密情報に関する情報が全く得られない、というものである。この安全性はコンピュータの性能向上によっては影響されないので、電子データを長期かつ安全に保管することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４６７６６９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、（２，３）しきい値秘密分散法を用いた場合、３個のシェアのうちいずれか１個が消失すると、それ以上のシェア消失は秘密情報の復元を不可能にするので、３個のシェアが存在する状態を早急に回復する必要がある。このような場合、２個のシェアから秘密情報を復元して、任意のシェアを生成することが可能であるが、秘密情報が一時的に現われることになり、機密性が損なわれる。
【０００６】
本発明は、上記に鑑みてなされたもので、その目的とするところは、秘密分散されたシェアを、秘密情報が復元されることなく再生成するデータ再生成装置、データ再生成方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明は、秘密分散されたシェアを再生成するデータ再生成装置であって、シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、前記シェアのうち、あるシェアが消失した場合、消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成する、ことを特徴とするデータ再生成装置を提供する。
【０００８】
また、本発明では、消失シェアのシェア部分データの生成に用いられた秘密部分データを用いて生成された、消失シェア以外のシェアのシェア部分データと、乱数部分データで構成されるシェア部分データとの排他的論理和によって、消失シェアのシェア部分データを再生成する、ことを特徴とする。
【０００９】
また、本発明では、消失シェアのシェア部分データの生成に用いられた秘密部分データを用いて生成された、消失シェア以外のシェアのシェア部分データは、消失シェアのシェア部分データと比較して乱数部分データの排他的論理和の演算回数の差が１である、ことを特徴とする。
【００１０】
また、本発明では、消失シェアのシェア部分データが乱数部分データで構成される場合には、該乱数部分データを用いて生成されたシェア部分データと、該乱数部分データを用いずに生成されたシェア部分データとの排他的論理和によって、消失シェアのシェア部分データを再生成する、ことを特徴とする。
【００１１】
また、本発明では、消失シェア以外のシェアに含まれる２個のシェア部分データの排他的論理和によって、消失シェアのシェア部分データを再生成することを特徴とする。
【００１２】
また、本発明では、シェアＤｉ（ｉ＝１〜３）は、秘密情報Ｓを２個に区分した秘密部分データＳ１、Ｓ２と、乱数Ｒを２個に区分した乱数部分データＲ１、Ｒ２とを用いて、
【００１３】
【数１】
2014238546.tif 000003
【００１４】
によって生成され、
シェアＤｐが消失した場合、シェアＤｉ（ｉ≠ｐ）を２個に区分したシェア部分データＤｉ，１、Ｄｉ，２を用いて、
【００１５】
【数２】
2014238546.tif 000004
【００１６】
によって再生成することを特徴とする。
【００１７】
また、本発明では、シェアＤｉ（ｉ＝１〜ｎ，ｎ≧３）を区分したシェア部分データＤｉ，ｊ（ｉ＝１〜ｎ，ｊ＝１〜ｎ−１）は、ｊが同じ値であって、シェア部分データ内での排他的論理和の演算回数の差が１である２個のシェア部分データ同士の排他的論理和によって、秘密部分データまたは乱数部分データが復元される排他的論理和の定義式に従って生成され、Ｄｎ，ｊ（ｊ＝１〜ｎ−１）は乱数部分データで構成され、シェアＤｐが消失した場合、ｐ≠ｎのとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊをＤｉ，ｊ（ｉ≠ｐ，ｉ≠ｎ）とＤｎ，ｑ（ｑ≠ｊ）との排他的論理和によって再生成し、ｐ＝ｎのとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊをＤｉ，ｑ（ｉ≠ｎ，ｑ≠ｊ）とＤｒ，ｑ（ｒ≠ｎ，ｒ≠ｉ）との排他的論理和によって再生成する、ことを特徴とする。
【００１８】
また、本発明では、シェア部分データＤｉ，ｊは、秘密情報をｎ−１個に区分した秘密部分データＳｊ（ｊ＝１〜ｎ−１）と、乱数をｎ−１個に区分した乱数部分データＲｋ（ｋ＝１〜ｎ−１）とを用いて、ｉ＝１〜ｎ−１，ｊ＝１〜ｎ−１の各ｉ，ｊについてＤｉ，ｊが、第ｍ列（ｍ＝１〜ｎ−ｉ）の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｓｊとの排他的論理和で構成され、ｊ＝１〜ｎ−１の各ｊについてＤｎ，ｊがＲｊで構成され、シェアＤｐが消失した場合、ｐ＝１のとき、ｊ＝１〜ｎ−１の各ｊについてＤ１，ｊを、第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄ２，ｊとの排他的論理和によって再生成し、１＜ｐ＜ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊを、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ＋１，ｊとの排他的論理和によって再生成するか、または、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ−１，ｊとの排他的論理和によって再生成し、ｐ＝ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｎ−１，ｊを、第２列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｎ−２，ｊとの排他的論理和によって再生成し、ｐ＝ｎのとき、ｊ＝１〜ｎ−１の各ｊについて第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応するＤｎのシェア部分データを、Ｄ１，ｊとＤ２，ｊとの排他的論理和によって再生成する、ことを特徴とする。
【００１９】
さらに、本発明は、秘密分散されたシェアを再生成するデータ再生成方法であって、シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、前記シェアのうち、あるシェアが消失した場合、消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成するステップを有することを特徴とするデータ再生成方法を提供する。
【００２０】
さらに、本発明は、秘密分散されたシェアを再生成するためのプログラムであって、シェアを区分したシェア部分データは、秘密情報を区分した秘密部分データと乱数データを区分した乱数部分データとの排他的論理和、または、乱数部分データで構成され、前記シェアのうち、あるシェアが消失した場合、消失シェア以外のシェアに含まれるシェア部分データの排他的論理和によって、秘密部分データを復元することなく消失シェアのシェア部分データを再生成する処理をコンピュータに実行させることを特徴とするプログラムを提供する。
【発明の効果】
【００２１】
本発明では、消失したシェアを残りのシェアから直接かつ高速に再生成することができ、処理中に秘密情報が復元されることはない。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施形態によるシステムの構成を表わす図である。
【図２】コンピュータ１の構成の一例を表わす図である。
【図３】本発明の秘密情報の通信への適用例を表わす図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施形態を説明する。図１は、本発明の一実施形態によるシステムの構成図である。本システムは、データ処理装置１０、データ保管装置３１、３２、３３、これらを接続する回線２１、２２、２３を備える。図１は、秘密情報Ｓから３個のシェアを生成し、３つのデータ保管装置に保管する場合を示す。災害対策のためには、生成されたシェアを異なる場所に保管することが望ましい。従って、生成されたシェアがｎ個の場合、データ保管装置はｎ個設置することが望ましい。
【００２４】
データ処理装置１０は、分散手段１１、復元手段１２、再生成手段１３、再構成手段１４を備える。分散手段１１は、秘密情報Ｓおよびそれと同じ長さの乱数Ｒからｎ（ｎ≧３）個のシェアを生成する。復元手段１２は、分散手段１１によって生成されたｎ個のシェアのうち所定の個数のシェアから秘密情報Ｓを復元する。再生成手段１３は、分散手段１１によって生成された１個のシェアを他の２個のシェアから再生成する。再構成手段１４は、分散手段１１によって生成されたｎ個のシェアと、それらの生成に使用された乱数Ｒとは別の乱数Ｒ’とを用いて、新たなｎ個のシェアを生成する。
【００２５】
ここで、本明細書で用いる記号を説明する。ビット列ａとｂを結合したビット列がｃであるとき、これを、
【００２６】
【数３】
2014238546.tif 000005
【００２７】
と表わす。また、同じ長さのビット列ａおよびｂに対して、それぞれのビット毎に排他的論理和を施したビット列をｃとすると、これを、
【００２８】
【数４】
2014238546.tif 000006
【００２９】
と表わす。排他的論理和は、次の演算規則が成り立つ。
【００３０】
【数５】
2014238546.tif 000007
【００３１】
＜秘密情報の分散（シェアの生成）＞
次に、分散手段１１について詳細に説明する。分散手段１１は、秘密情報Ｓと乱数Ｒからｎ個（ｎ≧３）のシェアＤ１〜Ｄｎを生成する。
【００３２】
一実施形態として、分散手段１１は、コンピュータとプログラムを用いて実現することができる。図２は、コンピュータ１の構成の一例を表わす。コンピュータ１は、中央演算処理装置（ＣＰＵ）２、メモリ３、ディスク装置４、入出力インタフェース５を備える。メモリ３は一次記憶装置または主記憶装置と呼ばれる記憶装置、ディスク装置４は二次記憶装置または補助記憶装置と呼ばれる記憶装置に該当する。ディスク装置４には、プログラム６が記憶されている。入出力インタフェース５は、ディスプレイ、キーボード、通信回線等とのインタフェースの役割を果たす。プログラム６は、以下に述べる分散処理をＣＰＵ２に実行させるためのプログラムを含むものとする。
【００３３】
例えば、ユーザがコンピュータ１に分散処理の実行を指示すると、ディスク装置４から分散処理プログラムがメモリ３に読み込まれ、このプログラムに含まれる命令に従って、ＣＰＵ２は処理を実行する。
【００３４】
ここでは、秘密情報Ｓ、同じ長さの乱数Ｒがメモリ３に格納されているものとする。秘密情報Ｓは、コンピュータ１が入出力インタフェース５を介して接続された外部記憶装置からコンピュータ１のメモリ３に読み込んでもよいし、通信回線を介して接続された他のコンピュータからコンピュータ１のメモリ３に読み込んでもよい。乱数Ｒは、擬似乱数生成アルゴリズムを用いて生成されたものでもよいし、自然界の物理現象を利用した乱数発生器を用いて生成されたものでもよい。後述するように、事前にまとめて生成してディスク装置に書き込んでおき、そこから読み出してもよい。
【００３５】
ビット列である秘密情報Ｓをｎ−１等分し、順に、Ｓ１、Ｓ２、・・・、Ｓｎ−１と表わし、ビット列である乱数Ｒをｎ−１等分し、順に、Ｒ１、Ｒ２、・・・、Ｒｎ−１と表わすと、ｎ＝３のとき、
【００３６】
【数６】
2014238546.tif 000008
【００３７】
ｎ＝４のとき、
【００３８】
【数７】
2014238546.tif 000009
【００３９】
ｎ＝５のとき、
【００４０】
【数８】
2014238546.tif 000010
【００４１】
である。
【００４２】
ｎ＝３の場合、ＣＰＵ２は、次式の右辺の演算により、シェアＤ１〜Ｄ３を生成する（以下、「分散処理（基本型）」と呼ぶ）。
【００４３】
【数９】
2014238546.tif 000011
【００４４】
すなわち、ＣＰＵ２は、メモリ３からＳ１、Ｒ１、Ｒ２を読み出し、これらの排他的論理和演算の結果を、メモリ３内のシェアＤ１用の格納領域のうち前半部分に格納し、メモリ３からＳ２、Ｒ２を読み出し、これらの排他的論理和演算の結果を、メモリ３内のシェアＤ１用の格納領域のうち後半部分に格納する。
次に、ＣＰＵ２は、メモリ３からＳ１、Ｒ１を読み出し、これらの排他的論理和演算の結果を、メモリ３内のシェアＤ２用の格納領域のうち前半部分に格納し、メモリ３からＳ２、Ｒ１、Ｒ２を読み出し、これらの排他的論理和演算の結果を、メモリ３内のシェアＤ２用の格納領域のうち後半部分に格納する。
次に、ＣＰＵ２は、メモリ３からＲ１を読み出し、メモリ３内のシェアＤ３用の格納領域のうち前半部分に格納し、メモリ３からＲ２を読み出し、メモリ３内のシェアＤ３用の格納領域のうち後半部分に格納する。
このようにしてメモリ３内に格納されたシェアＤ１〜Ｄ３は、入出力インタフェース５から図１に示す回線２１〜２３を介してそれぞれデータ保管装置３１〜３３に送信され保管される。
【００４５】
上記の演算におけるＤ１，２とＤ２，２を次式のように入れ替えてもよい。この場合、ＣＰＵ２は、次式の右辺の演算により、シェアＤ１〜Ｄ３を生成する（以下、「分散処理（変形３型）」と呼ぶ）。
【００４６】
【数１０】
2014238546.tif 000012
【００４７】
分散処理（変形３型）をシェア数が３より大きい場合に拡張すると以下の通りである。
ｎ＝４の場合、ＣＰＵ２は、次式の右辺の演算により、シェアＤ１〜Ｄ４を生成する（以下、「分散処理（変形４型）」と呼ぶ）。
【００４８】
【数１１】
2014238546.tif 000013
【００４９】
ｎ＝５の場合、ＣＰＵ２は、次式の右辺の演算により、シェアＤ１〜Ｄ５を生成する（以下、「分散処理（変形５型）」と呼ぶ）。
【００５０】
【数１２】
2014238546.tif 000014
【００５１】
一般に、シェア数ｎの場合、シェアＤｉ（ｉ＝１〜ｎ，ｎ≧３）を区分したシェア部分データＤｉ，ｊ（ｉ＝１〜ｎ，ｊ＝１〜ｎ−１）は、ｉ＝１〜ｎ−１，ｊ＝１〜ｎ−１の各ｉ，ｊについてＤｉ，ｊが、第ｍ列（ｍ＝１〜ｎ−ｉ）の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｓｊとの排他的論理和で構成され、ｊ＝１〜ｎ−１の各ｊについてＤｎ，ｊがＲｊで構成されたものであると言える（以下、「分散処理（変形ｎ型）」と呼ぶ）。
【００５２】
なお、上記の分散処理を行う前に、秘密情報Ｓを任意の整数個に分け、それぞれについて分散処理を行ってもよい。この場合、乱数は、秘密情報Ｓを整数個に分けた単位で異なるものを使用してもよいし、同じものを繰り返し使用してもよい。秘密情報Ｓを整数個に分ける場合のそれぞれの長さは、同じでもよいし、異なってもよい。
【００５３】
分散処理（基本型）は、分散処理（変形ｎ型）と比較して次の利点がある。分散処理（変形ｎ型）によって生成されたシェアは、個々のシェアのみから、それを構成するシェア部分データ間の演算によって乱数成分が失われる場合がある。例えば、ｎ＝３（分散処理（変形３型））の場合、Ｄ１，１とＤ１，２の排他的論理和演算を行うと、上述した演算規則によれば次の通りである。
【００５４】
【数１３】
2014238546.tif 000015
【００５５】
このように乱数成分が失われると、例えば、シェア部分データＳ２の一部が既知である場合（例えば、Ｓ２が標準フォーマットのヘッダ情報あるいはパディングを含む場合）にはＳ１の一部が復元可能となる。一方、分散処理（基本型）によって生成されたシェアは、次式のように、シェアＤ１、Ｄ２それぞれを構成するシェア部分データ間で演算を行っても乱数成分が失われないため、元の秘密情報Ｓの一部も復元されることはない。
【００５６】
【数１４】
2014238546.tif 000016
【００５７】
以上のように、分散処理の過程で使われる演算は、排他的論理和演算のみであり、多項式を用いる分散方式に比べ、アルゴリズムが単純で実装が容易かつ高速である。また、ｎ個のシェアのうちのいずれについても、１個のシェアのみからでは秘密情報に関する情報が全く得られない情報量的安全性を有している。
【００５８】
シェア数３の場合で説明すると、シェアＤ１〜Ｄ３のうちシェアＤ３は、分散処理に使用した乱数Ｒそのものであり、秘密情報Ｓを含んでいないため、シェアＤ３だけでは、秘密情報Ｓに関する情報を全く得ることができない。シェアＤ１、Ｄ２については、秘密情報Ｓと、乱数Ｒ１、Ｒ２の一方または両方との排他的論理和の結果となっており、バーナム暗号による暗号文と等価である。したがって、乱数Ｒとして物理乱数を用いれば、シェアＤ１またはＤ２と秘密情報Ｓとは互いが確率的に独立となり、シェアＤ１またはＤ２だけでは、秘密情報Ｓに関する情報を全く得られない。
【００５９】
このように、シェアＤ１〜Ｄ３のうち１個のシェアだけでは秘密情報Ｓに関する情報は全く得られない。それぞれのシェアＤ１〜Ｄ３を結託のない独立した管理主体において保管すれば、１個のシェア（例えば、シェアＤ１）を管理している管理主体が、他のシェア（例えば、シェアＤ３）の一部でも知ることは無いため、秘密情報Ｓの長期的な機密性を保つことができる。つまり、データ保管装置３１〜３３の管理主体は、結託の無い物理的にも独立したデータセンタなどが望ましい。
【００６０】
＜秘密情報の復元＞
次に、図１の復元手段１２について詳細に説明する。復元手段１２は、ｎ＝３の場合、上述した分散処理によって生成された３個のシェアのうち任意の２個から秘密情報Ｓを復元する。ｎが奇数のとき（ｎ＋１）／２個、ｎが偶数のとき（ｎ／２）＋１個あれば復元できる。
【００６１】
一実施形態として、復元手段１２は、コンピュータとプログラムを用いて実現することができる。図２のプログラム６は、以下に述べる復元処理をＣＰＵ２に実行させるためのプログラムを含むものとする。例えば、ユーザがコンピュータ１に復元処理の実行を指示すると、ディスク装置４から復元処理プログラムがメモリ３に読み込まれ、このプログラムに含まれる命令に従って、ＣＰＵ２は処理を実行する。
【００６２】
分散処理（基本型）によるシェアの場合、ＣＰＵ２は、入出力インタフェース５を制御し、回線２１〜２３を介して、データ保管装置３１、３２、３３のうち２つからシェアを取得してメモリ３に格納する。
【００６３】
取得したシェアがＤ１、Ｄ２である場合、Ｄ１、Ｄ２のシェア部分データについて次式が成り立つので、ＣＰＵ２は次式の左辺の演算によりＳ１、Ｓ２を算出する。
【００６４】
【数１５】
2014238546.tif 000017
【００６５】
取得したシェアがＤ１、Ｄ３である場合、Ｄ１、Ｄ３のシェア部分データについて次式が成り立つので、ＣＰＵ２は次式の左辺の演算によりＳ１、Ｓ２を算出する。
【００６６】
【数１６】
2014238546.tif 000018
【００６７】
取得したシェアがＤ２、Ｄ３である場合、Ｄ２、Ｄ３のシェア部分データについて次式が成り立つので、ＣＰＵ２は次式の左辺の演算によりＳ１、Ｓ２を算出する。
【００６８】
【数１７】
2014238546.tif 000019
【００６９】
分散処理（変形ｎ型）のシェアの場合、まず、次のようにして乱数Ｒを取得する。
ｎ＝３の場合、次式が成り立つので、シェアＤ１、Ｄ２が取得できた場合、左辺の演算を行い、その結果を２等分することによりＲ１、Ｒ２を取得する。
【００７０】
【数１８】
2014238546.tif 000020
【００７１】
ｎ＝４の場合、次式が成り立つので、シェアＤ１とＤ２、または、Ｄ２とＤ３が取得できた場合、それぞれ左辺の演算を行い、その結果を３等分することによりＲ１〜Ｒ３を取得する。
【００７２】
【数１９】
2014238546.tif 000021
【００７３】
ｎ＝５の場合、次式が成り立つので、シェアＤ１とＤ２、または、Ｄ２とＤ３、または、Ｄ３とＤ４が取得できた場合、それぞれ左辺の演算を行い、その結果を４等分することによりＲ１〜Ｒ４を取得する。
【００７４】
【数２０】
2014238546.tif 000022
【００７５】
すなわち、Ｄ１〜Ｄｎ−１のうち番号が連続した２個のシェアが取得できれば（ケース１）、その２個の排他的論理和演算によりＲ１〜Ｒｎ−１を取得することができる。この乱数部分データＲ１〜Ｒｎ−１と、取得できたシェアのうちいずれかを用いれば、シェア部分データを生成した計算式において用いたのと同じ乱数部分データを用いた排他的論理和演算により、Ｓ１〜Ｓｎ−１を復元することができる。
また、Ｄ１〜Ｄｎ−１のうちいずれか１つとＤｎが取得できれば（ケース２）、Ｄｎから直接にＲ１〜Ｒｎ−１を取得することができるので、取得できたＤ１〜Ｄｎ−１のうちいずれか１つを用いてＳ１〜Ｓｎ−１を復元することができる。
ｎが奇数のとき（ｎ＋１）／２個、ｎが偶数のとき（ｎ／２）＋１個のシェアが取得できれば、必然的に上記のケース１または２のいずれかに該当する。
【００７６】
このように、復元処理の過程で使われる演算は、分散処理と同様に排他的論理和演算のみである。また、任意の１個のシェアが消失しても他の２個のシェアから秘密情報Ｓが復元されるため、復元に関してバックアップと同等な可用性を確保できる。
【００７７】
＜シェアの再生成＞
次に、図１の再生成手段１３について詳細に説明する。再生成手段１３は、上述した分散処理によって生成された１個のシェアを、他の２個のシェアから、秘密情報Ｓを復元することなく再生成する。再生成によって得られるシェアは、分散処理によって生成された元のシェアと全く同じであるので、再生成によって得られたシェアとその他のシェアとの組み合わせにより秘密情報を復元することが可能である。機器の障害や災害などで１個のシェアが消失しても、残りの２個から当該シェアを再生成することで、長期にわたって可用性を確保することができる。
２個のシェアから秘密情報を一旦復元し、改めて分散処理を行えば、任意のシェアを生成することは可能であるが、このようにすると秘密情報が一時的に復元される。以下の再生成処理においては、１個のシェアを他の２個のシェアから直接かつ高速に生成することができ、秘密情報が処理中に復元されない。
【００７８】
一実施形態として、再生成手段１３は、コンピュータとプログラムを用いて実現することができる。図２のプログラム６は、シェアの再生成処理をＣＰＵ２に実行させるためのプログラムを含むものとする。例えば、ユーザがコンピュータ１に再生成処理の実行を指示すると、ディスク装置４から再生成処理プログラムがメモリ３に読み込まれ、このプログラムに含まれる命令に従って、ＣＰＵ２は次の処理を実行する。
【００７９】
分散処理（基本型）によるシェアの場合、ＣＰＵ２は、入出力インタフェース５を制御し、回線２１〜２３を介して、データ保管装置３１、３２、３３のうち２つからシェアを取得してメモリ３に格納する。
【００８０】
データ保管装置３３のシェアＤ３が消失した場合、ＣＰＵ２は、データ保管装置３１、３２からそれぞれシェアＤ１、Ｄ２を取得する。次式が成り立つので、ＣＰＵ２は左辺の演算を行い、その結果を結合することによりＤ３を再生成する。
【００８１】
【数２１】
2014238546.tif 000023
【００８２】
データ保管装置３２のシェアＤ２が消失した場合、ＣＰＵ２は、データ保管装置３１、３３からそれぞれシェアＤ１、Ｄ３を取得する。次式が成り立つので、ＣＰＵ２は左辺の演算を行い、その結果を結合することによりＤ２を再生成する。
【００８３】
【数２２】
2014238546.tif 000024
【００８４】
データ保管装置３１のシェアＤ１が消失した場合、ＣＰＵ２は、データ保管装置３２、３３からそれぞれシェアＤ２、Ｄ３を取得する。次式が成り立つので、ＣＰＵ２は左辺の演算を行い、その結果を結合することによりＤ１を再生成する。
【００８５】
【数２３】
2014238546.tif 000025
【００８６】
分散処理（変形３型）のシェアの場合は次の通りである。
シェアＤ３が消失した場合、Ｄ１、Ｄ２を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ３を再生成する。
【００８７】
【数２４】
2014238546.tif 000026
【００８８】
シェアＤ２が消失した場合、Ｄ１、Ｄ３を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ２を再生成する。
【００８９】
【数２５】
2014238546.tif 000027
【００９０】
シェアＤ１が消失した場合、Ｄ２、Ｄ３を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ１を再生成する。
【００９１】
【数２６】
2014238546.tif 000028
【００９２】
分散処理（変形４型）のシェアの場合は次の通りである。
シェアＤ１が消失した場合、Ｄ２、Ｄ４を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ１を再生成する。
【００９３】
【数２７】
2014238546.tif 000029
【００９４】
このように、右辺のＤ１，１、Ｄ１，２、Ｄ１，３を得るために、順に、乱数部分データＲ３、Ｒ１、Ｒ２が使用される。ｊ＝１〜３の各ｊについてＤ１，ｊを生成するために使用される乱数部分データの番号３、１、２は「第３列の成分が１で他の成分が０である１行３列の行列（０，０，１）の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号」と表わすことができる。Ｄ１，ｊをこの乱数部分データとＤ２，ｊとの排他的論理和によって生成する。
【００９５】
シェアＤ２が消失した場合、Ｄ３、Ｄ４を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ２を再生成する。
【００９６】
【数２８】
2014238546.tif 000030
【００９７】
このように、右辺のＤ２，１、Ｄ２，２、Ｄ２，３を得るために、順に、乱数部分データＲ２、Ｒ３、Ｒ１が使用される。ｊ＝１〜３の各ｊについてＤ２，ｊを生成するために使用される乱数部分データの番号２、３、１は「第２列の成分が１で他の成分が０である１行３列の行列（０，１，０）の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号」と表わすことができる。Ｄ２，ｊをこの乱数部分データと、Ｄ３，ｊとの排他的論理和によって生成する。
【００９８】
シェアＤ２が消失した場合のもう１つの方法として、Ｄ１、Ｄ４を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ２を再生成する。
【００９９】
【数２９】
2014238546.tif 000031
【０１００】
このように、右辺のＤ２，１、Ｄ２，２、Ｄ２，３を得るために、順に、乱数部分データＲ３、Ｒ１、Ｒ２が使用される。ｊ＝１〜３の各ｊについてＤ２，ｊを生成するために使用される乱数部分データの番号３、１、２は「第３列の成分が１で他の成分が０である１行３列の行列（０，０，１）の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号」と表わすことができる。Ｄ２，ｊをこの乱数部分データと、Ｄ１，ｊとの排他的論理和によって生成する。
【０１０１】
シェアＤ３が消失した場合、Ｄ２、Ｄ４を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ３を再生成する。
【０１０２】
【数３０】
2014238546.tif 000032
【０１０３】
このように、右辺のＤ３，１、Ｄ３，２、Ｄ３，３を得るために、順に、乱数部分データＲ２、Ｒ３、Ｒ１が使用される。ｊ＝１〜３の各ｊについてＤ３，ｊを生成するために使用される乱数部分データの番号２、３、１は「第２列の成分が１で他の成分が０である１行３列の行列（０，１，０）の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号」と表わすことができる。Ｄ３，ｊをこの乱数部分データと、Ｄ２，ｊとの排他的論理和によって生成する。
【０１０４】
シェアＤ４が消失した場合、Ｄ１、Ｄ２を取得する。次式が成り立つので、左辺の演算を行い、その結果を結合することによりＤ４を再生成する。
【数３１】
2014238546.tif 000033
【０１０５】
このように、シェアＤ１、Ｄ２それぞれの１番目のシェア部分データＤ１，１とＤ２，１、２番目のシェア部分データＤ１，２とＤ２，２、３番目のシェア部分データＤ１，３とＤ２，３を使用して、順に、Ｄ４，３、Ｄ４，１、Ｄ４，２、すなわち、乱数部分データＲ３、Ｒ１、Ｒ２が生成される。この乱数部分データの番号３、１、２は「第３列の成分が１で他の成分が０である１行３列の行列（０，０，１）の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号」と表わすことができる。
【０１０６】
シェア数が５以上の場合も同様に考えることができ、分散処理（変形ｎ型）のシェアの場合、シェアＤｐ（１≦ｐ≦ｎ）の再生成は、ｐ＝１のときＤｐはＤｐ＋１とＤｎから再生成でき、１＜ｐ＜ｎ−１のときＤｐはＤｐ＋１とＤｎ、または、Ｄｐ−１とＤｎから再生成でき、ｐ＝ｎ−１のときＤｐはＤｐ−１とＤｎから再生成でき、ｐ＝ｎのときＤｐはＤ１とＤ２から再生成できる。すなわち、
ｐ＝１のとき、ｊ＝１〜ｎ−１の各ｊについてＤ１，ｊを、第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄ２，ｊとの排他的論理和によって再生成し、
１＜ｐ＜ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｐ，ｊを、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ＋１，ｊとの排他的論理和によって再生成するか、または、第ｎ−ｐ列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｐ−１，ｊとの排他的論理和によって再生成し、
ｐ＝ｎ−１のとき、ｊ＝１〜ｎ−１の各ｊについてＤｎ−１，ｊを、第２列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応する乱数部分データと、Ｄｎ−２，ｊとの排他的論理和によって再生成し、
ｐ＝ｎのとき、ｊ＝１〜ｎ−１の各ｊについて第ｎ−１列の成分が１で他の成分が０である１行ｎ−１列の行列の成分を右方向にｊ−１回巡回させたとき成分が１である列の番号に対応するＤｎのシェア部分データを、Ｄ１，ｊとＤ２，ｊとの排他的論理和によって再生成する。
【０１０７】
上記のいずれの処理においても、秘密情報Ｓを復元する必要がなく、処理の過程で計算機内のＣＰＵやメモリなどからも秘密情報Ｓが漏洩する恐れがない。また、シェア数３でそのうち１個を失った状態では可用性が確保されていないため、再生成に要する時間を極力短縮する必要がある。各シェアを再生成する操作は、独立した２つのステップで構成されており、並列処理が可能な環境において、１回の排他的論理和演算の時間のみで完了することが期待される。
【０１０８】
＜シェアの再構成＞
次に、図１の再構成手段１４について詳細に説明する。再構成手段１４は、分散処理によって生成されたｎ個のシェアＤ１〜Ｄｎと、それらを生成する際に使用した乱数Ｒとは別の同じ長さの乱数Ｒ’とを用いて、新たなｎ個のシェアＤ１’〜Ｄｎ ’を生成する。新たなシェアは、元のシェアの算出に用いられたＲをＲ’で置換して算出されたものに等しい。
【０１０９】
一実施形態として、再構成手段１４は、コンピュータとプログラムを用いて実現することができる。図２のプログラム６は、以下に述べる再構成処理をＣＰＵ２に実行させるためのプログラムを含むものとする。例えば、ユーザがコンピュータ１に再構成処理の実行を指示すると、ディスク装置４から再構成処理プログラムがメモリ３に読み込まれ、このプログラムに含まれる命令に従って、ＣＰＵ２は処理を実行する。
【０１１０】
分散処理（基本型）の場合、ＣＰＵ２は、入出力インタフェース５を制御し、回線２１〜２３を介して、データ保管装置３１、３２、３３からそれぞれシェアＤ１、Ｄ２、Ｄ３を取得してメモリ３に格納する。メモリ３には、シェアＤ１〜Ｄ３を生成する際に使用した乱数Ｒではない別の同じ長さの乱数Ｒ’が格納されているものとする。乱数Ｒ’は、擬似乱数生成アルゴリズムを用いて生成されたものでもよいし、自然界の物理現象を利用した乱数発生器を用いて生成されたものでもよい。
【０１１１】
再構成に用いる乱数Ｒ’を
【０１１２】
【数３２】
2014238546.tif 000034
【０１１３】
とし、再構成によって得られる新たなシェアを
【０１１４】
【数３３】
2014238546.tif 000035
【０１１５】
とする。以下、
【０１１６】
【数３４】
2014238546.tif 000036
【０１１７】
とする。例えば、Ｄ２，１はＳ１とＲ１の排他的論理和として生成されたので、Ｄ２，１とＲ１の排他的論理和演算を行えばＲ１が打ち消されてＳ１が得られ、次にこれとＲ’１との排他的論理和演算を行えばＤ２，１’が得られる。このように計算すると処理中にＳ１が復元されてしまうが、Ｄ２，１とＲ１＊との排他的論理和演算を行えば、処理中にＳ１が復元されることはない。そこで、ＣＰＵ２は、新たなシェアのそれぞれを次式の右辺の演算によって生成する。
【０１１８】
【数３５】
2014238546.tif 000037
【０１１９】
この再構成処理によって生成される新たなシェアが、秘密情報Ｓと乱数Ｒ’を用いて上述した分散処理（基本型）によって生成されるものと同じであることは、上記の各式がそれぞれ次のように変形できることから確認できる。
【０１２０】
【数３６】
2014238546.tif 000038
【０１２１】
従って、新たなシェアについても、上述した復元処理および再生成処理を行うことができる。
【０１２２】
確認のため、再構成前のシェアのうち１個と再構成後のシェアのうち１個とで秘密情報の復元を試みる。例えば、シェアＤ１とシェアＤ３’を用いると、上述した分散処理（基本型）によるシェアＤ１とＤ３から秘密情報を復元する演算式のＤ３をＤ３’で置換して演算を行うと次式の通りである。
【０１２３】
【数３７】
2014238546.tif 000039
【０１２４】
これらの演算結果には、元の乱数成分と再構成の際に用いた乱数成分とが含まれるため、秘密情報Ｓを得ることはできない。他の組み合わせについても同様である。このことから、再構成前のシェアのうち１個が漏洩した可能性がある場合でも、再構成を行い、再構成前の残りの２個のシェアを全て消去すれば、第三者が復元のために必要な残りのシェアを入手して秘密情報を復元する可能性を排除し、機密性を回復することができる。
【０１２５】
分散処理（変形ｎ型）によるシェアの再構成処理も同様である。
【０１２６】
このように、再生成処理と同様、再構成処理の過程で秘密情報は復元されず、また、分散処理とほぼ同じ処理時間で新しいシェアを再構成することができる。
【０１２７】
＜秘密情報の完全性確保＞
上述した復元処理では、シェアの保管中に生じた機器の故障や改ざんなどにより、シェアに誤りが生じていたとしても、それを検出することができない。これに対して、次に示すように、ハッシュ値を併用することによって完全性を確保することができる。
【０１２８】
ｘを保管する場合、以下の手順を行う。ここで、ハッシュ関数をＨとする。
（１）ｘのハッシュ値をｈ＝Ｈ（ｘ）とする。
（２）分散する秘密情報Ｓを
【０１２９】
【数３８】
2014238546.tif 000040
【０１３０】
とする。
（３）上述した分散処理により分散を行う。
【０１３１】
ｘを復元する場合、以下の手順を行う。
（１）上述した復元処理により秘密情報を復元し、これをＳ’とおく。
（２）
【０１３２】
【数３９】
2014238546.tif 000041
【０１３３】
とみなし, Ｓ’からｘ’とｈ’を取り出す。
（３）Ｈ（ｘ’）とｈ’を比較する。Ｈ（ｘ’）とｈ’が一致すればｘ＝ｘ’であり、ｘ’が復元の結果として得られる情報の本体である。
【０１３４】
復元処理の（３）において、ハッシュ値が一致しなければ，復元処理に使用した２個のシェアのうちいずれか一方または両方に誤りが発生していることを示している。
シェア数３の場合、他の２通りの組み合わせによる復元を行い、どちらかの組み合わせで正しく復元されれば、そのときに使用しなかったシェアに誤りがあることがわかる。その際には，上述した再生成処理により、正しいシェアを回復することができる。どちらの組み合わせでも正しく復元されなければ、２個以上のシェアに誤りが発生していることになり、本方式では対処できない。
【０１３５】
上記のハッシュ値を用いた手順以外に、異なる２つのシェアの組み合わせにより、それぞれの組合せで復元した結果を突合することでも完全性を確認可能である。
【０１３６】
＜保管容量の削減＞
一般に、重要な情報を長期保管する場合、そのバックアップをとっておくのが通例であるため、可用性のみを確保する目的のために、合計で元の情報に対して２倍の容量を保管することになる。一方、上述した分散処理を行うと、機密性と可用性および完全性を同時に満たすが、シェア数３の場合、秘密情報と同じ長さの３個のシェアが生成されるので、秘密情報に対して３倍の容量を保管する必要がある。これは、バックアップにより可用性のみを確保した場合の１．５倍にあたる。ここでは、本発明におけるシェアの総容量を削減する方式について述べる。
【０１３７】
＜擬似乱数の利用＞
シェア数３の場合、シェアＤ３は、分散処理に使用した乱数Ｒそのものである。そこで、物理乱数の代わりに計算量的安全性に基づき適切な擬似乱数を利用し、シェアＤ３として擬似乱数のシードのみを保存する方法が考えられる。シードは、それから生成される擬似乱数系列に比べて十分に小さい容量であるため、この方法ではシェアの総容量を秘密情報Ｓの２倍程度に抑えることができる。
【０１３８】
＜擬似乱数を使用した長期的な機密性の確保＞
本発明において擬似乱数を使用し、長期にわたって機密性を確保するには、擬似乱数生成アルゴリズムの危殆化に対する考慮が必要である。本発明では、上述した再構成処理を以下のように利用することにより、危殆化への対応が可能である。
【０１３９】
まず、擬似乱数生成アルゴリズムＦｒ１とそのシードｓｅｅｄｒ１を使用して擬似乱数系列ｒ１を生成する。次に、秘密情報Ｓとｒ１を用いて、上述した分散処理に従ってシェアＤ１およびＤ２を生成する。最後に、ｒ１ではなくｓｅｅｄｒ１をシェアＤ３とする。
ある期間経過後Ｆｒ１が危殆化する前に、その時点で十分に安全なＦｒ２とｓｅｅｄｒ２を新たに用意し、これらを用いて擬似乱数系列ｒ２を生成する。また、シェアＤ１とＤ２から、
【０１４０】
【数４０】
2014238546.tif 000042
【０１４１】
により
【０１４２】
【数４１】
2014238546.tif 000043
【０１４３】
を得る。シェアの再構成を行うために与える新たな疑似乱数を
【０１４４】
【数４２】
2014238546.tif 000044
【０１４５】
とし、上述した再構成処理により新たなシェアＤ１’およびシェアＤ２’を求める。その結果、
【０１４６】
【数４３】
2014238546.tif 000045
【０１４７】
であり、以降、シェアＤ１’およびシェアＤ２’を保管する。一方、新たなシェアＤ３’としては、ｓｅｅｄｒ１を破棄してｓｅｅｄｒ２のみを保管する。
このように、擬似乱数生成アルゴリズムＦｒ１が危殆化する前に、Ｆｒ（ｉ＋１）を用いてシェアの再構成処理を行うことで、シェアの総容量を抑えつつ、長期的な安全性を確保することができる。
【０１４８】
なお、この方法では、シェアＤ３’はＦｒ２のシードであるため、上述した再生成処理を適用しても、シェアＤ３’だけはシェアＤ１’とシェアＤ２’から再生成することができない。仮に、シェアＤ３’が消失した場合、擬似乱数生成アルゴリズムが危殆化した場合と同様にシェアＤ１’およびシェアＤ２’の再構成処理を行い、その時に使用した擬似乱数生成アルゴリズムのシードを新たなシェアＤ３’とすればよい。
【０１４９】
＜ディザスタリカバリシステムへの適用＞
上述した復元処理により、３個のシェアのうち任意の２個のシェアで秘密情報を復元でき、かつ、上述した再生成処理により、任意の２個のシェアから秘密情報を復元することなく、他の１個のシェアを迅速に再生成することができる。この特長を利用し、ディザスタリカバリシステムを容易に構築可能である。
【０１５０】
図１に示すデータ保管装置３１〜３３は、それぞれ距離が離れた地点Ｘ、Ｙ、Ｚにあるデータセンタに設置され、シェアを１個ずつ格納する。分散処理や復元処理などは自社に設置されたデータ処理装置１０で行うこととし、各データセンタとの間は個別の回線２１〜２３で接続する。仮に、１つのデータセンタが災害に見舞われても、残りの２つのデータセンタに保管されたシェアから被災したデータセンタのシェアの再生成が可能である。
このようなディザスタリカバリシステムにおいて実装を効率化するための方式を述べる。
【０１５１】
＜乱数の事前生成＞
上述した分散処理では、秘密情報と同じサイズの乱数を生成する必要がある。良質な乱数を生成する装置は、ディスク装置のアクセス速度に比べて低速であり、多量の乱数を生成する場合、その生成時間が上述した分散処理の処理速度を抑える要因となる可能性がある。
上述した分散処理においてシェアＤ３は、分散時に使用する乱数そのものであり、秘密情報Ｓには依存していない。このため、事前に乱数を生成してシェアＤ３を作成しておくことが可能である。
【０１５２】
例えば、地点Ｚにあるディスク装置の全セクタに予め生成した乱数を書き込んでおく。また、秘密情報を保管する際、秘密情報をディスクのセクタサイズに分割し、その単位で分散処理を行うこととする。このとき、必要なセクタ番号の乱数を地点Ｚから読み出し、シェアＤ１およびシェアＤ２を生成し、使用した乱数が書かれていたセクタ番号に対応する地点Ｘおよび地点Ｙのディスク装置のセクタに書き込む。シェアＤ３は、分散処理の前後で変化しないため、分散処理後にシェアＤ３を書き込む必要はない。復元処理の際には、任意の２地点の対応するセクタを読み出し、セクタごとに復元処理を行い、その結果を結合することで秘密情報を得ることができる。
【０１５３】
一般に、ディスク装置に保管する情報とそれを記録するためのセクタ番号との対応は、ファイルシステムが管理する。このことを利用すれば、セクタ単位での分散処理および復元処理をディスクアクセスのためのデバイスドライバの機能の一部として実装することで、上述の方式を実現することができる。
【０１５４】
このように、乱数を事前に生成しておくことで、上述した分散処理の処理速度が乱数の生成速度により抑えられる事態を避けることが可能となる。
【０１５５】
＜乱数からなるシェアを平時に使用しない分散方式＞
図１に示したシェア数３のディザスタリカバリシステムを構築する場合、データ処理装置１０を自社に設置し、データ保管装置３１〜３３をそれぞれ異なる地点Ｘ、Ｙ、Ｚのデータセンタに設置すると、自社と各データセンタの間には、想定されるディスクへのアクセス頻度などに応じた帯域の回線を用意する必要がある。しかし、コスト面で既存の回線と共用せざるを得ず、十分な帯域を確保できないなどの場合も考えられる。ここでは、上述した乱数の事前生成がなされていることを前提として、シェアＤ１やシェアＤ２に誤りが発生しない限り、シェアＤ３に対してアクセスする必要がない実装方式を示す。
【０１５６】
事前準備として、上述した乱数の事前生成を行った後、何らかの意味のない情報（例えば、擬似乱数など）を秘密情報として、地点Ｘおよび地点Ｙのディスク装置全体にシェアが書き込まれるように分散処理を行っておく。すなわち、地点Ｘ、Ｙ、Ｚのディスク装置の対応するセクタには、何らかの意味のない情報を秘密情報として分散処理によって生成された対応するシェアが予め書き込まれ、このうち地点Ｚのディスク装置には事前生成された乱数が書き込まれた状態となっている。この後、次の手順により秘密情報Ｓを保管する。上記で乱数の事前生成に関して述べたのと同様に、分散処理によって生成されたシェアを保管するときには、地点Ｘ、Ｙ、Ｚのディスク装置の対応するセクタを使用するものとする。
【０１５７】
まず、分散処理によって生成されるシェアＤ１、Ｄ２を書き込むために使用されることになる地点Ｘ、Ｙのディスク装置のセクタから書き込まれている情報を読み出す。この情報は、そのセクタが直前に使用された際（そのセクタが初めて使用される場合は、事前準備として書き込みを行った際）に書き込まれたものである。これらのシェアから、上述した再生成処理を適用して乱数
【０１５８】
【数４４】
2014238546.tif 000046
【０１５９】
を得る。この乱数は、事前生成により地点Ｚのディスク装置の対応するセクタに書かれている乱数に等しい。この乱数を用い、上述した分散処理によってシェアＤ１、Ｄ２を生成し、それぞれ地点Ｘ、Ｙのディスク装置に書き込む。シェアＤ１とＤ２のみを用いた復元処理は、上述したとおりである。
【０１６０】
この方式によれば，通常はシェアＤ３にアクセスする必要はない。シェアＤ１またはシェアＤ２に誤りが生じたり、災害などで消失したりした場合のみ、シェアＤ３を用いて復元処理や再生成処理を行えばよい。
【０１６１】
上述したシェアＤ１とＤ２から乱数Ｒを導出する処理も、排他的論理和のみで構成されており、シェアへのアクセスに要する時間に比べ、十分に短い時間で完了することが期待できる。自社と地点Ｘおよび地点Ｙを結ぶ回線が十分広帯域で、かつ、シェアＤ１とシェアＤ２が同時にアクセスできるならば、この分散処理に要する時間は、ほぼ、シェアの読み出しに要する時間と書き込みに要する時間との和となる。上述した乱数を事前生成する方法でも、分散処理に要する時間は、ほぼ、シェアＤ３の読み出しに要する時間とシェアＤ１およびシェアＤ２の書き込みに要する時間との和となる。このことから、この方式を用いても分散処理に要する時間は、乱数を事前生成する方法と大差ないことがわかる。復元処理に要する時間は、どちらの方法においても、ほぼシェアの読み出しに要する時間となる。
【０１６２】
このように、この方式を用いれば、通常はシェアＤ３にアクセスする必要がなく、自社と地点Ｚとの間における回線の帯域が十分に確保できない場合に有効である。
【０１６３】
＜秘密情報の通信への適用＞
これまで、秘密情報の長期的な安全性を確保する保管への適用を述べた。ここでは、図３に示す本発明の秘密情報の通信への適用例に関して述べる。例えば、基地局４０と移動端末４１の無線によるリアルタイムな音声通信を想定する。
【０１６４】
まず、シェア数３の場合において、シェアＤ３が秘密情報Ｓから全く独立に構成されている点に着目する。つまり、シェアＤ３が乱数のみにより構成されており、秘密情報が発生するタイミングとは、完全に非同期なタイミングで生成可能である。よって、シェアＤ３を基地局４０と移動端末４１との間で事前に共有しておくことが可能である。具体的には、基地局４０においてシェアＤ３を生成し、電気通信に依存しない方法により、例えば、郵便などによりSDXCカードなどメモリーカードの格納媒体を送付して、移動端末４１との間でシェアＤ３を共有しておく。図３の点線はシェアＤ３が基地局４０から移動端末４１へオフラインで渡されることを示す。シェアＤ１はオンラインで送受信される。
【０１６５】
ここで注意を要するのは、シェアＤ３を確実に１回のみの使用に留める制御である。つまり、移動端末４１において音声を秘密情報Ｓとして、上述した分散処理を用い、例えば、シェアＤ１を生成したタイミングにおいて、これに用いたシェアＤ３を使い捨てとする。移動端末４１においては、勿論、シェアＤ２も生成可能であるが、この例では当該シェアを敢えて生成しない。
【０１６６】
移動端末４１からシェアＤ１のみを基地局４０へ送ることにより、通信路上において、これ以外のシェアが出現することは無い。よって、音声は情報量的安全性を確保した状態で通信される。
【０１６７】
なお、移動端末４１の紛失などが発生し、事前共有したシェアＤ３の危殆化が懸念される場合、単に、基地局４０にて保有している同一のシェアＤ３を破棄するのみである。
移動端末４１において生成しなかったシェアＤ２は、シェアＤ３を保有している基地局４０において、シェアＤ１が到着したタイミングで、上述した再生成処理を適用してリアルタイムに生成可能である。この際、基地局４０においても、秘密情報である音声を復元する必要がない。
【０１６８】
また、通信相手が接続されている基地局４０において、通信相手のシェアＤ３を用い、上述した再構成処理を行うことにより通信相手のシェアＤ１を生成することができる。この時、基地局４０においても通信相手のシェアＤ３を使い捨てとする必要がある。これにより、移動端末４１において発生された秘密情報は、情報量的安全性を常時維持した状態で相手と通信される。
【０１６９】
一方、基地局４０と移動端末４１の間においては、秘密情報の可用性が担保されていない。しかし、一般にはパケット通信が利用されており、必要に応じてパケットの再送を行うことにより、実質的な問題は生じないと考えられる。なお、パケット再送時においても、シェアＤ３の使い捨てに十分留意する必要がある。
【０１７０】
本発明の通信への適用には、シェアＤ３の安全な事前共有が必須であるため、この事前共有の頻度を考察する。例えば、２５６ＧＢのSDXCカードを利用し、音楽CDと同等な音声品質の確保を想定する。音声は、サンプリング周波数を４４．１ｋＨｚとし、１回のサンプリングで１６ビットの量子化を行う。また、移動端末４１においては送信と受信が同量とする。この条件下では、少なく見積もっても約４００時間の連続音声通信が可能となる。つまり、シェアＤ３の事前共有間隔は、最大４００時間あけることが可能となる。この時間は、移動端末４１の個人的な利用において、特段の制限となるものでは無いと考えられる。
【産業上の利用可能性】
【０１７１】
本発明は、一例として、データのディザスタリカバリシステムに利用することができる。
【符号の説明】
【０１７２】
１  コンピュータ
２  中央演算処理装置
３  メモリ
４  ディスク装置
５  入出力インタフェース
６  プログラム
１０  データ処理装置
１１  分散手段
１２  復元手段
１３  再生成手段
１４  再構成手段
２１、２２、２３  回線
３１、３２、３３  データ保管装置
４０  基地局
４１  移動端末
【図１】
2014238546.tif 000049
【図２】
2014238546.tif 000050
【図３】
2014238546.tif 000051