(57)【要約】【課題】生体情報を入力しユーザIDを出力するような生体認証システム（１：Ｎ認証システム）において、サーバに対し生体情報を秘匿したまま照合するキャンセラブル生体認証を実現する際に、サーバ側での１：Ｎ照合を高速化させる。【解決手段】登録時は、ダミー特徴量に対し特徴量ｘの類似検索を行い、最近傍ダミー特徴量Ｄ[i*]に対応する変換パラメータＲ[i*]を用いて、特徴量ｘを変換する（変換特徴量Ｔ）。変換特徴量ＴとグループＩＤ＝i*をサーバへ送信し、サーバは該当グループのＤＢへ変換特徴量Ｔを登録する。認証時は、登録時と同様に、特徴量ｙの類似検索を行い最近傍ダミー特徴量Ｄ[i*]し、対応する変換パラメータＲ[i*]を用いて特徴量ｙを変換する（変換特徴量Ｖ）。変換特徴量ＶとグループＩＤ＝i*をサーバへ送信する。サーバは、該当グループのＤＢ内のテンプレートと変換特徴量Ｖとの間で１：１照合を実行する。【選択図】図１
2010286937.tif 000002
【特許請求の範囲】
【請求項１】
クライアント端末は、個人の生体情報から抽出した認証用特徴量を変換パラメータで変換した認証用変換特徴量を認証サーバに送信し、
前記認証サーバは、複数の登録用変換特徴量と個人を特定する情報と対応付けて格納するデータベースを備え、前記データベースを検索して、前記認証用変換特徴量に最も類似する前記登録用変換特徴量に対応付けられた個人を特定する生体認証方法において、
前記クライアント端末は、予め、生体情報の登録用特徴量と前記認証用特徴量とを複数のグループのいずれかに分類するための基準とするダミー特徴量と、前記グループを識別するためのインデックスと、各々の前記ダミー特徴量に対応した変換パラメータと、をクライアント側データベースに記憶し、
前記認証サーバは、前記変換パラメータにより前記登録用特徴量から変換された登録用変換特徴量と、前記登録用特徴量の抽出元である個人を特定する情報と、を、前記インデックスに基づき、前記複数のグループのいずれかに分類して記憶するための登録用変換特徴量データベースを備え、
生体情報の登録時の処理として、
前記クライアント端末における、
個人から取得した生体情報から前記登録用特徴量を抽出するステップと、
前記クライアント側データベースを検索して、前記登録用特徴量に類似した一つの登録用ダミー特徴量を特定するステップと、
前記特定した登録用ダミー特徴量に対応した前記変換パラメータを用いて、前記登録用特徴量を変換して、登録用変換特徴量を作成するステップと、
前記登録用変換特徴量と、特定した前記登録用ダミー特徴量のグループを識別する登録用インデックスと、前記登録用特徴量の抽出元である前記個人を特定する情報と、を前記認証サーバへと送信するステップと、
前記認証サーバにおける、
前記登録用変換特徴量データベースの前記登録用インデックスに対応したグループに、受信した前記登録用変換特徴量と、前記個人を特定する情報と、を対応付けて登録するステップと、を含む
ことを特徴とする生体認証方法。
【請求項２】
請求項１に記載の生体認証方法において、
予め、抽出した複数の前記登録用特徴量を、所定の基準に従って複数のグループに分割し、
一つのグループに含まれる前記登録用特徴量から算出したセントロイドを当該グループに対応する前記ダミー特徴量とする
ことを特徴とする生体認証方法。
【請求項３】
請求項１または２に記載の生体認証情報の登録方法によって登録された生体認証情報に基づく生体認証方法において、
認証時の処理として、
前記クライアント端末における、
個人から取得した生体情報から認証用特徴量を抽出するステップと、
前記クライアント側データベースを検索して、前記認証用特徴量に類似した一つの認証用ダミー特徴量を特定するステップと、
前記特定した認証用ダミー特徴量に対応した前記変換パラメータを用いて、前記認証用特徴量を変換して、認証用変換特徴量を作成するステップと、
前記認証用変換特徴量と、特定した前記認証用ダミー特徴量のグループを識別する認証用インデックスと、を、前記認証サーバへと送信するステップと、
前記認証サーバにおける、
前記登録用変換特徴量データベースの前記認証用インデックスに対応したグループを検索して、前記認証用変換特徴量に最も類似した前記登録用変換特徴量を特定するステップと、
特定した前記登録用変換特徴量に対応づけられた個人を特定するステップと、
特定した前記個人に関わる情報を前記クライアント端末に送信するステップと、を含む
ことを特徴とする生体認証方法。
【請求項４】
請求項１ないし３いずれか一に記載の生体認証方法において、
前記クライアント端末における、前記登録用特徴量に類似した一つの登録用ダミー特徴量を特定するステップと、前記認証用特徴量に類似した一つの認証用ダミー特徴量を特定するステップと、において、
Locality−Sensitive HashingまたはApproximating and Eliminating Search Algorithmを用いる
ことを特徴とする生体認証方法。
【請求項５】
個人の生体情報から抽出した登録用特徴量を変換パラメータで変換した登録用変換特徴量を認証サーバに送信し、登録させる生体認証に用いるクライアント端末であって、
予め、生体情報の登録用特徴量と認証用特徴量とを複数のグループのいずれかに分類するための基準とするダミー特徴量と、前記グループを識別するためのインデックスと、各々の前記ダミー特徴量に対応した変換パラメータと、をクライアント側データベースに記憶し、
個人から取得した生体情報から前記登録用特徴量を抽出し、
前記クライアント側データベースを検索して、前記登録用特徴量に類似した一つの登録用ダミー特徴量を特定し、
前記特定した登録用ダミー特徴量に対応した前記変換パラメータを用いて、前記登録用特徴量を変換して、登録用変換特徴量を作成し、
前記登録用変換特徴量と、特定した前記登録用ダミー特徴量のグループを識別する登録用インデックスと、前記登録用特徴量の抽出元である前記個人を特定する情報と、を前記認証サーバへと送信する
ことを特徴とする生体認証に用いるクライアント端末。
【請求項６】
請求項５に記載の生体認証に用いるクライアント端末において、
予め、抽出した複数の前記登録用特徴量を、所定の基準に従って複数のグループに分割し、
一つのグループに含まれる前記登録用特徴量から算出したセントロイドを当該グループに対応する前記ダミー特徴量とする
ことを特徴とする生体認証に用いるクライアント端末。
【請求項７】
請求項５または６に記載の生体認証に用いるクライアント端末において、
個人から取得した生体情報から認証用特徴量を抽出し、
前記クライアント側データベースを検索して、前記認証用特徴量に類似した一つの認証用ダミー特徴量を特定し、
前記特定した認証用ダミー特徴量に対応した前記変換パラメータを用いて、前記認証用特徴量を変換して、認証用変換特徴量を作成し、
前記認証用変換特徴量と、特定した前記認証用ダミー特徴量のグループを識別する認証用インデックスと、を、前記認証サーバへと送信し、
前記認証サーバから、特定した個人に関わる情報を受信する
ことを特徴とする生体認証に用いるクライアント端末。
【請求項８】
請求項５ないし７いずれか一に記載の生体認証に用いるクライアント端末において、
前記登録用特徴量に類似した一つの登録用ダミー特徴量の特定において、
Locality−Sensitive HashingまたはApproximating and Eliminating Search Algorithmを用いる
ことを特徴とする生体認証に用いるクライアント端末。
【請求項９】
複数の登録用変換特徴量と個人を特定する情報と対応付けて格納するデータベースを備え、前記データベースを検索して、認証用変換特徴量に最も類似する前記登録用変換特徴量に対応付けられた個人を特定する生体認証方法に用いる認証サーバであって、
前記データベースに格納される前記登録用変換特徴量は、所定の基準に従い、複数の、インデックスが付与されたグループに分割されており、
前記登録用変換特徴量と、前記グループを識別するインデックスと、前記登録用特徴量の抽出元である前記個人を特定する情報と、を受信し、
前記データベースの前記インデックスに対応したグループに、受信した前記登録用変換特徴量と、前記個人を特定する情報と、を対応付けて登録する
ことを特徴とする認証サーバ。
【請求項１０】
請求応９に記載の認証サーバにおいて、
前記認証用変換特徴量と、前記グループを識別するインデックスと、を受信し、
前記データベースの前記インデックスに対応したグループを検索して、前記認証用変換特徴量に最も類似した前記登録用変換特徴量を特定し、
特定した前記認証用変換特徴量に対応づけられた個人を特定し、
特定した前記個人に関わる情報を、前記認証用変換特徴量の送信元に送信する
ことを特徴とする認証サーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、個人の生体情報を用いて本人を認証する生体認証方法およびシステムに関する。
【背景技術】
【０００２】
生体情報を用いた個人認証システムは、初期の登録時に個人の生体情報を取得し、特徴量と呼ばれる情報を抽出して登録する。この登録される特徴量をテンプレートという。認証時には、再び個人から生体情報を取得して特徴量を抽出し、先に登録されたテンプレートと照合して本人か否かを確認する。
【０００３】
クライアント装置（クライアントという）とサーバ装置（サーバという）がネットワークを介して接続されたシステムにおいて、サーバがクライアント側にいるユーザを生体認証する場合、典型的にはサーバがテンプレートを保持する。クライアントは認証時にユーザの生体情報を取得し、特徴量を抽出してサーバへ送信し、サーバは特徴量をテンプレートと照合して本人か否かを確認する。
【０００４】
しかし、テンプレートは個人を特定することのできる情報であるため、個人情報として厳密な管理が必要とされ、高い管理コストが必要となる。また、例え厳密に管理されていても、プライバシの観点からテンプレートを登録することに心理的な抵抗を感じる人も多い。また、生体情報は一生涯変わることがなく、パスワードや暗号鍵のように容易に変更することができない。他の生体情報に取り替えることが考えられるが、一人の個人が持つ一種類の生体情報の数には限りがある（例えば指紋は指の数）ため、根本的な解決策とはならない。このため、仮にテンプレートが漏洩して偽造の危険が生じた場合、これ以降その生体認証を安全に使用することができなくなるという問題がある。さらに、異なるシステムに対して同じ生体情報を登録している場合には他のシステムまで脅威に晒されることになる。
【０００５】
そこで、生体情報の登録時に特徴量を一定の関数（一種の暗号化）とクライアントが持つ秘密のパラメータ（一種の暗号鍵）で変換し、元の情報を秘匿した状態でテンプレートとしてサーバに保管し、認証時にクライアントが新たに抽出した生体情報の特徴量を、同じ関数とパラメータで変換してサーバへ送信し、サーバは受信した特徴量とテンプレートを変換された状態のまま照合する方法（キャンセラブル生体認証という）が，非特許文献１で提案されている。
【０００６】
この方法によれば、クライアントが変換パラメータを秘密に保持することで、サーバは認証時においても元の特徴量を知ることができず、個人のプライバシが保護される。
またテンプレートが漏洩した場合にも、変換パラメータを変更して再度テンプレートを作成、登録することで、安全性を保つことができる。更に異なるシステムに対して同じ生体情報を用いる場合に、各々異なるパラメータで変換したテンプレートを登録することで、一つのテンプレートが漏洩しても他のシステムの安全性が低下することを防止することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】N.K.Ratha， J.H.Connell， R.M.Bolle， ‘Enhancing security and privacy in biometric−based authentication systems.’ IBM System Journal 40(3) (2001)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記非特許文献１によれば、登録時、クライアントはユーザの生体から抽出した特徴量画像ｘを変換パラメータθを用いて変換し，変換特徴量Ｔを作成し、サーバに登録する。変換パラメータθはＩＣカードなどに保存してユーザが秘密裏に管理する。
【０００９】
認証時にはクライアントがあらたにユーザの生体から抽出した特徴量画像ｙを、ユーザのＩＣカードから読み出した変換パラメータθを用いて変換し，変換特徴量Ｖを作成し、サーバに送信する。サーバはＴとＶの類似度を計算し、一致／不一致を判定する。
【００１０】
このように秘密の変換パラメータθによってｘ、ｙを変換して求めたＴ，Ｖをサーバに送信することで、サーバに対してｘ、ｙを秘匿したまま、サーバが照合処理を実行可能とする。
【００１１】
ところで，（ユーザＩＤを入力せずに）生体情報を入力しユーザIDを出力するようなシステム（以下，１：Ｎ認証と呼ぶ）にキャンセラブル生体認証を適用する場合，単純には，サーバのＤＢ内にある全ての変換特徴量Ｔと照合を行う必要がある。しかし，大規模なＤＢの場合一般に，全てのＴと照合するには処理時間が長くなり，実用的でない問題がある。
【課題を解決するための手段】
【００１２】
本発明は、キャンセラブル生体認証を１：Ｎ認証システムに適用するに際し，サーバ側での１：Ｎ照合に要する時間を短縮し，処理を高速化させる生体認証技術を提供する。
【００１３】
本発明は以上の課題を解決するため、クライアントとサーバとを含むシステムにおいて、個人のＩＤを用いずに、生体情報を用いて個人を認証する生体認証方法における生体情報の登録方法において、類似する特徴量でグループを構成する場合の、グループの代表となるダミー特徴量を予め設定しておき、クライアントにおいて、登録対象となる特徴量が属すべきグループを、ダミー特徴量に基づき特定する概略処理を行い、サーバにおいて、上記特定したグループに、上記登録用の変換特徴量を登録する処理を行う、ことを特徴とする。
【００１４】
また、本発明は、クライアントとサーバとを含むシステムにおいて、個人のＩＤを用いずに、生体情報を用いて個人を認証する生体認証方法において、類似する特徴量でグループを構成し、グループの代表となるダミー特徴量を予め設定しておき、クライアントにおいて、認証対象となる特徴量が属するグループを、上記ダミー特徴量に基づき特定する概略処理を行い、サーバにおいて、特定したグループを対象に、類似するいずれか一つの特徴量を特定する詳細処理を行う、ことを特徴とする。
【００１５】
さらに、上記特徴量は、個人から抽出した生体情報を所定のパラメータで変換した変換特徴量であることを特徴とする。
【００１６】
本発明は、より具体的には、クライアント端末は、個人の生体情報から抽出した認証用特徴量を変換パラメータで変換した認証用変換特徴量を認証サーバに送信し、認証サーバは、複数の登録用変換特徴量と個人を特定する情報と対応付けて格納するデータベースを備え、データベースを検索して、認証用変換特徴量に最も類似する登録用変換特徴量に対応付けられた個人を特定する生体認証方法において、
クライアント端末は、予め、生体情報の登録用特徴量と認証用特徴量とを複数のグループのいずれかに分類するための基準とするダミー特徴量と、グループを識別するためのインデックスと、各々のダミー特徴量に対応した変換パラメータと、をクライアント側データベースに記憶し、
認証サーバは、変換パラメータにより登録用特徴量から変換された登録用変換特徴量と、登録用特徴量の抽出元である個人を特定する情報と、を、インデックスに基づき、複数のグループのいずれかに分類して記憶するための登録用変換特徴量データベースを備え、
生体情報の登録時の処理として、
クライアント端末は、
個人から取得した生体情報から登録用特徴量を抽出するステップと、
クライアント側データベースを検索して、登録用特徴量に類似した一つの登録用ダミー特徴量を特定するステップと、
特定した登録用ダミー特徴量に対応した変換パラメータを用いて、登録用特徴量を変換して、登録用変換特徴量を作成するステップと、
登録用変換特徴量と、特定した登録用ダミー特徴量のグループを識別する登録用インデックスと、登録用特徴量の抽出元である個人を特定する情報と、を認証サーバへと送信するステップと、を備え、
認証サーバは、
登録用変換特徴量データベースの登録用インデックスに対応したグループに、受信した登録用変換特徴量と、個人を特定する情報と、を対応付けて登録するステップと、を備えることを特徴とする。
【００１７】
また、本発明の認証時の処理として、
クライアント端末は、
個人から取得した生体情報から認証用特徴量を抽出するステップと、
クライアント側データベースを検索して、認証用特徴量に類似した一つの認証用ダミー特徴量を特定するステップと、
特定した認証用ダミー特徴量に対応した変換パラメータを用いて、認証用特徴量を変換して、認証用変換特徴量を作成するステップと、
認証用変換特徴量と、特定した認証用ダミー特徴量のグループを識別する認証用インデックスと、を、認証サーバへと送信するステップと、を備え、
認証サーバは、
登録用変換特徴量データベースの認証用インデックスに対応したグループを検索して、認証用変換特徴量に最も類似した登録用変換特徴量を特定するステップと、
特定した登録用変換特徴量に対応づけられた個人を特定するステップと、
特定した個人に関わる情報をクライアント端末に送信するステップと、を備えることを特徴とする。
【００１８】
上記態様によれば、生体情報を入力してユーザＩＤを出力する１：Ｎ生体認証システムにおいて、サーバ側での１：Ｎ照合に要する時間を短縮し，処理を高速化させることができる。
【発明の効果】
【００１９】
本発明によれば、ユーザの生体情報を秘匿したまま高速認証が可能な、１：Ｎ生体認証システムを実現可能になる。
【図面の簡単な説明】
【００２０】
【図１】第一の実施形態の機能構成を例示するブロック図である。
【図２】実施形態におけるダミー特徴量作成処理を例示する流れ図である。
【図３】実施形態におけるダミー特徴量のハッシュテーブル差作成処理を例示する流れ図である。
【図４】実施形態における登録処理を例示する流れ図である。
【図５】実施形態における１：Ｎ認証処理を例示する流れ図である。
【図６】実施形態におけるハードウェア構成を例示するブロック図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して、本発明の実施形態について説明する。
【００２２】
本実施形態では、キャンセラブル生体認証を１：Ｎ認証に適用した，１：Ｎキャンセラブル生体認証システムを例にあげて説明する。
【００２３】
図１に、１：Ｎキャンセラブル生体認証システムのシステム構成を示す。
【００２４】
本実施例の１：Ｎキャンセラブル生体認証システムは、登録・認証時の生体情報取得、特徴量抽出、ダミー特徴量との類似検索，および特徴量の変換を行うクライアント端末（以下、クライアント）１００と、ダミー特徴量を含む補助データＤＢの作成などを行う補助データＤＢ作成端末（以下、補助データＤＢ作成端末）１１０と、テンプレートの保管と１：Ｎ照合を行う認証サーバ（以下、サーバ）１２０とが、インターネットやイントラネットなどのネットワークを介し接続して構成される。
【００２５】
クライアント１００は、ユーザ自身か又は信頼できる第三者によって管理され、生体情報（例えば指紋や静脈など）を取得するセンサ１０７を有する。例えば小売店舗でクレジット決済を行う場合、クライアント１００は店舗が管理するクレジット端末であり、サーバ１２０はクレジット会社が管理するサーバマシンとするような構成も可能である。
【００２６】
クライアント１００は、センサ１０７が取得した生体情報から特徴量を抽出する特徴量抽出部１０１と、複数のダミー特徴量が予め格納された補助データＤＢ１０３と，補助データＤＢ１０３内のダミー特徴量との類似検索を行う類似検索部１０２と，ダミー特徴量おのおのに対応する変換パラメータを格納した変換パラメータＤＢ１０５と，登録用または認証用の特徴量を変換して、登録用変換特徴量（以下、テンプレートという）または認証用変換特徴量を作成する特徴量変換部１０４と、サーバとの通信を行う通信部１０６から構成される。
【００２７】
ここで生体情報とは、例えば指紋画像や静脈画像、虹彩画像といったデータであり、特徴量とは、例えば指紋や静脈の画像を強調処理して２値化した画像や、あるいは虹彩画像から作成するアイリスコード（虹彩コード）と呼ばれるビット列などを含む。２つの特徴量の間の類似度は、たとえば相互相関により計算されるものなどがある。相互相関に基づいて類似度を計算する照合アルゴリズムに対しては、２つの特徴量に特殊な変換を施して
元の特徴量を秘匿したまま、それらを元に戻すことなく類似度を計算するアルゴリズム（相関不変ランダムフィルタリング）が知られている。なお相関不変ランダムフィルタリングの詳細については、特開2007−293807号公報（文献１という）や比良田 他，”画像マッチングに適用可能なキャンセラブル生体認証方式の脆弱性分析と安全性向上”， SCIS2007予稿集CD−ROM（文献２という）に開示されている。
【００２８】
補助データＤＢ作成端末１１０は、ダミー特徴量を作成する元となる特徴量のＤＢである特徴量ＤＢ１１２、特徴量ＤＢ内の特徴量の集合に対してクラスタリングを行うクラスタリング部１１１、クラスタリング結果を利用してダミー特徴量を作成するダミー特徴量作成部１１３、クライアントにてダミー特徴量との類似検索に用いる補助データを作成する補助データ作成部１１５、補助データを格納する補助データＤＢ１１４、クライアント１００と通信を行う通信部１１６とから構成される。
【００２９】
サーバ１２０は、クライアント１００と通信を行う通信部１２１、テンプレートを管理するデータベース（テンプレートＤＢ。以下、データベースをＤＢと記す）１２２、クライアントから受信したテンプレートをテンプレートＤＢ１２２に登録する登録部１２３、クライアントから受信した変換特徴量とテンプレートＤＢ１２２内の複数のテンプレートとの照合を行う１：Ｎ照合部１２４とから構成される。
【００３０】
図６に、本実施形態におけるクライアント１００、サーバ１２０のハードウェア構成を示す。これらは図のようにＣＰＵ６００、メモリ６０１、ＨＤＤ６０２、入力装置６０３、出力装置６０４、通信装置６０５とから構成することができる。
【００３１】
クライアント１００、補助データＤＢ作成端末１１０、サーバ１２０の上記機能構成や、以下に説明する各処理は、それぞれのＣＰＵ６００がメモリ６０１またはＨＤＤ６０２に格納されたプログラムを実行することにより、具現化される。また、各プログラムは、予めそれぞれのメモリ６０１、ＨＤＤ６０２に格納されていても良いし、必要に応じて、当該装置が利用可能な、着脱可能な記憶媒体や、通信媒体である通信ネットワークまたは通信ネットワーク上を伝搬する搬送波やデジタル信号を介して、他の装置から導入されても良い。
【００３２】
次に、図２を用いて、本実施形態におけるダミー特徴量の作成処理フローを説明する。
ここでは一例として、Jiawei Han and Micheline Kamber， “Data Mining”， pp.348−353，  Morgan Kaufmann Publishers， 2001（文献３という）記載のセントロイドを用いた方法を示す。これ以外の方法でダミー特徴量を生成してもよい。
【００３３】
事前にシステム開発の段階で，開発者など有志から生体情報を収集しておき，特徴量の集合{ｘ[i]}を作成しておく。特徴量ＤＢ１１２に格納しておく。ここで例えば生体情報が指静脈画像の場合、特徴量抽出の方法は、N.Miura， A.Nagasaka， T.Miyatake， “Feature extraction of nger−vein patterns based on repeated line tracking and its application to personal identication.” Machine Vision and Applications 15(4) (2004) 194−203（文献４という）に記載の方法などを用いることができる。
【００３４】
クラスタリング部１１１は，特徴量の集合{ｘ[i]}を読込みクラスタリングを行う（Ｓ２０１）。クラスタリングによって，類似した特徴量同士がグループ化される。クラスタリングの詳細は文献３を参照のこと。特徴量のグループの集合を｛Ｇ[j]｝とする。Ｇ[j]には，特徴量ｘ[j，k]が含まれる。ここで，iは特徴量ＤＢ内の特徴量のインデックス，jはグループのインデックス，kはグループjに含まれる特徴量のインデックス。
【００３５】
クラスタリングの具体的な方法としては例えば， k−means 法が利用できる。ここでk−means 法の概要を説明する。k−means 法は，非階層的クラスタ分析の代表的手法であり，典型的にはユークリッド空間を仮定する。この方法では，クラスタ数をあらかじめ指定し（ここではk），対象をk 個のクラスに分割する。非類似度としてユークリッド距離の２乗をとり，クラスタの中心と各対象との間の非類似度を分類の基準とする。k−means法はクラスタ数を指定できるため，各クラスタ間での対象数の偏りを軽減できるメリットがある。k−means 法のアルゴリズムは以下のとおり。
step1. [初期値]k 個のクラスタ中心あるいは初期分割をランダムに与える。
step2. [割り当て] 各対象を最も近いクラスタ中心に割り当てる。
step3. [中心の更新] すべての対象の割り当てが一つ前のステップと変化が無ければ終了。そうでなければ，各クラスタの重心を新しい中心としてstep2 に戻る。
【００３６】
ここで，クラスタの中心の各座標は，そのクラスタに含まれる対象の座標の重みつき平均で表され，またクラスタの重心の各座標は重みつきの無い平均で表される。
【００３７】
ダミー特徴量作成部１１３は，グループＧ[j]ごとのセントロイドＤ[j]を作成する（Ｓ２０２）。セントロイドとは，グループに含まれる特徴量の重心となる特徴量のことである。詳細は文献３を参照のこと。作成したセントロイドの集合{Ｄ[j]}をダミー特徴量の集合{Ｄ[j]}として、補助データＤＢ１１４に書き出す（Ｓ２０３）。
【００３８】
次に，本実施形態における変換パラメータＤＢ105の作成方法を説明する。ここで変換パラメータは，ダミー特徴量Ｄ[i]それぞれに対し，個別に作成し対応づける。ダミー特徴量Ｄ[i]に対応する変換パラメータをＲ[i]とする。変換パラメータＲ[i]の作成方法であるが，たとえば指静脈画像の場合，文献１や文献２に記載の方法を用いることができる。具体的には，各画素の値が乱数となるような２次元のランダムフィルタを作成すればよい。乱数は，疑似乱数生成器などを用いて発生させる。このランダムフィルタを変換パラメータＲ[i]とする。
【００３９】
本実施形態におけるダミー特徴量との類似検索方法は，ここでは一例として， P. Indyk and R. Motwani，”Approximate nearest neighbors: towards removing the curse of dimensionality”， Proc. of the Symposium on Theory of Computing， 1998.（文献５という）に記載のLocality−Sensitive Hashing（以下，ＬＳＨと呼ぶ）を用いるものとする。これ以外の方法で類似検索をしても良い。たとえば、Vidal Ruiz， “An algorithm for finding nearest neighbours in (approximately) constant average time，” Pattern Recognition Letters pp.145−157， 1986.（文献６という）記載のApproximating and Eliminating Search Algorithm（以下、ＡＥＳＡと呼ぶ）などが利用できる。
【００４０】
ＬＳＨでは，ハッシュテーブルが必要となる。図３を用いて，ハッシュテーブル作成方法を説明する。
補助データ作成部１１５は、補助データＤＢ１１４に格納されているダミー特徴量集合｛Ｄ[i]｝を読み込む（Ｓ３０１）。
【００４１】
補助データ作成部１１５は、ハッシュテーブルを作成する（Ｓ３０２）。ここでは一例として、M.Datar， N.Immorlica，P.Indyk， and V.Mirrokni，”Locality−sensitive hashing scheme based on p−stable distributions.”， Proc. of the ACM Symposium on Computational Geometry， 2004.（文献７という）記載の方法を用いるものとする。これ以外の方法でも良い。文献７では，特徴量ベクトルvに対し，以下の式でハッシュを作成する。
【００４２】
【数１】
2010286937.tif 000003
【００４３】
なお、ＬＳＨで用いるハッシュ関数は、局所性に鋭敏なハッシュ関数と呼ばれ、以下のように定義される（以下，局所鋭敏ハッシュ関数と呼ぶ）。対象とする元の空間をS、生成されるハッシュ値の空間をU とする。ハッシュ関数集合H = { h : S →U } が次を満たすとき，局所鋭敏ハッシュ関数集合と定義される：
(a) もし点v がq から半径r1 以内に存在する場合，v とq のハッシュ値が衝突する確率はp1 以上、
(b) もし点v がq から半径r2(= cr1) 以内に存在しない場合，v とq のハッシュ値が衝突する確率はp2(p2 < p1) 以下。 
（式１）を用いて，ダミー特徴量Ｄ[i]のハッシュｈ[Ｄ[i]]を作成する。ハッシュテーブルは，（ｈ[Ｄ[i]]，Ｄ[i]）を要素とするテーブルとして作成する。なお，ＬＳＨを用いた類似検索については後述する。
【００４４】
以上で作成したハッシュテーブルを補助データＤＢ１１４に格納する。
【００４５】
そして、補助データＤＢ作成端末は、補助データＤＢ１１４のデータをクライアントに送信する。クライアントは、受信したデータを補助データＤＢ１０３に格納しておく。 
次に，図４を用いて，本実施形態における登録処理のフローを説明する。
【００４６】
センサ１０７は、ユーザの生体情報を取得する（Ｓ４０１）。
【００４７】
特徴量抽出部１０１は、生体情報から特徴量ｘを抽出する（Ｓ４０２）。特徴量抽出の方法は，たとえば指静脈画像であれば，文献４に記載の方法などを用いることができる。
【００４８】
類似検索部１０２は、ハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝を補助データDB103から読み込む（Ｓ４０３）。
【００４９】
類似検索部１０２は、読み込んだハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝を検索して，特徴量ｘに類似するダミー特徴量を特定する（Ｓ４０４）。
ここでは，たとえば一例として，文献５および文献７記載のＬＳＨという方法を用いるものとする。これ以外の方法、たとえば文献６記載のAESAを用いても良い。
【００５０】
まず（式１）を用いて，特徴量ｘのハッシュ値ｈ[ｘ]を算出する。次に読み込んだハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝内のハッシュの集合｛ｈ[Ｄ[i]]｝に対し，ハッシュｈ[x]と一致するものを検索する。ハッシュ値が一致するダミー特徴量Ｄ[i]は一般に一つ以上存在する。これらをハッシュ一致ダミー特徴量Ｄ*[i]と呼ぶ。そして，複数存在する場合は、それぞれのハッシュ一致ダミー特徴量Ｄ*[i]と特徴量ｘを照合する。照合の方法はたとえば相互相関を用いたものがある。相互相関が最大となるハッシュ一致ダミー特徴量を、特徴量ｘに最も類似したダミー特徴量とする。これを最近傍ダミー特徴量Ｄ*[i*]と呼ぶ。類似検索の結果は、最近傍ダミー特徴量Ｄ*[i*]のインデックスi*とする。
【００５１】
特徴量変換部１０４は、最近傍ダミー特徴量Ｄ*[i*]に対応する変換パラメータＲ[i*]を読み出す（Ｓ４０５）。
【００５２】
特徴量変換部１０４は、変換パラメータＲ[i*]を用いて，特徴量ｘを変換する（Ｓ４０６）。たとえば指静脈認証など，２つの特徴量の間の類似度は相互相関により計算されるものなどがある。相互相関に基づいて類似度を計算する照合アルゴリズムに対しては、２つの特徴量に特殊な変換を施して秘匿したまま、それらを元に戻すことなく類似度を計算するアルゴリズム（相関不変ランダムフィルタリング）が知られている（詳細については文献１や文献２を参照）。この場合，変換パラメータＲ[i*]は，各画素値が乱数であるランダムフィルタである。変換処理では，まず特徴量ｘを基底変換（数論変換やフーリエ変換など）し（基底変換後のデータをＸとする），つぎにＸに対してランダムフィルタを画素ごとに乗算する。以上が代表的な変換処理の例であるが，そのほかの方法を用いてもよい。
【００５３】
変換後の特徴量ＴをテンプレートＴとし、最近傍ダミー特徴量Ｄ*[i*]のインデックスi*をグループＩＤとする。テンプレートTと、グループＩＤi*をサーバ120へ送信する。
【００５４】
サーバ120は、テンプレートＤＢ122の、i*をＩＤとするグループにテンプレートＴを登録する（Ｓ４０７）。
【００５５】
次に，図５を用いて，本実施形態における１：Ｎ認証処理のフローを説明する。
センサ１０７は、ユーザの生体情報を取得する（Ｓ５０１）。
【００５６】
特徴量抽出部１０１は、生体情報から特徴量ｙを抽出する（Ｓ５０２）。特徴量抽出の方法は，たとえば指静脈画像であれば，文献４に記載の方法などを用いることができる。
【００５７】
類似検索部１０２は、ハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝を補助データＤＢ103から読み込む（Ｓ５０３）。
【００５８】
類似検索部１０２は、読み込んだハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝を検索して，特徴量ｙに類似するダミー特徴量を特定する（Ｓ５０４）。ここでは，たとえば一例として，文献２および文献５記載のＬＳＨという方法を用いるものとするが、これ以外の方法でも良い。他には例えば、文献６記載のAESAを用いても良い。
【００５９】
まず（式１）を用いて，特徴量ｙのハッシュ値ｈ[ｙ]を算出する。次に読み込んだハッシュテーブル｛ｈ[Ｄ[i]]，Ｄ[i]｝内のハッシュ集合｛ｈ[Ｄ[i]]｝に対し，ハッシュｈ[ｙ]と一致するものを検索する。ハッシュ値が一致するダミー特徴量Ｄ[i]は一般に一つ以上存在する。これらをハッシュ一致ダミー特徴量Ｄ*[i]と呼ぶ。そして，複数存在する場合は、それぞれのハッシュ一致ダミー特徴量Ｄ*[i]と特徴量ｙを照合する。照合の方法はたとえば相互相関を用いたものがある。相互相関が最大となるハッシュ一致ダミー特徴量を、特徴量ｙに最も類似したダミー特徴量とする。これを最近傍ダミー特徴量Ｄ*[i*]と呼ぶ。類似検索の結果は、最近傍ダミー特徴量Ｄ*[i*]のインデックスi*とする。
【００６０】
特徴量変換部１０４は、最近傍ダミー特徴量Ｄ*[i*]に対応する変換パラメータＲ[i*]を読み出す（Ｓ５０５）。
【００６１】
特徴量変換部１０４は、変換パラメータＲ[i*]を用いて，特徴量ｙを変換する（Ｓ５０６）。たとえば指静脈認証など，２つの特徴量の間の類似度は相互相関により計算されるものなどがある。相互相関に基づいて類似度を計算する照合アルゴリズムに対しては、２つの特徴量に特殊な変換を施して秘匿したまま、それらを元に戻すことなく類似度を計算するアルゴリズム（相関不変ランダムフィルタリング）が知られている（詳細については文献１や文献２を参照）。この場合，変換パラメータＲ[i*]は，各画素値が乱数であるランダムフィルタである。変換処理では，まず特徴量ｙを基底変換（数論変換やフーリエ変換など）し（基底変換後のデータをＹとする），つぎにＹに対してランダムフィルタを画素ごとに除算する。以上が代表的な変換処理の例であるが，そのほかの方法を用いてもよい。
【００６２】
最近傍ダミー特徴量Ｄ*[i*]のインデックスi*をグループＩＤとする。変換特徴量ＶとグループＩＤi*をサーバ120へ送信する。
【００６３】
サーバ120は、変換特徴量Ｖと、テンプレートＤＢ122の、i*をＩＤとするグループに含まれるテンプレートとの１：Ｎ照合を行う（Ｓ５０７）。たとえば指静脈認証など，２つの特徴量の間の類似度は相互相関により計算されるものなどがある。相互相関に基づいて類似度を計算する照合アルゴリズムに対しては、２つの特徴量に特殊な変換を施して秘匿したまま、それらを元に戻すことなく類似度を計算するアルゴリズム（相関不変ランダムフィルタリング）が知られている。詳細については文献１や文献２を参照のこと。この場合，グループi*  内で変換パラメータは共通であるため、１：Ｎ照合は、グループi*  内のテンプレートそれぞれと変換特徴量Ｖとの１：１照合を１回ずつ実行し、最も相関が高いテンプレートのＩＤを結果として出力することで実現できる。
【００６４】
本実施例によれば、認証時には、クライアント１００側でダミー特徴量との類似検索を以って該当グループへの割り当てを実行することで、サーバ１２０側での１：Ｎ照合の対象となるテンプレート数を大幅に絞り込める。これによって、サーバ側の処理負荷を削減し、１：Ｎ照合の処理時間を大幅に短縮できる。
【００６５】
以上のように、本実施例によれば、１：Ｎ認証において、サーバ側処理負荷を削減し、処理を高速化することが可能である。また、クライアント100には特定の個人に属する生体情報の特徴量ではなく、ダミー特徴量が保持されているため、プライバシやセキュリティの問題はない。
【００６６】
上記実施形態は、生体情報に基づいてユーザ認証を行う任意のアプリケーションに対して適用可能である。例えば、社内ネットワークにおける情報アクセス制御、インターネットバンキングシステムやＡＴＭにおける本人確認、会員向けＷｅｂサイトへのログイン、保護エリアへの入場時の個人認証、パソコンのログインなどへの適用が可能である。
【符号の説明】
【００６７】
１００：クライアント、１０１：特徴量抽出部、１０２：類似検索部、１０３：補助データＤＢ部、１０４：特徴量変換部、１０５：変換パラメータＤＢ部、１０６：通信部、１０７：センサ、１１０：補助データＤＢ作成端末、111：クラスタリング部、１１２：特徴量ＤＢ部、１１３：ダミー特徴量作成部、１１４：補助データＤＢ部、補助データ作成部、１１６：通信部、１２０：サーバ、１２１：通信部、１２２：テンプレートＤＢ部、１２３：登録部、１２４：１：Ｎ照合部、６００：ＣＰＵ、６０１：メモリ、６０２：ＨＤＤ、６０３：入力装置、６０４：出力装置、６０５：通信装置。
【図１】
2010286937.tif 000004
【図２】
2010286937.tif 000005
【図３】
2010286937.tif 000006
【図４】
2010286937.tif 000007
【図５】
2010286937.tif 000008
【図６】
2010286937.tif 000009