KR101593673B1 - Method and Apparatus for generating encrypted signature based lattices, Method and Apparatus for restoring encrypted signature based lattices - Google Patents

Abstract

A method for generating a lattice-based cryptographic signature is disclosed. A lattice-based cryptographic signature generation method according to an embodiment of the present invention sets public variables and generates a public key and a secret key of each of a data sender and a data receiver based on the set public variables and the base generation function step; Generating a signature of the data sender using the public variables, the secret key of the data sender, the object data to be transmitted, and a signature generation function; And generating a cryptographic signature including a signature value for the data sender as a cipher text for the data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data.

Description

FIELD OF THE INVENTION [0001] The present invention relates to a method and apparatus for generating a password signature based on a lattice,

The present invention relates to lattice-based cryptographic signatures, and more particularly, to a method and apparatus for generating a cryptographic signature based on a lattice, and a method and apparatus for recovering a cryptograph signature based on a lattice.

Cryptography is used to ensure confidentiality of data and is one of the most widely used techniques in the field of cryptography. Such cryptographic techniques are usually categorized as symmetric key cryptography and public key cryptography, and this patent deals with public key cryptography. The public key cryptography consists of an encryption key needed to encrypt data and a decryption key necessary to decrypt the ciphertext. The encryption key is publicly accessible and the decryption key is kept by the user. Anyone can encrypt data with the corresponding encryption key, and only the user who has the decryption key can decrypt the encrypted data and view the original data.

Digital signature technology is used for authentication and integrity verification of data and is one of the most widely used technologies together with cryptography in the field of cryptography. In this digital signature technique, the signer generates a signature for his / her data using his / her signature key, and the verifier uses the verification key paired with the signature key to judge the validity of the signature.

If you want to ensure both integrity and confidentiality of your data, you can use both of these techniques for the same data. However, in such a case, there is a disadvantage that the ciphertext and the signature must be generated, stored and managed at the same time. To solve this problem, the technology developed is a password signing technology. It is a technology that simultaneously provides the confidentiality and integrity of the data with only one cipher text. The encryption signature technique is generally a technique of including data and a signature in a passphrase, which the third party can not obtain any information about the data and the signature. The generated cryptographic signature ensures that only the user with the corresponding secret key can recover the signature and data pairs contained in it and that the signature is valid, ensuring confidentiality and integrity of the data at the same time do.

   Most cryptographic signature techniques proposed so far are designed based on factorization, discrete algebra, and pairing. However, these problems, which are considered to be difficult to solve, can not guarantee the reliability of the safety due to the recent development of quantum algorithms. A paper that solves the factorization problem using real quantum algorithms has been proposed. In this environment, interest in lattices is increasing. The existing lattice-based cryptosystem has many problems due to lack of safety proof, but recently, lattice-based cryptosystems proved based on the worst-case problem are emerging. It can be seen that the existing cryptosystem provides very high safety in view of the design based on the average-case problem. In addition, the Lattice cryptosystem is more efficient than the existing techniques. The computational complexity such as factorization, discrete logarithm, and pairing is, but the computational complexity in Lattice is much more efficient. In addition, the lattice cryptosystem is safe for quantum algorithms. Due to these various reasons, various cryptographic systems are being designed in the recent Lattice environment, and this work is considered to be very meaningful. Therefore, there is a need to develop an efficient and secure password signing technology in the Lattice environment.

An object of an embodiment of the present invention is to provide a method and apparatus for generating a cryptographic signature based on a lattice based on a lattice-based cryptosystem, which has both advantages of computational efficiency, high security, and resistance to quantum computer analysis, , And a method and apparatus for restoring a cryptographic signature based on a lattice.

According to another aspect of the present invention, there is provided a method of generating a cryptographic signature based on a lattice, the method comprising: setting public variables and generating a public key of each of a data sender and a data receiver based on the set public variables and a base generation function; And generating a secret key; Generating a signature of the data sender using the public variables, the secret key of the data sender, the object data to be transmitted, and a signature generation function; And generating a cryptographic signature including a signature value for the data sender as a cipher text for the data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data.

A first multiplication matrix generated by multiplying the public key matrix A of the data sender by the secret key matrix S _A of the data sender when the public key and secret key of the data sender and the data receiver are respectively a matrix, The value of each of the components of the second multiplication matrix generated by multiplying the public key matrix B of the data recipient and the secret key matrix S _B of the data recipient may be zero.

Preferably, the public variables include a first variable n, a second variable m, a third variable delta and a fourth variable q that are mutually related, and the public key matrix A of the data sender and the public key matrix A of the data sender The key matrix B has random values between 0 and q with a size of n * m, and the secret key matrix S _A of the data sender and the secret key matrix S _B of the data receiver have a size of m * m You can have random values between 0 and q as a component.

Preferably, the step of generating the signature of the data sender comprises the steps of inputting an m-dimensional vector having values between 0 and 2 as an element and an n-dimensional vector having random values between 0 and q as its components as input 0 Setting a secure hash function to output an n-dimensional vector having random hash values between q and q as elements; Generating an n-dimensional vector s having random values between 0 and q as an element; And an m-dimensional vector corresponding to the objective data and the n-dimensional hash output vector obtained by inputting the vector s into the secure hash function, a secret key S _A of the data sender, And generating a signature? Of the data sender having an m-dimensional vector form using the function?

Preferably, the cryptographic signature may be generated according to Equation (3).

&Quot; (3) "

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender , modq represents the remainder of the value in parentheses divided by q.

According to another aspect of the present invention, there is provided a method for restoring cryptographic signature based on a public key of a data recipient, a signature of a data sender, and object data to be transmitted, Receiving a cryptographic signature including a signature value for the data sender as a cipher text; Calculating an intermediate operation value having a form in which only the signature of the data sender and the object data are combined using the secret key of the data receiver; Extracting the target data from the intermediate calculation value by applying a mod function to the calculated intermediate calculation value; And extracting a signature of the data sender from the intermediate computation value using the extracted object data, wherein the public key and the secret key of the data recipient have a matrix form and correspond to the public key of the data recipient And the value of each of the elements of the matrix generated by multiplying the matrix corresponding to the secret key of the data receiver by 0 is 0.

Preferably, c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, And modq represents a remainder value obtained by dividing the value in parentheses by q, the encryption signature has a form according to Equation (3)

&Quot; (3) "

The step of calculating the intermediate operation value

The intermediate calculation value can be calculated as 2? + M based on the equations (4) and (5).

&Quot; (4) "

&Quot; (5) "

(S _B ) ^-T is an inverse matrix of the (S _B ) ^T matrix. In this case, (S _B ) ^T is a matrix in which a matrix S _B corresponding to the secret key of the data receiver is transposed.

Preferably, the step of extracting the object data may be performed according to the equation (6).

&Quot; (6) "

Preferably, extracting the signature of the data sender may be performed according to Equation (7).

&Quot; (7) "

Preferably, the step of verifying the integrity of the object data further comprises: calculating an n-dimensional vector s having random values as an element in Equation 8, And whether or not they are satisfied.

&Quot; (8) "

&Quot; (9) "

Here, 隆 is a third one of the open variables including the first variable n, the second variable m, the third variable 隆 and the fourth variable q, and H is an m-dimension Dimensional vector having random hash values between 0 and q as an input and an n-dimensional vector having random vectors between 0 and q as elements.

According to another aspect of the present invention, there is provided a lattice-based cryptographic signature generation apparatus for generating public key cryptograms of a data sender and a data recipient based on the set public variables and a base generation function, A key generation unit for generating a public key and a secret key; A signature generator for generating a signature of the data sender using the public variables, the secret key of the data sender, the object data to be transmitted, and the signature generation function; And a cryptographic signature generator for generating a cryptographic signature including a signature value for the data sender as a cipher text for the data to be transmitted using the public key of the data receiver, the signature of the data sender, and the object data.

Preferably, the signature generator is configured to input a vector of m-dimension having values between 0 and 2 as an element and an vector of n-dimension having random values between 0 and q as elements, A hash function generation unit for setting a secure hash function that outputs an n-dimensional vector having values as elements; A vector generating unit for generating an n-dimensional vector s having random values between 0 and q as elements; And an m-dimensional vector corresponding to the objective data and the n-dimensional hash output vector obtained by inputting the vector s into the secure hash function, a secret key S _A of the data sender, And a signature processing unit for generating a signature < s > of the data sender having an m-dimensional vector form using a function.

According to another aspect of the present invention, there is provided a lattice-based cryptographic signature restoration apparatus for recovering a cryptographic signature using a public key of a data recipient, a signature of a data sender, and object data to be transmitted, A receiver for receiving a cryptographic signature including a signature value for the data sender as a cipher text; An intermediate computation unit for computing an intermediate computation value having a form in which only the signature of the data sender and the objective data are combined using the secret key of the data recipient based on the encryption signature; A data extraction unit for extracting the object data from the intermediate calculation value by applying a mod function to the calculated intermediate calculation value; And a signature extraction unit for extracting a signature of the data sender from the intermediate calculation value using the extracted object data, wherein the public key and the secret key of the data receiver have a matrix form, and the public key of the data recipient The value of each of the elements of the matrix generated by multiplying the corresponding matrix by the matrix corresponding to the secret key of the data receiver is zero.

Preferably, the lattice-based cryptographic signature restoration apparatus according to an embodiment of the present invention further includes an integrity verification unit for verifying the integrity of the object data, Dimensional vector s, and then verifies the integrity based on whether or not the expression (9) is satisfied.

&Quot; (8) "

&Quot; (9) "

Here, 隆 is a third one of the open variables including the first variable n, the second variable m, the third variable 隆 and the fourth variable q, and H is an m-dimension Dimensional vector having random hash values between 0 and q as an input and an n-dimensional vector having random vectors between 0 and q as elements.

Since the cryptographic signature technique according to an embodiment of the present invention is designed based on lattice, it has the advantages of computational efficiency, high safety, and resistance to quantum computer analysis of a lattice-based cryptosystem, and guarantees integrity and confidentiality of data simultaneously There is an effect that can be done.

FIG. 1 is a diagram for explaining a lattice-based cryptographic signature generation apparatus according to an embodiment of the present invention.
2 is a block diagram illustrating a signature generator according to an exemplary embodiment of the present invention.
3 is a flowchart illustrating a method of generating a lattice-based encryption signature according to an exemplary embodiment of the present invention.
4 is a flowchart illustrating a signature generation method according to an embodiment of the present invention.
FIG. 5 is a diagram for explaining a lattice-based cryptographic signature restoration apparatus according to an embodiment of the present invention.
6 is a flowchart illustrating a method of recovering a cryptographic signature based on a lattice according to an embodiment of the present invention.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the invention is not intended to be limited to the particular embodiments, but includes all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. Like reference numerals are used for like elements in describing each drawing.

The terms first, second, A, B, etc. may be used to describe various elements, but the elements should not be limited by the terms. The terms are used only for the purpose of distinguishing one component from another. For example, without departing from the scope of the present invention, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component. And / or < / RTI > includes any combination of a plurality of related listed items or any of a plurality of related listed items.

It is to be understood that when an element is referred to as being "connected" or "connected" to another element, it may be directly connected or connected to the other element, . On the other hand, when an element is referred to as being "directly connected" or "directly connected" to another element, it should be understood that there are no other elements in between.

The terminology used in this application is used only to describe a specific embodiment and is not intended to limit the invention. The singular expressions include plural expressions unless the context clearly dictates otherwise. In the present application, the terms "comprises" or "having" and the like are used to specify that there is a feature, a number, a step, an operation, an element, a component or a combination thereof described in the specification, But do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, or combinations thereof.

Unless defined otherwise, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Terms such as those defined in commonly used dictionaries are to be interpreted as having a meaning consistent with the contextual meaning of the related art and are to be interpreted as either ideal or overly formal in the sense of the present application Do not.

Before describing the embodiments of the present invention, the lattices that are the basis of the present invention will be described, and the algorithms used in an embodiment of the present invention will be described in detail.

- lattices

차원의 풀-랭크(full-rank) 정수 래티스를 사용하며, 이것은 유한개의 지수(finite index)를 가지는

의 이산 가산 서브그룹(discrete additive subgroup)이다. 즉, 쿼션트 그룹(quotient group)

이 유한하다. 하나의 래티스

은

개의 선형 독립 기저(basis) 벡터

의 모든 정수 선형 결합의 집합과 동일하게 정의된다.In the present invention,

Dimensional full-rank integer lattice, which has a finite index < RTI ID = 0.0 >

Lt; RTI ID = 0.0 > a < / RTI > discrete additive subgroup. That is, a quotient group

This is finite. One Lattice

silver

The linear independent basis vectors

Is defined as the set of all integer linear combinations of.

일 경우, 동일한 래티스를 생성하는 기저들은 무수히 많다.here

, There are a myriad of bases for generating the same lattice.

- Hard Lattice, SIS, LWE Problems

과

는 정수이며, 차원

은 본 발명에서 사용되는 보안 파라미터이고, 모든 다른 파라미터들은

의 함수들로 내포되었다고 가정한다. 여기서

차원 하드 래티스는 패리티 검사 행렬(parity check matrix)

에 의해 생성되며, 다음과 같이 정의된다.In the present invention, a specific form of the following integer lattice is used. here

and

Is an integer, and dimension

Is a security parameter used in the present invention, and all other parameters

Are implied as functions of. here

Dimensional hard lattice is a parity check matrix.

And is defined as follows.

에 대해서, 패리티 검사 행렬

에 의해 생성되는 코셋(coset)은 다음과 같이 정의된다.And any

, A parity check matrix

Is defined as follows: cos (cos?

과 어떤

에 대해, 균등하게 랜덤한(uniformly random)

의 열 벡터는

상의 모두를 (

확률을 제외하고) 생성할 수 있다. 따라서 본 발명에서는 균등하게 랜덤한

를 사용한다.Some fixed constants

And any

Uniformly random < RTI ID = 0.0 >

The column vector of

All of the above (

(Except for probability). Therefore, in the present invention,

Lt; / RTI >

(Short Integer Solution) 문제에 대해서 살펴보자. 이 문제는 평균적인 경우에 어려운 문제(average-case hardness problems)에 속해 있으며, 이 문제를 최악의 경우에 어려운 문제(worst-case hardness problems)로 커넥션(connection)하는 방법에 대해서도 공지된 바 있다.Next to Hard Lattice

(Short Integer Solution). This problem belongs to the average-case hardness problems, and it has been known how to connect the problem to worst-case hardness problems in the worst case.

문제는 어떤

에 대해 균등하게 랜덤한 행렬

를 입력으로 받아

와

(즉,

)을 만족하는 영이 아닌(nonzero) 정수 벡터

를 찾는 것이다.

문제에서 알고리즘

의 성공 확률은

로 나타낸다.Note that,

The problem is

A uniformly random matrix < RTI ID = 0.0 >

As input

Wow

(In other words,

) Nonzero integer vector satisfying

.

Algorithms in Problems

The probability of success is

Respectively.

와

상의 특정 분포

에 대해,

문제는 주어진 다수의

에서 벡터

를 찾는 것으로 정의된다.Also, the LWE problem is an integer

Wow

Specific distribution of

About,

The problem is that a given number of

In vector

.

가 분포

을 따르는 경우, 이 역시 SIS 문제와 마찬가지로 최악의 경우에 어려운 문제(worst-case hardness problems)로 커넥션(connection)할 수 있다. 여기서 분포

란

, 소수

에 대해

가 평균

, 표준편차

을 따르는 정규분포라고 할 때,

에 가장 가까운 정수를 나타내는 확률변수를 의미한다.In particular, in the LWE problem

Distribution

, This can also be a connection to the worst-case hardness problems as in the SIS problem. Here distribution

Ran

, Minority

About

Average

, Standard Deviation

Is a normal distribution that follows < RTI ID = 0.0 >

Is a random variable that represents the integer closest to the target.

- Gaussian distribution in Lattice

과 차원

에 대해, 가우시안 함수(Gaussian function)

는

로 정의된다. 어떤 코셋

에 대해, 코셋 상의 (중심이

인) 이산 가우시안 분포(discrete Gaussian distribution)

는 각각의

에서

에 비례하는 확률을 가진다.The Gaussian distribution in the lattices will be described based on the contents proposed in the present invention. which

And dimension

Gaussian function < RTI ID = 0.0 >

The

. Any coset

(The center of gravity)

(Discrete Gaussian distribution)

Respectively,

in

.

는 어떤

에 대한

의 기저를 말하며,

이다.Next, properties related to the Gaussian distribution in the lattices used in the present invention will be described. From here

Is any

For

, And,

to be.

통계적인 거리를 가지는)

로부터 샘플링을 할 수 있는 PPT(probabilistic polynomial time) 알고리즘 SampleD(S,y,s)이 존재한다.(

With statistical distances)

(S, y, s), which is a probabilistic polynomial time (PPT)

- Base and trap doors

와 이러한 매트릭스로 생성되는 래티스

의 짧은 기저

를 생성하는 알고리즘

GBasis

을 사용한다. 위의 알고리즘에서 파라미터들은

을 만족하며, 기저

의 길이는

만큼 짧다. 임의의 래티스의 짧은 기저를 찾는 문제는 결국

문제이기 때문에 알고리즘

은 임의의 래티스와 그것의 트랩도어(

문제에 대한) 즉, 짧은 기저를 생성하게 된다.In the present invention, a matrix arbitrarily selected from an even distribution

And the lattice created by this matrix

Short base of

Algorithm to generate

GBasis

Lt; / RTI > In the above algorithm,

, And the base

The length of

. The problem of finding the short bases of arbitrary lattices is ultimately

Because of the problem,

Is an arbitrary lattice and its trap door (

That is, a short base for the problem).

- Base and trap door with special properties

알고리즘을 사용한다. 해당 알고리즘은 위의 GBasis의 입력값에 추가적으로 매트릭스

를 입력받아 위의 알고리즘과 동일한 분포의 결과값 즉, 래티스 및 그것의 짧은 기저 쌍

을 출력한다.In the present invention, a modified trap door generation algorithm satisfying the special properties of the above-described trap door generation algorithm is proposed.

Algorithm. In addition to the input values of GBasis above,

And outputs the result of the same distribution as the above algorithm, that is, the lattice and its short base pair

.

와 출력 매트릭스인

사이에는

을 만족한다는 것이다. SuperSamp의 입력 파라미터는 수식

을 만족해야 한다.The important property here is that the matrix

And output matrix

Between

. The input parameters of the SuperSamp are expressed as Equation

.

- delegation method

을 정의한다.

의 열벡터의 분포는 가우시안 분포

를 따른다.In the present invention, BasisDel algorithm, which is a technique for delegating short base of lattice, is used. First, a matrix having a short length vector as a column vector

.

The distribution of the column vectors of the Gaussian distribution

.

알고리즘은 매트릭스

, 래티스

의 짧은 기저

, 위에서 정의한 짧은 매트릭스

그리고 파라미터

을 입력값으로 받아, 매트릭스

와 이로 생성되는 래티스

의 짧은 기저

을 출력한다. 특히, 생성된 기저의 길이는

만큼 증가 비율을 갖는다.BasisDel

The algorithm

, Lattice

Short base of

, The short matrix defined above

And the parameters

As an input value,

And the resulting lattice

Short base of

. In particular, the generated base length is

.

- Matrix transformation method

은 매트릭스

, 래티스

의 짧은 기저

, 그리고 파라미터

을 입력값으로 받아, 위에서 정의한 짧은 매트릭스 분포

을 따르는 매트릭스

을 출력한다.The present invention proposes the following matrix (lattice) transformation algorithm and Transform algorithm. Transform the corresponding algorithm

The matrix

, Lattice

Short base of

, And parameters

As an input value, the short matrix distribution defined above

≪ / RTI >

.

는 수식

을 만족한다. 해당 알고리즘을 설계하는 방법은

를 각각 매트릭스

의

번째 열이라고 했을 때,

SamplePre

을 이용하여 생성할 수 있다. 해당 방법을

번 사용하면 매트릭스를 완성할 수 있으며, SamplePre의 성질에 따라

임을 확인할 수 있다.The output matrix

The equation

. How to design the algorithm

Respectively,

of

When we say the third column,

SamplePre

. ≪ / RTI > How to

Use it once to complete the matrix, depending on the nature of the SamplePre

.

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

FIG. 1 is a diagram for explaining a lattice-based cryptographic signature generation apparatus according to an embodiment of the present invention.

Referring to FIG. 1, a lattice-based cryptographic signature generation apparatus according to an exemplary embodiment of the present invention includes a key generation unit 110, a signature generation unit 120, and an encryption signature generation unit 130.

The key generation unit 110 sets public variables, and generates a public key and a secret key of each of the data sender and the data receiver based on the set public variables and the base generation function.

In this case, the open variables may include a mutually related first variable n, a second variable m, a third variable?, And a fourth variable q, and the first variable n is a security parameter, .

, q=(2δ+1)m²과 같이 정의될 수 있다. The first variable n, the second variable m, the third variable delta and the fourth variable q are n = k, m = 10nlogq,

, q = ( ^2? + 1) m ² .

On the other hand, in the lattice encryption system, the public key and secret key of each of the data sender and the data receiver can be defined as Equation (1) using the base generation function GBasis.

A denotes a public key of a data sender as a matrix, S _A denotes a secret key of a data sender as a matrix, B denotes a public key of a data receiver as a matrix, S _B denotes a secret key of a data sender as a matrix The public key matrix A of the data sender and the public key matrix B of the data recipient have random values between 0 and q with a size of n * m as a component, and the secret key matrix S _A of the data sender and the The secret key matrix, S _B , has a magnitude of m * m and has random values between 0 and q as components.

On the other hand, the public key A of the data sender, the secret key S _A of the data sender, the public key B of the data receiver, the secret key S _B The first multiplication matrix generated by multiplying the public key matrix A of the data sender by the secret key matrix S _A of the data sender and the first multiplication matrix generated by multiplying the public key matrix B of the data recipient and the secret key K of the data recipient The value of each of the components of the second multiplication matrix generated by multiplying the matrix S _B becomes zero.

The lattice-based cryptographic signature restoration method according to an embodiment of the present invention restores the cryptographic signature using this property.

The signature generation unit 120 generates a signature of the data sender using public variables, a secret key of the data sender, an object data to be transmitted, and a signature generation function.

At this time, since the signature generator 120 generates the signature of the data sender using the private key of the data sender, only the data sender can generate the signature of the data sender.

A specific process by which the signature generation unit 120 generates a signature of the data sender will be described later with reference to FIG.

The encryption signature generation unit 130 generates a cryptographic signature including a signature value for the data sender as a cipher text for data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data.

As such, an embodiment of the present invention generates the encryption signature using the base generation function and the signature generation function of the lattice encryption system, and thus provides advantages of the computational efficiency, high security, and immunity to quantum computer analysis of the lattice-based encryption system It is possible to guarantee both integrity and confidentiality of data at the same time.

2 is a block diagram illustrating a signature generator according to an exemplary embodiment of the present invention.

Referring to FIG. 2, the signature generator 120 includes a hash function generator 122, a vector generator 124, and a signature processor 126.

를 설정한다. The hash function generation unit 122 receives an m-dimensional vector having values between 0 and 2 as elements and an n-dimensional vector having random values between 0 and q as elements, A secure hash function that outputs an n-dimensional vector whose values are components.

.

를 생성한다. The vector generation unit 124 generates an n-dimensional vector having random values between 0 and q as components

.

The signature processing unit 126 inputs an output n-dimensional hash output vector by inputting the vector s generated by the vector generating unit 120 and the vector m of the m-dimension corresponding to the object data to the secure hash function H, S _A , the third parameter δ, and the signature generation function SampleD to generate a signature σ of the data sender having the m-dimensional vector form.

That is, the signature processing unit 126 generates the signature? Of the data sender according to Equation (2).

이다. 즉, M은 m차원의 벡터로서 0부터 2사이의 값들을 구성요소로 한다. At this time, M indicated by the input to the hash function H represents the target data to be transmitted, and the data space of M

to be. That is, M is an m-dimensional vector, and values between 0 and 2 are elements.

Meanwhile, since the signature generation function SampleD is a function commonly used in the lattice encryption system, a detailed description thereof will be omitted.

3 is a flowchart illustrating a method of generating a lattice-based encryption signature according to an exemplary embodiment of the present invention.

In step 310, a lattice-based cryptographic signature generation device sets public variables, and generates a public key and a secret key of each of the data sender and the data receiver based on the set public variables and the base generation function.

In step 320, a lattice-based cryptographic signature generation device generates a signature of the data sender using the public variables, the secret key of the data sender, the destination data to be transmitted, and the signature generation function.

In step 330, the lattice-based cryptographic signature generation device generates a cryptographic signature including a signature value for the data sender as a ciphertext for data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data.

More specifically, a lattice-based encryption signature generation apparatus generates a password signature as shown in Equation (3).

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender, modq represents the remainder of the value in parentheses divided by q.

4 is a flowchart illustrating a signature generation method according to an embodiment of the present invention.

In step 410, the lattice-based cryptographic signature generation apparatus receives an m-dimensional vector having values between 0 and 2 as an element and an n-dimensional vector having random values between 0 and q as elements, And sets a secure hash function that outputs an n-dimensional vector whose elements are random hash values between them.

In step 420, the lattice-based cryptographic signature generator generates an n-dimensional vector s with random values between 0 and q as an element.

In step 430, the lattice-based cryptographic signature generation apparatus inputs an m-dimensional vector and a vector s corresponding to the object data in the secure hash function and outputs the output n-dimensional hash output vector, the secret key S _A of the data sender, The signature σ of the data sender having the m-dimensional vector form is generated using the variable δ and the signature generation function.

FIG. 5 is a diagram for explaining a lattice-based cryptographic signature restoration apparatus according to an embodiment of the present invention.

5, a lattice-based cryptographic signature restoration apparatus according to an embodiment of the present invention includes a receiving unit 510, an intermediate calculation unit 520, a data extraction unit 530, and a signature extraction unit 540 do.

The receiving unit 510 receives a cryptographic signature including a signature value for the data sender as a cipher text for the target data generated using the public key of the data recipient, the signature of the data sender, and the object data to be transmitted.

The intermediate computation unit 520 computes an intermediate computation value having a form in which only the signature of the data sender and the objective data are combined using the secret key of the data receiver.

For example, the intermediate calculation unit 520 can calculate the intermediate calculation value based on Equation (4) and Equation (5).

이 산출된다. (S _B ) ^T is a matrix transposed to a matrix S _B corresponding to the secret key of the data receiver, and in Equation (4), (S _B ) ^T is multiplied by the encryption signature c. As described above, Since the value of each of the components of the second multiplication matrix generated by multiplying the public key B matrix of the data recipient by the secret key S _B matrix of the data receiver is 0,

.

In this case, (S _B) ^-T is (S _B) as the inverse matrix of the matrix ^T, is calculated by giving the intermediate computation value 2σ + M by multiplying the (S _B) ^-T to the value calculated by the equation (4).

The data extraction unit 530 applies the mod function to the calculated intermediate operation value to extract the target data from the intermediate operation value.

For example, the data extracting unit 530 can extract the object data based on Equation (6).

이기 때문이다. The reason why the objective data can be extracted by applying the mod2 function to the intermediate calculation value 2σ + M in Equation (6) is that 2σ is an even value, and the data space of M

.

The signature extraction unit 540 extracts the signature of the data sender from the intermediate calculation value using the extracted object data.

For example, the signature extraction unit 540 may extract the signature of the data sender based on Equation (7)

In Equation (7), after subtracting M from the intermediate calculation value 2σ + M, the signature σ of the data sender can be extracted simply by dividing the calculation result by 2.

Preferably, the lattice-based cryptographic signature restoration apparatus according to an embodiment of the present invention may further include an integrity verification unit (not shown) for verifying the integrity of the object data.

The integrity verification unit can verify the integrity of the object data by Equations (8) and (9).

&Quot; (8) "

According to Equation (8), the integrity verification unit calculates an n-dimensional vector s having random values as its constituent elements.

&Quot; (9) "

The integrity verification unit applies the vector s calculated in Equation (8) to Equation (9) and verifies the integrity of the objective data based on whether all three conditions of Equation (9) are satisfied. If all three conditions of Equation (9) are satisfied, the integrity of the objective data is recognized, and if none of the three conditions of Equation (9) is satisfied, the integrity of the objective data is not recognized.

As described above, according to the lattice-based cryptographic signature restoration apparatus according to the embodiment of the present invention, since the target data and the signature? Of the data sender can be extracted from the received cryptographic signature, the data sender and the data recipient can use the cryptographic signature It is possible to ensure both integrity and confidentiality of data at the same time by transmitting and receiving data.

6 is a flowchart illustrating a method of recovering a cryptographic signature based on a lattice according to an embodiment of the present invention.

In step 610, the lattice-based cryptographic signature restoration apparatus generates a cryptographic signature including a signature value for the data sender as a ciphertext for the objective data generated using the public key of the data recipient, the signature of the data sender, Lt; / RTI >

In step 620, the lattice-based cryptographic signature restoration apparatus calculates an intermediate computation value having a form in which only the signature of the data sender and the objective data are combined using the secret key of the data recipient based on the received cryptographic signature.

In step 630, the lattice-based cryptographic signature recovery apparatus extracts the object data from the intermediate computation value by applying the mod function to the computed intermediate computation value.

In step 640, the lattice-based cryptographic signature recovery apparatus extracts the signature of the data sender from the intermediate calculation value using the extracted object data.

Finally, the lattice-based cryptographic signature restoration device can verify the integrity of the object data using the extracted object data and the signature of the data sender.

The above-described embodiments of the present invention can be embodied in a general-purpose digital computer that can be embodied as a program that can be executed by a computer and operates the program using a computer-readable recording medium.

The computer readable recording medium includes a magnetic storage medium (e.g., ROM, floppy disk, hard disk, etc.), optical reading medium (e.g., CD ROM, DVD, etc.).

The present invention has been described with reference to the preferred embodiments. It will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. Therefore, the disclosed embodiments should be considered in an illustrative rather than a restrictive sense. The scope of the present invention is defined by the appended claims rather than by the foregoing description, and all differences within the scope of equivalents thereof should be construed as being included in the present invention.

Claims (14)

Setting public variables, and generating a public key and a private key of each of the data sender and the data receiver based on the set public variables and the base generating function;
Generating a signature of the data sender using the public variables, the secret key of the data sender, the object data to be transmitted, and a signature generation function; And
Generating a cryptographic signature including a signature value for the data sender as a cipher text for the data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data,
Wherein the cryptographic signature is generated according to Equation (3).
&Quot; (3) "

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender , modq represents the remainder of the value in parentheses divided by q. The method according to claim 1,
When the public key and secret key of each of the data sender and the data receiver are matrices,
A first multiplication matrix generated by multiplying the public key matrix A of the data sender by the secret key matrix S _A of the data sender and the first multiplication matrix generated by multiplying the public key matrix B of the data recipient by the secret key matrix S _B of the data recipient Wherein the value of each of the components of the 2-multiplication matrix is zero. 3. The method of claim 2,
The public variables include a first variable n, a second variable m, a third variable? And a fourth variable q, which are mutually related,
The public key matrix A of the data sender and the public key matrix B of the data recipient have random values between 0 and q,
Wherein the secret key matrix S _A of the data sender and the secret key matrix S _B of the data receiver have random values ranging from 0 to q with a size of m * m as a component. . The method of claim 3,
The step of generating a signature of the data sender
An n-dimensional vector having an m-dimensional vector having values between 0 and 2 and a random value between 0 and q as input, and an n-dimensional vector having random hash values between 0 and q as input Setting a secure hash function to output a vector of the hash function;
Generating an n-dimensional vector s having random values between 0 and q as an element; And
Dimensional hash output vector obtained by inputting the m-dimensional vector corresponding to the objective data and the vector s into the secure hash function, the secret key S _A of the data sender, the third variable? Generating a signature < RTI ID = 0.0 > o < / RTI > of the data sender having an m-dimensional vector form. delete Receiving a cryptographic signature including a signature value for the data sender as a cipher text for the target data generated using the public key of the data recipient, the signature of the data sender, and the target data to be transmitted;
Calculating an intermediate operation value having a form in which only the signature of the data sender and the object data are combined using the secret key of the data receiver;
Extracting the target data from the intermediate calculation value by applying a mod function to the calculated intermediate calculation value; And
And extracting the signature of the data sender from the intermediate calculation value using the extracted object data,
The public key and the secret key of the data receiver have a matrix form and the values of the elements of the matrix generated by multiplying the matrix corresponding to the public key of the data recipient and the matrix corresponding to the secret key of the data recipient are 0 Lt; / RTI &
Wherein the received cryptographic signature has a form according to Equation (3).
&Quot; (3) "

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender , modq represents the remainder of the value in parentheses divided by q. The method according to claim 6,
The step of calculating the intermediate operation value
And the intermediate calculation value is calculated as 2? + M based on Equation (4) and Equation (5).
&Quot; (4) "

&Quot; (5) "

In this case, (S _B) ^T is a matrix S _B corresponding to the private key of the data receiver transposed matrix, (S _B) ^-T is (S _B) being the inverse of the ^T matrix. 8. The method of claim 7,
The step of extracting the objective data
(6). ≪ / RTI >
&Quot; (6) "

8. The method of claim 7,
The step of extracting the signature of the data sender
(7). ≪ / RTI >
&Quot; (7) "

8. The method of claim 7,
Further comprising verifying the integrity of the object data,
The step of verifying the integrity is performed based on whether or not an equation (9) is satisfied after calculating an n-dimensional vector s having random values as elements in Equation (8). Way.
&Quot; (8) "

&Quot; (9) "

Here, 隆 is a third one of the open variables including the first variable n, the second variable m, the third variable 隆 and the fourth variable q, and H is an m-dimension And outputs an n-dimensional vector having random hash values between 0 and q as an input, by inputting an n-dimensional vector having a vector of 0 to q and random values between 0 and q as an element. A key generation unit for setting public variables and generating a public key and a secret key of each of the data sender and the data receiver based on the set public variables and the base generation function;
A signature generator for generating a signature of the data sender using the public variables, the secret key of the data sender, the object data to be transmitted, and the signature generation function; And
And a cryptographic signature generator for generating a cryptographic signature including a signature value for the data sender as a cipher text for the data to be transmitted using the public key of the data recipient, the signature of the data sender, and the object data,
The password signature
Is generated according to Equation (3).
&Quot; (3) "

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender , modq represents the remainder of the value in parentheses divided by q. 12. The method of claim 11,
The signature generator
An n-dimensional vector having an m-dimensional vector having values between 0 and 2 and a random value between 0 and q as input, and an n-dimensional vector having random hash values between 0 and q as input A hash function generating unit for setting a secure hash function for outputting a vector of the hash function;
A vector generating unit for generating an n-dimensional vector s having random values between 0 and q as elements; And
An m-dimensional vector corresponding to the objective data and an n-dimensional hash output vector input by inputting the vector s, a secret key S _A of the data sender, a third variable delta and the signature generation function And a signature processing unit for generating a signature < s > of the data sender having an m-dimensional vector form. A receiver for receiving a cryptographic signature including a signature value for the data sender as a cipher text for the target data generated using the public key of the data receiver, the signature of the data sender, and the object data to be transmitted;
An intermediate computation unit for computing an intermediate computation value having a form in which only the signature of the data sender and the objective data are combined using the secret key of the data recipient based on the encryption signature;
A data extraction unit for extracting the object data from the intermediate calculation value by applying a mod function to the calculated intermediate calculation value; And
And a signature extraction unit that extracts the signature of the data sender from the intermediate calculation value using the extracted object data,
The public key and the secret key of the data receiver have a matrix form and the values of the elements of the matrix generated by multiplying the matrix corresponding to the public key of the data recipient and the matrix corresponding to the secret key of the data recipient are 0 Lt; / RTI &
Wherein the cryptographic signature has a form according to Equation (3).
&Quot; (3) "

Where c denotes a cryptographic signature, B ^T denotes a value obtained by transposing the public key B of the data recipient, s denotes an n-dimensional vector having random values between 0 and q as an element, σ denotes a signature of the data sender , modq represents the remainder of the value in parentheses divided by q. 14. The method of claim 13,
Further comprising an integrity verification unit for verifying the integrity of the object data,
The integrity verification unit may calculate an n-dimensional vector s having random values as elements in Equation (8), and then verify the integrity based on whether Equation (9) is satisfied or not. Device.
&Quot; (8) "

&Quot; (9) "

Here, 隆 is a third one of the open variables including the first variable n, the second variable m, the third variable 隆 and the fourth variable q, and H is an m-dimension And outputs an n-dimensional vector having random hash values between 0 and q as an input, by inputting an n-dimensional vector having a vector of 0 to q and random values between 0 and q as an element.

Images