JP6139469B2 - Signature generation device, signature verification device, verification system, and program - Google Patents

Description

  The present invention relates to signature technology, and in particular, to a tagged disposable signature technology.

  Tagged One-Time Signature (TOS) method is a type of One-Time Signature (OTS) method, and it is a signature for a message based on a private key and a disposable public key called "tag". Is generated, and signature verification is performed using a public key, a tag, and a message corresponding to the secret key (see, for example, Non-Patent Document 1). Unlike the normal OTS method (see, for example, Non-Patent Document 2), the TOS method is highly convenient in that it does not require storing a disposable private key for generating a signature.

Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions,” ASI-ACRYPT 2012, 4-24. Payman Mohassel, “One-Time Signatures and Chameleon Hash Functions,” Selected Areas in Cryptography 2010, 302-319.

  However, the TOS method described in Non-Patent Document 1 is a method having safety (computational security) based on the computational assumption on the pairing group, and when the quantum computer is realized, the safety is Lost.

  An object of the present invention is to provide a single-use signature scheme with a tag based on a problem on a lattice that is considered to be able to maintain its security even if it is realized by a quantum computer.

At the time of signature generation, using the selected n _0- dimensional vector z ₀ , the selected m _1- dimensional vector σ ₁ , and the k _1- dimensional vector M ₁ corresponding to the message, A ₁ M ₁ + B ₁ σ ₁ is obtained. Obtain k _0- dimensional vector z ₁ corresponding to the included information, obtain m _0- dimensional vector σ ₀ satisfying z ₀ = A ₀ z ₁ + B ₀ σ ₀ , and output a signature including vectors σ ₀ and σ ₁ . However, n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ are integers of 1 or more, A ₀ is a row example of n ₀ rows and k ₀ columns, and B ₀ is a row example of n ₀ rows and m ₀ columns. , A ₁ is a row example of n ₁ row k ₁ column, and B ₁ is a row example of n ₁ row m ₁ column.

At the time of signature verification, vectors M ₁ , σ ₀ , σ ₁ , z ₀ are used to obtain a k _0- dimensional vector z ₁ corresponding to information including A ₁ M ₁ + B ₁ σ ₁ , and z ₀ = A ₀ z ₁ It is determined whether the verification condition that satisfies the requirement of satisfying + B ₀ σ ₀ is satisfied.

  In the present invention, it is possible to realize a tagged disposable signature system based on a problem on a lattice.

FIG. 1 is a block diagram for illustrating a functional configuration of the signature system according to the embodiment. FIG. 2 is a block diagram for illustrating a functional configuration of the key generation apparatus according to the embodiment. FIG. 3A is a block diagram for illustrating a functional configuration of the signature generation apparatus according to the embodiment. FIG. 3B is a block diagram for illustrating a functional configuration of the signature verification apparatus according to the embodiment. FIG. 4A is a flowchart for illustrating the key generation method of the embodiment. FIG. 4B is a flowchart for illustrating the signature generation method according to the embodiment. FIG. 4C is a flowchart for illustrating the signature verification method according to the embodiment. 5A to 5C are diagrams for illustrating the data configuration of the embodiment. 6A to 6C are diagrams for illustrating the data configuration of the embodiment. FIG. 7A to FIG. 7C are diagrams for illustrating the data configuration of the embodiment.

Embodiments of the present invention will be described below.
[Definition]
Terms used in the embodiments are defined.
<SIS (Small Integer Solution) problem>
The SIS problem is a kind of lattice problem that is difficult to solve, and is used as a basis for the security of cryptographic primitives (for example, see Reference 1). In summary, the SIS problem is for a matrix B of n rows and m columns (where n and m are integers of 1 or more, for example, integers of 2 or more) on the prime field Z _q (where q is a prime number). , A problem of obtaining a small m-dimensional vector r with Br = 0. Small vector means that the norm is less than some achievable small positive value s. For example, a vector whose elements are almost 0 or 1 can be said to be a small vector. For example, the SIS problem, uniform random _{Z q} consists of the original n rows and m columns of the matrix B∈Z _q ^{n × m} (although, m is obtained by a polynomial of n) to the following equation (1 ) And (2) to obtain an m-dimensional vector rεΛ ^⊥ (B) consisting of elements of the integer set Z.
Λ ^⊥ (B) = {rεZ ^m : Br = 0εZ _q ⁿ } ⊆Z ^m (1)
| R | ₂ ≦ s (2)
However, | r | ₂ represents the Euclidean norm of r.
[Reference 1] David Cash, Dennis Hofheinz, Eike Kiltz, Chris Perkest, “Bonsai, Trees, or How to Delegate a Lattice Basis,” Advances in Cryptology-EUROCRYPT 2010, Lecture Notes in Computer Science Volume 6110, 2010, 523- 552.

<Algorithms GenBasis and SampleD>
According to References 1 and 2, the following algorithms GenBasis and SampleD exist.
[Reference 2] C. Gentry, C. Peikert, and V. Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” In STOC, pages 197-206. 2008.

The algorithm GenBasis takes n, m, and q as inputs, and generates and outputs a set (S, B) of a basis vector SεZ ^m and a matrix BεZ _q ^{n × m} ((S, B) ← GenBasis (N, m, q)). However, the base vector S is any base that forms a subset (partial vector space) Λ ^⊥ (B) for the matrix B, and functions as a trap door.

The algorithm SampleD takes S, B, y, and s as inputs, and obtains a discrete Gaussian distribution of an m-dimensional vector x∈Λ _y ^⊥ (B) consisting of elements of an integer set Z that satisfies the following equations (3) and (4): (Discrete Gaussian Distribution) D (Λ _y ^⊥ (B), s) is selected and output (x ← SampleD (S, B, y, s)).
Λ _y ^⊥ (B) = {x∈Z ^m : Bx = y} (3)
| X | ₂ ≦ s (4)
However, yεZ _q ⁿ is a random n-dimensional vector having elements of Z _q as elements. The discrete Gaussian distribution D (Λ _y ^⊥ (B), s) means that the probability for each vector x∈Λ _y ^⊥ (B) is Gaussian distribution ρ _s (x) = exp (−π | x | ² / s ² ) Is a probability distribution in which the probability for other vectors is zero. Note that | x | ² represents the norm of x. If there is no basis vector S that functions as a trapdoor, it is difficult to obtain such a vector x.

<Chameleon hash function based on difficulty of SIS problem>
In Reference 1, a chameleon hash is constructed based on the difficulty of the SIS problem. This will be described below.
The safety parameters are k, n, m, and s. However, k is an integer greater than or equal to 1 (for example, an integer greater than or equal to 2). First, (S, B) ← GenBasis (n, m, q) is calculated, and a matrix A∈Z _q ^{n × k} on Z _{q of} n rows and k columns is selected at random. (A, B) is disclosed as a hash key, and S is secretly held as a trapdoor. Message is a bit string of k bits, the respective bits assigned to the value 0 on _{Z q,} expressed in row vector of k _{Z q} elements (M∈Z _q ^k). Let D (Z ^m , s) be a Gaussian distribution on Z ^m limited by s. D (Z ^m , s) means a Gaussian distribution in which the probability for each vector rεZ ^m is proportional to the distribution ρ _s (r) = exp (−π | r | ² / s ² ). To hash the message M, select the m-row vector rεZ ^m on Z _p according to the distribution D (Z ^m , s), calculate Hash (m, r) = AM + BrεZ ⁿ , and its output Let n-dimensional vector Hash (m, r) εZ ⁿ be a hash value h. For an arbitrary hash value h and an arbitrary message M′∈Z _q ^k , a vector r′∈Z ⁿ such that h = AM ′ + Br ′ is obtained by using a basis vector S as a trapdoor, r ′ = SampleD ( S, B, h-AM ′, s). On the other hand, if S is not known, finding such r ′ is difficult because it results in solving the SIS problem.

[First Embodiment]
Next, a first embodiment will be described.
<Configuration>
As illustrated in FIG. 1, the signature system 1 of this embodiment includes a key generation device 11, a signature generation device 12, and a signature verification device 13, which are configured to be communicable through a network such as the Internet. Yes. As illustrated in FIG. 2, the key generation device 11 of this embodiment includes a base generation unit 111, a matrix generation unit 112, a key configuration unit 113, an output unit 114, and a control unit 119. As illustrated in FIG. 3A, the signature generation apparatus 12 according to the present exemplary embodiment includes an input unit 121, a storage unit 122, a selection unit 123, calculation units 124 and 126, a tag selection unit 125, an output unit 127, and a control unit 129. . As illustrated in FIG. 3B, the signature verification apparatus 13 according to the present exemplary embodiment includes an input unit 131, a storage unit 132, a calculation unit 134, a determination unit 136, and a control unit 139. The key generation device 11, signature generation device 12, and signature verification device 13 execute each process under the control of the control units 119, 129, and 139, respectively. Each of the key generation device 11, the signature generation device 12, and the signature verification device 13 includes, for example, a processor (hardware processor) such as a central processing unit (CPU), a random-access memory (RAM), a read-only ROM (ROM). a general-purpose or dedicated computer having a memory such as a memory) executes a predetermined program. This program may be installed in a computer, or may be recorded in a ROM or the like in advance. In addition, some or all of the processing units may be configured using an electronic circuit that realizes a processing function independently instead of an electronic circuit (circuitry) that realizes a functional configuration by reading a program like a CPU. .

<Key generation process>
The key generation process will be described. It is assumed that safety parameters n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ , s, q are set in advance. However, n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , and m ₁ are integers of 1 or more. For example, these are integers of 2 or more. s is a positive value and q is a prime number. _Further, the _Z ^{q n1} → ^{{0,1} k0} consisting function T that maps the original ^{Z q n1} to _{k 0-dimensional} vector of _{k 0} amino {0, 1} ∈ Z _q is set . However, the superscripts “n1” and “k0” represent “n ₁ ” and “k ₀ ”, respectively. The function T is a function having target collision difficulty. Although the structure of the function T is not limited, for example, a hash function that is difficult to collide with the target can be used as T.

The key generation device 11 (FIG. 2) includes a key generation function TOS. The key (n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ , s) is executed to generate a key pair (sk, pk) of the public key pk and the secret key sk. First, as illustrated in FIG. 4A, the base generation unit 111 of the key generation device 11 receives (S ₀ , B ₀ ) ← GenBasis (n ₀ , m ₀ , q) with n ₀ , m ₀ , q as inputs. calculate. B ₀ εZ _q ^{n0 × m0} is a row example of n ₀ rows and m ₀ columns. However, the superscripts “n0” and “m0” represent “n ₀ ” and “m ₀ ”, respectively. S ₀ ∈Z ^m0 is a trap door which is secret information corresponding to the example B ₀ . As described above, the trap door _{S 0} is either _B 0 _r 0 = 0 vector _{r 0} of _{m 0} dimensional satisfying spanned a subset belonging (partial vector space) _{m 0-dimensional} basis vectors. (S ₀ , B ₀ ) is sent to the key construction unit 113 (step S111).

The matrix generation unit 112 includes a row example A ₀ εZ _q ^{n0 × k0 of} n ₀ rows and k ₀ columns, a row example A ₁ εZ _q ^{n1 × k1 of} n ₁ rows k ₁ columns, and n ₁ rows m ₁ columns. Row example B ₁ εZ _q ^{n1 × m1} is selected at random. A ₀ , A ₁ , B ₁ are sent to the key construction unit 113 (step S112).

The key configuration unit 113 receives S ₀ , B ₀ , A ₀ , A ₁ , B ₁ as input, and public key pk = (A ₀ , B ₀ , A ₁ , B ₁ , T, s) and secret key sk = Configure (S ₀ ) and output. The key pair (sk, pk) of the public key pk and the secret key sk is sent to the output unit 114 (step S113).

  The output unit 114 transmits the public key pk to the signature generation device 12 (FIG. 3A) and the signature verification device 13 (FIG. 3B). The public key pk is input to the input unit 121 of the signature generation device 12 and the input unit 131 of the signature verification device 13 and stored in the storage unit 122 and the storage unit 132. The private key sk is securely sent to the signature generation device 12, input to the input unit 121 of the signature generation device 12, and stored securely in the storage unit 122. The secret key sk is secret information (step S114).

<Signature generation processing>
The signature generation process will be described. As illustrated in FIG. 4B, first, a k _1- dimensional vector M ₁ εZ _q ^k1 corresponding to the message msg is input to the input unit 121 of the signature generation device 12 (FIG. 3A). The vector M ₁ is a row vector composed of k ₁ elements {0, 1} εZ _q ^k1 . Vector _{M 1} is stored in the storage unit 122 (step S121).

The tag selection unit 125 receives the public key pk, executes a tag generation function TOS.Tag (pk), randomly selects an n ₀ -dimensional vector z ₀ ∈Z _q ^n0, and outputs this as a tag z ₀ . . Tag z ₀ is newly selected each time the signature generation process. However, the tag selection unit 125 may set a vector generated randomly every time the signature generation process is performed as the tag z ₀ , or each time the signature generation process is performed from an n _0- dimensional vector generated in advance at random. The tag z ₀ may be selected. The selected tag z ₀ is sent to the calculation unit 126 and the output unit 127 (step S125).

The selection unit 123 and the calculation units 124 and 126 include a signature generation function TOS. Sign (sk, M ₁ , z ₀ ) is executed to generate a signature σ. The selection unit 123 selects and outputs an m _1- dimensional vector σ ₁ ∈Z _q ^m1 according to a Gaussian distribution D (Z ^m1 , s) (a distribution in which m = m ₁ in the above-described D (Z ^m , s)). To do. That is, the elements of the vector σ ₁ are selected according to a Gaussian distribution. The vector σ ₁ is newly selected for each signature generation process. However, the selection unit 123 may generate the vector σ ₁ according to the Gaussian distribution D (Z ^m1 , s) every time the signature generation process is performed, or generate a plurality of vectors according to the Gaussian distribution D (Z ^m1 , s) in advance. However, the vector σ ₁ may be selected from the m _one- dimensional vector for each signature generation process. The selected vector σ ₁ is sent to the calculation unit 124 and the output unit 127 (step S123).

The calculation unit 124 receives the public key pk read from the storage unit 122 and the vector σ ₁ sent from the selection unit 123 as input, and the n _one- dimensional vector h ₁ = A ₁ M ₁ + B ₁ σ ₁ εZ _q ⁿ¹ Obtain a k ₀ -dimensional vector z ₁ corresponding to the information containing (FIG. 5A). In this embodiment, the calculation unit 124 inputs the n _1- dimensional vector h ₁ to the function T, obtains and outputs the k _0- dimensional vector z ₁ = T (h ₁ ) (FIG. 5B). Vector _{z 1} is sent to the arithmetic unit 126 (step S124).

The calculation unit 126 receives the public key sk and secret key sk read from the storage unit 122, the tag z ₀ sent from the tag selection unit 125, and the vector z ₁ sent from the calculation unit 124, and z ₀ = A Obtain an m ₀ -dimensional vector σ ₀ ∈Z _q ^m0 that satisfies ₀ z ₁ + B ₀ σ ₀ (FIG. 6A). The calculation unit 126 of the present embodiment extracts a base vector S ₀ that is a trap door from the secret key sk, extracts A ₀ and B ₀ from the public key pk, and obtains z ₀ −A ₀ z ₁ (FIG. 6B). Thus, the m ₀ -dimensional vector σ ₀ = SampleD (S ₀ , B ₀ , z ₀ −A ₀ z ₁ , s) εZ _q ^m0 (FIG. 6C) is obtained and output. When tag z ₀ is regarded as a disposable public key, vector σ ₀ is a disposable private key corresponding to tag z ₀ . In this embodiment, the vector σ ₀ corresponding to the disposable secret key can be generated by the algorithm SampleD, and therefore it is not necessary to hold the vector σ ₀ . That is, a disposable signature with a tag can be realized. Further, it is difficult for a person who does not know the basis vector (trap door) S ₀ to obtain the vector σ ₀ , resulting in solving the SIS problem. The vector σ ₀ is sent to the output unit 127 (step S126).

The output unit 127 outputs the tag z ₀ , the signature σ = (σ ₀ , σ ₁ ) including the vectors σ ₀ and σ ₁ , and the vector M ₁ read from the storage unit 122 (step S 127).

<Signature verification processing>
The signature verification process will be described. The signature verification device 13 is configured to receive a signature verification function TOS. Vrf (pk, z ₀ , M ₁ , σ) is executed. As illustrated in FIG. 4C, the tag z ₀ , the signature σ = (σ ₀ , σ ₁ ), and the vector M ₁ are input to the input unit 131 of the signature verification apparatus 13 and stored in the storage unit 132. Note that the tag z ₀ , the signature σ = (σ ₀ , σ ₁ ), and the vector M ₁ input to the input unit 131 are not necessarily generated correctly as described above (step S 131).

The determination unit 136 reads the signature σ = (σ ₀ , σ ₁ ) and the public key pk from the storage unit 132, and determines whether σ ₀ and σ ₁ are in accordance with the Gaussian distribution D (Z ^m1 , s). To do. In this determination, for example, it is determined whether | r | ≦ s is satisfied, and if | r | ≦ s is satisfied, it is determined that σ ₀ and σ ₁ follow the Gaussian distribution D (Z ^m1 , s). To. When it is determined that σ ₀ and σ ₁ do not follow the Gaussian distribution D (Z ^m1 , s), the determination unit 136 outputs “0” indicating a verification failure (step S1360), and the process is performed. finish. On the other hand, if it is determined that σ ₀ and σ ₁ are in accordance with the Gaussian distribution D (Z ^m1 , s), the process proceeds to step S134.

In step S134, the calculation unit 134 reads out the public key pk, the tag z ₀ , the signature σ = (σ ₀ , σ ₁ ), and the vector M ₁ from the storage unit 132, and uses them, and h ₁ = A ₁ M Obtain a k ₀ -dimensional vector z ₁ εZ _q ^k0 corresponding to the information including ₁ + B ₁ σ ₁ (FIG. 5A). In this embodiment, the arithmetic unit 134 inputs the n _1- dimensional vector h ₁ to the function T, obtains and outputs the k _0- dimensional vector z ₁ = T (h ₁ ) (FIG. 5B). Vector _{z 1} is sent to the determination section 136 (step S134).

The determination unit 136 receives the vector z ₁ , the public key pk read out from the storage unit 132, and the vector σ ₀ as input, and determines a verification condition that satisfies the condition that z ₀ = A ₀ z ₁ + B ₀ σ ₀ is satisfied. To do. This determination may be made based on whether (1) z ₀ and A ₀ z ₁ + B ₀ σ ₀ match or (2) a function value of z ₀ and A ₀ z ₁ + B ₀ σ _0. Or (3) whether the function value of z _{0 and} the function value of A ₀ z ₁ + B ₀ σ ₀ satisfy a predetermined relationship. It may be done. Alternatively, it may be determined whether one of the conditions (1) to (3) is satisfied and another condition is satisfied. In other words, any determination may be made as long as the verification condition that satisfies the condition that z ₀ = A ₀ z ₁ + B ₀ σ ₀ is satisfied is determined. If it is determined that the verification condition is not satisfied, the determination unit 136 outputs “0” indicating a verification failure (step S1360) and ends the process. On the other hand, if it is determined that the verification condition is satisfied, the determination unit 136 outputs “1” indicating the verification success (step S 1361) and ends the process.

<Features of this embodiment>
In a general chameleon hash function, in order to obtain a random number such that a message has a certain hash value, the random number (and the original message) used when the hash value is generated is required. Therefore, when configuring a signature system using a hash value as a tag (disposable public key), it becomes necessary to store a random number (disposable secret key) used for the generation. On the other hand, in this embodiment, since the signature system is configured using the chameleon hash function based on the difficulty of the SIS problem, it is not necessary to store such a random number (vector σ ₀ ), only the secret trapdoor and the hash value. From this, a random number (vector σ ₀ ) can be obtained. By using this characteristic, the tag corresponding to the hash value is set as the tag z ₀ , and the trapdoor S ₀ is set as the long-term secret key sk, whereby the tagged disposable signature can be configured. Moreover, since safety is ensured based on the SIS problem which is a kind of problem on the lattice, the safety can be maintained even if the quantum computer is realized.

[Modification of First Embodiment]
In steps S124 and S134 of the first embodiment, an n _1- dimensional vector h ₁ is input to the function T to obtain a k _0- dimensional vector z ₁ = T (h ₁ ) (FIG. 5B). However, other functions may be used as long as the n _1- dimensional vector h ₁ can be mapped to the k _0- dimensional vector z ₁ so that no collision occurs. For _example, to the use of ^{Z q n1} → ^{0,1} in place of ^k0 consisting function ^{_{T Z q n1 + n2 → {}} 0,1} k0 consisting function T '(e.g., a target collision hash functions), _{n 1-dimensional} K ₀ dimensional vector z ₁ = T ′ (h ₁ | w ₁ ) may be obtained with respect to the concatenation h ₁ | w ₁ of vector h ₁ and n ₂ dimensional vector w ₁ (FIG. 5C). An example of w ₁ is public information such as a public key pk. The same w ₁ is used in the calculation unit 124 and the calculation unit 134.

[Second Embodiment]
Next, a second embodiment will be described. This embodiment is a modification of the first embodiment, and has a configuration in which the function T is not used. Below, it demonstrates centering on difference with 1st Embodiment, About the same part as 1st Embodiment, the same reference number as 1st Embodiment is used, and description is abbreviate | omitted.

<Configuration>
As illustrated in FIG. 1, the signature system 2 of this embodiment includes a key generation device 21, a signature generation device 22, and a signature verification device 23. As illustrated in FIG. 2, the key generation device 21 of this embodiment includes a base generation unit 111, a matrix generation unit 212, a key configuration unit 213, an output unit 114, and a control unit 119. As illustrated in FIG. 3A, the signature generation device 22 according to the present exemplary embodiment includes an input unit 121, a storage unit 122, a selection unit 123, calculation units 224 and 126, a tag selection unit 125, an output unit 127, and a control unit 129. . As illustrated in FIG. 3B, the signature verification apparatus 23 according to this embodiment includes an input unit 131, a storage unit 132, a calculation unit 234, a determination unit 136, and a control unit 139.

<Key generation process>
The key generation process of this embodiment is different from the key generation process of the first embodiment in that n ₁ = k ₀ and the function T is not set. As illustrated in FIG. 4A, first, the base generation unit 111 executes step S111, the matrix generation unit 212 executes the process of step S112 with n ₁ = k ₀ (step S212), and the key configuration unit 213 S ₀ , B ₀ , A ₀ , A ₁ , B ₁ are input, and public key pk = (A ₀ , B ₀ , A ₁ , B ₁ , s) and secret key sk = (S ₀ ) are configured. Output (step S213). Thereafter, the output unit 114 performs the process of step S <b> 114, and the public key pk is input to the input unit 121 of the signature generation device 22 and the input unit 131 of the signature verification device 23 and stored in the storage unit 122 and the storage unit 132. . The private key sk is securely sent to the signature generation device 22, input to the input unit 121 of the signature generation device 22, and stored securely in the storage unit 122.

<Signature generation processing>
The signature generation process of this embodiment is obtained by replacing step S124 of the signature generation process of the first embodiment with step S224. Only step S224 will be described. In step S224, the calculation unit 224 receives the public key pk read from the storage unit 122 and the vector σ ₁ sent from the selection unit 123, and inputs n ₁ = k _0- dimensional vector h ₁ = A ₁ M ₁ + B. Obtain a k ₀ -dimensional vector z ₁ corresponding to information including ₁ σ ₁ εZ _q ^k0 (FIG. 7A). Calculation unit 224 of this embodiment outputs the vector _{h 1} of _{k 0-dimensional} as _{z 1} as it is (Figure 7B). Vector _{z 1} is sent to the arithmetic unit 126 (step S224). Others are the same as the first embodiment.

<Signature verification processing>
The signature verification process according to this embodiment is obtained by replacing step S134 of the signature verification process according to the first embodiment with step S234. Only step S234 will be described. In step S234, the calculation unit 234 reads out the public key pk, the tag z ₀ , the signature σ = (σ ₀ , σ ₁ ), and the vector M ₁ from the storage unit 132, and uses them, and h ₁ = A ₁ M Obtain a k ₀ -dimensional vector z ₁ εZ _q ^k0 corresponding to information including ₁ + B ₁ σ ₁ (FIG. 7A). In this embodiment, the calculation unit 234 outputs the k _0- dimensional vector h _{1 as it} is as the vector z ₁ (FIG. 7B). Vector _{z 1} is sent to the determination section 136 (step S234). Others are the same as the first embodiment.

[Modification of Second Embodiment]
In step S224 and S234 of the second _embodiment, and the vector _{h 1} of n 1 = _{k 0-dimensional} as it is a vector _{z 1} (FIG. 7B). However, n ₁ <k ₀ and the connection h ₁ | w ₁ between the n _1- dimensional vector h ₁ and the k ₀ -n _1- dimensional vector w ₁ may be used as it is as the k _0- dimensional vector z ₁ (FIG. 7C). ). An example of w ₁ is public information such as a public key pk. The same w ₁ is used in the calculation unit 224 and the calculation unit 234.

[Other variations]
The present invention is not limited to the embodiment described above. For example, one may use the expanded body obtained by the basic body element Z _q in place of the body Z _q, using the ring Z _q in place of the element Z _q by using a positive integer other than prime numbers q May be. In the above embodiment, the signature generation device sends the signature, the tag, and the information corresponding to the message to the signature verification device at the same time, but these may be sent separately. For example, tags and messages may be published before the signature is sent. If it is clear that σ ₀ and σ ₁ constituting the signature σ = (σ ₀ , σ ₁ ) follow the Gaussian distribution D (Z ^m1 , s), the process of step S1362 is performed. It may be omitted. Further, instead of each device exchanging information via a network, at least a part of the devices may exchange information via a portable recording medium. Alternatively, at least some of the devices may exchange information via a non-portable recording medium. That is, the combination which consists of a part of these apparatuses may be the same apparatus.

  The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. By executing this program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads a program stored in its own recording device and executes a process according to the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and each time the program is transferred from the server computer to the computer. The processing according to the received program may be executed sequentially. The above-described processing may be executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition without transferring a program from the server computer to the computer. Good.

  In the above embodiment, the processing functions of the apparatus are realized by executing a predetermined program on a computer. However, at least a part of these processing functions may be realized by hardware.

1, 2 Signature system 11, 21 Key generation device 12, 22 Signature generation device 13, 23 Signature verification device

Claims (8)

n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ are integers greater than or equal to ₁ , A ₀ is a row example of n ₀ rows and k ₀ columns, B ₀ is a row example of n ₀ rows and m ₀ columns, A ₁ is a row example of n ₁ row k ₁ column, B ₁ is a row example of n ₁ row m ₁ column, a selected n _0- dimensional vector is z ₀ , a selected m _1- dimensional vector is σ ₁ , M ₁ is a k _one- dimensional vector corresponding to the message,
A _first arithmetic unit that obtains a k _0- dimensional vector z ₁ corresponding to information including A ₁ M ₁ + B ₁ σ ₁ ;
a second computing unit for obtaining an m ₀ -dimensional vector σ ₀ satisfying z ₀ = A ₀ z ₁ + B ₀ σ ₀ ;
An output unit for outputting a signature including the vectors σ ₀ and σ ₁ ;
A signature generation device. The signature generation device according to claim 1,
The signature generation device, wherein the second calculation unit obtains the vector σ ₀ by using a trapdoor S ₀ that is secret information corresponding to the row example B ₀ . The signature generation device according to claim 2,
The trapdoor S ₀ is a signature generation device, which is one of m ₀ -dimensional basis vectors spanning a partial vector space to which an m _0- dimensional vector r ₀ satisfying B ₀ r ₀ = 0 belongs. The signature generation device according to any one of claims 1 to 3,
The signature generation device, wherein the information including the A ₁ M ₁ + B ₁ σ ₁ is a k _0- dimensional vector. n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ are integers greater than or equal to ₁ , A ₀ is a row example of n ₀ rows and k ₀ columns, B ₀ is a row example of n ₀ rows and m ₀ columns, A ₁ is a row example of n ₁ row k ₁ column, B ₁ is a matrix of n ₁ row m ₁ column,
_{K 1} dimensional vector _{M 1} corresponding to the message, and, using the _{m 1-dimensional} vector sigma ₁ is the _signature, obtaining A ₁ M 1 + _{B 1} sigma vector _{z 1} of _{k 0-dimensional} corresponding to information containing ₁ An arithmetic unit;
Using at least the vector z ₁ , the input n _0- dimensional vector z ₀ , and the m _0- dimensional vector σ ₀ as a signature, and satisfying z ₀ = A ₀ z ₁ + B ₀ σ ₀ A determination unit that determines whether the verification condition to be satisfied is satisfied;
A signature verification apparatus. The signature verification apparatus according to claim 5, comprising:
The determination unit determines whether the vectors σ ₀ and σ ₁ follow a Gaussian distribution,
The signature verification apparatus, wherein the verification condition further includes that the vectors σ ₀ and σ ₁ are determined to follow a Gaussian distribution. n ₀ , k ₀ , m ₀ , n ₁ , k ₁ , m ₁ are integers greater than or equal to ₁ , A ₀ is a row example of n ₀ rows and k ₀ columns, B ₀ is a row example of n ₀ rows and m ₀ columns, A ₁ is a row example of n ₁ row k ₁ column, and B ₁ is a row example of n ₁ row m ₁ column,
Using the selected n _0- dimensional vector z ₀ , the selected m _1- dimensional vector σ ₁ , and the k _1- dimensional vector M ₁ corresponding to the message, corresponding to information including A ₁ M ₁ + B ₁ σ ₁ a first operation unit _{k 0-dimensional} vector _{z 1} Ru obtained _which, z ₀ = _{a 0} z 1 + _{B 0} and the second arithmetic unit sigma Ru give vector sigma ₀ of _{m 0} D satisfying _0, the vector sigma ₀ And an output unit that outputs a signature including σ ₁ ,
The vector _{M 1, σ 0, σ 1} , with _{z 0,} a third arithmetic unit Ru give A ₁ M ₁ + _{B 1} σ vector _{z 1} of _{k 0-dimensional} corresponding to information containing _{1, z} 0 = A A signature verification apparatus including a determination unit that determines whether a verification condition that satisfies the requirement of satisfying ₀ z ₁ + B ₀ σ ₀ is satisfied;
Having a signature system.   A program for causing a computer to function as the signature generation device according to any one of claims 1 to 4 or the signature verification device according to claim 5 or 6.

Images