Los investigadores Ignacio Cascudo (Instituto IMDEA Software) y Bernardo David (IT University of Copenhagen) han publicado recientemente “ALBATROSS: publicly AttestabLe BATched Randomness based On Secret Sharing”.
ALBATROSS es una familia de protocolos con el que un conjunto de usuarios puede generar conjuntamente números aleatorios; estos protocolos finalizan correctamente de forma garantizada si una mayoría de los participantes es honesta y además su corrección se puede verificar de forma pública. ALBATROSS permite encontrar diversos compromisos entre la cantidad de participantes maliciosos que se toleran y su complejidad computacional, que en cualquier caso mejora mucho con respecto a propuestas anteriores.
El protocolo más básico (con seguridad local o “stand-alone”) se basa en un esquema de compartición de secretos públicamente verificable (PVSS) y es seguro en el ampliamente aceptado “modelo de oráculo aleatorio” (random oracle model) si asumimos la dificultad del problema de Diffie-Hellman decisional (DDH). También se aborda la cuestión de como dotar a este tipo de protocolos de seguridad integrable universal (“universally composable security” o UC), que hace que se pueda integrar de forma segura en entornos más complejos, mostrando dos versiones UC de Albatross: una basada en pruebas de conocimiento zero no interactivas (UC-NIZK) y otra basada en novedosos “esquemas de compromiso homomórficos eficientes con verificador designado” (“designated verifier homomorphic commitments”). Curiosamente esta última versión puede implementarse usando un oráculo aleatorio global y el supuesto más débil de que el problema computacional de Diffie-Hellman (CDH) es difícil.
Una ejecución de ALBATROSS con n participantes, de las cuales hasta t = (1/2 - ε) · n pueden ser maliciosos, para una constante ε > 0, genera Θ(n^2) valores uniformemente aleatorios, requiriendo en el peor de los casos un cálculo amortizado de Θ(log n) operaciones de exponenciación por participante y valor aleatorio producido. En el artículo de Cascudo y David se mejora significativamente su anterior protocolo SCRAPE, que requería Θ(n^2) de estas operaciones por participante para generar un sólo valor aleatorio uniforme. Esto se logra principalmente mediante el uso de dos técnicas: en primer lugar, el uso de un esquema de compartición de secretos “empaquetado” de Shamir (packed Shamir secret sharing) como base para el PVSS; en segundo lugar, el uso de las llamadas “linear resilient functions” o funciones lineales resilientes (calculadas de forma eficiente mediante un algoritmo basado en la Transformada rápida de Fourier) para mejorar la extracción de aleatoriedad.
La aplicación principal de estos resultados está en las llamadas Proof of Stake Blockchains, cuyo funcionamiento hace necesaria elegir cada cierto periodo de tiempo un líder de forma aleatoria y sin posibilidad de manipulación o sesgo, y donde la corrección de este proceso se debe poder verificar de forma pública.
