基于全同态加密的ORAM方案

宋宁宁

(中国电子信息产业集团有限公司第六研究所，北京 100083)

0 引言

大数据时代信息总量以惊人的速度增长[1]，云存储可为用户提供按需、弹性、高效、可扩展、低成本的存储服务。用户将数据存储在云端，这使数据的归属权和管理权分离，在云服务提供商不可信的情况下，用户需要对敏感数据进行加密保证其机密性。用户可以将敏感数据进行加密后将密文传到服务器端进行存储，需要使用时进行下载并用密钥解密，进而得到明文数据，但云端密文数据的检索、处理等可用性受到影响。因此，如何在保证存储安全的同时，实现密文检索是大数据安全存储需要解决的关键问题[2]。

除了保证密文机密性，检索关键词的安全性，本文对密文检索在访问模式方面的安全性提出了新的要求。访问模式指的是用户访问云端数据的模式，包括访问类型是读操作还是写操作、访问概率等信息。通常密文检索算法考虑密文检索中的密文机密性和检索关键词的安全性，忽略访问模式带来的隐私泄露。但是，不完全可信的云端通过长时间地观察用户的访问模式，通过复杂的统计分析获得关于用户查询数据的隐私信息，造成用户的隐私泄露。不经意随机存储机(ORAM)机制[3]能够允许用户对云端进行读操作或写操作，但云端无法对读操作和写操作进行区分，同时云端也无法获取用户对某个密文的访问概率，从而达到保护密文检索访问模式的目的。

现有的ORAM方案主要有平方根方案、分层方案[4]和二叉树方案[5]。其他ORAM实现方案都是基于这三种方案的改进或变形。现有的ORAM方案，数据的加密和解密均在用户端进行，且均没有将数据的加密和解密造成的复杂度放入算法复杂度的计算中。由于数据的加密和解密均在客户端执行，尽管保证了数据的机密性，但是大量的数据加密和解密操作对用户端的计算负载和通信负载造成了巨大的负担，特别是为了实现不经意性，用户和云端存在大量的I/O操作，这会造成效率的降低和资源的浪费，不能够完全发挥云端高性能、分布式的特点。全同态加密[6]可以实现在不对密文数据解密的情况下操作密文数据，对计算后的密文进行解密的结果与直接对明文数据操作的结果一致。因此，本文引入全同态加密算法来构建ORAM，在保证检索安全、访问模式安全的前提下，能够提高云端计算和存储资源的利用率，尽可能地减少用户端负担。

1 密文检索模型

目前，云存储密文检索模型通常由用户和云端两部分组成，检索模型分为初始化阶段和检索执行阶段，用户和云端在初始化和检索这两个阶段相互作用，实现用户的密文检索。在初始化阶段，假设用户有n个文件F={F1,…,Fn}。在云端不完全可信的情况下，为了保证数据的机密性，用户必须在本地完成对数据的加密。假设加密算法采用对称加密机制AES算法[7]，其对称密钥为k。用户使用密钥k对文件集合F进行加密生成密文集合C={C1,…,Cn}，其中Ci=ENk(Di)。用户将密文集合C={C1,…,Cn}上传至云端，初始化阶段结束。

在初始化阶段，用户在本地将数据加密后再上传至云端，云端没有相应的密钥，因此，基于加密算法的安全性，云端无法获知用户的明文信息内容，从而保证了用户信息的机密性。

在检索阶段，假设用户需要云端查找并返回所有与关键字w相关的加密文件，为了保证检索关键字的安全性，用户使用检索关键字w构建一个安全令牌token，要保证该令牌token不会泄露任何关于关键字w的信息。用户将此令牌上传至云端，云端利用令牌token在加密数据库中找到用户想要的加密文件，并返回给用户。用户接收密文文件并在本地进行解密获得文件明文。

至此，定义了密文检索通用模型，通过模型可以看出，为了保证用户数据的机密性和检索关键字的安全性，模型分别采用了数据加密和构建安全令牌机制。随着信息安全、攻击等信息技术的发展，对密文检索的安全有了更高等级的定义。在对比现有密文检索机制之前，先对密文检索安全进行定义。一个密文检索算法需要具备以下安全属性：

(1)文件密文集合不能够泄露任何关于文件明文集合的信息；

(2)用户生成的令牌token不能泄露任何关于明文关键词w的信息；

(3)密文的检索不能够泄露用户的访问模式[8]。

2 不经意随机存储机(ORAM)模型

一个安全的ORAM模型包括三个算法[9-10]，分别是初始化算法setup，读操作read和写操作write。下面分别定义这三个算法。

(1)setup：初始化算法具体为：首先用户生成一个安全参数1k，一个拥有N个数据文件的RAM集合和原始文件索引i；执行初始化算法后，输出一个密钥K(可以采用对称加密算法或公钥加密算法)，一个经过加密后的ORAM以及密文索引EN(i)。

(2)read：读操作是一个两方协议，在用户和云端同时执行。用户希望获得原始索引为i所对应的RAM文件，用户执行读操作两方协议，输入为密钥K和密文索引EN(i)；与此同时，云端执行读操作两方协议，输入为ORAM。读操作两方协议分别在用户端和云端执行后，用户收到原始索引i对应的元素RAM[i]，同时云端得到重新加密后的ORAM′和⊥，其中⊥为空信息，表示云端无法获知用户读取的经意随机存储机ORAM的具体位置。读操作两方协议总结公式为：

read((K,EN(i)),ORAM)=

(1)

(3)write：写操作同样是一个在用户和云端同时执行的两方协议。用户希望将云端保存的原始索引i对应的数据文件更新为新的文件值v，用户执行写操作两方协议，输入密钥K，索引EN(i)和新的文件值v；同时云端执行写操作两方协议，输入为ORAM。写操作两方协议执行后，用户端得到⊥，同时，云端得到一个更新的ORAM′和⊥，存储在ORAM中的索引为i的元素被更新为值v，用户完成原始索引i对应的数据文件的更新。读操作两方协议总结公式为：

write((K,EN(i),v),ORAM)=

(2)

根据以上定义可以看出，ORAM模型首先利用数据加密和索引加密保证了用户数据的机密性和索引的安全性。用户和云端执行读操作和写操作的两方协议，实现用户对数据的读取、存储或更新，而云端得到的都是一个经过更新后的ORAM′。因此，在云端看来，用户的读操作和写操作是同样的过程，云端无法分辨。此外，云端得到⊥，也就是说云端无法获取用户的读取或写入的数据位置的访问概率。

3 基于全同态加密的不经意随机存储机方案

全同态加密[6]是对同态加密算法的发展和延伸，其最主要的特性是，对密文数据进行一系列的加法操作和乘法操作后经过解密得到的数据，与直接对原文数据进行上述操作得到的数据一样。首先，对全同态加密[6]算法方案由四个多项式时间复杂度的子算法组成FHE=(FKeyGen,FEnc,FDec,FEval)，分别是：全同态密钥生成算法FKeyGen，全同态加密算法FEnc，全同态解密算法FDec和全同态赋值算法FEval。假设，构建全同态加密方案的安全参数为1k，四个子算法定义如下：

(1)全同态加密算法FKeyGen：系统根据用户输入的安全参数1k，生成全同态加密公私钥对(pk,sk)=FKeyGen(1k)。

(2)全同态加密算法FEnc：用户输入数据明文m，使用全同态加密公钥pk进行加密得到相应的密文c=FEnc(pk,m,r)，其中r为随机数，保证使用相同的密钥对相同的明文加密能够得到不同的密文。

(3)全同态解密算法FDec：用户输入数据密文c，使用全同态加密私钥sk进行解密得到相应的明文m=FDec(sk,c)。

(4)全同态赋值算法FEval：用户输入全同态加密公钥pk，n个密文集合c={c1,c2,…,cn}(对应的明文集合为m={m1,m2,…,mn})和一个由加法门和乘法门构成的多入多出的计算电路f，根据用户对密文的操作需来确定计算电路的形式，如fn|1表示输入n个密文经过计算后输出1个密文，fn|n表示输入n个密文经过计算后输出n个密文。运行赋值算法FEval输出计算的密文c′=FEval(c,f,pk)，其中c′是根据原密文集合c={c1,c2,…,cn}和某些参数经过计算电路f计算后得到的新密文集合，且集合元素顺序随机变化。明文集合m和计算后的密文c′满足公式f(m)=FDec(sk,FEval(pk,f,c′))。

通过上述定义可以看出，本文设计的全同态加密算法与传统全同态加密算法在全同态密钥生成算法FKeyGen、全同态加密算法FEnc、全同态解密算法FDec这三个算法上保持一致。对于全同态赋值算法FEval进行了扩展，将传统全同态加密算法的赋值算法FEval定义为一个多入多出的计算电路。为了完成特定的计算功能，用户设计相应的计算电路，实现不解密密文直接对密文进行操作，多对一或者多对多的输入和输出关系。使用全同态加密算法构建ORAM的方法如下：

(1)setup(1k,RAM)：初始化阶段，用户通过计算(pk,sk)=FKeyGen(1k)，生成一个用于全同态加密算法的公私钥对(pk,sk)。用户生成随机数r，并使用公钥pk加密RAM和索引i，可以得到密文数据c=FEnc(pk,RAM,r)和密文索引EN(i)=FEnc(pk,i,r)，输出一个ORAM并上传到云端。

(3)write((K,EN(i),v),ORAM)：写操作，用户使用公钥pk重新加密需要写入的文件的索引i得到EN(i)=FEnc(pk,i,r)，并发送给云端。云端执行全同态赋值算法，输入ORAM，计算cEN(i)=FEval((ORAM,EN(i)),fn|1,pk)，并将cEN(i)返回给用户。用户收到cEN(i)后直接丢弃，然后用户加密待写入的值cv=FHE.encK(v)，并将cv上传至云端，云端再次执行全同态赋值算法ORAM′=FEval((ORAM,cv,EN(i)),fn|1,pk)，其中云端将ORAM′代替原来的ORAM。

4 安全性分析

分析FHE-ORAM方案的检索安全性。在ORAM初始化阶段，用户使用全同态加密对RAM进行加密，向云端发送ORAM时不会泄露任何关于RAM的信息，因此符合密文检索安全定义中(1)的要求。用户在执行读操作和写操作时向云端发送的令牌token为文件索引的加密值ci，不会泄露关于索引i的信息，因此，符合密文检索安全定义的要求。用户在执行读操作和写操作时，运行两次全同态赋值算法，利用全同态加密的性质，直接对密文进行操作。第一次赋值算法使用户从云端获取索引i对应的新密文数据，新密文数据经过全同态加密处理，和ORAM中索引i对应的密文数据在密码学上无法分辨其联系，从而保证云端无法获知用户“读”或“写”的位置。第二次赋值算法用户上传索引i对应的经过重新加密原明文或加密新明文的密文数据，更新整个ORAM。因此，云端同样无法获知用户“读”或“写”的位置。通过读操作和写操作的定义可知，在云端看来，用户的读操作和写操作都是执行两次赋值算法，具体包括返回给用户一个密文、用户上传一个密文以及云端更新整个ORAM这三个过程，云端无法分辨用户的“读”或“写”，从而对用户的访问模式进行了保护，因此符合密文检索安全定义的要求。综上所述，本文设计的基于全同态加密的不经意随机存储机方案满足检索安全的定义。

5 结论

在云服务提供商不完全可信的情况下，为了保护数据的机密性，用户将数据在本地进行加密后传到云端，导致无法灵活地对存储在云端的数据进行查询、更新等操作，云数据可用性较低。现有密文检索机制在保护用户数据、检索关键词安全的基础上实现密文的检索，但是并不能保护密文访问模式隐私安全。本文在研究现有密文检索机制的基础上，构建了基于全同态加密的不经意随机存储机方案，保护用户数据、检索关键词的同时，基于其“不经意”性实现访问模式的隐藏保护。目前全同态方案算法复杂度高，加解密效率相对较低，下一步将研究降低方案的复杂度，提高可用性。