ACM通信

研究突出了

技术视角:初见密码学的圣杯

Daniele Micciancio
ACM通信，2010年3月，第53卷第3期，第96页
10.1145/1666420.1666445
评论

我们都知道如何保护我们的私人数据或最有价值的数据不被未经授权的访问:加密。当一段数据米在密钥下加密K生成密文C = EncK(M)，只有预期的收件人(谁知道相应的秘密解密密钥年代)将能够反转加密功能，并使用解密算法恢复原始明文12月年代(C) = 12月年代(内附K(M)) = M．

今天的加密都是对称的(其中S = K)和公钥版本(其中年代即使是在K)被广泛用于在许多重要和知名的应用程序中实现保密性:网上银行、电子购物和虚拟专用网络只是使用加密的最常见应用程序中的几个，通常作为更大协议的一部分，如用于确保Internet上通信安全的TLS协议。

不过，使用加密技术来保护有价值或敏感的数据可能非常有限和不灵活。一旦数据米是加密的，对应的密文C在很大程度上表现为一个黑盒子:我们对盒子所能做的就是保持它关闭或打开，以便访问和操作数据。

在许多情况下，这可能正是我们想要的。例如，以一个远程存储系统为例，我们希望在其中存储大量文档或数据文件。我们以加密的形式存储数据，当我们想要访问特定的数据片段时，我们检索相应的密文，在我们自己信任的计算机上对其进行本地解密。但是一旦我们超越了简单的数据存储/检索模型，我们就有麻烦了。假设我们希望远程系统提供更复杂的功能，比如能够索引和搜索数据的数据库系统，或者能够回答复杂的关系或半结构化查询。使用标准的加密技术，我们立即面临一个困境:要么不加密地存储数据，向存储/数据库服务提供商透露宝贵或敏感的数据，要么加密数据，使提供商无法对其进行操作。

如果数据是加密的，那么回答一个简单的计数查询(例如，包含某个关键字的记录或文件的数量)通常都需要下载和解密整个数据库内容。

同态加密是一种特殊的加密，它允许对密文进行操作而不解密密文;事实上，连解密密钥都不知道。例如，给定密文C = EncK(M)而且C ' = EncK(M”)，一个加性同态加密方案将允许组合C而且C '获得内附K(M + M”)．这种加密方案在设计复杂的加密协议时非常有用。例如，电子投票方案可能会收集加密的选票C我= EncK(M我）其中每个投票米我是0还是1，然后对它们进行计数以获得加密的结果C = EncK(M1+ . . + Mn）．这将由拥有解密密钥和宣布结果能力的适当机构解密，但整个收集和计数过程将在加密数据上运行，而不使用秘密密钥。(当然，这是一个过于简化的协议，因为在真实的选举方案中必须解决许多其他问题，但它很好地说明了同态加密的潜在用途。)

到目前为止，所有已知的同态加密方案基本上只支持一种基本操作，例如加法。但是完全同态加密(即支持对密文进行任意复杂计算的同态加密)的潜力是显而易见的。在将查询发送到您最喜欢的搜索引擎之前，请考虑对查询进行加密，并在搜索引擎不知道查询内容的情况下接收加密结果。想象一下，在远程计算机集群(如云计算环境中)的大型数据集上运行计算密集型最多的程序，同时对程序、数据和结果进行加密和保密。完全同型加密方案的想法最早是由里维斯特、阿德曼和德图佐斯在20世纪70年代末提出的，但30年来一直是海市蜃楼，是密码学中从未被发现的圣杯。至少在2008年之前，Craig Gentry宣布了一种构建完全同态密码系统的新方法。

在接下来的文章中，Gentry描述了他构建完全同态加密方案的创新方法，这是对密码学和理论计算机科学中这个长期存在的主要问题的第一个可靠的解决方案。虽然在将完全同态加密应用于实际之前还有很多工作要做，但Gentry的工作显然是一个里程碑式的成就。在Gentry的发现之前，密码学研究界的许多成员认为完全同态加密是不可能实现的。现在，大多数密码学家(包括我在内)都相信圣杯的存在。事实上，肯定有好几个，效率或高或低的，都在那里等着被发现。

Gentry对他实现完全同态加密的一般方法进行了非常通俗易懂和令人愉快的描述，以及van Dijik、Gentry、Halevi和Vaikuntanathan最近提出的他的框架的一个可能实例。他非常小心地解释了他在技术上复杂的结果，其中一些源于基于晶格的密码学，使用了一个珠宝商的隐喻故事，她寻求保护她的珍贵材料的安全，同时允许她的员工处理这些材料。

Gentry的同态加密工作确实值得一读。

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。

---

没有发现记录