Encryption device, decryption device, encryption method, decryption method, encryption program product, and decryption program product

Abstract

An encryption device includes hardware processors to: acquire a public key including an identification polynomial f(t) and a multivariable indeterminate equation X having elements of a ring F[t]/g(t) as coefficients; disperse and embed a message m as coefficients of plaintext polynomial factors mhaving, as coefficients, polynomials with a limited degree among the elements of the ring; generate a plaintext polynomial M by multiplying the plaintext polynomial factors m; randomly generate a random polynomial r having as a coefficient an element of the ring; randomly generate a noise polynomial e having as coefficients polynomials with a limited degree among the elements of the ring; and generate a ciphertext by encryption processing of performing an operation including adding, subtracting, or multiplying the identification polynomial f(t), the random polynomial r, the noise polynomial e, and the multivariable indeterminate equation X to, from, or by the plaintext polynomial M.