JP3147373B2 - Multiple signature verification method - Google Patents

Description

Description: BACKGROUND OF THE INVENTION The present invention relates to a method for multiple verification of signatures, and particularly to electronically signing / sealing electronic documents by means of approval / decision, electronic voting system, etc. The present invention relates to a method for multiple verification of a digital signature.

[Conventional technology]

As a typical example of a digital signature scheme, Chaum (Ch
aum) rejection signature method (David Chaum, Hans van Antw
erpen, “Undeniable Signatures”, Crypto89 Abstracts,
pp.205-212, (1989), David Chaum “Zero-Knowledge
Undeniable Signatures ", EuroCrypto90 Abstracts, pp.4
19-426, (1990)). Chaum's digital signature method is a highly secure method that has the impossibility of diverting the signature and denial of denial. The improper use of the signature means that the correspondence (m, s) between the message m and the signature s does not prove that the signature is signed, and the signer uses the message m, which is the bit information for verification, and the signer. Only when the validity of the signature s correspondence obtained by calculation is proved by communication with the verifier, the validity of the signature s can be confirmed.

With a normal digital signature, the verifier can confirm the validity of the correspondence between the message m and the signature s without communicating with the signer, so that the signature is proved only by the correspondence (m, s) between the message m and the signature s. Will be used as

The non-repudiation property means that when the verifier seeks the validity of the correspondence (m, s) with the message m or the signature s, the signer himself can confirm and prove that the signature s is incorrect. It is necessary that the signer attempt to deny the validity of the correct signature s for the message m without success.

Chaum's rejection digital signature method is as follows.

(I) Registration of Key The signer A obtains a part of the inspection key α using the signature key (x) and the inspection key (g, p, α) (where g and α are public information and p is a prime number). α = g ^x (mod p) (1) The inspection key is made public, and the signature key is secretly managed. In equation (1), the remainder calculation a (mod p) is a random number a
By the prime number p. Therefore, equation (1) becomes
The remainder obtained by dividing g ^x by the prime number p is the value of α.

Chaum's signature method is secure due to the difficulty of the discrete logarithm problem that it is difficult to calculate x corresponding to a signature key satisfying α = g ^x (mod p) from α, g, and p when the divisor p is large. This is a signature method based on gender.

The verification key (g, p, α) of the verifier that verifies the signature s is managed in a public file of the center. If necessary, the verifier B inquires of the center and (g, p, α) α).

(II) Creation of Signature Signer A uses p and signature key (x) to generate message m
The signature s is computed by ^{s = m x (mod p)} ... (2) with respect to, and transmits to the verifier B with Mejji m. (Computations with remainders are shown, for example, in Ikeno and Koyama, “Modern Cryptography Theory,” IEICE, pp. 16-17, (1986)).

(III) Signature Inspection The verifier B communicates with the signer A to confirm that the signature s is a correct signature for the message m by using the inspection key by a confirmation procedure shown in the following (III-1). inspect. On the other hand, if the signature s is not a correct signature for the message m (hereinafter, the falsified signature is represented by f), the signer A certifies by the rejection procedure of (III-2).

(III-1) Confirmation procedure Step 1: Verifier B generates two random numbers a and b,
The communication text X calculated by ^{X = m a · g b (} mod p) ... (3), transmits a communication text X to the signer A.

Step 2: The signer A generates a random number q and sends a message (Y,
Z) is calculated as Y = X · g ^q (mod p) (4) Z = Y ^x (mod p) (5), and the message (Y, Z) is transmitted to the verifier B.

Step 3: Verifier B sends two random numbers a and b to signer A.

Step 4: The signer A examines whether satisfies the received random number a and b are X = m ^a · g ^b to the communication statement X received at step 1 (mod p) ... (6 ), is satisfied In this case, the pass is passed and the random number q is transmitted to the verifier B. If not, the processing is stopped as a failure.

Step 5: The verifier B receives the q, the message (Y, Z) received from the signer A in step 2, the random numbers a and b generated in step 1 are one component α of the inspection key, the message m and the signature. For s, Y = ^mq · gb ^{+ q} (mod p) (7) Z = s ^a · αb ^{+ q} (mod p) (8) Determines that the signature s is a correct signature of the signer A for the message m as a pass. If not, the processing is stopped as a failure.

Equation (7), it is Y = X · g ^q = the equal sign holds in ^{(8) (m a · g} b) g q = m a · g b + q (mod p) ... (9) Z = Y ^x = evidenced by ^{(m a · g b + q} ) x = (m x) a · (g x) b + q = s a · α b + q (mod p) ... (10).

(III-2) Denial procedure Step 6: Verifier B uses two random numbers e and random numbers β (0 ≦ β
≦ k) generates and communicates statement of (a, b) calculated by ^{a = m β · g e (} mod p) ... (11) b = f β · α e (mod p) ... (12), The message is sent to the signer A together with the message m and the signature f.

Step 7: Signer A retakes γ from 1 to k Is determined, and the value δ of the commitment function BC of γ
= BC (γ) to the verifier B. The commitment function is a function in which it is difficult to find γ satisfying BC (γ) = BC (γ ′) for γ. Commitment function BC
Is an example of the configuration of Brassard, Crepeau: “Non-transitive tra
nsfer of confidence: A perfect zeroknowledge intera
ctive protocol for SAT and beyond ", FOCS'86, pp188
At -195.

 Step 8: Verifier B sends random number e to signer A.

Step 9: The signer A receives (a, b) = ((m ^γ g ^e (mod p), f ^γ α ^e (mod p)) with respect to the received message (a, b) (14) If the condition is satisfied, γ is transmitted to the verifier β, otherwise the process is stopped.

Step 10: The verifier B checks that the received γ satisfies δ = BC (γ) and that γ = β holds. If the result of the check passes, it is confirmed that f is not a signature for the message m.

[Problems to be solved by the invention]

As described above, in the conventional Chaum denial signature method,
The signer's intervention is always required to confirm the validity of the correspondence (m, s) between the message m and the signature s. The problem of walking) is solved. However, when a plurality of verifiers verify the validity of the signature at the same time, the above procedure is repeated for each verifier, which is performed by the number of verifiers, which is inefficient.

SUMMARY OF THE INVENTION The present invention has been made in view of the above points, and provides a multiple verification method of a signature in which a signature can be verified without repeating the number of verifications even for a plurality of verifiers for one signer. With the goal.

[Means for solving the problem]

In a method of sequentially verifying a digital signature of a message digitized by a plurality of verifier devices, the center device includes:
The verification information of the signer device is registered in a public file, and the signer device uses a random number generator and a calculator with a remainder to input the generated random numbers g, p, x and a part of the random number as a remainder. Generate public information (g, p, α) that publishes the value α obtained as a result of performing the calculation α = g ^x (mod p) as a test key, register it in a public file of the center device, and signer device Transmits a signature s calculated using a computer with a remainder to each of a plurality of verifiers corresponding to the message m, and the final verifier transmits the message m, the generated first random numbers a2 and b2, and the verification information. A first message X ₂ = m ^a2 · g ^b2 (mod p) is calculated from the public information g in the above using a calculator with a remainder, and is transmitted to the intermediate verifier device together with the message m. verifier device, the second random number q2, u2, v2 Metropolitan generated using the communication text X ₂ and a random number generator of the first A remainder calculation X ₁ = X ₂ · g ^q2 · ^{mu 2} · g ^v2 is performed using a calculator with a remainder to generate a second message X _1, and the previous verifier device or signer together with the message m send apparatus to the signer apparatus, based on the second communication text X ₁ and message m received, with the remainder with calculator ^{_{Y 1 = X 1 · g q1}} (mod p) Z 1 = Y 1 x1 ( mod p) is calculated and transmitted to the intermediate verifier device as a third message (Y ₁ , Z ₁ ), and the intermediate verifier device calculates a remainder from the third message (Y ₁ , Z ₁ ). Calculate Y ₂ = Y ₁ / (m ^u2 · g ^v2 ) (mod p) using a calculator with a ^tag and Z ₂ = Z ₁ / (s ^u2 · α ^v2 ) (mod p) to obtain a fourth message by transmitting (Y _2, Z ₂₎ as the next verifier apparatus, final verifier apparatus receiving the communication statement said 4 (Y _2, Z ₂₎ is a first random number a2, b2 Transmitting to the intermediate verifier device, the intermediate verifier device receiving the first random a2, b2 against the communication sentence X ₂ of said first previously received inspects that it is legal if satisfying _{^{X 2 = m a2 · g b2}} (mod p), the second if pass The third random number (a1, b1) obtained by calculating a1 = a2 + u2 b1 = b2 + q2 + v2 by the adder from the random numbers q2, u2, v2 and the first random numbers a2, b2 is used as the previous verifier device or signer. A third random number (a1, b1) transmitted to the device and received by the signer device is the second message X received first.
_{For 1} , it is checked whether or not X ₁ = m ^a1 · g ^b1 (mod p) is satisfied. If it passes, a fourth random number q1 is transmitted from the signer apparatus to the intermediate verifier apparatus, and The verifier apparatus receives the third random number q1 together with the received fourth random number q1.
Message (Y ₁ , Z ₁ ) and the third random number (a1, b1) sent earlier
Is valid for the message m and the signature s by satisfying Y ₁ = m ^a1 · g ^{b1 + q1} (mod p) Z ₁ = s ^a1 · α ^{b1 + q1} (mod p) If it passes, it is determined that the signature is valid.

In a method in which a plurality of verifier devices sequentially verify a digital signature of an electronic message by a plurality of verifier devices, the center device registers verification information of the signer device in a public file, and Is a value α obtained as a result of performing a residue calculation α = g ^x (mod p) by using a random number generator and a calculator with a remainder and inputting the generated random numbers g, p, x and a part of the random numbers as inputs. the generated public information to publish (g, p, alpha) as the test key, registers the public file of the center apparatus, the signer apparatus using a remainder with calculator in response to the message m, Y ₂ = ^{M a2} · g ^{b2 + q} (mod p) The signature s calculated by Z ₂ = s ^a2 · α ^{b2 + q} (mod p) is transmitted to each of a plurality of verifiers, and the final verifier is a random number generator. And a calculator with a remainder to generate a first random number (e2, β2) and generate the first random number (e2, β2). ) And divided into a first component (e2) and the second component (.beta.2), the remainder calculator ^{a2 = m β2 · g e2 (} mod p) first communications by ^{b2 = f β2 · α e2 (} mod p) Calculate the sentence (a2, b2) and send it to the intermediate verifier with the message m. The intermediate verifier generates (e1, β1) using a random number generator and uses a calculator with a remainder. A1 = m ^β1 · a2 · ^ge1 (mod p) b1 = f ^β1 · b2 · α1 ^e1 (modp) The second message (a1, b1) is calculated and the signer device together with the message m And the signer device is represented by the relational expression (f / m ^x ) ^γ = b ₁ / a ₁ ^x (mod p), and when a message, a signature, and a message are given, the signer uses the signature key. By examining an integer value γ in a certain range (from 0 to 2k), a value of γ satisfying the relational expression (where m is a message, f is a signature, x is a test key,
a ₁ , b ₁ are the second message, (mod p) is the remainder of b ₁ / a ₁ ^x divided by the prime p), and the value of the commitment function δ = BC (Γ1) is transmitted to the intermediate verifier apparatus, and the intermediate verifier apparatus transmits the commitment function δ
= BC (γ1) using a subtractor to calculate δ2 = δ1−BC (β1), transmitting the calculated value δ2 to the next verifier apparatus, and finally The final verifier transmits the value generated as the first component e2 of the first random number to the intermediate verifier as the second random number, and the intermediate verifier transmits the value to the intermediate verifier. E = e1 + e2 is obtained from the third random number e using the second random number e2 and the random number e1 used when calculating the second message, and the third random number is transmitted to the signer apparatus. The device determines in advance the value of γ for the message m and the signature f for the second message (a1, b1) received first from the third random number e received from the intermediate verifier device. was relation (a1, b1) = {m γ1 g (mod p), f γ1 · α e (mod p)} inspects satisfying, between intermediate values of if passing the γ Transmitted to the witness apparatus, and the intermediate verifier apparatus obtains a fourth random number γ2 from γ2 = γ1-β1 using a subtractor from the γ1 and the random number β1 used in calculating the second message. , The fourth random number γ2 and the first
With remainder with calculator and a comparator that communication sentence (a2, b2) is not signed f for the message m, (a2, b2) = {m γ2 · g e2 (mod p), f γ2 · α e2 (Mod p)｝ is satisfied, and if passed, the fourth random number γ2
Is transmitted to the final verifier apparatus, and the final verifier apparatus transmits the fourth
It is confirmed that the random number γ2 of the first random number is equal to the second component β2 of the first random number. If the random number γ2 passes, it is determined that the signature f is not a signature for the message m.

[Action]

According to the present invention, the signer device generates a signature key by using a random number, calculates a value of the key and a part of the inspection key, and registers the calculated value in a public file of the center device. The signer apparatus calculates a signature for a verification message, which is bit information for verification, and transmits the signature to a plurality of verifier apparatuses. The plurality of verifier devices calculate and convert the message from the signer device using the random number for each verifier device, and transmit and receive the message between the verifier devices and between the signer device and the verifier device. Check that the signature is valid for the device. If the signature is not a correct signature for the verification message, the signer denies the signature to the verifier using the commitment function.

〔Example〕

FIG. 1 shows a system configuration diagram of an embodiment of the present invention.
In the figure, the center apparatus 100 is connected to the signer apparatus 200 and a plurality of verifier apparatuses 300 to 800 via a communication path 400 for registering information in the center apparatus 100. 800 is connected in series via a communication path 500 for communicating messages and the like, and performs verification sequentially from the verifier 300.

FIG. 2 shows the contents of a public file according to one embodiment of the present invention. The center apparatus 100 has a public file, and the signer apparatus 100 registers public information in the public file.

In this embodiment, a method performed by one signer apparatus 200 and two verifier apparatuses 300 and 800 via one center apparatus 100 will be described.

One of the two verifier devices is an intermediate verifier device 30.
0, and the other is the final verifier device 800.

FIG. 4 shows a signature creation confirmation and denial procedure of the signer apparatus according to one embodiment of the present invention. Signer device 200 is a random number generator 21
0, with calculators 220, 250, 270 with remainder, gamma detector 280, BC calculator 290, and the final verifier device 800 at the first transmission
Except that the signature s is transmitted to the intermediate verifier device 300.

FIG. 5 shows a procedure for confirming an intermediate verifier apparatus according to an embodiment of the present invention. FIG. 6 shows a procedure for rejecting an intermediate verifier device according to an embodiment of the present invention.

The verifier 300 is a random number generator 310, calculators with remainders 320, 330,
340,360,390, adder 350,370, comparator 345,365, subtractor 3
85, equipped with BC calculator 380. In this embodiment, the intermediate verifier apparatus 300 transmits and receives the signer apparatus 200 and the final verifier apparatus 800.

FIG. 7 shows a verification procedure of the final verifier apparatus 800. The verifier device 800 is a random number generator 810, calculators with remainders 820, 830, B
It has a C calculator 840. In this embodiment, the final verifier device
800 performs transmission and reception with the intermediate verifier device 300.

Next, the procedure of key registration to confirmation and rejection together with the communication sequence of the embodiment of the present invention shown in FIG. 3 will be described.

(I) Key Registration The signer apparatus 200 includes a random number generator 210 that generates a random number for registering a key, and a calculator 220 with a remainder that generates a signature key and an inspection key using the generated random number. Have.

Step 11: First, when the signer apparatus 200 joins the system, three random numbers g, p, x are generated using the random number generator 210, and the signature key (x) and a part of the inspection key ( g, p), and a part (α) of the inspection key is calculated from x, p, g by the calculator 220 with a remainder using α = g ^x (mod p) (15). Center device 100 with part of key
Register to the public file of. The public file is the second
As shown in the figure, public information (g, p, α) is held for each signer apparatus.

(II) Creation of Signature Hereinafter, a case where the signer apparatus 200 creates the signature s will be described.

Step 12: The signer apparatus 200 uses the calculator 230 with the remainder to publish the message m from the public information p generated in step 1 and the signature key (x), and s = ^mx (mod p) (16) ) To calculate the signature s and transmit it to the verifier devices 300 and 800.

(III) Inspection Hereinafter, a case will be described where two of the verifier devices 300 and 800 inspect the signature s of the message m.

By communicating with the final verifier device 800 or the signer device 200, the intermediate verifier device 300 verifies that the signature s is the correct signature of the signer 200 for the verification message m by the following procedure.

(III-1) Confirmation Procedure Step 13: The final verifier 800 shown in FIG. 7 generates two random numbers a2 and b2 using the random number generator 810. Then final verifier device 800 message m using a modulo-conditioned calculator 820, a g from the communication sentence X ₂ is a part of the inspection key ^{_{X 2 = m a2 · g b2}} (mod p) ... (17 ), And sends it to the verifier device 300 together with the message m.

Step 14: The verifier 300 shown in FIG.
Are used to generate three random numbers q2, u2, v2. Next step
The transmitted communication text X ₂ and the message m and the three random numbers in the remainder with calculator 320 at 13, the communication text _{X 1 X 1 = X 2 ·} g q2 · m u2 · g v2 (mod p) ... (18 ) Is calculated and transmitted to the signer apparatus 200 together with the message m.

Step 15: The signer apparatus 200 shown in FIG.
Using 0, a random number q1 is generated. Then communication text X ₁ sent by the verifier device 300 in step 14, communication text by the message m and a random number q1 (Y _1, Z ₁₎ with the remainder with calculator _{250 Y 1 = X 1 · g} q1 (mod p) ... (19) calculated by ^{_{Z 1 = Y 1 x1 (mod}} p) ... (20), the verifier apparatus as the communication sentence (Y _1, Z ₁₎ 300
Send to

Step 16: The verifier apparatus 300 shown in FIG. 5 uses the calculator with remainder 330 to obtain the message (Y ₁ , Z ₁ ) obtained from step 15;
The message (Y ₂ , Z ₂ ) is converted into Y ₂ = Y ₁ / (m ^u2 · g ^v2 ) (mod p) by the signature s obtained from step 12 (21) Z ₂ = Z ₁ / (s ^u2 · α ^v2 ) (mod p) ... (22) and transmit to the verifier apparatus 800.

Step 17: The verifier apparatus 800 transmits the two random numbers a2 and b2 generated by the random number generator 810 to the verifier apparatus 300.

Step 18: The verifier device 300 in FIG. 5 is a calculator with a remainder.
340 a comparator 345 X to the communication statement X ₂ in which two random numbers a2, b2 received from the verifier apparatus 800 in step 17 is received in step 13 using a ₂ = m ^a2 · g ^b2 a (mod p) It is checked that the condition is satisfied, and if the condition is satisfied, the result is determined as pass. The signer device 200 obtains the calculation result (a1, b1) obtained by calculating in the adder 350 according to a1 = a2 + u2...
Send to If the above condition is not satisfied, the processing is stopped as a failure.

Step 19: Signer device 200 in FIG. 4 is a calculator with a remainder.
A1 received from the verifier apparatus 300 using the comparator 270 and the comparator 275
If b1 is the communication statement X ₁ received in step 14, and checks that satisfy ^{_{X 1 = m a1 · g b1}} (mod p) ... (25), a pass if they meet, the random number q1 This is transmitted to the verifier device 300. If not, the processing is stopped as a reject.

Step 20: The verifier 300 in FIG. 5 is a calculator with a remainder.
Using the 360 and the comparator 365, in step 19 the signer device 200
, The message (Y ₁ , Z ₁ ) received in step 5, a1 sent to the signer device 200 in step 18,
b1 satisfies Y ₁ = m ^a1 · g ^{b1 + q1} (mod p)... (26) for the message m and the signature s (2) Z ₁ = s ^{a1 .α b1 + q1} (mod p). If the inspection satisfies the condition, it is judged as a pass, and it is determined that the signature s is a valid signature of the signer for m.
In addition, if it passes, the adder 370 is used to transmit q1 + q2 to the verifier device 800 using the random number q1 from the signer device 200 and q2 from the random number generator 310. On the other hand, if the inspection does not satisfy the condition, it is rejected and the process is stopped.

Step 21: The verifier device 800 in FIG. 7 is a calculator with a remainder.
Using the 830 and the comparator 835, in step 20, the verifier 300
Q (= q1 + q2), the message (Y ₂ , Z ₂ ) previously received from the verifier device 300, and the verifier device 300
A2 and b2 transmitted to the message m and the signature s, Y ₂ = m ^a2 · g ^{b2 + q} (mod p) (28) Z ₂ = s ^a2 · α ^{b2 + q} (mod p) (29) ) Is checked, and if satisfied, it is judged as pass, and it is determined that the signature s is a valid signature of the signer apparatus 200 for the message m.

(III-2) Denial procedure Step 22: Verifier device 800 in FIG.
, A random number e2 and a random number β2 (0 ≦ β2 ≦ k) are generated, and the message (a2, b2) is calculated using the calculator 820 with the remainder by a2 = ^mβ2 · ^ge2 (mod p). 30) b2 = f ^β2 · α ^e2 (mod p) (31) The message m and the signature f (here, the signature f is a falsified signature) are calculated together with the verifier device 300.
Send to (Where k is a security parameter,
This is a value agreed in advance by the signer apparatus 200, the verifier apparatus 300, and the verifier apparatus 800.

Step 23: The verifier device 300 shown in FIG.
, A random number e1 and a random number β1 (0 ≦ β1 ≦ k) are generated, and the message (a1, b1) is converted to a1 = ^mβ1 · a2 · ^ge1 (mod p) using the calculator 320 with a remainder. (32) b1 = f ^β1 · b2 · α1 ^e1 (mod p) (33) The signer device 20 is calculated together with the message m and the signature f.
Send to 0.

Step 24: The signer apparatus 200 in FIG. 4 uses the γ detector 280 to re-take γ1 from 0 to 2k. Γ1 that satisfies is satisfied, and the value δ1 = BC (γ1) of the commitment function of γ1 is determined using the BC calculator 290.
Send to 0.

Step 25: The verifier apparatus 300 in FIG. 6 obtains BC (β1) using the BC calculator 380, and δ2 = δ using the subtractor 380.
1-BC (β1) is calculated and the calculation result is δ2.
Send to 800.

Step 26: The verifier device 800 in FIG.
Is transmitted to the verifier device 300.

Step 27: The verifier device 300 shown in FIG.
The e = e1 + e2 is calculated by using the adder 370 with the random number e1 generated in step (1) and the random number e2 received from the verifier device 800 in step 26, and the calculation result e is transmitted to the signer device 200.

Step 28: The signer apparatus 200 uses the calculator with remainder 270 and the comparator 275 to convert e (= e1 + e2) received from the verifier apparatus 300 in step 27 into the message (a1, b1) by: (a1 ^{, b1) = {m γ1 ge} (mod p), f γ1 · α e (mod p)} verifies that meets ... (35), a pass if they meet,
γ1 is transmitted to the verifier device 300. If not, it is rejected and the process is stopped.

Step 29: The verifier apparatus 300 in FIG. 6 obtains γ2 = γ1−β1 using the subtractor 385, and using the calculator 390 with the remainder and the comparator 395, (a2, b2) = ｛ ^{mγ2g e2} (mod p), f ^γ2 · α ^e2 (mod p)｝ ……………………………… (36) Pass if satisfied, signature f
Is not a signature for message m.
Further, γ2 is transmitted to verifier apparatus 800.

Step 30: The verifier device 800 in FIG. 7 uses the BC calculator 840 and the comparator 845, and the γ2 received from the verifier device 300 in Step 29 satisfies δ2 = BC (γ2). (37) is verified using, and if it passes, it is confirmed that the signature f is not a signature for the message m.

 Note that the commitment function BC used in the present embodiment is one that satisfies BC (γ1) + BC (γ2) = BC (γ1 + γ2).

〔The invention's effect〕

As described above, according to the present invention, when a plurality of verifiers perform multiple verifications, for example, when there are five verifiers, it is necessary to prove the validity of the signature to all five verifications in a single verification procedure. Can be. Therefore, the time for verification can be greatly reduced, which is extremely useful in practice.

[Brief description of the drawings]

FIG. 1 is a system configuration diagram of one embodiment of the present invention, FIG. 2 is a diagram showing a public file of one embodiment of the present invention, FIG. 3 is a diagram showing a communication sequence of one embodiment of the present invention, FIG. 4 is a diagram showing a signature creation / confirmation and rejection procedure according to an embodiment of the present invention. FIG. 5 is a diagram showing a confirmation procedure of an intermediate verifier apparatus according to an embodiment of the present invention. FIG. 7 is a diagram showing a procedure for rejecting an intermediate verifier device according to an embodiment of the present invention. FIG. 7 is a diagram showing a procedure for verifying a final verifier device according to an embodiment of the present invention. In the figure, 100: center device, 150: public file, 200: signer device, 210, 310, 810: random number generator, 220, 230, 270, 3
20,340,360,820,830 ... Calculator with remainder, 275,345,365,
395 ... Comparator, 385 ... Subtractor, 380 ... BC calculator, 35
0,370 …… Adder, 300,600,700,800 …… Verifier device, 40
0, 500 ... Communication channel.

Continuation of the front page (58) Fields investigated (Int. Cl. ⁷ , DB name) G09C 1/00-5/00 H04K 1/00-3/00 H04L 9/00 C06F 15/00 INSPEC (DIALOG) JICST file (JOIS) WPI (DIALOG)

Claims (2)

(57) [Claims] 1. A method for sequentially verifying a digital signature of a message digitized by a plurality of verifier devices, wherein a center device registers verification information of the signer device in a public file, and the signer device generates a random number. Using a calculator and a calculator with a remainder,
With the generated random numbers g, p, x and a part of the random numbers as inputs,
Generates public information (g, p, α) that publishes the value α obtained as a result of performing the remainder calculation α = g ^x (mod p) as a test key, registers it in a public file of the center device, and signer The device transmits a signature s calculated using a computer with a remainder to each of the plurality of verifiers in response to the message m, and the final verifier transmits the message m and the generated first random number.
A first message X ₂ = m ^a2 · g ^b2 (mod p) is calculated from a2, b2 and the public information g in the verification information using a calculator with a remainder, and the message verb is used as an intermediate verifier. The intermediate verifier transmits a remainder X using a calculator with a remainder to the first message X ₂ and a second random number q2, u2, v2 generated using a random number generator. ₁ = X ₂ · g ^q2 · m ^u2 · g ^v2 to generate a second message X ₁ and send it to the previous verifier device or signer device together with the message m. Based on the received second message X ₁ and message m, a calculator with remainder calculates Y ₁ = X ₁ · g ^q1 (mod p) Z ₁ = Y ₁ ^x1 (mod p) The message is transmitted to the intermediate verifier as a message (Y ₁ , Z ₁ ), and the intermediate verifier uses a calculator with a remainder from the third message (Y ₁ , Z ₁ ) to obtain Y ₂ = ^{_{Y 1 / (m u2 · g}} v2) (mod p) Z ₂ = Z ₁ / (s ^u2 · α ^v2 ) (mod p) is calculated and transmitted to the next verifier apparatus as the fourth message (Y ₂ , Z ₂ ), whereby the fourth message is obtained. The final verifier apparatus that has received (Y ₂ , Z ₂ ) transmits the first random number a2, b2 to the intermediate verifier apparatus, and the intermediate verifier apparatus receives the received first random number a2, b2 There inspects that it is justified in the case of satisfying the communication sentence of the first previously received X ₂ with respect to _{^{X 2 = m a2 · g b2}} (mod p), a second random number q2 if passed, u2 , v2 and the third random number (a1, b1) obtained by calculating a1 = a2 + u2 b1 = b2 + q2 + v2 from the first random number a2, b2 by the adder to the previous verifier device or signer device. , checks third random number received by the signer apparatus (a1, b1) is the communication sentence X ₁ of the second previously received satisfies _{^{X 1 = m a1 · g b1}} (mod p) And if it passes, the fourth random number q1 is sent from the signer device to the Transmitted to the verifier apparatus between, the intermediate of the verifier device, a third random number transmitted third communication sentence received with a fourth random number q1 received (Y _1, Z ₁₎ and above (a1, b1) is valid for the message m and the signature s by satisfying Y ₁ = m ^a1 · g ^{b1 + q1} (mod p) Z ₁ = s ^a1 · α ^{b1 + q1} (mod p) A signature verification method that, if passed, determines that the signature is valid. 2. A method for sequentially verifying a digital signature of a message digitized by a plurality of verifier devices by a plurality of verifier devices, wherein the center device registers verification information of the signer device in a public file, The signer device uses a random number generator and a calculator with a remainder,
With the generated random numbers g, p, x and a part of the random numbers as inputs,
Generates public information (g, p, α) that publishes the value α obtained as a result of performing the remainder calculation α = g ^x (mod p) as a test key, registers it in a public file of the center device, and signer The apparatus uses a calculator with a remainder in response to the message m, and calculates the signature s calculated by Y ₂ = m ^a2 · g ^{b2 + q} (mod p) Z ₂ = s ^a2 · α ^{b2 + q} (mod p) The final verifier device generates a first random number (e2, β2) using a random number generator and a calculator with a remainder, and sends the first random number (e2,
β2) is divided into a first component (e2) and a second component (β2),
A2 = m ^β2 · a2 · ^ge2 (mod p) b2 = f ^β2 · b2 · α1 ^e2 (mod p) is calculated by the remainder calculator, and the first message (a2, b2) is calculated along with the message m. And the intermediate verifier generates (e1, β1) using a random number generator and a1 = m ^β1 · ^ge1 (mod p) b1 = The second message (a1, b1) is calculated by f ^β1 · α ^e1 (mod p) and transmitted to the signer device together with the message m, and the signer device obtains the relational expression (f / m ^x ) ^γ = b ₁ / a ₁ ^x (mod p), given a message, signature, or message, by examining an integer value γ in a certain range (from 0 to 2k) using a signature key. The value of γ that satisfies the relational expression (where m is a message, f is a signature, x is a test key,
a ₁ , b ₁ are the second message, (mod p) is the remainder of b ₁ / a ₁ ^x divided by the prime p), and the value of the commitment function δ = BC (Γ1)
Is transmitted to the intermediate verifier, and the intermediate verifier transmits a commitment function δ = BC (γ
Using a subtractor on the value calculated using 1), δ2 = δ1-BC (β1) is calculated, and the calculated value δ2 is transmitted to the next verifier device, and finally the final verifier device The final verifier transmits the value generated as the first component e2 of the first random number as the second random number to the intermediate verifier, and the intermediate verifier transmits the value to the intermediate verifier by an adder. The third random number e is used as the second random number e2 and the random number used in calculating the second message.
According to e1, e = e1 + e2 is obtained, and the third random number is transmitted to the signer apparatus. The signer apparatus receives the third random number e received from the intermediate verifier apparatus in the second message (a1 , b1)
the value of γ is, the message m, a predetermined relationship with respect to signature f (a1, b1) = { m γ1 g (mod p), f γ1 · α e (mod p)} inspects satisfying, If it passes, the value of γ is transmitted to the intermediate verifier, and the intermediate verifier uses a subtracter from γ1 and the random number β1 used in calculating the second message, and γ2 = γ1 −β1 is used to determine a fourth random number γ2, and the fourth random number γ2 and the first random number γ2 are calculated.
With remainder with calculator and a comparator that communication sentence (a2, b2) is not signed f for the message m, (a2, b2) = {m γ2 · g e2 (mod p), f γ2 · α e2 (Mod p)｝ is satisfied, and if passed, the fourth random number γ2
Is transmitted to the final verifier device, and the final verifier device confirms that the fourth random number γ2 is equal to the second component β2 of the first random number. A signature multiple verification method characterized by determining that the signature is not valid.