Paper 2002/182
Oblivious Keyword Search
Wakaha Ogata and Kaoru Kurosawa
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.
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},
note = {\url{https://eprint.iacr.org/2002/182}},
url = {https://eprint.iacr.org/2002/182}
}
