(57)【要約】  本発明は、演算の高速化、より安全な照合処理を可能とする。登録要求装置は、数値ベクトルである登録情報から生成された多項式を暗号化鍵を用いて暗号化し、照合補助装置は一つの項の係数が乱数でその他の項の係数が０である多項式を暗号化したチャレンジを生成し、認証要求装置は前記チャレンジと認証情報から生成された多項式との積の暗号文をレスポンスとして生成し、照合補助装置は登録情報から生成された多項式の暗号文と、前記一つの係数と次数からなるチャレンジ補助と前記認証情報から生成された多項式との積の暗号文とに基づき、登録情報と認証情報との距離の暗号文を生成して検証装置に送信し、検証装置では登録情報と認証情報との距離の暗号文を復号鍵を用いて復号し距離を算出する。
2017170780.tif 000002
【特許請求の範囲】
【請求項１】
登録要求装置と、照合補助装置と、認証要求装置と、検証装置とを含み、
前記検証装置は、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し、前記暗号化鍵を公開し、
前記登録要求装置は、
数値ベクトルである登録情報を多項式化し、
多項式化した前記登録情報を、前記暗号化鍵を用いて暗号化し、
前記照合補助装置は、
前記認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、
前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付し、
前記認証要求装置は、
数値ベクトルである認証情報を多項式化し、
多項式化した前記認証情報と、前記照合補助装置からの前記チャレンジと、に基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の暗号文を算出し、
多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助装置に送付し、
前記照合補助装置は、
前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、前記登録要求装置で暗号化された前記登録情報とに基づき、前記暗号化鍵を用いて、前記登録情報と前記認証情報の距離の暗号文を算出し、
前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付し、
前記検証装置は、
前記照合補助装置から受け取った、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、
算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する、ことを特徴とする暗号文照合システム。
【請求項２】
記憶装置をさらに含み、
前記記憶装置は、
記憶部と、
前記登録要求装置から受け取った、暗号化された前記登録情報に対して識別子を付与する識別子付与部と、
暗号化された前記登録情報と前記識別子との組からなる登録データを前記記憶部に格納する登録データ生成部と、
前記照合補助装置からの登録データ要求を受け、前記記憶部に記憶されている前記登録データの中から、前記登録データ要求に含まれる識別子と組とされている、暗号化された登録情報を、前記照合補助装置に送付する登録データ検索部と、
を備え、
前記照合補助装置は、
前記認証要求装置から受け取った認証要求に含まれ、前記認証情報に対応する認証識別子を含む登録データ要求を前記記憶装置に送付し、
前記記憶装置から、前記認証識別子に対応する暗号化された前記登録情報を受け取り、
前記認証要求装置から受け取った前記レスポンスと、前記チャレンジ補助と、前記記憶装置から受け取った暗号化された前記登録情報とに基づき、前記登録情報と前記認証情報の距離の暗号文を算出する、ことを特徴とする請求項１に記載の暗号文照合システム。
【請求項３】
記憶装置をさらに含み、
前記記憶装置は、
記憶部と、
前記登録要求装置から受け取った、暗号化された前記登録情報に対して識別子を付与する識別子付与部と、
暗号化された前記登録情報に前記識別子との組からなる登録データを前記記憶部に格納する登録データ生成部と、
を備え、
前記照合補助装置からの登録データ要求を受け、前記記憶部に格納されている一つ又は複数の登録データのうち、一部又はすべての登録データを、前記照合補助装置に送信し、
前記照合補助装置は、
前記記憶装置から、一つ又は複数の登録データを受け取り、
前記記憶装置から受け取った各登録データについて、
前記認証要求装置から受け取った前記レスポンスと、前記チャレンジと、前記登録データに含まれる暗号化された登録情報とに基づき、暗号化された前記登録情報と前記認証情報の距離の暗号文を算出し、
前記登録データについて、算出した前記登録情報と前記認証情報の距離の暗号文と、前記登録データに含まれる識別子との組を検証データとし、  
生成した一つ又は複数の前記検証データを前記検証装置に送付し、
前記検証装置は、
前記照合補助装置から、一つ又は複数の前記検証データを受け取り、
前記検証データについて、
前記検証データに含まれる、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、  
算出した前記距離と予め定められた閾値との比較結果、又は、算出した前記距離と前記検証データに含まれる識別子との組を、照合結果とし、前記照合結果を出力する、ことを特徴とする請求項１に記載の暗号文照合システム。
【請求項４】
前記登録要求装置は、
数値ベクトルである登録情報から、登録情報の第ｉ成分（ただしｉはＬ−１以下の非負整数、Ｌは２以上の正整数）をｉ次の項の係数とするＬ−１次多項式を生成し、前記認証要求装置は、数値ベクトルである認証情報の第ｉ成分（ただしｉはＬ−１以下の非負整数）の逆元をＮ−ｉ次（ＮはＬより大の正整数）の項の係数とするＮ次多項式を生成し、あるいは、
前記登録要求装置は、数値ベクトルである登録情報の第ｉ成分（ただしｉはＬ−１以下の非負整数）の逆元を、Ｎ−ｉ次（ＮはＬより大の正整数）の項の係数とするＮ次多項式を生成し、前記認証要求装置は、数値ベクトルである認証情報の第ｉ成分（ただしｉはＬ−１以下の非負整数、Ｌは２以上の正整数）を、ｉ次の項の係数とするＬ−１次多項式を生成する、ことを特徴とする請求項１乃至３のいずれか１項に記載の暗号文照合システム。
【請求項５】
少なくとも一つのコンピュータによる暗号文照合方法であって、
多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し、前記暗号化鍵を公開し、
登録情報の登録にあたり、
数値ベクトルである登録情報を多項式化し、
多項式化した前記登録情報を、前記暗号化鍵を用いて暗号化し、
照合補助処理では、
認証要求を受けると、一つの係数とその次数をランダムに選択し、
前記次数の係数以外の係数を０とした多項式を生成し、
前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求の要求元に送付し、
前記認証要求元では、
数値ベクトルである認証情報を多項式化し、
多項式化した前記認証情報と、前記照合補助処理からの前記チャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の暗号文を算出し、
多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助処理に送付し、
前記照合補助処理では、
前記認証要求元からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、暗号化された前記登録情報とに基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、
前記登録情報と前記認証情報の距離の前記暗号文を、検証先に送付し、
前記検証先では、
前記照合補助処理から受け取った、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、
算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する、ことを特徴とする暗号文照合方法。
【請求項６】
多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出する検証装置が公開した前記暗号化鍵を取得する照合補助装置であって、
認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付するチャレンジ生成部と、
数値ベクトルである認証情報を多項式化し、前記チャレンジに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして出力する前記認証要求装置からレスポンスを受け、
前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を検証装置に送付するクエリ生成部と、
を備え、
前記検証装置では、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、算出した前記距離又は、前記距離と予め定められた閾値との比較結果を照合結果として出力する、照合補助装置。
【請求項７】
多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する検証装置から前記暗号化鍵を取得する認証要求装置であって、
数値ベクトルである認証情報を多項式化する認証情報抽出部と、
照合補助装置に送信する認証要求を生成する認証要求生成部と、
を備え、
前記認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付する前記照合補助装置から前記チャレンジを受け取り、
前記認証要求生成部で多項式化した前記認証情報と、前記チャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と、前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして、前記照合補助装置に送付するレスポンス生成部をさらに備え、
前記照合補助装置では、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化された多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を、検証装置に送付する、認証要求装置。
【請求項８】
認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付し、前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出する照合補助装置に接続される検証装置であって、
多項式演算が可能な準同型暗号方式の前記暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する鍵生成部と、
前記照合補助装置から前記登録情報と前記認証情報の距離の前記暗号文を受け取ると、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出するクエリ検証部と、
算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する照合結果生成部と、
を備えた検証装置。
【請求項９】
多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する検証装置に接続され、認証要求装置に接続された照合補助装置を構成するコンピュータに、
前記認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、
前記次数の係数以外の係数を０とした多項式を生成し、
前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付する処理と、
数値ベクトルである認証情報を多項式化し、前記チャレンジに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして出力する前記認証要求装置からレスポンスを受ける処理と、
前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付する処理と、
を実行させるプログラム。
【請求項１０】
多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出する検証装置が公開した暗号化鍵を取得し、
認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを認証要求装置に送付し、前記認証要求装置から受け取ったレスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化された多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付する照合補助装置に接続された前記認証要求装置を構成するコンピュータに、
前記認証要求を生成して前記照合補助装置に送信する処理と、
前記照合補助装置からチャレンジを受け取る処理と、
数値ベクトルである認証情報を多項式化し、多項式化した前記認証情報と、前記照合補助装置から受け取ったチャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と、前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、
多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助装置に送付する処理と、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２０１６−０７２７７０号（２０１６年３月３１日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は暗号化技術に関し、特に、暗号文照合システム、ノード装置、暗号文照合方法、およびプログラムに関する。
【背景技術】
【０００２】
クラウドコンピューティング（クラウド）が普及するにつれ、クライアントが通信ネットワークに通信接続しているクラウド側の計算機資源を用いて当該クライアントのデータを管理するクラウドサービスが広く普及している。該サービスは、例えばクライアントの機密性の高いデータを管理することから、クラウド側では、該サービスにおいて扱われるデータが安全であることを保証する必要がある。【０００３】
利用者が通信ネットワークに自由に通信接続可能（オープン）なネットワーク環境において、データを暗号化されたままの状態で管理し、データを復号することなく、検索や、統計処理等を行う技術の研究開発が行われている。【０００４】
近時、パスワード、または、磁気カードを用いた個人認証における脆弱性を利用した犯罪が頻発している。この結果、指紋、または、静脈等の生体が有する特徴に基づいた情報（生体情報）を用いて、より安全性の高い認証を実現する生体認証技術が注目を集めている。【０００５】
良く知られた生体認証技術の典型例の一つにおいては、登録対象である生体から抽出した生体情報に基づきクライアントがテンプレートを作成し、作成されたテンプレートがサーバに送信され、サーバで保管される。生体認証技術において、サーバは、認証対象である生体からクライアントが抽出した生体情報と、サーバに保管されているテンプレート（クライアントが作成しサーバに送信したテンプレート）とを用いて照合処理を行う。【０００６】
同一の生体から抽出された複数の生体情報は完全に一致するとは限らないが、ある距離関数を用いて距離を測定すると、同一の生体から抽出された複数の生体情報間の距離は、異なる生体からそれぞれ抽出された複数の生体情報間の距離と比べて、短いことが知られている。【０００７】
生体認証技術は、上記の性質を利用することによって、登録対象に基づいて生成されたテンプレートと、認証対象に基づいて作成された生体情報との照合を行う。すなわち、生体認証技術においては、
・登録対象である生体から抽出された生体情報と、認証対象である生体から抽出された生体情報が類似（または、一致）している場合に、認証対象を受理する。
・登録対象である生体から抽出された生体情報と、認証対象である生体から抽出された生体情報が類似（または、一致）していない場合に、認証対象を受理しない。【０００８】
一般的に、生体情報の類似は、上記したように、距離によって判定される。すなわち、
・登録対象である生体から抽出された生体情報と、認証対象である生体から抽出された生体情報との間の距離が、事前に定められた閾値以下であれば受理される。
・登録対象である生体から抽出された生体情報と、認証対象である生体から抽出された生体情報との間の距離が、事前に定められた閾値より大きければ、受理されない。【０００９】
例えば、指紋、静脈等の生体が有する特徴は、生涯不変のデータとされている。生体情報が照合システムの外部に漏洩された場合の被害が甚大であるので、生体情報は、機密性が要求される情報の一つである。したがって、たとえ、登録対象である生体から抽出した生体情報に基づき生成したテンプレートと認証対象に基づいて作成された生体情報との照合を行う照合システムから、外部に、該テンプレートが漏洩したとしても、生体情報が外部に漏洩しない性質を満たすことが望ましい。【００１０】
また、生体認証技術では、他の認証技術と同様に、生体情報を登録した生体と異なる生体が登録対象の生体になりすますこと（すなわち、「なりすまし」）を防ぐ必要がある。例えば、特定の値を照合システムに送信することによって、認証に成功してしまうような認証技術は、なりすましへの耐性が十分でないといえる。【００１１】
さらに、認証技術においては、テンプレートが漏洩してしまうリスクだけでなく、認証時の通信内容が盗聴（傍受）されるリスクもある。認証技術においては、通信内容が盗聴されたとしても、上記したなりすましを防ぐ必要がある。例えば、認証対象が受理された場合に、照合システムへ送信されたデータを、再送することにより、再度受理される方式は、なりすましへの耐性が十分でない。【００１２】
例えば、非特許文献２には、登録対象である生体から抽出された生体情報や、認証対象である生体から抽出された生体情報を秘匿したまま、認証を行うことを可能とした生体認証方式が開示されている。また、非特許文献１には、加法及び乗法に関する準同型性を持つ準同型暗号方式が開示されている。【００１３】
準同型暗号方式について概説する。準同型暗号方式は、準同型あるいは準同型性（homomorphism）と呼ばれる特殊な性質を持つ公開鍵暗号方式である。【００１４】
公開鍵暗号方式は、
・公開鍵（「暗号化鍵」という）、及び、秘密鍵（「復号鍵」という）を生成するアルゴリズム（鍵生成アルゴリズム）、
・生成した暗号化鍵を用いてメッセージを暗号化するアルゴリズム（暗号化アルゴリズム）、及び、
・生成した復号鍵を用いて暗号文を復号するアルゴリズム（復号アルゴリズム）
を含む。【００１５】
鍵生成アルゴリズム（「Ｇｅｎ」と表記する）は、セキュリティパラメータλに基づき、暗号化鍵ｐｋと、復号鍵ｓｋとを算出するアルゴリズムであり、
Ｇｅｎ（λ）→（ｐｋ，ｓｋ）    ・・・(式１)
と表される。セキュリティパラメータλは、暗号の安全性を表す尺度であり、暗号化鍵や復号鍵の長さを決定するパラメータである。【００１６】
暗号化アルゴリズム（「Ｅｎｃ」と表記する）は、暗号化鍵ｐｋと、メッセージｘとに基づき、暗号化鍵ｐｋを用いてメッセージｘが暗号化された暗号文ｃを算出するアルゴリズムであり、
Ｅｎｃ（ｐｋ，Ｍ）→ｃ          ・・・(式２)
と表される。【００１７】
復号アルゴリズム（「Ｄｅｃ」と表記する）は、復号鍵ｓｋと暗号文ｃとに基づき、復号鍵ｓｋを用いて暗号文ｃが復号された復号結果Ｘを算出するアルゴリズムであり、
Ｄｅｃ（ｓｋ，ｃ）→Ｘ        ・・・(式３)
と表される。【００１８】
ただし、
Ａ（Ｂ）→Ｃ                ・・・(式４)
は、アルゴリズムＡにＢを入力すると、Ｃが出力される、ことを意味する。【００１９】
公開鍵暗号方式は、次の式５に示す条件を満たす場合に、準同型性を持つ。【００２０】
Ｅｎｃ（ｐｋ，ｘ１＃ｘ２）＝Ｅｎｃ（ｐｋ，ｘ１）＠Ｅｎｃ（ｐｋ，ｘ２）  ・・・（式５）【００２１】
ただし、＃、及び、＠は、それぞれ２項演算子を表す。また、ｘ１、及び、ｘ２は、それぞれ、メッセージを表す。【００２２】
特に、＃が加算である場合、式５に示す条件を満たす公開鍵暗号方式は、加算について準同型性を持つという。この場合のＥｎｃ（ｐｋ，ｘ１）＠Ｅｎｃ（ｐｋ，ｘ２）の計算を、「暗号文の加算」と呼ぶ。【００２３】
また、＃が乗算である場合に、式５に示す条件を満たす公開鍵暗号方式は、乗算について準同型性を持つという。この場合のＥｎｃ（ｐｋ，ｘ１）＠Ｅｎｃ（ｐｋ，ｘ２）の計算を、「暗号文の乗算」と呼ぶ。【００２４】
さらに、暗号文の加算や暗号文の乗算を応用することにより、次の式６に示す条件を満たす準同型暗号も存在する。【００２５】
Ｅｎｃ（ｐｋ，ｎ＃ｘ）＝Ｅｎｃ（ｐｋ，ｘ）＠ｎ  ・・・（式６）【００２６】
ただし、＃、及び、＠は、それぞれ２項演算子を表す。また、ｘ、及び、ｎは、それぞれ、メッセージを表す。【００２７】
特に、＃が加算である場合、式６に示す条件を満たす公開鍵暗号方式は、スカラー倍について準同型性を持つという。この場合のＥｎｃ（ｐｋ，ｘ）＠ｎの計算を、「暗号文のスカラー倍」と呼ぶ。【００２８】
非特許文献１に記載された、加法及び乗法について準同型性を持つ準同型暗号方式について説明する。この方式は、メッセージとして多項式を扱う、ｒｉｎｇ−ＬＷＥ問題の困難性に基づく暗号である。ｒｉｎｇ−ＬＷＥ問題の困難性に基づく暗号の特徴として、演算が高速に行えることが挙げられる。【００２９】
鍵生成アルゴリズムは入力として、主に４つのパラメータＮ、ｑ、ｔ、σを受け取る。【００３０】
Ｎは２冪の整数で、多項式ｘＮ＋１による剰余環である多項式環Ｒ＝Ｚ［ｘ］／＜ｘＮ＋１＞を定める。【００３１】
ｑは２Ｎを法として１と合同（ｑ≡１  ｍｏｄ  ２Ｎ）な素数であり、暗号文空間を表す多項式環Ｒｑ＝Ｒ／ｑＲ＝Ｚｑ［ｘ］／＜ｘＮ＋１＞を定める（Ｒｑの元は、各係数が群Ｚｑの元である（Ｎ−１）次多項式）。【００３２】
ｔはｑより小さい正の整数（素数とは限らない）であり、暗号方式における平文空間を表す多項式環Ｒｔ＝Ｒ／ｔＲ＝（Ｚ／ｔＺ）［ｘ］／＜ｘＮ＋１＞を定める（Ｒｔの元は、各係数が剰余群Ｚ／ｔＺの元である（Ｎ−１）次多項式）。【００３３】
σは、Ｎ次元離散ガウス分布χ＝Ｄ（ＺＮ，σ）の標準偏差である。Ｎ次元離散ガウス分布によってサンプルされるＮ次元整数ベクトルは、標準偏差がσであるガウス分布（正規分布とも呼ばれる）に従う実数値を丸めた整数値を各成分に持つベクトルである。
標準偏差がσであるＮ次元離散ガウス分布の確率密度関数は、
2017170780.tif 000003
【００３４】
標準偏差がσであるＮ次元離散ガウス分布χ＝Ｄ（ＺＮ，σ）から、多項式ε（ｘ）∈Ｒがサンプルされる。多項式の加算と乗算はｍｏｄｕｌｏ（ｘＮ＋１，ｑ）で定義される。【００３５】
次に、標準偏差がσであるＮ次元離散ガウス分布χからサンプリングされた元（Ｎ−１次多項式）ｓ∈Ｒを一つ固定する。【００３６】
次に、Ｒｑから一様ランダムにサンプルした環の要素（各係数がｑより小さいＮ−１次多項式）ｐ１∈Ｒｑとする。標準偏差がσであるＮ次元離散ガウス分布χから得られる元ｅ∈Ｒをとる。【００３７】
次に、
ｐ０＝−（ｐ１×ｓ＋ｔ×ｅ）      ・・・（式８）
を計算する。【００３８】
ｐｋ＝（ｐ０，ｐ１）            ・・・（式９）
を公開鍵（暗号化鍵）とし、
ｓｋ＝ｓ                          ・・・（式１０）
を秘密鍵（復号鍵）とする。【００３９】
ただし、多項式ｐ０の計算時のように、多項式の積を計算する場合において、多項式の次数がＮ以上となった場合には、以下のような置き換えが行われる。【００４０】
ｘＮ＝（ｘＮ＋１）−１＝−１  ｍｏｄ（ｘＮ＋１）     ・・・（式１１−１）
ｘＮ＋１＝x（ｘＮ＋１）−x=−ｘ  ｍｏｄ（ｘＮ＋１）  ・・・（式１１−２）【００４１】
さらに、多項式の和や積を計算する場合において、各係数がｑ以上となった場合には、その係数をｑで割った余りに置き換えて計算する（ｍｏｄ  ｑ）。これにより、計算される多項式は、常に、各係数がｑより小さい、Ｎ−１次以下の多項式となる。以下の計算においても同様に行う。【００４２】
暗号化アルゴリズムは、入力として、上記の鍵生成アルゴリズムに入力された４つのパラメータの組（Ｎ，ｑ，ｔ，σ）、上記の鍵生成アルゴリズムで生成した暗号化鍵ｐｋ＝（ｐ０，ｐ１）およびメッセージｘを受けとる。【００４３】
ただし、メッセージｘ（ｘ∈Ｒｔ）は、各係数がｔより小さい、Ｎ−１次多項式である。【００４４】
次に、３つのＮ−１次多項式ｕ、ｇおよびｆを、標準偏差がσであるＮ次元離散ガウス分布χに従って生成する。【００４５】
次に、Ｎ−１次多項式ｕ、ｇおよびｆ、暗号化鍵（公開鍵）ｐｋ、ｔから、
ｃ０＝ｐ０×ｕ＋ｔ×ｇ＋ｘ                    ・・・（式１２−１）
ｃ１＝ｐ１×ｕ＋ｔ×ｆ                        ・・・（式１２−２）
を計算する。【００４６】
そして、
ｃ=（ｃ０，ｃ１）∈（Ｒｑ）２                ・・・（式１３）
を暗号文（ｃｉｐｈｅｒｔｅｘｔ）として出力する。【００４７】
復号アルゴリズムは入力として、上記の鍵生成アルゴリズムに入力された４つのパラメータの組（Ｎ，ｑ，ｔ，σ）、上記の復号鍵ｓｋおよび暗号文
ｃ＝（ｃ０，ｃ１）∈（Ｒｑ）２または（ｃ０，ｃ１，ｃ２）∈（Ｒｑ）３
を受け取る。以下、前者の場合は、ｃ２＝０であるとみなす。【００４８】
次に、
Ｃ＝ｃ０＋ｃ１×ｓｋ＋ｃ２×ｓｋ２                ・・・（式１４）
を計算する。【００４９】
暗号文が含む多項式の数をｌ＋１とすると、
ｃ＝（ｃ０，・・・，ｃｌ）∈（Ｒｑ）ｌ＋１について、
Ｃ＝Σｉ＝０〜ｌｃｉｓｋｉ∈Ｒｑ                  ・・・（式１５）
を計算する。【００５０】
Ｃをｑで割った余りをＤとする。Ｄがｑ／２以上である場合には、ＤをＤ−ｑに変更する。これは、Ｄのｑを法とした［−ｑ／２，ｑ／２）への剰余演算である。【００５１】
次に、Ｄをｔで割った余り（Ｄ  ｍｏｄ  ｔ）を復号結果Ｘとして出力する。【００５２】
この公開鍵暗号方式は，加法及び情報について準同型性を持つ。【００５３】
２つのメッセージｘおよびｙについて、その暗号文をそれぞれ
Ｅｎｃ（ｐｋ，ｘ）→（ｃ０，ｃ１）                ・・・（式１６−１）
Ｅｎｃ（ｐｋ，ｙ）→（ｄ０，ｄ１）                ・・・（式１６−２）
とする。【００５４】
このとき、暗号文の加算は、
Ｅｎｃ（ｐｋ，ｘ）＋Ｅｎｃ（ｐｋ，ｙ）＝（ｃ０＋ｄ０，ｃ１＋ｄ１）        ・・・（式１７）
によって計算できる。【００５５】
暗号文の加算において、ｘ＝ｙである場合を応用すると、ｔより小さい任意の整数ｎについて、暗号文のスカラー倍を計算できる。すなわち、暗号文のスカラー倍は、
ｎ×Ｅｎｃ（ｐｋ，ｘ）＝（ｎ×ｃ０，ｎ×ｃ１）          ・・・（式１８）
によって計算できる。【００５６】
暗号文の乗算は、
Ｅｎｃ（ｐｋ，ｘ）＠Ｅｎｃ（ｐｋ，ｙ）＝（ｃ０×ｄ０，ｃ０×ｄ１＋ｃ１×ｄ０，ｃ１×ｄ１）    ・・・（式１９）
によって計算できる。【００５７】
この公開鍵暗号方式はメッセージとして多項式を扱う。ベクトルは、その各成分を、多項式の各係数とみなすことにより、多項式とみなすことができる。したがって、この公開鍵暗号方式を用いてベクトルを暗号化することができる。【００５８】
ベクトルを多項式にする方法を工夫し、さらに加法準同型性および乗法準同型性を利用することにより、２つのベクトルを暗号化したまま、その内積の暗号文を計算する方法について説明する。【００５９】
各成分がｔより小さい、２つのＬ（Ｌ＜Ｎ）次のベクトルを、
Ａ＝（ａ０，…，ａＬ−１）、
Ｂ＝（ｂ０，…，ｂＬ−１）
とする。【００６０】
ベクトルＡの各成分は昇順に、ベクトルＢの各成分は降順にそれぞれ係数として用いることにより、多項式ｆＡおよびｆＢを、それぞれ式２０、式２１にしたがって得る。【００６１】
ｆＡ（ｘ）＝Σｉ＝０〜Ｌ−１ａｉ×ｘｉ        ・・・（式２０）【００６２】
ｆＢ（ｘ）＝−Σｉ＝０〜Ｌ−１ｂｉ×ｘＮ−ｉ  ・・・（式２１）【００６３】
ベクトルを多項式に変換するための式２０および式２１の計算方法をそれぞれ、「昇順多項式化」および「降順多項式化」と呼ぶ。二つの多項式ｆＡおよびｆＢの積は次の通り計算される。【００６４】
ｆＡ（ｘ）×ｆＢ（ｘ）＝−Σｉ＝Ｎ−Ｌ＋１〜Ｎ−１（Σｊ＝０〜ｉ（ａｊ×ｂＮ−ｉ＋ｊ））ｘｉ＋Σｉ＝０〜Ｌ−１Σｊ＝ｉ〜Ｌ−１（ａｊ×ｂｊ−ｉ）ｘｉ      ・・・（式２２）【００６５】
式２２の多項式の定数項は、Σｊ（ａｊ×ｂｊ）、すなわちベクトルＡ、Ｂの内積
＜Ａ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｉ×ｂｉ      ・・・（式２３）
と等しい。【００６６】
各成分が０または１である２つのベクトル
Ａ＝（ａ０，…，ａＬ−１）、
Ｂ＝（ｂ０，…，ｂＬ−１）
について、対応する成分のうち異なるものの個数をハミング距離ｄＨ（Ａ，Ｂ）という。【００６７】
すなわち、各ｉ（ｉ＝０，…，Ｌ−１）に対し、ａｉ≠ｂｉを満たすｉの数がハミング距離である。２つのベクトルのハミング距離は内積を用いて計算できる。【００６８】
Ｎ次元ベクトルＣを、全成分が１であるベクトル、すなわちＣ＝（１，…，１）とする。このとき、ハミング距離について、次の式２４が成り立つ。【００６９】
ｄＨ（Ａ，Ｂ）＝＜Ａ，Ｃ＞＋＜Ｃ，Ｂ＞−２＜Ａ，Ｂ＞  ・・・（式２４）【００７０】
また、２つのベクトル
Ａ＝（ａ０，…，ａＬ−１）、
Ｂ＝（ｂ０，…，ｂＬ−１）
について、Ａ、Ｂ間のユークリッド距離は、
ｄＥ（Ａ，Ｂ）＝Σｉ＝０〜ｎ−１（ａｉ−ｂｉ）２      ・・・（式２５）
で定義される。【００７１】
２つのベクトルのユークリッド距離は、次の式２６の通り、内積を用いて計算できる。【００７２】
ｄＥ（Ａ，Ｂ）＝（Σｉ＝０〜ｎ−１ａｉ２）＋（Σｉ＝０〜ｎ−１ｂｉ２）−２＜Ａ，Ｂ＞  ・・・（式２６）【００７３】
非特許文献２に記載された生体認証方式は、上記の非特許文献１に記載された、加法及び乗法について、準同型性を持つ準同型暗号方式（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）を用いて構成される。【００７４】
この方式では、生体からＮ次未満のベクトルが抽出でき、同一の生体から抽出したベクトルのハミング距離は短く、異なる生体から抽出したベクトルのハミング距離は長いことを仮定する。ハミング距離の計算には、上記の式２４を用いる。【００７５】
非特許文献１に記載された生体認証方式は次のように実行される。各成分が０または１であるベクトルの形で表される生体情報
Ａ＝（ａ０，…，ａＬ−１）
を登録する際に、クライアントは、ベクトルＡを、上記の式２０に従って昇順多項式化してｆＡとし、暗号化鍵ｐｋを用いて暗号化した暗号文Ｅｎｃ（ｐｋ，ｆＡ）をテンプレートとして、サーバに記憶させる。【００７６】
各成分が０または１であるベクトルの形で表される生体情報
Ｂ＝（ｂ０，…，ｂＬ−１）
について、認証を行う際に、クライアントは、ベクトルＢを、上記の式２１に従って降順多項式化してｆＢとし、暗号化鍵ｐｋを用いて暗号化した暗号文Ｅｎｃ（ｐｋ，ｆＢ）をサーバに送付する。【００７７】
サーバは、全ての係数が１である多項式
ｆＣ＝Σｉ＝０〜ｎ−１ｘｉ        ・・・（式２７）
を暗号化鍵ｐｋを用いて暗号化したＥｎｃ（ｐｋ、ｆＣ）を計算し、上記式２４に従って、
Ｅｎｃ（ｐｋ，ｆＡ）＠Ｅｎｃ（ｐｋ，ｆＣ）＋Ｅｎｃ（ｐｋ，ｆＣ）＠Ｅｎｃ（ｐｋ，ｆＢ）−２Ｅｎｃ（ｐｋ，ｆＡ）＠Ｅｎｃ（ｐｋ，ｆＢ）      ・・・（式２８）
を計算する。【００７８】
これを、当該サーバおよび当該クライアントとは異なる復号鍵を持つエンティティに送ることにより、該エンティティが、暗号文を復号する。【００７９】
該エンティティで復号して得られたメッセージである多項式の定数項が、２つのベクトルＡおよびＢのハミング距離ｄＨ（Ａ、Ｂ）である。【００８０】
得られたハミング距離が、事前に定められた閾値と比べて長いか短いかによって、認証結果を決められる。【００８１】
また、非特許文献３には、非特許文献２の方法と、上記式２６（２つのベクトルの距離）を用いることにより、ユークリッド距離の長短による認証を行うこともできることが指摘されている。【００８２】
また、非特許文献２の方式は、なりすまし攻撃への耐性を持たない。例えば、通信内容が盗聴された場合であって、これが受理された場合に、照合システムへ送信されたデータを再送することにより、再度、受理される。【００８３】
具体的には、クライアントが、生体情報Ｂ＝（ｂ０、…、ｂＬ−１）について認証を行う際に、該クライアントは、ベクトルＢを、上記式２１に従って、降順多項式化してｆＢとし、暗号文Ｅｎｃ（ｐｋ、ｆＢ）をサーバに送付し、受理されたとする。【００８４】
このＥｎｃ（ｐｋ、ｆＢ）を盗聴した攻撃者がＥｎｃ（ｐｋ、ｆＢ）をそのまま再送すると、攻撃者が受理されることになる。【００８５】
非特許文献２および非特許文献３の方式では、復号鍵を持つエンティティが、生体情報間の距離を算出する。非特許文献４では、生体情報間の距離を得られるエンティティが能動的な攻撃を行うことができる状況下において、該エンティティによる登録された生体情報の復元を防ぐことができないことが指摘されている。さらに非特許文献４には、復号鍵を持つ該エンティティを含むすべてのエンティティに対して、生体情報間の距離を秘匿したまま、認証結果を計算する方法が記載されている。
【先行技術文献】
【非特許文献】
【００８６】
【非特許文献１】Brakerski, Z.; Vaikuntanathan, V., "Fully homomorphic encryption from ring-LWE and security for key dependent messages", CRYPTO 2011
【非特許文献２】Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T., "Secure Pattern Matching Using Somewhat Homomorphic Encryption", CCSW 2013.
【非特許文献３】Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T., "Practical Packing Method in Somewhat Homomorphic Encryption", DPM2013.
【非特許文献４】肥後 春菜; 一色 寿幸; 森 健吾; 尾花 賢, "生体情報間の距離を秘匿する秘匿生体認証方式", 2016年暗号と情報セキュリティシンポジウム (SCIS2016).
【発明の概要】
【発明が解決しようとする課題】
【００８７】
関連技術の分析を以下に与える。【００８８】
非特許文献２に記載された生体認証方式は、ｒｉｎｇ−ＬＷＥ問題の困難性に基づく暗号を用いて構成されているため、認証時の演算が軽い。【００８９】
しかし、上記で述べたとおり、非特許文献２に記載された生体認証方式は、なりすましへの耐性が十分でない。【００９０】
そこで、演算を高速に行うことができ、かつ、生体情報の漏洩やなりすまし攻撃を防ぐことができる生体認証方式が要望される。【００９１】
本発明の目的は、上述した課題に鑑みて創案されたものであって、その目的の一つは、演算の高速化、及び生体情報の漏洩やなりすまし攻撃を防ぐことを可能とする暗号文照合システム、ノード、方法、およびそのためのプログラムを提供することにある。
【課題を解決するための手段】
【００９２】
本発明の一様態に係る暗号文照合システムは、登録要求装置と、照合補助装置と、認証要求装置と、検証装置とを含む。前記検証装置は、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し、前記暗号化鍵を公開する。前記登録要求装置は、数値ベクトルである登録情報を多項式化し、多項式化した前記登録情報を、前記暗号化鍵を用いて暗号化する。前記照合補助装置は、前記認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付する。前記認証要求装置は、数値ベクトルである認証情報を多項式化し、多項式化した前記認証情報と、前記照合補助装置からの前記チャレンジと、に基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助装置に送付する。前記照合補助装置は、前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、前記登録要求装置で暗号化された前記登録情報とに基づき、前記暗号化鍵を用いて、前記登録情報と前記認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付する。前記検証装置は、前記照合補助装置から受け取った、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する。【００９３】
本発明の一様態に係る装置は、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出する検証装置が公開した前記暗号化鍵を取得する照合補助装置であって、認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付するチャレンジ生成部と、数値ベクトルである認証情報を多項式化し、前記チャレンジに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして出力する前記認証要求装置からレスポンスを受け、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を検証装置に送付するクエリ生成部と、を備える。前記検証装置では、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、算出した前記距離又は、前記距離と予め定められた閾値との比較結果を照合結果として出力する。【００９４】
本発明の一様態に係る装置は、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する検証装置から前記暗号化鍵を取得する認証要求装置であって、数値ベクトルである認証情報を多項式化する認証情報抽出部と、照合補助装置に送信する認証要求を生成する認証要求生成部と、を備えている。さらに、前記認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付する前記照合補助装置から前記チャレンジを受け取り、前記認証要求生成部で多項式化した前記認証情報と、前記チャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と、前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして、前記照合補助装置に送付するレスポンス生成部をさらに備えている。前記照合補助装置では、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化された多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を、検証装置に送付する。【００９５】
本発明の一様態に係る装置は、認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付し、前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出する照合補助装置に接続される検証装置であって、多項式演算が可能な準同型暗号方式の前記暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する鍵生成部と、前記照合補助装置から前記登録情報と前記認証情報の距離の前記暗号文を受け取ると、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出するクエリ検証部と、算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する照合結果生成部と、を備えている。【００９６】
本発明の一様態における方法は、少なくとも一つのコンピュータによる暗号文処理方法であって、
（Ａ）多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し、前記暗号化鍵を公開し、
（Ｂ）登録情報の登録にあたり、
数値ベクトルである登録情報を多項式化し、
多項式化した前記登録情報を、前記暗号化鍵を用いて暗号化し、
（Ｃ）照合補助処理では、
認証要求を受けると、一つの係数とその次数をランダムに選択し、
前記次数の係数以外の係数を０とした多項式を生成し、
前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求の要求元に送付し、
（Ｄ）前記認証要求元では、
数値ベクトルである認証情報を多項式化し、
多項式化した前記認証情報と、前記照合補助処理からの前記チャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の暗号文を算出し、
多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助処理に送付し、
（Ｅ）前記照合補助処理では、
前記認証要求元からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、暗号化された前記登録情報とに基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、
前記登録情報と前記認証情報の距離の前記暗号文を、検証先に送付し、
（Ｆ）前記検証先では、
前記照合補助処理から受け取った、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号して前記距離を算出し、
算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する。【００９７】
本発明の一様態に係るプログラムは、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する検証装置に接続され、認証要求装置に接続された照合補助装置を構成するコンピュータに、
前記認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、
前記次数の係数以外の係数を０とした多項式を生成し、
前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付する処理と、
数値ベクトルである認証情報を多項式化し、前記チャレンジに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、レスポンスとして出力する前記認証要求装置からレスポンスを受ける処理と、
前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付する処理と、を実行させるプログラムからなる。【００９８】
本発明の一様態に係るプログラムは、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアを算出する検証装置が公開した暗号化鍵を取得し、
認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、前記暗号化鍵を用いて暗号化した暗号文からなるチャレンジを認証要求装置に送付し、前記認証要求装置から受け取ったレスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化された多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出し、前記登録情報と前記認証情報の距離の前記暗号文を前記検証装置に送付する照合補助装置に接続された前記認証要求装置を構成するコンピュータに、
前記認証要求を生成して前記照合補助装置に送信する処理と、
前記照合補助装置からチャレンジを受け取る処理と、
数値ベクトルである認証情報を多項式化し、多項式化した前記認証情報と、前記照合補助装置から受け取ったチャレンジとに基づき、前記暗号化鍵を用いて、多項式化した前記認証情報と、前記チャレンジの生成に用いられた多項式との積の暗号文を算出し、
多項式化した前記認証情報と前記チャレンジの生成に用いられた前記多項式との積の前記暗号文を、前記レスポンスとして、前記照合補助装置に送付する処理と、を実行させるプログラムからなる。【００９９】
本発明の一様態に係るプログラムは、認証要求装置から認証要求を受けると、一つの係数とその次数をランダムに選択し、前記次数の係数以外の係数を０とした多項式を生成し、前記多項式を、暗号化鍵を用いて暗号化した暗号文からなるチャレンジを前記認証要求装置に送付し、前記認証要求装置からレスポンスを受け取ると、前記レスポンスと、前記一つの係数とその次数からなるチャレンジ補助と、登録要求装置で暗号化され記憶装置に記憶されている、多項式化した登録情報と、に基づき、前記暗号化鍵を用いて、前記登録情報と認証情報の距離の暗号文を算出する照合補助装置に接続される検証装置を構成するコンピュータに、
多項式演算が可能な準同型暗号方式の前記暗号化鍵と復号鍵のペアを算出し前記暗号化鍵を公開する鍵生成処理と、
前記照合補助装置から前記登録情報と前記認証情報の距離の前記暗号文を受け取ると、前記登録情報と前記認証情報の距離の暗号文を、前記復号鍵を用いて復号前記距離を算出するクエリ検証処理と、
算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する照合結果生成処理と、を実行させるプログラムからなる。本発明の一態様によれば、上記プログラムを記録したコンピュータ読み出し可能な記憶媒体（半導体メモリ、磁気ディスク媒体／光ディスク媒体等：non-transitory computer-readable recording medium）が提供される。
【発明の効果】
【０１００】
本発明によれば、照合処理を高速に行い、平文データの漏洩やなりすまし攻撃を防ぐことを可能としている。
【図面の簡単な説明】
【０１０１】
【図１】本発明の第１、第３の例示的な実施形態の構成を例示する図である。
【図２】本発明の第１、第３の例示的な実施形態の準備フェーズの処理の一例を説明する図である。
【図３】本発明の第１、第３の例示的な実施形態の登録フェーズの処理の一例を説明する図である。
【図４】本発明の第１、第３の例示的な実施形態の認証フェーズの処理の一例を説明する図である。
【図５】本発明の第２、第４の例示的な実施形態の構成を例示する図である。
【図６】本発明の第２、第４の例示的な実施形態の準備フェーズの処理の一例を説明する図である。
【図７】本発明の第２、第４の例示的な実施形態の登録フェーズの処理の一例を説明する図である。
【図８】本発明の第２、第４の例示的な実施形態の認証フェーズの処理の一例を説明する図である。
【発明を実施するための形態】
【０１０２】
はじめに本発明の基本概念を説明する。本発明の一態様に係るシステム（暗号文照合システム）において、検証装置（手段）は、多項式演算が可能な準同型暗号方式の暗号化鍵ｐｋと復号鍵ｓｋのペアを算出し、前記暗号化鍵ｐｋを公開する。
【０１０３】
登録要求装置（手段）（例えば図１の１１０）は、数値ベクトルである登録情報（Ａ＝（ａ０，…，ａＬ−１））を多項式化し（例えばｆＡ）、多項式化した前記登録情報を、前記暗号化鍵（ｐｋ）を用いて暗号化する（例えばＥｎｃ（ｐｋ，ｆＡ）、多項式の各係数（数値ベクトルの各成分）の２乗和Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））を含んでもよい）。
【０１０４】
照合補助装置（手段）（例えば図１の１４０）は、認証要求装置（手段）（例えば図１の１３０）から認証要求を受けると、一つの係数（ｒ）とその次数（ｈ）をランダムに選択し、前記次数（ｈ）の係数以外の係数を０とした多項式（ｒ×ｘｈ）を生成し、前記多項式（ｒ×ｘｈ）を、前記暗号化鍵ｐｋを用いて暗号化した暗号文（Ｅｎｃ（ｐｋ，ｒ×ｘｈ））からなるチャレンジを前記認証要求装置（手段）に送付する。
【０１０５】
前記照合補助装置（手段）は、前記認証要求装置（手段）からレスポンス（Ｅｎｃ（ｐｋ、（ｒ×ｘｈ）×（ｆＢ））を受け取ると、前記レスポンスと、前記一つの係数（ｒ）とその次数（ｈ）からなるチャレンジ補助（ｒ，ｈ）と、登録要求装置（手段）（例えば図１の１１０）で暗号化された前記登録情報（Ｅｎｃ（ｐｋ，ｆＡ））とに基づき、前記暗号化鍵（ｐｋ）を用いて、前記登録情報Ｅｎｃ（ｐｋ，ｆＡ）と認証情報の暗号化内積（Ｅｎｃ（ｐｋ，ｆＡ×ｆＢ））を生成する。前記照合補助装置（手段）は、暗号化鍵（ｐｋ）と暗号化内積（Ｅｎｃ（ｐｋ，ｆＡ×ｆＢ））と、暗号化された登録情報（Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））と、前記レスポンスに含まれるＥｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ｂｉ２）に基づき、距離（ｄＥ（Ａ，Ｂ））の暗号文（Ｅｎｃ（ｐｋ，ｄＥ（Ａ，Ｂ）））を算出する。
【０１０６】
前記照合補助装置（手段）は、暗号化された前記登録情報と前記認証情報の距離の前記暗号文を検証装置（例えば図１の１５０）に送付する。
【０１０７】
前記認証要求装置（手段）は、数値ベクトルである認証情報（ｂ０，…，ｂＬ−１）を多項式化し、多項式化した前記認証情報と、前記照合補助装置（手段）から送信された前記チャレンジ（Ｅｎｃ（ｐｋ，ｒ×ｘｈ）とに基づき、前記暗号化鍵（ｐｋ）を用いて、多項式化した前記認証情報（ｆＢ）と前記チャレンジの生成に用いられた前記多項式（ｒ×ｘｈ）との積の暗号文（Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ）））、および、多項式の各係数（数値ベクトルの各成分）の２乗和の暗号文（Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ｂｉ２））を算出する。
【０１０８】
前記認証要求装置（手段）は、多項式化した前記認証情報（ｆＢ）と、前記チャレンジの生成に用いられた前記多項式（ｒ×ｘｈ）との積の前記暗号文（Ｅｎｃ（ｐｋ，ｒ×ｘｈ）×（ｆＢ））、および、多項式の各係数（数値ベクトルの各成分）の２乗和の暗号文（Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ｂｉ２））を、前記レスポンスとして、前記照合補助装置（手段）に送付する。
【０１０９】
前記検証装置（手段）は、前記照合補助装置（手段）から受け取った、前記登録情報と前記認証情報の距離の暗号文（Ｅｎｃ（ｐｋ，ｄＥ（Ａ，Ｂ）））を、前記復号鍵（ｓｋ）を用いて復号し、前記登録情報と前記認証情報の距離を算出し、算出した前記距離又は、前記距離と予め定められた閾値との比較結果を、照合結果として出力する。
【０１１０】
本発明の一形態によれば、記憶装置（例えば図１の１２０）をさらに備えている。該記憶装置は、
登録データ記憶部（例えば図１の１２３）と、
前記登録要求装置（手段）から受け取った、暗号化された前記登録情報に対して識別子を付与する識別子付与部（手段）（例えば図１の１２１）と、
暗号化された前記登録情報と前記識別子との組からなる登録データを生成し前記登録データ記憶部に格納する登録データ生成部（手段）（例えば図１の１２２）と、
前記照合補助装置（手段）からの登録データ要求を受け、前記登録データ記憶部に記憶されている前記登録データの中から、前記登録データ要求に含まれる識別子と組とされている、暗号化された登録情報を、前記照合補助装置（手段）に送付する登録データ検索部（手段）（例えば図１の１２４）と、を備えた構成としてもよい。
【０１１１】
この場合、前記照合補助装置（手段）は、前記認証要求装置（手段）から受け取った認証要求に含まれ、前記認証情報に対応する認証識別子を含む登録データ要求を前記記憶装置（手段）に送付する構成としてもよい。前記照合補助装置（手段）は、前記記憶装置（手段）から、前記認証識別子に対応する暗号化された前記登録情報を受け取り、前記認証要求装置（手段）から受け取った前記レスポンスと、前記チャレンジ補助と、前記記憶装置（手段）から受け取った暗号化された前記登録情報とに基づき、前記登録情報と前記認証情報の距離の暗号文を算出する構成としてもよい。
【０１１２】
本発明の一形態によれば、記憶装置（例えば図５の２２０）をさらに備えている。該記憶装置は、
登録データ記憶部（例えば図５の２２３）と、
前記登録要求装置（手段）から受け取った、暗号化された前記登録情報に対して識別子を付与する識別子付与部（手段）（例えば図５の２２１）と、
暗号化された前記登録情報と前記識別子との組からなる登録データを生成し前記登録データ記憶部に格納する登録データ生成部（手段）（例えば図５の２２２）と、
を備えた構成としてもよい。
【０１１３】
この場合、前記照合補助装置（手段）（例えば図５の２４０）からの登録データ要求を受け、前記登録データ記憶部（図５の２２３）に格納されている一つ又は複数の登録データのうち、一部又はすべての登録データを、前記照合補助装置（手段）（図５の２４０）に送信する構成としてもよい。前記照合補助装置（手段）（図５の２４０）は、前記記憶装置（手段）から、一つ又は複数の登録データを受け取り、前記記憶装置（手段）から受け取った各登録データについて、前記認証要求装置（手段）（例えば図５の２３０）から受け取った前記レスポンスと、前記チャレンジ補助と、前記登録データに含まれる暗号化された登録情報とに基づき、暗号化された前記登録情報と前記認証情報の距離の暗号文を算出し、前記登録データについて、算出した前記登録情報と前記認証情報の距離の暗号文と、前記登録データに含まれる識別子との組を検証データとし、生成した一つ又は複数の前記検証データを前記検証装置（手段）（例えば図５の２５０）に送付する構成としてもよい。
【０１１４】
前記検証装置（手段）（図５の２５０）は、前記照合補助装置（手段）（図５の２４０）から、一つ又は複数の前記検証データを受け取り、各検証データについて、当該検証データに含まれる距離の暗号文を、前記復号鍵を用いて復号して距離を算出し、算出した前記距離と予め定められた閾値との比較結果、又は、算出した前記距離と前記検証データに含まれる識別子との組を、照合結果とし、該照合結果を出力する構成としてもよい。
【０１１５】
上記したように、本発明の一態様によれば、数値ベクトルである登録情報に基づき生成された多項式を暗号化鍵を用いて暗号化し、一つの項の係数が乱数でその他の項の係数が０である多項式を暗号化したチャレンジと、数値ベクトルである認証情報に基づき生成された多項式との積の暗号文を生成し、登録情報に基づき生成された多項式の暗号文と、前記チャレンジと、チャレンジと認証情報に基づき生成された多項式との積の暗号文と、から、登録情報と認証情報との距離の暗号文を生成する。そして、前記暗号文（前記登録情報と前記認証情報との距離の暗号文）を復号鍵を用いて復号し前記距離を算出する。
【０１１６】
上記態様では、前記登録要求装置は、登録情報（登録ベクトル）の第ｉ成分（ただしｉはＬ−１以下の非負整数、Ｌは２以上の正整数）をｉ次の項の係数とするＬ−１次多項式（ｆＡ）を生成し、前記認証要求装置は認証情報（認証ベクトル）の第ｉ成分（ただしｉはＬ−１以下の非負整数）の逆元を、Ｎ−ｉ次（ＮはＬより大の正整数）の項の係数とするＮ次多項式を生成するが、前記登録要求装置が登録情報（登録ベクトル）の第ｉ成分（ただしｉはＬ−１以下の非負整数）の逆元を、Ｎ−ｉ次（ＮはＬより大の正整数）の項の係数とするＮ次多項式を生成し、認証要求装置が認証情報（認証ベクトル）の第ｉ成分（ただしｉはＬ−１以下の非負整数、Ｌは２以上の正整数）を、ｉ次の項の係数とするＬ−１次多項式ｆＡを生成してもよい。
【０１１７】
本発明の例示的な実施形態について図面を参照して詳細に説明する。
【０１１８】
以下の各例示的な実施形態では、本発明を生体認証として用いた場合について説明する。各実施形態の暗号文照合システムは、生体認証の用途に限定されない。
【０１１９】
（第１の実施形態）
図１は、第１の例示的な実施形態に係る暗号文照合システム１００の構成を例示する図である。暗号文照合システム１００は、コンピュータシステム等による情報処理システムから構成される。第１の例示的な実施形態に係る暗号文照合システム１００は、大別して、登録要求装置１１０と、記憶装置１２０と、認証要求装置１３０と、照合補助装置１４０と、検証装置１５０とを有する。
【０１２０】
登録要求装置１１０は、登録情報抽出部１１１と、第一テンプレート生成部１１２と、第二テンプレート生成部１１３と、テンプレート生成部１１４とを有する。
【０１２１】
記憶装置１２０は、識別子付与部１２１と、登録データ生成部１２２と、登録データ記憶部１２３と、登録データ検索部１２４とを有する。
【０１２２】
認証要求装置１３０は、認証要求生成部１３１と、認証情報抽出部１３２と、第一レスポンス生成部１３３と、第二レスポンス生成部１３４と、レスポンス生成部１３５とを有する。
【０１２３】
照合補助装置１４０は、チャレンジ補助生成部１４１と、チャレンジ生成部１４２と、登録データ要求生成部１４３と、暗号化内積計算部１４４と、クエリ生成部１４５とを有する。
【０１２４】
検証装置１５０は、鍵生成部１５１と、復号鍵記憶部１５２と、クエリ検証部１５３と、照合結果生成部１５４とを有する。
【０１２５】
登録要求装置１１０と記憶装置１２０、記憶装置１２０と照合補助装置１４０、認証要求装置１３０と照合要求装置１４０、照合補助装置１４０と検証装置１５０は、例えば、通信ネットワークを介して、相互に通信することが可能であるものとする。あるいは、登録要求装置１１０、記憶装置１２０、照合補助装置１４０、認証要求装置１３０、検証装置１５０はＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、あるいは、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｒｏｋ）等のネットワークを介して接続する分散構成としてもよい。なお、登録要求装置１１０、記憶装置１２０、照合補助装置１４０、認証要求装置１３０、検証装置１５０のうち、複数の装置を一つのユニットに実装してもよいことは勿論である。登録要求装置１１０、記憶装置１２０、照合補助装置１４０、認証要求装置１３０は、検証装置１５０が公開した公開鍵（検証装置１５０が作成した、多項式演算が可能な準同型暗号方式の暗号化鍵と復号鍵のペアのうちの前記暗号化鍵）を取得可能に構成されている。登録要求装置１１０、記憶装置１２０、照合補助装置１４０、認証要求装置１３０、検証装置１５０の少なくとも一つの装置、又は全部の装置において、各部の少なくとも一部又は全部の処理は、コンピュータ（ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、プロセッサ）で実行されるプログラムによって実現するようにしてもよい。この場合、当該プログラムを記録したコンピュータ読み出し可能な半導体メモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等からプログラムをコンピュータの主メモリ等に読み出して実行することで各部の処理が実現される。
【０１２６】
なお、暗号文照合システム１００においては、登録要求装置１１０と、認証要求装置１３０とをまとめて、「第１ノード」と表してもよい。暗号文照合システム１００においては、記憶装置１２０と、照合補助装置１４０とをまとめて、「第２ノード」と表してもよい。また、暗号文照合システム１００においては、検証装置１５０を、「第３ノード」と表してもよい。すなわち、暗号文照合システム１００は、図１に例示した様態に限定されない。
【０１２７】
［動作の説明］
次に、図面を参照して、本実施形態に係る暗号文照合システム１００の動作について説明する。本発明の第１の例示的な実施形態に係る暗号文照合システム１００における処理について説明する。
【０１２８】
暗号文照合システム１００における処理は、大別して、
・準備フェーズ、
・登録フェーズ、及び、
・照合フェーズを含む。
【０１２９】
まず、各フェーズにおける処理の概要について説明する。本発明の第１の例示的な実施形態に係る暗号文照合システム１００では、加法及び乗法について準同型性を持つ準同型暗号方式を用いる。説明の便宜上、用いる暗号方式はメッセージとして、各係数がｔよりも小さい非負整数である、Ｎ−１次多項式を扱うものとする（係数∈Ｚｔ＝｛０，１，２，・・・，ｔ−１｝）。
【０１３０】
準備フェーズにおいては、主として、受信したセキュリティパラメータを用いて、暗号化鍵、及び、復号鍵が生成される。
【０１３１】
登録フェーズにおいては、主として、準備フェーズで生成された暗号化鍵を用いて、抽出された登録ベクトルが暗号化されたテンプレートが作成され、保存される。
【０１３２】
照合フェーズにおいては、主として、準備フェーズで生成された復号鍵を用いて、新たに抽出された認証ベクトルと一つの登録ベクトルとの間の距離が算出される。
【０１３３】
次に、暗号文照合システム１００が、上述した各フェーズにて実行する処理について詳細に説明する。
【０１３４】
図２は、準備フェーズにおいて、第１の例示的な実施形態に係る暗号文照合システム１００が実行する処理の一例を示すフローチャートである。図２を参照しながら、本実施形態に係る暗号文照合システム１００が、準備フェーズにて実行する処理について説明する。
【０１３５】
検証装置１５０における鍵生成部１５１は、セキュリティパラメータを受信し、受信したセキュリティパラメータを用いて、例えば、上述した鍵生成アルゴリズム（非特許文献１）に従い、暗号化鍵(公開鍵)ｐｋ、及び、復号鍵（秘密鍵）ｓｋを生成する（ステップＡ１）。なお、生成される暗号化鍵、及び、復号鍵は、加法及び乗法に関して準同型性を有する公開鍵暗号方式に準拠する。
【０１３６】
鍵生成部１５１は、生成した暗号化鍵ｐｋを、暗号文照合システム１００において公開する（ステップＡ２）。
【０１３７】
鍵生成部１５１は、生成した復号鍵ｓｋを、復号鍵記憶部１５２に格納する（ステップＡ３）。
【０１３８】
なお、本実施形態に係る暗号文照合システム１００が準備フェーズにて実行する処理は、図２に例示された様態に限定されない。
【０１３９】
図３は、登録フェーズにおいて、第１の例示的な実施形態に係る暗号文照合システム１００が実行する処理の一例を示すフローチャートである。図３を参照しながら、本実施形態に係る照合システム１００が、登録フェーズにて実行する処理について説明する。
【０１４０】
登録要求装置１１０における登録情報抽出部１１１は、登録対象の生体から生体情報（「登録ベクトル」と呼ぶ）
Ａ＝（ａ０，…，ａＬ−１）        ・・・（式２９）
を抽出する（ステップＢ１）。
【０１４１】
次に、登録要求装置１１０における第一テンプレート生成部１１２は、暗号化鍵ｐｋを用いて、次の式３０に従って生成される、登録ベクトルＡの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ａｉをｉ次の項の係数に持つＬ−１次多項式
ｆＡ（ｘ）＝Σｉ＝０〜Ｌ−１ａｉ×ｘｉ        ・・・（式３０）
の暗号文
Ｅｎｃ（ｐｋ，ｆＡ）
を計算する（ステップＢ２）。
【０１４２】
ステップＢ２で計算した暗号文Ｅｎｃ（ｐｋ，ｆＡ）を「第一テンプレート」と呼ぶことにする。
【０１４３】
次に、登録要求装置１１０における第二テンプレート生成部１１３は、暗号化鍵ｐｋを用いて、登録ベクトルＡの各成分の二乗和
Σｉ＝０〜Ｌ−１ａｉ２                  ・・・（式３１）
の暗号文
Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ａｉ２）
を計算する（ステップＢ３）。
【０１４４】
ステップＢ３で計算した登録ベクトルＡの各成分の二乗和暗号文Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ａｉ２）を「第二テンプレート」と呼ぶことにする。
【０１４５】
次に、登録要求装置１１０におけるテンプレート生成部１１４は、第一テンプレートと第二テンプレートをまとめ、テンプレート
（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））              ・・・（式３２）
とする（ステップＢ４）。
【０１４６】
登録要求装置１１０は、テンプレート（Ｅｎｃ（ｐｋ，ｆＡ）、Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））を記憶装置１２０に送付する（ステップＢ５）。
【０１４７】
次に、記憶装置１２０は、登録要求装置１１０から、テンプレート（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））を受け取る（ステップＢ６）。
【０１４８】
記憶装置１２０における識別子付与部１２１は、登録要求装置１１０から受け取ったテンプレート（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））に固有の識別子である登録識別子ｉｄを決定する（ステップＢ７）。
【０１４９】
記憶装置１２０は、登録識別子ｉｄを登録要求装置１１０に送付する（ステップＢ８）。
【０１５０】
次に、登録要求装置１１０は、記憶装置１２０から登録識別子ｉｄを受け取る（ステップＢ９）。
【０１５１】
登録要求装置１１０は、受信した登録識別子ｉｄを、ディスプレイ等のユーザインターフェース（ＵＩ）に表示する（ステップＢ１０）。あるいは、登録要求装置１１０は、社員証や、識別子カード等の、ＩＣ（ｉｎｔｅｇｒａｔｅｄ＿ｃｉｒｃｕｉｔ）カードに、受信した登録識別子ｉｄを格納してもよい。
【０１５２】
次に、記憶装置１２０における登録データ生成部１２２は、テンプレートと登録識別子ｉｄをまとめ、登録データ
（（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２）），ｉｄ）              ・・・（式３３）
とする（ステップＢ１１）。
【０１５３】
記憶装置１２０における登録データ記憶部１２３に、上記登録データ（式３３）を格納する（ステップＢ１２）。
【０１５４】
なお、本実施形態に係る暗号文照合システム１００が登録フェーズにて実行する処理は、図３に例示された様態に限定されない。例えば、ステップＢ８に先だってステップＢ１１とステップＢ１２とが実行されてもよい。
【０１５５】
図４は、認証フェーズにおいて、第１の例示的な実施形態に係る暗号文照合システム１００が実行する処理の一例を示すフローチャートである。図４を参照しながら、本実施形態に係る照合システム１００が、認証フェーズにて実行する処理について説明する。
【０１５６】
認証要求装置１３０は、認証対象の持つ識別子（「認証識別子」と呼ぶ）を受け取る（ステップＣ１）。
【０１５７】
次に、認証要求装置１３０における認証要求生成部１３１は、受け取った認証識別子を含む認証要求を生成する（ステップＣ２）。
【０１５８】
認証要求装置１３０は、認証要求を照合補助装置１４０に送付する（ステップＣ３）。
【０１５９】
照合補助装置１４０は、認証要求装置１３０から認証要求を受け取る（ステップＣ４）。
【０１６０】
次に、照合補助装置１４０におけるチャレンジ補助生成部１４１は、整数ｔより小さい整数ｒと、Ｎ−１より小さい整数ｈとをランダムに選択する。チャレンジ補助生成部１４１は、選択した値ｒ、ｈをまとめ、チャレンジ補助（ｒ，ｈ）とする（ステップＣ５）。
【０１６１】
次に、照合補助装置１４０におけるチャレンジ生成部１４２は、暗号化鍵ｐｋを用いて、チャレンジ補助（ｒ，ｈ）から算出される多項式
ｒ×ｘｈ                              ・・・（式３４）
の暗号文Ｅｎｃ（ｐｋ，ｒ×ｘｈ）を計算する（ステップＣ６）。ステップＣ６で計算した暗号文Ｅｎｃ（ｐｋ，ｒ×ｘｈ）を「チャレンジ」と呼ぶ。
【０１６２】
照合補助装置１４０は、チャレンジＥｎｃ（ｐｋ，ｒ×ｘｈ）を認証要求装置１３０に送付する（ステップＣ７）。
【０１６３】
次に、照合補助装置１４０における登録データ要求生成部１４３は、認証要求装置１３０から受け取った認証要求に含まれる認証識別子を含む登録データ要求を生成する（ステップＣ８）。
【０１６４】
照合補助装置１４０は、登録データ要求を記憶装置１２０に送付する（ステップＣ９）。
【０１６５】
次に、記憶装置１２０は、照合補助装置１４０から登録データ要求を受け取る（ステップＣ１０）。
【０１６６】
記憶装置１２０における登録データ検索部１２４は、登録データ記憶部１２３に格納されている、一つまたは複数の登録データのうち、登録データ要求に含まれる認証識別子を含む登録データを特定する（ステップＣ１１）。特定された登録データに含まれるテンプレートを「照合対象テンプレート」と呼ぶ。
【０１６７】
記憶装置１２０は、照合対象テンプレートを照合補助装置１４０に送付する（ステップＣ１２）。
【０１６８】
照合補助装置１４０は、記憶装置１２０から照合対象テンプレートを受け取る（ステップＣ１３）。
【０１６９】
認証要求装置１３０は、照合補助装置１４０がステップＣ７で送信したチャレンジを受け取る（ステップＣ１４）。
【０１７０】
次に、認証要求装置１３０における認証情報抽出部１３２は、認証対象の生体から生体情報（「認証ベクトル」という）
Ｂ＝（ｂ０，…，ｂＬ−１）                ・・・（式３５）
を抽出する（ステップＣ１５）。
【０１７１】
次に、認証要求装置１３０における第一レスポンス生成部１３３は、上記式２１に従って、認証ベクトルＢの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ｂｉの加法に関する逆元−ｂｉを、Ｎ−ｉ次の項の係数に持つＮ次多項式
ｆＢ（ｘ）＝−Σｉ＝０〜ｎ−１ｂｉ×ｘＮ−ｉ          ・・・（式３６）
を算出する。さらに、
・暗号化鍵ｐｋと、
・生成した多項式ｆＢと、
・照合補助装置１４０から受け取ったチャレンジＥｎｃ（ｐｋ，ｒ×ｘｈ）と、
に基づき、
例えば暗号方式の、暗号文のスカラー倍を計算できる性質（式６）を利用して、第一レスポンス
Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））              ・・・（式３７）
を生成する（ステップＣ１６）。
【０１７２】
次に、認証要求装置１３０における第二レスポンス生成部１３４は、暗号化鍵ｐｋを用いて、認証ベクトルＢの各成分の二乗和
Σｉ＝０〜Ｌ−１ｂｉ２        ・・・（式３８）
の暗号文
Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）
を計算する（ステップＣ１７）。ステップＣ１７で計算した認証ベクトルＢの各成分の二乗和の暗号文を「第二レスポンス」と呼ぶ。
【０１７３】
次に、認証要求装置１３０におけるレスポンス生成部１３５は、
・第一レスポンスＥｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））と、
・第二レスポンスＥｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）と
をまとめ、レスポンス
（Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ）），Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２））                ・・・（式３９）
とする（ステップＣ１８）。
【０１７４】
認証要求装置１３０は、ステップＣ１８で生成した上記レスポンス（式３９）を照合補助装置１４０に送付する（ステップＣ１９）。
【０１７５】
次に、照合補助装置１４０は、認証要求装置１３０から、上記レスポンス（式３９）を受け取る（ステップＣ２０）。
【０１７６】
次に、照合補助装置１４０における暗号化内積計算部１４４は、
・暗号化鍵ｐｋと、
・ステップＣ５で生成したチャレンジ補助（ｒ，ｈ）から生成される多項式−ｒ−１×ｘＮ−ｈと、
・ステップＣ２０で受け取ったレスポンス（Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ）），Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２））に含まれる第一レスポンスＥｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））と、
に基づき、
例えば暗号方式の、暗号文のスカラー倍を計算できる性質（式５）を用いて、
Ｅｎｃ（ｐｋ，ｆＢ）＝（−ｒ−１×ｘＮ−ｈ）×Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））        ・・・（式４０）
を計算する。
【０１７７】
さらに、暗号化内積計算部１４４は、
・暗号化鍵ｐｋと、
・ステップＣ１３で受け取った照合対象テンプレートに含まれる第一テンプレートＥｎｃ（ｐｋ，ｆＡ）と、
・計算した暗号文Ｅｎｃ（ｐｋ，ｆＢ）と、
に基づき、
暗号方式の乗法準同型性を利用して、暗号化内積
Ｅｎｃ（ｐｋ，ｆＡ×ｆＢ）
を生成する（ステップＣ２１）。
【０１７８】
なお、前述の通り（式２２、式２３）、ｆＡ×ｆＢの定数項は、登録ベクトルＡと認証ベクトルＢとの内積
＜Ａ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｉ×ｂｉ
と等しい。
【０１７９】
次に、照合補助装置１４０におけるクエリ生成部１４５は、
・暗号化鍵ｐｋと、
・ステップＣ２１で生成した暗号化内積Ｅｎｃ（ｐｋ，ｆＡ×ｆＢ）
と、
・ステップＣ１３で受け取った照合対象テンプレートに含まれる第二テンプレートＥｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２）と、
・ステップＣ２０で受け取ったレスポンスに含まれる第二レスポンスＥｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）と、
から、暗号方式の加法準同型性を利用して、クエリ
Ｅｎｃ（ｐｋ，ｆ）
を生成する（ステップＣ２２）。
【０１８０】
ただし、クエリＥｎｃ（ｐｋ，ｆ）において、ｆの定数項は、上記式２６に従う、登録ベクトルＡと認証ベクトルＢとのユークリッド距離
ｄＥ（Ａ，Ｂ）＝（Σｉ＝０〜ｎ−１ａｉ２）＋（Σｉ＝０〜ｎ−１ｂｉ２）−２＜Ａ，Ｂ＞
とする。
【０１８１】
照合補助装置１４０は、上記クエリＥｎｃ（ｐｋ，ｆ）を検証装置１５０に送付する（ステップＣ２３）。
【０１８２】
次に、検証装置１５０は、照合補助装置１４０から、上記クエリＥｎｃ（ｐｋ，ｆ）を受け取る（ステップＣ２４）。
【０１８３】
次に、検証装置１５０におけるクエリ検証部１５３は、復号鍵ｓｋを用いてクエリＥｎｃ（ｐｋ，ｆ）を復号する。
【０１８４】
復号結果Ｄｅｃ(ｓｋ，Ｅｎｃ（ｐｋ，ｆ）)として得られる多項式の定数項を、検証結果とする（ステップＣ２５）。
【０１８５】
前述の通り、検証結果は、登録ベクトルＡと認証ベクトルＢとのユークリッド距離ｄＥ（Ａ，Ｂ）である。
【０１８６】
次に、検証装置１５０における照合結果生成部１５４は、検証結果を照合結果とする。あるいは、照合結果生成部１５４は、検証結果とあらかじめ定められた閾値との大小を比較した結果を照合結果としてもよい（ステップＣ２６）。
【０１８７】
検証装置１５０は、算出した照合結果を出力する（ステップＣ２７）。
【０１８８】
なお、本実施形態に係る暗号文照合システム１００が認証フェーズにて実行する処理は、図４に例示された様態に限定されない。例えば、ステップＣ５に先だってステップＣ９からステップＣ１３が実行されてもよい。
【０１８９】
本実施形態に係る暗号文照合システム１００の上記の説明において、
・登録要求装置１１０における第一テンプレート生成部１１２が図３のステップＢ２において生成する多項式ｆＡは、登録ベクトルＡから式１９に従って生成される多項式であるとし、
・認証要求装置１３０における第一レスポンス生成部１３３が図４のステップＣ１６において生成する多項式ｆＢは、認証ベクトルから式２１に従って生成される多項式であるとした。しかし、本実施形態における二つの多項式の生成方法は、上記の方法にのみ限定されるものでないことは明らかである。例えば、
・登録要求装置１１０における第一テンプレート生成部１１２がステップＢ２において生成する多項式ｆＡを、登録ベクトルＡに基づき、式２１に従って生成される多項式とし、
・認証要求装置１３０における第一レスポンス生成部１３３がステップＣ１６において生成する多項式ｆＢを、認証ベクトルに基づき、式２０に従って生成される多項式としてもよい。
【０１９０】
［効果の説明］
次に、第１の例示的な実施形態に係る暗号文照合システム１００に関する効果について説明する。
【０１９１】
第１の例示的な実施形態に係る照合システム１００によれば、認証を要求するユーザが、自身の生体と識別子を提示して認証を行う、１：１認証を、安全に実現することが可能である。すなわち、次の２つの効果を有する。
【０１９２】
第１の例示的な実施形態に係る暗号文照合システム１００によれば、登録要求装置１１０が抽出した登録ベクトルは、登録要求装置１１０上で暗号化され、記憶装置１２０に送られる。また、認証要求装置１３０が抽出した認証ベクトルは、認証要求装置１３０上で暗号化され、照合補助装置１４０に送られる。
【０１９３】
これらの暗号文を復号できるのは、復号鍵を持つ検証装置１５０であるが、検証装置１５０が受け取るデータは、登録ベクトルと認証ベクトルの間のユークリッド距離の暗号文であり、登録ベクトルや認証ベクトルの値は開示されない。したがって、第１の例示的な実施形態に係る暗号文照合システム１００によれば、それぞれのベクトルを抽出する装置以外の装置には、登録ベクトルと認証ベクトルの距離以外の値は漏洩せず、検証装置において、登録ベクトルと認証ベクトルの間の距離を算出することが可能である。
【０１９４】
また、第１の例示的な実施形態に係る暗号文照合システム１００によれば、同じ登録ベクトルとの認証を行う際であっても、図４のステップＣ５で選ばれた乱数を用いた処理が行われる。したがって、照合処理の通信内容が漏洩したとしても、
・漏洩した内容を再送したり、
・漏洩した内容を利用して作成したデータを送付したりしても、
漏洩した照合時の距離と等しい距離を算出したり、小さい値を算出したりすることはできない。特に、第１の例示的な実施形態に係る暗号文照合システム１００を、登録ベクトルと認証ベクトルの間の距離が閾値より小さいときに「受理」とする認証に利用する場合、登録ベクトルを知らない攻撃者が「受理」とされない性質、すなわち、なりすまし攻撃への耐性を有する。
【０１９５】
さらに、第１の例示的な実施形態に係る暗号文照合システム１００では、復号鍵を持つ検証装置１５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しないように変形可能である。例えば、非特許文献４に記載された方式と同じ方法を適用することにより、復号鍵を持つ検証装置１５０が、登録ベクトルと認証ベクトルの間のユークリッド距離を算出できない方式に変形できる。復号鍵を持つ検証装置１５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しない方式は、特別な状況下においても復号鍵を持つ検証装置１５０が登録ベクトルの値を算出することを防ぐことができるため、より高い安全性を達成できる。
【０１９６】
［第２の実施形態］
［構成の説明］
図５は、第２の例示的な実施形態に係る暗号文照合システム（「情報処理システム」ともいう）２００の構成を模式的に例示する図である。第２の例示的な実施形態に係る暗号文照合システム２００は、大別して、登録要求装置２１０と、記憶装置２２０と、認証要求装置２３０と、照合補助装置２４０と、検証装置２５０とを有する。
【０１９７】
登録要求装置２１０は、登録情報抽出部２１１と、第一テンプレート生成部２１２と、第二テンプレート生成部２１３と、テンプレート生成部２１４とを有する。
【０１９８】
記憶装置２２０は、識別子付与部２２１と、登録データ生成部２２２と、登録データ記憶部２２３とを有する。
【０１９９】
認証要求装置２３０は、認証要求生成部２３１と、認証情報抽出部２３２と、第一レスポンス生成部２３３と、第二レスポンス生成部２３４と、レスポンス生成部２３５とを有する。
【０２００】
照合補助装置２４０は、チャレンジ補助生成部２４１と、チャレンジ生成部２４２と、登録データ要求生成部２４３と、暗号化内積計算部２４４と、クエリ生成部２４５と、検証データ生成部２４６と、を有する。
【０２０１】
検証装置２５０は、鍵生成部２５１と、復号鍵記憶部２５２と、クエリ検証部２５３と、照合結果生成部２５４と、を有する。
【０２０２】
登録要求装置２１０と記憶装置２２０、記憶装置２２０と照合補助装置２４０、認証要求装置２３０と照合要求装置２４０、照合補助装置２４０と検証装置２５０は、例えば、通信ネットワークを介して、相互に通信することが可能であるとする。
【０２０３】
なお、暗号文照合システム２００においては、登録要求装置２１０と、認証要求装置２３０とをまとめて、「第１ノード」と表してもよい。暗号文照合システム２００においては、記憶装置２２０と、照合補助装置２４０とをまとめて、「第２ノード」と表してもよい。また、暗号文照合システム２００においては、検証装置２５０を、「第３ノード」と表してもよい。すなわち、暗号文照合システム２００は、図５に例示した様態に限定されない。
【０２０４】
［動作の説明］
次に、第２の例示的な実施形態に係る暗号文照合システム２００の動作について説明する。
【０２０５】
本発明の第２の例示的な実施形態に係る暗号文照合システム２００における動作について説明する。暗号文照合システム２００における処理は、大別して、準備フェーズ、登録フェーズ、及び、照合フェーズを含む。まず、各フェーズにおける処理の概要について説明する。
【０２０６】
本発明の第２の例示的な実施形態に係る暗号文照合システムでは、加法及び乗法について準同型性を持つ準同型暗号方式を用いる。説明の便宜上、用いる暗号方式はメッセージとして、各係数がｔより小さい非負整数である、Ｎ−１次多項式を扱うものとする。
【０２０７】
準備フェーズにおいては、主として、受信したセキュリティパラメータを用いて、暗号化鍵、及び、復号鍵が生成される。
【０２０８】
登録フェーズにおいては、主として、準備フェーズで生成された暗号化鍵を用いて、抽出された登録ベクトルが暗号化されたテンプレートが作成され、保存される。
【０２０９】
照合フェーズにおいては、主として、準備フェーズで生成された復号鍵を用いて、新たに抽出された認証ベクトルと一つないし複数の登録ベクトルとの間の距離が算出される。
【０２１０】
次に、暗号文照合システム２００が、上述した各フェーズにて実行する処理について詳細に説明する。
【０２１１】
図６は、準備フェーズにおいて、第２の例示的な実施形態に係る暗号文照合システム２００が実行する処理の一例を示すフローチャートである。図６を参照しながら、第２の例示的な実施形態に係る暗号文照合システム２００が、準備フェーズにて実行する処理について説明する。
【０２１２】
検証装置２５０における鍵生成部２５１は、セキュリティパラメータを受信し、受信したセキュリティパラメータを用いて、例えば、上述した鍵生成アルゴリズムに従い、暗号化鍵ｐｋ、及び、復号鍵ｓｋを生成する（ステップＤ１）。なお、生成される暗号化鍵、及び、復号鍵は、加法及び乗法に関して準同型性を有する公開鍵暗号方式に準拠する。
【０２１３】
鍵生成部２５１は、暗号化鍵ｐｋを、暗号文照合システム２００において公開する（ステップＤ２）。
【０２１４】
鍵生成部２５１は、復号鍵ｓｋを、復号鍵記憶部２５２に格納する（ステップＤ３）。
【０２１５】
なお、本実施形態に係る暗号文照合システム２００が準備フェーズにて実行する処理は、図６に例示された様態に限定されない。
【０２１６】
図７は、登録フェーズにおいて、第２の例示的な実施形態に係る暗号文照合システム２００が実行する処理の一例を示すフローチャートである。図７を参照しながら、本実施形態に係る照合システム２００が、登録フェーズにて実行する処理について説明する。
【０２１７】
登録要求装置２１０における登録情報抽出部２１１は、登録対象の生体から生体情報（「登録ベクトル」と呼ぶ）
Ａ＝（ａ０、…、ａＬ−１）            ・・・（式４１）
を抽出する（ステップＥ１）。
【０２１８】
次に、登録要求装置２１０における第一テンプレート生成部２１２は、暗号化鍵ｐｋを用いて、次の式４２に従って生成される、登録ベクトルＡの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ａｉをｉ次の項の係数に持つＬ−１次多項式
ｆＡ（ｘ）＝Σｉ＝０〜Ｌ−１ａｉ×ｘｉ      ・・・（式４２）
の暗号文
Ｅｎｃ（ｐｋ，ｆＡ）を計算する（ステップＥ２）。
【０２１９】
ステップＥ２で計算した暗号文Ｅｎｃ（ｐｋ，ｆＡ）を「第一テンプレート」と呼ぶ。
【０２２０】
次に、登録要求装置２１０における第二テンプレート生成部２１３は、暗号化鍵ｐｋを用いて、登録ベクトルＡの各成分の二乗和
Σｉ＝０〜Ｌ−１ａｉ２            ・・・（式４３）
の暗号文
Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ａｉ２）を計算する（ステップＥ３）。ステップＥ３で計算した登録ベクトルＡの各成分の二乗和暗号文Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ａｉ２）を「第二テンプレート」と呼ぶ。
【０２２１】
次に、登録要求装置２１０におけるテンプレート生成部２１４は、第一テンプレートと第二テンプレートをまとめ、テンプレート
（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））          ・・・（式４４）
とする（ステップＥ４）。
【０２２２】
登録要求装置２１０は、上記テンプレート（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））を記憶装置２２０に送付する（ステップＥ５）。
【０２２３】
次に、記憶装置２２０は、登録要求装置２１０から上記テンプレート（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２））を受け取る（ステップＥ６）。
【０２２４】
記憶装置２２０における識別子付与部２２１は、受け取ったテンプレートに固有の識別子である登録識別子ｉｄを決定する（ステップＥ７）。
【０２２５】
記憶装置２２０は、登録識別子ｉｄを登録要求装置２１０に送付する（ステップＥ８）。
【０２２６】
次に、登録要求装置２１０は、記憶装置２２０から登録識別子ｉｄを受け取る（ステップＥ９）。登録要求装置２１０は、例えば、受信した登録識別子ｉｄを、ディスプレイ等のユーザインターフェース（ＵＩ）に表示するようにしてもよい（ステップＥ１０）。あるいは、登録要求装置２１０は、社員証や、識別子カード等の、ＩＣ（ｉｎｔｅｇｒａｔｅｄ＿ｃｉｒｃｕｉｔ）カードに、受信した登録識別子を格納してもよい。
【０２２７】
次に、記憶装置２２０における登録データ生成部２２２は、テンプレートと登録識別子をまとめ、登録データ
（（Ｅｎｃ（ｐｋ，ｆＡ），Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｉ２）），ｉｄ）          ・・・（式４５）
とする（ステップＥ１１）。
【０２２８】
記憶装置２２０における登録データ生成部２２２は、登録データ記憶部２２３に、上記登録データを格納する（ステップＥ１２）。
【０２２９】
なお、第２の例示的な実施形態に係る暗号文照合システム２００が登録フェーズで実行する処理は、図７に例示された様態に限定されない。例えば、ステップＥ８に先だってステップＥ１１とステップＥ１２とが実行されてもよい。
【０２３０】
図８は、認証フェーズにおいて、第２の例示的な実施形態に係る暗号文照合システム２００が実行する処理の一例を示すフローチャートである。図８を参照しながら、本実施形態に係る照合システム２００が、認証フェーズにて実行する処理について説明する。
【０２３１】
認証要求装置２３０における認証要求生成部２３１は、認証要求を生成する（ステップＦ１）。
【０２３２】
認証要求装置２３０は、認証要求を照合補助装置２４０に送付する（ステップＦ２）。
【０２３３】
照合補助装置２４０は、認証要求装置２３０から認証要求を受け取る（ステップＦ３）。
【０２３４】
次に、照合補助装置２４０におけるチャレンジ補助生成部２４１は、ｔより小さい整数をｒと、Ｎ−１よりも小さい整数ｈと、をランダムに選択する。選択した値をまとめ、チャレンジ補助（ｒ，ｈ）とする（ステップＦ４）。
【０２３５】
次に、照合補助装置２４０におけるチャレンジ生成部２４２は、暗号化鍵ｐｋを用いて、チャレンジ補助（ｒ，ｈ）から算出される多項式
ｒ×ｘｈ                ・・・（式４６）
の暗号文Ｅｎｃ（ｐｋ，ｒ×ｘｈ）を計算する（ステップＦ５）。
【０２３６】
ステップＦ５で計算した暗号文Ｅｎｃ（ｐｋ，ｒ×ｘｈ）を「チャレンジ」と呼ぶ。
【０２３７】
照合補助装置２４０は、上記チャレンジを認証要求装置２３０に送付する（ステップＦ６）。
【０２３８】
次に、照合補助装置２４０における登録データ要求生成部２４３は、登録データ要求を生成する（ステップＦ７）。
【０２３９】
照合補助装置２４０は、登録データ要求を記憶装置２２０に送付する（ステップＦ８）。
【０２４０】
次に、記憶装置２２０は、照合補助装置２４０から登録データ要求を受け取る（ステップＦ９）。
【０２４１】
記憶装置２２０は、登録データ記憶部２２３に格納されている一つまたは複数の登録データのうち、一部またはすべて（Ｍ個とする）の登録データを、照合補助装置２４０に送付する（ステップＦ１０）。ただし、各登録データは、テンプレートと登録識別子の組である。
【０２４２】
照合補助装置２４０は、記憶装置２２０からＭ個の登録データを受け取る（ステップＦ１１）。
【０２４３】
以下では、各ｊ番目（ｊ＝１，…，Ｍ）の登録データに含まれるテンプレートは、登録ベクトルＡｊから生成されたものとする。
【０２４４】
また、各ｊ番目（ｊ＝１、…、Ｍ）の登録データに含まれる第一テンプレートは、登録ベクトルＡｊから生成された多項式ｆＡ，ｊの暗号文Ｅｎｃ（ｐｋ，ｆＡ，ｊ）であるものとする。
【０２４５】
また、各ｊ番目（ｊ＝１，…，Ｍ）の登録データに含まれる第二テンプレートは、登録ベクトルＡｊの各成分の二乗和
Σｉ＝０〜ｎ−１ａｊ，ｉ２          ・・・（式４７）
の暗号文Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｊ，ｉ２）
であるものとする。
【０２４６】
認証要求装置２３０は、照合補助装置２４０から、上記チャレンジＥｎｃ（ｐｋ，ｒ×ｘｈ）を受け取る（ステップＦ１２）。
【０２４７】
次に、認証要求装置２３０における認証情報抽出部２３２は、認証対象の生体から生体情報（「認証ベクトル」と呼ぶ）
Ｂ＝（ｂ０，…，ｂＬ−１）          ・・・（式４８）
を抽出する（ステップＦ１３）。
【０２４８】
次に、認証要求装置２３０における第一レスポンス生成部２３３は、上記式２１に従って、認証ベクトルＢの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ｂｉの加法に関する逆元−ｂｉを、Ｎ−ｉ次の項の係数に持つＮ次多項式
ｆＢ（ｘ）＝−Σｉ＝０〜ｎ−１ｂｉ×ｘＮ−ｉ    ・・・（式４９）
を算出する。さらに、
・暗号化鍵ｐｋと、
・生成した多項式ｆＢと、
・受け取ったチャレンジＥｎｃ（ｐｋ，ｒ×ｘｈ）と、
から、
例えば、暗号方式の、暗号文のスカラー倍を計算できる性質（式６）を利用して、
第一レスポンス
Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））        ・・・（式５０）
を生成する（ステップＦ１４）。
【０２４９】
次に、認証要求装置２３０における第二レスポンス生成部２３４は、暗号化鍵ｐｋを用いて、認証ベクトルＢの各成分の二乗和
Σｉ＝０〜Ｌ−１ｂｉ２          ・・・（式５１）
の暗号文Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）を計算する（ステップＦ１５）。ステップＦ１５で計算した認証ベクトルＢの各成分の二乗和の暗号文Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）を「第二レスポンス」と呼ぶ。
【０２５０】
次に、認証要求装置２３０におけるレスポンス生成部２３５は、第一レスポンスと第二レスポンスをまとめ、レスポンス
（Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ）），Ｅｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２））        ・・・（式５２）
とする（ステップＦ１６）。
【０２５１】
認証要求装置２３０は、第一レスポンスと第二レスポンスをまとめた上記レスポンスを照合補助装置２４０に送付する（ステップＦ１７）。
【０２５２】
次に、照合補助装置２４０は、認証要求装置２３０から、上記レスポンスを受け取る（ステップＦ１８）。
【０２５３】
次に、照合補助装置２４０における暗号化内積計算部２４４は、
・暗号化鍵ｐｋと、
・ステップＦ４で生成したチャレンジ補助（ｒ，ｈ）から生成される項式−ｒ−１×ｘＮ−ｈと、
・ステップＦ１８で受け取ったレスポンスに含まれる第一レスポンスＥｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））と、
に基づき、
例えば暗号方式の、暗号文のスカラー倍を計算できる性質（式６）を用いて、
Ｅｎｃ（ｐｋ，ｆＢ）＝（−ｒ−１×ｘＮ−ｈ）×Ｅｎｃ（ｐｋ，（ｒ×ｘｈ）×（ｆＢ））      ・・・（式５３）
を計算する。
さらに、照合補助装置２４０における暗号化内積計算部２４４は、各ｊ（ｊ＝１，…，Ｍ）について、
・暗号化鍵ｐｋと、
・ステップＦ１１で受け取ったＭ個の登録データのうちｊ番目の登録データに含まれる第一テンプレートＥｎｃ（ｐｋ，ｆＡ，ｊ）と、
・計算した暗号文Ｅｎｃ（ｐｋ，ｆＢ）と、
に基づき、暗号方式の乗法準同型性を利用して、暗号化内積
Ｅｎｃ（ｐｋ，ｆＡ，ｊ×ｆＢ）      ・・・（式５４）
を生成する（ステップＦ１９）。
【０２５４】
なお、前述の通り、各ｊ（ｊ＝１，…，Ｍ）について、ｆＡ，ｊ×ｆＢの定数項は、登録ベクトルＡｊと認証ベクトルＢとの内積
＜Ａｊ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｊ，ｉ×ｂｉ 
と等しい。
【０２５５】
次に、照合補助装置２４０におけるクエリ生成部２４５は、各ｊ（ｊ＝１，…，Ｍ）について、
・暗号化鍵ｐｋと、
・ステップＦ１９で生成した暗号化内積Ｅｎｃ（ｐｋ，ｆＡ，ｊ×ｆＢ）
と、
・ステップＦ１１で受け取ったＭ個の登録データのうちｊ番目の登録データに含まれる第二テンプレートＥｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｊ，ｉ２）と、
・ステップＦ１８で受け取ったレスポンスに含まれる第二レスポンスＥｎｃ（ｐｋ，Σｉ＝０〜Ｌ−１ｂｉ２）と、
に基づき、暗号方式の加法準同型性を利用して、
クエリ
Ｅｎｃ（ｐｋ，ｆｊ）
を生成する（ステップＦ２０）。
【０２５６】
ただし、各ｊ（ｊ＝１，…，Ｍ）について、ｆｊの定数項は、上記式２６に従う、登録ベクトルＡｊと認証ベクトルＢとのユークリッド距離
ｄＥ（Ａｊ，Ｂ）＝（Σｉ＝０〜ｎ−１ａｊ，ｉ２）＋（Σｉ＝０〜ｎ−１ｂｉ２）−２＜Ａｊ，Ｂ＞
とする。
【０２５７】
次に、照合補助装置２４０における検証データ生成部２４６は、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の登録データのうちｊ番目の登録データに含まれる第二テンプレートからステップＦ２０で生成したクエリと、Ｍ個の登録データのうちｊ番目の登録データに含まれる登録識別子とを、ｊ番目の検証データとする（ステップＦ２１）。
【０２５８】
次に、照合補助装置２４０は、Ｍ個の検証データを検証装置２５０に送付する（ステップＦ２２）。
【０２５９】
次に、検証装置２５０は、照合補助装置２４０からＭ個の検証データを受け取る（ステップＦ２３）。
【０２６０】
検証装置２５０におけるクエリ検証部２５３は、各ｊ（ｊ＝１，…，Ｍ）について、復号鍵ｐｋを用いて、Ｍ個の検証データのうち、ｊ番目の検証データに含まれるクエリを復号し、復号結果として得られる多項式の定数項を、検証結果とする（ステップＦ２４）。
【０２６１】
前述の通り、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の検証データのうちｊ番目の検証データから生成された復号結果として得られる多項式の定数項は、登録ベクトルＡｊと認証ベクトルＢとのユークリッド距離ｄＥ（Ａｊ，Ｂ）である。
【０２６２】
次に、検証装置２５０における照合結果生成部２５４は、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の検証データのうち、ｊ番目の検証データに含まれるクエリからステップＦ２４で生成した検証結果と、ｊ番目の検証データに含まれる登録識別子と、をまとめ、ｊ番目の照合結果とする。
【０２６３】
あるいは、各ｊ（ｊ＝１，…，Ｍ）について、検証装置２５０における照合結果生成部２５４は、Ｍ個の検証データのうち、ｊ番目の検証データに含まれるクエリからステップＦ２４で生成したｊ番目の検証結果と、あらかじめ定められた閾値との大小を比較した結果と、ｊ番目の検証データに含まれる登録識別子と、をまとめ、ｊ番目の照合結果としてもよい（ステップＦ２５）。
【０２６４】
検証装置２５０は、算出したＭ個の照合結果を出力する（ステップＦ２６）。
【０２６５】
なお、第２の例示的な実施形態に係る暗号文照合システム２００が認証フェーズにて実行する処理は、図８に例示された様態に限定されない。例えば、ステップＦ７に先だってステップＦ１２からステップＦ１７が実行されてもよい。
【０２６６】
第２の例示的な実施形態に係る暗号文照合システム２００の上記の説明において、登録要求装置２１０における第一テンプレート生成部２１２が図７のステップＥ２において生成する多項式ｆＡは、登録ベクトルＡに基づき上記式２０に従って生成される多項式であるとした。また、認証要求装置２３０における第一レスポンス生成部２３３が図８のステップＦ１６において生成する多項式ｆＢは、認証ベクトルに基づき上記式２１に従って生成される多項式であるとした。
【０２６７】
第２の例示的な実施形態における二つの多項式の生成方法は、上記の方法に限らない。例えば、登録要求装置２１０における第一テンプレート生成部２１２がステップＥ２において生成する多項式ｆＡを、登録ベクトルＡに基づき上記式２１に従って生成される多項式とし、認証要求装置２３０における第一レスポンス生成部２３３が図８のステップＦ１６において生成する多項式ｆＢを、認証ベクトルに基づき上記式２０に従って生成される多項式としてもよい。
【０２６８】
［効果の説明］
次に、第２の例示的な実施形態に係る暗号文照合システム２００に関する効果について説明する。第２の実施形態に係る照合システム２００によれば、認証を要求するユーザが、自身の識別子を提示せず、登録された全ての情報と、認証に用いられる情報の照合を行う、１：Ｎ認証を安全に実現することが可能である。すなわち、次の２つの効果を有する。
【０２６９】
第２の例示的な実施形態に係る暗号文照合システム２００によれば、登録要求装置２１０が抽出した登録ベクトルは、登録要求装置２１０上で暗号化され、記憶装置２２０に送られる。
【０２７０】
また、認証要求装置２３０が抽出した認証ベクトルは、認証要求装置２３０上で暗号化され、照合補助装置２４０に送られる。これらの暗号文を復号できるのは、復号鍵を持つ検証装置２５０であるが、検証装置２５０の受け取るデータは登録ベクトルと認証ベクトルの間のユークリッド距離の暗号文であり、登録ベクトルや認証ベクトルの値を開示しない。
【０２７１】
したがって、第２の例示的な実施形態に係る暗号文照合システム２００によれば、それぞれのベクトルを抽出する装置以外の装置に登録ベクトルと認証ベクトルの距離以外の値を漏洩せず、登録ベクトルと認証ベクトルの間の距離を算出することが可能である。
【０２７２】
また、第２の例示的な実施形態に係る暗号文照合システム２００によれば、同じ登録ベクトルとの認証を行う際であっても、図８のステップＦ５で選ばれた乱数を用いた処理が行われる。
【０２７３】
したがって、照合処理の通信内容が漏洩したとしても、漏洩した内容を再送したり、漏洩した内容を利用して作成したデータを送付したりすることによって、漏洩した照合時の距離と等しい距離を算出させたり、小さい値を算出させたりすることができない。
【０２７４】
特に、第２の例示的な実施形態に係る暗号文照合システム２００を、距離が閾値より小さいときに「受理」とする認証に利用する場合、登録ベクトルを知らない攻撃者が「受理」とされない性質、すなわちなりすまし攻撃への耐性を有する。
【０２７５】
さらに、第２の例示的な実施形態に係る暗号文照合システム２００では、復号鍵を持つ検証装置２５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しないように変形することも可能である。例えば、非特許文献４に記載された方式と同じ方法を適用することにより、復号鍵を持つ検証装置２５０が、登録ベクトルと認証ベクトルの間のユークリッド距離を算出できない方式に変形できる。復号鍵を持つ検証装置２５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しない方式は、特別な状況下においても、復号鍵を持つ検証装置２５０が登録ベクトルの値を算出することを防ぐことができる。このため、より高い安全性を達成できる。
【０２７６】
［第３の実施形態］
次に、第３の例示的な実施形態について説明する。第３の例示的な実施形態は、前記第１の例示的な実施形態の説明で参照した図１に示す暗号文照合システム１００において、非特許文献１に示された暗号方式を用いる場合である。以下では、第３の例示的な実施形態に係る特徴的な部分を中心に説明し、前記第１の例示的な実施形態と同じ部分については説明を適宜省略する。
【０２７７】
第３の例示的な実施形態は、前述の、非特許文献１に記載された、加法及び情報に関して準同型性を持つ暗号方式を用いて構成される。本実施形態の構成には、非特許文献１の暗号方式の持つ次の特徴を利用する。
【０２７８】
非特許文献１の暗号方式の鍵生成アルゴリズムの受け取るパラメータは、整数Ｎおよび素数ｔを含む。非特許文献１の暗号方式の暗号化アルゴリズムは、各係数がｔより小さい、Ｎ−１次多項式をメッセージとして受け取る。
【０２７９】
各係数がｔより小さいＮ−１次多項式ｆに対し、ｆ×ｆ−１＝１を満たすｆ−１は必ずしも存在しない。すなわち、非特許文献１の暗号方式が暗号化するメッセージには、乗法に関する逆元は必ずしも存在しない。
【０２８０】
一方、ｔは素数であるため、任意の１以上ｔ未満の整数ｒに対し、ｔを法としてｒ×ｒ−１＝１を満たす、１以上ｔ未満の整数ｒ−１が存在する。
【０２８１】
さらに、ｈを０以上Ｎ−１以下の整数とする。
ｘｈ×（−ｘN−ｈ）＝−ｘN＝１      ・・・（式５５）
が成り立つ。
【０２８２】
ｒおよびｈについて、
（ｒ×ｘｈ）×（ｒ−１×（−ｘN−ｈ））＝１    ・・・（式５６）
が成り立つ。
【０２８３】
したがって、任意の１以上ｔ未満の整数ｒおよび０以上Ｎ−１以下の整数ｈについて、ｒ×ｘｈは非特許文献１の暗号方式を用いて暗号化できるメッセージであり、かつ逆元−ｒ−１×ｘN−ｈを持つ。
【０２８４】
［構成の説明］
第３の例示的な実施形態の構成は、図１に示した前記第１の実施形態に係る暗号文照合システム１００の構成と同様であるため、説明は省略する。
【０２８５】
［動作の説明］
次に、第３の例示的な実施形態に係る暗号文照合システム１００の動作について説明する。本実施形態に係る照合システム１００における動作は、前記第１の例示的な実施形態と同様に、大別して、準備フェーズ、登録フェーズ、及び、照合フェーズを含む。まず、各フェーズにおける処理の概要について説明する。
【０２８６】
準備フェーズにおいては、主として、受信したセキュリティパラメータを用いて、暗号化鍵、及び、復号鍵が生成される。
【０２８７】
登録フェーズにおいては、主として、準備フェーズで生成された暗号化鍵を用いて、抽出された登録ベクトルが暗号化されたテンプレートが作成され、保存される。
【０２８８】
照合フェーズにおいては、主として、準備フェーズで生成された復号鍵を用いて、新たに  抽出された認証ベクトルと一つの登録ベクトルとの間の距離が算出される。
【０２８９】
次に、暗号文照合システム１００が、上述した各フェーズにて実行する処理について詳細に説明する。
【０２９０】
第３の例示的な実施形態の準備フェーズは、前記第１の例示的な実施形態の図２のフローチャートに従う。図２を参照しながら、第３の実施形態に係る暗号文照合システム１００が、準備フェーズにて実行する処理について説明する。
【０２９１】
検証装置１５０における鍵生成部１５１は、４つのパラメータの組
λ＝（Ｎ，ｑ，ｔ，σ）    ・・・（式５７）
を受け取る。ただし、前述したように、Ｎは２冪の整数、ｑは２Ｎを法として１と合同な素数、ｔはｑより小さい正の素数、σはＮ次元離散ガウス分布の標準偏差である。
【０２９２】
次に、２つのＮ−１次多項式ｓおよびｅを標準偏差がσであるＮ次元離散ガウス分布に従って生成する。すなわち、離散ガウス分布に従って生成されたＮ個の値を係数とする多項式を生成する。ｓは秘密鍵となる。
【０２９３】
次に、各係数がｔより小さいＮ−１次多項式ｐ１をランダムに生成する。
【０２９４】
次に、
ｐ０＝−（ｐ１×ｓ＋ｔ×ｅ）    ・・・（式５８）
を計算する（ステップＡ１）。
（λ，ｐ０，ｐ１）を暗号化鍵ｐｋ、
（λ，ｐ０，ｐ１，ｓ）を復号鍵ｓｋとする。
【０２９５】
鍵生成部１５１は、暗号化鍵ｐｋを、暗号文照合システム１００において公開する（ステップＡ２）。鍵生成部１５１は、復号鍵ｓｋを、復号鍵記憶部１５２に格納する（ステップＡ３）。
【０２９６】
なお、第３の実施形態に係る暗号文照合システム１００が準備フェーズにて実行する処理は、図２に例示された様態に限定されない。
【０２９７】
第３の例示的な実施形態の登録フェーズは、第１の例示的な実施形態の図３のフローチャートに従う。図３を参照しながら、第３の実施形態に係る暗号文照合システム１００が、登録フェーズにて実行する処理について説明する。
【０２９８】
登録要求装置１１０における登録情報抽出部１１１は、登録対象の生体から生体情報（「登録ベクトル」と呼ぶ）
Ａ＝（ａ０，…，ａＬ−１）    ・・・（式５９）
を抽出する（ステップＢ１）。
【０２９９】
次に、登録要求装置１１０における第一テンプレート生成部１１２は、登録ベクトルＡ＝（ａ０，…，ａＬ−１）から、次の式６０（上記式２０）に従って生成される、登録ベクトルＡの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ａｉを、ｉ次の項の係数に持つＬ−１次多項式
ｆＡ＝Σｉ＝０〜Ｌ−１ａｉ×ｘｉ    ・・・（式６０）
を生成する。
【０３００】
次に、準備フェーズのステップＡ２において検証装置１５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ１とｇ１とｆ１とを生成する。
【０３０１】
次に、これらと、暗号化鍵ｐｋに含まれるｔ、ｐ０、ｐ１と、生成した多項式ｆＡと、に基づき、以下の二つの多項式、
ｃ１，０＝ｐ０×ｕ１＋ｔ×ｇ１＋ｆＡ      ・・・（式６１−１）
ｃ１，１＝ｐ１×ｕ１＋ｔ×ｆ１            ・・・（式６１−２）
を計算する。（ｃ１，０，ｃ１，１）を暗号文Ｃ１とする（ステップＢ２）。
【０３０２】
すなわち、Ｃ１は暗号化鍵ｐｋによるｆＡの暗号文である。ステップＢ２で計算した暗号文Ｃ１＝（ｃ１，０，ｃ１，１）を「第一テンプレート」と呼ぶ。
【０３０３】
次に、登録要求装置１１０における第二テンプレート生成部１１３は、登録ベクトルＡの各成分の二乗和
Σｉ＝０〜Ｌ−１ａｉ２  ・・・（式６２）
を計算する。
【０３０４】
次に、準備フェーズのステップＡ２において検証装置１５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ２とｇ２とｆ２とを生成する。
【０３０５】
次に、これらと、暗号化鍵の含むｔ、ｐ０、ｐ１と、生成した値Σｉ＝０〜Ｌ−１ａｉ２と、に基づき、以下の二つの多項式、
ｃ２，０＝ｐ０×ｕ２＋ｔ×ｇ２＋（Σｉ＝０〜Ｌ−１ａｉ２）  ・・・（式６３−１）
ｃ２，１＝ｐ１×ｕ２＋ｔ×ｆ２                             ・・・（式６３−２）
を計算する。（ｃ２，０，ｃ２，１）を暗号文Ｃ２とする（ステップＢ３）。すなわち、Ｃ２は暗号化鍵ｐｋによるΣｉ＝０〜Ｌ−１ａｉ２の暗号文である。ステップＢ３で計算した暗号文Ｃ２＝（ｃ２，０，ｃ２，１）を「第二テンプレート」と呼ぶ。
【０３０６】
次に、登録要求装置１１０におけるテンプレート生成部１１４は、第一テンプレートＣ１＝（ｃ１，０，ｃ１，１）と第二テンプレートＣ２＝（ｃ２，０，ｃ２，１）をまとめ、テンプレート（Ｃ１，Ｃ２）とする（ステップＢ４）。
【０３０７】
登録要求装置１１０は、上記テンプレート（Ｃ１，Ｃ２）を記憶装置１２０に送付する（ステップＢ５）。
【０３０８】
次に、記憶装置１２０は、登録要求装置１１０からテンプレート（Ｃ１，Ｃ２）を受け取る（ステップＢ６）。
【０３０９】
記憶装置１２０における識別子付与部１２１は、受け取ったテンプレート（Ｃ１，Ｃ２）に固有の識別子である登録識別子ｉｄを決定する（ステップＢ７）。
【０３１０】
記憶装置１２０は、登録識別子ｉｄを登録要求装置１１０に送付する（ステップＢ８）。
【０３１１】
次に、登録要求装置１１０は、記憶装置から登録識別子ｉｄを受け取る（ステップＢ９）。
【０３１２】
登録要求装置１１０は、例えば、受信した登録識別子ｉｄを、ディスプレイ等のユーザインターフェース（ＵＩ）に表示する（ステップＢ１０）。あるいは、登録データ装置１０２は、社員証や、識別子カード等の、ＩＣ（ｉｎｔｅｇｒａｔｅｄ＿ｃｉｒｃｕｉｔ）カードに、受信した登録識別子ｉｄを格納してもよい。  
【０３１３】
次に、記憶装置１２０における登録データ生成部１２２は、テンプレート（Ｃ１，Ｃ２）と登録識別子ｉｄをまとめ、登録データ
（（Ｃ１，Ｃ２），ｉｄ）
とする（ステップＢ１１）。
【０３１４】
記憶装置１２０における登録データ生成部１２２は、登録データ記憶部１２３に、登録データ（（Ｃ１，Ｃ２），ｉｄ）を格納する（ステップＢ１２）。
【０３１５】
なお、第３の実施形態に係る暗号文照合システム１００が登録フェーズにて実行する処理は、図３に例示された様態に限定されない。例えば、ステップＢ８に先だってステップＢ１１とステップＢ１２とが実行されてもよい。
【０３１６】
第３の例示的な実施形態の認証フェーズは、前記第１の例示的な実施形態の図４のフローチャートに従う。図４を参照しながら、第３の実施形態に係る暗号文照合システム１００が、認証フェーズにて実行する処理について説明する。
【０３１７】
認証要求装置１３０は認証対象の持つ識別子ｉｄ（「認証識別子」と呼ぶ）を受け取る（ステップＣ１）。
【０３１８】
次に、認証要求装置１３０における認証要求生成部１３１は、受け取った認証識別子ｉｄを含む認証要求を生成する（ステップＣ２）。
【０３１９】
認証要求装置１３０は、認証要求を照合補助装置１４０に送付する（ステップＣ３）。
【０３２０】
照合補助装置１４０は、認証要求装置１３０から認証要求を受け取る（ステップＣ４）。
【０３２１】
次に、照合補助装置１４０におけるチャレンジ補助生成部１４１は、ｔより小さい整数ｒと、Ｎ−１より小さい整数ｈとをランダムに選択する。選択した値をまとめ、チャレンジ補助（ｒ，ｈ）とする（ステップＣ５）。
【０３２２】
次に、照合補助装置１４０におけるチャレンジ生成部１４２は、チャレンジ補助（ｒ，ｈ）から多項式
ｒ×ｘｈ                        ・・・（式６４）
を算出する。
【０３２３】
次に、準備フェーズのステップＡ２において検証装置１５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ３とｇ３とｆ３とを生成する。
【０３２４】
次に、Ｎ−１次多項式ｕ３とｇ３とｆ３と、暗号化鍵の含むｔ、ｐ０、ｐ１と、多項式ｒ×ｘｈと、に基づき、以下の二つの多項式、
ｃ３，０＝ｐ０×ｕ３＋ｔ×ｇ３＋（ｒ×ｘｈ）            ・・・（式６５−１）
ｃ３，１＝ｐ１×ｕ３＋ｔ×ｆ３                          ・・・（式６５−２）
を計算する。（ｃ３，０，ｃ３，１）を暗号文Ｃ３とする（ステップＣ６）。すなわち、Ｃ３は暗号化鍵ｐｋによるｒ×ｘｈの暗号文である。ステップＣ６で計算した暗号文Ｃ３＝（ｃ３，０，ｃ３，１）を「チャレンジ」と呼ぶ。
【０３２５】
照合補助装置１４０は、チャレンジＣ３を認証要求装置１３０に送付する（ステップＣ７）。
【０３２６】
次に、照合補助装置１４０における登録データ要求生成部１４３は、認証要求装置１３０から受け取った認証要求に含まれる認証識別子ｉｄを含む登録データ要求を生成する（ステップＣ８）。
【０３２７】
照合補助装置１４０は、登録データ要求を記憶装置１２０に送付する（ステップＣ９）。
【０３２８】
次に、記憶装置１２０は、照合補助装置１４０から登録データ要求を受け取る（ステップＣ１０）。
【０３２９】
記憶装置１２０における登録データ検索部１２４は、登録データ記憶部に格納されている一つまたは複数の登録データのうち、登録データ要求に含まれる認証識別子ｉｄを含む登録データ（（Ｃ１，Ｃ２），ｉｄ）を特定する（ステップＣ１１）。
【０３３０】
特定された登録データに含まれるテンプレート（Ｃ１，Ｃ２）を「照合対象テンプレート」と呼ぶ。
【０３３１】
記憶装置１２０は、照合対象テンプレート（Ｃ１，Ｃ２）を照合補助装置１４０に送付する（ステップＣ１２）。
【０３３２】
照合補助装置１４０は、記憶装置１２０から照合対象テンプレート（Ｃ１，Ｃ２）を受け取る（ステップＣ１３）。
【０３３３】
認証要求装置１３０は、照合補助装置１４０からチャレンジＣ３＝（ｃ３，０，ｃ３，１-）を受け取る（ステップＣ１４）。
【０３３４】
次に、認証要求装置１３０における認証情報抽出部１３２は、認証対象の生体から生体情報（認証ベクトルと呼ぶ）
Ｂ＝（ｂ０，…，ｂＬ−１）            ・・・(式６６)
を抽出する（ステップＣ１５）。
【０３３５】
次に、認証要求装置１３０における第一レスポンス生成部１３３は、次の式６７に従って生成される、認証ベクトルＢの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ｂｉの加法に関する逆元−ｂｉをＮ−ｉ次の項の係数に持つ多項式
ｆＢ＝−Σｉ＝０〜ｎ−１ｂｉ×ｘＮ−ｉ          ・・・(式６７)
を生成する。
【０３３６】
ただし、多項式の次数がＮ以上となった場合には、前述したように、
ｘＮ＝−１、
ｘＮ＋１＝−ｘ、…
と置き換えることにより、多項式をＮ−１次以下にする。以下の計算においても同様に行う。
【０３３７】
次に、ステップＣ１４で受け取ったチャレンジＣ３＝（ｃ３，０，ｃ３，１）と、
生成した多項式ｆＢとに基づき、
ｃ４，０＝ｆＢ×ｃ３，０        ・・・(式６８−１)
ｃ４，１＝ｆＢ×ｃ３，１        ・・・(式６８−２)
を計算する。（ｃ４，０，ｃ４，１）を暗号文Ｃ４とする（ステップＣ１６）。すなわち、Ｃ４は暗号化鍵ｐｋによるｒ×ｘｈ×ｆＢの暗号文である。Ｃ４＝（ｃ４，０，ｃ４，１）を「第一レスポンス」と呼ぶ。
【０３３８】
次に、認証要求装置１３０における第二レスポンス生成部１３４は、認証ベクトルＢの各成分の二乗和
Σｉ＝０〜Ｌ−１ｂｉ２        ・・・(式６９)
を計算する。
【０３３９】
次に、準備フェーズのステップＡ２において検証装置１５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ５とｇ５とｆ５とを生成する。
【０３４０】
次に、３つのＮ−１次多項式ｕ５とｇ５とｆ５と、暗号化鍵の含むｔ、ｐ０、ｐ１と、生成した値Σｉ＝０〜Ｌ−１ｂｉ２と、に基づき、以下の二つの多項式、
ｃ５，０＝ｐ０×ｕ５＋ｔ×ｇ５＋（Σｉ＝０〜Ｌ−１ｂｉ２）    ・・・(式７０−１)
ｃ５，１＝ｐ１×ｕ５＋ｔ×ｆ５                               ・・・(式７０−２)
を計算する。（ｃ５，０，ｃ５，１）を暗号文Ｃ５とする（ステップＣ１７）。
【０３４１】
すなわち、Ｃ５は暗号化鍵ｐｋによるΣｉ＝０〜Ｌ−１ｂｉ２の暗号文である。ステップＣ１７で計算した暗号文Ｃ５＝（ｃ５，０，ｃ５，１）を「第二レスポンス」と呼ぶ。
【０３４２】
次に、認証要求装置１３０におけるレスポンス生成部１３５は、第一レスポンスＣ４＝（ｃ４，０，ｃ４，１）と第二レスポンスＣ５＝（ｃ５，０，ｃ５，１）をまとめ、レスポンス（Ｃ４，Ｃ５）とする（ステップＣ１８）。
【０３４３】
認証要求装置１３０は、上記レスポンス（Ｃ４，Ｃ５）を照合補助装置１４０に送付する（ステップＣ１９）。
【０３４４】
次に、照合補助装置１４０は、認証要求装置１３０から上記レスポンス（Ｃ４，Ｃ５）を受け取る（ステップＣ２０）。
【０３４５】
次に、照合補助装置１４０における暗号化内積計算部１４４は、ステップＣ５で生成したチャレンジ補助（ｒ，ｈ）から、
−ｒ−１×ｘＮ−ｈ        ・・・(式７１)
を計算する。ただし、ｒ−１はｔを法としてｒ×ｒ−１＝１を満たす、１以上ｔ未満の整数である。
【０３４６】
次に、照合補助装置１４０における暗号化内積計算部１４４は、
・ステップ１９で受け取った上記レスポンス（Ｃ４，Ｃ５）に含まれる第一レスポンスＣ４＝（ｃ４，０，ｃ４，１）と、
・生成した−ｒ−１×ｘＮ−ｈと、に基づき、
ｃ６，０＝（−ｒ−１×ｘＮ−ｈ）×ｃ４，０      ・・・(式７２−１)
ｃ６，１＝（−ｒ−１×ｘＮ−ｈ）×ｃ４，１      ・・・(式７２−２)
を計算する。
（ｃ６，０，ｃ６，１）    ・・・(式７３)
を暗号文Ｃ６とする。すなわち、Ｃ６は、暗号化鍵ｐｋによる
（ｒ×ｘｈ×ｆＢ）×（−ｒ−１×ｘＮ−ｈ）＝ｆＢ      ・・・(式７４)
の暗号文である。
【０３４７】
次に、照合補助装置１４０における暗号化内積計算部１４４は、
・ステップＣ１３で受け取った照合対象テンプレート（Ｃ１，Ｃ２）に含まれる第一テンプレートＣ１＝（ｃ１，０，ｃ１，１）と、
・生成した暗号文Ｃ６＝（ｃ６，０，ｃ６，１）と、に基づき、
ｃ７，０＝ｃ１，０×ｃ６，０                       ・・・(式７５−１)
ｃ７，１＝ｃ１，０×ｃ６，１＋ｃ１，１×ｃ６，０    ・・・(式７５−２)
ｃ７，２＝ｃ１，１×ｃ６，１                       ・・・(式７５−３)
を計算する。
（ｃ７，０，ｃ７，１，ｃ７，２）    ・・・(式７６)
を暗号文Ｃ７とする（ステップＣ２１）。すなわち、Ｃ７は、暗号化鍵ｐｋによるｆＡ×ｆＢの暗号文である。ステップＣ２１で計算した暗号文Ｃ７＝（ｃ７，０，ｃ７，１，ｃ７，２）を「暗号化内積」と呼ぶ。なお、前述の通り、ｆＡ×ｆＢの定数項は登録ベクトルＡと認証ベクトルＢとの内積＜Ａ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｉ×ｂｉと等しい。
【０３４８】
次に、照合補助装置１４０におけるクエリ生成部１４５は、
・ステップＣ１３で受け取った照合対象テンプレート（Ｃ１，Ｃ２）に含まれる第二テンプレートＣ２＝（ｃ２，０，ｃ２，１）と、
・ステップＣ２０で受け取ったレスポンス（Ｃ４，Ｃ５）に含まれる第二レスポンスＣ５＝（ｃ５，０，ｃ５，１）と、
・ステップＣ２１で生成した暗号化内積Ｃ７＝（ｃ７，０，ｃ７，１，ｃ７，２）と、に基づき、
ｃ８，０＝ｃ２，０＋ｃ５，０＋−２×ｃ７，０        ・・・(式７７−１)
ｃ８，１＝ｃ２，１＋ｃ５，１−２×ｃ７，１          ・・・(式７７−２)
ｃ８，２＝−２×ｃ７，２                            ・・・(式７７−３)
を計算する。（ｃ８，０，ｃ８，１，ｃ８，２）を暗号文Ｃ８とする（ステップＣ２２）。すなわち、Ｃ８は、暗号化鍵ｐｋによる
（Σｉ＝０〜ｎ−１ａｉ２）＋（Σｉ＝０〜ｎ−１ｂｉ２）−２×ｆＡ×ｆＢ      ・・・(式７８)
の暗号文である。計算した暗号文Ｃ８＝（ｃ８，０，ｃ８，１，ｃ８，２）を「クエリ」と呼ぶ。
【０３４９】
なお、前述の通り、ｆＡ×ｆＢの定数項は、登録ベクトルＡと認証ベクトルＢとの内積＜Ａ、Ｂ＞＝Σｉ＝０〜ｎ−１ａｉ×ｂｉと等しい。したがって、Ｃ８は登録ベクトルＡと認証ベクトルＢとのユークリッド距離ｄＥ（Ａ，Ｂ）を定数項に持つ多項式の暗号文である。
【０３５０】
次に、照合補助装置１４０は、上記クエリＣ８＝（ｃ８，０，ｃ８，１，ｃ８，２）を検証装置１５０に送付する（ステップＣ２３）。
【０３５１】
次に、検証装置１５０は、照合補助装置１４０から上記クエリＣ８を受け取る（ステップＣ２４）。
【０３５２】
検証装置１５０におけるクエリ検証部１５３は、
・クエリＣ８＝（ｃ８，０，ｃ８，１，ｃ８，２）と、
・秘密鍵ｓｋ＝（λ，ｐ０，ｐ１，ｓ）と
に基づき、
Ｄ１＝ｃ８，０＋ｃ８，１×ｓ＋ｃ８，２×ｓ２      ・・・(式７９)
を計算する。
【０３５３】
次に、Ｄ１をｑで割った余りをＤ２とする。Ｄ２がｑ／２以上であれば、Ｄ３＝Ｄ２−ｑとする。Ｄ２がｑ／２より小さければ、Ｄ３＝Ｄ２とする（Ｄ２∈Ｚ（ｑ）＝ ［−ｑ／２，ｑ／２）∩Ｚ）。
【０３５４】
次に、Ｄ３をｔで割った余りの多項式をＤ４とする。Ｄ４の定数項をＤ５とする（ステップＣ２５）。算出した値Ｄ５を、「検証結果」と呼ぶ。前述の通り、この定数項Ｄ５は登録ベクトルＡと認証ベクトルＢとのユークリッド距離ｄＥ（Ａ，Ｂ）である。
【０３５５】
次に、検証装置１５０における照合結果生成部１５４は、検証結果Ｄ５を照合結果ｄとする。あるいは、検証結果Ｄ５と、あらかじめ定められた閾値との大小を比較した結果を照合結果ｄとしてもよい（ステップＣ２６）。
【０３５６】
検証装置１５０は、算出した照合結果ｄを出力する（ステップＣ２７）。
【０３５７】
なお、第３の実施形態に係る暗号文照合システム１００が認証フェーズにて実行する処理は、図４に例示された様態に限定されない。例えば、ステップＣ５に先だってステップＣ９からステップＣ１３が実行されてもよい。
【０３５８】
第３の実施形態に係る暗号文照合システム１００の上記の説明において、登録要求装置１１０における第一テンプレート生成部１１２がステップＢ２において生成する多項式ｆＡは、登録ベクトルＡに基づき上記式２０に従って生成される多項式であるとし、認証要求装置１３０における第一レスポンス生成部１３３がステップＣ１６において生成する多項式ｆＢは、認証ベクトルに基づき上記式２１に従って生成される多項式であるとした。
【０３５９】
第３の実施形態における二つの多項式の生成方法は、上記の方法に限らない。例えば、登録要求装置１１０における第一テンプレート生成部１１２がステップＢ２において生成する多項式ｆＡを、登録ベクトルＡに基づき式２１に従って生成される多項式とし、認証要求装置１３０における第一レスポンス生成部１３３がステップＣ１６において生成する多項式ｆＢを、認証ベクトルに基づき式２０に従って生成される多項式としてもよい。
【０３６０】
［効果の説明］
次に、第３の例示的な実施形態に係る暗号文照合システム１００に関する効果について説明する。
【０３６１】
第３の例示的な実施形態に係る暗号文照合システム１００によれば、認証を要求するユーザが、自身の生体と識別子を提示して認証を行う、１：１認証を安全に実現することが可能である。すなわち、次の２つの効果を有する。
【０３６２】
第３の例示的な実施形態に係る暗号文照合システム１００によれば、登録要求装置１１０が抽出した登録ベクトルは、登録要求装置１１０上で暗号化され、記憶装置１２０に送られる。また、認証要求装置１３０が抽出した認証ベクトルは、認証要求装置１３０上で暗号化され、照合補助装置１４０に送られる。
【０３６３】
これらの暗号文を復号できるのは、復号鍵を持つ検証装置１５０であるが、検証装置１５０の受け取るデータは登録ベクトルと認証ベクトルの間のユークリッド距離の暗号文であり、登録ベクトルや認証ベクトルの値を開示しない。
【０３６４】
したがって、第３の例示的な実施形態に係る暗号文照合システム１００によれば、それぞれのベクトルを抽出する装置以外の装置に登録ベクトルと認証ベクトルの距離以外の値を漏洩せず、登録ベクトルと認証ベクトルの間の距離を算出することが可能である。
【０３６５】
また、第３の例示的な実施形態に係る暗号文照合システム１００によれば、同じ登録ベクトルとの認証を行う際であっても、ステップＣ５で選ばれた乱数を用いた処理が行われる。
【０３６６】
したがって、照合処理の通信内容が漏洩したとしても、漏洩した内容を再送したり、漏洩した内容を利用して作成したデータを送付したりすることによって、漏洩した照合時の距離と等しい距離を算出させたり、小さい値を算出させたりすることができない。
【０３６７】
特に、第３の例示的な実施形態に係る暗号文照合システム１００を、距離が閾値より小さいときに「受理」とする認証に利用する場合、登録ベクトルを知らない攻撃者が「受理」とされない性質、すなわちなりすまし攻撃への耐性を有する。
【０３６８】
さらに、第３の例示的な実施形態に係る暗号文照合システム１００は、高速な処理が可能な暗号方式である非特許文献１に記載された暗号方式を用いて構成される。そのため、高速な照合処理が可能である。
【０３６９】
さらに、第３の例示的な実施形態に係る暗号文照合システム１００では、復号鍵を持つ検証装置１５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しないように変形することが可能である。例えば、非特許文献４に記載された方式と同じ方法を適用することにより、復号鍵を持つ検証装置１５０が、登録ベクトルと認証ベクトルの間のユークリッド距離を算出できない方式に変形できる。復号鍵を持つ検証装置１５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しない方式は、特別な状況下においても復号鍵を持つ検証装置１５０が登録ベクトルの値を算出することを防ぐことができる。このため、より高い安全性を達成できる。
【０３７０】
［第４の実施形態］
次に、第４の例示的な実施形態について説明する。第４の例示的な実施形態は、前記第２の例示的な実施形態の説明で参照した図５に示す暗号文照合システム２００において、非特許文献１に示された暗号方式を用いる場合である。以下では、第４の例示的な実施形態に係る特徴的な部分を中心に説明し、前記第２の例示的な実施形態と同じ部分についての説明は適宜省略する。
【０３７１】
第４の例示的な実施形態は、非特許文献１に記載された、加法及び情報に関して準同型性を持つ暗号方式を用いて構成される。第４の例示的な実施形態の構成には、非特許文献１の暗号方式の持つ次の特徴を利用する。
【０３７２】
非特許文献１の暗号方式の鍵生成アルゴリズムの受け取るパラメータは、整数Ｎおよび素数ｔを含む。
【０３７３】
非特許文献１の暗号方式の暗号化アルゴリズムは、各係数がｔより小さい、Ｎ−１次多項式をメッセージとして受け取る。各係数がｔより小さいＮ−１次多項式ｆに対し、ｆ×ｆ−１＝１を満たすｆ−１は必ずしも存在しない。すなわち、非特許文献１の暗号方式が暗号化するメッセージには、必ずしも逆元が存在しない。
【０３７４】
一方、ｔは素数であるため、任意の１以上ｔ未満の整数ｒに対し、ｔを法として
ｒ×ｒ−１＝１                            ・・・(式８０)
を満たす、１以上ｔ未満の整数ｒ−１が存在する。
【０３７５】
さらに、ｈを０以上Ｎ−１以下の整数とする。ｒおよびｈについて、
（ｒ×ｘｈ）×（ｒ−１×（−ｘN−ｈ））＝１  ・・・(式８１)
が成り立つ。
【０３７６】
したがって、任意の１以上ｔ未満の整数ｒおよび０以上Ｎ−１以下の整数ｈについて、ｒ×ｘｈは非特許文献１の暗号方式を用いて暗号化できるメッセージであり、かつ逆元−ｒ−１×ｘN−ｈを持つ。
【０３７７】
［構成の説明］
第４の例示的な実施形態の構成は、図５に示した前記第２の例示的な実施形態に係る暗号文照合システム２００の構成と同様であるため、説明は省略する。
［動作の説明］
次に、第４の例示的な実施形態に係る暗号文照合システム２００の動作について説明する。
【０３７８】
次に、第４の例示的な実施形態に係る暗号文照合システム２００における動作は、前記第２の例示的な実施形態と同様に、大別して、準備フェーズ、登録フェーズ、及び、照合フェーズを含む。まず、各フェーズにおける処理の概要について説明する。
【０３７９】
準備フェーズにおいては、主として、受信したセキュリティパラメータを用いて、暗号化鍵、及び、復号鍵が生成される。
【０３８０】
登録フェーズにおいては、主として、準備フェーズで生成された暗号化鍵を用いて、抽出された登録ベクトルが暗号化されたテンプレートが作成され、保存される。
【０３８１】
照合フェーズにおいては、主として、準備フェーズで生成された復号鍵を用いて、新たに抽出された認証ベクトルと一つないし複数の登録ベクトルとの間の距離が算出される。
【０３８２】
次に、暗号文照合システム２００が、上述した各フェーズにて実行する処理について詳細に説明する。第４の例示的な実施形態の準備フェーズは、前記第２の例示的な実施形態に係る暗号文照合システム２００が実行する準備フェーズの処理の一例を示した図６のフローチャートに従う。図６を参照しながら、第４の例示的な実施形態に係る照合システム２００が準備フェーズにて実行する処理について説明する。
【０３８３】
検証装置２５０における鍵生成部２５１は、４つのパラメータの組
λ＝（Ｎ，ｑ，ｔ，σ）      ・・・(式８２)
を受け取る。ただしＮは２冪の整数、ｑは２Ｎを法として１と合同な素数、ｔはｑより小さい正の整数、σはＮ−１次多項式上のある離散ガウス分布の標準偏差である。
【０３８４】
次に、２つのＮ−１次多項式ｓおよびｅを標準偏差がσであるＮ次元離散ガウス分布に従って生成する。次に、各係数がｑより小さいＮ−１次多項式ｐ１をランダムに生成する。
【０３８５】
次に、ｐ０＝−（ｐ１×ｓ＋ｔ×ｅ）      ・・・(式８３)
を計算する。
（λ，ｐ０，ｐ１）を暗号化鍵（公開鍵）ｐｋ、
（λ，ｐ０，ｐ１，ｓ）を復号鍵（秘密鍵）ｓｋとする（ステップＤ１）。
【０３８６】
鍵生成部２５１は、暗号化鍵ｐｋを、暗号文照合システム２００において公開する（ステップＤ２）。鍵生成部２５１は、復号鍵ｓｋを、復号鍵記憶部２５２に格納する（ステップＤ３）。
【０３８７】
なお、第４の例示的な実施形態に係る暗号文照合システム２００が準備フェーズにて実行する処理は、図６に例示された様態に限定されない。
【０３８８】
第４の例示的な実施形態の登録フェーズは、前記第２の例示的な実施形態に係る暗号文照合システム２００が実行する登録フェーズの処理の一例を示した図７のフローチャートに従う。図７を参照しながら、第４の例示的な実施形態に係る照合システム２００が、登録フェーズにて実行する処理について説明する。
【０３８９】
登録要求装置２１０における登録情報抽出部２１１は、登録対象の生体から生体情報（登録ベクトルと呼ぶ）Ａ＝（ａ０，…，ａＬ−１）      ・・・(式８４)
を抽出する（ステップＥ１）。
【０３９０】
次に、登録要求装置２１０における第一テンプレート生成部２１２は、登録ベクトルＡ＝（ａ０，…，ａＬ−１）から、次の式８５（上記式２０）に従って生成される、登録ベクトルＡの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ａｉをｉ次の項の係数に持つＬ−１次多項式
ｆＡ＝Σｉ＝０〜Ｌ−１ａｉ×ｘｉ      ・・・(式８５)
を生成する。
【０３９１】
次に、準備フェーズのステップＤ２において検証装置２５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ１とｇ１とｆ１とを生成する。
【０３９２】
次に、Ｎ−１次多項式ｕ１とｇ１とｆ１と、暗号化鍵ｐｋに含まれるｔ、ｐ０、ｐ１と、生成した多項式ｆＡと、に基づき、以下の二つの多項式、
ｃ１，０＝ｐ０×ｕ１＋ｔ×ｇ１＋ｆＡ      ・・・(式８６−１)
ｃ１，１＝ｐ１×ｕ１＋ｔ×ｆ１            ・・・(式８６−２)
を計算する。（ｃ１，０，ｃ１，１）を暗号文Ｃ１とする（ステップＥ２）。すなわち、Ｃ１は暗号化鍵ｐｋによるｆＡの暗号文である。計算した暗号文Ｃ１＝（ｃ１，０，ｃ１，１）を「第一テンプレート」と呼ぶ。
【０３９３】
次に、登録要求装置２１０における第二テンプレート生成部２１３は、登録ベクトルＡの各成分の二乗和
Σｉ＝０〜Ｌ−１ａｉ２      ・・・(式８７)
を計算する。
【０３９４】
次に、準備フェーズのステップＤ２において検証装置２５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ２とｇ２とｆ２とを生成する。
【０３９５】
次に、Ｎ−１次多項式ｕ２とｇ２とｆ２と、暗号化鍵ｐｋに含まれるｔ、ｐ０、ｐ１と、生成した値Σｉ＝０〜Ｌ−１ａｉ２と、に基づき、以下の二つの多項式、
ｃ２，０＝ｐ０×ｕ２＋ｔ×ｇ２＋（Σｉ＝０〜Ｌ−１ａｉ２）  ・・・(式８８−１)
ｃ２，１＝ｐ１×ｕ２＋ｔ×ｆ２                              ・・・(式８８−２)
を計算する。（ｃ２，０，ｃ２，１）を暗号文Ｃ２とする（ステップＥ３）。すなわち、Ｃ２は暗号化鍵ｐｋによるΣｉ＝０〜Ｌ−１ａｉ２の暗号文である。計算した暗号文Ｃ２＝（ｃ２，０，ｃ２，１）を「第二テンプレート」と呼ぶ。
【０３９６】
次に、登録要求装置２１０におけるテンプレート生成部２１４は、第一テンプレートｃ１＝（ｃ１，０，ｃ１，１）と第二テンプレートＣ２＝（ｃ２，０，ｃ２，１）をまとめ、テンプレート（Ｃ１，Ｃ２）とする（ステップＥ４）。
【０３９７】
登録要求装置２１０は、テンプレートを記憶装置２２０に送付する（ステップＥ５）。
【０３９８】
次に、記憶装置２２０は、登録要求装置２１０からテンプレート（Ｃ１，Ｃ２）を受け取る（ステップＥ６）。
【０３９９】
記憶装置２２０における識別子付与部２２１は、受け取ったテンプレートに固有の識別子である登録識別子ｉｄを決定する（ステップＥ７）。
【０４００】
記憶装置２２０は、登録識別子ｉｄを登録要求装置２１０に送付する（ステップＥ８）。
【０４０１】
次に、登録要求装置２１０は、記憶装置から登録識別子ｉｄを受け取る（ステップＥ９）。登録要求装置２１０は、例えば、受信した登録識別子ｉｄを、ディスプレイ等のユーザインターフェース（ＵＩ）に表示する（ステップＥ１０）。あるいは、登録要求装置２１０は、社員証や、識別子カード等の、ＩＣ（ｉｎｔｅｇｒａｔｅｄ＿ｃｉｒｃｕｉｔ）カードに、受信した登録識別子ｉｄを格納してもよい。  
【０４０２】
次に、記憶装置２２０における登録データ生成部２２２は、テンプレート（Ｃ１，Ｃ２）と登録識別子ｉｄをまとめ、登録データ
（（Ｃ１，Ｃ２），ｉｄ）        ・・・(式８９)
とする（ステップＥ１１）。
【０４０３】
記憶装置２２０における登録データ生成部２２２は、登録データ記憶部２２３に、登録データ（（Ｃ１，Ｃ２），ｉｄ）を格納する（ステップＥ１２）。
【０４０４】
なお、第４の例示的な実施形態に係る暗号文照合システム２００が登録フェーズにて実行する処理は、図７に例示された様態に限定されない。例えば、ステップＥ８に先だってステップＥ１１とステップＥ１２とが実行されてもよい。
【０４０５】
第４の例示的な実施形態の認証フェーズの処理の一例は、前記第２の例示的な実施形態に係る暗号文照合システム２００が実行する処理の一例を示した図８のフローチャートに従う。図８を参照しながら、第４の例示的な実施形態に係る照合システム２００が、認証フェーズにて実行する処理について説明する。
【０４０６】
認証要求装置２３０における認証要求生成部２３１は、認証要求を生成する（ステップＦ１）。
【０４０７】
認証要求装置２３０は、認証要求を照合補助装置２４０に送付する（ステップＦ２）。
【０４０８】
照合補助装置２４０は、認証要求装置２３０から認証要求を受け取る（ステップＦ３）。
【０４０９】
次に、照合補助装置２４０におけるチャレンジ補助生成部２４１は、ｔより小さい整数ｒと、Ｎ−１より小さい整数ｈとをランダムに選択する。選択した値をまとめ、チャレンジ補助（ｒ，ｈ）とする（ステップＦ４）。
【０４１０】
次に、照合補助装置２４０におけるチャレンジ生成部２４２は、チャレンジ補助（ｒ，ｈ）から多項式
ｒ×ｘｈ      ・・・(式９０)
を算出する。
【０４１１】
次に、準備フェーズのステップＤ２において検証装置２５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って、３つのＮ−１次多項式ｕ３とｇ３とｆ３とを生成する。
【０４１２】
次に、３つのＮ−１次多項式ｕ３とｇ３とｆ３と、暗号化鍵の含むｔ、ｐ０、ｐ１-と、多項式ｒ×ｘｈと、に基づき、以下の二つの多項式、
ｃ３，０＝ｐ０×ｕ３＋ｔ×ｇ３＋（ｒ×ｘｈ）      ・・・(式９１−１)
ｃ３，１＝ｐ１×ｕ３＋ｔ×ｆ３                    ・・・(式９１−２)
を計算する。（ｃ３，０，ｃ３，１）を暗号文Ｃ３とする（ステップＦ５）。すなわち、Ｃ３は暗号化鍵ｐｋによるｒ×ｘｈの暗号文である。計算した暗号文Ｃ３＝（ｃ３，０，ｃ３，１）を「チャレンジ」と呼ぶ。照合補助装置２４０は、チャレンジＣ３を認証要求装置２３０に送付する（ステップＦ６）。
【０４１３】
次に、照合補助装置２４０における登録データ要求生成部２４３は、登録データ要求を生成する（ステップＦ７）。
【０４１４】
照合補助装置２４０は、登録データ要求を記憶装置２２０に送付する（ステップＦ８）。
【０４１５】
次に、記憶装置２２０は、照合補助装置２４０から登録データ要求を受け取る（ステップＦ９）。
【０４１６】
記憶装置２２０は、登録データ記憶部２２３に格納されている一つまたは複数の登録データのうち、一部またはすべて（Ｍ個とする）の登録データを照合補助装置２４０に送付する（ステップＦ１０）。ただし、各登録データはテンプレートと登録識別子の組である。
【０４１７】
照合補助装置２４０は、記憶装置２２０からＭ個の登録データを受け取る（ステップＦ１１）。
【０４１８】
以下では、各ｊ番目（ｊ＝１，…，Ｍ）の登録データを
（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）      ・・・(式９２)
と表す。
【０４１９】
また、各ｊ番目（ｊ＝１，…，Ｍ）の登録データ（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）に含まれるテンプレート（Ｃｊ，１，Ｃｊ，２）は、登録ベクトルＡｊから生成されたものであるものとする。
【０４２０】
また、各ｊ番目（ｊ＝１，…，Ｍ）の登録データ（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）に含まれる第一テンプレートＣｊ，１は、登録ベクトルＡｊから生成された多項式ｆＡ，ｊの暗号文
Ｅｎｃ（ｐｋ、ｆＡ，ｊ）＝（ｃｊ，１，０，ｃｊ，１，１）      ・・・(式９３)
であるものとする。
【０４２１】
また、各ｊ番目（ｊ＝１，…，Ｍ）の登録データ（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）に含まれる第二テンプレートＣｊ，２は、登録ベクトルＡｊの各成分の二乗和
Σｉ＝０〜ｎ−１ａｊ，ｉ２      ・・・(式９４)
の暗号文
Ｅｎｃ（ｐｋ，Σｉ＝０〜ｎ−１ａｊ，ｉ２）＝（ｃｊ，２，０，ｃｊ，２，１）        ・・・(式９５)
であるものとする。
【０４２２】
認証要求装置２３０は、照合補助装置２４０からチャレンジを受け取る（ステップＦ１２）。
【０４２３】
次に、認証要求装置２３０における認証情報抽出部２３２は、認証対象の生体から生体情報（「認証ベクトル」と呼ぶ）
Ｂ＝（ｂ０，…，ｂＬ−１）      ・・・(式９６)
を抽出する（ステップＦ１３）。
【０４２４】
次に、認証要求装置２３０における第一レスポンス生成部２３３は、次の式９７（上記式２０）に従って生成される、認証ベクトルＢの各ｉ番目（ｉ＝０，…，Ｌ−１）の成分ｂｉの加法に関する逆元−ｂｉをＮ−ｉ次の項の係数に持つ多項式
ｆＢ＝−Σｉ＝０〜ｎ−１ｂｉ×ｘＮ−ｉ  ・・・(式９７)
を生成する。
【０４２５】
ただし、多項式の次数がＮ以上となった場合には、
ｘＮ＝−１、ｘＮ＋１＝−ｘ、…
と置き換えることにより、多項式をＮ−１次以下にする。以下の計算においても同様に行う。
【０４２６】
次に、ステップＦ１２で受け取ったチャレンジＣ３＝（ｃ３，０，ｃ３，１）と、生成した多項式ｆＢと、に基づき、
ｃ４，０＝ｆＢ×ｃ３，０  ・・・(式９８−１)
ｃ４，１＝ｆＢ×ｃ３，１  ・・・(式９８−２)
を計算する。（ｃ４，０，ｃ４，１）を暗号文Ｃ４とする（ステップＦ１４）。すなわち、Ｃ４は暗号化鍵ｐｋによるｒ×ｘｈ×ｆＢの暗号文である。Ｃ４＝（ｃ４，０，ｃ４，１）を「第一レスポンス」と呼ぶ。
【０４２７】
次に、認証要求装置２３０における第二レスポンス生成部２３４は、認証ベクトルＢの各成分の二乗和
Σｉ＝０〜Ｌ−１ｂｉ２      ・・・(式９９)
を計算する。
【０４２８】
次に、準備フェーズのステップＡ２において、検証装置２５０が公開した暗号化鍵ｐｋ＝（λ，ｐ０，ｐ１）に含まれるパラメータσを用い、標準偏差がσであるＮ次元離散ガウス分布に従って３つのＮ−１次多項式ｕ５とｇ５とｆ５とを生成する。
【０４２９】
次に、３つのＮ−１次多項式ｕ５とｇ５とｆ５と、暗号化鍵ｐｋに含まれるｔ、ｐ０、ｐ１と、生成した値Σｉ＝０〜Ｌ−１ｂｉ２と、に基づき、以下の二つの多項式、
ｃ５，０＝ｐ０×ｕ５＋ｔ×ｇ５＋（Σｉ＝０〜Ｌ−１ｂｉ２）  ・・・(式１００−１)
ｃ５，１＝ｐ１×ｕ５＋ｔ×ｆ５                             ・・・(式１００−２)
を計算する。（ｃ５，０，ｃ５，１）を暗号文Ｃ５とする（ステップＦ１５）。すなわち、Ｃ５は暗号化鍵ｐｋによる、Σｉ＝０〜Ｌ−１ｂｉ２ 
の暗号文である。ステップＦ１５で計算した暗号文Ｃ５＝（ｃ５，０，ｃ５，１）を「第二レスポンス」と呼ぶ。
【０４３０】
次に、認証要求装置２３０におけるレスポンス生成部２３５は、第一レスポンスＣ４＝（ｃ４，０，ｃ４，１）と第二レスポンスＣ５＝（ｃ５，０，ｃ５，１）をまとめ、レスポンス（Ｃ４，Ｃ５）とする（ステップＦ１６）。
【０４３１】
認証要求装置２３０は、上記レスポンス（Ｃ４，Ｃ５）を照合補助装置２４０に送付する（ステップＦ１７）。
【０４３２】
次に、照合補助装置２４０は、認証要求装置２３０から上記レスポンス（Ｃ４，Ｃ５）を受け取る（ステップＦ１８）。
【０４３３】
次に、照合補助装置２４０における暗号化内積計算部２４４は、ステップＦ４で生成したチャレンジ補助（ｒ，ｈ）から、
−ｒ−１×ｘＮ−ｈ      ・・・(式１０１)
を計算する。ただし、ｒ−１はｔを法として、
ｒ×ｒ−１＝１          ・・・(式１０２)
を満たす、１以上ｔ未満の整数である。
【０４３４】
次に、照合補助装置２４０における暗号化内積計算部２４４は、ステップＦ１８で受け取ったレスポンス（Ｃ４，Ｃ５）に含まれる第一レスポンスＣ４＝（ｃ４，０，ｃ４，１）と、生成した−ｒ−１×ｘＮ−ｈと、に基づき、
ｃ６，０＝（−ｒ−１×ｘＮ−ｈ）×ｃ４，０  ・・・(式１０３−１)
ｃ６，１＝（−ｒ−１×ｘＮ−ｈ）×ｃ４，１  ・・・(式１０３−２)
を計算する。
（ｃ６，０，ｃ６，１）    ・・・(式１０４)
を暗号文Ｃ６とする。すなわち、Ｃ６は、暗号化鍵ｐｋによる
（ｒ×ｘｈ×ｆＢ）×（−ｒ−１×ｘＮ−ｈ）＝ｆＢ      ・・・(式１０５)
の暗号文である。
【０４３５】
次に、照合補助装置２４０における暗号化内積計算部２４４は、各ｊ（ｊ＝１，…，Ｍ）について、ステップＦ１１で受け取ったＭ個の登録データのうち、
ｊ番目の登録データ（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）に含まれる第一テンプレートＣｊ，１＝（ｃｊ，１，０，ｃｊ，１，１）と、
生成した暗号文Ｃ６＝（ｃ６，０，ｃ６，１）と、に基づき、
ｃｊ，７，０＝ｃｊ，１，０×ｃ６，０                         ・・・(式１０６−１)
ｃｊ，７，１＝ｃｊ，１，０×ｃ６，１＋ｃｊ，１，１×ｃ６，０  ・・・(式１０６−２)
ｃｊ，７，２＝ｃｊ，１，１×ｃ６，１                         ・・・(式１０６−３)
を計算する。
【０４３６】
各ｊ（ｊ＝１，…，Ｍ）について、
（ｃｊ，７，０，ｃｊ，７，１，ｃｊ，７，２）      ・・・(式１０７)
を暗号文Ｃｊ，７とする（ステップＦ１９）。すなわち、各ｊ（ｊ＝１，…，Ｍ）について、Ｃｊ，７は暗号化鍵ｐｋによるｆＡ，ｊ×ｆＢの暗号文である。
【０４３７】
各ｊ（ｊ＝１，…，Ｍ）について、計算した暗号文Ｃｊ，７＝（ｃｊ，７，０，ｃｊ，７，１，ｃｊ，７，２）を「暗号化内積」と呼ぶ。
【０４３８】
なお、前述の通り、各ｊ（ｊ＝１，…，Ｍ）について、ｆＡ，ｊ×ｆＢの定数項は登録ベクトルＡｊと認証ベクトルＢとの内積＜Ａｊ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｊ，ｉ×ｂｉと等しい。
【０４３９】
次に、照合補助装置２４０におけるクエリ生成部２４５は、各ｊ（ｊ＝１，…，Ｍ）について、
・ステップＦ１１で受け取ったＭ個の登録データのうち、
ｊ番目の登録データ（（Ｃｊ，１，Ｃｊ，２），ｉｄｊ）に含まれる第二テンプレート
Ｃｊ，２＝（ｃｊ，２，０，ｃｊ，２，１）と、
・ステップＦ１８で受け取ったレスポンス（Ｃ４，Ｃ５）に含まれる第二レスポンスＣ５＝（ｃ５，０，ｃ５，１）と、
・ステップＦ１９で生成したｊ番目の暗号化内積Ｃｊ，７＝（ｃｊ，７，０，ｃｊ，７，１，ｃｊ，７，２）と、に基づき、
ｃｊ，８，０＝ｃｊ，２，０＋ｃ５，０＋−２×ｃｊ，７，０    ・・・(式１０８−１)
ｃｊ，８，１＝ｃｊ，２，１＋ｃ５，１−２×ｃｊ，７，１      ・・・(式１０８−２)
ｃｊ，８，２＝−２×ｃｊ，７，２                            ・・・(式１０８−３)
を計算する。
【０４４０】
各ｊ（ｊ＝１，…，Ｍ）について、（ｃｊ，８，０，ｃｊ，８，１，ｃｊ，８，２）を暗号文Ｃｊ，８とする（ステップＦ２０）。
【０４４１】
すなわち、各ｊ（ｊ＝１，…，Ｍ）について、Ｃｊ，８は、暗号化鍵ｐｋによる
（Σｉ＝０〜ｎ−１ａｊ，ｉ２）＋（Σｉ＝０〜ｎ−１ｂｉ２）−２×ｆＡ，ｊ×ｆＢ
・・・(式１０９)
の暗号文である。
【０４４２】
各ｊ（ｊ＝１，…，Ｍ）について、計算した暗号文
Ｃｊ，８＝（ｃｊ，８，０，ｃｊ，８，１，ｃｊ，８，２）      ・・・(式１１０)
を「クエリ」と呼ぶ。
【０４４３】
なお、前述の通り、各ｊ（ｊ＝１，…，Ｍ）について、ｆＡ，ｊ×ｆＢの定数項は登録ベクトルＡｊと認証ベクトルＢとの内積＜Ａｊ，Ｂ＞＝Σｉ＝０〜ｎ−１ａｊ，ｉ×ｂｉと等しい。
【０４４４】
したがって、各ｊ（ｊ＝１，…，Ｍ）について、Ｃｊ，８は登録ベクトルＡｊと認証ベクトルＢとのユークリッド距離ｄＥ（Ａｊ，Ｂ）を定数項に持つ多項式の暗号文である。
【０４４５】
次に、照合補助装置２４０における検証データ生成部２４６は、各ｊ（ｊ＝１，…，Ｍ）について、
・ステップＦ１１で受け取ったＭ個の登録データのうち、ｊ番目の登録データに含まれる第二テンプレートを用いて、ステップＦ２０で生成したクエリＣｊ，８＝（ｃｊ，８，０，ｃｊ，８，１，ｃｊ，８，２）と、
・ステップＦ１１で受け取ったＭ個の登録データのうち、ｊ番目の登録データに含まれる登録識別子ｉｄｊと、を、
ｊ番目の検証データ（Ｃｊ，８，ｉｄｊ）とする（ステップＦ２１）。
【０４４６】
次に、照合補助装置２４０は、Ｍ個の検証データを検証装置２５０に送付する（ステップＦ２２）。
【０４４７】
次に、検証装置２５０は、照合補助装置２４０からＭ個の検証データを受け取る（ステップＦ２３）。
【０４４８】
検証装置２５０におけるクエリ検証部２５３は、各ｊ（ｊ＝１，…，Ｍ）について、
・ステップＦ２３で受け取ったＭ個の検証データのうち、ｊ番目の検証データ（Ｃｊ，８，ｉｄｊ）に含まれるクエリＣｊ，８＝（ｃｊ，８，０，ｃｊ，８，１，ｃｊ，８，２）と、
・秘密鍵（復号鍵）ｓｋ＝（λ，ｐ０，ｐ１，ｓ）と、に基づき、
Ｄｊ，１＝ｃｊ，８，０＋ｃｊ，８，１×ｓ＋ｃｊ，８，２×ｓ２      ・・・(式１１１)
を計算する。
【０４４９】
次に、各ｊ（ｊ＝１，…，Ｍ）について、Ｄｊ，１をｑで割った余りを、Ｄｊ，２とする。
【０４５０】
次に、各ｊ（ｊ＝１，…，Ｍ）について、Ｄｊ，２がｑ／２以上であればＤｊ，３＝Ｄｊ，２−ｑとする。Ｄｊ，２がｑ／２より小さければＤｊ，３＝Ｄｊ，２とする。これは、Ｄのｑを法とした［−ｑ／２，ｑ／２）への剰余演算である。
【０４５１】
次に、各ｊ（ｊ＝１，…，Ｍ）について、Ｄｊ，３をｔで割った余りの多項式をＤｊ，４とする。Ｄｊ，４の定数項を、Ｄｊ，５とする（ステップＦ２４）。各ｊ（ｊ＝１，…，Ｍ）について、Ｄｊ，５を「検証結果」と呼ぶ。
【０４５２】
前述の通り、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の検証データのうちｊ番目の検証データから生成されたＤ５は、登録ベクトルＡｊと認証ベクトルＢとのユークリッド距離ｄＥ（Ａｊ，Ｂ）である。
【０４５３】
次に、検証装置２５０における照合結果生成部２５４は、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の検証データのうち、
・ｊ番目の検証データに含まれるクエリに基づき、ステップＦ２４で生成した検証結果Ｄｊ，５と、
・ｊ番目の検証データに含まれる登録識別子ｉｄｊと、をまとめ、ｊ番目の照合結果（Ｄｊ，５，ｉｄｊ）とする。あるいは、検証装置２５０における照合結果生成部２５４は、各ｊ（ｊ＝１，…，Ｍ）について、Ｍ個の検証データのうち、
・ｊ番目の検証データに含まれるクエリからステップＦ２４で生成した検証結果ｉｄｊと、あらかじめ定められた閾値との大小を比較した結果ｄｊと、
・ｊ番目の検証データに含まれる登録識別子ｉｄｊと、をまとめ、ｊ番目の照合結果（ｄｊ，ｉｄｊ）としてもよい（ステップＦ２５）。
【０４５４】
検証装置２５０は、算出したＭ個の照合結果を出力する（ステップＦ２６）。
【０４５５】
なお、第４の例示的な実施形態に係る暗号文照合システム２００が認証フェーズにて実行する処理は、図８に例示された様態に限定されない。例えば、ステップＦ５に先だってステップＦ９からステップＦ１３が実行されてもよい。
【０４５６】
第４の例示的な実施形態に係る暗号文照合システム２００の上記の説明において、登録要求装置２１０における第一テンプレート生成部２１２がステップＢ２において生成する多項式ｆＡは、登録ベクトルＡに基づき上記式２０に従って生成される多項式であるとし、認証要求装置１３０における第一レスポンス生成部２３３がステップＣ１６において生成する多項式ｆＢは、認証ベクトルに基づき上記式２１に従って生成される多項式であるとした。
【０４５７】
第４の例示的な実施形態における二つの多項式の生成方法は、上記の方法に限らない。例えば、登録要求装置２１０における第一テンプレート生成部２１２がステップＢ２において生成する多項式ｆＡを、登録ベクトルＡに基づき上記式２１に従って生成される多項式とし、認証要求装置２３０における第一レスポンス生成部２３３がステップＦ１６において生成する多項式ｆＢを、認証ベクトルに基づき上記式２０に従って生成される多項式としてもよい。
［効果の説明］
【０４５８】
次に、第４の例示的な実施形態に係る暗号文照合システム２００に関する効果について説明する。
【０４５９】
第４の例示的な実施形態に係る暗号文照合システム２００によれば、認証を要求するユーザが、自身の識別子を提示せず、登録された全ての情報と、認証に用いられる情報の照合を行う、１：Ｎ認証を安全に実現することが可能である。すなわち、次の２つの効果を有する。
【０４６０】
第４の例示的な実施形態に係る暗号文照合システム２００によれば、登録要求装置２１０が抽出した登録ベクトルは、登録要求装置２１０上で暗号化され、記憶装置２２０に送られる。また、認証要求装置２３０が抽出した認証ベクトルは、認証要求装置２３０上で暗号化され、照合補助装置２４０に送られる。これらの暗号文を復号できるのは、復号鍵を持つ検証装置２５０であるが、検証装置２５０の受け取るデータは登録ベクトルと認証ベクトルの間のユークリッド距離の暗号文であり、登録ベクトルや認証ベクトルの値を開示しない。
【０４６１】
したがって、第４の例示的な実施形態に係る暗号文照合システム２００によれば、それぞれのベクトルを抽出する装置以外の装置に登録ベクトルと認証ベクトルの距離以外の値を漏洩せず、登録ベクトルと認証ベクトルの間の距離を算出することが可能である。
【０４６２】
また、第４の例示的な実施形態に係る暗号文照合システム２００によれば、同じ登録ベクトルとの認証を行う際であっても、ステップＣ５で選ばれた乱数を用いた処理が行われる。したがって、照合処理の通信内容が漏洩したとしても、漏洩した内容を再送したり、漏洩した内容を利用して作成したデータを送付したりすることによって、漏洩した照合時の距離と等しい距離を算出させたり、小さい値を算出させたりすることができない。
【０４６３】
特に、第４の例示的な実施形態に係る暗号文照合システム２００を、距離が閾値より小さいときに「受理」とする認証に利用する場合、登録ベクトルを知らない攻撃者が「受理」とされない性質、すなわちなりすまし攻撃への耐性を有する。
【０４６４】
さらに、第４の例示的な実施形態に係る暗号文照合システム２００は、高速な処理が可能な暗号方式である非特許文献１に記載された暗号方式を用いて構成される。そのため、高速な照合処理が可能である。
【０４６５】
さらに、第４の例示的な実施形態に係る暗号文照合システム２００では、復号鍵を持つ検証装置２５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しないように変形可能である。例えば、非特許文献４に記載された方式と同じ方法を適用することにより、復号鍵を持つ検証装置２５０が、登録ベクトルと認証ベクトルの間のユークリッド距離を算出できない方式に変形できる。復号鍵を持つ検証装置２５０に対して、登録ベクトルと認証ベクトルの間のユークリッド距離を開示しない方式は、特別な状況下においても復号鍵を持つ検証装置２５０が登録ベクトルの値を算出することを防ぐことができる。このため、より高い安全性を達成できる。
【０４６６】
特に制限されるものではないが、本発明の適用例として、例えば、特徴量として多値ベクトルを用いる生体認証が挙げられる。
【０４６７】
例えば登録フェーズにおける入力データと、照合フェーズにおける入力データを、指紋や静脈などから取得した生体情報から得られた生体情報（特徴ベクトル）とする。この場合、本発明を適用することで、生体情報を秘匿したまま、記憶装置に格納された暗号化された生体データと、照合要求装置から創出された暗号化された生体データが同一人物から採取されたものであるか否かを、２つの生体情報の間の距離が閾値以下となるかどうかにより判定することが可能となる。
【０４６８】
特に、生体情報は、常に安定して同一のデータが取得できるわけではないことが知られており、同じ人物から取得されるデータが類似している（各要素の距離が小さいデータが取得できる）と仮定することができる。このため、本発明は、生体認証等への活用に有用である。
【０４６９】
なお、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０４７０】
１００、２００  暗号文照合システム
１１０、２１０  登録要求装置
１１１、２１１  登録情報抽出部
１１２、２１２  第一テンプレート生成部
１１３、２１３  第二テンプレート生成部
１１４、２１４  テンプレート生成部
１２０、２２０  記憶装置
１２１、２２１  識別子付与部
１２２、２２２  登録データ生成部
１２３、２２３  登録データ記憶部
１２４  登録データ検索部
１３０、２３０  認証要求装置
１３１、２３１  認証要求生成部
１３２、２３２  認証情報抽出部
１３３、２３３  第一レスポンス生成部
１３４、２３４  第二レスポンス生成部
１３５、２３５  レスポンス生成部
１４０、２４０  照合補助装置
１４１、２４１  チャレンジ補助生成部
１４２、２４２  チャレンジ生成部
１４３、２４３  登録データ要求生成部
１４４、２４４  暗号化内積計算部
１４５、２４５  クエリ生成部
１５０、２５０  検証装置
１５１、２５１  鍵生成部
１５２、２５２  復号鍵記憶部
１５３、２５３  クエリ検証部
１５４、２５４  照合結果生成部
２４６  検証データ生成部
【図１】
2017170780.tif 000004
【図２】
2017170780.tif 000005
【図３】
2017170780.tif 000006
【図４】
2017170780.tif 000007
【図５】
2017170780.tif 000008
【図６】
2017170780.tif 000009
【図７】
2017170780.tif 000010
【図８】
2017170780.tif 000011
【国際調査報告】
2017170780.tif 000012
2017170780.tif 000013
2017170780.tif 000014
2017170780.tif 000015