加密去重场景下基于AONT 和NTRU 的密钥更新方案

贾春福，哈冠雄，武少强，陈杭，李瑞琪

（1.南开大学网络空间安全学院，天津 300350；2.天津市网络与数据安全技术重点实验室，天津 300350）

1 引言

云计算的飞速发展让个人和企业都越来越倾向于将数据外包至云服务器存储以节省本地的数据存储和管理开销[1-2]。面对海量的外包数据，如何实现高效的数据存储成为云服务提供商面临的关键问题。数据去重[3-4]是提高存储利用率的有效方法，当收到多份相同的数据副本时，云服务器可通过数据去重仅存储其中的非重复内容以节省存储开销。对用户而言，出于对外包数据的机密性和隐私考虑，更希望能够将数据在本地加密后上传至云服务器，防止自己的数据信息被泄露。然而，在传统的加密算法中，每个用户使用自己的密钥加密数据，不同用户间的相同数据将被加密为不同的密文，云服务器无法进行去重。

为此，文献[5]提出了消息锁加密（MLE,message-locked encryption），其中加密密钥基于数据内容生成，拥有相同数据的用户可生成相同的加密密钥，此特性可用于实现跨用户的加密去重。但MLE 存在拥有相同数据的多个用户共享同一加密密钥的特点，使多用户间的密钥更新缺乏独立性。系统中某一数据所有者进行密钥更新后，其他数据所有者均需同步该更新[6]，这为外包数据的密钥更新带来了困难。密钥更新[7-9]是密钥泄露后有效维持外包数据机密性，以及为外包数据提供有效访问控制[10-11]的重要方法。缺少密钥更新的云存储系统将在密钥泄露后的系统健壮性，以及在外包数据的访问控制变更等方面存在严重不足。

收敛加密[12]（CE,convergent encryption）是MLE 中一个最常用的实例，其以数据的哈希值作为加密密钥。下面以收敛加密为例说明基于MLE 的加密去重系统难以进行密钥更新的原因。假设云服务器存储的某一外包数据为F，加密密钥为数据本身的哈希值H(F)，其中H(⋅)表示哈希函数。当H(F)泄露后，F的数据所有者需要更新加密密钥，防止同时截获密钥H(F)和外包密文CF的敌手获得数据信息。密钥更新的过程如图1 所示，数据所有者首先需要将原密文从云服务器端下载解密得到F；然后选择一个新的哈希函数H′(⋅)作为新的MLE 密钥生成函数，生成新的加密密钥H′(F)，使用新密钥重新加密数据上传至云服务器；最后还需要将H′(⋅)广播至其他全部数据所有者。其他数据所有者同样需要完成下载外包数据，重新计算新MLE 密钥的过程以保证密钥更新后系统仍可进行跨用户数据去重。因此，基于MLE 的加密去重系统的密钥更新过程非常烦琐，并且具有较大的计算和通信开销。

图1 CE 中的密钥更新

针对上述问题，本文提出了一种加密去重场景下基于 AONT 和 NTRU 的密钥更新方案ANRDup，设计了一个全有或全无转换[13-14]（AONT,all-or-nothing transform）的变体以解决多用户数据去重时密钥更新的同步问题，引入了一种基于NTRU 的代理重加密方案[15]以降低密钥更新过程中的系统通信开销和客户端计算开销。ANRDup 利用AONT 将用户数据拆分为用于数据去重的修剪包和用于密钥更新的存根。基于AONT 的全有或全无特性，密钥更新时客户端仅需重加密外包数据的存根部分，而用于数据去重的修剪包可维持不变，这一特性实现了不同用户密钥更新时的独立性，避免了多用户密钥更新时的同步问题。ANRDup中还引入了一种基于NTRU的代理重加密方案，密钥更新时客户端仅需计算并上传一个重加密密钥至云服务器，大大提升了密钥更新的执行效率。本文的主要贡献总结如下。

1) 设计了一个加密去重场景下的AONT 的变体，安全高效地将整体外包数据的密钥更新转换到了体量较小的存根的密钥更新上，解决了基于MLE 的加密去重系统中多用户密钥更新的同步问题。

2) 在密钥更新的过程中引入了一种基于NTRU 的代理重加密方案，将计算量较大的密文转换过程外包至计算能力更强的云服务器完成，可显著降低密钥更新过程中的系统通信开销和客户端计算开销。

3) 分析了ANRDup 的正确性、安全性和效率，并对ANRDup 的原型进行了性能评估。评估结果表明ANRDup 与现有方案[16]相比具有更高的加解密效率，并且显著降低了密钥更新过程中的时间开销。

2 预备知识

2.1 MLE

MLE 是加密去重系统中一个常用的密码原语，其加密密钥基于数据内容生成。这一特性使相同数据对应的MLE 密钥相同，保证了相同数据在加密后可得到相同的密文，便于云服务器检测密文的重复性。MLE 密文需要对应一个数据标签，用于检测数据重复。MLE 一般由以下几种算法组成。

1) KeyGen(M)：MLE 密钥生成算法输入用户数据M，输出其对应的MLE 密钥K。

2) Enc(K,M)：MLE 加密算法输入MLE 密钥K和用户数据M，输出M加密后的密文C。

3) Dec(K,C)：MLE 解密算法输入MLE 密钥K和密文C，输出C解密后的明文M。

4) TagGen(C)：标签生成算法输入密文C，输出其对应的数据标签T。

MLE 中的KeyGen() 和TagGen() 一般使用哈希函数将用户数据和密文映射到体量较小的密钥和标签中，加解密算法则一般使用传统的对称加密算法（如AES）。由于MLE 中的加密密钥是基于数据内容生成而非随机生成，其无法为用户数据提供语义安全。只有在数据不可预测，即敌手无法遍历明文空间的情况下才可保证数据的机密性[17]。

2.2 AONT

AONT 是一个随机加密模式，其特性是只有得到全部密文后才可恢复出数据信息，缺少任一部分的密文都无法正确解密。假设数据M被拆分为{M1,M2,…,Mn}，随机密钥为K。AONT 转换后的前n个包为Ci=Mi⊕EncSE(K,i+1)，其中，i=1,2,3,…,n，EncSE(⋅)表示对称加密算法，⊕表示异或，第n+1个包为Cn+1=K⊕H(C1||C2||…||Cn)。当恢复数据时，解密方必须得到全部n+1个包才能恢复出密钥K=Cn+1⊕H(C1||C2||…||Cn)并解密密文。AONT 的性质类似于一个(n+1,n+1)的秘密共享[18]。除非得到全部n+1个包，否则任何数据信息都无法恢复。

2.3 NTRU

NTRU[19]是一种基于格的密码算法。在众多公钥加密算法中，其加密效率较为出众且可用于构造代理重加密方案。如NTRUReEncrypt[15]就是一种高效的基于NTRU 的代理重加密方案。

这里介绍一些NTRU 中的相关定义和概念。令Φ(x)=xn+1，其中，n为2 的幂次，Φ(x)为分圆多项式。q为一个素数，满足q=1 mod 2n。R为环Z[x]/Φ(x)，Rq=R/qR=Zq[x]/Φ(x)。NTRU 的加密方案定义在环R和Rq上，将Rq中的可逆元素集合定义为，消息空间M设定为环Rp=R/pR，其中，。NTRU 一般由以下几种算法组成。

1) KeyGen()。密钥生成算法从高斯分布中取样f′ 和g，令f=pf′+1，若(fmodq)∉或(gmodq)∉，则重新取样。计算h=pgf-1，输出私钥sk=f和公钥pk=h。

2) Enc(pk,m)。加密算法输入公钥pk 和消息m∈M，从高斯分布中取样噪声多项式s和e，输出密文c=hs+pe+m∈Rq。

3) Dec(sk,c)。解密算法输入私钥sk 和密文c，输出消息m=((skc) modp)∈M。

NTRUReEncrypt 在NTRU 的基础上加入了重加密密钥生成算法ReKeyGen() 和重加密算法ReEnc()，设计了一种基于NTRU 的代理重加密方案，其由以下几种算法组成。

1) KeyGen()。对于用户A来说，密钥生成算法从高斯分布中取样和gA，令fA=+1，若(fAmodq)∉或(gAmodq)∉，则重新取样。计算，输出私钥skA=fA和公钥pkA=hA。

2) ReKeyGen(skA,skB)。重加密密钥生成算法输入用户A的私钥skA和用户B的私钥skB，输出用 户A和B之间的重加密密钥

3) Enc(pkA,m)。加密算法输入公钥pkA和消息m∈M，从高斯分布中取样噪声多项式s和e，输出密文cA=hAs+pe+m∈Rq。

5) Dec(skA,c)。解密算法输入私钥skA和密文cA，输出消息m=((skA cA) modp)∈M。

3 相关工作

3.1 加密去重

针对传统加密算法与数据去重间的矛盾，文献[5]提出了MLE，其使用基于数据内容生成的加密密钥构造确定性加密以实现跨用户的加密去重。但由于MLE 的加密过程缺乏随机性，当用户数据可预测时，易受到敌手的离线字典攻击[17]。为此，DupLESS[17]引入了一个协助客户端生成加密密钥的密钥服务器以构造服务器辅助MLE。DupLESS中的密钥生成需要客户端与密钥服务器交互，敌手无法进行离线字典攻击，并且，系统可通过在密钥服务器端限制与客户端的交互速率防止敌手进行在线字典攻击。但中心化的密钥服务器易成为系统中的单点故障和效率瓶颈。因此，一些现有工作[20-22]设计了无第三方服务器的加密去重方案。但其中的客户端交互过多，并且要求大量客户端在线，难以适用于真实场景。

此外，加密去重系统中的安全问题还包括侧信道攻击[23-24]、所有权欺骗攻击[6,25]、频率分析攻击[26]、故障容错问题[27]和完整性审计[28-29]等。本文关注的主要问题是加密去重系统中的密钥更新问题。

3.2 密钥更新

在加密去重系统存在的众多安全问题当中，密钥更新问题近年来得到了越来越多的关注。现有的密钥更新方案可大致分为对加密密钥的密文进行密钥更新和对外包数据本身进行密钥更新2 类。

3.2.1密钥密文的密钥更新

分层加密是实现加密去重系统中密钥更新的重要方法。客户端首先使用MLE 密钥加密用户数据，然后使用一个用户密钥对MLE 密钥进行加密得到MLE 密钥的密文。密钥更新时仅对密钥的密文进行更新。EDedup[30]利用密钥分层的思想实现密钥更新，系统中的加密密钥可分为段级别和文件级别，其中，段级别密钥用于加密用户数据，而文件级别密钥用于加密段级别密钥。系统通过重加密文件级别密钥来实现密钥更新。文献[31]提出了将用户角色与加密密钥相关联的思路，实现了分层结构下的云数据去重。该方案通过撤销角色树的节点实现密钥更新，主要思路是对密钥分层结构的调整。文献[32]利用策略加密保护MLE 密钥的安全性。在执行密钥更新时，该方案结合公钥加密和身份认证的思想实现密钥密文的重加密。文献[10]使用ElGamal 算法加密对称密钥，密钥更新时通过重新拆分ElGamal 私钥，并将其外包至分布式密钥服务器以防止敌手通过已泄露的密钥破坏数据机密性。

基于分层加密设计的密钥更新方案的特点是系统仅对密钥的密文进行密钥更新。当外层密钥泄露时，方案可保证数据机密性；但当直接加密用户数据的内层密钥泄露后，外包数据的机密性将受到破坏。

3.2.2数据密文的密钥更新

由于对密钥的密文进行密钥更新这一方法具有局限性，一些研究工作开始关注对外包数据本身进行密钥更新。一些可更新块级别消息锁加密（UMLE,updatable block-level message-locked encryption）的相关研究工作[33-34]试图在文件的数据块动态改变时高效地更新MLE 密钥。UMLE 属于对外包数据本身进行密钥更新的方法，但其研究重点主要在于数据内容的变化对于MLE 密钥的影响，而非系统应如何对抗MLE 密钥泄露。因此，在UMLE 中，当敌手得到已泄露的MLE 密钥和外包数据时，系统无法为用户数据提供机密性保证。

REED[16]提出了支持密钥更新的2 种加密去重方案：基本加密方案和增强加密方案，其主要思想是通过使用AONT 将用户数据拆分为修剪包和存根，然后通过对存根进行重加密实现外包数据的密钥更新。该方案实现了外包数据本身的密钥更新，可有效防止得到已泄露密钥的敌手破坏数据机密性。然而，其提出的2 种方案均存在一定的缺陷：在基本加密方案中，一旦MLE 密钥泄露，数据机密性将不能得到保证；增强加密方案为提高安全性需要对用户数据进行2 层加密，这带来了额外的计算开销。此外，在REED 的密钥更新中，存根数据需要由客户端从云服务器端下载、重加密并上传。当存根体量较大或密钥更新频繁时，仍会引起不小的计算和通信开销。

4 系统模型

4.1 应用场景

ANRDup 的应用场景为某一群组的用户（如公司内的全体员工或高校内的各个院系）共同外包数据至云服务器，如图2 所示。用户不完全信任云服务器，将自己的数据加密后外包，防止云服务器窥探其数据隐私。由于使用云存储服务的用户均属于同一群组，其外包数据中很可能会存在大量的重复内容，云服务器可使用去重技术节省存储开销。一旦外包数据的加密密钥泄露，数据所有者可执行密钥更新操作防止同时得到已泄露的加密密钥和外包密文的敌手获取用户数据信息。

图2 应用场景

4.2 系统架构

ANRDup 中包括3 种实体：客户端、密钥服务器和云存储服务器（简称为云服务器）。

客户端：用户通过客户端外包数据至云服务器。客户端将用户数据拆分为数据块，对其进行加密，将密文块上传至云服务器。客户端可在密钥泄露后更新其外包数据的加密密钥。

密钥服务器：为了弥补MLE 难以为可预测数据提供机密性的缺陷，ANRDup 中部署了密钥服务器以实现服务器辅助MLE。客户端生成MLE密钥时需要与密钥服务器交互，MLE 密钥的生成同时基于数据内容与密钥服务器管理的系统主密钥。

云服务器：云服务器可为多个用户提供数据存储和管理服务，并可使用去重技术降低其存储开销。

4.3 敌手模型

本文主要考虑2 类敌手：内部敌手和外部敌手。内部敌手为诚实但好奇的云服务器，可通过外包数据和已泄露的用户私钥试图获取数据信息。外部敌手为系统外的恶意用户，可得到已泄露的MLE 密钥和用户外包数据。

本文的敌手模型基于如下的安全假设。首先，假设客户端与云服务器间的通信基于SSL/TLS 协议，二者在身份认证后进行通信。其次，由于系统可在密钥服务器端设定与客户端的交互速率限制，本文不考虑敌手的在线字典攻击，并且，方案中客户端与密钥服务器间的交互基于不经意的伪随机函数（OPRF,oblivious pseudo-random function），由于OPRF 的安全性已被证明[17]，本文假设密钥服务器无法在密钥生成阶段获取用户的数据信息。

基于上述的敌手模型，ANRDup 主要有以下2 个安全目标。

1) 为用户的外包数据提供机密性，即上述的内部或外部敌手均无法获取用户的数据信息。

2) 为用户的外包数据提供完整性，即客户端从云服务器下载数据后可检测外包数据是否被篡改。

5 方案设计

5.1 设计思想

通过对现有加密去重系统的研究与分析，总结了其进行密钥更新的2 个难点。

1) 在基于MLE 的加密去重系统中，拥有相同数据的多个用户共享同一加密密钥，使当某个数据所有者对其外包数据进行密钥更新时，其他数据所有者必须同步该更新，否则将出现相同数据加密后无法去重的情况。

2) 当需要更新密钥的文件体量较大时，大量数据需要在客户端和云服务器间传输，这将引起较大的通信开销。此外，重加密大体量文件也给计算能力本就相对薄弱的客户端带来了较大的计算开销。

针对第一个难点，本文构造一个适用于加密去重场景下的AONT 的变体来转换用户数据。首先，将原有AONT 中的随机密钥替换为基于数据内容生成的确定性密钥，构造收敛AONT[27]（CAONT,convergent all-or-nothing transform）。拥有相同数据的不同用户可计算得到相同的确定性密钥，因此跨用户间的相同数据经AONT 转换后可得到相同的包数据以便实现加密去重。ANRDup 中的数据加密过程的方案设计如图3 所示，客户端首先将用户文件拆分为数据块{M1,M2,…,Mn}，然后将这些数据块通过AONT 转换为修剪包{tp1,tp2,…,tpn}和存根{st1,st2,…,stn}，其中，修剪包与用户数据大小相同，用于云服务器进行去重处理；存根则需要进一步由NTRU 随机加密后得到密文存根，用于客户端进行密钥更新。由于不同用户的NTRU 密钥不同，云服务器无法对跨用户的密文存根进行去重，但由于其体量较小，不会引起过多的存储开销。

假设t个用户{U1,U2,…,Ut}经加密去重后共享同一密文C。当某个用户Ui进行密钥更新时，其仅需重加密外包数据的存根部分即可，而用于数据去重的修剪包部分维持不变，这维持了跨用户数据去重的特性，其他用户不需要同步Ui的密钥更新，解决了上述的第一个难点。由于AONT 的“全有或全无”特性，解密方缺少密文的存根部分便无法恢复数据信息。因此，系统可通过重加密存根实现整体外包数据的密钥更新。

针对第二个难点，避免密钥更新时体量较大的外包数据在客户端与云服务器间传输以及在客户端完成计算量较大的加解密操作的方法是将密文转换的过程直接外包至云服务器完成。此外，密文转换的过程中需要保证云服务器无法获取用户的数据信息。代理重加密正是实现这一需求的有效方法。由于ANRDup 中使用NTRU 加密存根，密钥更新的过程中可引入基于NTRU 的代理重加密方案NTRUReEncrypt[15]。客户端使用新旧密钥生成一个重加密密钥，将其上传至云服务器，云服务器完成数据的重加密过程，具体的方案设计如图3 所示。云服务器使用该重加密密钥和原存根密文通过重加密过程生成新的存根密文。因此，在整个密钥更新的过程中，系统的通信开销仅为一个重加密密钥，客户端的计算开销仅为生成该重加密密钥，这解决了上述的第二个难点。

图3 方案设计

5.2 方案细节

本节主要介绍ANRDup 中的服务器辅助MLE密钥生成，数据加解密和密钥更新的详细过程。

5.2.1服务器辅助MLE 的密钥生成

在ANRDup 中，客户端加密数据前需要与密钥服务器交互生成MLE密钥，这里使用RSA-OPRF[17]生成MLE 加密密钥。具体过程如下。

1) 密钥服务器生成 RSA 公私钥对{pk=(e,N),sk=d}，将公钥pk 分发至所有客户端，安全存储私钥sk。

2) 客户端计算用户数据的哈希值h，从群中随机选取用于盲化的随机值，计算x=hremodN发送至密钥服务器。

3) 密钥服务器利用私钥对客户端发送的数据签名，得到y=xdmodN。

4) 客户端进行去盲化过程，计算z=yr-1=hdmodN，验证h是否与zemodN相等。若相等，说明该MLE 密钥z有效；否则该密钥无效，需重新生成。

5.2.2数据加密

ANRDup 中AONT 的确定性密钥同时基于数据块内容和服务器辅助MLE 密钥生成，此设计是为了防止出现类似于REED 的基本加密方案中MLE 密钥泄露后数据机密性被破坏的情况。此外，为了在密钥更新中引入基于NTRU 的代理重加密方案，客户端使用NTRU 加密存根。图4 描述了ANRDup 的数据加密流程。

图4 数据加密流程

下面以加密单个数据块M为例详细介绍数据加密过程。假设M对应的服务器辅助MLE 密钥为KM，方案的加密过程如下。

1) 拼接M和KM得到(M||KM)，计算加密密钥Kh=H(M||KM)。

2) 使用Kh加密 (M||KM)得到密文C=EncSE(Kh,(M||KM))，本文的对称加密使用了AES 加密算法。

3) 将密文C拆分为{C1,C2,…,Cn}，其中每份密文均与密钥Kh大小相同。异或n份密文和Kh得到t=C1⊕C2⊕ …⊕Cn⊕Kh。

4) 拼接C和t得到(C||t)，从中截取部分数据（如64 byte）作为存根st，剩余部分作为修剪包tp。

5) 生成NTRU 密钥对(pk,sk)，使用公钥pk 加密存根st 得到Cst=EncNTRU(pk,st)，其 中，EncNTRU(⋅)为NTRU 加密算法。

不同用户上传相同数据块时计算得到的确定性密钥相同，因此得到的修剪包也相同，云服务器可对跨用户上传的修剪包进行数据去重。此外，本文设计的加密方案是一个AONT 的变体，满足计算安全性。除非敌手得到了全部的AONT 包数据或者可暴力猜测出加密密钥，否则其无法得到数据块的任何信息。6.2 节对该问题给出了更详尽的安全分析。

5.2.3数据解密

客户端从云服务器下载数据块M的全部密文（即存根密文Cst和修剪包tp）后，可通过以下步骤完成解密操作以恢复M。

1) 使用 NTRU 私钥sk 解密Cst得到存根st=DecNTRU(sk,Cst)，其中DecNTRU(⋅)为NTRU 解密算法。

2) 拼接tp 和st 得到完整的 AONT 包数据(tp||st)，从中截取与Kh大小相同的字节得到t，将剩余内容作为密文C。

3) 将密文C拆分为{C1,C2,…,Cn}，与t异或得到Kh=C1⊕C2⊕ …⊕Cn⊕t。

4) 利用Kh解密密文C，得到(M||KM)=DecSE(Kh,C)，从中截取得到数据块M，其中，DecSE(⋅)为对称解密算法。

5) 计算(M||KM)的哈希值h=H(M||KM)，比较h和密钥Kh是否相等，若相等则数据完整性未被损坏。否则，数据完整性已被损坏。

5.2.4密钥更新

当NTRU 密钥对泄露时，数据所有者需要对外包数据进行密钥更新，具体过程如下。

1) 假设泄露的密钥对(pkold,skold)，客户端生成新的NTRU 密钥对(pknew,sknew)，输入新旧私钥至重加密密钥生成算法RekeyGen(⋅)，计算得到重加密密钥rkold→new=RekeyGen(skold,sknew)，发送至云服务器。

2) 云服务器输入重加密密钥rkold→new和原密文Cst=EncNTRU(pkold,st)至重加密算法ReEnc(⋅)，输出新密文C'st=ReEnc(rkold→new,Cst)，其中，仅可由sknew解密，而skold失效。

5.3 方案流程

本节详细介绍ANRDup 中客户端的数据上传、数据恢复和密钥更新的详细操作流程。

5.3.1数据上传

假设用户的外包文件为F，客户端首先将其拆分为大量数据块{M}，计算这些数据块的哈希值，基于OPRF[35]与密钥服务器交互得到{M}对应的MLE 密钥{KM}。{M}经AONT 转换后得到存根{st}和修剪包{tp}，客户端将文件F对应的所有存根{st}写入存根文件Fst。然后客户端生成NTRU 密钥对(pk,sk)，对Fst进行NTRU 加密得到密文存根Cst=EncNTRU(pk,Fst)。由于NTRU 中的加密单元为多项式，客户端需要在加密前将存根文件编码为多项式系数，7.2.1 节对编码方式进行了详细介绍。最后，客户端将修剪包{tp}和密文存根Cst上传至云服务器，本地存储NTRU 密钥对(pk,sk)用于解密数据；云服务器存储客户端上传的密文存根和修剪包，并可对跨用户上传的修剪包进行去重。

5.3.2数据恢复

客户端从云服务器下载得到修剪包{tp}和密文存根Cst，使用 NTRU 私钥sk 解密Cst得到Fst=DecNTRU(sk,Cst)，使用{tp}和Fst恢复文件F。若在恢复文件时检测到外包数据已被篡改，则解密操作终止。

5.3.3密钥更新

客户端生成新的NTRU 密钥对(pknew,sknew)，基于原密钥对中的私钥skold和新私钥sknew生成重加密密钥rkold→new，将rkold→new上传至云服务器。云服务器利用原密文存根Cst和重加密密钥rkold→new生成新的密文存根。

6 安全性分析

本节首先分析ANRDup 的正确性，即数据加密或密钥更新后，客户端可正确恢复用户数据。然后，分析了ANRDup 中设计的AONT 的安全性，并基于4.3 节中的敌手模型分析了整体方案的安全性。

6.1 正确性分析

ANRDup 中所使用的对称加密的正确性已被证明，这里基于文献[15]对NTRU 的加解密和重加密过程进行正确性分析，假设客户端加密的存根数据为m。

NTRU加密后得到的密文为c=hs+pe+m∈Rq，解密时计算csk=cf=(hs+pe+m)f=(pgf-1s+pe+m)f=pgs+pef+mfmodp=mfmodp。由于f=1 modp，csk=mf=mmodp∈M，因此，ANRDup中NTRU 的加密部分满足解密正确性。

假设原密文为c=hs+pe+m∈Rq，新私钥为sk ′=f′。NTRU 重加密后得到的密文为c′=crk+pe′=pgf′-1s+peff′-1+mff′-1+pe′ ∈Rq。解密时可使用新私钥sk′ 计算得到c′s k′=pgs+pef+mf+pe′f′=mmodp∈M。因此，ANRDup 中的重加密过程满足解密正确性。

6.2 AONT 的安全性分析

ANRDup 是基于AONT 的全有或全无特性而设计的，全有或全无特性表示只有当得到AONT 转换后的所有包数据（即修剪包和存根）时才可恢复数据信息，缺少任何一部分包数据均无法完成解密。这里以加密单个数据块M为例对ANRDup 中所设计的AONT 的全有或全无特性进行分析，假设M在AONT 转换后可得到n+1份密文C={C1,C2,…,Cn,t}，加密密钥Kh的大小为lk。

定理1若AES 具有选择明文攻击下的不可区分性，则方案中的AONT 具有全有或全无特性。

证明M的密文块共n+1份，假设敌手可得到其中的n份。分2 种情况讨论，第一种即敌手得到了前n份数据{C1,C2,…,Cn}，第二种即敌手得到了t和{C1,C2,…,Cn}中的n-1份。

1) 若敌手得到了CN={C1,C2,…,Cn}，由于CN为AES 密文，若AES 具有选择明文攻击下的不可区分性，敌手无法区分CN 与等长的随机比特串。因此，敌手依据CN 恢复数据信息的概率等于其成功猜测出AES 密钥Kh的概率，为，实现了计算安全性。若密钥长度为128 位（即lk=128），敌手恢复数据信息的概率为1/2128，此概率是可忽略的。

2) 若敌手得到了t和{C1,C2,…,Cn}中的n-1份，由于ANRDup 中的Kh是经{C1,C2,…,Cn}异或后得到t的，这相当于对Kh进行了一次一密，为其提供了信息论安全。缺少{C1,C2,…,Cn}中任何一份的敌手恢复Kh的概率为，同样实现了计算安全性。

6.3 ANRDup 的安全性分析

本节首先针对敌手模型中的内部敌手对ANRDup 进行了形式化的安全证明，将ANRDup的安全性规约到AES 和NTRUReEncrypt[15]等已被证明安全的密码学原语上。证明了若存在内部敌手可攻破ANRDup，则该敌手可成功攻破AES 和NTRUReEncrypt。此外，本节证明了可得到MLE密钥的外部敌手同样无法恢复数据信息，并对方案中外包数据的完整性进行了分析。

定理2若方案中使用的AES和NTRUReEncrypt是密码学安全的，则内部敌手获取用户数据信息的概率是可忽略的。

证明这里通过定义多个不可区分的安全游戏来证明定理 2。Game0模拟了真实场景下的ANRDup 方案，敌手A 模拟了诚实但好奇的内部敌手的行为。若A 赢得Game0的概率优势是可忽略的，则可认为方案中内部敌手获取数据信息的概率是可忽略的。

1) Game0

初始化阶段。挑战者C 生成AES 密钥k和NTRU 密钥对(pk0,sk0)，将公钥pk0发送至敌手A，安全存储sk0和k。假设初始化阶段为e0，挑战阶段为eC，猜测阶段为eG。在每个时段ei开始前，C 生成新的密钥对(pki,ski)，将此前时段ei-1的私钥ski-1发送至A（挑战阶段的私钥skC不会发送给A）。

询问阶段1。在e0≤ei

挑战阶段。在eC中，A 输出2 个等长的挑战明文m0和m1({m0,m1}∉Qm)，C 随机选择b∈R{0,1}，返回mb对应的挑战密文Cb。

询问阶段2。在eC

猜测阶段。在eG中，A 输出b'。如果b=b'，则A 赢得Game0。将A 在Game0中具有的概率优势定义为

2) Game1

与Game0流程相同，区别在于C 返回密文时使用一个与存根密文等长的随机比特串strcst，即C 返回A 询问的消息密文或重加密后的密文为Cm=(tp,strcst)。

3) Game2

与Game1流程相同，区别在于C 返回密文时使用一个与修剪包等长的随机比特串strtp，即C 返回A 询问的消息密文或重加密后的密文为Cm=(strtp,strcst)。

将A 在Gamei中输出b=b'的事件定义为Si，A 在Gamei中可取得的概率优势定义为，其中i∈{0,1,2}。

引理1Pr[S2]=1/2。

在Game2中，A 得到的密文为Cm=(strtp,strcst)，存根与修剪包均为与m无关的随机比特串，A 只能随机输出b'。因此，Pr[S2]=1/2。

引理2若敌手在没有AES 密钥的前提下区分AES 密文与等长的随机比特串的概率为ξA，则|Pr[S1]-Pr[S2]|≤ξA。

在Game1中，密文为Cm=(tp,strcst)。A 区分Game1与Game2的概率将不超过其区分AES 密文tp 与等长的随机比特串strtp的概率ξA。

引理 3若敌手在没有私钥的前提下区分NTRUReEncrypt 中的密文与等长的随机比特串的概率为ξN，则|Pr[S0]-Pr[S1]|≤ξN。

在Game0中，A 可得到密文Cm=(tp,Cst)以及skC外的私钥集合{sk0,…,skC-1,skC,…,skG-1}。在没有skC的前提下，A 区分Game0与Game1的概率将不超过其区分密文Cst与随机比特串strcst的概率ξN。

由以上3 条引理可知，A 赢得Game0的概率优势如式(1)所示。由于ξA和ξN均为可忽略的值，A赢得Game0的概率优势是可忽略的。

定理3得到外包数据和MLE 密钥的外部敌手恢复用户数据信息的概率是可忽略的。

证明外部敌手可同时得到MLE 密钥和外包数据，ANRDup 可实现不可预测的数据块的机密性保证。方案中的加密密钥为Kh=H(M||KM)，鉴于哈希函数中的雪崩效应（输入发生任何微小的改变，都会导致输出的不可区分性改变），除非外部敌手可得到完整的(M||KM)，否则其无法计算得到Kh。因此，外部敌手恢复数据信息的概率等于其暴力猜测密钥Kh的概率，即，此概率是可忽略的。

定理4客户端无法检测数据完整性被损坏的概率是可忽略的。

证明客户端下载解密数据后可得到(M||KM)，其可通过比较H(M||KM)和Kh是否相等来判断数据完整性是否被损坏。由于哈希函数H(⋅) 的抗碰撞性，数据被篡改后仍满足H(M||KM)=Kh的概率是可忽略的。

7 性能分析

本节分别从理论分析与性能评估2 个方面对ANRDup 进行对比分析。

7.1 理论分析

本节从密钥更新中的客户端、服务器计算开销和系统中的通信开销3 个方面对方案的效率进行理论分析，并比较了现有方案与ANRDup 在密钥更新方式上的不同。表1 展示了不同方案在密钥更新中的时间开销，其中lF和lS分别表示整体数据和存根的长度，lRK和lK分别表示重加密密钥和对称密钥的长度，lSig和lAK分别表示方案中使用的签名长度和对称密钥经公钥加密后的密文长度。SE 和SD 分别表示对称加解密的计算开销，AE 和AD 分别表示公钥加解密的计算开销，H和oprf 分别表示哈希函数和OPRF 引起的计算开销，RKG 和RE 表示重加密密钥生成和数据重加密的计算开销。

表1 密钥更新中的开销对比

由表1 可以看出，CE、RCE 和DupLESS 3 个经典的加密去重方案中密钥更新的开销较大，计算和通信开销均与外包数据的长度线性相关。与近年来的几种密钥更新方案[16,30,32]相比，ANRDup 将部分计算开销外包至服务器端，具有更低的客户端计算开销和通信开销。表2 展示了现有方案在密钥更新方式上的不同。虽然文献[30]和文献[32]具有较高的密钥更新效率，但其密钥更新方式属于密钥密文的更新，当直接加密外包数据的密钥泄露时，无法保证用户数据的机密性。因此，只有REED 与ANRDup 实现了高效的数据密文更新，并且由表1 可以看出，与REED 相比，ANRDup 具有更低的客户端计算开销和带宽开销。

表2 密钥更新方式的对比

7.2 系统实现与性能评估

7.2.1系统实现

本文基于开源的REED 代码实现了ANRDup的原型，其中AES 和哈希函数等密码学原语均基于OpenSSL 实现，NTRU 加密则基于NTL 库实现。由于NTRU 的加密单元为多项式，客户端在对存根进行NTRU 加密前需要首先将其编码为多项式系数。编码方式如下：客户端从存根中读取一定数量的比特串，将其编码为ASCⅡ码。由于每个ASCⅡ码占8 位，且NTRU 中的明文空间大小与参数p相关，客户端将每p/8 个字符转换为一个pbit 的整数，然后将其编码为多项式系数。客户端完成编码后，使用NTRU 加密得到存根密文。

此外，本文对开源代码REED 中AONT 的实现进行了优化。为减少AONT 中的比特间操作，方案的原型实现中将待处理数据的每64 bit 分为一组执行运算，这使程序可在64 位的机器上更高效地运行。

7.2.2性能评估

本节分别使用人工数据和真实数据集对ANRDup 的性能进行了评估。实验所使用的机器配备有3.40GHz Inter i7-6700 处理器，3.5 GB RAM，64 位Ubuntu 16.04.1 LTS。所有评估结果均是10次以上程序运行结果的平均值。人工数据包括一些内容随机填充的文件，真实数据集来自FSLhomes，是石溪大学文件系统和存储实验室所收集的包含9 个用户的每日备份的一个数据集，很多加密去重系统[16,26,32]的评估均基于此数据集。本节将7.2.1节中程序优化前后的ANRDup 原型分别命名为ANRDup_Basic 和ANRDup_OP，将REED 中的基本加密和增强加密方案分别命名为REED_Basic 和REED_Enhanced。

1) 人工数据上的评估

这里首先使用人工数据评估ANRDup 在数据加密上传、下载解密和密钥更新3 个方面的性能开销，其中测试文件的大小从1 到1 000 MB，4 种方案的AONT 加解密开销分别如图5(a)和图5(b)所示。不难看出ANRDup_OP 具有最好的AONT 加解密效率。与其他3 种方案相比，ANRDup_OP 分别降低了 45.3%～66.6%的 AONT 加密开销和48.7%～72.5%的AONT 解密开销，其性能提升的主要原因在于方案在AONT 设计上的改进，以及代码实现上的优化。REED_Enhanced 的AONT 加解密效率最低，原因在于其对用户数据进行了2 层加密。ANRDup_Basic 和REED_Basic 的AONT 加解密效率相近。

图5 AONT 时间开销

图6(a)和图6(b)显示了ANRDup 和REED 在加解密存根上的时间开销对比。由于在ANRDup_OP 和ANRDup_Basic 中存根的加解密过程相同，且均是基于NTRU 加密算法实现的，因此统一简称为ANRDup_NTRU。而REED 中的2 种加密方案均是基于AES 加密算法实现的，因此统一简称为REED_AES。由于AES 的加解密速度明显优于NTRU，在加解密存根的时间开销上ANRDup 要高于REED。然而，由于存根的体量较小，其加解密的开销不会对整体的数据加密上传或下载解密产生过大的影响，这一点在图7 中得到了证明。

图6 存根加解密的时间开销

图7 显示了ANRDup 和REED 在整体的数据加解密上的时间开销对比，图7(a)和图7(b)分别对应数据加密和解密的时间开销，其中包括了AONT过程和存根加解密过程中的时间开销。ANRDup_OP 在整体的数据加解密上与其他3 个方案相比分别降低了19.6%～49.4%和37.1%～57.0%的时间开销。ANRDup_Basic 在解密速度上与REED_Basic 相似，加密速度略慢于REED_Basic，但与安全性相同的 REED_Enhanced 相比，ANRDup_Basic 具有更好的加解密效率。整体的数据加解密开销的对比情况充分说明了ANRDup 中NTRU 的引入并未对数据加解密的效率产生过大的影响，主要原因在于由NTRU 加解密的存根体量较小且方案在AONT 的设计和实现上均实现了优化。

图7 整体数据加解密的时间开销

图8(a)和图8(b)比较了ANRDup 与REED 在数据上传下载过程中客户端的时间开销。与图7 相比，图8 中增加了文件分块和数据通信部分的开销，反映了系统真实运行时客户端的时间开销。ANRDup_OP 在数据上传和下载过程中与其他3 种方案相比分别降低了21.3%～22.1%和23.3%～38.8%的时间开销。

图8 上传下载的时间开销

ANRDup 与REED 在性能上最大的差距体现在密钥更新的过程上，这同样也是本方案设计的主要目标。由于2 个版本的ANRDup 的密钥更新开销相同，统一称为ANRDup。出于相同的原因，REED中基本加密和增强加密统一称为REED。2 种方案密钥更新过程中的性能差异主要集中在系统通信开销和客户端的计算开销上。图9 比较了2 种方案在密钥更新过程中的时间开销，REED 中密钥更新的时间开销随文件大小的增加而增长，而ANRDup中的时间开销是几乎恒定的。原因在于在REED 的密钥更新中客户端需要下载密文存根、解密、重加密后上传至云服务器。文件体量越大，其存根的体量也会随之增加。因此，REED 中密钥更新的时间开销与文件大小线性相关，而ANRDup 中的数据重加密过程则外包至云服务器，无论需要密钥更新的文件大小如何，客户端的计算开销都仅为生成一个重加密密钥，系统的通信开销都仅为该重加密密钥的大小，二者均与文件大小无关。

图9 密钥更新的时间开销

2) 真实数据集上的评估

本小节使用真实数据集FSLhomes 对ANRDup的存储效率和加解密性能进行了评估。图10 中的逻辑数据（logical data）表示未经任何加密和去重的原始数据，物理数据（physical data）表示去重后存储在云服务器的修剪包，存根数据（stub data）表示云服务器存储的存根数据。尽管ANRDup 并未对存根数据进行去重，且NTRU 加密后的存根存在一定的密文扩张，但ANRDup 仍具有较高的存储效率。图10(a)比较了ANRDup 和REED 中物理数据和存根数据的总和与逻辑数据的大小关系，可以看出数据去重后2 种方案的存储效率均得到了提高。存储连续29 天的备份数据后，ANRDup 和REED的去重率分别为75.6%和78.8%，其中，去重率定义为物理数据和存根数据的总和除以逻辑数据的比率。由此可以看出，ANRDup 中NTRU 所引起的密文扩张并未对方案整体的存储开销带来过大的影响。图10(b)比较了ANRDup 和REED 中物理数据和存根数据分别所占的存储开销。与物理数据相比，存根数据所占的存储开销比例较低。ANRDup 中存根数据占总存储量（即物理数据和存根数据的总和）的5%，而REED 中该比例为1%。二者间的差异主要来自NTRU 加密算法引起的密文扩张。

图10 存储开销

图11 展示了ANRDup_OP 和与其安全性相同的REED_Enhanced 在真实数据集上的加解密性能。性能测试选择了5 个用户连续6 天的日常备份数据。这6 天中ANRDup_OP 的平均加解密速度分别为73.83 Mbit/s 和57.12 Mbit/s，REED_Enhanced 为58.42 Mbit/s 和43.13 Mbit/s。ANRDup_OP 在真实数据集上的加解密速度比REED_Enhanced 分别提高了20.9%和24.5%。

图11 真实数据集的加解密开销

8 结束语

针对现有加密去重系统的密钥更新过程中存在的困难，提出了基于AONT 和NTRU 的密钥更新方案ANRDup。方案基于AONT 的全有或全无特性实现了不同用户密钥更新时的独立性，解决了基于MLE 的加密去重系统中多用户密钥更新时存在的同步问题。同时，方案在密钥更新中引入了一种基于NTRU 的代理重加密方案降低了系统的通信开销和客户端的计算开销。性能评估表明所提方案具有较高的加解密效率，并且显著降低了密钥更新过程中的时间开销。由于方案使用了第三方的密钥服务器，易产生单点故障和效率瓶颈的问题。后续工作可通过设计基于阈值的分布式密钥服务器以缓解该问题。