Recuperación de información privada

Describimos esquemas que permiten a un usuario acceder a k copias replicadas de una base de datos (k/spl ges/2) y recuperar información de forma privada almacenada en la base de datos. Esto significa que cada base de datos individual no recibe información sobre la identidad del elemento recuperado por el usuario. Para una única base de datos, lograr este tipo de privacidad requiere comunicar toda la base de datos, o n bits (donde n es el número de bits en la base de datos). Nuestros esquemas utilizan la replicación para obtener un ahorro sustancial. En particular, tenemos: Un esquema de dos bases de datos con una complejidad de comunicación de O(n/sup 1/3/). Un esquema para un número constante, k, de bases de datos con una complejidad de comunicación O(n/sup 1/k/). Un esquema para 1/3 log/sub 2/ n bases de datos con complejidad de comunicación polilogarítmica (en n).