Homomorphic Encryption for Arithmetic of Approximate Numbers

CKKS scheme の提案論文

BFV scheme が原型

cannonical embedding norm

toohard

• $\Vert a{\Vert }_{\infty }^{\mathrm{can}}:=\Vert \sigma (a){\Vert }_{\infty }$: $\sigma (x)$ の${\ell }_{\infty }$ norm

性質

• ${}^{\forall }a,b\in S$, $\Vert a\cdot b{\Vert }_{\infty }^{\mathrm{can}}\le \Vert a{\Vert }_{\infty }^{\mathrm{can}}\cdot \Vert b{\Vert }_{\infty }^{\mathrm{can}}$
• ${}^{\forall }a\in S,\Vert a{\Vert }_{\infty }^{\mathrm{can}}\le \Vert a\Vert$
• ${}^{\forall }a\in S,\Vert a{\Vert }_{\infty }^{\mathrm{can}}\le {}^{\exists }{C}_M$ (const)
  • $C_M=\Vert {\mathrm{CRT}}_M^{-1}{\Vert }_{\infty }$
    • $\Vert U{\Vert }_{\infty }:={\max }_{0\le i\le N}{\sum }_{j=0}^{N-1}|u_{ij}|$ ($U$ は原始 $M$ 乗根のvandermonde matrix)

valid encryption

• $(c\in {\mathcal{R}}_{q_{\ell }}^2,\ell ,\nu ,B)$ を $m\in S$ の妥当な暗号文と呼ぶ
  • $\Vert m{\Vert }_{\infty }^{\mathrm{can}}\le \nu$
  • $⟨c,\mathrm{sk}⟩=m+e(\mathrm{mod}{q}_{\ell })$
  • ${}^{\exists }e\in S,\Vert e{\Vert }_{\infty }^{\mathrm{can}}\le B$