Granted Patent B2

US 12,739,102 · App. 18/459,261 · Granted Sep 15, 2026

Inventor: Koichiro Akiyama (Tokyo, JP)

Assignee: Kabushiki Kaisha Toshiba

H04L9/0825H04L9/0869

Abstract

Claims (9)

1 . 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(x 1 , . . . , x n ) having, as a coefficient, an element that is less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p and is determined depending on a total degree of each term, and acquire a prime number p, a degree d, a total degree D x regarding variables x 1 , . . . , x n , and a degree d x,ν 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(x 1 , . . . , x n ) are generated as a private key;

generate n d-degree polynomials u x1 (t), . . . , u xn (t) included in the univariable polynomial ring F p [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=ν≤D x ) that is a coefficient other than a constant term of the n-variable indeterminate equation X(x 1 , . . . , x n );

calculate a provisional constant term of the n-variable indeterminate equation X(x 1 , . . . , x n ) from the n polynomials u x1 (t), . . . , u xn (t) and the polynomial τ ij (t) (i+j=ν≤Dx), and generate the n-variable indeterminate equation X(x 1 , . . . , x n ) based on a quotient and a remainder obtained by dividing the provisional constant term by a polynomial u xi (t)u xj (t); and

output the n polynomials u x1 (t), . . . , u xn (t) as the private key to an application that decrypts data encrypted with the public key and output the n-variable indeterminate equation X(x 1 , . . . , x n ) as the public key to the application, wherein

the n-variable indeterminate equation X(x 1 , . . . , x n ) is a symmetric indeterminate equation that is symmetric with respect to at least two variables, and

the one or more processors are configured to generate the dx ,ν -degree polynomial τ ij (t) (i+j=ν≤Dx) to be τ ji (t)=τ ij (t).

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (51)