AbstractsComputer Science

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.