# US 2022/0286286 A1 · Method for multiplying polynomials for a cryptographic operation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0286286 A1
- Document ID: US20220286286A1
- Status: Published application
- Kind: A1
- Application number: 17/190,986
- Filed: 2021-03-03
- Published: 2022-09-08
- Earliest claimed: 2021-03-03
- Assignees: NXP B.V.
- Applicants: NXP B.V.
- Inventors: Joost Roland Renes; Joppe Willem Bos; Tobias Schneider; Christine van Vredendaal
- Web page: https://patentgrep.com/patent/US20220286286A1

## CPC

- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 1

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, comprising:
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
wherein the method allows a verification, encryption, or decryption operation using the multiplication of the first polynomial and the second polynomial with integer coefficients to be performed on the processor for post-quantum cryptography.

### Claim 2 (depends on 1)

The method of claim 1, wherein
the first ring is [X]/(XN/2−1), and
the second ring is [X]/(XN/2+1).

### Claim 3 (depends on 1)

The method of claim 1, wherein
the first polynomial f is f=f0+XN/2f1 in the ring [X]/(XN−1), wherein f0 is a lower portion of the first polynomial and f1 is an upper portion of the first polynomial,
the third polynomial is f0+f1 in the first ring, and
fourth polynomial is f0−f1 in the second ring.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

The method of claim 5, 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).

### Claim 7 (depends on 5)

The method of claim 5, wherein
the first polynomial and the sconed 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.

### Claim 8 (depends on 1)

The method of claim 1, wherein the cryptographic operation is a lattice-based cryptographic operation.

### Claim 9

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, 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; and
instructions for combining the first multiplication result and the second multiplication result using the map
wherein the method allows a verification, encryption, or decryption operation using the multiplication of the first polynomial and the second polynomial with integer coefficients to be performed on the processor for post-quantum cryptography.

### Claim 10 (depends on 9)

The data processing system of claim 9, wherein
the first ring is [X]/(XN/2−1), and
the second ring is [X]/(XN/2+1).

### Claim 11 (depends on 9)

The data processing system of claim 9, wherein
the first polynomial f is f=f0+XN/2f1 in the ring [X]/(XN−1), wherein f0 is a lower portion of the first polynomial and f1 is an upper portion of the first polynomial,
the third polynomial is f0+f1 in the first ring, and
fourth polynomial is f0−f1 in the second ring.

### Claim 12 (depends on 9)

The data processing system of claim 9, 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.

### Claim 13 (depends on 9)

The data processing system of claim 9, 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.

### Claim 14 (depends on 13)

The data processing system of claim 13, 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).

### Claim 15 (depends on 13)

The data processing system of claim 13, wherein
the first polynomial and the sconed 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.

### Claim 16 (depends on 9)

The data processing system of claim 9, wherein the cryptographic operation is a lattice-based cryptographic operation.