近年来云存储技术发展迅猛且应用广泛, 但同时也带来严重的安全问题.出于对云存储环境中个人数据隐私性的保护, 用户会将数据处理成密文形式再存储到远程的云服务器中, 但是这样直接导致无法对加密后的数据进行正常的语义搜索, 可搜索加密(searchable encrypion, SE)机制^[1]可以更好地解决云存储环境中的密文数据搜索问题.

Song等^[2]首次将可搜索加密机制应用于关键字搜索, 通过遍历加密数据库实现了单关键字对称可搜索加密.Dan等^[3]通过双线性映射和陷门置换的方法构建了2个PEKS(public key encryption with keyword search)方案, 首次实现了公钥可搜索加密.随后越来越多的学者研究基于公钥密码学的可搜索加密算法.基于公钥密码学的密文搜索机制大部分构建于双线性配对之上, 其安全性都是基于离散对数问题、判定性Diffie-Hellman问题等不同的困难性假设.而基于双线性映射构建的公钥可搜索加密方案的效率开销远高于对称可搜索加密方案, 致使其在算法和技术上都无法满足现实工作环境的需要.

为了提高搜索效率, Goh等^[4]在可搜索加密方案中引入了安全索引的概念, 服务器通过搜索索引来进行查询, 将搜索复杂度降低为O(n)(n为文件的个数).在后续的研究中, Cao等^[5]、Li等^[6]、Sun等^[7]都是分别设计自己的索引结构来实现基于安全索引的可搜索加密机制, 这种使用个人定义索引的主要缺点是每一个方案的索引结构会与其他方案的不匹配, 数据拥有者需要针对不同方案生成不同的索引结构, 当数据量很大时生成索引的代价较大.因而, 研究者普遍关注一种在文件检索系统中最受欢迎的索引结构——倒排索引.Curtmola等^[8]最先提出一个基于倒排索引的对称可搜索加密方案, 该方案较以往方案在效率上有所提升, 但还存在两个主要限制:一方面是该方案只支持单关键字搜索, 对于现实应用中常用到的多关键字搜索不提供支持; 另一方面是该方案在算法设计中并没有考虑到搜索模式和访问模式的保护问题, 导致一旦关键字被搜索那么倒排索引的位置和内容都会泄露给云服务器.

从上述内容看出, 目前的密文搜索方案大多只支持单关键字搜索, 无法保护搜索模式且效率低下.而实际应用场景中, 用户通常需要进行高效的连接多关键字搜索并且希望搜索隐私得到更好的保护.故针对现有公钥可搜索加密方案效率低下、表达能力弱且安全性不佳的问题, 本文基于同态加密和私有集合交集技术, 提出一种面向多关键字的可搜索加密方案(multi-keyword searchable encryption, MKSE).方案以提高多关键字密文搜索效率为前提, 以保护密文搜索的搜索模式和搜索内容为目标, 围绕多关键字的精确匹配和数据安全性保障问题进行方案设计, 具有重要的理论价值和应用前景.

1 预备知识 1.1 Paillier同态加密

全同态加密^[9]方案允许在不解密的情况下对密文数据进行任意的计算.即给定消息(m₁, …, m_n)的密文, 全同态加密方案能在不解密的情况下计算出f(m₁, …, m_n)的密文, 其中f为任意的可计算函数.

Paillier同态加密方案^[10]是一个基于决定性组合剩余类问题假设的公钥加密方案, 具有加法同态性以及一次乘法同态性, 可表述如下:

1) 加法同态性:给定密文E(a₁), E(a₂), 那么可以通过计算E(a₁+a₂)=E(a₁)E(a₂)得到a₁+a₂的密文;

2) 一次乘法同态性:给定密文E(a₁), 可计算a₁×a₂的密文为E(a₁)^a₂.

1.2 私有集合交集

私有集合交集^[11-12](private set intersection, PSI)是对于集合交集的私有匹配协议, 允许两个或更多实体来秘密地计算他们数据的交集, 并且在计算过程中除了集合交集本身不泄露任何额外信息.

通过采用Paillier同态加密方法构建私有集合交集方案, 可以保留Paillier同态加密方法的加法同态性和一次乘法同态性.根据这两个属性可以得出一个推论:给定一个k阶多项式P的系数a₀, …, a_k的密文, 和一个明文y, 可以直接计算P(y)的密文.

应用这个推论, 构建客户端C和服务器S之间的私有集合交集协议, 其基础结构如下:首先, C定义1个根为他的输入集合元素的多项式P, 之后C将上述多项式系数的密文发送给S.S对自己的每一个集合元素, 都使用加密系统的同态属性来计算该多项式, 然后S使用一个随机数r乘以每一个多项式结果来获得一个中间结果, 最后再加上他的输入集合元素的密文, 也就是说, S计算Enc(r·P(y)+y).对于两方输入的交集中的任何一个元素, Enc(r·P(y)+y)的结果是相应元素的值, 而对于其他不属于两方交集的元素, 结果是随机的.

2 MKSE模型 2.1 MKSE模型的架构

MKSE模型包含三个实体:数据拥有者、用户和云服务器.模型的架构如图 1所示.数据拥有者将本地文件集进行处理, 并上传到云服务器.对文件的处理包括将文件内容处理成密文形式, 以及为其生成安全索引.用户通过关键字进行文件搜索, 首先用户向数据拥有者提交多个搜索关键字, 之后利用数据拥有者返回给他的搜索陷门向云服务器提交搜索请求.云服务器接收到搜索陷门并执行搜索操作, 返回给用户加密的文件标签集合.最后, 用户将加密的文件标签集合发送给数据拥有者解密, 得到搜索关键字对应的文件标签信息.

各个实体的功能介绍如下:

1) 数据拥有者是与数据直接接触的一种特殊的可信赖用户.他负责初始化方案中要使用到的密钥等; 他要对自己的文件集合生成安全索引, 并上传到云服务器; 他接受用户选择的若干个关键字并生成搜索陷门.

2) 用户是数据拥有者授权的可信实体.他选择搜索的关键字并向数据拥有者申请搜索陷门; 他使用该陷门向云服务器发起搜索请求; 他将搜索结果发送给数据拥有者解密, 得到关键字对应的文件标签信息.

3) 由于不希望云服务器获得自身敏感数据, 因而云服务器只提供存储服务并可以根据用户的请求执行特定的搜索操作.

2.2 形式化定义

MKSE由4个算法组成, 形式化定义为:MKSE=(Setup, IndexGen, Trapdoor, Search), 具体描述如下:

1) MK←Setup(k):初始化算法.输入安全参数k, 输出主密钥MK.MK被保存在系统的整个生命周期中, 并与被存储的数据相互独立.

2) ()←IndexGen(MK, I):安全索引生成算法.输入主密钥MK和倒排索引I, 输出安全索引和字典矩阵M′_D.

3) T←Trapdoor(MK, Q):陷门生成算法.输入为主密钥MK和搜索请求Q, 输出搜索陷门T.

4) P_R(x)←Search(, T):搜索算法.输入安全索引和搜索陷门T, 输出一个含有文件标签信息的结果多项式P_R(x).

2.3 安全性定义

首先, 给出MKSE方案的正确性定义.在MKSE方案中, 对于概率多项式次搜索, 算法Search返回对应的搜索结果, 搜索结果为所有包含查询关键字的文件, 则称MKSE方案是正确的.

定理1(正确性)  基于Paillier和PSI的多关键字可搜索加密方案返回所有包含查询关键字的文件.

本文假设数据拥有者使用块加密法如AES来加密文件内容，本文不再对文体本身安全性进行讨论.MKSE方案应提供的隐私性保护包括：

1) 索引隐私.索引隐私的保护是双重的, 首先, 索引应该被加密，使得云服务器不能学习到索引的内容.其次, 通过分析安全索引，云服务器无法推论出关于文件的信息, 包括是否一个文件包含某些关键字以及是否不同的文件包含一个相同的关键字.

2) 陷门隐私.陷门包含加密形式的查询信息, 陷门隐私要求给定一个搜索陷门, 云服务器不能从中学习到任何关于用户查询的信息, 包括查询的内容, 查询的关键字数量以及相同查询是否已经被搜索过.

给定关键字集合Ω和安全索引, 任意概率多项式时间(PPT)敌手A伪造一系列查询, A始终不能区分算法Search返回的搜索结果.下面通过安全性实验来形式化描述该方案的安全性.

Setup:

挑战者C创建一个关键字集合Ω.C从集合Ω对应的文件中挑选出一些子集合构成文件集合Σ.首先挑战者C运行Setup生成密钥, 然后执行IndexGen为Σ生成安全的倒排索引.最后, C将关键字集合Ω和安全索引发布给敌手A.

Queries:

敌手A被允许向挑战者C请求对于查询Q∈Ω的陷门T.A可以在安全索引上使用T执行Search, 从而得到结果P_R.

Challenge:

在某个时刻, 敌手A选择两个非空查询V₀, V₁⊂Ω, 其中V₀-V₁≠ϕ且V₁-V₀≠ϕ.然后将查询请求发送给挑战者C.

在接收到V₀和V₁后, C选择, 然后对V_b生成陷门T_b.允许A使用T_b生成对T_b的搜索结果P_R.

敌手A的挑战就是判断b.挑战被发布后, 敌手A可以继续请求陷门.

Response:

敌手A输出他关于b的猜想b′.

在这个安全性实验中敌手A获胜的优势定义为:Adv_A=|Pr[b=b′]-1/2|.

如果没有多项式时间敌手能够以不可忽略的优势赢得上述的安全性实验, 则方案是语义安全的.

定理2(安全性)  如果方案所基于的加法同态加密方法是语义安全的, 那么基于Paillier和PSI的多关键字可搜索加密方案是语义安全的.

3 MKSE方案 3.1 系统初始化

MK←Setup(k):由数据拥有者执行.首先, 选择2个k-bit的素数p和q, 满足gcd(pq, (p-1)(q-1))=1.计算n=pq, 并选取g∈Ζn2*, 计算modn和λ=lcm(p-1, q-1), 从而得到Paillier同态加密算法的密钥对sk=(λ, μ), pk=(n, g).之后, 把私钥sk、伪随机置换方法f和一个可逆矩阵M作为主密钥MK, 其中矩阵M的度由倒排索引关键字字典d的大小决定.最后将公钥pk发布.

3.2 安全索引生成

()←IndexGen(MK, I):由数据拥有者执行.本文假设, 数据拥有者已经为自己的文件集合Σ构建好了倒排索引I=(I_W1, I_W2, …, I_Wm)^T, 一个倒排索引包括一个关键字字典d和针对每个关键字的文件列表I_Wi.本文不再对构建倒排索引的过程进行赘述.安全索引生成算法的主要工作是将倒排索引加密成安全索引, 算法的具体过程如下:

1) 为每个关键字W_i∈Ω生成标签t_Wi=f(W_i), 同时为每一个文件δ_i∈Σ生成标签t_δi=f(δ_i).定义关键字标签的集合为f(Ω), 文件标签的集合为f(Σ).假设所有文件列表I_Wi的最大长度设置为L, 为I_Wi生成一系列的随机数R_i={r_j}, 其中r_j∈Z_n^*, r_j∉f(Ω), 然后, 将R_i填充到文件列表中.为填充后的文件列表I_Wi生成一个多项式

2) 计算多项式矢量I=(P_W1, P_W2, …, P_Wm)^T.

3) 用多项式P_Wi本身的系数(a_L, …, a₁, a₀)来表示多项式, 采用Paillier同态加密算法, 使用其公钥pk=(n, g)来加密每一个多项式P_Wi的系数得到(Enc(a_L), …, Enc(a₁), Enc(a₀)), 将加密后的索引表示为

4) 构建一个字典矩阵M_D, 形如:

利用可逆矩阵M加密M_D, 得到M′_D=M·M_D.

最后，将加密的字典矩阵M′_D和安全索引多项式矢量发送给云服务器.

3.3 陷门生成

T←Trapdoor(MK, Q):由数据拥有者执行.为用户的多关键字搜索请求生成搜索陷门, 算法的具体过程如下:

1) 当接收到一个搜索请求Q, 将构建多项式P_Q(x)=∏_Wi∈Ω(x-t_Wi)/∏_Wi∈Q(x-t_Wi), 为了隐藏陷门长度, 数据拥有者向P_Q(x)中填充随机元组, 得到

2) 使用P′_Q(x)的系数(a_m, a_m-1, …, a₁, a₀)来表示P′_Q(x).计算T[1]=(a_m, a_m-1, …, a₁)·M^-1, T[2]=Enc_{(n, g)}(a₀).最后, 数据拥有者将二元组陷门T=(T[1], T[2])返回给用户.

3.4 多关键字搜索

P_R(x)←Search(, T):由云服务器执行.云服务器利用用户发送的陷门T=(T[1], T[2])在存储的安全索引中进行搜索.算法的具体过程如下:

1) 接收到陷门后, 云服务器首先计算值V:

2) 对于每一个v_i(i∈[m]), 云服务器计算v′_i=Enc_{(n, g)}(v_i)+_hT[2].其中+_h是Paillier加密算法的同态加法.然后所有的值构成一个矢量: V′=(v′₁, v′₂, …, v′_m).

3) 计算并将其返回给用户.

用户接收到P_R(x)之后, 在数据拥有者的帮助下解密该多项式, 之后对其进行因式分解并找到P_R(x)=0的根, 这些根就是搜索结果, 即关键字对应的文件标签.

4 安全性证明和性能分析 4.1 定理1的正确性证明

根据P_Q(x)的定义可以得出查询陷门P′_Q(x)= ，从而可以看出P′_Q(x)=0的根就是不包括在查询中的所有关键字的标签, 即{x|x=t_Wi, W_i∉Q}.

因为v′_i=Enc_{(n, g)}(v_i)+_hEnc_{(n, g)}(a₀)是P′_Q(t_Wi), i∈[m]的密文, 而且对于关键字W_i∉Q, P′_Q(W_i)=0，则, 结果多项式只包含查询相关的文件标签, 所以P_R(x)的根实际上是包含所有查询关键字的文件集合.因此, 用户将会从云服务器中获取到正确的文件标签集合.

4.2 定理2的安全性证明

MKSE的安全性依赖于加法同态加密算法的语义安全.如果MKSE所基于的加法同态加密算法即Paillier同态加密方法是语义安全的加密系统, 那么MKSE是语义安全的.

假设多项式时间算法A可以以一个不可忽略的优势赢得2.3节中安全性实验, 则可以利用A构建一个算法B, B可以破坏基于随机预言模型(ROM)加密算法的语义安全.B可以访问预言机O_f, 在预言机中方法f要么是一个随机算法, 要么是加法同态加密算法.用B的计算代替该方案中的加密操作，然后通过2.3节安全性定义中给定的安全性实验来证明MKSE方案的安全性.

安全性实验的具体过程如下:

A输出b′, 作为他对b的猜想.如果A输出0, 那么B猜想在O_f中的f是一个随机函数, 表示为B_f=0.否则, B猜想f是加密算法, 表示为B_f=1.

明显地, 如果f是随机函数, 有概率Pr[B_f=0]=1/2.如果f是加密算法, 那么B同A有相同概率输出1.因此B在从随机预言模型中区分语义安全加密算法同A赢得安全性实验, 具有相同的优势.然而, 根据语义安全加密系统的定义, B是不存在的.因此, 不存在具有不可忽略概率赢得安全性实验的算法A.

另外讨论索引隐私和陷门隐私, MKSE方案在生成安全索引的过程中进行了随机填充, 保证索引对应文件列表长度的一致性, 并且采用Paillier加密方法保证了索引的机密性.在陷门生成过程中, T[1]的系数是被加密的, 在T[2]中, 虽然a₀是不加密的, 但由于在陷门中添加了随机填充, a₀每一次都是不同的, 因此, 一个明文查询每次都会被转换成不同的陷门, 所以MKSE方案打破了陷门的可链接性, 进而敌手无法从搜索操作中判断两个(或多个)加密的查询中是否使用了相同的关键词, 所以MKSE保护了搜索模式.

4.3 效率分析

设MKSE方案中倒排索引的关键字个数为n.

在初始化阶段, 数据拥有者需要执行2个指数操作生成Paillier同态加密所需密钥, 计算复杂度为O(1)个指数操作.

在安全索引生成阶段, 数据拥有者要对倒排索引进行加密, 倒排索引包含n个文件列表, 每个文件列表表示为L阶多项式, 因为在加密操作时要用多项式系数表示多项式并对多项式系数进行加密, 所以需要执行n×L个加密操作.同时, 生成M′_D的过程需要n³个乘法操作.通常来讲, 加密操作的计算复杂度最高, 因此方案在生成安全索引时的计算复杂度为O(n)个加密操作.

在陷门生成阶段, 数据拥有者需要执行一个多项式除法操作生成P′_Q(x), 执行n²个乘法操作生成T_Q[1], 执行1个指数操作生成T_Q[2].因此方案在陷门生成时的计算复杂度为O(1)个指数操作和O(n²)个乘法操作.

在搜索阶段, 云服务器执行n²个乘法操作计算V, 执行n个指数运算生成V′, 并执行n个乘法操作进行同态求和.计算复杂度为O(n)个指数操作和O(n²)个乘法操作.

4.4 实验分析

本文对MKSE方案进行了实验分析.实验使用了2015年最新版本的Enron数据集[http://www.cs.cmu.edu/~./enron/], 在邮件集中选取3 000个邮件作为实验文件集合.

本文根据字典的大小对方案执行的三个阶段(索引生成、陷门生成、搜索)的耗时进行实验分析, 所有记录的结果都是每组数据运行20次后的平均值.本文按照字典大小的不同将测试数据分为4组:A类字典(大小为50), B类字典(大小为100), C类字典(大小为150)和D类字典(大小为200).测试过程中, 每次搜索请求的关键字个数都为4.通过对以上4组数据的性能分析, 得出如图 2所示的索引生成、陷门生成以及搜索操作的耗时.

从图 2可以看出, 随着关键字字典大小的增大, 索引生成和搜索过程的耗时会随着增加.主要因为关键字字典增大的同时倒排索引也会变多, 这样在索引生成和搜索过程中就需要相应进行更多的加密操作, 因而耗时随之增加.而在生成陷门过程中, 字典的大小不会明显地影响陷门生成的耗时.

5 结论

1) 提出一种基于同态加密和私有集合交集技术的多关键字可搜索加密方案MKSE.方案支持多关键字密文搜索, 同时突破了现有方案只支持一次性搜索的限制, 可以进行关键字重复搜索.

2) 在生成索引和搜索陷门的过程中引入了随机项, 保护了索引隐私和陷门隐私, 进而使得该方案能够有效地对搜索模式进行保护.安全性分析表明该方案满足可搜索加密的语义安全.

3) 与其他基于双线性映射的公钥可搜索加密方案相比, 该方案在整个搜索过程中仅仅使用了乘法和指数运算, 因而具有较小的计算开销.