バイオメトリックパラメータをデータベースに安全に記憶するための方法及びシステム、並びに、バイオメトリックパラメータをデータベースに安全に記憶してユーザを認証するための方法
【課題】バイオメトリックパラメータに基づく安全なユーザ認証を達成する。
【解決手段】登録バイオメトリックパラメータがユーザから取得されて、シンドロームとして符号化され、ハッシュ関数が適用されて登録ハッシュが生成され、データベースに記憶される。登録シンドロームが、シンドローム復号器及びユーザの認証バイオメトリックパラメータを使用して復号され、復号されたバイオメトリックパラメータが生成される。ハッシュ関数が、復号されたバイオメトリックパラメータに適用されて、認証ハッシュが生成される。これら認証ハッシュと登録ハッシュとが比較されて、ユーザアクセスが許可されるかどうかが判断される。
【解決手段】登録バイオメトリックパラメータがユーザから取得されて、シンドロームとして符号化され、ハッシュ関数が適用されて登録ハッシュが生成され、データベースに記憶される。登録シンドロームが、シンドローム復号器及びユーザの認証バイオメトリックパラメータを使用して復号され、復号されたバイオメトリックパラメータが生成される。ハッシュ関数が、復号されたバイオメトリックパラメータに適用されて、認証ハッシュが生成される。これら認証ハッシュと登録ハッシュとが比較されて、ユーザアクセスが許可されるかどうかが判断される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、データ圧縮及び暗号法の分野に関し、より詳細には、ユーザ認証用のバイオメトリックパラメータを記憶することに関する。
【背景技術】
【０００２】
従来のパスワードに基づくセキュリティシステム
従来のパスワードに基づくセキュリティシステムは、通常、２つのフェーズを含む。具体的には、登録フェーズの期間中、ユーザはパスワードを選択し、このパスワードは、サーバ等の認証デバイスに記憶される。認証フェーズの期間中、資源又はデータにアクセスするために、ユーザは、自身のパスワードを入力し、このパスワードが、パスワードの記憶されたものと照合される。パスワードがプレーンテキストとして記憶される場合、システムにアクセスする攻撃者は、あらゆるパスワードを得ることができる。したがって、攻撃が１回成功した場合であっても、システム全体のセキュリティが危険にさらされる可能性がある。
【０００３】
図１に示すように、従来のパスワードに基づくセキュリティシステム１００は、登録フェーズ１０の期間中に、暗号化された（１１０）パスワード１０１をパスワードデータベース１２０に記憶する（１１５）。具体的には、Ｘが、記憶される（１１５）パスワード１０１である場合、システム１００は、実際にはｆ（Ｘ）を記憶する。ここで、ｆ（・）は、或る暗号化関数又はハッシュ関数１１０である。認証フェーズ２０の期間中、ユーザは、候補のパスワードＹ１０２を入力し、システムはｆ（Ｙ）を求め（１３０）、そして、ｆ（Ｙ）が、記憶されたパスワードｆ（Ｘ）と一致する（１４０）場合にのみシステムへのアクセスを許可し（１５０）、そうでない場合、アクセスは拒否される（１６０）。
【０００４】
利点として、暗号化されたパスワードは、暗号化関数なしでは攻撃者にとって役に立たない。暗号化されたパスワードは、通例、戻すことが非常に困難である。
【０００５】
従来のバイオメトリックに基づくセキュリティシステム
従来のバイオメトリックセキュリティシステムは、パスワードに基づくシステムと同じ脆弱性を有し、暗号化されていないパスワードを記憶する。具体的には、データベースが、暗号化されていないバイオメトリックパラメータを記憶する場合、それらパラメータは、攻撃及び悪用の対象になる。
【０００６】
例えば、顔認識システム又は音声認識を使用するセキュリティシステムでは、攻撃者は、その攻撃者とよく似たバイオメトリックパラメータを検索することができる。適切なバイオメトリックパラメータが突き止められた後、攻撃者は、それらパラメータを変更して、攻撃者の外見又は音声と一致させ、認可されないアクセスを行うことができる。同様に、指紋認識又は虹彩認識を使用するセキュリティシステムでは、攻撃者は、一致する指紋又は虹彩を模倣するデバイスを構築して、認可されないアクセスを行うことができる。例えば、このデバイスは、偽造した指又は眼である。
【０００７】
バイオメトリックパラメータは、本来、時間の経過と共に変化するものであるので、バイオメトリックパラメータを暗号化することは常に可能であるとは限らない。具体的には、バイオメトリックパラメータＸは、登録フェーズの期間中に入力される。このパラメータＸは、暗号化関数又はハッシュ関数ｆ（Ｘ）を使用して暗号化されて記憶される。認証フェーズの期間中、同じユーザから得られたバイオメトリックパラメータは異なる可能性がある。例えば、顔認識を使用するセキュリティシステムでは、ユーザの顔は、認識の期間中と比べて登録の期間中は、カメラに対して異なる向きを有する可能性がある。肌の色合い、ヘアスタイル、及び顔の特徴は変化する可能性がある。したがって、認識の期間中、暗号化されたバイオメトリックパラメータは、記憶されたどのパラメータとも一致しないことになり、拒絶されることになる。
【０００８】
誤り訂正符号
アルファベットＱ上の（Ｎ，Ｋ）誤り訂正符号（ＥＣＣ）Ｃは、長さＮのＱＫベクトルを含む。線形（Ｎ，Ｋ）ＥＣＣは、Ｎ行及びＫ列を有する生成行列Ｇを使用することによるか、又は、Ｎ−Ｋ行及びＮ列を有するパリティチェック行列Ｈを使用することにより、記述することができる。「生成行列」という名称は、ベクトルｗとして表された符号語が、ｗ＝ｖＧに従って、任意の長さＫの入力された行ベクトルｖを行列Ｇに右乗算することにより、ベクトルｖから生成できるということに基づいている。同様に、ベクトルｗが符号語であるかどうかをチェックするために、ＨｗＴ＝０であるかどうかをチェックすることができる。ここで、列ベクトルｗＴは行ｗの転置である。
【０００９】
誤り訂正符号の標準的な使用では、入力ベクトルｖが、ベクトルｗに符号化され、記憶されるか、又は、送信される。ベクトルｗの破損したものが受信されると、復号器は、符号の冗長性を使用して誤りを訂正する。直感的に、符号の誤りの耐性（error capability）は、符号の冗長量に依存する。
【００１０】
Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号、Ｗｙｎｅｒ−Ｚｉｖ符号、及びシンドローム符号（syndrome code）
或る意味で、Ｓｌｅｐｉａｎ−Ｗｏｌｆ（ＳＷ）符号は、誤り訂正符号とは逆のものである。誤り訂正符号は、冗長性を追加してデータを拡張するのに対して、ＳＷ符号は、冗長性を取り除いてデータを圧縮する。具体的には、ベクトルｘ及びベクトルｙが、相関したデータのベクトルを表す。符号化器が、すでにベクトルｙを有する復号器にベクトルｘを通信したい場合、符号化器は、復号器がベクトルｙを有することを考慮してデータを圧縮することができる。
【００１１】
極端な例として、ベクトルｘ及びベクトルｙが１ビットしか異ならない場合、符号化器は、ベクトルｘ及びその相違した位置を単に記述するだけで圧縮を行うことができる。もちろん、より現実的な相関モデルには、より高度な符号が必要とされる。
【００１２】
ＳＷ符号化の基本理論、及び、関連したＷｙｎｅｒ−Ｚｉｖ（ＷＺ）符号化は、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及びRamchandranが、「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, G. I.、Frankel, Y.、Matt, B. J.著「On enabling secure applications through off-line biometric identification」, Proceedings of the IEEE Symposium on Security and Privacy, May 1998、Juels, A.、Sudan, M.著「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）」と呼ばれる或る量の雑音を追加する。
【００２１】
米国特許第６，３６３，４８５号は、バイオメトリックデータを誤り訂正符号及び或る秘密情報と結合して、秘密鍵を生成するための方法を記載している。或る秘密情報は、パスワードや個人識別番号（ＰＩＮ）等である。Ｇｏｐｐａ符号やＢＣＨ符号等の誤り訂正符号が、さまざまなＸＯＲ演算と共に使用される。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
従来技術に関連した問題
第１に、ビットに基づく従来技術の方法が提供するセキュリティは疑わしいものである。これに加えて、バイオメトリックは、多くの場合、バイナリ値の代わりに、実数値又は整数値である。この従来技術は、一般に、バイオメトリックが一様に分布したランダムなビットで構成され、記憶されたバイオメトリックからこれらのビットを正確に求めることは困難であると仮定する。実際には、バイオメトリックパラメータは、多くの場合、偏っており、セキュリティに悪影響を与える。また、たとえ、攻撃が、記憶されたバイオメトリックに近似したものしか復元しないとしても、その攻撃は重大な損害を引き起こす可能性もある。従来技術の方法は、攻撃者が、実際のバイオメトリックを符号化されたものから推定することを防止するようには設計されていない。
【００２３】
例えば、米国特許第６，０３８，３１５号は、ランダムな符号語Ｗを追加することによって、参照値Ｒ＝Ｗ＋ＥがバイオメトリックＥを有効に暗号化することに依拠している。しかしながら、その方法が達成するセキュリティは不十分である。ＲからＥを復元する複数の方法がある。例えば、ベクトルＥが、１に等しいビットを数ビットしか有しない場合、ＲとＷとの間のハミング距離は小さくなる。したがって、誤り訂正復号器は、ＲからＷを容易に復元することができ、したがって、Ｅを復元することもできる。代替的に、例えば、符号の重みスペクトル（weight spectrum）が小さく、多くの符号語がオールゼロベクトルの周りに密集する場合といった、符号語の分散が不十分である場合に、攻撃者は、ＲからＥの良好な近似を得ることができる。
【００２４】
第２に、セキュリティが疑わしいことに加えて、従来技術の方法は、記憶されるデータ量が増加するという実用上の不都合も有する。バイオメトリックデータベースは、多くの場合、多数の個人ユーザのデータを記憶するので、ストレージが追加されることによって、システムのコスト及び複雑度は大幅に増加する。
【００２５】
第３に、多くの従来技術の方法は、高い計算複雑度を有する誤り訂正符号又はアルゴリズムを必要とする。例えば、従来技術のリード−ソロモン復号アルゴリズム及びリード−マラー復号アルゴリズムは、一般に、符号化されたバイオメトリックの長さにおいて、少なくとも２次の計算複雑度を有し、多くの場合、それよりも高次の計算複雑度を有する。
【課題を解決するための手段】
【００２６】
バイオメトリックパラメータは、例えば、人間の顔、音声、指紋、及び虹彩から取得され、多くの場合、ユーザ認証及びデータアクセス制御に使用される。バイオメトリックパラメータは、パスワードで行われるように、ハッシュされた形態又は暗号化された形態でデータベースに記憶することはできない。その理由は、このパラメータは、連続的であり、同じユーザについて或る読み取りから次の読み取りまでに変化し得るからである。これによって、バイオメトリックデータベースは、「１度破れば、どこでも実行される（break once run everywhere）」攻撃の対象になる。
【００２７】
本発明は、Ｗｙｎｅｒ−Ｚｉｖ及びＳｌｅｐｉａｎ−Ｗｏｌｆ符号化に基づくシンドローム符号を使用して、バイオメトリックシンドロームを求める。このバイオメトリックシンドロームは、安全に記憶することができると同時に、依然として、バイオメトリックデータの本来的な可変性を許容する。
【００２８】
具体的には、本発明によるバイオメトリックシンドロームは、以下の特性を有する。第１に、シンドロームデータベースが危険にさらされた場合、記憶されたシンドロームが、システムのセキュリティを巧みに回避するのにほとんど役立たないように、シンドロームは、元のバイオメトリックの特徴に関する情報を有効に隠蔽するか、又は、暗号化する。第２に、記憶された各シンドロームを復号して、元のバイオメトリックパラメータを生成して、ユーザを認証することができる。
【発明の効果】
【００２９】
本発明は、バイオメトリックパラメータに基づく安全なユーザ認証を達成する。本発明は、元のバイオメトリックデータの代わりにシンドロームが記憶されるので安全である。これによって、データベースにアクセスする攻撃者が、基礎を成すバイオメトリックデータを知ることが防止される。
【００３０】
攻撃者がシンドロームＳのみを使用して行うことができる、元のバイオメトリックパラメータＥの最も良い可能な推定を、複数の記述の既知の問題からの従来のツールを使用して制限することが可能である。これについては、例えば、V. K. Goyal著「Multiple description coding: compression meets the network」, IEEE Signal Processing Magazine, Volume: 18, pages 74-93, September 2001を参照されたい。さらに、推定の質が絶対誤差測定を介して測定されようと、２乗誤差測定を介して測定されようと、加重誤差測定を介して測定されようと、あるいは任意の誤差関数を介して測定されようと、これらの限界を作成することが可能である。これとは対照的に、すべての従来技術の方法は、バイナリ値に基づいている。そこで、セキュリティはハミング距離に依存する。
【００３１】
基本的に、シンドロームＳのセキュリティは、シンドロームＳが元のバイオメトリックパラメータＥの圧縮されたものであるということに起因する。さらに、この圧縮表現は、Ｅの「最下位ビット」に対応する。データ圧縮理論からの既知のツールを使用すると、高圧縮を有するシンドローム符号が使用される場合、これらの最下位ビットが生成できる、元のパラメータＥの推定は、いくら良くても不十分なものであることを証明することが可能である。これについては、例えば、Effros著「Distortion-rate bounds for fixed- and variable-rate multiresolution source codes」, IEEE Transactions on Information Theory, volume 45, pages 1887-1910, September 1999、並びに、Steinberg及びMerhav著「On successive refinement for the Wyner-Ziv problem」, IEEE Transactions on Information Theory, volume 50, pages 1636-1654, August 2004を参照されたい。
【００３２】
第２に、本発明は、偽造が、少なくとも、基礎を成すハッシュ関数における衝突を見つけるのと同程度に困難であるので、安全である。特に、復号されたバイオメトリックＥ”のハッシュＨ’が元のハッシュＨと一致する場合に、システムは、認証フェーズ３１０においてシンドローム−ハッシュの対（Ｓ，Ｈ）のみを受け付ける。ＭＤ５等の暗号ハッシュ関数について、Ｅとは異なるが、Ｅのハッシュと一致するハッシュを有する要素Ｅ”を見つけることは、一般に不可能であると考えられる。したがって、シンドローム復号が、適切なハッシュでＥ”の復号に成功した場合に、システムは、Ｅ”が実際にＥと同じであり、すべての認証判定は元のバイオメトリックパラメータで行われることを確信することができる。
【００３３】
第３に、本発明は、シンドロームＳを生成する際に、元のバイオメトリックパラメータＥを圧縮する。多くのユーザ用のバイオメトリックデータベースは、特に、バイオメトリックデータの問いが、大量のデータ、例えば、顔画像又は会話信号を必要とする場合に、大量のストレージを必要とする可能性がある。したがって、必要とされるストレージを減少させることによって、コスト及び性能の双方で大幅な改善を生み出すことができる。これとは対照的に、バイオメトリックデータの安全な記憶のためのほとんどの従来技術の方法では、実際には、暗号化又は誤り訂正のオーバーヘッドによって、記憶されるデータのサイズが増加し、したがって、安全でないシステムよりも多くのストレージが必要とされる。
【００３４】
第４に、本発明は、シンドローム符号の理論を基に築かれているので、高度な符号構築アルゴリズム及び復号アルゴリズムを適用することができる。特に、本発明によるシンドローム符号化によって、バイナリ符号の構築及びマルチレベル符号の構築の双方について、既知のビタビアルゴリズム、確率伝播、及びターボ復号を使用するソフト復号の使用が容易になる。これとは対照的に、ほとんどの従来技術の方法は、バイナリ符号、リードソロモン符号、及び代数的復号に基づいているので、バイオメトリックデータがバイナリ値ではなく実数値を取る場合に、ソフト復号を有効に適用することができない。例えば、いくつかの方法は、具体的には、登録フェーズにおいて、バイオメトリックデータとランダムな符号語とのＸＯＲを計算して、基準値を生成することを必要とし、認証フェーズにおいて、その基準値とバイオメトリックデータとのＸＯＲを計算することを必要とする。
【００３５】
第５に、安全なバイオメトリックに関するほとんどの従来技術は誤り訂正符号化を使用するのに対して、本発明は、シンドローム符号化を使用する。誤り訂正符号化の計算複雑度は、通例、入力サイズにおいて超線形である。これとは対照的に、さまざまなタイプの低密度パリティチェックに基づくシンドローム符号を使用することによって、シンドローム符号化の計算複雑度が入力サイズにおいて線形にしかならないシンドローム符号化器を構築することが容易である。
【００３６】
第６に、シンドローム符号化のフレームワークを使用することによって、Yedidia他によって記載されたＳＣＡ符号のような新しい強力な組み込みシンドローム符号を使用することが可能である。これらの符号によって、登録期間中において、シンドローム符号化器は、バイオメトリックデータの本来の可変性を推定することが可能になり、シンドローム復号の成功を可能にするのに過不足のないシンドロームビットを符号化することが可能になる。
【発明を実施するための最良の形態】
【００３７】
図３は、本発明によるバイオメトリックセキュリティシステムを示している。発明者等の発明による本方法は、シンドローム符号でバイオメトリックパラメータを圧縮して、圧縮されたシンドロームを生成する。従来の圧縮と異なり、シンドローム符号によって生成されたシンドロームは、元のバイオメトリックデータと無関係である。したがって、記憶されたシンドロームを使用して、元のバイオメトリックパラメータと近似したものを復号することはできない。その結果生成された、圧縮されたシンドローム及びそのシンドロームのハッシュが、バイオメトリックデータベースに記憶される。
【００３８】
ユーザを認証するために、バイオメトリックパラメータが再び測定される。これらのバイオメトリックパラメータは、記憶されたシンドロームと結合されて、元のバイオメトリックパラメータが復号される。シンドロームの復号が失敗すると、ユーザは、アクセスを拒否される。シンドロームの復号が成功すると、元のバイオメトリックパラメータが使用されて、ユーザの真正性が検証される。
【００３９】
登録フェーズ
登録フェーズ３１０では、ユーザのバイオメトリックデータが取得される。例えば、このデータは、顔の画像、会話の記録、指紋の画像、又は虹彩をスキャンしたものである。特徴ベクトルが、測定されたバイオメトリックデータから抽出される。この特徴ベクトルは、登録バイオメトリックパラメータ３０１を形成する。さまざまな形式のバイオメトリックデータから特徴を抽出するための方法は、上述したように、当該技術分野において既知である。
【００４０】
バイオメトリックパラメータＥ３０１は、シンドローム符号化器３３０を使用して符号化され、登録シンドロームＳ３３１が生成される。次に、メッセージ認証符号又はハッシュ関数が登録シンドロームＳに適用され（３４０）、登録ハッシュＨ３４１が生成される。このハッシュ関数は、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、K. R. Narayanan、及びC. N. Georghiades著「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」という発明の名称の米国特許出願第１０／９２８，４４８号は、本発明によって使用されるようなＳＣＡ符号に基づく、発明者等の好ましいシンドローム符号化器のオペレーションを記載している。この米国特許出願は、参照により本明細書に援用される。
【００４４】
バイオメトリックパラメータ３０１の本発明のシンドローム符号化器３３０は、複数の利点を有する。このシンドローム符号化器３３０は、整数値の入力に対してオペレーションを行うことができる。これとは対照的に、従来技術の符号化器は、一般に、バイナリ値の入力に対してオペレーションを行う。このシンドローム符号化器は、バイオメトリックデータベース３５０のストレージ要件を最小にするために非常に高い圧縮率を有する。このシンドローム符号化器は、レート適合型であり、インクリメンタル形にオペレーションを行うことができる。先に送信されたシンドロームビットの情報を無駄にすることなく、必要に応じてより多くのビットを送信することができる。
【００４５】
認証フェーズ
認証フェーズ３２０では、バイオメトリックデータが、ユーザから再び取得される。特徴が抽出されて、認証バイオメトリックパラメータＥ’３６０が得られる。データベース３５０が検索されて、このユーザの一致する登録シンドロームＳ３３１及び登録ハッシュＨ３４１が突き止められる。
【００４６】
この検索は、データベース３５０のあらゆるエントリ（Ｓ−Ｈ対）をチェックすることもできるし、ヒューリスティックに順序付けられた検索を使用して、一致するエントリを見つけるプロセスを高速化することもできる。具体的には、発明者等が、データベースにおけるｉ番目のシンドローム−ハッシュの対を（Ｓｉ，Ｈｉ）と示す場合、全数検索は、まず、シンドローム復号をＥ’及びＳ１に適用し、シンドローム復号器の出力のハッシュをＨ１と比較する。アクセスが拒否される場合、同じプロセスが（Ｓ２，Ｈ２）で試みられ、次いで（Ｓ３，Ｈ３）で試みられ、すべてのエントリが試行されるか、又は、アクセスが許可されるまで、以下同様に試みられる。
【００４７】
登録ユーザ名等のサイド情報が利用可能である場合、そのサイド情報を使用して検索を高速化することができる。例えば、登録ユーザ名のハッシュが，登録フェーズの期間中にＳ及びＨの対と共に記憶される。次に、認証フェーズでは、ユーザが認証ユーザ名を供給し、システムが、その認証ユーザ名のハッシュを求め、一致する、ハッシュされた登録ユーザ名を有するＳ−Ｈ対を求めてデータベースを検索し、そして、その結果のＳ−Ｈ対でＥ’の認証を試みる。
【００４８】
具体的には、シンドローム復号器３７０が、登録シンドロームＳに適用され、認証パラメータＥ’３６０が「サイド」情報として働く。シンドローム復号器は、一般に当該技術分野において既知である。通常、確率伝播又はターボ符号を使用する復号器は、低い複雑度で優れた性能を有する。シンドローム復号器３７０の出力は、復号された登録パラメータＥ”３７１である。復号された値Ｅ”３７１は、シンドロームＳ３３１を生成するのに使用された元のバイオメトリックパラメータＥ３０１の推定値である。ハッシュ関数３４０がＥ”３７１に適用されて、認証ハッシュＨ’３８１が生成される。
【００４９】
登録値Ｈ３４１と認証値Ｈ’３８１とが比較される（３９０）。それらの値が一致しない場合、アクセスは拒否される（３９２）。そうでない場合、値Ｅ”３８１は、元のバイオメトリックＥ３０１と実質的に一致する。この場合、ユーザはアクセス許可を受けることができる（３９１）。
【００５０】
これに加えて、復号されたパラメータＥ”３８１と認証バイオメトリックパラメータＥ’３６０との間で直接比較を行って、ユーザを認証することもできる。例えば、Ｅ’及びＥ”が顔認識システムのバイオメトリックパラメータに対応する場合、顔の類似性を比較するための従来のアルゴリズムをパラメータＥ’及びパラメータＥ”に適用することができる。
【００５１】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るこのようなすべての変形及び変更を網羅することが添付の特許請求の範囲の目的である。
【図面の簡単な説明】
【００５２】
【図１】従来技術のパスワードに基づくセキュリティシステムのブロック図である。
【図２】従来技術のバイオメトリックに基づくセキュリティシステムのブロック図である。
【図３】本発明によるバイオメトリックセキュリティシステムのブロック図である。
【技術分野】
【０００１】
本発明は、包括的には、データ圧縮及び暗号法の分野に関し、より詳細には、ユーザ認証用のバイオメトリックパラメータを記憶することに関する。
【背景技術】
【０００２】
従来のパスワードに基づくセキュリティシステム
従来のパスワードに基づくセキュリティシステムは、通常、２つのフェーズを含む。具体的には、登録フェーズの期間中、ユーザはパスワードを選択し、このパスワードは、サーバ等の認証デバイスに記憶される。認証フェーズの期間中、資源又はデータにアクセスするために、ユーザは、自身のパスワードを入力し、このパスワードが、パスワードの記憶されたものと照合される。パスワードがプレーンテキストとして記憶される場合、システムにアクセスする攻撃者は、あらゆるパスワードを得ることができる。したがって、攻撃が１回成功した場合であっても、システム全体のセキュリティが危険にさらされる可能性がある。
【０００３】
図１に示すように、従来のパスワードに基づくセキュリティシステム１００は、登録フェーズ１０の期間中に、暗号化された（１１０）パスワード１０１をパスワードデータベース１２０に記憶する（１１５）。具体的には、Ｘが、記憶される（１１５）パスワード１０１である場合、システム１００は、実際にはｆ（Ｘ）を記憶する。ここで、ｆ（・）は、或る暗号化関数又はハッシュ関数１１０である。認証フェーズ２０の期間中、ユーザは、候補のパスワードＹ１０２を入力し、システムはｆ（Ｙ）を求め（１３０）、そして、ｆ（Ｙ）が、記憶されたパスワードｆ（Ｘ）と一致する（１４０）場合にのみシステムへのアクセスを許可し（１５０）、そうでない場合、アクセスは拒否される（１６０）。
【０００４】
利点として、暗号化されたパスワードは、暗号化関数なしでは攻撃者にとって役に立たない。暗号化されたパスワードは、通例、戻すことが非常に困難である。
【０００５】
従来のバイオメトリックに基づくセキュリティシステム
従来のバイオメトリックセキュリティシステムは、パスワードに基づくシステムと同じ脆弱性を有し、暗号化されていないパスワードを記憶する。具体的には、データベースが、暗号化されていないバイオメトリックパラメータを記憶する場合、それらパラメータは、攻撃及び悪用の対象になる。
【０００６】
例えば、顔認識システム又は音声認識を使用するセキュリティシステムでは、攻撃者は、その攻撃者とよく似たバイオメトリックパラメータを検索することができる。適切なバイオメトリックパラメータが突き止められた後、攻撃者は、それらパラメータを変更して、攻撃者の外見又は音声と一致させ、認可されないアクセスを行うことができる。同様に、指紋認識又は虹彩認識を使用するセキュリティシステムでは、攻撃者は、一致する指紋又は虹彩を模倣するデバイスを構築して、認可されないアクセスを行うことができる。例えば、このデバイスは、偽造した指又は眼である。
【０００７】
バイオメトリックパラメータは、本来、時間の経過と共に変化するものであるので、バイオメトリックパラメータを暗号化することは常に可能であるとは限らない。具体的には、バイオメトリックパラメータＸは、登録フェーズの期間中に入力される。このパラメータＸは、暗号化関数又はハッシュ関数ｆ（Ｘ）を使用して暗号化されて記憶される。認証フェーズの期間中、同じユーザから得られたバイオメトリックパラメータは異なる可能性がある。例えば、顔認識を使用するセキュリティシステムでは、ユーザの顔は、認識の期間中と比べて登録の期間中は、カメラに対して異なる向きを有する可能性がある。肌の色合い、ヘアスタイル、及び顔の特徴は変化する可能性がある。したがって、認識の期間中、暗号化されたバイオメトリックパラメータは、記憶されたどのパラメータとも一致しないことになり、拒絶されることになる。
【０００８】
誤り訂正符号
アルファベットＱ上の（Ｎ，Ｋ）誤り訂正符号（ＥＣＣ）Ｃは、長さＮのＱＫベクトルを含む。線形（Ｎ，Ｋ）ＥＣＣは、Ｎ行及びＫ列を有する生成行列Ｇを使用することによるか、又は、Ｎ−Ｋ行及びＮ列を有するパリティチェック行列Ｈを使用することにより、記述することができる。「生成行列」という名称は、ベクトルｗとして表された符号語が、ｗ＝ｖＧに従って、任意の長さＫの入力された行ベクトルｖを行列Ｇに右乗算することにより、ベクトルｖから生成できるということに基づいている。同様に、ベクトルｗが符号語であるかどうかをチェックするために、ＨｗＴ＝０であるかどうかをチェックすることができる。ここで、列ベクトルｗＴは行ｗの転置である。
【０００９】
誤り訂正符号の標準的な使用では、入力ベクトルｖが、ベクトルｗに符号化され、記憶されるか、又は、送信される。ベクトルｗの破損したものが受信されると、復号器は、符号の冗長性を使用して誤りを訂正する。直感的に、符号の誤りの耐性（error capability）は、符号の冗長量に依存する。
【００１０】
Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号、Ｗｙｎｅｒ−Ｚｉｖ符号、及びシンドローム符号（syndrome code）
或る意味で、Ｓｌｅｐｉａｎ−Ｗｏｌｆ（ＳＷ）符号は、誤り訂正符号とは逆のものである。誤り訂正符号は、冗長性を追加してデータを拡張するのに対して、ＳＷ符号は、冗長性を取り除いてデータを圧縮する。具体的には、ベクトルｘ及びベクトルｙが、相関したデータのベクトルを表す。符号化器が、すでにベクトルｙを有する復号器にベクトルｘを通信したい場合、符号化器は、復号器がベクトルｙを有することを考慮してデータを圧縮することができる。
【００１１】
極端な例として、ベクトルｘ及びベクトルｙが１ビットしか異ならない場合、符号化器は、ベクトルｘ及びその相違した位置を単に記述するだけで圧縮を行うことができる。もちろん、より現実的な相関モデルには、より高度な符号が必要とされる。
【００１２】
ＳＷ符号化の基本理論、及び、関連したＷｙｎｅｒ−Ｚｉｖ（ＷＺ）符号化は、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及びRamchandranが、「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, G. I.、Frankel, Y.、Matt, B. J.著「On enabling secure applications through off-line biometric identification」, Proceedings of the IEEE Symposium on Security and Privacy, May 1998、Juels, A.、Sudan, M.著「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）」と呼ばれる或る量の雑音を追加する。
【００２１】
米国特許第６，３６３，４８５号は、バイオメトリックデータを誤り訂正符号及び或る秘密情報と結合して、秘密鍵を生成するための方法を記載している。或る秘密情報は、パスワードや個人識別番号（ＰＩＮ）等である。Ｇｏｐｐａ符号やＢＣＨ符号等の誤り訂正符号が、さまざまなＸＯＲ演算と共に使用される。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
従来技術に関連した問題
第１に、ビットに基づく従来技術の方法が提供するセキュリティは疑わしいものである。これに加えて、バイオメトリックは、多くの場合、バイナリ値の代わりに、実数値又は整数値である。この従来技術は、一般に、バイオメトリックが一様に分布したランダムなビットで構成され、記憶されたバイオメトリックからこれらのビットを正確に求めることは困難であると仮定する。実際には、バイオメトリックパラメータは、多くの場合、偏っており、セキュリティに悪影響を与える。また、たとえ、攻撃が、記憶されたバイオメトリックに近似したものしか復元しないとしても、その攻撃は重大な損害を引き起こす可能性もある。従来技術の方法は、攻撃者が、実際のバイオメトリックを符号化されたものから推定することを防止するようには設計されていない。
【００２３】
例えば、米国特許第６，０３８，３１５号は、ランダムな符号語Ｗを追加することによって、参照値Ｒ＝Ｗ＋ＥがバイオメトリックＥを有効に暗号化することに依拠している。しかしながら、その方法が達成するセキュリティは不十分である。ＲからＥを復元する複数の方法がある。例えば、ベクトルＥが、１に等しいビットを数ビットしか有しない場合、ＲとＷとの間のハミング距離は小さくなる。したがって、誤り訂正復号器は、ＲからＷを容易に復元することができ、したがって、Ｅを復元することもできる。代替的に、例えば、符号の重みスペクトル（weight spectrum）が小さく、多くの符号語がオールゼロベクトルの周りに密集する場合といった、符号語の分散が不十分である場合に、攻撃者は、ＲからＥの良好な近似を得ることができる。
【００２４】
第２に、セキュリティが疑わしいことに加えて、従来技術の方法は、記憶されるデータ量が増加するという実用上の不都合も有する。バイオメトリックデータベースは、多くの場合、多数の個人ユーザのデータを記憶するので、ストレージが追加されることによって、システムのコスト及び複雑度は大幅に増加する。
【００２５】
第３に、多くの従来技術の方法は、高い計算複雑度を有する誤り訂正符号又はアルゴリズムを必要とする。例えば、従来技術のリード−ソロモン復号アルゴリズム及びリード−マラー復号アルゴリズムは、一般に、符号化されたバイオメトリックの長さにおいて、少なくとも２次の計算複雑度を有し、多くの場合、それよりも高次の計算複雑度を有する。
【課題を解決するための手段】
【００２６】
バイオメトリックパラメータは、例えば、人間の顔、音声、指紋、及び虹彩から取得され、多くの場合、ユーザ認証及びデータアクセス制御に使用される。バイオメトリックパラメータは、パスワードで行われるように、ハッシュされた形態又は暗号化された形態でデータベースに記憶することはできない。その理由は、このパラメータは、連続的であり、同じユーザについて或る読み取りから次の読み取りまでに変化し得るからである。これによって、バイオメトリックデータベースは、「１度破れば、どこでも実行される（break once run everywhere）」攻撃の対象になる。
【００２７】
本発明は、Ｗｙｎｅｒ−Ｚｉｖ及びＳｌｅｐｉａｎ−Ｗｏｌｆ符号化に基づくシンドローム符号を使用して、バイオメトリックシンドロームを求める。このバイオメトリックシンドロームは、安全に記憶することができると同時に、依然として、バイオメトリックデータの本来的な可変性を許容する。
【００２８】
具体的には、本発明によるバイオメトリックシンドロームは、以下の特性を有する。第１に、シンドロームデータベースが危険にさらされた場合、記憶されたシンドロームが、システムのセキュリティを巧みに回避するのにほとんど役立たないように、シンドロームは、元のバイオメトリックの特徴に関する情報を有効に隠蔽するか、又は、暗号化する。第２に、記憶された各シンドロームを復号して、元のバイオメトリックパラメータを生成して、ユーザを認証することができる。
【発明の効果】
【００２９】
本発明は、バイオメトリックパラメータに基づく安全なユーザ認証を達成する。本発明は、元のバイオメトリックデータの代わりにシンドロームが記憶されるので安全である。これによって、データベースにアクセスする攻撃者が、基礎を成すバイオメトリックデータを知ることが防止される。
【００３０】
攻撃者がシンドロームＳのみを使用して行うことができる、元のバイオメトリックパラメータＥの最も良い可能な推定を、複数の記述の既知の問題からの従来のツールを使用して制限することが可能である。これについては、例えば、V. K. Goyal著「Multiple description coding: compression meets the network」, IEEE Signal Processing Magazine, Volume: 18, pages 74-93, September 2001を参照されたい。さらに、推定の質が絶対誤差測定を介して測定されようと、２乗誤差測定を介して測定されようと、加重誤差測定を介して測定されようと、あるいは任意の誤差関数を介して測定されようと、これらの限界を作成することが可能である。これとは対照的に、すべての従来技術の方法は、バイナリ値に基づいている。そこで、セキュリティはハミング距離に依存する。
【００３１】
基本的に、シンドロームＳのセキュリティは、シンドロームＳが元のバイオメトリックパラメータＥの圧縮されたものであるということに起因する。さらに、この圧縮表現は、Ｅの「最下位ビット」に対応する。データ圧縮理論からの既知のツールを使用すると、高圧縮を有するシンドローム符号が使用される場合、これらの最下位ビットが生成できる、元のパラメータＥの推定は、いくら良くても不十分なものであることを証明することが可能である。これについては、例えば、Effros著「Distortion-rate bounds for fixed- and variable-rate multiresolution source codes」, IEEE Transactions on Information Theory, volume 45, pages 1887-1910, September 1999、並びに、Steinberg及びMerhav著「On successive refinement for the Wyner-Ziv problem」, IEEE Transactions on Information Theory, volume 50, pages 1636-1654, August 2004を参照されたい。
【００３２】
第２に、本発明は、偽造が、少なくとも、基礎を成すハッシュ関数における衝突を見つけるのと同程度に困難であるので、安全である。特に、復号されたバイオメトリックＥ”のハッシュＨ’が元のハッシュＨと一致する場合に、システムは、認証フェーズ３１０においてシンドローム−ハッシュの対（Ｓ，Ｈ）のみを受け付ける。ＭＤ５等の暗号ハッシュ関数について、Ｅとは異なるが、Ｅのハッシュと一致するハッシュを有する要素Ｅ”を見つけることは、一般に不可能であると考えられる。したがって、シンドローム復号が、適切なハッシュでＥ”の復号に成功した場合に、システムは、Ｅ”が実際にＥと同じであり、すべての認証判定は元のバイオメトリックパラメータで行われることを確信することができる。
【００３３】
第３に、本発明は、シンドロームＳを生成する際に、元のバイオメトリックパラメータＥを圧縮する。多くのユーザ用のバイオメトリックデータベースは、特に、バイオメトリックデータの問いが、大量のデータ、例えば、顔画像又は会話信号を必要とする場合に、大量のストレージを必要とする可能性がある。したがって、必要とされるストレージを減少させることによって、コスト及び性能の双方で大幅な改善を生み出すことができる。これとは対照的に、バイオメトリックデータの安全な記憶のためのほとんどの従来技術の方法では、実際には、暗号化又は誤り訂正のオーバーヘッドによって、記憶されるデータのサイズが増加し、したがって、安全でないシステムよりも多くのストレージが必要とされる。
【００３４】
第４に、本発明は、シンドローム符号の理論を基に築かれているので、高度な符号構築アルゴリズム及び復号アルゴリズムを適用することができる。特に、本発明によるシンドローム符号化によって、バイナリ符号の構築及びマルチレベル符号の構築の双方について、既知のビタビアルゴリズム、確率伝播、及びターボ復号を使用するソフト復号の使用が容易になる。これとは対照的に、ほとんどの従来技術の方法は、バイナリ符号、リードソロモン符号、及び代数的復号に基づいているので、バイオメトリックデータがバイナリ値ではなく実数値を取る場合に、ソフト復号を有効に適用することができない。例えば、いくつかの方法は、具体的には、登録フェーズにおいて、バイオメトリックデータとランダムな符号語とのＸＯＲを計算して、基準値を生成することを必要とし、認証フェーズにおいて、その基準値とバイオメトリックデータとのＸＯＲを計算することを必要とする。
【００３５】
第５に、安全なバイオメトリックに関するほとんどの従来技術は誤り訂正符号化を使用するのに対して、本発明は、シンドローム符号化を使用する。誤り訂正符号化の計算複雑度は、通例、入力サイズにおいて超線形である。これとは対照的に、さまざまなタイプの低密度パリティチェックに基づくシンドローム符号を使用することによって、シンドローム符号化の計算複雑度が入力サイズにおいて線形にしかならないシンドローム符号化器を構築することが容易である。
【００３６】
第６に、シンドローム符号化のフレームワークを使用することによって、Yedidia他によって記載されたＳＣＡ符号のような新しい強力な組み込みシンドローム符号を使用することが可能である。これらの符号によって、登録期間中において、シンドローム符号化器は、バイオメトリックデータの本来の可変性を推定することが可能になり、シンドローム復号の成功を可能にするのに過不足のないシンドロームビットを符号化することが可能になる。
【発明を実施するための最良の形態】
【００３７】
図３は、本発明によるバイオメトリックセキュリティシステムを示している。発明者等の発明による本方法は、シンドローム符号でバイオメトリックパラメータを圧縮して、圧縮されたシンドロームを生成する。従来の圧縮と異なり、シンドローム符号によって生成されたシンドロームは、元のバイオメトリックデータと無関係である。したがって、記憶されたシンドロームを使用して、元のバイオメトリックパラメータと近似したものを復号することはできない。その結果生成された、圧縮されたシンドローム及びそのシンドロームのハッシュが、バイオメトリックデータベースに記憶される。
【００３８】
ユーザを認証するために、バイオメトリックパラメータが再び測定される。これらのバイオメトリックパラメータは、記憶されたシンドロームと結合されて、元のバイオメトリックパラメータが復号される。シンドロームの復号が失敗すると、ユーザは、アクセスを拒否される。シンドロームの復号が成功すると、元のバイオメトリックパラメータが使用されて、ユーザの真正性が検証される。
【００３９】
登録フェーズ
登録フェーズ３１０では、ユーザのバイオメトリックデータが取得される。例えば、このデータは、顔の画像、会話の記録、指紋の画像、又は虹彩をスキャンしたものである。特徴ベクトルが、測定されたバイオメトリックデータから抽出される。この特徴ベクトルは、登録バイオメトリックパラメータ３０１を形成する。さまざまな形式のバイオメトリックデータから特徴を抽出するための方法は、上述したように、当該技術分野において既知である。
【００４０】
バイオメトリックパラメータＥ３０１は、シンドローム符号化器３３０を使用して符号化され、登録シンドロームＳ３３１が生成される。次に、メッセージ認証符号又はハッシュ関数が登録シンドロームＳに適用され（３４０）、登録ハッシュＨ３４１が生成される。このハッシュ関数は、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、K. R. Narayanan、及びC. N. Georghiades著「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」という発明の名称の米国特許出願第１０／９２８，４４８号は、本発明によって使用されるようなＳＣＡ符号に基づく、発明者等の好ましいシンドローム符号化器のオペレーションを記載している。この米国特許出願は、参照により本明細書に援用される。
【００４４】
バイオメトリックパラメータ３０１の本発明のシンドローム符号化器３３０は、複数の利点を有する。このシンドローム符号化器３３０は、整数値の入力に対してオペレーションを行うことができる。これとは対照的に、従来技術の符号化器は、一般に、バイナリ値の入力に対してオペレーションを行う。このシンドローム符号化器は、バイオメトリックデータベース３５０のストレージ要件を最小にするために非常に高い圧縮率を有する。このシンドローム符号化器は、レート適合型であり、インクリメンタル形にオペレーションを行うことができる。先に送信されたシンドロームビットの情報を無駄にすることなく、必要に応じてより多くのビットを送信することができる。
【００４５】
認証フェーズ
認証フェーズ３２０では、バイオメトリックデータが、ユーザから再び取得される。特徴が抽出されて、認証バイオメトリックパラメータＥ’３６０が得られる。データベース３５０が検索されて、このユーザの一致する登録シンドロームＳ３３１及び登録ハッシュＨ３４１が突き止められる。
【００４６】
この検索は、データベース３５０のあらゆるエントリ（Ｓ−Ｈ対）をチェックすることもできるし、ヒューリスティックに順序付けられた検索を使用して、一致するエントリを見つけるプロセスを高速化することもできる。具体的には、発明者等が、データベースにおけるｉ番目のシンドローム−ハッシュの対を（Ｓｉ，Ｈｉ）と示す場合、全数検索は、まず、シンドローム復号をＥ’及びＳ１に適用し、シンドローム復号器の出力のハッシュをＨ１と比較する。アクセスが拒否される場合、同じプロセスが（Ｓ２，Ｈ２）で試みられ、次いで（Ｓ３，Ｈ３）で試みられ、すべてのエントリが試行されるか、又は、アクセスが許可されるまで、以下同様に試みられる。
【００４７】
登録ユーザ名等のサイド情報が利用可能である場合、そのサイド情報を使用して検索を高速化することができる。例えば、登録ユーザ名のハッシュが，登録フェーズの期間中にＳ及びＨの対と共に記憶される。次に、認証フェーズでは、ユーザが認証ユーザ名を供給し、システムが、その認証ユーザ名のハッシュを求め、一致する、ハッシュされた登録ユーザ名を有するＳ−Ｈ対を求めてデータベースを検索し、そして、その結果のＳ−Ｈ対でＥ’の認証を試みる。
【００４８】
具体的には、シンドローム復号器３７０が、登録シンドロームＳに適用され、認証パラメータＥ’３６０が「サイド」情報として働く。シンドローム復号器は、一般に当該技術分野において既知である。通常、確率伝播又はターボ符号を使用する復号器は、低い複雑度で優れた性能を有する。シンドローム復号器３７０の出力は、復号された登録パラメータＥ”３７１である。復号された値Ｅ”３７１は、シンドロームＳ３３１を生成するのに使用された元のバイオメトリックパラメータＥ３０１の推定値である。ハッシュ関数３４０がＥ”３７１に適用されて、認証ハッシュＨ’３８１が生成される。
【００４９】
登録値Ｈ３４１と認証値Ｈ’３８１とが比較される（３９０）。それらの値が一致しない場合、アクセスは拒否される（３９２）。そうでない場合、値Ｅ”３８１は、元のバイオメトリックＥ３０１と実質的に一致する。この場合、ユーザはアクセス許可を受けることができる（３９１）。
【００５０】
これに加えて、復号されたパラメータＥ”３８１と認証バイオメトリックパラメータＥ’３６０との間で直接比較を行って、ユーザを認証することもできる。例えば、Ｅ’及びＥ”が顔認識システムのバイオメトリックパラメータに対応する場合、顔の類似性を比較するための従来のアルゴリズムをパラメータＥ’及びパラメータＥ”に適用することができる。
【００５１】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るこのようなすべての変形及び変更を網羅することが添付の特許請求の範囲の目的である。
【図面の簡単な説明】
【００５２】
【図１】従来技術のパスワードに基づくセキュリティシステムのブロック図である。
【図２】従来技術のバイオメトリックに基づくセキュリティシステムのブロック図である。
【図３】本発明によるバイオメトリックセキュリティシステムのブロック図である。
【特許請求の範囲】
【請求項１】
シンドローム符号化器を使用してユーザの登録バイオメトリックパラメータを符号化することによって、登録シンドロームを生成すること、
前記登録シンドロームにハッシュ関数を適用することによって、登録ハッシュを生成すること、及び、
前記登録シンドローム及び前記登録ハッシュをデータベースに記憶すること
を含む、バイオメトリックパラメータをデータベースに安全に記憶するための方法。
【請求項２】
登録バイオメトリックデータをユーザから取得すること、及び、
前記登録バイオメトリックデータから前記登録バイオメトリックパラメータを抽出すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記登録バイオメトリックデータは顔の画像である、請求項２に記載の方法。
【請求項４】
前記登録バイオメトリックデータは音声の記録である、請求項２に記載の方法。
【請求項５】
前記登録バイオメトリックデータは指紋の画像である、請求項２に記載の方法。
【請求項６】
前記登録バイオメトリックデータは虹彩の画像である、請求項２に記載の方法。
【請求項７】
前記ハッシュ関数は暗号ハッシュ関数である、請求項１に記載の方法。
【請求項８】
前記シンドローム符号化器はＳｌｅｐｉａｎ−Ｗｏｌｆ符号化器である、請求項１に記載の方法。
【請求項９】
前記シンドローム符号化器はＷｙｎｅｒ−Ｚｉｖ符号化器である、請求項１に記載の方法。
【請求項１０】
前記シンドローム符号化器は直列連鎖累積符号を使用する、請求項１に記載の方法。
【請求項１１】
前記登録バイオメトリックパラメータは整数値を有する、請求項１に記載の方法。
【請求項１２】
前記シンドローム符号化器は、前記登録バイオメトリックパラメータを圧縮する、請求項１に記載の方法。
【請求項１３】
前記シンドローム符号化器はレート適合型である、請求項１に記載の方法。
【請求項１４】
前記シンドローム符号化器はインクリメンタルである、請求項１に記載の方法。
【請求項１５】
前記ユーザから認証バイオメトリックパラメータを取得すること、
シンドローム復号器及び前記認証バイオメトリックパラメータを使用して前記登録シンドロームを復号することによって、復号されたバイオメトリックパラメータを生成すること、
前記ハッシュ関数を前記復号されたバイオメトリックパラメータに適用することによって、認証ハッシュを生成すること、及び、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断すること
をさらに含む、請求項１に記載の方法。
【請求項１６】
前記認証バイオメトリックパラメータを前記復号された登録バイオメトリックパラメータと比較することによって、アクセスが許可されるか否かを確認すること
をさらに含む、請求項１５に記載の方法。
【請求項１７】
前記シンドローム復号器は確率伝播を使用する、請求項１５に記載の方法。
【請求項１８】
前記シンドローム復号器はターボ符号を使用する、請求項１５に記載の方法。
【請求項１９】
前記シンドローム復号はビタビアルゴリズムを使用する、請求項１５に記載の方法。
【請求項２０】
ユーザから登録バイオメトリックパラメータを取得するための手段と、
前記登録バイオメトリックパラメータを登録シンドロームとして符号化するように構成されるシンドローム符号化器と、
前記登録シンドロームから登録ハッシュを生成するように構成されるハッシュ関数と、
前記登録シンドローム及び前記登録ハッシュを記憶するように構成されるデータベースと
を備えた、バイオメトリックパラメータをデータベースに安全に記憶するためのシステム。
【請求項２１】
前記ユーザから認証バイオメトリックパラメータを取得するための手段と、
前記認証バイオメトリックパラメータを使用して前記登録シンドロームを復号するように構成され、復号されたバイオメトリックパラメータを生成する、復号器と、
前記ハッシュ関数を前記復号されたバイオメトリックパラメータに適用することによって、認証ハッシュを生成する、手段と、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断する、手段と
をさらに備える、請求項２０に記載のシステム。
【請求項２２】
シンドローム符号化器を使用してユーザの登録バイオメトリックパラメータを符号化することによって、登録シンドロームを生成すること、
前記登録シンドロームにハッシュ関数を適用することによって、登録ハッシュを生成すること、
シンドローム復号器及び前記ユーザの認証バイオメトリックパラメータを使用して前記登録シンドロームを復号することによって、復号されたバイオメトリックパラメータを生成すること、
前記復号されたバイオメトリックパラメータに前記ハッシュ関数を適用することによって、認証ハッシュを生成すること、及び、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断すること
を含む、バイオメトリックパラメータをデータベースに安全に記憶してユーザを認証するための方法。
【請求項１】
シンドローム符号化器を使用してユーザの登録バイオメトリックパラメータを符号化することによって、登録シンドロームを生成すること、
前記登録シンドロームにハッシュ関数を適用することによって、登録ハッシュを生成すること、及び、
前記登録シンドローム及び前記登録ハッシュをデータベースに記憶すること
を含む、バイオメトリックパラメータをデータベースに安全に記憶するための方法。
【請求項２】
登録バイオメトリックデータをユーザから取得すること、及び、
前記登録バイオメトリックデータから前記登録バイオメトリックパラメータを抽出すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記登録バイオメトリックデータは顔の画像である、請求項２に記載の方法。
【請求項４】
前記登録バイオメトリックデータは音声の記録である、請求項２に記載の方法。
【請求項５】
前記登録バイオメトリックデータは指紋の画像である、請求項２に記載の方法。
【請求項６】
前記登録バイオメトリックデータは虹彩の画像である、請求項２に記載の方法。
【請求項７】
前記ハッシュ関数は暗号ハッシュ関数である、請求項１に記載の方法。
【請求項８】
前記シンドローム符号化器はＳｌｅｐｉａｎ−Ｗｏｌｆ符号化器である、請求項１に記載の方法。
【請求項９】
前記シンドローム符号化器はＷｙｎｅｒ−Ｚｉｖ符号化器である、請求項１に記載の方法。
【請求項１０】
前記シンドローム符号化器は直列連鎖累積符号を使用する、請求項１に記載の方法。
【請求項１１】
前記登録バイオメトリックパラメータは整数値を有する、請求項１に記載の方法。
【請求項１２】
前記シンドローム符号化器は、前記登録バイオメトリックパラメータを圧縮する、請求項１に記載の方法。
【請求項１３】
前記シンドローム符号化器はレート適合型である、請求項１に記載の方法。
【請求項１４】
前記シンドローム符号化器はインクリメンタルである、請求項１に記載の方法。
【請求項１５】
前記ユーザから認証バイオメトリックパラメータを取得すること、
シンドローム復号器及び前記認証バイオメトリックパラメータを使用して前記登録シンドロームを復号することによって、復号されたバイオメトリックパラメータを生成すること、
前記ハッシュ関数を前記復号されたバイオメトリックパラメータに適用することによって、認証ハッシュを生成すること、及び、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断すること
をさらに含む、請求項１に記載の方法。
【請求項１６】
前記認証バイオメトリックパラメータを前記復号された登録バイオメトリックパラメータと比較することによって、アクセスが許可されるか否かを確認すること
をさらに含む、請求項１５に記載の方法。
【請求項１７】
前記シンドローム復号器は確率伝播を使用する、請求項１５に記載の方法。
【請求項１８】
前記シンドローム復号器はターボ符号を使用する、請求項１５に記載の方法。
【請求項１９】
前記シンドローム復号はビタビアルゴリズムを使用する、請求項１５に記載の方法。
【請求項２０】
ユーザから登録バイオメトリックパラメータを取得するための手段と、
前記登録バイオメトリックパラメータを登録シンドロームとして符号化するように構成されるシンドローム符号化器と、
前記登録シンドロームから登録ハッシュを生成するように構成されるハッシュ関数と、
前記登録シンドローム及び前記登録ハッシュを記憶するように構成されるデータベースと
を備えた、バイオメトリックパラメータをデータベースに安全に記憶するためのシステム。
【請求項２１】
前記ユーザから認証バイオメトリックパラメータを取得するための手段と、
前記認証バイオメトリックパラメータを使用して前記登録シンドロームを復号するように構成され、復号されたバイオメトリックパラメータを生成する、復号器と、
前記ハッシュ関数を前記復号されたバイオメトリックパラメータに適用することによって、認証ハッシュを生成する、手段と、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断する、手段と
をさらに備える、請求項２０に記載のシステム。
【請求項２２】
シンドローム符号化器を使用してユーザの登録バイオメトリックパラメータを符号化することによって、登録シンドロームを生成すること、
前記登録シンドロームにハッシュ関数を適用することによって、登録ハッシュを生成すること、
シンドローム復号器及び前記ユーザの認証バイオメトリックパラメータを使用して前記登録シンドロームを復号することによって、復号されたバイオメトリックパラメータを生成すること、
前記復号されたバイオメトリックパラメータに前記ハッシュ関数を適用することによって、認証ハッシュを生成すること、及び、
前記認証ハッシュと前記登録ハッシュとを比較することによって、アクセスが許可されるか否かを判断すること
を含む、バイオメトリックパラメータをデータベースに安全に記憶してユーザを認証するための方法。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２００６−１６６４３３（Ｐ２００６−１６６４３３Ａ）
【公開日】平成１８年６月２２日（２００６．６．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２００５−３３８２３７（Ｐ２００５−３３８２３７）
【出願日】平成１７年１１月２４日（２００５．１１．２４）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成１８年６月２２日（２００６．６．２２）
【国際特許分類】
【出願番号】特願２００５−３３８２３７（Ｐ２００５−３３８２３７）
【出願日】平成１７年１１月２４日（２００５．１１．２４）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]