METHOD AND APPARATUS FOR PUBLIC-KEY CRYPTOGRAPHY BASED ON STRUCTURED MATRICES

Abstract

A method of generating a public key and a secret key using a key generator is disclosed. The method includes acquiring an affine map and a secret central map, and generating a public key and a secret key using the affine map and the secret central map, in which the secret central map is expressed as a system of o multivariate quadratic polynomials, the system of o multivariate quadratic polynomials can be expressed as a structured matrix or a product of a submatrix of a structured matrix and a vector when v linear equations and v variables defined on a finite field are given.

Claims

1. A method of generating a public key and a secret key using a key generator comprising: acquiring an affine map {tilde over (T)} and a map (:.sup.n.fwdarw..sub.q.sup.m); and generating a public key (=∘T) and a secret key (, {tilde over (T)}) and a secret key using the affine map and the map, wherein the map (:.sup.n.fwdarw..sub.q.sup.m) is expressed as a system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of O multivariate quadratic polynomials, the system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of O multivariate quadratic polynomials is expressed as below when υ linear polynomials (L.sub.1, . . . , L.sub.υ) and υ variables (χ.sub.1, . . . , χ.sub.υ) defined on a finite field .sub.q are given, $.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, T:.sub.q.sup.n.fwdarw..sub.q.sup.n, {tilde over (T)}=T.sup.−1, M.sub.V is a structured matrix or a submatrix of a structured matrix,
m=o,
V={1, . . . , υ},
O={υ+1, . . . , υ+o}, |V|=υ, |O|=o, V is an index set for defining Vinegar variables, and O is an index set for defining Oil variables.

2. The method of claim 1, wherein, when the system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of O multivariate quadratic polynomials is expressed as below $.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ M.sub.V herein is a circulant matrix or a submatrix of a circulant matrix.

3. A computer program which is stored in a storage medium to perform the method of generating a public key and a secret key of claim 1.

4. An electronic signer comprising the key generator configured to perform the method of generating a public key and a secret key of claim 1, wherein the electronic signer further comprises: a signature generator configured to generate an electronic signature σ of a message M using the affine map {tilde over (T)}, the map , and the message M; and a signature verifier configured to verify the electronic signature σ using the message M, the electronic signature σ, and the public key (=∘T), wherein the signature generator configured to calculate a hash message (H(M)=ξ) for the message M, and calculate a solution (s=(s.sub.1, . . . , s.sub.n)) of (x)=ξ using .sup.−1(ξ)=s when ξ=(ξ.sub.1, . . . , ξ.sub.m) is given, and calculates {tilde over (T)}(s)=σ, signature verifier determines whether P(σ)=H(M) and verify the electronic signature σ according to a result of the determination,
H:{0,1}*.fwdarw..sub.q.sup.m,
and
H(M)=ξ=(ξ.sub.1, . . . , ξ.sub.m)∈.sub.q.sup.m.

5. A method of generating a public key and a secret key using a key generator comprising: acquiring an affine map {tilde over (T)} and a map (:.sup.n.fwdarw..sub.q.sup.m); and generating a public key (=∘T) and a secret key (, {tilde over (T)}) using the affine map and the map, wherein the map (:.sup.n.fwdarw..sub.q.sup.m) is expressed as a system (.sub.OV.sup.(1), . . . , .sub.OV.sup.(o)) of O multivariate quadratic polynomials, the system (.sub.OV.sup.(1), . . . , .sub.OV.sup.(o)) of O multivariate quadratic polynomials is expressed as below when υ variables (χ.sub.1, . . . , χ.sub.υ) and O variables (χ.sub.υ+1, χ.sub.υ+2, . . . , χ.sub.υ+o) defined on a finite field (.sub.q) are given $\begin{array}{cc}\left(\begin{array}{c}{ℱ}_{\mathrm{OV}}^{\left(o_1+1\right)}\\ {ℱ}_{\mathrm{OV}}^{\left(o_1+2\right)}\\ \mathrm{.Math.}\\ {ℱ}_{\mathrm{OV}}^{\left(o_1+o_2\right)}\end{array}\right)=\left(\begin{array}{cccc}{v}^T.Math.a_{11}& v^{.Math.T}.Math.a_{12}& \mathrm{.Math.}& \text{?}\\ v^T.Math.a_{21}& v^{.Math.T}.Math.a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^{.Math.T}& 0& \mathrm{.Math.}& 0\\ 0& v^T& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& v^T\end{array}\right).Math.\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& a_{11}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.21\right]\end{array}$ wherein, $.Math.B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right),M_{\mathrm{OV}}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right),.Math..Math.v^T=[\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& x_v],\end{array}.Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ T:.sub.q.sup.n.fwdarw..sub.q.sup.n, {tilde over (T)}=T.sup.−1, and, when each column vector a.sub.ij is regarded as an element of one matrix, each column vector a.sub.ij is selected such that M.sub.OV is a structured matrix and element values of b.sub.ij are selected such that B is also a structured matrix of the same form as M.sub.OV.

6. The method of claim 5, when o(=2k) is an even number, M.sub.OV is a block circulant matrix of vectors when M.sub.OV is expressed as below, $M_{\mathrm{OV}}=\left(\begin{array}{cccc}{a}_{11}& a_{21}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}{p}_1& p_2& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cc}P& Q\\ R& S\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ each of p.sub.i, q.sub.i, s.sub.i, r.sub.i is a column vector having a size υ, each of P, Q, R, S is a circulant matrix of vectors, and B is a block circulant matrix when B is expressed as below $B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}{t}_1& t_2& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$

7. A computer program that is stored in a storage medium for performing the method of generating a public key and a secret key of claim 5.

8. An electronic signer, comprising the key generator configured to perform the method of generating a public key and a secret key of claim 5, wherein the electronic signer further comprises: a signature generator configured to generate an electronic signature σ of a message M using the affine map {tilde over (T)}, the map , and the message M; and a signature verifier configured to verify the electronic signature σ using the message M, the electronic signature σ, and the public key (=∘T), wherein the signature generator configured to calculate a hash message H(M)=ξ for the message M, calculate a solution (s=(s.sub.1, . . . , s.sub.n) of (x)=ξ using .sup.−1(ξ)=s when ξ=(ξ.sub.1, . . . , ξ.sub.m) is given, and calculates {tilde over (T)}(s)=σ, the signature verifier determines whether P(σ)=H(M) and verify the electronic signature σ according to a result of the determination,
H:{0,1}*.fwdarw..sub.q.sup.m,
and
H(M)=ξ=(ξ.sub.1, . . . , ξ.sub.m)∈.sub.q.sup.m.

9. A method of generating a public key and a secret key using a key generator comprising: acquiring a first affine map {tilde over (S)}, a second affine map {tilde over (T)}, and a map (:.sup.n.fwdarw..sub.q.sup.m); and generating a public key =S∘∘T and a secret key ({tilde over (S)}, , {tilde over (T)}) using the first affine map, the second affine map, and the map, wherein, the map (:.sup.n.fwdarw..sub.q.sup.m) is expressed as a system (=, . . . , .sup.(m)) of multivariate quadratic polynomials having m=o.sub.1+o.sub.2 polynomials and n=υ+m variables, .sup.(i) for i=1, . . . , o.sub.1 is expressed as below, $.Math.\{\begin{array}{c}\text{?}.Math.\left(\text{?},\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?},\\ \text{?}.Math.\left(\text{?},\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}\end{array}.Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ .sub.V.sup.(i) for i=1, . . . , o.sub.1 is expressed as below when υ linear equations (L.sub.1, . . . , L.sub.υ) and υ variables (χ.sub.1, . . . , χ.sub.υ) defined on a finite field .sub.q are given $.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.1 is a structured matrix or a submatrix of a structured matrix, .sup.(i) for i=o.sub.1+1, . . . , m is expressed as below, $.Math.\{\begin{array}{c}\text{?}.Math.\left(\text{?},\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}\\ \text{?}.Math.\left(\text{?},\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}\end{array},.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ .sub.V.sup.(i) for i=o.sub.1+1, . . . , m is expressed as below when linear equations (L′.sub.1, . . . , L′.sub.υ+o.sub.1) with υ+o.sub.1 variables and υ+o.sub.1 variables and ‘ ’ variables are given $.Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right).Math.\left(\begin{array}{c}{L}_1^{\prime }\\ L_2^{\prime }\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V^2.Math.\left(\begin{array}{c}{L}_1^{\prime }\\ L_2^{\prime }\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.2 is a structured matrix or a submatrix of a structured matrix,
m=o.sub.1+o.sub.2,
S:.sub.q.sup.m.fwdarw..sub.q.sup.m, T:.sub.q.sup.n.fwdarw..sub.q.sup.n, {tilde over (S)}=S.sup.−1, {tilde over (T)}=T.sup.−1,
V={1, . . . , υ},
O.sub.1={υ+1, . . . , υ+o.sub.1},
O.sub.2={υ+o.sub.1+1, . . . , υ+o.sub.1+o.sub.2}, which |V|=υ, i=|O.sub.i|=o.sub.i for 1 and 2, V is an index set for defining Vinegar variables, and O.sub.1 and O.sub.2 are index sets for defining Oil variables.

10. The method of claim 9, wherein, when the map (:.sup.n.fwdarw..sub.q.sup.m) is expressed as a system (=, . . . , .sup.(m)) of multivariate quadratic polynomials having m=o.sub.1+o.sub.2 polynomials and n=υ+m variables, .sub.V.sup.(i) for i=1, . . . , o.sub.1 is expressed as below $.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \text{?}& x_1& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V^1.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.1 is a circulant matrix or a submatrix of a circulant matrix, .sup.(i) for i=o.sub.1+1, . . . , m is expressed as below $.Math.\{\begin{array}{c}\text{?})+\text{?}\\ \text{?}\end{array},.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ .sub.V.sup.(i) for i=o.sub.1+1, . . . , m is expressed as below $.Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\text{?}.Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V^2\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.2 is a circulant matrix or a submatrix of a circulant matrix.

11. A computer program that is stored in a storage medium for performing the method of generating a public key and a secret key of claim 9.

12. An electronic signer comprising the key generator configured to perform the method of generating a public key and a secret key of claim 9, wherein the electronic signer further comprises: a signature generator configured to generate an electronic signature σ of a message M using the first affine map ({tilde over (S)}), the second affine map ({tilde over (T)}), the map (), and the message M; and a signature verifier configured to verify the electronic signature σ using the message M, the electronic signature σ, and the public key (=S∘∘T), wherein the signature generator configured to calculate a hash message H(M) for the message M, calculate {tilde over (S)}(H(M))=ξ=(ξ.sub.1, . . . , ξ.sub.m)∈.sub.q.sup.m, calculate a solution (s=(s.sub.1, . . , s.sub.n)) of (x)=ξ using .sup.−1(ξ)=s when ξ=(ξ.sub.1, . . . , ξ.sub.m) is given, and calculate {tilde over (T)}(s)=σ, the signature verifier configured to determine whether P(σ)=H(M) and verify the electronic signature σ according to a result of the determination, and
H:{0, 1}*.fwdarw..sub.q.sup.m.

13. The electronic signer of claim 12, wherein, when a matrix R given for randomization of the first affine map {tilde over (S)} in a product {tilde over (S)}.Math.h of a vector h of .sub.q.sup.m and the first affine map {tilde over (S)} is a circulant matrix, the signature generator calculates {tilde over (S)}(H(M)) using an equation below
{tilde over (S)}(H(M))=({tilde over (S)}+R)(H(M))−R(H(M)).

14. The electronic signer of claim 12, wherein, when the matrix R given for the randomization of the first affine map {tilde over (S)} in the product {tilde over (S)}.Math.h of the vector h of .sub.q.sup.m and the first affine map {tilde over (S)} is a circulant matrix, the signature generator calculates {tilde over (S)}(H(M)) using an equation below
{tilde over (S)}(H(M))=({tilde over (S)}.Math.R.sup.−1.Math.R)(H(M)).

15. A method of generating a public key and a secret key using a key generator comprising: acquiring a first affine map ({tilde over (S)}), a second affine map ({tilde over (T)}), and a map (:.sup.n.fwdarw..sub.q.sup.m); and generating a public key (=S∘∘T) and a secret key ({tilde over (S)}, , {tilde over (T)}) using the first affine map, the second affine map, and the map, wherein the map (:.sup.n.fwdarw..sub.q.sup.m) is expressed as a system (=, . . . , .sup.(m)) of m=o.sub.1+o.sub.2 multivariate quadratic polynomials, a system (.sub.OV.sup.(1), . . . , .sub.OV.sup.(o.sup.1.sup.)) of the O.sub.1 multivariate quadratic polynomials is expressed as below when υ variables (χ.sub.1, . . . , χ.sub.υ) and O.sub.1 variables (χ.sub.υ+1, χ.sub.υ+2, . . . , χ.sub.υ+o.sub.1) defined on a finite field .sub.q are given $\left(\begin{array}{c}{ℱ}_{\mathrm{OV}}^{\left(1\right)}\\ {ℱ}_{\mathrm{OV}}^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T.Math.a_{11}& v^T.Math.a_{12}& \mathrm{.Math.}& \text{?}\\ v^T.Math.a_{21}& v^T.Math.a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& 0\\ 0& v^T& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& v^T\end{array}\right).Math.\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein $.Math.M_{\mathrm{OV},1}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math..Math.\mathrm{and}.Math..Math.B_1\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ are given,
v.sup.T=[χ.sub.1χ.sub.2 . . . χ.sub.υ], each column vector a.sub.ij is selected such that M.sub.OV,1 is a structured matrix and element values of b.sub.ij are selected such that B.sub.1 is also a structure matrix of the same form as M.sub.OV,1, when each column vector a.sub.ij is regarded as elements of one matrix, and .sub.OV.sup.(i) for i=o.sub.1+1, . . . , m is given as below, $\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& 0\\ 0& v^T& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& v^T\end{array}\right).Math.\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \square & \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, $.Math.M_{\mathrm{OV},2}=\left(\begin{array}{cccc}{a}_{11}^{\prime }& a_{12}^{\prime }& \mathrm{.Math.}& \text{?}\\ a_{21}^{\prime }& a_{22}^{\prime }& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math..Math.\mathrm{and}.Math..Math.B_2\left(\begin{array}{cccc}{b}_{11}^{\prime }& b_{12}^{\prime }& \mathrm{.Math.}& \text{?}\\ b_{21}^{\prime }& b_{22}^{\prime }& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ are given,
v′.sup.T=[χ.sub.1χ.sub.2 . . . χ.sub.υ+o.sub.1], each column vector a′.sup.ij is selected such that M.sub.OV,2 is a structured matrix and element values of b′.sub.ij are selected such that B.sub.2 is also a structured matrix of the same form as M.sub.OV,2, when each column vector (a′.sub.ij) is regarded as an element of one matrix, S:.sub.q.sup.m.fwdarw..sub.q.sup.m, T:.sub.q.sup.n.fwdarw..sub.q.sup.n, {tilde over (S)}=S.sup.−1, and {tilde over (T)}=T.sup.−1.

16. The method of claim 15, wherein, when o.sub.1=2k.sub.1 and o.sub.2=2k.sub.2 are given, F.sub.OV.sup.(i) for i=1, . . . , o.sub.1 is expressed as below $\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& 0\\ 0& v^T& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& v^T\end{array}\right).Math.\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ a_{21}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_1\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, $\text{?}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}{p}_1& p_2& \mathrm{.Math.}& \text{?}& q_1& q_2& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ p_2& p_1& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& q_1\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}.Math.\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ r_2& r_3& \mathrm{.Math.}& r_1& s_1& s_2& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cc}\text{?}& Q_1\\ R_1& S_1\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ each of p.sub.i, q.sub.i, s.sub.i, r.sub.i is a column vector having the size υ, each of P.sub.1, Q.sub.1, R.sub.1, S.sub.1 is a circulant matrix of vectors, M.sub.OV,1 is a block circulant matrix of vectors $\text{?}=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& q_1\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}.Math.\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ r_2& r_3& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ B.sub.1 is block circulant matrix, .sub.OV.sup.(i) for i=o.sub.1+1, . . . , m is expressed as below $\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_2\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& 0\\ 0& v^T& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \mathrm{.Math.}& v^T\end{array}\right).Math.\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ a_{21}^{\prime }& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B_2\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, $M_{\mathrm{OV}.Math..Math.2}=\left(\begin{array}{cccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}.Math.\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cc}\text{?}& Q_2\\ R_2& S_2\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ p′.sub.i, q′.sub.i, s′.sub.i, r′.sub.i are column vectors each having the size (υ+o.sub.1), each of P.sub.2, Q.sub.2, R.sub.2, S.sub.2 is a circulant matrix of vectors, M.sub.OV,2 is a block circulant matrix of vectors, $\begin{array}{cc}\text{?}=\left(\begin{array}{cccc}{V}_{11}& V_{12}& \mathrm{.Math.}& \text{?}\\ V_{21}& V_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}.Math.\text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \end{array}$ B.sub.2 is a block circulant matrix, and m=o.sub.1+o.sub.2.

17. The method of claim 16, wherein, when υ linear equations (L.sub.1, . . . , L.sub.υ) and υ variables (χ.sub.1, . . . , x.sub.υ) defined on the finite field are given, .sub.V.sup.(i) for i=1, . . . , o.sub.1 is expressed as below, $.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \text{?}& x_1& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \text{?}& \text{?}& \text{?}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\text{?}.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)$ $\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.1 is a circulant matrix or a submatrix of a circulant matrix, .sub.V.sup.(i) for i=o.sub.1+1, . . . , m is expressed as below when linear equations (L′.sub.1, . . . , L′.sub.υ+o.sub.1) with υ+o.sub.1 variables and υ+o.sub.1 variables are given $.Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \text{?}& x_1& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \text{?}& \text{?}& \text{?}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}{L}_1^{\prime }\\ L_2^{\prime }\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\text{?}.Math.\left(\begin{array}{c}{L}_1^{\prime }\\ L_2^{\prime }\\ \mathrm{.Math.}\\ \text{?}\end{array}\right),.Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ wherein, M.sub.V.sup.2 is a circulant matrix or a submatrix of a circulant matrix, .sup.(i) for i=1, . . . , m is expressed as below, $.Math.\{\begin{array}{c}\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?},\\ \text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?},\end{array}.Math..Math..Math.\{\begin{array}{c}\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?},\\ \text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)=\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?}.Math.\left(x_1,\mathrm{.Math.}.Math.,\text{?}\right)+\text{?},\end{array}.Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}$ and m=o.sub.1+o.sub.2.

18. A computer program that is stored in a storage medium for performing the method of generating a public key and a secret key of claim 15.

19. An electronic signer comprising the key generator configured to perform the method of generating a public key and a secret key of claim 15, wherein the electronic signer further comprises: a signature generator configured to generate an electronic signature σ of a message M using the first affine map ({tilde over (S)}), the second affine map ({tilde over (T)}), the map (), and the message M; and a signature verifier configured to verify the electronic signature σ using the message M, the electronic signature σ, and the public key (=S∘∘T), wherein the signature generator configured to calculate a hash message H(M) for the message M, calculate {tilde over (S)}(H(M))=ξ=(ξ.sub.1, . . . , ξ.sub.m)∈.sub.q.sup.m, calculate a solution (s=(s.sub.1, . . . , s.sub.n)) of (x)=ξ using .sup.−1(ξ)=s when ξ=(ξ.sub.1, . . . , ξ.sub.m) is given, and calculate {tilde over (T)}(s)=σ, the signature verifier configured to determine whether P(σ)=H(M), and verify the electronic signature σ according to a result of the determination, and
H:{0, 1}*.fwdarw..sub.q.sup.m.

20. The electronic signer of claim 19, wherein, when a matrix R given for randomization of the first affine map {tilde over (S)} in a product {tilde over (S)}.Math.h of a vector h of .sub.q.sup.m and the first affine map ({tilde over (S)}) is a circulant matrix, the signature generator calculates {tilde over (S)}(H(M)) using an equation below
{tilde over (S)}(H(M))=({tilde over (S)}+R)(H(M))−R(H(M)).

21. The electronic signer of claim 19, wherein, when the matrix R given for randomization of the first affine map {tilde over (S)} in a product {tilde over (S)}.Math.h of a vector h of .sub.q.sup.m and the first affine map ({tilde over (S)}) is a circulant matrix, the signature generator calculates {tilde over (S)}(H(M)) using an equation below
{tilde over (S)}(H(M))=({tilde over (S)}.Math.R.sup.−1.Math.R)(H(M)).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] FIG. 1 is a block diagram of an electronic signer based on multivariate quadratic polynomials with one layer according to embodiments of the present invention;

[0014] FIG. 2 is a flowchart for describing an operation of the electronic signer based on multivariate quadratic polynomials shown in FIG. 1;

[0015] FIG. 3 is a block diagram of an electronic signer based on multivariate quadratic polynomials with two layers according to embodiments of the present invention; and

[0016] FIG. 4 is a flowchart for describing an operation of the electronic signer based on multivariate quadratic polynomials shown in FIG. 3.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0017] In the present specification, an electronic signature algorithm (or an apparatus, a method, and/or a computer program stored in a storage medium capable of performing the electronic signature algorithm) based on a generation of systems of multivariate quadratic polynomials (or equations), which can be expressed by a product of a structured matrix (or a submatrix of the structured matrix) and a vector after performing a suitable operation or operations, is disclosed.

[0018] 1. Generation of O (here, O is a natural number) quadratic polynomials which can be expressed by product of structured matrix or submatrix of structured matrix and vector using υ (Here, υ is a natural number) linear polynomials and υ variables (here, χ.sub.i, 1≤i≤υ).

[0019] When .sub.q is a finite field with q (here, q is a natural number) elements, and υ linear polynomials (L.sub.1, . . . , L.sub.υ) and υ variables (χ.sub.1, . . . , χ.sub.υ) defined on the finite field (.sub.q) are given, a system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of O quadratic polynomials, which can be expressed in a form of a product of a structured matrix (or a submatrix of a structured matrix) and a vector as shown in Equation 1 is generated.

[0020] The system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of quadratic polynomials will be expressed by Equation 1, in which M.sub.V is defined as a structured matrix (or a submatrix of a structured matrix).

[00012]$\begin{array}{cc}\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ {ℱ}_V^{\left(o\right)}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& x_o\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ L_v\end{array}\right)=M_v.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ L_v\end{array}\right)& \left[\mathrm{Equation}.Math..Math.1\right]\end{array}$

[0021] Here, the structure matrix includes a case in which complexity of the product of a structured matrix (or a submatrix of a structured matrix) and a vector is less than or equal to O(υ.sup.2).

1-1. Structured Matrix is Circulant Matrix

[0022] When υ linear polynomials (L.sub.1, . . . , L.sub.υ) and υ variables (χ.sub.1, . . . , χ.sub.υ) are given to an apparatus or a computer program, a system (.sub.V.sup.(1), . . . , .sub.V.sup.(o)) of O quadratic polynomials is generated as shown in Equation 2. Here, O is the number of quadratic polynomials, which is represented as O when there is one layer, and, when there are two layers, a first layer thereof is represented as O.sub.1 and a second layer is represented as O.sub.2.

[00013]$\begin{array}{cc}.Math.{ℱ}_V^{\left(1\right)}=x_1.Math.L_1+x_2.Math.L_2+\mathrm{.Math.}+\text{?}.Math.\text{?}.Math..Math..Math.{ℱ}_V^{\left(2\right)}=\text{?}.Math.L_1+x_1.Math.L_2+\mathrm{.Math.}+\text{?}.Math.\text{?}.Math..Math..Math.\mathrm{.Math.},.Math..Math.{ℱ}_V^{\left(o\right)}=\text{?}.Math.L_1+\text{?}.Math.L_2+\mathrm{.Math.}+\text{?}.Math.\text{?}.Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.2\right]\end{array}$

[0023] The system of quadratic polynomials in Equation 2 needs to be expressed in the form of a product of a circulant matrix (or a submatrix of a circulant matrix) and a vector as shown in Equation 3. That is, M.sub.V in Equation 3 is a circulant matrix or a submatrix of a circulant matrix.

[00014]$\begin{array}{cc}.Math.\left(\begin{array}{c}{ℱ}_V^{\left(1\right)}\\ {ℱ}_V^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=M_V.Math.\left(\begin{array}{c}{L}_1\\ L_2\\ \mathrm{.Math.}\\ \text{?}\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.3\right]\end{array}$

1-2. Additional Generation of System of Quadratic Equations Expressed by Block Circulant Matrix

[0024] After quadratic polynomials for variables (χ.sub.1, . . . , X.sub.υ) are selected as described in 1-1, a system (.sub.OV.sup.(1), . . . , .sub.OV.sup.(o)) of quadratic polynomials for o(=2k) (Here, k is a natural number) variables (χ.sub.υ+1, χ.sub.υ+2, . . . , χ.sub.υ+o) is additionally generated as shown in Equation 4.

[00015]$\begin{array}{cc}\left(\begin{array}{c}{ℱ}_{\mathrm{OV}}^{\left(1\right)}\\ {ℱ}_{\mathrm{OV}}^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T.Math.a_{11}& v^T.Math.a_{12}& \mathrm{.Math.}& \text{?}\\ v^T.Math.a_{21}& v^T.Math.a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& \text{?}\\ 0& v^T& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right).Math..Math.M_{\mathrm{OV}}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cc}P& \text{?}\\ \text{?}& S\end{array}\right).Math..Math.B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right)=\left(\begin{array}{cccccccc}\text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}& \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.4\right]\end{array}$

[0025] Here v.sup.T=[χ.sub.1 χ.sub.2 . . . χ.sub.υ], each of P, Q, R, S is a circulant matrix of vectors, M.sub.OV is a block circulant matrix of the vectors, and B is also a block circulant matrix with the same structure as M.sub.OV.

[0026] A system of quadratic equations such as in Equation 5 without quadratic terms that satisfy χ.sub.iχ.sub.j, i, j=υ+1, .. . , υ+o (here, each of i and j is a natural number) is generated by combining the system of quadratic polynomials in Equation 4 and the system of quadratic polynomials in Equation 2. Here, δ.sub.i is a constant term selected in the finite field (.sub.q).

[00016]$\begin{array}{cc}.Math.\{\begin{array}{c}{ℱ}^{\left(1\right)}\left(\text{?}\right)={ℱ}_V^{\left(1\right)}\left(\text{?}\right)+{ℱ}_{\mathrm{OV}}^{\left(1\right)}\left(\text{?}\right)+\text{?}\\ \mathrm{.Math.}\\ {ℱ}^{\left(o\right)}\left(\text{?}\right)={ℱ}_V^{\left(o\right)}\left(\text{?}\right).Math.\text{?}+{ℱ}_{\mathrm{OV}}^{\left(o\right)}\left(\text{?}\right)+\text{?}\end{array}.Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.5\right]\end{array}$

2. Generation of System of Quadratic Equations in Which Coefficient Matrix Has Structured Matrix Structure

[0027] In a system of quadratic polynomials having n=υ+o (n is a natural number) variables which can be expressed as shown in equation 6, it is assumed that there is a system (.sub.OV.sup.(i)) of quadratic polynomials for υ variables (χ.sub.1, . . . , χ.sub.υ) and O variables (χ.sub.υ+1, χ.sub.υ+2, . . . , χ.sub.υ+o).

[00017]$\begin{array}{cc}\left(\begin{array}{c}{ℱ}_{\mathrm{OV}}^{\left(1\right)}\\ {ℱ}_{\mathrm{OV}}^{\left(2\right)}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T.Math.a_{11}& v^T.Math.a_{12}& \mathrm{.Math.}& \text{?}\\ v^T.Math.a_{21}& v^T.Math.a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)=\left(\begin{array}{cccc}{v}^T& 0& \mathrm{.Math.}& \text{?}\\ 0& v^T& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math.\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right)+B\left(\begin{array}{c}\text{?}\\ \text{?}\\ \mathrm{.Math.}\\ \text{?}\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.6\right]\end{array}$

Here, v.sup.T=[χ.sub.1 χ.sub.2 . . . χ.sub.υ], and B and M.sub.OV are expressed as shown in Equation 7.

[00018]$\begin{array}{cc}.Math.B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& \text{?}\\ b_{21}& b_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right),M_{\mathrm{OV}}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& \text{?}\\ a_{21}& a_{22}& \mathrm{.Math.}& \text{?}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ \text{?}& \text{?}& \mathrm{.Math.}& \text{?}\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.7\right]\end{array}$

[0028] Here, when each column vector a.sub.ij is regarded as an element of one matrix, each column vector a.sub.ij is selected such that M.sub.OV is a structured matrix, element values of b.sub.ij are selected such that B is a structure matrix of the same form as M.sub.OV, thereby a system of desired quadratic polynomials is generated.

[0029] Here, the structured matrix includes a case in which complexity of obtaining an existing structured matrix or inverse matrix, or finding a solution of a system of a linear equation having a structured matrix as a coefficient matrix is less than or equal to O(n.sup.2). At this time, a size of the coefficient matrix of the system of a linear equation is n×n.

2-1. M.SUB.OV .and B Are Block Circulant Matrices (BC).

[0030] When (o=2k) is an even number, M.sub.OV and B are selected such that M.sub.OV and B are block circulant matrices, respectively, as shown in Equations 8 and 9.

[00019]$\begin{array}{cc}{M}_{\mathrm{OV}}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{.Math.}& a_{\text{?}}\\ a_{21}& a_{22}& \mathrm{.Math.}& a_{\text{?}}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ a_{o.Math.1}& a_{o.Math.2}& \mathrm{.Math.}& a_{\text{?}}\end{array}\right)=\left(\begin{array}{cccccccc}{p}_1& p_2& \mathrm{.Math.}& p_k& q_1& q_2& \mathrm{.Math.}& q_k\\ p_k& p_1& \mathrm{.Math.}& p_{k-1}& q_k& q_1& \mathrm{.Math.}& q_{k-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ p_2& p_3& \mathrm{.Math.}& p_1& q_2& q_3& \mathrm{.Math.}& q_1\\ r_1& r_2& \mathrm{.Math.}& r_k& s_1& s_2& \mathrm{.Math.}& s_k\\ r_k& r_1& \mathrm{.Math.}& r_{k-1}& s_k& s_1& \mathrm{.Math.}& s_{k-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ r_2& r_3& \mathrm{.Math.}& r_1& s_2& s_3& \mathrm{.Math.}& s_1\end{array}\right)=\left(\begin{array}{cc}P& Q\\ R& S\end{array}\right).Math..Math.\text{?}.Math.\text{indicates text missing or illegible when filed}& \left[\mathrm{Equation}.Math..Math.8\right]\end{array}$

Here, each of P, Q, R, S is a circulant matrix of vectors, and M.sub.OV is a block circulant matrix of the vectors.

[00020]$\begin{array}{cc}B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \mathrm{.Math.}& b_{}\\ b_{21}& b_{22}& \mathrm{.Math.}& b_{}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ b_{o.Math.1}& b_{o.Math.2}& \mathrm{.Math.}& b_{\mathrm{oo}}\end{array}\right)=\left(\begin{array}{cccccccc}{t}_1& t_2& \mathrm{.Math.}& t_k& u_1& u_2& \mathrm{.Math.}& u_k\\ t_k& t_1& \mathrm{.Math.}& t_{k-1}& u_k& u_1& \mathrm{.Math.}& u_{k-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ t_2& t_3& \mathrm{.Math.}& t_1& u_2& u_3& \mathrm{.Math.}& u_1\\ v_1& v_2& \mathrm{.Math.}& v_k& w_1& w_2& \mathrm{.Math.}& w_k\\ v_k& v_1& \mathrm{.Math.}& v_{k-1}& w_k& w_1& \mathrm{.Math.}& w_{k-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ v_2& v_3& \mathrm{.Math.}& v_1& w_2& w_3& \mathrm{.Math.}& w_1\end{array}\right)& \left[\mathrm{Equation}.Math..Math.9\right]\end{array}$