TECHNICAL FIELD

Various exemplary embodiments disclosed herein relate generally to method for multiplying polynomials for a cryptographic operation.

BACKGROUND

The development of quantum computers threatens the security of certain currently widely used public key cryptography algorithms such as the RSA (Rivest-Shamir-Adleman) algorithm. Most recently, advances in quantum computing have accelerated the research into “post-quantum cryptography” schemes, that is, new cryptography schemes that are believed to be secure even when faced with an attacker using a quantum computer. There are various families of problems that are being considered to instantiate these post-quantum cryptographic approaches. One approach is based on the hardness of certain lattice problems. That is, solving these difficult lattice problems compromises the cryptography. When implemented, computationally expensive operations of some proposed lattice-based post-quantum cryptography schemes include arithmetic with polynomials with integer coefficients. Some currently used public-key cryptography algorithms require arithmetic of large integers, where the integers may include hundreds or thousands of bits. In contrast, the coefficients used for polynomial multiplication for lattice-based algorithms may be much smaller, e.g., 32 bits or less. Typically, special purpose processors are implemented in a data processing system to offload the computationally difficult problems from the main processor of the system. However, the special purpose co-processors currently used to implement existing RSA or Elliptic-curve cryptography (ECC) algorithms cannot efficiently and quickly perform the polynomial multiplications required for lattice-based cryptography. Developing new special-purpose co-processors to perform the computations needed by lattice-based post-quantum cryptography efficiently and quickly is expensive and time consuming.

SUMMARY

A summary of various exemplary embodiments is presented below. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the various exemplary embodiments, but not to limit the scope of the invention. Detailed descriptions of an exemplary embodiment adequate to allow those of ordinary skill in the art to make and use the inventive concepts will follow in later sections.

Various embodiments relate to a method for multiplying a first and a second polynomial in the ring[X]/(XN−1) to perform a cryptographic operation in a data processing system, the method for use in a processor of the data processing system, including: receiving the first polynomial and the second polynomial by the processor; mapping the first polynomial into a third polynomial in a first ring and a fourth polynomial in a second ring using a map; mapping the second polynomial into a fifth polynomial in the first ring and a sixth polynomial in the second ring using the map; multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result; multiplying the fourth polynomial in the second ring with the sixth polynomial in the second ring to produce a second multiplication result using Renes multiplication; and combining the first multiplication result and the second multiplication result using the map.

Various embodiments are described, wherein the first ring is[X]/(XN/2−1), and the second ring is[X]/(XN/2+1).

Various embodiments are described, wherein the first polynomial f is f=f0+XN/2f1in the ring[X]/(XN−1), wherein f0is a lower portion of the first polynomial and f1is an upper portion of the first polynomial, the third polynomial is f0+f1in the first ring, and fourth polynomial is f0−f1in the second ring.

Various embodiments are described, wherein the first polynomial and the second polynomial are of order N and the third polynomial, fourth polynomial, fifth polynomial, and sixth polynomial are of order N/2.

Various embodiments are described, wherein multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result further includes: mapping the third polynomial into seventh polynomial in a third ring and an eighth polynomial in a forth ring using the map; mapping the fifth polynomial into a ninth polynomial in the third ring and a tenth polynomial in the fourth ring using the map; multiplying the seventh polynomial in the third ring with the ninth polynomial in the third ring to produce a third multiplication result; multiplying the eighth polynomial in the fourth ring with the tenth polynomial in the fourth ring to produce a fourth multiplication result using Renes multiplication; and combining the second multiplication result and the fourth multiplication result using the map to produce the first multiplication result.

Various embodiments are described, wherein the first ring is[X]/(XN/2−1), the second ring is[X]/(XN/2+1), the third first ring is[X]/(XN/4−1), and the fourth ring is[X]/(XN/4+1).

Various embodiments are described, wherein the first polynomial and the second polynomial are of order N, the third polynomial, fourth polynomial, fifth polynomial, and sixth polynomial are of order N/2, and the seventh polynomial, eighth polynomial, ninth polynomial, and tenth polynomial are of order N/4.

Various embodiments are described, wherein the cryptographic operation is a lattice-based cryptographic operation.

Further various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for multiplying a first and a second polynomial in the ring[X]/(XN−1) to perform a cryptographic operation in a processor, the instructions, including: instructions for receiving the first polynomial and the second polynomial by the processor; instructions for mapping the first polynomial into a third polynomial in a first ring and a fourth polynomial in a second ring using a map; instructions for mapping the second polynomial into a fifth polynomial in the first ring and a sixth polynomial in the second ring using the map; instructions for multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result; instructions for multiplying the fourth polynomial in the second ring with the sixth polynomial in the second ring to produce a second multiplication result using Renes multiplication; and instructions for combining the first multiplication result and the second multiplication result using the map.

Various embodiments are described, wherein the first ring is[X]/(XN/2−1), and the second ring is[X]/(XN/2+1).

Various embodiments are described, wherein the first polynomial f is f=f0+XN/2f1in the ring[X]/(XN−1), wherein f0is a lower portion of the first polynomial and f1is an upper portion of the first polynomial, the third polynomial is f0+f1in the first ring, and fourth polynomial is f0−f1in the second ring.

Various embodiments are described, wherein the first polynomial and the second polynomial are of order N and the third polynomial, fourth polynomial, fifth polynomial, and sixth polynomial are of order N/2.

Various embodiments are described, wherein the instructions for multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result further includes: instructions for mapping the third polynomial into seventh polynomial in a third ring and an eighth polynomial in a forth ring using the map; instructions for mapping the fifth polynomial into a ninth polynomial in the third ring and a tenth polynomial in the fourth ring using the map; instructions for multiplying the seventh polynomial in the third ring with the ninth polynomial in the third ring to produce a third multiplication result; instructions for multiplying the eighth polynomial in the fourth ring with the tenth polynomial in the fourth ring to produce a fourth multiplication result using Renes multiplication; and instructions for combining the second multiplication result and the fourth multiplication result using the map to produce the first multiplication result.

Various embodiments are described, wherein the first ring is[X]/(XN/2−1), the second ring is[X]/(XN/2+1), the third first ring is[X]/(XN/4−1), and the fourth ring is[X]/(XN/4+1).

Various embodiments are described, wherein the first polynomial and the second polynomial are of order N, the third polynomial, fourth polynomial, fifth polynomial, and sixth polynomial are of order N/2, and the seventh polynomial, eighth polynomial, ninth polynomial, and tenth polynomial are of order N/4.

Various embodiments are described, wherein the cryptographic operation is a lattice-based cryptographic operation.

