According to each embodiment of this invention, an encryption apparatus, decryption apparatus, and key generation apparatus based on a public-key cryptographic scheme whose security is based on the divisor finding problem of obtaining a divisor on an algebraic surface which is a difficult problem that has not been solved by contemporary mathematics are realized by an arrangement using, as a private key, a section D of algebraic curves (divisors) on a fibration X(x, y, t) of an algebraic surface X. This makes it possible to create a public-key cryptographic scheme which can ensure security even in the advent of a quantum computer, can be securely realized by even current computers, and can be realized in a low-power environment.