類似性指標のセキュアな計算
本発明は、少なくとも２つのデータセットの類似性の指標をセキュア計算する方法及びシステムに関する。本発明の基本的アイデアは、２つのデータセットが十分な程度まで互いに類似しているか判断するため、暗号化された２つのデータセットをセキュアに比較するというものである。類似性の指標が所定の基準に従う場合、暗号化されたデータセットが得られる２つのデータセットは、同一であるとみなされる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも２つのデータセットの類似性の指標をセキュアに計算する方法及びシステムに関する。
【背景技術】
【０００２】
物理オブジェクトの認証は、セキュアな建物への限定的アクセス、デジタルデータへの限定的アクセス（コンピュータ又は着脱可能な記憶媒体に格納されているものなど）、又は識別のため（例えば、特定の行動について識別された個人に委ねるため、又は入国するためなど）などの多数の用途に利用可能である。指紋、虹彩、耳、顔などユーザに独特の特徴が利用される識別及び／又は認証のためのバイオメトリックスの利用は、拡大しつつある程度まで、パスワードやピンコードなどの従来の識別手段と、個人と写真などとの間の視覚的比較に関する“手作業による（ｍａｎｕａｌ）”識別とのより良い代替と考えられている。将来的に、税関職員による手作業による識別を必要とする従来のパスポートは、生体特徴を利用する電子パスポートによって取って代わることができる。
【０００３】
生体特徴は、参照データと比較される。一致する場合、ユーザは識別され、アクセスを付与することが可能である。ユーザの参照データは予め取得された物であり、セキュアデータベースやスマートカードなどにセキュアに格納される。認証対象となる物理オブジェクトはまた、人間でなくてもよい。例えば、対象は、プロテクトされたデジタルコンテンツを有するＣＤ、ＤＶＤ、ソリッドステートメモリなどの記憶媒体であってもよい。この場合、バイオメトリックスは必ずしも利用されず、アナログ的に、秘密に保持されるべき識別特徴（ビットシーケンスなどの形式による）が対応する参照データに提供及び比較される。
【０００４】
認証では、ユーザは特定のアイデンティティを有していることを主張し、提供される生体テンプレートが、提供されたテンプレートと格納されているテンプレートとの間の対応を検証するため、主張されたアイデンティティにリンクした格納されている生体テンプレートと比較される。識別では、提供された生体テンプレートは、提供されたテンプレートと格納されているテンプレートとの間の対応を検証するため、格納されているすべての利用可能なテンプレートと比較される。セキュリティのため、生体測定（一般にはノイズのある）秘密を求める方法を開発することが重要である。生体データは個人のアイデンティティの良好な表示であり、個人に係る生体データの認証されていない取得は、個人のアイデンティティを盗むことと電子的に等価であるとみなされうるということに留意すべきである。個人を識別する適切な生体データを取得した後、ハッカーは当該ハッカーが取得したアイデンティティを有する個人になりすますかもしれない。さらに、生体データは健康状態に関する機密かつプライベートな情報を含むかもしれない。従って、生体認証／識別システムを利用する個人の完全性が保護される必要がある。
【０００５】
バイオメトリックスは個人に関する機密情報を提供するため、生体データの管理及び利用に関するプライバシー問題が存在する。例えば、従来の生体システムでは、ユーザは自らの生体テンプレートの完全性に関して完全に生体システムを必然的に信頼する必要がある。登録中、すなわち、登録期間がユーザの生体テンプレートを取得する初期過程において、ユーザはおそらく暗号化されたテンプレートをシステムに格納する登録期間の登録装置に自らのテンプレートを提供する。検証中、ユーザは再び自らのテンプレートをシステムに提供し、格納されているテンプレートが抽出され（及び必要な場合には、解読される）、格納されているテンプレートと提供されるテンプレートとのマッチングが実行される。真のテンプレートが決して自由に利用可能にならないように、生体テンプレートを暗号化又はハッシュし、暗号化されたデータに対して検証（又はマッチング）を実行する暗号技術を考えることができる。しかしながら、入力の小さな変化が出力における大きな変化をもたらすように、暗号関数が意図的に設計される。ノイズ汚染による提供されたテンプレートと格納されているテンプレートとを取得することに伴う測定誤差とバイオメトリックス本来の性質によって、提供されたテンプレートは格納されているテンプレートと正確には同一とはならず、このため、マッチングアルゴリズムは２つのテンプレートとの間の相違と許容すべきであり、すなわち、生体認証／検証スキームは、ノイズについて本来的にロウバストである必要がある。このことは、暗号化されたテンプレートに基づく検証を問題のあるものにする。
【０００６】
ＩＤ６１３３５６（ＮＬ０３０５５２、ＷＯ ＩＢ２００４／０５０６、ＥＰ０３１０１４５３．３）は、セキュアでプライベートな方法により生体認証を実行するアプローチを提供する。このスキームは、ノイズに対するロウバスト性を可能にするヘルパーデータスキームを利用する。生体認証と暗号化技術を組み合わせるため、ヘルパーデータが登録段階中に求められる。このヘルパーデータは、一意的な文字列が認証中だけでなく登録段階中も個人のバイオメトリックスから求めることが可能であることを保証する。ヘルパーデータはデータベースに格納されているため、公開されていると考えられる。なりすましを防ぐため、ヘルパーデータに統計的に独立し、認証段階において利用される参照データがバイオメトリックから求められる。参照データを秘密に保持するため、参照データはハッシュ形式により格納される。このようにして、なりすましは計算的に実現不可能になる。ＩＤ６１３３５６のアプローチによる問題点は、それが依然としてオリジナルの生体識別子に関する情報を潜在的に悪意のあるベリファイア（ｖｅｒｉｆｉｅｒ）に漏洩するということである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、２つのデータセットの平文バージョンにアクセスする必要なく、ある程度まで互いに類似しているか判断するため、２つのデータセットを比較するセキュアな暗号化スキームを提供することである。
【課題を解決するための手段】
【０００８】
本発明の課題は、請求項１記載の少なくとも２つのデータセットの類似性の指標をセキュアに計算する方法と、請求項８記載の少なくとも２つのデータセットの類似性の指標をセキュアに計算するシステムとによって実現される。
【０００９】
本発明の基本的なアイデアは、２つのデータセットが十分な程度まで互いに類似しているか判断するため、２つのデータセットをセキュアに比較することである。典型的には、生体特徴の測定は、ビットシーケンス、すなわち、０と１の長い系列として表現される（初期的な処理の後）。このようなビットシーケンスの周知の従来の具体例は、ＩｒｉｓＣｏｄｅ（登録商標）であり、個人の目に対して測定が実行され、虹彩の特徴が登録又は認識のため５１２バイトＩｒｉｓＣｏｄｅレコードに符号化される。結果として得られるＩｒｉｓＣｏｄｅレコードは、認識のためデータベースに登録されているすべてのＩｒｉｓＣｏｄｅレコードと比較される。一般に生体識別スキームでは、主要なタスクは、２つのシーケンスＸとＹが同一の個人に帰属するか否かを決定することである。同一の生体識別子、すなわち、特定の個人に属する生体特徴の２つの測定が完全に同一のシーケンス（すなわち、Ｘ＝Ｙ）を生じさせる可能性はごく僅かである。しかしながら、ＸとＹが実際に同一の生体識別子の測定である場合、それらは類似する。従って、生体識別システムは、どの程度までＸとＹが互いに類似しているかを決定することが可能である必要がある。上述されるように、認証対象となる物理オブジェクトは、人間でなくてもよいということに留意すべきである。例えば、当該オブジェクトは、プロテクトされたデジタルコンテンツを含むＣＤ、ＤＶＤ、ソリッドステートメモリなどの記憶媒体であってもよい。この場合、バイオメトリックスは必ずしも利用されず、アナログ的に、秘密に維持されるべき識別特徴（ビットシーケンスなどの形式により）が、対応する参照データに提供及び比較される。
【００１０】
生体識別システムに利用される一般的なアプローチは、いわゆるハミング距離ｄＨ（Ｘ，Ｙ）、すなわち、ベクトルＸ＝（ｘ１，．．．，ｘｎ）とベクトルＹ＝（ｙ１，．．．，ｙｎ）との間のミスマッチ数を計算することである。ハミング距離は、
【００１１】
【数１】
として規定される。
【００１２】
バイナリベクトルが使用されるという事実により、ハミング距離は、
【００１３】
【数２】
として表されるかもしれない。
【００１４】
この距離が十分小さいと考えられる場合、ＸとＹは同一であるとみなされる。典型的には、“十分小さい”とは、ある生体特徴の２つの測定に対するハミング距離の値が所定の閾値以下であることを意味する。例えば、ＩｒｉｓＣｏｄｅでは、ハミング距離はトータルのベクトル長ｎの２０％以下である必要がある。従って、ベクトルが６ビットから構成される場合、ＸとＹを比較すると、１ビットのミスマッチしか存在しないかもしれず、又は２つのベクトルは同一でないと考えられる。従来の識別システムにおいてハミング距離（又は他の何れかの類似性指標）を計算するため、生体特徴の測定（すなわち、Ｘ及びＹ）が明らかにされる必要がある。
【００１５】
本出願において記載される発明は、Ｘの暗号化されたコピーであるＥ（Ｘ）とＹの暗号化されたコピーであるＥ（Ｙ）との間の類似性指標（ハミング距離など）を計算するスキームを特定する。提案されるスキームは、類似性指標が所定の閾値を上回るか又は下回るかのみを開示し、測定された生体識別子の平文表現Ｘ及びＹに関する他の何れの情報も開示しない。
【００１６】
当該スキームは、生体特徴の測定を表す２つのベクトルＸとＹとの間の規定された類似性指標のセキュアな計算を提供し、測定された生体識別子の平文表現Ｘ及びＹを明らかにすることなく、類似性指標と所定の閾値との間の関係を決定する。以下において、類似性指標が上記規定されたハミング距離ｄＨ（Ｘ，Ｙ）により与えられることが仮定される。しかしながら、他の類似性指標が利用されてもよい。
【００１７】
この計算を実行するため、ＰａｉｌｌｉｅｒやＥｌ Ｇａｍａｌなどの準同型閾値暗号化システムが利用される。“準同型（ｈｏｍｏｍｏｒｐｈｉｃ）”という用語は、Ｅ（ｘ＋ｙ）＝Ｅ（ｘ）Ｅ（ｙ）であることを意味する。この用語はさらに、任意のｘ及びａについて、Ｅ（ｘ）ａ＝Ｅ（ｘ＊ａ）であることを意味する。パラメータｘの暗号化は、Ｅｐｋ（ｘ）により示され、ここで、“ｐｋ”は公開鍵暗号化を表す。ユーザとベリファイアは、同一の公開鍵ｐｋにアクセスする。さらに、ユーザとベリファイアはそれぞれ、対応する私有鍵のシェアにアクセスする。私有鍵のシェアは、解読に利用される。
【００１８】
ユーザは、自らのシェアを携帯してもよく（スマートカードなどにより）、又はシェアはユーザがやりとりする生体識別システムのセンサに格納されてもよい。登録中、長さｎのバイナリ文字列から構成されると仮定される生体識別子を表すビットシーケンスＸ、すなわち、Ｘ＝（ｘ１，．．．，ｘｎ）は、キャプチャされ、センサにおいて共通の公開鍵ｐｋにより暗号化され、Ｅｐｋ（Ｘ）＝（Ｅｐｋ（ｘ０），．．．，Ｅｐｋ（ｘｎ））となる。典型的には、これはビット毎に実行される。エントリｘｉは、以下の表現を通じてバイナリ文字列として表すことができる。
【００１９】
【数３】
その後、文字列Ｅｐｋ（Ｘ）はベリファイアにわたされ、格納される。ベリファイアは私有鍵の自らのシェアにしかアクセスできず、ユーザのシェアにはアクセスできないため、Ｅｐｋ（Ｘ）を解読することができないことに留意されたい。従って、生体識別子の平文表現Ｘは、ベリファイアに隠されたままとされる。
【００２０】
認証中、生体識別子のノイズのある表現Ｙが、システムのセンサにおいて取得される。このセンサは、登録が実行されたセンサと必ずしも同一である必要がないことに留意されたい。典型的には、認証センサは登録センサから遠隔的なものである。例えば、一度しか実行されない登録は、より大きなストアチェーンにより構成されるＤＶＤ／ビデオストアの形式により登録期間において行われ、典型的には、認証はユーザがＤＶＤを借りるストアにおいて実行される。このストアは、ユーザが認証されるべき実際のベリファイアとしてみなされてもよい。ユーザを認証するプロセスは、ユーザがスタでＤＶＤを借りるときは常に実行される。この認証センサは、共通の公開鍵ｐｋによりＹを暗号化し、Ｅｐｋ（Ｙ）＝（Ｅｐｋ（ｙ１），．．．，Ｅｐｋ（ｙｎ））となる。ここで、ＸとＹに関して他の何れの情報も明らかにすることなく、ｄＨ（Ｘ，Ｙ）＜Ｔ（Ｔは所定の閾値）であるか求めるためセキュアなプロトコルが実行される。ここで、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））は、以下のようにしてセキュアに計算される。
【００２１】
【数４】
この計算を実行するため、ベリファイアはセキュア計算が行われる認証センサにＥｐｋ（ｘｉ）を送信する。認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）＝Ｅｐｋ（ｘｉ）２ｙｉと、暗号化された出力データが正しいことを示すため構成されるプルーフとを計算する。認証センサでは、暗号化された第１データセットＥｐｋ（Ｘ）と平文の第１データセットＹとが取得される。その後、平文の第１データセットＹは、暗号化された第２データセットＥｐｋ（Ｙ）を生成するため暗号化される。さらに、認証センサは、実際に暗号化された第２データセットＥｐｋ（Ｙ）が、平文の第１データセットＹを公開鍵ｐｋにより暗号化することによって生成されたことを公開認証するプルーフを提供する。
【００２２】
その後、認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）とプルーフを発行し、ベリファイアは当該プルーフをチェックする。最後に、Ｅｐｋ（ｙｉ）に寄与するベリファイアと認証センサは共に、暗号化システムの準同型特性を利用して、式（３）を用いてＥｐｋ（ｄＨ（Ｘ，Ｙ））を計算する。この結果、暗号化された第１データセットＥｐｋ（ｘｉ）と暗号化された第２データセットＥｐｋ（ｙｉ）に部分的に基づき、当該暗号化された第１及び第２データセットに対して、類似性指標Ｅｐｋ（ｄＨ（Ｘ，Ｙ））が計算される。
【００２３】
最後に、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かのセキュア計算が実行される必要がある。上述した計算は、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））、すなわち、ハミング距離ｄＨ（Ｘ，Ｙ）の暗号化を生成する。ｄＨ（Ｘ，Ｙ）＞Ｔであるかチェックするため、認証センサとベリファイアは、２パーティプロトコルを実行する。Ｅｐｋ（ｄＨ（Ｘ，Ｙ））の表現が与えられると、いわゆるＭｉｌｌｉｏｎａｉｒｅｓプロトコルが、例えば、ｄＨ（Ｘ，Ｙ）＞Ｔか否かを求めるため利用されてもよい。その後、この比較の結果が、明らかにされる唯一の情報となる。
【００２４】
この段階では、ＸとＹとの間のハミング距離を表す暗号化されたビットが計算された。両当事者の何れもこの情報を解読することができないことに留意されたい。プロトコルの最後の段階は、与えられた閾値Ｔによる比較である。実際、閾値は暗号化され（ビット毎に）、両当事者には知らされないかもしれない。
【００２５】
Ｅ（ｄＨ（Ｘ，Ｙ））及びＥ（Ｔ）が与えられたとき、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かに関するセキュア計算は、多くの異なる方法により実行可能である。例えば、Ｂ．ＳｃｈｏｅｎｍａｋｅｒｓとＰ．Ｔｕｙｌｓによる“Ｐｒａｃｔｉｃａｌ Ｔｗｏ−Ｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ Ｃｏｎｄｉｔｉｏｎａｌ Ｇａｔｅ”（Ａｓｉａｃｒｙｐｔ ２００４，ＬＮＣＳ Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ ２００４）において開発されたプロトコルが、効果的に利用可能である。
【００２６】
本発明のスキームは、典型的にはノイズによる影響を受けた類似しているが異なるオブジェクトを比較する可能性と強力な暗号化の効果を組み合わせたものである。当該スキームは、使用される公開鍵暗号化システムがセキュアであるという仮定の下、オリジナルの生体特徴に関する情報を開示しないプライベートでセキュアな生体認証を導入する。それは、悪意のあるベリファイアに対するプロテクションセキュリティを提供する。
【００２７】
本発明のさらなる特徴は、共通の生体認証技術がセキュアな方法により、すなわち、暗号化されて利用されるという事実である。類似性指標の計算はセキュアな方法により強力なサーバにアウトソースされてもよい。すなわち、サーバは、生体テンプレートに関する情報を取得しない。計算のため、センサは秘密鍵を必要とせず、公開鍵のみを必要とする（センサは、認証のため秘密鍵を有してもよいが）。さらに、センサ（又はベリファイア）が攻撃された場合、重要な情報は取得できず、ユーザのプライバシーは危うくされない。使用される類似性指標は、自由に選択することが可能であり、使用される既存のセンサを変更することなく容易に更新可能である。計算が公開検証可能であるというさらなる効果が提供される。
【００２８】
本発明は２つのデータセットに対して類似性指標を計算することによって例示した方法により説明されたが、当該計算はさらなるデータセットに拡張可能であるということが当業者により理解される。この場合、ハミング距離以外の指標が利用される必要があるかもしれない。例えば、類似性指標が計算されるデータセット間の最大又は平均距離、又はいわゆるｌ１距離などのエディット距離を利用することが可能である。
【００２９】
本発明の実施例によると、プルーフは以下のように計算される。私有鍵α＝ｌｏｇｇｈが与えられると、
【００３０】
【数５】
のメッセージに対して、ｇｍに等しいｂ／ａαを計算することによって解読が行われる。暗号化は共通の公開鍵ｈにより計算され、解読は、各当事者が私有鍵α＝ｌｏｇｇｈのシェアを所持する当事者間の合成プロトコルを用いて実行される。これらの当事者は、分散された鍵生成プロトコルを実行することにより自らのシェアを取得する。
【００３１】
分散された鍵生成は、当事者Ｐ１とＰ２（センサとベリファイアなど）が、ｉ＝１，２について、
【００３２】
【数６】
による第１ブロードキャストコミットメント
【００３３】
【数７】
を有し、その後、ｉ＝１，２について、
【００３４】
【数８】
となるｌｏｇｇｈｉの知識のプルーフと共にｒｉの値をブロードキャストすることにより実現される。結合公開鍵は、私有鍵α＝α１＋α２によるｈ＝ｈ１ｈ２である。暗号（ａ，ｂ）を解読するため、Ｐｉは、
【００３５】
【数９】
というプルーフ、すなわち、暗号化された出力データが、生体識別子の表現の平文コピーに関する情報を明らかにすることなく正しいことを示すため構成されるプルーフと共に、
【００３６】
【数１０】
を生成する。その後、当該メッセージはｂ／（ａ１ａ２）から復元される。
【００３７】
本発明のさらなる特徴及び効果は、添付した請求項と以下の記載を参照するとき明らかになるであろう。当業者は、本発明の異なる特徴が以下に記載される以外の実施例を生成するため組み合わせ可能であるということを理解する。
【発明を実施するための最良の形態】
【００３８】
図１は、本発明が効果的に利用可能である個人に係る生体データに基づき個人の識別及び認証のための基本的な従来システムを示す。指紋、虹彩若しくは網膜、顔若しくは手のジオメトリ、声の特徴などの個人の生の生体データが、センサ１０１において取得される。取得したデータ（すなわち、生の平文データ）は、典型的には、デジタル信号プロセッサ（ＤＳＰ）などの処理装置１０２において処理される。その後、このデータは、好ましくは暗号化形式により、サービスプロバイダのデータベースストレージ１０３にパス１０５を介し格納される。これは、個人を登録するため、当該システムにアクセスすることを所望する各個人について一度実行される初期化処理である。個人のアイデンティティ、すなわち、生体データをプロテクトするため、暗号化が実行される。その後、個人がサービスにアクセスすることを所望するとき、個人は平文生体データをセンサ１０１に提供する。その後、当該データは、パス１０６を介し処理後に以前にデータベースに格納された個人の生体データと比較される。パス１０６と１０７を介し提供されるデータセットの間の比較装置１０４において実行される比較に一致がある場合、当該個人には提供されるサービスに対するアクセスが付与される。図１を参照するに、センサ１０１は、初期的な特徴抽出セッションでは登録装置として機能し、以降のセッションでは、センサ１０１は、以降に提供される生体情報Ｙ（パス１０６を介し）と初期的に登録された生体情報Ｘ（パス１０７を介し）との間の対応関係について比較装置１０４においてチェックするベリファイアとして機能する。上述したように、図１の装置は互いに遠隔配置されてもよい。
【００３９】
図２は、本発明による個人に係る生体データに基づき個人の識別及び認証を行うシステムを示す。ここでは、登録センサ２０１と検証又は認証センサ２０８とは、互いに遠隔的に配置される。図１と同様に、取得されたデータ（すなわち、生の平文データ）はＤＳＰ２０２において処理される。このデータは暗号化され、データベースストレージ２０３に格納される。その後、個人がシステムにアクセスすることを所望するとき、個人は平文生体データを認証センサ２０８に提供する。その後、当該データはＤＳＰ２０９において暗号化される。個人がシステムにアクセスすることを要求するとき、生体テンプレートＸが登録ストレージ２０１に以前に提供され、ＤＳＰ２０２において暗号化され、データベースストレージ２０３に暗号化形式Ｅｐｋ（Ｘ）により格納されると仮定される図２を参照するに、当該個人の生体テンプレートＹ（Ｘのノイズのある表現である）が検証センサ２０８（認証センサとも呼ばれる）により抽出され、暗号化されたコピーＥｐｋ（Ｙ）を生成するため、ＤＳＰ２０９により暗号化される。典型的には、ＤＳＰ２０９は認証センサ２０８に含まれる。
【００４０】
文字列Ｅｐｋ（Ｘ）は、ベリファイア２１１にわたされ、格納される。ベリファイア２１１はまた、図２には示されていないが、ＤＳＰを含む。ベリファイアは私有鍵のそれのシェのみしかアクセスできず、当該個人のシェアにはアクセスできないため、ベリファイアはＥｐｋ（Ｘ）を解読することはできないということに留意されたい。このため、生体識別子の平文表現Ｘは、ベリファイア２１１に隠されたままである。上述したように、Ｘ及びＹに関して情報を開示することなく、ｄＨ（Ｘ，Ｙ）＜Ｔ（Ｔは所定の閾値）であるか否か求めるため、セキュアプロトコルが実行される。ここで、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））が上述したように計算される。ベリファイア２１１は、セキュア計算を実行する認証センサ２０８にＥｐｋ（ｘｉ）を送信する。
【００４１】
認証センサ２０８は、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）＝Ｅｐｋ（ｘｉ）２ｙｉと、暗号化された出力データが正しいことを示すため構成されるプルーフとを計算する。認証センサは、暗号化された第２データセットＥｐｋ（Ｙ）が実際に平文の第１データセットＹを公開鍵ｐｋにより暗号化することにより生成されたことを公開認証するプルーフを提供する。その後、認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）とプルーフを発行し、ベリファイア２１１が当該プルーフをチェックする。最終的に、Ｅｐｋ（ｘｉ）により寄与するベリファイアと認証センサとは共に、暗号化システムの準同型特性を利用して、上述したようなＥｐｋ（ｄＨ（Ｘ，Ｙ））を計算する。
【００４２】
最後に、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かのセキュア計算が実行される必要がある。上述した計算は、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））、すなわち、ハミング距離ｄＨ（Ｘ，Ｙ）の暗号化をもたらす。ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かチェックするため、認証センサ２０８とベリファイア２１１は、２パーティプロトコルを実行する。ハミング距離の値が閾値Ｔを下回る場合、当該個人はパス２１２により示されるシステムへのアクセスを付与される。図２と共に図１において、本発明の各ステップは、典型的には、適切なソフトウェアパッケージを実行する各装置において実現されるマイクロプロセッサ（図示せず）により実行される。
【００４３】
本発明は、上述した効果に加えて、センサなどの設計についてさらなるフレキシビリティを与える計算のアウトソースを可能にするため、効果的である。さらに、計算ロードは、センサから計算が実行されるサーバ（図示せず）などにシフト可能である。
【００４４】
センサは（結合）公開鍵のみを有し、秘密を有せず、サーバは対応する秘密鍵を有していることが仮定される。１つのサーバのみが利用される場合、第１のアウトソースアルゴリズムが利用されてもよい。複数のサーバが使用される場合、秘密鍵はこれらのサーバの間のセキュア共有スキームにより共有される。この場合、第２のアウトソースアルゴリズムが利用されてもよい。
【００４５】
アクセス制御に加えて、暗号鍵Ｋが生体データから求められる。この鍵は、センサにおける人間の生体テンプレートが参照データベースに格納されているテンプレートに一致するときに限って、リリースされる。簡単には、これは以下のように実行することが可能である。ＸがＹに一致する場合、ｓ＝１とし、そうでない場合にはｓ＝０とする。さらに、マッチング計算の結果がｓの暗号化、すなわち、Ｅ（ｓ）を与えることを仮定する。鍵Ｋは以下のようにリリースすることができる。Ｅ（Ｋ）及びＥ（ｓ）が与えられると、関与する当事者は、結合的に生成された乱数ｒの暗号化Ｅ（ｒ）を計算すると共に、Ｅ（Ｋ＋ｒ（ｓ−１））を計算する。その後、この値は、閾値解読を利用することによって解読される。明らかに、生体テンプレートＸ及びＹが一致する場合、解読は鍵Ｋをリリースする。テンプレートが一致しない場合、ランダムな文字列Ｋ−ｒが取得される。
【００４６】
本発明がそれの具体的な実施例を参照して説明されたが、多数の異なる変更、改良などが当業者に明らかであろう。従って、説明された実施例は、添付される請求項により規定されるような本発明の範囲を限定するものでない。ＤＳＰの代わりに、汎用的な処理要素が利用可能である。
【図面の簡単な説明】
【００４７】
【図１】図１は、個人に係る生体データに基づき個人の識別及び認証を行う基本的な従来システムを示す。
【図２】図２は、本発明による個人に係る生体データに基づき個人の識別及び認証を行うシステムを示す。
【技術分野】
【０００１】
本発明は、少なくとも２つのデータセットの類似性の指標をセキュアに計算する方法及びシステムに関する。
【背景技術】
【０００２】
物理オブジェクトの認証は、セキュアな建物への限定的アクセス、デジタルデータへの限定的アクセス（コンピュータ又は着脱可能な記憶媒体に格納されているものなど）、又は識別のため（例えば、特定の行動について識別された個人に委ねるため、又は入国するためなど）などの多数の用途に利用可能である。指紋、虹彩、耳、顔などユーザに独特の特徴が利用される識別及び／又は認証のためのバイオメトリックスの利用は、拡大しつつある程度まで、パスワードやピンコードなどの従来の識別手段と、個人と写真などとの間の視覚的比較に関する“手作業による（ｍａｎｕａｌ）”識別とのより良い代替と考えられている。将来的に、税関職員による手作業による識別を必要とする従来のパスポートは、生体特徴を利用する電子パスポートによって取って代わることができる。
【０００３】
生体特徴は、参照データと比較される。一致する場合、ユーザは識別され、アクセスを付与することが可能である。ユーザの参照データは予め取得された物であり、セキュアデータベースやスマートカードなどにセキュアに格納される。認証対象となる物理オブジェクトはまた、人間でなくてもよい。例えば、対象は、プロテクトされたデジタルコンテンツを有するＣＤ、ＤＶＤ、ソリッドステートメモリなどの記憶媒体であってもよい。この場合、バイオメトリックスは必ずしも利用されず、アナログ的に、秘密に保持されるべき識別特徴（ビットシーケンスなどの形式による）が対応する参照データに提供及び比較される。
【０００４】
認証では、ユーザは特定のアイデンティティを有していることを主張し、提供される生体テンプレートが、提供されたテンプレートと格納されているテンプレートとの間の対応を検証するため、主張されたアイデンティティにリンクした格納されている生体テンプレートと比較される。識別では、提供された生体テンプレートは、提供されたテンプレートと格納されているテンプレートとの間の対応を検証するため、格納されているすべての利用可能なテンプレートと比較される。セキュリティのため、生体測定（一般にはノイズのある）秘密を求める方法を開発することが重要である。生体データは個人のアイデンティティの良好な表示であり、個人に係る生体データの認証されていない取得は、個人のアイデンティティを盗むことと電子的に等価であるとみなされうるということに留意すべきである。個人を識別する適切な生体データを取得した後、ハッカーは当該ハッカーが取得したアイデンティティを有する個人になりすますかもしれない。さらに、生体データは健康状態に関する機密かつプライベートな情報を含むかもしれない。従って、生体認証／識別システムを利用する個人の完全性が保護される必要がある。
【０００５】
バイオメトリックスは個人に関する機密情報を提供するため、生体データの管理及び利用に関するプライバシー問題が存在する。例えば、従来の生体システムでは、ユーザは自らの生体テンプレートの完全性に関して完全に生体システムを必然的に信頼する必要がある。登録中、すなわち、登録期間がユーザの生体テンプレートを取得する初期過程において、ユーザはおそらく暗号化されたテンプレートをシステムに格納する登録期間の登録装置に自らのテンプレートを提供する。検証中、ユーザは再び自らのテンプレートをシステムに提供し、格納されているテンプレートが抽出され（及び必要な場合には、解読される）、格納されているテンプレートと提供されるテンプレートとのマッチングが実行される。真のテンプレートが決して自由に利用可能にならないように、生体テンプレートを暗号化又はハッシュし、暗号化されたデータに対して検証（又はマッチング）を実行する暗号技術を考えることができる。しかしながら、入力の小さな変化が出力における大きな変化をもたらすように、暗号関数が意図的に設計される。ノイズ汚染による提供されたテンプレートと格納されているテンプレートとを取得することに伴う測定誤差とバイオメトリックス本来の性質によって、提供されたテンプレートは格納されているテンプレートと正確には同一とはならず、このため、マッチングアルゴリズムは２つのテンプレートとの間の相違と許容すべきであり、すなわち、生体認証／検証スキームは、ノイズについて本来的にロウバストである必要がある。このことは、暗号化されたテンプレートに基づく検証を問題のあるものにする。
【０００６】
ＩＤ６１３３５６（ＮＬ０３０５５２、ＷＯ ＩＢ２００４／０５０６、ＥＰ０３１０１４５３．３）は、セキュアでプライベートな方法により生体認証を実行するアプローチを提供する。このスキームは、ノイズに対するロウバスト性を可能にするヘルパーデータスキームを利用する。生体認証と暗号化技術を組み合わせるため、ヘルパーデータが登録段階中に求められる。このヘルパーデータは、一意的な文字列が認証中だけでなく登録段階中も個人のバイオメトリックスから求めることが可能であることを保証する。ヘルパーデータはデータベースに格納されているため、公開されていると考えられる。なりすましを防ぐため、ヘルパーデータに統計的に独立し、認証段階において利用される参照データがバイオメトリックから求められる。参照データを秘密に保持するため、参照データはハッシュ形式により格納される。このようにして、なりすましは計算的に実現不可能になる。ＩＤ６１３３５６のアプローチによる問題点は、それが依然としてオリジナルの生体識別子に関する情報を潜在的に悪意のあるベリファイア（ｖｅｒｉｆｉｅｒ）に漏洩するということである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、２つのデータセットの平文バージョンにアクセスする必要なく、ある程度まで互いに類似しているか判断するため、２つのデータセットを比較するセキュアな暗号化スキームを提供することである。
【課題を解決するための手段】
【０００８】
本発明の課題は、請求項１記載の少なくとも２つのデータセットの類似性の指標をセキュアに計算する方法と、請求項８記載の少なくとも２つのデータセットの類似性の指標をセキュアに計算するシステムとによって実現される。
【０００９】
本発明の基本的なアイデアは、２つのデータセットが十分な程度まで互いに類似しているか判断するため、２つのデータセットをセキュアに比較することである。典型的には、生体特徴の測定は、ビットシーケンス、すなわち、０と１の長い系列として表現される（初期的な処理の後）。このようなビットシーケンスの周知の従来の具体例は、ＩｒｉｓＣｏｄｅ（登録商標）であり、個人の目に対して測定が実行され、虹彩の特徴が登録又は認識のため５１２バイトＩｒｉｓＣｏｄｅレコードに符号化される。結果として得られるＩｒｉｓＣｏｄｅレコードは、認識のためデータベースに登録されているすべてのＩｒｉｓＣｏｄｅレコードと比較される。一般に生体識別スキームでは、主要なタスクは、２つのシーケンスＸとＹが同一の個人に帰属するか否かを決定することである。同一の生体識別子、すなわち、特定の個人に属する生体特徴の２つの測定が完全に同一のシーケンス（すなわち、Ｘ＝Ｙ）を生じさせる可能性はごく僅かである。しかしながら、ＸとＹが実際に同一の生体識別子の測定である場合、それらは類似する。従って、生体識別システムは、どの程度までＸとＹが互いに類似しているかを決定することが可能である必要がある。上述されるように、認証対象となる物理オブジェクトは、人間でなくてもよいということに留意すべきである。例えば、当該オブジェクトは、プロテクトされたデジタルコンテンツを含むＣＤ、ＤＶＤ、ソリッドステートメモリなどの記憶媒体であってもよい。この場合、バイオメトリックスは必ずしも利用されず、アナログ的に、秘密に維持されるべき識別特徴（ビットシーケンスなどの形式により）が、対応する参照データに提供及び比較される。
【００１０】
生体識別システムに利用される一般的なアプローチは、いわゆるハミング距離ｄＨ（Ｘ，Ｙ）、すなわち、ベクトルＸ＝（ｘ１，．．．，ｘｎ）とベクトルＹ＝（ｙ１，．．．，ｙｎ）との間のミスマッチ数を計算することである。ハミング距離は、
【００１１】
【数１】
として規定される。
【００１２】
バイナリベクトルが使用されるという事実により、ハミング距離は、
【００１３】
【数２】
として表されるかもしれない。
【００１４】
この距離が十分小さいと考えられる場合、ＸとＹは同一であるとみなされる。典型的には、“十分小さい”とは、ある生体特徴の２つの測定に対するハミング距離の値が所定の閾値以下であることを意味する。例えば、ＩｒｉｓＣｏｄｅでは、ハミング距離はトータルのベクトル長ｎの２０％以下である必要がある。従って、ベクトルが６ビットから構成される場合、ＸとＹを比較すると、１ビットのミスマッチしか存在しないかもしれず、又は２つのベクトルは同一でないと考えられる。従来の識別システムにおいてハミング距離（又は他の何れかの類似性指標）を計算するため、生体特徴の測定（すなわち、Ｘ及びＹ）が明らかにされる必要がある。
【００１５】
本出願において記載される発明は、Ｘの暗号化されたコピーであるＥ（Ｘ）とＹの暗号化されたコピーであるＥ（Ｙ）との間の類似性指標（ハミング距離など）を計算するスキームを特定する。提案されるスキームは、類似性指標が所定の閾値を上回るか又は下回るかのみを開示し、測定された生体識別子の平文表現Ｘ及びＹに関する他の何れの情報も開示しない。
【００１６】
当該スキームは、生体特徴の測定を表す２つのベクトルＸとＹとの間の規定された類似性指標のセキュアな計算を提供し、測定された生体識別子の平文表現Ｘ及びＹを明らかにすることなく、類似性指標と所定の閾値との間の関係を決定する。以下において、類似性指標が上記規定されたハミング距離ｄＨ（Ｘ，Ｙ）により与えられることが仮定される。しかしながら、他の類似性指標が利用されてもよい。
【００１７】
この計算を実行するため、ＰａｉｌｌｉｅｒやＥｌ Ｇａｍａｌなどの準同型閾値暗号化システムが利用される。“準同型（ｈｏｍｏｍｏｒｐｈｉｃ）”という用語は、Ｅ（ｘ＋ｙ）＝Ｅ（ｘ）Ｅ（ｙ）であることを意味する。この用語はさらに、任意のｘ及びａについて、Ｅ（ｘ）ａ＝Ｅ（ｘ＊ａ）であることを意味する。パラメータｘの暗号化は、Ｅｐｋ（ｘ）により示され、ここで、“ｐｋ”は公開鍵暗号化を表す。ユーザとベリファイアは、同一の公開鍵ｐｋにアクセスする。さらに、ユーザとベリファイアはそれぞれ、対応する私有鍵のシェアにアクセスする。私有鍵のシェアは、解読に利用される。
【００１８】
ユーザは、自らのシェアを携帯してもよく（スマートカードなどにより）、又はシェアはユーザがやりとりする生体識別システムのセンサに格納されてもよい。登録中、長さｎのバイナリ文字列から構成されると仮定される生体識別子を表すビットシーケンスＸ、すなわち、Ｘ＝（ｘ１，．．．，ｘｎ）は、キャプチャされ、センサにおいて共通の公開鍵ｐｋにより暗号化され、Ｅｐｋ（Ｘ）＝（Ｅｐｋ（ｘ０），．．．，Ｅｐｋ（ｘｎ））となる。典型的には、これはビット毎に実行される。エントリｘｉは、以下の表現を通じてバイナリ文字列として表すことができる。
【００１９】
【数３】
その後、文字列Ｅｐｋ（Ｘ）はベリファイアにわたされ、格納される。ベリファイアは私有鍵の自らのシェアにしかアクセスできず、ユーザのシェアにはアクセスできないため、Ｅｐｋ（Ｘ）を解読することができないことに留意されたい。従って、生体識別子の平文表現Ｘは、ベリファイアに隠されたままとされる。
【００２０】
認証中、生体識別子のノイズのある表現Ｙが、システムのセンサにおいて取得される。このセンサは、登録が実行されたセンサと必ずしも同一である必要がないことに留意されたい。典型的には、認証センサは登録センサから遠隔的なものである。例えば、一度しか実行されない登録は、より大きなストアチェーンにより構成されるＤＶＤ／ビデオストアの形式により登録期間において行われ、典型的には、認証はユーザがＤＶＤを借りるストアにおいて実行される。このストアは、ユーザが認証されるべき実際のベリファイアとしてみなされてもよい。ユーザを認証するプロセスは、ユーザがスタでＤＶＤを借りるときは常に実行される。この認証センサは、共通の公開鍵ｐｋによりＹを暗号化し、Ｅｐｋ（Ｙ）＝（Ｅｐｋ（ｙ１），．．．，Ｅｐｋ（ｙｎ））となる。ここで、ＸとＹに関して他の何れの情報も明らかにすることなく、ｄＨ（Ｘ，Ｙ）＜Ｔ（Ｔは所定の閾値）であるか求めるためセキュアなプロトコルが実行される。ここで、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））は、以下のようにしてセキュアに計算される。
【００２１】
【数４】
この計算を実行するため、ベリファイアはセキュア計算が行われる認証センサにＥｐｋ（ｘｉ）を送信する。認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）＝Ｅｐｋ（ｘｉ）２ｙｉと、暗号化された出力データが正しいことを示すため構成されるプルーフとを計算する。認証センサでは、暗号化された第１データセットＥｐｋ（Ｘ）と平文の第１データセットＹとが取得される。その後、平文の第１データセットＹは、暗号化された第２データセットＥｐｋ（Ｙ）を生成するため暗号化される。さらに、認証センサは、実際に暗号化された第２データセットＥｐｋ（Ｙ）が、平文の第１データセットＹを公開鍵ｐｋにより暗号化することによって生成されたことを公開認証するプルーフを提供する。
【００２２】
その後、認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）とプルーフを発行し、ベリファイアは当該プルーフをチェックする。最後に、Ｅｐｋ（ｙｉ）に寄与するベリファイアと認証センサは共に、暗号化システムの準同型特性を利用して、式（３）を用いてＥｐｋ（ｄＨ（Ｘ，Ｙ））を計算する。この結果、暗号化された第１データセットＥｐｋ（ｘｉ）と暗号化された第２データセットＥｐｋ（ｙｉ）に部分的に基づき、当該暗号化された第１及び第２データセットに対して、類似性指標Ｅｐｋ（ｄＨ（Ｘ，Ｙ））が計算される。
【００２３】
最後に、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かのセキュア計算が実行される必要がある。上述した計算は、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））、すなわち、ハミング距離ｄＨ（Ｘ，Ｙ）の暗号化を生成する。ｄＨ（Ｘ，Ｙ）＞Ｔであるかチェックするため、認証センサとベリファイアは、２パーティプロトコルを実行する。Ｅｐｋ（ｄＨ（Ｘ，Ｙ））の表現が与えられると、いわゆるＭｉｌｌｉｏｎａｉｒｅｓプロトコルが、例えば、ｄＨ（Ｘ，Ｙ）＞Ｔか否かを求めるため利用されてもよい。その後、この比較の結果が、明らかにされる唯一の情報となる。
【００２４】
この段階では、ＸとＹとの間のハミング距離を表す暗号化されたビットが計算された。両当事者の何れもこの情報を解読することができないことに留意されたい。プロトコルの最後の段階は、与えられた閾値Ｔによる比較である。実際、閾値は暗号化され（ビット毎に）、両当事者には知らされないかもしれない。
【００２５】
Ｅ（ｄＨ（Ｘ，Ｙ））及びＥ（Ｔ）が与えられたとき、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かに関するセキュア計算は、多くの異なる方法により実行可能である。例えば、Ｂ．ＳｃｈｏｅｎｍａｋｅｒｓとＰ．Ｔｕｙｌｓによる“Ｐｒａｃｔｉｃａｌ Ｔｗｏ−Ｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ Ｃｏｎｄｉｔｉｏｎａｌ Ｇａｔｅ”（Ａｓｉａｃｒｙｐｔ ２００４，ＬＮＣＳ Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ ２００４）において開発されたプロトコルが、効果的に利用可能である。
【００２６】
本発明のスキームは、典型的にはノイズによる影響を受けた類似しているが異なるオブジェクトを比較する可能性と強力な暗号化の効果を組み合わせたものである。当該スキームは、使用される公開鍵暗号化システムがセキュアであるという仮定の下、オリジナルの生体特徴に関する情報を開示しないプライベートでセキュアな生体認証を導入する。それは、悪意のあるベリファイアに対するプロテクションセキュリティを提供する。
【００２７】
本発明のさらなる特徴は、共通の生体認証技術がセキュアな方法により、すなわち、暗号化されて利用されるという事実である。類似性指標の計算はセキュアな方法により強力なサーバにアウトソースされてもよい。すなわち、サーバは、生体テンプレートに関する情報を取得しない。計算のため、センサは秘密鍵を必要とせず、公開鍵のみを必要とする（センサは、認証のため秘密鍵を有してもよいが）。さらに、センサ（又はベリファイア）が攻撃された場合、重要な情報は取得できず、ユーザのプライバシーは危うくされない。使用される類似性指標は、自由に選択することが可能であり、使用される既存のセンサを変更することなく容易に更新可能である。計算が公開検証可能であるというさらなる効果が提供される。
【００２８】
本発明は２つのデータセットに対して類似性指標を計算することによって例示した方法により説明されたが、当該計算はさらなるデータセットに拡張可能であるということが当業者により理解される。この場合、ハミング距離以外の指標が利用される必要があるかもしれない。例えば、類似性指標が計算されるデータセット間の最大又は平均距離、又はいわゆるｌ１距離などのエディット距離を利用することが可能である。
【００２９】
本発明の実施例によると、プルーフは以下のように計算される。私有鍵α＝ｌｏｇｇｈが与えられると、
【００３０】
【数５】
のメッセージに対して、ｇｍに等しいｂ／ａαを計算することによって解読が行われる。暗号化は共通の公開鍵ｈにより計算され、解読は、各当事者が私有鍵α＝ｌｏｇｇｈのシェアを所持する当事者間の合成プロトコルを用いて実行される。これらの当事者は、分散された鍵生成プロトコルを実行することにより自らのシェアを取得する。
【００３１】
分散された鍵生成は、当事者Ｐ１とＰ２（センサとベリファイアなど）が、ｉ＝１，２について、
【００３２】
【数６】
による第１ブロードキャストコミットメント
【００３３】
【数７】
を有し、その後、ｉ＝１，２について、
【００３４】
【数８】
となるｌｏｇｇｈｉの知識のプルーフと共にｒｉの値をブロードキャストすることにより実現される。結合公開鍵は、私有鍵α＝α１＋α２によるｈ＝ｈ１ｈ２である。暗号（ａ，ｂ）を解読するため、Ｐｉは、
【００３５】
【数９】
というプルーフ、すなわち、暗号化された出力データが、生体識別子の表現の平文コピーに関する情報を明らかにすることなく正しいことを示すため構成されるプルーフと共に、
【００３６】
【数１０】
を生成する。その後、当該メッセージはｂ／（ａ１ａ２）から復元される。
【００３７】
本発明のさらなる特徴及び効果は、添付した請求項と以下の記載を参照するとき明らかになるであろう。当業者は、本発明の異なる特徴が以下に記載される以外の実施例を生成するため組み合わせ可能であるということを理解する。
【発明を実施するための最良の形態】
【００３８】
図１は、本発明が効果的に利用可能である個人に係る生体データに基づき個人の識別及び認証のための基本的な従来システムを示す。指紋、虹彩若しくは網膜、顔若しくは手のジオメトリ、声の特徴などの個人の生の生体データが、センサ１０１において取得される。取得したデータ（すなわち、生の平文データ）は、典型的には、デジタル信号プロセッサ（ＤＳＰ）などの処理装置１０２において処理される。その後、このデータは、好ましくは暗号化形式により、サービスプロバイダのデータベースストレージ１０３にパス１０５を介し格納される。これは、個人を登録するため、当該システムにアクセスすることを所望する各個人について一度実行される初期化処理である。個人のアイデンティティ、すなわち、生体データをプロテクトするため、暗号化が実行される。その後、個人がサービスにアクセスすることを所望するとき、個人は平文生体データをセンサ１０１に提供する。その後、当該データは、パス１０６を介し処理後に以前にデータベースに格納された個人の生体データと比較される。パス１０６と１０７を介し提供されるデータセットの間の比較装置１０４において実行される比較に一致がある場合、当該個人には提供されるサービスに対するアクセスが付与される。図１を参照するに、センサ１０１は、初期的な特徴抽出セッションでは登録装置として機能し、以降のセッションでは、センサ１０１は、以降に提供される生体情報Ｙ（パス１０６を介し）と初期的に登録された生体情報Ｘ（パス１０７を介し）との間の対応関係について比較装置１０４においてチェックするベリファイアとして機能する。上述したように、図１の装置は互いに遠隔配置されてもよい。
【００３９】
図２は、本発明による個人に係る生体データに基づき個人の識別及び認証を行うシステムを示す。ここでは、登録センサ２０１と検証又は認証センサ２０８とは、互いに遠隔的に配置される。図１と同様に、取得されたデータ（すなわち、生の平文データ）はＤＳＰ２０２において処理される。このデータは暗号化され、データベースストレージ２０３に格納される。その後、個人がシステムにアクセスすることを所望するとき、個人は平文生体データを認証センサ２０８に提供する。その後、当該データはＤＳＰ２０９において暗号化される。個人がシステムにアクセスすることを要求するとき、生体テンプレートＸが登録ストレージ２０１に以前に提供され、ＤＳＰ２０２において暗号化され、データベースストレージ２０３に暗号化形式Ｅｐｋ（Ｘ）により格納されると仮定される図２を参照するに、当該個人の生体テンプレートＹ（Ｘのノイズのある表現である）が検証センサ２０８（認証センサとも呼ばれる）により抽出され、暗号化されたコピーＥｐｋ（Ｙ）を生成するため、ＤＳＰ２０９により暗号化される。典型的には、ＤＳＰ２０９は認証センサ２０８に含まれる。
【００４０】
文字列Ｅｐｋ（Ｘ）は、ベリファイア２１１にわたされ、格納される。ベリファイア２１１はまた、図２には示されていないが、ＤＳＰを含む。ベリファイアは私有鍵のそれのシェのみしかアクセスできず、当該個人のシェアにはアクセスできないため、ベリファイアはＥｐｋ（Ｘ）を解読することはできないということに留意されたい。このため、生体識別子の平文表現Ｘは、ベリファイア２１１に隠されたままである。上述したように、Ｘ及びＹに関して情報を開示することなく、ｄＨ（Ｘ，Ｙ）＜Ｔ（Ｔは所定の閾値）であるか否か求めるため、セキュアプロトコルが実行される。ここで、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））が上述したように計算される。ベリファイア２１１は、セキュア計算を実行する認証センサ２０８にＥｐｋ（ｘｉ）を送信する。
【００４１】
認証センサ２０８は、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）＝Ｅｐｋ（ｘｉ）２ｙｉと、暗号化された出力データが正しいことを示すため構成されるプルーフとを計算する。認証センサは、暗号化された第２データセットＥｐｋ（Ｙ）が実際に平文の第１データセットＹを公開鍵ｐｋにより暗号化することにより生成されたことを公開認証するプルーフを提供する。その後、認証センサは、Ｅｐｋ（ｙｉ）及びＥｐｋ（２ｘｉｙｉ）とプルーフを発行し、ベリファイア２１１が当該プルーフをチェックする。最終的に、Ｅｐｋ（ｘｉ）により寄与するベリファイアと認証センサとは共に、暗号化システムの準同型特性を利用して、上述したようなＥｐｋ（ｄＨ（Ｘ，Ｙ））を計算する。
【００４２】
最後に、ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かのセキュア計算が実行される必要がある。上述した計算は、Ｅｐｋ（ｄＨ（Ｘ，Ｙ））、すなわち、ハミング距離ｄＨ（Ｘ，Ｙ）の暗号化をもたらす。ｄＨ（Ｘ，Ｙ）＞Ｔであるか否かチェックするため、認証センサ２０８とベリファイア２１１は、２パーティプロトコルを実行する。ハミング距離の値が閾値Ｔを下回る場合、当該個人はパス２１２により示されるシステムへのアクセスを付与される。図２と共に図１において、本発明の各ステップは、典型的には、適切なソフトウェアパッケージを実行する各装置において実現されるマイクロプロセッサ（図示せず）により実行される。
【００４３】
本発明は、上述した効果に加えて、センサなどの設計についてさらなるフレキシビリティを与える計算のアウトソースを可能にするため、効果的である。さらに、計算ロードは、センサから計算が実行されるサーバ（図示せず）などにシフト可能である。
【００４４】
センサは（結合）公開鍵のみを有し、秘密を有せず、サーバは対応する秘密鍵を有していることが仮定される。１つのサーバのみが利用される場合、第１のアウトソースアルゴリズムが利用されてもよい。複数のサーバが使用される場合、秘密鍵はこれらのサーバの間のセキュア共有スキームにより共有される。この場合、第２のアウトソースアルゴリズムが利用されてもよい。
【００４５】
アクセス制御に加えて、暗号鍵Ｋが生体データから求められる。この鍵は、センサにおける人間の生体テンプレートが参照データベースに格納されているテンプレートに一致するときに限って、リリースされる。簡単には、これは以下のように実行することが可能である。ＸがＹに一致する場合、ｓ＝１とし、そうでない場合にはｓ＝０とする。さらに、マッチング計算の結果がｓの暗号化、すなわち、Ｅ（ｓ）を与えることを仮定する。鍵Ｋは以下のようにリリースすることができる。Ｅ（Ｋ）及びＥ（ｓ）が与えられると、関与する当事者は、結合的に生成された乱数ｒの暗号化Ｅ（ｒ）を計算すると共に、Ｅ（Ｋ＋ｒ（ｓ−１））を計算する。その後、この値は、閾値解読を利用することによって解読される。明らかに、生体テンプレートＸ及びＹが一致する場合、解読は鍵Ｋをリリースする。テンプレートが一致しない場合、ランダムな文字列Ｋ−ｒが取得される。
【００４６】
本発明がそれの具体的な実施例を参照して説明されたが、多数の異なる変更、改良などが当業者に明らかであろう。従って、説明された実施例は、添付される請求項により規定されるような本発明の範囲を限定するものでない。ＤＳＰの代わりに、汎用的な処理要素が利用可能である。
【図面の簡単な説明】
【００４７】
【図１】図１は、個人に係る生体データに基づき個人の識別及び認証を行う基本的な従来システムを示す。
【図２】図２は、本発明による個人に係る生体データに基づき個人の識別及び認証を行うシステムを示す。
【特許請求の範囲】
【請求項１】
少なくとも２つのデータセットの類似性の指標をセキュア計算する方法であって、
暗号化された第１データセットと平文の第１データセットとを取得するステップと、
暗号化された第２データセットが生成される前記平文の第１データセットを暗号化するステップと、
前記暗号化された第１データセットと前記暗号化された第２データセットとに部分的に基づき、前記暗号化された第１及び第２データセットの類似性の指標を計算するステップと、
前記暗号化されたデータセットと前記類似性の指標とが、正しく計算されたことの公開認証可能なプルーフを提供するステップと、
前記類似性の指標は所定の基準に従っているか判断するステップと、
を有する方法。
【請求項２】
前記類似性の指標は、ハミング距離を有する、請求項１記載の方法。
【請求項３】
前記実行される暗号化は、準同型暗号化を有する、請求項１又は２記載の方法。
【請求項４】
前記使用されるデータは、個人の生体特徴から抽出される、請求項１乃至３何れか一項記載の方法。
【請求項５】
前記類似性の指標は、所定の閾値を下回る場合、所定の基準に従っているとみなされる、請求項１乃至４何れか一項記載の方法。
【請求項６】
第１当事者は、前記暗号化された第２データセットと前記プルーフとを提供するため、前記平文の第１データセットを暗号化し、
第２当事者は、前記暗号化された第１データセットを提供し、
前記第１及び第２当事者は、前記暗号化された第１及び第２データセットを組み合わせることによって、前記類似性の指標を計算する、請求項１乃至５何れか一項記載の方法。
【請求項７】
前記第１当事者は、前記第２当事者に前記プルーフを提供する、請求項６記載の方法。
【請求項８】
前記公開鍵に対応する私有鍵は、前記公開鍵に対して対数関数を実行することによって生成される、請求項１乃至７何れか一項記載の方法。
【請求項９】
少なくとも２つのデータセットの類似性の指標をセキュア計算するシステムであって、
暗号化された第１データセットを取得するよう構成される検証装置と、
個人から平文の第１データセットを抽出し、該平文の第１データセットを暗号化し、暗号化された第２データセットが生成されるよう構成される認証センサと、
を有し、
前記検証装置と前記認証センサとは、前記暗号化された第１データセットと前記暗号化された第２データセットとに部分的に基づき、前記暗号化された第１及び第２データセットの類似性の指標を結合計算するよう構成され、
前記認証センサはさらに、前記暗号化されたデータセットと前記類似性の指標とが正しく計算されたという公開認証可能なプルーフを提供し、前記類似性の指標が所定の基準に従っているか判断するよう構成されるシステム。
【請求項１０】
前記使用されるデータは、個人の生体特徴から抽出される、請求項９記載のシステム。
【請求項１１】
前記個人から第２生体データセットを抽出し、前記暗号化された第１生体データセットを生成するため、第２生体データセットを暗号化するよう構成される登録センサをさらに有する、請求項１０記載のシステム。
【請求項１２】
前記検証装置は、ネットワークを介し前記暗号化された第１データセットを取得するよう構成される、請求項９乃至１１何れか一項記載のシステム。
【請求項１３】
前記実行される暗号化は、準同型暗号化を有する、請求項９乃至１２何れか一項記載のシステム。
【請求項１４】
前記類似性の指標は、所定の閾値を下回る場合、所定の基準に従っているとみなされるように構成される、請求項９乃至１３何れか一項記載のシステム。
【請求項１５】
前記公開鍵に対応する私有鍵が前記公開鍵に対して対数関数を実行することによって生成されるように、さらに構成される、請求項９乃至１４何れか一項記載のシステム。
【請求項１６】
前記認証センサが、前記暗号化された第２データセットと、前記暗号化された第１及び第２データセットの組み合わせとを提供し、前記検証装置が、前記暗号化された第１データセットを提供するように、前記類似性の指標の結合計算が実行される、請求項９乃至１５何れか一項記載のシステム。
【請求項１７】
データの暗号化と処理とがアウトソースされるサーバをさらに有する、請求項９乃至１６何れか一項記載のシステム。
【請求項１８】
コンピュータ実行可能コンポーネントが装置に含まれる処理ユニット上で実行されると、請求項１乃至８何れか一項記載のステップを前記装置に実行させるコンピュータ実行可能コンポーネントを有するコンピュータプログラム。
【請求項１】
少なくとも２つのデータセットの類似性の指標をセキュア計算する方法であって、
暗号化された第１データセットと平文の第１データセットとを取得するステップと、
暗号化された第２データセットが生成される前記平文の第１データセットを暗号化するステップと、
前記暗号化された第１データセットと前記暗号化された第２データセットとに部分的に基づき、前記暗号化された第１及び第２データセットの類似性の指標を計算するステップと、
前記暗号化されたデータセットと前記類似性の指標とが、正しく計算されたことの公開認証可能なプルーフを提供するステップと、
前記類似性の指標は所定の基準に従っているか判断するステップと、
を有する方法。
【請求項２】
前記類似性の指標は、ハミング距離を有する、請求項１記載の方法。
【請求項３】
前記実行される暗号化は、準同型暗号化を有する、請求項１又は２記載の方法。
【請求項４】
前記使用されるデータは、個人の生体特徴から抽出される、請求項１乃至３何れか一項記載の方法。
【請求項５】
前記類似性の指標は、所定の閾値を下回る場合、所定の基準に従っているとみなされる、請求項１乃至４何れか一項記載の方法。
【請求項６】
第１当事者は、前記暗号化された第２データセットと前記プルーフとを提供するため、前記平文の第１データセットを暗号化し、
第２当事者は、前記暗号化された第１データセットを提供し、
前記第１及び第２当事者は、前記暗号化された第１及び第２データセットを組み合わせることによって、前記類似性の指標を計算する、請求項１乃至５何れか一項記載の方法。
【請求項７】
前記第１当事者は、前記第２当事者に前記プルーフを提供する、請求項６記載の方法。
【請求項８】
前記公開鍵に対応する私有鍵は、前記公開鍵に対して対数関数を実行することによって生成される、請求項１乃至７何れか一項記載の方法。
【請求項９】
少なくとも２つのデータセットの類似性の指標をセキュア計算するシステムであって、
暗号化された第１データセットを取得するよう構成される検証装置と、
個人から平文の第１データセットを抽出し、該平文の第１データセットを暗号化し、暗号化された第２データセットが生成されるよう構成される認証センサと、
を有し、
前記検証装置と前記認証センサとは、前記暗号化された第１データセットと前記暗号化された第２データセットとに部分的に基づき、前記暗号化された第１及び第２データセットの類似性の指標を結合計算するよう構成され、
前記認証センサはさらに、前記暗号化されたデータセットと前記類似性の指標とが正しく計算されたという公開認証可能なプルーフを提供し、前記類似性の指標が所定の基準に従っているか判断するよう構成されるシステム。
【請求項１０】
前記使用されるデータは、個人の生体特徴から抽出される、請求項９記載のシステム。
【請求項１１】
前記個人から第２生体データセットを抽出し、前記暗号化された第１生体データセットを生成するため、第２生体データセットを暗号化するよう構成される登録センサをさらに有する、請求項１０記載のシステム。
【請求項１２】
前記検証装置は、ネットワークを介し前記暗号化された第１データセットを取得するよう構成される、請求項９乃至１１何れか一項記載のシステム。
【請求項１３】
前記実行される暗号化は、準同型暗号化を有する、請求項９乃至１２何れか一項記載のシステム。
【請求項１４】
前記類似性の指標は、所定の閾値を下回る場合、所定の基準に従っているとみなされるように構成される、請求項９乃至１３何れか一項記載のシステム。
【請求項１５】
前記公開鍵に対応する私有鍵が前記公開鍵に対して対数関数を実行することによって生成されるように、さらに構成される、請求項９乃至１４何れか一項記載のシステム。
【請求項１６】
前記認証センサが、前記暗号化された第２データセットと、前記暗号化された第１及び第２データセットの組み合わせとを提供し、前記検証装置が、前記暗号化された第１データセットを提供するように、前記類似性の指標の結合計算が実行される、請求項９乃至１５何れか一項記載のシステム。
【請求項１７】
データの暗号化と処理とがアウトソースされるサーバをさらに有する、請求項９乃至１６何れか一項記載のシステム。
【請求項１８】
コンピュータ実行可能コンポーネントが装置に含まれる処理ユニット上で実行されると、請求項１乃至８何れか一項記載のステップを前記装置に実行させるコンピュータ実行可能コンポーネントを有するコンピュータプログラム。
【図１】
【図２】
【図２】
【公表番号】特表２００８−５２１０２５（Ｐ２００８−５２１０２５Ａ）
【公表日】平成２０年６月１９日（２００８．６．１９）
【国際特許分類】
【出願番号】特願２００７−５４０８０１（Ｐ２００７−５４０８０１）
【出願日】平成１７年１１月９日（２００５．１１．９）
【国際出願番号】ＰＣＴ／ＩＢ２００５／０５３６９０
【国際公開番号】ＷＯ２００６／０５４２０８
【国際公開日】平成１８年５月２６日（２００６．５．２６）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成２０年６月１９日（２００８．６．１９）
【国際特許分類】
【出願日】平成１７年１１月９日（２００５．１１．９）
【国際出願番号】ＰＣＴ／ＩＢ２００５／０５３６９０
【国際公開番号】ＷＯ２００６／０５４２０８
【国際公開日】平成１８年５月２６日（２００６．５．２６）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]