Title :
Privacy Preserving String Matching for Cloud Computing
Author :
Bezawada, Bruhadeshwar ; Liu, Alex X. ; Jayaraman, Bargav ; Wang, Ann L. ; Rui Li
Author_Institution :
Nat. Key Lab. for Novel Software Technol., Nanjing Univ., Nanjing, China
fDate :
June 29 2015-July 2 2015
Abstract :
Cloud computing has become indispensable in providing highly reliable data services to users. But, there are major concerns about the privacy of the data stored on cloud servers. While encryption of data provides sufficient protection, it is challenging to support rich querying functionality, such as string matching, over the encrypted data. In this work, we present the first ever symmetric key based approach to support privacy preserving string matching in cloud computing. We describe an efficient and accurate indexing structure, the PASS tree, which can execute a string pattern query in logarithmic time complexity over a set of data items. The PASS tree provides strong privacy guarantees against attacks from a semi-honest adversary. We have comprehensively evaluated our scheme over large real-life data, such as Wikipedia and Enron documents, containing up to 100000 keywords, and show that our algorithms achieve pattern search in less than a few milliseconds with 100% accuracy. Furthermore, we also describe a relevance ranking algorithm to return the most relevant documents to the user based on the pattern query. Our ranking algorithm achieves 90%+ above precision in ranking the returned documents.
Keywords :
cloud computing; computational complexity; cryptography; data privacy; document handling; indexing; query processing; string matching; tree data structures; Enron documents; PASS tree; Wikipedia; cloud computing; cloud servers; data encryption; data items; data services; indexing structure; logarithmic time complexity; privacy preserving string matching; relevance ranking algorithm; returned document ranking; semi honest adversary; string pattern query; symmetric key based approach; Cloud computing; Complexity theory; Cryptography; Indexes; Pattern matching; Privacy; Servers; Cloud Storage; Data Privacy; IND-CKA; Prefix Matching; SSE; Secure Index; String Matching;
Conference_Titel :
Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on
Conference_Location :
Columbus, OH
DOI :
10.1109/ICDCS.2015.68