Patent ID: 7688973

Claim:
An encryption apparatus for encrypting a message m on the basis of a fibration X(x, y, t)=0 of an algebraic surface X which is a public key, the public key corresponding to private keys, the private keys for decryption being two or more sections corresponding to the fibration X(x, y, t) of the algebraic surface X, the encryption apparatus comprising: a plaintext embedding device executed by a processor and configured to embed the message m as coefficients of a plaintext polynomial m(t) with a degree not higher than a degree (r−1); a first polynomial generation device executed by the processor and configured to generate random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t; a second polynomial generation device executed by the processor and configured to generate a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r; and a ciphertext generation device executed by the processor and configured to generate ciphertext F=E pk (m, p, q, f, X) from the plaintext polynomial m(t) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of the polynomials p(x, y, t), q(x, y, t), and f(t) and the defining equation X(x, y, t) with respect to the plaintext polynomial m(t); wherein the plaintext embedding device separately embeds the message m in the coefficients of the plaintext polynomial m(t) with one variable t and a degree not higher than the degree (r−1) and some coefficients of a candidate for the 1-variable irreducible polynomial f(t), and the second polynomial generation device generates the 1-variable irreducible polynomial f(t) by setting, to a random value, a coefficient of the coefficients of the candidate for the 1-variable irreducible polynomial f(t) in which the message m is not embedded.