通信効率の良い秘匿情報検索及び紛失通信のための方法及び装置
【課題】データベースから非公開で情報を検索する方法、工業製品、及び装置を開示する。
【解決手段】一実施形態において、該方法は、データベースから検索する情報に対応するインデックスを取得するステップと、データベースに対して検索を明らかにしないクエリを生成するステップを含む。クエリは、インデックスの算術関数と秘密値であり、この算術関数には、素数の冪がランダム値の位数であるように、位数が素数の冪で割り切れるランダム値のモジュラスによって特定される乗法群を含む。秘密値は、モジュラスの素数への因数分解を含むインデックスの算術関数である。また、該方法は、データベースの全体に対して算術関数を実行するためにクエリをデータベースに通信するプロセスを更に含む。
【解決手段】一実施形態において、該方法は、データベースから検索する情報に対応するインデックスを取得するステップと、データベースに対して検索を明らかにしないクエリを生成するステップを含む。クエリは、インデックスの算術関数と秘密値であり、この算術関数には、素数の冪がランダム値の位数であるように、位数が素数の冪で割り切れるランダム値のモジュラスによって特定される乗法群を含む。秘密値は、モジュラスの素数への因数分解を含むインデックスの算術関数である。また、該方法は、データベースの全体に対して算術関数を実行するためにクエリをデータベースに通信するプロセスを更に含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本特許出願は、２００４年５月２０日に出願された「Ｍｅｔｈｏｄ Ａｎｄ Ａｐｐａｒａｔｕｓ Ｆｏｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｆｆｉｃｉｅｎｔ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ Ａｎｄ Ｏｂｌｉｖｉｏｕｓ Ｔｒａｎｓｆｅｒ」と題した仮出願第６０５７３５７３号に対して優先権を主張する。
【０００２】
本発明は、一般的な暗号論に関し、特に秘匿情報検索及び紛失通信の問題点に関する。
【背景技術】
【０００３】
２人の架空の人物ＡｌｉｃｅとＢｏｂの次のようなシナリオを考えてみる。人物Ｂｏｂは、ｍ個の要素からなるデータベースＤを所有している。ユーザであるＡｌｉｃｅは、このデータベースにアクセスしたいと思っており、そのデータベースにアクセスできるようにＢｏｂと契約を結んでいる。しかしながら、プライバシーの理由から、Ａｌｉｃｅは、自分がデータベース内のどの項目を探索しているのかをＢｏｂに知られたくないと思っている。当然、データベースのプライバシーが望まれる多くのシナリオを想定することができる。
【０００４】
当技術分野では、上記の問題に対処する課題分野が公知であり、本明細書では、その課題分野を「秘匿情報検索（ＰＩＲ：Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ）」と称す。（例えば、ユーザが知るべき情報以上の情報を知ることのないようにすることによる）データベースのプライバシー保持については、当技術分野において、その課題分野について時々言及されており、この明細書においては、「対称型秘匿情報検索（ＳＰＩＲ：Ｓｙｍｍｅｔｒｉｃ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ）」又は「紛失通信（Ｏｂｌｉｖｉｏｕｓ Ｔｒａｎｓｆｅｒ）」として言及する。
【０００５】
プライバシーの目的を実現するための単純なスキームとしては、データベースの所有者（この場合は、Ｂｏｂ）が、データベースの全てをＡｌｉｃｅに送ることである。データベースに、ｍ個のビットが含まれていれば、総通信計算量は、Ｏ（ｍ）である。ここで、目的のためのこの表記は、ａｍ＋ｂを意味する。なお、ａとｂは、数字である。Ａｌｉｃｅは、いかなるクエリをも実行することができ、Ｂｏｂは、単純に、Ａｌｉｃｅのクエリについての情報を全く持たない。もちろん、この解決法は、中位の大きさのデータベースに対してさえ、全くもって非実用的である。また、このタイプのスキームは、データベースのプライバシー保持に対する要求も満たさない。
【０００６】
あるスキームは、データベースの大きさにおいて超対数的である、つまり、Ｏ（（ｌｏｇ２ｍ）ｄ）である総通信量を要求する。ここで、ｍは、データベース内の項目数であり、ｄは、１より大きい。このようなシナリオでの総通信量の理論的下限で、最もよく知られているものが、Ｏ（ｌｏｇ２ｍ）である。
【０００７】
「Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ」（ＡＣＭジャーナル（Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ）、４５巻、１９９８年（旧バーションは、ＦＯＣＧ９５に掲載））において、Ｃｈｏｒ、Ｋｕｓｈｉｌｅｖｉｔｚ、Ｇｏｌｄｒｅｉｃｈ及びＳｕｄａｎは、セキュリティ分析に計算処理による仮定を必要としない情報理論的事例を検討している。
【０００８】
この場合、彼らは、単一データベースを使いさえすれば、ｍビットが通信されるはずであるということを示している。
【０００９】
一方、同一のデータベースの複製を数個使えば（これらのデータベースは互いに通信しないという制限のもと）、ｍビットの送信を必要としないスキームを実現することができる。
【００１０】
データベースが互いに通信しないという制限の下、通信計算量がＯ（ｍ１/３）である２つのデータベース用の秘匿情報検索スキームが存在し、任意の定数ｋ≧２に対して、データベースが互いに通信しないという制限の下、通信計算量がＯ（ｍ１/ｋ）であるｋ個のデータベース用の秘匿情報検索スキームが存在することについて究明している。
【００１１】
「Ｕｐｐｅｒ Ｂｏｕｎｄ ｏｎ ｔｈｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｐｒｉｖｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ」（第２４回ＩＣＡＬＰ予稿集、１９９７年）において、Ａｍｂａｉｎｉｓは、データベースが互いに通信しないという制限の下、任意の定数ｋ≧２に対して、通信計算量が
【数１】
【００１２】
であるｋ個のデータベース用の秘匿情報検索スキームが存在し、同じく、データベースが互いに通信しないという制限の下、任意のｋ＝θ（ｌｏｇｍ）に対して、通信計算量がＯ（ｌｏｇ２ｍ−ｌｏｇｌｏｇｍ）であるθ（ｌｏｇｍ）個のデータベース用の秘匿情報検索スキームが存在することを示している。
【００１３】
「Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ」（第２９回ＳＴＯＣ予稿集、ｐｐ．３０４−３１３、１９９７年）において、Ｃｈｏｒ及びＮ．Ｇｉｌｂｏａは、任意の∈＞０に対して、通信計算量がＯ（ｍ∈）である２つのデータベース用の秘匿情報検索スキームが存在していることを示している。
【００１４】
彼らのスキームでは、疑似ランダムジェネレータの存在が必要となっている。一方向の関数が存在すれば、そのようなジェネレータが構成されることは、当技術分野では公知である。
【００１５】
「Ｒｅｐｌｉｃａｔｉｏｎ ｉｓ ｎｏｔ ｎｅｅｄｅｄ：ｓｉｎｇｌｅ ｄａｔａｂａｓｅ、ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ ｐｒｉｖｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ」（１９９７年ＦＯＣ予稿集、ｐｐ．３６４−３７３）において、Ｋｓｈｉｌｅｖｉｔｚ及びＲ．Ｏｓｔｒｉｃｓｋｙは、計算処理による処理が難しい仮定を用いて、通信計算量がｍより小さい単一（すなわち、ｋ＝１である）データベース用の秘匿情報検索スキームを実現している。
【００１６】
公知の２次余剰仮定（Ｑｕａｄｒａｔｉｃ Ｒｅｓｉｄｕｏｃｉｔｙ ａｓｓｕｍｐｔｉｏｎ）に基づいて、彼らは、任意の∈＞０に対して、通信計算量がＯ（ｍ∈）である単一データベース用の秘匿情報検索スキームが存在することを実証している。
【００１７】
そのようなスキームを構成するために、第１に、彼らは、通信計算量がＯ（（２√ｍ＋１）−ｋ）（但し、ｋは、セキュリティのパラメータ）である基本的なスキームを実証した。
【００１８】
ある定数ｃに対してｋ＝ｍｃであるとの仮定の下、結果として得られるスキームでは、通信計算量
【数２】
【００１９】
を実現している。
【００２０】
次に、Ｋｓｈｉｌｅｖｉｔｚ及びＲ．Ｏｓｔｒｉｃｓｋｙは、このスキームのステップの１つ自体が単一データベース用の秘匿情報検索プロトコルで置換できるとすると、結果として得られる通信計算量が、少なくなるであろうということを実証している。
【００２１】
この考えを使って、彼らは、Ｌを帰納のレベルの数とする通信計算量が
【数３】
【００２２】
である帰納的スキームを提案している。
【００２３】
ある定数ｃに対して、セキュリティのパラメータがｋ＝ｍｃであると仮定し、
【数４】
【００２４】
を設定すると、通信計算量は、ｎＯ（√ｃ）である。
【００２５】
その後、Ｃａｃｈｉｎ、Ｍｉｃａｌｉ、Ｓｔａｄｌｅｒが、「Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ ｗｉｔｈ Ｐｏｌｙｌｏｇａｒｉｔｈｍｉｃ Ｃｏｍｍｕｎｉｃａｔｉｏｎ」（Ｅｕｒｏｃｒｙｐ１９９９年予稿集、ＬＮＣＳ、ｐｐ．４０２−４１４、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）において、データベースの大きさにおいて、通信計算量が、多項式対数関数的である、すなわち、Ｏ（ｌｏｇｄｍ）である単一データベース用の計算処理による秘匿情報検索スキームの構成の仕方を示した。ここで、ｄは、１よりも大きい定数である。
【００２６】
彼らのスキームにおいて推奨されるパラメータは、ｄ＝６であり、これにより、実際の総通信計算量は、Ｏ（ｌｏｇ６ｍ）となる。
【００２７】
Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームは、２つの計算処理による処理が難しい仮定に基づいている。
第１の仮定は、「Φ-ｈｉｄｉｎｇ仮定（Φ-ｈｉｄｉｎｇ ａｓｓｕｍｐｔｉｏｎ）」であり、これは、大雑把にいうと、合成数ｎ及び小さい素数ｐが与えられると、ｐが、１/２よりも無視できない程良い確率で、Φ（ｎ）を割り切れるかどうかについて決めることは難しいというものである。
【００２８】
第２の仮定は、「Φ-ｓａｍｐｌｉｍｇ仮定（Φ-ｓａｍｐｌｉｍｇ ａｓｓｕｍｐｔｉｏｎ）」であり、これは、大雑把にいうと、ｐが、Φ（ｎ）を割り切れるように、ランダムな合成数ｎを効率的に見つけることができるというものである。
【００２９】
ユーザは、ｍビットのデータベースのｉ番目のビットを得るためには、ｉの符号化したものを少なくとも送信しなければならない。よって、いかなるスキームにおいても、Ｏ（ｌｏｇｍ）ビットを通信しなければならない。
【００３０】
しかしながら、（計算量がＯ（ｌｏｇ６ｍ）である）「Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキーム」と、Ｏ（ｌｏｇｍ）という理論的下限との間には、まだ隔たりがある。
【００３１】
Ｃｈａｎｇは、「Ｓｉｎｇｌｅ−Ｄａｔａｂａｓｅ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ ｗｉｔｈ Ｌｏｇａｒｉｔｈｍｉｃ Ｃｏｍｍｕｎｉｃａｔｉｏｎ」（９ｔｈ Ａｕｓｔｒａｌａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ）（ＡＣＩＳＰ ２００４）予稿集、シドニー、オーストラリア、コンピュータサイエンスにおける講義録、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）において、サーバ側の通信計算量がＯ（ｌｏｇｍ）である最初の単一データベースの計算処理による秘匿情報検索スキームを実証している。
【００３２】
このスキームは、ビルディングブロックとして、Ｐａｉｌｌｉｅｒの暗号システムを利用しており、そのため、その暗号システである限り、安全である。
【００３３】
言い換えると、Ｐａｉｌｌｉｅｒの暗号システムは、（上述したＫｕｓｈｉｌｅｖｉｔｚ−Ｏｓｔｒｏｖｓｋｙスキームで使われるものと同じ仮定である）２次余剰仮定の拡張である合成剰余仮定を仮定し、安全であることを示すことができる。
【００３４】
大雑把に言うと、合成剰余仮定は、
【数５】
【００３５】
中のランダムな要素がｎ２を法とするｎ乗根を有するかどうかを決定することが、計算処理によっては難しいということである。
【００３６】
Ｊｕｌｉａｎ Ｓｔｅｍが、単一データベース用の秘匿情報検索の組みたて方法を、Ｐａｉｌｌｉｅｒの暗号システムがその一例となっている意味的に安全な加法同形暗号スキームのほぼ全てから実証しているため、Ｃｈａｎｇのスキームは、特別なケースのスキームである。
【発明の開示】
【発明が解決しようとする課題】
【００３７】
しかしながら、Ｃｈａｎｇのスキームのユーザ側の通信計算量は、Ｏ（ｍ∈・ｌｏｇｍ）であり、これは、総通信計算量がＯ（ｍ∈・ｌｏｇｍ）であることを意味している。
【００３８】
よって、全体の通信計算量の観点から、Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームが、より優れているが、それでもなお、このスキームのＯ（ｌｏｇ６ｍ）の計算量と、理論上の下限であるＯ（ｌｏｇｍ）との間には、著しい隔たりがあった。
【課題を解決するための手段】
【００３９】
一実施形態において、当該方法は、データベースから検索する情報に対応するインデックスを取得するステップと、データベースに対してインデックスを明らかにしないクエリを生成するステップを含む。
【００４０】
クエリは、インデックス及び秘密値の算術関数である。ここで、この算術関数には、素数の冪がランダム値の位数であるように、位数が素数の冪で割り切れるランダム値の法（モジュラス）によって特定される乗法群を含む。秘密値は、法の素数への因数分解を含むインデックスの算術関数である。
【００４１】
また、当該方法は、データベースの全体に対して算術関数を実行するためにクエリをデータベースに通信するステップを更に含む。
【発明の効果】
【００４２】
データベースから非公開で情報を検索する方法、工業製品、及び装置が開示されている。
【発明を実施するための最良の形態】
【００４３】
本発明は、後述する詳細な説明及び本発明の様々な実施形態の添付図によって、より深く理解できるであろう。なお、これらの図は、本発明を特定の実施形態に制限するために用いたものではなく、単に、説明と理解のためのものである。
【００４４】
以下、秘匿情報検索技術を説明する。これらの技術には、安全な秘匿情報検索技術が含まれる。
【００４５】
本発明の実施形態は、クエリを行う側及びデータベースの所有者の計算処理上の要件、及び、これらの当事者が通信を行うチャンネルの帯域幅の要件に関して、効率的である安全な秘匿情報検索のためのスキームを含む。
【００４６】
一実施形態において、ユーザは、自分がどのクエリを要求したかのかをデータベースの所有者に知られることなく、クエリに対する正しい応答を取得できるように、データベースに対してクエリを実行することができる。
【００４７】
別の実施形態においては、データベースの所有者は、自分が知らせてもよいと思うデータベース以上の情報をユーザが知り得ることがないようにすることができる。
【００４８】
これらの実施形態には、通信が、全体としてデータベースの大きさにおいて対数的であるスキームが含まれる。
【００４９】
すなわち、通信計算量が、Ｏ（ｌｏｇ２ｍ）であり、この通信計算量は、これらのスキームの全体の通信計算量と、典型的に実現しようとする理論上の下限であるＯ（ｌｏｇｍ）との範囲に収まる。
【００５０】
換言すると、かかるインタラクションの間に要求される全体の通信量は、Ｏ（ｌｏｇｍ）である。
【００５１】
一実施形態において、クライアントとサーバとの間で通信が発生する。ここでは、クライアントが、Ｏ（ｌｏｇｍ）ビットをサーバに送信し、サーバが、Ｏ（ｌｏｇｍ）ビットをクライアントに送信するものとする。
【００５２】
しかしながら、当業者であれば、本発明は、このような具体的な詳細がなくても実行できることが明らかであろう。別の例においては、本発明を曖昧にすることを防ぐために、公知の構成及び装置を、詳細ではなく、概略図の形式で示している。
【００５３】
以下に続く詳細な説明の幾つかの箇所は、コンピュータメモリ内のデータビットに関する演算のアルゴリズムとシンボリック表現によって表されている。
【００５４】
これらのアルゴリズム的説明及び表現は、データ処理技術における当業者が、自分達の仕事の実体を効率的に当該分野の他の技術者に伝達するために利用する手段である。
【００５５】
ここでのアルゴリズムは、一般的に、所望する結果へ導くステップの自己無撞着シーケンスであると考えられている。これらのステップは、物理量の物理的処理を必要としているものである。
【００５６】
通常、必ずそうであるというわけではないが、これらの量は、記録し、転送し、組み合わせ、比較し、もしくは処理することが可能な電気又は磁気信号の形式をとっている。これらの信号を、ビット、値、要素、シンボル、特徴、用語、数等として参照することが、時によっては、共有して使用するという主な理由のために、都合がよいと証明されることもあった。
【００５７】
しかしながら、これら全ての用語及び同様な用語は、適当な物理量と関連付けられ、これらの物理量に適用された都合のよいラベルにすぎないということに留意されたい。
【００５８】
以下の説明から明らかなように、特に言及していない場合は、本明細書を通して、「処理（ｐｒｏｃｅｓｓｉｎｇ）」、「計算処理（ｃｏｍｐｕｔｉｎｇ）」、「計算（ｃａｌｃｕｌａｔｉｎｇ）」、「決定（ｄｅｔｅｒｍｉｎｉｎｇ）」、「表示（ｄｉｓｐｌａｙｉｎｇ）」等の用語を用いて行う説明では、コンピュータシステム又は同様な電気演算器のアクションやプロセスに言及している。
【００５９】
ここに言うコンピュータシステム又は同様な電気演算器とは、コンピュータシステムのレジスタやメモリ内の物理（電気）量として表されるデータを処理して、コンピュータシステムのメモリやレジスタ、その他の情報記録装置、送信装置、表示装置の内部の物理量として表される他のデータへ変換するものである。
【００６０】
また、本発明は、本明細書の演算を実行する装置にも関する。
【００６１】
この装置は、要求される目的のために特別に構成されてもよく、又は、コンピュータに記憶されているコンピュータプログラムによって選択的に起動又は再構成される汎用型のコンピュータから構成されていてもよい。
【００６２】
このようなコンピュータプログラムは、それに限定されるものではないが、フロッピディスク、光ディスク、ＣＤ−ＲＯＭ、磁気光ディスク、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カード等のあらゆるタイプのディスク、或いは、電気命令を記憶するのに適しており、それぞれがコンピュータシステムのバスに接続されているあらゆるタイプの媒体等のコンピュータで読み取り可能な記憶媒体に記憶されていてもよい。
【００６３】
本明細書に提示したアルゴリズム及び表示は、特定のコンピュータ及び他の装置に本質的に関するものではない。様々な汎用型システムを、本明細書の教示に従ってプログラムと共に利用してもいいし、又は、必要な方法のステップを実行するためにより特化した装置を構成する方が便利かもしれない。
【００６４】
これらの様々なシステムに必要な構成は、以下の説明から明らかになるであろう。また、本発明は、いかなる特定のプログラム言語をも参照せずに、説明している。ここに説明する本発明の教示するものを実装するために、様々なプラグラム言語を使用することができるということが分かるであろう。
【００６５】
機械的に読み取り可能な媒体には、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を記憶又は送信するためのあらゆるメカニズムが含まれる。
【００６６】
例えば、機械的に読み取り可能な媒体には、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気、光、音響、又は、他形式の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等が含まれる。
【００６７】
＜用語の定義＞
以下の説明を通して、ｍは、データベース中の要素の数を表し、ｎは、効率的に因数分解することが難しいとされる合成モジュラスを表す。
【００６８】
話を簡単にするために、データベースの各要素は、単一のビット（０か１）と仮定する。当該技術分野において通常の熟練を有する者が、以下の定義を読めば、本明細書に記載した方法、構成要素、システムが、任意のビット数を取り扱うように（例えば、単純な反復によって）修正することができることがわかるであろう。
【００６９】
また、本明細書の目的のために、いかなる多項式関数ｑ（ｎ）においても、全てのｎ＞ｎ０に対して、ｆ（ｎ）＜１/ｑ（ｎ）となるような値ｎ０が存在するならば、関数ｆ（ｎ）は無視することができる。このように無視できる関数の一例が、ｆ（ｎ）＝１/２ｎである。
【００７０】
ａとｂが、ａ≦ｂとなる２つの整数である場合に、［ａ，ｂ］は、ａ以上ｂ以下の整数の集合を表すものとする。すなわち、［ａ，ｂ］＝｛ｃ∈Ｚ｜ａ≦ｃ≦ｂ｝である。
【００７１】
Ｓが、要素の集合で、Ｄが、Ｓにおいてサンプル化可能な確率分布とすると、分布Ｄに従って集合Ｓから要素ｓを取り出すプロセスを
【数６】
【００７２】
で表す。
【００７３】
多くの暗号化に関する発明の安全性は、特定の計算処理が困難であると仮定されていることに依拠している。
【００７４】
例えば、特定の数を素因数に効率的に分解することが難しい限りにおいて、暗号化が安全であると証明しようとした。
【００７５】
「計算処理上の（ｃｏｍｐｕｔａｔｉｏｎａｌ）」という用語が、このクラスの暗号システム（すなわち、特定の数を素因数に効率的に分解することが難しい限りにおいて安全である暗号システム）を識別するために使用されることがよくある。
【００７６】
したがって、単一データベースの計算処理による秘匿情報検索スキームは、そのスキームの安全性を確立するために、ある種の計算処理上の仮定が必要とされていることを意味している。
【００７７】
当技術分野においては、「情報理論的（ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｅｔｉｃ）」又は「無条件に（ｕｎｃｏｎｄｉｔｉｏｎａｌ）」という用語を、いかなるタイプの仮定をも行わずに、特定の意味のある安全性の定義に数学的に見合っていると考えられるスキームに関連して使用することが多い。
【００７８】
仮定に関しては、１つの仮説が別のものを示唆する場合が多々ある。
【００７９】
典型的には、当技術分野において、このことは、第２の仮定に反するためのメカニズムを、第１の仮定に反するためのメカニズムに変換（当技術分野においては簡約として知られている変換）することによって示されている。
【００８０】
そのような場合において、第１の仮説は、「より強い」と呼ばれ、一方の第２の仮定は、「より弱い」と呼ばれる。一般に、より弱い仮定のほうが好ましい。
【００８１】
＜計算処理による秘匿情報検索（ＣＰＩＲ）＞
本明細書の目的のために、多項式対数関数的単一データベースの計算処理による秘匿情報検索スキームは、以下の定義に従う。
【００８２】
（定義１：多項式対数関数的ＰＩＲ）
Ｄ（・，・，・）、Ｑ（・，・，・）、Ｒ（・，・，・）を効率的なアルゴリズムであるとする。
【００８３】
かかる定義によれば、以下のような定数ａ，ｂ，ｃ，ｄ＞０が存在するならば、（Ｄ，Ｑ，Ｒ）は、完全に多項式対数関数的ＣＰＩＲスキームである。
【００８４】
１．（正確さ） 全てのｍ、全てのｍビットの文字列Ｂ、全てのｉ∈［１，ｍ］、全てのｋに対して、
【数７】
【００８５】
２．（プライバシー） 全てのｍ、全ての（Ｉ，ｊ）∈［１，ｍ］、ｋ＞ｍａｘ（ｋ０，ｌｏｇｂｍ）となるような全てのｋ、全ての２ｃｋ−ゲート回路Ａに対して、
【数８】
【００８６】
ただし、ａ、ｂ、ｃ及びｄは、ＣＰＩＲの基礎の定数を使う。Ｂは、（サーバのコンポーネントに記憶してもよい）データベースの内容を構成し、個別のビットから成る。
【００８７】
Ｄは、データベースからの応答を生成する方法である。ペア（Ｑ，Ｒ）は、それぞれ、クエリ生成方法及び再構築方法を構成する。ｓは、（クエリｑに関連付けられており、クエリｑからのデータベースの応答を「再構築」するために使用される）秘密である。
【００８８】
ｒは、応答であり、ｋは、安全性のパラメータである。一実施形態において、安全性のパラメータｋは、個人個人が希望する安全性のレベルに従って設定され、残りのパラメータは、データベースの特徴（例えば、その大きさ）に基づいて設定される。
【００８９】
多項式対数関数的スキームが、純粋に対数的総通信計算量を持つことを保証するために、ｂ＝１であり、｜ｑ｜及び|ｒ|は、Ｏ（ｋ）である。
【００９０】
＜Φ-ｈｉｄｉｎｇ仮定及びその変形＞
定義される実施形態の安全性を提供することに関連して、多くの仮定がある。これらの仮定は、可変サンプリング分布Ｄに関して定義されている。その後、Ｄの候補である特定のサンプリング方法が与えられる。
【００９１】
（オリジナルのΦ-ｈｉｄｉｎｇ仮定）
（定義２： Φ-ｈｉｄｉｎｇ仮定）
次の２つの条件を満たすようなｅ，ｆ，ｇ，ｈ＞０が存在する。
【００９２】
［［１］］ 全てのｋ＞ｈに対して、全てのｋビットの素数ｐに対して、Ｓ（ｐ）が、ｐに対して「Φ-ｈｉｄｅ」処理を行うランダムなｋｆビットの数
【数９】
【００９３】
を出力するようなサンプリング・アルゴリズムＳ（・）が存在する。
【００９４】
［［２］］ 全てのｋ＞ｈに対して、多項式時間アルゴリズムＣが、
【数１０】
【００９５】
であるようなサンプリングアルゴリズムＳ（・）が存在する。
【００９６】
なお、オリジナルの仮定では、ｋ＞ｈに対するｋビットの素数の集合を使用している。一般化するために、Ｐで表される許容集合の１つの集合について考えてみる。
【００９７】
例えば、許容集合の１つである当該集合が、ある範囲内の奇素数の冪であるとする。次に、オリジナルのΦ-ｈｉｄｉｎｇ仮定において、サンプリングアルゴリズムは、一様にランダムである。
【００９８】
これは、問題を難しくする、ある効率的に計算可能な分布を要求するだけで一般化することができる。そのため、オリジナルの形式は、より強い仮定である。
【００９９】
（定義３：Ｐに対するΦ-ｈｉｄｉｎｇ仮定）
任意のＰ∈Ｐに対して、
【数１１】
【０１００】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１０１】
上記の仮定は、２通りに修正することができる。
【０１０２】
まず、ｐ０がランダムに選択されていないとしても真であるという仮定である。
【０１０３】
そして、安全性を保持するために、モジュラスにおいて必要とされるビットの数がより少ないという仮定である。
【０１０４】
一実施形態では、同じ素数が、それぞれの新たなクエリに対して使用されるので、固定したｐ０に対する安全性が仮定される。一方、Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームでは、各クエリに対する各データベースのビットに対して異なった素数を生成する。
【０１０５】
以下に、定義の形式表現を示す。
【０１０６】
（定義４：（Ｐに対する線形のΦ-ｈｉｄｉｎｇ仮定）
ｎｅｇ（ｋ）をｋにおいて無視できる関数とする。任意のＰ∈Ｐに対して、
【数１２】
【０１０７】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１０８】
（定義５：Ｐに対する強い線形のΦ-ｈｉｄｉｎｇ仮定）
ｎｅｇ（ｋ）をｋにおいて無視できる関数とする。Ｐ∈Ｐ且つ任意のｐ０∈Ｐに対して、
【数１３】
【０１０９】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１１０】
なお、Φ（ｎ）の大きい除数を明らかにすることは、ｎの因数分解を露呈することになりかねない。つまり、ｐ＞ｎ１/４が、Φ（ｎ）の除数であれば、（ｎ；ｐ）が与えられたｎを容易に因数分解できることは、従来技術において公知である。従って、ｆは少なくとも４である。しかし、ｐがこれより小さければ、同様のことは知られていない。
【０１１１】
＜サンプリング分布＞
集合Ｐが与えられると、分布Ｄは、様々なΦ-ｈｉｄｉｎｇ仮定を持つ傾向が強いと定義される。
【０１１２】
一実施形態において、ｎが２つの素数の積であり、Ｄが一様な分布である場合には、Φ-ｈｉｄｉｎｇ仮定は、ｐ＝３に対して適用されない。
【０１１３】
例えば、素数Ｑ１とＱ２に対するｎ＝Ｑ１Ｑ２≡２（ｍｏｄ ３）を仮定してみる。そうすると、Ｑ１とＱ２の一方が、３を法とする１と合同であることが分かる。したがって、３が、Φ（ｎ）＝（Ｑ１−１）（Ｑ２−１）を割ることが明らかである。
【０１１４】
３よりも大きな素数に対して同様な議論が可能である。
【０１１５】
例えば、Ｄが、２つの素数の合成数を
【数１４】
【０１１６】
から一様に引き出すと仮定してみる。
【０１１７】
そうすると、ｐを法とするＤの出力を考慮するだけで、Ｄが、どの集合を引き出したかを識別することができる。
【０１１８】
原則的に、一方の素数は、ｐを法とする１の値に合同であり、他方の素数は、ｐを法とする任意の値（０を除く）に合同になることができるので、第１の集合から引き出された数は、ｐを法とする一様なものとなる。
【０１１９】
しかしながら、第２の集合から引き出される数は、ｐを法とする一様なものではない。この場合、両方の素数は、ｐを法とする［２，ｐ−１］における、ある数と合同である。
【０１２０】
ｐを素数と仮定すると、ａ∈［１，ｐ−１］に対して、そのような２つの素数の積ｎは、ａ≠１であれば、ｎ≡ａ（ｍｏｄ ｐ）を満たす
【数１５】
【０１２１】
の確率があり、ａ＝１であれば、確率は、少し高い
【数１６】
【０１２２】
となる。ｐが、合成数であれば、同じような状況が起こる。
【０１２３】
したがって、一実施形態において、特徴的な利点が無視することができるように分布Ｄが調整される。この目的を実現する１つの解決法は、
【数１７】
【０１２４】
からサンプリングする場合に、上述した一様でない分布に一致するｐを法とする分布でサンプリングするように、分布Ｄを調整することである。これは、先ず一様な分布でサンプリングし、次に或る確率で出力を拒否することで達成することができる。
【０１２５】
＜データベースクエリ、応答、再構築＞
図１は、データベースから非公開で情報を検索するプロセスの一実施形態の流れ図である。
【０１２６】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置などで作動する）ソフトウェアや、又は、その両者の組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアから構成されてもよい。一実施形態において、処理ロジックは、（例えば、コンピュータシステム、移動装置（例えば、携帯電話等）の）クライアント装置の一部である。
【０１２７】
図１を参照すると、データベースから検索される情報に対応するインデックスを取得する処理ロジックによってプロセスが始まる（処理ブロック１０１）。インデックスは、データベース内の特定の場所を特定するアドレスを表している。
【０１２８】
このインデックスを使うことにより、処理ロジックは、インデックスの算術関数であるクエリ及びインデックスの算術関数である秘密値を生成する（処理ブロック１０２）。
【０１２９】
かかる算術関数は、モジュラス及びランダム値を含み、データベースにインデックスを明らかにしないために、インデックスの暗号化を表している。
【０１３０】
秘密値は、モジュラスの素数への因数分解を含む。一実施形態においては、クエリは、Ｏ（ｌｏｇｍ）ビットを含み、ｍは、データベースに記憶されている要素の数と等しい。
【０１３１】
クエリを生成すると、処理ロジックは、データベースの全体に対して算術関数を実行するために、クエリをデータベースに通信する（処理ブロック１０３）。
【０１３２】
その後、処理ロジックは、データベースによる算術関数の実行結果を受け取り（処理ブロック１０４）、その結果を復号する（処理ブロック１０５）。一実施形態においては、データベースとの間で交換する情報の総量は、データベースに記憶されている情報の総量よりも少ない。
【０１３３】
（クエリ生成プロセスの例）
以下、σ：［１；ｍ］→Ｐは、データベースのインデックスの集合を、
【数１８】
【０１３４】
、素数であるｐ’ｊによって与えられる素数の冪の集合へ写像することを表すものとする。ここで、ｐｊは、Ｐにおけるｊ番目の素数の冪である。
【０１３５】
本明細書の目的のために、Ｐ及びσの写像は、クエリア及びデータベースの両方に知られているものと仮定する。
【０１３６】
図２は、クエリを生成するプロセスの一実施形態の流れ図である。
【０１３７】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動する）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。
【０１３８】
一実施形態において、プロセスは、入力値として、多くの値（ｍ，I，ｋ０，P，D，σ）を有する。
【０１３９】
ここで、ｍは、データベース内のビット数であり、ｉ∈［１，ｍ］は、クエリアが興味を持っている事項を表すデータベースのインデックスであり、ｋ０は、より高いセキュリティを提供するために大きくすることができるセキュリティのパラメータであり、Ｐは、素数の冪の集合であり、Ｄは、
【数１９】
【０１４０】
に対する分布であり、σは、上述した［１，ｍ］からＰへの写像である。
【０１４１】
図２を参照すると、素数の冪を求めるために、写像をインデックスに論理的に適用する処理ロジックによって、かかるプロセスが開始する（処理ブロック２０１）。一実施形態において、素数の冪は、σ（ｉ）＝Ｐｉ’を計算することにより求められる。
【０１４２】
素数の冪を使って、処理ロジックは、素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、十分に大きいモジュラスを、分布関数により、サンプリングする（処理ブロック２０２）。
【０１４３】
つまり、モジュラスの因数分解を困難にするために、モジュラスは十分に大きい。例えば、一実施形態においては、１０２４ビットは、十分に大きいと考えられるが、それよりも大きいモジュラスを使用してもよい。
【０１４４】
一実施形態において、このことは、
【数２０】
【０１４５】
を生成することにより起こる。
【０１４６】
モジュラスをサンプリングした後、処理ロジックは、モジュラスを法としてとる乗法群において、位数が素数の冪であるランダム値を生成する（処理ブロック２０３）。
【０１４７】
一実施形態においては、ランダム値は、ｐｉ’で割り切れる位数を有するランダムなｘ∈（Ｚ/ｎＺ）＊を生成することによって生成される。
【０１４８】
ランダム値を生成した後に、処理ロジックは、クエリを出力する（処理ブロック２０４）。一実施形態において、クエリｑ＝（ｎ；ｘ）及び秘密ｓは、ｎの因数分解を表している。
【０１４９】
（応答生成プロセスの例）
データベースは、クエリアからクエリを受け取り、それに応答して、クエリアに送信される応答を生成する。図３は、応答を生成するプロセスの一実施形態の流れ図である。
【０１５０】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム又は専用装置等で作動する）ソフトウェアや、又は、それらの組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。処理ロジックは、データベースの一部であってよい。
【０１５１】
一実施形態において、かかるプロセスは、入力値として多くの値（Ｂ，ｎ，ｘ，Ｐ，σ）を有する。
【０１５２】
ここで、Ｂは、ｍビット文字列として閲覧されたデータベースの内容を示し、ｎは、合成モジュラスであり、ｘは、（Ｚ/ｎＺ）＊からの要素であり、Ｐは、素数の冪の集合であり、σは、上述した［１，ｍ］からＰへの写像である。
【０１５３】
図３を参照すると、データベースを複数の群に分割することによって、プロセスが始まる（処理ブロック３０１）。
【０１５４】
一実施形態において、データベースＢは、
【数２１】
【０１５５】
に分割される。ここで、
【数２２】
【０１５６】
である。
【０１５７】
データベースを群に分割した後で、処理ロジックは、データベースの複数の群のそれぞれを整数として表す（処理ブロック３０２）。
【０１５８】
一実施形態において、このことは、各Ｃｉを、数Ｃ’ｉ∈［０，２ｌ−１］として表現することで起こる。つまり、［０，２ｌ−１］内の数を、底２で表記したものとしてＣｉを見る場合に、そのときの数をＣ’ｉと呼ぶ。
【０１５９】
次に、処理ロジックは、上述した各群のインデックスに関連付けられた素数の冪を法とする群のそれぞれの整数表記と合同である整数値を計算処理する（処理ブロック３０３）。
【０１６０】
一実施形態においては、全てのｉに対して、ｅ≡Ｃ’ｉ（ｍｏｄ ｐｉ’）となるような最小の正の整数となるように、ｅを設定することにより、整数値の計算が行われる。
【０１６１】
かかる整数値を使うことにより、処理ロジックは、応答を生成する（処理ブロック３０４）。
【０１６２】
一実施形態において、処理ロジックは、かかる整数値と等しい指数を持つ底の入力値を冪乗し、モジュラス値で算術モジュロ演算を実行することによって、応答を生成する。一実施形態において、応答生成には、応答ｒ＝ｘｅ（ｍｏｄ ｎ）の出力が含まれる。
【０１６３】
この技術の最初の３つの演算は、クエリから独立していることに留意されたい。そのため、本発明の他の実施形態では、これらの３つの演算は、予め計算処理することができる。
【０１６４】
（再構築プロセスの例）
データベースが、クエリへの応答をクエリアに提供した後、クエリアは、応答を検索するために、結果に基づいて再構築を行う。図４は、応答の検索を実行するプロセスの流れ図である。
【０１６５】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム又は専用装置等で作動する）ソフトウェアや、又は、それらの組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。処理ロジックは、データベースの一部であってもよい。
【０１６６】
一実施形態において、かかるプロセスは、入力値として多くの値（ｍ，ｉ，ｎ，ｘ，ｒ）を有する。
【０１６７】
ここで、ｍは、データベース内のビット数であり、ｉ∈［１，ｍ］は、クエリアが興味を持っている事項を表すデータベースのインデックスであり、ｎは、合成モジュラスであり、ｘは、（Ｚ/ｎＺ）＊からの要素であり、ｒは、（Ｚ/ｎＺ）＊における値である。
【０１６８】
図４を参照すると、特定のインデックスに関連付けられた素数の冪によって分割されるモジュラスに適用されるオイラーのファイ関数（Ｅｕｌｅｒ ｔｏｔｉｅｎｔ ｆｕｎｃｔｉｏｎ）と等しい冪まで、第１の入力底を冪乗し、第１の入力底を冪乗した結果に基づくモジュラスを使用するモジュロ演算を実行することによって第１の値を決定するという処理ロジックにより、プロセスが開始される（処理ブロック４０１）。
【０１６９】
一実施形態において、第２の値は、
【数２３】
【０１７０】
を演算処理することにより生成される。
【０１７１】
第１の値を決定した後で、処理ロジックは、素数の冪まで第２の入力底を冪乗し、第１の入力底を冪乗した結果に基づくモジュラスを用いるモジュロ演算を実行することによって、第２の値を決定する（処理ブロック４０２）。
【０１７２】
一実施形態において、第２の値は、
【数２４】
【０１７３】
を演算処理することにより生成される。
【０１７４】
第２の値を決定した後で、処理ロジックは、第１の値と等しい底に対する第２の値の離散対数に基づき、第３の値を算術的に決定する（処理ブロック４０３）。
【０１７５】
一実施形態において、第３の値は、底ｙに対するｚの離散対数（モジュロｎ）であるＣ’ｉを演算処理することにより生成される。
【０１７６】
一度、第３の値が生成されると、処理ロジックは、この第３の値から、クエリに関連付けられた少なくとも１ビットを生成する（処理ブロック４０４）。
【０１７７】
一実施形態において、少なくとも１ビットを生成することには、Ｃ’ｉの（ｉ ｍｏｄ ｌ）ビットであるＢｉの出力を含む。
【０１７８】
＜単一データベースの計算処理的秘匿情報検索のためのクライアント、サーバ及びシステムの実施形態＞
クライアントコンポーネントは、処理ロジックを実行することができる（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型のコンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０１７９】
図５は、クライアントの一実施形態の流れ図である。
【０１８０】
図５を参照すると、クライアントは、クエリを生成して応答を送信する方法を実行することによってデータベースの項目を要求することができる外部ネットワークインターフェイス５０１と、外部ネットワークインターフェイス５０１及びメモリ５０３に連結されたプロセッサ５０２とを備える。
【０１８１】
一実施形態において、プロセッサ５０２は、データベースに対する応答を受け取り、再構築のための方法を適用することができるので、興味のあるデータベースに含まれる項目を取得することができる。
【０１８２】
サーバコンポーネントは、処理ロジックを実行することができる（回路、専用ロジック等の）ハードウェア装置や、（汎用型のコンピュータシステム、又は、専用装置上で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０１８３】
図６は、クライアントの一実施形態の流れ図である。
【０１８４】
図６を参照すると、サーバは、データベースの項目に対する要求を受け取ることのできる外部ネットワークインターフェイス６０１と、外部ネットワークインターフェイス及びメモリに接続されたプロセッサ６０２とを備える。
【０１８５】
かかるプロセッサは、データベースの応答を生成するための方法によって与えられた出力をネットワークに送信する。ここで、第２、第３の入力が、かかる要求から取られる。
【０１８６】
単一データベースの計算処理による秘匿情報検索を提供するクライアントとサーバとの間のデータを通信するシステムについて考えてみる。
【０１８７】
このようなシステムは、データベースクエリを生成し、そのようなクエリを通信ネットワークを通じてサーバに送信し、サーバから通信ネットワークを介して応答を受け取り、興味のあるデータベースの項目を再構成することができるクライアントコンポーネントを備え、サーバコンポーネントは、データベースの応答を生成し、そのような応答を、通信ネットワークを通じてクライアントに送信することができる。
【０１８８】
＜対数的紛失通信＞
紛失通信において、クエリアが情報の単一ビットの検索だけを許可されているという意味で、サーバのプライバシーも保持されている。秘匿情報検索スキームのための本明細書に記載の技術は、紛失通信を提供するために修正することができる。
【０１８９】
一実施形態において、幾分不十分な紛失通信スキームを構成するための一般的な合成パラダイムが、効率的な秘匿情報検索スキームで定義され、効率的な紛失通信スキームが実現する。
【０１９０】
次に、どのようにして上述した既存の秘匿情報検索スキームを、そのような幾分不十分な紛失通信スキームに変換することができるかについて具体的に述べる。
【０１９１】
非効率な紛失通信のコンポーネントは、小さい入力の演算のみを行い、一方で、より効率的な秘匿情報検索コンポーネントは、大きいサイズの入力の演算を行うので、合成パラダイムが機能する。合成パラダイムを適用することにより、対数的総通信を実現する紛失通信スキームが得られる。
【０１９２】
上述した秘匿情報検索の技術によって、クエリアが、（少なくとも）ｌｏｇｍビットを回復することができる。ここで、ｍは、データベースのサイズである。
【０１９３】
このスキームを修正するために、このスキームにより、クエリアは、所与のｌビット（ｌ＝ｌｏｇｍ）ブロックＣｉから単一ビットを回復させることだけができるが、同時に、クエリアが、１つ以上のブロックからビットを回復することも防いでいる。
【０１９４】
以下では、ＯＴｌを、ｌビットの文字列Ｃｉ及びクエリアのクエリｑＯＴｉ，ｊを入力として取得し、応答
【数２５】
【０１９５】
を出力する既存の紛失通信スキームとする。
【数２６】
【０１９６】
という制限を条件として、さまざまな紛失通信スキームを使うことができる。
【０１９７】
一実施形態において、この制限は、紛失通信スキームの通信計算量がＯ（ｌｏｇｍ）であるように使われている。この紛失通信スキームを使うことで、上述した秘匿情報検索スキームの技術を、クエリアが任意のブロックの単一ビットを越えて回復することができないことを保証するように修正してもよい。
【０１９８】
（紛失通信クエリ生成プロセスの例）
図８は、紛失通信クエリ生成方法の一実施形態の流れ図である。
【０１９９】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両者の組み合わせによって構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、流れ図中の演算は、クエリアによって実行される。
【０２００】
図８を参照すると、このプロセスは、データベースＢ中のデータベースビットを素数の冪に写像する処理ロジックによって開始される（処理ブロック８０１）。このことは、上述したものと同様に起こる。但し、例外は、（底の素数は同じであっても）素数の冪がオリジナルのものより小さい、又は、大きい可能性があるということである。
【０２０１】
一実施形態において、各素数の冪は（各素数の冪が２ｌより大きくなくてはならないことにもともと反して）２ｍａｘ｛ｒｉ｝より大きいので、データベースの応答は、劣化なしに暗号化することができる。
【０２０２】
次に、クエリアにおける処理ロジックは、適当な素数の冪ｐｉ及びジェネレータｘに対して「Φ-ｈｉｄｅ」処理を行うモジュラスｎを生成する（処理ブロック８０２）。
【０２０３】
これにより、データベースのビットＣｉのｊ番目のビット、ブロックＣにおけるｊ∈［１，ｌ］に、クエリアが興味を持っていることを推測することができる。
【０２０４】
その後、クエリアの処理ロジックは、（任意の文字列Ｃｉに対して）データベースの紛失通信応答
【数２７】
【０２０５】
により、クエリアが、Ｃｉｊを回復できるように、ｊ∈［１，ｌ］におけるインデックスを暗号化する紛失通信クエリ
【数２８】
【０２０６】
を生成する（処理ブロック８０３）。
【０２０７】
（紛失通信応答生成プロセスの例）
図９は、紛失通信クエリ生成プロセスの一実施形態の流れ図である。
【０２０８】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両者の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。 一実施形態において、流れ図中の演算は、データベースによって実行される。
【０２０９】
図９を参照すると、このプロセッサは、全てのｉに対して、ｅ≡ｒｉｊ（ｍｏｄ ｐｉ）であるようなｅを計算処理する処理ロジックによって開始される（処理ブロック９０１）。
【０２１０】
次に、処理ロジックは、値ｘｅ（ｍｏｄ ｎ）を計算し（処理ブロック９０２）、そして、この値をクエリアに送信する（処理ブロック９０３）。
【０２１１】
（紛失通信再構築プロセスの例）
図１０は、紛失通信応答検索のプロセスの一実施形態の流れ図である。
【０２１２】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１０に記載されている演算は、クエリアによって実行される。
【０２１３】
プロセッサは、図１０を参照すると、ｒｉｊを回復する処理ロジックによって開始される（処理ブロック１００１）。
【０２１４】
一実施形態において、処理ロジックは、秘匿情報検索の再構築プロセスにおいてＣｉを回復するのと同様の方法で回復を実行する。
【０２１５】
ｒｉｊを回復した後に、処理ロジックは、ビットＣｉｊを紛失通信応答ｒｉｊから回復する（処理ブロック１００２）。
【０２１６】
（紛失通信プロセスの分析）
上記のやり方によって、クエリアが、任意の単一ブロックＣｉから１ビットを越えて回復することはできないことを保証されるが、クエリアが、１つ以上のブロックから１ビットを回復することができないことを保証するものではない。
【０２１７】
例えば、クエリアは、２つの素数の冪ｐｉ１及びｐｉ２に対して「Φ-ｈｉｄｅ」処理を行うように、ｎを選択することができ、この場合、上述したデータベースの紛失通信の補足された応答によって、２つのデータベースビット、つまり、Ｃｉ１ｊとＣｉ２ｊが、クエリアに与えられる。
【０２１８】
この問題に対処するため、一実施形態において、データベースは、クエリアが、ｎにおいて、２以上の素数の冪に対して「Φ-ｈｉｄｅ」処理を行うことから恩恵を受けることができないことを保証するために、この技術を使う。
【０２１９】
議論のために、Φ（ｎ）が、１つの素数の冪ｐｉだけによって割り切れ、残りに対して互いに素であることを確認することができるデータベースを想定してみる。
【０２２０】
また、ｅ’が、ｐｉを法とするｒｉｊと合同である最も小さい整数であり、（上記スキームで設定したように）ｅ＝ｅ’と設定する代わりに、データベースが、適当に大きい範囲（例えば、［１，ｎ２］）から乱数ｚを選び、
【数２９】
【０２２１】
を設定し、ｘｅ（ｍｏｄ ｎ）をクエリアに送信する場合を考えてみる（この方法で選択された場合、ｅは、必要なモジュール方式の等式をまだ満たしていることに注意されたい）。
【０２２２】
このシナリオにおいて、ｐｉ２が、Φ（ｎ）に対して互いに素であれば、クエリアは、値Ｃｉ２ｊについて何らかの情報を取得することができるかどうかの問いに関して、たとえ境界のない計算処理上の素数を有し、データベースの他の全てのビットを知っていたとしても、クエリアは、せいぜい無視できる程の情報を得られ程度であるというのが答えである。
【０２２３】
なぜならば、クエリアが、Ｃｉ２ｊに関して取得可能な唯一の情報は、ｅに埋め込まれているためである。特に、クエリアが、ｅについて引き出せる唯一の情報は、以下の通りである。
【０２２４】
１． Φ（ｎ）を法とするｅの値（クエリアは、難しい課題ではあるが、底ｘに対してｘｅの離散対数を計算処理することによって、この値を回復することができる）
２．
【数３０】
【０２２５】
に対して、
【数３１】
【０２２６】
である。ここで、Ｃｉｊ＝０ならば、ｅ’＝ｅ’０であり、Ｃｉｊ＝１ならば、ｅ’＝ｅ’１である（これは、データベースが、ｅを計算処理する方法なので、クエリアは、このことを知っている）。
【０２２７】
そこで、問題は、クエリアが、
【数３２】
【０２２８】
の２つの確率のうち、どちらが真であるかを見分けることができるかどうかである。答えは、（無視できる程度の利点を除き、）できない、である。
【０２２９】
なぜならば、２つの事象の条件付き確率（クエリアのｅについての情報に関する条件）は、無視できるためである。
【０２３０】
ｅΦ（ｎ）＝ｅ ｍｏｄ Φ（ｎ）を設定すると、ｚ∈［１，ｎ２］に対して、
【数３３】
【０２３１】
を満たすｅの
【数３４】
【０２３２】
の可能値のどちらか一方が存在する。
【０２３３】
状況は、等式、すなわち、ｚ∈［１，ｎ２］に対して、
【数３５】
【０２３４】
の第２の集合に対して同じである。
【０２３５】
したがって、条件付き確率同士の差は、せいぜい
【数３６】
【０２３６】
であり、これは、無視できるものであることを検証することができる。
【０２３７】
一実施形態において、ユーザは、Φ（ｎ）が、素数の冪ｐｉのうち、１つだけによって割り切れ、残りに対して互いに素であるように、ｎを選択する。
【０２３８】
なお、クエリアが、不正を行わなければ（そして、Φ（ｎ）が、Φ（ｎ）を割り切る１つ（ｐｉ）を除く全ての素数の冪に対して互いに素であれば）、Ｚ/ｎＺの任意の数が、ｎを法とする固有の
【数３７】
【０２３９】
乗根を持つことになることに留意されたい。
【０２４０】
しかしながら、ユーザが、不正を行った場合（根が存在するならば）、その根は、固有ではなくなる。
【０２４１】
そのため、不正を防止するため、不正を行わない者は、計算処理を行うことができるが、不正を行う者は、計算処理を行うことができない固有の
【数３８】
【０２４２】
乗根から生成される疑似ランダム系列で、データベースが、ブロックＣｉのビットをマスクする（そして、オリジナルのＣｉではなく、このマスクされた文字列からｒｉｊを生成する）
一実施形態において、全体的に改良した紛失通信スキームの方法について以下に説明する。
【０２４３】
（紛失通信のためのクエリ生成プロセスの他の実施形態）
一実施形態において、紛失通信クエリ生成のためのクエリ生成プロセスは、上述したプロセスと同じである。
【０２４４】
（応答生成プロセスの他の実施形態）
図１１は、応答生成プロセスの他の実施形態の流れ図である。
【０２４５】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１１に記載される演算は、データベースよって実行される。
【０２４６】
図１１を参照すると、このプロセスは、乱数ｙ∈（Ｚ/ｎＺ）＊を生成するロジックを処理する処理ロジックによって開始され、
【数３９】
【０２４７】
を設定する（処理ブロック１１０１）。
【０２４８】
各ブロックＣｉに対して、処理ロジックは、ｙｉ＝ｙｐｉ（ｍｏｄ ｎ）を設定し、
【数４０】
【０２４９】
を設定し、そして、ｒｉｊ＝ＯＴｌ（Ｃ’ｉ；ｑＯＴ，ｌ）を設定する（処理ブロック１１０２）。
【０２５０】
そして、処理ブロックは、乱数ｚ∈［１，ｎ２］（又は、他の適当な範囲において）を生成する（処理ブロック１１０３）。
【０２５１】
その後、処理ブロックは、任意のｉに対して、ｅ’＝ｒｉｊ（ｍｏｄ ｐｉ）を満たす最小の正の整数となるｅ’を設定し、
【数４１】
【０２５２】
を設定し（処理ブロック１１０４）、そして、ｒ＝ｘｅ（ｍｏｄ ｎ）とする応答（Ｙ，ｙ）を送信する（処理ブロック１１０５）。
【０２５３】
図１２は、紛失通信応答検索の他の実施形態の流れ図である。
【０２５４】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１２に記載する演算は、クエリアによって実行される。
【０２５５】
図１２を参照すると、このプロセスは、上述した標準的なメカニズム、すなわち、Φ（ｎ）/ｐｉによって冪乗し、関連する離散対数を計算するメカニズムを使って、ｒｉｊを回復する処理ブロックによって開始される（処理ブロック１２０１）。
【０２５６】
ｒｉｊを使って、処理ロジックは、Ｃ’ｉのｊ番目のビットを回復する（処理ブロック１２０２）。
【０２５７】
そして、処理ロジックは、ｎを法とするＹの固有の
【数４２】
【０２５８】
乗根として、ｙｉを回復する（処理ブロック１２０３）。
【０２５９】
最後に、処理ロジックは、Ｃｉ’ｊとＨ（ｙｉ）から、Ｃｉｊを計算する（処理ブロック１２０４）。
【０２６０】
結果として得られるビットが予測不可能であるということが、関数Hから必要とされる唯一の安全性のプロパティである。この目的を実現するための数多くの方法が、当業者には公知である。このような方法には、ハードコアビットや、ＳＨＡ-１等の安全な暗号化ハッシュ関数、強秘匿暗号化スキーム当を使用することが含まれるが、これらに限定されるものではない。
【０２６１】
（紛失通信クライアントの例）
紛失通信クライアントのコンポーネントは、処理ロジックを実行可能な、（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置、又は、その両方の組み合わせであってよい。
【０２６２】
一実施形態において、このコンポーネントは、図５のクライアントコンポーネントと同様なコンポーネントを有する。例えば、コンポーネントは、データベースの項目に対する要求がなされる外部ネットワークインターフェイスから構成されている。
【０２６３】
しかしながら、紛失通信クライアントは、紛失通信クエリを生成して応答を送信する方法を実行することによってそれを行う。
【０２６４】
コンポーネントは、外部ネットワークインターフェイス及びメモリに接続されたプロセッサを更に備える。
【０２６５】
プロセッサは、紛失通信データベースに対する応答を受け取り、データベースに含まれる興味のある項目を取得するために、再構築プロセスを適用することができる。
【０２６６】
紛失通信サーバのコンポーネントは、上述した処理を実行可能な、（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０２６７】
一実施形態において、コンポーネントは、図６のクライアントコンポーネントと同様なコンポーネントを有する。
【０２６８】
例えば、サーバコンポーネントは、データベースの項目に対する要求を受け取る外部ネットワークインターフェイスを備える。
【０２６９】
また、コンポーネントは、外部ネットワークインターフェイス及びメモリに接続されたプロセッサを更に備える。
【０２７０】
プロセッサは、紛失通信データベースの応答を生成するプロセスによって与えられる出力をネットワークへ送信する。ここで、第２及び第３の入力は、かかる要求から取得される。
【０２７１】
＜単一データベースの計算処理による秘匿情報検索のためのシステム＞
システムの一実施形態では、単一データベースの紛失通信を提供するために、クライアントとサーバとの間で、データを通信する。
【０２７２】
一実施形態において、システムは、紛失通信データベースクエリが可能で、そのようなクエリを通信ネットワーク上でサーバに送信することができ、サーバから通信ネットワークを介して紛失通信応答が可能であり、データベースの興味がある項目を再構築することができる紛失通信応答クライアントコンポーネントを含む。
【０２７３】
一実施形態において、サーバコンポーネントは、データベース応答を生成し、そのような応答を通信ネットワーク上でクライアントに送信する。
【０２７４】
＜紛失通信を実現するための入れ子秘匿情報検索方法＞
上述の秘匿情報検索スキームを使うことで、非効率的な紛失通信スキームが構築されることがある。
【０２７５】
この非効率的なスキームが、本明細書に記載されている秘匿情報検索からなる場合、その結果として得られるスキームは、効率的な秘匿情報検索スキームである。
【０２７６】
「非効率な」紛失通信スキームは、小さい入力値を演算するだけであり、一方、効率的な秘匿情報検索スキームは、大きい入力値を演算するので、その構成は効率的である。
【０２７７】
スキームは、秘匿情報検索スキームの修正であり、ｍと等しくなるように値ｌが選択されている。
【０２７８】
この場合、結果として得られるデータベースは、それぞれ１ビットを構成するｍブロックに分割される。
【０２７９】
上述したように、不正を行わない者は、計算処理を行うことができ、不正を行う者は、それができない固有の
【数４３】
【０２８０】
乗根から生成される疑似ランダム系列を使って各値がマスクされる。
【０２８１】
上述の紛失通信スキームは、クエリアが、モジュラー根を計算するので、クエリアに対して、（秘匿情報検索スキームのように、Ｏ（√ｍ）の計算ではなく）、Ｏ（ｍ）の計算を持つ。
【０２８２】
しかしながら、入れ子秘匿情報検索スキームという当技術分野において公知の技術を使うことで、因数ｆｃ−１（但し、ｆは、（ｌｏｇｎ）/｜Ｐの最小許容値を表す定数）により、スキームの通信計算量を増加させるという犠牲を払って、ユーザによる計算Ｏ（ｍ１/ｃ）を得ることができる。
【０２８３】
本明細書に記載されているプロセスは、紛失ファイル通信を実現するために拡張することもできる。
【０２８４】
クエリアが、データベースからのファイルを欲しており、データベースが、ユーザにクエリ毎に１ファイルまでと制限したいというシナリオを例とする。
【０２８５】
各ファイルを、（各ｌビット列ではなく）素数の冪に関連付けることより、ビット単位の解決策よりも効率的な解決策を構成することが可能である。長いファイルは、定数因数の暗号文展開だけで紛失通信することができる。
【０２８６】
（コンピュータシステムの一実施形態）
図１３は、本明細書に説明する１つ以上の演算を実行するコンピュータシステムの一例のブロック図である。
【０２８７】
図１３を参照すると、コンピュータシステムは、クライアント又はサーバのコンピュータシステムを備えていてもよい。
【０２８８】
コンピュータシステムは、通信メカニズム、又は、情報を通信するためのバス、及び、情報を処理するためのバスに連結されたプロセッサを備えている。
【０２８９】
プロセッサには、マイクロプロセッサに限定しないが、例えば、Ｐｅｎｔｉｕｍ、ＰｏｗｅｒＰＣ、Ａｌｐｈａなどのマイクロプロセッサを含んでいる。
【０２９０】
システムは、情報や、プロセッサによって実行される命令を格納するバスに連結されるランダムアクセスメモリ（ＲＡＭ）、又は、他の動的記憶装置（メインメモリと称す）を更に備える。
【０２９１】
また、メインメモリも、プロセッサによる命令を実行している間に、暫定変数、又は、他の中間情報のために使うことができる。
【０２９２】
また、コンピュータシステムも、静的情報やプロセッサに対する命令を記憶するためにバスに接続されている読み取り専用メモリ（ＲＯＭ）、及び／又は、他の静的記憶装置、磁気ディスク、又は、光学ディスク等のデータ記憶装置、及び、それに対応するディスクドライブを備えている。
【０２９３】
データ記憶装置は、情報及び命令を記憶するために、バスに接続されている。
【０２９４】
コンピュータシステムは、ブラウン管ディスプレイ装置（ＣＲＴ）、又は、液晶表示装置（ＬＣＤ）等のコンピュータユーザに情報を表示するためにバスに接続されている表示装置に更に接続されてもよい。
【０２９５】
英数字キー及び他のキーを含む英数字入力装置も、情報及びプロセッサに対するコマンドを選択を通信するために、バスに接続されている。
【０２９６】
他のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、又は、カーソル指示キー等の、指示情報やコマンドの選択をプロセッサに通信し、表示装置上でのカーソルの動きを制御するために、バスに接続されているカーソル制御である。
【０２９７】
バスに連結することができる他の装置は、紙、フィルム、又は、同様のタイプの媒体に、指示、データ、又は、他の情報をプリントとするために使うことのできるハードコピー装置である。
【０２９８】
また、スピーカー、及び／又は、マイク等の音声録音再生装置も、コンピュータシステムと音声でインターフェイスするために、オプションとしてバスに接続してもよい。
【０２９９】
バスに接続してもよい他の装置は、電話、又は、手のひらサイズの携帯装置と通信する有線／無線の通信機能である。
【０３００】
なお、システムの任意の、又は、全てのコンポーネント、及び、関連するハードウェアを本発明に使用してもよいことに留意されたい。
【０３０１】
しかしながら、コンピュータシステムの他の構成には、上記の装置の中のいくつかの装置又は全ての装置を含んでも良いということを理解することができる。
【０３０２】
上述の説明を読めば、本発明の変更や修正が、当該技術分野において通常の熟練を有する者には明らかとなるであろうが、図を使って表し説明した、いかなる特定の実施形態も、本発明を制限するものと考えられるようには意図されていないことを理解すべきである。
【０３０３】
よって、様々な実施形態の詳細を参照することは、本発明にとって必要不可欠であると見なされる特徴だけを詳述する請求項の範囲を制限するように意図するものではない。
【図面の簡単な説明】
【０３０４】
【図１】データベースから情報を非公開に検索するプロセスの一実施形態の流れ図である。
【図２】クエリ生成プロセスの一実施形態の流れ図である。
【図３】応答生成プロセスの一実施形態の流れ図である。
【図４】応答検索プロセスの流れ図である。
【図５】クライアントコンポーネントの一実施形態を示す。
【図６】サーバコンポーネントの一実施形態を示す。
【図７】クライアントコンポーネントを有するシステム構成の一実施形態を示す。
【図８】紛失通信クエリ生成方法の一実施形態の流れ図である。
【図９】紛失通信クエリ生成プロセスの一実施形態の流れ図である。
【図１０】紛失通信応答検索プロセスの一実施形態の流れ図である。
【図１１】応答生成プロセスの他の実施形態の流れ図である。
【図１２】紛失通信応答検索プロセスの他の実施形態の流れ図である。
【図１３】コンピュータシステムの一実施形態の例を示す。
【符号の説明】
【０３０５】
５０１、６０１…ネットワークインターフェイス
５０２、６０２…プロセッサ
５０３、６０３…メモリ（暗号鍵）
【技術分野】
【０００１】
本特許出願は、２００４年５月２０日に出願された「Ｍｅｔｈｏｄ Ａｎｄ Ａｐｐａｒａｔｕｓ Ｆｏｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｆｆｉｃｉｅｎｔ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ Ａｎｄ Ｏｂｌｉｖｉｏｕｓ Ｔｒａｎｓｆｅｒ」と題した仮出願第６０５７３５７３号に対して優先権を主張する。
【０００２】
本発明は、一般的な暗号論に関し、特に秘匿情報検索及び紛失通信の問題点に関する。
【背景技術】
【０００３】
２人の架空の人物ＡｌｉｃｅとＢｏｂの次のようなシナリオを考えてみる。人物Ｂｏｂは、ｍ個の要素からなるデータベースＤを所有している。ユーザであるＡｌｉｃｅは、このデータベースにアクセスしたいと思っており、そのデータベースにアクセスできるようにＢｏｂと契約を結んでいる。しかしながら、プライバシーの理由から、Ａｌｉｃｅは、自分がデータベース内のどの項目を探索しているのかをＢｏｂに知られたくないと思っている。当然、データベースのプライバシーが望まれる多くのシナリオを想定することができる。
【０００４】
当技術分野では、上記の問題に対処する課題分野が公知であり、本明細書では、その課題分野を「秘匿情報検索（ＰＩＲ：Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ）」と称す。（例えば、ユーザが知るべき情報以上の情報を知ることのないようにすることによる）データベースのプライバシー保持については、当技術分野において、その課題分野について時々言及されており、この明細書においては、「対称型秘匿情報検索（ＳＰＩＲ：Ｓｙｍｍｅｔｒｉｃ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ）」又は「紛失通信（Ｏｂｌｉｖｉｏｕｓ Ｔｒａｎｓｆｅｒ）」として言及する。
【０００５】
プライバシーの目的を実現するための単純なスキームとしては、データベースの所有者（この場合は、Ｂｏｂ）が、データベースの全てをＡｌｉｃｅに送ることである。データベースに、ｍ個のビットが含まれていれば、総通信計算量は、Ｏ（ｍ）である。ここで、目的のためのこの表記は、ａｍ＋ｂを意味する。なお、ａとｂは、数字である。Ａｌｉｃｅは、いかなるクエリをも実行することができ、Ｂｏｂは、単純に、Ａｌｉｃｅのクエリについての情報を全く持たない。もちろん、この解決法は、中位の大きさのデータベースに対してさえ、全くもって非実用的である。また、このタイプのスキームは、データベースのプライバシー保持に対する要求も満たさない。
【０００６】
あるスキームは、データベースの大きさにおいて超対数的である、つまり、Ｏ（（ｌｏｇ２ｍ）ｄ）である総通信量を要求する。ここで、ｍは、データベース内の項目数であり、ｄは、１より大きい。このようなシナリオでの総通信量の理論的下限で、最もよく知られているものが、Ｏ（ｌｏｇ２ｍ）である。
【０００７】
「Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ」（ＡＣＭジャーナル（Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ）、４５巻、１９９８年（旧バーションは、ＦＯＣＧ９５に掲載））において、Ｃｈｏｒ、Ｋｕｓｈｉｌｅｖｉｔｚ、Ｇｏｌｄｒｅｉｃｈ及びＳｕｄａｎは、セキュリティ分析に計算処理による仮定を必要としない情報理論的事例を検討している。
【０００８】
この場合、彼らは、単一データベースを使いさえすれば、ｍビットが通信されるはずであるということを示している。
【０００９】
一方、同一のデータベースの複製を数個使えば（これらのデータベースは互いに通信しないという制限のもと）、ｍビットの送信を必要としないスキームを実現することができる。
【００１０】
データベースが互いに通信しないという制限の下、通信計算量がＯ（ｍ１/３）である２つのデータベース用の秘匿情報検索スキームが存在し、任意の定数ｋ≧２に対して、データベースが互いに通信しないという制限の下、通信計算量がＯ（ｍ１/ｋ）であるｋ個のデータベース用の秘匿情報検索スキームが存在することについて究明している。
【００１１】
「Ｕｐｐｅｒ Ｂｏｕｎｄ ｏｎ ｔｈｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｐｒｉｖｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ」（第２４回ＩＣＡＬＰ予稿集、１９９７年）において、Ａｍｂａｉｎｉｓは、データベースが互いに通信しないという制限の下、任意の定数ｋ≧２に対して、通信計算量が
【数１】
【００１２】
であるｋ個のデータベース用の秘匿情報検索スキームが存在し、同じく、データベースが互いに通信しないという制限の下、任意のｋ＝θ（ｌｏｇｍ）に対して、通信計算量がＯ（ｌｏｇ２ｍ−ｌｏｇｌｏｇｍ）であるθ（ｌｏｇｍ）個のデータベース用の秘匿情報検索スキームが存在することを示している。
【００１３】
「Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ」（第２９回ＳＴＯＣ予稿集、ｐｐ．３０４−３１３、１９９７年）において、Ｃｈｏｒ及びＮ．Ｇｉｌｂｏａは、任意の∈＞０に対して、通信計算量がＯ（ｍ∈）である２つのデータベース用の秘匿情報検索スキームが存在していることを示している。
【００１４】
彼らのスキームでは、疑似ランダムジェネレータの存在が必要となっている。一方向の関数が存在すれば、そのようなジェネレータが構成されることは、当技術分野では公知である。
【００１５】
「Ｒｅｐｌｉｃａｔｉｏｎ ｉｓ ｎｏｔ ｎｅｅｄｅｄ：ｓｉｎｇｌｅ ｄａｔａｂａｓｅ、ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ ｐｒｉｖｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ」（１９９７年ＦＯＣ予稿集、ｐｐ．３６４−３７３）において、Ｋｓｈｉｌｅｖｉｔｚ及びＲ．Ｏｓｔｒｉｃｓｋｙは、計算処理による処理が難しい仮定を用いて、通信計算量がｍより小さい単一（すなわち、ｋ＝１である）データベース用の秘匿情報検索スキームを実現している。
【００１６】
公知の２次余剰仮定（Ｑｕａｄｒａｔｉｃ Ｒｅｓｉｄｕｏｃｉｔｙ ａｓｓｕｍｐｔｉｏｎ）に基づいて、彼らは、任意の∈＞０に対して、通信計算量がＯ（ｍ∈）である単一データベース用の秘匿情報検索スキームが存在することを実証している。
【００１７】
そのようなスキームを構成するために、第１に、彼らは、通信計算量がＯ（（２√ｍ＋１）−ｋ）（但し、ｋは、セキュリティのパラメータ）である基本的なスキームを実証した。
【００１８】
ある定数ｃに対してｋ＝ｍｃであるとの仮定の下、結果として得られるスキームでは、通信計算量
【数２】
【００１９】
を実現している。
【００２０】
次に、Ｋｓｈｉｌｅｖｉｔｚ及びＲ．Ｏｓｔｒｉｃｓｋｙは、このスキームのステップの１つ自体が単一データベース用の秘匿情報検索プロトコルで置換できるとすると、結果として得られる通信計算量が、少なくなるであろうということを実証している。
【００２１】
この考えを使って、彼らは、Ｌを帰納のレベルの数とする通信計算量が
【数３】
【００２２】
である帰納的スキームを提案している。
【００２３】
ある定数ｃに対して、セキュリティのパラメータがｋ＝ｍｃであると仮定し、
【数４】
【００２４】
を設定すると、通信計算量は、ｎＯ（√ｃ）である。
【００２５】
その後、Ｃａｃｈｉｎ、Ｍｉｃａｌｉ、Ｓｔａｄｌｅｒが、「Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ ｗｉｔｈ Ｐｏｌｙｌｏｇａｒｉｔｈｍｉｃ Ｃｏｍｍｕｎｉｃａｔｉｏｎ」（Ｅｕｒｏｃｒｙｐ１９９９年予稿集、ＬＮＣＳ、ｐｐ．４０２−４１４、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）において、データベースの大きさにおいて、通信計算量が、多項式対数関数的である、すなわち、Ｏ（ｌｏｇｄｍ）である単一データベース用の計算処理による秘匿情報検索スキームの構成の仕方を示した。ここで、ｄは、１よりも大きい定数である。
【００２６】
彼らのスキームにおいて推奨されるパラメータは、ｄ＝６であり、これにより、実際の総通信計算量は、Ｏ（ｌｏｇ６ｍ）となる。
【００２７】
Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームは、２つの計算処理による処理が難しい仮定に基づいている。
第１の仮定は、「Φ-ｈｉｄｉｎｇ仮定（Φ-ｈｉｄｉｎｇ ａｓｓｕｍｐｔｉｏｎ）」であり、これは、大雑把にいうと、合成数ｎ及び小さい素数ｐが与えられると、ｐが、１/２よりも無視できない程良い確率で、Φ（ｎ）を割り切れるかどうかについて決めることは難しいというものである。
【００２８】
第２の仮定は、「Φ-ｓａｍｐｌｉｍｇ仮定（Φ-ｓａｍｐｌｉｍｇ ａｓｓｕｍｐｔｉｏｎ）」であり、これは、大雑把にいうと、ｐが、Φ（ｎ）を割り切れるように、ランダムな合成数ｎを効率的に見つけることができるというものである。
【００２９】
ユーザは、ｍビットのデータベースのｉ番目のビットを得るためには、ｉの符号化したものを少なくとも送信しなければならない。よって、いかなるスキームにおいても、Ｏ（ｌｏｇｍ）ビットを通信しなければならない。
【００３０】
しかしながら、（計算量がＯ（ｌｏｇ６ｍ）である）「Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキーム」と、Ｏ（ｌｏｇｍ）という理論的下限との間には、まだ隔たりがある。
【００３１】
Ｃｈａｎｇは、「Ｓｉｎｇｌｅ−Ｄａｔａｂａｓｅ Ｐｒｉｖａｔｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ ｗｉｔｈ Ｌｏｇａｒｉｔｈｍｉｃ Ｃｏｍｍｕｎｉｃａｔｉｏｎ」（９ｔｈ Ａｕｓｔｒａｌａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ）（ＡＣＩＳＰ ２００４）予稿集、シドニー、オーストラリア、コンピュータサイエンスにおける講義録、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社）において、サーバ側の通信計算量がＯ（ｌｏｇｍ）である最初の単一データベースの計算処理による秘匿情報検索スキームを実証している。
【００３２】
このスキームは、ビルディングブロックとして、Ｐａｉｌｌｉｅｒの暗号システムを利用しており、そのため、その暗号システである限り、安全である。
【００３３】
言い換えると、Ｐａｉｌｌｉｅｒの暗号システムは、（上述したＫｕｓｈｉｌｅｖｉｔｚ−Ｏｓｔｒｏｖｓｋｙスキームで使われるものと同じ仮定である）２次余剰仮定の拡張である合成剰余仮定を仮定し、安全であることを示すことができる。
【００３４】
大雑把に言うと、合成剰余仮定は、
【数５】
【００３５】
中のランダムな要素がｎ２を法とするｎ乗根を有するかどうかを決定することが、計算処理によっては難しいということである。
【００３６】
Ｊｕｌｉａｎ Ｓｔｅｍが、単一データベース用の秘匿情報検索の組みたて方法を、Ｐａｉｌｌｉｅｒの暗号システムがその一例となっている意味的に安全な加法同形暗号スキームのほぼ全てから実証しているため、Ｃｈａｎｇのスキームは、特別なケースのスキームである。
【発明の開示】
【発明が解決しようとする課題】
【００３７】
しかしながら、Ｃｈａｎｇのスキームのユーザ側の通信計算量は、Ｏ（ｍ∈・ｌｏｇｍ）であり、これは、総通信計算量がＯ（ｍ∈・ｌｏｇｍ）であることを意味している。
【００３８】
よって、全体の通信計算量の観点から、Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームが、より優れているが、それでもなお、このスキームのＯ（ｌｏｇ６ｍ）の計算量と、理論上の下限であるＯ（ｌｏｇｍ）との間には、著しい隔たりがあった。
【課題を解決するための手段】
【００３９】
一実施形態において、当該方法は、データベースから検索する情報に対応するインデックスを取得するステップと、データベースに対してインデックスを明らかにしないクエリを生成するステップを含む。
【００４０】
クエリは、インデックス及び秘密値の算術関数である。ここで、この算術関数には、素数の冪がランダム値の位数であるように、位数が素数の冪で割り切れるランダム値の法（モジュラス）によって特定される乗法群を含む。秘密値は、法の素数への因数分解を含むインデックスの算術関数である。
【００４１】
また、当該方法は、データベースの全体に対して算術関数を実行するためにクエリをデータベースに通信するステップを更に含む。
【発明の効果】
【００４２】
データベースから非公開で情報を検索する方法、工業製品、及び装置が開示されている。
【発明を実施するための最良の形態】
【００４３】
本発明は、後述する詳細な説明及び本発明の様々な実施形態の添付図によって、より深く理解できるであろう。なお、これらの図は、本発明を特定の実施形態に制限するために用いたものではなく、単に、説明と理解のためのものである。
【００４４】
以下、秘匿情報検索技術を説明する。これらの技術には、安全な秘匿情報検索技術が含まれる。
【００４５】
本発明の実施形態は、クエリを行う側及びデータベースの所有者の計算処理上の要件、及び、これらの当事者が通信を行うチャンネルの帯域幅の要件に関して、効率的である安全な秘匿情報検索のためのスキームを含む。
【００４６】
一実施形態において、ユーザは、自分がどのクエリを要求したかのかをデータベースの所有者に知られることなく、クエリに対する正しい応答を取得できるように、データベースに対してクエリを実行することができる。
【００４７】
別の実施形態においては、データベースの所有者は、自分が知らせてもよいと思うデータベース以上の情報をユーザが知り得ることがないようにすることができる。
【００４８】
これらの実施形態には、通信が、全体としてデータベースの大きさにおいて対数的であるスキームが含まれる。
【００４９】
すなわち、通信計算量が、Ｏ（ｌｏｇ２ｍ）であり、この通信計算量は、これらのスキームの全体の通信計算量と、典型的に実現しようとする理論上の下限であるＯ（ｌｏｇｍ）との範囲に収まる。
【００５０】
換言すると、かかるインタラクションの間に要求される全体の通信量は、Ｏ（ｌｏｇｍ）である。
【００５１】
一実施形態において、クライアントとサーバとの間で通信が発生する。ここでは、クライアントが、Ｏ（ｌｏｇｍ）ビットをサーバに送信し、サーバが、Ｏ（ｌｏｇｍ）ビットをクライアントに送信するものとする。
【００５２】
しかしながら、当業者であれば、本発明は、このような具体的な詳細がなくても実行できることが明らかであろう。別の例においては、本発明を曖昧にすることを防ぐために、公知の構成及び装置を、詳細ではなく、概略図の形式で示している。
【００５３】
以下に続く詳細な説明の幾つかの箇所は、コンピュータメモリ内のデータビットに関する演算のアルゴリズムとシンボリック表現によって表されている。
【００５４】
これらのアルゴリズム的説明及び表現は、データ処理技術における当業者が、自分達の仕事の実体を効率的に当該分野の他の技術者に伝達するために利用する手段である。
【００５５】
ここでのアルゴリズムは、一般的に、所望する結果へ導くステップの自己無撞着シーケンスであると考えられている。これらのステップは、物理量の物理的処理を必要としているものである。
【００５６】
通常、必ずそうであるというわけではないが、これらの量は、記録し、転送し、組み合わせ、比較し、もしくは処理することが可能な電気又は磁気信号の形式をとっている。これらの信号を、ビット、値、要素、シンボル、特徴、用語、数等として参照することが、時によっては、共有して使用するという主な理由のために、都合がよいと証明されることもあった。
【００５７】
しかしながら、これら全ての用語及び同様な用語は、適当な物理量と関連付けられ、これらの物理量に適用された都合のよいラベルにすぎないということに留意されたい。
【００５８】
以下の説明から明らかなように、特に言及していない場合は、本明細書を通して、「処理（ｐｒｏｃｅｓｓｉｎｇ）」、「計算処理（ｃｏｍｐｕｔｉｎｇ）」、「計算（ｃａｌｃｕｌａｔｉｎｇ）」、「決定（ｄｅｔｅｒｍｉｎｉｎｇ）」、「表示（ｄｉｓｐｌａｙｉｎｇ）」等の用語を用いて行う説明では、コンピュータシステム又は同様な電気演算器のアクションやプロセスに言及している。
【００５９】
ここに言うコンピュータシステム又は同様な電気演算器とは、コンピュータシステムのレジスタやメモリ内の物理（電気）量として表されるデータを処理して、コンピュータシステムのメモリやレジスタ、その他の情報記録装置、送信装置、表示装置の内部の物理量として表される他のデータへ変換するものである。
【００６０】
また、本発明は、本明細書の演算を実行する装置にも関する。
【００６１】
この装置は、要求される目的のために特別に構成されてもよく、又は、コンピュータに記憶されているコンピュータプログラムによって選択的に起動又は再構成される汎用型のコンピュータから構成されていてもよい。
【００６２】
このようなコンピュータプログラムは、それに限定されるものではないが、フロッピディスク、光ディスク、ＣＤ−ＲＯＭ、磁気光ディスク、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カード等のあらゆるタイプのディスク、或いは、電気命令を記憶するのに適しており、それぞれがコンピュータシステムのバスに接続されているあらゆるタイプの媒体等のコンピュータで読み取り可能な記憶媒体に記憶されていてもよい。
【００６３】
本明細書に提示したアルゴリズム及び表示は、特定のコンピュータ及び他の装置に本質的に関するものではない。様々な汎用型システムを、本明細書の教示に従ってプログラムと共に利用してもいいし、又は、必要な方法のステップを実行するためにより特化した装置を構成する方が便利かもしれない。
【００６４】
これらの様々なシステムに必要な構成は、以下の説明から明らかになるであろう。また、本発明は、いかなる特定のプログラム言語をも参照せずに、説明している。ここに説明する本発明の教示するものを実装するために、様々なプラグラム言語を使用することができるということが分かるであろう。
【００６５】
機械的に読み取り可能な媒体には、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を記憶又は送信するためのあらゆるメカニズムが含まれる。
【００６６】
例えば、機械的に読み取り可能な媒体には、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気、光、音響、又は、他形式の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等が含まれる。
【００６７】
＜用語の定義＞
以下の説明を通して、ｍは、データベース中の要素の数を表し、ｎは、効率的に因数分解することが難しいとされる合成モジュラスを表す。
【００６８】
話を簡単にするために、データベースの各要素は、単一のビット（０か１）と仮定する。当該技術分野において通常の熟練を有する者が、以下の定義を読めば、本明細書に記載した方法、構成要素、システムが、任意のビット数を取り扱うように（例えば、単純な反復によって）修正することができることがわかるであろう。
【００６９】
また、本明細書の目的のために、いかなる多項式関数ｑ（ｎ）においても、全てのｎ＞ｎ０に対して、ｆ（ｎ）＜１/ｑ（ｎ）となるような値ｎ０が存在するならば、関数ｆ（ｎ）は無視することができる。このように無視できる関数の一例が、ｆ（ｎ）＝１/２ｎである。
【００７０】
ａとｂが、ａ≦ｂとなる２つの整数である場合に、［ａ，ｂ］は、ａ以上ｂ以下の整数の集合を表すものとする。すなわち、［ａ，ｂ］＝｛ｃ∈Ｚ｜ａ≦ｃ≦ｂ｝である。
【００７１】
Ｓが、要素の集合で、Ｄが、Ｓにおいてサンプル化可能な確率分布とすると、分布Ｄに従って集合Ｓから要素ｓを取り出すプロセスを
【数６】
【００７２】
で表す。
【００７３】
多くの暗号化に関する発明の安全性は、特定の計算処理が困難であると仮定されていることに依拠している。
【００７４】
例えば、特定の数を素因数に効率的に分解することが難しい限りにおいて、暗号化が安全であると証明しようとした。
【００７５】
「計算処理上の（ｃｏｍｐｕｔａｔｉｏｎａｌ）」という用語が、このクラスの暗号システム（すなわち、特定の数を素因数に効率的に分解することが難しい限りにおいて安全である暗号システム）を識別するために使用されることがよくある。
【００７６】
したがって、単一データベースの計算処理による秘匿情報検索スキームは、そのスキームの安全性を確立するために、ある種の計算処理上の仮定が必要とされていることを意味している。
【００７７】
当技術分野においては、「情報理論的（ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｅｔｉｃ）」又は「無条件に（ｕｎｃｏｎｄｉｔｉｏｎａｌ）」という用語を、いかなるタイプの仮定をも行わずに、特定の意味のある安全性の定義に数学的に見合っていると考えられるスキームに関連して使用することが多い。
【００７８】
仮定に関しては、１つの仮説が別のものを示唆する場合が多々ある。
【００７９】
典型的には、当技術分野において、このことは、第２の仮定に反するためのメカニズムを、第１の仮定に反するためのメカニズムに変換（当技術分野においては簡約として知られている変換）することによって示されている。
【００８０】
そのような場合において、第１の仮説は、「より強い」と呼ばれ、一方の第２の仮定は、「より弱い」と呼ばれる。一般に、より弱い仮定のほうが好ましい。
【００８１】
＜計算処理による秘匿情報検索（ＣＰＩＲ）＞
本明細書の目的のために、多項式対数関数的単一データベースの計算処理による秘匿情報検索スキームは、以下の定義に従う。
【００８２】
（定義１：多項式対数関数的ＰＩＲ）
Ｄ（・，・，・）、Ｑ（・，・，・）、Ｒ（・，・，・）を効率的なアルゴリズムであるとする。
【００８３】
かかる定義によれば、以下のような定数ａ，ｂ，ｃ，ｄ＞０が存在するならば、（Ｄ，Ｑ，Ｒ）は、完全に多項式対数関数的ＣＰＩＲスキームである。
【００８４】
１．（正確さ） 全てのｍ、全てのｍビットの文字列Ｂ、全てのｉ∈［１，ｍ］、全てのｋに対して、
【数７】
【００８５】
２．（プライバシー） 全てのｍ、全ての（Ｉ，ｊ）∈［１，ｍ］、ｋ＞ｍａｘ（ｋ０，ｌｏｇｂｍ）となるような全てのｋ、全ての２ｃｋ−ゲート回路Ａに対して、
【数８】
【００８６】
ただし、ａ、ｂ、ｃ及びｄは、ＣＰＩＲの基礎の定数を使う。Ｂは、（サーバのコンポーネントに記憶してもよい）データベースの内容を構成し、個別のビットから成る。
【００８７】
Ｄは、データベースからの応答を生成する方法である。ペア（Ｑ，Ｒ）は、それぞれ、クエリ生成方法及び再構築方法を構成する。ｓは、（クエリｑに関連付けられており、クエリｑからのデータベースの応答を「再構築」するために使用される）秘密である。
【００８８】
ｒは、応答であり、ｋは、安全性のパラメータである。一実施形態において、安全性のパラメータｋは、個人個人が希望する安全性のレベルに従って設定され、残りのパラメータは、データベースの特徴（例えば、その大きさ）に基づいて設定される。
【００８９】
多項式対数関数的スキームが、純粋に対数的総通信計算量を持つことを保証するために、ｂ＝１であり、｜ｑ｜及び|ｒ|は、Ｏ（ｋ）である。
【００９０】
＜Φ-ｈｉｄｉｎｇ仮定及びその変形＞
定義される実施形態の安全性を提供することに関連して、多くの仮定がある。これらの仮定は、可変サンプリング分布Ｄに関して定義されている。その後、Ｄの候補である特定のサンプリング方法が与えられる。
【００９１】
（オリジナルのΦ-ｈｉｄｉｎｇ仮定）
（定義２： Φ-ｈｉｄｉｎｇ仮定）
次の２つの条件を満たすようなｅ，ｆ，ｇ，ｈ＞０が存在する。
【００９２】
［［１］］ 全てのｋ＞ｈに対して、全てのｋビットの素数ｐに対して、Ｓ（ｐ）が、ｐに対して「Φ-ｈｉｄｅ」処理を行うランダムなｋｆビットの数
【数９】
【００９３】
を出力するようなサンプリング・アルゴリズムＳ（・）が存在する。
【００９４】
［［２］］ 全てのｋ＞ｈに対して、多項式時間アルゴリズムＣが、
【数１０】
【００９５】
であるようなサンプリングアルゴリズムＳ（・）が存在する。
【００９６】
なお、オリジナルの仮定では、ｋ＞ｈに対するｋビットの素数の集合を使用している。一般化するために、Ｐで表される許容集合の１つの集合について考えてみる。
【００９７】
例えば、許容集合の１つである当該集合が、ある範囲内の奇素数の冪であるとする。次に、オリジナルのΦ-ｈｉｄｉｎｇ仮定において、サンプリングアルゴリズムは、一様にランダムである。
【００９８】
これは、問題を難しくする、ある効率的に計算可能な分布を要求するだけで一般化することができる。そのため、オリジナルの形式は、より強い仮定である。
【００９９】
（定義３：Ｐに対するΦ-ｈｉｄｉｎｇ仮定）
任意のＰ∈Ｐに対して、
【数１１】
【０１００】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１０１】
上記の仮定は、２通りに修正することができる。
【０１０２】
まず、ｐ０がランダムに選択されていないとしても真であるという仮定である。
【０１０３】
そして、安全性を保持するために、モジュラスにおいて必要とされるビットの数がより少ないという仮定である。
【０１０４】
一実施形態では、同じ素数が、それぞれの新たなクエリに対して使用されるので、固定したｐ０に対する安全性が仮定される。一方、Ｃａｃｈｉｎ―Ｍｉｃａｌｉ―Ｓｔａｄｌｅｒスキームでは、各クエリに対する各データベースのビットに対して異なった素数を生成する。
【０１０５】
以下に、定義の形式表現を示す。
【０１０６】
（定義４：（Ｐに対する線形のΦ-ｈｉｄｉｎｇ仮定）
ｎｅｇ（ｋ）をｋにおいて無視できる関数とする。任意のＰ∈Ｐに対して、
【数１２】
【０１０７】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１０８】
（定義５：Ｐに対する強い線形のΦ-ｈｉｄｉｎｇ仮定）
ｎｅｇ（ｋ）をｋにおいて無視できる関数とする。Ｐ∈Ｐ且つ任意のｐ０∈Ｐに対して、
【数１３】
【０１０９】
である効率的に計算処理可能な分布Ｄが存在するような定数ｆが存在する。
【０１１０】
なお、Φ（ｎ）の大きい除数を明らかにすることは、ｎの因数分解を露呈することになりかねない。つまり、ｐ＞ｎ１/４が、Φ（ｎ）の除数であれば、（ｎ；ｐ）が与えられたｎを容易に因数分解できることは、従来技術において公知である。従って、ｆは少なくとも４である。しかし、ｐがこれより小さければ、同様のことは知られていない。
【０１１１】
＜サンプリング分布＞
集合Ｐが与えられると、分布Ｄは、様々なΦ-ｈｉｄｉｎｇ仮定を持つ傾向が強いと定義される。
【０１１２】
一実施形態において、ｎが２つの素数の積であり、Ｄが一様な分布である場合には、Φ-ｈｉｄｉｎｇ仮定は、ｐ＝３に対して適用されない。
【０１１３】
例えば、素数Ｑ１とＱ２に対するｎ＝Ｑ１Ｑ２≡２（ｍｏｄ ３）を仮定してみる。そうすると、Ｑ１とＱ２の一方が、３を法とする１と合同であることが分かる。したがって、３が、Φ（ｎ）＝（Ｑ１−１）（Ｑ２−１）を割ることが明らかである。
【０１１４】
３よりも大きな素数に対して同様な議論が可能である。
【０１１５】
例えば、Ｄが、２つの素数の合成数を
【数１４】
【０１１６】
から一様に引き出すと仮定してみる。
【０１１７】
そうすると、ｐを法とするＤの出力を考慮するだけで、Ｄが、どの集合を引き出したかを識別することができる。
【０１１８】
原則的に、一方の素数は、ｐを法とする１の値に合同であり、他方の素数は、ｐを法とする任意の値（０を除く）に合同になることができるので、第１の集合から引き出された数は、ｐを法とする一様なものとなる。
【０１１９】
しかしながら、第２の集合から引き出される数は、ｐを法とする一様なものではない。この場合、両方の素数は、ｐを法とする［２，ｐ−１］における、ある数と合同である。
【０１２０】
ｐを素数と仮定すると、ａ∈［１，ｐ−１］に対して、そのような２つの素数の積ｎは、ａ≠１であれば、ｎ≡ａ（ｍｏｄ ｐ）を満たす
【数１５】
【０１２１】
の確率があり、ａ＝１であれば、確率は、少し高い
【数１６】
【０１２２】
となる。ｐが、合成数であれば、同じような状況が起こる。
【０１２３】
したがって、一実施形態において、特徴的な利点が無視することができるように分布Ｄが調整される。この目的を実現する１つの解決法は、
【数１７】
【０１２４】
からサンプリングする場合に、上述した一様でない分布に一致するｐを法とする分布でサンプリングするように、分布Ｄを調整することである。これは、先ず一様な分布でサンプリングし、次に或る確率で出力を拒否することで達成することができる。
【０１２５】
＜データベースクエリ、応答、再構築＞
図１は、データベースから非公開で情報を検索するプロセスの一実施形態の流れ図である。
【０１２６】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置などで作動する）ソフトウェアや、又は、その両者の組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアから構成されてもよい。一実施形態において、処理ロジックは、（例えば、コンピュータシステム、移動装置（例えば、携帯電話等）の）クライアント装置の一部である。
【０１２７】
図１を参照すると、データベースから検索される情報に対応するインデックスを取得する処理ロジックによってプロセスが始まる（処理ブロック１０１）。インデックスは、データベース内の特定の場所を特定するアドレスを表している。
【０１２８】
このインデックスを使うことにより、処理ロジックは、インデックスの算術関数であるクエリ及びインデックスの算術関数である秘密値を生成する（処理ブロック１０２）。
【０１２９】
かかる算術関数は、モジュラス及びランダム値を含み、データベースにインデックスを明らかにしないために、インデックスの暗号化を表している。
【０１３０】
秘密値は、モジュラスの素数への因数分解を含む。一実施形態においては、クエリは、Ｏ（ｌｏｇｍ）ビットを含み、ｍは、データベースに記憶されている要素の数と等しい。
【０１３１】
クエリを生成すると、処理ロジックは、データベースの全体に対して算術関数を実行するために、クエリをデータベースに通信する（処理ブロック１０３）。
【０１３２】
その後、処理ロジックは、データベースによる算術関数の実行結果を受け取り（処理ブロック１０４）、その結果を復号する（処理ブロック１０５）。一実施形態においては、データベースとの間で交換する情報の総量は、データベースに記憶されている情報の総量よりも少ない。
【０１３３】
（クエリ生成プロセスの例）
以下、σ：［１；ｍ］→Ｐは、データベースのインデックスの集合を、
【数１８】
【０１３４】
、素数であるｐ’ｊによって与えられる素数の冪の集合へ写像することを表すものとする。ここで、ｐｊは、Ｐにおけるｊ番目の素数の冪である。
【０１３５】
本明細書の目的のために、Ｐ及びσの写像は、クエリア及びデータベースの両方に知られているものと仮定する。
【０１３６】
図２は、クエリを生成するプロセスの一実施形態の流れ図である。
【０１３７】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動する）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。
【０１３８】
一実施形態において、プロセスは、入力値として、多くの値（ｍ，I，ｋ０，P，D，σ）を有する。
【０１３９】
ここで、ｍは、データベース内のビット数であり、ｉ∈［１，ｍ］は、クエリアが興味を持っている事項を表すデータベースのインデックスであり、ｋ０は、より高いセキュリティを提供するために大きくすることができるセキュリティのパラメータであり、Ｐは、素数の冪の集合であり、Ｄは、
【数１９】
【０１４０】
に対する分布であり、σは、上述した［１，ｍ］からＰへの写像である。
【０１４１】
図２を参照すると、素数の冪を求めるために、写像をインデックスに論理的に適用する処理ロジックによって、かかるプロセスが開始する（処理ブロック２０１）。一実施形態において、素数の冪は、σ（ｉ）＝Ｐｉ’を計算することにより求められる。
【０１４２】
素数の冪を使って、処理ロジックは、素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、十分に大きいモジュラスを、分布関数により、サンプリングする（処理ブロック２０２）。
【０１４３】
つまり、モジュラスの因数分解を困難にするために、モジュラスは十分に大きい。例えば、一実施形態においては、１０２４ビットは、十分に大きいと考えられるが、それよりも大きいモジュラスを使用してもよい。
【０１４４】
一実施形態において、このことは、
【数２０】
【０１４５】
を生成することにより起こる。
【０１４６】
モジュラスをサンプリングした後、処理ロジックは、モジュラスを法としてとる乗法群において、位数が素数の冪であるランダム値を生成する（処理ブロック２０３）。
【０１４７】
一実施形態においては、ランダム値は、ｐｉ’で割り切れる位数を有するランダムなｘ∈（Ｚ/ｎＺ）＊を生成することによって生成される。
【０１４８】
ランダム値を生成した後に、処理ロジックは、クエリを出力する（処理ブロック２０４）。一実施形態において、クエリｑ＝（ｎ；ｘ）及び秘密ｓは、ｎの因数分解を表している。
【０１４９】
（応答生成プロセスの例）
データベースは、クエリアからクエリを受け取り、それに応答して、クエリアに送信される応答を生成する。図３は、応答を生成するプロセスの一実施形態の流れ図である。
【０１５０】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム又は専用装置等で作動する）ソフトウェアや、又は、それらの組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。処理ロジックは、データベースの一部であってよい。
【０１５１】
一実施形態において、かかるプロセスは、入力値として多くの値（Ｂ，ｎ，ｘ，Ｐ，σ）を有する。
【０１５２】
ここで、Ｂは、ｍビット文字列として閲覧されたデータベースの内容を示し、ｎは、合成モジュラスであり、ｘは、（Ｚ/ｎＺ）＊からの要素であり、Ｐは、素数の冪の集合であり、σは、上述した［１，ｍ］からＰへの写像である。
【０１５３】
図３を参照すると、データベースを複数の群に分割することによって、プロセスが始まる（処理ブロック３０１）。
【０１５４】
一実施形態において、データベースＢは、
【数２１】
【０１５５】
に分割される。ここで、
【数２２】
【０１５６】
である。
【０１５７】
データベースを群に分割した後で、処理ロジックは、データベースの複数の群のそれぞれを整数として表す（処理ブロック３０２）。
【０１５８】
一実施形態において、このことは、各Ｃｉを、数Ｃ’ｉ∈［０，２ｌ−１］として表現することで起こる。つまり、［０，２ｌ−１］内の数を、底２で表記したものとしてＣｉを見る場合に、そのときの数をＣ’ｉと呼ぶ。
【０１５９】
次に、処理ロジックは、上述した各群のインデックスに関連付けられた素数の冪を法とする群のそれぞれの整数表記と合同である整数値を計算処理する（処理ブロック３０３）。
【０１６０】
一実施形態においては、全てのｉに対して、ｅ≡Ｃ’ｉ（ｍｏｄ ｐｉ’）となるような最小の正の整数となるように、ｅを設定することにより、整数値の計算が行われる。
【０１６１】
かかる整数値を使うことにより、処理ロジックは、応答を生成する（処理ブロック３０４）。
【０１６２】
一実施形態において、処理ロジックは、かかる整数値と等しい指数を持つ底の入力値を冪乗し、モジュラス値で算術モジュロ演算を実行することによって、応答を生成する。一実施形態において、応答生成には、応答ｒ＝ｘｅ（ｍｏｄ ｎ）の出力が含まれる。
【０１６３】
この技術の最初の３つの演算は、クエリから独立していることに留意されたい。そのため、本発明の他の実施形態では、これらの３つの演算は、予め計算処理することができる。
【０１６４】
（再構築プロセスの例）
データベースが、クエリへの応答をクエリアに提供した後、クエリアは、応答を検索するために、結果に基づいて再構築を行う。図４は、応答の検索を実行するプロセスの流れ図である。
【０１６５】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム又は専用装置等で作動する）ソフトウェアや、又は、それらの組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。処理ロジックは、データベースの一部であってもよい。
【０１６６】
一実施形態において、かかるプロセスは、入力値として多くの値（ｍ，ｉ，ｎ，ｘ，ｒ）を有する。
【０１６７】
ここで、ｍは、データベース内のビット数であり、ｉ∈［１，ｍ］は、クエリアが興味を持っている事項を表すデータベースのインデックスであり、ｎは、合成モジュラスであり、ｘは、（Ｚ/ｎＺ）＊からの要素であり、ｒは、（Ｚ/ｎＺ）＊における値である。
【０１６８】
図４を参照すると、特定のインデックスに関連付けられた素数の冪によって分割されるモジュラスに適用されるオイラーのファイ関数（Ｅｕｌｅｒ ｔｏｔｉｅｎｔ ｆｕｎｃｔｉｏｎ）と等しい冪まで、第１の入力底を冪乗し、第１の入力底を冪乗した結果に基づくモジュラスを使用するモジュロ演算を実行することによって第１の値を決定するという処理ロジックにより、プロセスが開始される（処理ブロック４０１）。
【０１６９】
一実施形態において、第２の値は、
【数２３】
【０１７０】
を演算処理することにより生成される。
【０１７１】
第１の値を決定した後で、処理ロジックは、素数の冪まで第２の入力底を冪乗し、第１の入力底を冪乗した結果に基づくモジュラスを用いるモジュロ演算を実行することによって、第２の値を決定する（処理ブロック４０２）。
【０１７２】
一実施形態において、第２の値は、
【数２４】
【０１７３】
を演算処理することにより生成される。
【０１７４】
第２の値を決定した後で、処理ロジックは、第１の値と等しい底に対する第２の値の離散対数に基づき、第３の値を算術的に決定する（処理ブロック４０３）。
【０１７５】
一実施形態において、第３の値は、底ｙに対するｚの離散対数（モジュロｎ）であるＣ’ｉを演算処理することにより生成される。
【０１７６】
一度、第３の値が生成されると、処理ロジックは、この第３の値から、クエリに関連付けられた少なくとも１ビットを生成する（処理ブロック４０４）。
【０１７７】
一実施形態において、少なくとも１ビットを生成することには、Ｃ’ｉの（ｉ ｍｏｄ ｌ）ビットであるＢｉの出力を含む。
【０１７８】
＜単一データベースの計算処理的秘匿情報検索のためのクライアント、サーバ及びシステムの実施形態＞
クライアントコンポーネントは、処理ロジックを実行することができる（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型のコンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０１７９】
図５は、クライアントの一実施形態の流れ図である。
【０１８０】
図５を参照すると、クライアントは、クエリを生成して応答を送信する方法を実行することによってデータベースの項目を要求することができる外部ネットワークインターフェイス５０１と、外部ネットワークインターフェイス５０１及びメモリ５０３に連結されたプロセッサ５０２とを備える。
【０１８１】
一実施形態において、プロセッサ５０２は、データベースに対する応答を受け取り、再構築のための方法を適用することができるので、興味のあるデータベースに含まれる項目を取得することができる。
【０１８２】
サーバコンポーネントは、処理ロジックを実行することができる（回路、専用ロジック等の）ハードウェア装置や、（汎用型のコンピュータシステム、又は、専用装置上で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０１８３】
図６は、クライアントの一実施形態の流れ図である。
【０１８４】
図６を参照すると、サーバは、データベースの項目に対する要求を受け取ることのできる外部ネットワークインターフェイス６０１と、外部ネットワークインターフェイス及びメモリに接続されたプロセッサ６０２とを備える。
【０１８５】
かかるプロセッサは、データベースの応答を生成するための方法によって与えられた出力をネットワークに送信する。ここで、第２、第３の入力が、かかる要求から取られる。
【０１８６】
単一データベースの計算処理による秘匿情報検索を提供するクライアントとサーバとの間のデータを通信するシステムについて考えてみる。
【０１８７】
このようなシステムは、データベースクエリを生成し、そのようなクエリを通信ネットワークを通じてサーバに送信し、サーバから通信ネットワークを介して応答を受け取り、興味のあるデータベースの項目を再構成することができるクライアントコンポーネントを備え、サーバコンポーネントは、データベースの応答を生成し、そのような応答を、通信ネットワークを通じてクライアントに送信することができる。
【０１８８】
＜対数的紛失通信＞
紛失通信において、クエリアが情報の単一ビットの検索だけを許可されているという意味で、サーバのプライバシーも保持されている。秘匿情報検索スキームのための本明細書に記載の技術は、紛失通信を提供するために修正することができる。
【０１８９】
一実施形態において、幾分不十分な紛失通信スキームを構成するための一般的な合成パラダイムが、効率的な秘匿情報検索スキームで定義され、効率的な紛失通信スキームが実現する。
【０１９０】
次に、どのようにして上述した既存の秘匿情報検索スキームを、そのような幾分不十分な紛失通信スキームに変換することができるかについて具体的に述べる。
【０１９１】
非効率な紛失通信のコンポーネントは、小さい入力の演算のみを行い、一方で、より効率的な秘匿情報検索コンポーネントは、大きいサイズの入力の演算を行うので、合成パラダイムが機能する。合成パラダイムを適用することにより、対数的総通信を実現する紛失通信スキームが得られる。
【０１９２】
上述した秘匿情報検索の技術によって、クエリアが、（少なくとも）ｌｏｇｍビットを回復することができる。ここで、ｍは、データベースのサイズである。
【０１９３】
このスキームを修正するために、このスキームにより、クエリアは、所与のｌビット（ｌ＝ｌｏｇｍ）ブロックＣｉから単一ビットを回復させることだけができるが、同時に、クエリアが、１つ以上のブロックからビットを回復することも防いでいる。
【０１９４】
以下では、ＯＴｌを、ｌビットの文字列Ｃｉ及びクエリアのクエリｑＯＴｉ，ｊを入力として取得し、応答
【数２５】
【０１９５】
を出力する既存の紛失通信スキームとする。
【数２６】
【０１９６】
という制限を条件として、さまざまな紛失通信スキームを使うことができる。
【０１９７】
一実施形態において、この制限は、紛失通信スキームの通信計算量がＯ（ｌｏｇｍ）であるように使われている。この紛失通信スキームを使うことで、上述した秘匿情報検索スキームの技術を、クエリアが任意のブロックの単一ビットを越えて回復することができないことを保証するように修正してもよい。
【０１９８】
（紛失通信クエリ生成プロセスの例）
図８は、紛失通信クエリ生成方法の一実施形態の流れ図である。
【０１９９】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両者の組み合わせによって構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、流れ図中の演算は、クエリアによって実行される。
【０２００】
図８を参照すると、このプロセスは、データベースＢ中のデータベースビットを素数の冪に写像する処理ロジックによって開始される（処理ブロック８０１）。このことは、上述したものと同様に起こる。但し、例外は、（底の素数は同じであっても）素数の冪がオリジナルのものより小さい、又は、大きい可能性があるということである。
【０２０１】
一実施形態において、各素数の冪は（各素数の冪が２ｌより大きくなくてはならないことにもともと反して）２ｍａｘ｛ｒｉ｝より大きいので、データベースの応答は、劣化なしに暗号化することができる。
【０２０２】
次に、クエリアにおける処理ロジックは、適当な素数の冪ｐｉ及びジェネレータｘに対して「Φ-ｈｉｄｅ」処理を行うモジュラスｎを生成する（処理ブロック８０２）。
【０２０３】
これにより、データベースのビットＣｉのｊ番目のビット、ブロックＣにおけるｊ∈［１，ｌ］に、クエリアが興味を持っていることを推測することができる。
【０２０４】
その後、クエリアの処理ロジックは、（任意の文字列Ｃｉに対して）データベースの紛失通信応答
【数２７】
【０２０５】
により、クエリアが、Ｃｉｊを回復できるように、ｊ∈［１，ｌ］におけるインデックスを暗号化する紛失通信クエリ
【数２８】
【０２０６】
を生成する（処理ブロック８０３）。
【０２０７】
（紛失通信応答生成プロセスの例）
図９は、紛失通信クエリ生成プロセスの一実施形態の流れ図である。
【０２０８】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両者の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。 一実施形態において、流れ図中の演算は、データベースによって実行される。
【０２０９】
図９を参照すると、このプロセッサは、全てのｉに対して、ｅ≡ｒｉｊ（ｍｏｄ ｐｉ）であるようなｅを計算処理する処理ロジックによって開始される（処理ブロック９０１）。
【０２１０】
次に、処理ロジックは、値ｘｅ（ｍｏｄ ｎ）を計算し（処理ブロック９０２）、そして、この値をクエリアに送信する（処理ブロック９０３）。
【０２１１】
（紛失通信再構築プロセスの例）
図１０は、紛失通信応答検索のプロセスの一実施形態の流れ図である。
【０２１２】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１０に記載されている演算は、クエリアによって実行される。
【０２１３】
プロセッサは、図１０を参照すると、ｒｉｊを回復する処理ロジックによって開始される（処理ブロック１００１）。
【０２１４】
一実施形態において、処理ロジックは、秘匿情報検索の再構築プロセスにおいてＣｉを回復するのと同様の方法で回復を実行する。
【０２１５】
ｒｉｊを回復した後に、処理ロジックは、ビットＣｉｊを紛失通信応答ｒｉｊから回復する（処理ブロック１００２）。
【０２１６】
（紛失通信プロセスの分析）
上記のやり方によって、クエリアが、任意の単一ブロックＣｉから１ビットを越えて回復することはできないことを保証されるが、クエリアが、１つ以上のブロックから１ビットを回復することができないことを保証するものではない。
【０２１７】
例えば、クエリアは、２つの素数の冪ｐｉ１及びｐｉ２に対して「Φ-ｈｉｄｅ」処理を行うように、ｎを選択することができ、この場合、上述したデータベースの紛失通信の補足された応答によって、２つのデータベースビット、つまり、Ｃｉ１ｊとＣｉ２ｊが、クエリアに与えられる。
【０２１８】
この問題に対処するため、一実施形態において、データベースは、クエリアが、ｎにおいて、２以上の素数の冪に対して「Φ-ｈｉｄｅ」処理を行うことから恩恵を受けることができないことを保証するために、この技術を使う。
【０２１９】
議論のために、Φ（ｎ）が、１つの素数の冪ｐｉだけによって割り切れ、残りに対して互いに素であることを確認することができるデータベースを想定してみる。
【０２２０】
また、ｅ’が、ｐｉを法とするｒｉｊと合同である最も小さい整数であり、（上記スキームで設定したように）ｅ＝ｅ’と設定する代わりに、データベースが、適当に大きい範囲（例えば、［１，ｎ２］）から乱数ｚを選び、
【数２９】
【０２２１】
を設定し、ｘｅ（ｍｏｄ ｎ）をクエリアに送信する場合を考えてみる（この方法で選択された場合、ｅは、必要なモジュール方式の等式をまだ満たしていることに注意されたい）。
【０２２２】
このシナリオにおいて、ｐｉ２が、Φ（ｎ）に対して互いに素であれば、クエリアは、値Ｃｉ２ｊについて何らかの情報を取得することができるかどうかの問いに関して、たとえ境界のない計算処理上の素数を有し、データベースの他の全てのビットを知っていたとしても、クエリアは、せいぜい無視できる程の情報を得られ程度であるというのが答えである。
【０２２３】
なぜならば、クエリアが、Ｃｉ２ｊに関して取得可能な唯一の情報は、ｅに埋め込まれているためである。特に、クエリアが、ｅについて引き出せる唯一の情報は、以下の通りである。
【０２２４】
１． Φ（ｎ）を法とするｅの値（クエリアは、難しい課題ではあるが、底ｘに対してｘｅの離散対数を計算処理することによって、この値を回復することができる）
２．
【数３０】
【０２２５】
に対して、
【数３１】
【０２２６】
である。ここで、Ｃｉｊ＝０ならば、ｅ’＝ｅ’０であり、Ｃｉｊ＝１ならば、ｅ’＝ｅ’１である（これは、データベースが、ｅを計算処理する方法なので、クエリアは、このことを知っている）。
【０２２７】
そこで、問題は、クエリアが、
【数３２】
【０２２８】
の２つの確率のうち、どちらが真であるかを見分けることができるかどうかである。答えは、（無視できる程度の利点を除き、）できない、である。
【０２２９】
なぜならば、２つの事象の条件付き確率（クエリアのｅについての情報に関する条件）は、無視できるためである。
【０２３０】
ｅΦ（ｎ）＝ｅ ｍｏｄ Φ（ｎ）を設定すると、ｚ∈［１，ｎ２］に対して、
【数３３】
【０２３１】
を満たすｅの
【数３４】
【０２３２】
の可能値のどちらか一方が存在する。
【０２３３】
状況は、等式、すなわち、ｚ∈［１，ｎ２］に対して、
【数３５】
【０２３４】
の第２の集合に対して同じである。
【０２３５】
したがって、条件付き確率同士の差は、せいぜい
【数３６】
【０２３６】
であり、これは、無視できるものであることを検証することができる。
【０２３７】
一実施形態において、ユーザは、Φ（ｎ）が、素数の冪ｐｉのうち、１つだけによって割り切れ、残りに対して互いに素であるように、ｎを選択する。
【０２３８】
なお、クエリアが、不正を行わなければ（そして、Φ（ｎ）が、Φ（ｎ）を割り切る１つ（ｐｉ）を除く全ての素数の冪に対して互いに素であれば）、Ｚ/ｎＺの任意の数が、ｎを法とする固有の
【数３７】
【０２３９】
乗根を持つことになることに留意されたい。
【０２４０】
しかしながら、ユーザが、不正を行った場合（根が存在するならば）、その根は、固有ではなくなる。
【０２４１】
そのため、不正を防止するため、不正を行わない者は、計算処理を行うことができるが、不正を行う者は、計算処理を行うことができない固有の
【数３８】
【０２４２】
乗根から生成される疑似ランダム系列で、データベースが、ブロックＣｉのビットをマスクする（そして、オリジナルのＣｉではなく、このマスクされた文字列からｒｉｊを生成する）
一実施形態において、全体的に改良した紛失通信スキームの方法について以下に説明する。
【０２４３】
（紛失通信のためのクエリ生成プロセスの他の実施形態）
一実施形態において、紛失通信クエリ生成のためのクエリ生成プロセスは、上述したプロセスと同じである。
【０２４４】
（応答生成プロセスの他の実施形態）
図１１は、応答生成プロセスの他の実施形態の流れ図である。
【０２４５】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されてもよい処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１１に記載される演算は、データベースよって実行される。
【０２４６】
図１１を参照すると、このプロセスは、乱数ｙ∈（Ｚ/ｎＺ）＊を生成するロジックを処理する処理ロジックによって開始され、
【数３９】
【０２４７】
を設定する（処理ブロック１１０１）。
【０２４８】
各ブロックＣｉに対して、処理ロジックは、ｙｉ＝ｙｐｉ（ｍｏｄ ｎ）を設定し、
【数４０】
【０２４９】
を設定し、そして、ｒｉｊ＝ＯＴｌ（Ｃ’ｉ；ｑＯＴ，ｌ）を設定する（処理ブロック１１０２）。
【０２５０】
そして、処理ブロックは、乱数ｚ∈［１，ｎ２］（又は、他の適当な範囲において）を生成する（処理ブロック１１０３）。
【０２５１】
その後、処理ブロックは、任意のｉに対して、ｅ’＝ｒｉｊ（ｍｏｄ ｐｉ）を満たす最小の正の整数となるｅ’を設定し、
【数４１】
【０２５２】
を設定し（処理ブロック１１０４）、そして、ｒ＝ｘｅ（ｍｏｄ ｎ）とする応答（Ｙ，ｙ）を送信する（処理ブロック１１０５）。
【０２５３】
図１２は、紛失通信応答検索の他の実施形態の流れ図である。
【０２５４】
このプロセスは、（例えば、回路、専用ロジック等の）ハードウェアや、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェアや、又は、その両方の組み合わせから構成されている処理ロジックによって実行される。処理ロジックは、ファームウェアによって構成されていてもよい。一実施形態において、図１２に記載する演算は、クエリアによって実行される。
【０２５５】
図１２を参照すると、このプロセスは、上述した標準的なメカニズム、すなわち、Φ（ｎ）/ｐｉによって冪乗し、関連する離散対数を計算するメカニズムを使って、ｒｉｊを回復する処理ブロックによって開始される（処理ブロック１２０１）。
【０２５６】
ｒｉｊを使って、処理ロジックは、Ｃ’ｉのｊ番目のビットを回復する（処理ブロック１２０２）。
【０２５７】
そして、処理ロジックは、ｎを法とするＹの固有の
【数４２】
【０２５８】
乗根として、ｙｉを回復する（処理ブロック１２０３）。
【０２５９】
最後に、処理ロジックは、Ｃｉ’ｊとＨ（ｙｉ）から、Ｃｉｊを計算する（処理ブロック１２０４）。
【０２６０】
結果として得られるビットが予測不可能であるということが、関数Hから必要とされる唯一の安全性のプロパティである。この目的を実現するための数多くの方法が、当業者には公知である。このような方法には、ハードコアビットや、ＳＨＡ-１等の安全な暗号化ハッシュ関数、強秘匿暗号化スキーム当を使用することが含まれるが、これらに限定されるものではない。
【０２６１】
（紛失通信クライアントの例）
紛失通信クライアントのコンポーネントは、処理ロジックを実行可能な、（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置、又は、その両方の組み合わせであってよい。
【０２６２】
一実施形態において、このコンポーネントは、図５のクライアントコンポーネントと同様なコンポーネントを有する。例えば、コンポーネントは、データベースの項目に対する要求がなされる外部ネットワークインターフェイスから構成されている。
【０２６３】
しかしながら、紛失通信クライアントは、紛失通信クエリを生成して応答を送信する方法を実行することによってそれを行う。
【０２６４】
コンポーネントは、外部ネットワークインターフェイス及びメモリに接続されたプロセッサを更に備える。
【０２６５】
プロセッサは、紛失通信データベースに対する応答を受け取り、データベースに含まれる興味のある項目を取得するために、再構築プロセスを適用することができる。
【０２６６】
紛失通信サーバのコンポーネントは、上述した処理を実行可能な、（例えば、回路、専用ロジック等の）ハードウェア装置や、（汎用型コンピュータシステム、又は、専用装置等で作動するような）ソフトウェア装置や、又は、その両方の組み合わせであってよい。
【０２６７】
一実施形態において、コンポーネントは、図６のクライアントコンポーネントと同様なコンポーネントを有する。
【０２６８】
例えば、サーバコンポーネントは、データベースの項目に対する要求を受け取る外部ネットワークインターフェイスを備える。
【０２６９】
また、コンポーネントは、外部ネットワークインターフェイス及びメモリに接続されたプロセッサを更に備える。
【０２７０】
プロセッサは、紛失通信データベースの応答を生成するプロセスによって与えられる出力をネットワークへ送信する。ここで、第２及び第３の入力は、かかる要求から取得される。
【０２７１】
＜単一データベースの計算処理による秘匿情報検索のためのシステム＞
システムの一実施形態では、単一データベースの紛失通信を提供するために、クライアントとサーバとの間で、データを通信する。
【０２７２】
一実施形態において、システムは、紛失通信データベースクエリが可能で、そのようなクエリを通信ネットワーク上でサーバに送信することができ、サーバから通信ネットワークを介して紛失通信応答が可能であり、データベースの興味がある項目を再構築することができる紛失通信応答クライアントコンポーネントを含む。
【０２７３】
一実施形態において、サーバコンポーネントは、データベース応答を生成し、そのような応答を通信ネットワーク上でクライアントに送信する。
【０２７４】
＜紛失通信を実現するための入れ子秘匿情報検索方法＞
上述の秘匿情報検索スキームを使うことで、非効率的な紛失通信スキームが構築されることがある。
【０２７５】
この非効率的なスキームが、本明細書に記載されている秘匿情報検索からなる場合、その結果として得られるスキームは、効率的な秘匿情報検索スキームである。
【０２７６】
「非効率な」紛失通信スキームは、小さい入力値を演算するだけであり、一方、効率的な秘匿情報検索スキームは、大きい入力値を演算するので、その構成は効率的である。
【０２７７】
スキームは、秘匿情報検索スキームの修正であり、ｍと等しくなるように値ｌが選択されている。
【０２７８】
この場合、結果として得られるデータベースは、それぞれ１ビットを構成するｍブロックに分割される。
【０２７９】
上述したように、不正を行わない者は、計算処理を行うことができ、不正を行う者は、それができない固有の
【数４３】
【０２８０】
乗根から生成される疑似ランダム系列を使って各値がマスクされる。
【０２８１】
上述の紛失通信スキームは、クエリアが、モジュラー根を計算するので、クエリアに対して、（秘匿情報検索スキームのように、Ｏ（√ｍ）の計算ではなく）、Ｏ（ｍ）の計算を持つ。
【０２８２】
しかしながら、入れ子秘匿情報検索スキームという当技術分野において公知の技術を使うことで、因数ｆｃ−１（但し、ｆは、（ｌｏｇｎ）/｜Ｐの最小許容値を表す定数）により、スキームの通信計算量を増加させるという犠牲を払って、ユーザによる計算Ｏ（ｍ１/ｃ）を得ることができる。
【０２８３】
本明細書に記載されているプロセスは、紛失ファイル通信を実現するために拡張することもできる。
【０２８４】
クエリアが、データベースからのファイルを欲しており、データベースが、ユーザにクエリ毎に１ファイルまでと制限したいというシナリオを例とする。
【０２８５】
各ファイルを、（各ｌビット列ではなく）素数の冪に関連付けることより、ビット単位の解決策よりも効率的な解決策を構成することが可能である。長いファイルは、定数因数の暗号文展開だけで紛失通信することができる。
【０２８６】
（コンピュータシステムの一実施形態）
図１３は、本明細書に説明する１つ以上の演算を実行するコンピュータシステムの一例のブロック図である。
【０２８７】
図１３を参照すると、コンピュータシステムは、クライアント又はサーバのコンピュータシステムを備えていてもよい。
【０２８８】
コンピュータシステムは、通信メカニズム、又は、情報を通信するためのバス、及び、情報を処理するためのバスに連結されたプロセッサを備えている。
【０２８９】
プロセッサには、マイクロプロセッサに限定しないが、例えば、Ｐｅｎｔｉｕｍ、ＰｏｗｅｒＰＣ、Ａｌｐｈａなどのマイクロプロセッサを含んでいる。
【０２９０】
システムは、情報や、プロセッサによって実行される命令を格納するバスに連結されるランダムアクセスメモリ（ＲＡＭ）、又は、他の動的記憶装置（メインメモリと称す）を更に備える。
【０２９１】
また、メインメモリも、プロセッサによる命令を実行している間に、暫定変数、又は、他の中間情報のために使うことができる。
【０２９２】
また、コンピュータシステムも、静的情報やプロセッサに対する命令を記憶するためにバスに接続されている読み取り専用メモリ（ＲＯＭ）、及び／又は、他の静的記憶装置、磁気ディスク、又は、光学ディスク等のデータ記憶装置、及び、それに対応するディスクドライブを備えている。
【０２９３】
データ記憶装置は、情報及び命令を記憶するために、バスに接続されている。
【０２９４】
コンピュータシステムは、ブラウン管ディスプレイ装置（ＣＲＴ）、又は、液晶表示装置（ＬＣＤ）等のコンピュータユーザに情報を表示するためにバスに接続されている表示装置に更に接続されてもよい。
【０２９５】
英数字キー及び他のキーを含む英数字入力装置も、情報及びプロセッサに対するコマンドを選択を通信するために、バスに接続されている。
【０２９６】
他のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、又は、カーソル指示キー等の、指示情報やコマンドの選択をプロセッサに通信し、表示装置上でのカーソルの動きを制御するために、バスに接続されているカーソル制御である。
【０２９７】
バスに連結することができる他の装置は、紙、フィルム、又は、同様のタイプの媒体に、指示、データ、又は、他の情報をプリントとするために使うことのできるハードコピー装置である。
【０２９８】
また、スピーカー、及び／又は、マイク等の音声録音再生装置も、コンピュータシステムと音声でインターフェイスするために、オプションとしてバスに接続してもよい。
【０２９９】
バスに接続してもよい他の装置は、電話、又は、手のひらサイズの携帯装置と通信する有線／無線の通信機能である。
【０３００】
なお、システムの任意の、又は、全てのコンポーネント、及び、関連するハードウェアを本発明に使用してもよいことに留意されたい。
【０３０１】
しかしながら、コンピュータシステムの他の構成には、上記の装置の中のいくつかの装置又は全ての装置を含んでも良いということを理解することができる。
【０３０２】
上述の説明を読めば、本発明の変更や修正が、当該技術分野において通常の熟練を有する者には明らかとなるであろうが、図を使って表し説明した、いかなる特定の実施形態も、本発明を制限するものと考えられるようには意図されていないことを理解すべきである。
【０３０３】
よって、様々な実施形態の詳細を参照することは、本発明にとって必要不可欠であると見なされる特徴だけを詳述する請求項の範囲を制限するように意図するものではない。
【図面の簡単な説明】
【０３０４】
【図１】データベースから情報を非公開に検索するプロセスの一実施形態の流れ図である。
【図２】クエリ生成プロセスの一実施形態の流れ図である。
【図３】応答生成プロセスの一実施形態の流れ図である。
【図４】応答検索プロセスの流れ図である。
【図５】クライアントコンポーネントの一実施形態を示す。
【図６】サーバコンポーネントの一実施形態を示す。
【図７】クライアントコンポーネントを有するシステム構成の一実施形態を示す。
【図８】紛失通信クエリ生成方法の一実施形態の流れ図である。
【図９】紛失通信クエリ生成プロセスの一実施形態の流れ図である。
【図１０】紛失通信応答検索プロセスの一実施形態の流れ図である。
【図１１】応答生成プロセスの他の実施形態の流れ図である。
【図１２】紛失通信応答検索プロセスの他の実施形態の流れ図である。
【図１３】コンピュータシステムの一実施形態の例を示す。
【符号の説明】
【０３０５】
５０１、６０１…ネットワークインターフェイス
５０２、６０２…プロセッサ
５０３、６０３…メモリ（暗号鍵）
【特許請求の範囲】
【請求項１】
非公開で、データベースから情報を検索する方法であって、
前記データベースから検索される情報に対応するインデックスを取得する工程と、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信する工程とを有し、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする方法。
【請求項２】
前記素数の冪を求めるために、前記データベースに対する写像を適用する工程を更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、前記モジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪である前記ランダム値を生成する工程とを有することを特徴とする請求項１に記載の方法。
【請求項４】
素数の冪を求めるために、写像を前記インデックスに適用する工程と、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成する工程とを有することを特徴とする請求項１に記載の方法。
【請求項５】
前記算術関数を実行した結果を受け取る工程と、
前記結果を復号する工程を有し、
前記データベースと交換された情報の総量は、前記データベースに記憶されている情報の総量より少ないことを特徴とする請求項１に記載の方法。
【請求項６】
システムによって実行される時に、前記システムに対して方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記方法は、
前記データベースから検索される情報に対応するインデックスを取得する工程と、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信する工程とを有し、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする工業製品。
【請求項７】
前記方法は、前記素数の冪を求めるために、前記データベースに対する写像を適用する工程を更に有することを特徴とする請求項６に記載の工業製品。
【請求項８】
前記方法は、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、前記モジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪である前記ランダム値を生成する工程とを有することを特徴とする請求項６に記載の工業製品。
【請求項９】
前記方法は、
素数の冪を求めるために、写像を前記インデックスに適用する工程と、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成する工程とを有することを特徴とする請求項６に記載の工業製品。
【請求項１０】
前記算術関数を実行した結果を受け取る工程と、
前記結果を復号する工程を有し、
前記データベースと交換された情報の総量は、前記データベースに記憶されている情報の総量より少ないことを特徴とする請求項６に記載の工業製品。
【請求項１１】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
前記データベースから検索される情報に対応するインデックスを取得し、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成し、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信するように構成されており、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする方法。
【請求項１２】
前記プロセッサは、
素数の冪を求めるために、写像を前記インデックスに適用し、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングし、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成するように構成されていることを特徴とする請求項１１に記載の装置。
【請求項１３】
多項式対数関数的な単一データベースの計算処理による秘匿情報検索プロセスであって、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信する工程と、
前記データベースから前記算術関数を実行した結果を受け取る工程とを有し、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とするプロセス。
【請求項１４】
システムによって実行される時に、前記システムに対して多項式対数関数的な単一データベースの計算処理による秘匿情報検索プロセスを実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記プロセスは、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信する工程と、
前記データベースから前記算術関数を実行した結果を受け取る工程とを有し、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とする工業製品。
【請求項１５】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成し、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信し、
前記データベースから前記算術関数を実行した結果を受け取るように構成されており、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とする装置。
【請求項１６】
データベースの複数の群の各々を整数として表す工程と、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算する工程と、
モジュラス値を法とする前記整数値の演算に等しい指数がを与えられた底入力値を冪乗することより応答を生成する工程とを有することを特徴とする方法。
【請求項１７】
システムによって実行される時に、前記システムに対して方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記方法は、
データベースの複数の群の各々を整数として表す工程と、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算する工程と、
モジュラス値を法とする前記整数値の演算に等しい指数がを与えられた底入力値を冪乗することより応答を生成する工程とを有することを特徴とする工業製品。
【請求項１８】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
データベースの複数の群の各々を整数として表し、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算し、
モジュラス値を法とする前記整数値の演算に等しい指数が与えられた底入力値を冪乗することより応答を生成するように構成されていることを特徴とする装置。
【請求項１９】
入力に対して紛失通信関数を適用して、出力を生成する工程と、
前記紛失通信の前記出力を用いた秘匿検索プロセスを適用する工程とを有することを特徴とする方法。
【請求項１】
非公開で、データベースから情報を検索する方法であって、
前記データベースから検索される情報に対応するインデックスを取得する工程と、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信する工程とを有し、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする方法。
【請求項２】
前記素数の冪を求めるために、前記データベースに対する写像を適用する工程を更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、前記モジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪である前記ランダム値を生成する工程とを有することを特徴とする請求項１に記載の方法。
【請求項４】
素数の冪を求めるために、写像を前記インデックスに適用する工程と、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成する工程とを有することを特徴とする請求項１に記載の方法。
【請求項５】
前記算術関数を実行した結果を受け取る工程と、
前記結果を復号する工程を有し、
前記データベースと交換された情報の総量は、前記データベースに記憶されている情報の総量より少ないことを特徴とする請求項１に記載の方法。
【請求項６】
システムによって実行される時に、前記システムに対して方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記方法は、
前記データベースから検索される情報に対応するインデックスを取得する工程と、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信する工程とを有し、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする工業製品。
【請求項７】
前記方法は、前記素数の冪を求めるために、前記データベースに対する写像を適用する工程を更に有することを特徴とする請求項６に記載の工業製品。
【請求項８】
前記方法は、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、前記モジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪である前記ランダム値を生成する工程とを有することを特徴とする請求項６に記載の工業製品。
【請求項９】
前記方法は、
素数の冪を求めるために、写像を前記インデックスに適用する工程と、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングする工程と、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成する工程とを有することを特徴とする請求項６に記載の工業製品。
【請求項１０】
前記算術関数を実行した結果を受け取る工程と、
前記結果を復号する工程を有し、
前記データベースと交換された情報の総量は、前記データベースに記憶されている情報の総量より少ないことを特徴とする請求項６に記載の工業製品。
【請求項１１】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
前記データベースから検索される情報に対応するインデックスを取得し、
前記インデックスを前記データベースに対して明らかにしないクエリであり、前記インデックスの算術関数で、かつ、前記インデックスの算術関数である秘密値であるクエリを生成し、
前記データベースの全体に対して前記算術関数を実行するために前記クエリを前記データベースに通信するように構成されており、
前記算術関数は、素数の冪がランダム値の位数であるように、位数が前記素数の冪によって割り切れるランダム値のモジュラスによって特定される乗法群を含み、
前記秘密値は、前記モジュラスの素数への因数分解を含むことを特徴とする方法。
【請求項１２】
前記プロセッサは、
素数の冪を求めるために、写像を前記インデックスに適用し、
前記素数の冪に対して「Φ-ｈｉｄｅ」処理を行う値の集合から、分布関数に従って、十分に大きいモジュラスをサンプリングし、
前記モジュラスを法としてとる前記乗法群において、位数が前記素数の冪であるランダム値を生成するように構成されていることを特徴とする請求項１１に記載の装置。
【請求項１３】
多項式対数関数的な単一データベースの計算処理による秘匿情報検索プロセスであって、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信する工程と、
前記データベースから前記算術関数を実行した結果を受け取る工程とを有し、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とするプロセス。
【請求項１４】
システムによって実行される時に、前記システムに対して多項式対数関数的な単一データベースの計算処理による秘匿情報検索プロセスを実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記プロセスは、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成する工程と、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信する工程と、
前記データベースから前記算術関数を実行した結果を受け取る工程とを有し、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とする工業製品。
【請求項１５】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
インデックスを前記データベースに対して明らかにしないように、前記インデックスを算術関数に暗号化するクエリを生成し、
前記データベースの全体に対して前記算術関数を実行するために、前記クエリを前記データベースに通信し、
前記データベースから前記算術関数を実行した結果を受け取るように構成されており、
前記データベースと交換された情報の総量が、前記データベースのサイズの対数の定数因数内であることを特徴とする装置。
【請求項１６】
データベースの複数の群の各々を整数として表す工程と、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算する工程と、
モジュラス値を法とする前記整数値の演算に等しい指数がを与えられた底入力値を冪乗することより応答を生成する工程とを有することを特徴とする方法。
【請求項１７】
システムによって実行される時に、前記システムに対して方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する工業製品であって、
前記方法は、
データベースの複数の群の各々を整数として表す工程と、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算する工程と、
モジュラス値を法とする前記整数値の演算に等しい指数がを与えられた底入力値を冪乗することより応答を生成する工程とを有することを特徴とする工業製品。
【請求項１８】
情報に対する要求が行われる外部ネットワークインターフェイスと、メモリと、前記外部ネットワークインターフェイス及び前記メモリに接続されているプロセッサとを具備する装置であって、
前記プロセッサは、
データベースの複数の群の各々を整数として表し、
前記各群のインデックスに関連付けられた素数の冪を法とする前記群の各々の各整数表記と合同である整数値を計算し、
モジュラス値を法とする前記整数値の演算に等しい指数が与えられた底入力値を冪乗することより応答を生成するように構成されていることを特徴とする装置。
【請求項１９】
入力に対して紛失通信関数を適用して、出力を生成する工程と、
前記紛失通信の前記出力を用いた秘匿検索プロセスを適用する工程とを有することを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２００８−５００５９８（Ｐ２００８−５００５９８Ａ）
【公表日】平成２０年１月１０日（２００８．１．１０）
【国際特許分類】
【出願番号】特願２００７−５２７４５０（Ｐ２００７−５２７４５０）
【出願日】平成１７年５月２０日（２００５．５．２０）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０１７６１８
【国際公開番号】ＷＯ２００５／１１４４８１
【国際公開日】平成１７年１２月１日（２００５．１２．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＰＥＮＴＩＵＭ
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
【公表日】平成２０年１月１０日（２００８．１．１０）
【国際特許分類】
【出願日】平成１７年５月２０日（２００５．５．２０）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０１７６１８
【国際公開番号】ＷＯ２００５／１１４４８１
【国際公開日】平成１７年１２月１日（２００５．１２．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＰＥＮＴＩＵＭ
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
[ Back to top ]