Abstract

When a quantum computer is put into practical use, it is expected that currently used RSA cryptography and elliptic curve cryptography can be deciphered in polynomial time. For this reason, many studies have been conducted to construct ciphers that are unbreakable in polynomial time even with a quantum computer, and one such study is the Ring-LWE problem. Since the Ring-LWE problem involves a large number of multiplications, one of the research goals is to speed up the computation of the multiplications. Arita et al. proposed a method for fast multiplication of the decomposition of a circle for a prime number m. However, this method is limited in the number of circular decompositions that can be used. In this study, we propose a method for fast multiplication of decompositions of circular objects to powers of primes, based on the method by Arita et al. This method is expected to increase the number of circular decompositions that can be used in Ring-LWE and to expand the choice of parameters.

Top