la versión original de esta historia apareció en Revista Quanta.
Todos sabemos Hay que tener cuidado con los detalles que compartimos online, 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», afirmó David Wu, criptógrafo de la Universidad de Texas en 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 han ampliado para crear una estrategia de privacidad más general. El trabajo, que recibió el premio al Mejor Trabajo en junio de 2023 en el Simposio anual sobre Teoría de la Computación, derriba una importante barrera teórica en el camino hacia una búsqueda verdaderamente privada.
“[This is] algo en criptografía que supongo que todos queríamos pero que no creíamos que existiera”, dijo Vinod Vaikuntanathan, criptógrafo del Instituto Tecnológico 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 usuarios futuros obtener información de forma privada sin ningún esfuerzo adicional.
Para 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.