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