秘密分散に基づく秘匿全文検索

• Item type: Symposium(1)
• 公開日: 2019-10-14
• タイトル: 秘密分散に基づく秘匿全文検索
• タイトル / 言語: en
• タイトル: Privacy-Preserving Full-Text Search Based on Secret Sharing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 全文検索，秘密分散，FM-index，マルチパーティ計算，プライバシ保護
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 早稲田大学
• 著者所属: 産業技術総合研究所
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 中川, 佳貴; 大畑, 幸矢; 清水, 佳奈
• 著者名(英): Yoshiki, Nakagawa; Satsuya, Ohata; Kana, Shimizu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 秘密分散法に基づき，クエリと文書を互いに秘匿したまま全文検索する手法を提案する．計算には，クエリ保有者，文書保有者，結託の恐れのない二人の委託計算者が参加する．クエリ保有者と文書保有者のそれぞれが事前にクエリと文書のシェアを作って委託計算者に送り，委託計算者は検索結果のみをクエリ保有者に返す．提案手法では，FM-indexと呼ばれる全文索引により文書を検索しやすい構造に変換する．これにより，委託計算で必要となる計算量，通信量，通信ラウンド数の全てが文書の長さに依存せず，クエリの長さのみに比例する．提案手法を実装し，文書とクエリの長さがそれぞれ1000万と100のゲノム配列検索を行ったところ，委託計算者の計算時間は1CPUの利用でわずか0.30秒，ラウンド数は202，通信量は7.13KBであった．文書保有者の事前計算は文書長とクエリ長の積に線形だが，並列化により効率的に計算できるため，実装上の工夫をせずとも10CPUの利用で15分以内に留まる．提案手法は文字列検索の他に，オートマトンによるパターンマッチや木構造の走査等にも応用でき，多様なデータ検索の高速化に貢献することが期待される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a secure full-text search protocol based on secret sharing. We consider a case in which a database holder and a querier send shares of the database and the query to two non-colluding computing nodes and they return the result to the querier. By using an efficient full-text index called FM-index, all the time, communication and round complexities of the protocol become linear to the length of query and do not depend on the length of database. In the experiment using a genomic sequence of length 10 million and a query sequence of length 100, the CPU time, communication round, and data transfer size for a single query were only 0.3s, 202 and 7.13KB. The building block of the protocol can also be applied to other applications such as a deterministic finite automaton matching and a tree traversal, and is expected to contribute to various real word problems.
• 書誌レコードID / 識別子タイプ: NCID
• 書誌レコードID / 関連識別子: ISSN 1882-0840
• 書誌情報: コンピュータセキュリティシンポジウム2019論文集; 巻 2019, p. 289-296, 発行日 2019-10-14
• 出版者 / 言語: ja
• 出版者: 情報処理学会