In contrast, our solution provides a realistic and practical trade-off between performance and privacy by efficiently supporting very large databases at the cost of moderate and well-defined leakage to the outsourced server (leakage is in the form of data access patterns, never as direct exposure of plaintext data or searched values). A key aspect of our protocols is that it allows the searcher to pivot its conjunctive search on the estimated least frequent keyword in the conjunction. We show that a Decisional Diffie-Hellman (DDH) based pseudo-random function can be used not just to implement search tokens but also to hide query access pattern of non-pivot, and hence possibly highly frequent, keywords in conjunctive queries. We present a formal cryptographic analysis of the privacy and security of our protocols and establish precise upper bounds on the allowed leakage.
To demonstrate the real-world practicality of our approach, we provide performance results of a prototype applied to several large representative data sets.
Category / Keywords: cryptographic protocols / Encrypted search, privacy,implementation Publication Info: To be published: Crypto'2013. Date: received 28 Mar 2013, last revised 16 Aug 2013 Contact author: hugo at ee technion ac il Available format(s): PDF | BibTeX Citation Version: 20130816:211344 (All versions of this report) Short URL: ia.cr/2013/169 Discussion forum: Show discussion | Start new discussion