WO2006057171A1 - 署名および検証方法ならびに署名および検証装置 - Google Patents

署名および検証方法ならびに署名および検証装置 Download PDF

Info

Publication number
WO2006057171A1
WO2006057171A1 PCT/JP2005/020729 JP2005020729W WO2006057171A1 WO 2006057171 A1 WO2006057171 A1 WO 2006057171A1 JP 2005020729 W JP2005020729 W JP 2005020729W WO 2006057171 A1 WO2006057171 A1 WO 2006057171A1
Authority
WO
WIPO (PCT)
Prior art keywords
signature
storage medium
calculation
necessary data
calculation result
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2005/020729
Other languages
English (en)
French (fr)
Inventor
Isamu Teranishi
Kazue Sako
Daigo Taguchi
Jun Noda
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Priority to JP2006547724A priority Critical patent/JP4848957B2/ja
Priority to EP05806273A priority patent/EP1819090B1/en
Priority to US11/719,798 priority patent/US20090044017A1/en
Publication of WO2006057171A1 publication Critical patent/WO2006057171A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/12—Applying verification of the received information
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/12—Applying verification of the received information
    • H04L63/123—Applying verification of the received information received data contents, e.g. message integrity
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
    • H04L9/3249—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using RSA or related signature schemes, e.g. Rabin scheme

Definitions

  • the present invention relates to a signature and verification method and a signature and verification device, and particularly in a situation where a plurality of signature devices sign, the signature length and the verification method and the signature and verification are independent of the number of signature devices. Relates to the device.
  • Non-Patent Document 1 A signature method described in Non-Patent Document 1 has been proposed as one of signature methods for solving such problems.
  • Figure 11 shows the procedure of this conventional signature method.
  • T_ ⁇ m ⁇ is calculated by concatenating the public key of the self-signed device and the public key of the signature device that has already signed (S3F103).
  • S3F104 the exclusive OR of the hash value of T_ ⁇ m ⁇ and the signature sentence u_ ⁇ i_ ⁇ m_l ⁇ is calculated (S3F104).
  • the first security parameter k bits in the bit string of U is a, and the rest is s (S3F105).
  • a is compared with the RSA modulus n_ ⁇ i_ ⁇ m ⁇ of the self-signed device (S3F106) , A is smaller than the RSA modulus n_ ⁇ i_ ⁇ m ⁇ ! /,
  • the signature key u_ ⁇ i_ ⁇ m ⁇ is applied to a with the private key d_ ⁇ i_ ⁇ m ⁇ according to the RSA method Calculate (S3F107) and output (S3F109).
  • 1-bit information 0 is added to s as control information.
  • n_ ⁇ i_ ⁇ m ⁇ when a has a large RSA modulus n_ ⁇ i_ ⁇ m ⁇ , it is larger than the modulus, and RSA signatures cannot be calculated for numbers, so a is subtracted by n_ ⁇ i_ ⁇ m ⁇
  • a signature sentence u_ ⁇ i_ ⁇ m ⁇ is calculated for the object (S3F108) and output (S3F109). In this case, 1-bit information 1 is added to s as control information.
  • the signature cannot be calculated for a number larger than the RSA modulus n_ ⁇ i_ ⁇ m ⁇ of the signing device. Subtract by modular n_ ⁇ i_ ⁇ m ⁇ and sign the force. At this time, in order to enable later verification, add lbit control information (1 if the modulus is exceeded, 0 if not). When verifying the signature sentence u_ ⁇ i_ ⁇ m ⁇ , repeat the verification using the public key of the signature device in the reverse order of the signature order, and finally reach the point where a predetermined initial value is obtained. Since it can be verified retrospectively, it is determined that the signature is correct.
  • the signature length is a fixed value + the number of signatures, and there is a problem that the signature length increases little by little as the number of signatures increases.
  • An object of the present invention is to improve the above-described problems of the conventional signature scheme and make the signature length constant regardless of the number of signature devices.
  • the signing method according to claim 1 has an initial value or a signature sentence created by sequentially performing a signing operation by a plurality of other signing devices, a message, and a private key of the self-signing device as inputs,
  • a signature method in a signature device that outputs a signature sentence having the same length as an input, wherein the signature apparatus that was involved in the creation of the output signature sentence is input to each signature apparatus Indicates that the message has been signed
  • the signing method according to claim 2 is the signing method according to claim 1, wherein the operation of calculating a signature sentence has two steps, the first step and the first step ( ⁇ -1 ⁇ Operation) is calculated using the inverse function of unidirectional replacement with trap doors, and the second step 0 ⁇ -1 ⁇ operation) is calculated in the first step.
  • the first step and the first step ( ⁇ -1 ⁇ Operation) is calculated using the inverse function of unidirectional replacement with trap doors
  • the second step 0 ⁇ -1 ⁇ operation) is calculated in the first step.
  • the signing method according to claim 3 is the signing method according to claim 2, wherein in the first step, the input to the first step is an element of a range of the one-way replacement with the trapdoor. If so, the input is mapped with the inverse function of the one-way replacement with the trapdoor, otherwise nothing is done, and the input to the second step is The input is mapped by the inverse function of the unidirectional replacement with the trapdoor if it is an element of the range of the directional replacement, and nothing is performed otherwise.
  • the signing method according to claim 4 is the signing method according to claim 3, wherein the calculation of the one-way replacement with a trapdoor used in the second step is further performed by a first substep and a second substep.
  • the first sub-step operation of ⁇ -1 ⁇
  • the bijection in the space of the entire signature sentence is calculated, and the bijection can be calculated in polynomial time.
  • the inverse function of bijection can also be calculated in polynomial time.
  • the second substep operation of the part of g ll
  • the inverse function of unidirectional replacement with a trapdoor is used.
  • the input is mapped by the inverse function of the unidirectional replacement with the trapdoor if it is an element of the range of the directional replacement, and nothing is performed otherwise. 2
  • the required data at the start of the substep The storage medium And reading a calculation result into the storage medium at the end of the first sub-step and the second sub-step.
  • the signing method according to claim 5 is the signing method according to claim 4, wherein the one-way replacement with the trap door used in the first step and the second sub-step of the second step.
  • the one-way replacement with trap door used in the above is an RSA function.
  • Multiply ⁇ m ⁇ mod 2 ⁇ , n_ ⁇ i_ ⁇ m ⁇ is the RSA modulus that is part of the public key of the signing device i_ ⁇ m ⁇ , and ⁇ is the security 'parameter.
  • the signature method according to claim 10 is the signature method according to claim 9, characterized in that there is a signature sentence verification step for verifying an input signature sentence before the first step. .
  • the signing method according to claim 11 is the signing method according to claim 8, wherein, prior to the first step, pk_ ⁇ i_ ⁇ l ⁇ , ..., pk_ ⁇ i_ ⁇ m-1 ⁇ ⁇ Is characterized by a key validity verification step that confirms that all of ⁇ are different, and a signature verification step that verifies the input signature.
  • the signing method according to claim 12 is the signing method according to any one of claims 1 to 11, wherein the initial value of the input or the signature text or their no and sh values are used as auxiliary information. And writing to the storage medium, and outputting the auxiliary information and the signature sentence as a set.
  • the input means uses an initial value or a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing a signature operation with a plurality of other signature devices, and those signature devices.
  • Input the message ⁇ _ ⁇ 1 ⁇ , ⁇ , M_ ⁇ m-1 ⁇ and store it in the storage medium, T_ ⁇ m ⁇ calculation means are required from the storage medium and the public key storage device Pk_ ⁇ i_ ⁇ j ⁇ is the public key of the signature device i_ ⁇ j ⁇ and II is the concatenation of bit strings, T_ ⁇ m ⁇ M_ ⁇ l ⁇
  • the exclusive OR calculation means includes H as a hash function and ⁇ as an exclusive OR.
  • a step of reading necessary data from the storage medium, calculating U H (T_ ⁇ m ⁇ ) 0 u_ ⁇ i_ ⁇ ml ⁇ , and storing the calculation result in the storage medium, first conversion means Is necessary from the storage medium.
  • N_ ⁇ i_ ⁇ m ⁇ is the RSA modulus of the self-signed device
  • the bijection transformation means reads the necessary data from the storage medium and secures ⁇ .
  • V ′ v + n_ ⁇ i_ ⁇ m ⁇ mod 2 ⁇ , and storing the calculation result in the storage medium, and the second conversion means uses the necessary data from the storage medium.
  • the verification method according to claim 15 is created by a plurality of signature devices sequentially performing signature operations.
  • the signature passes the verification that the signature signature u is involved in the creation of the output signature signature. Only when and when a device signs the message input to each signature device, the bit length of the signature text U depends on the number of signature devices involved in calculating the signature text U However, it is characterized by being a constant.
  • the verification method according to claim 16 is the verification method in the verification device that verifies whether the signature sentence u created by performing the signature operation in order by a plurality of signature devices is valid. This is only when and when the signing device that created the signature sentence u created the signature sentence u in a legitimate manner, and the bit length of the signature sentence u was involved in calculating the signature sentence u. It is a constant that does not depend on the number of signature devices, and the verification of the signature sentence u is performed using auxiliary information w that is data before the last one of the plurality of signature devices performs a signature operation. It is characterized by performing.
  • the verification method according to claim 17 is the verification method according to claim 15 or 16, wherein the operation for verifying a signature sentence has two steps, the first step and the first step.
  • the calculation of (operation of h part) uses unidirectional replacement with trap doors, and the calculation of the second step (operation of part f) is the same or different from that of the first step.
  • the necessary data is read from the storage medium, and when the first step and the second step are finished, the calculation is performed on the storage medium. It is characterized by writing the result.
  • the verification method according to claim 18 is the verification method according to claim 17, wherein, in the first step, the input to the first step is defined as the one-way replacement with the trap door. If it is an element of the area, the input is mapped by the one-way replacement with the trap door, otherwise nothing is done, and if the input to the second step is the one-way replacement with the trap door The input is mapped by the one-way permutation with the trap door if it is in the domain of the definition, otherwise nothing is done.
  • the verification method according to claim 19 is the same as the verification method according to claim 18, wherein the calculation of the one-way replacement with a trap door used in the first step is further performed by the first and second methods.
  • the trapped Map the input with the one-way replacement function with the trapdoor if it is within the range of the one-way replacement with the trapdoor, otherwise what In the second substep (operation of ⁇ part), the bijection in the space of the entire signature sentence is calculated, and the bijection can be calculated in polynomial time.
  • the bijective inverse function can also be calculated in polynomial time.
  • the verification method according to claim 20 is the verification method according to claim 19, wherein the one-way replacement with the trap door used in the first sub-step of the first step;
  • the one-way replacement with trap door used in the second step is an RSA function.
  • T_ ⁇ j ⁇ M_ ⁇ 1 ⁇
  • the verification method according to claim 27 is the verification method according to claim 21, wherein the first step is preceded by a T_ ⁇ m-1 ⁇ calculation step and a V "calculation step.
  • the input means includes a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing a signature operation by one or more other signature devices, and the signature devices Enter the message ⁇ _ ⁇ 1 ⁇ , ..., M_ ⁇ m-1 ⁇ and the public key pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pk_ ⁇ i_ ⁇ ml ⁇ of those signing devices
  • T_ ⁇ j ⁇ M_ ⁇ 1 river...
  • pk_ ⁇ i_ ⁇ j ⁇ is calculated, and the calculation result is stored in the storage medium.
  • a storing step, wherein the u calculation means reads necessary data from the storage medium, calculates u_ ⁇ i_ ⁇ jl ⁇ H (T_ ⁇ j ⁇ ) ⁇ U, and stores the calculation result in the storage medium
  • the input means is a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing a signature operation by one or more other signature devices, and the previous signature device inputs Signed text or auxiliary information that is the hash value v_ ⁇ i_ ⁇ ml ⁇ , message M_ ⁇ 1 ⁇ , M_ ⁇ m-1 ⁇ , those signature devices input to those signature devices.
  • the public key pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pk_ ⁇ i_ ⁇ ml ⁇ is input and stored in the storage medium, and T_ ⁇ m-1 ⁇ calculating means stores the necessary data from the storage medium.
  • T_ ⁇ m-1 ⁇ M_ ⁇ 1 ⁇
  • the signature device includes a readable / writable storage medium, an initial value or a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing a signature operation with a plurality of other signature devices, and The message ⁇ _ ⁇ 1 ⁇ , ⁇ , M_ ⁇ m-1 ⁇ input to the signature device is input and stored in the storage medium, and it is necessary from the storage medium and the public key storage device.
  • T_ ⁇ m ⁇ ⁇ _ ⁇ 1 ⁇
  • pk_ ⁇ i_ ⁇ m ⁇ is calculated
  • H is a hash function
  • O an exclusive OR
  • the necessary data is read from the storage medium
  • U H (T_ ⁇ m ⁇ ) 0 u_ ⁇ i_ ⁇ ml ⁇ is calculated, and the calculation result is stored in the storage medium
  • the verification device includes a readable / writable recording medium and a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing signature operations on one or more other signature devices, and , M_ ⁇ 1 ⁇ , M_ ⁇ m-1 ⁇ , and the public key pk_ ⁇ i_ ⁇ l ⁇ of these signing devices, pk_ ⁇ i_ ⁇ m-1 Input means to input »and save it to the storage medium, and j initialization means to set variable j to m-1 And the necessary data is read from the storage medium.
  • v ′ u_ ⁇ i_ ⁇ j ⁇ is calculated, and the second conversion means for saving the calculation result to the storage medium and the necessary data read from the storage medium are read.
  • the first conversion means to be stored and the step by the second conversion means, the bijection calculation means, and the first conversion means are repeated each time the variable j is decreased by 1 until the variable j force SO is reached.
  • T_ ⁇ j ⁇ M_ ⁇ i ⁇
  • pk_ ⁇ i_ ⁇ j ⁇ is calculated and T_ ⁇ j ⁇ calculating means for storing the calculation result in the storage medium;
  • Read necessary data from the storage medium, calculate u_ ⁇ i_ ⁇ jl ⁇ H (T_ ⁇ j ⁇ ) 0 U, and store the calculation result in the storage medium.
  • the verification device is a readable / writable recording medium and a signature sentence u_ ⁇ i_ ⁇ ml ⁇ created by sequentially performing a signature operation on one or more other signature devices, and the previous signature.
  • Ancillary information v_ ⁇ i_ ⁇ ml ⁇ that is the signature text input by the device or its hash value, M_ ⁇ 1 ⁇ , M_ ⁇ m-1 ⁇ , messages input to those signing devices
  • ⁇ m-1 ⁇ M_ ⁇ 1 river...
  • pk_ ⁇ i_ ⁇ m-1 ⁇ is calculated and the result is stored in the storage medium
  • T_ ⁇ m-1 ⁇ calculating means that reads necessary data from the storage medium, calculates v " H (T_ ⁇ ml ⁇ ) 0 U _ ⁇ i_ ⁇ ml ⁇ , and outputs the calculation result to the storage medium
  • the program according to claim 34 is a signature sentence u_ ⁇ i_ ⁇ ml ⁇ generated by performing a signature operation on a computer having an initial value or a plurality of other signature devices in sequence, using a computer having a readable / writable storage medium.
  • a program according to claim 36 includes a signature sentence u_ ⁇ i_ ⁇ ml ⁇ , which is a computer having a readable / writable recording medium and is created by sequentially performing a signature operation by one or more other signature devices.
  • T_ ⁇ j ⁇ M_ ⁇ 1 ⁇
  • U calculation means for reading necessary data from the storage medium, calculating u_ ⁇ i_ ⁇ j -l ⁇ H (T_ ⁇ j ⁇ ) U and storing the calculation result in the storage medium; and the storage medium
  • the necessary data is read from u, u is determined to determine whether it is a predetermined initial value, u judgment means, and if u is a predetermined initial value, a notification indicating a successful verification is output. Otherwise, it functions as an output means for outputting a notification indicating verification failure.
  • a program according to claim 37 includes a signature sentence u_ ⁇ i_ ⁇ ml ⁇ , which is a computer having a readable / writable recording medium and is created by sequentially performing a signature operation by one or more other signature devices.
  • T_ ⁇ m-1 ⁇ calculating means for calculating and storing the calculation result in the storage medium, and the storage medium Read necessary data from the body, calculate v " H (T_ ⁇ ml ⁇ ) ⁇ U _ ⁇ i_ ⁇ ml ⁇ , and store the calculation result in the storage medium V" calculation means
  • the signature device i_ ⁇ m ⁇ if the input signature sentence u_ ⁇ i_ ⁇ ml ⁇ exceeds the modulus n_ ⁇ i_ ⁇ m ⁇ , nothing is done. Is a first operation that performs a signature in accordance with the RSA signature, a second operation that creates a function that maps the result of the first operation to a larger value by the modulus n_ ⁇ i_ ⁇ m ⁇ , and this second operation. 2 If the result of the operation exceeds the modulus n_ ⁇ i_ ⁇ m ⁇ , do nothing, and if not, perform the third operation to sign according to the RSA signature.
  • the signature sentence u_ ⁇ i_ ⁇ ml ⁇ that takes a value from 0 to n_ ⁇ i_ ⁇ m ⁇ is signed according to the RSA signature, so the value after the first operation is 0 to n_
  • the signature sentence u_ ⁇ i_ ⁇ m-1 ⁇ that takes the value of n_ ⁇ i_ ⁇ m ⁇ to 2 ⁇ does nothing, so the first The value after the operation is n_ ⁇ i_ ⁇ m ⁇ to ⁇ .
  • the value after the first operation is also added by n_ ⁇ i_ ⁇ m ⁇ with a modulus of 2 ⁇ , so the value after the second operation is also a small number of 2 ⁇ ,
  • the value after the first operation is n_ ⁇ i_ ⁇ m ⁇ to 2 ⁇ becomes 0 to n_ ⁇ i_ ⁇ m ⁇ after the second operation. Therefore, in the third operation, a signature that conforms to the RSA signature is applied to those that have the value power ⁇ to n_ ⁇ i_ ⁇ m ⁇ after the second operation.
  • the RSA signature is performed at least once for the signature text u_ ⁇ i_ ⁇ ml ⁇ of any value.
  • the signature value u_ ⁇ i_ Since the value after the third operation, that is, the value of the signature value u_ ⁇ i_ ⁇ m ⁇ and the value of the input signature sentence u_ ⁇ i_ ⁇ ml ⁇ has a one-to-one correspondence, the signature value u_ ⁇ i_ Since the applied signature operation can be uniquely determined from the value of ⁇ m ⁇ , there is no need to add a control bit as in Non-Patent Document 1.
  • the first effect is that the signature length does not depend on the number of signature devices. The reason is that the number of bits of data before signing and data after signing is unchanged.
  • a second effect is that the order of signature devices can be changed for each signature.
  • the reason for this is the same as in the case of the first effect.
  • the number of bits of data before signing and the data that can be created after signing is unchanged. For this reason, the input to each signing device is constant regardless of the number of signing by the signing device, and therefore, it is possible to sign by the same operation regardless of the number.
  • the third effect is that the attacker who collaborates with the signature device cannot forge the signature text that passes through the honest signature device in the middle of the path.
  • the reason is that even if the input u to the signing device is something, u is the force that changes at least one of the RSA calculations performed at the maximum twice.
  • the fourth effect is that the number of signing devices m need not be strong at the beginning of system operation.
  • the number of signing devices m can be applied without any problem even if it changes dynamically during operation. is there .
  • the reason is that the signing procedure when the number of signing devices is m + 1 is that the same signing operation is performed once after the signing procedure when the number of signing devices is m. This is because the signature operation method does not depend on the number of signature devices m!
  • FIG. 1 is a block diagram of a first exemplary embodiment of the present invention.
  • FIG. 2 is a block diagram showing a configuration of a signature device according to the first embodiment of the present invention.
  • FIG. 3 is a flowchart showing the operation of the signature device in the first exemplary embodiment of the present invention.
  • FIG. 4 is a block diagram showing a configuration of a verification apparatus according to the first embodiment of the present invention.
  • FIG. 5 is a flowchart showing the operation of the verification apparatus in the first embodiment of the present invention.
  • FIG. 6 is a block diagram of a second embodiment of the present invention.
  • FIG. 7 is a block diagram showing a configuration of a signature apparatus according to a second embodiment of the present invention.
  • FIG. 8 is a flowchart showing the operation of the signature device in the second exemplary embodiment of the present invention.
  • FIG. 9 is a block diagram showing a configuration of a verification apparatus according to a second embodiment of the present invention.
  • FIG. 10 is a flowchart showing the operation of the verification apparatus in the second embodiment of the present invention.
  • FIG. 11 is a flowchart showing the operation of a conventional signature device.
  • the first embodiment of the present invention shows that a signature device i_ ⁇ l ⁇ ,... ⁇ M ⁇ , a verification device i — ⁇ 1 ⁇ -2,. , Public key storage device i— ⁇ 1 ⁇ -3, ⁇ , ⁇ — ⁇ m ⁇ -3, key validity verification device i— ⁇ 1 ⁇ -4, ⁇ , ⁇ — ⁇ m ⁇ -4, Private key storage device i— ⁇ 1 ⁇ -5,..., I— ⁇ m ⁇ -5.
  • signature apparatus i_ ⁇ m ⁇ includes input means S1B100, T_ ⁇ m ⁇ calculation means S1B103, exclusive OR calculation means S1B104, first conversion means S1B105, bijection conversion means S1B106 The second conversion unit S1B107, the storage medium S1B108, and the output unit S1B109.
  • Other signature devices have the same configuration as the signature device i_ ⁇ m ⁇ .
  • the verification device i_ ⁇ m ⁇ -2 includes input means V1B100, j initialization means V1B102, j determination means V1B103, second conversion means V1B104, bijection conversion means V1B105, first Conversion means V 1B106, T_ ⁇ j ⁇ calculation means V1B107, u calculation means V1B108, j reduction means V1B109, storage medium VI B1010, u determination means V1B1011, accept output means V1B1012 and reject output means V1B1013.
  • Other verification apparatuses have the same configuration as the verification apparatus i_ ⁇ m ⁇ -2. An outline of the present embodiment will be described.
  • the public key / private key pair of signature apparatus i_ ⁇ l ⁇ , initial value u_ ⁇ i_ ⁇ 0 ⁇ , and message M_ ⁇ 1 ⁇ are input to signature apparatus i_ ⁇ l ⁇ .
  • the signature device i_ ⁇ l ⁇ creates a signature sentence u_ ⁇ i_ ⁇ l ⁇ for the message M_ ⁇ 1 ⁇ using u_ ⁇ i_ ⁇ 0 ⁇ .
  • the signature device i_ ⁇ j ⁇ receives the public key private key pair of the signature device i_ ⁇ j ⁇ , the signature sentence u_ ⁇ i_ ⁇ jl ⁇ output by the immediately preceding signature device, and the message M_ ⁇ j ⁇ in order, The signature device i_ ⁇ j ⁇ uses these to create a signature sentence u_ ⁇ i_ ⁇ j ⁇ .
  • the signature sentence u_ ⁇ i_ ⁇ j ⁇ is signed by the signing device i_ ⁇ l ⁇ signing the message M_ ⁇ 1 ⁇ and the signing device i_ ⁇ 2 ⁇ signing the message M_ ⁇ 2 ⁇ This data indicates that i_ ⁇ j ⁇ has signed the message M_ ⁇ j ⁇ .
  • the verification device i_ ⁇ j ⁇ has the signature device i_ ⁇ l ⁇ , ⁇ , i_ ⁇ j ⁇ 's public key and message M_ ⁇ 1 ⁇ , ⁇ , M_ ⁇ j-1 ⁇ , And a signature sentence u_ ⁇ i_ ⁇ jl ⁇ . Then, the verification device i_ ⁇ j ⁇ has a signature sentence u_ ⁇ i_ ⁇ jl ⁇ for the message M_ ⁇ 1 ⁇ , ⁇ , M_ ⁇ jl ⁇ , and the signature device i_ ⁇ l ⁇ , ⁇ , i_ ⁇ jl ⁇ It is verified whether the signature is created using the private key.
  • the goal of the system of this embodiment is that the signature sentence u_ ⁇ i_ ⁇ m ⁇ , that is, the signature device i_ ⁇ l ⁇ signs the message M_ ⁇ 1 ⁇ and the signature device i_ ⁇ 2 ⁇ M_ ⁇ 2 ⁇ sign this ... to create data that signing device i_ ⁇ m ⁇ signed the message M_ ⁇ m ⁇ .
  • the number m of signature devices does not need to be as high as when the operation of the system of the present embodiment is started.
  • the number m of signature devices may change dynamically during operation.
  • the operations of the signature devices i_ ⁇ l ⁇ ,, i_ ⁇ m ⁇ are all the same.
  • the verification device, public key storage device, key validity verification device, and secret key storage device all basically perform the same operation.
  • the public key pk_ ⁇ i ⁇ and secret key sk_ ⁇ i ⁇ of the signing device i_ ⁇ j ⁇ are (n_ ⁇ i ⁇ , e_ ⁇ i ⁇ ), (p_ ⁇ i_ ⁇ j ⁇ , q_ ⁇ i_ ⁇ j ⁇ , d_ ⁇ i_ ⁇ j ⁇ ), which satisfies the following five properties.
  • n_ ⁇ i_ ⁇ j ⁇ P_ ⁇ i_ ⁇ j ⁇ q_ ⁇ i_ ⁇ j ⁇
  • n_ ⁇ i_ ⁇ j ⁇ is equal to the security parameter ⁇ .
  • d_ ⁇ i_ ⁇ j ⁇ e_ ⁇ i_ ⁇ j ⁇ -1 mod ⁇ ( ⁇ _ ⁇ )
  • ⁇ ( ⁇ _ ⁇ ) is the number of integers between 1 and less than n_ ⁇ i ⁇ and prime to n_ ⁇ i ⁇ .
  • Non-Patent Document 2 “Alfred J. Menezes Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC, describes how to create (pk_ ⁇ i ⁇ , (sk_ ⁇ i ⁇ ) that satisfies these properties. Pr ess. "(Http://www.cacr.math.uwaterloo.ca/hac/).
  • the secret key storage device i_ ⁇ j ⁇ -5 stores the secret key sk_ ⁇ i_ ⁇ j ⁇
  • the public key storage device i_ ⁇ j ⁇ -3 , Pk_ ⁇ l ⁇ ,..., Pk_ ⁇ m ⁇ are stored.
  • M_ ⁇ m ⁇ The operation of the signature device i_ ⁇ m ⁇ will be described.
  • M_ ⁇ m-1 ⁇ is a signature sentence U _ ⁇ i_ ⁇ m-1 ⁇
  • the method of signing the message M_ ⁇ m ⁇ by the signing device i_ ⁇ m ⁇ when input to m ⁇ will be described with reference to FIGS.
  • the signing device i_ ⁇ m ⁇ includes u_ ⁇ i_ ⁇ m-1 ⁇ , M_ ⁇ 1 ⁇ , ⁇ , M_ ⁇ m-1 ⁇ , pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pkjijm-1 ⁇ is sent to the verification device i_ ⁇ m ⁇ -2.
  • the verification device i_ ⁇ m ⁇ -2 verifies the validity of the signature text u_ ⁇ i_ ⁇ m_l ⁇ ( S1 B101, SlF102) o
  • the verification device i_ ⁇ m ⁇ - 2 is, pkjijl ⁇ , - , pkjijm-1 ⁇ to the key validity verification device i_ ⁇ m ⁇ -4.
  • T_ ⁇ m ⁇ calculation means S1B103 writes T_ ⁇ m ⁇ to storage medium S1B108 when the calculation is completed
  • H is a hash function that outputs a hash value having the same number of bits as the input.
  • the signature device i_ ⁇ m ⁇ reads the data input to the signature device i_ ⁇ m ⁇ from the storage medium S1B108 by the first conversion unit S1B105.
  • the signature device i_ ⁇ m ⁇ reads u_ ⁇ i_ ⁇ m ⁇ from the storage medium S1B108 and outputs it by the output means S1B109 (S1F1012).
  • the signature device i_ ⁇ m ⁇ has the input signature sentence u_ ⁇ i_ ⁇ m-1 ⁇ exceeding the modulus n_ ⁇ i_ ⁇ m ⁇ . If it does not exceed, do nothing, and if not, perform the first operation to sign according to the RSA method, and the modulus n_ ⁇ i_ ⁇ m ⁇ Is larger, and the second operation is applied to the function that maps to the direction, and whether the result of this second operation exceeds the modulus n_ ⁇ i_ ⁇ m ⁇ is determined. If not, the third operation for signing according to the RSA method is performed. Depending on the value of the signature text u_ ⁇ i_ ⁇ ml ⁇ , the RSA signature strength may be implemented. Since the signature operation performed can be uniquely determined by the value of the signature value u_ ⁇ i_ ⁇ m ⁇ , there is no need to add a control bit as in Non-Patent Document 1.
  • the verification device i_ ⁇ m ⁇ -2 is first input from the public key storage device i_ ⁇ m ⁇ -3 to pk_ ⁇ i_ ⁇ 1 ⁇ , ..., pk_ ⁇ i_ ⁇ m-1 ⁇ by the input means V1B100. ⁇ , And then the message M_ ⁇ 1 ⁇ , ..., M_ ⁇ m-1 ⁇ is read (V1F10 0). The read data is written to the storage medium V1B1010 by the input means V1B100.
  • the verification device i_ ⁇ m ⁇ -2 sends pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pk_ ⁇ i_ ⁇ ml ⁇ to the key verification device i_ ⁇ m ⁇ -4 by the input means V1B100.
  • V1B101, VlF101 public key
  • the verification device i_ ⁇ m ⁇ -2 first performs a verification process in order from the previous signature device to the first signature device, in order to perform which verification device i1 ⁇ m ⁇ -2 Set m-1 to the variable j that manages whether the signature in is verified (V1F102).
  • the verification device i_ ⁇ m ⁇ -2 determines whether j> 0 by using the j determination unit V1B103 (V1F103)
  • the verification device i_ ⁇ m ⁇ -2 first reads necessary data from the storage medium V1B1010 by the second conversion means V1B104, and checks whether u_ ⁇ i_ ⁇ j ⁇ Kn_ ⁇ i_ ⁇ j ⁇ Is determined (V1F104).
  • the verification device i_ ⁇ m ⁇ -2 reads necessary data from the storage medium V1B1010 by the first conversion means V1B106, and first determines whether V_n_ ⁇ i_ ⁇ j ⁇ ( V1F108).
  • V is n_ ⁇ i_ ⁇ j ⁇
  • the verification device i_ ⁇ m ⁇ -2 uses the first conversion means V1B106 to
  • V1B1010 V1F109
  • the verification device i_ ⁇ m ⁇ -2 again determines whether j> 0 by the j determination unit V1B103 (VI F103).
  • the verification apparatus i_ ⁇ m ⁇ -2 performs the processing after step V1F104.
  • the verification device i_ ⁇ m ⁇ -2 uses the u determination means V1B1011 to store the storage medium V1B101.
  • the verification device i_ ⁇ m ⁇ -2 outputs an accept indicating verification success by the accept output means V1B1012 (V1F1015), otherwise, by the reject output means V1B1013
  • reject indicating validation failure is output (V1F1016).
  • the operations surrounded by the dotted line in Fig. 5 are x), g (x), h (x), and ⁇ ( ⁇ ).
  • g (x) x e_ ⁇ i_ ⁇ j ⁇ mod n_ ⁇ i_ ⁇ j ⁇ if x n— ⁇ i— ⁇ j ⁇
  • ⁇ (x) x + n_ ⁇ i_ ⁇ j ⁇ mod 2 ⁇
  • the signature device i_ ⁇ m ⁇ in the present embodiment is The signature text is created by the following formula: ⁇ -l ⁇ (f_ ⁇ mF ⁇ -l ⁇ (H (T_ ⁇ m ⁇ ) ⁇ u_ ⁇ i_ ⁇ ml ⁇ ) >>).
  • the first effect is that the signature length does not depend on the number of signature devices. The reason is that the number of bits of data before signing and data after signing is unchanged.
  • the second effect is that the order of the signature devices can be changed for each signature.
  • the reason is the same as in the case of the first effect, because the number of bits of data before signing and data created after signing is unchanged. For this reason, the input to each signing device is constant regardless of the order of signing by the signing device, and for this reason, the signing can be performed by the same operation. However, it is necessary to notify the verification device in some form of the order in which the signatures were made.
  • the third effect is that an attacker who collaborates with a signature device uses an honest signature device along the way.
  • the signature text that passes is not forged.
  • the reason is that, regardless of what is input to the signing device, u changes at least in one of the RSA calculations performed twice during signing.
  • the fourth effect is that the number m of signature devices that need to be strong at the beginning of system operation can be applied without any problem even if the number of signature devices changes dynamically during operation. is there .
  • the reason is that the signing procedure when the number of signing devices is m + 1 is that the same signing operation is performed once after the signing procedure when the number of signing devices is m. This is because the signature operation method does not depend on the number of signature devices m!
  • the RSA function which is the most typical example, has been described. More generally, there exists a subset X with ⁇ , ⁇ ⁇ . If the condition (1) 2) is satisfied, as in the first embodiment, the signature length does not depend on the number of signers, and a secure signature scheme can be realized.
  • f and g are one-way replacements with trapdoors, and X is included in both f and g domains.
  • Both ⁇ force ⁇ and ⁇ 1 ⁇ can be calculated in polynomial time and must be bijective on ⁇ , ⁇ ⁇ , which maps ⁇ 0, 1 ⁇ " ⁇ ⁇ ⁇ to X .
  • unidirectional replacement with trapdoor is a function that satisfies the following four properties.
  • the signature device i_ ⁇ l ⁇ ,... ⁇ M ⁇ the verification device i — ⁇ 1 ⁇ -2,. , Public key storage device i— ⁇ 1 ⁇ -3, ⁇ , ⁇ — ⁇ m ⁇ -3, key validity verification device i— ⁇ 1 ⁇ -4, ⁇ , ⁇ — ⁇ m ⁇ -4, Private key storage device i— ⁇ 1 ⁇ -5,..., I— ⁇ m ⁇ -5.
  • signature apparatus i_ ⁇ m ⁇ includes input means S1B100, T_ ⁇ m ⁇ calculation means S1B103, exclusive OR calculation means S1B104, first conversion means S1B105, bijection conversion means S1B106 , Second conversion means S1B107, storage medium S1B108, output means S1B109, and w setting means S2B100.
  • Other signature devices have the same configuration as the signature device i_ ⁇ m ⁇ .
  • the verification device i_ ⁇ m ⁇ -2 includes input means V2B200, T_ ⁇ m-1 ⁇ calculating means V2B202, V "calculating means V2B203, second converting means V2B204, bijective converting means. V2B205, first conversion means V2B206, u judgment means V2B207, accept output means V2B208, reject output means V2B209 and storage medium V2B2010
  • Other verification devices have the same configuration as the verification device i_ ⁇ m ⁇ -2. .
  • the public key / private key pair of signature apparatus i_ ⁇ l ⁇ , initial value u_ ⁇ i_ ⁇ 0 ⁇ , and message M_ ⁇ 1 ⁇ are input to signature apparatus i_ ⁇ l ⁇ .
  • the signature device i_ ⁇ l ⁇ creates a signature sentence u_ ⁇ i_ ⁇ l ⁇ for the message M_ ⁇ 1 ⁇ using u_ ⁇ i_ ⁇ 0 ⁇ and sets the initial value u_ ⁇ i_ ⁇ 0 ⁇ as auxiliary information Create as w_ ⁇ i_ ⁇ l ⁇ and output a set of u_ ⁇ i_ ⁇ l ⁇ and w_ ⁇ i_ ⁇ l ⁇ .
  • the signature device i_ ⁇ 2 ⁇ is input with the public key private key pair of the signature device i_ ⁇ 2 ⁇ , the pair u_ ⁇ i_ ⁇ l ⁇ and w_ ⁇ i_ ⁇ l ⁇ , and the message M_ ⁇ 2 ⁇ Is done.
  • the signature device i_ ⁇ 2 ⁇ uses u_ ⁇ i_ ⁇ l ⁇ as V, creates a signature sentence u_ ⁇ i_ ⁇ 2 ⁇ for the message M_ ⁇ 2 ⁇ , and uses u_ ⁇ i_ ⁇ l ⁇ as auxiliary information Create as w_ ⁇ i_ ⁇ 2 ⁇ and output a set of u_ ⁇ i_ ⁇ 2 ⁇ and w_ ⁇ i_ ⁇ 2 ⁇ .
  • the signature device i_ ⁇ j ⁇ is followed by the public key private key pair of the signature device i_ ⁇ j ⁇ , the signature sentence u_ ⁇ i_ ⁇ jl ⁇ and the auxiliary information w_ ⁇ i_ ⁇ jl ⁇ output by the immediately preceding signature device. And the message M_ ⁇ j ⁇ are input, and the signature device i_ ⁇ j ⁇ uses these to create a pair of the signature text u_ ⁇ i_ ⁇ j ⁇ and auxiliary information w_ ⁇ i_ ⁇ j ⁇ .
  • u_ ⁇ i_ ⁇ j ⁇ is a signature sentence similar to that of the first embodiment, in which the signature device i_ ⁇ l ⁇ signs the message M_ ⁇ 1 ⁇ and the signature device ⁇ 2 ⁇ receives the message M_ ⁇ 2 This is data indicating that it is signed and signed to the signing device i_ ⁇ j ⁇ force message M_ ⁇ j ⁇ .
  • w_ ⁇ i_ ⁇ j ⁇ is auxiliary information for easily verifying the signature sentence u_ ⁇ i_ ⁇ j ⁇ .
  • the signature device i_ ⁇ This is the signature sentence u_ ⁇ i_ ⁇ jl ⁇ itself that was input to j ⁇ .
  • a verification device and ⁇ j ⁇ have a signature device ⁇ _ ⁇ 1 ⁇ , ⁇ , public key and message ⁇ _ ⁇ 1 ⁇ , ⁇ ,
  • the verification device i_ ⁇ j ⁇ becomes u_ ⁇ i_ ⁇ j- 1 ⁇ Is a signature sentence created using the public key of the signature device i_ ⁇ l ⁇ , ..., i_ ⁇ jl ⁇ for the message M_ ⁇ 1 ⁇ , ..., M_ ⁇ jl ⁇
  • Verification is made using auxiliary information W _ ⁇ i_ ⁇ j-1 ⁇ .
  • the goal of the system of this embodiment is to sign the same signature sentence u_ ⁇ i_ ⁇ m ⁇ , that is, the signature device i_ ⁇ l ⁇ cassette M_ ⁇ 1 ⁇ as in the first embodiment. Then, the signature device i_ ⁇ 2 ⁇ signs the message M_ ⁇ 2 ⁇ and creates data indicating that the signature device i_ ⁇ m ⁇ has signed the message M_ ⁇ m ⁇ .
  • the number m of signature devices does not need to be as large as that in the system of the present embodiment when the operation is started.
  • the number m of signing devices may change dynamically during operation.
  • the operations of the signature devices i_ ⁇ l ⁇ , i_ ⁇ m ⁇ are all the same.
  • the verification device, public key storage device, key validity verification device, and secret key storage device all basically perform the same operation.
  • the storage device i_ ⁇ j ⁇ -5 stores the secret key sk_ ⁇ i_ ⁇ j ⁇
  • the public key storage device i_ ⁇ j ⁇ -3 stores the public key pk_ ⁇ l ⁇ ,..., Pk_ ⁇ m ⁇ Is memorized.
  • Messages M_ ⁇ 1 ⁇ , ⁇ , M_ ⁇ m ⁇ , and signature devices i_ ⁇ l ⁇ , ⁇ ⁇ , i_ ⁇ m-1 ⁇ are public keys pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , p k_ ⁇ i_ ⁇ ml ⁇ and the signature text u_ ⁇ i_ ⁇ ml ⁇ and auxiliary information w_ ⁇ i_ ⁇ m- for message M_ ⁇ 1 ⁇ , ⁇ , M_ ⁇ m-1 ⁇ 1 ⁇ is input to the signing device i_ ⁇ m ⁇ , the signing device i_ ⁇ m ⁇ signs the message M_ ⁇ m ⁇ because it adds a procedure to create auxiliary information.
  • the signature device i_ ⁇ m ⁇ performs w_ ⁇ i_ ⁇ m ⁇ by the w setting means S2B100 following the processing of step S1F102.
  • ⁇ u_ ⁇ i_ ⁇ ml ⁇ is calculated, and the calculation result is written to the storage medium S1B108 (S2F100).
  • the auxiliary information w_ ⁇ i_ ⁇ m ⁇ written in the recording medium S1B108 is created by the output unit S1B109 in the same procedure as in the first embodiment and written in the recording medium S1B108 u_ ⁇ Read with i_ ⁇ m ⁇ and output (S1F1012 ') [0119]
  • a method in which the verification apparatus i_ ⁇ m ⁇ -2 verifies the signature sentence u_ ⁇ ml ⁇ will be described with reference to FIG. 9 and FIG.
  • the verification device i_ ⁇ m ⁇ -2 first reads pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pk_ ⁇ i_ ⁇ ml ⁇ from the public key storage device i_ ⁇ m ⁇ -3 by the input means V2B200, In addition, messages ⁇ _ ⁇ 1 ⁇ , ⁇ M_ ⁇ m-1 ⁇ are read and stored in the storage medium V2B2010 (V2F200).
  • the verification device i_ ⁇ m ⁇ -2 sends pk_ ⁇ i_ ⁇ l ⁇ , ⁇ , pk_ ⁇ i_ ⁇ ml ⁇ to the key verification device i_ ⁇ m ⁇ -4 by the input means V2B200.
  • V2F201 public key
  • pk_ ⁇ i_ ⁇ m-1 ⁇ is calculated, and T_ ⁇ m-1 ⁇ of the calculation result is stored in the storage medium V2B2010 (V2F202).
  • the first effect is that the signature length does not depend on the number of signature devices.
  • the reason is that the number of bits of data before signing and data after signing is unchanged.
  • the data length is increased by the amount of auxiliary information.
  • the second effect is that it is possible to reduce the amount of calculation required for the verification calculation as compared with the first embodiment.
  • the reason is that in the first embodiment, since it is necessary to finally obtain an initial value, a verification calculation proportional to the number of signature devices that have already signed is required. This is because the signature text that has been input to the signature device is transmitted as auxiliary information, so verification calculations for one signature device need only be performed.
  • this embodiment requires the premise that the previous signing device can be trusted, and therefore is less secure than the first embodiment that can prove the safety without such premise.
  • the signature text u_ input to the signature device i_ ⁇ j ⁇ is used as auxiliary information w_ ⁇ i_ ⁇ j ⁇ paired with the signature text u_ ⁇ i_ ⁇ j ⁇ .
  • ⁇ i_ ⁇ jl ⁇ itself, but h is a predetermined hash function that outputs a hash value with the same number of bits as the input, and the hash value h (u_ ⁇ i_ ⁇ jl ⁇ of u_ ⁇ i_ ⁇ jl ⁇ ) May be auxiliary information w_ ⁇ i_ ⁇ j ⁇ .
  • the signature device and the verification device of the present invention can be realized by a computer and a program as well as by realizing the functions of the signature device and the verification device in the form of nodeware.
  • the program is provided by being recorded on a computer-readable recording medium such as a magnetic disk or semiconductor memory.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computing Systems (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Hardware Design (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Storage Device Security (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

　複数の署名装置が署名する状況における、署名長が署名装置の数に依存しない、RSA署名方法を提供する。 　署名装置i_{m}は、入力された署名文u_{i_{m-1}}がモジュラスn_{i_{m}}を超える場合には何もせず、超えない場合にはRSA方式に準じた署名を行う第一変換手段SS1B105と、その結果に対して、モジュラスn_{i_{m}}だけ大きいほうに写像させる関数をかける全単射変換手段S1B106と、その操作結果がモジュラスn_{i_{m}}を超える場合には何もせず、超えない場合にはRSA方式に準じた署名を行う第二変換手段S1B107と、その操作結果を署名文u_{i_{m}}として出力する出力手段S1B109とを備える。

Description

明 細 書
署名および検証方法ならびに署名および検証装置
技術分野
[0001] 本発明は署名および検証方法ならびに署名および検証装置に関し、特に複数の 署名装置が署名する状況における、署名長が署名装置の数に依存しな 、署名およ び検証方法ならびに署名および検証装置に関する。
背景技術
[0002] 計算機やインターネット環境の普及に伴い、電子的にメッセージを送受信する機会 が増えている。このような場合には、メッセージを送信する途中でメッセージが改竄さ れることを防ぐため、メッセージに電子署名を添付することが望ま 、。
[0003] し力し RSAや DSAと 、つたよく知られた署名方式を用いて複数の署名装置が署名を 作成した場合、全員が署名したことを表すには、全署名装置が個々に署名文を作成 し、それらの署名文を全て保存する必要がある。この為、署名文のデータ長の合計値 が署名装置の台数に比例するので、署名装置数が多い場合には効率がよくない。
[0004] このような問題を解決する署名方式の 1つとして、非特許文献 1に記載される署名方 式が提案されている。図 11に、この従来の署名方式の手順を示す。
[0005] なお、本明細書において使用する記号の意味について、ここで定義しておく。「||」 はビット列同士の連結を意味する。「〇」はビット毎の排他的論理和を意味する。「」 は右の被演算子を指数として左の被演算子をべき乗した値を算出する算術演算子を 表する。例えば、 は f— 1のことである。「_{x}」は Xが添え字であることを表す。例えば 、 u」i}は uのことである。
[0006] 図 11を参照すると、署名対象となる署名文 u_{i_{m-l}}が入力されると (S3F100)、所有 している鍵の正当性の検証 (S3F101)と署名文 u_{i_{m-l}}の正当性の検証 (S3F102)を 実施した後、自署名装置の公開鍵及び既に署名した署名装置の公開鍵を連結した T_{m}を計算する (S3F103)。次に、 T_{m}のハッシュ値と署名文 u_{i_{m_l}}の排他的論理 和 Uを計算し (S3F104)、 Uのビット列のうちはじめのセキュリティパラメタ kビットを a、残り を sとする (S3F105)。次に、 aと自署名装置の RSAモジュラス n_{i_{m}}とを比較し (S3F106) 、 aが RSAモジュラス n_{i_{m}}よりも小さ!/、ときは、 aに対して秘密鍵 d_{i_{m}}で RSA方式に 準じて署名文 u_{i_{m}}を計算し (S3F107)、出力する (S3F109)。このとき sに制御情報とし て 1ビットの情報 0を付けカ卩える。また、 aが RSAモジュラス n_{i_{m}はりも大きいときは、モ ジュラスより大き 、数に対しては RSA署名を計算できな 、ので、 aを n_{i_{m}}だけ減算し たものに対して署名文 u_{i_{m}}を計算し (S3F108)、出力する (S3F109)。このときは sに制 御情報として 1ビットの情報 1を付け加える。
[0007] このように、 RSAの場合、署名装置の RSAモジュラス n_{i_{m}}より大きい数に対しては 署名を計算できないので、非特許文献 1による従来技術では、若し大きい場合はモジ ュラス n_{i_{m}}だけ減算して力も署名を付ける。このとき、後の検証を可能にするため に、後ろに lbitの制御情報 (モジュラスを超えていた場合は 1、そうでない場合は 0)を 付けておく。署名文 u_{i_{m}}の検証時は、署名装置の公開鍵を署名順番と逆順に使 用して検証を繰り返して ヽき、最終的に予め定められた初期値が得られるところまで 遡って検証できることにより、正しい署名であると判断する。
特干文献 1： Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, Hovav Shacham.beq uential Aggregate Signatures from Trapdoor Permutations. In Advances in Cryptolog y -- EUROCRYPT 2004,vol. 3027 of LNCS, pp. 74—90. Springer— Verlag, 2004. 発明の開示
発明が解決しょうとする課題
[0008] 非特許文献 1に記載された従来の署名方式によれば、複数の署名装置が順々に署 名しても署名文のデータ長の合計値が署名装置の台数に比例しな 、ため、署名文 を記憶する場合にはメモリ量の削減が可能になり、通信する場合には通信量の削減 が可能になる。し力しながら、署名長は固定値 +署名回数であり、署名回数が増える と少しずつではあるが署名長が伸びるという問題点がある。
[0009] 本発明の目的は、上述した従来の署名方式が有する問題点を改善し、署名長が署 名装置の数によらずに一定になるようにすることにある。
課題を解決するための手段
[0010] 請求項 1にかかる署名方法は、初期値もしくは他の複数の署名装置が順々に署名 操作を行って作成した署名文、メッセージ、および自署名装置の秘密鍵を入力とし、 入力と同じ長さの署名文を出力する署名装置における署名方法であって、前記出力 した署名文が、その前記出力した署名文の作成にかかわった署名装置が各々の署 名装置に入力された前記メッセージに署名したことを示すものであることを特徴とする
[0011] 請求項 2にかかる署名方法は、請求項 1に記載された署名方法において、署名文を 計算する操作が第 1および第 2の 2つのステップを持ち、前記第 1ステップ (Π-1}の部 分の操作)の計算にはトラップドアつき一方向性置換の逆関数を用い、前記第 2ステ ップ 0 {-1}の部分の操作)の計算には、前記第 1ステップのものと同じもしくは異なるト ラップドアつき一方向性置換の逆関数を用い、前記第 1ステップが終了したら計算結 果を記憶媒体に記憶し、前記第 2ステップ開始時には必要なデータを前記記憶媒体 から読み出し、前記第 2ステップが終了したら計算結果を前記記憶媒体に記憶するこ とを特徴とする。
[0012] 請求項 3にかかる署名方法は、請求項 2に記載された署名方法において、前記第 1 ステップでは、前記第 1ステップへの入力がもし前記トラップドアつき一方向性置換の 値域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を写 像し、そうでなければ何もしないというものであり、前記第 2ステップへの入力がもし前 記トラップドアつき一方向性置換の値域の元であればその前記トラップドアつき一方 向性置換の逆関数で前記入力を写像し、そうでなければ何もしな 、と 、うものである ことを特徴とする。
[0013] 請求項 4に力かる署名方法は、請求項 3に記載された署名方法において、前記第 2 ステップで用いる前記トラップドアつき一方向性置換の計算がさらに第 1および第 2の サブステップからなり、前記第 1サブステップ（ φ -1}の部分の操作)では、署名文全 体の空間上の全単射を計算し、その全単射が多項式時間で計算でき、し力もその前 記全単射の逆関数も多項式時間で計算できるものであり、前記第 2サブステップ (g llの部分の操作)ではトラップドアつき一方向性置換の逆関数を用い、もし前記トラッ プドアつき一方向性置換の値域の元であればその前記トラップドアつき一方向性置 換の逆関数で前記入力を写像し、そうでなければ何もしないというものであり、前記第 1サブステップおよび前記第 2サブステップの開始時には必要なデータを前記記憶媒 体から読み込み、前記第 1サブステップおよび前記第 2サブステップの終了時には計 算結果を前記記憶媒体に書き込むことを特徴とする。
[0014] 請求項 5にかかる署名方法は、請求項 4に記載された署名方法において、前記第 1 ステップで使用する前記トラップドアつき一方向性置換と、前記第 2ステップの前記第 2サブステップで使用する前記トラップドアつき一方向性置換とが RSA関数であること を特徴とする。
[0015] 請求項 6にかかる署名方法は、請求項 5に記載された署名方法において、前記第 2 ステップの前記第 1サブステップで使用する前記全単射力 (x) = X - n_{i_{m}} mod 2 κ }とかけ、前記 n_{i_{m}}が署名装置 i_{m}の公開鍵の一部である RSAモジュラスであ り、前記 κがセキュリティ 'パラメータであることを特徴とする。
[0016] 請求項 7にかかる署名方法は、請求項 6に記載された署名方法において、前記第 1 ステップの前に T_{m}計算ステップがあり、前記 T_{m}計算ステップでは、 T_{m} = M_{1}|| •••l|M_{m}||pk_{i_{l}}|卜 · ' ||ρ1 ί_{πι}}を計算し、各 jに対し前記 Μ_{1}, · · ·， M_{j}が潘目の署 名装置に入力されたメッセージであり、前記 pk_{i_{j}}が署名装置 i_{j}の公開鍵であるこ とを特徴とする。
[0017] 請求項 8にかかる署名方法は、請求項 7に記載された署名方法で、前記第 1ステツ プの前に排他的論理和計算ステップがあり、前記排他的論理和計算ステップでは、 U=H(T_{m})〇u_{i_{m-l}}を計算し、前記 Hがハッシュ関数で、前記 u_{i_{m-l}}が前記入 力された署名文であり、〇が排他的論理和であることを特徴とする。
[0018] 請求項 9にかかる署名方法は、請求項 8に記載された署名方法で、前記第 1ステツ プより前に鍵正当性検証ステップがあり、前記鍵正当性検証ステップでは pk_{i_{l}}， · · - , Pk_{i_{m-1}}が全て異なることを確認する力 ただし m=lの場合は何も確認しないステ ップであることを特徴とする。
[0019] 請求項 10にかかる署名方法は、請求項 9に記載された署名方法で、前記第 1ステツ プより前に、入力の署名文を検証する署名文検証ステップがあることを特徴とする。
[0020] 請求項 11にかかる署名方法は、請求項 8に記載された署名方法で、前記第 1ステツ プより前に、 pk_{i_{l}},〜，pk_{i_{m- 1}}が全て異なることを確認する鍵正当性検証ステツ プと、入力の署名文を検証する署名文検証ステップとがあることを特徴とする。 [0021] 請求項 12に力かる署名方法は、請求項 1ないし 11の何れか 1項に記載された署名 方法において、入力の初期値もしくは署名文またはそれらのノ、ッシュ値を補助情報と して作成し前記記憶媒体に書き込むステップを含み、前記補助情報と署名文とを組 にして出力することを特徴とする。
[0022] 請求項 13にかかる署名方法は、入力手段が、初期値もしくは他の複数の署名装置 が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それらの署名装置に入力さ れたメッセージ Μ_{1}, · · ·， M_{m-1}を入力し、記憶媒体に保存するステップ、 T_{m}計算 手段が、前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、 pk_{i_{j }}を署名装置 i_{j}の公開鍵、 IIをビット列同士の連結とするとき、 T_{m} = M_{l}|| - ||M_{m} llpkjijl}川… ||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するステップ、排 他的論理和計算手段が、 Hをハッシュ関数、〇を排他的論理和とするとき、前記記憶 媒体から必要なデータを読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果を前 記記憶媒体に保存するステップ、第一変換手段が、前記記憶媒体から必要なデータ を読み込み、 n_{i_{m}}を自署名装置の RSAモジュラスとするとき、 U< n_{i_{m}}であれば 、 v= u djijm}}} mod n_{i_{m}}を計算し、それ以外であれば、 v=Uを計算し、計算結果 を前記記憶媒体に保存するステップ、全単射変換手段が、前記記憶媒体から必要な データを読み込み、 κをセキュリティ 'パラメータとするとき、 v'=v + n_{i_{m}} mod 2 κ } を計算し、計算結果を前記記憶媒体に保存するステップ、第二変換手段が、前記記 憶媒体から必要なデータを読み込み、 v' < n_{i_{m}}ならば、 u_{i_{m}} = v' djijm}}} mod n_{i_{m}}を計算し、それ以外ならば、 u_{i_{m}} = vを計算し、計算結果を前記記憶媒体 に保存するステップ、出力手段が、前記記憶媒体力 u_{i_{m}}を読み込み、署名文と して出力するステップ、を含むことを特徴とする。
[0023] 請求項 14に力かる署名方法は、請求項 13に記載される署名方法において、 wセット 手段が、 w_{i_{m}}=u_{i_{m-l}}、または、 hをハッシュ関数としたとき、 w_{i_{m}}=h(u_{i_{m-l} })を計算し、計算結果を前記記憶媒体に保存するステップを含み、前記計算した w_{i_ {m}}を補助情報として、前記作成した署名文 u_{i_{m}}と組にして出力することを特徴と する。
[0024] 請求項 15にかかる検証方法は、複数の署名装置が順々に署名操作を行って作成 した署名文 Uが正当であるかどうかを検証する検証装置における検証方法において、 検証を通過するのは、署名文 uが、前記出力した署名文がその前記出力した署名文 の作成にかかわった署名装置が各々の署名装置に入力された前記メッセージに署 名したときおよびそのときのみであり、前記署名文 Uのビット長が前記署名文 Uを計算 するのにかかわった前記署名装置の数に依存しな 、定数であることを特徴とする。
[0025] 請求項 16にかかる検証方法は、複数の署名装置が順々に署名操作を行って作成 した署名文 uが正当であるかどうかを検証する検証装置における検証方法において、 検証を通過するのは、署名文 uを作成した署名装置が正当な方法で署名文 uを作成 したときおよびそのときのみであり、前記署名文 uのビット長が前記署名文 uを計算す るのにかかわった前記署名装置の数に依存しな 、定数であり、しかも前記署名文 uの 検証は、前記複数の署名装置のうち最後の 1台が署名操作を施す前のデータである 補助情報 wを使って行うことを特徴とする。
[0026] 請求項 17に力かる検証方法は、請求項 15または 16に記載された検証方法におい て、署名文を検証する操作が第 1および第 2の 2つのステップがあり、前記第 1ステップ (hの部分の操作)の計算にはトラップドアつき一方向性置換を用い、前記第 2ステツ プ (fの部分の操作)の計算には、前記第 1ステップのものと同じもしくは異なるトラップ ドアつき一方向性置換を用い、前記第 1ステップおよび第 2ステップを開始する際、記 憶媒体から必要なデータを読み込み、前記第 1ステップおよび第 2ステップを終了す る際、前記記憶媒体に計算結果を書き込むことを特徴とする。
[0027] 請求項 18に力かる検証方法は、請求項 17に記載された検証方法において、前記 第 1ステップでは、前記第 1ステップへの入力がもし前記トラップドアつき一方向性置 換の定義域の元であればその前記トラップドアつき一方向性置換で前記入力を写像 し、そうでなければ何もしないものであり、前記第 2ステップへの入力がもし前記トラッ プドアつき一方向性置換の定義域の元であればその前記トラップドアつき一方向性 置換で前記入力を写像し、そうでなければ何もしな 、ものであることを特徴とする。
[0028] 請求項 19に力かる検証方法は、請求項 18に記載された検証方法にぉ 、て、前記 第 1ステップで用いる前記トラップドアつき一方向性置換の計算がさらに第 1および第 2の 2つのサブステップ力 なり、前記第 1サブステップ (gの部分の操作)ではトラップド ァつき一方向性置換の関数を用い、もし前記トラップドアつき一方向性置換の値域の 元であればその前記トラップドアつき一方向性置換の関数で入力を写像し、そうでな ければ何もしないというものであり、前記第 2サブステップ（ φの部分の操作)では、署 名文全体の空間上の全単射を計算し、その全単射が多項式時間で計算でき、し力も その前記全単射の逆関数も多項式時間で計算できるものであり、前記第 1サブステツ プおよび前記第 2サブステップの開始時には必要なデータを前記記憶媒体力 読み 込み、前記第 1サブステップおよび前記第 2サブステップの終了時には計算結果を前 記記憶媒体に書き込むことを特徴とする。
[0029] 請求項 20にかかる検証方法は、請求項 19に記載された検証方法にお 、て、前記 第 1ステップの前記第 1サブステップで使用する前記トラップドアつき一方向性置換と 、前記第 2ステップで使用する前記トラップドアつき一方向性置換とが RSA関数である ことを特徴とする。
[0030] 請求項 21にかかる検証方法は、請求項 20に記載された検証方法にお 、て、前記 第 1ステップの前記第 2サブステップで使用する前記全単射が、 (x) = X + n_i_{m} mo d 2 κ }とかけ、前記 n_{i_{m}}が署名装置 i_{m}の公開鍵の一部である RSAモジュラスで あり、前記 κがセキュリティ 'パラメータであることを特徴とする。
[0031] 請求項 22に力かる検証方法は、請求項 21に記載された検証方法にぉ 、て、前記 第 2ステップの後に T_{j}計算ステップがあり、前記 T_{j}計算ステップでは、 T_{j} = M_{1}|| •••l|M_{j}||pk_{i_{l}川… ||pk_{i_{j}}を計算するものであり、ここで、各 jに対し前記 M_{1}， M_{j}が j番目の署名装置に入力されたメッセージであり、前記 pk_{i_{j}}が署名装置 i_{j} の公開鍵であることを特徴とする。
[0032] 請求項 23に力かる検証方法は、請求項 22に記載された検証方法にぉ 、て、前記 T_ {j}計算ステップの後に、 Hをハッシュ関数、 Uを第 2ステップの計算結果とするとき、前 記記憶媒体から必要なデータを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算結果 を前記記憶媒体に保存する u計算ステップがあることを特徴とする。
[0033] 請求項 24に力かる検証方法は、請求項 23に記載された検証方法にぉ 、て、前記 第 1ステップ、前記第 2ステップ、前記 T_{j}計算ステップおよび前記 u計算ステップを、 j =m-l , · · · , 1に対して繰り返すことを特徴とする。 [0034] 請求項 25にかかる検証方法は、請求項 24に記載された検証方法にお 、て、前記 第 1ステップ、前記第 2ステップ、前記 T_{j}計算ステップおよび前記 u計算ステップを、 j =m-l , " ' , lに対して繰り返す前に、鍵正当性検証ステップがあり、前記鍵正当性検証 ステップでは、 pkjijl}}, - - - , pk_{i_{m-l}}が全て異なることを確認する力 ただし m=lの 場合は何も確認しな ヽものであることを特徴とする。
[0035] 請求項 26に力かる検証方法は、請求項 25に記載された検証方法にぉ 、て、前記 第 1ステップ、前記第 2ステップ、前記 T_{j}計算ステップおよび前記 u計算ステップを、 j =m-l , · · · , 1に対して繰り返した後に、検証結果として初期値が得られたカゝどうかを判 定する u判定ステップがあることを特徴とする。
[0036] 請求項 27にかかる検証方法は、請求項 21に記載された検証方法にお 、て、前記 第 1ステップの前に T_{m-1}計算ステップおよび V"計算ステップがあり、前記 T_{m-1}計 算ステップでは、 T_{m-1} = M_{l}| ' ||M_{m-l}||pk_{i_{l}}| ' ||pk_{i_{m-l}}を計算するもの であり、ここで、 Μ_{1},· ··， M_{m- 1}が l ' ,m-l番目の署名装置に入力されたメッセ一 ジであり、前記 pk_{i_{j}}が署名装置 i_{j}の公開鍵であり、前記 V"計算ステップでは、 v" =H(T_{m- l})〇u_{i_{m-l}}を計算するものであり、かつ、前記第 1ステップは前記 v"を入 力とし、かつ、前記第 2ステップの後に、前記第 2ステップの計算結果が前記補助情 報に一致する力判定する u判定ステップがあることを特徴とする。
[0037] 請求項 28に力かる検証方法は、入力手段が、他の 1以上の署名装置が順々に署名 操作を行って作成した署名文 u_{i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1},· ··, M_{m-1}、それらの署名装置の公開鍵 pk_{i_{l}},〜,pk_{i_{m-l}}を入力し、記 憶媒体に保存するステップ、 j初期化手段が、変数 jに m-1をセットするステップ、第二 変換手段が、前記記憶媒体から必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であれば、 v'=u_{i_{j}He_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計算し、計算 結果を前記記憶媒体に保存するステップ、全単射計算手段が、前記記憶媒体から 必要なデータを読み込み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶 媒体に保存するステップ、第一変換手段が、前記記憶媒体から必要なデータを読み 込み、 Vく n_{i_{j}}であれば、 U=v e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 U=v を計算し、計算結果を前記記憶媒体に保存するステップ、前記変数 jが 0になるまで、 前記変数 jを- 1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換 手段による前記ステップを繰り返すステップ、 T_{j}計算手段が、前記記憶媒体から必 要なデータを読み込み、 T_{j} = M_{1川… ||M_{j}||pk_{i_{l}川… ||pk_{i_{j}}を計算し、計算結 果を前記記憶媒体に保存するステップ、 u計算手段が、前記記憶媒体から必要なデ ータを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算結果を前記記憶媒体に保存 するステップ、 u判定手段が、前記記憶媒体から必要なデータを読み込み、 u=予め定 められた初期値であるかどうかを判定するステップ、出力手段が、 u=予め定められた 初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す 通知を出力するステップ、を含むことを特徴とする。
請求項 29に力かる検証方法は、入力手段が、他の 1以上の署名装置が順々に署名 操作を行って作成した署名文 u_{i_{m-l}}、 1つ前の署名装置が入力した署名文または そのハッシュ値である補助情報 v_{i_{m-l}}、それらの署名装置に入力されたメッセ一 ジ M_{1}， · · · , M_{m-1}、それらの署名装置の公開鍵 pk_{i_{l}}， · · · ,pk_{i_{m-l}}を入力し、 記憶媒体に保存するステップ、 T_{m-1}計算手段が、前記記憶媒体から必要なデータ を読み込み、 T_{m-1} = M_{1}|卜 · · llMjm-llllpkJiJl}}!卜 lpkifoi-l}}を計算し、計算結 果を前記記憶媒体に保存するステップ、 V"計算手段が、前記記憶媒体から必要な データを読み込み、 v"=H(T_{m-l})〇u_{i_{m-l}}を計算し、計算結果を前記記憶媒体 に保存するステップ、第二変換手段が、前記記憶媒体から必要なデータを読み込み 、 V"く n_{i_{m- 1}}であれば、 v'=v" e_{i_{m-l}}} mod n_{i_{m- 1}}を計算し、それ以外であ れば、 v =v "を計算し、計算結果を前記記憶媒体に保存するステップ、全単射計算 手段が、前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を 計算し、計算結果を前記記憶媒体に保存するステップ、第一変換手段が、前記記憶 媒体カゝら必要なデータを読み込み、 Vく n_{i_{m-l}}であれば、 u_{i_{m-2}}=v e_{i_{m-l}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 u_{i_{m-2}}=vを計算し、計算結果を前記 記憶媒体に保存するステップ、 u判定手段が、前記記憶媒体から必要なデータを読 み込み、 u_{i_{m-2}}またはそのハッシュ値が前記補助情報 V_{i_{m-1}}と一致するかどう かを判定するステップ、出力手段が、 u_{i_{m-2}}またはそのノ、ッシュ値が前記補助情 報 V_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失 敗を示す通知を出力するステップ、を含むことを特徴とする。
[0039] 請求項 30にかかる署名装置は、読み書き可能な記憶媒体と、初期値もしくは他の 複数の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それらの署 名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}を入力し、前記記憶媒体に保存す る入力手段と、前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、 pk_{i_{j}}を署名装置 i_{j}の公開鍵、 ||をビット列同士の連結とするとき、 T_{m} = Μ_{1}|| · · · | |M_{m}||pk_{i_{l}}|卜 ||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存する T_{m}計 算手段と、 Hをハッシュ関数、〇を排他的論理和とするとき、前記記憶媒体から必要 なデータを読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果を前記記憶媒体 に保存する排他的論理和計算手段と、前記記憶媒体から必要なデータを読み込み 、 n_{i_{m}}を自署名装置の RSAモジュラスとするとき、 Uく n_{i_{m}}であれば、 v= u d_{i_{ m}}} mod n_{i_{m}}を計算し、それ以外であれば、 v=Uを計算し、計算結果を前記記憶 媒体に保存する第一変換手段と、前記記憶媒体から必要なデータを読み込み、 Kを セキュリティ ·パラメータとするとき、 ν'=ν + n_{i_{m}} mod 2 κ }を計算し、計算結果を前 記記憶媒体に保存する全単射変換手段と、前記記憶媒体から必要なデータを読み 込み、 Vく n_{i_{m}}ならば、 u_{i_{m}} = v' djijm}}} mod n_{i_{m}}を計算し、それ以外なら ば、 u_{i_{m}} = Vを計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前 記記憶媒体力 u_{i_{m}}を読み込み、署名文として出力する出力手段と、を含むことを 特徴とする。
[0040] 請求項 31にかかる署名装置は、請求項 30に記載される署名装置において、 w_{i_{m} }=u_{i_{m-l}}、または、 hをハッシュ関数としたとき、 w_{i_{m}}=h(U_{i_{m-l}})を計算し、計 算結果を前記記憶媒体に保存する wセット手段を含み、前記計算した w_{i_{m}}を補助 情報として、前記作成した署名文 u_{i_{m}}と組にして出力するものであることを特徴と する。
[0041] 請求項 32に力かる検証装置は、読み書き可能な記録媒体と、他の 1以上の署名装 置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それらの署名装置に入力 されたメッセージ M_{1}， · · · , M_{m- 1}、それらの署名装置の公開鍵 pk_{i_{l}}， · · · ,pk_{i_{m- 1»を入力し、記憶媒体に保存する入力手段と、変数 jに m-1をセットする j初期化手段 と、前記記憶媒体から必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であれば、 v'=u_{i_{j}H e_{i_腿 mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計算し、計算結果を前 記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデータを読み込 み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶媒体に保存する全単射 計算手段と、前記記憶媒体から必要なデータを読み込み、 Vく n_{i_®であれば、 U=v e_{i_腿 mod n_{i_{j}}を計算し、それ以外であれば、 U=vを計算し、計算結果を前記記 憶媒体に保存する第一変換手段と、前記変数 j力 SOになるまで、前記変数 jを- 1する毎 に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステツ プが繰り返し実行された後、前記記憶媒体から必要なデータを読み込み、 T_{j} = M_{ i}||-||M_{j}| |Pk_{i_{i}}|卜 · · I |pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存する T_{j} 計算手段と、前記記憶媒体から必要なデータを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計 算し、計算結果を前記記憶媒体に保存する u計算手段と、前記記憶媒体から必要な データを読み込み、 u=予め定められた初期値であるかどうかを判定する u判定手段と 、 u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなけれ ば、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする。
請求項 33にかかる検証装置は、読み書き可能な記録媒体と、他の 1以上の署名装 置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、 1つ前の署名装置が入力 した署名文またはそのハッシュ値である補助情報 v_{i_{m-l}}、それらの署名装置に入 力されたメッセージ M_{1}， · · · , M_{m-1}、それらの署名装置の公開鍵 pk_{i_{l}}， · · · ,pk_{i_{ m-1}}を入力し、記憶媒体に保存する入力手段と、前記記憶媒体から必要なデータを 読み込み、 T_{m-1} = M_{1川… ||M_{m-l}||pk_{i_{l}川… ||pk_{i_{m- 1}}を計算し、計算結果 を前記記憶媒体に保存する T_{m-1}計算手段と、前記記憶媒体から必要なデータを 読み込み、 v"=H(T_{m-l})〇U_{i_{m-l}}を計算し、計算結果を前記記憶媒体に保存す る V"計算手段と、前記記憶媒体から必要なデータを読み込み、 V"く n_{i_{m-l}}であれ ば、 v'=v' {e_{i_{m-l}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 v'=v "を計算し、 計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデ ータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を計算し、計算結果を前記記憶媒体に 保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、 v<n_{i_{m -1}}であれば、 u_{i_{m-2}}=v e_{i_{m-l}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記 記憶媒体力 必要なデータを読み込み、 u_{i_{m-2}}またはそのハッシュ値が前記補助 情報 v_{i_{m-l}}と一致するかどうかを判定する u判定手段と、 u_{i_{m-2}}またはそのハツ シュ値が前記補助情報 V_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そう でなければ、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする。
[0043] 請求項 34に力かるプログラムは、読み書き可能な記憶媒体を有するコンピュータを 、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文 u_{ i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}を入力し、前記 記憶媒体に保存する入力手段と、前記記憶媒体および公開鍵記憶装置から必要な データを読み込み、 pk_{i_{j}}を署名装置 i_{j}の公開鍵、 IIをビット列同士の連結とすると き、 T_{m} = M_{1川… ||M_{m}||pk_{i_{l}川一|| {1 }}を計算し、計算結果を前記記憶媒 体に保存する T_{m}計算手段と、 Hをハッシュ関数、〇を排他的論理和とするとき、前 記記憶媒体から必要なデータを読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結 果を前記記憶媒体に保存する排他的論理和計算手段と、前記記憶媒体から必要な データを読み込み、 n_{i_{m}}を自署名装置の RSAモジュラスとするとき、 U< n_{i_{m}}で あれば、 v= u djijm}}} mod n_{i_{m}}を計算し、それ以外であれば、 v=Uを計算し、計 算結果を前記記憶媒体に保存する第一変換手段と、前記記憶媒体から必要なデー タを読み込み、 κをセキュリティ 'パラメータとするとき、 v'=v + n_{i_{m}} mod 2 κ }を計 算し、計算結果を前記記憶媒体に保存する全単射変換手段と、前記記憶媒体から 必要なデータを読み込み、 v' < n_{i_{m}}ならば、 u_{i_{m}} = v' djijm}}} mod n_{i_{m}}を 計算し、それ以外ならば、 u_{i_{m}} = Vを計算し、計算結果を前記記憶媒体に保存す る第二変換手段と、前記記憶媒体から u_{i_{m}}を読み込み、署名文として出力する出 力手段と、して機能させることを特徴とする。
[0044] 請求項 35に力かるプログラムは、請求項 34に記載されるプログラムにおいて、前記 コンピュータをさらに、 w_{i_{m}}=u_{i_{m-l}}、または、 hをハッシュ関数としたとき、 w_{i_{m} }=h(u_{i_{m-l}})を計算し、計算結果を前記記憶媒体に保存する wセット手段、として機 能させ、かつ、前記計算した w— {i— {m}}を補助情報として、前記作成した署名文 u_{i_{m}} と組にして出力することを特徴とする。
[0045] 請求項 36に力かるプログラムは、読み書き可能な記録媒体を有するコンピュータを 、他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それ らの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}、それらの署名装置の公開 鍵 pk_{i_{l}}, " ' ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、変数 jに m-1を セットする j初期化手段と、前記記憶媒体から必要なデータを読み込み、 u_{i_{j}}<n_{i_{j} }であれば、
Figure imgf000015_0001
mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計 算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必 要なデータを読み込み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶媒 体に保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、 ν<η_ {i_{j}}であれば、 U=v e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 U=vを計算し、 計算結果を前記記憶媒体に保存する第一変換手段と、前記変数 jが 0になるまで、前 記変数 jを- 1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手 段による前記ステップが繰り返し実行された後、前記記憶媒体力 必要なデータを読 み込み、 T_{j} = M_{1}|卜 · · llMJ pkJiJl}}!卜 lpkiij}}を計算し、計算結果を前記記憶 媒体に保存する T_{j}計算手段と、前記記憶媒体から必要なデータを読み込み、 u_{i_{j -l}}=H(T_{j})〇Uを計算し、計算結果を前記記憶媒体に保存する u計算手段と、前記 記憶媒体から必要なデータを読み込み、 u=予め定められた初期値であるかどうかを 判定する u判定手段と、 u=予め定められた初期値であれば、検証成功を示す通知を 出力し、そうでなければ、検証失敗を示す通知を出力する出力手段として機能させる ことを特徴とする。
[0046] 請求項 37に力かるプログラムは、読み書き可能な記録媒体を有するコンピュータを 、他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、 1つ 前の署名装置が入力した署名文またはそのハッシュ値である補助情報 v_{i_{m-l}}、そ れらの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}、それらの署名装置の公 開鍵 Pk_{i_{l}}, ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、前記記憶媒 体から必要なデータを読み込み、 T_{m-1} = M_{1}| I · · · I |M_{m-l}| |pk_{i_{l}}| | · · · | |pk_{i_{m- 1»を計算し、計算結果を前記記憶媒体に保存する T_{m-1}計算手段と、前記記憶媒 体から必要なデータを読み込み、 v"=H(T_{m-l})〇U_{i_{m-l}}を計算し、計算結果を 前記記憶媒体に保存する V"計算手段と、前記記憶媒体から必要なデータを読み込 み、 V"く n_{i_{m- 1}}であれば、 v'=v" e_{i_{m-l}}} mod n_{i_{m- 1}}を計算し、それ以外で あれば、 v =v "を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前 記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を計算し、計 算結果を前記記憶媒体に保存する全単射計算手段と、前記記憶媒体から必要なデ ータを読み込み、 Vく n_{i_{m- 1}}であれば、 u_{i_{m-2}}=v~{e_{i_{m-l}}} mod n_{i_{m- 1}}を計 算し、それ以外であれば、 u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存す る第一変換手段と、前記記憶媒体から必要なデータを読み込み、 u_{i_{m-2}}またはそ のノ、ッシュ値が前記補助情報 v_{i_{m-l}}と一致するかどうかを判定する u判定手段と、 u_{i_{m-2}ほたはそのハッシュ値が前記補助情報 V_{i_{m-1}}と一致すれば、検証成功 を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段と 、して機能させることを特徴とする。
『作用』
本発明にあっては、署名装置 i_{m}において、入力された署名文 u_{i_{m-l}}がモジュ ラス n_{i_{m}}を超える場合には何もせず、超えない場合には RSA署名に準じた署名を 行う第 1操作と、第 1操作の結果に対して、モジュラス n_{i_{m}}だけ大きいほうに写像さ せる関数をカゝける第 2操作と、この第 2操作の結果がモジュラス n_{i_{m}}を超える場合 には何もせず、超えない場合には RSA署名に準じた署名を行う第 3操作とを行う。ここ で、各署名装置の RSAモジュラスのビット長がセキュリティ 'パラメータ κに等しいとす ると、署名文 u_{i_{m-l}}および署名装置 i_{m}のモジュラス n_{i_{m}}は、 κはり小さい数 になる。第 1操作では、 0〜n_{i_{m}}の値をとる署名文 u_{i_{m-l}}については RSA署名に 準じた署名が行われるため、第 1操作後の値は 0〜n_{i_{m}}になり、他方、 n_{i_{m}}〜2 κ }の値をとる署名文 u_{i_{m- 1}}につ 、ては何もしな 、ので、第 1操作後の値は n_{i_{m}} 〜 { κ }になる。また、第 2操作では、第 1操作後の値力も 2 κ }をモジュラスとする n_{i_{ m}}の加算を行うので、第 2操作後の値も 2 κはり小さい数になるが、第 1操作後の値 が n_{i_{m}}〜2 κ }であったものは第 2操作後は 0〜n_{i_{m}}になる。従って、第 3操作に おいて、第 2操作後の値力^〜 n_{i_{m}}となるものに対して RSA署名に準じた署名を行 うことで、任意の値の署名文 u_{i_{m-l}}に対し、少なくとも 1回は RSA署名が行われるこ とになる。また、第 3操作後の値、つまり署名値 u_{i_{m}}の値と入力の署名文 u_{i_{m-l}} の値とは 1対 1に対応するため、署名値 u_{i_{m}}の値から、施された署名操作が一意に 決定できるため、非特許文献 1におけるような制御ビットを付加する必要がなくなる。 発明の効果
[0048] 第 1の効果は，署名長が署名装置の数に依存しないことである。その理由は署名前 のデータと、署名後にできるデータのビット数が不変であることによる。
[0049] 第 2の効果は、署名装置の順番を、署名のたびに変えることができることである。そ の理由は第 1の効果の場合と同じで署名前のデータと、署名後にできるデータのビッ ト数が不変であること〖こよる。この為、各署名装置への入力が、その署名装置が何番 目に署名を行うのかによらず一定であり、その為に何番目であっても同じ操作で署名 ができる。
[0050] 第 3の効果は，署名装置と結託した攻撃者が、経路の途中で honestな署名装置を 通って 、る署名文を偽造できな 、ことにある。その理由は署名装置への入力 uが 、か なるものであっても、署名時に最大 2回行う RSA計算の少なくとも一方で uが変化する 力 である。
[0051] 第 4の効果は、システムの運用を始めた段階で署名装置の数 mがわ力つている必要 はなぐ署名装置の数 mは運用中に動的に変わっても支障なく適用できることである 。その理由は、署名装置の数が m+1台のときの署名手順は、署名装置の数が m台の ときの署名手順を行つた後に同様の署名操作をさらに 1回行うというものであり、署名 装置の数 mに署名の操作方法が依存しな!、からである。
図面の簡単な説明
[0052] [図 1]本発明の第 1の実施の形態のブロック図である。
[図 2]本発明の第 1の実施の形態における署名装置の構成を示すブロック図である。
[図 3]本発明の第 1の実施の形態における署名装置の動作を示す流れ図である。
[図 4]本発明の第 1の実施の形態における検証装置の構成を示すブロック図である。
[図 5]本発明の第 1の実施の形態における検証装置の動作を示す流れ図である。
[図 6]本発明の第 2の実施の形態のブロック図である。 [図 7]本発明の第 2の実施の形態における署名装置の構成を示すブロック図である。
[図 8]本発明の第 2の実施の形態における署名装置の動作を示す流れ図である。
[図 9]本発明の第 2の実施の形態における検証装置の構成を示すブロック図である。
[図 10]本発明の第 2の実施の形態における検証装置の動作を示す流れ図である。
[図 11]従来の署名装置の動作を示す流れ図である。
符号の説明
[0053] i— {1},…上 {m-1} 署名装置
i_{l}-2,-,i_{m-l}-2 検証装置
i_{l}-3,-,i_{m-l}-3 鍵記憶装置
i_{l}-4, · · · ,i— {m- 1}- 4 鍵正当性検証装置
ί_{1}-5,· · -,i_{m-l}-5 鍵生成装置
Μ_{1},· ··, M_{m} メッセージ
u_ {i_{0}},-, u_ {i_{m-l}} 署名文
w_ {i_{0}},-, w_ {i_{m-l}} 補助情報
発明を実施するための最良の形態
[0054] 『第 1の実施の形態』
図 1を参照すると、本発明の第 1の実施の形態は、署名装置 i_{l}，… {m}、検証装置 i — {1}- 2,· ··,ί— {m}- 2、公開鍵記憶装置 i— {1}- 3,· ··,ί— {m}- 3、鍵正当性検証装置 i— {1}- 4,· ··,ί— { m}-4、秘密鍵記憶装置 i— {1}-5, · · · ,i— {m}-5から構成される。
[0055] 図 2を参照すると、署名装置 i_{m}は、入力手段 S1B100、 T_{m}計算手段 S1B103、排 他的論理和計算手段 S1B104、第一変換手段 S1B105、全単射変換手段 S1B106、第 二変換手段 S1B107、記憶媒体 S1B108および出力手段 S1B109から構成される。他の 署名装置も署名装置 i_{m}と同様の構成を有する。
[0056] 図 4を参照すると、検証装置 i_{m}-2は、入力手段 V1B100、 j初期化手段 V1B102、 j判 定手段 V1B103、第二変換手段 V1B104、全単射変換手段 V1B105、第一変換手段 V 1B106、 T_{j}計算手段 V1B107、 u計算手段 V1B108、 j減少手段 V1B109、記憶媒体 VI B1010、 u判定手段 V1B1011、 accept出力手段 V1B1012および reject出力手段 V1B10 13から構成される。他の検証装置も検証装置 i_{m}-2と同様の構成を有する。 [0057] 本実施の形態の概略を述べる。まず、署名装置 i_{l}に、署名装置 i_{l}の公開鍵秘 密鍵ペア、初期値 u_{i_{0}}、およびメッセージ M_{1}が入力される。署名装置 i_{l}は u_{i_{ 0}}を用いてメッセージ M_{1}に対する署名文 u_{i_{l}}を作成する。以下順に署名装置 i_{j }に、署名装置 i_{j}の公開鍵秘密鍵ペア、直前の署名装置が出力した署名文 u_{i_{j-l}} 、およびメッセージ M_{j}が入力され、署名装置 i_{j}はこれら用いて署名文 u_{i_{j}}を作成 する。署名文 u_{i_{j}}は、署名装置 i_{l}がメッセージ M_{1}に署名し、署名装置 i_{2}がメッ セージ M_{2}に署名し、 ···、署名装置 i_{j}がメッセージ M_{j}に署名したことを表すデー タである。
[0058] 各 jに対し、検証装置 i_{j}に署名装置 i_{l}， · · · ,i_{j}の公開鍵とメッセージ M_{1}， · · · ,M_{j- 1}、および署名文 u_{i_{j-l}}が入力される。すると検証装置 i_{j}は署名文 u_{i_{j-l}}がメッ セージ M_{1}， · · · ,M_{j-l}に対する、署名装置 i_{l}， · · · ,i_{j-l}の秘密鍵を使って作成され た署名文であるかどうかを検証する。
[0059] 本実施の形態のシステムの目標は、署名文 u_{i_{m}}、すなわち署名装置 i_{l}がメッセ ージ M_{1}に署名し、署名装置 i_{2}がメッセージ M_{2}〖こ署名し、 ···、署名装置 i_{m}がメ ッセージ M_{m}に署名したことを表すデータを作成することである。
[0060] なお、本実施の形態のシステムの運用を始めた段階で署名装置の数 mがわ力つて いる必要はない。署名装置の数 mは運用中に動的に変わってもよい。また、署名装 置 i_{l}, ,i_{m}の動作は全て同様である。検証装置、公開鍵記憶装置、鍵正当性検 証装置、秘密鍵記憶装置も全て基本的に同じ動作を行う。
[0061] 次に本実施の形態の詳細を述べる。
[0062] 署名装置 i_{j}の公開鍵 pk_{i}、秘密鍵 sk_{i}はそれぞれ (n_{i},e_{i})、（p_{i_{j}}， q_{i_{j}}, d_ {i_{j}})で、次の 5性質を満たすものである。
1. P_{i_{j}}, qJiJj}}は素数。
2. n_{i_{j}} =P_{i_{j}}q_{i_{j}}
3. n_{i_{j}}のビット長がセキュリティパラメータ κに等しい。
4. p_{i_{j}}, q_{i_{j}}のビット長が同程度。
5. e_{i_{j}}は Φ(η_{ί})と互いに素。
6. d_{i_{j}}=e_{i_{j}} -1 mod Φ(η_{ί}) ただし、ここで Φ(η_{ί})は 1以上 n_{i}未満で n_{i}と互いに素な整数の個数。これらの性質 を満たす (pk_{i},(sk_{i})の作り方は、例えば、非特許文献 2「Alfred J. Menezes Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Pr ess.」 (http://www.cacr.math.uwaterloo.ca/hac/)に記載されている。
[0063] 安全性の観点力も言えば、 e_{i_{j}}が Φ(η_{ί})と互いに素であることを皆が確認できる ことが望ま 、。この確認を可能にする方法としてたとえば e_{i_{j}}を n_{iはりも大き ヽ素 数にするという方法がある。しかし、必ずしも e_{i_{j}}がこの性質を満たす必要はない。
[0064] 各 j=l,〜,mに対し、秘密鍵記憶装置 i_{j}-5は秘密鍵 sk_{i_{j}}を記憶し、さらに公開鍵 記憶装置 i_{j}-3は、公開鍵 pk_{l}，… ,pk_{m}を記憶する。
[0065] 鍵正当性検証装置 i_{m}-4の動作を説明する。鍵正当性検証装置 i_{m}-4は、公開 鍵 pk_{i_{l}}， · ··, pk_{i_{m-l}}の正当性を確認する装置である。正当性を確認するには、 まず鍵記憶装置 i_{m}-3から pk_{i_{l}},"'， pk_{i_{m-l}}を読み込み、 pk_{i_{l}},"'， pkjijm -1}}が全て異なることを確認する。ただし m=lの場合は何も確認しな 、。
[0066] 安全性の観点力も言えば、 e_{i_{j}}が Φ(η_{ί})と互いに素であることも確認しておくこと が望ま 、が、この確認は省略することも可能である。
[0067] 署名装置 i_{m}の動作を説明する。メッセージ M_{1}， · ··, M_{m}、および署名装置 i_{l} , • · · ,i— {m- 1}が公開鍵 pk— {i— {1}}, · ··, pk—{i—{m-l}}を使って作成したメッセージ M—{1}， · ··, M_{ m-1}に対する署名文 U_{i_{m-1}}が署名装置 i_{m}に入力されたとき、署名装置 i_{m}がメ ッセージ M_{m}に署名する方法を、図 2、図 3を参照して説明する。
[0068] 署名装置 i_{m}は、まず入力手段 S1B101により、 Μ_{1},· ··, M_{m}、 pk_{i_{l}},- --, pk_{i_{ m}}、 sk_{i_{m}}、 u_{i_{m-l}}を読み込み、記憶媒体 S1B108に記憶する (S1F100)。ただし 、 m=lの場合は、 u_{i_{0}}=0が満たされているものとする。
[0069] 次に署名装置 i_{m}は、 u_{i_{m- 1}}、 M_{1}, · ··, M_{m- 1}、 pk_{i_{l}}, · ··, pkjijm- 1}}を検 証装置 i_{m}-2に送る。検証装置 i_{m}-2は、署名文 u_{i_{m_l}}の正当性を検証する (S1 B101,SlF102)oこの際、検証装置 i_{m}- 2は、 pkjijl}},-, pkjijm- 1}}を鍵正当性検証 装置 i_{m}-4に送る。鍵正当性検証装置 i_{m}-4は、鍵の正当性を検証する (S1B102,S1 F101)。ただし m=lの場合は u_{i_{0}}=0であることのみを確認する。
[0070] 安全性の観点カゝら言えば、上述の u_{i_{m-l}}の検証と鍵正当性検証とを行うことが 望ましいが、効率ィ匕を図るためにその何れか一方または双方の操作を省略してもよ い。
[0071] 次に署名装置 i_{m}は、 T_{m}計算手段 S1B103により、記憶媒体 S1B108から必要な データを読み込み、 T_{m} = M_{1}|卜 · · llMjmJllpkJiJl}}!卜 ΙΙρΙίΙίπι}}を計算する (S1F10 3)。 T_{m}計算手段 S1B103は、計算が終わったら記憶媒体 S1B108に T_{m}を書き込む
[0072] 次に署名装置 i_{m}は、排他的論理和手段 S1B104により、記憶媒体 S1B108から必 要なデータを読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果を記憶媒体 S1B 108に記憶する (S1F104)。ここで、 Hは入力と同じビット数のハッシュ値を出力するハツ シュ関数である。
[0073] 次に署名装置 i_{m}は、第一変換手段 S1B105により、署名装置 i_{m}に入力されたデ ータを記憶媒体 S1B108から読み込み、まず、 Uが n_{i_{m}}より小さいかどうかを判定す る (S1F105)。そして、 U< n_{i_{m}}であれば、署名装置 i_{m}は、第一変換手段 S1B105 により、 v= u djijm}}} mod n_{i_{m}}を計算し、計算結果を記憶媒体 S1B108に書き込 む (S1F106)。逆に U≥n_{i_{m}}であれば、署名装置 i_{m}は、第一変換手段 S1B105によ り、 v=uとし、計算結果を記憶媒体 S1B108に書き込む (S1F107)。
[0074] そして次に、署名装置 i_{m}は、全単射変換手段 S1B106により、記憶媒体 S1B108か ら必要なデータを読み込み、 v'=v + n_{i_{m}} mod 2 κ }を計算し、計算結果を記憶媒 体 S1B108に書き込む (S1F108)。
[0075] 次に署名装置 i_{m}は、第二変換手段 S1B107により、記憶媒体 S1B108から必要なデ ータを読み込み、 v'が n_{i_{m}}より小さ ヽかどうかを判定する (S1F109)。もし v' < n_{i_{m}} ならば、署名装置 i_{m}は、第二変換手段 S1B107により、 u_{i_{m}} = v'ldjijm}}} mod n_{ i_{m}}を計算し、計算結果を記憶媒体 S1B108に書き込む (S1F1010)。逆に、もし v'≥n_{ i_{m}}ならば、署名装置 i_{m}は、第二変換手段 S1B107により、 u_{i_{m}} = vを計算し、 計算結果を記憶媒体 S1B108に書き込む (S1F1011)。
[0076] そして最後に、署名装置 i_{m}は、出力手段 S1B109により、記憶媒体 S1B108から u_{i_ {m}}を読み込み、出力する (S1F1012)。
[0077] このように、署名装置 i_{m}は、入力された署名文 u_{i_{m- 1}}がモジュラス n_{i_{m}}を超 えるかどうかを判定し、超える場合には何もせず、超えない場合には RSA方式に準じ た署名を行う第 1操作を行い、この第 1操作の結果に対して、モジュラス n_{i_{m}}だけ大 き 、ほうに写像させる関数をかける第 2操作を行 、、この第 2操作の結果がモジュラス n_{i_{m}}を超えるかどうかを判定し、超える場合には何もせず、超えない場合には RSA 方式に準じた署名を行う第 3操作を行うものであり、署名文 u_{i_{m-l}}の値によっては R SA署名力 ¾度実施される冗長さはあるものの、署名値 u_{i_{m}}の値によって、施された 署名操作が一意に決定できるため、非特許文献 1におけるような制御ビットを付加す る必要がなくなる。
[0078] 次に、検証装置 i_{m}-2が署名文 ujm-l}を検証する方法を図 4、図 5を参照して説明 する。
[0079] 検証装置 i_{m}-2は、まず入力手段 V1B100により、公開鍵記憶装置 i_{m}-3から pk_{i_{ 1}}, · · · ,pk_{i_{m- 1}}を読み込み、さらにメッセージ M_{1}， · ··, M_{m-1}を読み込む (V1F10 0)。読み込んだデータは、入力手段 V1B100により記憶媒体 V1B1010に書き込まれる
[0080] 次に検証装置 i_{m}-2は、入力手段 V1B100により、 pk_{i_{l}},〜,pk_{i_{m-l}}を鍵検証 装置 i_{m}-4に送り、公開鍵 pk_{i_{l}},〜,pk_{i_{m-l}}の正当性を検証してもらう (V1B101, VlF101)o
[0081] 次に検証装置 i_{m}-2は、 1つ前の署名装置から最初の署名装置まで遡って順に検 証処理を行うために、まず、 j初期化手段 V1B102により、どの署名装置における署名 を検証しているかを管理する変数 jに m-1をセットする (V1F102)。
[0082] 次に検証装置 i_{m}-2は、 j判定手段 V1B103により、 j〉0かどうかを判定する (V1F103)
[0083] 以下、 j〉0の場合の検証装置 i_{m}-2の動作を説明する。 j〉0でな ヽ場合の動作につ いては後述する。
[0084] 次に検証装置 i_{m}-2は、第二変換手段 V1B104により、まず記憶媒体 V1B1010から 必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であるかどうかを判定する (V1F104)。
[0085] そして、もし u_{i_{j}Kn_{i_{j}}であれば、検証装置 i_{m}-2は、第二変換手段 V1B104によ り、 v'=u_{i_{j}He_{i_{j}}} mod n_{i_{j}}を計算し、計算結果を記憶媒体 V1B1010に書き込 む (V1F105)。
[0086] 逆に、もし u_{i_{j}Kn_{i_{j}}でなければ、検証装置 i_{m}-2は、第二変換手段 V1B104〖こ より、 v'=u_{i_{j}とし、計算結果を記憶媒体 V1B1010に書き込む (V1F106)。
[0087] 次に検証装置 i_{m}-2は、全単射計算手段 V1B105により、記憶媒体 V1B1010から必 要なデータを読み込み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、計算結果を記憶媒体 VI
B1010に書き込む (V1F107)。
[0088] 次に検証装置 i_{m}-2は、第一変換手段 V1B106により、記憶媒体 V1B1010から必要 なデータを読み込み、まず Vく n_{i_{j}}であるかどうかを判定する (V1F108)。
[0089] そして、もし Vく n_{i_{j}}であれば、検証装置 i_{m}-2は、第一変換手段 V1B106により、 U
=v e_{i_{j}}} mod n_{i_{j}}を計算し、計算結果を記憶媒体 V1B1010に書き込む (V1F109)
[0090] 他方、もし Vく n_{i_{j}}でなければ、検証装置 i_{m}-2は、第一変換手段 V1B106により、
U=vとし、計算結果を記憶媒体 V1B1010に書き込む (V1F1010)。
[0091] 次に検証装置 i_{m}-2は、 T_{j}計算手段 V1B107により、記憶媒体 V1B1010から必要 なデータを読み込み、 T_{j} = M_{1川… ||M_{j}||pk_{i_{l}川… ||pk_{i_{j}}を計算し、計算結果 を記憶媒体 V1B1010に書き込む (V1F1011)。
[0092] 検証装置 i_{m}-2は次に、 u計算手段 V1B108により、記憶媒体 V1B1010力 必要な データを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算結果を記憶媒体 V1B1010に 書き込む (V1F1012)。
[0093] そして次に検証装置 i_{m}-2は、 j減少手段 V1B109により、 j=j-lとする (V1F1013)。
[0094] そして再び検証装置 i_{m}-2は、 j判定手段 V1B103により、 j〉0かどうかを判定する (VI F103)。
[0095] もし j〉0であれば、検証装置 i_{m}-2は、ステップ V1F104以降の処理を行う。
[0096] もし j=0であれば、検証装置 i_{m}-2は、 u判定手段 V1B1011により、記憶媒体 V1B101
0から必要なデータを読み込み、 u=0であるかどうかを調べる (V1F1014)。
[0097] そして u=0であれば、検証装置 i_{m}-2は、 accept出力手段 V1B1012により、検証成 功を示す acceptを出力し (V1F1015)、そうでなければ、 reject出力手段 V1B1013により
、検証失敗を示す rejectを出力する (V1F1016)。 [0098] さて、図 5の点線で囲った部分の操作を x), g(x), h(x), φ (χ)とする。
すなわち、
f (χ) = x e_{i_{j}}} mod n_{i_{j}} if xく n— {i— {j}}
= x otherwise.
g (x) = x e_{i_{j}}} mod n_{i_{j}} if xく n— {i— {j}}
= x otherwise.
φ (x)= x + n_{i_{j}} mod 2 κ }
h(x)= §( φ (χ))
とする。
[0099] すると、図 3の点線で囲った部分の操作 Π- lKx), g -1} (x), h -1} (x), φ -1} (x)は 、それぞれ )， g(x), h(x), φ (x)の逆関数である。
[0100] 従って、本実施の形態における署名装置 i_{m}は、
Figure imgf000024_0001
φ -l}(f_{mF{- l}(H(T_{m})〇u_{i_{m-l}})》)なる計算式によって、署名文を作成していることになる。ま た、本実施の形態における検証装置 i_{m}-2は、 u_{i_{m-2}}=H(T_{m-l})0(f_{m-l}( (g_ {m-l}(u_{i_{m-l}}))》によって、 1つ前の署名装置の入力となった署名文を求
め、以下、同様の処理を最初の署名装置まで繰り返して入力の初期値を求め、求め た初期値が予め定められた初期値 (本実施の形態の場合は値 0)に一致するかどうか を調べていることになる。
[0101] 次に本実施の形態の効果を説明する。
[0102] 第 1の効果は、署名長が署名装置の数に依存しないことである。その理由は、署名 前のデータと、署名後にできるデータのビット数が不変であることによる。
[0103] 第 2の効果は、署名装置の順番を、署名のたびに変えることができることにある。そ の理由は、第 1の効果の場合と同じで署名前のデータと、署名後にできるデータのビ ット数が不変であることによる。この為、各署名装置への入力が、その署名装置が何 番目に署名を行うのかによらず一定であり、その為に何番目であっても同じ操作で署 名ができる。ただし、どの順番で署名が行われたのかを、何らかの形で検証装置に通 知する必要はある。
[0104] 第 3の効果は、署名装置と結託した攻撃者が、経路の途中で honestな署名装置を 通っている署名文を偽造できないことにある。その理由は、署名装置への入力 がい かなるものであっても、署名時に二回行う RSA計算の少なくとも一方で uが変化するか らである。
[0105] 第 4の効果は、システムの運用を始めた段階で署名装置の数 mがわ力つている必要 はなぐ署名装置の数 mは運用中に動的に変わっても支障なく適用できることである 。その理由は、署名装置の数が m+1台のときの署名手順は、署名装置の数が m台の ときの署名手順を行つた後に同様の署名操作をさらに 1回行うというものであり、署名 装置の数 mに署名の操作方法が依存しな!、からである。
[0106] なお、以上の第 1の実施の形態では、もっとも典型的な例である RSA関数を使って 説明したが、より一般に {Ο, ΐΗ κ }のある部分集合 Xが存在して、以下の条件 (1)ズ2)が 満たされるならば、第 1の実施の形態と同様に、署名者の人数に署名長が依存せず かつ安全な署名方式を実現できる。
(1) f,gがトラップドアつき一方向性置換で Xが fの定義域にも gの定義域にも含まれるも のであること。
(2) φ力 φも φ 1}も多項式時間で計算できる {Ο, ΙΠ κ }上の全単射であって、 {0, 1}"{ κ }\Χを Xに写すものであること。
ここで、トラップドアつき一方向性置換とは、以下の 4性質を満たす関数のことである。
1) ¾計算するのは容易。
2)トラップドア (秘密鍵ともいう）を知らない人には Π-1}を計算するのは困難。
3)トラップドアを知っている人には Π-1}を計算するのは容易。
4)全単射である。
[0107] さらに一般に {Ο, ΙΗ κ }のある部分集合 Xが存在して、以下の条件 (1)ズ2)が満たされ るならば、第 1の実施の形態と同様に、署名者の人数に署名長が依存せずかつ安全 な署名方式を実現できる。
(1) i¾トラップドアつき一方向性置換で Xカ^の定義域にふくまれるものであること。
(2)かつ hがトラップドアつき一方向性置換で {Ο, ΙΗ κ }\Χが hの定義域にふくまれるも のであること。
[0108] 『第 2の実施の形態』 図 6を参照すると、本発明の第 2の実施の形態は、署名装置 i_{l}，… {m}、検証装置 i — {1}- 2,· ··,ί— {m}- 2、公開鍵記憶装置 i— {1}- 3,· ··,ί— {m}- 3、鍵正当性検証装置 i— {1}- 4,· ··,ί— { m}-4、秘密鍵記憶装置 i— {1}-5, · · · ,i— {m}-5から構成される。
[0109] 図 7を参照すると、署名装置 i_{m}は、入力手段 S1B100、 T_{m}計算手段 S1B103、排 他的論理和計算手段 S1B104、第一変換手段 S1B105、全単射変換手段 S1B106、第 二変換手段 S1B107、記憶媒体 S1B108、出力手段 S1B109および wセット手段 S2B100 力 構成される。他の署名装置も署名装置 i_{m}と同様の構成を有する。
[0110] 図 9を参照すると、検証装置 i_{m}-2は、入力手段 V2B200、 T_{m-1}計算手段 V2B202 、 V"計算手段 V2B203、第二変換手段 V2B204、全単射変換手段 V2B205、第一変換 手段 V2B206、 u判定手段 V2B207、 accept出力手段 V2B208、 reject出力手段 V2B209 および記憶媒体 V2B2010から構成される。他の検証装置も検証装置 i_{m}-2と同様の 構成を有する。
[0111] 本実施の形態の概略を述べる。まず、署名装置 i_{l}に、署名装置 i_{l}の公開鍵秘 密鍵ペア、初期値 u_{i_{0}}、およびメッセージ M_{1}が入力される。署名装置 i_{l}は u_{i_{ 0}}を用いてメッセージ M_{1}に対する署名文 u_{i_{l}}を作成し、かつ、初期値 u_{i_{0}}を 補助情報 w_{i_{l}}として作成し、 u_{i_{l}}と w_{i_{l}}の組を出力する。次に、署名装置 i_{2} に、署名装置 i_{2}の公開鍵秘密鍵ペア、 u_{i_{l}}と w_{i_{l}}の組、およびメッセージ M_{2} が入力される。署名装置 i_{2}は u_{i_{l}}を用 V、てメッセージ M_{2}に対する署名文 u_{i_{2} }を作成し、かつ、 u_{i_{l}}を補助情報 w_{i_{2}}として作成し、 u_{i_{2}}と w_{i_{2}}の組を出力 する。以下順に署名装置 i_{j}に、署名装置 i_{j}の公開鍵秘密鍵ペア、直前の署名装 置が出力した署名文 u_{i_{j-l}}と補助情報 w_{i_{j-l}}、およびメッセージ M_{j}が入力され 、署名装置 i_{j}はこれら用いて署名文 u_{i_{j}}と補助情報 w_{i_{j}}の組を作成する。 u_{i_{j} }は、第 1の実施の形態と同様の署名文であり、署名装置 i_{l}がメッセージ M_{1}に署名 し、署名装置し{2}がメッセージ M_{2}に署名し、 ···、署名装置 i_{j}力 ツセージ M_{j}に署 名したことを表すデータである。
[0112] また、 w_{i_{j}}は、署名文 u_{i_{j}}の検証を簡易に行えるようにするための補助情報で あり、本実施の形態の場合、署名装置 i_{j}の入力となった署名文 u_{i_{j-l}}そのもので ある。各 jに対し、検証装置し {j}に署名装置 ί_{1},· ··,ί_¾の公開鍵とメッセージ Μ_{1},· ··， M_{j- 1}、および u_{i_{j- l}},w_{i_{j- 1}}が入力されると、検証装置 i_{j}は、 u_{i_{j- 1}}がメッセ ージ M_{1}， · · · ,M_{j-l}に対する、署名装置 i_{l}， · · · ,i_{j-l}の公開鍵を使って作成された 署名文であるかどうかを、補助情報 W_{i_{j-1}}を活用して検証する。
[0113] 本実施の形態のシステムの目標は、第 1の実施の形態と同じぐ署名文 u_{i_{m}}、す なわち署名装置 i_{l}カ^ツセージ M_{1}に署名し、署名装置 i_{2}がメッセージ M_{2}〖こ署 名し、…、署名装置 i_{m}がメッセージ M_{m}に署名したことを表すデータを作成するこ とである。
[0114] なお、第 1の実施の形態と同様に、本実施の形態のシステムにおいてもその運用を 始めた段階で署名装置の数 mがわ力つている必要はない。署名装置の数 mは運用中 に動的に変わってもよい。また、署名装置 i_{l}, ,i_{m}の動作は全て同様である。検 証装置、公開鍵記憶装置、鍵正当性検証装置、秘密鍵記憶装置も全て基本的に同 じ動作を行う。
[0115] 次に本実施の形態の詳細を、第 1の実施の形態との相違点を中心に説明する。
[0116] 署名装置 i_{j}の公開鍵 pk_{i}、秘密鍵 sk_{i}は、第 1の実施の形態と同様に作成され、 各 j=l ,… ,mに対し、秘密鍵記憶装置 i_{j}-5は秘密鍵 sk_{i_{j}}を記憶し、さらに公開鍵記 憶装置 i_{j}-3は、公開鍵 pk_{l}， · · · ,pk_{m}を記憶する。
[0117] 鍵正当性検証装置の動作は第 1の実施の形態と同じである。
[0118] メッセージ M_{1}， · ··, M_{m}、および署名装置 i_{l} , · · · ,i_{m- 1}が公開鍵 pk_{i_{l}}， · ··, p k_{i_{m-l}}を使って作成した、メッセージ M_{1}， · ··, M_{m-1}に対する署名文 u_{i_{m-l}} と補助情報 w_{i_{m- 1}}が署名装置 i_{m}に入力されたときの、署名装置 i_{m}がメッセ一 ジ M_{m}に署名する方法は、補助情報を作成する手順が追加されている点で第 1の実 施の形態と相違し、それ以外は第 1の実施の形態と同じである。これを図 7、図 8を参 照して説明すると、本実施の形態の場合、署名装置 i_{m}は、ステップ S1F102の処理 に続けて、 wセット手段 S2B100により、 w_{i_{m}}=u_{i_{m-l}}を計算し、計算結果を記憶 媒体 S1B108に書き込む (S2F100)。記録媒体 S1B108に書き込まれた補助情報 w_{i_{m}} は、出力手段 S1B109により、第 1の実施の形態と同様の手順で作成されて記録媒体 S 1B108に書き込まれている署名文 u_{i_{m}}と一緒に読み出され、出力される (S1F1012') [0119] 次に、検証装置 i_{m}-2が署名文 u_{m-l}を検証する方法を図 9および図 10を参照し て説明する。
[0120] 検証装置 i_{m}-2は、まず入力手段 V2B200により、公開鍵記憶装置 i_{m}-3から pk_{i_{ l}},〜,pk_{i_{m-l}}を読み込み、さらにメッセージ Μ_{1}, · · ·， M_{m-1}を読み込み、記憶 媒体 V2B2010に保存する (V2F200)。
[0121] 次に検証装置 i_{m}-2は、入力手段 V2B200により、 pk_{i_{l}},〜,pk_{i_{m-l}}を鍵検証 装置 i_{m}-4に送り、公開鍵 pk_{i_{l}},〜,pk_{i_{m-l}}の正当性を検証してもらう (V2F201)
[0122] 次に検証装置 i_{m}-2は、 T_{m-1}計算手段 V2B202により、必要なデータを記憶媒体 V2B2010から読み込み、 T_{m-1} = M_{1川… ||M_{m- l}||pk_{i_{l}川… ||pk_{i_{m- 1}}を計算 し、計算結果の T_{m-1}を記憶媒体 V2B2010に保存する（V2F202)。
[0123] 次に検証装置 i_{m}-2は、 V"計算手段 V2B203により、必要なデータを記憶媒体 V2B 2010から読み込み、 v"=H(T_{m- l})〇u_{i_{m-l}}を計算し、計算結果の v"を記憶媒体 V2B2010に保存する (V2F203)。
[0124] 次に検証装置 i_{m}-2は、第二変換手段 V2B204により、必要なデータを記憶媒体 V 2B2010から読み込み、 V"く n_{i_{m- 1}}であるかどうかを判定する (V2F204)。もし V"く n_{i_ {m-1}}であれば、検証装置 i_{m}-2は、第二変換手段 V2B204により、 v'=v" e_{i_{m-l}}} mod n_{i_{m- 1}}を計算し、計算結果の v'を記憶媒体 V2B2010に保存する (V2F205)。 他方 V"く n_{i_{m-l}}でなければ、検証装置 i_{m}-2は、 v =v "とし、計算結果の v'を記憶 媒体 V2B2010に保存する (V2F206)。
[0125] 次に検証装置 i_{m}-2は、全単射変換手段 V2B205により、必要なデータを記憶媒体 V2B2010から読み込み、 ν=ν' - n_{i_{m-l}} mod 2 κ }を計算し、計算結果の νを記憶 媒体 V2B2010に保存する (V2F207)。
[0126] 次に検証装置 i_{m}-2は、第一変換手段 V2B206により、必要なデータを記憶媒体 V 2B2010から読み込み、 Vく n_{i_{m- 1}}であるかどうかを判定する (V2F208)。もし v〈n_{i_{m -1}}であれば、検証装置 i_{m}-2は、第一変換手段 V2B206により、 u _{i_{m-2}} = v e_{i_{ m-1}}} mod n_{i_{m-l}}}を計算し、計算結果の u _{i_{m-2}}を記憶媒体 V2B2010に保存 する (V2F209)。他方、もし u_{i_{m-2}}〈n_{i_{m-l}}でなければ、検証装置 i_{m}-2は u _{i_{ m-l}}}=vとし、計算結果の u _{i_{m- 2}}を記憶媒体 V2B2010に保存する (V2F2010)。
[0127] 次に検証装置 i_{m}-2は、 u判定手段 V2B2011により、必要なデータを記憶媒体 V2B 2010から読み込み、 u_{i_{m-2}}} =w_{i_{m- 1}}であるかどうかを調べる (V2F2011)。もし u_{ i_{m-2}}} =w _{i_{m- 1}}であれば、検証装置 i_{m}-2は、 accept出力手段 V2B208により、 a cceptを出力し (V2F2012)、そうでなければ、 reject出力手段 V2B209により、 rejectを出 力する (V2F2013)。
[0128] 次に本実施の形態の効果を説明する。
[0129] 第 1の効果は、署名長が署名装置の数に依存しないことである。その理由は、署名 前のデータと、署名後にできるデータのビット数が不変であることによる。ただし、第 1 の実施の形態と比較すると、補助情報の分だけデータ長は長くなる。
[0130] 第 2の効果は、第 1の実施の形態に比べて検証計算に力かる計算量を削減すること ができることである。その理由は、第 1の実施の形態では、最終的に初期値を求める 必要があるため既に署名を行った署名装置の数に比例した検証計算が必要なのに 対し、本実施の形態では、直前の署名装置の入力となった署名文が補助情報として 伝達されているため、 1署名装置分の検証計算を行えばよいからである。ただし、本 実施の形態は、 1つ前の署名装置が信頼できるという前提が必要であるため、そのよ うな前提なしに安全性を証明できる第 1の実施の形態よりは安全性は低くなる。
[0131] その他、第 1の実施の形態と同様の効果が奏される。
[0132] なお、本実施の形態では、署名文 u_{i_{j}}と組になる補助情報 w_{i_{j}}として、署名装 置 i_{j}の入力となった署名文 u_{i_{j-l}}そのものとしたが、 hを入力と同じビット数のハツ シュ値を出力する所定のハッシュ関数とし、 u_{i_{j-l}}のハッシュ値 h(u_{i_{j-l}})を補助 情報 w_{i_{j}}としてもよい。また、本実施の形態に対しても第 1の実施の形態と同様の 付加変更が可能である。
[0133] 以上本発明の実施の形態について説明したが、本発明は以上の実施の形態にの み限定されず、その他各種の付加変更が可能である。また、本発明の署名装置およ び検証装置は、その有する機能をノヽードウエア的に実現することは勿論、コンビユー タとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ 等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時な どにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコ ンピュータを前述した各実施の形態における署名装置および検証装置として機能さ せる。

Claims

請求の範囲
[1] 初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文、 メッセージ、および自署名装置の秘密鍵を入力とし、入力と同じ長さの署名文を出力 する署名装置における署名方法であって、前記出力した署名文が、その前記出力し た署名文の作成にかかわった署名装置が各々の署名装置に入力された前記メッセ ージに署名したことを示すものであることを特徴とする署名方法。
[2] 請求項 1に記載された署名方法において、署名文を計算する操作が第 1および第 2 の 2つのステップを持ち、前記第 1ステップ (Π-1}の部分の操作)の計算にはトラップド ァつき一方向性置換の逆関数を用い、前記第 2ステップ 0 {-1}の部分の操作)の計 算には、前記第 1ステップのものと同じもしくは異なるトラップドアつき一方向性置換の 逆関数を用い、前記第 1ステップが終了したら計算結果を記憶媒体に記憶し、前記 第 2ステップ開始時には必要なデータを前記記憶媒体力 読み出し、前記第 2ステツ プが終了したら計算結果を前記記憶媒体に記憶することを特徴とする署名方法。
[3] 請求項 2に記載された署名方法において、前記第 1ステップでは、前記第 1ステップ への入力がもし前記トラップドアつき一方向性置換の値域の元であればその前記トラ ップドアつき一方向性置換の逆関数で前記入力を写像し、そうでなければ何もしな!、 というものであり、前記第 2ステップへの入力がもし前記トラップドアつき一方向性置換 の値域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を 写像し、そうでなければ何もしな 、と 、うものであることを特徴とする署名方法。
[4] 請求項 3に記載された署名方法において、前記第 2ステップで用いる前記トラップド ァつき一方向性置換の計算がさらに第 1および第 2のサブステップ力 なり、前記第 1 サブステップ（ φ -1}の部分の操作)では、署名文全体の空間上の全単射を計算し、 その全単射が多項式時間で計算でき、し力もその前記全単射の逆関数も多項式時 間で計算できるものであり、前記第 2サブステップ (g -1}の部分の操作)ではトラップド ァつき一方向性置換の逆関数を用い、もし前記トラップドアつき一方向性置換の値 域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を写像 し、そうでなければ何もしないというものであり、前記第 1サブステップおよび前記第 2 サブステップの開始時には必要なデータを前記記憶媒体力 読み込み、前記第 1サ ブステップおよび前記第 2サブステップの終了時には計算結果を前記記憶媒体に書 き込むことを特徴とする署名方法。
[5] 請求項 4に記載された署名方法にお!、て、前記第 1ステップで使用する前記トラップ ドアつき一方向性置換と、前記第 2ステップの前記第 2サブステップで使用する前記ト ラップドアつき一方向性置換とが RSA関数であることを特徴とする署名方法。
[6] 請求項 5に記載された署名方法において、前記第 2ステップの前記第 1サブステップ で使用する前記全単射が、 φ GO = X - n_{i_{m}} mod 2 κ }とかけ、前記 n_{i_{m}}が署名 装置 i_{m}の公開鍵の一部である RSAモジュラスであり、前記 κがセキュリティ 'パラメ ータであることを特徴とする署名方法。
[7] 請求項 6に記載された署名方法にお!、て、前記第 1ステップの前に T_{m}計算ステツ プがあり、前記 T_{m}計算ステップでは、 T_{m} = M_{1}| I · · · I |M_{m}| |pk_{i_{l}}| | · · · | |pk_{i_{m}} を計算し、各 jに対し前記 Μ_{1}, · · ·， M_{j}が潘目の署名装置に入力されたメッセージ であり、前記 pk_{i_{j}}が署名装置し {j}の公開鍵であることを特徴とする署名方法。
[8] 請求項 7に記載された署名方法で、前記第 1ステップの前に排他的論理和計算ステ ップがあり、前記排他的論理和計算ステップでは、 U=H(T_{m})〇u_{i_{m-l}}を計算し、 前記 Hがハッシュ関数で、前記 u_{i_{m- 1}}が前記入力された署名文であり、〇が排他 的論理和であることを特徴とする署名方法。
[9] 請求項 8に記載された署名方法で、前記第 1ステップより前に鍵正当性検証ステツ プがあり、前記鍵正当性検証ステップでは pk_{i_{l}}， · · · , pk_{i_{m-l}}が全て異なること を確認する力 ただし m=lの場合は何も確認しな 、ステップであることを特徴とする署 名方法。
[10] 請求項 9に記載された署名方法で、前記第 1ステップより前に、入力の署名文を検 証する署名文検証ステップがあることを特徴とする署名方法。
[11] 請求項 8に記載された署名方法で、前記第 1ステップより前に、 pkjijl}}, - , pk_{i_{m
-1}}が全て異なることを確認する鍵正当性検証ステップと、入力の署名文を検証する 署名文検証ステップとがあることを特徴とする署名方法。
[12] 請求項 1ないし 11の何れか 1項に記載された署名方法において、入力の初期値もし くは署名文またはそれらのハッシュ値を補助情報として作成し前記記憶媒体に書き 込むステップを含み、前記補助情報と署名文とを組にして出力することを特徴とする 署名方法。
[13] 入力手段が、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成 した署名文 u_{i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1} を入力し、記憶媒体に保存するステップ、
T_{m}計算手段が、前記記憶媒体および公開鍵記憶装置から必要なデータを読み 込み、 pk_{i_{j}}を署名装置し {j}の公開鍵、 IIをビット列同士の連結とするとき、 T_{m} = M_ {1川… ||M_{m}||pk_{i_{l}}|卜 を計算し、計算結果を前記記憶媒体に保存する ステップ、
排他的論理和計算手段が、 Hをハッシュ関数、〇を排他的論理和とするとき、前記 記憶媒体から必要なデータを読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果 を前記記憶媒体に保存するステップ、
第一変換手段が、前記記憶媒体から必要なデータを読み込み、 n_{i_{m}}を自署名 装置の RSAモジュラスとするとき、 Uく n_{i_{m}}であれば、 v= u djijm}}} mod n_{i_{m}}を 計算し、それ以外であれば、 v=Uを計算し、計算結果を前記記憶媒体に保存するス テツプ、
全単射変換手段が、前記記憶媒体から必要なデータを読み込み、 Kをセキュリティ 'パラメータとするとき、 ν'=ν + n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶媒 体に保存するステップ、
第二変換手段が、前記記憶媒体から必要なデータを読み込み、 V < n_{i_{m}}ならば 、 u_{i_{m}} = v' djijm}}} mod n_{i_{m}}を計算し、それ以外ならば、 u_{i_{m}} = vを計算し 、計算結果を前記記憶媒体に保存するステップ、
出力手段が、前記記憶媒体力 u_{i_{m}}を読み込み、署名文として出力するステツ プ、
を含むことを特徴とする署名方法。
[14] 請求項 13に記載される署名方法にお!ヽて、 wセット手段が、 w_{i_{m}}=u_{i_{m-l}}、ま たは、 hをハッシュ関数としたとき、 w_{i_{m}}=h(u_{i_{m-l}})を計算し、計算結果を前記記 憶媒体に保存するステップを含み、前記計算した w_{i_{m}}を補助情報として、前記作 成した署名文 u_{i_{m}}と組にして出力することを特徴とする署名方法。
[15] 複数の署名装置が順々に署名操作を行って作成した署名文 uが正当であるかどう かを検証する検証装置における検証方法において、検証を通過するのは、署名文 u 力 前記出力した署名文がその前記出力した署名文の作成にかかわった署名装置 が各々の署名装置に入力された前記メッセージに署名したときおよびそのときのみで あり、前記署名文 uのビット長が前記署名文 uを計算するのにかかわった前記署名装 置の数に依存しない定数であることを特徴とする検証方法。
[16] 複数の署名装置が順々に署名操作を行って作成した署名文 uが正当であるかどう かを検証する検証装置における検証方法において、検証を通過するのは、署名文 u を作成した署名装置が正当な方法で署名文 uを作成したときおよびそのときのみであ り、前記署名文 uのビット長が前記署名文 uを計算するのにかかわった前記署名装置 の数に依存しない定数であり、し力も前記署名文 uの検証は、前記複数の署名装置 のうち最後の 1台が署名操作を施す前のデータである補助情報 wを使って行うことを 特徴とする検証方法。
[17] 請求項 15または 16に記載された検証方法において、署名文を検証する操作が第 1 および第 2の 2つのステップがあり、前記第 1ステップ (hの部分の操作)の計算にはトラ ップドアつき一方向性置換を用い、前記第 2ステップ (fの部分の操作)の計算には、 前記第 1ステップのものと同じもしくは異なるトラップドアつき一方向性置換を用い、前 記第 1ステップおよび第 2ステップを開始する際、記憶媒体力 必要なデータを読み 込み、前記第 1ステップおよび第 2ステップを終了する際、前記記憶媒体に計算結果 を書き込むことを特徴とする検証方法。
[18] 請求項 17に記載された検証方法にお 、て、前記第 1ステップでは、前記第 1ステツ プへの入力がもし前記トラップドアつき一方向性置換の定義域の元であればその前 記トラップドアつき一方向性置換で前記入力を写像し、そうでなければ何もしな 、も のであり、前記第 2ステップへの入力がもし前記トラップドアつき一方向性置換の定義 域の元であればその前記トラップドアつき一方向性置換で前記入力を写像し、そうで なければ何もしないものであることを特徴とする検証方法。
[19] 請求項 18に記載された検証方法にぉ 、て、前記第 1ステップで用いる前記トラップ ドアつき一方向性置換の計算がさらに第 1および第 2の 2つのサブステップ力 なり、 前記第 1サブステップ (gの部分の操作)ではトラップドアつき一方向性置換の関数を用 V、、もし前記トラップドアつき一方向性置換の値域の元であればその前記トラップドア つき一方向性置換の関数で入力を写像し、そうでなければ何もしないというものであ り、前記第 2サブステップ（ φの部分の操作)では、署名文全体の空間上の全単射を 計算し、その全単射が多項式時間で計算でき、しかもその前記全単射の逆関数も多 項式時間で計算できるものであり、前記第 1サブステップおよび前記第 2サブステップ の開始時には必要なデータを前記記憶媒体力 読み込み、前記第 1サブステップお よび前記第 2サブステップの終了時には計算結果を前記記憶媒体に書き込むことを 特徴とする検証方法。
[20] 請求項 19に記載された検証方法において、前記第 1ステップの前記第 1サブステツ プで使用する前記トラップドアつき一方向性置換と、前記第 2ステップで使用する前 記トラップドアつき一方向性置換とが RSA関数であることを特徴とする検証方法。
[21] 請求項 20に記載された検証方法において、前記第 1ステップの前記第 2サブステツ プで使用する前記全単射が、 φ (X) = X + n_i_{m} mod 2 κ }とかけ、前記 n_{i_{m}}が署 名装置 i_{m}の公開鍵の一部である RSAモジュラスであり、前記 κがセキュリティ 'パラ メータであることを特徴とする検証方法。
[22] 請求項 21に記載された検証方法にお ヽて、前記第 2ステップの後に T_{j}計算ステツ プがあり、前記 Tjj}計算ステップでは、 T_{j} = M_{1}|卜 lMJ pldiJl}川… ||pk_{i_{j}}を計 算するものであり、ここで、各 jに対し前記 M_{1}， M_{j}が潘目の署名装置に入力さ れたメッセージであり、前記 pk_{i_{j}}が署名装置 i_{j}の公開鍵であることを特徴とする検 証方法。
[23] 請求項 22に記載された検証方法にお!、て、前記 T_{j}計算ステップの後に、 Hをハツ シュ関数、 Uを第 2ステップの計算結果とするとき、前記記憶媒体から必要なデータを 読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算結果を前記記憶媒体に保存する u計 算ステップがあることを特徴とする検証方法。
[24] 請求項 23に記載された検証方法にお 、て、前記第 1ステップ、前記第 2ステップ、前 記 T_{j}計算ステップおよび前記 u計算ステップを、 j=m-l ,… , 1に対して繰り返すことを 特徴とする検証方法。
[25] 請求項 24に記載された検証方法にぉ 、て、前記第 1ステップ、前記第 2ステップ、前 記 T_{j}計算ステップおよび前記 u計算ステップを、 j=m-l,… , 1に対して繰り返す前に、 鍵正当性検証ステップがあり、前記鍵正当性検証ステップでは、 pkjijl}},-, pkjijm -1}}が全て異なることを確認する力 ただし m=lの場合は何も確認しな ヽものであるこ とを特徴とする検証方法。
[26] 請求項 25に記載された検証方法にお 、て、前記第 1ステップ、前記第 2ステップ、前 記 T_{j}計算ステップおよび前記 u計算ステップを、 j=m-l,… , 1に対して繰り返した後に 、検証結果として初期値が得られたかどうかを判定する u判定ステップがあることを特 徴とする検証方法。
[27] 請求項 21に記載された検証方法にぉ 、て、前記第 1ステップの前に T_{m- 1}計算ス テツプおよび V"計算ステップがあり、前記 T_{m-1}計算ステップでは、 T_{m-1} = M_{1}|| •••||M_{m-l}||pk_{i_{l}}| '||pk_{i_{m-l}}を計算するものであり、ここで、 Μ_{1},· ··， M_{m- 1} 力 Sl,〜,m-1番目の署名装置に入力されたメッセージであり、前記 pk_{i_{j}}が署名装 置 i_{j}の公開鍵であり、前記 V"計算ステップでは、 v"=H(T_{m- l})〇u_{i_{m-l}}を計算 するものであり、かつ、前記第 1ステップは前記 V"を入力とし、かつ、前記第 2ステップ の後に、前記第 2ステップの計算結果が前記補助情報に一致するか判定する u判定 ステップがあることを特徴とする検証方法。
[28] 入力手段が、他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{ i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1},· ··， M_{m-1}、それらの署名 装置の公開鍵 pk_{i_{l}},"',pk_{i_{m- 1}}を入力し、記憶媒体に保存するステップ、 j初期化手段が、変数 jに m-1をセットするステップ、
第二変換手段が、前記記憶媒体から必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であ れば、 v'=u_{i_{j}He_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計算し 、計算結果を前記記憶媒体に保存するステップ、
全単射計算手段が、前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m}} m od 2 K }を計算し、計算結果を前記記憶媒体に保存するステップ、
第一変換手段が、前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{j}}であれば 、 U=v e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 U=vを計算し、計算結果を 前記記憶媒体に保存するステップ、
前記変数 jが 0になるまで、前記変数 jを- 1する毎に前記第二変換手段、前記全単射 計算手段、前記第一変換手段による前記ステップを繰り返すステップ、
T_{j}計算手段が、前記記憶媒体から必要なデータを読み込み、 T_{j} = Μ_{1}|| · · · ||Μ_{ j}||pk_{i_{l}川… ||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するステップ、 u計算手段が、前記記憶媒体から必要なデータを読み込み、 u_{i_{j-l}}=H(T_{j})OU を計算し、計算結果を前記記憶媒体に保存するステップ、
u判定手段が、前記記憶媒体から必要なデータを読み込み、 u=予め定められた初 期値であるかどうかを判定するステップ、
出力手段が、 u=予め定められた初期値であれば、検証成功を示す通知を出力し、 そうでなければ、検証失敗を示す通知を出力するステップ、
を含むことを特徴とする検証方法。
入力手段が、他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{ i_{m-l}}、 1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報 v _{i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}、それらの署 名装置の公開鍵 pk_{i_{l}}， · · · ,pk_{i_{m- 1}}を入力し、記憶媒体に保存するステップ、
T_{m-1}計算手段が、前記記憶媒体から必要なデータを読み込み、 T_{m-1} = M_{1}| 卜 · I |M_{m-l}| |pk_{i_{l}川… I |pk_{i_{m-l}}を計算し、計算結果を前記記憶媒体に保存す るステップ、
V"計算手段が、前記記憶媒体から必要なデータを読み込み、 v"=H(T_{m-l})Ou_{i_ {m-1}}を計算し、計算結果を前記記憶媒体に保存するステップ、
第二変換手段が、前記記憶媒体から必要なデータを読み込み、 V"く n_{i_{m-l}}であ れば、 v'=v" e_{i_{m-l}}} mod n_{i_{m_l}}を計算し、それ以外であれば、 v'=v "を計算し 、計算結果を前記記憶媒体に保存するステップ、
全単射計算手段が、前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を計算し、計算結果を前記記憶媒体に保存するステップ、
第一変換手段が、前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{m-l}}であ れば、 u_{i_{m-2}}=v e_{i_{m-l}}} mod n_{i_{m- 1}}を計算し、それ以外であれば、 u_{i_{m_ 2}}=vを計算し、計算結果を前記記憶媒体に保存するステップ、
u判定手段が、前記記憶媒体から必要なデータを読み込み、 u_{i_{m-2}}またはその ハッシュ値が前記補助情報 v_{i_{m-l}}と一致するかどうかを判定するステップ、 出力手段が、 u_{i_{m-2}}またはそのハッシュ値が前記補助情報 V_{i_{m-1}}と一致すれ ば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力す るステップ、
を含むことを特徴とする検証方法。
読み書き可能な記憶媒体と、
初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文 u_{ i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}を入力し、前記 記憶媒体に保存する入力手段と、
前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、 pk_{i_{j}}を署 名装置 i_{j}の公開鍵、 IIをビット列同士の連結とするとき、 T_{m} = M_{l}|| - ||M_{m}||pk_{i_ {I}}|| Ilpk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存する T_{m}計算手段と、
Hをハッシュ関数、〇を排他的論理和とするとき、前記記憶媒体から必要なデータ を読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果を前記記憶媒体に保存す る排他的論理和計算手段と、
前記記憶媒体から必要なデータを読み込み、 n_{i_{m}}を自署名装置の RSAモジュラ スとするとき、 U< n_{i_{m}}であれば、 v= uldjijm}}} mod n_{i_{m}}を計算し、それ以外で あれば、 v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、 前記記憶媒体から必要なデータを読み込み、 κをセキュリティ 'パラメータとするとき 、 v'=v + n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶媒体に保存する全単射 変換手段と、
前記記憶媒体から必要なデータを読み込み、 V < n_{i_{m}}ならば、 u_{i_{m}} = v' d_{i_ {m}}} mod n_{i_{m}}を計算し、それ以外ならば、 u_{i_{m}} = vを計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、
前記記憶媒体から u_{i_{m}}を読み込み、署名文として出力する出力手段と、 を含むことを特徴とする署名装置。
[31] 請求項 30に記載される署名装置にぉ 、て、 w_{i_{m}}=u_{i_{m-l}}、または、 hをハツシ ュ関数としたとき、 w_{i_{m}}=h(U_{i_{m-l}})を計算し、計算結果を前記記憶媒体に保存 する wセット手段を含み、前記計算した w_{i_{m}}を補助情報として、前記作成した署名 文 u_{i_{m}}と組にして出力するものであることを特徴とする署名装置。
[32] 読み書き可能な記録媒体と、
他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それ らの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}、それらの署名装置の公開 鍵 pk_{i_{l}}, ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、
変数 jに m-1をセットする j初期化手段と、
前記記憶媒体から必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であれば、 v'=u_{i_{j}} e_ {i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、 計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{j}}であれば、 U=v e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 U=vを計算し、計算結果を前記記憶媒体に保 存する第一変換手段と、
前記変数 jが 0になるまで、前記変数 jを- 1する毎に前記第二変換手段、前記全単射 計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記 憶媒体から必要なデータを読み込み、 T_{j} = M_{1川… ||M_{j}||pk_{i_{l}川… ||pk_{i_{j}}を 計算し、計算結果を前記記憶媒体に保存する T_{j}計算手段と、
前記記憶媒体から必要なデータを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算 結果を前記記憶媒体に保存する u計算手段と、
前記記憶媒体から必要なデータを読み込み、 u=予め定められた初期値であるかど うかを判定する u判定手段と、
u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなけれ ば、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする検証装置 [33] 読み書き可能な記録媒体と、
他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、 1つ 前の署名装置が入力した署名文またはそのハッシュ値である補助情報 v_{i_{m-l}}、そ れらの署名装置に入力されたメッセージ Μ_{1},· ··， M_{m-1}、それらの署名装置の公 開鍵 Pk_{i_{l}}, ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、
前記記憶媒体から必要なデータを読み込み、 T_{m-1} = M_{l}||-||M_{m-l}||pk_{i_{l}} I卜 - llpkjijm-l}}を計算し、計算結果を前記記憶媒体に保存する T_{m-1}計算手段と、 前記記憶媒体から必要なデータを読み込み、 V '=H(T_{m-l})〇u_{i_{m-l}}を計算し、 計算結果を前記記憶媒体に保存する V"計算手段と、
前記記憶媒体から必要なデータを読み込み、 V"く n_{i_{m-l}}であれば、 v =v" e_{i_{ m-1}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 v =v "を計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を計算し 、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{m-l}}であれば、 u_{i_{m-2}}=v~{ e_{i_{m-l}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 u_{i_{m-2}}=vを計算し、計算 結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体力 必要なデータを読み込み、 u_{i_{m-2}ほたはそのハッシュ値が前 記補助情報 V_{i_{m-1}}と一致するかどうかを判定する u判定手段と、
u_{i_{m-2}}またはそのハッシュ値が前記補助情報 V_{i_{m-1}}と一致すれば、検証成功 を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段と を備えたことを特徴とする検証装置。
[34] 読み書き可能な記憶媒体を有するコンピュータを、
初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文 u_{ i_{m-l}}、それらの署名装置に入力されたメッセージ Μ_{1},· ··， M_{m-1}を入力し、前記 記憶媒体に保存する入力手段と、
前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、 pk_{i_{j}}を署 名装置 i_{j}の公開鍵、 IIをビット列同士の連結とするとき、 T_{m} = M_{l}|| - ||M_{m}||pk_{i_ {l}}|h llpk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存する T_{m}計算手段と、
Hをハッシュ関数、〇を排他的論理和とするとき、前記記憶媒体から必要なデータ を読み込み、 U=H(T_{m})〇u_{i_{m-l}}を計算し、計算結果を前記記憶媒体に保存す る排他的論理和計算手段と、
前記記憶媒体から必要なデータを読み込み、 n_{i_{m}}を自署名装置の RSAモジュラ スとするとき、 U< n_{i_{m}}であれば、 v= u djijm}}} mod n_{i_{m}}を計算し、それ以外で あれば、 v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、 前記記憶媒体から必要なデータを読み込み、 κをセキュリティ 'パラメータとするとき 、 v'=v + n_{i_{m}} mod 2 κ }を計算し、計算結果を前記記憶媒体に保存する全単射 変換手段と、
前記記憶媒体から必要なデータを読み込み、 V < n_{i_{m}}ならば、 u_{i_{m}} = v' d_{i_ {m}}} mod n_{i_{m}}を計算し、それ以外ならば、 u_{i_{m}} = vを計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、
前記記憶媒体から u_{i_{m}}を読み込み、署名文として出力する出力手段と、 して機能させるためのプログラム。
[35] 請求項 34に記載されるプログラムにお 、て、前記コンピュータをさらに、 w_{i_{m}}=u_{i _{m-l}}、または、 hをハッシュ関数としたとき、 w_{i_{m}}=h(U_{i_{m-l}})を計算し、計算結 果を前記記憶媒体に保存する wセット手段、として機能させ、かつ、前記計算した w_{i_ {m}}を補助情報として、前記作成した署名文 u_{i_{m}}と組にして出力するためのプログ ラム。
[36] 読み書き可能な記録媒体を有するコンピュータを、
他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、それ らの署名装置に入力されたメッセージ Μ_{1}, · · ·， M_{m-1}、それらの署名装置の公開 鍵 pk_{i_{l}}, ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、
変数 jに m-1をセットする j初期化手段と、
前記記憶媒体から必要なデータを読み込み、 u_{i_{j}Kn_{i_{j}}であれば、 v'=u_{i_{j}} e_ {i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 v'=u_{i_{j}を計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m}} mod 2 κ }を計算し、 計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{j}}であれば、 U=v e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、 U=vを計算し、計算結果を前記記憶媒体に保 存する第一変換手段と、
前記変数 jが 0になるまで、前記変数 jを- 1する毎に前記第二変換手段、前記全単射 計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記 憶媒体から必要なデータを読み込み、 T_{j} = M_{1川… ||M_{j}||pk_{i_{l}川… ||pk_{i_{j}}を 計算し、計算結果を前記記憶媒体に保存する T_{j}計算手段と、
前記記憶媒体から必要なデータを読み込み、 u_{i_{j-l}}=H(T_{j})〇Uを計算し、計算 結果を前記記憶媒体に保存する u計算手段と、
前記記憶媒体から必要なデータを読み込み、 u=予め定められた初期値であるかど うかを判定する u判定手段と、
u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなけれ ば、検証失敗を示す通知を出力する出力手段として機能させるためのプログラム。 読み書き可能な記録媒体を有するコンピュータを、
他の 1以上の署名装置が順々に署名操作を行って作成した署名文 u_{i_{m-l}}、 1つ 前の署名装置が入力した署名文またはそのハッシュ値である補助情報 v_{i_{m-l}}、そ れらの署名装置に入力されたメッセージ Μ_{1},· ··， M_{m-1}、それらの署名装置の公 開鍵 Pk_{i_{l}}, ,pk_{i_{m-l}}を入力し、記憶媒体に保存する入力手段と、
前記記憶媒体から必要なデータを読み込み、 T_{m-1} = M_{l}||-||M_{m-l}||pk_{i_{l}} I卜 - llpkjijm-l}}を計算し、計算結果を前記記憶媒体に保存する T_{m-1}計算手段と、 前記記憶媒体から必要なデータを読み込み、 V '=H(T_{m-l})〇u_{i_{m-l}}を計算し、 計算結果を前記記憶媒体に保存する V"計算手段と、
前記記憶媒体から必要なデータを読み込み、 V"く n_{i_{m-l}}であれば、 v =v" e_{i_{ m-1}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 v =v "を計算し、計算結果を前記 記憶媒体に保存する第二変換手段と、 前記記憶媒体から必要なデータを読み込み、 v=v'- n_{i_{m-l}} mod 2 κ }を計算し 、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、 Vく n_{i_{m-l}}であれば、 u_{i_{m-2}}=v~{ e_{i_{m-l}}} mod n_{i_{m-l}}を計算し、それ以外であれば、 u_{i_{m-2}}=vを計算し、計算 結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体力 必要なデータを読み込み、 u_{i_{m-2}ほたはそのハッシュ値が前 記補助情報 V_{i_{m-1}}と一致するかどうかを判定する u判定手段と、
u_{i_{m-2}}またはそのハッシュ値が前記補助情報 V_{i_{m-1}}と一致すれば、検証成功 を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段と して機能させるためのプログラム。
[38] 初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文、 前記署名装置に入力されたメッセージが入力されると、前記メッセージと自装置の公 開鍵及び既に署名した署名装置の公開鍵とを連結した結果を計算し、前記連結結 果のハッシュ値と前記署名文との排他的論理和を導出する手段を少なくとも含む署 名装置であって、
前記排他的論理和が、前記署名装置の公開鍵の一部である RSAモジュラスを超え る場合には、前記排他的論理和をそのまま出力し、超えない場合には、前記排他的 論理和に RSA署名に準じた署名を行った結果を出力する第一の手段と、
前記第一の手段の出力に対して前記 RSAモジュラスだけ大き 、ほうに写像させる関 数をかける第二の手段と、
前記第二の手段での演算結果が前記 RSAモジュラスを超える場合には、前記全単 射手段での演算結果をそのまま出力し、超えない場合には、前記第二の手段での演 算結果に RSA署名に準じた署名を行った結果を出力する第三の変換手段と、 をさらに含む、ことを特徴とする署名装置。
[39] 請求項 38記載の署名装置の複数が順々に署名操作を行って作成した署名文が正 当であるかどうかを検証する検証装置であって、それぞれの署名装置における署名 を検証するために、
前記署名文が、対応する署名装置の RSAモジュラスを超える場合にはそのまま出 力し、超えない場合には、 RSA署名に準じた署名を行った結果を出力する第四の手 段と、
前記第四の手段の出力に対して前記 RSAモジュラスだけ小さ 、ほうに写像させる関 数をかける第五の手段と、
前記第五の手段の出力が前記 RSAモジュラスを超える場合には、前記第五の手段 の出力をそのまま出力し、超えない場合には、前記第五の手段の出力に、 RSA署名 に準じた署名を行った結果を出力する第六の手段と、
前記署名装置に入力されたメッセージと自装置の公開鍵及び既に署名した署名装 置の公開鍵とを連結した結果のハッシュ値と前記第六の手段の出力の排他的論理 和を求める第七の手段と、
を含み、
それぞれの前記署名装置に対する前記第七の手段による出力結果に基づき検証 の成功、失敗を判定する、ことを特徴とする検証装置。
PCT/JP2005/020729 2004-11-29 2005-11-11 署名および検証方法ならびに署名および検証装置 Ceased WO2006057171A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2006547724A JP4848957B2 (ja) 2004-11-29 2005-11-11 署名および検証方法ならびに署名および検証装置
EP05806273A EP1819090B1 (en) 2004-11-29 2005-11-11 Signature and verifying method, and signature and verifying device
US11/719,798 US20090044017A1 (en) 2004-11-29 2005-11-11 Signature and verifying method, and signature and verifying device

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2004-343703 2004-11-29
JP2004343703 2004-11-29

Publications (1)

Publication Number Publication Date
WO2006057171A1 true WO2006057171A1 (ja) 2006-06-01

Family

ID=36497909

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2005/020729 Ceased WO2006057171A1 (ja) 2004-11-29 2005-11-11 署名および検証方法ならびに署名および検証装置

Country Status (5)

Country Link
US (1) US20090044017A1 (ja)
EP (2) EP2381616B1 (ja)
JP (1) JP4848957B2 (ja)
CN (1) CN101069381A (ja)
WO (1) WO2006057171A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112241328A (zh) * 2020-09-10 2021-01-19 长沙市到家悠享网络科技有限公司 数据处理方法、装置及系统

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11080433B2 (en) * 2018-04-29 2021-08-03 Cryptowerk Corp. Cryptographic data storage
US11601284B2 (en) * 2019-06-14 2023-03-07 Planetway Corporation Digital signature system based on a cloud of dedicated local devices
KR102568418B1 (ko) * 2021-08-26 2023-08-18 하이파이브랩 주식회사 다중 서명을 지원하는 전자 인증 시스템 및 방법

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6177440A (ja) * 1984-09-22 1986-04-21 Nippon Telegr & Teleph Corp <Ntt> 署名文書通信方式
JPH02275983A (ja) * 1989-01-19 1990-11-09 Nippon Telegr & Teleph Corp <Ntt> 多重ディジタル署名方式
JPH0695590A (ja) * 1992-09-10 1994-04-08 Toshiba Corp 電子署名システム及び電子署名方法
JPH09270787A (ja) * 1996-03-29 1997-10-14 Nippon Telegr & Teleph Corp <Ntt> 順序指定多重電子署名システム及び順序指定多重電子署名方法
JP2000221882A (ja) * 1999-02-02 2000-08-11 Nippon Telegr & Teleph Corp <Ntt> 多重デジタル署名方法、そのシステム、その装置及びそのプログラム記録媒体

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6177440A (ja) * 1984-09-22 1986-04-21 Nippon Telegr & Teleph Corp <Ntt> 署名文書通信方式
JPH02275983A (ja) * 1989-01-19 1990-11-09 Nippon Telegr & Teleph Corp <Ntt> 多重ディジタル署名方式
JPH0695590A (ja) * 1992-09-10 1994-04-08 Toshiba Corp 電子署名システム及び電子署名方法
JPH09270787A (ja) * 1996-03-29 1997-10-14 Nippon Telegr & Teleph Corp <Ntt> 順序指定多重電子署名システム及び順序指定多重電子署名方法
JP2000221882A (ja) * 1999-02-02 2000-08-11 Nippon Telegr & Teleph Corp <Ntt> 多重デジタル署名方法、そのシステム、その装置及びそのプログラム記録媒体

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112241328A (zh) * 2020-09-10 2021-01-19 长沙市到家悠享网络科技有限公司 数据处理方法、装置及系统
CN112241328B (zh) * 2020-09-10 2024-01-23 长沙市到家悠享网络科技有限公司 数据处理方法、装置及系统

Also Published As

Publication number Publication date
EP2381616A1 (en) 2011-10-26
EP1819090B1 (en) 2012-07-11
EP1819090A4 (en) 2010-12-22
JPWO2006057171A1 (ja) 2008-06-05
EP2381616B1 (en) 2013-01-16
EP1819090A1 (en) 2007-08-15
US20090044017A1 (en) 2009-02-12
CN101069381A (zh) 2007-11-07
JP4848957B2 (ja) 2011-12-28

Similar Documents

Publication Publication Date Title
JP6042663B2 (ja) ｓｉｇｎｃｒｙｐｔｉｏｎ方法と装置及び対応するｓｉｇｎｃｒｙｐｔｉｏｎ検証方法と装置
US7372961B2 (en) Method of public key generation
McGrew et al. Fundamental elliptic curve cryptography algorithms
JP3998640B2 (ja) 暗号化及び署名方法、装置及びプログラム
EP2686978B1 (en) Keyed pv signatures
KR101099867B1 (ko) 서명 장치, 검증 장치, 증명 장치, 암호화 장치, 및 복호화장치
US8631240B2 (en) Compressed ECDSA signatures
CN103493428A (zh) 数据加密
WO2008026345A1 (en) Electronic signature system and electronic signature verifying method
Merz et al. Another look at some isogeny hardness assumptions
WO2006057171A1 (ja) 署名および検証方法ならびに署名および検証装置
Mohamed et al. The shortest signatures ever
JP5421361B2 (ja) メッセージに対する署名を生成する方法及び装置並びにそのような署名を検証する方法及び装置
JP2012103655A (ja) 耐量子コンピュータ性をもつディジタル署名方式
Rossi et al. Identity-based secure group communications using pairings
JPWO2006114948A1 (ja) 署名生成装置および署名検証装置
Kaliski Jr On hash function firewalls in signature schemes
JPWO2007010903A1 (ja) 鍵発行方法、グループ署名システム
WO2009090519A1 (en) Efficient reconstruction of a public key from an implicit certificate
US9054861B2 (en) Enhanced key agreement and transport protocol
WO2011033642A1 (ja) 署名生成装置及び署名検証装置
JP4802228B2 (ja) 鍵生成装置及びプログラム
Shao Improvement of efficient proxy signature schemes using self-certified public keys
McGrew et al. RFC 6090: Fundamental Elliptic Curve Cryptography Algorithms
Preneel Topics in Cryptology-CT-RSA 2002: The Cryptographer's Track at the RSA Conference 2002, San Jose, CA, USA, February 18-22, 2002, Proceedings

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KM KN KP KR KZ LC LK LR LS LT LU LV LY MA MD MG MK MN MW MX MZ NA NG NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SM SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LT LU LV MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

DPE2 Request for preliminary examination filed before expiration of 19th month from priority date (pct application filed from 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2006547724

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 2005806273

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11719798

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 200580040976.0

Country of ref document: CN

NENP Non-entry into the national phase

Ref country code: DE

WWP Wipo information: published in national office

Ref document number: 2005806273

Country of ref document: EP