Cryptology ePrint Archive: Report 2016/801

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

Gizem S. Çetin and Wei Dai and Yarkın Doröz and 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.

Category / Keywords: fully homomorphic encryption, privacy preserving applications, encrypted web search

Date: received 21 Aug 2016

Contact author: gscetin at wpi edu

Available format(s): PDF | BibTeX Citation

Version: 20160824:141218 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]