Secure Frequent Pattern Mining by Fully Homomorphic Encryption with Ciphertext Packing
【一言まとめ】
データを秘匿したまま頻出パターンマイニングを行ううえで完全準同型暗号を用い、その時間・空間計算量を削減した。
【著者】
Hiroki Imabayashi, Yu Ishimaki, Akira Umayabara, Hiroki Sato, Hayato Yamana
【所属機関】
WASEDA Univ.
【URL】
https://link.springer.com/chapter/10.1007/978-3-319-47072-6_12
【Abstract】
We propose an efficient and secure frequent pattern mining protocol with fully homomorphic encryption (FHE). Nowadays, secure outsourcing of mining tasks to the cloud with FHE is gaining attentions. However, FHE execution leads to significant time and space complexities. P3CC, the first proposed secure protocol with FHE for frequent pattern mining, has these particular problems. It generates ciphertexts for each component in item-transaction data matrix, and executes numerous operations over the encrypted components. To address this issue, we propose efficient frequent pattern mining with ciphertext packing. By adopting the packing method, our scheme will require fewer ciphertexts and associated operations than P3CC, thus reducing both encryption and calculation times. We have also optimized its implementation by reusing previously produced results so as not to repeat calculations. 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.
【Abstract翻訳】
完全準同型暗号（FHE）を用いた、計算量が効率化された安全頻出パターンマイニングプロトコルを提案する。近年、FHEを用いて、マイニングタスクを安全にクラウドへアウトソーシングすることが注目を集めている。しかし、FHEによる実行には膨大な時間・空間計算量がかかる。FHEを用いた安全頻出パターンマイニングプロトコルとして初めて提案されたP3CCにはこの問題がある。アイテム・トランザクション行列の各要素に対して暗号文を生成し、暗号化されたコンポーネントに対して数多くの操作を実行しなければならない。この問題に対処するため、われわれは、暗号文パキング手法を適用した、効率的な頻出パターンマイニングプロトコルを提案する。このパッキング手法を用いることにより、より少ない暗号文の生成で抑えられ、また暗号化や計算の回数を削減できる。我々はさらに、同様の計算を繰り返さないように、事前に生成された結果を再利用するように最適化した。実験評価では、10,000トランザクションのデータセットについて、P3CCの430倍の高速化、94.7%のメモリ削減を達成した。
【どんなもの？】
・FHEを用いた安全な頻出パターンマイニングでは、世界一高速である。
【先行研究と比べてどこがすごい？】
・10,000トランザクションのデータセットについて、P3CCの430倍の高速化、94.7%のメモリ削減を達成
【技術や手法のキモはどこ？】
・暗号文パッキング手法
頻出パターンマイニングのデータセットにうまく適用することで生成される暗号文を削減（メモリ削減）および高速化を達成。
・暗号文キャッシング手法
頻出パターンマイニングのサポート値計算の特徴にうまく適用することで高速化を可能にした。
【どうやって有効だと検証した？】
・様々なデータセットやパラメータを用いて、一つ一つの手法を検討している。
【議論はある？】
・暗号文上での比較を可能にすると、完全にサーバに計算を委託することができる。
【次に読むべき論文は？】
【手法詳細】
【関連リンク】
