AbstractsComputer Science

Security and Privacy in Search Services

by Peng Wang

Institution: University of California – Riverside
Department: Computer Science
Year: 2014
Keywords: Computer science; Privacy; Search; Security
Record ID: 2055402
Full text PDF: http://www.escholarship.org/uc/item/2mc9n20d


In the first part of this dissertation, we show how to execute range queries securelyand efficiently on encrypted databases in the cloud. Current methods provideeither security or efficiency, but not both. Many schemes even reveal the orderingof encrypted tuples, which, as we show, allows adversaries to estimate plaintextvalues accurately.We present the \widehat{R}-tree, a hierarchical encrypted index that may be securelyplaced in the cloud, and searched efficiently. It is based on a mechanism we designfor encrypted halfspace range queries in Rd, using Asymmetric Scalar-productPreserving Encryption. Data owners can tune the \widehat{R}-tree parameters to achievedesired security-efficiency tradeoffs. We also present extensive experiments toevaluate \widehat{R}-tree performance. Our results show that \widehat{R}-tree queries are efficient onencrypted databases, and reveal far less information than competing methods.In the second part, we propose a new query obfuscation scheme to protectuser privacy in key word search. Text-based search queries reveal user intent tothe search engine, compromising privacy. Topical Intent Obfuscation (TIO) is a promising new approach to preserving user privacy. TIO masks topical intentby mixing real user queries with dummy queries matching various different topics.Dummy queries are generated using a Dummy Query Generation Algorithm(DGA).We demonstrate various shortcomings in current TIO schemes, and show howto correct them. Current schemes assume that DGA details are unknown to theadversary. We argue that this is a flawed assumption, and show how DGA detailscan be used to construct efficient attacks on TIO schemes, using an iterative DGAas an example. Our extensive experiments on real data sets show that our attackscan flag up to 80% of dummy queries. We also propose HDGA, a new DGA thatwe prove to be immune to the attacks based on DGA semantics that we describe.