Quartz 5

完全準同型暗号による安全頻出パターンマイニングの省メモリ高速化

Properties2
tags
aliases

3 min read

完全準同型暗号による安全頻出パターンマイニングの省メモリ高速化

早稲田の修士論文
https://core.ac.uk/download/pdf/144465803.pdf

1. はじめに

課題

  • サポート値の計算には加算と乗算が必要
    • 時間, 空間計算量が多い
  • サポート値計算終了まで待機時間が長い

2. 関連研究

  • 数値比較はクライアント側で行う
    • 出来るが膨大な計算が必要となるため

3. FHEでの頻出パターンマイニングプロトコル

3.2 プロトコルに用いる要素技術

  • プロトコルの説明, 2-party

3.2.1 Aprioriアルゴリズム

  • 頻出パターンマイニング: ただの内積の事だった
  • アルゴリズム

3.2.2 多項式CRTパッキング

  • CRT packingでSIMDされている, 詳細あり watchlater

3.2.3 CRT packing cipherでのtotal sum

3.3 P3CC方式

  • プロトコルの手続き

4. プロトコルの省メモリ高速化

4.1 サポート値計算量の削減

4.1.1 暗号文パッキング

  • P3CC方式は行列の要素数分暗号文を生成する

4.1.2 暗号文キャッシング

  • CSE の考え方に近い?

4.1.3 暗号文プルーニング

  • 使わない変数はdropする

5. 評価

  • マルチスレッドで同期とっていたのでストリームで非同期にした
    • x1.3 faster
  • RAM 445GB -> 33.8GB
  • exp: 先行手法に提案手法を加えていくとRAMがどのくらい削減されるか
  • 平分での計算結果の一致を以て正確性を保証している

6. おわりに

  • ただ並列化しただけなのでスケジューリングとかで高速化の余地

  • Aprioriアルゴリズムより省メモリのを対象にしたい

  • bib 32 items

  • データセット, 実験結果は付属DVD

Graph View

Backlinks