"二重準同型暗号アルゴリズムに基づいて生成された公開鍵を記憶する公開鍵記憶部と、前記公開鍵を用いて暗号化された第1データを暗号化第1データとして記憶する暗号化データ記憶部と、前記公開鍵の少なくとも一部を用いて、乱数を生成する乱数生成部と、前記乱数生成部により生成された乱数を用いた演算を行って、前記暗号化第1データを更新する暗号化データ更新部とを有することを特徴とするデータ処理装置。前記データ処理装置は、更に、前記乱数生成部により生成された乱数を用いた演算を行って、前記公開鍵を更新する公開鍵更新部を有することを特徴とする請求項1に記載のデータ処理装置。前記乱数生成部は、所定のトリガイベントが発生する度に、トリガイベント発生の際に前記公開鍵記憶部に記憶されている公開鍵の少なくとも一部を用いて、乱数を生成し、前記公開鍵更新部は、前記乱数生成部により乱数が生成される度に、前記乱数生成部により生成された乱数を用いた演算を行って、トリガイベント発生の際に前記公開鍵記憶部に記憶されている公開鍵を更新し、前記暗号化データ更新部は、前記乱数生成部により乱数が生成される度に、前記乱数生成部により生成された乱数を用いた演算を行って、トリガイベント発生の際に前記暗号化データ記憶部に記憶されている暗号化第1データを更新し、前記公開鍵記憶部は、前記公開鍵更新部により公開鍵が更新される度に、更新後の公開鍵を更新前の公開鍵に上書きして記憶し、前記暗号化データ記憶部は、前記暗号化データ更新部により暗号化第1データが更新される度に、更新後の暗号化第1データを更新前の暗号化第1データに上書きして記憶することを特徴とする請求項2に記載のデータ処理装置。前記データ処理装置は、更に、第2のデータを公開鍵を用いて暗号化する暗号装置から、前記第2のデータの暗号化に用いる公開鍵の供給を要求する公開鍵供給要求を入力する公開鍵供給要求入力部を有し、前記乱数生成部は、前記公開鍵供給要求入力部が前記暗号装置から公開鍵供給要求を入力した際に前記トリガイベントが発生したと判断し、前記公開鍵供給要求入力部が前記暗号装置から公開鍵供給要求を入力する度に、前記公開鍵記憶部に記憶されている公開鍵の少なくとも一部を用いて、乱数を生成し、前記公開鍵更新部は、前記乱数生成部により乱数が生成される度に、前記乱数生成部により生成された乱数を用いた演算を行って、前記公開鍵記憶部に記憶されている公開鍵を更新し、前記暗号化データ更新部は、前記乱数生成部により乱数が生成される度に、前記乱数生成部により生成された乱数を用いた演算を行って、前記暗号化データ記憶部に記憶されている暗号化第1データを更新し、前記公開鍵供給要求入力部は、前記公開鍵更新部による更新後の公開鍵を、前記暗号装置における前記第2のデータの暗号化に用いられる公開鍵として、前記暗号装置に出力することを特徴とする請求項3に記載のデータ処理装置。前記データ処理装置は、更に、前記暗号装置が、前記公開鍵供給要求入力部から出力された更新後の公開鍵を用いて前記第2のデータを暗号化して生成した暗号化第2データを入力する暗号化データ入力部と、前記暗号化データ記憶部に記憶されている暗号化第1データと前記暗号化第2データに対して前記公開鍵記憶部に記憶されている公開鍵を用いた演算を行って、前記暗号化第1データと前記暗号化第2データがそれぞれ暗号化された状態のままで、前記公開鍵に対応付けられている秘密鍵を用いた復号処理により前記第1データと前記第2データとの間の類似度を導出可能な暗号化された情報を暗号化類似度情報として生成する暗号化類似度生成部とを有することを特徴とする請求項4に記載のデータ処理装置。前記暗号化データ記憶部は、前記第1データを構成するTTは2以上の整数個の部分データが前記暗号装置により暗号化されて得られたT個の暗号化された部分データで構成される暗号化第1データを記憶し、前記暗号化データ入力部は、前記第2データを構成するTTは2以上の整数個の部分データが前記暗号装置により暗号化されて得られたT個の暗号化された部分データで構成される暗号化第2データを入力し、前記暗号化類似度生成部は、部分データごとに、前記暗号化第1データと前記暗号化第2データに対して前記公開鍵記憶部に記憶されている公開鍵を用いた演算を行って、前記第1データと前記第2データとの間の類似度として、前記第1データのT個の部分データと前記第2データのT個の部分データにおけるハミング距離を導出可能な情報を生成することを特徴とする請求項5に記載のデータ処理装置。前記暗号化データ記憶部は、前記第1データを構成するTTは2以上の整数個の部分データが前記暗号装置により暗号化されて得られたT個の暗号化された部分データで構成される暗号化第1データを記憶し、前記暗号化データ入力部は、前記第2データを構成するTTは2以上の整数個の部分データが前記暗号装置により暗号化されて得られたT個の暗号化された部分データで構成される暗号化第2データを入力し、前記暗号化類似度生成部は、部分データごとに、前記暗号化第1データと前記暗号化第2データに対して前記公開鍵記憶部に記憶されている公開鍵を用いた演算を行って、前記第1データと前記第2データとの間の類似度として、前記第1データのT個の部分データと前記第2データのT個の部分データにおけるユークリッド二乗距離を導出可能な情報を生成することを特徴とする請求項5に記載のデータ処理装置。前記暗号化データ更新部は、前記暗号化第1データを更新した後に、更新に用いた乱数を消去することを特徴とする請求項1に記載のデータ処理装置。前記公開鍵記憶部は、前記二重準同型暗号アルゴリズムに基づいて生成された公開鍵として、岡本-高島暗号アルゴリズムに基づいて生成された公開鍵を記憶し、前記暗号化データ記憶部は、前記岡本-高島暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第1データを記憶することを特徴とする請求項1に記載のデータ処理装置。前記公開鍵記憶部は、前記二重準同型暗号アルゴリズムに基づいて生成された公開鍵として、BGNBoneh-Goh-Nissim暗号アルゴリズムに基づいて生成された公開鍵を記憶し、前記暗号化データ記憶部は、前記BGN暗号アルゴリズムに基づいて生成された公開鍵による暗号化で得られた暗号化第1データを記憶することを特徴とする請求項1に記載のデータ処理装置。コンピュータが、二重準同型暗号アルゴリズムに基づいて生成された公開鍵を記憶し、前記公開鍵を用いて暗号化された第1データを暗号化第1データとして記憶し、前記公開鍵の少なくとも一部を用いて、乱数を生成し、生成した乱数を用いた演算を行って、前記暗号化第1データを更新することを特徴とするデータ処理方法。二重準同型暗号アルゴリズムに基づいて生成された公開鍵を記憶する公開鍵記憶処理と、前記公開鍵を用いて暗号化された第1データを暗号化第1データとして記憶する暗号化データ記憶処理と、前記公開鍵の少なくとも一部を用いて、乱数を生成する乱数生成処理と、前記乱数生成処理により生成された乱数を用いた演算を行って、前記暗号化第1データを更新する暗号化データ更新処理とをコンピュータに実行させることを特徴とするプログラム。特許文献1にて本願出願人は、特徴ベクトルを利用する照合方式を対象として、岡本-高島準同型暗号非特許文献2やBGNBoneh-Goh-Nissim暗号非特許文献3などの二重準同型暗号を用いて秘匿照合を実現する方法を開示した。検証者側に保存される暗号化テンプレートが漏洩した場合に備えるために、暗号化テンプレートを安全に更新することが必要であるが、特許文献1では暗号化テンプレートの更新の方法については開示していなかった。また、非特許文献1では、同じく特徴ベクトルを利用する照合方式を対象として、岡本-高島準同型暗号やBGN暗号などの二重準同型暗号を用いて秘匿照合を実現し、さらにチャレンジレスポンスの考え方を応用した手法を導入することにより、リプレイ攻撃を防ぐ方法が開示されている。しかしながら、やはりテンプレートを安全に更新するための方法については開示されていなかった。一方、特許文献2では、画像を利用する照合方式に対して、テンプレートを安全に更新するための方法が開示されている。しかしながら、情報の秘匿方法が画像に特化したものとなっているため、画像を利用する照合方式にしか適用できないという課題があった。本発明は、これらの点に鑑みたものであり、二重準同型暗号アルゴリズムに基づいて生成され、認証に用いられる暗号化データテンプレートを安全に更新することを主な目的とする。本発明に係るデータ処理装置は、二重準同型暗号アルゴリズムに基づいて生成された公開鍵を記憶する公開鍵記憶部と、前記公開鍵を用いて暗号化された第1データを暗号化第1データとして記憶する暗号化データ記憶部と、前記公開鍵の少なくとも一部を用いて、乱数を生成する乱数生成部と、前記乱数生成部により生成された乱数を用いた演算を行って、前記暗号化第1データを更新する暗号化データ更新部とを有することを特徴とする。本発明によれば、暗号化データを更新することができるため、暗号化データが漏洩した場合でも、漏洩した暗号化データを用いたなりすましに対して有効に対抗することができ、セキュリティ強度を向上させることができる。本明細書では、特徴ベクトルを利用する照合方式に関して、テンプレートを安全に更新する方法を開示する。さらに、本明細書では、上記のテンプレートを安全に更新する方法を応用してリプレイ攻撃を防ぐ方法を開示する。本明細書では、基本的に、本願出願人が開示した特許文献1のデータ処理装置において、テンプレートを安全に更新する方法を新たに開示するものであり、特許文献1の実施の形態2および4に記載されている特徴ベクトルのハミング距離またはユークリッド二乗距離により生体認証を行う認証方法について適用できるものである。そこで本明細書では、実施の形態1にて特許文献1の実施の形態2に記載の方式におけるテンプレートの更新方法を説明し、実施の形態2にて特許文献1の実施の形態4に記載の方式におけるテンプレートの更新方法を説明する。その上で、テンプレート更新の応用であるリプレイ攻撃対策を実施する方法について、本明細書の実施の形態3と4で説明する。また、実施の形態1及び実施の形態3の補足説明として、実施の形態1及び実施の形態3の方法の前提となる特許文献1の実施の形態2に記載の認証方法の要旨を、実施の形態5として示す。また、実施の形態2及び実施の形態4の補足説明として、実施の形態2及び実施の形態4の方法の前提となる特許文献1の実施の形態4に記載の認証方法の要旨を、実施の形態6として示す。ここで、非特許文献1の岡本-高島暗号のアルゴリズムを、本明細書の実施の形態1および3に必要となる範囲に限って説明する。岡本-高島暗号は、楕円曲線を用いて定義される双対ペアリングベクトル空間を用いた二重準同型暗号である。この双対ペアリングベクトル空間を構成する方法は複数考えられるが、ここでは楕円曲線の直積により構成する方法に基づいて説明する。なお、楕円曲線上の群の演算は一般に加法群の演算として記述されることが多いが、ここでは有限体上の演算も含めすべて乗法群として記述する。また、非対称ペアリングを用いたより一般的な方式に従って記述する。G、G^、GTをそれぞれ素数位数qの群とする。Fq={0,1,...,q-1}とする。e:G×G^→GTを、双線型性任意のu∈G,v^∈G^,a,b∈Fqに対してeua,v^b=eu,v^abとなる性質および非退化性eg,g^≠1であるようなg∈G,g^∈G^が存在する性質を満たすペアリングとする。N個の群Gの直積集合をV=G×G×...×G、同じくN個の群G^の直積集合をV^=G^×G^×...×G^とする。このとき、数1に示す関係が成り立つ。2つのベクトル空間V,V^のペアリングとして、u=u1,u2,...,uN∈V,v^=v^1,v^2,...,v^N∈V^に対するペアリングを、数2のように定義する。ベクトル空間V,V^において、数3に示す関係が成り立つ。x=x1a1x2a2...xNaN∈Vとする。ベクトル空間Vにおけるディストーション写像φi,j:V→Vを、φi,jx=xjaiと定義する。同様に、x^=x1a^1x2a^2...xNa^N∈V^に対し、φ^i,j:V^→V^を、φ^i,jx^=xja^iと定義する。このようなディストーション写像は容易に計算可能である。このように、標準基底があり、空間同士のペアリングが定義され、計算可能なディストーション写像が定義された2つのベクトル空間を双対ペアリングベクトル空間という。X=Xi,j,X^=X^i,jを、各要素がFqから一様ランダムに選ばれた値で構成されるN行N列の正方行列とする。このように構成したX,X^はきわめて高い確率で正則行列となる。このような正則行列を用いて、数4に示すように定義すると、W=w1,w2,...,wN,W^=w^1,w^2,...,w^Nもまた基底となる。この基底をランダム基底と呼ぶ。非特許文献2によれば、ベクトル空間V,V^におけるランダム基底W=w1,w2,...,wN,W^=w^1,w^2,...,w^Nに関して、以下の性質が成り立つ。FNqの要素x1,x2,...,xNが与えられたとき、x=x1w1x2w2...xNwN,x^=x1w^1x2w^2...xNw^Nを得ることは容易である。しかし、x=x1w1x2w2...xLwL,x^=x1w^1x2w^2...xLw^L1<L≦Nが与えられたときに、X=Xi,j,X^=X^i,jを用いずしてベクトルy=x1w1x2w2...xlwl,y^=x1w^1x2w^2...xlw^l1≦l<Lを得ることは、一般化されたDiffie-Hellman計算問題と同程度に難しいことが知られている。一方で、X=Xi,j,X^=X^i,jを用いるならば、以下のアルゴリズムDeco数5により上記のようなベクトル分解が容易に計算可能である。なお、数5中のkは整数である。この性質から、正則行列を秘密鍵とすることによりトラップドア関数が実現できる。以下、双対ペアリングベクトル空間を用いたデータ処理装置において、テンプレートを安全に更新する方法を説明する。実施の形態1.本実施の形態では、上述の岡本-高島準同型暗号を用いて特徴ベクトルを暗号化し、特徴ベクトルのハミング距離またはユークリッド二乗距離に基づいて生体認証を行うデータ処理装置において、テンプレートを安全に更新する方法を説明する。図1は、実施の形態1-4に係る生体認証システムの構成例を示す図である。図1において、証明装置101はユーザから生体情報を測定し、測定した生体情報を用いて秘匿照合処理を行う装置である。認証装置102は、ユーザの生体情報を暗号化して格納しておくとともに、格納した暗号化された生体情報を用いて認証を行う装置である。復号装置103は、暗号化類似度情報を復号する装置である。なお、証明装置101は暗号装置の例であり、認証装置はデータ処理装置の例である。図2は証明装置101の内部構成の構成例を示す図である。図2において、生体情報抽出部201は、光学カメラ、赤外線カメラなどの各種センサを用いて、個人識別を行うのに必要となる情報を生体から抽出する。特徴ベクトル形成部202は、生体情報抽出部201で抽出された生体情報から、個人の特徴を表す特徴ベクトルを形成する。乱数生成部203は、乱数を生成する。暗号化部204は、特徴ベクトルを暗号化する。記憶部205は、公開鍵などの各種データを格納する。通信部206は、データベースなど他の装置との間でデータの送受信を行う。図3は認証装置102の内部構成の構成例を示す図である。図3において、記憶部301は、暗号化された特徴ベクトル以下、暗号化特徴ベクトルともいうや公開鍵などの各種データを格納する。記憶部301が記憶する暗号化特徴ベクトルは、証明装置101により暗号化された登録用の特徴ベクトルであり、認証時にテンプレートとして用いられる。本明細書では、暗号化特徴ベクトルは、テンプレート、暗号化生体情報とも表記する。なお、暗号化前の登録用の特徴ベクトル暗号化前の登録用の生体情報が第1データの例に相当し、記憶部301が記憶する暗号化特徴ベクトルテンプレート、暗号化生体情報が暗号化第1データの例に相当する。また、後述するように、テンプレート更新部307により暗号化特徴ベクトルが更新された場合には、記憶部301は、既存の暗号化特徴ベクトル証明装置101から取得した暗号化特徴ベクトル又は前回の更新により得られた暗号化特徴ベクトルに上書きして、更新された暗号化特徴ベクトルを記憶する。また、記憶部301が記憶する公開鍵は、復号装置103で生成され、復号装置103から配布された公開鍵である。また、後述するように、公開鍵更新部306により公開鍵が更新された場合は、既存の公開鍵復号装置103から取得した公開鍵又は前回の更新により得られた公開鍵に上書きして、更新された公開鍵を記憶する。なお、記憶部301は、暗号化データ記憶部及び公開鍵記憶部の例に相当する。暗号化類似度生成部302は、登録されている暗号化特徴ベクトルと、認証用の暗号化特徴ベクトルから、暗号化類似度情報を生成する。認証用の暗号化特徴ベクトルは、証明装置101により暗号化された認証用の特徴ベクトルである。暗号化前の認証用の特徴ベクトルが第2データの例に相当し、認証用の暗号化特徴ベクトルが暗号化第2データの例に相当する。また、暗号化類似度情報は、公開鍵に対応付けられている秘密鍵を用いた復号処理により登録用の特徴ベクトル第1データと認証用の特徴ベクトル第2データとの間の類似度を復号装置103において導出可能な暗号化された情報である。なお、暗号化類似度生成部302の詳細は、後述の実施の形態5及び6で説明する。判定部303は、類似度から個人識別を行い、本人か否かを判定する。通信部304は、証明装置101や復号装置103との間でデータの送受信を行う。例えば、通信部304は、認証時に、証明装置101から認証用の暗号化特徴ベクトルを受信する。前述のように、暗号化特徴ベクトルが暗号化第2データの例に相当するため、通信部304は暗号化データ入力部の例に相当する。また、通信部304は、後述の実施の形態3及び4に示すように、証明装置101から認証要求を受信する場合がある。認証要求は、例えば、ユーザの認証が必要になった際に証明装置101から認証装置102に送信される。例えば、証明装置101が銀行のATMに付設されている場合には、銀行の顧客がATMの利用を開始する際に、証明装置101から認証装置102に送信される。後述するように、証明装置101から認証要求があった場合に、認証装置102では公開鍵更新部306により公開鍵が更新され、更新された公開鍵が証明装置101に送信される。この意味で、認証要求は公開鍵の供給を要求するものであり、認証要求は公開鍵供給要求の例に相当する。このため、通信部304は公開鍵供給要求入力部の例でもある。乱数生成部305は、乱数を生成する。より具体的には、乱数生成部305は、所定のトリガイベントが発生する度に、トリガイベント発生の際に記憶部301に記憶されている公開鍵の少なくとも一部を用いて、乱数を生成する。例えば、証明装置101からの認証要求の受信や、公開鍵及び暗号化特徴ベクトルの周期的な更新タイミングの到来等をトリガイベントとすることが考えられる。また、システム管理者が、認証装置102に公開鍵や暗号化特徴ベクトルの更新を指示したことをトリガイベントの発生としてもよい。公開鍵更新部306は、乱数生成部305により乱数が生成される度に、乱数生成部305により生成された乱数を用いた演算を行って、トリガイベント発生の際に記憶部301に記憶されている公開鍵を更新する。テンプレート更新部307は、乱数生成部305により乱数が生成される度に、乱数生成部305により生成された乱数を用いた演算を行って、トリガイベント発生の際に記憶部301に記憶されているテンプレート暗号化第1データを更新する。テンプレート更新部307は、暗号化データ更新部の例に相当する。図4は復号装置103の内部構成の構成例を示す図である。図4において、パラメータ生成部401は、公開鍵や秘密鍵など、暗号化と復号に必要なパラメータを生成する。復号部402は、暗号化類似度情報を復号し、平文の類似度を取り出す。記憶部403は、公開鍵や秘密鍵などの各種データを格納する。通信部404は、データベースなど他の装置との間でデータの送受信を行う。次に、本実施の形態に係るデータ処理方法を説明する。まず、動作の全体像を説明する。動作は、セットアップ処理、登録処理、認証処理、テンプレート更新処理の4つに分かれる。セットアップ処理では、復号装置103が、暗号化と復号に必要となるパラメータを生成する。登録処理では、証明装置101がユーザの生体情報を暗号化して認証装置102に送付し、認証装置102が記憶部301に格納する。認証処理では、まず証明装置101がユーザの生体情報を暗号化して認証用の暗号化生体情報を認証装置102に送付する。次に、認証装置102が、記憶部301の暗号化生体情報テンプレートと受領した暗号化生体情報を用いて暗号化類似度情報を生成し、暗号化類似度情報を復号装置103に送付する。次に、復号装置103が類似度を復号し、認証装置102に復号された類似度を送付する。最後に認証装置102が類似度としきい値とを比較し、認証をする。テンプレート更新処理では、認証装置102が公開鍵とテンプレートを更新し、新しい公開鍵を公開する。なお本明細書では、セットアップ処理、登録処理、認証処理については記号も含めて特許文献1に記載のとおりである。セットアップ処理、登録処理、認証処理の詳細は実施の形態5において説明し、実施の形態1では、テンプレートの更新処理についてのみ説明する。図5を用いて、テンプレートの更新処理について詳細に説明する。図5は、テンプレートの更新手順を示したフローチャートである。トリガイベントが発生した場合に、はじめに、ステップS501にて、乱数生成部305が、0からq-1までの整数から一様ランダムに値δを取り出す。値δは、乱数値である。また、上記の一様とは、0からq-1の各値の出現確率が同一であることを意味する。ここで、上記のqは群位数である。実施の形態5において説明する図9のS906に示すように、公開鍵pk=q、V、V^、e、GT、A、A^、W、W^、eg,g^であり、群位数qは公開鍵pkの一部構成要素である。つまり、乱数生成部305は、公開鍵pkの一部を用いて乱数を生成する。次に、ステップS502にて、公開鍵更新部306が、既存の公開鍵パラメータeg,g^とランダム基底W=w1、w2、w3、W^=w^1、w^2、w^3と乱数値δとを用いて、新たな公開鍵パラメータeg,g^=eδg,δg^、ランダム基底W=δw1、δw2、δw3、W^=δw^1、δw^2、δw^3を定める。前述したように、公開鍵pk=q、V、V^、e、GT、A、A^、W、W^、eg,g^であり、公開鍵パラメータeg,g^とランダム基底W及びW^は、公開鍵pkの一部である。このように、既存の公開鍵パラメータeg,g^とランダム基底W及びW^から新たな公開鍵パラメータeg,g^とランダム基底W及びW^に更新することは、既存の公開鍵pkから新たな公開鍵pkに更新することと同義である。次に、ステップS503にて、テンプレート更新部307が、既存のテンプレートC=c1,c2,...,cTと乱数値δとを用いて、新たなテンプレートC=δc1,δc2,...,δcTを計算する。そして、記憶部301は、既存のテンプレートCに上書きして、新たなテンプレートCを記憶する。また、このとき、記憶部301は、公開鍵パラメータeg,g^とランダム基底W及びW^に上書きして、公開鍵更新部306により生成された新たな公開鍵パラメータeg,g^とランダム基底W及びW^を記憶する。新たな公開鍵パラメータeg,g^とランダム基底W及びW^を記憶することは、既存の公開鍵pkを上書きして新たな公開鍵pkを記憶することに相当する。次に、ステップS504にて、テンプレート更新部307が、乱数値δを消去する。最後に、ステップS505にて、新たな公開鍵パラメータeg,g^とランダム基底W=δw1、δw2、δw3、W^=δw^1、δw^2、δw^3を公開する。ステップS505は、例えば、通信部304が新たな公開鍵パラメータeg,g^とランダム基底W及びW^を証明装置101及び復号装置103に送信することにより実現される。証明装置101及び復号装置103では、新たな公開鍵パラメータeg,g^とランダム基底W及びW^を用いて新たな公開鍵pkを生成することができ、新たな公開鍵パラメータeg,g^とランダム基底W及びW^を送信することは、新たな公開鍵pkを送信することと同義である。なお、通信部304は、新たな公開鍵パラメータeg,g^とランダム基底W及びW^を送信する代わりに、証明装置101及び復号装置103に、新たな公開鍵pkを送信するようにしてもよい。また、通信部304による送信に代えて、可搬記憶媒体に新たな公開鍵パラメータeg,g^とランダム基底W及びW^又は、新たな公開鍵pkを格納して、証明装置101及び復号装置103に当該可搬記憶媒体から新たな公開鍵パラメータeg,g^とランダム基底W及びW^又は、新たな公開鍵pkを読み込ませてもよい。以降は、新たな公開鍵pkと新たなテンプレートCを用いて、特許文献1の実施の形態2つまり、本明細書の実施の形態5に示す手順に従った認証処理が行われる。すなわち、まず証明装置101がユーザの生体情報を新たな公開鍵pkを用いて暗号化して認証用の暗号化生体情報を認証装置102に送付する。次に、認証装置102が、記憶部301の暗号化生体情報新たなテンプレートCと受領した暗号化生体情報と記憶部301の新たな公開鍵pkとを用いて暗号化類似度情報を生成し、暗号化類似度情報を復号装置103に送付する。次に、復号装置103が秘密鍵skと新たな公開鍵pkを用いて類似度を復号し、認証装置102に復号された類似度を送付する。最後に認証装置102が類似度としきい値とを比較し、認証をする。なお、図5に示す手順にて公開鍵とテンプレートが更新されても、秘密鍵skは更新されない。アルゴリズムの性質上、秘密鍵skが更新されなくても、復号装置103は類似度の復号を行うことができる。以上の手順によりテンプレートと公開鍵とを更新すれば、仮に旧テンプレートが漏洩したとしても、旧テンプレートを用いて認証装置102になりすますことはできない。なぜならば、すでに公開鍵の一部である公開鍵パラメータとランダム基底が新たな公開鍵パラメータeg,g^とランダム基底W=δw1、δw2、δw3、W^=δw^1、δw^2、δw^3に置きかわっており、復号装置103での復号処理にもこの新たな公開鍵パラメータとランダム基底が用いられるため、新たな公開鍵パラメータとランダム基底と旧テンプレートとの間で齟齬が生じてしまい、この齟齬がハミング距離やユークリッド二乗距離の復号結果に反映して、乱数値δに応じたランダムな値になるからである。また、以上の手順によりテンプレートと公開鍵とを更新すれば、旧テンプレートと新公開鍵パラメータとランダム基底を入手したとしても、新テンプレートを計算することはできない。なぜならば、この計算問題が計算量理論の分野において計算困難な問題の一つとされている計算Diffie-Hellman問題に帰着されるからである。以上、実施の形態1を説明した。この実施の形態1によれば、岡本-高島準同型暗号を用いたデータ処理装置において、テンプレートを安全に更新することができるという効果がある。このため、テンプレートが漏洩した場合でも、漏洩したテンプレートを用いたなりすましに対して有効に対抗することができ、セキュリティ強度を向上させることができる。また、この実施の形態1によれば、岡本-高島準同型暗号を用いているので、BGN暗号を用いる場合に比べて群のサイズを小さくすることができ、演算を高速にすることができるという効果がある。実施の形態2.本実施の形態では、非特許文献3に示されたBGNBoneh-Goh-Nissim暗号を用いたデータ処理装置において、テンプレートを安全に更新する方法を説明する。なお、本実施の形態に係る生体認証システムの構成例も図1に示した通りである。また、本実施の形態に係る証明装置101、認証装置102、復号装置103の内部構成例も、図2-図4に示した通りである。はじめに、BGN暗号のアルゴリズムについて説明する。BGN暗号も二重準同型暗号の一つである。BGN暗号は、鍵生成、暗号化、復号の3つのアルゴリズムからなる。鍵生成アルゴリズムは以下のとおりである。p、qをそれぞれ素数とする。N=pqとして、Nを位数とする群G、GTを生成する。e:G×G→GTを、双線型性および非退化性を満たすペアリングとする。g、uをGから一様ランダムに選んだ要素とする。h=uqによりhを定める。そして、公開鍵をG,GT,N,e、g、h、eg,g、秘密鍵をpとする。暗号化アルゴリズムは以下のとおりである。なお、平文空間を{0、1、...、L}とする。{0、1、...、N-1}から一様ランダムにrを選ぶ。xに対する暗号文ExをEx=gxhrとする。復号アルゴリズムは以下のとおりである。暗号文をExとすると、まず、秘密鍵pを用いてExpを計算する。定義より、Exp=gxhrp=gpxとなる。そして、この値について、gpを底とする離散対数を求め、元の平文xを得る。なお、gは、公開鍵の一部として、復号装置103から配布されたものである。なお、離散対数を求める計算は現在の計算機能力では困難とされているが、平文空間の大きさLが小さい場合には、Pollardのラムダ法を用いることにより√L程度の計算量で計算できることが知られている。このようなBGN暗号を用いたデータ処理装置において、テンプレートを安全に更新する方法を説明する。なお本明細書では、セットアップ処理、登録処理、認証処理については記号も含めて特許文献1に記載のとおりである。セットアップ処理、登録処理、認証処理の詳細は実施の形態6において説明し、実施の形態2では、テンプレートの更新処理についてのみ説明する。図6を用いて、テンプレートの更新について詳細に説明する。図6は、テンプレートの更新手順を示したフローチャートである。トリガイベントが発生した場合に、はじめに、ステップS601にて、乱数生成部305が、0からq-1までの整数から一様ランダムに値δを取り出す。値δは、乱数値である。また、上記の一様とは、0からq-1の各値の出現確率が同一であることを意味する。上記のとおりqは素数である。実施の形態6において説明する図14のS1301に示すように、N=pqであり、また、図14のS1303に示すように、公開鍵pk=G,GT,N,e,g,h,eg,gであり、素数qは公開鍵pkの一部構成要素である。つまり、乱数生成部305は、公開鍵pkの一部を用いて乱数を生成する。次に、ステップS602にて、公開鍵更新部306が、既存の公開鍵G,GT,N,e,g,h,eg,gと乱数値δとを用いて、新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を定める。次に、ステップS603にて、テンプレート更新部307が、既存のテンプレートC=c1,c2,...,cTと乱数値δとを用いて、新たなテンプレートC=cδ1,cδ2,...,cδTを計算する。そして、記憶部301は、既存のテンプレートCに上書きして、新たなテンプレートCを記憶する。また、このとき、記憶部301は、既存の公開鍵G,GT,N,e,g,h,eg,gに上書きして、公開鍵更新部306により生成された新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を記憶する。次に、ステップS604にて、テンプレート更新部307が、乱数値δを消去する。最後に、ステップS605にて、新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を公開する。ステップS605は、例えば、通信部304が新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を証明装置101及び復号装置103に送信することにより実現される。また、通信部304による送信に代えて、可搬記憶媒体に新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を格納して、証明装置101及び復号装置103に当該可搬記憶媒体から新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を読み込ませてもよい。以降は、新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2と新たなテンプレートCを用いて、特許文献1の実施の形態4つまり、本明細書の実施の形態6に示す手順に従った認証処理が行われる。すなわち、まず証明装置101がユーザの生体情報を新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を用いて暗号化して認証用の暗号化生体情報を認証装置102に送付する。次に、認証装置102が、記憶部301の暗号化生体情報新たなテンプレートCと受領した暗号化生体情報と記憶部301の新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2とを用いて暗号化類似度情報を生成し、暗号化類似度情報を復号装置103に送付する。次に、復号装置103が秘密鍵skと新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を用いて類似度を復号し、認証装置102に復号された類似度を送付する。最後に認証装置102が類似度としきい値とを比較し、認証をする。なお、図6に示す手順にて公開鍵とテンプレートが更新されても、秘密鍵skは更新されない。アルゴリズムの性質上、秘密鍵skが更新されなくても、復号装置103は類似度の復号を行うことができる。以上の手順によりテンプレートと公開鍵とを更新すれば、仮に旧テンプレートが漏洩したとしても、旧テンプレートを用いて認証装置102になりすますことはできない。なぜならば、すでに公開鍵が新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2に置きかわっており、復号装置103での復号処理にもこの新たな公開鍵が用いられるため、新たな公開鍵と旧テンプレートとの間で齟齬が生じてしまい、この齟齬がハミング距離やユークリッド二乗距離の復号結果に反映して、乱数値δに応じたランダムな値になるからである。また、以上の手順によりテンプレートと公開鍵とを更新すれば、旧テンプレートと新ランダム基底を入手したとしても、新テンプレートを計算することはできない。なぜならば、この計算問題が計算量理論の分野において計算困難な問題の一つとされている計算Diffie-Hellman問題に帰着されるからである。以上、実施の形態2を説明した。この実施の形態2によれば、BGN暗号を用いたデータ処理装置において、テンプレートを安全に更新することができるという効果がある。このため、テンプレートが漏洩した場合でも、漏洩したテンプレートを用いたなりすましに対して有効に対抗することができ、セキュリティ強度を向上させることができる。また、この実施の形態2によれば、BGN暗号を用いているので、実施の形態1に比べてテンプレートのサイズを小さくすることができるという効果がある。実施の形態3.本実施の形態では、実施の形態1のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する方法を説明する。システム構成および各装置の構成は図1から図4のとおりであるのでここでは記述を省略する。図7を用いて、実施の形態1のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する方法を詳細に説明する。図7は、実施の形態1のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する場合の手順を示したフローチャートである。図7において、証明装置101は、ステップS701にて認証要求を送信する。認証要求を受け取った認証装置102は、ステップS702にて、乱数生成部305が、0からq-1までの整数から一様ランダムに値δを取り出す。次に、ステップS703にて、公開鍵更新部306が、既存の公開鍵パラメータeg,g^とランダム基底W=w1、w2、w3、W^=w^1、w^2、w^3と乱数値δとを用いて、新たな公開鍵パラメータeg,g^=eδg,δg^とランダム基底W=δw1、δw2、δw3、W^=δw^1、δw^2、δw^3を定める。次に、ステップS704にて、テンプレート更新部307が、既存のテンプレートC=c1,c2,...,cTと乱数値δとを用いて、新たなテンプレートC=δc1,δc2,...,δcTを計算し、記憶部301が、既存のテンプレートを上書きして、新たなテンプレートCを記憶する。また、記憶部301が、既存の公開鍵パラメータeg,g^とランダム基底W及びW^を上書きして、新たな公開鍵パラメータeg,g^とランダム基底W及びW^を記憶する。次に、ステップS705にて、テンプレート更新部307が、乱数値δを消去する。次に、ステップS706にて、新たな公開鍵パラメータeg,g^とランダム基底W=δw1、δw2、δw3、W^=δw^1、δw^2、δw^3を公開する。この新たな公開鍵パラメータとランダム基底を受け取ると、証明装置101は、ステップS707以降にて、新たな公開鍵パラメータとランダム基底を含む公開鍵を新公開鍵として、特許文献1の実施の形態2つまり、本明細書の実施の形態5に記載の認証方法により認証する。以上の手順により認証処理を行えば、認証のたびごと認証要求が送信されるごとに新たな公開鍵が生成されるので、リプレイ攻撃を防ぐことができる。以上、実施の形態3を説明した。この実施の形態3によれば、実施の形態1に記載のテンプレートの更新方法を流用してリプレイ攻撃対策を実施することができ、新たな装置の追加を必要としないので、別途リプレイ攻撃対策を施すのに比べてコストを低減できるという効果がある。実施の形態4.本実施の形態では、実施の形態2のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する方法を説明する。システム構成および各装置の構成は図1から図4のとおりであるのでここでは記述を省略する。図8を用いて、実施の形態2のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する方法を詳細に説明する。図8は、実施の形態2のテンプレートの更新方法を流用してリプレイ攻撃対策を実施する場合の手順を示したフローチャートである。図8において、証明装置101は、ステップS801にて認証要求を送信する。認証要求を受け取った認証装置102は、ステップS802にて、乱数生成部305が、0からq-1までの整数から一様ランダムに値δを取り出す。次に、ステップS803にて、公開鍵更新部306が、公開鍵G,GT,N,e,g,h,eg,gと乱数値δとを用いて、新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を定める。次に、ステップS804にて、テンプレート更新部307が、既存のテンプレートC=c1,c2,...,cTと乱数値δとを用いて、新たなテンプレートC=cδ1,cδ2,...,cδTを計算し、記憶部301が、既存のテンプレートを上書きして、新たなテンプレートCを記憶する。また、記憶部301が、既存の公開鍵を上書きして、新たな公開鍵を記憶する。次に、ステップS805にて、テンプレート更新部307が、乱数値δを消去する。次に、ステップS806にて、新たな公開鍵G,GT,N,e,gδ,hδ,eg,gδ^2を公開する。この新たな公開鍵を受け取ると、証明装置101は、ステップS807以降にて、新公開鍵を用いて、特許文献1の実施の形態4つまり、本明細書の実施の形態6に記載の認証方法により認証する。以上の手順により認証処理を行えば、認証のたびごと認証要求が送信されるごとに新たな公開鍵が生成されるので、リプレイ攻撃を防ぐことができる。以上、実施の形態4を説明した。この実施の形態4によれば、実施の形態2に記載のテンプレートの更新方法を流用してリプレイ攻撃対策を実施することができ、新たな装置の追加を必要としないので、別途リプレイ攻撃対策を施すのに比べてコストを低減できるという効果がある。以上、実施の形態1および実施の形態2でテンプレートの更新方法を説明し、実施の形態3および実施の形態4でそれを応用したリプレイ攻撃対策方法を説明した。なお、これらを組み合わせて利用することができることは当然である。すなわち、認証のたびごとにリプレイ攻撃対策を施し、さらにテンプレートの漏洩のおそれがあるときにテンプレート更新を実施することができる。実施の形態5.実施の形態5では、実施の形態1及び実施の形態3の説明を補足するために、特許文献1の実施の形態2に記載の方式におけるセットアップ処理、登録処理、認証処理を説明する。特許文献1の実施の形態2に記載の方式では、T個の配列を用意し、それによって特徴ベクトルを構成するが、このとき類似度の指標として2つの特徴ベクトルのハミング距離またはユークリッド二乗距離を用いる。2つの特徴ベクトルをb=b1,b2,...,bT、b’=b’1,b’2,...,b’Tとする。このとき、2つの特徴ベクトルのハミング距離は、数6で与えられただしbi,b’i∈{0,1}、また、2つの特徴ベクトルのユークリッド二乗距離は、数7で与えられる。次に、図19-図22を用いて、特許文献1の実施の形態2に記載の方式におけるセットアップ処理、登録処理、認証処理の各々の概要を説明する。図19がセットアップ処理の概要を示し、図20が登録処理の概要を示し、図21及び図22が認証処理の概要を示す。まず、図19を参照して、セットアップ処理の概要を説明する。最初に、復号装置103のパラメータ生成部401が、岡本-高島暗号アルゴリズムに基づき、秘密鍵skと公開鍵pkを生成するS2101。次に、復号装置103の記憶部403が秘密鍵skを記憶し、通信部404が公開鍵pkを証明装置101及び認証装置102に送信するS2102。次に、証明装置101では、通信部206が公開鍵pkを受信し、記憶部205が公開鍵pkを記憶し、認証装置102では、通信部304が公開鍵pkを受信し、記憶部301が公開鍵pkを記憶するS2102。なお、ここでは、公開鍵pkを送受信する例を説明しているが、証明装置101及び認証装置102に公開鍵pkを配布する方法は他の方法でもよい。例えば、復号装置103が公開鍵pkを記録媒体に格納し、証明装置101及び認証装置102において当該記録媒体から公開鍵pkを読み出して格納するようにしてもよい。次に、図20を参照して、登録処理の概要を説明する。最初に、証明装置101において、生体情報抽出部201が、ユーザの生体情報を抽出するS2201。次に、証明装置101の特徴ベクトル形成部202が、S2201で抽出された生体情報の特徴ベクトルbを生成するS2202。次に、証明装置101の乱数生成部203が公開鍵pkの一部を用いて乱数を生成し、また、暗号化部204が記憶部205から公開鍵pkを読み出し、暗号化部204が公開鍵pkと乱数を用いて特徴ベクトルbを暗号化するS2203。次に、証明装置101の通信部206が、暗号化された特徴ベクトルCを認証装置102に送信するS2204。次に、認証装置102の通信部304が、暗号化された特徴ベクトルCを受信し、記憶部205が暗号化された特徴ベクトルCを記憶するS2205。次に、図21及び図22を参照して、認証処理の概要を説明する。最初に、証明装置101において、生体情報抽出部201が、ユーザの生体情報を抽出するS2301。次に、証明装置101の特徴ベクトル形成部202が、S2301で抽出された生体情報の特徴ベクトルb’を生成するS2302。次に、証明装置101の乱数生成部203が公開鍵pkの一部を用いて乱数を生成し、また、暗号化部204が記憶部205から公開鍵pkを読み出し、暗号化部204が公開鍵pkと乱数を用いて特徴ベクトルb’を暗号化するS2303。次に、証明装置101の通信部206が、暗号化された特徴ベクトルC^を認証装置102に送信するS2304。次に、認証装置102の通信部304が、暗号化された特徴ベクトルC^を受信するS2305。次に、認証装置102の暗号化類似度生成部302が、記憶部301の暗号化特徴ベクトルCを読み出すS2401。次に、認証装置102の乱数生成部305が公開鍵pkの一部を用いて乱数を生成し、また、暗号化類似度生成部302が記憶部301から公開鍵pkを読み出し、暗号化類似度生成部302が記憶部301から読み出した暗号化特徴ベクトルCと証明装置101から受信した暗号化特徴ベクトルC^に対して、公開鍵pkと乱数を用いて暗号化類似度情報を生成するS2402。認証装置102は、公開鍵pkに対応付けられている秘密鍵skを知りえないので、暗号化特徴ベクトルC及び暗号化特徴ベクトルC^を復号することはできない。このため、暗号化特徴ベクトルC及び暗号化特徴ベクトルC^が暗号化された状態のままで、暗号化類似度情報が生成される。次に、認証装置102の通信部304が、暗号化類似度情報を復号装置103に送信するS2403。次に、復号装置103の通信部404が、暗号化類似度情報を受信するS2404。次に、復号装置103の復号部402が、パラメータ生成部401から秘密鍵skを読み出し、暗号化類似度情報に秘密鍵skを用いて復号処理を行い、平文の類似度を導出するS2405。次に、復号装置103の通信部404が、平文の類似度を認証装置102に送信するS2406。なお、類似度は、登録用の特徴ベクトルbと認証用の特徴ベクトルb’がどの程度類似しているかを示す情報であり、類似度からは特徴ベクトル、生体情報を計算することはできない。次に、認証装置102の通信部304が、平文の類似度を受信するS2407。次に、認証装置102の判定部303が、平文の類似度が所定のしきい値以上であるか否かを判定し、しきい値以上であれば本人であると判定し、しきい値を下回っている場合は、本人ではないと判定するS2408。以下、図9-図13を参照して、各処理の動作をより詳しく説明する。図9がセットアップ処理の詳細を示し、図10が登録処理の詳細を示し、図11-図13が認証処理の詳細を示す。まず、図9を用いてセットアップについて説明する。セットアップでは、復号装置103が、公開鍵pkおよび秘密鍵skを生成する。この公開鍵pkおよび秘密鍵skは、ユーザごとに異なる公開鍵および秘密鍵であってもよいし、システムに1つの公開鍵および秘密鍵であってもよい。ここでは、説明を簡単にするために、システムに1つの公開鍵および秘密鍵を用いる場合について説明するが、これをユーザごとの公開鍵および秘密鍵の場合に拡張するのは容易である。図9は、パラメータ生成部401における公開鍵pk及び秘密鍵skの生成手順を示したフローチャートである。はじめに、ステップS901にて、パラメータ生成部401は、群位数q、群G、G^、GT、生成元g∈G、g^∈G^を定める。この具体的な方法は例えば非特許文献5にあるので、ここでは省略する。なお、群位数はセキュリティレベルに応じて定まるが、通常は200ビットや1024ビットなどの大きなサイズの素数とする。次に、ステップS902にて、パラメータ生成部401は、ベクトル空間をV=G×G×G、V^=G^×G^×G^とし、標準基底A=a1,a2,a3,A^=a^1,a^2,a^3を定める。この定め方はすでに述べたとおりである。次に、ステップS903にて、パラメータ生成部401は、0からq-1までの整数から一様ランダムに値を9回取り出し、それらを用いて3行3列の行列X=Xi,jを定める。この行列は正則行列でなければならないが、この方法で行列を定めることによりきわめて高い確率で正則行列になる。なお、より正確性を期すのであれば、このように行列を定めた後に行列式を計算するなどの方法により正則性を判定し、正則でなければ行列の要素を再度ランダムに選べばよい。次に、ステップS904にて、パラメータ生成部401は、0からq-1までの整数から一様ランダムに値を9回取り出し、それらを用いて3行3列の行列X^=X^i,jを定める。この行列はきわめて高い確率で正則行列になるが、正則行列にならなかった場合には再度ランダムに選べばよい。次に、ステップS905にて、パラメータ生成部401は、以下の数8および数9によりランダム基底W=w1,w2,w3,W^=w^1,w^2,w^3を定める。最後に、ステップS906にて、パラメータ生成部401は、公開鍵pk=q、V、V^、e、GT、A、A^、W、W^、eg,g^を公開し、秘密鍵sk=X、X^を記憶部403に格納する。図10は、証明装置101において生体情報を登録する手順を示したフローチャートである。はじめに、ステップS1001にて、生体情報抽出部201が、ユーザの生体情報を抽出する。これには様々な方法があるが、例えば指紋に光を当てて紋様をセンサで読み取るといったことにより抽出する。次に、ステップS1002にて、特徴ベクトル形成部202が、生体情報から特徴ベクトルb=b1,b2,...,bTを形成する。ここでTは特徴ベクトルを格納する配列の大きさであり、特徴ベクトルの形成方法によって決まる値である。本実施の形態の形成方法は、読み取った紋様を領域分割し、各領域で特徴点の有無を検出し、特徴点がある箇所の配列に1、ない箇所の配列に0を格納することにより特徴ベクトルを形成するという方法である。ただし、ここでハミング距離の場合はbi∈{0,1}であり、ユークリッド二乗距離の場合は、bi∈{0,1,...,q-1}であることに注意する。次に、ステップS1003にて、乱数生成部203が、0からq-1までの整数から一様ランダムに値を4T回取り出し、{r2,i,r3,i,r^2,i,r^3,i}i=1,2,...,Tとする。次に、ステップS1004にて、暗号化部204が、ci=biw1r2,iw2r3,iw3,c^i=biw^1r^2,iw^2r^3,iw^3により暗号化特徴ベクトルC=c1,c2,...,cT,暗号化特徴ベクトルC^=c^1,c^2,...,c^Tを計算する。なお、w1,w2,w3とw^1,w^2,w^3は、公開鍵の一部W及びW^として、復号装置103から配布されたものである。次に、ステップS1005にて、通信部206が、暗号化特徴ベクトルC=c1,c2,...,cT,暗号化特徴ベクトルC^=c^1,c^2,...,c^Tを認証装置102に送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。最後に、ステップS1006にて、認証装置102が、暗号化特徴ベクトルC=c1,c2,...,cT,暗号化特徴ベクトルC^=c^1,c^2,...,c^Tを記憶部301に格納する。次に、図11、図12、図13を用いて、認証方法を説明する。なお、簡単のためここでは認証時に認証の対象となるユーザが別途ID情報などによって特定されているいわゆる1:1認証の場合について説明する。はじめに、ステップS1101にて、証明装置101の生体情報抽出部201がユーザの生体情報を抽出する。抽出方法は生体情報の登録時と同様である。次に、ステップS1102にて、証明装置101の特徴ベクトル形成部202が、生体情報から特徴ベクトルb’=b’1,b’2,...,b’Tを形成する。形成方法は、生体情報の登録時と同様である。ただし、ここでハミング距離の場合はb’i∈{0,1}であり、ユークリッド二乗距離の場合はb’i∈{0,1,...,q-1}であることに注意する。次に、ステップS1103にて、証明装置101の乱数生成部203が、0からq-1までの整数から一様ランダムに値を4T回取り出し、{r’2,i,r’3,i,r^’2,i,r^’3,i}i=1,2,...,Tとする。次に、ステップS1104にて、証明装置101の暗号化部204が、c’i=b’iw1r’2,iw2r’3,iw3,c^’i=b’iw^1r’2,iw^2r’3,iw^3により暗号化特徴ベクトルC’=c’1,c’2,...,c’T,暗号化特徴ベクトルC^’=c^’1,c^’2,...,c^’Tを計算する。次に、ステップS1105にて、証明装置101の通信部206が、暗号化特徴ベクトルC’=c’1,c’2,...,c’T,暗号化特徴ベクトルC^’=c^’1,c^’2,...,c^’Tを認証装置102に送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。次に、ステップS1106にて、認証装置102の通信部206が、暗号化特徴ベクトルC’=c’1,c’2,...,c’T,暗号化特徴ベクトルC^’=c^’1,c^’2,...,c^’Tを受信する。次に、ステップS1107にて、認証装置102の暗号化類似度生成部302が、記憶部301から暗号化特徴ベクトルC=c1,c2,...,cT,暗号化特徴ベクトルC^=c^1,c^2,...,c^Tを取り出す。このとき、一般に記憶部301には多数のユーザの暗号化生体情報が格納されているが、その中からどれを取り出すかについては、別途与えられるID情報を用いる。次に、ステップS1108にて、認証装置102の乱数生成部203が、0からq-1までの整数から一様ランダムに値を6T回取り出し、{s1,i,s2,i,s3,i,s^1,i,s^2,i,s^3,i}i=1,2,...,Tとする。次に、ステップS1109にて、認証装置102の乱数生成部203が、0からq-1までの整数から一様ランダムに値を4回取り出し、{u2,u3,u^2,u^3}とする。次に、ステップS1110にて、認証装置102の暗号化類似度生成部302が、di=ci-c’is1,iw1s2,iw2s3,iw3を計算する。なお、w1,w2,w3は、公開鍵の一部Wとして、復号装置103から配布されたものである。次に、ステップS1111にて、認証装置102の暗号化類似度生成部302が、d^i=c^i-c^’is^1,iw^1s^2,iw^2s^3,iw^3を計算する。なお、w^1,w^2,w^3は、公開鍵の一部W^として、復号装置103から配布されたものである。次に、ステップS1112にて、認証装置102の暗号化類似度生成部302が、数10に従って、Eを計算する。次に、ステップS1113にて、認証装置102の暗号化類似度生成部302が、数11に従って、E^を計算する。次に、ステップS1114にて、認証装置102の通信部206がd1,...,dT,d^1,...,d^T...,E,E^を復号装置103へ送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。本実施の形態では、d1,...,dT,d^1,...,d^T...,E,E^が暗号化類似度情報の例となる。次に、ステップS715にて、復号装置103の通信部404が、d1,...,dT,d^1,...,d^T,E,E^を受信する。次に、ステップS716にて、復号装置103の復号部402が、記憶部403から秘密鍵sk=X,X^を取り出す。次に、ステップS717にて、復号装置103の復号部402が、Xの逆行列X-1=ti,jおよびX^の逆行列X^-1=t^i,jを計算する。なお、この値は毎回計算するのではなく、あらかじめ計算した状態で記憶部403に格納しておき、それを取り出すものとしてもよい。次に、ステップS718にて、復号装置103が、数12に従ってZ1を計算する。ここで、Decoアルゴリズムは以下の数13のように計算される。なお、数13中のkは整数である。次に、ステップS719にて、復号装置103の復号部402が、Z2=eDecoE,w1,X,w^1ew1,DecoE^,w^1,X^を計算する。このDecoアルゴリズムも上記と同様に計算される。次に、ステップS720にて、復号装置103の復号部402がZ=Z1/Z2を計算する。次に、ステップS721にて、復号装置103の復号部402がeg,g^を底とするZの離散対数dを計算する。なお、eg,g^は、公開鍵の一部として、復号装置103から配布されたものである。この離散対数dが、特徴点の一致数に対応しており、類似度を表す。なお、離散対数を求める計算は現代の計算機能力では困難とされているが、dが小さい場合には効率的に計算することができる。本実施の形態においてdは位数qに比べて十分小さいため、効率的に計算することができる。次に、ステップS722にて、復号装置103の通信部404が、類似度dを認証装置102へ送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。次に、ステップS723にて、認証装置102の通信部304が、類似度dを受信する。次に、ステップS724にて、類似度dがしきい値以上かを判定する。しきい値は、利用する生体情報の種類や安全性要件などさまざまな要素を勘案してあらかじめシステムで決められた値である。しきい値以上であれば、証明装置101から送られてきた暗号化生体情報はIDで指定された本人のものであると判断する。一方、しきい値未満であれば、証明装置101から送られてきた暗号化生体情報はIDで指定された人物のものではなく、他人のものであると判断する。以上のステップにより、認証装置102は証明装置101との間で生体認証を行うことができる。なお、本実施の形態では3次元の双対ペアリングベクトル空間を用いる方法を開示したが、3次元というのはあくまで例であって、必ずしも3次元である必要はない。例えば2次元でも実施可能であるし、4次元以上でも実施可能である。2次元の場合には、本実施の形態中に現れたw3,w^3のベクトルを取り除いて実施すればよい。このようにすれば、生体情報の登録時や認証時の計算量を低減できるという効果がある。また、4次元以上の場合には、増えた分のベクトルにw2,w3,w^2,w^3と同様のはたらきをさせればよい。すなわち、ci,c^i,di,d^iを計算する際、増えた分のベクトルに乱数係数をかけて、w2,w3,w^2,w^3に加え合わせればよい。このようにすれば、より解読が困難な暗号文を作成することができ、安全性を向上させることができる。実施の形態6.実施の形態6では、実施の形態2及び実施の形態4の説明を補足するために、特許文献1の実施の形態4に記載の方式におけるセットアップ処理、登録処理、認証処理を説明する。なお、本実施の形態においても、セットアップ処理、登録処理、認証処理の概要は、図19-22に示したとおりである。特許文献1の実施の形態4に記載の方式では、生体認証で用いる特徴ベクトルとして、特徴点の配列を用意し、ユーザがその特徴点を保有する場合に1、特徴点を保有しない場合に0を配列に格納して、配列を特徴ベクトルとし、認証時には1が一致している箇所の数を類似度の指標とするような認証方式を例に説明する。まず、図14を用いてセットアップについて説明する。図14は、パラメータ生成部401における公開鍵及び秘密鍵の生成手順を示したフローチャートである。はじめに、ステップS1301にて、パラメータ生成部401が、素数p,q、群G,GTを定める。なお、素数はセキュリティレベルに応じて定まるが、素数pとqの積を群位数とするため、通常は素因数分解ができないように素数を1024ビットや2048ビットなどの大きなサイズの素数とする。次に、ステップS1302にて、パラメータ生成部401が、Gから一様ランダムにg、uを選び、h=uqを計算する。最後に、ステップS1303にて、パラメータ生成部401が、公開鍵pk=G,GT,N,e,g,h,eg,gを公開し、秘密鍵sk=pを記憶部403に格納する。次に、図15を用いて、生体情報の登録方法を説明する。なお、ここではユーザが証明装置101を経由して認証装置102に生体情報を登録する場合について説明するが、認証装置102上で直接生体情報を登録する場合や、登録用の専用装置を経由して登録する場合などにおいても同様の手順により実現できる。図15は、証明装置101において生体情報を登録する手順を示したフローチャートである。はじめに、ステップS1401にて、生体情報抽出部201がユーザの生体情報を抽出する。これには様々な方法があるが、例えば指紋に光を当てて紋様をセンサで読み取るといったことにより抽出する。次に、ステップS1402にて、特徴ベクトル形成部202が、生体情報から特徴ベクトルb=b1,b2,...,bTを形成する。次に、ステップS1403にて、乱数生成部203が、0からN-1までの整数から一様ランダムに値をT回取り出し、{ri}i=1,2,...,Tとする。次に、ステップS1404にて、暗号化部204が、ci=gbihriにより暗号化特徴ベクトルC=c1,c2,...,cTを計算する。なお、g、hは公開鍵の一部として復号装置103から配布されたものである。次に、ステップS1405にて、通信部206が、暗号化特徴ベクトルC=c1,c2,...,cTを認証装置102に送信する。最後に、ステップS1406にて、認証装置102が、暗号化特徴ベクトルC=c1,c2,...,cTを記憶部301に格納する。次に、図16、図17、図18を用いて、認証方法を説明する。なお、簡単のためここでは認証時に認証の対象となるユーザが別途ID情報などによって特定されているいわゆる1:1認証の場合について説明する。はじめに、ステップS1801にて、証明装置101の生体情報抽出部201が、ユーザの生体情報を抽出する。抽出方法は生体情報の登録時と同様である。次に、ステップS1802にて、証明装置101の特徴ベクトル形成部202が、生体情報から特徴ベクトルb’=b’1,b’2,...,b’Tを形成する。形成方法は、生体情報の登録時と同様である。次に、ステップS1803にて、証明装置101の乱数生成部203が、0からN-1までの整数から一様ランダムに値をT回取り出し、{r’i}i=1,2,...,Tとする。次に、ステップS1804にて、証明装置101の暗号化部204が、c’i=gb’ihr’iにより暗号化特徴ベクトルC’=c’1,c’2,...,c’Tを計算する。次に、ステップS1805にて、証明装置101の通信部206が、暗号化特徴ベクトルC’=c’1,c’2,...,c’Tを認証装置102に送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。次に、ステップS1806にて、認証装置102の通信部206が、暗号化特徴ベクトルC’=c’1,c’2,...,c’Tを受信する。次に、ステップS1807にて、認証装置102の暗号化類似度生成部302が、記憶部301から暗号化特徴ベクトルC=c1,c2,...,cTを取り出す。次に、ステップS1808にて、認証装置102の乱数生成部305が、0からN-1までの整数から一様ランダムに値を取り出し、sとする。ステップS1809にて、認証装置102の暗号化類似度生成部302が、数14に従って、Eを計算する。次に、ステップS1810にて、認証装置102の通信部304が、Eを復号装置103へ送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。本実施の形態では、Eが暗号化類似度情報となる。次に、ステップS1811にて、復号装置103の通信部404が、Eを受信する。次に、ステップS1812にて、復号装置103の復号部402が、記憶部403から秘密鍵pを取り出す。次に、ステップS1813にて、復号装置103の復号部402が、Z=Epを計算する。次に、ステップS1814にて、復号装置103の復号部402が、eg,gpを底とするZの離散対数dを計算する。なお、eg,gは、公開鍵の一部として、復号装置103から配布されたものである。本実施の形態でも、この離散対数dが類似度に相当する。次に、ステップS1815にて、復号装置103の通信部404がdを認証装置102へ送信する。その際、例えばSSLなどの通信用改ざん検出技術を用いて通信の途中で改ざんが行われないようにすることが望ましい。次に、ステップS1816にて、認証装置102の通信部304が、類似度dを受信する。次に、ステップS1817にて、判定部303が、類似度dがしきい値以上かを判定する。このしきい値は、利用する生体情報の種類や安全性要件などさまざまな要素を勘案してあらかじめシステムで決められた値である。しきい値以上であれば、証明装置101から送られてきた暗号化生体情報はIDで指定された本人のものであると判断する。一方、しきい値未満であれば、証明装置101から送られてきた暗号化生体情報はIDで指定された人物のものではなく、他人のものであると判断する。以上のステップにより、認証装置102は証明装置101との間で生体認証を行うことができる。最後に、実施の形態1-6に示した証明装置101、認証装置102、復号装置103のハードウェア構成例について説明する。図23は、実施の形態1-6に示した証明装置101、認証装置102、復号装置103のハードウェア資源の一例を示す図である。なお、図23の構成は、あくまでも証明装置101、認証装置102、復号装置103のハードウェア構成の一例を示すものであり、証明装置101、認証装置102、復号装置103のハードウェア構成は図23に記載の構成に限らず、他の構成であってもよい。図23において、証明装置101、認証装置102、復号装置103は、プログラムを実行するCPU911CentralProcessingUnit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいうを備えている。CPU911は、バス912を介して、例えば、ROMReadOnlyMemory913、RAMRandomAccessMemory914、通信ボード915、表示装置901、キーボード902、マウス903、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。更に、CPU911は、FDD904FlexibleDiskDrive、コンパクトディスク装置905CDD、プリンタ装置906と接続していてもよい。また、証明装置101は、生体情報を読み取るための読取り装置907と接続されている。また、磁気ディスク装置920の代わりに、光ディスク装置、メモリカード登録商標読み書き装置などの記憶装置でもよい。RAM914は、揮発性メモリの一例である。ROM913、FDD904、CDD905、磁気ディスク装置920の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。実施の形態1-6で説明した記憶部は、RAM914、磁気ディスク装置920等により実現される。通信ボード915、キーボード902、マウス903、読取り装置907、FDD904などは、入力装置の一例である。また、通信ボード915、表示装置901、プリンタ装置906などは、出力装置の一例である。通信ボード915は、他の装置と接続されている以外に、例えば、LANローカルエリアネットワーク、インターネット、WANワイドエリアネットワーク、SANストレージエリアネットワークなどに接続されていても構わない。磁気ディスク装置920には、オペレーティングシステム921OS、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911がオペレーティングシステム921、ウィンドウシステム922を利用しながら実行する。また、RAM914には、CPU911に実行させるオペレーティングシステム921のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、RAM914には、CPU911による処理に必要な各種データが格納される。また、ROM913には、BIOSBasicInputOutputSystemプログラムが格納され、磁気ディスク装置920にはブートプログラムが格納されている。証明装置101、認証装置102、復号装置103の起動時には、ROM913のBIOSプログラム及び磁気ディスク装置920のブートプログラムが実行され、BIOSプログラム及びブートプログラムによりオペレーティングシステム921が起動される。上記プログラム群923には、実施の形態1-6の説明において~部記憶部以外、以下も同様として説明している機能を実行するプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。ファイル群924には、実施の形態1-6の説明において、~の判断、~の判定、~の生成、~の計算、~の比較、~の導出、~の抽出、~の形成、~の更新、~の設定、~の登録、~の選択等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、~ファイルや~データベースの各項目として記憶されている。~ファイルや~データベースは、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出検索参照比較演算計算処理編集出力印刷表示などのCPUの動作に用いられる。抽出検索参照比較演算計算処理編集出力印刷表示のCPUの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。また、実施の形態1-6で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、FDD904のフレキシブルディスク、CDD905のコンパクトディスク、磁気ディスク装置920の磁気ディスク、その他光ディスク、ミニディスク、DVD等の記録媒体に記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体によりオンライン伝送される。また、実施の形態1-6の説明において~部として説明しているものは、~回路、~装置、~機器であってもよく、また、~ステップ、~手順、~処理であってもよい。すなわち、実施の形態1-6で説明したフローチャートに示すステップ、手順、処理により、本発明に係るデータ処理方法を実現することができる。また、~部として説明しているものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子デバイス基板配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、DVD等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、実施の形態1-6の~部としてコンピュータを機能させるものである。あるいは、実施の形態1-6の~部の手順や方法をコンピュータに実行させるものである。このように、実施の形態1-6に示す証明装置101、認証装置102、復号装置103は、処理装置たるCPU、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように~部として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。"