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

Top-H Query on Structured Encrypted Graph

为了保护外包数据的隐私,用户通常需要对数据加密后再存储到云服务器.但数据加密后,对密文数据的查询与处理变得极为困难.2010年,Kamara等提出结构化加密的概念,可以实现各种类型数据的高效查询,包括文本、矩阵及图数据等.利用结构化加密的思想,本文提出第一个结构化加密图数据的top-H跳节点查询方法.现有的H跳查询方案主要通过2-Hop索引计算查询节点之间的跳数来判断它们之间的可达性,当节点数达到十万或百万级时,构建2-Hop索引的计算和存储开销都非常大.本文提出的方案在满足可达性判断的同时极大地降低了存储开销,同时提高了查询效率,还实现了更加丰富的H跳范围查询.本方案采用了结构化加密中可链接(chainable)的思想,实现邻居节点的迭代查询.同时,根据用户指定的跳数(H)获取满足条件的top-H跳节点.安全性分析表明本方案满足CQA2安全.在真实数据集上的测试结果表明,本方案比已有方案更加高效.

In order to protect the privacy of outsourced data,users usually need to encrypt the data and store them to a cloud server.After data encryption,it is difficult to query and process encrypted data.In 2010,Kamara et al.proposed the concept of structured encryption,which can realize efficient query of various types of data,including text,matrix,graph data,etc.Base on the idea of structured encryption,a top-H-hop node query method for structured encrypted graph data is proposed in this paper.The existing H-hop query schemes mainly calculate the number of hops between query nodes by 2-Hop index to judge the reachability between them.Once the number of nodes reaches 100,000 or millions,the computing and storage overheads of building 2-Hop index are very large.The scheme proposed in this paper greatly reduces the storage overhead while satisfying the reachability judgment,improves the query efficiency,and achieves richer H-hop range queries.The proposed scheme adopts the idea of“chainability”in structured encryption to achieve iterative querying of neighbor nodes.It queries the top-H-hop nodes that satisfy the conditions according to the user-specified hop number(H).The security analysis shows that this scheme satisfies CQA2-security.The experimental results on real datasets show that the proposed scheme is more efficient compared to some existing schemes.