On a private search problem
Martin Felix Wosnitzka · instname:Universidad de los Andes · 2024
"In the Private Search problem we study, copies of a database are stored on several non-communicating servers. A user wishes to retrieve a subset of files of the database that are similar (i.e. close in Hamming Space) to a privately chosen user file, while having the servers learn as little as possible about the user file. First, we formally introduce the problem and show its relation to the well-known Private Information Retrieval Problem. Then we proceed to study a specific class of search strategies: Set theoretical search strategies. A general bound on the privacy to download ratio for these strategies is given in the case of a single server and it is shown that a similar bound can not be found in the case of several servers. Finally, we introduce a new measure of privacy for which we suspect a bound on the privacy to download ratio exists, and show first attempts of trying to prove the bound."--Tomado del Formato de Documento de Grado.