Simulating Homomorphic Evaluation of Deep Learning

Simulating Homomorphic Evaluation of Deep Learning Predictions

2020-11-18
paper nn

@inproceedings{boura2019simulating,
  title={Simulating homomorphic evaluation of deep learning predictions},
  author={Boura, Christina and Gama, Nicolas and Georgieva, Mariya and Jetchev, Dimitar},
  booktitle={International Symposium on Cyber Security Cryptography and Machine Learning},
  pages={212--230},
  year={2019},
  organization={Springer},
  url={https://eprint.iacr.org/2019/591.pdf}
}

Abstract

秘密を保護した機械学習が流行っています
TFHEとHEAANで近似的なCNNを動かしたい
はじめに準同型演算(積, 線形結合, rotation, bootstrapping)のあとのノイズの増加を分析した.
機械学習における非線形演算の理論、各スキームで評価する方法
成果: 実際に評価すること無く準同型演算のノイズやaccuracyの影響を予測することができる

Introduction

秘密計算とかMPCとかあるが、準同型暗号は単体で完結するので通信のコストがかからない

準同型暗号には主に3つのスキームがある, B/FV, TFHE, HEAAN

どれもがRLWE問題に基づいている.

B/FVはSIMDな演算ができ, 演算をするごとにノイズが溜まっていき復号をしたときにどれくらい正しさが残るか, Bootstrapはノイズ削減

一方でHEAANは小数の演算ができ、演算によって下位ビットが丸められます

誤差は下位ビットに溜まっていき, 復号でもbootstrapでも直すことができません

同型演算の最大数という概念があり(=Leveled?), multiplication level

レベルを超えると意味をなさなくなる

HEAANのbootstrapはそのレベルを引き上げる事ができる

(実はB/FVやHEAANは正確な演算をすることができるが, 本論文では近似を使う)

実はHEAANとTFHEの併用したハイブリッドなアプローチがある(Chimera)

bootstrapが早いTFHEと行列とかの演算が早い(SIMD)HEAANを併用することができる

Our Contributions

NNの回路をシミュレーションし, パフォーマンスやノイズを分析する

CNNの小さいやつ(LeNet-5)とかでやった

誤差は多くても10%なので4bit precisionでいい?(通常は20-40bit)

とても小さいパラメータで済み, 高速

2. Homomorphic RLWE encryption shcemes and noise propagation

Notation:

$\mathbb{T}=\mathbb{R}/\mathbb{Z}$ mod 1 をトーラス

${\mathbb{Z}}_N[X]=\mathbb{Z}[X]/(X^N+1)$

slotsの概念を紹介するために ${\mathbb{R}}^N$ の同型を紹介

coefficient packing

$\mathbb{R}[X]/(X^N+1)\simeq {\mathbb{R}}^N$

$f=a_0+\cdots +a_{N-1}{X}^{N-1}\mapsto (a_0,\cdots ,a_N)$

slot packing

$\mathbb{R}[X]/(X^N+1)\simeq {\mathbb{C}}^{\frac{N}{2}}$

$f=(f(\zeta ),f({\zeta }^3),\cdots ,f({\zeta }^{N-1}))$

$\zeta =e^{\frac{\pi i}{N}}$は$X^N-1$の原始根

2.1 HEAAN and TFHE through the Chinema framework

precision: $\rho >0$ を持つ

$x,y\in [-1,1]$, $(x+iy)\cdot 2^{\tau }$

x, y は $\rho$ ビットの精度を持つ

mantissa: 仮数

ciphertexts:

TFHE

${\mathbb{R}}_N[X{]}^2\mathrm{mod}1$

HEAAN

${\mathbb{R}}_N[X{]}^2\mathrm{mod}q$

鍵空間:

TFHE, HEAAN

${\mathbb{Z}}_N[X]$ (小さい係数)

位相関数: ${\phi }_s(a,b)=b-s\cdot a$

最後に TFHE, HEAAN にあるmaximal multiplicative depth

0に達してしまったら, bootstrapをしないと続きの計算ができない.

セキュリティパラメータ $\lambda$, 最大レベル $L$, 精度 $\rho$ から最小鍵サイズ $N$ が決まる, 詳細は以下さんsヂョ

以下では, TFHE と HEAAN の暗号化, 復号化について述べる

KeyGen

一様ランダムな鍵 $s\in {\mathbb{Z}}^N[X]$

非線形な演算演算をサポートするために他の様々な鍵が必要になる場合がある.

Evaluation Key, SwitchingKey, BootstrappingKey ここでは説明しない

EncryptAtLevel ${}_\tau, _L (x, s)$

1. 平文 x (in C^N/2), $(|x|\le 2^{\tau })$
2. $2^{\tau +L}$ で割って(1)の同型写像に通すと $\mu <2^{-L}$ が得られる
3. 一様ランダムから $a\in {\mathbb{R}}_N[X]\mathrm{mod}1$
4. 小さなガウシアンエラー $e$ を選び
5. $(a,s\cdot a+\mu$+ e) を返す

DecrypyApproxAtLevel ${}_{\tau }{,}_L(c,s)$

1. 位相: ${\phi }_s(c)=b-s\cdot a\mathrm{mod}1$ を計算
2. すべての係数が $[-\frac{1}{2},\frac{1}{2})$ $\mu$ の近似でリカバーできる(?)
3. (1)の同型写像を適用し, $2^{\tau +L}$ をかける(誤差は $2^{\tau -\rho }$ 以下)

注意

対象鍵バージョンについて説明した.

公開鍵バージョンは秘密鍵でこれらの関数を評価することにより実現される.

2.2 Noise models for homomorphic operations

TFH と HEAAN の準同型演算のノイズについて分析する.

2スキームにの共通な演算は線形結合, 積, slot permutations(?), functional bootstrapping(?)

Linear combination

${\sum }_{i=1}^k{\alpha }_i{c}_i$

c は RLWE ciphertext , $\alpha$は係数 in Z

ciphertextのノイズはガウスノイズなので $e_i\in {\mathbb{C}}^{\frac{N}{2}}$

よって合計のノイズは N(x_i, \sigma_i

2^{\tau - \rho} かけることで実際のエラーをシミュレートすることができる　

Multiplications

内積に相当する.

e_1 e_2 はとても小さいので無視できる

よって x_1 e_2 + x_2 + e_1

に2^{(\tau_1 + \tau_2) - \rho} をかけることで実際の誤差を出せる.

Rotations/Permutations

slot representation から coefficient representation に変換することで実現

prthogonal matrixを適用することで変換できる(?)

変換にDFTの評価が入ってしまうのでmultiplication levelを消費してしまう.

Bootstrapping

いままでのbootstrapは平文に準同型な恒等関数を適用して乗算レベルをリセットする.

複雑な非線形関数はinterleaving(間をあけて配置する?)bootstrapによって評価してきた(?)が3つの理由から最適な方法ではありません.

1. 非線形評価のたびにbootstrapが必要
2. 多項式近似で代用可能, 任意の精度で近似しようとするとコストがとても高くなる.
3. bootstrapにはとても大きいパラメータを必要とする

のでより良い方法を探す必要がある.

Functional Bootstrappin

TFHE

テーブルルックアップをつかうことによって離散的な結果を得られる

HEAAN

sinのテイラー展開を評価することでbootstrappingしていた

3. Evaluation of nonlinear functions in neural networks

非線形関数はディープラーニング中心をなるもの, max関数, ReLUとか

注意

ReLUは絶対値があればかんたんに表現できる

ReLU(x) = x + |x|

3.1 Non-linear functions in TFHE

(割愛)

3.2 Non-linear functions in HEAAN

HEAAN では非線形関数は

• 複素数の多項式
• 三角多項式(bootstrap)はこれ

に近似される.

convergence: 収束
superalgebraically: 超代数的

フーリエ変換は連続関数とか正則関数だったら急速に収束する

関数に不連続性がある場合は収束が遅くなる(尖ってるから)

(Skip)

4. Predictions for Deep Learning

4.2 Experiments

LeNet5にMNIST手書き文字認識で実験

表1:

LeNet(7 layers) を max-pooling と average-pooling で　$\sigma$ = 0.0:0.1:1.0で活性化関数に ReLU と ReLU近似 を使用して, train accuracyとtest accuracy 計