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

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.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority under 35 U.S.C. § 119 from Korean Patent Application No. 10-2019-0149105 filed on Nov. 19, 2019, this disclosures of which are hereby incorporated by reference in their entireties.

TECHNICAL FIELD

The present invention relates to public-key cryptography, and, in particular, to a method and an apparatus which can perform a digital signature algorithm based on multivariate quadratic polynomials based on structured matrices.

DISCUSSION OF RELATED ART

Digital signature based on multivariate quadratic polynomials refers to digital signature (or referred to as “electronic signature”) used in a multivariate cryptography system. Here, a multivariate cryptography system refers to a system having asymmetric cryptographic primitives based on multivariate polynomials defined on a finite field. In particular, when a degree of multivariate polynomials used in the multivariate cryptography system is 2, the multivariate cryptography system is referred to as a cryptography system based on multivariate quadratic polynomials.

SUMMARY

A technical object of the present invention is to provide a method, an apparatus, and a computer program, which can perform an electronic signature algorithm based on multivariate quadratic polynomials that can greatly reduce a length of a secret key by using structured matrices and quickly generate signatures by increasing efficiency in calculation.

According to embodiments of the present invention, a method of generating a public key and a secret key using a key generator includes acquiring an affine map {tilde over (T)} and a map:n→qm, and generating a public key=∘T and a secret key (, {tilde over (T)}) using the affine map and the map, in which the map:n→qmis expressed as a systemV(1), . . . ,V(o)of O multivariate quadratic polynomials, and the systemV(1), . . . ,V(o)of O multivariate quadratic polynomials is expressed as below when υ linear equations L1, . . . , Lυand υ variables χ1, . . . , χυdefined on a finite fieldqare given

(ℱ?(?)ℱ?(?)…ℱ?(?))=(x?x?…x?………)·(L1L2…L?)=M?·(L1L2…L?),?indicates text missing or illegible when filed

in which T:qn→qn, {tilde over (T)}=T−1, MVis 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.

A computer program which is stored in a storage medium stores the method of generating a public key and a secret key using a key generator.

According to the embodiments of the present invention, an electronic signer includes the key generator configured to perform the method of generating a public key and a secret key, 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, in which the signature generator calculates a hash message H(M)=ξ for the message M, calculates a solution s=(s1, . . . , sn) of(x)=ξ using−1(ξ)=s when ξ=(ξ1, . . . , ξm) is given, and calculates {tilde over (T)}(s)=σ, the signature verifier determines whether P(σ)=H(M) and verifies the electronic signature σ according to a result of the determination, H:{0, 1}*→qm, and H(M)=ξ=(ξ1, . . . , ξm)∈qm.

According to the embodiments of the present invention, a method of generating a public key and a secret key using a key generator includes acquiring an affine map {tilde over (T)} and a map:n→qm, and generating a public key=∘T and a secret key (, {tilde over (T)}) using the affine map and the map, in which the map:n→qmis expressed as a systemOV(1), . . . ,OV(o)of O multivariate quadratic polynomials, and the systemOV(1), . . . ,OV(o)of O multivariate quadratic polynomials is expressed as below when υ variables χ1, . . . , χυand O variables χυ+1, χυ+2, . . . , χυ+odefined on a finite fieldqare given

(ℱOV(1)ℱOV(2)⋮ℱOV())=(vTa11vTa12…vTa??vTa21vTa22…vTa??⋮⋮⋱⋮vTa?1vTa?2…vTa??)(x?+1?⋮x?+?)+B(x?+1x?+2⋮x?+?)=(vT0…00vT…0⋮⋮⋱⋮00…vT)(a11a12…a1?a21a22…a2?⋮⋮⋱⋮a?1a11…a??)(x?+1?⋮x?+?)+B(x?+1x?+2⋮x?+?),?indicates text missing or illegible when filed

in which,

B=(b11b12…b1?b21b22…b2?⋮⋮⋱⋮b?1b?2…b??),MOV=(a11a12…a1?a21a22…a2?⋮⋮⋱⋮a?1a?2…a??),?indicates text missing or illegible when filed

vT=[χ1χ2. . . χυ], T:qn→qn, {tilde over (T)}=T−1, and, when each column vector aijis regarded as an element of one matrix, each column vector aijis selected such that MOVis a structured matrix and element values of bijare selected such that B is also a structured matrix of the same form as MOV.

A computer program that is stored in a storage medium stores the method of generating a public key and a secret key using a key generator.

According to the embodiments of the present invention, an electronic signer further includes the key generator configured to perform the method of generating a public key and a secret key, 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, in which the signature generator calculates a hash messages H(M)=ξ for the message M, calculates a solution of s=(s1, . . . , sn) of(x)=ξ using−1(ξ)=s when ξ=(ξ1, . . . , ξm) is given, and calculates {tilde over (T)}(s)=σ, the signature verifier determines whether P(σ)=H(M) and verifies the electronic signature σ according to a result of the determination, H:{0, 1}*→qm, and H(M)=ξ=(ξ1, . . . , ξm)∈qm.

According to the embodiments of the present invention, a method of generating a public key and a secret key using a key generator includes acquiring a first affine map {tilde over (S)}, a second affine map {tilde over (T)}, and a map:n→qm, 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, in which, when the map:n→qmis expressed as a system=, . . . ,(m)of multivariate quadratic polynomials having m=o1+o2polynomials and n=υ+m variables,(i)for i=1, . . . , o1is expressed as below

{ℱ(1)(?)=ℱV(1)(?)+ℱOV(1)(?)+?⋮ℱ(o1)(?)=?+?(?)+?,?indicates text missing or illegible when filed

in which MV1is a structured matrix or a submatrix of a structured matrix,(i)for i=o1+1, . . . , m is expressed as below

{ℱ(o1+1)(?)=?(?)+?(?)+?⋮?(?)=?(?)+?+?,?indicates text missing or illegible when filed

(ℱV(o1+1)ℱV(o1+2)⋮?)=(x1x2⋯?⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯)·(L1′L2′⋯?)=MV2·(L1′L2′⋯?),?indicates text missing or illegible when filed

According to the embodiments of the present invention, a method of generating a public key and a secret key using a key generator includes acquiring a first affine map ({tilde over (S)}) a second affine map ({tilde over (T)}), and a map (:n→qm), 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, in which the map:n→qmis expressed as a system=, . . . ,(m)of m=o1+o2multivariate quadratic polynomials, a systemOV(1), . . . ,OV(oi)of the O1multivariate quadratic polynomials is expressed as below when υ variables (χ1, . . . , χυ) and O1variables (χυ+1, χυ+2, . . . , χυ+o1) defined on a finite fieldqare given

(ℱOV(1)ℱOV(2)⋮?)=(vTa11vTa12⋯?vTa21vTa22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B1(??⋮?)=(vT0⋯?0vT⋯?⋮⋮⋱⋮??⋯?)(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B1(??⋮?),?indicates text missing or illegible when filed

in which,

MOV,1=(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)andB1=(b11b12⋯?b21b22⋯?⋮⋮⋱⋮??⋯?)?indicates text missing or illegible when filed

are given, vT=[χ1χ2. . . χυ], each column vector aijis selected such that MOV,1is a structured matrix and element values of bijare selected such that B1is also a structure matrix of the same form as MOV,1, when each column vector aijis regarded as an element of one matrix, andOV(i)for i=o1+1, . . . , m is given as below

in which

MOV,2=(a11′a12′⋯?a21′a22′⋯?⋮⋮⋱⋮??⋯?)andB2=(b11′b12′⋯?b21′b22′⋯?⋮⋮⋱⋮??⋯?)?indicates text missing or illegible when filed

are given, v′T=[χ1χ2. . . χυ+o1], each column vector a′ijis regarded as elements of one matrix, each column vector a′ijis selected such that MOV,2is a structured matrix and element values of b′ijare selected such that B2is also a structured matrix of the same form as MOV,2when each column vector a′ijis regarded as an element of one matrix,
S:qm→qm, T:qn→qn, {tilde over (S)}=S−1, {tilde over (T)}=T−1.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

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.

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, χi, 1≤i≤υ).

Whenqis a finite field with q (here, q is a natural number) elements, and υ linear polynomials (L1, . . . , Lυ) and υ variables (χ1, . . . , χυ) defined on the finite field (q) are given, a system (V(1), . . . ,V(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.

The system (V(1), . . . ,V(o)) of quadratic polynomials will be expressed by Equation 1, in which MVis defined as a structured matrix (or a submatrix of a structured matrix).

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(υ2).

1-1. Structured Matrix is Circulant Matrix

When υ linear polynomials (L1, . . . , Lυ) and υ variables (χ1, . . . , χυ) are given to an apparatus or a computer program, a system (V(1), . . . ,V(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 O1and a second layer is represented as O2.

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, MVin Equation 3 is a circulant matrix or a submatrix of a circulant matrix.

(ℱV(1)ℱV(2)⋮?)=(x1x2⋯???⋯?⋯⋯⋯⋯??⋯?)·(L1L2⋯?)=MV·(L1L2⋯?)?indicates text missing or illegible when filed[Equation3]

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

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

(ℱOV(1)ℱOV(2)⋮?)=(vTa11vTa12⋯?vTa21vTa22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B(??⋮?)=(vT0⋯?0vT⋯?⋮⋮⋱⋮??⋯?)(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B(??⋮?)MOV=(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)=(??⋯???⋯???⋯???⋯?⋮⋮⋱⋮⋮⋮⋱⋮??⋯???⋯???⋯???⋯???⋯???⋯?⋮⋮⋱⋮⋮⋮⋱⋮??⋯???⋯?)=(P??S)B=(b11b12⋯?b21b22⋯?⋮⋮⋱⋮??⋯?)=(??⋯???⋯???⋯???⋯?⋮⋮⋱⋮⋮⋮⋱⋮??⋯???⋯???⋯???⋯???⋯???⋯?⋮⋮⋱⋮⋮⋮⋱⋮??⋯???⋯?)?indicates text missing or illegible when filed[Equation4]

Here vT=[χ1χ2. . . χυ], each of P, Q, R, S is a circulant matrix of vectors, MOVis a block circulant matrix of the vectors, and B is also a block circulant matrix with the same structure as MOV.

A system of quadratic equations such as in Equation 5 without quadratic terms that satisfy χiχ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, δiis a constant term selected in the finite field (q).

{ℱ(1)(?)=ℱV(1)(?)+ℱOV(1)(?)+?⋮ℱ(o)(?)=ℱV(o)(?)?+ℱOV(o)(?)+??indicates text missing or illegible when filed[Equation5]

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

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 (OV(i)) of quadratic polynomials for υ variables (χ1, . . . , χυ) and O variables (χυ+1, χυ+2, . . . , χυ+o).

(ℱOV(1)ℱOV(2)⋮?)=(vTa11vTa12⋯?vTa21vTa22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B(??⋮?)=(vT0⋯?0vT⋯?⋮⋮⋱⋮??⋯?)(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B(??⋮?)?indicates text missing or illegible when filed[Equation6]

Here, vT=[χ1χ2. . . χυ], and B and MOVare expressed as shown in Equation 7.

B=(b11b12⋯?b21b22⋯?⋮⋮⋱⋮??⋯?),MOV=(a11a12⋯?a21a22⋯?⋮⋮⋱⋮??⋯?)?indicates text missing or illegible when filed[Equation7]

Here, when each column vector aijis regarded as an element of one matrix, each column vector aijis selected such that MOVis a structured matrix, element values of bijare selected such that B is a structure matrix of the same form as MOV, thereby a system of desired quadratic polynomials is generated.

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(n2). At this time, a size of the coefficient matrix of the system of a linear equation is n×n.

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

MOV=(a11a12⋯a?a21a22⋯a?⋮⋮⋱⋮ao1ao2⋯a?)=(p1p2⋯pkq1q2⋯qkpkp1⋯pk-1qkq1⋯qk-1⋮⋮⋱⋮⋮⋮⋱⋮p2p3⋯p1q2q3⋯q1r1r2⋯rks1s2⋯skrkr1⋯rk-1sks1⋯sk-1⋮⋮⋱⋮⋮⋮⋱⋮r2r3⋯r1s2s3⋯s1)=(PQRS)?indicates text missing or illegible when filed[Equation8]

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

Here, B is a block circulant matrix.

2-2. Method of Efficiently Calculating Inverse Matrix (BC−1) of Given Block Circulant Matrix (BC)

A block determinant (K−PS−QR) of a given block circulant matrix

is obtained. Since all of P, Q, R, S are circulant matrices, K is also a circulant matrix.

First, an inverse matrix (K−1) of K is obtained, and an inverse matrix (BC−1) of BC is obtained by calculating

At this time, efficient algorithms such as the Extended Euclidean Algorithm are used to obtain the inverse matrix of K.

3. Randomization Using Structured Matrix

Embodiments of message randomization or secret key randomization to cope with various types of attacks such as a side-channel attack are as below.(i) generating a first operation result by adding a matrix and a message (or a secret key), and then, subtracting the matrix from the first operation result, or(ii) generate a second operation result by multiplying a matrix and a message (or a secret key), and then, multiplying the second operation result by an inverse matrix of the matrix.

At this time, if the matrix is selected as a structured matrix, calculation efficiency can be increased.

3-1. Randomization Using a Circulant Matrix or a Block Circulant Matrix

Embodiments of message randomization or secret key randomization to cope with various types of attacks such as a side-channel attack are as below.(i) generating a first operation result by adding a matrix and a message (or a secret key), and then, subtracting the matrix from the first operation result, or(ii) generating a second operation result by multiplying a matrix and a message (or a secret key), and then, multiplying the second operation result by an inverse matrix of the matrix.

At this time, if a random matrix is selected as a circulant matrix or a block circulant matrix, the calculation efficiency can be increased.

3-2. Whenqis a finite field with q elements, if a random matrix (R) is selected as a circulant matrix as shown in Equation 10 to randomize a secret key ({tilde over (S)}) in a product ({tilde over (S)}·h) of a vector (h) ofqmand the secret key ({tilde over (S)}), the calculation efficiency can be increased.

Here, {tilde over (S)}=S−1, and H(M) is a hash value for a message M and is expressed as H(M)=ξ=(ξ1, . . . , ξm)∈qm.

The electronic (or digital) signature algorithms based on multivariate quadratic polynomials (or equations) according to the present invention include a key generation algorithm, a signature generation algorithm, and a signature verification algorithm. The electronic signature algorithms based on multivariate quadratic polynomials are executed by an electronic apparatus (or a digital signature apparatus) or a computer program being executed in the electronic apparatus.

A computer program stored in a storage medium has a program code for performing a method for electronic signature algorithms based on a structured matrix (algorithms that protect authentication, non-repudiation, and/or integrity of a message (or data)), and the program code is executed in a computing apparatus.

The computing apparatus refers to a PC (personal computer), a server, or a mobile device, and the mobile device refers to a mobile phone, a smartphone, an Internet mobile device (MID), a laptop computer, or the like, but the present invention is not limited thereto.

FIG. 1is a block diagram of an electronic signer based on multivariate quadratic polynomials with one layer according to embodiments of the present invention, andFIG. 2is a flowchart for describing an operation of the electronic signer based on multivariate quadratic polynomials shown inFIG. 1. An electronic signer100ofFIG. 1constitutes a secret central map having one layer, executes electronic signature algorithms based on multivariate quadratic polynomials using the secret central map, and includes a key generator110, a signature generator120, and a signature verifier130.

In the present specification, the electronic signer100or200may be implemented as a hardware component or a software component. When the electronic signer100or200is implemented as a hardware component, each of the components110,120, and130is implemented as a hardware component, and, when the electronic signer100is implemented as a software component, each of the components110,120, and130is implemented as a software component.

Key Generation Algorithm

The key generator110performs steps (S110to S130) to perform the key generation algorithm for calculating a public key.

For a security parameter (λ), a pair (<PK, SK>=<, (, {tilde over (T)})>) of a public key (PK) and a secret key (SK) is generated as follows. The security parameter (λ) indicates a security level.1. one affine map ({tilde over (T)}) is randomly selected (S110). If the affine map ({tilde over (T)}) is not invertible, a new affine map will be randomly selected again. Here, T:qn→qnand, {tilde over (T)}=T−1. It is assumed that affine maps and a secret central map (=, . . . ,(m)) are securely stored in an apparatus (for example, a data storage apparatus) which can be accessed by the key generator110.2. The secret central map (=, . . . ,(m)) is selected as below (S120).

For application to electronic signature algorithms based on multivariate quadratic polynomials using a structured matrix, a configuration of a new central map according to the present invention requires two index sets (V, O) when there is one (1) layer.:n→qm, and each of n and m is a natural number.

Here, |V|=υ, and |O|=o. V is an index set for defining Vinegar variables, and O is an index set for defining Oil variables.

In the secret central map (=, . . . ,(m)), that is, a system of multivariate quadratic polynomials having m=o equations and n=υ+m variables,(i)for i=1, . . . , o will be defined as shown in Equation 11.

V(i)for i=1, . . . , o will be defined as shown in Equation 12,

(ℱOV(1)ℱOV(2)⋮FOV(o))=(x1x2⋯xvx?x1⋯xv-1⋮⋮⋱⋮x?+2x?+3⋯x?1)·(L1L2⋯L?)+Mv·(L1L2⋯L?)?indicates text missing or illegible when filed[Equation12]

Here, Mvis a circulant matrix or a submatrix of a circulant matrix.

OV(i)for i=1, . . . , o will be defined as shown in Equation 13, and

Here, B is the same as B in Equation 9, and MOVis the same as MOVin Equation 8.

B=(b11b12⋯b1ob21b22⋯b2o⋮⋮⋱⋮bo1bo2⋯boo),MOV=(a11a12⋯a1oa21a22⋯a2o⋮⋮⋱⋮ao1ao2⋯a?),MOV=(a11a12⋯a1oa21a22⋯a2o⋮⋮⋱⋮ao1ao2⋯a?)=(p1p2⋯pkq1q2⋯qkpkp1⋯pk-1qkq1⋯qk-1⋮⋮⋱⋮⋮⋮⋱⋮p2p3⋯p1q2q3⋯q1r1r2⋯rks1s2⋯skrkr1⋯rk-1sks1⋯sk-1⋮⋮⋱⋮⋮⋮⋱⋮r2r3⋯r1s2s3⋯s1)=(PQRS)B=(b11b12⋯b?b21b22⋯b?⋮⋮⋱⋮bo1bo2⋯boo)=(t1t2⋯tku1u2⋯uktkt1⋯tk-1uku1⋯uk-1⋮⋮⋱⋮⋮⋮⋱⋮t2t3⋯t1u2u3⋯u1v1v2⋯vkw1w2⋯wkvkv1⋯vk-1wkw1⋯wk-1⋮⋮⋱⋮⋮⋮⋱⋮v2v3⋯v1w2w3⋯w1)?indicates text missing or illegible when filed

A constant term (δi) is randomly selected in the finite field (q).3. A public key (=∘T) is calculated (S130). Here, a circle means a composition, the public key (=∘T) is required for signature verification, and a secret key (SK=(, {tilde over (T)}) is required for signature generation.

Signature Generation Algorithm

A signature generator120performs steps (S140to S160) to perform the signature generation algorithm, that is, how to invert a new central map according to the present invention.

The signature generator120receives an affine map {tilde over (T)}, a secret central map, and a message M. The message M refers to a message to be transmitted via a communication medium (for example, wired or wireless) as plain text.1. A hash message (H(M)=ξ) for the message M is calculated (S140). Here,
H:{0, 1}*→qmis a collision resistant hash function.
H(M)=ξ=(ξ1, . . . , ξm)∈qmis calculated.2. When ο=(ξ1, . . . , ξm) is given, processes of finding−1(ξ)=s, that is, a solution s=(s1, . . . , sn) of(x)=ξ are as below (S150).

If the vector (sv) is plugged intoOV(i)for i=1, . . . , m to obtain a system of O linear equations having O variables (χυ+1, . . . , χn), a form of the coefficient matrix is a block circulant matrix (BC).

Here, the block circulant matrix (BC) is a matrix obtained by multiplying a matrix that is obtained by plugging the vector (sv) into a matrix composed of vTin Equation 13 by MOV.

A solution (sυ+1, . . . , sn), is obtained by multiplying the inverse matrix (BC−1) obtained by the method defined in 2-2 described above by a transpose of (ξ1−c1−δ1, . . . , ξo−co−δo). Accordingly, a vector s=(s1, . . . , sn) is a solution of(x)=ξ.

If there is no inverse matrix BC−1of the block circulant matrix BC, the procedure returns to a beginning of the signature generation algorithm to select a vector of new random values sv′=(s′1, . . . , s′υ) and performs the methods (or processes) described above again.3. {tilde over (T)}(s)=σ is calculated (S160). σ refers to a signature of the message M (here, the signature means a digital signature or an electronic signature).

Signature Verification or Verification Algorithm

The signature verifier130performs a step (S170) to perform a signature verification or verification algorithm. If the signature verifier130receives one of the public keyand a certificate including the public key, the message M, and the signature σ from the signature generator120, that is, if the public keyand the signature σ for the message M are given, the signature verifier130checks whether P(σ)=H(M). If P(σ)=H(M), the signature σ is accepted, and otherwise, the signature σ is rejected.

FIG. 3is a block diagram of an electronic signer based on multivariate quadratic polynomials with two layers according to embodiments of the present invention.FIG. 4is a flowchart for describing an operation of the electronic signer based on multivariate quadratic polynomials shown inFIG. 3. The electronic signer200ofFIG. 3constitutes and processes a secret central map with two layers.

The key generator210performs step (S210) to perform the key generation algorithm for calculating a secret key and a public key.

Key Generation Algorithm:

For the security parameter (λ), a pair (<PK, SK>=<, ({tilde over (S)},, {tilde over (T)})>) of a public key (PK) and a secret (SK) is generated as follows. The security parameter (λ) represents a security level.1. Two affine maps {tilde over (S)} and {tilde over (T)} are randomly selected (S210). If {tilde over (S)} and {tilde over (T)} are not invertible, two (new) affine maps {tilde over (S)} and {tilde over (T)} are randomly selected again. Here, S:qm→qmand {tilde over (S)}=S−1, and T:qn→qnand, {tilde over (T)}=T−1. Affine maps including the affine maps {tilde over (S)} and {tilde over (T)} and the secret central map (=, . . . ,(m)can be securely stored in an apparatus which can be accessed by the key generator210.2. The secret central map=, . . . ,(m)is selected as below (S220).

For application to electronic signature algorithms based on multivariate quadratic polynomials using a structured matrix, a configuration of a new central map according to the present invention requires two index sets (V, O1, and O2) when there are two layers.

Here, |V|=υ, and |Oi|=oifor i=1, 2. V is an index set for defining Vinegar variables, and O1and O2are index sets for defining Oil variables.

In the secret central map=, . . . ,(m), that is, a system of quadratic polynomials having m=o1+o2(here, each of O1and O2and is a natural number) polynomials and n=υ+m variables,(i)for i=1, . . . , o1will be defined as shown in Equation 14.

Here,V(i)is defined as shown in Equation 2 andOV(i)is defined as shown in Equation 4. At this time, when O is replaced with O1(o1=2k, here, k1is a natural number) as in 1-2 described above, Equation 3 becomes Equation 15, Equation 6 becomes Equation 16, and Equations 8 and 9 become Equation 17.

Here, MOV,1is a block circulant matrix whose elements are column vectors aijeach having a size υ, and B1is a block circulant matrix.

The block circulant matrix MOV,1of the vectors and the block circulant matrix B1are as shown in Equation 17.

At last, a constant term δiis randomly selected in the finite fieldq.(i)for i=o1+1, . . . , m will be defined as shown in Equation 18.

Here,V(i)is defined as shown in Equation 2. At this time, if Liof 1-1 described above is replaced with L′iand υ is replaced with υ+o1,V(i)is as shown in Equation 19.

OV(i)is defined as shown in Equation 4. At this time, if υ described in 1-2 is replaced with υ+o1and O is replaced with O2(o2=2k2, here, k2is a natural number), Equation 3 becomes Equation 20, Equation 6 becomes Equation 21, and Equations 8 and 9 become Equation 22.

[Equation20](??⋯?)=(x1x2⋯??x1⋯?⋯⋯⋯⋯??⋯?)·(L1′L2′⋯?)=MV2·(L1′L2′⋯?)?indicates text missing or illegible when filed

Here, MV2is a circulant matrix or a submatrix of a circulant matrix, andOV(i)for i=o1+1, . . . , o1+o2will be defined as shown in Equation 21.

(ℱOV(o1+1)ℱOV(o1+2)⋮ℱOV(o1+o2))=(v′Ta′11v′Ta′12⋯?v′Ta′21v′Ta′22⋯?⋮⋮⋱⋮??⋯?)(??⋮?)+B2(??⋮?)=(v′T0⋯00v′T⋯0⋮⋮⋱⋮00⋯v′T)(a11′a12′⋯?a21′a22′⋯?⋮⋮⋱⋮?a11′⋯?)(??⋮?)+B2(??⋮?)?indicates text missing or illegible when filed[Equation21]

Here, MOV,2is a block circulant matrix whose elements are column vectors a′ijeach having a size υ, and B2is a block circulant matrix.

The block circulant matrix MOV,2of vectors and the block circulant matrix B2are as shown in Equation 22.

Here, p′i, q′i, s′i, r′iare column vectors each having the size υ, each of P2, Q2, R2, S2is a circulant matrix of vectors, and MOV,2is a block circulant matrix of vectors.

At last, a constant term δiis randomly selected in the finite fieldq.3. A public key=S∘∘T is calculated (S230).

Signature Generation Algorithm

The signature generator220performs steps (S240to S260) to perform the signature generation algorithm, that is, how to invert a new central map according to the present invention. The signature generator220receives the affine maps {tilde over (S)} and {tilde over (T)}, the secret central map, and the message M.1. A hash message H(M) for the message M is calculated (S240).

In a first layer,

The vector (sv) is plugged into the first layerV(i)for i=1, . . . , o1to calculate a product of a o1×υ submatrix of a υ×υ circulant matrix and the transpose of a vector (L1(sυ), . . . , Lυ(sυ)), and, as a result, (c1, . . . , co1) is obtained. At this time, the o1×υ submatrix into which the vector svis plugged is MV1.

The vector svis plugged intoOV(i)for i=1, . . . , o1to obtain a system of linear equations of O1equations having O1variables. At this time, a coefficient matrix of the system of linear equations is a block circulant matrix BC1.

Here, the block circulant matrix BC1is a matrix obtained by multiplying a matrix that is obtained by plugging the vector svinto a matrix composed of vTin Equation 13 by MOV,1.

A solution sυ+1, . . . , sυ+o1is obtained by multiplying the transpose of (ξ1−c1−δ1, . . . , ξo1−co1−δo1) by the inverse matrix BC1−1obtained by the method defined in 2-2 described above.

In a second layer,

a vector sυ+o1=(s1, . . . , sυ+o1) is plugged into the second layerV(i)for i=o1+1, . . . , m to calculate a product of a o2×(υ+o1) submatrix of a (υ+o1)×(υ+o1) circulant matrix and a transpose of a vector (L′1(sυ+o1), . . . , L′υ+o1(sυ+o1)), and, as a result (co11, . . . , cm), is obtained.

At this time, the o2×(υ+o1) submatrix into which the vector (sυ+o1) is plugged is MV2.

The vector (sυ+o1) is plugged intoOV(i)for i=o1+1, . . . , m to obtain a system of linear equations of o2equations having o2variables. At this time, a coefficient matrix of the system of linear equations is a block circulant matrix BC2.

Here, the block circulant matrix BC2is a matrix obtained by multiplying a matrix that is obtained by plugging the vector Sυ+o1into a matrix composed of vTin Equation 21 by MOV,2.

A solution (sυ+o1+1, . . . , sυ+m) is obtained by multiplying the transpose of (ξo1+1−co1+1−δo1+1, . . . , ξm−cm−δm) by the inverse matrix BC2−1obtained by the method defined in 2-2 described above. Then, a vector s=(s1, . . . , sn) is a solution of(x)=ξ.

If there is no inverse matrix BC1−1of the block circulant matrix BC1or there is no inverse matrix BC2−1of the block circulant matrix BC2, the procedure returns to a beginning of the electronic signature algorithm to select a vector sv′=(s′1, . . . , s′υ) of new random values, and performs the methods (or processes) described above again.4. {tilde over (T)}(s)=σ is calculated (S260). σ refers to a signature of the message M (here, the signature is a digital signature or an electronic signature).

Signature Verification or Verification Step:

If the signature verifier230receives the message M, the signature σ, and the public key, that is, if the public keyand the signature σ for the message M are given, the signature verifier230checks whether P(σ)=H(M) (S270). If P(σ)=H(M), the signature σ is accepted, and otherwise, the signature σ is rejected.

A method, an apparatus (or a device), or a computer program for performing an electronic signature algorithm based on multivariate quadratic polynomials according to the embodiment of the present invention can greatly reduce a length of a secret key by using structured matrices, and generate signatures quickly by increasing calculation efficiency.

Although the present invention has been described with reference to the embodiment shown in the drawings, this is merely exemplary, and it will be understood by those skilled in the art that various modifications and equivalent other embodiments thereof can be made. Therefore, a true technical protection scope of the present invention will be defined by a technical spirit of the appended claims.