An NTRU decryption method according to an embodiment includes: a step of determining a secret polynominal F′ in which -1, 0, and 1, which are coefficients of a secret polynominal F corresponding to a private key f, are respectively converted into natural numbers a, b, and c; a step of multiplying a predetermined integer p by each of the coefficients in a cryptogram array ei and storing the result in an array PEi (i being integers equal to or greater than 0 and less than N and N-1 being the maximum order of the cryptogram e and the secret polynominal F′); a step of allocating a random value as an initial value to a first array Ti[a] corresponding to the natural number a, a second array Ti[b] corresponding to the natural number b, and a third array Ti[c] corresponding to the natural number c; a step of allocating and accumulating the values stored in the array PEi for each of the first array Ti[a], the second array Ti[b], and the third array Ti[c] based on the order of the term having the natural numbers a, b, and c as coefficients in the secret polynominal F′; and a step of determining a plain text array mi corresponding to ei based on the value obtained by subtraction of the value accumulated in the first array Ti[a] from the value accumulated in the third array Ti[c].
展开▼
