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

IPSJ

Bibliographic Information

Other Title
  • Secure Pattern Matching Using Homomorphic Encryption for Extended String Patterns

Abstract

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

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.

Journal

Keywords

Details 詳細情報について

  • CRID
    1050292572154330368
  • NII Article ID
    170000080844
  • Web Site
    http://id.nii.ac.jp/1001/00098278/
  • Text Lang
    ja
  • Article Type
    conference paper
  • Data Source
    • IRDB
    • CiNii Articles

Report a problem

Back to top