On a private search problem

Abstract

"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.

"En el problema de búsqueda privada que se estudia en esta tesis, copias de una base de datos están guardadas con varios servidores. Un usuario tiene un archivo privado y desea conseguir cierto subconjunto de la base de datos que consiste de archivos parecidos (o 'cerca' con respecto a la distancia de Hamming) al suyo, revelando tan poco como sea posible sobre su archivo privado. Primero, introducimos formalmente el problema y mostramos su relación con otro problema bien conocido de 'Private Information Retrieval'. Después analizamos una clase particular de estrategias de búsqueda: Estrategias de teoría de conjuntos. Damos un límite superior para la razón de privacidad por bits descargados en el caso de un solo servidor y demostramos que un límite parecido no existe en el caso de varios servidores. Por último, introducimos una nueva medida de privacidad de la cual sospechamos que existe un límite para la razón de privacidad por bits descargados. Incluimos unos primeros intentos de demostrar la existencia de tal límite."--Tomado del Formato de Documento de Grado.