(57)【要約】【課題】秘匿化パターンマッチングにおけるコストを削減する。【解決手段】本方法は、第1データから生成された第1バイナリベクトルV1の要素を、次数について降順と昇順とのうちいずれかである第1順番で係数として用いることで表される第1多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された第1多項式を他のコンピュータから受信し、第2データから生成された第2バイナリベクトルV2の要素を、第1順番とは異なる第2順番で係数として用いることで表される第2多項式を、上記準同型暗号方式によって暗号化することで得られる、暗号化された第2多項式と、暗号化された第1多項式とを用いて、暗号文空間における所定演算を実行し、所定の演算の結果を、他のコンピュータに送信する。所定演算は、当該所定演算の結果を復号することで得られる第3多項式の各項の係数がV2に対するV1の各対比位置における距離を表すように規定される。【選択図】図２
2015031935.tif 000002
【特許請求の範囲】
【請求項１】
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する
処理を含み、１又は複数のコンピュータにより実行される情報処理方法。
【請求項２】
第２のデータから生成された第２のバイナリベクトルの要素を、次数について前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つ第２のデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行する
処理をさらに含み、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
請求項１記載の情報処理方法。
【請求項３】
前記所定の演算の演算結果を復号することで得られる前記第３の多項式の各項の係数のうち値がゼロとなる係数が存在するか否かを判断する処理
をさらに含む請求項２記載の情報処理方法。
【請求項４】
前記所定の演算が、
暗号化された前記第１の多項式と第１の補助データとの積の項と、暗号化された前記第２の多項式と第２の補助データとの積の項と、暗号化された前記第１の多項式と暗号化された前記第２の多項式との積の項とを含む距離計算式によって規定される
請求項２又は３記載の情報処理方法。
【請求項５】
前記第１の補助データが、
暗号化された前記第１の多項式に対応する前記第１の順番が昇順であれば、所定次数の多項式であって係数が全て１の多項式のうち降順に前記第１のバイナリベクトルの要素数の項のみを取り出した多項式を含み、
暗号化された前記第１の多項式に対応する前記第１の順番が降順であれば、前記第１のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含み、
前記第２の補助データが、
暗号化された前記第２の多項式に対応する前記第２の順番が降順であれば、前記第２のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含み、
暗号化された前記第２の多項式に対応する前記第２の順番が昇順であれば、前記所定次数の多項式であって係数が全て１の多項式のうち降順に前記第２のバイナリベクトルの要素数の項のみを取り出した多項式を含む、
請求項４記載の情報処理方法。
【請求項６】
暗号化された前記第１の多項式を、第２のデータから生成された第２のバイナリベクトルの要素を、次数について前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第２の多項式を格納する第２の格納部にアクセス可能な他のコンピュータに送信し、
前記他のコンピュータから、暗号化された前記第１の多項式と暗号化された前記第２の多項式とを用いて暗号文空間における所定の演算を実行することで得られた演算結果を受信し、
前記演算結果を復号することで得られる第３の多項式の各項の係数のうち値がゼロとなる係数を特定する
処理をさらに含む請求項１記載の情報処理方法。
【請求項７】
コンピュータが、
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信し、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行し、
前記所定の演算の結果を、前記他のコンピュータに送信する
処理を含み、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
情報処理方法。
【請求項８】
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する
処理を、１又は複数のコンピュータに実行させるためのプログラム。
【請求項９】
コンピュータに、
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信し、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行し、
前記所定の演算の結果を、前記他のコンピュータに送信する
処理を実行させ、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
プログラム。
【請求項１０】
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成するバイナリ変換部と、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成する多項式変換部と、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する暗号化部と、
を有する情報処理装置。
【請求項１１】
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信する受信部と、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行する暗号演算処理部と、
前記所定の演算の結果を、前記他のコンピュータに送信する送信部と、
を有し、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを秘匿化したままでパターンマッチングを行うための技術に関する。
【背景技術】
【０００２】
現在、個人情報及び機密情報を保護する規制が強化される一方で、そのような情報を利用したサービスの市場が拡大しつつある。そこで、個人情報及び機密情報を保護したままデータの活用が可能な秘匿化技術が注目されている。秘匿化技術の中には、データ種別やサービス要件に応じて、暗号技術や統計技術を使った技術がある。
【０００３】
暗号技術を用いた秘匿化技術として準同型暗号技術が知られている。準同型暗号技術は、暗号化のための鍵と復号化のための鍵とが異なる公開鍵暗号方式の１つであって、暗号化したままデータ操作が可能となる機能を備えた暗号である。例えば、平文ｍ１及びｍ２に対して、加算又は乗法に関する準同型暗号方式の暗号化関数をＥとすると、以下の式（１）又は（２）の性質が成り立つ。
（１）Ｅ（ｍ１）＋Ｅ（ｍ２）＝Ｅ（ｍ１＋ｍ２）
（２）Ｅ（ｍ１）＊Ｅ（ｍ２）＝Ｅ（ｍ１＊ｍ２）
（１）式が成り立つものを加算について準同型と呼び、（２）式が成り立つものを乗算について準同型と呼ぶ。
【０００４】
準同型暗号方式を用いれば、暗号文を復号することなく、暗号文の加算や乗算により、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、電子投票や電子現金などの分野、さらに近年ではクラウドコンピューティング分野において利用されることが期待されている。
【０００５】
このような準同型暗号方式として、ＲＳＡ（Rivest Shamir Adleman）暗号方式（乗算のみ準同型）や、Additive ElGamal暗号方式（加算のみ準同型）が代表的である。また、２００９年には加算と乗算の両方が可能な準同型暗号方式（式（１）及び（２）を満たす暗号方式）が提案された（非特許文献１に開示の技術）。しかし、このような準同型暗号方式は、処理性能や暗号データサイズの面で実用向きではないことが知られている。そこで、２０１１年に、加算と乗算の両方が可能で且つ処理性能と暗号データサイズの両面で実用的な準同型暗号方式が提案され、その応用例などが提示された（非特許文献２に開示の技術）。
【０００６】
ここで、２０１１年に提案された準同型暗号方式について説明する（詳細は、非特許文献２の３．２節を参照のこと）。まず、暗号鍵生成について、主に３つの鍵生成パラメータ（ｎ，ｑ，ｔ）を用意する。ｎは２冪の整数で格子次元と呼ばれ、ｑは素数、ｔは素数ｑよりも小さい整数とする。暗号鍵生成の手順としては、まず秘密鍵として各係数が非常に小さいｎ次元の多項式ｓｋをランダムに生成する。なお、各係数の小ささは、あるパラメータσで制限される。次に、各係数がｑより小さいｎ次元多項式ａ１と各係数が非常に小さいｎ次元多項式ｅをランダムに生成する。
【０００７】
そこで、ａ０＝−（ａ１＊ｓｋ＋ｔ＊ｅ）を計算し、組（ａ０，ａ１）を公開鍵ｐｋと定義する。但し、ａ０の多項式計算時において、ｎ次以上の多項式に対してｘn＝−１，ｘn+1＝−ｘ，．．．と計算することで、絶えずｎ次より小さい多項式を計算する。さらに、多項式の係数については、素数ｑで割った余りを出力する。このような演算を行う空間を、学術的にはＲｑ：＝Ｆｑ［ｘ］／（ｘn＋１）と表すことが多い。
【０００８】
次に、各係数がｔより小さいｎ次多項式で表される平文データｍと公開鍵ｐｋ＝（ａ０，ａ１）に対して、各係数が非常に小さい３つのｎ次元多項式ｕ，ｆ，ｇをランダムに生成し、平文データｍの暗号データＥ（ｍ，ｐｋ）＝（ｃ０，ｃ１）を次のように定義する。（ｃ０，ｃ１）については、ｃ０＝ａ０＊ｕ＋ｔ＊ｇ＋ｍ，ｃ１＝ａ１＊ｕ＋ｔ＊ｆと計算する。なお、これらの計算も空間Ｒｑ上での演算を行う。
【０００９】
そして、２つの暗号文Ｅ（ｍ１，ｐｋ）＝（ｃ０，ｃ１）と、Ｅ（ｍ２，ｐｋ）＝（ｄ０，ｄ１）に対して、暗号加算Ｅ（ｍ１，ｐｋ）＋Ｅ（ｍ２，ｐｋ）を（ｃ０＋ｄ０，ｃ１＋ｄ１）と計算し、暗号乗算Ｅ（ｍ１，ｐｋ）＊Ｅ（ｍ２，ｐｋ）を（ｃ０＋ｄ０，ｃ０＊ｄ１＋ｃ１＊ｄ０，ｃ１＊ｄ１）と計算する。このように暗号乗算を行うと、暗号文のデータサイズが２成分ベクトルから３成分ベクトルになることに注意する。
【００１０】
最後に、復号処理であるが、暗号文ｃ＝（ｃ０，ｃ１，ｃ２，．．．）に対して（ここでは複数の暗号乗算などの暗号操作により暗号文データの成分が増大したと仮定している）、秘密鍵ｓｋを用いてＤ（ｃ，ｓｋ）＝［ｃ０＋ｃ１＊ｓｋ＋ｃ２＊ｓｋ2＋・・・］ｑ  ｍｏｄ  ｔを計算することで、復号する。ここで、［ｚ］ｑの値は、整数ｚをｑで割った余りｗを計算し、ｗ＜ｑならば［ｚ］ｑ＝ｗを出力し、ｗ≧ｑの場合には［ｚ］ｑ＝ｗ−ｑを出力する。さらに、ａ  ｍｏｄ  ｔは整数ａをｔで割った余りを意味する。
【００１１】
以下、分かりやすくするために数値例を示しておく。
秘密鍵ｓｋ＝Mod（Mod(4,1033)＊ｘ3＋Mod(4,1033)＊ｘ2＋Mod(1,1033)*ｘ，ｘ4＋１）
公開鍵ｐｋ＝（ａ０，ａ１）
ａ０＝Mod（Mod(885,1033)＊ｘ3＋Mod(519,1033)＊ｘ2＋Mod(621,1033）＊ｘ＊＋Mod(327,1033)，ｘ4，ｘ4＋１）
ａ１＝Mod（Mod(661,1033)＊ｘ3＋Mod(625,1033)＊ｘ2＋Mod(861,1033)＊ｘ＋Mod(311,1033)，ｘ4＋１）
Ｅ（ｍ，ｐｋ）＝（ｃ０，ｃ１）
平文データｍ＝３＋２ｘ＋２ｘ2＋２ｘ3とする。
ｃ０＝Mod（Mod(822,1033)＊ｘ3＋Mod(1016,1033)＊ｘ2＋Mod(292,1033)＊ｘ＋Mod(243,1033)，ｘ4＋１）
ｃ１＝Mod（Mod(840,1033)＊ｘ3＋Mod(275,1033)＊ｘ2＋Mod(628,1033)＊ｘ＋Mod(911,1033)，ｘ4＋１）
【００１２】
なお、上記値において、鍵生成パラメータ（ｎ，ｑ，ｔ）については、（４，１０３３，２０）と設定した。さらに、Mod（ａ，ｑ）は整数ａを素数ｑで割った余りを意味し、Mod（ｆ（ｘ），ｘ4＋１）は多項式ｆ（ｘ）を多項式ｘ4＋１で割った余りの多項式を意味する。但し、ｘ4＝−１、ｘ5＝ｘ，．．．などを意味するものとする
【００１３】
次に、パターンマッチングについて簡単に説明しておく。パターンマッチングとは、例えばテキスト文字列の中にパターン文字列が存在するか否かを判定する処理で、例えばテキスト文字列Ｔ＝”acbabbaccb”の中に、パターン文字列Ｐ＝”abbac”があるか否かを判定する処理を考える。このとき、図１に示すように、テキスト文字列Ｔに対して、パターン文字列Ｐを１文字ずつずらしながら、テキストとパターンが一致する文字の個数（距離とも呼ぶ）を算出する。図１では、個数を表す数値の並びをスコアベクトルと呼ぶ。今回の例ではパターン文字列Ｐの長さが５なので、スコアベクトルの値が５の成分のところで、テキスト文字列Ｔとパターン文字列Ｐとが一致することがわかる。
【００１４】
このように、暗号化なしのパターンマッチングでは、テキスト文字列Ｔとパターン文字列Ｐに対して、パターン文字列Ｐを１文字ずつずらしながらテキスト文字列との距離を計算していく。
【００１５】
一方、準同型暗号を利用した秘匿パターンマッチングでは、テキスト文字列Ｔとパターン文字列Ｐを準同型暗号で暗号化した状態で、複数の距離を計算することになる。ここでは、テキスト文字列Ｔを有する情報登録者、パターン文字列Ｐを有する照合者、秘匿パターンマッチングにおける暗号距離計算を行うクラウド事業者の３者における秘匿パターンマッチング計算モデルを考える。まず、照合者は、準同型暗号の鍵生成を行い公開鍵と秘密鍵を生成し、公開鍵のみを情報登録者とクラウド事業者に公開する。このあと、情報登録者は照合者から送られた公開鍵を用いて、自身が有するテキスト文字列Ｔを準同型暗号で暗号化し、その暗号化テキストＥ（Ｔ）をクラウド内のデータベースに保存しておく。照合者は、パターン文字列Ｐがあるか照合するために、パターン文字列Ｐを準同型暗号化し、暗号化パターンＥ（Ｐ）をクラウドに送信する。クラウドは、暗号化テキストＥ（Ｔ）と暗号化パターンＥ（Ｐ）に対して、ＴとＰに関する複数の距離を暗号化したまま計算し、その暗号化計算結果のみを照合者に送信する。照合者は、クラウドから送信された暗号化計算結果を自身が有する秘密鍵を用いて復号し、復号結果からパターン文字列Ｐがテキスト文字列Ｔに含まれるか否かを判定する。
【００１６】
このようなクラウド秘匿パターンマッチングであれば、クラウド上では暗号化した状態で処理が行われるので、情報登録者及び照合者のデータを開示することがない。これにより、安全性が強固ではないクラウドなどの環境で、パターンマッチング処理がアウトソーシングできるようになる。
【００１７】
しかしながら、単純に準同型暗号方式をパターンマッチングに適用するだけでは、データ量や計算負荷の点で実用的ではない。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009.
【非特許文献２】K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、一側面によれば、秘匿化パターンマッチングにおけるコストを削減するための技術を提供することである。
【課題を解決するための手段】
【００２０】
本発明の第１の態様に係る情報処理方法は、（Ａ）第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、（Ｂ）第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、（Ｃ）第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する処理を含む。
【００２１】
本発明の第２の態様に係る情報処理方法は、（Ａ）第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された第１の多項式を他のコンピュータから受信し、（Ｂ）第２のデータから生成された第２のバイナリベクトルの要素を、第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された第２の多項式と、暗号化された第１の多項式とを用いて、暗号文空間における所定の演算を実行し、（Ｃ）所定の演算の結果を、他のコンピュータに送信する処理を含む。そして、上記所定の演算が、当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が第２のバイナリベクトルに対する第１のバイナリベクトルの各対比位置における距離を表すように規定されるものである。
【発明の効果】
【００２２】
一側面によれば、秘匿化パターンマッチングにおけるコストを削減できるようになる。
【図面の簡単な説明】
【００２３】
【図１】図１は、パターンマッチングを説明するための図である。
【図２】図２は、暗号距離計算を解説するための図である。
【図３】図３は、本発明の実施の形態に係るシステムの概要を示す図である。
【図４】図４は、提供者装置の機能ブロック図である。
【図５】図５は、照合者装置の機能ブロック図である。
【図６】図６は、情報処理装置の機能ブロック図である。
【図７】図７は、登録処理の処理フローを示す図である。
【図８】図８は、照合処理の処理フローを示す図である。
【図９】図９は、暗号化パターンマッチングの演算のバリエーションを示す図である。
【図１０】図１０は、暗号化パターンマッチングの演算のバリエーションを示す図である。
【図１１】図１１は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００２４】
まず、本発明の一実施の形態に係る処理の概要を説明する。
【００２５】
準同型暗号を利用した秘匿パターンマッチング計算においては、データサイズや距離計算コストを削減するために、バイナリ化したテキストの各ビットを次数について昇順で係数に用いることで表される多項式を求め、多項式演算可能な同準型暗号方式（例えばRing-LWEベース準同型暗号：非特許文献２を参照のこと）で暗号化する。一方、バイナリ化したパターンの各ビットを次数について降順で係数に用いることで表される多項式を求め、同じ準同型暗号方式で暗号化する。
【００２６】
そして、準同型暗号で暗号化されたテキスト多項式及びパターン多項式に対して、多項式上の準同型性を利用して、各係数が、テキストとパターンとのハミング距離になるような暗号演算を実施する。その後、暗号演算結果を復号することで得られる多項式の各係数からハミング距離を特定し、ハミング距離が０となっているか否かを判定する。このようにすることで、秘匿パターンマッチング計算が行われる。
【００２７】
具体的には、バイナリ化した長さｋのテキスト（バイナリベクトルとも呼ぶ）Ｔ＝（ｔ0，ｔ1，...，ｔk-1）に対して、各ビットを昇順で係数として用いる多項式ｍt（Ｔ）＝Σiｔiｘiを生成し、これに対して上で述べた準同型暗号方式により、暗号化テキストEnc（ｍt（Ｔ），ｐｋ）を生成する。これによって、テキストＴは秘匿化される。
【００２８】
一方、バイナリ化した長さｌのパターンＰ＝（ｐ0，ｐ1，...，ｐl-1）に対して、各ビットを降順に係数として用いる多項式ｍp（Ｐ）＝−Σjｐjｘn-jを生成し、それを上で述べた準同型暗号方式により暗号化パターンEnc(ｍp（Ｐ），ｐｋ）を生成する。これによって、パターンＰは秘匿される。
【００２９】
次に、暗号化されたテキストEnc（ｍt（Ｔ），ｐｋ）とパターンEnc(ｍp（Ｐ），ｐｋ）に対して、暗号化距離計算を以下のように実行する。
Enc（ｍt（Ｔ），ｐｋ）＊Ｃl＋Enc（ｍp（Ｐ），ｐｋ）＊Ｃk−２Enc（ｍt（Ｔ），ｐｋ）＊Enc（ｍp（Ｐ），ｐｋ）  （３）
【００３０】
ここで、Ｃlは長さｌの降順の多項式を含む元であり、Ｃkは長さｋの昇順の多項式を含む元であり、以下のように表される。
Ｃl＝（−Σjｘn-j，０）  （４）
Ｃk＝（Σiｘi，０）      （５）
【００３１】
（３）式で得られた暗号化距離計算結果を復号した結果をｒ0＋ｒ1ｘ＋ｒ2ｘ2＋・・・＋ｒn-1ｘn-1（係数がパラメータｔ以下のｎ次多項式で表される）としたとき、０≦ｉ≦ｋ−ｌに対してｉ次の係数ｒiは、ｉ番目のビットを先頭とする部分テキストＴ(i)とパターンＰのハミング距離ｄ（Ｔ(i)，Ｐ）と一致する。従って、復号結果ｒ0＋ｒ1ｘ＋ｒ2ｘ2＋・・・＋ｒn-1ｘn-1からパターンＰがテキストＴのどの部分に含まれるかは、係数が０となる次数を特定すればよい。すなわち、テキストＴとパターンＰを準同型暗号で秘匿したまま計算することが可能となる。
【００３２】
ここで、本実施の形態に係る秘匿パターンマッチング計算の考え方を図２を用いて示しておく。平文空間において、多項式の各係数がハミング距離ｄ（Ｔ(i)，Ｐ）になるようにするには、以下のような演算を行うことになる。
Σi（ＨＷ（Ｔ(i)）＋ＨＷ（Ｐ）−２＜Ｔ(i)，Ｐ＞）ｘi    （６）
なお、ＨＷ（Ａ）はＡのハミング重みを表し、＜Ａ，Ｂ＞はＡとＢとの内積計算を表す。
【００３３】
（６）式におけるΣiＨＷ（Ｔ(i)）ｘiは、図２（Ａ）に示すように、ｍt（Ｔ）＊（−Σjｘn-j）である。また、（６）式におけるΣiＨＷ（Ｐ）ｘiは、図２（Ｂ）に示すようにｍp（Ｐ）＊（Σiｘi）である。さらに、（６）式におけるΣi＜Ｔ(i)，Ｐ＞ｘiは、図２（Ｃ）に示すように、ｍt（Ｔ）＊ｍp（Ｐ）である。
【００３４】
そうすると、図２（Ａ）乃至（Ｃ）に示すように、各平文演算に対して、暗号文空間における対応する暗号演算が得られる。従って、結果として、図２（Ｄ）のように、（３）式に示すような暗号演算を実行することで、復号化すれば係数がハミング距離となるような演算がなされたことになる。
【００３５】
但し、平文多項式上の演算は、ｎ次以上の多項式に対してｘn＝−１，ｘn+1＝−ｘ，．．．と計算することで、絶えずｎ次以下の多項式を計算し、ｎ次以下の各多項式の係数については、パラメータｔで割った余りを出力するようにする。このような演算を行う空間を、Ｒt＝Ｆｑ［ｘ］／（ｘn＋１）と表すことが多い。
【００３６】
ここで、本実施の形態に係る演算の数値例を示しておく。バイナリ化された長さｋ＝８のテキストＴ＝（１，１，０，１，１，１，０，１）の中に、長さｌ＝３のパターンＰ＝（１，０，１）が含まれているか否かを、テキストＴとパターンＰを準同型暗号で秘匿したまま判定することを考える。実際には、テキストＴの２番目と６番目の部分ベクトルＴ(2)及びＴ(6)と一致することが分かる。
【００３７】
長さｋ＝８のベクトルを扱うために、準同型暗号方式のパラメータをｎ＝８，ｑ＝1073741857（３０ビット素数）、ｔ＝ｎ＝８と設定する。このとき、秘密鍵ｓｋと公開鍵ｐｋを以下のようにとる。
ｓｋ＝Mod（Mod(2,1073741857)＊ｘ6＋Mod(5,1073741857)＊ｘ5＋Mod(5,1073741857)＊ｘ4＋Mod(5,1073741857)＊ｘ3＋Mod(6,1073741857)＊ｘ2＋Mod(1,1073741857)＊ｘ, ｘ8＋１）
ｐｋ＝（ａ０，ａ１）
ａ０＝Mod（Mod(943067072,1073741857)＊ｘ7＋Mod(208992892,1073741857)＊ｘ6＋Mod(757863697,1073741857)＊ｘ5＋Mod(463766550,1073741857)＊ｘ4＋Mod(868678190,1073741857)＊ｘ3＋Mod(79684227,1073741857)＊ｘ2＋Mod(794283856,1073741857)＊ｘ＋Mod(118588567,1073741857)，ｘ8＋１）
ａ１＝Mod（Mod(476812016,1073741857)＊ｘ7＋Mod(135271255,1073741857)＊ｘ6＋Mod(610902088,1073741857)＊ｘ5＋Mod(561030593,1073741857)＊ｘ4＋Mod(693790135,1073741857)＊ｘ3＋Mod(656347688,1073741857)＊ｘ2＋Mod(903267448,1073741857)＊ｘ＋Mod(326511477,1073741857)，ｘ8＋１）
【００３８】
次に、テキストＴの準同型暗号化について、まずテキスト多項式ｍt（Ｔ）＝１＋ｘ＋ｘ3＋ｘ4＋ｘ5＋ｘ7を生成し、このテキスト多項式ｍt（Ｔ）を公開鍵ｐｋで暗号化すると以下のようになる。
Enc（ｍt（Ｔ），ｐｋ）＝（ｃ０，ｃ１）
ｃ０＝Mod（Mod(571455796,1073741857)＊ｘ7＋Mod(134025403,1073741857)＊ｘ6＋Mod(5586025,1073741857)＊ｘ5＋Mod(982959780,1073741857)＊ｘ4＋Mod(172339206,1073741857)＊ｘ3＋Mod(484151018,1073741857)＊ｘ2＋Mod(843536573,1073741857)＊ｘ＋Mod(647203954,1073741857)，ｘ8＋１）
ｘｃ１＝Mod（Mod(483026714,1073741857)＊ｘ7＋Mod(807015171,1073741857)＊ｘ6＋Mod(282283030,1073741857)＊ｘ5＋Mod(326992586,1073741857)＊ｘ4＋Mod(809754218,1073741857)＊ｘ3＋Mod(19049111,1073741857)＊ｘ2＋Mod(406264220,1073741857)＊ｘ＋Mod(18166841,1073741857)，ｘ8＋１）
【００３９】
次に、パターンＰの準同型暗号化については、パターン多項式ｍp（Ｐ）＝−ｘn−ｘn-1−ｘn-2＝１−ｘ6−ｘ7（長さｌ＝３）を生成し、このパターン多項式ｍp（Ｐ）を公開鍵ｐｋで暗号化すると以下のように表される。
Enc（ｍp（ｐ），ｐｋ）＝（ｂ０，ｂ１）
ｂ０＝Mod（Mod(559859414,1073741857)＊ｘ7＋Mod(567905533,1073741857)＊ｘ6＋Mod(12416926,1073741857)＊ｘ5＋Mod(844327741,1073741857)＊ｘ4＋Mod(167539656,1073741857)＊ｘ3＋Mod(473962809,1073741857)＊ｘ2＋Mod(200462840,1073741857)＊ｘ＋Mod(281512325,1073741857)，ｘ8＋１）
ｂ１＝Mod（Mod(866509748,1073741857)＊ｘ7＋Mod(110516036,1073741857)＊ｘ6＋Mod(103878204,1073741857)＊ｘ5＋Mod(419487345,1073741857)＊ｘ4＋Mod(208664258,1073741857)＊ｘ3＋Mod(230233533,1073741857)＊ｘ2＋Mod(428440586,1073741857)＊ｘ＋Mod(1069138858,1073741857)，ｘ8＋１）
【００４０】
さらに、暗号化テキストEnc（ｍt（Ｔ），ｐｋ）と暗号化パターンEnc（ｍp（Ｐ），ｐｋ）に対して、Ｃl＝−ｘn−ｘn-1−ｘn-2＝１−ｘ6−ｘ7（長さｌ＝３）と、Ｃk＝１＋ｘ＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＋ｘ7（長さｋ＝８）とを生成する。そして、（３）式により暗号化距離計算結果（ｄ０，ｄ１，ｄ２）を算出する。
ｄ０＝Mod（Mod(797968254, 1073741857)＊ｘ7＋Mod(466213893, 1073741857)＊ｘ6＋Mod(252129696, 1073741857)＊ｘ5＋Mod(1009528361, 1073741857)＊ｘ4＋Mod(535752679, 1073741857)＊ｘ3＋Mod(91616621, 1073741857)＊ｘ2＋Mod(627437050, 1073741857)＊ｘ＋Mod(983411190, 1073741857)，ｘ8＋１)
ｄ１＝Mod（Mod(702170729, 1073741857)＊ｘ7＋Mod(300526001, 1073741857)＊ｘ6＋Mod(385829973, 1073741857)＊ｘ5＋Mod(6675019, 1073741857)＊ｘ4＋Mod(571006407, 1073741857)＊ｘ3＋Mod(627553259, 1073741857)＊ｘ2＋Mod(657519649, 1073741857)＊ｘ＋Mod(465629239, 1073741857)，ｘ8＋１）
ｄ２＝Mod（Mod(249662899, 1073741857)＊ｘ7＋Mod(819300197, 1073741857)＊ｘ6＋Mod(802151858, 1073741857)＊ｘ5＋Mod(1002057738, 1073741857)＊ｘ4＋Mod(759197621, 1073741857)＊ｘ3＋Mod(488279887, 1073741857)＊ｘ2＋Mod(105297021, 1073741857)＊ｘ＋Mod(517181369, 1073741857)，ｘ8＋１）
【００４１】
最後に、上記の暗号計算結果を秘密鍵ｓｋを用いて復号すると、その復号結果はベクトルｍ＝［２，０，２，２，２，０，２，７］となる。このうち判定に採用できるのは０番目からｋ−ｌ＝８−３＝５番目までの値である。多項式で表現すれば、２＋２ｘ2＋２ｘ3＋２ｘ4となり、係数が０の位置がｘの１次及び５次の項であることが分かる。
【００４２】
よって、パターンＰはテキストＴの２番目と６番目の部分ベクトルＴ(2)及びＴ(6)に一致していることがわかる。
【００４３】
本発明の一実施の形態に係るシステムの概要を図３に示す。インターネットなどのネットワーク１には、マッチング対象のテキスト等を登録する処理を行う１又は複数の提供者装置５と、マッチング対象のテキスト等に対するパターンの照合処理を要求する１又は複数の照合者装置７と、例えばクラウドに含まれる情報処理装置３とが接続されている。
【００４４】
次に、図４に提供者装置５の機能ブロック図を示す。提供者装置５は、入力部５０と、第１データ格納部５１と、バイナリ変換部５２と、第２データ格納部５３と、多項式変換部５４と、第３データ格納部５５と、暗号化部５６と、公開鍵格納部５７と、第４データ格納部５８と、送信部５９とを有する。
【００４５】
入力部５０は、ユーザから又は接続されている他のコンピュータなどから、情報処理装置３に登録すべきマッチング対象のテキスト等のデータを取得し、第１データ格納部５１に格納する。また、バイナリ変換部５２は、第１データ格納部５１に格納されているデータを、バイナリ化する処理を実行し、第２データ格納部５３に格納する。多項式変換部５４は、第２データ格納部５３に格納されているバイナリベクトルを多項式に変換し、当該多項式のデータを第３データ格納部５５に格納する。暗号化部５６は、多項式演算可能な準同型暗号方式に従って、公開鍵格納部５７に格納されている照合者の公開鍵を用いて第３データ格納部５５に格納されている多項式を暗号化し、暗号化されたデータを第４データ格納部５８に格納する。送信部５９は、第４データ格納部５８に格納されているデータ及びテキストの長さｋを、情報処理装置３へ送信する。
【００４６】
次に、図５に照合者装置７の機能ブロック図を示す。照合者装置７は、入力部７０と、第１データ格納部７１と、バイナリ変換部７２と、第２データ格納部７３と、多項式変換部７４と、第３データ格納部７５と、暗号化部７６と、公開鍵格納部７７と、第４データ格納部７８と、送信部７９と、受信部８０と、第５データ格納部８１と、復号化部８２と、秘密鍵格納部８３と、第６データ格納部８４と、判定部８５と、第７データ格納部８６と、出力部８７とを有する。
【００４７】
入力部７０は、ユーザから又は接続されている他のコンピュータなどから、マッチング対象のテキスト等のデータと照合すべきパターンのデータを取得し、第１データ格納部７１に格納する。また、バイナリ変換部７２は、第１データ格納部７１に格納されているデータを、バイナリ化する処理を実行し、第２データ格納部７３に格納する。多項式変換部７４は、第２データ格納部７３に格納されているバイナリベクトルを多項式に変換し、当該多項式のデータを第３データ格納部７５に格納する。暗号化部７６は、多項式演算可能な準同型暗号方式に従って、公開鍵格納部７７に格納されている照合者の公開鍵を用いて第３データ格納部７５に格納されている多項式を暗号化し、暗号化されたデータを第４データ格納部７８に格納する。送信部７９は、第４データ格納部７８に格納されているデータ及びパターンの長さｌを、情報処理装置３へ送信する。
【００４８】
また、受信部８０は、情報処理装置３から暗号演算結果を受信すると、第５データ格納部８１に格納する。復号化部８２は、秘密鍵格納部８３に格納されている照合者の秘密鍵を用いて復号処理を行って、処理結果を第６データ格納部８４に格納する。判定部８５は、第６データ格納部８４に格納された多項式のデータから、テキストなどにおいてパターンと一致する部分が存在するか否かなどを判定し、判定結果を第７データ格納部８６に格納する。出力部８７は、第７データ格納部８６に格納されている判定結果を、出力装置（例えば他のコンピュータや印刷装置や表示装置など）へ出力する。
【００４９】
次に、図６に、情報処理装置３の機能ブロック図を示す。情報処理装置３は、登録部３１と、データベース３２と、受信部３３と、補助データ生成部３４と、暗号演算処理部３５と、演算結果格納部３６と、送信部３７とを有する。
【００５０】
登録部３１は、提供者装置５からマッチング対象テキスト等の暗号化データ及び長さｋを受信すると、データベース３２に格納する。受信部３３は、照合者装置７から照合すべきパターンの暗号化データ及び長さｌを受信すると、照合すべきパターンの暗号化データについては暗号演算処理部３５に出力し、長さｌについては補助データ生成部３４に出力する。
【００５１】
補助データ生成部３４は、データベース３２に格納されているマッチング対象テキスト等の暗号化データについての長さｋと、受信部３３から受け取った長さｌとから、補助データを生成し、暗号演算処理部３５に出力する。
【００５２】
暗号演算処理部３５は、照合すべきパターンの暗号化データと補助データとデータベース３２に格納されているマッチング対象テキスト等の暗号化データとを用いて、上記（３）式で表される暗号演算を実行し、演算結果及びｋ−ｌを演算結果格納部３６に格納する。そして、送信部３７は、受信部３３から得られる照合要求元に対して、演算結果格納部３６に格納されている演算結果及びｋ−ｌを送信する。
【００５３】
次に、図７及び図８を用いて図３に示したシステムの処理内容について説明する。
【００５４】
まず、提供者装置５が、情報処理装置３に、マッチング対象テキストの暗号化データを登録する際の処理について図７を用いて説明する。
【００５５】
提供者装置５の入力部５０は、例えば情報提供者又は他のコンピュータなどから、情報処理装置３に登録すべきテキスト（テキストは一例であって画像データ、遺伝子記号列等の場合もある）を取得し、第１データ格納部５１に格納する（図７：ステップＳ１）。そして、バイナリ変換部５２は、第１データ格納部５１に格納されているテキストをバイナリ化して、バイナリ化テキストのデータＴ＝（ｔ0，ｔ1，．．．，ｔk-1）を第２データ格納部５３に格納する（ステップＳ３）。
【００５６】
また、多項式変換部５４は、バイナリ化されたテキストＴに対して多項式変換を実行し、多項式変換によって生成された多項式ｍt（Ｔ）を第３データ格納部５５に格納する（ステップＳ５）。具体的には、バイナリ化されたテキストＴの各成分ｔiを昇順に各次元の係数として用いることで多項式ｍt（Ｔ）＝Σiｔiｘiを生成する。なお、多項式変換部５４は、バイナリ化されたテキストＴのビット長ｋも、第３データ格納部５５に格納する。
【００５７】
そして、暗号化部５６は、第３データ格納部５５に格納されている多項式ｍt（Ｔ）を、多項式演算可能な準同型暗号方式に従って、公開鍵格納部５７に格納されている照合者の公開鍵ｐｋを用いて暗号化することで暗号化テキストＥｎｃ（ｍt（Ｔ））を生成し、第４データ格納部５８に格納する（ステップＳ７）。なお、暗号化部５６は、テキストＴのビット長ｋをも第４データ格納部５８に格納する。Ｅｎｃ（Ｚ）は、Ｚを多項式演算可能な準同型暗号方式に従って暗号化する処理を表す。
【００５８】
その後、送信部５９は、第４データ格納部５８に格納されている暗号化テキストＥｎｃ（ｍt（Ｔ））及び長さｋを、情報処理装置３へ送信する（ステップＳ９）。
【００５９】
情報処理装置３の登録部３１は、暗号化テキストＥｎｃ（ｍt（Ｔ））及び長さｋを受信し、データベース３２に登録する（ステップＳ１１）。
【００６０】
以上のような処理を行うことで、暗号化した状態でテキスト等を、クラウドなどに設置された情報処理装置３へ登録することができるようになる。
【００６１】
次に、照合者が、特定のパターンについて照合処理を行わせる際の処理内容を図８を用いて説明する。
【００６２】
照合者装置７の入力部７０は、例えば情報提供者又は他のコンピュータなどから、マッチング対象のテキスト等のデータと照合すべきパターンのデータを取得し、第１データ格納部７１に格納する（図８：ステップＳ２１）。そして、バイナリ変換部７２は、第１データ格納部７１に格納されているテキストをバイナリ化して、バイナリ化テキストのデータＰ＝（ｐ0，ｐ1，．．．，ｐl-1）を第２データ格納部７３に格納する（ステップＳ２３）。
【００６３】
また、多項式変換部７４は、バイナリ化されたパターンＰに対して多項式変換を実行し、多項式変換によって生成された多項式ｍp（Ｐ）を第３データ格納部７５に格納する（ステップＳ２５）。具体的には、バイナリ化されたテキストＰの各成分ｐiを降順に各次元の係数として用いることで多項式ｍp（Ｐ）＝−Σjｐjｘn-jを生成する。なお、多項式変換部７４は、バイナリ化されたパターンＰのビット長ｌも、第３データ格納部７５に格納する。
【００６４】
そして、暗号化部７６は、第３データ格納部７５に格納されている多項式ｍp（Ｐ）を、多項式演算可能な準同型暗号方式に従って、公開鍵格納部７７に格納されている照合者の公開鍵ｐｋを用いて暗号化することで暗号化パターンＥｎｃ（ｍp（Ｐ））を生成し、第４データ格納部７８に格納する（ステップＳ２７）。なお、暗号化部７６は、パターンＰのビット長ｌをも第４データ格納部７８に格納する。
【００６５】
その後、送信部７９は、第４データ格納部７８に格納されている暗号化パターンＥｎｃ（ｍp（Ｐ））及び長さｌを、情報処理装置３へ送信する（ステップＳ２９）。
【００６６】
情報処理装置３の受信部３３は、暗号化パターンＥｎｃ（ｍp（Ｐ））及び長さｌを受信し（ステップＳ３１）、暗号化パターンＥｎｃ（ｍp（Ｐ））については暗号演算処理部３５に出力し、長さｌについては補助データ生成部３４に出力する。
【００６７】
補助データ生成部３４は、受信部３３から暗号化パターンの長さｌを受け取ると、データベース３２に格納されている暗号化テキストの長さｋを読み出し、補助データＣl及びＣkを生成し、暗号演算処理部３５に出力する（ステップＳ３３）。補助データＣl及びＣkは、（４）式及び（５）式に従って生成される。
【００６８】
その後、暗号演算処理部３５は、（３）式に従って、データベース３２に格納されている暗号化テキストＥｎｃ（ｍt（Ｔ））と、暗号化パターンＥｎｃ（ｍp（Ｐ））と、補助データＣl及びＣkとを用いて、暗号化パターンマッチングの演算を実行し、演算結果ｄ＝（ｄ０，ｄ１，．．．）を演算結果格納部３６に格納する（ステップＳ３５）。
【００６９】
そして、送信部３７は、演算結果格納部３６に格納された演算結果ｄ及び長さｋ−ｌを、受信部３３へ暗号化パターン等を送信してきた照合者装置７へ送信する（ステップＳ３７）。
【００７０】
照合者装置７の受信部８０は、情報処理装置３から暗号化パターンマッチングの演算結果ｄ及び長さｋ−ｌを受信し、第５データ格納部８１に格納する（ステップＳ３９）。そして、復号化部８２は、秘密鍵格納部８３に格納されている秘密鍵ｓｋを用いて、多項式演算可能な準同型暗号方式に従って、演算結果ｄを復号化することで、復号結果ベクトルｍ＝［ｍ0，ｍ1，．．．，ｍn-1］を生成し、第６データ格納部８４に格納する（ステップＳ４１）。第６データ格納部８４には、ｋ−ｌの値も格納される。
【００７１】
判定部８５は、第６データ格納部８４に格納された復号結果ベクトルにおいて、０からｋ−ｌまでの要素値において０となる位置を特定することで、マッチング対象テキストにおいてパターンと一致する部分が存在するか否かを判定する（ステップＳ４３）。ベクトルｍ＝［２，０，２，２，２，０，２，７］且つｋ−ｌ＝８−３＝５であれば、左から順番に［２，０，２，２，２，０］において０となる位置「１」及び「５」が存在しているので、マッチング対象テキストにおいてパターンと一致する部分が存在することが分かる。さらに、バイナリ化されたテキストＴにおける２ビット目及び６ビット目にパターンと一致する部分が存在することも分かる。判定部８５は、判定結果を第７データ格納部８６に格納する。出力部８７は、照合者などの要求に応じて、出力装置（表示装置、印刷装置、他のコンピュータ）などに対して判定結果を出力する。
【００７２】
以上のような処理を実行することで、照合すべきパターンについても暗号化したままで、マッチング対象テキストと一致するか否かを判断するための暗号化パターンマッチングの演算結果を得ることができる。そして、照合者装置７において、照合者しか保持していない秘密鍵で復号すれば、簡単な処理にて、マッチング対象テキストとの一致の有無及びパターンが一致する位置を特定できるようになる。
【００７３】
例えば、バイナリ化されたテキストＴにおけるｋ個の要素の各々を暗号化するような方式を採用する場合には、ｋ個の暗号化テキストのデータが生成される。一方、上で述べた本実施の形態によれば、多項式変換を実行するため暗号化テキストは１個のみとなる。同様に、前者の方法を採用する場合には、バイナリ化されたパターンＰにおけるｌ個の要素の各々を暗号化するので、ｌ個の暗号化テキストのデータが生成される。一方、上で述べた本実施の形態によれば、多項式変換を実行するため暗号化パターンは１個のみとなる。このように暗号データのサイズが削減されている。
【００７４】
これに対して、前者の方式を採用すると、暗号化パターンマッチングの演算は、０からｋ−ｌまでの各要素位置についてハミング距離を算出することになる。そうすると、暗号文空間におけるハミング距離計算Σil（Ｅ（ｔi）＋Ｅ（ｐi）−２Ｅ（ｔi）＊Ｅ（ｐi））（Ｅ（ｔi）は、テキストＴのｉ番目の要素の暗号化結果を表し、Ｅ（ｐi）は、パターンＰのｉ番目の要素の暗号化結果を表す）をｋ−ｌ＋１回行うことになる。すなわち、暗号乗算が計算コストの大部分であるとすると、ｌ＊（ｋ−ｌ＋１）回の暗号乗算が行われる。一方、本実施の形態では、（３）式から暗号乗算は３回であることが分かる。
【００７５】
このように計算負荷の点においても、本実施の形態の方が削減されていることが分かる。
【００７６】
以上のように、本実施の形態によれば、暗号化パターンマッチングの計算コストが削減できる。
【００７７】
なお、上で述べた実施の形態における演算は基本形を示しただけであり、様々な変形が可能である。
【００７８】
例えば、図９に示すように、バイナリ化されたテキストＴの多項式ｍt（Ｔ）と、バイナリ化されたパターンＰの多項式ｍp（Ｐ）と、補助データＣlと、補助データＣkとについて、符号を様々に変更することができる。但し、距離計算式を具体的に書き下した場合には、同じ内容となっている。
【００７９】
図９からも分かるように、バイナリ化されたテキストＴの多項式ｍt（Ｔ）を生成する際には、バイナリ化されたテキストＴの各要素を昇順に係数として用いているが、この多項式ｍt（Ｔ）に対して用いられる補助データＣlについては、降順に係数が１となっている、ｎ次から（ｎ−ｌ＋１）次までの多項式となっている。また、バイナリ化されたパターンＰの多項式ｍp（Ｐ）については、バイナリ化されたパターンＰの各要素を降順に係数として、ｎ次から（ｎ−ｌ＋１）次までの多項式に用いているが、この多項式ｍp（Ｐ）に対して用いられる補助データＣkについては、昇順に係数が１となっている多項式が用いられている。すなわち、昇順と降順との組み合わせで、乗算が行われている。
【００８０】
また、図１０に示すような変形も可能である。図１０は、昇順と降順との組み合わせを反転させ、符号の反転を考慮したものである。
【００８１】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、各装置の機能ブロック図は一例であって、プログラムモジュール構成とは一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、ステップの順番を入れ替えたり、複数ステップを並列実行するようにしても良い。
【００８２】
また、各装置については１台のコンピュータではなく、複数台のコンピュータにて実装される場合もある。また、照合者装置７と提供者装置５とが一体となっている場合もある。
【００８３】
なお、上で述べた情報処理装置３、提供者装置５及び照合者装置７は、コンピュータ装置であって、図１１に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００８４】
以上述べた本実施の形態をまとめると、以下のようになる。
【００８５】
本発明の第１の態様に係る情報処理方法は、（Ａ）第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、（Ｂ）第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、（Ｃ）第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する処理を含む。
【００８６】
このように多項式を生成した上で多項式演算可能な準同型暗号方式によって暗号化することで、暗号化データのデータ量及び計算負荷を削減でき、秘匿化パターンマッチングのコスト削減に繋がる。なお、第１のデータは、マッチング対象テキスト等である場合もあれば、照合すべきパターンである場合もあり、これらについては昇順と降順とで異なる順番を採用する。
【００８７】
また、上記情報処理方法は、（Ｄ）第２のデータから生成された第２のバイナリベクトルの要素を、次数について第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られ且つ第２のデータ格納部に格納されている、暗号化された第２の多項式と、暗号化された第１の多項式とを用いて、暗号文空間における所定の演算を実行する処理をさらに含むようにしても良い。この際、上記所定の演算が、当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が第２のバイナリベクトルに対する第１のバイナリベクトルの各対比位置における距離を表すように規定される場合もある。
【００８８】
このように、第１の多項式及び第２の多項式を復号することなく、暗号化したままで演算を実行することで、パターンマッチングがなされる。なお、所定の演算については、上でも述べたように多項式変換を実行しているため、計算負荷が下げられている。
【００８９】
また、上記情報処理方法は、（Ｅ）所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数のうち値がゼロとなる係数が存在するか否かを判断する処理をさらに含むようにしても良い。上記所定の演算は、このような判断ができるようにするための演算であり、存在の有無だけではなく、パターンと一致する位置をも特定できる。
【００９０】
さらに、上で述べた所定の演算が、暗号化された第１の多項式と第１の補助データとの積の項と、暗号化された第２の多項式と第２の補助データとの積の項と、暗号化された第１の多項式と暗号化された第２の多項式との積の項とを含む距離計算式によって規定されるようにしても良い。このように暗号乗算の個数が削減されている。
【００９１】
さらに、上で述べた第１の補助データが、（ａ）暗号化された第１の多項式に対応する第１の順番が昇順であれば、所定次数の多項式であって係数が全て１の多項式のうち降順に第１のバイナリベクトルの要素数の項のみを取り出した多項式を含み、（ｂ）暗号化された第１の多項式に対応する第１の順番が降順であれば、第１のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含む場合もある。また、第２の補助データが、（ｃ）暗号化された第２の多項式に対応する第２の順番が降順であれば、第２のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含み、（ｄ）暗号化された第２の多項式に対応する第２の順番が昇順であれば、所定次数の多項式であって係数が全て１の多項式のうち降順に第２のバイナリベクトルの要素数の項のみを取り出した多項式を含む場合もある。このように所定の演算の本質を変更せずに様々な変形が可能である。
【００９２】
さらに、上記情報処理方法は、（Ｆ）暗号化された第１の多項式を、第２のデータから生成された第２のバイナリベクトルの要素を、次数について第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された第２の多項式を格納する第２の格納部にアクセス可能な他のコンピュータに送信し、（Ｇ）他のコンピュータから、暗号化された第１の多項式と暗号化された第２の多項式とを用いて暗号文空間における所定の演算を実行することで得られた演算結果を受信し、（Ｈ）演算結果を復号することで得られる第３の多項式の各項の係数のうち値がゼロとなる係数を特定する処理をさらに含むようにしても良い。実施の形態に係る照合者装置であれば、このような処理を実行する。
【００９３】
本発明の第２の態様に係る情報処理方法は、（Ａ）第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された第１の多項式を他のコンピュータから受信し、（Ｂ）第２のデータから生成された第２のバイナリベクトルの要素を、第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された第２の多項式と、暗号化された第１の多項式とを用いて、暗号文空間における所定の演算を実行し、（Ｃ）所定の演算の結果を、他のコンピュータに送信する処理を含む。そして、上記所定の演算が、当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が第２のバイナリベクトルに対する第１のバイナリベクトルの各対比位置における距離を表すように規定されるものである。
【００９４】
所定の演算は、多項式変換されたデータを用いているため、演算コストが削減されている。
【００９５】
なお、上で述べたような処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【００９６】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００９７】
（付記１）
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する
処理を含み、１又は複数のコンピュータにより実行される情報処理方法。
【００９８】
（付記２）
第２のデータから生成された第２のバイナリベクトルの要素を、次数について前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つ第２のデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行する
処理をさらに含み、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
付記１記載の情報処理方法。
【００９９】
（付記３）
前記所定の演算の演算結果を復号することで得られる前記第３の多項式の各項の係数のうち値がゼロとなる係数が存在するか否かを判断する処理
をさらに含む付記２記載の情報処理方法。
【０１００】
（付記４）
前記所定の演算が、
暗号化された前記第１の多項式と第１の補助データとの積の項と、暗号化された前記第２の多項式と第２の補助データとの積の項と、暗号化された前記第１の多項式と暗号化された前記第２の多項式との積の項とを含む距離計算式によって規定される
付記２又は３記載の情報処理方法。
【０１０１】
（付記５）
前記第１の補助データが、
暗号化された前記第１の多項式に対応する前記第１の順番が昇順であれば、所定次数の多項式であって係数が全て１の多項式のうち降順に前記第１のバイナリベクトルの要素数の項のみを取り出した多項式を含み、
暗号化された前記第１の多項式に対応する前記第１の順番が降順であれば、前記第１のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含み、
前記第２の補助データが、
暗号化された前記第２の多項式に対応する前記第２の順番が降順であれば、前記第２のバイナリベクトルの要素数に対応する次数の多項式であって係数が全て１の多項式を含み、
暗号化された前記第２の多項式に対応する前記第２の順番が昇順であれば、前記所定次数の多項式であって係数が全て１の多項式のうち降順に前記第２のバイナリベクトルの要素数の項のみを取り出した多項式を含む、
付記４記載の情報処理方法。
【０１０２】
（付記６）
暗号化された前記第１の多項式を、第２のデータから生成された第２のバイナリベクトルの要素を、次数について前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第２の多項式を格納する第２の格納部にアクセス可能な他のコンピュータに送信し、
前記他のコンピュータから、暗号化された前記第１の多項式と暗号化された前記第２の多項式とを用いて暗号文空間における所定の演算を実行することで得られた演算結果を受信し、
前記演算結果を復号することで得られる第３の多項式の各項の係数のうち値がゼロとなる係数を特定する
処理をさらに含む付記１記載の情報処理方法。
【０１０３】
（付記７）
コンピュータが、
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信し、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行し、
前記所定の演算の結果を、前記他のコンピュータに送信する
処理を含み、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
情報処理方法。
【０１０４】
（付記８）
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成し、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成し、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する
処理を、１又は複数のコンピュータに実行させるためのプログラム。
【０１０５】
（付記９）
コンピュータに、
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信し、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行し、
前記所定の演算の結果を、前記他のコンピュータに送信する
処理を実行させ、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
プログラム。
【０１０６】
（付記１０）
第１のデータ格納部に格納される第１のデータから第１のバイナリベクトルを生成するバイナリ変換部と、
前記第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を生成する多項式変換部と、
前記第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化する暗号化部と、
を有する情報処理装置。
【０１０７】
（付記１１）
第１のデータから生成された第１のバイナリベクトルの要素を、次数について降順と昇順とのうちいずれかである第１の順番で係数として用いることで表される第１の多項式を、多項式演算可能な準同型暗号方式によって暗号化することで得られる、暗号化された前記第１の多項式を他のコンピュータから受信する受信部と、
第２のデータから生成された第２のバイナリベクトルの要素を、前記第１の順番とは異なる第２の順番で係数として用いることで表される第２の多項式を、前記多項式演算可能な準同型暗号方式によって暗号化することで得られ且つデータ格納部に格納されている、暗号化された前記第２の多項式と、暗号化された前記第１の多項式とを用いて、暗号文空間における所定の演算を実行する暗号演算処理部と、
前記所定の演算の結果を、前記他のコンピュータに送信する送信部と、
を有し、
前記所定の演算が、
当該所定の演算の演算結果を復号することで得られる第３の多項式の各項の係数が前記第２のバイナリベクトルに対する前記第１のバイナリベクトルの各対比位置における距離を表すように規定される
情報処理装置。
【符号の説明】
【０１０８】
３１  登録部
３２  データベース
３３  受信部
３４  補助データ生成部
３５  暗号演算処理部
３６  演算結果格納部
３７  送信部
５０  入力部
５１  第１データ格納部
５２  バイナリ変換部
５３  第２データ格納部
５４  多項式変換部
５５  第３データ格納部
５６  暗号化部
５７  公開鍵格納部
５８  第４データ格納部
５９  送信部
７０  入力部
７１  第１データ格納部
７２  バイナリ変換部
７３  第２データ格納部
７４  多項式変換部
７５  第３データ格納部
７６  暗号化部
７７  公開鍵格納部
７８  第４データ格納部
７９  送信部
８０  受信部
８１  第５データ格納部
８２  復号化部
８３  秘密鍵格納部
８４  第６データ格納部
８５  判定部
８６  第７データ格納部
８７  出力部
【図１】
2015031935.tif 000003
【図２】
2015031935.tif 000004
【図３】
2015031935.tif 000005
【図４】
2015031935.tif 000006
【図５】
2015031935.tif 000007
【図６】
2015031935.tif 000008
【図７】
2015031935.tif 000009
【図８】
2015031935.tif 000010
【図９】
2015031935.tif 000011
【図１０】
2015031935.tif 000012
【図１１】
2015031935.tif 000013