Criptógrafos diseñan un enfoque para la privacidad total de las búsquedas | Revista Quanta

Todos sabemos que debemos tener cuidado con los detalles que compartimos en línea, pero la información que buscamos también puede ser reveladora. Busque indicaciones para llegar en automóvil y nuestra ubicación será mucho más fácil de adivinar. Busque una contraseña entre un tesoro de datos comprometidos y corremos el riesgo de filtrarla nosotros mismos.

Estas situaciones alimentan una pregunta clave en criptografía: ¿Cómo se puede extraer información de una base de datos pública sin revelar nada sobre a qué se ha accedido? Es el equivalente a sacar un libro de la biblioteca sin que el bibliotecario sepa cuál.

Elaborar una estrategia que resuelva este problema, conocida como recuperación de información privada, es "un componente muy útil en una serie de aplicaciones que preservan la privacidad", dijo David Wu, criptógrafo de la Universidad de Texas, Austin. Desde la década de 1990, los investigadores han ido socavando la cuestión, mejorando las estrategias para acceder de forma privada a las bases de datos. Un objetivo importante, aún imposible con bases de datos grandes, es el equivalente a una búsqueda privada en Google, donde se puede examinar un montón de datos de forma anónima sin realizar ningún trabajo computacional pesado.

Ahora, tres investigadores han Elaborado una versión largamente buscada de recuperación de información privada y la amplió para construir una estrategia de privacidad más general. La obra, que recibió un Premio al mejor papel en junio en la anual Simposio de Teoría de la Computación, derriba una barrera teórica importante en el camino hacia una búsqueda verdaderamente privada.

"[Esto es] algo en criptografía que supongo que todos queríamos pero no creíamos que existiera", dijo Vinod Vaikuntanathan, un criptógrafo del Instituto de Tecnología de Massachusetts que no participó en el artículo. "Es un resultado histórico".

El problema del acceso a bases de datos privadas tomó forma en la década de 1990. Al principio, los investigadores asumieron que la única solución era escanear toda la base de datos durante cada búsqueda, lo que sería como hacer que un bibliotecario revise cada estante antes de regresar con su libro. Después de todo, si la búsqueda omitió alguna sección, el bibliotecario sabría que su libro no se encuentra en esa parte de la biblioteca.

Ese enfoque funciona bastante bien a escalas más pequeñas, pero a medida que la base de datos crece, el tiempo necesario para escanearla crece al menos proporcionalmente. A medida que se lee en bases de datos más grandes (e Internet es bastante grande), el proceso se vuelve prohibitivamente ineficiente.

A principios de la década de 2000, los investigadores comenzaron a sospechar que podrían sortear la barrera del escaneo completo “preprocesando” la base de datos. En términos generales, esto significaría codificar toda la base de datos como una estructura especial, de modo que el servidor pueda responder una consulta leyendo solo una pequeña parte de esa estructura. Un preprocesamiento lo suficientemente cuidadoso podría, en teoría, significar que un único servidor que aloja información solo realiza el proceso una vez, por sí solo, permitiendo a todos los futuros usuarios obtener información de forma privada sin ningún esfuerzo adicional.

Daniel Wichs, criptógrafo de la Universidad Northeastern y coautor del nuevo artículo, eso parecía demasiado bueno para ser verdad. Alrededor de 2011, empezó a intentar demostrar que este tipo de plan era imposible. "Estaba convencido de que no había manera de que esto se pudiera hacer", dijo.

Pero en 2017, dos grupos de investigadores publicado dE TRATAMIENTOS eso hizo que cambiara de opinión. Construyeron los primeros programas que podían realizar este tipo de recuperación de información privada, pero no pudieron demostrar que los programas fueran seguros. (Los criptógrafos demuestran la seguridad de un sistema al mostrar que romperlo es tan difícil como resolver algún problema difícil. Los investigadores no pudieron compararlo con un problema difícil canónico).

Entonces, incluso con sus esperanzas renovadas, Wichs asumió que cualquier versión segura de estos programas aún estaba muy lejos. En cambio, él y sus coautores... Wei-Kai Lin, ahora en la Universidad de Virginia, y Ethan Mook, también en Northeastern, trabajaron en problemas que pensaban que serían más fáciles, que involucraban casos en los que varios servidores alojaban la base de datos.

En los métodos que estudiaron, la información de la base de datos se puede transformar en una expresión matemática, que los servidores pueden evaluar para extraer la información. Los autores pensaron que podría ser posible hacer que ese proceso de evaluación sea más eficiente. Jugaron con una idea de 2011, cuando otros investigadores encontraron una manera de evaluar rápidamente dicha expresión preprocesándola, creando tablas de valores especiales y compactas que permiten omitir los pasos de evaluación normales.

Ese método no produjo ninguna mejora y el grupo estuvo a punto de darse por vencido, hasta que se preguntaron si esta herramienta realmente podría funcionar en el codiciado caso de un solo servidor. Vieron que eligieron un polinomio con suficiente cuidado y un único servidor podría preprocesarlo basándose en el resultado de 2011, generando el esquema de búsqueda seguro y eficiente que había reflexionado durante años. De repente, después de todo, habían resuelto el problema más difícil.

Al principio, los autores no lo creían. “Averigüemos qué hay de malo en esto”, recordó haber pensado Wichs. "Seguimos tratando de descubrir dónde se descompone".

Pero la solución se mantuvo: realmente habían descubierto una forma segura de preprocesar una base de datos de un solo servidor para que cualquiera pudiera extraer información en secreto. "Realmente está más allá de todo lo que esperábamos", dijo yuval ishai, un criptógrafo del Technion en Israel que no participó en este trabajo. Es un resultado que “ni siquiera fuimos lo suficientemente valientes para pedirlo”, dijo.

Después de construir su esquema de búsqueda secreta, los autores recurrieron al objetivo del mundo real de una búsqueda privada en Internet, que es más complicada que extraer fragmentos de información de una base de datos, dijo Wichs. El esquema de búsqueda privada por sí solo permite una versión de búsqueda privada similar a la de Google, pero requiere mucha mano de obra: usted mismo ejecuta el algoritmo de Google y extrae datos de Internet en secreto cuando es necesario. Wichs dijo que una búsqueda verdadera, en la que se envía una solicitud y se sienta mientras el servidor recopila los resultados, es en realidad un objetivo para un enfoque más amplio conocido como cifrado homomórfico, que disfraza los datos para que otra persona pueda manipularlos sin saber nada al respecto. .

Las estrategias típicas de cifrado homomórfico tendrían el mismo problema que la recuperación de información privada, recorriendo con dificultad todos los contenidos de Internet para cada búsqueda. Pero utilizando su método de búsqueda privada como andamiaje, los autores construyeron un nuevo esquema que ejecuta cálculos que se parecen más a los programas que usamos todos los días, extrayendo información de forma encubierta sin barrer todo Internet. Eso proporcionaría un aumento de eficiencia para las búsquedas en Internet y cualquier programa que necesite un acceso rápido a los datos.

Si bien el cifrado homomórfico es una extensión útil del esquema de búsqueda privada, dijo Ishai, considera que la recuperación de información privada es el problema más fundamental. La solución de los autores es el "bloque de construcción mágico", y su estrategia de cifrado homomórfico es una continuación natural.

Por ahora, ninguno de los dos esquemas es útil en la práctica: el preprocesamiento actualmente ayuda en los extremos, cuando el tamaño de la base de datos se dispara hacia el infinito. Pero implementarlo significa que esos ahorros no pueden materializarse y el proceso consumiría demasiado tiempo y espacio de almacenamiento.

Afortunadamente, dijo Vaikuntanathan, los criptógrafos tienen una larga historia de optimización de resultados que inicialmente no eran prácticos. Si el trabajo futuro puede simplificar el enfoque, cree que las búsquedas privadas en bases de datos gigantes pueden estar al alcance de la mano. "Todos pensábamos que estábamos atrapados allí", dijo. “Lo que da el resultado de Daniel es esperanza”.

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta a lectores de informática y entrarás para ganar gratis ¿Cuánto mercancía.