Publicado 28/08/2021
Palabras clave
- ring learning with errors,
- multiquadratic rings,
- Walsh-Hadamard transform,
- oblivious linear function evaluation
Cómo citar
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Resumen
El problema Ring Learning with Errors (RLWE) ha sido utilizado ampliamente para la construcción de nuevas primitivas criptográficas resistentes a ataques por parte de un ordenador cuántico. La mayoría de los esquemas existentes basados en RLWE hacen uso de anillos ciclotómicos de orden potencia de dos, debido a su buen comportamiento y sencillez. Esta charla explora el reemplazo de los anillos ciclotómicos potencia de dos por anillos multicuadráticos. Se muestra que, para polinomios con $n$ coeficientes, el coste de las operaciones polinomiales puede ser reducido de $\mathcal{O}(n \log{n})$ multiplicaciones a $\mathcal{O}(n)$ multiplicaciones y $\mathcal{O}(n \log{n})$ sumas. Finalmente, se discuten los beneficios que estos anillos introducen al implementar la primitiva OLE (Oblivious Linear Function Evaluation), que es un bloque básico utilizado en muchos protocolos de Secure Multiparty Computation (MPC).