Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (1): 133-154.doi: 10.1007/s11390-019-1903-2

Special Issue: Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

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.

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. Edge Computing Based Applications in Vehicular Environments: Comparative Study and Main Issues [J]. Journal of Computer Science and Technology, 2019, 34(4): 869-886.
[2] Jiang Rong, Tao Qin, Bo An. Competitive Cloud Pricing for Long-Term Revenue Maximization [J]. Journal of Computer Science and Technology, 2019, 34(3): 645-656.
[3] Yang Li, Wen-Zhuo Song, Bo Yang. Stochastic Variational Inference-Based Parallel and Online Supervised Topic Model for Large-Scale Text Processing [J]. Journal of Computer Science and Technology, 2018, 33(5): 1007-1022.
[4] Ji-Zhou Luo, Sheng-Fei Shi, Guang Yang, Hong-Zhi Wang, Jian-Zhong Li. O2iJoin: An Efficient Index-Based Algorithm for Overlap Interval Join [J]. Journal of Computer Science and Technology, 2018, 33(5): 1023-1038.
[5] Bao-Kun Zheng, Lie-Huang Zhu, Meng Shen, Feng Gao, Chuan Zhang, Yan-Dong Li, Jing Yang. Scalable and Privacy-Preserving Data Sharing Based on Blockchain [J]. , 2018, 33(3): 557-567.
[6] An-Zhen Zhang, Jian-Zhong Li, Hong Gao, Yu-Biao Chen, Heng-Zhao Ma, Mohamed Jaward Bah. CrowdOLA: Online Aggregation on Duplicate Data Powered by Crowdsourcing [J]. , 2018, 33(2): 366-379.
[7] Qin Liu, Yuhong Guo, Jie Wu, Guojun Wang. Effective Query Grouping Strategy in Clouds [J]. Journal of Computer Science and Technology, 2017, 32(6): 1231-1249.
[8] Wei-Qing, Liu Jing Li. An Approach to Automatic Performance Prediction for Cloud-enhanced Mobile Applications with Sparse Data [J]. , 2017, 32(5): 936-956.
[9] Yuhun Jun, Jaemin Lee, Euiseong Seo. Evaluation of Remote-I/O Support for a DSM-Based Computation Offloading Scheme [J]. , 2017, 32(5): 957-973.
[10] Dong-Gang Cao, Bo An, Pei-Chang Shi, Huai-Min Wang. Providing Virtual Cloud for Special Purposes on Demand in JointCloud Computing Environment [J]. , 2017, 32(2): 211-218.
[11] Zuo-Ning Chen, Kang Chen, Jin-Lei Jiang, Lu-Fei Zhang, Song Wu, Zheng-Wei Qi, Chun-Ming Hu, Yong-Wei Wu, Yu-Zhong Sun, Hong Tang, Ao-Bing Sun, Zi-Lu Kang. Evolution of Cloud Operating System: From Technology to Ecosystem [J]. , 2017, 32(2): 224-241.
[12] Bin-Lei Cai, Rong-Qi Zhang, Xiao-Bo Zhou, Lai-Ping Zhao, Ke-Qiu Li. Experience Availability: Tail-Latency Oriented Availability in Software-Defined Cloud Computing [J]. , 2017, 32(2): 250-257.
[13] Xian-Mang He, Xiaoyang Sean Wang, Member, CCF, ACM, IEEE, Dong Li, Yan-Ni Hao. Semi-Homogenous Generalization:Improving Homogenous Generalization for Privacy Preservation in Cloud Computing [J]. , 2016, 31(6): 1124-1135.
[14] Xiao-Fen Wang, Yi Mu, Rongmao Chen, Xiao-Song Zhang. Secure Channel Free ID-Based Searchable Encryption for Peer-to-Peer Group [J]. , 2016, 31(5): 1012-1027.
[15] Farrukh Nadeem, Rizwan Qaiser. An Early Evaluation and Comparison of Three Private Cloud Computing Software Platforms [J]. , 2015, 30(3): 639-654.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] Ju Jiubin; Wang Yong; Yin Yu;. Scheduling PVM Tasks[J]. , 1997, 12(2): 167 -176 .
[3] Chi Xuebin;. Parallel Implementation of Linear Algebra Problems on Dawning-1000[J]. , 1998, 13(2): 141 -146 .
[4] Fu Yuxi;. Symmetric π-Calculus[J]. , 1998, 13(3): 202 -208 .
[5] Wu Hong; Nie Xumin;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[6] GU Jing; SHUAI Dianxun;. A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm[J]. , 1999, 14(6): 572 -579 .
[7] Sheng-En Li and Shan Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time[J]. , 2005, 20(3): 367 -372 .
[8] Yu Guo(郭 宇), Xin-Yu Jiang(蒋信予), and Yi-Yun Chen(陈意云). Certification of Thread Context Switching[J]. , 2010, 25(4): 827 -840 .
[9] Hui-Min Cui(崔慧敏), Lei Wang(王 蕾), Dong-Rui Fan(范东睿), Member CCF, IEEE and Xiao-Bing Feng(冯晓兵). Landing Stencil Code on Godson-T[J]. , 2010, 25(4): 886 -894 .
[10] Min-Yi Guo, Zi-Li Shao, Edwin Hsing-Mean Sha. Preface[J]. , 2011, 26(3): 373 -374 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved