计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (1): 133-154.doi: 10.1007/s11390-019-1903-2

所属专题： Data Management and Data Mining

• Data Management and Data Mining • 上一篇    下一篇

用户访问权限管理加密云数据的安全反向索引搜索

Fateh Boucenna1,2, Omar Nouali1, Samir Kechid2, and M. Tahar Kechadi3   

  1. 1 Security Division, Research Center for Scientific and Technical Information, Algiers 16028, Algeria;
    2 Laboratory of Research in Artificial Intelligence, Department of Computer Science, University of Sciences and Technology Houari Boumediene, Algiers 16111, Algeria;
    3 The Insight Centre, University College Dublin, Dublin, D04 V1W8, Ireland
  • 收稿日期:2017-09-21 修回日期:2018-10-24 出版日期:2019-01-05 发布日期:2019-01-12
  • 作者简介:Fateh Boucenna is currently a Ph.D. student at the University of Sciences and Technology Houari Boumediene (USTHB), Algiers, and research assistant at the Research Centre for Scientific and Technical Information (CERIST), Algiers. He was awarded an M.S. degree from the University of Jijel in 2010 and a Magister degree from USTHB, Algiers, in 2013. His research interests include information retrieval, computer security and cloud computing.

Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management

Fateh Boucenna1,2, Omar Nouali1, Samir Kechid2, and M. Tahar Kechadi3   

  1. 1 Security Division, Research Center for Scientific and Technical Information, Algiers 16028, Algeria;
    2 Laboratory of Research in Artificial Intelligence, Department of Computer Science, University of Sciences and Technology Houari Boumediene, Algiers 16111, Algeria;
    3 The Insight Centre, University College Dublin, Dublin, D04 V1W8, Ireland
  • Received:2017-09-21 Revised:2018-10-24 Online:2019-01-05 Published:2019-01-12
  • About author:Fateh Boucenna is currently a Ph.D. student at the University of Sciences and Technology Houari Boumediene (USTHB), Algiers, and research assistant at the Research Centre for Scientific and Technical Information (CERIST), Algiers. He was awarded an M.S. degree from the University of Jijel in 2010 and a Magister degree from USTHB, Algiers, in 2013. His research interests include information retrieval, computer security and cloud computing.

PDF (PC)

470

补充材料

1

云计算是一项为用户提供大量储存空间和庞大计算能力的技术。然而，外包数据通常较为敏感和机密，进而在外包之前必须予以加密。不幸的是，经典的收索方法已经过时并且与加密数据的新方法已经成为必需的方法。考虑到隐私，大多数方法都基于耗时的矢量模型，因为考虑到查询矢量必须与每个文件矢量对比，全部索引在收索过程中必须被载入和利用。为了解决此问题，我们提出了构建一个安全反向索引的新方法，它使用了两个核心技术：同态加密和虚拟文件技术。但是，1）同态加密产生了大量的加密文本，它比与之对应的纯文本大了成千上万倍；2）提升索引安全的虚拟文件技术在搜索结果中产生了许多主动错误信息。通过两种方法，即，加密分数压缩表和双分数公式，本文提出的方法利用了两个技术的优点。此外，我们使用一个次安全反向索引以管理用户访问数据的权限。最后，为了验证我们的方法，我们收集100万文档数据作了一项实证研究。结果表明我们方法的计算速度是其他基于矢量模型方法的很多倍。

关键词: 可收索加密, 云计算, 同态加密, 基于属性加密, 反向索引

Abstract: Cloud computing is a technology that provides users with a large storage space and an enormous computing power. However, the outsourced data are often sensitive and confidential, and hence must be encrypted before being outsourced. Consequently, classical search approaches have become obsolete and new approaches that are compatible with encrypted data have become a necessity. For privacy reasons, most of these approaches are based on the vector model which is a time consuming process since the entire index must be loaded and exploited during the search process given that the query vector must be compared with each document vector. To solve this problem, we propose a new method for constructing a secure inverted index using two key techniques, homomorphic encryption and the dummy documents technique. However, 1) homomorphic encryption generates very large ciphertexts which are thousands of times larger than their corresponding plaintexts, and 2) the dummy documents technique that enhances the index security produces lots of false positives in the search results. The proposed approach exploits the advantages of these two techniques by proposing two methods called the compressed table of encrypted scores and the double score formula. Moreover, we exploit a second secure inverted index in order to manage the users' access rights to the data. Finally, in order to validate our approach, we performed an experimental study using a data collection of one million documents. The experiments show that our approach is many times faster than any other approach based on the vector model.

Key words: searchable encryption, cloud computing, homomorphic encryption, attribute-based encryption, inverted index

[1] Song D X D, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In Proc. the 2000 IEEE Symposium on Security and Privacy, May 2000, pp.44-55.
[2] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption:Improved definitions and efficient constructions. In Proc. the 13th ACM Conference on Computer and Communications Security, October 2006, pp.79-88.
[3] Wang B, Yu S C, Lou W J, Hou Y T. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud. In Proc. 2014 INFOCOM, April 2014, pp.2112-2120.
[4] Xu J, Zhang W M, Yang C, Xu J J, Yu N H. Two-stepranking secure multi-keyword search over encrypted cloud data. In Proc. the 2012 International Conference on Cloud and Service Computing, November 2012, pp.124-130.
[5] Yu J D, Lu P, Zhu Y M, Xue G T, Li M L. Toward secure multikeyword top-k retrieval over encrypted cloud data. IEEE Transactions on Dependable and Secure Computing, 2013, 10(4):239-250.
[6] Cao N, Wang C, Li M, Ren K, Lou W J. Privacy-preserving multi-keyword ranked search over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1):222-233.
[7] Xia Z H, Zhu Y, Sun X M, Qin Z, Ren K. Towards privacypreserving content-based image retrieval in cloud computing. IEEE Transactions on Cloud Computing, 2018, 6(1):276-286.
[8] Boucenna F, Nouali O, Kechid S. Concept-based semantic search over encrypted cloud data. In Proc. the 12th International Conference on Web Information Systems and Technologies, April 2016, pp.235-242.
[9] Li K, Zhang W M, Tian K, Liu R D, Yu N H. An efficient multi-keyword ranked retrieval scheme with JohnsonLindenstrauss transform over encrypted cloud data. In Proc. the 2013 International Conference on Cloud Computing and Big Data, December 2013, pp.320-327.
[10] Wang C, Cao N, Li J, Ren K, Lou W J. Secure ranked keyword search over encrypted cloud data. In Proc. the 30th International Conference on Distributed Computing Systems, June 2010, pp.253-262.
[11] Xia Z H, Wang X H, Sun X M, Wang Q. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2):340-352.
[12] Gentry C. A fully homomorphic encryption scheme[Ph.D. Thesis]. Department of Computer Science, Stanford University, 2009.
[13] Naehrig M, Lauter K, Vaikuntanathan V. Can homomorphic encryption be practical? In Proc. the 3rd ACM Cloud Computing Security Workshop, October 2011, pp.113-124.
[14] Bethencourt J, Sahai A, Waters B. Ciphertext-policy attribute-based encryption. In Proc. the 2007 IEEE Symposium on Security and Privacy, May 2007, pp.321-334.
[15] Yang J, Li S J. Searchable public key encryption scheme with data integrity checking. In Proc. the 11th International Conference on Broadband and Wireless Computing, Communication and Applications, November 2016, pp.363-370.
[16] Cash D, Grubbs P, Perry J, Ristenpart T. Leakage-abuse attacks against searchable encryption. In Proc. the 22nd ACM SIGSAC Conference on Computer and Communications Security, October 2015, pp.668-679.
[17] Yang Y, Ma M D. Semantic searchable encryption scheme based on lattice in quantum-era. Journal of Information Science & Engineering, 2016, 32(2):425-438.
[18] van Dijk M, Gentry C, Halevi S, Vaikuntanathan V. Fully homomorphic encryption over the integers. In Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2010, pp.24-43.
[19] Wong W K, Cheung D W L, Kao B, Mamoulis N. Secure kNN computation on encrypted databases. In Proc. the 2009 ACM SIGMOD International Conference on Management of Data, June 2009, pp.139-152.
[20] Sun X, Zhu Y, Xia Z et al. Secure keyword-based ranked semantic search over encrypted cloud data. Advanced Science and Technology Letters, 2013, 31:271-283.
[21] Yang Y. Attribute-based data retrieval with semantic keyword search for e-health cloud. Journal of Cloud Computing, 2015, 4(1):Article No.10.
[22] Bouabana-Tebibel T, Kaci A. Parallel search over encrypted data under attribute based encryption on the cloud computing. Computers & Security, 2015, 54:77-91.
[23] Meharwade A, Patil G. Efficient keyword search over encrypted cloud data. Procedia Computer Science, 2016, 78:139-145.
[24] Fu Z J, Sun X M, Liu Q, Zhou L, Shu J G. Achieving efficient cloud search services:Multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Transactions on Communications, 2015, E98.B(1):190-200.
[25] Xia Z H, Xiong N N, Vasilakos A V, Sun X M. EPCBIR:An efficient and privacy-preserving content-based image retrieval scheme in cloud computing. Information Sciences, 2017, 387:195-204.
[26] Johnson W B, Lindenstrauss J. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 1984, 26(189-206):Article No. 1.
[27] Boucenna F, Nouali O, Dabah A, Kechid S. Accelerated search over encrypted cloud data. In Proc. the 2017 IEEE International Conference on Big Data and Smart Computing, February 2017, pp.170-177.
[28] Deng Z J, Li K L, Li K Q, Zhou J L. A multi-user searchable encryption scheme with keyword authorization in a cloud storage. Future Generation Computer Systems, 2016, 72:208-218.
[29] Li M, Yu S C, Cao N, Lou W J. Authorized private keyword search over encrypted data in cloud computing. In Proc. the 31st International Conference on Distributed Computing Systems, June 2011, pp.383-392.
[30] Han F, Qin J, Zhao H W, Hu J K. A general transformation from KP-ABE to searchable encryption. Future Generation Computer Systems, 2014, 30:107-115.
[31] Goyal V, Pandey O, Sahai A, Waters B. Attribute-based encryption for fine-grained access control of encrypted data. In Proc. the 13th ACM conference on Computer and Communications Security, October 2006, pp.89-98.
[32] Yuan J W, Yu S C, Guo L K. SEISA:Secure and efficient encrypted image search with access control. In Proc. the 2015 IEEE Conference on Computer Communications, April 2015, pp.2083-2091.
[33] Wang B, Song W, Lou W J, Hou Y T. Inverted index based multikeyword public-key searchable encryption with strong privacy guarantee. In Proc. the 2015 IEEE Conference on Computer Communications, April 2015, pp.2092-2100.
[34] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. In Proc. the 3rd Innovations in Theoretical Computer Science Conference, January 2012, pp.309-325.
[35] Sahai A, Waters B. Fuzzy identity-based encryption. In Proc. the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2005 pp.457-473.
[36] Emura K, Miyaji A, Nomura A, Omote K, Soshi M. A ciphertext-policy attribute-based encryption scheme with constant ciphertext length. In Proc. the 5th International Conference on Information Security Practice and Experience, April 2009, pp.13-23.
[37] Ibraimi L, Tang Q, Hartel P, Jonker W. Efficient and provable secure ciphertext-policy attribute-based encryption schemes. In Proc. the 5th International Conference on Information Security Practice and Experience, April 2009, pp.1-12.
[38] Islam M S, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption:Ramification, attack and mitigation. In Proc. the 19th Annual Network & Distributed System Security Symposium, February 2012, Article No. 12.
[39] Liu C, Zhu L, Wang M Z, Tan Y. Search pattern leakage in searchable encryption:Attacks and new construction. Information Sciences, 2014, 265:176-188.
[40] Gabrilovich E, Markovitch S. Computing semantic relatedness of words and texts in Wikipedia-derived semantic space. In Proc. the 20th International Joint Conference on Artificial Intelligence, January 2006, pp.1606-1611.
[41] Egozi O, Markovitch S, Gabrilovich E. Concept-based information retrieval using explicit semantic analysis. ACM Transactions on Information Systems, 2011, 29(2):Article No. 8.
[42] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on Computing, 2014, 43(2):831-871.
[43] Smart N P, Vercauteren F. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Proc. International Workshop on Public Key Cryptography, May 2010, pp.420-443.
[44] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. In Proc. the 52nd Annual Symposium on Foundations of Computer Science, October 2011, pp.97-106.
[45] Naveed M, Prabhakaran M, Gunter C A. Dynamic searchable encryption via blind storage. In Proc. the 2014 IEEE Symposium on Security and Privacy, May 2014, pp.639-654.
[1] Leo Mendiboure, Mohamed-Aymen Chalouf, Francine Krief. 车辆环境中边缘运算的应用：对比研究和主要问题[J]. 计算机科学技术学报, 2019, 34(4): 869-886.
[2] Jiang Rong, Tao Qin, Bo An. 基于长远利益和竞争优化的云计算定价[J]. 计算机科学技术学报, 2019, 34(3): 645-656.
[3] Yang Li, Wen-Zhuo Song, Bo Yang. 一种针对大规模文本处理的基于随机变分推理的并行在线监督主题模型[J]. 计算机科学技术学报, 2018, 33(5): 1007-1022.
[4] Bao-Kun Zheng, Lie-Huang Zhu, Meng Shen, Feng Gao, Chuan Zhang, Yan-Dong Li, Jin. 基于区块链的可扩展和隐私保护的数据共享[J]. , 2018, 33(3): 557-567.
[5] An-Zhen Zhang, Jian-Zhong Li, Hong Gao, Yu-Biao Chen, Heng-Zhao Ma, Mohamed Jawa. CrowdOLA:重复数据上基于众包的在线聚集查询系统[J]. , 2018, 33(2): 366-379.
[6] Wei-Qing, Liu Jing Li. 面向仅有稀疏数据的移动云应用的一种自动化性能预测方法[J]. , 2017, 32(5): 936-956.
[7] Yuhun Jun, Jaemin Lee, Euiseong Seo. 一种基于分布式共享存储的计算迁移模式的远程I/O支持的评估方法[J]. , 2017, 32(5): 957-973.
[8] Dong-Gang Cao, Bo An, Pei-Chang Shi, Huai-Min Wang. 虚拟专用云:云际计算下的新型云服务[J]. , 2017, 32(2): 211-218.
[9] Yun-Gang Bao, Sa Wang. 面向软件定义云计算的标签化冯诺依曼体系结构[J]. , 2017, 32(2): 219-223.
[10] Zuo-Ning Chen, Kang Chen, Jin-Lei Jiang, Lu-Fei Zhang, Song Wu, Zheng-Wei Qi, Ch. 云操作系统演进:从技术到生态[J]. , 2017, 32(2): 224-241.
[11] Bin-Lei Cai, Rong-Qi Zhang, Xiao-Bo Zhou, Lai-Ping Zhao, Ke-Qiu Li. 体验可用性:面向尾延迟的软件定义的云计算的可用性[J]. , 2017, 32(2): 250-257.
[12] Xian-Mang He, Xiaoyang Sean Wang, Member, CCF, ACM, IEEE, Dong Li, Yan-Ni Hao. 半同构泛化:改进同构泛化在云计算中的隐私保护[J]. , 2016, 31(6): 1124-1135.
[13] Farrukh Nadeem, Rizwan Qaiser. 三个私有云计算软件平台的早期评估与比较[J]. , 2015, 30(3): 639-654.
[14] Shu-Sheng Guo, Zi-Mu Yuan, Ao-Bing Sun, Qiang Yue. 一种基于数据虚拟化的新型ETL方法[J]. , 2015, 30(2): 311-323.
[15] 邱杰凡, 李栋, 石海龙, 侯陈达, 崔莉. EasiSMP：一种支持REST资源运行时繁殖的编程架构[J]. , 2014, 29(2): 194-204.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 朱明远;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] 鞠九滨; 王勇; 尹玉;. Scheduling PVM Tasks[J]. , 1997, 12(2): 167 -176 .
[3] 迟学斌;. Parallel Implementation of Linear Algebra Problems on Dawning-1000[J]. , 1998, 13(2): 141 -146 .
[4] 傅育熙;. Symmetric π-Calculus[J]. , 1998, 13(3): 202 -208 .
[5] 吴虹; 聂旭民;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[6] 顾静; 帅典勋;. A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm[J]. , 1999, 14(6): 572 -579 .
[7] . 半封闭数据立方体：一种有效平衡数据立方体体积和查询响应时间的实现方法[J]. , 2005, 20(3): 367 -372 .
[8] . 关于线程上下文切换的验证研究[J]. , 2010, 25(4): 827 -840 .
[9] . 在Godson-T上对Stencil计算的优化[J]. , 2010, 25(4): 886 -894 .
[10] Min-Yi Guo, Zi-Li Shao, Edwin Hsing-Mean Sha. [J]. , 2011, 26(3): 373 -374 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：