ノンインタラクティブな秘密計算上でのセット極大マッチの列挙

• Item type: Symposium(1)
• 公開日: 2019-10-14
• タイトル: ノンインタラクティブな秘密計算上でのセット極大マッチの列挙
• タイトル / 言語: en
• タイトル: Finding All the Set-Maximal Matches over Non-Interactive Secure Computation
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: set-maximal match，non-interactive secure computation，TFHE，fully homomorphic encryption
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 理化学研究所革新知能統合研究センター／筑波大学情報学群情報科学類
• 著者所属: 理化学研究所革新知能統合研究センター
• 著者所属: 理化学研究所革新知能統合研究センター
• 著者所属: 理化学研究所革新知能統合研究センター／筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Advanced Intelligence Project / University of Tsukuba
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Advanced Intelligence Project
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Advanced Intelligence Project
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Advanced Intelligence Project / University of Tsukuba
• 著者名: 小池, 悠生; 西本, 崇晃; 田部井, 靖生; 佐久間, 淳
• 著者名(英): Yuki, Koike; Takaaki, Nishimoto; Yasuo, Tabei; Jun, Sakuma
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文ではセット極大マッチ問題と呼ばれる文字列の問題をノンインタラクティブな秘密計算上で効率良く解決するアルゴリズムを提案する．セット極大マッチ問題とは，パターン文字列と文字列集合が与えられた時，集合中の文字列とパターン文字列が共通の部分文字列を持つ区間の内，極大なものを全て列挙する問題である．この問題は遺伝学分野において関心を持たれている．提案手法が先行研究に比べ，理論計算量・実測値双方において漸近的に高速である事も示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an efficient non-interactive privacy-preserving algorithm for the set-maximal match problem. The set-maximal match problem is, given a pattern string and a set of strings, to enumerate all of the maximal segments in which the pattern and some string in the set have the same substring. The motivation of this problem arises from genetics. We show our method runs asymptotically faster than the existing methods in both of theoretical time complexity and experiments.
• 書誌レコードID / 識別子タイプ: NCID
• 書誌レコードID / 関連識別子: ISSN 1882-0840
• 書誌情報: コンピュータセキュリティシンポジウム2019論文集; 巻 2019, p. 365-372, 発行日 2019-10-14
• 出版者 / 言語: ja
• 出版者: 情報処理学会