深度详谈 | 超越传统公钥密码：基于身份、属性、函数的新型公钥加密技术探讨

同态科技开放隐私计算 2022-09-24

✪原文作者：Matthew Green

✪原文标题：Beyond public key encryption

✪原文链接：https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/

✪本文导航：

◈ 身份基加密 6%

◈ 身份基加密中的“加密” 37%

◈ 属性基加密 55%

◈ 函数加密 73%

◈ 作者愿景 83%

关于应用密码学最美妙但也令人扼腕的一件事就是我们在现实中实际使用的密码学是多么的少。但这并不代表密码学在业界没有被广泛应用——事实上它的应用很广泛。与之相反，密码学家深耕数十余年所研究出的密码技术，在业界能落地应用使用的却少之又少。

实际上，除少数个别情况，我们现今使用的绝大部分密码学技术仍然是在 21 世纪初 ^[1] 就已经存在的技术。

今天，就让我们从最基础的公钥加密技术展开，具体讨论在过去二十年里大多数人并不熟知的密码学技术，其中任何一个都可以帮助我们走出对传统公钥加密概念的局限。

这虽然是一篇技术文章，但相比于困难的数学内容，重点在于解释这些新方案的作用——以及它们如何在实践中可以如何发挥作用。对于涉及方案的一些实际定义，文中会提供一些原论文的链接与背景知识的参考资料。

身份基加密
在发明公钥密码之前，所有密码学都涉及到密钥。而处理密钥是一个累赘而繁琐的工作。在您可以安全地进行通信之前，您需要与合作伙伴交换密钥。这个过程充满了困难，并且随着通信规模的增大变得难以运作。公钥加密（由 Diffie-Hellman 和 Shamir 的 RSA 密码发展而来）通过简化密钥分发过程极大地革新了密码学。用户现在只需将他们的公钥发送给其他使用者，而无需共享密钥。这把公钥的接收者可以对给你的信息进行加密（或者验证你的数字签名），但它不能用于执行相应的解密（或签名生成）操作，这一部分要通过您自己保留的私钥完成。尽管公钥的使用改进了密码学应用的许多方面，它也带来了一系列新的挑战。从实践中的情况来看，拥有公钥往往只是成功的一半——人们通常还需要安全地分发这些公钥。

举一个例子，假设我想向你发送一封 PGP 加密的电子邮件。在此之前，我需要获取你的公钥的副本。我要怎么获得呢？显然，我们可以亲自见面，然后当面交换密钥——但没人会愿意这样做。

以电子方式获取公钥会更加理想。实际上，这意味着（1）双方必须通过电子邮件交换公钥（2）其中一方必须从第三个基础设施（例如网站或密钥服务器）获取密钥。

在这种情况下，往往会面临这样的问题：

01 Alice需要将公钥同步给Bob

假设该电子邮件或密钥服务器不可信（或者说，它允许任何人以Alice的名义上传密钥）。

02 Bob下载了一把恶意密钥

Bob错误下载了由Mallory生成的一把恶意密钥，此处的Mallory理解为双方之间的中间人或攻击者。

03Bob将消息误发给Mallory

当Bob后续准备使用密钥向Alice发送加密消息时，实际上是Bob在将所以消息加密发送给 Mallory。

为了解决这个问题，即如何交换公钥和验证它们的来源——已经存在大量的实践密码工程进行研究探索，包括整个web PKI（网络公钥基础设施）。在大多数情况下，这些系统都非常奏效。但Adi Shamir并不满足。在 20 世纪 80 年代中期，Adi Shamir 提出了一个全新的“摒弃公钥”的想法。更具体一些，他想问的其实是：
是否有更好的技术可以替换传统的公钥？

Shamir提出的是一种新的公钥密码形式，在这个方案中，用户的“公钥”就是他们的身份，包括名字（例如“Matt Green”）或是电子邮箱地址这样更准确的信息。实际上，这并不重要。重要的是公钥可以是一个任意的字符串——而不是像“7cN5K4pspQy3ExZV43F6pQ6nEKiQVg6sBkYPg1FG56Not”这样的一大堆无意义的字符。当然，使用任意字符串作为公钥会引发一个严重的问题！在实际环境中，有意义的身份作为公钥听起来很棒，但很多场景下均存在限制。- 如果公钥是“Matt Green”，那对应的私钥如何获取？
- 如果能获取到私钥，如何阻止其他同样叫 Matt Green 的人获得同样的私钥，进而误读或误发消息？
- 如何设置权限以阻止非 Matt Green 的人获取私钥？

可以发现，在提高密钥可读性的同时，保障其安全性，是很难的一件事。

因此，Shamir的想法需要更多细节佐证，相比期望身份可以全世界范围使用，他提出了一个称为“密钥生成机构”的特殊服务器，该服务器负责生成私钥。在设置时，该机构将生成一个主公钥 (MPK)，并将其发布给全世界。如果你想加密一条消息并发送给“Matt Green”（或验证我的签名），那么你可以用我的身份和我们达成一致的密钥机构的 MPK 来执行此操作。那么，要解密该消息（或制作签名），我需要访问同一个密钥机构，然后请求一份我的密钥副本。此时，密钥机构将根据主私钥 (MSK) 计算我的密钥，并将其保密。

指定所有算法和参与者后，整个系统如下所示：

▲ 身份基加密 (IBE) 系统概览：密钥生成机构的 Setup 算法生成主公钥 (MPK) 和主密钥 (MSK)。该机构可以使用 Extract 算法导出与特定 ID 对应的密钥。加密器（图左）仅使用身份和 MPK 来加密。消息的接受者请求对应她身份的私钥，然后用这个私钥解密。（图标来自 Eugen Belyakoff ）

这种设计的优点和缺点都很明显。

从优点来说，它完全不需要发送消息方与接收消息方进行任何的密钥交换。一旦发送方选定了一个主密钥授权机构（并下载了它的 MPK），就可以加密消息发给世界上的任何一个人。甚至接收方不需要提前联系密钥机构。可以在发送消息之后，再去获得私钥。

当然，这个“特性”也是一个bug。因为密钥机构生成所有的私钥，所以它拥有非常大的权力。那么，一个不可信的机构可以轻易地生成你的私钥并解密消息。更恰当地表述，是标准的 IBE 系统有效“融入”了密钥托管机制 ^[2] 。

身份基加密中的 “加密”

Shamir 在他上述 1984 年的论文中阐述了这些想法以及额外的一些思考。但当时的Shamir 只能解决其中一半的问题。具体来说，Shamir 提出了一种基于身份的签名（IBS）方案——一个公共验证密钥为一个身份、而签名密钥由密钥机构生成的签名方案。但尽他所能，他无法找到一个构建基于身份的加密（IBE）问题的解决方案。这成为一个悬而未决的问题 ^[3]。

▲ 论文中提出的IBS方案

直到十六年之后，终于有研究学者解决了 Shamir 的问题，提出了IBE的解决方案。
IBE 的第一个，且最负盛名的实现是由 Dan Boneh 和 Matthew Franklin 在多年后—— 在2001 年开发的。Boneh 和Franklin发现的时机非常有意义。Boneh-Franklin 方案从根本上依赖于支持有效“双线性映射”（或“配对”）的椭圆曲线 ^[4]。而计算此类配对所需的算法在 Shamir 撰写论文时并不为人所知，也没有被建设性地使用过——即不仅作为一种攻击手段而是作为一种有效的密码技术。
2003 年左右，由 Sakai 和 Kasahara 提出的SK-IBE方案的情况也同样利用双线性映射，并且通过采用基于指数逆（exponent-inversion）的新密钥提取方法提高了算法的性能。（有关 Boneh-Franklin IBE 方案的简要教程，请参阅https://blog.cryptographyengineering.com/boneh-franklin-ibe/）IBE 的第三个实现虽不如前二者高效，但更令人吃惊。该方案由英国 GCHQ（国家通信总局）的高级密码学家 Clifford Cocks 开发。值得注意的原因有两个。首先，Cocks 的 IBE 方案完全不需要用到双线性映射——它基于更古老的 RSA 设置，这意味着原则上这个算法这么多年来仅仅是没有被人们发现（而非在等待相应的理论基础）。其次，Cocks 本人最近因更令人惊讶的事情而闻名：发现 RSA 密码系统（即公钥加密算法），比 RSA 早了将近 5 年。以公钥密码学的第二次重大进步来结束这一成就，实属令人印象深刻的创举。
自 2001 年以来，也有许多额外的 IBE 结构涌现出来，其中也用到了各种的密码学背景知识。尽管如此，Boneh 和 Franklin 的早期方案仍然是其中最为简单和有效的。
即使对 IBE 本身的技术原理不感兴趣，但事实证明，这个原语（primitive）对于密码学家来说在许多除了简单加密之外的领域都非常有用。

如果我们把 IBE 视为是一种由单一的主公/私钥对来产生数以亿计的相关密钥对的方式，会更显得意义非凡。这使得它对于阻止选定密文攻击（CCA）、设计前向安全公钥加密和短签名方案等各种应用非常有用。

属性基加密
如果单独给密码学家一个类似 IBE 的密码工具，他们要做的第一件事就是找到一种让事情变得更复杂的方法来改进它。那么回顾历史，最大的改进之一要归功于 Sahai 和 Waters。他们提出的方案也被称为属性基加密（Attribute-Based Encryption），或 ABE。这个想法的最初并不是用属性来加密。相反，Sahai 和 Waters 正试图开发一种使用生物识别技术的基于身份的加密方案。为了更好理解这个问题，可以想象为加密方决定使用你的虹膜扫描影像的生物特征作为“身份”来加密一条发给你的消息。稍后，你需要向选为机构索要一个对应你自己的虹膜扫描的解密私钥——如果一切匹配，你就能够解密该消息。
问题在于这很难奏效。生物辨识特征的读取（比如虹膜扫描或者指纹模板）本就是容易出错的。这意味着每次扫描虽然结果会非常接近，但总是出现几个对不上的位。在标准的 IBE 系统中这是灾难性的：哪怕加密使用的身份和你的密钥身份只有一位不同，解密都会失效。Sahai 和 Waters 决定通过开发一种包含“门槛”的 IBE 来解决这个问题。在这个方案中，一个身份的每一个字节都被表示为一个不同的“属性”。把每一个属性视为是你用于加密的一个组件——譬如“虹膜扫描的第 5 位是 1”和“虹膜扫描的第 23 位是 0”。加密方罗列出所有这些字节，并在每个字节下进行加密。权威机构生成的解密密钥也嵌入了类似的字节值列表。该方案被定义为，当且仅当（你的密钥和密文之间）匹配属性的数量超过某个预定义的阈值时，才能顺利解密：例如，2048 个字节中的（至少） 2024 个必须相同才能解密。

这个想法的美妙之处不在于模糊 IBE，而在于一旦你有了一个门槛（即阈值）和“属性”的概念，你就能做更多有趣的事情。主要的观察结论是该门槛可用于实现布尔逻辑的 AND 门和 OR 门，如下所示：

甚至，你还可以将这些逻辑闸门堆叠起来，以表现一个相当复杂的布尔表达式——该表达式本身就用于判定你的密文在什么条件下可以被解密。举个例子，考虑一组更为现实的属性，你可以加密一份医疗记录，以便医院的儿科医生或者保险理算员都可以读取它。你所需要做的只不过是保证人们收到正确描述他们属性的密钥（只要是任意字符串，如同身份那样）。▲ 此处为一个简单的“密文策略”。其中，当且仅当密钥与一组特定的属性匹配时，密文才能被解密。在这种情况中，密钥满足该公式，因此密文被解密，而其余用不到的属性将被忽略掉。

其他的条件判断也能实现。基于一个很长的属性列表，例如创建时间、文件名，甚至是文件创建位置的 GPS 坐标，来加密密文。然后，你可以让权威机构分发与你的数据集非常精确对应的密钥——例如，“此密钥可以解密 11 月 3 日至 12 月 12 日期间在芝加哥加密的任何带有‘儿科’或‘肿瘤学’标签的放射学文件 ”。

函数加密

一旦拥有了像 IBE 和 ABE 这样的相关原语（基础工具），研究人员的本能就是去进行扩展和归纳。

- 为什么要止步于在简单的布尔公式？
- 是否可以开发嵌入任意计算机程序的密钥（或密文）？事实证明，答案是肯定的——尽管效率不是很高。最近的一组研究表明，可以使用各种基于格的密码假设来构建适用于任意多项式大小线路的 ABE。所以这一方向毫无疑问有很大的发展潜力。
这种潜力激发了研究人员将上述所有想法归纳到单独一类称为“函数加密”（或功能加密）的加密类别中。函数加密更多是一种抽象的概念而没有具体所指——它只是将所有这些系统视为特定类的实例的一种方式。基本思想是将解密过程表示为一种用于计算任意函数F的算法，该算法依赖于（1）明文和（2）嵌入密钥中的数据。此函数约是长这样的：
输出= F(密钥数据, 明文数据)在该模型中，IBE 可以通过加密算法加密（身份，明文）并定义函数 F 来表示，如果“密钥输入 == 身份”，则输出对应明文，否则输出空字符串。类似地，ABE 可以用稍微复杂一点的函数来表示。遵循这一范式，我们可以展望在将来，各种有趣的功能都可以由计算不同的函数得到，并在未来的方案中被实现。

作者愿景
对Matthew来说，重点不过是想表明密码学可以做一些非常了不起的事情。当谈及工业和“应用”密码学时，我们很少在日常应用中看到这些技术，但它们一直在等待被广泛应用的那一天。也许完美的应用就在那里。总有一天你会找到它。

注释：

[1] 最初在这片博文里我写的是 “20 世纪 90 年代中期”。在评论中，Tom Ristenpart 对此提出质疑，并指出许多重要的发展都在此之后发生。所以我将日期提前了大约五年，我也正在考虑如何更好的表达这一点。

[2] 还有一种中间形式的加密，称为“无证书加密”。这个想法由 Al-Riyami 和 Paterson 提出，结合了标准公钥加密和 IBE。其基本思想是使用传统公钥（由接收者生成）和 IBE 身份来共同加密每条消息。然后，接收者必须从 IBE 机构获取私钥的副本才能解密。这里的优点是双重的：（1）IBE 密钥机构不能自己解密消息，因为它没有相应的密钥，这解决了“托管”问题。并且 (2) 发送者不需要验证公钥是否真的属于发送者（例如，通过检查证书），因为 IBE 部分可以防止冒名顶替者解密生成的消息。不幸的是，这个系统比 IBE 更像是传统的公钥密码学，并且没有 IBE 的简洁的可用性特性。[3] 开发 IBE 的部分挑战是需要建立一个安全的系统，以防止不同密钥持有者之间的“串通”。譬如，想象一个非常简单只有 2 位标识的身份验证系统。这给出了四种可能的身份：“00”、“01”、“10”、“11”。如果我给你一个身份“01”的密钥，给 Bob 一个“10”的密钥，我们需要确保你们两个不会合谋生成对应“00”和“11”身份的密钥。许多早期提出的解决方案试图通过以各种方式将标准公共加密密钥粘合在一起来解决这个问题（例如，通过为身份的每一位提供单独的公共密钥并将密钥作为单个“密钥”提供）。然而，当只有少数用户串通（或他们的密钥被盗）时，这些系统往往会发生灾难性的失败。解决勾结问题是真正的 IBE 与其虚假表亲的根本区别。[4] Boneh 和 Franklin 方案的完整描述可以在https://en.wikipedia.org/wiki/Boneh-Franklin_scheme看到，或者在他们的原论文中。

来源：本文来自同态科技。

END

往期推荐:

隐私计算头条周刊（5.22-5.28）

怎么评定隐私计算技术本身的安全？首个“隐私计算安全需求”国际标准立项

Gartner:2025年60%的大型企业机构将使用隐私增强计算技术

超“硬核”隐私计算编年史

开放隐私计算社区征稿啦！