WO2015030553A1

WO2015030553A1 - Lattice-based certificateless signature system and method

Info

Publication number: WO2015030553A1
Application number: PCT/KR2014/008144
Authority: WO
Inventors: 김기성; 정익래; 박소현
Original assignee: 고려대학교 산학협력단
Priority date: 2013-08-30
Filing date: 2014-09-01
Publication date: 2015-03-05
Also published as: KR101404642B1

Abstract

The present invention provides a digital signature system comprising: a master object for generating a first secret key by using a master key of the master object and published identification information of a user object, and then allocating the first secret key to the user object; and the user object for generating a public key of the user object and a second secret key, wherein the user object comprises: a signer object for transmitting, to a verifier object, a signature generated by using the public key, the first secret key and the second secret key of the signer object; and the verifier object for verifying the signature received from the signer object by using the published identification information of the signer object and the public key, and a trapdoor generated on the basis of the difficulty of a small integer solution (SIS) problem in a lattice is used for the generation of the master key, the first secret key and the second secret key.

Description

Lattice-based certificate unused signing system and method

The present invention relates to an electronic signature system and method.

Digital signature technology is used for authentication and integrity of data and is one of the most widely used technologies in cryptography. In this digital signature technology, the signer generates a signature using a private key for a given message, and the verifier uses the public key paired with the private key to determine the validity of the signature.

In this environment, the problem of proving which user is a specific public key is very important. In most environments, this problem is solved through a certificate issued by a trusted third party.

However, certificate-based digital signature systems are expensive to maintain, and the issuing authority must handle the enormous traffic. It also has a trust issue with the certificate itself.

Accordingly, a paper titled “Certificateless Public Key Cryptography” published by A.AC.RYPT in 2003 by S. S. Al-Riyami and K. G. Paterson proposed a digital signature technology without a certificate. Since no certificate is used, the above-mentioned problems are solved, providing higher efficiency and security than conventional certificate-based digital signature systems.

On the other hand, a lot of research has been done on the mathematical difficulties that are the foundation for enhancing the safety of signatures. For example, on average lattice, known as worst-case hardness problems, to average-case hardness problems, such as the difficulty of discrete algebraic problems and the difficulty of fold-line functions. Significance techniques are evolving based on the difficulty of small integer solution (SIS) problems and learning with errors (LWE) problems. This lattice-based encryption technology provides not only high security but also operational efficiency. In particular, it is known to be resistant to quantum computer analysis, and research on this has been greatly increased in recent years.

Therefore, if Lattice-based cryptography is applied to certificate-free digital signature technology, it is possible to provide digital signature technology with higher security and efficiency.

Regarding an electronic signature, Korean Patent Publication No. 0369408 (name of the invention: "a method for designating a recipient-specific proxy signature in mobile communication") discloses a signature generation method based on the difficulty of discrete algebra problems.

In addition, Korean Laid-Open Patent Publication No. 2005-0128506 (name of the invention: "Limited validator signature method using parallel mapping") discloses a method for generating a specified validator signature using the parallel mapping.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object thereof is to provide an electronic signature system and method having high safety and efficiency.

In order to achieve the above object, an electronic signature system according to the first aspect of the present invention uses a master key and public identification information of a user entity to generate a first private key and assign it to the user entity. individual; And a user entity that generates its own public key and a second private key; wherein the user entity is a verifier entity that generates a signature generated using the public key, the first private key, and the second private key. Signer object to send to; And a verifier entity that verifies a signature received from the signer entity using the public identification information of the signer entity and a public key, wherein the master key, the first secret key, and the second secret key are generated. A trapdoor generated based on the difficulty of a small integer solution (SIS) problem on the lattice is used.

According to a second aspect of the present invention, there is provided a digital signature method comprising: (a) a master entity setting security parameters and generating its own master key; (b) the master entity generating and assigning a first private key to the user entity based on the publicly identified identification information of the user entity including a signer entity and a verifier entity; (c) the user entity generating its public key and second private key; (d) sending a signature generated by the signer entity using its public key, first secret key, and second secret key to the verifier entity; And (e) verifying, by the verifier entity, the signature received from the signer entity using the signer entity's published identification information and a public key, wherein the master key, the first secret key, and A trapdoor generated based on the difficulty of a small integer solution (SIS) problem on a lattice is used to generate the second secret key.

The present invention provides an electronic signature system and method having high safety and efficiency.

Specifically, since the present invention does not use a certificate, there is no certificate management cost and security problem of a certificate-based digital signature system, and there is no need to fully trust an accredited certification authority.

In addition, the present invention is based on the difficulty of the SIS problem on Lattice, which is a difficult mathematical problem even in the worst case, and thus has high safety.

Designed on a Lattice basis, it demonstrates the advantages of computational efficiency, high security, and immunity to quantum computer analysis. Therefore, it has the highest security among certificate-free, that is, certificate-free, digital signature techniques known to date.

1 illustrates a structure of an electronic signature system according to an embodiment of the present invention.

FIG. 2 shows the structure of the system of FIG. 1 from another perspective.

3 illustrates a flow of an electronic method according to an embodiment of the present invention.

4 shows a flow of a system setting method according to an embodiment of the present invention.

Figure 5 shows the flow of a first secret key issuing method according to an embodiment of the present invention.

6 illustrates a flow of a public key and second secret key generation method according to an embodiment of the present invention.

7 shows a flow of a signature method according to an embodiment of the present invention.

8 illustrates a flow of a verification method according to an embodiment of the present invention.

9 is a flow diagram illustrating a trapdoor generation method according to an embodiment of the present invention.

Figure 10 shows the flow of the trapdoor expansion method according to an embodiment of the present invention.

11 illustrates a flow of a Gaussian sampling method according to an embodiment of the present invention.

DETAILED DESCRIPTION Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art may easily implement the present invention. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. In the drawings, parts irrelevant to the description are omitted in order to clearly describe the present invention, and like reference numerals designate like parts throughout the specification.

Throughout the specification, when a part is "connected" to another part, this includes not only "directly connected" but also "electrically connected" with another element in between. . In addition, when a part is said to "include" a certain component, which means that it may further include other components, except to exclude other components unless otherwise stated.

As mentioned above, the certificate-free digital signature system, which is certificate-free, solves the problem of a high cost of maintaining and managing the certificates of the conventional certificate-based digital signature system and the occurrence of certificate-related accidents such as leakage or manipulation. It was.

So far, these certificate-free digital signature systems have been designed based on factoring, discrete algebra, and pairing. However, these problems, which were difficult to solve and considered safe, cannot be guaranteed anymore due to the recent development of quantum algorithms.

Accordingly, there is a growing interest in lattice-based cryptographic systems that are known to be resistant to quantum analysis.

Conventional Lattice-based cryptosystems have had many problems due to lack of security proofs, but recently, Lattice-based cryptosystems have been introduced based on worst-case problems. In view of the fact that existing cryptosystems are designed based on average-case problems, we can see that they provide very high security.

In addition, Lattice-based cryptographic systems are very efficient compared to conventional techniques. The computational complexity of factoring, discrete algebra, pairing, etc.

However, the computational complexity in Lattice

to be.

Accordingly, the present invention is to provide a certificate-free electronic signature technology that can prove the safety in a lattice environment.

1 and 2 illustrate a structure of an electronic signature system according to an embodiment of the present invention.

The electronic signature system 10 according to an embodiment of the present invention includes an object such as a user and a master (M) including a signer (X), a verifier (Y), and a third party (Z) connected through a network. entity) participates.

Among the users, the signer (X) is an entity that signs a message and sends it to the verifier (Y), and the verifier (Y) is an entity that verifies the signature received from the signer (X). At this time, the verification is to confirm that the received signature is a valid signature generated by the signer X as described above.

A third party (Z), a user other than the signer (X) that generated and sent the signature and the verifier (Y) that received the signature, cannot verify the signature.

Only one signer (X), validator (Y), and third party (Z) entity is shown in the figure, and they are shown as if they are different entities. However, signers (X), verifiers (Y), and third parties (Z) are all user entities, and their roles are not fixed, and there is no limit to the number of user entities participating in the electronic signature system 10. It will be easy to understand. In addition, each of these user entities may mean an entity such as a device or software used by the user. Since this is a commonly used concept, an explicit description thereof is omitted herein. For example, in the following description, a user may refer to a user entity such as a signer (X), a verifier (Y), a third party (Z), and the like.

As described above, in the electronic signature system 10 according to an embodiment of the present invention, a master (M) entity that generates and distributes a first private key of each user participates. In this case, the master (M) may be called various names such as a key generation center and a certification authority, and is used as a general term for agencies that manage the digital signature system 10 to operate smoothly. It was.

In the conventional public key based environment, as described above, the master (M) should issue a public certificate to each user, but the electronic signature system 10 according to an embodiment of the present invention, the master (M) is a user (X) The first secret key is issued to the user (X, Y, Z) by using the public identification information (ID) of Y, Z). Therefore, the electronic signature system 10 does not need to manage the public certificate for both the master M and the users X, Y, and Z, so that the electronic signature system 10 has high efficiency and safety. This is because the electronic signature system 10 has no cost or load due to the management of the public certificate, and there is no security risk such as public certificate theft. In addition, as will be described later, the electronic signature system 10 further generates stability because the users X, Y, and Z generate themselves a second secret key, which is another secret key not exposed to the master M.

Unlike the conventional public certificate is not used, the electronic signature system 10 according to an embodiment of the present invention is a public key based method.

The public key-based scheme generates a pair of keys corresponding to each other so that the double public key is used for encryption or signature verification, and the secret key is an asymmetric encryption or signature scheme for decryption or signature.

Since the public key-based method is used to prove who sent the message, when signing a message, the private key is signed and the corresponding public key is verified. In other words, the secret key functions like a stamp on a document.

On the other hand, as described above, encryption and digital signature systems are built on mathematical challenges that are difficult to solve without specific information. The electronic signature system 10 according to an embodiment of the present invention is based on the difficulty of a small integer solution (SIS) problem and a learning with errors (LWE) problem in a lattice.

Difficult to solve without specific information means that the operation is one-way. Unidirectionality is easy, but it is difficult to find the inverse of the calculation. However, if you have certain information, you can easily find the inverse. This specific information is called a trapdoor.

For example, in public key-based environments, cryptographic operations are easy to encrypt. However, if there is no decryption key corresponding to the encryption key used for encryption, decryption, which is an inverse transformation of encryption, is performed using a very difficult one-way operation. That is, the decryption key corresponding to the encryption key used at the time of encryption is a trapdoor. Once the message has been encrypted, the encryption key may be disclosed even if the encryption key exists, so that it can be decrypted. On the other hand, trapdoors or decryption keys should not be disclosed. Therefore, in the public key based environment, the information used to generate the trapdoor is disclosed as the public key, and the trapdoor is not disclosed as the secret key.

The LSIS-based SIS problem and the LWE problem are mathematical problems that are difficult to solve in the worst case as described above. Therefore, many attempts have been made to apply them to encryption and digital signature systems. Lattice is the collection of all points created through the linear combination of two basis in space. If you don't know the basis, even if the third party (Z) finds a point, it is very difficult to find out where the nearest lattice point is. In addition, the third party (Z) has the advantage that it is very difficult to find a lattice point within a certain length without knowing the basis.

Accordingly, the electronic signature system 10 according to an embodiment of the present invention generates a first private key by using the public identification information of its master key and the user entity (X, Y, Z) to generate the user entity (X). It includes the master object (M) to assign to, Y, Z). The electronic signature system 10 also includes a user entity (X, Y, Z) for generating its public key and second secret key. And the electronic signature system 10, the user object (X, Y, Z) is a signer for transmitting to the verifier entity (Y) a signature generated using its public key, the first secret key, and the second secret key And a verifier entity (Y) that verifies the signature received from the entity (X) and the signer entity (X) using the public identification information of the signer entity (X), and the public key. In this case, a trapdoor generated based on a difficulty of a small integer solution (SIS) problem on a lattice is used to generate a master key, a first secret key, and a second secret key.

As illustrated in FIG. 2, a library L including a trapdoor generator L100, a trapdoor expansion unit L200, and a sampling unit L300 may be connected to or included therein. At this time, the trapdoor generator L100 is a trap that is a short basis of the lattice generated from an arbitrary matrix selected from the master (M) and each user (A, B, C) uniform distribution (uniform distribution) You can create a door. In addition, the trapdoor extension L200 may extend the lattice of the trapdoor to another lattice and generate an extended trapdoor that is a short base of another lattice. The sampling unit L300 may sample the vector from the trapdoor extension L200 and the Gaussian distribution of the trapdoor.

In other words, the library L is based on the difficulty of the SIS problem on the lattice, each object (M) of the electronic signature system 10 in accordance with an embodiment of the present invention provides the basic functions for creating, extending, and using trapdoors. , X, Y, Z).

The operations performed by the trapdoor generator L100, the trapdoor extension L200, and the sampling unit L300 are illustrated in FIGS. 9 through 11.

The system setting unit 100 of the master M sets security parameters, selects a series of hash functions, and uses a trap door generated by using the trap door generation unit L100 as a master key which is its secret key. . The system setting unit 100 also publishes the corresponding matrix generated together with the hash function.

The key issuer 200 of the master uses the trapdoor extension L200 to issue an extended trapdoor generated from the user's public identification information as the first secret key of the user.

The user's key generation unit 300 uses the trapdoor generated using the trapdoor generation unit L100 as its second secret key, and uses the generated corresponding matrix as its own public key.

Therefore, as described above, since the user's second secret key is generated by the user independently of the master M at all, the electronic signature system 10 according to the embodiment of the present invention trusts the master M entirely. It has the advantage of not having to.

Among the users, the signer (X) uses the signing unit 400 to generate a first signature using its first private key and public key, and a second signature using its second private and public key. do. In addition, the signer X generates a signature using the first signature and the second signature, and at this time, the trapdoor generator L100, the trapdoor extension L200, and the sampling unit L300 are used.

The signer X samples the vector from the Gaussian distribution of the first secret key to generate a first signature, and extends the lattice of the second secret key into an extended lattice using the public key. The signer X generates an extended trapdoor, which is a short basis of the extended lattice, and samples a vector from the Gaussian distribution of the extended trapdoor to generate a second signature.

The verifier Y of the user verifies the first signature and the second signature by using the verifier 500 and the public identification information of the signer X, and the public key. Also, verifier Y accepts the signature received when it is determined that both the first signature and the second signature are legitimate signatures, and otherwise rejects it.

Thus, each entity of the electronic signature system 10 according to an embodiment of the present invention has the same keys as shown in the keystore associated with each entity of FIG.

The master M has a master key msk, which is a secret key that should not be disclosed to the outside. While the corresponding matrix is a public parameter with hash functions

Published as.

Identification information and public key of each user (X, Y, Z) are also disclosed. On the other hand, the first and second secret keys of each user X, Y, and Z are not disclosed.

The master entity M sets security parameters and generates its own master key (S100).

The master object M generates a first secret key based on the publicly identified identification information of the user object X, Y, Z, including the signer object X and the verifier object Y, thereby generating the user object X. , Y, Z) (S200).

The user entity (X, Y, Z) generates its own public key and second secret key (S300).

The signer entity X transmits the signature generated using its public key, the first secret key, and the second secret key to the verifier entity Y (S400).

The verifier entity Y verifies the signature received from the signer entity X using the public identification information and the public key of the signer entity X (S500).

Hereinafter, each step will be described in more detail with reference to FIGS. 4 to 8.

The master M selects a hash function (S110).

The system setting method generates a matrix A and a corresponding trapdoor by using the trapdoor generator L100 (S120). The trapdoor is a short basis of lattice generated based on matrix A.

The system setting method outputs the matrix A and the hash function as public parameters (S130).

The generated trapdoor is used as a master key (S140).

In other words, the system setting step (S100) is a step of determining a master key of the master (M), which is an institution that issues various keys and issues keys for use in the system.

First, we choose a collision-resistant hash function that satisfies the following properties:

And the master (M)

To create a public parameter

And master key

Determine.

5 shows a flow of a first secret key issuing method according to an embodiment of the present invention.

The master M receives a user ID (S210).

The matrix B is calculated by hashing the user ID (S220).

Using the trapdoor extension L200, the master key is extended based on the matrix B (S230).

The extended master key is transmitted to the user (X, Y, Z) as the first secret key for the ID (S240).

In other words, the first private key issuing step S200 is a step in which the master M issues a first private key for a given using its master key.

Master (M) is

, And

After running the algorithm,

of

Set as the primary private key for, and in a secure way

Pass the key to the signer.

6 illustrates a flow of a method for generating a public key and a second secret key according to an embodiment of the present invention.

As will be described later, the users X, Y, and Z generate their public and second secret keys completely independent of the master M. Therefore, as described above, the users X, Y, and Z do not have to trust the master M entirely, and since the second secret key is not known to the master M, the electronic signature method according to an embodiment of the present invention is safe. This is high.

The users X, Y, and Z generate the matrix C and the corresponding trapdoors by using the trapdoor generator L100 (S310). The trapdoor is a short basis of lattice generated based on matrix C.

The matrix C is used as its public key (S320).

The generated trap door is used as a second secret key (S330).

In other words, the public key and the second secret key generation step (S300)

The user X, Y, and Z corresponding to the step of generating their own public key and second secret key.

User (X, Y, Z)

After running the algorithm,

Own

As the public key for

To

Output as the second secret key for.

Note that, as described above, the master M can directly know the first secret key of the user X, Y, and Z, but the second secret key is generated by the user X, Y, and Z. Because I can not know. Therefore, even if the master M does not know the second secret key, the signature of the signer X cannot be generated. As such, the certificate-free electronic signature system 10 according to an embodiment of the present invention has an advantage of not having to trust the master M entirely.

7 illustrates a flow of a signature method according to an embodiment of the present invention.

The signer X receives the message m (S410).

A first signature is generated from its private key using the sampling unit L300 (S420). At this time, the hash value of the public key along with the message and arbitrary string is used.

The second secret key is expanded using the trapdoor expansion unit L200 (S440).

A second signature is generated from its extended second secret key using the sampling unit L300 (S450). The value that hashes the message with another random string is used.

A signature is generated using the first signature and the second signature (S460).

The generated signature is sent to the verifier Y (S470).

In other words, the signing step (S400)

Signer (X) corresponding to his first private key

And the second secret key

Generating a signature for a given message using. Signer (X) is the message

Create a signature for

first,

Calculate here

Is any string chosen by the signer (X) and is a parameter

Is

This parameter is used for algorithm.

After that,

By calculating its own second secret key

Using

After running the algorithm,

Using

Calculate here

Is also an arbitrary string chosen by the signer (X), with the same parameters

Use

Finally, the electronic signature

It consists of.

8 shows a flow of a verification method according to an embodiment of the present invention.

The verifier Y receives the signature of the signer X (S510).

It is determined whether the predetermined condition as shown for the first signature is satisfied using the signer's ID and the public key (S520).

It is determined whether the predetermined condition as shown for the first signature is satisfied using the signer's ID and the public key (S530).

If both the first signature condition and the second signature condition are satisfied, the signature is verified, and if none is satisfied, the signature is rejected (S540).

In other words, the verification step S500 is a step in which the verifier Y verifies the signature sent by the signer X corresponding to the ID.

Given signature

Is justified when the following conditions are met:

And

9 through 11 illustrate a method of generating, extending, and sampling a trapdoor based on the difficulty of an SIS problem on a lattice for use in issuing and signing a key according to an electronic signature method according to an embodiment of the present invention. It demonstrates concretely.

The present invention

We use a full-rank integer lattice of dimensions, which has a finite index

Is a discrete additive subgroup of. That is, a quoted group

This is finite.

One lattice

silver

Linear independent basis vectors

Is defined equal to the set of all integer linear combinations.

here

In this case, there are a number of bases that produce the same lattice.

The present invention uses the following specific forms of integer lattice. here

and

Is an integer, dimension

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

Suppose it is nested into functions of. here

Dimensional hard lattice is a parity check matrix

It is created by and defined as

which

For the parity check matrix

The coset generated by is defined as follows.

Any fixed constant

And what

Uniformly random

Column vector of the

All of the tops (

Except for probability). Therefore, the present invention is equally random

Use

The problem of hard lattice (short integer solution) on which the present invention is based belongs to the average-case hardness problems, and Miklos Ajtai describes this problem as the worst-case hardness problems. I've found a way to connect.

Lattice's SIS problem is (

norm)

The question is what

Equally random matrix for

Take as input

Wow

(In other words,

Nonzero integer vector satisfying

It is defined as finding.

9 is a flowchart illustrating a trapdoor generation method according to an embodiment of the present invention.

The security parameter is input (SL110).

An arbitrary matrix is selected from the uniform distribution (SL120).

A lattice is generated from the matrix (SL130).

Calculate the short basis of lattice (SL140).

The calculated short basis is outputted along with the matrix as a trapdoor (SL150).

In other words, the trapdoor generator L100 is a matrix randomly selected from the uniform distribution.

And the lattice generated from these matrices

Short basis of

Algorithm to generate

To provide.

The problem of finding a short basis for random lattice ends up

Algorithm because it's a problem

Is a random lattice and its trapdoor (

That is, a short basis.

Where the parameters

Satisfied

The length of

As short as

10 is a flowchart illustrating a trapdoor expansion method according to an embodiment of the present invention.

The matrix representing the lattice, that is, the matrix generating the lattice and the short basis of the lattice are input (SL210).

An arbitrary matrix is selected from the uniform distribution (SL220).

An extended lattice is generated (SL230).

The short basis of the expanded lattice is calculated (SL240).

The calculated short basis is output to the extended trapdoor (SL250).

In other words, the trapdoor extension L200 provides an algorithm that delegates the short basis of Lattice.

Lattice

And its short basis

,

As an input

Is the output as a lattice

And its short basis

Outputs

A short basis of lattice, a sampling input value, and a sampling parameter are input (SL310).

A Gaussian distribution is generated (SL320).

The vector is sampled from the distribution (SL330).

The vector is output (SL340).

In other words, the sampling unit L300 provides an algorithm for sampling the vector from the Gaussian distribution of the lattice.

which

And dimensions

For the Gaussian function

Is

Is defined.

For any corset, a discrete Gaussian distribution (zero center) on the corset

Is each

in

Has a probability proportional to

The properties related to Gaussian distribution in Lattice are as follows. From here

Which

For

The basis of

to be.

Accordingly

silver

With statistical distance

Sampling can be done from

As mentioned above, Gaussian sampling is used by the signer X to extract a lattice vector to use for signing from its private key, i. E. The extended trapdoor.

One embodiment of the present invention may also be implemented in the form of a recording medium including instructions executable by a computer, such as a program module executed by the computer. Computer readable media can be any available media that can be accessed by a computer and includes both volatile and nonvolatile media, removable and non-removable media. In addition, computer readable media may include both computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Communication media typically includes computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave, or other transmission mechanism, and includes any information delivery media.

Although the methods and systems of the present invention have been described in connection with specific embodiments, some or all of their components or operations may be implemented using a computer system having a general purpose hardware architecture. Referring to one example of a computer system architecture that may be used to perform one or more components or operations of one embodiment of the present invention, a hardware system includes a processor, cache, memory, and one or more software applications and drivers related to the functions described above. can do.

The foregoing description of the present invention is intended for illustration, and it will be understood by those skilled in the art that the present invention may be easily modified in other specific forms without changing the technical spirit or essential features of the present invention. will be. Therefore, it should be understood that the embodiments described above are exemplary in all respects and not restrictive. For example, each component described as a single type may be implemented in a distributed manner, and similarly, components described as distributed may be implemented in a combined form.

The scope of the present invention is shown by the following claims rather than the above description, and all changes or modifications derived from the meaning and scope of the claims and their equivalents should be construed as being included in the scope of the present invention. do.

Claims

In an electronic signature system,

A master entity for generating and assigning a first secret key to the user entity, using its master key and publicly identified identification information of the user entity; And

Including a user object for generating its own public key and second private key;

The user object

A signer entity for transmitting a signature generated using the public key, the first secret key, and the second secret key to a verifier entity; And

And a verifier entity that verifies the signature received from the signer entity using the public identification information of the signer entity and a public key.

And a trapdoor generated based on difficulty of a small integer solution (SIS) problem on a lattice for generating the master key, the first secret key, and the second secret key.
The method of claim 1,

The master entity

By creating a trapdoor that is a short basis of lattice generated from any matrix selected in a uniform distribution,

And use the trapdoor as its master key, which is its secret key, and disclose the arbitrary matrix.
The method of claim 1,

Extend the lattice of the master key to the extended lattice using the publicly identified identification of the user entity and create an extended trapdoor that is a short basis of the extended lattice,

Electronic signature system for issuing the extended trapdoor with a first private key of the user entity.
The method of claim 1,

The user object

Create a trapdoor, a short base of lattice generated from a random matrix chosen from a uniform distribution,

And use the trapdoor as its second secret key and use the arbitrary matrix as its public key.
The method of claim 1,

The user object

Generate a first signature using its first private key and public key,

Generate a second signature using its second private key and public key,

And generate the signature using the first signature and the second signature.
The method of claim 5,

The user object

And generate a first signature by sampling a vector from a Gaussian distribution of the first secret key.
The method of claim 5,

The user object

Expand the lattice of the second secret key into an extended lattice using the public key and generate an extended trapdoor that is a short basis of the extended lattice,

And generate a second signature by sampling a vector from a Gaussian distribution of the extended trapdoor.
In the digital signature method,

(a) the master entity setting security parameters and generating its master key;

(b) the master entity generating and assigning a first private key to the user entity based on the publicly identified identification information of the user entity including a signer entity and a verifier entity;

(c) the user entity generating its public key and second private key;

(d) sending a signature generated by the signer entity using its public key, first secret key, and second secret key to the verifier entity; And

(e) verifying, by the verifier entity, the signature received from the signer entity using the publicly identifying information of the signer entity, and a public key;

And a trapdoor generated based on a difficulty of a small integer solution (SIS) problem on a lattice for generating the master key, the first secret key, and the second secret key.
The method of claim 8,

Step (a) is

By creating a trapdoor that is a short basis of lattice generated from any matrix selected in a uniform distribution,

Using the trapdoor as a master key, which is the secret key of the master entity, and wherein the arbitrary matrix is public.
The method of claim 8,

Step (b) is

Extend the lattice of the master key to the extended lattice using the publicly identified identification of the user entity and create an extended trapdoor that is a short basis of the extended lattice,

Electronic signature method for issuing the extended trapdoor with a first private key of the user entity.
The method of claim 8,

Step (c) is

Create a trapdoor, a short basis of lattice, generated from a random matrix chosen from a uniform distribution

Using the trapdoor as the second private key of the user entity and using the arbitrary matrix as the public key of the user entity.
The method of claim 8,

Step (d)

Generate a first signature by sampling a vector from a Gaussian distribution of the first private key using the first private key and the public key of the signer entity,

Using the second private key and the public key of the signer entity, expand the lattice of the second private key into an extended lattice using the public key and create an extended trapdoor that is a short basis of the expanded lattice Generating a second signature by sampling a vector from a Gaussian distribution of the extended trapdoor;

Electronic signature method for generating the signature using the first signature and the second signature.