32

密码学中似乎发生了一些有趣的事情：最近出现了第一个同态加密方案（解释，HT）。粗略地说，它是一种编码方式，即使您无法轻松恢复xand （对于 也是如此），您也可以轻松f(x)计算。f(x+y)f(x)f(y)xyf(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 正在联手选择两名候选人中的一名，其中一名是喝拿铁的自由人A l，另一名是持圣经的枪支爱好者（所有名字都是虚构的）。他们决定他们希望投票是私密但快速的。他们将投票以(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，而且每一步都很慢（涉及一些格子）。

4

10 回答 10

10

这是黑暗中的狂野镜头：

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

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

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

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

于 2009-07-03T02:15:13.737 回答
4

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

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

但是，在该方案经过严格测试并被认为安全之前，我会保持兴奋。加密算法有一个臭名昭著的习惯，即未能通过第一次测试，进行修订并重复循环，直到它们得到某些政府机构的“认证”。

于 2009-07-04T04:48:36.480 回答
3

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

在函数符号中，这将是：

用户标志：

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

并传输：

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

应用程序获取段：

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

并使用以下方法计算相同的密文转换：

if ciphertext::plaintext then ??::desiredPlaintext

找到想要的密文

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

发送（desiredPlaintext，desiredCiphertext，证书）

并且服务可以验证此消息，就好像用户直接发送了它一样。

这取决于用于压缩明文的哈希算法也是同态的。如果没有，这将不起作用......或者没有应用哈希算法。

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

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

  • 财务需要向我的帐户收费，并开始从我这里获得付款
  • 库存需要从库存中提取物品，或处理任何缺货问题
  • 运输需要从库存中接收并将东西移动到我的地址

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

阅读有关格密码学的论文，听起来更像是一个对称密钥系统……这对签名消息不太有利。

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

于 2009-06-23T21:12:50.307 回答
3

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

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

于 2009-07-09T13:06:22.113 回答
2

我不知道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)。

于 2009-07-04T18:25:27.423 回答
2

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

那么，你怎么能使用它呢？

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

先上数据：

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

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

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

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

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

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

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

另外，请记住，每个门的执行成本都非常高。

所以，总结一下，

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

现有同态加密算法的问题是你只能用它执行一个多对数 (NC1) 电路，这几乎排除了任何有趣的算法。

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

于 2009-06-25T19:45:42.053 回答
1

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

于 2009-07-04T07:33:01.900 回答
1

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

于 2010-09-27T14:36:11.847 回答
-1

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

他们可以在云上使用加密数据执行操作，而不是将其从云传输到本地再放到云上。也不需要加密-解密-执行操作-加密管道，加密-执行操作就可以了。

于 2017-07-06T07:38:21.113 回答