Vol 8, No 4 (2017) > Electrical, Electronics and Computer Engineering >

User Verifiable Multiple Keyword Search Scheme using the Merkle Tree for Outsourced Data in the Cloud

Devi Thiyagarajan, Ganesan R


Abstract: Cloud computing has revolutionized the IT industry by offering huge storage for data outsourcing and also for computation. Various security issues concerned with security and privacy of data arise in the context of data outsourcing. The framework enables clients to outsource encrypted data to the cloud, enables users to retrieve preferred documents using multiple keywords and allows the user to verify the response from the server. The strength of the proposed model relies on the discrete logarithmic problem of Hyper Elliptic Curve Cryptography (HECC) and the security of Merkle trees. The paper proposes a user verifiable multi-keyword search scheme, which focuses on: (i) construction of inverted index for the documents with keywords; (ii) index and document encryption by HECC; (iii) index and document authentication by the Merkle tree; and (iv) verification of the accuracy of response from server by top hash or root hash value of the Merkle tree. Security analysis and results demonstrate the correctness of proposed multiple keyword search (MKS) scheme. The search algorithm combined with the hash value verification process by the Merkle tree is strong enough to provide data security, privacy, and integrity. The proposed model reduces the storage overhead on both the client’s and user’s side. As the number of documents increases, the retrieval time is less, which reduces the storage overhead on both sides.
Keywords: Client; Cloud; Merkle tree; Search; Verifiable

Full PDF Download


Attrapadung, N., Libert, B., 2010. Functional Encryption for Inner Product: Achieving Constant-size Ciphertexts with Adaptive Security or Support for Negation. In: Proceedings of PKC, pp. 384–402

Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G., 2004. Public Key Encryption with Keyword Search. In: Proceedings of EUROCRYPT, pp. 506–522

Cao, N., Wang, C., Li, M., Ren, K., Lou, W., 2011. Privacy-preserving Multi-keyword Ranked Search over Encrypted Cloud Data. In: Proceedings of IEEE INFOCOM, pp. 829–837

Cao, Q., Fujita S., 2014. Cost-effective Replication Schemes for Query Load Balancing in DHT-based Peer-to-peer File Searches. Journal of Information Processing Systems, Volume 10, pp. 628–645

Chai Q., Gong, G., 2012. Verifiable Symmetric Searchable Encryption for Semi-Honest-but-Curious Cloud Servers, In: IEEE International Conference on Communications (ICC), 2012, pp. 917–922

Chang, Y.C., Mitzenmacher, M., 2005. Privacy Preserving Keyword Searches on Remote Encrypted Data. In: Proceedings of ACNS, pp. 391–421

Cheng, R., Yan, J., Guan, C., Zhang, F., Ren, K., 2015. Verifiable Searchable Symmetric Encryption from Indistinguishability Obfuscation. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, ASIA CCS ’15, New York, NY, USA, ACM, pp. 621–626

Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R., 2006. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In: Proceedings of ACM CCS, pp. 79–88

Goh, E.J., 2003. Secure Indexes (2003), Cryptology ePrint Archive. Available online at http://eprint.iacr.org/2003/21

Hwang, Y., Lee, P., 2007. Public Key Encryption with Conjunctive Keyword Search and its Extension to a Multi-user system, In: Pairing, 2007

Kissel, Z. A., Wang, J., 2013. Verifiable Phrase Search over Encrypted Data Secure Against a Semi-honest-but-curious Adversary, In: IEEE 33rd International Conference on Distributed Computing Systems Workshops (ICDCSW), pp. 126–131

Lee, S. H., Lee I.Y., 2013. A Secure Index Management Scheme for Providing Data Sharing in Cloud Storage. Journal of Information Processing Systems, Volume 9, pp. 287–300

Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W., 2010. Computationally Efficient Searchable Symmetric Encryption. Secure Data Management, Volume 6358, pp. 87–100

Merkle, R. C., 1988. A Digital Signature Based on a Conventional Encryption Function. In: Advances in Cryptology–CRYPTO’87, Springer, pp. 369–378

Pang, H., Shen, J., Krishnan, R., 2010. Privacy-preserving Similarity-based Text Retrieval. ACM Transactions on Internet Technology, Volume 10(1), pp. 4:1–4:39

Salam, M.I., Yau, W.C., Chin, J.J., Heng, S.H., Ling, H.C., Phan, R.C.W., Poh, G.S., Tan, S.Y., Yap, W.S., 2015. Implementation of Searchable Symmetric Encryption for Privacy-preserving Keyword Search on Cloud Storage. Human-Centric Computing and Information Sciences, Volume 5(19), pp. 1–16

Shen E., Shi, E., Waters, B., 2009. Predicate Pivacy in Encryption Systems. In: Proceedings of TCC, pp. 457–473

Shi, E., Bethencourt, J., Chan, H., Song, D., Perrig A., 2007. Multi-dimensional Range Query over Encrypted Data. In: Proceedings of S & P, pp. 350–364

Song, D., Wagner, D., Perrig, A., 2000. Practical Techniques for Searches on Encrypted Data. In: Proceedings of S & P, pp. 44–55

Subashini, S., Kavitha, V., 2011. A survey on Security Issues in Service Delivery Models of Cloud Computing. Journal of Network and Computer Applications, Volume 34, pp. 1–11

Swaminathan, A., Mao, Y., Su, G.M., Gou, H., Varna, A.L., He, S., Wu, M., Oard, D.W., 2007. Confidentiality-preserving Rank-ordered Search. In: Proceedings of the 2007 ACM Workshop on Storage Security and Survivability, pp. 7–12

Wang, C., Cao, N., Ren, K., Lou, W., 2012. Enabling Secure and Efficient Ranked Keyword Search over Outsourced Cloud Data. IEEE Transactions on Parallel and Distributed Systems, Volume 23(8), pp. 1467–1479

Xu, L., Weng, C.Y., Yuan, L.P., Wu, M.-E., Sun, H.M., Tso, R., 2015. A Shareable Keyword Search over Encrypted Data in Cloud Computing. The Journal of Supercomputing, pp. 1–23

Yang, J.J., Li, J.Q., Niu, Y., 2015. A Hybrid Solution for Privacy Preserving Medical Data Sharing in the Cloud Environment. Future Generation Computer Systems, pp. 74–86

Zerr, S., Olmedilla, D., Nejdl, W., Siberski, W., 2009. Zerber+R – Top-k Retrieval from a Confidential Index. In: Proceedings of EDBT, pp. 439–449

Zheng, Q., Xu, S., Ateniese, G., 2014. VABKS: Verifiable Attribute-based Keyword Search over Outsourced Encrypted Data. In: INFOCOM, 2014 Proceedings IEEE, pp. 522–530