(57)【要約】【課題】秘匿化パターンマッチングの汎用性を高める。【解決手段】本方法は、第1テキストを数値ベクトル化することで生成された第1数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第1多項式と、第1数値ベクトルの各成分を二乗した第2数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第2多項式と、三乗した場合の第3多項式と、第2テキストを数値ベクトル化することで生成された第4数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第4多項式と、第4数値ベクトルの各成分を二乗した第5数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第5多項式と、三乗した場合の第6多項式とを用いて所定の演算を暗号化したまま実行し、所定の演算の演算結果を返信する処理を含む。【選択図】図３
2015212756.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”があるか否かを判定する処理を考える。このとき、図１に示すように、テキスト文字列Ｔに対して、パターン文字列Ｐを１文字ずつずらしながら、テキストとパターンが一致する文字の個数（距離とも呼ぶ）を算出する。図１では、個数を表す数値の並びをスコアベクトルと呼ぶ。今回の例ではパターン文字列Ｐの長さが５なので、スコアベクトルの値が５の成分のところで、テキスト文字列Ｔとパターン文字列Ｐとが一致することがわかる。
【００１５】
このように、暗号化なしのパターンマッチングでは、テキスト文字列Ｔとパターン文字列Ｐに対して、パターン文字列Ｐを１文字ずつずらしながらテキスト文字列との距離を計算していく。
【００１６】
一方、準同型暗号を利用した秘匿パターンマッチング（例えば非特許文献３）では、データサイズや距離計算コストを削減するために、バイナリ化したテキストの各ビットを次数について昇順で係数に用いることで表される多項式を求め、多項式演算可能な同準型暗号方式（例えば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＋１）と表すことが多い。
【００２８】
しかしながら、いずれの文字とも一致することを表す特殊文字（ワイルドカードと呼ぶ）についての取り扱いは考慮されておらず、ワイルドカードを含むような一般的なパターンによる秘匿パターンマッチングを効率的に行えない。
【先行技術文献】
【非特許文献】
【００２９】
【非特許文献１】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.
【非特許文献３】M. Yasuda, T, Shimoyama, J. Kogure, K. Yokoyama and T. Koshiba, "Secure Pattern Matching using Somewhat Homomorphic Encryption", CCSW'13, November 8, 2013, pp. 65-76
【発明の概要】
【発明が解決しようとする課題】
【００３０】
本発明の目的は、一側面によれば、秘匿化パターンマッチングの汎用性を高めるための技術を提供することである。
【課題を解決するための手段】
【００３１】
本発明の第１の態様に係るマッチング方法は、（Ａ）第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、（Ｂ）第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、（Ｃ）第１の数値ベクトルを多項式変換した第１の多項式と、第２の数値ベクトルを多項式変換した第２の多項式と、第３の数値ベクトルを多項式変換した第３の多項式とを生成し、（Ｄ）第１の多項式と第２の多項式と第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化し、（Ｅ）第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第４の多項式と、第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第５の多項式と、第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第６の多項式とを格納する第２のデータ格納部に格納された第４の多項式と第５の多項式と第６の多項式と、暗号化された第１の多項式と第２の多項式と第３の多項式とを用いて所定の演算を暗号化したまま実行し、（Ｆ）所定の演算の演算結果を復号化する処理を含む。
【００３２】
本発明の第２の態様に係る秘匿処理方法は、（Ａ）第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、（Ｂ）第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、（Ｃ）第１の数値ベクトルを多項式変換した第１の多項式と、第２の数値ベクトルを多項式変換した第２の多項式と、第３の数値ベクトルを多項式変換した第３の多項式とを生成し、（Ｄ）第１の多項式と第２の多項式と第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化する処理を含む。
【００３３】
また、本発明の第３の態様に係る秘匿処理方法は、（Ａ）第１のテキストを数値ベクトル化することで生成された第１の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第１の多項式と、第１の数値ベクトルの各成分を二乗した第２の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第２の多項式と、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第３の多項式とを受信し、（Ｂ）第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第４の多項式と、第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第５の多項式と、第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第６の多項式とを格納するデータ格納部に格納された第４の多項式と第５の多項式と第６の多項式と、第１の多項式と第２の多項式と第３の多項式とを用いて所定の演算を暗号化したまま実行し、（Ｃ）所定の演算の演算結果を返信する処理を含む。
【発明の効果】
【００３４】
一側面によれば、秘匿化パターンマッチングの汎用性を高めることができるようになる。
【図面の簡単な説明】
【００３５】
【図１】図１は、パターンマッチングを説明するための図である。
【図２】図２は、暗号距離計算を解説するための図である。
【図３】図３は、本実施の形態に係る考え方を表す図である。
【図４】図４は、本実施の形態に係るシステムの概要を示す図である。
【図５】図５は、提供者装置の機能ブロック図である。
【図６】図６は、照合者装置の機能ブロック図である。
【図７】図７は、情報処理装置の機能ブロック図である。
【図８】図８は、登録処理の処理フローを示す図である。
【図９】図９は、照合処理の処理フローを示す図である。
【図１０】図１０は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００３６】
まず、本実施の形態に係る処理の概要を説明する。本実施の形態においても、図２（Ａ）乃至（Ｄ）を用いて説明したのと同様に、平文空間において距離を定義して、復号した結果が当該平文空間において定義された距離に合致するように、暗号空間における演算を規定する。
【００３７】
テキストをＴ＝（ｔ0，ｔ1，ｔ2，．．．）というように数値ベクトル化し、同じくパターンについてもＰ＝（ｐ0，ｐ1，ｐ2，．．．ｐl-1）というように数値ベクトル化する。なお、ワイルドカードについては０を割り当て、その他の文字については所定のルール（例えばＡに対して１、Ｂに対して２、Ｃに対して３など）に従って数値ベクトル化する。
【００３８】
この時、図３左側に模式的に示すように、テキストに対してパターンを１成分ずつずらしながら一致しているか否かを判断することを考える。例えばｔiを先頭にした、テキストの一部と、パターンとの距離を、図３右側のような式で定義する。
【００３９】
この式は、ｊ＝０乃至ｌ−１の範囲における任意のｊについて、ｐj＝ｔi+j、すなわち文字が一致する場合に、その値が０となる。同様に、ｐj＝０、すなわちｐjがワイルドカードである場合にも、その値は０となる。さらに、ｔi+j＝０、すなわちｔi+jがワイルドカードである場合にも、その値は０となる。
【００４０】
このような距離を定義して距離が０となるｉを見つければ、パターンの数値ベクトルＰは、テキストの数値ベクトルＴの成分ｔiから一致していることが分かる。
【００４１】
ここで、長さｋのテキストの数値ベクトルＴ＝（ｔ0，ｔ1，...，ｔk-1）から、各成分を昇順で係数として用いる多項式ｍt（Ｔ）＝Σiｔiｘiを生成する。
【００４２】
同様に、長さｌのパターンの数値ベクトルＰ＝（ｐ0，ｐ1，...，ｐl-1）から、各成分を降順に係数として用いる多項式ｍp（Ｐ）＝−Σjｐjｘn-jを生成する。
【００４３】
そして、図３右側に示す式の値が、ｉ＝０乃至ｋ−１の範囲における任意のｉについて、ｘiの係数となるように、多項式で表すと以下のようになる。
ｍt（Ｔ）＊ｍp（Ｐ3）＋ｍt（Ｔ3）＊ｍp（Ｐ）−２ｍt（Ｔ2）＊ｍp（Ｐ2）    （７）
【００４４】
（７）式は、非特許文献２に示すような多項式演算可能な準同型暗号方式を用いれば、以下のように表される。
Ｅ（ｍt（Ｔ））＊Ｅ（ｍp（Ｐ3））＋Ｅ（ｍt（Ｔ3））＊Ｅ（ｍp（Ｐ））−２Ｅ（ｍt（Ｔ2））＊Ｅ（ｍp（Ｐ2））    （８）
【００４５】
よって、Ｅ（ｍt（Ｔ））、Ｅ（ｍp（Ｐ3））、Ｅ（ｍt（Ｔ3））、Ｅ（ｍp（Ｐ））、Ｅ（ｍt（Ｔ2））及びＥ（ｍp（Ｐ2））を用意すれば、テキストもパターンも秘匿したまま距離演算を行うことができるようになる。この場合、平文空間で一致した場合には距離０となる。
【００４６】
次に、図４乃至図９を用いて、本実施の形態に係るシステムの概要を説明する。
【００４７】
図４に示すように、インターネットなどのネットワーク１には、マッチング対象のテキスト等を登録する処理を行う１又は複数の提供者装置５と、マッチング対象のテキスト等に対するパターンの照合処理を要求する１又は複数の照合者装置７と、例えばクラウドに含まれる情報処理装置３とが接続されている。
【００４８】
次に、図５に提供者装置５の機能ブロック図を示す。提供者装置５は、入力部５０と、第１データ格納部５１と、第１変換部５２と、第２データ格納部５３と、乗算部５４と、第３データ格納部５５と、第２変換部５６と、第４データ格納部５７と、暗号化部５８と、公開鍵格納部５９と、第５データ格納部６０と、送信部６１とを有する。
【００４９】
入力部５０は、ユーザから又は接続されている他のコンピュータなどから、情報処理装置３に登録すべきマッチング対象のテキスト等のデータを取得し、第１データ格納部５１に格納する。また、第１変換部５２は、第１データ格納部５１に格納されているデータを、数値ベクトル化する処理を実行し、第２データ格納部５３に格納する。
【００５０】
乗算部５４は、第２データ格納部５３に格納されている数値ベクトルＴの各成分の値を二乗することで得られる数値ベクトルＴ2と、三乗することで得られる数値ベクトルＴ3とを生成し、第３データ格納部５５に格納する。
【００５１】
第２変換部５６は、第２データ格納部５３に格納されている数値ベクトルＴを多項式に変換し、第３データ格納部５５に格納されている数値ベクトルＴ2及びＴ3を多項式に変換し、当該多項式のデータを第４データ格納部５７に格納する。
【００５２】
暗号化部５８は、多項式演算可能な準同型暗号方式に従って、公開鍵格納部５９に格納されている照合者の公開鍵を用いて第４データ格納部５７に格納されている各多項式を暗号化し、暗号化されたデータを第５データ格納部６０に格納する。送信部６１は、第５データ格納部６０に格納されているデータ及びテキストの長さｋを、情報処理装置３へ送信する。
【００５３】
次に、図６に照合者装置７の機能ブロック図を示す。照合者装置７は、入力部７０と、第１データ格納部７１と、第１変換部７２と、第２データ格納部７３と、乗算部７４と、第３データ格納部７５と、第２変換部７６と、第４データ格納部７７と、暗号化部７８と、公開鍵格納部７９と、第５データ格納部８０と、送信部８１と、受信部８２と、第６データ格納部８３と、復号化部８４と、秘密鍵格納部８５と、第７データ格納部８６と、判定部８７と、第８データ格納部８８と、出力部８９とを有する。
【００５４】
入力部７０は、ユーザから又は接続されている他のコンピュータなどから、マッチング対象のテキスト等のデータと照合すべきパターンのデータを取得し、第１データ格納部７１に格納する。また、第２変換部７２は、第１データ格納部７１に格納されているデータを、数値ベクトル化する処理を実行し、第２データ格納部７３に格納する。
【００５５】
乗算部７４は、第２データ格納部７３に格納されている数値ベクトルＰの各成分の値を二乗することで得られる数値ベクトルＰ2と、三乗することで得られる数値ベクトルＰ3とを生成し、第３データ格納部７５に格納する。
【００５６】
第２変換部７６は、第２データ格納部７３に格納されている数値ベクトルＰを多項式に変換し、第３データ格納部７５に格納されている数値ベクトルＰ2及びＰ3を多項式に変換し、当該多項式のデータを第４データ格納部７７に格納する。
【００５７】
暗号化部７８は、多項式演算可能な準同型暗号方式に従って、公開鍵格納部７９に格納されている照合者の公開鍵を用いて第４データ格納部７７に格納されている各多項式を暗号化し、暗号化されたデータを第５データ格納部８０に格納する。送信部８１は、第５データ格納部８０に格納されているデータを、情報処理装置３へ送信する。
【００５８】
また、受信部８２は、情報処理装置３から暗号演算結果を受信すると、第６データ格納部８３に格納する。復号化部８４は、秘密鍵格納部８５に格納されている照合者の秘密鍵を用いて復号処理を行って、処理結果を第７データ格納部８６に格納する。判定部８７は、第２データ格納部７３に格納されているデータ（パターンの長さｌ）と、第７データ格納部８６に格納されたデータから、テキストなどにおいてパターンと一致する部分が存在するか否かなどを判定し、判定結果を第８データ格納部８８に格納する。出力部８９は、第８データ格納部８８に格納されている判定結果を、出力装置（例えば他のコンピュータや印刷装置や表示装置など）へ出力する。
【００５９】
次に、図７に、情報処理装置３の機能ブロック図を示す。情報処理装置３は、登録部３１と、データベース３２と、受信部３３と、暗号演算処理部３５と、演算結果格納部３６と、送信部３７とを有する。
【００６０】
登録部３１は、提供者装置５からマッチング対象テキスト等の暗号化データ及び長さｋを受信すると、データベース３２に格納する。受信部３３は、照合者装置７から照合すべきパターンの暗号化データを受信すると、照合すべきパターンの暗号化データについては暗号演算処理部３５に出力する。
【００６１】
暗号演算処理部３５は、照合すべきパターンの暗号化データとデータベース３２に格納されているマッチング対象テキスト等の暗号化データとを用いて、上記（８）式で表される暗号演算を実行し、演算結果を演算結果格納部３６に格納する。そして、送信部３７は、受信部３３から得られる照合要求元に対して、演算結果格納部３６に格納されている演算結果及びテキストの長さｋを送信する。
【００６２】
次に、図８及び図９を用いて図４に示したシステムの処理内容について説明する。
【００６３】
まず、提供者装置５が、情報処理装置３に、マッチング対象テキストの暗号化データを登録する際の処理について図８を用いて説明する。
【００６４】
提供者装置５の入力部５０は、例えば情報提供者又は他のコンピュータなどから、情報処理装置３に登録すべきテキスト（テキストは一例であって画像データ、音声データ、遺伝子記号列等の場合もある）を取得し、第１データ格納部５１に格納する（図８：ステップＳ１）。そして、第１変換部５２は、第１データ格納部５１に格納されているテキストを数値ベクトル化することで数値ベクトルＴ＝（ｔ0，ｔ1，．．．，ｔk-1）を第２データ格納部５３に格納する（ステップＳ３）。テキストにもワイルドカードが含まれる場合がある。ワイルドカードについては原則的には「０」を割り当て、その他の文字については予め定められた数値を割り当てる。例えば、遺伝子の種類毎に特定の数値を予め割り当てておき、暗号化すべき遺伝子配列に含まれる遺伝子に応じて数値を選択して数値ベクトル化する。
【００６５】
また、乗算部５４は、第２データ格納部５３に格納されている数値ベクトルＴの各成分を二乗することで数値ベクトルＴ2を算出し、三乗することで数値ベクトルＴ3を算出し、第３データ格納部５５に格納する（ステップＳ５）。
【００６６】
さらに、第２変換部５６は、第２データ格納部５３に格納されている数値ベクトルＴと、第３データ格納部５５に格納されている数値ベクトルＴ2及びＴ3とに対して多項式変換を実行し、多項式変換によって生成された多項式ｍt（Ｔ）、ｍt（Ｔ2）及びｍt（Ｔ3）を第４データ格納部５７に格納する（ステップＳ７）。
【００６７】
具体的には、数値ベクトルＴの各成分ｔiを昇順に各次元の係数として用いることで多項式ｍt（Ｔ）＝Σiｔiｘiを生成する。
【００６８】
同様に、数値ベクトルＴ2の各成分ｔ2iを昇順に各次元の係数として用いることで多項式ｍt（Ｔ2）＝Σiｔ2iｘiを生成する。
【００６９】
さらに、数値ベクトルＴ3の各成分ｔ3iを昇順に各次元の係数として用いることで多項式ｍt（Ｔ3）＝Σiｔ3iｘiを生成する。
【００７０】
なお、第２変換部５６は、数値ベクトルＴのビット長ｋも、第４データ格納部５７に格納する。
【００７１】
そして、暗号化部５８は、第４データ格納部５７に格納されている多項式ｍt（Ｔ）、ｍt（Ｔ2）及びｍt（Ｔ3）を、多項式演算可能な準同型暗号方式に従って、公開鍵格納部５９に格納されている照合者の公開鍵ｐｋを用いて暗号化することで暗号化テキストＥ（ｍt（Ｔ））、Ｅ（ｍt（Ｔ2））及びＥ（ｍt（Ｔ3））を生成し、第５データ格納部６０に格納する（ステップＳ９）。なお、暗号化部５８は、数値ベクトルＴのビット長ｋをも第５データ格納部６０に格納する。Ｅ（Ｚ）は、Ｚを多項式演算可能な準同型暗号方式に従って暗号化する処理を表す。
【００７２】
その後、送信部６１は、第５データ格納部６０に格納されている暗号化テキストＥ（ｍt（Ｔ））、Ｅ（ｍt（Ｔ2））及びＥ（ｍt（Ｔ3））と長さｋとを、情報処理装置３へ送信する（ステップＳ１１）。
【００７３】
情報処理装置３の登録部３１は、暗号化テキストＥ（ｍt（Ｔ））、Ｅ（ｍt（Ｔ2））及びＥ（ｍt（Ｔ3））と長さｋとを受信し、データベース３２に登録する（ステップＳ１３）。
【００７４】
以上のような処理を行うことで、暗号化した状態でテキスト等を、クラウドなどに設置された情報処理装置３へ登録することができるようになる。
【００７５】
次に、照合者が、特定のパターンについて照合処理を行わせる際の処理内容を図９を用いて説明する。
【００７６】
照合者装置７の入力部７０は、例えば情報提供者又は他のコンピュータなどから、マッチング対象のテキスト等のデータと照合すべきパターンのデータを取得し、第１データ格納部７１に格納する（図９：ステップＳ２１）。
【００７７】
そして、第１変換部７２は、第１データ格納部７１に格納されているテキストを数値ベクトル化して、数値ベクトルデータＰ＝（ｐ0，ｐ1，．．．，ｐl-1）を第２データ格納部７３に格納する（ステップＳ２３）。
【００７８】
また、乗算部７４は、第２データ格納部７３に格納されている数値ベクトルＰの各成分を二乗することで数値ベクトルＰ2を算出し、三乗することで数値ベクトルＰ3を算出し、第３データ格納部７５に格納する（ステップＳ２５）。
【００７９】
さらに、第２変換部７６は、第２データ格納部７３に格納されている数値ベクトルＰと、第３データ格納部７５に格納されている数値ベクトルＰ2及びＰ3に対して多項式変換を実行し、多項式変換によって生成された多項式ｍp（Ｐ）、ｍp（Ｐ2）及びｍp（Ｐ3）を第４データ格納部７７に格納する（ステップＳ２７）。
【００８０】
具体的には、数値ベクトルＰの各成分ｐiを降順に各次元の係数として用いることで多項式ｍp（Ｐ）＝−Σjｐjｘn-jを生成する。
【００８１】
また、数値ベクトルＰ2の各成分ｐ2iを降順に各次元の係数として用いることで多項式ｍp（Ｐ2）＝−Σjｐ2jｘn-jを生成する。
【００８２】
さらに、数値ベクトルＰ3の各成分ｐ3iを降順に各次元の係数として用いることで多項式ｍp（Ｐ3）＝−Σjｐ3jｘn-jを生成する。
【００８３】
そして、暗号化部７８は、第４データ格納部７７に格納されている多項式ｍp（Ｐ）、ｍp（Ｐ2）及びｍp（Ｐ3）を、多項式演算可能な準同型暗号方式に従って、公開鍵格納部７９に格納されている照合者の公開鍵ｐｋを用いて暗号化することで暗号化パターンＥ（ｍp（Ｐ））、Ｅ（ｍp（Ｐ2））及びＥ（ｍp（Ｐ3））を生成し、第５データ格納部８０に格納する（ステップＳ２９）。
【００８４】
その後、送信部８１は、第５データ格納部８０に格納されている暗号化パターンＥ（ｍp（Ｐ））、Ｅ（ｍp（Ｐ2））及びＥ（ｍp（Ｐ3））を、情報処理装置３へ送信する（ステップＳ３１）。
【００８５】
情報処理装置３の受信部３３は、暗号化パターンＥ（ｍp（Ｐ））、Ｅ（ｍp（Ｐ2））及びＥ（ｍp（Ｐ3））を受信し（ステップＳ３３）、暗号化パターンＥ（ｍp（Ｐ））、Ｅ（ｍp（Ｐ2））及びＥ（ｍp（Ｐ3））を暗号演算処理部３５に出力する。
【００８６】
そして、暗号演算処理部３５は、（８）式に従って、データベース３２に格納されている暗号化テキストＥ（ｍt（Ｔ））、Ｅ（ｍt（Ｔ2））及びＥ（ｍt（Ｔ3））と、暗号化パターンＥ（ｍp（Ｐ））、Ｅ（ｍp（Ｐ2））及びＥ（ｍp（Ｐ3））とを用いて、暗号化パターンマッチングの演算を実行し、演算結果ｄ＝（ｄ０，ｄ１，．．．）を演算結果格納部３６に格納する（ステップＳ３５）。なお、テキストの長さｋについても、演算結果格納部３６に格納する。
【００８７】
そして、送信部３７は、演算結果格納部３６に格納された演算結果ｄ及びテキストの長さｋを、受信部３３へ暗号化パターン等を送信してきた照合者装置７へ送信する（ステップＳ３７）。
【００８８】
照合者装置７の受信部８２は、情報処理装置３から暗号化パターンマッチングの演算結果ｄ及びテキストの長さｋを受信し、第６データ格納部８３に格納する（ステップＳ３９）。そして、復号化部８４は、秘密鍵格納部８５に格納されている秘密鍵ｓｋを用いて、多項式演算可能な準同型暗号方式に従って、演算結果ｄを復号化することで、復号結果ベクトルｍ＝［ｍ0，ｍ1，．．．，ｍn-1］を生成し、第７データ格納部８６に格納する（ステップＳ４１）。第７データ格納部８６には、テキストの長さｋの値も格納される。
【００８９】
判定部８７は、第７データ格納部８６に格納された復号結果ベクトルにおいて、０からｋ−ｌ（長さｌは第２データ格納部７３から取得）までの成分値において０となる位置を特定することで、マッチング対象テキストにおいてパターンと一致する部分が存在するか否かを判定する（ステップＳ４３）。
【００９０】
ベクトルｍ＝［２，０，２，２，２，０，２，７］且つｋ−ｌ＝８−３＝５であれば、左から順番に［２，０，２，２，２，０］において０となる位置「１」及び「５」が存在しているので、マッチング対象テキストにおいてパターンと一致する部分が存在することが分かる。判定部８７は、判定結果を第８データ格納部８８に格納する。出力部８９は、照合者などの要求に応じて、出力装置（表示装置、印刷装置、他のコンピュータ）などに対して判定結果を出力する。
【００９１】
以上のような処理を実行することで、照合すべきパターンについても暗号化したままで、マッチング対象テキストと一致するか否かを判断するための暗号化パターンマッチングの演算結果を得ることができる。そして、照合者装置７において、照合者しか保持していない秘密鍵で復号すれば、簡単な処理にて、マッチング対象テキストとの一致の有無及びパターンが一致する位置を特定できるようになる。
【００９２】
さらに、ワイルドカードが、テキストやパターンに含まれていても同じ処理にて対処できるようになっている。すなわち、秘匿パターンマッチングの汎用性が高くなっている。
【００９３】
なお、上で述べた実施の形態における演算は基本形を示しただけであり、様々な変形が可能である。
【００９４】
上で述べた例では、多項式化において、テキストについては昇順、パターンについては降順というルールで、成分を各次数の係数として用いるようになっていたが、逆に、テキストについては降順、パターンについては昇順といったルールを採用しても良い。さらに、テキストについては正の係数、パターンについては負の係数を採用するルールであったが、テキストについて負の係数、パターンについては正の係数を採用するようにしても良い。
【００９５】
さらに、上で述べた例では、ワイルドカードについては「０」となるような数値ベクトル化を行っていたが、他の文字に対応する数値と重ならないようにすれば、どのような数値をワイルドカードに割り当てるようにしても良い。
【００９６】
すなわち、例えばワイルドカードにｚという値を割り当てるようにした場合、図３右側の式は、以下のように書き換えられる。
【００９７】
【数１】
2015212756.tif 000003
【００９８】
このような式を展開して、対応する多項式演算を規定すれば、暗号化パターンマッチングの演算が規定される。この場合でも、Ｔ、Ｔ2、Ｔ3、Ｐ、Ｐ2及びＰ3をベースにした演算ということは変わらない。
【００９９】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、各装置の機能ブロック図は一例であって、プログラムモジュール構成とは一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、ステップの順番を入れ替えたり、複数ステップを並列実行するようにしても良い。
【０１００】
また、各装置については１台のコンピュータではなく、複数台のコンピュータにて実装される場合もある。また、照合者装置７と提供者装置５とが一体となっている場合もある。
【０１０１】
なお、上で述べた情報処理装置３、提供者装置５及び照合者装置７は、コンピュータ装置であって、図１０に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１０２】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１０３】
本実施の形態の第１の態様に係るマッチング方法は、（Ａ）第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、（Ｂ）第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、（Ｃ）第１の数値ベクトルを多項式変換した第１の多項式と、第２の数値ベクトルを多項式変換した第２の多項式と、第３の数値ベクトルを多項式変換した第３の多項式とを生成し、（Ｄ）第１の多項式と第２の多項式と第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化し、（Ｅ）第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第４の多項式と、第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第５の多項式と、第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第６の多項式とを格納する第２のデータ格納部に格納された第４の多項式と第５の多項式と第６の多項式と、暗号化された第１の多項式と第２の多項式と第３の多項式とを用いて所定の演算を暗号化したまま実行し、（Ｆ）所定の演算の演算結果を復号化する処理を含む。
【０１０４】
このような処理を行うことで、第１のテキストが第２のテキストの一部と一致するか否かを秘匿したまま判断することができるようになる。この際、数値ベクトルの二乗及び三乗をも用意するのは、ワイルドカードが含まれるような場合に対処するためであり、秘匿パターンマッチングの汎用性が高くなっている。
【０１０５】
すなわち、上で述べた所定の演算が、平文において、（ｅ１）第１のテキストが第２のテキストの一部と一致する場合、（ｅ２）いずれの文字とも一致することを表す特殊文字を含む第１のテキストが第２のテキストの一部と一致する場合、及び（ｅ３）第１のテキストが、特殊文字を含む、第２のテキストの一部と一致する場合に、距離が０となる演算であれば好ましい。
【０１０６】
また、上で述べたマッチング方法は、（Ｇ）復号化された演算結果に含まれるベクトルにおいて、０となる成分を特定する処理をさらに含むようにしても良い。このようにすれば、第２のテキストにおいて第１のテキストがどの位置で一致するかをも判断できるようになる。
【０１０７】
さらに、第４乃至第６の多項式を生成する際に行われる多項式変換が、第１乃至第３の多項式を生成する際に行われる多項式変換とは異なる多項式変換であることもある。
【０１０８】
本実施の形態の第２の態様に係る秘匿処理方法は、（Ａ）第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、（Ｂ）第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、（Ｃ）第１の数値ベクトルを多項式変換した第１の多項式と、第２の数値ベクトルを多項式変換した第２の多項式と、第３の数値ベクトルを多項式変換した第３の多項式とを生成し、（Ｄ）第１の多項式と第２の多項式と第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化する処理を含む。
【０１０９】
テキストを登録する場合も、パターンで検索する場合も、このような処理を実行する。
【０１１０】
また、本実施の形態の第３の態様に係る秘匿処理方法は、（Ａ）第１のテキストを数値ベクトル化することで生成された第１の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第１の多項式と、第１の数値ベクトルの各成分を二乗した第２の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第２の多項式と、第１の数値ベクトルの各成分を三乗した第３の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第３の多項式とを受信し、（Ｂ）第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第４の多項式と、第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第５の多項式と、第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第６の多項式とを格納するデータ格納部に格納された第４の多項式と第５の多項式と第６の多項式と、第１の多項式と第２の多項式と第３の多項式とを用いて所定の演算を暗号化したまま実行し、（Ｃ）所定の演算の演算結果を返信する処理を含む。
【０１１１】
例えば、クラウドなどに設けられるコンピュータにより実行される。
【０１１２】
なお、上で述べたような処理をコンピュータ又はプロセッサに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０１１３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１１４】
（付記１）
第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、
前記第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、前記第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、
前記第１の数値ベクトルを多項式変換した第１の多項式と、前記第２の数値ベクトルを多項式変換した第２の多項式と、前記第３の数値ベクトルを多項式変換した第３の多項式とを生成し、
前記第１の多項式と前記第２の多項式と前記第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化し、
第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第４の多項式と、前記第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第５の多項式と、前記第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第６の多項式とを格納する第２のデータ格納部に格納された前記第４の多項式と前記第５の多項式と前記第６の多項式と、暗号化された前記第１の多項式と前記第２の多項式と前記第３の多項式とを用いて所定の演算を暗号化したまま実行し、
前記所定の演算の演算結果を復号化する
処理を含み、複数のコンピュータを含むシステムが実行するマッチング方法。
【０１１５】
（付記２）
前記所定の演算が、
平文において、前記第１のテキストが前記第２のテキストの一部と一致する場合、いずれの文字とも一致することを表す特殊文字を含む前記第１のテキストが前記第２のテキストの一部と一致する場合、及び前記第１のテキストが、前記特殊文字を含む、前記第２のテキストの一部と一致する場合に、距離が０となる演算である
付記１記載のマッチング方法。
【０１１６】
（付記３）
復号化された前記演算結果に含まれるベクトルにおいて、０となる成分を特定する処理
をさらに含む付記１又は２記載のマッチング方法。
【０１１７】
（付記４）
前記第４乃至第６の多項式を生成する際に行われる多項式変換が、前記第１乃至第３の多項式を生成する際に行われる多項式変換とは異なる多項式変換である
付記１乃至３のいずれか１つ記載のマッチング方法。
【０１１８】
（付記５）
第１のテキストを格納する第１のデータ格納部にアクセス可能な第１の情報処理装置と、
第２の情報処理装置と、
を有し、
前記第１の情報処理装置が、
第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、
前記第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、前記第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、
前記第１の数値ベクトルを多項式変換した第１の多項式と、前記第２の数値ベクトルを多項式変換した第２の多項式と、前記第３の数値ベクトルを多項式変換した第３の多項式とを生成し、
前記第１の多項式と前記第２の多項式と前記第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化し、
暗号化された前記第１の多項式と前記第２の多項式と前記第３の多項式を、前記第２の情報処理装置に送信し、
前記第２の情報処理装置は、
前記第１の情報処理装置から、暗号化された前記第１の多項式と前記第２の多項式と前記第３の多項式を受信し、
第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第４の多項式と、前記第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第５の多項式と、前記第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第６の多項式とを格納する第２のデータ格納部に格納された前記第４の多項式と前記第５の多項式と前記第６の多項式と、暗号化された前記第１の多項式と前記第２の多項式と前記第３の多項式とを用いて所定の演算を暗号化したまま実行し、
前記所定の距離の演算結果を、前記第１の情報処理装置に送信し、
前記第１の情報処理装置が、
前記第２の情報処理装置から、前記所定の距離の演算結果を受信し、
前記所定の演算の演算結果を復号化する
システム。
【０１１９】
（付記６）
第１のデータ格納部に格納された第１のテキストを数値ベクトル化することで第１の数値ベクトルを生成し、
前記第１の数値ベクトルの各成分を二乗した第２の数値ベクトルと、前記第１の数値ベクトルの各成分を三乗した第３の数値ベクトルとを生成し、
前記第１の数値ベクトルを多項式変換した第１の多項式と、前記第２の数値ベクトルを多項式変換した第２の多項式と、前記第３の数値ベクトルを多項式変換した第３の多項式とを生成し、
前記第１の多項式と前記第２の多項式と前記第３の多項式とを、多項式演算可能な準同型暗号方式によって暗号化する
処理を、コンピュータに実行させるためのプログラム。
【０１２０】
（付記７）
第１のテキストを数値ベクトル化することで生成された第１の数値ベクトルに対して多項式変換且つ準同型暗号方式による暗号化を行って得られる第１の多項式と、前記第１の数値ベクトルの各成分を二乗した第２の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第２の多項式と、前記第１の数値ベクトルの各成分を三乗した第３の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第３の多項式とを受信し、
第２のテキストを数値ベクトル化することで生成された第４の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第４の多項式と、前記第４の数値ベクトルの各成分を二乗した第５の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第５の多項式と、前記第４の数値ベクトルの各成分を三乗した第６の数値ベクトルに対して多項式変換且つ前記準同型暗号方式による暗号化を行って得られる第６の多項式とを格納するデータ格納部に格納された前記第４の多項式と前記第５の多項式と前記第６の多項式と、前記第１の多項式と前記第２の多項式と前記第３の多項式とを用いて所定の演算を暗号化したまま実行し、
前記所定の演算の演算結果を返信する
処理を、コンピュータに実行させるためのプログラム。
【符号の説明】
【０１２１】
３１  登録部
３２  データベース
３３  受信部
３５  暗号演算処理部
３６  演算結果格納部
３７  送信部
５０  入力部
５１  第１データ格納部
５２  第１変換部
５３  第２データ格納部
５４  乗算部
５５  第３データ格納部
５６  第２変換部
５７  第４データ格納部
５８  暗号化部
５９  公開鍵格納部
６０  第５データ格納部
６１  送信部
７０  入力部
７１  第１データ格納部
７２  第１変換部
７３  第２データ格納部
７４  乗算部
７５  第３データ格納部
７６  第２変換部
７７  第４データ格納部
７８  暗号化部
７９  公開鍵格納部
８０  第５データ格納部
８１  送信部
８２  受信部
８３  第６データ格納部
８４  復号化部
８５  秘密鍵格納部
８６  第７データ格納部
８７  判定部
８８  第８データ格納部
８９  出力部
【図１】
2015212756.tif 000004
【図２】
2015212756.tif 000005
【図３】
2015212756.tif 000006
【図４】
2015212756.tif 000007
【図５】
2015212756.tif 000008
【図６】
2015212756.tif 000009
【図７】
2015212756.tif 000010
【図８】
2015212756.tif 000011
【図９】
2015212756.tif 000012
【図１０】
2015212756.tif 000013