Vectorized Secure Evaluation of Decision Forests

paper algorithm

BGV scheme で決定木をvectorize

@inproceedings{malik2021vectorized,
  title={Vectorized secure evaluation of decision forests},
  author={Malik, Raghav and Singhal, Vidush and Gottfried, Benjamin and Kulkarni, Milind},
  booktitle={Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
  pages={1049--1063},
  year={2021}
}

Abstract

通常のニューラルネットワークモデルはベクトル化が簡単

決定森などの複雑なMLモデルはベクトル化しにくいので自動的にベクトル化可能なプリミティブに再構築してコンパイルすることにした

様々な決定森モデルにおいてx10+ faster, スケーラビリティに優れている

1.Introduction

FHEは計算速度が遅いがパッキングでいくらかマシになる

回路がパッキングされた暗号文に対する演算として表現できれば同型演算の総数が減少してスケーリングできる

課題は任意の計算をベクトル化すること

NNの計算はもともとベクトル化されているのでFHEの応用の魅力的な対象になっている

決定木は各枝での比較があるのでFHEの加算乗算primitiveを使って表現するのが難しいしそもそも逐次的

1.1 COPSE: Secure Evaluation of Decision Forests

FHEスキームが提供するprimitiveは非干渉を保証するセマンティクスを持つ命令セットと考えられる

= 測定可能な出力から機密情報が漏れることはない

ので分岐を禁止しなければならない(そうしないとサイドチャネル攻撃みたいなことされる)

COPSEは決定木評価という逐次的なプロセスを効率的なFHEprimitiveにマッピングするためのシステム

2.3.3で紹介するが
Blindfolded Evaluation of Random Forests with Multi-Key Homomorphic Encryption
の多項式ベースな方式と違う

流れとして決定ノードを並列に評価 -> 決定を正規の順序に並べる reshaping -> 木の特定の深さのすべての決定を評価するレベル処理 -> 各深さの結果を最終分類に結合する集約

木の閾値をエンコードしてベクトルに, 分岐形状を行列に, して HELibを用いた C++に変換される.

1.2 Summary of contributions

決定森を効率的なFHE演算に変換するベクトル化コンパイラ

生成されたFHEプログラムの複雑度の解析

回路の深さが小さいか(低オーバーヘッドにつながる)

効率的なパッキングか(並列化の効率)

HElib 1.1.0 現在, MKHE は実装されていない

Multi-Key HEはサーバー, モデル所有者, データ所有者が全て異なること

2. Background

2.1 Decision Forests

決定木は分類モデル, 葉がクラスラベルに対応, false: 左, true: 右として選んでいく
決定森: 複数の決定木を並べたもので各木からクラスラベルを得た後結合する(平均, 多数決, etc)
木の親と子に依存関係があるため並列化できない, それぞれの木の構造が違うので森でまとめることもできない

2.3 Related Work

2.3.1 Securely evaluating decision treees

決定森の代表的なsecurelyな推論方法2つ

oblivious transfer based methods (21: Wu et al.)

OT=紛失通信
additive homomorphismを用いてinteractiveに森の経路を明らかにすること無く評価できる
サーバーは決定結果がわからない

サーバーは木にダミーノードを追加しランダムに枝を並び替える

モデルがサーバーから平文で利用可能である必要がある

モデルを暗号文で提供するのでクライアント・サーバー両方から隠蔽

constructuing polynomial representations of the trees

Blindfolded Evaluation of Random Forests with Multi-Key Homomorphic Encryption
各木をBool多項式で表現して各決定ノードが変数, 各ラベルが多項式の項に対応して各項のANDが経路を符号化

ex.

枝 $d_0$ , true: $L_0$ , false: $L_1$ のとき $i$ th多項式

$$p_i(d_0)=d_0{L}_0^i+(1-d_0)L_1^i$$

$L_j^i$ はラベル $L_j$ の $i$ ビット目

乗算深さは多項式の次数に比例
関連性のない決定ノード間のSIMD並列性を利用する我々の技術とは異なる

2.3.2 Evaluationg vectorized decision forests

決定木の評価をベクトル化するために
(19) では各枝の制御依存性をデータ依存性に変えるために各木を連続したメモリにレイアウトしている
その結果森の各木を1つのSIMDスロットに収める事ができて, 森全体の評価を並列に行える
各stepで次に評価するノードのインデックスをもらってそれにアクセスするのが必要なので
FHE上では効率的に行えない

2.3.3 Vectorized interence

CHET
はNN推論のための効率的なデータレイアウト, 暗号化パラメータを決定する. テンソルのような規則的なデータ構造では性能向上できるが, 決定木などの複雑なデータ構造は扱えない

3. Overview

Maurice: model owner モデルをベクトル化されたものにコンパイラで変換
Diane: data owner 各特徴量を分類して結果を得る
Sally: performs the computation実行

3.3 The Evaluation Algorithm

Step 0: 特徴量

木の特徴量の最大重複度を求める(図1だとyが3つなので3)
その回数だけ特徴量を繰り返す ($[x,x,x,y,y,y]$)
これを暗号文とする

Step1: 比較

ツリー内の全ての閾値を含むベクトルを作成する. 対応がないところはセンチネル値で埋める(

$$[x_{d_1},x_{d_2},S,y_{d_0},y_{d_2},y_{d_4}]=[4,1,S,6,5,2]$$

)
暗号文と比較をする(1ステップで出来る)

$$[x,x,x,y,y,y]<[4,1,S,6,5,2]=[d_1,d_2,S,d_0,d_2,d_4]$$

Step2: 並び替え

$S$ を削除しながら訪れた順で並び替える

Step3: Level Processing

評価の順序が正しいので, それぞれのレベル(葉から数える)で処理を分離できる.
それぞれのレベルで2値のマスクを構築する

4. Vectorizable Evaluation Algorithm

4.1. Preliminaries

4.1.1. Definitions and Important Properties

Decision Forest

$M$ は 木 $T_1,\cdots ,T_N$ を持ち,
$T_i$ は枝 $B_i$ とラベル $L_i$ の集合
構造はベクトルの組 $(x,f,t)$ にエンコードされる.
$x=(x_1,\cdots ,x_n)$: 特徴量の集合
$f$ : 特徴量のインデックス,
$t$ 閾値
ex. $B_7:x_3<100$ なら $f_7=3,t_7=100$
${\kappa }_i$: 特徴量
$x_i$ の重複度
$K={\max }_i{\kappa }_i$ , $b=\sum {\kappa }_i,q=n\ast K$
(ex. $\kappa =[2,3],K=5,q=6$ )

Representing Non-integral Values

閾値を精度 $p$ の固定小数点値で表す. この値は長さ $k$ のビットベクトルで表され,この表現は比較演算を並列で行うのに役立つ
Integer Comparison
Blindfolded Evaluation of Random Forests with Multi-Key Homomorphic Encryption で言われている 等しいビット長の2値を比較する SecCompアルゴリズム

Matrix Representation

行列は一般化対角行列(generalized diagonals)を並べて表される. $m\times n$ 行列 $A$ は

$$d_i=(A_{0,i},A_{1,i+1},\cdots ,A_{n-i+1,0},\cdots ,A_{m,(m+i)(\mathrm{mod}n)})$$

Matrix Multiplication

Algorithms in HElib の方法で
$m\times n$ 行列 $M$ と $n\times 1$ ベクトル $v$ の積を計算.

$m\times n$ 行列 $M$ を $n\times 1$ vector $v$ で表す.
$i$-th diagonal ベクトルは $\mathrm{rot}(v,i)$

mult depth 1 で計算できる.

Classfiication Result

比較結果を bitvector で持つ.

4.2. Algorithmic Primitives

4.2.1 Padded Threshold Vector

特徴量ベクトルと1:1対応するしきい値ベクトルは $p$ bitベクトルのシーケンス.
layout: vec[i]: 各しきい値の i th bit
長さにバラツキが出るのでセンチネル値($S=0$)でpaddingする

4.2.2 Reshuffling Matrix

バイナリ行列 $\mathcal{R}:\{0,1{\}}^{l\times l}$: 判定結果ベクトルと乗算すると正しい順序の判定結果となる行列 = 列と行で1つしかないやつ

4.2.3 Level Matrices

level matrix: $\{0,1{\}}^{?\times ?}$
行,列 1は1つのみ

4.2.4 Level Masks

その枝が含まれるかどうかを表すバイナリ行列のマスク.
trueのパスのとき0, otherwize 1にして各レベルでXORを取るとすべてが1になるように = not は反転するという意味.
各レベルでANDを取ると結果になる.

4.3 Algorithm

今までの流れをアルゴリズムにする.

Algorithm for vectorized inference

SecComp を用いている.

5 Compiler and Runtime

上記のアルゴリズムは自然でないのでこういうアルゴリズムを自動生成するコンパイラについて考える.

Input Representation

決定森をシリアライズしたものを入力として, HElib の BGV scheme 実装(C++)を吐き出す.
8章では可能な暗号化パラメータを一通り調べて良いパラメータを見つけた.

6 Complexity Analysis

決定森のパラメータ:
分岐数 $b$
レベルの総数 $d$
固定小数点精度 $p$
量子化幅 $q$

FHE回路のパラメータは

• FHE primitive演算の数
• FHE回路のmult depth

BFVの#opsと乗算深さ

BFVについてよく知らないので知る

op	# of ops	mult-depth
Add	$4p-2$	$42\log p+1$
AddConst	$p$	$2\log p+1$
Multiply	$p\log p+3p-2$	$2\log p+1$

Two Physical Parties

FHEによる計算は2者間プロトコルなので, Model Owner $M$, Data Owner $D$, Server $S$ の3つの役割を兼任

• $M=D$: “standard computation offloading”
  • leak to $S$: データのshape, 森の深さに関する情報
• $M=S$: clientはデータを暗号化してサーバーに送る
  • leak to $D$: $K$, $b$
• $D=S$: Sでデータを見られるかも
  • $K$, $b$, $q$

Three Parties

$S,M,D$ が別々の時を考える.

single-keyで $M$ と $D$ のどちらにも, $S$ と共謀していないことをしめすのは難しい todo なんで
ので, MultiKey-HEや秘密分散を用いる先行研究がある.
これらは鍵が増えるだけなのでアルゴリズム部分は流用できる

8 Evaluation

8.2 COPSE Performance

逐次処理版(Blindfolded Evaluation of Random Forests with Multi-Key Homomorphic Encryption) の自前実装と比較.
{single, multi} threadsで27のクエリに対して実行時間の中央値を計測したら x5~7 faster

baseline, ours どちらもsingle thread

Multithreading

single thread baseline vs multi threads ours でのCOPSEの速度比

baseline, ours どちらも multi threads

fig6と同じにならないのでCOPSEのスケーリング性能が多少良くない
(packing を多用しているから?)

• forestのdepth増やしても実行時間にはあまり影響しない
• 枝数増やすとreshaping, 処理時間が増加
• 精度を上げると比較時間が増加