如何理解算法为什么使用相加或乘法同态

Question

如果我们以LWE (带错误学习)为例，我们如何知道它是通过加法还是乘法来同态的？

Answer 1

为什么问题有一个深刻的答案，因为它是深入的研究！如何解决这个问题要容易得多。要检查加密方案是如何同态的，请查看一般的同态；

让f:A\to B成为保存结构的映射。f(x \cdot y) = F(x)\cdot f(y)，那么我们说f是同态(用一个非常简单的术语)。

这在FHE设置中有点不同，因为方案在语义上是安全的(其中大多数方案)，因此不能在范围(加密消息空间)上进行比较，因此需要解密才能看到这一点。

要检查加法(或FHE (或部分FHE)使用的任何操作)，需要两个不同的输入x_1 \neq x_2，并应用\mathcal{E}表示FHE加密和\mathcal{D}代表FHE解密的规则。

\mathcal{E}(x_1 + x_2) = \mathcal{E}x_2) \boxplus \mathcal{E}(x_1),我们不能检查这个，所以我们需要解密。

x_1 + x_2 = \mathcal{D}\left(\mathcal{E}(x_2) \boxplus \mathcal{E}(x_2)\right)

正如为加法所做的那样，任何操作都可以这样做。为什么\boxplus而不是+，加密消息上的操作不需要添加。

所以一般的规则，让\oplus是你想要测试它的同态的操作。然后

x \oplus y = \mathcal{D}\left(\mathcal{E}(x) \boxplus \mathcal{E}(y)\right)，其中\boxplus可以等于\oplus也可以不等于D14。

例如，在Goldwasser-Micali密码体制中

\begin{align} \mathcal{E}(b_1)\cdot \mathcal{E}(b_2) &= x^{b_1} r_1^2 x^{b_2} r_2^2 \;\bmod\; n \\[6pt] &= x^{b_1+b_2} (r_1r_2)^2 \;\bmod\; n \\[6pt] &= \mathcal{E}(b_1 \oplus b_2). \end{align}

密文的乘法等于明文的X-或，这主要用于加密数据的指纹验证。

在Paillier密码系统中

\begin{align} \mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= (g^{m_1} r_1^n)(g^{m_2} r_2^n) \;\bmod\; n^2 \\[6pt] &= g^{m_1 + m_2} (r_1r_2)^n \;\bmod\; n^2 \\[6pt] &= \mathcal{E}(m_1 + m_2). \end{align}

如我们所见，密文的乘法等于明文的加法。这用于数据的聚合，特别是在数据库中。

另一方面，(教科书) RSA密码体制

\begin{align} \mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= m_1^e m_2^e \;\bmod\; n \\[6pt] &= (m_1 m_2)^e \;\bmod\; n \\[6pt] &= \mathcal{E}(m_1 \cdot m_2) \end{align}

对明文和密文都使用相同的操作。