Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
The Ring Learning with Errors (RLWE) problem has become one of the most widely used cryptographic assumptions for the construction of modern cryptographic primitives. Most of these solutions make use of power-of-two cyclotomic rings mainly due to its simplicity and efficiency. This work explores the possibility of substituting them for multiquadratic rings and shows that the latter can bring about important efficiency improvements in reducing the cost of the underlying polynomial operations. We introduce a generalized version of the fast Walsh-Hadamard Transform which enables faster degree-n polynomial multiplications by reducing the required elemental products by a factor of O(log n). Finally, we showcase how these rings find immediate application in the implementation of OLE (Oblivious Linear Function Evaluation) primitives, which are one of the main building blocks used inside Secure Multiparty Computation (MPC) protocols.