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

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

国内特許コード P140010562
整理番号 S2014-0062-N0
掲載日 2014年5月22日
出願番号 特願2013-217903
公開番号 特開2015-079228
出願日 平成25年10月18日(2013.10.18)
公開日 平成27年4月23日(2015.4.23)
発明者
  • 原田 弘毅
  • 佐久間 淳
  • 有村 博紀
  • 笹川 裕人
出願人
  • 国立大学法人 筑波大学
  • 国立大学法人北海道大学
発明の名称 検出装置、検出方法、コンピュータ、及び、プログラム
発明の概要 【課題】非決定性有限オートマトンを直接使用することができなかった。
【解決手段】検出装置は、入力データ列に予め定められた検出対象パターンが含まれるか否かを検出する検出装置であって、前記検出対象パターンの各データ位置に対応して、前記入力データ列において前記検出対象パターンにおける当該データ位置までのパターン部分を検出中か否かを示す検査配列を記憶する検査配列記憶部と、データの種類毎に、前記検出対象パターンの各データ位置が当該種類のデータか否かを示すデータ対応パターンを生成するデータ対応パターン生成部と、次の入力データに対応する前記データ対応パターンに基づいて、前記検査配列を更新する更新部と、前記検出対象パターンの末尾のデータ位置に対応する前記検査配列の要素に基づいて、前記入力データ列中に前記検出対象パターンが含まれたか否かを判定する判定部と、を備える。
【選択図】図1
従来技術、競合技術の概要



近年の個人情報保護の必要性の高まりにより、保護が必要なデータを開示せずに入力データ列中に特定の検出対象パターンが含まれているか否かを検出する秘密パターン照合の重要性が高まっている(非特許文献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 年.

産業上の利用分野



本発明は、検出装置、検出方法、コンピュータ、及び、プログラムに関する。

特許請求の範囲 【請求項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情報処理部としてコンピュータを機能させるプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2013217903thum.jpg
出願権利状態 公開
この特許について質問等ある場合は、電子メールによりご連絡ください。


PAGE TOP

close
close
close
close
close
close
close