这篇文章实际上描述了两种构造，第二种使用第一种作为构建工具。第一种结构提供不可区分的混淆，而第二种结构是功能加密。

不可区分性混淆是一个相当深奥的属性，这不是非学术人士听到“混淆”时所想到的；该术语用词不当。该属性意味着，如果您可以将某些“处理”编码为电路（粗略地说是一段可以展开的代码，没有无限循环），这样就有几个可能的不同电路产生相同的结果，那么不可区分混淆允许发布“混淆电路”，这样任何人都可以运行该电路并获得结果，但外人无法知道哪个可能的电路被用作内部的基础。

好的 IO 本身能做什么还不清楚。作者在他们文章的第 1.7 节中，仍然提出了一个相当牵强的例子：

软件开发人员通常希望发布其软件的演示或限制使用版本，以限制完整版本中可用的功能。在某些情况下，商业软件开发人员会这样做来展示他们的产品；在其他情况下，开发人员将希望制作具有不同价格点的多层产品。在其他领域，软件可能会提供给仅部分受信任的合作伙伴，而开发人员只想发布任务所需的功能。

理想情况下，开发人员只需从完整版本开始，然后在界面级别关闭某些功能，即可创建软件的降级版本——只需最少的额外工作。但是，如果这一切都完成了，攻击者很容易绕过这些控制并获得对完整版本或其背后代码的访问权限。另一种选择是软件开发团队小心地从软件核心中删除所有未使用的功能。删除功能可能会成为一项非常耗时的任务，它本身可能会导致引入软件错误。此外，在许多应用程序中，可能不清楚哪些可以保留，哪些不能保留为受限使用版本。

一种直接的解决方案是开发人员在接口级别限制使用，然后发布程序的混淆版本。对于这个应用程序，难以区分的混淆就足够了，因为根据定义，接口中受限的版本与具有等效行为的混淆程序无法区分，该程序在开始时就删除了它的智能。

用例充其量是可疑的。但是，IO 有一个更有用的（理论上的）功能，作者随后将其公开：它使他们能够构建功能加密。

功能加密是关于提供一个可计算的电路（用 IO 混淆），它接收某个值x 的加密版本作为输入，并为某个函数F返回F(x)，而不会透露有关x 的任何其他信息。作者展示了他们如何为任何可以编码为电路的函数F做到这一点，并且由此产生的混淆电路相对于实现F的原始未混淆电路是“多项式大小的” 。

现在这个“多项式大小”的表达式告诉我们，我们处于数学的抽象世界中，而不是在实际世界中。它与电路大小向无穷大增长时的渐近行为有关。它并没有说明在任何实际的、有限的情况下建造的成本是多少；只是如果上帝与宇宙大小的计算机一起玩，那么他会发现这个结构是“相当有效的”，前提是他首先创造了一个足够大的宇宙来容纳大部分相关的计算机——没有先验测量有多大宇宙必须是理论结果适用。凭经验，我们发现我们操作并提供多项式复杂性的大多数普通算法“有点快”，但这主要是因为这些算法非常简单；没有证据甚至暗示文章中描述的结构将是"平凡的"。

功能加密如果可以在合理的 CPU 和 RAM 预算内工作，那么在许多情况下对安全性很有用。例如，想象一个FPS 游戏联网计算机上的对手玩家。为了高效的 3D 渲染，每个玩家的本地机器必须知道地形图和所有对象的当前位置，包括其他玩家，以便它可以决定从本地玩家的角度来看，是否有其他玩家可见（并且必须在屏幕上绘制）或隐藏（例如偷偷地站在墙后，准备投掷手榴弹）——但作弊者会发现实时知道这些位置非常方便。假设每个玩家都可以完全控制他的机器（他有物理访问权限）。通过函数加密，玩家的机器可以根据服务器发送的位置计算渲染（即F函数），而无需自己获取位置。

不幸的是，对于实际应用，我们远没有一个可行的解决方案。必须理解的是，在所有这些结构中，每个电路门都必须映射到 Gentry 的全同态加密方案的一个实例，并且在混淆电路的每个时钟周期，所有门都必须被处理，无论它们是否“活跃”或不在电路中（这是混淆理论上起作用的重要原因：它不会显示活动门，总是使它们都处于活动状态）。本文给出了性能结果：在相当大的 PC 上，我们可以进行几分钟的计算。这适用于混淆电路中的每个门，以及每个时钟周期。

考虑到功能加密的设置，设想的电路中有数百万甚至可能数十亿的门：“混淆电路”必须包括非对称解密和零知识证明的验证。因此，现在我们正在谈论使用目前在地球上运行的所有计算机，所有计算机都在计算上进行协作，并且它们可能会在几个世纪内在运行一个函数加密实例方面取得不可忽视的进展。

这些只是我从文章中看到的估计，但它们应该给你一个数量级。也就是说，信天翁的比喻与现实相去甚远；你宁愿想象一整支致力于银河统治的宇宙飞船。如果它真的飞起来了，尽管官僚主义很重，但它会有巨大的惯性并且相当昂贵。

在继续进行功能加密和不可区分性混淆之前，只需添加对功能加密完全同态加密的更简单解释，因为这样更容易解释。主要取自http://crypto.stanford.edu/craig/easy-fhe.pdf以上是 Craig Gentry（该领域的先驱之一）的一篇论文，他给出了一个非常容易理解的 Alice 示例，其中包含一些数学。

全同态加密

排除数学功能加密完全同态加密是这样的：

假设有一些未加密的数据 - UD。未加密数据有一种加密方式，称为加密数据 - ED。我们在 UD 上执行一些分析/操作（让我们将分析称为函数 F）得到一些未加密的输出 - UO。

功能加密提出/回答的问题是 - 可以对加密数据 ED 运行分析/操作函数 F，并获得相应的加密输出 - EO，例如，如果解密 EO，可以获得上面定义的未加密输出- 你好？

一个简单的图表（过程 1 应该给出与过程 2 相同的输出）：

1. Unencrypted Data UD -> 通过一些分析函数 F -> 给出 Unencrypted Output UO。

2. a) 未加密数据 UD -> 加密算法 -> 加密数据 ED [此过程在受信任的环境中]

   b) 将 ED 转移到任何地方。-> 对 ED 执行分析函数 F -> 获取 EO（加密输出）。[可以在任何地方完成，包括不受信任的环境，比如云]

   c) 获取 EO。-> 解密算法 -> 获取 UO（未加密输出）[在受信任的环境中]

位级别的工作方案只需要支持 ADD、SUBTRACT 和 MULTIPLY，如上述论文中所述。如果它在位级别工作，它通常可以扩展到所有计算。

作为扩展，给定一般递归，甚至可以对分析函数 F 进行加密，这样即使正在执行的分析对于不受信任的环境也是未知的。

回答下面的评论，因为我没有足够的声誉来发表评论！

在写上面的答案时，你的问题确实让我印象深刻。可能上面的例子有点太简单了，概念有点抽象。

一般来说，明文和密文是一一对应的，以保证解密。

因此，假设有人想在数据中搜索文本“蓝色”。继续上面的例子，假设文本“blue”被加密为“xChd”。因此，对加密数据的功能搜索将搜索“xChd”而不是“blue”。从算法上讲，功能是相同的，即“搜索某些文本”。该函数的各个实例将根据上下文搜索不同的短语。但我再说一遍，这太过分了。

在位级别，只有 ADD（通常称为 OR）、SUBTRACT（NOT 和 OR）和 MULTIPLY（AND） - 如本文所述。否则在位级别我们只有 3 个基本操作 - AND、OR 和 NOT。

当今世界的典型加密涉及生成唯一但随机的比特流，这些比特流与纯文本异或以提供加密文本。在解密中，加密文本与密码进行异或运算以提供纯文本。

因此，作者 (Craig) 和/或其他人试图在位级别实现的是：

1. [AND,OR,NOT 或这些基本操作的任何组合] 对未加密的输入给出一些未加密的输出。

2. 是否有可能开发一种加密方案，这样 [AND，OR，NOT 或这些基本操作的任何组合] 对加密输入给出一些加密输出，这些输出可以被解密以提供与未加密输出相同的输出（ s)。

在文献中，完全同态加密使用所谓的 Evaluate 函数描述如下。

假设如下：

一个。f 是简化为布尔电路 C 的函数（即仅由门和各种输入和输出组成）

湾。密钥对 - pk 是公钥，sk 是密钥

C。UI 和 UO 分别是未加密的输入和输出

d。EI 和 EO 分别是加密的输入和输出。

那么FHE（Fully Homomorphic Encryption）被描述为

Evaluate(pk,C,EI) 给我们 EO 使得 Decrypt(sk, EO) 与在 UI 上运行电路 C 相同。

因此，要在 FHE 中回答您的问题，函数 f 或电路 C 是相同的，因为逻辑或算法必须相同。Evaluate 函数需要公钥，以便它可以将电路 C 中的任何未加密输入/中间体转换为加密形式（例如，如果要搜索“blue”，函数 f 可能在某个位置嵌入了“blue”代码，但需要在加密数据中搜索“xChd”。同样，这是一个非常高级的示例，并不完全对应于位级别，因为在位级别，Evaluate 函数需要独立于电路 C。进一步在位级功能被定义为具有单个输出 - 基本门 AND、OR 和 NOT 都是单个输出。我们在算法和高级语言程序中谈论的普通多输入多输出函数都是从基本门构建的。这里高级类比失败了，Evaluate 函数需要公钥。适合非对称加密公钥/私钥模型——就像我向你发送用我的私钥和一个函数和我的公钥加密的数据一样，FHE 可以总结为——您可以使用我的公钥计算我的加密数据的函数并将加密的输出发送给我）。

功能加密

继续进行功能加密。FE（功能加密）的定义不是很简单或清楚。事实上，有一整篇研究论文致力于正式定义 FE - http://eprint.iacr.org/2010/543.pdf

FE 听起来有点神奇——有点像有人被介绍给公钥/私钥加密。

在 FE 中再次有一个 Master Secret Key - msk，也称为主密钥。有一个Function Key——fk，通常称为skf，secret function key，secret token，secret key（不要与Master Secret Key混淆）。msk/fk 对就像一个私钥/公钥对。

让我们将未加密的输入称为“x”。假设有任何函数 F（或门电路）。假设使用称为 E(x) [Encrypted x] 的 msk 对 x 进行加密。然后，如果我们有功能键 - fk，我们可以仅使用 E(x) 计算 F(x)。请注意，输出 F(x) 未加密。

用数学方法表示 F(x) = Decrpyt(fk, E(x)) 其中 E(x) 是密钥对 msk,fk 的 Encrypt(x,msk)

虽然它可能看起来非常违反直觉，但问题在于 E(x) 的大小或长度是函数 F 大小的函数，并且通常不是线性缩放的。直觉上可以把它想象成函数 F 的算法或逻辑被映射到解密算法上。另请注意，Decrypt(fk, E(x)) 的输出未加密。这样我们就实现了算法的加密！我可以给任何第三方一些加密的输入和一个功能密钥，第三方可以获得对未加密数据运行功能的结果。例如，垃圾邮件过滤器可以确定邮件是否为垃圾邮件，而无需解密电子邮件，也无需知道我的垃圾邮件判定算法是什么。

在上面的 FHE 示例中，可以轻松发起字典攻击，因为未加密数据和加密数据之间存在一对一的对应关系（有些加密方案并不总是为相同的输入生成相同的输出 - 实际上几乎所有广泛使用的 ssl、ssh 等加密方案并不总是为相同的输入生成相同的输出，但我们不会在这里讨论），通常单词可以按出现的顺序排列并且很容易猜到。但是对于FE，什么都猜不到！数据和算法都是安全的！

FE的主要优点是可以为不同的功能生成不同的功能键。我们可以通过适当地分配功能键来让不同的人访问不同的功能。每个人都不需要知道一切[当然如果他们勾结，那就是一个问题]。FE 的一个子类是 ABE（基于属性的加密）。ABE首先被形式化，然后被推广到FE。在 ABE 中，不同的人获得不同级别的信息访问权限。加密信息是公开的。然而，每个人可以解密的信息取决于他们持有的密钥。因此，在完整的产品发布中，可以发布密钥，以便工程人员只能看到图纸，销售人员只能看到最终产品的艺术再现和产品功能的描述，而管理层可以看到一切。http://www.cs.uiuc.edu/class/fa07/cs498mmp/presentations/john.pdf ABE 的最大优势在于，与当前的公钥基础设施相比，它使密钥分发和管理更加容易。

一个非常好的关于 FHE 和 FE 的数学介绍在这里http://outsourcedbits.org/2013/10/06/how-to-search-on-encrypted-data-part-1/在这里http://outsourcedbits .org/2012/06/26/applying-fully-homomorphic-encryption-part-1/

此处探讨了 FE 和 FHE 之间的关系https://www.usukita.org/sites/default/files/func_enc.pdf

然而，FE 的问题在于它只能用于少数功能。它不能用于任何通用或任意功能。这就是Indistinguishability Obfuscation（IO）的用武之地。上面作者对IO的定义是错误的。

不可区分性混淆

根据原始论文（http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf）假设有两个相同功能 F（布尔电路）的实现，即 F1 和 F2。给定 F1 和 F2 的混淆，如果不可能（成功概率可以忽略不计）区分哪个是 F1 的混淆，哪个是 F2 的混淆（哪个混淆是混淆 F1 的结果，哪个混淆是混淆 F2 的结果）。

如上所述 IO 到目前为止，IO 的唯一用途是它被用作实现任何功能的完整通用 FE 的垫脚石。在这里首先实现了完整的 FE - https://eprint.iacr.org/2013/451.pdf 没有“使用 IO 混淆程序”之类的东西。

结论性想法

到目前为止，所有这些发展似乎在实际使用方面甚至在某种程度上在概念上都没有太大的意义，特别是在保护代码和算法方面（与目前保护得很好的数据相反。数据泄露主要通过以下方式发生用于计算它的代码）。撇开实现这些所需的巨大计算资源不谈，上述协议中仍然存在各种安全漏洞，这将使得难以阻止强大的对手。请参阅http://outsourcedbits.org/2013/10/30/how-to-search-on-encrypted-data-part-3/和http://windowsontheory.org/2014/01/14/progress-and- Challenges-in-code-obfuscation-part-ii/保护代码安全的前沿可能是这里描述的东西http://outsourcedbits.org/2013/12/20/how-to-search-on-encrypted-data-part-4-oblivious-rams/