(57)【要約】  秘密分散法を用いた秘匿検索システムにおいて、その検索機能を損なうことなく、各サーバ装置が保持するデータのサイズを低減する。サーバ装置は、秘密情報の１シンボルごとの分散登録データを保存するデータ記憶部と、データ記憶部に保存された分散登録データを、複数シンボルを連結したデータに対する検索用データに変換するデータ変換部と、検索用データと分散検索要求データとを用いて、他のサーバ装置のデータ検索部と通信を行いながら、データ記憶部の分散登録データに対する検索を行って、分散検索結果を出力するデータ検索部と、を備える。
2016136201.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報の１シンボルごとの分散登録データを保存するデータ記憶手段と、
前記データ記憶手段に保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換するデータ変換手段と、
前記検索用データと分散検索要求データとを用いて、他のサーバ装置のデータ検索手段と通信し、前記データ記憶手段の前記分散登録データに対する検索を行って、分散検索結果を出力するデータ検索手段と、
を有するサーバ装置。
【請求項２】
前記分散登録データは、１シンボルごとの複製型秘密分散法の分散情報として保持し、
前記データ変換手段は、前記データ記憶手段に格納された１シンボルごとの複製型秘密分散法の分散情報を、複数シンボルに対する１つのしきい値秘密分散法の分散情報に生成して前記検索用データを得る、
請求項１に記載のサーバ装置。
【請求項３】
前記データ記憶手段は、前記分散登録データとして、しきい値秘密分散法によって生成された秘密情報の分散データを保持し、
前記データ変換手段は、前記データ記憶手段に保存された秘密情報の分散データを連結して前記検索用データを取得し、
前記データ検索手段は、前記データ変換手段によって連結されたデータを用いて、拡大体上の演算で検索して前記分散検索結果を得る、
請求項１に記載のサーバ装置。
【請求項４】
各々が請求項１乃至３のいずれか１つに記載のサーバ装置からなる第１乃至第Ｎ（Ｎは２以上の整数）のサーバ装置と、該第１乃至第Ｎのサーバ装置にネットワークを介して接続されたクライアント装置と、から成る秘匿検索システムであって、前記クライアント装置は、
登録データから、前記第１乃至第Ｎのサーバ装置にそれぞれ登録されるべき第１乃至第Ｎの分散登録データを生成する登録データシェア生成手段と、
検索要求データから、前記第１乃至第Ｎのサーバ装置へそれぞれ送信するための第１乃至第Ｎの分散検索要求データを生成するクエリデータシェア生成手段と、
前記第１乃至第Ｎのサーバ装置からそれぞれ受信した第１乃至第Ｎの分散検索結果から、検索結果の分散情報を復号する秘密分散復号手段と、
を有する秘匿検索システム。
【請求項５】
クライアント装置と、該クライアント装置にネットワークを介して接続された第１乃至第Ｎ（Ｎは２以上の整数）のサーバ装置と、を備える検索システムにおける秘匿検索方法であって、
前記クライアント装置によって登録データに対して秘密分散法を用い生成された第１乃至第Ｎの分散登録データが、前記第ｎ（１≦ｎ≦Ｎ）のサーバ装置の第ｎのデータ記憶手段に第ｎの分散登録データとして保存され、
前記クライアント装置が、検索要求データに対して前記秘密分散法を用いて第１乃至第Ｎの分散検索データを生成し、該第１乃至第Ｎの分散検索データをそれぞれ前記第１乃至第Ｎのサーバ装置へ送信し、
前記第ｎのサーバ装置が、前記第ｎのデータ記憶手段に保存された前記第ｎの分散登録データを、複数シンボルを連結したデータに対する第ｎの検索用データに変換し、
前記第ｎのサーバ装置が、前記第ｎの検索用データと前記第ｎの分散検索データとを用いて、他のサーバ装置と通信を行いながら、前記第ｎのデータ記憶手段の前記第ｎの分散登録データに対する検索を行い、第ｎの分散検索結果を前記クライアント装置へ送信し、
前記クライアント装置が、前記第１乃至第Ｎのサーバ装置から受信した第１乃至第Ｎの分散検索結果に対して、前記秘密分散法の復号手順を実行して、検索結果を復元する、
秘匿検索方法。
【請求項６】
前記登録データ生成ステップでは、前記クライアント装置が、前記登録データを複製型秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索要求データ生成ステップでは、前記クライアント装置が、前記検索要求データをＳｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索データ変換ステップでは、前記第ｎのサーバ装置が、前記第ｎの分散登録データを前記Ｓｈａｍｉｒのしきい値秘密分散法の分散データである前記第ｎの検索用データに変換する、
請求項５に記載の秘匿検索方法。
【請求項７】
前記登録データ生成ステップでは、前記クライアント装置が、前記登録データをＳｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索要求データ生成ステップでは、前記クライアント装置が、前記検索要求データを前記Ｓｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索データ変換ステップでは、前記第ｎのサーバ装置が、前記第ｎの分散登録データを連結して一つのデータとして前記第ｎの検索用データに変換する、
請求項５に記載の秘匿検索方法。
【請求項８】
サーバ装置で検索を実行する検索方法であって、
秘密情報の１シンボルごとの分散登録データを、複数シンボルを連結したデータに対する検索用データに変換し、
前記検索用データと分散検索要求データとを用いて、他のサーバ装置と通信し、前記分散登録データに対する検索を行って、分散検索結果を出力する、
検索方法。
【請求項９】
コンピュータに、
秘密情報の１シンボルごとの分散登録データを、複数シンボルを連結したデータに対する検索用データに変換し、
前記検索用データと分散検索要求データとを用いて、他のサーバ装置と通信し、前記分散登録データに対する検索を行って分散検索結果を出力する、ことを実行させる検索プログラムを格納した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを検索する検索システムに関し、特に、データを複数に分散して保持する際に、検索条件と保持されたデータを秘匿できる秘匿検索システムに関する。
【背景技術】
【０００２】
クラウドなど外部のサーバ装置に、ユーザが情報を預けるサービスなどが知られている。そのようなサービスにおいては、預けたデータが漏洩することを防ぐために、暗号化などによってデータを秘匿化する方法が一般的に採用されている。一般的な秘匿化方法には、次に述べるような問題がある。具体的には、秘匿化されたデータから所望のデータをサーバ装置側で検索する場合、秘匿化されたデータをサーバ装置側で復元することで検索が可能となる。しかしながら、このようなサーバ装置側での復元が伴う方法では、サーバ装置からのデータ漏洩のリスクが発生する。【０００３】
このため秘匿化されたデータを秘匿化したままで検索できる秘匿検索技術が、種々提案されている。【０００４】
秘匿検索を実現する一つの技術として、マルチパーティ計算（Ｍｕｌｔｉ−Ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ：ＭＰＣ）技術が知られている（例えば、特許文献１、特許文献２参照）。【０００５】
ＭＰＣは、それぞれ秘密情報を持つ２台以上のサーバ装置が協力して計算することで、それぞれの秘密情報を漏らすことなく、秘密情報を入力とする任意の関数値を計算する。ＭＰＣを用いて秘匿検索は、以下のように実現する。まず、預けるデータを秘密分散法（例えば、非特許文献１参照）で上記２台以上のサーバ装置に分散して保持する。
そして、上記関数として「ある部分データを含むデータが秘密分散されてサーバ装置に保存されているときに１を、そうでないときに０を返す関数」のように定義する。【０００６】
ＭＰＣの実現方法として、非特許文献１に記載されている、Ｓｈａｍｉｒのしきい値型秘密分散法（Ｔｈｒｅｓｈｏｌｄ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ：ＴＳＳＳ）がある。まず、非特許文献１について説明する。【０００７】
しきい値型秘密分散法（ＴＳＳＳ）は、秘密情報を複数の分散情報に変換し、変換された分散情報をしきい値以上の個数を集めることによって秘密情報を復元する方法である。しきい値型秘密分散法では、しきい値以下の個数の分散情報からは元の秘密情報が漏れない。【０００８】
非特許文献１のしきい値秘密分散法（ＴＳＳＳ）は、Ｎ台のサーバ装置で有限体Ｚｐに属する数ａを秘密に分散する方法であり、ｋ−１次多項式ｆ_ａ（ｘ）を用いる。この方法では、例えばｆ_ａ（０）＝ａとし、第ｉのサーバ装置（１≦ｉ≦Ｎ）には、それぞれ多項式上の点ｆ_ａ（ｉ）を配る。配られる情報ｆ_ａ（ｉ）をしきい値秘密分散法（ＴＳＳＳ）におけるｘの分散情報と呼ぶ。このとき、ｋ台のサーバ装置が協力すると、多項式上のｋ個の点からｋ−１次多項式ｆ_ａ（ｘ）を一意に復元することができるので、秘密情報であるｆ_ａ（０）を求めることができる。【０００９】
秘密情報ａを、ｐを法とする多項式ｆ_ａ（ｘ）を用いてＮ台のサーバ装置で分散するときに生成される、秘密情報ａの分散情報を、［ａ］_ｐ＝（ｆ_ａ（１），ｆ_ａ（２），…，ｆ_ａ（Ｎ））と記述する。このとき、識別子ｉ（１≦ｉ＜Ｎ）を持つ第ｉのサーバ装置にｆ_ａ（ｉ）が保持されているものとする。【００１０】
非特許文献２は、分散情報を非特許文献１のしきい値秘密分散法（ＴＳＳＳ）で保持する複数台のサーバ装置が、協力計算によって秘密情報を復元することなく算術演算を行うＭＰＣの方法を開示する。次に、非特許文献２の方法について説明する。【００１１】
非特許文献１の方法において、秘密情報ａ＋ｂを分散する多項式ｆ_（ａ＋ｂ）（ｘ）は、秘密情報ａを分散する多項式ｆ_ａ（ｘ）と、秘密情報ｂを分散する多項式ｆ_ｂ（ｘ）との和で書き表すことができる。すなわち、ｆ_（ａ＋ｂ）（ｘ）＝ｆ_ａ（ｘ）＋ｆ_ｂ（ｘ）  ｍｏｄ  ｐとなる。この性質より、識別子ｉを持つ各サーバ装置は、秘密情報ａの分散情報と秘密情報ｂの分散情報とから秘密情報ａ＋ｂの分散情報を計算したいときには、個別に計算を行えばよい。すなわち、各サーバ装置は、ｆ_（ａ＋ｂ）（ｉ）＝ｆ_ａ（ｉ）＋ｆ_ｂ（ｉ）  ｍｏｄ  ｐを個別に計算することによって、サーバ装置間の通信なしに、秘密情報の和を秘密に分散して保持することができる。【００１２】
同様に、秘密情報の積を秘密に分散することも可能である。ただし、積の計算を行う場合にはＮ（Ｎ−１）回の通信を要する。【００１３】
非特許文献２では、このような秘密情報の和と積を秘密に分散する方法を組み合わせて、加法と乗法で計算可能な任意の関数を計算する。【００１４】
上記の通り、非特許文献２の方法によって任意の関数が計算でき、文字列検索を実現することができる。非特許文献１の方法を用いた秘匿検索は、次のように実現される。【００１５】
検索を依頼するクライアント装置は、検索要求データｓに対して、その分散情報を生成して各サーバ装置に送信する。Ｎ台のサーバ装置は、自身が保持するデータｔの部分情報の分散データ［ｔ’_１］_ｐ，…，［ｔ’_ｌ］_ｐと、検索要求データであるｓの分散情報［ｓ］_ｐとから、非特許文献２のマルチパーティ計算（ＭＰＣ）で［ｓ−ｔ’_１］_ｐ，［ｓ−ｔ’_２］_ｐ，…，［ｓ−ｔ’_ｌ］_ｐを計算する。検索要求データと一致した分散データが存在するとき、差の値が０になることに注意する。その後、Ｎ台のサーバ装置は、乱数の分散情報を共有し、非特許文献１に記載の秘密情報の積計算によって差の情報をマスクして、マスクされた差の情報を検索結果の分散情報として出力する。【００１６】
一方、非特許文献３は、乱数の分散情報のサイズを削減する方法が開示されている。非特許文献３では、複製型秘密分散法（Ｒｅｐｌｉｃａｔｅｄ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ：ＲＳＳＳ）が利用されている。【００１７】
まず、非特許文献３に記載された複製型秘密分散法（ＲＳＳＳ）の方法について説明する。ＲＳＳＳは、Ｎ台のサーバ装置で有限体Ｚｑに属する整数ｂを秘密に分散する方法であり、次のような方法で秘密情報を分散する。【００１８】
Ｎ−１個の乱数ｂ_１，ｂ_２，…，ｂ_（Ｎ−１）を選び、ｂ_Ｎ＝ｂ−（ｂ_１＋ｂ_２＋…＋ｂ_（Ｎ−１））  ｍｏｄ  ｑとする（ｑは素数）。ｂ_１，ｂ_２，…，ｂ_（Ｎ−１），ｂ_Ｎをすべて足し合わせると、もとの秘密情報ｂに戻ることに注意する。このｂ_１，ｂ_２，…，ｂ_（Ｎ−１），ｂ_Ｎを、サーバ装置に適当に割り当てることによって、複数台のサーバ装置が協力してｂ_１，ｂ_２，…，ｂ_（Ｎ−１），ｂ_Ｎがすべて揃うときに限り、秘密情報を復元することが出来る。秘密情報を復元することが可能なサーバ装置の組み合わせは、ｂ_１，ｂ_２，…，ｂ_（Ｎ−１），ｂ_Ｎの割り当て方によって任意に設計が可能である。【００１９】
例えば、３台のサーバ装置があり、いずれか２台のサーバ装置が協力したときに秘密情報ｂが復元できるＲＳＳＳは、ｂ＝ｂ_１＋ｂ_２＋ｂ_３となるようにｂ_１，ｂ_２，ｂ_３を生成したのち、（ｂ_１，ｂ_２），（ｂ_２，ｂ_３），（ｂ_３，ｂ_１）のように２つずつの値を各サーバ装置に割り当てることで実現できる。【００２０】
秘密情報ｂを、ｂ＝ｂ_１＋ｂ_２＋…＋ｂ_Ｎ  ｍｏｄ  ｑとなるようなｂ_１，ｂ_２，…，ｂ_Ｎを用いてＲＳＳＳでＮ台のサーバ装置に分散するときに生成されるｂの分散情報を＜ｂ＞ｑ＝（ｖ_１，ｖ_２，…ｖ_ｎ）と書くことにする。このとき、識別子ｉ（１≦ｉ＜Ｎ）を持つサーバ装置にｖ_ｉが保持されているものとする。上記の３台のサーバ装置のうち２台によって復号できるＲＳＳＳの例では、ｖ_１＝（ｂ_１，ｂ_２）、ｖ_２＝（ｂ_２，ｂ_３）、ｖ_３＝（ｂ_３，ｂ_１）である。【００２１】
非特許文献３は、乱数のＲＳＳＳによる分散情報をサーバ装置間で共有しておき、この乱数の分散情報を用いて、通信を伴わない計算によって、疑似乱数のＳＳＳによる分散情報を生成する方法を記載している。この方法を用いると、ＳＳＳの乱数の分散情報は計算時に必要に応じて生成できるので、事前に分散しておく必要がない。したがって、保持する乱数の分散情報のサイズは小さくなる。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２００７−１１４４９４号公報
【特許文献２】特開２０１２−０２４１８２号公報
【非特許文献】
【００２３】
【非特許文献１】Ａｄｉ  Ｓｈａｍｉｒ，  “Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”  Ｃｏｍｍｕｎ．  ＡＣＭ  ２２（１１），  ｐｐ．６１２−６１３，  １９７９．
【非特許文献２】Ｍｉｃｈａｅｌ  Ｂｅｎ−Ｏｒ，  Ｓｈａｆｉ  Ｇｏｌｄｗａｓｓｅｒ  ａｎｄ  Ａｖｉ  Ｗｉｇｄｅｒｓｏｎ，  “Ｃｏｍｐｌｅｔｅｎｅｓｓ  Ｔｈｅｏｒｅｍｓ  ｆｏｒ  Ｎｏｎ−Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｆａｕｌｔ−Ｔｏｌｅｒａｎｔ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔａｔｉｏｎ  （Ｅｘｔｅｎｄｅｄ  Ａｂｓｔｒａｃｔ），”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０ｔｈ  Ａｎｎｕａｌ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，  １９８８．
【非特許文献３】Ｒｏｎａｌｄ  Ｃｒａｍｅｒ，  Ｉｖａｎ  Ｄａｍｇａｒｄ，  Ｙｕｖａｌ  Ｉｓｈａｉ，  ”Ｓｈａｒｅ  Ｃｏｎｖｅｒｓｉｏｎ，  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｓｅｃｒｅｔ−Ｓｈａｒｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｓｅｃｕｒｅ  Ｃｏｍｐｕｔａｔｉｏｎ，”  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｓｅｃｏｎｄ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ（ＴＣＣ），ｐｐ．  ３４２−３６２，  ２００５．
【発明の概要】
【発明が解決しようとする課題】
【００２４】
非特許文献１を用いた方法では、次に述べるような問題がある。ｎシンボルのデータＴ＝（ｔ_１，ｔ_２…，ｔ_ｎ）に対して任意の長さの検索要求データｓ＝（ｓ_１，…，ｓ_ｍ）（ただし、ｎ＞ｍとする）の検索に対応するとする。この場合、上記のような検索を実行するために、各サーバ装置はＳＳＳによるＴのあらゆる部分データに対する分散情報を保持する必要がある。具体的には、非特許文献１を用いた方法では、任意の１≦ｉ＜ｊ≦ｎに対して（ｔ_ｉ，…，ｔ_ｊ）の分散情報を保持する必要がある。したがって、非特許文献１を用いた方法には、元データの（ｔ_１，ｔ_２…，ｔ_ｎ）に対して、各サーバ装置が保持すべき分散情報のデータサイズが非常に大きくなるという課題がある。【００２５】
一方、非特許文献３の方法は任意に選べるデータではなく、乱数の分散情報のサイズを削減するための方法である。秘匿検索という目的において、分散されるデータは秘匿検索システムの利用者の秘密情報であり、乱数ではない。そのため、非特許文献３の方法を、秘匿検索にそのまま適用することができない。【００２６】
本発明の目的は、秘密分散法を用いた秘匿検索システムにおいて、その検索機能を損なうことなく、各サーバ装置が保持するデータ（分散情報）のサイズを低減する、サーバ装置、検索方法等を提供することにある。
【課題を解決するための手段】
【００２７】
本発明のサーバ装置は、秘密情報の１シンボルごとの分散登録データを保存するデータ記憶部と；前記データ記憶部に保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換するデータ変換部と；前記検索用データと分散検索要求データとを用いて、他のサーバ装置のデータ検索部と通信を行いながら、前記データ記憶部の前記分散登録データに対する検索を行って、分散検索結果を出力するデータ検索部と；を有する。【００２８】
本発明の検索方法は、サーバ装置で検索を実行する検索方法であって、秘密情報の１シンボルごとの分散登録データを保存し、保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換し、前記検索用データと分散検索要求データとを用いて、他のサーバ装置と通信し、前記分散登録データに対する検索を行って、分散検索結果を出力する。【００２９】
本発明の記録媒体は、コンピュータに、秘密情報の１シンボルごとの分散登録データを保存し、保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換し、前記検索用データと分散検索要求データとを用いて、他のサーバ装置と通信し、前記分散登録データに対する検索を行って、分散検索結果を出力する、ことを実行させる検索プログラムを格納した記録媒体。
【発明の効果】
【００３０】
本発明によれば、各サーバ装置に保存するデータ（分散情報）のサイズを削減することができる。
【図面の簡単な説明】
【００３１】
【図１】第１の実施形態に係る秘匿検索システムの構成を示すブロック図である。
【図２】第１の実施形態の秘匿検索システムにおけるサーバ装置の構成を示すブロック図である。
【図３】第１の実施形態の秘匿検索システムにおけるクライアント装置の構成を示すブロック図である。
【図４】第１の実施形態の秘匿検索システムにおけるデータ登録時の処理を示すフローチャートである。
【図５】第１の実施形態の秘匿検索システムにおけるデータ検索時の処理を示すフローチャートである。
【図６】第２の実施形態に係る秘匿検索システムの構成を示すブロック図である。
【図７】第２の実施形態の秘匿検索システムにおけるサーバ装置の構成を示すブロック図である。
【図８】第２の実施形態の秘匿検索システムにおけるクライアント装置の構成を示すブロック図である。
【図９】第２の実施形態の秘匿検索システムのデータ登録時の処理を示すフローチャートである。
【図１０】第１の実施形態の秘匿検索システムにおけるデータ検索時の処理を示すフローチャートである。
【発明を実施するための形態】
【００３２】
はじめに、本発明の実施形態の概要について説明する。
［実施形態の概要］
【００３３】
関連技術による方法では、各サーバ装置は検索可能な部分文字列の分散情報を全て持つ必要があった。これに対し、本実施形態では、検索として長さｍシンボル分のデータが入力されたときに、１シンボルごとに分散された秘密情報から、ｍシンボルを連結した秘密情報の分散情報を生成する処理を行う。
【００３４】
秘密情報の分散情報を生成するために秘密情報を１シンボルごとに持つ方法として、複製型秘密分散法を用いる方法（第１の方法）と、Ｓｈａｍｉｒのしきい値型秘密分散法を用いる方法（第２の方法）とがある。
【００３５】
第１の方法では、１シンボルごとの複製型秘密分散法の分散情報を連結したｍシンボルの分散情報に変換するために、複製型秘密分散法（ＲＳＳＳ）の分散情報をＳｈａｍｉｒのしきい値型秘密分散法（ＴＳＳＳ）の分散情報に変換する手法を利用する。このとき、分散情報のサイズが大きくなるために、元の秘密情報がうまく復元できない可能性がある。そこで、これを補正するため、分散情報を復号せずに大小比較を行うマルチパーティ計算（ＭＰＣ）を利用する。
【００３６】
一方、検索対象の秘密情報をしきい値型秘密分散法（ＴＳＳＳ）で分散する方法（第２の方法）では、小さい体上のしきい値型秘密分散法（ＴＳＳＳ）で生成された分散情報を、拡大体上のしきい値型秘密分散法の分散情報として扱うことで分散情報の連結を行う。
【００３７】
本実施形態の秘匿検索システムは、Ｎ台のサーバ装置と１台のクライアント装置とから成る。本実施形態のサーバ装置は、秘匿検索システムの中の１つの計算装置である。
【００３８】
換言すると、本実施形態では、各サーバ装置に保存するデータを１シンボルごとの分散情報として保管する。そして、検索処理時に必要な部分データに対応する分散情報を生成する前処理を行ってから検索を行うという方法を取る。これによって、各サーバ装置に保存するデータ（分散情報）のサイズを削減する。
【００３９】
本実施形態の秘匿検索システムは、Ｎ個のサーバ装置に分散されて保持された複数のデータの中に、ユーザが指定した部分データを含むデータが存在するかどうかを、データを復号することなく、またユーザが指定したデータをサーバに明かすことなく検索することができる。
【００４０】
このとき、各サーバ装置が保持する分散データのデータ量は、例えば、上記第１の方法で分散前のデータの１２倍程度である。非特許文献２を利用した通常の秘匿検索と比較して、後述する実施形態では、データの変換処理以外は同等の計算コストであり、データの変換処理を各サーバ装置が個々に計算することが出来る。このため、本実施形態の秘匿検索システムは、データの変換処理に通信を必要とせず、高速に実行できる。
【００４１】
関連技術において、任意の長さのデータを検索するときに、複数シンボルをまとめて秘密計算することで、サーバ装置間の通信の回数を減らそうとすると、あらゆる長さの部分データに対する分散データを全て持つ必要があり、保持しなければならないデータのサイズが増大するという問題があった。
【００４２】
これに対して、本実施形態では、各サーバ装置は秘密情報の１シンボルごとの部分データを保持する。そして、ｍシンボルの検索要求データの部分情報が入力されたときに、各サーバ装置は、秘密情報のｍシンボル分の部分データに対応する分散情報を、通信を伴わない処理によって生成する。このため、本実施形態では、事前に保持する分散データのデータ量を増やさずに通信回数を減らすことができる。
【００４３】
本実施形態を用いれば、複数のサーバ装置にデータを分散して、各サーバ装置にデータを隠ぺいしたまま任意のデータに対する検索を行うことができる。これはあるサーバ装置で秘密のデータを外部のサーバ装置に委託する何らかのサービスを提供するときに、サーバ装置の管理者がデータを盗み出すことを防止することになる。すなわち、複数の管理者が結託しない限り、サーバ装置の中の秘密情報を管理者が復号することは不可能であり、サービス利用者の秘密情報を保護することに貢献する。
【００４４】
本実施形態は、例えば、関連技術と比べて、データサイズをおよそ１／８０から１／１０００に削減する効果がある。
【００４５】
本発明の実施形態について、図面を用いて詳細に説明する。なお、実施形態の構成を示す図において図面中の矢印の方向は、一例を示すものであり、ブロック間の信号の向きを限定するものではない。
［第１の実施形態］
図１乃至図３を参照して、本発明の第１の実施形態に係る秘匿検索システムについて説明する。
【００４６】
［構成の説明］
図１は、本発明の第１の実施形態に係る秘匿検索システムの構成を示すブロック図である。
【００４７】
図１を参照すると、本発明の第１の実施形態に係る秘匿検索システムは、Ｎ（Ｎは２以上の整数）台のサーバ装置１００_１、１００_２、…、１００_Ｎと、クライアント装置２００とからなる。ここでは、サーバ装置１００_１〜１００_Ｎを、それぞれ、第１乃至第Ｎのサーバ装置とも呼ぶ。クライアント装置２００は、Ｎ台のサーバ装置１００_１〜１００_Ｎと通信する。また、Ｎ台のサーバ装置１００_１〜１００_Ｎは互いに通信する。
【００４８】
図２は、第ｎのサーバ装置１００_ｎ（１≦ｎ≦Ｎ）の構成を示すブロック図である。第ｎのサーバ装置１００_ｎは、第ｎのデータ記憶部１０１_ｎと、第ｎのデータ変換部１０２_ｎと、第ｎのデータ検索部１０３_ｎとを備える。
【００４９】
第ｎのデータ記憶部１０１_ｎは、後述するクライアント装置２００から第ｎの分散登録データ１０４_ｎを受け、それを保存する。また、検索時には、第ｎのデータ記憶部１０１_ｎは、保存した第ｎの分散登録データを第ｎのデータ変換部１０２_ｎに出力する。第ｎのデータ変換部１０２_ｎは、第ｎのデータ記憶部１０１_ｎに保存された第ｎの分散登録データを、第ｎの検索用の分散情報（第ｎの検索用データ）１０５_ｎに変換する。
【００５０】
第ｎのデータ検索部１０３_ｎは、第ｎのデータ変換部１０２_ｎから受けた第ｎの検索用データ１０５_ｎと、クライアント装置２００から受けた第ｎの分散検索要求データ１０６_ｎとを用いて、他のデータ検索部１０３_１〜１０３_Ｎ（１０３_ｎを除く）と互いに通信を行いながら、第ｎのデータ記憶部１０１_ｎの第ｎの分散登録データに対する検索を行って、第ｎの分散検索結果１０７_ｎを出力する。
【００５１】
図３は、クライアント装置２００の構成を示すブロック図である。クライアント装置２００は、登録データシェア生成部２０１と、クエリデータシェア生成部２０２と、秘密分散復号部２０３とを備える。
【００５２】
登録データシェア生成部２０１は、図示しない入力装置から登録データ２０４を受ける。登録データシェア生成部２０１は、登録データ２０４に対して秘密分散法を用いて、第１乃至第Ｎの分散登録データ１０４_１、…、１０４_Ｎを生成する。登録データシェア生成部２０１は、第ｎの分散登録データ１０４_ｎ（１≦ｎ≦Ｎ）を第ｎのサーバ装置１００_ｎに送信する。
【００５３】
クエリデータシェア生成部２０２は、図示しない入力装置から検索要求データ２０５を受ける。クエリデータシェア生成部２０２は、検索要求データ２０５に対して秘密分散法を用いて、第１乃至第Ｎの分散検索要求データ１０６_１、…、１０６_Ｎを生成する。クエリデータシェア生成部２０２は、第ｎの分散検索要求データ１０６_ｎ（１≦ｎ≦Ｎ）を第ｎのサーバ装置１００_ｎに送信する。
【００５４】
秘密分散復号部２０３は、第ｎのサーバ装置１００_ｎ（１≦ｎ≦Ｎ）から第ｎの分散検索結果１０７_ｎを受ける。秘密分散復号部２０３は、第１乃至第Ｎの分散検索結果１０７_１、…、１０７_Ｎに対して秘密分散法を用いて、検索結果２０６を復元する。
【００５５】
［動作の説明］
次に、図１から図５を用いて、本発明の第１の実施形態に係る秘匿検索システムの動作について詳細に説明する。
【００５６】
本発明の第１の実施形態に係る秘匿検索システムは、（１）データ登録処理と、（２）データ検索処理と、の２種類の処理を行う。図４、５は、それぞれ、データ登録処理およびデータ検索処理を示すフローチャートである。
【００５７】
（データ登録処理）
図４は、本発明の第１の実施形態における秘匿検索システムのデータ登録処理の動作を示すフローチャートである。
【００５８】
新規データを第１乃至第Ｎのサーバ装置１００_１、…、１００_Ｎに登録するときには、以下のようにする。
【００５９】
秘匿検索システムは、新規に分散したい登録データ２０４（ｔ_１，…，ｔ_ｎ）を、クライアント装置２００の登録データシェア生成部２０１に入力する。ただし、ｔ_１，…，ｔ_ｎはそれぞれデータの１シンボルに対応するものであり、それぞれのサイズはｌｏｇｑとする（ｑは素数、底は２）（ステップＳ１０１）。なお、以降のｌｏｇも底は２であるが、省略してｌｏｇとして記載する。
【００６０】
登録データシェア生成部２０１は、登録データ２０４をＲＳＳによって第ｎの分散登録データ１０４_ｎ（１≦ｎ≦Ｎ）に変換する（ステップＳ１０２）。
【００６１】
詳述すると、まず、登録データシェア生成部２０１は、１≦ｉ≦ｎについて、ｔ_ｉ＝ｔ｛ｉ，１｝＋ｔ_｛ｉ，２｝＋…＋ｔ_｛ｉ，Ｎ｝  ｍｏｄ  ｑとなるようなｔ_｛ｉ，１｝，…，ｔ_｛ｉ，Ｎ｝を生成し、適当な組み合わせで各サーバ装置に割り当てることによって、各シンボルｉ  （１≦ｉ≦ｎ）について、＜ｔ_ｉ＞ｑ＝（（ｔ_｛１，１｝，…，ｔ_｛Ｎ，１｝），（ｔ_｛１，２｝，…，ｔ_｛Ｎ，２｝），…，（ｔ_｛１，Ｎ｝，…，ｔ_｛Ｎ，Ｎ｝））を生成する。
【００６２】
また、登録データシェア生成部２０１は、（ｎ−１）ｑ  ≦  ｔ_ｉ  ＜  ｑであればｂ_ｉ＝ｎとし、ｂ_ｉのＳＳＳによる分散情報［ｂ_ｉ］_ｐ＝（ｂ_｛ｉ，１｝，ｂ_｛ｉ，２｝，…，ｂ_｛ｉ，Ｎ｝）を生成する。このとき，ｔ_｛ｉ，１｝＋ｔ_｛ｉ，２｝＋…＋ｔ_｛ｉ，Ｎ｝＝ｔ_ｉ＋ｂ_ｉ  ・ｑとなることに注意する。
【００６３】
第ｎの分散登録データ１０４_ｎは，ｔ_ｉの分散情報（ｔ_｛１，ｎ｝，…，ｔ｛Ｎ，ｎ｝）とｂ_ｉの分散情報ｂ_｛ｉ，ｎ｝の組とする。
【００６４】
登録データシェア生成部２０１は、第ｎの分散登録データ１０４_ｎを第ｎのサーバ装置１００_ｎ  （１≦ｎ≦Ｎ）に送信する（ステップＳ１０３）。
【００６５】
（ステップＳ１０４）第ｎのサーバ装置１００_ｎ（１≦ｎ≦Ｎ）は受信した第ｎの分散登録データ１０４_ｎを第ｎのデータ記憶部１０１_ｎに保存する。
【００６６】
（データ検索処理）
図５は、本発明の第１の実施形態における秘匿検索システムのデータ検索時の動作を示すフローチャートである。
【００６７】
第１乃至第Ｎのサーバ装置１００_１、…、１００_Ｎに分散されたデータＴ＝（ｔ_１，ｔ_２，…，ｔ_ｎ）の組に関して、ある部分データ（ｓ_１，…，ｓ_ｍ）を含むデータが存在するかどうかを検索したいときには次のようにする。
【００６８】
秘匿検索システムは、検索を行いたいデータである検索要求データ２０５  （ｓ_１，…，ｓ_ｍ）を、クライアント装置２００のクエリデータシェア生成部２０２に入力する（ステップＳ２０１）。ｓ_１，…，ｓ_ｍは検索要求データの各文字を表すものであり、それぞれのサイズはｌｏｇｑである。
【００６９】
クエリデータシェア生成部２０２は、非特許文献１のＴＳＳＳの方法で、下記数１のような形の第１乃至第Ｎの分散検索要求データ（１０６_１、…、１０６_Ｎ）［ｓ_１  ｓ_２  …  ｓ_ｍ］_ｐを生成する（ステップＳ２０２）。
【００７０】
【数１】
2016136201.tif 000003
【００７１】
そして、クエリデータシェア生成部２０２は、第ｎの分散検索要求データ１０６_ｎを第ｎのサーバ装置１００_ｎの第ｎのデータ検索部１０３_ｎに送信する。ただし、ｌｏｇｐ＝ｌｏｇｑ×ｍとする（ｐ、ｑは素数、ｍは任意の正の整数でｍ＞ｎ）。
【００７２】
第ｎのサーバ装置１００_ｎ（１≦ｎ≦Ｎ）は、第ｎのデータ記憶部１０１_ｎから第ｎの分散登録データを読み出し、第ｎのデータ変換部１０２_ｎに送信する（ステップＳ２０３）。分散登録データはｎ文字のテキストそれぞれについて、＜ｔ_１＞ｑ，…，＜ｔ_ｎ＞ｑの形で分散されていることに注意する。
【００７３】
第ｎのデータ変換部１０２_ｎはまず、第ｎのデータ記憶部１０１_ｎから受けたＲＳＳの分散データ＜ｔ_１＞ｑ，…，＜ｔ_ｎ＞ｑを、非特許文献３に記載の方法でＳＳＳの分散情報［ｔ＊_１］_ｐ，…，［ｔ＊_ｎ］_ｐに変換する（ステップＳ２０４）。
【００７４】
このとき，ｔ＊_ｉ＝ｔ_ｉ＋ｂ_ｉ・ｑとなっているので，以下の計算によってｂ_ｉに補正する。
【００７５】
第ｎのデータ変換部１０２_ｎは、各ｔ_ｉについて，［ｔ’_ｉ］_ｐ＝［ｔ＊_ｉ］_ｐ−ｑ×［ｂ_ｉ］_ｐを計算することによって，分散情報［ｔ’_１］_ｐ，［ｔ’_２］_ｐ，…［ｔ’_ｎ］_ｐを生成する。
【００７６】
第ｎのデータ変換部１０２_ｎは、非特許文献２に記載の方法を用いて、和と定数倍の計算は通信を要さずに実行できることを利用して、下記数２のようにｍシンボルを結合したデータに関するＳＳＳの分散データに変換する。
【００７７】
【数２】
2016136201.tif 000004
【００７８】
第ｎのデータ変換部１０２_ｎは、［ｓ’］_ｐを第ｎの検索用データ１０５_ｎとして第ｎのデータ検索部１０３_ｎに送出する。
【００７９】
第ｎのデータ検索部１０３_ｎは、第ｎのデータ変換部１０２_ｎから送られた第ｎの検索用データ１０５_ｎと、クエリデータシェア生成部２０２から送信された第ｎの分散検索要求データ１０６_ｎを用いて、下記数３の計算によって、分散データ  ［ｓ’_０］_ｐ，…，［ｓ’_｛ｎ−ｍ｝］_ｐを生成する（ステップＳ２０５）。
【００８０】
【数３】
2016136201.tif 000005
【００８１】
もし検索対象の部分データであるｔ’_１，…，ｔ’_（ｎ−ｍ）のいずれかが検索要求データと一致した場合、ｓ’_０，…，ｓ’_（ｎ−ｍ）のいずれかが０になることに注意する。
【００８２】
その後、第１乃至第Ｎのデータ検索部１０３_１〜１０３_Ｎは、互いに通信しながら、下記数４のような計算を行い、第ｎのデータ検索部１０３_ｎは、得られた結果を第ｎの分散検索結果１０７_ｎとしてクライアント装置２００に送信する。
【００８３】
【数４】
2016136201.tif 000006
【００８４】
クライアント装置２００は、第１乃至第Ｎのサーバ装置１００_１、…、１００_Ｎから受け取った第１乃至第Ｎの分散検索結果１０７_１、…、１０７_Ｎをすべて秘密分散復号部２０３に入力し、検索結果２０６を復号する（ステップＳ２０６）。復号された結果が０であったときは、登録データの中に検索要求データを含むデータが存在することを意味し、０でなかったときは、そのようなデータは存在しなかったことを示す。
【００８５】
（第１の実施形態の効果）
第１の実施形態によれば、各サーバ装置に保存するデータ（分散情報）のサイズを削減することができる。その理由は、各サーバ装置に保存するデータを１シンボルごとの分散情報として保管する。そして、検索処理時に必要な部分データに対応する分散情報を生成する前処理を行ってから検索するからである。
【００８６】
第１の実施形態では、秘密情報を１シンボルごとにＲＳＳＳで保管し、データ変換部ではこれを非特許文献３の方法でＴＳＳＳの分散情報に変換する。このとき、非特許文献３の方法で変換した分散情報はｔ_ｉの分散情報ではなくｔ＊_ｉ＝ｔ_ｉ＋ｂ_ｉ・ｑの分散情報になっている可能性がある。そこで、ｔ_ｉとともにｂ_ｉを分散しておき、［ｔ_ｉ］_ｐ＝［ｔ＊_ｉ］_ｐ−ｑ×［ｂ_ｉ］_ｐの計算を行うことによって、分散情報の変換後も同じ秘密情報に復元されるように補正を行っている。上記数２の式によって計算される値はｔ’_ｉの分散情報であり、ｔ’_ｉはｑビットごとに（ｔ_１，…，ｔ_ｎ）の各シンボルであるので、ｍシンボルの部分データに対する分散情報になっている。ｔ’_ｉと検索要求データｓ’との差を取ったのちに乱数でマスクをかける操作は、ｍ個のシンボルそれぞれに関して差を取ってマスクをかける操作と同様の効果がある。
【００８７】
［第２の実施形態］
次に、図６乃至図８を参照して、本発明の第２の実施形態に係る秘匿検索システムについて説明する。
【００８８】
［構成の説明］
図６は、本発明の第２の実施形態に係る秘匿検索システムの構成を示すブロック図である。
【００８９】
図６を参照すると、第２の実施形態に係る秘匿検索システムは、クライアント装置２００Ａと、第１乃至第Ｎのサーバ装置１００Ａ_１、１００Ａ_２、…、１００Ａ_Ｎとを備える。サーバ装置１００Ａ_１〜１００Ａ_Ｎは、それぞれ、第１乃至第Ｎのサーバ装置とも呼ばれる。クライアント装置２００Ａは、Ｎ台のサーバ装置１００Ａ_１〜１００Ａ_Ｎと通信する。また、Ｎ台のサーバ装置１００Ａ_１、…、１００Ａ_Ｎは互いに通信する。
【００９０】
図７は、第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦Ｎ）の構成を示すブロック図である。
第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦Ｎ）は、第ｎのデータ記憶部１０１Ａ_ｎと、第ｎのデータ変換部１０２Ａ_ｎと、第ｎのデータ検索部１０３Ａ_ｎとを備える。
【００９１】
第ｎのデータ記憶部１０１Ａ_ｎは、クライアント装置２００Ａから第ｎの分散登録データ１０４Ａ_ｎを受け、それを保存する。また、第ｎのデータ記憶部１０１Ａ_ｎは、検索時に保存した第ｎの分散登録データ１０４Ａ_ｎを第ｎのデータ変換部１０２Ａ_ｎに出力する。第ｎのデータ変換部１０２Ａ_ｎは、第ｎのデータ記憶部１０１Ａ_ｎに保存された第ｎの分散登録データを第ｎの検索用の分散情報（検索用データ）１０５Ａ_ｎに変換する。
【００９２】
第ｎのデータ検索部１０３Ａ_ｎは、第ｎのデータ変換部１０２Ａ_ｎから受けた第ｎの検索用データ１０５Ａ_ｎと、クライアント装置２００Ａから受けた第ｎの分散検索要求データ１０６Ａ_ｎとを用いて、他のデータ検索部１０３Ａ_１〜１０３Ａ_Ｎ（１０３Ａ_ｎを除く）と互いに通信しながら、第ｎのデータ記憶部１０１Ａ_ｎの第ｎの分散登録データに対する検索を行って、第ｎの分散検索結果１０７Ａ_ｎを出力する。
【００９３】
図８は、クライアント装置２００Ａの構成を示すブロック図である。クライアント装置２００Ａは、登録データシェア生成部２０１Ａと、クエリデータシェア生成部２０２Ａと、秘密分散復号部２０３Ａとを備える。
【００９４】
登録データシェア生成部２０１Ａは、図示しない入力装置から登録データ２０４Ａを受ける。登録データシェア生成部２０１Ａは、秘密分散法の分散データ生成手順を実行して、第１乃至第Ｎの分散登録データ１０４Ａ_１、…、分散登録データ１０４Ａ_Ｎを生成する。登録データシェア生成部２０１Ａは、第ｎの分散登録データ１０４Ａ_ｎ（１≦ｎ≦Ｎ）を第ｎのサーバ装置１００Ａ_ｎに送信する。
【００９５】
クエリデータシェア生成部２０２Ａは、図示しない入力装置から検索要求データ２０５Ａを受ける。クエリデータシェア生成部２０２Ａは、秘密分散法の分散データ生成手順を実行して、第１乃至第Ｎの分散検索要求データ１０６Ａ_１、…、１０６Ａ_Ｎを生成する。クエリデータシェア生成部２０２Ａは、第ｎの分散検索要求データ１０６Ａ_ｎ（１≦ｎ≦Ｎ）を第ｎのサーバ装置１００Ａ_ｎに送信する。
【００９６】
秘密分散復号部２０３Ａは、第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦Ｎ）から第ｎの分散検索結果１０７Ａ_ｎを受ける。秘密分散復号部２０３Ａは、第１乃至第Ｎの分散検索結果１０７Ａ_１、…、１０７Ａ_Ｎに対して秘密分散法の復号手順を実行して、検索結果２０６Ａを復元する。
【００９７】
［動作の説明］
次に、図６から図１０を用いて、本発明の第２の実施形態に係る秘匿検索システムの動作について詳細に説明する。
【００９８】
本発明の第２の実施形態に係る秘匿検索システムは、（１）データ登録処理と、（２）データ検索処理と、の２種類の処理を行う。図９、図１０は、それぞれ、データ登録処理およびデータ検索処理のフローを示すフローチャートである。
【００９９】
（データ登録処理）
図９は、本発明の第２の実施形態における秘匿検索システムのデータ登録時の動作を示すフローチャートである。
【０１００】
新規データを第１乃至第Ｎのサーバ装置１００Ａ_１、…、１００Ａ_Ｎに登録するときには以下のようにする。
【０１０１】
秘匿検索システムは、新規に分散したい登録データ２０４Ａ  （ｔ_１，…，ｔ_ｎ）をクライアント装置２００Ａの登録データシェア生成部２０１Ａに入力する（ステップＳ１０１Ａ）。ただし、ｔ_１，…，ｔ_ｎはそれぞれデータの１シンボルに対応するものであり、各ｔ_ｉは有限体ＧＦ（ｑ）の元とする。
【０１０２】
登録データシェア生成部２０１Ａは、１≦ｉ≦ｎについて、ＳＳＳによるｔ_ｉのシェア［ｔ_ｉ］ｑを生成し，［ｔ_１］ｑ，…［ｔ_ｎ］ｑをそれぞれ第１乃至第Ｎの分散登録データ１０４Ａ_１，…，１０４Ａ_Ｎとする（ステップＳ１０２Ａ）。
【０１０３】
登録データシェア生成部２０１Ａは、第ｎの分散登録データ１０４Ａ_ｎを第ｎのサーバ装置１００Ａ_ｎ  （１≦ｎ≦Ｎ）に送信する（ステップＳ１０３Ａ）。
【０１０４】
第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦Ｎ）は、受信した第ｎの分散登録データ１０４Ａ_ｎを第ｎのデータ記憶部１０１Ａ_ｎに保存する（ステップＳ１０４Ａ）。
【０１０５】
（データ検索処理）
図１０は、本発明の第２の実施形態における秘匿検索システムのデータ検索時の動作を示すフローチャートである。
【０１０６】
第１乃至第Ｎのサーバ装置１００Ａ_１、…、１００Ａ_Ｎに分散されたデータＴ＝（ｔ_１，ｔ_２，…，ｔ_ｎ）の組に関して、ある部分データ（ｓ_１，…，ｓ_ｍ）を含むデータが存在するかどうかを検索したいときには次のようにする。
【０１０７】
秘匿検索システムは、検索を行いたいデータである検索要求データ２０５Ａ（ｓ_１，…，ｓ_ｍ）を、クライアント装置２００Ａのクエリデータシェア生成部２０２Ａに入力する（ステップＳ２０１Ａ）。ｓ_１，…，ｓ_ｍは検索要求データの各文字を表すものであり、それぞれのサイズはｌｏｇｑである。
【０１０８】
クエリデータシェア生成部２０２Ａは、検索要求データ２０５Ａ（ｓ_１，…，ｓ_ｍ）から、ＳＳＳの分散情報［ｓ］_ｐ＝［ｓ_１  ||  ｓ_２  ||  …  ||  ｓ_ｍ］_ｐを生成する（ステップＳ２０２Ａ）。ただし、ｐ＝ｑ＾ｍであり、ｓは有限体ＧＦ（ｑ＾ｍ）の元である。クエリデータシェア生成部２０２Ａは、第ｎの分散検索要求データ１０６Ａ_ｎ（１≦ｎ≦Ｎ）を第ｎのサーバ装置１００Ａ_ｎに送信する。
【０１０９】
第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦Ｎ）は、第ｎのデータ記憶部１０１Ａ_ｎから第ｎの分散登録データを読み出し、第ｎのデータ変換部１０２Ａ_ｎに送出する（ステップＳ２０３Ａ）。
【０１１０】
第ｎのデータ変換部１０２Ａ_ｎはまず、第ｎのデータ記憶部１０１Ａ_ｎから受けたＳＳＳの分散情報［ｔ_１］ｑ，…，［ｔ_ｎ］ｑを、以下の方法で検索用データに変換する（ステップＳ２０４Ａ）。
【０１１１】
第ｎのデータ変換部１０２Ａ_ｎは、各ｔ_ｉについて［ｔ_ｉ］ｑ＝（ｔ_｛ｉ，１｝，ｔ_｛ｉ，２｝，．．．，ｔ_｛ｉ，Ｎ｝）のうち、自らが保持する分散情報ｔ_｛１，ｊ｝，ｔ_｛２，ｊ｝，．．．，ｔ_｛ｎ，ｊ｝を用いて、ｔ’_｛ｉ，ｊ｝＝ｔ_｛ｉ，ｊ｝  ||  ｔ_｛ｉ＋１，ｊ｝  ||  …  ||  ｔ_｛ｉ＋ｍ−１，ｊ｝を０≦ｉ≦ｎ−ｍについて計算し、ｔ’_｛０｝，．．．，ｔ’_｛ｎ−ｍ｝を得る。ｔ’_｛ｉ，１｝，．．．，ｔ’_｛ｉ，Ｎ｝は、ｔ’_｛ｉ｝＝ｔ_｛ｉ｝  ||  …  ||  ｔ_｛ｉ＋ｍ−１｝の分散情報である。すなわち、［ｔ’_ｉ］_ｐ＝［ｔ_｛ｉ｝  ||  …  ||  ｔ_｛ｉ＋ｍ−１｝］_ｐである。ただし、ｐ＝ｑ＾ｍであり、各ｔ’_ｉは有限体ＧＦ（２＾ｑ）の元である。
【０１１２】
第ｎのデータ変換部１０２Ａ_ｎは、［ｔ’_０］_ｐ，．．．，［ｔ’_｛ｎ−ｍ｝］_ｐを第ｎの検索用データ１０５Ａ_ｎとして、第ｎのデータ検索部１０３Ａ_ｎに送出する。
【０１１３】
第ｎのデータ検索部１０３Ａ_ｎは、第ｎのデータ変換部１０２Ａ_ｎから送られた第ｎの検索用データ１０５Ａ_ｎと、クエリデータシェア生成部２０２Ａから送信された第ｎの分散検索要求データ１０６Ａ_ｎを用いて、上記数３の計算によって、分散データ［ｓ’_０］_ｐ，…，［ｓ’_｛ｎ−ｍ｝］_ｐを生成する（ステップＳ２０５Ａ）。もし検索対象の部分データであるｔ’_０，…，ｔ’_（ｎ−ｍ）のいずれかが検索要求データと一致した場合、ｓ’_０，…，ｓ’_｛ｎ−ｍ｝のいずれかが０になることに注意する。
【０１１４】
その後、第ｎのデータ検索部１０３Ａ_ｎは、上記数４のような計算を行い、得られた結果を第ｎの分散検索結果１０７Ａ_ｎとして、クライアント装置２００Ａに送信する。
【０１１５】
クライアント装置２００Ａは、第１乃至第Ｎのサーバ装置１００Ａ_１、…、１００Ａ_Ｎから受け取った第１乃至第Ｎの分散検索結果１０６Ａ_１、…、１０６Ａ_Ｎをすべて秘密分散復号部２０３Ａに入力し、検索結果２０６Ａを復号する（ステップＳ２０６Ａ）。復号された結果が０であったときは、登録データの中に検索要求データを含むデータが存在することを意味し、０でなかったときは、そのようなデータは存在しなかったことを示す。
【０１１６】
（第２の実施形態の効果）
第２の実施形態によれば、各サーバ装置に保存するデータ（分散情報）のサイズを削減することができる。その理由は、各サーバ装置に保存するデータを１シンボルごとの分散情報として保管する。そして、検索処理時に必要な部分データに対応する分散情報を生成する前処理を行ってから検索するからである。
【０１１７】
第２の実施形態において、秘密情報は１シンボルごとにＴＳＳＳで分散されており、データ変換部ではこれをステップＳ２０４Ａのｔ’_｛ｉ，ｊ｝＝ｔ_｛ｉ，ｊ｝  ||  ｔ_｛ｉ＋１，ｊ｝  ||  …  ||  ｔ_｛ｉ＋ｍ−１，ｊ｝のように連結する。各シンボルｔ_｛１，ｊ｝，ｔ_｛２，ｊ｝，．．．，ｔ_｛ｎ，ｊ｝が有限体ＧＦ（ｑ）の元であるとき、これをｍ個連結したものは有限体ＧＦ（ｑ＾ｍ）の元であり、もとの秘密情報ｔ＝（ｔ１，…，ｔ_ｎ）のうちのｍシンボルの部分データに対する分散情報になっている。これにより、上記第１の実施形態と同様に、ｍシンボル分に対する操作をまとめて実行することがでる。
【０１１８】
［実施形態の具体例］
上記第１の実施形態の具体例として、３台のサーバ装置１００_１、１００_２、１００_３と、クライアント装置２００とで構成された文字列検索システムの構成を示す。
【０１１９】
この第１の実施形態の具体例では、テキストの元データはそれぞれ最大２００文字とし、Ｔ＝（ｔ_１，…，ｔ_２００）の形で表現され、ｔ_ｉ（１≦ｉ≦ｎ）はテキストの各文字を表す。３台のサーバ装置１００_１、１００_２、１００_３には文字列の組が１文字ごとにＲＳＳＳを用いて＜ｔ_１＞ｑ，…，＜ｔ_２００＞ｑのように分散されて保管されている。各文字は８ビットで符号化されており、ｑ＝２＾８とする。第１の実施形態の具体例では、クライアント装置２００が検索を要求するキーワードの長さは１０文字とする。すなわち、検索要求データは最大８０ビットの文字列であり、ｐ＝２＾８０とする。
【０１２０】
クライアント装置２００は、検索要求データとして、１０文字のテキストｓ＝（ｓ_１，ｓ_２，…，ｓ_１０）＝“ｃａｌｃｕｌａｔｏｒ”をＳＳＳで［（“ｃａｌｃｕｌａｔｏｒ”）］_ｐ＝［２＾（７２）・”ｃ”＋２＾（６４）・”ａ”＋２＾（５６）・”ｌ”＋２＾（４８）・”ｃ”＋２＾（４０）・”ｕ”＋２＾（３２）・”ｌ”＋２＾（２４）・”ａ”＋２＾（１６）・”ｔ”＋２＾（８）・”ｏ”＋“ｒ”］_ｐのように、３台のサーバ装置１００_１、１００_２、１００_３に分散する。
【０１２１】
第ｎのサーバ装置１００_ｎ（１≦ｎ≦３）は、１０文字の検索要求データに対するＲＳＳＳの第ｎの分散登録データ１０４_ｎを受けたのち、第ｎのデータ記憶部１０１_ｎに保存された、テキストの各文字に対するＲＳＳＳの分散情報＜ｔ_１＞ｑ，…，＜ｔ_２００＞ｑのうち、自らが保持する情報を、第ｎのデータ変換部１０２_ｎに入力し、上記数２のようにＴＳＳＳの分散情報［ｔ＊_１］_ｐ，…，［ｔ＊_ｎ］_ｐに変換する。このとき、ｔ＊_ｉ（＝ｔ_ｉ  ｍｏｄ  ｑ）は，ｔ_ｉ，ｔ_ｉ＋ｑ，ｔ_ｉ＋２ｑの３種類の値を取る可能性があることに注意する。
【０１２２】
次に，第ｎのサーバ装置１００_ｎは，各ｔ_ｉについて、［ｔ_ｉ］_ｐ＝［ｔ＊_ｉ］_ｐ−ｑ×［ｂ_ｉ］_ｐを計算する。
【０１２３】
その後，サーバ装置１００_ｎは，上記で計算した［ｔ_１］_ｐ，．．．，［ｔ_｛ｎ−ｍ｝］_ｐから，１０文字ごとの部分文字列に対するＳＳＳの分散情報［ｔ’_ｉ］_ｐ＝［２＾（７２）・ｔ_｛ｉ｝＋２＾（６４）・ｔ_｛ｉ＋１｝＋２＾（５６）・ｔ_｛ｉ＋２｝＋２＾（４８）・ｔ_｛ｉ＋３｝＋２＾（４０）・ｔ_｛ｉ＋４｝＋２＾（３２）・ｔ_｛ｉ＋５｝＋２＾（２４）・ｔ_｛ｉ＋６｝＋２＾（１６）・ｔ_｛ｉ＋７｝＋２＾（８）・ｔ_｛ｉ＋８｝＋ｔ_｛ｉ＋９｝］_ｐ  （１≦ｉ＜１９１）  １０５_ｎに変換する。
【０１２４】
第ｎのサーバ装置１００_ｎは、クライアント装置２００から受けた第ｎの分散検索要求データ１０６_ｎと第ｎのデータ記憶部１０１_ｎのデータから変換された第ｎの検索用データ１０５_ｎとを、第ｎのデータ検索部１０３_ｎに入力する。
【０１２５】
第ｎのデータ検索部１０３_ｎは、入力された分散検索要求データ［（ｃａｌｃｕｌａｔｏｒ）］_ｐと検索用データ［ｔ’_１］_ｐ，…，［ｔ’_１９１］_ｐから、
［ｓ’_１］_ｐ＝［ｔ’_１］_ｐ−［（ｃａｌｃｕｌａｔｏｒ）］_ｐ，
…
［ｓ’_１９１］_ｐ＝［ｔ’_１９１］_ｐ−［（ｃａｌｃｕｌａｔｏｒ）］_ｐ
の計算で検索要求データと部分文字列とのマッチングを行う。
【０１２６】
ここで、ある部分文字列ｔ’_ｋについて、ｔ’_ｋ＝（“ｃａｌｃｕｌａｔｏｒ”）となるとする。このとき、［ｓ’_ｋ］＝［ｔ’_ｋ］_ｐ−［（”ｃａｌｃｕｌａｔｏｒ”）］_ｐ＝［０］_ｐとなる。
【０１２７】
その後、第ｎのデータ検索部１０３_ｎは、乱数ｒの分散情報［ｒ］_ｐを分散し、上記数に示す式を用いて計算を行い、検索結果Ｓ＝ｓ’_１×…×ｓ’_（１９１）×ｒの分散情報を生成する。あるｓ’_ｋ＝０であるため、Ｓの値は０となる。
【０１２８】
第ｎのデータ検索部１０３_ｎは、Ｓの分散情報を第ｎの分散検索結果１０７_ｎとして出力する。第ｎのサーバ装置１００_ｎは、第ｎの分散検索結果１０７_ｎをクライアント装置２００に送信する。
【０１２９】
クライアント装置２００は、３台のサーバ装置１００_１、１００_２、１００_３から、検索結果Ｓの部分情報１０７_１、１０７_２、１０７_３を受け、ＴＳＳＳの復元アルゴリズムによって検索結果Ｓを復元する。クライアント装置２００は、Ｓ＝０が復号されたことを確認し、「サーバに”ｃａｌｃｕｌａｔｏｒ”を含む文字列が存在する」という結果を出力する。
【０１３０】
第１の実施形態の具体例において、サーバ装置に保存されるテキストの分散情報のサイズは、１テキストあたりｎ・ｌｏｇｐ＋２ｎ・ｌｏｇｑ＝２００×８０＋２×２００×８＝１９２００ビットである。関連技術のように、部分文字列をすべて８０ビットのＴＳＳＳの分散情報で保持していた場合、分散情報のサイズは、（１／２）・ｎ・（ｎ＋１）・ｌｏｇｐ＝（１／２）×２００×２０１×８０＝１６０８０００ｂｉｔｓ（≒２００ＫＢ）となる。このように、第１の実施形態の具体例では、関連技術と比べて分散情報のサイズを１／８３にすることができる。
【０１３１】
上記第２の実施形態の具体例として、３台のサーバ装置１００Ａ_１、１００Ａ_２、１００Ａ_３とクライアント装置２００Ａとで構成された文字列検索システムの構成を示す。
【０１３２】
この第２の実施形態の具体例では、テキストの元データはそれぞれ最大２００文字とし、Ｔ＝（ｔ_１，…，ｔ_２００）の形で表現され、ｔ_ｉ（１≦ｉ＜ｎ）はテキストの各文字を表す。３台のサーバ装置１００Ａ_１、１００Ａ_２、１００Ａ_３には文字列の組が１文字ごとにＴＳＳＳで［ｔ_１］ｑ，…，［ｔ_２００］ｑのように分散されて保管されている。各文字は８ビットで符号化されており、ｑ＝２＾８とする。本具体例では、クライアント装置２００Ａが検索を要求するキーワードの長さは１０文字とする。すなわち、検索要求データは最大８０ビットの文字列であり、ｐ＝２＾８０とする。
【０１３３】
クライアント装置２００Ａは、検索要求データとして、１０文字のテキストｓ＝（ｓ_１，ｓ_２，…，ｓ_１０）＝“ｃａｌｃｕｌａｔｏｒ”をＳＳＳで［（“ｃａｌｃｕｌａｔｏｒ”）］_ｐ＝［２＾（７２）・”ｃ”＋２＾（６４）・”ａ”＋２＾（５６）・”ｌ”＋２＾（４８）・”ｃ”＋２＾（４０）・”ｕ”＋２＾（３２）・”ｌ”＋２＾（２４）・”ａ”＋２＾（１６）・”ｔ”＋２＾（８）・”ｏ”＋“ｒ”］_ｐのように、３台のサーバ装置１００Ａ_１、１００Ａ_２、１００Ａ_３に分散する。
【０１３４】
第ｎのサーバ装置１００Ａ_ｎ（１≦ｎ≦３）は、１０文字の検索要求データに対するＴＳＳＳの分散登録データ１０４Ａ_ｎを受けたのち、第ｎのデータ記憶部１０１Ａ_ｎに保存された、テキストの各文字に対するＳＳＳの分散情報［ｔ_１］ｑ，…，［ｔ_２００］ｑのうち、自らが保持する情報ｔ_｛１，ｊ｝，ｔ_｛２，ｊ｝，．．．，ｔ_｛ｎ，ｊ｝を、第ｎのデータ変換部１０２Ａ_ｎに入力する。
第ｎのデータ変換部１０２Ａ_ｎは、
ｔ’_｛ｉ，ｊ｝＝ｔ_｛ｉ，ｊ｝  ||  ｔ_｛ｉ＋１，ｊ｝  ||  …  ||  ｔ_｛ｉ＋ｍ−１，ｊ｝
を０≦ｉ≦ｎ−ｍについて計算し、［ｔ’_｛０｝］_ｐ，．．．，［ｔ’_｛ｎ−ｍ｝］_ｐを第ｎの検索用データ１０５Ａ_ｎとして、第ｎのデータ検索部１０３Ａ_ｎに送信する。
【０１３５】
その後は、上記第１の実施形態の具体例と同様に、第ｎのデータ検索部１０３Ａ_ｎは、入力された第ｎの分散検索要求データ［（ｃａｌｃｕｌａｔｏｒ）］_ｐと第ｎの検索用データ［ｔ’_１］_ｐ，…，［ｔ’_１９１］_ｐから、
［ｓ’_１］_ｐ＝［（ｃａｌｃｕｌａｔｏｒ）］_ｐ−［ｔ’_１］_ｐ，
…
［ｓ’_１９１］_ｐ＝［（ｃａｌｃｕｌａｔｏｒ）］_ｐ−［ｔ’_１９１］_ｐ，
の計算で、検索要求データと部分文字列とのマッチングを行い、第１の実施形態の具体例と同様の方法で検索結果を出力する。
【０１３６】
第２の実施形態の具体例において、サーバ装置に保存されるテキストの分散情報のサイズは、１テキストあたりｎ・ｌｏｇｑ＝２００×８＝１６００ビットである。関連技術のように、部分文字列をすべて８０ビットのＴＳＳＳの分散情報で保持していた場合、分散情報のサイズは、（１／２）ｎ（ｎ＋１）・ｌｏｇｐ＝（１／２）×２００×２０１×８０＝１６０８０００ｂｉｔｓ（≒２００ＫＢ）となる。このように、第２の実施形態の具体例では、関連技術と比べて分散情報のサイズを１／１０００にすることができる。
【０１３７】
なお、本発明は、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲で構成要素を変形することができる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、上記実施形態の具体例では、サーバ装置が３台ある場合で説明したが、サーバ装置がＮ台（Ｎは２以上の整数）ある場合にも同様に適用できる。
【０１３８】
第１、第２の実施形態によれば、秘密分散法を用いた秘匿検索システムにおいて、その検索機能を損なうことなく、各サーバ装置が保持するデータ（分散情報）のサイズを低減することが可能となる。
【０１３９】
第１、第２の実施形態は、秘匿検索を組み合わせたより高度な秘匿データ分析にも貢献することができる。例えば、実施形態とその他のデータを秘匿したまま関数の計算を行う技術を組み合わせることにより、ある部分データを含むデータに対して何らかの処理を行う秘匿データ分析システムを実現することができる。
【０１４０】
また、サーバ装置にデータを委託するクラウドサービスにおいて、サービスの価格は通常データサイズと通信料によって決定される。本実施形態を適用した秘匿検索システムによって、サーバ装置の保持するデータサイズを削減することができ、秘匿検索システムを利用したサービスの低価格化と利用促進の実現を可能にする。
【０１４１】
なお、第１、第２の実施形態に記載した方法は、コンピュータに実行させることができる。この方法を実行させるプログラムは、フロッピー（登録商標）ディスク、ハードディスクなどの磁気ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｃ）などの光ディスク、光磁気ディスク（ＭＯ）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１４２】
また、この記録媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。
【０１４３】
また、記録媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト等のミドルウェアなどが各処理の一部を実行してもよい。
【０１４４】
さらに、記録媒体は、コンピュータと独立した媒体に限らず、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）やインターネットなどにより伝送されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
【０１４５】
また、記録媒体は１つに限らず、複数の記録媒体から上記実施形態における処理が実行される場合も含まれ、媒体構成は何れの構成であってもよい。
【０１４６】
コンピュータは、記録媒体に記憶されたプログラムに基づき各処理を実行するものであって、パソコンなどからなる装置、複数の装置がネットワーク接続されたシステムなどの何れの構成であってもよい。
【０１４７】
また、コンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置を含み、プログラムによって本実施形態の機能を実現することが可能な機器、装置である。
【０１４８】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１４９】
（付記１）  秘密情報の１シンボルごとの分散登録データを保存するデータ記憶部と、
前記データ記憶部に保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換するデータ変換部と、
前記検索用データと分散検索要求データとを用いて、他のサーバ装置のデータ検索部と通信を行いながら、前記データ記憶部の前記分散登録データに対する検索を行って、分散検索結果を出力するデータ検索部と、
を有するサーバ装置。
【０１５０】
（付記２）  前記データ記憶部は、前記分散登録データを、１シンボルごとの複製型秘密分散法の分散情報として保持し、
前記データ変換部は、前記データ記憶部に格納された１シンボルごとの複製型秘密分散法の分散情報を、複数シンボルに対する１つのＳｈａｍｉｒのしきい値秘密分散法の分散情報に生成する処理を実行して前記検索用データを得る、
付記１に記載のサーバ装置。
【０１５１】
（付記３）  前記データ記憶部は、前記分散登録データとして、Ｓｈａｍｉｒのしきい値秘密分散法によって生成された秘密情報の分散データを保持し、
前記データ変換部は、前記データ記憶部に保存された秘密情報の分散データを連結する処理を実行して前記検索用データを得、
前記データ検索部は、前記データ変換部によって連結されたデータを用いて、拡大体上の演算で検索を行う処理を実行して前記分散検索結果を得る、
付記１に記載のサーバ装置。
【０１５２】
（付記４）  各々が付記１乃至３のいずれか１つに記載のサーバ装置からなる第１乃至第Ｎ（Ｎは２以上の整数）のサーバ装置と、該第１乃至第Ｎのサーバ装置にネットワークを介して接続されたクライアント装置と、から成る秘匿検索システムであって、前記クライアント装置は、
登録データから、前記第１乃至第Ｎのサーバ装置にそれぞれ登録されるべき第１乃至第Ｎの分散登録データを生成する登録データシェア生成部と、
検索要求データから、前記第１乃至第Ｎのサーバ装置へそれぞれ送信するための第１乃至第Ｎの分散検索要求データを生成するクエリデータシェア生成部と、
前記第１乃至第Ｎのサーバ装置からそれぞれ受信した第１乃至第Ｎの分散検索結果から、検索結果の分散情報を復号する秘密分散復号部と、
を有する秘匿検索システム。
【０１５３】
（付記５）  クライアント装置と、該クライアント装置にネットワークを介して接続された第１乃至第Ｎ（Ｎは２以上の整数）のサーバ装置と、を備える検索システムにおける秘匿検索方法であって、預けるデータを秘密分散法で秘密分散して前記第１乃至第Ｎのサーバ装置に保存し、前記第１乃至第Ｎのサーバ装置に保存されたデータを秘匿したまま検索できる秘匿検索方法であって、
前記クライアント装置が、登録データに対して前記秘密分散法の分散データ生成手順を実行して第１乃至第Ｎの分散登録データを生成し、該第１乃至第Ｎの分散登録データをそれぞれ前記第１乃至第Ｎのサーバ装置へ送信する登録データ生成ステップと、
前記第ｎ（１≦ｎ≦Ｎ）のサーバ装置が、第ｎの分散登録データを第ｎのデータ記憶部に保存する登録データ保存ステップと、
前記クライアント装置が、検索要求データに対して前記秘密分散法の分散データ生成手順を実行して第１乃至第Ｎの分散検索データを生成し、該第１乃至第Ｎの分散検索データをそれぞれ前記第１乃至第Ｎのサーバ装置へ送信する検索要求データ生成ステップと、
前記第ｎのサーバ装置が、前記第ｎのデータ記憶部に保存された前記第ｎの分散登録データを、複数シンボルを連結したデータに対する第ｎの検索用データに変換する検索データ変換ステップと、
前記第ｎのサーバ装置が、前記第ｎの検索用データと前記第ｎの分散検索データとを用いて、他のサーバ装置と通信を行いながら、前記第ｎのデータ記憶部の前記第ｎの分散登録データに対する検索を行い、第ｎの分散検索結果を前記クライアント装置へ送信する検索ステップと、
前記クライアント装置が、前記第１乃至第Ｎのサーバ装置から受信した第１乃至第Ｎの分散検索結果に対して、前記秘密分散法の復号手順を実行して、検索結果を復元する復元ステップと、
を含む秘匿検索方法。
【０１５４】
（付記６）  前記登録データ生成ステップでは、前記クライアント装置が、前記登録データを複製型秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索要求データ生成ステップでは、前記クライアント装置が、前記検索要求データをＳｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索データ変換ステップでは、前記第ｎのサーバ装置が、前記第ｎの分散登録データを前記Ｓｈａｍｉｒのしきい値秘密分散法の分散データである前記第ｎの検索用データに変換する、
付記５に記載の秘匿検索方法。
【０１５５】
（付記７）  前記登録データ生成ステップでは、前記クライアント装置が、前記登録データをＳｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、  前記検索要求データ生成ステップでは、前記クライアント装置が、前記検索要求データを前記Ｓｈａｍｉｒのしきい値秘密分散法によって前記第１乃至第Ｎの分散検索データに変換し、
前記検索データ変換ステップでは、前記第ｎのサーバ装置が、前記第ｎの分散登録データを連結して一つのデータとして前記第ｎの検索用データに変換する、
付記５に記載の秘匿検索方法。
【０１５６】
（付記８）  サーバ装置で検索を実行する検索方法であって、
秘密情報の１シンボルごとの分散登録データをデータ記憶部に保存する保存ステップと、
データ変換部が、前記データ記憶部に保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換する変換ステップと、
データ検索部が、前記検索用データと分散検索要求データとを用いて、他のサーバ装置のデータ検索部と通信を行いながら、前記データ記憶部の前記分散登録データに対する検索を行って、分散検索結果を出力する検索ステップと、
を含む検索方法。
【０１５７】
（付記９）  前記保存ステップでは、前記分散登録データを、１シンボルごとの複製型秘密分散法の分散情報として前記データ記憶部に保持し、
前記変換ステップでは、前記データ変換部が、前記データ記憶部に格納された１シンボルごとの複製型秘密分散法の分散情報を、複数シンボルに対する１つのＳｈａｍｉｒのしきい値秘密分散法の分散情報に生成する処理を実行して前記検索用データを得る、
付記８に記載の検索方法。
【０１５８】
（付記１０）  前記保存ステップでは、前記分散登録データとして、Ｓｈａｍｉｒのしきい値秘密分散法によって生成された秘密情報の分散データを前記データ記憶部に保持し、
前記変換ステップでは、前記データ変換部が、前記データ記憶部に保存された秘密情報の分散データを連結する処理を実行して前記検索用データを得、
前記検索ステップでは、前記データ検索部が、前記変換手順によって連結されたデータを用いて、拡大体上の演算で検索を行う処理を実行して前記分散検索結果を得る、
付記８に記載の検索方法。
【０１５９】
（付記１１）  コンピュータであるサーバ装置に検索を実行させる検索プログラムであって、前記コンピュータに、
秘密情報の１シンボルごとの分散登録データをデータ記憶部に保存する保存手順と、
前記データ記憶部に保存された前記分散登録データを、複数シンボルを連結したデータに対する検索用データに変換する変換手順と、
前記検索用データと分散検索要求データとを用いて、他のサーバ装置と通信を行いながら、前記データ記憶部の前記分散登録データに対する検索を行って分散検索結果を出力する検索手順と、
を実行させるための検索プログラム。
【０１６０】
（付記１２）  前記保存手順は、前記コンピュータに、前記分散登録データを、１シンボルごとの複製型秘密分散法の分散情報として前記データ記憶部に保持させ、
前記変換手順は、前記コンピュータに、前記データ記憶部に格納された１シンボルごとの複製型秘密分散法の分散情報を、複数シンボルに対する１つのＳｈａｍｉｒのしきい値秘密分散法の分散情報に生成する処理を実行させて前記検索用データを得させる、
付記１１に記載の検索プログラム。
【０１６１】
（付記１３）  前記保存手順は、前記コンピュータに、前記分散登録データとして、Ｓｈａｍｉｒのしきい値秘密分散法によって生成された秘密情報の分散データを前記データ記憶部に保持させ、
前記変換手順は、前記コンピュータに、前記データ記憶部に保存された秘密情報の分散データを連結する処理を実行させて前記検索用データを得させ、
前記検索手順は、前記コンピュータに、前記変換手順によって連結されたデータを用いて、拡大体上の演算で検索を行う処理を実行させて前記分散検索結果を得させる、
付記１１に記載の検索プログラム。
【産業上の利用可能性】
【０１６２】
本発明は、秘匿検索を組み合わせたより高度な秘匿データ分析にも貢献する。例えば、ある部分データを含むデータに対して何らかの処理を行う秘匿データ分析システムは、本発明とその他のデータを秘匿したまま関数の計算を行う技術を組み合わせることによって実現することが可能である。【０１６３】
また、サーバ装置にデータを委託するクラウドサービスなどにおいて、サービスの価格は通常データサイズと通信料によって決定される。したがって、秘匿検索システムにおけるサーバ装置の保持するデータサイズを削減することは、秘匿検索システムを利用したサービスの低価格化につながり、サービスの利用を促進するものと考えられる。【０１６４】
この出願は、２０１５年２月２３日に出願された日本出願特願２０１５−０３２５７３号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１６５】
１００_１〜１００_Ｎ、１００_ｎ  サーバ装置
１００Ａ_１〜１００Ａ_Ｎ、１００Ａ_ｎ  サーバ装置
１０１_１〜１０１_Ｎ、１０１_ｎ  データ記憶部
１０１Ａ_１〜１０１Ａ_Ｎ、１０１Ａ_ｎ  データ記憶部
１０２_１〜１０２_Ｎ、１０２_ｎ  データ変換部
１０２Ａ_１〜１０２Ａ_Ｎ、１０２Ａ_ｎ  データ変換部
１０３_１〜１０３_Ｎ、１０３_ｎ  データ検索部
１０３Ａ_１〜１０３Ａ_Ｎ、１０３Ａ_ｎ  データ検索部
１０４_ｎ、１０４Ａ_ｎ    分散登録データ
１０５_ｎ、１０５Ａ_ｎ    検索用データ
１０６_ｎ、１０６Ａ_ｎ    分散検索要求データ
１０７_ｎ、１０７Ａ_ｎ      分散検索結果
２００、２００Ａ  クライアント装置
２０１、２０１Ａ    登録データシェア生成部
２０２、２０２Ａ    クエリデータシェア生成部
２０３、２０３Ａ    秘密分散復号部
２０４、２０４Ａ  登録データ
２０５、２０５Ａ  検索要求データ
２０６、２０６Ａ  検索結果
【図１】
2016136201.tif 000007
【図２】
2016136201.tif 000008
【図３】
2016136201.tif 000009
【図４】
2016136201.tif 000010
【図５】
2016136201.tif 000011
【図６】
2016136201.tif 000012
【図７】
2016136201.tif 000013
【図８】
2016136201.tif 000014
【図９】
2016136201.tif 000015
【図１０】
2016136201.tif 000016
【国際調査報告】
2016136201.tif 000017
2016136201.tif 000018
2016136201.tif 000019
2016136201.tif 000020