Paper 2003/216

Secure Indexes

Eu-Jin Goh


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

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Private Data StructuresSearching on Encrypted Data
Contact author(s)
eujin @ cs stanford edu
2004-03-16: last of 10 revisions
2003-10-09: received
See all versions
Short URL
Creative Commons Attribution


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