在云计算和大数据环境下, 数据不再像传统信息系统一样集中存储在本地, 而是更多地通过云服务提供商在云端进行存储, 以此来节省存储和管理开销.云存储虽然为数据拥有者提供了便利, 但同时使其失去了对数据安全性和正确性的有效控制.为了保护数据的隐私和安全, 加密成为确保云存储机密性的重要手段，但加密后的数据往往会失去原有的特征, 包括顺序、大小和所属范围等, 导致用户无法使用对存储数据进行搜索、浏览和在线编辑等常用服务.因此如何在保证数据机密性的前提下, 确保数据的可用性成为近年来云计算和密码学领域的重要研究内容.

密文搜索是指数据以密文方式存储, 并仍然可以对数据进行搜索和查询的技术.目前得到最多关注、并且应用最广泛的密文搜索技术是对称可搜索加密^[1](searchable symmetric encryption, SSE), SSE方案支持对加密文档的关键词搜索.2004年Goh^[2]指出了文献[1]中的不足, 并提出了基于布隆过滤器的密文搜索方案.2006年Curtmola等^[3]提出了两个基于倒排索引的密文搜索方案, 方案的搜索操作十分高效.2010年Liesdonk等^[4]提出两个支持高效更新的密文搜索方案.2012年, Kamara等^[5]对CGK+Ⅰ方案进行扩展与改进, 使其可以支持高效的更新操作(文档添加、删除和修改).近年来, 针对密文搜索存在的问题, 很多拥有不同特性的方案被提出, 例如支持模糊查询的方案^[6-9]、支持动态更新的方案^[10-13]、支持完整性验证的方案^[14-17]和支持布尔运算的方案等^[18-20].

目前的密文搜索方案大多集中在对文件集合进行加密, 并使用关键词进行搜索；然而在大数据环境下, 数据的存储结构更加复杂, 并且需要支持更加灵活的查询操作.图结构是最常用的数据结构之一, 被广泛应用于很多领域.将数据以图结构的形式进行储存, 便可以利用图论的多种算法对数据进行不同的操作与查询.因此针对图结构的密文搜索方案在云环境中拥有广泛的应用前景.

本文针对目前现有的密文搜索方案大多仅支持简单数据结构的问题, 提出了一个支持邻接关系查询的图结构密文搜索方案.方案使用矩阵结构构建加密索引, 并使用伪随机函数和伪随机置换保证了方案的机密性与隐私性.

1 预备知识 1.1 密文搜索方案通用模型

密文搜索方案包括两方实体:客户端C和服务器S.其中客户端拥有私有数据M, 并希望在不泄露任何信息的前提下将M存储在不可信的服务器上, 同时能够随时对数据进行搜索操作.

密文搜索方案包含两个阶段:初始化阶段和查询阶段.在初始化阶段中, 客户端将私有数据M进行加密, 生成密文数据M′, 并根据需要支持的查询类型生成加密索引δ, 然后将M′和δ发送到服务器进行保存; 在查询阶段, 客户端根据查询语句q生成查询令牌τ, 并发送给服务器.服务器根据查询令牌在加密索引中进行查找和计算, 并返回给客户端查询结果m′∈M′.最后客户端对密文查询结果进行解密操作, 得到明文查询结果m∈M.

密文搜索方案有两个安全目标:索引安全和查询安全.索引安全是指, 敌手服务器根据加密索引δ和密文数据M′, 无法得到任何关于私有数据M的信息; 查询安全是指, 敌手服务器根据适应性选择的查询语句q=(q₁, …, q_n)和对应的查询令牌τ=(τ₁, …, τ_n), 无法得到任何关于查询语句q和查询结果m的信息.

但是在实际应用中, 严格的索引安全和查询安全往往很难达到, 并且在部分应用场景中并不必要.因此在考虑密文搜索方案的安全性时, 需要构造泄露函数L₁和L₂, 分别指明方案中在加密索引和查询令牌中允许泄露的信息.

1.2 伪随机函数与伪随机置换

设D和R是两个域, K是密钥空间, 其中D={0, 1}^m, R={0, 1}ⁿ, K={0, 1}^k.伪随机函数的定义为f:{0, 1}^m×{0, 1}^k→{0, 1}ⁿ.一个安全的伪随机函数符合以下两个性质:

1) 给予一个输入x∈D和一个密钥k∈K, 存在多项式时间算法来计算f:x×k→y, 其中y∈R.

2) 任意的多项式时间敌手无法区分伪随机函数的结果与随机预言机(随机函数, 对于任何输入都返回均匀分布的随机结果).

相对于伪随机函数, 伪随机置换将输出映射到与输入相同的域中, 它的定义为f:{0, 1}^m×{0, 1}^k→{0, 1}^m, 其安全定义与伪随机函数相同.

2 模型与定义 2.1 符号标志与图的表示

本节给出支持邻接关系查询的图结构密文搜索方案的形式化描述与安全定义.为了便于描述, 将采用表 1中的符号标志.

方案中的图数据为有向图, 由点集合V、边集合E和邻接矩阵A组成:G=(V, E, A).A=(a_ij)_n×n, 其中a_ij={0, 1}, 表示点v_i和点v_j在图中的邻接关系, 若v_i和v_j在图中存在边, 则a_ij=1, 否则a_ij=0.

2.2 模型形式化描述

支持邻接关系查询的图结构密文搜索方案包含两方实体:客户端C和服务器S.客户端希望将隐私的图数据G保存在不可信服务器上, 并且能够在不泄露信息的情况下对G进行邻接关系查询.

方案包含两个阶段:初始化阶段和查询阶段.在初始化阶段中, 客户端根据自己的图数据生成加密索引, 并将加密索引发送给服务器保存, 初始化阶段仅执行一次.在查询阶段中, 客户端根据查询语句生成查询令牌, 并将查询令牌发送到服务器.其中查询语句包含图中两个点的标志符i, j, 即查询点v_i和点v_j在图中是否邻接.服务器收到查询令牌后, 在加密索引中进行查找和计算, 并返回给客户端查询结果, 查询阶段可执行多次.

方案由5个多项式时间算法组成：Setup, EDS, Token, Query, Dec.各算法的具体描述如下:

1) K←Setup(1^k):初始化算法, 输入为安全参数k, 输出为密钥K.

2) δ←EDS(K, G):加密索引构建算法, 输入为密钥K和图数据G, 输出为加密索引δ.

3) τ←Token(K, q):查询令牌生成算法, 输入为密钥K和查询语句q, 输出为查询令牌τ.

4) c←Query(δ, τ):查询算法, 输入为加密索引δ和查询令牌τ, 输出为搜索结果c(密文).

5) r←Dec(K, c):解密算法, 输入为密钥K和密文结果c, 输出为明文结果r.

2.3 安全定义

设L₁和L₂为两个泄露函数, 其中L₁为图G中点的数量n, L₂为查询模式(两次查询是否使用相同的查询语句).

对于敌手服务器A, 通过构建现实模型实验和理想模型实验给出安全定义.

现实模型实验Real_{A, C}(k):敌手A和客户端C通过方案中的真实算法进行交互.在初始化阶段, A首先选择两个图G₀和G₁并发送给客户端, 客户端随机选择其中一个图作为输入, 执行方案的Setup算法和EDS算法, 并将生成的加密索引发送给A.在查询阶段, A选择查询语句q并发送给客户端, 客户端使用Token算法生成查询令牌, 并发送给A.在经过多项式次查询后, 若A能够以不可忽略的概率判断出客户端选择了G₀还是G₁, 则敌手获胜.

理想模型实验Ideal_{A, Sim}(k):敌手A和模拟器Sim进行交互.在初始化阶段, 敌手选择图G并发送给模拟器; 模拟器根据L₁生成矩阵δ, δ的大小为n×n, 矩阵中所有的值为随机字符串.在查询阶段, A选择查询语句q并发送给模拟器; 模拟器根据L₂判断以前是否使用查询语句查询过:若查询过, 则返回A之前生成的查询令牌, 若没查询过, 则随机挑选邻接矩阵中未访问过的位置x, y, 并生成查询令牌返回A.

若敌手A在现实模型实验和理想模型实验中的视都是可忽略的, 则方案在泄露函数(L₁, L₂)下针对适应性选择查询攻击是安全的(简写为IND-CQA2安全).

定理1  支持邻接关系查询的图结构密文搜索方案在泄露函数(L₁, L₂)下针对适应性选择查询攻击是安全的，即IND-CQA2安全.

3 方案构建 3.1 算法描述

设F:{0, 1}^k×{0, 1}^*×{0, 1}^*={0, 1}^*是一个安全的伪随机函数, P:{0, 1}^k×[n]=[n]是一个安全的伪随机置换, 其中n是客户端的图数据中点的数量, π=(Gen, Enc, Dec)是一个针对不可区分的选择明文攻击具有安全性(即IND-CPA安全)的对称加密算法.在没有密钥的情况下, π生成的密文和F, P的结果与随机字符串在多项式时间内是计算不可区分的.

支持邻接关系查询的图结构密文搜索方案算法的详细构建方法如下.

1) K₁, K₂, K₃←Setup(1^k):初始化算法, 由客户端执行.首先根据安全参数k, 随机生成两个k比特长度的密钥K₁和K₂; 然后选择IND-CPA安全的对称加密算法π, 并生成K₃←π.Gen(1^k).算法的伪代码如下:

Algorithm: K₁, K₂, K₃←Setup(1^k)

Input: security parameter k

Output: secret keys K₁, K₂ and K₃

1  Random Sample

2  Random Sample

3  Choose a IND-CPA symmetric encryption scheme π

4  Run K₃←π.Gen(1^k)

5  Return K₁, K₂ and K₃

2) δ←EDS(K₁, K₂, K₃, G):加密索引构建算法, 由客户端执行.设图G中点的数量为n, 首先构建新的矩阵δ, δ和图G的邻接矩阵A的大小相同, 即n×n；对于所有的1≤i, j≤n, 在邻接矩阵中查找a_ij, 并使用对称加密算法π对其进行加密, 得到t=π.Enc_K3(a_ij)；之后使用伪随机置换, 根据i和j计算新的位置坐标, i′=P_K2(i), j′=P_K2(j)；最后, 使用异或操作计算t⊕F_K1(i, j), 并将结果保存到δ[i′, j′]中.矩阵δ即为图G的加密索引.算法的伪代码如下:

Algorithm: δ←EDS(K₁, K₂, K₃, G)

Input: secret keys K₁, K₂, K₃ and graph G={V, E, A}

Output: encrypted index δ

1  Initialize Matrix δ of size n×n

2  for each 1≤i, j≤n

3    Compute t=π.Enc_K3(a_{i, j})

4    Compute i′=P_K2(i)

5    Compute j′=P_K2(j)

6    Assign δ[i′, j′]=t⊕F_K1(i, j)

7  end for each

8  Return δ

3) τ←Token(K₁, K₂, q):查询令牌生成算法, 由客户端执行.一个邻接关系查询q中包含图中两个点的标志符, q=(x, y).在生成查询令牌时, 首先使用伪随机置换, 计算x′=P_K2(x)和y′=P_K2(y); 然后使用伪随机函数, 计算s=F_K1(x, y).查询令牌τ包含以上三个部分, 即τ=(s, x′, y′).算法的伪代码如下:

Algorithm: τ←Token(K₁, K₂, q)

Input: secret keys K₁, K₂, and query q=(x, y)

Output: query token τ

1  Compute x′=P_K2(x)

2  Compute y′=P_K2(y)

3  Compute s=F_K1(x, y)

4  Return τ=(s, x′, y′)

4) c←Query(δ, τ):查询算法, 由服务器执行.在收到查询令牌τ后, 服务器首先在加密索引中查找(x′, y′)位置的值, 即δ[x′, y′]；之后计算c=δ[x′, y′]⊕s, c是查询结果的密文, 即点v_x和v_y在图G中的邻接关系的密文.算法的伪代码如下:

Algorithm: c←Query(δ, τ)

Input: encrypted index δ and query token τ

Output: query result c

1  Parse τ as (s, x′, y′)

2  Lookup δ[x′, y′]

3  Compute c=δ[x′, y′]⊕s

4  Return c

5) r←Dec(K₃, c):解密算法, 由客户端执行.在收到查询结果的密文c后, 用户使用π和密钥K₃进行解密, 得到r=π.DecK₃(c).r是查询q的最终结果, 即点v_x和v_y在图G中的邻接关系.算法的伪代码如下:

Algorithm: r←Dec(K₃, c)

Input: secret key K₃ and ciphertext c

Output: plaintext r

1  Run r=π.Dec_K3(c)

2  Return r

3.2 方案交互过程

方案交互过程分为初始化阶段和查询阶段.

在初始化阶段, 客户端首先执行初始化算法Setup, 生成密钥; 然后执行加密索引构建算法EDS, 使用密钥将隐私图数据进行加密, 并生成加密索引; 最后客户端将加密索引发送给服务器.初始化阶段仅执行一次.

在查询阶段, 客户端根据查询语句, 首先执行查询令牌生成算法Token, 使用密钥和查询语句生成查询令牌, 并发送给服务器; 服务器在收到查询令牌后, 执行查询算法Query, 在加密索引中查找与计算, 并返回客户端查询结果; 客户端收到查询结果后, 执行解密算法Dec, 利用密钥将密文的查询结果解密, 得到最终的明文查询结果.查询阶段可多次执行.方案的交互图如图 1所示.

4 安全性证明和效率分析 4.1 定理1的安全性证明

根据方案的安全性定义, 通过构建现实模型实验和理想模型实验证明方案的安全性, 即证明，对于敌手服务器A, 加密索引δ不泄露任何关于图数据G的信息, 并且适应性选择的查询语句q不泄露任何关于查询的信息, 除了预定义的泄露函数L₁和L₂中的信息.

首先构建现实模型实验, 在现实模型实验中, 敌手服务器A与真实的用户使用方案中的算法进行交互.具体实验如下:

在以上实验中, A是一个概率多项式时间敌手服务器.在初始化阶段, A选取两个相同大小(点的数量相同)的图, G₀和G₁, 并发送给客户端C.在收到两个图后, 客户端随机选取一个比特b={0, 1}, 并选择图G_b作为自己的图数据.之后客户运行方案中的Setup算法和EDS算法, 得到加密索引δ, 并发送给敌手服务器.在查询阶段, A选择查询语句q并发送给客户端.客户端使用方案中的Token算法生成查询令牌并返回给A.在进行多项式次查询后, A根据学到的知识(δ和τ)猜测一个比特={0, 1}.如果b=, 则实验输出1, 否则输出0.

敌手A想要赢得以上实验, 即以不可忽略的概率使实验输出1或0, 则需要判断出收到的δ是根据G₀还是G₁生成的.因为G₀与G₁拥有相同的大小, 因此生成的δ的大小也相同.根据方案中的算法EDS, δ[x′, y′]中存储的数据为π.Enc_K3(a_xy)⊕F_K1(x, y), 其中a_xy是图G_b的邻接矩阵A的元素, x′=P_K2(x), y′=P_K2(y).因此若π是一个IND-CPA的对称加密算法, 且F和P是安全的伪随机函数和伪随机置换, 则δ中的所有数据计算不可区分.

在查询时, 客户端根据查询语句生成查询令牌.根据方案中的算法Token, 对于查询语句q=(x, y), 查询令牌的生成方法为τ=(F_K1(x, y), P_K2(x), P_K2(y)).因此若F和P是安全的伪随机函数和伪随机置换, 则查询令牌与随机字符串计算不可区分.

综上所述, 敌手A在该实验中获得优势的概率是可忽略的, 即Adv_A=|Pr[EXP_A^Real]=1|－|Pr[EXP_A^Real]=0|=ε, 即A在现实模型中的视是可忽略的, 即View_A^Real[C(G_A), A]=ε.

然后构建理想模型实验, 在理想模型实验中, 敌手服务器A与模拟器Sim进行交互.在初始化阶段, Sim根据泄露函数L₁, 发送一个矩阵δ给A, δ的大小与A选择的图G的邻接矩阵的大小相同, 且δ中保存的数据为随机字符串.在查询阶段, A选择查询语句q, 并发送给Sim.Sim根据泄露函数L₂判断该查询语句之前是否出现过.若出现过, 则返回A之前生成的查询令牌; 若没出现过, 则随机挑选未访问过的位置x, y, 生成查询令牌, 并返回给A.

若π是IND-CPA安全的对称加密算法, 则算法生成的密文与随机字符串不可区分, 并且若F和P是安全的伪随机函数和伪随机置换, 则δ中的所有数据与随机字符串计算不可区分.综上所述, 敌手A在理想模型实验中的视是可忽略的, 即View_A^Ideal[Sim(L₁, L₂), A]=ε.

根据以上两个实验, 可以得到View_A^Real[C(G_A), A]≈View_A^Ideal[Sim(L₁, L₂), A]=ε, 即敌手在现实模型下和理想模型下的视都是可忽略的.因此对于敌手服务器A, 加密索引δ不泄露任何关于图数据G的信息, 并且适应性选择的查询令牌τ不泄露任何关于查询语句的信息, 除了预定义的泄露函数L₁和L₂中的信息.

综上所述, 如果π是一个IND-CPA的对称加密算法, 且F和P是安全的伪随机函数和伪随机置换, 则支持邻接关系查询的图结构密文搜索方案在泄露函数(L₁, L₂)下针对适应性选择查询攻击是安全的.

4.2 效率分析

在初始化阶段, 客户端根据图数据G=(V, E, A), 使用算法EDS生成加密索引δ.设图中点的数量为n, 首先需要对邻接矩阵A中的所有数据进行加密.A的大小为n×n, 因此计算量为n²个加密操作；之后需要对A中所有的位置执行伪随机函数F, 并与之前的密文做异或操作, 因此计算量是n²个F和n²个异或操作；最后需要对A中所有的位置执行两次伪随机置换P, 即2n²个P.综上所述, 初始化阶段的计算量为n²个加密操作+n²个F+2n²个P+n²个异或操作.通常来讲, 加密操作的计算复杂度最高, 因此方案在生成加密索引时的计算复杂度为O(n²)个加密操作.

在查询阶段, 客户端首先根据查询语句q, 使用算法Token生成查询令牌τ.在算法中需要2个伪随机置换P和1个伪随机函数F；之后客户端将τ发送给服务器, 并收到查询结果c；最后客户端使用Dec算法对查询结果进行解密, 其计算量为1个解密操作.综上所述, 查询阶段客户端的计算量为2个P+1个F+1个解密操作.通常来讲, 解密操作的计算复杂度最高, 因此方案在查询阶段时客户端的计算复杂度为O(1)个解密操作.

在收到查询令牌后, 服务器执行Query算法，在加密索引δ中进行查找与计算.算法首先查找δ中一个位置的值, 之后进行1次异或操作.所以方案在查询阶段时服务器的计算复杂度为O(1)个异或操作.

5 结语

针对目前现有的密文搜索方案仅支持简单数据结构的问题, 本文提出了支持邻接关系查询的图结构密文搜索方案模型, 并给出了方案的形式化描述和安全性定义.使用现实实验和理想实验的方法, 对方案的安全性进行了证明, 并对效率进行分析.对比传统密文搜索方案, 该方案支持更加灵活的查询, 并拥有更高的效率, 同时保护了用户图数据的机密性和查询的隐私性，在大数据环境下拥有广泛的应用前景.