Con un avance que un experto en criptografía llamó una "obra maestra", los científicos informáticos de la Universidad de Texas en Austin han desarrollado un nuevo método para producir números verdaderamente aleatorios, un avance que podría usarse para cifrar datos, hacer que la votación electrónica sea más segura, conducirencuestas estadísticamente significativas y simulan con mayor precisión sistemas complejos como el clima de la Tierra.
El nuevo método crea números verdaderamente aleatorios con menos esfuerzo computacional que otros métodos, lo que podría facilitar niveles significativamente más altos de seguridad para todo, desde transacciones de tarjetas de crédito de consumidores hasta comunicaciones militares.
El profesor de informática David Zuckerman y el estudiante graduado Eshan Chattopadhyay presentarán una investigación sobre su método en junio en el Simposio anual sobre Teoría de la Computación STOC, la principal conferencia teórica de informática de la Asociación de Maquinaria de Computación. Una invitación para presentar en la conferenciase basa en un riguroso proceso de revisión por pares para evaluar la corrección y la importancia del trabajo. Su trabajo será uno de los tres que recibirán el Premio al Mejor Papel STOC.
"Este es un problema al que he vuelto una y otra vez durante más de 20 años", dice Zuckerman. "Estoy encantado de haberlo resuelto".
Chattopadhyay y Zuckerman publicaron un borrador del documento que describe su método para hacer números aleatorios en un foro en línea el año pasado http://eccc.hpi-web.de/report/2015/119/ .En un campo más acostumbrado a las pequeñas mejoras incrementales, la comunidad de ciencias de la computación elogió el método y sugirió que, en comparación con los métodos anteriores, este está a años luz de distancia.Oded Goldreich, profesor de ciencias de la computación en el Instituto de Ciencia Weizmann en Israel, comentó que incluso si hubiera sido una mejora moderada sobre los métodos existentes, habría justificado una "fiesta de una noche".
"Cuando me enteré, no pude dormir", dice Yael Kalai, investigador principal que trabaja en criptografía en Microsoft Research New England y que también trabajó en la extracción aleatoria. "Estaba tan emocionado. No podía creerlo.. Corrí al archivo en línea para mirar el periódico. Es realmente una obra maestra ".
El nuevo método toma dos secuencias de números débilmente aleatorias y las convierte en una secuencia de números verdaderamente aleatorios. Las secuencias débilmente aleatorias, como la temperatura del aire y los precios del mercado de valores muestreados a lo largo del tiempo, albergan patrones predecibles. Las secuencias verdaderamente aleatorias no tienen nada predecibleellos, como un lanzamiento de moneda.
La nueva investigación parece desafiar ese viejo adagio en la programación de computadoras, "Basura adentro, basura afuera". De hecho, es la última y más poderosa adición a una clase de métodos que Zuckerman fue pionero en la década de 1990 llamados extractores de aleatoriedad.
Las versiones anteriores de los extractores de aleatoriedad eran menos prácticas porque requerían que una de las dos secuencias de origen fuera verdaderamente aleatoria lo que presenta un problema de gallina o huevo o que ambas secuencias de origen estuvieran cerca de ser realmente aleatorias.de esas restricciones y permite el uso de dos secuencias que son débilmente aleatorias.
Una aplicación importante para números aleatorios es generar claves para el cifrado de datos que son difíciles de descifrar para los piratas informáticos. El cifrado de datos es fundamental para realizar compras seguras con tarjeta de crédito y transacciones bancarias, mantener la privacidad de los datos médicos personales y proteger las comunicaciones militares de los enemigos, entre otros.muchas aplicaciones prácticas.
Zuckerman dice que aunque ya existen métodos para producir números aleatorios de alta calidad, son muy exigentes computacionalmente. Su método produce aleatoriedad de mayor calidad con menos esfuerzo.
"Una forma común de mal uso del cifrado es no usar aleatoriedad de alta calidad", dice Zuckerman. "Entonces, en ese sentido, al facilitar la obtención de aleatoriedad de alta calidad, nuestros métodos podrían mejorar la seguridad".
Su trabajo muestra cómo generar solo un número verdaderamente aleatorio, similar a un lanzamiento de moneda, pero el ex alumno de Zuckerman, Xin Li, ya ha demostrado cómo expandirlo para crear secuencias de muchos más números aleatorios.
El sitio web donde Zuckerman y Chattopadhyay publicaron su borrador el verano pasado, llamado Coloquio electrónico sobre la complejidad computacional, permite a los investigadores compartir su trabajo y recibir comentarios antes de publicar versiones finales en revistas o conferencias. Los informáticos y matemáticos han estado revisando cuidadosamente elartículo, proporcionando sugerencias e incluso extendiendo el método para hacerlo más poderoso.
Fuente de la historia :
Materiales proporcionado por Universidad de Texas en Austin . Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :