本文是基于作者最近發表于CCSW’14的一篇論文，Distributed Key Generation for Encrypted Deduplication:Achieving the Strongest Privacy，簡要介紹云存儲系統中支持數據去重的加密算法的最新進展。論文的DOI是 http://dx.doi.org/10.1145/2664168.2664169

為了描述方便，本文采用了和論文中完全一致的參考文獻標號。讀者可去論文中直接參閱。

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(只要將所有可能的原文都加密，和欲破解的密文相比即可)。

#p#

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$是支持去重的加密算法所能達到的最強的安全性。那么問題來了，這樣的安全性是否足夠?特別是，為了支持去重而不得不泄露的數據相等性信息對用戶來講是否可以接受?

如何衡量和控制這種泄露?這些都是后續待研究的問題。