JPH11231777A - Multiple digital signature method using elliptic curve, its apparatus and program recording medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] It is possible to improve the security than using the discrete logarithm problem on a finite field as the basis of security. SOLUTION: An element in a rational point group E (F (p ⁿ )) on an elliptic curve E defined on F (p ⁿ ) of a finite field F (p ⁿ ) (p: prime number, n: natural number). published by selecting the different elements G _1, G ₂ randomly from subgroup G _q number q, the signing device _{11 i (i = 1,2, ...} , N) is a secret key s _1i, s _2i
Are randomly selected from Z / qZ, and the user public key V _i = [− s _1i ] G ₁ + [− s _2i ] G ₂ is E
Calculated as an element of the above, and discloses the public key ^{_{V = Σ i = 1 N V}} i, r 1i from Z / qZ, a r _2i selected randomly, the user element _{X i = [r 1i] G} 1 + [ seeking r _2i] G ₂ as an element of the E, obtains the ^{_{X = Σ i = 1 N X}} i, e = h (X,
m), and y _1i = r _1i + es · s _1i mod q, y _2i = r
_1i + _es2s mod q is calculated, and y ₁ = (Σ _{i = 1} ^N y _1i )
mod q, y ₂ = (Σ _{i = 1} ^N y _2i ) mod q is obtained, and e, y
Let ₁ and y _{2 be} multiple signatures for m. X '= [y ₁ ]
G ₁ + [y ₂ ] G ₂ + [e] V is obtained as an element on E, and if e = h (X ′, m) holds, it is valid.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to information such as digitized documents and approvals as information security technology.
The present invention relates to a multiplex digital signature method, an apparatus, and a program recording medium for giving a digital signature / seal to a plurality of persons in duplicate on one document.

[0002]

2. Description of the Related Art As a prior art, a multisignature scheme proposed by Okamoto will be described. FIG. 5 shows the procedure of this signature method. Users participating in multiple signatures are N
And the i-th user is numbered and the system parameter p, q,
Generate g ₁ , g ₂ , and t. Here, p and q are prime numbers, and q is divisible by p-1. g ₁ and g ₂ are selected from the elements of the irreducible coset group (Z / pZ) ^* modulo p, and both indices are q.

[0003] User i uses Z / q as secret keys s _1i and s _2i.
Z (Z / qZ is an integer of {0, 1,..., Q−1}) is used to select a different element at random, and a public key ^vi = g ₁ ^-s1 _i g ₂
^-s2i mod Calculate p and publish v. Let h be a hash function and let the bit length of the output be t. In a multi-signature public key, the public key of all users is multiplied under mod p.
= (Π _{i = 1} ^N v _i ) mod p.

As a pre-calculation, the user i is a random number
r_1i, R_2i∈ Select Z / qZ, x = g₁ ^r1ig_Two ^r2imo
Calculate d p. One user collectively or
X = (Π_{i = 1} ^Nx (i)) Calculate mod p
To inform each user. As a signature generation, the user i
Partial signature for message m (e, y_1i, Y_2u) To
Is obtained by calculation. e = h (x, m) ∈Z / 2^tZ, y
_1i= R_1i+ E · s _1imod q, y_2i= R_2i+ E · s_2i mod
q collectively or multi-signature by each user in cooperation
(E, y₁, Y_Two) Is generated by the following equation.

Y ₁ = ( _{1 i = 1} ^N y _1i ) mod q, y _2i =
(Σ _{i = 1} ^N y _2i ) mod q The message m and its signature (e, y ₁ , y ₂ ) are sent to the verifier. The verifier verifies the signature as x ′ = g ₁ ^y1 g ₂
^y2 v ^e mod p is calculated, and h (x ', m) is further calculated. If the equation e = h (x', m) is satisfied, the signature is determined to be valid.

The multi-signature scheme by Okamoto is a scheme whose security has been proven. (Tatsuaki Okamoto, “Pr
ovably Secure and Practical Identification Scheme
andCorresponding Signature Schemes, Lecture Notes
in Computer Science, Volume 740, Advances in Cry
ptology: CRYPT'92) On the other hand, in recent years, in the field of public key cryptography, the main purpose is to improve the security of public key cryptography by replacing the discrete logarithm problem on a finite field with a discrete logarithm problem on an elliptic curve. Attempts have been made to build cryptographic algorithms.

The discrete logarithm problem on an elliptic curve is as follows. Now, let p be a prime number and n be a natural number,
A group consisting of F (p ⁿ ) rational points of an elliptic curve E defined on a finite field F (p ⁿ ) having the number of elements p ⁿ is represented by E (F (p (p
ⁿ )), the binary operation on E (F (p ⁿ )) is represented by the symbol +
G + which is obtained by adding x elements G of E (F (p ⁿ ))
Let G + ... + G (x) be written as [x] G.

At this time, the discrete logarithm problem on the elliptic curve is
For elements P and Q of group E (F (p ⁿ )) on the elliptic curve, P
= [N] It is a problem to find n when there is an integer n that satisfies Q. For elliptic curves and groups on elliptic curves, see JHS Silverman's "The Arithmetic of El
liptic Curves ", GTM106, Springer-Verlag New
See York 1986.

Okamoto's multiple signature scheme uses the discrete logarithm problem over a finite field as the basis for security, but replaces Okamoto's multiple signature scheme with a multiple signature scheme that uses the discrete logarithm problem over an elliptic curve as the basis for security. No proposal was made.

[0010]

With the increase in computing power of computers and the discovery of algorithms for solving discrete logarithm problems on finite fields, it has become necessary to base more difficult problems on improving security. SUMMARY OF THE INVENTION An object of the present invention is to provide a multi-signature method, a device and a program recording medium which use the discrete logarithm problem for a group on an elliptic curve, which is a more difficult problem, as a basis for security, in order to solve the problems of the conventional method. It is.

[0011]

In the multi-signature method according to claim 2 in order to achieve the above object, according to an aspect of, the prime p, where n is a natural number, the finite field is a number of elements p ⁿ F (p
ⁿ ) A group composed of F (p ⁿ ) rational points of the elliptic curve E defined above is defined as E (F (p ⁿ )), and E (F (p ⁿ ))
Write binary operation above the symbol +, write inverse element G of E (F (p ⁿ⁾⁾ by the symbol -G, element G of E (F (p ⁿ⁾⁾
G + G +... + G (x) obtained by adding x are written as [x] G, and for the negative integer x, the inverse element -G of the element G of E (F (p ⁿ )) is added by -x. (-G) + (-G) + ... +
Assuming that (−G) (−x) is written as [x] G, the group E (F
In (p ⁿ )), a subgroup in which the number of elements is a prime number q is G _q , and two elements G ₁ and G ₂ having different sub groups G _q are selected, and (p ⁿ , E, q, G ₁₎ , G ₂ ) as public parameters, N users participating in the multiple signature are numbered and numbered, the i-th user i is a user i, and for each user i, a group element on an elliptic curve X
_{With i} and integers as input variables, for a ^t such that 2 ^t -1 is less than or equal to q, let h be a one-way function that outputs elements of {0, 1, ..., 2 ^t -1}, In an environment where the N signing devices and the verification device perform signature communication, the signing device i of each user i secretly and randomly _writes two different elements s _1i and s _2i as Z / q.
Select from Z, elements V _i of the group of the elliptic curve E using these
_{= [- s 1i] G 1} + [- s 2i] to calculate the G _2.

Element V for all users i_iOn the elliptic curve E
The public key V = Ｖ_{i = 1} ^NV_iAnd each signature
The position i is secretly and randomly two different elements r_1i, R_2iTo
Z / qZ, and use these to calculate the group of elliptic curves E
Element X_i= [R_1i] G₁+ [R_2i] G_TwoCalculate the user
User variable element X for all users i_iAdd
In addition, the variable element X = Σ_{i = 1} ^NX_iAnd the one-way function
The operation e = h (X, m) is executed, and these s_1i, S_2i,
e, r_1i, R_2iUsing y_1i= R_1i+ E · s_1i modq,
y_2i= R_2i+ E · s_2i Calculate modq and calculate
Signature (e, y_1i, Y_2i), And one user puts together
Or each user cooperates₁= (Σ
_{i = 1} ^Ny_1i) Mod q, y_Two= (Σ_{i = 1} ^Ny _2i) Mod q
Is calculated and this multiple signature (e, y₁, Y_Two) To the verification device
In the verification device, the signature (e, y₁ , Y_Two ) And published above
Parameter G₁, G_Two, The elements of the group on the elliptic curve
X '= [y₁ ] G₁ + [Y_Two ] G_Two Calculate + [e] V
And input X 'and m which is the numerical value of the message
Calculate the directional function h and satisfy the verification equation e = h (X ', m)
Check whether the signature is satisfied if the expression is satisfied
If the expression is not satisfied, the verification fails.

[0013]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiment 1 FIG. 1 shows a processing procedure of Embodiment 1 of the signature method of the present invention.
FIG. 2 shows the functional configuration of the signature device, and FIG. 3 shows the functional configuration of the verification device. N users participate in the multiple signature,
Each user is numbered, i th user writes a user i, the signature device used by the user i referred to as 11 _i. When constructing a system parameter generation system, a finite field F satisfying the following properties
Choose (p ⁿ ) and the elliptic curve E defined on its finite field.

The order of the subgroup _Gq of the group defined above the elliptic curve E is large, for example, a prime number of about 160 bits. -Two elements of the above subgroup can be selected at random. Here, the prime number which is the order of the subgroup _Gq is set to q. Next, different elements G ₁ and G ₂ of the subgroup _Gq are randomly selected.

The above (GF (p ⁿ ), E, q, G ₁ , G
₂ ) Publish as public parameters. Further, the elements of the group on the elliptic curve and integers are input as {0, 1, ..., 2 ^t −
Let h be a one-way hash function that outputs 1｝ elements. These public parameters GF (p ⁿ ) or p ⁿ , E,
In general, q, G ₁ , and G ₂ are generated by the center device 10 as shown in FIG. 5A, and each signature device 11 ₁ is transmitted via a communication line.
To 11 _N and received by each receiving unit 41 (FIG. 2).
It is stored in the memory 12 (FIG. 2). The secret key / public key generation user i secretly and randomly converts two different elements s _1i and s _2i into Z / qZ, that is, {0, 1,..., Q, by the secret key generation unit 14 in the signature device 11 _i . Choose from integers of -1｝. For example, a random number is generated from a random number generator, and if the random number is one element of Z / qZ, it is output to obtain two different s _1i and s _2i . These elements s _1i ,
elements V _i of the group of s _2i and public elements G _1, G ₂ elliptic curve E with a is calculated by the public key generation unit 15 by the following equation.

[0016] _{V i = [- s 1i]} G 1 + [- s 2i] G 2 (1) user i has issued a V _i as a user public key, (s _1i,
s _2i ) is secretly held in the memory 12 as a secret key. All user public key V _i to generate a public key V corresponding to the sum in group operation of the elliptic curve by the following equation.

[0017] ^{_{V = Σ i = 1 N V}} (i) (2) summing the user public key V _i is the center device and the user public key V _i from the signature device 11 _i as shown in FIG. 4A 10 To the public key V. Alternatively, as shown in FIG. 4B, one of the signature device 11 _i, for example, the signature apparatus 11 _N to feed the user public key V ₁ ~V _N-1 other signing devices 11 ₁ to 11 _N-1, the signature adding together all the user public key V _i in apparatus 11 _N may generate a public key V. Alternatively, as shown in FIG. 4C, for example, the signature device 1
1 sent ₁ of the user public key V ₁ to the next of the signature device 11 _2,
The signature device 11 _2, by adding the user's public key V ₂ of V ₁ and self sends a V ₁ + V ₂ to the next of the signature device 11 _3, here to make a _{V 1 + V 2 + V 3} , following the signature device 11 feed to _4, added together sequentially in the same manner, at the final signing devices 11 _N may be obtained the public key V.

In this case, as shown by a broken line in FIG. 2, V ₁ +... + V _i-1 from the preceding signature device 11 _i-1 received by the reception unit 41 is added to the V _{i by the} addition unit 42. Is transmitted from the transmission unit 21 to the next signature device 11 _{i + 1} . It is assumed that the message to be subjected to the pre-computation signature is digitized and represented by an integer m and stored in the memory 12. Here, the signature device 11 _i of the user i who is the signer is the auxiliary variable generation unit 16.
_Gives two randomly different elements r _1i , r
_2i is selected from Z / qZ. The elements r _1i and r _2i may be obtained in the same manner as the generation of the secret keys s _1i and s _2i . These r _1i , r _2i and the public elements G ₁ , G ₂ are input to the variable operation unit 17, and the element X _i of the group of the elliptic curve E is calculated by the following equation.

X_i= [R_1i] G₁ + [R_2i] G_Two (3) User variable element X that is the result of this calculation_iIs available to all users
Variable element X, which is an element of the elliptic curve E
Is obtained by the following equation. X = Σ_{i = 1} ^NX_i (4) This user variable element X_iOf the user public key V
_i4A, B, and C.
The obtained variable element X is stored in each signature device 11 _iReturned to
And stored in the memory 12.Signature generation The variable element X and the message m are sent to the hash function operation unit 18
The following equation is calculated by inputting.

E = h (X, m) The hash function operation result e and auxiliary variables r _1i , r _2i ,
The secret keys s _1i and s _2i are input to the remainder operation unit 19 and the following equation is calculated. _y1i = _r1i + _esi2modq (5) _y2i = _r2i + _es2imodq (6) Let (e, _y1i , _y2i ) be a partial signature for m.

Elements y of these partial signatures_1i, Y_2iIs all you
An addition operation modulo q is performed on the₁= (Σ_{i = 1} ^Ny_1i) Mod q (7) y_Two= (Σ_{i = 1} ^Ny_2i) Mod q (8) is obtained. (E, y₁, Y_Two) Is a multiple signature for m
Is sent to the verification device 31 together with m. Partial signature required
Element y_1i, Y_2iAddition described for FIGS. 4A, 4B and 4C.
V_i, X_iIs performed by any of the additions of Therefore
m and e, y₁, Y _TwoIs the case when the method of FIG. 4A is used.
Sent to the verification device 31 from the
If used, one collected signature device 11_NVerified from
4C, and in the case of the method of FIG.
Signature device 11_NWill be sent to the verification device 31
You.Signature verification In the verification device 31 (FIG. 3),
Public element G from the data device 10₁ , G_Two And also as mentioned above
The public key V obtained is stored in the receiving unit 33
And m and its multiple signature (e, y₁ , Y_Two ) As described above
When received, G₁ , G_Two , V, and receiving
The trusted multi-signature is input and the following equation
The group element X 'is calculated.

X ′ = [y ₁ ] G ₁ + [y ₂ ] G ₂ + [e] V (9) The calculation result X ′ and the message m are input into the hash function operation unit 35, and the following equation is obtained. Is calculated. e ′ = h (X ′, m) This operation result e ′ is compared with the received e by the comparing section 36, and it is checked whether e ′ = e.

If the multiple signature is created successfully
Substituting equations (1) to (8) into equation (9) gives
Become. X '= [y₁] G₁+ [Y_Two] G_Two+ [E] V = [Σ_{i = 1} ^Ny_1i] G₁+ [Σ_{i = 1} ^Ny_2i] G_Two+ [E] (Σ_{i = 1} ^NV_i) = Σ_{i = 1} ^N([Y_1i] G₁ + [Y_2i] G_Two + [E] V_i) = Σ_{i = 1} ^N([R_1i+ E · s_1i] G₁ + [R_2i+ E · s_2i] G_Two + [E] ([-s_1i] G₁ + [-S_2i] G_Two)) = Σ_{i = 1} ^N([R_1i+ E · s_1i+ E · (-s_1i)] G₁ + [R_2i+ E · s_2i+ E · (-s_2i)] G_Two) = Σ_{i = 1} ^N[R_1i] G₁ + [R_2i] G_Two = Σ_{i = 1} ^NX_i= X That is, X '= X, and h (X', m) = e '= e,
Output from the comparing unit 36 that the multiple signature is correct.
If e ′ = e, the multiple signature (e, y₁ , Y _Two )
Is determined to be incorrect and output.

In the method shown in FIG. 4A, the center device 10
Since it is assumed that the secret key is held, e = h (X,
m) is performed by the center device 10, and e is set to each signature device.
11 _iMay be sent to Signature device 11_i, Verification device 31
Is generally a control unit mainly composed of a microprocessor, etc.
23 and 37 are provided, respectively, to sequentially control each means.
And reading from and writing to memory.

[0025]

As described above, according to the present invention, the security can be improved more than before by changing the basis of security from a discrete logarithm problem of a finite field to a discrete logarithm problem on an elliptic curve. Was.

[Brief description of the drawings]

FIG. 1 is a diagram showing an operation procedure of a multiple signature method using an elliptic curve according to the present invention.

FIG. 2 is a block diagram showing a functional configuration of an embodiment of the multiple signature device of the present invention.

FIG. 3 is a block diagram showing a functional configuration of a verification device used for implementing the method of the present invention.

FIG. 4 is a block diagram showing various examples of a method of generating a system parameter, V from each V _i , and X from each X _i .

FIG. 5 is a diagram showing an operation procedure of a conventional digital multiple signature method on a finite field by Okamoto.

Claims (7)

[Claims] 1. A plurality of users i (i = 1, 2,..., N)
Finite field F but a method of multiplexing digital signature the same message at the signing device i, prime p, the n is a natural number, a number of elements p ⁿ
The F (p ⁿ⁾ the group consisting of rational points (p ⁿ⁾ on a defined elliptic curve E and ^{E (F (p n))} , the group E (F (p
ⁿ )), G ₁ , G ₂ and E (F (p ⁿ )) or p
ⁿ and E are publicized, and the signature device i publishes the private keys s _1i and s _2i and the public elements G ₁ and G
A user public key seeking elements V _i of the group of the elliptic curve E with _{2, = 0} public key V = sigma _i of multisignature all user public key V _i by adding on an elliptic curve E ^N V _i Each signature device i randomly obtains the user element X _i of the group of the elliptic curve E, and adds X _{i of} all the users i on the elliptic curve E to obtain an element X = Σ
_{i = 1} ^N and X _i, element X and performs function operation as inputs and digitized message m, the signature device i as a result the function calculating e and a secret key s _1i, s _2i
When obtains the partial signature element y _1i, y _2i by using the information used in determining the user element X _i, y ₁ by adding the partial signature element y _1i of all users, y _2i respectively, y ₂ Then, y ₁ , y ₂ and e are sent to the verification device as a multi-signature for m, and the verification device uses the received multi-signatures y ₁ , y ₂ and e and the public elements G ₁ and G ₂ to generate an elliptic curve E An ellipse characterized in that a function operation is performed using the elements X 'and m as inputs and the operation result is compared with e, and if they match, it is determined that the multiple signature is correct. Multiple digital signature method using curves. 2. E (F (p (pⁿ)) The above binary operation is represented by the symbol +
And write E (F (p ⁿ)) The inverse of element G with the symbol -G
Write, E (F (pⁿG + G obtained by adding x elements G of))
+ ... + G (x) is written as [x] G, and for a negative integer x
And E (F (pⁿ)) -X operations on the inverse -G of element G
(−G) + (− G) +... + (− G) (−x)
[X] G, the group E (F (pⁿ)) And the number of elements is prime
Let G be a subgroup of the number q _qAs a subgroup G_qTwo different
Public element G₁ , G_Two As pⁿ,
q is also disclosed, and the above function operation is an operation of the one-way function h.^t-1
{0, 1,..., 2 for t such that^t
-1}, and outputs the secret key s_1i, S_2iAs two different randomly
The elements are represented by Z / qZ (Z / qZ is {0, 1,..., Q-1}
Integer), and the above user public key V_iAnd V_i= [-S_1i] G₁ + [-
s_2i] G_Two And two different elements are secretly and randomly generated by each signature device i.
r_1i, R_2iIs selected from Z / qZ, and the user is
Element X_i= [R_1i] G₁ + [R_2i] G_Two , And the function operation result, e = h (X, m), and the element
r_1i, R_2iAnd secret key s_1i, S_2iAnd the partial signature using
Element y_1i= R_1i+ E · s_1i modq, y_2i= R_2i+ E · s
_2i modq and calculate all the above partial signature elements y_1i, Y_2iWith q modulo
And add the above multi-signature element y₁= (Σ_{i = 1} ^Ny_1i)
mod q, y_Two= (Σ_{i = 1} ^Ny_2i) Mod q is obtained, and the above element X ′ in the verification device is expressed as X ′ = [y₁ ] G₁ + [Y
_Two ] G_Two + [E] V, and the verification equation e = h
Check whether (X ', m) is satisfied.
2. A digital signature using an elliptic curve according to claim 1.
Name method. 3. A signature device for performing multiple digital signatures on the same message by a plurality of signature devices, wherein the public element G ₁ , which is a rational point on an elliptic curve defined by a secret key and a finite field, G ₂ and the private key s _1i, a memory for storing s _2i, the secret key s _1i, and the private key generating means for generating a s _2i, the secret key s _1i, s _2i and the public elements G _1, G ₂ enter the door, and the public key generating means for generating a user public key V _i is an element of rational points on the elliptic curve, an auxiliary variable generation unit for generating auxiliary variables r _1i, the r _2i randomly, the Variable operation means for inputting the auxiliary variables r _1i , r _2i and the public elements G ₁ , G ₂ to generate a user variable element X _i which is an element of a rational point on the elliptic curve; and all user variable elements X _i Is added as a variable on the above elliptic curve and the message m is entered as a variable. Is a function operation means for performing a function calculation, the calculation result e of the function operation unit, the auxiliary variable r _1i,
r _2i, the secret key s _1i, s _2i is inputted partial signature element y _1i, a signature element calculation means for calculating the y _2i, and the user public key V _i, and the user variable element X _i,
Transmitting means for outputting the operation result e of the function operation means and the partial signature elements y _1i and y _{2i of} all users to the outside; receiving means for receiving the variable element X from the outside; A signature device comprising: a control unit that controls and performs reading and writing on the memory. 4. The elliptic curve E is defined on a finite field F (p ⁿ ) having p ⁿ elements, where p is a prime number and n is a natural number, and the rational point is a group E (F (p ⁿ ) ) Is composed,
The addition of x elements G on E (F (p ⁿ )) is represented by [x] G, and two additions different from the subgroup G _q in which the number of elements in the group E (F (p ⁿ )) is a prime number q. The elements G ₁ and G ₂ are selected as the public elements, and the secret key generation means uses Z / qZ (Z / qZ is {0, 1,
.., Q−1}) to generate two different integers s _1i , s _2i at random, and the public key generation means V _i = [− s _1i ] G ₁ + [−
s _2i] to calculate the G ₂ is a means to the user public key V _i, the auxiliary variable selection means is means for generating two different integers r _1i, r _2i random from Z / qZ, the The variable operation means is X _i = [r _1i ] G ₁ + [r _2i ] G ₂
The calculated a means to the user variable element X _i, the function calculating means is means for calculating the one-way function h (X, m) = e , the signature element calculation unit y _1i = r _1i + _{es 1s} mod q,
_4. The signature apparatus according to claim 3, wherein _y2i = _r2i + _es2s mod q is calculated to obtain the partial signature elements _y1i and _y2i . 5. The receiving means sends all preceding user public keys V _{1 to} V _i-1 , all preceding user variable elements X _{1 to} X _i-1 , and all preceding partial signatures from the preceding signature device. Element y
_{1i ~y 1i-1, y 2i} ~y 2i-1 is also a means for receiving, by adding V _i from V ₁ ~V _i-1 and the public key generating unit thus received, X ₁ ~ thus received X _i−1 and X _i from the variable operation means are added, and the received y _1i to y _1i-1 and y _{2i to} y are received.
_2i-1 and addition means for adding y _1i and y _2i from the remainder operation means, respectively, and means for transmitting each addition result in the addition means from the transmission means to the next signature device by the transmission means. 5. The method according to claim 3, wherein
A signature device as described. 6. A plurality of users i (i = 1, 2,..., N)
Is a secret key generation process of generating secret keys s _1i and s _2i by a signature device of a user i performing digital multiple signature on the same message m, and a rational point on an elliptic curve defined by a finite field. public elements G _1, G ₂ and the secret key s _1i, and the public key generation process of generating a user public key V _i is an element of rational points on the elliptic curve using s _2i, auxiliary variables r _1i, r An auxiliary variable generation process of randomly generating _2i , and generating a user variable element X _i that is an element of a rational point on the elliptic curve using the auxiliary variables r _1i and r _2i and the public elements G ₁ and G _2. A variable calculation process, a variable request X obtained by adding all user variable elements X _i on the elliptic curve and a message m are input as variables and a function calculation is performed, and a calculation result of the function calculation process e and the above auxiliary variables r _1i ,
r _2i , a signature element operation process of _operating partial signature elements y _1i , y _2i using the secret keys s _1i , s _2i , an operation result e of the function operation, and the partial signature elements y _1i , y
A computer-readable recording medium storing a program for executing a transmitting step of outputting _2i to the outside and a receiving step of receiving the variable element X from the outside. 7. The elliptic curve E has p as a prime number and n as its own.
Naturally, the number of elements pⁿFinite field F (pⁿ) Fixed on
And the rational point group E (F (pⁿ)) Is constructed and E
(F (pⁿ)) X addition of the above element G is represented by [x] G
And group E (F (pⁿPart where the number of elements in)) is a prime number q
Group G_qTwo elements G different from₁ , G _Two Is the above public element
And the secret key generation process is Z / qZ (Z / qZ is {0, 1,
..., an integer of q-1})
s_1i, S_2iAnd the above public key generation process_i= [-S_1i] G₁ + [-
s_2i] G_Two The above-mentioned auxiliary variable selection process is a process of calculating two random numbers from Z / qZ.
Different integer r_1i, R_2iAnd the above variable operation process is X_i= [R_1i] G₁ + [R_2i] G_Two 
The function operation process described above performs a one-way function h (X, m) = e.
Where the signature element operation process is y_1i= R_1i+ E · s_1i modq,
y_2i= R_2i+ E · s_2iBe a process of calculating mod q
The recording medium according to claim 6, wherein: