结构化加密图数据的Top-H 跳节点查询*

胡梦迪, 陈兰香

福建师范大学 计算机与网络空间安全学院 福建省网络安全与密码技术重点实验室, 福州350117

1 引言

随着互联网的飞速发展, 不同类型的数据已经应用于各个领域, 为了节约对大规模数据的管理成本,越来越多的用户选择将数据外包到第三方云服务器[1,2].随着数据外包的不断发展, 数据加密和密文检索的研究得到了极大的关注.近年来, 研究者在可搜索对称加密研究领域取得了极大的进展.Song 等人[3]首次引入可搜索对称加密(searchable symmetric encryption, SSE) 的概念, 并构建了第一个SSE 方案.该方案的思想主要是对文档的每个关键字进行特殊的两层加密, 然后存储在云服务器, 云服务器接收陷门并对每个关键字执行顺序扫描.此后可搜索对称加密还扩展到多关键字搜索[4,5]、动态关键字搜索[6–8]及范围搜索[9]等.然而, 这些搜索方案大多针对文本类型的数据.

2010 年, Kamara 等人[10]提出结构化加密(structured encryption, STE) 的概念, 可以实现各种类型数据的高效查询, 包括文本、矩阵及图数据等.同时, Kamara 等人[10]提出可链接性(chainability) 的思想, 主要用于多种数据类型之间建立关联.在一个可链接的结构化加密方案中, 半私密项yi和数据项zi是相关联的, 即查询操作返回指针j和半私密项yi.通过半私密项yi可以将两种复杂数据结构建立关联.但是当前的结构化加密方案只能实现邻居节点的查询, 不能实现多跳节点查询.因此, 本文基于结构化加密中可链接的思想, 提出了第一个结构化加密图数据的top-H跳节点查询方案, 从而实现邻居节点的迭代查询.

首先, 本文定义了外包图上的隐私保护top-H跳节点查询问题, 即给定一个无向图和一个待查询节点v, 返回距离查询节点v的H跳内的所有节点.其次, 为了支持隐私保护top-H跳节点查询, 本文利用结构化加密思想, 构建邻居索引表, 并使用对称加密方案和伪随机函数进行加密, 生成特殊的安全索引.最后, 针对构建的索引设计了一种用于top-H跳节点查询的算法.本文的贡献如下:

(1) 提出第一个结构化加密图数据的top-H跳节点查询方案.利用结构化加密的可链接性, 设计特殊的安全索引, 实现邻居节点的迭代查询.

(2) 对结构化加密图数据的top-H跳节点查询方案构建安全模型, 并进行安全性分析.

(3) 在真实数据集上进行测试, 对存储开销、时间开销和查询效率进行比对, 结果表明, 本方案安全性强, 查询效率高.

本文的组织结构如下: 第2 节介绍可搜索对称加密和结构化加密的相关工作;第3 节介绍系统模型、泄露函数及安全模型; 第4 节是符号定义和top-H跳节点查询方案模型; 第5 节介绍方案的算法以及安全性分析; 第6 节通过实验对本方案进行评估; 第7 节总结全文.

2 相关工作

随着网络的飞速发展, 云计算凭借其海量资源、动态扩展等优势成为学者研究重点.用户可以将大规模数据外包给云服务器, 以节约管理成本和存储空间.然而, 数据外包使得数据所有权和数据管理权分离,从而带来新的数据安全问题.为保护数据安全, 数据拥有者在外包数据之前对数据加密.但是, 传统的数据加密技术使得密文检索耗费大量的通信开销和本地计算开销.因此, 如何对加密数据执行高效检索仍是一个具有挑战性的工作.

可搜索对称加密2000 年, Song 等人[3]首次提出可搜索对称加密的概念, 并构造了第一个SSE 方案SWP.该方案的基本思想是: 数据拥有者对文档中的每个关键字采用特殊的两层加密, 然后将加密的文档集合存储在云端.数据拥有者对查询的关键字生成特定陷门并发送给云服务器, 云服务器接收陷门并对密文文档集合执行顺序扫描.但是这种方案需要云服务器对每个文档的关键字进行检索, 从而使得检索效率很低.为了提高检索效率, 2003 年, Goh 等人[11]提出新的SSE 方案.该方案的思想是为每个文档构建一个布隆过滤器, 并将关键字插入其中.当数据拥有者需要检索时, 服务器只需对布隆过滤器进行检索,判断关键字是否存在, 从而提高检索效率.2006 年, Curtmola 等人[12]提出了基于倒排索引的SSE 方案.他们首先构建倒排索引来存储从关键字到包含关键字的相应文档集合的映射, 然后服务器利用检索陷门定位到匹配项, 最后返回对应的文档集合.2014 年, Cash 等人[13]设计并构建了一个动态的SSE 方案.近几年随着研究者对可搜索对称加密的深入研究, 大量的SSE 方案被提出来.2020 年, Wang 等人[14]对当前可搜索加密方案进行了详细的分析, 包括多关键字搜索[4,5]和范围搜索[9]等方案.2022 年, Liu 等人[15]为了能够支持形式多样化的密文搜索, 提出了复杂语义可搜索加密方案, 该方案基于一种新的关键字特征提取方式, 将通配符可搜索加密转化为一般的多关键词可搜索加密.然而上述方案大多只针对于文本类型的数据, 并不适用于现实世界中的社交网络、线路规划及社区查找等数据类型.

结构化加密 2010 年, Kamara 等人[10]引入结构化加密的概念, 同时还提出了对加密图执行保密查询的图加密方案,例如: 邻居、邻接查询和聚焦子图查询.他们将图结构的数据视为一种数据结构δ和数据项z={z1,z2,···,zn}, 然后将结构化数据(δ,z) 加密后得到数据结构γ和密文序列c=(c1,c2,···,cn)并存储云端.用户使用私钥, 可以为任何查询构造令牌τ, 云服务器根据令牌从γ和τ恢复指向(zi)i∈I(I ∈[1,n]) 的指针, 返回密文ci.2011 年, Cao 等人[16]提出在加密图上实现隐私保护的查询方案, 该方案支持加密域中的内积计算.2017 年, Liu 等人[17]提出了一种top-K最近邻关键字搜索的图加密方案.2018 年, Liu 等人[18]提出了一种基于2HCL 索引的图加密方案, 用于查询存储在远端云服务器图上的最短距离.2018 年, Shen 等人[19]提出了近似最短距离查询图加密方案, 该方案结合了同态加密和基于顺序显示加密的基于树的密文比较协议.2021 年, Sun 等人[20]进一步提出在加密图上执行约束top-K最近关键字查询方案, 该方案利用2HCL 构建新的索引来计算约束最短距离, 同时还支持模糊关键字查询.2022 年, Yang 等人[21]为了实现对加密社交网络图的计算和统计分析, 提出了结构化加密的PSI 方案STE_max-PSI.该方案通过引入混乱布隆过滤器, 在确保数据隐私的前提下, 实现了更复杂数据结构的更加丰富的查询功能.2022 年, Wang 等人[22]提出top-K社交空间关键字搜索图加密方案.2022 年, Ge等人[23]为了实现搜索模式隐私, 提出了基于两个非共谋云服务器的加密图的近似最短距离查询图加密方案.本文在结构化加密的基础上, 第一个提出基于结构化加密图数据top-H跳节点查询方案.该方案以结构化加密可链接思想构建特殊安全索引, 通过迭代查询实现H跳节点查询.

3 系统模型

3.1 系统模型

系统模型包括三个实体: 数据拥有者、云服务器和数据使用者, 如图1 所示.数据拥有者拥有一个社交网络图G, 同时授权数据使用者以执行top-H跳节点查询.云服务器具有强大的计算资源和充足的存储空间, 用于提供top-H跳节点查询服务.云服务器接收到用户的查询请求后, 对外包的数据集执行查询并将查询结果返回给用户.数据使用者在获得授权后, 向云服务器发送top-H跳节点查询令牌.

图1 系统模型Figure 1 System model

Top-H跳节点查询方案主要包括六个步骤, 可以定义为六元组Π = (GenKey, BuildIndex, Encrypt,Token, Query, Decrypt), 具体描述如下:

(1) GenKey(λ)→K: 数据拥有者输入安全参数λ, 输出密钥K={K1,K2,K3}, 其中K1和K3用于加密邻居节点索引N,K2用于加密节点标识符.

(2) BuildIndex(G)→N: 构建邻居节点表.数据拥有者对图G中每个节点提取邻居节点并生成邻居节点索引表N.

(3) Encrypt(K,N)→I: 加密邻居节点表.数据拥有者使用伪随机函数f和g加密邻居节点表N,生成安全索引I.

(4) Token(K,H,v)→τ: 数据使用者向数据拥有者发出查询请求、跳数H和节点v, 数据拥有者返回查询令牌τ=(gK1(v),fK3(v),H).

(5) Query(I,τ)→R: 检索并返回结果.数据使用者将令牌τ发送给云服务器, 云服务器得到令牌τ后, 通过对安全索引I查询, 找到最终的密文集R并返回给数据使用者.

(6) Decrypt(K2,R)→v: 解密密文.数据使用者收到云服务器返回的密文集合R, 使用密钥K2对其进行解密.

3.2 泄露函数

针对top-H跳图加密方案, 我们给出两个泄露函数Lsetup(G) 和Lquery(G,q).具体定义如下:

-Lsetup(G): 主要是在设置阶段, 表示敌手A可以从安全索引I中学到的信息.从安全索引I中,A可以学习到节点的数n, 最大集合I(v) 的大小|I(v)| 信息.即Lsetup(G)={n,|I(v)|}.

-Lquery(G,q): 主要由查询模式和交集模式组成, 即Lquery(G,q)=QP(v)+IP(v).

· 查询模式QP(v): 给定一系列的top-H查询, 敌手A可以通过检查两次查询是否包含相同的令牌了解查询的节点是否已经被先前查询过.

· 交集模式IP(v): 从top-H查询的结果中, 敌手A可以得知两个查询结果是否包含相同的节点信息.

3.3 安全模型

本文方案采用自适应选择查询攻击(adaption chosen query attacks, CQA2[10]) 安全模型进行安全性分析.在CQA2 安全模型中, 敌手A适应性地进行询问.

定义1 (CQA2 安全模型) 给定一个top-H跳图加密方案Π = (GenKey, BuildIndex, Encrypt,Token, Query, Decrypt), 一个安全参数λ、一个敌手A和一个模拟器S, 其中泄露函数为Lsetup和Lquery, 定义游戏Real 和Ideal 如下所示:

- RealA(λ):A首先生成一个图G.挑战者分别运行K ←GenKey(λ) 和I ←Encrypt(K,N) 生成密钥K和安全索引I.给定安全索引I, 敌手A自适应地发出查询.对于每一个查询(H,v), 挑战者通过T ←Token(K,H,v) 生成并发送给敌手A.最后, 敌手A输出一个bit 位b ∈{0,1}作为游戏的输出.

- IdealA,S(λ): 敌手A生成一个图G.模拟器S根据泄露函数Lsetup(G) 生成安全索引结构I∗.给定安全索引I∗, 敌手A自适应地发出查询.对于每一个查询q, 模拟器S根据挑战者提供的Lquery(G,q) 模拟的一个令牌T∗并发送给敌手A.最后, 敌手A输出一个bit 位b ∈{0,1}作为游戏的输出.

如果对于所有多项式时间的敌手A, 总存在一个多项式时间模拟器S满足公式(1):

那么该图加密方案自适应选择查询攻击(CQA2) 安全的, 其中negl 是一个可忽略函数.

4 预备知识

4.1 符号定义

本文符号定义如表1 所示, 文中使用的几个函数定义如下.

表1 符号定义Table 1 Symbol definition

伪随机函数fK3和伪随机函数gK1如公式(2)所示:

生成密钥的伪随机函数P如公式(3)所示:

对称密钥加密(symmetric-key encryption, SKE) 方案由加密算法SKE.Enc 和解密算法SKE.Dec组成.

- SKE.Enc(K2,v)→c: 是一种概率算法, 输入密钥K2和节点v, 返回密文c, 表示为EncK2(v);

- SKE.Dec(K2,c)→v: SKE.Dec 是一种确定性算法, 输入密钥K2和密文c, 返回节点v, 表示为DecK2(c).

4.2 Top-H 跳模型

在top-H模型中, 我们使用字典和集合数据结构.其中集合Lv存储社交网络节点v的所有邻居节点, 字典则用于存储节点v和邻居节点集合Lv的映射.图2 给出了一个具体的例子.图2(a) 是一个含有7 个节点的社交网络图.图2(b) 是由BuildIndex 算法构建的一个字典N.BuildIndex 通过广度优先算法遍历每一个节点v的邻居节点并将其添加到集合Lv中, 然后将(v,Lv) 添加到字典N中, 直至所有节点遍历结束.

图2 示例图Figure 2 Example graph

加密字典N如表2 所示.使用伪随机函数g和密钥K1对字典N的索引入口加密, 例如: 对索引入口v加密得到gK1(v); 对于节点v的每一个邻居节点(ui) 构建一个三元组(EncK2(ui),αvui,βvui),并存储在集合L∗v中.其中EncK2(ui) 表示使用对称加密方案SKE 和密钥K2对节点ui加密;αvui=gK1(ui)⊕fK3(v), 表示使用伪随机函数f和密钥K3对节点v加密后的结果和加密的节点ui的索引入口异或;βvui=fK3(v)⊕fK3(ui) 表示使用伪随机函数f和密钥K3分别对节点v和ui加密后的结果异或.这样构造的好处是, 可以通过输入的令牌τ= (gK1(v),fK3(v),H), 在查询过程中计算出隐藏的邻居节点索引入口, 从而生成新的令牌以执行下一跳查询.对每个节点的邻居节点执行上述加密方案.但由于每个节点的邻居节点个数并不一样多, 最后需要对加密后的邻居集合L∗v进行填充, 使其大小相同.

表2 加密索引表Table 2 Encrypted index

如果想要检索节点v的H跳节点, 具体步骤如下:

(1) 首先生成一个令牌τ=(gK1(v),fK3(v),H) 并发送到云服务器;

(2) 云服务器接收到之后, 按照预先设定的算法执行检索.云服务器首先从令牌中读取gK1(v),找到索引表的索引入口, 从而获取节点v的邻居节点集合L∗v.云服务器从邻居节点集合L∗v中, 依次获得节点v的邻居节点密文信息, 并存放在集合R中, 假设获取的节点信息为R={EncK2(u1),EncK2(u2),···,EncK2(ut)};

(3) 对于每一个ui, 利用τ中的fK3(v), 计算gK1(ui)=αvui ⊕fK3(v) 和fK3(ui)=βvui ⊕fK3(v),得到节点ui的τui=(gK1(ui),fK3(ui),H −1);

(4) 利用每个ui的令牌τui进一步查询节点v的第二跳邻居节点, 过滤掉已查询的节点, 将未查询的节点添加到集合R中;

(5) 按照上述迭代式的查询下一跳节点直至查询到H跳为止;

(6) 最后云服务器返回最终结果集R.

5 Top-H 跳查询方案

5.1 算法描述

本文提出的基于结构化加密图数据的top-H跳节点查询方案包括六个算法: (GenKey, BuildIndex,Encrypt, Token, Query, Decrypt), 其中三个算法(GenKey, BuildIndex, Encrypt) 由数据拥有者负责执行, Query 由云服务器执行, Decrypt 由授权的数据使用者执行, 具体步骤及算法描述如下:

5.1.1 GenKey(1λ)→K

数据拥有者进行初始化, 生成密钥, 具体见算法1.数据拥有者输入安全参数λ, 输出密钥集合K={K1,K2,K3}.其中K1伪随机函数g的密钥,K2是对称加密方案SKE 的密钥,K3是伪随机函数f的密钥.

算法1 GenKey(1λ)→K Input: A security parameter λ Output: K = {K1,K2,K3}1 for each i ∈[1,3] do 2 Ki ←−Pk1(λ);3 end 4 Output K = {K1,K2,K3}.

5.1.2 BuildIndex(G)→N

数据拥有者利用广度优先遍历算法遍历每个节点v的邻居节点并存放于集合Lv中, 然后以键值对(v,Lv) 的形式存储于邻居节点表N中.详细过程见算法2.

算法2 BuildIndex(G)→N Input: A graph G Output: A neighbor index N 1 Parse G as (V,E);2 Initialize a dictionary N;3 for each v ∈V do 4 Let Lv be a set of vertices which are neighbor to v;5 N(v) ←Lv;6 end 7 Output N.

5.1.3 Encrypt(K,N)→I

数据拥有者输入密钥集合K和邻居节点表N, 生成安全索引I, 详细算法见算法3.第10 行表示对加密后的邻居节点集合L∗v进行填充, 使其具有相同长度.其中max|L∗v|表示填充后的长度.

算法3 Encrypt(K,N)→I Input: A neighbor index N and key K Output: An encrypted neighbor index I 1 Initialize a dictionary I;2 for each v ∈V do 5 αuv = gK1(u)⊕fK3(v);3 Initialize a set L∗v;4 for each u ∈Lv do 6 βuv = fK3(u)⊕fK3(v);7 Encu =Enc(K2,u);L∗v ←(Encu,αvu,βvu);9 end 10 Pad L∗v to max|L∗v|;11 I(gK1(v)) ←L∗v;12 end 13 Output I.8

5.1.4 Token(K,H,v)→τ

数据使用者向数据拥有者发送要检索的查询节点v和查询跳数H, 数据拥有者返回令牌τ:=(gK1(v),fK3(v),H) , 然后数据使用者发送令牌到云服务器进行检索, 详细过程见算法4.

算法4 Token(K,v,H)→τ :=(gK1(v),fK3(v),H)Input: K,v,H Output: τ 1 gK1(v) ←g(K1,v);2 fK3(v) ←f(K3,v);3 Output τ := (gK1(v),fK3(v),H).

5.1.5 Query(I,τ)→R

云服务器接收到用户的查询令牌后, 从查询令牌中读取gK1(v), 找到节点v的索引入口, 获得邻居节点集合L∗v.对于集合L∗v中的每个节点u使用τ中的fK3(v) 计算:gK1(u) =αvu ⊕fK3(v) 和fK3(u)=βvu ⊕fK3(v); 进而得到节点u的令牌τu=(gK1(u),fK3(u),H −1), 然后利用每个节点的令牌τu进行迭代式下一跳查询, 直至H跳为止, 最后将结果集R返回给用户.详细过程见算法5.

算法5 Query(I,τ)→R Input: A query token τ and an index structure I Output: An encrypted result set R 1 Parse τ as (gK1(v),fk3(v),H);2 Initialize set R, A;3 Initialize a Queue Q;4 Initialize a countl = 1, countr = 0;5 Add gK1(v) into Q, add (gK1(v),fK3(v)) into A;6 for each i ∈[1,H] do 7 while Q ̸= ∅do 8 Parse the queue header element as v′;9 for (encu,αv′u,βv′u) ∈L∗v′ do 10 gK1(u) = αv′u ⊕fK3(v′);11 fK3(u) = βv′u ⊕fK3(v′);12 if ((gK1(u),fK3(u)) ̸∈A) then 13 add (gK1(u),fK3(u)) into A;14 countr++;15 R ←encu;16 end 17 end 18 v′ ←Q 19 end 20 for i ∈[countl,countr] do 21 Q ←A[i]22 end 23 end 24 Output R.

5.1.6 Decrypt(K2,R)→v

数据使用者收到云服务器返回的加密结果集R后, 使用数据拥有者授权的密钥K2进行解密, 得到明文下的数据.具体见算法6.

算法6 Decrypt(K2,R)→v Input: K2,R Output: v 1 Compute v = DecK2(R);2 Output v.

5.2 安全性分析

在本方案中, 云服务器被认为是“诚实但好奇” 的, 云服务器会正确地执行检索任务并返回查询结果.但是在此过程中,云服务器会对敏感数据感到好奇.根据定义1 中的泄露函数和安全模型,我们将对top-H跳查询的图加密方案安全性进行分析.

在一个可链接的结构化加密方案中, 我们需要对其附加两个属性, 即半私密结构独立性和顺序独立性.半私密结构独立性要求加密数据结构和密文所揭示的信息只能依赖于保密数据项, 而不依赖于半私密数据.顺序独立性确保以不同顺序执行查询不会更改泄露信息, 这是因为在可链接的结构化加密方案会预先计算子令牌并存储在半私密数据项中, 当对复杂数据结构进行查询时, 这些子令牌会以不同的顺序显示出来.将这两种属性详细定义如下:

定义2 可链接性(Chainability): 一个结构化加密方案的泄露函数(Lsetup,Lquery) 针对自适应选择查询攻击是安全的, 则该结构化加密方案是可链接的, 并且泄露函数满足以下属性:

半私密结构独立性: 存在泄露函数L′setup满足公式(4).其中,z为保密数据项集合,y为半私密数据项集合.

顺序独立性: 存在一个转换T, 使得对于任何数据结构G、任何一系列查询q1,q2,···,qt和任何随机排列p满足公式(5):

如果本文top-H跳节点查询方案是一种可链接的结构化加密方案, 且满足公式(6)–(7):

其中,n表示节点个数,|I(v)| 表示索引表中最大索引项大小, QP(v) 表示当前查询节点是否已经被查询过, IP(v) 表示何时那些相同的密文数据项被访问过, QP(i) 表示I(v) 的第i个节点是否出现在先前查询中, IP(i) 表示I(v) 的第i个节点的邻居节点是否为当前或先前查询的节点的邻居节点.那么本文的方案针对自适应选择查询攻击是(Lsetup,Lquery) 安全的.

定理1 本文提出的top-H图加密方案满足CQA2 安全性.

证明: 首先构造一个模拟器S, 给定泄露函数Lsetup和Lquery,S构建一个伪造的加密索引I∗和一个大小为x的查询列表q∗.如果对于所有多项式时间的敌手A都无法区分Real 和Ideal 两个游戏, 那么本文的top-H图加密方案是(Lsetup,Lquery)-针对自适应选择查询攻击安全的.其中,A为敌手,S为模拟器,B为挑战者.

Game0: 该游戏执行真实实验RealA(λ).首先, 挑战者B通过GenKey(λ) 生成密钥K={K1,K2,K3}; 然后, 敌手A输出数据(G,N) 并接受挑战者B通过Encrypt(N) 生成的安全索引I.敌手A自适应的输出查询并且对于每一个查询敌手A接收令牌τv ←Token(K,H,v).最后, 敌手A返回游戏输出一个比特位b.

Game1: 首先, 挑战者B通过GenKey(λ) 生成密钥K={K1,K2,K3}; 然后, 敌手A输出数据(G,N) 并接收模拟器S通过泄露函数Lsetup(G,N) 生成的索引I∗.对于每个节点v的查询令牌τ计算如下: 使用R(v) 表示节点v的邻居节点集,yv:= (τi)i∈R(v)表示节点v的邻居节点的半私密数据项集合, 敌手A接收τv ←S(Lquery(G,I∗,v,H),yv).最后, 敌手A返回游戏输出一个比特位b.

在Game1中, 给定泄露函数Lsetup(G,N) , 模拟器S生成密钥K2←GenKey(1λ), 构造一个包含n个随机对(k,s) 的索引字典I∗, 并计算密文c=(EncK2(v1),EncK2(v2),···,EncK2(vn)).对于每一个查询(v,H), 模拟器会收到(Lquery(G,I∗,v,H),yv).使用Lquery(G,I∗,v,H) 的查询模式来确定查询是否为新的.如果不是, 则返回之前生成的相同的令牌, 否则就考虑两种情况.如果|I∗(v)|=0, 则随机选择未存储在I∗中的搜索节点k和随机值t, 并输出令牌τ= (t,k,H).否则就使用交叉模式来确定当前查询访问的位置之前是否被访问过.如果没有, 就将其设置为未使用的随机值, 否则, 就将其设置为先前选择的值.然后, 随机选择I∗中尚未使用的搜索节点k, 将s表示为(s1,s2), 计算并返回令牌τ= (t,k,H),其中t=yv ⊕s2,s是I∗中与k相关的值.

对于k的每一个随机选择都将与伪随机函数g的输出无法区分.由于表I∗中的所有值s都是随机选择的, 因此t=yv ⊕s2将是随机分布的, 因此伪随机函数f的输出是不可区分的.因为敌手不能区分伪随机函数g、伪随机函数f和真正的随机数, 所以Game0和Game1是不可区分的.

Game2: 与Game1相似, 区别在于对τ的计算, Game2只有在需要时才计算.对于每一个节点v,τ的计算如下:

(1) 对于所有的i ∈R(v),τi=(αij,βij)j∈|I(v)|,i∈R(v),αij=gK1(j)⊕fK3(i),βij=fK3(j)⊕fK3(i);

(2)τv ←S(Lquery(G,I∗,v,H),yv),yv:=(τi)i∈R(v).

因为令牌的产生是无状态的, 所以Game1等价于Game2.

Game3: 与Game2相似, 只是Lsetup(G,N) 和Lquery((G,I∗,v,H),yv) 是直接提供的而不是通过(G,N,v,H) 计算得到的.

由上述分析得知, Game3相当于模拟器S执行IdealA,S(λ).可以得出Game2和Game3的输出分布是相同的, 他们是不可区分的.

通过上述分析, 本文方案除了会泄露当前查询的节点之前是否查询过, 那些密文何时被再次访问、节点是否出现在先前的查询过程中以及访问节点的邻居节点是否为当前或先前查询的节点的邻居节点, 没有额外的泄露.本方案满足公式(7), 所以针对自适应选择查询攻击是Lquery安全的.

另外, 在本方案中, 云服务器仅知道加密的数据结构I、查询令牌t和查询过程中的半私密数据项y.因此, 云服务器可以在本方案模型中进行唯密文攻击(ciphertext only attack, COA).在本方案中, 采用密钥K2和对称密钥加密方案SKE 对节点标识符进行加密, 并存储在云服务器端.因为密钥是由数据拥有者管理, 且可以授权给数据使用者, 而云服务器不保护加密的密文, 所以概率多项式时间敌手A不能以超过1/2 的概率区分一个密文是对哪个节点标识符加密得到的.敌手A对节点v进行H跳查询, 可以获得节点v的最大邻居节点数|I(v)|.通过对所有H跳查询结果的统计可以获取节点个数n, 其满足公式(6).因此, 本文提出的方案对自适应选择查询攻击是Lsetup安全的.

对于所有多项式时间的敌手A都无法区分Real 和Ideal 两个游戏.如公式(8)所示:

综上所述, 本文的top-H图加密方案针对自适应选择查询攻击是(Lsetup,Lquery) 安全的.

6 实验评估

本节评估所提出的图加密方案的性能.实验环境为一台Intel(R) Core(TM) i5-8300H CPU @2.30 GHz 和8.00 GB RAM 的Windows 机器.PRF 和SKE 是使用安全参数λ= 128 的PyCrypto 实现,字典则使用Python 的字典数据结构实现.实验数据集使用来自斯坦福网络分析项目(SNAP) 的真实世界图形数据集.本文使用Facebook 社交网络数据集, 其中每个节点表示一个人, 而每条边表示两个节点之间的朋友关系.数据集详细信息如表3 所示.

表3 数据集Table 3 Data set

6.1 复杂度分析

本小节主要分析top-H节点查询图加密方案的空间复杂度和时间复杂度.在一个含有n个节点的图G中,I表示构建的安全索引,|I(v)|表示安全索引I中最大索引项大小,m表示边数.在top-H节点查询图加密方案中, 安全索引I为主要存储开销.因此, 空间复杂度为O(n×m).对于时间复杂度, 主要包括生成令牌和执行检索.算法Token 用于生成令牌,其时间复杂度为O(1).算法Query 用于执行检索,对于每一个查询令牌τ:= (gK1(v),fK3(v),H), 云服务器需要对每个节点的邻居节点迭代H次.假设,H跳以内的节点数为n, 执行检索的时间复杂度为O(n×(1+|I(v)|)), 总的时间复杂度为O(n×(1+|I(v)|)).

本文是第一个提出结构化加密图数据的top-H跳节点查询方案, 同时将本方案与相近且具有代表性的图加密方案进行对比, 具体见表4.其中n表示节点总数,m表示边的总数,H表示迭代次数,|W| 表示关键字总数,|I(v)| 表示安全索引I中最大索引项大小.

表4 方案比较Table 4 Scheme comparison

由表4 可知, 许多top-K方案都选择以2-Hop 作为基本索引结构, 为每个节点v分配一个标签, 在标签中存储二元组(u,H), 其中u表示节点v可达的顶点,H表示u和v之间的跳数.然而, 这种索引结构存在一定的不足, 包括索引本身和功能性不足.当待处理的节点数量达到十万或百万数量级时, 构建2-Hop 索引的初始化时间以及自身存储开销会变得很大, 使得在密文检索过程中计算量增大, 进而极大地降低了密文检索的效率.在社交网络中, 用户节点之间的跳数反映着用户之间的紧密程度, 限定跳数的节点查询可以帮助分析用户社区间的关系等, 而2-Hop 索引结构对于这种查询存在一定的局限性.而本方案极大地降低了索引的存储开销、提高了查询效率, 同时也实现了限定跳数的节点查询.

相比于文献[20,22,24] 的图加密方案, 本文的top-H跳节点查询图加密方案存储开销最少, 空间复杂度最优.本方案的时间复杂度是线性函数, 而文献[20] 和文献[22] 时间复杂度是指数函数, 所以本文的top-H跳节点查询图加密方案的时间复杂度优于二者.

6.2 时间开销

本文测试了方案生成邻居索引表和构建安全索引I的时间开销.为了更直观地看出时间开销, 本文计算了构建邻居索引表和加密索引的时间之和, 时间开销如图3 所示.

图3 不同数据集下构建索引时间Figure 3 Time to build indexes for different datasets

本方案构建安全索引I主要分为两步.首先, 对社交网络图中每一个节点提取其邻居节点构建邻居节点表N.然后使用伪随机函数和对称密钥加密方案加密索引表中的元素以生成安全索引I.从方案的构造可以看出, 构建索引的主要影响因素是数据集中边的数量.因此, 我们用四个不同数据集来评估构建安全索引的时间开销.为了更直观地看出时间开销, 我们计算了构建邻居索引表和加密索引的时间之和, 时间开销如图3 所示.

从图3 可以看出, 构建索引的时间开销随着数据集中边数的增加而线性增加.这是因为在构建安全索引I过程中, 对于n个节点的图G, 每个节点的邻居节点集合大小为|I(v)|,t为构建一个三元组使用伪随机函数的次数, 则构建安全索引需要执行n×|I(v)|×t次伪随机函数进行加密.

6.3 存储开销

本方案分别计算了邻居索引表N和安全索引I的存储开销.由图4 可以看出, 存储开销主要取决于安全索引I的大小.这是因为在安全索引I中, 每个节点的邻居节点以三元组(EncK2(u),αvu,βvu) 形式存储于数组L∗v.每个数组填充后的大小为|I(v)|, 节点个数为n, 总存储为O(n×|I(v)|).当边数m=20000 时, 所需要的存储开销为299.65 MB; 当边数m= 40000 时, 所需要的存储开销为618.19 MB.通过对比可以看出, 存储开销随着边数的增加而线性增加.

图4 不同数据集下构建索引开销Figure 4 Index overhead for different datasets

6.4 查询效率

对于top-H节点查询图加密方案的查询效率, 本文对不同跳数和不同数据集的查询时间进行比对.同时, 为了更直观地展现本方案的查询效率, 本文还测试了相同数据集和相同跳数H下的明文和密文的查询时间.对于每个数据集随机选取100 个节点进行查询且每个节点重复查询50 次, 最后以平均值作为实验评估值.

根据top-H跳节点查询方案的构造和查询模式可以看出, 影响top-H跳节点查询方案效率的因素主要包括两个方面, 分别为数据集中边的数量以及查询跳数H.由图5 可以看出, 在同一数据集下, 查询时间随着查询跳数H的增加而增加.这是因为随着跳数H的增大, 所涉及的邻居节点增多, 在密文检索过程中, 需要扫描和过滤的顶点增多, 进而使得查询时间增多.当查询跳数不变时, 随着数据集的增大, 节点和边同样随之增多, 进而使得查询时间增加.

图5 不同数据集和跳数下的查询时间Figure 5 Query time for different datasets

从图6 可以看出, 当数据集和跳数H相同时, 明文和密文的查询时间差别在几秒之间.对于明文的查询可直接对节点进行迭代.但是对于密文的查询, 需要对密文进行处理, 包括过滤填充信息等.

图6 明文和密文下的查询时间Figure 6 Query time for different hops

6.5 小结

通过实验分析可知, 本文提出的第一个结构化加密图数据top-H跳节点查询方案的存储开销比文献[20,22,24] 更优.Top-H跳节点查询方案的时间复杂度也是最优的.本方案构建的安全索引I的空间复杂度为O(n×m), 查询时间复杂度为O(n×(1+|I(v)|)).数据集的大小和查询跳数H的大小影响查询过程中所涉及的节点和边, 进而影响查询效率.同时, 本文还对明文和密文的查询效率进行了对比, 结果表明在密文下的查询是高效的.

7 总结

本文提出了第一个结构化加密图数据的top-H跳节点查询方案, 可以应用于社交网络好友查询等.为了能够实现更快更多的查询功能, 本文结合结构化加密可链接思想, 设计一个特殊的安全索引.利用特定的迭代查询算法可以更高效、更安全地执行查询操作.本文也对top-H跳图加密方案的安全性进行证明, 同时使用真实世界的图形数据集对本方案进行了评估测试.在接下来的工作中, 我们将进一步把结构化加密和分布式技术结合.当数据集非常大且查询跳数H很大时, 本文的迭代算法查询的效率就会随之下降,但是如果采用分布式技术来执行top-H跳节点查询,可以实现更高效的查询.