JP4738003B2 - Signature system, signing method - Google Patents

Description

  The present invention relates to information security technology, and to a digital signature technology with a threshold.

The digital signature technique with a threshold is an electronic signature that can be confirmed from only the signature so that it is not known who has cooperated in signature generation that the signature has been generated by the cooperation of some of a plurality of participants. An electronic signature method that can confirm from the signature alone that the signature has been generated by the cooperation of arbitrary t or more of the n participants without knowing who has cooperated in the signature generation (t, n) Called threshold electronic signature method. There is a method disclosed in Non-Patent Document 1 as a conventional method. First, symbols used in this description will be described. Let G be a cyclic group that is considered to be difficult to solve the discrete logarithm problem, g be the generation source, and q be the order of the group (G = <g>, # G = q). Z _q is a residue class {0, 1, 2,..., Q−1} modulo q. ∈ _U means that elements are extracted uniformly and randomly, {0, 1} ^* means a bit string in which 0 or 1 are arranged in an arbitrary length, and K means a finite field. H, I, and J are hash functions that are converted as follows: H: {0, 1} ^* → G, I: K → Z _q , J: {0, 1} ^* → K. The method disclosed in Non-Patent Document 1 will be described below.

FIG. 1 shows a configuration example and a flow of an electronic signature system with a threshold. The total number of participants in this system is n, and n participating devices 910-i (i = 1,..., N) use a predetermined element g (gεG) of a cyclic group G. Thus, the secret key sk _i and the public key pk _{i of} each participating device are generated, and the public key pk _i is made public. When creating a signature, any t or more of the n people generate a commitment a _i with the participating devices 910-i (i = 1,..., T), and transmit the commitment a _i to a device including the signature generation unit 920. Here, to simplify the explanation, i = 1,..., T is a number indicating the participating devices that used (cooperated) for signature generation, and i = t + 1,. The number of participating devices that did not cooperate) may be any of the n participating devices.

The signature generation unit 920 may be an independent device, or may be provided in any participating device. The signature generation unit 920 generates a dummy response e _i , a dummy challenge c _i , and a dummy commitment a _i for i = t + 1,..., N, and then an n−t degree polynomial f (x), i = 1,. , T, a challenge c _i and a response e _i are generated, and a signature σ (m) is generated. The signature σ (m) is a commitment a _i acquired from t participating devices 910-i (i = 1,..., T) and a commitment a _i (i = t + 1,...) Generated as a dummy by the signature generation unit 920. , N), etc., and not only the signature generation with which t people cooperated, but also the signature with which it is not known which t people cooperated.

The signature verification unit 930 may be provided in any apparatus that wishes to perform signature verification. The signature verification unit verifies that the degree of the polynomial f (x) is n−t and that the values of the challenges c _i (i = 1,..., N) and f (0) are correct.
FIG. 2 is a diagram illustrating a functional configuration example of the participation apparatus 910-i. Participating device 910-i includes key generation unit 911-i, signer evidence generation unit 912-i, recording unit 913-i, and communication unit 914-i. FIG. 3 is a diagram illustrating a processing flow of the key generation unit 911-i, and FIG. 4 is a diagram illustrating a processing flow of the signer evidence generation unit 912-i.

により公開鍵ｐｋ_ｉ（ｐｋ_ｉ∈Ｇ＝{１，ｇ，ｇ^２，…，ｇ^ｑ−１}）を生成し（Ｓ９１１３）、公開鍵ｐｋ_ｉを記録部９１３−ｉに記録する（Ｓ９１１４）。ここで、巡回群Ｇは、離散対数問題が難しい群から選ばれているため、公開鍵ｐｋ_ｉと元ｇが分かっても、秘密鍵ｓｋ_ｉは分からない。このように生成された公開鍵ｐｋ_ｉは、元ｇの情報とともに通信部９１４−ｉを介して公開される。 The key generation unit 911-i includes a secret key sk _i generation unit 9111-i and a public key pk _i generation unit 9112-i. An example of a specific key generation method in the key generation unit 911-i is shown below. In the secret key sk _i generating means 9111-i, one element is selected at random from the remainder class Z _q modulo q with an equal probability as the secret key sk _i (sk _i ∈ _U Z _q ) (S 9111), the secret key sk _i is recorded in the recording unit 913-i (S9112). The public key pk _i generating means 9112-i uses the element g of the cyclic group G determined in advance,

Generates a public key pk _i (pk _i ∈ G = {1, g, g ² ,..., G ^q−1 }) (S9113), and records the public key pk _i in the recording unit 913-i (S9114). . Here, since the cyclic group G is selected from a group in which the discrete logarithm problem is difficult, even if the public key pk _i and the element g are known, the secret key sk _i is not known. The public key pk _i generated in this way is disclosed via the communication unit 914-i together with the information on the original g.

によりコミットメントａ_ｉ（∈Ｇ）を生成し（Ｓ９１２２）、コミットメントａ_ｉを記録部９１３−ｉに記録し、通信部９１４−ｉを介して署名生成部９２０を備える装置に送信する（Ｓ９１２３）。通常、署名者証拠ｒ_ｉはコミットメントａ_ｉを生成すれば不要となるため、記録部９１３−ｉに記録されること無く消去される。署名生成部９２０で署名生成処理が行われると、署名生成部９２０の計算部９２２の処理過程で生成されたチャレンジｃ_ｉが署名生成部９２０から、署名生成に協力している参加装置９１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃ_ｉをチャレンジｃ_ｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅ_ｉ生成手段９１２２−ｉで、ｅ_ｉ：＝ｒ_ｉ−ｃ_ｉｓｋ_ｉ（ｅ_ｉ∈Ｚ_ｑ）により、ｅ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ９１２６）、記録部９１３−ｉに記録するとともに署名生成部９２０に送信する（Ｓ９１２７）。 Signer evidence generator 912-i is a component which operates when to cooperate with the signature generation, the signer evidence _{r i} generation means 9121-i, commitment _{a i} generation means 9122-i, challenge _{c i} acquisition unit 9123 -i, and consists of a response _{e i} generation means 9122-i. An example of a specific processing procedure in the signer evidence generation unit 912-i is shown below. If the participants cooperate to signature, the signer evidence r _i generation means in 9121-i, and selects one based on randomly with equal probability from coset Z _q modulo q signer evidence r _i (R _i ε _U Z _q ) (S9121). Next, the commitment a _i generating means 9122-i uses the element g,

To generate a commitment a _i (∈G) (S9122), record the commitment a _i in the recording unit 913-i, and transmit it to the apparatus including the signature generation unit 920 via the communication unit 914-i (S9123). Usually, the signer proof r _i is not necessary if the commitment a _i is generated, and thus is deleted without being recorded in the recording unit 913-i. If the signature generation processing is performed in the signature generation unit 920, from the challenge c _i is the signature generation unit 920 generated in the process of calculating unit 922 of the signature generation unit 920, participants are collaborating in the signature generating apparatus 910-i (I = 1,..., T). Gets the challenge _{c i} a challenge _{c i} acquisition unit 9123-i (S9124), and records in the recording unit 913-i (S9125). Further, the response _{e i} generation means _9122-i, e _{i: =} the _{r i -c i sk i (e} i ∈Z q), e i (i = 1, ..., t) and calculated (S9126), recording The information is recorded in the part 913-i and transmitted to the signature generation part 920 (S9127).

によりダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ９２１５）、記録部９２４に記録する（Ｓ９２１６）。 FIG. 5 shows a functional configuration example of the signature generation unit 920. The signature generation unit 920 includes a dummy generation unit 921, a calculation unit 922, an information acquisition unit 923, a recording unit 924, and a communication unit 925. FIG. 6 is a diagram showing a processing flow of the signature generation unit 920.
The signature generation unit 920 generates a signature σ (m) by the following procedure. The public key _{pk i (i = 1, ...} , n) of the information acquisition unit 923 via the communication unit 925 by acquiring unit 9231, obtains the public key pk _i participating device 910-i (i = 1, ..., n) (S9231). The dummy generation unit 921 generates a dummy response e _i , a dummy challenge c _i , and a dummy commitment a _i (i = t + 1,..., N) as follows. The dummy response e _i (i = t + 1,..., N) generation unit 9211 selects one element at random with equal probability from the remainder class Z _q modulo q, and the dummy response e _i (i = t + 1,...). , N) (e _i ∈ _U Z _q ) (S9211), and records it in the recording unit 924 (S9212). The dummy challenge c _i (i = t + 1,..., N) generation unit 9212 selects one coordinate value y _i from the finite field K at random with equal probability, and the hash function is set as the dummy challenge c _i (i = t + 1,...). , n) and then _{(y i ∈ U K, c} i: = I (y i) ∈Z q) (S9213), and records in the recording unit 924 (S9214). In addition, the dummy commitment a _i (i = t + 1,..., N) generation unit 9213 uses the element g and the public key pk _i ,

The dummy commitment a _i (i = t + 1,..., N) is generated (S9215) and recorded in the recording unit 924 (S9216).

The commitment _{a i (i = 1, ...} , t) in the information acquisition unit 923 via the communication unit 925 by acquiring unit 9232, acquires the commitment _{a i} participating device 910-i (i = 1, ..., t) (S9232).

Next, the calculation unit 922 obtains the (t, n) threshold signature σ (m) of the message m as follows. The n-th order polynomial f (x) calculating means 9221 causes the n-th order polynomial f (x) (f (x) = α ₀ + α ₁ x + α ₂ x ² +... + α _n−t x ^n−t , α _j ∈ K), f (0) = J (t, n, pk ₁ ,..., pk _n , a ₁ ,..., a _n , m) and f (i) = y _i (i = t + 1,. , N) to obtain an nt degree polynomial f (x) by calculating α _j (j = 0,..., Nt) (S9221). Further, the obtained nt degree polynomial f (x) is recorded in the recording unit 924 (S9222). Challenge _{c i (i = 1, ...} , t) in the generator _9222, c i: = by I (f (i)), the challenge _{c i (i = 1, ...} , t) and calculated (S9223), recording unit and records in 924, the challenge _{c i} participating device corresponding to the 910-i (i = 1, ..., t) to send a challenge _{c i} (S9224). Each participant device 910-i (i = 1,..., T) generates the response e _i as described above using the transmitted challenge c _i and transmits it to the signature generation unit 920 (S9124 to S9127). . Therefore, the response e _i (i = 1,..., T) acquisition unit 9223 acquires the response e _i (i = 1,..., T) (S9225) and records it in the recording unit 924 (S9226). The signature σ (m) creating means 9223 obtains σ (m) from σ (m) = (t, n, f, c ₁ ,..., C _n , e ₁ ,..., E _n ) (S9227), Recording is performed in the recording unit 924 (S9228). In this way, the (t, n) threshold signature σ (m) for the message m is obtained.

であることを確認する（Ｓ９３２）。 FIG. 7 shows a functional configuration example of the signature verification unit 930. FIG. 8 shows a flow for verifying the signature σ (m) in the signature verification unit 930. The information acquisition unit 933 acquires the public key pk _i (i = 1,..., N) and the signature σ (m) (S933), and the degree confirmation unit 931 of the polynomial f (x) determines the degree of the polynomial f (x). Is nt (S931), challenge c _i , polynomial f (0) confirmation means 932,

(S932).

By generating and verifying the signature σ (m) in this way, the signature verification unit 930 (the person who performs the signature verification) cooperates with at least t participating devices 910-i (t participants). You can confirm that you have created a signature. In addition, the signature verification unit 930 does not know which t of the n participating devices 910-i (which t of the n participants) cooperated in generating the signature.
[CDS94] R. Cramer and I. Damgard and B. Schoen-makers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, CRYPTO '94, pp. 174-187, 1994.

The prior art is characterized by the fact that it is not known which participant has cooperated in signature generation, but it has not been possible to prove that the participant has cooperated in signature generation (named out).
In addition, when it is possible to prove that the signature generation has been cooperated, it is also necessary to be able to confirm from the signature how many participants can be proved. Furthermore, since it is conceivable that secret key information is also leaked when proving that the signature generation has been cooperated, the secret key and the public key so far cannot be used.

In the present invention, the signer evidence is recorded in advance in the recording unit of the participating device, and when the participant wants to prove that he has cooperated in the signature generation, the signer evidence is disclosed, and the signer evidence is displayed in the signature verification device. Confirm.
Moreover, the means for making it possible to confirm from the signature how many participants can be proved is as follows. At least one public key for a participating device that does not cooperate in signature generation is generated by the information acquisition unit of the dummy key generation device, and the public key, the random number used when generating the public key, and the element of the cyclic group having a difficult discrete logarithm problem are generated. Publish. The signature generation apparatus generates an electronic signature using a dummy public key. Obtain the public key including the dummy public key with the signature verification device, obtain the random number used when generating the dummy public key, and the above-mentioned elements of the cyclic group where the discrete logarithm problem is difficult, and check the number of signer participants .

  Furthermore, the means for dealing with the leakage of secret key information when proving that the signature generation has been cooperated are as follows. In the participation apparatus, in addition to a private key and public key pair (first private key and public key) used for a long time such as registering a public key with a public institution, a disposable private key used for signature generation A set of public keys (second secret key and public key) is generated, and a dummy public key for at least one second public key is generated by the dummy key generation device. The signature generation device generates a first signature and a second signature. The signature verification apparatus acquires a first public key and a second public key for each participant apparatus, and confirms the first signature and the second signature.

  Alternatively, the participating device generates a disposable private key (second private key) used for signature generation from the first private key. The signature generation device generates only a signature using the second secret key. The signature verification apparatus verifies the signature using the first public key and the elements of the two difficult cyclic groups used in the first key generation and the second key generation.

  In the present invention, it is possible to prove by the above-described means when it is desired to prove that the participant cooperated with the signature generation. In addition, it can be confirmed from the signature how many participants can prove. Further, by using the disposable private key (second private key), it is possible to avoid the outflow of information on the private key paired with the public key registered in the public organization.

  Embodiments of the present invention will be described below with reference to the drawings, but portions having the same functions are denoted by the same reference numerals in each of the drawings, and redundant description is omitted. Also, in the following description, as in the background art, for simplicity, i = 1,..., T is a number indicating the participating devices that cooperated in signature generation, and i = t + 1,. The number indicates the participating devices that did not cooperate in the creation, but the t participating devices may be any of the n participating devices.

[First Embodiment]
In the present invention, it is proved that the participant i (i = 1,..., T) who cooperated with the signature in the (t, n) threshold signature scheme cooperated with the signature after the signature verification by setting t to 1 ≦ t ≦ n. it can. FIG. 9 is a diagram showing a system configuration example and a flow of the present invention. The difference from FIG. 1 which is a diagram showing a system configuration example of the prior art is as follows. Each participant devices 110-i (i = 1, ..., t) is, Record the signer evidence r _i generated in the process to cooperate with the signature creation, it has cooperated in the signature generation (one of the signers If the user wants to prove that the signer evidence r _i is transmitted to the apparatus including the signature verification unit 130, it is proved that the signature generation cooperation has been cooperated. Hereinafter, a configuration apparatus different from the conventional technique will be described in detail.

FIG. 10 is a diagram illustrating a functional configuration example of the participation apparatus 110-i. The participation device 110-i differs from the conventional participation device 910-i in a signer evidence generation unit 112-i and a recording unit 113-i, and a signer evidence disclosure unit 115-i is added. FIG. 11 is a diagram showing a processing flow of the signer evidence generating unit 112-i, and FIG. 12 is a diagram showing a processing flow of the signer evidence disclosing unit 115-i. As shown in FIG. 11, the signer evidence generating unit 112-i records the signer evidence r _i that is unnecessary when the normal commitment a _i is generated in the conventional method in the recording unit 913-i ( performing additional processing after S1121) the signer evidence _{r i} generating step (S9121). When it is desired to prove that the participant i cooperated in signature generation, as shown in FIG. 12, the signer evidence disclosing unit 115-i performs signer evidence r _i recorded in the recording unit 113- _i. Is disclosed to the signature verification unit 130 (S115).

であることを確認する（Ｓ１３３）ことで、署名者証拠ｒ_ｉを公開した参加者ｉが署名生成に協力した参加者であることが分かる。 FIG. 13 shows a functional configuration example of the signature verification unit 130. The difference between conventional signature verification unit 930 shown in FIG. 7 are that the signer evidence r _i confirmation unit 133 is added, is that the information obtaining unit 134 has been modified to also retrieve signer evidence r _i . FIG. 14 shows a signer proof r _i confirmation flow when the signer proof r _i is released from the participant who wants to prove that he / she cooperated in the signature. If the signer evidence r _i from participants i was published that want to prove that it has cooperated with the signature, signature information acquisition unit 134 of the verification unit 130 to get the signer evidence r _i (S134). Next, in the signer proof r _i confirmation means 133,

(S133) confirms that the participant _i who disclosed the signer evidence ri is a participant who cooperated in signature generation.

However, the signer evidence _{r i,} response _{e i,} challenge _{c i,} and between the secret key sk _{i is,} because there is a relationship of _{e i = r i -c i sk} i, to publish a signer evidence _{r i} Thus, the secret key sk _i is also known. Therefore, after proving that the signature has been cooperated, the pair of the secret key sk _i and the public key pk _i that have been used so far cannot be used.

[Second Embodiment]
The present invention relates to a (t, n−1, n) threshold signature scheme in which t is 1 ≦ t ≦ n−1. The (t, n-1, n) threshold signature scheme is a scheme in which it is possible to confirm from the signature only that there are t or more and n-1 or fewer participants who can prove that they are signers. is there. FIG. 15 is a diagram showing a system configuration example and a flow of the present invention. The difference from the first embodiment is that the dummy key generation unit 240 is added and the signature verification unit 230 is changed. . The dummy key generation unit 240 generates a public key pk _n used for signature generation instead of the key generation unit 911-n of the participating device 110-n. By generating a signature using this public key pk _n , a system is realized that can confirm from the signature only that there are t or more and n-1 or less participants who can prove that they were signers. To do. The present invention is described in detail below.

FIG. 16 shows a functional configuration example of the dummy key generation unit 240, and FIG. 17 shows a processing flow of the dummy key generation unit 240. In the dummy key generation unit 240, the public device pk _i (i = 1,..., N−1) acquisition unit 2421 of the information acquisition unit 242 via the communication unit 243, the participating device 110-i (i = 1,. The public key pk _i of n-1) is acquired (S2421). The dummy public key pk _n generation unit 2411 of the calculation unit 241 generates an element x (xεG) belonging to the cyclic group G as a hash value of a random number R of {0, 1} ^* , for example (x = H (R )). For example, the bit length of the random number R is 1024. Here, the secret key sk _i is one element (sk _i ∈ _U Z _q ) randomly with equal probability from the remainder class Z _q modulo _q (see S9111), and the public key pk _i is the cyclic group G Element (pk _i εG) (see S9113). The public key pk _n is defined as pk _n : = x / pk ₁ pk ₂ ... Pk _n−1 (S2411), and the public key pk _n , the element x, and the random number R are disclosed (S2412). If the public key pk _n is determined in this way, the discrete logarithm of x is not known, so the secret key of the participant n is not known.

It should be noted that a dummy key generation unit 240 is provided in each participating device 110-i (i = 1,..., N), and only one participating device 110-n that has created a dummy public key has a dummy key. The generation unit 240 may generate the public key pk _n . Also, one dummy key generation device having a single dummy key generation unit 240 is installed, a public key pk _n is generated instead of the participation device 110-n, and a public key pk is directly or via the participation device 110-n. _n may be disclosed.

FIG. 18 shows a functional configuration example of the signature verification unit 230. The difference from the first embodiment is that the signature participant number confirmation unit 235 is added, and the information acquisition unit 234 is changed so as to also acquire the elements x and R. FIG. 19 shows a flow in which the signature verification unit 230 verifies the signature σ (m). Since the verification flow of the signature σ (m) of the first embodiment is the same as that of the conventional technique, the difference of this flow will be described with respect to the difference from the verification flow of the conventional signature σ (m) shown in FIG. In the signature verification unit 230, the information acquisition unit 234 acquires the public key pk _i (i = 1,..., N), the signature σ (m), the element x, and the random number R (S234), and the polynomial f (x) Are confirmed (same as S931), challenge c _i , and polynomial f (0) confirmation (same as S932). Further, the signature participant number confirmation means 235 confirms x = H (R) and pk ₁ pk ₂ ... Pk _n = x (S235).

By generating and verifying the signature σ (m) in this way, it is not known which public key pk _i, but at least one dummy public key without a private key exists, so cooperation in signature generation It can be confirmed from the signature only that there are t or more and n-1 or less participants who can prove the above.

[Third Embodiment]
The present invention relates to a (t, t ′, n) threshold signature scheme in which t and t ′ are 1 ≦ t ≦ t ′ ≦ n−1. The (t, t ′, n) threshold signature scheme is a scheme in which it is possible to confirm from the signature only that there are t or more and t ′ or fewer participants who can prove that they are signers. FIG. 20 is a diagram showing a system configuration example and a flow of the present invention. The difference from the second embodiment is that the dummy key generation unit 340 and the signature verification unit 330 are changed. In the dummy key generation unit 340, the public key pk used for signature generation instead of the key generation unit 911-i (i = t ′,..., N) of the participating device 110-i (i = t ′,..., N). _i (i = t ′,..., n) is generated. By generating a signature using this public key pk _i , a system is realized in which it is possible to confirm from the signature alone that there are t or more and t ′ or fewer participants who can prove that they were signers. . The present invention is described in detail below.

のｔ'×ｔ'行列（ｉ^ｊ）の逆行列として、Ａ_ｉ（ｉ＝１，…，ｔ'）を

と定め、公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を

として公開鍵ｐｋ_ｉを生成し（Ｓ３４１１）、公開鍵ｐｋ_ｉ、元Ａ_ｉ、および乱数Ｒを公開する（Ｓ３４１２）。このように公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、公開鍵ｐｋ_ｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚ_ｑ［ｘ］）が存在し、秘密鍵ｓｋ_ｉ＝Ｆ（ｉ）かつｌｏｇ_ｇＡ_０＝Ｆ（０）となっている。ここで、Ａ_０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。 FIG. 21 shows a functional configuration example of the dummy key generation unit 340, and FIG. 22 shows a processing flow of the dummy key generation unit 340. In the dummy key generation unit 340, the public device pk _i (i = 1,..., T ′) acquisition unit 3421 of the information acquisition unit 342 via the communication unit 243 performs the participation apparatus 110-i (i = 1,..., T). The public key pk _i of ') is acquired (S3421). In the dummy public key pk _i (i = t ′ + 1,..., N) generation means of the calculation unit 341, the element A ₀ (A ₀ ∈G) belonging to the cyclic group G is represented by a random number R of {0, 1} ^* , for example. (A ₀ = H (R)). ( _{M ij} )

A _i (i = 1,..., T ′) as an inverse matrix of the t ′ × t ′ matrix (i ^j ) of

And the public key pk _i (i = t ′ + 1,..., N)

The public key pk _i is generated (S3411), and the public key pk _i , the element A _i , and the random number R are disclosed (S3412). If the public key pk _i (i = t ′ + 1,..., N) is generated in this way, the public key pk _i ∈G is satisfied, and therefore a t′-order polynomial F (F∈Z _q [x]) exists. The secret key sk _i = F (i) and log _g A ₀ = F (0). Here, since the discrete logarithm of A ₀ is not known, the secret key of the participant i (i = t ′ + 1,..., N) is not known.

（ｐｋ_ｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５）。 FIG. 23 shows a functional configuration example of the signature verification unit 330. The difference from the second embodiment is that the signature participant number confirmation means 335 and the information acquisition means 334 are changed. FIG. 24 shows a flow in which the signature verification unit 330 verifies the signature σ (m). In the signature verification unit 330, the information acquisition unit 334 receives the public key pk _i (i = 1,..., N), the signature σ (m), the element A _i (i = 1,..., T ′), and the random number R. Obtain (S334), confirm the degree of the polynomial f (x) (same as S931), perform the challenge c _i and confirm the polynomial f (0) (same as S932). Further, in the signature participant number confirmation means 335, A ₀ = H (R)

(Pk _i εG) (i = 1,..., N) is confirmed (S335).

By generating and verifying the signature σ (m) in this way, it is not known which public key pk _i is, but at least nt ′ has a dummy public key without a secret key. It can be confirmed from the signature only that the number of participants who can prove that they have cooperated with t is t or more and t 'or less.

[Fourth Embodiment]
The present invention is an improvement of the second embodiment so that the same public key can be used even after a participant proves that he has cooperated in signature generation, where t is 1 ≦ t ≦ n−1. The present invention relates to a (t, n-1, n) threshold signature scheme. FIG. 25 is a diagram showing a system configuration example and a flow of the present invention. The difference from the second embodiment is that the participating devices 410-i (i = 1,..., N), the signature generation unit 420, the signature verification unit 430, and each of the dummy key generation unit 440, a normal private key (public and first private key key) public key and the signer evidence to expose r _i disposable private key unusable public key (the (2 secret key and public key). By using two types of keys, while the effect of the second embodiment maintains the public key such as that registered in the authority of the public (first public key) I am also was published signer evidence r _i Can be used. The present invention is described in detail below.

FIG. 26 is a diagram illustrating a functional configuration example of the participation apparatus 410-i. The participation apparatus 410-i includes a key generation unit 411-i that generates a first secret key and a public key, a key generation unit 911-i that generates a second secret key and a public key, and a signer evidence generation unit 112-. i, a recording unit 413-i, a communication unit 914-i, and a signer proof disclosure unit 115-i. FIG. 27 is a diagram illustrating a processing flow of the key generation unit 411-i that generates the first secret key and the public key. In secret key SK _i generation means 4111-i of the key generation unit 411-i, and generates a secret key SK _i at any (t, n) threshold signature sigma (m) method (S4111), the recording unit 413-i (S4112). For this (t, n) threshold signature Σ (m), a conventional technique may be used, or the same method as the key generation unit 911-i may be used. In public key PK _i generation means 4112-i, and generates a public key PK _i in a manner corresponding to the secret key SK _i generation means 4111-i of the (S4113), and records in the recording unit 413-i (S4114). Set of key generation unit 411-i and the secret key SK _i, which is generated by the public key PK _i is used continuously, it is key that can be used after publication of the signer evidence r _i. Also, a set of secret key sk _i and the public key pk _i generated by the key generation unit 911-i (key generation flow is the same as FIG. 3) is the key is disposable after publishing the signer evidence r _i used It is a key that cannot be done. Incidentally, the signer evidence _{r i} revealer 115-i signer proof generating unit 112-i is the same as the first embodiment.

FIG. 28 shows a configuration example of the dummy key generation unit 440, and FIG. 29 shows a processing flow of the dummy key generation unit 440. In the dummy key generation unit 440, the public key PK _i (i = 1,..., N−1) acquisition unit 4421 of the information acquisition unit 442 via the communication unit 243 performs the participation device 410-i (i = 1,..., The public key PK _i of n-1) is acquired (S4421). Further, the public key _pk i information acquisition unit 242 (i = 1, ..., n-1) obtained by the obtaining unit 2421, participation device 410-i (i = 1, ..., n-1) the public key pk _i of (Same as S2421). The dummy public key pk _n generation means 4411 of the calculation unit 441 uses the element x (x∈G) belonging to the cyclic group G as R = (t, n−1, n, PK ₁ ,..., PK _n , m). , R as a hash value (x = H (R)). The public key pk _n is defined as pk _n : = x / pk ₁ pk ₂ ... Pk _n−1 (S4411), and the public key pk _n , the element x, and R are made public (same as S2412). If the public key pk _n is determined in this way, the discrete logarithm of x is not known, so the secret key of the participant n is not known.

FIG. 30 shows a functional configuration example of the signature generation unit 420. The signature generation unit 420 includes a dummy generation unit 921, a calculation unit 422, an information acquisition unit 423, a recording unit 424, and a communication unit 925. FIG. 31 is a diagram showing a processing flow of the signature generation unit 420.
The signature generation unit 420 generates a signature σ (m) and a signature Σ (m) by the following procedure. Public key _{PK i (i = 1, ...} , n) of the information acquisition unit 423 via the communication unit 925 by acquiring unit 4231, obtains the public key PK _i participating device 910-i (i = 1, ..., n) (S4231). Acquisition of public key pk _i (i = 1,..., N) in step S9231, step S9211 to step S9216, which is a processing flow of the dummy key generation unit, and commitment a _i (i = 1,..., T) in step S9232. Is obtained in the same manner as described with reference to FIG. Further, the element x acquisition unit 4233 of the information acquisition unit 423 acquires the element x (S4233). The processing of steps S9221 to S9228 of the calculation unit 422 is the same as the description of FIG. Therefore, an nt degree polynomial f (x), a challenge c _i (i = 1,..., T), a response e _i (i = 1,..., T), a (t, n) threshold signature σ ( m) is the same as that of the second embodiment, and is the same as the prior art described as the background art. Next, in the signature creation means 4225, M = (t, n−1, n, PK ₁ ,..., PK _n , m, x, pk ₁ ,..., Pk _n ), and (M, σ (M), Σ (M, σ (M)), (M, Σ (M), σ (M, Σ (M))) or (M, σ (M), Σ (M)) is used as a signature (S4227), Storage and disclosure in the recording unit 424 (S4228) Note that Σ (m) is an arbitrary (t, n) threshold signature Σ (m) method corresponding to the method for generating the secret key SK _{i in} step S4411. May be used.

FIG. 32 shows a functional configuration example of the signature verification unit 430, and FIG. 33 shows a verification flow of the signature σ (m) and the signature Σ (m) in the signature verification unit 430. The information acquisition unit 434 acquires the public key PK _i (i = 1,..., N), the public key pk _i (i = 1,..., N), the signature σ (m), the element x, and R (S434). ). Order confirmation of the polynomial f (x) (the same as S931), by performing the challenge _{c i,} the polynomial f (0) Check (same as S932), it is verified the sigma (m). The verification of Σ (m) is performed using an arbitrary (t, n) threshold signature Σ (m) method corresponding to the generation method of the secret key SK _{i in} step S4411 (S431). Further, the signature participant number confirmation means 235 confirms x = H (R) and pk ₁ pk ₂ ... Pk _n = x (same as S235).

Thus signature σ (m) and the signature Σ generate a (m), by verification, also can use the public key PK _i with the secret key SK _i after publication of the signer evidence r _i, and cooperate with the signature generation It can be confirmed from the signature only that there are t or more and n-1 or less participants who can prove the above.

[Fifth Embodiment]
The present invention is an improvement of the third embodiment so that the same public key can be used even after a participant proves that he has cooperated in signature generation, and t and t ′ are set to 1 ≦ t ≦ t ′. (T, t ′, n) Threshold signature scheme with n. FIG. 34 is a diagram showing a system configuration example and a flow of the present invention. The difference from the third embodiment is that a participating device 410-i (i = 1,..., N), a signature generation unit 520, a signature verification unit. 530, and each of the dummy key generation unit 540, a normal private key (public and first private key key) public key and the signer evidence to expose r _i disposable private key unusable public key (the (2 secret key and public key). By using two types of keys, while the effect of the third embodiment maintains the public key such as that registered in the authority of the public (first public key) I am also was published signer evidence r _i Can be used. The present invention is described in detail below.

のｔ'×ｔ'行列（ｉ^ｊ）の逆行列として、Ａ_ｉ（ｉ＝１，…，ｔ'）を

と定め、

として公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成する（Ｓ５４１１）。生成された公開鍵ｐｋ_ｉ、元Ａ_ｉ、およびＲを公開する（Ｓ３４１２と同じ）。このように公開鍵ｐｋ_ｉ（ｉ＝ｔ'＋１，…，ｎ）を生成すれば、第３実施形態と同様に、公開鍵ｐｋ_ｉ∈Ｇを満足するので、ｔ’次多項式Ｆ（Ｆ∈Ｚ_ｑ［ｘ］）が存在し、秘密鍵ｓｋ_ｉ＝Ｆ（ｉ）かつｌｏｇ_ｇＡ_０＝Ｆ（０）となっている。ここで、Ａ_０の離散対数は分からないので、参加者ｉ（ｉ＝ｔ'＋１，…，ｎ）の秘密鍵は分からない。 Since the participating devices 410-i (i = 1,..., N) are the same as those in the fourth embodiment, description thereof is omitted. FIG. 35 shows a configuration example of the dummy key generation unit 540, and FIG. 36 shows a processing flow of the dummy key generation unit 540. In the dummy key generation unit 540, the public device PK _i (i = 1,..., N) acquisition unit 4421 of the information acquisition unit 542 via the communication unit 243 and the participating device 410-i (i = 1,..., N). The public key PK _i is acquired (same as S4421). Further, the public key _pk i information acquisition unit 342 (i = 1, ..., t ') in acquiring unit 3421, participation device 410-i (i = 1, ..., t') to acquire the public key pk _i of ( Same as S2421). The dummy public key pk _i (i = t ′ + 1,..., N) generation unit 5411 of the calculation unit 541 sets R = (t, t ′, n, PK ₁ ,..., PK _n , m) as a cyclic group G. the original _{a 0 (a} 0 ∈G) belonging to generates a hash value of _{R (a 0 = H (R} )). After that, it is the same method as step S3411, and (m _ij ) is

A _i (i = 1,..., T ′) as an inverse matrix of the t ′ × t ′ matrix (i ^j ) of

And

To generate a public key pk _i (i = t ′ + 1,..., N) (S5411). The generated public key pk _i , element A _i , and R are made public (same as S3412). If the public key pk _i (i = t ′ + 1,..., N) is generated in this way, the public key pk _i ∈G is satisfied as in the third embodiment, and therefore the t′-order polynomial F (F∈ Z _q [x]) exists, and the secret key sk _i = F (i) and log _g A ₀ = F (0). Here, since the discrete logarithm of A ₀ is not known, the secret key of the participant i (i = t ′ + 1,..., N) is not known.

FIG. 37 shows a functional configuration example of the signature generation unit 520. The signature generation unit 520 includes a dummy generation unit 921, a calculation unit 522, an information acquisition unit 523, a recording unit 424, and a communication unit 925. FIG. 38 is a diagram showing a processing flow of the signature generation unit 520. This functional configuration and processing flow are almost the same as those of the signature generation unit 420 of the fourth embodiment, and the only difference is that the element A _i (i = 0,..., T ′) is used instead of the element x. Only the differences are shown below. Original _{A i (i = 0, ...} , t ') of the information acquisition unit 523 in the acquisition means 5233, the original x rather original _{A i (i = 0, ...} , t') to get (S5233). In the signature creation means 5225, M = (t, t ′, n, PK ₁ ,..., PK _n , m, A ₀ ,..., A _{t ′} , pk ₁ ,..., Pk _n ), and (M, σ ( M), Σ (M, σ (M)), (M, Σ (M), σ (M, Σ (M))) or (M, σ (M), Σ (M)) are used as signatures ( S5227), storage in the recording unit 424 and disclosure (S4228).

（ｐｋ_ｉ∈Ｇ）（ｉ＝１，…，ｎ）を確認する（Ｓ３３５と同じ）。 FIG. 39 shows a functional configuration example of the signature verification unit 530, and FIG. 40 shows a verification flow of the signature σ (m) and the signature Σ (m) in the signature verification unit 530. In the information acquisition means 534, the public key PK _i (i = 1,..., N), the public key pk _i (i = 1,..., N), the signature σ (m), the element A _i (i = 0,. t ′) and R are acquired (S534). Order confirmation of the polynomial f (x) (the same as S931), by performing the challenge _{c i,} the polynomial f (0) Check (same as S932), it is verified the sigma (m). Further, the verification of Σ (m) is performed using an arbitrary (t, n) threshold signature Σ (m) method corresponding to the generation method of the secret key SK _{i in} the participating device 410-i (the same as S431). ). Further, in the signature participant number confirmation means 335, A ₀ = H (R)

(Pk _i ∈ G) (i = 1,..., N) is confirmed (same as S335).

Thus signature σ (m) and the signature Σ generate a (m), by verification, also can use the public key PK _i with the secret key SK _i after publication of the signer evidence r _i, and cooperate with the signature generation It can be confirmed from the signature only that there are t or more participants who can prove this.

[Sixth Embodiment]
The present invention is an improvement of the first embodiment so that the same public key can be used even after a participant proves that he has cooperated in signature generation, where t is 1 ≦ t ≦ n (t N) Threshold signature scheme. FIG. 41 is a diagram showing a system configuration example and a flow of the present invention. The difference from the first embodiment is that a participating device 610-i (i = 1,..., N), a signature generation unit 620, and a signature verification unit. each 630, two types of keys of a conventional private and public keys (first secret key and public key) and the signer evidence r _i becomes unusable and publish disposable secret key (the second private key) It has been changed so that it can respond to. By using two types of keys, while the effect of the first embodiment is maintained, public key such as that registered in the authority of the public (first public key) is also was published signer evidence r _i Can be used. Further, the difference between the fourth embodiment and the fifth embodiment is that the first secret key SK _i to be used continuously and the second secret key sk _i to be used are associated with each other using a pairing map. In the present invention, the signature generation unit 620 generates only one signature σ (m).

First, symbols and the like that are added or changed for the description of the invention will be briefly described. Let E = {0, P, 2P,..., (P−1) P} be a cyclic group of order p generated by P by addition. E is a cyclic group in which the discrete logarithm problem is difficult (that is, it is difficult to obtain a even if the values of P and aP are known). Let G = {1, g, g ² ,..., G ^(q−1) } be a cyclic group of order q (p is a divisor of q ⁾ generated by g by multiplication. G is a cyclic group in which the discrete logarithm problem is difficult (that is, it is difficult to obtain a even if the values of g and g ^a are known). <•, •>: E × E → G is bilinear (that is, <aP, Q> = <P, aQ> = <P, Q> ^a holds for any a) and non-degenerate ( That is, if <P, Q> = 1 holds for an arbitrary Q, the pairing map satisfies P = 0). H, I, and J are hash functions for conversion as H: {0, 1} ^* → E, I: K → Z _p , and J: {0, 1} ^* → K, respectively. Such groups and pairing maps can be realized using elliptic curves and Weil Pairing on top of them (eg D. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, CRYPTO '01, pp. 213-229, 2001.). The present invention is described in detail below.

  FIG. 42 shows a functional configuration example of the participation apparatus 610-i. The participation apparatus 610-i includes a first key generation unit 611-i, a second key generation unit 612-i, a signer evidence generation unit 613-i, a recording unit 614-i, and a signer evidence disclosure unit 115-i. , And a communication unit 914-i. 43 is a diagram showing a processing flow of the first key generation unit 611-i, FIG. 44 is a diagram showing a processing flow of the second key generation unit 612-i, and FIG. 45 is a diagram of the signer evidence generation unit 613-i. It is a figure which shows a processing flow.

The key generation unit 611-i of the participating device 610-i (i = 1,..., N) generates the first secret key SK _i and the public key PK _i by the following procedure. The secret key SK _i generating means 6111-i selects one element s _i at random from the remainder class Z _p modulo _{p with} equal probability as the secret key SK _i (SK _i = s _i ∈ _U Z _p ) (S6111), the secret key SK _i is recorded in the recording unit 614-i (S6112). The public key PK _i generating means 6112- _i generates a public key PK _i (PK _i εE) by PK _i = s _i P using a predetermined element P of the cyclic group E (S 6113). The key PK _i is recorded in the recording unit 614-i (S6114). Here, since the cyclic group E is selected from a group in which the discrete logarithm problem is difficult, even if the public key PK _i and the element P are known, the secret key SK _i (= s _i ) is not known. The public key PK _i generated in this way is disclosed through the communication unit 914-i together with the information of the original P.

The key generation unit 612-i generates the second secret key ski _i by the following procedure. First, the public key _{PK i (i = 1, ...} , n) participating device acquisition unit 6123-i 610-i (i = 1, ..., n) to obtain the public key PK _i of (S6121). The Q _m generation means 6122-i generates Q _m (Q _m ∈E) as Q _m = H (t, n, PK ₁ ,..., PK _n , m) (S 6122), and Q _m is recorded in the recording unit 614. -I is recorded and released (S6123). The secret key sk _i generating means 6121- _i generates a disposable secret key sk _i (sk _i εE) as sk _i = s _i Q _m (S6124), and records the secret key sk _i in the recording unit 614-i. (S6125). In the above method for obtaining Q _m , public keys PK _i (i = 1,..., N) of all participating devices 610-i are used, and the same Q _m is obtained regardless of which participating device calculates. . Therefore, Q _m may be obtained by one participating device or another device and transmitted to each participating device.

によりコミットメントａ_ｉ（∈Ｇ）を生成し（Ｓ６１３２）、コミットメントａ_ｉを記録部６１４−ｉに記録し、通信部９１４−ｉを介して署名生成部６２０に送信する（Ｓ９１２３）。署名生成部６２０で署名生成処理が行われると、署名生成部６２０の計算部６２２の処理過程で生成されたチャレンジｃ_ｉが署名生成部６２０から、署名生成に協力している参加装置６１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃ_ｉをチャレンジｃ_ｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅ_ｉ生成手段６１３２−ｉで、ｅ_ｉ：＝ｒ_ｉＱ_ｍ−ｃ_ｉｓｋ_ｉ（ｅ_ｉ∈Ｅ）により、ｅ_ｉ（ｉ＝１，…，ｔ）を求め（Ｓ６１３６）、記録部６１４−ｉに記録するとともに署名生成部６２０に送信する（Ｓ９１２７）。 If the participants cooperate to signature, the signer the evidence generation unit 613-i of the signer evidence r _i generation means 6121-i, 1 randomly with equal probability from residue class Z _p modulo p Tsunomoto And signer evidence r _i (r _i ε _U Z _p ) is selected (S6121) and recorded in the recording unit 614-i (S1121). Next, the commitment a _i generating means 6132-i uses the element P,

To generate a commitment a _i (∈G) (S6132), record the commitment a _i in the recording unit 614-i, and transmit it to the signature generation unit 620 via the communication unit 914-i (S9123). If the signature generation processing is performed in the signature generation unit 620, from the challenge c _i is the signature generation unit 620 generated in the process of calculating portion 622 of the signature generation unit 620, participants are collaborating in the signature generating apparatus 610-i (I = 1,..., T). Gets the challenge _{c i} a challenge _{c i} acquisition unit 9123-i (S9124), and records in the recording unit 913-i (S9125). Further, the response _{e i} generation means _6132-i, e _{i: =} the _{r i Q m -c i sk i} (e i ∈E), e i (i = 1, ..., t) and calculated (S6136), The information is recorded in the recording unit 614-i and transmitted to the signature generation unit 620 (S9127).

  FIG. 46 shows a functional configuration example of the signature generation unit 620. The signature generation unit 620 includes a dummy generation unit 621, a calculation unit 622, an information acquisition unit 623, a recording unit 624, and a communication unit 925. FIG. 47 is a diagram showing a processing flow of the signature generation unit 620.

によりダミーコミットメントａ_ｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ６２１５）、記録部６２４に記録する（Ｓ９２１６）。 The signature generation unit 620 generates a signature σ (m) by the following procedure. Public key _{PK i (i = 1, ...} , n) of the information acquisition unit 623 via the communication unit 925 by acquiring unit 4231, obtains the public key PK _i participating device 910-i (i = 1, ..., n) (S4231). Further, the _{Q m} acquisition unit 6231 acquires a _{Q m} (S6231). The dummy generation unit 621 generates a dummy response e _i , a dummy challenge c _i , and a dummy commitment a _i (i = t + 1,..., N) as follows. The dummy response e _i (i = t + 1,..., N) generating means 6211 selects one element at random from the remainder class Z _p modulo _{p with} equal probability, and the dummy response e _i (i = t + 1,. , N) (e _i ∈ _U Z _p ) (S6211), and records it in the recording unit 624 (S9212). The dummy challenge c _i (i = t + 1,..., N) generation unit 9212 selects one coordinate value y _i from the finite field K at random with equal probability, and the hash function is set as the dummy challenge c _i (i = t + 1,...). , n) and then _{(y i ∈ U K, c} i: = I (y i) ∈Z p) (S6213), and records in the recording unit 624 (S9214). Further, the dummy commitment a _i (i = t + 1,..., N) generation unit 6213 uses the element P, Q _m , and the public key PK _i ,

The dummy commitment a _i (i = t + 1,..., N) is generated (S6215) and recorded in the recording unit 624 (S9216).

The commitment _{a i (i = 1, ...} , t) in the information acquisition unit 623 via the communication unit 925 by acquiring unit 9232, acquires the commitment _{a i} participating device 610-i (i = 1, ..., t) (Same as S9232).

Next, the calculation unit 622 obtains the (t, n) threshold signature σ (m) of the message m as follows. The n-th order polynomial f (x) calculating means 6221 causes the n-th order polynomial f (x) (f (x) = α ₀ + α ₁ x + α ₂ x ² +... + α _n−t x ^n−t , α defined as _{j ∈K), f (0)} = J (t, n, PK 1, ..., PK n, Q m, a 1, ..., a n, m) and _{f (i) = y i (} i = By calculating α _j (j = 0,..., nt) from the condition of t + 1,..., n), an nt degree polynomial f (x) is obtained (S6221). Further, the obtained nt degree polynomial f (x) is recorded in the recording unit 624 (S9222). Challenge _{c i (i = 1, ...} , t) in the generator _9222, c i: = by I (f (i)), the challenge _{c i (i = 1, ...} , t) and calculated (S9223), recording unit and records in 924, the challenge _{c i} participating device corresponding to the 910-i (i = 1, ..., t) to send a challenge _{c i} (S9224).

Each participant device 610-i (i = 1,..., T) generates a response e _i as described above using the transmitted challenge c _i and transmits it to the signature generation unit 620 (S9124 in FIG. 45). To S9127). Therefore, the response e _i (i = 1,..., T) acquisition unit 9223 acquires the response e _i (i = 1,..., T) (S9225) and records it in the recording unit 624 (S9226). The signature σ (m) creating means 6223 obtains σ (m) from σ (m) = (f, c ₁ ,..., C _n , e ₁ ,..., E _n ) (S 6227) and stores it in the recording unit 624. Recording is performed (S9228). In this way, the (t, n) threshold signature σ (m) for the message m is obtained.

であることを確認する（Ｓ９３２）。 FIG. 48 shows a functional configuration example of the signature verification unit 630, and FIG. 49 shows a flow for verifying the signature σ (m) in the signature verification unit 630. The processing flow for confirming the signer evidence r _i is the same as the first embodiment. When verifying the signature σ (m), the information acquisition unit 634 acquires the public key PK _i (i = 1,..., N), Q _m , and the signature σ (m) (S634), and the polynomial f (x ) Order confirmation means 931 confirms that the degree of the polynomial f (x) is n−t (S931), and Q _m confirmation means 632 confirms that Q _m = H (t, n, PK ₁ ,..., PK _n , m) and Q _m ∈ E (S632), the challenge c _i , the polynomial f (0) confirmation means 633,

(S932).

を確認しているため、署名者証拠ｒ_ｉ（ｒ_ｉ∈Ｚ_ｐ）と公開鍵ＰＫ_ｉ（ＰＫ_ｉ＝ｓ_ｉＰ∈Ｅ）とは関連しており、署名者証拠ｒ_ｉを示すことにより公開鍵ＰＫ_ｉに対応する参加者ｉが署名に協力したことを証明することができる。 By generating and verifying the signature σ (m) in this way, the following effects can be obtained. If you publish a signer evidence _{r i} in order to prove the participants i that it has cooperated in the signature generation, the second of the secret key sk _{i is, sk i = s i Q m} = c i -1 (r i Q _m −e _i ), but since E is selected from a cyclic group in which the discrete logarithm problem is difficult, the first secret key SK _i (SK _i = s _i ∈Z _p ) cannot be obtained. . Therefore, the public key PK _i can be used even after the signer proof r _{i is} disclosed. In addition, the challenge _{c i,} a polynomial f (0) confirmation means 633,

Therefore, the signer evidence r _i (r _i ∈Z _p ) and the public key PK _i (PK _i = s _i P∈E) are related, and by indicating the signer evidence r _i It can be proved that the participant _i corresponding to the public key PK _i cooperated in the signature.

[Seventh Embodiment]
This embodiment is a summary of the first to sixth embodiments. FIG. 50 shows a processing flow of the (t, n) threshold electronic signature system in which the first to sixth embodiments are summarized. In FIG. 50, apparatuses (parts) and processing steps common to all the embodiments are indicated by solid squares, and apparatuses (parts) and processing steps necessary for the second to fifth embodiments are indicated by dotted squares. The apparatuses (parts) and processing steps necessary for the fourth to sixth embodiments are indicated by a dashed-dotted line. The processing steps necessary for the sixth embodiment are indicated by a two-dot chain square.

Participating devices (410-i or 610-i) (i = 1,..., N) of the fourth to sixth embodiments generate a first secret key SK _i and a public key PK _{i and} make them public. Publish the key PK _i . In the case of the first embodiment and the sixth embodiment, all the participating devices (110-i or 610-i) (i = 1,..., N) generate a secret key sk _i used for signature. the first embodiment also generates a public key pk _i, publishes the public key pk _i. In the second and fourth embodiments, the participating device (110-i or 410-i) (i = 1,..., N-1) generates a private key sk _i and a public key pk _i used for signature. And public key pk _i is made public. In the third and fifth embodiments, the participating device (110-i or 410-i) (i = 1,..., T ′) generates a secret key sk _i and a public key pk _i used for signature. , Public key pk _i is made public.

In the case of the second to fifth embodiments, the dummy key generation unit (240, 340, 440, 540) generates a dummy public key pk _i (i = n or t ′,..., N), Publish.
Join apparatus to cooperate with the signature generation (110-i, 410-i or 610-i,) (i = 1, ..., t) generates a signer evidence _{r i} and commitment _{a i,} signed commitment _{a i} It transmits to a production | generation part (920, 420, 520, or 620). The signature generation unit (920, 420, 520, or 620) corresponds to a participating device (110-i, 410-i, or 610-i) (i = t + 1,..., N) that does not cooperate with signature generation. Participating devices (110-i, 410-i, or 610-i) that have generated dummy responses e _i , challenges c _i , and commitment a _i and cooperated in generating the nt-order polynomial f and signature (i = 1) , ..., generates a challenge _{c i} corresponding to t), join apparatus Challenge _{c i (110-i, 410} -i or 610-i) (i = 1 ,, ..., are transmitted to t). Each participating device (110-i, 410-i, or 610-i) (i = 1,..., T) generates a response e _i and transmits it to the signature generation unit (920, 420, 520, or 620). . The signature generation unit (920, 420, 520, or 620) generates a signature σ (in the case of the fourth and fifth embodiments, further Σ). The signature verification unit (130, 230, 330, 430, 530, or 630) confirms the signature σ (in the case of the fourth and fifth embodiments, further Σ), and the second to fifth embodiments. In the case of a form, the number of signature participants is confirmed. Further, if the participant who cooperated with the signature wants to prove that the participant cooperated with the signature, the participating device (110-i, 410-i, or 610-i) (i = 1,. publish the r _i, the signature verification unit (130,230,330,430,530 or 630,) confirms the signer evidence _{r i.} The details of each process are as shown in the first to sixth embodiments.

  With such a system configuration and processing method, it is possible to prove that the participant wants to prove that he / she cooperated in signature generation. In addition, it can be confirmed from the signature how many participants can prove. Further, by using the disposable private key (second private key), it is possible to avoid the outflow of information on the private key paired with the public key registered in the public organization.

The figure which shows the structural example and flow of an electronic signature system with a threshold value. The figure which shows the function structural example of participation apparatus 910-i. The figure which shows the processing flow of the key generation part 911-i. The figure which shows the processing flow of the signer proof production | generation part 912-i. The figure which shows the function structural example of the signature production | generation part 920. FIG. The figure which shows the processing flow of the signature production | generation part 920. The figure which shows the function structural example of the signature verification part 930. FIG. The figure which shows the flow which verifies signature (sigma) (m) in the signature verification part 930. FIG. The figure which shows the system configuration example and flow of 1st Embodiment. The figure which shows the function structural example of participating apparatus 110-i. The figure which shows the processing flow of the signer proof production | generation part 112-i. The figure which shows the processing flow of the signer proof disclosure part 115-i. The figure which shows the function structural example of the signature verification part 130. FIG. The figure which shows a signer proof r _i confirmation flow when the signer proof r _i is made public by a participant who wants to prove that he has cooperated in the signature. The figure which shows the system configuration example and flow of 2nd Embodiment. The figure which shows the function structural example of the dummy key production | generation part 240. FIG. The figure which shows the processing flow of the dummy key production | generation part 240. FIG. FIG. 3 is a diagram illustrating an example of a functional configuration of a signature verification unit 230. The figure which shows the flow in which the signature verification part 230 verifies signature (sigma) (m). The figure which shows the system configuration example and flow of 3rd Embodiment. The figure which shows the function structural example of the dummy key production | generation part 340. The figure which shows the processing flow of the dummy key production | generation part 340. FIG. 3 is a diagram illustrating an example of a functional configuration of a signature verification unit 330. The figure which shows the flow in which the signature verification part 330 verifies signature (sigma) (m). The figure which shows the system configuration example and flow of 4th Embodiment. The figure which shows the function structural example of participating apparatus 410-i. The figure which shows the processing flow of the key generation part 411-i which produces | generates a 1st secret key and a public key. The figure which shows the structural example of the dummy key production | generation part 440. FIG. The figure which shows the processing flow of the dummy key production | generation part 440. FIG. FIG. 4 is a diagram illustrating an example of a functional configuration of a signature generation unit 420. The figure which shows the processing flow of the signature production | generation part 420. FIG. The figure which shows the function structural example of the signature verification part 430. FIG. The figure which shows the verification flow of signature (sigma) (m) and signature (SIGMA) (m) in the signature verification part 430. FIG. The figure which shows the system configuration example and flow of 5th Embodiment. The figure which shows the structural example of the dummy key production | generation part 540. The figure which shows the processing flow of the dummy key production | generation part 540. The figure which shows the function structural example of the signature production | generation part 520. FIG. The figure which shows the processing flow of the signature production | generation part 520. The figure which shows the function structural example of the signature verification part 530. FIG. The figure which shows the verification flow of signature (sigma) (m) and signature (SIGMA) (m) in the signature verification part 530. FIG. The figure which shows the system configuration example and flow of 6th Embodiment. The figure which shows the function structural example of participating apparatus 610-i. The figure which shows the processing flow of the 1st key production | generation part 611-i. The figure which shows the processing flow of the 2nd key production | generation part 612-i. The figure which shows the processing flow of the signer proof production | generation part 613-i. The figure which shows the function structural example of the signature production | generation part 620. FIG. The figure which shows the processing flow of the signature production | generation part 620. FIG. The figure which shows the function structural example of the signature verification part 630. FIG. The figure which shows the flow which verifies signature (sigma) (m) in the signature verification part 630. FIG. The figure which shows the processing flow of the (t, n) threshold value electronic signature system which put together 6th Embodiment from 1st Embodiment.

Claims (12)

n number of participating devices, with respect to the signature generation unit which is provided in either or independent apparatus participating device has a signature verification unit that is provided in any device, a message by t stand participating device to cooperate A signature system for generating a signature,
n is an integer of 2 or more, t is an integer of n-1 or less, G is a cyclic group in which the discrete logarithm problem is difficult, g is a generator of the group G,
i is an index for identifying the numbers of participating devices, i = 1,..., t participating devices cooperate in signature generation, and i = t + 1,... n participating devices do not cooperate in signature generation. And
Each participating device

A key generation unit that generates a secret key sk _i and a public key pk _i having the relationship:
If you want to cooperate with the signature generation generates a signer evidence r _i,

The transmitted to the signature generation unit obtains the challenge c _i from the signature generation unit generates a commitment a _i having a relationship,
_{e i = r i -c i sk} i
A signer proof generation unit that generates a response e _i having the following relationship and transmits the response e _i to the signature generation unit ;
A recording unit for recording the signer evidence r _i,
A signer proof publishing unit that transmits the signer proof r _i to the signature verification unit ;
The signature generation unit
Response _{e i} for participation devices that did not cooperate with the signature generation, the challenge _{c i,} dummy response _{e i} is a commitment _{a i,} dummy challenge _{c i,} a dummy commitment _{a i}

A dummy generation unit that generates the relationship as follows:
Receiving the commitment a _i from the participating device to cooperate with the signature, the public key pk _i and the commitment a _i and n-t-order polynomial depending on the calculation using the dummy commitment a _i of participation apparatus to cooperate with the signature f is obtained, the challenge c _i of the participating device cooperating with the signature is generated and transmitted to the corresponding participating device, the response e _i is received from the participating device cooperating with the signature, the polynomial f and all the participating devices generates a signature σ comprising the response e _i and the challenge c _i, and a calculating unit that records,
The signature verification unit
The acquired from the signature generating unit said signature sigma, acquires the public key pk _i of all the participating device, the information acquiring means for acquiring the signer evidence r _i from one of the participating device,
And the order confirmation means for confirming that the degree of the polynomial f included in the signature σ is a n-t,
The public key pk _i and the response e _i included in the signature σ that the challenge c _i included in the signature σ is generated by the calculation unit and the polynomial f included in the signature σ is determined by the calculation unit. Challenge / polynomial confirmation means to confirm using
The signer evidence _{r i} is,

A signing system comprising: signer evidence confirmation means for confirming that the participating device cooperates in signature generation by confirming that The signature system of claim 1,
Furthermore, it has a dummy key generation unit provided in any of the participating devices or an independent device ,
The dummy key generation unit
Generate an arbitrary element x of group G,
Obtain public keys pk _i (i = 1,..., N−1) of participating devices excluding one participating device not cooperating in signature generation;
pk _n = x / pk ₁ pk ₂ ... pk _n−1
Calculate the public key pk _n of one participating device that is not cooperating with signature generation as follows:
The signature verification unit further includes pk ₁ pk ₂ ... Pk _n = x
A signature system that also includes means for confirming the number of signing participants. The signature system of claim 1,
Let t ′ be an integer between t and n,
Furthermore, it has a dummy key generation unit provided in any of the participating devices or an independent device ,
The dummy key generation unit
Generate an arbitrary element A ₀ of group G;

Calculate m _ij as _follows :

A _i (i = 1,..., T ′) is calculated as follows :

Compute public keys pk _i (i = t ′ + 1,..., N) of (nt ′) participating devices that do not cooperate in signature generation as
The signature verification unit further includes

A signature system that also includes means for confirming the number of signing participants. The signature system according to claim 2,
Each participating device
The key generation unit is a second key generation unit, and
A first key generation unit for generating a secret key SK _i and a public key PK _i ;
The element x generated by the dummy key generation unit is
Generated from a bit string including public keys PK ₁ ,..., PK _n using a hash function H that converts a bit string of arbitrary length into an element of group G;
The calculation unit of the signature generation unit is:
A signature Σ for the message is also generated by a method corresponding to the method for generating the secret key SK _i ,
The signature verification unit
A signature system comprising Σ confirmation means for confirming the signature Σ. A signature system according to claim 3,
Each participating device
The key generation unit is a second key generation unit, and
A first key generation unit for generating a secret key SK _i and a public key PK _i ;
The _element A ₀ generated by the dummy key generation unit is
Generated from a bit string including public keys PK ₁ ,..., PK _n using a hash function H that converts a bit string of arbitrary length into an element of group G;
The calculation unit of the signature generation unit is:
A signature Σ for the message is also generated by a method corresponding to the method for generating the secret key SK _i ,
The signature verification unit
A signature system comprising Σ confirmation means for confirming the signature Σ. n number of participating devices, with respect to the signature generation unit which is provided in either or independent apparatus participating device has a signature verification unit that is provided in any device, a message by t stand participating device to cooperate A signature system for generating a signature,
n is an integer of 2 or more, t is an integer of n-1 or less, G is a cyclic group in which the discrete logarithm problem is difficult, g is a generator of the group G, E is a cyclic group in which the discrete logarithm problem generated by addition is difficult, P Is a generator of group E, <·, ·> is a pairing map that transforms two group E elements into group G elements,
i is an index for identifying the numbers of participating devices, i = 1,..., t participating devices cooperate in signature generation, and i = t + 1,... n participating devices do not cooperate in signature generation. And
Each participating device
PK _i = SK _i P
A first key generation unit that generates a secret key SK _i and a public key PK _i having the relationship:
Generate an element Q _{m of the} group E from the bit string including the public keys PK ₁ ,..., PK _n using a hash function H that converts a bit string of arbitrary length into the elements of the group E,
sk _i = SK _i Q _m
A second key generation unit for generating the secret key sk _i as follows:
If you want to cooperate with the signature generation generates a signer evidence r _i,

The transmitted to the signature generation unit obtains the challenge c _i from the signature generation unit generates a commitment a _i having a relationship,
_{e i = r i Q m -c} i sk i
A signer proof generation unit that generates a response e _i having the following relationship and transmits the response e _i to the signature generation unit ;
A recording unit for recording the signer evidence r _i,
A signer proof publishing unit that transmits the signer proof r _i to the signature verification unit ;
The signature generation unit
Response _{e i} for participation devices that did not cooperate with the signature generation, the challenge _{c i,} dummy response _{e i} is a commitment _{a i,} dummy challenge _{c i,} a dummy commitment _{a i}

A dummy generation unit that generates the relationship as follows:
Receiving the commitment a _i from the participating device to cooperate with the signature, the public key PK _i and the commitment a _i and n-t-order polynomial depending on the calculation using the dummy commitment a _i of participation apparatus to cooperate with the signature f is obtained, the challenge c _i of the participating device cooperating with the signature is generated and transmitted to the corresponding participating device, the response e _i is received from the participating device cooperating with the signature, the polynomial f and all the participating devices A calculation unit that generates and records a signature σ including the challenge c _i and the response e _i ,
The signature verification unit
The acquired from the signature generating unit said signature sigma, acquires the public key pk _i of all the participating device, the information acquiring means for acquiring the signer evidence r _i from one of the participating device,
And the order confirmation means for confirming that the degree of the polynomial f included in the signature σ is a n-t,
Original Q _m, using the hash function H, public keys PK 1 _above, ..., and Q _m confirmation means for confirming that it has been generated from a bit string containing the PK _n,
The challenge c _i included in the signature σ is generated by the calculation unit, and the fact that the polynomial f included in the signature σ is determined by the calculation unit indicates that the public key pk _i and the response e included in the signature σ Challenge / polynomial confirmation means to confirm using _i ,
The signer evidence _{r i} is,

A signing system comprising: signer evidence confirmation means for confirming that the participating device cooperates in signature generation by confirming that With the cooperation of t participating devices in a signature system having n participating devices, a signature generation unit provided in any of the participating devices or an independent device, and a signature verification unit provided in an arbitrary device. A signature method for generating a signature for a message ,
n is an integer of 2 or more, t is an integer of n-1 or less, G is a cyclic group in which the discrete logarithm problem is difficult, g is a generator of the group G,
i is an index for identifying the numbers of participating devices, i = 1,..., t participating devices cooperate in signature generation, and i = t + 1,... n participating devices do not cooperate in signature generation. And
All participating devices

A key generation step of generating a secret key sk _i and a public key pk _i having the relationship:
Each participating device to cooperate with the signature generation is to generate a signer evidence r _i,

The transmitted to the signature generation unit obtains the challenge c _i from the signature generation unit generates a commitment a _i having a relationship,
_{e i = r i -c i sk} i
A signer evidence generation step of generating a response e _i having the following relationship and transmitting the response e _i to the signature generation unit ;
Each participating device to cooperate with the signature generation, and recording the signer evidence r _i,
The signature generation unit obtains a response e _i , a challenge c _i , a dummy response e _i that is a commitment a _i , a dummy challenge c _i , and a dummy commitment a _i for the participating devices that did not cooperate in signature generation.

A dummy generation step for generating the relationship as follows:
The signature generation unit receives the commitment a _i from a participating device cooperating with the signature, and performs calculation using the public key pk _i and the commitment a _i and the dummy commitment a _i of the participating device cooperating with the signature. Te seek n-t-degree polynomial f, and transmitted to the corresponding participant device generates a challenge c _i participating device to cooperate with the signature, and receives the response e _i from the participant device to cooperate with the signing, the polynomial a calculation step of generating and recording a signature σ including f and the challenge c _i and the response e _i of all participating devices;
Any of the participating device, and the signer evidence public step to send a signer evidence r _i to the signature verification unit,
Information to the signature verification unit, obtains the signature σ from the signature generation unit, to obtain the public key pk _i of all of the participating devices, to get the signer evidence r _i from any of the participating devices An acquisition step;
And the order confirmation step of confirming that the degree of the polynomial f included in the signature σ is a n-t,
The signature verification unit determines that the challenge c _i included in the signature σ is generated by the calculation unit, and that the polynomial f included in the signature σ is determined by the calculation unit, the public key pk _i , the signature σ and Challenge polynomial confirmation step of confirming with the response e _i that is included in,
Before Symbol signature verification unit, the previous Symbol signer evidence r _i,

By confirming that satisfy, signature method and a signer evidence confirming step participants published a signer evidence r _i device to confirm that cooperated with the signature generation. The signature method according to claim 7, comprising:
The signature system also has the dummy key generating unit that is provided in either or independent apparatus of the participating device,
The dummy key generation unit generates an arbitrary element x of the group G;
Obtain public keys pk _i (i = 1,..., N−1) of participating devices excluding one participating device not cooperating in signature generation;
pk _n = x / pk ₁ pk ₂ ... pk _n−1
A dummy key generation step for calculating the public key pk _n of one participating device not cooperating with signature generation ,
The signature verification unit
pk ₁ pk ₂ ... pk _n = x
The signing method also includes a step of confirming the number of signing participants to confirm that the number of signing participants. The signature method according to claim 7, comprising:
The signature system also has the dummy key generating unit that is provided in either or independent apparatus of the participating device,
Let t ′ be an integer between t and n,
The dummy key generation unit generates an arbitrary element A ₀ of the group G;

Calculate m _ij as _follows :

A _i (i = 1,..., T ′) is calculated as follows :

A dummy key generation step of calculating public keys pk _i (i = t ′ + 1,..., N) of (nt−t ′) participating devices that are not cooperating in signature generation,
The signature verification unit

The signing method also includes a step of confirming the number of signing participants to confirm that the number of signing participants. The signing method according to claim 8, comprising:
The key generation step is a second key generation step,
Before the second key generation step, all participating devices have a first key generation step of generating a secret key SK _i and a public key PK _i ,
The element x generated in the dummy key generation step is generated from a bit string including public keys PK ₁ ,..., PK _n using a hash function H that converts a bit string of an arbitrary length into a group G element. And
The calculating step also generates a signature Σ for the message by a method corresponding to the method for generating the secret key SK _i ,
The signature method further comprising a Σ confirmation step in which the signature verification unit confirms the signature Σ. The signature method according to claim 9, comprising:
The key generation step is a second key generation step,
Before the second key generation step, all participating devices have a first key generation step of generating a secret key SK _i and a public key PK _i ,
The element A ₀ generated in the dummy key generation step is generated from a bit string including the public keys PK ₁ ,..., PK _n using a hash function H that converts an arbitrary-length bit string into a group G element. It has been
The calculating step also generates a signature Σ for the message by a method corresponding to the method for generating the secret key SK _i ,
The signature method further comprising a Σ confirmation step in which the signature verification unit confirms the signature Σ. With the cooperation of t participating devices in a signature system having n participating devices, a signature generation unit provided in any of the participating devices or an independent device, and a signature verification unit provided in an arbitrary device. A signature method for generating a signature for a message ,
n is an integer of 2 or more, t is an integer of n-1 or less, G is a cyclic group in which the discrete logarithm problem is difficult, g is a generator of the group G, E is a cyclic group in which the discrete logarithm problem generated by addition is difficult, P Is a generator of group E, <·, ·> is a pairing map that transforms two group E elements into group G elements,
i is an index for identifying the numbers of participating devices, i = 1,..., t participating devices cooperate in signature generation, and i = t + 1,... n participating devices do not cooperate in signature generation. And
All participating devices
PK _i = SK _i P
A first key generation step of generating a secret key SK _i and a public key PK _i having the relationship:
All participating devices generate a group E element Q _m from a bit string including public keys PK ₁ ,..., PK _n using a hash function H that converts a bit string of arbitrary length into a group E element,
sk _i = SK _i Q _m
A second key generation step of generating the secret key sk _i as follows:
Each participating device to cooperate with the signature generation is to generate a signer evidence r _i,

The transmitted to the signature generation unit obtains the challenge c _i from the signature generation unit generates a commitment a _i having a relationship,
_{e i = r i Q m -c} i sk i
A signer evidence generation step of generating a response e _i having the following relationship and transmitting the response e _i to the signature generation unit ;
Each participating device to cooperate with the signature generation, and recording the signer evidence r _i,
The signature generation unit obtains a response e _i , a challenge c _i , a dummy response e _i that is a commitment a _i , a dummy challenge c _i , and a dummy commitment a _i for the participating devices that did not cooperate in signature generation.

A dummy generation step for generating the relationship as follows:
The signature generation unit receives the commitment a _i from a participating device cooperating with the signature, and calculates n using the public key PK _i and the commitment a _i and the dummy commitment a _i of the participating device cooperating with the signature. Obtaining a t-order polynomial f , generating the challenge c _i of the participating device cooperating with the signature and transmitting it to the corresponding participating device, receiving the response e _i from the participating device cooperating with the signature, and the polynomial f and A calculation step of generating and recording a signature σ including the challenge c _i and the response e _i of all participating devices;
Any of the participating device, and the signer evidence public step to send a signer evidence r _i to the signature verification unit,
Information to the signature verification unit, obtains the signature σ from the signature generation unit, to obtain the public key pk _i of all of the participating devices, to get the signer evidence r _i from any of the participating devices An acquisition step;
And the order confirmation step of confirming that the degree of the polynomial f included in the signature σ is a n-t,
The signature verification unit, the original Q _m, using the hash function H, public keys PK 1 _above, ..., and Q _m confirmation step of confirming that generated a bit string containing the PK _n,
The signature verification unit determines that the challenge c _i included in the signature σ is generated by the calculation unit, and that the polynomial f included in the signature σ is calculated by the calculation unit, the public key pk _i , the signature and Challenge polynomial confirmation step of confirming with the response e _i included in the sigma,
Before Symbol signature verification unit, the previous Symbol signer evidence r _i,

By confirming that satisfy, signature method and a signer evidence confirming step participants published a signer evidence r _i device to confirm that cooperated with the signature generation.

Images