JP2002040935A - Multiple signature generation device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a multiple signature allowing a signer to freely alter a document and verify an alteration of the document, a person who has altered it, and further a sequence of the document flow at the time of verifying it without specifying the sequence of the document flow beforehand, relating to an encipherment technique as information security technology, especially relating to a digital signature technique by plural persons. SOLUTION: Step 1: Initial setting. Step 2: Signature generation. Step 2-1: Signature generation by I1. Step 2-2: Signature generation by Ij. Step 3: Signature verification. Therefore, a multiple signature system is provided in which the alteration part of the document and the sequence of the signatures can be verified while realizing freedom of the document and sequence.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cryptographic technique as an information security technique,
It concerns digital signature technology by multiple people.

[0002]

2. Description of the Related Art A secret communication method is a method of performing communication without leaking communication contents to a person other than a specific communication partner.
The digital signature method is a communication method that shows the validity of the communication contents to the communication partner and proves the identity of the person. This signature scheme uses an encryption scheme called public key encryption. Public key cryptography is a method for easily managing different encryption keys for each communication partner when there are many communication partners.
It is a fundamental technology that is indispensable for communicating with many communication partners. Briefly, this is a method in which the encryption key and the decryption key are different, and the decryption key is kept secret, but the encryption key is made public. The factors used as the basis for the security of this public key cryptosystem include prime factorization and the discrete logarithm problem. Discrete logarithm problems are typically defined over a finite field or over an elliptic curve, as described by Neil Koblitz, "Akous in Namba Aseolii and
Cryptography "(Neal Koblitz," A
Course in Number theory a
nd Cryptography ", Spinger-
Verlag, 1987).

A digital signature scheme by a plurality of persons, which is an application of the digital signature scheme, is called a multiple signature. In the following, a multisignature scheme based on the discrete logarithm problem over a finite field is given as a conventional example. The details are described in detail in Jun Shinbo, "A variant of ElGamal signature suitable for multiple signatures", and "Cryptography and Information Security Symbol SCIS94".

FIG. 3 shows a conventional example of a method of constructing a multisignature scheme based on a discrete logarithm problem on a finite field. The procedure of the conventional example will be described below with reference to FIG.

[0005] Step 1. Initial setting Finite field Fp (p is a prime number), base point g∈Fp, its order ord (g) = n is a prime number, h1 is Zn * = {1,. . , N−1}, and the secret key xi of each signer Ii
Find Zn * and the public key on Fp as yi = g xi.

[0006] Step 2. Signature generation It is assumed that Il,..., Ij apply a digital signature to the document m.

Step 2-1. Signature generation by Il For a random number k1 {Zn *, r_ {1} = g {k1 (mod p), s_ {1} = x1 * h (m) + k1 * r_ {1} (m
od n),. Next, (s_ {1}, r_ {1}, m) is transmitted to the next user as a signature for m.

[0008] Step 2-2. Signature generation by Ij.
(S_ {j-1}, r_ {1}, ..., r_ {j-
Ij that has received (1 署名, m) generates a signature for m in the following procedure. For a random number kj∈Zn *, r_ {j} = g ＾ kj (mod p), s_ {j} = s_ {j−1} + xj * h (m) + kj *
r_ {j} (mod n), is obtained. Next, (s_ {j}, r_ {1},.
{J}, m) is sent to the next user as a signature for m.

[0009] Step 3. Signature verification Signature sentence (s_ {j}, r_ {1}, ..., r_ {j},
g), g {s_ {j} = (y1 *... * yj)} h (m)
(R_ {1} r_ {1} * ... * r_ {j} r_
{J}) is verified. If so, consider the signature valid.

In the above conventional example, the document cannot be changed by the signer. Also, the signature order of the signer cannot be verified at the time of verification. The method that can verify the signature order does not satisfy the flexibility of the order, such as specifying the order of the signers in advance. The following literature is detailed about this method. M. Burmester, Yvo De
smedt, Hiroshi Doi, Masahir
o Mambo, Eiji Okamoto, m_
｛I｝ tsuru Tada, and Y. Yoshi
FUJI, @A Structured ElGam
al-Type Multisignature Sc
heme '', Advances_ ｛i｝ n Cryp
strategy-Proceedings of PK
C'2000, LectureNotes_ @ i @ n
Computer Sc_ @ i @ ence, (200
0), Spr_ {i} nger−Ver_ {1} ag,
466-482.

However, in the situation of distribution of free software using the Internet, a situation in which an arbitrary user improves the software and distributes the software can be sufficiently considered. In such a situation, to use multiple signatures as a technique for identifying a malicious user while protecting the user's copyright, the signer can freely modify the document,
It is necessary to have a property that can verify the document change location, the person who changed the document, and the document flow order at the time of verification without specifying the document flow order in advance. However, there is no such technology that constitutes such a thing.

[0012]

In a conventional multiple signature, a document cannot be changed by a signer. In addition, the signature order of the signer cannot be verified at the time of verification,
The method that can verify the signature order does not satisfy the flexibility of the order, such as specifying the order of the signers in advance.

The present invention has been made in view of the problems in the conventional example, and allows a signer to freely change a document, and to specify a document flow at the time of verification without previously specifying a flow order of the document. The purpose of the present invention is to provide a multi-signature that can verify the place of change, the person who made the change, and the order in which the signatures were generated.

[0014]

According to the present invention, in order to solve the above-mentioned problems, in claim 1, Ii is the i-th signer, the original document is M_ {1} = m_ {1}, and the subscript is When it is necessary to specify i, it shall be expressed as _ {i}, and the document shall be a general term for all electronic data such as software, data, and documents, and the i-th person who made the changes thereafter will be the document before. M_ {1, 2,. . . , I-1} are changed to M_ {1, 2,. . . , I}, and Ii is the received document M_ {1, 2,. . . , I-1}, m_ {i} = Diff (M_ {1,2, ..., i-
1}, M_ {1, 2,. . . , I}), that is, m_ {i} is M_ {1,
2,. . . , I−1} and M_ {1, 2,. . . , I}, and from the difference using the function Pat, the document is M_ {1, 2,. . . , I} = Pat (m_ {1}, m
_ {2}, ..., m_ {i}), and each signer Ii sets its ID to I
Di, a secret key sk_ {i}, and a public key pk_ {i},
The input of the message restoration type signature function sign is pk_
{I}, m_ {i}, and the output, that is, the signature is SIG_
Let SIG_ {i} be SIG_ {i} = (r_
{I}, s_ {i}), and r_ {i} is the signature SI
G_ {i} is a part that can be restored at the time of verification, s_ {i} is the remaining part of SIG_ {i}, and conversely, the input of the function rec for restoring the document from the signature is pk_ {i}, r_
{I}, s_ {i}, and as its output the document m_
{I} is restored, that is, sign (sk_ {i}, m_ {i}) = SIG_
｛I｝ = (r_ ｛i｝, s_ ｛i｝) rec (pk_ ｛i｝, (r_ ｛i｝, s_ ｛i｝))
= M_ {i}, h1 is a hash function for outputting the original input of an arbitrary bit length to the range of the domain of the signature generation function, and%
And # are arbitrary operations (A% B) # B = A, such as modular multiplication, which have the following inverse operation relationship. The signature generation step is as follows.
When digitally signing {1} = m_ {1},
SIG_ {1} = sign (sk_ {1}, h1 (m_
{1} || ID_ {1})) = (r_ {1}, s_
{ID}, (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, to the next user, and includes a signature (ID_ {1}, s_ {1}, m_ {1}),. (I
D_ {j-2}, s_ {j-2}, m_ {j-2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}), and a message restoration type signature sign is added to the obtained m_ {j} and r_ {j−1} of the received signature statement.
SIGj = sign (skj, r_ {j-1}% h1
(M_ {j} || ID_ {j})) = (r_ {j}, s
_ {J}), (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, m_ {1}), ..., (ID_ {j-1}, s_
{J-1}, m_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, m_ {j}), i = j,
, 2, Ti = rec (pk_ {i}, (r_ {i}, s_
{I})) r_ {i-1} = Ti # h1 (m_ {i} || IDi), and T1 = rec (pk_ {1}, (r_ {1}, s_
{1})), determining whether T1 = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that it enables the verification of the document change and the document distribution order without making the order of the users who distribute the document possible.

According to a second aspect of the present invention, as the message restoration type signature according to the first aspect, a finite field Fp (p is a prime number), a base point g∈Fp, and its order ord (g) = n are prime numbers, and each signer Ii uses ID as IDi and secret key xiｘ
Zn * = {1,. . , N−1}, and the public key is yi on Fp
= G ＾ xi, and h1 is a hash function for outputting to Zn * with respect to the original input having an arbitrary bit length. The signature generation step is as follows.
When digitally signing {1} = m_ {1},
For a random number k1∈Zn *, R1 = g ＾ k1 (mod p), r_ {1} = R1 / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n), and (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, and transmitting the signature to the next user. The signature sentence (ID_ {1}, s_ {1} m_ {1}),. ID
_ {J-2}, s_ {j-2}, m_ {j-2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, for a random number kj {Zn *, Rj = g {kj (mod p) r_ {j} = Rj / ( h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj
(Modn), and (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, m_ {1}), ..., (ID_ {j-1}, s_
{J-1}, m_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, m_ {j}), i = j,
, 2, Ri = g ＾ (1 / s_ ｛i｝) yi ＾ (r_ ｛i｝ / s
_ {I}) (mod p), Ti = Ri / r_ {i} (mod n) r_ {i-1} = Ti / h1 (m_ {i} || IDi)
(Mod n), R1 = g {(1 / s_ {1}) y1} (r_ {1} / s
_ {1}), T1 = R1 / r_ {1} (mod n), T1 = h1 (m_ {1} || ID_ {1}), and a multiple signature based on the determination result The multi-signature generating apparatus is characterized in that the document signature can be changed for each user, and the document change and the document distribution order can be verified without fixing the order of the users who distribute the documents. .

According to a third aspect of the present invention, as the message restoration type signature according to the first aspect, an elliptic curve E / Fp on a finite field Fp (p: prime number), a base point G∈E (Fq), and an order ord (G ) = N is a prime number, and each signer Ii
Let D be IDi and the secret key xiｘZn * = {1,. . , N-
1}, the step of obtaining the public key as Yi = xiG on E; and h1 is a hash function for outputting to the Zn * with respect to the original input having an arbitrary bit length. The signature generation step is as follows. When a digital signature is applied to document M_ {1} = m_ {1}, E / F
determining R1 = k1G = (R1_x, R1_y) on p; r_ {1} = R1_x / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n), and (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, to the next user, and includes a signature (ID_ {1}, s_ {1}, m_ {1}),. (I
D_ {j-2}, s_ {j-2}, m_ {J_2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}) and a document M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, the E / F
determining Rj = kjG = (Rj_x, Rj_y) on p; r_ {j} = Rj_x / (h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (m
odn), and (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j},
m. {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user. The signature verification step includes a signature sentence (ID_ {1}, s).
_ {1}, m_ {1}), ..., (ID_ {j-1}, s
_ {J-1}, m_ {j-1}), (ID_ {j}, s
_ {J}, r_ {j}, m_ {j}), i =
For j,..., 2, Ri = (1 / s_
{I}) G + (r_ {i} / s_ {1}) Yi = (Ri
_X, Ri_y), sequentially obtaining Ti = Ri_x / r_ {i} (mod n) r_ {i-1} = Ti / h1 (m_ {i} || IDi), and R1 on Fp. = (1 / s_
{1}) G + (r_ {1} / s_ {1}) Y1 = (R1
_X, R1_y), a step of determining T1 = R1_x / r_ {1}, a step of determining whether T1 = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that it enables the document to be changed for each user and can verify the document change and the document distribution order without fixing the order of the users who distribute the document.

In a fourth aspect, a set of small prime numbers is {r_ {1}} as the message restoration type signature according to the first aspect.
= {2,3,5, ...}, and each signer Ii has its ID
To IDi, two large t-bit primes p_i, q_i
Is secretly generated, and the product of each element of {r_ {1}, n_
For {i, 1} = p_ {i} q_ {i} r_ {1}, L_ {i, 1} = LCM ((p_ {i} −1),
(Q_ {i} -1), (r_ {1} -1)) (least common multiple) and e_ {i, 1}, d_ {i, 1} 1,
2,. . , N_ {i, 1} _1} to e_ {i, 1} * d_ {i, 1} = 1 (mod L_
{I, 1}), and for each {r_ {1}, {n_ {i, 1}, e_ {i, 1} is the signer Ii's public key, and {d_ {i, Let 1｝｝ be the corresponding private key,
h1 is a hash function that outputs 2t bits to an original input having an arbitrary bit length. The signature generation step is performed when the signer Il applies a digital signature to the document M_ {1} = m_ {1}. , N_ {1, l_ {1}> h1 (m
_ {1} || ID_ {1}) n_ {1, l_
For {1}, sgn_ {1} = h1 (m_ {1} || ID_ {1})
{(D_ {1, l_ {1}) (mod n_ {1,
l_ {1}), and (ID_ {1}, sgn_
({1}, l_ {1}, m_ {1}) as a signature for m_ {1}, and transmitting the signature to the next user (ID_ {1}, l_ {1}, m_
{1}), ..., (ID_ {j-2}, l_ {j-2},
m_ {j-2}), (ID_ {j-1}, sgn_ {j
−1}, l_ {j−1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, n_ {j, l_ {j}> sgn_ {j-1} (+) h
1 (m_ {j} || ID_ {j}), where (+) is exclusive OR, and sgn_ {j} = (sgn_ {j-1) ｝ (+) H1 (m
_ {J} || ID_ {j}))} (d_ {j, 1_
{J}) (mod n_ {j, l_ {j}), and (ID_ {j}, l_ {j}, s
gn_ {j}, m_ {j}) is a signature for m_ {j}, and (ID_ {1}, sgn_ {1}, m_
{1}), ..., (ID_ {j-1}, sgn_ {j-
1}, m_ {j-1}, (ID_ {j}, sgn_
{J}, m_ {j} is (m_ {1}, ..., m_
{J}) as a signature to the next user, and the signature verification step includes a signature (ID
_ {1}, l_ {1}, m_ {1}), ..., (ID_
{J-1}, l_ {j-1}, m_ {j-1}), (I
D_ {j}, l_ {j}, sgn_ {j}, m_
{J}), T = sgn_ {i} e_ {i, l_ {i} (mod
n_ {i, l_ {i}) sgn_ {i-1} = T (+) h1 (m_ {i} || I
Di) and T = sgn_ {1} e_ {1,1_ {1} (mod
n_ {1, l_ {1}), determining whether T = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. It is a multi-signature generation device characterized in that the document can be changed every time, and the document change and the document distribution order can be verified without fixing the order of the users who distribute the document.

In claim 5, Ii is the i-th signer, the original document is M_ {1} = m_ {1}, and if it is necessary to specify the subscript i, it is expressed as _ {i}. , And a document is a general term for all electronic data such as software, data, and documents, and the i-th modifier after this is the document M_ {1, 2,. . . , I-1} are changed to M_ {1, 2,. . . , I}, and Ii is the received document M_ {1, 2,. . . , I-1}, m_ {i} = Diff (M_ {1,2, ..., i-
1}, M_ {1, 2,. . . , I}), that is, m_ {i} is M_ {1,
2,. . . , I−1} and M_ {1, 2,. . . , I}, and M_ {1, 2,. . . , I} = Pat (m_ {1}, m
_ {2}, ..., m_ {i}), and each signer Ii sets its ID to I
Di, a secret key sk_ {i}, and a public key pk_ {i},
The input of the message restoration type signature function sign is pk_
{I}, m_ {i}, and the output, that is, the signature is SIG_
Let SIG_ {i} be SIG_ {i} = (r_
{I}, s_ {i}), and r_ {i} is the signature SI
G_ {i} is a part that can be restored at the time of verification, s_ {i} is the remaining part of SIG_ {i}, and conversely, the input of the function rec for restoring the document from the signature is pk_ {i}, r_
{I}, s_ {i}, and as its output the document m_
{I} is restored, that is, sign (sk_ {i}, m_ {i}) = SIG_
｛I｝ = (r_ ｛i｝, s_ ｛i｝) rec (pk_ ｛i｝, r_ ｛i｝, s_ ｛i｝) = m
_ {I}, and the encryption function and the decryption function of the symmetric encryption are
E (K, m) = c, D (K, c) = m, where m is a document, c is a ciphertext, K is a key for symmetric key encryption, and h1 is an input having an arbitrary bit length. A hash function to be output in the range of the domain of the signature generation function, h2 is a hash function to output the key length of the symmetric encryption for an input of an arbitrary bit length, and% and # are mutually Arbitrary operation (A% B) # B = A in the inverse operation relationship, and the signature generation step is such that the signer Il
When digitally signing {1} = m_ {1},
SIG_ {1} = sign (sk_ {1}, h1 (m_
{1} || ID_ {1})) = (r_ {1}, s_
{1}), a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and m_ {1} || ID_ {1} To obtain the output c_ {1} = E (K1, m_ {1} || ID_ {1}) by the encryption function E, and (ID_ {1}, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
{J-1}), the user Ij restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}), and the obtained m_ {j} is output by the message restoration type signature sign SIGj = sign (skj, r_ {j−1}% h1
(M_ {j} || ID_ {j})) = (r_ {j}, s
_ {J}) and a session key Kj Kj = h2 (r_ {j-1}% h1 (m_ {j} || I
D_ {j}) and an output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E And (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1}, s_
{J-1}, c_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, c_ {j}), i = j,
, 2, Ti = rec (pk_ {i}, (r_ {i}, s_
{I})), Ki = h2 (Ti), m_ {i｝ ′ || IDi ′ = D (Ki, c_ {i}), a step of determining IDi ′ = IDi, and a determination result And the step of restoring m_ {i} = m_ {i} ', r_ {i-1} = Ti # h1 (m_ {i} || IDi) is sequentially repeated, and T1 = rec ( pk_ {1}, (r_ {1}, s_
{1})), K1 = h2 (T1), m_ {1} '|| ID_ {1}' = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that the document can be changed and the document change and document distribution order can be verified without fixing the order of users who distribute the document.

According to a sixth aspect of the present invention, as the message restoration type signature according to the fifth aspect, a finite field Fp (p is a prime number), a base point g∈Fp, and its order ord (g) = n are prime numbers. Ii uses ID as IDi and secret key xiｘ
A step of obtaining Zn and a public key as yi = gｉxi on Fp, and h1 is a Zn * with respect to an original input having an arbitrary bit length.
= {1,. . , N−1},
In the signature generation step, the signer Il confirms that the document M_ {1}
= M_ {1}, a random number k
For 1∈Zn *, R1 = g ＾ k1 (mod p), r_ {1} = R1 / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
odn),, a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and a step of calculating m_ {1} || ID_ {1} Determining the output c_ {1} = E (K1, m_ {1} || ID_ {1}) by the encryption function E, and (ID_ {1}, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
{J-1}), the user Ij restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, for a random number kj {Zn *, Rj = g {kj (mod p) r_ {j} = Rj / ( h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj
(Mod n), and a session key Kj Kj = h2 ((r_ {j-1} * h1 (m_ {j} ||
Idj) (mod n)) and the output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E. Calculating step, (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1}, s_
{J-1}, c_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, c_ {j}), i = j,
, 2, Ri = g ＾ (1 / s_ ｛i｝) yi ＾ (r_ ｛i｝ / s
_ {I}) (mod p), Ti = Ri / r_ {i} (mod n), Ki = h2 (Ti), m_ {i} ′ || IDi ′ = D (Ki, c_ {i}), , Determining IDi ′ = IDi, verifying the signature based on the determination result, m_ {i} = m_ {i} ′, r_ {i−1} = Ti / h1 (m_ {i ｝ || IDi)
(Mod n) are sequentially repeated, and R1 = g {(1 / s_ {1}) y1} (r_ {1} / s
_ {1}), T1 = R1 / r_ {1} (mod n) K1 = h2 (T1), m_ {1} '|| ID_ {1}' = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that the document can be changed and the document change and the document distribution order can be verified without fixing the order of the users who distribute the document.

According to a seventh aspect of the present invention, as the message restoration type signature according to the fifth aspect, an elliptic curve E / Fp on a finite field Fp (p: prime number), a base point G∈E (Fq), and an order ord (G ) = N is a prime number, and each signer Ii
D is IDi, secret key xi @ EZn, and public key is Y on Ei.
= XiG, and h1 is given by Zn * = {1,. . , N−1}, the signature generation step is as follows. When the signer Il applies a digital signature to the document M_ {1} = m_ {1}, Determining R1 = k1G = (R1_x, R1_y) on E / Fp; r_ {1} = R1_x / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
odn),, a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and a step of calculating m_ {1} || ID_ {1} Determining the output c_ {1} = E (K1, m_ {1} || ID_ {1}) by the encryption function E, and (ID_ {1}, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
{J-1}), the user Ij restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, the E / F
determining Rj = kjG = (Rj_x, Rj_y) on p; r_ {j} = Rj_x / (h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (m
odn), and a session key Kj Kj = h2 ((r_ {j-1} * h1 (m_ {j} ||) used in the encryption function.
Idj) (mod n)) and the output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E. Calculating step, (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1},
s. . {J-1}, c_ {j-1}), (ID_
Using {j}, s_ {j}, r_ {j}, c_ {j}), for i = j,..., 2, Ri = (1 / s_ {i}) G + (r_ {i} / S_
{I}) Yi = (Ri_x, Ri_y) (operation on E / Fp), Ti = Ri_x / r_ {1} (mod n) Ki = h2 (Ti), m_ {i} ′ || IDi ′ = D (Ki, c_ {i}), the step of determining IDi '= IDi, the step of verifying the signature based on the determination result, and the step of m_ {i} = m_ {i}', r_ {i-1 ｝ = Ti / h1 (m_ {i} || IDi)
(Mod n) are successively repeated to obtain R
1 = (1 / s_ {1}) G + (r_ {1} / s_
{1}) Y1 = (R1_x, R1_y) (operation on E / Fp), T1 = R1_x / r_ {1} (modn), K1 = h2 (T1), m_ {1} ′ || ID_ {1} ′ = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that the document can be changed and the document change and document distribution order can be verified without fixing the order of users who distribute the document.

According to an eighth aspect, a set of small prime numbers is {r_ {1}} as the message restoration type signature according to the fifth aspect.
= {2,3,5, ...}, and each signer Ii has its ID
To IDi, two large t-bit primes p_i, q_i
Is secretly generated, and the product of each element of {r_ {1}, n_
For {i, 1} = p_ {1} q_ {i} r_ {1}, L_ {1,1} = LCM ((p_ {i} _1),
(Q_ {i} _1), (r_ {1} _1)) (least common multiple) and e_ {i, 1}, d_ {i, 1} 1,
2,. . , N_ {i, 1} _1} to e_ {i, 1} * d_ {i, 1} = 1 (mod L_
{I, 1}), and for each {r_ {1}, {n_ {i, 1}, e_ {i, 1} is the signer Ii's public key, and {d_ {i, Let 1｝｝ be the corresponding private key,
h1 is a hash function that outputs a 2t-bit length with respect to the original input having an arbitrary bit length.
When the signer Il applies a digital signature to the document M_ {1} = m_ {1}, n_ {1,1_ {1}> h
N_ {1,1 which becomes 1 (m_ {1} || ID_ {1})
_ {1}, sgn_ {1} = h1 (m_ {1}
|| ID_ {1})} (d_ {1, l_ {1})
(Mod n_ {1, l_ {1}), a step of determining a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, Determining the output c_ {1} = E (K1, m_ {1} || ID_ {1}) of {1} || ID_ {1} by the encryption function E; and (ID_ {1}, l_ {1 ｝, S
gn_ {1}, c_ {1}) as a signature for m_ {1} to the next user;
D_ {1}, l_ {1}, c_ {1}), ..., (ID_
{J-2}, l_ {j-2}, c_ {j-2}), (I
D_ {j-1}, l_ {j-1}, sgn_ {j}, c
_ {J-1}), a step of restoring m_ {1},..., M_ {j-1} from a verification step described later, . . , J-1} = P
at (m_ {1}, m_ {2}, ..., m_ {j-1})
Restoring a document according to M_ ｛1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, n_ {j, l_ {j}> sgn
_ {J-1} (+) h1 (m_ {j} || ID_
Here, (+) is an exclusive OR, and sgn_ {j} = (sgn
_ {J-1} (+) h1 (m_ {j} || ID_
{J})) {(d_ {j, l_ {j}) (mod n
_ {J, l_ {j}), and a session key Kj Kj = h2 (sgn_ {j−1} (+) h1 (m_
{J} || ID_ {j})) and the output of m_ {j} || ID_ {j} by the encryption function E c_ {j} = E (Kj, m_ {j} || ID_} j}), and (ID_ {j}, sgn_
Let {j}, l_ {j}, c_ {j}) be a signature for m_ {j} and (ID_ {1}, l_ {1}, c_
{1}), ..., (ID_ {j-1}, l_ {j-1},
c_ {j-1}), (ID_ {j}, l_ {j}, sg
n_ {j}, c_ {j}) to (m_ {1},..., m_
{J}) as a signature to the next user, and the signature verification step includes a signature (ID
_ {1}, l_ {1}, c_ {1}), ..., (ID_
{J-1}, l_ {j-1}, c_ {j-1}), (I
D_ {j}, l_ {j}, sgn_ {j}, c_
{J}), T = sgn_ {i} e_ {i, l_ {i} (mod
n_ {i, l_ {i}) ki = h2 (Ti), m_ {i} ′ || IDi ′ = D (ki, c_ {i}), and a step of determining IDi ′ = IDi Verifying the signature based on the determination result; m_ {i} = m_ {i} ', sgn_ {i-1} = T (+) h1 (m_ {i} ||
Di) are sequentially repeated, and T1 = sgn_ {1} e_ {1,1_ {1} (mo
dn_ {1,1_ {1}) K1 = h2 (T1), m_ {1} '|| ID_ {1}' = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. The multi-signature generation device is characterized in that the document can be changed and the document change and the document distribution order can be verified without fixing the order of the users who distribute the document.

[0022]

Embodiment 1 FIG. 1 shows a multiple signature using a message restoration type signature based on a discrete logarithm problem on a finite field. The multi-signature generation device will be described below with reference to FIG.

Step 1. Initial setting Finite field Fp (p is a prime number), base point g∈Fp, its order ord (g) = n is a prime number, and h1 is a hash function that outputs to Zn * for an original input of an arbitrary bit length And Each signer Ii assigns its ID to IDi, secret key xiｘZn * = {1,. . , N−1}, and the public key yi = g ＾ xi (mod p). When the signer Il receives the document M_ {1} = m_ {1}
, And the i-th modifier after this creates documents M_ {1, 2,. . . , I-1} are changed to M_ {1, 2,. . . , I}, and Ii is the received document M_ {1, 2,. . . , I−1} is defined as m_ {1} = Diff (M_ {1, 2,..., I−
1}, M_ {1, 2,. . . , I}), that is, m_ {i} is M_ {1,
2,. . . , I−1} and M_ {1, 2,. . . , I}, and from the difference using the function Pat, the document is M_ {1, 2,. ,. , I} = Pat (m_ {1}, m
_ {2}, ..., m_ {i}).

Step 2. Signature generation

Step 2-1. Signature generation by Il For a random number k1∈Zn *, R1 = g ＾ k1 (mod p), r_ {1} = R1 / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n),. (ID_ {1}, s_ {1}, r_ {1},
m_ {1}) is transmitted to the next user as a signature for m_ {1}.

Step 2_2. Signature generation by Ij Signature sentence (ID_ {1}, s_ {1}, m_ {1}),
..., (ID_ {j-2}, s_ {j-2}, m_ {j-
2}), (ID_ {j−1}, s_ {j−1}, r_
{J-1}, m_ {j-1}) user Ij
Is M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2}, ..., m_ {j-1}). Next, the document M_ $ 1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J｝). For the obtained m_ {j}, a random number kj {Z
Using n *, Rj = g {kj (mod p) r_ {j} = Rj / (h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (mo
dn) and are obtained. (ID_ {j}, s_ {j}, r_ {j},
m_ {j}) is a signature for m_ {j}. (ID
_ {1}, s_ {1}, m_ {1}), ..., (ID_
{J-1}, s_ {j-1}, m_ {j-1}), (I
D_ {j}, s_ {j}, r_ {j}, m_ {j}) as a signature for (m_ {1},..., M_ {j})
Send to the next user.

Step 3 Signature verification signature statement (ID_ {1}, s_ {1}, m_ {1}),
..., (ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}), Ri = g {(1 / s_ {i}) yi} (r_ {i} / s
_ {I}) (mod p), Ti = Ri / r_ {i} (mod n) r_ {i-1} = Ti / h1 (m_ {i} || IDi)
(Mod n) are sequentially obtained. Next, R1 = g {(1 / s_ {1}) y1} (r_ {1} / s
_ {1}), T1 = R1 / r_ {1} (mod n). Next, it is verified whether T1 = h1 (m_ {1} || ID_ {1}) holds. If so, consider the signature valid.

The first embodiment is an embodiment of the present invention. In the first embodiment, it is not necessary to fix the document to be signed in advance, and it is not necessary to specify the order of the signers in advance. Furthermore, at the time of verification, it is possible to verify who modified the document and where and in what order. As a result, it can be used in a variety of applications where multiple people sign.

In the first embodiment, each signer Ij applies a signature to his or her modified part m_ {j}.
This is, of course, M_ {1,. . , J} can be easily extended. As a result, it is possible to deal with the case where each signer performs only the signature without making any modifications. If no modification has been made, transmit as m_ {j} = NULL, and in each signature generation / verification phase, m_ {j}
{1,. . , J}.

In the first embodiment, as a message restoration type signature on a finite field, a message restoration type signature expression using a DSA signature expression, s = (xr + 1) / k (mod n), is used. Here, x is a user's secret key, and a random number k
, R = g ＾ k (mod p). However,
The realization of the multiple signature according to the present invention is not limited to this signature type. It can be realized by using any message restoration type signature formula based on DLP. Several variations of the message restoration type signature are described below. Of course,
It is also possible to use a message restoration type signature other than the one described. A. Miyaji, "Another countermeasurement
o forgeriesover messager
ecological signature ”, IEICE
Trans. , Fundamentals. vol.
E80-A, no. 11 (1997), 2192-2
200.

[0031]

As described above, in the conventional multiple signature, the document cannot be changed by the signer.
In addition, the method that cannot verify the signer's signature order at the time of verification or the method that can verify the signature order does not satisfy the flexibility for the order, such as specifying the signer's order in advance. For this reason, it is difficult for the signer to freely change the document, and it is difficult to verify the changed portion of the document, the person who changed the document, and the order in which the document flows at the time of verification without specifying the order in which the document flows. There was a problem.

The present invention has been made in view of the problems in the conventional example, and allows a signer to freely change a document, and to specify a document flow at the time of verification without previously specifying a flow order of the document. The purpose is to provide a multi-signature that can verify the location of change, the person who made the change, and the order in which the document flows. As a result, even in the situation of free software distribution using the Internet, in the situation where arbitrary users improve the software and distribute it,
It is possible to identify a malicious user while protecting the user's copyright, and its practical value is great.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a multiple signature generation device according to a first embodiment;

FIG. 2 is a configuration diagram of a multi-signature generation device according to a first conventional example;

Claims (8)

[Claims] (1) Ii is the i-th signer, the original document is M_ {1} = m_ {1}, and if it is necessary to specify the subscript i, it is expressed as _ {i}. Is a general term for all electronic data such as software, data, documents, etc.
{1, 2,. . . , I-1} is changed to M_
{1, 2,. . . , I}, and Ii is the received document M_
{1, 2,. . . , I-1}, m_ {i} = Diff (M_ {1,2, ..., i-
1}, M_ {1, 2,. . . , I}), that is, m_ {1} is M_ {1,
2,. . . , I−1} and M_ {1, 2,. . . , I}, and from the difference using the function Pat, the document is M_ {1, 2,. . . , I} = Pat (m_ {1}, m
_ {2}, ..., m_ {i}), and each signer Ii sets its ID to I
Di, a secret key sk_ {i}, and a public key pk_ {i},
The input of the message restoration type signature function sign is pk_
{I}, m_ {i}, and the output, that is, the signature is SIG_
Let SIG_ {i} be SIG_ {i} = (r_
{I}, s_ {i}), and r_ {i} is the signature SI
G_ {i} is a part that can be restored at the time of verification, s_ {i} is the remaining part of SIG_ {i}, and conversely, the input of the function rec for restoring the document from the signature is pk_ {i}, r_
{I}, s_ {i}, and as its output the document m_
{I} is restored, that is, sign (sk_ {i}, m_ {i}) = SIG_
｛I｝ = (r_ ｛i｝, s_ ｛i｝) rec (pk_ ｛i｝, (r_ ｛i｝, s_ ｛i｝))
= M_ {i}, h1 is a hash function that outputs the original input of an arbitrary bit length in the range of the domain of the signature generation function, and% and # are mutually Arbitrary operation having a reverse operation relationship (A% B) # B = A, and the signature generation step is such that the signer I1 checks whether the document M_
When digitally signing {1} = m_ {1},
SIG_ {1} = sign (sk_ {1}, h1 (m_
{1} || ID_ {1})) = (r_ {1}, s_
{ID}, (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, to the next user, and includes a signature (ID_ {1}, s_ {1}, m_ {1}),. (I
D_ {j-2}, s_ {j-2}, m_ {j-2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j-1}), the user IJ receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}), and a message restoration type signature sign is added to the obtained m_ {j} and r_ {j−1} of the received signature statement.
SIGj = sign (skj, r_ {j-1}% h1
(M_ {j} || ID_ {j})) = (r_ {j}, s
_ {J}), (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, m_ {1}), ..., (ID_ {j-1}, s_
{J-1}, m_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, m_ {j}), i = j,
, 2, Ti = rec (pk_ {i}, (r_ {i}, s_
{I})) r_ {i-1} = Ti # h1 (m_ {i} || IDi), and T1 = rec (pk_ {1}, (r_ {1}, s_
{1})), determining whether T1 = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. A multi-signature generating apparatus characterized in that a document can be changed and a document distribution order can be verified without making the order of users distributing documents fixed. 2. The message restoration type signature according to claim 1, wherein a finite field Fp (p is a prime number), a base point g∈F
p, its order ord (g) = n is a prime number, and each signer I
i is IDi of the ID and secret key xiｘZn * =
{1,. . , N−1}, and the public key is converted to yi = g ＾ x on Fp.
i and a step of obtaining a hash function that outputs to a Zn * with respect to an original input having an arbitrary bit length. The signature generation step is such that the signer I1 determines that the document M_ {1} = m_
When digitally signing {1}, random number k1 {Z
For n *, R1 = g {k1 (mod p), r_ {1} = R1 / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n), and (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, to the next user, and includes a signature (ID_ {1}, s_ {1}, m_ {1}),. (I
D_ {j-2}, s_ {j-2}, m_ {j-2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, for a random number kj {Zn *, Rj = g {kj (mod p) r_ {j} = Rj / ( h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (m
odn), and (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, m_ {1}), ..., (ID_ {j-1}, s_
{J-1}, m_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, m_ {j}), i = j,
, 2, Ri = g ＾ (1 / s_ ｛i｝) yi ＾ (r_ ｛i｝ / s
_ {I}) (mod p), Ti = Ri / r_ {i} (mod n) r_ {i-1} = Ti / h1 (m_ {i} || IDi)
(Mod n), R1 = g {(1 / s_ {1}) y1} (r_ {1} / s
_ {1}), T1 = R1 / r_ {1} (mod n), a step of determining whether T1 = h1 (m_ {1} || ID_ {1}), and a multiple signature based on the determination result. A multi-signature generating apparatus characterized in that the method comprises the steps of verifying a document, enabling a document change for each user, and verifying a document change and document distribution order without fixing the order of users who distribute the document. 3. The message restoration type signature according to claim 1, wherein an elliptic curve E / Fp on a finite field Fp (p: prime number), a base point G∈E (Fq), and its order ord (G) =
n is a prime number, and each signer Ii sets its ID to IDi and secret key xi∈Zn * = {1,. . , N−1}, and the public key is E
Above, the step of obtaining Yi = xiG, and h1 is a hash function for outputting to the Zn * with respect to the original input having an arbitrary bit length.
When digital signature is applied to _ {1} = m_ {1}, R1 = k1 on E / Fp for random number k1∈Zn *
G = (R1_x, R1_y); r_ {1} = R1_x / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
odn), and (ID_ {1}, s_ {1}, r
_ {1}, m_ {1}) as a signature for m_ {1}, to the next user, and includes a signature (ID_ {1}, s_ {1}, m_ {1}),. (I
D_ {j-2}, s_ {j-2}, m_ {j-2}),
(ID_ {j-1}, s_ {j-1}, r_ {j-
1}, m_ {j−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}) and a document M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, the E / F
determining Rj = kjG = (Rj_x, Rj_y) on p; r_ {j} = Rj_x / (h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (m
odn), and (ID_ {j}, s_ {j}, r
_ {J}, m_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, m_ {1}),.
(ID_ {j-1}, s_ {j-1}, m_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, m
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, m_ {1}), ..., (ID_ {j-1}, s_
{J-1}, m_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, m_ {j}), i = j,
.., 2 on the E / Fp, Ri = (1 / s_
{I}) G + (r_ {i} / s_ {i}) Yi = (Ri
_X, Ri_y), sequentially obtaining Ti = Ri_x / r_ {i} (mod n) r_ {i-1} = Ti / h1 (m_ {i} || IDi), and R1 on Fp. = (1 / s_
{1}) G + (r_ {1} / s_ {1}) Y1 = (R1
_X, R1_y), a step of determining T1 = R1_x / r_ {1}, a step of determining whether T1 = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. A multi-signature generating apparatus characterized in that a document change can be performed for each user, and the document change and the document distribution order can be verified without fixing the order of the users who distribute the documents. 4. A message restoration type signature according to claim 1, wherein a set of small prime numbers is {r_ {1} = {2, 3,
5,...}, Each signer Ii secretly generates its ID as IDi and two large t-bit primes p_i and q_i, and multiplies each element of {r_ {1} with n_ {i, 1｝ =
For p_ {i} q_ {i} r_ {1}, L_ {i,
1} = LCM ((p_ {i} −1), (q_ {i} −
1), (r_ {1} -1)) (the least common multiple) and e_
{I, 1}, d_ {i, 1 {1, 2,. . , N_
{I, 1} -1} is changed to e_ {i, 1} * d_ {i, 1} = 1 (mod L_
{I, 1}), and for each {r_ {1}, {n_ {i, 1}, e_ {i, 1} is the signer Ii's public key, and {d_ {i, Let 1｝｝ be the corresponding private key,
h1 is a hash function that outputs 2t bits to the original input having an arbitrary bit length. The signature generation step is performed when the signer I1 applies a digital signature to the document M_ {1} = m_ {1}. , N_ {1,1_ {1}> h1 (m
_ {1} || ID_ {1}) n_ {1, l_
For {1}, sgn_ {1} = h1 (m_ {1} |
| ID_ {1}) {(d_ {1,1_ {1}) (m
od n — {1, l — {1}), and (ID — {1}, sgn — {1}, l — {1}, m
_ {1}) as a signature for m_ {1}, and transmitting the signature to the next user.
{1}, l_ {1}, m_ {1}), ..., (ID_ {j
−2}, l_ {j−2}, m_ {j−2}), (ID_
{J-1}, sgn_ {j-1}, l_ {j-1}, m
_ {J−1}), the user Ij receives M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, n_ {j, l_ {j}> sgn_ {j-1} (+) h
1 (m_ {j} || ID_ {j}), where (+) is exclusive OR, and sgn_ {j} = (sgn_ {j-
1 {(+) h1 (m_ {j} || ID_ {j}))}
(D_ {j, l_ {j}) (mod n_ {j, l
_ {J}), and (ID_ {j},
l_ {j}, sgn. {J}, m_ {j}) to m_
{J} as a signature, and (ID_ {1}, sgn_
{1}, m_ {1}, ..., (ID_ {j-1}, sg
n_ {j-1}, m_ {j-1}), (ID_ {j},
sgn_ {j}, m_ {j}) to (m_ {1},..., m
_ {J}) as a signature to the next user. The signature verification step includes a signature sentence (I
D_ {1}, l_ {1}, m_ {1}), ..., (ID_
{J-1}, l_ {j-1}, m_ {j-1}), (I
D_ {j}, l_ {j}, sgn_ {j}, m_
{J}), T = sgn_ {i} e_ {i, l_ {i} (mod
n_ {i, l_ {i}) sgn_ {i-1} = T (+) h1 (m_ {i} || I
Di) and T = sgn_ {1} e_ {1,1_ {1} (mod
n_ {1, l_ {1}), determining whether T = h1 (m_ {1} || ID_ {1}), and verifying the multiple signature based on the determination result. A multi-signature generation apparatus characterized in that a document change can be performed for each document, and the document change and the document distribution order can be verified without fixing the order of users who distribute the documents. (5) Ii is the i-th signer, the original document is M_ {1} = m_ {1}, and if it is necessary to specify the subscript i, it is expressed as _ {i}. Is a general term for electronic data in general, such as software, data, and documents.
{1, 2,. . . , I-1} is changed to M_
{1, 2,. . . , I}, and Ii is the received document M_
{1, 2,. . . , I-1}, m_ {i} = Diff (M_ {1,2, ..., i-
1}, M_ {1, 2,. . . , I}), that is, m_ {i} is M_ {1,
2,. . . , I−1} and M_ {1, 2,. . . , I}, and M_ {1, 2,. . . , I} = Pat (m_ {1}, m
_ {2}, ..., m_ {i}), and each signer Ii sets its ID to I
Di, a secret key sk_ {i}, and a public key pk_ {i},
The input of the message restoration type signature function sign is pk_
{I}, m_ {i}, and the output, that is, the signature is SIG_
Let SIG_ {i} be SIG_ {i} = (r_
{I}, s_ {i}), and r_ {i} is the signature SI
G_ {i} is a part that can be restored at the time of verification, s_ {i} is the remaining part of SIG_ {i}, and conversely, the input of the function rec for restoring the document from the signature is pk_ {i}, r_
{I}, s_ {i}, and as its output the document m_
{I} is restored, that is, sign (sk_ {i}, m_ {i}) = SIG_
｛I｝ = (r_ ｛i｝, s_ ｛i｝) rec (pk_ ｛i｝, (r_ ｛i｝, s_ ｛i｝))
= M_ {i}, and the encryption function and the decryption function of the symmetric encryption are respectively
E (K, m) = c, D (K, c) = m, where m is a document, c is a ciphertext, K is a key for symmetric key encryption, and h1 is an input having an arbitrary bit length. A hash function to be output in the range of the domain of the signature generation function, h2 is a hash function to output the key length of the symmetric encryption for an arbitrary bit length input, and% and # are mutually Arbitrary operation (A% B) # B = A in the inverse operation relationship, and the signature generation step is as follows.
When digitally signing {1} = m_ {1},
Output by message restoration type signature sign, SIG_
{1} = sign (sk_ {1}, h1 (m_ {1} |
| ID_ {1})) = (r_ {1}, s_ {1}) and a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function ID_ {1} = E (K1, m_ {1} || ID_ {1}) output from the encryption function E of m_ {1} || ID_ {1} 1｝, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
{J-1}), the user Ij restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}), and the obtained m_ {j} is output by the message restoration type signature sign SIGj = sign (skj, r_ {j−1}% h1
(M_ {j} || ID_ {j})) = (r_ {j}, s_ {j}) and a session key Kj Kj = h2 (r_ {j-1}% used in the encryption function) h1 (m_ {j} || I
D_ {j}) and an output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E And (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1}, s_
{J-1}, c_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, c_ {j}), i = j,
, 2, Ti = rec (pk_ {i}, (r_ {i}, s_
{I})), Ki = h2 (Ti), m_ {i｝ ′ || IDi ′ = D (Ki, c_
{I}), and the step of determining IDi ′ = IDi, and verifying the signature based on the determination result. M_ {i} = m_ {i} ′, r_ {i−1} = Ti # h1 ( m_ {i} || IDi) is sequentially repeated, and T1 = rec (pk_ {1}, (r_ {1}, s_
{1})), K1 = h2 (T1), m_ {1} '|| ID_ {1}' = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. A multi-signature generation apparatus characterized in that a document can be changed and a document change and a document distribution order can be verified without fixing a document distribution user order. 6. The message restoration type signature according to claim 5, wherein a finite field Fp (p is a prime number), a base point g∈F
p, its order ord (g) = n is a prime number, and each signer I
i is a step of obtaining its ID as IDi, a secret key xi∈Zn, and a public key as yi = g ＾ xi on Fp, and h1 is Zn * = {1,. . ,
n-1}, and the signature generation step is as follows. When the signer I1 applies a digital signature to the document M_ {1} = m_ {1}, the signer I1 generates R1 = G {k1 (mod p), r_ {1} = R1 / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n), and a step of determining a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and a step of calculating m_ {1} || ID_ {1} Determining the output c_ {1} = E (K1, m_ {1} || ID_ {1}) by the encryption function E, and (ID_ {1}, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
{J-1}), the user Ij restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, for a random number kj {Zn *, Rj = g {kj (mod p) r_ {j} = Rj / ( h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj
(Modn), and a session key Kj Kj = h2 ((r_ {j-1} * h1 (m_ {j} ||) used in the encryption function.
Idj) (mod n)) and the output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E. Calculating step (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1}, s_
{J-1}, c_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, c_ {j}), i = j,
, 2, Ri = g ＾ (1 / s_ ｛i｝) yi ＾ (r_ ｛i｝ / s
_ {I}) (mod p), Ti = Ri / r_ {i} (mod n), Ki = h2 (Ti), m_ {i} '|| IDi' = D (Ki, c_
{I}), determining IDi ′ = IDi, verifying the signature based on the determination result, m_ {i} = m_ {i} ′, r_ {i−1} = Ti / h1 (m_ {i} || IDi)
(Mod n) are sequentially repeated, and R1 = g {(1 / s_ {1}) y1} (r_ {1} / s
_ {1}), T1 = R1 / r_ {1} (mod n) K1 = h2 (T1), m_ {1} '|| ID_ {1}' = D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. A multi-signature generating apparatus characterized in that a document can be changed and the document change and the document distribution order can be verified without fixing the order of users who distribute the document. 7. The message restoration type signature according to claim 5, wherein an elliptic curve E / Fp on a finite field Fp (p: prime number), a base point G∈E (Fq), and its order ord (G) =
n is a prime number, and each signer Ii obtains its ID as IDi, a secret key xi ， Zn, and obtains a public key as Yi = xiG on E, and h1 represents an original input having an arbitrary bit length.
Zn * = {1,. . , N−1}, and the signature generation step is as follows.
When digitally signing {1} = m_ {1},
For a random number k1∈EZ *, R1 = k1G =
(R1_x, R1_y); r_ {1} = R1_x / h1 (m_ {1} || ID_
{1}) (mod n), s_ {1} = (x1r_ {1} +1) / k1 (m
od n),, a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and m_ {1} || ID_ {1} To obtain the output c_ {1} = E (K1, m_ {1} || ID_ {1}) by the encryption function E, and (ID_ {1}, s_ {1}, r
_ {1}, c_ {1}) as a signature for m_ {1}, to the next user, and a signature (ID_
{1}, s_ {1}, c_ {1}), ..., (ID_ {j
-2}, s_ {j-2}, c_ {j-2}), (ID_
{J-1}, s_ {j-1}, r_ {j-1}, c_
The user Ij receiving {j-1}) restores m_ {1},..., M_ {j-1} from the verification step described below, and M_ {1, 2,. . . , J-1} = Pa
restoring a document by t (m_ {1}, m_ {2},..., m_ {j-1});
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, the E / F
determining Rj = kjG = (Rj_x, Rj_y) on p; r_ {j} = Rj_x / (h1 (m_ {j} || ID_
{J}) r_ {j-1}) (mod n), s_ {j} = (xjr_ {j} +1) / kj (m
odn), and a session key Kj Kj = h2 ((r_ {j-1} * h1 (m_ {j} ||) used in the encryption function.
Idj) (mod n)) and the output c_ {j} = E (Kj, m_ {j} || ID_ {j}) of m_ {j} || ID_ {j} by the encryption function E. Calculating step, (ID_ {j}, s_ {j}, r
_ {J}, c_ {j}) as a signature for m_ {j}, and (ID_ {1}, s_ {1}, c_ {1}),.
(ID_ {j-1}, s_ {j-1}, c_ {j-
1}), (ID_ {j}, s_ {j}, r_ {j}, c
_ {J}) as a signature for (m_ {1},..., M_ {j}) and communicating to the next user;
The signature verification step includes a signature sentence (ID_ {1}, s_
{1}, c_ {1}), ..., (ID_ {j-1}, s_
{J-1}, c_ {j-1}), (ID_ {j}, s_
{J}, r_ {j}, c_ {j}), i = j,
, 2, Ri = (1 / s_ {i}) G + (r_
{I} / s_ {i}) Yi = (Ri_x, Ri_y)
(Operation on E / Fp), Ti = Ri_x / r_ {i} (mod n) Ki = h2 (Ti), m_ {i} '|| IDi' = D (Ki, c_ {i}), Step, a step of judging IDi ′ = IDi, a step of verifying the signature based on the judgment result, m_ {i} = m_ {i} ′, r_ {i−1} = Ti / h1 (m_ {i} | | IDi)
(Mod n) are successively repeated, and R1 = (1 / s_
{1}) G + (r_ {1} / s_ {1}) Y1 = (R1
_X, R1_y) (operation on E / Fp), T1 = R1_x / r_ {1} (mod n), and K1 = h2 (T1), m_ {1} ′ || ID_ {1} '= D (K1, c_
{1}), a step of determining whether T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. A multi-signature generation apparatus characterized in that a document can be changed and a document change and a document distribution order can be verified without fixing a document distribution user order. 8. A message restoration type signature according to claim 5, wherein a set of small prime numbers is {r_ {1} = {2, 3,
5,...}, Each signer Ii secretly generates its ID as IDi and two large t-bit primes p_i and q_i, and multiplies each element of {r_ {1} with n_ {i, 1｝ =
For p_ {i} q_ {i} r_ {1}, L_ {i,
1} = LCM ((p_ {i} −1), (q_ {i} −
1), (r_ {1} -1)) (the least common multiple) and e_
{I, 1}, d_ {i, 1 {1, 2,. . , N_
{I, 1} -1} is changed to e_ {i, 1} * d_ {i, 1} = 1 (mod L_
{I, 1}), and for each {r_ {1}, {n_ {i, 1}, e_ {i, 1} is the signer Ii's public key, and {d_ {i, Let 1｝｝ be the corresponding private key,
h1 is a hash function that outputs a 2t-bit length with respect to the original input having an arbitrary bit length.
When the signer I1 applies a digital signature to the document M_ {1} = m_ {1}, n_ {1,1_ {1}> h1
N_ {1,1_ which becomes (m_ {1} || ID_ {1})
For {1}, sgn_ {1} = h1 (m_ {1} |
| ID_ {1}) {(d_ {1,1_ {1}) (m
od n — {1, 1 — {1}), a session key K1 K1 = h2 (h1 (m_ {1} || ID_ {1}) used in the encryption function, and m_ ｛ Determining the output c_ {1} = E (K1, m_ {1} || ID_ {1}) of 1 {|| ID_ {1} by the encryption function E, and (ID_ {1}, 1_ {1}) , S
gn_ {1}, c_ {1}) as a signature for m_ {1} to the next user;
D_ {1}, 1_ {1}, c_ {1}), ..., (ID_
{J-2}, 1_ {j-2}, c_ {j-2}), (I
D_ {j-1}, 1_ {j-1}, sgn_ {j}, c
_ {J-1}), a step of restoring m_ {1},..., M_ {j-1} from a verification step described below; . . , J−1} = Pat (m_
{1}, m_ {2},..., M_ {j−1}), and M_ {1,
2,. . . , J−1} to M_ {1, 2,. . . , J} and the difference m_ {j} = Diff (M_ {1, 2,..., J−
1}, M_ {1, 2,. . . , J}) and applying a digital signature to the obtained m_ {j}, n_ {j, 1_ {j}> sgn
_ {J-1} (+) h1 (m_ {j} || ID_
Here, (+) is an exclusive OR, and sgn_ {j} = (sgn
_ {J-1} (+) h1 (m_ {j} || ID_
{J})) {(d_ {j, 1_ {j}) (mod
n_ {j, 1_ {j}), and a session key Kj Kj = h2 (sgn_ {j-1} (+) h1 (m_
{J} || ID_ {j})) and the output of m_ {j} || ID_ {j} by the encryption function E c_ {j} = E (Kj, m_ {j} || ID_} j}), and (ID_ {j}, sgn_
Let {j}, l_ {j}, c_ {j}) be a signature for m_ {j} and (ID_ {1}, l_ {1}, c_
{1}), ..., (ID_ {j-1}, l_ {j-1},
c_ {j-1}), (ID_ {j}, l_ {j}, sg
n_ {j}, c_ {j}) to (m_ {1},..., m_
{J}) as a signature to the next user, and the signature verification step includes a signature (ID
_ {1}, l {1}, c_ {1}), ..., (ID_ {j
-1}, l_ {j-1}, c_ {j-1}, (ID_
{J}, l_ {j}, sgn_ {j}, c_ {j}), T = sgn_ {i} e_ {i, l_ {i} for i = j,... (Mod
n_ {i, l_ {i}) ki = h2 (Ti), m_ {i} '|| IDi' = D (ki, c_
{I}), determining IDi ′ = IDi, verifying the signature based on the determination result, m_ {i} = m_ {i} ′, sgn_ {i−1} = T ( +) H1 (m_ {i} || I
Di) are sequentially repeated, and T1 = sgn_ {1} e_ {1,1_ {1} (mo
dn_ {1, l_ {1}) K1 = h2 (T1), m_ {1} || ID_ {1} ′ = D (K1, c_
{1}),, T1 = h1 (m_ {1} '|| ID_ {1}'), and a step of verifying the multiple signature based on the determination result. A multi-signature generating apparatus characterized in that a document can be changed and the document change and the document distribution order can be verified without fixing the order of users who distribute the document.