Compartición de Secretos con Verificación Pública

Abstract

Publicly Verifiable Secret Sharing (PVSS) is the base of many decentralised systems: it neutralises the threats of a cheating dealer distributing malformed shares and a dishonest subset of participants submitting inconsistent or no shares at all, by attaching a public proof of correctness to every share. Existing PVSS constructions need linear work for sharing verification. Recent advances such as folding low-degree tests to collapse a length-n polynomial proof into O(log2 2 n) cost and succinct vector commitments with constant size proofs, offer paths for improvement. The main goal of this thesis is to integrate these techniques into the PVSS layer of ALBATROSS, a state-of-the-art randomness beacon. The resulting construction maintains the worst-case O(n) exponentiations for the verifier of the original protocol but reduces their work to logarithmic operations whenever no complaints are raised, plus a linear or quadratic factor which can be amortised whenever the protocol is executed multiple times.

La compartición de secretos verificable p ́públicamente es la base de muchos sistemas descentralizados: neutraliza las amenazas de un distribuidor tramposo que entrega fragmentos (shares) malformados y de un subconjunto deshonesto de participantes que envían fragmentos inconsistentes o no envían ninguna, al adjuntar una prueba pública de validez. Las construcciones existentes requieren un trabajo lineal en la verificación de los fragmentos. Avances recientes, como los tests basados en plegado de polinomios (folding) para demostrar que un polinomio tiene grado pequeño para colapsar una prueba polinómica de longitud n en un coste de O(log2 2 n) y los compromisos vectoriales (vector commitments) con pruebas constantes, ofrecen v ́ıas de mejora. El objetivo principal de esta tesis es integrar estas técnicas en la capa de compartición de secretos del protocolo ALBATROSS. La construcción resultante mantiene las O(n) exponenciaciones en el peor caso para el verificador del protocolo original, pero reduce su trabajo a operaciones logarítmicas siempre que no se planteen quejas, además de un factor lineal o cuadrático que puede amortizarse al ejecutarlo múltiples veces.