Source: https://patents.google.com/patent/US20080320557?oq=6%2C240%2C376
Timestamp: 2018-02-19 12:55:10
Document Index: 42598967

Matched Legal Cases: ['art 136', 'art 136', 'art 136', 'art 136', 'art 136', 'art 136', 'art 135', 'art 136', 'art 136', 'art 136', 'art 136', 'art 136', 'art 137', 'art 136', 'art 136', 'art 136']

US20080320557A1 - Batch verification device, program and batch verification method - Google Patents
Batch verification device, program and batch verification method
US20080320557A1
US20080320557A1 US12046585 US4658508A US2008320557A1 US 20080320557 A1 US20080320557 A1 US 20080320557A1 US 12046585 US12046585 US 12046585 US 4658508 A US4658508 A US 4658508A US 2008320557 A1 US2008320557 A1 US 2008320557A1
US12046585
The present invention relates to technology for batching and verifying of multiple digital signatures.
For this type of signature, it is necessary to carry out repetitive and complicated processing when verifying, but in technology described in, for example, M. Bellare, J. Garay and T. Rabin, “Fast Batch Verification for Modular Exponentiation and Digital Signatures”, Advances in Cryptology—EUORCRYPT 1998, LNCS 1403, pp. 236-250, 1998, (referred to as Reference 1), batch verifying of multiple digital signatures enables improvement in the efficiency of verification processing of the digital signatures.
A batch instance (xi, yi), (i=1, . . . , n), is “valid” when it satisfies Equation (1) with respect to each i (i=1, . . . , n), and “invalid” when it does not. Furthermore, when the batch instance is valid, the signature data is also deemed to be “valid” and when the batch instance is invalid, the signature data is also deemed to be “invalid”.
Additionally in batch verification, valid batch instances are always accepted as “valid” but there are instances when an invalid batch instance with an extremely small probability is also accepted as “valid”. When the upper limit of the probability that an invalid batch instance will be accepted as “valid” is a maximum of ½m (m is a positive integer), m is called the security level of batch verification. It is well known that with the capability of recent computers it is preferable to have m set to approximately 80. Furthermore, it is well known that the larger the security level m, the higher the security of the digital signatures.
1(i=1, . . . , n) (5)
Here, as shown in Equation (5), 0 or 1 are randomly selected for si with respect to each i (i=1, . . . , n).
Additionally, as shown in Equation (5), “Random” in the Random Subset Test stems from randomly selecting si for each i (I=1, 2, 3, . . , n). The Random Subset Test accepts an “invalid” batch instance as “valid” with a probability of ½ at most. Consequently, in order to actually set the security level at m, the Atomic Random Subset Test is used to perform the Random Subset Test m times independently. By doing this, the probability that the Atomic Random Subset Test, which carries out the Random Subset Text m times independently, will accept an “invalid” batch instance as “valid” is ½m at most. Furthermore, even in the Small Exponents Test mentioned above, the probability of an “invalid” batch instance being accepted as “valid” is a ½m at most.
The efficiency of the batch verification described in Reference 1 depends on the number n of batch instances and the security level m but there is a trade-off relationship between efficiency and security (security level m) in that if high security is desired, high efficiency cannot be expected.
FIG. 1 is a diagram exemplifying an outline of a signature batch verification system for a first embodiment;
FIG. 1 is an outline of a signature batch verification system 100 which is a first embodiment of this invention.
For example, in this embodiment, the mathematical function computing part 136 as shown in FIG. 4 (outline of the mathematical function computing part 136) is composed of a batch instance generating part 136 a, a substitute part 136 b and a modular exponentiation computing part 136 f.
The batch instance generating part 136 a generates a batch instance from the signature contained in the signature data input from the signature batch verification part 135. Here, the batch instance generating method depends on the form of the signature used in the signature device 110 and the verification device 130. Furthermore, when the signature generated by the form of the signature used in the signature device 110 and the verification device 130 becomes the batch instance, it is not necessary to set up the batch instance generating part 136 a in the mathematical function computing part 136. Additionally, an explanation will be given in Embodiments 2 and 3 described later regarding the specific generating method of the batch instances.
The modular exponentiation computing part 136 f carries out verification by performing modular exponentiation on the batch instances which have been replaced by the permutation part 136 b. Additionally, a detailed explanation will be given using FIG. 8 regarding processing with the modular exponentiation computing part 136 f.
The input part 137 receives the input of the information.
Additionally, the ECDSA* signature and the ECDSA signature scheme are described in A. Antipa, D. Brown, R. Gallant, R. Lambert, R. Struik, and S. Vanstone, “Accelerated Verification of ECDSA Signatures”, Selected Areas in Cryptography—SAC 2005, LNCS 3897, pp. 307-318, 2006 (referred to below as Reference 2).
FIG. 9 is a flow chart exemplifying the permutation processing in the permutation part 136 b.
First, the intermediate state storage part 136 d in the permutation part 136 b stores the batch instance (xi, yi) (i=1, . . . , n) in the area T (S40).
Additionally, a detailed description of the pseudo-random number generator is given in, for example, D. Watanabe, S. Furuya, H. Yoshida, K. Takaragi, and B. Preneel, “A New Keystream Generator MUGI”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E87-A, No.1, 2004.
Furthermore, in the batch instance (xi, yi) (i=1, . . . , n), if Equation (1) above is satisfied with respect to each i (i=1, . . . , n), Equation (10) above is satisfied. That is, the signature batch verification method always receives a valid batch instance as “valid”. The reason is given below.
The upper limit of the probability that the above described signature batch verification method will receive an invalid batch instance as “valid” is a maximum 1/q. The reason for this is given below.
Πλτ(i) a ≡g Σa τ(i) α i ×yΣb τ(i) α i mod q (26)
That is, when Equation (26) is satisfied, the signature Si is received as “valid” and when it is not, the signature Si is rejected as “invalid”. Furthermore, α in Equation (26) is an arbitrary natural number. Here, αi in Equation (26) is not limited to this condition and may be a number that is different than the order i and may, for example, be an arbitrary function f (i) in which i is the variable.
#E (Fq)=n×h (here, h is a small integer, n is a large prime number).
That is, when Equation (33) is satisfied, the signature Si is received as “valid” and when it is not, the signature Si is rejected as “invalid”. Furthermore, α in Equation (33) is an arbitrary natural number. Here, αi in Equation (33) is not limited to this condition and may be a number that depends on the order i, for example, an arbitrary function f(i) with i as the variable.
a value calculated by multiplying a value calculated by carrying out an exponentiation of the generator of a finite multiplicative cyclic group in all of the batch instances, with a multiplied value, obtained by multiplying the first value by a number which differs depending on the order, as an exponent, and
a value calculated by multiplying a value calculated by carrying out a modular exponentiation of the second value in all of the batch instances, with a number which differs depending on the order as an exponent, are in agreement.
a processing part which carries out verification based on whether or not a value obtained by calculating a scalar multiplication of a generator of a finite additive cyclic group, with a multiplied value, calculated by multiplying the first value by a number which differs depending on the order, as a scalar value, and a value obtained by calculating a scalar multiplication of the second value, with a number which differs depending on the order, as a scalar value, are in agreement.
the program causes the computer to function as a processor which carries out verification based on whether or not a value calculated by carrying out an exponentiation of a generator of a finite multiplicative cyclic group, with a multiplied value, obtained by multiplying the first value by numbers which differ depending on the order, as an exponent, and a value calculated by carrying out a modular exponentiation of the second value, with a number which differs depending on the order, as an exponent, are in agreement.
the program causes the computer to function as a processor which carries out verification based on whether or not a value obtained by calculating a scalar multiplication of a generator of a finite additive cyclic group, with a multiplied value, calculated by multiplying the first value by a number which differs depending on the order, as a scalar value, and a value obtained by calculating a scalar multiplication of the second value, with a number which differs depending on the order as a scalar value, are in agreement.
US12046585 2007-06-25 2008-03-12 Batch verification device, program and batch verification method Abandoned US20080320557A1 (en)
JP2007-165892 2007-06-25
JP2007165892A JP4988448B2 (en) 2007-06-25 2007-06-25 Batch verification apparatus, program and batch verification method
US20080320557A1 true true US20080320557A1 (en) 2008-12-25
ID=39328064
US12046585 Abandoned US20080320557A1 (en) 2007-06-25 2008-03-12 Batch verification device, program and batch verification method
US (1) US20080320557A1 (en)
JP (1) JP4988448B2 (en)
CN (1) CN101335625B (en)
GB (1) GB2450574B (en)
US8990575B2 (en) 2012-03-16 2015-03-24 Samsung Electronics Co., Ltd. Apparatus and method for electronic signature verification
WO2013153628A1 (en) * 2012-04-11 2013-10-17 株式会社日立製作所 Calculation processing system and calculation result authentication method
CN103428692B (en) * 2013-08-07 2016-08-10 华南理工大学 Privacy and accountability radio access network authentication method and an authentication system
JP2001044987A (en) * 1999-08-03 2001-02-16 Advanced Mobile Telecommunications Security Technology Research Lab Co Ltd Batch authentication method
JP2001209308A (en) * 2000-01-24 2001-08-03 Advanced Mobile Telecommunications Security Technology Research Lab Co Ltd Batch signing method
FR2807246B1 (en) 2000-03-28 2002-12-27 Gemplus Card Int Electronic method for generating from first integers between them and method of implementation of device
EP1998493A4 (en) * 2006-03-16 2015-12-09 Nec Corp Group signature system and information processing method
JP4988448B2 (en) 2012-08-01 grant
GB2450574B (en) 2009-08-12 grant
CN101335625B (en) 2012-07-11 grant
GB0804683D0 (en) 2008-04-16 grant
JP2009005213A (en) 2009-01-08 application
GB2450574A (en) 2008-12-31 application
CN101335625A (en) 2008-12-31 application
Sander 1999 Efficient accumulators without trapdoor extended abstract
US20100166175A1 (en) 2010-07-01 Cryptographic hash functions using elliptic polynomial cryptography
Yang et al. 2005 Analysis and improvement of a signcryption scheme with key privacy
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HUKUTA, KEISUKE;SATO, HISAYOSHI;REEL/FRAME:021181/0955;SIGNING DATES FROM 20080512 TO 20080609