存在哪些部分同态加密实现以及如何利用它们?

信息安全 加密 密码学 云计算 。网 同态加密
2021-08-19 07:47:42

似乎只有部分同态加密(PHE)对于现代(2011)使用是实用的。但是,我很难找到使我能够利用这项技术的库(FOSS 或其他)。

El Gamal 是执行 PHE 的算法的一个示例,但wiki 页面没有清楚地解释支持哪些盲数学运算以及如何实现它们。

潜在用例

PHE 是一种可以抽象使用的东西,可以将数学运算卸载到第 3 位,而无需该方知道潜在价值是什么。例如,可以执行 x+y=z 并且它将具有有效的加密结果,但所有 3 个值都不会以未加密的格式为第三方所知。这有利于保护股票市场分析数据、PII 或任何被视为专有或机密的数据。

问题

那么,存在哪些加密算法以及允许我对加密数据进行操作的库?我感兴趣的操作示例包括

  • 加减
  • 乘法或除法
  • 比较(加密 X 大于加密 Y)
  • 一种技术,可以让我比较单词“Ap”的二进制/加密 ASCII 版本,并使用“Apple”的加密版本执行 Contains() 或 StartsWith()
4个回答

El Gamal加密允许乘法。这发生在 El Gamal 所在的组内;因此,您将数字乘以给定的素数,而不是“普通”整数。如果您可以乘法,则可以除法(一组大小q的求逆是通过提高q-2的幂来完成的,因此这是执行一些乘法的问题)。El Gamal 在libgcrypt中实现(在GnuPG中使用),但您必须自己进行乘法运算(El Gamal 用于 OpenPGP 格式,但不是因为它的同态属性)。

Paillier加密允许添加。再一次,加法发生在一个有限群中(这里,数字模n,一个大的复合整数)。我不知道这个系统在广泛的通用加密库中的实现(尽管我的不知道并不意味着不存在),但是一个简单的谷歌搜索发现了一些基于 Java 的实现(Java 提供了BigInteger,使此类系统的实现变得容易)。

重要的一点是这种加密系统是随机的:对于给定的明文,有许多可能的密文。因此,您无法知道两个密文是否对应相同的明文。更何况,它们不允许比较(有限组内的顺序无论如何都没有明确定义)。请注意,比较方法与安全的非对称加密不兼容:任何人都可以加密选择的值以通过二分搜索来猜测加密数据。一般来说,关键词是“数据挖掘”。对加密数据进行数据挖掘是一个未被广泛探索的领域,子字符串匹配是一种圣杯。简而言之,没有任何东西可以立即适用。

实际使用 PHE(尤其是 El Gamal)的一个例子是Helios Voting有了它,您可以在云端公开存储加密投票选票,还可以让公众将它们加起来以确认每个候选人的票数,并检查他们自己的投票是否确实包含在总数中,而无需收据这可以证明他们是如何投票给第三方的。

它是开源的。您可以在此处获取源代码(基于 Python、JavaScript、Django):

我不知道将 Helios 的各个部分提取到可重复使用的库中是多么容易,但它是一个可以查看的地方。

@Thomas 搞定了。有支持加法的方案和支持乘法的方案(但没有支持两者的实际方案)。没有支持比较的方案,因为这与安全性不兼容。

也有支持检查加密文本是否包含特定关键字的方案(例如,本文),尽管威胁模型和完成的内容有些不同。这些方案面向您自己是上传数据的人,并且您记得加密密钥并且它们专注于只读(或主要读取)数据集的情况。它们还揭示了可用于流量分析的信息(例如,关键字的点击次数及其在加密文件中的位置)。

您可以与这里这里强烈争论其安全性的顺序保持加密方案进行比较。该部分的 II-A 部分还描述了 OPE 的一些弱点