Encryption apparatus, decryption apparatus, key generation apparatus, program, and method

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 one section 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 polynomial generation device executed by the processor and configured to generate two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) each having three variables x, y, and t;
• a 1-variable irreducible 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 a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, 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 1-variable irreducible polynomial f(t), the two pairs of polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t), and the fibration X(x, y, t) of the algebraic surface X which is opened to the public;
• 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 1-variable irreducible 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.

A decryption apparatus for decrypting a message m from ciphertext F=Epk(m, p, q, f, X) on the basis of two sections D1 and D2 which are private keys to be held in advance and correspond to a fibration X(x, y, t)=0 of an algebraic surface X, in inputting the ciphertext F which is generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t , a 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, and the fibration X(x, y, t) of the algebraic surface X which is a public key with respect to the plaintext polynomial m(t), the decryption apparatus comprising:

• a section substituting device executed by a processor and configured to substitute the sections D1 and D2 into the input ciphertext F to generate two 1-variable polynomials h1(t) and h2(t);
• a polynomial subtraction device executed by the processor and configured to subtract the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• a factorization device executed by the processor and configured to factorize the subtraction result {h1(t)−h2(t)};
• a polynomial extraction device executed by the processor and configured to extract an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• a remainder computing device executed by the processor and configured to compute a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded in the coefficients of the plaintext polynomial m(t) with one variable t and degree not higher than the degree (r−1) and some coefficients of the 1-variable irreducible polynomial f(t) with a degree not lower than the degree r, and
• which further comprises a plaintext expanding device configured to expand the plaintext polynomial m(t) obtained by the remainder computing device and the irreducible polynomial f(t) extracted by the polynomial extraction device to obtain the message m.

A decryption apparatus for decrypting a message m from a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, f, X) on the basis of one section D which is private keys to be held in advance and corresponds to a fibration X(x, y, t)=0 of an algebraic surface X, in inputting the ciphertexts F1 and F2 which are generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) at least one pair of which are different from each other, and the fibration X(x, y, t) of the algebraic surface X which is opened to the public with respect to the plaintext polynomial m(t), the decryption apparatus comprising:

• a section substituting device executed by a processor and configured to substitute the section D into the two input ciphertexts F1 and F2 to generate two 1-variable polynomials h1(t) and h2(t);
• a polynomial subtraction device executed by the processor and configured to subtract the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• a factorization device executed by the processor and configured to factorize the subtraction result {h1(t)−h2(t)};
• a polynomial extraction device executed by the processor and configured to extract an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• a remainder computing device executed by the processor and configured to compute a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded 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 the 1-variable irreducible polynomial f(t) with a degree not lower than the degree r;
• which further comprises a plaintext expanding device configured to expand the plaintext polynomial m(t) obtained by the remainder computing device and the irreducible polynomial f(t) extracted by the polynomial extraction device to obtain the message m;
• a second remainder computing device configured to compute a remainder by dividing the 1-variable polynomial h2(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• and
• a verification device configured to verify that the two plaintext polynomials m(t) obtained by the respective remainder computing devices coincide with each other, by comparing the plaintext polynomials.

A key generation apparatus for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and two sections D1 and D2 which are private keys for decrypting the encrypted message m and correspond to the fibration X(x, y, t)=0 of the algebraic surface X, the key generation apparatus comprising:

• a first polynomial generation device executed by a processor and configured to generate a random 1-variable polynomial λx(t);
• a second plaintext generation device executed by the processor and configured to generate a 1-variable polynomial λy(t) which is divisible by the 1-variable polynomial λx(t);
• a third polynomial generation device executed by the processor and configured to generate two 1-variable polynomials ux(t) and vx(t) each indicating a variable x with a parameter t on the basis of the 1-variable polynomial λx(t) so as to make a difference {ux(t)−vx(t)} between the two 1-variable polynomials become equal to λx(t);
• a fourth polynomial generation device executed by the processor and configured to generate two 1-variable polynomials uy(t) and vy(t) each indicating a variable y with a parameter t on the basis of the 1-variable polynomial λy(t) so as to make a difference {uy(t)−vy(t)} between the two 1-variable polynomials become equal to λy(t);
• a section generation device executed by the processor and configured to generate the two sections D1:(x, y, t)=(ux(t), uy(t), t) and D2:(x, y, t)=(vx(t), vy(t), t) on the basis of the 1-variable polynomials ux(t), vx(t), uy(t), and vy(t);
• and
• a fibration generation device executed by the processor and configured to generate a fibration X(x, y, t) of the algebraic surface X which has the sections D1 and D2 .

A key generation apparatus for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and a section D which is a private key for decrypting the encrypted message m and corresponds to the fibration X(x, y, t)=0 of the algebraic surface X, the key generation apparatus comprising:

• a polynomial generation device executed by a processor and configured to generate a random 1-variable polynomial ξi(t) (where i is a natural number);
• a polynomial generation device executed by the processor and configured to generate two 1-variable polynomials ux(t) and uy(t) which indicate variables x and y of the algebraic surface with a parameter t;
• a section generation device executed by the processor and configured to generate the section D:(x, y, t)=(ux(t), uy(t), t) on the basis of the 1-variable polynomials ux(t) and uy(t);
• and
• a fibration generation device executed by the processor and configured to generate a fibration X(x, y, t) of the algebraic surface X which has the section D on the basis of the 1-variable polynomials ξi(t) and the section D.

A computer-readable storage medium used in an encryption apparatus and including computer executable instructions 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 computer readable storage medium comprising:

• first computer executable instructions which cause a computer to sequentially execute a process of embedding the message m as coefficients of a plaintext polynomial m(t) with a degree not higher than a degree (r−1);
• second computer executable instructions which cause the computer to sequentially execute a process of generating random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t;
• third computer executable instructions which cause the computer to sequentially execute a process of generating a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r;
• and fourth computer executable instructions which cause the computer to sequentially execute a process of generating ciphertext F=Epk(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 first computer executable instructions cause the computer to sequentially execute a process of separately embedding 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 third computer executable instructions cause the computer to sequentially execute a process of generating the 1-variable irreducible polynomial f(t) by selling, 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.

A computer-readable storage medium used in an encryption apparatus and including computer executable instructions 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 a private key, the private key for decryption being one section corresponding to the fibration X(x, y, t) of the algebraic surface X, the computer readable storage medium comprising:

• first computer executable instructions which cause a computer to sequentially execute a process of embedding the message m as coefficients of a plaintext polynomial m(t) with a degree not higher than a degree (r−1);
• second computer executable instructions which cause the computer to sequentially execute a process of generating two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) each having three variables x, y, and t;
• third computer executable instructions which cause the computer to sequentially execute a process of generating a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r;
• and
• fourth computer executable instructions which cause the computer to sequentially execute a process of generating a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, 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 1-variable irreducible polynomial f(t), the two pairs of polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t), and the fibration X(x, y, t) of the algebraic surface X which is opened to the public;
• wherein the first computer executable instructions cause the computer to sequentially execute a process of separately embedding 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 third computer executable instructions cause the computer to sequentially execute a process of generating the 1-variable irreducible polynomial f(t) by selling, 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.

A computer-readable storage medium used in a decryption apparatus and including computer executable instructions for decrypting a message m from a ciphertext F=Epk(m, p, q, f, X) on the basis of two sections D1 and D2 which are private keys to be held in advance and correspond to a fibration X(x, y, I)=0 of an algebraic surface X, in inputting the ciphertext F which is generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t, a 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, and the fibration X(x, y, t) of the algebraic surface X which is a public key with respect to the plaintext polynomial m(t), the computer readable storage medium comprising:

• first computer executable instructions which cause a computer to sequentially execute a process of substituting the sections D1 and D2 into the input ciphertext F to generate two 1-variable polynomials h1(t) and h2(t);
• second computer executable instructions which cause the computer to sequentially execute a process of subtracting the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• third computer executable instructions which cause the computer to sequentially execute a process of factorizing the subtraction result {h1(t)−h2(t)};
• fourth computer executable instructions which cause the computer to sequentially execute a process of extracting an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• fifth computer executable instructions which cause the computer to sequentially execute a process of computing a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded 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 the 1-variable irreducible polynomial f(t) with a degree not lower than the degree r, and further comprising
• which further comprises sixth computer executable instructions which cause the computer to sequentially execute a process of expanding the plaintext polynomial m(t) obtained by execution of the fifth computer executable instructions and the irreducible polynomial f(t) extracted by execution of the fourth computer executable instructions to obtain the message m.

A computer-readable storage medium used in a decryption apparatus and including computer executable instructions for decrypting a message m from a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, f, X) on the basis of one section D which is a private key to be held in advance and corresponds to a fibration X(x, y, t)=0 of an algebraic surface X, in inputting the ciphertexts F1 and F2 which are generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) at least one pair of which are different from each other, and the fibration X(x, y, t) of the algebraic surface X which is opened to the public with respect to the plaintext polynomial m(t), the computer readable storage medium comprising:

• first computer executable instructions which cause a computer to sequentially execute a process of substituting the section D into the two input ciphertexts F1 and F2 to generate two 1-variable polynomials h1(t) and h2(t);
• second computer executable instructions which cause the computer to sequentially execute a process of subtracting the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• third computer executable instructions which cause the computer to sequentially execute a process of factorizing the subtraction result {h1(t)−h2(t)};
• fourth computer executable instructions which cause the computer to sequentially execute a process of extracting an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• fifth computer executable instructions which cause the computer to sequentially execute a process of computing a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded 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 the 1-variable irreducible polynomial f(t) with a degree not lower than the degree r, and
• which further comprises sixth computer executable instructions which cause the computer to sequentially execute a process of expanding the plaintext polynomial m(t) obtained by execution of the fifth computer executable instructions and the irreducible polynomial f(t) extracted by execution of the fourth computer executable instructions to obtain the message m;
• seventh computer executable instructions which cause the computer to sequentially execute a process of computing a remainder by dividing the 1-variable polynomial h2(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• and
• eighth computer executable instructions which cause the computer to sequentially execute a process of verifying that the two plaintext polynomials m(t) obtained by execution of the fifth computer executable instructions and seventh computer executable instructions coincide with each other, by comparing the plaintext polynomials.

A computer-readable storage medium used in a key generation apparatus and including computer executable instructions for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and two sections D1 and D2 which are private keys for decrypting the encrypted message m and correspond to fibration X(x, y, t)=0 of the algebraic surface X, the computer readable storage medium comprising:

• first computer executable instructions which cause the computer to sequentially execute a process of generating a random 1-variable polynomial λx(t);
• second computer executable instructions which cause the computer to sequentially execute a process of generating a 1-variable polynomial λy(t) which is divisible by the 1-variable polynomial λx(t);
• third computer executable instructions which cause the computer to sequentially execute a process of generating two 1-variable polynomials ux(t) and vx(t) each indicating a variable x with a parameter t on the basis of the 1-variable polynomial λx(t) so as to make a difference {ux(t)−vx(t)} between the two 1-variable polynomials become equal to λx(t);
• fourth computer executable instructions which cause the computer to sequentially execute a process of generating two 1-variable polynomials uy(t) and vy(t) each indicating a variable y with a parameter t on the basis of the 1-variable polynomial λy(t) so as to make a difference {uy(t)−vy(t)} between the two 1-variable polynomials become equal to λy(t);
• fifth computer executable instructions which cause the computer to sequentially execute a process of generating the two sections D1:(x, y, t)=(ux(t), uy(t), t) and D2:(x, y, t)=(vx(t), vy(t), t) on the basis of the 1-variable polynomials ux(t), vx(t), uy(t), and vy(t);
• and
• sixth computer executable instructions which cause the computer to sequentially execute a process of generating a fibration X(x, y, t) of the algebraic surface X which has the sections D1 and D2.

A computer-readable storage medium used in a key generation apparatus and including computer executable instructions for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and a section D which is a private key for decrypting the encrypted message m and corresponds to the fibration X(x, y, t)=0 of the algebraic surface X, the computer readable medium comprising:

• first computer executable instructions which cause a computer to sequentially execute a process of generating a random 1-variable polynomial ξi(t) (where i is a natural number);
• second computer executable instructions which cause the computer to sequentially execute a process of generating two 1-variable polynomials ux(t) and uy(t) which indicate variables x an y of the algebraic surface with a parameter t;
• third computer executable instructions which cause the computer to sequentially execute a process of generating the section D:(x, y, t)=(ux(t), uy(t), t) on the basis of the 1-variable polynomials ux(t) and uy(t);
• and
• fourth computer executable instructions which cause the computer to sequentially execute a process of generating a fibration X(x, y, t) of the algebraic surface X which has the section D on the basis of the 1-variable polynomial ξi(t) and the section D.

An encryption method executed by 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 method comprising:

• embedding the message m as coefficients of a plaintext polynomial m(t) with a degree not higher than a degree (r−1);
• generating random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t;
• generating a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r;
• and
• generating ciphertext F=Epk(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 message m is separately embedded 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 1-variable irreducible polynomial f(t) is generated 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.

An encryption method executed by 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 a private key, the private key for decryption being one section corresponding to the fibration X(x, y, t) of the algebraic surface X, the encryption method comprising:

• embedding the message m as coefficients of a plaintext polynomial m(t) with a degree not higher than a degree (r−1);
• generating two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) each having three variables x, y, and t;
• generating a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r;
• and
• generating a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, 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 1-variable irreducible polynomial f(t), two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t) at least one pair of which are different from each other, and the fibration X(x, y, t) of the algebraic surface X which is opened to the public;
• wherein the message m is separately embedded 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 1-variable irreducible polynomial f(t) is generated 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.

A decryption method executed by a decryption apparatus for decrypting a message m from a ciphertext F=Epk(m, p, q, f, X) on the basis of two sections D1 and D2 which are private keys to be held in advance and correspond to a fibration X(x, y, t)=0 of an algebraic surface X, in inputting the ciphertext F which is generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of random polynomials p(x, y, t) and q(x, y, t) each having three variables x, y, and t , a 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, and the fibration X(x, y, t) of the algebraic surface X which is a public key with respect to the plaintext polynomial m(t), the decryption method comprising:

• substituting the sections D1 and D2 into the input ciphertext F to generate two 1-variable polynomials h1(t) and h2(t);
• subtracting the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• factorizing the subtraction result {h1(t)−h2(t)};
• extracting an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• computing a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded 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) with a degree not lower than the degree r, and
• which further comprises expanding the plaintext polynomial m(t) obtained as the remainder and the extracted irreducible polynomial f(t) to obtain the message m.

A decryption method executed by a decryption apparatus for decrypting a message m from a plurality of ciphertexts F1=Epk(m, p1, q1, f, X) and F2=Epk(m, p2, q2, f, X) on the basis of one section D which is a private key to be held in advance and corresponds to a fibration X(x, y, t)=0 of an algebraic surface X, the ciphertexts F1 and F2 which are generated from a plaintext polynomial m(t) in which the message m is embedded as coefficients of a plaintext polynomial m(t) with one variable t and a degree not higher than a degree (r−1) by encryption processing of performing computation including at least one of addition, subtraction, and multiplication of a random 1-variable irreducible polynomial f(t) with a degree not lower than a degree r, two pairs of random polynomials q1(x, y, t) and q2(x, y, t), and p1(x, y, t) and p2(x, y, t), and the fibration X(x, y, t) of the algebraic surface X which is opened to the public with respect to the plaintext polynomial m(t), the decryption method comprising:

• substituting the section D into the two input ciphertexts F1 and F2 to generate two 1-variable polynomials h1(t) and h2(t);
• subtracting the 1-variable polynomials h1(t) and h2(t) from each other to obtain a subtraction result {h1(t)−h2(t)};
• factorizing the subtraction result {h1(t)−h2(t)};
• extracting an irreducible polynomial f(t) having a highest degree from the factorization result;
• and
• computing a remainder by dividing the 1-variable polynomial h1(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• wherein the message m is separately embedded 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 the 1-variable irreducible polynomial f(t) with a degree not lower than the degree r, and
• which further comprises expanding the plaintext polynomial m(t) obtained as the remainder and the extracted irreducible polynomial f(t) to obtain the message m;
• and
• computing a remainder by dividing the 1-variable polynomial h2(t) by the irreducible polynomial f(t) to obtain a plaintext polynomial m(t) as the remainder;
• and
• verifying that the two plaintext polynomials m(t) obtained in the remainder computing steps coincide with each other, by comparing the plaintext polynomials.

A key generation method executed by a key generation apparatus for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and two sections D1 and D2 which are private keys for decrypting the encrypted message m and correspond to fibration X(x, y, t)=0 of the algebraic surface X, the key generation method comprising:

• generating a random 1-variable polynomial λx(t);
• generating a 1-variable polynomial λy(t) which is divisible by the 1-variable polynomial λx(t);
• generating two 1-variable polynomials ux(t) and vx(t) each indicating a variable x with a parameter t on the basis of the 1-variable polynomial λx(t) so as to make a difference {ux(t)−vx(t)} between the two 1-variable polynomials become equal to λy(t);
• generating two 1-variable polynomials uy(t) and vy(t) each indicating a variable y with a parameter t on the basis of the 1-variable polynomial λy(t) so as to make a difference {ux(t)−vx(t)} between the two 1-variable polynomials become equal to λy(t);
• generating the two sections D1:(x, y, t)=(ux(t), uy(t), t) and D2:(x, y, t)=(vx(t), vy(t), t) on the basis of the 1-variable polynomials ux(t), vx(t), uy(t), and vy(t);
• and
• generating a fibration X(x, y, t) of the algebraic surface X which has the sections D1 and D2.

A key generation method executed by a key generation apparatus for generating a fibration X(x, y, t) of an algebraic surface X which is a public key for encrypting a message m and a section D which is a private key for decrypting the encrypted message m and corresponds to the fibration X(x, y, t)=0 of the algebraic surface X, the key generation method comprising:

• generating a random 1-variable polynomial ξi(t) (where i is a natural number);
• generating two 1-variable polynomials ux(t) and uy(t) which indicate variables x and y of the algebraic surface with a parameter t;
• generating the section D:(x, y, t)=(ux(t), uy(t), t) on the basis of the 1-variable polynomials ux(t) and uy(t);
• and
• generating a fibration X(x, y, t) of the algebraic surface X which has the section D on the basis of the 1-variable polynomials ξi(t) and the section D.