@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00201335,
 author = {中川, 佳貴 and 大畑, 幸矢 and 清水, 佳奈 and Yoshiki, Nakagawa and Satsuya, Ohata and Kana, Shimizu},
 book = {コンピュータセキュリティシンポジウム2019論文集},
 month = {Oct},
 note = {秘密分散法に基づき，クエリと文書を互いに秘匿したまま全文検索する手法を提案する．計算には，クエリ保有者，文書保有者，結託の恐れのない二人の委託計算者が参加する．クエリ保有者と文書保有者のそれぞれが事前にクエリと文書のシェアを作って委託計算者に送り，委託計算者は検索結果のみをクエリ保有者に返す．提案手法では，FM-indexと呼ばれる全文索引により文書を検索しやすい構造に変換する．これにより，委託計算で必要となる計算量，通信量，通信ラウンド数の全てが文書の長さに依存せず，クエリの長さのみに比例する．提案手法を実装し，文書とクエリの長さがそれぞれ1000万と100のゲノム配列検索を行ったところ，委託計算者の計算時間は1CPUの利用でわずか0.30秒，ラウンド数は202，通信量は7.13KBであった．文書保有者の事前計算は文書長とクエリ長の積に線形だが，並列化により効率的に計算できるため，実装上の工夫をせずとも10CPUの利用で15分以内に留まる．提案手法は文字列検索の他に，オートマトンによるパターンマッチや木構造の走査等にも応用でき，多様なデータ検索の高速化に貢献することが期待される．, 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.},
 pages = {289--296},
 publisher = {情報処理学会},
 title = {秘密分散に基づく秘匿全文検索},
 volume = {2019},
 year = {2019}
}