(57)【特許請求の範囲】
【請求項１】
クライアントと、認証サーバと、復号サーバとを備える暗号文照合システムであって、
前記クライアントに備えられ、暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを出力する登録データ生成部と、
前記認証サーバに備えられ、該登録データを暗号文記憶部に、当該登録データを一意に特定するための識別子を識別子記憶部に、それぞれ対応が分かるように記憶する記憶装置と、
前記クライアントに備えられ、前記暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを出力するデータ照合要求生成部と、
前記認証サーバに備えられ、前記暗号文記憶部に記憶されているすべての登録データと前記照合データとから前記暗号化鍵を用いて、すべての暗号化距離データを出力する距離計算部と、
前記復号サーバに備えられ、復号鍵を用いて前記すべての暗号化距離データを復号して、すべての距離データを生成する復号部と、
前記復号サーバに備えられ、前記すべての距離データから距離の順序を保つようにランダムに選択されたスコアを生成するスコア計算部と、
前記認証サーバに備えられ、前記スコアから照合結果を出力する判定部と、
を含む、暗号文照合システム。
【請求項２】
前記復号サーバは、セキュリティパラメータから、前記暗号化鍵と前記復号鍵とを生成する鍵生成部を更に含む、請求項１に記載の暗号文照合システム。
【請求項３】
前記鍵生成部は、前記暗号化鍵および前記復号鍵として、それぞれ、準同型暗号あるいはSomewhat準同型暗号の公開鍵および秘密鍵を生成する請求項２に記載の暗号文照合システム。
【請求項４】
請求項１乃至３のいずれか１項に記載の暗号文照合システムを備え、前記秘匿対象となる入力データおよび前記照合対象の入力データが生体情報であり、前記秘匿対象となる入力データと前記照合対象の入力データとが類似している否かを判定することによって生体認証を行うことを特徴とする生体認証システム。
【請求項５】
第１のクライアントが、暗号化鍵を用いて秘匿対象となる入力データを暗号化して登録データを生成し、認証サーバが、該登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶するデータ登録ステップと、
第２のクライアントが、前記暗号化鍵を用いて照合対象の入力データを暗号化して照合データを生成し、前記認証サーバが、前記記憶部に記憶されたすべての前記登録データと前記照合データとから、前記暗号化鍵を用いてすべての暗号化距離データを生成し、復号サーバが、復号鍵を用いて前記すべての暗号化距離データを復号してすべての距離データを生成し、該すべての距離データから距離の順序を保つようにランダムに選択されたスコアを生成し、前記認証サーバが、前記スコアから照合結果を生成する、暗号文照合ステップと、
を含む、暗号文照合方法。
【請求項６】
第１のクライアントが、暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを生成する登録データ生成ステップと、
認証サーバが、該登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶するステップと、
第２のクライアントが、前記暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを生成するデータ照合要求生成ステップと、
前記認証サーバが、前記記憶部に記憶されたすべての前記登録データと前記照合データとから、前記暗号化鍵を用いてすべての暗号化距離データを生成する距離計算ステップと、
復号サーバが、復号鍵を用いて前記すべての暗号化距離データを復号して、すべての距離データを生成する復号ステップと、
前記復号サーバが、前記すべての距離データから距離の順序を保つようにランダムに選択されたスコアを計算するスコア計算ステップと、
前記認証サーバが、前記スコアから照合結果を生成する判定ステップと、
を含む、暗号文照合方法。
【請求項７】
登録データ生成装置と、記憶装置と、データ照合要求装置と、データ照合判定装置と、照合補助装置とを備える暗号文照合システムであって、
前記登録データ生成装置は、秘匿対象となる入力データと、暗号化鍵とを入力とし、登録データを出力する登録データ生成部を備え、
前記記憶装置は、前記登録データ生成部が生成した登録データを入力として受け取り、データごとに異なる識別子を生成し、前記登録データを暗号文記憶部に、対応する識別子を識別子記憶部に、それぞれ対応が分かるように記憶する識別子管理部を備え、
前記データ照合要求装置は、前記暗号化鍵と、照合対象データとを入力とし、照合データを出力するデータ照合要求生成部を備え、
前記データ照合判定装置は、
前記記憶装置の前記暗号文記憶部に記憶されている登録データをすべて取得するデータ取得部と、
取得した登録データと、前記照合データと、前記暗号化鍵とを入力とし、すべての暗号化距離データを出力する距離計算部と、
前記すべての暗号化距離データを入力とし、前記照合補助装置に補助要求データを出力する補助要求部と、
前記照合補助装置から受信したスコアを入力とし、照合結果を出力する判定部と、を備え、
前記照合補助装置は、
セキュリティパラメータを入力とし、前記暗号化鍵および復号鍵を出力する鍵生成部と、
前記データ照合判定装置から受信した補助要求データと、前記復号鍵とを入力とし、すべての距離データを生成する復号部と、
前記すべての距離データを入力とし、距離の順序を保つようにランダムに選択された前記スコアを出力するスコア計算部と、を備える
ことを特徴とする暗号文照合システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化されたデータの曖昧さを許容する暗号文照合システム、方法およびプログラムに関し、特に、秘匿対象となる入力データ（照合元データ）も、照合対象の入力データ（照合対象データ）もともに暗号化されている状況で、曖昧さの指標を平文のユークリッド距離とした場合の暗号文照合システム、方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、クラウドの普及に伴い、ネットワークに接続された計算資源に利用者のデータを置き、そのデータに基づいたサービスが急速に広がってきている。このようなサービスでは、利用者の機微なデータを扱う機会も増大してきている。このため、利用者が自分のデータが安全に管理されていることを保証することが重要になってきている。
【０００３】
このような状況の下、オープンなネットワーク環境でデータを暗号化したまま管理し、データを復号することなく、検索や、統計処理などを行う技術の研究開発が活発に行われている。
【０００４】
また、近年、従来のパスワードや磁気カードを用いた個人認証の脆弱性をついた犯罪が頻発している。このため、より安全性の高い指紋、静脈などの生体的な特徴に基づく生体認証技術が注目を集めている。
【０００５】
生体認証においては、認証情報の検証を行うために、生体情報に関するテンプレートをデータベースに保管する必要がある。指紋、静脈等の生体情報は基本的に生涯不変のデータである。生体情報は、もしそれが漏洩すると、その被害は甚大なものとなる。このため、生体情報は、最も機密性が要求される情報である。したがって、テンプレートが漏洩した場合でも、「なりすまし」等が行えないようにする必要がある。
【０００６】
例えば、特許文献１は、生体データから得られた特徴ベクトルのユークリッド距離を、準同型暗号を用いて暗号化したまま計算することにより、特徴ベクトルを秘匿したままの生体認証を実現している。
【０００７】
特許文献１に開示された方式は、生体認証を依頼するクライアント、認証を行う認証サーバのほかに、準同型暗号の復号鍵を保持し、サーバの依頼に応じて復号を行う復号サーバが存在する。特許文献１の生体認証では、生体情報から得られる特徴ベクトルを用いて、認証を行う。
【０００８】
また、非特許文献１、非特許文献２、非特許文献３、非特許文献４は、上記特許文献１の方式に対して復号サーバを利用した攻撃方法を提案し、それぞれ攻撃を防ぐ方法を述べている。
【０００９】
一方、特許文献２は、暗号文照合において、元の平文に関する漏洩を回避可能とし、安全性を担保可能とした暗号文照合システムを開示している。この特許文献２に開示された暗号文照合システムにおいて、照合対象の入力データが暗号化され、該入力の照合を行うための登録データが暗号化されている。また、特許文献２は、入力データのみがシステムに入力され、入力データと照合する暗号データの識別子が出力され、１対多照合を実現する、実施の形態も開示している。
【００１０】
また、特許文献３は、生体情報を暗号化したままで生体認証を行う方法を開示している。特許文献３は、証明装置と、認証装置と、復号装置とを有する生体認証装置を開示している。証明装置は、ユーザから生体情報を測定し、測定した生体情報を用いて秘匿証明処理を行う。認証装置は、ユーザの生体情報を暗号化した格納しておくとともに、格納した暗号化された生体情報を用いて認証を行う。復号装置は、暗号化データを復号する。
【００１１】
証明装置の暗号化部は、公開鍵と乱数を用いて特徴ベクトルを暗号化する。認証装置の暗号化類似度生成部は、登録されている暗号化特徴ベクトルと認証用の特徴ベクトルとから、公開鍵と乱数を用いて暗号化類似度情報を生成する。復号装置の復号部は、暗号化類似度情報に秘密鍵を用いて復号処理を行い、平文の類似度を導出する。復号装置の通信部は、平文の類似度を認証装置に送信する。認証装置の判定部は、平文の類似度が所定のしきい値以上であるか否かを判定し、しきい値以上であれば本人と判定し、しきい値を下回っている場合は、本人ではないと判定する。
【００１２】
尚、特許文献３では、類似度の指標として２つの特徴ベクトルのハミング距離またはユークリッド二乗距離を用いている。
【００１３】
さらに、特許文献４は、暗号化した画像データに対して復号せずに画像の評価等の画像処理を行う技術を開示している。特許文献４に開示された画像検索では、検索先画像及びクリエ画像の各々から特徴量を抽出し、これらを秘密分散暗号化し、暗号化領域で特徴量の距離の演算を行っている。特許文献４に開示の画像検索では、特徴量ベクトル同士の距離を暗号化領域で演算し、その復号した値を類似度としている。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特許第５４９６４１０号公報
【特許文献２】国際公開第２０１４／０１０７２５号
【特許文献３】国際公開第２０１１／０５２０５６号
【特許文献４】特開２０１３−０９７３５１号公報
【非特許文献】
【００１５】
【非特許文献１】キャンセラブル生体認証方式の安全性について（その２），伊豆哲也，酒見由美，武中正彦，鳥居直哉，電子情報通信学会ISEC研究会，2013．
【非特許文献２】キャンセラブル生体認証方式の安全性について（その３），伊豆哲也，酒見由美，武中正彦，鳥居直哉，2014年暗号と情報セキュリティシンポジウム，2014．
【非特許文献３】準同型暗号を用いた秘匿生体認証に対する安全性について（その１），酒見由美，武中正彦，鳥居直哉，安田雅哉，電子情報通信学会ISEC研究会，2014．
【非特許文献４】準同型暗号を用いた秘匿生体認証に対する安全性について（その２），酒見由美，武中正彦，鳥居直哉，安田雅哉，電子情報通信学会ISEC研究会，2014．
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、特許文献１および非特許文献１〜４に開示されたいずれの方式も、復号サーバからの返答はOKまたはNGであり、どの程度近かったかを表す距離情報（類似度）は認証サーバに伝えられていない。
【００１７】
特許文献２に開示されているような、1:N認証を行う際に、距離情報（類似度）が認証サーバに伝えられないことが問題となりうる。ここで、「1:N認証」とは、１つの認証データが、Ｎ個の登録データに含まれているかどうかを判定する認証である。上記の方式のように、認証サーバに距離情報（類似度）が伝えられない場合、認証サーバがその判定を行えない。
【００１８】
一方で、復号サーバからの返答をOKあるいはNGではなく、例えば、上記特許文献３のように、復号結果、すなわち特徴ベクトル（特徴量）ZとZ’と間の距離を表す距離情報（類似度）を返すように変更すれば、上記問題は容易に解決する。しかしながら、距離情報（類似度）そのものを認証サーバに返答することにより、距離を利用したヒルクライミング攻撃（後述する）が可能となることが知られている。したがって、復号サーバから距離情報（類似度）そのものを出力することは、安全性上好ましくない。
【００１９】
また、暗号化したままの照合方法として、決定的な共通鍵暗号や公開鍵暗号を利用した検索可能暗号を利用する方法が知られている。しかしながら、これらの方法は一般に、検索に用いるキーワードが一意に定まっている必要がある。上記のように生体情報を利用して照合を行う場合、生体情報取得時に含まれるノイズのせいで常に同じ生体情報が得られるわけではないことが知られている。このため、検索可能暗号を適用することが難しい。
【００２０】
尚、特許文献４は、単に、特徴量ベクトル同士の距離を暗号化領域で演算し、その復号した値を類似度とする、画像検索技術を開示しているに過ぎない。
【００２１】
上述した先行技術の問題点は、復号サーバからの返答が登録に使った特徴ベクトル（特徴量）Zと認証に使った特徴ベクトル（特徴量）Z’が近い，あるいは遠いのみであることである。あるいは、距離情報（類似度）そのものを出力してしまうことにより、登録データあるいは認証データから特徴ベクトル（特徴量）ZあるいはZ’が復元されてしまうことである。
【００２２】
本発明の目的は、登録時に使用したデータZと照合時に使用したデータZ’との間の距離に関する情報を出力しても、データに関する情報が漏れない、暗号文照合システム、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２３】
本発明の暗号文照合システムは、クライアントと、認証サーバと、復号サーバとを備える暗号文照合システムであって、上記クライアントに備えられ、暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを出力する登録データ生成部と、上記認証サーバに備えられ、登録データを暗号文記憶部に、当該登録データを一意に特定するための識別子を識別子記憶部に、それぞれ対応が分かるように記憶する記憶装置と、上記クライアントに備えられ、暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを出力するデータ照合要求生成部と、上記認証サーバに備えられ、上記暗号文記憶部に記憶されているすべての登録データと照合データとから暗号化鍵を用いて、すべての暗号化距離データを出力する距離計算部と、上記復号サーバに備えられ、復号鍵を用いてすべての暗号化距離データを復号して、すべての距離データを生成する復号部と、上記復号サーバに備えられ、すべての距離データから距離の順序を保つようにランダムに選択されたスコアを生成するスコア計算部と、上記認証サーバ備えられ、スコアから照合結果を出力する判定部と、を含む。
【００２４】
また、本発明の暗号文照合方法は、第１のクライアントが、暗号化鍵を用いて秘匿対象となる入力データを暗号化して登録データを生成し、認証サーバが、登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶するデータ登録ステップと、第２のクライアントが、暗号化鍵を用いて照合対象の入力データを暗号化して照合データを生成し、認証サーバが、記憶部に記憶されたすべての登録データと照合データとから、暗号化鍵を用いてすべての暗号化距離データを生成し、復号サーバが、復号鍵を用いてすべての暗号化距離データを復号してすべての距離データを生成し、すべての距離データから距離の順序を保つようにランダムに選択されたスコアを生成し、認証サーバが、スコアから照合結果を生成する、暗号文照合ステップと、を含む。
【発明の効果】
【００２６】
本発明によれば、登録時に使用したデータと照合時に使用したデータとの間の距離に関する情報を出力しても、データに関する情報が漏れないという効果がある。
【図面の簡単な説明】
【００２７】
【図１】第１の関連技術による暗号文照合システムの構成を示すブロック図である。
【図２】第２の関連技術による暗号文照合システムの構成を示すブロック図である。
【図３】本発明に係る暗号文照合システムの概略構成を示すブロック図である。
【図４】本発明の第１の実施形態に係る暗号文照合システムの構成例を示すブロック図である。
【図５】図４に示した暗号文照合システムに使用される、登録データ生成装置および記憶装置の構成例を示すブロック図である。
【図６】図４に示した暗号文照合システムに使用される、データ照合要求装置およびデータ照合判定装置の構成例を示すブロック図である。
【図７】図４に暗号文照合システムに使用される、照合補助装置の構成例を示すブロック図である。
【図８】図４に示した暗号文照合システムの、セットアップフェイズの動作例を示すフローチャートである。
【図９】図４に示した暗号文照合システムの、データ登録フェイズの動作例を示すフローチャートである。
【図１０】図４に示した暗号文照合システムの、暗号文照合フェイズの動作例を示すフローチャートである。
【図１１】本発明の第２の実施形態に係る暗号文照合システムの構成例を示すブロック図である。
【図１２】図１１に示した暗号文照合システムに使用される、登録データ生成装置の構成例を示すブロック図である。
【図１３】図１１に示した暗号文照合システムに使用される、データ照合要求装置の構成例を示すブロック図である。
【図１４】図１１に示した暗号文照合システムに使用される、データ照合判定装置の構成例を示すブロック図である。
【図１５】図１１に示した暗号文照合システムの、セットアップフェイズの動作例を示すフローチャートである。
【図１６】図１１に示した暗号文照合システムの、データ登録フェイズの動作例を示すフローチャートである。
【図１７】図１１に示した暗号文照合システムの、暗号文照合フェイズの前半の動作例を示すフローチャートである。
【図１８】本発明の第１の実施例による暗号文照合システムの、セットアップフェイズの動作例を示すフローチャートである。
【図１９】本発明の第１の実施例による暗号文照合システムの、データ登録フェイズの動作例を示すフローチャートである。
【図２０】本発明の第１の実施例による暗号文照合システムの、暗号文照合フェイズの動作例を示すフローチャートである。
【図２１】本発明の第２の実施例による暗号文照合システムの、セットアップフェイズの動作例を示すフローチャートである。
【図２２】本発明の第２の実施例による暗号文照合システムの、データ登録フェイズの動作例を示すフローチャートである。
【図２３】本発明の第２の実施例による暗号文照合システムの、暗号文照合フェイズの動作例を示すフローチャートである。
【発明を実施するための形態】
【００２８】
［関連技術］
上述したように、上記特許文献１では、生体データから得られた特徴ベクトルのユークリッド距離を、準同型暗号を用いて暗号化したまま計算することにより、特徴ベクトルを秘匿したままの生体認証を実現している。
【００２９】
図１に示されるように、特許文献１に開示された、第１の関連技術による暗号文照合システムは、生体認証を依頼するクライアント１０と、認証を行う認証サーバ２０と、準同型暗号の復号鍵を保持し、認証サーバ２０の依頼に応じて復号を行う復号サーバ３０と、を備える。特許文献１に開示された生体認証（暗号文照合システム）では、生体情報から得られる特徴ベクトルZを用いて、以下のように認証を行う。
【００３０】
まず、第１の関連技術による暗号文照合システムでは、登録を以下の通り行う。
【００３１】
クライアント１０は、自身の生体データから得られた特徴ベクトルZを準同型暗号の暗号化鍵を用いて暗号化する。
【００３２】
（Ａ１）復号サーバ３０は鍵生成を行い、準同型暗号の公開鍵pkおよび秘密鍵skを生成する。復号サーバ３０は、公開鍵をクライアント１０へ送付する。
【００３３】
（Ａ２）クライアント１０は、特徴ベクトルZを公開鍵pkを用いて暗号化し、登録データENC(pk, Z)を生成する。クライアント１０は、登録データENC(pk, Z)を認証サーバ２０へ送付する。
【００３４】
（Ａ３）認証サーバ２０は登録データENC(pk, Z)を記憶する。
【００３５】
次に、第１の関連技術による暗号文照合システムでは、認証を以下の通り行う。
【００３６】
ここでクライアント１０は、特徴ベクトルZ’を保持しているものとする。同じ人物であれば２つの特徴ベクトルZ, Z’の距離は近く、異なる人物の特徴ベクトルZ, Z’の距離は遠いものとする。
【００３７】
（Ｂ１）クライアント１０は、特徴ベクトルZ’ を公開鍵pkを用いて暗号化し、照合データENC(pk, Z’)を生成する。クライアント１０は、照合データENC(pk, Z’)を認証サーバ２０へ送付する。
【００３８】
（Ｂ２）認証サーバ２０は、準同型性を利用し、暗号化したまま暗号化距離データENC(pk, d(Z, Z’))を計算する。ここでd(a, b)はaとbとの間の距離を意味する。認証サーバ２０は、暗号化距離データENC(pk, d(Z, Z’))を復号サーバ３０へ送付する。
【００３９】
（Ｂ３）復号サーバ３０は、秘密鍵skを用いて暗号化距離データENC(pk, d(Z, Z’))を復号して、復号結果d(Z, Z’)を得る。この復号結果は距離情報を示している。
【００４０】
（Ｂ４）復号サーバ３０は、復号結果d(Z, Z’)があらかじめ決められた閾値t以下であるか否かを確認する。復号サーバ３０は、復号結果d(Z, Z’)が閾値t以下であったらOKを、復号結果d(Z, Z’)が閾値tよりも大きかったらNGを、認証サーバ２０へ送付する。
【００４１】
（Ｂ５）認証サーバ２０は、復号サーバ３０の返答がOKであったら受理を、NGであったら不受理を、クライアント１０へ出力する。
【００４２】
また、上記非特許文献１、非特許文献２、非特許文献３、非特許文献４では、上記特許文献１の方式に対して復号サーバを利用した攻撃方法を提案し、それぞれ攻撃を防ぐ方法を述べている。
【００４３】
しかしながら、いずれの方式も、復号サーバ３０からの返答はOKまたはNGであり、どの程度近かったかを表す距離情報(類似度)は認証サーバ２０に伝えられていない。
【００４４】
一般に生体認証では、FAR(False Acceptance Rate=誤り受け入れ率)が小さくない。すなわち、別人を本人として受け入れてしまう確率が無視できない。そのため、上記特許文献２のように、1:N認証を行う際に、上記距離情報（類似度）が認証サーバ２０に伝えられないことが問題となりうる。ここで、「1:N認証」とは、１つの認証データが、Ｎ個の登録データに含まれているかどうかを判定する認証である。
【００４５】
詳述すると、登録されている暗号文をENC(pk, Z[1])，…，ENC(pk, Z[N])とする。このとき、認証サーバ２０は、特徴ベクトルZ’と近いZ[1]，…，Z[N]が存在するかどうかを判定する。このとき、生体認証では、FARが無視できないため、Ｎが大きい場合、特徴ベクトルZ’と近いZ[i]が複数個存在する。このときテンプレート保護ではない生体認証では、認証サーバ２０が、特徴ベクトルZと有意に近い（他のZ[i]よりも明らかに近い）Z[j]を本人として判定していることがある。しかしながら、上記の方式のように、認証サーバ２０に距離情報（類似度）が伝えられない場合、認証サーバ２０がその判定を行えない。
【００４６】
一方で、図２に示される第２の関連技術による暗号文照合システムのように、復号サーバ３０Ａからの返答をOKあるいはNGではなく、上記特許文献３のように、復号結果、すなわち特徴ベクトルZと特徴ベクトルZ’との間の距離を表す距離情報（類似度）そのものを返すように変更すれば、上記問題は容易に解決する。
【００４７】
しかしながら、距離情報（類似度）そのものを認証サーバ２０Ａに返答することにより、距離を利用したヒルクライミング攻撃が可能となることが知られている。ここで、「ヒルクライミング攻撃」とは、次に述べるような攻撃のことをいう。
【００４８】
ある特徴ベクトルZ’を使って生成した認証データに対する第１の距離d(Z, Z’)を得、次に、特徴ベクトルZ’の一部を改変した（例えば1ビット反転した）Z”を利用した認証データに対する第２の距離d(Z, Z”)を得る。第１の距離d(Z, Z’)よりも第２の距離d(Z, Z”)が小さくなった場合は、改変によって特徴ベクトルZに近づいたことを意味し、逆に大きくなった場合は、改変によって特徴ベクトルZから遠ざかったことを意味する。
【００４９】
このような行動を繰り返すことにより、比較的小さな計算量で、登録データから特徴ベクトルZを（あるいは認証データから特徴ベクトルZ’を）復元することが可能となることが知られている。したがって、復号サーバ３０Ａから距離情報（類似度）そのものを出力することは、安全性上好ましくない。
【００５０】
また、暗号化したままの照合方法として、決定的な共通鍵暗号や公開鍵暗号を利用した検索可能暗号を利用する方法が知られている。しかしながら、これらの方法は一般に、検索に用いるキーワードが一意に定まっている必要がある。上記のように生体情報を利用して照合を行う場合、生体情報取得時に含まれるノイズのせいで常に同じ生体情報が得られるわけではないことが知られている。このため、生体情報の照合方法に、検索可能暗号を適用することが難しい。
【００５１】
上述の先行技術（関連技術)の問題点は、復号サーバ３０からの返答が登録に使った特徴ベクトル（特徴量）Zと認証に使った特徴ベクトル（特徴量）Z’とが近い，あるいは遠いのみであることである。あるいは、復号サーバ３０Ａから距離情報（類似度）そのものを出力してしまうことにより、登録データあるいは認証データから特徴ベクトル（特徴量）ZあるいはZ’が復元されてしまうことである。
【００５２】
［発明の概要］
そこで、本発明では、登録時に使用したデータZと照合時に使用したデータZ’と間の距離に関する情報（距離情報)を出力しても、データに関する情報が漏れない、照合元データと照合対象データに多少の誤差を許した暗号文照合システムを実現することを目的とする。
【００５３】
図３は、本発明に係る暗号文照合システムの概略構成を示すブロック図である。図示の暗号文照合システムは、生体認証を依頼するクライアント１０と、認証を行う認証サーバ２０Ｂと、準同型暗号の復号鍵を保持し、認証サーバ２０Ｂの依頼に応じて復号を行う復号サーバ３０Ｂと、を備える。
【００５４】
本発明に係る暗号文照合システムでは、照合時に復号サーバ３０Ｂにより計算された距離情報を、適切な分布に従って選ばれた乱数値に置き換えることにより、スコアを生成する。適切な分布に従って乱数を選ぶことにより、例えば１位と２位が有意に差があるか否かを認証サーバ２０Ｂが判定することが可能となる。また、毎回照合時に用いる乱数を変更することにより、前回より近くなったか遠くなったかの判定ができず、ヒルクライミング攻撃が不可能となる。
【００５５】
本発明に係る暗号文照合システムでは、復号サーバ３０Ｂからの出力がスコアとなることにより、認証サーバ２０Ｂが認証結果（照合結果）を判断するために必要な情報を得ることができる。その理由は、 復号後に、スコア生成のために適切な分布に従った乱数を利用するためである。
【００５６】
（第１の実施形態）
次に、本発明の第１の実施形態による暗号文照合システムについて図面を参照して詳細に説明する。
【００５７】
図４を参照すると、本発明の第１の実施形態による暗号文照合システムは、登録データ生成装置１００と、記憶装置２００と、データ照合要求装置３００と、データ照合判定装置４００と、照合補助装置５００と、から成る。
【００５８】
登録データ生成装置１００およびデータ照合要求装置３００を利用するエンティティが、図３のクライアント１０に相当する。記憶装置２００を有し、データ照合判定装置４００を利用するエンティティが、図３の認証サーバ２０Ｂに相当する。そして、照合補助装置５００を利用するエンティティが、図３の復号サーバ３０Ｂに相当する。
【００５９】
換言すれば、登録データ生成装置１００は第１のクライアントとして実現され、データ照合要求装置３００は第２のクライアントとして実現される。記憶装置２００とデータ照合判定装置４００との組み合わせは認証サーバ２０Ｂとして動作する。照合補助装置５００は復号サーバ３０Ｂとして動作する。第１のクライアントと第２のクライアントとは、別々のクライアントであっても良いし、同じ１つのクライアントであって良い。
【００６０】
［構成の説明］
図５を参照すると、登録データ生成装置１００は、登録データ生成部１０１から成る。登録データ生成部１０１は、秘匿対象となる入力データと、後述する照合補助装置５００の鍵生成部５０１が生成した暗号化鍵とを入力とし、登録データを出力する。
【００６１】
図５に示されるように、記憶装置２００は、識別子管理部２０１と、暗号文記憶部２０２と、識別子記憶部２０３と、から成る。
【００６２】
識別子管理部２０１は、登録データ生成装置１００の登録データ生成部１０１が生成した登録データを入力として受け取り、登録データごとに異なる識別子を生成する。識別子管理部２０１は、登録データを暗号文記憶部２０２に、対応する識別子を識別子記憶部２０３に、それぞれ対応が分かるように記憶する。
【００６３】
図６を参照すると、データ照合要求装置３００は、データ照合要求生成部３０１と、識別子記憶部３０２とから成る。
【００６４】
データ照合要求生成部３０１は、後述する照合補助装置５００の鍵生成部５０１が生成した暗号化鍵と、識別子記憶部３０２に記憶された識別子と、照合対象の入力データとを入力とし、照合データを出力する。
【００６５】
図６に示されるように、データ照合判定装置４００は、データ取得部４０１と、距離計算部４０２と、補助要求部４０３と、判定部４０４とから成る。
【００６６】
データ取得部４０１は、照合データに含まれる識別子に対応する登録データを、記憶装置２００の暗号文記憶部２０２および識別子記憶部２０３から取得する。
【００６７】
距離計算部４０２は、取得した登録データと、照合データと、暗号化鍵とを入力とし、暗号化距離データを出力する。
【００６８】
補助要求部４０３は、暗号化距離データを入力とし、照合補助装置５００に補助要求データを出力する。
【００６９】
判定部４０４は、照合補助装置５００から受信したスコアを入力とし、照合結果を出力する。
【００７０】
図７を参照すると、照合補助装置５００は、鍵生成部５０１と、復号部５０２と、スコア計算部５０３と、鍵記憶部５０４とから成る。
【００７１】
鍵生成部５０１は、セキュリティパラメータを入力とし、暗号化鍵および復号鍵を出力する。
【００７２】
復号部５０２は、前記データ照合判定装置４００から受信した補助要求データと、復号鍵とを入力とし、距離データを生成する。
【００７３】
スコア計算部５０３は、距離データを入力とし、乱数を用いてスコアを出力する。
【００７４】
［動作の説明］ 
次に、本発明の第１の実施形態による暗号文照合システムの動作に関して詳細に説明する。
【００７５】
本発明の第１の実施形態による暗号文照合システムの動作は、セットアップフェイズと、データ登録フェイズと、暗号文照合フェイズと、の３つのフェイズに大別される。
【００７６】
ここで、データ登録フェイズは、登録データ生成装置１００に入力データを入力し、入力データを暗号化し、記憶装置２００に登録するフェイズである。暗号文照合フェイズは、データ照合要求装置３００に入力された入力データを暗号化し、その際に生成された照合要求が、データ照合判定装置４００によって記憶装置２００内の暗号データ（登録データ）と近い（ユークリッド距離の小さい）平文となるものであるかを判定するフェイズである。
【００７７】
以下、各フェイズにおける動作に関して詳細に説明する。
【００７８】
図８を参照すると、セットアップフェイズにおいては、まず、照合補助装置５００の鍵生成部５０１にセキュリティパラメータが入力され、暗号化鍵および復号鍵が生成される（ステップＡ１）。
【００７９】
次に、鍵生成部５０１は、生成した暗号化鍵を登録データ生成装置１００と、照合要求装置３００と、データ照合判定装置４００とに送付し、復号鍵を鍵記憶部５０３に記憶する（ステップＡ２）。
【００８０】
図９を参照すると、データ登録フェイズにおいては、まず、登録データ生成装置１００の登録データ生成部１０１に、暗号化鍵と、秘匿対象となる入力データとが入力される（ステップＢ１）。
【００８１】
次に、登録データ生成部１０１は、入力データと、暗号化鍵とから、登録データを生成し、記憶装置２００へ送付し、入力データを登録したことをデータ照合要求装置３００に送付する（ステップＢ２）。
【００８２】
次に、登録データを受信した記憶装置２００の識別子管理部２０１は、登録データを入力とし、データごとに異なる識別子を生成し、登録データを暗号文記憶部２０２に、識別子を識別子記憶部２０３にそれぞれ記憶する（ステップＢ３）。
【００８３】
このとき、登録データと、登録データに対して発行された識別子とが組であることが分かるように記憶されるものとする。また、暗号文記憶部と識別子記憶部を別の部として記載しているが、同じ記憶装置（例えばデータベース等）に記憶してもよい。
【００８４】
さらに、識別子管理部２０１は、データ照合要求装置３００に、識別子を送付する（ステップＢ４）。データ照合要求装置３００は、受信した識別子と入力データを識別子記憶部３０２に記憶する（ステップＢ５）。
【００８５】
図１０を参照すると、暗号文照合フェイズにおいては、データ照合要求装置３００のデータ照合要求生成部３０１に照合対象の入力データが入力される（ステップＣ１）。
【００８６】
次に、データ照合要求生成部３０１は、入力データに対応する識別子を識別子記憶部３０２から読み込む（ステップＣ２）。
【００８７】
次に、データ照合要求生成部３０１は、入力データと、識別子と、暗号化鍵とを入力として、照合データを生成し、データ照合判定装置４００に送付する（ステップＣ３）。
【００８８】
次に、データ照合判定装置４００のデータ取得部４０１は、照合データを入力とし、照合データに含まれる識別子に対応した登録データを、記憶装置２００の暗号文記憶部２０２から受信する（ステップＣ４）。
【００８９】
次に、距離計算部４０２は、照合データと、登録データと、暗号化鍵とを入力として、暗号化距離データを生成する（ステップＣ５）。
【００９０】
次に、補助要求部４０３は、暗号化距離データを入力とし、照合補助要求を生成し、照合補助装置５００に送付する（ステップＣ６）。
【００９１】
次に、照合補助装置５００の復号部５０２は、照合補助要求と、鍵記憶部５０４に記憶された復号鍵とを入力とし、距離データを生成する（ステップＣ７）。
【００９２】
次に、スコア計算部５０３は、距離データを入力とし、乱数を用いてスコアを生成し、データ照合判定装置４００に送付する（ステップＣ８）。
【００９３】
次に、データ照合判定装置４００の判定部４０４は、スコアを入力とし、照合結果を生成する（ステップＣ９）。
【００９４】
このように、本第１の実施形態では、復号サーバ３０Ｂとして働く照合補助装置５００からの出力がスコアとなることにより、認証サーバ２０Ｂとして働くデータ照合判定装置４００が認証結果を判断するために必要な情報を得ることができる。その理由は、復号後に、スコア生成のために適切な分布に従った乱数を利用するからである。また、毎回照合時に用いる乱数を変更することにより、前回より近くなったか遠くなったかの判定ができず、ヒルクライミング攻撃が不可能となる。
【００９５】
（第２の実施形態）
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。
【００９６】
本発明の第１の実施形態で説明した暗号文照合システムと、本発明の第２の実施形態で記載する暗号文照合システムとの差分は、次の通りである。すなわち、本発明の第１の実施形態では、照合要求時に識別子を指定し、その識別子に対応する登録データとの照合を行っていた、いわゆる１：１照合である。これに対して、本発明の第２の実施形態では、照合時に識別子を指定せず、登録された登録データの中にマッチするデータが存在するかを確認する１：Ｎ照合を行っている。
【００９７】
図１１を参照すると、本発明の第２の実施形態による暗号文照合システムは、登録データ生成装置６００と、記憶装置２００と、データ照合要求装置７００と、データ照合判定装置４００Ａと、照合補助装置５００と、から成る。
【００９８】
登録データ生成装置６００およびデータ照合要求装置３００を利用するエンティティが、図３のクライアント１０に相当する。記憶装置２００を有し、データ照合判定装置７００を利用するエンティティが、図３の認証サーバ２０Ｂに相当する。そして、照合補助装置５００を利用するエンティティが、図３の復号サーバ３０Ｂに相当する。
【００９９】
換言すれば、登録データ生成装置６００は第１のクライアントとして実現され、データ照合要求装置７００は第２のクライアントとして実現される。記憶装置２００とデータ照合判定装置４００との組み合わせは認証サーバ２０Ｂとして動作する。照合補助装置５００は復号サーバ３０Ｂとして動作する。第１のクライアントと第２のクライアントとは、別々のクライアントであっても良いし、同じ１つのクライアントであって良い。
【０１００】
［構成の説明］
図１２を参照すると、登録データ生成装置６００は、登録データ生成部６０１から成る。登録データ生成部６０１は、秘匿対象となる入力データと、照合補助装置５００の鍵生成部５０１が生成した暗号化鍵とを入力とし、登録データを出力する。
【０１０１】
記憶装置２００は、上述した本発明の第１の実施形態の記憶装置２００と同じであるため、説明を省略する。
【０１０２】
図１３を参照すると、データ照合要求装置７００は、データ照合要求生成部７０１から成る。データ照合要求生成部７００は、照合補助装置５００の鍵生成部５０１が生成した暗号化鍵と、照合対象の入力データとを入力とし、照合データを出力する。
【０１０３】
図１４を参照すると、データ照合判定装置４００Ａは、データ取得部４０１Ａと、距離計算部４０２と、補助要求部４０３と、判定部４０４とから成る。
【０１０４】
データ取得部４０１Ａは、記憶装置２００の暗号文記憶部２０２に記憶されている登録データをすべて取得する。
【０１０５】
距離計算部４０２は、取得した登録データと、照合データと、暗号化鍵とを入力とし、暗号化距離データを出力する。
【０１０６】
補助要求部４０３は、暗号化距離データを入力とし、照合補助装置５００に補助要求データを出力する。
【０１０７】
判定部４０４は、照合補助装置５００から受信したスコアを入力とし、照合結果を出力する。
【０１０８】
照合補助装置５００は、上述した本発明の第１の実施形態の照合補助装置５００と同じであるため、説明を省略する。
【０１０９】
［動作の説明］ 
次に、本発明の第２の実施形態の暗号文照合システムの動作に関して詳細に説明する。
【０１１０】
本発明の第２の実施形態の暗号文照合システムの動作は、セットアップフェイズと、データ登録フェイズと、暗号文照合フェイズと、の３つのフェイズに大別される。
【０１１１】
ここで、データ登録フェイズは、登録データ生成装置６００に入力データを入力し、入力データを暗号化し、記憶装置２００に登録するフェイズである。暗号文照合フェイズは、データ照合要求装置７００に入力された入力データを暗号化し、その際に生成された照合要求が、データ照合判定装置４００Ａによって記憶装置内の暗号データと近い（ユークリッド距離の小さい）平文となるものであるかを判定するフェイズである。以下、各フェイズにおける動作に関して詳細に説明する。
【０１１２】
図１５を参照すると、セットアップフェイズにおいては、まず、照合補助装置５００の鍵生成部５０１にセキュリティパラメータが入力され、暗号化鍵および  復号鍵が生成される（ステップＤ１）。
【０１１３】
次に、鍵生成部５０１は、生成した暗号化鍵を登録データ生成装置６００と、照合要求装置７００と、データ照合判定装置４００Ａとに送付し、復号鍵を鍵記憶部５０３に記憶する（ステップＤ２）。
【０１１４】
図１６を参照すると、データ登録フェイズにおいては、まず、登録データ生成装置６００の登録データ生成部６０１に、暗号化鍵と、秘匿対象となる入力データが入力される（ステップＥ１）。
【０１１５】
次に、登録データ生成部６０１は、入力データと、暗号化鍵とから、登録データを生成し、記憶装置２００へ送付する（ステップＥ２）。
【０１１６】
次に、登録データを受信した記憶装置２００の識別子管理部２０１は、登録データを入力とし、データごとに異なる識別子を生成し、登録データを暗号文記憶部２０２に、識別子を識別子記憶部２０３にそれぞれ記憶する（ステップＥ３）。
【０１１７】
このとき、登録データと、登録データに対して発行された識別子とが組であることが分かるように記憶されるものとする。また、暗号文記憶部と識別子記憶部とを別の部として記載しているが、同じ記憶装置（例えばデータベース等）に記憶してもよい。
【０１１８】
図１７を参照すると、暗号文照合フェイズにおいては、データ照合要求装置７００に照合対象の入力データが入力される（ステップＦ１）。
【０１１９】
次に、データ照合要求生成部７０１は、入力データと、暗号化鍵とを入力として、照合データを生成し、データ照合判定装置４００Ａに送付する（ステップＦ２）。
【０１２０】
次に、データ照合判定装置４００Ａのデータ取得部４０１Ａは、記憶装置２００の暗号文記憶部２０２から登録データをすべて受信する（ステップＦ３）。
【０１２１】
次に、距離計算部４０２は、照合データと、登録データと、暗号化鍵とを入力として、暗号化距離データを生成する（ステップＦ４）。
【０１２２】
次に、補助要求部４０３は、暗号化距離データを入力とし、照合補助要求を生成し、照合補助装置５００に送付する（ステップＦ５）。
【０１２３】
次に、照合補助装置５００の復号部５０２は、照合補助要求と、鍵記憶部５０４に記憶された復号鍵とを入力とし、距離データを生成する（ステップＦ６）。
【０１２４】
次に、スコア計算部５０３は、距離データを入力とし、乱数を用いてスコアを生成し、データ照合判定装置４００Ａに送付する（ステップＦ７）。
【０１２５】
次に、データ照合判定装置４００Ａの判定部４０４は、スコアを入力とし、照合結果を生成する（ステップＦ８）。
【０１２６】
このように、本第２の実施形態では、復号サーバ３０Ｂとして働く照合補助装置５００からの出力がスコアとなることにより、認証サーバ２０Ｂとして働くデータ照合判定装置４００Ａが認証結果を判断するために必要な情報を得ることができる。その理由は、復号後に、スコア生成のために適切な分布に従った乱数を利用するからである。また、毎回照合時に用いる乱数を変更することにより、前回より近くなったか遠くなったかの判定ができず、ヒルクライミング攻撃が不可能となる。
【実施例１】
【０１２７】
次に、本発明の第１の実施例について詳細に説明する。本第１の実施例は、本発明の第１の実施形態の実施例である。
【０１２８】
説明のために、まず、本第１の実施例で用いる「公開鍵暗号」について説明する。本第１の実施例では、公開鍵暗号として、Boneh-Goh-Nissim 暗号（BGN暗号）を利用する。BGN暗号は、somewhat 準同型暗号である。すなわち、暗号化したまま１回の乗算、複数回の加算を計算できる公開鍵暗号である。
【０１２９】
公開鍵暗号（BGN暗号）は、（鍵生成、暗号化、復号）の３つのアルゴリズムから構成される。以下にそれぞれを説明する。
【０１３０】
鍵生成アルゴリズムGen(k)は、セキュリティパラメータkを入力として、k/2ビットのランダムな素数q, rを選ぶ。n=qrとする。次に、鍵生成アルゴリズムGen(k)は、位数nの点Pを持つsupersinglar 楕円曲線 E/F_p を用意し、Pで生成される群をGとする。鍵生成アルゴリズムGen(k)は、群Gから無限遠点を除いた群からランダムにQ’を選び、Q=[r]Q’とする。（このときQは位数qである。）鍵生成アルゴリズムGen(k)は、e:G×G→μをペアリング関数とする。鍵生成アルゴリズムGen(k)は、公開鍵pk=(E, e, n, P, Q)と秘密鍵sk=qを出力する。
【０１３１】
暗号化アルゴリズムENC(pk, M)は、ランダムにtを[1,n]から選び、C=[m]P+[t]Qを計算する。暗号化アルゴリズムENC(pk, M)は、暗号文Cを出力する。
【０１３２】
復号アルゴリズムDEC(sk, D)は、P’=[q]PとC’=[q]Cを計算する。復号アルゴリズムDEC(sk, D)は、M’=log_{P’}C’を計算する。復号アルゴリズムDEC(sk, D)は、平文M’を出力する。
【０１３３】
尚、加算 ADD(pk, C1, C2)は、C’=C1+C2を計算して、暗号文C’を出力する。
【０１３４】
乗算 MULT(pk, C1, C2)は、D=e(C1, C2)を計算して、暗号文Dを出力する。
【０１３５】
乗算後の復号 DEC’(sk, D)は、g=e(P, P)とし、g’=g^{q}とD’=D^{q}を計算し、M’=log_{g’}D’を計算して、平文M’を出力する。
【０１３６】
乗算後の加算 ADD’(pk, D1, D2)は、D’=D1・D2を計算して、暗号文D’を出力する。
【０１３７】
BGN暗号は選択平文攻撃を行う攻撃者に対して識別不可能性を満たすことが数学的に証明可能な方式である。本第１の実施例では、BGN暗号を例として説明を行うが、他のsomewhat 準同型暗号を用いても構わない。また、本第１の実施例では、登録データおよび照合要求データをいずれも秘匿したまま照合を行う方法について説明するが、いずれか一方だけが秘匿される形態に容易に変換できる。その際は、somewhat 準同型暗号の代わりに、一般の準同型暗号、例えばPaillier暗号やElgamal暗号などを適用できる。
【０１３８】
本発明の第１の実施例の暗号文照合システムの動作は、セットアップフェイズと、データ登録フェイズと、暗号文照合フェイズと、の３つのフェイズに大別される。
【０１３９】
図１８を参照して、セットアップフェイズにおいては、まず、照合補助装置５００の鍵生成部５０１にセキュリティパラメータkが入力され、鍵生成部５０１は、鍵生成アルゴリズムGEN(k)を実行し、暗号化鍵（公開鍵）pkおよび復号鍵（秘密鍵）skを生成する（ステップＡ１）。
【０１４０】
次に、鍵生成部５０１は、生成した暗号化鍵pkを登録データ生成装置１００と、照合要求装置３００と、データ照合判定装置４００とに送付し、復号鍵skを鍵記憶部５０３に記憶する（ステップＡ２）。
【０１４１】
図１９を参照して、データ登録フェイズにおいては、まず、登録データ生成装置１００の登録データ生成部１０１に、暗号化鍵pkと、秘匿対象となる入力データZが入力される（ステップＢ１）。
【０１４２】
次に、登録データ生成部１０１は、入力データZと、暗号化鍵pkから、暗号化アルゴリズムENC(pk, Z)を行い、登録データPTを生成し、記憶装置２００へ送付し、入力データZを登録したことをデータ照合要求装置３００に送付する（ステップＢ２）。
【０１４３】
次に、登録データPTを受信した記憶装置２００の識別子管理部２０１は、登録データPTを入力とし、データごとに異なる識別子IDを生成し、登録データPTを暗号文記憶部２０２に、識別子IDを識別子記憶部２０３にそれぞれ記憶する（ステップＢ３）。
【０１４４】
このとき、登録データPTと、登録データに対して発行された識別子IDとが組であることが分かるように記憶されるものとする。また、暗号文記憶部と識別子記憶部とを別の部として記載しているが、同じ記憶装置（例えばデータベース等）に記憶してもよい。
【０１４５】
さらに、識別子管理部２０１は、データ照合要求装置３００に、識別子を送付する（ステップＢ４）。
【０１４６】
データ照合要求装置３００は、受信した識別子と入力データを識別子記憶部３０２に記憶する（ステップＢ５）。
【０１４７】
図２０を参照して、暗号文照合フェイズにおいては、データ照合要求装置３００に照合対象の入力データZ’が入力される（ステップＣ１）。
【０１４８】
次に、データ照合要求生成部３０１は、入力データZ’に対応する識別子ID’を識別子記憶部３０２から読み込む（ステップＣ２）。
【０１４９】
次に、データ照合要求生成部３０１は、入力データZ’と、識別子ID’と、暗号化鍵pkを入力として、暗号化アルゴリズムENC(pk, Z’)を行い、暗号文C’を生成する。そして、データ照合要求生成部３０１は、照合データ(ID’, C’)を生成し、データ照合判定装置４００に送付する（ステップＣ３）。
【０１５０】
次に、データ照合判定装置４００のデータ取得部４０１は、照合データ(ID’, C’)を入力とし、照合データに含まれる識別子ID’に対応した登録データPT’を、記憶装置２００の暗号文記憶部２０２から受信する（ステップＣ４）。
【０１５１】
次に、距離計算部４０２は、照合データ(ID’, C’)と、登録データPT’と、暗号化鍵pkとを入力として、まずADD(pk, C, C’^{-1})を計算し、暗号文C-C’を生成する。ここでC’^{-1}はC’の逆元を意味する。次に、距離計算部４０２は、MULT(pk, C-C’, C-C’)を計算し、暗号文Dを生成する。そして、距離計算部４０２は、暗号文Dを暗号化距離データとする（ステップＣ５）。
【０１５２】
次に、補助要求部４０３は、暗号化距離データDを入力とし、照合補助要求(D)を生成し、照合補助装置５００に送付する（ステップＣ６）。
【０１５３】
次に、照合補助装置５００の復号部５０２は、照合補助要求(D)と、鍵記憶部５０４に記憶された復号鍵skとを入力とし、復号アルゴリズムDEC’(sk, D)を行い、復号結果dを得る。復号部５０２は、復号結果dを距離データとする（ステップＣ７）。
【０１５４】
次に、スコア計算部５０３は、距離データdを入力とし、距離データdがあらかじめ決められた値tよりも小さければ、乱数rを選択し、スコアsc=d+rを生成し、データ照合判定装置４００に送付する。一方、距離データdがあらかじめ決められた値tよりも大きな値ならば、スコア計算部５０３は、スコアsc=0として、データ照合判定装置４００に送付する（ステップＣ８）。
【０１５５】
次に、データ照合判定装置４００の判定部４０４は、スコアscを入力とし、sc≠0ならば受理を、そうでなければ不受理を照合結果とし、照合結果を生成する（ステップＣ９）。
【０１５６】
このように、第１の実施例では、復号サーバ３０Ｂとして働く照合補助装置５００からの出力がスコアscとなることにより、認証サーバ２０Ｂとして働くデータ照合判定装置４００が認証結果（照合結果）を判断するために必要な情報を得ることができる。その理由は、復号後に、スコア生成のために適切な分布に従った乱数を利用するからである。また、毎回照合時に用いる乱数を変更することにより、前回より近くなったか遠くなったかの判定ができず、ヒルクライミング攻撃が不可能となる。
【実施例２】
【０１５７】
次に、本発明の第２の実施例について詳細に説明する。本第２の実施例は、本発明の第２の実施形態の実施例である。
【０１５８】
本発明の第３の暗号文照合システムの動作は、セットアップフェイズと、データ登録フェイズと、暗号文照合フェイズと、の３つのフェイズに大別される。
【０１５９】
ここで、データ登録フェイズは、登録データ生成装置６００に入力データを入力し、入力データを暗号化し、記憶装置２００に登録するフェイズである。暗号文照合フェイズは、データ照合要求装置７００に入力された入力データを暗号化し、その際に生成された照合要求が、データ照合判定装置４００Ａによって記憶装置内の暗号データ（登録データ）と近い（ユークリッド距離の小さい）平文となるものであるかを判定するフェイズである。以下、各フェイズにおける動作に関して詳細に説明する。
【０１６０】
図２１を参照して、セットアップフェイズにおいては、まず、照合補助装置５００の鍵生成部５０１にセキュリティパラメータkが入力され、鍵生成部５０１は、鍵生成アルゴリズムGen(k)を行い、暗号化鍵pkおよび復号鍵skを生成する（ステップＤ１）。
【０１６１】
次に、鍵生成部５０１は、生成した暗号化鍵pkを登録データ生成装置６００と、データ照合要求装置７００と、データ照合判定装置４００Ａとに送付し、復号鍵skを鍵記憶部５０３に記憶する（ステップＤ２）。
【０１６２】
図２２を参照して、データ登録フェイズにおいては、まず、登録データ生成装置６００の登録データ生成部６０１に、暗号化鍵pkと、秘匿対象となる入力データZが入力される（ステップＥ１）。
【０１６３】
次に、登録データ生成部６０１は、入力データZと、暗号化鍵pkから、暗号化アルゴリズムENC(pk, Z)を行い、暗号文Cを生成する。登録データ生成部６０１は、登録データPT=Cとし、記憶装置２００へ送付する（ステップＥ２）。
【０１６４】
次に、登録データPTを受信した記憶装置２００の識別子管理部２０１は、登録データPTを入力とし、データごとに異なる識別子IDを生成し、登録データPTを暗号文記憶部２０２に、識別子IDを識別子記憶部２０３にそれぞれ記憶する（ステップＥ３）。
【０１６５】
このとき、登録データPTと、登録データPTに対して発行された識別子IDとが組であることが分かるように記憶されるものとする。また、暗号文記憶部と識別子記憶部とを別の部として記載しているが、同じ記憶装置（例えばデータベース等）に記憶してもよい。
【０１６６】
図２３を参照して、暗号文照合フェイズにおいては、データ照合要求装置７００に照合対象の入力データZ’が入力される（ステップＦ１）。
【０１６７】
次に、データ照合要求生成部７０１は、入力データZ’と、暗号化鍵pkを入力として、暗号化アルゴリズムENC(pk, Z’)を実行し、暗号文C’を生成する。登録データ生成部６０１は、照合データQD=C’とし、データ照合判定装置４００Ａに送付する（ステップＦ２）。
【０１６８】
次に、データ照合判定装置４００Ａのデータ取得部４０１Ａは、記憶装置２００の暗号文記憶部２０２から登録データ{PT}をすべて受信する（ステップＦ３）。
【０１６９】
次に、{PT}に含まれるPTすべてに対して、距離計算部４０２は、照合データQDと、登録データPTと、暗号化鍵pkとを入力として、まず、加算ADD(pk, PT, QD^{-1})=ENC(pk, Z-Z’)=C”を計算する。次に、距離計算部４０２は、乗算MULT(pk, C”, C”)=ENC(pk, (Z-Z’)^2)=Dを計算する。そして、距離計算部４０２は、全PTに対するDの集合を{D}とし、{D}を暗号化距離データとする（ステップＦ４）。
【０１７０】
次に、補助要求部４０３は、暗号化距離データ｛D｝を入力とし、照合補助要求｛D｝を生成し、照合補助装置５００に送付する（ステップＦ５）。
【０１７１】
次に、照合補助装置５００の復号部５０２は、照合補助要求{D}と、鍵記憶部５０４に記憶された復号鍵skとを入力とし、{D}に含まれるすべてのDに対して、距離データdを生成する（ステップＦ６）。
【０１７２】
次に、スコア計算部５０３は、すべての距離データ{d}を入力とし、あらかじめ決められた閾値tよりも小さいdのリスト{d1,…,dm}を生成する。ここで簡単のため、d1，…，dmは昇順すなわち、d1≦d2≦…≦dmを満たすことにする。次に、スコア計算部５０３は、ランダムにr1，…，rmを選ぶ。ｒ1，…，ｒmは昇順すなわち、r1≦r2≦…≦rmを満たす。ただし、あるdi=djのとき、ri=rjであるように選ぶ。そして、スコア計算部５０３は、スコアを{r1，．．．，rm}とし、データ照合判定装置４００に送付する（ステップＦ７）。
【０１７３】
次に、データ照合判定装置４００Ａの判定部４０４は、スコアを入力{r1，．．．，rm}とし、照合結果を生成する（ステップＦ８）。照合結果は例えば、スコアの一番小さいr1に対応するID１を識別子記憶部２０３から受信し、ID1を受理とする。あるいは閾値を下回ったすべてのIDを受理としてもよい。その他、アプリケーションによって受理の判断方法は複数考えられるが、いずれの判断方法にも適用可能である。
【０１７４】
また、本第２の実施例では、スコアを距離の順序を保つようにランダムに選んでいるが、例えばアプリケーションによっては、距離の差を保存したい場合も考えられる。例えば、１位と２位の差が有意に（２位と３位，３位と４位などと比較して大きく）離れているか、などが照合結果を判断する方法になりうる。この場合は、上記方法の代わりに、d2-d1，d3-d2，…，dm-dm-1に対してm-1個の乱数を割り当てることで適用可能である。
【０１７５】
このように、本第２の実施例では、照合時に復号サーバ３０Ａ（照合補助装置５００）により計算された距離を、適切な分布に従って選ばれた乱数値に置き換え、スコアを生成することにより、例えば1位と2位が有意に差があるかを認証サーバ２０Ｂ（データ照合判定装置４００Ａ）が判定可能となる。また、毎回照合時に用いる乱数を変更することにより、前回より近くなったか遠くなったかの判定ができず、ヒルクライミング攻撃が不可能となる。
【０１７６】
なお、本発明に記載した方法は、コンピュータに実行させることのできるプログラムとして、フレキシブルディスク、ハードディスクなどの磁気ディスク、ＣＤ-ＲＯＭ（compact disc read only memory）、ＤＶＤ（digital versatile disc）などの光ディスク、光磁気ディスク（ＭＯ(magneto-optical disc)）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１７７】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。
【０１７８】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト等のミドルウェアなどが各処理の一部を実行してもよい。
【０１７９】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネットなどにより伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１８０】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であってもよい。
【０１８１】
本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき各処理を実行するものであって、パソコンなどからなる装置、複数の装置がネットワーク接続されたシステムなどの何れの構成であってもよい。
【０１８２】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置を含み、プログラムによって本発明の機能を実現することが可能な機器、装置である。
【０１８３】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。また、構成要素を適宜組合せてもよい。
【０１８４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１８５】
（付記１）
暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを出力する登録データ生成部と、
該登録データを暗号文記憶部に、当該登録データを一意に特定するための識別子を識別子記憶部に、それぞれ対応が分かるように記憶する記憶装置と、
前記暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを出力するデータ照合要求生成部と、
前記登録データと前記照合データとから前記暗号化鍵を用いて、暗号化距離データを出力する距離計算部と、
復号鍵を用いて前記暗号化距離データを復号して、距離データを生成する復号部と、
前記距離データから乱数を用いてスコアを生成するスコア計算部と、
前記スコアから照合結果を出力する判定部と、
を含む、暗号文照合システム。
【０１８６】
（付記２）
前記スコア計算部は、
前記距離データと予め決められた値とを比較する手段と、
前記距離データが前記予め決められた値よりも小さければ、前記乱数を選択して、前記距離データと前記乱数とを加算した値を、前記スコアとして生成する手段と、
前記距離データが前記予め決められた値よりも大きければ、ゼロを前記スコアとして生成する手段と、
を有する、付記１に記載の暗号文照合システム。
【０１８７】
（付記３）
セキュリティパラメータから、前記暗号化鍵と前記復号鍵とを生成する鍵生成部を更に含む、付記１又は２に記載の暗号文照合システム。
【０１８８】
（付記４）
前記鍵生成部は、前記暗号化鍵および前記復号鍵として、それぞれ、準同型暗号あるいはSomewhat準同型暗号の公開鍵および秘密鍵を生成する付記３に記載の暗号文照合システム。
【０１８９】
（付記５）
付記１乃至４のいずれか１項に記載の暗号文照合システムを備え、前記秘匿対象となる入力データおよび前記照合対象の入力データが生体情報であり、前記秘匿対象となる入力データと前記照合対象の入力データとが類似している否かを判定することによって生体認証を行うことを特徴とする生体認証システム。
【０１９０】
（付記６）
第１のクライアントが、暗号化鍵を用いて秘匿対象となる入力データを暗号化して登録データを生成し、認証サーバが、該登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶するデータ登録ステップと、
第２のクライアントが、前記暗号化鍵を用いて照合対象の入力データを暗号化して照合データを生成し、前記認証サーバが、前記記憶部に記憶された前記登録データと前記照合データとから、前記暗号化鍵を用いて暗号化距離データを生成し、復号サーバが、復号鍵を用いて前記暗号化距離データを復号して距離データを生成し、該距離データから乱数を用いてスコアを生成し、前記認証サーバが、前記スコアから照合結果を生成する、暗号文照合ステップと、
を含む、暗号文照合方法。
【０１９１】
（付記７）
第１のクライアントが、暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを生成する登録データ生成ステップと、
認証サーバが、該登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶するステップと、
第２のクライアントが、前記暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを生成するデータ照合要求生成ステップと、
前記認証サーバが、前記記憶部に記憶された前記登録データと前記照合データとから、前記暗号化鍵を用いて暗号化距離データを生成する距離計算ステップと、
復号サーバが、復号鍵を用いて前記暗号化距離データを復号して、距離データを生成する復号ステップと、
前記復号サーバが、前記距離データから乱数を用いてスコアを計算するスコア計算ステップと、
前記認証サーバが、前記スコアから照合結果を生成する判定ステップと、
を含む、暗号文照合方法。
【０１９２】
（付記８）
暗号化鍵を用いて秘匿対象となる入力データを暗号化して、登録データを生成する登録データ生成処理と、
該登録データを、当該登録データを一意に特定するための識別子とともに記憶部に記憶する処理と、
前記暗号化鍵を用いて照合対象の入力データを暗号化して、照合データを生成するデータ照合要求生成処理と、
前記記憶部に記憶された前記登録データと前記照合データとから、前記暗号化鍵を用いて暗号化距離データを生成する距離計算処理と、
復号鍵を用いて前記暗号化距離データを復号して、距離データを生成する復号処理と、
前記距離データから乱数を用いてスコアを計算するスコア計算処理と、
前記スコアから照合結果を生成する判定処理と、
をコンピュータに実行させる、暗号文照合プログラム。
【０１９３】
（付記９）
セキュリティパラメータから、暗号化鍵と復号鍵とを生成する鍵生成部と、
前記復号鍵を用いて暗号化距離データを復号して、距離データを生成する復号部と、
前記距離データから乱数を用いてスコアを計算するスコア計算部と、
を有する照合補助装置。
【０１９４】
（付記１０）
付記９に記載の照合補助装置で生成された暗号化鍵を用いて、秘匿対象となる入力データを暗号化して、登録データを生成する登録データ生成部を有する登録データ生成装置。
【０１９５】
（付記１１）
付記１０に記載の登録データ生成装置で生成された前記登録データを入力として、前記登録データを一意に特定する識別子を管理する識別子管理部と、
前記登録データを記憶する暗号文記憶部と、
前記識別子を記憶する識別子記憶部と、
を有する記憶装置。
【０１９６】
（付記１２）
付記１１に記載の記憶装置に記憶されている前記識別子を記憶する識別子記憶部と、
照合対象の入力データに対応する識別子を前記識別子記憶部から読み込み、付記９に記載の照合補助装置で生成された暗号化鍵を用いて、前記照合対象の入力データを暗号化して、前記識別子を含む照合データを生成するデータ照合要求生成部と、
を有するデータ照合要求装置。
【０１９７】
（付記１３）
付記１２に記載のデータ照合要求装置から受信した照合データに含まれる識別子に対応する登録データを、付記１１に記載の記憶装置の前記暗号文記憶部から取得するデータ取得部と、
前記登録データと前記照合データとから、付記９に記載の照合補助装置で生成された暗号化鍵を用いて、暗号化距離データを計算する距離計算部と、
前記暗号化距離データを補助要求データとして、付記９に記載の照合補助装置へ送出する補助要求部と、
付記９に記載の照合補助装置から受信したスコアから照合結果を出力する判定部と、
を有するデータ照合判定装置。
【０１９８】
（付記１４）
付記９に記載の照合補助装置で生成された暗号化鍵を用いて、照合対象の入力データを暗号化して、照合データを生成するデータ照合要求生成部を有するデータ照合要求装置。
【０１９９】
（付記１５）
付記１１に記載の記憶装置の前記暗号文記憶部に記憶されている登録データの全てを取得するデータ取得部と、
前記登録データと前記照合データとから、付記９に記載の照合補助装置で生成された暗号化鍵を用いて、暗号化距離データを計算する距離計算部と、
前記暗号化距離データを補助要求データとして、付記９に記載の照合補助装置へ送出する補助要求部と、
付記９に記載の照合補助装置から受信したスコアから照合結果を出力する判定部と、
を有するデータ照合判定装置。
【０２００】
（付記１６）
登録データ生成装置と、記憶装置と、データ照合要求装置と、データ照合判定装置と、照合補助装置とを備える暗号文照合システムであって、
前記登録データ生成装置は、秘匿対象となる入力データを、暗号化鍵を用いて暗号化して、登録データを出力する登録データ生成部を備え、
前記記憶装置は、前記登録データ生成部が生成した登録データを入力として受け取り、データごとに異なる識別子を生成し、前記登録データを暗号文記憶部に、対応する識別子を識別子記憶部に、それぞれ対応が分かるように記憶する識別子管理部を備え、
前記データ照合要求装置は、前記暗号化鍵と、識別子記憶部に記憶された識別子と、照合対象の入力データとを入力とし、照合データを出力するデータ照合要求生成部を備え、
前記データ照合判定装置は、
前記照合データに含まれる識別子に対応する登録データを、前記記憶装置の暗号文記憶部から取得するデータ取得部と、
取得した登録データと、前記照合データと、前記暗号化鍵とを入力とし、暗号化距離データを出力する距離計算部と、
前記暗号化距離データを入力とし、前記照合補助装置に補助要求データを出力する補助要求部と、
前記照合補助装置から受信したスコアを入力とし、照合結果を出力する判定部と、を備え、
前記照合補助装置は、
セキュリティパラメータを入力とし、前記暗号化鍵および復号鍵を出力する鍵生成部と、
前記データ照合判定装置から受信した補助要求データと、前記復号鍵とを入力とし、距離データを生成する復号部と、
前記距離データを入力とし、乱数を用いて前記スコアを出力するスコア計算部と、を備える
ことを特徴とする暗号文照合システム。
【０２０１】
（付記１７）
付記１６に記載の暗号文照合システムであって、
前記照合補助装置の前記鍵生成部は、準同型暗号あるいはSomewhat準同型暗号の暗号化鍵および復号鍵を生成し、
前記登録データ生成装置の前記登録データ生成部は、前記暗号化鍵を用いて前記登録データを生成し、
前記データ照合要求装置の前記データ照合要求生成部は、前記暗号化鍵を用いて前記照合データを生成し、
前記照合補助装置の前記復号部は、前記復号鍵を用いて前記距離データを生成する
ことを特徴とする暗号文照合システム。
【０２０２】
（付記１８）
登録データ生成装置と、記憶装置と、データ照合要求装置と、データ照合判定装置と、照合補助装置とを備える暗号文照合システムであって、
前記登録データ生成装置は、秘匿対象となる入力データと、暗号化鍵とを入力とし、登録データを出力する登録データ生成部を備え、
前記記憶装置は、前記登録データ生成部が生成した登録データを入力として受け取り、データごとに異なる識別子を生成し、前記登録データを暗号文記憶部に、対応する識別子を識別子記憶部に、それぞれ対応が分かるように記憶する識別子管理部を備え、
前記データ照合要求装置は、前記暗号化鍵と、照合対象データとを入力とし、照合データを出力するデータ照合要求生成部を備え、
前記データ照合判定装置は、
前記記憶装置の前記暗号文記憶部に記憶されている登録データをすべて取得するデータ取得部と、
取得した登録データと、前記照合データと、前記暗号化鍵とを入力とし、暗号化距離データを出力する距離計算部と、
前記暗号化距離データを入力とし、前記照合補助装置に補助要求データを出力する補助要求部と、
前記照合補助装置から受信したスコアを入力とし、照合結果を出力する判定部と、を備え、
前記照合補助装置は、
セキュリティパラメータを入力とし、前記暗号化鍵および復号鍵を出力する鍵生成部と、
前記データ照合判定装置から受信した補助要求データと、前記復号鍵とを入力とし、距離データを生成する復号部と、
前記距離データを入力とし、乱数を用いて前記スコアを出力するスコア計算部と、を備える
ことを特徴とする暗号文照合システム。
【０２０３】
（付記１９）
付記１８に記載の暗号文照合システムであって、
前記照合補助装置の前記鍵生成部は、準同型暗号あるいはSomewhat準同型暗号の暗号化鍵および復号鍵を生成し、
前記登録データ生成装置の前記登録データ生成部は、前記暗号化鍵を用いて前記登録データを生成し、
前記データ照合要求装置の前記データ照合要求生成部は、前記暗号化鍵を用いて前記照合データを生成し、
前記照合補助装置の前記復号部は、前記復号鍵を用いて前記距離データを生成する
ことを特徴とする暗号文照合システム。
【産業上の利用可能性】
【０２０４】
本発明の活用例として、生体情報を保護した認証が挙げられる。データ登録フェイズにおける入力データと、暗号文照合フェイズにおける入力データを、指紋や静脈などから取得した生体情報とする。このことで、登録時に使用したデータZと照合時に使用したデータZ’との間の距離に関するスコアを出力しても、データに関する情報が漏れない、照合元データと照合対象データに多少の誤差を許した認証を行うことが可能となる。生体情報は、常に安定して同一のデータが取得できるわけではないが、同じ人物から取得されるデータが類似している（ユークリッド距離が小さいデータが取得できる）と仮定できるため、本発明の生体認証への活用は産業上有用であると考えられる。
【符号の説明】
【０２０５】
１０    クライアント
２０Ｂ    認証サーバ
３０Ｂ    復号サーバ
１００    登録データ生成装置
１０１    登録データ生成部
２００    記憶装置
２０１    識別子管理部
２０２    暗号文記憶部
２０３    識別子記憶部
３０１    データ照合要求生成部
３０２    識別子記憶部
４００    データ照合判定装置
４００Ａ    データ照合判定装置
４０１    データ取得部
４０１Ａ    データ取得部
４０２    距離計算部
４０３    補助要求部
４０４    判定部
５００    照合補助装置
５０１    鍵生成部
５０２    復号部
５０３    スコア計算部
５０４    鍵記憶部
６００    登録データ生成装置
６０１    登録データ生成部
７００    データ照合要求装置
７０１    データ照合要求生成部
【図１】
0006451938.tif 000002
【図２】
0006451938.tif 000003
【図３】
0006451938.tif 000004
【図４】
0006451938.tif 000005
【図５】
0006451938.tif 000006
【図６】
0006451938.tif 000007
【図７】
0006451938.tif 000008
【図８】
0006451938.tif 000009
【図９】
0006451938.tif 000010
【図１０】
0006451938.tif 000011
【図１１】
0006451938.tif 000012
【図１２】
0006451938.tif 000013
【図１３】
0006451938.tif 000014
【図１４】
0006451938.tif 000015
【図１５】
0006451938.tif 000016
【図１６】
0006451938.tif 000017
【図１７】
0006451938.tif 000018
【図１８】
0006451938.tif 000019
【図１９】
0006451938.tif 000020
【図２０】
0006451938.tif 000021
【図２１】
0006451938.tif 000022
【図２２】
0006451938.tif 000023
【図２３】
0006451938.tif 000024