(57)【要約】  複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）に一組のオリジナルデータ（Ｅ１，...，Ｅｎ）を格納して、複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）から一組のオリジナルデータ（Ｅ１，...，Ｅｎ）を検索する方法は、一組のオリジナルデータ（Ｅ１，...，Ｅｎ）から一組のコード化されたデータ（Ｓ１，...，ＳＮ）を生成するコード化ステップと、一組のコード化されたデータ（Ｓ１，...，ＳＮ）を複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）に格納する格納ステップとを備える。上記複数のサーバの各サーバ（ＳＰ１，...，ＳＰｌ＋１）は、一組のコード化されたデータ（Ｓ１，...，ＳＮ）のそれぞれ一部のみを格納し、当該方法は、一組のコード化されたデータ（Ｓ１，...，ＳＮ）のどのそれぞれの部分が上記複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）のどのサーバに格納されるかを示すテーブル（Ｔ１，Ｔ２）を生成するステップを備える。
2017511552.tif 000002
【特許請求の範囲】
【請求項１】
複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）に一組のオリジナルデータ（Ｅ１，...，Ｅｎ）を格納して、前記複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）から前記一組のオリジナルデータ（Ｅ１，...，Ｅｎ）を検索する方法であって、
前記一組のオリジナルデータ（Ｅ１，...，Ｅｎ）から一組のコード化されたデータ（Ｓ１，...，ＳＮ）を生成するコード化ステップと、
前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）を前記複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）に格納する格納ステップとを備え、
前記複数のサーバの各サーバ（ＳＰ１，...，ＳＰｌ＋１）は、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）のそれぞれ一部のみを格納し、
前記方法は、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）のどのそれぞれの部分が前記複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）のどのサーバに格納されるかを示すテーブル（Ｔ１，Ｔ２）を生成するステップを備えることを特徴とする、方法。
【請求項２】
前記方法は、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）をコード化されたデータのサブセットに分割するステップを備え、コード化されたデータ（Ｓ１，...，ＳＮ）のサブセットのうちの任意の２つは、前記２つのうちの一方のサブセットから前記２つのうちの他方のサブセットまで同一のデータを持たず、
前記方法は、コード化されたデータ（Ｓ１，...，ＳＮ）の各サブセットを前記複数のリモートサーバ（ＳＰ１，...，ＳＰｌ＋１）のそれぞれのサーバに格納するステップを備えることを特徴とする、請求項１に記載の方法。
【請求項３】
どのコード化されたデータ（Ｓ１，...，ＳＮ）がどのサブセット（Ｇ１，...，Ｇｌ＋１）に配置されるかを示すテーブル（Ｔ１）を生成するステップを備えることを特徴とする、請求項２に記載の方法。
【請求項４】
どのサブセット（Ｇ１，...，Ｇｌ＋１）がどのサーバ（ＳＰ１，...，ＳＰｌ＋１）に配置されるかを示すテーブル（Ｔ２）を生成するステップを備えることを特徴とする、請求項２または３に記載の方法。
【請求項５】
前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）の前記各部分は、シンボルに存在し、前記方法は、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）の前記各部分から少なくとも１つのシンボルをクエリするクエリステップを備えることを特徴とする、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記クエリステップは、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）の前記各部分においてどのシンボル（Ｓ１，...，ＳＮ）をクエリしなければならないかを判断するステップを備えることを特徴とする、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
前記一組の符号化されたデータ（Ｓ１，...，ＳＮ）は、符号化されたデータのサブセットに分割され、各サブセットは、周囲空間の超平面を表わすことを特徴とする、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）の前記各部分においてどのシンボル（Ｓ１，...，ＳＮ）をクエリしなければならないかを判断するステップは、前記判断されたシンボルが、前記一組のコード化されたデータ（Ｓ１，...，ＳＮ）の前記各部分によってそれぞれ形成される各超平面を横断する方向を構成するように実行されることを特徴とする、請求項６および７の組み合わせに係る方法。
【請求項９】
特定のシンボル（Ｓｉ）を検索するために、前記クエリされたシンボル（Ｓ１，...，ＳＮ）を復号するステップを備えることを特徴とする、請求項５〜８のいずれか１項に記載の方法。
【請求項１０】
前記コード化ステップ（Ｅ１，...，Ｅｎ、Ｓ１，...，ＳＮ）は、局所復号可能符号を用いて実行されることを特徴とする、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
前記復号ステップ（Ｓ１，...，ＳＮ）は、局所復号アルゴリズムを用いて実行されることを特徴とする、請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データストレージサーバ内の情報、データベースに対してなされるクエリ、およびこのようなクエリのプライバシのストレージに関する。
【背景技術】
【０００２】
昨今では、多くのドキュメントおよびデータベースが、アウトソーシングされたデータストレージサーバに格納される。この傾向は、多くのサービスおよび企業の情報システムのクラウド化によりさらに強まっている。このようなアウトソーシングされたデータベースは、安価にメンテナンスでき、最新の情報を効率的に検索できるが、セキュリティまたはプライバシの観点からは重大なリスクをもたらす恐れがある。複数のクラウド上でアウトソーシングされたデータストレージをセキュリティ保護するためにいくつかのソリューションが提案されてきたが、それらはプライバシの問題には対処していない。実際、データベースにアクセスすることによって、当該データベースを格納するエンティティは、クエリアまたはユーザのクエリを学習するが、これは、ユーザの意向を秘密にすべきである場合には問題になる可能性がある。例えば、特定の株式の現行市場価格について株式市場データベースに照会する投資家は、当該株式に関心を持っていることを明らかにすることを望まないかもしれない。なぜなら、それが意図せずに当該株式の価格に影響を及ぼし得るからである。一方、企業は、特許のアイデンティティを明らかにすることなく特定の特許を探し出したいかもしれない。
【０００３】
個人情報検索（private information retrieval：ＰＩＲ）スキームは、検索された記録（record）のアイデンティティをデータベース所有者から完全に隠しながら、クライアントがアウトソーシングされたデータベースまたはクラウドから記録を検索することを可能にする暗号プロトコルである。２種類のＰＩＲ、すなわち情報理論的ＰＩＲまたは算術的ＰＩＲがある。後者はセキュリティ保証が弱いため、ユーザが何を望んでいるかについての情報をサーバが入手することはない、絶対的な保証を提供する情報理論的ＰＩＲに注目する。情報理論的ＰＩＲは、複数のサーバにわたっていくつかの複製を有するマルチサーバ設定においてのみ可能である。コード化理論、より特定的に局所復号可能符号（locally decodable codes）、すなわちＬＤＣに基づいてこの問題に対するソリューションを提供する広範な研究がある。しかし、現在のソリューションは、多数の複製を必要とする。基本的に、ｌがＬＤＣの局所性である場合、データベース全体をまず符号化する必要があり、これはデータベースのサイズの増大の第１の要因をもたらし、次いで、符号化されたデータベース全体をｌ個の異なるサーバ上でｌ回複製する必要がある。
【０００４】
ｎ個の要素、例えばＥ１，...，Ｅｎで構成されるデータベースを有していると仮定する。現在のソリューションは、Ｎ個のシンボルＳ１，...，ＳＮ（Ｎ＞ｎ）の符号語でデータベースを符号化し、次いで、符号化されたデータベースのｌ個のコピーをｌ個の異なるサーバに格納し、ｌは符号の局所性である。シンボルＳｉを明らかにすることなく検索するために、ユーザは、どれもＳｉではない１つのシンボルを各サーバから検索しなければならない。したがって、ユーザは、ｌ個のシンボルを入手し、局所復号によってＳｉを計算することができる。検索されたシンボルは、ランダムではなく、復号アルゴリズムに従って選択され、これは、Ｓｉを計算できるためにシンボルＳｊ１，...，Ｓｊｌを検索しなければならないことを示している。所定のシンボルを常に検索できることを確実にするために、既存のプロトコルは、全てのサーバに全てのシンボルを格納しており、これは、長さＮの符号語全体がｌ回複製されることを意味する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
解決すべき技術的課題は、クエリを明らかにすることなく、特に情報をサーバまたはクラウドに明らかにすることなく、ユーザが情報をデータベースから照会する可能性を提供し、現在のソリューションの格納オーバーヘッドを減少させながら、複数のアウトソーシングされた格納エンティティまたはクラウドにおけるドキュメント群またはデータベース群の格納を可能にすることである。
【課題を解決するための手段】
【０００６】
この目的は、請求項１の主題によって、本発明のおかげで達成される。
本発明の他の特徴、目的および利点は、添付の図面を参照する以下の詳細な説明の随所に見られるであろう。
【図面の簡単な説明】
【０００７】
【図１】本発明の実施例に係るストレージおよびクエリ構成を示す。
【図２】図２ａおよび図２ｂは本発明の実施例に係るクエリおよび超平面を示す。
【発明を実施するための形態】
【０００８】
添付の図面には、ｎ個の要素Ｅ１，...，Ｅｎで構成されるデータベースが示されている。
【０００９】
したがって、本実施例では、Ｎ／（ｌ＋１）個のシンボルのみが各サーバに格納され、そのため合計Ｎ個のシンボルが格納され、復号アルゴリズムに対してさらなる小さな制約が課されて、各サーバから１つのシンボルを必要とすることを確実にするように、シンボルは構成および配置される。より正確には、符号語シンボルまたは符号化されたデータベースは、濃度ｌ＋１の有限体にわたるｍ次元ベクトル空間に属する。この空間における超平面は、（ｍ−１）次元部分空間である。（ｌ＋１）個の超平面にシンボルを配置し、ユーザまたはクライアントまたはクエリアまたは恐らくブローカは、当該超平面の方向を横断する、すなわち当該超平面の方向に平行でない方向の線に従ってシンボルを要求するであろう。それがｌ＋１だけストレージオーバーヘッドを減少させるという利点が主に重要である。
【００１０】
（ｌ，ｄ）−局所復号可能符号は、符号化されたデータのｄ個のシンボルの一部が破損していても依然として２／３よりも大きな確率で復号が後に続くように、恐らく破損した符号化のｌ個のランダムに選択された座標のみを調べることによってメッセージの特定のシンボルを確率的に検索することを可能にする。このとき、ｌは符号の局所性である。
【００１１】
添付の図面では、クライアントまたはユーザまたは顧客は、参照符号Ｃで示されている。ストレージプロバイダ、例えばクラウドストレージプロバイダは、参照符号ＳＰ１，ＳＰ２...で示されている。クエリアＱは、格納されたデータにアクセスしたいと考える。ブローカＢ１，Ｂ２が示されている。このようなブローカは、必須というわけではないが、その役割は、いくつかのオペレーションを容易にすること、またはＣもしくはＱの代わりにそれらを実行することである。この例では、クライアントＣは、ＳＰ、すなわちＳＰ１，ＳＰ２，ＳＰ３およびＳＰ４に対してアウトソーシングされたデータストレージを有している。クエリアＱは、格納されたデータの一部にアクセスしたいと考える。機密性の理由から、またはプライバシを保護するために、Ｑは、Ｑがどのデータまたは情報にアクセスしたかをＳＰに知ってほしくない。一旦格納されると、ＳＰは、ここでは識別子に基づいてデータを検索するためにＱに対してＡＰＩを提供し、当該識別子は、いくつかのデータベースがある場合にはデータベースの名前のつらなりであり、データベース内の要素のインデックスのつらなりである。ＳＰは、個人情報の検索を可能にするように特定の機構を実行することはなく、ＳＰは、標準的なストレージプロバイダである。例えば実行するタスク次第で、ブローカＢ１，Ｂ２を信頼するエンティティまたは独立したエンティティの構成では、ブローカＢ１，Ｂ２はどちらも信頼される。情報の格納は、ここでは以下の態様で実行される。第１のステップにおいて、クライアントＣは、適切なコード化アルゴリズム、局所復号可能符号、例えば重複度符号（multiplicity codes）を用いて、ｎ個の要素Ｅ１，...，Ｅｎで構成されるデータベースを符号化する。ｎ個の要素のデータベースは、Ｎ個のシンボルＳ１，...，ＳＮ（Ｎ＞ｎ）で符号化される。この第１のステップは、情報をＳＰに明らかにしないという点においてＣによって信頼されなければならない第１のブローカＢ１によっても実行されることができる。ｌは、例えば局所復号可能符号の局所性の値であり、Ｎ個のシンボルは、（ｌ＋１）個のグループに分割され、各グループは、全空間の１つの超平面に対応するシンボルを含み、その結果、グループＧ１，...，Ｇｌ＋１となる。任意に、このオペレーションは、同一の信頼できるブローカＢ１によって実行されてもよい。クライアントＣによって実行されようとブローカＢ１によって実行されようと、このステップの出力は、どのグループの中にシンボルＳｉを見つけることができるかを示す関数またはテーブルＴ１である。添付の図面では、局所復号可能符号は、局所性３を有している。
【００１２】
次いで、シンボルの各グループは、サービスプロバイダＳＰに格納される。ＳＰの選択は、コスト、待ち時間、信頼性などの多くのパラメータに左右され得る。これらの局面を考慮に入れるために、ディスパッチングおよびストレージは、第２のブローカＢ２によって処理され得て、第２のブローカＢ２は、単にグループインデックスとストレージプロバイダとの間のマップを返す必要があるだけである。このマップは、典型的にｌ＋１行のテーブルＴ２で示され、行番号ｉは、Ｇｉに対応するストレージプロバイダを示すなどである。ブローカＢ２は、クライアントＣによって強く信頼される必要はなく、それどころかサービスプロバイダのうちの１つによって提供されるサービスであってもよい。クライアントＣは、その後のステップにおいて結託を回避するためにテーブルＴ２の中の全てのサービスプロバイダＳＰが互いに別個のものであることを単に有利に確認する。
【００１３】
情報のクエリは、ここでは以下の態様で実行される。クエリアＱは、所与のシンボルを検索したい場合、まずデータベースの名前を検索する必要がある。データベースの名前は通常は公知であるが、クライアントＣが自身の情報へのアクセスを制御したい場合には、クライアントＣは、この知識を秘密にするかまたは信頼できるブローカＢ１にこのタスクを委任することによってクエリアにまず許可を要求させ得る。
【００１４】
クエリアは、Ｓｉに関心があるが、復号アルゴリズムによって決定される一組のｌ＋１個のクエリＳｊ１，...，Ｓｊ（ｌ＋１）としてクエリを表現する必要がある。より正確には、クエリアは、ランダムであるが超平面方向に平行でない方向を選択し、次いでクエリしなければならない点Ｓｊ１，...，Ｓｊ（ｌ＋１）を計算する。この計算は、クエリアＱによって信頼されるブローカＢ３によって実行されてもよい。
【００１５】
次いで、クエリアＱまたはブローカＢ３は、Ｔ１を検索して各Ｓｊｉがどのグループに属するかを判断し、Ｔ２を検索して各グループがどこに格納されているかを知る必要がある。次いで、クエリアまたはブローカＢ３は、対応するＳＰからＳｊ１，...，Ｓｊ（ｌ＋１）をフェッチし、それらを局所的に復号して、Ｓｉを検索する。この方法の１つの利点は、当該方法が重複度符号および恐らく任意の局所復号可能符号に基づく任意のＰＩＲスキームとともに機能することである。プロトコルは、クエリアが関心を持っている要素のアイデンティティについての情報を全ての個々のサーバが入手しないことを保証する。当該方法は、既存のソリューションと比較して少なくともｌ＋１だけグローバルストレージオーバーヘッドを分割し、ここでｌは復号方法の局所性である。パラメータを微調整することによって、いくつかのＳＰの欠陥からの回復を可能にすることができ、これは、当該方法が固有のエラー修正機能および障害回復力を特徴とすることを意味する。また、パラメータの微調整は、セキュリティ、すなわちこの場合にはクエリの秘密性を損なうことなくいくつかのＳＰの結託を考慮に入れることを可能にする。ブローカＢ１およびＢ３は、情報をサーバに与えない限り、それぞれＣおよびＱの代わりに計算を実行することができる。ブローカＢ２は、セキュリティの観点から信頼される必要なくＳＰの選択を決定することができるので、興味深い。
【００１６】
シンボルから、特定の復号機構によってオリジナルのドキュメントに戻ることが可能である。
【００１７】
この例のクエリ局面において、クエリアＱは、クエリをブローカＢ３に送信し、それをいくつかのシンボルとして表現し、ブローカＢ１からテーブルＴ１を要求し、ブローカＢ２からテーブルＴ２を要求し、次いで対応するＳＰからシンボルを要求し、対応は、ここではテーブルのおかげで可能である。要求されたシンボルを受け取った後、ブローカＢ３は、それらを局所的に復号し、要求されたシンボルをクエリアＱに戻す。
【００１８】
【数１】
2017511552.tif 000003
【００１９】
【数２】
2017511552.tif 000004
【００２０】
個人情報の検索の問題点は、１９９５年にChor、Goldreich、KushilevitzおよびSudanによって紹介された。ＰＩＲプロトコルは、暗号プロトコルであり、その目的は、ユーザがどの記録を検索したいかをサーバに明らかにすることなくデータベースの特定の記録をクエリすることを可能にする（クエリ匿名性の別名でも知られる）という意味で、サーバを介してパブリックデータベースにアクセスするユーザのプライバシを保護することである。ここでは、算術的に安全なＰＩＲとは対照的に情報理論的ＰＩＲを取り上げる［７］。ＩＴ  ＰＩＲ設定では、サーバは、無限の計算能力を有していたとしても、ユーザが関心を持っている記録のアイデンティティについての情報を入手することはない。［２］には、単一のデータベースにアクセスする際、情報理論的な意味においてユーザのプライバシを完全に保証するために、データベース全体をダウンロードする必要があり、これは、Ｏ（ｎ）の通信複雑性をもたらし、ｎはデータベースのビット長であることが示されている。したがって、彼らは、データベースがいくつかの、例えばｌ個のサーバにわたって複製されるシナリオを紹介し、ｌ≧３の場合に通信複雑性Ｏ（ｎ１／ｌ）であるスキームを提案した。それ以降、このような複数サーバ設定が研究され、これまでの最良の通信複雑性は、以下の通りである。
【００２１】
【数３】
2017511552.tif 000005
【００２２】
KatzおよびTrevisan［５］は、局所復号可能符号に非常に近い概念、すなわち平滑符号の概念を紹介した。平滑符号は、デコーダが同一のインデックスをそれほど頻繁には読出すことができないという考え方を取込む。非公式に、ｌおよびｃが固定される場合、（ｌ，ｃ）−平滑符号では、有効な符号語からせいぜいｌ個のインデックスをクエリするデコーダは、ｃ／ｍ回以上インデックスをクエリすることはできない。［５］には、（ｌ，δ）−ＬＤＣが（ｌ，ｃ＝ｌ／δ）−平滑符号であることが示されている。
【００２３】
符号語（または受取られた語）の座標の中でのクエリの均一な分布は、クエリの情報理論的プライバシを達成するためにＰＩＲ設定において我々がまさに必要としているものである。ＬＤＣの中心的特徴としての局所性は、ＬＤＣの全ての公知の構成では局所復号アルゴリズムＡによってなされるクエリが均一に分布されるという事実とともに、ＰＩＲスキームへのＬＤＣの適用をかなり自然なものにする。以下の補題は、それが公式にいかに機能するかを説明している。
【００２４】
なお、また、ＰＩＲスキームは、最良漸近符号長を有するＬＤＣを構築するために使用されてもよい。実際、［１］において引用されているように、「任意の情報理論的ＰＩＲプロトコルは、関連する効率性のＬＤＣに変換されることができる。」
我々は、長さｋのΔ変数文字列ｘとしてデータベースをモデル化する。ｌ−サーバＰＩＲスキームは、各々が同一のデータベースｘを保持するｌ個のサーバＳ１，...，Ｓｌと、ｋを知っていて、ｉについてのいかなる情報もサーバに明らかにすることなくある値ｘｉ，ｉ∈［ｋ］を検索したいユーザとを含む。
【００２５】
【数４】
2017511552.tif 000006
【００２６】
なお、Yekhanin［８］は、三つ組のアルゴリズム（Ｑ，Ａ，Ｃ）が不均一であり、そのため長さｋがアドバイスとして与えられていると考えている。
【００２７】
各デコーダのクエリが一組の符号語座標に均一に分散されているｌ−クエリ局所復号可能符号Ｃ：Δｋ→Σｎが存在すると仮定する。すると、データベースにアクセスするためのＯ（ｌlog（ｎ｜Σ｜））通信を有するｌ−サーバ１−ＰＩＲプロトコルｘ∈Δｋが存在する。
【００２８】
【数５】
2017511552.tif 000007
【００２９】
【数６】
2017511552.tif 000008
【００３０】
【数７】
2017511552.tif 000009
【００３１】
【数８】
2017511552.tif 000010
【００３２】
【数９】
2017511552.tif 000011
【００３３】
【数１０】
2017511552.tif 000012
【００３４】
【数１１】
2017511552.tif 000013
【００３５】
［６］の復号アルゴリズムは、実際にははるかに複雑であり、より多くのエラーに対処する。しかし、我々の関心事としては、簡略化されたバージョンで十分である。
【００３６】
【数１２】
2017511552.tif 000014
【００３７】
【数１３】
2017511552.tif 000015
【００３８】
なお、局所性符号の局所性は、サーバの数にはマッピングされない。符号はｑσの局所性を有するが、要求されるサーバの数は依然としてｑである。さらに、クエリの数は依然としてｑσであり、各サーバはσ個のクエリを受け取る。
【００３９】
【数１４】
2017511552.tif 000016
【００４０】
【数１５】
2017511552.tif 000017
【００４１】
【数１６】
2017511552.tif 000018
【００４２】
［参照文献］
2017511552.tif 000019
【図１】
2017511552.tif 000020
【図２】
2017511552.tif 000021
【国際調査報告】
2017511552.tif 000022
2017511552.tif 000023