JP5288935B2 - コード化および復号化前のバイオメトリックパラメータの前処理方法 - Google Patents

Description

関連出願
本願は、Ｄｒａｐｅｒ外によって２００６年１１月２９日に、「Ｂｉｏｍｅｔｒｉｃ Ｂａｓｅｄ Ｕｓｅｒ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ａｎｄ Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ（バイオメトリックに基づくユーザ認証とデータ暗号化）」という名称で出願された、米国特許出願第１１／５６４，６３８の一部係属出願であり、その米国特許出願１１／５６４，６３８は、また、Ｍａｒｔｉｎｉａｎ外によって２００５年９月１日に、「Ｂｉｏｍｅｔｒｉｃ Ｂａｓｅｄ Ｕｓｅｒ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ａｎｄ Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ（バイオメトリックに基づくユーザ認証とデータ暗号化）」という名称で出願された米国特許出願第１１／２１８，２６１（米国公開２００６−０１２３２４１）の一部係属出願であり、またその米国特許出願第１１／２１８，２６１は、Ｍａｒｔｉｎｉａｎ外により２００４年１２月７日に、「Ｂｉｏｍｅｔｒｉｃ Ｂａｓｅｄ Ｕｓｅｒ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｗｉｔｈ Ｓｙｎｄｒｏｍｅ Ｃｏｄｅｓ（シンドロームコードを有するバイオメトリックに基づくユーザ認証）」という名称で出願された米国特許出願第１１／００６，３０８（米国公開２００６−０１２３２３９）の一部係属出願である。

一般に、この発明は、暗号の分野に関連し、特に、ユーザ認証およびデータ暗号化のために、バイオメトリックパラメータを取得し、前処理し、コード化し、格納することに関する。

従来のパスワードベースのセキュリティシステム

従来のパスワードに基づくセキュリティシステムは、典型的に２つのフェイズ（段階）を含む。具体的には、登録段階の間、ユーザはパスワードを選択し、それらのパスワードはサーバなどの認証デバイスに格納（記憶）される。認証段階の間、リソースやデータへのアクセスを得るために、ユーザは彼らのパスワードを入力し、それらのパスワードは該パスワードの格納されたバージョンに対して検証される。パスワードがプレーンテキストとして格納されるなら、システムへのアクセスを得る敵対者は、あらゆるパスワードを得ることができるかもしれない。このようにして、単一の成功している攻撃でさえも、全体システムのセキュリティを危険に曝しうる。

図１に示されているように、従来のパスワードに基づくセキュリティシステム１００は、登録段階１０の間に、コード化１１０されたパスワード１０１をパスワードデータベース１２０に格納（記憶）１１１５する。具体的には、Ｘが格納１１５されるパスワード１０１であるならば、システム１００は実際にｆ（Ｘ）を格納し、ここでｆ（．）は或る暗号化すなわちハッシュ関数１１０である。認証段階２０の間、ユーザは候補パスワードＹ１０２を入力し、システムはｆ（Ｙ）を判別１３０して、ｆ（Ｙ）が格納されたパスワードｆ（Ｘ）に一致するとき、システムへのアクセス１５０を許可し、そうでなければ、アクセスは否定１６０される。

利点としては、暗号化されたパスワードは、通常、インバート（逆転、逆行）させることが非常に難しいので、暗号化関数なしでは、敵対者には役に立たない。

従来のバイオメトリックに基づくセキュリティシステム

バイオメトリックセキュリティシステムは、しばしば観測と呼ばれるバイオメトリックパラメータを得るため、肉体的なバイオメトリック特徴を計測する。従来のバイオメトリックセキュリティシステムには、暗号化されていないパスワードを格納する、パスワードに基づくシステムと同じような脆弱性がある。具体的には、データベースが暗号化されていないバイオメトリックパラメータを格納するならば、それらのパラメータは攻撃と誤用を被りやすい。

たとえば、顔認識システムまたは音声認識を使用するセキュリティシステムでは、敵対者は、該敵対者と同様のバイオメトリックパラメータを捜し求めることができるかもしれない。適当なバイオメトリックパラメータが見つけ出された後に、敵対者は、不正アクセスを得るために、該パラメータを変更して該敵対者の外観または声と一致するようにすることができるかもしれない。同様に、指紋或いは虹彩認識を使用するセキュリティシステムでは、敵対者は、不正アクセスを得るために、一致する指紋または虹彩を模造するデバイスを制作することができるかもしれない。たとえば、そのようなデバイスは、偽造の指または偽造の目である。

基本的なバイオメトリック特徴の変動可能性ばかりでなく、それらの特徴が測定される方法における変動可能性によっても、バイオメトリックパラメータを暗号化することが常に可能であるというわけではない。この変動可能性すなわち差を「ノイズ」と呼ぶことができる。

具体的には、バイオメトリックパラメータＸは登録段階の間に入力される。たとえば、パラメータＸが暗号化すなわちハッシュ化関数ｆ（Ｘ）を使用して暗号化されて、格納されるとする。認証段階の間に、同じユーザから得られたバイオメトリックパラメータは異なる場合がある。たとえば、顔認証を使用するセキュリティシステムでは、登録および認証のために使用されるカメラは、異なる方向、感度および分解能を持つことができる。通常、照明はかなり異なる。肌の色合い、ヘアスタイル、およびその他の顔の特徴は簡単に変えることができる。このようにして、認証の間に、新たに観測されたパラメータＹが同じ暗号化関数ｆに通されるならば、その結果ｆ（Ｙ）はｆ（Ｘ）と一致せず、拒否を引き起こすであろう。同様の問題は、虹彩および指紋パターンなどの他のバイオメトリックに基づくユーザ認証でも存在する。

誤り訂正符号（コード）

アルファベットＱ上の、（Ｎ、Ｋ）誤り訂正符号（ＥＣＣ）Ｃは長さＮのＱ^Ｋベクトルを含む。リニア（Ｎ、Ｋ）ＥＣＣは、Ｎ行Ｋ列の生成行列Ｇを使用するか、またはＮ−Ｋ行Ｎ列のパリティチェックマトリクスＨを使用することによって、説明できる。名称「生成行列」は、ベクトルｗとして表される符号語が、ベクトルｖにマトリクスＧを後から（右から）掛けることにより、すなわちｗ＝ｖＧにより、どんな長さＫの入力行ベクトルｖからも生成され得るという事実に基づいている。同様に、ベクトルｗが符号語であるかどうかをチェックするために、Ｈｗ^Ｔ＝０であるか否かチェックしてもよく、ここで、列ベクトルｗ^Ｔは行ｗの転置である。

誤り訂正符号の標準的用法では、入力ベクトルｖはベクトルｗにコード化（符号化）されて、格納されるか、或いは伝送される。ベクトルｗの崩壊した（間違いのある）バージョンが受信されるならば、デコーダは、エラーを修正するために、コードに冗長性を使用する。直観的に、コードのエラー修正能力はコードの冗長性の量に依存する。

スレピアンーウォルフ、ウイナージブ、およびシンドロームコード

ある意味で、スレピアンーウォルフ（ＳＷ）コードは誤り訂正符号の逆（反意語）である。誤り訂正符号は冗長性を加えてデータを拡大するが、ＳＷコードは冗長性を取り除いてデータを圧縮する。具体的に、ベクトルｘおよびｙは関連付けられたデータを表している。エンコーダが既にベクトルｙを持っているデコーダにベクトルｘを伝えることを望むならば、該エンコーダは、デコーダにはベクトルｙがあるという事実を考慮に入れて、データを圧縮することができる。

極端な例として、ベクトルｘおよびｙが１ビットだけ異なるならば、エンコーダは、単にベクトルｘおよび相違の位置を記載することにより、データの圧縮を実現することができる。勿論、より現実的な相関モデルに対しては、より高度なコードが要求される。

ＳＷコーディングおよび関連するウイナージブ（ＷＺ）コーディングの基本理論は、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ（情報理論に関するＩＥＥＥトランザクション）、Ｖｏｌ．１９、ページ４７１〜４８０、１９７３年７月発行の「Ｎｏｉｓｅｌｅｓｓ ｃｏｄｉｎｇ ｏｆ ｃｏｒｒｅｌａｔｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｏｕｒｃｅｓ（相関情報ソースの無雑音符号化）」において、スレピアンおよびヴォルフによって記載されているとともに、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、Ｖｏｌ．２２、ページ１〜１０、１９７６年１月発行の「Ｔｈｅ ｒａｔｅ−ｄｉｓｔｏｒｔｉｏｎ ｆｕｎｃｔｉｏｎ ｆｏｒ ｓｏｕｒｃｅ ｃｏｄｉｎｇ ｗｉｔｈ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ａｔ ｔｈｅ ｄｅｃｏｄｅｒ（デコーダでの副情報を有するソースコーディングに対する速度−歪み関数」において、ＷｙｎｅｒおよびＺｉｖによっても記載されている。より最近、プラダン（Ｐｒａｄｈａｎ）およびラムチャンドラン（Ｒａｍｃｈａｎｄｒａｎ）が、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、Ｖｏｌ．４９、ページ６２６〜６４３、２００３年３月発行の「Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｏｕｒｃｅ Ｃｏｄｉｎｇ Ｕｓｉｎｇ Ｓｙｎｄｒｏｍｅｓ （ＤＩＳＣＵＳ）：Ｄｅｓｉｇｎ ａｎｄ Ｃｏｎｓｔｒｕｃｔｉｏｎ（シンドロームを使用する分散型ソースコーディング：設計と構成）」において、そのようなコードの実用的な実用化について記載している。

本質的には、シンドロームコードは、Ｎ−Ｋ行Ｎ列を有するパリティチェックマトリクスＨを使用することによって、動作する。長さＮのバイナリ（２進）ベクトルｘを長さＫのシンドロームベクトルに圧縮するために、Ｓ＝Ｈｘを判定する。復号化は、しばしば、使用された特定のシンドロームコードの詳細に依存する。たとえば、シンドロームコードがトレリス（ｔｒｅｌｌｉｓ）に基づくならば、パラダン（Ｐｒａｄｈａｎ）外により記述されているように、シンドロームベクトルＳに対応する最も有望なソースシーケンスＸおよび副情報のシーケンスを見つけるために、周知のヴィテルビ（Ｖｉｔｅｒｂｉ）アルゴリズムなどの様々なダイナミックプログラミングに基づく検索アルゴリズムを使用できる。

或いはまた、低密度のパリティチェックシンドロームコードが用いられるならば、２００４年３月発行のＤａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ（データ圧縮カコンファレンス）の予稿集、ページ２８２〜２９１、「Ｏｎ ｓｏｍｅ ｎｅｗ ａｐｐｒｏａｃｈｅｓ ｔｏ ｐｒａｃｔｉｃａｌ Ｓｌｅｐｉａｎ−Ｗｏｌｆ ｃｏｍｐｒｅｓｓｉｏｎ ｉｎｓｐｉｒｅｄ ｂｙ ｃｈａｎｎｅｌ ｃｏｄｉｎｇ（チャネル符号化で鼓舞された実用的なスレピアンーウォルフ圧縮への幾つかの新アプローチ）」に、コールマン外により記載されているように、確率伝搬復号化を適用できる。

ファクター（要素）グラフ

従来技術では、上述したようなコードは、しばしば「ファクターグラフ」と呼ばれる２部グラフによって表される。Ｆ．Ｒ．Ｋｓｃｈｉｓｃｈａｎｇ、Ｂ．Ｊ．ＦｒｅｙおよびＨ．Ａ．Ｌｏｅｌｉｇｅｒ、「Ｆａｃｔｏｒ Ｇｒａｐｈｓ ａｎｄ ｔｈｅ Ｓｕｍ−Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍ（ファクターグラフと加算値積のアルゴリズム）」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、ｖｏｌ．４７、ページ４９８〜５１９、２００１年２月、およびＧ．Ｄ．Ｆｏｒｎｅｙ，Ｊｒ．、「Ｃｏｄｅｓ ｏｎ Ｇｒａｐｈｓ：Ｎｏｒｍａｌ Ｒｅａｌｉｚａｔｉｏｎｓ（グラフに関するコード：通常の実現」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、ｖｏｌ．４７、ページ５２０〜５４９、２００１年２月、およびＲ．Ｍ．Ｔａｎｎｅｒ、「Ａ Ｒｅｃｕｒｓｉｖｅ Ａｐｐｒｏａｃｈ ｔｏ Ｌｏｗ−Ｃｏｍｐｌｅｘｉｔｙ Ｃｏｄｅｓ（低複雑さコードへの反復アプローチ）」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、ｖｏｌ．２７、ページ５３３〜５４７、１９８１年９月、を参照。また、これらはすべて本明細書中に引用して援用される。

一般に、ファクター（要素）グラフは２部グラフであり、「可変ノード」および「ファクター（要素）ノード」と呼ばれる２つのタイプのノードを含んでいる。可変ノードはファクターノードに接続されるだけであり、また、逆も同様である。ファクターノードは慣習的に四角形を使用して描かれ、また、可変ノードは慣習的に円を使用して描かれ、また、可変ノードおよびファクターノードの間の接続は対応する円および四角形を接続する線によって表される。時々、符号（シンボル）、すなわち「＋」は、それが実行する制約条件の種類を表すために、ファクターノードの中に描かれる。

可変ノードはコードで使用される符号を表しており、またファクターノードはそれらの符号に対する制約条件を表している。可変ノードは該当する制約条件を受ける場合にだけ、ファクターノードに接続される。

バイオメトリックパラメータをコーディングする従来技術

この発明に関連する従来技術は３つのカテゴリになる。まず最初に、そのようなバイオメトリックパラメータの安全な格納に関係ない、特徴抽出、記録およびバイオメトリックパラメータの使用について記述している多くの従来技術がある。この発明は安全な格納に関係しており、主に、バイオメトリックパラメータをどのように取得するかに関する詳細には関わらないので、従来技術のこのカテゴリの詳細は省略される。

この発明に関連する２番目のクラスの従来技術は、安全な格納とバイオメトリックス（生物測定学）の認証のために設計された以下のシステムを含む。「Ｍｅｔｈｏｄ ａｎｄ ｓｙｓｔｅｍ ｆｏｒ ｎｏｒｍａｌｉｚｉｎｇ ｂｉｏｍｅｔｒｉｃ ｖａｒｉａｔｉｏｎｓ ｔｏ ａｕｔｈｅｎｔｉｃａｔｅ ｕｓｅｒｓ ｆｒｏｍ ａ ｐｕｂｌｉｃ ｄａｔａｂａｓｅ ａｎｄ ｔｈａｔ ｅｎｓｕｒｅｓ ｉｎｄｉｖｉｄｕａｌ ｂｉｏｍｅｔｒｉｃ ｄａｔａ ｐｒｉｖａｃｙ（公開データベースからユーザを認証するためにバイオメトリックなバラツキを正規化して、個々のバイオメトリックデータのプライバシーを保障する方法およびシステム）」、米国特許６，０３８，３１５；Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ，Ｍａｙ １９９８における、Ｄａｖｉｄａ，Ｇ．Ｉ．，Ｆｒａｎｋｅｌ，Ｙ．，Ｍａｔｔ，Ｂ．Ｊ．による「Ｏｎ ｅｎａｂｌｉｎｇ ｓｅｃｕｒｅ ａｐｐｌｉｃａｔｉｏｎｓ ｔｈｒｏｕｇｈ ｏｆｆ−ｌｉｎｅ ｂｉｏｍｅｔｒｉｃ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ（オフラインバイオメトリック認証で安全な応用を可能にすることについて）」；Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００２ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，Ｊｕｎｅ ２００２における、Ｊｕｅｌｓ，Ａ．，Ｓｕｄａｎ，Ｍ．，による「Ａ Ｆｕｚｚｙ Ｖａｕｌｔ Ｓｃｈｅｍｅ（ファジィボールトスキーム）」；２００１年１１月２６日に出願された米国特許出願第０９／９９４，４７６、「Ｏｒｄｅｒ ｉｎｖａｒｉａｎｔ ｆｕｚｚｙ ｃｏｍｍｉｔｍｅｎｔ ｓｙｓｔｅｍ（順序不変ファジィコミットメントシステム」；Ｐｒｏｃ． ５^ｔｈ ＡＣＭ Ｃｏｎｆ． ｏｎ Ｃｏｍｐ． ａｎｄ Ｃｏｍｍｕｎ． Ｓｅｃｕｒｉｔｙ，Ｎｅｗ Ｙｏｒｋ，ＮＹ，ｐｇｓ．２８−３６，１９９９における、Ｊｕｅｌｓ ａｎｄ Ｗａｔｔｅｎｂｅｒｇの「Ａ ｆｕｚｚｙ ｃｏｍｍｉｔｍｅｎｔ ｓｃｈｅｍｅ（ファジィコミットメントスキーム）」；Ａｓｉｌｏｍａｒ Ｃｏｎｆ． ｏｎ Ｓｉｇｎａｌｓ，Ｓｙｓｔｅｍｓ，ａｎｄ Ｃｏｍｐ．，ｖｏｌ．１，ｐｐ．５７７−５８１，Ｎｏｖｅｍｂｅｒ ２００４における、Ｓ．Ｙａｎｇ ａｎｄ Ｉ．Ｍ．Ｖｅｒｂａｕｗｈｅｄｅの「Ｓｅｃｕｒｅ ｆｕｚｚｙ ｖａｕｌｔ ｂａｓｅｄ ｆｉｎｇｅｒｐｒｉｎｔ ｖｅｒｉｆｉｃａｔｉｏｎ ｓｙｓｔｅｍ（安全なファジィボールトに基づく指紋照合システム」；Ｐｒｏｃ． Ｗｏｒｋｓｈｏｐ：Ｂｉｏｍｅｔｒｉｃｓ：Ｃｈａｌｌｅｎｇｅｓ ａｒｉｓｉｎｇ ｆｒｏｍ ｔｈｅｏｒｙ ｔｏ ｐｒａｃｔｉｃｅ，ｐｐ．１３−１６，Ａｕｇｕｓｔ ２００４における、Ｕ．Ｕｌｕｄａｇ ａｎｄ Ａ．Ｊａｉｎの「Ｆｕｚｚｙ ｆｉｎｇｅｒｐｒｉｎｔ ｖａｕｌｔ（ファジィ指紋ボールト」。

図２は、米国特許６，０３８，３１５に記載されている基本的方法の詳細の幾つかを示す。登録フェーズ（段階）２１０では、バイオメトリックパラメータが、Ｅで表されたビットのシーケンスの形式で取得２０１される。次に、ランダムな符号語Ｗ２０２が２進の誤り訂正符号から選択され、エクスクルーシブＯＲ（排他的論理和）関数２２０を使用してパラメータＥに加算的に結合されて、リファレンス（基準）Ｒを生成２２１する。任意ではあるが、リファレンスＲはさらにコード化２３０されうる。何れの場合でも、リファレンスＲはパスワードデータベース２４０に格納される。

認証段階２２０では、バイオメトリックパラメータＥ’２０５が認証のために提示される。その方法は、Ｅ’でＲのＸＯＲ（排他的論理和）を判定２５０し、これらの２つを減算してＺ＝Ｒ−Ｅ＝Ｗ＋Ｅ−Ｅ’を得る２５１。次に、この結果が誤り訂正符号で復号２６０されて、Ｗ’を生成２６１する。ステップ２７０で、Ｗ’がＷと一致するならば、アクセスが許可２７１され、そうでなければ、アクセスが拒否２７２される。

その方法は、本質的には、ハミング距離、すなわち登録されたバイオメトリックＥ２０１と認証バイオメトリックＥ’２０５との間で異なるビット数を測定する。その差が或る所定の閾値より小さいならば、アクセスが許可される。この方法は実際のバイオメトリックパラメータＥではなく、リファレンスＲだけを格納するので、安全である。

ダビダ外（Ｄａｖｉｄａ ｅｔ ａｌ．）およびジュエルス外（Ｊｕｅｌｓ ｅｔ ａｌ．）は、図２に示される方法の変形例を記述する。具体的には、両者とも、結果として得られる符号語を安全にする操作が後に続く登録段階の間、誤り訂正符号でバイオメトリックデータをコード化する。ダビダ外は、チェックビットを送るだけで符号語を隠し、他方、ジュエルス外は「チャフ」と呼ばれる幾らかの量のノイズを加算する。

「多因子のバイオメトリック認証デバイスおよび方法」という名称の米国特許６，３６３，４８５は、秘密鍵を生成するために、バイオメトリックデータと誤り訂正符号およびパスワードや個人識別番号（ＰＩＮ）などの或る秘密情報を結合するための方法について記載している。ゴッパコードやＢＣＨコードなどの誤り訂正符号が様々な排他的論理和操作で使われる。

図２に図示した固定データベースアクセス制御システムに加えて、３番目のクラスの従来技術は、データ保護、具体的には、ラップトップ、ＰＤＡ、携帯電話、およびデジタルカメラなどの、メモリを含むモバイル機器ためのデータ保護のための生体認証を使用することを含む。モバイル機器は容易に紛失したり、盗まれたりし易いので、モバイル機器に格納されたデータを保護することが必要になる。

従来技術に関する問題

図４は、データＤを格納するための現存する手法での問題を図示する。コード化プロセス４１０では、データＤを暗号化４４０して暗号文Ｃを生成４４１するために、バイオメトリックパラメータＰ４０２がユーザから得られ、キーとして使用される。バイオメトリックパラメータＰおよび暗号文Ｃの両方ともストリッジ４５０にセーブ（保存）される。ユーザがデータＤを解読４２０したがっているとき、バイオメトリックパラメータＰ’４６０がユーザから得られて、格納されたバイオメトリックパラメータＰ４０２と比較される。Ｐ’がＰと一致４７０するならば、システムはアクセスを許して、格納された暗号文Ｃを解読してデータＤを生成４０１するためにＰを使用し、さもなければ、データは解読されない４７１。

記憶媒体が危険にさらされていない限りでのみ、そのような従来のシステムは有効である。しかし、敵対者がそのようなメディア（媒体）へアクセスすることができるならば、敵対者はＰを得て、データを復号する。

第１に、ビットベースの従来の方法は疑わしいセキュリティ（安全性）しか提供しない。さらに、バイオメトリックパラメータは、バイナリ（２進）値の代わりに、しばしば実数或いは整数である。一般に、従来技術は、バイオメトリックパラメータが一様に分布しているランダムな（無作為の）ビットで構成され、格納されたバイオメトリックからこれらのビットを正確に判別するのが難しいと仮定する。実際には、バイオメトリックパラメータはしばしばバイアスをかけられており、これがセキュリティにネガティブに影響する。また、敵対者が格納されたバイオメトリックの大体（近似）のバージョンだけを再生したとしても、敵対者の攻撃により重要な害が引き起こされる場合がある。従来の方法は、敵対者がコード化されたバージョンから実際のバイオメトリックを推定するのを防止するように設計されていない。

たとえば、米国特許６，０３８，３１５は、ランダムな符号語Ｗを加算することによって、基準値Ｒ＝Ｗ＋Ｅが効果的にバイオメトリックＥを暗号化するという事実に頼る。ところで、その方法は劣悪なセキュリティを実現する。ＥをＲから再生する多くの方法がある。たとえば、ベクトルＥが１と等しいほんの数ビットを有するならば、ＲとＷの間のハミング距離は小さい。このようにして、誤り訂正デコーダは容易にＷをＲから再生することができるかもしれないし、したがってＥを再生することができるかもしれない。或いはまた、たとえば、符号語の分布が悪く、すなわちコードの重さスペクトルが小さくて、多くの符号語がすべてゼロベクトルの回りに群がるならば、敵対者はＲからＥの良い近似を得ることができるかもしれない。

第２に、疑わしいセキュリティに加えて、従来の方法は、格納されるデータ量を増大させるという実用的な不都合を有する。バイオメトリックデータベースがしばしば多数の個々のユーザのためのデータを格納するので、追加のストリッジ（記憶装置）によりシステムの費用と複雑さがかなり増大される。

第３に、多くの従来の方法は、高い計算量（複雑さ）を有する誤り訂正符号またはアルゴリズムを必要とする。たとえば、従来技術のリード−ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）およびリード−ミューラー（Ｒｅｅｄ−Ｍｕｌｌｅｒ）復号アルゴリズムは一般に、２次関数的な大きな計算量（複雑さ）を有し、また、しばしばコード化されたバイオメトリックの長さにおいて、より高位に（大きく）なる。

第４に、従来技術では既知のモバイルセキュリティシステム用の基本アーキテクチャに基本的な問題がある。図４に示されているようなモバイルセキュリティシステムは、それ自体が危険にさらされない場合にだけ、有効であり得る。ラップトップ上のモバイルセキュリティシステムの例に戻ると、敵対者がＰとＣが格納された媒体へ物理的にアクセスすることができない場合にだけ、セキュリティは有効であり得る。敵対者が、たとえばラップトップからハードディスクを取り外すことによって、そのようなメディアへアクセスすることができるならば、敵対者は、直ちに、Ｃを生成するのに使用された暗号化キーであったＰを得て、Ｃを解読できる。

従来のモバイルセキュリティシステムにおける主な困難は、ユーザのバイオメトリックパラメータに対応する暗号キーが、デバイスに格納されているということである。このようにして、デバイスが盗まれるならば、格納されたパラメータを使用することでデータを復号できる。

第５に、バイオメトリックス（生体認証）に特有のノイズ構造に対する、誤り訂正符号化またはシンドロームコード復号化を行うための良い方法がないので、或いは、該ノイズ構造をモデル化するまでの多くの考察も行われていないので、安全なバイオメトリック（生体測定認証）システムに関する殆どの従来技術は、無記憶な雑音モデルや、ノイズの本質を単純化しすぎて実際の運用条件を反映しない、他のモデルを使用している。すなわち、従来のモデルは、バイオメトリック特徴の時間とともに変動するダイナミックス（動力学）および取得と測定のプロセスを正確に表していない。その代わりに、それらのモデルは、ノイズが無記憶であり、空間的或いは時間的な構造も持っていないと仮定する。

しばしば、バイオメトリック特徴は、１つの計測から別の計測まで変動する。たとえば、指紋生体認証では、「マニューシャ（特徴；ｍｉｎｕｔｉａｅ）」点が設定された特徴集合（ｆｅａｔｕｒｅ ｓｅｔ）としてしばしば使用される。マニューシャ点の相対的な位置と方向は、登録および認証の間、かなり異なる場合がある。これにより、認証過程が複雑になる。この問題を解決するためのほとんどの簡単な試みは、非常に高次元であるために、実用化のためには非実用的であるモデルを使用する。

したがって、構造化されたノイズを含むバイオメトリックデータのためのモデルを提供することが望ましい。さらに、チャネルコードを使用してバイオメトリックパラメータを前処理し、前処理されたパラメータが符号化および復号化のために最適な形式を有するようにすることが望ましい。

たとえば、人間の顔、声、指紋、および虹彩から取得されるバイオメトリックパラメータは、ユーザ認証およびデータアクセス制御ために使用することができる。バイオメトリックパラメータは、通常連続しており、同じユーザに対しても、１つの読取りから次の読取りまでに変動することがあるので、パスワードで行われているように、ハッシュ化すなわち暗号化された形式でデータベースに格納することができない。たとえば、顔または指紋のサンプリングされた外観や、声の調子は時間経過とともに変化することがある。

この発明の実施の形態１では、バイオメトリックデータ、たとえばウイナージブまたはスレピアンーウォルフコーディングに基づくシンドロームコードを保護するために、シンドロームコードを使用する。我々がシンドロームベクトルと呼ぶシンドロームコード化の出力は、生のバイオメトリックデータの固有の変動性を許容しつつ、データベースに安全に格納することができる。

具体的には、この発明によるバイオメトリックシンドロームベクトルには、以下の特性がある。

第１に、シンドロームコードは元のバイオメトリック特性に関する情報を効果的に隠す、すなわち暗号化し、シンドロームデータベースが危険にさらされるとしても、格納されたシンドロームベクトルが、システムのセキュリティを回避する際に、ほとんど役に立たないようにする。

第２に、各バイオメトリックの２回目のノイズの混じった計測の場合でも、対応する格納されたシンドロームベクトルを復号して、元のバイオメトリックパラメータを生成して、該元のバイオメトリックパラメータで暗号化されたデータを解読することができる。

第３に、本シンドロームコーディング方法論は、ユーザ認証ために使用できる。

この発明の第２の実施の形態は、時間経過とともにバイオメトリック特徴の変動（バラツキ）により変動することがあるバイオメトリックパラメータであって、さらに、測定プロセスをモデル化するバイオメトリックパラメータを効率的にモデル化するための方法を記述する。

本方法により、バイオメトリック特徴の複数の読取りの間の関係を、計算上効率的に、正確に利用できる。特に、本方法により、現存する従来の方法よりも遙かに良く、そのようなバイオメトリック特徴のシンドローム復号化を成功裏に行うことができる。

実施の形態１では、バイオメトリックパラメータは１組のロジック条件にしたがって前処理されて、１組の所定の統計的性質を有するバイナリ（２進）表示を形成する。なお、統計的性質は我々が実現することを望んでいる目標特性であることに注意するべきである。

実施の形態１．
この発明の実施の形態は以下の構成部を含む：
バイオメトリックパラメータを安全に格納するためのシンドロームエンコーダとハッシュ化方法、バイオメトリックキーで暗号化されたデータを安全に格納するためのシンドロームコードに基づく暗号化方法、および前の２つの方法などの安全なバイオメトリック応用のために使用されるシンドロームコードを最適化する方法。

安全なバイオメトリックパラメータのためのシンドロームおよびハッシュ化方法

図３は、この発明によるシンドロームとハッシング（ハッシュ化）に基づくバイオメトリックセキュリティシステム３００を示している。ユーザのバイオメトリック特徴が、バイオメトリックパラメータ（データまたは観測）を得るために、測定される。この発明による方法は、圧縮されたシンドロームベクトルに生成するために、シンドロームコードでバイオメトリックパラメータを圧縮する。

従来の圧縮とは違って、シンドロームコードによって生成されたシンドロームベクトルのみから、元のバイオメトリックデータを再構成或いは近似することはできない。シンドロームベクトルおよび元のバイオメトリックパラメータのハッシュはバイオメトリックデータベースに格納される。

ユーザを認証するために、バイオメトリックパラメータが再び測定される。そのバイオメトリックパラメータは、元のバイオメトリックパラメータを復号するために、格納されたシンドロームベクトルに結合される。シンドローム復号化が失敗するならば、元のバイオメトリックパラメータが再生されず、また復号されたパラメータのハッシュは格納されたハッシュと一致しない。したがって、ユーザはアクセスを拒否される。シンドローム復号化が成功するならば、元のバイオメトリックパラメータのハッシュは復号されたパラメータのハッシュと一致し、それはユーザの真正性を証明する。ハッシュの役割は、ユーザエントリ制御を提供し、ユーザによって提供されたバイオメトリックパラメータが、元のバイオメトリックパラメータを正確に再構成することができるくらいに、充分に良いことを確認することである。シンドロームエンコーダとハッシュの両方とも多対１マッピングであるが、シンドロームコードは、元のバイオメトリックパラメータを再構成するのに有用な構造を有する。他方、ハッシュ関数は、たとえば、暗号のハッシュでもよいが、それは元のバイオメトリックを推定するのに役に立つ情報を提供しない。

登録フェーズ（段階）

登録段階３１０では、ユーザの肉体的（身体的）な特徴についてのバイオメトリックデータを取得する。たとえば、バイオメトリックデータは、顔の画像、スピーチ（音声）の録音、指紋の画像、または虹彩のスキャンから得られる。

以下、バイオメトリックデータとは、ユーザの身体的な特徴から感知され、測定され、または別の方法で取得された生のバイオメトリック信号のことを言及する。特徴はバイオメトリックデータから抽出される。特徴はｄ次元の特徴ベクトルに配設される。特徴ベクトルは登録バイオメトリックパラメータ３０１を形成する。様々な形式のバイオメトリックデータから特徴を抽出するための方法は、上述したように、当技術分野では周知である。特徴ベクトルのバイオメトリックパラメータへの変換および最適なシンドロームコードは以下に詳述する。

バイオメトリックパラメータＥ３０１は、登録シンドロームベクトルがＳ３３１を生成するために、シンドロームエンコーダ３３０を使用してコード化される。次に、登録ハッシュＨ３４１を生成するために、メッセージ認証符号すなわちハッシュ関数がバイオメトリックパラメータＥに適用３４０される。ハッシュ関数は、ＲＦＣ１３２１、１９９２年４月の「Ｔｈｅ ＭＤ５ Ｍｅｓｓａｇｅ Ｄｉｇｅｓｔ Ａｌｇｏｒｉｔｈｍ（ＭＤ５メッセージダイジェストアルゴリズム）」において、ロン リベスト（Ｒｏｎ Ｒｉｖｅｓｔ）により記述された周知のＭＤ５暗号ハッシュ関数でもよい。登録シンドロームベクトル−ハッシュペア（Ｓ、Ｈ）３３１、３４１はバイオメトリックデータベース３５０に格納される。

如何なるタイプのシンドロームコード、たとえば、上述したＳＷコードやＷＺコード、でも使用できる。この発明の好適な実施の形態では、いわゆる「反復−累積（ｒｅｐｅａｔ−ａｃｃｕｍｕｌａｔｅ）コード」から得られたコード、すなわち「積−累積（ｐｒｏｄｕｃｔ−ａｃｃｕｍｕｌａｔｅ）コード」および我々が「拡張ハミング−累積（ｅｘｔｅｎｄｅｄ Ｈａｍｍｉｎｇ−ａｃｃｕｍｕｌａｔｅ）コード」と呼ぶコードを使用する。

我々は一般に、これらを直列に連結された累積（ＳＣＡ）コードと言及する。一般的な意味における、これらのクラスのコードに関する詳しい情報ためには、以下を参照。Ｊ． Ｌｉ，Ｋ．Ｒ．Ｎａｒａｙａｎａｎ，ａｎｄ Ｃ．Ｎ．Ｇｅｏｒｇｈｉａｄｅｓ、「Ｐｒｏｄｕｃｔ Ａｃｃｕｍｕｌａｔｅ Ｃｏｄｅｓ：Ａ Ｃｌａｓｓ ｏｆ Ｃｏｄｅｓ Ｗｉｔｈ Ｎｅａｒ−Ｃａｐａｃｉｔｙ Ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ Ｌｏｗ Ｄｅｃｏｄｉｎｇ Ｃｏｍｐｌｅｘｉｔｙ（積累積コード：能力に近いパフォーマンスおよび低い復号化複雑さのクラスのコード）」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，Ｖｏｌ．５０，ｐｐ．３１−４６，Ｊａｎｕａｒｙ ２００４；Ｍ．Ｉｓａｋａ ａｎｄ Ｍ．Ｆｏｓｓｏｒｉｅｒ、「Ｈｉｇｈ Ｒａｔｅ Ｓｅｒｉａｌｌｙ Ｃｏｎｃａｔｅｎａｔｅｄ Ｃｏｄｉｎｇ ｗｉｔｈ Ｅｘｔｅｎｄｅｄ Ｈａｍｍｉｎｇ Ｃｏｄｅｓ（拡張ハミングコードを有する高速直列連鎖コーディング）」、ｓｕｂｍｉｔｔｅｄ ｔｏ ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｌｅｔｔｅｒｓ， ２００４；Ｄ．Ｄｉｖｓａｌａｒ ａｎｄ Ｓ．Ｄｏｌｉｎａｒ、「Ｃｏｎｃａｔｅｎａｔｉｏｎ ｏｆ Ｈａｍｍｉｎｇ Ｃｏｄｅｓ ａｎｄ Ａｃｃｕｍｕｌａｔｏｒ Ｃｏｄｅｓ ｗｉｔｈ Ｈｉｇｈ Ｏｒｄｅｒ Ｍｏｄｕｌａｔｉｏｎ ｆｏｒ Ｈｉｇｈ Ｓｐｅｅｄ Ｄｅｃｏｄｉｎｇ（高速デコーディングための上位変調によるハミングコードと累算器コードとの連結）」、ＩＰＮ Ｐｒｏｇｒｅｓｓ Ｒｅｐｏｒｔ ４２−１５６，Ｊｅｔ Ｐｒｏｐｕｌｓｉｏｎ Ｌａｂｏｒａｔｏｒｙ，Ｆｅｂ．１５，２００４。

Ｙｅｄｉｄｉａ，ｅｔ ａｌ．により２００４年８月２７日に出願された、「Ｃｏｍｐｒｅｓｓｉｎｇ Ｓｉｇｎａｌｓ Ｕｓｉｎｇ Ｓｅｒｉａｌｌｙ−Ｃｏｎｃａｔｅｎａｔｅｄ Ａｃｃｕｍｕｌａｔｅ Ｃｏｄｅｓ（直列連鎖累積コードを使用して信号を圧縮する）」という発明の名称の米国特許出願第１０／９２８，４４８が、引用によりここに援用されるが、これには、この発明によって使用されるようなＳＣＡコードに基づく、我々の好適なシンドロームエンコーダの動作が記載されている。

バイオメトリックパラメータ３０１ための我々のシンドロームエンコーダ３３０には、多くの利点がある。そのシンドロームエンコーダ３３０は整数値入力で作動することができる。対照的に、従来のエンコーダは一般的に２進値入力で作動する。シンドロームエンコーダは、バイオメトリックデータベース３５０のストリッジ（格納）要求条件を最小にするために、非常に高い圧縮率を有する。シンドロームエンコーダは、レート（ｒａｔｅ）適応型になるように設計できて、増加形式（漸増的）に作動することができる。

認証フェーズ（段階）

認証段階３２０では、ユーザからバイオメトリックデータを再び取得する。認証バイオメトリックパラメータＥ’３６０を得るために、特徴が抽出される。マッチ（一致）する登録シンドロームベクトルＳ３３１および登録ハッシュＨ３４１を見つけるために、データベース３５０が検索される。

この検索によりデータベース３５０のあらゆるエントリ（Ｓ−Ｈペア）をチェックすることができ、或いはまたヒューリスティック（発見的）に順序付けられた検索を使用して、マッチするエントリを見つけるプロセスを加速することができる。具体的には、データベースのｉ番目のシンドロームベクトル−ハッシュペアを（Ｓ_ｉ、Ｈ_ｉ）と表すならば、全数探索により最初に、シンドローム復号化をＥ’およびＳ_１に適用して、シンドロームデコーダ出力のハッシュをＨ_１と比較する。アクセスが拒否されるならば、同じプロセスが（Ｓ_２、Ｈ_２）で試みられ、次に（Ｓ_３、Ｈ_３）など、すべてのエントリが試みられるまで、或いはまた、アクセスが許可されるまで、実行される。

登録ユーザ名などのその他の情報が利用可能であれば、検索を加速できる。たとえば、登録ユーザ名のハッシュ（バイオメトリックパラメータのハッシュＨと混同すべきではない）は、登録段階の間、ペアＳおよびＨとともに格納される。次に、認証段階では、ユーザは認証ユーザ名を提供し、またシステムはその認証ユーザ名のハッシュを判別して、マッチ（一致）するハッシュ化登録ユーザ名でＳ−Ｈペアに対してデータベースを検索し、その結果得られたＳ−Ｈペアを有するＥ’を認証するよう試みる。

具体的には、シンドロームデコーダ３７０が登録シンドロームベクトルＳに適用され、この際、認証パラメータＥ’３６０は「副」情報として働く。シンドロームデコーダは、当技術分野では一般的に知られている。典型的には、確率伝播すなわちターボ符号を使用するデコーダは、低い複雑さで素晴らしいエラー復元力を持っている。シンドロームデコーダ３７０の出力は復号された登録パラメータＥ”３７１である。復号された値Ｅ”３７１は、シンドロームベクトルＳ３３１を生成するのに使用された元のバイオメトリックパラメータＥ３０１の推定値である。ハッシュ関数３４０は、認証ハッシュＨ’３８１を生成するために、Ｅ”３７１に適用される。

登録値および認証値Ｈ３４１およびＨ’３８１が互いに比較３９０される。それらの値が一致しないならば、アクセスは拒否３９２される。そうでなければ、値Ｅ”３８１は元のバイオメトリックＥ３０１にほぼ（実質的に）一致する。この場合、ユーザはアクセス３９１を許可されることができる。

また、ユーザを認証するため、復号されたパラメータＥ”３８１と認証バイオメトリックパラメータＥ’３６０とを直接比較してもよい。たとえば、Ｅ’およびＥ”が顔認識システムでバイオメトリックパラメータに対応するならば、顔の間の類似性を比較するための在来型アルゴリズムをパラメータＥ’およびＥ”に適用してもよい。

シンドロームに基づくデータ暗号化

図５は、データ５０１をコード化（符号化）５１０および復号化５２０するための方法５００を示している。コード化プロセス５１０では、第１のユーザから最初のバイオメトリックパラメータＰ５０２を得る。パラメータは、暗号文Ｃ５４１を生成するために、入力データＤ５０１を暗号化５４０するのに使用される。ところで、従来技術と対比して、第１のバイオメトリックパラメータＰはメ決してモリに格納されない。その代わりに、シンドロームエンコーダ５３０は、シンドロームベクトルＳ５３１を生成するために、第１のバイオメトリックパラメータＰをコード化し、また、ペア（Ｓ、Ｃ）が互いに関連付けられてメモリ５５０に格納される。この発明の実施の形態１では、入力データは、登録プロセスの間にユーザから取得された生のバイオメトリックデータである。

人が暗号文５４１を解読５２０したいと思うとき、第２のユーザからバイオメトリックパラメータＰ’５６０を取得する。格納されたシンドロームベクトルＣ５３１は、第２のバイオメトリックパラメータを使用してシンドローム復号化され、第３のバイオメトリックパラメータＰ”５７１を生成する。そして、第３のバイオメトリックパラメータＰ”は、出力データＤ’５０９を生成するために、暗号文５４１を解読５８０するのに使用される。明らかに、第２または第３のバイオメトリックパラメータが第１のバイオメトリックパラメータと一致しないならば、出力データＤ’５０９は入力データＤ５０１と一致しない。出力データは、第１のユーザと第２のユーザが正確に同一人である場合にだけ、入力データと一致するであろう。

この発明の実施の形態１では、前述と同様に、バイオメトリックパラメータのハッシュＨもまた格納できる。ハッシュ同士が一致するのをチェックすることにより、復号化が成功したことを確認する。ハッシュがなければ、セキュリティは維持されるが、デコーダは、復号化が成功したことを確認できない。多くの形式のソースデータには、不正確な復号化に起因するファイルは有用なものは何ら対応しないので、ハッシュは必要でない。

本方法には、以下の利点がある。敵対者がシンドロームベクトルおよび暗号文（Ｓ、Ｃ）へのアクセスを得たとしても、データを解読することができない。これは、シンドロームベクトルから暗号キー、すなわち第１のバイオメトリックパラメータＰを再生できないからである。また、シンドロームコードの誤り訂正特性により、第２のバイオメトリックパラメータＰ’が第１のバイオメトリックパラメータＰと若干異なっても、適切に設計されたシンドロームデコーダは、暗号キーＰ５０２として使用された第１のバイオメトリックパラメータと正確に同じ第３のバイオメトリックパラメータＰ”を成功裏に生成することができる。

シンドロームコード化は、バイオメトリックパラメータを安全に格納する効果的な方法を提供し、また、バイオメトリックな情報を安全に格納する他の方法にも適用できる。なお、バイオメトリックデータから特徴ベクトルを抽出できることに注意するべきである。したがって、上述したバイオメトリックパラメータのいずれも、対応する特徴ベクトルで代替することができる。

暗号化された形式でバイオメトリックパラメータを格納することの追加の利点は、これが、安全なバイオメトリックストリッジアプリケーション（バイオメトリック格納への適用）がバイオメトリック認識アプリケーション（バイオメトリック認識への適用）で使用されたものと異なる特徴ベクトルで作動するのを可能にすることである。たとえば、指紋認識システムは、しばしば指紋の画像から抽出された、いわゆる「マニューシャ（特徴：ｍｉｎｕｔｉａｅ）」に基づく特徴ベクトルを使用する。同様に、虹彩認識システムは、虹彩画像を１列のガボール（Ｇａｂｏｒ）フィルタに通過させることにより抽出された特徴を使用することもある。

多くの場合、バイオメトリック認識（たとえば、顔認証や指紋による本人確認）用の理想的な特徴ベクトルは、シンドロームコード化／復号化のための理想的な特徴ベクトルと異なる場合がある。多くの場合、これは、認識（ｒｅｃｏｇｎｉｔｉｏｎ）または確認（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）システムのための分類子、たとえば、ガウス混合モデル（ＧＭＭ）、或いはニューラルネットワーク、或いは隠れマルコフ（Ｍａｒｋｏｖ）モデルに基づく分類子、を訓練するためのプロセスは、シンドロームエンコーダやデコーダの確率伝搬デコーダとともに用いられるヒストグラムを訓練するために使用されるプロセスとは異なる特徴ベクトルを生成することによる。

図６は、入力バイオメトリックデータ６０１の暗号化されたバージョンを格納するための方法６００を示している。上述したように、バイオメトリックデータは、ユーザのバイオメトリック特性を測定或いは検知するのに使用される生の信号から得る。

アクセス制御システムの登録段階６１０では、たとえば、ユーザから最初のバイオメトリックデータＢ６０１を取得する。次に、最初のバイオメトリックデータＢ６０１から第１のバイオメトリックパラメータＰ６０２の特徴ベクトルを得る。第１のバイオメトリックデータＢは、暗号キーとして第１のバイオメトリックパラメータＰを使用して暗号化６４０され、暗号文Ｃ６４１を生成する。さらに、第１のバイオメトリックパラメータは、シンドロームコード化されて、シンドロームベクトルＳ６３１を生成する。そして、関連付けられたペア（Ｓ、Ｃ）がバイオメトリックデータベース６５０に格納される。

認証段階６２０では、ユーザから認証用の第２のバイオメトリックデータＢ’６６０を得る。この第２のデータは、第２のバイオメトリックパラメータＰ’６６１の特徴ベクトルを生成するのに使用される。そして、シンドロームデコーダ６７０は、第１のバイオメトリックパラメータを復号して、第３のバイオメトリックパラメータＰ”６７１を生成する。次に、第３のバイオメトリックパラメータをキーとして使用して暗号文Ｃを解読６８０して、第３のバイオメトリックデータＢ”６８１を生成する。その後、認証バイオメトリックデータＢ’および復号されたバイオメトリックデータＢ”をバイオメトリック認識法６９０のより比較して、特有の関数へのアクセスが許可されるか拒否されるかを判別する６９２。前述したように、第１および第３バイオメトリックデータが正確に同じである場合、すなわち最初および次のユーザが同じ人間である場合にだけ、アクセスが許可される。

別の変形例では、比較ステップは、バイオメトリックデータから抽出された特徴ベクトルを使用できる。それらの特徴ベクトルは、バイオメトリックパラメータと同じである必要はない。さらに、検証ステップは完全に異なるプロセスを使用できるので、比較されるそれら２つの特徴ベクトルは、ほぼ（実質的に）同じであればよい。このようにして、特徴ベクトルは、時間経過とともに特定のユーザを特徴付けるバイオメトリックデータの変動（バラツキ）における、より広い範囲を許容することができる。

我々は、図６に示されるプロセスの幾つかの利点を列挙する。認証システムは、ステップ６９０で従来の認識システムを使用できる。また、シンドロームエンコーダ／デコーダによって使用されるバイオメトリックパラメータＰおよびＰ’は、バイオメトリックな検証ステップ６９０によって使用されるパラメータまたは特徴ベクトルの如何にかかわらず選択できる。その上、シンドロームコード化はバイオメトリックパラメータを安全に格納する効果的な方法である。ところで、図６に示される方法は、バイオメトリックパラメータを安全に格納する他の方法にも適用できる。

安全なバイオメトリックパラメータのための最適のシンドロームコードの設計

一般に、バイオメトリックパラメータとバイオメトリック特徴とを保護するためにシンドロームコードを使用する際のセキュリティと精度との間には、トレードオフがある。具体的には、如何なるシンドロームコードのキーパラメタも、シンドロームベクトルにおけるビットの数である。多くのビットを有するシンドロームベクトルは、バイオメトリックデータに関するより多くの情報を伝達して、バイオメトリックデータにおけるノイズと変動を許容することをより容易にする。対照的に、より小さなシンドロームベクトルは、より少ない情報を敵対者に与えるが、エラーをより生じやすい傾向がある。

或る極端な場合、シンドロームベクトルの長さがその基礎となるバイオメトリックデータの長さとほぼ同じであるとき、元のバイオメトリックデータはシンドロームベクトルのみから正確に再生できるので、如何なる量のノイズも許容できる。勿論、この場合、シンドロームベクトルを得る敵対者はまたバイオメトリックデータを再生することができるので、システムのセキュリティを危険にさらすことになる。

それとは正反対に、非常に少ないビット数のシンドロームベクトルは、敵対者がそのシンドロームベクトルからバイオメトリックデータを再生できないという意味で、非常に良いセキュリティを提供する。しかし、この場合、登録バイオメトリックデータと認証バイオメトリックデータとの間の許容できる変動（バラツキ）は限定的である（小さい）。

明らかに、シンドロームに基づくエンコーダおよびデコーダは、セキュリティとバイオメトリック変動（バラツキ）に対する許容度とをバランスさせるシンドロームベクトルのための長さを選択するべきである。ところで、入念に設計されたシンドロームコードはエラー復元力を改善できる。

図１２に示されるように、以下の用語でシンドロームコードのデザインと動作について記述する。バイオメトリックデータ１２０１は、たとえば、顔や指紋の画像でよい。完全な特徴ベクトル１２０２はトレーニングバイオメトリックデータから抽出される。完全な特徴ベクトル１２０２はシンドローム特徴ベクトル１２０３まで減少される。シンドローム特徴ベクトルは、デザイナーがシンドロームコード化および復号化のために適切であると判断する、完全な特徴ベクトルの部分をキャプチャする。シンドローム特徴ベクトルからシンドロームベクトル１２０４をコード化するのに、シンドロームコードが使用される。シンドローム特徴ベクトル１２０３は図３においてバイオメトリックパラメータＥ３１０の役割を担い、一方、シンドロームベクトルはＳ３３１である。

バイオメトリック統計モデル

図１３は、この発明の実施の形態によるシンドロームコード１２０４および対応するデコーダ１２０５（すなわちエンコーダおよびデコーダ）を構成するためのプロセス１３００を示している。トレーニングバイオメトリックデータ１３０１を取得する。選択された特徴モデル１３０４のパラメータ１３０２を、トレーニングデータから決定１３１０する。コーデックに関して、特徴モデルは本質的には「ソース」モデルである。同様に、選択された測定モデル１３０５のパラメータ１３０３を１３２０決定する。測定モデルは、実質的には、「チャンネル」モデルである。そして、パラメータ１３０２−１３０３およびモデル１３０４−１３０５は、シンドロームコードおよび対応デコーダを構成するのに使用される。なお、チャネルモデルは計測プロセスにおける構造化ノイズに対処するように設計されていることに注意するべきである。このノイズはたとえば、異なる計測インスタンスで観測されるようなバイオメトリックデータの特徴における変化や、インスタンス間の特徴の挿入および削除によって引き起こされ得る。

機械学習の多くのツールは上記の設計プロセス（工程）で役立ち得るが、結果として得られるモデルがシンドロームコード化のために適切な「ハード」特徴ベクトルを有するので、この問題は、機械学習における多くのモデル化問題とは可成り異なる。「ハード」および「ソフト」特徴ベクトル間の相異について、以下で詳細に議論する。

図１２に示されるように、シンドローム特徴ベクトル１２０３は、シンドローム復号化を取り扱い易くするために、典型的には、減少されたサイズ（大きさ）である。シンドロームコードを構成するために、デンシティエボリューション（ｄｅｎｓｉｔｙ ｅｖｏｌｕｔｉｏｎ）を度数分布（ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ）に適用できる。シンドロームコードは、シンドロームベクトル１２０４をユーザ間に亘るバイオメトリック特徴における変動（バラツキ）に一致させるために、シンドローム特徴ベクトル１２０３の有限ブロック長などの特徴、或いは可変レートコードを使用する必要性、を考慮に入れるためにさらに洗練される。

シンドロームコードが構成されて選択された後に、以下に述べるように、繰り返しの確率伝搬デコーダを構成する。

量子化

図７に示されるプロセス１３００のインスタンス７００を詳しく述べる前に、先ず、認証のときに登録中および認証中のバイオメトリックデータの使用を区別する以下の用語を定義する。特徴ベクトルの量子化バージョンに言及するために「ハード」特徴ベクトルという用語を使用し、非量子化特徴ベクトル、または細かく量子化された特徴ベクトルのバージョンに言及するために「ソフト」特徴ベクトルという用語を使用する。

幾つかのバイオメトリックパラメータは、比較的大きな数値範囲に亘って、整数および実数を含むことができるため、量子化が使用されている。暗号化、キー発行、および他の認証プロセス（過程）は小さな範囲に亘って整数でベストに働く。

「ハード」特徴ベクトルと「ソフト」特徴ベクトルとを区分けする理由は、シンドロームベクトルが「ハードな」特徴ベクトルから得られるためである。したがって、「ハード」特徴ベクトルは通常、量子化される。対照的に、認証段階の間、シンドロームデコーダは、「ハード」特徴ベクトルを復号するために、シンドロームベクトルに「ソフト」特徴ベクトルを結合してもよい。したがって、「ソフト」特徴ベクトルは、量子化される必要がないか、またはシステムにおけるエラーを小さくするために異なるように量子化され得る。たとえば、ソフト特徴ベクトルの使用により、シンドロームデコーダは各特徴の最も可能性のありそうな選択の困難な決断より、むしろ各特徴の尤度（ｌｉｋｅｌｉｈｏｏｄｓ）を入力として取ることが可能になる。

一般に、バイオメトリックデータから完全な特徴ベクトルに抽出する複数の方法があり、また、完全な特徴ベクトルから「ハード」および「ソフト」特徴ベクトルを抽出する複数の方法がある。したがって、図１３のプロセスを各可能性に適用して、トレーニングの間、最も良い総合的な結果をもたらすシンドローム特徴ベクトル１３０４を選択する。

図７は、最適のシンドロームを構成するためのプロセス１３００のインスタンスの詳細を示しており、ここで、バイオメトリック特徴１３０４に対する統計モデルはバイオメトリック特徴の間のマルコフ関係を表す。トレーニングバイオメトリックデータを取得８００する。バイオメトリックデータは、エラーヒストグラム８９０を生成するのに使用される。エラーヒストグラムはシンドローム特徴ベクトルを選択９００するのに使用される。このような関係において、すべてのバイオメトリックパラメータを表すのに「完全な特徴ベクトル」１２０２（図１２を参照）という用語を使用し、また、完全な特徴ベクトルの部分集合を表すのに「シンドローム特徴ベクトル」１２０３という用語を使用する。シンドローム特徴ベクトルを任意の特徴空間に変形することができる。

シンドローム特徴ベクトル１２０３が選択された後に、私たちはシンドローム特徴ベクトルの異なる係数の間の相関関係を測定１０００する。次に、シンドローム特徴ベクトルと係数間相関関係に対するエラー統計を使用することによって、デンシティエボリューション７４０を適用して、所与の長さの最適のシンドロームコード１２０４をもたらす度数分布を検索する。シンドローム特徴ベクトルおよびシンドロームコードが選択された後に、係数間相関関係を利用する確率伝搬デコーダを構成１１００する。

エラーヒストグラムを構成する

図８は、エラーヒストグラム８９０を生成するためのプロセス８００を示している。最初に、異なる機会に採られた特定のユーザのためのトレーニングバイオメトリックデータを取得８１０する。次に、一対のバイオメトリックパラメータＢおよびＢ’を選択８２０して、完全な「ソフト」特徴ベクトルＶＳ（Ｂ）８３０および完全な「ハード」特徴ベクトルＶＨ（Ｂ’）８４０を決定する。そして、完全な特徴ベクトルの中の各特徴または寸法（ｄｉｍｅｎｓｉｏｎ）ｉに対して、位置ｉのＶＳ（Ｂ）から対応する特徴ｉにおけるＶＨ（Ｂ’）の値を推定８４５し、その推定値が正しいか否かを判定８５０する。その推定値が正しくなければ、エラーヒストグラム８９０における特徴ｉでのＶＨ（Ｂ’）およびＶＳ（Ｂ）の対応する値に対する階級（ｂｉｎ）をインクリメントする。各特徴ｉに対してこの過程を完了した後に、すべてのペアのバイオメトリクス（生体認証）ＢおよびＢ’が処理されたか否かをチェック８６０する。そうでなければ、ステップ８２０に戻って、別のペアのバイオメトリックパラメータを選択する。すべてのペアが既に処理されていれば、エラーヒストグラムが完了し、本プロセスは終了８８０する。

シンドローム特徴ベクトルの選択

図９は、図８のエラーヒストグラムの支援によりシンドローム特徴ベクトルを選択するためのプロセス９００を示している。まず最初に、エラーヒストグラムは信頼性の最も高い特徴から最も低い特徴９２０へソート（並べ替え）される。具体的には、Ｅ（ｉ）がＶＳ（Ｂ）の特徴ｉからＶＨ（Ｂ’）の特徴ｉを予測するさいの平均誤差であるならば、特徴ｉは、Ｅ（ｉ）＜Ｅ（ｊ）のときに、特徴ｊよりも信頼できると考えられる。エラーヒストグラムがソートされた後に、エラーヒストグラムから次に最も信頼できる特徴をシンドローム特徴ベクトルに含めて９３０、現在のシンドローム特徴ベクトルに対する最も良いシンドロームコードを構成し９４０、最新の特徴を含めることがセキュリティすなわちエラー復元力を増大させるか否かをテスト９５０する。セキュリティすなわちエラー復元力が増大するならば、シンドローム特徴ベクトルに付加的な特徴を追加し続ける。さもなければ、特徴ベクトルから最も最近に加算された特徴を取り除き９６０、そして、本プロセスを終了９７０する。

セキュリティのレベルを特定して、エラー復元力を最適化することを望むならば、ステップ９４０および９５０に対して以下のステップを使用できる。まず最初に、ステップ９４０で、ｋシンドロームを有する低密度パリティチェック（ＬＤＰＣ）コードを固定度数分布から生成することによって、特徴ベクトルの中の現在の特徴の数に対応する長さＮの新しいシンドロームコードが構成される。この場合、セキュリティのレベルは、数量Ｎ−ｋを固定して、且つ本プロセス中それを一定に保っことによって一定に保たれる。そして、バイオメトリックデータのランダムなバイオメトリックサンプルがデータベースから選択され、ＬＤＰＣコードのパリティチェックマトリクスを適用することによって、シンドロームベクトルへマッピングされ、この結果得られたシンドロームベクトルは、同じユーザからの別のランダムなバイオメトリックサンプルに適用された確率伝搬を使用して復号される。これを何回も繰り返すことにより、与えられた特徴ベクトルに対するシンドロームコードのエラー復元力の推定値を生成する。或いはまた、計算上の更なる複雑さが設計プロセス（工程）で許容できるならば、そのコードに対する度数分布を最適化して、より精度よく誤り確率を推定するためにデンシティエボリューションプロセスを使用できる。これに関して、Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ，Ｍ．Ａ．Ｓｈｏｋｒｏｌｌａｈｉ，ａｎｄ Ｒ．Ｌ．Ｕｒｂａｎｋｅ，ｄｉｓｃｕｓｓｅｄ，「Ｄｅｓｉｇｎ ｏｆ ｃａｐａｃｉｔｙ−ａｐｐｒｏａｃｈｉｎｇ ｉｒｒｅｇｕｌａｒ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，Ｖｏｌｕｍｅ ４７，Ｉｓｓｕｅ ２，ｐｐ．６１９−６３７，Ｆｅｂｒｕａｒｙ ２００１を参照。なお、この文献は引用によりここに援用される。

エラー復元力のレベルを特定して、最高のセキュリティを得ることを望むならば、ステップ９４０および９５０に対して以下のステップを使用できる。まず最初に、ステップ９４０では、特徴ベクトルの中で現在の特徴の数に対応する長さＮの新しいシンドロームコードが、デンシティエボリューションを使用して、設計される。具体的には、デンシティエボリューションによって評価されるように、エラー復元力の特定のレベルを満たす最も高いレートコードが見つかるまで、デンシティエボリューションを使用して、一連の異なるレートコードが構成される。

このプロセスによって選択された特徴ベクトルは、そのシンドロームコードのために特別に設計された特徴ベクトルであるため、「シンドローム特徴ベクトル」として言及される。なお、この特徴ベクトルは、顔或いは物体の認識などのバイオメトリック認識のために構成された他のタイプの特徴ベクトルとは異なる特性を持つことができることに注意すべきである。

係数間相関関係を測定する

シンドローム特徴ベクトルが選択された後、次のステップは、データが互いに相関すると信じられるならば、その係数間相関関係を測定することである。図７によりエラーヒストグラムは完全な特徴ベクトル１２０２に対して生成されたものなので、そのエラーヒストグラムからこの情報を抽出することはできない。ステップ９００は、シンドローム特徴ベクトル１２０３を生成するために、完全な特徴ベクトルの中の特徴の部分集合だけを選択する。

図１０は、バイナリ（２進の）シンドローム特徴ベクトルにおける一次相関関係を測定するためのプロセス１０００を示している。このプロセスはまた、非バイナリ特徴ベクトルまたは高次相関に適用できる。まず最初に、バイオメトリックトレーニングデータセットから要素が選択され、そして、シンドローム特徴ベクトルがその要素から抽出される。それから、カウンタ変数ｉがゼロに初期化１０１０される。次に、特徴ｉが０であるか１であるかを検査して、前者（すなわち０）の場合にはステップ１０３０へ進み、後者（すなわち１）の場合にはステップ１０４０へ進む。その後、特徴ｉ−１、すなわち１つ前の特徴、が０であったか１であったかを検査して、ヒストグラム中の適切な階級（ｂｉｎ）をインクリメント（増分）１０３５する。直観的には、階級ｐ００はａ０が後続するａ０の出現を計数し、また、階級ｐ０１はａ１が後続するａ０の出現を計数する、などである。次に、カウンタｉを増分１０５０し、更なる（処理されていない）特徴がシンドローム特徴ベクトルに残っていないか検査１０６０して、次の特徴に対して本プロセスを繰り返す。そうでなければ、すなわち各特徴を既に処理していれば、本プロセスを終了１０７０する。

図１０のプロセスがバイオメトリックトレーニングセット（生体認証訓練集合）の各要素に対して実行された後、シンドローム特徴ベクトルの一次相関関係を測定するために、階級ｐ００、ｐ０１、ｐ１０、およびｐ１１の値を該バイオメトリックトレーニングセットのサイズ（大きさ）で除算する。

最適のシンドロームコードを構成するためにデンシティエボリューションを使用する

シンドローム特徴ベクトル１２０３が選択されて、係数間相関関係が測定された後、デンシティエボリューションを使用してシンドロームコード１２０４を設計する。具体的には、ＬＤＰＣシンドロームコードに対して、シンドロームコード用の度数分布を設計する。

実際に最適度分布を構成するために、デンシティエボリューション技術を適用して幾つかの候補度数分布を生成する。

ところで、当技術分野で知られているような従来のデンシティエボリューションプロセスは係数間相関関係を考慮していない。したがって、デンシティエボリューションによって生成された候補度数分布は、係数間相関関係がないケースに対して適切であるかもしれないが、係数間相関関係が存在するときには、一般的には、異なった振る舞い方をする。

シンドロームコードに対して最も良い度数分布を得るために、バイオメトリックトレーニングデータセットでデンシティエボリューションによって得られた候補度数分布同士を比較して、最善に振る舞う度数分布を選択する。代わりの実施の形態では、係数間相関関係を考慮に入れるように、従来のデンシティエボリューションアルゴリズムを変更する。

シンドロームコードに対する確率伝搬デコーダを構成する

シンドロームコードを設計する際の最終的なステップは、関連付けられた確率伝搬シンドロームデコーダ１２０５を構成することである。

図１１Ａは登録段階のハイレベル構造を示しており、ここで、エンコーダ３３０は、シンドロームコード１１０２を使用して、シンドローム特徴ベクトル１２０３からシンドロームベクトル１２０４を生成する。

図１１Ｂは、認証段階の間に使用される相補型（ｃｏｍｐｌｅｍｅｎｔａｒｙ）デコーダ１１０７に対する構造を示している。再び、認証を試みるユーザについてバイオメトリックデータ１１０４のノイズの入った観測が取得される。元のシンドローム特徴ベクトル１２０３の推定値１１０８を復号１１０７して生成するために、バイオメトリックデータ１１０４は、その測定モデル１３０５（および測定モデルパラメータ１３０３）とともに、反復確率伝搬ネットワーク（ファクタ（要素）グラフ）におけるシンドロームベクトル１２０４および特徴モデル１３０４（およびその特徴モデルのパラメータ１３０２）とともに使用される。復号化が成功するならば、推定されたシンドローム特徴ベクトル１１０８と元のシンドローム特徴ベクトル１２０３とは一致する。

図１１Ｃに示されるように、我々の確率伝搬ファクターグラフの構成１１００は、シンドロームコード１１０２および可変ノード（＝）１１２０を特定するチェックノード（＋）１１１０に加えて、特徴モデル１３０４（およびモデルパラメータ１３０２）を特定する相関関係ノード（Ｃ）１１３０を含む。具体的には、相関関係ノードは各ペアの連続した可変ノードの間に加えられる。可変ノードから隣接するチェックノードまでメッセージを流通させる方法は、他のメッセージで乗算される、各隣接相関ファクターノードからの追加メッセージを含むように変更される。

具体的には、Ｋｓｃｈｉｓｃｈａｎｇ外の表記を使用して、μ_ｙ→ｆ（ｘ）がチェックｆから可変ノードｙへの状態ｘに対する入力メッセージであり、Ｌ（ｘ）が左の相関関係ノードからの入力メッセージであるならば、可変ノードから右の相関関係ノードへの出力メッセージは、次式で表される。
Ｌ（ｘ）・Πμ_ｙ→_ｆ（ｘ），
一方、左の相関関係ノードへの出力メッセージは次式で表される。
Ｒ（ｘ）・Πμ_ｙ→_ｆ（ｘ），
ここで、Ｒ（ｘ）は右の相関関係ノードからの入力メッセージである。

また、この発明の実施の形態による、メッセージを相関関係ノードに対して流通（入出力）する方法についても記述する。具体的には、メッセージＬ（ｘ）およびＲ（ｘ）を判別するための処理手順について記述する。μ（０）が左の相関関係ノードへの入力メッセージであるならば、その相関関係ノードの右側への出力メッセージ、すなわちその相関関係ノードの右側の可変ノードへの入力メッセージ、は次式で表される。
Ｌ（０）＝ｐ００・μ（０）＋ｐ１０・μ（１） ａｎｄ Ｌ（１）＝ｐ１０・μ（０）＋ｐ１１・μ（１），
ここで、ｐ００、ｐ０１、ｐ１０、およびｐ１１の項は、図１０に示されるように、測定された一次相関関係値である。

同様に、その相関関係ノードの左側の出力メッセージ、すなわちその相関関係ノードの左の可変ノードへの入力メッセージ、は次式で表される。

Ｒ（０）＝ｐ００・μ（０）＋ｐ０１・μ（１） ａｎｄ Ｒ（１）＝ｐ０１・μ（０）＋ｐ１１・μ（１）．

虹彩バイオメトリックパラメータに対するシンドロームコード設計

次に、処理手順７００の虹彩バイオメトリックパラメータの特定のケースへの適用について記述する。完全な「ハード」特徴ベクトルは、「Ｈｏｗ ｉｒｉｓ ｒｅｃｏｇｎｉｔｉｏｎ ｗｏｒｋｓ」，ｂｙ Ｊ．Ｄａｕｇｍａｎ ｉｎ ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ，Ｖｏｌｕｍｅ １４，Ｉｓｓｕｅ １，Ｊａｎ．２００４ ｐａｇｅｓ ２１−３０に記述されるように、１組のガボールフィルタから抽出されたビットのシーケンスであるように選択される。この文献は引用によりここに援用される。

完全な「ハード」特徴ベクトルはバイナリ（２元）であるが、完全な「ソフト」特徴ベクトルはクオターナリ（４元）であるように選択される。具体的には、特徴ｉの完全な「ソフト」特徴ベクトルの値は、その特徴が「ハード」特徴ベクトルにおいて最良の推測であるように選択され、また信頼レベル（信頼度）を示すビットが追加される。詳細には、その特徴に対する判定に自信があるか、または自信が無いかを示すビットが追加された。

たとえば、「ハード」特徴ベクトルの幾つかの特徴は、予測するのが難しいかもしれない。その理由は、たとえば、それらの特徴が、瞼或いは睫毛よって覆われて、「自信が無い」という信頼度数値を受けるべきであるからである。

次に、図８について上述したように、エラーヒストグラムを作成するために、バイオメトリックトレーニングデータを使用し、それから図９の特徴ベクトル設計方法を適用する。完全な特徴ベクトルは約１万の長さを有するが、我々は、多くの特徴１２０２が信頼できないことを発見した。たとえば、目の上端に対応する特徴ベクトルの構成要素はしばしば瞼または睫毛で覆われる。最も信頼の低い特徴が図９の処理手順によって捨てられた後、シンドローム特徴ベクトル中のおよそ２，０００の最も信頼できる特徴が残される。

図７におけるステップ９００で処理を止めると、結果として得られるシンドロームベクトルは、単一ユーザに対する虹彩バイオメトリックパラメータにおける自然な変動（バラツキ）を許容しうるようなエラー復元力を有さないであろう。具体的には、或る日に採られたユーザの虹彩の計測が異なる日に採られ同じ虹彩からの計測に結合された状態でコード化されたシンドロームベクトルは、その時の約１２％の復号に失敗する。これは、図７における残りのステップに対する必要性を正当化する。

図１０の手続きを使用して一次相関関係を測定した後、我々は、「ハード」シンドローム特徴ベクトルにおける或るビットが隣接ビットと同じ値を取る見込み（可能性）が、該隣接ビットの反対の値を取る見込み（可能性）の約２倍であることを検出した。そして、我々は、高い相関関係を利用するために、図７のステップ７４０を続けて、デンシティエボリューションを使用して最適化されたシンドロームコードを構成した。最終的に、高い一次相関関係を考慮に入れるために、ステップ１１００にしたがって確率伝搬デコーダを構成した。

これらのステップに従うことにより、我々の初期のコードより１桁以上も信頼できるシンドロームコードを生成でき、したがって、図７の全体の手続きに従う利点を実証することができる。

指紋特徴に対するシンドロームコード

手続き１３００を指紋に適用する。指紋に基づくシステムは、一般に、パターンに基づくか、或いはマニューシャ（特徴）に基づく。ここでは、後者を使用する。指紋マニューシャから特徴ベクトルを抽出する。一般的な手順１３００を殆どのバイオメトリックデータに適用できるが、我々は、指紋のマニューシャに対する手続きの詳細について記述する。指紋マニューシャは、その特性として、時間経過とともに変動することがあり、また、計測プロセスは構造化ノイズを受け易い。

図１４は、一例の指紋１４０１および抽出された特徴ベクトル１４０２を示している。抽出された特徴ベクトル１４０２はシンドローム特徴ベクトル１２０３の一例である。特徴は計測フィールド（観測窓）１４０３で測定されるのみである。便宜上、マニューシャは格子状の四角形で示される。各マニューシャはトリプレットにマッピングされ、たとえば、（ａ、ｂ、ｃ）は空間的な位置座標（ａ、ｂ）とマニューシャの角度（ｃ）を表す。以下に述べるように、１つのマニューシャはアラインメント（位置合わせ、整列）の目的のための「コア」として指定することができる。

指紋１４０１が測定される平面はピクセルのアレーを有するディジタルセンサによって量子化されるので、特徴はマトリクスとして格納される。各センサーピクセルはマトリクス１４０２における特定のエントリに対応している。マニューシャの存在（有ること）は「１」により表されるが、検知されたマニューシャの欠如（無いこと）はマトリクス１４０２において「０」で表される。より一般的な表示では、マニューシャの存在を意味する「１」の代わりに、マトリクスにおけるエントリはマニューシャの角度ｃであろう。

マニューシャの数、位置、および角度は指紋の或る計測から次の計測までに変化する。たとえば、或る計測で（７４、５２、３６^ｏ）にマニューシャが存在すれば、別の計測では、それは（８０、４５、６３^ｏ）として現れるかも知れないし、或いは全く現れないかも知れない。

様々な理由により、或る計測から次の計測までのマニューシャのこの変動性は、指紋を処理するための多くの従来の方法に対して問題を生じさせる。

明白なバイオメトリックデータの変動性

図に１５Ａ−１５Ｃに示されているように、我々のモデルはバイオメトリックデータにおける変動性に対処することができる。これらの図では、破線１５００はローカル（局所的）な近傍を示す。図１５Ａはマニューシャの運動１５０１（ｐｉ、ｊ）を示している。図１５Ｂは削除ｐｅ１５０２を示しており、また、図１５Ｃは挿入ｐｓを示している。

図１６Ａおよび１６Ｂは、この発明の実施の形態による確率伝搬復号化１１０７を実施するために使用されるファクターグラフ１６００の高レベルおよび低レベルの詳細をそれぞれ示す。

高レベルでは、バイオメトリックデータ１２０１は、シンドロームベクトル１２０４を生成するために使用されるシンドローム特徴ベクトル１２０３を生成するために使用される。しかし、シンドローム特徴ベクトル１２０３はデコーダにより知られていないが、シンドロームベクトル１２０４は知られている。シンドロームベクトル１２０４とシンドローム特徴ベクトル１２０３とは、コード構造１６２３によって関連付けられる。また、デコーダはバイオメトリックデータ１１０４のノイズの入った計測を得る。雑音構造は統計モデル１３０５により記述される。シンドロームベクトル１２０３とともに、コード構造１６２３、観測１１０４および測定モデル１３０５は、復号１１０７を行って、元のシンドローム特徴ベクトル１２０３の推定値１１０８を生成するために使用される。

図１６Ｂはシンドローム特徴ベクトル、シンドロームベクトルおよびノイズの入った観測の統計モデルを記述するファクターグラフ１６００の低レベル構造を示している。

特徴ベクトルグリッド（格子）１４０２の各位置ｔは、ファクターグラフ１６００における対応するバイナリ確率変数ｘ［ｔ］ノード１６０９を有する。この確率変数は登録の間、位置ｔに存在し、それ以外はゼロである、１つのマニューシャである。

特徴ベクトルの格子位置とラベルｔとの関連付けは任意であり得る、たとえば、ラスタス−キャン順序でもよい。特徴集合の２次元的性質は、我々のモデルでも考慮に入れられる。

各格子位置に対して、マニューシャが登録の間存在しているという事前確率がある。この事前確率、Ｐｒ［ｘ［ｔ］＝１］、はファクターノード１６０８により表される。

その登録格子に対する可変ノード１６０９の各位置に対して、対応する認証格子に対する対応位置ノード１６０１がある。認証の間の格子位置ｔにおけるマニューシャの存在はバイナリ（２進）確率変数ｙ［ｔ］によって表される。マニューシャがプローブに存在していれば、この変数は１と等しく、そうでなければ、ゼロに等しい。ファクターグラフの目標は、登録時の指紋の最初の計測と認証時の２番目の計測との同時分布を表すことである。

我々のモデルでは、各登録位置は、ｘ［ｔ］＝１の場合、位置ｔのマニューシャがプローブ内の位置ｔの近傍の位置へ移動する確率を持っているか、或いはまた、削除の場合には、測定されない。

変数１６０４は登録マニューシャの位置の相対変化を表し、また、ファクターノード１６０３は挿入されたマニューシャの移動および確率に関する事前確率分布を表す。特に、図１６Ｂに示された１次元の移動モデルに対して、ｚ［ｔ］＝ｉは、登録時の位置ｘ［ｔ＋ｉ］のマニューシャが認証時に位置ｚ［ｔ］へ移動することを表す。より一般には、そして我々の実施では、２次元移動モデルを使用する。

このような変位（移動）｛ｉ｝のドメインまたは近域（ｎｅｉｇｈｂｏｒｈｏｏｄ）は、破線１５００で表す設計パラメータである。変数ｚ［ｔ］＝ｓであれば、偽マニューシャが認証時に位置ｔに挿入され、また、ｚ［ｔ］＝＊は、認証時にマニューシャが位置ｔ存在しないことを示す。ｚ［ｔ］＝＊などのような変数ｚ［ｔ］とｙ［ｔ］＝０などのような変数ｙ［ｔ］との間には、正確な対応がある。

位置ｔの登録マニューシャ、すなわちｘ［ｔ］＝１、は、ｔの近傍におけるたかだか１つの観測されたマニューシャについて説明できるだけであるという制約条件を表すために、我々はファクターノード１６０７を含める。これらのノードに接続される確率変数ｈ［ｔ］１６０６は、ｘ［ｔ］の削除を表すバイナリ変数である。削除は、検知されなかった或いは抽出されなかったマニューシャ、または登録時に検知された偽のマニューシャ、または大きな移動から生じ得る。ノード１６０５は各ｈ［ｔ］に対する事前分布を表す。

各ノードｙ［ｔ］をその対応ノードｚ［ｔ］に接続するファクターノード１６０２は、該対応ノードｚ［ｔ］が＊でない場合にのみ、各認証マニューシャｙ［ｔ］がノンゼロでなければならないという概念を表す。

このモデルに、シンドロームコード１１０２から生じる制約条件を加える。各シンドロームノードｓ［ｉ］１６１１はローカルコード制約条件１６１０を満し、その制約条件１６１０は、シンドロームの値が特徴ベクトルｘ１、ｘ２、…に適合する場合には１に等しく、そうでなければ、ゼロに等しい特性関数である。

それらのマニューシャの方位をファクターグラフに加えることができる。方位情報を加えるために、登録ノード１６０９はマニューシャについて位置ｔと方位の両方を示す。また、この情報は事前確率ノード１６０８に反映される。登録時の方位をシンドロームコード化に必要なハード特徴ベクトルに適合させるために、該登録時の方位は量子化される。

シンドロームビット１６１１のベクトルは、以上と同様にコード化されるが、今度は、マニューシャの存在の有無およびもし存在すれば、その方位を表す登録変数１６０９のベクトルからである。削除１６０５の事前確率は、移動に関する制約条件１６０７と同様に、変化しないままである。移動と挿入１６０４の事前確率も変化しないままである。認証ノード１６０２上の制約条件ノードは、登録ノード１６０９と認証ノード１６０１との間の方位の変化がより少なるであろうという概念を反映するように変更される。

メッセージ通過規則と最適化

ファクターグラフ１６００によって表される計測および移動モデルを考えると、従来からの技術を使用することによりメッセージ通過規則を導き出すことができる。以下、複雑さの減少を実現するために、メッセージを通過させるための幾つかの簡素化について記述する。

第１の簡素化は制約条件ノード１６０２からのメッセージに関連する。私たちは、観測されないマニューシャを取り除くためにファクターグラフから「余分なものを取り除く」。具体的には、制約条件１６０２の形式にしたがって、ｙ［ｔ］＝０であるなら、ノード１６０２からｚ［ｔ］可変ノード１６０４への唯一のノンゼロメッセージは状態ｚ［ｔ］＝＊に対するものである。

その結果、隣接するノード１６０７に送られる唯一のノンゼロメッセージｚ［ｔ］は、＊状態に対するものである。我々は、この一定のメッセージが１に正規化されると仮定することができる。たとえば、ｙ［ｔ］＝ｙ［ｔ＋２］＝ｙ［ｔ＋４］＝ｙ［ｔ＋５］＝＊であれば、図１６Ｂの完全なファクターグラフを使用する代わりに、必要なメッセージ通過作用を導き出すために、図１７に示すように、余分なものを取り除いたグラフ１７００を使用する。これは、ノード１６０７に対するメッセージ計算の複雑さを大幅に減少させることに通じる。

ファクターノード１６０７に出入りするメッセージを演算することによって、第２の簡素化が得られる。ｚ［ｔ］可変ノードからの完全なメッセージを使用する必要はない。代わりに、これらのメッセージを、ｘ［ｔ’］におけるマニューシャが位置ｚ［ｔ］に対応する位置へ移動するか否かを示すバイナリメッセージに減少させることができる。ノードｚ［ｔ］に対するバイナリ情報を使用することによって、可成り演算量を削減することができる。

最初に１組の中間的数量を計算して、その後これらの中間的数量を再利用することにより、様々な規則に対する第３の簡素化を図ることができる。たとえば、可変ノードｚ［ｔ］からの出力メッセージは他のすべてのノードからの入力メッセージの積である。可変ノードｚ［ｔ］へのＫ個の接続があれば、この規則の簡単な実施は、他のＫ−１個の接続からのメッセージを結合しなければならないので、Ｋ^２に比例する演算を必要とする。これをより効率的に行うためには、ノードｚ［ｔ］に対する限界確率（ｍａｒｇｉｎａｌ ｂｅｌｉｅｆ）を計算するプロセスにおいて、一度、ノードｚ［ｔ］に入ってくるすべてのメッセージを結合する。そして、特定の接続に対する出力メッセージを得るために、対数尤度ドメインにおいて、その接続からの入力メッセージにより全メッセージを割り算或いは減算する。

また、三角形ノードからの出力メッセージを計算する際に、中間的数量の同様の再利用を適用できる。特に、ｚ’［ｔ］が、可変ノードｚ［ｔ］から位置ｔ’のノード１６０７へのバイナリメッセージを表すものとする。数量ｚ’［ｔ］は、マニューシャが認証の間、位置ｔ’から位置ｔまで移動するか否かを示す。これらのバイナリメッセージに関するノード１６０７に対する簡単な合計積（ｓｕｍ−ｐｒｏｄｕｃｔ）の規則は、１６０４が位置ｔ’でノード１６０７に接続される可変ノードのすべての可能な組合せに亘って積算することを必要とする。たとえば、位置ｔ’におけるノード１６０７がノードｚ［１］、ｚ［２］、ｚ［３］およびｚ［４］に接続されるならば、ｚ’［１］へのメッセージを演算することは、ｚ’［２］、ｚ’［３］およびｚ’［４］のすべての可能な組合せに亘って積算することを必要とする。この方法は、各三角形ノードに接続された可変ノードの数で指数関数的な計算の複雑さを有する。

制約条件ノード１６０７が、高々ｚ’［ｔ］ノードの１つがノンゼロであることを許容することを実現することによって、この指数関数的な複雑さを解消することができる。このようにして、ノードｚ’［ｔ］に対する各出力メッセージは、他のすべてのノードｚ’［ｔ］がゼロであることに対応する項と、１つのノードがゼロであることを除いて他のすべてのノードｚ’［ｔ］に対応する項とを含む。これらの項をあらかじめ計算することによって、ファクターノード１６０７に対するメッセージ通過規則を、接続の数における指数関数的複雑さから接続の数における１次関数的複雑さへ減少させることができる。

バイオメトリックパラメータの統計を収集する

図１８は、ファクターグラフ１６００、すなわちこの発明によるモデル、のパラメータ１３０３を設定するためのプロセス１８００を示す。バイオメトリックトレーニングデータ１３０１を取得する。未処理の指紋Ｆが選択１８０２される。指紋Ｆの測定値ＢおよびＢ’の未処理のペアが選択１８０３される。それらのそれぞれのマニューシャＭ（Ｂ）およびＭ（Ｂ’）が判別１８０４される。マニューシャを比較１８０５して、移動、回転、挿入および削除の統計を判別１８０６する。統計はファクターグラフにおける統計を改訂（ｒｅｖｉｓｅ）１８０７するのに使用される。まだ処理１８０８されていない指紋Ｆの一対の測定値があれば、ステップ１８０３へ戻る。そうでなければ、まだ処理１８０９されていない指紋があれば、ステップ１８０２に戻る。すべての指紋とそれらのマニューシャペアが処理済になった後、統計収集はステップ１８１０で完了する。

データアラインメント

生体測定システムでは、登録バイオメトリックデータはしばしば認証データに対して位置がずれる。同じバイオメトリックデータの異なる測定値は、平行移動、回転、拡大縮小などのグローバル（大域的）変換（ｇｌｏｂａｌ ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ）によりしばしば変動する。そのような変動は、パターンに基づくバイオメトリック認証、すなわちシンドロームコーディングを使用しない認証方式ではそれほど問題ではない。

対照的に、我々のシステムでは、登録バイオメトリックパラメータのシンドロームベクトル３３１だけが比較のために利用できる。したがって、異なるアラインメント（配列、配置）に亘る検索は、各可能なアラインメントに対する復号化を伴う。マニューシャ移動モデルは細かいミスアラインメント（位置ずれ）に対応できるが、復号化の演算費用を最小にするために、探索空間を最小にすることが望まれる。

図１９は、この発明の実施の形態による、登録或いは認証時の指紋のアラインメントプロセス（整合処理）の各々のステップを示している。指紋が取得１９０１され、マニューシャパラメータが、そのコア（中心）点の位置および方位とともに、抽出１９０２される。そのコア点と方位は指紋に対する慣性基準フレームを定義し、ここで、コア点の位置は原点であり、その方位はＹ軸として機能する。そのコア点に関連する慣性基準フレームに対するマニューシャの位置と方位が再計算１９０３される。その結果１９０４、指紋に対する基準フレームで測定された１組のマニューシャが得られる。

利点としては、この手続きにより、平行移動および回転の効果の大部分またはすべてを取り除くことができる。典型的には、そのような前処理は、復号化がより少ない組の平行移動および回転で実行される、計算上より強力（集中的）なローカルサーチ（局所検索）と結合される。この前処理手続きは、マニューシャ抽出ルーチンの一部として使用できる。

パラメータ設定に関するアラインメント後のリビジョン（改訂）

登録および認証バイオメトリック特徴が復号化前にお互いに対して変位する毎に、ファクターグラフのパラメータはこの変位を反映するように変更される。このような例は、登録および認証機能がアラインメント手続き１９００により、或いはローカルサーチに対応する多数の小変位により移行する時である。

変位、および登録と認証観測窓１４０３（図１４を参照）の相対的大きさによっては、認証の間、幾つかの登録特徴位置を全く観測できないかも知れない。したがって、これらの観測されない位置に対して、マニューシャ消去の確率を１に設定することによって、これを反映するようにファクターグラフを変更する。これは、ファクターノード１６０５における消去確率を１に等しく設定することによって、図１６Ｂに反映される。観測される多少の尤度および観測されない多少の尤度を持っている窓１４０３のエッジ（縁部）の近くのマニューシャに対して、その事前確率１６０５がそれに応じて変更される。

シンドローム前処理

図３のバイオメトリックセキュリティシステム３００では、登録段階の間、バイオメトリックパラメータ３０１はシンドロームエンコーダ３３０に直接入力される。同様に、認証段階では、バイオメトリックパラメータ３６０はシンドロームデコーダ３７０に直接入力される。

図１４はマニューシャ点位置を表示しており、マニューシャ点位置は指紋に対するバイオメトリックパラメータとしてしばしば使用される。図３、５および６に記載したようなバイオメトリックセキュリティシステム用のシンドロームに基づくフレームワークにおいて、この表示を使用することに関して幾つかの問題がある。

第１に、その表示は、まばら（ｓｐａｒｓｅ）であり、モデル化するのは難しい。図１５に示されるモデルは、マニューシャに固有の移動、挿入および削除をモデル化することを試みる。しかしながら、それらのモデルは複雑である。

第２に、その表示は従来のシンドロームコードに余り適していない。その表示はバイナリデータの形式であっても、データは、偏っており、従来のチャネルコードおよび対応する復号方法がデータに適用されるとき高性能をもたらすような固有の統計的性質を持っていない。

その性能は、ソースの偏った性質および計測チャンネルの非対称性を説明する新しいシンドロームコードを設計することによって、改善できる。これは興味深く且つ複雑なプロセスである。

図２０はこの発明の実施の形態によるバイオメトリックパラメータをシンドロームコード化する方法を表している。第１のバイオメトリックパラメータ２０１０が、たとえば登録段階１０の間に（図１を参照）、ユーザから取得される。第１のバイオメトリックパラメータ２０１０は、バイオメトリックパラメータ２０３０のバイナリ表示を生成するために、シンドローム前処理２０２０される。前処理２０２０は、１組（１以上）のバイナリロジック条件２０２２を、取得されたバイオメトリックパラメータ２０１０に適用する。１組のバイナリロジック条件２０２２は、そのバイナリ表示２０３０に１組（１以上）の望ましい所定の統計的性質２０２５を持たせるように、強制或いは試みる。その１組の所定の統計的性質２０２５について、以下でさらに記述する。バイオメトリックパラメータ２０３０のバイナリ表示はシンドロームコード化２０４０されて、第１のシンドローム２０５０を生成する。ここで、ロジック条件が目標統計的性質を達成しようとすることができることに注意するべきである。また、その処理の間、その統計的性質をダイナミックに調整できることに注意するべきである。

次に、ハッシュ関数を適用することによって、第１のシンドロームをさらに処理して登録ハッシュを生成することができ、生成された登録ハッシュは、後でユーザを認証する際に使用するために、シンドロームベクトルとともに格納されることができる。

我々は、バイナリ表示２０３０および望ましい統計的性質２０２５と互換性があるように、我々のエンコーダ２０４０を明確に設計する。我々は、コード化をバイナリ表示および望ましい統計的性質に適合させることにより、我々のシステムの性能と信頼性が改善されると信じる。

図２１は、この発明の実施の形態にしたがってシンドローム復号化する方法の詳細を示す。バイオメトリックパラメータは、たとえば認証段階２０の間に、再び獲得される。第２のバイオメトリックパラメータ２１１０は、シンドローム前処理２０２０されて、バイオメトリックパラメータ２１３０のバイナリ表示を生成する。上述したように、バイナリ表示２１３０は、登録時に課されるのと同じ組の望ましい所定の統計的性質２０２５を有する。そして、前処理されたバイナリ表示２１３０は、シンドローム復号化２１４０への入力として使用されて、再構成されたバイオメトリックパラメータが２１４５を生成する。上述したように、デコーダは望ましい統計的性質を持っているバイナリ表示と互換性がある。コード化および復号化をバイナリ表示および望ましい統計的性質に適合させることにより、我々のシステムの性能と信頼性とを改善する。

第１および第２のバイオメトリックパラメータが同じ人から来ているならば、譬え第１および第２のパラメータからのバイオメトリックパラメータが詳細では異なっていたとしても、再構成されたバイオメトリックパラメータは、第１のバイオメトリックパラメータと同じでなければならない。

本明細書に記載されたシンドローム前処理は、図３、５および６に示された方法に適用できる。

望ましい目標統計的性質

シンドローム前処理２０２０は、バイオメトリックパラメータを、望ましい統計的性質２０２５を有するバイナリ表示すなわちバイナリストリング（文字列）に変形するのに使用される。それらの性質は、いつも得られるわけではないかも知れないので、目標性質であると考えられる。

統計的性質は、シンドロームコードが最適性能を実現できることを保証する。我々の前処理２０２０により、バイオメトリックパラメータ間の複雑な関係をモデル化するのに関わる複雑さは大きく減少される。

バイナリ表示２０３０／２１３０の望ましい１組の統計的性質２０２５は以下の通り概括される：バイナリ表示における各ビットには、ゼロまたは１のどちらかであるという等しい確率がある；同じバイナリ表示における異なるビットはお互いに独立している；異なるユーザからのバイナリ表示はお互いに独立している；同じユーザの異なる読取りに対するバイナリ表示はお互いに統計的に依存している。

この発明のこれらの実施の形態に具現された手法は図１３の実施の形態に対比することができる。図１３に示された実施の形態では、特徴モデル１３０４および測定モデル１３０５は、トレーニング（訓練）集合におけるバイオメトリックデータの基底構造をモデル化するとともに、バイオメトリックデータが、単一ユーザに対するおよび複数のユーザに亘る、複数の読取りの中でどう変動するかをモデル化する。コード化および復号化をそれらのモデルに適合させるために、何も行わない。

対照的に、図２０に示されるようなシンドローム前処理手法は、図１３のように、バイオメトリックデータから直接取得された特徴集合を使用しない。その代わりに、図２０−２１の特徴集合、すなわちバイナリ表示、は、シンドロームコード化および復号化手続きと互換性があるように設計される。

我々は、特徴集合を、既存の、コード設計、シンドロームコード化およびシンドローム復号化手続きと互換性があるように明確に設計する。本明細書に記述した所定の統計的性質を有する特定の組の特徴に対して、設計された特徴集合に適合するバイナリ（２進）対称チャネルに対するチャネルコードを利用できる。そのようなチャネルコードの構造およびそれらに関連するシンドロームコード化および復号化手続きは、よく理解され且つ深く探究されたトピックである。

図２２Ａ−２２Ｃはそれぞれ２００ビットを有する１組のバイナリ表示のビットストリング（列）に対応する１組の統計的性質を示す。

図２２Ａはその組のバイナリストリングにおける平均数のヒストグラムを示す。理想的な分布は１００を中心しており、それはビットの半分が１であることを含意する。

図２２Ｂは各ストリングにおける、ビットのペア平均情報量（ｐａｉｒ−ｗｉｓｅ ｅｎｔｒｏｐｙ）を示す。理想的には、各対のビットが独立していれば、平均情報量はすべての対に対して２である。しかしながら、ビットの中に幾らか依存性があれば、平均情報量の値は２未満となる。最悪の場合には、プロセスバイオメトリックパラメータにおける特定のビットがいつも別のビットから予測できて、その他のビットが等しい確率でゼロまたは１であるなら、ペア平均情報量は１である。

図２２Ｃは、イントラユーザ（ユーザ内）変動（ｉｎｔｒａ−ｕｓｅｒ ｖａｒｉａｔｉｏｎｓ）２２１０とインターユーザ（ユーザ間）変動（ｉｎｔｅｒ−ｕｓｅｒ ｖａｒｉａｔｉｏｎｓ）２２２０を示す。イントラユーザ変動２２１０は、同じユーザの複数のサンプルに対応するビットストリング（ビット列）の間の正規化されたハミング距離を表す。インターユーザ変動２２２０は、異なるユーザのサンプルに対応するビットストリングの間の正規化されたハミング距離を表す。理想的には、イントラユーザ変動とインターユーザ変動は重ね合わせるべきでなく、また、それぞれが狭い範囲に亘って分布するべきである。その上、イントラユーザ変動２２１０はできるだけ低く（小さく）なるべきであり、たとえば、図示されるように、分布約０．１は、同じユーザの各ビットには１０％のエラー確率があることを示す。他方、インターユーザ変動に対する分布は０．５を中心にするべきであり、これは、異なるユーザからのビットストリングがお互いに独立していることを示す。

シンドローム前処理の実行

図２３は、我々のシンドローム前処理方法を示す。シンドローム前処理は１組（１以上）のバイナリロジック条件を適用する、すなわち、バイナリ表示すなわちバイナリストリング「００１１１０００１０１１１０００１…．．」をもたらすバイオメトリックパラメータに関してイエス（ｙｅｓ）／ノー（ｎｏ）応答を有する条件を適用する。

図２４に示される我々の方法では、１組のバイナリロジック条件２０２２がバイオメトリックパラメータに適用される。その適用結果の出力が非バイナリ２４３０であるならば、その出力は、必要なバイナリ表示をもたらすために２値化４２０２される。

たとえば、バイオメトリックパラメータは指紋に対するマニューシャ点の位置である。１つのバイナリ（２値）条件は、与えられた２次元（２Ｄ）領域のマニューシャの数が閾値Ｍより大きいか否かを判別する。

バイナリロジック条件

図２５Ａ−２５Ｃに示されるように、幾つかのタイプのバイナリロジック条件がバイオメトリックパラメータに適用できる。図２５Ａ−２５Ｃのドットは指紋マニューシャの座標（サンプル位置）を表す。図２５Ａおよび２５Ｂにおいて（ｘ−位置、ｙ−位置）座標、或いはまた図２５Ｃにおいて（ｘ−位置、ｙ−位置、方位）座標（ｚ）。

図２５Ａでは、各条件はサンプルを通して描かれた線２５０１に基づいている。バイナリロジック条件はｙ−ｍｘ−ｎ＝０である。線はランダムな傾きとｙ切片値を持つことができる。この発明の実施の形態１では、線より上の（すなわち、条件ｙ−ｍｘ−ｎ＞０を満たす領域に位置する）マニューシャ点の数と線より下の（すなわち、条件ｙ−ｍｘ−ｎ＜０を満たす領域に位置する）マニューシャ点の数の差が得られる。これは範囲［−Ｍ、Ｍ］の値のベクトルをもたらし、ここで、Ｍは指紋のマニューシャ点の最大数である。必要ならば、ベクトルを２値化することができる。

図２５Ｂでは、条件は１組の長方形２５０２である。各長方形は、幅と高さとともに、該長方形の左上隅を表す原点で生成される。１組の長方形は、これらの点のランダムな値で、または所定の配置により生成できる。この発明の実施の形態１では、条件は与えられた長方形の中のマニューシャ点の数である。

この発明の実施の形態１では、条件は、特定の閾値よりも大きな、与えられた長方形内のマニューシャ点の数であり、ここで、その閾値は、各長方形に対して、その位置および領域、および／又はユーザデータサンプルのグローバルな統計に基づいて変動してもよい。

この発明の別の実施の形態では、条件は１つの長方形内のマニューシャの数と２番目の長方形内のマニューシャの数の差である。

マニューシャ方位などの指紋に関する追加データを含めるために、長方形条件を立方体や直方体２５０３に拡張でき、ここで、最初の２つの寸法（ｄｉｍｅｎｓｉｏｎｓ）は、上述したように、マニューシャ点位置を表し、また、３番目の寸法（ｄｉｍｅｎｓｉｏｎ）（ｚ）はマニューシャ方位を表す。図２５Ｃでは、条件は１組の直方体を含んでいる。各直方体は、幅、高さおよび深さとともに、該直方体の左上隅を示す原点で生成される。１組の直方体は、これらの点のランダムな値で、または所定の配置により生成できる。この発明の実施の形態１では、条件は与えられた直方体内のマニューシャ点の数である。この発明の実施の形態１では、条件は、特定の閾値よりも大きな、与えられた長方体内のマニューシャ点の数であり、ここで、その閾値は、各直方体に対して、その位置および体積、および／又はユーザデータサンプルのグローバルな統計に基づいて変動してもよい。この発明の更に別の実施の形態では、条件は１つの直方体内のマニューシャの数と２番目の直方体内のマニューシャの数の差である。

この発明は本明細書に記述した特定のロジック条件に限定されない。バイオメトリックの特性によって、円形、球形、および多角形に基づく他の様々な条件もまた使用できる。

さらに、これらの方法は、マニューシャに基づく特徴集合の変換および２値化に制限されない。その目的は、シンドロームコード化および復号化に適合する、統計情報を有するバイナリ表示を生成するために、バイナリロジック条件をバイオメトリックデータに適用することである。たとえば、この発明は、とりわけ他のタイプの指紋データの中で、パターンに基づくデータや周波数領域データに適用できる。

一般的に言えば、条件の間のオーバラップは、結果として得られるバイナリ表示における相関関係に影響する。条件は、この影響を考えて設計され得る。たとえば、２つの長方形の間の許容できるオーバラップの量に関して制限を課すことができるであろう。また、シンドロームコード化および復号化手続きも、そのような相関関係を考えて設計され得る。しかしながら、この発明の目的は、市販のコード設計やコード化および復号化手続きに対するそのような調整の必要性を最小にすることである。

２値化

図２６は２値化の幾つかのタイプを示す。図２６Ａでは、閾値２６０１が、バイナリベクトル２６０３を生成ために、ベクトル２６０２のすべての値に適用される。この閾値は、すべてのビット位置に対して同じでもよいし、或いは各ビット位置に対して変化してもよい。

図２６Ｂでは、正規直交基底へのランダム投影２６０４が最初に非バイナリのベクトル２６０２に適用され、ここで、このランダム投影はすべてのユーザに対して同じである。そして、この投影の結果は、バイナリベクトル２６０３を生成するために、閾値化プロセスを加えられる。ランダム投影の代わりに、本物のユーザと詐欺師（偽者）とから取得されたサンプルの分離を改善するために、たとえば、主成分分析（ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ）や線形判別分析（ｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓ）などの他の線形（リニア）或いは非線（ノンリニア）変換を使用することができる。

図２６Ｃでは、非バイナリ（非２値）ベクトル２６０２が最初に正規化２６０５され、次に、１組のランダム投影（ＲＰ）２６０４が各ユーザに対して適用され、それに続いて、各ランダム投影に対する閾値化２６０１が行われる。この閾値化は各投影に対して同じでもよいし、それらの投影の中で変動してもよい。そして、バイナリベクトル２６０３を生成するため、連結（ｃｏｎｃａｔｅｎａｔｉｏｎ）２６０７がこの後に続いて行われる。

統計的分析

望ましい目標統計的性質が達成されることを保証、確認するために、シンドローム前処理の設計の一部として、統計的分析をバイナリ表示に対して実行することができる。このように、統計的分析が、シンドローム前処理の最終的な結果に対して実行され、シンドローム前処理の動作に対してフィードバックは行われない。

或いは、シンドローム前処理の動作を導くために、シンドローム前処理の間、統計的分析はまた中間的バイナリストリングに対しても実行することができる。このようにして、シンドローム前処理の間、統計的性質の明確なフィードバックが提供される。

シンドローム前処理に対するセキュリティの考察

バイナリ表示におけるビット数および同じユーザの異なるサンプル間の相関関係により、セキュリティのレベルが判別される。たとえば、バイナリストリングが４００ビットであり、相関関係が十分に強いためユーザの復号に成功するために３００ビットのシンドロームを必要とするだけであるならば、セキュリティのレベルは１００ビットである。

セキュリティがシンドロームコード化段階から得られる。事実、シンドローム前処理の結果、所定の統計的相関を有するバイナリストリングが生成される。この場合、本システムによって提供されるセキュリティの推定値は、シンドロームコード化および復号化がモデル化の難しい相関関係を有するバイナリストリングを使用して実行される場合と比較して、より正確であると考えられる。

発明の効果

この発明はバイオメトリックパラメータに基づく安全なユーザ認証を実現する。シンドロームベクトルが元のバイオメトリックデータ或いは如何なる特徴ベクトルの代わりに格納されるので、この発明は安全である。これにより、基礎となるバイオメトリックデータを学習することによりデータベースへのアクセスを得る敵対者を防ぐことができる。

多重記述（ｍｕｌｔｉｐｌｅ ｄｅｓｃｒｉｐｔｉｏｎｓ）の周知の問題から従来のツールを使用することにより、敵対者がシンドロームベクトルＳだけを使用することで作り出すことができる元のバイオメトリックパラメータＥの可能な限り良い推定値を制限することが可能である。たとえば、Ｖ．Ｋ．Ｇｏｙａｌ，Ｍｕｌｔｉｐｌｅ ｄｅｓｃｒｉｐｔｉｏｎ ｃｏｄｉｎｇ：ｃｏｍｐｒｅｓｓｉｏｎ ｍｅｅｔｓ ｔｈｅ ｎｅｔｗｏｒｋ」，ＩＥＥＥ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｍａｇａｚｉｎｅ，Ｖｏｌｕｍｅ：１８，ｐａｇｅｓ ７４−９３，Ｓｅｐｔｅｍｂｅｒ ２００１を参照。その上、推定値の品質が絶対誤差、２乗誤差、重み付け誤差方法、或いは如何なる任意の誤差関数により測定されるか否かに関係なく、これらの制限（限界）を策定することが可能である。対照的に、すべての従来技術の方法はバイナリ値に基づいている。そこでは、セキュリティはハミング距離に依存する。

本質的には、シンドロームベクトルＳのセキュリティは、それが元のバイオメトリックパラメータＥの圧縮されたバージョンであるという事実による。その上、この圧縮表現はＥの「最下位ビット」に対応している。データ圧縮理論から周知のツールを使用して、「高圧縮のシンドロームコードが使用されるならば、これらの最下位ビットはせいぜい元のパラメータＥの劣悪な（不十分な）推定値しか生成することができない」ことを立証することが可能である。たとえば、Ｅｆｆｒｏｓ、「Ｄｉｓｔｏｒｔｉｏｎ−ｒａｔｅ ｂｏｕｎｄｓ ｆｏｒ ｆｉｘｅｄ− ａｎｄ ｖａｒｉａｂｌｅ−ｒａｔｅ ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ ｓｏｕｒｃｅ ｃｏｄｅｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌｕｍｅ ４５，ｐａｇｅｓ１８８７−１９１０，Ｓｅｐｔｅｍｂｅｒ １９９９、および「Ｓｔｅｉｎｂｅｒｇ ａｎｄ Ｍｅｒｈａｖ，「Ｏｎ ｓｕｃｃｅｓｓｉｖｅ ｒｅｆｉｎｅｍｅｎｔ ｆｏｒ ｔｈｅ Ｗｙｎｅｒ−Ｚｉｖ ｐｒｏｂｌｅｍ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌｕｍｅ ５０，ｐａｇｅｓ １６３６−１６５４，Ａｕｇｕｓｔ ２００４を参照。

第２に、偽造は基礎となるハッシュ関数３４０における衝突を見つけるのと少なくとも同じくらい難しいので、この発明は安全である。特に、復号されたバイオメトリックＥ”のハッシュＨ’が元のハッシュＨと一致する場合にだけ、本システムは認証段階３９０におけるシンドロームペア（Ｓ、Ｈ）を受け付ける。ＭＤ５などの暗号化ハッシュ関数にとって、Ｅと異なっているがＥのハッシュと一致するハッシュを持つ要素Ｅ”を見つけ出すことは、一般的に、不可能であると考えられている。而して、シンドローム復号化が、適切なハッシュでＥ”を復号するのに成功するならば、本システムは事実上、Ｅ”がＥと同じであると確信することができ、すべての認証決定が元のバイオメトリックパラメータで行われる。

第３に、この発明は、シンドロームベクトルＳを生成する際に、元のバイオメトリックパラメータＥを圧縮する。特にバイオメトリックデータの質問がたとえば顔画像或いは音声信号などの多量のデータを必要とする場合には、多くのユーザに対するバイオメトリックデータベースは大容量ストレージを必要とすることがある。したがって、必要とされるストリッジ容量を小さくすることにより、費用とエラー復元力の両方で劇的な改良をもたらすことができる。対照的に、バイオメトリックデータの安全な格納に対する殆どの従来技術の方法は、暗号化や誤り訂正のオーバヘッドにより実際に記憶データのサイズ（大きさ）を増大させ、したがって安全でない（セキュリティ保護されていない）システムよりも多くのストリッジ容量を必要とする。

第４に、この発明は、シンドロームコードの理論で作られるので、精巧なコード構造と復号アルゴリズムを適用することができる。特に、この発明によるシンドロームコーディングは、バイナリおよびマルチレベル両方の符号化構造に対して、周知のビタビ（Ｖｉｔｅｒｂｉ）アルゴリズム、確率伝搬、およびターボデコーディングを用いたソフトデコーディングの使用を容易にする。対照的に、殆どの従来技術の方法はバイナリコード、リード−ソロモンコード、および代数的復号化に基づいているので、バイオメトリックデータが、バイナリ値とは反対に、実際の値（ｒｅａｌ ｖａｌｕｅｓ）をとるとき、ソフトデコーディングを効果的に適用することができない。たとえば、幾つかの方法は、リファレンス（基準）を生成するために、登録段階におけるランダムな符号語でバイオメトリックデータの排他的論理和（ＸＯＲ）を計算することを特に要求し、また、認証段階におけるバイオメトリックデータでそのリファレンスの排他的論理和を計算することを要求する

第５に、安全なバイオメトリックスに関する殆どの従来技術は誤り訂正符号化を使用するが、この発明はシンドローム符号化を使用する。通常、誤り訂正符号化の計算の複雑さは、入力サイズ（大きさ）において超線形（ｓｕｐｅｒ ｌｉｎｅａｒ）である。対照的に、様々なタイプの低密度パリティチェックに基づくシンドロームコードを使用することによって、シンドローム符号化の計算の複雑さ（量）が入力サイズ（大きさ）においてリニアのみであるシンドロームエンコーダを構成することが容易になる。

第６に、シンドロームコーディングフレームワークを使用することによって、「直列連鎖累積コードを使用して信号を圧縮する」という発明の名称の米国特許出願第１０／９２８，４４８（引用によりここに援用される）にＹｅｄｉｄｉａ外によって記載されたＳＣＡコードのような強力な新しい埋め込まれたシンドロームコードを使用することが可能である。これらのコードは、シンドロームエンコーダが、登録の間、バイオメトリックデータの固有の変動性を推定して、シンドローム復号化に成功するのを許容するのに丁度充分なだけのシンドロームビットを符号化することを許容する。

第７に、データを暗号化するために、上述したようなシンドロームコードを使用できる。その上、所与のレベルの性能とエラー復元力とを有する最適のシンドロームコードのための設計を可能にする方法が記述される。

第８に、計測チャンネルが構造化ノイズを受けることがあっても、シンドローム特徴ベクトルを正しく復号できる。

第９に、符号化および復号化は、バイナリロジック条件によって課される望ましい統計的性質と互換性があるように設計することができる。

この発明は好適な実施の形態を例に挙げて説明したが、この発明の精神および範囲内で種々の他の改変および変更を行うことができることを理解すべきである。したがって、この発明の精神および範囲内に入るすべての変更例および変形例をカバーすることが、付加されたクレームの目的である。

従来技術のパスワードに基づくセキュリティシステムのブロック図である。 従来技術のバイオメトリックに基づくセキュリティシステムのブロック図である。 この発明の実施の形態１によるバイオメトリックセキュリティシステムのブロック図である。 データを保護するための従来技術のセキュリティシステムのブロック図である。 この発明の実施の形態によるデータセキュリティシステムのブロック図である。 この発明の実施の形態によるセキュリティシステムのブロック図である。 この発明の実施の形態によるシンドロームコードを構成するためのプロセスのブロック図である。 この発明の実施の形態によるヒストグラムを生成するためのプロセスのブロック図である。 この発明の実施の形態による特徴ベクトルを選択するためのプロセスのブロック図である。 この発明の実施の形態による係数間相関関係を測定するためのブロック図である。 登録時に、この発明の実施の形態によるシンドロームベクトルを生成するためのバイオメトリックエンコーダのブロック図、および、この発明の実施の形態による、認証の間に使用される図１１Ａのエンコーダのための相補型デコーダのブロック図である。 この発明の実施の形態による相関関係ノードを有する確率伝搬ファクターのグラフである。 この発明の実施の形態による、バイオメトリック特徴、完全な特徴ベクトル、シンドローム特徴ベクトル、および符号化されたシンドロームベクトルの間の依存関係を示すブロック図である。 この発明の実施の形態によるシンドロームコードを構成するためのプロセスのブロック図である。 この発明の実施の形態による指紋マニューシャ符号化のブロック図である。 この発明の実施の形態による、測定されたバイオメトリックデータにおける変動性のブロック図である。 この発明の実施の形態による、測定されたバイオメトリックデータにおける変動性のブロック図である。 この発明の実施の形態による、測定されたバイオメトリックデータにおける変動性のブロック図である。 この発明の実施の形態による確率伝搬ファクターグラフの高レベルの詳細のブロック図である。 この発明の実施の形態による確率伝搬ファクターグラフの低レベルの詳細のブロック図である。 この発明の実施の形態による、余分なものを取り除いた確率伝搬ファクターのグラフである。 この発明の実施の形態による指紋マニューシャの移動および測定モデルのパラメータを推定するためのプロセスのブロック図である。 この発明の実施の形態によるマニューシャのアラインメントを行うブロック図である。 この発明の実施の形態によるシンドローム前処理を有するシンドローム符号化プロセスのブロック図である。 この発明の実施の形態によるシンドローム前処理を有するシンドローム復号化プロセスのブロック図である。 この発明の実施の形態による所定の統計的性質のグラフである。 この発明の実施の形態による所定の統計的性質のグラフである。 この発明の実施の形態による所定の統計的性質のグラフである。 この発明の実施の形態によるバイナリロジック条件に基づくシンドローム前処理のブロック図である。 この発明の別の実施の形態による、シンドローム前処理に基づくバイナリロジック条件のブロック図である。 この発明の実施の形態によるシンドローム前処理の一部としてのロジック条件のグラフである。 この発明の実施の形態によるシンドローム前処理の一部としてのロジック条件のグラフである。 この発明の実施の形態によるシンドローム前処理の一部としてのロジック条件のグラフである。 この発明の実施の形態によるシンドローム前処理の一部としての２値化のグラフである。 この発明の実施の形態によるシンドローム前処理の一部としての２値化のグラフである。 この発明の実施の形態によるシンドローム前処理の一部としての２値化のグラフである。

Claims (21)

1. ユーザのバイオメトリック特徴を表すバイオメトリックパラメータを、データベースに安全に格納するためのコンピュータにより実行される前処理方法であって、
   １組のバイナリロジック条件を前記バイオメトリックパラメータへ適用して、前記バイオメトリックパラメータの２進表示を生成するステップであって、前記バイナリロジック条件は、前記バイオメトリック特徴の少なくとも一部の統計的性質に基づいて、少なくとも前記２進表示の１ビットを生成し、前記統計的性質は、１組の所定の統計的性質から選択されるステップと、
   シンドロームエンコーダを使用して前記２進表示をコード化して登録シンドロームベクトルを生成するステップであって、前記コード化が前記２進表示および前記１組の所定の統計的性質と互換性があるステップと、
   前記登録シンドロームベクトルに、暗号化であるハッシュ関数を適用して登録ハッシュを生成するステップと、
   データベースに前記登録シンドロームベクトルと前記登録ハッシュを格納するステップと、からなるコンピュータにより実行されるコード化および復号化前のバイオメトリックパラメータの前処理方法。
2. 請求項１の方法であって、認証ステップはさらに、
   ユーザの認証バイオメトリックパラメータを取得するステップと、
   前記１組のバイナリロジック条件を前記認証バイオメトリックパラメータに適用して認証バイオメトリックパラメータの２進表示を生成するステップであって、前記２進表示が、前記１組の所定の統計的性質により課された前記１組のバイナリロジック条件を有するステップと、
   シンドロームデコーダを使用して前記バイオメトリックパラメータの２進表示を復号して認証シンドロームベクトルを生成するステップであって、コード化が前記バイオメトリックパラメータの２進表示と前記１組の所定の統計的性質と互換性があるステップと、
   前記認証シンドロームベクトルにハッシュ関数を適用して認証ハッシュを生成するステップと、
   前記認証シンドロームベクトルと前記認証ハッシュで前記データベースへアクセスしてユーザを検証するステップと、からなる方法。
3. 請求項１の方法であって、前記１組の統計的性質は前記２進表示における各ビットが零または１のどちらかである確率が等しいことを強制する方法。
4. 請求項１の方法であって、前記１組の統計的性質は前記２進表示における異なるビットが互いに独立していることを強制する方法。
5. 請求項１の方法であって、前記１組の統計的性質は異なるユーザからの２進表示が互いに独立していることを強制する方法。
6. 請求項１の方法であって、前記１組の統計的性質は同一のユーザからの２進表示が統計的に互いに依存することを強制する方法。
7. 請求項１の方法であって、前記バイオメトリックパラメータは指紋に対するマニューシャ点の位置である方法。
8. 請求項７の方法であって、前記１組のバイナリロジック条件は、与えられた２次元領域におけるマニューシャ点の数が閾値Ｍより大きいか否かを判別する条件を含む方法。
9. 請求項７の方法であって、前記１組のバイナリロジック条件は、１つの線よりも上のマニューシャ点の数と、該線よりも下のマニューシャ点の数の差に基づく条件を含む方法。
10. 請求項７の方法であって、前記１組のバイナリロジック条件は、第１矩形部内のマニューシャ点の数と、第２矩形部内のマニューシャ点の数の差に基づく方法。
11. 請求項１の方法であって、前記バイオメトリックパラメータは、指紋に対するマニューシャ点の位置および方位である方法。
12. 請求項１１の方法であって、前記１組のバイナリロジック条件は、与えられた三次元領域におけるマニューシャ点の数が閾値Ｍより大きいか否かを判別する条件を含む方法。
13. 請求項１の方法であって、前記所定の統計的性質は、パターンベースのデータと互換性がある方法。
14. 請求項１の方法であって、前記所定の統計的性質は、周波数ドメイン（領域）のデータと互換性がある方法。
15. 請求項１の方法であって、論理的なバイナリ条件の適用により中間値を生成するとともに、前記方法はさらに、中間値を２値化することを含む方法。
16. 請求項１５の方法であって、前記２値化はさらに、中間値を閾値化することを含む方法。
17. 請求項１６の方法であって、前記２値化はさらに、前記閾値化の前に、中間値に変換を適用することを含む方法。
18. 請求項１７の方法であって、前記２値化はさらに、前記中間値を正規化することを含む方法。
19. 請求項１７の方法であって、前記変換は無作為の投影である方法。
20. 請求項１７の方法であって、前記変換は主成分分析である方法。
21. 請求項１の方法であって、前記２進表示を分析して前記１組の統計的性質が課されることを保障、確認することを含む方法。

Images