Paper 2016/801

Blind Web Search: How far are we from a privacy preserving search engine?

Gizem S. Çetin, Wei Dai, Yarkın Doröz, William J. Martin, and Berk Sunar

Abstract

Recent rapid progress in fully homomorphic encryption (FHE) and somewhat homomorphic encryption (SHE) has catalyzed renewed efforts to develop efficient privacy preserving protocols. Several works have already appeared in the literature that provide solutions to these problems by employing FHE or SHE techniques. In this work, we focus on a natural application where privacy is a major concern: web search. An estimated 5 billion web queries are processed by the world's leading search engines each day. It is no surprise, then, that privacy-preserving web search was proposed as the paragon FHE application in Gentry's seminal FHE paper. Indeed, numerous proposals have emerged in the intervening years that attack various privatized search problems over encrypted user data, e.g. private information retrieval (PIR). Yet, there is no known work that focuses on implementing a completely blind web search engine using an FHE/SHE construction. In this work, we focus first on single keyword queries with exact matches, aiming toward real-world viability. We then discuss multiple-keyword searches and tackle a number of issues currently hindering practical implementation, such as communication and computational efficiency.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
fully homomorphic encryptionprivacy preserving applicationsencrypted web search
Contact author(s)
gscetin @ wpi edu
History
2016-08-24: received
Short URL
https://ia.cr/2016/801
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/801,
      author = {Gizem S.  Çetin and Wei Dai and Yarkın Doröz and William J.  Martin and Berk Sunar},
      title = {Blind Web Search: How far are we from a privacy preserving search engine?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/801},
      year = {2016},
      url = {https://eprint.iacr.org/2016/801}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.