Method for multiplying polynomials for a cryptographic operation
Various embodiments relate to a method for multiplying a first and a second polynomial in the ring [X]/(X N −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.
1. A computer implemented method for multiplying a First and a second polynomial in the ring [X]/(X N −1) and performing a cryptographic operation in a data processing system, the method executed using a hardware processor of the data processing system, comprising:
receiving the first polynomial and the second polynomial by the hardware 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;
combining the first multiplication result and the second multiplication result using the map,
wherein the first ring is [X]/(X N/2 +1),
wherein the second ring is [X]/(X N/2 +1), and
performing a post-quantum cryptography operation using the hardware processor including executing a verification, encryption, or decryption operation using the multiplication of the first polynomial and the second polynomial with integer coefficients.
2. The method of claim 1 , wherein
the first polynomial f is f=f 0 +X N/2 f 1 in the ring [X]/(X N −1), wherein f 0 is a lower portion of the first polynomial and f 1 is an upper portion of the first polynomial,
the third polynomial is f 0 +f 1 in the first ring, and
fourth polynomial is f 0 −f 1 in the second ring.
3. The method of claim 1 , 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.
4. The method of claim 1 , wherein multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result further comprises:
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.
5. The method of claim 4 , wherein
the third first ring is [X]/(X N/4 −1), and
the fourth ring is [X]/(X N/4 +1).
6. The method of claim 4 , 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.
7. The method of claim 1 , wherein the cryptographic operation is a lattice-based cryptographic operation.
8. 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]/(X N −1) and performing a cryptographic operation using a hardware processor, the instructions executed by the hardware processor, comprising:
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;
instructions for combining the first multiplication result and the second multiplication result using the map,
wherein the first ring is [X]/(X N/2 −1), and
wherein the second ring is [X]/(X N/2 +1),
instructions for performing a post-quantum cryptography operation using the hardware processor including executing a verification, encryption, or decryption operation using the multiplication of the first polynomial and the second polynomial with integer coefficients.
9. The data processing system of claim 8 , wherein
the first polynomial f is f=f 0 +X N/2 f 1 in the ring [X]/(X N −1), wherein f 0 is a lower portion of the first polynomial and f 1 is an upper portion of the first polynomial,
the third polynomial is f 0 +f 1 in the first ring, and
fourth polynomial is f 0 −f 1 in the second ring.
10. The data processing system of claim 8 , 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.
11. The data processing system of claim 8 , 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 comprises:
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.
12. The data processing system of claim 11 , wherein
the third first ring is [X]/(X N/4 −1), and
the fourth ring is [X]/(X N/4 +1).
13. The data processing system of claim 11 , 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.
14. The data processing system of claim 8 , wherein the cryptographic operation is a lattice-based cryptographic operation.