RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations
Publicado en 17th IMA International Conference on Cryptography and Coding, 2019
Cita recomendada: Martínez R., Morillo P. (2019) RLWE-Based Zero-Knowledge Proofs for Linear and Multiplicative Relations. In: Albrecht M. (eds) Cryptography and Coding. IMACC 2019. Lecture Notes in Computer Science, vol 11929. Springer, Cham https://doi.org/10.1007/978-3-030-35199-1_13
Presentamos pruebas de conocimiento nulo (ZKPoK) eficientes para relaciones lineales y multiplicativas entre mensajes secretos ocultos como muestras Ring Learning With Errors (RLWE). Los mensajes son polinomios en \(\mathbb{Z}_q[x]/\left<x^{n}+1\right>\) y los protocolos que proponemos par ZKPoK están basados en el aclamado artículo de Stern sobre esquemas de identificación usando problemas de códigos (Crypto’93). Nuestro protocolo de 5 movimientos tiene un error de consistencia ligeramente superior a 1/2 y conocimiento nulo perfecto.
Como aplicación presentamos pruebas de conocimiento nulo de relaciones entre mensajes comprometidos. El esquema de compromiso resultante es perfectamente vinculante salvo con una probabilidad despreciable sobre la elección de la clave pública, y computacionalmente vinculante bajo la hipótesis RLWE. Comparado con los anteriores esquemas de compromiso basados en Stern reducimos la complejidad computacional, mejoramos el tamaño de los parámetros y reducimos el error de consistencia de cada ronda.