\n<\/p>\n
la versi\u00f3n original<\/span> de<\/em> esta historia<\/em> apareci\u00f3 en<\/em> Revista Quanta.<\/em><\/p>\n Todos sabemos<\/span> Hay que tener cuidado con los detalles que compartimos online, pero la informaci\u00f3n que buscamos tambi\u00e9n puede ser reveladora. Busque indicaciones para llegar en autom\u00f3vil y nuestra ubicaci\u00f3n ser\u00e1 mucho m\u00e1s f\u00e1cil de adivinar. Busque una contrase\u00f1a entre un tesoro de datos comprometidos y corremos el riesgo de filtrarla nosotros mismos.<\/p>\n Estas situaciones alimentan una pregunta clave en criptograf\u00eda: \u00bfC\u00f3mo se puede extraer informaci\u00f3n de una base de datos p\u00fablica sin revelar nada sobre a qu\u00e9 se ha accedido? Es el equivalente a sacar un libro de la biblioteca sin que el bibliotecario sepa cu\u00e1l.<\/p>\n Elaborar una estrategia que resuelva este problema (conocida como recuperaci\u00f3n de informaci\u00f3n privada) es \u00abun componente muy \u00fatil en una serie de aplicaciones que preservan la privacidad\u00bb, afirm\u00f3 David Wu, cript\u00f3grafo de la Universidad de Texas en Austin. Desde la d\u00e9cada de 1990, los investigadores han ido socavando la cuesti\u00f3n, mejorando las estrategias para acceder de forma privada a las bases de datos. Un objetivo importante, a\u00fan imposible con bases de datos grandes, es el equivalente a una b\u00fasqueda privada en Google, donde se puede examinar un mont\u00f3n de datos de forma an\u00f3nima sin realizar ning\u00fan trabajo computacional pesado.<\/p>\n Ahora, tres investigadores han elaborado una versi\u00f3n largamente buscada de recuperaci\u00f3n de informaci\u00f3n privada y la han ampliado para crear una estrategia de privacidad m\u00e1s general. El trabajo, que recibi\u00f3 el premio al Mejor Trabajo en junio de 2023 en el Simposio anual sobre Teor\u00eda de la Computaci\u00f3n, derriba una importante barrera te\u00f3rica en el camino hacia una b\u00fasqueda verdaderamente privada.<\/p>\n \u201c[This is] algo en criptograf\u00eda que supongo que todos quer\u00edamos pero que no cre\u00edamos que existiera\u201d, dijo Vinod Vaikuntanathan, cript\u00f3grafo del Instituto Tecnol\u00f3gico de Massachusetts que no particip\u00f3 en el art\u00edculo. \u00abEs un resultado hist\u00f3rico\u00bb.<\/p>\n El problema del acceso a bases de datos privadas tom\u00f3 forma en la d\u00e9cada de 1990. Al principio, los investigadores asumieron que la \u00fanica soluci\u00f3n era escanear toda la base de datos durante cada b\u00fasqueda, lo que ser\u00eda como hacer que un bibliotecario revise cada estante antes de regresar con su libro. Despu\u00e9s de todo, si la b\u00fasqueda omiti\u00f3 alguna secci\u00f3n, el bibliotecario sabr\u00eda que su libro no se encuentra en esa parte de la biblioteca.<\/p>\n Ese enfoque funciona bastante bien a escalas m\u00e1s peque\u00f1as, 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\u00e1s grandes (e Internet es bastante grande), el proceso se vuelve prohibitivamente ineficiente.<\/p>\n A principios de la d\u00e9cada de 2000, los investigadores comenzaron a sospechar que podr\u00edan sortear la barrera del escaneo completo \u201cpreprocesando\u201d la base de datos. En t\u00e9rminos generales, esto significar\u00eda codificar toda la base de datos como una estructura especial, de modo que el servidor pueda responder una consulta leyendo solo una peque\u00f1a parte de esa estructura. Un preprocesamiento lo suficientemente cuidadoso podr\u00eda, en teor\u00eda, significar que un \u00fanico servidor que aloja informaci\u00f3n solo realiza el proceso una vez, por s\u00ed solo, permitiendo a todos los usuarios futuros obtener informaci\u00f3n de forma privada sin ning\u00fan esfuerzo adicional.<\/p>\n Para Daniel Wichs, cript\u00f3grafo de la Universidad Northeastern y coautor del nuevo art\u00edculo, eso parec\u00eda demasiado bueno para ser verdad. Alrededor de 2011, empez\u00f3 a intentar demostrar que este tipo de plan era imposible. \u00abEstaba convencido de que no hab\u00eda manera de que esto se pudiera hacer\u00bb, dijo.<\/p>\n<\/div>\n