Quartz 5

Rule based HE Compiler

Properties1
tagslab, term, tips

13 min read

Thesis , Juliaで HE Compiler
2022-04-01 - 2022-02-01

repo: wakame-tech/FHESimu.jl
poster: poster

大学院の研究これにしようかな

  • 「任意の関数DAGに変換してくれる君」を作る
    • relinearize まずはナイーブに
    • BootStrapはノイズをへらすのでbit(TFHE)のbootstrapつかうことでif文の誤差を減らせないか？
    • 各種非線形関数(max, min, sin, log) とかの誤差評価をする
  • 多項式近似で
    • HEAANのbootstrapはノイズへらない regain level
  • CGGI scheme
    • 関数の中にあらかじめ0と1を暗号化したものをおいておく
    • 謎の暗号文(0 or 1)が来た時にソレに対応したものが出力される
  • CKKS方式の多項式をTFHEの形式ｂに変換するのは難しそう

予定

  • DAGを使って何をしたいのか
  • 計算を効率化(の何を?)
  • bootstraping problemとかだと整数計画問題とかあまりわからないものが関わってきそう
  • 準同型演算をopcodeとみてコンパイラの最適化手法を使いたい
  • ループ 最適化: ループの変化しない変数を外に出す
  • 行列積: rotation等を駆使して効率的に(batching) を使う
  • どうやって暗号文を0 or 1にするか
  • 非線形関数を多項式近似して評価
  • CKKS BootStrappingの理解

アイデア: 1/0 + eps を RotRしてRotLしたらノイズ減ったりしないかな(scale: 1bit) で演算する
→ Rotate演算はVectorを回転させる処理
→ しかも左シフトしか出来ない

LookUpTable

名前の通りテーブルを引くので誤差とかはなく非線形でも問題ないが
取りうる値の数だけ結果を用意しておく必要がある
取りうる値減らせば実用的かも

    • FHEの暗号文のブリッジを作った(やばい)

  • やっぱり計算グラフ最適化したい

    • 乗算を減らすために依存していない
    • 乗算ノード同士をパッキング
      • 内積・行列積もローテーションと加乗算を駆使して書き換える
        • ベクトル中の並び替えが自由にできない

    • CKKS scheme における非線形関数への対処の記述あり

やること

  • EVA: グループ機能 ✅ 2024-07-17

  • EVA: ciphertextの依存見つける ✅ 2024-07-17

  • nGraph-he読む ✅ 2024-07-17

  • ゼミスライド: DL特有の関数のノード ✅ 2024-07-17

  • FHE-BOOK書きながら論文に書く理論決める

  • 非線形演算を含む計算回路の誤差と時間の評価したい

  • 非線形関数が入力されたら多項式近似して誤差を測る

    • → 新規性: 任意の非線形関数に対応できる

実験手法

  1. abs, ReLU, heviside などの非線形関数に対して
  2. 多項式近似の手法をいくつか比較
  3. 実際にコードにして処理時間や誤差などを検証

論文に必要な理論

  • 準同型暗号
    • CKKS
      • 演算とか、暗号化などの理論
      • オーダーの話
    • 多項式近似

先行研究

  • CKKS型準同型暗号における非線形関数を含む計算グラフの評価手法と誤差の分析
    NN触れる

  • パラメタ変えてゲート数みる

    • 処理時間もはかる
    • どうやって削減するのか(新規性)

  • mul, add, rescaling, modswitch のノイズ増加, 演算コストをシミュレートする

    • 非線形演算は適切なパラメータnで近似
    • いい感じの計算グラフを出力できる

  • 耐量子暗号

  • 新しい体系

2021-08-01

2021-09-03

Fully Homomorphically Encrypted Deep Lerning as a Service

2021-09-07

2021-09-08

2021-09-13

  • キーワード: DAG-optimization

  • キーワード: SIMD最適化
  • なぜこんなに関連研究がないのだろう?
  • 仮説: あまりDAGでの最適化に期待できないから？
    • CHETとかのFHE Graph Compilerは割と成果出ている
  • 仮説: cryptographerにはarithmetic-based FHEがadd, mult, rotしか出来ないSIMDマシンに見えていないから？

  • “SIMDを考慮した効率的なDAG Term Rewritingをしたい” は欲張りすぎ

  • KVSPみたいな話かな
  • う～ん今日も進捗ゼロ!!w
  • ゼミまで残り:23日, 研究できる日: 14日, リサーチ:実験:スライド=2:10:2

2021-09-22

  • Pattern Rewriting : Generic DAG-to-DAG Rewriting
    • SAT符号化の話、問題をどうやって落とし込むか
  • Z3による汎用大域的最適化 - Qiita
    • 充足判定を繰り返すことで最適化問題を解ける
    • LLVM loop optimization passの話
    • BootStrapping problemの話
    • 各レイヤーで最適化をしたらかなり早くなったよ
    • 抽象高レイヤーの最適化周りを調査しないといけないが低レイヤーの話も気になるというか全然詳しくない
  • fhe operation scheduring の話もされていた

2021-09-29

  • 今の論文呼んだら(12h + まとめ 6h + 実装 12h)
  • 次の論文これ読め(6h + まとめ 6h + 実装 6h)

Auto-vectorization of interleaved data for SIMD

  • その後、 loop indexing optimization を検討しろ(12h)
  • スライド作ろう(おさらい, 概観 20 + ConeRewriting 30 + SIMD 20 + Indexing Redution 30枚目標), まとめているなら簡単に出来る(6h)
  • あと丸7日もあるので出来るはず

2021-10-04
研究やること

  • MatMul のFHE IRを作れ (3h)
    • FHE IRのベンチマーク作りたい
    • algo から DAG(フォーマットは?) を吐き出せるツール

Incremental column-wise verification of arithmetic circuits using computer algebra - PubMed

  • Verify circuit の分野? で arithmetic circuitの話が, わからん

Boolean: XOR, ANDは可換だが,

Vec<Complex> Rotは可換じゃないのでこういう最適化(ConeRewriting) 難しそう
→ いや可換

2021-10-12

サービス｜EAGLYS株式会社

EAGLYS(イーグリス)

準同型暗号ベースの秘密計算はどこへ向かっているのか（社会の取り組み編）｜EAGLYS株式会社 https://www.eaglys.co.jp/developers-blog/product/mihara_01

個人情報保護法ニュースNo.1：リクナビ事件と個人情報保護法の改正 | 弁護士法人　三宅法律事務所
https://miyake.gr.jp/topics/201912/個人情報保護法ニュースno1：リクナビ事件と個人情報保護法の改正

2021-11-10

‘comb’ Dialect

タスク

  • 数値実験(8h) ✅ 2024-07-17
  • 改善(4h) ✅ 2024-07-17
  • ポスター作成(24h) ✅ 2024-07-17

2021-11-14

  • かなり切羽つまっている

Connected Papers | Find and explore academic papers

CKKSで比較するやるの改善が出ていた

2021-11-26
ゲートレベルで乗算深さを最適化したい

2021-12-20
ポスターフィードバック

Untitled

ごみと言われなくてよかった(本当はごみ)

Graph View

Backlinks