Shorter Lattice-based Zero-Knowledge Proofs for the Correctness of a Shuffle
Publicado en Financial Cryptography and Data Security Workshop VOTING’21, 2021
Cita recomendada: Herranz J., Martínez R., Sánchez M. (2021) Shorter Lattice-Based Zero-Knowledge Proofs for the Correctness of a Shuffle. In: Bernhard M. et al. (eds) Financial Cryptography and Data Security. FC 2021 International Workshops. FC 2021. Lecture Notes in Computer Science, vol 12676. Springer, Berlin, Heidelberg https://doi.org/10.1007/978-3-662-63958-0_27
En una votación electrónica se usan redes de mezcla para garantizar el anonimato de los votos emitidos. Cada nodo de la red recifra y permuta aleatoriamente la lista de cifrados que recibe como entrada en un proceso conocido como mezcla, y debe probar (con conocimiento nulo) que el proceso se ha realizado honestamente. Para mantener la seguridad de un proceso como este en un escenario poscuántico se usan nuevas pruebas basadas en diferentes conjeturas matemáticas, como los problemas de retículos. Sin embargo, los mejores protocolos basados en retículos para garantizar mezclas verificables tienen una complejidad computacional lineal en \(N\), el número de cifrados a mezclar.
En este artículo proponemos el primer argumento de conocimiento nulo poscuántico sublineal (en \(N\)) para demostrar la corrección de una mezcla, para el cual principalmente hemos utilizado dos ideas: los resultados sobre satisfactibilidad de circuitos aritméticos de Baum et al. (CRYPTO’2018) y redes de Beneš para representar una permutación de \(N\) elementos. Alcanzamos una complejidad computacional de \(\mathcal{O}(\sqrt{N}\log^{2}(N))\) respecto a \(N\), aunque también resaltamos la dependencia respecto a otros parámetros importantes de los retículos subyacentes.