Patent ID: 11922135
Assignee: KABUSHIKI KAISHA TOSHIBA
Field: Computer technology (Electrical engineering)
Classification: CPC G  H | IPC G  H

Claim 8:
9. A number-theoretic transform processing method for a noise in lattice-based cryptography, comprising:
reading out, using a hardware processor, a precomputation table including a combination of products of 2k+1 or less elements (where k is a positive integer) that belong to a subspace of a finite field Zq and indicate coefficients of the noise, with 2n or less number-theoretic transform constants selected from number-theoretic transform constants of {1, ω, ω2, . . . , ωn-1} and {γ, γω, γω2, . . . , γωn-1} (where ωn≡1 (mod q), γ2≡ω (mod q)), from a storage; and
performing, using the hardware processor, number-theoretic transform of the noise using the precomputation table, without performing a computation for the products included in the precomputation table, reducing a number of Zq multiplications in the number-theoretic transform of the noise over a polynomial ring Rq.