(57)【要約】  第２のノードが公開鍵と秘密鍵の対を生成し、公開鍵を第１のノードに送信し、第１のノードが公開鍵により認証データを暗号化して第３のノードに送信する工程と、第３のノードが暗号化された認証データを保持し第１のノードが、認証データと照合される被認証データを受信すると、暗号化された認証データを第３のノードから取得して、被認証データと認証データとの距離を公開鍵により暗号化したまま算出し、第３のノードが被認証データと認証データの距離の閾値をパラメータとして含む多項式を生成して第１のノードに送信し、第１のノードが、多項式に距離を代入して公開鍵により暗号化した値を、照合用データとして生成して第２のノードに送信し、第２のノードが、秘密鍵と照合用データに基づいて、被認証データを認証データと照合する。簡便な処理に基づいて被認証データおよび認証データをサーバに対して秘匿する。
2014185450.tif 000002
【特許請求の範囲】
【請求項１】
第１のノード、第２のノードおよび第３のノードを備え、
前記第１のノードは、公開鍵により認証データを暗号化して前記第３のノードに送信する暗号化部と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する距離計算部と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する照合用データ生成部と、を有し、
前記第２のノードは、前記公開鍵と秘密鍵の対を生成し、前記公開鍵を第１のノードに送信する鍵生成部と、
前記秘密鍵と前記照合用データに基づいて、前記被認証データを前記認証データと照合する照合部と、を有し、
前記第３のノードは、暗号化された前記認証データを保持する記憶部と、
前記多項式として、前記認証データと前記被認証データの距離の閾値をパラメータとして含む多項式を生成する照合用情報生成部と、を有する、照合システム。
【請求項２】
前記暗号化部は、加法準同型性を有する暗号化方式に基づいて暗号化を行う、請求項１に記載の照合システム。
【請求項３】
前記暗号化部は、Paillier暗号に基づいて暗号化を行う、請求項２に記載の照合システム。
【請求項４】
前記照合用情報生成部は、前記多項式として、独立変数と前記認証データの距離が前記閾値以内であるときにゼロとなる多項式を生成する、請求項１ないし３のいずれか１項に記載の照合システム。
【請求項５】
前記暗号化部は、さらに、前記公開鍵により前記認証データの２乗を暗号化して前記第３のノードに送信し、
前記記憶部は、さらに、暗号化された前記認証データの２乗を保持し、
前記距離計算部は、暗号化された前記認証データおよび暗号化された前記認証データの２乗を前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する、請求項２ないし４のいずれか１項に記載の照合システム。
【請求項６】
前記認証データおよび前記被認証データは、ｎ次元の要素を含み、
前記距離計算部は、前記被認証データと前記認証データとのｎ次元ユークリッド距離を、前記公開鍵により暗号化したまま算出する、請求項５に記載の照合システム。
【請求項７】
前記認証データおよび前記被認証データは、複数の要素を含み、
前記距離計算部は、各要素について前記距離を暗号化したまま算出し、
前記照合用情報生成部は、各要素について前記多項式を生成し、
前記照合用データ生成部は、各要素について前記照合用データを生成し、
前記照合部は、前記秘密鍵と前記複数の要素について生成された照合用データとを用いて、前記被認証データを前記認証データと照合する、請求項１ないし６のいずれか１項に記載の照合システム。
【請求項８】
公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する暗号化部と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する距離計算部と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する照合用データ生成部と、を備え、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む、ノード。
【請求項９】
第１のノードが、公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する工程と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する工程と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する工程と、を含み、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む、照合方法。
【請求項１０】
公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する処理と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する処理と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する処理と、を第１のノードに設けられたコンピュータに実行させ、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１３−１０２９５５号（２０１３年５月１５日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、照合システム、ノード、照合方法およびプログラムに関し、特に、照合されるデータの曖昧さを許容する照合システム、ノード、照合方法およびプログラムに関する。
【背景技術】
【０００２】
近年、クラウドの普及に伴い、ネットワークに接続された計算機資源に利用者のデータを蓄積し、蓄積されたデータを用いて提供されるサービスが急速に広がってきている。このようなサービスでは、利用者の機微なデータを扱う機会も増大してきている。したがって、利用者のデータが安全に管理されていることを保証することが重要になってきている。【０００３】
このような状況の下、オープンなネットワーク環境でデータを暗号化したまま管理し、データを復号することなく、検索、統計処理などを行う技術の研究開発が活発に行われている。【０００４】
また、近年、パスワードや磁気カードを用いた個人認証の脆弱性をついた犯罪が頻発しており、指紋、静脈などの生体的な特徴に基づくより安全性の高い生体認証技術が注目を集めている。【０００５】
生体認証においては、認証情報の検証を行うために、生体情報に関するテンプレートをデータベースに保管する必要がある。指紋、静脈などの生体情報は基本的に生涯不変のデータであり、情報が漏洩すると甚大な被害がもたらされるため、高い機密性が要求される。【０００６】
このため、テンプレートが漏洩しても「なりすまし」を行えないように、テンプレート情報を秘匿したまま認証を行うテンプレート保護型の生体認証技術が重要となってきている。【０００７】
例えば、特許文献１には、指紋データを多項式上の点として表現し、その点にランダムな点を付加して指紋データを秘匿したデータをテンプレートとして生体認証を行う方式が記載されている。【０００８】
また、非特許文献１には、凖同型性を有する公開鍵暗号を利用することにより、認証を求めているクライアントの生体情報を保護する方式が記載されている。【０００９】
さらに、特許文献２には、証明装置が公開鍵と乱数を用いて登録用の特徴ベクトルを暗号化し、登録用の暗号化特徴ベクトルを認証装置に登録し、認証時に、証明装置が認証用の特徴ベクトルを公開鍵と乱数を用いて暗号化し、認証装置が２つの暗号化特徴ベクトルが暗号化された状態のままで、秘密鍵を用いた復号処理により２つの特徴ベクトル間の類似度を導出可能な暗号化類似度情報を生成し、復号装置が暗号化類似度情報を復号して平文の類似度を導出し、類似度がしきい値以上であれば本人と判定するシステムが記載されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００６−１５８８５１号公報
【特許文献２】国際公開第２０１１／０５２０５６号
【非特許文献】
【００１１】
【非特許文献１】Siamak F. Shahandashti, Reihaneh Safavi-Naini, and Philip Ogunbona, "Private Fingerprint Matching," ACISP2012.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記の特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【００１３】
特許文献１の方式は、生体認証を何度も繰り返したとき、十分な強度で生体情報が保護されていないおそれがあることが知られている。【００１４】
一方、非特許文献１は、凖同型性を有する公開鍵暗号を利用することにより、認証を求めているクライアントの生体情報を保護する方式を提案している。【００１５】
生体情報を保護しない生体認証方式では、生体情報（例えば、指紋など）からマニューシャと呼ばれる特徴点を抽出し、マニューシャを認証用テンプレートとしてサーバに登録する。一般に、マニューシャは、タイプ、座標(x,y)、角度という３つの成分から成る。タイプは特徴点のタイプを表し、例えば、端点、分岐点などがある。座標は特徴点の座標を表し、角度は特徴点における接線の傾きを表す。【００１６】
サーバは、認証時において、クライアントの生体情報から抽出されたマニューシャと、認証用テンプレートとして登録されたマニューシャが一致することを確認する。（１）特徴点のタイプが一致し、（２）特徴点間の距離が閾値以内であり、（３）特徴点における接線の傾きの差が閾値以内である、という３条件が満たされたとき、マニューシャは一致したとみなされる。【００１７】
具体的には、認証時に抽出されたマニューシャを(type1,(x1,y1),θ1)とし、登録されたマニューシャを(type2,(x2,y2),θ2)としたとき、
（１）type1=type2
（２）0≦((x1-x2)^2+(y1-y2)^2)≦δd
（３）0≦(θ1-θ2)^2≦δt
の３条件が満たされたとき、２つのマニューシャが一致したとみなされる。【００１８】
ここで、δd、δtはシステムによって決められるパラメータである。また、（２）で評価される距離は、２次元ユークリッド距離、または、L2ノルムと呼ばれる。同様に、（３）で評価される距離は１次元ユークリッド距離と呼ばれる。以下では、これらをまとめてユークリッド距離と呼び、DとD’のユークリッド距離をd(D,D’)と表す。【００１９】
非特許文献１には、認証要求をしているクライアントの生体情報を秘匿できる生体認証方式が記載されている。具体的には、Aided ComputationおよびSet Intersectionと呼ばれる暗号プロトコルを利用することにより、認証時に抽出されたマニューシャ(type1,(x1,y1),θ1)をサーバに明かさずに、サーバに登録されたマニューシャ(type2,(x2,y2),θ2)とマニューシャ(type1,(x1,y1),θ1)とが一致するかどうかを確認することができる。【００２０】
以下では、クライアントからサーバに対して事前に登録されるデータを「認証データ」という。また、認証時に抽出され認証データとの照合が行われるデータを「被認証データ」という。上記の例では、マニューシャ(type2,(x2,y2),θ2)は認証データに相当し、マニューシャ(type1,(x1,y1),θ1)は被認証データに相当する。【００２１】
これらの暗号プロトコルを説明する準備として、公開鍵暗号について説明する。公開鍵暗号は、鍵生成、暗号化、復号の３つのアルゴリズムからなる。鍵生成はセキュリティパラメータを入力として受け取り、公開鍵pkと秘密鍵skを出力する確率的アルゴリズムである。暗号化は、公開鍵pkとメッセージMを入力として受け取り、暗号文Cを出力する確率的アルゴリズムである。復号は、秘密鍵skと暗号文Cを入力として受け取り、復号結果Mを出力する決定的アルゴリズムである。【００２２】
以下、鍵生成、暗号化、復号の各アルゴリズムを次のように記載する。
鍵生成：KeyGen(1^k)→(pk,sk)
暗号化：Enc(pk,M)→C
復号：Dec(sk,C)→M【００２３】
公開鍵暗号方式が凖同型性を有するとは、ある演算(*)、(+)に対して、以下の式が成立する場合をいう。
Enc(pk,M1(+)M2)=Enc(pk,M1)(*)Enc(pk,M2)【００２４】
例えば、Paillier暗号は、(*)を乗算、(+)を加算とした凖同型性を有する公開鍵暗号であることが知られている。次に、Paillier暗号について説明する。【００２５】
鍵生成：セキュリティパラメータ1^kを受け取る。
kビットの素数p,qをランダムに選び、n=pqとする。
次に、g=1+n mod n^2とする。
公開鍵pk=(n,g)、秘密鍵sk=(p,q)を出力する。【００２６】
暗号化：pk=(n,g)、メッセージmを入力として受け取る。
Z*_{n^2}からランダムにrを選ぶ。
C=(1+mn)・r^n mod n^2を計算する。
暗号文Cを出力する。【００２７】
復号：sk=(p,q)、暗号文Cを入力として受け取る。
λ=(p-1)(q-1)を計算する。
m=(c^{λ} mod n^2 -1)/(g^{λ} mod n^2 -1) mod nを計算する。
平文mを出力する。【００２８】
C1=Enc(pk,m1)=(1+m1 n)・r1^n mod n^2、C2=Enc(pk,m2)=(1+m2 n)・r2^n mod n^2とすると、C1×C2=(1+(m1+m2)n+m1・m2・n^2)・(r1r2)^n mod n^2=(1+(m1+m2)n)・(r1r2)^n mod n^2 =Enc(pk,m1+m2)となり、Paillier暗号は凖同型性を有する。このように、暗号化したまま平文の加算を行うことができる公開鍵暗号を、加法凖同型公開鍵暗号と呼ぶ。【００２９】
Set Intersection とは、２人のエンティティであるアリス（Alice）とボブ（Bob）の間で行われる暗号プロトコルである。アリスはあるデータaを持ち、ボブはデータの集合Bを持つものと仮定する。このとき、Set Intersectionはアリスの持つデータaをボブに秘匿したまま、データaが集合Bに含まれるかどうかを確認するプロトコルである。【００３０】
簡単のため、集合B={b1,b2,b3}としてSet Intersectionを説明する。また、ボブは加法凖同型公開鍵暗号の公開鍵pkを公開し、対応する秘密鍵skを保持しているものとする。【００３１】
１．ボブはx=b1,b2,b3のとき、値が0となり、それ以外のとき、値が0以外となる多項式F(x)を生成する。例えば、F(x)=(x-b1)(x-b2)(x-b3)とすればよい。このような多項式は、ラグランジェ補間を利用して容易に生成することができる。ここで、F(x)の係数をα[0]、α[1]、…、α[n]とする。すなわち、F(x)=α[n]x^n+α[n-1]x^{n-1}+…+α[1]x+α[0]である。
２．ボブは、公開鍵pkを使用してα[0]、α[1]、…、α[n]をそれぞれ暗号化する。また、ボブは、暗号文C[0]、C[1]、…、C[n]をアリスに送付する。
３．アリスは、a^{n}、a^{n-1}、…、a^{0}を計算する。さらに、アリスは、C[n]^{a^{n}}、C[n-1]^{a^{n-1}}、…、C[0]^{a^{0}}を計算する。
４．アリスは、C=C[n]^{a^{n}}・C[n-1]^{a^{n-1}}・…・C[0]^{a^{0}}を計算する。凖同型性により、C=Enc(pk、F(a))である。また、アリスは、ランダムにrを選択し、C’=C^{r}とする。さらに、アリスは、C’をボブに送付する。
５．ボブは、受け取ったC’を復号する。ボブは、復号結果が0の場合、アリスは集合Bに含まれるデータを有すると判断し、復号結果が0以外の場合、アリスは集合Bに含まれるデータを持たないと判断する。【００３２】
簡単のため、入力aを持つアリスと、集合Bおよび秘密鍵skを持つボブによるSet IntersectionのプロトコルをSet Intersection[アリス(a),ボブ(B,sk)](pk)と表記する。ここで、pkはアリスとボブへの共通入力である公開鍵pkを表す。【００３３】
次に、Aided Computationを説明する。Aided Computationも、２人のエンティティであるアリスとボブの間で行われる暗号プロトコルである。アリスはあるデータaの暗号文Enc(pk,a)を持ち、ボブはデータの集合Bおよび公開鍵pkに対応する秘密鍵skを持つものと仮定する。ボブの暗号は、加法凖同型公開鍵暗号である。このとき、Aided Computationはアリスの持つデータaをボブに秘匿したまま、データaが集合Bに含まれるかどうかを確認するプロトコルである。Aided Computationでは、Set Intersectionとは異なり、アリスはデータaの平文を知らない。【００３４】
簡単のため、B={b1,b2,b3}としてAided Computationを説明する。また、x=b1,b2,b3のときに0となり、それ以外のときに0以外となる多項式F(x)が公開されているものとする。すなわち、F(x)=α[n]x^n+α[n-1]x^{n-1}+…+α[1]x+α[0]であり、α[0]〜α[n]が公開されているとする。【００３５】
１．アリスはランダムにrを選び、Enc(pk,ra)={Enc(pk,a)}^{r}を計算し、ボブに送付する。
２．ボブはEnc(pk,ra)を復号し、raを得る。
３．ボブは(ra)^{α[1]}、(ra)^{α[2]}、…、(ra)^{α[n]}を計算し、それぞれ公開鍵pkを用いて暗号化する。すなわち、C[i]=Enc(pk,(ra)^{α[i]})をi=1〜nに対して行い、C[1]〜C[n]をアリスに送付する。
４．アリスは、i=1〜nに対してC’[i]=(C[i])^{1/(r^{i})}を計算する。
５．アリスはC=C’[1]・C’[2]・…・C’[n]・Enc(pk,α[0])を計算し、ボブに送付する。凖同型性より、C=Enc(pk,F(a))である。
６．ボブは、Cを復号する。ボブは、復号結果が0の場合、アリスが集合Bに含まれるデータの暗号文を有すると判断し、復号結果が0以外の場合、アリスが集合Bに含まれるデータの暗号文を持たないと判断する。【００３６】
簡単のため、入力Enc(pk,a)を持つアリスと、集合Bおよび秘密鍵skを持つボブによる関数F(x)に対するAided ComputationのプロトコルをAided Computation[アリス(Enc(pk,a)),ボブ(B,sk)](pk,F(x))と表す。ここで、pkはアリスとボブへの共通入力である公開鍵pkを表す。【００３７】
非特許文献１では、クライアントのマニューシャ(type1,(x1,y1),θ1)（被認証データ）と、サーバに保管されている認証用テンプレート(type2,(x2,y2),θ2)（認証データ）が一致することを確認するために、Set IntersectionとAided Computationを利用する。具体的には、以下の処理を行う。【００３８】
（１）タイプの一致：Set Intersection[クライアント(type1),サーバ(type2,sk)](pk)を行う。【００３９】
（２）距離の一致：まず暗号化したまま(x1,y1)および(x2,y2)間のユークリッド距離を計算する。
（ア）サーバは、B={0,1,…,δd}として、F(x)を生成する。
（イ）サーバは、Enc(pk,x2^2),Enc(pk,x2),Enc(pk,y2^2),Enc(pk,y2)をそれぞれ計算し、クライアントに送付する。
（ウ）クライアントは、Enc(pk,x1^2),Enc(pk,y1^2)を計算する。
（エ）クライアントは、Enc(pk,x1^2)・{Enc(pk,x2)}^{-2x1}・Enc(pk,x2^2)・Enc(pk,y1^2)・{Enc(pk,y2)}^{-2y1}・Enc(pk,y2^2)=Enc(pk,(x1-x2)^2+(y1-y2)^2)を計算する。
（オ）Aided Computation[クライアント(Enc(pk,(x1-x2)^2+(y1-y2)^2)),サーバ({0,1,…,δd},sk)](pk,F(x))を実行する。【００４０】
（３）角度の一致：距離の一致と同様に、Enc(pk,(θ1-θ2)^2)を計算し、B’={0,1,…,δt}に対応したG(x)に対するAided Computation[クライアント(Enc(pk,(θ1-θ2)^2)),サーバ(B’,sk)](pk,G(x))を実行する。【００４１】
非特許文献１に記載された技術によると、クライアントからサーバに登録された認証データに基づいて認証される被認証データを、サーバに対して秘匿することができる。しかしながら、非特許文献１に記載された技術によると、サーバ上に登録された認証データが平文であるため、サーバからクライアントの機微データである認証データが漏えいするおそれがあり、サーバ管理者に対して認証データを秘匿していないという問題もある。【００４２】
なお、かかる問題を解消するために、特許文献２に記載された技術を採用することが考えられる。しかしながら、特許文献２に記載された技術によると、登録用の特徴ベクトル（認証データ）および認証用の特徴ベクトル（被認証データ）の暗号化の際に、二重凖同型暗号と呼ばれる特殊な凖同型暗号を用いる必要がある。一般に、二重凖同型暗号は計算コストがかかり、かつ、秘密鍵や公開鍵のサイズがとても大きくなるため、現実的な時間で処理することが難しいという問題がある。【００４３】
そこで、簡便な処理に基づいて、被認証データおよび認証データをサーバに対して秘匿することが要望される。本発明の目的は、かかる要望に寄与する照合システム、照合方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００４４】
本発明の第１の視点に係る照合システムは、
第１のノード、第２のノードおよび第３のノードを備え、
前記第１のノードは、公開鍵により認証データを暗号化して前記第３のノードに送信する暗号化部と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する距離計算部と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する照合用データ生成部と、を有し、
前記第２のノードは、前記公開鍵と秘密鍵の対を生成し、前記公開鍵を第１のノードに送信する鍵生成部と、
前記秘密鍵と前記照合用データに基づいて、前記被認証データを前記認証データと照合する照合部と、を有し、
前記第３のノードは、暗号化された前記認証データを保持する記憶部と、
前記多項式として、前記認証データと前記被認証データの距離の閾値をパラメータとして含む多項式を生成する照合用情報生成部と、を有する。【００４５】
本発明の第２の視点に係るノードは、
公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する暗号化部と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する距離計算部と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する照合用データ生成部と、を備え、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む。【００４６】
本発明の第３の視点に係る照合方法は、
第１のノードが、公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する工程と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する工程と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する工程と、を含み、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む。【００４７】
本発明の第４の視点に係るプログラムは、
公開鍵と秘密鍵の対を生成する第２のノードから受信した前記公開鍵により、認証データを暗号化して第３のノードに送信する処理と、
前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する処理と、
前記第３のノードから取得した多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する処理と、を第１のノードに設けられたコンピュータに実行させ、
前記多項式は、前記認証データと前記被認証データの距離の閾値をパラメータとして含む。
なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することができる。
【発明の効果】
【００４８】
本発明に係る照合システム、ノード、照合方法およびプログラムによると、簡便な処理に基づいて被認証データおよび認証データをサーバに対して秘匿することが可能となる。
【図面の簡単な説明】
【００４９】
【図１】一実施形態に係る照合システムの構成を一例として示すブロック図である。
【図２】第１の実施形態に係る照合システムの構成を一例として示すブロック図である。
【図３】第１の実施形態に係る照合システムのデータ登録動作を一例として示すシーケンス図である。
【図４】第１の実施形態に係る照合システムの暗号文照合動作を一例として示すシーケンス図である。
【発明を実施するための形態】
【００５０】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００５１】
図１は、一実施形態に係る照合システムの構成を一例として示すブロック図である。図１を参照すると、照合システムは、クライアントに相当する第１のノード１００と、認証ノードに相当する第２のノード２００と、サーバに相当する第３のノード３００とを備えている。第１のノード１００は、暗号化部１１、距離計算部２２、および、照合用データ生成部２３を有する。一方、第２のノードは、鍵生成部５１および照合部５４を有する。また、第３のノード３００は、記憶部３１および照合用情報生成部４１を有する。
【００５２】
第２のノード２００の鍵生成部５１は、公開鍵と秘密鍵の対を生成し、公開鍵を第１のノード１００に送信する。第１のノード１００の暗号化部１１は、公開鍵により認証データを暗号化して第３のノード３００に送信する。第３のノード３００の記憶部３１は、暗号化された認証データを保持する。
【００５３】
第１のノードの距離計算部２２は、認証データと照合される被認証データを受信すると、暗号化された認証データを第３のノード３００から取得して、被認証データと認証データとの距離を公開鍵により暗号化したまま算出する。第３のノード３００の照合用情報生成部４１は、認証データと被認証データの距離の閾値をパラメータとして含む多項式を生成する。第１のノード１００の照合用データ生成部２３は、第３のノード３００から取得した多項式に算出した距離を代入して公開鍵により暗号化した値を、照合用データとして生成して第２のノード２００に送信する。第２のノード２００の照合部５４は、秘密鍵と照合用データに基づいて、被認証データを認証データと照合する。
【００５４】
ここで、暗号化部１１は、加法準同型性を有する暗号化方式に基づいて暗号化を行うことが好ましい。一例として、暗号化部１１は、Paillier暗号に基づいて暗号化を行ってもよい。
【００５５】
照合用情報生成部４１は、上記の多項式として、独立変数と認証データの距離が上記の閾値以内であるときにゼロとなる多項式を生成してもよい。
【００５６】
また、暗号化部１１は、さらに、公開鍵により認証データの２乗を暗号化して第３のノード３００に送信し、記憶部３１は、さらに、暗号化された認証データの２乗を保持するようにしてもよい。このとき、距離計算部２２は、暗号化された認証データおよび暗号化された認証データの２乗を第３のノード３００から取得して、被認証データと認証データとの距離を公開鍵により暗号化したまま算出することが好ましい。
【００５７】
さらに、認証データおよび被認証データは、ｎ次元の要素を含んでいてもよい。このとき、距離計算部２２は、被認証データと認証データとのｎ次元ユークリッド距離を、公開鍵により暗号化したまま算出することが好ましい。
【００５８】
また、認証データおよび被認証データは、複数の要素を含んでいてもよい。このとき、距離計算部２２は、各要素について上記の距離を暗号化したまま算出し、照合用情報生成部４１は、各要素について多項式を生成し、照合用データ生成部２３は、各要素について照合用データを生成し、照合部５４は、秘密鍵と複数の要素について生成された照合用データとを用いて、被認証データを前記認証データと照合することが好ましい。
【００５９】
非特許文献１に記載された技術によると、サーバに登録されているデータが平文のままであるため、サーバからデータが漏えいする可能性がある。また、サーバ管理者へのデータの秘匿が行えないという問題もある。
【００６０】
上記一実施形態に係る照合システムによると、認証時にクライアント（第１のノード）からサーバ（第３のノード）に送付される被認証データのみならず、サーバ（第３のノード）のデータベース等に格納される認証データも秘匿強度の高い暗号方式を用いて暗号化される。したがって、かかる照合システムによると、非特許文献１に記載された技術における上記の問題が解消される。また、暗号化方式に凖同型性という特殊な性質を持たせることで、暗号化したままデータのユークリッド距離を計算することを可能とし、暗号データを復号することなく照合可能であることが保証される。さらに、登録時に生成するデータとして、認証データの２乗の暗号文を追加することにより、非特許文献１では不可能であった、暗号化されたデータ間の距離が計算可能となる。
【００６１】
以上のとおり、上記一実施形態に係る照合システムによると、第３のノード（サーバ）に保存された認証データの漏えいを防止することができ、サーバ管理者に悪意がある場合でも、認証データの平文の漏えいを防止することができる。その理由は、データ登録時に、第１のノード（クライアント）によって、サーバ管理者に復号されることのない暗号化鍵によって認証データが暗号化されるからである。
【００６２】
＜実施形態１＞
次に、第１の実施形態に係る照合システムついて図面を参照して詳細に説明する。
【００６３】
図２は、本実施形態に係る照合システムの構成を一例として示すブロック図である。図２を参照すると、照合システムは、登録データ生成装置１０、照合要求装置２０、記憶装置３０、データ照合装置４０、および、照合補助装置５０を備えている。
【００６４】
なお、図２は照合システムが５つのノードによって構成される場合を例示するが、本発明の照合システムは図示の態様に限定されない。一例として、登録データ生成装置１０と照合要求装置２０をまとめて第１のノード（クライアント）とし、照合補助装置５０を第２のノード（認証ノード）とし、記憶装置３０とデータ照合装置４０をまとめて第３のノード（サーバ）としてもよい。
【００６５】
登録データ生成装置１０は、暗号化部１１を有する。暗号化部１１は、秘匿の対象となる認証データと、照合補助装置５０が公開する暗号化鍵とを入力とし、認証データを暗号化鍵を用いて秘匿処理し、暗号データとして出力する。
【００６６】
ここで、照合補助装置５０により公開される暗号化鍵は、加法凖同型公開鍵暗号の公開鍵である。
【００６７】
記憶装置３０は、記憶部３１および識別子管理部３２を有する。記憶部３１は、登録データ生成装置１０から送付された暗号データとともに、識別子管理部３２により付与された固有の識別子を記憶する。
【００６８】
照合要求装置２０は、照合要求部２１、距離計算部２２、および、照合用データ生成部２３を有する。照合要求部２１は、認証データと照合すべき被認証データを入力として受け取ると、データ照合装置４０へ照合要求を送付する。距離計算部２２は、照合すべき被認証データと、データ照合装置４０から受信した照合用情報を入力として、暗号化距離データを生成する。照合用データ生成部２３は、暗号化距離データを入力として、照合補助装置５０と対話しながら、照合用データを生成する。
【００６９】
データ照合装置４０は、照合用情報生成部４１、照合用情報送付部４２、照合補助要求部４３、および、判定部４４を有する。照合用情報生成部４１は、記憶装置３０に記憶されている暗号データを入力として、照合用情報を生成する。照合用情報送付部４２は、照合要求装置２０から送付された照合要求を入力として受け取り、照合用情報を送付する。照合補助要求部４３は、照合要求装置２０から送付された照合用データを入力として受け取り、照合補助要求を生成し、照合補助装置５０へ送付する。判定部４４は、照合補助装置５０から受信した総合結果を入力として受け取り、照合結果を生成して出力する。
【００７０】
照合補助装置５０は、鍵生成部５１、照合補助部５２、および、総合結果補助部５３を有する。鍵生成部５１は、加法凖同型暗号の公開鍵および秘密鍵を生成し、公開鍵を公開し、秘密鍵を保持する。照合補助部５２は、照合要求装置２０の照合用データ生成部２３と対話を行い、照合用データの生成を補助する。総合結果補助部５３は、データ照合装置４０から送付された照合補助要求と、加法凖同型暗号の秘密鍵を入力として受け取り、総合結果を生成する。
【００７１】
次に、本実施形態に係る照合システム（図２）の動作を、図面を参照して詳細に説明する。
【００７２】
照合システムの動作は、データ登録フェーズと暗号文照合フェーズの２つのフェーズに大別される。データ登録フェーズでは、登録データ生成装置１０に認証データを入力し、認証データを暗号化し、記憶装置３０に登録する。一方、暗号文照合フェーズでは、照合要求装置２０に入力された被認証データを秘匿しながら、被認証データが、記憶装置３０に記憶されている暗号データの平文と近い（ユークリッド距離の小さい）ものであるか否かを判定する。以下、各フェーズにおける動作に関して詳細に説明する。
【００７３】
[データ登録フェーズ]
図３は、照合システムのデータ登録フェーズにおける動作を一例として示すシーケンス図である。
【００７４】
図３を参照すると、照合補助装置５０の鍵生成部５１は、加法凖同型暗号の公開鍵および秘密鍵を生成し、公開鍵を公開する（ステップＡ１）。
【００７５】
次に、登録データ生成装置１０は、秘匿対象となる認証データと、公開鍵を受け取る（ステップＡ２）。
【００７６】
次に、登録データ生成装置１０の暗号化部１１は、入力された認証データと、公開鍵とから、暗号データを生成し、記憶装置３０に送付する（ステップＡ３）。
【００７７】
記憶装置３０の識別子管理部３２は、暗号データを受信すると、暗号データに対して固有の識別子を付与する（ステップＡ４）。また、識別子管理部３２は、暗号データと識別子の組を記憶部３１に記憶する（ステップＡ５）。
【００７８】
[暗号文照合フェーズ]
図４は、照合システムの暗号文照合フェーズにおける動作を一例として示すシーケンス図である。
【００７９】
図４を参照すると、データ照合装置４０の照合用情報生成部４１は、記憶部３１に記憶された暗号データと暗号データに対応する識別子およびパラメータを受け付け（ステップＢ１）、照合用情報を生成する（ステップＢ２）。
【００８０】
次に、照合要求装置２０の照合要求部２１は、被認証データと公開鍵を受け付ける（ステップＢ３）。
【００８１】
次に、照合要求装置２０の照合要求部２１は、被認証データと公開鍵を受け付けると、照合要求を生成し、データ照合装置４０に出力する（ステップＢ４）。
【００８２】
データ照合装置４０の照合用情報送付部４２は、照合要求を受信すると、照合要求装置２０に照合用情報を出力する（ステップＢ５）。
【００８３】
照合要求装置２０の距離計算部２２は、照合用情報を受信すると、被認証データと暗号データの平文のユークリッド距離を暗号化したまま計算し、暗号化距離データを生成する（ステップＢ６）。
【００８４】
照合用データ生成部２３は、暗号化距離データと照合用情報を入力とし、照合補助装置５０の照合補助部５２と対話しながら、照合用データを生成し、データ照合装置４０に出力する（ステップＢ７）。
【００８５】
データ照合装置４０の照合補助要求部４３は、照合用データを受信すると、照合補助要求を生成し、照合補助装置５０に出力する（ステップＢ８）。
【００８６】
照合補助装置５０の総合結果補助部５３は、照合補助要求を受信すると、秘密鍵を入力として、総合結果を生成し、データ照合装置４０へ出力する（ステップＢ９）。
【００８７】
データ照合装置４０の判定部４４は、総合結果を受信すると、判定を行い、判定結果を出力する（ステップＢ１０）。
【００８８】
本実施形態に係る照合システムによると、認証時に登録データ生成装置１０から記憶装置３０に送付される被認証データのみならず、記憶装置３０に格納される認証データも秘匿強度の高い暗号方式を用いて暗号化される。したがって、例えば、記憶装置３０とデータ照合装置４０によりサーバを構成した場合、本実施形態に係る照合システムによると、サーバから認証データが漏洩することを防ぐことが可能となる。
【００８９】
＜実施形態２＞
次に、第２の実施形態に係る照合システムについて、図面を参照して説明する。
【００９０】
本実施形態では、第１の実施形態に係る照合システムにおいて、距離として１次元ユークリッド距離を用いる。すなわち、d(D,D’)=(D-D’)^{2}が閾値d以下である場合、マッチしたと判定し、dよりも大きい場合、マッチしなかったと判定する。また、本実施形態では、加法凖同型暗号（例えば、Paillier暗号など）を利用する。以下、各フェーズにおける動作に関して図３および図４を参照して詳細に説明する。
【００９１】
[データ登録フェーズ]
図３を参照すると、照合補助装置５０の鍵生成部５１は、加法凖同型暗号の公開鍵pkおよび秘密鍵skを生成し、公開鍵pkを公開する（ステップＡ１）。
【００９２】
次に、登録データ生成装置１０は、秘匿対象となる認証データDと、鍵生成部５１により生成された公開鍵pkを受け付ける（ステップＡ２）。
【００９３】
次に、登録データ生成装置１０の暗号化部１１は、入力された認証データDと公開鍵pkから、暗号データ(Enc(pk,D),Enc(pk,D^2))を生成し、記憶装置３０に送付する（ステップＡ３）。ここで、Enc(pk,D)は、公開鍵pkを用いて認証データDを暗号化した結果を表す。同様に、Enc(pk,D^2)は、公開鍵pkを用いて認証データDの２乗を暗号化した結果を表す。
【００９４】
記憶装置３０の識別子管理部３２は、暗号データを受信すると、暗号データに対して固有の識別子IDを付与する（ステップＡ４）。また、識別子管理部３２は、暗号データと識別子の組((Enc(pk,D),Enc(pk,D^2)),ID)を記憶部３１に記録する（ステップＡ５）。
【００９５】
[暗号文照合フェーズ]
図４を参照すると、データ照合装置４０の照合用情報生成部４１は、記憶部３１に記憶された暗号データと、暗号データに対応する識別子の組((Enc(pk,D),Enc(pk,D^2)),ID)を受け付け（ステップＢ１）、照合用情報を以下の手順で生成する（ステップＢ２）。
【００９６】
１．x=0,1,…,dである場合F(x)=0、それ以外の場合F(x)≠0となる多項式F(x)をランダムに生成する。例えば、F(x)=x(x-1)(x-2)…(x-d)は上記の性質を満たすd+1次の多項式である。一般に、このような条件を満たすd+1次以上の多項式は容易に構成することができる。簡単のため、F(x)の係数をα[0]〜α[N]とする。すなわち、F(x)=α[N]x^N+α[N-1]x^{N-1}+…+α[0]である。F(x)=x(x-1)(x-2)…(x-d)の場合、N=dとなる。
【００９７】
２．((Enc(pk,D),Enc(pk,D^2)),α[0]〜α[N])を照合用情報とする。
【００９８】
次に、照合要求装置２０の照合要求部２１は、被認証データD’と公開鍵pkを受け付ける（ステップＢ３）。
【００９９】
次に、照合要求装置２０の照合要求部２１は、被認証データD’と公開鍵pkを受け付けると、照合要求reqを生成し、データ照合装置４０に出力する（ステップＢ４）。照合要求reqは、照合を要求するメッセージである。
【０１００】
データ照合装置４０の照合用情報送付部４２は、照合要求を受信すると、照合要求装置２０に照合用情報を出力する（ステップＢ５）。
【０１０１】
照合要求装置２０の距離計算部２２は、照合用情報を受信すると、次のように、被認証データD’と暗号データの平文のユークリッド距離を暗号化したまま計算し、暗号化距離データを生成する（ステップＢ６）。
【０１０２】
１．Enc(pk,D’^2)を計算する。
２．Enc(pk,d(D,D’))=Enc(pk,D^2)・Enc(pk,D)^{-2D’}・Enc(pk,D’^2)を計算する。
【０１０３】
照合用データ生成部２３は、暗号化距離データと照合用情報を入力とし、次のように、照合補助装置５０の照合補助部５２と対話しながら、照合用データを生成し、データ照合装置４０に出力する（ステップＢ７）。
【０１０４】
１．ランダムにrを選び、Enc(pk,r・d(D,D’))=Enc(pk,d(D,D’))^{r}を計算し、照合補助装置５０に送付する。
２．照合補助装置５０の照合補助部５２は、秘密鍵skを用いてEnc(pk,r・d(D,D’))を復号し、r・d(D,D’)を計算する。
３．照合補助部５２は、(r・d(D,D’))^{2}、…、(r・d(D,D’))^{N}を計算し、公開鍵pkを用いてそれぞれ暗号化し、Enc(pk,((r・d(D,D’))^{2}))、…、Enc(pk,((r・d(D,D’))^{N}))を計算し、照合要求装置２０へ出力する。
４．照合用データ生成部２３は、ステップ１で選んだrを用いて、Enc(pk,((r・d(D,D’))^{2}))^{1/r^2}、…、Enc(pk,((r・d(D,D’))^{N}))^{1/(r^{N})}を計算し、Enc(pk,((d(D,D’))^{2}))、…、Enc(pk,((d(D,D’))^{N}))を得る。
５．Enc(pk,F(d(D,D’)))=(Enc(pk,((d(D,D’))^{N}))^{α[N]}・(Enc(pk,((d(D,D’))^{N-1}))^{α[N-1]}・…・(Enc(pk,d(D,D’)))^{α[1]}・Enc(pk,α[0])を計算する。
６．ランダムにRを選び、Enc(pk,F(d(D,D’)))^{R}を計算し、データ照合装置４０に出力する。
【０１０５】
ここで、ステップ６は、d(D,D’)＜dの場合の出力をランダムにするために行われる。出力をランダムにする必要がない場合、ステップ６を省略してもよい。また、ステップ１は、d(D,D’)の値を照合補助装置５０に秘匿するために行われる。秘匿する必要がない場合、ステップ１を省略してもよい。
【０１０６】
データ照合装置４０の照合補助要求部４３は、照合用データを受信すると、次のように、照合補助要求を生成し、照合補助装置５０に出力する（ステップＢ８）。
【０１０７】
１．ランダムにsを選び、C=Enc(pk,F(d(D,D’)))^{R}・Enc(pk,s)を計算し、照合補助装置５０に出力する。
【０１０８】
ここで、ステップ１は、Cの平文をランダムにすることにより、照合補助装置５０に照合結果を知らせないために行われる。照合補助装置５０に照合結果を知らせてもよい場合、ステップ１を省略してもよい。
【０１０９】
照合補助装置５０の総合結果補助部５３は、照合補助要求を受信すると、秘密鍵skを入力として、総合結果Pを次のように生成し、データ照合装置４０へ出力する（ステップＢ９）。すなわち、総合結果補助部５３は、秘密鍵skを用いて暗号文Cを復号し、復号結果を総合結果Pとして、データ照合装置４０へ出力する。
【０１１０】
データ照合装置４０の判定部４４は、総合結果Pを受信すると、次のように判定を行い、判定結果を出力する（ステップＢ１０）。すなわち、判定部４４は、P=sの場合、0≦d(D,D’)≦dであると判定し、それ以外の場合、d(D,D’)＞dであると判定する。
【０１１１】
本実施形態では、記憶装置３０に登録されているデータは暗号データである。また、照合フェーズにおいて照合要求装置２０から送付されるデータはいずれも暗号文である。したがって、記憶装置３０、データ照合装置４０に対して、登録された認証データDおよび被認証データD’に関する情報は一切洩れない。
【０１１２】
さらに、照合補助装置５０に対しても、照合要求装置２０およびデータ照合装置４０が乱数を用いることにより、登録された認証データDおよび被認証データD’に関する情報を一切漏らさない。
【０１１３】
＜実施形態３＞
次に、第３の実施形態に係る照合システムについて説明する。
【０１１４】
本実施形態では、第１の実施形態に係る照合システムにおいて、距離として２次元ユークリッド距離を用いる。すなわち、２つの２次元データD=(Dx,Dy)とD’=(D’x,D’y)の距離d(D,D’)=(Dx-D’x)^{2}+(Dy-D’y)^{2}が閾値d以下である場合、マッチしたと判定し、dよりも大きい場合、マッチしなかったと判定する。また、本実施形態では、加法凖同型暗号（例えば、Paillier暗号など）を利用する。以下、各フェーズにおける動作に関して詳細に説明する。
【０１１５】
[データ登録フェーズ]
距離として１次元ユークリッド距離を用いる第２の実施形態に係る照合システムのデータ登録フェーズのステップＡ３において、暗号データ(Enc(pk,D),Enc(pk,D^2))を暗号データ(Enc(pk,Dx),Enc(pk,Dx^2),Enc(pk,Dy),Enc(pk,Dy^2))に置き換える。
【０１１６】
[暗号文照合フェーズ]
距離として１次元ユークリッド距離を用いる第２の実施形態に係る照合システムの暗号文照合フェーズにおいて、ステップＢ６を以下のように変更する。
【０１１７】
１．Enc(pk,D’x^2),Enc(pk,D’y^2)を計算する。
２．Enc(pk,d(D,D’))=Enc(pk,Dx^2)・Enc(pk,Dx)^{-2D’x}・Enc(pk,D’x^2)・Enc(pk,Dy^2)・Enc(pk,Dy)^{-2D’y}・Enc(pk,D’y^2)を計算する。
【０１１８】
本実施形態では、第２の実施形態と同様に、記憶装置３０に登録されている認証データは暗号データである。また、照合フェーズにおいて照合要求装置２０から送付されるデータはいずれも暗号文である。したがって、記憶装置３０、データ照合装置４０に対して、登録された認証データDおよび被認証データD’に関する情報は一切洩れない。
【０１１９】
さらに、照合補助装置５０に対しても、照合要求装置２０およびデータ照合装置４０が乱数を用いることにより、登録された認証データDおよび被認証データD’に関する情報を一切漏らさない。
【０１２０】
＜実施形態４＞
次に、第４の実施形態に係る照合システムについて、図面を参照して説明する。
【０１２１】
本実施形態では、第１の実施形態に係る照合システムにおいて、２つ以上の複数要素を持つデータの照合を行う。ここでは、一例として、各データが２つの要素を持ち、一方は１次元ユークリッド距離、もう一方を２次元ユークリッド距離を指標として照合を行う場合について説明する。すなわち、２つのデータD=(t,(x,y))、D’=(t’,(x’,y’))としたとき、d(t,t’)≦d_{t}、かつ、d((x,y),(x’,y’))≦d_{e}である場合、マッチしたと判定し、それ以外の場合、マッチしなかったと判定する。また、本実施形態では、加法凖同型暗号（例えば、Paillier暗号など）を利用する。以下、各フェーズにおける動作に関して詳細に説明する。
【０１２２】
[データ登録フェーズ]
図３を参照すると、照合補助装置５０の鍵生成部５１は、加法凖同型暗号の公開鍵pkおよび秘密鍵skを生成し、公開鍵pkを公開する（ステップＡ１）。
【０１２３】
次に、登録データ生成装置１０は、秘匿対象となる認証データDと、鍵生成部５１により生成された公開鍵pkを受け付ける（ステップＡ２）。
【０１２４】
次に、登録データ生成装置１０の暗号化部１１は、入力された認証データDと公開鍵pkから、暗号データ
(Enc(pk,ｔ),Enc(pk,ｔ^2)),(Enc(pk,x),Enc(pk,x^2)),(Enc(pk,y),Enc(pk,y^2))
を生成し、記憶装置３０に送付する（ステップＡ３）。
【０１２５】
ここで、Enc(pk,a)は公開鍵pkを用いてデータaを暗号化した結果を表す。同様に、Enc(pk,a^2)は公開鍵pkを用いてデータaの２乗を暗号化した結果を表す。
【０１２６】
記憶装置３０の識別子管理部３２は、暗号データを受信すると、暗号データに対して固有の識別子IDを付与する（ステップＡ４）。また、識別子管理部３２は、暗号データと識別子の組
((Enc(pk,ｔ),Enc(pk,ｔ^2)),(Enc(pk,x),Enc(pk,x^2)),(Enc(pk,y),Enc(pk,y^2)),ID)
を記憶部３１に記録する（ステップＡ５）。
【０１２７】
[暗号文照合フェーズ]
図４を参照すると、データ照合装置４０の照合用情報生成部４１は、記憶部３１に記憶された暗号データと、暗号データに対応する識別子の組
((Enc(pk,t),Enc(pk,t^2)),(Enc(pk,x),Enc(pk,x^2)),(Enc(pk,y),Enc(pk,y^2)),ID)
を入力とし（ステップＢ１）、照合用情報を次の手順で生成する（ステップＢ２）。
【０１２８】
１．x=0,1,…,d_ｔの場合F(x)=0、それ以外の場合F(x)≠0となる多項式F(x)をランダムに生成する。例えば、F(x)=x(x-1)(x-2)…(x-d_t)は上記の性質を満たすd_t+1次の多項式である。一般に、このような条件を満たすd_t+1次以上の多項式は容易に構成することができる。簡単のため、F(x)の係数をα[0]〜α[N]とする。すなわち、F(x)=α[N]x^N+α[N-1]x^{N-1}+…+α[0]である。例えば、F(x)=x(x-1)(x-2)…(x-d_t)の場合、N=d_tとなる。
２．１．と同様にして、x=0,1,…,d_eの場合G(x)=0、それ以外の場合G(x)≠0となる多項式G(x)をランダムに生成する。簡単のため、G(x)の係数をβ[0]〜β[N’]とする。すなわち、G(x)=β[N’]x^n+β[N’-1]x^{n-1}+…+β[0]である。例えば、G(x)=x(x-1)(x-2)…(x-d_e)の場合、N’=d_eとなる。
３．((Enc(pk,ｔ),Enc(pk,ｔ^2)),(Enc(pk,x),Enc(pk,x^2)),(Enc(pk,y),Enc(pk,y^2)),α[0]〜α[N],β[0]〜β[N’])を照合用情報とする。
【０１２９】
次に、照合要求装置２０の照合要求部２１は、入力データD’と公開鍵pkを受け付ける（ステップＢ３）。
【０１３０】
次に、照合要求装置２０の照合要求部２１は、被認証データD’と公開鍵pkを受け付けると、照合要求reqを生成し、データ照合装置４０に出力する（ステップＢ４）。照合要求reqは、照合を要求するメッセージである。
【０１３１】
データ照合装置４０の照合用情報送付部４２は、照合要求を受信すると、照合要求装置２０に照合用情報を出力する（ステップＢ５）。
【０１３２】
照合要求装置２０の距離計算部２２は、照合用情報を受信すると、次のように、被認証データと暗号データの平文のユークリッド距離を暗号化したまま計算し、暗号化距離データを生成する（ステップＢ６）。
【０１３３】
１．Enc(pk,t’^2),Enc(pk,x’^2),Enc(pk,y’^2)を計算する。
２．Enc(pk,d(ｔ,ｔ’))=Enc(pk,ｔ^2)・Enc(pk,ｔ)^{-2ｔ’}・Enc(pk,ｔ’^2)を計算する。
３．Enc(pk,d((x,y),(x’,y’)))=Enc(pk,x^2)・Enc(pk,x)^{-2x’}・Enc(pk,x’^2)・Enc(pk,y^2)・Enc(pk,y)^{-2y’}・Enc(pk,y’^2)を計算する。
【０１３４】
照合用データ生成部２３は、暗号化距離データと照合用情報を入力とし、次のように、照合補助装置５０の照合補助部５２と対話しながら、照合用データを生成し、データ照合装置４０に出力する（ステップＢ７）。
【０１３５】
１．ランダムにr_tを選び、Enc(pk,r_t・d(t,t’))=Enc(pk,d(t,t’))^{r_t}を計算する。
２．ランダムにr_eを選び、
Enc(pk,r_e・d((x,y),(x’,y’)))=Enc(pk,d((x,y),(x’,y’)))^{r_e}
を計算し、１.で計算したEnc(pk,r_t・d(t,t’))とともに照合補助装置５０に送付する。
３．照合補助装置５０の照合補助部５２は、秘密鍵skを用いてEnc(pk,r_t・d(t,t’))およびEnc(pk,r_e・d((x,y),(x’,y’)))を復号し、r_t・d(t,t’),r_e・d((x,y),(x’,y’))を計算する。
４．照合補助部５２は、(r_t・d(t,t’))^{2}、…、(r_t・d(t,t’))^{N}、(r_e・d((x,y),(x’,y’)))^{2}、…、(r_e・d((x,y),(x’,y’)))^{N’}を計算し、公開鍵pkを用いてそれぞれ暗号化し、Enc(pk,(r_t・d(t,t’))^{2})、…、Enc(pk,(r_t・d(t,t’))^{N})、Enc(pk,(r_e・d((x,y),(x’,y’)))^{2})、…、Enc(pk,(r_e・d((x,y),(x’,y’)))^{N’})を計算し、照合要求装置２０へ出力する。
５．照合用データ生成部２３は、ステップ１、２で選んだr_t,r_eを用いて、Enc(pk,((r・Enc(pk,(r_t・d(t,t’))^{2})^{1/r_t^2}、…、Enc(pk,(r_t・d(t,t’))^{N})^{1/(r_t)^N}、Enc(pk,(r_e・d((x,y),(x’,y’)))^{2})^{1/r_e^2}、…、Enc(pk,(r_e・d((x,y),(x’,y’)))^{N’})^{1/(r_e)^{N}}を計算し、Enc(pk,((r・Enc(pk,(r_t・d(t,t’))^{2})、…、Enc(pk,(r_t・d(t,t’))^{N})、Enc(pk,(r_e・d((x,y),(x’,y’)))^{2})、…、Enc(pk,(r_e・d((x,y),(x’,y’)))^{N’})を得る。
６．Enc(pk,F(d(t,t’)))=(Enc(pk,((d(t,t’))^{N}))^{α[N]}・(Enc(pk,((d(t,t’))^{N-1}))^{α[N-1]}・…・(Enc(pk,d(t,t’)))^{α[1]}・Enc(pk,α[0]),Enc(pk,G(d((x,y),(x’,y’))))=(Enc(pk,((d((x,y),(x’,y’)))^{N’}))^{β[N’]}・(Enc(pk,((d((x,y),(x’,y’)))^{N’-1}))^{β[N’-1]}・…・(Enc(pk,d((x,y),(x’,y’))))^{β[1]}・Enc(pk,β[0])を計算する。
７．Enc(pk,d(D,D’))=Enc(pk,F(d(t,t’)))・Enc(pk,G(d((x,y),(x’,y’))))を計算する。
８．ランダムにRを選び、Enc(pk,F(d(D,D’)))^{R}を計算し、データ照合装置４０に出力する。
【０１３６】
ここで、ステップ８は、d(D,D’)＜dの場合の出力をランダムにするために行われる。出力をランダムにする必要がない場合、ステップ８を省略してもよい。また、ステップ１、２は、d(D,D’)の値を照合補助装置５０に秘匿するために行われる。秘匿する必要がない場合、ステップ１、２を省略してもよい。
【０１３７】
データ照合装置４０の照合補助要求部４３は、照合用データを受信すると、次のように、照合補助要求を生成し、照合補助装置５０に出力する（ステップＢ８）。
１．ランダムにsを選び、C=Enc(pk,F(d(D,D’)))^{R}・Enc(pk,s)を計算し、照合補助装置５０に出力する。
【０１３８】
ここで、ステップ１は、Cの平文をランダムにすることにより、照合補助装置５０に照合結果を知らせないために行われる。照合補助装置５０に照合結果を知らせてもよい場合、ステップ１を省略してもよい。
【０１３９】
照合補助装置５０の総合結果補助部５３は、照合補助要求を受信すると、秘密鍵skを入力として、次のように総合結果Pを生成し、データ照合装置４０へ出力する（ステップＢ９）。すなわち、総合結果補助部５３は、秘密鍵skを用いて暗号文Cを復号し、復号結果を総合結果Pとしてデータ照合装置４０へ出力する。
【０１４０】
データ照合装置４０の判定部４４は、総合結果Pを受信すると、次のように判定して、判定結果を出力する（ステップＢ１０）。すなわち、判定部４４は、P=sの場合、認証データDと被認証データD’がマッチしたと判定し、それ以外の場合、認証データDと被認証データD’はマッチしないと判定する。
【０１４１】
本実施形態では、記憶装置３０に登録されているデータは暗号データである。また、照合フェーズにおいて照合要求装置２０から送付されるデータはいずれも暗号文である。したがって、記憶装置３０、データ照合装置４０に対して、登録された認証データDおよび被認証データD’に関する情報は一切洩れない。
【０１４２】
さらに、照合補助装置５０に対しても、照合要求装置２０およびデータ照合装置４０が乱数を用いることにより、登録された認証データDおよび被認証データD’に関する情報を一切漏らさない。
【０１４３】
本実施形態では、データが２要素から構成され、それぞれ１次元ユークリッド距離、２次元ユークリッド距離を指標として照合を行う場合を説明したが、データが３要素以上から構成される場合にも容易に適用可能である。また、指標とするユークリッド距離が３次元以上の場合にも容易に適用可能である。
【０１４４】
上記実施形態に係る認証システムは、一例として、タイプと２次元座標と角度を要素とするマニューシャを用いた生体認証に対して適用することができる。具体的には、データ登録フェーズにおける入力データと、暗号文照合フェーズにおける入力データを、指紋や静脈などから取得した生体情報（マニューシャ）とする。これにより、生体情報を秘匿したまま、記憶装置に格納された暗号化された生体データと、照合要求装置から創出された暗号化された生体データが同一人物から採取されたものであるか否かを、２つの入力データのユークリッド距離が一定数以下となるかどうかにより判定することが可能となる。特に、生体情報は、常に安定して同一のデータが取得できるわけではないことが知られている。一方、同一人物から取得されるデータは類似している（各要素のユークリッド距離が小さいデータが取得できる）と仮定することができる。したがって、本発明に係る照合システムは、生体認証に対して好適に適用し得る。
【０１４５】
なお、上記の特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素などを含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【０１４６】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の視点に係る照合システムのとおりである。
［形態２］
前記暗号化部は、加法準同型性を有する暗号化方式に基づいて暗号化を行う、形態１に記載の照合システム。
［形態３］
前記暗号化部は、Paillier暗号に基づいて暗号化を行う、形態２に記載の照合システム。
［形態４］
前記照合用情報生成部は、前記多項式として、独立変数と前記認証データの距離が前記閾値以内であるときにゼロとなる多項式を生成する、形態１ないし３のいずれか一に記載の照合システム。
［形態５］
前記暗号化部は、さらに、前記公開鍵により前記認証データの２乗を暗号化して前記第３のノードに送信し、
前記記憶部は、さらに、暗号化された前記認証データの２乗を保持し、
前記距離計算部は、暗号化された前記認証データおよび暗号化された前記認証データの２乗を前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する、形態２ないし４のいずれか一に記載の照合システム。
［形態６］
前記認証データおよび前記被認証データは、ｎ次元の要素を含み、
前記距離計算部は、前記被認証データと前記認証データとのｎ次元ユークリッド距離を、前記公開鍵により暗号化したまま算出する、形態５に記載の照合システム。
［形態７］
前記認証データおよび前記被認証データは、複数の要素を含み、
前記距離計算部は、各要素について前記距離を暗号化したまま算出し、
前記照合用情報生成部は、各要素について前記多項式を生成し、
前記照合用データ生成部は、各要素について前記照合用データを生成し、
前記照合部は、前記秘密鍵と前記複数の要素について生成された照合用データとを用いて、前記被認証データを前記認証データと照合する、形態１ないし６のいずれか一に記載の照合システム。
［形態８］
上記第２の視点に係るノードのとおりである。
［形態９］
前記暗号化部は、加法準同型性を有する暗号化方式に基づいて暗号化を行う、形態８に記載のノード。
［形態１０］
前記暗号化部は、Paillier暗号に基づいて暗号化を行う、形態９に記載のノード。
［形態１１］
前記多項式は、独立変数と前記認証データの距離が前記閾値以内であるときにゼロとなる多項式である、形態８ないし１０のいずれか一に記載のノード。
［形態１２］
前記暗号化部は、さらに、前記公開鍵により前記認証データの２乗を暗号化して前記第２のノードに送信し、
前記距離計算部は、暗号化された前記認証データおよび暗号化された前記認証データの２乗を前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する、形態９ないし１１のいずれか一に記載のノード。
［形態１３］
前記認証データおよび前記被認証データは、ｎ次元の要素を含み、
前記距離計算部は、前記被認証データと前記認証データとのｎ次元ユークリッド距離を、前記公開鍵により暗号化したまま算出する、形態１２に記載のノード。
［形態１４］
前記認証データおよび前記被認証データは、複数の要素を含み、
前記距離計算部は、各要素について前記距離を暗号化したまま算出し、
前記照合用データ生成部は、各要素について生成された前記多項式を用いて、各要素について前記照合用データを生成して前記第２のノードに送信する、形態８ないし１３のいずれか一に記載のノード。
［形態１５］
第１のノード、第２のノードおよび第３のノードを備えた照合システムにおける照合方法であって、
前記第２のノードが、公開鍵と秘密鍵の対を生成し、前記公開鍵を第１のノードに送信する工程と、
前記第１のノードが、前記公開鍵により認証データを暗号化して前記第３のノードに送信する工程と、
前記第３のノードが、暗号化された前記認証データを保持する工程と、
前記第１のノードが、前記認証データと照合される被認証データを受信すると、暗号化された前記認証データを前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する工程と、
前記第３のノードが、前記被認証データと前記認証データの距離の閾値をパラメータとして含む多項式を生成して前記第１のノードに送信する工程と、
前記第１のノードが、前記多項式に前記距離を代入して前記公開鍵により暗号化した値を、照合用データとして生成して前記第２のノードに送信する工程と、
前記第２のノードが、前記秘密鍵と前記照合用データに基づいて、前記被認証データを前記認証データと照合する工程と、を含む、照合方法。
［形態１６］
上記第３の視点に係る照合方法のとおりである。
［形態１７］
前記第１のノードは、加法準同型性を有する暗号化方式に基づいて暗号化を行う、形態１６に記載の照合方法。
［形態１８］
前記第１のノードは、Paillier暗号に基づいて暗号化を行う、形態１７に記載の照合方法。
［形態１９］
前記多項式は、独立変数と前記認証データの距離が前記閾値以内であるときにゼロとなる多項式である、形態１６ないし１８のいずれか一に記載の照合方法。
［形態２０］
前記第１のノードが、さらに、前記公開鍵により前記認証データの２乗を暗号化して前記第３のノードに送信する工程を含み、
前記第１のノードは、暗号化された前記認証データおよび暗号化された前記認証データの２乗を前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する、形態１７ないし１９のいずれか一に記載の照合方法。
［形態２１］
前記認証データおよび前記被認証データは、ｎ次元の要素を含み、
前記第１のノードは、前記被認証データと前記認証データとのｎ次元ユークリッド距離を、前記公開鍵により暗号化したまま算出する、形態２０に記載の照合方法。
［形態２２］
前記認証データおよび前記被認証データは、複数の要素を含み、
前記第１のノードは、各要素について前記距離を暗号化したまま算出し、
前記照合用データ生成部は、各要素について生成された前記多項式を用いて、各要素について前記照合用データを生成して前記第２のノードに送信する、形態１６ないし２１のいずれか一に記載の照合方法。
［形態２３］
上記第４の視点に係るプログラムのとおりである。
［形態２４］
加法準同型性を有する暗号化方式に基づいて暗号化する処理を、前記コンピュータに実行させる、形態２３に記載のプログラム。
［形態２５］
Paillier暗号に基づいて暗号化する処理を、前記コンピュータに実行させる、形態２４に記載のプログラム。
［形態２６］
前記多項式は、独立変数と前記認証データの距離が前記閾値以内であるときにゼロとなる多項式である、形態２３ないし２５のいずれか一に記載のプログラム。
［形態２７］
前記公開鍵により前記認証データの２乗を暗号化して前記第３のノードに送信する処理と、
暗号化された前記認証データおよび暗号化された前記認証データの２乗を前記第３のノードから取得して、前記被認証データと前記認証データとの距離を前記公開鍵により暗号化したまま算出する処理と、を前記コンピュータに実行させる、形態２４ないし２６のいずれか一に記載のプログラム。
［形態２８］
前記認証データおよび前記被認証データは、ｎ次元の要素を含み、
前記被認証データと前記認証データとのｎ次元ユークリッド距離を、前記公開鍵により暗号化したまま算出する処理を、前記コンピュータに実行させる、形態２７に記載のプログラム。
［形態２９］
前記認証データおよび前記被認証データは、複数の要素を含み、
各要素について前記距離を暗号化したまま算出する処理と、
前記照合用データ生成部は、各要素について生成された前記多項式を用いて、各要素について前記照合用データを生成して前記第２のノードに送信処理と、を前記コンピュータに実行させる、形態２３ないし２８のいずれか一に記載のプログラム。
【符号の説明】
【０１４７】
１０    登録データ生成装置
１１    暗号化部
２０    照合要求装置
２１    照合要求部
２２    距離計算部
２３    照合用データ生成部
３０    記憶装置
３１    記憶部
３２    識別子管理部
４０    データ照合装置
４１    照合用情報生成部
４２    照合用情報送付部
４３    照合補助要求部
４４    判定部
５０    照合補助装置
５１    鍵生成部
５２    照合補助部
５３    総合結果補助部
５４    照合部
１００、２００、３００  ノード
【図１】
2014185450.tif 000003
【図２】
2014185450.tif 000004
【図３】
2014185450.tif 000005
【図４】
2014185450.tif 000006
【国際調査報告】
2014185450.tif 000007
2014185450.tif 000008
2014185450.tif 000009
2014185450.tif 000010