密码学基础：同态与同构

这是关于加密技术的更大系列文章的一部分。如果这是你看到的第一篇文章，我强烈建议你从 系列的开头 开始。

到目前为止，我们对 群 的基本理解已经足够有用，可以设计满足许多需求的加密方案，包括 加密，签名，（以及一些 特异变体）， 证明，承诺，可验证的随机性 等等。

我相信，现在是进一步理解群结构的好时机，同时揭开一套新的 酷加密原语。

你可能已经听说过 同态 和 同构。但这些名字听起来奇怪的东西到底是什么？

听起来就像是变形金刚电影中出来的东西

同态的概述

一般来说，同态是一个 函数 或 映射，它保持 代数性质 的不变。

回想一下，当我们处理群时，我们只有一个 集合 和一个 运算。因此，一个 群同态 确实是将一个群的元素映射到 另一个群，其中运算的 性质 是 保持 的。

这一切可以简化为：如果 a 和 b 是一个群的元素，那么一个同态 f 应该像这样工作：

一个同态的好例子发生在我们获取一个具有生成元 G 和阶 n 的 椭圆曲线群，以及 模 n 整数的加法群 时。我们只需定义：

我们可以轻松看到加法是保持的：

同构

注意在上述情况下，两个群的元素之间存在一一对应关系。这 并不总是这样：如果我们选择模 q 的整数，而 q > n，那么至少有两个整数将共享相同的函数值。

在实际上存在一一对应的情况下，我们可以理论上使用 f 将 ℤₙ 映射到 ⟨G⟩，并使用其 逆 f ⁻¹ 将 ⟨G⟩ 映射回 ℤₙ。

用数学术语来说，这意味着 f 是一个 双射。你知道的，以防你想更加确切地说明它！

当这种情况发生时，我们说 f 是一个 同构 而不是同态。两个群被称为是 同构的。

对于群论，我们认为同构的群本质上是同一个群 伪装 而成，因为我们可以找到一个函数，使我们能够将一个群转化为另一个群，反之亦然。

我为什么要关心？

啊，百万美元的问题。

群表达为同态或同构的想法非常有趣，因为在选择的群之间来回移动意味着我们可以在 任一群 中执行操作。这允许我们做一些 魔法。我们稍后将看到这一点。

在深入一个示例之前，我想澄清一些你可能会遇到的符号。如果你查看例如 这一页 有关 ElGamal 加密系统（我们稍后将看到的算法），你会注意到他们在处理群时似乎不使用 加法。相反，他们使用 乘法 和 指数表示法：

嘻，这与我们之前的例子不太一样。怎么会这样？

理解这一点的关键是从 同构 的角度来看待事物。看看这两个群：

如果我们仅仅拿起笔和纸，逐个元素进行匹配，我们可以清楚地看到有一一对应的关系。形式上，关系具有以下形式：

我们说第二个群是 乘法 的——注意 ℤ₅ 中元素的加法被 G ₅ 中元素的乘法所替代：

这是完全可以接受的，因为两个群中的运算 不一定 是相同的。

所以，当你在查看基于群的系统时，看到乘法表示法，请记住，加法版本也可能通过这种同构进行公式化。

好的，可以了

同态加密

好吧，足够的形式化。让我们进入重点。

假设你想对两个整数进行求和，模 q。但这些数字是 加密的。通常，你需要解密这两个数，然后相加。如果你想存储加密结果，你还得 重新加密。

但如果我们可以 完全跳过解密 呢？

这正是 同态加密 的目标：在 受保护 的 私有 数据上进行操作，但得到的结果与使用 未保护 的 原始 数据进行操作的结果相同，然后再进行 加密。

一般思路

这太棒了，因为我们可以节省执行解密操作（这些操作是昂贵的）的时间，同时还保护了数据的隐私。

理论上，至少。关于此还有一些细微差别，我们将在稍后讨论。但隐私部分是很酷的！

那么，我们如何实现这种功能呢？

ElGamal 加密

这是最 简单的加密系统 之一。尽管它很简单，但加密函数具有一个非常好的属性： 它是同态的！

因此，我们可以对加密的数据执行操作。让我们看看它是如何工作的。

像往常一样，我们从Alice拥有一个私钥 d 开始，她利用这个私钥计算出一个公钥 Q = [d]G。是的，G 是你典型的椭圆曲线生成元。

假设Bob想要为Alice加密一条消息，知道她的公钥 Q。为了使这一切有效，我们必须假设 消息 是 椭圆曲线中的一个点， M。这可以通过将原始消息通过一个 可逆函数（散列函数无效）来获得。

我们现在不会讨论如何进行这一步——我们假设我们知道如何实现。

然后，Bob根据以下程序进行加密：

• 他选择一个随机整数 r，计算 R = [r]G。
• 然后，他计算一个 掩码（像往常一样）作为 [r]Q。
• 最后，他将掩码添加到消息中，因此 C = M + [r]Q。

获得的密文为 (R, C)。要解密，Alice需要：

• 计算 [d]R，这将恰好等于掩码 [r]Q。
• 从 C 中减去掩码，因此 C - [r]Q = M。

由于我们现在更加精确，我们可以说减法实际上是添加被减数的 加法逆元素。这样说“减去”会更简单。

这个过程的加密部分可以表示为一个 函数，它接受消息 M 和一些随机性 r，输出一个 密文：

而 这 将是我们的 同态。

想象一下你用随机性 r₁ 加密 M₁，用随机性 r₂ 加密 M₂。如果我们对加密结果进行 加法，会发生什么？

砰！得到的结果与我们先求和消息（和随机性）的结果相同！

简直就像魔法。

虽然这不如调制药水那么神奇，但也不错…

观察

上述方案简单得令人惊讶。尽管这个例子非常具说明性，但它并不完美，还有一些事情我们必须讨论。

可编码的消息

首先，请注意我们可以加密的 消息 与 群的阶 n 相关。还记得群的阶意味着群中 元素的数量，因此群中只有有限的（准确来说是 n）不同的点。

由于我们需要将消息 可逆编码 为一个点 M，这意味着每个点 M 对应于一个唯一的消息——因此我们只能编码 n 个唯一的消息。

这反过来又意味着我们 无法编码 任意长度的消息。我们可以考虑一些巧妙的策略将消息分成“块”，但这可能会破坏我们方案的同态特性。

但这并不意味着该技术没有价值——例如，将消息视为 私有余额。我们可以处理一个最大可表示余额，我们不是吗？

部分同态

另一方面，这种同态加密只支持 单个操作。这也是可以预期的，因为我们在 群 上工作。因此，如果群运算是 加法，那么我们就无法进行 乘法。因此，这被称为 部分同态加密，或 PHE。

如果我们能同时支持 加法 和 乘法，那么我们的方案就会是 全同态的——我们将讨论 全同态加密，简称 FHE。

创建一个全同态加密方案并不是一件容易的事情——并且群 根本无法完成这个任务。我们需要不同的数学结构来解决它，支持 两个运算。当这是我们的要求时，我们需要进入 环理论 的领域，这是我们将在 系列后期 追求的目标。

零知识证明

想象一个具有 私有余额 的应用程序。你可以解密自己的余额，但处理转账请求的任何人 无法解密。因此，你需要以某种方式向处理人证明你：

• 知道自己的余额和转账金额
• 有足够的余额来覆盖转账

但你需要在不揭示值的情况下做到这一点，因为应用程序的整个目的就是 保持余额私密！

为了实现这一点，我们需要将我们的同态加密努力与 零知识证明 (ZKP) 结合起来。一般来说，ZKP 通常计算密集——因此不需要解密的好处在某种程度上被平衡。但是，数据的隐私仍然是必要的——例如，同态加密是公共网络（如区块链）上隐私的一个吸引解决方案。

总结

这次我们深入了数学，这使我们能够更好地理解构建底层的结构。

我们看到一个（部分）同态加密方案的实际应用。当然，ElGamal 不是唯一具有同态特性的系统。其他基于群的方案也存在，比如 Benaloh 加密系统 或大量引用的 Paillier 加密系统。

我们走了很长一段路。目前，我们将暂停对椭圆曲线密码学 (ECC) 的探索。但这并不是旅程的结束， 绝对不是。事实证明，椭圆曲线群与 另一种构造 非常契合，这允许一些 非常酷的加密。我们将很快深入探讨。

然而，我想在此之前谈一个主题： 多项式 及其提供的可能性。这将是 下一篇文章 的主题！

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～