(57)【要約】      （修正有）【課題】登録データに関する情報漏洩を回避し照合処理を行う対象を削減する照合システムと方法とプログラムを提供する。【解決手段】登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成する第１のステップＳ１と、これらを記憶装置に登録し、照合対象の平文データを暗号化した暗号化照合データを生成する第２のステップＳ２と、前記照合対象の平文データの部分に対応する部分照合データを生成し、前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３のステップＳ３を含む。【選択図】図１４
2018042045.tif 000002
【特許請求の範囲】
【請求項１】
登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、記憶装置に登録する第１の手段と、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２の手段と、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３の手段と、
を含む、ことを特徴とする照合システム。
【請求項２】
前記第１の手段は、
前記登録対象の平文データ及び平文の部分登録データを、鍵生成装置で生成された準同型暗号の公開鍵でそれぞれ暗号化し、前記暗号化登録データと暗号化部分登録データを生成する登録データ生成装置と、
前記暗号化登録データと前記暗号化部分登録データを前記記憶装置に登録する登録装置と、
を備え、
前記第２の手段は、
前記照合対象の平文データと平文の部分照合データを前記準同型暗号の公開鍵でそれぞれ暗号化し、前記暗号化照合データと暗号化部分照合データを生成する照合要求装置を備え、
前記第３の手段は、
前記暗号化部分照合データと前記暗号化部分登録データを暗号化したまま距離を計算する照合装置と、
前記照合装置から、前記暗号化された距離を受け、前記鍵生成装置で生成された準同型暗号の秘密鍵を用いて前記距離を復号し、前記距離が予め定められた値以下であるか否かを判定する照合補助装置と、
を備え、
前記照合装置は、
前記部分照合データと前記部分登録データとの間の距離が予め定められた第１の値以下である場合、前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算し、
前記照合補助装置は、前記照合装置から、前記暗号化された距離を受け、前記準同型暗号の秘密鍵を用いて、前記距離を復号し、前記距離が予め定められた第２の値以下であるか否かを判定する、ことを特徴とする請求項１に記載の照合システム。
【請求項３】
前記第１の手段は、
前記登録対象の平文データを、鍵生成装置で生成された準同型暗号の公開鍵で暗号化し、前記暗号化登録データと平文の部分登録データを生成する登録データ生成装置と、
前記暗号化登録データと前記平文の部分登録データを前記記憶装置に登録する登録装置と、
を備え、
前記第２の手段は、
前記照合対象の平文データを前記準同型暗号の公開鍵で暗号化し、前記暗号化照合データを生成する照合要求装置を備え、
前記第３の手段は、
平文の部分照合データと前記平文の部分登録データとの間の距離を計算する平文部分データ照合処理部を備え、
前記平文の部分照合データと平文の部分登録データとの間の距離が予め定められた第１の値以下である場合、前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算する照合装置と、
前記照合装置から、前記暗号化された距離を受け、前記鍵生成装置で生成された準同型暗号の秘密鍵を用いて、前記距離を復号し、前記距離が予め定められた第２の値以下であるか否かを判定する照合補助装置を備えた、ことを特徴とする請求項１に記載の照合システム。
【請求項４】
前記第１の手段と前記第２の手段のいずれか一方で、平文の部分登録データ又は平文の部分照合データを暗号化する、ことを特徴とする請求項１に記載の照合システム。
【請求項５】
登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、これらを記憶装置に登録する第１のステップと、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２のステップと、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３のステップと、
を含む、ことを特徴とする照合方法。
【請求項６】
前記第１のステップでは、
前記登録対象の平文データ及び平文の部分登録データを準同型暗号の公開鍵でそれぞれ暗号化して、前記暗号化登録データと暗号化部分登録データを生成して前記記憶装置に登録し、
前記第２のステップでは、
前記照合対象の平文データと平文の部分照合データを前記準同型暗号の公開鍵でそれぞれ暗号化して前記暗号化照合データ及び暗号化部分照合データを生成し、
前記第３のステップでは、
前記暗号化部分照合データと前記暗号化部分登録データを暗号化したまま距離を計算して照合を依頼し、
前記部分照合データと前記部分登録データとの間の距離が予め定められた第１の値以下である場合、
前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算して照合を依頼し、
前記暗号化照合データと前記暗号化登録データの照合を行う、ことを特徴とする請求項５に記載の照合方法。
【請求項７】
前記第３のステップでは、
前記照合の依頼に対して、前記暗号化部分照合データと前記暗号化部分登録データとの間の距離を、準同型暗号の秘密鍵を用いて復号し、前記部分照合データと前記部分登録データとの間の距離が予め定められた前記第１の値以下であるか否か判定し、
前記部分照合データと前記部分登録データの前記距離が予め定められた前記第１の値以下である場合、
前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算して照合を依頼し、
前記照合の依頼に対して、前記暗号化照合データと前記暗号化登録データとの間の距離を前記準同型暗号の前記秘密鍵を用いて復号し、
前記復号された照合データと登録データとの間の距離が予め定められた第２の値以下であるか否か判定することで照合を行う、ことを特徴とする請求項６に記載の照合方法。
【請求項８】
前記第１のステップでは、
前記登録対象の平文データを準同型暗号の公開鍵で暗号化して前記暗号化登録データを生成し、前記暗号化登録データと、平文の部分登録データを前記記憶装置に登録し、
前記第２のステップでは、
前記照合対象の平文データを準同型暗号の公開鍵で暗号化して前記暗号化照合データを生成し、
前記第３のステップでは、
平文の部分照合データと前記平文の部分登録データとの間の距離が予め定められた第１の値以下である場合、
前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算して照合を依頼し、
前記暗号化照合データと前記暗号化登録データとの間の距離を、前記準同型暗号の前記秘密鍵を用いて復号し、照合データと登録データとの間の距離が予め定められた第２の値以下であるか否か判定することで照合処理を行う、ことを特徴とする請求項５に記載の照合方法。
【請求項９】
前記第１のステップと前記第２のステップのいずれか一方で、平文の部分登録データ又は平文の部分照合データを暗号化する、ことを特徴とする請求項５に記載の照合方法。
【請求項１０】
登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、記憶装置に登録する第１の処理と、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２の処理と、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３の処理と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、照合システムと方法とプログラムに関する。
【背景技術】
【０００２】
近年、クラウドの普及に伴い、ネットワークに接続された計算資源に利用者のデータを置き、そのデータに基づいたサービスが急速に広がってきている。このようなサービスでは、利用者の機微なデータを扱う機会も増大してきているため、利用者が自分のデータが安全に管理されていることを保証することが重要になってきている。このような状況の下、オープンなネットワーク環境でデータを暗号化したまま管理し、データを復号することなく、検索や、統計処理などを行う技術の研究開発が活発に行われている。
【０００３】
また、近年、従来のパスワードや磁気カードを用いた個人認証の脆弱性をついた犯罪が頻発しており、より安全性の高い指紋、静脈などの生体的な特徴に基づく生体認証技術が注目を集めている。
【０００４】
生体認証においては、認証情報の検証を行うために、生体情報に関するテンプレートをデータベースに保管する必要がある。指紋、静脈等の生体情報は基本的に生涯不変のデータであり、情報が漏洩するとその被害は甚大なものとなる最も機密性が要求される情報である。このため、テンプレートが漏洩しても「なりすまし」を行えないようにするために、テンプレート情報を秘匿したまま認証を行うテンプレート保護型の生体認証技術が重要となってきている。
【０００５】
特許文献１には、第１のノード（クライアントに相当する）が、公開鍵と秘密鍵を生成する第２のノード（認証ノードに相当する）から受信した公開鍵により認証データを暗号化して第３のノード（サーバに相当）に送信し、被認証データを受信すると認証データを第３のノードより取得し被認証データと認証データの距離を公開鍵により暗号化したまま算出し、第３のノードから取得した多項式に前記距離を代入して公開鍵に暗号化した値を、照合用データとして生成して第２のノードに送信する方法が開示されている。多項式は認証データと被認証データの距離の閾値をパラメータとして含む。特許文献１では、信頼できる第３者をシステムに導入することにより、認証データと被認証データをサーバに対して秘匿可能としている。しかしながら、この関連技術は、照合における第３者の負荷が大きい。
【０００６】
特許文献２には、第１のノードが認証データとの距離を評価する評価式を生成し、公開鍵と秘密鍵を生成する第２のノードから受信した公開鍵により評価式の係数を暗号化して第３のノードに送信し、被認証データを受信すると、暗号化された前記係数を第３のノードより取得し、被認証データと暗号化された前記係数に基づいて、前記被認証データを認証データと照合するための評価値を生成し、該評価値を第２のノードに送信する方法が開示されている。
【０００７】
特許文献３には、暗号化ランダム類似度算出部（類似度途中暗号文算出部）は、復号装置の公開鍵を使って暗号化された暗号化特徴ベクトル（比較暗号文）と、復号装置の公開鍵を使って暗号化された暗号化特徴ベクトル（対象暗号文）と、乱数生成部（一時鍵生成部）が生成した乱数（一時鍵）とに基づいて、２つの暗号化特徴ベクトルＣ、Ｃ’が暗号化されたままの状態で、類似度算出の第一段階の計算をし、第二チャレンジＣ＾を算出する。復号装置は、復号装置の秘密鍵で第二チャレンジＣ＾を復号し、復号した結果が一時鍵で暗号化されたままの状態で、類似度算出の第二段階の計算をして、第二レスポンスＺを算出する。平文類似度抽出部（類似度算出部）は、一時鍵で第二レスポンスＺを復号することにより、類似度を算出する構成が開示されている。
【０００８】
特許文献４には、暗号化した預託データなどをデータベースサーバに送信するデータ登録用の送受信装置として機能する登録クライアント、秘匿化した検索クエリをデータベースサーバに送信して検索結果を受信する検索用の送受信装置として機能する検索クライアント、暗号化した預託データなどをデータベースに登録し、かつデータベース内のデータを検索する秘匿検索装置として機能するデータベースサーバを備えた構成が開示されている。特許文献４では、データベースサーバに預託するデータを記憶装置から読み出し、検索可能暗号特有のアルゴリズムで預託データの内容から秘匿化インデックスを生成し、生成した秘匿化インデックスを登録部に通知し、またはメモリもしくは記憶装置に一時的に出力する。データベースサーバは、秘匿検索処理において、まず、各クラスタにおいて秘匿化インデックスの代表（ピボット）を選択し、このピボットと、検索クライアントで検索クエリに含まれる検索キーワードを秘匿化したトラップドアとの照合を行なうことにより、登録データ照合時のクラスタの優先順位を決定する。データベースサーバは、優先順位に基づいて、クラスタ単位に全登録データの照合を行い、検索結果を検索クライアントに出力する。
【０００９】
特許文献５には、生体認証に用いられる参照情報を登録するとき、登録センサは正規ユーザの生体の一部の特徴量を抽出して特徴量をベクトル化し、ベクトル化された特徴量を準同型暗号化し、さらに、登録センサは準同型暗号化された特徴量を計算サーバに送信し、計算サーバのデータベースに暗号登録データとして登録しておく。ユーザが正規ユーザであるかを認証するために、照合センサはユーザの生体の一部の特徴量を抽出してベクトル化し、ベクトル化された特徴量を準同型暗号化し、準同型暗号化された特徴量を計算サーバに送信する。計算サーバでは、受け取った準同型暗号化された特徴量と登録されている暗号登録データの間の秘匿距離を計算し、秘匿距離計算結果を得、準同型暗号の秘密鍵を持つ認証局に送信する。認証局は、送信された秘匿距離計算結果を復号し、復号結果と閾値を比較し、復号結果が閾値よりも小さい場合は、ユーザを認証する。秘匿距離としてハミング距離を用いる。特許文献５の開示は、完全一致検索に係る発明である。
【００１０】
上記以外に下記の非特許文献等も参照される。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】国際公開第２０１４／１８５４５０号
【特許文献２】国際公開第２０１４／１８５４４７号
【特許文献３】国際公開第２０１２／１１４４５２号
【特許文献４】国際公開第２０１３／０８０３６５号
【特許文献５】特開２０１４−１２６８６５号公報
【００１２】
【非特許文献１】“テンプレートサイズの小さい秘匿指紋認証方式”，肥後，一色，森，尾花，暗号と情報セキュリティシンポジウム（ＳＣＩＳ２０１５），２０１５．
【００１３】
【非特許文献２】“Privacy-Preserving Fingerprint Authentication Resistant to Hill-Climbing Attacks”,Haruna Higo, Toshiyuki Isshiki, Kengo Mori, Satoshi Obana, SAC2015, 2015.
【非特許文献３】“認証時の情報開示の少ない秘匿生体認証方式”，肥後，一色，森，尾花，暗号と情報セキュリティシンポジウム（ＳＣＩＳ２０１６），２０１６．
【発明の概要】
【発明が解決しようとする課題】
【００１４】
特許文献２、非特許文献１、特許文献３には、信頼できる第３者を導入したシステムにおいて、照合における第３者の負荷を小さくした技術が開示されている。しかしながら、これらの方式は、計算コストが大きいため、１：１認証のみに対応し、１：Ｎ認証に適していない。１：１認証は、被認証者が、自分は誰（被認証者）であると主張し、検証者が、被認証者は、該被認証者が主張した人物であることを検証する認証である。１：Ｎ認証は、被認証者が、自分（被認証者）がある集合（組織）に所属していると主張し、検証者が、被認証者は、被認証者が主張した集合に属することを検証する認証である。
【００１５】
１：１認証を、集合に登録されている人物のそれぞれとＮ回実行することにより、１：Ｎ認証を構成できることが一般に知られている。
【００１６】
しかしながら、上記した特許文献２、非特許文献１、特許文献３に記載の方式は、１回の１：１認証に必要な計算コストが大きいため、１：Ｎ認証のＮが大きい場合には、非現実的となる。
【００１７】
そのため、１：Ｎ認証において、１：１認証１回当たりの計算コストが小さい方式、および、照合対象のＮを減らす方式が望まれている。
【００１８】
一般に、生体情報を秘匿しない生体認証では、１：Ｎ認証を行う場合、生体から得られる特徴量による大まかな分類（例えば、指紋の紋章による分類）を利用したグループ分けや、生体情報の一部を利用した簡易検証を行うことによって、照合候補の枝刈りを行うことにより、効率化を行っている。
【００１９】
しかしながら、生体情報を秘匿したまま照合を行う場合、被認証者から送られてくる生体情報は、暗号化等により、秘匿されている。このため、特徴量による大まかな分類や生体情報の一部を利用した簡易検証を行うことはできない。
【００２０】
暗号化されたデータの曖昧さを許容する暗号文照合システムでは、
データを秘匿しつつ、
照合対象の暗号文の数を削減することを、同時に満たすことはできない、という課題がある。
【００２１】
本発明は、上記課題を解決するために創案されたものであって、その目的は、登録データに関する情報漏洩を回避し照合処理を行う対象を削減することができるシステム、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２２】
本発明の一つの側面によれば、登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、記憶装置に登録する第１の手段と、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２の手段と、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して、前記暗号化照合データとの照合を行う第３の手段と、を含む照合システムが提供される。
【００２３】
本発明の一つの側面によれば、登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、これらを記憶装置に登録する第１のステップと、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２のステップと、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３のステップとを含む照合方法が提供される。
【００２４】
本発明の一つの側面によれば、登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、記憶装置に登録する第１の処理と、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２の処理と、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して前記暗号化照合データとの照合を行う第３の処理と、をコンピュータに実行させるプログラムが提供される。本発明によれば、上記プログラムを記憶したコンピュータ読み出し可能な記録媒体（例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、又は、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）等の半導体ストレージ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）等のｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｒｅｃｏｒｄｉｎｇ  ｍｅｄｉｕｍ）が提供される。
【発明の効果】
【００２５】
本発明によれば、登録データに関する情報漏洩を回避し照合処理を行う対象を削減することができる。
【図面の簡単な説明】
【００２６】
【図１】本発明の一実施形態のシステム全体の構成を例示する図である。
【図２】（Ａ）と（Ｂ）は本発明の一実施形態の登録データ生成装置と登録装置の構成を例示する図である。
【図３】（Ａ）と（Ｂ）は本発明の一実施形態の記憶装置と鍵生成装置の構成を例示する図である。
【図４】（Ａ）と（Ｂ）は本発明の一実施形態の照合要求装置と照合装置の構成を例示する図である。
【図５】本発明の一実施形態の照合補助装置の構成を例示する図である。
【図６】本発明の一実施形態の動作を説明する図である。
【図７】本発明の一実施形態の動作を説明する図である。
【図８】本発明の一実施形態の動作を説明する図である。
【図９】本発明の一実施形態の動作を説明する図である。
【図１０】本発明の一実施形態の動作を説明する図である。
【図１１】本発明の一実施形態の動作を説明する図である。
【図１２】（Ａ）と（Ｂ）は本発明の一実施形態の変形例の登録データ生成装置と照合要求装置の構成を例示する図である。
【図１３】（Ａ）と（Ｂ）は本発明の一実施形態の変形例の照合装置と照合補助装置の構成を例示する図である。
【図１４】本発明の一形態を例示する図である。
【図１５】本発明の別の形態を例示する図である。
【発明を実施するための形態】
【００２７】
本発明の実施形態について説明する。図１４は、本発明の一形態を例示する図である。図１４には、本発明の一形態の動作原理が例示されている。図１４を参照すると、登録対象の平文データを暗号化した暗号化登録データを生成し、前記登録対象の平文データの部分に対応する部分登録データを生成し、記憶装置に登録する第１のステップ（Ｓ１）と、
照合対象の平文データを暗号化した暗号化照合データを生成し、前記照合対象の平文データの部分に対応する部分照合データを生成する第２のステップ（Ｓ２）と、
前記部分照合データとの間の距離が予め定められた値以下である前記部分登録データに対応する前記暗号化登録データに対して暗号化照合データとの照合を行う第３のステップ（Ｓ３）と、を有する。
【００２８】
本発明の一形態によれば、前記第１のステップ（Ｓ１）では、
前記登録対象の平文データ及び平文の部分登録データを準同型暗号の公開鍵でそれぞれ暗号化して、暗号化登録データと暗号化部分登録データを生成して記憶装置に登録するようにしてもよい。
【００２９】
前記第２のステップ（Ｓ２）では、照合対象の平文データと平文の部分照合データを準同型暗号の公開鍵で暗号化し、暗号化照合データ及び暗号化部分照合データを生成するようにしてもよい。
【００３０】
前記第３のステップ（Ｓ３）において、以下のステップを含むようにしてもよい。
暗号化部分照合データと暗号化部分登録データを暗号化したままま部分照合データと部分登録データ間の距離を計算して照合（照合補助）処理を依頼する。
照合（照合補助）処理では、前記距離を準同型暗号の秘密鍵で復号する。
照合（照合補助）処理の結果、部分照合データと部分登録データとの間の距離が予め定められた第１の値（t’）以下である場合（簡易照合が受理の場合）、前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算して照合（照合補助）処理を依頼する。
照合（補助）処理では、準同型暗号の秘密鍵で前記距離を復号し、照合データと登録データの照合を行う。
【００３１】
本発明の一形態によれば、前記第３のステップ（Ｓ３）において、以下のステップを含むようにしてもよい。
照合（照合補助）処理では、前記暗号化部分照合データと前記暗号化部分登録データとの間の距離を受け、前記距離を準同型暗号の秘密鍵を用いて復号する。
前記復号された部分照合データと部分登録データとの間の距離が予め定められた前記第１の値(t')以下であるか否か判定する。
前記部分照合データと前記部分登録データの前記距離が予め定められた前記第１の値以下である場合、前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算して照合（照合補助）処理を依頼する。
照合（照合補助）処理では、前記暗号化照合データと前記暗号化登録データとの間の前記距離を、前記準同型暗号の前記秘密鍵を用いて復号する。
復号された照合データと登録データとの間の距離が予め定められた第２の値（t）以下であるか否か判定することで照合処理を行う。
【００３２】
本発明の別の形態によれば、第１のステップ（Ｓ１）では、前記登録対象の平文データを準同型暗号の公開鍵で暗号化し、前記暗号化登録データを生成するようにしてもよい。
前記第２のステップ（Ｓ２）では、前記照合対象の平文データを準同型暗号の公開鍵で暗号化し、及び前記暗号化照合データを生成するようにしてもよい。
前記第３のステップ（Ｓ３）では、平文の部分照合データと平文の部分登録データとの間の距離を計算するステップと、
部分照合データと部分登録データとの間の距離が予め定められた第１の値（t’）以下である場合、前記暗号化照合データと前記暗号化登録データを暗号化したまま距離を計算するステップと、
前記暗号化照合データと前記暗号化登録データとの間の距離を、前記準同型暗号の前記秘密鍵を用いて復号し、
前記照合データと前記登録データとの間の距離が予め定められた第２の値（t）以下であるか否か判定することで照合処理を行うステップを含むようにしてもよい。
【００３３】
本発明の別の形態によれば、第１のステップ又は第２のステップのいずれかで部分データ（部分登録データ又は部分照合データ）を暗号化するようにしてもよい。
【００３４】
図１５は、図１４を参照して動作原理を説明した一形態の方法を、コンピュータで実現する形態を例示した図である。図１５を参照すると、コンピュータ装置１は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２、記憶装置（メモリ）３、入出力（Ｉｎｐｕｔ・Ｏｕｔｐｕｔ：Ｉ／Ｏ）インタフェース４、通信インタフェース５を備える。記憶装置３は、ハードディスクドライブ（ＨＤＤ）、半導体メモリ（例えば、ソリッドステートドライブ（ＳＳＤ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、読み出し専用のリードオンリメモリ（ＲＯＭ）、電気的に消去およびプログラム可能なリードオンリメモリ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、コンパクトディスク（ＣＤ）、デジタルバーサタイルディスク（ＤＶＤ））等のいずれか、または複数の組み合わせで構成してもよい。記憶装置３は、ＣＰＵ２で実行されるプログラムを格納する。ＣＰＵ２は、記憶装置３に格納されたプログラムを実行することで、図１４のステップの処理を実行する。コンピュータ装置１は、通信インタフェース５を介して、例えばネットワーク（ローカルエリアネットワーク又は広域ネットワーク）等に接続し、不図示の他のコンピュータ装置と通信するようにしてもよい。
【００３５】
なお、図１４の各ステップＳ１〜Ｓ３（ないし、そのサブステップ）は、ネットワークを介して通信接続する複数のコンピュータ装置１で連携して実現するようにしてもよい。コンピュータ装置１は、Ｉ／Ｏインタフェース４を介して例えば指紋センサや静脈センサ等のセンサ６（オプション）に接続し、登録対象、又は、照合対象の指紋や静脈等の生体情報（デジタルデータ）を取得するようにしてもよい。図１５のコンピュータ装置１が、登録装置を構成する場合、記憶装置３には、暗号化された登録データや部分登録データを記憶するようにしてもよい。
【００３６】
本発明によれば、登録時に、データの暗号文とデータの一部の暗号文を対にして登録し、照合時に、データの一部と照合したいデータの一部の暗号文を用いて、照合対象のデータの一部と、一部に近い登録データに対して照合を行うことにより、効率的な１：Ｎ暗号文照合システムを実現する。暗号化されたデータの曖昧さを許容する照合システムに適用して好適とされ、特に、照合対象のデータと照合を行うためのデータがともに暗号化されている状況で、曖昧さの指標を、平文の距離とした場合の照合システムに適用される。
【００３７】
本発明によれば、データ登録時に、該データの暗号文を登録し、照合時には、暗号化されたまま登録されている平文データと、照合対象の平文データとの間の距離が、許容される範囲に入っていることを検証することが可能とされる。また、登録データと照合対象データの一部を照合することによって、照合対象データ数を削減することができる。登録されたデータ（暗号化登録データ、暗号化部分登録データ）は、常に暗号化されており、データに関する情報の漏洩が回避される。このため、安心、かつ安全に、システムを利用することが可能となる。このため、効率的な１：Ｎ暗号文照合システムの利用が可能となる。以下、いくつかの例示的な実施形態について説明する。
【００３８】
＜例示的な実施形態１＞
本発明の例示的な一実施の形態について図面を参照して詳細に説明する。図１を参照すると、一実施の形態に係るシステムは、データを暗号化した登録データを生成する登録データ生成装置１００と、登録データを受信し記憶装置３００に登録する登録装置２００と、鍵生成装置４００と、照合要求装置５００と、照合装置６００と、照合補助装置７００とを備えている。これらの装置は、プロセッサ（ＣＰＵ）、記憶装置（メモリ）、通信インタフェース（ＩＦ）等を備え、ネットワーク（構内網、広域網）を介して通信接続する複数のノード装置として構成してもよい。図２乃至図５を参照して、各装置について説明する。
【００３９】
図２（Ａ）を参照すると、登録データ生成装置１００は、登録データ生成部１０１と、部分登録データ生成部１０２と、部分登録データ暗号化部１０３と、登録データ暗号化部１０４と、登録データ送付部１０５と、通信インタフェース（ＩＦ）１０６を備えている。登録データ生成部１０１は、登録対象のデータ（「平文登録データ」とも称される）を生成する。部分登録データ生成部１０２は、登録データ生成部１０１から平文登録データを入力し、部分登録データを生成する。部分登録データ暗号化部１０３は、部分登録データ生成部１０２から部分登録データを入力し、鍵生成装置４００が生成した公開鍵を受信し、公開鍵を用いて部分登録データを暗号化し、暗号化部分登録データを生成する。登録データ暗号化部１０４は、登録データ生成部１０１から平文登録データを入力し、鍵生成装置４００から公開鍵を入力として受信し、公開鍵を用いて暗号化登録データを生成する。登録データ送付部１０５は、部分登録データ生成部１０２から暗号化部分登録データと、登録データ暗号化部１０４から暗号化登録データを入力として受信し、登録データを生成し、通信ＩＦ１０６を介して、登録装置２００に送付する。
【００４０】
図２（Ｂ）を参照すると、登録装置２００は、登録処理部２０１と登録データ受信部２０２と通信ＩＦ２０３を備えている。登録処理部２０１は、登録データ生成装置１００から、通信ＩＦ２０３および登録データ受信部２０２を介して受信した登録データを受け取り、登録データの登録処理を行う。
【００４１】
図３（Ａ）を参照すると、記憶装置３００は、暗号化部分データ記憶部３０１と、暗号化データ記憶部３０２と通信ＩＦ３０３とを備えている。記憶装置３００は、ハードディスクドライブ（ＨＤＤ）、ソリッドステートドライブ（ＳＳＤ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、又は、スタティクランダムアクセスメモリ（ＳＲＡＭ）、電気的にプログラム消去可能なリードオンリメモリ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ：  ＥＥＰＲＯＭ）等を備えた構成としてもよい。
【００４２】
図３（Ｂ）を参照すると、鍵生成装置４００は、鍵生成部４０１と通信ＩＦ４０２を備えている。鍵生成部４０１は、セキュリティパラメータを入力とし、公開鍵と秘密鍵を生成する。
【００４３】
図４（Ａ）を参照すると、照合要求装置５００は、照合データ生成部５０１と、部分照合データ生成部５０２と、部分照合データ暗号化部５０３と、照合データ暗号化部５０４と、照合クエリ送付部５０５と、通信ＩＦ５０６を備えている。照合データ生成部５０１は、照合対象の平文データ（「平文照合データ」と呼ぶ）を生成する。部分照合データ生成部５０２は、平文照合データを入力として、部分照合データを生成する。部分照合データ暗号化部５０３は、部分照合データと、鍵生成装置４００が生成した公開鍵を入力とし、暗号化部分照合データを生成する。照合データ暗号化部５０４は、平文照合データと、鍵生成装置４００が生成した公開鍵とを入力とし、暗号化平文照合データを生成する。照合クエリ送付部５０５は、暗号化照合データと、暗号化部分照合データを入力とし、照合クエリを生成し、通信ＩＦ５０６を介して照合装置６００へ送付する。
【００４４】
図４（Ｂ）を参照すると、照合装置６００は、暗号化部分距離生成部６０１と、部分データ照合補助依頼部６０２と、暗号化照合データ距離生成部６０３と、照合補助依頼部６０４と、照合処理部６０５と、照合クエリ受信部６０６と、通信ＩＦ６０７を備えている。暗号化部分距離生成部６０１は、記憶装置３００の暗号化部分データ記憶部３０１に記憶された暗号化部分登録データと、照合クエリに含まれる、暗号化部分照合データを入力として、暗号化部分距離を生成する。部分データ照合補助依頼部６０２は、暗号化部分距離を入力として、部分データ照合補助依頼を生成する。暗号化照合データ距離生成部６０３は、部分データ照合補助依頼に従って照合補助装置７００が生成した部分データ照合補助結果と、部分データ照合補助結果に対応し、記憶装置３００に記憶された暗号化登録データを入力とし、照合データと登録データとの間の距離の暗号文である暗号化距離を生成する。照合補助依頼部６０４は、暗号化距離を入力として、照合補助依頼を生成する。照合処理部６０５は、照合補助依頼に従って、照合補助装置７００が生成した照合補助結果を通信ＩＦ６０７を介して入力として、照合結果を生成する。
【００４５】
図５を参照すると、照合補助装置７００は、鍵記憶部７０１と、部分データ照合補助部７０２と、照合補助部７０３と、通信ＩＦ７０４を備えている。
【００４６】
鍵記憶部７０１は、鍵生成装置４００が生成した秘密鍵を通信ＩＦ７０４を介して受信し、記憶する。部分データ照合補助部７０２は、鍵記憶部７０１に記憶された秘密鍵と、照合装置６００から送付された部分データ照合補助依頼とを入力とし、部分データ照合補助結果を生成する。部分データ照合補助部７０２は、鍵記憶部７０１に記憶された秘密鍵と、照合装置６００から送付され通信ＩＦ７０４を介して受信した照合補助依頼を入力とし、照合補助結果を生成する。
【００４７】
次に、本実施形態の動作について説明する。本実施形態の暗号文照合システムの動作は、登録セットアップフェイズと、データ登録フェイズと、照合セットアップフェイズと、暗号文照合フェイズの４つのフェイズに大別される。
【００４８】
登録セットアップフェイズは、鍵生成装置４００にセキュリティパラメータを入力し、準同型暗号の公開鍵と秘密鍵を生成し、各装置に必要な鍵を送付するフェイズである。
【００４９】
照合セットアップフェイズは、鍵生成装置４００が登録セットアップフェイズで生成した公開鍵と秘密鍵を、各装置に送付するフェイズである。
【００５０】
データ登録フェイズは、登録データ生成装置１００が生成した平文の登録データと、平文の登録データの一部である平文の部分登録データ（「部分平文登録データ」とも称する）を暗号化し、記憶装置３００に登録するフェイズである。
【００５１】
暗号文照合フェイズは、照合要求装置５００が生成した平文の照合データを秘匿しながら、入力データが、記憶装置３００に記憶されている暗号データの平文と近い（ある種の距離が小さい）ものであるかを判定するフェイズである。以下、各フェイズにおける動作に関して詳細に説明する。
【００５２】
＜登録セットアップフェイズ＞
図６は、登録セットアップフェイズを例示する図である。鍵生成装置４００の鍵生成部４０１は、セキュリティパラメータｋを入力とし準同型暗号の公開鍵および秘密鍵を生成し（ステップＳ１０１）、通信ＩＦ４０２を介して、公開鍵を登録データ生成装置１００と登録装置２００に送付する（ステップＳ１０２、Ｓ１０３）。
【００５３】
平文ｍ１及びｍ２に対して、加算又は乗法に関する準同型暗号方式の暗号化関数ENC
に関して、
ENC(pk, m1)(+)ENC(pk, m2)=ENC(pk, m1+m2)  （加法準同型）又は、
ENC(pk, m1)(*)ENC(pk, m2)=ENC(pk, m1*m2)  （乗法準同型）
が成り立つ。ここで(+)や(*)は暗号方式によって定められる二項演算子である。なお、準同型暗号方式として、乗法に利用されるＲＳＡ（Rivest Shamir Adleman）暗号、加法に利用される加法Elgamal暗号等が知られている。
【００５４】
＜データ登録フェイズ＞
図７は、データ登録フェイズを例示する図である。
【００５５】
登録データ生成装置１００の登録データ生成部１０１が、平文登録データを生成する（ステップＳ２０１）。
【００５６】
次に、部分登録データ生成部１０２が、平文登録データから部分平文登録データを生成する（ステップＳ２０２）。
【００５７】
次に、部分登録データ暗号化部１０３が、部分平文登録データと、鍵生成装置４００が生成した公開鍵を入力とし、暗号化部分登録データを生成する（ステップＳ２０３）。
【００５８】
次に、登録データ暗号化部１０４が、平文登録データと、公開鍵を入力とし、暗号化登録データを生成する（ステップＳ２０４）。
【００５９】
次に、登録データ送付部１０５が、暗号化部分登録データと、暗号化登録データを入力とし、暗号化部分登録データと、暗号化登録データを含む登録データを生成する（ステップＳ２０５）。
【００６０】
登録データ送付部１０５は、通信ＩＦ１０６を介して登録データを登録装置２００へ送付する（ステップＳ２０６）。
【００６１】
登録装置２００の登録処理部２０１は、受信した登録データに含まれる暗号化部分登録データを、通信ＩＦ２０３を介して記憶装置３００の暗号化部分データ記憶部３０１に記憶し（ステップＳ２０７）、暗号化登録データを通信ＩＦ２０３を介して記憶装置３００の暗号化データ記憶部３０２にそれぞれ記憶する（ステップＳ２０９）。
【００６２】
＜照合セットアップフェイズ＞
図８は、照合セットアップフェイズを例示する図である。鍵生成装置４００は、登録セットアップフェイズで生成した準同型暗号の公開鍵を通信ＩＦ４０２を介して、照合要求装置５００、照合装置６００、照合補助装置７００に送信する（ステップＳ３０１〜Ｓ３０３）。また、鍵生成装置４００は、登録セットアップフェイズで生成した準同型暗号の秘密鍵を通信ＩＦ４０２を介して照合補助装置７００に送付する（ステップＳ３０４）。
【００６３】
照合補助装置７００は、通信ＩＦ７０４を介して受信した秘密鍵を鍵記憶部７０１に記憶する（ステップＳ３０５）。
【００６４】
＜暗号文照合フェイズ＞
図９は、暗号文照合フェイズを例示する図である。照合要求装置５００の照合データ生成部５０１が平文照合データを生成する（ステップＳ４０１）。
【００６５】
次に、部分照合データ生成部５０２が、照合データ生成部５０１で生成した平文照合データを入力として、部分照合データを生成する（ステップＳ４０２）。
【００６６】
次に、部分照合データ暗号化部５０３が、部分照合データ生成部５０２が生成した部分照合データと、鍵生成装置４００が生成した公開鍵を入力として、暗号化部分照合データを生成する（ステップＳ４０３）。
【００６７】
次に、照合データ暗号化部５０４が、照合データ生成部５０１で生成した平文照合データと公開鍵を入力として、暗号化照合データを生成する（ステップＳ４０４）。
【００６８】
次に、照合クエリ送付部５０５が、部分照合データ暗号化部５０３が生成した暗号化部分照合データと、照合データ暗号化部５０４が生成した暗号化照合データを入力として、暗号化部分照合データと、暗号化照合データを含む照合クエリを生成する（ステップＳ４０5）。
【００６９】
照合クエリ送付部５０５は、照合クエリを、通信ＩＦ５０６を介して照合装置６００へ送付する（ステップＳ４０６）。
【００７０】
次に、照合クエリを受信した照合装置６００の暗号化部分距離生成部６０１は、照合クエリに含まれる暗号化部分照合データと、記憶装置３００の暗号化部分データ記憶部３０１に記憶された暗号化部分登録データと、公開鍵を入力として、暗号化部分距離を生成する（ステップＳ４０７）。ここで、暗号化部分データ記憶部３０１に、複数のデータが記憶されている場合には、ステップＳ４０７を複数回行ってもよい。この場合、次の部分データ照合補助依頼部６０２への入力は、複数個の暗号化部分距離になる。
【００７１】
次に、照合装置６００の部分データ照合補助依頼部６０２は、暗号化部分距離を入力として、部分データ照合補助依頼を生成する（ステップＳ４０８）。
【００７２】
部分データ照合補助依頼部６０２は、部分データ照合補助依頼を、照合補助装置７００に送付する（ステップＳ４０９）。
【００７３】
部分データ照合補助依頼を受信した照合補助装置７００の部分データ照合補助部７０２は、部分データ照合補助依頼と、鍵記憶部７０１に記憶された秘密鍵を入力とし、部分データ照合補助結果を生成し（ステップＳ４１０）、通信ＩＦ７０４を介して照合装置６００に送付する（ステップＳ４１１）。
【００７４】
部分データ照合補助結果を受信した照合装置６００の暗号化照合データ距離生成部６０３は、部分データ照合補助結果によって定められた暗号化登録データを、記憶装置３００の暗号化データ記憶部３０２から受信し、照合クエリに含まれる暗号化照合データZと、暗号化登録データZ'と、公開鍵pkを入力とし、暗号化距離ENC(pk, d（Z,Z'))を生成する（ステップＳ４１２）。
【００７５】
次に、照合装置６００の照合補助依頼部６０４は、暗号化距離を入力とし、照合補助依頼を生成し（ステップＳ４１３）、照合補助装置７００に送付する（ステップＳ４１４）。
【００７６】
照合補助依頼を受信した照合補助装置７００の照合補助部７０３は、鍵記憶部７０１に記憶された秘密鍵と、照合補助依頼を入力とし、照合補助結果を生成し（ステップＳ４１５）、照合装置６００に送付する（ステップＳ４１６）。
【００７７】
照合補助結果を受信した照合装置６００の照合処理部６０５は、照合結果を生成し（ステップＳ４１７）出力する（ステップＳ４１８）
【００７８】
＜実施例１＞
次に、上記した例示的な実施形態についてより詳細な実施例に即して説明する。本実施例は、距離として、二乗n次元ユークリッド距離を扱う場合の実施例である。すなわち、
２つのn次元ベクトル 
X=(x[1], x[2], …, x[n])と、
Y=(y[1], y[2], …, y[n]
)に対して、
XとYとの間の距離d(X, Y)を、
d(X,Y)=[(x[1]-y[1])^{2}+(x[2]-y[2])^{2}+…+(x[n]-y[n])^{2}]
と定義する。この二乗n次元ユークリッド距離は、距離を定義する条件式（１．（非負性）：d(X,Y)>=0, X=Y ⇒ d(X,Y)=0, ２．（対称性）：d(X,Y)=d(Y,X), ３．（三角不等式）：d(X,Y)+d(Y,Z)>=d(X,Y)）のうち三角不等式を満たさないが、本実施例で用いるようなマッチ判定には利用できることが知られている。
【００７９】
d(X,Y)が閾値t以下である場合に、XとYは、近いと判定し、閾値tよりも大きい場合には、XとYは遠いと判定するものとする。本実施例では、XとYが近い場合は、マッチしたと判定し（照合受理）、遠い場合には、マッチしなかったと判定する（照合不受理）。
【００８０】
特に制限されるものではないが、本実施例では、Somewhat凖同型暗号を利用する。Somewhat 準同型暗号とは、暗号化したまま任意回の平文の加算や定数回の乗算を計算できる暗号である。Somewhat準同型暗号は、鍵生成KeyGen，暗号化Enc，復号Dec，準同型加算HomAdd，準同型乗算HomMulの5つのアルゴリズムからなる。以下にそれぞれを説明する。
【００８１】
鍵生成KeyGen：セキュリティパラメータ1^kを入力とし、公開鍵pk, 秘密鍵skを出力する。
(pk, sk)←KeyGen(1^k)
と記す。
【００８２】
暗号化Enc：公開鍵pk、メッセージMを入力とし、暗号文Cを出力する。
C←Enc(pk, M)と記す。
【００８３】
復号Dec：秘密鍵sk、暗号文Cを入力とし、メッセージMを出力する。
M←Dec(sk, C)
と記す。
【００８４】
準同型加算HomAdd：
公開鍵pk，暗号文C_1←Enc(pk, M_1)および C_2←Enc(pk, M_2) を入力として、
暗号文C_3←Enc(pk, M_1+M_2)を出力する。これを、
C_3←HomAdd(pk, C_1, C_2)
と記す。
【００８５】
準同型乗算HomMul：公開鍵pk，暗号文C_1←Enc(pk, M_1) および C_2←Enc(pk, M_2) を入力として、
暗号文C_3←Enc(pk, M_1・M_2)
を出力する。これを、
C_3←HomMul(pk, C_1, C_2)
と記す。
【００８６】
Somewhat準同型暗号を利用した場合、２つのｎ次元ベクトル 
X=(x[1], x[2], …, x[n])と
Y=(y[1], y[2], …, y[n])
の暗号文：
Enc(pk, X)=(Enc(pk, x[1]), Enc(pk, x[2]),…,Enc(pk, x[n])) と
Enc(pk, Y)=(Enc(pk, y[1]), Enc(pk,y[2]),…,Enc(pk, y[n]))
に対して、
XとYとの間の距離の暗号文Enc(pk, d(X,Y))を、XとYを暗号化したまま計算できる。
【００８７】
本実施例における各フェイズの動作について図面を参照して以下に説明する。
【００８８】
セキュリティパラメータ1^kを入力とした鍵生成装置４００の鍵生成部４０１が、Somewhat準同型暗号の鍵生成アルゴリズムKeyGen(1^k)を実行して公開鍵pkおよび秘密鍵skを生成し、公開鍵pkを登録データ生成装置１００、登録装置２００に送付する（図６のステップＳ１０１からＳ１０２）。
【００８９】
＜データ登録フェイズ＞
登録データ生成装置１００の登録データ生成部１０１が、平文登録データX=(x[1],…,x[n])を生成する（図７のステップＳ２０１）。
【００９０】
次に、部分登録データ生成部１０２が、平文登録データX=(x[1],…,x[n])から、部分平文登録データX’=(x’[1],…,x’[m])を生成する（図７のステップＳ２０２）。
【００９１】
このとき，n＞mであれば、どのような方法で部分平文登録データを生成してもよいが、ある整数（閾値） t’<=tに対して、X, Yが近いならば（距離d(X,Y)<t）、それぞれの部分データX’, Y’との間の距離d(X’,Y’)がt’以下となるようにする。例えば、t’=tとして、{x’[1], …,x’[m]}を、{x[1],…,x[n]}の部分集合とすれば、容易に生成できる。ただし、上記と異なる方法で生成してもよい。
【００９２】
次に、部分登録データ暗号化部１０３が、部分平文登録データX’と、鍵生成装置４００が生成した公開鍵pkを入力とし、以下の手順で暗号化部分登録データENC(X’)を生成する（図７のステップＳ２０３）。
【００９３】
＜登録セットアップフェイズ＞
1. i=1,…,mに対して、
enc_x’[i]=Enc(pk,x’[i])
を計算する。
【００９４】
2.  ENC(X’)=(enc_x’[1],…,enc_x’[m])
とする。
【００９５】
次に、登録データ暗号化部１０４が、平文登録データXと、鍵生成装置４００が生成した公開鍵pkを入力とし、以下の手順で暗号化登録データENC(X)を生成する（図７のステップＳ２０４）。
【００９６】
1.  i=1,…,nに対して、
enc_x[i]=Enc(pk,x[i])
を計算する。
【００９７】
2.  ENC(X)=(enc_x[1],…,enc_x[n])
とする。
【００９８】
3.  次に、登録データ送付部１０５が、暗号化部分登録データENC(X’)と、暗号化登録データENC(X)を入力とし、暗号化部分登録データと、暗号化登録データを含む登録データ(ENC(X), ENC(X)’)を生成し（図７のステップＳ２０５）、登録装置２００へ送信し（図７のステップＳ２０６）、登録装置２００は、暗号化部分登録データと、暗号化登録データを記憶装置３００へ送付する（図７のステップＳ２０７、Ｓ２０８）。
【００９９】
記憶装置３００は、受信した登録データに含まれる暗号化部分登録データを暗号化部分データ記憶部３０１に、暗号化登録データを暗号化データ記憶部３０２に、それぞれ記憶する（図７のステップＳ２０９）。
【０１００】
＜照合セットアップフェイズ＞
登録セットアップフェイズで鍵生成装置４００が生成した準同型暗号の公開鍵ｐｋを照合要求装置５００、照合装置６００、照合補助装置７００にそれぞれ送付し（図８のステップＳ３０１〜Ｓ３０３）、秘密鍵skを照合補助装置７００に送付する（図８のステップＳ３０４）。
【０１０１】
照合補助装置７００は、受信した秘密鍵skを鍵記憶部７０１に記憶する（図８のステップＳ３０５）。
【０１０２】
＜暗号文照合フェイズ＞
照合要求装置５００の照合データ生成部５０１が平文照合データ
Y=(y[1],…,y[n])
を生成する（図９のステップＳ４０１）。
【０１０３】
次に、部分照合データ生成部５０２が、平文照合データYを入力として、部分照合データY’=(y’[1],…,y’[m])を生成する（図９のステップＳ４０２）。ここで、Y’はデータ登録フェイズのステップＳ２０２（図７）と同じ方法で生成するものとする。
【０１０４】
次に、部分照合データ暗号化部５０３が、部分照合データY’と、鍵生成装置４００が生成した公開鍵pkを入力として、暗号化部分照合データENC(Y’)を以下の手順で生成する（図９のステップＳ４０３）。
【０１０５】
1.  i=1,…,mに対して、
enc_y’[i]=Enc(pk, y’[i])
とする。
【０１０６】
2.            ENC(Y’)=(enc_y’[1],…,enc_y’[m])とする。
【０１０７】
次に、照合データ暗号化部５０４が、平文照合データYと、公開鍵pkを入力として、暗号化照合データENC(Y)を以下の手順で生成する（図９のステップＳ４０４）。
【０１０８】
3.  i=1,…,nに対して、
enc_y[i]=Enc(pk, y[i])
とする。
【０１０９】
4.            ENC(Y)=(enc_y[1],…,enc_y[n])
とする。
【０１１０】
次に、照合クエリ送付部５０５が、暗号化部分照合データENC(Y’)と、暗号化照合データENC(Y)を入力として、暗号化部分照合データENC(Y’)と、暗号化照合データENC(Y)を含む照合クエリ(ENC(Y), ENC(Y’))を生成し（図９のステップＳ４０５）、照合装置６００へ送付する（図９のステップＳ４０６）。
【０１１１】
次に、照合クエリ(ENC(Y), ENC(Y’))を受信した照合装置６００の暗号化部分距離生成部６０１は、照合クエリに含まれる暗号化部分照合データENC(Y’)と、記憶装置３００の暗号化部分データ記憶部３０１に記憶された暗号化部分登録データENC(X’)と、公開鍵pkを入力として、以下の手順で暗号化部分距離ENC(d’)を生成する（図１０のステップＳ４０７）。
【０１１２】
1.  i=1,…,mに対して
(ａ)  準同型加算HomAddを使って，
Enc(pk,x’[i])とEnc(pk, y’[i])から
Enc(pk,x’[i]-y’[i])
を計算する。
(ｂ)  準同型乗算HomMulを使って，
Enc(pk, x’[i]-y’[i])から
Enc(pk, (x’[i]-y’[i])^2)
を計算する。
【０１１３】
2.  準同型加算HomAddを使って、
Enc(pk, (x’[1]-y’[1])^2),…, Enc(pk, (x’[m]-y’[m])^2)から、
ENC(d’)=Enc(pk, d(X’,Y’))
を計算する。
【０１１４】
ここで、暗号化部分データ記憶部３０１に複数のデータが記憶されている場合、ステップＳ４０７を複数回行ってもよい。その場合、次の部分データ照合補助依頼部６０２への入力は、複数個の暗号化部分距離{ENC(d’)}になる。簡単のため、以下では１つのENC(d’)について説明する。複数個の暗号化部分距離の場合にも容易に適用できる。
【０１１５】
次に、部分データ照合補助依頼部６０２は、暗号化部分距離ENC(d’)を入力として、部分データ照合補助依頼(ENC(d’))を生成し（図１０のステップＳ４０８）、照合補助装置７００に送付する（図１０のステップＳ４０９）。
【０１１６】
次に、部分データ照合補助依頼(ENC(d’))を受信した照合補助装置７００の部分データ照合補助部７０２は、部分データ照合補助依頼(ENC(d’))と、鍵記憶部７０１に記憶された秘密鍵skを入力とし、準同型暗号の復号Dec(sk, ENC(d’))を計算する（図１０のステップＳ４１０）。
【０１１７】
照合補助装置７００の部分データ照合補助部７０２は、
復号結果が閾値t’以下であった場合、部分照合受理を、
そうでなかった場合部分照合不受理を、
部分データ照合補助結果Result_y’とし、照合装置６００に送付する（図１０のステップＳ４１１）。
【０１１８】
次に、部分データ照合補助結果Result_y’を受信した照合装置６００の暗号化照合データ距離生成部６０３は、部分データ照合補助結果Result_y’が不受理であったら不受理を出力して以降の動作を停止する。
【０１１９】
部分データ照合補助結果Result_y’が受理であった場合、対応する暗号化登録データENC(X)を、記憶装置３００の暗号化データ記憶部３０２から受信し、前記照合クエリに含まれる暗号化照合データENC(Y)と、前記暗号化登録データENC(X)と、前記公開鍵pkを入力とし、以下の通りに暗号化距離ENC(d)を生成する（図１０のステップＳ４１２）。
【０１２０】
ここで、部分データ照合補助依頼が複数個の暗号文であった場合、部分データ照合補助結果は、どの暗号化部分距離が部分照合受理であったかがわかる情報（例えばデータのＩＤやインデックスなど）とすることができる。
【０１２１】
この場合、データのＩＤ等は部分データ照合補助依頼に含まれているものとする。
【０１２２】
1.  i=1,…,nに対して
(ａ)  準同型加算HomAddを使って、
Enc(pk,x[i])と、Enc(pk, y[i])から、
Enc(pk,x[i]-y[i])
を計算する。
(ｂ)  準同型乗算HomMulを使って、
Enc(pk, x[i]-y[i])から
Enc(pk, (x[i]-y[i])^2)
を計算する。
【０１２３】
2.  準同型加算HomAddを使って、
Enc(pk, (x[1]-y[1])^2),…, Enc(pk, (x[n]-y[n])^2)から、
ENC(d)=Enc(pk, d(X,Y))
を計算する。
【０１２４】
次に、照合装置６００の照合補助依頼部６０４は、暗号化距離ENC(d)を入力とし、照合補助依頼(ENC(d))を生成し（図１０のステップＳ４１３）、照合補助装置７００に送付する（図１０のステップＳ４１４）。
【０１２５】
照合補助依頼(ENC(d))を受信した照合補助装置７００の照合補助部７０３は、鍵記憶部７０１に記憶された秘密鍵skと、照合補助依頼(ENC(d))を入力とし、準同型暗号の復号
Dec(sk, ENC(d))を実行する。
【０１２６】
復号結果ｄが閾値t以下であったら、受理を、
復号結果ｄが閾値tを超えていたら、不受理を
照合補助結果Result_yとし（図１１のステップＳ４１５）、
照合補助結果Result_yを照合装置６００に送付する（図１１のステップＳ４１６）。
【０１２７】
照合補助結果Result_yを受信した照合装置６００の照合処理部６０５は、
Result_yが受理であったら、照合受理を、
Result_yが受理でなかったら、照合不受理を照合結果Resultとし生成し（図１１のステップＳ４１７）、
照合結果を照合要求装置５００に出力する（図１１のステップＳ４１８）。
【０１２８】
また、本実施形態では、二乗ユークリッド距離の例を挙げたが、他の距離（ハミング距離、マハラノビス距離など）にも容易に適用可能である。  
【０１２９】
また、本実施形態では、部分データも暗号化された例について説明したが、部分データを暗号化しない場合であってもよい。
【０１３０】
その場合は、照合装置が、照合時に、平文部分データと平文照合データとの距離を計算し、部分データの受理・不受理を判断できる。
【０１３１】
前記実施形態では、部分データを暗号化しているが、変形例として、部分データを暗号化しない場合を以下に説明する。
【０１３２】
＜実施形態の変形例１＞
図１２、図１３は、この変形例の構成を説明する図である。図１２に示すように、登録データ生成装置１００Ａは、部分登録データ暗号部１０３を備えていず、登録データ送付部１０５が、暗号化登録データと平文の部分登録データを、登録装置２００に送信する。また、照合要求装置５００Ａは、部分照合データ暗号化部５０３を備えていず、照合クエリ送付部５０５は、暗号化照合データと平文の部分照合データを入力としてクエリを生成し照合装置６００に送信する。図１３を参照すると、照合装置６００は、暗号化部分距離生成部６０１、部分データ照合補助依頼部６０２を備えていず、平文の部分登録データと平文の部分照合データとの間の距離が所定の閾値(t')以下であるか判別し、部分照合受理、不受理を出力する平文部分データ照合処理部６０８を備えている。なお図３（Ａ）の記憶装置３００の暗号化部分データ記憶部３０１は、平文の部分登録データを記憶する記憶部に置き換えられる。
【０１３３】
変形例では、図７のステップＳ２０３の処理が削除され、ステップＳ２０５では、登録データには、暗号化登録データと平文の部分登録データを含ませる。ステップＳ２０７では、平文の部分登録データが記憶装置３００に転送され、ステップＳ２０９では、暗号化登録データと平文の部分登録データ（部分平文登録データ）が記憶される。図９のステップＳ４０２、４０３の処理が削除され、図９のステップＳ４０５では、照合クエリには、暗号化照合データと平文の部分照合データ（部分平文照合データ）を含ませる。また図１０のステップＳ４０７からステップＳ４１１が省略される。図１０のステップＳ４０７〜Ｓ４１１の代わりに、照合装置６００Ａにおいて、平文部分データ照合処理部６０８が、平文の登録部分データ（部分平文登録データ）と平文の照合部分データ（部分平文照合データ）の距離が閾値ｔ’以下であるか判定し、該距離が閾値（t'）以下である場合には、部分照合受理、閾値（t'）を超える場合には、部分照合不受理を出力する。暗号化照合データ距離生成部６０３は、部分照合受理の場合に、図１０のステップＳ４１２の処理を実行し、図１０のステップ４１３から図１１のステップ４１８の処理が実行される。
【０１３４】
＜実施形態の変形例２＞
同様に、登録時と照合時のいずれか一方だけ、部分平文データを暗号化するようにしてもよい。この場合、照合装置６００（図４（Ｂ））において、例えば暗号化部分距離生成部６０１は削除され、部分データ照合補助依頼部６０２は、部分登録データと部分照合データのうちの一方の平文の部分データと、部分登録データと部分照合データのうちの他方の暗号化部分データの部分データ照合補助依頼を、照合補助装置７００に依頼する。照合補助装置７００の部分データ照合補助部７０２（図５）では、部分登録データと部分照合データの前記他方の暗号化部分データを、秘密鍵を用いて復号した上で、部分登録データと部分照合データの前記一方の平文の部分データとの間の距離を求める。部分データ照合補助部７０２（図５）では、該距離が閾値（t’）以下である場合には、部分照合受理を、該距離が閾値（t’）を上回る場合には、部分照合不受理を照合装置６００に送信するようにしてもよい。これ以降の照合装置６００の処理と、照合補助装置７００による暗号化照合データと暗号化登録データの照合処理は、前述した実施形態と同様であるため説明は省略する。
【０１３５】
さらに、非特許文献２や非特許文献３には、登録データと照合データ間の距離を秘匿したまま照合を行う方法が記載されており、本発明はこれらの方式とも組み合わせ可能である。
【０１３６】
上記実施形態は、特徴量として多値ベクトルを用いる生体認証への適用が可能である。
挙げられる。
【０１３７】
例えば、データ登録フェイズにおいて登録データ生成装置１００が入力するデータと、暗号文照合フェイズにおいて照合要求装置５００が入力するデータを、指紋センサや静脈センサで取得した生体情報から抽出された特徴量（特徴ベクトル）とすることで、生体情報を秘匿したまま、記憶装置に格納された暗号化された生体データと、照合要求装置から送出された暗号化された生体データが、同一人物から採取されたものであるか否かを、２つの入力データの距離が一定数以下となるかどうかにより判定することが可能となる。特に、生体情報は、常に安定して同一のデータが取得できるわけではないことが知られており、同じ人物から取得されるデータが類似している（各要素の距離が小さいデータが取得できる）と仮定できるため、生体認証へ適用して好適とされる。
【０１３８】
なお、上記の特許文献１−５、非特許文献１−３の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各付記の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１３９】
１  コンピュータ装置
２  ＣＰＵ
３  記憶装置
４  Ｉ／Ｏインタフェース
５  通信インタフェース
６  センサ
１００、１００Ａ  登録データ生成装置
１０１  登録データ生成部
１０２  部分登録データ生成部
１０３  部分登録データ暗号化部
１０４  登録データ暗号化部
１０５  登録データ送付部
１０６  通信インタフェース（ＩＦ）
２００  登録装置
２０１  登録処理部
２０２  登録データ受信部
２０３  通信インタフェース（ＩＦ）
３００  記憶装置
３０１  暗号化部分データ記憶部
３０２  暗号化データ記憶部
３０３  通信インタフェース（ＩＦ）
４００  鍵生成装置
４０１  鍵生成部
４０２  通信インタフェース（ＩＦ）
５００、５００Ａ  照合要求装置
５０１  照合データ生成部
５０２  部分照合データ生成部
５０３  部分照合データ暗号化部
５０４  照合データ暗号化部
５０５  照合クエリ送付部
５０６  通信インタフェース（ＩＦ）
６００、６００Ａ  照合装置
６０１  暗号化部分距離生成部
６０２  部分データ照合補助依頼部
６０３  暗号化照合データ距離生成部
６０４  照合補助依頼部
６０５  照合処理部
６０６  照合クエリ受信部
６０７  通信インタフェース（ＩＦ）
６０８  平文部分データ照合処理部
７００、７００Ａ  照合補助装置
７０１  鍵記憶部
７０２  部分データ照合補助部
７０３  照合補助部
７０４  通信インタフェース（ＩＦ）
【図１】
2018042045.tif 000003
【図２】
2018042045.tif 000004
【図３】
2018042045.tif 000005
【図４】
2018042045.tif 000006
【図５】
2018042045.tif 000007
【図６】
2018042045.tif 000008
【図７】
2018042045.tif 000009
【図８】
2018042045.tif 000010
【図９】
2018042045.tif 000011
【図１０】
2018042045.tif 000012
【図１１】
2018042045.tif 000013
【図１２】
2018042045.tif 000014
【図１３】
2018042045.tif 000015
【図１４】
2018042045.tif 000016
【図１５】
2018042045.tif 000017