Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup

Mikhail Strizhov, Zachary Osman and Indrajit Ray
Additional contact information
Mikhail Strizhov: Computer Science Department, Colorado State University, Fort Collins, CO 80523, USA
Zachary Osman: Computer Science Department, Colorado State University, Fort Collins, CO 80523, USA
Indrajit Ray: Computer Science Department, Colorado State University, Fort Collins, CO 80523, USA

Future Internet, 2016, vol. 8, issue 3, 1-26

Abstract: Existing Searchable Encryption (SE) solutions are able to handle simple Boolean search queries, such as single or multi-keyword queries, but cannot handle substring search queries over encrypted data that also involve identifying the position of the substring within the document. These types of queries are relevant in areas such as searching DNA data. In this paper, we propose a tree-based Substring Position Searchable Symmetric Encryption (SSP-SSE) to overcome the existing gap. Our solution efficiently finds occurrences of a given substring over encrypted cloud data. Specifically, our construction uses the position heap tree data structure and achieves asymptotic efficiency comparable to that of an unencrypted position heap tree. Our encryption takes O ( k n ) time, and the resulting ciphertext is of size O ( k n ) , where k is a security parameter and n is the size of stored data. The search takes O ( m 2 + o c c ) time and three rounds of communication, where m is the length of the queried substring and o c c is the number of occurrences of the substring in the document collection. We prove that the proposed scheme is secure against chosen-query attacks that involve an adaptive adversary. Finally, we extend SSP-SSE to the multi-user setting where an arbitrary group of cloud users can submit substring queries to search the encrypted data.

Keywords: substring position search; searchable symmetric encryption; cloud computing; position heap tree (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1999-5903/8/3/28/pdf (application/pdf)
https://www.mdpi.com/1999-5903/8/3/28/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:8:y:2016:i:3:p:28-:d:73291

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().