International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Secure Indexes

Eu-Jin Goh
Search ePrint
Search Google
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.
  title={Secure Indexes},
  booktitle={IACR Eprint archive},
  keywords={Private Data Structures, Searching on Encrypted Data},
  note={ eujin at cs stanford edu 12493 received 7 Oct 2003, last revised 16 Mar 2004},
  author={Eu-Jin Goh},