(57)【要約】【課題】  指紋認証に適用可能な、精度の劣化のないキャンセラブル生体認証を実現する。【解決手段】  キャンセラブル生体認証における指紋情報の変換手段として、指紋特徴点の座標と方向の対称変換と、座標の回転変換と、方向の回転と、特徴点種別の反転を組み合わせた変換を用いる。また対称変換の有無と、座標の回転角度と、方向の回転角度と、特徴点種別の反転の有無を、変換パラメータとして用いる。この変換は指紋照合アルゴリズムの特徴量空間における等長変換であり、従って二つの特徴量を同一の変換パラメータで変換しても特徴量同士の照合結果は変化せず、従って精度劣化のないキャンセラブル指紋認証が実現される。【選択図】図１
2006158851.tif 000002
【特許請求の範囲】
【請求項１】
生体情報の特徴量変換方法であって、
平面上の複数の特徴点の座標を含む特徴量を受け取るステップと、
前記特徴点の座標を、少なくとも、予め決められた直線に関して対称変換するか、予め決められた点を中心に回転変換するステップ
とを有することを特徴とする特徴量変換方法。
【請求項２】
生体情報の特徴量変換方法であって、
平面上の複数の特徴点の座標を含む特徴量を受け取るステップと、
対称変換の有無の指定と座標回転角とを含む変換パラメータを受け取るステップと、
前記変換パラメータの対象変換の有無の指定が有の場合、前記特徴点の座標を予め決められた直線に関して対称変換するステップと、
前記変換パラメータの座標回転角に従って前記特徴点の座標を予め決められた点を中心に回転変換するステップと
を有することを特徴とする特徴量変換方法。
【請求項３】
請求項２において、
前記特徴量は、各特徴点の方向を含み、
前記変換パラメータは、方向回転角を含み、
前記特徴量変換方法は、
前記方向回転角に従って前記特徴点の方向を回転する
ことを特徴とする特徴量変換方法。
【請求項４】
請求項２において、
前記特徴量は、各特徴点の種別を含み、
前記変換パラメータは、種別変換の有無の指定を含み、
前記特徴量変換方法は、
前記変換パラメータにおいて種別変換の有無の指定が有の場合、前記各特徴点の種別を変換する
ことを特徴とする特徴量変換方法。
【請求項５】
請求項２において、
前記特徴量は、各特徴点の番号と種別とを含み、
前記変換パラメータは、前記特徴点の番号ごとの種別変換の有無の指定を含み、
前記特徴量変換方法は、
前記変換パラメータにおいて種別変換の有無の指定が有である番号の特徴点について、種別を変換する
ことを特徴とする特徴量変換方法。
【請求項６】
請求項２において、
前記特徴量は、特徴点の番号の対ごとのリレーション値を含み、
前記変換パラメータは、特徴点の番号の対ごとのリレーション値の変換量を含み、
前記特徴量変換方法は、
前記特徴量のリレーション値を、前記変換パラメータの、対応する特徴点の番号の対のリレーション値の変換量を用いて所定の演算により変換する
ことを特徴とする特徴量変換方法
【請求項７】
請求項２において、
前記特徴量は、各特徴点の番号を含み、
前記変換パラメータは、特徴点の番号ごとの置換番号を含み、
前記特徴量変換方法は、
前記特徴点の番号を、前記変換パラメータの、対応する特徴点の置換番号に変換する
ことを特徴とする特徴量変換方法。
【請求項８】
請求項６において、
前記変換パラメータは、特徴点の番号の対ごとに、置換のための番号の対を含み、
前記特徴量変換方法は、
前記特徴点の番号の対を、前記変換パラメータの、対応する置換のための特徴点の番号の対に変換する
ことを特徴とする特徴量変換方法。
【請求項９】
生体情報を取得する手段と、
前記生体情報から特徴量を抽出する手段と、
請求項１ないし８のいずれか一項に記載の特徴量変換方法に従って前記特徴量を変換する手段と
を有することを特徴とする特徴量変換装置。
【請求項１０】
生体認証システムであって、
請求項９に記載の特徴量変換装置と、照合装置とを有し、
前記特徴量変換装置は、
登録のための生体情報を取得し、取得した生体情報から特徴量を抽出し、前記変換パラメータに従い前記特徴量を変換して登録用変換特徴量を作成する手段と、
作成した前記登録用変換特徴量を前記照合装置へ送信する手段とを有し、
前記照合装置は、
前記登録用変換特徴量を受信する手段と、
受信した登録用変換特徴量を記憶する記憶手段とを有し、
前記特徴量変換装置は、さらに、
認証のための生体情報を取得し、取得した生体情報から特徴量を抽出し、与えられた変換パラメータに従い前記特徴量を変換して照合用変換特徴量を作成する手段と、
作成した前記照合用変換特徴量を前記照合装置へ送信する手段とを有し、
前記照合装置は、さらに、
前記照合用変換特徴量と前記記憶手段に記憶されている登録用変換特徴量とを照合する手段と
を有することを特徴とする生体認証システム。
【請求項１１】
生体認証システムであって、
特徴量変換装置と照合装置とを有し、
前記特徴量変換装置は、
登録のための生体情報を取得する手段と、
取得した生体情報から登録用の特徴量を抽出する手段と、
抽出した登録用の特徴量を第一の登録用特徴量および第二の登録用特徴量に分割する手段と、
与えられた第一の変換パラメータに従い前記第一の登録用特徴量を変換して第一の登録用変換特徴量を作成する第一の登録用特徴量変換手段と、
与えられた第二の変換パラメータに従い前記第二の登録用特徴量を変換して第二の登録用変換特徴量を作成する第二の登録用特徴量変換手段と、
前記第一の登録用変換特徴量および第二の登録用変換特徴量を前記照合装置に送信する手段とを有し、
前記照合装置は、
前記第一の登録用変換特徴量および第二の登録用変換特徴量を受信する手段と、
受信した前記第一の登録用変換特徴量および第二の登録用変換特徴量を記憶する記憶手段とを有し、
前記特徴量変換装置は、
認証のための生体情報を取得する手段と、
取得した生体情報から認証用の特徴量を抽出する手段と、
抽出した認証用の特徴量を第一の照合用特徴量および第二の照合用特徴量に分割する手段と、
前記第一の変換パラメータに従い前記第一の照合用特徴量を変換して第一の照合用変換特徴量を作成する第一の照合用特徴量変換手段と、
作成した前記第一の照合用変換特徴量を前記照合装置に送信する手段とを有し、
前記照合装置は、
前記第一の照合用変換特徴量を受信する手段と、
前記第一の照合用変換特徴量を、前記記憶手段に記憶されている前記第一の登録用変換特徴量と照合する第一の照合手段と、
照合の過程で得られる特徴量補正情報を前記特徴量変換装置に送信する手段とを有し、
前記特徴量変換装置は、
前記特徴量補正情報を受信する手段と、
前記特徴量補正情報に従い前記第二の照合用特徴量を補正する特徴量補正手段と、
補正した前記第二の照合用特徴量を、前記第二の変換パラメータに従い変換して第二の照合用変換特徴量を作成する第二の照合用特徴量変換手段と、
作成した前記第二の照合用変換特徴量を前記照合装置に送信する手段とを有し、
前記照合装置は、
前記第二の照合用変換特徴量を受信する手段と、
前記第二の照合用変換特徴量を、前記記憶手段に記憶されている前記第二の登録用変換特徴量と照合する第二の照合手段とを有する
ことを特徴とする生体認証システム。
【請求項１２】
請求項１１において
前記特徴量は、平面上の複数の特徴点の座標と、各特徴点の番号と、各特徴点の方向と、各特徴点の種別とを含み、
前記第一の登録用特徴量及び前記第一の照合用特徴量は、前記特徴点座標と、前記特徴点番号と、前記特徴点方向とを含み、
前記第二の登録用特徴量及び前記第二の照合用特徴量は、前記特徴点番号と、前記特徴点種別とを含み、
前記第一の変換パラメータは対称変換の有無の指定と、座標回転角と、方向回転角とを含み、
前記第二の変換パラメータは、特徴点番号ごとの、種別変換の有無の指定と、置換番号とを含み、
前記第一の登録用特徴量変換手段は、請求項３に記載の特徴量変換方法を用いて前記第一の登録用特徴量を変換し、
前記第二の登録用特徴量変換手段は、
前記第二の登録用特徴量が含む各特徴点に対し、前記第二の変換パラメータにおける種別変換の有無の指定が有である番号の特徴点の種別を変換する機能と、
前記特徴点の番号を、前記第二の変換パラメータの、対応する特徴点の置換番号に変換する機能とを有し、
前記第一の照合用特徴量変換手段は、前記特徴量変換方法を用いて前記第一の照合用特徴量を変換し、
前記第一の照合手段は、前記第一の登録用変換特徴量と前記第一の照合用変換特徴量を比較して、前記第一の照合用特徴量に含まれる各特徴点に対し、前記第一の登録用変換特徴量から対応する特徴点を探索し、特徴点番号の対応関係を、前記特徴量補正情報として出力する機能を有し、
前記特徴量補正手段は、前記特徴量補正情報に従い前記第二の照合用特徴量に含まれる各特徴点の特徴点番号を振り変える機能を有し、
前記第二の照合用変換特徴量変換手段は、
前記第二の照合用変換特徴量が含む各特徴点に対し、前記第二の変換パラメータにおける種別変換の有無の指定が有である番号の特徴点の種別を変換する機能と、
前記特徴点の番号を、前記第二の変換パラメータの、対応する特徴点の置換番号に変換する機能とを有し、
前記第二の照合手段は、前記第二の照合用変換特徴量と、前記第二の登録用変換特徴量の、同じ特徴点番号の特徴点同士を比較し、特徴点種別が一致する特徴点の数を用いて類似度を計算する機能を有する、
ことを特徴とする生体認証システム。
【請求項１３】
請求項１１において、
前記特徴量は、平面上の複数の特徴点の座標と、各特徴点の番号と、各特徴点の方向と、特徴点の番号の対ごとのリレーション値とを含み、
前記第一の登録用特徴量及び第一の照合用特徴量は、前記特徴点座標と、前記特徴点番号と、前記特徴点方向とを含み、
前記第二の登録用特徴量及び第二の照合用特徴量は、前記特徴点番号と、前記リレーション値とを含み、
前記第一の変換パラメータは、対称変換の有無と、座標回転角と、方向回転角とを含み、
前記第二の変換パラメータは、特徴点の番号の対ごとのリレーション値の変換量と、特徴点番号の対の置換のための置換番号対とを含み、
前記第一の登録用特徴量変換手段は、請求項３に記載の特徴量変換方法を用いて前記第一の登録用特徴量を変換し、
前記第二の登録用特徴量変換手段は、前記特徴量のリレーション値を、前記第二の変換パラメータの、対応する特徴点番号の対のリレーション値の変換量を用いて所定の演算により変換し、
前記第一の照合手段は、前記第一の登録用変換特徴量と前記第一の照合用変換特徴量を比較して、前記第一の照合用変換特徴量に含まれる各特徴点に対し、前記第一の登録用変換特徴量から対応する特徴点を探索し、特徴点番号の対応関係を、前記特徴量補正情報として出力する機能を有し、
前記特徴量補正手段は、前記特徴量補正情報に従い前記第二の照合用特徴量に含まれる各特徴点の特徴点番号を振り変える機能を有し、
前記第二の照合用特徴量変換手段は、前記特徴量のリレーション値を、前記第二の変換パラメータの、対応する特徴点番号の対のリレーション値の変換量を用いて所定の演算により変換し、
前記第二の照合手段は、前記第二の照合用変換特徴量と、前記第二の登録用変換特徴量の、同じ特徴点番号の対に対応するリレーション値同士を比較して類似度を計算する機能を有する
ことを特徴とする生体認証システム。
【請求項１４】
鍵生成復元システムであって、
変換パラメータ生成機能と、鍵生成機能と、生体情報取得機能と、特徴量抽出機能と、特徴量変換機能とを持つ鍵生成装置と、
記憶装置と、
生体情報取得機能と、特徴量抽出機能と、変換パラメータ推定機能と、鍵生成機能を持つ鍵復元装置とを有し、
前記鍵生成装置は、
変換パラメータを生成する手段と、
前記変換パラメータから鍵データを生成して出力する手段と、
生体情報を取得する手段と、
前記生体情報から登録用の特徴量を抽出する手段と、
前記変換パラメータに従い請求項１ないし６のいずれか一項に記載の特徴量変換方法を用いて前記登録用の特徴量を変換して登録用変換特徴量を生成する手段と、
前記記憶装置へ前記登録用変換特徴量を書き込む手段とを有し、
前記鍵復元装置は、
前記記憶装置から前記登録用変換特徴量を読み込む手段と、
生体情報を取得する手段と、
前記生体情報から復元用の特徴量を抽出する手段と、
前記復元用特徴量を前記特徴量変換方法により変換した場合に得られる変換特徴量が、前記登録用の変換特徴量と一致することとなる変換パラメータを出力する変換パラメータ出力手段と、
出力した前記変換パラメータから鍵データを生成して出力する鍵出力手段と
ことを特徴とする鍵生成復元システム。
【請求項１５】
請求項１４において、
前記鍵生成装置は、さらに、
前記変換パラメータの一部に対して誤り訂正符号を生成し、前記記憶装置へ前記誤り訂正符号を書き込む手段を有し、
前記鍵出力手段は、
前記変換パラメータ出力手段が出力した変換パラメータを前記誤り訂正符号により訂正し、訂正した前記変換パラメータから鍵データを生成して出力する
ことを特徴とする鍵生成復元システム。
【請求項１６】
生体認証システムの生体認証方法であって、
前記生体認証システムは、
請求項９に記載の特徴量変換装置と、照合装置とを有し、
前記特徴量変換装置は、
登録のための生体情報を取得し、取得した生体情報から特徴量を抽出し、前記変換パラメータに従い前記特徴量を変換して登録用変換特徴量を作成し、
作成した前記登録用変換特徴量を前記照合装置へ送信し、
前記照合装置は、
前記登録用変換特徴量を受信し、
受信した登録用変換特徴量を記憶し、
前記特徴量変換装置は、さらに、
認証のための生体情報を取得し、取得した生体情報から特徴量を抽出し、与えられた変換パラメータに従い前記特徴量を変換して照合用変換特徴量を作成し、
作成した前記照合用変換特徴量を前記照合装置へ送信し、
前記照合装置は、さらに、
前記照合用変換特徴量と前記記憶手段に記憶されている登録用変換特徴量とを照合しする
ことを特徴とする生体認証方法。
【請求項１７】
生体認証システムの生体認証方法であって、
前記生体認証システムは、特徴量変換装置と照合装置とを有し、
前記特徴量変換装置は、
登録のための生体情報を取得するステップと、
取得した生体情報から登録用の特徴量を抽出するステップと、
抽出した登録用の特徴量を第一の登録用特徴量および第二の登録用特徴量に分割するステップと、
与えられた第一の変換パラメータに従い前記第一の登録用特徴量を変換して第一の登録用変換特徴量を作成する第一の登録用特徴量変換ステップと、
与えられた第二の変換パラメータに従い前記第二の登録用特徴量を変換して第二の登録用変換特徴量を作成する第二の登録用特徴量変換ステップと、
前記第一の登録用変換特徴量および第二の登録用変換特徴量を前記照合装置に送信するステップとを行い、
前記照合装置は、
前記第一の登録用変換特徴量および第二の登録用変換特徴量を受信するステップと、
受信した前記第一の登録用変換特徴量および第二の登録用変換特徴量を記憶する記憶ステップとを行い、
前記特徴量変換装置は、
認証のための生体情報を取得するステップと、
取得した生体情報から認証用の特徴量を抽出するステップと、
抽出した認証用の特徴量を第一の照合用特徴量および第二の照合用特徴量に分割するステップと、
前記第一の変換パラメータに従い前記第一の照合用特徴量を変換して第一の照合用変換特徴量を作成する第一の照合用特徴量変換ステップと、
作成した前記第一の照合用変換特徴量を前記照合装置に送信するステップとを行い、
前記照合装置は、
前記第一の照合用変換特徴量を受信するステップと、
前記第一の照合用変換特徴量を、前記記憶ステップに記憶されている前記第一の登録用変換特徴量と照合する第一の照合ステップと、
照合の過程で得られる特徴量補正情報を前記特徴量変換装置に送信するステップとを行い、
前記特徴量変換装置は、
前記特徴量補正情報を受信するステップと、
前記特徴量補正情報に従い前記第二の照合用特徴量を補正する特徴量補正ステップと、
補正した前記第二の照合用特徴量を、前記第二の変換パラメータに従い変換して第二の照合用変換特徴量を作成する第二の照合用特徴量変換ステップと、
作成した前記第二の照合用変換特徴量を前記照合装置に送信するステップとを行い、
前記照合装置は、
前記第二の照合用変換特徴量を受信するステップと、
前記第二の照合用変換特徴量を、前記記憶手段に記憶されている前記第二の登録用変換特徴量と照合する第二の照合ステップとを行う
ことを特徴とする生体認証方法。
【請求項１８】
鍵生成復元システムの鍵生成復元方法であって、
前記鍵生成復元システムは、
変換パラメータ生成機能と、鍵生成機能と、生体情報取得機能と、特徴量抽出機能と、特徴量変換機能とを持つ鍵生成装置と、
記憶装置と、
生体情報取得機能と、特徴量抽出機能と、変換パラメータ推定機能と、鍵生成機能を持つ鍵復元装置とを有し、
前記鍵生成装置は、
変換パラメータを生成するステップと、
前記変換パラメータから鍵データを生成して出力するステップと、
生体情報を取得するステップと、
前記生体情報から登録用の特徴量を抽出するステップと、
前記変換パラメータに従い請求項１ないし６のいずれか一項に記載の特徴量変換方法を用いて前記登録用の特徴量を変換して登録用変換特徴量を生成するステップと、
前記記憶装置へ前記登録用変換特徴量を書き込むステップとを行い、
前記鍵復元装置は、
前記記憶装置から前記登録用変換特徴量を読み込むステップと、
生体情報を取得するステップと、
前記生体情報から復元用の特徴量を抽出するステップと、
前記復元用特徴量を前記特徴量変換方法により変換した場合に得られる変換特徴量が、前記登録用の変換特徴量と一致することとなる変換パラメータを出力する変換パラメータ出力ステップと、
出力した前記変換パラメータから鍵データを生成して出力する鍵出力ステップとを行う
ことを特徴とする鍵生成復元方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、人が持つ生体的特徴（生体情報）を用いて個人を認証する技術に関する。
【背景技術】
【０００２】
生体情報を用いたユーザ認証システムは、登録時にユーザから生体情報を取得し、特徴量と呼ばれる情報を抽出して登録する。この登録情報をテンプレートという。認証時は、再びユーザから生体情報を取得して特徴量を抽出し、テンプレートと照合して本人か否かを確認する。
【０００３】
非特許文献１に記載のキャンセラブル生体認証方法では、登録時に特徴量を一定の関数とクライアントが持つ秘密のパラメータで変換し、元の情報を秘匿した状態でテンプレートとしてサーバに保管する。そして、認証時にクライアントが新たに抽出した生体情報の特徴量を、同じ関数とパラメータで変換してサーバへ送信し、サーバは受信した特徴量とテンプレートを変換された状態のまま照合する。
【０００４】
また、非特許文献１には、特徴量の変換方法として、指紋画像をブロック分割して入れ替える方法および、特徴点の座標と方向を高次多項式関数を用いて変換する方法が提案されている。
【０００５】
【非特許文献１】N. K. Ratha, et al., “Enhancing security and privacy in biometric-based authentication systems”, IBM System Journal, Vol.40, No.3, 2001
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１の前者の方法では、指紋の隆線の連続性などの条件から容易に元画像を復元できる。また、後者の方法では、特徴点の座標や方向に対して非線形変換を行うため、変換前の特徴点同士の距離が変換後において保存されない。このため本来一致するべき特徴点同士が変換後において不一致と判断される、あるいは本来一致しない特徴点同士が変換後において一致と判断される可能性があり、特に認証時に指を置く位置がずれたり、歪みが生じたりした場合に、照合精度が大きく劣化することがある。
【０００７】
本発明の目的は、指紋のように平面上の複数の特徴点の座標、方向、種別などで特徴量が表現される生体情報に適用可能であり、精度の劣化を抑制したキャンセラブル生体認証を実現することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決すべく本発明は、生体情報の特徴量の変換において、変換によって二つの特徴点（例えば、指紋の隆線の端点および分岐点）間の距離が変化しないように等長変換を行う。
【０００９】
例えば、本発明の生体情報の特徴量変換方法は、平面上の複数の特徴点の座標を含む特徴量を受け取るステップと、前記特徴点の座標を、少なくとも、予め決められた直線に関して対称変換するか、予め決められた点を中心に回転変換するステップとを有する。
【００１０】
また、本発明の生体情報の特徴量変換方法は、平面上の複数の特徴点の座標を含む特徴量を受け取るステップと、対称変換の有無の指定と座標回転角とを含む変換パラメータを受け取るステップと、前記変換パラメータの対象変換の有無の指定が有の場合、前記特徴点の座標を予め決められた直線に関して対称変換するステップと、前記変換パラメータの座標回転角に従って前記特徴点の座標を予め決められた点を中心に回転変換するステップとを有する。
【００１１】
より具体的には、本発明の生体認証システムは、前記特徴量変換方法により変換を行う特徴量変換装置と、照合装置とを有する。そして、前記特徴量変換装置は、登録のための生体情報を取得し、取得した生体情報から特徴量を抽出し、前記変換パラメータに従い前記特徴量を変換して登録用変換特徴量を作成する手段と、作成した前記登録用変換特徴量を前記照合装置へ送信する手段とを有する。前記照合装置は、前記登録用変換特徴量を受信する手段と、受信した登録用変換特徴量を記憶する記憶手段とを有する。前記特徴量変換装置は、さらに、認証のための生体情報を取得し、取得した生体情報から特徴量を抽出し、与えられた変換パラメータに従い前記特徴量を変換して照合用変換特徴量を作成する手段と、作成した前記照合用変換特徴量を前記照合装置へ送信する手段とを有する。前記照合装置は、さらに、前記照合用変換特徴量と前記記憶手段に記憶されている登録用特徴量とを照合する手段とを有する。
【発明を実施するための最良の形態】
【００１２】
＜第一の実施形態＞
以下、本発明の第一の実施形態について、指紋の特徴量情報をサーバに対して秘匿したまま、サーバ内で指紋照合を行う、キャンセラブル指紋認証システムを例にして説明する。
【００１３】
図１に本実施形態のシステムの構成を示す。本実施形態のキャンセラブル指紋認証システムは、登録・認証時の指紋取得と特徴量抽出、変換を行うクライアント端末100と、指紋の画像化を行う指紋センサ110と、ユーザが携帯することになる携帯型記録媒体120と、携帯型記録媒体120の読み書きを行う媒体読書装置130と、テンプレートの保管と照合を行う認証サーバ140とから構成される。また、クライアント端末100とサーバ140はインターネットやイントラネットなどのネットワーク88で接続されているものとする。
【００１４】
指紋センサ110は、ユーザから提示された指紋を撮像し、指紋の画像データを生成する。
【００１５】
携帯型記憶媒体120はユーザが携帯、管理するものとし、ICカード、USBメモリ、携帯端末、フロッピーディスクなどが利用可能である。
【００１６】
クライアント端末100は、ユーザ自身か、信頼できる第三者によって管理されているものとする。
【００１７】
クライアント端末100は、指紋センサ110との通信を行う指紋センサI/F 101と、指紋画像から特徴量を抽出する特徴量抽出部102と、指紋登録時にランダムに変換パラメータを生成する変換パラメータ生成部103と、変換パラメータを用いて特徴量を変換して変換特徴量を作成する特徴量変換部104と、媒体読書装置130との通信を行う媒体読書I/F 105と、インターネットなどを介した通信を行う通信I/F 106と、記憶装置107とから構成される。
【００１８】
認証サーバ140は、インターネットなどを介した通信を行う通信I/F 141と、変換特徴量をテンプレートとして登録する登録部142と、テンプレートを記憶する記憶装置143と、認証時に新たに受信した変換特徴量をテンプレートと照合して類似度を計算する照合部144とから構成される。
【００１９】
なお、クライアント端末100及び認証サーバ140は、図１７に示すように、ＣＰＵ２、メモリ３、ＨＤＤ４、入力装置（キーボード、マウス等）５、出力装置（ディスプレイ、プリンタ等）６、通信装置７を有するパーソナルコンピュータやワークステーションなどのコンピュータシステムにより達成できる。クライアント端末100の各機能部101〜106、及び認証サーバ140の各機能部141,142,144は、ＣＰＵ２がメモリ３にロードされたプログラムを実行することにより達成される。クライアント端末100の記憶装置107及び認証サーバ140の記憶装置143としては、メモリ３又はＨＤＤ４が使用される。
【００２０】
また、例えば自宅からインターネットバンキングを行う場合、クライアント端末100はユーザが管理する自宅のPCであり、認証サーバ140は銀行が管理するサーバマシンとすることで、本実施例を適応することが可能である。
【００２１】
つぎに、指紋登録時と認証時の処理について説明する。
【００２２】
図２は、指紋登録時の処理のフロー図である。
【００２３】
このフローは、クライアント端末100がユーザから指紋登録要求を受け付けたときに開始される。
【００２４】
まず、クライアント端末100の通信I/F 106は、ネットワーク88を介して、認証サーバ140にＩＤを要求する。このＩＤは、登録される指紋ごとに割り当てられる識別コードである。これを受けて、認証サーバ140の登録部142は、予め定めたアルゴリズムにより、ＩＤを生成し、通信I/F 141を介して、クライアント端末100に送信する。クライアント端末装置100の通信I/F 106は、受信したＩＤを記憶装置107に記憶する（Ｓ２００）。
【００２５】
つぎに、クライアント端末100の指紋センサI/F 101は、指紋センサ110を介してユーザの指紋画像を取得する。そして、特徴量抽出部102に送る（Ｓ２０１）。
【００２６】
つぎに、特徴量抽出部102は、後述する処理により、指紋画像から特徴量Bを抽出する。そして、特徴量変換部104に送る（Ｓ２０２）。
【００２７】
つぎに、変換パラメータ生成部103は、変換パラメータSをランダムに生成し、特徴量変換部104に送るとともに、記憶装置107に記憶する（Ｓ２０３）。
【００２８】
媒体読書I/F 105は、記憶装置107に記憶されたＩＤ及び変換パラメータSを読み込み、媒体読書装置130を介して、携帯型記憶媒体120に書き込む。（Ｓ２０４）。
【００２９】
つぎに、特徴量変換部104は、後述する処理により、変換パラメータSおよび特徴量Bから、変換特徴量F(S,B)を生成する。そして、通信I/F 106に送る（Ｓ２０５）。
【００３０】
通信I/F 106は、変換特徴量F(S,B)を、ネットワーク88を介して、認証サーバ140へ送信する（Ｓ２０６）。
【００３１】
また、通信I/F 106は、ＩＤ及び変換パラメータSを、記憶装置107から消去する。これにより、変換パラメータSは、携帯型記憶媒体120内のみで保管され、認証サーバ140に対して秘匿される
認証サーバ140の通信I/F 141は、クライアント端末100から送信された変換特徴量F(S,B)を受信し、登録部142に送る。登録部142は、変換特徴量F(S,B)を、テンプレートとして記憶装置143に登録する。このとき、テンプレートF(S,B)を、Ｓ２００で生成したＩＤと対応させて登録する（Ｓ２０７）。
【００３２】
図３に、指紋認証時の処理のフロー図を示す。このフローは、クライアント端末100がユーザから指紋認証要求を受け付けたときに開始される。
【００３３】
クライアント端末100の指紋センサI/F 101は、指紋センサ110を介してユーザの指紋画像を取得する（Ｓ２１１）。
【００３４】
つぎに、特徴量抽出部102は、後述する処理により、指紋画像から特徴量B’を抽出する。そして、特徴量変換部104に送る（Ｓ２１２）。
【００３５】
つぎに、媒体読書I/F 105は、媒体読書装置130を介して、携帯型記憶媒体120に記憶されたＩＤ及び変換パラメータSを読み込み、記憶装置107に記憶する（Ｓ２１３）。
【００３６】
つぎに、特徴量変換部104は、記憶装置107に記憶されている変換パラメータＳを読み込む。そして、後述する処理により、変換パラメータSおよび特徴量B’から、変換特徴量F(S,B’)を生成する。そして、通信I/F 106に送る（Ｓ２１４）。
【００３７】
通信I/F 106は、記憶装置107に記憶されているＩＤと、特徴量変換部104から受信した変換特徴量F(S,B’)を、ネットワーク88を介して、認証サーバ104に送る。その後、記憶装置107に記憶されているＩＤ及び変換パラメータSを消去する（Ｓ２１５）
認証サーバ140の認証部144は、記憶装置143に記憶されたテンプレートの中から、クライアント端末100から受信したＩＤと同一のＩＤのテンプレートを抽出する。そして、抽出したテンプレートF(S,B)と、受信した変換特徴量F(S,B’)との照合を試みる。なお、認証部144は、一般的な指紋認証アルゴリズムにより照合を行う。すなわち、テンプレートと照合用特徴量F(S,B’)を、予め決められた範囲内での平行移動および回転を許容して重ね合わせ、対応する特徴点の対を探索する処理（アライメント）を行い、対応する特徴点同士の距離、方向の差の絶対値、種別の同異から、類似度を計算する。
【００３８】
認証部144は、照合に成功した場合、本人であると判定し、照合に失敗した場合、本人でないと判定する（Ｓ２１６）。そして、その結果を、通信I/F 141を介して、クライアント端末100に送信する。
【００３９】
つぎに、指紋の特徴量のデータ構造について、図４を用いて説明する。
【００４０】
指紋の特徴量は、図４（ａ）に示すように、平面状の複数の特徴点の集合として抽出される。各特徴点は、平面座標、方向および種別（端点あるいは分岐点）の属性を持つ。抽出された特徴量は、図４（ｂ）の表に示すように、各特徴点に対して番号i 311、座標(x[i],y[i])312、方向θ[i]（-180°以上180°未満）313、種別t[i]（t[i]=0（端点）またはt[i]=1（分岐点））314を組みとしたデータ構造{(i,x[i],y[i],θ[i],t[i]) | i=1,…,n}で表される。なお、特徴点の番号311は、特徴量抽出部102により、特徴点抽出後にアルゴリズムにより便宜的に振られるもので、各特徴点が元々持っている情報ではない。従って登録時と認証時では、一般に同じ特徴点に対して別の番号が振られる。
【００４１】
なお、ここで示した特徴量のデータ構造は、一般的な指紋認証アルゴリズムにおいて使用されているものである（例えば、A.Jain,“Biometrics,” Kluwer Academic Publishers （1999）参照）。
【００４２】
つぎに、特徴量変換部104が行う特徴量変換処理（Ｓ２０５、Ｓ２１４）について説明する。図５は、特徴量変換処理（Ｓ２０５、Ｓ２１４）のフロー図である。
【００４３】
変換パラメータSは、（P,α,β,M）の４つの値を組としたデータ構造で表される。Pは、対称変換の有無を表し、1または0の値をとる。Ｍは、種別反転の有無を表し、M=1または0の値をとる。αは、座標回転角度を表し、-180°以上180°未満の値をとる。βは、方向回転角度を表し、-180°以上180°未満の値をとる。
【００４４】
特徴量変換部104は、特徴量Ｂおよび変換パラメータSの入力を受けて以下の手順により変換を行い、F(S,B)を出力する。なお、ここでは、特徴量Ｂの変換について説明するが、特徴量Ｂ’からF(S,B’)への変換も同様にして行われる。
【００４５】
特徴量変換部104は、Pが1のときx軸について全特徴点の座標と方向を対称変換する（Ｓ４０１）。具体的には、各特徴点の座標 (x, y)と方向θを、座標 (x, y・(1-2・P))と方向θ・(1-2・P)に変換する。
【００４６】
つぎに、特徴量変換部104は、全特徴点の座標をα回転する（Ｓ４０２）。具体的には、各特徴点の座標(x,y)を、（x・cos(α)-ｙ・sin(α), x・sin(α)+y・cos(α)）に変換する。以下、この変換後の座標をRα（x,y）と記述する。
【００４７】
つぎに、特徴量変換部104は、全特徴点の方向をβ回転する（Ｓ４０３）。具体的には、各特徴点の方向θを、θ+βに変換する。なお変換後の方向は-180°以上180°未満の値として表す。
【００４８】
つぎに、特徴量変換部104は、Ｍが1のとき全特徴点の種別を反転する（Ｓ４０４）。具体的には、各特徴点の種別tを、t^Tに変換する。ここで、記号a^bは、aとbの排他的論理和を表すものとする。
【００４９】
以上の手順により変換された特徴量をF(S,B)と表す。まとめると、B={(i,x[i],y[i],θ[i],t[i]) | i=1,…,n}、S=(P,α,β,M)のとき、F(S,B)={(i,Rα(x[i],y[i]・(1-2・P)), θ・(1-2・P)+β, t[i]^M) | i=1,…,n}となる。
【００５０】
図６に、変換パラメータS=(0,-30°,-80°,1)の場合における、特徴量変換の様子を示す。各特徴点は、-30°の座標回転、-80°の方向回転、および種別反転によって変換されている。
【００５１】
以上、特徴量変換処理について説明した。このような特徴量変換により、第一の実施形態が達成される。
【００５２】
なお、本実施形態では、変換パラメータSは、ユーザが所持する記録媒体120に記録されるが、クライアント端末100の記憶装置107に記憶させておいてもよい。また、変換パラメータＳは、ユーザが入力するパスワードから動的に生成するようにしてもよい。
【００５３】
本実施形態によれば、認証サーバ140は、変換された特徴量F(S,B)をテンプレートとして保管し、また認証時には、変換された特徴量F(S,B’)を受信する。一方、変換パラメータSは、ユーザが携帯する携帯型記録媒体120（若しくはユーザの所有するクライアント端末100の記憶装置107）が保持し、認証サーバ140に対して秘匿される。したがって、認証サーバ140は、元の特徴量BおよびB’を知ることができない。このため、認証サーバ140に対してユーザの匿名性が高まり、プライバシが保護される。また万が一認証サーバ140からテンプレートF(S,B)が漏洩した場合にも、元の特徴量Bが不明なため偽造指紋を作成することができない。
【００５４】
また、本実施形態における特徴量変換方法によれば、登録時と認証時で同じ変換パラメータSを用いた場合、最終的な照合結果に影響を与えない。以下に、具体的に説明する。
【００５５】
上述したように、指紋認証アルゴリズムは、テンプレートと照合用特徴量を、予め決められた範囲内での平行移動および回転を許容して重ね合わせ、対応する特徴点の対を探索する処理（アライメント）を行い、対応する特徴点同士の距離、方向の差の絶対値、種別の同異から、類似度を計算する。
【００５６】
特徴量Bおよび特徴量B’の照合において、移動距離Dの平行移動および角度τの回転によりアライメントが行われるならば、変換後の特徴量F(S,B)およびF(S,B’)に対しても移動距離Dの平行移動および角度τ（又は-τ）の回転により同様のアライメントが行われる。
【００５７】
またアライメントの結果、Bのi番の特徴点とB’のj番の特徴点が対応し、特徴点間の距離がd、方向の差の絶対値がΔθであったならば、変換後の特徴量F(S,B)のi番目の特徴点とF(S,B’)のj番目の特徴点も対応し、特徴点間の距離はd、方向の差の絶対値はΔθとなる。また特徴点の種別の同異も、変換によって変化しない。つまり特徴点同士の距離、方向の差の絶対値、種別の同異は、特徴量変換によって変化せず、従って類似度も変化しない。
【００５８】
このように、本実施形態の特徴量変換方法によれば、照合結果に影響を与えないため、精度を劣化させずにキャンセラブル指紋認証を実現することができる。
【００５９】
更に、テンプレートが漏洩した場合や有効期間が切れた場合に、以下の方法により指紋の再取得を行うことなくテンプレートを更新することができる。ただし、認証サーバ140も特徴量変換部を持つものとする。クライアント端末100の変換パラメータ生成部103は、新たな変換パラメータS’=(P’,α’,β’,M’)をランダムに生成し、古い変換パラメータS=(P,α,β,M)を、S+S’に置き換える。ここでS+S’=(P^P’,α＋α’,β＋β’,M^M’)と定義する。次にクライアント端末100の通信I/F106は、変換パラメータS’を認証サーバ140へ送信する。認証サーバ140の登録部142は、古いテンプレートF(S,B)をS’によって変換したF(S’,F(S,B))を、新たなテンプレートとして登録する。
【００６０】
ここで、F(S’,F(S,B))=F(S+S’,B)である。したがって、テンプレートと変換パラメータの更新が正しく行われたことになる。
【００６１】
この方法によれば、テンプレート更新処理において、クライアント端末100は秘密情報である変換パラメータSを外部へ送信しない。また、認証サーバ140は保護すべき情報であるテンプレートF(S,B)を外部へ送信しない。したがって、安全性の高いテンプレート更新を実現することができる。
【００６２】
＜第二の実施形態＞
次に本発明の第二の実施形態として、サーバがアライメント情報をクライアントへフィードバックすることにより、変換パラメータの自由度を増やし、匿名性と安全性を高めたキャンセラブル指紋認証システムを例に説明する。
【００６３】
図７は、本実施形態のキャンセラブル指紋認証システムの構成を示す。
【００６４】
本実施形態のキャンセラブル指紋認証システムは、登録時の指紋取得と特徴量抽出および変換を行う登録装置600と、テンプレートの保管と照合を行う認証サーバ610と、認証時の指紋取得と特徴量抽出および変換を行う認証装置620と、変換パラメータを記憶する携帯型記憶媒体630から構成される。
【００６５】
認証サーバ610と、登録装置600と、認証装置620は、インターネットやイントラネットなどのネットワーク88で接続されているものとする。また、登録装置600と認証装置620は、信頼できる第三者によって管理されているものとする。
【００６６】
携帯型記憶媒体630はユーザが携帯、管理するものとし、ICカード、USBメモリ、携帯端末、フロッピーディスクなどが利用可能である。
【００６７】
本実施形態における認証サーバ610と登録装置600は、プロセッサや指紋センサ、ICカードリーダライタなどが一体となった専用端末である。一般的なPC（図１７参照）に指紋センサやICカードリーダライタなどを外付けしてもよい。また認証装置620はPDAや携帯電話のようにユーザが所持する携帯端末であるとし、携帯型記録媒体630と一体であるとしてもよい。
【００６８】
登録装置600は、指紋センサ601と、指紋画像から特徴量を抽出する特徴量抽出部602と、指紋登録時にランダムに変換パラメータを生成する変換パラメータ生成部603と、変換パラメータを用いて特徴量を変換しサーバへ送信する第一の特徴量変換部604および第二の特徴量変換部605と、変換パラメータを携帯型記録媒体630へ書き込む媒体書込部606と、通信I/F 607と、記憶装置608とから構成される。
【００６９】
認証装置620は、指紋センサ621と、特徴量抽出部622と、携帯型記録媒体630から変換パラメータを読み込む媒体読込部623と、第一の特徴量変換部624と、認証サーバ610からアライメント結果を受信して特徴量の特徴点番号を入れ替える特徴点番号入替部625と、第二の特徴量変換部626と、通信I/F 628と、記憶装置627とから構成される。認証装置620の特徴量変換部624および626は、それぞれ登録装置600の特徴量変換部604および605と同等の機能である。
【００７０】
認証サーバ610は、登録時に登録装置600から変換特徴量を受信してテンプレートとして登録する登録部611と、テンプレートを記憶する記憶装置612と、認証時に認証装置620から第一の変換特徴量を受信し、テンプレートと比較してアライメントを行いアライメント情報を認証装置620へ送信するアライメント部613と、認証装置620から第二の変換特徴量を受信しテンプレートと比較し類似度を計算し照合する照合部614と、通信I/F 615とから構成される。
【００７１】
なお、登録装置600、認証サーバ610、認証装置620の各機能部は、ＣＰＵがメモリにロードされたプログラムを実行することにより達成される。
【００７２】
つぎに、指紋登録時および認証時の処理について説明する。
【００７３】
図８は、指紋登録時の処理のフロー図である。
【００７４】
このフローは、クライアント端末100がユーザから指紋登録要求を受け付けたときに開始される。
【００７５】
まず、登録装置600の通信I/F 607は、ネットワーク88を介して、認証サーバ610にＩＤを要求する。このＩＤは、登録される指紋ごとに割り当てられる識別コードである。これを受けて、認証サーバ610の登録部611は、予め定めたアルゴリズムにより、ＩＤを生成し、通信I/F 615を介して、登録装置600に送信する。登録装置600の通信I/F 607は、受信したＩＤを記憶装置608に記憶する（Ｓ７００）。
【００７６】
つぎに、登録装置600の指紋センサ601は、ユーザの指紋画像を取得する。そして、特徴量抽出部602に送る（Ｓ７０１）
つぎに、特徴量抽出部602は、指紋画像から特徴量Bを抽出する（Ｓ７０２）。ここで特徴量Bは、第一の特徴量B1と第二の特徴量B2から構成されるものとする。これらの特徴量のデータ構造に関しては後述する。
【００７７】
つぎに、変換パラメータ生成部603は、変換パラメータSをランダムに生成し、第一の特徴量変換部604に送るとともに、記憶装置608に記憶する。なお、変換パラメータSは、第一の変換パラメータS1と第二の変換パラメータS2から構成されるものとする。変換パラメータのデータ構造に関しては後述する（Ｓ７０３）。
【００７８】
つぎに、第一の特徴量変換部604は、後述する処理により、第一の変換パラメータS1および第一の特徴量B1から、第一の登録用変換特徴量F1(S1,B1)を生成する。そして、生成した第一の登録用変換特徴量F1(S1,B1)を、通信I/F607にお送る（Ｓ７０４）。
【００７９】
つぎに、第二の特徴量変換部605は、後述する処理により、第二の変換パラメータS2および第二の特徴量B2から、第二の登録用変換特徴量F2(S2,B2)を生成する。そして、生成した第二の登録用変換特徴量F1(S1,B1)を、通信I/F607にお送る（Ｓ７０５）。
【００８０】
つぎに、通信I/F607は、記憶装置608に記憶されているＩＤを読み込み、このＩＤと、第一の登録用変換特徴量F1(S1,B1)と、第二の登録用変換特徴量F1(S1,B1)とを、認証サーバ610へ送信する（Ｓ７０６）。
【００８１】
以後、第一の登録用変換特徴量F1(S1,B1)と第二の登録用変換特徴量F2(S2,B2)を合わせたデータを、登録用変換特徴量F(S,B)と表す。
【００８２】
認証サーバ610の登録部611は、登録用変換特徴量F(S,B)を受信し、これをテンプレートとして記憶装置612に登録する。このとき、受信したＩＤと対応させて登録する（Ｓ７０８）。
【００８３】
一方、登録装置600の媒体読書部606は、記憶装置608に記憶されたＩＤ及び変換パラメータSを読み込み、携帯型記憶媒体630に書き込む。また、ＩＤおよび変換パラメータSを、記憶装置107から消去する。これにより、変換パラメータSは、携帯型記憶媒体630内のみで保管され、認証サーバ610に対して秘匿される（Ｓ７０７）。
【００８４】
次に、認証時の処理のフローについて説明する。このフローは、認証装置620がユーザから認証要求を受け付けたときに開始される。
【００８５】
認証装置620の媒体読込部623は、携帯型記録媒体630に記憶されているＩＤ及び変換パラメータSを読み込み、記憶装置627に記憶する（Ｓ７１１）。
【００８６】
つぎに、認証装置620の指紋センサ621は、ユーザの指紋から指紋画像を取得する。そして、指紋画像を特徴量抽出部622に送る（Ｓ７１２）。
【００８７】
つぎに、特徴量抽出部622は、後述する処理により、指紋画像から特徴量B’を抽出する。そして、第一の特徴量変換部624に送る。ここで特徴量B’は、第一の特徴量B’1と第二の特徴量B’2から構成されるものとする（Ｓ７１３）。
【００８８】
つぎに、第一の特徴量変換部624は、記憶装置627に記憶されている第一の変換パラメータS1を読み込む。そして、後述する処理により、第一の変換パラメータS1および第一の特徴量B’1から、第一の照合用変換特徴量F1(S1,B’1)を生成する。そして、通信I/F 628に送る（Ｓ７１４）。
【００８９】
通信I/F 628は、記憶装置627に記憶されているＩＤと、第一の特徴量変換部624から受信した第一の照合用変換特徴量F1(S1,B’1)を、認証サーバ610に送る（Ｓ７１５）。
【００９０】
認証サーバ610のアライメント部613は、記憶装置612に記憶されているテンプレートの中から、認証装置620から受信したＩＤと同一のＩＤのテンプレートを抽出する。そして、抽出したテンプレートF(S,B)に含まれる第一の登録用変換特徴量F1(S1,B1)と、受信した第一の照合用変換特徴量F1(S1,B’1)を比較して、後述する処理によりアライメントを行う（Ｓ７１６）。さらに、その結果、得られたアライメント情報を、認証装置620へ送信する（Ｓ７１７）。なお、アライメント情報のデータ構造は後述する。
【００９１】
認証装置620の特徴点番号入替部625は、後述する処理により、受信したアライメント情報に基づいて、第二の特徴量B’2の特徴点番号を入れ替える。そして、特徴点番号を入替えた第二の特徴量B’2を第二の特徴量変換部626に送る（Ｓ７１８）。
【００９２】
つぎに、第二の特徴量変換部626は、記憶装置627に記憶されている変換パラメータＳに含まれる第二の変換パラメータS2を取得する。そして、後述する処理により、第二の変換パラメータS2および特徴点番号を入れ替えた第二の特徴量B’2から、第二の照合用変換特徴量F2(S2,B’2)を生成する。そして、通信I/F 628に送る（Ｓ７１９）。
【００９３】
通信I/F 628は、記憶装置627に記憶されているＩＤと、第二の特徴量変換部626から受信した第二の照合用変換特徴量F2(S2,B’2)を、認証サーバ610に送る（Ｓ７２０）。
【００９４】
認証サーバ610の照合部614は、記憶装置612の中から、受信したＩＤと同一のＩＤのテンプレートF(S,B)を抽出し、さらに、抽出したF(S,B)に含まれる第二の登録用変換特徴量F2(S2,B2)を抽出する。そして、抽出した第二の登録用変換特徴量F2(S2,B2)と、受信した第二の照合用変換特徴量F2(S2,B’2)との照合を試みる。照合部614は、上記第一の実施形態と同様に、一般的な指紋認証アルゴリズムにより照合して類似度を求める。
【００９５】
すなわち、照合部614は、アライメントによって得られた特徴点対の各々に対し、F2(S2,B’2)とF2(S2,B2)から種別情報を調べ、種別が一致する特徴点対のみを選択する。次に、選択された特徴点対に対し、特徴点対を構成する照合用特徴
点と他の複数の照合用特徴点とのリレーション情報（F2(S2,B’2)内に含まれる）と、特徴点対を構成する登録用特徴点と他の複数の登録用特徴点とのリレーション情報（F2(S2,B2)内に含まれる）を比較し、リレーションがほぼ一致する（例えばリレーションの差の平均がしきい値以下となる）ような特徴点対のみを選択する。このように二段階に選択された結果残った特徴点対の個数を、類似度とする。
【００９６】
照合部614は、照合に成功した場合（類似度が所定値以上の場合）、本人であると判定し、照合に失敗した場合、本人でないと判定する（Ｓ７２１）。そして、その結果を、認証装置620にに送信する。
【００９７】
なお、媒体読込部623は、Ｓ７２０の処理の後、記憶装置627に記憶されているＩＤおよび変換パラメータＳを消去する。
【００９８】
図１０に、本実施形態における指紋の特徴量Bのデータ構造を示す。特徴量Bは、特徴点情報330およびリレーション情報340から構成される。特徴点情報330は、各特徴点iの番号331、特徴点iの座標(x[i],y[i]) 332、方向θ[i] 333、種別t[i] 334を含む。またリレーション情報340は、二つの特徴点i,jの番号341、二つの特徴点i,j間の指紋の隆線の本数（リレーション）r[i,j]（i<j） 342を含む。例えば、図１０（ｂ）において特徴点i,jの間の隆線は2本であり、従ってこの場合r[i,j]=2となる。リレーション 342は必ずしも全ての特徴点の対に対して計算されるものではなく、通常は近接する特徴点対に対して計算される。計算されないリレーションは「−」と示す。
【００９９】
なお、ここで示したリレーションを含む指紋特徴量のデータ構造は、一般的な指紋認証アルゴリズムにおいて使用されているものである
（例えば、浅井絋, 星野幸夫, 木地和夫：“マニューシャネットワーク特徴による自動指紋照合−特徴抽出過程”,電子情報通信学会論文誌,Vol.J72-D-II,No.5,pp.724-732,1989、
浅井絋, 星野幸夫, 木地和夫：“マニューシャネットワーク特徴による自動指紋照合− 照合過程”,電子情報通信学会論文誌,Vol.J72-D-II,No.5,pp.733-740,1989.等参照）
本実施形態の指紋認証システムは、上述のように、前記特徴量Bを第一の特徴量B1および第二の特徴量B2に分割して扱う。第一の特徴量B1は、各特徴点の特徴点番号i、座標(x[i],y[i])、方向θ[i]から構成されるデータ{(i,x[i],y[i],θ[i]) | i=1,…,n}である。第二の特徴量B2は、各特徴点の特徴点番号iと種別t[i]、およびリレーション情報から構成されるデータ{{(i,t[i]) | i=1,…,n}, {(i,j, r[i,j]) | 1<=i<j<=n}}である。
【０１００】
図１１に、本実施形態におけるアライメント情報350のデータ構造を示す。前述の通り、アライメント処理は、認証時に抽出され変換された特徴量（照合用変換特徴量）およびテンプレートに含まれる特徴点同士を、予め決められた範囲内での平行移動および回転を許容して重ね合わせ、対応する特徴点の組を探索する処理である。図１２は、アライメントの結果例を図示したものであり、対応する照合用特徴点と登録用特徴点の対を、点線の楕円で示している。
【０１０１】
なお、指の置き方や皮膚の状態、ノイズなどによって、同一の指紋であっても、登録時に存在した特徴点が認証時に抽出できないことがある。また、登録時には存在しなかった特徴点が認証時に抽出されるといったことがある。このため図１２に示すように対応する照合用特徴点がない登録用特徴点や、対応する登録用特徴点がない照合用特徴点が存在する。
【０１０２】
アライメント情報350は、図１１に示すように、照合用特徴点番号i 351に対応する登録用特徴点番号をA[i] 352とし、{(i,A[i])|i=1,2,…n}で表される。対応する登録用特徴点が存在しない場合は、A[i]を「−」と表す。
【０１０３】
認証装置620の特徴点入替部625は、上述したように、Ｓ７１８において、アライメント情報を受信し、認証時に抽出した第二の特徴量B’2の特徴点番号を入れ替える。具体的には、B’2{{(i,t[i]) | i=1,…,n}, {(i,j, r[i,j]) | 1<=i<j<=n}}を、{{(A[i],t[i]) | i=1,…,n}, {(A[i],A[j], r[i,j]) | 1<=i<j<=n}}とする。
【０１０４】
図１３は、本実施形態における第一の特徴量変換部604（F1）と、第二の特徴量変換部605F2）の処理の流れ、および変換パラメータSのデータ構造を示す。なお、認証時における第一の特徴量変換部624（F1）と、第二の特徴量変換部626（F2）の処理も、図１３のフローと同様に行われる。
【０１０５】
変換パラメータSは、第一の変換パラメータS1および第二の変換パラメータS2から構成される。第一の変換パラメータS1は、（P,α,β）の３つの値を組としたデータ構造を有する。各記号の意味と値域は第一の実施形態と同様であり、Pは対称変換の有無、αは座標回転角度、βは方向回転角度を表す。
【０１０６】
第二の変換パラメータS2は、種別マスク{TM[i]|i=1,…,n}と、種別置換表{TS[i]|i=1,…,n}と、リレーションマスク{RM[i,j]|1<=i<j<=n}と、リレーション置換表{(RS1[i,j],RS2[i,j])|1<=i<j<=n}とから構成される。ここで種別マスクの各TM[i]は0または1をとる。また、種別置換表は、n!通りある{1,2,…,n}の順列のいずれかを表す。リレーションマスクの各RM[i,j]は、リレーションr[i,j]を変換するための値を表し、本実施形態では0以上9以下の乱数とする。リレーション置換表は、(n(n-1)/2)!通りある{(i,j)|1<=i<j<=n}の順列のいずれかを表す。
【０１０７】
第一の特徴量変換部604は、第一の特徴量B1および第一の変換パラメータS1の入力を受けて、第一の変換特徴量F1(S1,B1)を出力する。処理手順（Ｓ４０１，Ｓ４０２，Ｓ４０３）は、前述の第一の実施形態と同じため説明を省略する。
【０１０８】
第二の特徴量変換部605は、第二の特徴量B2および第二の変換パラメータS2の入力を受けて、以下の手順により変換を行い、第二の変換特徴量F2(S2,B2)を出力する。
【０１０９】
第二の特徴量変換部605は、各特徴点種別t[i]に対し、TM[i]が1のとき反転する（Ｓ１００１）。つまり各特徴点種別t[i]をt[i]^TM[i]に変換する。
【０１１０】
第二の特徴量変換部605は、TS[i]番の特徴点種別t[TS[i]]を、i番の特徴点種別t[i]で置き換える（Ｓ１００２）。
【０１１１】
第二の特徴量変換部605は、各リレーションr[i,j]を、r[i,j]+RM[i,j] mod 10と変換し、第二の変換特徴量を出力する（Ｓ１００３）。ここでa mod bは、aをbで割った余りを表す。
【０１１２】
第二の特徴量変換部605は、特徴点対（RS1[i,j], RS2[i,j]）に対応するリレーションr[RS1[i,j], RS2[i,j]]を、特徴点対(i,j)に対応するリレーションr[i,j]で置き換える（Ｓ１００４）。
【０１１３】
以上の手順により変換された第二の変換特徴量をF2(S2,B2)と表す。まとめると、B2={{(i,t[i]) | i=1,…,n}, {(i,j,r[i,j]) | 1<=i<j<=n}}のとき、F2(S2,B2)={{(TS[i],t[i]^TM[i]) | i=1,…,n}, {(RS1[i,j],RS2[i,j],r[i,j]^RM[i,j]) | 1<=i<j<=n}}となる。
【０１１４】
以上、第一の特徴量変換および第二の特徴量変換について説明した。このような特徴量変換によって、第二の実施形態では、指紋登録および指紋認証が行われる。
【０１１５】
第二の実施形態によれが、特徴量変換は、第一の実施形態と比較して変換パラメータの自由度が高く、また指紋認証精度を高める効果のあるリレーション情報に対しても変換を行う。また、リレーション情報は、認証サーバに対して秘匿される。このため匿名性と安全性がより高い認証方法となる。
【０１１６】
また、指紋認証は、一般に、指の位置や回転のずれ、歪み、皮膚の状態変化、ノイズなどによって、取得される指紋画像が毎回異なるため、認証時に特徴点の位置や方向、種別が変化し、また特徴点自体が消失する、あるいはテンプレートにない特徴点が抽出されることがある。このため登録時と認証時で、同一の特徴点に対し同じ番号を振ることは困難である。第一の実施形態における特徴点変換方法は、変換後の特徴量が、特徴点番号の振り方に依存せず決定するよう構成することで、変換後の特徴量同士を一般的な指紋照合アルゴリズムで照合可能とした。
【０１１７】
これに対して、第二の実施形態における第二の特徴量変換は、各特徴点やリレーションに対して独立に変換を行うため、特徴点番号の振り方が、照合用特徴量とテンプレートの間で一致していなくてはならない。これを実現するため、認証装置620は、まず特徴点番号の振り方に依存しない第一の特徴量変換を用いて第一の特徴量（特徴点の座標および方向）を変換し、認証サーバ610へ送信する。
【０１１８】
そして、認証サーバ610は、アライメントを行う。これにより、照合用特徴量の特徴点とテンプレートの特徴点の対応をとる。そして、対応情報（アライメント情報）を認証装置610へ送信する。
【０１１９】
認証装置620は、認証サーバ610から受信したアライメント情報により、照合用特徴量の特徴点番号をテンプレートの特徴点番号と一致させ、その後に第二の特徴量変換を行う。
【０１２０】
このように、本実施形態では、アライメント情報をフィードバックするよう指紋認証のプロトコルを変えることで、第一の実施形態と比較して匿名性と安全性のより高い指紋認証を実現する。
【０１２１】
また本実施形態のキャンセラブル指紋認証システムは、第一の実施形態のキャンセラブル指紋認証システムと同様の方法により、指紋の再取得を行わずにテンプレート更新を行うことが可能である。
【０１２２】
＜第三の実施形態＞
次に、本発明の第三の実施形態として、認証や暗号に用いるユーザの鍵データを生成、登録し、認証時にユーザの指紋情報を用いて鍵データを復元する、鍵生成復元システムを説明する。
【０１２３】
図１４に、本実施形態の鍵生成復元システムの構成を示す。鍵生成復元システムは、鍵生成装置1100と、鍵復元装置1110と、記憶装置1120から構成される。
【０１２４】
記憶装置1120は、ユーザが所有する携帯型の記録媒体や、鍵復元装置1110内の記憶装置であってもよい。
【０１２５】
鍵生成装置1100は、変換パラメータ生成部1101と、鍵生成部1102と、指紋センサ1103と、特徴量抽出部1104と、第一の特徴量変換部1105と、第二の特徴量変換部1106と、誤り訂正符号生成部1107と、データ書込み部1108とから構成される。ここで第一の特徴量変換部1105は、前記第二の実施形態における第一の特徴量変換部604と同等の処理を行う機能であるとする。また第二の特徴量変換部1106は、前記第二の実施形態における第二の特徴量変換部605とほぼ同等の処理を行う機能部であるが、前記第二の実施形態におけるステップ1002およびステップ1004の処理は行わないものとする。
【０１２６】
鍵復元装置1110は、データ読込部1111と、指紋センサ1112と、特徴量抽出部1113と、第一の鍵復元部1114と、第二の鍵復元部1115と、誤り訂正部1116と、鍵出力部1117とから構成される。
【０１２７】
なお、鍵生成装置1100及び鍵復元装置1110は、図１７に示すように、ＣＰＵ２、メモリ３、ＨＤＤ４、入力装置（キーボード、マウス等）５、出力装置（ディスプレイ、プリンタ等）６、通信装置７を有するパーソナルコンピュータやワークステーションなどのコンピュータシステムにより達成できる。鍵生成装置1100の各機能部1001〜1108、及び鍵復元装置1110の各機能部1111〜1117はＣＰＵ２がメモリ３にロードされたプログラムを実行することにより達成される。
【０１２８】
図１５は、鍵生成時の鍵生成装置1100の処理のフロー図でさる。実線は処理の流れおよびデータの流れを表す。点線は、記憶装置に書き込まれる各データがどの処理によって生成されたものかを示す。
【０１２９】
変換パラメータ生成部1101は、変換パラメータSをランダムに生成する（Ｓ１２０１）。変換パラメータＳは、第一の変換パラメータS1および第二の変換パラメータS2から構成されるものとし、第一の変換パラメータS1のデータ構造は前記第二の実施形態と同等であるものとする。ただし座標回転角度αは、指の回転ずれを吸収するよう離散化した値とする。具体的には、鍵生成時と鍵復元時の指の回転ずれを-Δτ/2以上Δτ/2未満の範囲で許容するならば、αは360°/Δτ個の値i・Δτ（i=0,1,…,360°/Δτ）のいずれかをとるものとする。例えば指の回転ずれを-10°以上10°未満の範囲で許容するならば、αは0°, 20°, 40°,…,340°の、18通りの値を取る。方向回転角度βについても、歪みなどによって生じる特徴点方向のずれを吸収するよう離散化した値とする。
【０１３０】
また、第二の変換パラメータS2のデータ構造は、前記第二の実施形態とほぼ同等であるが、種別マスクTM[i](i=1,2,…,n)およびリレーションマスクRM[i,j](1<=i<j<=n)のみを含むものとする。
【０１３１】
つぎの、指紋センサ1103は、ユーザの指紋画像を取得する。そして、指紋画像を特徴量抽出部1104に送る（Ｓ１２０２）。
【０１３２】
特徴量抽出部1104は、前記指紋画像から指紋の特徴量Bを抽出する（Ｓ１２０３）。特徴量Bは、第一の特徴量B1および第二の特徴量B2から構成されるものとし、それぞれのデータ構造は第二の実施形態と同等であるものとする。
【０１３３】
第一の特徴量変換部1105は、第一の変換パラメータS1に従って、第一の特徴量B1を変換し、第一の変換特徴量F1(S1,B1)を生成する（Ｓ１２０４）。
【０１３４】
第二の特徴量変換部1106は、第二の変換パラメータS2に従って、第二の特徴量B2を変換し、第二の変換特徴量F2(S2,B2)を生成する（Ｓ１２０５）。
【０１３５】
誤り訂正符号生成部1107は、第二の変換パラメータS2に含まれる種別マスクをnビットデータTM=(TM[1],…,TM[n])として扱い、誤り訂正符号ECC(TM)を生成する（Ｓ１２０６）。特徴点の種別は、湿度や皮膚の状態、ノイズなどによる指紋画像の画質の変化によって、端点が分岐点として認識されたり、分岐点が端点として認識されることがある。また鍵生成時の入力指紋から抽出された特徴点が、鍵復元時の入力指紋から全て抽出されるとは限らない。従って鍵復元時にはTMの一部のビットが反転したり、不明であったりする。このような不完全な情報から、完全な情報を復元するために、誤り訂正符号を用いる。下記のリレーションマスクについても同様の理由で誤り訂正符号を用いる。符号化方式としては、BCH符号やＲＳ符号などが利用可能である。
【０１３６】
誤り訂正符号生成部1107は、第二の変換パラメータに含まれるリレーションマスクをn(n-1)/2ビットデータRM=(RM[1,2],RM[1,3],…,RM[n-1,n])として扱い、誤り訂正符号ECC(RM)を生成する（Ｓ１２０７）。
【０１３７】
データ書込部1108は、第一の変換特徴量F1(S1,B1)と、第二の変換特徴量F2(S2,B2)と、種別マスクの誤り訂正符号ECC(TM)と、リレーションマスクの誤り訂正符号ECC(RM)を、記憶装置1120へ書き込む（Ｓ１２０８）。以下、F1(S1,B1)、F2(S2,B2)、ECC(TM)、ECC(RM)をまとめて補助情報と呼ぶ。
【０１３８】
鍵出力部1102は、変換パラメータSから鍵を生成して出力する。その後、変換パラメータSおよび鍵を、鍵生成装置1100のメモリや記憶媒体から消去する（Ｓ１２０９）。出力する鍵は、例えばSのハッシュ値や、あるいはSそのものを用いてもよい。出力された鍵は、例えばネットワークを介した認証を行う場合、サーバのデータベースへ登録してもよい。あるいは出力された鍵を公開鍵暗号における秘密鍵とし、対応する公開鍵を生成することも可能である。
【０１３９】
図１６は、鍵復元時の鍵復元装置1110の処理のフロー図である。実線は処理の流れおよびデータの流れを表す。点線は、記憶装置から読み込まれる各データがどの処理に使われるかを示す。
【０１４０】
データ読込部1111は、記憶装置1120から補助情報を読み込む（Ｓ１３００）。
【０１４１】
指紋センサ1112は、ユーザの指紋画像を取得する。そして、特徴量抽出部1113に送る（Ｓ１３０１）。
【０１４２】
特徴量抽出部1113は、指紋画像から指紋の特徴量B’を抽出する（Ｓ１３０２）。特徴量B’は、第一の特徴量B’1および第二の特徴量B’2から構成されるものとし、それぞれのデータ構造は第二の実施形態と同等であるものとする。
【０１４３】
第一の鍵復元部1114は、仮の座標回転角αと、仮の対象変換Pを定める。そして、定めた仮の座標回転角αと、仮の対象変換Pに従って、第一の特徴量B’1を変換し、第一の変換特徴量を作成する（Ｓ１３０３）。ここで特徴量変換は、第一の実施形態におけるステップ401およびステップ402と同等の処理を行い、方向の回転は行わないものとする。
【０１４４】
第一の鍵復元部1114は、補助情報に含まれるF1(S1,B1)と、第一の変換特徴量のアライメントを試みる（Ｓ１３０４）。アライメントは、予め決められた範囲内での平行移動および回転を許容して特徴点全体を重ね合わせ、一定数以上の特徴点対において座標と方向が一致した場合に、アライメント処理が成功したとみなす。ただし、ここで方向の一致は、各特徴点対における方向の差が、ある値βに集中している場合（例えば方向の差の分散が一定値以下の場合）に、βをS1における仮の方向回転角とみなし、方向が一致したものとする。このように本発明によれば、αとPを変化させながら探索することで、βを含めた変換パラメータS1を復元することができる。つまりS1の全空間を探索することなく、高速に復元処理を行うことができる。
【０１４５】
アライメントに失敗した場合（Ｓ１３０４で「失敗」）、第一の鍵復元部1114は、Ｓ１３０３に戻り、仮の方向回転角αと仮の対称変換Pの組合せを変えて、特徴量変換およびアライメント（Ｓ１３０５）を行う。仮の方向回転角αと仮の対称変換Pは、例えば、現在Ｐが１の場合、αはそのままに、Ｐを１にする。現在Ｐが０の場合、αに１を足し、Ｐを１にする。
【０１４６】
仮の方向回転角αと仮の対称変換Pの組合せとして取り得る全ての値についてＳ１３０３の処理を試みたにも関らず、アライメントに失敗した場合（Ｓ１３０５でＹｅｓ）、第一の鍵復元部1114は、鍵復元失敗として処理を終了する。
【０１４７】
一般に登録時と異なる指紋が入力された場合、鍵復元に失敗する。
【０１４８】
一方、アライメントが成功したならば（Ｓ１３０４で「成功」）、第一の鍵復元部1114は、（α,β,P）を復元された第一の変換パラメータS’1として鍵出力部1117へ渡し、またアライメント情報を鍵復元部1115へ渡す。
【０１４９】
第二の鍵復元部1115は、アライメント情報に従って、第二の特徴量B’2の特徴点番号を入れ替える（Ｓ１３０６）。
【０１５０】
第二の鍵復元部1115は、番号を入れ替えた第二の特徴量B’2と、補助情報に含まれるF2(S2,B2)から、種別マスクを復元する（Ｓ１３０７）。具体的には、B’2の特徴点i（iは入れ替えた後の番号）の種別t’[i]と、F2(S2,B2)の特徴点iの種別t[i]から、TM’[i]=t’[i]^t[i]を計算し、TM’=(TM’[1],…,TM’[n])とする。ただしアライメントによりF2(S2,B2)の特徴点iに対応するB’2の特徴点が見つからなかった場合、TM’[i]は不明とする。
【０１５１】
第二の鍵復元部1115は、番号を入れ替えた第二の特徴量B’2と、補助情報に含まれるF2(S2,B2)から、リレーションマスクを復元する（Ｓ１３０８）。具体的には、B’2のリレーションr’[i,j]（i,jは入れ替えた後の番号）と、F2(S2,B2)のリレーションr[i,j]から、RM’[i,j]=r[i,j]-r’[i,j] mod 10を計算し、RM’=(RM’[1,2],RM’[1,3],…,RM’[n-1,n])とする。
【０１５２】
誤り訂正部1116は、補助情報に含まれるECC(TM)を用いて、復元した種別マスクTM’の誤りを訂正する（Ｓ１３０９）。
【０１５３】
誤り訂正部1116は、補助情報に含まれるECC(RM)を用いて、復元したリレーションマスクRM’の誤りを訂正する（Ｓ１３１０）。誤りを訂正したTM’とRM’をまとめ、復元された第二の変換パラメータS’2として鍵出力部1117へ送る。
【０１５４】
このように本実施形態によれば、S2の復元に必要な計算量は、特徴点数nに対してnビットの排他的論理和演算と、nの2乗回程度の引き算および mod 演算と、誤り訂正処理の計算量のみであり、高速に計算することができる。
【０１５５】
鍵出力部1117は、復元されたパラメータS’から鍵を生成し、出力する（Ｓ１３１１）。
【０１５６】
以上、第三の実施形態について説明した。
【０１５７】
本実施形態によれば、鍵生成復元システムは、鍵生成時に、鍵の生成元となる変換パラメータおよび生体情報から補助情報を作成して保存し、鍵復元時に補助情報と生体情報から変換パラメータを求めて鍵を動的に復元する。鍵の復元は、鍵空間を全て探索する必要はなく、比較的高速に実行が可能である。また生体情報から補助情報を作成する方法は、一般的な暗号化とは異なり、特徴量空間内での等長変換を用いるため、データフォーマットの条件や正当な特徴量であるための制約条件を破ることはない。このため補助情報が漏洩した場合にも、補助情報のみから鍵や特徴量を特定することは困難であり、従来技術と比較して安全性の高い動的鍵生成を実現可能である。なお、誤り訂正符号の適切な長さは、特徴点種別やリレーションのエラーをどの程度許容するかによって異なる。誤り訂正符号を長くすると、鍵の自由度は小さくなるが、安定して鍵を抽出することが可能となる。
【０１５８】
以上、本発明のいくつかの実施形態について説明したが、本発明は、これらの実施形態に限定されることなく、発明の要旨の範囲内で様々な変形が可能である。
【０１５９】
また、本発明は、生体情報をサーバに登録して照合を行う、任意に生体認証システムに対して適用可能である。例えば社内ネットワークにおける情報アクセス制御、インターネットバンキングシステムやＡＴＭにおける本人確認、会員向けWebサイトへのログイン、保護エリアへの入場時の個人認証などへの適用が可能である。
【図面の簡単な説明】
【０１６０】
【図１】本発明の第一の実施形態（キャンセラブル指紋認証システム）の概略構成図である。
【図２】同実施形態における指紋の登録処理を示す流れ図である。
【図３】同実施形態における指紋の認証処理を示す流れ図である。
【図４】同実施形態において用いる指紋特徴量およびそのデータ構造を示す図である。
【図５】同実施形態における特徴量変換処理の流れおよび変換パラメータのデータ構造を示す図である。
【図６】同実施形態における特徴量変換を説明するための図である。
【図７】本発明の第二の実施形態（キャンセラブル指紋認証システム）を示す概略構成図である。
【図８】同実施形態における指紋の登録処理を示す流れ図である。
【図９】同実施形態における指紋の認証処理を示す流れ図である。
【図１０】同実施形態において用いる指紋特徴量およびそのデータ構造を示す図である。
【図１１】同実施形態において用いるアライメント情報を説明するための図である。
【図１２】同実施形態において用いるアライメント情報のデータ構造を示す図である。
【図１３】同実施形態における特徴量変換処理の流れおよび変換パラメータのデータ構造を示す図である。
【図１４】本発明の第三の実施形態（鍵生成復元システム）を示す概略構成図である。
【図１５】同実施形態における鍵生成処理を示す流れ図である。
【図１６】同実施形態における鍵復元処理を示す流れ図である。
【図１７】ハードウエアの構成図である。
【符号の説明】
【０１６１】
100  クライアント端末
101  指紋センサI/F
102  特徴量抽出部
103  変換パラメータ生成部
104  特徴量変換部
105  媒体読書I/F
106  通信I/F
107  記憶装置
110  指紋センサ
120  携帯型記録媒体
130  媒体読書装置
140  認証サーバ
141  通信I/F
142  登録部
143  記憶装置
144  照合部
600  登録装置
601  指紋センサ
602  特徴量抽出部
603  変換パラメータ生成部
604  第一の特徴量変換部
605  第二の特徴量変換部
606  媒体書込部
607  記憶装置
608  通信I/F
610  認証サーバ
611  登録サーバ
612  記憶装置
613  アライメント部
614  照合部
615  通信I/F
620  認証装置
621  指紋センサ
622  特徴量抽出部
623  媒体読込部
624  第一の特徴量変換部
625  特徴点番号入替部
626  第二の特徴量変換部
627  記憶装置
628  通信I/F
630  携帯型記録媒体
1100  鍵生成装置
1101  変換パラメータ生成部
1102  鍵出力部
1103  指紋センサ
1104  特徴量抽出部
1105  第一の特徴量変換部
1106  第二の特徴量変換部
1107  誤り訂正符号生成部
1108  データ書込部
1110  鍵復元装置
1111  データ読込部
1112  指紋センサ
1113  特徴量抽出部
1114  第一の鍵復元部
1115  第二の鍵復元部
1116  誤り訂正部
1117  鍵出力部
1120  記憶装置
2  ＣＰＵ、3  メモリ、4  ＨＤＤ、5  入力装置、6  出力装置、7  通信装置
【図１】
2006158851.tif 000003
【図２】
2006158851.tif 000004
【図３】
2006158851.tif 000005
【図４】
2006158851.tif 000006
【図５】
2006158851.tif 000007
【図６】
2006158851.tif 000008
【図７】
2006158851.tif 000009
【図８】
2006158851.tif 000010
【図９】
2006158851.tif 000011
【図１０】
2006158851.tif 000012
【図１１】
2006158851.tif 000013
【図１２】
2006158851.tif 000014
【図１３】
2006158851.tif 000015
【図１４】
2006158851.tif 000016
【図１５】
2006158851.tif 000017
【図１６】
2006158851.tif 000018
【図１７】
2006158851.tif 000019