Paper 2003/216

Secure Indexes

Eu-Jin Goh

Abstract

A secure index is a data structure that allows a querier with a ``trapdoor'' for a word x to test in O(1) time only if the index contains x; The index reveals no information about its contents without valid trapdoors, and trapdoors can only be generated with a secret key. Secure indexes are a natural extension of the problem of constructing data structures with privacy guarantees such as those provided by oblivious and history independent data structures. In this paper, we formally define a secure index and formulate a security model for indexes known as semantic security against adaptive chosen keyword attack (IND-CKA). We also develop an efficient IND-CKA secure index construction called Z-IDX using pseudo-random functions and Bloom filters, and show how to use Z-IDX to implement searches on encrypted data. This search scheme is the most efficient encrypted data search scheme currently known; It provides O(1) search time per document, and handles compressed data, variable length words, and boolean and certain regular expression queries. The techniques developed in this paper can also be used to build encrypted searchable audit logs, private database query schemes, accumulated hashing schemes, and secure set membership tests.

Note: The latest version can always be found at http://crypto.stanford.edu/~eujin/papers/secureindex/

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
Private Data StructuresSearching on Encrypted Data
Contact author(s)
eujin @ cs stanford edu
History
2004-03-16: last of 10 revisions
2003-10-09: received
See all versions
Short URL
https://ia.cr/2003/216
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/216,
      author = {Eu-Jin Goh},
      title = {Secure Indexes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/216},
      year = {2003},
      url = {https://eprint.iacr.org/2003/216}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.