Patent ID: 8311215

Claim:
An encryption apparatus including: an embedding device configured to embed a message m as a coefficient of a three-variable plaintext polynomial m(x,y,t) when encrypting the message m if a fibration X(x,y,t) of an algebraic surface X is a public key and one or more sections corresponding to the fibration X(x,y,t) are private keys; a first generation device configured to generate a three-variable discriminant polynomial f(x,y,t) in such a manner that a degree of a one-variable polynomial obtained when assigning the section becomes larger than a degree of a one-variable polynomial obtained when assigning the section to the plaintext polynomial; a second generation device configured to randomly generate three or more pairs of polynomials r i (x,y,t) and s i (x,y,t) (i=1, . . . , k); and an encryption device configured to generate three or more encrypted texts F i (x,y,t)=E(m,s i ,r i ,f,X) (i=1, . . . , k) by processing of adding or subtracting a multiplication result f(x,y,t)s i (x,y,t) of the discriminant polynomial f(x,y,t) and the polynomial s i (x,y,t) and a multiplication result X(x,y,t)r i (x,y,t) of the fibration X(x,y,t) and the polynomial r i (x,y,t) with respect to the plaintext polynomial m(x,y,t).