完全準同型暗号による安全頻出パターンマイニング計算量効率化

• Item type: Trans(1)
• 公開日: 2017-03-22
• タイトル: 完全準同型暗号による安全頻出パターンマイニング計算量効率化
• タイトル / 言語: en
• タイトル: Streamline Computation of Secure Frequent Pattern Mining by Fully Homomorphic Encryption
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] 頻出パターンマイニング，秘匿計算，完全準同型暗号，暗号文パッキング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 今林, 広樹; 石巻, 優; 馬屋原, 昂; 佐藤, 宏樹; 山名, 早人
• 著者名(英): Hiroki, Imabayashi; Yu, Ishimaki; Akira, Umayabara; Hiroki, Sato; Hayato, Yamana
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 医薬品や遺伝子などの機密性の高いデータに対する各種処理をクラウドなどの第三者のサーバ上で行う場合，第三者のサーバからの機密情報漏洩が懸念される．解決策として，機密情報そのものではなく匿名化したデータを第三者のサーバに保存し各種処理を行う方法が考えられるが，医療分野など，処理の正確性が求められる分野では匿名化を採用することが困難である．この問題を解決するため，本稿では，完全準同型暗号（FHE: Fully Homomorphic Encryption）を用いてデータを秘匿した状態で各種処理を行うことを考える．そして，各種処理の対象として頻出パターンマイニングを取り上げる．FHEを用いた各種処理を行ううえでの問題は，膨大な時間・空間計算量を要する点である．FHEの頻出パターンマイニング手法への適用例としては，Aprioriアルゴリズムを対象としたLiuらのP3CCがあるが，やはり膨大な時間・空間計算量を要する．これに対して本稿では，1) 暗号文パッキングによる暗号文数の削減，および2) 暗号文キャッシングによるサポート値計算の高速化によって，時間・空間計算量を削減する手法を提案する．実験評価では，10,000トランザクションのデータセットにおいて，P3CCの430倍の高速化と94.7%のメモリ使用量削減を達成した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Private information disclosure from a third-party is concerned as a security risk, while processing highly confidential data such as medicines and genes on the third-party as a cloud server. Although there is a solution that stores and processes the data anonymized from private information on the third-party's server, it is difficult to apply anonymizing techniques to application fields such as a medical field which requires accurate processing. To address this issue, we will perform the processing with concealed data by Fully Homomorphic Encryption (FHE). In addition, we will adopt frequent pattern mining as a processing object. The problem of the processing with FHE is both huge time complexity and space complexity. P3CC by Liu et al. is the first proposed application of FHE for frequent pattern mining, which targets Apriori algorithm and has these particular problems. In this paper, we propose an Apriori based mining method with smaller time and space complexities than P3CC, by adopting two techniques: 1) ciphertext packing that reduces the number of ciphertexts, and 2) ciphertext caching that enables to speed up the support-counting. Our experimental evaluation shows that the proposed scheme runs 430 times faster than P3CC, and uses 94.7% less memory with 10,000 transactions data.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 10, 号 1, p. 1-12, 発行日 2017-03-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会