Dissertation/Thesis Abstract

Encrypted Search: Enabling Standard Information Retrieval Techniques for Several New Secure Index Types While Preserving Confidentiality Against an Adversary With Access to Query Histories and Secure Index Contents
by Towell, Alexander R., M.S., Southern Illinois University at Edwardsville, 2015, 107; 1601582
Abstract (Summary)

Encrypted Search is a way for a client to store searchable documents on untrusted systems such that the untrusted system can obliviously search the documents on the client's behalf, i.e., the untrusted system does not know what the client is searching for nor what the documents contain. Several new secure index types (which enable Encrypted Search functionality) are designed and implemented, and then compared against each other and against the more typical Bloom filter-based secure index. We compare them with respect to several performance measures: time complexity, space complexity, and retrieval accuracy with respect to two rank-ordered search heuristics, MinDist* and BM25. In order to support these search heuristics, the secure indexes must store frequency and proximity information. We investigate the risk this poses to confidentiality and explore ways to mitigate said risk. Finally, we analyze the effect the false positive rate and secure index poisoning techniques have on both confidentiality and performance. Separately, we also simulate an adversary who has access to a history of hidden (encrypted) queries and design techniques that demonstrably mitigate the risk posed by this adversary, e.g., query obfuscation, without adversely effecting retrieval accuracy.

Supplemental Files

Some files may require a special program or browser plug-in. More Information

Indexing (document details)
Advisor: Fujinoki, Hiroshi
Commitee: Ercal, Gunes, Jacks, Tim
School: Southern Illinois University at Edwardsville
Department: Computer Science
School Location: United States -- Illinois
Source: MAI 55/02M(E), Masters Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Encrypted search, Information leaks, Perfect hash filter, Query obfuscation, Secure indexes, Trapdoors
Publication Number: 1601582
ISBN: 9781339134925