CHET

CHET: An Optimizing Compiler for Fully-Homomorphic Neural-Network Inferencing

@inproceedings{dathathri2019chet,
  title={CHET: an optimizing compiler for fully-homomorphic neural-network inferencing},
  author={Dathathri, Roshan and Saarikivi, Olli and Chen, Hao and Laine, Kim and Lauter, Kristin and Maleki, Saeed and Musuvathi, Madanlal and Mytkowicz, Todd},
  booktitle={Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation},
  pages={142--156},
  year={2019},
  url={https://www.cs.utexas.edu/~roshan/CHET.pdf}
}

• Faster PCA and Linear Regression through Hypercubes in HElib

Abstract

• FHEのパラメータは低すぎると安全性がなくなり高すぎると演算のコストが高く
  • そこでベクトルの演算してコスト下げる(batching)
• process CNN per image
• 結果
  • base implementation: 18h+
  • hand tuned: 45min-
  • CHET: 5min-

2. Background

詳細な理論は A Survey on Homomorphic Encryption Schemes Theory and Implementation 参照

• current schemes are “leveled” (= SHE)
• 整数の演算ができるFHEに固定小数点として

CKKS scheme

• rescaleの例

  • <3.14> = <314> with scale 100

• rescaling

  • <2000> → <20> with scale 100

• 機械学習を含む様々なアプリケーションはexp, log, tanhのような非線形演算を含む

  • 適切な近似多項式でカバー [23]

• $r$ は $\log Q$ より遥かに小さい

• 次数 $N=2^k$, modulus $Q$ の多項式

• $Q$ 大きいと正しい演算がたくさんできる

• $Q$ 大きいと安全性, CKKSは最小の$N,Q$ でも128bit security

2.4 FHE Vectorization

• CRTを利用したSIMD演算
  • $N/2$ のサイズのSIMD演算ができる
• “rotate”演算: rotate([a_1, ... a_n], i) = [a_i+1, ... a_n, a_1, ... a_i]
  • (要 rotate key)
• 2の累乗のrotation keyを組合せて任意の回転量
• CHETは明示的にrotation keyを与えることで最適化

2.5 Approximation in CKKS

演算のノイズが精度に影響を与えないように十分大きなscaleをもつ必要がある.

2.6 Tensor Programs

機械学習ではネットワークはテンソルの演算で表される

例:

• Convolution: input tensorとfilter tnsor の cross correlation
• Matrix multiplication
• Pooling: 近隣の要素との演算(max-, ave-)
• Element-wise operation: e.g. batch-norm
• Reshaping: flattenとか

我々はこの演算の流れをDAGで表す

3. Overview of CHET

3.1 Motivating Example

• 2x2行列 A, B の行列積を例に
• コンパイラは
  • input: 画像と重みのschema, tensorの回路, 出力の精度
  • output: Encryptor & Decryptor, 最適化されたtensorの回路

• 適切にpaddingをする
• 回転と加算(a + a >> 1)で2つに複製をする
• 行列積に必要な積 $c_{ijk}=a_{ij}\cdot b_{jk}$ を一回の演算で出来ている
• 更に回転と加算をする事により $c_{ij}$ を得る
  • 行列 $C$ のレイアウトは $A,B$ のレイアウトと異なる
    • さらに連続して計算する場合はそれだと困る
• HE上の計算の課題
  • maskや回転等が平文と比べて高価
    • ex. シフト量に対して1つの鍵が必要
  • mask操作で mult depth が増える
  • 多次元のtensorはSIMD幅に収まらないので複数の暗号文に分割しなければならない
  • 暗号化幅によって乗算深さとSIMD幅が決まっている

3.2 Using the Compiler

• scaling factor
  • 大きい: 計算コストが高い
  • 小さい: 予測精度が落ちる
• そこでプロファイルガイド付き最適化
  • 使用するscaleと訓練画像を与えると適切なscaleを決定する
• 各opの出力にはdata layoutの選択肢がある
  • HW layoutとか
• serverとcompilerはsemi-honestを仮定
  • 要求された計算を実効するが, clientやuserのデータを知りたがる
• batchingをsupportするが焦点はlatencyを下げること
  • 残りの部分はbatch size 1とする

3.3 Design of the Compiler

• CHETは2つの中間表現を持つ
  • Homomorphic Tensor Circuit(HTC)
    • 高レベルな中間表現
    • 行列がどのようにベクトルにmappingされるか, 出力のレイアウト
  • Homomorphic Instruction Set Architecture(HISA)
    • 低レベルな中間表現
    • 各opのコストモデルを指定出来る

4. Intermediate Representations

4.1 HISA

• 命令セット
  • 暗号化, 復号化, encode, decode
  • コピー, free
  • 左右巡回シフト, 暗号文-暗号文, 暗号文-平文, スカラー加減乗算と複合代入演算子
  • rescale
    • CKKS shcemeではmodulusは2ベキ, CKKS-RNS schemeでは modulus chain の次のmodulusでなければいけない

4.2 Homomorphic Tensor Circuit

• HTCは抽象的なテンソル演算をHISAにマップする
• 次元, padding, strideを含んだ CipherTensor として扱われる
  • 高性能kernelのlocallityを向上されるためのvector tiling, blockingに似ているが制約が異なる

• 例: $N\times C\times H\times W$ テンソル

  • HW layout: $H\times W$ をpadding=0, stride=1でベクトルにしたのを
  • CHW layout: $C\times HW$
    • この2レイアウトしかないのか

• CipherTensor はstrideの情報も含んでいる

  • ex. $(H,W)=(28,28)\to (30,\ast )$ にすると各行はpadding=2となる

• ex. 画像フィルタのHEアルゴリズムの例

• mulPlain と mulScalar の計算量

  • CKKS-RNSではどちらも $\mathcal{O}(N\cdot r)$
  • CKKSでは mulPlain: $\mathcal{O}(N\cdot \log N\cdot M(Q))$, mulScalar: $\mathcal{O}(N\cdot M(Q))$

5. Compiling a Tensor Circuit

5.1 Analysis and Transformation Framework

色々言っているが単にIRを使っていると言いたいだけ

• input Tensor circuit -> HTC
  • HISAAnalyser
  • データフローグラフはDAG

Each such analysis requires an FHE expert to specify the data-flow equation for each HISA primitive.

???

• CHET compiler 変換pass
  • ct datatype to store the data-flow information along with its initialization
  • data-flow equation for each HISA primitive (HISA-Analyser)
  • a transformer that takes the data-flow analysis results and returns a specification for the HTC
• 解析部と変換部に分かれているから拡張性に優れている

5.2 Encryption Parameters Selection

• $Q$ に対し, 現在知られている攻撃に対するセキュリティを保証する $N$ が決まる

• あらかじめ128bit securityを満たすパラメータセットを列挙しておく

• perfを最大化するには $Q$ の下限を見つけることが必要

• RNS-CKKS schemeでの $Q$ の決定方法

  • modulus chain が存在する, 十分大きな $n$ に対して $Q_1,Q_2,Q_n$ が存在すると仮定して解析する
    • $k$ 番目の ct の消費moduliは1に初期化