TR-07-14: Simple Blind Search on Public-Key Encrypted Data

Abstract

We consider the problem of blind search on encrypted data, wherein servers are to perform a search service on the data without being able to discover the associated underlying search criteria. We focus on the case in which search is performed on an index of blinded (i.e. confidentiality-protected) keywords appended to the encrypted data or message. In recent years, several attempts have been made to provide such functionality using public-key encrypted keyword search (PEKS) schemes. We show that all PEKS schemes we are aware of fall to a generic dictionary attack which compromises the privacy of search keywords. This suggests revisiting the existing PEKS model. Given this motivation, we distinguish blind search on incoming encrypted data (largely the focus of previous work) from blind search on outgoing encrypted data (which addresses novel applications), and provide both a new model for blind keyword search, and a specific proposal fitting the model. Our proposal is both (time- and space-) efficient, and prevents dictionary attacks by search servers. The simple idea is to build search tokens using message authentication codes (MACs) keyed by user-specific strings (in essence, confounders). The keys are shared between the user and the party creating the search tokens, the latter being distinct from the search server. We also distinguish between systematic blind search (search on each incoming or outgoing message), and request-based blind search (search prompted by sporadic requests, as best resembles the only scheme we are aware of that provides blind search on public-key encrypted data, and does not fall to the aforementioned attack). We show how our specific proposal can be used to address both systematic and request-based blind search efficiently.

TR-07-14.pdf