当前位置：网站首页>Relinearization in homomorphic encryption (ckks)

Relinearization in homomorphic encryption (ckks)

2022-06-25 22:39:00 【Salted fish Feifei】

Homomorphic encryption scheme based on ring , such as BGV,BFV perhaps CKKS, After multiplicative homomorphism , It often leads to the increase of the dimension of the ciphertext . For example, by plaintext m_1 Encrypted ciphertext $\textbf{c}_1=(a_0,a_1)$ , Plaintext m_2 The encrypted ciphertext is $\textbf{c}_2=(b_0,b_1)$ , be $\textbf{c}_1 \cdot \textbf{c}_2=(a_0b_0,a_0b_1+a_1b_0,a_1b_1)$ , The dimension becomes 3. In order to calculate homomorphic multiplication efficiently , Suppress ciphertext growth , We need to re linearize .

We use CKKS For example

Suppose there is a ciphertext $\textbf{c}=(c_0,c_1)$ And the ciphertext after a multiplication $\textbf{d}=(d_0,d_1,d_2)$ , Private key $\textbf{s}=(1,s)$ , For $\textbf{c}$ , Decrypted as m+e=c_0+c_1s , about $\textbf{d}$ , Decrypted as m+e=d_0+d_1s+d_2s^2 .（ Operations are modular p operation ,p Module of plaintext space ,e To generate noise ）

In order to realize the re linearization of ciphertext , We also need a secondary key evk=(b,a) , among b=-as+e+ps^2 .

On the other hand $\textbf{d}$ Reduplicalized ciphertext $\textbf{c}\prime=(c_0,c_1)=(d_0,d_1)+\lceil evk \cdot d_2 \cdot p^{-1} \rfloor$ .

Prove the following ：

$c_0=d_0+\lceil bd_2p^{-1} \rfloor=d_0+\lceil -asd_2p^{-1}+d_2ep^{-1}+d_2s^2 \rfloor$

$c_1=d_1+\lceil ad_2p^{-1}\rfloor$

$c_0+c_1s=d_0+d_1s+d_2s^2+\lceil d_2ep^{-1} \rfloor$

because e It's noise , be relative to p It's very small , therefore $\lceil d_2ep^{-1} \rfloor$ In case of effective decryption, it is 0. so , The new ciphertext is $\textbf{d}$ One of the 2 Uyghur ciphertext .

原网站

版权声明
本文为[Salted fish Feifei]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202180953524108.html

当前位置：网站首页>Relinearization in homomorphic encryption (ckks)

Relinearization in homomorphic encryption (ckks)

边栏推荐

猜你喜欢

随机推荐