バイナリ埋め込みを用いたプライバシーが保護される信号をハッシュする方法
【課題】信号比較のためにバイナリ埋め込みを用いた、プライバシー保護ハッシング方法を提供する。
【解決手段】信号のハッシュが、信号のランダム射影のディザリング及びスケーリングによって求められる。次に、ディザリング及びスケーリングされたランダム射影は、非単調スカラー量子化器を用いて量子化されて、ハッシュが形成され、信号のプライバシーは、スケーリング、ディザリング、及び射影のパラメーターが、求めるステップ及び量子化するステップによってしか知られていない限り保護される。
【解決手段】信号のハッシュが、信号のランダム射影のディザリング及びスケーリングによって求められる。次に、ディザリング及びスケーリングされたランダム射影は、非単調スカラー量子化器を用いて量子化されて、ハッシュが形成され、信号のプライバシーは、スケーリング、ディザリング、及び射影のパラメーターが、求めるステップ及び量子化するステップによってしか知られていない限り保護される。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には、基礎を成す信号のプライバシーを保護するように信号をハッシュすることに関し、より詳細には、ハッシュされた信号をセキュアに比較することに関する。
【背景技術】
【０００２】
多くの信号処理、機械学習、及びデータマイニングの用途は、信号を比較して、それらの信号がどの程度類似しているかを何らかの類似度メトリック又は距離メトリックに従って求めることを必要とする。これらの用途の多くにおいて、比較は、信号のクラスター内の信号のうちのいずれがクエリ信号に最も類似しているかを求めるのに用いられる。
【０００３】
距離尺度を用いる複数の最近傍探索(ＮＮＳ)法が既知である。近接度探索又は類似度探索としても知られるＮＮＳは、メトリック空間内の最も近い傍データを求める。メトリック空間Ｍ内のデータの集合Ｓ(クラスター)及びクエリｑ∈Ｍについて、探索は、集合Ｓ内でクエリｑに最も近いデータｓを求める。
【０００４】
幾つかの用途では、探索はセキュアマルチパーティ計算(ＳＭＣ)を用いて実行される。ＳＭＣは複数のパーティを可能にし、例えばサーバーが１つ又は複数のクライアントからの入力信号の関数を計算してクライアント(複数の場合もあり)への出力信号を生成する一方、入力及び出力は、クライアントにおいてのみ非公開で知られている。加えて、サーバーによって用いられるプロセス及びデータは、サーバーにおいて非公開のままである。このため、ＳＭＣは、クライアントもサーバーも互いの非公開データ及び非公開プロセスから何も知ることができないという意味でセキュアである。このため、以下において、セキュアとは、マルチパーティ計算に用いられるデータの所有者しか、そのデータ及びそのデータに適用されるプロセスが何であるかを知らないことを意味する。
【０００５】
これらの用途では、信号を、サーバーにおける管理可能な計算複雑度、及びクライアントとサーバーとの間の低い通信オーバーヘッドと比較することが必要である。ＮＮＳの難度は、プライバシー制約が存在するとき、すなわちパーティのうちの１つ又は複数が、探索に関連した信号、データ、又は方法を他のパーティと共有することを望まないときに増大する。
【０００６】
ソーシャルネットワーキング、ユーザーデータのインターネットベースのストレージ、及びクラウドコンピューティングの出現により、プライバシー保護計算は重要度を増している。プライバシー制約を満たすために、例えば類似度を求めることを依然として可能にしながら、１つ又は複数のパーティのデータは通常、加法的準同形暗号化システムを用いて暗号化される。
【０００７】
１つの方法は、クライアントのクエリをサーバーに明らかにすることなくＮＮＳを実行し、サーバーは、ｋ最近傍集合内のデータ以外、そのサーバーのデータベースを明らかにしない。距離決定は暗号化領域内で実行される。したがって、本方法の計算複雑度はデータ項目数の二次式となり、入力の暗号化及び出力の復号化が必要とされるので、この計算複雑度は甚大である。剪定技法を用いて距離決定の回数を低減し、計算及び通信の線形複雑度を得ることができるが、暗号化データの処理及び送信に起因して、プロトコルオーバヘッドは依然として極めて大きい。
【０００８】
したがって、プロセスに関与する全てのパーティのプライバシーを依然として確保しながら、ハッシュ計算を実行する複雑度を低減することが望ましい。
【０００９】
この発明は、２０１０年８月２４日にBoufounosによって出願された「Method for Hierarchical Signal Quantization and Hashing」と題する米国特許出願第１２／８６１，９２３号に関連する。
【００１０】
関連出願第１２／８６１，９２３号は、階層的信号量子化及び局所性鋭敏型ハッシュのために非単調量子化器を用いる方法を記載している。階層的操作を可能にするために、比較的大きな値の感度パラメーターΔが、より広範囲の入力信号に対する精度の粗い操作を可能にする一方、比較的小さな値のパラメーターが、類似した入力信号に対し精度の細かい操作を可能にする。したがって、反復ごとに感度パラメーターは減少する。
【００１１】
上記関連出願において記載されているように、選択する最も重要なパラメーターは感度パラメーターである。このパラメーターは、ハッシュがどのように信号を互いに区別するかを制御する。信号対間の距離尺度が検討される場合(距離が小さいほど、信号はより類似する)、Δによって、ハッシュが距離変化に対しどの程度感度が高いかが決まる。特に、Δが小さい場合、ハッシュは信号が非常に類似しているときの類似度変化に対し感度が高いが、類似していない信号の類似度変化に対し感度が高くない。Δが大きくなるとともに、ハッシュはそれほど類似していない信号に対し、より感度が高くなるが、類似している信号の感度のうちの幾らかが失われる。この特性は、信号の階層的ハッシュを構成するのに用いられる。ここで、第１の幾つかのハッシュ係数は、より大きな値をΔに用いて構成され、Δの値は後続の値について減少される。特に、大きなΔを用いて第１の幾つかのハッシュ値を計算することによって、計算的に単純な粗い信号再構成又は粗い距離推定が可能になり、これによって、離れた信号であってもその信号の情報が提供される。次に、より小さなΔを用いて得られた後続のハッシュ値を用いて、信号再構成を精緻化するか、又はより類似した信号の距離情報を精緻化することができる。
【００１２】
この方法は、階層的信号量子化に有用である。しかしながら、この方法はプライバシーを保護しない。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
この発明は、信号比較のためにバイナリ埋め込みを用いた、プライバシー保護ハッシング方法を提供する。
【課題を解決するための手段】
【００１４】
この発明の実施の形態は、信号比較のためにバイナリ埋め込みを用いた、プライバシー保護ハッシング方法を提供する。１つの応用形態では、セキュアな領域内で、１つ又は複数のハッシュされた信号が比較され、それらの信号の類似度が求められる。本方法を適用して、最近傍探索(ＮＮＳ)及びクラスタリングを近似することができる。本方法は、量子化されたランダム埋め込みを用いて求められた埋め込みに基づく局所性鋭敏型バイナリハッシュ方式に部分的に基づく。
【００１５】
信号から抽出されたハッシュは、２つの信号間の距離が或る所定のしきい値未満であるならば、その距離(類似度)に関する情報を提供する。信号間の距離がしきい値よりも大きい場合、距離に関する情報は明らかにされない。さらに、ランダム化された埋め込みパラメーターが知られていない場合、任意の２つの信号のハッシュ間の相互情報は、信号間のｌ２距離(ユークリッドノルム)とともに指数関数的にゼロまで減少する。バイナリハッシュを用いて、暗号化された信号を直接用いる従来の方法と比較して大幅に低い複雑度で、プライバシーを保護したＮＮＳを実行することができる。
【００１６】
本方法は、量子化されたランダム射影を用いたセキュアな安定した埋め込みに基づく。局所性鋭敏型の特性が達成され、ここで、ハッシュ間のハミング距離は、基礎を成すデータ間のｌ２距離が所定のしきい値未満である限り、この距離に比例する。
【００１７】
基礎を成す信号又はデータが類似していない場合、ハッシュは、埋め込みパラメーターが明らかにされていないならば、データ間の真の距離に関する情報を提供しない。
【００１８】
プライバシーを保護したＮＮＳの埋め込み方式は、クラスタリング及び認証の用途のためのプロトコルを提供する。これらのプロトコルの顕著な特徴は、距離決定を、基礎を成す信号又はデータを明らかにすることなく、平文においてハッシュに対して実行することができることである。平文は暗号化されずに(unencrypted)、すなわち平文で(in the clear)格納又は送信される。このため、暗号化領域の距離決定の観点からの計算オーバーヘッドは、暗号化を用いる従来技術よりも大幅に低い。さらに、暗号化が必要な場合であっても、固有の最近傍特性により、特定の数の最近傍を選択する最終ステップにおいて必要とされる複雑な選択プロトコルが不要になる。
【００１９】
本方法は、部分的に、レート効率のよい普遍的なスカラー量子化に基づく。このスカラー量子化は、量子化のための安定したバイナリ埋め込み、及び最近傍決定のための局所性鋭敏型ハッシュ(ＬＳＨ)法と密接な関係を有する。ＬＳＨは、潜在的に大きな信号の非常に短いハッシュを用いて、それらの信号の近似距離を効率的に求める。
【００２０】
本方法と従来技術との間の主要な差異は、この発明による方法が、この発明による埋め込みの情報理論的セキュリティを保証することである。
【図面の簡単な説明】
【００２１】
【図１Ａ】この発明の実施の形態による普遍的なスカラー量子化の概略図である。
【図１Ｂ】この発明の実施の形態による単位区間を用いた非単調量子化関数の図である。
【図１Ｃ】この発明の実施の形態による感度区間を用いた代替的な非単調量子化関数の図である。
【図１Ｄ】この発明の実施の形態による複数レベルの区間を用いた代替的な非単調量子化関数の図である。
【図２】この発明の実施の形態による２つの信号間の距離の関数としての上下界(bounds)を有する埋め込みマップの図である。
【図３】この発明の実施の形態による信号距離の関数としてのハミング距離の埋め込み挙動のグラフである。
【図４】この発明の実施の形態によるスター型接続されたパーティのための近似のセキュアな最近傍クラスタリングの概略図である。
【図５】この発明の実施の形態による、盗聴者の存在下におけるサーバーによるユーザー認証の概略図である。
【図６】この発明の実施の形態による、局所性鋭敏型ハッシュを用いたクエリの最近傍の近似の概略図である。
【発明を実施するための形態】
【００２２】
普遍的なスカラー量子化
図１Ａに概略的に示すように、普遍的なスカラー量子化１００は、図１Ｂ又は図１Ｃに示される、互いに素な量子化領域を有する量子化器を用いる。Ｋ次元信号
【００２３】
【数１】
【００２４】
について、図１Ａに示すように
【００２５】
【数２】
【００２６】
によって表される量子化プロセス
【００２７】
【数３】
【００２８】
を用いる。ここで、＜ｘ，ａ＞はベクトル内積であり、Ａｘは行列ベクトル乗算であり、ｍ＝１，…，Ｍは測定インデックスであり、ｙｍは量子化されていない(実数の)測定値であり、ａｍは行列Ａの行である測定ベクトルであり、ｗｍは加法的ディザーであり、Δｍは感度パラメーターであり、関数Ｑ(・)は量子化器であり、ここで
【００２９】
【数４】
【００３０】
が対応する行列表現である。ここで、ΔはエントリーΔｍを有する対角行列であり、量子化器Ｑ(・)はスカラー関数であり、すなわち、入力データ又は入力信号に対し要素単位で動作する。
【００３１】
量子化、及び本明細書に記載の方法のいかなる他のステップも、当該技術分野において既知のメモリ及び入力／出力インターフェースに接続されたプロセッサにおいて実行することができることに留意されたい。さらに、プロセッサはクライアント又はサーバーとすることができる。
【００３２】
行列Ａはランダムであり、独立同一分布を有する(ｉ．ｉ．ｄ．)、ゼロ平均の、正規分布したエントリーが分散σ２を有する。このため、行列Ａ内のエントリーはガウス分布を有すると言うことができる。感度パラメーターΔｍ＝Δは全ての測定値について”同一かつ所定”であり、ｗは区間［０，Δ］で一様分布している。
【００３３】
以下において、パラメーターＡ、ｗ、及びΔは埋め込みパラメーターとして知られている。
【００３４】
関連出願における感度パラメーターは、ｍが増加するとともに減少することに留意されたい。これは階層表現に有用であるが、セキュリティを一切提供しない。今回は、パラメーターΔは全てのｍについて一定のままであり、これによって、以下でより詳細に説明するようにセキュリティが提供される。
【００３５】
図１Ｂに示すように、この発明では量子化関数Ｑ(・)１１０を用いる。この発明の実施の形態によれば、この非単調量子化関数Ｑ(・)は、普遍的なレート効率のよいスカラー量子化を可能にし、情報理論的セキュリティを提供する。この関数において、バイナリ量子化レベルの場合、関数の区間幅は１である。例えば図１Ｂに示すように、実数−３．２、１．５、及び２．５はそれぞれ１、０、及び１に量子化される。
【００３６】
図１Ｃは、関数Ｑの代替的な実施の形態１２０を示している。ここで、区間幅は感度Δ１２１に等しく、これは本質的に区分をΔで置き換える。通常、関数Ｑは不連続量子化領域を有する量子化器を表す。
【００３７】
図１Ｄは、関数Ｑの代替的な実施の形態１３０を示している。ここで、区間は複数の(マルチビット)量子化レベルに対応する。例えば、各量子化レベルの値はハッシュにおいて、１ビットではなく２ビットｂ０、ｂ１として符号化される。
【００３８】
補題Ｉ
類似度測定用途の場合、入力は、差又は二乗距離ｄ＝||ｘ−ｘ’||２を有する２つの(第１及び第２の)信号ｘ及びｘ’、並びに図１に示すような量子化された測定関数１００である。
【００３９】
【数５】
【００４０】
ここで、
【００４１】
【数６】
【００４２】
であり、
【００４３】
【数７】
【００４４】
は平均０、分散σ２を有する正規分布から選択されたｉ．ｉ．ｄ．要素を含み、ｗは区間［０，Δ］において一様分布する。
【００４５】
図２に示すように、２つの信号の単一の測定が、一致した、すなわち等しい量子化された測定値を生成する確率２０２は、
【００４６】
【数８】
【００４７】
であり、ここで、確率は行列Ａ及びｗの分布にわたって取得される。「一致した」という用語は、双方の信号が同一のハッシュ値を生成する、すなわち、ｘのハッシュ値が１の場合、ｘ’のハッシュ値も１であるか、双方について０及び０であることを意味する。図２において、確率は概して１−Ｐの形式で表される。
【００４８】
さらに、上記の確率は以下を用いて有界にすることができる。
【００４９】
【数９】
【００５０】
ここで、Ｐｃ|ｄは、本明細書においてＰ(ｘ，ｘ’一致|ｄ)を意味する。式(４)〜式(６)は、図２の２０４〜２０６に対応する。特定の信号の場合、各量子化ビットは、例えば図１Ｂに示すように同じ確率０．５で値０又は１をとる。
【００５１】
セキュアなバイナリ埋め込み
この発明による量子化プロセスは、局所性鋭敏型ハッシュ(ＬＳＨ)に類似した特性を有する。したがって、ｑ、すなわちｘの量子化された測定値を、ｘのハッシュと呼ぶ。したがって、この説明において、ハッシュ及び量子化という用語は交換可能に用いられる。
【００５２】
この発明者らの目的は２つある。第１に、情報理論的議論を用いて、ｌ２距離ｄ＝||ｘ−ｘ’||２が所定のしきい値未満である場合にのみ、量子化プロセスが２つの信号ｘ及びｘ’間の距離に関する情報を提供することを実証する。さらに、プロセスは、ｌ２距離がしきい値よりも大きいとき、信号のセキュリティを保護する。第２に、測定値のハッシュが、正規化されたハミング距離の下でｌ２距離の安定した埋め込みを提供することを実証することによって、この測定値のハッシュによって提供される情報を量子化する。すなわち、２つの信号間のｌ２距離が、その２つの信号のハッシュ間の正規化されたハミング距離を制限することを示す。１つの要件は、測定行列Ａ及びディザーｗが、ハッシュの受信者から秘密のままであることである。そうでない場合、受信者は元の信号を再構成することができる。しかしながら、そのような測定値からの再構成は、測定パラメーターＡ及びｗが知られている場合であっても、組み合わせ的複雑度を有し、おそらく計算量が非常に多い。
【００５３】
情報理論的セキュリティ
この埋め込みのセキュリティ特性を理解するために、距離ｄを条件として、２つの信号ｘ及びｘ’のｉ番目のビットｑｉ及びｑ’ｉ間の相互情報を検討する。
【００５４】
【数１０】
【００５５】
ここで、最後のステップはｌｏｇ ｘ≦ｘ−１を用いて式を統合する。
【００５６】
このため、２つの信号の２つの長さＭのハッシュｑ、ｑ’間の相互情報は、以下の定理によって制限される。
【００５７】
定理Ｉ
２つの信号ｘ及びｘ’、並びに補題Ｉの量子化方法がＭ回適用され、それぞれ量子化されたベクトル(ハッシュ)ｑ及びｑ’が生成されたと考える。２つの信号の２つの長さＭのハッシュｑ及びｑ’間の相互情報は以下によって有界である。
【００５８】
【数１１】
【００５９】
定理Ｉによれば、ハッシュ対間の相互情報は、そのハッシュを生成した信号間の距離とともに指数関数的に減少する。指数関数的減少率は、感度パラメーターΔによって制御される。このため、かけ離れた(Δによって制御されるようなしきい値よりも大きい)信号に関するいかなる情報も、それらの信号のハッシュを観測することのみによって復元することはできない。
【００６０】
安定した埋め込み
この安定した埋め込みは、信号空間内の信号の距離と、測定値の距離、すなわちハッシュとの間の高次元関係からのジョンソンーリンデンシュトラウス埋め込みに趣旨が類似している。ハッシュはバイナリ空間｛０，１｝Ｍ内にあるので、適切な距離メトリックは正規化されたハミング距離
【００６１】
【数１２】
【００６２】
である。
【００６３】
上述したようにｌ２距離ｄ＝||ｘ−ｘ’||２を有するベクトルｘ及びｘ’の量子化を考える。個々の量子化ビットの各対間の距離
【００６４】
【数１３】
【００６５】
は、分布
【００６６】
【数１４】
【００６７】
を有するランダムバイナリ値である。
【００６８】
この分布及び上下界は図２にプロットされている。例えば図１Ｄにおけるようなマルチビット量子化器の場合、ハミング距離は埋め込み空間内の別の適切な距離によって置き換えることができる。例えば、ハミング距離は埋め込み空間内のｌ１距離又はｌ２距離によって置き換えることができる。
【００６９】
ランダム変数の和がその予測値から逸れる確率に対する上界を与えるヘフディングの不等式を用いると、ハミング距離が
【００７０】
【数１５】
【００７１】
を満たすことを示すのは簡単である。
【００７２】
次に、セキュアに埋め込むことを望むＬ個のデータ点の「クラウド」を考える。それぞれが式(８)を満たす、このクラウド内の最大でＬ２個の可能な信号対に対する和集合上界(union bound)を用いると、以下が成り立つ。
【００７３】
定理ＩＩ
【００７４】
【数１６】
【００７５】
内のＬ個の信号の集合Ｓ及び補題Ｉの量子化方法を考える。確率
【００７６】
【数１７】
【００７７】
で、全ての対ｘ，ｘ’∈Ｓ及びそれらの対応するハッシュｑ、ｑ’について以下が成り立つ。
【００７８】
【数１８】
【００７９】
ここで、Ｐｃ|ｄは補題Ｉにおいて定義され、ｄはｌ２距離であり、ｄＨ(・，・)はそれらのハッシュ間の正規化されたハミング距離である。
【００８０】
定理ＩＩは、圧倒的な確率で、２つのハッシュ間の正規化されたハミング距離が、ｔによって制御されて、１−Ｐｃ|ｄによって定義されるｌ２距離のマッピングに非常に近いことを述べている。さらに、式(４)〜式(６)内の上下界を用いて、式(９)の閉形式の埋め込み境界を得ることができる。
【００８１】
【数１９】
【００８２】
図２は、マッピング１−Ｐｃ|ｄを、その上下界とともに示す。マッピング２０１は、小さなｄの場合に線形であり、大きなｄの場合に実質的に平坦となり(２０２)、したがって可逆でなく、スケーリングを用いて感度パラメーターΔによって制御される。さらに、図２において、上界２０１
【００８３】
【数２０】
【００８４】
が、それぞれ小さいｄ及び大きいｄについて非常に厳密であり、マッピングの近似として用いることができることが明らかである。当然ながら、定理ＩＩの結果及びマッピングに対する制限は、ハミング距離の関数としてｌ２距離に対する保証を提供するように反転することができる。
【００８５】
図３は、実際に埋め込みがどのように挙動するかを示している。図３の(Ａ)，(Ｂ)は、ハッシュの対間の正規化されたハミング距離に対する結果を、それらの距離を生成した信号間の距離の関数として示している。図面は、この発明によるセキュアなハッシングの重要な特性を示している。しきい値Ｔ３０１よりも大きな全ての距離について、正規化された距離応答は平坦であり、正規化されたハミング距離は全てのｌ２距離について同一であるので、実際の距離については何も習得することができない。しかしながら、しきい値よりも小さな距離の場合、正規化されたハミング距離は実際の距離にほぼ比例する。
【００８６】
示された例では、信号は
【００８７】
【数２１】
【００８８】
、すなわちＫ＝２１０においてランダムに生成される。図３の(Ａ)のプロットは、ハッシュあたりＭ＝２１２＝４０９６個の測定値、すなわち係数あたり４ビットを用いる。図３の(Ｂ)のプロットは、ハッシュあたりＭ＝２８＝２５６個の測定値、すなわち係数あたり１／４ビットを用いる。各プロットにおいて２つの異なるΔ、すなわちΔ＝２−３、２−１が用いられる。Δが大きくなると、埋め込みの線形部分の傾斜が増大し、より大きな範囲のｌ２距離を識別することができる。より大きな距離の信号について情報が明らかになるので、これによってセキュリティが低下する。さらに、ハッシュビット数Ｍが小さくなると、線形領域の幅３０１が増大し、これによって線形領域においてマップを反転させる際の不確実性が増大する。他方で、ハッシュビット数Ｍが増大すると、埋め込みは、帯域幅要件が大きくなることと引き換えに、より厳密になる。これは、近傍間のｌ２距離をハッシュからより正確に推定することができることを意味する。信号が量子化されている場合であっても、信号の距離間の正確なマッピングにおける同様の不確実性が存在し、次に、例えば準同形暗号化システムを用いて、暗号化領域内で比較されることに留意されたい。
【００８９】
この挙動は、埋め込みの、上述した情報理論的セキュリティと一致する。小さな距離ｄの場合、ハッシュ内に提供される情報が存在し、この情報を用いて信号間の距離を求めることができる。より大きな距離ｄの場合、情報は明らかにされない。したがって、２つの信号のハッシュからそれらの２つの信号間の距離も、いかなる他の情報も求めることが可能でない。
【００９０】
応用形態
ハッシュに基づく最近傍探索が特に有利である様々な応用形態を説明する。全てのパーティが準正直である、すなわちパーティはプロトコルの規則に従うが、プロトコルの各ステップにおいて利用可能な情報を用いて他のパーティが保有するデータの発見を試みる可能性があると仮定する。
【００９１】
以下に説明するプロトコルの全てにおいて、埋め込みパラメーターＡ、ｗ、及びΔが、図２の線形比例領域が少なくとも最大でＤのｌ２距離まで拡張するように選択されると仮定する。ＤＨによって表されるこの比例領域内では、ハッシュ間の正規化されたハミング距離は、基礎を成す信号間のＤのｌ２距離に対応する。線形比例領域の外側では、埋め込みは平坦な応答を有し、不可逆であり、したがってセキュアであることを想起されたい。換言すれば、２つの信号間の距離が線形比例領域の外側にある場合、信号のハッシュを観察することによってその信号に関するいかなる情報も得ることができない。
【００９２】
スタートポロジーを用いたプライバシー保護クラスタリング
図４に示すようなこの応用形態では、埋め込み行列Ａ及びディザーベクトルｗが知られていないとき、対応するハッシュを観察することによってベクトルｘに関する情報が明らかにされない特性を利用する。この応用形態では、複数のクライアントパーティＰ(ｉ)がサーバーＳによって解析されるデータｘ(ｉ)を提供する。目標は、Ｓがデータを明らかにすることなくデータをクラスタリングし、クライアントＰをクラスに編成することを可能にすることである。クライアントごとに、サーバーはＤのｌ２距離内のクライアントの近似最近傍を得る。
【００９３】
プロトコル：プロトコルは図４に要約されている。
１)全てのパーティが、ランダム埋め込み行列Ａと、ディザーベクトルｗと、感度パラメーターΔとを等しく得る。これを達成する１つの方法は、１つのクライアントパーティが受信者の公開暗号化鍵を用いて他のクライアントパーティにＡ、ｗ、及びΔを送信することである。
２)ｉ∈Ｉ＝｛１，２，…，Ｎ｝について、各クライアントがｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求め、ｑ(ｉ)を平文としてサーバーＳに送信する。
３)各パーティＰ(ｉ)に応じて、サーバーは集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成する。
【００９４】
式(９)から、Ｃｉの要素がパーティＰ(ｉ)の近似最近傍であることがわかる。埋め込みの特性により、サーバーは基礎を成すデータｘ(ｉ)を発見することなく、平文形式でバイナリハッシュを用いてクラスタリングを実行することができる。このため、パラメーターＡ、ｗ、及びΔをＮ個のパーティに通信するために被る最初の一時的な前処理オーバーヘッドは別として、このプロトコルにおいて、いかなる後続の処理にも暗号化は必要とされない。
【００９５】
これは、元のデータｘ(ｉ)に基づいて距離計算を実行することが必要なプロトコルと対照的である。このプロトコルは、サーバーが追加のサブプロトコルに携わり、準同形暗号化を用いて暗号化領域内でＯ(Ｎ２)個の対ごとの距離を求めることを必要とする。
【００９６】
対称鍵を用いた認証
図５に示すようなこの応用形態では、例えば生体パラメーター又は画像から導出されたベクトルｘを用いて認証する。目標は、データｘを可能性のある盗聴者に明らかにすることなく、信頼されたサーバーを用いてユーザーｘを認証することである。目標が認証である場合、クライアントユーザーはアイデンティティーを主張し、サーバーは、サブミットされた認証ハッシュベクトルｑがサーバーにおけるデータベース内に格納された登録ハッシュベクトルｑ(Ｎ)ベクトルから所定のｌ２距離内にあるか否かを判断する。目標が識別である場合、サーバーは、サブミットされたベクトルが、そのサーバーのデータベース内に格納された少なくとも１つの登録ベクトルから所定のｌ２距離以内にあるか否かを判断する。量子化されたランダム埋め込みの部分空間内で認証を実行する。ここで、埋め込みパラメーター(Ａ，ｗ，Δ)は、クライアント及び信頼された認証サーバーにのみ知られているが盗聴者には知られていない対称鍵としての役割を果たす。ユーザー識別シナリオのためのプロトコルを以下で説明する。認証プロトコルは同様に進む。
【００９７】
クライアントのユーザーは、識別に用いられるベクトルｘを有する。サーバーはＮ個の登録ベクトルｘ(ｉ)(ｉ∈Ｉ＝｛１，２，…，Ｎ｝)のデータベースを有する。ユーザー及びサーバー(盗聴者ではない)は埋め込みパラメーター(Ａ，ｗ，Δ)を有する。
【００９８】
サーバーは、Ｄのｌ２距離内のベクトルｘの近似最近傍の集合Ｃを求める。
【００９９】
【数２２】
【０１００】
である、すなわち空である場合、ユーザー識別は失敗し、そうでない場合、ユーザーは、データベース内の少なくとも１人の正当な登録ユーザーに近いと識別される。盗聴者はｘに関する情報を得ない。
【０１０１】
プロトコル：プロトコル送信は図５に要約されている。
１)ユーザー５０１はｑ＝Ｑ(Δ−１(Ａｘ＋ｗ))を求め、ｑを平文としてサーバーに送信する。
２)サーバー５０３は全てのｉについてｑ(ｉ)＝Ｑ(Δ―１(Ａｘ(ｉ)＋ｗ))を求める。
３)サーバーは集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成する。
【０１０２】
ここでも、式(９)から、集合Ｃがｘの近似最近傍を含むことがわかる。
【０１０３】
【数２３】
【０１０４】
である場合、識別は失敗し、そうでない場合、ユーザーはＣ内のインデックスのうちの１つを有するものとして識別されている。盗聴者５０２は(Ａ，ｗ，Δ)５０４を知らないので、量子化された埋め込みは基礎を成すベクトルに関する情報を明らかにしない。このプロトコルは、ハッシュを認証サーバーに送信する前にユーザーがハッシュを暗号化することを必要としない。通信オーバーヘッドの観点から、これは従来の最近傍探索を上回る利点である。従来の最近傍探索は、ベクトルを盗聴者から隠すために、クライアントがそのベクトルを暗号化形式でサーバーに送信することを必要とする。
【０１０５】
一変形形態として、信頼されていないサーバーのプロトコルを設計するために、サーバーはｘ(ｉ)ではなくｑ(ｉ)のみを格納し、埋め込みパラメーター(Ａ，ｗ，Δ)を保有しないことを規定することができる。認証サーバーが信用されていない場合、クライアントユーザーは、自身の識別ベクトルｘ(ｉ)を用いて登録することを望まない。この場合、(サーバーではなく)ユーザーのみが(Ａ，ｗ，Δ)を保有するように上記のプロトコルを変更する。
【０１０６】
ユーザーは、対応するデータベクトルｘ(ｉ)の代わりにハッシュｑ(ｉ)を用いてサーバーのデータベースに登録する。ハッシュはサーバー上に格納される唯一のデータである。この場合、サーバーは、(Ａ’，ｗ，Δ)を知らないので、ｑ(ｉ)からｘ(ｉ)を再構成することができない。さらに、データベースが危険にさらされている場合、ｑ(ｉ)を無効にすることができ、異なる埋め込みパラメーター(Ａ’，ｗ’，Δ’)を用いて新たなハッシュを登録することができる。
【０１０７】
２つのパーティを用いたプライバシー保護クラスタリング
次に図６に示すように、クライアント６０１がデータベースサーバー６０２に対しクエリを開始する２パーティプロトコルを考える。プライバシー制約は、クエリがサーバーに明らかにされないこと、及びクライアントが、そのクライアントのクエリから所定のｌ２距離内にあるデータベースサーバー内のベクトルのみを知ることができることである。スタートポロジーのための前のプロトコルと異なり、ここでは、暗号化領域内で単純な操作を実行するのに、公開鍵暗号化のための確率非対称パイエ(Paillier)暗号化システム等の準同形暗号化システム方式を用いることが必要である。
【０１０８】
パイエ暗号化システムの加法的準同形特性により、ξｐ(ａ)ξｑ(ｂ)＝ξｐｑ(ａ＋ｂ)であることが確実にされ、ここでａ及びｂはメッセージ空間内の整数であり、ξ(・)は暗号化関数である。整数ｐ及びｑはランダムに選択された暗号化パラメーターであり、これによってパイエ暗号化システムが意味論的にセキュアになる。すなわち、パラメーターｐ、ｑをランダムに選択することによって、所与の平文の繰り返された暗号化の結果として異なる暗号文が生成され、それによって選択平文攻撃(ＣＰＡ)に対して保護されることを確実にすることができる。簡単にするために、この発明者らの表記から添え字ｐ、ｑを省略する。加法的準同形特性の当然の帰結として、ξ(ａ)ｂ＝ξ(ａｂ)である。
【０１０９】
クライアントはクエリベクトルｘを有する。サーバーは、Ｉ＝１，…，ＮについてＮ個のベクトルｘ(ｉ)のデータベースを有する。サーバーは(Ａ，ｗ，Δ)を生成し、Δを公開する。クライアントは
【０１１０】
【数２４】
【０１１１】
、すなわちＤのｌ２距離内のクエリベクトルｘの近似最近傍の集合を得る。そのようなベクトルが存在しない場合、クライアントは
【０１１２】
【数２５】
【０１１３】
を得る。
【０１１４】
プロトコル：プロトコル送信は図６に要約されている。
１)クライアントは、パイエ暗号化の公開暗号化鍵ｐｋ及び秘密復号化鍵ｓｋを生成する。次に、クライアントは、ξ(ｘ)＝(ξ(ｘ１)，ξ(ｘ２)，…，ξ(ｘＫ))によって表される、ｘの要素ごとの暗号化を実行する。クライアントはξ(ｘ)をサーバーに送信する。
２)サーバーは加法的準同形特性を用いてξ(ｙ)＝ξ(Ａｘ＋ｗ)を求め、ξ(ｙ)をクライアントに返す。
３)クライアントはｙを復号化し、ｑ＝Δ−１ｙを求め、ξ(ｑ)をサーバーに送信する。
４)サーバーは、ハッシュｑ(ｉ)＝Ｑ(Δ―１(Ａｘ(ｉ)＋ｗ))を求める。
５)サーバーは、準同形特性を用いて、量子化されたクエリベクトルと、量子化されたデータベースベクトルとの間のハミング距離の暗号化を求め、すなわちｄＨ(ｑ，ｑ(ｉ))：
【０１１５】
【数２６】
【０１１６】
を求め、暗号化された距離をクライアントに送信する。
６)クライアントはｄＨ(ｑ，ｑ(ｉ))を復号化し、集合Ｄ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))＜ＤＨ｝を得る。
７)Ｄ＝０の場合、プロトコルは終了する。そうでない場合、クライアントはＮ個のうち|Ｄ|個の紛失通信(ＯＴ)プロトコルをサーバーとともに実行し、Ｃ＝｛ｘ(ｉ)｝を取り出す。ＯＴは、クライアントが
【０１１７】
【数２７】
【０１１８】
となるようなベクトルｘ(ｉ)のうちのいずれも発見しないことを保証する一方で、クエリ集合Ｄがサーバーに明らかにされないことを確実にする。
【０１１９】
式(９)から、集合Ｃはクエリベクトルｘの近似最近傍を含む。基礎を成すベクトル間の距離を暗号化領域で求めることに対する、ハッシュ部分空間において距離を求めることの利点を考える。サイズＮのデータベース場合、ベクトル間の距離を求めることによって、全てのＮ個の距離||ｘ−ｘ(ｉ)||２が明らかとなる。最近傍に対応する距離、すなわち距離の局所分布のみがクライアントに明らかにされることを確実にするには別個のサブプロトコルが必要である。
【０１２０】
対照的に、この発明によるプロトコルは、||ｘ−ｘ(ｉ)||２≦Ｄの場合にのみ距離を明らかにする。||ｘ−ｘ(ｉ)||２＞Ｄの場合、量子化されたランダム埋め込みを用いて求められたハミング距離はもはや真の距離に比例しない。これは、クライアントがサーバーのデータベース内のベクトルの大域分布を知ることを防ぐ一方、クエリベクトル付近のベクトルの局所分布のみを明らかにする。
【０１２１】
発明の効果
量子化されたランダム埋め込みを用いたセキュアなバイナリ法を説明している。このバイナリ法は、信号ベクトルとデータベクトルとの間の距離を特殊な形で保持する。１つのベクトルが別のベクトルからあらかじめ指定された距離ｄ内にある限り、それらのベクトルの２つの量子化された埋め込み間の正規化されたハミング距離は２つのベクトル間のｌ２距離にほぼ比例する。しかしながら、２つのベクトル間の距離がｄを超えて増大すると、それらのベクトルの埋め込み間のハミング距離は、ベクトル間の距離と無関係になる。
【０１２２】
埋め込みは、幾つかの有用なプライバシー特性を更に示す。任意の２つのハッシュ間の相互情報は、それらのハッシュの基礎を成す信号間の距離とともに指数関数的にゼロまで減少する。
【０１２３】
この埋め込み手法を用いて、効率的なプライバシーを保護した最近傍探索を実行する。ほとんどの以前のプライバシーを保護した最近傍探索法は、プライバシー制約を満たすには暗号化しなくてはならない元のベクトルを用いて実行される。
【０１２４】
上記の特性に起因して、元のベクトルの代わりにこの発明によるハッシュを用いて、大幅に低い複雑度で又は高速に、暗号化されていない領域内でプライバシー保護された最近傍探索を実施することができる。これを動機付けするために、低複雑度のクラスタリング及びサーバーベースの認証においてプロトコルを説明している。
【０１２５】
好ましい実施の形態の例としてこの発明を説明してきたが、この発明の趣旨及び範囲内において、他の様々な適合及び変更を行えることが理解されるべきである。
【技術分野】
【０００１】
この発明は、包括的には、基礎を成す信号のプライバシーを保護するように信号をハッシュすることに関し、より詳細には、ハッシュされた信号をセキュアに比較することに関する。
【背景技術】
【０００２】
多くの信号処理、機械学習、及びデータマイニングの用途は、信号を比較して、それらの信号がどの程度類似しているかを何らかの類似度メトリック又は距離メトリックに従って求めることを必要とする。これらの用途の多くにおいて、比較は、信号のクラスター内の信号のうちのいずれがクエリ信号に最も類似しているかを求めるのに用いられる。
【０００３】
距離尺度を用いる複数の最近傍探索(ＮＮＳ)法が既知である。近接度探索又は類似度探索としても知られるＮＮＳは、メトリック空間内の最も近い傍データを求める。メトリック空間Ｍ内のデータの集合Ｓ(クラスター)及びクエリｑ∈Ｍについて、探索は、集合Ｓ内でクエリｑに最も近いデータｓを求める。
【０００４】
幾つかの用途では、探索はセキュアマルチパーティ計算(ＳＭＣ)を用いて実行される。ＳＭＣは複数のパーティを可能にし、例えばサーバーが１つ又は複数のクライアントからの入力信号の関数を計算してクライアント(複数の場合もあり)への出力信号を生成する一方、入力及び出力は、クライアントにおいてのみ非公開で知られている。加えて、サーバーによって用いられるプロセス及びデータは、サーバーにおいて非公開のままである。このため、ＳＭＣは、クライアントもサーバーも互いの非公開データ及び非公開プロセスから何も知ることができないという意味でセキュアである。このため、以下において、セキュアとは、マルチパーティ計算に用いられるデータの所有者しか、そのデータ及びそのデータに適用されるプロセスが何であるかを知らないことを意味する。
【０００５】
これらの用途では、信号を、サーバーにおける管理可能な計算複雑度、及びクライアントとサーバーとの間の低い通信オーバーヘッドと比較することが必要である。ＮＮＳの難度は、プライバシー制約が存在するとき、すなわちパーティのうちの１つ又は複数が、探索に関連した信号、データ、又は方法を他のパーティと共有することを望まないときに増大する。
【０００６】
ソーシャルネットワーキング、ユーザーデータのインターネットベースのストレージ、及びクラウドコンピューティングの出現により、プライバシー保護計算は重要度を増している。プライバシー制約を満たすために、例えば類似度を求めることを依然として可能にしながら、１つ又は複数のパーティのデータは通常、加法的準同形暗号化システムを用いて暗号化される。
【０００７】
１つの方法は、クライアントのクエリをサーバーに明らかにすることなくＮＮＳを実行し、サーバーは、ｋ最近傍集合内のデータ以外、そのサーバーのデータベースを明らかにしない。距離決定は暗号化領域内で実行される。したがって、本方法の計算複雑度はデータ項目数の二次式となり、入力の暗号化及び出力の復号化が必要とされるので、この計算複雑度は甚大である。剪定技法を用いて距離決定の回数を低減し、計算及び通信の線形複雑度を得ることができるが、暗号化データの処理及び送信に起因して、プロトコルオーバヘッドは依然として極めて大きい。
【０００８】
したがって、プロセスに関与する全てのパーティのプライバシーを依然として確保しながら、ハッシュ計算を実行する複雑度を低減することが望ましい。
【０００９】
この発明は、２０１０年８月２４日にBoufounosによって出願された「Method for Hierarchical Signal Quantization and Hashing」と題する米国特許出願第１２／８６１，９２３号に関連する。
【００１０】
関連出願第１２／８６１，９２３号は、階層的信号量子化及び局所性鋭敏型ハッシュのために非単調量子化器を用いる方法を記載している。階層的操作を可能にするために、比較的大きな値の感度パラメーターΔが、より広範囲の入力信号に対する精度の粗い操作を可能にする一方、比較的小さな値のパラメーターが、類似した入力信号に対し精度の細かい操作を可能にする。したがって、反復ごとに感度パラメーターは減少する。
【００１１】
上記関連出願において記載されているように、選択する最も重要なパラメーターは感度パラメーターである。このパラメーターは、ハッシュがどのように信号を互いに区別するかを制御する。信号対間の距離尺度が検討される場合(距離が小さいほど、信号はより類似する)、Δによって、ハッシュが距離変化に対しどの程度感度が高いかが決まる。特に、Δが小さい場合、ハッシュは信号が非常に類似しているときの類似度変化に対し感度が高いが、類似していない信号の類似度変化に対し感度が高くない。Δが大きくなるとともに、ハッシュはそれほど類似していない信号に対し、より感度が高くなるが、類似している信号の感度のうちの幾らかが失われる。この特性は、信号の階層的ハッシュを構成するのに用いられる。ここで、第１の幾つかのハッシュ係数は、より大きな値をΔに用いて構成され、Δの値は後続の値について減少される。特に、大きなΔを用いて第１の幾つかのハッシュ値を計算することによって、計算的に単純な粗い信号再構成又は粗い距離推定が可能になり、これによって、離れた信号であってもその信号の情報が提供される。次に、より小さなΔを用いて得られた後続のハッシュ値を用いて、信号再構成を精緻化するか、又はより類似した信号の距離情報を精緻化することができる。
【００１２】
この方法は、階層的信号量子化に有用である。しかしながら、この方法はプライバシーを保護しない。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
この発明は、信号比較のためにバイナリ埋め込みを用いた、プライバシー保護ハッシング方法を提供する。
【課題を解決するための手段】
【００１４】
この発明の実施の形態は、信号比較のためにバイナリ埋め込みを用いた、プライバシー保護ハッシング方法を提供する。１つの応用形態では、セキュアな領域内で、１つ又は複数のハッシュされた信号が比較され、それらの信号の類似度が求められる。本方法を適用して、最近傍探索(ＮＮＳ)及びクラスタリングを近似することができる。本方法は、量子化されたランダム埋め込みを用いて求められた埋め込みに基づく局所性鋭敏型バイナリハッシュ方式に部分的に基づく。
【００１５】
信号から抽出されたハッシュは、２つの信号間の距離が或る所定のしきい値未満であるならば、その距離(類似度)に関する情報を提供する。信号間の距離がしきい値よりも大きい場合、距離に関する情報は明らかにされない。さらに、ランダム化された埋め込みパラメーターが知られていない場合、任意の２つの信号のハッシュ間の相互情報は、信号間のｌ２距離(ユークリッドノルム)とともに指数関数的にゼロまで減少する。バイナリハッシュを用いて、暗号化された信号を直接用いる従来の方法と比較して大幅に低い複雑度で、プライバシーを保護したＮＮＳを実行することができる。
【００１６】
本方法は、量子化されたランダム射影を用いたセキュアな安定した埋め込みに基づく。局所性鋭敏型の特性が達成され、ここで、ハッシュ間のハミング距離は、基礎を成すデータ間のｌ２距離が所定のしきい値未満である限り、この距離に比例する。
【００１７】
基礎を成す信号又はデータが類似していない場合、ハッシュは、埋め込みパラメーターが明らかにされていないならば、データ間の真の距離に関する情報を提供しない。
【００１８】
プライバシーを保護したＮＮＳの埋め込み方式は、クラスタリング及び認証の用途のためのプロトコルを提供する。これらのプロトコルの顕著な特徴は、距離決定を、基礎を成す信号又はデータを明らかにすることなく、平文においてハッシュに対して実行することができることである。平文は暗号化されずに(unencrypted)、すなわち平文で(in the clear)格納又は送信される。このため、暗号化領域の距離決定の観点からの計算オーバーヘッドは、暗号化を用いる従来技術よりも大幅に低い。さらに、暗号化が必要な場合であっても、固有の最近傍特性により、特定の数の最近傍を選択する最終ステップにおいて必要とされる複雑な選択プロトコルが不要になる。
【００１９】
本方法は、部分的に、レート効率のよい普遍的なスカラー量子化に基づく。このスカラー量子化は、量子化のための安定したバイナリ埋め込み、及び最近傍決定のための局所性鋭敏型ハッシュ(ＬＳＨ)法と密接な関係を有する。ＬＳＨは、潜在的に大きな信号の非常に短いハッシュを用いて、それらの信号の近似距離を効率的に求める。
【００２０】
本方法と従来技術との間の主要な差異は、この発明による方法が、この発明による埋め込みの情報理論的セキュリティを保証することである。
【図面の簡単な説明】
【００２１】
【図１Ａ】この発明の実施の形態による普遍的なスカラー量子化の概略図である。
【図１Ｂ】この発明の実施の形態による単位区間を用いた非単調量子化関数の図である。
【図１Ｃ】この発明の実施の形態による感度区間を用いた代替的な非単調量子化関数の図である。
【図１Ｄ】この発明の実施の形態による複数レベルの区間を用いた代替的な非単調量子化関数の図である。
【図２】この発明の実施の形態による２つの信号間の距離の関数としての上下界(bounds)を有する埋め込みマップの図である。
【図３】この発明の実施の形態による信号距離の関数としてのハミング距離の埋め込み挙動のグラフである。
【図４】この発明の実施の形態によるスター型接続されたパーティのための近似のセキュアな最近傍クラスタリングの概略図である。
【図５】この発明の実施の形態による、盗聴者の存在下におけるサーバーによるユーザー認証の概略図である。
【図６】この発明の実施の形態による、局所性鋭敏型ハッシュを用いたクエリの最近傍の近似の概略図である。
【発明を実施するための形態】
【００２２】
普遍的なスカラー量子化
図１Ａに概略的に示すように、普遍的なスカラー量子化１００は、図１Ｂ又は図１Ｃに示される、互いに素な量子化領域を有する量子化器を用いる。Ｋ次元信号
【００２３】
【数１】
【００２４】
について、図１Ａに示すように
【００２５】
【数２】
【００２６】
によって表される量子化プロセス
【００２７】
【数３】
【００２８】
を用いる。ここで、＜ｘ，ａ＞はベクトル内積であり、Ａｘは行列ベクトル乗算であり、ｍ＝１，…，Ｍは測定インデックスであり、ｙｍは量子化されていない(実数の)測定値であり、ａｍは行列Ａの行である測定ベクトルであり、ｗｍは加法的ディザーであり、Δｍは感度パラメーターであり、関数Ｑ(・)は量子化器であり、ここで
【００２９】
【数４】
【００３０】
が対応する行列表現である。ここで、ΔはエントリーΔｍを有する対角行列であり、量子化器Ｑ(・)はスカラー関数であり、すなわち、入力データ又は入力信号に対し要素単位で動作する。
【００３１】
量子化、及び本明細書に記載の方法のいかなる他のステップも、当該技術分野において既知のメモリ及び入力／出力インターフェースに接続されたプロセッサにおいて実行することができることに留意されたい。さらに、プロセッサはクライアント又はサーバーとすることができる。
【００３２】
行列Ａはランダムであり、独立同一分布を有する(ｉ．ｉ．ｄ．)、ゼロ平均の、正規分布したエントリーが分散σ２を有する。このため、行列Ａ内のエントリーはガウス分布を有すると言うことができる。感度パラメーターΔｍ＝Δは全ての測定値について”同一かつ所定”であり、ｗは区間［０，Δ］で一様分布している。
【００３３】
以下において、パラメーターＡ、ｗ、及びΔは埋め込みパラメーターとして知られている。
【００３４】
関連出願における感度パラメーターは、ｍが増加するとともに減少することに留意されたい。これは階層表現に有用であるが、セキュリティを一切提供しない。今回は、パラメーターΔは全てのｍについて一定のままであり、これによって、以下でより詳細に説明するようにセキュリティが提供される。
【００３５】
図１Ｂに示すように、この発明では量子化関数Ｑ(・)１１０を用いる。この発明の実施の形態によれば、この非単調量子化関数Ｑ(・)は、普遍的なレート効率のよいスカラー量子化を可能にし、情報理論的セキュリティを提供する。この関数において、バイナリ量子化レベルの場合、関数の区間幅は１である。例えば図１Ｂに示すように、実数−３．２、１．５、及び２．５はそれぞれ１、０、及び１に量子化される。
【００３６】
図１Ｃは、関数Ｑの代替的な実施の形態１２０を示している。ここで、区間幅は感度Δ１２１に等しく、これは本質的に区分をΔで置き換える。通常、関数Ｑは不連続量子化領域を有する量子化器を表す。
【００３７】
図１Ｄは、関数Ｑの代替的な実施の形態１３０を示している。ここで、区間は複数の(マルチビット)量子化レベルに対応する。例えば、各量子化レベルの値はハッシュにおいて、１ビットではなく２ビットｂ０、ｂ１として符号化される。
【００３８】
補題Ｉ
類似度測定用途の場合、入力は、差又は二乗距離ｄ＝||ｘ−ｘ’||２を有する２つの(第１及び第２の)信号ｘ及びｘ’、並びに図１に示すような量子化された測定関数１００である。
【００３９】
【数５】
【００４０】
ここで、
【００４１】
【数６】
【００４２】
であり、
【００４３】
【数７】
【００４４】
は平均０、分散σ２を有する正規分布から選択されたｉ．ｉ．ｄ．要素を含み、ｗは区間［０，Δ］において一様分布する。
【００４５】
図２に示すように、２つの信号の単一の測定が、一致した、すなわち等しい量子化された測定値を生成する確率２０２は、
【００４６】
【数８】
【００４７】
であり、ここで、確率は行列Ａ及びｗの分布にわたって取得される。「一致した」という用語は、双方の信号が同一のハッシュ値を生成する、すなわち、ｘのハッシュ値が１の場合、ｘ’のハッシュ値も１であるか、双方について０及び０であることを意味する。図２において、確率は概して１−Ｐの形式で表される。
【００４８】
さらに、上記の確率は以下を用いて有界にすることができる。
【００４９】
【数９】
【００５０】
ここで、Ｐｃ|ｄは、本明細書においてＰ(ｘ，ｘ’一致|ｄ)を意味する。式(４)〜式(６)は、図２の２０４〜２０６に対応する。特定の信号の場合、各量子化ビットは、例えば図１Ｂに示すように同じ確率０．５で値０又は１をとる。
【００５１】
セキュアなバイナリ埋め込み
この発明による量子化プロセスは、局所性鋭敏型ハッシュ(ＬＳＨ)に類似した特性を有する。したがって、ｑ、すなわちｘの量子化された測定値を、ｘのハッシュと呼ぶ。したがって、この説明において、ハッシュ及び量子化という用語は交換可能に用いられる。
【００５２】
この発明者らの目的は２つある。第１に、情報理論的議論を用いて、ｌ２距離ｄ＝||ｘ−ｘ’||２が所定のしきい値未満である場合にのみ、量子化プロセスが２つの信号ｘ及びｘ’間の距離に関する情報を提供することを実証する。さらに、プロセスは、ｌ２距離がしきい値よりも大きいとき、信号のセキュリティを保護する。第２に、測定値のハッシュが、正規化されたハミング距離の下でｌ２距離の安定した埋め込みを提供することを実証することによって、この測定値のハッシュによって提供される情報を量子化する。すなわち、２つの信号間のｌ２距離が、その２つの信号のハッシュ間の正規化されたハミング距離を制限することを示す。１つの要件は、測定行列Ａ及びディザーｗが、ハッシュの受信者から秘密のままであることである。そうでない場合、受信者は元の信号を再構成することができる。しかしながら、そのような測定値からの再構成は、測定パラメーターＡ及びｗが知られている場合であっても、組み合わせ的複雑度を有し、おそらく計算量が非常に多い。
【００５３】
情報理論的セキュリティ
この埋め込みのセキュリティ特性を理解するために、距離ｄを条件として、２つの信号ｘ及びｘ’のｉ番目のビットｑｉ及びｑ’ｉ間の相互情報を検討する。
【００５４】
【数１０】
【００５５】
ここで、最後のステップはｌｏｇ ｘ≦ｘ−１を用いて式を統合する。
【００５６】
このため、２つの信号の２つの長さＭのハッシュｑ、ｑ’間の相互情報は、以下の定理によって制限される。
【００５７】
定理Ｉ
２つの信号ｘ及びｘ’、並びに補題Ｉの量子化方法がＭ回適用され、それぞれ量子化されたベクトル(ハッシュ)ｑ及びｑ’が生成されたと考える。２つの信号の２つの長さＭのハッシュｑ及びｑ’間の相互情報は以下によって有界である。
【００５８】
【数１１】
【００５９】
定理Ｉによれば、ハッシュ対間の相互情報は、そのハッシュを生成した信号間の距離とともに指数関数的に減少する。指数関数的減少率は、感度パラメーターΔによって制御される。このため、かけ離れた(Δによって制御されるようなしきい値よりも大きい)信号に関するいかなる情報も、それらの信号のハッシュを観測することのみによって復元することはできない。
【００６０】
安定した埋め込み
この安定した埋め込みは、信号空間内の信号の距離と、測定値の距離、すなわちハッシュとの間の高次元関係からのジョンソンーリンデンシュトラウス埋め込みに趣旨が類似している。ハッシュはバイナリ空間｛０，１｝Ｍ内にあるので、適切な距離メトリックは正規化されたハミング距離
【００６１】
【数１２】
【００６２】
である。
【００６３】
上述したようにｌ２距離ｄ＝||ｘ−ｘ’||２を有するベクトルｘ及びｘ’の量子化を考える。個々の量子化ビットの各対間の距離
【００６４】
【数１３】
【００６５】
は、分布
【００６６】
【数１４】
【００６７】
を有するランダムバイナリ値である。
【００６８】
この分布及び上下界は図２にプロットされている。例えば図１Ｄにおけるようなマルチビット量子化器の場合、ハミング距離は埋め込み空間内の別の適切な距離によって置き換えることができる。例えば、ハミング距離は埋め込み空間内のｌ１距離又はｌ２距離によって置き換えることができる。
【００６９】
ランダム変数の和がその予測値から逸れる確率に対する上界を与えるヘフディングの不等式を用いると、ハミング距離が
【００７０】
【数１５】
【００７１】
を満たすことを示すのは簡単である。
【００７２】
次に、セキュアに埋め込むことを望むＬ個のデータ点の「クラウド」を考える。それぞれが式(８)を満たす、このクラウド内の最大でＬ２個の可能な信号対に対する和集合上界(union bound)を用いると、以下が成り立つ。
【００７３】
定理ＩＩ
【００７４】
【数１６】
【００７５】
内のＬ個の信号の集合Ｓ及び補題Ｉの量子化方法を考える。確率
【００７６】
【数１７】
【００７７】
で、全ての対ｘ，ｘ’∈Ｓ及びそれらの対応するハッシュｑ、ｑ’について以下が成り立つ。
【００７８】
【数１８】
【００７９】
ここで、Ｐｃ|ｄは補題Ｉにおいて定義され、ｄはｌ２距離であり、ｄＨ(・，・)はそれらのハッシュ間の正規化されたハミング距離である。
【００８０】
定理ＩＩは、圧倒的な確率で、２つのハッシュ間の正規化されたハミング距離が、ｔによって制御されて、１−Ｐｃ|ｄによって定義されるｌ２距離のマッピングに非常に近いことを述べている。さらに、式(４)〜式(６)内の上下界を用いて、式(９)の閉形式の埋め込み境界を得ることができる。
【００８１】
【数１９】
【００８２】
図２は、マッピング１−Ｐｃ|ｄを、その上下界とともに示す。マッピング２０１は、小さなｄの場合に線形であり、大きなｄの場合に実質的に平坦となり(２０２)、したがって可逆でなく、スケーリングを用いて感度パラメーターΔによって制御される。さらに、図２において、上界２０１
【００８３】
【数２０】
【００８４】
が、それぞれ小さいｄ及び大きいｄについて非常に厳密であり、マッピングの近似として用いることができることが明らかである。当然ながら、定理ＩＩの結果及びマッピングに対する制限は、ハミング距離の関数としてｌ２距離に対する保証を提供するように反転することができる。
【００８５】
図３は、実際に埋め込みがどのように挙動するかを示している。図３の(Ａ)，(Ｂ)は、ハッシュの対間の正規化されたハミング距離に対する結果を、それらの距離を生成した信号間の距離の関数として示している。図面は、この発明によるセキュアなハッシングの重要な特性を示している。しきい値Ｔ３０１よりも大きな全ての距離について、正規化された距離応答は平坦であり、正規化されたハミング距離は全てのｌ２距離について同一であるので、実際の距離については何も習得することができない。しかしながら、しきい値よりも小さな距離の場合、正規化されたハミング距離は実際の距離にほぼ比例する。
【００８６】
示された例では、信号は
【００８７】
【数２１】
【００８８】
、すなわちＫ＝２１０においてランダムに生成される。図３の(Ａ)のプロットは、ハッシュあたりＭ＝２１２＝４０９６個の測定値、すなわち係数あたり４ビットを用いる。図３の(Ｂ)のプロットは、ハッシュあたりＭ＝２８＝２５６個の測定値、すなわち係数あたり１／４ビットを用いる。各プロットにおいて２つの異なるΔ、すなわちΔ＝２−３、２−１が用いられる。Δが大きくなると、埋め込みの線形部分の傾斜が増大し、より大きな範囲のｌ２距離を識別することができる。より大きな距離の信号について情報が明らかになるので、これによってセキュリティが低下する。さらに、ハッシュビット数Ｍが小さくなると、線形領域の幅３０１が増大し、これによって線形領域においてマップを反転させる際の不確実性が増大する。他方で、ハッシュビット数Ｍが増大すると、埋め込みは、帯域幅要件が大きくなることと引き換えに、より厳密になる。これは、近傍間のｌ２距離をハッシュからより正確に推定することができることを意味する。信号が量子化されている場合であっても、信号の距離間の正確なマッピングにおける同様の不確実性が存在し、次に、例えば準同形暗号化システムを用いて、暗号化領域内で比較されることに留意されたい。
【００８９】
この挙動は、埋め込みの、上述した情報理論的セキュリティと一致する。小さな距離ｄの場合、ハッシュ内に提供される情報が存在し、この情報を用いて信号間の距離を求めることができる。より大きな距離ｄの場合、情報は明らかにされない。したがって、２つの信号のハッシュからそれらの２つの信号間の距離も、いかなる他の情報も求めることが可能でない。
【００９０】
応用形態
ハッシュに基づく最近傍探索が特に有利である様々な応用形態を説明する。全てのパーティが準正直である、すなわちパーティはプロトコルの規則に従うが、プロトコルの各ステップにおいて利用可能な情報を用いて他のパーティが保有するデータの発見を試みる可能性があると仮定する。
【００９１】
以下に説明するプロトコルの全てにおいて、埋め込みパラメーターＡ、ｗ、及びΔが、図２の線形比例領域が少なくとも最大でＤのｌ２距離まで拡張するように選択されると仮定する。ＤＨによって表されるこの比例領域内では、ハッシュ間の正規化されたハミング距離は、基礎を成す信号間のＤのｌ２距離に対応する。線形比例領域の外側では、埋め込みは平坦な応答を有し、不可逆であり、したがってセキュアであることを想起されたい。換言すれば、２つの信号間の距離が線形比例領域の外側にある場合、信号のハッシュを観察することによってその信号に関するいかなる情報も得ることができない。
【００９２】
スタートポロジーを用いたプライバシー保護クラスタリング
図４に示すようなこの応用形態では、埋め込み行列Ａ及びディザーベクトルｗが知られていないとき、対応するハッシュを観察することによってベクトルｘに関する情報が明らかにされない特性を利用する。この応用形態では、複数のクライアントパーティＰ(ｉ)がサーバーＳによって解析されるデータｘ(ｉ)を提供する。目標は、Ｓがデータを明らかにすることなくデータをクラスタリングし、クライアントＰをクラスに編成することを可能にすることである。クライアントごとに、サーバーはＤのｌ２距離内のクライアントの近似最近傍を得る。
【００９３】
プロトコル：プロトコルは図４に要約されている。
１)全てのパーティが、ランダム埋め込み行列Ａと、ディザーベクトルｗと、感度パラメーターΔとを等しく得る。これを達成する１つの方法は、１つのクライアントパーティが受信者の公開暗号化鍵を用いて他のクライアントパーティにＡ、ｗ、及びΔを送信することである。
２)ｉ∈Ｉ＝｛１，２，…，Ｎ｝について、各クライアントがｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求め、ｑ(ｉ)を平文としてサーバーＳに送信する。
３)各パーティＰ(ｉ)に応じて、サーバーは集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成する。
【００９４】
式(９)から、Ｃｉの要素がパーティＰ(ｉ)の近似最近傍であることがわかる。埋め込みの特性により、サーバーは基礎を成すデータｘ(ｉ)を発見することなく、平文形式でバイナリハッシュを用いてクラスタリングを実行することができる。このため、パラメーターＡ、ｗ、及びΔをＮ個のパーティに通信するために被る最初の一時的な前処理オーバーヘッドは別として、このプロトコルにおいて、いかなる後続の処理にも暗号化は必要とされない。
【００９５】
これは、元のデータｘ(ｉ)に基づいて距離計算を実行することが必要なプロトコルと対照的である。このプロトコルは、サーバーが追加のサブプロトコルに携わり、準同形暗号化を用いて暗号化領域内でＯ(Ｎ２)個の対ごとの距離を求めることを必要とする。
【００９６】
対称鍵を用いた認証
図５に示すようなこの応用形態では、例えば生体パラメーター又は画像から導出されたベクトルｘを用いて認証する。目標は、データｘを可能性のある盗聴者に明らかにすることなく、信頼されたサーバーを用いてユーザーｘを認証することである。目標が認証である場合、クライアントユーザーはアイデンティティーを主張し、サーバーは、サブミットされた認証ハッシュベクトルｑがサーバーにおけるデータベース内に格納された登録ハッシュベクトルｑ(Ｎ)ベクトルから所定のｌ２距離内にあるか否かを判断する。目標が識別である場合、サーバーは、サブミットされたベクトルが、そのサーバーのデータベース内に格納された少なくとも１つの登録ベクトルから所定のｌ２距離以内にあるか否かを判断する。量子化されたランダム埋め込みの部分空間内で認証を実行する。ここで、埋め込みパラメーター(Ａ，ｗ，Δ)は、クライアント及び信頼された認証サーバーにのみ知られているが盗聴者には知られていない対称鍵としての役割を果たす。ユーザー識別シナリオのためのプロトコルを以下で説明する。認証プロトコルは同様に進む。
【００９７】
クライアントのユーザーは、識別に用いられるベクトルｘを有する。サーバーはＮ個の登録ベクトルｘ(ｉ)(ｉ∈Ｉ＝｛１，２，…，Ｎ｝)のデータベースを有する。ユーザー及びサーバー(盗聴者ではない)は埋め込みパラメーター(Ａ，ｗ，Δ)を有する。
【００９８】
サーバーは、Ｄのｌ２距離内のベクトルｘの近似最近傍の集合Ｃを求める。
【００９９】
【数２２】
【０１００】
である、すなわち空である場合、ユーザー識別は失敗し、そうでない場合、ユーザーは、データベース内の少なくとも１人の正当な登録ユーザーに近いと識別される。盗聴者はｘに関する情報を得ない。
【０１０１】
プロトコル：プロトコル送信は図５に要約されている。
１)ユーザー５０１はｑ＝Ｑ(Δ−１(Ａｘ＋ｗ))を求め、ｑを平文としてサーバーに送信する。
２)サーバー５０３は全てのｉについてｑ(ｉ)＝Ｑ(Δ―１(Ａｘ(ｉ)＋ｗ))を求める。
３)サーバーは集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成する。
【０１０２】
ここでも、式(９)から、集合Ｃがｘの近似最近傍を含むことがわかる。
【０１０３】
【数２３】
【０１０４】
である場合、識別は失敗し、そうでない場合、ユーザーはＣ内のインデックスのうちの１つを有するものとして識別されている。盗聴者５０２は(Ａ，ｗ，Δ)５０４を知らないので、量子化された埋め込みは基礎を成すベクトルに関する情報を明らかにしない。このプロトコルは、ハッシュを認証サーバーに送信する前にユーザーがハッシュを暗号化することを必要としない。通信オーバーヘッドの観点から、これは従来の最近傍探索を上回る利点である。従来の最近傍探索は、ベクトルを盗聴者から隠すために、クライアントがそのベクトルを暗号化形式でサーバーに送信することを必要とする。
【０１０５】
一変形形態として、信頼されていないサーバーのプロトコルを設計するために、サーバーはｘ(ｉ)ではなくｑ(ｉ)のみを格納し、埋め込みパラメーター(Ａ，ｗ，Δ)を保有しないことを規定することができる。認証サーバーが信用されていない場合、クライアントユーザーは、自身の識別ベクトルｘ(ｉ)を用いて登録することを望まない。この場合、(サーバーではなく)ユーザーのみが(Ａ，ｗ，Δ)を保有するように上記のプロトコルを変更する。
【０１０６】
ユーザーは、対応するデータベクトルｘ(ｉ)の代わりにハッシュｑ(ｉ)を用いてサーバーのデータベースに登録する。ハッシュはサーバー上に格納される唯一のデータである。この場合、サーバーは、(Ａ’，ｗ，Δ)を知らないので、ｑ(ｉ)からｘ(ｉ)を再構成することができない。さらに、データベースが危険にさらされている場合、ｑ(ｉ)を無効にすることができ、異なる埋め込みパラメーター(Ａ’，ｗ’，Δ’)を用いて新たなハッシュを登録することができる。
【０１０７】
２つのパーティを用いたプライバシー保護クラスタリング
次に図６に示すように、クライアント６０１がデータベースサーバー６０２に対しクエリを開始する２パーティプロトコルを考える。プライバシー制約は、クエリがサーバーに明らかにされないこと、及びクライアントが、そのクライアントのクエリから所定のｌ２距離内にあるデータベースサーバー内のベクトルのみを知ることができることである。スタートポロジーのための前のプロトコルと異なり、ここでは、暗号化領域内で単純な操作を実行するのに、公開鍵暗号化のための確率非対称パイエ(Paillier)暗号化システム等の準同形暗号化システム方式を用いることが必要である。
【０１０８】
パイエ暗号化システムの加法的準同形特性により、ξｐ(ａ)ξｑ(ｂ)＝ξｐｑ(ａ＋ｂ)であることが確実にされ、ここでａ及びｂはメッセージ空間内の整数であり、ξ(・)は暗号化関数である。整数ｐ及びｑはランダムに選択された暗号化パラメーターであり、これによってパイエ暗号化システムが意味論的にセキュアになる。すなわち、パラメーターｐ、ｑをランダムに選択することによって、所与の平文の繰り返された暗号化の結果として異なる暗号文が生成され、それによって選択平文攻撃(ＣＰＡ)に対して保護されることを確実にすることができる。簡単にするために、この発明者らの表記から添え字ｐ、ｑを省略する。加法的準同形特性の当然の帰結として、ξ(ａ)ｂ＝ξ(ａｂ)である。
【０１０９】
クライアントはクエリベクトルｘを有する。サーバーは、Ｉ＝１，…，ＮについてＮ個のベクトルｘ(ｉ)のデータベースを有する。サーバーは(Ａ，ｗ，Δ)を生成し、Δを公開する。クライアントは
【０１１０】
【数２４】
【０１１１】
、すなわちＤのｌ２距離内のクエリベクトルｘの近似最近傍の集合を得る。そのようなベクトルが存在しない場合、クライアントは
【０１１２】
【数２５】
【０１１３】
を得る。
【０１１４】
プロトコル：プロトコル送信は図６に要約されている。
１)クライアントは、パイエ暗号化の公開暗号化鍵ｐｋ及び秘密復号化鍵ｓｋを生成する。次に、クライアントは、ξ(ｘ)＝(ξ(ｘ１)，ξ(ｘ２)，…，ξ(ｘＫ))によって表される、ｘの要素ごとの暗号化を実行する。クライアントはξ(ｘ)をサーバーに送信する。
２)サーバーは加法的準同形特性を用いてξ(ｙ)＝ξ(Ａｘ＋ｗ)を求め、ξ(ｙ)をクライアントに返す。
３)クライアントはｙを復号化し、ｑ＝Δ−１ｙを求め、ξ(ｑ)をサーバーに送信する。
４)サーバーは、ハッシュｑ(ｉ)＝Ｑ(Δ―１(Ａｘ(ｉ)＋ｗ))を求める。
５)サーバーは、準同形特性を用いて、量子化されたクエリベクトルと、量子化されたデータベースベクトルとの間のハミング距離の暗号化を求め、すなわちｄＨ(ｑ，ｑ(ｉ))：
【０１１５】
【数２６】
【０１１６】
を求め、暗号化された距離をクライアントに送信する。
６)クライアントはｄＨ(ｑ，ｑ(ｉ))を復号化し、集合Ｄ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))＜ＤＨ｝を得る。
７)Ｄ＝０の場合、プロトコルは終了する。そうでない場合、クライアントはＮ個のうち|Ｄ|個の紛失通信(ＯＴ)プロトコルをサーバーとともに実行し、Ｃ＝｛ｘ(ｉ)｝を取り出す。ＯＴは、クライアントが
【０１１７】
【数２７】
【０１１８】
となるようなベクトルｘ(ｉ)のうちのいずれも発見しないことを保証する一方で、クエリ集合Ｄがサーバーに明らかにされないことを確実にする。
【０１１９】
式(９)から、集合Ｃはクエリベクトルｘの近似最近傍を含む。基礎を成すベクトル間の距離を暗号化領域で求めることに対する、ハッシュ部分空間において距離を求めることの利点を考える。サイズＮのデータベース場合、ベクトル間の距離を求めることによって、全てのＮ個の距離||ｘ−ｘ(ｉ)||２が明らかとなる。最近傍に対応する距離、すなわち距離の局所分布のみがクライアントに明らかにされることを確実にするには別個のサブプロトコルが必要である。
【０１２０】
対照的に、この発明によるプロトコルは、||ｘ−ｘ(ｉ)||２≦Ｄの場合にのみ距離を明らかにする。||ｘ−ｘ(ｉ)||２＞Ｄの場合、量子化されたランダム埋め込みを用いて求められたハミング距離はもはや真の距離に比例しない。これは、クライアントがサーバーのデータベース内のベクトルの大域分布を知ることを防ぐ一方、クエリベクトル付近のベクトルの局所分布のみを明らかにする。
【０１２１】
発明の効果
量子化されたランダム埋め込みを用いたセキュアなバイナリ法を説明している。このバイナリ法は、信号ベクトルとデータベクトルとの間の距離を特殊な形で保持する。１つのベクトルが別のベクトルからあらかじめ指定された距離ｄ内にある限り、それらのベクトルの２つの量子化された埋め込み間の正規化されたハミング距離は２つのベクトル間のｌ２距離にほぼ比例する。しかしながら、２つのベクトル間の距離がｄを超えて増大すると、それらのベクトルの埋め込み間のハミング距離は、ベクトル間の距離と無関係になる。
【０１２２】
埋め込みは、幾つかの有用なプライバシー特性を更に示す。任意の２つのハッシュ間の相互情報は、それらのハッシュの基礎を成す信号間の距離とともに指数関数的にゼロまで減少する。
【０１２３】
この埋め込み手法を用いて、効率的なプライバシーを保護した最近傍探索を実行する。ほとんどの以前のプライバシーを保護した最近傍探索法は、プライバシー制約を満たすには暗号化しなくてはならない元のベクトルを用いて実行される。
【０１２４】
上記の特性に起因して、元のベクトルの代わりにこの発明によるハッシュを用いて、大幅に低い複雑度で又は高速に、暗号化されていない領域内でプライバシー保護された最近傍探索を実施することができる。これを動機付けするために、低複雑度のクラスタリング及びサーバーベースの認証においてプロトコルを説明している。
【０１２５】
好ましい実施の形態の例としてこの発明を説明してきたが、この発明の趣旨及び範囲内において、他の様々な適合及び変更を行えることが理解されるべきである。
【特許請求の範囲】
【請求項１】
信号をハッシュする方法であって、
前記信号のディザリング及びスケーリングされたランダム射影を求めるステップと、
ハッシュを形成するために、非単調スカラー量子化器を用いて前記ディザリング及びスケーリングされたランダム射影を量子化するステップと、
を含み、
前記信号のプライバシーは、前記スケーリング、前記ディザリング、及び前記射影のパラメーターが前記求めるステップ及び前記量子化するステップによってしか知られていない限り保護され、前記ステップはプロセッサにおいて実行される、信号をハッシュする方法。
【請求項２】
埋め込みパラメーターＡ、ｗ、Δを定義するステップと、
ｙ＝Δ−１(Ａｘ＋ｗ)を求めるステップと、
を更に含み、
ここで、Ａはランダムに生成された射影行列であり、Δは同一で所定の感度パラメーターの対角行列であり、ｗは区間［０，Δ］で一様分布した加法的ディザーのベクトルである、請求項１に記載の方法。
【請求項３】
前記行列Ａは、独立同一分布の行列要素を導出することによってランダムに生成される、請求項２に記載の方法。
【請求項４】
前記導出は正規分布から行われる、請求項３に記載の方法。
【請求項５】
複数の信号のハッシュｑ(ｉ)を比較して、該複数の信号の類似度をセキュアに求める、請求項１に記載の方法。
【請求項６】
前記類似度は距離の観点からのものであり、該距離が所定のしきい値未満である場合、前記複数の信号は類似している、請求項５に記載の方法。
【請求項７】
前記ハッシュ間の埋め込み距離は、前記信号間のｌ２距離が所定のしきい値未満である限り、該距離に比例する、請求項５に記載の方法。
【請求項８】
前記ハッシュ間の埋め込み距離はバイナリ空間内のハミング距離である、請求項７に記載の方法。
【請求項９】
距離が所定のしきい値よりも大きい限り、前記ハッシュは類似していない信号に関する情報を明らかにしない、請求項５に記載の方法。
【請求項１０】
前記比較は、前記複数の信号の最近傍探索を近似する、請求項５に記載の方法。
【請求項１１】
ハッシュｑｎに従って前記複数の信号のクラスタリングを実行するステップを更に含む、請求項５に記載の方法。
【請求項１２】
距離決定は、前記複数の信号を明らかにすることなく、平文において前記ハッシュに対して実行される、請求項５に記載の方法。
【請求項１３】
前記ハッシュは感度パラメーターΔに等しい幅区間を有する非単調量子化関数を用いる、請求項１に記載の方法。
【請求項１４】
前記ハッシュは複数の量子化レベルを用いる、請求項１に記載の方法。
【請求項１５】
前記複数の信号のそれぞれは、対応するクライアントによってサーバーに提供され、前記方法は、
前記信号を明らかにすることなく前記クライアントをクラスに編成するステップを更に含む、請求項５に記載の方法。
【請求項１６】
Ａ、ｗ、及びΔは埋め込みパラメーターであり、前記各クライアントは公開暗号化鍵を用いて前記埋め込みパラメーターのコピーを取得し、
前記各クライアントｉにおいて、ｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求め、ｑ(ｉ)を平文として前記サーバーに送信するステップと、
前記サーバーにおいて、集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成するステップであって、ＤＨは比例領域であるものと、
を含む、請求項１５に記載の方法。
【請求項１７】
前記信号のうちの１つはクライアントにおいて格納されるユーザーの認証鍵であり、他のｉ個の信号はサーバーにおいて格納される登録鍵である、請求項５に記載の方法。
【請求項１８】
前記認証鍵及び前記登録鍵は生体パラメーターに基づき、前記方法は、
前記クライアントにおいてｑ＝Ｑ(Δ−１(Ａｘ＋ｗ))を求めるステップと、
ｑを平文として前記サーバーに送信するステップと、
前記サーバーにおいて、全てのＩについてｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求めるステップと、
前記サーバーにおいて、集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成するステップであって、ＤＨは比例領域であるものと、
を更に含む、請求項１７に記載の方法。
【請求項１９】
前記信号のうちの１つは、クライアントにおいて格納されるクエリであり、他のｉ個の信号は、サーバーにおいて格納されるベクトルである、請求項５に記載の方法。
【請求項１】
信号をハッシュする方法であって、
前記信号のディザリング及びスケーリングされたランダム射影を求めるステップと、
ハッシュを形成するために、非単調スカラー量子化器を用いて前記ディザリング及びスケーリングされたランダム射影を量子化するステップと、
を含み、
前記信号のプライバシーは、前記スケーリング、前記ディザリング、及び前記射影のパラメーターが前記求めるステップ及び前記量子化するステップによってしか知られていない限り保護され、前記ステップはプロセッサにおいて実行される、信号をハッシュする方法。
【請求項２】
埋め込みパラメーターＡ、ｗ、Δを定義するステップと、
ｙ＝Δ−１(Ａｘ＋ｗ)を求めるステップと、
を更に含み、
ここで、Ａはランダムに生成された射影行列であり、Δは同一で所定の感度パラメーターの対角行列であり、ｗは区間［０，Δ］で一様分布した加法的ディザーのベクトルである、請求項１に記載の方法。
【請求項３】
前記行列Ａは、独立同一分布の行列要素を導出することによってランダムに生成される、請求項２に記載の方法。
【請求項４】
前記導出は正規分布から行われる、請求項３に記載の方法。
【請求項５】
複数の信号のハッシュｑ(ｉ)を比較して、該複数の信号の類似度をセキュアに求める、請求項１に記載の方法。
【請求項６】
前記類似度は距離の観点からのものであり、該距離が所定のしきい値未満である場合、前記複数の信号は類似している、請求項５に記載の方法。
【請求項７】
前記ハッシュ間の埋め込み距離は、前記信号間のｌ２距離が所定のしきい値未満である限り、該距離に比例する、請求項５に記載の方法。
【請求項８】
前記ハッシュ間の埋め込み距離はバイナリ空間内のハミング距離である、請求項７に記載の方法。
【請求項９】
距離が所定のしきい値よりも大きい限り、前記ハッシュは類似していない信号に関する情報を明らかにしない、請求項５に記載の方法。
【請求項１０】
前記比較は、前記複数の信号の最近傍探索を近似する、請求項５に記載の方法。
【請求項１１】
ハッシュｑｎに従って前記複数の信号のクラスタリングを実行するステップを更に含む、請求項５に記載の方法。
【請求項１２】
距離決定は、前記複数の信号を明らかにすることなく、平文において前記ハッシュに対して実行される、請求項５に記載の方法。
【請求項１３】
前記ハッシュは感度パラメーターΔに等しい幅区間を有する非単調量子化関数を用いる、請求項１に記載の方法。
【請求項１４】
前記ハッシュは複数の量子化レベルを用いる、請求項１に記載の方法。
【請求項１５】
前記複数の信号のそれぞれは、対応するクライアントによってサーバーに提供され、前記方法は、
前記信号を明らかにすることなく前記クライアントをクラスに編成するステップを更に含む、請求項５に記載の方法。
【請求項１６】
Ａ、ｗ、及びΔは埋め込みパラメーターであり、前記各クライアントは公開暗号化鍵を用いて前記埋め込みパラメーターのコピーを取得し、
前記各クライアントｉにおいて、ｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求め、ｑ(ｉ)を平文として前記サーバーに送信するステップと、
前記サーバーにおいて、集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成するステップであって、ＤＨは比例領域であるものと、
を含む、請求項１５に記載の方法。
【請求項１７】
前記信号のうちの１つはクライアントにおいて格納されるユーザーの認証鍵であり、他のｉ個の信号はサーバーにおいて格納される登録鍵である、請求項５に記載の方法。
【請求項１８】
前記認証鍵及び前記登録鍵は生体パラメーターに基づき、前記方法は、
前記クライアントにおいてｑ＝Ｑ(Δ−１(Ａｘ＋ｗ))を求めるステップと、
ｑを平文として前記サーバーに送信するステップと、
前記サーバーにおいて、全てのＩについてｑ(ｉ)＝Ｑ(Δ−１(Ａｘ(ｉ)＋ｗ))を求めるステップと、
前記サーバーにおいて、集合Ｃ＝｛ｉ|ｄＨ(ｑ，ｑ(ｉ))≦ＤＨ｝を構成するステップであって、ＤＨは比例領域であるものと、
を更に含む、請求項１７に記載の方法。
【請求項１９】
前記信号のうちの１つは、クライアントにおいて格納されるクエリであり、他のｉ個の信号は、サーバーにおいて格納されるベクトルである、請求項５に記載の方法。
【図１Ａ】
【図１Ｂ】
【図１Ｃ】
【図１Ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１Ｂ】
【図１Ｃ】
【図１Ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−１０１３３２（Ｐ２０１３−１０１３３２Ａ）
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−２２７６５６（Ｐ２０１２−２２７６５６）
【出願日】平成２４年１０月１５日（２０１２．１０．１５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願番号】特願２０１２−２２７６５６（Ｐ２０１２−２２７６５６）
【出願日】平成２４年１０月１５日（２０１２．１０．１５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]