Efficient conjunctive keyword search on encrypted data storage system

Jin Wook Byun, Dong Hoon Lee, Jongin Lim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

81 Citations (Scopus)


We study conjunctive keyword search scheme allowing for remote search of data containing each of several keywords on encrypted data storage system. A data supplier first uploads encrypted data on a storage system, and then a user of the storage system searches data containing keywords over encrypted data hence insider (such as an administrator of the storage system) and outsider attackers do not learn anything else about the data. Recently, Golle et al. first suggested conjunctive keyword search scheme, but the communication and storage costs linearly depend on the number of stored data in the database, hence it is not really suitable for a large scale database. In this paper, we propose an efficient conjunctive keyword search scheme over encrypted data in aspects of communication and storage costs. Concretely, we reduce the storage cost of a user and the communication cost between a user and a data supplier to the constant amounts. We formally define security model for a conjunctive keyword search scheme and prove that the proposed scheme is secure under the decisional bilinear Diffie-Hellman (DBDH) assumption in the random oracle model.

Original languageEnglish
Title of host publicationPublic Key Infrastructure
Subtitle of host publicationThird European PKI Workshop - Theory and Practice, EuroPKI 2006, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540351515, 9783540351511
Publication statusPublished - 2006
EventThird European PKI Workshop, Public Key Infrastructure - Theory and Practice, EuroPKI 2006 - Turin, Italy
Duration: 2006 Jun 192006 Jun 20

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherThird European PKI Workshop, Public Key Infrastructure - Theory and Practice, EuroPKI 2006


  • Conjunctive keyword search over encrypted data
  • Database security and privacy

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient conjunctive keyword search on encrypted data storage system'. Together they form a unique fingerprint.

Cite this