relinearize

• 積の結果を3成分から2成分にする方法
• $q$ と同程度の大きさの奇数 $P$ を選ぶ

$$(A,B)={\mathrm{Enc}}_{sk}(s^{2}P)=(\leftarrow {\mathbb{Z}}^{(qP)},[As-s^{2}P+2e{]}_{qP})$$ $$c^{\prime \prime }=\mathrm{Mul}(c,c^{\prime })=(c_0^{\prime \prime },c_1^{\prime \prime },c_2^{\prime \prime })$$ $$c_0^{\ast }:=[P{c}_0^{\prime \prime }+B{c}_2^{\prime \prime }{]}_{qP},c_1^{\ast }:=[P{c}_1^{\prime \prime },A{c}_2^{\prime \prime }{]}_{qP}$$ $$({\mathbf{c}}_0,{\mathbf{c}}_1)=([\frac{c_0^{\ast }-{\delta }_0}{P}{]}_q,[\frac{c_1^{\ast }-{\delta }_1}{P}{]}_q)({}^{\exists }{\delta }_i\in {\mathbb{Z}}^P,[c_i^{\ast }-{\delta }_i{]}_P=0,[{\delta }_i{]}_2=0)$$

意味: $\delta$ は $P$ で割り切れるように調整することによってノイズを消しながら剰余を $q$ に戻している.

参考文献

• Lattice based Somewhat Homomorphic Encryption