Algorithms in HElib

@inproceedings{halevi2014algorithms,
  title={Algorithms in helib},
  author={Halevi, Shai and Shoup, Victor},
  booktitle={Annual Cryptology Conference},
  pages={554--571},
  year={2014},
  organization={Springer},
  url={https://www.shoup.net/papers/helib.pdf}
}

FHEで行列積

Abstract

• BGV scheme のアルゴリズム
• 線形代数に基づくデータ移動とか最適化とか

Introduction

• HElibはアセンブリとか言われる(わかる)
• ss3 で GHS permutation techniques
  • Parallel Processing Letters - Wikipedia の拡張
  • GHS hypercube networksの最適化　
• ss4: ベクトルを複製してベクトル和とか計算する, norm とかtrace

Batckground and Notation

• 最適化の指標: ノイズ最小化と実行時間
  

雑なprimitiveな演算のノイズと実行時間

notations

• $[n]:=\{0,n-1\}$
• $\times ,+$ はelement-wise

Permutations and shift-networks

• GHS data-routing techniquesは Benes network みたいな基づく
  • slotsの並び替え
• shift-networktとその最小化を紹介

3.1 Shift Networks

• shift network

The Cheapest-shift-network(CSN) problem

in: 深さ $B$ の並び替え $\pi$ over $[n]$
out: $B$ 以下のcostが最小の $\pi$

• $B$ 大事
  ex. 解が cost-$\Omega (n)$, depth-1 もあれば
  cost-$\mathcal{O}(\sqrt{n})$ depth-2もある
• depthに制限つけると効率的な解を探せる
• NP Hard? -> 知らない

3.2 Benes Networks

• 任意の並び替えは適切にcontrol bitを設定してバタフライ演算で出来る
  • Benes network はshift-networkの特別な場合
• 効率的に構築でき, 演算costも低い
• $n=2^r$ でかんがえる
  • $\pi$ on $[n]$ は depth $2^r-1$ の shift-network
    • すべてのネットワークでcost 2
• $\pi$ を$2r-1$の並び替え $\pi ={\delta }_{r-1}\circ \cdots {\delta }_1\circ {\delta }_0\circ {\tau }_1\cdots {\tau }_{r-1}$ に分解できる
  • ${\delta }_k$: ${}^{\forall }i\to i+2^k$
  • ${\tau }_k:{}^{\forall }i\to i-2^k$
    • それぞれは $2^{r-1-k}$ のseparate permutatins n different $2^{k+1}$-intervals of indexes
• これは depth-$2r-1=\mathcal{O}(\log n)$ , cost-$4r-2=\mathcal{O}(\log n)$

Benes Networkのアルゴリズム

permutatonsをBenes networkに分解するのは再帰的な処理で出来る

1. $\pi \to \sigma \circ \rho \circ \tau$
   $\rho$ はnetworkの上下半分に???, これは貪欲なlooping alghrithm で
   $m:=\frac{n}{2}=2^{r-1}$とする
   $S_0:=\{0,\cdots ,m-1\},S_1:=\{m\cdots ,n-1\}$

(P1)

• $\sigma :i\in S_0\to$ $i$ or $i+m$

• $\tau :i\in S_1\to i\mathrm{or}i-m$
  (P2)

• $\rho$ は$S_0,S_1$ 上で2つの並び替えからなる

• $n$ nodesのa無向グラフ $G$ を作る

  • 両端に $L_i,R_i(i\in [n])$ がある
  • $L_i$から $R_{\pi (i)}$ への辺(permutation edgesと呼ぶ)を追加
  • $i<m$ のとき, conflict edges $L_i\to L_{i+m}$ も追加する(彩色のため)

• $G$ は 簡単に, 2-colorable 出来て, 2分割可能

• $i\in S_0$

  • $\tau (i)\leftarrow i+C(L_i)m$
  • ${\delta }^{-1}(i)\leftarrow i+(!C(R_i))m$

• $i\in S_1$

  • $\tau (i)\leftarrow i-!C(L_i)m$
  • ${\delta }^{-1}(i)\leftarrow i-C(R_i)m$

• ${\delta }_{k,}{\tau }_k$ のshit量は $\pm 2^k,0$

3.3 General Benes Networks

• Changらは Benes network をslot数任意の $n$ に一般化した
• $n$ が奇数の時は $\lfloor n/2\rfloor$ と $+1$

Further optimizations

• 分け方が2通りあるが, トータルのshift量は変わる

  • 下半分 が+1だと $m=\lfloor n/2\rfloor$ となり,
    • conflict edge $L_{n-1}\to R_{n-1}$ を追加して $\sigma (n=1)=\tau (n-1)=n-1$

• $\pi ={\sigma }_{r-1}\circ \cdots ,{\sigma }_1{\circ }_0\circ {\tau }_1\circ \cdots ,{\tau }_{r-1}$ (r=$\lceil \log n\rceil$)

  • ${\delta }_k,{\tau }_k$ のshiftは $i,i\pm {\Delta }_k$ になる
    • ${\Delta }_k:=\lceil \lfloor n/2^{r-1-k}\rfloor /2\rceil$

• depth 2 $\lceil \log n\rceil -1$ , 各レベルでcost2のshift networkを得る.

  • これはunbounded cheapest-shift-network problem

3.4 Balancing Depth and Cost in Benes Networks

• slots数 $n$ とコスト上限 $B$ が与えられればDP出来る

• $d:=2\lceil \log n-1\rceil$

• $S_k$: level k で現れたshift量の集合

• $0\le j_1\le j_2<d$, で $L(j_i,j_2)\in (-n,n)$: level $j_1$..$j_2$ で可能な非0なshift量.

• $L$ は効率的に計算できるので d’ in 0..d, B’ in 0..B でDPを使って $\mathrm{Opt}({\mathrm{d}}^{\prime },{\mathrm{B}}^{\prime })$ を計算できる

3.5 Hypercube networks

• Hypercube network: shift networkを構築する別の方法

  • $n=ab$ とできるなら, $a\times b$ 行列でapproximate(??) bimap $M:[n]\to [a]\times [b]$

• CRT order: $a\perp b$ , $M:i\to (i\mathrm{mod}a,i\mathrm{mod}b)$

• Row-major order: $i\to (i/b,i\mathrm{mod}b)$

  • 横に並べる

• Column-major order: $i\to (i\mathrm{mod}a,i/a)$

  • 縦に並べる

• CRT orderingがadvantage

  • ring homなので

• Lemmaはproofつけて高校

• shift networkから $a\times b$ 行列に自然に拡張できる

• $\mathrm{SplitRcost}(n,B)$: reduced const

• $\mathrm{SplitUcost}(n,B)$: un-

なぜ, Bを3つに分けるのか todo

4. Replication and Linear Algebra

• アルゴリズムどうやるかみる
  • 総和, mat-vec mul

4.1 Running- and Total Sums

• Running Sums
  • 累積和: $w\leftarrow \mathrm{RS}(v),w[i]={\sum }_{k=0}^{i}v[k]$
• 
• mask使うので? noiseはTSよりも多い
• Total Sum

4.2 Replication

• 普通のHE回路は大きなfan-out:入力をもつ

  • 暗号文のコピーが多く起こる

• generic replication methodは出来ていない

• few interesting casesに対して効率的なreplicationを実装した

• q binaryとしてコピーするのはだめなのか

Replicating a single value

• 定数maskをすれば良い
  • TSなので $\mathcal{O}(\log n)$ add, rots, 1 mask

4.2.1 Full replication

• naive: single repl を $n$ 回繰り返す = $\mathcal{O}(n\log n)$

• あまり興味ないのでskip todo

4.3 Matrix/Vector Multiplication

Matrix in column-order

• $A=(c_0\mid \cdots \mid c_{n-1})$
• $Av={\sum }_{i=0}^{n-1}v[i]c_i$
  • $v$ のfull replicationが必要
• $w\leftarrow {\sum }_{i=0}^{n-1}{v}_i\cdot c_i$
  • HybridReplicate アルゴリズムで O(n) add, mult, mask, rots

Matrix in row-order

todo

Matrix in diagonal order

• もし, 行列がplaintextならbest solution
• vector $d_0,\cdots ,d_{n-1}$
  • $d_i=(A_{0,i},A_{i,i+1},\cdots ,A_{n-1,i-1})$
  • $d_i[j]=A_{j,[j+i]}$
• $Av={\sum }_{i=0}^{n-1}{d}_i\cdot (v\ll i)$
  • $n$ rots, mult, add
  • mult-depth: 1
• $w[j]=\sum d_i[j]\cdot (v\ll i)[j]=\sum A_{j,j+i}=\sum A_{j,k}\cdot v[k]$

4.4 Computing norms and traces

todo

5. Hypercubes in the Underlying Platform

参考文献

• Algorithms in HElib - YouTube