Function Evaluation with Fully Homomorphic Encryption using Table Lookup

Table Lookup の話

Abstract

• 加算や乗算で表現できない関数のために WAHC 2018 で Look Up Table(LUT) が考案された

• $(\mathrm{mod}P)$

  • $P=2$: GSW scheme
  • $P>2$: BGV scheme

2.3 PIR

選択する

data $v=[v_{0,}\cdots ,v_t,\cdots ,v_{n-1}]$
query $q=[0,\cdots ,1,\cdots ,0]$
result $v_R=[0,\cdots ,v_t,\cdots ,0]$

• 計算済みテーブル $T_F[x]=f(x)(x\in R)$
  • 複雑な関数も評価できるがすべての入力を含むので巨大

4. LookUp を用いたFHEの関数評価

• 2-party protocol
  • computation server(cs), decryptor, users
• 複雑(非線形)な関数 $f$ を cs で評価
  • e.g. $f(x)=\sqrt{x}$