(57)【要約】【課題】準同型暗号を利用した暗号処理システムにおいて、暗号化された情報を簡便にキャンセルする。【解決手段】  コンピュータによって実行される暗号処理方法の一例は、第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、第１の多項式と第２の多項式と乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを用いて、第１のデータと第２のデータとの照合を行うことを特徴とする。【選択図】図１０
2016012111.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって実行される暗号処理方法であって、
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、
前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、
前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う、
を含む暗号処理方法。
【請求項２】
さらに、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、復号すると前記第１のデータと前記第２のデータの間の秘匿距離となる暗号化秘匿距離を算出し、
前記第１のデータと前記第２のデータとの前記照合は、前記秘匿距離と所定の値との比較によって行う、請求項１に記載の暗号処理方法。
【請求項３】
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の和である、請求項１または２に記載の暗号処理方法。
【請求項４】
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の積である、請求項１または２に記載の暗号処理方法。
【請求項５】
さらに、
外部から入力されパスワードを用いて、前記乱数を生成することを含む、請求項１乃至４のいずれか一項に記載の暗号処理方法。
【請求項６】
前記第１の変換多項式は前記第１のベクトルの要素を累乗の昇順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の降順に並べる、または前記第１の変換多項式は前記第１のベクトルの要素を累乗の降順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の昇順に並べる、請求項１乃至４のいずれか一項に記載の暗号処理方法。
【請求項７】
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得する多項式変換部と、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得する暗号化部と、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う比較部と、
を含む暗号処理装置。
【請求項８】
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、
前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、
前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う
処理をコンピュータに実行させることを特徴とする暗号処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理方法、暗号処理装置、および暗号処理プログラムに関する。
【背景技術】
【０００２】
現在、個人情報、機密情報の保護の重要性が増す中、それらの情報を利用したサービスの市場が拡大しつつある。そのようなサービスとしては、たとえば、スマートフォンから取得できる個人ユーザの位置情報を活用したサービスなどがある。そこで、個人情報・機密情報を保護したままデータの利活用ができる秘匿化技術が注目されている。秘匿化技術の中には、データ種別・サービス要件に応じて、暗号技術や統計技術を使った技術がある。
【０００３】
暗号技術を用いた秘匿化技術として、準同型暗号技術がある。準同型暗号技術は、暗号化と復号とで一対の異なる鍵を用いる公開鍵暗号方式の１つで、暗号化したままデータ操作が可能となる機能を備えた暗号である。
【０００４】
準同型暗号方式を用いれば、暗号文の加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、電子投票・電子現金などの分野や近年ではクラウド・コンピューティング分野において利用されることが期待されている。加算または乗算に関する準同型暗号方式として、乗算のみ可能なＲＳＡ暗号方式や、加算のみが可能なＡｄｄｉｔｉｖｅ  ＥｌＧａｍａｌ暗号が知られている。乗算準同型暗号では、平文（メッセージ）ａ、ｂの暗号文をＥ（ａ）、Ｅ（ｂ）とすると、平文の積ａ・ｂの暗号文Ｅ（ａ・ｂ）を、Ｅ（ａ）とＥ（ｂ）から計算することができる。また、加算準同型暗号では、平文ａ、ｂの暗号文をＥ（ａ）、Ｅ（ｂ）とすると、平文の和ａ＋ｂの暗号文Ｅ（ａ＋ｂ）を、Ｅ（ａ）とＥ（ｂ）から計算することができる。準同型暗号方式を用いれば、暗号文の加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、電子投票・電子現金などの分野や近年ではクラウド・コンピューティング分野において利用されることが期待されている。
【０００５】
最近、加算と乗算の両方に関して準同型性を有する暗号として完全準同型暗号が知られている（たとえば、非特許文献１、２）。加法と乗法が暗号化したままで計算できれば、排他的論理和、論理積、否定といった演算を暗号化したままで計算することができる。つまり、完全準同型暗号とは、すべての論理回路による演算に対して準同型性を有する暗号である。当初は、理論的な実現方法のみが示され、実用的な構成方法は明らかにされなかったが、鍵生成方法の具体的な構成方法の例や、暗号化できるデータの種類を拡張した暗号方式も提案されつつある。また、限定回だけ加算と乗算の両方が可能な準完全準同型暗号（Ｓｏｍｅｗｈａｔ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ）があり、この暗号方式は完全準同型暗号に比べ暗号サイズと処理性能が大幅に少なくて済むため、より実用的な運用が期待されている。
【０００６】
一般に、暗号技術は２つの情報の類似性を検証する暗号処理システムにおいて使用されている。そのような暗号処理システムとしては、たとえば、生体認証システムが挙げられる（たとえば、非特許文献３）。たとえば、準同型暗号を応用した暗号処理システムでは、情報は計算サーバでは暗号化されて登録されるため、情報が漏れることはなく高い安全性を得ることができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｃ．Ｇｅｎｔｒｙ、“Ｆｕｌｌｙ Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｕｓｉｎｇ  ｉｄｅａｌ  ｌａｔｔｉｃｅｓ”、ＳＴＯＣ２００９、ｐｐ．１６９−１７８、２００９
【非特許文献２】Ｃ．Ｇｅｎｔｒｙ  ａｎｄ  Ｓ．Ｈａｌｅｖｉ、“Ｉｍｐｌｅｍｅｎｔｉｎｇ  Ｇｅｎｔｒｙ’ｓ  Ｆｕｌｌｙ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ”、ＥＵＲＯＣＲＹＰＴ  ２０１１、ＬＮＣＳ  ６６３２、ｐｐ．１２９−１４８、 ２０１１
【非特許文献３】安田、矢嶋、下山、小暮「複数企業が持つ購買履歴データのクラウド秘匿集計」ＳＣＩＳ  ２０１２
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、準同型暗号を応用した暗号処理システムでは、ユーザがシステムを利用しなくなった場合に、暗号化された情報をシステムの鍵を変えることなくユーザが簡便にキャンセル（無効化）することが難しいという問題がある。
そこで、１つの側面では、本発明は、準同型暗号を利用した暗号処理システムにおいて、暗号化された情報を簡便にキャンセルすることを目的とする。
【課題を解決するための手段】
【０００９】
コンピュータによって実行される暗号処理方法の一例は、第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、第１の多項式と第２の多項式と乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを用いて、第１のデータと第２のデータとの照合を行うことを特徴とする。
【発明の効果】
【００１０】
実施形態の暗号処理装置および方法では、準同型暗号を利用した暗号処理システムにおいて、暗号化された情報を簡便にキャンセルすることができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】生態認証システムの概要を説明するための図である。
【図２】比較例における準同型暗号を利用した生体認証システムの概要を示す図である。
【図３】比較例における準同型暗号を利用した生体認証システムの端末の機能ブロックの例を示す図である。
【図４】比較例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（登録時）の例を示す図である。
【図５】比較例における暗号化テンプレートのデータフォーマットの例を示す図である。
【図６】比較例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（照合時）の例を示す図である。
【図７】比較例における準同型暗号を利用した生体認証システムの認証サーバの機能ブロックの例を示す図である。
【図８】比較例における準同型暗号を利用した生体認証方法の登録時の処理の流れの例を示す図である。
【図９】比較例における準同型暗号を利用した生体認証方法の照合時の処理の流れの例を示す図である。
【図１０】実施例における準同型暗号を利用した生体認証システムの概要を示す図である。
【図１１】実施例における準同型暗号を利用した生体認証システムの端末の機能ブロックの例を示す図である。
【図１２】実施例における準同型暗号を利用した生体認証システムの端末の機能ブロックの別の例を示す図である。
【図１３】乱数生成の例の概要を示す図である。
【図１４】実施例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（登録時）の例を示す図である。
【図１５Ａ】実施例における暗号化テンプレートのデータフォーマットの例を示す図である。
【図１５Ｂ】実施例における暗号化テンプレートのデータフォーマットの別の例を示す図である。
【図１６】実施例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（照合時）の例を示す図である。
【図１７】実施例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（照合時）の別の例を示す図である。
【図１８】実施例における準同型暗号を利用した生体認証システムの認証サーバの機能ブロックの例を示す図である。
【図１９】準同型暗号を利用した暗号処理装置の構成の例を示す構成図である。
【図２０】実施例における準同型暗号を利用した生体認証方法の登録時の処理の流れの例を示す図である。
【図２１】実施例における準同型暗号を利用した生体認証方法の照合時の処理の流れの例を示す図である。
【図２２】実施例における準同型暗号を利用した生体認証方法の照合時の処理の流れの別の例を示す図である。
【発明を実施するための形態】
【００１２】
以下では、まず、準同型暗号を用いた、ハミング距離などの秘匿距離の計算方法について説明する。以下では準同型暗号として、イデアル格子ベースの準同型暗号を例に説明する。その後、図１〜９を参照しながら比較例と図１０〜２２を参照しながら実施例を説明する。
【００１３】
＜準同型暗号を用いた秘匿距離計算＞
まず、準完全準同型暗号方式について説明する。以下で説明する準完全準同型暗号は、イデアル格子ベース準同型暗号とも呼ばれる。この名称は、イデアル格子を用いることで加法的準同型性と乗法的準同型性が導入されることに由来する。
【００１４】
完全準同型暗号とは、すべてのロジック回路による演算に対して準同型性を満たす暗号である。
【００１５】
以下の説明は、すべて準完全準同型暗号に関するものである。
準同型性の例としては、加算に関する準同型性や、乗算に関する準同型性がある。加算に関する準同型性や、乗算に関する準同型性とは、例えば、引数ｍ１、ｍ２について、写像（関数）Ｆが、下の（１）または（２）が成立することである。すなわち、
【数１】
2016012111.tif 000003
が成立する。（１）の場合が加算に関して準同型、（２）の場合が乗算に関して準同型であるという。上の引数ｍ１、ｍ２を平文、写像Ｆとして暗号化関数Ｅｎｃを代入すれば、準同型暗号となる。平文ｍ１、ｍ２から暗号文Ｅｎｃ（ｍ１）、Ｅｎｃ（ｍ２）を得る演算を「暗号化」とも呼ぶ。暗号文Ｅｎｃ（ｍ１）、Ｅｎｃ（ｍ２）は誤解を生じない場合には、単に暗号文Ｅ（ｍ１）、Ｅ（ｍ２）と表記することがある。
【００１６】
準完全準同型暗号方式では、鍵ペア（ｐｋ、ｓｋ）と、平文ｍ１、ｍ２、…、ｍｎの公開鍵ｐｋを用いて暗号化する関数である暗号化関数をＥｎｃ（または単にＥ）、秘密鍵ｓｋを用いて復号する復号関数をＤｅｃとすると、
【数２】
2016012111.tif 000004
を満たす写像Ｆの存在と、実行が保証される。準完全準同型暗号方式は公開鍵暗号方式である。ここで、Ｆは写像としたが、アルゴリズムであっても良い。さらに、写像Ｆは、加算および乗算の組み合わせによって表現可能であるとする。
【００１７】
上の数式（３）は次のことを意味する。左辺のプロセスをプロセスＡと呼び、右辺のプロセスをプロセスＢと呼ぶ。簡単のために、平文ｍ１を考える。プロセスＡの暗号化のステップでは、平文ｍ１を公開鍵ｐｋを用いて暗号化し、暗号データｃ＝Ｅｎｃ（ｍ１）を得る。そして、この暗号データｃについて、公開鍵ｐｋを用いて所定の写像（アルゴリズム）Ｆを作用させる処理が行われ、処理結果ｒを得る。続いて、復号のステップでは、秘密鍵ｓｋを用いて、処理結果ｒの復号処理が行われ、復号結果Ｒ＝Ｄｅｃ（Ｆ（Ｅｎｃ（ｍ１））が生成される。
【００１８】
一方プロセスＢでは、平文ｍ１について、所定の写像（アルゴリズム）Ｆを作用させる処理が行われ、処理結果Ｒ’＝Ｆ（ｍ１）を得る。
【００１９】
上式は、プロセスＡの結果ｒ＝Ｄｅｃ（Ｆ（Ｅｎｃ（ｍ１））と、プロセスＢの結果Ｒ’＝Ｆ（ｍ１）が等しいことを意味する。
【００２０】
さらに、平文ｍ１、ｍ２、…、ｍｎに対する準同型性は、
【数３】
2016012111.tif 000005
を意味する。ここで右辺では、暗号化関数Ｅｎｃの引数は、Ｆ（ｍ１、ｍ２、…、ｍｎ）の一つだけであることに注意する。（任意のＦに対して数４が成り立つとき完全準同型性を持つと呼ぶが、上記で説明したイデアル準同型暗号は有限回の加算と乗算の組み合わせで得られる写像Ｆに対してのみ準同型性をもつため、この暗号方式は準完全準同型暗号と呼ぶ）コメント：実際に完全準同型暗号を構成するためには、上記で説明した準完全準同型暗号を変形させる必要があるが、その変形方法は上記では述べていない。
【００２１】
鍵生成の方法には次のようなものがある。
鍵生成を行う際、次元ｎとビット長ｔの２つのパラメータが必要である。次元ｎとビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）を生成する。このとき、秘密鍵を、行列
【数４】
2016012111.tif 000006
とする。
【００２２】
また、上の行列Ｖのエルミート標準形である行列Ｂを公開鍵とする。エルミート標準形とは、整数行列に対して整数上の行基本変形を施して得られる下または上三角行列である。一般に、エルミート標準形が効率的に計算できることはよく知られており、公開鍵として行列Ｖのエルミート標準形である行列Ｂを用いることで、計算時間を短縮することができる。
【００２３】
暗号化について説明する。１ビットの平文ｂに対して公開鍵Ｂを用いて暗号化する場合、まず成分が０または１のｎ次元乱数ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を選び、ｅ１=（１、０、…、０）として、ベクトルａ：
【数５】
2016012111.tif 000007
を生成する。このようにして得られたベクトルａをフレッシュ暗号文と呼ぶことがある。
【００２４】
１ビットの平文ｂの暗号文ｃは、
【数６】
2016012111.tif 000008
のように生成する。ここで、Ｂ−１は行列Ｂの逆行列とし、“ｑ”は有理数ｑに最も近い整数値を与える関数とする。
【００２５】
１ビットの平文ｂの暗号文ｃの復号は、まず［数８］で定義されるｎ次元ベクトルａ’、
【数７】
2016012111.tif 000009
を計算する。次に、ｎ次元ベクトルａ’の第１成分ａ０’を取り、整数ａ０’を２で割った余りが暗号文ｃを復号した値になる。
【００２６】
また、別の復号方法として、次のような方法が知られている。暗号文ａの第１成分をｃとする。また、ｗを秘密鍵Ｖの逆行列Ｖ−１の要素であり、かつ、奇数のものとする。さらに、
【数８】
2016012111.tif 000010
で、値域が［−ｄ／２、ｄ／２）なるものである。［数９］で、ｄは公開鍵Ｂの判別式とする。このとき、
【数９】
2016012111.tif 000011
によって、暗号文ｃを定義する。
【００２７】
暗号文ｃを、秘密鍵Ｖを用いて復号する場合、まず［数８］で定義される４次元ベクトルａ’を計算する。次に、ｎ次元ベクトルａ’の第１成分ａ０’を取り、整数ａ０’を２で割った余りが暗号文ｃを復号した値になる。
【００２８】
上では、平文ｂが１ビットの場合を説明したが、平文の定義域を拡張することができる。平文ｂが｛０、１、…、ｓ−１｝から選択される、すなわち平文空間サイズがｓであるときも、上と同様の方法で、暗号化、復号を行うことができる。
【００２９】
平文空間サイズs以下の平文ｂに対して公開鍵Ｂを用いて暗号化する場合、まず成分が０または１のｎ次元乱数ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を選び、ベクトルａ：
【数１０】
2016012111.tif 000012
を生成する。上と同様、ｅ１=（１、０、…、０）である。このベクトルａもフレッシュ暗号文と呼ぶことがある。平文ｂの暗号文ｃは、上の［数７］と同様、
【数１１】
2016012111.tif 000013
で与えられる。ここでベクトルｃ=（ｃ、０、…、０）となることから、暗号文ｃは整数である。
【００３０】
平文ｂの暗号文ｃの復号は、まず以下のように定義されるｎ次元ベクトルａ’、
【数１２】
2016012111.tif 000014
を計算する。次に、ｎ次元ベクトルａ’の第１成分ａ０’を取り、整数ａ０’を平文空間サイズｓで割った余りが暗号文ｃを復号した値になる。この復号処理は、ベクトルｃに対して行列Ｖ−１を乗算する処理、及び、その乗算によって得られたベクトルに対し、行列Ｖを乗算する処理を行う。つまり、ベクトルと行列の積の計算を２回行うこととなる。このときの乗算回数は、ベクトルの要素数Ｄに比例し２×Ｄ２回となる。また、扱うデータが大きい場合、乗算１回は多倍長の乗算となる。
【００３１】
暗号データの加算と乗算を説明する。上記の数値例のように、暗号文は必ず第一成分以外が０となるｎ次元ベクトルｃ=（ｃ１、０、…）として表せる。この暗号文の第１成分の整数は、平文ｂと平文空間サイズｓと暗号化で利用するｎ次元ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を用いて、
【数１３】
2016012111.tif 000015
として計算することも可能である。ただし、［ｘ］ｄは、
【数１４】
2016012111.tif 000016
であり、値域が［−ｄ／２、ｄ／２）なる整数であり、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分である。これにより、暗号文を整数データとしてみなすことができる。
【００３２】
２つの暗号文ｃ１、ｃ２に対し、暗号加算は[ｃ１＋ｃ２]ｄ、暗号乗算は[ｃ１×ｃ２]ｄとして定義される。
【００３３】
上のような準同型暗号の性質を、２つのベクトルデータの比較に適用するためには、例えば以下のようにすれば良い。
【００３４】
ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）とベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）があるとする。ここでは、ベクトルデータＡとベクトルデータＢは、ｎ次元ベクトル量として書けるものとする。
【００３５】
ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）に対して、変換多項式、
【数１５】
2016012111.tif 000017
を計算する。このように、変換多項式ａ（ｘ）では、ベクトルデータＡの要素を累乗の昇順に並べる。そして、変換多項式ａ（ｘ）を暗号化して暗号データＥｎｃ（ａ（ｘ））を計算する。今の場合、
【数１６】
2016012111.tif 000018
とする。
【００３６】
ベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）に対して、変換多項式、
【数１７】
2016012111.tif 000019
を計算する。このように、変換多項式ｂ（ｘ）では、ベクトルデータＢの要素を累乗の降順に並べる。そして、変換多項式ｂ（ｘ）を暗号化して暗号データＥｎｃ（ｂ（ｘ））を計算する。ベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）に対する変換多項式は、ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）に対するものとは異なっている。
【００３７】
＜準同型暗号を用いた秘匿距離計算＞
次に、秘匿距離計算を行うために、事前に２つの整数Ｃ１、Ｃ２を用意する。の整数Ｃ１、Ｃ２は次の［数１８］で定義される。
【数１８】
2016012111.tif 000020
このとき、秘匿距離ｄは、
【数１９】
2016012111.tif 000021
である。［数１９］で、Ｃ１×Ｅｎｃ（ａ（ｘ））、Ｃ２×Ｅｎｃ（ｂ（ｘ））はそれぞれ、暗号文上のハミング重みＨＷ（ａ）、ＨＷ（ｂ）に対応する。上の秘匿距離ｄを復号すると、２つのベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）とベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）のハミング距離となる。上記では秘匿距離としてハミング距離を用いたが、開示の方法は、ユークリッド距離などの距離計算やコサイン類似度などの類似度計算にも適用可能である。
【００３８】
また、[数１８]、[数１９]を用いた計算式以外にも、次のような計算が存在する。
たとえば、
【数２０】
2016012111.tif 000022
とし、
【数２１】
2016012111.tif 000023
に対して、秘匿距離ｄを
【数２２】
2016012111.tif 000024
としても良い。
【００３９】
上記のように、まず、暗号鍵生成について、主に３つの鍵生成パラメータ(ｎ、ｑ、ｔ)が必要である。ｎは２冪の整数で格子次元と呼ばれ、ｑは素数、ｔは素数qよりも小さい整数とする。暗号鍵生成の手順として、まず秘密鍵として各係数が非常に小さいｎ次元の多項式ｓｋをランダムに生成する（各係数の小ささはあるパラメータσで制限されてもよい）。次に、各係数がｑより小さいｎ次元多項式ａ１と各係数が非常に小さいｎ次元多項式ｅをランダムに生成する。そこで、ａ０＝−(ａ１×ｓｋ ＋ｔ×ｅ)を計算し、組（ａ０、ａ１）を公開鍵ｐｋと定義する（ただし、ａ０の多項式計算時において、ｎ次以上の多項式に対してｘｎ＝−１、ｘｎ＋１＝−ｘ、...、と計算することで、ｎ次より小さい多項式を計算する。さらに、多項式の係数については、素数ｑで割った余りを出力する（このような演算を行う空間を、Ｒｑ＝Ｆｑ[ｘ]／（ｘｎ＋１)と表すことがある）。次に、各係数がｔより小さいｎ次多項式で表される平文データｍと公開鍵ｐｋ＝（ａ０、ａ１）に対して、まず各係数が非常に小さい３つのn次元多項式ｕ、ｆ、ｇをランダムに生成し、平文データｍの暗号データＥｎｃ（ｍ、ｐｋ）＝（ｃ０、ｃ１）を次のように定義する。（ｃ０、ｃ１）については、
【数２３】
2016012111.tif 000025
と計算する。このとき、これらの計算も空間Ｒｑ上の演算を用いる。次に、２つの暗号文Ｅｎｃ（ｍ１、ｐｋ）＝（ｃ０、ｃ１）とＥｎｃ（ｍ２、ｐｋ）＝（ｄ０、ｄ１）に対して、暗号加算Ｅｎｃ（ｍ１、ｐｋ）＋Ｅｎｃ（ｍ２、ｐｋ）を（ｃ０＋ｄ０、ｃ１＋ｄ１）と計算し、暗号乗算Ｅｎｃ（ｍ１、ｐｋ）×Ｅｎｃ（ｍ２、ｐｋ）を（ｃ０＋ｄ０、ｃ０×ｄ１＋ｃ１×ｄ０、ｃ１×ｄ１）と計算する。ここで、暗号乗算を行うと、暗号文のデータサイズが２成分ベクトルから３成分ベクトルになる。
【００４０】
最後に、復号処理であるが、複数の暗号乗算などの暗号操作などにより暗号文データの成分が増大したと仮定すると、暗号文ｃ＝（ｃ１、ｃ２、ｃ３、・・・）に対して、秘密鍵ｓｋを用いてＤｅｃ（ｃ、ｓ）＝［ｃ０＋ｃ１×ｓｋ＋ｃ２×ｓｋ２＋・・・］ｑ  ｍｏｄ   ｔを計算することで、復号する。ここで、［ｚ］ｑの値は、整数ｚのｑで割った余りｗを計算し、ｗ＜ｑなら［ｚ］ｑ＝ｗを出力し、そうでなければ［ｚ］ｑ＝ｗ―ｑを出力する。さらに、ａ  ｍｏｄ  ｔは整数aをtで割った余りを意味する。
【００４１】
以上のように、開示の方法は次のような特徴を有している。
（１）格子ベース準同型暗号を利用する、
（２）特徴量を表すベクトルを変換多項式によって多項式に変換する、
（３）変換多項式の暗号文とベクトルのハミング重みなどの重みの暗号文を用いる、
（４）秘匿距離計算として準同型暗号の多項式演算に関する準同型性を利用する。
このように、ハミング距離などの秘匿距離の計算に、準同型暗号を用いることによって、暗号データサイズと計算時間の大幅な削減が可能となる。
【００４２】
上のイデアル格子ベース準同型暗号の暗号化、復号は、次のように説明することもできる。
【００４３】
まず、用語を簡単に定義する。
格子とはＺを整数環として、Ｚｎ中の離散的な加法的部分群である。Ｚｎ中でｂ０、…、ｂｎ−１が線形独立だとすると、これらを並べて作られる正方行列Ｂ＝［ｂ０、…、ｂｎー１］を基底と呼ぶ。格子Ｌは、ｖをＺｎの要素として、
【数２４】
2016012111.tif 000026
と書くことができる。
【００４４】
格子Ｌがイデアル格子であるとは、格子Ｌと同型な環Ｒ＝Ｚ［ｘ］／ｆ（ｘ）のイデアルＩが存在することである。ここで、Ｚ［ｘ］は整数係数多項式環、ｆ（ｘ）は整数係数モニックなｎ次多項式である。
【００４５】
剰余環Ｒの１つの元、
【数２５】
2016012111.tif 000027
で生成される単項イデアルの元は、ａ、ａ・ｘ、ａ・ｘ２、ａ・ｘｎ−１の線形結合で書ける。ａの転置をａＴと書く。
【００４６】
ｆ（ｘ）＝ｘｎ＋１として、環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）の整数係数モニック多項式ａ（ｘ）＝ａ０＋ａ１ｘ＋…＋ａｎ-１ｘｎ−１を考える。ベクトルａ＝（ａ０、ａ１、…、ａｎ−１）を環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）と同一視するためには、次のようにする。ａに対して巡回行列を定義する。
【数２６】
2016012111.tif 000028
これは上の［数５］と同一である。すると、２つの多項式ａ（ｘ）、ｂ（ｘ）に対して、積をａ（ｘ）・ｂ（ｘ）＝Ｒｏｔ（ａ）・ｂによって定義することができる。また、巡回行列Ｒｏｔ（ａ）は、基底行列となる。
【００４７】
すると、上の格子ベースの準同型暗号方法における鍵生成とは次のようなことである。つまり、環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）のイデアルＩと互いに素なイデアルＪの基底行列を秘密鍵Ｖ、公開鍵Ｂはその基底行列のエルミート標準形である。たとえば、秘密鍵はＲをランダム、かつノルムの小さな行列として、ｎ１／２Ｉ＋Ｒとすることができる。
【００４８】
このとき、暗号化は、平文ｂの暗号文ｃは、ｒをＲから選び、ｃ＝ｂ＋ｒｓ  ｍｏｄ  Ｂの第１成分とする。平文ｂのノルムが小さければ、ｂ＝（ｃ  ｍｏｄ  Ｂ）ｍｏｄ  Ｉにより復号することができる。
【００４９】
上記のような格子ベースの準完全準同型暗号を用いてハミング距離などの秘匿距離を計算することによって、暗号ベクトルデータのサイズと秘匿距離計算の時間の両方を削減することができる。
【００５０】
なお上記の準同型演算は、イデアル格子、Ｒｉｎｇ−ＬＷＥベースのいずれを用いてもよい。
【００５１】
上で説明した準同型暗号方式は、生体認証システムだけでなく、タグ検索システムなどへの応用が考えられる。
【００５２】
＜比較例＞
図１は、暗号処理装置の一例として生態認証システムの概要を説明するための図である。
【００５３】
準同型暗号方式の応用例として、秘匿生体認証システムへの適用などのシーンが考えられる。準同型暗号を利用した秘匿生体認証システムの図１を用いて、説明する。このシステムは、指紋や静脈などの生体情報を利用した個人認証システムである。生体情報を利用した個人認証システムは、パスワードなどの複雑な情報を覚える必要がないため利用しやすい個人認証方式である反面、生体情報は各ユーザにとって終生不変な機密情報であるので生体情報漏洩などに対して強く保護しなければならないという課題がある。
【００５４】
図２は、比較例における準同型暗号を利用した生体認証システムの概要を示す図である。
【００５５】
図２に示した生体認証システム１０では、ユーザの生体情報を準同型暗号で保護しつつ認証が可能となる方式である。システム１０は、クライアント端末１００（以下、クライアント端末を単に端末と呼ぶことがある）、計算サーバ１１０、認証サーバ１２０を含んでいる。
【００５６】
生体情報の登録時に生体認証システム１０は、ユーザは指紋や静脈などの生体情報を端末１００に入力する。端末１００のバイナリ化部１００２は特徴量を抽出し生体情報をベクトル化しベクトルＡを得る。さらに暗号化部１００４でベクトルＡの多項式変換と準同型暗号化を行う。以下では、たとえば、ベクトルＡを多項式１（たとえば［数１４］のａ（ｘ））で多項式変換をし、準同型暗号化をしたものをＥ１（Ａ）と表す。別の例としては、ベクトルＢを多項式２（たとえば［数１６］のｂ（ｘ））で多項式変換をし、準同型暗号化をしたものをＥ２（Ｂ）と表す。暗号化部１００４での暗号化の際には、公開鍵１００６を用いる。また、登録でも暗号化部１０１２で公開鍵１０１２を用いて暗号化をすることもある。そして端末１００は、準同型暗号化した生体情報Ｅ１（Ａ）を計算サーバ１１０に送り、計算サーバ１１０は、準同型暗号化した生体情報を、データベース（準同型暗号化テンプレート）１１０２に登録する。このとき、生体情報Ｅ１（Ａ）と一緒に、Ｅ１（Ｃ）、Ｅ２（Ｃ）をデータベース（準同型暗号化テンプレート）１１０２に登録しても良い。
【００５７】
照合時にユーザは、端末１００に生体情報を入力し、バイナリ化部１００８で生体情報をベクトル化してベクトルＢを得る。暗号化部１０１０でベクトルＡの多項式変換と準同型暗号化を行う。暗号化部１０１０での暗号化の際には、公開鍵１０１２を用いる。端末１００は、ベクトル化生体情報を準同型暗号化したデータＥ２（Ｂ）を計算サーバ１１０に送信し、計算サーバ１１０はデータベース１１０２に格納されているデータ（準同型暗号化テンプレート）を参照して、準同型暗号データ１１０４（Ｅ１（Ａ））と準同型暗号データ１１１６（Ｅ２（Ｂ））との秘匿距離を計算する。そして計算サーバ１１０は、秘匿距離計算結果のみを準同型暗号の秘密鍵１２０４を持つ認証サーバ１２０に送信する。認証サーバ１２０の比較部１２０２は、受信した秘匿距離計算結果を復号し、復号結果と閾値を比較し、復号結果が閾値よりも小さい場合は、ユーザを認証する。
【００５８】
生体認証システム１０において、２つの生体ベクトルデータを比較する際にはよくハミング距離計算を用いる。図２に示されている秘匿生体認証システム１０の秘匿距離計算処理として、２つのベクトルデータを準同型暗号化した状態で、ハミング距離を計算することとする。図２の秘匿生体認証システムでは、計算サーバ１１０には準同型暗号化生体ベクトル情報をのみを送信し、計算サーバは秘密鍵を持たないため、ユーザの生体情報を知ることはできず、認証局も秘匿距離計算結果のみを復号するので、ユーザの生体情報（ベクトル化生体情報）を知ることはできない。これにより、秘密鍵を持つ認証サーバ１２０と計算サーバ１１０の両方が結託しない限り、ユーザの生体情報を保護したまま個人認証サービスを受けることができる。
【００５９】
図３〜７を参照して、比較例の生体認証システム１０について、より詳細に説明する。
図３は、比較例における準同型暗号を利用した生体認証システムの端末の機能ブロックの例を示す図である。
【００６０】
生体認証システムの端末１００のセンサ部１０１６はユーザの生体画像を取得する。
バイナリ特徴コード部１０１８は、センサ部１０１６で取得された生体画像を二値化するなどして、特徴コードを生成する。
【００６１】
多項式変換部１０２２は、登録／照合切替部１０２０に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、特徴コードを多項式変換して、多項式コードを出力する。
【００６２】
準同型暗号処理部１０２４は、公開鍵１００６を用いて、多項式コードを暗号化する。準同型暗号処理部１０２４は、暗号化テンプレート／暗号化照合データを出力し、送信部１０２６から送信する。
【００６３】
そして、センサ部１０１６、バイナリ特徴コード部１０１８、多項式変換部１０２２、準同型暗号処理部１０２４、送信部１０２６は制御部１０１４によって制御され得る。
【００６４】
図４は、比較例における準同型暗号を利用した生体認証システムの計算サーバ１１０の機能ブロック（登録時）の例を示す図である。
【００６５】
受信部１１１０は、端末１００から暗号化テンプレートを受信する。その暗号化テンプレートは、テンプレート登録部１１１２によって、暗号化テンプレートが格納されるデータベース１１１４に保存される。
【００６６】
図５は、比較例における暗号化テンプレートのデータフォーマットの例を示す図である。暗号化テンプレート１１６、たとえばユーザＩＤと暗号化テンプレートＥ１（Ａ）、Ｅ１（Ｃ）、Ｅ２（Ｃ）を含んでいる。
【００６７】
図６は、比較例における準同型暗号を利用した生体認証システムの計算サーバ１１０の機能ブロック（照合時）の例を示す図である。
【００６８】
受信部１１１０は、端末から暗号化照合データを受信する。暗号化照合データは、たとえばユーザＩＤと暗号化照合データＥ２（Ｂ）を含んでいる。
【００６９】
準同型乗算部１１１６は、暗号化テンプレート保存部１１１２からＥ１（Ａ）と、定数Ｅ２（Ｃ）を用いて両者の掛け算ｘ＝Ｅ１（Ａ）×Ｅ２（Ｒ）を計算する。
【００７０】
準同型乗算部１１１８は、暗号化照合データからＥ２（Ｂ）と、定数Ｅ１（Ｃ）を用いて両者の掛け算ｙ＝Ｅ１（Ｃ）×Ｅ２（Ｂ）を計算する。
【００７１】
準同型乗算部１１２０は、暗号化テンプレート保存部１１１２からＥ１（Ａ）と、暗号化照合データからＥ２（Ｂ）を用いて両者の掛け算ｚ＝Ｅ１（Ａ）×Ｅ２（Ｂ）を計算する。
【００７２】
準同型加算部１１２２は、準同型乗算部１１１６、準同型乗算部１１１８、準同型乗算部１１２０からの出力ｘ、ｙ、ｚを用いて、暗号化ハミング距離Ｅ（ＨＤ）＝ｘ＋ｙ−２ｚを計算する。
【００７３】
準同型加算部１１２２は、準同型乗算部１１１６、準同型乗算部１１１８、準同型乗算部１１２０、準同型加算部１１２２は組み合わされて暗号化ハミング距離計算部１１１４を構成する。
送信部１１２４は、暗号化ハミング距離Ｅ（ＨＤ）を送信する。
【００７４】
図７は、比較例における準同型暗号を利用した生体認証システムの認証サーバ１２０の機能ブロックの例を示す図である。
【００７５】
認証サーバ１２０の受信部１２０８は、計算サーバ１１０から暗号化ハミング距離Ｅ（ＨＤ）を受信する。
【００７６】
準同型復号部１２１０は、秘密鍵１２０４を用いて、暗号化ハミング距離Ｅ（ＨＤ）を復号してハミング距離ＨＤを得る。
【００７７】
比較部１２１２は、ハミング距離ＨＤを予め与えられた閾値θと比較する。ハミング距離ＨＤが閾値θより小さければユーザは認証され（ＯＫ）、そうでなければユーザは認証されない（ＮＧ）。
【００７８】
送信部１２１４は、比較部１２１２の比較結果（ＯＫ／ＮＧ）を送信する。
図８は、比較例における準同型暗号を利用した生体認証方法の登録時の処理の流れの例を示す図である。
【００７９】
処理が開始されるとＳ１００でクライアント端末１００のバイナリ化部１００２は、生体認証のために登録される登録画像を用いて特徴コードＡを生成する。
【００８０】
次のＳ１０２で端末１００の暗号化部１００４は、特徴コードＡを暗号化し、暗号文Ｅ１（Ａ）を得る。Ｓ１０２の処理が終了すると、処理はＳ１０４に進む。
【００８１】
Ｓ１０４で端末１００の送信部１０２６は、暗号文Ｅ１（Ａ）を送信する。Ｓ１０４の処理が終了すると、処理はＳ１０６に進む。
【００８２】
Ｓ１０６で計算サーバ１１０の受信部１１１０は、暗号文Ｅ１（Ａ）を受信する。Ｓ１０６の処理が終了すると、処理はＳ１０８に進む。
【００８３】
Ｓ１０８で計算サーバ１１０のテンプレート登録部１１１２は、暗号文Ｅ１（Ａ）をデータベース１１０２に格納する。
【００８４】
図９は、比較例における準同型暗号を利用した生体認証方法の照合時の処理の流れの例を示す図である。
【００８５】
処理が開始されるとＳ２００でクライアント端末１００のバイナリ化部１００８は、照合に用いられる照合画像を用いて特徴コードＢを生成する。
【００８６】
次のＳ２０２で端末１００の暗号化部１０１０は、特徴コードＢを暗号化し、暗号文Ｅ２（Ｂ）を得る。Ｓ２０２の処理が終了すると、処理はＳ２０４に進む。
【００８７】
Ｓ２０４で端末１００の送信部１０２６は、暗号文Ｅ２（Ｂ）を送信する。Ｓ２０４の処理が終了すると、処理はＳ２０６に進む。
【００８８】
Ｓ２０６で計算サーバ１１０の受信部１１１０は、暗号文Ｅ２（Ｂ）を受信する。Ｓ２０６の処理が終了すると、処理はＳ２０８に進む。
【００８９】
Ｓ２０８で計算サーバ１１０の暗号化ハミング距離計算部１１１４は、Ｅ１（Ａ）とＥ２（Ｂ）の秘匿距離Ｅ（ＨＤ）を計算する。準同型乗算部１１１６で得られるｘ＝Ｅ１（Ａ）×Ｅ２（Ｃ）、準同型乗算部１１１８で得られるｙ＝Ｅ１（Ｃ）×Ｅ２（Ｂ）、準同型乗算部１１２０で得られるｚ＝Ｅ１（Ａ）×Ｅ２（Ｂ）を用いて、暗号化ハミング距離Ｅ（ＨＤ）＝ｘ＋ｙ−２ｚを計算する。このとき、データベース１１０２に格納されている準暗号化テンプレートＥ１（Ａ）を参照する。
【００９０】
またＳ２０８で計算サーバ１１０の送信部１１２４は、暗号化ハミング距離Ｅ（ＨＤ）を送信する。Ｓ２０８の処理が終了すると、処理はＳ２１０に進む。
【００９１】
Ｓ２１０で認証サーバ１２０は、暗号化ハミング距離Ｅ（ＨＤ）を復号し、ハミング距離ＨＤを予め与えられた閾値θと比較する。ハミング距離ＨＤが閾値θより小さければユーザは認証され（ＯＫ）、そうでなければユーザは認証されない（ＮＧ）。
【００９２】
秘匿生体認証システム１０において、生体情報は、計算サーバでは暗号化されて登録されるため、生の生体情報が漏れることはなく安全であると言える。しかし、ユーザがこのシステム１０を利用しなくなった場合に、暗号化された生体情報をシステムの鍵を変えることなくユーザが簡便にキャンセルすることはできない。
【００９３】
以下で説明する実施例は、準同型暗号を利用した秘匿生体認証システムにおいて、計算サーバの処理負荷を大きく増加させることなく、ユーザによる登録された暗号化生体情報をキャンセルする処理を実現する。
【００９４】
＜実施例＞
以下、図１０〜２２を参照して実施例の暗号処理装置（生体認証システム）について説明する。以下では、平文Ａを多項式１で多項式化したのち準同型暗号化したものをＥ１（Ａ）と表わすことがある。以下では、主に生体認証システムについて説明するが、生体認証システムのほか、タグ検索システムなどへの応用が可能である。
【００９５】
実施例の暗号処理装置（生体認証システム）は、ユーザが保管する乱数でテンプレートや照合データをマスクし、それを準同型暗号で二重に暗号化して送信する。そして実施例の暗号処理装置は、二重暗号化されたまま照合処理を行い、照合処理でマスクをキャンセルするマスクはユーザが変更できるので、ユーザによる登録生体情報のキャンセル（無効化）が可能である。
【００９６】
以下でも、既に説明した準同型暗号方式を利用する。登録用の生体情報を表すベクトルデータＡ＝（ａ０、ａ１、・・・）と照合時の生体情報を表すベクトルデータＢ＝（ｂ０、ｂ１、・・・）を暗号化して、秘匿距離を計算する場合を考える。本例では、秘匿距離はハミング距離を用いるが、他の距離を用いても良い。
【００９７】
まず加算マスクと呼ぶ方法について説明する。
この場合は、ユーザ固有かつ秘匿された暗号学的に安全な乱数ベクトルＲ＝（ｒ０、ｒ１、・・・）を生成する。乱数ベクトルＲを単に乱数とも呼ぶこともある。続いて公開鍵ｐｋを用いてＡ、Ｒを２種類の多項式化と準同型暗号Ｅで暗号化し、暗号文Ｅ１（Ｒ）、Ｅ２（Ｒ）を計算する。多項式化と準同型暗号化に関しては、既に説明したものを使用し得る。２種類の多項式化は、第１の変換多項式は第１のベクトルの要素を累乗の昇順に並べ、第２の変換多項式は第２のベクトルの要素を累乗の降順に並べる、または第１の変換多項式は第１のベクトルの要素を累乗の降順に並べ、第２の変換多項式は前記第２のベクトルの要素を累乗の昇順に並べるものであっても良い。上記［数１５］、［数１７］はそのような多項式の組の例である。乱数（乱数ベクトル）Ｒは不揮発性メモリなどのメモリに格納しておいても良い。ただし、乱数Ｒは外部から書き換え可能であるとする。同様に、ベクトルＢに対しても、乱数Ｒ、公開鍵ｐｋに対して準同型暗号を用いた暗号文 Ｅ２（Ｂ＋Ｒ）を計算する。準同型暗号の性質から、二つの暗号文から、ふたつの平文ベクトルのハミング距離ＨＤ（Ａ、Ｂ）の暗号文を生成することができる。
【数２７】
2016012111.tif 000029
ここで、ユーザは乱数ベクトルＲをＲ´に変更することで、システムの変更なく登録された暗号化生体情報をキャンセルすることができる。また、そのために増加する計算量は、準同型暗号加算２回、保存しなければならない情報が暗号化生体情報Ｅ１（Ａ）だけから、Ｅ１（Ａ）、Ｅ２（Ｒ）と２倍に過ぎない。
【００９８】
また、乗算マスクと呼ぶ方法も存在する。
この場合は、ユーザ固有かつ秘匿された暗号学的に安全な乱数ベクトルＲ＝（ｒ０、ｒ１、・・・）を生成し、その逆元Ｒ−１＝（ｒ０−１、ｒ１−１、・・・）を計算する。そしてその乱数ベクトルＲを用いて生体情報を表すベクトルＡに対し、各項の乗算演算を行う。すなわちＡ×Ｒ−１＝（ａ１×ｒ１−１、ａ２×ｒ２−１、・・・）を計算する。続いて公開鍵ｐｋを用いてＡ×Ｒ−１、Ｒ、Ｒ−１を２種類の多項式化と準同型暗号Ｅで暗号化し、Ｅ１（Ａ×Ｒ−１）、Ｅ１（Ｒ−１）、Ｅ２（Ｒ）を計算する。多項式化と準同型暗号化に関しては、既に説明したものを使用し得る。同様に、ベクトルＢに対しても、乱数Ｒ、公開鍵ｐｋに対して準同型暗号を用いた暗号文Ｅ２（Ｂ×Ｒ）を計算する。準同型暗号の性質から、２つの暗号文から、ふたつの平文ベクトルのハミング距離ＨＤ（Ａ、Ｂ）の暗号文を生成することができる。Ｒは不揮発性メモリなどのメモリに格納しておいても良い。
【数２８】
2016012111.tif 000030
ここで、ユーザは乱数ベクトルＲをＲ´に変更することで、システムの変更なく登録された暗号化生体情報をキャンセルすることができる。また、そのために増加する計算量は、元の計算量と全く同じであり、保存しなければならない情報が暗号化生体情報Ｅ１（Ａ）だけから、Ｅ１（Ａ×Ｒ−１）、Ｅ１（Ｒ−１）、Ｅ２（Ｒ）と３倍に過ぎない。
【００９９】
図１０は、実施例における準同型暗号を利用した生体認証システムの概要を示す図である。図１０に示されている生体認証システム２０を暗号処理装置と呼ぶこともある。
【０１００】
図１０に示した生体認証システム２０は、加算マスクを用いる場合、クライアント端末２００ａ（以下、クライアント端末を単に端末と呼ぶことがある）、計算サーバ２１０ａ、認証サーバ２２０を含んでいる。生体認証システム２０は、乗算マスクを用いる場合、クライアント端末２００ｂ（以下、クライアント端末を単に端末と呼ぶことがある）、計算サーバ２１０ｂ、認証サーバ２２０を含んでいる。
【０１０１】
生体情報の登録時に生体認証システム２０は、ユーザは指紋や静脈などの生体情報を端末２００ａ（２００ｂ）に入力する。端末２００のバイナリ化部２００２は特徴量を抽出し生体情報をベクトル化しベクトルＡを得る。さらに暗号化部２００４でベクトルＡと乱数Ｒの多項式変換と準同型暗号化を行い加算マスクの場合はＥ１（Ａ）、Ｅ２（Ｒ）（乗算マスクの場合は、Ｅ１（Ａ×Ｒ−１）、Ｅ１（Ｒ−１）、Ｅ２（Ｒ））を得る。Ｅ２（Ｒ）（加算マスクの場合）、（乗算マスクの場合は、Ｅ１（Ｒ−１）、Ｅ２（Ｒ））を乱数多項式と呼ぶことがある。ベクトルＡと乱数Ｒは別々の多項式で変換される。多項式１、２の例は、次のようなａ（ｘ）、ｂ（ｘ）であり得る。
【数２９】
2016012111.tif 000031
暗号化部２００４での暗号化の際には、公開鍵２００６を用いる。また、暗号化部２００４は乱数Ｒを格納するメモリを有している。このメモリは不揮発性メモリであっても良い。そして端末２００ａは、加算マスクの場合はＥ１（Ａ）、Ｅ２（Ｒ）（乗算マスクの場合は、Ｅ１（Ａ×Ｒ−１）、Ｅ１（Ｒ−１）、Ｅ２（Ｒ））を計算サーバ２１０ａに送り、計算サーバ２１０は、準同型暗号化した生態情報を、データベース２１０２に登録する。
【０１０２】
照合時にユーザは、端末２００に生体情報を入力し、バイナリ化部２００８で生体情報をベクトル化してベクトルＢを得る。端末２００ａのマスク部２０１０ではベクトルＢに対して加算マスクを施す。端末２００ｂのマスク部２０１０ではベクトルＢに対して乗算マスクを施す。暗号化部２０１２でベクトルＢ＋Ｒの多項式変換と準同型暗号化を行う。以下、端末２００ａ、端末２００ｂを単に端末２００と表現することがある。端末２００は、加算マスクまたは乗算マスクを用いる。
【０１０３】
暗号化部２０１２での暗号化の際には、公開鍵２０１４を用いる。端末２００ａは、加算マスクの場合、ベクトル化生体情報を準同型暗号化したデータＥ２（Ｂ＋Ｒ）（乗算マスクの場合は、Ｅ２（Ｂ×Ｒ））を計算サーバ２１０ａ（２１０ｂ）に送信する。
【０１０４】
計算サーバ２１０ａ（２１０ｂ）はデータベース（準同型暗号化テンプレート）２１０２に格納されているデータを参照して、秘匿距離計算部２１０４で加算マスクの場合は準同型暗号データＥ１（Ａ）と準同型暗号データＥ２（Ｂ）との秘匿距離を計算する。この計算の前にアンマスク部２１０６で準同型暗号データＥ２（Ｂ＋Ｒ）（加算マスクの場合）またはＥ２（Ｂ×Ｒ）（乗算マスクの場合）のアンマスクを行う。たとえば、Ｅ２（Ｂ＋Ｒ）をアンマスクするには、Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ）を計算する。Ｅ２（Ｂ×Ｒ）をアンマスクするには、Ｅ２（Ｂ×Ｒ）×Ｅ２（Ｒ−１）を計算する。そして計算サーバ２１０は、秘匿距離計算結果のみを準同型暗号の秘密鍵２２０４を持つ認証サーバ２２０に送信する。
【０１０５】
認証サーバ２２０の比較部２２０２は、受信した秘匿距離計算結果を復号し、復号結果と閾値を比較し、復号結果が閾値よりも小さい場合は、ユーザを認証する。
【０１０６】
図１１は、加算マスクを用いる実施例における準同型暗号を利用した生体認証システムの端末２００ａの機能ブロックの例を示す図である。
【０１０７】
端末２００ａのセンサ部２０１８はユーザの生体画像を取得する。
乱数入力部２０２２は、乱数の入力を受ける。乱数入力部２０２２はメモリであり、乱数が格納されていても良い。
【０１０８】
バイナリ特徴コード部２０２０は、センサ部２０１８で取得された生体画像を二値化するなどして、特徴コードを生成する。特徴コードはベクトルであっても良い。
【０１０９】
加算部２０２４は、特徴コードと乱数を加える。
切替２０２６は、登録／照合切替部２０２８に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、バイナリ特徴コード部２０２０からの出力を多項式変換部２０３０に入力するか（登録時）、加算部２０２４からの出力を多項式変換部２０３０に入力するか（照合時）を切り替える。
【０１１０】
多項式変換部２０３０は、登録／照合切替部１０２０に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、入力されたＡ（登録時）またはＢ＋Ｒ（照合時）を多項式変換して、多項式コードを出力する。
【０１１１】
準同型暗号処理部２０３４は、公開鍵２０３２を用いて、多項式コードを暗号化する。準同型暗号処理部２０３４は、暗号化テンプレート／暗号化照合データを出力し、送信部２０３６から送信する。
【０１１２】
センサ部２０１８、バイナリ特徴コード部２０２０、乱数入力部２０２２、加算部２０２４、切替２０２６、登録／照合切替部２０２８、多項式変換部２０３０、準同型暗号処理部２０３４、送信部２０３６は、制御部２０１６によって制御され得る。
【０１１３】
図１２は、乗算マスクを用いる実施例における準同型暗号を利用した生体認証システムの端末２００ｂの機能ブロックの別の例を示す図である。
【０１１４】
端末２００ｂのセンサ部２０４２はユーザの生体画像を取得する。
バイナリ特徴コード部２０５０は、センサ部２０４２で取得された生体画像を二値化するなどして、特徴コードを生成する。特徴コードはベクトルであっても良い。
【０１１５】
乱数入力部２０４６は、乱数の入力を受ける。乱数入力部２０４６はメモリであり、乱数が格納されていても良い。この場合、乱数が外部から書き換え可能であるとする。
【０１１６】
逆数計算部２０４４は、乱数の逆数を計算する。
切替２０４８は、登録／照合切替部２０５４に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、乗算部２０５２に乱数を入力するか、乱数の逆数を入力するかを切り替える。
【０１１７】
乗算部２０５２は、登録／照合切替部２０５４に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、登録時はＡ×Ｒ−１を、照合時はＢ×Ｒを計算する。
【０１１８】
多項式変換部２０５６は、登録／照合切替部１０５４に対して外部から入力される、登録時であるか照合時であるかを区別する命令に依存して、入力されたＡ×Ｒ−１（登録時）またはＢ×Ｒ（照合時）を多項式変換して、多項式コードを出力する。
【０１１９】
準同型暗号処理部２０６０は、公開鍵２０５８を用いて、多項式コードを暗号化する。準同型暗号処理部２０６０は、暗号化テンプレート／暗号化照合データを出力し、送信部２０６２から送信する。
【０１２０】
図１３は、乱数生成の例の概要を示す図である。
乱数入力部２０２２、２０４６に入力される乱数は、Ｐａｓｓｗｏｒｄ  Ｂａｓｅ  Ｋｅｙ  Ｄｅｒｉｖａｔｉｏｎ  Ｆｕｎｃｔｉｏｎ（ＰＢＫＤＦ）等を用いて、外部から入力されるパスワードや鍵から乱数生成部２０６４で生成されても良い。
【０１２１】
図１４は、実施例における準同型暗号を利用した生体認証システムの計算サーバ２１０ａ（２１０ｂ）の機能ブロック（登録時）の例を示す図である。
【０１２２】
受信部２１１０は、端末２００ａ（２００ｂ）から暗号化テンプレートを受信する。その暗号化テンプレートは、テンプレート登録部２１１２によって、暗号化テンプレート保存部２１０２に保存される。
【０１２３】
図１５Ａは、加算マスクを用いる実施例における暗号化テンプレートのデータフォーマットの例を示す図である。
【０１２４】
暗号化テンプレート／暗号化照合データ２１４２は、たとえばユーザＩＤと暗号化テンプレートＥ１（Ａ）、Ｅ１（Ｃ）、Ｅ２（Ｃ）、暗号化乱数Ｅ２（Ｒ）を含んでいる。
【０１２５】
図１５Ｂは、乗算マスクを用いる実施例における暗号化テンプレートのデータフォーマットの別の例を示す図である。
【０１２６】
暗号化テンプレート／暗号化照合データ２１４４は、たとえばユーザＩＤと暗号化テンプレートＥ１（Ａ×Ｒ−１）、暗号化乱数Ｅ２（Ｒ）、暗号化逆数Ｅ１（Ｒ−１）を含んでいる。
【０１２７】
図１６は、加算マスクを用いる実施例における準同型暗号を利用した生体認証システムの計算サーバ２１０ａの機能ブロック（照合時）の例を示す図である。
【０１２８】
受信部２１１０は、端末から暗号化照合データＥ２（Ｂ＋Ｒ）を受信する。
準同型加算部２１１４は、暗号化テンプレート保存部２１０２に格納されている乱数Ｅ２（Ｒ）を参照して、Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ）を計算する。
【０１２９】
準同型乗算部２１１６は、暗号化テンプレート保存部２１０２に格納されているＥ１（Ａ）と、Ｅ２（Ｃ）を用いて両者の掛け算ｘ＝Ｅ１（Ａ）×Ｅ２（Ｃ）を計算する。
【０１３０】
準同型乗算部２１１８は、暗号化テンプレート保存部２１０２に格納されているＥ１（Ｃ）と、暗号化照合データからＥ２（Ｂ）を用いて両者の掛け算ｙ＝Ｅ１（Ｃ）×（Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ））を計算する。
【０１３１】
準同型乗算部２１２０は、暗号化テンプレート保存部２１０２に格納されているＥ１（Ａ）と、暗号化照合データから（Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ））を用いて両者の掛け算ｚ＝Ｅ１（Ａ）×（Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ））を計算する。
【０１３２】
準同型加算部２０２２は、準同型乗算部２１１６、準同型乗算部２１１８、準同型乗算部２１２０からの出力ｘ、ｙ、ｚを用いて、暗号化ハミング距離Ｅ（ＨＤ）＝ｘ＋ｙ−２ｚを計算する。
【０１３３】
準同型加算部２１１４、準同型乗算部２１１６、準同型乗算部２１１８、準同型乗算部２１２０、準同型加算部２１２２は組み合わされて暗号化ハミング距離計算部（秘匿距離計算部）２１１２を構成する。
送信部２０２４は、暗号化ハミング距離Ｅ（ＨＤ）を送信する。
【０１３４】
図１７は、乗算マスクを用いる実施例における準同型暗号を利用した生体認証システムの計算サーバの機能ブロック（照合時）の別の例を示す図である。
【０１３５】
受信部２１１０は、端末から暗号化照合データＥ２（Ｂ×Ｒ）を受信する。
準同型乗算部２１３２は、暗号化照合データ２１０２からＥ１（Ａ×Ｒ−１）と、暗号化乱数Ｅ２（Ｒ）を用いて両者の掛け算ｘ＝Ｅ１（Ａ×Ｒ−１）×Ｅ２（Ｒ）を計算する。
【０１３６】
準同型乗算部２１３４は、暗号化照合データ２１０２からＥ２（Ｂ×Ｒ）と、暗号化逆数Ｅ１（Ｒ−１）を用いて両者の掛け算ｙ＝Ｅ２（Ｂ×Ｒ）×Ｅ１（Ｒ−１）を計算する。
【０１３７】
準同型乗算部２１３６は、暗号化テンプレート保存部２１０２からＥ１（Ａ）と、暗号化照合データから（Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ））を用いて両者の掛け算ｚ＝Ｅ１（Ａ）×（Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ））を計算する。
【０１３８】
準同型加算部２１３８は、準同型乗算部２１３２、準同型乗算部２１３４、準同型乗算部２１３６からの出力ｘ、ｙ、ｚを用いて、暗号化ハミング距離Ｅ（ＨＤ）＝ｘ＋ｙ−２ｚを計算する。
【０１３９】
送信部２１４０は、暗号化ハミング距離Ｅ（ＨＤ）を送信する。
準同型乗算部２１３２、準同型乗算部２１３４、準同型乗算部２１３６、準同型加算部２１３８は組み合わされて暗号化ハミング距離計算部（秘匿距離計算部）２１３０を構成する。
【０１４０】
図１８は、実施例における準同型暗号を利用した生体認証システムの認証サーバ２２０の機能ブロックの例を示す図である。
【０１４１】
認証サーバ２２０の受信部２２０８は、計算サーバ２１０から暗号化ハミング距離Ｅ（ＨＤ）を受信する。
【０１４２】
準同型復号部２２１０は、秘密鍵２２０４を用いて、暗号化ハミング距離Ｅ（ＨＤ）を復号してハミング距離ＨＤを得る。
【０１４３】
比較部２２１２は、ハミング距離ＨＤを予め与えられた閾値θと比較する。ハミング距離ＨＤが閾値θより小さければユーザは認証され（ＯＫ）、そうでなければユーザは認証されない（ＮＧ）。
【０１４４】
送信部２２１４は、比較部２２１２の比較結果（ＯＫ／ＮＧ）を送信する。
このように暗号処理装置２０は、多項式変換部２０３０、３０５６と、暗号化部２０３４、２０５８と、秘匿距離計算部２１１２、２１３０と、比較部２２１２を含む。
【０１４５】
多項式変換部２０３０、３０５６は、第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得する。。
【０１４６】
暗号化部２０３４、２０５８は、第１の多項式と第２の多項式と乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得する。
【０１４７】
比較部は、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを用いて、第１のデータと前記第２のデータとの照合を行う。
【０１４８】
秘匿距離計算部２１１２、２１３０は、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを用いて、復号すると第１のデータと第２のデータの間の秘匿距離となる暗号化秘匿距離を算出してもよい。この場合、比較部２２１２は、第１のデータと第２のデータとの照合を、秘匿距離と所定の値との比較によって行い得る。
【０１４９】
ここで、乱数は、第１のベクトルと一対一の対応関係を有しても良い。
上記のような構成を採用することによって暗号処理装置は、準同型暗号を利用した暗号処理システムにおいて、暗号化された情報を簡便にキャンセルすることができるという効果を奏する。
【０１５０】
図１９は、準同型暗号を利用した暗号処理装置の構成の例を示す構成図である。準同型暗号装置は、汎用コンピュータ５００として実現され得る。
【０１５１】
このコンピュータ３００は、ＣＰＵ３０２、ＲＯＭ３０４、ＲＡＭ３０６、ハードディスク装置３０８、入力装置３１０、表示装置３１２、インタフェース装置３１４、及び記録媒体駆動装置３１６を備えている。なお、これらの構成要素はバスライン３２０を介して接続されており、ＣＰＵ３０２の管理の下で各種のデータを相互に授受することができる。
【０１５２】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０２は、このコンピュータ３００全体の動作を制御する演算処理装置であり、コンピュータ３００の制御処理部として機能する。
【０１５３】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＣＰＵ３０２は、この基本制御プログラムをコンピュータ３００の起動時に読み出して実行することにより、このコンピュータ３００の各構成要素の動作制御が可能になる。
【０１５４】
ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０６は、ＣＰＵ３０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【０１５５】
ハードディスク装置３０８は、ＣＰＵ３０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＣＰＵ３０２は、ハードディスク装置３０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【０１５６】
入力装置３１０は、例えばマウス装置やキーボード装置であり、システムの利用者により操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＣＰＵ３０２に送付する。
【０１５７】
表示装置３１２は例えば液晶ディスプレイであり、ＣＰＵ３０２から送付される表示データに応じて各種のテキストや画像を表示する。
【０１５８】
インタフェース装置３１４は、このコンピュータ３００に接続される各種機器との間での各種情報の授受の管理を行う。
【０１５９】
記録媒体駆動装置３１６は、可搬型記録媒体３１８に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＣＰＵ３０２は、可搬型記録媒体３１８に記録されている所定の制御プログラムを、記録媒体駆動装置３１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体３１８としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【０１６０】
このようなコンピュータ３００を用いて暗号処理装置を構成するには、例えば、上述の各処理部における処理をＣＰＵ３０２に行わせるための制御プログラム（暗号処理プログラム）を作成する。作成された制御プログラムはハードディスク装置３０８若しくは可搬型記録媒体３１８に予め格納しておく。そして、ＣＰＵ３０２に所定の指示を与えてこの制御プログラム（暗号処理プログラム）を読み出させて実行させる。こうすることで、暗号処理装置が備えている機能がＣＰＵ３０２により提供される。
【０１６１】
図２０は、実施例における準同型暗号を利用した生体認証方法の登録時の処理の流れの例を示す図である。
【０１６２】
処理が開始されるとＳ３００でクライアント端末２００のバイナリ化部２００２は、外部から乱数Ｒの入力を受ける。この乱数はクライアント端末２００のバイナリ化部２００２に予め用意されていても良い。
【０１６３】
次のＳ３０２でクライアント端末２００のバイナリ化部２００２は、生体認証のために登録される登録画像を用いて特徴コードＡを生成する。Ｓ３００の処理とＳ３０２の処理の順番は逆でも良い。
【０１６４】
次のＳ３０４で端末２００の暗号化部２００４は、乱数Ｒと特徴コードＡを暗号化し、暗号文Ｅ１（Ｒ）、Ｅ２（Ａ）を得る。Ｓ１０２の処理が終了すると、処理はＳ１０４に進む。Ｓ３０４の処理が終了すると、処理はＳ３０６に進む。
【０１６５】
Ｓ３０６で端末２００の送信部２０３６は、暗号文Ｅ１（Ｒ）、Ｅ２（Ａ）を送信する。Ｓ３０６の処理が終了すると、処理はＳ３０８に進む。
【０１６６】
Ｓ３０８で計算サーバ２１０の受信部２１１０は、暗号文Ｅ１（Ｒ）、Ｅ２（Ａ）を受信する。また、Ｓ３０８で計算サーバ２１０のテンプレート登録部２１１２は、暗号文Ｅ１（Ｒ）、Ｅ２（Ａ）をデータベース（準同型暗号化テンプレート保存部）２１０２に格納する。
【０１６７】
図２１は、加算マスクを用いる実施例における準同型暗号を利用した生体認証方法の照合時の処理の流れの例を示す図である。
【０１６８】
また、暗号処理装置が図１９に示されているような汎用コンピュータ３００である場合には、下記の説明は、そのような処理を行う制御プログラム（暗号処理プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（暗号処理プログラム）の説明でもある。
【０１６９】
以下の処理では、クライアント端末２００のバイナリ化部２００８に乱数Ｒが格納されており、ユーザはその乱数Ｒを新しい乱数Ｒ´に変更する処理を含んでいる。
【０１７０】
処理が開始されるとＳ４００でクライアント端末２００のバイナリ化部２００８は、旧乱数Ｒを入力する。
【０１７１】
次のＳ４０２でクライアント端末２００のバイナリ化部２００８は、新乱数Ｒ´を入力する。単に従来の乱数を用いた照合処理だけならば、このステップは省略しても良い。
【０１７２】
Ｓ４０４でクライアント端末２００のバイナリ化部２００８は、照合に用いられる照合画像を用いて特徴コードＢを生成する。
【０１７３】
Ｓ４００〜Ｓ４０４の処理の順番は任意である。
Ｓ４０６で端末２００の暗号化部２０１０は、特徴コードＢと乱数Ｒの和Ｂ＋Ｒを暗号化し、暗号文Ｅ２（Ｂ＋Ｒ）を得る。本ステップの処理が終了すると、処理はＳ４０８に進む。
【０１７４】
Ｓ４０８で端末２００の暗号化部２０１０は、乱数Ｒ´を暗号化しＥ２（Ｒ´）を得る。本ステップの処理が終了すると、処理はＳ４１０に進む。単に従来の乱数を用いた照合処理だけならば、このステップは省略しても良い。
【０１７５】
Ｓ４１０で端末２００の送信部２０２６は、Ｅ２（Ｂ＋Ｒ）、Ｅ２（Ｒ´）を送信する。単に従来の乱数を用いた照合処理だけならば、Ｅ２（Ｂ＋Ｒ）のみを送信しても良い。本ステップの処理が終了すると、処理はＳ４１２に進む。
【０１７６】
Ｓ４１２で計算サーバ２１０の受信部２１１０は、Ｅ２（Ｂ＋Ｒ）、Ｅ２（Ｒ´）を受信する。本ステップの処理が終了すると、処理はＳ４１４に進む。
次のＳ４１４で計算サーバ２１０のアンマスク部２１０６は、アンマスク処理を行う。加算マスクの場合は、Ｅ２（Ｂ＋Ｒ）−Ｅ２（Ｒ）を計算することによってアンマスクすることができる。本ステップの処理が終了すると、処理はＳ４１６に進む。
【０１７７】
Ｓ４１６で計算サーバ２１０の秘匿距離計算部２１０４は、Ｅ１（Ａ）とＥ２（Ｂ）の秘匿距離、たとえばハミング距離ＨＤを計算する。またＳ４１６で計算サーバ２１０の送信部２１２４は、計算結果を認証サーバ２２０に送る。本ステップの処理が終了すると、処理はＳ４１８に進む。
【０１７８】
Ｓ４１８で認証サーバ２２０の受信部２２０８は計算サーバ２１０から送られた暗号化された秘匿距離、たとえばハミング距離ＨＤを受信し、準同型複合部２２１０で復号する。そして、比較部２２１２で閾値θと復号されたハミング距離ＨＤを比較する。ハミング距離ＨＤが閾値θより小さければユーザは認証され（ＯＫ）、そうでなければユーザは認証されない（ＮＧ）。
【０１７９】
次のＳ４２０で認証サーバ２２０の送信部２２１４は判定結果を計算サーバ２１０に送信する。本ステップの処理が終了すると、処理はＳ４２２に進む。
【０１８０】
Ｓ４２２で計算サーバ２１０の受信部２１１０は、判定結果を受信する。本ステップの処理が終了すると、処理はＳ４２４に進む。
【０１８１】
Ｓ４２４で計算サーバ２１０は、ユーザが認証されたか否かを判定する。この判定の結果が“ＹＥＳ”、つまり照合しようとしているユーザが新規のユーザではない場合、新たな処理をせずに終了する。この判定の結果が“ＮＯ”、つまり照合しようとしているユーザが新規のユーザである場合、ユーザが登録された暗号化生体情報をキャンセルするために、処理はＳ４２６に進む。
【０１８２】
Ｓ４２６で計算サーバ２１０は、Ｅ１（Ａ）とＥ２（Ｒ´）をデータベース２１０２に登録する。
【０１８３】
図２２は乗算マスクを用いる実施例における準同型暗号を利用した生体認証方法の照合時の処理の流れの例を示す図である。
【０１８４】
また、暗号処理装置が図１９に示されているような汎用コンピュータ３００である場合には、下記の説明は、そのような処理を行う制御プログラム（暗号処理プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（暗号処理プログラム）の説明でもある。
【０１８５】
処理が開始されるとＳ５００でクライアント端末２００のバイナリ化部２００８は、旧乱数Ｒを入力する。
【０１８６】
次のＳ５０２でクライアント端末２００のバイナリ化部２００８は、新乱数Ｒ´を入力する。単に従来の乱数を用いた照合処理だけならば、このステップは省略しても良い。
【０１８７】
Ｓ５０４でクライアント端末２００のバイナリ化部２００８は、照合に用いられる照合画像を用いて特徴コードＢを生成する。
Ｓ５００〜Ｓ５０４の処理の順番は任意である。
【０１８８】
Ｓ５０６で端末２００の暗号化部２０１０は、特徴コードＢと乱数Ｒの積Ｂ×Ｒを暗号化し、暗号文Ｅ２（Ｂ×Ｒ）を得る。本ステップの処理が終了すると、処理はＳ５０８に進む。
【０１８９】
Ｓ５０８で端末２００の暗号化部２０１０は、特徴コードＢと乱数Ｒの逆数の積Ｂ×Ｒ´−１、乱数Ｒの逆数Ｒ´−１、乱数Ｒ´を暗号化し、Ｅ１（Ｂ×Ｒ´−１）、Ｅ１（Ｒ´−１）、Ｅ２（Ｒ´）を得る。本ステップの処理が終了すると、処理はＳ５１０に進む。単に従来の乱数を用いた照合処理だけならば、このステップは省略しても良い。
【０１９０】
Ｓ５１０で端末２００の送信部２０２６は、Ｅ２（Ｂ×Ｒ）、Ｅ１（Ｂ×Ｒ´−１）、Ｅ１（Ｒ´−１）、Ｅ２（Ｒ´）を送信する。単に従来の乱数を用いた照合処理だけならば、Ｅ２（Ｂ×Ｒ）のみを送信しても良い。本ステップの処理が終了すると、処理はＳ５１２に進む。
【０１９１】
Ｓ５１２で計算サーバ２１０の受信部２１１０は、Ｅ２（Ｂ×Ｒ）、Ｅ１（Ｂ×Ｒ´−１）、Ｅ１（Ｒ´−１）、Ｅ２（Ｒ´）を受信する。本ステップの処理が終了すると、処理はＳ５１４に進む。
次のＳ５１４で計算サーバ２１０のアンマスク部２１０６は、アンマスク処理を行う。加算マスクの場合は、Ｅ２（Ｂ×Ｒ）×Ｅ２（Ｒ−１）を計算することによってアンマスクすることができる。本ステップの処理が終了すると、処理はＳ５１６に進む。
【０１９２】
Ｓ５１６で計算サーバ２１０の秘匿距離計算部２１０４は、Ｅ１（Ａ）とＥ２（Ｂ）の秘匿距離、たとえばハミング距離ＨＤを計算する。またＳ５１６で計算サーバ２１０の送信部２１２４は、計算結果を認証サーバ２２０に送る。本ステップの処理が終了すると、処理はＳ５１８に進む。
【０１９３】
Ｓ５１８で認証サーバ２２０の受信部２２０８は計算サーバ２１０から送られた暗号化された秘匿距離、たとえばハミング距離ＨＤを受信し、準同型複合部２２１０で復号する。そして、比較部２２１２で閾値θと復号されたハミング距離ＨＤを比較する。ハミング距離ＨＤが閾値θより小さければユーザは認証され（ＯＫ）、そうでなければユーザは認証されない（ＮＧ）。
【０１９４】
次のＳ５２０で認証サーバ２２０の送信部２２１４は判定結果を計算サーバ２１０に送信する。本ステップの処理が終了すると、処理はＳ５２２に進む。
【０１９５】
Ｓ５２２で計算サーバ２１０の受信部２１１０は、判定結果を受信する。本ステップの処理が終了すると、処理はＳ４２４に進む。
【０１９６】
Ｓ５２４で計算サーバ２１０は、ユーザが認証されたか否かを判定する。この判定の結果が“ＹＥＳ”、つまり照合しようとしているユーザが新規のユーザではない場合、新たな処理をせずに終了する。この判定の結果が“ＮＯ”、つまり照合しようとしているユーザが新規のユーザである場合、ユーザが登録された暗号化生体情報をキャンセルするために、処理はＳ５２６に進む。
【０１９７】
Ｓ５２６で計算サーバ２１０は、Ｅ１（Ｂ×Ｒ´−１）、Ｅ１（Ｒ´−１）、Ｅ２（Ｒ´）をデータベース２１０２に登録する。
【０１９８】
上記のような処理を用いることで、準同型暗号を利用した暗号処理システムにおいて、暗号化された情報を簡便にキャンセルすることができるという効果を奏する。
【０１９９】
また、上記の方法では、ユーザによる生体特徴ベクトルのキャンセル・再登録は乱数ＲをＲ´に変更すればよく、暗号化生体情報の再登録は不要であるという利点を有する。
【０２００】
上記実施例に関し、さらに以下の付記を開示する。
（付記１）
コンピュータによって実行される暗号処理方法であって、
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、
前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、
前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う、
を含む暗号処理方法。
（付記２）
さらに、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、復号すると前記第１のデータと前記第２のデータの間の秘匿距離となる暗号化秘匿距離を算出し、
前記第１のデータと前記第２のデータとの前記照合は、前記秘匿距離と所定の値との比較によって行う、付記１に記載の暗号処理方法。
（付記３）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の和である、付記１または２に記載の暗号処理方法。
（付記４）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の積である、付記１または２に記載の暗号処理方法。
（付記５）
さらに、
外部から入力されパスワードを用いて、前記乱数を生成することを含む、付記１乃至４のいずれか一項に記載の暗号処理方法。
（付記６）
前記第１の変換多項式は前記第１のベクトルの要素を累乗の昇順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の降順に並べる、または前記第１の変換多項式は前記第１のベクトルの要素を累乗の降順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の昇順に並べる、付記１乃至４のいずれか一項に記載の暗号処理方法。
（付記７）
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得する多項式変換部と、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得する暗号化部と、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う比較部と、
を含む暗号処理装置。
（付記８）
さらに、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、復号すると前記第１のデータと前記第２のデータの間の秘匿距離となる暗号化秘匿距離を算出する秘匿距離算出部と、
を含み、
前記比較部は、前記第１のデータと前記第２のデータとの前記照合は、前記秘匿距離と所定の値との比較によって行う、付記７に記載の暗号処理方法。
（付記９）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の和である、付記７または８に記載の暗号処理装置。
（付記１０）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の積である、付記７または８に記載の暗号処理装置。
（付記１１）
さらに、
外部から入力されパスワードを用いて、前記乱数を生成する乱数生成部を含む、付記７乃至１０のいずれか一項に記載の暗号処理装置。
（付記１２）
前記多項式変換部は、前記第１の変換多項式は前記第１のベクトルの要素を累乗の昇順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の降順に並べる、または前記第１の変換多項式は前記第１のベクトルの要素を累乗の降順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の昇順に並べる、付記７乃至１１のいずれか一項に記載の暗号処理装置。
（付記１３）
第１のデータを第１の変換多項式を用いて変換して第１の多項式を取得し、
前記第１のデータに対応する乱数と第２のデータとを基に得られる式を、第２の変換多項式を用いて変換して第２の多項式を取得し、
前記第１の変換多項式または前記第２の変換多項式のうち少なくとも一方を用いて前記乱数を変換して乱数多項式を取得し、
前記第１の多項式と前記第２の多項式と前記乱数多項式とを、準同型暗号方式を用いて暗号化して、暗号化された第１の多項式と暗号化された第２の多項式と暗号化された乱数多項式とを取得し、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、前記第１のデータと前記第２のデータとの照合を行う
処理をコンピュータに実行させることを特徴とする暗号処理プログラム。
（付記１４）
さらに、
前記暗号化された第１の多項式と前記暗号化された第２の多項式と前記暗号化された乱数多項式とを用いて、復号すると前記第１のデータと前記第２のデータの間の秘匿距離となる暗号化秘匿距離を算出し、
前記第１のデータと前記第２のデータとの前記照合は、前記秘匿距離と所定の値との比較によって行う処理をコンピュータに実行させることを特徴とする、付記１３に記載の暗号処理プログラム。
（付記１５）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の和である、付記１３または１４に記載の暗号処理プログラム。
（付記１６）
第２のベクトルと前記乱数を演算して得られる式は、第２のベクトルと前記乱数の積である、付記１３または１４に記載の暗号処理プログラム。
（付記１７）
さらに、
外部から入力されパスワードを用いて、前記乱数を生成する処理をコンピュータに実行させることを特徴とする、付記１３乃至１６のいずれか一項に記載の暗号処理プログラム。
（付記１８）
前記第１の変換多項式は前記第１のベクトルの要素を累乗の昇順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の降順に並べる、または前記第１の変換多項式は前記第１のベクトルの要素を累乗の降順に並べ、前記第２の変換多項式は前記第２のベクトルの要素を累乗の昇順に並べる、付記１３乃至１７のいずれか一項に記載の暗号処理プログラム。
【符号の説明】
【０２０１】
１０、２０  生体認証システム
１００、２００（２００ａ、２００ｂ）  クライアント端末（端末）
１１０、２１０（２１０ａ、２１０ｂ）  計算サーバ
１２０、２２０  認証サーバ
１００２、１００８、  バイナリ化部
１００４、１０１０  暗号化部
１００６、１０１２  公開鍵
１１０２、１１１２、２１０２  データベース
１１１０  受信部
１０１６、２０１８、２０４２  センサ部
１０１８、２０２０、２０５０  バイナリ特徴コード化部
１０２０、２０２８、２０５４  登録／照合切替部
１０２２、２０３０、２０５６  多項式変換部
１０２４、２０３２、２０６０  準同型暗号処理部
１１２４、２１４０、１０２６、２０２６、２０６２、２１２４、２２１４  送信部
１１１６、１１１８、１１２０  準同型乗算部
１１２２  準同型加算部
１０１４、２０１６、２１０８、２０４０、２１２６、２２０６  制御部
２０２２、２０４６  乱数入力部
２０２４  加算部
２０５２  乗算部
２０２６、２０４８  切替
２１１０、２１２６  受信部
２１１２  暗号化ハミング距離計算部
２１１４、２１２２、２１３８  準同型加算部
２１１６、２１１８、２１２０、２１３２、２１３４、２１３６  準同型乗算部
２１２２  テンプレート登録部
１２０２、２２１２  比較部
１２０４  秘密鍵
２２１０  準同型復号部
【図５】
2016012111.tif 000032
【図８】
2016012111.tif 000033
【図９】
2016012111.tif 000034
【図１５Ａ】
2016012111.tif 000035
【図１５Ｂ】
2016012111.tif 000036
【図１９】
2016012111.tif 000037
【図１】
2016012111.tif 000038
【図２】
2016012111.tif 000039
【図３】
2016012111.tif 000040
【図４】
2016012111.tif 000041
【図６】
2016012111.tif 000042
【図７】
2016012111.tif 000043
【図１０】
2016012111.tif 000044
【図１１】
2016012111.tif 000045
【図１２】
2016012111.tif 000046
【図１３】
2016012111.tif 000047
【図１４】
2016012111.tif 000048
【図１６】
2016012111.tif 000049
【図１７】
2016012111.tif 000050
【図１８】
2016012111.tif 000051
【図２０】
2016012111.tif 000052
【図２１】
2016012111.tif 000053
【図２２】
2016012111.tif 000054