JP3331321B2 - Method for collectively verifying a plurality of digital signatures, apparatus therefor and recording medium recording the method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a system for approval / payment of an electronic document, in which a plurality of signers are individually or multiplexed or superimposed on one or a plurality of documents. The present invention relates to a method and an apparatus for performing signature / stamping, and a verifier to collectively verify those signatures, and a recording medium on which the method is recorded.

[0002]

2. Description of the Related Art As a typical example of a digital signature system,
RSA encryption (RL Rivest, et.al, "AMethod for Obtain
ing Digital Signatures and Public-Key Cryptosystem
s ", Communications of the ACM, Vol. 21, No. 2, pp. 1
20-126, (1978)). The RSA encryption is as follows.

The signer A has a signature key (d, N) and a verification key.
Generate (e, N) such that they satisfy N = P × Q e × d 1 (mod L) where L = LCM ｛(P-1), (Q-1)｝, and publish the inspection key The secret key is managed secretly. Here, LCM {a, b} represents the least common multiple of integers a and b, and P and Q are two different large prime numbers. Ab (mod L) indicates that ab is a multiple of L.

[0004] The RSA cryptosystem is a cryptosystem having a security basis that it is difficult to factor N when N is large.
It is difficult to obtain the d component of the secret signature key from the published inspection key (N, e). The verifier B manages the inspection key (e, N) of the signer A in combination with the personal identification information (ID) of the signer A. The center often manages the inspection key as a public information management book.

[0005] The signature function D and verification function E is defined by ^{D (m) = m d mod} NE (y) = y e mod N. It can be shown that E (D (m)) = m holds for an integer m satisfying 0 ≦ m <N. Where a mod N is a
Represents the remainder when divided by.

The digital signature system using the RSA encryption is as follows. The signer A applies a secret signature function D to f (m) generated from the document m using the one-way function f.
Is applied to generate a signature y with y = D (f (m)), and a combination of the personal identification information (ID) of the signer A, the document m, and the signature y (ID, m, y) is added to the signed message. To the verifier B. Verifier B,
Searching the public information management book in which the inspection key is registered using the signer A's ID as a key, obtaining the information (e, N) of the signer A, and using it, from the y component of the signed message E determine the (y) = y ^e modN, inspect it matches the f (m) obtained using a one-way function f from the m. If E (y) = f (m) holds, the signature function D (m)
= m ^{d Since} the only person who knows modN, that is, the person who knows d is the true signer A, the sender is the real A and (ID, m,
It is determined that y) has not been tampered with.

Here, f is a one-way function when x
This function is easy to calculate f (x) from f (x), but it is difficult to calculate x from f (x). f is a high-speed conventional encryption device, for example, DES encryption (Data Encryption Standard, Fed
eral Information Processing Standards Publication 4
6, 1977). If a high-speed component is used, the calculation time of f can be almost ignored. The one-way functions f and h used hereinafter can calculate their values f (x) and h (x) for x having an arbitrary data length.

The integer N used in the RSA encryption is usually about 308 decimal digits (1024 bits),
The component is also about 1024 bits. Here, in order to calculate the signature function D, a square multiplication algorithm is well known, which requires an average of 1536 multiplications of a 308-digit integer (including the remainder calculation by the modulus N). Significant amount of signature creation processing.

The square multiplication algorithm for calculating x ^a mod N is as follows. Step S1: z = 1 Step S2: The following processing steps S2-1 and S2-2 are repeatedly executed from 0 to | a | -1 for the subscript i.
(It is assumed that | a | represents the number of bits of a.) Step S2-1: z ′ = z ² mod N Step S2-2: If a _i = 1, update z = z′x mod N and z The process returns to step S2-1 (a _i is the value of the i-th bit of a, 0 or 1). If a _i = 0, the process directly returns to step S2-1 without updating z. Step S3: Output z.

The square multiplication algorithm is, for example, Square-an
d-multiply algorithm, Douglas R. Stinson: "CRYPTOGR
APHY, Theory and Practice ", CRC Press p.127, 1995
Is shown in As a method for solving the problem of an increase in the amount of processing for creating a signature in the signer device, interactive proof (Fiat and
Typical examples are the Shamir method and the Schnorr method) (A.Fi
at, andA.Shamir ,: "How to prove yourself: practica
l solutions to identification and signature problem
s ", Advances in Cryptology-Crypto 86, Springer-Ver
lag, pp.186-194. CP Schnorr: "Efficient Identifi
cation and Signatures for Smart Card "Advances in C
ryptology-EUROCRYPT'89, Springer-Verlag, pp.235-25
1 and M. Tompa and H. Woll: "Random Self-Reducibili
ty and Zero Knowledge Interactive Proofs Possesion
of Information, "Proceedings of the28th IEEE Symp
osium on the Fundation of computer Science, pp. 47
2-482 (1987)).

The digital signature according to the Schnorr method will be described below. For a reliable center, q is p-1
, And two large prime numbers p and q having a relationship of divisors and an integer g (Z / pZ) ^* = {1, 2,..., P-1} having an order q. Step S1: The signer A obtains a random number s∈ (Z / qZ) = ｛0, 1,
2, ..., and generates a q-1}, and calculates the public information I in ^{I = g s modp (1)} , personal identification information (ID) and exposes a set of I.

The signer A proves to the verifier B that the document m is authentic by the following procedure. Step S2: The signer A generates a random number r∈ (Z / qZ) and calculates X = g ^r modp (2). Step S3: The signer A calculates the integer e∈ (Z / qZ) by the operation of e = f (X, m) (3) using the one-way function f. Step S4: The signer A generates a signature y by an operation of y = (r + es) modq (4), and sends {ID, m, X, y} to the verifier B as a signed communication message. Step S5: The verifier B calculates the integer e∈ (Z / qZ) by the calculation of e = f (X, m) (5) using the one-way function f. Step S6: The verifier B checks that g ^y ≡ XI ^e (modp) (6) holds. Here, I is public information corresponding to the identification information ID.

From the way of creating ^y , g ^y ≡g ^r (g ^s ) ^e ≡XI ^e (modp)
Therefore, if the above-mentioned inspection is passed, the verifier B recognizes that the document m is transmitted from A. In the above steps S2 to S4, the integers e∈ (Z / qZ) and y∈ (Z / q
X) (Z / pZ) ^*
, And if e = f (X, m) holds, then {ID, X, m, y}
Is a signed message, the signature is successfully forged. However, the probability that the check formula e = f (m, X) is 1 / q,
The amount of computation required to forge a signature is determined by q. Hereafter, p
Is represented by | p |.

According to Schnorr's scheme, the signature creation process at the sender is performed by multiplying an integer of | p | bits (including the remainder calculation in the modulus p) 3/2 | q | Multiplication (including the remainder calculation in modulo q)
Once, and the addition of an integer of | q | bits (including the remainder calculation in modulo q) is performed once. Here, the signed message is {ID, X, m, y}, but it is also possible to use {e, instead of X} to {ID, e, m, y}. At this time, X is calculated by X = (g ^y ) (I ^e ) ^-1 modp, and e = f (X, m)
It is checked that the relational expression holds. ｜ e ｜
When <| X |, the latter can shorten the message.

Here, consider a case where a plurality of signers superimpose a signature on different documents. As a typical example in which the superimposed signature method is used, the public information manager CA determines the validity of the correspondence between the signer's public identification information ID and the public information I by using a digital signature for the document (ID, I), T _{= D CA (ID, I)} , ensured by, it sends the digital signature T signer, signer signed using the secret information corresponding to the public information I for a set of signatures T and document m D It is conceivable that the _ID (m, T) is created and transmitted to the verifier, and the verifier verifies the signature D _ID (m, T) by the signer and the signature T by the public information manager.

At this time, in the superimposed signature scheme, there are problems in that the processing amount of signature generation by the signer, the processing amount of signature verification by the verifier, and the increase in signature components are reduced. The digital signature using the RSA cryptosystem, each signer i sequentially signature applied to a document m _{i, i.e., D L (m L, ...} , D 2 (f (m 2, D 1 (f (m 1 ))))…)
Thus, a superimposed signature can be realized. At this time, there is a problem that the processing amount of signature generation is large.

On the other hand, when the Schnorr method is simply applied, a method of adding information of {ID _i , X _i , y _i } to a document (m ₁ ,..., Mi _i , _mi ) for each signer i Can be considered. Where the X _i component is | p
Bits, the y _i component is | q | bits. When L signers sign, finally (│p│ + │q│) × L bits of information are the message, ie, the L person's ID and the document (m ₁ ,..., _{M L} )
Is added to An increase in signature components (X component, y component) is a problem.

Next, consider application to a multiple signature in which a plurality of signers sequentially sign one document. RSA
In the digital signature using an encryption system, a multiple signature can be realized by sequentially applying a signature to the signature y of the message {ID, m, y} (that is, D _L ... D ₁ (f (m))). At this time, there is a problem that the processing amount of signature generation is large. On the other hand, if the Schnorr method is simply applied, a method of adding information of {ID, X, y} to the message m for each signer can be considered. Here, the X component is | p | bits, and the y component is | q | bits. When the L signers sequentially sign, the information of (| p | + | q |) × L bits is finally added to the message (the IDs of the L persons and the document m).
An increase in signature components (X component, y component) becomes a problem.

Conventionally, with respect to a multiple signature for sequentially signing the same document, the X component and the y component can be reduced to one by accumulating the values of the X component and the y component for each signature creation process. A signature method has been proposed (K. Ohta and TO
kamoto: "A Digital Multisignature Scheme Based on
the Fiat-Shamir Scheme, "Advances in Cryptology-AS
IACRYPT'91, Springer-Verlag, pp.139-148). But,
In this method, since it is necessary to carry a message twice (two rounds) between a plurality of signers, (2L-1) times of communication is required to perform multiple signatures by L persons. An increase in the number of times becomes a problem.

In a multi-signature requiring two rounds, even if an attempt is made to expand the document to be signed when the signer differs for each signer,
Superimposed signatures cannot be realized. This is because it is not possible to generate a signature for the document (m ₁ , m ₂ ) after generating a signature for the document m ₁ because all documents, for example, m ₁ and m ₂ , need to be determined in the first round. is there. A method of transforming ElGamal signatures into multiple signatures has been proposed (Jun Shinbo: "A modification of ElGamal signatures suitable for multiple signatures" SCIS94-2C). However, the reference does not consider the use of signature superposition. With the proposed modified method, it is difficult to make the Schnorr signature one cycle, and further, there is a problem that the security of any of the proposed methods cannot be strictly evaluated (see the above document). Conclusion on p.9).

In an application system using a digital signature, a situation in which a plurality of signatures are collected at one place and a verification process is executed often occurs even when a superimposed signature or a multiple signature is not performed. For example, there is a case where the electronic money is returned to the issuing institution to verify the validity of the electronic money. In such a case, as described above, the use of the interactive proof can significantly reduce the amount of processing for creating a signature. However, the amount of processing for signature verification may increase. For example, comparing Schnorr's method with the RSA method, the Schnorr's method requires | p | -bit integer multiplication (including the remainder calculation in modulo p) on average 3 | q | / 2
However, in the RSA method, e = 3 can be set without impairing security, so that multiplication by an integer of | N | bits (including the remainder calculation in the modulus N) is performed twice.

Here, consider the above digital signature scheme in which a plurality of signatures are collectively verified. The digital signature using the RSA cryptosystem, to be treated of signature generation is large has been a problem, and because using the value N _i different laws for each signer, batch verification of N _i and N _j Probably not processed.

When the Schnorr method is simply applied, the signer i
The message m _i to _{{ID i, X i, y} i} and signed by adding information. Here, the X _i component is | p | bits, and the y _i component is |
q | bits. When each of the L signers i signs a different document _mi (1 ≦ i ≦ L), if L verification equations are independently checked, the processing amount for the inspection is L times. Therefore, by accumulating the value of the y component, the inspection formula is

[0024]

(Equation 22) _{^{However, y '= Σ L i =}} 1 y i and _{e i = f (X i,} m i), and a method of one has been proposed. For example, Literature: Ota, Okamoto: "Multi-signature method using Fiat-Shamir method", IEICE Spring Conference (1989), A-277 (1989), Literature:
Harada, Tatebayashi: "Efficient n-variable modular exponentiation and its application", IEICE technical report ISEC91-40 (199)
1).

In these methods, the signer can forge the signature of another signer, and thus a security problem arises. This problem is described in, for example, literatures: Shinbo and Kawamura: "Study on" N-variable exponentiation operation and its application "", Chapter 5 of IEICE technical report ISEC91-59 (1991). Describes how to create and verify a signature and how to attack it in a situation where multiple persons sign a single document. However, even if the documents are different, the above check formula can be used to attack multiple signatures. Can be applied as it is, so there is a security problem.

[0026]

A first object of the present invention is to provide a signature method capable of collectively verifying a superimposed signature, a multiple signature, or an individual signature given to the same document or different documents by a plurality of signatures. It is to provide the device and the recording medium. A second object of the present invention is to provide a secure superimposed signature method, an apparatus and a recording method thereof, in which a plurality of signers sign different documents and want to guarantee the order relationship of the signatures, while suppressing an increase in the data amount of the signature component. To provide a medium.

The third object of the present invention can be realized only by carrying a message once between a plurality of signers (that is, one round consisting of (L-1) communications), and can realize a signature. It is an object of the present invention to provide a secure multi-signature method, an apparatus and a recording medium which suppress the increase in the data amount of components. A fourth object of the present invention is to provide a secure signature method, an apparatus, and a recording medium that can be efficiently and collectively verified when a plurality of signers sign different documents.

[0028]

A signature verification method according to a first aspect of the present invention includes the following steps: each signer i: (a) generates a first random number s _i as secret information; Information using the function G ₂ using β and the first random number s _i
I _i = (s _i , β) is generated, and the signer's public information ｛ID _i , I _i , f along with the two one-way functions f _i , h _i and the identification information ID _i used by the signer _{i i,} and published as h _i}, (b) a second random number r _i generates, information to set the above parameters beta and the second random number r _i to the function _{Φ X i = Φ (r i} , β) It generates the information including the information X _i X uses _i and the information X _'i to' _i Distant, document information m containing documents m _i should sign (c) ', the one-way function f _i h _i by _{e i = f i (X '} i, m' i) d i = h i (X 'i, m' i) to _{generate, (d) e i, d} i, s i, the r _i For the information included, a signature y _i = Sg _i (e _i , d _i , s _i , r _i , y ′ _i−1 ) is generated by the signature function Sg _i generated using the parameter β, and the identification is performed. The information including the information ID _i is identified by the identification information ID ' _i
Then, {ID ' _i , X' _i , m ' _i , y _i } is sent to the verifier as the final destination. However, when sent directly to the verifier, y' _i-1
Is an empty sentence and sent via another signer, y ' _i-1 = y
_i-1 and the verifier (e) receives the information ｛ID ' _i , X' _i , m ' _i
Information I _i corresponding to identification information ID _i included in ID ′ _i in y _i ｝
And the one-way function f _i, public information _{h i {ID i, I i} , f i, h i}
, And the one-way functions f _i , h _i and the received X ′ _i , m ′ _i
To obtain e _i and d _i using (f), obtain X _i in the above information X ′ _i , and calculate d _i and X _i for i = 1,..., L (X _i * d _i ) And e _i
And calculation of _{I i (I i * e i} ) Z by a function V including '= V | seeking _{((X i * d i)} , (I i * e i) i = 1, ..., L), ( g) By the function Γ including the operation of y _i and β (y _i * β),
= Γ (y _i * β), and a verification process is performed with W = Z ′. If the values match, it is determined that all signatures are correct.

According to the second aspect of the present invention, the value of the y component, which is the main signature component, is accumulated for each signature creation process to suppress an increase in the data amount of the signature component, thereby achieving the Fiat-Shami
Construct a superposition signature method applicable to the r method and the Schnorr method. Conventionally, the exponent component used in the verification process is only the e component used as a power component of I. However, a power component of X is newly performed, and a d component is introduced as a second power component. Is created in consideration of the order of the signers, thereby suppressing the increase in the number of communications while ensuring security.

According to the third aspect of the present invention, the value of the y component, which is a main signature component, is accumulated for each signature creation process to suppress an increase in the data amount of the signature component, thereby achieving a Fiat-Shami
Construct a multisignature method applicable to the r method and the Schnorr method. Conventionally, the exponent component used in the verification processing is only the e component used as a power of I component. However, by introducing a power of X as a new power component and introducing a d component as a second power component, safety is improved. Suppress the increase in the number of communications while guaranteeing.

According to the fourth aspect of the present invention, conventionally, the exponent component used in the verification processing is only the e component used as a power of I component. By introducing the d component as a power component, the value of the y component, which is the main signature component, is accumulated at the time of signature verification, and even if there is only one check formula for signature verification, the Fiat-Shamir can guarantee security. A signature method that can be collectively verified that can be applied to the law and the Schnorr method is constructed.

[0032]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS As shown in FIG. 1A, a system for performing a collective signature according to the present invention includes a center device (hereinafter simply referred to as a center) 100 and L (L is an integer of 2 or more) signers. Equipment (hereinafter also simply referred to as signer) 30 ₁ , 3
0 _2, ..., (hereinafter also referred to as simply the verifier) 30 _L and the verifier's apparatus 800 and is connected by line 400 safety is guaranteed, the signer apparatus 30 _1, 30 _2, ..., 30 _L safety Are sequentially connected by a line 500 whose performance is not guaranteed. The Lth signer device 30 _L is connected to the verifier device 800 by a line 700 whose security is not guaranteed. In this system, the signer 30 _1, y ₁ = transmitted as Sg ₁ (m ₁₎ to the next signer 30 ₂ with a signature by the signature function Sg ₁ to document m _1, signer 30 ₂ Article m ₂ and signature function Sg for received signature information y _1
2 by with the signature _{y 2 = Sg 2 (m 1} , y 1) as a signer 30 ₃
Transmitted to, and so repetition, the last signer 30 _L whereas signature information y _L-1 and the received document m _L, with a signature by the signature function _{Sg L y L = Sg L (} m L, y _L-1 ) as verifier device 800
Give to. Such a signature process is called a superimposed signature.

In this example, if only the first signer's document m ₁ exists and no subsequent signer's documents m ₂ ,..., _{M L} exist, _L signers for the same document m ₁ Are sequentially superimposed on each other, and this is called a multiple signature. In any case, according to the present invention, the verifier 800
Verify y _L collectively. In the verification method of the present invention, if all signatures are not invalid, the process is completed by one verification process. However, if any one is invalid, in order to detect the unauthorized signer, for example, If the number of Sha is 2 ^M, the first half or about 2 ^M-1 person of the signature of the second half performs a batch verification, the 2 ^M-1 person of the first half or the second half of the ^{2 M-2} people if there is fraud, the remaining without signed batch verification of 2 ^M-1 person half or 2 ^M-2 people in the second half, it is possible to detect illegal signature by M + 1 times of the verification process by repeating on.

[0034] The second system embodying the present invention, as shown in FIG. 1B, the center device 100 and the L signer apparatus 30 _1, ..., and if 30 _L and verifier device 800 of FIG. 1A Similarly, they are connected by a secure line 400, but each signer device 30 ₁ ,…, 30 _L and verifier device
800 is directly connected by a line 500 whose security is not guaranteed. In this system, each signer signs a document m _{i with a} signature function Sg _i and y _i = Sg _i (m
_i ) is transmitted to the verifier 800, and the verifier 800 collectively verifies the received signature information y _i = Sg _i (m _i ), i = 1,..., L.

In these two systems, the principle of the method for collectively verifying signatures by a plurality of signers according to the present invention will be described first. Step S1: The center 100 determines that each signer has a signature function Sg _i
Public parameters including a parameter q for generating and a parameter β = G ₁ (q) generated by the function G ₁ using the parameter q (distributed to all signers and verifiers). Step S2: Each signer i generates the first random number s _i as secret information and holds it in the storage device. The information by a function G ₂ with the public parameter β and the first random number s _{i
I i = G 2 (s i} , β) to generate a signer i is two used one-way function f _i, h _i and the identification information ID signer public information with _i {ID _i, I _i, f _i , h _i } are registered in the center 100. Step S3: The signer i generates a second random number r _i, information to set the parameters β and the second random number r _i to the function [Phi X _i = [Phi
(r _i , β) is generated, and information including the information X _i is set as X ′ _i . Step S4: The signer i uses the document information m _'i and information X' _i including the document m _i should sign, and two one-way function f _i
h _i by _{e i = f i (X '} i, m' i) (8) d i = h i (X 'i, m' i) to generate (9). Step S5: The signer i signs the information including e _i , d _i , s _i , and r _i by the signature function Sg _i y _i = Sg _i (e _i , d _i , s _i , r _i , y ′). _i-1) (10) generates the identification information ID _i information identification information ID including _{'i Distant, {ID' i, X '} i, m' i, y i} the verifier as the final destination Send out directly or via another signer. However, when sending directly to the verifier, set y ' _i-1 = blank sentence, and when sending via another signer, set y' _i-1 = y _i-1 . Step S6: The verifier receives the received information {ID ′ _i , X ′ _i ,
The information I _i corresponding to the identification information ID _i included in the ID ′ _i in m ′ _i , y _iと and the two one-way functions f _i , h _i are made public information ｛ID _i , I
_i , f _i , h _i 、, and the one-way functions f _i , h _{i in} equations (8) and (9)
Request e _i and d _i with the X _'i, m' _i and the received. Extracts X _i further included in the information X _'i received, it performs an arithmetic d _i * X _i between d _i and X _i, the operation e _i * I _i between e _i and I _i, the calculation With respect to the result, Z ′ = V ((X _i * d _i ), (I _i * e _i ) | i = 1,..., L) (11) is obtained by the function V. As the operation indicated by the symbol *, a power operation, multiplication, or the like can be used. Step S7: The verifier further calculates the operation result between y _i and β
Set y _i * β to the function Γ to obtain W = Γ (y _i * β), and W = Z '
The verification process is performed by comparing the above, and if the equality sign is satisfied, it is determined that all signatures are correct.

In order to perform batch verification by the above-described method in the superimposition or multi-signature system of FIG. 1A, y ′ _i−1 = y _i−1 and X ′ _i = (X ′ _i−1 , X _i ) (12) m ′ _i = (m ′ _i−1 , m _i ) (13) ID ′ _i = (ID ′ _i−1 , ID _i ) (14), and signer i is signer (i−1) From ｛ID ' _i-1 , X' _i-1 ,
m ′ _i , y _i−1 } and execute steps S3 to S5,
Send {ID ′ _i , X ′ _i , m ′ _i , y _i } to the signer (i + 1), and the last signer executes steps S3 to S5 to execute {ID ′ _L , X ′ _L ,
Send m ' _L , y _Lに to the verifier. In this case, a superimposed signature is performed.

In the above, m ′ ₁ = m ₁ = m, and m ₂ = m ₃ =... = M
_{If L} = “empty statement”, that is, m ' ₂ = m' ₃ =… = m ' _L = m,
This is the multiple signature described above. In the individual signature system shown in FIG. 1B, in order to perform batch verification by the method of the above-mentioned steps S1 to S7, y ′ _i−1 = empty sentence, X ′ _i = X _i , m ′ _i = m _i , ID ′ _i = and ID _i, the signer i sends steps S3, S4, information generated by _{S5 {ID i, X i,} m i, y i} a directly verifier.

As described above, in the present invention, as shown in step S4, each signer generates two pieces of information, e _i and d _i , using two one-way functions f _i , h _i. Contains the components of
Since y _i is generated and the signature is verified by incorporating these two pieces of information e _i and d _i in the verification, it is possible to perform verification based on a single information flow after signing by the signers 1 to L. Yes, and safety is guaranteed. On the other hand, according to the above-mentioned Schnorr signature verification method, as shown in equations (3) and (4), a signature y is obtained from e and a random number r and s obtained using one one-way function f. Therefore, if the method is simply applied to a superimposed signature, the amount of information {ID _i , X _i , y _i } transmitted to the next signer every time the signer adds a signature increases greatly. Thus, there is a problem that the burden of processing on the verifier increases.

Hereinafter, a specific method for carrying out the above-described principle signature batch verification method applied to the system of FIGS. 1A and 1B, each signer apparatus for executing the method, and a configuration example of the verifier apparatus will be described. . Embodiment 1 Here, an embodiment will be described in which a superimposed signature based on the principle of the present invention and its collective verification are applied to the Schnorr method in the system of FIG. 1A. The concept using the second power component shown here can be widely applied to the Fiat-Shamir method and a digital signature using interactive proof that includes them. Examples of constructing dialog proofs that include the Fiat-Shamir method and others are given in the paper by Tompa and Woll.

Each signer device 30 _i (i = 1,..., L) generates secret information s _i and public information when joining the system, and stores the public information (ID, I) in the public information management book of the center device 100. Register with. The center device 100 delivers the public information to the signer devices 30 ₁ ,..., 30 _L and the verifier device 800 as necessary. First,
Initial information setting processing when the center device 100 starts the system will be described (see FIG. 2). Here, the purpose is to make the system unique values {p, q, g} public.

(1-A) Initial information setting processing (processing of the center device at the start of the system) Step S1: A prime number p is generated using the prime number generator 110, and a divisor of p-1 is calculated using the divider 120. A prime number q is generated. Step S2: A primitive element α of (Z / pZ) ^* is generated by using the primitive element generator 130, and g = α ^{(p−1) / q} modp (15) An integer g having an order q is generated by the operation. Right side of equation (15) represents a function G ₁ of the foregoing, the right side of g corresponds to beta. Step S3: via a secure channel 400, the signer apparatus 30 _1, ..., public information to the verifier apparatus 800 and _{30 L {p, q, g} }
Deliver.

(1-B) Processing of Signer i Apparatus When Joining System Next, processing when the signer i joins the system will be described (see FIG. 3 showing the signer i apparatus _30i ). The public information {p, q, g} given from the center 100 is stored in the storage unit 33 of the signer apparatus 30 _i . Step S4: A random number s _i is generated by using the random number generator 31 and input to the modular exponentiation multiplier 32 together with the public information g and p.

[0043]

(Equation 23) To the calculation of the public information I _i in operation. Right side of equation (16) represents the aforementioned function G _2. Step S5: The signer i apparatus sends the personal identification information ID to the center apparatus 100 via the secure communication path 400.
_The public information I _i and the one-way functions f _i and h _i are transmitted together with _i and registered as public information {ID _i , I _i , f _i , h _i }. s _i is stored in the storage unit 33 as secret information.

Similar processing is performed when another signer apparatus joins the system. Center device 100 public information from all signer _{(ID i, I i, f} i, h i) (i = 1, 2, ..., L) somehow verifier device by exposing, for example, by public list
Give 800. Hereinafter, the signed communication message for the document m ′ _i output from the signer i apparatus is denoted by ｛ID ′ _i , X ′ _i , m ′ _i ,
y _i ｝. In the following, the signer (i-1) device transmits a message to be signed, the signer i device performs a signature creation process, and transmits the result to the signer (i + 1) device. The case will be described. In a case where L persons perform the superimposition signature, i may be increased by 1 from 1 to L, and the following procedure may be repeated. Here, the signer (L + 1) device is regarded as a verifier device. Where ID ' ₀ = empty set, X' ₀ = empty set, y ₀
= 0.

(1-C) Processing of Signer i-Device at the Time of Signature Creation FIG. 4 shows a communication sequence of a communication message, and FIG. 5 shows a functional configuration of the signer i-device. Signer (i-1) Message ｛ID 'from device
_{i-1, X 'i-} 1, m', receives the y _i-1}, the signer i device performs the following signature creation process. Step S6: generates a random number r _i using a random number generator 310, public information p stored in the storage unit 33, together with g, and enter the remainder with a power multiplier 320 for calculating a function Ф

[0046]

(Equation 24) Calculate X _i by the following operation. Step S7: function f _i calculator 330 and a function h _i calculator 340
Is used to obtain e _i and d _i in each operation of e _i = f _i (X ′ _i , m ′ _i ) (18) d _i = h _i (X ′ _i , m ′ _i ) (19). Here, it is assumed that X ′ _i = (X ′ _i−1 , X _i ) and m ′ _i = (m ′ _i−1 , m _i ). _mi is the document to be signed by signer i. Step S8: e _i , d _i , r _i are made public information q, secret information s _i
At the same time, it is input to a multiplier 350 with a remainder and an adder 360 with a remainder to generate a signature y _i = (y _i−1 + d _i r _i + e _i s _i ) modq (20). Right side of the equation (20) represents a signature function Sg _i in the above equation (10). Step S9: Set ID ′ _i = (ID ′ _i−1 , ID _i ) and ｛ID ′ _i ,
X ′ _i , m ′ _i , y _i } are sent to the signer (i + 1) device.

(1-D) Processing of Verifier Apparatus 800 at the Time of Signature Verification FIG. 6 shows a functional configuration of the verifier apparatus 800. Signer L communication text from the device _{{ID 'L, X' L} , m 'L, y L} receives a verifier device 800 signature to verify correct by the following process. Step S10: To set the public information given from the center apparatus _{100 {ID i, I i,} f i, h i} one-way function f _i in the h _i one-way function calculator 810 and 820. X constitute a 'beginning of i pieces of components from the X of _{L' i,} constitutes the _i 'm from the beginning of the i-number of components of the _L' m, X _'i, m' _i-function f _i calculator 810 And the function h _i calculator 820 are set to e _i = f _i (X ′ _i , m ′ _i ) = f _i (X ₁ , X ₂ ,…, X _i , ｛m ₁ , m ₂ ,…, m _i ｝) (21) d _i = h _i (X ′ _i , m ′ _i ) = h _i (X ₁ , X ₂ ,…, X _i , ｛m ₁ , m ₂ ,…, m _i ｝) (22 ) And e _i and d _i are obtained (1 ≦ i ≦ L). Step S11: I _i is obtained from public information {ID _i , I _i , f _i , h _i } (i = 1, 2,..., L) given from the center apparatus 100, and X in X ′ _L is obtained. _i is obtained and input to the exponentiation multiplier 830 with the multi-component remainder together with e _i , d _i , and the public information p created above.

[0048]

(Equation 25) Z ′ is calculated by the following operation. The right side of equation (23) corresponds to the function V ((X _i * d _i ), (I _i * e _i ) | i = 1,..., L) described in the principle of the present invention. Step S12: y _L public information p, which is held in the storage unit 88, is input to modular with a power multiplier 840 with g

[0049]

(Equation 26) W is calculated by the following calculation. Step S13: Z ′ and W are input to the comparator 850 to check whether W = Z ′ (25) holds. If they match, the document (m ₁ ,...,
m _L ) are each signed by L correct signer i devices.

(1-E) An improved square multiplication algorithm for a plurality of components. As in the operation of equation (23) in the multiplicative remainder exponentiation multiplier 830, for example, ^a plurality of squares represented by x ay ^b modN An improved square multiplication algorithm for calculating a modular exponentiation multiplication of components is as follows. Step 1: z = 1 Step 2: Perform the following processing on the subscripts i = 0, 1,..., | A | -1 (| a | represents the number of bits of a) Step 2-1: z = z ² modN (26) Step 2-2: If (a _i , b _i ) = (1, 0), z = zx mod N (27) If (a _i , b _i ) = (0, 1), then z = Zy mod N (28) If (a _i , b _i ) = (1, 1), then z = z (xy) mod N (29) where a _i is the value of the i-th bit of a and 0 Or take the value of 1, and b _i is the same. Step 3: Output z.

By using the above algorithm with x = X _i , a = d _i , y = I _i , b = e _i , and N = p, Z ₁ Z ₂ modp can be obtained. However,

[0052]

[Equation 27] It is. From how to make y _L

[0053]

[Equation 28] Therefore, if the above inspection is passed, the verifier device 80
0 recognizes that the document {m ₁ ,..., _{M L} } has been signed by L (number) correct signers (devices). A more efficient implementation of the square multiplication algorithm for multiple components is:
For example, DEKnuth “The Art of Computer Programmin
g, Vol. 2, Seminumerical Argorithms, “Addison-Wesle
y pubilishing (1981), p. 465, Exercises 27 and 35.

According to this method, the number of times of multiplication (including the remainder calculation by the modulus p) is expressed by s as the unit of storage (the above-described multi-component In the square multiplication algorithm, s = 2.) If (2 ^s -s-1) [(2L + 1) / s] + [(2L + 1) / s] | q | -1+ | q | -1. [b / a] represents the smallest integer not less than b / a.

Prior to the signature, the signer i device 30 _i is preceded by the received message {ID ′ _i−1 , X ′ _i−1 , m ′ _i , y _i−1 }. The signer (i-1) can verify that the signatures are correctly signed by the devices, and if the verification is successful, sign the signature. In this case, the center 100 previously gives the signer i public information (ID _i , I _i , f _i , h _i ) associated with i = 1,..., (I-1), The processing may be performed in the same manner as the processing steps S10 to S13 in the device 800. In this case, L in steps S10 to S13
Instead of (i-1).

The signer apparatus and the verifier apparatus usually execute each of the above-described processes using a computer. The invention is based on Sch
It was mentioned earlier that the method is applicable not only to the norr method but also to the Fiat-Shamir method and digital signatures using interactive proofs that include them. Therefore, the method of the present invention is generally described as follows.

That is, the system parameters to be disclosed are p specifying the number of elements of the group, element g of the group which is the starting point of the operation in the group operation, and a positive integer q which returns to g when the element g is operated q times. . Signer i device, published by the time of system subscriber, generates a random number s _i by using a random number generator, publish s _i in group operation calculator information g, the g and enter with p computes s _i times Calculate information I _i and public information together with personal identification information ID _i
I _i and the one-way functions f _i and h _i are disclosed as public information, and s _i
Is held as secret information, and the signer i
Upon receiving the signed message {ID ′ _i−1 , X ′ _i−1 , m ′ _i−1 , y _i−1 } for the document _mi−1 from the signer (i−1) device,
Generates a random number r _i using a random number generator, publish r _i information p, with g, the g is input to the group operation calculator calculates the X _i by calculating r _i times, X _'i = (X ' _i-1 , X _i ) and m'
_{i = (m 'i-1} , m i) and then, further with a function f _i calculator and function h _i calculator _{e i = f i (X'} i, m 'i) d i = h i (X _'i, m' seek e _i and d _i by calculating the _i), e _i, d _i, publish r _i information q, together with the secret information s _i, type index component multiplier, the exponential component adder Te, the signature _{y i = (y i-1} + d i r i + e i s i) modq by signature function Sg _i calculates sought y _i by, ID a _{'i = (ID' i-} 1, ID i) Every ｛I
D ′ _i , X ′ _i , m ′ _i , y _i ｝ are sent to the signer (i + 1) device.

Meanwhile verification device, signer L communication text from the device _{{ID 'L, X' L} , m 'L, y L} Upon receiving the, X' the leading i pieces of X from component _'i of _L configured, and m constitute the _i 'm from the beginning of the i-number of components of the _L', X _'i, m' _i the function f _i calculator and function h _i
Each of them is input to a calculator, and e _i = f _i (X ′ _i , m ′ _i ) d _i = h _i (X ′ _i , m ′ _i ) is calculated to obtain e _i and d _i for each i ( 1 ≦ i ≦ L), I
The corresponding public information I _i is obtained from the ID _i component in D ′ _L , and X in X ′ _L
seeking _i, e _i created above, d _i, a value of X _i computed d _i times for i from 1 to enter the multicomponent group arithmetic calculator with public information p to L, and I _i e _The value calculated _i times is sequentially calculated to obtain Z ′, and y _L is input to the group operation calculator together with the public information p and g, and W is calculated by calculating g y _L times to obtain Z ′ and Z ′. W is input to the comparator to check W {Z ', and if they match, the document {m ₁ ,..., _{M L} } is recognized to have been signed by each of the L correct signers i devices. .

For this general method, each signer i
The device, the user device, and the recording medium are similarly configured. Further above
In the description, ID '_i= (ID '_i-1, ID_i) But ID '_i= (ID '
_i-1, I_i). In this case, the verifier uses the ID
_iTo I_iThe hassle of searching for is lost. Embodiment 2 The superimposed signature described with reference to FIGS.
The signer device 30 ₁ Document m to sign with₁M₁= m,
Signer device 30_Two~ 30_LThen document m_Two,…, M_LAre all empty sentences
In this case, as described above, signers 1 to L are multi-signed for document m.
Will be named. An embodiment in that case will be described below.
You. Also in this embodiment, when the Schnorr method is used,
explain about.

The system configuration to which the second embodiment is applied is the same as that of FIG. 1A, and the configuration of the center device 100 is also the same as that shown in FIG. The processing of the center apparatus 100 executes also identical to that of the first embodiment, generates public information by the initial information setting process {p, q, g}, the signer apparatus 30 _1-3
0 _L is delivered to the verifier apparatus 800. The processing when the signer i joins the system is the same as in the first embodiment, and the device _30i for that is the same as that shown in FIG. This process generates public information I _i, via a secure channel 400, published to the center device 100 together with the personal identification information ID _i information I _i, public information by sending a one-way function f _i and h _i ｛ID _i ,
Register as I _i , f _i , h _i ｝. On the other hand, held in the storage unit 33 a s _i as confidential.

Similar processing is performed when another signer apparatus joins the system. In this embodiment, a signed communication message for the document m output from the signer i apparatus is represented by {ID ′ _i ,
X ′ _i , m, y _i ｝. The message to be signed is signed by the signer (i-
1) The device transmits the data, the signer i performs the signature creation process, and transmits the result to the signer (i + 1) device. When L people sign sequentially, i is 1 from L to 1
Then, the following procedure may be repeated. Here, the signer (L + 1) device is regarded as a verifier device. Where I
Let D ' ₀ = empty set, X' ₀ = empty set, y ₀ = 0.

(2-A) Processing of Signer i-Device at Signature Creation FIG. 7 shows a communication sequence of a communication message, and FIG. 8 shows a functional configuration of the signer i-device. Signer (i-1) Message ｛ID 'from device
Upon receiving _i−1 , X ′ _i−1 , m, y _i−1 ｝, the signer i apparatus performs the following signature creation processing. The storage unit 33 has a center 100
Holds the public information {p, q, g}, the secret random number s _i , and the identification information ID _i . Step S1: A random number r _i is generated by using the random number generator 310, and the exponentiation multiplier 32 with the remainder is generated together with the public information p and g.
0 and the function Φ

[0063]

(Equation 29) Is calculated, and X ′ _i = (X ′ _i−1 , X _i ) is set. Step S2: the function f _i calculator 330 and a function h _i calculator 340
Is used to calculate e _i and d _i in each operation of e _i = f _i (X ′ _i , m) (32) d _i = h _i (X ′ _i , m) (33). Step S3: e _i , d _i , r _i are made public information q, secret information s _i
With the remainder with the multiplier 350, and input to the remainder with the adder 360, the signature function _{Sg i y i = Sg i (} e i, d i, s i, r i, y i-1) = (y i _{-1 + d i r i + e} i s i) obtaining a mod q (34). Step S4: Set ID ′ _i = (ID ′ _i−1 , ID _i ) and set ｛ID ′ _i ,
X ′ _i , m, y _i } is sent to the signer (i + 1) device.

(2-B) Processing of Verifier Apparatus 800 at the Time of Signature Verification FIG. 9 shows a functional configuration of the verifier apparatus 800. Signer L device
From the message ｛ID '_L, X ' _L, m, y_LUpon receiving｝, the verifier
The device 800 checks whether the signature is correct by the following verification processing.
You. Step S5: X '_LX ′ from the first i components of_iBe composed
Function f with document m_iCalculator 810 and function h_iCalculator 82
Enter 0 and e_i= f_i(X '_i, m) = f_i(X₁… X_i, m) (35) d_i= h_i(X '_i, m) = h_i(X₁… X_i, m) (36)_iAnd d_i(1 ≦ i ≦ L). Step S6: ID '_LID inside_iIngredient from I_iX '_L
X in_iAnd extract the e created above_i, D_i, Public information p and
Both are input to the power multiplier 830 with multiple component remainder and verified.
By function V

[0065]

[Equation 30] Z ′ is calculated by the following operation. Step S7: y _L is input to the modular exponentiation multiplier 840 together with the public information p and g held in the storage unit 88, and the third function Γ

[0066]

(Equation 31) W is calculated by the following calculation. Step S8: Z ′ and W are input to the comparator 850 to check whether W = Z ′ holds. If they match, the document m has been signed by L correct signer devices. Admit.

In a power multiplier with a multi-component remainder,
An improved square multiplication algorithm for calculating x ^a y ^b mod N may use the same algorithm as described in the first embodiment. From how to make y _L

[0068]

(Equation 32) Therefore, if the above inspection is passed, the verifier device 80
0 recognizes that document m has been signed by L (significant) correct signers (devices). Prior to the signature, the signer i device receives the received message {ID ′ _i−1 , X ′ _i−1 ,
m, y _i-1 } are verified to have been correctly signed by the preceding signer 1 device to signer (i-1) device, respectively, and if the verification is passed, signing is performed. You can also. The verification in this case may be performed in the same manner as the processing steps S10 to S13 in the verifier device 800. In this case, (i-1) may be used instead of L in steps S10 to S13.

The signer apparatus and the verifier apparatus usually execute each of the above-mentioned processes by computer. This second embodiment uses Sc
It was mentioned earlier that the method can be applied not only to the hnorr method but also to the Fiat-Shamir method and digital signatures using interactive proofs that include them. Therefore, the method of the present invention is generally described as follows. In other words, the system parameters to be disclosed are p specifying the number of elements in the group, the element g of the group that is the starting point of the operation in the group operation, and q
This is a positive integer q that returns to g when it is calculated a number of times.

[0070] signer i device, when the system subscriber, generates a random number s _i by using a random number generator, s _i published group operation calculator information g, the g computes s _i times to input with p public information I _i calculated by the public information together with the personal identification information ID _i
I _i , function f _i , and function g _i are disclosed as public information, and s _i is held as secret information. In the signature processing, the signer i device signs the document m from the signer (i-1) device. communication text regarding _{{ID 'i-1, X} ' i-1, m, y i-1} receives the generates a random number r _i using a random number generator, the r _i public information p, with g , Input to the group operation calculator and calculate g by r _i times to obtain X _i
Was _{calculated, X 'i = (X'} i-1, X i) Distant, further by using the function f _i calculator and function h _i calculator _{e i = f i (X '} i, m) d i _{= h i (X 'i,} m) the calculated seek e _i and d _i, e _i, d _i, publish r _i information q, together with the secret information s _i, the index component multiplier, exponent component adder , And y _i = Sg _i (e _i , d _i , s _i , r _i , y _i−1 ) = (y _i−1 + d _i r _i + e _i s _i ) mod by the signature function Sg _i
q ′ is calculated and obtained, and ID ′ _i = (ID ′ _i−1 , ID _i ), and ｛I
D ′ _i , X ′ _i , m, y _i } are sent to the signer (i + 1) device.

[0071] On the other hand, the verification device, the signer L communication text from the device _{{ID 'L, X' L} , m, y L} Upon receiving the, X 'beginning of i of _L
X ′ _i are constructed from the components and input to the function f _i calculator and the function h _i calculator together with the document m, and e _i = f _i (X ′ _i , m) d _i = h _i (X ′ _i , m) to obtain e _i and d _i for each i (1 ≦ i ≦ L).
The corresponding public information I _i is obtained from the ID _i component in D ′ _L , and X in X ′ _L
i is obtained and input to the multi-component group calculation calculator together with e _i , d _i created above and the public information p to calculate X _{i di} times for i from 1 to L, and I _i to e _The value calculated _i times is sequentially calculated to obtain Z ′, and y _L is input to the group operation calculator together with the public information p and g, and W is calculated by calculating g y _L times to obtain Z ′ and Z ′. W is entered into the comparator to check W≡Z 'and if they match, document m is deemed to have been signed by the L correct signers.

In this general method, each signer i device, user device, and recording medium are similarly configured. Further, in the above, ID ′ _i = (ID ′ _i−1 , ID _i ), but ID ′ _i = (I
D ′ _i−1 , I _i ). In this case, it is not necessary for the verifier to search for I _i from ID _i . Embodiment 3 Next, in the system shown in FIG. 1B, each document m _{1 to} m _L is individually signed by each signer device 30 ₁ to 30 _L and given to the verifier device 800. An example in which documents are collectively verified will be described with an example using the Schnorr method. The concept using the second power component shown here is also widely applicable to the Fiat-Shamir method and a digital signature using interactive proof that includes them.

(3-A) Initial Information Setting Processing The apparatus configuration for the center apparatus 100 to perform the initial information setting processing for disclosing the system unique values {p, q, g} is the same as that in FIG. The processing described in (1) is the same. Step S1: A prime number p is generated using the prime number generator 110, and a prime number q that is a divisor of p-1 is generated using the divider 120. Step S2: Use the primitive element generator 130 to generate a primitive element α of (Z / pZ) ^* , and use the modular exponentiation multiplier 140 for executing the operation of the function G ₁ (q) described in the principle of the present invention. Then, an integer g having an order q is generated as the above-mentioned parameter β by an operation of β = g = G ₁ (q) = α ^{(p−1) / q} modp (40). Step S3: via a secure channel 400, the signer apparatus 30 _1, ..., 30 _L and the public information to the verifier device 800 {p,
Deliver q, g｝.

[0074] processing (3-B) signer i device during system subscriber Then, the signer i device is described with reference to the signer i apparatus 30 _i shown in FIG. 10 for the process at the time of subscribing to the system . Note that the storage unit 33 holds the public information {p, q, g} provided from the center 100. Step S4: A random number generator 31 is used to generate a random number s _i , and a public information g (= β) is output to a modular exponentiation multiplier 32 for calculating the function G ₂ (s _i , β) described in the principle of the present invention. , P

[0075]

[Equation 33] To the calculation of the public information I _i in operation. Step S5: The signer i device via a secure channel 400, published together with the personal identification information ID _i to the center device 100 information I _i, the one-way function f _i, registered as public information by sending h _i , held in the storage unit 33 a s _i as confidential.

When another signer device joins the system
Performs the same processing. Hereinafter, the signer i-device is a document
m_i通信 ID_i, X _i, m_i, y
_i Expressed as｝. (3-C) Processing of Signer i Device at the Time of Signature Creation FIG. 11 shows a communication sequence of a communication message, and FIG.
Device 30_i Are shown below. Step S6: Random number r using random number generator 310_iGenerate a
And the remainder to calculate the function Ф together with the public information p and g
Input to the exponentiation multiplier 320

[0077]

(Equation 34) To calculate X _i . Step S7: function f _i calculator 330 and a function h _i calculator 340
Respectively, using the _{e i = f i (X i} , m i) (43) obtains the _{d i = h i (X i} , m i) e i and d _i in each computation of (44). Step S8: e _i , d _i , r _i are made public information q, secret information s _i
With the remainder with the multiplier 350, and input to the remainder with the adder 360, the signature function Sg _i by _{y i = Sg i (e i} , d i, s i, r i, q) = (d i r i + e _i s _i ) modq (45) is obtained. Step S9: {ID _i , X _i , m _i , y _i } are verified by the verifier device 800
Send to

(3-D) Processing of Verifier Device 800 During Signature Verification FIG. 13 shows a functional configuration of the verifier device 800. Storage unit 88
Holds public information {p, q, g} from the center 100, and transmits L communication messages {ID _i , X _i , m
_i , y _i }, the verifier apparatus 800 collectively verifies that each signature is correct by the following verification. Step S10: function X _i with Article m _i f _i calculator 810
A function h _i each input to the calculator _{720 e i = f i (X} i, m i) d i = h i (X i, m i) in the calculation of obtaining the e _i and d _i (1 ≦ i ≦ L). Step S1
1: Input from the center 100 obtains public information I _i corresponding to ID _i, e _i created by X _i and said, d _i public information p, the multi-component residue with power multiplier 830 for calculating a function V with do it

[0079]

(Equation 35) To find Z '. Step S12: L y _i are input to the adder with remainder 840 together with the public information q, and Y = Σ _{i = 1} ^L y _i modq (47) to obtain the cumulative value Y, and together with the public information p and q, the function Γ
(Y * g) is input to a modular exponentiation multiplier 845 to calculate W, and W = Γ (Y * g) = g ^Y modp (48) to obtain W. Step S13: Z ′ and W are input to the comparator 850, and W =
It is checked whether Z ′ holds, and if they match, each document _mi is recognized as having been signed by L correct signers i.

[0080] In multi-component residue with power multiplier 830, for computing a x ^a y ^b modN, one method of square-and-multiply algorithm is the same as described above. From how to make the cumulative value Y

[0081]

[Equation 36] Therefore, if the above inspection is passed, the verifier device 80
0 admits one in which each document m _i is signed by the L good signer i device. If W = Z ′ is not satisfied in step S13, for example, if L = 100, L /
The message {ID _i , X _i , _mi , y _i } is divided into 2 = 50
> Steps S9 to S9 for one of the two divided messages
13 is checked to see if there is any mismatch. If they do not match, the divided message is further divided.
By executing S13 and repeating the same division processing,
The verifier device can detect which signer device has not been correctly signed.

It has been mentioned above that the present invention can be applied not only to the Schnorr method but also to the Fiat-Shamir method and digital signatures using interactive proofs that include them. Therefore, the method of the present invention is generally described as follows. That is, the system parameters to be disclosed are p specifying the number of elements of the group, element g of the group which is the starting point of the operation in the group operation, and a positive integer q which returns to g when the element g is operated q times.

[0083] signer i device, when the system subscriber, generates a random number s _i by using a random number generator, s _i published group operation calculator information g, the g computes s _i times to input with p The public information I _i is calculated in this way, the public information I _i , the functions f _i , and h _i are disclosed as public information along with the personal identification information ID _i , and s _i is held as secret information. who i unit generates a random number r _i using a random number generator, publish r _i information p, with g, calculate the X _i by the g is input to the group operation calculator calculates r _i times And e _i = f _i (X _i , m _i ) d _i = h _i (X _i , m _i ) using the function f _i calculator and the function h _i calculator to obtain e _i and d _i Then, e _i , d _i , and r _i are input to an exponential component multiplier and an exponential component adder together with public information q and secret information s _i , and y _i = (d _i r _i + e _i s _i ) modq is obtained. calculated seeking y _i, communication text _{{ID i, X i, m} i, y i} Determined to send to the verifier device.

When the verifier apparatus receives the message {ID _i , X _i , m _i , y _i } from the L signer i apparatuses (1 ≦ i ≦ L), X
The _i, and input to the function f _i calculator and function h _i calculator with documents _{m i e i = f i (} X i, m i) d i = h i (X i, m i) calculates the Te seeking e _i and d _i for each i (1 ≦ i ≦ L) , ID
seeking I _i from _i, the I _i and X _i, e _i created above, d _i, the X _i for i from 1 to enter the multicomponent group arithmetic calculator with public information p to L d _i Z ′ is obtained by sequentially calculating the value calculated _i times and the value calculated I _i times e _i , while L y _i are input to the exponential component adder together with the public information q, and Y = Σ _{i = 1} ^L y _i modq to obtain Y, input Y to the group operation calculator together with public information p and g, calculate g by Y times to obtain W, and Z ′
And it examines the W≡Z 'by entering W to the comparator, if they match, the L document m _i admit that it was signed by the L good signer i device.

The signer device and the verifier device respectively
Usually, the processing is executed by a computer. By the way, in the above-described first to third embodiments, the parameter q
Was a case where Zq was used as a commutative group of a finite field defined by
As a result, the problem of an increase in the amount of processing for creating a signature by the signer can be solved. While the RSA cipher bases security on the difficulty of the prime factorization problem, the elliptic curve cryptosystem secures the discrete logarithm problem on the elliptic curve, which is considered to be more difficult to solve than the prime factorization problem. Have a gender basis.

The elliptic curve on the finite field GF (q) is defined as follows using the parameters a, b∈GF (q) (4a ³ + 27b ² ≠ 0). E _{a, b} (GF (q)) = ｛(x, y) ∈GF (q) ² | y ² = x ³ + ax + b｝ ∪ ｛O｝ (50) Here, GF (q) is transformed into an elliptic curve E _{a , b} (GF (q)). O indicates a point at infinity. The addition on the elliptic curve at this time is given by P _i = (x _i , y _i ) ∈E _{a, b} (GF (q)) (i = 1, 2), and (x ₃ , y ₃ ) = P ₁ + P ₂ is (a): In the case of P ₁ λP ₂ , if λ = (y ₂ -y ₁ ) / (x ₂ -x ₁ ), x ₃ = λ ² − (x ₁ + x ₂ ) , Y ₃ = −y ₁ + λ (x ₁ −x ₃ ) (51) (b): When P ₁ = P ₂ , that is, when (x ₃ , y ₃ ) = 2P ₁ , λ
= Putting the ^{_{(3x 1 2 + a) /}} (2y 1), x 3 = λ 2 -2x 1, y 3 = -y 1 + λ (x 1 -x 3) written as (52). For operations on groups on elliptic curves, for example, Dagl
as R. Stinson, “CRYPTOGRAPHY Theory and Practic
e ", CRC Press, pp. 187-190, 1995.
In the following description, representative of the elliptic curve _{E a, b (GF (q} )) the addition operation of the P ₁ and P ₂ on the _{(P 1 + P 2) overE} a, b (GF (q)).

The method of solving a discrete logarithm problem on an elliptic curve which is currently known is less efficient than the method of solving a prime factorization problem, that is, it is more difficult. However, the amount of calculation can be reduced. Specifically, it is said that in order to guarantee the same security as when | N | = 1024, it is sufficient to select | q | = 160. Here, | p | represents the number of bits of p. (For example, Bruce Schneicer, “APPLIED CRYPTOGRAPHY (Second E
dition) ”, John Wiley & Sons, Inc., pp. 480-481, 1
996,).

An ordinary discrete logarithm problem is that when an integer g∈ (Z / pZ) ^* = {1,2,..., P-1} having a large prime p and an order q is given as public information, This is a problem of finding y∈Z / qZ that satisfies g ^y x (modp) for an integer x∈ (Z / pZ) ^* . On the other hand, the discrete logarithm problem on an elliptic curve is defined by the definition field GF
(q), parameters a, b, GF (q) of the elliptic curve and a point P∈E _{a, b} (GF (q)) on the elliptic curve where the order on the elliptic curve is k are given as public information. (That is, when kP = O holds), for a point X∈E _{a, b} (GF (q)) on the elliptic curve, yP≡X
This is a problem to find y∈Z / kZ that satisfies overE _{a, b} (GF (q)). Point P is called a base point. Where yP≡X over E
_{a, b} (GF (q)) indicates that when the base point P is added y times on the elliptic curve, it matches the point X aE _{a, b} (GF (q)). In particular, an elliptic curve E _{a, b} and adding y times the base point P on (GF (q)), yP over E a, expressed as _b (GF (q)), a group operation on the elliptic curve Stipulate.

Using the group operation on the elliptic curve defined above, Diffie-
Hellman's key agreement method, ElGamal encryption, ElGamal signature, etc. can all be transformed into methods that use the difficulty of discrete logarithms on elliptic curves. Schnorr's method using interactive proofs
The Fiat-Shamir method can also be transformed into a method that uses the difficulty of discrete logarithms on elliptic curves. For example, using an elliptic curve
The digital signature according to Schnorr's method is as follows.

The reliable center is defined by the parameter q of the definition field GF (q), the parameters a, b, and GF (q) of the elliptic curve, and the base point P∈E _a on the curve whose order on the elliptic curve is k. _{, b} (GF (q))
Publish. Step 1: The signer A generates a random number s∈ (Z / kZ), calculates public information I by using I = sP overE _{a, b} (GF (q)) (53), and obtains personal identification information ( Publish the set of ID) and I.

The signer A proves to the verifier B that the document m is genuine by the following procedure. Step 2: The signer A generates a random number r∈ (Z / kZ), and calculates X = rP overE _{a, b} (GF (q)) (54). Step 3: The signer A calculates the integer e∈ (Z / kZ) by using the one-way function f as e = f (X, m) (55). Step 4: The signer A generates a signature y by y = (r + es) modk (56) and sends {ID, m, X, y} to the verifier B as a signed message. Step 5: The verifier B calculates the integer e∈ (Z / kZ) by using the one-way function f with e = f (X, m). Step 6: Verifier B checks that yPP (X + eI) overE _{a, b} (GF (q)) (57) holds. Here, I is public information corresponding to the ID.

Since yP≡ (r + es) P≡rP + e (sP) ≡ (X + eI) overE _{a, b} (GF (q)) (58), y If it passes, verifier B acknowledges that document m was sent from A. In the above, the integers e, (Z / kZ) and y∈ (Z / kZ) are appropriately determined, then X∈E _{a, b} (GF (q)) that passes the check formula is calculated, and e = f (X, m)
Is found, and if {ID, X, m, y} is defined as a signed message, the signature is successfully forged. Since the probability that the check formula e = f (m, X) holds is 1 / k, the amount of calculation required for forging a signature is determined by k.

In the elliptic Schnorr method, the number of executions of equations (51) and (52) for calculating the n-fold point on the elliptic curve (including the remainder calculation in the modulus q) is an average of 3 | q | / Twice, | k |
The multiplication of the bit integer (including the remainder calculation in the modulus k) is performed once, and the addition of the | k | -bit integer (including the remainder calculation in the modulus k) is performed once. Therefore, an embodiment in which the above-described elliptic curve method is applied to the above-described first to third embodiments will be described below.

The addition result P ₃ (= P ₁ + P ₂ ) on the elliptic curve is calculated by the equations (51) and (52) using the x coordinate and the y coordinate. As is clear from), once the x coordinate is determined, a point on the elliptic curve is uniquely determined by the positive / negative value of the y coordinate. Where the x coordinate is the definition field GF (q)
Note that the point on the elliptic curve can be represented by (| q | +1) bits. Embodiment 4 This embodiment corresponds to the first embodiment in which a superimposed signature and batch verification are performed. Here, an embodiment in which the Schnorr method is applied to a superimposed signature using the elliptic curve method and its collective verification will be described. Here, the concept of using the second multiple component is as follows.
It is widely applicable to the ElGamal signature method and digital signatures using interactive proofs that include them. The system configuration to which this embodiment is applied is the same as that of FIG. 1A, and a description thereof will be omitted.

(4-A) Initial Information Setting Process The initial information setting process when the center 100 starts the system will be described with reference to FIG. Here, the purpose is to make the system unique values {q, a, b, P, k} public. Step S1: A prime number q is generated by using the prime number generator 110, and a, b∈GF (q) is generated by using the parameter generator 120. Step S2: A point P∈E _{a, b} (GF (q)) on the elliptic curve is generated using the base point generator 130, and the order k of the base point P is obtained using the order calculator 140. E _a, corresponding to _b (GF (q)) function value G _i described invention principles (q), P corresponds to beta. Step S3: Signer 30 via secure communication channel 400
_1, ..., 30 _L and the public information to the verifier 800 {q, a, b, P, k} to deliver, a storage unit 33 of the signer apparatus 30 ₁ to 30 _L, the verifier apparatus 80
0 is stored in the storage unit 88.

The order calculator 140 has, for example, an elliptic curve E_{a, b}(G
F (q)) 's order (number of points on the curve)
It can be easily realized by using the algorithm. (reference
Reference: R. Schoof; "Elliptic Curves Over Finite Fields
 and the Computation of Square Roots Mod p, "Math.
Comp., 44, pp. 483-494, 1985). (4-B) Processing of signer i when joining system Next, processing when signer i joins the system
This will be described with reference to FIG. Step S4: Random number s using random number generator 31_iGenerate a
And enters it into the n-fold point calculator 32 together with the public information {q, a, b, P}.
Force the function G explained in the principle of the invention_Two(s_i, β)_i= G_Two(s_i, P) = s_iP over E_{a, b}(GF (q)) Information published in (59) I_iIs calculated. Step S5: Each signer i
Sends the personal identification information to the center 100 via the secure communication path 400.
Report ID_i Public Information I with_i, One-way function f_i, h_iSend
Public information ｛ID_i, I _i, f_i, h_i Register as｝. s_iTo
It is stored in the storage unit 33 as secret information.

[0097] The signer i output document m _i signed communication text for the _{{ID 'i, X' i} , m 'i, y i} represents the. The communication sequence of the message is the same as that of FIG. 4, and the signer (i-1)
When the message {ID ′ _i−1 , X ′ _i−1 , m ′ _i−1 , y _i−1 } is received from the user, the signer i performs the following signature creation processing. Signer device
The structure of 30 _i shown in FIG. 16. Hereinafter, a case will be described in which the signer (i-1) transmits a message to be signed, the signer i performs a signature creation process, and transmits the result to the signer (i + 1). In a case where L persons perform the superimposition signature, i may be increased by 1 from 1 to L, and the following procedure may be repeated. Here, the signer (L + 1) is regarded as the verifier. However,
ID _'0 = empty set, put the X ₀ = empty set, y ₀ = _0.

[0098] (4-C) signature creation signer i process Step S6: generates a random number r _i using a random number generator 310, public information {q read from the storage unit 33, a, b, P｝
With Type n times point calculator 320 for calculating a second function _{Ф X i = Ф (r i} , P) = r i P over E a, b at _{X i (GF (q))} (60) calculate. Step S7: function f _i calculator 330 and a function h _i calculator 340
Is used, e _i = f _i (X ′ _i , m ′ _i ) (61) d _i = h _i (X ′ _i , m ′ _i ) (62) to obtain e _i and d _i . Here, it is assumed that X ′ _i = (X ′ _i−1 , X _i ) (63) m ′ _i = (m ′ _i−1 , m _i ) (64) Step S8: e _i , d _i , r _i are made public information k, secret information s _i
With, by entering the remainder with the multiplier 350 and the remainder with the adder 360, the signature function _{Sg i y i = Sg i (} e i, d i, s i, r i, y i-1) = (y i _{-1 + d i r i + e} i s i) obtaining the modk (65). Step S9: Set ID ′ _i = (ID ′ _i−1 , ID _i ) and ｛ID ′ _i ,
X ′ _i , m ′ _i , y _i } are sent to the signer (i + 1).

(4-D) Processing of Verifier 800 at Signature Verification FIG. 17 shows the configuration of the verifier device 800. Verifier signer L communication text from _{{ID 'L, X' L} , m 'L, y L} receives a signature or verifying correct by the following process. Step S10: From the first i components of X ′ _L , X ′ _i ,
m ′ _i is constructed from the first i components of m ′ _L and input to the function f _i calculator 810 and the function h _i calculator 820, and e _i = f _i (X ′ _i , m ′ _i ) d e _i and d _i are obtained by _i = h _i (X ′ _i , m ′ _i ). (1 ≦ i ≦ L) Step S11: the public 'the ID _i component from I _i in _L, X' ID sought X _i from in _L, read from e _i, d _i and the storage section 88 created above Along with the information {q, a, b, P}, it is input to an n-fold calculator 830 that calculates a function V, and Z ′ = V ((X _i * d _i ), (I _i * e _i ) | i = 1, ..., L) = (d ₁ X ₁ +... + D _L X _L + e ₁ I ₁ +... + E _L I _L ) overE _{a, b} (GF (q)) (66) Here, e _i = f _i (X ₁ ,…, X _i , ｛m ₁ ,…, m _i ｝) (67) d _i = h _i (X ₁ ,…, X _i , ｛m ₁ ,…, m _i ｝) (68) (1 ≦ i ≦ L). Step S12: Publish y _L information {q, a, b, P } is input to the n-times point calculator 840 for calculating a function gamma a (y _L * P) with _{W = Γ (y L, P} ) = y W is obtained by _L P over E _{a, b} (GF (q)) (69). Step S13: Z ′ and W are input to the comparator 850 to check W = Z ′, and if they match, the document {m ₁ ,..., _{M L} } is signed by L correct signers Admit. Embodiment 5 This fifth embodiment corresponds to the second embodiment in which multiple signatures and batch verification are performed. Here, an embodiment in which the Schnorr method is applied to multiple signatures and batch verification using the elliptic curve method will be described. Also in this embodiment, the concept of using the second multiple component is widely applicable to ElGamal signature methods and digital signatures using interactive proofs that include them.

The structure of the system to which the fifth embodiment is applied is the same as that of FIG. 1A, and the structure of the center device 100 is the same as that shown in FIG. (5-A) Initial Information Setting Process of System First, the initial information setting process when the center device 100 starts the system will be described with reference to FIG. Step S1: A prime number q is generated using the prime number generator 110, and a, b, GF (q) are generated using the parameter generator 120. Step S2: Base point generator for calculating function G ₁ (q)
A point P E _{a, b} (GF (q)) on the elliptic curve is generated using 130 and an order k of the base point P is obtained using the order calculator 140. P corresponds to the parameter β described in the principle of the invention. Step S3: via a secure channel 400, the signer apparatus 30 _1, ..., public information on the 30 _L and verifier device 800 {q, a, b, P,
k｝ is delivered and stored in the respective storage units 33 and 88.

Here, the order calculator 140 uses the Schoof algorithm for obtaining the order (the number of points on the curve) of the elliptic curve E _{a, b} (GF (q)) as described above. Can be easily realized. (5-B) Processing of Signer i-Device at System Subscription Next, the processing when the signer i-device joins the system will be described with reference to FIG. Step S4: A random number generator 310 is used to generate a random number s _i, which is input to an n-fold calculator 220 for calculating a function G ₂ (s _i , P) together with the public information q, a, b, P and I _i = G ₂ (s _i , P) = s _i P overE _{a, b} (GF (q)) (70) The public information I _i is calculated. Step S5: Each signer i device transmits the public information I _i , the one-way function f _i , h _i together with the personal identification information ID _i to the center device 100 via the secure communication channel 400, and the public information ｛ID _i ,
Register as I _i , f ₁ , h ₁ ｝. s _i is held as secret information.

Hereinafter, the document m output from the signer i
署名 I '_i, X ' _i, m, y_iExpressed as｝. Through
The communication sequence of the message is the same as that of FIG.
(I-1) Message ｛ID 'from device_i-1, X '_i-1, m, y_i-1｝
Upon receipt, the signer i apparatus performs the following signature creation processing.
Signer device 30_i 18 is shown in FIG. In the following, the signature
The signer (i-1) device sends the target message and sends it to
On the other hand, the signer i-device performs the signature creation process, and
The case of transmitting to the signer (i + 1) device will be described. L
When a person performs multiple signatures, i is one from 1 to L
Then, the following procedure may be repeated. Here is the signature
The verifier (L + 1) device is regarded as the verifier device. Where ID '₀= Empty
Set, X '₀ = Empty set, y₀= 0.

[0103] processing steps (5-C) signature creation signer i device S6: generates a random number r _i using a random number generator 310, public information {q read from the storage unit 33, a, b ,
With _{P}, X i = Φ (} r i, P) = r i P over E a is input to the n-times point calculator 320 for calculating a function _[Phi, in the calculation of _{b (GF (q)) (} 71) Calculate X _i . Step S7: One-way function
f _i calculator 330 and a one-way function h _i using calculators _{340 e i = f i (X} 'i, m) (72) d i = h i (X' i, m) each of (73) calculation of acquiring e _i and d _i in. Here, X ′ _i = (X ′ _i−1 , X _i ). Step _{S8: e i, d i,} r i, y i-1 public information k, together with the secret information s _i, the remainder with the multiplier 350, and input to the remainder with the adder 360, signed by the signature function Sg _i y _i = Sg _i (e _i , d _i , s _i , r _i , y _i−1 , k) = (y _i−1 + d _i r _i + e _i s _i ) modk (74) Step S9: Set ID ′ _i = (ID ′ _i−1 , ID _i ) and set ΔI
D ′ _i , X ′ _i , m, y _i } are sent to the signer (i + 1) device.

(5-D) Processing of Verifier Apparatus 800 at the Time of Signature Verification FIG. 19 shows a functional configuration of the verifier apparatus 800. Communication text from the signer L device _{{ID 'L, X' L} , m, y L} receives a verifier device 800 to verify the signature by the following process is correct. Step S10: X ′ _i is constructed from the first i components of X ′ _L , and the function f _i calculator 810 and the function h _i calculator together with the document m
820 and e _i = f _i (X ′ _i , m) d _i = h _i (X ′ _i , m) to obtain e _i and d _i (1 ≦ i ≦ L). Step S11: 'the ID _i component from I _i in _L, X' ID sought X _i from the _L, e _i, d _i and the storage section 88 created above
And the public information {q, a, b, P, k} read out from the input to the n-fold calculator 830 that calculates the function V, and Z ′ = V ((X _i * d _i ), (I _i * e _{i) | i = 1, ...} , L) = computation of _{(d 1 X 1 + ... +} d L X L + e 1 I 1 + ... + e L I L) over E a, b (GF (q)) (75) To find Z '. Here, e _i = f _i (X ₁ ,..., X _i , m) (76) d _i = h _i (X ₁ ,..., X _i , m) where 1 ≦ i ≦ L (77). Step S12: Publish y _L information q, a, b, and input to the n-times point calculator 840 for calculating a function gamma a (y _L * P) with _{P W = Γ (y L *} P) = y L P over E _{a, b} (GF (q)) W is obtained by the operation of (78). Step S13: Z ′ and W are input to the comparator 850 to check whether W = Z ′ is satisfied. If they match, the document m has been signed by L correct signer devices. Admit.

Each device can read a program by a computer, execute the decoding, and execute its function. Also, ID ′ _i = (ID ′ _i−1 , ID _i ) at each signer i device
May be set as ID ′ _i = (ID ′ _i−1 , I _i ). In this case I _i
Must be stored in the storage means.
Finding I _i from _i is troublesome. Embodiment 6 This sixth embodiment corresponds to a third embodiment in which a plurality of signers individually sign each document and collectively verify them. Also in this embodiment, the Sch using the elliptic curve method is used.
The case where the norr method is applied will be described. Also in this embodiment, the idea of using the second multiple component is ElGama
l It is widely applicable to digital signatures using signature methods and interactive proofs that include them.

The structure of the system to which the sixth embodiment is applied is the same as that of FIG. 1B, and the structure of the center device 100 is the same as that shown in FIG. Hereinafter, it is assumed that the signer i signs the document _mi and the signed communication message is represented as {ID _i , X _i , _mi , y _i }. The communication sequence of the message is the same as that shown in FIG. FIG. 20 shows a block diagram of the signer i.

[0107] (6-A) signature creation signer i processing step S14: generates a random number r _i using a random number generator 310, public information {q read from the storage unit 33, a, b,
N times-multiplier calculator 320 for calculating a function Φ (r _i , P) together with P｝
In Type _{X i = Φ (r i,} P) = r i P over E a, b (GF (Q)) (79) to calculate the X _i in. Step S15: the one-way function f _i calculator 330 and a one-way function h _i using calculators _{340 e i = f i (X} i, m i) (80) d i = h i (X i, m _i ) Find e _i and d _i in (81). Step S16: e _i , d _i , r _i are made public information k, secret information
with s _i, the remainder with the multiplier 350, and input to the remainder with the adder 360, signed by the signature function _{Sg i y i = Sg i (} e i, d i, s i, r i, k) = (d i r _i + e _i s _i ) modk (82). Step S17: (ID _i , X _i , m _i , y _i ) is transmitted to the verifier 800.

(6-B) Processing of Verifier 800 at Signature Verification FIG. 21 is a block diagram of the verifier 800. Upon receiving L messages {I _{i ,} X _{i, mi,} y _i } from the L signers, verifier 800 collectively verifies the signature by the following processing. Step S18: function X _i with Article m _i f _i calculator 810
And the function h _i calculator 820 to obtain e _i and d _i by e _i = f _i (X _i , m _i ) d _i = h _i (X _i , m _i ) (1 ≦ i ≦ L) . Step S19: determine the I _i from ID _i component, e _i created by X _i and said, n times the public information read from the d _i and the storage section 88 {q, a, b, P} with computing function V Point calculator 830
And Z ′ = V ((X _i * d _i ), (I _i * e _i ) | i = 1, ..., L) = (d ₁ X ₁ + ... + d _L X _L + e ₁ I ₁ + … + E _L I _L ) over E _{a, b} (GF (q)) (83) Here, e _i = f _i (X ₁ ,…, X _i , ｛m ₁ ,…, m _i ｝) (84) d _i = h _i (X ₁ ,…, X _i , ｛m ₁ ,…, m _i ｝) where 1 ≦ i ≦ L (85). Step S20: L y _i are input to the adder with remainder 840 together with the public information k, and Y = Σ _{i = 1} ^L y _i modk
The accumulated value Y is obtained in (86), and input to the n-fold calculator 845 which calculates the function Γ (Y * P) together with the public information {q, a, b, P}, and W = Γ (Y * P) = YP over E _{a, b} (GF (q)) (87) Step S21: Examine the 'enter a and W to the comparator 850 W = Z' Z, if they match, finds the L is the document m _i are those signed by the correct signer i, respectively.

[0109] YP≡ than how to make the cumulative value _{Y (y L-1 P)} + {d L (r L P)} + {e L (s L P)} ≡y L-1 P + d L X L + e L I _L ≡ ≡ d (d ₁ X ₁ + ... + d _L X _L + e ₁ I ₁ + ... + e _L I _L ) over E _{a, b} (GF (q)) (88) In that case, the verifier 800 recognizes that the documents _mi (i = 1,... L) are each signed by L correct signers. Evaluation of the embodiment The amount of computation required for basic operations used in signature and verification according to the embodiment of the present invention, the redundancy of the message, the case where the RSA encryption is used, and the case where the Schnorr method is used The following is a comparison. However, the system is a system for performing a multiple signature and its verification, and therefore the second and fifth embodiments of the present invention are evaluated.

The table of FIG. 22 shows a comparison between the RSA encryption, the Schnorr method, and the basic arithmetic expressions used for performing the multiple signature and verification in the second and fifth embodiments. The table in FIG. 23 shows the number of operations required for signature and verification in each system when using the formula in FIG. The table also shows the redundancy of the message, the number of communications required to verify all signatures, and the number of rounds of the message.

[0111] (1) In the calculation used to sign shown in Table amount of processing Figure 22 of the signer's apparatus, the one-way function f, f _i, since the calculation of the h _i is faster than multiplication and n times point calculator Then, the processing amount of each signer apparatus is compared using the number of times the multiplication by the modulus N (including the remainder calculation by the modulus N or the modulus p) on the elliptic curve is performed on the elliptic curve.

Normally, | N | = 1024 and | q | = 160 are recommended. At this time, since the main terms are the first operation, they are almost as shown in FIG. 23. In the second and fifth embodiments, the processing speed is more than five times as fast as the method using the RSA encryption. Further, it is reported that the calculation amount of the n-fold point on the elliptic curve as in the fifth embodiment is about 10 times faster when compared with the signature processing amount using the RSA encryption (for example,
http: //www.certicom.com/html/eccqa.html.)

(2) Processing Amount of Verifier Device In the calculation used for the verification shown in FIG. 22, the calculation of the one-way functions f, f _i , and h _i is performed by multiplication and calculation of the n-fold point on the elliptic curve. Since it is faster, the processing amount of the verifier
The comparison is made using the number of exponentiation multiplications (including the remainder calculation by the modulus N or the modulus p) in the cryptography and the number of executions of the n-fold point calculation on the elliptic curve. As shown in FIG. 23, the amount of calculation required for the verification according to the present invention is equivalent to the case where the RSA encryption method is used, and is almost half the case where the Schnorr method is used.

(3) Redundancy of communication message In the sequential multiple signature, ID information is added to each signature (ID ' _L component) in order to clarify the signer by any method. In the following, the redundancy of the message {ID ', X, m, y} is evaluated by the number of bits of the X component and the y component. The signature component (y component) using the RSA encryption system is D _L ... D ₁ (f (m)). The result is shown in FIG.

In the method of the second and fifth embodiments according to the present invention, L × │X│ + │y│ bits. When applied to the fifth embodiment, | p│ = │q│ = │e│ = 160, | X | = | q
Since it can be | +1, it becomes 161L + 160 bits. When 2 ≦ L ≦ 6, it can be seen that the method of the fifth embodiment is advantageous. (4) Number of Communication and Number of Circulations As described in the background of the invention, in order to perform a multiple signature and its verification using the Schnorr method, it is necessary to make a message twice. Therefore, the required number of times of communication is almost double that of the other systems.

Note that the security of the signature and the batch verification method according to the present invention will be described.
Not be able to calculate the secret information s _i from I _i can guarantee by can be difficult discrete logarithm problem by law p. The inability of a signer device to forge a multiple signature, including the signatures of other signer devices, indicates that the method of the present invention is based on the "Exact Securi"
It can be guaranteed by satisfying the ty ”property.

Regarding the “Exact Security” property, for example,
M. Bellare and P. Rogaway, “RandomOracles are Practi
cal: A Paradigm for Designing Efficient Protocols,
”Proc. Of the First ACM Conference on Computer an
d Communications Security, pp. 62-73, and K. Ohta and
T. Okamoto, “The Exact Security of Multi-Signature
See Schemes, “Technical Report of IEICE ISEC 97-27.

[0118]

As described above, according to the present invention, R
It is possible to realize a signature generation processing speed five times or more that in the case of using the SA method. The verification processing is equivalent to the RSA method, and can achieve twice the speed as compared with the case where the Schnorr method is repeatedly used. When the redundancy of the message is 6 or less, the method according to the present invention and the case where the Schnorr method is repeatedly applied are equivalent, and are more advantageous than the case where the RSA method is used.

[Brief description of the drawings]

FIG. 1A is a block diagram showing a configuration of a system to which a superimposed signature or a multi-signature and a collective verification thereof are applied according to the present invention;
1B is a block diagram showing the configuration of a system to which the individual signature and the collective verification thereof according to the present invention are applied.

FIG. 2 is a block diagram showing a functional configuration related to an initial information setting process of the center device 100 in FIG. 1A or 1B.

3 is a block diagram showing the relevant functional configuration as the signer i apparatus 30 _i process during system subscription in Figure 1A.

FIG. 4 is a diagram showing a communication sequence of superimposed signed information.

[5] signer i apparatus 30 _i a block diagram showing a functional structure associated with the signature generation processing in Figure 1A.

FIG. 6 is a block diagram showing a functional configuration related to signature verification processing of the verifier device 800 in FIG. 1A.

FIG. 7 is a diagram showing a communication sequence of information that has been multiply signed.

FIG. 8 shows a signer i device 30 _i in FIG. 1A in a multiple signature.
FIG. 2 is a block diagram showing a functional configuration related to a signature creation process of FIG.

FIG. 9 is a block diagram showing a functional configuration related to a signature verification process of the verifier device 800 in FIG. 1A in a multiple signature.

FIG. 10 shows a signer i-device 30 in FIG. 1B for an individual signature.
FIG. 6 is a block diagram showing a functional configuration related to processing at the time of system subscription _i .

FIG. 11 is a diagram showing a communication sequence of information in an individual signature.

[12] signer i apparatus 30 _i a block diagram showing a functional structure associated with the signature creation process in FIG. 1B.

FIG. 13 is a block diagram showing a functional configuration related to a signature verification process of the verifier device 800 in FIG. 1B.

FIG. 14 is a block diagram showing a functional configuration related to initial information setting processing of the center device 100 in FIG. 1A when using elliptic curve cryptography.

FIG. 15 is a block diagram showing a functional configuration related to processing when the signer i-device _30i joins the system in the system shown in FIGS. 1A and 1B using the elliptic curve cryptosystem.

FIG. 16A is a diagram showing a superimposed signature using elliptic curve cryptography.
FIG. 13 is a block diagram showing a functional configuration related to a signature creation process of the signer i device 30 _i in the system of FIG.

FIG. 17A is a diagram showing a superimposed signature using elliptic curve cryptography.
FIG. 13 is a block diagram showing a functional configuration related to a signature verification process of the verifier device 800 in the system of FIG.

Figure 18 is a block diagram showing the configuration of a signer i apparatus 30 _i in the system of Figure 1A performing multiple signature using elliptic curve.

FIG. 19 is a block diagram showing a configuration of a verifier device 800 in the system shown in FIG. 1A for performing a multiple signature using an elliptic curve.

Figure 20 is a block diagram showing the configuration of a signer i apparatus 30 _i in FIG. 1B system that provides individual signature using elliptic curve.

FIG. 21 is a block diagram showing a configuration of a verifier device 800 in the system shown in FIG. 1B for performing an individual signature using an elliptic curve.

FIG. 22 is a diagram for explaining a basic operation expression of R to evaluate the present invention;
Table showing comparison with SA method and Schnorr method.

FIG. 23 is a diagram illustrating an evaluation of the present invention.
It is a table shown in comparison with the A method and the Schnorr method.

Continued on front page (31) Priority claim number Japanese Patent Application No. Hei 10-141342 (32) Priority date May 22, 1998 (1998.5.22) (33) Priority claim country Japan (JP) (56) References JP-A-2-275983 (JP, A) JP-A-6-118873 (JP, A) JP-A-5-128132 (JP, A) JP-A-10-133576 (JP, A) Patent 2511464 (JP) , B2) Strict security of multiple signatures, IEICE Technical Report, July 19, 1997, Vol. 97, no. 182, p. 41-52 Consideration on “N-variable exponentiation operation and its application”, IEICE Technical Report, March 18, 1992, Vol. 91, No. 524, p. 27-32 (58) Field surveyed (Int. Cl. ⁷ , DB name) H04L 9/32 G09C 1/00 640 JICST file (JOIS)

Claims (17)

(57) [Claims] An electronic document m is sent to a signer 1
The apparatus to the signer L device (L is an integer of 2 or more) rows cormorants Way Method electronic signature sequentially overlapped, p specifying the number of groups of elements, the group as a starting point of the operation in the group computing element When g and the element g are operated q times, a positive integer q that returns to g is made public as system public information, and each signer i device (i = 1, 2,..., L) has (a) generates a random number s _i, the g, seek I _i by computing s _i times groups using the p, information I _i, personal identification information ID _i of the signer i device, the unidirectional function f _i, the one-way Sex function h _i
Is held, and the first random number s _i is held as secret information. (B) Signed message ( ID ′ _i−1 , X ′ _i−1 , m, Upon receiving the y _'i-1), generates a second random number r _i, obtains the X _i and r _i times groups Starring <br/> calculated using the g, and p, (c) X _i = _{(X 'i-1, X} i) and integrating the unidirectional function <br/> number f _i, the h _i, respectively X' _i, and calculates the _{m, e i = f i (} X 'i , M) d _i = h _i (X ′ _i , m), and (d) these e _i , d _i , and the above r _i , s _i , q, y ′
using _i-1, 'seeking _{i-1 + d i r i} + e i s i mod q, the y _i y' y _i = y and _i, and ID _'i = _(I
D ′ _i−1 , ID _i ) as a message ( ID ′ _i , ID _i ).
_{X 'i, m, y'} i) was sent to the next signer i + 1 system, the verifier apparatus communication text from signer L device (ID _'L, X'
_L , m, y ′ _L ), (e) construct X ′ _i from the first i components of X ′ _L ,
Its X _'i and the document m and the one-way function f _i, h _i
The performed for each operation _{e i = f i (X '} i, m) d i = h i (X' i, m) each to seek i (1 <i <L) , the received (f) obtains ID 'corresponding public information I _i from ID _i component in the _L, the received X' from in _L X _i, respectively,
Using these, the obtained e _i , d _i , and the public information p, a value obtained by calculating X _{i di} times for each i from 1 to L by a multiple component group operation, and I _i ( _i ) Using the received y ′ _L and the public information p and q, g is calculated y ′ _L times to obtain W, Compare Z ' and W, and if they match, document m is L signers 1
A plurality of digital signature collective verification methods, each of which is recognized as being signed by a device or a signer L device. 2. An electronic document m _i (i = 1, 2, 2)
.., L; L is an integer of 2 or more) and the signer i device sequentially superimposes the electronic signatures. P, which specifies the number of elements of the group, p of the group which is the starting point of the operation in the group operation When the element g and the element g are group-operated q times, a positive integer q returning to g is disclosed as system public information, and each signer i device (i = 1, 2,..., L) is represented by (a) generating a first random number s _i, the g, seek I _i by computing s _i times groups using the p, information I _i, personal identification information ID _i of the signer i device, the one-way function f _i, One-way function h _i
And hold the first random number s _i as secret information. (B) The document m ′ _i−1 =
(M ₁ ,..., M _i-1 ) signed message (ID ′)
_{i-1, X 'i-} 1, m' i-1, y 'i-1) receives the generates a second random number r _i, and g, and calculates r _i times groups using the p seeking _{X i, (c) X i} = (X 'i-1, X i), m' i =
(M ′ _i−1 , m _i ), and the one-way function f
_i and h _i are calculated for X ′ _i and m ′ _i , respectively, to obtain e _i = f _i (X ′ _i , m ′ _i ) d _i = h _i (X ′ _i , m ′ _i ), (D) These e _i , d _i , and the above r _i , s _i , q, y ′
using _i-1, 'seeking _{i-1 + d i r i} + e i s i mod q, the y _i y' y _i = y and _i, and ID _'i = _(I
D ′ _i−1 , ID _i ) as a message (ID ′ _i ,
X ′ _i , m ′ _i , y ′ _i ) to the next signer i + 1 device, and the verifier device transmits a message (ID ′ _L , X ′) from the signer L device.
_L, m _'L, y' receives the _L), constitutes a _i 'X from the beginning of the i-number of components of the _L' (e) X,
m ′ _i is constructed from the first i components of m ′ _L , and the one-way functions f _i and h _i are respectively operated on these X ′ _i and m ′ _i to obtain e _i = f _i (X ′ _i , m ′ _i ) d _i = h _i (X ′ _i , m ′ _i ) is obtained for each i (1 < i < L). (f) From the ID _i component in the received ID ′ _L The corresponding public information I _i is obtained from the received X ′ _L to obtain X _i ,
Using with these, the obtained e _i, d _i, further the public information p, the plurality of components group arithmetic, for each i from 1 to L, a value obtained by the X _i is calculated d _i times group, I _i Is calculated in order by e _i times to obtain Z ′. (G) On the other hand, using the received y ′ _L and public information p and q, g is calculated y ′ _L times and W is calculated. A plurality of digital signature collective verification methods for recognizing that the document _mi is signed in a predetermined order by the signer i device if Z 'and W are matched. 3. An electronic document m _i (i = 1, 2, 2, 3)
, L; L is an integer of 2 or more), each of which is individually electronically signed by the signer i device, and these L signatures are collectively verified. In this method, p, which specifies the number of elements in the group, If an element g of the group as a starting point of the operation in group operation, and the element g for calculating q times, publish a positive integer q as return to g as a system public information, each signer i device the 1 (a) Generate a random number s _i , and calculate g by s _i times using p
Seeking I _i and group operation, information I _i, personal identification information ID _i of the signer i device, the unidirectional function f _i, unidirectional function h _i
Publish, a first random number s _i is held as confidential information, (b) generating a second random number r _i, the g, seek X _i by computing r _i times groups using the p, (c) unidirectional function f _i, the h _i, respectively X _i, m _i
Is calculated to obtain e _i = f _i (X _i , m _i ) d _i = h _i (X _i , m _i ) . (D) These e _i , d _i , and the above r _i , s _i , q using, by calculating _{y i = d i r i +} e i s i mod q, sends communication text _{(ID i, X i, m} i, y i) to the verifier device, the verifier device ( e) Message (ID ) from signer 1 device to signer L device
_i, X _i, m _i, upon receiving the y _i), X _i and the document m _i and the one-way function f _i, and calculates the h _i, respectively _{e i = f i (X i} , m i) d _i = h _i ( X _i , m _i ) is obtained for each i (1 < i < L). (f) I _i is obtained from the received ID _i , and the above I _i and X _i are obtained. Using _i e, d _i , and the public information p, for each i from 1 to L, a value obtained by calculating X _{i di} times and a value obtained by calculating I _i e _i times for each i from 1 to L preparative 'seek, (g) on the other hand, using the L y _i public information q received, y' Z calculates sequentially obtains the ^{_{L = Σ L i = 1 y}} i mod q, the y ' _L and public information p, with q, determine the W and g by computing y _'L times, it compares the Z and W, if they match the L document m _i corresponding the L signer i device Are signed by A plurality of digital signature batch verification method to recognize those. 4. The method according to claim 1, wherein
Generating the p and q are prime numbers of pre-1 = pmodq the relationship, (Z / pZ) ^* There is the step of generating a primitive element alpha of, the following equation the _{g g = G 1 (q)} = α ( determined by calculating the ^{p-1) / q} modp, the I _i is [1 number] following equation in step (a) It is calculated by, the calculation for obtaining the X _i in step (b) [2 Number] following formula Done, following equation 3] operation of obtaining the Z 'in the above Symbol step (f) by The calculation for obtaining the W in the step (g) is performed by the following equation: It is performed by 5. An electronic document m _i (i = 1, 2, 2)
, L; L is an integer of 2 or more) by the signer i device individually and individually, and the L signatures are collectively verified. In this method, the parameters q, The parameters a and b パ ラ メ ー タ GF (q) of the elliptic curve and the base point P∈E _{a, b} (GF (q)) on the curve whose order on the elliptic curve is k are disclosed as system public information. The signer i device (i = 1, 2,..., L) generates a random number s _i and uses public information q, a, b, P to obtain I _i = s _i PoverE _{a, b} (GF (q) ) Is calculated, and the information I _i and the personal identification information ID of the signer i device are calculated.
_i , one-way function f _i , one-way function h _i
i as secret information, each signer i device generates a random number r _i ,
X _i = r _i PoverE _{a, b} (GF (q)) is calculated using b and P, and the one-way functions f _i and h _i are calculated as X _i , h _i , respectively.
and calculates the _{m i, e i = f i} (X i, m i) d i = h i (X i, m i) seeking, these e _i, d _i, the r _i, s _i, public information Using k, y _i = d _i r _i + e _i s _i mod k is calculated, and the message (ID _i , X _i , m _i , y _i ) is transmitted to the verifier device. signer i device to communication text from the signer L device (ID _i, X _i, m _i, y _i) When receiving a one-way function for its X _i and the document m _i f _i, h _i
Is calculated for each i (1 < i < L) to obtain e _i = f _i (X _i , m _i ) d _i = h _i (X _i , m _i ), and from the received ID _i The corresponding public information I _i is obtained, and this I _i
X _i, the obtained e _i and received, d _i, with further public information q, a, b, and P, for each i from 1 to _{L, Z '= d 1 X} 1 + ... + d L _{X L + e 1 I 1 +} ... + e L I
_L overE _{a, b} (GF (q)) is calculated to obtain Z ′. On the other hand, using L received y _i and public information q, a, b, P, Y = Σ _{i = 1} ^L y _i mod k W = Y PoverE _a, obtains the W by calculating the _{b (GF (q)),} Z ' is compared with W, if they match the L document m _i of the plurality deemed ones signed by the signer i device respectively Digital signature batch verification method. 6. A signer device in which a plurality of signer i devices (i = 1, 2,...) Sequentially and electronically sign one digitized document m in an electronically signed manner, , A group element g serving as a starting point of the operation in the group operation, and a positive integer q that returns to g when the element g is operated q times and the signer i
Identification information ID _i of the device, storage means for storing secret information s _i, signer (i-1) signed communication text to the document m from the device _{(ID 'i-1, X} ' i-1, m, y 'and _i-1) means for receiving a random number generating means for generating a random number r _i, the r _i and the g and p are input, group operation calculation means to g by computing r _i times Request X _i When, 'means for integrating the _(i-1, X _i, the _{X X i = X)' i} , m is input, calculates a one-way function _{f i, e i = f i} (X ' _i, and f _i calculating means for obtaining m), the X _'i, m is input, calculates a unidirectional function _{h i, d i = h i} (X' i, m) h i calculation for obtaining the An exponent component for inputting e _i , d _i and r _i , s _i , q, y ′ _i−1 , and obtaining y _i = y ′ _i−1 + d _i r _i + e _i s _i mod q and the multiply-add means, ID _'i = _(I 'And _i-1, ID _i) to means, the y _i y' as _i, the communication sentence (ID _'i, X' _i,
m, y ′ _i ) to the next signer i + 1 device. 7. An electronic document m _i (i = 1, 2)
2,..., L; L is an integer of 2 or more) in a signer device in which a plurality of signer i devices sequentially superimpose and sign an electronic signature. The system public information of the element g of the group that is the starting point of the operation and a positive integer q that returns to g when the element g is operated q times and the signer i
Storage means for storing the identification information ID _{i of the} device and the secret information s _i , and a document m ′ _i-1 = (m ₁ ,...,
m _i-1 ) ( ID ′ _i−1 , X ′)
a _{i-1, m 'i,} y' means for receiving the _i-1), a random number generating means for generating a random number r _i, the r _i and the g and p are inputted, r _i times group calculates g A group operation calculating means for calculating X _i by means of: X _i = (X ′ _i−1 , X _i ); a means for integrating _mi = (m ′ _i−1 , _mi ); the X _'i, m' _i is inputted, calculates the one-way function _{f i, e i = f i} (X 'i, m' i) and f _i calculating means for obtaining, said X _'i, m _'i is inputted, it calculates the unidirectional function _{h i, d i = h i} (X' i, m 'i) and h _i calculating means for obtaining said e _i, d _i, the r _{i , s i, q, y '} i-1 is input, y _i = y' and _{i-1 + d i r i} + e i s i index component multiply-add means for determining a _{mod q, ID 'i = (} ID' _i−1 , ID _i ), and the ID ′ _i , X ′ _i , m ′ _i , y _i is input, the y _i 'as _i, the communication sentence _{(ID' y i, X '} i, m'
_i , y ′ _i ) to the next signer i + 1 device. 8. An electronic document m _i (i = 1, 2, 2, 3)
…) Is individually and electronically signed by each of the signer i devices,
A signer device used for a method in which the verifier device collectively verifies these, where p designates the number of group elements, group element g which is the starting point of the operation in group operation, and element g is q Times, the system public information of a positive integer q that returns to g and the signer i
Identification information ID _i of the device, storage means for storing secret information s _i, a random number generating means for generating a random number r _i, the r _i, the g, p is input, the g calculates r _i times X a group operation means for obtaining a _i, the X _i, m _i is input, and f _i function operation means for obtaining a by calculating the one-way function _{f i e i = f i (} X i, m i), the X _i, m _i is _{input, d i = h i (X} i, m i) by calculating the one-way function h _i and h _i function operation means for obtaining, these e _i, d _i, the r _i , s _i, q are input, and _{y i = d i r i +} e i s i seek mod q exponential component multiply-add unit, the _{ID i, X i, m i} , is y _i is input, communication text (I
(D _i , X _i , m _i , y _i ) to the verifier device. 9. The signer apparatus according to claim 6 , wherein said p and q are prime numbers having a relation of 1 = pmodq,
Assuming that the primitive element of (Z / pZ) ^* is α, the above g is obtained by the calculation of the following equation g = α ^{(p−1) / q} modp , and the above s _i , g, and p are inputted, and ] , And the group operation means for calculating the above X _i is given by the following equation: Is a means for calculating 10. An electronic document m_i(I = 1, 2,
.., L; L is an integer of 2 or more).
Electronic signature, and the verifier device verifies these L signatures.
In the signer device of the system for verifying all the parameters, the parameter q of the definition field GF (q) and the parameter of the elliptic curve
A, b∈GF (q), a song whose order on the elliptic curve is k
Base point P∈E on line_{a, b}System with (GF (q))
Public information and identification information ID of the signer i-device_i, Secret
News_iStorage means for storing_i, P is input, and P is expressed as s on the elliptic curve._iDouble
As I_iIn search of I_iPublish_iMeans for calculating multiple points,  Random number r_iRandom number generating means for generating the q, a, b, P and r_iIs entered and the above elliptic curve
With P_iX as times_iFind r_iMultiple point calculating means;_i, Above m _i Is input and the public one-way function f_i
And e_i= F_i(X_i, M _i F_iCalculating means;_i, Above m _i Is input and the public one-way function h_i
Is calculated as d_i= H_i(X_i, M _i H)_iCalculating means;_i, D_i, R above_i, S_i, K is input, and y_i= D_ir_i+ E_is_imultiplication / addition means with remainder for obtaining mod k;_i, X_i, M_i, Y_iIs entered and the message
(I_i, X_i, M_i, Y_i) To the next verifier device
Signer device comprising: 11. A digitized one document m, an L number (L is an integer of 2 or more) verifier apparatus of a multiple signature verifying those sequentially signed with the signer apparatus, information I
D ′ _L is ID ′ _i = ( ID ′ _i−1 , ID _i ) (i = 1,
2,..., L; L is an integer of 2 or more), and the information X ′ _L is formed by X ′ _i = (X ′ _i−1 , X _i ),
And p, storage means for public information element g of the group as a starting point of the operation in group operation is stored that specifies the number of groups of elements, the signer apparatus L communication text from _{(ID 'L, X' L} , m , Y '
Means for receiving a _L), the means constituting the _i 'X from the beginning of the i-number of components of the _L' X, the document m and the X _'i is inputted, the public one-way function f _i
The calculated _{e i = f i (X '} i, m) and function f _i calculating means for calculating a respective i, the X' _i and m are inputted, d calculates a public one-way function h _{i i = h i (X 'i} , m) and function h _i calculation means for obtaining for each i, the ID' means for determining corresponding public information I _i from ID _i components in _L, X in the X _'L means for determining _i , the above I _i , X _i , the above created e _i , d _i , and the public information p are input, and X _i
Is calculated d _i times and I _i is calculated e _i times in order to obtain a multi-component group calculation means for obtaining Z ′. The above y ′ _L and public information p and g are input. , G to y ′ _L
A group operation calculating means for obtaining W by performing the above operations; Z 'and W are input; and W = Z' is checked. If they match, the document m is signed by L correct signer devices. And a comparing unit that outputs the following. 12. An electronic document _mi (i = 1, 2, 2)
.., L; L is an integer of 2 or more), which is a verifier apparatus of a superimposed signature that verifies a superimposed signature that has been sequentially superimposed by the signer i apparatus, where information ID ′ _L is ID ′ _i = ( ID ′ _{i) -1} , ID _i ) (i
= 1, 2,..., L; L is an integer of 2 or more)
'Is _L X' information X 'is composed of _{(i-1, X i,} m i = X)' L is constituted by _{m 'i = (m' i} -1, m i), the number of groups of elements and p, storage means for public information element g of the group as a starting point of the operation in group operation is stored that specifies the communication sentence from the signer apparatus _{L (ID 'L, X'} L, m 'L,
'means for receiving _L), X' y 'means constituting the _i, m' X from the beginning of the i-number of components of the _L and means for configuring the m _'i from the head of the i-number of components of the _L, the m _'i and the X' _i is input, and the function f _i calculating means for calculating _{e i = f i (X '} i, m'i) to calculate a public one-way function f _i a for each i, the X _'i and m' _i is inputted, published unidirectional function h _i
The calculated _{d i = h i (X '} i, m'i) and function h _i calculation means for obtaining for each i, the ID' means for determining corresponding public information I _i from ID _i components in _L, means for determining the X _i in the X _'L, the X _i, I _i, e _i created above, d _i, public information p is input, for i from multiple components 1 to L X _i
A value obtained by calculating d _i times group of 'a plurality of components group arithmetic calculation means for obtaining, the y' by calculating a value obtained by calculating the I _i e _i times group sequentially Z _L and public information p, g is input It is, the g y _'L
A group operation calculation means for obtaining a W then rotate operations, the Z 'and W are inputted, W = Z' examines the, if they match, the document m _1, ..., m _L is the L good signer A verifier device comprising: a comparing unit that outputs that the device is signed by the device. 13. The public information of p which designates the number of elements of the group, the element g of the group which is the starting point of the operation in the group operation, and the positive integer q which returns to g when the element g is operated q times are stored. storage means has signer i device (i = 1,2, ..., L : L is an integer of 2 or more) means for receiving communication text (ID _i, X _i, m _i, y _i) from the above and m _i was received X _i and the reception is input, single
A function f _i calculating means for calculating a directional function f _i to obtain e _i = f _i (X _i , m _i ); and the received X _i , m _i as input, and a one-way function h _i
The by calculating _{d i = h i (X i} , m i) and the function h _i calculating means for obtaining, the public information I _i individual identification information ID _i thus received
And a value obtained by inputting I _i and X _i , e _i and d _i created above, and public information p, calculating X _{i di} times for i from 1 to L, and I _i Z by calculating the value computed e _i times in order 'and the plurality of components group arithmetic calculation means for obtaining, and the L number of the received y _i public information q is ^{_{input, y' L = Σ L i}} = 1 'exponent component calculating means for calculating _L, and the above-mentioned y' y by calculating y _i mod q _L and public information p, and the g is input, the g y _'L
A group operation calculation means for obtaining a W then rotate operations, the Z 'and W are inputted, W = Z' examines the, if they match, the L document m _i is the L good signer i device And a comparing means for outputting that the signature is signed by the verifier. In any of the verifier apparatus 14. The method of claim 11 to 13, the p and q are prime numbers 1 = pmodq the relationship, and α a (Z / pZ) ^* primitive elements, g is Is given to the calculation of the following equation g = α ^{(p−1) / q} modp. The above group operation means is calculated by the following equation: Is a means for calculating 15. The parameter q of the definition field GF (q), the parameters a and b∈GF (q) of the elliptic curve, and the base point P∈E _{a, b} (curve whose order on the elliptic curve is k) GF
(Q)) from the storage means, and a message (ID _i , X _i , m) from the signer i device (i = 1, 2,..., L; L is an integer of 2 or more). _i , y _i ), the document _mi and the X _i are input, a public one-way function f _i is calculated, and e _i = f _i (X _i , m _i ) is calculated for each i. and functions f _i calculating means which calculates, the X _i and m _i is input, d _i = h _i (X _i, m _i) by calculating the public one-way function h _i function h _i calculate the determining for each i means, means for determining the corresponding public information I _i from the ID _i, created above e _i, d _i, public information q, a, b, P is input, for i from multiple components 1 to L, and adding to compute the multiplication d _i X _i and e _i I _i on the elliptic curve in the _{order, Z '= d 1 X 1} + ... + d L X L + e 1 I 1 + ... + e L I
N over-point calculating means for obtaining _L overE _{a, b} (GF (q)), and inputting the above y _i and public information q, a, b, P, Y =
Σ Calculate _{i = 1} ^L y _i mod k and set P on the elliptic curve to Y
W = Y PoverE _{a, b An} n-fold point calculating means for calculating (GF (q)), Z 'and W are inputted, it is checked whether W = Z', and if they match, the L documents m _i
And a comparing means for outputting that each signer i device has signed. 16. A computer-readable recording medium in which a program for causing a computer to function as the signer apparatus according to claim 5 is recorded. 17. A computer-readable recording medium in which a program for causing a computer to function as the verifier device according to claim 11 is recorded.