Advertencia: este algoritmo se autodestruirá después de su uso

Imagine dos millonarios, Alice y Bob, que quieren decidir quién es más rico pero sin revelar su riqueza. ¿Cómo hacen para resolver su enigma? Se trata del Problema del Millonario de Yao, ideado por el informático Andrew Yao en 1982.

Una solución potencial es un programa de computadora de una sola vez. Este programa permite que Alice y Bob ingresen sus datos de forma privada, realiza el cálculo una vez, da la respuesta y luego se destruye. Esto asegura que nadie pueda acceder a los datos originales o la forma en que se procesaron. Y le da a Alice y Bob su respuesta sin comprometer sus detalles financieros.

Los expertos en seguridad informática dicen que los programas únicos son una herramienta muy importante en la ciberseguridad. O lo serían, si alguien pudiera construirlos.

Resulta que es imposible construir un programa único ideal que se ejecute una vez y luego se destruya a sí mismo. Una computadora clásica de este tipo tendría que destruirse físicamente para garantizar que no se pueda volver a utilizar, y no se conoce ninguna forma de garantizarlo.

Una computadora cuántica podría parecer que ofrece más potencial, ya que la información cuántica se destruye fácilmente y es imposible de copiar. Pero resulta que una computadora cuántica no puede dar una respuesta determinista a un cálculo único.

Así que el sueño de un programa de una sola vez que se destruye a sí mismo después de un solo cálculo parece condenado al fracaso.

Entran Marie-Christine Roehsner en la Universidad de Viena y Joshua Kettlewell en la Universidad Nacional de Singapur y algunos amigos. Hoy, dicen que han encontrado una manera de construir un programa de una sola vez y han construido y demostrado un dispositivo de prueba de principio por primera vez.

El nuevo método se basa en una forma diferente de pensar sobre los programas únicos realizados por computadoras cuánticas. Hasta ahora, los expertos en seguridad siempre han esperado una solución definitiva: el valor de Bob es mayor o menor que el de Alice.

Pero la mecánica cuántica es un proceso inherentemente probabilístico, y eso significa que solo puede dar la respuesta correcta dentro de ciertos límites de probabilidad, digamos el 75 por ciento del tiempo. Siempre que Alice y Bob estén dispuestos a aceptar la posibilidad de un error en el cálculo, es posible garantizar que su información permanecerá segura, que el programa se ejecutará una sola vez y luego se destruirá a sí mismo.

Relajamos la definición de programas de una sola vez para permitir cierta probabilidad de error en la salida y mostramos que la mecánica cuántica ofrece ventajas de seguridad sobre los recursos puramente clásicos, dicen los investigadores.

El enfoque es sencillo. Alice codifica en secreto su riqueza en los estados de un conjunto de qubits almacenados en una computadora cuántica. Esta computadora está programada para comparar este número con uno ingresado por Bob y decirle si su riqueza es mayor o menor que la de Alice.

Este procesamiento cuántico es en sí mismo un proceso irreversible y esto evita que Bob ingrese otros números para determinar la riqueza de Alice.

Pero el hardware es fijo y una debilidad potencial de este enfoque es que Bob puede aplicar ingeniería inversa al programa averiguando cómo están conectadas las puertas lógicas.

Sin embargo, Roehsner y compañía tienen un truco para evitar esto. Aunque no pueden ocultar el cableado físico, pueden ocultar las tablas de verdad que rigen el comportamiento de cada puerta lógica. Esto se debe a que nuestro enfoque es codificar la tabla de verdad para las puertas individuales como un programa de una sola vez por derecho propio, dicen.

Esto permite que la información de Alice se codifique en la elección precisa de las puertas lógicas y no en las conexiones entre ellas. De esta forma permanece oculto para Bob.

Roehsner y compañía han probado esta idea en un experimento de prueba de principio. Este codifica información en la polarización de fotones y la procesa usando varios tipos de puertas lógicas ópticas. La probabilidad promedio de éxito para cada una de las puertas es del 75 por ciento, lo que, según el equipo, está en buena concordancia con el valor esperado.

Luego, el equipo usó esta configuración para resolver el problema del millonario de Yao para números que consisten en cuatro bits que difieren en un solo bit. El programa funciona comparando cada bit para decidir cuál es más grande.

Los resultados hacen una lectura interesante. El equipo dice que la probabilidad de éxito aumenta con la cantidad de bits utilizados para la corrección de errores, pero esto también reduce la seguridad del sistema. Por lo tanto, existe una clara compensación entre precisión y seguridad. Sin embargo, el equipo dice que la seguridad es mejor que la que se puede lograr solo con la computación clásica.

Nuestros resultados demuestran que la física cuántica permite mejores compensaciones de seguridad para ciertas tareas informáticas seguras que las que son posibles en el mundo clásico, incluso cuando no se puede lograr la seguridad perfecta, dicen.

Además, el método funciona con la tecnología actual y los avances relativamente modestos deberían aumentar aún más la seguridad.

Ese es un trabajo interesante que muestra el potencial de las tecnologías cuánticas para aumentar drásticamente la seguridad utilizando la tecnología que está disponible en la actualidad. Creemos que el trabajo presentado apunta fuertemente a un área rica de protocolos cuánticos para mejorar la seguridad de la computación clásica, incluso antes de que se puedan realizar computadoras cuánticas a gran escala, dicen Roehsner y compañía.

Será interesante ver cómo se recibe el trabajo.

Ref: arxiv.org/abs/1709.09724 : Quantum Advantage para programas probabilísticos únicos

esconder