Faster PCA and Linear Regression through Hypercubes in HElib

Abstract

• HEでPCAとかLR(Linear Regression)やりたいね
• Lu protocols(NDSS2017) でptの構造改善
  • linear arrayから2d hypercubeに
• HElib 上に BGV scheme で実装した
  • x5 faster

Introduction

hypercube pt slotsの操作として2種類ある

• hypercube arrangement
  • $n$-d hypercube $V$ の添字は $e=(e_1,\cdots ,e_n)$
  • 各次元は $rotate1d(v,i,k)$ で独立に回転できる
    • $(\cdots ,e_i,\cdots )\to (\cdots ,e_i+k,\cdots )$
• linear array arrangement
  • 1d arrayと見立てて, $\mathrm{rotate}(v,k)$ する

他の高レベルの操作に Total Sum とreplicateがある

• hypercube total sum
  • $TS1d(V,j)={\sum }_{k=0}^{m_j-1}V[\cdots ,j=k,\cdots ]$
• hypercube
  • $rep1d(V,j,\{k_i\})=V[\cdots ,j=k_i,\cdots ]$