(57)【要約】  証明装置１０１が、復号装置１０３にて秘密鍵と対応付けられている公開鍵と、乱数を用いて登録用の特徴ベクトルを暗号化し、登録用の暗号化特徴ベクトルを認証装置１０２に登録し、認証時には、証明装置が認証用の特徴ベクトルを前記公開鍵と乱数を用いて暗号化し、認証装置が、２つの暗号化特徴ベクトルが暗号化された状態のままで、復号装置において前記秘密鍵を用いた復号処理により２つの特徴ベクトル間の類似度を導出可能な暗号化類似度情報を生成し、復号装置１０３が暗号化類似度情報を復号して平文の類似度を導出し、認証装置１０２では、類似度がしきい値以上であれば本人と判定し、平文の特徴ベクトルを用いることなく類似度を導出でき、平文の窃取の可能性の低い安全な本人認証を実現する。
2011052056.tif 000002
【特許請求の範囲】
【請求項１】
二重準同型暗号アルゴリズムに基づいて復号装置において生成され、前記復号装置から配布された公開鍵を記憶する公開鍵記憶部と、
前記復号装置から配布された前記公開鍵を保有する暗号装置が保有する前記公開鍵を用いて暗号化した第１データを暗号化第１データとして記憶する暗号化データ記憶部と、
前記暗号化第１データが前記暗号化データ記憶部に記憶された後に前記暗号装置が保有する前記公開鍵を用いて暗号化した第２データを暗号化第２データとして入力する暗号化データ入力部と、
前記公開鍵の少なくとも一部を用いて、乱数を生成する乱数生成部と、
前記暗号化第１データと前記暗号化第２データに対して前記公開鍵記憶部に記憶されている前記公開鍵と前記乱数生成部により生成された乱数を用いた演算を行って、前記暗号化第１データと前記暗号化第２データがそれぞれ暗号化された状態のままで、前記公開鍵に対応付けられて生成された秘密鍵を用いた復号処理により前記第１データと前記第２データとの間の類似度を導出可能な暗号化された情報を暗号化類似度情報として生成する暗号化類似度生成部とを有することを特徴とするデータ処理装置。
【請求項２】
前記公開鍵記憶部は、
前記復号装置により前記二重準同型暗号アルゴリズムに基づいて秘密鍵と対応付けられて生成された公開鍵を記憶し、
前記データ処理装置は、更に、
前記暗号化類似度生成部により生成された暗号化類似度情報を前記復号装置に出力する暗号化類似度出力部と、
前記復号装置において前記暗号化類似度情報に対して前記秘密鍵を用いた復号処理が行われて導出された前記第１データと前記第２データとの間の類似度を入力する類似度入力部と、
前記類似度入力部により入力された前記類似度を解析して、前記第２データの発生源が正当であるか否かを判定する判定部とを有することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第２データを入力し、
前記暗号化類似度生成部は、
部分データごとに、前記暗号化第１データと前記暗号化第２データに対して前記公開鍵記憶部に記憶されている前記公開鍵と前記乱数生成部により生成された乱数を用いた演算を行って、前記第１データと前記第２データとの間の類似度として、前記第１データのＴ個の部分データと前記第２データのＴ個の部分データにおいて値が一致する部分データの数を導出可能な情報を生成することを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第２データを入力し、
前記暗号化類似度生成部は、
部分データごとに、前記暗号化第１データと前記暗号化第２データに対して前記公開鍵記憶部に記憶されている前記公開鍵と前記乱数生成部により生成された乱数を用いた演算を行って、前記第１データと前記第２データとの間の類似度として、前記第１データのＴ個の部分データと前記第２データのＴ個の部分データにおけるハミング距離を導出可能な情報を生成することを特徴とする請求項１に記載のデータ処理装置。
【請求項５】
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データが前記暗号装置により暗号化されて得られたＴ個の暗号化された部分データで構成される暗号化第２データを入力し、
前記暗号化類似度生成部は、
部分データごとに、前記暗号化第１データと前記暗号化第２データに対して前記公開鍵記憶部に記憶されている前記公開鍵と前記乱数生成部により生成された乱数を用いた演算を行って、前記第１データと前記第２データとの間の類似度として、前記第１データのＴ個の部分データと前記第２データのＴ個の部分データにおけるユークリッド二乗距離を導出可能な情報を生成することを特徴とする請求項１に記載のデータ処理装置。
【請求項６】
前記公開鍵記憶部は、
前記二重準同型暗号アルゴリズムに基づいて生成された公開鍵として、岡本−高島暗号アルゴリズムに基づいて生成された公開鍵を記憶し、
前記暗号化データ記憶部は、
前記岡本−高島暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記岡本−高島暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第２データを入力することを特徴とする請求項１に記載のデータ処理装置。
【請求項７】
前記公開鍵記憶部は、
正則行列である秘密鍵に対応付けられて生成されたランダム基底ｗ１、ｗ２、ｗ３、ｗ＾１、ｗ＾２、ｗ＾３と所定の値ｑを公開鍵として記憶し、
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データｂｉ（添字ｉは１からＴ）に前記ランダム基底ｗ１、ｗ２、ｗ３を保有する前記暗号装置により前記ランダム基底ｗ１、ｗ２、ｗ３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃｉ（添字ｉは１からＴ）で構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データｂ’ｉ（添字ｉは１からＴ）に前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３を保有する前記暗号装置により前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ＾ｉ（添字ｉは１からＴ）で構成される暗号化第２データを入力し、
前記乱数生成部は、
前記値ｑに基づいて複数の乱数値ｓ１，ｉ、ｓ２，ｉ、ｓ３，ｉ、ｓ＾１，ｉ、ｓ＾２，ｉ、ｓ＾３，ｉ（添字ｉは１からＴ）を生成し、前記値ｑに基づいて複数の乱数値ｕ２、ｕ３，、ｕ＾２、ｕ＾３を生成し、
前記暗号化類似度生成部は、
ｄｉ＝ｃｉ＋（ｓ１，ｉ×ｗ１）＋（ｓ２，ｉ×ｗ２）＋（ｓ３，ｉ×ｗ３）を添字ｉについて１からＴまでを計算し、
ｄ＾ｉ＝ｃ＾ｉ＋（ｓ＾１，ｉ×ｗ＾１）＋（ｓ＾２，ｉ×ｗ＾２）＋（ｓ＾３，ｉ×ｗ＾３）を添字ｉについて１からＴまでを計算し、
Ｅ＝｛（ｓ＾１，ｉ×ｃｉ＋ｓ１，ｉ×ｓ＾１，ｉ×ｗ１）の添字ｉについての１からＴまでの総和｝＋（ｕ２×ｗ２）＋（ｕ３×ｗ３）を計算し、
Ｅ＾＝｛（ｓ１，ｉ×ｃ＾ｉ）の添字ｉについての１からＴまでの総和｝＋（ｕ＾２×ｗ＾２）＋（ｕ＾３×ｗ＾３）を計算し、
計算した値ｄｉ、ｄ＾ｉ、Ｅ及びＥ＾を含む暗号化類似度情報を生成することを特徴とする請求項６に記載のデータ処理装置。
【請求項８】
前記暗号化データ記憶部は、
Ｔ個の部分データｂｉが前記暗号装置で生成された乱数値ｒ２，ｉとｒ３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ１、ｗ２、ｗ３が用いられてｃｉ＝（ｂｉ×ｗ１）＋（ｒ２，ｉ×ｗ２）＋（ｒ３，ｉ×ｗ３）により暗号化されたＴ個の部分データｃｉで構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
Ｔ個の部分データｂ’ｉが前記暗号装置で生成された乱数値ｒ’２，ｉとｒ’３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３が用いられてｃｉ＝（ｂ’ｉ×ｗ＾１）＋（ｒ’２，ｉ×ｗ＾２）＋（ｒ’３，ｉ×ｗ＾３）により暗号化されたＴ個の部分データｃ＾ｉで構成される暗号化第２データを入力することを特徴とする請求項７に記載のデータ処理装置。
【請求項９】
前記データ処理装置は、更に、
前記暗号化類似度生成部により生成された暗号化類似度情報を前記復号装置に出力する暗号化類似度出力部と、
前記復号装置において前記暗号化類似度情報に対して前記秘密鍵の逆行列と双対ペアリングベクトル空間におけるディストーション写像とが用いられる復号処理が行われて導出された前記第１データと前記第２データとの間の類似度を入力する類似度入力部と、
前記類似度入力部により入力された前記類似度を解析して、前記第２データの発生源が正当であるか否かを判定する判定部とを有することを特徴とする請求項７に記載のデータ処理装置。
【請求項１０】
前記公開鍵記憶部は、
正則行列である秘密鍵に対応付けて生成されたランダム基底ｗ１、ｗ２、ｗ３、ｗ＾１、ｗ＾２、ｗ＾３と所定の値ｑを公開鍵として記憶し、
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データｂｉ（添字ｉは１からＴ）に前記ランダム基底ｗ１、ｗ２、ｗ３を保有する前記暗号装置により前記ランダム基底ｗ１、ｗ２、ｗ３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃｉ（添字ｉは１からＴ）と、前記第１データを構成するＴ個の部分データｂｉに前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３を保有する前記暗号装置により前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ＾ｉ（添字ｉは１からＴ）で構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データｂ’ｉ（添字ｉは１からＴ）に前記暗号装置により前記ランダム基底ｗ１、ｗ２、ｗ３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ’ｉ（添字ｉは１からＴ）と、前記第２データを構成するＴ個の部分データｂ’ｉに前記暗号装置により前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３を用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ’＾ｉ（添字ｉは１からＴ）で構成される暗号化第２データを入力し、
前記乱数生成部は、
前記値ｑに基づいて複数の乱数値ｓ１，ｉ、ｓ２，ｉ、ｓ３，ｉ、ｓ＾１，ｉ、ｓ＾２，ｉ、ｓ＾３，ｉ（添字ｉは１からＴ）を生成し、前記値ｑに基づいて複数の乱数値ｕ２、ｕ３，、ｕ＾２、ｕ＾３を生成し、
前記暗号化類似度生成部は、
ｄｉ＝（ｃｉ−ｃ’ｉ）＋（ｓ１，ｉ×ｗ１）＋（ｓ２，ｉ×ｗ２）＋（ｓ３，ｉ×ｗ３）を添字ｉについて１からＴまでを計算し、
ｄ＾ｉ＝（ｃ＾ｉ−ｃ’＾ｉ）＋（ｓ＾１，ｉ×ｗ＾１）＋（ｓ＾２，ｉ×ｗ＾２）＋（ｓ＾３，ｉ×ｗ＾３）を添字ｉについて１からＴまでを計算し、
Ｅ＝｛（ｓ＾１，ｉ×（ｃｉ−ｃ’ｉ）＋ｓ１，ｉ×ｓ＾１，ｉ×ｗ１）の添字ｉについての１からＴまでの総和｝＋（ｕ２×ｗ２）＋（ｕ３×ｗ３）を計算し、
Ｅ＾＝［｛ｓ１，ｉ×（ｃ＾ｉ−ｃ’＾ｉ）｝の添字ｉについての１からＴまでの総和］＋（ｕ＾２×ｗ＾２）＋（ｕ＾３×ｗ＾３）を計算し、
計算した値ｄｉ、ｄ＾ｉ、Ｅ及びＥ＾を含む暗号化類似度情報を生成することを特徴とする請求項６に記載のデータ処理装置。
【請求項１１】
前記暗号化データ記憶部は、
Ｔ個の部分データｂｉが前記暗号装置で生成された乱数値ｒ２，ｉとｒ３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ１、ｗ２、ｗ３が用いられてｃｉ＝（ｂｉ×ｗ１）＋（ｒ２，ｉ×ｗ２）＋（ｒ３，ｉ×ｗ３）により暗号化されたＴ個の部分データｃｉと、Ｔ個の部分データｂｉが前記暗号装置で生成された乱数値ｒ＾２，ｉとｒ＾３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３が用いられてｃ＾ｉ＝（ｂｉ×ｗ＾１）＋（ｒ＾２，ｉ×ｗ＾２）＋（ｒ＾３，ｉ×ｗ＾３）により暗号化されたＴ個の部分データｃ＾ｉで構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
Ｔ個の部分データｂ’ｉが前記暗号装置で生成された乱数値ｒ’２，ｉとｒ’３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ１、ｗ２、ｗ３が用いられてｃ’ｉ＝（ｂ’ｉ×ｗ１）＋（ｒ’２，ｉ×ｗ２）＋（ｒ’３，ｉ×ｗ３）により暗号化されたＴ個の部分データｃ’ｉと、Ｔ個の部分データｂ’ｉが前記暗号装置で生成された乱数値ｒ’＾２，ｉとｒ’＾３，ｉ（添字ｉは１からＴ）と前記ランダム基底ｗ＾１、ｗ＾２、ｗ＾３が用いられてｃ’＾ｉ＝（ｂ’ｉ×ｗ＾１）＋（ｒ’＾２，ｉ×ｗ＾２）＋（ｒ’＾３，ｉ×ｗ＾３）により暗号化されたＴ個の部分データｃ’＾ｉで構成される暗号化第２データを入力することを特徴とする請求項１０に記載のデータ処理装置。
【請求項１２】
前記データ処理装置は、更に、
前記暗号化類似度生成部により生成された暗号化類似度情報を前記復号装置に出力する暗号化類似度出力部と、
前記復号装置において前記暗号化類似度情報に対して前記秘密鍵の逆行列と双対ペアリングベクトル空間におけるディストーション写像とが用いられる復号処理が行われて導出された前記第１データと前記第２データとの間の類似度を入力する類似度入力部と、
前記類似度入力部により入力された前記類似度を解析して、前記第２データの発生源が正当であるか否かを判定する判定部とを有することを特徴とする請求項１０に記載のデータ処理装置。
【請求項１３】
前記公開鍵記憶部は、
前記二重準同型暗号アルゴリズムに基づいて生成された公開鍵として、ＢＧＮ（Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ）暗号アルゴリズムに基づいて生成された公開鍵を記憶し、
前記ＢＧＮ暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記ＢＧＮ暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第２データを入力することを特徴とする請求項１に記載のデータ処理装置。
【請求項１４】
前記公開鍵記憶部は、
Ｎ＝ｐ×ｑ（ｐ及びｑは素数）を位数とする群Ｇからランダムに選択された値ｇと値ｕと、値ｈ＝ｕｑと、所定の値Ｎを公開鍵として記憶し、
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データｂｉ（添字ｉは１からＴ）に値ｇと値ｈを保有する前記暗号装置により値ｇと値ｈを用いた暗号化が行われて得られたＴ個の暗号化された部分データｃｉ（添字ｉは１からＴ）で構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データｂ’ｉ（添字ｉは１からＴ）に前記暗号装置により値ｇと値ｈを用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ’ｉ（添字ｉは１からＴ）で構成される暗号化第２データを入力し、
前記乱数生成部は、
前記値Ｎに基づいて乱数値ｓを生成し、
前記暗号化類似度生成部は、
Ｅ＝ｅ（ｃｉ、ｃ’ｉ）×ｅ（ｇ、ｈ）ｓの添字ｉについて１からＴまでの総乗を計算し（ｅ：Ｇ×Ｇ＾→ＧＴは双線型性と非退化性を満たすペアリング）、計算した値Ｅを含む暗号化類似度情報を生成することを特徴とする請求項１３に記載のデータ処理装置。
【請求項１５】
前記公開鍵記憶部は、
Ｎ＝ｐ×ｑ（ｐ及びｑは素数）を位数とする群Ｇからランダムに選択された値ｇと値ｕと、値ｈ＝ｕｑと、所定の値Ｎを公開鍵として記憶し、
前記暗号化データ記憶部は、
前記第１データを構成するＴ（Ｔは２以上の整数）個の部分データｂｉ（添字ｉは１からＴ）に値ｇと値ｈを保有する前記暗号装置により値ｇと値ｈを用いた暗号化が行われて得られた部分データｃｉ（添字ｉは１からＴ）で構成される暗号化第１データを記憶し、
前記暗号化データ入力部は、
前記第２データを構成するＴ（Ｔは２以上の整数）個の部分データｂ’ｉ（添字ｉは１からＴ）に前記暗号装置により値ｇと値ｈを用いた暗号化が行われて得られたＴ個の暗号化された部分データｃ’ｉ（添字ｉは１からＴ）で構成される暗号化第２データを入力し、
前記乱数生成部は、
前記値Ｎに基づいて乱数値ｓを生成し、
前記暗号化類似度生成部は、
Ｅ＝ｅ（ｃｉ、ｇ）×ｅ（ｃ’ｉ、ｇ）×ｅ（ｃｉ×ｃ’ｉ）−２×ｅ（ｇ、ｈ）ｓの添字ｉについて１からＴまでの総乗を計算し（ｅ：Ｇ×Ｇ＾→ＧＴは双線型性と非退化性を満たすペアリング）、計算した値Ｅを含む暗号化類似度情報を生成することを特徴とする請求項１３に記載のデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生体情報等を用いて本人認証を行う認証技術に関する。
【背景技術】
【０００２】
指紋認証や静脈認証などの生体認証は、指紋の紋様や静脈の形が個人ごとに異なることを利用して個人識別を行う仕組みのことである。
近年はビルの入退室管理やパーソナルコンピュータのログイン管理、銀行ＡＴＭ（Ａｕｔｏｍａｔｅｄ  Ｔｅｌｌｅｒ  Ｍａｃｈｉｎｅ）での本人認証などのアクセス管理に用いられている。【０００３】
生体認証においては、ユーザ（被認証者あるいは証明者）と認証装置（認証者）の間で以下のようにして認証を行うのが一般的である。【０００４】
あらかじめ登録段階において、ユーザが自分の生体情報を認証装置に登録しておく。
そして認証時には、ユーザが認証装置に生体情報を提示する。
認証装置は、登録されている生体情報と提示された生体情報とを照合し、その類似度がある条件を満たしていればユーザ本人であると判断し、条件を満たしていなければ他人であると判断する。【０００５】
このような生体認証において、生体情報は個人を特徴付けるプライバシー情報であるため保護されることが望ましい。
そこで、登録時に生体情報を暗号化して登録し、認証時にも生体情報を暗号化して照合を行うことで、生体情報そのものを露わにすることなく生体認証を行う方法が提案されている（例えば特許文献１）。
また、生体情報の暗号化に利用可能な暗号アルゴリズムとして、例えば、非特許文献１−４に開示の暗号アルゴリズムが考えられる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００８−５２１０２５号公報
【非特許文献】
【０００７】
【非特許文献１】Ｔ．Ｏｋａｍｏｔｏ、Ｋ．Ｔａｋａｓｈｉｍａ、“Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ”、Ｐａｉｒｉｎｇ  ２００８、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．５２０９、  ｐｐ．５７−７４、  ２００８．
【非特許文献２】Ｄ．Ｂｏｎｅｈ、Ｅ．−Ｊ．Ｇｏｈ、Ｋ．Ｎｉｓｓｉｍ、  “Ｅｖａｌｕａｔｉｎｇ  ２−ＤＮＦ  ｆｏｒｍｕｌａｓ  ｏｎ  ｃｉｐｈｅｒｔｅｘｔｓ”、  Ｔｈｅｏｒｙ  Ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．３３７８、  ｐｐ．３２５−３４１、  ２００５．
【非特許文献３】Ｃ．Ｇｅｎｔｒｙ、  “Ｆｕｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｕｓｉｎｇ  ｉｄｅａｌ  ｌａｔｔｉｃｅｓ”、  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  Ｏｆ  Ｃｏｍｐｕｔｉｎｇ、  ｐｐ．１６９−１７８、  ２００９．
【非特許文献４】Ｄ．Ｆｒｅｅｍａｎ、Ｍ．Ｓｃｏｔｔ、Ｅ．Ｔｅｓｋｅ、  “Ａ  ｔａｘｏｎｏｍｙ  ｏｆ  ｐａｉｒｉｎｇ−ｆｒｉｅｎｄｌｙ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ”、  Ｊｏｕｒｎａｌ  Ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ、２００９年６月．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１では、公開鍵暗号技術を用いた暗号化により生体情報の保護を図っているが、生体情報を暗号化する際、暗号アルゴリズムとしてＰａｉｌｌｉｅｒ暗号やＥｌＧａｍａｌ暗号などの通常の準同型暗号を用いている。
ここで通常の準同型暗号とは、例えばＴ個の暗号文Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ）を用いて暗号文Ｅ（ｘ１＋ｘ２＋．．．＋ｘＴ）が計算できるというように、複数の暗号文から元の平文の和の暗号文が計算できるような暗号である。
ここでＥ（ｘ１）はある公開鍵を用いて生成したｘ１の暗号文を表す。
なお、上記では加算を例に挙げたが、正確に定義すると、ここでいう通常の準同型暗号とは、複数の暗号文から元の平文に対してある１種類の演算を施した暗号文が計算できるような暗号である。
演算の種類としては、有限体における加法や乗法などの種類があるが、いずれにしても１種類のみの演算が可能な暗号である。【０００９】
しかし、このような通常の準同型暗号を用いた場合、認証時の計算過程において、暗号化した生体情報だけですべての処理を完結させることはできず、平文の生体情報を必要とする箇所が存在していた。【００１０】
例えば、特許文献１に記載の認証方法の場合、類似度判定の指標として、生体情報から生成された特徴ベクトルのハミング距離（すなわち、ベクトルを構成するビット列同士のハミング距離）を利用し、以下のような手順で秘匿照合処理を行っていた。
なお、ここでは、ユーザは認証装置に直接アクセスするのではなく、証明装置にアクセスし、証明装置が認証装置との間で通信を行って、生体情報の登録処理および認証処理を行うものとする。
つまり、生体情報を用いたリモートログインをも含めたより一般的な生体認証方式を想定する。
また、暗号化時には、システム共通の公開鍵を用いて暗号化を行うものとする。【００１１】
登録時、証明装置はユーザから生体情報を抽出し、抽出した生体情報からユーザの特徴を表す特徴ベクトルを構成する。
この特徴ベクトルをビット列Ｘ＝（ｘ１，ｘ２，．．．，ｘＴ）とする。
証明装置は、抽出した特徴ベクトルを、Ｐａｉｌｌｉｅｒ暗号を用いてビットごとに暗号化して暗号化ビット列Ｅ（Ｘ）＝（Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ））を計算し、認証装置に送付して登録する。
認証時、証明装置は登録時と同様にユーザから生体情報ビット列Ｙ＝（ｙ１，ｙ２，．．．，ｙＴ）を抽出する。
その上で、登録しておいた暗号化ビット列Ｅ（Ｘ）＝（Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ））を認証装置から受け取る。
ここで証明装置は、ビット列ＸとＹのハミング距離ｄＨ（Ｘ，Ｙ）の暗号文を算出するに際して、準同型暗号の以下の性質（数１）を利用する。【００１２】
【数１】
2011052056.tif 000003
【００１３】
ここで、第２式から第３式への移行は、ｘ１，ｙ１が０、１の二値しかとらないことによる。
また、第３式から第４式への移行は、Ｐａｉｌｌｉｅｒ暗号が通常の準同型暗号であり、暗号文同士の積により元の平文の和の暗号文が得られるという性質による。【００１４】
この性質を利用して、証明装置は、認証装置から受け取った暗号化ビット列Ｅ（Ｘ）＝（Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ））と、生体情報ビット列Ｙ＝（ｙ１，ｙ２，．．．，ｙＴ）を用いて以下の値を計算し（数２）、認証装置に送付する。【００１５】
【数２】
2011052056.tif 000004
【００１６】
認証装置では、受け取った値に以下の値（数３）を掛け合わせ、暗号化ハミング距離Ｅ（ｄＨ（Ｘ，Ｙ））を計算する。
そして、セキュアプロトコルを用いてハミング距離を復号し、類似度判定を行う。【００１７】
【数３】
2011052056.tif 000005
【００１８】
このように、Ｐａｉｌｌｉｅｒ暗号などの通常の準同型暗号を用いた場合には、−２ｘｉｙｉの暗号文を計算する際にＥ（ｘｉ）−２ｙｉと計算するため、指数部分に平文ｙｉが必要である。
つまり、準同型暗号の本質上、すべてを暗号文で処理することはできない。
そのため、一旦認証装置から証明装置に暗号化生体情報Ｅ（Ｘ）＝（Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ））を送付し、証明装置が平文ｙｉを用いた計算を行う必要がある。【００１９】
この暗号化生体情報の送付に際しては、認証の対象となるユーザが別途ＩＤ情報などによって特定されているいわゆる１：１認証の場合には１人分の送付でよいが、認証の対象となるユーザが特定されておらず、データベースに格納された多くのユーザとの照合を必要とするいわゆる１：Ｎ認証の場合には、ユーザ数に比例した送付が必要となる。
そのため、ユーザ数に比例して認証装置と証明装置との間の通信量が増大するという課題がある。【００２０】
また、証明装置から平文の生体情報をできるだけ早く消去することがセキュリティの観点から望ましい。
しかし、上記のように認証に平文の生体情報が必要なため、特に１：Ｎ認証においては認証が完了するまで端末上の生体情報を消去できず、窃取の危険により長くさらされてしまうという課題がある。【００２１】
本発明は、上記のような課題を解決することを主な目的の一つとし、認証処理の過程において必要であった平文を不要とし、平文の窃取の機会を減少させ、それによってより安全性の高い秘匿照合方法を提供することを主な目的とする。
また、認証装置と証明装置との間の通信量を低減させることも目的とする。
【課題を解決するための手段】
【００２２】
本発明に係るデータ処理装置は、
二重準同型暗号アルゴリズムに基づいて復号装置において生成され、前記復号装置から配布された公開鍵を記憶する公開鍵記憶部と、
前記復号装置から配布された前記公開鍵を保有する暗号装置が保有する前記公開鍵を用いて暗号化した第１データを暗号化第１データとして記憶する暗号化データ記憶部と、
前記暗号化第１データが前記暗号化データ記憶部に記憶された後に前記暗号装置が保有する前記公開鍵を用いて暗号化した第２データを暗号化第２データとして入力する暗号化データ入力部と、
前記公開鍵の少なくとも一部を用いて、乱数を生成する乱数生成部と、
前記暗号化第１データと前記暗号化第２データに対して前記公開鍵記憶部に記憶されている前記公開鍵と前記乱数生成部により生成された乱数を用いた演算を行って、前記暗号化第１データと前記暗号化第２データがそれぞれ暗号化された状態のままで、前記公開鍵に対応付けられて生成された秘密鍵を用いた復号処理により前記第１データと前記第２データとの間の類似度を導出可能な暗号化された情報を暗号化類似度情報として生成する暗号化類似度生成部とを有することを特徴とする。
【発明の効果】
【００２３】
本発明によれば、暗号化第１データと暗号化第２データがそれぞれ暗号化された状態のままで、公開鍵に対応付けられて生成された秘密鍵を用いた復号処理により第１データと第２データとの間の類似度を導出可能な暗号化類似度情報を生成するので、平文である第１データと第２データを用いることなく第１データと第２データの類似度を導出することができ、平文の窃取の可能性の低い安全な本人認証を実現することができる。
【図面の簡単な説明】
【００２４】
【図１】実施の形態１に係る生体認証システムの構成例を示す図。
【図２】実施の形態１に係る証明装置の構成例を示す図。
【図３】実施の形態１に係る認証装置の構成例を示す図。
【図４】実施の形態１に係る復号装置の構成例を示す図。
【図５】実施の形態１に係るセットアップ処理の例を示すフローチャート図。
【図６】実施の形態１に係る生体情報の登録処理の例を示すフローチャート図。
【図７】実施の形態１に係る認証処理の例を示すフローチャート図。
【図８】実施の形態１に係る認証処理の例を示すフローチャート図。
【図９】実施の形態１に係る認証処理の例を示すフローチャート図。
【図１０】実施の形態２に係る生体情報の登録処理の例を示すフローチャート図。
【図１１】実施の形態２に係る認証処理の例を示すフローチャート図。
【図１２】実施の形態２に係る認証処理の例を示すフローチャート図。
【図１３】実施の形態３に係るセットアップ処理の例を示すフローチャート図。
【図１４】実施の形態３に係る生体情報の登録処理の例を示すフローチャート図。
【図１５】実施の形態３に係る認証処理の例を示すフローチャート図。
【図１６】実施の形態３に係る認証処理の例を示すフローチャート図。
【図１７】実施の形態３に係る認証処理の例を示すフローチャート図。
【図１８】実施の形態４に係る認証処理の例を示すフローチャート図。
【図１９】実施の形態４に係る認証処理の例を示すフローチャート図。
【図２０】実施の形態４に係る認証処理の例を示すフローチャート図。
【図２１】実施の形態１に係るセットアップ処理の概要を示すフローチャート図。
【図２２】実施の形態１に係る生体情報の登録処理の概要を示すフローチャート図。
【図２３】実施の形態１に係る認証処理の概要を示すフローチャート図。
【図２４】実施の形態１に係る認証処理の概要を示すフローチャート図。
【図２５】実施の形態１に係る証明装置、認証装置、復号装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【００２５】
以下に示す実施の形態では、生体情報を保護するための暗号方式として、通常の準同型暗号ではなく、二重準同型暗号（Ｄｏｕｂｌｙ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ）と呼ばれる暗号を用いる。
ここで二重準同型暗号とは、通常の準同型暗号とは異なり、例えば２Ｔ個の暗号文Ｅ（ｘ１），Ｅ（ｘ２），．．．，Ｅ（ｘＴ），Ｅ（ｙ１），Ｅ（ｙ２），．．．，Ｅ（ｙＴ）を用いて暗号文Ｅ（ｘ１＊ｙ１＋ｘ２＊ｙ２＋．．．＋ｘＴ＊ｙＴ）が計算できるというように、複数の暗号文から元の平文の有限体上の和と積を組み合わせた暗号文を計算できる暗号である。
つまり、以下に示す実施の形態では、登録用の生体情報はＴ（Ｔは２以上の整数）個の部分データから構成され、認証用の生体情報はＴ（Ｔは２以上の整数）個の部分データから構成される。
そして、登録されているＴ個の部分データと、認証用として入力されたＴ個の部分データにおいて値が一致する部分データの数やハミング距離等を類似度として導出して、類似度が所定レベル以上であれば本人であると認証する。
【００２６】
二重準同型暗号の具体的なアルゴリズムとしては、例えば非特許文献１から非特許文献３に開示のアルゴリズムがある。
生体認証においてこれらの二重準同型暗号を利用するには、生体情報から特徴ベクトルを生成する方法と、特徴ベクトルに対する二重準同型暗号の適用方法とにそれぞれ工夫を加える必要がある。
【００２７】
生体認証では、本人判定をするための指標に様々な種類があり、それに応じて特徴ベクトルの生成方法にも様々な種類がある。
しかし、二重準同型暗号の特性を生かして平文の特徴ベクトルを認証処理時に不要とするためには、本人判定の指標をそのまま用いてもよいというわけではない。
以下の実施の形態では、特徴点の有無を１，０のビット列で表現し、１のビットが一致した箇所の数の多さを指標とすることにより本人判定をする方法、ビット列同士のハミング距離を指標とすることにより本人判定をする方法、数値列同士のユークリッド二乗距離を指標とすることにより本人判定をする方法、を開示する。
【００２８】
また、本人判定の方法に合わせて各文献の暗号の適用方法を工夫する必要もある。
本発明では、実施の形態１および実施の形態２において非特許文献１の適用方法を開示し、実施の形態３および実施の形態４において非特許文献２の適用方法を開示する。
【００２９】
ここで、非特許文献１の岡本−高島暗号のアルゴリズムを、実施の形態１および実施の形態２の説明に必要となる範囲に限って説明する。
【００３０】
岡本−高島暗号は、楕円曲線を用いて定義される双対ペアリングベクトル空間を用いた暗号である。
この双対ペアリングベクトル空間を構成する方法は複数考えられるが、ここでは楕円曲線の直積により構成する方法に基づいて説明する。
なお、楕円曲線上の群の演算は一般に加法群の演算として記述されることが多いが、ここでは有限体上の演算も含めすべて乗法群として記述する。
また、非対称ペアリングを用いたより一般的な方式に従って記述する。
【００３１】
Ｇ、Ｇ＾、ＧＴをそれぞれ素数位数ｑの群とする。
Ｆｑ＝｛０，１，…，ｑ−１｝とする。
ｅ：Ｇ×Ｇ＾→ＧＴを、双線型性（任意のｕ∈Ｇ，ｖ＾∈Ｇ＾，ａ，ｂ∈Ｆｑに対してｅ（ｕａ，ｖ＾ｂ）＝ｅ（ｕ，ｖ＾）ａｂとなる性質）および非退化性（ｅ（ｇ，ｇ＾）≠１であるようなｇ∈Ｇ，ｇ＾∈Ｇ＾が存在する性質）を満たすペアリングとする。
Ｎ個の群Ｇの直積集合をＶ＝Ｇ×Ｇ×…×Ｇ、同じくＮ個の群Ｇ＾の直積集合をＶ＾＝Ｇ＾×Ｇ＾×…×Ｇ＾とする。
このとき、数４に示す関係が成り立つ。
【００３２】
【数４】
2011052056.tif 000006
【００３３】
２つのベクトル空間Ｖ，Ｖ＾のペアリングとして、
ｕ＝（ｕ１，ｕ２，…，ｕＮ）∈Ｖ，ｖ＾＝（ｖ＾１，ｖ＾２，…，ｖ＾Ｎ）∈Ｖ＾に対するペアリングを、数５のように定義する。
【００３４】
【数５】
2011052056.tif 000007
【００３５】
ベクトル空間Ｖ，Ｖ＾において、数６に示す関係が成り立つ。
【００３６】
【数６】
2011052056.tif 000008
【００３７】
ｘ＝ｘ１ａ１＋ｘ２ａ２＋…＋ｘＮａＮ∈Ｖとする。
ベクトル空間Ｖにおけるディストーション写像φｉ，ｊ：Ｖ→Ｖを、φｉ，ｊ（ｘ）＝ｘｊａｉと定義する。
同様に、ｘ＾＝ｘ１ａ＾１＋ｘ２ａ＾２＋…＋ｘＮａ＾Ｎ∈Ｖ＾に対し、φ＾ｉ，ｊ：Ｖ＾→Ｖ＾を、φ＾ｉ，ｊ（ｘ＾）＝ｘｊａ＾ｉと定義する。
このようなディストーション写像は容易に計算可能である。
【００３８】
このように、標準基底があり、空間同士のペアリングが定義され、計算可能なディストーション写像が定義された２つのベクトル空間を双対ペアリングベクトル空間という。
【００３９】
Ｘ＝（Ｘｉ，ｊ），Ｘ＾＝（Ｘ＾ｉ，ｊ）を、各要素がＦｑから一様ランダムに選ばれた値で構成されるＮ行Ｎ列の正方行列とする。
このように構成したＸ，Ｘ＾はきわめて高い確率で正則行列となる。
このような正則行列を用いて、数７に示すように定義すると、Ｗ＝（ｗ１，ｗ２，…，ｗＮ），Ｗ＾＝（ｗ＾１，ｗ＾２，…，ｗ＾Ｎ）もまた基底となる。この基底をランダム基底と呼ぶ。
【００４０】
【数７】
2011052056.tif 000009
【００４１】
非特許文献１によれば、ベクトル空間Ｖ，Ｖ＾におけるランダム基底Ｗ＝（ｗ１，ｗ２，…，ｗＮ），Ｗ＾＝（ｗ＾１，ｗ＾２，…，ｗ＾Ｎ）に関して、以下の性質が成り立つ。
【００４２】
ＦＮｑの要素（ｘ１，ｘ２，…，ｘＮ）が与えられたとき、ｘ＝ｘ１ｗ１＋ｘ２ｗ２＋…＋ｘＮｗＮ，ｘ＾＝ｘ１ｗ＾１＋ｘ２ｗ＾２＋…＋ｘＮｗ＾Ｎを得ることは容易である。
しかし、ｘ＝ｘ１ｗ１＋ｘ２ｗ２＋…＋ｘＬｗＬ，ｘ＾＝ｘ１ｗ＾１＋ｘ２ｗ＾２＋…＋ｘＬｗ＾Ｌ（１＜Ｌ≦Ｎ）が与えられたときに、Ｘ＝（Ｘｉ，ｊ），Ｘ＾＝（Ｘ＾ｉ，ｊ）を用いずしてベクトルｙ＝ｘ１ｗ１＋ｘ２ｗ２＋…＋ｘｌｗｌ，ｙ＾＝ｘ１ｗ＾１＋ｘ２ｗ＾２＋…＋ｘｌｗ＾ｌ（１≦ｌ＜Ｌ）を得ることは、一般化されたＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ計算問題と同程度に難しいことが知られている。
一方で、Ｘ＝（Ｘｉ，ｊ），Ｘ＾＝（Ｘ＾ｉ，ｊ）を用いるならば、以下のアルゴリズムＤｅｃｏ（数８）により上記のようなベクトル分解が容易に計算可能である。なお、数８中のｋは整数である。
【００４３】
【数８】
2011052056.tif 000010
【００４４】
この性質から、正則行列を秘密鍵とすることによりトラップドア関数が実現できる。
【００４５】
以下、双対ペアリングベクトル空間を用いて、生体情報を暗号化したままで生体認証を行う方法の例を説明する。
【００４６】
実施の形態１．
本実施の形態では、生体認証で用いる特徴ベクトルとして、特徴点の配列を用意し、ユーザがその特徴点を保有する場合に１、特徴点を保有しない場合に０を配列に格納して、配列を特徴ベクトルとし、認証時には１が一致している箇所の数を類似度の指標とするような認証方式を例に説明する。
【００４７】
より詳しく言うと、例えば指紋認証の場合、指紋画像を小領域に分割しその領域内で隆線の流れる方向を調べると、個人ごとに各領域における流れの方向に特徴が出る。
そこで、例えば各領域について４つの流れの方向（０度、４５度、９０度、１３５度など）を定義しておき、検出した流れの方向を１、それ以外を０として、Ｎ個すべての領域について各４個の配列を用意し、検出値にしたがって配列値を定めることで特徴ベクトルとするような認証方式を考える。
【００４８】
このような認証方式においては、同一人物の特徴ベクトルでは１の位置がほぼ同じであるため、登録した特徴ベクトルと認証対象の特徴ベクトルの内積値が大きくなることが期待される。
一方、別人物の特徴ベクトルでは１の位置が本人のときよりも異なることが多いため、２つの特徴ベクトルの内積値が小さくなることが期待される。
【００４９】
図１は、実施の形態１−４に係る生体認証システムの構成例を示す図である。
【００５０】
図１において、証明装置１０１はユーザから生体情報を測定し、測定した生体情報を用いて秘匿照合処理を行う装置である。
認証装置１０２は、ユーザの生体情報を暗号化して格納しておくとともに、格納した暗号化された生体情報を用いて認証を行う装置である。
復号装置１０３は、暗号化データを復号する装置である。
なお、証明装置１０１は暗号装置の例であり、認証装置はデータ処理装置の例である。
【００５１】
図２は、証明装置１０１の内部構成の構成例を示す図である。
【００５２】
図２において、生体情報抽出部２０１は、光学カメラ、赤外線カメラなどの各種センサを用いて、個人識別を行うのに必要となる生体情報をユーザから抽出する。
特徴ベクトル形成部２０２は、生体情報抽出部２０１で抽出された生体情報から、個人の特徴を表す特徴ベクトルを形成する。
乱数生成部２０３は、公開鍵の一部を用いて乱数を生成する。
暗号化部２０４は、乱数生成部２０３が生成した乱数を用いて特徴ベクトルを暗号化する。
記憶部２０５は、公開鍵などの各種データを格納する。記憶部２０５が記憶する公開鍵は、復号装置１０３で生成され、復号装置１０３から配布された公開鍵である。
通信部２０６は、データベースなど他の装置との間でデータの送受信を行う。
【００５３】
図３は、認証装置１０２の内部構成の構成例を示す図である。
【００５４】
図３において、記憶部３０１は、暗号化された特徴ベクトル（以下、暗号化特徴ベクトルともいう）や公開鍵などの各種データを格納する。記憶部３０１は、公開鍵記憶部及び暗号化データ記憶部の例である。
なお、記憶部３０１が記憶する暗号化特徴ベクトルは、証明装置１０１により暗号化された登録用の特徴ベクトルである。暗号化前の登録用の特徴ベクトルが第１データの例に相当し、暗号化特徴ベクトルが暗号化第１データの例に相当する。
また、記憶部３０１が記憶する公開鍵は、復号装置１０３で生成され、復号装置１０３から配布された公開鍵である。
【００５５】
暗号化類似度生成部３０２は、登録されている暗号化特徴ベクトルと、認証用の暗号化特徴ベクトルから、暗号化類似度情報を算出する。
認証用の暗号化特徴ベクトルは、証明装置１０１により暗号化された認証用の特徴ベクトルである。暗号化前の認証用の特徴ベクトルが第２データの例に相当し、暗号化特徴ベクトルが暗号化第２データの例に相当する。
また、暗号化類似度情報は、公開鍵に対応付けられて生成された秘密鍵を用いた復号処理により登録用の特徴ベクトル（第１データ）と認証用の特徴ベクトル（第２データ）との間の類似度を復号装置１０３において導出可能な暗号化された情報である。
【００５６】
判定部３０３は、復号された類似度から個人識別を行い、本人か否かを判定する。
つまり、判定部３０３は、類似度を解析して、認証用の特徴ベクトルの発生源が正当であるか否かを判定する。
【００５７】
通信部３０４は、証明装置１０１や復号装置１０３との間でデータの送受信を行う。
より具体的には、通信部３０４は、登録用の暗号化特徴ベクトルが記憶部３０１に格納された後に証明装置１０１から認証用の暗号化特徴ベクトルを受信する。
また、通信部３０４は、暗号化類似度生成部３０２により生成された暗号化類似度情報を復号装置１０３に送信する。
また、通信部３０４は、復号装置１０３において暗号化類似度情報に対して秘密鍵を用いた復号処理が行われて導出された登録用の特徴ベクトルと認証用の特徴ベクトルとの間の類似度（平文）を受信する。
通信部３０４は、暗号化データ入力部、暗号化類似度出力部及び類似度入力部の例である。
【００５８】
乱数生成部３０５は、公開鍵の一部を用いて乱数を生成する。
【００５９】
図４は復号装置１０３の内部構成の構成例を示す図である。
【００６０】
図４において、パラメータ生成部４０１は、公開鍵や秘密鍵など、暗号化と復号に必要なパラメータを生成する。
復号部４０２は、暗号化類似度情報を復号し、平文の類似度を取り出す。
記憶部４０３は、公開鍵や秘密鍵などの各種データを格納する。
通信部４０４は、データベースなど他の装置との間でデータの送受信を行う。
【００６１】
次に、本実施の形態に係るデータ処理方法を説明する。
【００６２】
まず、動作の全体像を説明する。
動作は、セットアップ処理、登録処理、認証処理の３つに分かれる。
セットアップ処理では、復号装置１０３が、暗号化と復号に必要となるパラメータを生成する。
登録処理では、証明装置１０１がユーザの生体情報を暗号化して認証装置１０２に送付し、認証装置１０２が記憶部３０１に格納する。
認証処理では、まず証明装置１０１がユーザの生体情報を暗号化して認証装置１０２に送付する。次に、認証装置１０２が、記憶部３０１の暗号化生体情報と受領した暗号化生体情報を用いて暗号化類似度情報を生成し復号装置１０３に送付する。次に、復号装置１０３が類似度を復号し、認証装置１０２に復号された類似度を送付する。最後に認証装置１０２が類似度としきい値とを比較し、認証をする。
【００６３】
以下、図２１−図２４を用いて、各処理の概要を説明する。
図２１がセットアップ処理の概要を示し、図２２が登録処理の概要を示し、図２３及び図２４が認証処理の概要を示す。
【００６４】
まず、図２１を参照して、セットアップ処理の概要を説明する。
最初に、復号装置１０３のパラメータ生成部４０１が、岡本−高島暗号アルゴリズムに基づき、秘密鍵ｓｋと公開鍵ｐｋを生成する（Ｓ２１０１）。
次に、復号装置１０３の記憶部４０３が秘密鍵ｓｋを記憶し、通信部４０４が公開鍵ｐｋを証明装置１０１及び認証装置１０２に送信する（Ｓ２１０２）。
次に、証明装置１０１では、通信部２０６が公開鍵ｐｋを受信し、記憶部２０５が公開鍵ｐｋを記憶し、認証装置１０２では、通信部３０４が公開鍵ｐｋを受信し、記憶部３０１が公開鍵ｐｋを記憶する（Ｓ２１０２）。
なお、ここでは、公開鍵ｐｋを送受信する例を説明しているが、証明装置１０１及び認証装置１０２に公開鍵ｐｋを配布する方法は他の方法でもよい。
例えば、復号装置１０３が公開鍵ｐｋを記録媒体に格納し、証明装置１０１及び認証装置１０２において当該記録媒体から公開鍵ｐｋを読み出して格納するようにしてもよい。
【００６５】
次に、図２２を参照して、登録処理の概要を説明する。
最初に、証明装置１０１において、生体情報抽出部２０１が、ユーザの生体情報を抽出する（Ｓ２２０１）。
次に、証明装置１０１の特徴ベクトル形成部２０２が、Ｓ２２０１で抽出された生体情報の特徴ベクトルｂを生成する（Ｓ２２０２）。
次に、証明装置１０１の乱数生成部２０３が公開鍵ｐｋの一部を用いて乱数を生成し、また、暗号化部２０４が記憶部２０５から公開鍵ｐｋを読み出し、暗号化部２０４が公開鍵ｐｋと乱数を用いて特徴ベクトルｂを暗号化する（Ｓ２２０３）。
次に、証明装置１０１の通信部２０６が、暗号化された特徴ベクトルＣを認証装置１０２に送信する（Ｓ２２０４）。
次に、認証装置１０２の通信部３０４が、暗号化された特徴ベクトルＣを受信し、記憶部２０５が暗号化された特徴ベクトルＣを記憶する（Ｓ２２０５）。
【００６６】
次に、図２３及び図２４を参照して、認証処理の概要を説明する。
最初に、証明装置１０１において、生体情報抽出部２０１が、ユーザの生体情報を抽出する（Ｓ２３０１）。
次に、証明装置１０１の特徴ベクトル形成部２０２が、Ｓ２３０１で抽出された生体情報の特徴ベクトルｂ’を生成する（Ｓ２３０２）。
次に、証明装置１０１の乱数生成部２０３が公開鍵ｐｋの一部を用いて乱数を生成し、また、暗号化部２０４が記憶部２０５から公開鍵ｐｋを読み出し、暗号化部２０４が公開鍵ｐｋと乱数を用いて特徴ベクトルｂ’を暗号化する（Ｓ２３０３）。
次に、証明装置１０１の通信部２０６が、暗号化された特徴ベクトルＣ＾を認証装置１０２に送信する（Ｓ２３０４）。
次に、認証装置１０２の通信部３０４が、暗号化された特徴ベクトルＣ＾を受信する（Ｓ２３０５）。
【００６７】
次に、認証装置１０２の暗号化類似度生成部３０２が、記憶部３０１の暗号化特徴ベクトルＣを読み出す（Ｓ２４０１）。
次に、認証装置１０２の乱数生成部３０５が公開鍵ｐｋの一部を用いて乱数を生成し、また、暗号化類似度生成部３０２が記憶部３０１から公開鍵ｐｋを読み出し、暗号化類似度生成部３０２が記憶部３０１から読み出した暗号化特徴ベクトルＣと証明装置１０１から受信した暗号化特徴ベクトルＣ＾に対して、公開鍵ｐｋと乱数を用いて暗号化類似度情報を生成する（Ｓ２４０２）。
認証装置１０２は、公開鍵ｐｋに対応付けられている秘密鍵ｓｋを知りえないので、暗号化特徴ベクトルＣ及び暗号化特徴ベクトルＣ＾を復号することはできない。このため、暗号化特徴ベクトルＣ及び暗号化特徴ベクトルＣ＾が暗号化された状態のままで、暗号化類似度情報が生成される。
【００６８】
次に、認証装置１０２の通信部３０４が、暗号化類似度情報を復号装置１０３に送信する（Ｓ２４０３）。
次に、復号装置１０３の通信部４０４が、暗号化類似度情報を受信する（Ｓ２４０４）。
次に、復号装置１０３の復号部４０２が、パラメータ生成部４０１から秘密鍵ｓｋを読み出し、暗号化類似度情報に秘密鍵ｓｋを用いて復号処理を行い、平文の類似度を導出する（Ｓ２４０５）。
次に、復号装置１０３の通信部４０４が、平文の類似度を認証装置１０２に送信する（Ｓ２４０６）。なお、類似度は、登録用の特徴ベクトルｂと認証用の特徴ベクトルｂ’がどの程度類似しているかを示す情報であり、類似度からは特徴ベクトル、生体情報を計算することはできない。
次に、認証装置１０２の通信部３０４が、平文の類似度を受信する（Ｓ２４０７）。
次に、認証装置１０２の判定部３０３が、平文の類似度が所定のしきい値以上であるか否かを判定し、しきい値以上であれば本人であると判定し、しきい値を下回っている場合は、本人ではないと判定する（Ｓ２４０８）。
【００６９】
以下、図５−図９を参照して、各処理の動作をより詳しく説明する。
図５がセットアップ処理の詳細を示し、図６が登録処理の詳細を示し、図７−図９が認証処理の詳細を示す。
【００７０】
まず、図５を用いてセットアップについて説明する。
セットアップでは、復号装置１０３が、公開鍵ｐｋおよび秘密鍵ｓｋを生成する。
この公開鍵ｐｋおよび秘密鍵ｓｋは、ユーザごとに異なる公開鍵および秘密鍵であってもよいし、システムに１つの公開鍵および秘密鍵であってもよい。
ここでは、説明を簡単にするために、システムに１つの公開鍵および秘密鍵を用いる場合について説明するが、これをユーザごとの公開鍵および秘密鍵の場合に拡張するのは容易である。
【００７１】
図５は、パラメータ生成部４０１における公開鍵ｐｋ及び秘密鍵ｓｋの生成手順を示したフローチャートである。
【００７２】
はじめに、ステップＳ５０１にて、パラメータ生成部４０１は、群位数ｑ、群Ｇ、Ｇ＾、ＧＴ、生成元ｇ∈Ｇ、ｇ＾∈Ｇ＾を定める。
この具体的な方法は例えば非特許文献４にあるので、ここでは省略する。
なお、群位数はセキュリティレベルに応じて定まるが、通常は２００ビットや１０２４ビットなどの大きなサイズの素数とする。
【００７３】
次に、ステップＳ５０２にて、パラメータ生成部４０１は、ベクトル空間をＶ＝Ｇ×Ｇ×Ｇ、Ｖ＾＝Ｇ＾×Ｇ＾×Ｇ＾とし、標準基底Ａ＝（ａ１，ａ２，ａ３），Ａ＾＝（ａ＾１，ａ＾２，ａ＾３）を定める。
この定め方はすでに述べたとおりである。
【００７４】
次に、ステップＳ５０３にて、パラメータ生成部４０１は、０からｑ−１までの整数から一様ランダムに値を９回取り出し、それらを用いて３行３列の行列Ｘ＝（Ｘｉ，ｊ）を定める。
この行列は正則行列でなければならないが、この方法で行列を定めることによりきわめて高い確率で正則行列になる。なお、より正確性を期すのであれば、このように行列を定めた後に行列式を計算するなどの方法により正則性を判定し、正則でなければ行列の要素を再度ランダムに選べばよい。
【００７５】
次に、ステップＳ５０４にて、パラメータ生成部４０１は、０からｑ−１までの整数から一様ランダムに値を９回取り出し、それらを用いて３行３列の行列Ｘ＾＝（Ｘ＾ｉ，ｊ）を定める。
この行列はきわめて高い確率で正則行列になるが、正則行列にならなかった場合には再度ランダムに選べばよい。
【００７６】
次に、ステップＳ５０５にて、パラメータ生成部４０１は、以下の数９および数１０によりランダム基底Ｗ＝（ｗ１，ｗ２，ｗ３），Ｗ＾＝（ｗ＾１，ｗ＾２，ｗ＾３）を定める。
【００７７】
【数９】
2011052056.tif 000011
【００７８】
【数１０】
2011052056.tif 000012
【００７９】
最後に、ステップＳ５０６にて、パラメータ生成部４０１は、公開鍵ｐｋ＝（ｑ、Ｖ、Ｖ＾、ｅ、ＧＴ、Ａ、Ａ＾、Ｗ、Ｗ＾）を公開し、秘密鍵ｓｋ＝（Ｘ、Ｘ＾）を記憶部４０３に格納する。
【００８０】
次に、図６を用いて、生体情報の登録方法を説明する。
【００８１】
なお、ここではユーザが証明装置１０１を経由して認証装置１０２に生体情報を登録する場合について説明するが、認証装置１０２上で直接生体情報を登録する場合や、登録用の専用装置を経由して登録する場合などにおいても同様の手順により実現できる。
【００８２】
図６は、証明装置１０１において生体情報を登録する手順を示したフローチャートである。
【００８３】
はじめに、ステップＳ６０１にて、生体情報抽出部２０１が、ユーザの生体情報を抽出する。
これには様々な方法があるが、例えば指紋に光を当てて紋様をセンサで読み取るといったことにより抽出する。
【００８４】
次に、ステップＳ６０２にて、特徴ベクトル形成部２０２が、生体情報から特徴ベクトルｂ＝（ｂ１，ｂ２，…，ｂＴ）を形成する。
ここでＴは特徴ベクトルを格納する配列の大きさであり、特徴ベクトルの形成方法によって決まる値である。
本実施の形態の形成方法は、読み取った紋様を領域分割し、各領域で特徴点の有無を検出し、特徴点がある箇所の配列に１、ない箇所の配列に０を格納することにより特徴ベクトルを形成するという方法である。
【００８５】
次に、ステップＳ６０３にて、乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を２Ｔ回取り出し、｛ｒ２，ｉ，ｒ３，ｉ｝ｉ＝１，２，…，Ｔとする。
なお、ｑ−１のｑは、公開鍵ｐｋに含まれているｑである。
【００８６】
次に、ステップＳ６０４にて、暗号化部２０４が、ｃｉ＝ｂｉｗ１＋ｒ２，ｉｗ２＋ｒ３，ｉｗ３により暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を計算する。
なお、ｗ１，ｗ２，ｗ３は、公開鍵の一部（Ｗ）として、復号装置１０３から配布されたものである。
【００８７】
次に、ステップＳ６０５にて、通信部２０６が、暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を認証装置１０２に送信する。
その際、例えばＳＳＬ（Ｓｅｃｕｒｅ  Ｓｏｃｋｅｔｓ  Ｌａｙｅｒ）などの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【００８８】
最後に、ステップＳ６０６にて、認証装置１０２において、通信部３０４が暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を受信し、記憶部３０１に格納する。
【００８９】
次に、図７ないし図９を用いて、認証方法を説明する。
なお、簡単のためここでは認証時に認証の対象となるユーザが別途ＩＤ情報などによって特定されているいわゆる１：１認証の場合について説明する。
【００９０】
図７、図８、図９は、認証を行う手順を示したフローチャートである。
【００９１】
はじめに、ステップＳ７０１にて、証明装置１０１の生体情報抽出部２０１がユーザの生体情報を抽出する。
抽出方法は生体情報の登録時と同様である。
【００９２】
次に、ステップＳ７０２にて、証明装置１０１の特徴ベクトル形成部２０２が、生体情報から特徴ベクトルｂ’＝（ｂ’１，ｂ’２，…，ｂ’Ｔ）を形成する。
形成方法は、生体情報の登録時と同様である。
【００９３】
次に、ステップＳ７０３にて、証明装置１０１の乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を２Ｔ回取り出し、｛ｒ’２，ｉ，ｒ’３，ｉ｝ｉ＝１，２，…，Ｔとする。
【００９４】
次に、ステップＳ７０４にて、証明装置１０１の暗号化部２０４が、ｃ＾ｉ＝（ｂ’ｉｗ＾１＋ｒ’２，ｉｗ＾２＋ｒ’３，ｉｗ＾３）により暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を計算する。
なお、ｗ＾１，ｗ＾２，ｗ＾３は、公開鍵の一部（Ｗ＾）として、復号装置１０３から配布されたものである。
【００９５】
次に、ステップＳ７０５にて、証明装置１０１の通信部２０６が、暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を認証装置１０２に送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【００９６】
次に、ステップＳ７０６にて、認証装置１０２の通信部３０４が、暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を受信する。
【００９７】
次に、ステップＳ７０７にて、認証装置１０２において、暗号化類似度生成部３０２が、記憶部３０１から暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を取り出す。
このとき、一般に記憶部３０１には多数のユーザの暗号化生体情報が格納されているが、その中からどれを取り出すかについては、別途与えられるＩＤ情報を用いる。
【００９８】
次に、ステップＳ７０８にて、認証装置１０２の乱数生成部３０５が、０からｑ−１までの整数から一様ランダムに値を６Ｔ回取り出し、｛ｓ１，ｉ，ｓ２，ｉ，ｓ３，ｉ，ｓ＾１，ｉ，ｓ＾２，ｉ，ｓ＾３，ｉ｝ｉ＝１，２，…，Ｔとする。
【００９９】
次に、ステップＳ７０９にて、認証装置１０２の乱数生成部３０５が、０からｑ−１までの整数から一様ランダムに値を４回取り出し、｛ｕ２，ｕ３，ｕ＾２，ｕ＾３｝とする。
【０１００】
次に、ステップＳ７１０にて、認証装置１０２の暗号化類似度生成部３０２が、ｄｉ＝ｃｉ＋ｓ１，ｉｗ１＋ｓ２，ｉｗ２＋ｓ３，ｉｗ３を計算する。
暗号化類似度生成部３０２は、これをすべてのｉ＝１、２、…、Ｔについて行う。
なお、ｗ１，ｗ２，ｗ３は、公開鍵の一部（Ｗ）として、復号装置１０３から配布されたものである。
【０１０１】
次に、ステップＳ７１１にて、認証装置１０２の暗号化類似度生成部３０２、がｄ＾ｉ＝ｃ＾ｉ＋ｓ＾１，ｉｗ＾１＋ｓ＾２，ｉｗ＾２＋ｓ＾３，ｉｗ＾３を計算する。
暗号化類似度生成部３０２は、これをすべてのｉ＝１、２、…、Ｔについて行う。
なお、ｗ＾１，ｗ＾２，ｗ＾３は、公開鍵の一部（Ｗ＾）として、復号装置１０３から配布されたものである。
【０１０２】
次に、ステップＳ７１２にて、認証装置１０２の暗号化類似度生成部３０２が、数１１に従って、Ｅを計算する。
【０１０３】
【数１１】
2011052056.tif 000013
【０１０４】
次に、ステップＳ７１３にて、認証装置１０２の暗号化類似度生成部３０２が、数１２に従って、Ｅ＾を計算する。
【０１０５】
【数１２】
2011052056.tif 000014
【０１０６】
次に、ステップＳ７１４にて、認証装置１０２の通信部３０４が、（ｄ１，…，ｄＴ，ｄ＾１，…，ｄ＾Ｔ，Ｅ，Ｅ＾）を復号装置１０３へ送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
なお、上記（ｄ１，…，ｄＴ，ｄ＾１，…，ｄ＾Ｔ，Ｅ，Ｅ＾）が、一体となって暗号化類似度情報を構成する。
【０１０７】
次に、ステップＳ７１５にて、復号装置１０３の通信部４０４が、（ｄ１，…，ｄＴ，ｄ＾１，…，ｄ＾Ｔ，Ｅ，Ｅ＾）を受信する。
【０１０８】
次に、ステップＳ７１６にて、復号装置１０３の復号部４０２が、記憶部４０３から秘密鍵ｓｋ＝（Ｘ，Ｘ＾）を取り出す。
【０１０９】
次に、ステップＳ７１７にて、復号装置１０３の復号部４０２が、Ｘの逆行列Ｘ−１＝（ｔｉ，ｊ）およびＸ＾の逆行列Ｘ＾−１＝（ｔ＾ｉ，ｊ）を計算する。
なお、この値は毎回計算するのではなく、あらかじめ計算した状態で記憶部４０３に格納しておき、それを取り出すものとしてもよい。
【０１１０】
次に、ステップＳ７１８にて、復号装置１０３が、数１３に従ってＺ１を計算する。
【０１１１】
【数１３】
2011052056.tif 000015
【０１１２】
ここで、Ｄｅｃｏアルゴリズムは以下の数１４のように計算される。なお、数１４中のｋは整数である。
【０１１３】
【数１４】
2011052056.tif 000016
【０１１４】
次に、ステップＳ７１９にて、復号装置１０３の復号部４０２が、Ｚ２＝ｅ（Ｄｅｃｏ（Ｅ，〈ｗ１〉，Ｘ），ｗ＾１）・ｅ（ｗ１，Ｄｅｃｏ（Ｅ＾，〈ｗ＾１〉，Ｘ＾））を計算する。
このＤｅｃｏアルゴリズムも上記と同様に計算される。
【０１１５】
次に、ステップＳ７２０にて、復号装置１０３の復号部４０２がＺ＝Ｚ１／Ｚ２を計算する。
【０１１６】
次に、ステップＳ７２１にて、復号装置１０３の復号部４０２がｅ（ｇ，ｇ＾）を底とするＺの離散対数ｄを計算する。
この離散対数ｄが、特徴点の一致数に対応しており、類似度を表す。
【０１１７】
なお、離散対数を求める計算は現代の計算機能力では困難とされているが、ｄが小さい場合には効率的に計算することができる。
本実施の形態においてｄは位数ｑに比べて十分小さいため、効率的に計算することができる。
【０１１８】
次に、ステップＳ７２２にて、復号装置１０３の通信部４０４が、類似度ｄを認証装置１０２へ送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【０１１９】
次に、ステップＳ７２３にて、認証装置１０２の通信部３０４が、類似度ｄを受信する。
【０１２０】
次に、ステップＳ７２４にて、類似度ｄがしきい値以上かを判定する。
しきい値は、利用する生体情報の種類や安全性要件などさまざまな要素を勘案してあらかじめシステムで決められた値である。
しきい値以上であれば、証明装置１０１から送られてきた暗号化生体情報はＩＤで指定された本人のものであると判断する。
一方、しきい値未満であれば、証明装置１０１から送られてきた暗号化生体情報はＩＤで指定された人物のものではなく、他人のものであると判断する。
【０１２１】
以上のステップにより、認証装置１０２は証明装置１０１との間で生体認証を行うことができる。
【０１２２】
以上の実施の形態によれば、認証装置１０２には特徴ベクトルがそのまま保管されるのではなく、暗号化された状態で保管されるため、ユーザにとっては、プライバシー情報である特徴ベクトルが認証装置１０２の管理者に盗み見られるというリスクを低減させることができるという効果がある。
【０１２３】
また、認証装置１０２にとっては、暗号化された特徴ベクトルが仮に漏洩したとしても、元の特徴ベクトル自体が漏洩することはないため、特徴ベクトルそのものを保管するのに比べてデータ管理の手間を削減できるという効果がある。
【０１２４】
また、本実施の形態の手順に従えば、復号装置１０３が復号できるのは類似度という指標値だけであり、特徴ベクトルを復号することはできない。
したがって、証明装置１０１と復号装置１０３が結託しない限り、認証の過程において特徴ベクトルが現れることはないため、生体情報を秘匿したままでの生体認証が可能であるという効果がある。
【０１２５】
また、本実施の形態によれば、認証時に証明装置１０１から認証装置１０２へ暗号化特徴ベクトルを送付すれば、その後は認証装置１０２と復号装置１０３との間で認証処理を行うことができるため、特に１：Ｎ認証においては、証明装置１０１と認証装置１０２との間でユーザ数に比例した回数の通信を行う必要がなく、通信量を低減させることができるという効果がある。
【０１２６】
また、本実施の形態によれば、認証時に証明装置１０１から認証装置１０２へ暗号化特徴ベクトルを送付すれば、その後は認証装置１０２と復号装置１０３との間で認証処理を行うことができるため、証明装置１０１上で取得した生体情報をただちに消去できる。
したがって、証明装置１０１における生体情報の窃取の機会を低減できるという効果がある。
【０１２７】
また、本実施の形態では、特徴ベクトルの構成時に、特徴点がある箇所に１、特徴点がない箇所に０を格納し、１と０から構成されるベクトル同士で内積を取るという構成としたが、これに重要度の概念を導入し、重要な特徴点については重みをつける（たとえば１の代わりに５を格納する）という構成にすることもできる。
このような構成にすれば、単に内積をとる場合に比べて、より精度の高い生体認証を実現することができるという効果がある。
【０１２８】
なお、本実施の形態では３次元の双対ペアリングベクトル空間を用いる方法を開示したが、３次元というのはあくまで例であって、必ずしも３次元である必要はない。
例えば２次元でも実施可能であるし、４次元以上でも実施可能である。
２次元の場合には、本実施の形態中に現れたｗ３，ｗ＾３のベクトルを取り除いて実施すればよい。
このようにすれば、生体情報の登録時や認証時の計算量を低減できるという効果がある。
また、４次元以上の場合には、増えた分のベクトルにｗ２，ｗ３，ｗ＾２，ｗ＾３と同様のはたらきをさせればよい。
すなわち、ｃｉ，ｃ＾ｉ，ｄｉ，ｄ＾ｉを計算する際、増えた分のベクトルに乱数係数をかけて、ｗ２，ｗ３，ｗ＾２，ｗ＾３に加え合わせればよい。
このようにすれば、より解読が困難な暗号文を作成することができ、安全性を向上させることができる。
【０１２９】
また、本実施の形態では安全性向上のため、認証時にステップＳ７０９にて｛ｕ２，ｕ３，ｕ＾２，ｕ＾３｝を選び、ステップＳ７１２およびステップＳ７１３にて使用する構成としていたが、これを省略することもできる。
そうすれば、認証の手順が省けるので、計算量を低減させることができる。
【０１３０】
実施の形態２．
以上の実施の形態１では、特徴点の一致数を評価指標として生体認証を行うという認証方法を開示したが、次に、特徴ベクトルのハミング距離またはユークリッド二乗距離により生体認証を行うという認証方法を述べる。
なお、本実施の形態に係る生体認証システムの構成例も図１に示した通りである。
また、本実施の形態に係る証明装置１０１、認証装置１０２、復号装置１０３の内部構成例も、図２−図４に示した通りである。
【０１３１】
本実施の形態では、実施の形態１と同様にＴ個の配列を用意し、それによって特徴ベクトルを構成するが、このとき類似度の指標として２つの特徴ベクトルのハミング距離またはユークリッド二乗距離を用いる。２つの特徴ベクトルをｂ＝（ｂ１，ｂ２，…，ｂＴ）、ｂ’＝（ｂ’１，ｂ’２，…，ｂ’Ｔ）とする。
このとき、２つの特徴ベクトルのハミング距離は、数１５で与えられ（ただしｂｉ，ｂ’ｉ∈｛０，１｝）、また、２つの特徴ベクトルのユークリッド二乗距離は、数１６で与えられる。
【０１３２】
【数１５】
2011052056.tif 000017
【０１３３】
【数１６】
2011052056.tif 000018
【０１３４】
本実施の形態におけるパラメータ生成方法は、実施の形態１の図５と同様であるので説明を省略する。
【０１３５】
次に、図１０を用いて、生体情報の登録方法を説明する。
【０１３６】
なお、ここではユーザが証明装置１０１を経由して認証装置１０２に生体情報を登録する場合について説明するが、認証装置１０２上で直接生体情報を登録する場合や、登録用の専用装置を経由して登録する場合などにおいても同様の手順により実現できる。
【０１３７】
図１０は、証明装置１０１において生体情報を登録する手順を示したフローチャートである。
【０１３８】
ステップＳ１００１とステップＳ１００２は実施の形態１と同様である。
ただし、ここでハミング距離の場合はｂｉ∈｛０，１｝であり、ユークリッド二乗距離の場合は、ｂｉ∈｛０，１，…，ｑ−１｝であることに注意する。
【０１３９】
次に、ステップＳ１００３にて、乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を４Ｔ回取り出し、｛ｒ２，ｉ，ｒ３，ｉ，ｒ＾２，ｉ，ｒ＾３，ｉ｝ｉ＝１，２，…，Ｔとする。
【０１４０】
次に、ステップＳ１００４にて、暗号化部２０４が、ｃｉ＝ｂｉｗ１＋ｒ２，ｉｗ２＋ｒ３，ｉｗ３，ｃ＾ｉ＝ｂｉｗ＾１＋ｒ＾２，ｉｗ＾２＋ｒ＾３，ｉｗ＾３により暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ），暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を計算する。
なお、ｗ１，ｗ２，ｗ３とｗ＾１，ｗ＾２，ｗ＾３は、公開鍵の一部（Ｗ及びＷ＾）として、復号装置１０３から配布されたものである。
【０１４１】
次に、ステップＳ１００５にて、通信部２０６が、暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ），暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を認証装置１０２に送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【０１４２】
最後に、ステップＳ１００６にて、認証装置１０２が、暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ），暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を記憶部３０１に格納する。
【０１４３】
次に、図１１、図１２、図１３を用いて、認証方法を説明する。
なお、簡単のためここでは認証時に認証の対象となるユーザが別途ＩＤ情報などによって特定されているいわゆる１：１認証の場合について説明する。
【０１４４】
ステップＳ１１０１とステップＳ１１０２は実施の形態１と同様である。
ただし、ここでハミング距離の場合はｂ’ｉ∈｛０，１｝であり、ユークリッド二乗距離の場合はｂ’ｉ∈｛０，１，…，ｑ−１｝であることに注意する。
【０１４５】
次に、ステップＳ１１０３にて、証明装置１０１の乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を４Ｔ回取り出し、｛ｒ’２，ｉ，ｒ’３，ｉ，ｒ＾’２，ｉ，ｒ＾’３，ｉ｝ｉ＝１，２，…，Ｔとする。
【０１４６】
次に、ステップＳ１１０４にて、証明装置１０１の暗号化部２０４が、ｃ’ｉ＝ｂ’ｉｗ１＋ｒ’２，ｉｗ２＋ｒ’３，ｉｗ３，ｃ＾’ｉ＝ｂ’ｉｗ＾１＋ｒ’２，ｉｗ＾２＋ｒ’３，ｉｗ＾３により暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ），暗号化特徴ベクトルＣ＾’＝（ｃ＾’１，ｃ＾’２，…，ｃ＾’Ｔ）を計算する。
【０１４７】
次に、ステップＳ１１０５にて、証明装置１０１の通信部２０６が、暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ），暗号化特徴ベクトルＣ＾’＝（ｃ＾’１，ｃ＾’２，…，ｃ＾’Ｔ）を認証装置１０２に送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【０１４８】
次に、ステップＳ１１０６にて、認証装置１０２の通信部２０６が、暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ），暗号化特徴ベクトルＣ＾’＝（ｃ＾’１，ｃ＾’２，…，ｃ＾’Ｔ）を受信する。
【０１４９】
次に、ステップＳ１１０７にて、認証装置１０２の暗号化類似度生成部３０２が、記憶部３０１から暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ），暗号化特徴ベクトルＣ＾＝（ｃ＾１，ｃ＾２，…，ｃ＾Ｔ）を取り出す。
このとき、一般に記憶部３０１には多数のユーザの暗号化生体情報が格納されているが、その中からどれを取り出すかについては、別途与えられるＩＤ情報を用いる。
【０１５０】
次に、ステップＳ１１０８にて、認証装置１０２の乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を６Ｔ回取り出し、｛ｓ１，ｉ，ｓ２，ｉ，ｓ３，ｉ，ｓ＾１，ｉ，ｓ＾２，ｉ，ｓ＾３，ｉ｝ｉ＝１，２，…，Ｔとする。
【０１５１】
次に、ステップＳ１１０９にて、認証装置１０２の乱数生成部２０３が、０からｑ−１までの整数から一様ランダムに値を４回取り出し、｛ｕ２，ｕ３，ｕ＾２，ｕ＾３｝とする。
【０１５２】
次に、ステップＳ１１１０にて、認証装置１０２の暗号化類似度生成部３０２が、ｄｉ＝（ｃｉ−ｃ’ｉ）＋ｓ１，ｉｗ１＋ｓ２，ｉｗ２＋ｓ３，ｉｗ３を計算する。
なお、ｗ１，ｗ２，ｗ３は、公開鍵の一部（Ｗ）として、復号装置１０３から配布されたものである。
【０１５３】
次に、ステップＳ１１１１にて、認証装置１０２の暗号化類似度生成部３０２が、ｄ＾ｉ＝（ｃ＾ｉ−ｃ＾’ｉ）＋ｓ＾１，ｉｗ＾１＋ｓ＾２，ｉｗ＾２＋ｓ＾３，ｉｗ＾３を計算する。
なお、ｗ＾１，ｗ＾２，ｗ＾３は、公開鍵の一部（Ｗ＾）として、復号装置１０３から配布されたものである。
【０１５４】
次に、ステップＳ１１１２にて、認証装置１０２の暗号化類似度生成部３０２が、数１７に従って、Ｅを計算する。
【０１５５】
【数１７】
2011052056.tif 000019
【０１５６】
次に、ステップＳ１１１３にて、認証装置１０２の暗号化類似度生成部３０２が、数１８に従って、Ｅ＾を計算する。
【０１５７】
【数１８】
2011052056.tif 000020
【０１５８】
次に、ステップＳ１１１４にて、認証装置１０２の通信部２０６が（ｄ１，…，ｄＴ，ｄ＾１，…，ｄ＾Ｔ…，Ｅ，Ｅ＾）を復号装置１０３へ送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
本実施の形態では、（ｄ１，…，ｄＴ，ｄ＾１，…，ｄ＾Ｔ…，Ｅ，Ｅ＾）が暗号化類似度情報の例となる。
【０１５９】
これ以降のステップは実施の形態１と同様であるので説明を省略する。
【０１６０】
以上の実施の形態によれば、実施の形態１と同様の効果を奏するのに加えて、類似度の指標としてハミング距離またはユークリッド二乗距離を用いることができるという効果がある。
【０１６１】
実施の形態３．
以上、実施の形態１および実施の形態２にて、岡本−高島暗号を用いて生体認証を行う方法を開示したが、次に、非特許文献２に示されたＢＧＮ（Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ）暗号を用いて生体認証を行う方法を開示する。
なお、本実施の形態に係る生体認証システムの構成例も図１に示した通りである。
また、本実施の形態に係る証明装置１０１、認証装置１０２、復号装置１０３の内部構成例も、図２−図４に示した通りである。
【０１６２】
はじめに、ＢＧＮ暗号のアルゴリズムについて説明する。
ＢＧＮ暗号は、鍵生成、暗号化、復号の３つのアルゴリズムからなる。
【０１６３】
鍵生成アルゴリズムは以下のとおりである。
ｐ、ｑをそれぞれ素数とする。
Ｎ＝ｐｑとして、Ｎを位数とする群Ｇ、ＧＴを生成する。
ｅ：Ｇ×Ｇ→ＧＴを、双線型性および非退化性を満たすペアリングとする。
ｇ、ｕをＧから一様ランダムに選んだ要素とする。
ｈ＝ｕｑによりｈを定める。
そして、公開鍵を（（Ｇ，ＧＴ，Ｎ，ｅ），ｇ，ｈ）、秘密鍵をｐとする。
【０１６４】
暗号化アルゴリズムは以下のとおりである。
なお、平文空間を｛０，１，…，Ｌ｝とする。｛０，１，…，Ｎ−１｝から一様ランダムにｒを選ぶ。
ｘに対する暗号文Ｅ（ｘ）をＥ（ｘ）＝ｇｘｈｒとする。
【０１６５】
復号アルゴリズムは以下のとおりである。
暗号文をＥ（ｘ）とすると、まず、秘密鍵ｐを用いてＥ（ｘ）ｐを計算する。
定義より、Ｅ（ｘ）ｐ＝（ｇｘｈｒ）ｐ＝（ｇｐ）ｘとなる。
そして、この値について、ｇｐを底とする離散対数を求め、元の平文ｘを得る。
【０１６６】
なお、離散対数を求める計算は現在の計算機能力では困難とされているが、平文空間の大きさＬが小さい場合には、Ｐｏｌｌａｒｄのラムダ法を用いることにより√Ｌ程度の計算量で計算できることが知られている。
【０１６７】
このようなＢＧＮ暗号を用いて、生体認証を行う方法を述べる。
本実施の形態では、実施の形態１と同様の特徴ベクトル構成法をとる場合について説明する。
すなわち、生体認証で用いる特徴ベクトルとして、特徴点の配列を用意し、ユーザがその特徴点を保有する場合に１、特徴点を保有しない場合に０を配列に格納して、配列を特徴ベクトルとし、認証時には１が一致している箇所の数を類似度の指標とするような認証方式を例に説明する。
【０１６８】
まず、図１３を用いてセットアップについて説明する。
図１３は、パラメータ生成部４０１における公開鍵及び秘密鍵の生成手順を示したフローチャートである。
【０１６９】
はじめに、ステップＳ１３０１にて、パラメータ生成部４０１が、素数ｐ，ｑ、群Ｇ，ＧＴを定める。
なお、素数はセキュリティレベルに応じて定まるが、素数ｐとｑの積を群位数とするため、通常は素因数分解ができないように素数を１０２４ビットや２０４８ビットなどの大きなサイズの素数とする。
【０１７０】
次に、ステップＳ１３０２にて、パラメータ生成部４０１が、Ｇから一様ランダムにｇ、ｕを選び、ｈ＝ｕｑを計算する。
【０１７１】
最後に、ステップＳ１３０３にて、パラメータ生成部４０１が、公開鍵ｐｋ＝（（Ｇ，ＧＴ，Ｎ，ｅ），ｇ，ｈ）を公開し、秘密鍵ｓｋ＝ｐを記憶部４０３に格納する。
【０１７２】
次に、図１４を用いて、生体情報の登録方法を説明する。
なお、ここではユーザが証明装置１０１を経由して認証装置１０２に生体情報を登録する場合について説明するが、認証装置１０２上で直接生体情報を登録する場合や、登録用の専用装置を経由して登録する場合などにおいても同様の手順により実現できる。
【０１７３】
図１４は、証明装置１０１において生体情報を登録する手順を示したフローチャートである。
【０１７４】
はじめに、ステップＳ１４０１にて、生体情報抽出部２０１がユーザの生体情報を抽出する。これには様々な方法があるが、例えば指紋に光を当てて紋様をセンサで読み取るといったことにより抽出する。
【０１７５】
次に、ステップＳ１４０２にて、特徴ベクトル形成部２０２が、生体情報から特徴ベクトルｂ＝（ｂ１，ｂ２，…，ｂＴ）を形成する。
【０１７６】
次に、ステップＳ１４０３にて、乱数生成部２０３が、０からＮ−１までの整数から一様ランダムに値をＴ回取り出し、｛ｒｉ｝ｉ＝１，２，…，Ｔとする。
【０１７７】
次に、ステップＳ１４０４にて、暗号化部２０４が、ｃｉ＝ｇｂｉｈｒｉにより暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を計算する。
なお、ｇ、ｈは公開鍵の一部として復号装置１０３から配布されたものである。
【０１７８】
次に、ステップＳ１４０５にて、通信部２０６が、暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を認証装置１０２に送信する。
【０１７９】
最後に、ステップＳ１４０６にて、認証装置１０２が、暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を記憶部３０１に格納する。
【０１８０】
次に、図１５ないし図１７を用いて、認証方法を説明する。
なお、簡単のためここでは認証時に認証の対象となるユーザが別途ＩＤ情報などによって特定されているいわゆる１：１認証の場合について説明する。
【０１８１】
図１５、図１６、図１７は、認証を行う手順を示したフローチャートである。
【０１８２】
はじめに、ステップＳ１５０１にて、証明装置１０１の生体情報抽出部２０１が、ユーザの生体情報を抽出する。
抽出方法は生体情報の登録時と同様である。
【０１８３】
次に、ステップＳ１５０２にて、証明装置１０１の特徴ベクトル形成部２０２が、生体情報から特徴ベクトルｂ’＝（ｂ’１，ｂ’２，…，ｂ’Ｔ）を形成する。
形成方法は、生体情報の登録時と同様である。
【０１８４】
次に、ステップＳ１５０３にて、証明装置１０１の乱数生成部２０３が、０からＮ−１までの整数から一様ランダムに値をＴ回取り出し、｛ｒ’ｉ｝ｉ＝１，２，…，Ｔとする。
【０１８５】
次に、ステップＳ１５０４にて、証明装置１０１の暗号化部２０４が、ｃ’ｉ＝ｇｂ’ｉｈｒ’ｉにより暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ）を計算する。
【０１８６】
次に、ステップＳ１５０５にて、証明装置１０１の通信部２０６が、暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ）を認証装置１０２に送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【０１８７】
次に、ステップＳ１５０６にて、認証装置１０２の通信部２０６が、暗号化特徴ベクトルＣ’＝（ｃ’１，ｃ’２，…，ｃ’Ｔ）を受信する。
【０１８８】
次に、ステップＳ１５０７にて、認証装置１０２の暗号化類似度生成部３０２が、記憶部３０１から暗号化特徴ベクトルＣ＝（ｃ１，ｃ２，…，ｃＴ）を取り出す。
【０１８９】
次に、ステップＳ１５０８にて、認証装置１０２の乱数生成部３０５が、０からＮ−１までの整数から一様ランダムに値を取り出し、ｓとする。
【０１９０】
次に、ステップＳ１５０９にて、認証装置１０２の暗号化類似度生成部３０２が、数１９に従って、Ｅを計算する。
【０１９１】
【数１９】
2011052056.tif 000021
【０１９２】
次に、ステップＳ１５１０にて、認証装置１０２の通信部３０４が、Ｅを復号装置１０３へ送信する。
その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
本実施の形態では、Ｅが暗号化類似度情報となる。
【０１９３】
次に、ステップＳ１５１１にて、復号装置１０３の通信部４０４が、Ｅを受信する。
【０１９４】
次に、ステップＳ１５１２にて、復号装置１０３の復号部４０２が、記憶部４０３から秘密鍵ｐを取り出す。
【０１９５】
次に、ステップＳ１５１３にて、復号装置１０３の復号部４０２が、Ｚ＝Ｅｐを計算する。
次に、ステップＳ１５１４にて、復号装置１０３の復号部４０２が、ｅ（ｇ，ｇ）ｐを底とするＺの離散対数ｄを計算する。
本実施の形態でも、この離散対数ｄが類似度に相当する。
【０１９６】
次に、ステップＳ１５１５にて、復号装置１０３の通信部４０４がｄを認証装置１０２へ送信する。その際、例えばＳＳＬなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。
【０１９７】
次に、ステップＳ１５１６にて、認証装置１０２の通信部３０４が、類似度ｄを受信する。
【０１９８】
次に、ステップＳ１５１７にて、判定部３０３が、類似度ｄがしきい値以上かを判定する。
このしきい値は、利用する生体情報の種類や安全性要件などさまざまな要素を勘案してあらかじめシステムで決められた値である。
しきい値以上であれば、証明装置１０１から送られてきた暗号化生体情報はＩＤで指定された本人のものであると判断する。
一方、しきい値未満であれば、証明装置１０１から送られてきた暗号化生体情報はＩＤで指定された人物のものではなく、他人のものであると判断する。
【０１９９】
以上のステップにより、認証装置１０２は証明装置１０１との間で生体認証を行うことができる。
【０２００】
以上の実施の形態によれば、実施の形態１と同様の効果を奏するのに加えて、実施の形態１に比べて公開鍵、秘密鍵の数を低減できるという効果がある。
【０２０１】
また、実施の形態１に比べて復号装置１０３に送付する暗号文の数を低減できるという効果がある。
【０２０２】
実施の形態４．
以上の実施の形態３では、特徴ベクトルの内積を計算し、その値により生体認証を行うという認証方法を開示したが、次に、特徴ベクトルのハミング距離またはユークリッド二乗距離により生体認証を行うという認証方法を述べる。
なお、本実施の形態に係る生体認証システムの構成例も図１に示した通りである。
また、本実施の形態に係る証明装置１０１、認証装置１０２、復号装置１０３の内部構成例も、図２−図４に示した通りである。
【０２０３】
本実施の形態におけるパラメータ生成方法と生体情報の登録方法は実施の形態３と同様であるので説明を省略する。
【０２０４】
次に、図１８、図１９、図２０を用いて、認証方法を説明する。
なお、簡単のためここでは認証時に認証の対象となるユーザが別途ＩＤ情報などによって特定されているいわゆる１：１認証の場合について説明する。
【０２０５】
ステップＳ１８０１からＳ１８０８までは実施の形態３と同様であるので説明を省略する。
【０２０６】
ステップＳ１８０９にて、認証装置１０２の暗号化類似度生成部３０２が、数２０に従って、Ｅを計算する。
【０２０７】
【数２０】
2011052056.tif 000022
【０２０８】
これ以降のステップは実施の形態３と同様であるので説明を省略する。
【０２０９】
以上の実施の形態によれば、実施の形態２と同様の効果を奏する上に、実施の形態３と同様の効果を奏する。
【０２１０】
以上、実施の形態１から実施の形態４にわたって、二重準同型暗号を用いた生体認証方法を開示したが、これは生体認証に限らず、パターンマッチング分野に応用できることは明らかである。
すなわち、実施の形態１−４に示した認証方法によれば、データを暗号化したままでデータの類似度判定ができる。
したがって、データを暗号化したままでの画像検索、動画検索、音声検索などが可能となる。
【０２１１】
以上の実施の形態１−４では、生体認証と二重準同型暗号とを用いることで、生体情報を暗号化したままで生体認証を実現したことを説明した。
つまり、従来は、通常の準同型暗号を使っていたので、すべてを暗号化したままで認証処理を行うことができなかった。そのため認証処理においてユーザと認証装置との間の通信量が大きくなってしまうという課題がある。
二重準同型暗号を用いることで、すべてを暗号化したままで認証処理を行うことができるようになる。そのためユーザと認証装置との間の通信量を低減させることができるという効果が生まれる。
また、この生体認証と二重準同型暗号との組合せにより、安全でかつ通信量効率の高い生体認証が実現できるという効果が生まれる。
【０２１２】
最後に、実施の形態１−４に示した証明装置１０１、認証装置１０２、復号装置１０３のハードウェア構成例について説明する。
図２５は、実施の形態１−４に示す証明装置１０１、認証装置１０２、復号装置１０３のハードウェア資源の一例を示す図である。
なお、図２５の構成は、あくまでも証明装置１０１、認証装置１０２、復号装置１０３のハードウェア構成の一例を示すものであり、証明装置１０１、認証装置１０２、復号装置１０３のハードウェア構成は図２５に記載の構成に限らず、他の構成であってもよい。
【０２１３】
図２５において、証明装置１０１、認証装置１０２、復号装置１０３は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６と接続していてもよい。また、証明装置１０１は、生体情報を読み取るための読取り装置９０７と接続されている。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
実施の形態１−４で説明した「記憶部」は、ＲＡＭ９１４、磁気ディスク装置９２０等により実現される。
通信ボード９１５、キーボード９０２、マウス９０３、読取り装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【０２１４】
通信ボード９１５は、他の装置と接続されている以外に、例えば、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）、ＳＡＮ（ストレージエリアネットワーク）などに接続されていても構わない。
【０２１５】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【０２１６】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【０２１７】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
証明装置１０１、認証装置１０２、復号装置１０３の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【０２１８】
上記プログラム群９２３には、実施の形態１−４の説明において「〜部」（「記憶部」以外、以下も同様）として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【０２１９】
ファイル群９２４には、実施の形態１−４の説明において、「〜の判断」、「〜の判定」、「〜の計算」、「〜の比較」、「〜の導出」、「〜の抽出」、「〜の形成」、「〜の更新」、「〜の設定」、「〜の登録」、「〜の選択」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１−４で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０２２０】
また、実施の形態１−４の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、実施の形態１−４の「〜部」としてコンピュータを機能させるものである。あるいは、実施の形態１−４の「〜部」の手順や方法をコンピュータに実行させるものである。
【０２２１】
このように、実施の形態１−４に示す証明装置１０１、認証装置１０２、復号装置１０３は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【０２２２】
１０１  証明装置、１０２  認証装置、１０３  復号装置、２０１  生体情報抽出部、２０２  特徴ベクトル形成部、２０３  乱数生成部、２０４  暗号化部、２０５  記憶部、２０６  通信部、３０１  記憶部、３０２  暗号化類似度生成部、３０３  判定部、３０４  通信部、３０５  乱数生成部、４０１  パラメータ生成部、４０２  復号部、４０３  記憶部、４０４  通信部。
【図１】
2011052056.tif 000023
【図２】
2011052056.tif 000024
【図３】
2011052056.tif 000025
【図４】
2011052056.tif 000026
【図５】
2011052056.tif 000027
【図６】
2011052056.tif 000028
【図７】
2011052056.tif 000029
【図８】
2011052056.tif 000030
【図９】
2011052056.tif 000031
【図１０】
2011052056.tif 000032
【図１１】
2011052056.tif 000033
【図１２】
2011052056.tif 000034
【図１３】
2011052056.tif 000035
【図１４】
2011052056.tif 000036
【図１５】
2011052056.tif 000037
【図１６】
2011052056.tif 000038
【図１７】
2011052056.tif 000039
【図１８】
2011052056.tif 000040
【図１９】
2011052056.tif 000041
【図２０】
2011052056.tif 000042
【図２１】
2011052056.tif 000043
【図２２】
2011052056.tif 000044
【図２３】
2011052056.tif 000045
【図２４】
2011052056.tif 000046
【図２５】
2011052056.tif 000047
【国際調査報告】
2011052056.tif 000048
2011052056.tif 000049
2011052056.tif 000050
2011052056.tif 000051