Encryption device, key generation device, and computer program product for encryption

A key generation device comprising:

• a memory;
• and
• one or more processors coupled to the memory and configured to:
• generate, as a public key, an n-variable indeterminate equation X(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of a univariable polynomial ring Fp[t] on a finite field Fp and is determined depending on a total degree of each term, and acquire a prime number p, a degree d, a total degree Dx regarding variables x1, . . . , xn, and a degree dx,ν of a coefficient of a term of the total degree ν, which are used when one or more zero-points u of the n-variable indeterminate equation X(x1, . . . , xn) are generated as a private key;
• generate n d-degree polynomials ux1(t), . . . , uxn(t) included in the univariable polynomial ring Fp[t], the n d-degree polynomials having n (d+1) random numbers from 0 to p-1 randomly generated as coefficients, and generate the dx,ν-degree polynomial τij(t) (i+j=ν≤Dx) that is a coefficient other than a constant term of the n-variable indeterminate equation X(x1, . . . , xn ) ;
• calculate a provisional constant term of the n-variable indeterminate equation X(x1, . . . , xn) from the n polynomials ux1 (t), . . . , uxn (t) and the polynomial τij(t) (i+j=ν≤Dx), and generate the n-variable indeterminate equation X(x1, . . . , xn) based on a quotient and a remainder obtained by dividing the provisional constant term by a polynomial uxi(t)uxj(t);
• and
• output the n polynomials ux1(t), . . . , uxn(t) as the private key and output the n-variable indeterminate equation X(x1, . . . , xn) as the public key.

An encryption device comprising:

• a memory;
• and
• one or more processors coupled to the memory and configured to:
• acquire, as a public key, an n-variable indeterminate equation X(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of a univariable polynomial ring Fp[t] on a finite field Fp and is determined depending on a total degree of each term;
• embed a plaintext M in coefficients of an n-variable plaintext polynomial mi(x1, . . . , xn ) (i=1, 2) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• randomly generate an n-variable polynomial ri(x1, . . . , xn)having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient, randomly generate an n-variable polynomial si(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of the univariable polynomial ring Fp[t] and is determined depending on a total degree of each term, and randomly generate a noise polynomial ei(x1, . . . , xn) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• and
• generate a ciphertext ci(x1, . . . , xn) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial ri(x1, . . . , xn), the n-variable polynomial si(x1, . . . , xn), the noise polynomial e(x1, . . . , xn), and the n-variable indeterminate equation X(x1, . . . , xn)on the n-variable plaintext polynomial mi(x1, . . . , xn).

A computer program product for encryption comprising a non-transitory computer-readable medium including programmed instructions, the instructions causing a computer to execute:

• acquiring an n-variable symmetric indeterminate equation X(x1, . . . , xn) as a public key, the n-variable symmetric indeterminate equation X(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of a univariable polynomial ring Fp[t] on a finite field Fp and is determined depending on a total degree of each term, the n-variable symmetric indeterminate equation X(x1, . . . , xn) being symmetric with respect to at least two variables;
• embedding a plaintext M in coefficients of an n-variable plaintext polynomial m(x1, . . . , xn ) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• randomly generating an n-variable polynomial (x1, . . . , xn) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient, randomly generating an n-variable symmetric polynomial s(x1, . . . , xn) having an element that is less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient and is determined depending on a total degree of each term, and being symmetric with respect to at least two variables, and randomly generating a noise polynomial e(x1, . . . , xn) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• and
• generating a ciphertext c(x1, . . . , xn) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial r(x1, . . . , xn), the n-variable symmetric polynomial s(x1, . . . , xn), the noise polynomial e(x1, . . . , xn), and the n-variable symmetric indeterminate equation X(x1, . . . , xn) on the n-variable plaintext polynomial m(x1, . . . , xn ).

A computer program product for encryption comprising a non-transitory computer-readable medium including programmed instructions, the instructions causing a computer to execute:

• acquiring, as a public key, an n-variable indeterminate equation X(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of a univariable polynomial ring Fp[t] on a finite field Fp and is determined depending on a total degree of each term;
• embedding a plaintext M in coefficients of an n-variable plaintext polynomial mi(x1, . . . , xn ) (i=1, 2) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• randomly generating an n-variable polynomial ri(x1, . . . , xn) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient, randomly generating an n-variable polynomial si(x1, . . . , xn) having, as a coefficient, an element that is less than or equal to a constant degree of the univariable polynomial ring Fp[t] and is determined depending on a total degree of each term, and randomly generating a noise polynomial ei(x1, . . . , xn) having an element less than or equal to a constant degree of the univariable polynomial ring Fp[t] as a coefficient;
• and
• generating a ciphertext ci(x1, . . . , xn) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial r(x1, . . . , xn), the n-variable polynomial si(x1, . . . , xn), the noise polynomial ei(x1, . . . , xn), and the n-variable indeterminate equation X(x1, . . . , xn)on the n-variable plaintext polynomial mi(x1, . . . , xn).