International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Oblivious Keyword Search

Authors:
Wakaha Ogata
Kaoru Kurosawa
Download:
URL: http://eprint.iacr.org/2002/182
Search ePrint
Search Google
Abstract: 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 $T$ commits $n$ data. In each transfer subphase, a user $U$ can choose a keyword $w \in W$ adaptively and find $Search(w)$ without revealing $w$ to $T$, 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 $(nB)$ regardless of the size of $W$, where $B$ is the size of each data. It is formally proved that $U$ learns nothing more and $T$ gains no information on the keywords which $U$ searched. We further present a more efficient adaptive $OT_k^n$ protocol than the previous one as an application of our first $OKS$ protocol.
BibTeX
@misc{eprint-2002-11705,
  title={Oblivious Keyword Search},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / oblivious transfer},
  url={http://eprint.iacr.org/2002/182},
  note={Journal of Complexity, Vol.20 [2-3],  pp. 356-371 (2004) kurosawa@cis.ibaraki.ac.jp 12486 received 26 Nov 2002, last revised 8 Mar 2004},
  author={Wakaha Ogata and Kaoru Kurosawa},
  year=2002
}