2012 Articles

Usable Secure Private Search

Raykova, Mariana Petrova; Cui, Ang; Vo, Binh D.; Liu, Bin; Malkin, Tal G.; Bellovin, Steven Michael; Stolfo, Salvatore

Real-world applications commonly require untrusting parties to share sensitive information securely. This article describes a secure anonymous database search (SADS) system that provides exact keyword match capability. Using a new reroutable encryption and the ideas of Bloom filters and deterministic encryption, SADS lets multiple parties efficiently execute exact-match queries over distributed encrypted databases in a controlled manner. This article further considers a more general search setting allowing similarity searches, going beyond existing work that considers similarity in terms of error tolerance and Hamming distance. This article presents a general framework, built on the cryptographic and privacy-preserving guarantees of the SADS primitive, for engineering usable private secure search systems.