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: ia.cr/2016/801
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]