支持邻接关系查询的图结构密文搜索方案

doi:10.12068/j.issn.1005-3026.2018.08.006

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (8): 1092-1097.DOI: 10.12068/j.issn.1005-3026.2018.08.006

支持邻接关系查询的图结构密文搜索方案

徐紫枫，周福才，李宇溪，秦诗悦

(东北大学软件学院，辽宁沈阳110169)

收稿日期:2017-04-19 修回日期:2017-04-19 出版日期:2018-08-15 发布日期:2018-09-12
通讯作者: 徐紫枫
作者简介:徐紫枫(1990-)，男，黑龙江佳木斯人，东北大学博士研究生；周福才(1964-)，男，辽宁沈阳人，东北大学教授，博士生导师.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61772127，61472184); 国家科技重大专项 (2013ZX03002006)；辽宁省科技攻关项目(2013217004)；中央高校基本科研业务费专项资金资助项目(N151704002). 国家自然科学基金资助项目(51171041).

Searchable Encryption for Graph Data with Adjacency Query

XU Zi-feng， ZHOU Fu-cai， LI Yu-xi， QIN Shi-yue

School of Software， Northeastern University， Shenyang 110169， China.

Received:2017-04-19 Revised:2017-04-19 Online:2018-08-15 Published:2018-09-12
Contact: ZHOU Fu-cai
About author:-
Supported by:
-

摘要/Abstract

摘要： 现有的密文搜索方案不支持复杂数据结构，因此，提出一个针对图结构的密文搜索模型，给出其算法的形式化定义及安全模型.利用矩阵结构的加密索引提出一个支持邻接关系查询的图结构密文搜索方案，给出了方案算法的具体描述，并对安全性与效率进行分析.方案使用伪随机函数和伪随机置换，保证了用户的图数据和索引信息不被泄露，并通过现实模型实验和理想模型实验的方法进行安全性证明.对比传统密文搜索方案，该方案支持更加灵活的查询，并拥有更高的效率，在大数据环境下拥有广泛的应用前景.

关键词: 云存储, 密文搜索, 图结构加密, 邻接矩阵, 加密索引

Abstract: This paper proposes a searchable encryption model for graph data to address the problem that most of the current searchable encryption schemes cannot deal with complex data structures. The algorithms and security models of the scheme are described. Taking the encryption index of matrix structure into account， the detailed description of the searchable encryption scheme for graph data that supports adjacency queries is presented. The scheme utilizes pseudo-random functions and pseudo-random permutations to protect the privacy of the graph data and the encrypted index. Real models and ideal models test the security of the scheme. Compared with traditional searchable encryption schemes， the proposed scheme has more flexible searching ability and higher efficiency， which promotes broader application under big data environment.

Key words: cloud storage, searchable encryption, graph encryption, adjacency matrix, encrypted index

中图分类号:

TP309

徐紫枫，周福才，李宇溪，秦诗悦. 支持邻接关系查询的图结构密文搜索方案[J]. 东北大学学报:自然科学版, 2018, 39(8): 1092-1097.

XU Zi-feng， ZHOU Fu-cai， LI Yu-xi， QIN Shi-yue. Searchable Encryption for Graph Data with Adjacency Query[J]. Journal of Northeastern University Natural Science, 2018, 39(8): 1092-1097.

参考文献

[1]Song D X，Wagner D，Perrig A.Practical techniques for searches on encrypted data［C］// IEEE Symposium on Security and Privacy.Oakland，2000:44-55.
[2]Goh E J.Secure indexes［J/OL］.［2017-02-04］.https://gnunet.org/sites/default/files/secureindex.pdf.
[3]Curtmola R，Garay J，Kamara S，et al.Searchable symmetric encryption:improved definitions and efficient constructions［C］// ACM Conference on Computer and Communications Security.Alexandria，2006:79-88.
[4]van Liesdonk P，Sedghi S，Doumen J，et al.Computationally efficient searchable symmetric encryption［C］//Workshop on Secure Data Management.Singapore，2010:87-100.
[5]Kamara S，Papamanthou C，Roeder T.Dynamic searchable symmetric encryption［C］//Proceedings of the 2012 ACM Conference on Computer and Communications Security.Raleigh，2012:965-976.
[6]Li J，Wang Q，Wang C，et al.Fuzzy keyword search over encrypted data in cloud computing［C］// 2010 Proceedings IEEE INFOCOM.San Diego，2010:1-5.
[7]Chuah M，Hu W.Privacy-aware bedtree based solution for fuzzy multi-keyword search over encrypted data［C］// 2011 31st International Conference on Distributed Computing Systems Workshops (ICDCSW).Minneapolis，2011:273-281.
[8]Liu C，Zhu L，Li L，et al.Fuzzy keyword search on encrypted cloud storage data with small index［C］// 2011 IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS).Beijing，2011:269-273.
[9]Wang C，Ren K，Yu S，et al.Achieving usable and privacy-assured similarity search over outsourced cloud data［C］// 2012 Proceedings IEEE INFOCOM.Orlando，2012:451-459.
[10]Stefanov E，Papamanthou C，Shi E.Practical dynamic searchable encryption with small leakage［C］//NDSS Symposium 2014.San Diego，2014:72-75.
[11]Yang Y，Li H，Liu W，et al.Secure dynamic searchable symmetric encryption with constant document update cost［C］// 2014 IEEE Global Communications Conference (GLOBECOM).Austin，2014:775-780.
[12]Cash D，Jaeger J，Jarecki S，et al.Dynamic searchable encryption in very-large databases:data structures and implementation［C］ //NDSS Symposium 2014.San Diego，2014:23-26.
[13]Kamara S，Papamanthou C.Parallel and dynamic searchable symmetric encryption［C］//International Conference on Financial Cryptography and Data Security.Okinawa，2013:258-274.
[14]Chai Q，Gong G.Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers［C］//2012 IEEE International Conference on Communications (ICC).Ottawa，2012:917-922.
[15]Zheng Q，Xu S，Ateniese G.VABKS:verifiable attribute-based keyword search over outsourced encrypted data［C］//2014 Proceedings IEEE INFOCOM.Toronto，2014:522-530.
[16]Zhou F，Li Y，Liu A X，et al.Integrity preserving multi-keyword searchable encryption for cloud computing［C］//International Conference on Provable Security 2016.Nanjing，2016:153-172.
[17]Alderman J，Janson C，Martin K M，et al.Extended functionality in verifiable searchable encryption［C］//International Conference on Cryptography and Information Security in the Balkans.Koper，2015:187-205.
[18]Cash D，Jarecki S，Jutla C，et al.Highly-scalable searchable symmetric encryption with support for boolean queries［M］.Berlin:Springer，2013:353-373.
[19]Moataz T，Shikfa A.Boolean symmetric searchable encryption［C］//Proceedings of the 8th ACM SIGSAC Symposium on Information，Computer and Communications Security.Hangzhou，2013:265-276.
[20]Ryu E K，Takagi T.Efficient conjunctive keyword-searchable encryption［C］// 21st International Conference on Advanced Information Networking and Applications Workshops.Ontario，2007:409-414.

支持邻接关系查询的图结构密文搜索方案

Searchable Encryption for Graph Data with Adjacency Query

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	厉鹏，周福才，张帅. 基于BSSEVD的可搜索加密方案原型系统设计与实现[J]. 东北大学学报:自然科学版, 2020, 41(9): 1244-1250.
[2]	贾强，张帅，周福才. 一种面向密文大型数据集的可搜索加密方案[J]. 东北大学学报:自然科学版, 2019, 40(7): 913-919.
[3]	周福才，张宗烨，王恺璇，李宇溪. 基于Paillier和PSI的多关键字可搜索加密方案[J]. 东北大学学报:自然科学版, 2019, 40(3): 321-326.
[4]	李宇溪，周福才，徐紫枫. 隐藏访问模式的高效安全云存储方案[J]. 东北大学学报:自然科学版, 2018, 39(8): 1086-1091.
[5]	高健，曾康，金恒展，周福才. 基于CP-ABE的云存储数据访问控制方案[J]. 东北大学学报:自然科学版, 2015, 36(10): 1416-1421.