Rizomas y las raíces de la eficiencia — Mejorando Prio

Resumen

Prio, diseñado bajo principios de privacidad desde el diseño, es un protocolo para agregar medidas proporcionadas por el cliente entre entidades que no colluden. La validez de las medidas se determina utilizando una prueba completamente lineal y probabilísticamente verificable (FLPCP). El que prueba distribuye partes secretas de la medida y la prueba a varios verificadores. Estos verificadores solo pueden utilizar consultas lineales en la declaración de entrada para la validación sin acceder a la medida real. La eficiencia es clave para la aplicación práctica de Prio. El FLPCP opera con polinomios representados en la base de Lagrange utilizando raíces de la unidad como nodos. Sin embargo, se observan oportunidades para mejorar su rendimiento abrazando la base de Lagrange de manera más extensa. Por ejemplo, mostramos un algoritmo de complejidad temporal O(n) sin inversión para la evaluación de polinomios en la base de Lagrange (una alternativa a la fórmula clásica de barycentric racional). Al aplicar nuestros métodos a libprio-rs, una implementación de vanguardia en Rust, la fase de fragmentación (generación de pruebas) se ejecuta un 36 % más rápido y la fase de preparación-inicial (verificación de pruebas) es dos veces más rápida, lo que muestra una aceleración sustancial de las fases más consumidoras de tiempo de Prio.