Rizomas e as raízes da eficiência — Melhorando Prio

Resumo

Prio, personalizado sob princípios de privacidade por design, é um protocolo para agregar medições fornecidas pelo cliente entre entidades que não colaboram. A validade das medições é determinada usando uma prova totalmente linear e probabilisticamente verificável (FLPCP). O Prover distribui ações secretas da medição e da prova para vários Verificadores. Esses Verificadores só podem usar consultas lineares na declaração de entrada para validação sem acessar a medição real. A eficiência é fundamental para a aplicação prática de Prio. A FLPCP opera com polinômios representados na base de Lagrange usando raízes da unidade como os nós. No entanto, observamos oportunidades para melhorar seu desempenho abraçando a base de Lagrange de forma mais extensiva. Por exemplo, mostramos um algoritmo de complexidade de tempo O(n) sem inversão para avaliação de polinômios na base de Lagrange (uma alternativa à fórmula clássica de barycentric racional). Ao aplicar nossos métodos à libprio-rs, uma implementação de ponta em Rust, a fase de Sharding (geração de prova) executa 36% mais rápido e a fase Prep-Init (verificação de prova) é duas vezes mais rápida, mostrando uma aceleração substancial das fases mais demoradas de Prio.