Lattice based Somewhat Homomorphic Encryption

• $q\in \mathbb{N}$ 大きな自然数,
• $n$ 円分整数の次元
• 秘密鍵

$$s=\sum _{i=0}^{n-1}{s}_i{\xi }^i\leftarrow {\mathbb{Z}}^{(2)}[\xi ]({\mathbb{Z}}^{(q)}:=\{-\frac{q}{2}+1,\cdots ,\frac{q}{2}\})$$

ノイズ

$$e\in {\mathbb{Z}}^{(q)}[\xi ]\leftarrow \chi (0,{\sigma }^2)$$

• 注意: $\sigma$ は大きすぎると復号できなくなり, 小さすぎても安全性が低い

公開鍵

$${\mathrm{pk}}_1=a=\sum ^{n-1}{a}_i{\xi }^i\leftarrow {\mathbb{Z}}^{(q)}[\xi ]$$

${\mathrm{pk}}_2=[as+e{]}_q$

Scheme

$\mathrm{KeyGen}$

• $e\leftarrow \chi (0,{\sigma }^2)$
• $s\leftarrow {\mathbb{Z}}^{(2)}[\xi ]$
• $a\leftarrow {\mathbb{Z}}^{(q)}[\xi ]$
• $b=[as+2e{]}_q\in {\mathbb{Z}}^{(q)}[\xi ]$
• $(\mathrm{pk},\mathrm{sk})=((a,b),s)$

${\mathrm{Enc}}_{\mathrm{pk}}(m)$

• 小さな一様乱数 $v{\leftarrow }^U{\mathbb{Z}}^{(2)}[\xi ]$
• ノイズ $e_0,e_1\leftarrow \chi (0,{\sigma }^2)$
• $c_0=[bv+2e_0+m{]}_q,c_1=[av+2e_1{]}_q$
• $c=(c_0,c_1)$

${\mathrm{Dec}}_{sk}(c)$

• $m=[[c_0-s{c}_1{]}_q{]}_2$

$\mathrm{Add}(m,m^{\prime })$

• $(c_0+c_0^{\prime },c_1+c_1^{\prime })={\mathrm{Enc}}_{pk}(m+m^{\prime })$

$\mathrm{Mul}(m,m^{\prime })$

• $(c_0^{\prime \prime },c_1^{\prime \prime },c_2^{\prime \prime }):=([c_0{c}_0^{\prime }{]}_q,[c_0{c}_1^{\prime }+c_0^{\prime }{c}_1{]}_q,[-c_1{c}_1^{\prime }{]}_q)(\mathrm{mod}q)$
• $m{m}^{\prime }=[[c_0^{\prime \prime }-s{c}_1^{\prime \prime }-s^2{c}_2^{\prime \prime }{]}_q{]}_2$

問題点は計算結果が3成分になってしまうこと

Relinearize

• relinearize

健全性の証明

加算

$$m+m^{\prime }={\mathrm{Dec}}_{\mathrm{sk}}(c{+}^{\prime }{c}^{\prime })$$

を示す
$c_0^{\prime }-s{c}_1^{\prime }:=m^{\prime }+2e_t^{\prime }$

$${\mathrm{Dec}}_{sk}({\mathrm{Enc}}_{pk}(m+m^{\prime }))$$ $$\equiv (c_0+c_0^{\prime })+s(c_1+c_1^{\prime })$$

$\equiv \cdots$

$$\equiv m+m^{\prime }+2(e_t+e_t^{\prime })(\mathrm{mod}q)$$

$2(e_t+e_t^{\prime })\ll q$
よりOK

乗算

$$m{m}^{\prime }={\mathrm{Dec}}_{sk}(c{\times }^{\prime }{c}^{\prime })$$

を示す
$c_0^{\prime }-s{c}_1^{\prime }:=m+e_t^{\prime }$

$$c^{\prime \prime }\equiv m{m}^{\prime }+2(e_t{m}^{\prime }+e_t^{\prime }m+e_t{e}_t^{\prime })(\mathrm{mod}q)$$

積のノイズ部分(第2項) が
$q$
より小さい時に正しく復号できる.

$$c_0^{\ast }-s{c}_1^{\ast }\equiv \cdots \equiv Pm{m}^{\prime }+2P{e}_t^{\prime \prime }+2e{c}_2(\mathrm{mod}q)$$

は
$P$
の倍数.

$$[[c_0^{\ast }-s{c}_1^{\ast }{]}_q{]}_2=\cdots =m{m}^{\prime }$$

参考文献

• 完全準同型暗号入門 | Mathlog