TOP > 国内特許検索 > 検出装置、検出方法、コンピュータ、及び、プログラム > 明細書

明細書 :検出装置、検出方法、コンピュータ、及び、プログラム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2015-079228 (P2015-079228A)
公開日 平成27年4月23日(2015.4.23)
発明の名称または考案の名称 検出装置、検出方法、コンピュータ、及び、プログラム
国際特許分類 G09C   1/00        (2006.01)
H04L   9/08        (2006.01)
FI G09C 1/00 660D
H04L 9/00 601F
請求項の数または発明の数 19
出願形態 OL
全頁数 26
出願番号 特願2013-217903 (P2013-217903)
出願日 平成25年10月18日(2013.10.18)
発明者または考案者 【氏名】原田 弘毅
【氏名】佐久間 淳
【氏名】有村 博紀
【氏名】笹川 裕人
出願人 【識別番号】504171134
【氏名又は名称】国立大学法人 筑波大学
【識別番号】504173471
【氏名又は名称】国立大学法人北海道大学
個別代理人の代理人 【識別番号】110000877、【氏名又は名称】龍華国際特許業務法人
審査請求 未請求
テーマコード 5J104
Fターム 5J104AA16
5J104EA08
5J104EA19
5J104JA21
要約 【課題】非決定性有限オートマトンを直接使用することができなかった。
【解決手段】検出装置は、入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置であって、前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、を備える。
【選択図】図1
特許請求の範囲 【請求項1】
入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置であって、
前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、
データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、
次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、
前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、
を備える検出装置。
【請求項2】
前記更新部は、前記検査配列の各データ位置に対応する要素の値と、次の入力データに対応する前記データ対応パターンにおける次のデータ位置に対応する要素の値とに基づいて、前記検査配列の次のデータ位置に対応する要素の値を算出する請求項1に記載の検出装置。
【請求項3】
前記検査配列記憶部は、前記検出対象パターンの各データ位置に対応して、当該データ位置までのパターン部分を検出中である場合に0となる要素を有する前記検査配列を記憶し、
前記データ対応パターン生成部は、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータである場合に0となる要素を有する前記データ対応パターンを生成し、
前記更新部は、前記検査配列の各データ位置に対応する要素の値、および、次の入力データに対応するデータ対応パターンにおける次のデータ位置に対応する要素の値が共に0であることに応じて、前記検査配列の次のデータ位置に対応する要素を0とする請求項2に記載の検出装置。
【請求項4】
前記更新部は、前記検査配列の各データ位置に対応する要素の値と、次の入力データに対応するデータ対応パターンにおける次のデータ位置に対応する要素の値とを加算して、前記検査配列の次のデータ位置に対応する要素の値とする請求項3に記載の検出装置。
【請求項5】
予め定められたデータ位置における値を複数回繰り返すことを許容する前記検出対象パターンについて、前記更新部は、前記検査配列の各データ位置に対応する要素の値と、前記検査配列の次のデータ位置に対応する要素の値と、次の入力データに対応するデータ対応パターンにおける次のデータ位置に対応する要素の値とに基づいて、前記検査配列の次のデータ位置に対応する要素の値を算出する請求項2から4のいずれか一項に記載の検出装置。
【請求項6】
前記検査配列記憶部および前記更新部を有し、前記入力データ列を管理する第1情報処理部と、
前記データ対応パターン生成部を有し、前記検出対象パターンを管理する第2情報処理部と、
を備え、
前記データ対応パターン生成部は、データの種類毎のデータ対応パターンを暗号化した暗号化データ対応パターンを前記第2情報処理部へと送信し、
前記検査配列記憶部は、前記検査配列を暗号化した暗号化検査配列を記憶し、
前記更新部は、次の入力データに対応する前記暗号化データ対応パターンに基づいて、前記暗号化検査配列を更新し、
前記判定部は、暗号化された前記検出対象パターンの末尾のデータ位置に対応する前記暗号化検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する
請求項1から5のいずれか一項に記載の検出装置。
【請求項7】
前記データ対応パターン生成部は、前記第2情報処理部の公開鍵である第2公開鍵を用いて加法準同型性暗号により前記データ対応パターンを暗号化し、
前記更新部は、前記第2公開鍵を用いて加法準同型性暗号により前記検査配列を暗号化して、前記暗号化検査配列の各データ位置に対応する要素の値、および、次の入力データに対応する前記暗号化データ対応パターンにおける次のデータ位置に対応する要素の値の、加法準同型性暗号における加法に基づき暗号化された前記検査配列を更新する
請求項6に記載の検出装置。
【請求項8】
前記第2情報処理部は、前記判定部を更に有し、
前記第1情報処理部は、前記検出対象パターンの末尾のデータ位置に対応する前記暗号化検査配列の要素を第1乱数によりべき乗した値に基づく検査用データを前記第2情報処理部へと送信し、
前記第2情報処理部の前記判定部は、前記検査用データを前記第2情報処理部の秘密鍵である第2秘密鍵により復号化して前記検査配列の要素を乱数によりべき乗した値を求め、当該値が0か否かに基づいて前記入力データ列中に前記検出対象パターンを検出したか否かを判定する請求項7に記載の検出装置。
【請求項9】
前記第1情報処理部は、前記判定部を更に有し、
前記第1情報処理部は、前記検出対象パターンの末尾のデータ位置に対応する前記暗号化検査配列の要素を第1乱数によりべき乗した値に基づく検査用データを前記第2情報処理部へと送信し、
前記第2情報処理部は、前記検査用データを前記第2情報処理部の秘密鍵である第2秘密鍵により復号化したデータに基づく値を前記第1情報処理部の公開鍵である第1公開鍵により暗号化したデータを第2乱数によりべき乗した値を求め、検査用応答データとして前記第1情報処理部へと返信し、
前記第1情報処理部の判定部は、前記検査用応答データを復号化したデータの値が0か否かに基づいて前記入力データ列に前記検出対象パターンを検出したか否かを判定する
請求項7に記載の検出装置。
【請求項10】
前記第1情報処理部は、前記検出対象パターンの末尾のデータ位置に対応する前記暗号化検査配列の要素を前記第1乱数によりべき乗した値と第3乱数を前記第2公開鍵により暗号化した値とを加法準同型性暗号における加法により加えた前記検査用データと、前記第3乱数を前記第1公開鍵により暗号化した乱数交換データとを前記第2情報処理部へと送信し、
前記第2情報処理部は、前記検査用データを前記第2秘密鍵により復号化し前記第1公開鍵により暗号化した値に前記乱数交換データを加えたデータを前記第2乱数によりべき乗して前記検査用応答データとして返信する
請求項9に記載の検出装置。
【請求項11】
前記検査配列記憶部は、前記検出対象パターンの各データ位置に対応して、前記検出対象パターンにおける当該データ位置までのパターン部分を検出中である場合に0となる要素を有する前記検査配列を暗号化した前記暗号化検査配列を記憶し、
前記検出対象パターンは、予め定められたデータ位置における値を複数回繰り返すことを許容するものであり、
前記更新部は、次の入力データに対応する前記暗号化データ対応パターン及び前記暗号化検査配列に基づいて、パターン部分の一致を各データ位置から次のデータ位置へと伝搬させるための暗号化伝搬配列を生成して、前記暗号化伝搬配列に基づく第1配列および前記暗号化検査配列に基づく第2配列を前記第2情報処理部に送信し、
前記第2情報処理部は、前記第1配列および前記第2配列に基づいて、前記予め定められたデータ位置以外のデータ位置においては前記暗号化伝搬配列の対応する要素を前記更新部に取得させ、前記予め定められたデータ位置においては前記暗号化検査配列および前記暗号化伝搬配列の対応する要素の積を前記更新部に取得させるための返信用配列を生成して前記第1情報処理部へと返信する更新補助部を更に備え、
前記更新部は、前記返信用配列に基づいて前記検査配列を更新する
請求項7から10のいずれか一項に記載の検出装置。
【請求項12】
前記第1情報処理部の前記更新部は、
前記暗号化伝搬配列の各データおよび第4乱数を前記第2公開鍵により暗号化した値同士を加法準同型性暗号の加法により加えた各要素を有する前記第1配列と、
前記暗号化検査配列の各データおよび第5乱数を前記第2公開鍵により暗号化した値同士を加法準同型性暗号の加法により加えた各要素を有する前記第2配列と、
前記暗号化検査配列の各データを前記第4乱数によりべき乗した値と、前記第4乱数および前記第5乱数の積を前記第2公開鍵により暗号化した値と、前記暗号化伝搬配列を前記第5乱数および第6乱数の積によりべき乗した値と、第7乱数を前記第2公開鍵により暗号化した値とを、加法準同型性暗号の加法により加えた各要素を有する第3配列と、
を前記第2情報処理部に送信し、
前記第2情報処理部の前記更新補助部は、
前記予め定められたデータ位置においては、前記第1配列の要素を復号化した値および前記第2配列の要素を復号化した値の積を前記第2公開鍵により暗号化した値を要素とし、前記予め定められたデータ位置以外のデータ位置においては前記第3配列の要素を前記第2公開鍵により暗号化し直した値を要素とする前記返信用配列と、
前記予め定められたデータ位置においては前記第2公開鍵により0を暗号化した値を要素とし、前記予め定められたデータ位置以外においては前記第2公開鍵により1を暗号化した値を要素とする第4配列と、
を前記第1情報処理部に返信する
請求項11に記載の検出装置。
【請求項13】
前記更新部は、前記返信用配列の各要素と、前記暗号化検査配列を前記第4乱数のマイナス値によりべき乗した値と、前記第4乱数および前記第5乱数を前記第2公開鍵により暗号化した値の逆元と、前記暗号化伝搬配列を前記第5乱数のマイナス値によりべき乗した値と、前記第4配列を前記第7乱数のマイナス値によりべき乗した値とを、加法準同型性暗号の加法により加えた各要素により前記検査配列を更新する
請求項12に記載の検出装置。
【請求項14】
当該検出装置は、前記入力データ列として商品の広告履歴データおよび商品の購買履歴データの少なくとも一方を含む履歴データ列を入力し、
前記履歴データ列中に前記検出対象パターンが検出されたことに応じて、広告を発行すべきことを示すトリガ情報を出力する出力部を更に備える
請求項1から13のいずれか一項に記載の検出装置。
【請求項15】
当該検出装置は、前記入力データ列として遺伝子配列を入力し、
前記遺伝子配列中に前記検出対象パターンが検出されたか否かを出力する出力部を更に備える
請求項1から13のいずれか一項に記載の検出装置。
【請求項16】
入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出方法であって、
前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶段階と、
データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成段階と、
次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新段階と、
前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定段階と、
を備える検出方法。
【請求項17】
入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置としてコンピュータを機能させるプログラムであって、
前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、
データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、
次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、
前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、
して機能させるプログラム。
【請求項18】
請求項6から13のいずれか1項に記載の前記第1情報処理部または前記第2情報処理部として機能するコンピュータ。
【請求項19】
請求項6から13のいずれか1項に記載の前記第1情報処理部または前記第2情報処理部としてコンピュータを機能させるプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、検出装置、検出方法、コンピュータ、及び、プログラムに関する。
【背景技術】
【0002】
近年の個人情報保護の必要性の高まりにより、保護が必要なデータを開示せずに入力データ列中に特定の検出対象パターンが含まれているか否かを検出する秘密パターン照合の重要性が高まっている(非特許文献1~3)。
[非特許文献1] J. R. Troncoso-Pastoriza, S. Katzenbeisser, and M. Celik. Privacy preserving error resilient dna searching through oblivious automata. In Proc. Comput. Commun. Security (CCS'07), pages 519{528. ACM, 2007.
[非特許文献2] K. B. Frikken. Practical private dna string searching and matching through efficient oblivious automata evaluation. In Data and Applications Security XXIII, pages 81-94. Springer, 2009.
[非特許文献3] 渡邊裕治,立石孝彰. 通信回数を低減した紛失オートマトン計算. In 暗号と情報セキュリティシンポジウム(SCIS2012) 予稿集, 2012 年.
【発明の概要】
【発明が解決しようとする課題】
【0003】
上記非特許文献1~3においては、いずれも決定性有限オートマトン(DFA:Deterministic Finite Automaton)を想定しており、非決定性有限オートマトン(NFA:Non-deterministic Finite Automaton)を直接使用することができなかった。
【課題を解決するための手段】
【0004】
本発明の第1の態様においては、入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置であって、前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、を備える検出装置を提供する。
【0005】
本発明の第2の態様においては、入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出方法であって、前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶段階と、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成段階と、次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新段階と、前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定段階と、を備える検出方法を提供する。
【0006】
本発明の第3の態様においては、入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置としてコンピュータを機能させるプログラムであって、前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、して機能させるプログラムを提供する。
【0007】
なお、上記の発明の概要は、本発明の特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【0008】
【図1】検出装置10の全体構成図である。
【図2】検出方法の全体の流れを説明するフローチャートである。
【図3】図2に示す検出方法で生成されるデータ対応パターンMTiを説明する図である。
【図4】ステップSs208の状態配列Sの更新処理のフローチャートである。
【図5】更新処理によって更新される状態配列Sを説明する図及び表である。
【図6】ステップSp110及びSs210の照合結果の判定処理のフローチャートである。
【図7】ステップSp110及びSs210の照合結果の判定処理のフローチャートである。
【図8】状態配列の更新処理を変更した検出装置10の全体構成図である。
【図9】セルフループの出力を説明する図である。
【図10】変更した状態配列の更新処理のフローチャートである。
【図11】上述した実施形態の効果を説明する表である。
【図12】本実施形態に係るコンピュータ1900のハードウェア構成の一例を示す。
【発明を実施するための形態】
【0009】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

【0010】
図1は、検出装置10の全体構成図である。検出装置10は、入力データ列T中に予め定められた検出対象パターンPが含まれるか否かを検出する。本実施形態においては、検出装置10は、入力データ列Tを取得・保持・管理する第1情報処理部12(SH:String Holderとも示す。)と、検出対象パターンPを保持・管理する第2情報処理部14(PH:Pattern Holderとも示す。)とを備え、第1情報処理部12および第2情報処理部14の間で入力データ列Tおよび検査対象パターンPを互いに秘匿しつつ、入力データ列T中に検出対象パターンPを検出する秘密パターン照合を実現する。ここで、第1情報処理部12および第2情報処理部14は、一例としてプログラムを実行可能なコンピュータまたは情報処理装置であってよく、有線または無線ネットワークを介して互いに接続される。

【0011】
尚、以下においては、第1情報処理部12および第2情報処理部14間で入力データ列Tおよび検出対象パターンPを秘匿する秘密パターン照合を中心に示すが、第1情報処理部12および第2情報処理部14間で秘密を持たないパターン照合については以下における暗号処理を除くことで実現できる。

【0012】
第1情報処理部12は、複数のデータを含む入力データ列Tの一例として、複数の文字Tiを含む文字列Tを管理する。ここで、第1情報処理部12は、オフラインで文字列T全体を取得してパターン照合に供してもよく、オンラインで文字列Tの各文字を順次取得し、順次パターン照合に供してもよい。以下においては、第1情報処理部12が、文字列Tとして、1文字目からn文字までの文字T1からTnを順次入力していくオンライン処理を中心に示す。第1情報処理部12は、検査配列記憶部20と、更新部22と、第1判定部24とを有する。

【0013】
検査配列記憶部20は、検出対象パターンPの各データ位置(文字位置)に対応して、文字列Tにおいて検出対象パターンPにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列の一例である状態配列を記憶する。ここで本実施形態においては、検出対象パターンPのパターン長をmとする。検査配列記憶部20は、i-1番目の文字Ti-1(1≦i≦n)までの照合を終えた状態において、検出対象パターンPの各データ位置j(0≦j≦m)に対応して、当該データ位置jまでのパターン部分(すなわちP[1]~P[j]の部分)を検出中である場合に検出中を示す値0となる配列要素Si-1[j]を有する状態配列Si-1を記憶する。すなわち、状態配列Si-1の配列要素Si-1[j]は、文字列Tのi-1文字目の文字Ti-1までを読み込んだ状態において、検出対象パターンPのj番目のパターン要素までの一致を検出しているかどうかを表す遷移状態を示す。本実施形態においては、Si-1[j]=0ならばactive(すなわちj番目のパターン要素までの一致を検出していること)、Si-1[j]≠0ならばinactive(すなわちj番目のパターン要素までの一致を検出していないこと)とする。

【0014】
尚、検査配列記憶部20は、秘密パターン照合を実現するために、第2情報処理部14の第2公開鍵pkPHにより状態配列Sを暗号化し、暗号化状態配列SEiとして記憶する。

【0015】
更新部22は、後述する第2情報処理部14のデータ対応パターン生成部32が生成した、文字列Tの次の文字Tに対応するデータ対応パターンMTiに基づいて、状態配列Si-1を更新し、更新された状態配列Sとする。例えば、更新部22は、状態配列Si-1の各データ位置j-1に対応する要素の一例である配列要素Si-1[j-1]の値と、文字列Tの次の文字Tiに対応するデータ対応パターンMTiにおける次のデータ位置jに対応する要素の一例であるパターン要素MTi[j]とに基づいて、状態配列Sの次のデータ位置jに対応する配列要素S[j]を算出する。これにより、更新部22は、i-1番目の文字Ti-1まで入力された状態で検出対象パターンPのj-1番目のパターン部分までの一致を検出しており(Si-1[j-1]が検出中を示す値であり)、かつ、i番目の文字Tに対応するデータ対応パターンMTiのj番目の要素MTi[j]が検査対象パターンPのj番目のパターン要素に文字Tが含まれることを示す場合に、状態配列Si[j]をj番目のパターン部分までの一致を検出していることを示す値に更新することができる。なお、本実施形態に係る更新部22は、上記更新処理を暗号化された状態配列である暗号化状態配列SEiに対して行うが、この処理については後述する。

【0016】
第1判定部24は、第2情報処理部14の第2判定部34と協働して、検出対象パターンPの末尾のデータ位置mに対応する状態配列S[m]に基づいて、文字列T中に検査対象パターンPが含まれているか否かを判定する。本実施形態に係る第1判定部24は、状態配列S[m]を暗号化した暗号化状態配列SEi[m]に基づく判定を行う。尚、mの一例は、検出対象パターンPの文字数である。

【0017】
第2情報処理部14は、検出対象パターンPを管理する。第2情報処理部14は、データ対応パターン生成部32と、第2判定部34を有する。

【0018】
データ対応パターン生成部32は、データの種類の一例である文字Tiの種類毎に、検出対象パターンPの各データ位置jが当該種類のデータか否かを示すデータ対応パターンMTiを生成する。ここで、文字Tiの種類は、文字列Tを構成する文字集合Σの要素であり、例えばa、b等のアルファベット、数字、日本語文字、および、データ要素の値等であってよい。例えば、データ対応パターン生成部32は、データの文字Tiの種類毎に、検出対象パターンPの各データ位置jが当該種類の文字である場合に文字が検出対象パターンPの対応するパターン要素に含まれることを示す値0となる要素MTi[j]を有するデータ対応パターンMTiを生成する。

【0019】
データ対応パターン生成部32は、文字Tiの種類毎のデータ対応パターンMTiを、第2情報処理部14の第2公開鍵pkPHにより暗号化して、暗号化データ対応パターンMETiを第1情報処理部12へと送信する。

【0020】
第2判定部34は、第1情報処理部12の第1判定部24と協働して、検出対象パターンPの末尾のデータ位置mに対応する状態配列Sの配列要素S[m]に基づいて、文字列T中に検出対象パターンPが含まれたか否かを判定する。本実施形態に係る第2判定部34は、状態配列S[m]を暗号化した暗号化状態配列SEi[m]に基づく判定を行う。

【0021】
次に、検査方法について説明する。

【0022】
各検査方法における暗号化は、加法準同型性公開鍵暗号による。加法準同型性公開鍵暗号の一例は、Paillier暗号である。Paillier暗号は、"P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in cryptology EUROCRYPT'99, pages 223-238. Springer, 1999."に記載されている。加法準同型性公開鍵暗号は、同一の公開鍵で暗号化された暗号文同士の積が対応する平文同士の和の暗号文となり、式(1)の関係を満たす。暗号については、Encを用いる。従って、例えば、平文tを暗号化して暗号cにする場合、c=Enc(t)と表記する。白丸○は、暗号同士の積の演算子とする。t1、t2は平文である。r1、r2は、乱数である。r1、r2は、暗号の安全性を保つため暗号化毎に変更することが好ましい。尚、説明の簡略化のため乱数r1、r2は省略して表記する。また、復号については、Decを用いる。従って、例えば、暗号cを復号して平文tにする場合、t=Dec(c)と表記する。
【数1】
JP2015079228A_000003t.gif

【0023】
また、次に示す式(2)により、同一の平文を持つ異なる暗号文を生成する再暗号化もできる。
【数2】
JP2015079228A_000004t.gif

【0024】
図2は、検出方法の全体の流れを説明するフローチャートである。図2に示す検出方法は、第1情報処理部12及び第2情報処理部14がプログラムを読み込むことによって実行される。図2に示す検査方法は、入力された検査対象パターンPからそれを受理する非決定性有限オートマトンを構築して文字列T上でその遷移を模倣することで照合を実行する。本実施形態では、更に、ビット並列パターン照合方法を準同型性暗号上の秘密計算へを実施可能とすべく、配列と加法のみを用いる。尚、Shift-OR法を配列上で実行するアルゴリズムを配列Shift-OR法とする。図3は、図2に示す検出方法で生成されるデータ対応パターンMTiを説明する図である。本実施形態では、文字列Tが第1情報処理部12に入力されている。また、検出対象パターンPが第2情報処理部14に入力されている。実施形態では、検出対象パターンP=ababbとして、文字列T=abababbとする。

【0025】
図2に示す検査方法では、第2情報処理部14において、データ対応パターン生成部32が、第2情報処理部14の公開鍵及び秘密鍵として第2秘密鍵skPH及び第2公開鍵pkPHを生成する(Sp102)。次に、データ対応パターン生成部32は、公開鍵pkPHを第1情報処理部12へと送信する(Sp104)。データ対応パターン生成部32は、式(3)によって、データ対応パターンMTiを生成する。データ対応パターン生成部32は、検出対象パターンP=ababbの文字種"a"についてのデータ対応パターンMaを生成する場合、式(3)に基づいて、検出対象パターンPの1番目及び3番目はaなので、Ma[1]=Ma[3]=0となる。一方、検出対象パターンPの2番目、4番目及び5番目はbなので、Ma[2]=Ma[4]=Ma[5]=1となる。これにより、データ対応パターン生成部32は、式(3)によって、図3に示す検出対象パターンP=ababbのデータ対応パターンMTiを生成する。
【数3】
JP2015079228A_000005t.gif

【0026】
データ対応パターン生成部32は、文字Tiの種類毎にデータ対応パターンMTiの各パターン要素METi[j]を暗号化して、暗号化パターン要素METi[j]を生成する(Sp106)。例えば、データ対応パターン生成部32は、生成した第2公開鍵pkPH及び第2公開鍵skPHのうち、当該第2公開鍵pkPHを用いて加法準同型性暗号によりデータ対応パターンMTiを暗号化してもよい。データ対応パターン生成部32は、暗号化パターン要素METi[j]を含む暗号化データ対応パターンMETiを第1情報処理部12へと送信する(Sp108)。

【0027】
第1情報処理部12では、検査配列記憶部20が、第2情報処理部14から送信された公開鍵pkPH、及び、暗号化されたデータ対応パターンMTiを受信する(Ss202、Ss204)。

【0028】
第1情報処理部12では、更新部22は、式(4)によって、状態配列Sの初期値Sが暗号化された暗号化状態配列SE0を生成して、検査配列記憶部20に記憶させる(Ss206)。
【数4】
JP2015079228A_000006t.gif

【0029】
次に、更新部22は、後述する暗号化状態配列SEiの更新処理によって、状態配列Sが暗号化された暗号化状態配列SEiの各配列要素SEi[j]を生成して、順次、暗号化状態配列SEiを更新する(Ss208)。第1判定部24は、後述する照合結果の判定処理を実行する(Ss210)。この後、更新部22及び第1判定部24は、それぞれステップSs208及びSs210をそれぞれn回繰り返す。尚、nの一例は、文字列Tの文字数である。

【0030】
第2情報処理部14では、第2判定部34が、第1判定部24の照合結果の判定処理と連動して、後述する照合結果の判定処理(Sp110)をn回繰り返す。尚、第2判定部34が、検査対象パターンPが文字列Tを含むか否かを判定する場合、照合結果ΓPHをn回出力して、当該判定を実行する。

【0031】
図4は、ステップSs208の状態配列Sの更新処理のフローチャートである。更新処理のフローチャートに先立って、第1情報処理部12に文字列T、暗号化データ対応パターンMETi、暗号化状態配列SEi-1が入力されている。図5は、更新処理によって更新される状態配列Sを説明する図及び表である。図5の上図は、検出対象パターンP=ababbを受け付けた非決定性有限オートマトンによる状態遷移の図である。図5の上図における各丸の中の数字は、データ位置jを示す。図5の下図において、最上位の行は、データ位置jを示す。各行は、文字列Tのi文字目の文字を読み込んだ場合に生成される状態配列Sを示す。状態配列Sの初期値である状態配列Sの各要素は、S[0]=0と、及び、S[j]=1、j∈{1、2、・・・、m}、S[0]=0に初期設定されている。各セルは、配列要素S[j]を示す。配列要素S[j]は、値が0の場合、activeであって、値が0でない場合、inactiveである。尚、本実施形態では、更新された状態配列Sが暗号化された状態配列SEiを生成する。

【0032】
図4に示すように、状態配列SEiの更新処理では、更新部22は、j=0の配列要素S[0]の値として予め定められた0を、第2公開鍵pkPHを用いて加法準同型性暗号により暗号化して、暗号化状態配列SEiの暗号化配列要素SEi[0]を生成する(Ss220)。換言すれば、更新部22は、j=0の配列要素S[0]の値を、iの値に関わらず0とし、文字Tiが入力される度にデータ対応パターンMの先頭からのマッチングを開始させる。

【0033】
次に、更新部22は、暗号化配列要素SEi[j]を更新する(Ss222)。ここで、更新部22は、暗号化されていない状態で示すと、配列要素S[j]を式(5)によって算出する。具体的には、更新部22は、状態配列Si-1の各データ位置j-1に対応する配列要素Si-1[j-1]の値、および、文字列Tの次の文字Tiに対応するデータ対応パターンMTiにおける次のデータ位置jに対応するパターン要素MTi[j]の値が共に0であることに応じて、状態配列Sの次のデータ位置jに対応する配列要素S[j]を0とする。例えば、更新部22は、状態配列Si-1の各データ位置j-1に対応する配列要素Si-1[j-1]の値と、文字列Tの次の文字Tiに対応するデータ対応パターンMTiにおける次のデータ位置jに対応するパターン要素MTi[j]の値とを加算して、状態配列Sの次のデータ位置jに対応する配列要素S[j]とする。

【0034】
例えば、i=6、j=1の配列要素S[1]の値は、配列要素S[0]の値が0であって、図3に示すようにMT6[1]=Mb[1]の値が1なので、それぞれを足して1となる。i=7、j=5の配列要素S[5]の値は、配列要素S[4]の値が0であって、MT6[5]=Mb[5]の値が0なので、それぞれを足して0となる。
【数5】
JP2015079228A_000007t.gif

【0035】
本実施形態において、更新部22は、パターン要素MTi[j]ではなく、暗号化された暗号化パターン要素METi[j]を第2情報処理部14から受信している。従って、更新部22は、次の文字列Tに対応する暗号化データ対応パターンMETiに基づいて、加法準同型性の性質より自明の下記の式(6)によって、暗号化状態配列SEiの配列要素SEi[j]を算出して更新する。具体的には、更新部22は、1つ前の暗号化状態配列SEi-1の各データ位置j-1に対応する配列要素SEi-1[j-1]の値、および、次の文字列Tに対応する暗号化データ対応パターンMETiにおける次のデータ位置jに対応する暗号化パターン要素METi[j]の値との積、即ち、加法準同型性暗号における加法に基づき暗号化状態配列SEiを算出して更新する。
【数6】
JP2015079228A_000008t.gif

【0036】
更新部22は、ステップSs222を、m回繰り返すまで続ける。ここでいうmは、検出対象パターンP=ababbに含まれる文字数であって、本実施形態では5個である。上述した図2に示すように、更新部22は、更新処理のステップSs208をn回繰り返す。これにより、更新部22は、図5に示すn個の状態配列Sが暗号化された暗号化状態配列SEiを生成することになる。これにより、状態配列の更新処理が終了する。

【0037】
図6は、ステップSp110及びSs210の照合結果の判定処理のフローチャートである。照合結果の判定処理のフローチャートに先立って、第1情報処理部12に第2公開鍵pkPHが入力され、第2情報処理部14には第2秘密鍵skPHが入力されている。尚、図6に示す照合結果の判定処理は、第2情報処理部14が照合結果を判定する場合である。尚、データ対応パターンMTiが暗号化されている場合、第2判定部34は、暗号化検出対象パターンPの末尾のデータ位置mに対応する暗号化状態配列SEiの暗号化配列要素SEi[m]に基づいて、文字列T中に検出対象パターンPが含まれたか否かを判定する。以下、判定処理について詳細に説明する。

【0038】
図6に示すように、照合結果の判定処理では、第1情報処理部12の第1判定部24が第1乱数V[i]及び第3乱数W[i]を生成する(Ss230)。尚、乱数は、i毎、即ち、文字列Tの文字毎に生成される。第1判定部24が、式(7)によって、第1乱数V[i]によりべき乗した暗号化配列要素SEi[m]が、公開鍵pkPHによって暗号化された第3乱数W[i]によって、ランダム化された検査用データZ[i]を算出する(Ss232)。尚、暗号化配列要素SEi[m]は、検出対象パターンPの末尾のデータ位置mに対応する暗号化状態配列Sの要素である。
【数7】
JP2015079228A_000009t.gif

【0039】
第1判定部24は、検査用データZ[i]を第2情報処理部14へと送信する(Ss234)。

【0040】
第2情報処理部14では、第2判定部34が、検査用データZ[i]を受信する(Sp120)。第2判定部34は、受信した検査用データZ[i]を公開鍵pkPHによって復号して、検査用データZ[i]を生成する(Sp122)。

【0041】
第1判定部24は、第3乱数W[i]を第2情報処理部14へと送信する。(Ss236)。

【0042】
第2判定部34は、第3乱数W[i]を受信する(Sp124)。第2判定部34は、検査用データZ[i]を第2情報処理部14の秘密鍵である第2秘密鍵skPHにより復号化する。第2判定部34は、式(8)に基づいて、復号した検査用データZ[i]と、受信した第3乱数W[i]との和によって、末尾のデータ位置mの状態配列Sの配列要素S[m]を第1乱数V[i]によりべき乗した値である照合結果ΓPH[i]として算出する(Sp126)。尚、第3乱数W[i]は省略してもよい。
【数8】
JP2015079228A_000010t.gif

【0043】
第2判定部34は、照合結果ΓPH[i]の値が0か否かに基づいて文字列T中に検出対象パターンPを検出したか否かを判定する。(Sp128)。換言すれば、第2判定部34は、暗号化検出対象パターンPの末尾のデータ位置mに対応する暗号化状態配列SEiの暗号化配列要素SEi[m]に基づいて、文字列T中に検出対象パターンPが含まれたか否かを判定する。具体的には、第2判定部34は、照合結果ΓPH[i]が"0"の場合、検出対象パターンPが文字列Tに含まれていると判定して、それ以外は検出対象パターンPが文字列Tに含まれていないと判定する。例えば、第2判定部34は、図5の例では、i=7において、Si[5]=0(active)を検出して、文字列Tの7文字目が、合致した検査対象パターンPの末尾であると判定する。これにより、照合結果の判定処理が終了する。尚、第1判定部24を有する第1情報処理部12は、何らの結果も得ることはない。換言すれば、第2情報処理部14は、第1情報処理部12に何らの情報を与えることなく、検出対象パターンPが文字列Tに含まれているか否かを検出できる。

【0044】
図7は、ステップSp110及びSs210の照合結果の判定処理のフローチャートである。照合結果の判定処理のフローチャートに先立って、第1情報処理部12に第2公開鍵pkPHが入力され、第2情報処理部14には第2秘密鍵skPHが入力されている。尚、図7に示す照合結果の判定処理は、第1情報処理部12の第1判定部24が照合結果を判定する場合である。図7の処理において、点線で囲まれたステップが図6と異なる。図6と同じ処理には、同じステップ番号を付与して説明を省略する。

【0045】
本実施形態においては、第2判定部34は、検出対象パターンPの末尾のデータ位置mに対応する状態配列Sの配列要素S[m]に基づいて、文字列T中に検出対象パターンPが含まれたか否かを判定する。

【0046】
第1情報処理部12の第1判定部24は、検出対象パターンP]の末尾のデータ位置mに対応する暗号化状態配列SEiの配列要素SEi[m]を第1乱数V[i]によりべき乗した値に基づく検査用データZ[i]を第2情報処理部14へと送信する。

【0047】
例えば、第1判定部24は、検出対象パターンPの末尾のデータ位置mに対応する暗号化状態配列SEiの配列要素SEi[m]を第1乱数V[i]によりべき乗した値と第3乱数W[i]を第2公開鍵pkPHにより暗号化した値とを加法準同型性暗号における加法により加えた検査用データZ[i]と、第3乱数W[i]を第1公開鍵pkSHにより暗号化した乱数交換データRDとを第2情報処理部14へと送信してもよい。

【0048】
第1判定部24は、後述する第2情報処理部14から返信された検査用応答データZ' [i]を復号化したデータの値が0か否かに基づいて文字列Tに検出対象パターンPを検出したか否かを判定する。

【0049】
第2情報処理部14の第2判定部34は、検査用データZ[i]を第2情報処理部14の秘密鍵である第2秘密鍵skPHにより復号化したデータに基づく値を第1情報処理部12の公開鍵である第1公開鍵pkSHにより暗号化したデータを第2乱数W' [i]によりべき乗した値を求め、検査用応答データZ'[i]として第1情報処理部12へと返信する。例えば、第1判定部24は、検査用データZ[i]を第2秘密鍵skPHにより復号化し第1公開鍵pkSHにより暗号化した値に乱数交換データRDを加えたデータを第2乱数W' [i]によりべき乗して検査用応答データZ'[i]として返信する。

【0050】
図7に示すように、第1情報処理部12では、第1判定部24が、秘密鍵skSH、及び、公開鍵pkSHを生成する(Ss240)。次に、第1判定部24は、式(9)によって、第3乱数W[i]を暗号化した第3乱数W[i]を算出する(Ss242)。
【数9】
JP2015079228A_000011t.gif

【0051】
第1判定部24は、第1公開鍵pkSH、及び、第3乱数W[i]を第2情報処理部14へ送信する(Ss244)。

【0052】
第2情報処理部14では、第2判定部34が、第1公開鍵pkSH、及び、第3乱数W[i]を受信する(Sp130)。第2判定部34は、新たに第2乱数W'[i]を生成する(Sp132)。第2判定部34は、式(10)によって、照合結果を秘密にしつつシェアするために暗号化検査用データZ[i]をランダム化した検査用応答データZ' [i]を算出する(Sp134)。
【数10】
JP2015079228A_000012t.gif

【0053】
第2判定部34は、第2乱数W'[i]及び検査用応答データZ' [i]を第1情報処理部12へと送信する(Sp136)。

【0054】
第1判定部24は、第2判定部34が送信した第2乱数W'[i]及び検査用応答データZ' [i]を受信する(Ss246)。次に、第1判定部24は、式(11)によって、照合結果ΓSH[i]を算出する(Ss248)。
【数11】
JP2015079228A_000013t.gif

【0055】
第1判定部24は、照合結果ΓSH[i]の結果で、パターンPが文字列Tに含まれているか否かを判定する。具体的には、第1判定部24は、照合結果ΓSH[i]が"0"の場合、検出対象パターンPが文字列Tに含まれていると判定して、それ以外は検出対象パターンPが文字列Tに含まれていないと判定する。これにより、照合結果の判定処理が終了する。尚、第2判定部34を有する第2情報処理部14は、何らの結果も得ることはない。換言すれば、第1情報処理部12は、第2情報処理部14に何らの情報を与えることなく、検出対象パターンPが文字列Tに含まれているか否かを検出できる。

【0056】
次に、上述した実施形態の状態配列の更新処理を変更した形態について説明する。図8は、状態配列の更新処理を変更した検出装置10の全体構成図である。図9は、セルフループの出力を説明する図である。本実施形態は、セルフループの遷移処理を含む場合に有効である。

【0057】
図8に示す検査配列記憶部20は、検出対象パターンPの各データ位置に対応して、検出対象パターンPにおける当該データ位置までのパターン部分を検出中である場合に0となる要素を有する状態配列Sを暗号化した暗号化状態配列SEiを記憶する。

【0058】
予め定められたデータ位置Lにおける値を複数回繰り返すセルフループを許容する検出対象パターンPの場合、例えば、更新部22は、状態配列Si-1の各データ位置jに対応する配列要素Si-1[j]と、状態配列Si-1の次のデータ位置jに対応する配列要素S[j]と、次の文字列Tに対応するデータ対応パターンMTiにおける次のデータ位置j+1に対応するパターン要素MTi[j]とに基づいて、状態配列Sの次のデータ位置j+1に対応する配列要素S[j+1]を算出する。尚、セルフループとは、現在の状態への遷移である。セルフループによって、パターンから生成される非決定性有限オートマトンでは無現ギャップが実現される。

【0059】
セルフループによる遷移は、状態配列Sを図9に示す関係に基づいて、更新する。尚、図9の出力は、上述の式(5)により文字の遷移を実行した後、次の式(12)の処理によって得られる。尚、式(12)は、ループのある状態については、文字の遷移以前の状態との積をとることでセルフループ遷移を実現して、ループのない状態に関しては何も実行しない。
【数12】
JP2015079228A_000014t.gif

【0060】
更新部22は、式(5)及び文字列Tの次に入力される文字に対応する暗号化データ対応パターンMEi-1及び暗号化状態配列SEi-1に基づいて、パターン部分の一致を各データ位置j-1から次のデータ位置jへと伝搬させるための暗号化伝搬配列SEiを生成して、暗号化伝搬配列SEiに基づく第1配列S'Eiの要素S'Ei[j]および暗号化状態配列SEi-1に基づく第2配列S' Ei-1の要素S' Ei-1[j]を第2情報処理部14に送信する。

【0061】
第2情報処理部14は、更新補助部36を更に備える。更新補助部36は、第1配列S' Eiおよび第2配列S' Ei-1に基づいて、予め定められたセルフループのデータ位置L以外のデータ位置においては暗号化伝搬配列SEiの対応する要素SEi[j]を更新部22に取得させ、予め定められたデータ位置Lにおいては暗号化状態配列SEi-1および暗号化伝搬配列SEiの対応する要素SEi[j]の積を更新部22に取得させるための返信用配列SEiを生成して第1情報処理部12へと返信する。

【0062】
更新部22は、返信用配列SEiに基づいて状態配列SEiを更新する。

【0063】
第1情報処理部の更新部22は、暗号化伝搬配列SEiの各データおよび第4乱数R[j]を第2公開鍵pkPHにより暗号化した値同士を加法準同型性暗号の加法により加えた各要素S' Ei[j]を有する第1配列S' Eiと、暗号化状態配列SEiの各データおよび第5乱数Q[j]を第2公開鍵pkPHにより暗号化した値同士を加法準同型性暗号の加法により加えた各要素S' Ei-1[j]を有する第2配列S' Ei-1と、暗号化状態配列SEiの各データを第4乱数R[j]によりべき乗した値と、第4乱数R[j]および第5乱数Q[j]の積を第2公開鍵pkPHにより暗号化した値と、暗号化伝搬配列SEiを第5乱数Q[j]および第6乱数K[j]の積によりべき乗した値と、第7乱数U[j]を第2公開鍵pkPHにより暗号化した値とを、加法準同型性暗号の加法により加えた各要素を有する第3配列ΔEiとを第2情報処理部14に送信する。

【0064】
第2情報処理部の更新補助部36は、予め定められたデータ位置Lにおいては、第1配列S' Eiの要素S' Ei[j]を復号化した値および第2配列S' Ei-1の要素S' Ei-1[j]を復号化した値の積を第2公開鍵pkPHにより暗号化した値を要素とし、予め定められたデータ位置L以外のデータ位置においては第3配列ΔEiの要素ΔEi[j]を第2公開鍵pkPHにより暗号化し直した値を要素とする返信用配列SEiと、予め定められたデータ位置Lにおいては第2公開鍵pkPHにより0を暗号化した値の要素を暗号化零EEi[j]とし、予め定められたデータ位置L以外においては第2公開鍵pkPHにより1を暗号化した値を要素EEi[j]とする第4配列EEiとを第1情報処理部12に返信する。

【0065】
更新部22は、返信用配列SEiの各要素SEi[j]と、暗号化状態配列SEiを第4乱数R[j]のマイナス値によりべき乗した値と、第4乱数R[j]および第5乱数Q[j]を第2公開鍵pkPHにより暗号化した値の逆元と、暗号化伝搬配列SEiを第5乱数Q[j]のマイナス値によりべき乗した値と、第4配列EEiを第7乱数U[j]のマイナス値によりべき乗した値とを、加法準同型性暗号の加法により加えた各要素により状態配列Sを更新する。

【0066】
図10は、変更した状態配列の更新処理のフローチャートである。状態配列の更新処理の当該フローチャートでは、第1情報処理部12に文字列T、暗号化データ対応パターンMETi、暗号化状態配列Si-1、及び、第2公開鍵pkPHが入力されている。第2情報処理部14には、セルフループのデータ位置L、第2秘密鍵skPH、第2公開鍵pkPHが入力されている。本フローチャートは、無限長ギャップを含むパターンへの拡張を行った拡張配列Shift-OR法である。尚、図10に示す処理は、図4に示す処理の後に継続して実行される。また、Lはセルフループを行う予め定められた処理の番号であって、L⊂{1、・・・・、m}である。

【0067】
図4に示すステップSs220からSs222が実行される。次に、更新部22は、乱数K[j]、R[j]、Q[j]、U[j]を生成する(Ss260)。尚、更新部22は、一例として、1からNまでの整数から乱数K[j]、R[j]、Q[j]、U[j]を抽出する。更新部22は、式(13)及び生成した乱数から、第1配列S'Eiの要素S'Ei[j]、第2配列S'Ei-1の要素S'Ei-1[j]、及び、第3配列ΔEiの要素ΔEi[j]を算出する(Ss262)。
【数13】
JP2015079228A_000015t.gif

【0068】
更新部22は、算出した第1配列S'Ei、第2配列S'Ei-1、及び、第3配列ΔEiを第2情報処理部14へと送信する(Ss264)。更新部22は、ステップSs260からS264をm回繰り返す。

【0069】
第2情報処理部14では、更新補助部36が、第1情報処理部12から送信された第1配列S'Ei、第2配列S'Ei、及び、第3配列ΔEiを受信する(Sp140)。

【0070】
次に、更新補助部36は、今回の処理対象のデータ位置jがセルフループのデータ位置Lに含まれるか否かを判断する(Sp144)。更新補助部36は、データ位置jがデータ位置Lに含まれると判断すると(Sp144:Yes)、式(14)によって、返信用配列SEiの各要素SEi[j]を算出するとともに、式(15)によって、暗号化零EEi[j]を算出する(Sp146)。
【数14】
JP2015079228A_000016t.gif
【数15】
JP2015079228A_000017t.gif

【0071】
一方、更新補助部36は、データ位置jがデータ位置Lに含まれないと判断すると(Sp144:No)、式(16)によって、返信用配列SEiの各要素SEi[j]を算出するとともに、式(17)によって、暗号化零EEi[j]を算出する(Sp148)。ここで、本実施形態では、第7乱数Uを用いることによって、S[j]=0の場合であっても、式(16)の関係においても、式(18)に示すように第7乱数U[j]が残るので、S[j]=0であることが第2情報処理部14にはわからない。
【数16】
JP2015079228A_000018t.gif
【数17】
JP2015079228A_000019t.gif
【数18】
JP2015079228A_000020t.gif

【0072】
更新補助部36は、算出した返信用配列SEiの各要素SEi[j]、及び、暗号化零EEi[j]を第1情報処理部12へ送信する(Sp150)。更新補助部36は、ステップSp144からSp150をm回繰り返す。

【0073】
更新部22は、第2情報処理部14から送信された返信用配列SEi[j]、及び、暗号化零EEi[j]を受信する(Ss266)。更新部22は、式(18)によって、状態配列SEiの各要素SEi[j]を算出して更新する(Ss268)。
【数19】
JP2015079228A_000021t.gif

【0074】
図11は、上述した実施形態の効果を説明する表である。表中のSPM1の列は、図4に示す実施形態の性能を示す。表中のSPM2の列は、図10に示す実施形態の性能を示す。

【0075】
上述の非特許文献は、事前処理では文字列の文字数nに依存するとともに、更新処理では文字列が含みうる文字種(いわゆるアルファベット等)の数Σに依存する。これにより、各非特許文献は、それぞれの処理における計算量が増加する。一方、図11に示すように、本実施形態は、事前処理では文字列の文字数nに依存せず、更新処理では文字列が含みうる文字種の数Σに依存しないので、それぞれの処理における計算量を低減できる。特に、本実施形態は、文字数n及び文字種の数Σが大きくなる日本語テキスト及び購買ログ等において、より計算量の増加を各非特許文献に比べて、抑制することができる。

【0076】
次に、上述した実施形態を具体的に適用する例を示す。

【0077】
例えば、上述した実施形態は、購買履歴の検出に適用してもよい。この場合、検出装置10は、入力データ列として商品の広告履歴データおよび商品の購買履歴データの少なくとも一方を含む履歴データ列が入力される。検出装置10は、出力部を更に備えることが好ましい。出力部は、履歴データ列中に検出対象パターンPが検出されたことに応じて、広告を発行すべきことを示すトリガ情報を出力する。

【0078】
また、例えば、上述した実施形態は、遺伝子配列の検出に適用してもよい。この場合、検出装置10は、入力データ列として遺伝子配列が入力される。検出装置10は、出力部を更に備えることが好ましい。出力部は、遺伝子配列中に検出対象パターンが検出されたか否かを出力する。

【0079】
上述したように、検出装置10は、非決定性有限オートマトンを直接評価することにより、非決定性有限オートマトンを決定性有限オートマトンに変換した場合に、文字列Tの文字数及び検出対象パターンの文字数の増加に伴う状態数の増加を低減して、通信量及び計算量を低減できる。更に、検出装置10は、文字列T及び検査対象パターンPを、加法準同型性を満たす暗号により暗号化することによって、文字列T及び検査対象パターンPを相手に知られることなく、上述の効果を実現できる。

【0080】
上述した実施形態は、一例であって、各実施形態における構成、値、データの種類等は適宜変更してよい。また、各実施形態を適切に組み合わせてもよい。

【0081】
例えば、検出対象パターンPのh番目の要素P[h]が複数の文字を含む集合である文字種Aである場合、各文字σ∈Σに対して、マスク配列Mσ[h]を式(19)によって生成してもよい。
【数20】
JP2015079228A_000022t.gif

【0082】
上述の実施形態では、入力データ列を文字列としたが、入力データ列は文字列以外のデータ列であってもよい。

【0083】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

【0084】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。

【0085】
図12は、本実施形態に係るコンピュータ1900のハードウェア構成の一例を示す。本実施形態に係るコンピュータ1900は、第1情報処理部12及び第2情報処理部14の一例である。コンピュータ1900は、ホスト・コントローラ2082により相互に接続されるCPU2000、RAM2020、グラフィック・コントローラ2075、及び表示部2080を有するCPU周辺部と、入出力コントローラ2084によりホスト・コントローラ2082に接続される通信インターフェイス2030、及び、ハードディスクドライブ2040を有する入出力部と、入出力コントローラ2084に接続されるROM2010、メモリドライブ2050及び入出力チップ2070を有するレガシー入出力部とを備える。

【0086】
ホスト・コントローラ2082は、RAM2020と、高い転送レートでRAM2020をアクセスするCPU2000及びグラフィック・コントローラ2075とを接続する。CPU2000は、ROM2010及びRAM2020に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ2075は、CPU2000等がRAM2020内に設けたフレーム・バッファ上に生成する画像データを取得し、表示部2080上に表示させる。これに代えて、グラフィック・コントローラ2075は、CPU2000等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。

【0087】
入出力コントローラ2084は、ホスト・コントローラ2082と、比較的高速な入出力装置である通信インターフェイス2030、ハードディスクドライブ2040を接続する。通信インターフェイス2030は、ネットワークを介して他の装置と通信する。ハードディスクドライブ2040は、コンピュータ1900内のCPU2000が使用する表示プログラム等のプログラム及びデータを格納する。

【0088】
また、入出力コントローラ2084には、ROM2010と、メモリドライブ2050、及び入出力チップ2070の比較的低速な入出力装置とが接続される。ROM2010は、コンピュータ1900が起動時に実行するブート・プログラム、及び/又は、コンピュータ1900のハードウェアに依存するプログラム等を格納する。メモリドライブ2050は、メモリカード2090から例えば表示プログラム等のプログラム又はデータを読み取り、RAM2020を介してハードディスクドライブ2040に提供する。入出力チップ2070は、メモリドライブ2050を入出力コントローラ2084へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ2084へと接続する。

【0089】
RAM2020を介してハードディスクドライブ2040に提供されるプログラムは、メモリカード2090、又はICカード等の記録媒体に格納されて利用者によって提供される。表示プログラム等のプログラムは、記録媒体から読み出され、RAM2020を介してコンピュータ1900内のハードディスクドライブ2040にインストールされ、CPU2000において実行される。

【0090】
コンピュータ1900にインストールされ、コンピュータ1900を検出装置10として機能させるプログラムは、検査配列記憶モジュール、データ対応パターン生成モジュール、更新モジュール、及び、判定モジュールとを備える。これらのプログラム又はモジュールは、CPU2000等に働きかけて、コンピュータ1900を、検査配列記憶モジュール、データ対応パターン生成モジュール、更新モジュール、及び、判定モジュールとしてそれぞれ機能させる。

【0091】
これらのプログラムに記述された情報処理は、コンピュータ1900に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である検査配列記憶モジュール、データ対応パターン生成モジュール、更新モジュール、及び、判定モジュールとして機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ1900の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有の検出装置10が構築される。

【0092】
一例として、コンピュータ1900と外部の装置等との間で通信を行う場合には、CPU2000は、RAM2020上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス2030に対して通信処理を指示する。通信インターフェイス2030は、CPU2000の制御を受けて、RAM2020、ハードディスクドライブ2040、又はメモリカード2090等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス2030は、DMA(ダイレクト・メモリ・アクセス)方式により記憶装置との間で送受信データを転送してもよく、これに代えて、CPU2000が転送元の記憶装置又は通信インターフェイス2030からデータを読み出し、転送先の通信インターフェイス2030又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。

【0093】
また、CPU2000は、ハードディスクドライブ2040、メモリドライブ2050(メモリカード2090)等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をDMA転送等によりRAM2020へと読み込ませ、RAM2020上のデータに対して各種の処理を行う。そして、CPU2000は、処理を終えたデータを、DMA転送等により外部記憶装置へと書き戻す。このような処理において、RAM2020は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはRAM2020および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、CPU2000は、RAM2020の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはRAM2020の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもRAM2020、メモリ、及び/又は記憶装置に含まれるものとする。

【0094】
また、CPU2000は、RAM2020から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、RAM2020へと書き戻す。例えば、CPU2000は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合(又は不成立であった場合)に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。また、CPU2000は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。

【0095】
以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、メモリカード2090の他に、DVD又はCD等の光学記録媒体、MO等の光磁気記録媒体、テープ媒体、ICカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はRAM等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ1900に提供してもよい。
【符号の説明】
【0096】
10 検出装置
12 第1情報処理部
14 第2情報処理部
20 検査配列記憶部
22 更新部
24 第1判定部
32 データ対応パターン生成部
34 第2判定部
36 更新補助部
1900 コンピュータ
2000 CPU
2010 ROM
2020 RAM
2030 通信インターフェイス
2040 ハードディスクドライブ
2050 メモリドライブ
2070 入出力チップ
2075 グラフィック・コントローラ
2080 表示部
2082 ホスト・コントローラ
2084 入出力コントローラ
2090 メモリカード
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11