(57)【要約】  第１のバイオメトリックパラメータがユーザから取得される。入力データがバイオメトリックパラメータに従って暗号化されて、暗号文を保護する。バイオメトリックパラメータは、シンドローム符号化器を使用して符号化され、シンドローム符号を生成する。暗号文およびシンドローム符号は、互いに関連付けられ、同じユーザしか暗号文を復号化できないようにコンピュータ可読媒体に記憶される。
2009507267.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法であって、
第１のユーザから第１のバイオメトリックデータを取得することと、
前記第１のバイオメトリックデータから第１のバイオメトリックパラメータを生成することと、
暗号文を生成するために、前記第１のバイオメトリックパラメータを使用して前記第１のバイオメトリックデータを暗号化することと、
シンドローム符号を生成するために、シンドローム符号化器を使用して前記第１のバイオメトリックパラメータを符号化することと、
前記暗号文と前記シンドローム符号とを関連付けることと、
前記暗号文および前記シンドローム符号をコンピュータ可読媒体に記憶することと
を含むコンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法。
【請求項２】
第２のユーザから第２のバイオメトリックデータを取得することと、
前記第２のバイオメトリックデータから第２のバイオメトリックパラメータを生成することと、
第３のバイオメトリックパラメータを生成するために、シンドローム復号器および前記第２のバイオメトリックパラメータを使用して前記第１のバイオメトリックパラメータを復号化することと、
第３のバイオメトリックデータを生成するために、前記第３のバイオメトリックパラメータを使用して前記暗号文を復号化することと
をさらに含む請求項１に記載の方法。
【請求項３】
前記第１のバイオメトリックデータと前記第３のバイオメトリックデータとを比較することと、
前記第１のバイオメトリックデータと前記第２のバイオメトリックデータとが同一の場合のみ、機能へのアクセスを許可し、同一ではない場合にアクセスを拒絶することと
をさらに含む請求項２に記載の方法。
【請求項４】
コンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法であって、
第１のユーザから第１のバイオメトリックパラメータを取得することと、
暗号文を生成するために、前記第１のバイオメトリックパラメータに従って入力データを暗号化することと、
シンドローム符号を生成するために、シンドローム符号化器を使用して前記第１のバイオメトリックパラメータを符号化することと、
前記暗号文と前記シンドローム符号とを関連付けることと、
前記暗号文および前記シンドローム符号をコンピュータ可読媒体に記憶することと
を含むコンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法。
【請求項５】
第２のユーザから第２のバイオメトリックパラメータを取得することと、
第３のバイオメトリックパラメータを生成するために、シンドローム復号器および前記第２のバイオメトリックパラメータを使用して前記第１のバイオメトリックパラメータを復号化することと、
出力データを生成するために、前記第３のバイオメトリックパラメータを使用して前記暗号文を復号化することと
をさらに含む請求項４に記載の方法。
【請求項６】
前記入力データおよび前記出力データは、前記第１のユーザが前記第２のユーザと同一である場合のみ全く同じである請求項５に記載の方法。
【請求項７】
前記入力データは、バイオメトリックデータである請求項４に記載の方法。
【請求項８】
前記第１のバイオメトリックデータから第１の特徴ベクトルを抽出することと、
前記第３のバイオメトリックデータから第２の特徴ベクトルを抽出することと、
前記第１の特徴ベクトルと前記第２の特徴ベクトルとを比較することと、
前記第１の特徴ベクトルと前記第２の特徴ベクトルとが実質的に同じである場合のみ、機能へのアクセスを許可し、実質的に同じではない場合にアクセスを拒絶することと
をさらに含む請求項５に記載の方法。
【請求項９】
前記第１のバイオメトリックパラメータおよび前記第３のバイオメトリックパラメータは、前記第１の特徴ベクトルおよび前記第２の特徴ベクトルとそれぞれ異なる請求項８に記載の方法。
【請求項１０】
前記第１のバイオメトリックデータから完全な特徴ベクトルを抽出することと、
前記完全な特徴ベクトルから誤差ヒストグラムを構築することと、
前記誤差ヒストグラムを使用して前記完全な特徴ベクトルをシンドローム特徴ベクトルに低減することと、
前記シンドローム特徴ベクトルの複数の異なる係数間の相関を測定することと、
前記シンドローム特徴ベクトルのシンドローム符号を設計するために、密度発展法を適用することと
をさらに含む請求項４に記載の方法。
【請求項１１】
前記完全な特徴ベクトルは、整数のみを記憶する完全な硬特徴ベクトルと、整数および実数を記憶する完全な軟特徴ベクトルとを含む請求項１０に記載の方法。
【請求項１２】
前記シンドローム復号器は、確率伝搬ネットワークを使用する請求項４に記載の方法。
【請求項１３】
前記確率伝搬ネットワークは、検査ノード、変数ノード、および各変数ノード対の間の相関ノードを含む請求項１２に記載の方法。
【請求項１４】
コンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法であって、
ユーザからバイオメトリックデータを取得することと、
前記バイオメトリックデータから暗号鍵を生成することと、
暗号文を生成するために、前記暗号鍵に従ってデータを暗号化することと、
前記暗号鍵を符号化鍵として符号化することと、
前記符号化鍵を前記暗号文と関連付けてコンピュータ可読媒体に記憶することと
を含むコンピュータ可読媒体にデータを記憶するためにコンピュータで実施される方法。
【請求項１５】
続けて、前記ユーザからバイオメトリックデータを再び取得することと、
前記再び取得されたバイオメトリックデータから復号化鍵を生成することと、
前記復号化鍵を使用して前記符号化鍵を復号化することと、
前記復号化鍵が前記暗号鍵に一致する場合のみ、前記復号化鍵を使用して前記暗号文を復号化することと
をさらに含む請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、暗号法の分野に関し、より詳細には、ユーザ認証用およびデータ暗号化用のバイオメトリックパラメータを記憶することに関する。
【背景技術】
【０００２】
従来のパスワードに基づくセキュリティシステム
従来のパスワードに基づくセキュリティシステムは、通常、２つのフェーズを含む。具体的には、登録フェーズの期間中、ユーザは、パスワードを選択し、このパスワードは、サーバ等の認証デバイスに記憶される。認証フェーズの期間中、資源またはデータにアクセスするために、ユーザは、自身のパスワードを入力し、このパスワードが、パスワードの記憶されたものと照合される。パスワードがプレーンテキストとして記憶される場合、システムにアクセスする攻撃者は、あらゆるパスワードを得ることができる。したがって、攻撃が１回成功した場合であっても、システム全体のセキュリティが危険にさらされる可能性がある。
【０００３】
図１に示すように、従来のパスワードに基づくセキュリティシステム１００は、登録フェーズ１０中に、暗号化された（１１０）パスワード１０１をパスワードデータベース１２０に記憶する（１１５）。本明細書では、データベースは、任意のメモリまたは他のコンピュータ可読媒体、テープ、フラッシュメモリ、ＲＡＭ、ＲＯＭ、ディスク等に記憶することができる。
【０００４】
具体的には、Ｘが、記憶される（１１５）パスワード１０１である場合、システム１００は、実際にはｆ（Ｘ）を記憶する。ここで、ｆ（  ）は、ある暗号化関数またはハッシュ関数１１０である。認証フェーズ２０の期間中、ユーザは、候補のパスワードＹ１０２を入力し、システムは、ｆ（Ｙ）を求め（１３０）、そして、ｆ（Ｙ）が、記憶されたパスワードｆ（Ｘ）と一致する（１４０）場合にのみ、システムへのアクセスを許可し（１５０）、そうでない場合、アクセスは拒否される（１６０）。
【０００５】
利点としては、暗号化されたパスワードは、暗号化関数なしでは攻撃者にとって役に立たないことである。暗号化されたパスワードは、通例、戻すことが非常に困難である。
【０００６】
従来のバイオメトリックに基づくセキュリティシステム
従来のバイオメトリックセキュリティシステムは、パスワードに基づくシステムと同じ脆弱性を有し、暗号化されていないパスワードを記憶する。具体的には、データベースが、暗号化されていないバイオメトリックパラメータを記憶する場合、それらパラメータは、攻撃および悪用の対象になる。
【０００７】
例えば、顔認識システムまたは音声認識を使用するセキュリティシステムでは、攻撃者は、その攻撃者とよく似たバイオメトリックパラメータを検索することができる。適切なバイオメトリックパラメータが突き止められた後、攻撃者は、それらパラメータを変更して、攻撃者の外見または音声と一致させ、認可されないアクセスを行うことができる。同様に、指紋認識または虹彩認識を使用するセキュリティシステムでは、攻撃者は、一致する指紋または虹彩を模倣するデバイスを構築して、認可されないアクセスを行うことができる。例えば、このデバイスは、偽造した指または眼である。
【０００８】
バイオメトリックパラメータは、本来、時間の経過と共に変化するものであるので、バイオメトリックパラメータを暗号化することは、常に可能であるとは限らない。具体的には、バイオメトリックパラメータＸは、登録フェーズの期間中に入力される。このパラメータＸは、暗号化関数またはハッシュ関数ｆ（Ｘ）を使用して暗号化されて記憶される。認証フェーズの期間中、同じユーザから得られたバイオメトリックパラメータは、異なる可能性がある。例えば、顔認識を使用するセキュリティシステムでは、ユーザの顔は、認証の期間中と比べて登録の期間中は、カメラに対して異なる向きを有する可能性がある。肌の色合い、髪型、および顔の特徴は、変化する可能性がある。したがって、認証の期間中、暗号化されたバイオメトリックパラメータは、記憶されたどのパラメータとも一致しないことになり、拒絶されることになる。
【０００９】
誤り訂正符号
アルファベットＱ上の（Ｎ，Ｋ）誤り訂正符号（ＥＣＣ）Ｃは、長さＮのＱＫベクトルを含む。線形（Ｎ，Ｋ）ＥＣＣは、Ｎ行およびＫ列を有する生成行列Ｇを使用することによるか、または、Ｎ−Ｋ行およびＮ列を有するパリティチェック行列Ｈを使用することにより、記述することができる。「生成行列」という名称は、ベクトルｗとして表された符号語が、ｗ＝ｖＧに従って、任意の長さＫの入力された行ベクトルｖを行列Ｇに右乗算することにより、ベクトルｖから生成できるということに基づいている。同様に、ベクトルｗが符号語であるかどうかをチェックするために、ＨｗＴ＝０であるかどうかをチェックすることができる。ここで、列ベクトルｗＴは、行ｗの転置である。
【００１０】
誤り訂正符号の標準的な使用では、入力ベクトルｖが、ベクトルｗに符号化され、記憶されるか、または、送信される。ベクトルｗの破損したものが受信されると、復号器は、符号の冗長性を使用して誤りを訂正する。直感的に、符号の誤りの耐性は、符号の冗長量に依存する。
【００１１】
Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号、Ｗｙｎｅｒ−Ｚｉｖ符号、およびシンドローム符号
ある意味で、Ｓｌｅｐｉａｎ−Ｗｏｌｆ（ＳＷ）符号は、誤り訂正符号とは逆のものである。誤り訂正符号は、冗長性を追加してデータを拡張するのに対して、ＳＷ符号は、冗長性を取り除いてデータを圧縮する。具体的には、ベクトルｘおよびベクトルｙが、相関したデータのベクトルを表す。符号化器が、すでにベクトルｙを有する復号器にベクトルｘを通信したい場合、符号化器は、復号器がベクトルｙを有することを考慮してデータを圧縮することができる。
【００１２】
極端な例として、ベクトルｘおよびベクトルｙが１ビットしか異ならない場合、符号化器は、ベクトルｘおよびその相違した位置を単に記述するだけで圧縮を行うことができる。もちろん、より現実的な相関モデルには、より高度な符号が必要とされる。
【００１３】
ＳＷ符号化の基本理論、および、関連したＷｙｎｅｒ−Ｚｉｖ（ＷＺ）符号化は、SlepianおよびWolf著「Noiseless coding of correlated information sources」（IEEE Transactions on Information Theory, Vol. 19, pp. 471-480, July 1973）並びに、WynerおよびZiv著「The rate-distortion function for source coding with side information at the decoder」（IEEE Transactions on Information Theory, Vol. 22, pp. 1-10, January 1976）に記載されている。より最近では、PradhanおよびRamachandranが、「Distributed Source Coding Using Syndromes (DISCUS): Design and Construction」（IEEE Transactions on Information Theory, Vol. 49, pp. 626-643, March 2003）に、このような符号の実用的な実施態様が記載されている。
【００１４】
基本的に、シンドローム符号は、Ｎ−Ｋ行およびＮ列を有するパリティチェック行列Ｈを使用することによって動作する。長さＮのバイナリベクトルｘを長さＫのシンドロームベクトルに圧縮するために、Ｓ＝Ｈｘが求められる。復号は、多くの場合、使用される特定のシンドローム符号の詳細に依存する。例えば、シンドローム符号がトレリスに基づくものである場合、既知のビタビアルゴリズム等のさまざまな動的計画法に基づく探索アルゴリズムを使用して、Pradhan他によって記載されているようなシンドロームＳに対応する最も可能性のあるソースシーケンスｘ、および、一連のサイド情報を見つけることができる。
【００１５】
代替的に、低密度のパリティチェックシンドローム符号が使用される場合、Coleman他著「On some new approaches to practical Slepian-Wolf compression inspired by channel coding」（Proceedings of the Data Compression Conference, March, 2004, pages 282-291）に記載されているように、確率伝播復号を適用することもできる。
【００１６】
従来技術
本発明に関係した従来技術は、３つのカテゴリーに分類される。第１に、多くの従来技術は、このようなバイオメトリックパラメータの安全な記憶とは関係のないバイオメトリックパラメータの詳細な特徴抽出、記録、および使用を記載している。本発明は、安全な記憶に関係したものであり、バイオメトリックパラメータがどのように取得されるかに関する詳細とは概ね関係がないので、従来技術のこのカテゴリーの詳細は、省略する。
【００１７】
従来技術の第２の部類は、本発明に関連したものであり、バイオメトリックの安全な記憶および認証用に設計された以下のシステムを含む。すなわち、米国特許第６，０３８，３１５号の「Method and system for normalizing biometric variations to authenticate users from a public database and that ensures individual biometric data privacy」、Davida他著「On enabling secure applications through off-line biometric identification」（Proceedings of the IEEE Symposium on Security and Privacy, May 1998）、Juels他著「A Fuzzy Vault Scheme」（Proceedings of the 2002 IEEE International Symposium on Information Theory, June 2002）および米国特許第６，３６３，４８５号の「Multi-factor biometric authenticating device and method」を含む。
【００１８】
図２は、米国特許第６，０３８，３１５号に記載されている基本的な方法の詳細のいくつかを示している。登録フェーズ２１０において、バイオメトリックパラメータが、Ｅ２０１で表記されるビットシーケンスの形で取得される。次に、ランダムな符号語Ｗ２０２が、バイナリ誤り訂正符号から選択され、排他的ＯＲ（ＸＯＲ）関数２２０を使用してパラメータＥと加法結合されて、参照値Ｒ２２１が生成される。オプションとして、参照値Ｒをさらに符号化することができる（２３０）。いずれの場合も、参照値Ｒは、パスワードデータベース２４０に記憶される。
【００１９】
認証フェーズ２１５において、バイオメトリックパラメータＥ’２０５が認証用に提示される。この方法は、基本的には、Ｅ’をＲから減算することによって、ＲとＥ’とのＸＯＲを求め（２５０）、Ｚ＝Ｒ−Ｅ’＝Ｗ＋Ｅ−Ｅ’が得られる（２５１）。次に、この結果は、誤り訂正符号を用いて復号され（２６０）、Ｗ’が生成される（２６１）。ステップ２７０において、Ｗ’がＷと一致する場合、アクセスが許可され（２７１）、そうでない場合、アクセスは拒否される（２７２）。
【００２０】
この方法は、基本的に、ハミング距離、すなわち、登録されたバイオメトリックＥ２０１と認証バイオメトリックＥ’２０５との間で異なるビット数を測定する。この相違が、ある所定のしきい値よりも小さい場合、アクセスが許可される。この方法は、参照値Ｒのみを記憶し、実際のバイオメトリックパラメータＥを記憶しないので、安全である。
【００２１】
Davida他およびJuels他は、図２に示す方法を変形したものを記載している。具体的には、両者は、登録フェーズの期間中に誤り訂正符号を有するバイオメトリックデータを符号化し、その後、その結果生成された符号語を安全にするオペレーションが続く。Davida他は、チェックビットの送信のみによって符号語を隠蔽するのに対して、Juels他は、「チャフ（chaff）」と呼ばれるある量の雑音を追加する。
【００２２】
米国特許第６，３６３，４８５号は、バイオメトリックデータを誤り訂正符号およびある秘密情報と結合して、秘密鍵を生成するための方法を記載している。ある秘密情報は、パスワードまたは個人識別番号（ＰＩＮ）等である。Ｇｏｐｐａ符号またはＢＣＨ符号等の誤り訂正符号が、さまざまなＸＯＲ演算と共に使用される。
【００２３】
図２に示す固定データベースアクセス制御システムに加えて、第３の分類の従来技術は、データ保護、具体的にはラップトップ、ＰＤＡ、携帯電話、およびデジタルカメラ等の、メモリを含む携帯機器のデータ保護にバイオメトリクスを使用することを含む。携帯機器は、紛失しやすい、または盗まれやすいため、携帯機器に記憶されているデータを保護することが必要になる。
【００２４】
図４は、データＤ４０１を記憶するための既存の手法に伴う問題を示す。符号化プロセス４１０において、バイオメトリックパラメータＰ４０２がユーザから取得され、これが鍵として使用されてデータＤが暗号化され（４４０）、暗号文Ｃ４４１を生成する。ＰおよびＣが両方とも記憶装置４５０に保存される。ユーザがデータ４０１を復号化（４２０）したい場合、バイオメトリックパラメータＰ’４６０がユーザから取得され、これが記憶されているバイオメトリックＰ４０２と比較される（４６５）。Ｐ’がＰと一致する場合（４７０）、システムは、アクセスを許可し、Ｐを使用して記憶されている暗号文Ｃ４４１を復号化し（４８０）、データＤ４０１を生成する。Ｐ’がＰと一致しない場合、データは、復号化されない（４７１）。
【００２５】
このような従来技術によるシステムは、記憶媒体が危機にさらされない場合に限ってのみ有効である。攻撃者がこのような媒体にアクセスすることができる場合、攻撃者は、Ｐを取得してデータを復号化する。
【００２６】
従来技術に関連した問題
第１に、ビットに基づく従来技術の方法が提供するセキュリティは、疑わしいものである。これに加えて、バイオメトリックパラメータは、多くの場合、バイナリ値ではなく、実数値または整数値である。この従来技術は、一般に、バイオメトリックパラメータが一様に分布したランダムなビットで構成され、記憶されたバイオメトリックからこれらのビットを正確に求めることは、困難であると仮定する。実際には、バイオメトリックパラメータは、多くの場合、偏っており、これは、セキュリティに悪影響を与える。また、たとえ、攻撃者が、記憶されたバイオメトリックに近似したものしか復元しないとしても、その攻撃は、重大な損害を引き起こす可能性がある。従来技術の方法は、攻撃者が、実際のバイオメトリックを符号化したものから推定することを防止するようには設計されていない。
【００２７】
例えば、米国特許第６，０３８，３１５号は、ランダムな符号語Ｗを追加することによって、参照値Ｒ＝Ｗ＋ＥがバイオメトリックＥを有効に暗号化することに依拠している。しかしながら、その方法が達成するセキュリティは、不十分である。ＲからＥを復元する複数の方法がある。例えば、ベクトルＥが、１に等しいビットを数ビットしか有しない場合、ＲとＷとの間のハミング距離は、小さくなる。したがって、誤り訂正復号器は、ＲからＷを容易に復元することができ、したがって、Ｅを復元することもできる。代替的に、例えば、符号の重みスペクトルが小さく、多くの符号語がオールゼロベクトルの周りに密集する場合といった、符号語の分布が不十分である場合に、攻撃者は、ＲからＥの良好な近似を得ることができる。
【００２８】
第２に、セキュリティが疑わしいことに加えて、従来技術の方法は、記憶されるデータ量が増加するという実用上の不都合も有する。バイオメトリックデータベースは、多くの場合、多数の個人ユーザのデータを記憶するので、ストレージが追加されることによって、システムのコストおよび複雑度は、大幅に増加する。
【００２９】
第３に、多くの従来技術の方法は、高い計算複雑度を有する誤り訂正符号またはアルゴリズムを必要とする。例えば、従来技術のリード−ソロモン復号アルゴリズムおよびリード−マラー復号アルゴリズムは、一般に、符号化されたバイオメトリックの長さにおいて、少なくとも２次の計算複雑度を有し、多くの場合、それよりも高次の計算複雑度を有する。
【００３０】
第４に、従来技術において既知の携帯セキュリティシステムの基本構造に伴う基本的な問題がある。図４に示すような携帯セキュリティシステムは、携帯セキュリティシステム自体が危険にさらされない場合にしか有効であり得ない。ラップトップの携帯セキュリティシステムの例に戻ると、セキュリティは、攻撃者が、ＰおよびＣが記憶されている媒体に物理的にアクセスできない場合にしか有効であり得ない。攻撃者がこのような媒体に、例えば、ハードディスクをラップトップから取り出すことによってアクセスすることができる場合、攻撃者は、Ｃの生成に使用された暗号鍵であったＰを即座に取得し、ひいては、Ｃを復号化する。
【００３１】
従来の携帯セキュリティシステムに伴う主な問題は、ユーザのバイオメトリックパラメータに対応する暗号鍵がその装置に記憶されることである。このため、装置が盗まれれば、記憶されているパラメータを使用してデータが復号化される恐れがある。
【発明の開示】
【発明が解決しようとする課題】
【００３２】
したがって、攻撃者が、暗号化された情報および記憶されているバイオメトリックパラメータの両方にアクセスできる場合であっても、データの復号化が不可能なように、バイオメトリック並びに対応する暗号化された情報を記憶する方法が必要である。
【課題を解決するための手段】
【００３３】
バイオメトリックパラメータは、例えば、人間の顔、音声、指紋、および虹彩から取得され、多くの場合、ユーザ認証およびデータアクセス制御に使用される。バイオメトリックパラメータは、パスワードで行われるように、ハッシュされた形態または暗号化された形態でデータベースに記憶することはできない。その理由は、パラメータが連続的であり、同じユーザについて、ある読み取りから次の読み取りまでに変化することがあるためである。例えば、顔の外観または音声のトーンは、わずかに経時変化することがある。バイオメトリックパラメータがデータベースに記憶される場合、「１度破れば、どこでも実行される」攻撃の対象になる。
【００３４】
本発明の１つの実施の形態は、シンドローム符号、例えば、Ｗｙｎｅｒ−Ｚｉｖ符号化またはＳｌｅｐｉａｎ−Ｗｏｌｆ符号化に基づくシンドローム符号を使用してバイオメトリックデータを保護する。こういったシンドローム符号は、データベースに安全に記憶することが可能でありながら、依然として未処理のバイオメトリックデータに固有の可変性を許容する。
【００３５】
具体的には、本発明によるバイオメトリックシンドロームは、以下の特性を有する。第１に、シンドロームデータベースが危険にさらされた場合、記憶されたシンドローム符号が、システムのセキュリティを巧みに回避するのにほとんど役立たないように、シンドロームは、元のバイオメトリックの特徴に関する情報を有効に隠蔽するか、または、暗号化する。第２に、記憶された各シンドローム符号を復号して、元のバイオメトリックパラメータを生成して、ユーザを認証するか、またはバイオメトリックデータを用いて暗号化されたデータを復号することができる。
【００３６】
シンドローム符号は、ユーザ認証およびデータ暗号化に使用することができる。
【発明を実施するための最良の形態】
【００３７】
本発明の実施の形態は、以下の構成要素：シンドローム符号化器およびバイオメトリックパラメータを安全に記憶するためのハッシュ方法、バイオメトリック鍵を使用して暗号化されたデータを安全に記憶するためのシンドローム符号に基づく暗号方法、並びに前者の２つの方法等の安全なバイオメトリック用途に使用されるシンドローム符号を最適化する方法を含む。各方法を別個のサブセクションで説明する。
【００３８】
安全なバイオメトリックパラメータのためのシンドロームおよびハッシュ方法
図３は、本発明によるシンドロームおよびハッシングに基づくバイオメトリックセキュリティシステム３００を示している。本発明による方法は、シンドローム符号で測定されたバイオメトリックパラメータを圧縮して、圧縮されたシンドローム符号を生成する。従来の圧縮と異なり、シンドローム符号によって生成されたシンドローム符号は、元のバイオメトリックデータと無関係である。したがって、記憶されたシンドローム符号を使用して、元のバイオメトリックパラメータと近似したものを復号することはできない。その結果生成された、圧縮されたシンドローム符号およびそのシンドローム符号のハッシュが、バイオメトリックデータベースに記憶される。
【００３９】
ユーザを認証するために、バイオメトリックパラメータが再び測定される。これらのバイオメトリックパラメータは、記憶されたシンドローム符号と結合されて、元のバイオメトリックパラメータが復号する。シンドロームの復号が失敗すると、ユーザは、アクセスを拒否される。シンドロームの復号が成功すると、元のバイオメトリックパラメータが使用されて、ユーザの真正性が検証される。
【００４０】
登録フェーズ
登録フェーズ３１０では、ユーザのバイオメトリックデータが取得される。例えば、バイオメトリックデータは、顔の画像、音声の記録、指紋の画像、または虹彩をスキャンしたものから導き出される。以下、バイオメトリックデータは、ユーザから感知、測定、またはその他の方法で取得される未処理のバイオメトリック信号を指す。特徴がバイオメトリックデータから抽出される。この特徴は、ｄ次元特徴ベクトルに配置される。この特徴ベクトルは、登録バイオメトリックパラメータ３０１を形成する。様々な形式のバイオメトリックデータから特徴を抽出する方法は、上述したように当該技術分野において既知である。特徴ベクトルをバイオメトリックパラメータおよび最適なシンドローム符号に変換することについて、さらに詳細に、以下説明する。
【００４１】
バイオメトリックパラメータＥ３０１は、シンドローム符号化器３３０を使用して符号化され、登録シンドローム符号Ｓ３３１が生成される。次に、メッセージ認証符号またはハッシュ関数が、登録シンドローム符号Ｓに適用され（３４０）、登録ハッシュＨ３４１が生成される。このハッシュ関数は、Ron Rivest著「The MD5 Message Digest Algorithm」（RFC 1321, April 1992）に記載されている既知のＭＤ５暗号ハッシュ関数とすることができる。登録シンドローム符号−ハッシュの対（Ｓ，Ｈ）３３１、３４１が、バイオメトリックデータベース３５０に記憶される。
【００４２】
任意のタイプのシンドローム符号、例えば、上述したＳＷ符号またはＷＺ符号を使用することができる。本発明の好ましい実施の形態は、いわゆる「繰り返し累積符号（repeat-accumulate code）」、すなわち「積累積符号（product-accumulate code）」から導出された符号、および、本発明において「拡張ハミング累積符号（extended Hamming-accumulate code）」と呼ぶ符号を使用する。
【００４３】
本発明では、一般に、これらの符号を直列連鎖累績（ＳＣＡ：serially concatenated accumulate）符号と呼ぶ。一般的な意味でのこれらの部類の符号に関する、より多くの情報については、J. Li、著他「Product Accumulate Codes: A Class of Codes With Near-Capacity Performance and Low Decoding Complexity」（IEEE Transactions on Information Theory, Vol. 50, pp. 31-46, January 2004）IEEE Communications Letters, 2004に投稿されたM. IsakaおよびM. Fossorier著「High Rate Serially Concatenated Coding with Extended Hamming Codes」、並びにD. DivsalarおよびS. Dolinar著「Concatenation of Hamming Codes and Accumulator Codes with High Order Modulation for High Speed Decoding」（IPN Progress Report 42-156, Jet Propulsion Laboratory, Feb. 15, 2004）を参照願いたい。
【００４４】
Yedidia他によって２００４年８月２７日に出願された「Compressing Signals Using Serially-Concatenated Accumulate Codes」という発明の名称の米国特許出願番号第１０／９２８４４８号（参照により本明細書に援用される）は、本発明によって使用されるようなＳＣＡ符号に基づく、本発明の好ましいシンドローム符号化器のオペレーションを記載している。
【００４５】
バイオメトリックパラメータ３０１の本発明のシンドローム符号化器３３０は、多数の利点を有する。このシンドローム符号化器３３０は、整数値の入力に対してオペレーションを行うことができる。これとは対照的に、従来技術の符号化器は、一般に、バイナリ値の入力に対してオペレーションを行う。このシンドローム符号化器は、バイオメトリックデータベース３５０の記憶要件を最小にするために、非常に高い圧縮率を有する。このシンドローム符号化器は、レート適合型であり、インクリメンタル形にオペレーションを行うことができる。先に送信されたシンドロームビットの情報を無駄にすることなく、必要に応じて、より多くのビットを送信することができる。
【００４６】
認証フェーズ
認証フェーズ３２０では、バイオメトリックデータが、ユーザから再び取得される。特徴が抽出されて、認証バイオメトリックパラメータＥ’３６０が得られる。データベース３５０が検索されて、このユーザの一致する登録シンドローム符号Ｓ３３１および登録ハッシュＨ３４１が突き止められる。
【００４７】
この検索は、データベース３５０のあらゆるエントリ（Ｓ−Ｈ対）をチェックすることもできるし、ヒューリスティックに順序付けられた検索を使用して、一致するエントリを見つけるプロセスを高速化することもできる。具体的には、本発明においてデータベースにおけるｉ番目のシンドローム符号−ハッシュの対を（Ｓｉ，Ｈｉ）と示す場合、全数検索は、まず、シンドローム復号をＥ’およびＳ１に適用し、シンドローム復号器の出力のハッシュをＨ１と比較する。アクセスが拒否される場合、同じプロセスが（Ｓ２，Ｈ２）で試みられ、次いで（Ｓ３，Ｈ３）で試みられ、すべてのエントリが試行されるか、または、アクセスが許可されるまで、以下同様に試みられる。
【００４８】
登録ユーザ名等のサイド情報が利用可能である場合、そのサイド情報を使用して検索を高速化することができる。例えば、登録ユーザ名のハッシュが，登録フェーズの期間中にＳ−Ｈの対で記憶される。次に、認証フェーズでは、ユーザが認証ユーザ名を供給し、システムがその認証ユーザ名のハッシュを求め、一致する、ハッシュされた登録ユーザ名を有するＳ−Ｈ対を求めてデータベースを検索し、そして、その結果のＳ−Ｈ対でＥ’の認証を試みる。
【００４９】
具体的には、シンドローム復号器３７０が、登録シンドロームＳに適用され、認証パラメータＥ’３６０が「サイド」情報として働く。シンドローム復号器は、一般に、当該技術分野において既知である。通常、確率伝播またはターボ符号を使用する復号器は、低い複雑度で優れた誤差耐性を有する。シンドローム復号器３７０の出力は、復号された登録パラメータＥ’’３７１である。復号された値Ｅ’’３７１は、シンドローム符号Ｓ３３１を生成するのに使用される元のバイオメトリックパラメータＥ３０１の推定値である。ハッシュ関数３４０がＥ’’３７１に適用されて、認証ハッシュＨ’３８１が生成される。
【００５０】
登録値Ｈ３４１と認証値Ｈ’３８１とが比較される（３９０）。それらの値が一致しない場合、アクセスは、拒否される（３９２）。そうでない場合、値Ｅ’’３８１は、元のバイオメトリックＥ３０１と実質的に一致する。この場合、ユーザは、アクセス許可を受けることができる（３９１）。
【００５１】
これに加えて、復号されたパラメータＥ’’３８１と認証バイオメトリックパラメータＥ’３６０との間で直接比較を行って、ユーザを認証することもできる。例えば、Ｅ’およびＥ’’が顔認識システムのバイオメトリックパラメータに対応する場合、顔の類似性を比較するための従来のアルゴリズムをパラメータＥ’およびパラメータＥ’’に適用することができる。
【００５２】
シンドロームに基づくデータ暗号
図５は、データ５０１の符号化５１０および復号化５２０の方法５００である。符号化プロセス５１０において、第１のバイオメトリックパラメータＰ５０２が第１のユーザから取得される。このパラメータが使用されて、入力データＤ５０１が暗号化され（５４０）、暗号文Ｃ５４１が生成される。しかし、従来技術とは対照的に、第１のバイオメトリックパラメータＰは、決してメモリに記憶されない。メモリに記憶されることに代えて、シンドローム符号化器５３０が第１のバイオメトリックパラメータＰを符号化して、シンドローム符号Ｓ５３１を生成する。ＳおよびＣは、互いに関連付けられ、この対（Ｓ，Ｃ）５３２がメモリ５５０に記憶される。本発明の１つの実施の形態では、入力データは、登録プロセス中にユーザから取得される未処理のバイオメトリックデータである。
【００５３】
暗号文５４１を復号化したい（５２０）場合、第２のバイオメトリックパラメータＰ’５６０が第２のユーザから取得される。記憶されているシンドローム符号Ｓ５３１は、第２のバイオメトリックパラメータを使用してシンドローム復号化され（５７０）、第３のバイオメトリックパラメータＰ’’５７１が生成される。次に、第３のバイオメトリックパラメータＰ’’が使用されて暗号文Ｃ５４１が復号化され（５８０）、出力データＤ’５０９が生成される。明らかなことに、第２のバイオメトリックパラメータおよび第３のバイオメトリックパラメータが第１のバイオメトリックパラメータと一致しない場合、出力データＤ’５０９は、入力データＤ５０１と一致しない。出力データは、第１のユーザと第２のユーザが同一人物である場合にのみ入力データと厳密に一致する。
【００５４】
この方法は、以下の利点を有する。攻撃者がシンドローム符号および暗号文（Ｓ，Ｃ）にアクセスできても、データを復号化することはできない。これは、暗号鍵、すなわち、第１のバイオメトリックパラメータＰは、シンドローム符号から復元できないためである。さらに、シンドローム符号の誤り修正性により、第２のバイオメトリックパラメータＰ’が第１のバイオメトリックパラメータＰとわずかに異なる場合であっても、適宜設計されたシンドローム復号器は、暗号鍵Ｐ５０２として使用された第１のバイオメトリックパラメータと全く同じである第３のバイオメトリックパラメータＰ’’を生成することに成功することができる。
【００５５】
シンドローム符号化は、バイオメトリックパラメータを安全に記憶する効率的な方法を提供し、バイオメトリック情報を安全に記憶する他の方法に適用することができる。特徴ベクトルは、バイオメトリックデータから抽出できることに留意願いたい。したがって、上述したバイオメトリックパラメータは、いずれも、対応する特徴ベクトルで置き換えることができる。
【００５６】
バイオメトリックパラメータを暗号化された形で記憶することのさらなる利点は、これにより、安全なバイオメトリック記憶アプリケーションが、バイオメトリック認証アプリケーションに使用される特徴ベクトルと異なる特徴ベクトルで動作することが可能になることである。例えば、指紋認証システムは、多くの場合、指紋の画像から抽出される、いわゆる「特徴点（minutiae）」に基づく特徴ベクトルを使用する。同様に、虹彩認識システムは、時に、虹彩画像をガボールフィルタバンクに通すことから抽出される特徴を使用する。
【００５７】
多くの場合、バイオメトリック認証、例えば、顔認証または指紋識別に理想的な特徴ベクトルは、シンドローム符号化／復号化に理想的な特徴ベクトルと異なり得る。多くの場合、これは、認識システムまたは識別システムの分類器、例えば、ガウス混合モデル（ＧＭＭ）、ニューラルネットワーク、または隠れマルコフモデルに基づく分類器をトレーニングするプロセスが、本明細書において説明するように、シンドローム符号化器および復号器の確率伝搬復号器と併せて使用されるヒストグラムのトレーニングに使用されるプロセスと異なる特徴ベクトルを生成することによる。
【００５８】
図６は、入力バイオメトリックデータ６０１を暗号化したものを記憶する方法６００を示す。上述したように、バイオメトリックデータは、ユーザのバイオメトリック特徴を測定または感知するために使用される未処理の信号から導き出される。
【００５９】
アクセス制御システムの登録フェーズ６１０において、例えば、第１のバイオメトリックデータＢ６０１がユーザから取得される。次に、第１のバイオメトリックパラメータＰ６０２の特徴ベクトルが、第１のバイオメトリックデータＢ６０１から取得される。第１のバイオメトリックデータＢは、第１のバイオメトリックパラメータＰを暗号鍵として使用して暗号化され（６４０）、暗号文Ｃ６４１が生成される。さらに、第１のバイオメトリックパラメータは、シンドローム符号化され（６３０）、シンドローム符号Ｓ６３１が生成される。次に、関連付けられた対（Ｓ，Ｃ）６３２がバイオメトリックデータベース６５０に記憶される。
【００６０】
認証フェーズ６２０において、第２のバイオメトリックデータＢ’６６０がユーザから取得される。この第２のデータを使用して、第２のバイオメトリックパラメータＰ’６６１の特徴ベクトルが生成される。次に、シンドローム復号器６７０が第１のバイオメトリックパラメータを復号化して、第３のバイオメトリックパラメータＰ’’６７１を生成する。次に、この第３のバイオメトリックパラメータが鍵として使用されて、暗号文Ｃが復号化され（６８０）、第３のバイオメトリックデータＢ’’６８１が生成される。この時点で、認証バイオメトリックデータＢ’および復号化されたバイオメトリックデータＢ’’がバイオメトリック認識方法６９０によって比較され、特定の機能へのアクセスが許可される（６９１）か、それとも拒絶される（６９２）かが判断される。前のように、アクセスは、第１のバイオメトリックデータと第３のバイオメトリックデータが全く同一である、すなわち、第１のユーザと第２のユーザが、同じ人物である場合のみ許可される。
【００６１】
別の変形では、比較ステップは、バイオメトリックデータから抽出された特徴ベクトルを使用することができる。特徴ベクトルは、バイオメトリックパラメータと同じである必要はない。さらに、比較されている２つの特徴ベクトルは、認証ステップがまったく異なるプロセスを使用し得るため、実質的に同じである必要があるだけである。したがって、特徴ベクトルは、特定のユーザを経時にわたって特徴付ける、より広い範囲のバイオメトリックデータ変化を許すことができる。
【００６２】
図６に示すプロセスに伴ういくつかの利点がある。認証システムは、従来の認証システムをステップ６９０において使用することができる。さらに、シンドローム符号化器／復号器により使用されるバイオメトリックパラメータＰおよびＰ’は、バイオメトリック検証ステップ６９０により使用されるパラメータまたは特徴ベクトルから独立して選択することができる。さらに、シンドローム符号は、バイオメトリックパラメータを安全に記憶する効率的な方法である。しかし、図６の方法は、安全なバイオメトリック記憶方法がバイオメトリック検証方法から独立した特徴ベクトルを使用できるように、バイオメトリックパラメータを安全に記憶する他の方法に適用することも可能である。
【００６３】
安全なバイオメトリックパラメータの最適なシンドローム符号の設計
一般に、シンドローム符号を使用してバイオメトリックパラメータおよびバイオメトリック特徴を保護するに当たり、セキュリティと精度との間にトレードオフがある。具体的には、任意のシンドローム符号の鍵となるパラメータは、符号中のビット数である。多数のビットを有するシンドローム符号は、バイオメトリックデータについて、より多くの情報を伝達し、バイオメトリックデータのノイズおよびばらつきを許容しやすくする。これとは対照的に、小さなシンドローム符号ほど攻撃者に与える情報は少ないが、誤りやすい。
【００６４】
極端な一例として、シンドローム符号の長さが基礎を成すバイオメトリックデータの長さとほぼ同じである場合、元のバイオメトリックデータをシンドローム符号のみからそのまま復元できるため、いかなる量のノイズも許容され得る。もちろん、この場合、シンドローム符号を取得する攻撃者は、おそらく、バイオメトリックデータも復元することができ、システムのセキュリティを危険にさらす。
【００６５】
これとは反対の極端な一例として、非常にビット数の少ないシンドローム符号は、攻撃者がバイオメトリックデータをシンドローム符号から復元できないという点で、極めて良好なセキュリティを提供する。しかし、この場合、登録バイオメトリックデータと認証バイオメトリックデータとの間で許容される変化が限られる。
【００６６】
明らかなことに、シンドロームに基づく符号化器および復号器は、セキュリティとバイオメトリック変化の許容とのバランスをとるシンドローム符号の長さを選択すべきである。しかし、入念に設計されたシンドローム符号は、誤差耐性を向上させることができる。
【００６７】
シンドローム符号の設計を、図１２に示すように、以下の用語を用いて説明する。この設計は、バイオメトリックデータ１２０１、例えば、顔の画像から開始する。完全な特徴ベクトル１２０２がバイオメトリックデータから抽出される。完全な特徴ベクトル１２０２は、シンドローム特徴ベクトル１２０３に低減され、シンドローム特徴ベクトルを使用して最適なシンドローム符号１２０４が設計される。
【００６８】
図７は、最適なシンドローム符号を構築するプロセス７００を示す。トレーニングバイオメトリックデータ１２０１が取得される。バイオメトリックデータを使用して誤差ヒストグラム８９０が生成される（８００）。誤差ヒストグラムを使用してシンドローム符号の特徴ベクトルが選択される（９００）。この文脈の中では、「完全な特徴ベクトル」１２０２という用語を用いてすべてのバイオメトリックパラメータを表し、「シンドローム特徴ベクトル」１２０３という用語を用いて完全な特徴ベクトルの部分集合を指す。シンドローム特徴ベクトルは、異なる特徴空間に変形することができる。
【００６９】
シンドローム特徴ベクトル１２０３が選択された後、シンドローム特徴ベクトルの異なる係数間の相関を測定する（１０００）。シンドローム特徴ベクトルの誤差統計および係数間相関を用いることにより、密度発展法７４０を適用して、所与の長さの最適なシンドローム符号１２０４をもたらす次数分布を探す。シンドローム特徴ベクトルおよびシンドローム符号が選択された後、係数間相関を利用した確率伝搬復号器を構築する（１１００）。
【００７０】
図７中の各構成要素をさらに詳細に説明する前に、以下の用語も定義する。本明細書では、「硬」特徴ベクトルという用語を用いて特徴ベクトルを量子化したものを指し、「軟」特徴ベクトルという用語を用いて特徴ベクトルの量子化されていないもの、または「硬」特徴ベクトルよりも細かく量子化したものを指す。バイオメトリックパラメータによっては大きな数値範囲にわたる整数および実数を含み得るため、量子化が使用される。暗号化プロセス、鍵生成プロセス、および他の認証プロセスは、小範囲にわたる整数の場合に最も上手く働く。
【００７１】
「硬」特徴ベクトルと「軟」特徴ベクトルとを区別する理由は、シンドローム符号が「硬」特徴ベクトルから形成されることによる。したがって、「硬」特徴ベクトルは、通常、量子化される。これとは対照的に、認証フェーズでは、シンドローム復号器は、「軟」特徴ベクトルをシンドローム符号と組み合わせて「硬」特徴ベクトルを復号化する。したがって、「軟」特徴ベクトルは、量子化する必要がないか、またはシステムの誤差耐性を向上させるために別々に量子化され得る。
【００７２】
一般に、完全な特徴ベクトルをバイオメトリックデータから抽出する複数の方法の可能性があり、また同様に「硬」特徴ベクトルおよび「軟」特徴ベクトルを完全な特徴ベクトルから抽出する複数の方法があり得る。このような場合、図７のプロセスを各可能性に適用し、トレーニング中に最も良い全体結果をもたらす特徴ベクトルを選択する。
【００７３】
誤差ヒストグラムの構築
図８は、誤差ヒストグラム８９０を生成するプロセス８００を示す。まず、異なるときに取得された特定のユーザのトレーニングバイオメトリックデータを取得する（８１０）。次に、１対のバイオメトリックパラメータＢおよびＢ’を選択し（８２０）、完全な「軟」特徴ベクトルＶＳ（Ｂ）（８３０）および完全な「硬」特徴ベクトルＶＨ（Ｂ’）（８４０）を求める。次に、完全な特徴ベクトル中の各位置または各次元ｉごとに、ＶＳ（Ｂ）の位置ｉから、ＶＨ（Ｂ’）の対応する位置ｉにある値を推定し（８４５）、この推定が正しいか否かを判断する（８５０）。この推定が正しくない場合、誤差ヒストグラム８９０のＶＨ（Ｂ’）およびＶＳ（Ｂ）の位置ｉにある対応する値のビンを増分する（８７０）。このプロセスを各位置ｉに対して完了した後、バイオメトリックＢおよびＢ’のすべての対が処理されたか否かを調べる（８６０）。まだの場合、ステップ８２０に戻り、別のバイオメトリックパラメータ対を選択する。すべての対がすでに処理されている場合、誤差ヒストグラムが完了し、プロセスは、終了する（８８０）。
【００７４】
シンドローム特徴ベクトルの選択
図９は、図８の誤差ヒストグラムを用いて特徴ベクトルを選択するプロセス９００を示す。まず、誤差ヒストグラムが最も信頼性の高い位置から最も信頼性の低い位置９２０までソートされる（９１０）。具体的には、Ｅ（ｉ）がＶＳ（Ｂ）の位置ｉからＶＨ（Ｂ’）の位置ｉを予測する際の平均誤差である場合、位置ｉは、Ｅ（ｉ）＜Ｅ（ｊ）のときに位置ｊよりも信頼性が高いものとみなされる。誤差ヒストグラムがソートされた後、誤差ヒストグラムからの次に信頼性の高い位置をシンドローム特徴ベクトルに含め（９３０）、その時点のシンドローム特徴ベクトルに最良のシンドローム符号を構築し（９４０）、最新位置を含めることで、セキュリティまたは誤差耐性が増大するか否かをテストする（９５０）。セキュリティまたは誤差耐性が増大する場合、さらなる位置をシンドローム特徴ベクトルに加え続ける。増大しない場合、最も新しく追加された位置を特徴ベクトルから除去し（９６０）、プロセスを終了する（９７０）。
【００７５】
セキュリティレベルを指定し、誤差耐性を最適化することが望まれる場合、以下のステップをステップ９４０および９５０に使用することができる。まず、ステップ９４０において、その時点で特徴ベクトル中にある位置の数に対応する長さＮを有する新しいシンドローム符号が、固定次数分布からＳ個のシンドロームを有する低密度パリティチェック（ＬＤＰＣ）符号を生成することによって構築される。この場合、セキュリティレベルは、量Ｎ−Ｓを固定し、それをプロセス全体を通して一定に保つことによって一定に保たれる。次に、バイオメトリックデータのランダムなバイオメトリックサンプルがデータベースから選択され、ＬＤＰＣ符号のパリティチェック行列を適用することによってシンドローム符号にマッピングされ、その結果生成されるシンドローム符号は、同じユーザからの別のランダムなバイオメトリックサンプルに適用される確率伝搬を使用して復号化される。これを多数回繰り返すことで、所与の特徴ベクトルのシンドローム符号の誤差耐性の推定が得られる。別法として、より高い計算複雑性が設計プロセスにおいて許容される場合、Richardson他著「Design of capacity-approaching irregular low-density parity-check codes」（IEEE Transactions on Information Theory, vol. 47, issue 2, pp. 619-637, February 2001）（参照により本明細書に援用される）において考察される密度発展法プロセスを使用して、符号の次数分布を最適化するとともに、誤差確率をより正確に推定することができる。
【００７６】
誤差耐性レベルを指定し、最良のセキュリティを獲得することが望まれる場合、以下のステップをステップ９４０および９５０に使用することができる。まず、ステップ９４０において、その時点で特徴ベクトル中にある位置の数に対応する長さＮを有する新しいシンドローム符号が、密度発展法を用いて設計される。具体的には、レートの異なる一連の符号が、密度発展法によって評価される指定の誤差耐性レベルを満たす最高レートの符号が見つかるまで密度発展法を用いて構築される。
【００７７】
本発明では、このプロセスにより選択される特徴ベクトルを「シンドローム特徴ベクトル」と呼ぶ。この理由は、特徴ベクトルがシンドローム符号用に特に設計された特徴ベクトルであることによる。この特徴ベクトルは、顔認識または物体認識等のバイオメトリック認識用に構築される他のタイプの特徴ベクトルと異なる性質を有し得ることに留意されたい。
【００７８】
係数間相関の測定
シンドローム特徴ベクトルを選択した後、次のステップは、係数間相関を測定することである。この情報は、図７により生成される誤差ヒストグラムから抽出することができない。この理由は、誤差ヒストグラムが完全な特徴ベクトル１２０２に対して生成されたのに対して、ステップ９００は、完全な特徴ベクトル中の位置の部分集合のみを選択してシンドローム特徴ベクトル１２０３を生成することによる。
【００７９】
図１０は、バイナリシンドローム特徴ベクトルでの一次相関を測定するプロセス１０００を示す。このプロセスは、非バイナリ特徴ベクトルまたは、より高次の相関に適用することもできる。まず、バイオメトリックトレーニングデータセットからの要素が選択され、シンドローム特徴ベクトルがその要素から抽出される。次に、カウンタ変数ｉがゼロに初期化される（１０１０）。次に、位置ｉが０であるか、それとも１であるかをテストし（１０２０）、前者の場合にはステップ１０３０に進み、後者の場合にはステップ１０４０に進む。次に、位置ｉ−１、すなわち、前の位置が０であったかそれとも１であったかをテストし（１０３０）、ヒストグラムの適当なビンを増分する（１０３５）。直観的に、ビンｐ００は、０の後に０が続くことをカウントし、ビンｐ０１は、０の後に１が続くことをカウントし、以下同様である。次に、カウンタｉを増分し（１０５０）、シンドローム特徴ベクトルにまだ位置が残っているか否かをテストし（１０６０）、次の位置に対してプロセスを繰り返す。そうではなく、各位置をすでに処理し終えている場合には、プロセスを終了する（１０７０）。
【００８０】
図１０のプロセスがバイオメトリックトレーニングセットの各要素に対して行われた後、ビンｐ００、ｐ０１、ｐ１０、およびｐ１１の値をバイオメトリックトレーニングセットのサイズで割り、シンドローム特徴ベクトルの一次相関を測定する。
【００８１】
密度発展法を使用しての最適なシンドローム符号の構築
シンドローム特徴ベクトル１２０３が選択され、係数間相関が測定された後、密度発展法を用いてシンドローム符号１２０４を設計する。具体的には、ＬＤＰＣシンドローム符号の場合、このシンドローム符号の次数分布を設計する。このような設計は、２つの理由により望ましい。第１に、ステップ９００において設計される初期シンドローム符号は、シンドローム特徴ベクトル１２０３が選択される前に選択された固定次数分布を使用した可能性がある。第２に、初期シンドローム符号は、係数間相関の知識を利用しなかった。この理由は、この相関が、シンドローム特徴ベクトルが選択された後でしか測定できないことによる。
【００８２】
最適な次数分布を正確に構築するために、密度発展技法を適用していくつかの候補次数分布を生成する。
【００８３】
しかし、当該技術分野において既知の従来の密度発展法プロセスは、係数間相関を考慮に入れていない。このため、密度発展法によって生成される候補次数分布が、係数間相関がない場合に適当な場合であっても、それら候補次数分布のパフォーマンスは、一般に、係数間相関が存在する場合には異なるであろう。
【００８４】
シンドローム符号に最も良い次数分布を取得するために、バイオメトリックトレーニングデータセットに対して、密度発展法によって取得される候補次数分布を比較し、パフォーマンスが最も良い次数分布を選択する。代替の実施の形態では、従来の密度発展法アルゴリズムを、係数間相関を考慮に入れるように変更する。
【００８５】
シンドローム符号のための確率伝搬復号器の構築
シンドローム符号を設計するに際しての最終ステップは、関連する確率伝搬シンドローム復号器を構築することである。係数間相関のないアプリケーションのための確率伝搬復号器は、既知である。しかし、従来の復号器は、係数間相関に対処するように設計されていない。具体的には、従来の確率伝搬方法は、「メッセージ」を変数ノードから検査ノードに渡し、積和式を使用して再び戻す。これは、Kschischang他著「Factor graphs and the sum-product algorithm」（IEEE Transactions on Information Theory, vol. 47, issue 2, pp. 498-519, February 2001）（参照により本明細書に援用される）に説明されている。
【００８６】
図１１に示すように、本発明による確率伝搬因子グラフの構築１１００は、従来の検査ノード１１１０および変数ノード１１２０に加えて、相関ノード１１３０を含む。具体的には、相関ノードは、連続した変数ノードの各対間に追加される。メッセージを変数ノードから隣接する検査ノードに渡す方法は、その他のメッセージで乗算される、隣接する各相関因子ノードからの追加メッセージを含むように変更される。
【００８７】
具体的には、Kschischang他の表記を用いて、μｙ→ｆ（ｘ）が検査ｆから変数ノードｙへの状態ｘの入力メッセージであり、Ｌ（ｘ）が左側の相関ノードからの入力メッセージである場合、変数ノードから右側の相関ノードへの出力メッセージは、
Ｌ（ｘ）・Πμｙ→ｆ（ｘ）
であり、左側の相関ノードへの出力メッセージは、
Ｒ（ｘ）・Πμｙ→ｆ（ｘ）
であり、式中、Ｒ（ｘ）は、右側の相関ノードからの入力メッセージである。
【００８８】
本明細書では、本発明の実施の形態により相関ノードに、また相関ノードからメッセージを渡す方法も説明する。具体的には、メッセージＬ（ｘ）およびＲ（ｘ）を求める手順を説明する。μ（０）が左側の相関ノードへの入力メッセージである場合、相関ノードの右側への出力メッセージは、相関ノードの右側にある変数ノードへの入力メッセージであり、
Ｌ（０）＝ｐ００・μ（０）＋ｐ１０・μ（１）
および
Ｌ（１）＝ｐ１０・μ（０）＋ｐ１１・μ（１）
であり、式中、ｐ００、ｐ０１、ｐ１０、およびｐ１１の各項は、図１０に示すように、測定される一次相関値である。
【００８９】
同様に、相関ノードの左側への出力メッセージは、相関ノードの左側の変数ノードへの入力メッセージであり、
Ｒ（０）＝ｐ００・μ（０）＋ｐ０１・μ（１）
および
Ｒ（１）＝ｐ０１・μ（０）＋ｐ１１・μ（１）
である。
【００９０】
虹彩バイオメトリックパラメータのシンドローム符号設計
次に、上記手順を虹彩バイオメトリックパラメータという具体的なケースにどのように適用するかについて説明する。完全な「硬」特徴ベクトルを、J. Daugman著「How iris recognition works」（IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, issue 1, pp. 21-30, January 2004）（参照により本明細書に援用される）に説明されているように、１組のガボールフィルタから抽出されるビットシーケンスであるように選択する。
【００９１】
完全な「硬」特徴ベクトルがバイナリであるのに対して、完全な「軟」特徴ベクトルを４成分のものとして選択する。具体的には、完全な「軟」特徴ベクトルの位置ｉの値に、「硬」特徴ベクトルのその位置の値の最良推定を選択し、信頼性レベルを示すビットをさらに添付する。具体的には、その位置の決定に対して確信があったか否かを示すビットを添付する。
【００９２】
例えば、「硬」特徴ベクトルのいくつかの位置の特徴は、例えば、まぶたまたはまつげで覆われているために予測することが困難である場合があり、こういった位置は「不確実」信頼性値を受け取るべきである。
【００９３】
次に、バイオメトリックトレーニングデータを使用して、図８に関連して上述したように誤差ヒストグラムを生成し、次に、図９の特徴ベクトル設計方法を適用する。完全な特徴ベクトルは、長さ約１０，０００を有するが、本発明は、多くの位置に関連する特徴の信頼性が低いことを発見した。例えば、目の上に対応する特徴ベクトルの成分は、多くの場合、まぶたまたはまつげで覆われている。有用性が最も低い位置が図９の手順によって破棄された後には、シンドローム特徴ベクトル内におよそ２０００の最も信頼性の高い位置が残る。
【００９４】
図７のステップ９００というこの時点で停止する場合、結果生成されるシンドローム符号は、一人のユーザの虹彩バイオメトリックパラメータの自然な変化を許容するだけの誤差耐性を持たない。具体的には、ある日に取得され、別の日に取得された同じ虹彩からの別のバイオメトリックと組み合わせられたユーザの虹彩のシンドローム符号は、約１２％で復号化に失敗する。これは、図７の残りのステップが必要であることの正当性を示す。
【００９５】
図１０の手順を用いて一次相関を測定した後、「硬」シンドローム特徴ベクトル中のビットが、隣接ビットと同じ値をとる可能性が、隣接ビットの逆の値をとる可能性よりも約２倍高かったことを検出する。次に、図７のステップ７４０に続き、密度発展法を用いて高相関を利用して最適化されたシンドローム符号を構築する。最後に、ステップ１１００に続き、高い一次相関を考慮に入れた確率伝搬復号器を構築する。
【００９６】
これらのステップ後に、初期符号よりも信頼性が１桁高いシンドローム符号がもたらされ、かくして、図７の全体手順に従うことの利点を実証する。
【００９７】
発明の効果
本発明は、バイオメトリックパラメータに基づく安全なユーザ認証を達成する。本発明は、元のバイオメトリックデータの代わりに、シンドローム符号が記憶されるので安全である。これによって、データベースにアクセスする攻撃者が、基礎を成すバイオメトリックデータを知ることが防止される。
【００９８】
攻撃者がシンドローム符号Ｓのみを使用して行うことができる、元のバイオメトリックパラメータＥの最も良い可能な推定を、複数の記述の既知の問題からの従来のツールを使用して制限することが可能である。これについては、例えば、V. K. Goyal著「Multiple description coding: compression meets the network」（IEEE Signal Processing Magazine, Vol. 18, pp. 74-93, September 2001）を参照願いたい。さらに、推定の質が絶対誤差測定を介して測定されようと、２乗誤差を介して測定されようと、加重誤差測定を介して測定されようと、または任意の誤差関数を介して測定されようと、これらの限界を作成することが可能である。これとは対照的に、すべての従来技術の方法は、バイナリ値に基づいている。そこで、セキュリティは、ハミング距離に依存する。
【００９９】
基本的に、シンドローム符号Ｓのセキュリティは、シンドローム符号Ｓが元のバイオメトリックパラメータＥの圧縮されたものであるということに起因する。さらに、この圧縮表現は、Ｅの「最下位ビット」に対応する。データ圧縮理論からの既知のツールを使用すると、高圧縮を有するシンドローム符号が使用される場合、これらの最下位ビットが生成できる、元のパラメータＥの推定は、いくら良くても不十分なものであることを証明することが可能である。これについては、例えば、Effros著「Distortion-rate bounds for fixed- and variable-rate multiresolution source codes」（IEEE Transactions on Information Theory, vol. 45, pp. 1887-1910, September 1999）並びに、SteinbergおよびMerhav著「On successive refinement for the Wyner-Ziv problem」（IEEE Transactions on Information Theory, vol. 50, pp. 1636-1654, August 2004）を参照願いたい。
【０１００】
第２に、本発明は、偽造が、少なくとも、基礎を成すハッシュ関数における衝突を見つけるのと同程度に困難であるので、安全である。特に、復号されたバイオメトリックＥ’’のハッシュＨ’が元のハッシュＨと一致する場合に、システムは、認証フェーズにおいてシンドローム対（Ｓ，Ｈ）のみを受け付ける。ＭＤ５等の暗号ハッシュ関数について、Ｅとは異なるが、Ｅのハッシュと一致するハッシュを有する要素Ｅ’’を見つけることは、一般に不可能であると考えられる。したがって、シンドローム復号が、適切なハッシュでＥ’’の復号に成功した場合に、システムは、Ｅ’’が実際にＥと同じであり、すべての認証判定は、元のバイオメトリックパラメータで行われることを確信することができる。
【０１０１】
第３に、本発明は、シンドロームＳを生成する際に、元のバイオメトリックパラメータＥを圧縮する。多くのユーザ用のバイオメトリックデータベースは、特に、バイオメトリックデータの問いが、大量のデータ、例えば、顔画像または音声信号を必要とする場合に、大量のストレージを必要とする可能性がある。したがって、必要とされるストレージを減少させることによって、コストおよび誤差耐性の双方で大幅な改善を生み出すことができる。これとは対照的に、バイオメトリックデータの安全な記憶のためのほとんどの従来技術の方法では、実際には、暗号化または誤り訂正のオーバーヘッドによって、記憶されるデータのサイズが増加し、したがって、安全でないシステムよりも多くのストレージが必要とされる。
【０１０２】
第４に、本発明は、シンドローム符号の理論を基に築かれているので、高度な符号構築アルゴリズムおよび復号アルゴリズムを適用することができる。特に、本発明によるシンドローム符号化によって、バイナリ符号の構築およびマルチレベル符号の構築の双方について、既知のビタビアルゴリズム、確率伝播、およびターボ復号を使用する軟復号の使用が容易になる。これとは対照的に、ほとんどの従来技術の方法は、バイナリ符号、リードソロモン符号、および代数的復号に基づいているので、バイオメトリックデータがバイナリ値ではなく実数値を取る場合に、軟復号を有効に適用することができない。例えば、いくつかの方法は、具体的には、登録フェーズにおいて、バイオメトリックデータとランダムな符号語とのＸＯＲを計算して、基準値を生成することを必要とし、認証フェーズにおいて、その基準値とバイオメトリックデータとのＸＯＲを計算することを必要とする。
【０１０３】
第５に、安全なバイオメトリックに関するほとんどの従来技術は、誤り訂正符号化を使用するのに対して、本発明は、シンドローム符号化を使用する。誤り訂正符号化の計算複雑度は、通例、入力サイズにおいて超線形である。これとは対照的に、さまざまなタイプの低密度パリティチェックに基づくシンドローム符号を使用することによって、シンドローム符号化の計算複雑度が、入力サイズにおいて線形にしかならないシンドローム符号化器を構築することが容易である。
【０１０４】
第６に、シンドローム符号化のフレームワークを使用することによって、Yedidia他によって記載されているＳＣＡ符号のような新しい強力な組み込みシンドローム符号を使用することが可能である。これらの符号によって、登録期間中において、シンドローム符号化器は、バイオメトリックデータの本来の可変性を推定することが可能になり、シンドローム復号の成功を可能にするのに過不足のないシンドロームビットを符号化することが可能になる。
【０１０５】
第７に、上述したシンドローム符号は、データの暗号化に使用することができる。さらに、所与のパフォーマンスレベルおよび誤差耐性を有する最適なシンドローム符号の設計を可能にする方法が説明された。
【０１０６】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神および範囲内で他のさまざまな適合および変更を行えることが理解されるべきである。したがって、本発明の真の精神および範囲内に入るこのようなすべての変形および変更を網羅することが添付の特許請求の範囲の目的である。
【図面の簡単な説明】
【０１０７】
【図１】従来技術によるパスワードに基づくセキュリティシステムのブロック図である。
【図２】従来技術によるバイオメトリックに基づくセキュリティシステムのブロック図である。
【図３】本発明の１つの実施の形態によるバイオメトリックセキュリティシステムのブロック図である。
【図４】データを保護する従来技術によるセキュリティシステムのブロック図である。
【図５】本発明の１つの実施の形態によるデータセキュリティシステムのブロック図である。
【図６】本発明の１つの実施の形態によるバイオメトリックセキュリティシステムのブロック図である。
【図７】本発明の１つの実施の形態によるシンドローム符号を構築するプロセスのブロック図である。
【図８】本発明の１つの実施の形態によるヒストグラムを生成するプロセスのブロック図である。
【図９】本発明の１つの実施の形態による特徴ベクトルを選択するプロセスのブロック図である。
【図１０】本発明の１つの実施の形態による係数間の相関を測定するブロック図である。
【図１１】本発明の１つの実施の形態による相関ノードを有する確率伝搬因子グラフである。
【図１２】本発明の１つの実施の形態によるシンドローム符号設計のブロック図である。
【図１】
2009507267.tif 000003
【図２】
2009507267.tif 000004
【図３】
2009507267.tif 000005
【図４】
2009507267.tif 000006
【図５】
2009507267.tif 000007
【図６】
2009507267.tif 000008
【図７】
2009507267.tif 000009
【図８】
2009507267.tif 000010
【図９】
2009507267.tif 000011
【図１０】
2009507267.tif 000012
【図１１】
2009507267.tif 000013
【図１２】
2009507267.tif 000014
【国際調査報告】
2009507267.tif 000015
2009507267.tif 000016
2009507267.tif 000017