Blind signature method, device therefor, and program and recording medium therefor

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a blind signature method, a device thereof, a program thereof, and a recording medium thereof, which allows a signer to attach an electronic signature to electronic information while keeping the electronic information confidential.

【0002】

[Conventional technology]

For this type of blind signature, the method based on the RSA method is described in Reference D. Chaum, Security without Identification: Transaction Systems to Make Big Brother Obsolete, Comm.of the ACM, 28,10, pp.1030-1044 (1985). ). The requester of the signature creates a blind message e by disturbing the document m with a random number a by the blind signature preprocessing. The signer uses the private key to calculate the tentative signature s corresponding to e. At this time, since e is disturbed by a, the signer cannot know the document m. The signing requester removes the influence of the random number a from the temporary signature s by blind signature post-processing, obtains the signature c for the original document m, and sends the pair of m and c to the verifier. The verifier uses the signer's public key to verify that c is the signature of m. Here, since the verifier does not know the random number a, he cannot know the correspondence between s and c.

【0003】

The procedure for blind signature based on Schnorr signature is shown below. Let p and q be large prime numbers, and let q be divisible by p-1. g, Z_pIt is the source of the order q of. The signer is the private key x and y = g^xHold the public key y that satisfies mod p. Let H be a hash function. It is assumed that p, q, g, H and y are open to the public (see Fig. 9 below). Step-1 The signer is a random number k Z_pTo generate r: = g^kCalculate mod q and send r to the signing requester.

【0004】

Step-2 The signing requester is a random number a, bIs generated and r is d: = rg^ay^{b b}Disturb with modp. Next, using d and the document m, the challenge h is calculated as h: = H (m, d), and this challenge is disturbed by b as C = h-b mod q. Finally, send C to the signer. Step-3 The signer calculates s = k-xCmod q and sends the tentative signature s to the signing requester. Step-4 The signing requester outputs c: = s + amod q and s as a signature for the document m by disturbing with a so that it can be verified.

【0005】

The signature (h, c) for document m is h = H (m, g)^cy^hWhen mod p) holds, it is recognized as a correct document-signature pair, and if it does not hold, it is considered an invalid signature. If the signature generation procedure is executed correctly, the output (h, c) is h = H (m, d) h = H (m, rg^ay^{b b}mod p) = H (m, g^{k + a}y^{b b}mod p) = H (m, g^{s + xC + a}y^{b b}mod p) = H (m, g^{c-a + hx-bx + a}y^{b b}mod p) = H (m, g^{c + hx}mod p) = H (m, g^cy^hmod p) And the verification formula h = H (m, g)^cy^hmod p) is satisfied.

【0006】

[Problems to be Solved by the Invention]

With the blind signature method described above, it is difficult to prove that the signature (h, c) is unique to the document m, so the security of the signature is unknown. That is, it cannot be denied that the number of signatures requested by the signature requester may be output more than the number requested. Therefore, it cannot be safely used for applications such as electronic cash and electronic tickets that require that the signature issued by the signer cannot be inflated.

【0007】

An object of the present invention is to provide a blind signature method, an apparatus thereof, a program thereof and a recording medium thereof to ensure that a signature requester cannot output more signatures than requested.

【0008】

[Means for solving problems]

According to the present invention, the signer device generates a temporary public key z'from a part z of a plurality of public keys at the time of signing. At this time, z and z satisfy a certain relation R, but generate z in a way that the signing requester can understand the fact that the signer does not know the relation. The signer device generates signatures s based on this z, z'. The signing requester device disturbs z, z'and s to make them U, U', σ, and obtains a signature σ based on a part U of the disturbed public key. At this time, the method of disturbance by the signature requester device is such that when z, z'is correctly disturbed, the relation R satisfied by z, z'is also satisfied by U, U', and the signature requester device If does not follow the correct method of disturbance, make it difficult to obtain U, U', σ that the verifier considers correct.

【0009】

By limiting the method of disturbance by the signature requester device as described above, the signature s issued by the signer device and the signature σ after the disturbance can be related. At the same time, all signatures issued by the signer's device and the signing requester's device by using a perturbation method such that it is difficult for the signer's device to obtain an irrelevant signature by a method other than the original perturbation method. It will be possible to guarantee that there is a one-to-one correspondence between all the correct signatures obtained.

【0010】

BEST MODE FOR CARRYING OUT THE INVENTION

As shown in FIG. 1, the signature requester device 10, the signer device 20, and the verifier device 30 can be connected via, for example, a communication network 40. The signature requester device 10 may be like an IC card, in which case the signer device 20 and the verifier device shall be capable of reading and writing to the IC card. FIG. 2 shows each process of the signature requester device 10 and the signer device 20 and an example of mutual communication, FIG. 3 shows an example of the process procedure in the signer device 20, and FIG. 4 shows a process procedure of the signature requester device 10. Examples of each are shown. Embodiment 1 In this embodiment, a method based on the Schnorr signature will be described. Let p and q be large prime numbers, and let q be divisible by p-1. g, Z_pIt is the source of the order q of. Z generated by g_pLet G be a subgroup of. The signer device has private keys x and y = g^xHold the public key y that satisfies mod p. H, H₁, H₂Is a hash function. H, H₁, H₂Is a hash function that accepts arbitrary input and outputs G elements. Let h be h = H (gThepTheqThey). z = H₁Let (gThepTheqThehThey). p, q, g, h, H, H₁, H₂And y, z shall be publicly available as a public key. In the following explanation, all operations shall be performed by mod p unless otherwise specified.

【0011】

First, the processing procedure of the signer device 20 will be described (see FIGS. 2 and 3). When the signature requester device 10 requests a signature (A0), the signer device issues a blind signature according to the following procedure. A1: Select (generate) the unique information rnd for issuing any of the signatures. For example, rnd may be a random character string that is different for each signature issued, or may be a serial number. A2: z₁: = H₁(rnd), z₂: = z / z₁Calculate mod p. This z (part of the public key) and z₁, z₂Is a temporary public key for each signature issuance. Temporary public key z and z₁Are both elements of G, so z = z₁ⁱThe relationship is always established, but z and z₁Finding i from is a so-called discrete logarithm problem and is difficult. That is, the temporary public keys z and z₁Is z = z₁ⁱSatisfies the relationship R, but the signer device 20 z in a way that the signer can be convinced that the signer does not know this relationship.₁Is being generated.

【0012】

A3: u, s₁, s₂Randomly select (generate), d from {0, ..., q-1}. A4: a: = g^u, b₁: = g^s1z₁^d, b₂: = h^s2z₂^dTo calculate. A5: rnd, a, b₁, b₂Is sent to the signature requester device 10. A6: Receive e from the signing requester device 10. A7: Find c: = e-dmod q. A8: Find r: = u-cxmod q. In other words, blind signature is done with the private key x.

【0013】

A9: r, c, s₁, s₂Is temporarily sent to the signing requester device 10 as a signature. After making a request to the signer device 20 (B0), the signing requester device 10 obtains a signature for the document m according to the following procedure (see FIGS. 2 and 4). B1: rnd, a, b₁, b₂Is received from the signer device 20. B2: b₁, b₂Make sure that is an element of G. Otherwise it terminates abnormally (b)₁Is an element of G, for example b₁^qIt can be confirmed by the fact that mod p = 1 holds. b b₂The same applies to). For example, b₁As for q, g₁, z₁Are both elements of G, so g^s1, z₁^dAre also elements of G, and the product of these is also an element of G.

【0014】

B3: z₁: = H₁Calculate (rnd). B4: v is randomly selected (generated) from {1, ..., q-1}. B5: U: = z^v, U₁: = z₁^v, U₂: = U / U₁To calculate. That is, the temporary public key z, z₁To disturb. Moreover, U and U₁Is z = zⁱThe same relationship as the relationship U = U₁ⁱWill be satisfied. Z, z so that such a relationship can be obtained₁Is disturbing. B6: t₁, t₂, t₃, t₄, t₅Is randomly selected (generated) from {0, ..., q-1}.

【0015】

B7: A: = ag^t1y^t2, B₁: = b₁^vg^t3U₁^t4, B₂: = b₂^vh^t5U₂^t4To calculate. That is, a, b₁, b₂Is disturbed, and the tentative signature is disturbed. B8: W is randomly selected (generated) from {0, ..., q-1}. B9: D: = z^wTo calculate. B10: E: = H₂(UTheU₁TheATheB₁B₂TheDThem) (challenge) is sought. B11: e: = Et₂-t₄Find mod q. That is, it disturbs E.

【0016】

B12: Send e to signer device 20. Since the signer device 20 processes steps A7 and A8 for this e, z, z₁, z₂Temporary signature based on r, c, s₁, s₂Will be generated. B13: Temporary signature r, c, s from signer device 20₁, s₂To receive. B14: F: = r + t₁mod q, K: = c + t₂mod q, T₁: = vs₁+ t₃mod q, T₂: = vs₂+ t₅mod q, L: = e-c + t₄Find mod q, N: = w-Lv mod q. That is, the tentative signature is disturbed so that it can be verified, and the disturbed temporary public key U is proved to be generated from the original public key. Generate certificates L and N. Since the disturbance is used as an exponent at the time of verification, it is performed by an addition process. In this way, the tentative signature s₁, s₂Disturbance against, z, z₁It is done in the same relationship as the disturbance to.

【0017】

B15: K + L = H₂(UTheU₁Theg^Fy^KTheg^T1U₁^LTheh^T2U₂^LThe z^NU^LThem) If mod q holds, proceed to the next step. If it does not hold, it ends abnormally. That is, it is verified that the signer device 20 has signed correctly. That is, g^Fy^K, g^T1U₁^L, h^T2U₂^LIs to confirm that the signer device 20 was made correctly, z^NU^LIs for confirmation that the signing requester device 10 correctly created U from z. B16: U, U like this₁, U₂U, U by the perturbation treatment of step B14 with the signature based on₁, F, K, T₁, T₂, L, N are output as a signature for the document m.

【0018】

The signature verifier device 30 is a signature-document pair (U, U).₁, F, K, T₁, T₂, L, N) m for K + L = H₂(UTheU₁Theg^Fy^KTheg^T1U₁^LTheh^T2(U / U₁)^LThe z^NU^LThem) Verify that mod q and U 1 hold. If it holds, the signature is considered correct, otherwise it is considered an invalid signature. If signature generation is successful K + L = c + t₂+ d + t₄= e + t₂+ t₄= E (mod q) g^Fy^K= g^{r + t1}y^{c + t2}= g^{r + cx}g^t1y^t2= ag^t1y^t2= A g^T1U₁^L= g^{vs1 + t3}U₁^{d + t4}= (b₁z₁^-d)^vg^t3U₁^{d + t4}= b₁^vg^t3U₁^t4= B₁h^T2(U / U₁)^L= h^{vs2 + t5}U₂^{d + t4}= (b₂z₂^-d)^Vh^t5U₂^{d + t4}= b₂^vh^t5U₂^t4= B₂z^NU^L= z^w-LvU^L= z^w= D And (U, U₁, F, K, T₁, T₂, L, N), m pass the verification. In addition, z^NU^LIt will be understood that = D to N, L are proofs that U is made from z.

【0019】

If U = 1 is acceptable, U = z^vTherefore, U = 1 is v = 0, and U = U₁ U₂Therefore, U = 1, U₁= 1, U₂Allows the relationship of = 1, y = g^xThere is a relationship, U = z^v= g^xo, U₁= g^x1, D₂= h^x2U = 1, U₁= 1, U₂Allowing = 1 is x₀= x₁= x₂Can be signed as = 0, i.e. x₀, x₁, x₂Anyone other than those who know or x will be able to sign. Therefore, in step B4, v is selected from {1, ..., q-1}, and if U = 1, it is not recognized as a signature by the legitimate signer device 20.

【0020】

The order of the variables input to the hash function may be any order as long as the procedure of the signing requester device 10 and the verifier device 30 is the same. In the above method, the temporary public key generation means of the signer device 20 z from any unique string rnd that is selected each time it is signed.₁= H₁Calculate (rnd), z and z₁Is used as a temporary public key. In addition, the temporary public key disturbing means of the signing requester device 10 randomly selects the disturbing component v, and U = z.^v, U₁= z₁^vLike z, z₁Disturb, U, U₁Is a disturbed temporary public key.

【0021】

Temporary public key (U, U) disturbed by the above procedure₁) Is the original temporary public key (z, z) used when issuing the signature₁), Log₂z₁= log_UU₁Have a relationship. However, someone other than the signing requester who does not know the disturbing component v (z, z)₁, U, U₁) Satisfies the relationship, which is a problem called Diffie-Hellman decision problem, which is considered to be computationally difficult. Therefore, even the signaturer has the signature sent to the verifier device 30. However, it is difficult to determine which signature requester device 10 the signature was issued to. In other words, it is difficult for the signer to deal with the signature document m and the signature requester. Therefore, the above method provides blindness as a blind signature.

【0022】

The signature issuing procedure of the above embodiment is y = g.^xThe private key x, or z₁= g^w1, z / z₁= h^w2W₁, w₂It is a zero-knowledge proof of knowing one of the private keys. w₁, w₂The zero-knowledge proof part for is (z) by multiplying both sides by v at the same time.₁)^v= g^w1v, (z / z₁)^v= h^w2vIn w₁, w₂It is possible to convert to zero-knowledge proof of. Therefore, U, U made according to the correct disturbance procedure₁Regarding, the signing requester device 10 is w₁, w₂Zero-knowledge proof (rnd, a) by signer device 20 without knowing₁, b₁, b₂, r, c, s₁, s₂) Can be converted to obtain a signature that passes the verification. However, U, U did not follow the original disturbance procedure.₁Is v = v₁V, v₁Against U = z^v, U₁= z₁^v1If so, s₁, s₂I don't know what to do with the disturbance. Therefore, it is not possible to convert the zero-knowledge proof by the signer device 20 to obtain a signature that passes the verification. Creating a signature that passes verification by means other than converting the zero-knowledge proof by the signer device 20 is y = g, as described above.^xThe private key x, or z₁= g^w1, z / z₁= h^w2W₁, w₂It is equivalent to performing a zero-knowledge proof that the signer knows any of the private keys, and no third party other than the signer can do this. Therefore, it can be said that all the signatures that pass the verification are linked to one of the signature issuing acts, and the number of signatures that pass the verification does not exceed the number issued.

【0023】

As shown in FIG. 5, the functional configuration of the signature requester device 10 is such that public keys such as g, p, q, y, h, and z are stored in the storage unit 101, and the transmission unit 102 and the reception unit 103 are provided. A signature request is issued to the signer device 20, and the signature device 20 issues a signature unique information rnd, a disturbed random number a, and a disturbed temporary public key b.₁, b₂Is received, in the element determination unit 104, b₁, b₂Is determined to be an element of the subgroup G, and if the determination is passed, the temporary public key arithmetic unit 105 z₁= H₁(rnd) is calculated, and in the temporary public key disturbance unit 106, the random number v Z from the random number generation unit 107._qU = z in U arithmetic unit 108 using^vBut U₁U in arithmetic unit 109₁= z₁^vBut U₂U in arithmetic unit 111₂= U / U₁Are calculated respectively.

【0024】

Random number generator 112 to t₁, ..., t₅ Z_qIs generated, and in the random number disturbance unit 113, A = ag in the A calculation unit 114.^t1y^t2But B₁B in arithmetic unit 115₁= b₁^vg^t3U₁^t4But B₂B in arithmetic unit 116₂= b₂^vh^t5U₂^t4Are calculated respectively. Random number w Z from random number generator 117_qBy D = z in D arithmetic unit 118^wIs calculated, and in the challenge generation unit 119, in the E calculation unit 121 E = H₂(UTheU₁TheAB₁B₂TheDThem) Is calculated, and e = Et in the e-calculation unit 122.₂-t₄It is disturbed with mod q, and e is transmitted from the transmitter 102 to the signer device 20.

【0025】

Temporary signature r, c, s from signer device 20₁, s₂Is received, in the tentative signature disturbance unit 124, F = w + t in the F calculation unit.₁mod q is K = c + t in K arithmetic unit 125₂mod q is T₁T in arithmetic unit 126₁= vs₁+ t₃mod q is T₂T in arithmetic unit 127₂= vs₁+ t₅Each mod q is calculated, and in the certificate generation unit 129, L = e-c + t in the L calculation unit 131.₄mod q is calculated by N calculation unit 132, and N = w-Lv mod q is calculated respectively. In the verification unit 133, in the hash calculation unit 134 H₂(UTheU₁Theg^Fy^KTheg^T1U₁^LR^T2U₂^LThe z^NU^LThem) Is calculated, K + L is calculated by the addition unit 135, the calculation result of K + L and the calculation result of the hash calculation unit 134 are compared by the comparison unit 136, and if they match, the signature composition unit 137 m. Its signature (U, U₁, F, K, T₁, T₂, L, N) is added and output from the transmitter 102.

【0026】

The processing of each of the above is executed by the control unit 138. Figure 6 shows an example of the functional configuration of the signer device 20. The private key x, a part of the public key, etc. are stored in the storage unit 201, and in the public key generation unit 202, y = g in the y calculation unit 203.^xmod p is h = H (gThepTheqThey) in h arithmetic unit 204, and z = H in z arithmetic unit 205.₁(gThepTheqThehThey) are calculated respectively. These are published, for example, through transmitter 206. When a signature request is received from the signing requester device 10 to the receiving unit 207, the temporary public key generating unit 208 generates the unique information rnd from the unique information generating unit 209 each time, and z₁Z in arithmetic unit 211₁= H₁(rnd) is z₂Z in arithmetic unit 212₂= z / z₁Are calculated respectively. Furthermore, random numbers u, s from the random number generator 213₁, s₂, d ( Z_q) Is generated, and in the random number disturbance unit 214, a = g in the a calculation unit 215.^uBut b₁In arithmetic unit 216 b₁= g^s1z₁^dBut b₂In arithmetic unit 217 b₂= h^s2z₂^dAre calculated respectively. Rnd, a, b as random numbers₁, b₂Is transmitted from the transmission unit 206 to the signature requester device 10.

【0027】

When the challenge e is received from the signature requester device 10 in the receiving unit 207, the signature unit 231 calculates c = ed mod q in the c calculation unit 232 and the r calculation unit 233 calculates r = u-c x mod q. , Temporary signature r, c, s₁, s₂Is transmitted from the transmission unit 206 to the signature requester device 10. The processing in each of the above units is controlled and executed by the control unit 234. Figure 7 shows an example of the functional configuration of the verifier device 30. The public key g, q, y, h, z is stored in the storage unit 301, and when the document m to be verified and its signature are input to the reception unit 302, it is temporarily stored in the storage unit 301 and the U determination unit. At 303, it is determined whether or not U is 1, and the result is supplied to the output unit 304. A calculation unit 305 g^Fy^KBut B₁G in arithmetic unit 306^T1U₁^LBut B₂Calculator 307 h^T2(U / U₁)^LHowever, in D calculation unit 308, z^NU^LAre calculated respectively. These calculation results and U, U¹, M are input to the hash calculation unit 309, and the hash function calculation of these bit concatenations is performed. Further, K and L are added by the addition unit 311 and these addition values and hash values are compared by the comparison unit 312, and the comparison result is supplied to the output unit 304. From the output unit 304, whether or not the signature is correct is transmitted to the verification requester through the transmission unit 314. The control unit 315 controls the execution of the processing of each unit. Embodiment 2 In the above, the document m to be signed is sent to the signer device 20, and the temporary public keys U and U whose signature m is disturbed in step B10 at the time of requesting the signature.₁The signer device 20 blindly signed the signature device 20 with the private key x, but according to the method of the present invention, the signature requester was blindly signed from the signer device 20 ( After receiving the (temporary signature), you can add a signature target at any time. Hereinafter, only the processes different from those of the second embodiment will be described.

【0028】

In the signing requester device 10, m is omitted in step B10, E = H₂(UTheU₁TheAB₁B₂TheD) Is calculated. Verification in step B15 is based on the following equation K + L = H₂(UTheU₁Theg^Fy^KTheg^T1U₁^LTheh^T2U₂^LThe z^NU^L) mod q In step B16, if the verification of step B15 is true (U, U)₁, F, K, T₁, T₂) S_pIs retained, and N is omitted. v and w to S_pKeep with. The following processing is performed when signing the signature target m (see Fig. 8).

【0029】

When B16-1: m is entered, M = H₃(z^wTheS_pThem) is calculated. H₃Is a hash function, Z_pIt outputs the elements of the subgroup G of, and is open to the public. B16-2: Calculate N'= w-Mvmod q. B16-3: S_p, M, N'are output as the signature for the signature target m. The certificates that prove that the disturbed temporary public key U was generated from the original public key z are L and N'.

【0030】

In the verifier device 30, S_p, M, N'and m are received and U 1 K + L = H₂(UTheU₁UTheg^Fy^KTheg^T1U₁^LTheh^T2(U / U₁)^LThe z^N'U^M) mod q M = H₃(z^N'U^MTheS_pThem) mod q If both of these equations hold, it is a valid signature for M. This is z^N'U^M= z^w-Mvz^vMIt is easy to understand from the fact that = D. For example S_pIs the electronic cash signed by the bank, and the signature target m is the electronic cash S that uniquely determines the shopping (transaction) by the electronic cash._pWhen paying by S_p, M, N'may be sent to the store equipment.

【0031】

As described above, when the signature target m is attached at any time, in the signature requester device 10, the random numbers a and b received from the signer device 20 in steps B10 and B11₁, b₂And disturbed temporary public key U, U₁Data e is created based on the above and sent to the signer device 20. The signer device 20 performs signature processing (steps A7 and A8) on the data e, and the signing requester device 10 can verify the tentative signature on the data e when outputting the signature target m and its signature. Disturbed to F, K, T, T₁, T₂(This may be done in advance), and the signature S of the signer device 20 for the data e._p= (U, U₁, F, K, T₁, T₂) Ask for this signature S_pThe information M that associates with the signature target m is generated, and the disturbed temporary public key is generated from the original public key by using the information M and the information for disturbing the temporary public key. Generate a certificate of existence N'and S_p, M, N'are the signatures for the signature target m.

【0032】

Therefore, the signature requester device 10 has a means for generating the above information M, a means for generating the certificate N', and S._pA means for outputting, M, N'as a signature for m will be provided. The signature requester device 10, the signer device 20, and the verifier device 30 may each be operated by executing a program by a computer. The above embodiment is the multiplicative group Z._p^*As with the El Gamal signature, the example constructed above can be implemented on any group where the discrete logarithm problem is difficult. For example, according to the purpose of this embodiment, it may be carried out with a finite group on an elliptic curve.

【0033】

[Effect of the invention]

As described above, according to the present invention, it is guaranteed that the signature requester device cannot obtain more correct signatures than the number issued by the signer device, and the signatures such as electronic cash and electronic tickets are inflated. Blind signatures can also be used in applications where is a problem.

[Simple explanation of drawings]

[Figure 1]

The figure which shows the structural example of the system to which this invention is applied.

[Figure 2]

The figure which shows the processing procedure of Embodiment 1 of this invention method.

[Fig. 3]

The flow chart which shows the processing procedure of the signer apparatus 20 in Embodiment 1. FIG.

[Fig. 4]

The flow chart which shows the processing procedure of the signature requester apparatus 10 in Embodiment 1. FIG.

[Fig. 5]

The block diagram which shows the functional structure of the signature requester apparatus 10 in Embodiment 1. FIG.

[Fig. 6]

The block diagram which shows the functional structure of the signer apparatus 20 in Embodiment 1. FIG.

[Fig. 7]

The block diagram which shows the functional structure of the verifier apparatus 30 in Embodiment 1. FIG.

[Fig. 8]

The flow chart which shows a part of the process of the signature requester apparatus 10 in Embodiment 2.

[Fig. 9]

The figure which shows the procedure of the conventional blind signature method.