準同型性暗号を用いた拡張文字列の秘匿パターン照合

• 原田, 弘毅

• 笹川, 裕人

• 有村, 博紀

• 佐久間, 淳

書誌事項

タイトル別名

• Secure Pattern Matching Using Homomorphic Encryption for Extended String Patterns

抄録

本研究では、パターンと文字列の両方が秘密情報であるときに、互いの情報を秘匿したまま、文字列上でパターンの検索を行うプロトコルを提案する。本方式の用途として、個人ゲノムにおける遺伝子検索や、顧客の購買パターン検出などが挙げられる。従来の秘匿有限オートマトン評価では、本稿で扱う拡張文字列パターンのクラスに対して、一般に決定性有限オートマトンの状態数が指数的に爆発する問題がある。提案方式では、非決定性有限オートマトンの模倣に基づくパターン照合手法の一つであるビット並列照合手法に基づき、準同型性暗号を用いた二者間の秘密計算によって、状態数の爆発を回避しつつ、照合を効率良く実行する。

In this paper, we propose a protocol for secure pattern matching between two parties which have a string and a pattern, respectively. This protocol searches the pattern on the string without revealing their information each other. It is applicable to DNA search in personal genomes and detection of purchase patterns of customers. The existing approach with oblivious automata evaluation has a problem of exponential state explosion for the class of extended string patterns in general. To avoid this problem, our method extends bit-parallel pattern matching, which simulates a non-deterministic finite automaton, to secure multi-party computation using homomorphic encryption between two parties.

収録刊行物

• コンピュータセキュリティシンポジウム2013論文集

  コンピュータセキュリティシンポジウム2013論文集 2013 (4), 801-808, 2013-10-14

キーワード

• 秘密計算，プライバシ保護，文字列照合，有限オートマトン，正規表現照合

詳細情報

• CRID: 1050292572154330368
• NII論文ID: 170000080844
• Web Site: http://id.nii.ac.jp/1001/00098278/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles