Una forma más rápida de preservar la privacidad en línea

El cómputo del servidor en SimplePIR. Cada celda representa un elemento Z? y × denota la multiplicación de matrices. El servidor realiza la mayor parte de su trabajo en un único paso de preprocesamiento. A partir de entonces, el servidor puede responder a la consulta de cada cliente con una fase en línea ligera. Crédito: Un servidor por el precio de dos: recuperación de información privada simple y rápida en un solo servidor (2022).

Buscar en Internet puede revelar información que un usuario preferiría mantener en privado. Por ejemplo, cuando alguien busca síntomas médicos en línea, podría revelar sus condiciones de salud a Google, a una base de datos médica en línea como WebMD, y quizás a cientos de anunciantes y socios comerciales de estas empresas.

Durante décadas, los investigadores han estado elaborando técnicas que permiten a los usuarios buscar y recuperar información de una base de datos de forma privada, pero estos métodos siguen siendo demasiado lentos para ser utilizados de manera efectiva en la práctica.

Los investigadores del MIT ahora han desarrollado un esquema para la recuperación de información privada que es unas 30 veces más rápido que otros métodos comparables. Su técnica permite a un usuario buscar en una base de datos en línea sin revelar su consulta al servidor. Además, está impulsado por un algoritmo simple que sería más fácil de implementar que los enfoques más complicados del trabajo anterior.

Su técnica podría permitir la comunicación privada al evitar que una aplicación de mensajería sepa lo que dicen los usuarios o con quién están hablando. También podría usarse para obtener anuncios en línea relevantes sin que los servidores de publicidad conozcan los intereses de los usuarios.

«Este trabajo se trata realmente de devolver a los usuarios algo de control sobre sus propios datos. A la larga, nos gustaría que navegar por la web fuera tan privado como navegar por una biblioteca. Este trabajo aún no logra eso, pero comienza a construir las herramientas que nos permiten hacer este tipo de cosas de manera rápida y eficiente en la práctica», dice Alexandra Henzinger, estudiante de posgrado en informática y autora principal de un artículo que presenta la técnica.

Preservar la privacidad

Los primeros esquemas para la recuperación de información privada fueron desarrollados en la década de 1990, en parte por investigadores del MIT. Estas técnicas permiten a un usuario comunicarse con un servidor remoto que contiene una base de datos y leer registros de esa base de datos sin que el servidor sepa lo que está leyendo el usuario.

Para preservar la privacidad, estas técnicas obligan al servidor a tocar cada uno de los elementos de la base de datos, por lo que no puede saber qué entrada está buscando un usuario. Si un área se deja intacta, el servidor aprenderá que el cliente no está interesado en ese artículo. Pero tocar cada elemento cuando puede haber millones de entradas en la base de datos ralentiza el proceso de consulta.

Para acelerar las cosas, los investigadores del MIT desarrollaron un protocolo, conocido como PIR simple, en el que el servidor realiza gran parte del trabajo criptográfico subyacente por adelantado, incluso antes de que un cliente envíe una consulta. Este paso de preprocesamiento produce una estructura de datos que contiene información comprimida sobre el contenido de la base de datos y que el cliente descarga antes de enviar una consulta.

En cierto sentido, esta estructura de datos es como una pista para el cliente sobre lo que hay en la base de datos.

«Una vez que el cliente tiene esta pista, puede realizar una cantidad ilimitada de consultas, y estas consultas serán mucho más pequeñas tanto en el tamaño de los mensajes que está enviando como en el trabajo que necesita que haga el servidor. Esto es lo que hace que Simple PIR sea mucho más rápido», explica Henzinger.

Pero la pista puede ser de tamaño relativamente grande. Por ejemplo, para consultar una base de datos de 1 gigabyte, el cliente necesitaría descargar una sugerencia de 124 megabytes. Esto aumenta los costos de comunicación, lo que podría dificultar la implementación de la técnica en dispositivos del mundo real.

Para reducir el tamaño de la pista, los investigadores desarrollaron una segunda técnica, conocida como Doble PIR, que básicamente implica ejecutar el esquema Simple PIR dos veces. Esto produce una sugerencia mucho más compacta que tiene un tamaño fijo para cualquier base de datos.

Usando Double PIR, la sugerencia para una base de datos de 1 gigabyte sería solo de 16 megabytes.

“Nuestro esquema Double PIR funciona un poco más lento, pero tendrá costos de comunicación mucho más bajos. Para algunas aplicaciones, esto será una compensación deseable”, dice Henzinger.

Alcanzando el límite de velocidad

Probaron los esquemas Simple PIR y Double PIR aplicándolos a una tarea en la que un cliente busca auditar una información específica sobre un sitio web para garantizar que sea seguro visitarlo. Para preservar la privacidad, el cliente no puede revelar el sitio web que está auditando.

La técnica más rápida de los investigadores pudo preservar con éxito la privacidad mientras se ejecutaba a unos 10 gigabytes por segundo. Los esquemas anteriores solo podían lograr un rendimiento de alrededor de 300 megabytes por segundo.

Muestran que su método se acerca al límite de velocidad teórico para la recuperación de información privada: es casi el esquema más rápido posible que se puede construir en el que el servidor toca todos los registros de la base de datos, agrega Corrigan-Gibbs.

Además, su método solo requiere un único servidor, lo que lo hace mucho más simple que muchas técnicas de alto rendimiento que requieren dos servidores separados con bases de datos idénticas. Su método superó estos protocolos más complejos.

«He estado pensando en estos esquemas durante algún tiempo, y nunca pensé que esto podría ser posible a esta velocidad. El folclore decía que cualquier esquema de un solo servidor va a ser muy lento. Este trabajo pone toda la noción de cabeza. , dice Corrigan-Gibbs.

Si bien los investigadores han demostrado que pueden hacer que los esquemas PIR sean mucho más rápidos, aún queda trabajo por hacer antes de que puedan implementar sus técnicas en escenarios del mundo real, dice Henzinger. Les gustaría reducir los costos de comunicación de sus esquemas y al mismo tiempo permitirles alcanzar altas velocidades. Además, quieren adaptar sus técnicas para manejar consultas más complejas, como consultas SQL generales, y aplicaciones más exigentes, como una búsqueda general en Wikipedia. Y, a largo plazo, esperan desarrollar mejores técnicas que puedan preservar la privacidad sin requerir que un servidor toque cada elemento de la base de datos.

«Escuché a personas afirmar enfáticamente que PIR nunca será práctico. Pero nunca apostaría en contra de la tecnología. Esa es una lección optimista que aprender de este trabajo. Siempre hay formas de innovar», dijo el autor principal Vinod Vaikuntanathan, profesor de EECS. e investigador principal en CSAIL, dice.

«Este trabajo mejora significativamente el costo práctico de la recuperación de información privada. Si bien se sabía que los esquemas PIR de bajo ancho de banda implican criptografía de clave pública, que suele ser mucho más lenta que la criptografía de clave privada, este trabajo desarrolla un ingenioso método para cerrar la brecha Esto se hace haciendo un uso inteligente de las propiedades especiales de un esquema de cifrado de clave pública debido a Regev para llevar la gran mayoría del trabajo computacional a un paso de precálculo, en el que el servidor calcula una breve ‘pista ‘ sobre la base de datos», dice Yuval Ishai, profesor de informática en Technion (el Instituto de Tecnología de Israel), que no participó en el estudio.

«Lo que hace que su enfoque sea particularmente atractivo es que la misma sugerencia se puede usar una cantidad ilimitada de veces, por cualquier cantidad de clientes. Esto hace que el costo (moderado) de calcular la sugerencia sea insignificante en un escenario típico donde se accede a la misma base de datos muchos veces.»

Esta historia se vuelve a publicar por cortesía de MIT News (web.mit.edu/newsoffice/), un sitio popular que cubre noticias sobre investigación, innovación y enseñanza del MIT.