Granted Patent B2

US 12,549,362 · App. 18/458,570 · Granted Feb 10, 2026

Inventor: Koichiro Akiyama (Setagaya Tokyo, JP)

Assignee: KABUSHIKI KAISHA TOSHIBA

H04L9/3026H04L9/06

Abstract

Claims (49)

1 . An encryption device comprising:

a memory; and

one or more processors coupled to the memory and configured to:

acquire a plaintext M from an application;

acquire, as a public key, an n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) having, as a coefficient, an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p and being symmetric with respect to at least two variables;

embed the plaintext M in coefficients of an n-variable plaintext polynomial m(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

randomly generate an n-variable polynomial r(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient, randomly generate an n-variable symmetric polynomial s(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient and being symmetric with respect to at least two variables, and randomly generate a noise polynomial e(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

generate a ciphertext c(x 1 , . . . , x n ) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial r(x 1 , . . . , x n ), the n-variable symmetric polynomial s(x 1 , . . . , x n ), the noise polynomial e(x 1 , . . . , x n ), and the n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) on the n-variable plaintext polynomial m(x 1 , . . . , x n ); and

output the ciphertext c(x 1 , . . . , x n ) to the application.

2 . A decryption device comprising:

a memory; and

one or more processors coupled to the memory and configured to:

acquire a ciphertext c(x 1 , . . . , x i , . . . x j , . . . , x n ) from an application, where 1≤i≤j≤n;

acquire, as a private key, one or more zero-points u of an n-variable symmetric indeterminate equation X(x 1 , . . . x i , . . . x j , . . . , x n ) having an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p as a coefficient and being symmetric with respect to at least two variables x i and x j (1≤i≤j≤n);

generate a univariable polynomial h 1 (t) by substituting the zero-point u into the ciphertext c(x 1 , . . . , x i , . . . x j , . . . , x n ), and generate a univariable polynomial h 2 (t) by substituting the zero-point u into a ciphertext c(x 1 , . . . , x j , . . . x i , . . . , x n ) obtained by inverting the variable x i and the variable x j of the ciphertext c(x 1 , . . . , x i , . . . , x j , . . . , x n );

calculate an approximate GCD (Greatest Common Divisor) of the univariable polynomial h k (t)(k=1, 2) to obtain a univariable polynomial m(u) obtained by substituting the zero-point u into an n-variable plaintext polynomial m(x 1 , . . . , x n );

obtain a plaintext polynomial m(x 1 , . . . , x n ) by solving simultaneous linear equations derived from the univariable polynomial m(u) and the one or more zero-points u;

decrypt a plaintext M from coefficients of the plaintext polynomial m(x 1 , . . . , x n ); and

output the plaintext M to the application.

3 . An encryption method implemented by a computer functioning as an encryption device, the method comprising:

acquiring, by the encryption device, a plaintext M from an application;

acquiring, by the encryption device, as a public key, an n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) having, as a coefficient, an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p and being symmetric with respect to at least two variables;

embedding, by the encryption device, h plaintext M in coefficients of an n-variable plaintext polynomial m(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

by the encryption device, randomly generating an n-variable polynomial r(x 1 , . . . x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient, randomly generating an n-variable symmetric polynomial s(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient and being symmetric with respect to at least two variables, and randomly generating a noise polynomial e(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

generating, by the encryption device, a ciphertext c(x 1 , . . . , x n ) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial r(x 1 , . . . , x n ), the n-variable symmetric polynomial s(x 1 , . . . , x n ), the noise polynomial e(x 1 , . . . , x n ), and the n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) on the n-variable plaintext polynomial m(x 1 , . . . , x n ); and

outputting the ciphertext c(x 1 , . . . , x n ) to the application.

4 . A decryption method implemented by a computer functioning as a decryption device, the method comprising:

acquiring, by the decryption device, a ciphertext c(x 1 , . . . x i , . . . x j , . . . , x n ) from an application, where 1≤i≤j≤n;

acquiring, by the decryption device, as a private key, one or more zero-points u of an n-variable symmetric indeterminate equation X(x 1 , . . . x i , . . . x j , . . . , x n ) having an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p as a coefficient and being symmetric with respect to at least two variables x i and x j (1≤i≤j≥n);

by the decryption device, generating a univariable polynomial h 1 (t) by substituting the zero-point u into the ciphertext c(x 1 , . . . , x i , . . . , x j , . . . , x n ), and generating a univariable polynomial h 2 (t) by substituting the zero-point u into a ciphertext c(x 1 , . . . , x j , . . . x i , . . . , x n ) obtained by inverting the variable x i and the variable x j of the ciphertext c(x 1 , . . . , x i , . . . , x j , . . . , x n );

calculating, by the decryption device, an approximate GCD (Greatest Common Divisor) of the univariable polynomial h k (t) (k=1, 2) to obtain a univariable polynomial m(u) obtained by substituting the zero-point u into an n-variable plaintext polynomial m(x 1 , . . . , x n );

obtaining, by the decryption device, a plaintext polynomial m(x 1 , . . . , x n ) by solving simultaneous linear equations derived from the univariable polynomial m(u) and the one or more zero-points u;

decrypting, by the decryption device, a plaintext M from coefficients of the plaintext polynomial m(x 1 , . . . , x n ); and

outputting the plaintext M to the application.

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

acquiring a plaintext M from an application;

acquiring, as a public key, an n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) having, as a coefficient, an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p and being symmetric with respect to at least two variables;

embedding the plaintext M in coefficients of an n-variable plaintext polynomial m(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

randomly generating an n-variable polynomial r(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient, randomly generating an n-variable symmetric polynomial s(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient and being symmetric with respect to at least two variables, and randomly generating a noise polynomial e(x 1 , . . . , x n ) having an element of less than or equal to a constant degree of the univariable polynomial ring F p [t] as a coefficient;

generating a ciphertext c(x 1 , . . . , x n ) by encryption processing of performing an operation including at least one of addition, subtraction, and multiplication of the n-variable polynomial r(x 1 , . . . , x n ), the n-variable symmetric polynomial s(x 1 , . . . , x n ), the noise polynomial e(x 1 , . . . , x n ), and the n-variable symmetric indeterminate equation X(x 1 , . . . , x n ) on the n-variable plaintext polynomial m(x 1 , . . . , x n ); and

outputting the ciphertext c(x 1 , . . . , x n ) to the application.

6 . A computer program product for decryption comprising a non-transitory computer-readable medium including instructions stored thereon, the instructions causing a computer to execute:

acquiring a ciphertext c(x 1 , . . . x i , . . . x j , . . . , x n ) from an application, where 1≤i≤j≤n;

acquiring, as a private key, one or more zero-points u of an n-variable symmetric indeterminate equation X(x 1 , . . . x i , . . . x j , . . . , x n ) having an element of less than or equal to a constant degree of a univariable polynomial ring F p [t] on a finite field F p as a coefficient and being symmetric with respect to at least two variables x i and x j (1≤i≤j≤n);

generating a univariable polynomial h 1 (t) by substituting the zero-point u into the ciphertext c(x 1 , . . . , x i , . . . , x j , . . . , x n ), and generating a univariable polynomial h 2 (t) by substituting the zero-point u into a ciphertext c(x 1 , . . . x j , . . . x i , . . . , x n ) obtained by inverting the variable x i and the variable x j of the ciphertext c(x 1 , . . . , x i , . . . x j , . . . , x n );

calculating an approximate GCD (Greatest Common Divisor) of the univariable polynomial h k (t)(k=1, 2) to obtain a univariable polynomial m(u) obtained by substituting the zero-point u into an n-variable plaintext polynomial m(x 1 , . . . , x n );

obtaining a plaintext polynomial m(x 1 , . . . , x n ) by solving simultaneous linear equations derived from the univariable polynomial m(u) and the one or more zero-points u;

decrypting a plaintext M from coefficients of the plaintext polynomial m(x 1 , . . . , x n ); and

outputting the plaintext M to the application.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (50)