同态加密的定义

设

其中 $f$ 为待计算的函数，$x_1, ..., x_n$ 为输入值。

若满足以下条件，则 $enc$ 为同态加密函数：

换言之，同态加密函数允许您在加密数据上进行计算。然而，对加密数据进行计算会产生加密输出，除非能将其解密以得出有意义的数值，否则其并无实际作用。因此，同态加密函数需要配备相应的解密函数，用于恢复最终的加密结果。

我们将解密函数记为 $dec$，则应满足以下关系：

寻找一对无论函数 $f$ 为何都能完美运行的加密和解密函数（$enc-dec$）是具有挑战性的。然而，如果对函数 $f$ 的形式施加限制，则可以创建相应的同态加密函数。

例如，假设函数 $f$ 仅由乘法组成。以下同态加密-解密函数集或可适用：

其中 $e$、$d$ 和 $n$ 是经过精心选择的数字，从而对于任何给定的 $x$，均满足 $(x^e)^d = x \mod n$。感兴趣的读者可以参考该 Wikipedia 页面，了解如何生成满足上述等式的这些数字。

为了说明其工作原理，我们以一个仅由乘法组成的简单函数 $f(x_1, x_2, x_3) = x_1 * x_2 * x_3$ 为例。显而易见：

这满足了 $enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))$ 的要求。

对于解密过程：

我们的确可以通过对加密输入计算函数 $f$ 的输出，从而恢复正确的乘法结果。

上述同态系统被称为未填充 RSA（因为其利用了 RSA 密码系统），是所谓的半同态密码系统（Partially Homomorphic Cryptosystems）的一个实例。顾名思义，它们是“部分”的，因为它们无法应用于任意函数 $f$。您可以在此处找到许多其他半同态密码系统。

同态加密与安全多方计算

现在您可能会产生疑问：同态加密如何帮助我们实现安全多方计算？解决这一问题需要发挥创造力，因为您必须在不同情况下以不同的方式利用同态加密。我们以基于未填充 RSA 同态密码系统的示例来进行阐述。

假设有三个人 Alice、Bob 和 Charlie，他们各自持有希望保密的数字 $a$、$b$、$c$。他们希望在不向彼此透露各自数字的前提下，共同计算这些数字的乘积。实现此目标可以在另外两个人 Sarah 和 Nancy 的协助下完成。

具体步骤如下：

Sarah 生成未填充 RSA $enc-dec$ 密钥对，并将 $enc$ 函数发送给 Alice、Bob 和 Charlie。
Alice、Bob 和 Charlie 分别计算 $a' = enc(a)$、$b' = enc(b)$、$c' = enc(c)$ 并发送给 Nancy。
Nancy 将从 Alice、Bob 和 Charlie 处接收到的数字相乘，得到 $d' = a' * b' * c'$，后将 $d'$ 回传给 Sarah。
Sarah 随后计算 $d = dec(d')$ 并将其回传给 Alice、Bob 和 Charlie。

此时，$d$ 即为乘积结果 $a * b * c$。

在上述流程中，Alice、Bob 和 Charlie 未曾向其他任何人泄露其私密数字，但所有人都获知了这些数字的乘积结果。

说明>