Secure Indexes

[jmpzero]

Secure Indexes

• Author: Eu-Jin Goh (eujin@cs.stanford.edu)
• Links: https://ia.cr/2003/216 / https://crypto.stanford.edu/~eujin/papers/secureindex/
• Abstract: [1]
• PDF: [0]

KW

[0] https://eprint.iacr.org/2003/216.pdf
[1]
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.