(57)【要約】例示的な実施形態によれば、本発明のメッセージを確実に保管する方法は、第１メッセージを第複数シェアに分割するステップと、この第１複数シェアを、少なくとも第２メッセージの第２複数シェアとともに保管ホスト上に保管するステップと、を有し、この保管は混ぜ合わせにした状態で行う。
2009535660.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを安全に保管する方法において、
第１メッセージを第１複数シェアに分割するステップと、
この第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に、互いに混ぜ合わせ状態にして保管ホスト上に保管するステップと、
を有する、メッセージ保管方法。
【請求項２】
請求項1に記載のメッセージ保管方法において、
前記保管ホストはリモートホストとし、メッセージ保管方法は、さらに、
第１複数シェアをリモートホストに送信するステップ
を有するものとする、メッセージ保管方法。
【請求項３】
請求項１または２に記載の保管方法において、メッセージ保管方法はさらに、
前記保管ホスト上に前記第１複数シェアを保管する前に、前記第１複数シェアの各シェアに、第３複数ラベルからの対応するラベルでラベル付けするステップ、
を有するものとする、メッセージ保管方法。
【請求項４】
請求項３に記載のメッセージ保管方法において、ラベル付けは、前記第１複数シェアを送信する前に行うものとする、メッセージ保管方法。
【請求項５】
請求項３または４に記載のメッセージ保管方法において、メッセージ保管方法は、さらに、
前記保管ホストから第３複数シェアを受信するものとする、メッセージ保管方法。
【請求項６】
請求項１〜５のうち一つに記載のメッセージ保管方法において、メッセージ保管方法は、さらに、
前記第１複数シェアのうち少なくとも一つと、前記第２複数シェアのシェアとを比較するステップと、
前記第１複数シェアのうち少なくとも一つが、前記第２複数シェアのうち一つのシェアと同一の場合、
前記保管ホスト上に、前記第１複数シェアのうち前記少なくとも一つのシェアを保管しないステップと、
前記第１複数シェアのうち前記少なくとも一つのシェアのラベルを、前記第２複数シェアの一つのシェアに関連付けるステップと、
を有するものとする、メッセージ保管方法。
【請求項７】
請求項６に記載のメッセージ保管方法において、メッセージ保管方法はさらに、
前記第１複数シェアのうち前記少なくとも一つが、前記第２複数シェアのうち一つのシェアと同一の場合、
前記第１および第２の複数シェアのうち少なくとも一方に対して、参照カウンタを増加させるステップと、
を有するものとする、メッセージ保管方法。
【請求項８】
安全に保管されたメッセージの検索方法であって、安全に保管されたメッセージを、保管ホスト上に混ぜ合わせ状態にして保管される第１複数シェアに分割するものとした該メッセージの検索方法において、各シェアにラベル付けするステップを有し、このラベル付けステップは、
第４複数ラベルを有するリストを、クライアントから前記保管ホストに送信するステップと、
前記第４複数ラベルのラベルに関連付けしたシェアを、前記保管ホストから前記クライアントホストに送信するステップと、
を有するものとする、メッセージ検索方法。
【請求項９】
請求項８に記載のメッセージ検索方法において、第４複数性は第１複数性よりも多くの要素を有するものとする、メッセージ検索方法。
【請求項１０】
請求項８または９に記載のメッセージ検索方法において、保管ホスト上に保管された各シェアに対して、参照カウンタを関連付けし、前記参照カウンタは、関連付けしたシェアがメッセージの一部として使用される回数をカウントするものとし、前記メッセージ検索方法は、さらに、
対応する特定シェアの削除が要求される度毎に、特定シェアに対する参照カウンタを減らすステップ、
を有するものとする、メッセージ検索方法。
【請求項１１】
請求項１０に記載のメッセージ検索方法において、メッセージ検索方法は、さらに、
前記参照カウンタがゼロのときのみ、前記保管ホスト上の前記特定シェアを削除するステップ
を有するものとする、メッセージ検索方法。
【請求項１２】
プライベートメッセージの安全保管システムにおいて、
保管ホストを備え、
この保管ホストは、複数のプライベートメッセージを混ぜ合わせ状態にして保管し、前記複数のプライベートメッセージをそれぞれ複数のメッセージシェアに分割するよう構成した、
安全保管システム。
【請求項１３】
請求項１２に記載の安全保管システムにおいて、さらに、
前記保管ホストに接続可能なクライアントを備え、
このクライアントは、プライベートメッセージを第１複数メッセージシェアに分割するよう構成した、
安全保管システム。
【請求項１４】
請求項１３に記載の安全保管システムにおいて、
前記クライアントは、複数のラベルからの対応ラベルを前記第１複数メッセージシェアからの各シェアに関連付けするよう構成し、
前記クライアントは、さらに、前記プライベートメッセージに関連付けした対応ラベルのリストを保管するよう構成した、
安全保管システム。
【請求項１５】
請求項１４に記載の安全保管システムにおいて、前記クライアントは、さらに、偽ラベルを前記リストに追加するよう構成した、
安全保管システム。
【請求項１６】
請求項１３〜１５のうちいずれか一項に記載の安全保管システムにおいて、前記クライアントは、前記保管ホストよりも安全性レベルが高いものとする、
安全保管システム。
【請求項１７】
コンピュータ可読媒体であって、プライベートメッセージを安全に保管するためのプログラムを格納し、このプログラムは、プロセッサによって実行されるときに、以下の方法、すなわち、
第１メッセージを第１複数シェアに分割するステップと、
前記第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に、混ぜ合わせ状態にして保管するステップと、
を有する方法を実施するよう構成する、コンピュータ可読媒体。
【請求項１８】
コンピュータ可読媒体であって、安全に保管されたプライベートメッセージを検索するためのプログラムを格納し、このプログラムは、プロセッサによって実行されるときに、以下の方法、すなわち、
第４複数ラベルを有するリストを、クライアントから前記保管ホストに送信するステップと、
前記第４複数ラベルのラベルに関連付けしたシェアを、前記保管ホストから前記クライアントホストに送信するステップと、
を有する方法を実施するよう構成した、コンピュータ可読媒体。
【請求項１９】
プライベートメッセージを安全に保管するためのプログラム要素を格納し、このプログラムは、プロセッサによって実行されるとき、以下の方法、すなわち、
第１メッセージを第複数シェアに分割するステップと、
第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に混ぜ合わせ状態にして保管するステップと、
を実施するよう構成した、プログラム要素。
【請求項２０】
安全に保管されたプライベートメッセージを検索するためのプログラム要素で、このプログラムは、プロセッサが実行するときに、以下の方法、すなわち、
第１メッセージを第１複数シェアに分割するステップと、
第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に混ぜ合わせ状態にして保管するステップと、
を実施するよう構成した、プログラム要素。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、安全保管システム、安全保管方法、安全に保管されたメッセージの検索方法、コンピュータ可読媒体、およびプログラム要素に関し、とくに、単に暗号法原理に基づく計算上の複雑さに依存しない安全保管システムに関する。
【背景技術】
【０００２】
ほとんどの暗号化システムは、それを解読するのに計算上の複雑さに依存している。最終的には、これら全ては、いつか解読されるであろう。すなわち、今日使用されるほとんど全ての暗号化システムは、強引な攻撃の計算上の複雑さに依存している。暗号化機能は、計算的に不可逆的であることを前提とするが、少なくとも１個の可逆な暗号解読機能（復号化）が存在することは知られている。キーを使用する全ての暗号アルゴリズムは、可能な限り全てのキーを試行することで解読できる。計算が終了する、またはコンピュータが十分速くなるのに十分に長く待つだけの問題である。ムーア法によると、コンピュータの処理能力は、１８ヶ月ごとに、倍になる。したがって、現在解読不可能に見えるものも、最終的には将来どこかで解読される。時が経過すると、ほとんどのデータは徐々にその価値および機密性を失うため、通常、問題は起こらない。しかし、それ以外のデータは、無期限に慎重に扱うべきである。例えば、医療データは、決して公にするべきでない。誰かが何年も前に亡くなった時でさえも、（祖）父母からの遺伝性疾患を持つかもしれない子孫は、この情報が公表されると不快に感ずるであろう。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これに代わる、安全保管システム、安全保管方法、保管されたメッセージの検索（回収）方法、コンピュータ可読媒体、およびプログラム要素を提供することが望ましい。
【課題を解決するための手段】
【０００４】
この必要性は、特許請求の範囲の独立請求項による、代替的、安全保管システム、安全保管方法、安全に保管されたメッセージの検索（回収）方法、コンピュータ可読媒体、およびプログラム要素によって満たされる。
【０００５】
本発明の例示的な実施形態によれば、メッセージを安全に保管する方法は、第１メッセージを第１複数シェアに分割するステップと、この第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に、互いに混ぜ合わせ状態にして保管ホスト上に保管するステップと、を有するものとする。
【０００６】
例示的な実施形態によれば、安全に保管されたメッセージを、保管ホスト上に混ぜ合わせ状態にして保管される第１複数シェアに分割するものとした、安全に保管されたメッセージの検索方法は、各シェアにラベル付けするステップを有し、このラベル付けステップは、第４複数ラベルを有するリストを、クライアントから保管ホストに送信するステップと、第４複数ラベルのラベルに関連付けしたシェアを、保管ホストからクライアントに送信するステップと、を有する。
【０００７】
例示的な実施形態によれば、プライベートメッセージの保管システムは、保管ホストを備え、この保管ホストは、複数のプライベートメッセージを混ぜ合わせ状態にして保管し、複数のプライベートメッセージを、それぞれ複数のメッセージシェアに分割するよう構成する。
【０００８】
例示的な実施形態によれば、コンピュータ可読媒体を設け、このコンピュータ可読媒体は、プライベートメッセージを保管するためのプログラムを格納し、そのプログラムは、プロセッサにより実行されるとき、以下の方法、すなわち、第１メッセージを第１複数シェアに分割するステップと、この第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に、混ぜ合わせ状態にして保管するステップと、を有する方法を実施するよう構成する。
【０００９】
例示的な実施形態によれば、コンピュータ可読媒体を設け、このコンピュータ可読媒体は、安全に保管されたプライベートメッセージを検索するためのプログラムを格納し、そのプログラムは、プロセッサにより実行されるとき以下の方法、すなわち、第４複数ラベルを有するリストを、クライアントから保管ホストへ送信するステップと、第４複数ラベルのラベルに関連付けしたシェアを、保管ホストからクライアントホストに送信するステップと、を有する方法を実施するよう構成する。
【００１０】
例示的な実施形態によれば、プライベートメッセージを安全に保管するためのプログラム要素を設け、そのプログラムは、プロセッサにより実行されるとき、以下の方法、すなわち、第１メッセージを第１複数シェアに分割するステップと、第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に混ぜ合わせ状態にして保管するステップと、を有する方法を実施するよう構成する。
【００１１】
例示的な実施形態によれば、安全に保管されたプライベートメッセージを検索するためのプログラム要素を設け、そのプログラムは、プロセッサにより実行されるときに、以下の方法、すなわち、第１メッセージを第１複数シェアに分割するステップと、第１複数シェアを、少なくとも第２メッセージの第２複数シェアと共に保管ホスト上に混ぜ合わせ状態にして保管するステップと、を有する方法を実施するよう構成する。
【発明の効果】
【００１２】
本発明の例示的な実施形態として、メッセージの安全保管および／または検索方法およびそれに対応する安全保管システムを提案し、その方法および安全保管システムは、単に暗号法原理に基づく計算的複雑さに依存しないという意味で、標準的な暗号方式とは異なる。敵対者が無限の計算能力を持つと予想されるときでさえも、例示的な実施形態による安全保管方法は、既知の方法より安全である。説明上、安全保管システムは、データおよび／またはメッセージを多数（シェア）に分け、他のデータ（メッセージ）の断片と混ぜ合わせ、これら断片をすべて大きな保管場所、いわゆるラッキーディップに投入する、と言える。もちろん、無限の計算能力を持つ攻撃者は、全ての断片から元のデータ（メッセージ）を再現するかもしれない。しかし、彼はラッキーディップに投入されないメッセージもまた「再現」する。敵対者は、偽メッセージと真正メッセージを区別できないため、適正メッセージを見つける確率は低い。このメッセージは、電子ドキュメントまたはファイルとすることができる。
【００１３】
本発明の一態様は、データ所有者が所有していない信頼できないホスト上にあるデータベースにプライベート（私的）情報を保管する方法を提供する。好ましくは、その方法は、単に従来の暗号化方式に共通の計算的複雑さに依存しないだけでなく、情報の理論予測にも依存しない。この方法は、例えば、秘密共有を使用して、各データ要素（メッセージ）を、多数のシェアに分割し、これら多数のシェアを、可能であれば他のユーザーからの、他のデータ要素（メッセージ）のシェアと混ぜ合わせる。
【００１４】
その方法は、信頼できないホスト上にあるメッセージを保管する効率的な方法を促進する。メッセージは、信頼できないホスト上にある他のメッセージにおける他のシェアと共に、すなわち混ぜ合わせ状態にして保管される、複数のシェアに分割する。とくに、どのシェアがどの特定メッセージに属しているかの情報は、メッセージを保管するホスト、すなわち保管ホスト上に保管されない。したがって、その方法は、とくに、信頼できないホスト上にメッセージを保管するのに有利である。とくに、用語「混ぜ合わせ状態にして」は、保管ホスト上に保管されているどのシェアがどのメッセージに属するかの情報は、保管ホスト上に保管されないことを意味する。したがって、保管ホストに対して、異なるシェアは特定メッセージに割り当て可能ではない。好ましくは、複数のメッセージを、保管ホストに共に追加し、例えば、複数のメッセージシェアの一つとともに追加する。したがって、複数のメッセージシェアがどのくらい多くのメッセージに属しているか、また、どの複数メッセージシェアがどの元メッセージに属しているか、の情報がまったく保管ホストにないため、さらに安全レベルを上げることが可能である。
【発明を実施するための最良の形態】
【００１５】
以下において、安全保管方法のさらに例示的な実施形態を説明する。しかし、これらの実施形態は、安全保管システム、安全に保管されたメッセージの検索方法、コンピュータ可読媒体、およびプログラム要素にも適用する。
【００１６】
安全保管方法の他の例示的な実施形態によれば、保管ホストは、リモートホストとし、メッセージ保管方法は、さらに、第１複数シェアをリモートホストに送信するステップを有する。
【００１７】
他の例示的な実施形態によれば、その方法は、さらに、第１複数シェアを保管ホスト上に保管する前に、第１複数シェアの各シェアに、第３複数ラベルからの対応するラベルでラベル付けするステップを有する。好ましくは、ラベル付けは、第１複数シェを送信する前に行う。
【００１８】
メッセージ、すなわちシェアを保管ホストに送信する前に行う、ラベル付けを使用することによって、一方で保管を保管ホスト上で安全に行い、他方で、どのシェアがどの特定メッセージに属するかの情報は保管ホスト上に保管されないようにする効果的な方法を提供することが可能である。これは、とくに、いくつかのメッセージを保管ホストに共に送信する場合に適切である。一つの例示的な態様によれば、付加したラベルは、データ所有者が簡単に検索できるように、データ要素（メッセージシェア）に対するプライベート鍵と見なすことができる。
【００１９】
他の例示的な実施形態によれば、第３複数レベルは、保管ホストから受信する。
【００２０】
保管ホストから複数のラベルを受信することによって、各ラベルが保管ホスト上で一度だけ使用されることが可能になり、ラベル付けは一義的である。とくに、必要以上に多くラベルを要求するのに有利である、すなわち、受信したラベルの数は、メッセージを分割するシェアの数より多い。したがって、ラベルが一つのメッセージに対するラベルとして使用される保管ホストから隠すことが可能である。
【００２１】
他の例示的な実施形態によれば、その方法は、さらに、第１複数シェアのうち少なくとも一つを、第２複数シェアのシェアと比較するステップを有する。第１複数シェアのうち少なくとも一つが、第２複数シェアの一つのシェアと一致している場合、その方法は、保管ホスト上に保管された第１複数シェアのうち前記少なくとも一つを保管しないステップと、第１複数シェアのうち前記少なくとも一つのラベルを、第２複数シェアの一つのシェアに関連付けるステップと、を有する。
【００２２】
本発明のこの例示的な態様においては、他のデータ要素および／またはユーザーからのシェアを再使用する方法として示すことができる。すなわち、同一のシェアまたはデータ要素は、保管ホストに一度だけ保管されるが、異なるメッセージに対して使用される。これは、保管方法の安全性を少し下げることによって、保管ホスト上の必要な保管スペースを減らす。この比較は、例えばクライアントホスト上または保管ホストそのもの上の保管ホストへ、シェアを送信する前に行う。比較が保管ホストによって行われたら、保管されていない同一のシェアのラベルは、好ましくは、既に保管されたシェアに追加し、保管されたシェアは２個のラベルを有する。比較がクライアントホスト上で行われたら、特定シェア、すなわち、既に保管ホスト上に保管されたシェアは、好ましくは、保管ホストに再び送信しない。
【００２３】
他の例示的な実施形態によれば、その方法は、さらに、第１複数シェアのうち少なくとも一つが、第２複数シェアの一つのシェアと同一である場合、第１および第２の複数シェアのうち少なくとも一方に対して、参照カウンタを増加させるステップを有する。
【００２４】
この参照カウンタを設けることは、１個のシェアの削除によって確実に多くのメッセージを破損させない適切な手段である。これは、とくにシェアの再使用が許される場合に有利である。そのシェアがどのメッセージに属するかわかっている単一実体はないため、他の手法を取らずにシェアを安全に削除することはできない。この手法の一つとしては、各シェアに参照カウンタを付加する。シェアを新たに付加したメッセージの一部として用いる度毎に、カウンタを増加し、対応するメッセージが削除される度毎に、カウンタを減少する。ある瞬間、またはいかなる瞬間にもラッキーディップを見ることができる攻撃者が、増加および減少操作を見つけることによって、どのシェアが同一グループに属しているかを探し出すのを回避するため、これらの操作を時間的に拡張する。例えば、クライアントは、保管ホスト（サーバ）にその参照カウンタを増やすように要求することによって、初期段階におけるシェアの束をリザーブ（取り置き）できる。クライアントがメッセージを付加したい度毎に、サーバに知らせることなく、これらのリザーブ（取り置き）したシェアのうち若干を使用することができる。削除するときは、クライアントは、真正シェアに、十分にリザーブ（取り置き）された（ただし、使用されていない）シェアを混ぜ合わせ、十分な安全性を提供する。ラッキーディップは、リザーブされたシェアと使用されるシェアを区別できない。ラッキーディップは、参照カウンタがゼロに達したときのみ、実際にシェアを削除する。他の手法としては、時間切れメカニズムまたは分散ごみ回収法がある。
【００２５】
以下において、検索方法のさらなる例示的な実施形態を説明する。しかし、これらの実施形態は、安全保管システム、メッセージの安全保管方法、コンピュータ可読媒体、およびプログラム要素にも適用する。
【００２６】
検索方法の他の模範的な実施形態によると、第４複数性は、第１複数性よりも多くの要素を有する。
【００２７】
言い換えれば、これは、シェアが、メッセージそのものが有するよりも多いことを必要とされることを意味し、偽シェアも保管ホストから送信される。したがって、攻撃者は、どのシェアが実際にどの受信メッセージに属しているか、またどのシェアがメッセージ自体に属していないかわからないため、安全レベルを上げることができる。したがって、送信にアクセスする攻撃者は、送信されたシェアを結合して元のメッセージを得ることができない。
【００２８】
検索方法の他の例示的な実施形態によれば、保管ホストに保管された各シェアに対して、参照カウンタを関連付けし、参照カウンタは、関連付けしたシェアがメッセージの一部として使用される回数をカウントする。その方法は、さらに、対応する特定のシェアの削除が必要とされる度毎に、特定シェアに対する参照カウンタを減らすステップを有する。好ましくは、保管ホスト上の特定シェアは、参照カウンタがゼロのときのみ削除する。
【００２９】
この参照カウンタを設けることは、単一のシェアの削除によって確実に多くのメッセージを破損するのに適切な手段である。これは、とくにシェアの再使用を可能にする場合に有利である。どのシェアがどのメッセージに属するかわかっている単一実体はないため、他の手法を取らずにシェアを安全に削除することはできない。この手法の一つとしては、各シェアに参照カウンタを付加するものがある。シェアを新たに付加したメッセージの一部として用いる度毎にカウンタを増加し、対応するメッセージが削除される度毎に、カウンタを減少する。
【００３０】
以下において、保管システムのさらなる例示的な実施形態を説明する。しかし、これらの実施形態は、検索方法、メッセージの安全保管方法、コンピュータ可読媒体、およびプログラム要素にも適用する。
【００３１】
他の例示的な実施形態によれば、安全保管システムは、さらに、保管ホストと接続可能なクライアントを備え、このクライアントは、プライベートメッセージを第１複数メッセージシェアに分割するよう構成する。好ましくは、クライアントは、複数のラベルからの対応ラベルを、第１複数メッセージシェアからの各シェアに関連付けするよう構成し、さらに、プライベートメッセージに関連付けした対応ラベルのリストを保管するよう構成する。とくに、クライアントは、さらに、偽ラベルをリストに追加するよう構成する。
【００３２】
各メッセージのラベルのリストを、好ましくはクライアント側に保管することによって、保管システムの安全性を上げることができ、これは、すなわち、保管ホスト上に保管されているどのシェアがどの特定メッセージに属するかの情報が、保管ホスト上に保管されていないためである。
【００３３】
保管したメッセージを検索している間に偽ラベルを使用しているときは、これは、特定メッセージを保管ホストから検索する度に、同じ偽ラベルを用いて、保管の安全性を向上するのに有利である。こうすることで、どのシェアが実際にどのメッセージに属しているか、また、どのシェアが偽ラベルに属しているか、すなわち実際のメッセージに属していないかを推測する可能性が減る。
【００３４】
保管システムの他の例示的な実施形態によれば、クライアントは、保管ホストよりも高い安全性を持つものとする。とくに、クライアントは、メッセージの所有者により信頼される。例えば、クライアントは、メッセージの所有者自体に所有されているコンピュータシステムであり、保管ホストは、他の実体によって所有されているデータベースである。したがって、メッセージの所有者は、保管ホストそのものの安全レベルは直接わからないが、クライアントホストの安全性に対応しており、したがって、クライアントがどの程度安全であるかわかる。
【００３５】
要約すると、例示的な実施形態の要点は、異なるユーザーによって所有されているいくつかのメッセージを１個のラッキーディップに保管するデータベースを提供する。各メッセージは、多数のシェアに分割し、他のメッセージのシェアと混ぜ合わせ、どのシェアに属するかを不明瞭にする。付加的な情報がなければ、メッセージを検索することは計算的に難しい。メッセージの再現の唯一の方法は、全ての可能な方法を試行し、強行検索することである。推測される数はシェアの数によって指数関数的に増加する。さらに、シェアは多くの方法で結合し、それらの再結合の多くが適正であるとみなされるが、これら再結合がラッキーディップに置かれることは決してない。敵対者または攻撃者は、どの再結合が真正で、どの再結合が偽物であるかを推測する以外はできない。適正ユーザーが効率的にメッセージを検索できるようにするため、シェアはラベルによって注釈付けする。ラベルを付け、および／または、ラベルをユーザーによってシェアと関連付けることで、プライベート（秘密）鍵として機能できる。ラベルは、通常はメッセージよりもスペースを取らないが、クライアントサイトに保管され、同一メッセージに属するシェアを検索するのに使用される。ラベル間の関連を盗聴者から隠すため、真正ラベルを偽ラベルと混ぜ合わせる。好ましくは、偽ラベルの数は、攻撃者が元メッセージを再現する危険性を最小にする程十分に多くなるように決定する。偽ラベルの数の選択は、安全性とシステムおよび／または方法の効率との間の妥協点である。
【００３６】
好ましくは、その方法は、標準的なデータベース操作、すなわち読み込み、追加、および削除を実行する。
【００３７】
本発明のこれらおよび他の態様は、以下で説明する実施例から明らかになるであろう。
【実施例】
【００３８】
本発明の例示的な実施例を、以下図面につき説明する。
【００３９】
図面は模式的である。異なる図面において、類似の、または同一の要素は、類似の、または同一の参照符号付して説明する。
【００４０】
図１は、保管システム１００の簡略化した模式図である。保管システム１００は、保管ホストまたはデータベース１０１および、複数のクライアントホスト、例えばクライアントホスト１０２，１０３，１０４，１０５を有する。クライアントホストは、データベース１０１に接続し、異なる所有者によって所有される。通常は、クライアントの記憶容量は、保管ホストの記憶容量よりも小さい。保管ホスト１０１は、セントラルサーバまたはデータベースによって形成する。保管ホスト１０１は、ハードディスク１０６または同様のもののような、保管媒体を有する。この保管媒体において、メモリを、異なるホストの所有者のよって所有されている複数のメッセージを保管するよう割り当てる。例示的な実施形態によると、メモリに保管した各メッセージは、複数のメッセージシェアに分割し、全メッセージシェアをこの割り当てたメモリにおいて混ぜ合せ状態にして保管する、すなわち、メッセージシェアは互いに混ぜ合わされ、いわゆるラッキーディップを形成し、また、保管ホストおよび保管ホストの所有者は、どのメッセージシェアがどの元メッセージに属するかという情報を持たない。したがって、同様にデータベースにアクセスする攻撃者も、どのメッセージシェアがどの実際メッセージに属するのかわからない。
【００４１】
図２は、例示的な実施形態による、本発明保管および受取方法の簡素化した概略フローチャートである。この保管方法の第１ステップ２０１において、複数のラベルを保管ホストから受信する。その後、ステップ２０２において、メッセージを、メッセージの所有者によって複数のメッセージシェアに分割する。この分割は、好ましくは、メッセージの所有者が所有するクライアント上で行う。ステップ２０３において、各メッセージシェアを、複数のラベルにおける一つのラベルに関連付けする。それから、ステップ２０４において、ラベル付けされたメッセージシェアを、保管ホストに送る。さらに、いくつかの偽シェアを、実際にメッセージに属するメッセージシェアと共に送る。好ましくは、メッセージを保管ホストに送信するとき、とくに、「ラッキーディップ」が空の場合、単独メッセージに関連するシェアも保管ホストに追加するべきである。もっと正確に言えば、第１メッセージを、異なるメッセージの混ぜ合わせシェアの束として追加する。ユーザーが保管するメッセージを１個しか持っていなかったら、不要メッセージの束を生成する、または他のユーザーと協力する。実際上、これら不要シェアは後で削除することができる。メッセージシェアを送信する時点で、どのメッセージシェアが保管されるメッセージに属するかのリストを、クライアント上に保管する。つぎに、ステップ２０５において、メッセージシェアを、同一ユーザーおよび／または異なるユーザーの他のメッセージシェアと共に保管ホスト上に保管する。したがって、いわゆるラッキーディップは、保管ホスト上で形成される。随意的には、保管ホスト上で、送信されたメッセージシェアを、既に保管ホスト上に保管されたシェアと比較する。同一のシェアが既に保管ホスト上に保管されている場合、これらの同一のメッセージシェアは再び保管ホスト上に保管せず、むしろ再使用する。すなわち、特定のメッセージシェアは、一度だけしか保管されず、各ラベルは、既に保管されたメッセージシェアにも関連付ける。代案として、この比較は、既にクライアントホスト上で行うこともでき、この場合、比較は同一所有者のメッセージシェアにのみ行うことに注意しなければならない。逆に、比較をクライアントホスト上で行う場合、比較は、全ての保管したメッセージシェア間で行う、すなわち、他のユーザーのメッセージシェアとも比較する。メッセージシェアの再使用を行う場合、参照カウンタは、メッセージシェアがメッセージの一部として使用される回数をカウントして各メッセージシェアと関連付けする。この参照カウンタは、各メッセージ、すなわちメッセージシェアが、保管ホスト上で削除することを要求される度毎に、減少する。
【００４２】
メッセージの所有者が保管ホストからメッセージを検索したいときは、要求を、送信される全てのラベルのリストと共に保管ホストへ転送し、これはステップ２０６で送信される。つぎにステップ２０７で、保管ホストは、要求されたメッセージシェアをクライアントに送信し、メッセージはメッセージシェアに分割されたときクライアント上に保管されたラベルのリストを使用して、元のメッセージを再結合する。好ましくは、実際にメッセージに属するメッセージシェアを要求するだけでなく、安全レベルを上げるため、実際のメッセージに属さないいくつかの偽メッセージシェアも要求する。回収すべきメッセージの「真正」メッセージシェアとともに要求される、偽メッセージシェアは、真正メッセージとともに保管ホストに送信された偽メッセージシェアと同一にする、または、使用時に既知の他の偽メッセージシェア、例えば、同一ユーザーの異なるメッセージのメッセージシェアもしくは他のユーザーのメッセージシェアとすることができる。したがって、攻撃者は、どのメッセージシェアがどの実際のメッセージに属するかわからない。安全レベルをさらに上げるため、この特定のメッセージを再度クライアント、すなわち、この特定のメッセージの所有者に送信するとき、常に同一偽メッセージシェアを要求するようにすると有利である。
【００４３】
以下において、例示的な実施形態による本発明方法をさらに考察する。
【００４４】
各メッセージを有限フィールドＦにおける同じ数のブロックに分割すると仮定することができる。代表的な用途では、この有限フィールドは、２進数の有限フィールド、すなわち２進数付加の｛０；１｝である。このようなブロックはそれぞれ、Ｆｎの要素であり、ｎはブロック長である。議論を簡単にするため、全メッセージｍｉは、Ｍ⊆Ｆｎから取る。各ｍｉは、ｋ∈Ｎシェアに分け、Ｎは、自然数の集合とする、すなわち、秘密シェア（共有）手法を用いて、
【数１】
2009535660.tif 000003
である。
【００４５】
シェアｍｉ（ｊ）はラベルｌｉ（ｊ）を取る。ラベルは、任意のタイプとすることができるが、ラベルがＬ⊆Ｆｓの要素であれば、ｓはラベルの大きさで、通常ｎよりもずっと小さいのが、最も実用的である。サーバは、タプル（ｌｉ（ｊ），ｍｉ（ｊ））を含むラッキーディップを保管し、また、クライアントはラベルがともに属するトラック（ｉ，｛ｌｉ（ｌ），．．．，ｌｉ（ｋ）｝）、すなわち、がメッセージｍｉに属しているラベル（ｌｉ（ｌ），．．．，ｌｉ（ｋ））のトラックを維持する。
【００４６】
メッセージｍｉをデータベースから検索する際、ユーザーは、まず、自身の保管データから対応するラベルｌｉ（ｌ），．．．，ｌｉ（ｋ）を検索する。これらの真正ラベルは、サーバに送られる前に、偽ラベルと混ぜ合わされる。好ましくは、偽ラベルは、ラッキーディップ、例えば、同一ユーザーのそれ以前の先行メッセージにおける使用済みラベルまたは同一ユーザーにおける生成した偽ラベル、すなわち、真正または実際のメッセージに関連せず、先行メッセージと共に送信するよう生成された、ごみメッセージシェアに関連したラベルに使用する。こうして、同一集合に属するｌｉ（ｌ），．．．，ｌｉ（ｋ）が、サーバから隠れる。サーバは、真正シェアｍｉ（ｊ）および偽シェアとの両方を送信する。後者の偽シェアは、単独メッセージのメッセージシェアに関連するラベルのリストはクライアント上に保管されるため、簡単にクライアントによってフィルタ処理できる。
【００４７】
必要とされるラベルの総数は、ｋ個のみ真正として、ｃｋ（ｃ∈Ｎ）にする。このとき、攻撃者は、ともに組み合わせるシェアとしては、次式で表される個数、すなわち
【数２】
2009535660.tif 000004
個の可能性を持つ。すなわち
【数３】
2009535660.tif 000005
の選択がある。ｍｉを検索するために実際のラベルと共に送られた（ｃ−１）ｋ個のラベルが、同一メッセージｍｉが検索される度に異なるときは、よくない。なぜなら、攻撃者が、ユーザーがメッセージを二度検索していることに気づいたら、一度目および二度目に送られたラベルの交差を取るだけだろう。これを防止するため、同一メッセージを二度要求するとき、好ましくは、確実に要求したｃｋ個のラベルが必ず特定のメッセージに対して同一であるようにする。このことを達成するための方法は様々ある。例えば、各ある得るラベルをｃ個のラベルよりなるプリセットしたグループ内に含めることができる。すなわち、ラベルのうちの１個をこのグループに含めたいとき、このグループにおける各ラベルに関連するデータを要求する。例えば、ラベルｌ  ｌ∈｛０，１｝５０）と接続するデータを要求する場合、共通する最初の４０ビットを有する全ラベルｌ′と接続するデータを必ず要求する。
【００４８】
ラッキーディップにおけるカオス（混沌状態）をさらに増大するため、異なるユーザーによって所有されることができる異なるメッセージは、互いにシェアを共有することができる。例えば、
【数４】
2009535660.tif 000006
とすると、ｍ２は、ｍ１（１）およびｍ１（２）を再使用して、
【数５】
2009535660.tif 000007
によって決定される。シェアを再使用する目的は、２個ある。より少ない数のシェアしか保管しないため、一方で、ラッキーディップの大きさを小さくする。他方で、安全性を上げる。
【００４９】
シェアの再使用の効果を数値化するため、２個のラッキーディップ、すなわち、再使用を有するものと、再使用を有していないものを比較する。最初のメッセージを除いた、各メッセージは、ディップ（またはごみ箱）に既に入っている（ｋ−１）個のシェア、および新しい１個のシェアから成る。この場合、シェアを再使用するディップは、ｋ＋ｈ−１個のシェア（ｈはメッセージの総数）を保管し、シェアを再使用しないディップは、全てのｈｋ個のシェアを保管する。したがって、シェアは、およそ係数ｋだけ小さくなる。
【００５０】
他方で、より小さいごみ箱からｋ個より少ないタプルが取り出されるため、シェアが少ないと、安全性が下がる。しかし、思ったほど悪くはない。再使用しない場合、ラッキーディップは、ランダムにそのｈｋ個のシェアをｈ個の区分に分割し、再使用する場合、攻撃者は申し分のない区分の利点がない。
【００５１】
以下において、更新を確実安全にするために再使用を活用する。
再使用がない場合：
攻撃者は、どの特定区分が選択されたかわからず、そのため、全てのあり得る区分を調べなければならない。可能性の数は以下のように計算する。
第１  ｋタプル：
【数６】
2009535660.tif 000008
第２  ｋタプル：
【数７】
2009535660.tif 000009
．．．
第ｉ  ｋタプル：
【数８】
2009535660.tif 000010
．．．
第ｈ  ｋタプル：１
取り得る区分の総数は、
【数９】
2009535660.tif 000011
再使用する場合：
再使用する場合、攻撃者は、申し分のない区分を信頼することができない。大きさｋ＋ｈ−１個のラッキーディップの中からｈ個の独立したｋタプルを取らなければならない。したがって、可能性の総数は、
【数１０】
2009535660.tif 000012
である。この数は、再使用しない場合よりも少ないが、それでも莫大な数である。
【００５２】
保管システムに対する起こり得る脅威は、攻撃者の能力による。攻撃者を３つのタイプに分類できる。
【表１】
2009535660.tif 000013
【００５３】
タイプIの攻撃者（例えば、ハードディスクを盗用した従業員）は、通信を見ることができず、タイプIIの攻撃者（例えば、頻繁にデータベースをコピーするバックアップオペレータ）は、更新を見ることができ、タイプIIIの攻撃者（例えば、システムを完全に制御するシステムオペレータ）は、更新と読み込み操作の両方を見ることができる。そのモデルの攻撃者は全て受動的である。送信中またはラッキーディップにおいて保管されたデータを修正する能動的な攻撃者は、調査していない。
【００５４】
●  データベースにおいて、ある標準的データベース操作が可能である。これらの標準的データベース操作は、読み込み
●  追加
●  削除
●  （修正）、修正は、＜削除、追加＞としてモデル化することができ、したがって以下では扱わない。
【００５５】
ラッキーディップの原則に基づいたデータベースシステムは、好ましくは、情報漏洩がこれらの操作の間中少ない状態を維持するように処理する。好ましくは、妥協点（トレードオフ）は、安全性と効率との間で決定する。ラッキーディップのパラメーによって、この妥協点が精密に特定できる。全操作は、それ自身安全性の脅威および結果を有する。各操作を以下にまとめる。
【００５６】
読み込み：
タイプIおよびI I（上表）の攻撃者だけが、注意すべき対象であるとき、特別な予防措置は必要ない。しかし、タイプIIIの攻撃者が存在する場合、ｋ個のシェア探し出すだけで、メッセージ全体が漏洩する。ｋ個のシェアが同一グループに属するということを隠すため、ｂ個の偽ラベルをクエリーに付け加えることで、ノイズを誘発する。こうして、情報漏洩は、ｋ＋ｂ個のシェア内にメッセージ（ｋ個のシェアに分割された）が隠れることに集約される。しかし、可能なメッセージの総数は、
【数１１】
2009535660.tif 000014
であり、十分に大きいｂに対して極めて多いものであり、安全性と効率との間における妥協点のパラメータとして機能することができる。メッセージが複数回検索されているとき、毎回ｋ＋ｂ個のシェアの同一セットを用いるのが望ましい。そうしないと、攻撃者は、同一であると推測される２個のメッセージに属する２個のシェアセットの交差を取ることができる。メッセージが実際に同一である場合、交差取りは、ほぼ確実にｋ個のシェアを露呈する。
追加：
タイプIの攻撃者は、いかなる更新をも見ることができない。したがって、それに対して予防措置は必要ない。タイプIIの攻撃者は、シェアの再使用を可能にすることで、ミスリードされる。ｋ−ｓ個のシェアを、ラッキーディップ中に既に存在するシェアから取り出すとき、ｓ（例えばｓ＝１）個のシェアを追加しなければならない。タイプIIの攻撃者は、他のどのシェアがメッセージに属しているかの手掛かりがない。これは、タイプIIIの攻撃者にとっては当てはまらない。これはすなわち、更新に先立つｋ−ｓ個のシェアの検索結果を見ることができるからである。タイプIIIの攻撃者をミスリードさせるため、好ましくは、一度に複数のメッセージを追加する。ｔ個のメッセージを混ぜ合わせると、結果ｔｋ個のシェアができる。再結合の総数は、
【数１２】
2009535660.tif 000015
であり、この総数は、ｔが十分に大きいとき十分多い数である。追加すべきメッセージの数が少ないとき、真正メッセージに偽シェアを混ぜ合わせると安全性が上がる。偽シェアが貴重な保管スペースを占有することを防ぐため、偽シェアは、既にラッキーディップ内にあるものから選択する。ラッキーディップによってシェアが再使用を可能にするとき、攻撃者は偽シェアと再使用されたシェアを区別できない。
削除：
削除すべきメッセージが古い、または不正であり、したがって、メッセージを削除することの理由であるが、古いメッセージを露呈させるのはよいアイデアではない。削除すべきメッセージの数（ｔ）が十分に大きければ、メッセージは十分に混ぜ合わされて、ｔｋ個のシェアをｔ個の元メッセージに再区分するのを防ぐ。シェアの再使用を可能にするとき、１個のシェアの削除は、多くのメッセージを破損させる。どのシェアがどこに属しているかを知る単一の実体はないため、他の特別な手法を取らずに安全にシェアを削除することはできない。このような手法としては、各シェアに参照カウンタを付加することがある。シェアを新たに付加したメッセージの一部として使用する度毎に、カウンタを増加し、対応するメッセージを削除する度毎に、カウンタを減少する。ある瞬間、またはあらゆる瞬間にラッキーディップを見ることができる攻撃者が、増加および減少操作を見つけることによって、どのシェアが同一グループに属しているか探し出すのを回避するため、これらの操作を時間的に拡張する。例えば、クライアントは、保管ホスト（サーバ）にその参照カウンタを増やすように要求することによって、初期段階におけるシェアの束をリザーブ（取り置き）できる。クライアントがメッセージを付加したい度毎に、サーバに知らせることなく、これらリザーブ（取り置き）したシェアのうち若干を使用することができる。削除するときは、クライアントは、真正シェアに、十分にリザーブされた（ただし、使用されていない）シェアを混ぜ合わせ、十分な安全性を提供する。ラッキーディップは、リザーブされたシェアと使用されるシェアを区別できない。ラッキーディップは、参照カウンタがゼロに達したときのみ、実際にシェアを削除する。他の手法としては、時間切れメカニズムまたは分散ごみ回収法がある。
【００５７】
要約すると、例示的な実施形態の要旨は、異なるユーザーが所有するいくつかのメッセージを１個のラッキーディップに保管するデータベースを提供するということである。各メッセージを、他のメッセージのシェアに混ぜ合わせる多数のシェアに分割し、どのシェアが同一グループに属するのかを曖昧にする。付加的な情報がなくとも、メッセージを復元するのは計算的に難しい。
【００５８】
用語「有する」は、他の要素またはステップを除外せず、また“ａ”もしくは“ａｎ”は、複数を除外しないことに留意されたい。異なる実施形態に関連して説明した要素も含む。特許請求の範囲における参照符号は請求項の範囲を限定するものと解釈すべきではないことに留意されたい。
【図面の簡単な説明】
【００５９】
【図１】例示的な実施形態における、本発明による確実保管システムの簡素化した模式図である。
【図２】例示的な実施形態における、本発明による保管および受取方法の簡素化した概略フローチャートである。
【図１】
2009535660.tif 000016
【図２】
2009535660.tif 000017
【国際調査報告】
2009535660.tif 000018
2009535660.tif 000019
2009535660.tif 000020
2009535660.tif 000021