KR101753721B1 - High speed multivariate quadratic digital signature scheme and system thereof - Google Patents

Abstract

According to the digital signature method according to the embodiments of the present invention, the key generation apparatus includes a step of generating a center mapping including multivariate quadratic polynomials defined at a finite position, and the key generation apparatus having a first reversible mapping, Generating a second reversible event and a history of the second reversible event in the history of reversible events; transmitting the secret key to the digital signature device by the key generation device; And generating the digital signature using the secret key, wherein the center mapping includes the quadratic polynomials with the coefficients of the most quadratic terms being zero.

Description

TECHNICAL FIELD [0001] The present invention relates to a high-speed multivariate secondary signature method,

Embodiments of the present invention relate to a multivariate quadratic signature method and system, and more particularly to a fast multivariate quadratic signature method and system that supports high speed.

A multivariate quadratic signature is a digital signature used in a multivariate cryptography system. Here, a multivariable cryptosystem refers to an asymmetric cryptosystem based on multivariate polynomials defined on a finite field.

In particular, when the degree of the multivariate polynomial used in the multivariable cryptosystem is 2, the multivariable cryptosystem is called a multivariate secondary cryptosystem.

U.S. Registration Bulletin US 8,811,608 B2 (2014. 08. 19.) US Registration No. 7,158,636 B2 (2007. 01. 02.)

SUMMARY OF THE INVENTION It is an object of the present invention to provide a high-speed multivariate secondary signature method and a system thereof that support a high speed.

)를 생성하는 단계를 포함하고, 상기 중심 사상(F)은 각각이 o_t 개(t=1,...,L)의 이차 다항식들을 포함하는 L 개(L≥2 인 자연수)의 레이어들을 포함하고,

및 v+m=n이고, 상기 레이어들 중 첫 번째 레이어는 수식, The digital signature method according to the embodiments of the present invention is characterized in that the key generation apparatus is a digital signature method in which m (n is a natural number equal to or greater than 3) variables defined in the finite field (K _q , q is a natural number of 2 or more) ) Multivariate quadratic polynomials (F ⁽ⁱ⁾ : K _q ⁿ → K _q ^m (S = K _q ^m ? K _q ^m ) and a second reversible mapping (S = K _q ^m ? K _q ^m ) spirit ^{_{(T: K q n → K}} q n) the generating step and the key generation apparatus is the first synthesis of a reversible mapping (S), the central idea (F), and said second reversible mapping (T) (public key)

) For a step of generating, and the central idea (F) are each o _t (L > = 2) layers including quadratic polynomials of t (t = 1, ..., L)

And v + m = n, and the first one of the layers is an equation,

)(here,

)

)을 포함하고, 상기 레이어들 중에서 마지막 레이어는 아래의 수식,Polynomials defined according to (

), And the last layer among the layers includes the following equation,

,

및

)(

,

And

)

)을 포함한다.Polynomials defined according to (

).

A digital signature method according to embodiments of the present invention is a digital signature method in which a digital signature apparatus encrypts a secret key SK = (S ^{- 1} ) including a center map F, a first map S ^-1 and a second map T ^-1 , ¹ , F, T ^- receiving a ^1), (by applying the hash function to M) hashed message (h (M) the message is the digital signature device, given that the secret key; and the digital signature apparatus for generating a) (SK ) To generate a digital signature (?) For the hash message (h (M)),

및 v+m=n이고, 상기 레이어들 중 첫 번째 레이어는 수식, The center mapping F includes m-variable (n is a natural number of 2 or more) quadratic polynomials of m (m is a natural number of 3 or more) defined on a finite field (K _Q , q is a natural number of 2 or more) (F ⁽ⁱ⁾ : K _q ⁿ ? K _q ^m including (i = 1, 2, ... , m)), and the central idea (F) are each a _t o (L > = 2) layers including quadratic polynomials of t (t = 1, ..., L)

And v + m = n, and the first one of the layers is an equation,

)(here,

)

)을 포함하고, 상기 레이어들 중 마지막 레이어는 수식,Polynomials defined according to (

), And the last one of the layers includes a formula,

,

및

)(

,

And

)

)을 포함한다.Polynomials defined according to (

).

)를 생성하고, 상기 중심 사상(F)은 각각이 o_t개(t=1,...,L)의 이차 다항식들을 포함하는 L 개(L≥2 인 자연수)의 레이어들을 포함하고,

및 v+m=n이고, 상기 레이어들 중 첫 번째 레이어는 수식, In the encryption apparatus including a key generation apparatus according to embodiments of the present invention, the key generation apparatus, finite field (K _q, q is a natural number more than 2); m defined above, (m is a natural number more than 3) n - variable (n is a natural number greater than 2) multivariate quadratic polynomials (F ⁽ⁱ⁾ : K _q ⁿ → K _q ^m (S: K _q ^m ? K _q ^m ) and a second reversible mapping (? i = 1, 2, ..., m) T: by K _q ⁿ → K _q ⁿ⁾ to generate, and the key generation apparatus the composite (composition of the first reversible mapping (S), the central idea (F), and said second reversible mapping (T)) Public key (

, And the center mapping F includes L layers (natural numbers of L? 2) each including quadratic polynomials of o _t (t = 1, ..., L)

And v + m = n, and the first one of the layers is an equation,

)(here,

)

)을 포함하고, 상기 레이어들 중에서 마지막 레이어는 아래의 수식,Polynomials defined according to (

), And the last layer among the layers includes the following equation,

,

및

)(

,

And

)

)을 포함한다.Polynomials defined according to (

).

A program for storing instructions for performing the digital signature method according to embodiments of the present invention may be stored in a computer-readable storage medium.

According to the embodiments of the present invention, the key size of the secret key used in the multivariate secondary digital signature is reduced.

According to embodiments of the present invention, since the key size of the public key and secret key used for the multivariate secondary digital signature is reduced, the amount of computation required for the digital signature is reduced, .

Figure 1 conceptually illustrates a multivariate secondary digital signature system in accordance with embodiments of the present invention.
Figure 2 conceptually illustrates a multivariate secondary digital signature scheme in accordance with embodiments of the present invention.
Figure 3 conceptually illustrates a matrix associated with a quadratic part of first secret polynomials and second secret polynomials according to embodiments of the present invention.
4 is a flowchart illustrating a method for a signature device to calculate a signature value through calculation of a second result value, in accordance with embodiments of the present invention.

Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

The quadratic polynomial described herein refers to an equation consisting of variables and the linear term of the variables, the quadratic terms of the variables and the linear combination (or primary combination) of the variables.

In this specification, a field is an algebraic structure, which means a set closed with respect to arithmetic operation and having an identity for each arithmetic operation.

In this specification, a polynomial is defined on a finite field, which means that the coefficients of the polynomial are included in the finite field. That is, unless otherwise stated herein, the polynomial (F) defined above on finite field K,

는 모든 인덱스들에 대하여 상기 유한체 K의 원소임을 가정한다.Each coefficient of

Is an element of the finite field K for all indices.

In this specification, for the field F, F ^* means a field containing only elements having an inverse to the multiplication among the elements included in the field F. In this specification, when a certain polynomial is defined on a finite body (on), it means that the coefficient of the polynomial is included in the finite field.

In this specification, f: X → Y means a map or function in which f corresponds to the elements of domain (X) with elements of conjugate (Y).

In the present specification, x (mod y) means a residue obtained by dividing x by y.

Figure 1 conceptually illustrates a multivariate secondary digital signature system (or electronic signature system) in accordance with embodiments of the present invention. 1, the digital signature system 10 may include a key generation device 100, a digital signature generation device (or signature generation device) 200, and a verification device 300.

The key generation apparatus 100 may include a processor 110, a memory 120, and a transmission / reception interface 130.

The processor 110 may control the operation of the key generating apparatus 100. [ The memory 120 may store a program (e.g., a key generating program) necessary for operation of the key generating apparatus 100. [ For example, the processor 110 may execute the key generation program stored in the memory 120 and control the operation of the key generation apparatus 100 based on the control of the instructions included in the key generation program.

The key generation apparatus 100 generates a public key PK and a secret key SK used in the digital signature system 10 under the control of the processor 110 and generates a public key PK and a secret key SK) may be stored in the memory 120. The public key PK may be a signature verification key, and the secret key SK may be a signature key corresponding to the public key PK.

According to embodiments, the key generation apparatus 100 may receive a security level (?) And generate a public key (PK) and a secret key (SK) based on the input non-degree (?). The ratio λ is a parameter for determining the security of the digital signature system 10 and means a value for determining the size (or the number of bits) of the public key PK and / or the secret key SK.

The processor 110 of the key generation apparatus 100 may transmit the public key PK to the signature apparatus 200 and / or the verification apparatus 300 using the transmission / reception interface 130. [

The processor 110 of the key generation apparatus 100 may transmit the secret key SK to the signature apparatus 200 using the transmission / reception interface 130. [

Signature device 200 may include a processor 210, a memory 220, and a transceiver interface 230. In accordance with embodiments, the signing device 200 may be, but is not limited to, a computer, a mobile communication terminal (e.g., a smart phone), and a payment terminal.

The processor 210 may control the operation of the signature device 100. The memory 220 may store a program (e.g., a digital signature program) necessary for operation of the signing device 200. [ For example, the processor 210 may execute the digital signature program stored in the memory 220 and may control the operation of the signature device 200 based on control of the instructions contained in the digital signature program.

The signature device 200 can receive the public key PK and / or the secret key SK transmitted from the key generation device 100 via the transmission / reception interface 230. [ According to embodiments, the signing device 200 may send the public key PK to the verification device 300 via the send / receive interface 230.

Signature device 200 may apply a given message M to a hash function to produce a hash message h (M). The message M may be generated by the signature device 200, but may also be input from outside the signature device 200.

The hash function is a function for mapping data of an arbitrary length to data of a fixed length.

The signature device 200 generates a digital signature τ using the hash message h (M) using the secret key SK and sends the hash message h (M) and the digital signature τ to the memory 220 ). ≪ / RTI >

The processor 210 of the signature device 200 may send the hash message h (M) and the digital signature? To the verification device 300. Although the key generating apparatus 100 and the signing apparatus 200 are shown as separate apparatuses in FIG. 1, according to the embodiments, the key generating apparatus 100 and the signing apparatus 200 are integrated into one encryption apparatus Can be implemented.

For example, the one encryption device may be a device capable of performing both the functions of the key generation device 100 and the signature device 200. For example, the encryption apparatus generates a secret key (SK) and a public key (PK), transmits the public key PK to the verification apparatus 300, generates a digital signature τ, M) and a digital signature ([tau]) to the verification device 300. [

The verification apparatus 300 may include a processor 310, a memory 320, and a transmission / reception interface 330. [

The processor 310 may control the operation of the verification device 300. The memory 320 may store a program (e.g., a signature verification program) necessary for the operation of the verification apparatus 300. For example, the processor 310 may execute a signature verification program stored in the memory 320 and may control the operation of the verification device 300 based on the control of the instructions contained in the signature verification program.

The memory 320 of the signing device 300 may receive and store a public key PK used in the digital signature system 10. [ According to embodiments, the public key PK may be, but is not limited to, the public key PK transmitted from the key generation apparatus 100 via the transmission / reception interface 330. [ For example, the public key PK may be downloaded from a web server or moved through a particular storage medium.

The verification apparatus 300 receives the hash message h (M) and the digital signature? From the signature apparatus 200 using the transmission / reception interface 330 and outputs the hash message h (M) can be stored in the memory 320. [

The processor 310 of the verification apparatus 300 compares the hash message h (M) with the value (PK (?) Applied to the public key PK with the digital signature? (H (M)) is correctly transmitted from the signature apparatus 200 when the hash message h (M) is identical to the hash message h (M).

FIG. 2 conceptually illustrates a multivariate secondary digital signature method (hereinafter digital (or electronic) signature method) according to embodiments of the present invention.

Referring to FIG. 2, the key generation apparatus 100 includes a finite field K _q The m n-variable quadratic polynomials (F ⁽ⁱ⁾ : K _q ⁿ ? K _q ^m generate (i = 1, 2, ... , m)) , and, m of the n- variable quadratic polynomial (F ^(i): K → K _q ⁿ _q ^m F ⁽¹⁾ , ..., F ^(m) including the central map (i = 1, 2, ..., m). Here, q may be a natural number of 2 or more, n may be a natural number of 2 or more, and m may be natural number of 3 or more.

m n-variable quadratic polynomials (F ⁽ⁱ⁾ : K _q ⁿ ? K _q ^m (i = 1, 2, ..., m) may include L (a natural number L 2) layers S (1) to S (L). Each of the layers S (1) to S (L) may include a plurality of secondary polynomials.

을 만족하도록 선택된다. The tth (1? t? L) layer S (t) may include o _t secondary polynomials. In this case, o ₁ , o ₂ , ..., o _t

Is satisfied.

,

,

이다.Also, in the equations described in this specification, v is a natural number of n or less and satisfies n = v + m. Also,

,

,

to be.

)을 포함하는 첫 번째 레이어(S(1))를 생성할 수 있다.The key generation apparatus 100 generates polynomials defined by Equation (1)

) ≪ / RTI > (S (1)).

 [Equation 1]

)(here,

)

)을 포함하는 첫 번째 레이어(S(1))를 생성할 수 있다.According to embodiments, the key generation apparatus 100 may generate polynomials (< RTI ID = 0.0 >

) ≪ / RTI > (S (1)).

 &Quot; (2) "

이고

)(here,

ego

)

와 수학식 2의

은

의 각각의 이차항들로 이루어진 행렬의 랭크가 v가 되도록 임의적으로 선택될 수 있다. According to the embodiments,

And Equation 2

silver

May be arbitrarily selected so that the rank of the matrix consisting of the respective quadratic terms of v is v.

)을 포함하는 L 번째(즉, 마지막) 레이어(S(L))를 생성할 수 있다.The key generation apparatus 100 generates polynomials (

(I.e., the last) layer S (L) including the Lth (i.e.

&Quot; (3) "

)을 포함하는 L 번째(즉, 마지막) 레이어(S(L))를 생성할 수 있다.According to embodiments, the key generation apparatus 100 may include polynomials (e.g.,

(I.e., the last) layer S (L) including the Lth (i.e.

&Quot; (4) "

이고

)

(here,

ego

)

와

는

의 각각의 이차항들로 이루어진 행렬들 각각의 랭크가 풀(full)이 되도록 임의적으로 선택될 수 있다.According to the embodiments,

Wow

The

May be arbitrarily selected so that the rank of each of the matrices of the respective quadratic terms of the matrix is full.

는

의 각각의 이차항들로 이루어진 행렬들 각각의 랭크가 풀(full)이 되도록 임의적으로 선택될 수 있다.According to the embodiments,

The

May be arbitrarily selected so that the rank of each of the matrices of the respective quadratic terms of the matrix is full.

When L> 2, the key generation apparatus 100 generates the t-th layer S (t) (1 (t)) in the same manner as the first layer S (1) or the last layer S < t < L).

That is, at least one remaining layer S (2) excluding the first layer S (1) and the last layer S (L) among the L layers S (1) to S (L) The form of the polynomials included in the last layer S (L-1) is the same as the form of the polynomials included in the first layer S (1) Shape.

)을 포함하는 t 번째 비밀 다항식 레이어(S(t))를 생성할 수 있다.For example, the key generation apparatus 100 may generate the polynomials defined by Equation (5) or Equation (6)

Th secret polynomial layer S (t) including the t-th secret polynomial layer S (t).

&Quot; (5) &quot;

)(here,

)

&Quot; (6) &quot;

은

의 각각의 이차항들로 이루어진 행렬의 랭크가 v_t가 되도록 임의적으로 선택될 수 있다.According to the embodiments,

silver

May be arbitrarily selected so that the rank of the matrix consisting of each quadratic term of v is _t .

,

는

의 각각의 이차항들로 이루어진 행렬들 각각의 랭크가 풀(full)이 되도록 임의적으로 선택될 수 있다.In Equation (4)

,

The

May be arbitrarily selected so that the rank of each of the matrices of the respective quadratic terms of the matrix is full.

FIG. 3 conceptually shows a matrix related to a quadratic part of a polynomial included in layers according to embodiments of the present invention. As shown in FIG. 3, the coefficients of the quadratic terms included in a certain quadratic polynomial can be expressed as a matrix.

For the sake of explanation, FIG. 3 assumes a case where L = 2, that is, a case where the center mapping F includes the first layer S (1) and the second layer (S (2) Respectively.

)에 포함된 이차항들(

)의 계수들을 대칭 행렬로 나타낸 것이고, 제2행렬들(MX2)은 수학식 3에 따라 정의된 다항식들(

Referring to FIG. 3, the first matrices MX1 are polynomials defined according to Equation (2)

) Contained in the second term (

), And the second matrixes MX2 are the polynomials defined in accordance with Equation (3)

)의 계수들을 대칭 행렬로 나타낸 행렬이다.) Of the second term (

) As a symmetric matrix.

In FIG. 3, an empty part means that the coefficient of the corresponding quadratic term is 0 (that is, the corresponding quadratic term does not exist), and the portion denoted by a dot in FIG. 3 indicates that the coefficient of the corresponding quadratic term is not 0 That is, a corresponding second term exists).

)이 수학식 1에 따라 정의되고, 다항식들(

)이 수학식 3에 따라 정의될 때, 제1행렬들 (MX1)과 제2행렬들(MX2)의 대부분의 성분은 0이 되고, 제1행렬들(MX)의 랭크는 v+2이며, 제2행렬들(MX)의 랭크는 풀-랭크이다. 다만, 여기서, 다항식들 (

)에는 특정 이차항 (

)이 존재하지 않는다.As shown in FIG. 3, the polynomials (

) Is defined according to Equation (1), and the polynomials

) Is defined according to Equation (3), most components of the first matrices MX1 and the second matrices MX2 become zero, the rank of the first matrices MX is v + 2, The rank of the second matrixes MX is a full-rank. However, here, the polynomials (

) Has a specific secondary term (

) Does not exist.

The key generation apparatus 100 may generate a random first reversible mapping S = K _q ^m ? K _q ^m and an arbitrary second reversible mapping T = K _q ⁿ ? K _q ⁿ (S1020). An invertible map means an inverse map. According to embodiments, the first reversible mapping S and the second reversible mapping T may be an affine transformation map or a linear map. The key generation apparatus 100 stores the first reversible event S, the center event F and the second reversible event T in the memory 120 as a secret key SK = (S, F, T) .

According to the embodiments, the key generation apparatus 100 can generate the first reversible mapping S, the center mapping F, and the second reversible mapping T based on the input non-degree?.

)를 생성할 수 있다(S1030).The key generation apparatus 100 synthesizes a first reversible event S, a center event F and a second reversible event T to generate a public key K

(S1030).

)는 랜덤한 사상과 실질적으로 동일하고, 따라서 공개키는 역변환하기 어렵다. 즉, 공개키(

)는 일방향 함수(one way function)일 수 있다.Since the first reversible mapping S and the second reversible mapping T are arbitrarily generated,

) Is substantially the same as a random event, and thus the public key is difficult to invert. That is,

) May be a one way function.

The key generation device may store the generated public key (PK) in the memory 120.

According to the embodiments, the key generation apparatus 100 generates a public key PK and generates a public key PK in the history S ^-1 of the first reversible event S and the history T ^-1 of the second reversible event T, a calculation and a first reversible mapping (S) in the history (S ^-1), central idea (F), and a second reversible mapping (T) in the history (T ^-1) the secret key (SK = a (S ^-1 , F, T- ¹ ).

)을 포함하므로, 디지털 서명 시스템(10)에서 사용되는 비밀키(SK)(또는 공개키(PK))의 크기가 감소하는 효과가 있다. The polynomials included in the center mapping (F) are quadrants with a plurality of coefficients of 0

, There is an effect that the size of the private key SK (or the public key PK) used in the digital signature system 10 is reduced.

)를 서명 장치(200)로 전송할 수 있다(S1040).The key generation apparatus 100 generates a secret key (SK = (S ^-1 , F, T ^-1 )) and /

) To the signature device 200 (S1040).

Signing device 200 may receive a secret key (SK) and / or a public key (PK).

The signature device 200 may generate a digital signature τ corresponding to the hash message h (M) using the secret key SK.

The signature device 200 may generate a hash message h (M), which is a function value of a hash function h having an input value of a given message M (S1050).

로 표시한다.The signature device 200 obtains the first result value S ^-1 (h (M)) of the history S ^-1 of the first reversible event S having the hash message h (M) as an input value (S1060). Hereinafter, for convenience, the first result value (S ^-1 (h (M)))

.

를 만족하는

을 계산할 수 있다. 상기 연립방정식

는 m 개의 방정식들을 포함할 수 있다.Signature device 200 includes a first result value (S ^-1 (h (M))), the second result value (F ^-1 (S ^-1 (h (M) of the central idea (F) of input values) ) (S1070). That is, the signing device 200 is a combination of the simultaneous equations

Satisfy

Can be calculated. The simultaneous equations

May include m equations.

If the center mapping F is m n-variable quadratic polynomials F ⁽ⁱ⁾ : K _q ⁿ ? K _q ^m (i = 1, 2, ..., m)), it may require a large amount of computation to obtain the inverse transformation of the center mapping F. That is, in order to obtain the second result value F ^-1 (S ^-1 (h (M))), a large amount of calculation is required, and thus it may take a considerable amount of time.

)을 포함하므로, 서명 장치(200)는 상대적으로 적은 계산을 통해 제2결과 값(F^-1(S^-1(M)))을 구할 수 있다. 이는 이하 도 4를 참조하여 상세히 설명한다.However, as described above, the polynomials included in the center mapping (F) are the quadrants having a plurality of coefficients of 0

), The signature device 200 can obtain the second result value F ^-1 (S ^-1 (M)) through a relatively small calculation. This will be described in detail below with reference to FIG.

과 동일하므로, 제3결과 값(T^-1(F^-1(S^-1(h(M)))))이 해시 메시지(h(M))의 디지털 서명(τ)이 된다.The signature device 200 outputs the third result value T ^-1 of the history of the second reversible mapping T in which the second result value F ^-1 (S ^-1 (h (M))) (T ^-1 (F ^-1 (S ^-1 (h (M)))) (S1080). The third resultant value T ^-1 (F ^-1 (S ^-1 (h (M)))))

, The third resultant value T ^-1 (F ^-1 (S ^-1 (h (M)))) becomes the digital signature τ of the hash message h (M).

The signature apparatus 200 generates the third result value T ^-1 (F ^-1 (S ^-1 (h (M)))) as a digital signature τ corresponding to the hash message h (M) , And store the generated digital signature (tau) in the memory 220.

The signature device 200 may transmit the digital signature τ corresponding to the hash message h (M) and the hash message h (M) to the verification device 300 using the transmission / reception interface 230 S1090).

The verification apparatus 300 can receive the hash message h (M) and the digital signature? Sent from the signature apparatus 200. [

The verification apparatus 300 can verify whether the hash message h (M) transmitted using the digital signature τ and the public key PK has been transmitted from the true signature apparatus 200. The public key PK may be transmitted from the key generation device 100 and / or the signature device 200.

)를 이용하여, 디지털 서명(τ)을 공개키(PK)를 적용한 값(

)을 계산할 수 있다.According to embodiments, verification device 300 may include a public key (e.g.,

), A value obtained by applying the public key PK to the digital signature?

) Can be calculated.

)과 해시 메시지(h(M))를 비교하고, 공개키(PK)를 적용한 값(

)과 해시 메시지(h(M))가 일치할 때, 전송된 해시 메시지(h(M))가 진정한 서명 장치(200)로부터 올바르게 전송된 것으로 판단(또는 검증)할 수 있다(S1100). 이 경우, 검증 장치(300)는 해시 메시지(h(M)) 또는 디지털 서명(τ)을 수락(accept)할 수 있다.The verification device 300 may be a digital signature (&quot;

) And a hash message h (M), compares the hash value h (M) with a value obtained by applying the public key PK

(Or verify) the transmitted hash message h (M) from the true signature device 200 when the hash message h (M) matches the hash message h (M). In this case, the verification apparatus 300 may accept a hash message h (M) or a digital signature?.

)과 해시 메시지(h(M))를 비교하고, 공개키(PK)가 적용된 디지털 서명(

)과 해시 메시지(h(M))가 일치하지 않을 때, 전송된 해시 메시지(h(M))가 진정한 서명 장치(200)로부터 전송되지 않은 것으로 판단하고, 해시 메시지(h(M))를 거부(reject)할 수 있다. The verification device 300 determines whether the value (

) And the hash message h (M), and compares the digital signature (PK) applied with the public key PK

Judges that the transmitted hash message h (M) has not been transmitted from the true signature apparatus 200 when the hash message h (M) is not identical to the hash message h (M) It can be rejected.

4 is a flow chart illustrating a method by which a signature device computes a second result value, in accordance with embodiments of the present invention. For the sake of explanation, FIG. 4 assumes a case where L = 2, that is, the case where the center mapping F includes the first layer S (1) and the second (= last) layer S (2) Respectively.

)를 생성할 수 있다(S1071).The signature device 200 can be any test variable

(S1071).

)를 연립방정식

에 포함된 방정식들 중, 첫 번째 레이어(S(1))에 포함된 다항식들(

)에 대한 방정식에 적용(또는 대입(plug))하여 제1근들(

)을 계산(또는 도출)할 수 있다(S1073).The signature device 200 is a test variable

) To the simultaneous equations

Among the equations included in the first layer S (1), the polynomials included in the first layer S (1)

(Or plugged) into an equation for the first muscle

) (Step S1073).

)이 수학식 2에 따라 정의된 경우, 서명 장치(200)는 수학식 7에 나타난 바와 같이, o₁ 개의 변수들에 대한 o₁ 개의 이차 방정식들을 생성할 수 있다. According to embodiments, polynomials included in the first layer S (1)

) In this case defined according to equation 2, the signature device 200 may generate, o ₁ o ₁ two quadratic equations for the variables, as shown in Equation (7).

 &Quot; (7) &quot;

Equation (7) can be transformed into Equation (8).

&Quot; (8) &quot;

)(here

)

)을 계산할 수 있다.Since the o1 quadratic equations for the o1 variables shown in Equation (8) are relatively easy to solve than the general case, the signature apparatus 200 can calculate the o1 quadratic equations of Equation (7) or (8) Solve the equations, and o1 The first roots of the two quadratic equations (

) Can be calculated.

들을 이용하여

를 계산하고, 서명 장치(200)로 를 전송할 수 있다. 이후, 서명 장치(200)는 전송된

만을 이용하여 제1근들(

)을 계산할 수 있다.According to the embodiments, the key generation apparatus 100 generates the center mapping F

Using

And outputs it to the signature device 200 Can be transmitted. Then, the signing device 200 transmits

Only the first muscles (

) Can be calculated.

)와 제1근들 (

)을

에 포함된 방정식들 중, 다항식들 (F⁽ⁱ⁾ (i=o₁+1, o₁+2, …, m=o₁+o₂))에 대한 방정식들에 적용(또는 대입(plug))하여 o₂ 개의 변수들에 대한 o₂ 개의 선형(또는 일차) 방정식들을 생성할 수 있다.The signature device 200 is a test variable

) And the first muscles (

)of

Of the equation contained in the polynomial of ^{(F (i) (i =} o 1 +1, o 1 +2, ..., m = o 1 + o 2)) of the equation applied (or substituted (plug) to about ) To produce o ₂ linear (or linear) equations for o ₂ variables.

)을 계산할 수 있다(S1075). 실시 예들에 따라, 서명 장치(200)는 가우스 소거법(Gaussian elimination)을 이용하여 o₂ 개의 선형(또는 일차) 방정식들의 제2근들 (

)을 계산할 수 있다.Signature device 200 may be configured to include the second roots of o ₂ linear (or linear) equations

) (S1075). In accordance with embodiments, the signature device 200 may use Gaussian elimination to generate the second roots of o ₂ linear (or linear) equations

) Can be calculated.

), 제1근들 (

) 및 제2근들(

)을 제2결과 값(F^-1(S^-1(M)))으로서 생성할 수 있다(S1077).The signature device 200 is a test variable

), The first muscles (

) And the second roots (

) As a second result value (F- ¹ (S- ¹ (M))) (S1077).

가 성립하므로, 서명 장치 (200)는

를 만족하는 디지털 서명(τ)을 생성할 수 있다.

The signing device 200 is able to

Lt; RTI ID = 0.0 &gt; tau &lt; / RTI &gt;

)를 다시 생성하고, 앞의 과정을 반복하여 제1근들(

)과 제2근들(

)을 계산할 수 있다.According to the embodiments, if o ₂ linear (or linear) equations are harmless,

) Is generated again, and the above process is repeated to obtain the first muscle

) And the second muscles

) Can be calculated.

Although it is assumed that the center mapping F includes the first layer S (1) and the second (= last) layer S (2) for convenience of explanation, it is assumed that the technical idea The ordinary descriptor having the above description can be easily applied even when the center mapping F includes L (L> 2) layers S (1) to S (L).

)를 연립방정식

에 포함된 방정식들 중에서 첫 번째 레이어(S(1))에 포함된 제1다항식들에 대응하는 제1방정식들에 대입하고 상기 제1방정식들의 제1근들을 계산한다.For example, the signature device 200 may include a test variable

) To the simultaneous equations

To the first equations corresponding to the first polynomials included in the first layer S (1) among the equations included in the first equation S (1) and calculates the first roots of the first equations.

)와 상기 제1근들을 연립방정식

에 포함된 방정식들 중에서 두 번째 레이어(S(2))에 포함된 제2다항식들에 대응하는 제2방정식들에 대입하여 상기 제2방정식들의 제2근들을 계산한다.The signature device 200 is a test variable

) And the first roots to a simultaneous equations

(2) corresponding to the second polynomials included in the second layer S (2) among the equations included in the second equation S (2).

의 최종 근들을 구할 수 있고, 상기 최종 근들을 제2결과 값(F^-1(S^-1(M)))으로서 생성할 수 있다.The above method is applied sequentially from the third layer S (3) to the last layer S (L) to calculate the simultaneous equations

, And generate the final roots as a second result value F ^-1 (S ^-1 (M)).

According to embodiments of the present invention, the size of the public key (PK) and the secret key (SK) used in the digital signature system 10 is reduced and accordingly the signature device 200 generates a digital signature The required amount of computation and time are reduced.

A digital signature method in accordance with embodiments of the present invention may be written in a computer readable computer program (or program code) and stored and executed in a computer readable recording medium (e.g., a memory device, a database, or a processor) .

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the true scope of the present invention should be determined by the technical idea of the appended claims.

100: key generation device
200: Digital signature device
300: verification device
110, 210, 310: Processor
120, 220, 320: memory
130, 230, 330: transmission / reception interface

Claims (19)

The key generation device generates multivariate quadratic polynomials (F ⁽ n)) of n (n is a natural number greater than or equal to 2) variables (m is a natural number of 3 or more) defined above on a finite field (K _q , q is a natural number of 2 or more) ⁱ⁾ : K _q ⁿ ? K _q ^m (i = 1, 2, ..., m));
Generating a first reversible mapping (S: K _q ^m ? K _q ^m ) and a second reversible mapping (T: K _q ⁿ ? K _q ⁿ ); And
The key generation apparatus synthesizes the first reversible mapping S, the center mapping F and the second reversible mapping T to generate a public key

), &Lt; / RTI &gt;
The central idea (F) are each a _t o (L &gt; = 2) layers including quadratic polynomials of t (t = 1, ..., L)

And v + m = n,
The first layer among the layers is represented by the following equation,

(here,

)
Polynomials defined according to (

),
The last layer among the layers is expressed by the following equation,

(

,

And

)
Polynomials defined according to (

). &Lt; / RTI &gt; The method according to claim 1,
The first layer is represented by the following equation

(here,

ego

)
Polynomials defined according to (

). &Lt; / RTI &gt; The method according to claim 1,
The last layer is defined by the following equation

(here,

ego

)

Polynomials defined according to (

). &Lt; / RTI &gt; The method according to claim 1,
(S ^-1 ) of the first reversible mapping (S) and a history (T ^-1 ) of the second reversible mapping (T);
The key generation apparatus generates a secret key SK in the history S ^-1 of the first reversible mapping S, the center mapping F of the first reversible mapping S and the history T ^-1 of the second reversible mapping T, To a digital signature device;
The digital signature apparatus calculating a hash message (h (M)) for a given message (M) using a hash function; And
Wherein the digital signature device generates a digital signature (?) For the hash message (h (M)) using the secret key (SK). 5. The method of claim 4, wherein the digital signature device generates the digital signature &lt; RTI ID = 0.0 &gt;
(S ^-1 (h (M))) in the history (S ^-1 ) of the first reversible mapping (S) in which the digital signature device has the hash message h (M) ;
The second result of said digital signature apparatus of the first result value ^{(S -1 (h (M)} )) central idea (F) to the input value ^{(F -1 (S -1 (h} (M)) ));
(T ^-1 ) of the second reversible mapping image T in which the digital signature apparatus sets the second result value F ^-1 (S ^-1 (h (M))) as an input value, Calculating a value T ^-1 (F ^-1 (S ^-1 (h (M)))); And
Wherein the digital signature device generates the third result value T ^-1 F ^-1 S ^-1 h (M))) as the digital signature τ. 6. The method of claim 5, wherein the digital signature device generates the second result value (F- ¹ (S- ¹ (M)))
Wherein the digital signature device is operable to determine

);
Wherein the digital signature device is adapted to receive the test variable &lt; RTI ID =

) To the simultaneous equations

(1) to the equations corresponding to the polynomials included in the first layer S (1) to generate quadratic equations having o ₁ equations and variables;
The digital signature apparatus calculating first roots of quadratic equations having the o ₁ equation and variables;
Wherein the digital signature device is adapted to receive the test variable &lt; RTI ID =

) And the first roots, the simultaneous equations

Calculating remaining roots of equations corresponding to the polynomials included in the remaining layers except for the first layer among the L layers among the equations included in the first layer; And
Wherein the digital signature device generates the first and second roots as the second result value (F ^-1 (S ^-1 (M))). 5. The method of claim 4,
The verification device receiving a hash message (h (M)) and a digital signature (?) From the digital signature device;
Applying the digital signature (?) To the public key, and calculating a digital signature (PK (?) To which the public key is applied;
The verification device compares the received digital signature PK () with the received digital signature PK () and compares the received digital signature PK () with the received hash message h (M) h &lt; / RTI &gt; (M)). &lt; / RTI &gt; The method according to claim 1,
Wherein the shape of the polynomial included in at least one remaining layer of the L layers, excluding the first layer and the last layer,
The form of the polynomial included in the first layer or the form of the polynomial included in the last layer. The method according to claim 1,
Wherein the L is 2. A digital signature unit is mainly thought (F), a first idea (S ^-1) and a second idea (T ^-1) the secret key (SK = containing (S ^-1, F, T ^{- 1} );
Applying the hash function to a given message (M) to generate a hash message (h (M));
Wherein the digital signature device generates a digital signature (?) For the hash message (h (M)) using the secret key (SK)
The center mapping F includes m-variable (n is a natural number of 2 or more) quadratic polynomials of m (m is a natural number of 3 or more) defined on a finite field (K _Q , q is a natural number of 2 or more) (F ⁽ⁱ⁾ : K _q ⁿ ? K _q ^m (i = 1, 2, ..., m)
The center mapping F includes L layers (natural numbers of L? 2) each including quadratic polynomials of o _t (t = 1, ..., L)

And v + m = n,
The first layer among the layers is represented by the following equation,

(here,

)
Polynomials defined according to (

),
The last layer among the layers is expressed by the following equation,

(

,

And

)
Polynomials defined according to (

). &Lt; / RTI &gt; The method of claim 10, wherein the step of the digital signature device generating the digital signature (?) Comprises:
Calculating a first result value (S ^-1 (h (M)) of the first mapping (S ^-1 ) in which the digital signature apparatus takes the hash message (h (M)) as an input value;
The second result of said digital signature apparatus of the first result value ^{(S -1 (h (M)} )) central idea (F) to the input value ^{(F -1 (S -1 (h} (M)) ));
The third result in the second history (T ^-1) which is the digital signature device and the second result value ^{(F -1 (S -1 (h} (M)))) as an input value (T ^-1 ( F ^-1 (S ^-1 (h (M))))); And
Wherein the digital signature device generates the third result value T ^-1 F ^-1 S ^-1 h (M))) as the digital signature τ. 12. The method of claim 11, wherein the digital signature device generates the second result value (F- ¹ (S- ¹ (M)))
Wherein the digital signature device is operable to determine

);
Wherein the digital signature device is adapted to receive the test variable &lt; RTI ID =

) To the simultaneous equations

(1) to the equations corresponding to the polynomials included in the first layer S (1) to generate quadratic equations having o ₁ equations and variables;
The digital signature apparatus calculating first roots of quadratic equations having the o ₁ equation and variables;
Wherein the digital signature device is adapted to receive the test variable &lt; RTI ID =

) And the first roots, the simultaneous equations

Calculating remaining roots of equations corresponding to the polynomials included in the remaining layers except for the first layer among the L layers among the equations included in the first layer; And
Wherein the digital signature device generates the first and second roots as the second result value F ^{- 1} (S ^-1 (M)). 11. The method of claim 10,
Wherein the shape of the polynomial included in at least one remaining layer of the L layers, excluding the first layer and the last layer,
The form of the polynomial included in the first layer or the form of the polynomial included in the last layer. A computer-readable storage medium storing a program including instructions for performing the digital signature method recited in any one of claims 1 to 13. An encryption apparatus including a key generation apparatus,
Wherein the key generation device comprises:
The multivariate quadratic polynomials (F ⁽ⁱ⁾ : K (where m is a natural number of 3 or more) n-variables (n is a natural number of 2 or more) defined above on the finite field (K _q , q is a natural number of 2 or more) _q ⁿ ? K _q ^m (i = 1, 2, ..., m)
The key generation apparatus generates a first reversible mapping (S: K _q ^m ? K _q ^m ) and a second reversible mapping (T: K _q ⁿ ? K _q ⁿ )
The key generation apparatus synthesizes the first reversible mapping S, the center mapping F and the second reversible mapping T to generate a public key

),
The central idea (F) are each a _t o (L &gt; = 2) layers including quadratic polynomials of t (t = 1, ..., L)

And v + m = n,
The first layer among the layers is represented by the following equation,

(here,

)
Polynomials defined according to (

),
The last layer among the layers is expressed by the following equation,

(

,

And

)
Polynomials defined according to (

). 16. The apparatus of claim 15, wherein the encryption device further comprises a digital signature device,
Wherein the key generation device comprises:
A history (S ^-1 ) of the first reversible mapping (S) and a history (T ^-1 ) of the second reversible mapping (T)
(T ^-1 ) of the history (S ^-1 ), the central idea (F) and the second reversible event (T ^-1 ) of the first reversible event S is transmitted to the digital signature device as a secret key and,
The digital signature apparatus comprising:
Generates a hash message h (M) by applying a hash function to a given message M,
Calculates a first result value (S ^-1 (h (M)) of the history (S ^-1 ) in the history of the first reversible mapping (S) in which the hash message h (M)
Produce the first result ^{(S -1 (h (M)} )) the second result value ^{(F -1 (S -1 (h} (M)))) of the central idea (F) according to the input value, and ,
The second result of the third result value ^{(F -1 (S -1 (h} (M)))) in the history (T ^-1) of the second reversible mapping (T) of the input values (T ^-1 (F ^-1 (S ^-1 (h (M)))) is calculated,
Wherein the digital signature apparatus generates the third resultant value T ^-1 (F ^-1 (S ^-1 (h (M)))) as a digital signature τ. The digital signature apparatus according to claim 16,
Any test variable (

),
The test variable (

) To the simultaneous equations

To the equations corresponding to the polynomials included in the first layer S (1) among the equations included in the first layer S (1) to generate quadratic equations having o ₁ equations and variables,
Calculating the first roots of the quadratic equations having the o ₁ equation and the variable,
The test variable (

) And the first roots, the simultaneous equations

Calculating remaining roots of equations corresponding to the polynomials included in the remaining layers except for the first layer among the L layers among the equations included in the first layer,
And generates the first and second residuals as the second result value F ^-1 (S ^-1 (M)). 16. The method of claim 15,
Wherein the shape of the polynomial included in at least one remaining layer of the L layers, excluding the first layer and the last layer,
Wherein the form of the polynomial included in the first layer or the form of the polynomial included in the last layer is the same. 16. The encryption apparatus as claimed in claim 15, wherein L is 2.

Images