shift network

任意の回転, 乗算マスク, 加算を実現するための手法

• 任意の並び替え: $\pi :[n]\to [n]$

  • に対するshift-column $c_{\pi }$: 各slotでどれだけ回転すればよいか
    ex. $\pi :[1,2,3,4,5,6,7]\to [4,2,6,1,3,7,5]$
    なら
    $c_{\pi }:[3,0,2,-3,2,-3,-1]$

• mask $m_{\delta }$ は 1 $c_{\pi }[i]=\delta$ otherwize: $0$

• maskと掛け算した後に非0が先頭に来るようにshift

$$\pi (v)\leftarrow \sum _{\delta \in c_{\pi }}(m_{\delta }\times v)\ll \delta$$

• cost: # of $\delta \ne 0$ rots

• 1 cmult depth

• shift network: shift-colの列 $(c_{{\pi }_1},\cdots ,c_{{\pi }_t})$

  • $t$ 個の置換 $\pi ={\pi }_t\times \circ \cdots {\pi }_1$ ($d$ はnetworkのdepthとする)

• $N$ のcostはlevelの和

• $d$ のdepth

  • $\pi$ は $c$ 定数マスク, $c$ rots, $\mathcal{O}(c)$ adds, $d$

• と $c$ のcost

  • $d$ rots, $\mathcal{O}(d)$ adds

参考文献

• Algorithms in HElib