# US 2021/0279040 A1 · Number-theoretic transform processing apparatus, number-theoretic transform processing method, and computer program product

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

- Number: US 2021/0279040 A1
- Document ID: US20210279040A1
- Status: Published application
- Kind: A1
- Application number: 17/005,390
- Filed: 2020-08-28
- Published: 2021-09-09
- Earliest claimed: 2020-03-06
- Assignees: Kabushiki Kaisha Toshiba
- Applicants: Kabushiki Kaisha Toshiba
- Inventors: Tomoko YONEMURA
- Web page: https://patentgrep.com/patent/US20210279040A1

## CPC

- G06F 7/725: {over elliptic curves}
- G10L 21/0208: Noise filtering
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

According to an embodiment, a number-theoretic transform processing apparatus for a noise in lattice-based cryptography, includes a processor configured to perform number-theoretic transform of the noise using a precomputation table including a combination of products of one or more elements that belong to a subspace of a finite field Zq and indicate coefficients of the noise, with one or more number-theoretic transform constants.

## Claims

### Claim 1

A number-theoretic transform processing apparatus for a noise in lattice-based cryptography, comprising
a processor configured to perform number-theoretic transform of the noise using a precomputation table including a combination of products of one or more elements that belong to a subspace of a finite field Zq and indicate coefficients of the noise, with one or more number-theoretic transform constants.

### Claim 2 (depends on 1)

The apparatus according to claim 1, wherein
the precomputation table includes a combination of products of all elements belonging to the subspace, with the one or more number-theoretic transform constants.

### Claim 3 (depends on 1)

The apparatus according to claim 1, wherein
the precomputation table includes a combination of products of one or more elements except zero in elements belonging to the subspace, with the one or more number-theoretic transform constants.

### Claim 4 (depends on 1)

The apparatus according to claim 1, wherein
the precomputation table includes only one of a pair of products having values that are converted to each other by changing between plus and minus signs.

### Claim 5 (depends on 1)

The apparatus according to claim 1, wherein
the precomputation table includes a combination of products of one or more elements that occur as coefficients of the noise at higher frequencies than a threshold frequency of occurrence among elements belonging to the subspace, with the one or more number-theoretic transform constants.

### Claim 6 (depends on 1)

The apparatus according to claim 1, wherein
the processor computes a product of a number-theoretic transform constant with a coefficient of the noise by performing additions or subtractions over the finite field Zq plural times.

### Claim 7 (depends on 6)

The apparatus according to claim 6, wherein
the product of the number-theoretic transform constant with the coefficient of the noise includes a first product stored in the precomputation table and a second product not stored in the precomputation table, and
the processor reads out the first product from the precomputation table and computes the second product by performing additions or subtraction over the finite field Zq plural times.

### Claim 8

A number-theoretic transform processing method for a noise in lattice-based cryptography, comprising:
reading out a precomputation table including a combination of products of one or more elements that belong to a subspace of a finite field Zq and indicate coefficients of the noise, with one or more number-theoretic transform constants, from a storage; and
performing number-theoretic transform of the noise using the precomputation table.

### Claim 9

A computer program product having a non-transitory computer readable medium including programmed instructions, the instructions causing a computer configured to perform number-theoretic transform processing of a noise in lattice-based cryptography, to function as a processor that performs number-theoretic transform of the noise using a precomputation table including a combination of products of one or more elements that belong to a subspace of a finite field Zq and indicate coefficients of the noise, with one or more number-theoretic transform constants.