段亦涛（有道首席科学家）

本文是基于作者最近发表于CCSＷ’14的一篇论文，Distributed Key Generation for Encrypted Deduplication:Achieving the Strongest Privacy，简要介绍云存储系统中支持数据去重的加密算法的最新进展。论文的DOI是

为了描述方便，本文采用了和论文中完全一致的参考文献标号。读者可去论文中直接参阅。

1. 背景

大规模云存储系统往往面临两个矛盾的需求：一方面系统需要压缩数据以节省存储空间的开销；另一方面，用户出于数据安全和隐私的考虑，希望自己的数据加密存储。目前数据压缩非常有效也是很常用的一个手段是去重（deduplication），即识别数据中冗余的数据块，只存储一份，其余位置存储类似指针的数据结构。研究表明，基于数据分布的不同，有效的去重能够节省高达50%甚至90%的存储空间和带宽 [32, 17, 27, 21]。去重已经被广泛用于很多商业化的系统如 Dropbox [3]，EMC [36]，等等。许多Peer-to-Peer (P2P) 系统也使用同样的技术来节省存储空间 [52, 53, 5, 6].

但是去重却是和数据加密的目标直接相矛盾的。为什么这么说呢呢？这是由于加密本身的性质和目标造成的。人类使用加密手段来保护数据的安全已经有上千年的历史了，最早的密码可以追溯到公元前1900年的埃及古王国时期。近代，尤其是两次世界大战中各方的斗法极大地推动了密码学的发展。步入计算机时代，密码学更是如虎添翼。90年代兴起的互联网，特别是迅猛发展电子商务，既对密码技术提出了更高的需求（从而进一步推动了它的发展），也使得密码技术应用到人们生活的各个方面。今天，从网上银行到在线购物，从电子邮件到社交网络甚至游戏，密码技术无处不在。

然而，人们对密码安全性的认识却是直到80年代才有了实质性的进展。在此之前，人们对密码安全性的目标缺乏严格的定义，从而缺乏对其度量的尺度。一个加密算法到底怎样才算是安全的？这个貌似简单的问题其实需要非常深刻的对密码本质的思考。加密算法不是孤立地，它会被使用在不同的环境和条件下。密码学家期望能够对加密算法的性质做出精确的刻画和严格的证明，从而避免在数据安全上出现百密一疏的漏洞。这一点非常不容易做到，它不仅仅取决于人们对密码本质的理解，还依赖相关学科（例如信息论等）的发展。

1.1 Information-theoretic Security

1949年，信息论的创始人Claude Shannon从信息论的角度考察密文所泄露的关于原文的信息，提出了information-theoretic security的概念。

简单地讲，一个具有information-theoretic security的加密算法所产生的密文对于一个没有相应秘钥的人来说，不含有任何关于原文的信息。

这一性质的后果是，即使对手拥有无限的计算能力和时间，也不可能破译。这显然是一个极强的概念，但是在实际中很难使用，因为它要求使用和原文长度一样的随机秘钥，并且每一个秘钥只能使用一次。满足这种性质的加密算法只有一种，就是One-time pad（OTP）。

现实中OTP是不可能实用的，人们很难安全地分发和原文长度一样的秘钥。于是人们退而追求computational secrecy。即，我们假设对手的计算能力是有限的，我们的加密算法只要做到对手在可行的时间内无法破译就可以认为是安全的。在这种模式下，我们需要一个新的方式来度量密文所泄露的信息。

1.2 Semantic Security

1982年，当时还正在UC Berkeley读研究生的Shafi Goldwasser和Silvio Micali [39] 提出了semantic security的概念。
这一概念的阐述可以基于比较两个事件的概率：

1. 给定一个密文，和原文的长度，一个polynomial-time的对手从中算出关于原文的任何部分信息（如原文是奇数还是偶数）；
2. 只基于原文的长度（没有密文），任何一个polynomial-time算法从中算出关于原文的任何部分信息。

如果1和2的概率足够接近，则该加密算法被认为满足semantic security。我们试着来理解一下这个定义。在1的情况，对手拿到密文和原文的长度，在2的情况下，对手只拿到原文的长度，完全没有密文。如果这两个情况下对手成功获得原文信息的概率接近的话，说明该加密算法产生的密文不足以使之从中获取任何关于原文的信息，因为有它和没它差别不大。这显然是一个安全的状态。

稍后Goldwasser和Micali又给出了一个基于密文不可区分性，即ciphertext indistinguishability (IND) [40]，的等价定义。IND的意思是，给定从两个原文m0和m1中随机选择一个进行加密后产生的密文，对手不能区分加密的是哪一个。后者因为更容易使用而被广泛采纳。

这是一个里程碑性的工作，它赋予安全性明确严格的数学定义，使得密码的设计和分析都有了明确的方向，它的意义是如何强调也不过分的。正如ACM对两位的评价，他们的工作“helped make cryptography a precise science。”部分由于他们的这一开拓性的工作，两位作者在30年后（2013年）获得图灵奖（ACM Turing Award）。

2. 云存储系统中的去重与加密

回到云存储的应用中来，云存储系统中使用支持去重的加密问题的主要挑战有两点：

1. 加密之后的密文需要保留原文的冗余，即原文相同的数据块加密后的密文仍相同（这里的相同不一定是密文的全等，系统只要一种识别包含相同内容的密文的手段即可），这样去重才能够起作用。
2. Cross-user decryption （CUD），即由某个用户加密上传的数据块应该能够被所有有读取权限的用户解密，即使后者不是最初的上传和加密者。

2可以用“lockbox”或者key encapsulation 的方式解决 [22, 45, 29]，在此不再赘述。而1所需的特性我们称之为convergent特性，它是基于去重的数据压缩不可或缺的。但是，它与加密算法的安全性定义有不可调和的矛盾。Semantic security明确禁止原文相等性的检测，即给定两个密文，不应该能够允许对手断定它们加密的是否是同样的数据，否则对手可以利用这一性质攻破前述IND。可以明确断言的是，满足现代加密算法安全性（如semantic security）的所有加密算法都不支持去重。

3. Convergent Encryption （CE）及其安全性

于是退而求其次，即，我们可以适度放宽对安全性的要求，允许密文泄露原文相等性信息，从而使加密后的去重成为可行。最早提出的方案是Convergent Encryption （CE） [27]。它的想法非常简单：一个数据块d的加密如下：

E(h(d), d)

其中E(key, d)是以key做秘钥加密数据d的对称加密算法，h(x)是一个hash function。也就是说， 当需要加密一个数据块d的时候，CE先用数据内容生成key，再用一个symmetric encryption算法（如AES等）加密。

严格地讲，symmetric encryption加密算法本身通常都是randomized或者stateful，即除了key之外，算法本身会生成一些随机数（例如Initialization vector或IV），或者维护一个计数器之类的状态，这样即使多次加密同样的信息也会有不同的结果，目的还是为了获得类似semantic security这样的安全性。这里CE的做法可以理解为h(x)输出的一部分作为key，另外一部分作为算法所需的随机数（如IV）。这样做的结果是，不管是哪个用户加密，同样的数据块一定会被加密成同样的密文，后续可以做去重了。CE已经被广泛应用于很多研究[14, 7]和商业系统中比如Freenet [5], GNUnet [6], flud [4], Ciphertite [2], Bitcasa[1]等。

但是一个令密码学研究者不安的状况是，虽然CE已经被广泛应用，它的安全性却始终没有严格的分析。它显然没有达到semantic security。那么它到底提供一种什么样的保护呢？这种保护是否足够？是否存在很容易的破解方法使得它完全失去作用？在没有解决这些问题的情况下就广泛使用它显然是令人忐忑的。人们曾经做过一些边缘性的工作，比如人们研究过deterministic encryption所能达到的安全性[9, 16, 11]。直到2013年，Mihir Bellare, et al.,  才把这些研究都纳入了Message-Locked Encryption（MLE）的框架 [13]。他们同时提出了PRV$-CDA的安全性概念，并证明了PRV$-CDA比其他相关的安全性都更强。简单地地讲，MLE是这样一种加密算法，它使用的key是从待加密的原文算出来的（key used for encryption is derived from the message itself）。CE是MLE的一个特例。MLE允许原文相等信息的判断（equality checking），从而支持去重。

PRV$-CDA是什么意义呢？PRV$-CDA的命名采用与其他安全性定义相同的惯例：以横线（-）为界，前面是所达到的目标，后面是所承受的攻击。$通常表示随机数据或因素。在PRV$-CDA的例子里，CDA代表chosen-distribution attack，PRV$代表与随机数的不可区分性。简单讲，PRV$-CDA意味着对手不能够将密文同与密文同样长度的随机数区分开来。具体的定义这里不在赘述，感兴趣的读者可参看 [13]。

这是一个相当强的定义。在应用于MLE时，必须对待加密的数据有所限制才能达到。简单讲，数据本身必须有足够大的最小熵(min-entropy)，亦即数据必须是不可预测的，否则达不到PRV$-CDA的安全性。min-entropy是衡量一个随机变量的不可预测性的度量，具体定义可参看相关文献。例如，如果待加密的数据只有“进攻”和“撤退”两个可能的话（数据分布的不可预测性很低），则对手可以很容易地破解一个MLE（只要将所有可能的原文都加密，和欲破解的密文相比即可）。

4. Convergent Encryption的弱点

在MLE的框架下，CE被证明满足PRV$-CDA安全性 [13]。这是一个有重大意义的成果，人们终于能够准确刻画一个已经被广泛使用的技术的安全性了。万事大吉了吗？NO！至少还剩下两个问题：

1. PRV$-CDA安全性对于存储系统来说是否足够强？
2. 是否还有可能获得比PRV$-CDA更强的安全性？

对1，我们的判断是否定的。首先，我们知道，MLE只能保护具有比较高的不可预测性的数据。而在云存储系统的实际使用中，很多用户数据恰恰是可预测。比如说很多公司的文档都有共同的模板和格式，这可能导致有些数据块只可能有很少的取值可能。其次，即使数据的不可预测性很高，对手仍然可以很容易地验证一个信息：判断给定的密文是否加密了一个来自于一个不大的集合的数据。只要将该集合内的所有元素分别加密后与给定密文比较即可。在很多情况下，这一信息可能是非常严重的泄露。例如，云存储的提供商可以很容易判断一个用户的加密数据中是否包括某些受版权保护的电影。

对于第二个问题，最新的研究给出的答案是肯定的。我们的CCSW’14工作指出，所有的CE或MLE，有一个关键的特性是public encryption，即任何一个人，只要拿到数据，就可以生成合法的密文。所有public encryption的MLE的安全都依赖于数据本身的随机性，再加上MLE允许equality checking，这就决定了MLE只能保护具有足够大的min-entropy的数据这一局限性。PRV$-CDA的定义对数据分布做了明确的限制。那么这种局限是否可以突破呢？答案是肯定的。MLE之所以采取public encryption的模式，是考虑到不同的用户需要独立地完成数据加密，并且需要同样的数据产生同样的密文。
完成这一目标还可以采用另外一种server assisted模式。即引入一个第三方的服务，该服务协助用户生成加密所需要的数据（key和IV等），并保证去重所需要的convergent特性。引入一个第三方的服务的好处是，该服务可以使用所有用户都不知道的秘密数据（比如另外一个key）。这就意味着加密过程不再是公开的，从而杜绝前面提到过的问题。DupLESS [12]和我们最新的工作都是这方面的思路。

5. Encryption with Signature（EwS）及其安全性

我们在加密过程中如何引入额外的秘密且同时保证密文的convergent特性呢？和MLE的思路类似，我们需要由数据产生加密的key（从而保证convergent特性），而我们不希望这一个过程是公开的。一个办法是，由第三方服务用自己的秘钥对数据签名（这里签名算法必须是deterministic的），然后用签名作为伪随机数生成器的种子，从而得到一致的加密key。DupLESS [12]和我们的CCSW’14论文都采用这种方法。我们称之为Encryption with Signature（EwS），其过程可以用下图表示：

其中H和G都是hash function，Sign是数字签名算法（如RSA），SK是Sign所需要的秘钥，它由第三方服务掌握，或者用secret sharing的方式分布式地存储于各个用户。SE是一个symmetric encryption算法（如AES）。也就是说，EwS先对数据进行签名，然后用签名生成加密的key。只要使用的签名算法是deterministic的，则每一个数据块都会被加密成唯一的密文。

那么这种方法获得的安全性是什么样的呢？我们的论文给出了这个问题的答案。我们提出了一个新的安全性概念，称为D-IND$并证明D-IND$-CPA严格强于（strictly stronger than）PRV$-CDA。与PRV$-CDA类似，D-IND$也意味着对手不能够将密文同与密文同样长度的随机数区分开来。但是，D-IND$-CPA不再要求数据的分布具有高的min-entropy，从而可以保护可预测性比较高的数据。我们证明EwS的模式是满足D-IND$-CPA安全性。

为了更好地理解CE和EwS安全性的区别，亦即PRV$-CDA和D-IND$-CPA的区别，我们再来看前面的例子。如果待加密的数据只有“进攻”和“撤退”两个可能的话，则对手可以很容易地破解一个CE。但是如果数据是用EwS的加密的，则这种攻击不再可能，因为对手没有第三方服务用来签名的秘钥。

与DupLESS [12]相比，我们的方案还有一个优势就是它是分布式的。它不需要第三方的服务，可以直接将服务部署在用户中。它巧妙使用了threshold signature这一工具。Threshold signature是一种分布式的数字签名生成技术，它将签名所用的秘钥分布地存储于多个节点，使得任何小于t个节点联合起来，既不能够计算出签名的秘钥，也不能够生成正确的签名。相反任何大于t个节点联合起来就能够生成正确的签名。其中t是一个系统参数。这一特性使得threshold signature既具有更高的安全性，也有更好的容错能力。用在EwS上，签名的秘钥不再有单一个服务器维护，它会分布在所有用户中。当一个用户需要加密时，他向大于t个其他用户发出请求，在足够多的用户的协助下生成签名，再使用EwS方式加密。

我们还证明了，EwS，不论是单机的还是分布式的，仅仅泄露数据相等的信（message equality）。而该信息是目前去重手段所依赖的，这表明EwS是支持去重条件下所能达到的最强的安全性。

6. 结论

综上，存储系统中去重和加密是一对矛盾的需求，要支持去重的话必须降低对加密算法安全性的要求。我们提出了D-IND$的安全性概念并证明了D-IND$强于目前所有的相关安全性定义。同时又证明了D-IND$是支持去重的加密算法所能达到的最强的安全性。那么问题来了，这样的安全性是否足够？特别是，为了支持去重而不得不泄露的数据相等性信息对用户来讲是否可以接受？
如何衡量和控制这种泄露？这些都是后续待研究的问题。