(57)【特許請求の範囲】
【請求項１】
ユーザの秘密情報データを記憶するデータベースを評価するデータベース評価装置であって、
前記データベースのうちの一部分であって、前記ユーザのうちの一部のユーザの秘密情報データを記憶する第１データベースと、前記データベースのうちの前記第１データベース以外の部分であって、前記一部のユーザ以外の前記ユーザの秘密情報データを記憶する第２データベースとにおいて、前記第１データベースが漏洩したと仮定した場合に、前記第１データベースのデータ分布である第１分布に基づいて、任意の分布推測アルゴリズムを用いて前記第２データベースのデータ分布である第２分布を推測する推測手段と、
前記推測手段によって推測された推測分布において選択されたデータと、前記第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、
前記評価指標に基づいて、前記データベースが安全であるか否かを判定する判定手段と、
を備えるデータベース評価装置。
【請求項２】
前記判定手段は、前記評価指標が、前記推測分布を一様分布であるとしたときに、攻撃が成功する確率以下である場合に、前記データベースを安全であると判定する、請求項１に記載のデータベース評価装置。
【請求項３】
前記推測分布と前記第２分布との第１距離を算出する第１距離算出手段と、
一様分布と前記第２分布との第２距離を算出する第２距離算出手段と、をさらに備え、
前記判定手段は、前記評価指標に基づく判定に替えて、前記推測分布の２次のレニーエントロピーが、前記第２分布の２次のレニーエントロピー以上であり、かつ、前記第１距離が、前記第２距離に所定の係数を乗じた値以上である場合に、前記データベースを安全であると判定する、請求項１に記載のデータベース評価装置。
【請求項４】
ユーザの秘密情報データを記憶するデータベースを分割するデータベース分割装置であって、
前記データベースのうちの一部分であって、前記ユーザのうちの一部のユーザの秘密情報データを記憶する第１データベースと、前記データベースのうちの前記第１データベース以外の部分であって、前記一部のユーザ以外の前記ユーザの秘密情報データを記憶する第２データベースとにおいて、前記第１データベースのデータ分布である第１分布の２次のレニーエントロピーと、前記第２データベースのデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、
前記第１データベース又は前記第２データベースの一方に含まれるデータ分布に基づいて任意の分布推測アルゴリズムを用いて他方のデータベースに含まれるデータ分布を推測した推測分布から選択されたデータと、前記他方のデータベースから選択されたデータとが一致して前記他方のデータベースへの攻撃が成功する確率が所定以下となるように、前記データベースを前記第１データベースと前記第２データベースとに分割する分割手段を備える、
データベース分割装置。
【請求項５】
前記分割手段は、前記第１分布と前記第２分布との距離が、前記第１分布又は前記第２分布と一様分布との距離に基づく一定の値以上であるように、前記データベースを前記第１データベースと前記第２データベースとに分割する、請求項４に記載のデータベース分割装置。
【請求項６】
前記分割手段は、前記第１分布の２次のレニーエントロピー及び前記第２分布の２次のレニーエントロピーと、前記データベースのデータ分布の２次のレニーエントロピーとの差をそれぞれ所定の範囲内にするという、さらに追加した条件の下で分割する、請求項４又は５に記載のデータベース分割装置。
【請求項７】
前記分割手段は、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数と、前記データベースのデータ分布をヒストグラムに表した場合の階級の個数とをそれぞれ同一にするという、さらに追加した条件の下で分割する、請求項４から６のいずれか一項に記載のデータベース分割装置。
【請求項８】
前記分割手段は、グリーディ法により、前記第１データベースと前記第２データベースとの距離の変化量の大きい階級を優先させてデータを移動させる、請求項４から７のいずれか一項に記載のデータベース分割装置。
【請求項９】
請求項１に記載のデータベース評価装置が実行する方法であって、
前記推測手段が、前記データベースのうちの一部分であって、前記ユーザのうちの一部のユーザの秘密情報データを記憶する第１データベースと、前記データベースのうちの前記第１データベース以外の部分であって、前記一部のユーザ以外の前記ユーザの秘密情報データを記憶する第２データベースとにおいて、前記第１データベースが漏洩したと仮定した場合に、前記第１データベースのデータ分布である第１分布に基づいて、任意の分布推測アルゴリズムを用いて前記第２データベースのデータ分布である第２分布を推測する推測ステップと、
前記判定手段が、前記推測ステップによって推測された推測分布において選択されたデータと、前記第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、前記評価指標に基づいて、前記データベースが安全であるか否かを判定する判定ステップと、
を備える方法。
【請求項１０】
請求項４に記載されたデータベース分割装置が実行する方法であって、
前記分割手段が、前記データベースのうちの一部分であって、前記ユーザのうちの一部のユーザの秘密情報データを記憶する第１データベースと、前記データベースのうちの前記第１データベース以外の部分であって、前記一部のユーザ以外の前記ユーザの秘密情報データを記憶する第２データベースとにおいて、前記第１データベースのデータ分布である第１分布の２次のレニーエントロピーと、前記第２データベースのデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、
前記第１データベース又は前記第２データベースの一方に含まれるデータ分布に基づいて任意の分布推測アルゴリズムを用いて他方のデータベースに含まれるデータ分布を推測した推測分布から選択されたデータと、前記他方のデータベースから選択されたデータとが一致して前記他方のデータベースへの攻撃が成功する確率が所定以下となるように、前記データベースを前記第１データベースと前記第２データベースとに分割する分割ステップを備える、
方法。
【請求項１１】
前記データベース評価装置に、請求項９に記載の方法の各ステップを実行させるためのプログラム。
【請求項１２】
前記データベース分割装置に、請求項１０に記載の方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース評価装置、方法及びプログラム、並びにデータベース分割装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、パスワードや暗証番号などの秘密情報が漏洩する事例が多発しており、漏洩情報を用いたシステムの不正利用に関する被害が多数報告されている。それらの事例の多くは、人的ミスや機器の故障、あるいは故意による不正などの潜在的な脆弱性に起因するものであり、根本的な原因を取り除くことは容易ではない。このため、今後も情報漏洩のリスクをゼロにすることはきわめて難しいと考えられる。
【０００３】
特に、現在多くのサービスがクラウド上で展開されていることから、情報漏洩のケースとして以下が想定される。
クラウド上のシステムでは複数のサーバを仮想的に統合して利用しているため、一部のストレージに故障やバグが生じることや、異なる管理者のデータセンターのサーバを統合している場合には一部の管理者が不正を働くなど、部分的にインシデントが発生する可能性がある。それらのインシデントにより脆弱性が顕在化した場合、システムの一部のユーザの秘密情報が大量に漏洩する可能性がある。
また、情報漏洩が発覚した直後、対象ユーザは早期に情報を変更すると考えられるが、それ以外のユーザは、複数のサービスで同一の情報を使用していることなどに起因する変更の煩わしさから、変更に消極的であることが考えられる。
また、秘密情報として用いられるパスワードや生体情報などの認証情報、あるいは物理的なソースなどの多くは、各値が一様に生起しない非一様な情報である。それらの非一様性を普遍的にモデル化することは容易ではないが、一部のユーザの秘密情報を知ることができれば、クラウド上のシステムの他のユーザの秘密情報の偏りを推測できる可能性がある。このような秘密情報の非一様性を利用した攻撃は、総当たり的に攻撃するよりも効率的に攻撃を遂行できる。
【０００４】
また、セキュリティ分野における機能安全の概念に基づく従来研究としては、サイドチャネル攻撃などにより秘密情報について何らかの情報が漏洩することを想定した漏洩耐性暗号に関する試みがあげられる。それらの議論では、漏洩耐性の暗号プリミティブが情報漏洩時においても安全であることを立証するために、漏洩関数ｆにより定式化された秘密情報ｘに関する漏洩情報ｆ（ｘ）を用いて情報漏洩時の安全性をモデル化している。例えば、部分漏洩に対するモデルを提示する非特許文献１や、部分漏洩について非特許文献１とは別のモデルを提示する非特許文献２が知られている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ａｄｉ  Ａｋａｖｉａ、Ｓｈａｆｉ  Ｇｏｌｄｗａｓｓｅｒ、Ｖ．  Ｖ．：Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｈａｒｄｃｏｒｅ  Ｂｉｔｓ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｇａｉｎｓｔ  Ｍｅｍｏｒｙ  Ａｔｔａｃｋｓ、ｔｈｅ  ６ｔｈ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ（ＴＣＣ  ０９）、ＬＮＣＳ、Ｖｏｌ．５４４４、ｐｐ．４７４−４９５（２００９）．
【非特許文献２】Ｄｕｃ、Ａ．、Ｄｚｉｅｍｂｏｗｓｋｉ、Ｓ．  ａｎｄ  Ｆａｕｓｔ、Ｓ．：Ｕｎｉｆｙｉｎｇ  ｌｅａｋａｇｅ  ｍｏｄｅｌｓ：ｆｒｏｍ  ｐｒｏｂｉｎｇ  ａｔｔａｃｋｓ  ｔｏ  ｎｏｉｓｙ  ｌｅａｋａｇｅ、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ  ２０１４、ＬＮＣＳ、Ｖｏｌ．８４４１、ｐｐ．４２３−４４０（２０１４）．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述のモデルではある特定のユーザｘの部分的な情報のみが漏洩すること、例えば、ｆ（ｘ）はｘの一部のビットであるなど、を想定しており、システムから大量の秘密情報が漏洩した状況下での情報の安全性を保障するものではない。
【０００７】
そこで、システムから一部のユーザの秘密情報が漏洩した際に、秘密情報の非一様性を考慮した攻撃モデルに対しての耐性を評価する装置が望まれている。また、残りのユーザの秘密情報への影響を最小限に抑えるために、評価する装置により安全性が高いと判定されるようなデータベースの分割をする装置が望まれている。
【０００８】
本発明は、データベースのうち一部分が漏洩した場合に残りの部分の安全性を評価できるデータベース評価装置、方法及びプログラムと、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベースを分割できるデータベース分割装置、方法及びプログラムとを提供することを目的とする。
【課題を解決するための手段】
【０００９】
具体的には、以下のような解決手段を提供する。
（１）  データベースを評価するデータベース評価装置であって、前記データベースのうちの一部分である第１データベースと、前記データベースのうちの前記第１データベース以外の部分である第２データベースとにおいて、前記第１データベースが漏洩したと仮定した場合に、前記第１データベースのデータ分布である第１分布に基づいて、前記第２データベースのデータ分布である第２分布を推測する推測手段と、前記推測手段によって推測された推測分布において選択されたデータと、前記第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、前記評価指標に基づいて、前記データベースが安全であるか否かを判定する判定手段と、を備えるデータベース評価装置。
【００１０】
（１）のデータベース評価装置は、推測分布において選択されたデータと、第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を、データベースの安全性を評価するための評価指標とする。
【００１１】
したがって、（１）に係るデータベース評価装置は、平均攻撃成功確率を評価指標に用いるので、データベースのうち一部分が漏洩した場合に残りの部分の安全性を評価できる。
【００１２】
（２）  前記判定手段は、前記評価指標が、前記推測分布を一様分布であるとしたときに、攻撃が成功する確率以下である場合に、前記データベースを安全であると判定する、（１）に記載のデータベース評価装置。
【００１３】
（２）に係るデータベース評価装置は、データベースのうち一部分が漏洩した場合に残りの部分の安全性を、確実に評価できる。
【００１４】
（３）  前記推測分布と前記第２分布との第１距離を算出する第１距離算出手段と、
一様分布と前記第２分布との第２距離を算出する第２距離算出手段と、をさらに備え、
前記判定手段は、前記推測分布の２次のレニーエントロピーが、前記第２分布の２次のレニーエントロピー以上であり、かつ、前記第１距離が、前記第２距離に基づく一定の値以上である場合に、前記データベースを安全であると判定する、（１）に記載のデータベース評価装置。
【００１５】
（３）に係るデータベース評価装置は、データベースのうち一部分が漏洩した場合に残りの部分の安全性を、さらに確実に評価できる。
【００１６】
（４）  データベースを分割するデータベース分割装置であって、前記データベースのうちの一部分である第１データベースと、前記データベースのうちの前記第１データベース以外の部分である第２データベースとにおいて、前記第１データベースのデータ分布である第１分布の２次のレニーエントロピーと、前記第２データベースのデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、前記第１データベース又は前記第２データベースの一方に含まれるデータの分布に基づいて他方のデータベースに含まれるデータの分布を推測した推測分布から選択されたデータと、前記他方のデータベースから選択されたデータとが一致して前記他方のデータベースへの攻撃が成功する確率が所定以下となるように、前記データベースを前記第１データベースと前記第２データベースとに分割する分割手段を備える、データベース分割装置。
【００１７】
（４）に係るデータベース分割装置は、第１データベース又は第２データベースの一方に含まれるデータの分布に基づいて他方のデータベースに含まれるデータの分布を推測した推測分布から選択されたデータと、他方のデータベースから選択されたデータとが一致して他方のデータベースへの攻撃が成功する確率が所定以下となるように、データベースを第１データベースと第２データベースとに分割する。
【００１８】
したがって、（４）に係るデータベース分割装置は、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベースを分割することができる。
【００１９】
（５）  前記分割手段は、前記第１分布と前記第２分布との距離が、前記第１分布又は前記第２分布と一様分布との距離に基づく一定の値以上であるように、前記データベースを前記第１データベースと前記第２データベースとに分割する、（４）に記載のデータベース分割装置。
【００２０】
したがって、（５）に係るデータベース分割装置は、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が、確実に安全であるようにデータベースを分割することができる。
【００２１】
（６）  前記分割手段は、前記第１分布の２次のレニーエントロピー及び前記第２分布の２次のレニーエントロピーと、前記データベースのデータ分布の２次のレニーエントロピーとの差をそれぞれ所定の範囲内にするという、さらに追加した条件の下で分割する、（４）又は（５）に記載のデータベース分割装置。
【００２２】
（６）に係るデータベース分割装置は、データベースを分割する場合に分割した一方がすべて漏洩しても、分割した他方が安全であるようにデータベースを分割することができる。
【００２３】
（７）  前記分割手段は、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数と、前記データベースのデータ分布をヒストグラムに表した場合の階級の個数とをそれぞれ同一にするという、さらに追加した条件の下で分割する、（４）から（６）のいずれか一に記載のデータベース分割装置。
【００２４】
（７）に係るデータベース分割装置は、分割したデータベースがいずれも漏洩していない場合の安全性を高くするようにデータベースを分割することができる。
【００２５】
（８）  前記分割手段は、グリーディ法により、前記第１データベースと前記第２データベースとの距離の変化量の大きい階級を優先させてデータを移動させる、（４）から（７）のいずれか一に記載のデータベース分割装置。
【００２６】
（８）に係るデータベース分割装置は、第１データベースと第２データベースとのデータの移動において、データベース間の距離を大きくするように効率よく移動させることができる。
【００２７】
（９）  （１）に記載のデータベース評価装置が実行する方法であって、前記推測手段が、前記データベースのうちの一部分である第１データベースと、前記データベースのうちの前記第１データベース以外の部分である第２データベースとにおいて、前記第１データベースが漏洩したと仮定した場合に、前記第１データベースのデータ分布である第１分布に基づいて、前記第２データベースのデータ分布である第２分布を推測する推測ステップと、前記判定手段が、前記推測ステップによって推測された推測分布において選択されたデータと、前記第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、前記評価指標に基づいて、前記データベースが安全であるか否かを判定する判定ステップと、を備える方法。
【００２８】
（９）に係る方法は、平均攻撃成功確率を評価指標に用いるので、データベースのうち一部分が漏洩した場合に残りの部分の安全性を評価できる。
【００２９】
（１０）  （４）に記載されたデータベース分割装置が実行する方法であって、前記分割手段が、前記データベースのうちの一部分である第１データベースと、前記データベースのうちの前記第１データベース以外の部分である第２データベースとにおいて、前記第１データベースのデータ分布である第１分布の２次のレニーエントロピーと、前記第２データベースのデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、前記第１分布及び前記第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、前記第１データベース又は前記第２データベースの一方に含まれるデータ分布に基づいて他方のデータベースに含まれるデータ分布を推測した推測分布から選択されたデータと、前記他方のデータベースから選択されたデータとが一致して前記他方のデータベースへの攻撃が成功する確率が所定以下となるように、前記データベースを前記第１データベースと前記第２データベースとに分割する分割ステップを備える、方法。
【００３０】
（１０）に係る方法は、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベースを分割することができる。
【００３１】
（１１）  コンピュータに、（９）に記載の方法の各ステップを実行させるためのプログラム。
【００３２】
（１１）に係るプログラムは、コンピュータに、データベースのうち一部分が漏洩した場合に残りの部分の安全性を評価させることができる。
【００３３】
（１２）  コンピュータに、（１０）に記載の方法の各ステップを実行させるためのプログラム。
【００３４】
（１２）に係るプログラムは、コンピュータに、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベースを分割させることができる。
【発明の効果】
【００３５】
本発明によれば、データベース評価装置は、データベースのうち一部分が漏洩した場合に残りの部分の安全性を評価できる。データベース分割装置は、データベースを分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベースを分割できる。
【図面の簡単な説明】
【００３６】
【図１】本発明の一実施形態に係るデータベース評価装置及びデータベース分割装置の構成を示すブロック図である。
【図２】本発明の一実施形態に係るデータベース評価装置の評価指標に基づく評価処理の例を示すフローチャートである。
【図３】本発明の一実施形態に係るデータベース評価装置の距離に基づく評価処理の例を示すフローチャートである。
【図４】本発明の一実施形態に係るデータベース分割装置の分割アルゴリズムの例を示すフローチャートである。
【図５】図４に続く、フローチャートである。
【図６】本発明の一実施形態に係るデータベース分割装置２０により分割された第１ＤＢ及び第２ＤＢのヒストグラムの例を示す図である。
【発明を実施するための形態】
【００３７】
以下、本発明の実施形態について、図を参照しながら説明する。
【００３８】
説明に利用する２次のレニーエントロピー及び確率変数の定義は以下の通りである。
離散集合χ上の確率変数Ｘの確率関数をｐ（ｘ）とすると、Ｘの２次のレニーエントロピーＨ２（Ｘ）は、式（１）で定義される。
【００３９】
【数１】
0006632796.tif 000002
【００４０】
離散集合χ上の確率変数Ｘ、Ｙの確率関数をそれぞれｐ（ｘ）、ｑ（ｘ）とすると、ＸとＹとの距離Ｄ（Ｘ，Ｙ）は、式（２）で定義される。
【００４１】
【数２】
0006632796.tif 000003
【００４２】
ｑ（ｘ）が一様分布のとき、ＸとＹとの距離Ｅ（Ｘ）は式（３）で表せる。
【００４３】
【数３】
0006632796.tif 000004
【００４４】
［データベース評価装置１０］
まず、データベース評価装置１０について説明する。
ユーザの秘密情報（例えば、ユーザに対応付けられる暗証番号やパスワード、生体情報など）を記憶するデータベース３０のうちの一部分が漏洩した場合、攻撃者は漏洩した情報を利用することにより、残りのユーザの秘密情報の分布を推測できる可能性がある。このような推測された分布である推測分布を用いた攻撃モデルの１つであるＤＧＡ（Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｇｕｅｓｓｉｎｇ  Ａｔｔａｃｋ）に対する、データベース評価装置１０の安全性の評価について説明する。
【００４５】
ＤＧＡの攻撃手順を攻撃者と挑戦者によるゲーム形式で示す。
ここで、秘密情報が漏洩したユーザの集合をＵ′、Ｕ′の各ユーザの秘密情報データの集合をＷ′とする。また、攻撃対象のユーザの集合をＵ、Ｕの各ユーザの秘密情報データの集合をＷとする。Ｗの各データはその取りうる値の集合χ上の確率関数ｐ（ｘ）にしたがって生起したものとする。ただし、ｕ≠ｕ′、ｕ∈Ｕ、ｕ′∈Ｕ′とする。
（１）攻撃者は任意の分布推測アルゴリズムΚを用いて取得したＷ′から確率関数ｐ（ｘ）を推測する。このとき、推測された分布をｑ（ｘ）とする。
（２）挑戦者はユーザｕ∈Ｕをランダムに選択し、対応する秘密情報ｗ∈Ｗを抽出する。
（３）攻撃者はｑ（ｘ）にしたがって秘密情報ｘ∈ｑχを選択する。
（４）ｘとｗとが一致すれば、攻撃者の勝ちとする。
【００４６】
データベース評価装置１０は、攻撃が成功する確率である平均攻撃成功確率を、安全性を評価するための評価指標とし、安全性を評価する。
【００４７】
図１は、本発明の一実施形態に係るデータベース評価装置１０及びデータベース分割装置２０の構成を示すブロック図である。データベース評価装置１０は、推測手段１１と、判定手段１２と、第１距離算出手段１３と、第２距離算出手段１４とを備える。手段ごとに詳述する。
【００４８】
推測手段１１は、漏洩した情報の分布に基づいて、漏洩していない残りの情報の分布を、攻撃者に代わって推測する。すなわち、推測手段１１は、データベース３０（例えば、ユーザの秘密情報など）のうちの一部分である第１データベース（第１ＤＢ３１と言う。）と、データベース３０のうちの第１ＤＢ３１以外の部分である第２データベース（第２ＤＢ３２と言う。）とにおいて、第１ＤＢ３１が漏洩したと仮定した場合に、第１ＤＢ３１のデータ分布である第１分布に基づいて、第２ＤＢ３２のデータ分布である第２分布を推測する。
【００４９】
［データベース評価装置１０：評価指標に基づく評価の実施例］
判定手段１２は、推測手段１１によって推測された推測分布（攻撃者に代わって推測した分布）ｑ（ｘ）において選択されたデータと、第２分布（攻撃対象ユーザの秘密情報の分布）ｐ（ｘ）において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、評価指標に基づいて、データベース３０が安全であるか否かを判定する。具体的には、判定手段１２は、第２分布ｐ（ｘ）と、推測分布ｑ（ｘ）とにより、ＤＧＡの平均攻撃成功確率ＰＤＧＡを、式（４）によって算出し、データベース３０が安全であるか否かを判定する。
【００５０】
【数４】
0006632796.tif 000005
【００５１】
仮に、システムから何の情報も漏洩していなければ、攻撃者はｐ（ｘ）に関して何の情報も持たないため、離散集合χ上の一様分布にしたがってＤＧＡを実行する他ない。｜χ｜＝２ｎとすれば、そのときの攻撃成功確率は２−ｎで表せる。したがって、一部の秘密情報が漏洩した場合であっても、ＰＤＧＡ≦２−ｎであれば、情報が漏洩していないときと同様に安全であるといえる。本明細書ではこのときの安全性をＤＧＡ安全と定義する。
【００５２】
さらに、判定手段１２は、評価指標が、推測分布を一様分布であるとしたときに、攻撃が成功する確率（２−ｎ）以下である場合に、データベース３０を安全であると判定する。
【００５３】
図２は、本発明の一実施形態に係るデータベース評価装置１０の評価指標に基づく評価処理の例を示すフローチャートである。データベース評価装置１０は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成される。以下の処理は、制御部（例えば、ＣＰＵ）が、所定のソフトウェアに従い実行する処理である。
【００５４】
ステップＳ１０１において、ＣＰＵ（推測手段１１）は、データベース３０の一部が漏洩したと仮定して、残りの部分のデータ分布を推測する。より具体的には、ＣＰＵは、データベース３０のうちの一部分である第１ＤＢ３１と、データベース３０のうちの第１ＤＢ３１以外の部分である第２ＤＢ３２とにおいて、第１ＤＢ３１が漏洩したと仮定した場合に、第１ＤＢ３１のデータ分布である第１分布に基づいて、第２ＤＢ３２のデータ分布である第２分布を推測する。
【００５５】
ステップＳ１０２において、ＣＰＵ（判定手段１２）は、推測分布に基づく平均攻撃成功確率を評価指標として、残りの部分の安全性を評価する。より具体的には、ＣＰＵは、評価指標として、ＤＧＡの平均攻撃成功確率ＰＤＧＡを式（４）によって算出し、算出した評価指標と、ステップＳ１０１において推測された推測分布ｑ（ｘ）が一様分布であるときに攻撃が成功する確率（２−ｎ）とを比較し、評価指標が確率（２−ｎ）以下である場合に、データベース３０を安全であると判定する。その後、ＣＰＵは、処理を終了する。
【００５６】
［データベース評価装置１０：距離に基づく評価の実施例］
図１に戻り、データベース評価装置１０による、距離に基づく判定について説明する。
データベース評価装置１０は、第１距離算出手段１３と、第２距離算出手段１４とをさらに備える。
第１距離算出手段１３は、推測分布と第２分布との第１距離（Ｄ）を算出する。
第２距離算出手段１４は、一様分布と第２分布との第２距離（Ｅ）を算出する。
判定手段１２は、推測分布と第２分布との距離に基づいて、データベース３０を安全であると判定する。
【００５７】
ここで、Ｘ、Ｙをそれぞれｐ（ｘ）、ｑ（ｘ）を確率関数として持つ離散集合χ上の確率変数とし、Ｈ２（Ｘ）＝ｒ、Ｈ２（Ｙ）＝ｓとすると、第１距離算出手段１３は、式（２）により、第１距離（Ｄ）を算出する。第２距離算出手段１４は、式（３）により、第２距離（Ｅ）を算出する。
ｒ≦ｓのとき、不等式（５）が成立する。
【００５８】
【数５】
0006632796.tif 000006
【００５９】
なお、式（５）が成立することを、次に示す。
【００６０】
【数６】
0006632796.tif 000007
【００６１】
すなわち、式（５）が成立する。
【００６２】
式（３）及び式（５）より、ＰＤＧＡ≦２−ｎのとき、次の不等式が成立する。
【００６３】
【数７】
0006632796.tif 000008
【００６４】
したがって、ｒ≦ｓ、かつ、Ｄ（Ｘ，Ｙ）２≧２Ｅ（Ｘ）２を達成できれば、ＰＤＧＡ≦２−ｎの定義と同様にそのシステムはＤＧＡ安全であるといえる。
すなわち、判定手段１２は、第１距離が、第２距離に基づく一定の値以上である場合に、データベース３０を安全であると判定する。
【００６５】
図３は、本発明の一実施形態に係るデータベース評価装置１０の距離に基づく評価処理の例を示すフローチャートである。
【００６６】
ステップＳ１１１において、ＣＰＵ（推測手段１１）は、データベース３０の一部が漏洩したと仮定して、残りの部分のデータ分布を推測する。より具体的には、ＣＰＵは、データベース３０のうちの一部分である第１ＤＢ３１と、データベース３０のうちの第１ＤＢ３１以外の部分である第２ＤＢ３２とにおいて、第１ＤＢ３１が漏洩したと仮定した場合に、第１ＤＢ３１のデータ分布である第１分布に基づいて、第２ＤＢ３２のデータ分布である第２分布を推測する。
【００６７】
ステップＳ１１２において、ＣＰＵ（第１距離算出手段１３）は、推測分布と残りの部分との距離を算出する。より具体的には、ＣＰＵは、式（２）により、第１距離（Ｄ）を算出する。
【００６８】
ステップＳ１１３において、ＣＰＵ（第２距離算出手段１４）は、一様分布と残りの部分との距離を算出する。より具体的には、ＣＰＵは、式（３）により、第２距離（Ｅ）を算出する。
【００６９】
ステップＳ１１４において、ＣＰＵ（判定手段１２）は、算出した距離に基づいて、残りの部分の安全性を評価する。より具体的には、ＣＰＵは、第１距離が、第２距離に基づく一定の値以上である場合（ｒ≦ｓ、かつ、Ｄ（Ｘ，Ｙ）２≧２Ｅ（Ｘ）２を満たす場合）に、データベース３０を安全であると判定する。その後、ＣＰＵは、処理を終了する。
【００７０】
［データベース分割装置２０］
次に、図１に戻り、データベース分割装置２０について説明する。
データベース分割装置２０は、分割手段２１を備え、分割した一方の第１ＤＢ３１が漏洩し、漏洩した第１ＤＢ３１に基づいて攻撃者が他方の第２ＤＢ３２にＤＧＡ攻撃をしても、データベース３０がＤＧＡ安全であるようにデータベース３０を分割する。
データベース分割装置２０は、第１ＤＢ３１又は第２ＤＢ３２のどちらが漏洩した場合においても、ＤＧＡに対して耐性のある秘密情報の分割保管をする。
【００７１】
秘密情報（例えば、ユーザに対応付けられた暗証番号やパスワードなど）は、クラウド化された２つのデータベース（例えば、第１ＤＢ３１、第２ＤＢ３２）に分割され、異なるストレージに保管されている。
【００７２】
分割手段２１は、以下の３つの条件の下でデータベースの分割をする。
条件１：攻撃者は，分布推測アルゴリズムΚとしてヒストグラムを用いる。
条件２：第１ＤＢ３１及び第２ＤＢ３２のどちらのデータベースが漏洩してもＤＧＡへの耐性は同様である。
条件３：第１ＤＢ３１及び第２ＤＢ３２のいずれのデータベースも漏洩していない場合、第１ＤＢ３１及び第２ＤＢ３２は同様に十分に安全である。
【００７３】
分割手段２１は、データベース３０のうちの一部分である第１ＤＢ３１と、データベース３０のうちの第１ＤＢ３１以外の部分である第２ＤＢ３２とにおいて、第１ＤＢ３１のデータ分布である第１分布の２次のレニーエントロピーと、第２ＤＢ３２のデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、第１分布及び第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、第１ＤＢ３１又は第２ＤＢ３２の一方に含まれるデータの分布に基づいて他方のデータベースに含まれるデータの分布を推測した推測分布から選択されたデータと、他方のデータベースから選択されたデータとが一致して他方のデータベースへの攻撃が成功する確率が所定以下となるように、データベース３０を第１ＤＢ３１と第２ＤＢ３２とに分割する。
【００７４】
第１分布の２次のレニーエントロピーと、第２分布の２次のレニーエントロピーとの差を所定の範囲内にするとは、例えば、ｒ＝Ｈ２（Ｘ１）＝Ｈ２（Ｘ２）の状態にすることをいう。これにより、ＤＧＡに対する耐性が向上する。また、第１ＤＢ３１又は第２ＤＢ３２のどちらが漏洩した場合においてもその程度は同様となる。
【００７５】
ここで、ｐ１（ｘ）を第１ＤＢ３１に含まれるデータのヒストグラム、ｐ２（ｘ）を第２ＤＢ３２に含まれるデータのヒストグラムとする。
条件１より、攻撃者の推測分布ｑ（ｘ）は、第２ＤＢ３２が漏洩した場合はｐ２（ｘ）、第１ＤＢ３１が漏洩した場合はｐ１（ｘ）で表せる。
Ｘ１、Ｘ２をそれぞれｐ１（ｘ）、ｐ２（ｘ）にしたがう確率変数とする。ｒ＝Ｈ２（Ｘ１）＝Ｈ２（Ｘ２）とすると、式（５）の等号が成立するため、第１ＤＢ３１又は第２ＤＢ３２のどちらが漏洩した場合においてもＤＧＡの攻撃成功確率ＰＤＧＡは式（１２）で表せる。
【００７６】
【数８】
0006632796.tif 000009
【００７７】
本実施形態では、条件１により攻撃者は分布推測アルゴリズムとしてヒストグラムを用いることを仮定しているが、実際にはより有効なアルゴリズムを使用する可能性もある。攻撃者が攻撃対象のデータベースの分布ｐ（ｘ）と同一の分布を推測できた場合、Ｄ（Ｘ１，Ｘ２）＝０となり、ＤＧＡの平均攻撃成功確率は２−ｒで表せる。したがって、ｒの値は十分に大きくする必要がある。ただし、Ｈ２（Ｘ１）＝Ｈ２（Ｘ２）を仮定しているため、第１ＤＢ３１及び第２ＤＢ３２にランダムにデータを振り分けたときにＨ２（Ｘ１），Ｈ２（Ｘ２）はそれぞれ最大となる。したがって、ｒは式（１３）を満たすように設定する。
ｒ＝Ｈ２（Ｘ１）＝Ｈ２（Ｘ２）＝Ｈ（Ｘ）      （１３）
ただし、Ｘは第１ＤＢ３１及び第２ＤＢ３２の総データの分布にしたがう確率変数とする。
【００７８】
分割手段２１は、第１分布の２次のレニーエントロピー及び第２分布の２次のレニーエントロピーと、データベース３０のデータ分布の２次のレニーエントロピーとの差をそれぞれ所定の範囲内にするという、追加した条件の下で分割する。
具体的には、分割手段２１は、攻撃者がｐ（ｘ）を完全に推測できた場合の安全性を高くするために、ｒが式（１３）を満たすという、追加した条件の下で分割する。
【００７９】
また、条件３を考慮して、攻撃者がｐ（ｘ）に関して何の情報も持たないときのＤＧＡへの耐性を高くするために、式（１４）を設定する．
｜χ１｜＝｜χ２｜＝｜χ｜      （１４）
ただし、χ１、χ２は第１ＤＢ３１及び第２ＤＢ３２のデータの取りうる値の集合とし、χは第１ＤＢ３１と第２ＤＢ３２とに含まれる総データの取りうる値の集合とする。
以上より、ＤＧＡへの耐性を向上させるためには、式（１３）、式（１４）の条件の下、式（１２）のＤ（Ｘ１，Ｘ２）を大きくすればよいことがわかる。
【００８０】
すなわち、分割手段２１は、第１分布と第２分布との距離が、第１分布又は第２分布と一様分布との距離に基づく一定の値以上（上述のＤ（Ｘ，Ｙ）２≧２Ｅ（Ｘ）２）であるように、データベース３０を第１ＤＢ３１と第２ＤＢ３２とに分割する。
【００８１】
分割手段２１は、第１分布及び第２分布をヒストグラムに表した場合の階級の個数と、データベース３０のデータ分布をヒストグラムに表した場合の階級の個数とをそれぞれ同一にするという、追加した条件の下で分割する。
具体的には、分割手段２１は、攻撃者がｐ（ｘ）に関して何の情報も持たないときのＤＧＡへの耐性を高くするために、式（１４）を満たすように分割する。
【００８２】
［分割アルゴリズム］
データの個数が増加するにつれて、分割の組み合わせ総数は指数的に増加するため、効率的に解く分割アルゴリズムについて説明する。
【００８３】
ここで、ｃ１（ｘ）及びｃ２（ｘ）をそれぞれ第１ＤＢ３１又は第２ＤＢ３２に含まれる値ｘ∈χを取るデータの個数とする。このとき、第１ＤＢ３１及び第２ＤＢ３２の総データの中で値ｘを取るものの個数はｃ（ｘ）＝ｃ１（ｘ）＋ｃ２（ｘ）で与えられる。
分割アルゴリズムは、式（１５）を目的関数とし、式（１６）〜（１８）を制約条件として、目的関数を最大にするｃ１（ｘ）及びｃ２（ｘ）を求める。
【００８４】
【数９】
0006632796.tif 000010
【００８５】
分割アルゴリズムは、初期設定からＳｔｅｐ４までの手順からなる。
【００８６】
初期設定：Ｎ個の秘密情報データを同一サイズの第１ＤＢ３１及び第２ＤＢ３２に分割する。ただし、すべてのｘ∈χにおいてｃ１（ｘ）＝ｃ２（ｘ）を満たすように分割する。次いで、Δ＝｛δ（ｘ）＝ｃ（ｘ）−２｝（ｘ∈χ）を作成する。
【００８７】
Ｓｔｅｐ１：最も大きいδ（ｘ）∈Δと対応するｘを選択し、［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを第２ＤＢ３２から第１ＤＢ３１に移動させる。
【００８８】
Ｓｔｅｐ２：［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを式（１６）を満たすように第１ＤＢ３１から第２ＤＢ３２に移動させる。ただし、この移動はグリーディ法により行う。
【００８９】
Ｓｔｅｐ２で用いるグリーディ法について説明する。値ｘを取るデータを第１ＤＢ３１から第２ＤＢ３２にｅ個移動させたときのｃ２（ｘ）２−ｃ１（ｘ）２の変化量は次式で表せる．
［（ｃ２（ｘ）＋ｅ）２−（ｃ１（ｘ）−ｅ）２］
−［ｃ２（ｘ）２−ｃ１（ｘ）２］              （１９）
＝２・［ｃ２（ｘ）＋ｃ１（ｘ）］・ｅ            （２０）
＝２・ｃ（ｘ）・ｅ                          （２１）
したがって、ｃ（ｘ）が大きいｘのデータを移動させた方が少ないデータの移動で式（２２）の値を大きく変化させられることが分かる。このため、Ｓｔｅｐ２のグリーディ法では、ｃ（ｘ）が最も大きいｘのデータから順に移動させる。
【００９０】
【数１０】
0006632796.tif 000011
【００９１】
Ｓｔｅｐ３：δ（ｘ）＝⊥（データ終了）としてΔを更新する。
【００９２】
ただし、Ｓｔｅｐ２において、条件を満たすデータの移動ができなかった場合には、Ｓｔｅｐ１及びＳｔｅｐ２を行う前の状態に戻し、δ（ｘ）＝δ（ｘ）−２としてΔを更新する。
【００９３】
Ｓｔｅｐ４：Ｓｔｅｐ１からＳｔｅｐ３までの動作をΔのすべてのδ（ｘ）が０以下もしくは⊥になるまで繰り返す。
【００９４】
ただし、本ステップは以下の条件にしたがって行う。
・Ｓｔｅｐ１において、ｃ２（ｘ）＞ｃ１（ｘ）が成立する場合、データは第１ＤＢ３１から第２ＤＢ３２に移動する。この場合、Ｓｔｅｐ２では、第２ＤＢ３２から第１ＤＢ３１に移動する。
・Ｓｔｅｐ１において、｜ｃ１（ｘ）−ｃ２（ｘ）｜≧δ（ｘ）が成立する場合、当該ｘに関するデータの移動は行わずに、δ（ｘ）＝⊥（データ終了）としてΔを更新し、次のｘのプロセスに移行する。
・Ｓｔｅｐ２では、δ（ｘ）≠⊥（データの終了）のｘのデータのみ移動する。
【００９５】
本アルゴリズムにおいてグリーディ法の計算量はＮ／２を超えることはない。また、Ｓｔｅｐ３の計算量はΔの更新回数に比例するため、最悪の場合でも高々Ｎ／２である。したがって、本分割アルゴリズムの最悪時の計算量はΟ（Ｎ２）となる。
【００９６】
次に、上述の分割アルゴリズムについて、フローチャートを用いて説明する。
図４及び図５は、本発明の一実施形態に係るデータベース分割装置２０の分割アルゴリズムの例を示すフローチャートである。データベース分割装置２０は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成される。以下の処理は、制御部（例えば、ＣＰＵ）が、所定のソフトウェアに従い実行する処理である。なお、本処理は、データベース評価装置１０によってデータベース３０の一部が安全でないと判定された場合に、起動されるとしてもよい。
【００９７】
ステップＳ２０１において、ＣＰＵ（分割手段２１）は、初期設定をする。より具体的には、ＣＰＵは、Ｎ個の秘密情報データを同一サイズの第１ＤＢ３１及び第２ＤＢ３２に分割し、Δ＝｛δ（ｘ）＝ｃ（ｘ）−２｝（ｘ∈χ）を作成する。ただし、ＣＰＵは、すべてのｘ∈χにおいてｃ１（ｘ）＝ｃ２（ｘ）を満たすように分割する。
【００９８】
ステップＳ２０２において、ＣＰＵ（分割手段２１）は、最も大きいδ（ｘ）∈Δと対応するｘを選択し、｜ｃ１（ｘ）−ｃ２（ｘ）｜≧δ（ｘ）が成立するか否かを判断する。この判断が、ＹＥＳの場合、ＣＰＵは、処理をステップＳ２０７に移し、この判断が、ＮＯの場合、ＣＰＵは、処理をステップＳ２０３に移す。
【００９９】
ステップＳ２０３において、ＣＰＵ（分割手段２１）は、ｃ２（ｘ）＞ｃ１（ｘ）が成立するか否かを判断する。この判断が、ＹＥＳの場合、ＣＰＵは、処理をステップＳ２１０に移し、この判断が、ＮＯの場合、ＣＰＵは、処理をステップＳ２０４に移す。
【０１００】
ステップＳ２０４において、ＣＰＵ（分割手段２１）は、データを第２ＤＢ３２から第１ＤＢ３１に移動させる。より具体的には、ＣＰＵは、［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを第２ＤＢ３２から第１ＤＢ３１に移動させる。
【０１０１】
ステップＳ２０５において、ＣＰＵ（分割手段２１）は、グリーディ法によりデータを第１ＤＢ３１から第２ＤＢ３２に移動させる。より具体的には、ＣＰＵは、［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを式（１６）を満たすように第１ＤＢ３１から第２ＤＢ３２に移動させる。ＣＰＵは、値ｘを取るデータを第１ＤＢ３１から第２ＤＢ３２に移動させたときのｃ２（ｘ）２−ｃ１（ｘ）２の変化量の大きいデータから順に移動させる（グリーディ法）。
【０１０２】
ステップＳ２０６において、ＣＰＵ（分割手段２１）は、式（１６）を満たすように移動できたか否かを判断する。この判断が、ＹＥＳの場合、ＣＰＵは、処理をステップＳ２０７に移し、この判断が、ＮＯの場合、ＣＰＵは、処理をステップＳ２０８に移す。
【０１０３】
ステップＳ２０７において、ＣＰＵ（分割手段２１）は、δ（ｘ）＝⊥（データ終了）としてΔを更新する。その後、ＣＰＵは、処理をステップＳ２０９に移す。
【０１０４】
ステップＳ２０８において、ＣＰＵ（分割手段２１）は、ステップＳ２０４及びステップＳ２０５におけるデータの移動を前の状態に戻し、δ（ｘ）＝δ（ｘ）−２としてΔを更新する。
【０１０５】
ステップＳ２０９において、ＣＰＵ（分割手段２１）は、Δのすべてのδ（ｘ）が０以下又は⊥（データの終了）か否かを判断する。この判断が、ＹＥＳの場合、ＣＰＵは、処理を終了し、この判断が、ＮＯの場合、ＣＰＵは、処理をステップＳ２０２に移す。
【０１０６】
ステップＳ２１０において、ＣＰＵ（分割手段２１）は、データを第１ＤＢ３１から第２ＤＢ３２に移動させる。より具体的には、ＣＰＵは、［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを第１ＤＢ３１から第２ＤＢ３２に移動させる。
【０１０７】
ステップＳ２１１において、ＣＰＵ（分割手段２１）は、グリーディ法によりデータを第２ＤＢ３２から第１ＤＢ３１に移動させる。より具体的には、ＣＰＵは、［δ（ｘ）−｜ｃ１（ｘ）−ｃ２（ｘ）｜］／２個のデータを式（１６）を満たすように第２ＤＢ３２から第１ＤＢ３１に移動させる。ＣＰＵは、値ｘを取るデータを第２ＤＢ３２から第１ＤＢ３１に移動させたときのｃ２（ｘ）２−ｃ１（ｘ）２の変化量の大きいデータから順に移動させる（グリーディ法）。
【０１０８】
ステップＳ２１２において、ＣＰＵ（分割手段２１）は、式（１６）を満たすように移動できたか否かを判断する。この判断が、ＹＥＳの場合、ＣＰＵは、処理をステップＳ２１３に移し、この判断が、ＮＯの場合、ＣＰＵは、処理をステップＳ２１４に移す。
【０１０９】
ステップＳ２１３において、ＣＰＵ（分割手段２１）は、δ（ｘ）＝⊥（データ終了）としてΔを更新する。その後、ＣＰＵは、処理をステップＳ２０９に移す。
【０１１０】
ステップＳ２１４において、ＣＰＵ（分割手段２１）は、ステップＳ２１０及びステップＳ２１１におけるデータの移動を前の状態に戻し、δ（ｘ）＝δ（ｘ）−２としてΔを更新する。その後、ＣＰＵは、処理をステップＳ２０９に移す。
【０１１１】
図６は、本発明の一実施形態に係るデータベース分割装置２０により分割された第１ＤＢ３１及び第２ＤＢ３２のヒストグラムの例を示す図である。分割される前のデータベース３０は、秘密情報が３２個の異なる値を取るものとし、１０００個のデータを記憶している。ただし、それらのデータは、標準正規分布にしたがって生起されている。データについて、［−３σ，３σ］の区間が均等に３２分割され、それぞれの区間に秘密情報の各値が割り当てられている。
【０１１２】
図６の例は、データベース３０が分割アルゴリズムによって分割され、分割された第１ＤＢ３１と、第２ＤＢ３２とのそれぞれのヒストグラムの例を示す。図６における横軸は、秘密情報の階級（取りうる値の参照番号）を示し、縦軸はその頻度を示す。図６の例では、ほぼすべての参照番号において、第１ＤＢ３１と第２ＤＢ３２との間でデータの出現頻度が大きく異なっている。したがって、図６の例は、データベース分割装置２０によって、第１ＤＢ３１又は第２ＤＢ３２のどちらのデータベースが漏洩した場合においても、ＤＧＡに対して耐性のある秘密情報の分割保管がされたことを示している。
【０１１３】
本実施形態によれば、データベース評価装置１０は、データベース３０のうちの一部分である第１ＤＢ３１と、データベース３０のうちの第１ＤＢ３１以外の部分である第２ＤＢ３２とにおいて、第１ＤＢ３１が漏洩したと仮定した場合に、第１ＤＢ３１のデータ分布である第１分布に基づいて、第２ＤＢ３２のデータ分布である第２分布を推測し、推測された推測分布において選択されたデータと、第２分布において選択されたデータとが一致して攻撃が成功する確率である平均攻撃成功確率を評価指標とし、評価指標に基づいて、データベース３０が安全であるか否かを判定する。データベース評価装置１０は、評価指標が、推測分布を一様分布であるとしたときに攻撃が成功する確率以下である場合に、データベース３０を安全であると判定する。データベース評価装置１０は、推測分布と第２分布との第１距離を算出し、一様分布と第２分布との第２距離を算出し、推測分布の２次のレニーエントロピーが、第２分布の２次のレニーエントロピー以上であり、かつ、第１距離が、第２距離に基づく一定の値以上である場合に、データベース３０を安全であると判定する。
したがって、データベース評価装置１０は、データベース３０のうち一部分が漏洩した場合に残りの部分の安全性を評価できる。
【０１１４】
本実施形態によれば、データベース分割装置２０は、データベース評価装置１０によって安全であると評価されるように、データベース３０を分割する。データベース分割装置２０は、データベース３０のうちの第１ＤＢ３１と、第２ＤＢ３２とにおいて、第１ＤＢ３１のデータ分布である第１分布の２次のレニーエントロピーと、第２ＤＢ３２のデータ分布である第２分布の２次のレニーエントロピーとの差を所定の範囲内にすると共に、第１分布及び第２分布をヒストグラムに表した場合の階級の個数を互いに同一にするという条件の下で、第１分布と第２分布との距離が、第１分布又は第２分布と一様分布との距離に基づく一定の値以上であるように、データベース３０を第１ＤＢ３１と第２ＤＢ３２とに分割する。
さらに、データベース分割装置２０は、第１分布の２次のレニーエントロピー及び第２分布の２次のレニーエントロピーと、データベース３０のデータ分布の２次のレニーエントロピーとの差をそれぞれ所定の範囲内にするという、追加した条件の下で分割する。
さらに、データベース分割装置２０は、第１分布及び第２分布をヒストグラムに表した場合の階級の個数と、データベース３０のデータ分布をヒストグラムに表した場合の階級の個数とをそれぞれ同一にするという、追加した条件の下で分割する。
さらに、データベース分割装置２０は、グリーディ法により、第１ＤＢ３１と第２ＤＢ３２との距離の変化量の大きい階級を優先させてデータを移動させる。
したがって、データベース分割装置２０は、データベース３０を分割する場合に分割した一方が漏洩しても、分割した他方が安全であるようにデータベース３０を分割できる。
このように、本発明は、情報漏洩が起きた際の安全性を評価することができる。また、本発明は、システムから一部のユーザの秘密情報が漏洩した際に、残りのユーザの秘密情報への影響を最小限に抑えることができる。本発明は、秘密情報を大量に扱うシステムに特化したクラウドプラットフォームを提供することができる。
【０１１５】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【０１１６】
データベース評価装置１０又はデータベース分割装置２０による一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータなどにインストールされる。また、当該プログラムは、コンピュータ読み取り可能な記録媒体（例えば、ＣＤ−ＲＯＭのようなリムーバブルメディアなど）に記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【０１１７】
１０    データベース評価装置
１１    推測手段
１２    判定手段
１３    第１距離算出手段
１４    第２距離算出手段
２０    データベース分割装置
２１    分割手段
３０    データベース
３１    第１ＤＢ
３２    第２ＤＢ
【図１】
0006632796.tif 000012
【図２】
0006632796.tif 000013
【図３】
0006632796.tif 000014
【図４】
0006632796.tif 000015
【図５】
0006632796.tif 000016
【図６】
0006632796.tif 000017