(57)【要約】【課題】数値情報を秘匿したまま、他の数値情報との近接度合いを判別することを目的とする。【解決手段】鍵生成サーバ２は、近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合を端末装置３と情報提供装置４に配布する。端末装置３は、第１の数値情報と、第１の乱数と、鍵行列の一次結合とに基づいて第１の秘匿ベクトルとを、近傍判定サーバ７に送信する。また、情報提供装置４は、第２の数値情報と、第２の乱数と、鍵行列の一次結合とに基づいて第２の秘匿ベクトルを、近傍判定サーバ７に送信する。そして、近傍判定サーバ７は、第１の秘匿ベクトルと、第２の秘匿ベクトルとの差分から、鍵行列を法とした際の剰余である剰余ベクトルを算出し、算出した剰余ベクトルに基づき、第１の数値情報と第２の数値情報とが近傍範囲に属するか否かを判定する。【選択図】図１
2014095878.tif 000002
【特許請求の範囲】
【請求項１】
第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定する近接判定方法において、
前記近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集し、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを収集し、
前記収集した第１の秘匿ベクトルと、前記第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出し、
前記算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する
処理を情報処理装置が実行することを特徴とする近傍判定方法。
【請求項２】
前記第１の秘匿ベクトルに係わる一次結合とは異なる一次結合と、前記第２の数値情報と、前記第２の乱数とに基づく第２の秘匿ベクトルを収集することを特徴とする請求項１に記載の近傍判定方法。
【請求項３】
前記一次結合と第１の乱数との積に前記第１の数値情報を加算した第１の秘匿ベクトル、および、前記一次結合と第２の乱数との積に前記第２の数値情報を加算した第２の秘匿ベクトルを収集することを特徴とする請求項１または２に記載の近傍判定方法。
【請求項４】
第１の情報処理装置の位置を示す前記第１の数値情報と、前記一次結合と、前記第１の乱数とに基づく前記第１の秘匿ベクトル、および、第２の情報処理装置の位置を示す前記第２の数値情報と、前記一次結合と、前記第２の乱数とに基づく前記第２の秘匿ベクトルを収集することを特徴とする請求項１〜３のいずれか１つに記載の近傍判定方法。
【請求項５】
第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集する第１の収集部と、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを第２の情報処理装置から収集する第２の収集部と、
前記第１の収集部が収集した第１の秘匿ベクトルと、前記第２の収集部が収集した第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出する算出部と、
前記算出部が算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する判定部と
を有することを特徴とする近傍判定装置。
【請求項６】
第１の情報処理装置が記憶する第１の数値情報と第２の情報処理装置が記憶する第２の数値情報とが近傍範囲に属するか否かを判定する近傍判定装置と、
前記第１の数値情報と前記第２の数値情報とを秘匿するための鍵行列を生成する鍵行列生成装置と
を有する近傍判定システムにおいて、
前記鍵行列生成装置は、
前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定するための閾値を対角成分とする行列に、乱数ベクトルを最終列として付加して生成された鍵行列を生成する生成部と、
前記生成部が生成した鍵行列の行ベクトルの一次結合を前記第１の情報処理装置、および前記第２の情報処理装置へ送信し、前記生成部が生成した鍵行列を前記近傍判定装置へ送信する送信部と
を有し、
前記近傍判定装置は、
前記鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを前記第１の情報処理装置から収集する第１の収集部と、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを前記第２の情報処理装置から収集する第２の収集部と、
前記第１の収集部が収集した第１の秘匿ベクトルと、前記第２の収集部が収集した第２の秘匿ベクトルとの差分から、前記鍵行列生成装置から受信した鍵行列を法とした際の剰余である剰余ベクトルを算出する算出部と、
前記算出部が算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する判定部と
を有することを特徴とする近傍判定システム。
【請求項７】
第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定するコンピュータに、
前記近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集し、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを収集し、
前記収集した第１の秘匿ベクトルと、前記第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出し、
前記算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する
処理を実行させることを特徴とする近傍判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、近傍判定方法、近傍判定装置、近傍判定システム、および近傍判定プログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク上に存在する演算資源を用いて、利用者に様々なサービスを提供するクラウドコンピューティングの技術が利用されている。このようなクラウドコンピューティング技術の一例として、位置情報や生体情報等、利用者に係わる様々な数値情報をネットワーク上の情報処理装置が収集し、収集した数値情報の比較結果や分析結果に応じたサービスを利用者に提供する技術が考えられる。例えば、ネットワーク上の情報処理装置が、利用者やタクシーの位置情報を収集して比較し、利用者の近傍に位置するタクシーの情報を利用者に提供する技術が考えられる。
【０００３】
このように、ネットワーク上の情報処理装置が利用者に係わる数値情報を収集、分析した場合は、利用者側の演算資源にかかわらずサービスを提供できるので、利便性が向上する。しかしながら、ネットワーク上の情報処理装置が利用者に係わる数値情報を収集する場合は、セキュリティの観点から、数値情報が第三者に漏洩しないよう秘匿するのが好ましい。このような利用者に係わる数値情報を秘匿する技術として、マスク化による秘匿の技術が知られている。
【０００４】
例えば、利用者が利用する端末装置や、タクシーに設置された端末装置は、所定のマスク値を用いて、現在位置を示す数値情報を秘匿化し、秘匿化した数値情報をネットワーク上の情報処理装置へ送信する。そして、ネットワーク上の情報処理装置は、秘匿化された数値情報を利用者やタクシーから収集し、収集した数値情報を付き合わせることで、利用者とタクシーとの近傍度合を判定する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】”Privacy-preserving  Data  Mining”  Jun  Sakuma、  Interdisciplinary  Graduate  school  of  Science  and  Engineering、  Tokyo  Institute  of  Technology、  Shigenobu  Kobayashi、  Interdisciplinary  Graduate  school  of  Science  and  Engineering、  Tokyo  Institute  of  Technology
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述したマスク化の技術では、秘匿化された数値情報を用いて近接度合を判別するために、各数値情報を共通のマスク値で秘匿化するので、利用者の数値情報が他の利用者などに漏洩しやすいという問題がある。
【０００７】
１つの側面では、本発明は、数値情報を秘匿したまま、他の数値情報との近接度合いを判別することが可能な方法、装置、システムおよびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの側面では、情報処理装置が第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定する近接判定方法である。具体的には、情報処理装置は、近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集する。また、情報処理装置は、鍵行列の行ベクトルの一次結合と、第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを収集する。そして、情報処理装置は、収集した第１の秘匿ベクトルと、第２の秘匿ベクトルとの差分から、鍵行列を法とした際の剰余である剰余ベクトルを算出し、算出した剰余ベクトルに基づいて、第１の数値情報と第２の数値情報とが近傍範囲に属するか否かを判定する。
【発明の効果】
【０００９】
１つの実施形態では、数値情報を秘匿したまま、他の数値情報との近接度合いを判別することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係わる近傍判定システムの一例を説明する図である。
【図２】図２は、実施例１に係わる鍵生成サーバの機能構成を説明する図である。
【図３】図３は、実施例１に係わる鍵行列を説明する図である。
【図４】図４は、実施例１に係わる端末装置の機能構成を説明する図である。
【図５】図５は、実施例１に係わる情報提供装置の機能構成を説明する図である。
【図６】図６は、実施例１に係わる近傍判定サーバの機能構成を説明する図である。
【図７】図７は、近傍判定システムが実行する処理の一例を説明する図である。
【図８】図８は、実施例１に係わる近傍判定システムが実行する処理の流れを説明するためのシーケンス図である。
【図９】図９は、生体認証システムの一例を説明する図である。
【図１０】図１０は、近傍判定プログラムを実行するコンピュータの一例について説明するための図である。
【００１１】
以下に添付図面を参照して本願に係る近傍判定方法、近傍判定装置、近傍判定システム、および近傍判定プログラムについて説明する。
【実施例１】
【００１２】
以下の実施例１では、図１を用いて、近傍判定システムの一例を説明する。図１は、実施例１に係わる近傍判定システムの一例を説明する図である。図１に示す例では、近傍判定システム１は、鍵生成サーバ２、端末装置３、複数の情報提供装置４〜６、近傍判定サーバ７がインターネット８を解して接続されている。図１では、理解を容易にするため記載を省略したが、近傍判定システム１は、さらに複数の情報提供装置を有していてもよく、また、さらに複数の端末装置３を有していてもよい。
【００１３】
このような近傍判定システム１は、各情報提供装置４〜６に係わる数値情報、および端末装置３に係わる数値情報の近傍判定を行う。なお、近傍判定システム１は、各情報提供装置４〜６や端末装置３の数値情報として任意の数値情報を取り扱うことができるが、以下の説明では、端末装置３と各情報提供装置４〜６の位置を示す数値情報である位置情報を取り扱う例について説明する。
【００１４】
端末装置３は、近傍判定システム１の利用者が有する端末装置であり、ＧＰＳ（Global  Positioning  System）やガリレオ、その他任意のシステムを用いて利用者の位置情報を取得可能な端末である。また、各情報提供装置４〜６は、各タクシーに設置された情報処理装置であり、端末装置３と同様に、任意のシステムを用いて利用者の位置情報を取得可能な端末である。
【００１５】
このような端末装置３は、利用者の近傍に位置するタクシーを検索する場合は、インターネット８を介して近傍判定サーバ７にタクシーの検索を要求する。そして、端末装置３は、自身の位置情報を秘匿化し、秘匿化した位置情報を近傍判定サーバ７へ送信する。なお、各情報提供装置４〜６は、一定時間ごとに、もしくは近傍判定サーバ７の要求に応じて、秘匿化した位置情報を近傍判定サーバ７に送信する。
【００１６】
近傍判定サーバ７は、端末装置３と各情報提供装置４〜６とが取得した位置情報を収集し、収集した位置情報の近傍判定を行う。例えば、近傍判定サーバ７は、端末装置３からの求めに応じて、端末装置３と各情報提供装置４〜６とから秘匿化された位置情報を収集し、収集した位置情報が示す位置が、所定の近傍範囲に含まれているか否かを判定する近傍判定を行う。
【００１７】
そして、近傍判定サーバ７は、近傍判定の結果、端末装置３の近傍に位置する情報提供装置を端末装置３に通知することで、利用者の近傍に位置するタクシーを利用者に通知することができる。なお、近傍判定サーバ７は、端末装置３の近傍に位置する情報提供装置に端末装置３の位置を通知することで、利用者の位置をタクシーに通知してもよい。
【００１８】
ここで、近傍判定システム１は、端末装置３、および各情報提供装置４〜６から位置情報を収集する際に、共通のマスク値で秘匿された情報を受信した場合には、他の利用者に端末装置３や各情報提供装置４〜６の位置情報を秘匿することができない。例えば、情報提供装置４は、端末装置３と共通のマスク値を有するので、端末装置３が秘匿化した位置情報を取得した場合は、取得した秘匿化情報から端末装置３の位置情報を読み取ることができてしまう。
【００１９】
このため、近傍判定システム１では、端末装置３、および各情報提供装置４〜６は、それぞれ異なる乱数を用いて、位置情報を秘匿化し、秘匿化した位置情報を近傍判定サーバ７へ送信する。以下、このような近傍判定システム１における位置情報の秘匿化、および秘匿化された位置情報の近傍判定の内容について説明する。なお、以下の説明では、ｍ＋１＝ｎを満たす任意の自然数ｍおよびｎを用いて近傍判定の内容について説明する。
【００２０】
例えば、鍵生成サーバ２は、近傍範囲を示す閾値を対角成分とし、他の成分を「０」とする対角行列を生成する。ここで、近傍範囲を示す閾値とは、利用者が近傍範囲として設定した領域を示す数値であり、近傍範囲の各次元方向の長さを示す情報である。なお、鍵生成サーバ２は、判定対象となる位置情報がｍ個の成分を有する情報である場合、すなわち位置情報がｍ次元の情報である場合には、ｍ×ｍの対角行列を生成する。そして、鍵生成サーバ２は、生成したｍ×ｍの対角行列に、全ての成分が「０」である最終行を付加したｎ×ｍ行列を生成する。
【００２１】
また、鍵生成サーバ２は、対角行列の列の数ｍに１を加算した数の成分を有する乱数ベクトルを生成する。そして、鍵生成サーバ２は、生成したｎ×ｍ行列に生成した乱数ベクトルを行列の最終列、すなわちｍ＋１＝ｎ番目の列として付加したｎ×ｎの正方行列を鍵行列として生成する。なお、鍵生成サーバ２は、対角行列に付加した乱数ベクトルの各成分が、同一の行に含まれる対角行列の成分の半分以下となるように乱数ベクトルを生成する。また、鍵生成サーバ２は、乱数ベクトルの最終成分については、適当な乱数を割り当てる。
【００２２】
次に、鍵生成サーバ２は、生成した鍵行列の一次結合を複数生成する。例えば、ｎ×ｎの正方行列である鍵行列は、それぞれｎ個の成分を有する行ベクトルｖ１、ｖ２…、ｖｎを列成分とする行列で表すことができる。鍵生成サーバ２は、各行ベクトルｖ１、ｖ２…、ｖｎに対して、それぞれ適当な整数ｄ１、ｄ２…、ｄｎを選び、各行ベクトルと各整数との積の和、すなわちｄ１＊ｖ１＋ｄ２＊ｖ２＋…＋ｄｎ＊ｖｎであらわされるｎ次元のベクトルを一次結合として算出する。
【００２３】
なお、鍵生成サーバ２は、端末装置３、および各情報提供装置４〜６が近傍判定サーバ７に送信する位置情報ごとに、異なる整数ｄ１、ｄ２…、ｄｎの組を選択し、選択した整数の組と鍵行列の各行ベクトルとの積の和である一次結合を算出する。そして、鍵生成サーバ２は、算出した一次結合を端末装置３、および各情報提供装置４〜６に配布する。また、鍵生成サーバ２は、生成した鍵行列を近傍判定サーバ７に送信する。
【００２４】
このような場合には、端末装置３は、位置情報が有するｍ次元の成分に、ｎ番目の成分として「０」を追加した位置ベクトルを生成し、鍵生成サーバ２から受信した一次結合と乱数との積に、生成した位置ベクトルを加算した秘匿ベクトルを生成する。そして、端末装置３は、生成した秘匿ベクトルを近傍判定サーバ７に送信する。
【００２５】
また、各情報提供装置４〜６は、端末装置３と同様に、位置情報を成分とする位置ベクトルと、生成サーバ２から受信した一次結合と乱数との積に、生成した位置ベクトルを加算した秘匿ベクトルを生成する。そして、各情報提供装置４〜６は、生成した秘匿ベクトルを近傍判定サーバ７に送信する。
【００２６】
一方、近傍判定サーバ７は、端末装置３から受信した秘匿ベクトルと、各情報提供装置４〜６から受信した秘匿ベクトルとの差分ベクトルをそれぞれ算出する。そして、近傍判定サーバ７は、算出した差分ベクトルから、鍵生成サーバ２から受信した鍵行列を法とした際の剰余である剰余ベクトルを算出し、算出した剰余ベクトルを用いて近傍判定を行う。
【００２７】
例えば、近傍判定サーバ７は、端末装置３から受信した秘匿ベクトルと、情報提供装置４から受信した秘匿ベクトルとの差から、鍵行列を法とした際の剰余である剰余ベクトルの最終成分が「０」である場合は、端末装置３と情報提供装置４とが近傍に位置すると判別する。そして、近傍判定サーバ７は、端末装置３に情報提供装置４の情報を通知する。
【００２８】
このように、近傍判定サーバ７は、端末装置３、および各情報提供装置４〜６からそれぞれ異なる乱数により秘匿化された位置情報を用いて、近傍判定を行う。このため、近傍判定システム１は、端末装置３、および情報提供装置４〜６が近傍判定サーバ７に送信した秘匿ベクトルを他の端末装置や情報提供装置が取得した場合にも、位置情報の漏洩を防ぐことができる。すなわち、近傍判定システム１においては、位置情報がそれぞれ異なる乱数で秘匿化されるため、他の装置が生成した秘匿ベクトルから、位置情報を読み取ることができないので、位置情報の漏洩を防ぐことができる。
【００２９】
また、端末装置３、および情報提供装置４〜６は、鍵行列の一次結合と乱数との積に位置ベクトルを加算した秘匿ベクトルを近傍判定サーバ７に送信する。そして、近傍判定サーバ７は、秘匿ベクトルの差分から、鍵行列を法とした際の剰余である剰余ベクトルを算出し、算出した剰余ベクトルに基づいて、近傍判定を行う。このため、近傍判定サーバ７は、異なる乱数を用いて秘匿化された位置情報を用いて、近傍判定を行うことができる。
【００３０】
なお、たとえば、鍵生成サーバ２は、端末装置３から近傍判別サーバ７に近傍判定の実行を要求された際に、一次結合を端末装置３および各情報提供装置４〜６に配布してもよい。また、鍵生成サーバ２は、一次結合の配布要求があった端末装置３、および各情報提供装置４〜６に対してのみ、一次結合を配布してもよい。
【００３１】
以下、近傍判定サーバ７が実行する近傍判定の原理について説明する。鍵行列Ｖの各行ベクトルｖ１、ｖ２…、ｖｎの一次結合は、鍵行列Ｖの各行ベクトルの一次結合ｄ１＊ｖ１＋ｄ２＊ｖ２＋…＋ｄｎ＊ｖｎを元とする集合Ｌ（格子Ｌ）で表すことができる。つまり、鍵行列Ｖの各行ベクトルの一次結合は、集合Ｌの元からなる格子上のいずれかの交点に対応する。
【００３２】
ここで、ｍ次元の位置情報ａ１を集合Ｌの元ｂ１と乱数ｒ１で秘匿化した秘匿ベクトルｃ１は、ｃ１＝［ａ１、０］＋ｒ１＊ｂ１で表すことができる。ここで、［ａ１、０］とは、位置情報ａ１にｎ番目の成分「０」を付加した位置ベクトルである。また、ｍ次元の位置情報ａ２を集合Ｌの元ｂ２と乱数ｒ２で秘匿化した秘匿ベクトルｃ２は、ｃ２＝［ａ２、０］＋ｒ２＊ｂ２で表すことができる。このような場合には、秘匿ベクトルｃ１とｃ２との差分ベクトルｚは、ｚ＝ｃ１−ｃ２＝［ａ１、０］＋ｒ１＊ｂ１−［ａ２、０］−ｒ２＊ｂ２＝［ａ１−ａ２、０］＋ｒ１＊ｂ１−ｒ２＊ｂ２で表すことができる。
【００３３】
ここで、差分ベクトルｚが有するｒ１＊ｂ１−ｒ２＊ｂ２は、集合Ｌの元と乱数との積同士の差分であるため、集合Ｌの元に含まれている。つまり、ｒ１＊ｂ１−ｒ２＊ｂ２は、集合Ｌの元からなる格子上のいずれかの交点に対応する。また、差分ベクトルｚから鍵行列Ｖの剰余ベクトルを計算した場合は、集合Ｌによって定まる基本領域Ｐ（Ｌ）に差分ベクトルｚを写像することと対応する。このため、差分ベクトルｚから鍵行列Ｖの剰余ベクトルを計算した場合は、ｒ１＊ｂ１−ｒ２＊ｂ２が無視されることとなる。このため、ｚｍｏｄＶを算出した場合には、差分ベクトルｚのうち、差分ベクトルｚの先端以外を含む格子部分を無視し、差分ベクトルｚの先端を含む１つの格子のみを基本領域Ｐ（Ｌ）に写像することとなる。
【００３４】
この結果、ｚｍｏｄＶ＝［ａ１−ａ２、０］ｍｏｄＶとなるので、ベクトル［ａ１−ａ２、０］が基本領域Ｐ（Ｌ）に含まれる場合、すなわち位置情報ａ１、ａ２が近傍範囲に含まれる場合は、ｚｍｏｄＶ＝［ａ１−ａ２、０］となる。この結果、位置情報ａ１、ａ２が近傍範囲に含まれる場合には、ｚｍｏｄＶの最終成分が非常に高い確率で「０」となる。
【００３５】
一方、ベクトル［ａ１−ａ２、０］が基本領域Ｐ（Ｌ）に含まれない場合、すなわち位置情報ａ１、ａ２が近傍範囲に含まれない場合には、集合Ｌによる格子のある元をｂとすると、ｚｍｏｄＶ＝［ａ１−ａ２、０］＋ｂとなる。この結果、位置情報ａ１、ａ２が近傍範囲に含まれない場合は、ｚｍｏｄＶの最終成分が非常に高い確率で「０」以外の値となる。このような原理のもと、近傍判定サーバ７は、秘匿ベクトルの差分から鍵行列の剰余ベクトルを算出し、算出した剰余ベクトルの最終成分に基づいて、異なる乱数で秘匿化された位置情報の近傍判定を行うことができる。
【００３６】
次に、図２を用いて、鍵生成サーバの機能構成について説明する。図２は、実施例１に係わる鍵生成サーバの機能構成を説明する図である。鍵生成サーバ２は、ベクトル記憶部１０、乱数生成部１１、鍵行列生成部１２、一次結合生成部１３、送信部１４を有する。ベクトル記憶部１０は、鍵行列生成部１２が生成した鍵行列の各行ベクトルを記憶する。
【００３７】
乱数生成部１１は、鍵行列生成部１２から鍵行列用の乱数を生成するよう要求された場合には、鍵行列用の乱数を生成し、生成した乱数を鍵行列生成部１２に出力する。ここで、鍵行列用の乱数とは、鍵行列を生成する際に閾値を示す正方行列に最終列として付加する乱数である。例えば、乱数生成部１１は、鍵行列用の乱数を生成するよう要求されるとともに、鍵行列に含まれる閾値「ｅ、ｆ、ｇ」の通知を受けた場合には、ｅ／２≧ｈ、ｆ／２≧ｉ、ｇ／２≧ｋを満たす乱数「ｈ、ｉ、ｊ」、および任意の乱数「ｋ」を生成する。そして、乱数生成部１１は、乱数ベクトル「ｈ、ｉ、ｊ、ｋ」を鍵行列生成部１２に通知する。
【００３８】
また、乱数生成部１１は、一次結合生成部１３から一次結合用の乱数を複数組生成するよう要求された場合は、鍵行列の列の数と同じ数の乱数の組を複数生成し、生成した乱数の組を一次結合生成部１３に通知する。
【００３９】
鍵行列生成部１２は、近傍判定を行うための鍵行列を生成する。具体的には、鍵行列生成部１２は、あらかじめ定められた近傍範囲を示す閾値を対角要素に含む対角行列を生成する。次に、鍵行列生成部１２は、対角要素を乱数生成部１１に通知するとともに、鍵行列用の乱数を生成するよう要求する。
【００４０】
そして、鍵行列生成部１２は、対角行列に全成分が「０」となる最終行を付加し、乱数生成部１１から受信した乱数ベクトルを対角行列の最終列の列ベクトルとして付加した鍵行列を生成する。その後、鍵行列生成部１２は、生成した鍵行列を近傍判定サーバ７へ送信するよう送信部１４に指示する。また、鍵行列生成部１２は、生成した鍵行列の各行ベクトルをベクトル記憶部１０に格納する。
【００４１】
ここで、図３は、実施例１に係わる鍵行列を説明する図である。なお、図３に示す例では、位置情報、および近傍範囲が３次元の数値によって表される例について記載する。図３に示すように、鍵行列Ｖは、点線で示す範囲の近傍判定用の行列に乱数ベクトルを最終列として付加した行列である。
【００４２】
ここで、近傍判定用の行列は、近傍範囲の各次元方向の長さを指定する閾値を対角要素として有する。例えば、図３に示す例では、近傍範囲のｘ軸方向の長さが「４０」であり、ｙ軸方向の長さが「３０」であり、ｚ軸方向の長さが「２０」である旨を示す。すなわち、図３に示す近傍判定用の行列は、任意の点を中心としてｘ軸方向に「±２０」、ｙ軸方向に「±１５」、ｚ軸方向に「±１０」の範囲内に２つの位置情報が含まれるか否かを判定するための行列である。
【００４３】
また、乱数ベクトルの各要素は、同じ行に含まれる閾値の半分以下の値となるように選択される。例えば、図３に示す例では、乱数ベクトルの最初の３つの要素は「１０、５、７」が選択される。なお、乱数ベクトルの最後の要素は、同じ行に閾値が含まれないので、任意の乱数が選択される。なお、図３に示す例では、近傍範囲を３次元の数値で指定したが、実施例はこれに限定されるものではなく、任意の次元の数値を用いることができる。例えば、鍵生成サーバ２は、緯度、経度、高度、時間等を任意の組み合わせで用いることができる。
【００４４】
図２に戻って、一次結合生成部１３は、鍵行列の各行ベクトルの一次結合を生成し、生成した一次結合を端末装置３、および各情報提供装置４〜６に配布する。例えば、一次結合生成部１３は、ベクトル記憶部１０に記憶された各行ベクトルｖ１、ｖ２…、ｖｎを取得する。また、一次結合生成部１３は、乱数の組を生成するよう乱数生成部１１に指示する。
【００４５】
そして、一次結合生成部１３は、乱数生成部１１から乱数の組ｄ１、ｄ２…、ｄｎを受信した場合は、一次結合ｄ１＊ｖ１＋ｄ２＊ｖ２＋…＋ｄｎ＊ｖｎを算出する。また、一次結合生成部１３は、配布する一次結合の数だけ乱数の組を乱数生成部１１に要求し、各組ごとに一次結合を生成する。そして、一次結合生成部１３は、生成した複数の一次結合を端末装置３、および各情報提供装置４〜６に出力するよう送信部１４に指示する。
【００４６】
送信部１４は、鍵行列生成部１２から鍵行列を受信した場合は、インターネット８を介して、近傍判定サーバ７に鍵行列を送信する。また、送信部１４は、一次結合生成部１３から複数の一次結合を受信した場合は、端末装置３、および各情報提供装置４〜６に、それぞれ異なる一次結合を配布する。
【００４７】
なお、鍵生成サーバ２が鍵行列および一次結合を生成する処理、および配布する処理は、任意のタイミングで行うことができる。例えば、鍵生成サーバ２は、所定の時間間隔で新たな鍵行列を生成し、生成した鍵行列を近傍判定サーバ７に送信する。そして、鍵生成サーバ２は、端末装置３から近傍判定の要求を受けた旨を近傍判定サーバ７から通知されたことをトリガとして、一次結合を生成し、生成した一次結合を端末装置３、および各情報提供装置４〜６に配布してもよい。また、鍵生成サーバ２は、所定の時間間隔で鍵行列と一次結合とを生成し、生成した鍵行列を近傍判定サーバ７に送信し、一次結合を端末装置３、および各情報提供装置４〜６に配布してもよい。
【００４８】
次に、図４を用いて、端末装置３の機能構成について説明する。図４は、実施例１に係わる端末装置の機能構成を説明する図である。なお、以下の説明では、情報提供装置５、６は、情報提供装置４と同様の機能を発揮するものとして、説明を省略する。
【００４９】
図４に示す例では、端末装置３は、ＧＰＳアンテナ２０、位置情報取得部２１、位置情報記憶部２２、受信部２３、乱数生成部２４、秘匿位置情報生成部２５、送信部２６を有する。例えば、ＧＰＳアンテナ２０は、ＧＰＳの各衛星が出力した信号を受信し、受信した信号を位置情報取得部２１に出力する。
【００５０】
位置情報取得部２１は、ＧＰＳアンテナ２０が受信した各信号から端末装置３の位置情報を取得し、取得した情報を位置情報記憶部２２に格納する。なお、位置情報取得部２１は、近傍判定に時刻等、位置情報以外の情報を用いる場合には、位置情報を取得した時刻等の情報とともに位置情報記憶部２２に出力する。また、位置情報取得部２１は、常時端末装置３の位置を取得する必要はなく、所定の時間間隔で位置情報を取得することとしてもよいし、近傍判定を近傍判定サーバ７に要求したタイミングで実行してもよい。位置情報記憶部２２は、端末装置３の位置情報を記憶する記憶装置であり、例えばフラッシュメモリ等の半導体メモリである。
【００５１】
受信部２３は、インターネット８を介して、鍵生成サーバ２から一次結合を受信する。そして、受信部２３は、鍵生成サーバ２から受信した一次結合を秘匿位置情報生成部２５に出力する。乱数生成部２４は、秘匿位置情報生成部２５から乱数の生成を要求された場合には、任意の乱数を生成し、生成した乱数を秘匿位置情報生成部２５に出力する。なお、乱数生成部２４が乱数を生成する手法は、任意の手法を用いることが可能であるものの、各情報提供装置４〜６と生成する乱数がかぶらないよう、各種パラメータがそれぞれ異なるものであることが望ましい。
【００５２】
秘匿位置情報生成部２５は、受信部２３から一次結合を受信すると、乱数生成部２４に乱数の生成を指示し、乱数を取得する。また、秘匿位置情報生成部２５は、位置情報記憶部２２から端末装置３の位置情報を取得する。そして、秘匿位置情報生成部２５は、位置情報から位置ベクトルを生成し、一次結合と乱数との積に位置ベクトルを加算した秘匿ベクトルを生成する。その後、秘匿位置情報生成部２５は、生成した秘匿ベクトルを近傍判定サーバ７に送信するよう送信部２６に指示する。
【００５３】
例えば、秘匿位置情報生成部２５は、ｎ次元の一次結合ｄ１＊ｖ１＋ｄ２＊ｖ２＋…＋ｄｎ＊ｖｎを受信するとともに、乱数生成部２４から乱数ｒ１を取得する。また、秘匿位置情報生成部２５は、位置情報記憶部２２が記憶する位置情報ａ１から「０」を最終成分とするｎ次元の位置ベクトル［ａ１、０］を生成する。そして、秘匿位置情報生成部２５は、ｃ１＝［ａ１、０］＋ｒ１＊ｂ１で表される秘匿ベクトルｃ１を生成し、生成した秘匿ベクトルｃ１を近傍判定サーバ７に送信するよう送信部２６に指示する。
【００５４】
送信部２６は、秘匿位置情報生成部２５から秘匿ベクトルを受信すると、受信した秘匿ベクトルを近傍判定サーバ７に送信する。なお、送信部２６は、図示しないアプリケーション等から近傍判定を依頼するよう要求された場合には、近傍判定の要求を近傍判定サーバ７に送信する。このような場合には、近傍判定サーバ７から近傍判定を要求された旨が鍵生成サーバ２に通知され、鍵生成サーバ２から端末装置３用の一次結合が配布されることとなる。
【００５５】
また、受信部２３は、インターネット８を介して、近傍判定の結果を近傍判定サーバ７から受信した場合は、図示しないアプリケーション等に近傍判定の結果を通知する。この結果、端末装置３は、利用者に近傍判定の結果として、近傍に位置するタクシー等を表示することとなる。
【００５６】
次に、図５を用いて、情報提供装置４の機能構成について説明する。なお、以下の説明では、情報提供装置５、６は、情報提供装置４と同様の機能を発揮するものとして、説明を省略する。また、図５に示すように、情報提供装置４は、端末装置３と同様の機能を発揮するため、端末装置３と同様の機能構成を有している。
【００５７】
例えば、図４に示すように、情報提供装置４は、ＧＰＳアンテナ３０、位置情報取得部３１、位置情報記憶部３２、受信部３３、乱数生成部３４、秘匿位置情報生成部３５、送信部３６を有する。ＧＰＳアンテナ３０は、ＧＰＳアンテナ２０と同様に、ＧＰＳの各衛星が出力した信号を受信し、受信した信号を位置情報取得部３１に出力する。
【００５８】
また、位置情報取得部３１は、位置情報取得部２１と同様に、ＧＰＳアンテナ３０が受信した各信号から情報提供装置４の位置情報を取得し、取得した情報を位置情報記憶部３２に格納する。位置情報記憶部３２は、位置情報記憶部２２と同様に、情報提供装置４の位置情報を記憶する記憶装置であり、例えばフラッシュメモリ等の半導体メモリである。
【００５９】
受信部３３は、受信部２３と同様に、インターネット８を介して、鍵生成サーバ２から一次結合を受信し、受信した一次結合を秘匿位置情報生成部３５に出力する。乱数生成部３４は、乱数生成部２４と同様に、秘匿位置情報生成部３５から乱数の生成を要求された場合には、任意の乱数を生成し、生成した乱数を秘匿位置情報生成部３５に出力する。
【００６０】
秘匿位置情報生成部３５は、秘匿位置情報生成部２５と同様に、受信部３３が受信した一次結合と、乱数生成部３４が生成した乱数と、情報提供装置４の位置情報から生成した位置ベクトルとを用いて、秘匿ベクトルを生成する。そして、秘匿位置情報生成部３５は、秘匿ベクトルを近傍判定サーバ７に送信するよう送信部３６に出力する。また、送信部３６は、送信部２６と同様に秘匿位置情報生成部３５から受信した秘匿ベクトルを、インターネット８を介して、近傍判定サーバ７に送信する。
【００６１】
次に、図６を用いて、近傍判定サーバ７の機能構成について説明する。図６は、実施例１に係わる近傍判定サーバの機能構成を説明する図である。図６に示す例では、近傍判定サーバ７は、受信部４０、秘匿位置情報記憶部４１、鍵行列記憶部４２、演算部４３、近傍判定部４４、判定結果出力部４５を有する。なお、秘匿位置情報記憶部４１は、端末装置３、および各情報提供装置４〜６から受信した秘匿ベクトルを記憶する記憶装置であり、例えばフラッシュメモリ等の半導体メモリである。また、鍵行列記憶部４２は、鍵生成サーバ２から受信した鍵行列を記憶する記憶装置であり、例えばフラッシュメモリ等の半導体メモリである。
【００６２】
受信部４０は、インターネット８を介して、鍵生成サーバ２から鍵行列を受信すると、受信した鍵行列を鍵行列記憶部４２に格納する。また、受信部４０は、インターネット８を介して、端末装置３、および各情報提供装置４〜６から秘匿ベクトルを受信すると、受信した秘匿ベクトルと送信元を示す情報とを対応付けて秘匿位置情報記憶部４１に格納する。
【００６３】
演算部４３は、秘匿位置情報記憶部４１に端末装置３、および各情報提供装置４〜６の秘匿ベクトルが秘匿位置情報記憶部４１に格納された場合は、以下の処理を実行する。まず、演算部４３は、各秘匿ベクトルを秘匿位置情報記憶部４１から取得し、鍵行列記憶部４２から鍵行列を取得する。次に、演算部４３は、端末装置３から受信した秘匿ベクトルと、各情報提供装置４〜６から受信した各秘匿ベクトルとの差分ベクトルｚをそれぞれ算出する。
【００６４】
そして、演算部４３は、算出した差分ベクトルｚから鍵行列を法とした際の剰余である剰余ベクトルを算出する。詳細には、演算部４３は、ｚｍｏｄＶ＝ｚ−［ｚ＊Ｖ−１］＊Ｖで定義される剰余ベクトルを算出する。なお、［ｑ］は、分数ｑの最近似整数への丸め込み写像を示す。
【００６５】
そして、演算部４３は、算出した剰余ベクトルを近傍判定部４４に出力する。なお、演算部４３は、各剰余ベクトルが、いずれかの情報提供装置と端末装置３との秘匿ベクトルに係わる剰余ベクトルであるかを近傍判定部４４に通知する。
【００６６】
近傍判定部４４は、演算部４３から受信した各剰余ベクトルの最終成分が「０」であるか否かを判定し、剰余ベクトルの最終成分が「０」である場合は、剰余ベクトルに係わる秘匿ベクトルの送信元と端末装置３とが近傍範囲に属すると判定する。そして、近傍判定部４４は、端末装置３の近傍範囲に属すると判定した情報提供装置を判定結果出力部４５に通知する。
【００６７】
例えば、近傍判定部４４は、端末装置３の秘匿ベクトルと情報提供装置４の秘匿ベクトルとの差分ベクトルから算出された剰余ベクトルの最終成分が「０」である場合は、情報提供装置４が端末装置３の近傍に位置すると判別する。そして、近傍判定部４４は、情報提供装置４を判定結果出力部４５に通知する。
【００６８】
一方、近傍判定部４４は、端末装置３の秘匿ベクトルと情報提供装置４の秘匿ベクトルとの差分ベクトルから算出された剰余ベクトルの最終成分が「０」ではない場合は、情報提供装置４が端末装置３の近傍に位置していないと判別する。また、近傍判定部４４は、すべての剰余ベクトルの最終成分が「０」以外の値であり、全ての情報提供装置４〜６が端末装置３の近傍に位置していないと判別した場合は、端末装置３の近傍範囲に情報提供装置が存在しない旨を判定結果出力部４５に出力する。
【００６９】
判定結果出力部４５は、判定結果を端末装置３に出力する場合は、近傍判定部４４から通知された情報提供装置、すなわち端末装置３の近傍に位置する情報提供装置を、インターネット８を介して、端末装置３に通知する。なお、判定結果出力部４５は、判定結果を各情報提供装置４〜６に出力する場合は、近傍判定部４４から通知された情報提供装置に、インターネット８を介して、端末装置３の情報を通知する。
【００７０】
なお、近傍判定サーバ７は、受信部４０が端末装置３から近傍判定の要求を受信した場合は、近傍判定の要求を受けた旨の通知を鍵生成サーバ２へ送信することで、鍵生成サーバ２から各端末装置３、および各情報提供装置４〜６へ一次結合を配布させる。そして、近傍判定サーバ７は、各端末装置３、および各情報提供装置４〜６から、それぞれ異なる乱数、およびそれぞれ異なる一次結合を用いて秘匿化された秘匿ベクトルを受信し、受信した秘匿ベクトルを用いて、近傍判定を行う。
【００７１】
次に、図７を用いて、近傍判定システムが実行する処理の具体例について説明する。図７は、近傍判定システムが実行する処理の一例を説明する図である。なお、図７に示す例では、端末装置３は、近傍のタクシーを検索する利用者の端末装置であるものとし、情報提供装置４、５は、タクシーに設置されているものとする。
【００７２】
また、図７に示す例では、端末装置３、および情報提供装置４、５は、位置情報として、３次元の情報を用いているものとする。例えば、図７に示す例では、端末装置３の位置情報ａが［１００，１００，１００］であり、情報提供装置４の位置情報ａ１が［１１５，１０５，１０３］であり、情報提供装置５の位置情報ａ２が［２００，７５，１０２］であるものとする。
【００７３】
まず、鍵生成サーバ２は、図７中（Ａ）に示す鍵行列Ｖを生成する。具体的には、鍵生成サーバ２は、閾値「４０，３０，２０」を対角要素とする３×３の対角行列に、４行目の行「０，０，０」を付加し、さらに乱数ベクトル「１０，５，７，１３」を４列目に付加した４×４の鍵行列Ｖを生成する。そして、鍵生成サーバ２は、図７中（Ｂ）に示すように、鍵行列Ｖを近傍判定サーバ７に送信する。
【００７４】
また、鍵生成サーバ２は、鍵行列Ｖから端末装置３、および情報提供装置４、５に配布する一次結合を生成する。例えば、鍵生成サーバ２は、鍵行列の各行ベクトルをｖ１〜ｖ４とし、ｖ２とｖ３との和である一次結合ｂ＝［０，３０，２０，１２］を算出する。そして、鍵生成サーバ２は、図７中（Ｃ）に示すように、一次結合ｂ＝［０，３０，２０，１２］を端末装置３に出力する。
【００７５】
このような場合は、端末装置３は、乱数ｒ＝１３を選択し、図７中（Ｄ）に示すように、位置情報ａ、一次結合ｂ、および乱数ｒから秘匿ベクトルｃ＝［ａ、０］＋ｒ*ｂ＝［１００，４９０，３６０，１５６］を算出する。そして、端末装置３は、図７中（Ｅ）に示すように、算出した秘匿ベクトルｃ＝［１００，４９０，３６０，１５６］を近傍判定サーバ７に送信する。
【００７６】
一方、鍵生成サーバ２は、鍵行列Ｖの行ベクトルｖ１とｖ４との和である一次結合ｂ１＝［４０，０，０，２３］を算出し、行ベクトルｖ１とｖ３との和である一次結合ｂ２＝［４０，０，２０，１７］を算出する。そして、鍵生成サーバ２は、図７中（Ｆ）に示すように、一次結合ｂ１を情報提供装置４に配布し、一次結合ｂ２を情報提供装置５に配布する。
【００７７】
このような場合は、情報提供装置４は、乱数ｒ１＝７を選択し、図７中（Ｇ）に示すように、位置情報ａ１、一次結合ｂ１、および乱数ｒ１から秘匿ベクトルｃ１＝［ａ１、０］＋ｒ１＊ｂ１＝［３９５，１０５，１０３，１６１］を算出する。そして、情報提供装置４は、図７中（Ｈ）に示すように、算出した秘匿ベクトルｃ１＝［３９５，１０５，１０３，１６１］を近傍判定サーバ７に送信する。
【００７８】
また、情報提供装置５は、乱数ｒ２＝−４を選択し、図７中（Ｉ）に示すように、位置情報ａ２、一次結合ｂ２、および乱数ｒ２から秘匿ベクトルｃ２＝［ａ２、０］＋ｒ２＊ｂ２＝［４０，７５，２２，−６８］を算出する。そして、端末装置３は、図７中（Ｊ）に示すように、算出した秘匿ベクトルｃ２＝［４０，７５，２２，−６８］を近傍判定サーバ７に送信する。
【００７９】
このような場合には、近傍判定サーバ７は、図７中（Ｋ）に示すように、秘匿ベクトルｃ１と秘匿ベクトルｃとの差分ベクトルｚ１、および秘匿ベクトルｃ２と秘匿ベクトルｃとの差分ベクトルｚ２から鍵行列Ｖを法とする剰余ベクトルを算出する。具体的には、近傍判定サーバ７は、差分ベクトルｚ１＝（ｃ１−ｃ）を算出し、ｚ１ｍｏｄＶ＝ｚ１−［ｚ１＊Ｖ−１］＊Ｖ＝［１５，５，３，０］を算出する。また、近傍判定サーバ７は、差分ベクトルｚ２＝（ｃ２−ｃ）を算出し、ｚ２ｍｏｄＶ＝ｚ２−［ｚ２＊Ｖ−１］＊Ｖ＝［−２０，５，２，１］を算出する。
【００８０】
この結果、近傍判定サーバ７は、秘匿ベクトルｃ１から算出した剰余ベクトルの最終成分が「０」であるので、情報提供装置４が端末装置３の近傍に位置すると判別する。一方、近傍判定サーバ７は、秘匿ベクトルｃ２から算出した剰余ベクトルの最終成分が「０」ではないため、情報提供装置５が端末装置３の近傍には位置していないと判別する。そして、近傍判定サーバ７は、端末装置３に情報提供装置４を通知し、もしくは、情報提供装置４に端末装置３の位置を通知し、処理を終了する。
【００８１】
次に、図８を用いて、近傍判定システム１が実行する処理の流れについて説明する。図８は、実施例１に係わる近傍判定システムが実行する処理の流れを説明するためのシーケンス図である。まず、鍵生成サーバ２は、鍵行列を生成し（ステップＳ１０１）、近傍判定サーバ７に鍵行列を送信する（ステップＳ１０２）。
【００８２】
次に、鍵生成サーバ２は、鍵行列から行ベクトルの一次結合を生成し、生成した一次結合を各情報提供装置４〜６、および端末装置３に配布する（ステップＳ１０３）。すると、各情報提供装置４〜６は、乱数と配布された一次結合を用いて、位置情報を秘匿した秘匿ベクトルを生成する（ステップＳ１０４）。そして、各情報提供装置４〜６は、生成した秘匿ベクトルを近傍判定サーバ７に送信する（ステップＳ１０５）。また、端末装置３は、乱数と配布された一次結合を用いて、位置情報を秘匿した秘匿ベクトルを生成する（ステップＳ１０６）。そして、端末装置３は、秘匿ベクトルを近傍判定サーバ７に送信する（ステップＳ１０７）。
【００８３】
すると、近傍判定サーバ７は、各情報提供装置４〜６から受信した秘匿ベクトルと、端末装置３から受信した秘匿ベクトルとの差分ベクトルを算出し（ステップＳ１０８）、算出した差分ベクトルから鍵行列に対する剰余ベクトルを算出する（ステップＳ１０９）。その後、近傍判定サーバ７は、算出した剰余ベクトルを用いて近傍判定を行い（ステップＳ１１０）、判定結果を端末装置３に通知し（ステップＳ１１１）、処理を終了する。
【００８４】
［近傍判定サーバ７の効果］
上述したように、近傍判定サーバ７は、近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、端末装置３の位置情報と、端末装置３が生成した乱数とに基づいて秘匿ベクトルを収集する。また、近傍判定サーバ７は、鍵行列の行ベクトルの一次結合と、各情報提供装置４〜６の位置情報と、各情報提供装置４〜６が生成した乱数とに基づいて秘匿ベクトルを収集する。
【００８５】
そして、近傍判定サーバ７は、端末装置３から収集した秘匿ベクトルと、各情報提供装置４〜６から収集した秘匿ベクトルとの差分から、鍵行列を法とした際の剰余である剰余ベクトルを算出する。その後、近傍判定サーバ７は、算出した剰余ベクトルに基づいて、端末装置３の位置と各情報提供装置４〜６の位置とが近傍範囲に属するか否かを判定する。
【００８６】
このように、端末装置３、および各情報提供装置４〜６は、それぞれが生成した乱数を用いて位置情報を秘匿化する。このような場合においては、送信された位置情報ごとに、秘匿化する乱数が異なるので、秘匿化した位置情報が他の装置に漏れた場合にも、基となる位置情報を逆算するのが困難になる。このため、近傍判定サーバ７は、端末装置３、および各情報提供装置４〜６の位置情報を他の装置に秘匿したまま、近傍判定を行うことができる。
【００８７】
また、近傍判定サーバ７は、鍵行列の行ベクトルの一次結合と、端末装置３、および各情報提供装置４〜６が生成した乱数とを用いて秘匿化された位置情報を収集し、秘匿化された位置情報の差分から、鍵行列を法とした際の剰余である剰余ベクトルを算出する。そして、近傍判定サーバ７は、剰余ベクトルの成分に基づいて、端末装置３の位置と各情報提供装置４〜６の位置とが近傍範囲に属するか否かを判定する。このため、近傍判定サーバ７は、各位置情報がそれぞれ異なる乱数で秘匿化されている場合にも、各位置情報を秘匿化したままで近傍判定を行うことができる。
【００８８】
また、近傍判定サーバ７は、それぞれ異なる一次結合で秘匿化された位置情報を収集する。このため、近傍判定サーバ７は、秘匿化された位置情報の解読困難性を向上させることができる。
【００８９】
また、近傍判定サーバ７は、端末装置３からは、鍵行列の一次結合と、端末装置３が選択した乱数との積に、端末装置３の位置情報を加算した秘匿ベクトルを収集する。また、近傍判定サーバ７は、各情報提供装置４〜６からは、鍵行列の一次結合と、各情報提供装置４〜６がそれぞれ選択した乱数との積に、各情報提供装置４〜６の位置情報を加算した秘匿ベクトルを収集する。このため、近傍判定サーバ７は、端末装置３、および各情報提供装置４〜６の位置情報を秘匿したまま、近傍判定を行うことができる。
【実施例２】
【００９０】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【００９１】
（１）鍵行列について
上述した鍵生成サーバ２は、近傍範囲の閾値として、位置情報を対角成分とする対角行列を用いて、鍵行列を生成した。しかし、実施例はこれに限定されるものではない。すなわち、鍵生成サーバ２は、近傍判定に用いる任意の情報を閾値として用いることができる。例えば、鍵生成サーバ２は、位置情報に時間情報を付加した４次元の閾値を対角成分とする対角行列を用いて、鍵行列を生成してもよい。このような場合には、近傍判定サーバ７は、端末装置３が位置情報を取得した時刻と、各情報提供装置４〜６が位置情報を取得した時間とが所定の範囲内に収まる場合に、近傍に属する旨の判定を行うこととなる。
【００９２】
なお、鍵生成サーバ２は、鍵行列の内容として、ｘｙｚ軸方向の情報だけではなく、緯度、経度、時間のみならず、任意の特徴量、判定量、その他近傍範囲に属するか否かを判定するための任意の数値を用いることができる。
【００９３】
（２）近傍判定について
上述した近傍判定サーバ７は、剰余ベクトルの最終成分が「０」であるか否かで、端末装置３と各情報提供装置４〜６とが近傍に属するか否かを判定した。しかし、実施例はこれに限定されるものではない。例えば、近傍判定サーバ７は、剰余ベクトルの最終成分だけではなく、任意の数の要素を用いて近傍判定を行うことができる。
【００９４】
例えば、鍵生成サーバ２は、閾値を対角成分とするｍ×ｍの正方行列に、判定要素として各成分が「０」の行ベクトルをｕ個付加したｍ＋ｕ×ｍの行列を生成する。ここで、ｕは、任意の自然数である。また、鍵生成サーバ２は、ｍ＋ｕ次元の乱数ベクトルをｕ個生成し、生成したｕ個の乱数ベクトルをｍ＋１〜ｍ＋ｕ列目の列ベクトルとしてｍ＋ｕ×ｍの行列に付加することで、ｍ＋ｕ×ｍ＋ｕの鍵行列Ｖを生成する。また、端末装置３、および各情報提供装置４は、成分が「０」である次元を位置情報にｕ個付加したｍ＋ｕ次元の位置ベクトルを生成し、乱数と鍵行列Ｖの一次結合で秘匿化して、近傍判定サーバ７に送信する。
【００９５】
すると、近傍判定サーバ７は、実施例１と同様の処理を行うことで、ｍ＋ｕ次元の剰余ベクトルを取得する。そして、近傍判定サーバ７は、剰余ベクトルのｍ＋１次元目からｍ＋ｕ次元目までの要素がそれぞれ「０」であるか否かを判定し、「０」であると判定した要素の数によって、近傍判定を行う。このように、近傍判定システム１は、任意の数の要素を用いて近傍判定を行うことができる。また、近傍判定システム１は、複数の数の要素を用いて近傍判定を行った場合には、近傍判定の制度を向上させることができる。
【００９６】
（３）使用様態について
上述した近傍判定システム１は、端末装置３と各情報提供装置４〜６の位置が近傍に属するか否かを判定した。しかし、実施例はこれに限定されるものではなく、任意の２つの情報が近傍に属するか否かを判定するシステムについて、近傍判定システム１を適用することができる。
【００９７】
例えば、図９は、生体認証システムの一例を説明する図である。図９に示すように、生体認証システム１ａは、鍵生成サーバ２、端末装置３、ストレージ装置４ａ、近傍判定サーバ７、インターネット８を有する。例えば、近傍判定システム１は、利用者の指紋・静脈などの生体情報から抽出される特徴量ベクトルをあらかじめ取得し、取得した特長量ベクトルをネットワーク上のストレージ装置４ａに格納する。
【００９８】
また、鍵生成サーバ２は、特徴量ベクトルの近傍範囲として許容される各成分の閾値を対角成分とする対角行列から、鍵行列を生成する。そして、鍵生成サーバ２は、鍵行列を近傍判定サーバ７に送信するとともに、鍵行列の各行ベクトルから生成した一次結合を端末装置３、およびストレージ装置４ａに出力する。
【００９９】
このような場合には、端末装置３は、利用者の指紋や静脈から特徴量ベクトルを抽出し、実施例１と同様に抽出した特徴量ベクトルを秘匿化し、秘匿化した特徴量ベクトルを近傍判定サーバ７に送信する。また、ストレージ装置４ａは、登録された利用者の特徴量ベクトルを情報提供装置４と同様の処理を用いて秘匿化し、秘匿化した特徴量ベクトルを近傍判定サーバ７に送信する。その後、近傍判定サーバ７は、実施例１と同様の処理を行うことで、利用者の特徴量ベクトルを秘匿化したまま、近傍判定を行うことができる。
【０１００】
また、近傍判定システム１や生体認証システム１ａは、上述した位置情報や生体認証に用いられる特徴量ベクトルの近傍判定だけではなく、機密文章間の秘匿類似判定を行うことができる。例えば、ストレージ装置４ａは、機密文章から特徴を有する文字、文章部分を抽出し、抽出した部分の特徴量を示す特徴量ベクトルに変換する。そして、端末装置３は、判定対象となる文章から特徴を有する文字、文章部分を抽出し、抽出した部分の特徴量を示す特徴量ベクトルを取得する。
【０１０１】
その後、端末装置３、およびストレージ装置４ａは、実施例１と同様の処理により秘匿化した特徴量ベクトルを近傍判定サーバ７に出力する。この結果、近傍判定サーバ７は、機密文章や判定対象となる文章の具体的内容を秘匿したまま、類似度判定を行うことができる。
【０１０２】
また、近傍判定システム１は、ネットワーク監視サービスにおける秘匿ＩＰアドレスの位置判定を行うことができる。例えば、情報提供装置４には、近傍判定システム１に接続された情報処理装置のＩＰアドレスが記憶されている。このような情報処理装置は、障害が生じた場合には、ＩＰアドレスを秘匿化して近傍判定サーバ７に出力する。すると、近傍判定サーバ７は、情報提供装置４から秘匿化された各情報処理装置のＩＰアドレスを収集し、ＩＰアドレスを秘匿化したままで、障害が生じた情報処理装置を特定することができる。
【０１０３】
上述したように、近傍判定システム１は、位置情報だけでなく、生体認証、機密文章間の秘匿類似判定、秘匿ＩＰアドレス一致判定等、任意の情報について近傍判定を行うことができる。なお、近傍判定システム１が取り扱う情報の種類によって、鍵情報を生成する際に用いる閾値の次元数や値が異なるが、任意の次元数や値に対し、近傍判定システム１は、実施例１と同様の処理により、近傍判定を行うことができる。
【０１０４】
（４）クラウドについて
上述した実施例１では、鍵生成サーバ２、端末装置３、情報提供装置４、近傍判定サーバ７がインターネット８を介して接続する例について記載した。しかし、実施例はこれに限定されるものではなく、例えば、鍵生成サーバ２や近傍判定サーバ７は、いわゆるクラウドシステムにより実現されてもよい。
【０１０５】
すなわち、鍵生成サーバ２は、ネットワーク上に設置された複数の情報処理装置が、図２に示したベクトル記憶部１０、乱数生成部１１、鍵行列生成部１２、一次結合生成部１３の処理をそれぞれ実行することで、実現されてもよい。また、近傍判定サーバ７は、ネットワーク上に設置された複数の情報処理装置が、図６に示した受信部４０、秘匿位置情報記憶部４１、鍵行列記憶部４２、演算部４３、近傍判定部４４、判定結果出力部４５の処理をそれぞれ実行することで、実現されてもよい。
【０１０６】
（５）端末装置が送信する情報について
上述した実施例１では、端末装置３が自身の位置情報を秘匿化して近傍判定サーバ７に送信する処理について記載した。しかし、実施例はこれに限定されるものではない。例えば、端末装置３は、タクシー会社に設置された端末装置であり、タクシーの呼び出しを依頼した利用者の位置を取得し、取得した利用者の位置を秘匿化して近傍判定サーバ７に出力してもよい。このような場合には、端末装置３は、利用者の近傍に位置するタクシーを識別し、識別したタクシーを利用者に配車することができる。
【０１０７】
（６）プログラム
上記の実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１０を用いて、上記の実施例と同様の機能を有する近傍判定プログラムを実行するコンピュータの一例について説明する。
【０１０８】
図１０は、近傍判定プログラムを実行するコンピュータの一例について説明するための図である。図１０に示すように、コンピュータ１００は、ＣＰＵ１５０と、ＲＯＭ（Read  Only  Memory）１６０と、ＨＤＤ（Hard  Disk  Drive）１７０と、ＲＡＭ（Random  Access  Memory）１８０とを有する。これら１１０〜１８０の各部はバス１４０を介して接続される。
【０１０９】
ＨＤＤ１７０には、近傍判定装置２０と同様の機能を発揮する近傍判定プログラム１７０ａが予め記憶される。この近傍判定プログラム１７０ａについては、実施例１で示した各構成要素と同様、適宜統合又は分離してもよい。すなわち、ＨＤＤ１７０に格納される各データは、常に全てのデータがＨＤＤ１７０に格納される必要はなく、処理に必要なデータのみがＨＤＤ１７０に格納されればよい。
【０１１０】
そして、ＣＰＵ１５０が、近傍判定プログラム１７０ａをＨＤＤ１７０から読み出してＲＡＭ１８０に展開する。これによって、図１０に示すように、近傍判定プログラム１７０ａは、近傍判定プロセス１８０ａとして機能する。この近傍判定プロセス１８０ａは、ＨＤＤ１７０から読み出した各種データを適宜ＲＡＭ１８０上の自身に割り当てられた領域に展開し、この展開した各種データに基づいて各種処理を実行する。
【０１１１】
なお、近傍判定プロセス１８０ａは、受信部４０、演算部４３、近傍判定部４４、判定結果出力部４５にて実行される処理を含む。また、ＣＰＵ１５０上で仮想的に実現される各処理部は、常に全ての処理部がＣＰＵ１５０上で動作する必要はなく、処理に必要な処理部のみが仮想的に実現されればよい。
【０１１２】
なお、上記の近傍判定プログラム１７０ａについては、必ずしも最初からＨＤＤ１７０やＲＯＭ１６０に記憶させておく必要はない。例えば、コンピュータ１００に挿入されるフレキシブルディスク、いわゆるＦＤ（Flexible  Disk）、ＣＤ（Compact  Disk）−ＲＯＭ、ＤＶＤ（Digital  Video  Disk）、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させる。
【０１１３】
そして、コンピュータ１００がこれらの可搬用の物理媒体から各プログラムを取得して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ、ＷＡＮ（Wide  Area  Network）などを介してコンピュータ１００に接続される他のコンピュータまたはサーバ装置などに各プログラムを記憶させておき、コンピュータ１００がこれらから各プログラムを取得して実行するようにしてもよい。
【０１１４】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１１５】
（付記１）第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定する近接判定方法において、
前記近傍範囲を判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集し、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを収集し、
前記収集した第１の秘匿ベクトルと、前記第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出し、
前記算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する
処理を情報処理装置が実行することを特徴とする近傍判定方法。
【０１１６】
（付記２）前記第１の秘匿ベクトルに係わる一次結合とは異なる一次結合と、前記第２の数値情報と、前記第２の乱数とに基づく第２の秘匿ベクトルを収集することを特徴とする付記１に記載の近傍判定方法。
【０１１７】
（付記３）前記一次結合と第１の乱数の積に前記第１の数値情報を加算した第１の秘匿ベクトル、および、前記一次結合と第２の乱数との積に前記第２の数値情報を加算した第２の秘匿ベクトルを収集することを特徴とする付記１または２に記載の近傍判定方法。
【０１１８】
（付記４）第１の情報処理装置の位置を示す前記第１の数値情報と、前記一次結合と、前記第１の乱数とに基づく前記第１の秘匿ベクトル、および、第２の情報処理装置の位置を示す前記第２の数値情報と、前記一次結合と、前記第２の乱数とに基づく前記第２の秘匿ベクトルを収集することを特徴とする付記１〜３のいずれか１つに記載の近傍判定方法。
【０１１９】
（付記５）第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定するための閾値を対角成分とする行列に乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集する第１の収集部と、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを第２の情報処理装置から収集する第２の収集部と、
前記第１の収集部が収集した第１の秘匿ベクトルと、前記第２の収集部が収集した第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出する算出部と、
前記算出部が算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する判定部と
を有することを特徴とする近傍判定装置。
【０１２０】
（付記６）前記第２の収集部は、前記第１の秘匿ベクトルに係わる一次結合とは異なる一次結合と、前記第２の数値情報と、前記第２の乱数とに基づく第２の秘匿ベクトルを収集することを特徴とする付記５に記載の近傍判定装置。
【０１２１】
（付記７）前記第１の収集部は、前記一次結合と第１の乱数との積に前記第１の数値情報を加算した第１の秘匿ベクトルを収集し
前記第２の収集部は、前記一次結合と第２の乱数との積に前記第２の数値情報を加算した第２の秘匿ベクトルを収集することを特徴とする付記５または６に記載の近傍判定装置。
【０１２２】
（付記８）前記第１の収集部は、第１の情報処理装置の位置を示す前記第１の数値情報と、前記一次結合と、前記第１の乱数とに基づく前記第１の秘匿ベクトルを収集し、
前記第２の収集部は、第２の情報処理装置の位置を示す前記第２の数値情報と、前記一次結合と、前記第２の乱数とに基づく前記第２の秘匿ベクトルを収集することを特徴とする付記５〜７のいずれか１つに記載の近傍判定装置。
【０１２３】
（付記９）第１の情報処理装置が記憶する第１の数値情報と第２の情報処理装置が記憶する第２の数値情報とが近傍範囲に属するか否かを判定する近傍判定装置と、
前記第１の数値情報と前記第２の数値情報とを秘匿するための鍵行列を生成する鍵行列生成装置と
を有する近傍判定システムにおいて、
前記鍵行列生成装置は、
前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定するための閾値を対角成分とする行列に、乱数ベクトルを最終列として付加して生成された鍵行列を生成する生成部と、
前記生成部が生成した鍵行列の行ベクトルの一次結合を前記第１の情報処理装置、および前記第２の情報処理装置へ送信し、前記生成部が生成した鍵行列を前記近傍判定装置へ送信する送信部と
を有し、
前記近傍判定装置は、
前記鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを前記第１の情報処理装置から収集する第１の収集部と、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを前記第２の情報処理装置から収集する第２の収集部と、
前記第１の収集部が収集した第１の秘匿ベクトルと、前記第２の収集部が収集した第２の秘匿ベクトルとの差分から、前記鍵行列生成装置から受信した鍵行列を法とした際の剰余である剰余ベクトルを算出する算出部と、
前記算出部が算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する判定部と
を有することを特徴とする近傍判定システム。
【０１２４】
（付記１０）前記第２の収集部は、前記第１の秘匿ベクトルに係わる一次結合とは異なる一次結合と、前記第２の数値情報と、前記第２の乱数とに基づく第２の秘匿ベクトルを収集することを特徴とする付記９に記載の近傍判定システム。
【０１２５】
（付記１１）前記第１の収集部は、前記一次結合と第１の乱数との積に前記第１の数値情報を加算した第１の秘匿ベクトルを収集し
前記第２の収集部は、前記一次結合と第２の乱数との積に前記第２の数値情報を加算した第２の秘匿ベクトルを収集することを特徴とする付記９または１０に記載の近傍判定システム。
【０１２６】
（付記１２）前記第１の収集部は、第１の情報処理装置の位置を示す前記第１の数値情報と、前記一次結合と、前記第１の乱数とに基づく前記第１の秘匿ベクトルを収集し、
前記第２の収集部は、第２の情報処理装置の位置を示す前記第２の数値情報と、前記一次結合と、前記第２の乱数とに基づく前記第２の秘匿ベクトルを収集することを特徴とする付記９〜１１のいずれか１つに記載の近傍判定システム。
【０１２７】
（付記１３）第１の数値情報と第２の数値情報とが近傍範囲に属するかを判定するコンピュータに、
前記近傍範囲を判定するための閾値を対角成分とする行列に、乱数ベクトルを最終列として付加して生成された鍵行列の行ベクトルの一次結合と、前記第１の数値情報と、第１の乱数とに基づいて第１の秘匿ベクトルを収集し、
前記鍵行列の行ベクトルの一次結合と、前記第２の数値情報と、第２の乱数とに基づいて第２の秘匿ベクトルを収集し、
前記収集した第１の秘匿ベクトルと、前記第２の秘匿ベクトルとの差分から、前記鍵行列を法とした際の剰余である剰余ベクトルを算出し、
前記算出した剰余ベクトルに基づいて、前記第１の数値情報と前記第２の数値情報とが近傍範囲に属するか否かを判定する
処理を実行させることを特徴とする近傍判定プログラム。
【符号の説明】
【０１２８】
１  近傍判定システム
１ａ  生体認証システム
２  鍵生成サーバ
３  端末装置
４，５，６  情報提供装置
４ａ  ストレージ装置
７  近傍判定サーバ
１０  ベクトル記憶部
１１  乱数生成部
１２  鍵行列生成部
１３  一次結合生成部
１４  送信部
２０、３０  ＧＰＳアンテナ
２１、３１  位置情報取得部
２２、３２  位置情報記憶部
２３、３３  受信部
２４、３４  乱数生成部
２５、３５  秘匿位置情報生成部
２６、３６  送信部
【図１】
2014095878.tif 000003
【図２】
2014095878.tif 000004
【図３】
2014095878.tif 000005
【図４】
2014095878.tif 000006
【図５】
2014095878.tif 000007
【図６】
2014095878.tif 000008
【図７】
2014095878.tif 000009
【図８】
2014095878.tif 000010
【図９】
2014095878.tif 000011
【図１０】
2014095878.tif 000012