Oblivious Keyword Search

Wakaha Ogata; Kaoru Kurosawa

Paper 2002/182

Oblivious Keyword Search

Wakaha Ogata and Kaoru Kurosawa

Abstract

In this paper, we introduce a notion of Oblivious Keyword Search ( $O K S$ ). Let $W$ be the set of possible keywords. In the commit phase, a database supplier $T$ commits $n$ data. In each transfer subphase, a user can choose a keyword adaptively and find without revealing to , where is the set of all data which includes as a keyword. We then show two efficient protocols such that the size of the commitments is only regardless of the size of , where is the size of each data. It is formally proved that learns nothing more and gains no information on the keywords which searched. We further present a more efficient adaptive protocol than the previous one as an application of our first protocol.

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Journal of Complexity, Vol.20 [2-3], pp. 356-371 (2004)
Keywords: oblivious transfer
Contact author(s): kurosawa @ cis ibaraki ac jp
History: 2004-03-09: revised; 2002-12-01: received; See all versions
Short URL: https://ia.cr/2002/182
License: CC BY

BibTeX

@misc{cryptoeprint:2002/182,
      author = {Wakaha Ogata and Kaoru Kurosawa},
      title = {Oblivious Keyword Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/182},
      year = {2002},
      url = {https://eprint.iacr.org/2002/182}
}