Vol. 2 (2021): Proceedings of the 3rd BYMAT Conference
Artículos

Multiquadratic rings and oblivious linear function evaluation

Alberto Pedrouzo-Ulloa
atlanTTic Research Center and Universidade de Vigo
Cover for TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMat Conference

Publicado 28/08/2021

Palabras clave

  • ring learning with errors,
  • multiquadratic rings,
  • Walsh-Hadamard transform,
  • oblivious linear function evaluation

Cómo citar

Pedrouzo-Ulloa, Alberto. «Multiquadratic rings and oblivious linear function evaluation». En: TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMAT Conference, págs. 83-86. ISSN: 2660-6003. URL: https://temat.es/monograficos/article/view/vol2-p83.

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).