(57)【要約】      （修正有）【課題】準同型暗号を利用した秘匿距離計算において、暗号ベクトルデータのサイズと秘匿距離計算時間の両方を削減する。【解決手段】暗号処理装置の一例として、多項式変換部（以下ａと表記）、重み計算部（ｂ）、準同型暗号化部（ｃ）、および秘匿距離計算部（ｄ）を含む。ａは、第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る。ｂは、前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る。ｃは、前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化する。ｄは、前記ｃで暗号化したそれぞれから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る。【選択図】図１Ａ
2014126865.tif 000002
【特許請求の範囲】
【請求項１】
第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る多項式変換部と、
前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る重み計算部と、
前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得る準同型暗号部と、
前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る秘匿距離計算部と、
を含む暗号処理装置。
【請求項２】
前記重みはハミング重みであり、前記秘匿距離はハミング距離である、付記１の装置。
【請求項３】
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数９６】
2014126865.tif 000098
または、
【数９７】
2014126865.tif 000099
で定義され、前記第２の変換多項式は、［数９６］、［数９７］の前記第１の変換多項式ではない方で定義される、請求項１または２の装置。
【請求項４】
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数９８】
2014126865.tif 000100
と定義すると、
【数９９】
2014126865.tif 000101
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数１００】
2014126865.tif 000102
として、
【数１０１】
2014126865.tif 000103
である、請求項３の装置。
【請求項５】
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数１０２】
2014126865.tif 000104
または、
【数１０３】
2014126865.tif 000105
で定義され、前記第２の変換多項式は、［数１０２］、［数１０３］の前記第１の変換多項式ではない方で定義される、付記１または２の装置。
【請求項６】
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数１０４】
2014126865.tif 000106
と定義すると、
【数１０５】
2014126865.tif 000107
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数１０６】
2014126865.tif 000108
として、
【数１０７】
2014126865.tif 000109
または、
【数１０８】
2014126865.tif 000110
である、請求項５の装置。
【請求項７】
前記準同型暗号方式では、平文ｂの暗号文ｃは、ベクトルｕを、平文ｂと同じ次元のベクトルであって、成分が０または１であるベクトルとし、ベクトルｅ１を第１成分のみが１で、それ以外の成分は全て０であるベクトルとして、
【数１０９】
2014126865.tif 000111
で与えられ、ここで、Ｂは平文をベクトル表示したときの次元ｎと所定のビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）として、
【数１１０】
2014126865.tif 000112
のエルミート標準形である、請求項１乃至６のいずれか一項の装置。
【請求項８】
さらに、
正規ユーザの生体の一部に関する情報から前記正規ユーザを他のユーザから区別する特徴を第１の特徴量として抽出する第１の特徴量抽出部と、
前記正規ユーザとして認証されるべきユーザの生体の一部に関する情報から前記正規ユーザの前記第１の特徴量と比較される第２の特徴量を抽出する特徴量抽出部と、
前記第１の特徴量を、前記第１のベクトルとして表現する第１のベクトル化部と、
前記第２の特徴量を、前記第２のベクトルとして表現する第２のベクトル化部と、
前記暗号化秘匿距離を復号して前記秘匿距離を算出する復号処理部と、
前記秘匿距離と予め決められた閾値との比較に基づいて、前記正規ユーザとして認証されるべきユーザが前記正規ユーザであるかどうかを判定する判定部と、
を含み、生体認証装置として機能する、請求項１乃至７のいずれか一項の装置。
【請求項９】
さらに、
秘匿情報にタグ付けされる第１のテキストデータを前記第１のベクトルとして表現する第１のベクトル化部と、
前記秘匿情報の検索のために使用される第２のテキストデータを前記第２のベクトルとして表現する第２のベクトル化部と、
前記第１のテキストデータ、前記第１のベクトルとして表現する第１のベクトル化部と、
前記第２のテキストデータを、前記第２のベクトルとして表現する第２のベクトル化部と、
前記暗号化秘匿距離を復号して類似度として前記秘匿距離を算出する復号処理部と、
を含み、タグ検索装置として機能する、請求項１乃至７のいずれか一項の装置。
【請求項１０】
第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得ることと、
前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る重みことと、
前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得ることと、
前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得ることと、
を含む暗号処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置および方法に関する。
【背景技術】
【０００２】
現在、個人情報、機密情報の保護の重要性が増す中、それらの情報を利用したサービスの市場が拡大しつつある。そのようなサービスとしては、たとえば、スマートフォンから取得できる個人ユーザの位置情報を活用したサービスなどがある。そこで、個人情報・機密情報を保護したままデータの利活用ができる秘匿化技術が注目されている。秘匿化技術の中には、データ種別・サービス要件に応じて、暗号技術や統計技術を使った技術がある。
【０００３】
暗号技術を用いた秘匿化技術として、準同型暗号技術がある。準同型暗号技術は、暗号化と復号とで一対の異なる鍵を用いる公開鍵暗号方式の１つで、暗号化したままデータ操作が可能となる機能を備えた暗号である。
【０００４】
準同型暗号方式を用いれば、暗号文の加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、電子投票・電子現金などの分野や近年ではクラウド・コンピューティング分野において利用されることが期待されている。加算または乗算に関する準同型暗号方式として、乗算のみ可能なＲＳＡ暗号方式や、加算のみが可能なＡｄｄｉｔｉｖｅ  ＥｌＧａｍａｌ暗号が知られている。乗算準同型暗号では、平文（メッセージ）ａ、ｂの暗号文をＥ（ａ）、Ｅ（ｂ）とすると、平文の積ａ・ｂの暗号文Ｅ（ａ・ｂ）を、Ｅ（ａ）とＥ（ｂ）から計算することができる。また、加算準同型暗号では、平文ａ、ｂの暗号文をＥ（ａ）、Ｅ（ｂ）とすると、平文の和ａ＋ｂの暗号文Ｅ（ａ＋ｂ）を、Ｅ（ａ）とＥ（ｂ）から計算することができる。準同型暗号方式を用いれば、暗号文の加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、電子投票・電子現金などの分野や近年ではクラウド・コンピューティング分野において利用されることが期待されている。
【０００５】
最近、加算と乗算の両方に関して準同型性を有する暗号として完全準同型暗号が知られている。加法と乗法が暗号化したままで計算できれば、排他的論理和、論理積、否定といった演算を暗号化したままで計算することができる。つまり、完全準同型暗号とは、すべての論理回路による演算に対して準同型性を有する暗号である。当初は、理論的な実現方法のみが示され、実用的な構成方法は明らかにされなかったが、鍵生成方法の具体的な構成方法の例や、暗号化できるデータの種類を拡張した暗号方式も提案されつつある。また、限定回だけ加算と乗算の両方が可能な準完全準同型暗号（Ｓｏｍｅｗｈａｔ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ）があり、この暗号方式は完全準同型暗号に比べ暗号サイズと処理性能が大幅に少なくて済むため、より実用的な運用が期待されている。
【０００６】
一般に、暗号技術は２つの情報の類似性を検証するシステムにおいて使用されている。そのようなシステムとしては、たとえば、生体認証システム、タグ検索システムが挙げられる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１１−１４５５１２号公報
【非特許文献】
【０００８】
【非特許文献１】Ｃ．Ｇｅｎｔｒｙ、“Ｆｕｌｌｙ Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｕｓｉｎｇ  ｉｄｅａｌ  ｌａｔｔｉｃｅｓ”、ＳＴＯＣ２００９、ｐｐ．１６９−１７８、２００９
【非特許文献２】Ｃ．Ｇｅｎｔｒｙ  ａｎｄ  Ｓ．Ｈａｌｅｖｉ、“Ｉｍｐｌｅｍｅｎｔｉｎｇ  Ｇｅｎｔｒｙ’ｓ  Ｆｕｌｌｙ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ”、ＥＵＲＯＣＲＹＰＴ  ２０１１、ＬＮＣＳ  ６６３２、ｐｐ．１２９−１４８、 ２０１１
【非特許文献３】安田、矢嶋、下山、小暮「複数企業が持つ購買履歴データのクラウド秘匿集計」ＳＣＩＳ  ２０１２
【発明の概要】
【発明が解決しようとする課題】
【０００９】
準同型暗号を利用した秘匿生体認証システム・秘匿タグ検索システムにおいて、生体情報やタグを表す特徴量をベクトル化してそのベクトルデータを準同型暗号化する必要がある。通常、ベクトルデータＡ＝（ａ１、ａ２、…）を準同型暗号で暗号化する場合、各成分ａｉを暗号化し、暗号ベクトルデータＥ（Ａ）＝（Ｅ（ａ１）、Ｅ（ａ２）、…）を生成する。さらに、2つの暗号ベクトルデータＥ（Ａ）＝（Ｅ（ａ１）、Ｅ（ａ２）、…）とＥ（Ｂ）＝（Ｅ（ｂ１）、Ｅ（ｂ２）、…）の秘匿距離を計算する。暗号距離は、一般に、暗号加算と暗号乗算の組み合わせで構成される。そのような秘匿距離の例には、ハミング距離、
【００１０】
【数１】
2014126865.tif 000003
がある。しかし、このようにベクトルデータの各成分を準同型暗号化する場合、暗号ベクトルデータＥ（Ａ）＝（Ｅ（ａ１）、Ｅ（ａ２）、…）、Ｅ（Ｂ）＝（Ｅ（ｂ１）、Ｅ（ｂ２）、…）などのサイズが巨大になり、さらに秘匿距離計算に多大な計算時間を要するという問題がある。
【００１１】
そこで、１つの側面では、本発明は、準同型暗号を利用した秘匿距離計算において、暗号ベクトルデータのサイズと秘匿距離計算の時間の両方を削減することを目的とする。
【課題を解決するための手段】
【００１２】
１つの案では、暗号処理装置は多項式変換部と、重み計算部と、準同型暗号化部と、秘匿距離計算部と、を含むことを特徴とする。多項式変換部は、第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る。重み計算部は、多項式変換部と、前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る。準同型暗号化部は、前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得る。秘匿距離計算部は、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る。
【発明の効果】
【００１３】
実施形態の暗号処理装置および方法では、準同型暗号を利用した秘匿距離計算において、暗号ベクトルデータのサイズと計算の時間の両方を削減することができるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１Ａ】準同型暗号を利用した生体認証システムの登録時における概略を示す図である。
【図１Ｂ】準同型暗号を利用した生体認証システムの照合時における概略を示す図である。
【図２Ａ】準同型暗号を利用した生体認証システムの登録時における構成の例を示すブロック図である。
【図２Ｂ】準同型暗号を利用した生体認証システムの照合時における構成の例を示すブロック図である。
【図３】準同型暗号を利用した生体認証システムの登録時における処理フローの例を示す図である。
【図４】準同型暗号を利用した生体認証システムの照合時における処理フローの例を示す図である。
【図５Ａ】準同型暗号を利用したタグ検索システムの保存時における概略を示す図である。
【図５Ｂ】準同型暗号を利用したタグ検索システムの検索時における概略を示す図である。
【図６Ａ】準同型暗号を利用したタグ検索システムの保存時における構成の例を示すブロック図である。
【図６Ｂ】準同型暗号を利用したタグ検索システムの検索時における構成の例を示すブロック図である。
【図７】準同型暗号を利用したタグ検索システムの保存時における処理フローの例を示す図である。
【図８】準同型暗号を利用したタグ検索システムの検索時における処理フローの例を示す図である。
【図９】準同型暗号を利用した暗号処理装置の構成の例を示す構成図である。
【発明を実施するための形態】
【００１５】
以下では、まず、完全準同型暗号を用いた、ハミング距離などの秘匿距離の計算方法について説明する。以下では完全準同型暗号として、イデアル格子ベースの完全準同型暗号を例に説明する。
【００１６】
＜完全準同型暗号を用いた秘匿距離計算＞
まず、準完全準同型暗号方式について説明する。以下で説明する準完全準同型暗号は、イデアル格子ベース準同型暗号とも呼ばれる。この名称は、イデアル格子を用いることで加法的準同型性と乗法的準同型性が導入されることに由来する。
【００１７】
準完全準同型暗号とは、すべてのロジック回路による演算に対して準同型性を満たす暗号である。
【００１８】
準同型性の例としては、加算に関する準同型性や、乗算に関する準同型性がある。加算に関する準同型性や、乗算に関する準同型性とは、例えば、引数ｍ１、ｍ２について、写像（関数）Ｆが、（１）または（２）が成立することである。すなわち、
【００１９】
【数２】
2014126865.tif 000004
が成立する。（１）の場合が加算に関して準同型、（２）の場合が乗算に関して準同型であるという。上の引数ｍ１、ｍ２を平文、写像Ｆとして暗号化関数Ｅｎｃを代入すれば、準同型暗号となる。平文ｍ１、ｍ２から暗号文Ｅｎｃ（ｍ１）、Ｅｎｃ（ｍ２）を得る演算を「暗号化」とも呼ぶ。
【００２０】
準完全準同型暗号方式では、鍵ペア（ｐｋ、ｓｋ）と、平文ｍ１、ｍ２、…、ｍｎの公開鍵ｐｋを用いて暗号化する関数である暗号化関数をＥｎｃ、秘密鍵ｓｋを用いて復号する復号関数をＤｅｃとすると、
【００２１】
【数３】
2014126865.tif 000005
を満たす写像Ｆの存在と、実行が保証される。準完全準同型暗号方式は公開鍵暗号方式である。ここで、Ｆは写像としたが、アルゴリズムであっても良い。さらに、写像Ｆは、加算および乗算の組み合わせによって表現可能であるとする。
【００２２】
上の［数３］は次のことを意味する。左辺のプロセスをプロセスＡと呼び、右辺のプロセスをプロセスＢと呼ぶ。簡単のために、平文ｍ１を考える。プロセスＡの暗号化のステップでは、平文ｍ１を公開鍵ｐｋを用いて暗号化し、暗号データｃ＝Ｅｎｃ（ｍ１）を得る。そして、この暗号データｃについて、公開鍵ｐｋを用いて所定の写像（アルゴリズム）Ｆを作用させる処理が行われ、処理結果ｒを得る。続いて、復号のステップでは、秘密鍵ｓｋを用いて、処理結果ｒの復号処理が行われ、復号結果Ｒ＝Ｄｅｃ（Ｆ（Ｅｎｃ（ｍ１））が生成される。
【００２３】
一方プロセスＢでは、平文ｍ１について、所定の写像（アルゴリズム）Ｆを作用させる処理が行われ、処理結果Ｒ’＝Ｆ（ｍ１）を得る。
【００２４】
上式は、プロセスＡの結果ｒ＝Ｄｅｃ（Ｆ（Ｅｎｃ（ｍ１））と、プロセスＢの結果Ｒ’＝Ｆ（ｍ１）が等しいことを意味する。
【００２５】
さらに、平文ｍ１、ｍ２、…、ｍｎに対する準同型性は、
【００２６】
【数４】
2014126865.tif 000006
を意味する。ここで右辺では、暗号化関数Ｅｎｃの引数は、Ｆ（ｍ１、ｍ２、…、ｍｎ）の一つだけであることに注意する。任意のＦに対して数４が成り立つとき完全準同型性を持つと呼ぶが、上記で説明したイデアル準同型暗号は有限回の加算と乗算の組み合わせで得られる写像Ｆに対してのみ準同型性をもつため、この暗号方式は準完全準同型暗号と呼ぶ。
【００２７】
鍵生成の方法には次のようなものがある。
鍵生成を行う際、次元ｎとビット長ｔの２つのパラメータが必要である。次元ｎとビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）を生成する。このとき、秘密鍵を、行列
【００２８】
【数５】
2014126865.tif 000007
とする。
【００２９】
また、上の行列Ｖのエルミート標準形である行列Ｂを公開鍵とする。エルミート標準形とは、整数行列に対して整数上の行基本変形を施して得られる下または上三角行列である。一般に、エルミート標準形が効率的に計算できることはよく知られており、公開鍵として行列Ｖのエルミート標準形である行列Ｂを用いることで、計算時間を短縮することができる。
【００３０】
暗号化について説明する。１ビットの平文ｂに対して公開鍵Ｂを用いて暗号化する場合、まず成分が０または１のｎ次元乱数ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を選び、ｅ１=（１、０、…、０）として、ベクトルａ：
【００３１】
【数６】
2014126865.tif 000008
を生成する。このようにして得られたベクトルａをフレッシュ暗号文と呼ぶことがある。
【００３２】
１ビットの平文ｂの暗号文ｃは、
【００３３】
【数７】
2014126865.tif 000009
のように生成する。ここで、Ｂ−１は行列Ｂの逆行列とし、「ｑ」は有理数ｑに最も近い整数値を与える関数とする。
【００３４】
１ビットの平文ｂの暗号文ｃの復号は、まず［数８］で定義されるｎ次元ベクトルａ’、
【００３５】
【数８】
2014126865.tif 000010
を計算する。次に、ｎ次元ベクトルａ’の第１成分ａ０’を取り、整数ａ０’を２で割った余りが暗号文ｃを復号した値になる。
【００３６】
また、別の復号方法として、次のような方法が知られている。暗号文ａの第１成分をｃとする。また、ｗを秘密鍵Ｖの逆行列Ｖ−１の要素であり、かつ、奇数のものとする。さらに、
【００３７】
【数９】
2014126865.tif 000011
で、値域が［−ｄ／２、ｄ／２）なるものである。［数９］で、ｄは公開鍵Ｂの判別式とする。このとき、
【００３８】
【数１０】
2014126865.tif 000012
によって、暗号文ｃを定義する。
【００３９】
上記の鍵生成と暗号化、復号の数値例を説明する。次元ｎ＝４、 ビット長ｔ=７に対して説明する。まず、絶対値が７ビット以下の整数となる４次元の乱数ベクトルｖ＝（１１２、９９、−１２５、７７）を選ぶ。このとき、行列Ｖは、
【００４０】
【数１１】
2014126865.tif 000013
を秘密鍵とする。次に、秘密鍵Ｖのエルミート標準形Ｂは、
【００４１】
【数１２】
2014126865.tif 000014
と計算され、この行列Ｂを公開鍵とする。
【００４２】
平文ｂ＝１を、公開鍵Ｂを用いて暗号化する場合を考える。まず、成分が０または１の４次元乱数ベクトルｕ＝（１、０、１、１）を選ぶ。次にフレッシュ暗号文ａを計算する。今の場合、
【００４３】
【数１３】
2014126865.tif 000015
である。すると、平文ｂ＝１の暗号文ｃは、
【００４４】
【数１４】
2014126865.tif 000016
となる。ただし、ａ×Ｂ−１＝（−１３４３０００１３３/１１４３８２１４４９、０、２、２）、「ａ×Ｂ−１」＝（−１、 ０、２、２）となる。結局、暗号文ｃ＝―１９９１７８６８４であることが分かる。
【００４５】
暗号文ｃを、秘密鍵Ｖを用いて復号する場合、まず［数８］で定義される４次元ベクトルａ’を計算する。今の場合、４次元ベクトルａ’＝（３、０、２、２）となる。４次元ベクトルａ’の第１成分を２で割った余りは３＝２＋１なので、暗号文ｃ＝１となり、無事に復号されていることが分かる。上の準同型暗号方式では、４次元ベクトルａと４次元ベクトルａ’が一致する。
【００４６】
上では、平文ｂが１ビットの場合を説明したが、平文の定義域を拡張することができる。平文ｂが｛０、１、…、ｓ−１｝から選択される、すなわち平文空間サイズがｓであるときも、上と同様の方法で、暗号化、復号を行うことができる。
【００４７】
平文空間サイズs以下の平文ｂに対して公開鍵Ｂを用いて暗号化する場合、まず成分が０または１のｎ次元乱数ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を選び、ベクトルａ：
【００４８】
【数１５】
2014126865.tif 000017
を生成する。上と同様、ｅ１=（１、０、…、０）である。このベクトルａもフレッシュ暗号文と呼ぶことがある。平文ｂの暗号文ｃは、上の［数７］と同様、
【００４９】
【数１６】
2014126865.tif 000018
で与えられる。ここでベクトルｃ=（ｃ、０、…、０）となることから、暗号文ｃは整数である。
【００５０】
平文ｂの暗号文ｃの復号は、まず以下のように定義されるｎ次元ベクトルａ’、
【００５１】
【数１７】
2014126865.tif 000019
を計算する。次に、ｎ次元ベクトルａ’の第１成分ａ０’を取り、整数ａ０’を平文空間サイズｓで割った余りが暗号文ｃを復号した値になる。この復号処理は、ベクトルｃに対して行列Ｖ−１を乗算する処理、及び、その乗算によって得られたベクトルに対し、行列Ｖを乗算する処理を行う。つまり、ベクトルと行列の積の計算を２回行うこととなる。このときの乗算回数は、ベクトルの要素数Ｄに比例し２×Ｄ２回となる。また、扱うデータが大きい場合、乗算１回は多倍長の乗算となる。
【００５２】
鍵生成と暗号化・復号化の数値例を説明する。次元ｎ＝４、 ビット長ｔ=７、平文空間サイズｓ＝１３に対して説明する。まず、絶対値が７ビット以下の整数となる４次元の乱数ベクトルｖ＝（１１２、９９、−１２５、８１）を選ぶ。このとき、秘密鍵Ｖは、行列
【００５３】
【数１８】
2014126865.tif 000020
となる。次に、秘密鍵Ｖのエルミート標準形は、
【００５４】
【数１９】
2014126865.tif 000021
と計算され上記の行列Ｂを公開鍵とする。
【００５５】
次に、平文空間サイズｓ＝１３以下の平文ｂ＝３に対し公開鍵Ｂを用いて暗号化する場合を考える。まず、成分が０または１の４次元乱数ベクトルｕ＝（１、０、１、１）を選ぶ。ベクトルａは、ａ＝(１６、０、１３、１３）となる。次に平文ｂ＝３の暗号文ｃは、
【００５６】
【数２０】
2014126865.tif 000022
となる。ただし、ａ×Ｂ−１＝（−８７２９５００８６８／１１４３８２１４４９、０、１３、１３）、「ａ×Ｂ−１」＝（−８、０、１３、１３）となる。
【００５７】
暗号文ｃを秘密鍵Ｖを用いて復号する場合、まず４次元ベクトルａ’＝（１６、０、１３、１３）を計算する。この４次元ベクトルａ’の第１成分を平文空間サイズｓ＝１３で割った余り３が復号した値になる。
【００５８】
また、暗号データの加算と乗算を説明する。上記の数値例のように、暗号文は必ず第一成分以外が０となるｎ次元ベクトルｃ=（ｃ１、０、…）として表せる。この暗号文の第１成分の整数は、平文ｂと平文空間サイズｓと暗号化で利用するｎ次元ベクトルｕ=（ｕ０、ｕ１、…、ｕｎ−１）を用いて、
【００５９】
【数２１】
2014126865.tif 000023
として計算することも可能である。ただし、［ｘ］ｄは、
【００６０】
【数２２】
2014126865.tif 000024
であり、値域が［−ｄ／２、ｄ／２）なる整数であり、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分である。上の例では、ｄ＝１１４３８２１４４９、ｒ＝９８２６２３５４８となる。これにより、暗号文を整数データとしてみなすことができる。
【００６１】
２つの暗号文ｃ１、ｃ２に対し、暗号加算は[ｃ１＋ｃ２]ｄ、暗号乗算は[ｃ１×ｃ２]ｄとして定義される。
【００６２】
上のような準同型暗号の性質を、２つのベクトルデータの比較に適用するためには、例えば以下のようにすれば良い。
【００６３】
ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）とベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）があるとする。ここでは、ベクトルデータＡとベクトルデータＢは、ｎ次元ベクトル量として書けるものとする。
【００６４】
ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）に対して、変換多項式、
【００６５】
【数２３】
2014126865.tif 000025
を計算する。そして、変換多項式ａ（ｘ）を暗号化して暗号データＥｎｃ（ａ（ｘ））を計算する。今の場合、
【００６６】
【数２４】
2014126865.tif 000026
とする。
【００６７】
ベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）に対して、変換多項式、
【００６８】
【数２５】
2014126865.tif 000027
を計算する。そして、変換多項式ｂ（ｘ）を暗号化して暗号データＥｎｃ（ｂ（ｘ））を計算する。ベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）に対する変換多項式は、ベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）に対するものとは異なっている。
【００６９】
＜準同型暗号を用いた秘匿距離計算＞
次に、秘匿距離計算を行うために、事前に２つの整数Ｃ１、Ｃ２を用意する。の整数Ｃ１、Ｃ２は次の［数２６］で定義される。
【００７０】
【数２６】
2014126865.tif 000028
このとき、秘匿距離ｄは、
【００７１】
【数２７】
2014126865.tif 000029
である。［数２７］で、Ｃ１×Ｅｎｃ（ａ（ｘ））、Ｃ２×Ｅｎｃ（ｂ（ｘ））はそれぞれ、暗号文上のハミング重みＨＷ（ａ）、ＨＷ（ｂ）に対応する。上の秘匿距離ｄを復号すると、２つのベクトルデータＡ＝（ａ１、ａ２、…、ａｎ）とベクトルデータＢ＝（ｂ１、ｂ２、…、ｂｎ）のハミング距離となる。上記では秘匿距離としてハミング距離を用いたが、開示の方法は、ユークリッド距離などの距離計算やコサイン類似度などの類似度計算にも適用可能である。
【００７２】
ここで、数値例を示す。ベクトルデータＡ＝（１、０、１、１）とベクトルデーＢ＝（０、０、１、０）に対して、ベクトルデータＡ、Ｂを暗号化したままハミング距離を計算することを考える。ベクトルデータＡ＝（１、０、１、１）とベクトルデーＢ＝（０、０、１、０）のハミング距離は２であることは明らかである。
【００７３】
ベクトルデータＡ＝（１、０、１、１）に対して、変換多項式ａ（ｘ）＝１＋ｘ２＋ｘ３とハミング重みＨＷ（Ａ） =１＋１＋１＝３を計算する。次に、公開鍵行列Ｂを上記に示したものとし、ｄ＝１１４３８２１４４９、ｒ＝９８２６２３５４８とする。ここで、２つのデータｄと ｒのみあれば暗号化可能であることに注意する。また、平文空間サイズｓ＝４とする。変換多項式ａ（ｘ）の暗号データは、上の［数１９］を用いて、Ｅｎｃ（ａ（ｘ））＝−５７０７５８８３１となる。４次元乱数ベクトルｕ＝（０、１、１、０）としている。ハミング重みＨＷ（Ａ）＝３を暗号化した暗号データＥｎｃ（ＨＷ（Ａ））は、４次元乱数ベクトルｕ＝（１、０、０、１）として、
【００７４】
【数２８】
2014126865.tif 000030
となる。
【００７５】
同様に、ベクトルデータＢ＝（０、０、１、０）に対して、変換多項式ｂ（ｘ）＝ｘ２とハミング重みＨＷ（Ｂ）＝１を計算する。ハミング重みＨＷ（Ｂ）＝１を暗号化した暗号データＥｎｃ（ＨＷ（Ｂ））は、４次元乱数ベクトルｕ＝（０、０、０、１）として、
【００７６】
【数２９】
2014126865.tif 000031
となる。
【００７７】
秘匿距離ｄは、Ｅｎｃ（ＨＷ（Ａ））、Ｅｎｃ（ＨＷ（Ｂ））、Ｅｎｃ（ａ（ｘ））、およびＥｎｃ（ｂ（ｘ））を用いて、秘匿距離ｄ＝Ｅｎｃ（ＨＷ（Ａ））＋Ｅｎｃ（ＨＷ（Ｂ））＋２×Ｅｎｃ（ａ（ｘ））×Ｅｎｃ（ｂ（ｘ））＝５８１４７３５９となる。
【００７８】
最後に、この暗号データｄに対して秘密鍵行列Ｖを用いて復号すると、ｄ=（５８１４７３５９、０、０、０）として、ｃ−［ｃ×Ｖ−１］×Ｖ＝（１０、３０、−４２、１１）である。このベクトルデータの第１成分に対して、平文空間サイズｓ＝４で割った余りを考えると、復号結果は２となり、これが２つのベクトルデータＡ、 Ｂのハミング距離に一致する。
【００７９】
また、上では[数２６]、[数２７]を用いたが、ｂ（ｘ）、Ｃ２をそれぞれ、次式のようなｂ’（ｘ）、Ｃ２’
【００８０】
【数３０】
2014126865.tif 000032
に置きかえ、秘匿距離ｄを、
【００８１】
【数３１】
2014126865.tif 000033
のように定義しても良い。上の［数３１］の右辺第３項の符号が、［数２７］のものとは異なっていることに注意しよう。［数３１］は、
【００８２】
【数３２】
2014126865.tif 000034
と計算することも可能である。
【００８３】
以上のように、開示の方法は次のような特徴を有している。
（１）格子ベース準同型暗号を利用する、
（２）特徴量を表すベクトルを変換多項式によって多項式に変換する、
（３）変換多項式の暗号文とベクトルのハミング重みなどの重みの暗号文を用いる、
（４）秘匿距離計算として準同型暗号の多項式演算に関する準同型性を利用する。
このように、ハミング距離などの秘匿距離の計算に、準同型暗号を用いることによって、暗号データサイズと計算時間の大幅な削減が可能となる。
【００８４】
上のイデアル格子ベース準同型暗号の暗号化、復号は、次のように説明することもできる。
【００８５】
まず、用語を簡単に定義する。
格子とはＺを整数環として、Ｚｎ中の離散的な加法的部分群である。Ｚｎ中でｂ０、…、ｂｎ−１が線形独立だとすると、これらを並べて作られる正方行列Ｂ＝［ｂ０、…、ｂｎー１］を基底と呼ぶ。格子Ｌは、ｖをＺｎの要素として、
【００８６】
【数３３】
2014126865.tif 000035
と書くことができる。
【００８７】
格子Ｌがイデアル格子であるとは、格子Ｌと同型な環Ｒ＝Ｚ［ｘ］／ｆ（ｘ）のイデアルＩが存在することである。ここで、Ｚ［ｘ］は整数係数多項式環、ｆ（ｘ）は整数係数モニックなｎ次多項式である。
【００８８】
剰余環Ｒの１つの元、
【００８９】
【数３４】
2014126865.tif 000036
で生成される単項イデアルの元は、ａ、ａ・ｘ、ａ・ｘ２、ａ・ｘｎ−１の線形結合で書ける。ａの転置をａＴと書く。
【００９０】
ｆ（ｘ）＝ｘｎ＋１として、環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）の整数係数モニック多項式ａ（ｘ）＝ａ０＋ａ１ｘ＋…＋ａｎ-１ｘｎ−１を考える。ベクトルａ＝（ａ０、ａ１、…、ａｎ−１）を環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）と同一視するためには、次のようにする。ａに対して巡回行列を定義する。
【００９１】
【数３５】
2014126865.tif 000037
これは上の［数５］と同一である。すると、２つの多項式ａ（ｘ）、ｂ（ｘ）に対して、積をａ（ｘ）・ｂ（ｘ）＝Ｒｏｔ（ａ）・ｂによって定義することができる。また、巡回行列Ｒｏｔ（ａ）は、基底行列となる。
【００９２】
すると、上の格子ベースの準同型暗号方法における鍵生成とは次のようなことである。つまり、環Ｒ＝Ｚ［ｘ］／（ｘｎ＋１）のイデアルＩと互いに素なイデアルＪの基底行列を秘密鍵Ｖ、公開鍵Ｂはその基底行列のエルミート標準形である。たとえば、秘密鍵はＲをランダム、かつノルムの小さな行列として、ｎ１／２Ｉ＋Ｒとすることができる。
【００９３】
このとき、暗号化は、平文ｂの暗号文ｃは、ｒをＲから選び、ｃ＝ｂ＋ｒｓ  ｍｏｄ  Ｂの第１成分とする。平文ｂのノルムが小さければ、ｂ＝（ｃ  ｍｏｄ  Ｂ）ｍｏｄ  Ｉにより復号することができる。
【００９４】
上記のような格子ベースの準完全準同型暗号を用いてハミング距離などの秘匿距離を計算することによって、暗号ベクトルデータのサイズと秘匿距離計算の時間の両方を削減することができる。
【００９５】
上で説明した準同型暗号方式は、生体認証システム、タグ検索システムなどへの応用が考えられる。
【００９６】
また、上で説明した準同型暗号方式は、例えば、後述するように、図９に示されている装置によって実装され得る。
【００９７】
そのような暗号処理装置は、以下の実施例で説明されるように、多項式変換部と、重み計算部と、準同型暗号化部と、秘匿距離計算部と、を含むことを特徴とする。多項式変換部は、第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る。重み計算部は、多項式変換部と、前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る。準同型暗号化部は、前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得る。秘匿距離計算部は、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る。
【００９８】
＜第１実施例＞
図１〜４を参照して、上記のイデアル格子ベース完全準同型暗号を用いた暗号処理装置の例としての生体認証システムについて説明する。
【００９９】
生体認証システムでは、個人ごとに固有の情報である、音声、指紋、静脈パターン、顔、虹彩など生体情報を用いて、利用者が正規のユーザであることを認証する。生体情報は、重要な個人情報であるため、認証の際にも暗号化した情報が用いられることが好ましい。利用者が正規のユーザであるか否かを判定するために、認証されるユーザの生体情報が、予め登録されている生体情報と比較されるが、その比較の際に、準同型暗号を用いることによって、暗号化された情報同士を比較することができる。
【０１００】
図１Ａおよび１Ｂは、準同型暗号を利用した生体認証システムの概略を示す図である。図１Ａは、生体認証に用いられる参照情報の登録時の生体認証システムの概略を示す図である。図１Ｂは、ユーザが正規ユーザであるかどうかを判定する照合時の生体認証システムの概略を示す図である。
【０１０１】
図１Ａおよび１Ｂに示されている生体認証システムは、指紋や静脈などの生体情報を利用した個人認証システムである。生体情報を利用した個人認証システムは、パスワードなどの複雑な情報を覚える必要がないため利用しやすい個人認証方式である反面、生体情報は各ユーザにとって終生不変な機密情報であるので生体情報漏洩などに対して強く保護しなければならない。図１Ａおよび１Ｂに示されている生体認証システムでは、ユーザの生体情報を準同型暗号で保護しつつ認証が可能となる方式である。
【０１０２】
図１Ａに示されているように、生体認証に用いられる参照情報を登録するとき、登録センサは正規ユーザの生体の一部の特徴量を抽出し、その特徴量をベクトル化する。さらにそのベクトル化された特徴量を準同型暗号化する。さらに、登録センサは準同型暗号化された特徴量を計算サーバに送信し、計算サーバのデータベースに暗号登録データとして登録しておく。
【０１０３】
図１Ｂに示されているように、ユーザが正規ユーザであるかを認証するために、照合センサはユーザの生体の一部の特徴量を抽出し、その特徴量をベクトル化する。さらにそのベクトル化された特徴量を準同型暗号化する。そして準同型暗号化された特徴量を計算サーバに送信する。計算サーバでは、受け取った準同型暗号化された特徴量と登録されている暗号登録データの間の秘匿距離を計算し、秘匿距離計算結果を得る。そして、秘匿距離計算結果を準同型暗号の秘密鍵を持つ認証局に送信する。認証局は、送信された秘匿距離計算結果を復号し、復号結果と閾値を比較し、復号結果が閾値よりも小さい場合は、ユーザを認証する。本実施例では、秘匿距離としてハミング距離を用いる。
【０１０４】
図１Ａおよび１Ｂに示されている生体認証システムでは、予め登録されている特徴量と、認証されるべきユーザの特徴量の２つのデータのハミング距離を、準同型暗号化した状態で計算することができる。よって、計算サーバには準同型暗号化生体ベクトルデータをのみを送信し、計算サーバは秘密鍵を持たないため、ユーザの生体情報を知ることはできず、情報が秘匿される。また、認証局も秘匿距離計算結果のみを復号するので、ユーザの生の生体情報、すなわち暗号化されていない特徴量を知ることはできない。これにより、ユーザの生体情報を保護したまま個人認証サービスを受けることができる。
【０１０５】
＜生体認証システムの構成＞
図２Ａおよび２Ｂを参照して、図１Ａおよび１Ｂに示されている生体認証システムについて詳細に説明する。
【０１０６】
図２Ａは、準同型暗号を利用した生体認証システムの登録時における構成の例である生体認証システム１０を示すブロック図である。
【０１０７】
生体認証システム１０は、登録センサ２０と計算サーバ３０を含む。登録センサ２０は、特徴量抽出部２０２、ベクトル化部２０４、多項式変換部２０６、Ｈａｍｍｉｎｇ（ハミング）重み計算部２０８、および準同型暗号部２１０を含む。これらを、第１の特徴量抽出部２０２、第１のベクトル化部２０４、第１の多項式変換部２０６、第１のＨａｍｍｉｎｇ重み計算部２０８、および第１の準同型暗号部２１０として参照することもある。また、第１のＨａｍｍｉｎｇ重み計算部２０８は単に重み計算部２０８として参照することもある。
【０１０８】
計算サーバ３０は、正規ユーザ４０の生体情報を参照情報として格納する暗号登録データ３０２を含む。図２Ａには図示されていないが、計算サーバ３０は、図２Ｂに示されているように、準同型暗号化された２つのデータの加算演算を行う暗号乗算部３０４、準同型暗号化されたデータのスカラー倍の計算を行う暗号スカラー部３０６、および準同型暗号化された２つのデータの加算演算を行う暗号加算部３０８を含む。
【０１０９】
暗号乗算部３０４、暗号スカラー部３０６、および暗号加算部３０８は組み合わされて、秘匿距離計算部を構成する。
【０１１０】
特徴量抽出部２０２では、正規ユーザとして登録されるユーザ４０の生体の情報の一部をセンサから取得し、特徴量を抽出する。特徴量としては、図１Ａに示されているように指紋であっても良い。このように、第１の特徴抽出部２０２は、正規ユーザの生体の一部に関する情報から正規ユーザを他のユーザから区別する特徴を第１の特徴量として抽出する。
【０１１１】
ベクトル化部２０４では、特徴量抽出部２０２で抽出された特徴量をｎ次元ベクトルａとして表現する。例えば、ベクトルａは、ａ０、…、ａｎ−１を０または１として、
【０１１２】
【数３６】
2014126865.tif 000038
のように表される。このように第１のベクトル化部２０４は、第１の特徴量を、第１のベクトルａとして表現する。
【０１１３】
多項式変換部２０６では、ベクトル化部２０４で得られたベクトルａを多項式に変換する。例えば、変換多項式、
【０１１４】
【数３７】
2014126865.tif 000039
を計算する。このように（第１の）多項式変換部２０６は、第１のベクトルａから第１の変換多項式を用いて第１の多項式ａ（ｘ）を得る。
【０１１５】
Ｈａｍｍｉｎｇ重み計算部２０８では、ベクトルａのハミング重みＨＷ（ａ）を計算する。今の場合、ハミング重みＨＷ（ａ）は、
【０１１６】
【数３８】
2014126865.tif 000040
である。このように（第１の）重み計算部２０８は、第１のベクトルａの秘匿距離に関する第１の重みＨＷ（ａ）を計算する。今の場合、秘匿距離はハミング距離であり、第１の重みはハミング重みである。
【０１１７】
準同型暗号化部２１０では、多項式変換部２０６で得られた多項式ａ（ｘ）とＨａｍｍｉｎｇ重み計算部２０８で得られたハミング重みＨＷ（ａ）を暗号化し、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））、
【０１１８】
【数３９】
2014126865.tif 000041
を得る。このように、（第１の）準同型暗号化部２１０は、第１の多項式ａ（ｘ）、第１の重みＨｗ（ａ）のそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式Ｅｎｃ（ａ（ｘ））および第１の暗号化重みＥｎｃ（ＨＷ（ａ））を得る。ここで、［数３６］にあるＥｎｃ(ＨＷ(ａ))の方のｕｉと、Ｅｎｃ(ａ(ｘ))のｕｉ’とは異なる乱数であってもよい。Ｅｎｃ(ｂ(ｘ))とＥｎｃ(ＨＷ(ｂ))についても同様である。
【０１１９】
準同型暗号化部２１０で得られた暗号化データＥｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））は、計算サーバ３０に送られ登録データとして暗号登録データ３０２に格納される。
【０１２０】
図２Ｂは、準同型暗号を利用した生体認証システムの照合時における構成の例である生体認証システム５０を示すブロック図である。
【０１２１】
生体認証システム５０は、照合センサ６０、計算サーバ３０、および認証局７０を含む。照合センサ６０は、特徴量抽出部６０２、ベクトル化部６０４、多項式変換部６０６、Ｈａｍｍｉｎｇ（ハミング）重み計算部６０８、および準同型暗号部６１０を含む。これらはぞれぞれ、登録センサ２０の特徴量抽出部２０２、ベクトル化部２０４、多項式変換部２０６、Ｈａｍｍｉｎｇ（ハミング）重み計算部２０８、および準同型暗号部２１０と同一または類似の構成を有する。またこれらを、第２の特徴量抽出部６０２、第２のベクトル化部６０４、第２の多項式変換部６０６、第２のＨａｍｍｉｎｇ重み計算部６０８、および第２の準同型暗号部６１０として参照することもある。第１の特徴量抽出部２０２、第１のベクトル化部２０４、第１の多項式変換部２０６、第１のＨａｍｍｉｎｇ重み計算部２０８、および第１の準同型暗号部２１０と、第２の特徴量抽出部６０２、第２のベクトル化部６０４、第２の多項式変換部６０６、第２のＨａｍｍｉｎｇ重み計算部６０８、および第２の準同型暗号部６１０を区別せずに参照することもある。また、第２のＨａｍｍｉｎｇ重み計算部６０８は単に重み計算部２０８として参照することもある。
【０１２２】
特徴量抽出部６０２では、認証するユーザ８０の生体の情報の一部をセンサから取得し、特徴量を抽出する。特徴量としては、図１Ｂに示されているように指紋であっても良い。このように、第２の特徴量抽出部６０２は、正規ユーザとして認証されるべきユーザの生体の一部に関する情報から前記正規ユーザの前記第１の特徴量と比較される第２の特徴量を抽出する。
【０１２３】
ベクトル化部６０４では、特徴量抽出部６０２で抽出された特徴量をｎ次元ベクトルｂとして表現する。例えば、ベクトルｂは、ｂ０、…、ｂｎ−１を０または１として、
【０１２４】
【数４０】
2014126865.tif 000042
のように表される。このように、第２のベクトル化部６０４は、第２の特徴量を、第２のベクトルｂとして表現する。
【０１２５】
多項式変換部６０６では、ベクトル化部６０４で得られたベクトルｂを多項式に変換する。
【０１２６】
【数４１】
2014126865.tif 000043
を計算する。照合時の変換多項式ｂ（ｘ）は、登録時の変換多項式ａ（ｘ）とは異なっていることに注意する。このように（第２の）多項式変換部６０６は、第２のベクトルｂから第２の変換多項式を用いて第２の多項式ｂ（ｘ）を得る。
【０１２７】
Ｈａｍｍｉｎｇ重み計算部６０８では、ベクトルｂのハミング重みＨＷ（ｂ）を計算する。今の場合、ハミング重みＨＷ（ｂ）は、
【０１２８】
【数４２】
2014126865.tif 000044
である。このように（第２の）重み計算部６０８は、第２のベクトルｂの秘匿距離に関する第２の重みＨＷ（ｂ）を計算する。今の場合、秘匿距離はハミング距離であり、第２の重みはハミング重みである。
【０１２９】
多項式変換部６０６で得られた多項式とＨａｍｍｉｎｇ重み計算部６０８で得られたハミング重みＨＷ（ｂ）は、準同型暗号化部６１０で暗号化され、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））が得られる。このように、（第２の）準同型暗号化部６１０は、第２の多項式ｂ（ｘ）、第２の重みＨＷ（ｂ）のそれぞれを、準同型暗号方式を用いて暗号化し、第２の暗号化多項式Ｅｎｃ（ｂ（ｘ））および第２の暗号化重みＥｎｃ（ＨＷ（ｂ））を得る。
【０１３０】
準同型暗号化部６１０で得られた暗号化データＥｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））は、計算サーバ３０に送られる。Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））はそれぞれ、上式［数３８］および［数３９］において、ａ（ｘ）をｂ（ｘ）と置き換えたものである。
【０１３１】
計算サーバ３０の暗号乗算部３０４では、暗号登録データ３０２に格納されているＥｎｃ（ａ（ｘ））と準同型暗号化部６１０で得られたＥｎｃ（ｂ（ｘ））の積
【０１３２】
【数４３】
2014126865.tif 000045
を計算する。
【０１３３】
暗号スカラー部３０６では、事前に計算された２つの整数、
【０１３４】
【数４４】
2014126865.tif 000046
と、Ｅｎｃ（ａ（ｘ）））とＥｎｃ（ｂ（ｘ））との積、
【０１３５】
【数４５】
2014126865.tif 000047
を計算する。また、暗号スカラー部３０６では、暗号乗算部３０４で得られたＣ１の２倍、
【０１３６】
【数４６】
2014126865.tif 000048
を計算する。
【０１３７】
暗号加算部３０８では、ｋ１×Ｅｎｃ（ＨＷ（ａ））、ｋ２×Ｅｎｃ（ＨＷ（ｂ））、２×Ｅｎｃ（ａ（ｘ）））×Ｅｎｃ（ｂ（ｘ））の和を計算し、秘匿距離として［数４４］で表されるハミング距離Ｄを算出する。
【０１３８】
【数４７】
2014126865.tif 000049
このように、秘匿距離計算部では、第１の暗号化多項式Ｅｎｃ（ａ（ｘ）））、第２の暗号化多項式Ｅｎｃ（ｂ（ｘ））、第１の暗号化重みＥｎｃ（ＨＷ（ａ））、および第２の暗号化重みＥｎｃ（ＨＷ（ｂ））から、第１のベクトルａと第２のベクトルｂの秘匿距離の暗号化に対応する暗号化秘匿距離（ハミング距離）Ｄを得る。そして、ハミング距離Ｄのみを認証局７０に送信する。
【０１３９】
計算サーバ３０と認証局７０の通信では、公開鍵暗号が用いられ、通信データの秘匿性を確保する。
【０１４０】
この際の鍵は、予め設定された次元ｎとビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）を用いて、秘密鍵を［数４０］のような行列Ｖとする。
【０１４１】
【数４８】
2014126865.tif 000050
また、公開鍵は、上の秘密鍵である行列Ｖのエルミート標準である行列Ｂとする。
【０１４２】
認証局７０は、秘密鍵７０２、復号処理部７０４および判定処理部７０６を含む。
秘密鍵７０２には、上記［数４８］で表される秘密鍵Ｖか格納される。
【０１４３】
復号処理部７０４では、秘密鍵Ｖを用いて、計算サーバ３０から送られた準同型暗号化されたハミング距離Ｄを復号する。復号して得られるハミング距離Ｄ’は、
【０１４４】
【数４９】
2014126865.tif 000051
と計算される。このように復号処理部７０２は、暗号化秘匿距離を復号して前記秘匿距離を算出する。
【０１４５】
判定処理部７０６では、復号されたハミング距離Ｄ’を予め用意された閾値Ｄｔｈと比較する。そして、Ｄ’＜Ｄｔｈの場合は、ベクトルｂで表される特徴量は、ベクトルａで表される特徴量と同一であると判定し、ユーザ８０を正規ユーザとして認証する。このように、判定処理部７０６は、秘匿距離Ｄ’と予め決められた閾値Ｄｔｈとの比較に基づいて、ユーザを正規ユーザであるかどうかを判定する。
【０１４６】
このような生体認証システムでは、生体情報ベクトルの次元はｎ＝５１２を利用することが多く、個々のビットを比べる場合には５１２個の暗号文が必要なのに対し、本実施例では２個の暗号文となるため、２５６倍の暗号データサイズの削減が可能となる。
【０１４７】
また、秘匿距離計算時間については、個々のビットを比べる場合には
【０１４８】
【数５０】
2014126865.tif 000052
を計算する必要があるため５１２回の暗号乗算が必要であったのに対し、本実施例では、［数４７］の演算をすればよく、暗号操作関数の中で暗号乗算の処理時間が最も大きく、暗号乗算は１回の演算だけで秘匿距離計算可能となり、約５１２倍の高速化が実現できる。
【０１４９】
＜生体認証システムの処理＞
図３および４を参照して、生体認証システムにおける処理の例を説明する。図３は、準同型暗号を利用した生体認証システムの登録時における処理フローの例を示す図である。
【０１５０】
まず処理が開始されると、登録センサ２０では、ステップＳ１０２で、正規ユーザとして登録されるユーザ４０の生体の情報の一部をセンサから取得し、特徴量を抽出する。そして、処理はＳ１０４に進む。この処理は、登録センサ２０の特徴量抽出部２０２で行われ得る。
【０１５１】
Ｓ１０４では、Ｓ１０２で抽出された特徴量をｎ次元ベクトルａとして表現する。この処理は登録センサ２０のベクトル化部２０４で行われ得る。
【０１５２】
次のＳ１０６では、ｎ次元ベクトルａを多項式に変換する。この処理は登録センサ２０の多項式変換部２０６で行われ得る。
【０１５３】
Ｓ１０６の次のＳ１０８では、ｎ次元ベクトルａに対するハミング重みＨＷ（ａ）が計算される。この処理は登録センサ２０のＨａｍｍｉｎｇ重み計算部２０８で行われ得る。
【０１５４】
次のＳ１１０では、Ｓ１０６で得られた多項式ａ（ｘ）とＳ１０８で得られたハミング重みＨＷ（ａ）を暗号化し、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））を得る。これらのデータ、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））は計算サーバ３０に送られる。本ステップの処理は登録センサ２０の準同型暗号化部２１０で行われ得る。
【０１５５】
Ｓ１１２では、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））をデータベース、例えば、計算サーバ３０の暗号登録データ３０２に格納する。
そして、登録処理を終了する。
【０１５６】
図４は、準同型暗号を利用した生体認証システムの照合時における処理フローの例を示す図である。
【０１５７】
処理が開始されると、照合センサ６０では、ステップＳ２０２で、認証するユーザ８０の生体の情報の一部をセンサから取得し、特徴量を抽出する。そして、処理はＳ２０４に進む。この処理は、照合センサ６０の特徴量抽出部６０２で行われ得る。
【０１５８】
Ｓ２０４では、Ｓ２０２で抽出された特徴量をｎ次元ベクトルｂとして表現する。この処理は照合センサ６０のベクトル化部６０４で行われ得る。
【０１５９】
次のＳ１０６では、ｎ次元ベクトルａを多項式に変換する。この処理は登録センサ２０の多項式変換部６０６で行われ得る。
【０１６０】
Ｓ２０６の次のＳ２０８では、ｎ次元ベクトルａに対するハミング重みＨＷ（ｂ）が計算される。この処理は照合センサ６０のＨａｍｍｉｎｇ重み計算部６０８で行われ得る。
【０１６１】
次のＳ２１０では、Ｓ２０６で得られた多項式ｂ（ｘ）とＳ１０８で得られたハミング重みＨＷ（ｂ）を暗号化し、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））を得る。これらのデータ、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））を計算サーバ３０に送られる。本ステップの処理は照合センサ６０の準同型暗号化部６１０で行われ得る。
【０１６２】
Ｓ２１２では、暗号登録データ３０２に格納されているＥｎｃ（ａ（ｘ））とＳ２１０で得られたＥｎｃ（ｂ（ｘ））の積Ｅｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））を計算する。この処理は、計算サーバ３０の暗号乗算部３０４で行われ得る。
【０１６３】
Ｓ２１４では、［数４４］の２つの整数、ｋ１、ｋ２と、Ｅｎｃ（ａ（ｘ）））とＥｎｃ（ｂ（ｘ））との積、ｋ１Ｅｎｃ（ａ（ｘ）））、ｋ２Ｅｎｃ（ｂ（ｘ））が計算される。また、Ｓ２１４では、Ｓ２１０で得られたＥｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））の２倍、２Ｅｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））を計算する。本ステップの処理は、計算サーバ３０の暗号スカラー部３０６で行われ得る。
【０１６４】
Ｓ２１６では、ｋ１×Ｅｎｃ（ＨＷ（ａ））、ｋ２×Ｅｎｃ（ＨＷ（ｂ））、２×Ｅｎｃ（ａ（ｘ）））×Ｅｎｃ（ｂ（ｘ））の和を計算し、秘匿距離として［数４７］で表されるハミング距離Ｄを算出する。ハミング距離Ｄのみを認証局７０に送信する。本ステップの処理は、計算サーバ３０の暗号加算部３０８で行われ得る。
【０１６５】
次のＳ２１８では、［数４８］のような秘密鍵Ｖを用いて、計算サーバ３０から送られた準同型暗号化されたハミング距離Ｄを復号する。秘密鍵Ｖは認証局７０の暗号登録データ７０２に格納されていても良い。本ステップの処理は、認証局７０の復号処理部７０４で行われ得る。
【０１６６】
Ｓ２２０では、復号されたハミング距離Ｄ’を予め用意された閾値ｄｔｈと比較する。そして、Ｄ’＜ｄｔｈの場合は、ベクトルｂで表される特徴量は、ベクトルａで表される特徴量と同一であると判定し、ユーザ８０を正規ユーザとして認証する。本ステップの処理は、認証局７０の判定処理部７０６で行われ得る。
【０１６７】
Ｓ２２２では、Ｓ２２０の結果を出力する。この処理は、不図示の表示装置によって行われ得る。
そして、照合処理を終了する。
【０１６８】
＜第２実施例＞
図５Ａ〜８を参照して、上記のイデアル格子ベース完全準同型暗号を用いた暗号処理装置の例としてのタグ検索システムについて説明する。
【０１６９】
タグ検索システムは、クラウドストレージに写真やドキュメントを格納する際に、その資料に関連するタグを付与することで、検索を高速に行うためのシステムである。クラウドストレージに格納される写真やドキュメントは、仕事に関連するものであったり、旅行などプライベートなものであったりするので、秘匿性の高いデータであることがある。
【０１７０】
図５Ａに示されているように、データの保存時には、ユーザは、自身が所有するパーソナルコンピュータ（ＰＣ）内でタグをベクトル化し、さらにベクトル化したタグを準同型暗号で秘匿した暗号データを作成する。そして、暗号データのみをクラウドのデータベースに保存する。
【０１７１】
図５Ｂに示されているように、タグ検索時には、ＰＣ内で検索タグをベクトル化しベクトル化タグを準同型暗号で秘匿したデータのみをクラウドに送信する。クラウド内では、２つの準同型暗号化されたベクトルの距離を暗号化したまま２つのデータの秘匿距離を計算し、秘匿距離の計算結果のみをユーザＰＣに返す。最後に、ユーザＰＣは秘密鍵を用いて秘匿距離計算結果を復号して、２つのベクトルデータが類似しているか判定する。
【０１７２】
＜タグ検索システムの構成＞
図６Ａおよび６Ｂを参照して、図５Ａおよび５Ｂに示されているタグ検索システムについて詳細に説明する。
【０１７３】
図６Ａは、準同型暗号を利用したタグ検索システムの保存時における構成の例であるタグ検索システム１００を示すブロック図である。
【０１７４】
タグ検索システム１００は、ユーザＰＣ１１０とクラウド１２０を含む。ユーザＰＣ１１０は、ベクトル化部１１０２、多項式変換部１１０４、Ｈａｍｍｉｎｇ（ハミング）重み計算部１１０６、および準同型暗号部１１０８を含む。これらを、第１のベクトル化部１１０２、第１の多項式変換部１１０４、第１のＨａｍｍｉｎｇ重み計算部１１０６、および第１の準同型暗号部１１０８として参照することもある。また、第１のＨａｍｍｉｎｇ重み計算部１１０６は単に重み計算部１１０６として参照することもある。
【０１７５】
クラウド１２０は、テキストデータをタグとして格納する暗号登録データ１２０２を含む。図６Ａには図示されていないが、クラウド１２０は、図６Ｂに示されているように、準同型暗号化された２つのデータの加算演算を行う暗号乗算部１２０４、準同型暗号化されたデータのスカラー倍の計算を行う暗号スカラー部１２０６、および準同型暗号化された２つのデータの加算演算を行う暗号加算部１２０８を含む。
【０１７６】
暗号乗算部１２０４、暗号スカラー部１２０６、および暗号加算部１２０８は組み合わされて、秘匿距離計算部を構成する。
【０１７７】
ベクトル化部１１０４では、入力されたテキストデータをｎ次元ベクトルａとして表現する。例えば、ベクトルａは、ａ０、…、ａｎ−１を０または１として、
【０１７８】
【数５１】
2014126865.tif 000053
のように表される。テキストデータとしては、キーワードとなり得るものが好ましい。例えば、仕事に関連するものであれば、プロジェクト名や日付などであり得る。またプライベートの旅行に関連するものであれば、旅行先の地名や日付などであり得る。また、子供の成長記録のような場合には、名前と日付の組み合わせであっても良い。このように第１のベクトル化部１１０４は、入力された（第１の）テキストデータを、第１のベクトルａとして表現する。
【０１７９】
多項式変換部１１０６では、ベクトル化部１１０４で得られたベクトルａを多項式に変換する。例えば、変換多項式
【０１８０】
【数５２】
2014126865.tif 000054
を計算する。このように（第１の）多項式変換部１１０６は、第１のベクトルａから第１の変換多項式を用いて第１の多項式ａ（ｘ）を得る。
【０１８１】
Ｈａｍｍｉｎｇ重み計算部１１０８では、ベクトルａのハミング重みＨＷ（ａ）を計算する。今の場合、ハミング重みＨＷ（ａ）は、
【０１８２】
【数５３】
2014126865.tif 000055
である。このように（第１の）重み計算部１１０８は、第１のベクトルａの秘匿距離に関する第１の重みＨＷ（ａ）を計算する。今の場合、秘匿距離はハミング距離であり、第１の重みはハミング重みである。
【０１８３】
準同型暗号化部１１１０では、多項式変換部１１０６で得られた多項式ａ（ｘ）とＨａｍｍｉｎｇ重み計算部１１０８で得られたハミング重みＨＷ（ａ）を暗号化し、Ｅｎｃ（ａ（ｘ））、
【０１８４】
【数５４】
2014126865.tif 000056
とＥｎｃ（ＨＷ（ａ））
【０１８５】
【数５５】
2014126865.tif 000057
を得る。このように、（第１の）準同型暗号化部１１１０は、第１の多項式ａ（ｘ）、第１の重みＨＷ（ａ）のそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式Ｅｎｃ（ａ（ｘ））および第１の暗号化重みＥｎｃ（ＨＷ（ａ））を得る。
【０１８６】
準同型暗号化部１１１０で得られた暗号化データＥｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））は、クラウド１２０に送られ登録データとして暗号登録データ１２０２に格納される。
【０１８７】
図６Ｂは、準同型暗号を利用したタグ検索システムの検索時における構成の例である生体認証システム１５０を示すブロック図である。
【０１８８】
タグ検索システム１５０は、ユーザＰＣ１６０、およびクラウド１２０を含む。ユーザＰＣ１６０は、ベクトル化部１６０２、多項式変換部１６０４、Ｈａｍｍｉｎｇ（ハミング）重み計算部１６０６、準同型暗号部１６０８を含む。これらはぞれぞれ、ユーザＰＣ１１０のベクトル化部１１０２、多項式変換部１１０４、Ｈａｍｍｉｎｇ（ハミング）重み計算部１１０６、および準同型暗号部１１０８と同一または類似の構成を有する。また、ユーザＰＣ１６０は、復号処理部１６１０と公開鍵暗号方式の秘密鍵を格納する秘密鍵格納部１６１２を含む。また、これらを第２のベクトル化部１６０２、第２の多項式変換部１６０４、第２のＨａｍｍｉｎｇ重み計算部１６０６、および第２の準同型暗号部１６０８として参照することもある。第１のベクトル化部１１０２、第１の多項式変換部１１０４、第１のＨａｍｍｉｎｇ重み計算部１１０６、および第１の準同型暗号部１１０８と、第２のベクトル化部１６０２、第２の多項式変換部１６０４、第２のＨａｍｍｉｎｇ重み計算部１６０６、および第２の準同型暗号部１６０８を区別せずに参照することもある。また、第２のＨａｍｍｉｎｇ重み計算部１６０６は単に重み計算部１６０６として参照することもある。
【０１８９】
ベクトル化部１６０２では、ユーザによって入力されたテキストデータをｎ次元ベクトルｂとして表現する。例えば、ベクトルｂは、ｂ０、…、ｂｎ−１を０または１として、
【０１９０】
【数５６】
2014126865.tif 000058
のように表される。このように第２のベクトル化部１６０２は、ユーザによって入力された（第２の）テキストデータを、第１のベクトルｂとして表現する。
【０１９１】
多項式変換部１６０４では、ベクトル化部１６０２で得られたベクトルｂを多項式に変換する。
【０１９２】
【数５７】
2014126865.tif 000059
を計算する。検索時の変換多項式ｂ（ｘ）は、保存時の変換多項式ａ（ｘ）とは異なっていることに注意する。このように（第２の）多項式変換部１６０４６は、第２のベクトルｂから第２の変換多項式を用いて第２の多項式ｂ（ｘ）を得る。
【０１９３】
Ｈａｍｍｉｎｇ重み計算部１６０６では、ベクトルｂのハミング重みＨＷ（ｂ）を計算する。今の場合、ハミング重みＨＷ（ｂ）は、
【０１９４】
【数５８】
2014126865.tif 000060
である。このように（第２の）重み計算部１６０６は、第２のベクトルｂの秘匿距離に関する第２の重みＨＷ（ｂ）を計算する。今の場合、秘匿距離はハミング距離であり、第２の重みはハミング重みである。
【０１９５】
多項式変換部１６０４で得られた多項式とＨａｍｍｉｎｇ重み計算部１６０６で得られたハミング重みＨＷ（ｂ）は、準同型暗号化部１６０８で暗号化され、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））が得られる。このように、（第２の）準同型暗号化部１６０８は、第２の多項式ｂ（ｘ）、第２の重みＨＷ（ｂ）のそれぞれを、準同型暗号方式を用いて暗号化し、第２の暗号化多項式Ｅｎｃ（ｂ（ｘ））および第２の暗号化重みＥｎｃ（ＨＷ（ｂ））を得る。
【０１９６】
準同型暗号化部１６０８で得られた暗号化データＥｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））は、クラウド１２０に送られる。Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））はそれぞれ、上式［数５７］および［数５８］において、ａ（ｘ）をｂ（ｘ）と置き換えたものである。
【０１９７】
クラウド１２０の暗号乗算部１２０４では、暗号登録データ１２０２に格納されているＥｎｃ（ａ（ｘ））と準同型暗号化部１６０８で得られたＥｎｃ（ｂ（ｘ））の積
【０１９８】
【数５９】
2014126865.tif 000061
を計算する。
【０１９９】
暗号スカラー部１２０６では、事前に計算された２つの整数、
【０２００】
【数６０】
2014126865.tif 000062
と、Ｅｎｃ（ａ（ｘ）））とＥｎｃ（ｂ（ｘ））との積、
【０２０１】
【数６１】
2014126865.tif 000063
を計算する。また、暗号スカラー部１２０６では、暗号乗算部１２０４で得られたＣ１の２倍、
【０２０２】
【数６２】
2014126865.tif 000064
を計算する。
【０２０３】
暗号加算部１２０８では、ｋ１×Ｅｎｃ（ＨＷ（ａ））、ｋ２×Ｅｎｃ（ＨＷ（ｂ））、２×Ｅｎｃ（ａ（ｘ）））×Ｅｎｃ（ｂ（ｘ））の和を計算し、秘匿距離として［数６３］で表されるハミング距離Ｄを算出する。
【０２０４】
【数６３】
2014126865.tif 000065
このように、秘匿距離計算部では、第１の暗号化多項式Ｅｎｃ（ａ（ｘ）））、第２の暗号化多項式Ｅｎｃ（ｂ（ｘ））、第１の暗号化重みＥｎｃ（ＨＷ（ａ））、および第２の暗号化重みＥｎｃ（ＨＷ（ｂ））から、第１のベクトルａと第２のベクトルｂの秘匿距離の暗号化に対応する暗号化秘匿距離（ハミング距離）Ｄを得る。そして、ハミング距離ＤのみをユーザＰＣ１６０に送信する。
【０２０５】
ユーザＰＣ１６０とクラウド１２０の通信では、公開鍵暗号が用いられ、通信データの秘匿性を確保する。
【０２０６】
この際の鍵は、予め設定された次元ｎとビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）を用いて、秘密鍵を［数６４］のような行列Ｖとする。
【０２０７】
【数６４】
2014126865.tif 000066
また、公開鍵は、上の秘密鍵である行列Ｖのエルミート標準である行列Ｂとする。
【０２０８】
秘密鍵１６１２には、上記［数６４］で表される秘密鍵Ｖか格納される。
復号処理部１６１０では、秘密鍵Ｖを用いて、クラウド１２０から送られた準同型暗号化されたハミング距離Ｄを復号する。復号して得られるハミング距離Ｄ’は、
【０２０９】
【数６５】
2014126865.tif 000067
と計算される。復号処理部１６０６では、暗号化秘匿距離Ｄを復号して類似度として秘匿距離Ｄ’を算出する。そして、ハミング距離Ｄ’は類似度として出力される。
【０２１０】
復号処理部１６１０ではまた、復号されたハミング距離Ｄ’を予め用意された閾値Ｄｔｈと比較しても良い。そして、Ｄ’＜Ｄｔｈの場合は、２つのテキストデータは同一であると判定される。
【０２１１】
＜タグ検索システムの処理＞
図７および８を参照して、タグ検索システムにおける処理の例を説明する。図７は、準同型暗号を利用したタグ検索システムの保存時における処理フローの例を示す図である。
【０２１２】
まず処理が開始されると、ユーザＰＣ１１０では、ステップＳ３０２で、テキストデータのデータ入力を受ける。そして、処理はＳ１０４に進む。
【０２１３】
Ｓ３０４では、Ｓ３０２で入力されたテキストデータをｎ次元ベクトルａとして表現する。この処理はユーザＰＣ１１０のベクトル化部１１０２で行われ得る。
【０２１４】
次のＳ３０６では、ｎ次元ベクトルａを多項式に変換する。この処理はユーザＰＣ１１０の多項式変換部１１０４で行われ得る。
【０２１５】
Ｓ３０６の次のＳ３０８では、ｎ次元ベクトルａに対するハミング重みＨＷ（ａ）が計算される。この処理はユーザＰＣ１１０のＨａｍｍｉｎｇ重み計算部１１０６で行われ得る。
【０２１６】
次のＳ３１０では、Ｓ３０６で得られた多項式ａ（ｘ）とＳ１０８で得られたハミング重みＨＷ（ａ）を暗号化し、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））を得る。これらのデータ、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））はクラウド１２０に送られる。本ステップの処理はユーザＰＣ１１０の準同型暗号化部１１０８で行われ得る。
【０２１７】
Ｓ３１２では、Ｅｎｃ（ａ（ｘ））とＥｎｃ（ＨＷ（ａ））をデータベース、例えば、クラウド１２０の暗号登録データ１２０２に格納する。
そして、登録処理を終了する。
【０２１８】
図８は、準同型暗号を利用した生体認証システムの検索時における処理フローの例を示す図である。
【０２１９】
処理が開始されると、ユーザＰＣ１６０では、ステップＳ４０２で、テキストデータのデータ入力を受ける。そして、処理はＳ４０４に進む。
【０２２０】
Ｓ４０４では、Ｓ４０２で入力されたテキストデータをｎ次元ベクトルｂとして表現する。この処理はユーザＰＣ１６０のベクトル化部１６０２で行われ得る。
【０２２１】
次のＳ４０６では、ｎ次元ベクトルａを多項式に変換する。この処理はユーザＰＣ１６０の多項式変換部１６０４で行われ得る。
【０２２２】
Ｓ４０６の次のＳ４０８では、ｎ次元ベクトルａに対するハミング重みＨＷ（ｂ）が計算される。この処理はユーザＰＣ１６０のＨａｍｍｉｎｇ重み計算部１６０６で行われ得る。
【０２２３】
次のＳ４１０では、Ｓ４０６で得られた多項式ｂ（ｘ）とＳ４０８で得られたハミング重みＨＷ（ｂ）を暗号化し、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））を得る。そして、これらのデータ、Ｅｎｃ（ｂ（ｘ））とＥｎｃ（ＨＷ（ｂ））をクラウド１２０に送る。本ステップの処理はユーザＰＣ１６０の準同型暗号化部１６０８で行われ得る。
【０２２４】
Ｓ４１２では、暗号登録データ１２０２に格納されているＥｎｃ（ａ（ｘ））とＳ４１０で得られたＥｎｃ（ｂ（ｘ））の積Ｅｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））を計算する。この処理は、クラウド１２０の暗号乗算部１２０４で行われ得る。
【０２２５】
Ｓ４１４では、［数６１］の２つの整数、ｋ１、ｋ２と、Ｅｎｃ（ａ（ｘ）））とＥｎｃ（ｂ（ｘ））との積、ｋ１Ｅｎｃ（ａ（ｘ）））、ｋ２Ｅｎｃ（ｂ（ｘ））が計算される。また、Ｓ４１４では、Ｓ４１０で得られたＥｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））の２倍、２Ｅｎｃ（ｂ（ｘ））×Ｅｎｃ（ＨＷ（ｂ））を計算する。本ステップの処理は、クラウド１２０の暗号スカラー部１２０６で行われ得る。
【０２２６】
Ｓ４１６では、ｋ１×Ｅｎｃ（ＨＷ（ａ））、ｋ２×Ｅｎｃ（ＨＷ（ｂ））、２×Ｅｎｃ（ａ（ｘ）））×Ｅｎｃ（ｂ（ｘ））の和を計算し、秘匿距離として［数６０］で表されるハミング距離Ｄを算出する。ハミング距離ＤのみをユーザＰＣ１６０に送信する。本ステップの処理は、クラウド１２０の暗号加算部１２０８で行われ得る。
【０２２７】
次のＳ４１８では、［数６４］のような秘密鍵Ｖを用いて、クラウド１２０から送られた準同型暗号化されたハミング距離Ｄを復号する。秘密鍵ＶはユーザＰＣ１６０の暗号登録データ１２１２に格納されていても良い。本ステップの処理は、ユーザＰＣ１６０の復号処理部１６１０で行われ得る。
【０２２８】
Ｓ４２０では、Ｓ４１８の結果を類似度として出力する。この処理は、不図示の表示装置によって行われ得る。
そして、照合処理を終了する。
【０２２９】
図９は、準同型暗号を利用した暗号処理装置の構成の例を示す構成図である。準同型暗号装置は、汎用コンピュータ５００として実現され得る。
【０２３０】
このコンピュータ５００は、ＭＰＵ５０２、ＲＯＭ５０４、ＲＡＭ５０６、ハードディスク装置５０８、入力装置５１０、表示装置５１２、インタフェース装置５１４、及び記録媒体駆動装置５１６を備えている。なお、これらの構成要素はバスライン５２０を介して接続されており、ＭＰＵ５０２の管理の下で各種のデータを相互に授受することができる。
【０２３１】
ＭＰＵ（Ｍｉｃｒｏ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０２は、このコンピュータ２００全体の動作を制御する演算処理装置であり、コンピュータ５００の制御処理部として機能する。
【０２３２】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＭＰＵ５０２は、この基本制御プログラムをコンピュータ５００の起動時に読み出して実行することにより、このコンピュータ５００の各構成要素の動作制御が可能になる。
【０２３３】
ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０６は、ＭＰＵ５０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【０２３４】
ハードディスク装置５０８は、ＭＰＵ５０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ５０２は、ハードディスク装置５０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【０２３５】
入力装置５１０は、例えばマウス装置やキーボード装置であり、図６のシステムの利用者により操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＭＰＵ５０２に送付する。
【０２３６】
表示装置５１２は例えば液晶ディスプレイであり、ＭＰＵ５０２から送付される表示データに応じて各種のテキストや画像を表示する。
【０２３７】
インタフェース装置５１４は、このコンピュータ５００に接続される各種機器との間での各種情報の授受の管理を行う。
【０２３８】
記録媒体駆動装置５１６は、可搬型記録媒体５１８に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＭＰＵ５０１は、可搬型記録媒体２１８に記録されている所定の制御プログラムを、記録媒体駆動装置５１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体２１８としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【０２３９】
このようなコンピュータ５００を用いて暗号処理装置を構成するには、例えば、上述の各処理部における処理をＭＰＵ５０２に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置５０８若しくは可搬型記録媒体５１８に予め格納しておく。そして、ＭＰＵ５０２に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、暗号処理装置が備えている機能がＭＰＵ５０２により提供される。
【０２４０】
以上の実施例１〜２を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る多項式変換部と、
前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る重み計算部と、
前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得る準同型暗号部と、
前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る秘匿距離計算部と、
を含む暗号処理装置。
（付記２）
前記重みはハミング重みであり、前記秘匿距離はハミング距離である、付記１の装置。
（付記３）
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数６６】
2014126865.tif 000068
または、
【数６７】
2014126865.tif 000069
で定義され、前記第２の変換多項式は、［数６６］、［数６７］の前記第１の変換多項式ではない方で定義される、付記１または２の装置。
（付記４）
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数６８】
2014126865.tif 000070
と定義すると、
【数６９】
2014126865.tif 000071
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数７０】
2014126865.tif 000072
として、
【数７１】
2014126865.tif 000073
である、付記３の装置。
（付記５）
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数７２】
2014126865.tif 000074
または、
【数７３】
2014126865.tif 000075
で定義され、前記第２の変換多項式は、［数７２］、［数７３］の前記第１の変換多項式ではない方で定義される、付記１または２の装置。
（付記６）
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数７４】
2014126865.tif 000076
と定義すると、
【数７５】
2014126865.tif 000077
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数７６】
2014126865.tif 000078
として、
【数７７】
2014126865.tif 000079
または、
【数７８】
2014126865.tif 000080
である、付記５の装置。
（付記７）
前記準同型暗号方式では、平文ｂの暗号文ｃは、ベクトルｕを、平文ｂと同じ次元のベクトルであって、成分が０または１であるベクトルとし、ベクトルｅ１を第１成分のみが１で、それ以外の成分は全て０であるベクトルとして、
【数７９】
2014126865.tif 000081
で与えられ、ここで、Ｂは平文をベクトル表示したときの次元ｎと所定のビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）として、
【数８０】
2014126865.tif 000082
のエルミート標準形である、付記１乃至６のいずれか一項の装置。
（付記８）
さらに、
正規ユーザの生体の一部に関する情報から前記正規ユーザを他のユーザから区別する特徴を第１の特徴量として抽出する第１の特徴量抽出部と、
前記正規ユーザとして認証されるべきユーザの生体の一部に関する情報から前記正規ユーザの前記第１の特徴量と比較される第２の特徴量を抽出する特徴量抽出部と、
前記第１の特徴量を、前記第１のベクトルとして表現する第１のベクトル化部と、
前記第２の特徴量を、前記第２のベクトルとして表現する第２のベクトル化部と、
前記暗号化秘匿距離を復号して前記秘匿距離を算出する復号処理部と、
前記秘匿距離と予め決められた閾値との比較に基づいて、前記正規ユーザとして認証されるべきユーザが前記正規ユーザであるかどうかを判定する判定部と、
を含み、生体認証装置として機能する、付記１乃至７のいずれか一項の装置。
（付記９）
さらに、
秘匿情報にタグ付けされる第１のテキストデータを前記第１のベクトルとして表現する第１のベクトル化部と、
前記秘匿情報の検索のために使用される第２のテキストデータを前記第２のベクトルとして表現する第２のベクトル化部と、
前記第１のテキストデータ、前記第１のベクトルとして表現する第１のベクトル化部と、
前記第２のテキストデータを、前記第２のベクトルとして表現する第２のベクトル化部と、
前記暗号化秘匿距離を復号して類似度として前記秘匿距離を算出する復号処理部と、
を含み、タグ検索装置として機能する、付記１乃至７のいずれか一項の装置。
（付記１０）
第１のベクトルから第１の変換多項式を用いて第１の多項式と、第２のベクトルから第２の変換多項式を用いて第２の多項式を得ることと、
前記第１のベクトルの秘匿距離に関する第１の重みと、前記第２のベクトルの秘匿距離に関する第２の重みを得る重みことと、
前記第１の多項式、前記第２の多項式、前記第１の重み、および前記第２の重みのそれぞれを、準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、および第２の暗号化重みを得ることと、
前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、および前記第２の暗号化重みから、前記第１のベクトルと前記第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得ることと、
を含む暗号処理方法。
（付記１１）
前記重みはハミング重みであり、前記秘匿距離はハミング距離である、付記１０の方法。
（付記１２）
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数８１】
2014126865.tif 000083
または、
【数８２】
2014126865.tif 000084
で定義され、前記第２の変換多項式は、［数８１］、［数８２］の前記第１の変換多項式ではない方で定義される、付記１０または１１の方法。
（付記１３）
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数８３】
2014126865.tif 000085
と定義すると、
【数８４】
2014126865.tif 000086
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数８５】
2014126865.tif 000087
として、
【数８６】
2014126865.tif 000088
である、付記１２の方法。
（付記１４）
前記第１の変換多項式は、ベクトル（ａ１、ａ２、…、ａｎ）に対して、
【数８７】
2014126865.tif 000089
または、
【数８８】
2014126865.tif 000090
で定義され、前記第２の変換多項式は、［数８７］、［数８８］の前記第１の変換多項式ではない方で定義される、付記１０または１１の方法。
（付記１５）
前記第１の変換多項式、前記第２の変換多項式、第１の暗号化重み、または第２の暗号化重みをａ（ｘ）とすると、ｄは公開鍵を表す行列Ｂの（１、１）成分、ｒは公開鍵を表す行列Ｂの（２、１）成分として、前記第１の暗号化多項式、前記第２の暗号化多項式、前記第１の暗号化重み、または前記第２の暗号化重みは、整数ｘおよびｄに対して、
【数８９】
2014126865.tif 000091
と定義すると、
【数９０】
2014126865.tif 000092
であり、前記第１のベクトルをＡ＝（ａ１、ａ２、…、ａｎ）と前記第２のベクトルをＢ＝（ｂ１、ｂ２、…、ｂｎ）とすると、前記秘匿距離は、
【数９１】
2014126865.tif 000093
として、
【数９２】
2014126865.tif 000094
または、
【数９３】
2014126865.tif 000095
である、付記１４の方法。
（付記１６）
前記準同型暗号方式では、平文ｂの暗号文ｃは、ベクトルｕを、平文ｂと同じ次元のベクトルであって、成分が０または１であるベクトルとし、ベクトルｅ１を第１成分のみが１で、それ以外の成分は全て０であるベクトルとして、
【数９４】
2014126865.tif 000096
で与えられ、ここで、Ｂは平文をベクトル表示したときの次元ｎと所定のビット長ｔに対し、各成分の絶対値がｔビット以下の整数となるｎ次元の乱数ベクトルｖ＝（ｖ０、ｖ１、…、ｖｎ−１）として、
【数９５】
2014126865.tif 000097
のエルミート標準形である、付記１０乃至１５のいずれか一項の方法。
（付記１７）
さらに、
正規ユーザの生体の一部に関する情報から前記正規ユーザを他のユーザから区別する特徴を第１の特徴量として抽出することと、
前記正規ユーザとして認証されるべきユーザの生体の一部に関する情報から前記正規ユーザの前記第１の特徴量と比較される第２の特徴量を抽出することと、
前記第１の特徴量を、前記第１のベクトルとして表現することと、
前記第２の特徴量を、前記第２のベクトルとして表現することと、
前記暗号化秘匿距離を復号して前記秘匿距離を算出することと、
前記秘匿距離と予め決められた閾値との比較に基づいて、前記ユーザを前記正規ユーザであるかどうかを判定する判定部と、
を含み、生体認証方法として機能する、付記１０乃至１６のいずれか一項の方法。
（付記１８）
さらに、
秘匿情報にタグ付けされる第１のテキストデータを前記第１のベクトルとして表現することと、
前記秘匿情報の検索のために使用される第２のテキストテキストを前記第２のベクトルとして表現することと、
前記第１のテキストデータを、前記第１のベクトルとして表現することと、
前記第２のテキストデータを、前記第２のベクトルとして表現する第２のベクトル化部と、
前記暗号化秘匿距離を復号して類似度として前記秘匿距離を算出する復号処理部と、
を含み、タグ検索方法として機能する、付記１０乃至１６のいずれか一項の方法。
【符号の説明】
【０２４１】
１０  生体認証システム
２０  登録センサ
３０  計算サーバ
６０  照合センサ
７０  認証局
１００  タグ検索システム
１１０  ユーザＰＣ
１２０  クラウド
２０２、６０２  特徴量抽出部
２０４、６０４、１１０２、１６０２  ベクトル化部
２０６、６０６、１１０４、１６０４  多項式変換部
２０８、６０８、１１０６、１６０６  Ｈａｍｍｉｎｇ重み計算部
２１０、６１０、１１０８、１６０８  準同型暗号部
３０２、１２０２  暗号登録データ
３０４、１２０４  暗号乗算部
３０６、１２０６  暗号スカラー部
３０８、１２０８  暗号加算部
７０２、１６１２  秘密鍵
７０４、１６１０  復号処理部
７０６  判定処理部
【図９】
2014126865.tif 000113
【図１Ａ】
2014126865.tif 000114
【図１Ｂ】
2014126865.tif 000115
【図２Ａ】
2014126865.tif 000116
【図２Ｂ】
2014126865.tif 000117
【図３】
2014126865.tif 000118
【図４】
2014126865.tif 000119
【図５Ａ】
2014126865.tif 000120
【図５Ｂ】
2014126865.tif 000121
【図６Ａ】
2014126865.tif 000122
【図６Ｂ】
2014126865.tif 000123
【図７】
2014126865.tif 000124
【図８】
2014126865.tif 000125