同态加密算法的实际应用？

StackOverflow https://stackoverflow.com/questions/1023981

题

密码学领域似乎发生了一些有趣的事情：首先 同态加密 最近出现了方案（解释, H T）。粗略的说就是一种编码方式 x 进入 f(x) 这样你就可以计算 f(x+y) 容易知道 f(x) 和 f(y) 即使你无法轻易恢复 x 和 y （同样对于 f(x*y)).

这种类型的方案有哪些实际应用（一旦其安全性得到确立）？对我来说，它们似乎可以使编写操纵私人数据的算法变得更加容易。

这里有 我的想法:

  1. 电子投票
  2. 检查私有数据的完整性
  3. 是否有机会总体上有助于保护隐私？

例子:我在 A、B、C 银行都有账户。实体 X 想要确认我的总金额超过 1000 美元；它很乐意接受银行 A、B、C 或 D 的对账单，但不幸的是我的任何一个账户中都没有足够的钱。A银行用我的公钥加密了我的500美元的信息；同样，银行B和C分别加密了我有200美元和300美元的信息。他们将这些数据发送给 X，X 将它们添加到某个数字中，我证明该数字实际上加密了 1000 美元（通过使用我的公钥加密 1000 美元并证明结果是相同的）。我已经证明了一些事情但没有透露给 X 我每个账户里有多少钱。

另一个例子:好公民X_1，..., X_n 正在联手选出两名候选人之一，其中一名是喝拿铁的 liberAl 而另一个是 乙持枪爱好者（所有名字均为虚构）。他们决定希望投票以私下方式进行，但速度要快。他们以矢量格式发送选票 (1, vote_A, vote_B, vote_None) 加密发送给选举委员会，选举委员会公开添加它们并以表格形式获取结果 (count, count_A, count_B, count_None). 。检查后 count = count_A + count_B + count_None, ，官员们宣布其中一名候选人获胜，之后法官因某种与电子投票无关的原因宣布选举无效，并在法庭上奋斗了接下来的 10 年，但是，嘿，这无论如何都不是我的问题。

笔记:- 我相信这些特定的例子在 RSA 之前就可以实现，因为它只需要一个操作中的同态性。我们希望通过更多的操作可以得到更加有趣的东西——所以，举一些例子吧！

  • 我特别希望看到包含有机会在实践中使用的代码和/或开发框架的答案，原因是 SO 不是理论计算机科学讨论板。

  • 同态算法，重复下面评论中所说的内容，允许创建一个在不知道数据的情况下管理数据的程序。不幸的是，程序的类型有些有限：你不能拥有 if (x=0) ... 因为 x 是加密的，每一步都很慢（涉及到一些格子）。

有帮助吗？

解决方案

这是黑暗中的狂野镜头：

我们正在考虑保护明文免受对其进行计算的人的侵害。但如果目标是保护明文和算法呢？

以 MRI 机器为例。MRI 机器最昂贵的部分是机器分析磁共振数据的算法。因此，它们受到硬件设备的严格保护，这些硬件设备旨在在允许不受信任的一方（或与此相关的任何人）检查程序之前破坏程序。

如果 MRI 制造商能够集中 MRI 数据计算，那么丢失算法的风险将大大降低。然而，法律禁止他们访问私人患者数据。

所以！同态加密允许在患者数据和算法都受到保护的情况下发生这种情况。“完全”同态加密（即在加密数据上引入环同态）允许对数据进行更高效、更稳健的计算。

其他提示

作为 PKI 极客，如果同态加密函数也是一个非对称密钥系统，那么您在签名领域将拥有一些非常有趣的可能性。签名者可能会对消息进行签名，而收件人则可以重新传输 部分 将消息和密文的相应部分发送给第三方。

用函数表示法来说，那就是：

用户标志：

符号（明文，私钥）=密文

并传输：

发送（明文、密文、证书）

应用程序获取段：

明文 = 所需明文 + 其他明文

并使用类似以下内容计算密文的相同转换：

如果密文::明文则 ??::desiredPlaintext

找到想要的密文

应用程序仅将所需内容转发到外部服务：

发送（所需的明文，所需的密文，证书）

该服务可以验证该消息，就像用户直接发送该消息一样。

这取决于用于压缩明文的哈希算法也是同态的。如果没有的话，这行不通……或者不应用哈希算法。

如果您希望外部服务执行某些操作来响应签名的用户请求，但又不想公开用户发送到该外部服务的所有内容，这可能非常有用。

一个例子是一个简单的包裹订购系统 - 我向一个 Web 应用程序发送购买一组商品的请求。为了超级安全，我签署了一份采购订单，确认我想要（并承诺支付）一些物品，在某个特定日期之前运送到某个特定位置，并附带一些特定的付款信息。现在..Web 应用程序希望发生以下几件事：

  • 财务部门需要向我的账户收费，并开始向我收取付款
  • 库存需要从库存中提取商品，或处理任何缺货问题
  • 运输需要从库存中接收并将物品转移到我的地址

库存或运输部门没有理由知道我如何支付账单。财务部门可能没有理由知道我的送货地址......在每种情况下，desiredPlaintext 和desiredCiphertext 都会发生变化，具体取决于接收者是谁。这在像 Amazon.com 二手书这样的系统中甚至更加有效，在该系统中，我从亚马逊购买的实体与提供商品的实体（二手书卖家）不同。

阅读有关格密码学的论文，它听起来更像是对称密钥系统......这不太有利于签署消息。

关于“永不言败”的概念，我并不是说将其用于隐私应用程序是不合理的。但你可以找到多种从密文到明文的方法，这似乎很麻烦。

恕我直言，同态加密的最大应用是数据挖掘。该算法的使用可以同时解决隐私和趋势发现的问题。例如，假设您的公司在某个 SAS 提供商上托管其销售信息。现在，该提供商可以为您提供复杂的数据挖掘服务，而您不必实际透露您的真实信息。基本上，您可以将数据发送给计算提供商，让他利用他的 CPU 周期代表您进行计算，然后将加密数据发回给您。对于那些希望迁移到基于云的系统但因隐私/知识产权问题而无法这样做的公司来说，这真是太棒了。

另一个潜在的应用程序，在较低和更个人的层面上，是处理各种财务数据。伊利亚的示例扩展可以适用于您的会计师提交纳税申报表，而无需实际查看您的财务信息、信用卡处理等。

然而，我会保持兴奋，直到该方案经过严格测试并被认为是安全的。加密算法有一个臭名昭著的习惯，即第一次测试失败，然后进行修改并重复这个循环，直到获得某些政府机构的“认证”。

您可能有兴趣查看 Bruce Schneier 对同态加密的相当负面的看法：

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

我不知道有多贵 f(x) + f(x) 计算将会是，但也许它可以用作实现加密数据库的一种方式。

您可以存储 100 万行加密的数据 f(x_1), f(x_2), ... f(x_n). 。你可以做

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

首先可以计算出 SUM(f(x)) 然后将其解密为 SUM(x).

有了这个，您可以执行有界深度的任意非递归电路，因此给定对数密钥长度，您可以执行 NC1 算法（基本上是前馈布尔电路）。

那么，你可以如何使用它呢？

让我们看看在一组输入上映射/减少电路和减少方案。

首先是数据：

我们可能不希望客户端必须对我们要搜索的所有数据进行加密，因此可以向服务器提供一个加密的 1 和一个加密的 0，并让它使用环结构构造任意的加密整数对于我们来说，或者我们可以直接将它们用作位。这样服务器就可以提供我们正在搜索的部分或全部数据。对于整数，它可以通过农民算术（double 或 double 并为每个位加 1）来构造它们，对于位，它只提供适当的加密位。

我们可以在设计中混合和匹配布尔值和整数值，通过使用 1 作为 true 和 0 作为 false 评估 cond * then + (1 - cond) * else 来获得 if/then/else（需要评估两个分支 SIMD 样式）条件是，这样你就可以不用使用环的内置算术来使你的电路更浅。

另一方面，我们也可能对一些数据进行了预加密，但由于您必须不断回收相同的密钥集才能使用它，因此要正确执行这一操作变得非常棘手。

所以，现在我们有了服务器提供的数据。现在，加密您不希望服务器知道的内容，例如您正在搜索的内容，并让它们在正确的点将其输入电路中，例如作为地图功能的额外输入。

我们应该能够在每个输入上映射任意类似 NC1 的电路，以提取字段、乘以一些值，然后通常将其映射为可以廉价简化的形式。

然后使用更小的电路减少这些片段，例如具有良好大小限制结果的简单幺半群。（IE。您映射以获得指示是否找到匹配项的位，然后通过使用小型加法器电路对这些位进行计数来减少）

由于您只需要逻辑地构造电路并在同态环中的这些加密位上模拟其执行，因此您可能可以使用小型 DSL 相对快速地实现它，即就像 Haskell 中的 Lava 一样，假设你直接得到了同态加密片段。

另外，请记住，每个门都是 严重地 执行起来昂贵。

所以，总结一下，

  1. 为服务器提供加密的 1 和 0 以及映射和归约函数的任何加密元信息。
  2. 对于每个数据点，将其编码到同态环中，向映射电路提供输入和元信息，以获得适合减少的值。
  3. 在平衡二叉树（或其他平衡排列以最小化树高度）中，将归约操作应用于电路的输出和任何加密的地图元信息。
  4. 将结果交给客户端解密

现有同态加密算法的问题在于，您只能用它执行多对数 (NC1) 电路，这在算法上几乎排除了任何有趣的东西。

另外，编码的复杂性似乎并不比自己执行多对数电路的复杂性低，所以乍一看你并没有获得任何免费的工作，除非你用它做了一些特别棘手的事情。

像 SETI@Home、蛋白质折叠项目等分布式计算相当受欢迎，因为它们利用了数千名用户捐赠的 CPU 时间和电力。更有趣的是，人们可以通过为商业项目提供这些资源来获得报酬。然而，没有一家负责任的公司愿意将其数据发送到数千台匿名计算机进行处理。如果您可以有效地将算法应用于加密数据，则可以将处理委托给没有可信关系的任何人。

电子投票确实是同态加密的实际应用，即 http://heliosvoting.org/

在同态加密的帮助下，一些银行应用程序可能会变得更快。

他们可以在云端对加密数据进行操作，而不是将其从云端转移到本地然后再放到云端。也不需要加密-解密-执行操作-加密管道，加密-执行操作就可以了。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top