A Recommender System for Efficient Implementation of Privacy Preserving Machine Learning Primitives Based on FHE

@InProceedings{shaik20,
author="Shaik, Imtiyazuddin
and Kumar Singh, Ajeet
and Narumanchi, Harika
and Emmadi, Nitesh
and Bhattachar, Rajan Mindigal Alasingara",
editor="Dolev, Shlomi
and Kolesnikov, Vladimir
and Lodha, Sachin
and Weiss, Gera",
title="A Recommender System for Efficient Implementation of Privacy Preserving Machine Learning Primitives Based on FHE",
booktitle="Cyber Security Cryptography and Machine Learning",
year="2020",
publisher="Springer International Publishing",
address="Cham",
pages="193--218",
abstract="With the increased dependence on cloud computing, there is growing concern for privacy of data that is stored and processed on third party cloud service providers. Of many solutions that achieve privacy preserving computations, fully homomorphic encryption (FHE) is a promising direction. FHE has several applications that can be used to perform computations on encrypted data without decrypting them. In this paper, we focus on realizing privacy preserving machine learning (PPML) using FHE. Our prime motivation behind choosing PPML is the increased use of machine learning algorithms on end-user's data for predictions or classification, where privacy of end-user's data is at stake. Given the importance of PPML and FHE, we formulate a recommender system that enables machine learning experts who are new to cryptography to efficiently realize a machine learning application in privacy preserving manner. We formulate the recommender system as a multi objective multi constraints optimization problem along with a simpler single objective multi constraint optimization problem. We solve this optimization using TOPSIS based on experimental analysis performed on three prominent FHE libraries HElib, SEAL and HEAAN from the PPML perspective. We present the observations on the performance parameters such as elapsed time and memory usage for the primitive machine learning algorithms such as linear regression and logistic regression. We also discuss the technical issues in making the FHE schemes practically deployable and give insights into selection of parameters to efficiently implement PPML algorithms. We observe that our estimates for matrix multiplication and linear regression correlate with the experimental analysis when assessed using an optimizer. The proposed recommendation system can be used in FHE compilers to facilitate optimal implementation of PPML applications.",
isbn="978-3-030-49785-9",
url={https://drive.google.com/file/d/1DUVPY-ksOwU-cX0mxmx0NhNUsEuRXCb-/view?usp=sharing}
}

(PPML): privacy priserving ml

TOPSIS: optimizer

Related Work

iDash Genome sequence competition

prediction & classification tasks of genome dataset

secure division: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4698942/

SEAL: automatic parameter selection

FHE Libraries and Implementation Aspects

FHEの困難性の論拠

• Lattice: SVP, CVPの困難性
• LWE: key size $O(n^2)$
• RLWE: key size $O(nlogn)$

preliminaries

$M$: サイクロマティック多項式
$N$: の次数
$p$: 平文のモジュラス
$t=p^r$
$h$: 秘密鍵の $L_1$ norm
$q={\prod }_{\mathrm{1..}l}{q}_i,q_i$ は小さな素数
$\alpha$: sampling errorのためのガウス分布の幅
$\xi$: ノイズ分布

HE standardization のパラメータセットで実験を行った

同じ $\lambda$ でも異なるパラメーター選択があるが,
アプリケーションや計算グラフの深さに適したパラメータを選択するのが課題
積極的な研究分野で

Conditionals in Homomorphic Encryption and Machine Learning Applications

FHEの計算に大きな影響を与えるのは格子次元 $N$ とモジュラス $q$

$q$: 計算回数の限度に影響

→ モジュラススイッチでノイズを減らせるため

$N$: 平文スロット数に影響

CKKSでは精度もパラメータとして選択する

3.4 Ciphertext Packing

ベクトル状の平文を暗号化してSIMDで計算できる

多項式のCRTを背景

欠点は各要素にアクセスする事ができない

→ 回転演算を用いて解決

特定の要素(スロット)に対しての演算を行うには膨大な回転と定数乗算を必要にするのでコスト高い

→ on the fly(実行中/動的に) で同型にアンパックする必要がある.

次元 d の行列積比較

• 異なるユーザーの暗号化されたデータを単一の暗号文にパックして計算時間を節約できる(ciphertext packing)
• 共通の処理をまとめておこない, 展開して残りの演算を行う(on-the-fly packing)
• MLアプリケーションでは効率的なon-the-fly-packingが必要

3.5 Bootstrapping

主なbootstrappingの時間とか

4. Case Studies

4.1 FHE Primitive Operations

• HElib: 値の範囲 $[0,p-1]$
• SEAL, HEAAN: $[-(p-1)/2,(p-1)/2]$

除算

• HElib: 2べきのみ可能
• SEAL, HEAAN: $x^{-1}$ を暗号化して乗算

除算を効率的に行う方法は未解決

Recommendation

TOPSISによる最適化問題を解くことで検証

4.2 Matrix Multiplication

4.3 Linear Regression

• bootstrapping か interaction(decrypt and encrypt) が必要になる前に計算できた
• SEALのほうがかんたん

表6. SEALのイテレーションごとの線形回帰パフォーマンス（32コアCPU使用時）。
E.T - 経過時間，通信コストはインタラクションごとにθ値を送信するための片道コスト，150×4データセットのN=8192パラメータレベルのメモリ消費量は
150 × 4 データセットの N = 8192 パラメータレベルのメモリ消費量は 1.1 GB，265 × 10 データセットの場合は
150×4データセットのN=8192パラメータレベルのメモリ消費量は1.1GB、265×10データセットのメモリ消費量は2.5GBである。
パラメータが大きいほど乗算の深さが大きくなるため，段階的にインタラクションを使用することができる．

• noise budget を使い切るために3-4回の乗算しかできない
• HEAANはより高くパラメータ設定して5回

Packed Linear Regression Without Bootstrapping

ブートストラッピングを行うことで
非対話型のモデルを実現することができます。私たちは、HEAAN
ライブラリで実験しました。ブートストラッピングのためには、パラメータを非常に高く設定する必要があります。
を15以上に設定し、より多くのノイズバジェットを必要とします。この設定では、150×4
データセットは320-240秒、265×10データセットは950-500秒かかります。
低いモジュラスに変更すると性能が向上します。

4.4 Logistic Regression

• シグモイド関数使うがコスト高い → Taylor展開で近似

低出生体重児に対するロジスティック回帰の学習とテストを行った。

データセット[52]は，189行，8つの特徴を持ち，分類のためのバイナリ出力を持つ．
判定のためのバイナリ出力を持つ．このデータセットは，低出生体重児（体重2.5kg未満）の出産に関連する危険因子を特定するために使用される．

低出生体重児（体重2.5kg未満）の出産に関連する危険因子を特定するために用いられる．このデータセットは
このデータセットは、いくつかの行動変数に基づいて、赤ちゃんの出生時体重を予測するために使用されます。

我々の実装は、[14]の実装を忠実に踏襲しています。モデルのパラメータを取得するための総実行時間は
モデルパラメータを得るための総実行時間は、7回の反復で14.5秒、AUCは0.785でした。

AUCは0.785であった。

ここでは，N値を8192に設定し，4096個のスロットを用意しました．
データセットを1つの暗号文にまとめるために、余分なゼロをパディングして、256×16の寸法にしました。
256×16の大きさになるように，余分なゼロをパディングして1つの暗号文にまとめました．これは，[14]で説明されているように，スロット内でのデータの移動が正しく行われるようにするためです．
これは，[14]で説明されているように，スロット内での正しいデータ移動を確保するためです．log qは、相互作用が必要ないように十分に高い値に設定しました。
を必要としませんでした。これは、[14]のガイドラインに従って計算することができます。
推奨事項 ノイズバジェットをHEAANで適切に設定することで
提言：ノイズバジェットをHEAANで適切に設定することで、特定の反復回数で相互作用が必要ないようにすることができる。大きなデータセットの場合
大規模なデータセットの場合は、データセットを列ごとに分割し、PPMLアルゴリズムを
を繰り返し行うことができる。

4.5 Bootstrapping

このセクションでは、HEAANライブラリでのブートストラップ技術の実験結果を説明します。
の実験結果を紹介します。図4bは、入力値やパラメータ値を変えてブートストラップを行った後の誤差偏差（±実測値）を示しています。
図4bは、異なる入力値とパラメータ値(log pやslotsなど)に対するブートストラップ操作後の
図4bは，異なる入力値とパラメータ値（log pとslots）に対するブートストラップ操作後の誤差偏差（±実測値）を示している．ここでlog pは計算の正確さを表し、slots
は詰めることのできる値の数を表します。ブートストラップが機能するためには
(log p + log (input)) < (log q) が必要となります。

ブートストラップ回路の深さのためです。これはブートストラップ回路の深さのためです。
log pの値が変化しても、ブートストラップ操作にかかる時間は一定です。8 スロットと 16 スロットでは、それぞれ 5.2 秒と 5.7 秒かかります。
スロットの場合，それぞれ5.2秒，5.7秒かかりました．図4aは、スロット数の増加に伴うブートストラップ動作にかかる時間を
図4aは、スロット数の増加に伴うブートストラップ操作にかかる時間を示しています。ブートストラップにかかる時間は、スロット数に対して指数関数的に増加することがわかります。
指数関数的に増加しています。

5 Recommendation System for FHE

5.1 定式化