Oblivious keyword search

In this paper, we introduce a notion of oblivious keyword search (OKS). Let W be the set of possible keywords. In the commit phase, a database supplier F commits n data. In each transfer subphase, a user u can choose a keyword w is an element of W adaptively and find Search(w) without revealing w to where Search(w) is the set of all data which includes w as a keyword. We then show two efficient protocols such that the size of the commitments is only O(nB) regardless of the size of W, where B is the size of each data. It is formally proved that V learns nothing more than search(w) and F gains no information on the keywords which W searched for. We further present a more efficient adaptive OTkn protocol than the previous one [19] as an application of our first OKS protocol. (C) 2003 Elsevier Inc. All rights reserved.