Welcome to the resource topic for 2022/879
Title:
Modular Polynomial Multiplication Using RSA/ECC coprocessor
Authors: Aurélien Greuet, Simon Montoya, and Clémence Vermeersch
Abstract:Modular polynomial multiplication is a core and costly operation of ideal lattice-based schemes. In the context of embedded devices, previous works transform the polynomial multiplication to an integer one using Kronecker substitution. Then thanks to this transformation, existing coprocessors which handle large-integer operations can be re-purposed to speed-up lattice-based cryptography. In a nutshell, the Kronecker substitution transforms by evaluation the polynomials to integers, multiplies it with an integer multiplication and gets back to a polynomial result using a radix conversion. The previous work focused on optimization of the integer multiplication using coprocessor instructions. In this work, we pursue the seminal research by optimizing the evaluation, radix conversion and the modular reductions modulo q with today’s RSA/ECC coprocessor. In particular we show that with a RSA/ECC coprocessor that can compute addition/subtraction, (modular) multiplication, shift and logical AND on integers, we can compute the whole modular polynomial multiplication using coprocessor instructions. The efficiency of our modular polynomial multiplication depends on the component specification and on the cryptosystem parameters set. Hence, we assess our algorithm on a chip for several lattice-based schemes, which are finalists of the NIST standardization. Moreover, we compare our modular polynomial multiplication with other polynomial multiplication techniques.
ePrint: https://eprint.iacr.org/2022/879
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .