×

Simplified small exponent test for batch verification. (English) Zbl 1356.68263

Summary: The Small Exponent Test (SET) for exponentiation is an essential batch-verification technique that is widely applied. In this paper, we propose a simplified SET that can securely batch-verify \(n\) instances with only \(n - 1\) randomizing exponents. We show that the structure of the proposed batch test is compact in the sense that it works with a minimal number of randomizing exponents for the SET. Thus, our test offers various advantages. Overall, compared to the original SET, the proposed simplified SET is more efficient for any sized batch instance. In particular, unlike the SET, our proposal performs well even when the size of a batch instance is small, e.g., \(n = 1, 2, 3\), and 4. This feature can be also used to significantly reduce pairing computations in a signature scheme where several pairing equations are verified. In addition, our test can be combined easily and generically with existing batch techniques such as the use of sparse exponents, the bucket test for large batch sizes, or an automated tool to generate a batch algorithm. Finally, with our simplified test, an efficient identification algorithm can be constructed to discover incorrect instances in a batch.

MSC:

68W20 Randomized algorithms
68Q60 Specification and verification (program logics, model checking, etc.)
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Software:

PBC Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antipa, A.; Brown, D.; Gallant, R.; Lambert, R.; Struik, R.; Vanstone, S., Accelerated verification of ECDSA signatures, (SAC 2005, vol. 3897 (2006), Springer), 307-318 · Zbl 1151.94595
[2] Akinyele, J. A.; Green, M.; Hohenberger, S.; Pagano, M. W., Machine-generated algorithms, proofs and software for the batch verification of digital signature schemes, (ACM CCS’12 (2012), ACM Press), 474-487
[3] Abe, M.; Fuchsbauer, G.; Groth, J.; Haralambiev, K.; Ohkubo, M., Structure-preserving signatures and commitments to group elements, (CRYPTO’10, vol. 6223 (2010), Springer), 209-236 · Zbl 1280.94102
[4] Abe, M.; Groth, J.; Haralambiev, K.; Ohkubo, M., Optimal structure-preserving signatures in asymmetric bilinear groups, (CRYPTO’11, vol. 6841 (2011), Springer), 649-666 · Zbl 1290.94038
[5] Abe, M.; Groth, J.; Ohkubo, M.; Tibouchi, M., Unified, minimal and selectively randomizable structure-preserving signatures, (TCC’14, vol. 8349 (2014), Springer), 688-712 · Zbl 1326.94067
[6] Bernstein, D.; Doumen, J.; Lange, T.; Oosterwijk, J., Faster batch forgery identification, (Indocrypt 2012, vol. 7668 (2012), Springer-Verlag), 454-473 · Zbl 1295.94173
[7] Bellare, M.; Garay, J. A.; Rabin, T., Fast batch verification for modular exponentiation and digital signatures, (Eurocrypt 1998, vol. 1403 (1998), Springer-Verlag), 236-250 · Zbl 0929.68053
[8] Cha, J. C.; Cheon, J. H., An identity-based signature from gap Diffie-Hellman groups, (PKC 2003, vol. 2567 (2003), Springer-Verlag), 18-30 · Zbl 1033.94554
[9] Choi, K. Y.; Hwang, J. Y.; Lee, D. H., Efficient ID-based group key agreement with bilinear maps, (PKC 2004, vol. 2947 (2004), Springer-Verlag), 130-144 · Zbl 1177.94140
[10] Camenisch, J.; Hohenberger, S.; Pedersen, M.Ø., Batch verification of short signatures, J. Cryptology, 25, 4, 723-747 (2012) · Zbl 1286.94091
[11] Cheon, J. H.; Lee, D. H., Use of sparse and/or complex exponents in batch verification of exponentiations, IEEE Trans. Comput., 55, 12, 1536-1542 (2006)
[12] Cheon, J. H.; Lee, M.-K., Improved batch verification of signatures using generalized sparse exponents, Comput. Stand. Interfaces, 40, 42-52 (2015)
[13] Elashry, I.; Mu, Y.; Susilo, W., Jhanwar-Barua’s identity-based encryption revisited, (NSS’14. NSS’14, LNCS, vol. 8792 (2014), Springer-Verlag), 271-284
[14] Fait, A., A batch RSA, (Crypto 1989, vol. 435 (1989), Springer-Verlag), 175-185
[15] Ferrara, A. L.; Green, M.; Hohenberger, S.; Pedersen, M., Practical short signature batch verification, (CT-RSA 2009, vol. 5473 (2009), Springer-Verlag), 309-324 · Zbl 1237.94063
[16] Gallbraith, S., Pairings, (Advances in Elliptic Curve Cryptography, vol. 317 (2005), Cambridge University Press), 183-213, chapter IX
[17] Goldwasser, S.; Micali, S.; Rivest, R., A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput., 17, 2, 281-308 (1988) · Zbl 0644.94012
[18] Gopal, P. V.S. S.N.; Vasudeva Reddy, P.; Gowri, T., Efficient signature scheme with batch verifications in identity-based framework, ETRI J., 38, 2, 397-404 (2016)
[19] Hess, F., Efficient identity based signature schemes based on pairings, (Selected Areas in Cryptography, vol. 2595 (2002), Springer), 310-324 · Zbl 1066.94554
[20] Hwang, J. Y.; Choi, D.; Cho, H.; Song, B., New Efficient Batch Verification for an Identity-Based Signature Scheme, Secur. Commun. Netw., 8, 15, 2524-2535 (2015)
[21] Hankerson, D.; Menezes, A.; Vanstone, S., Guide to Elliptic Curve Cryptography (2004), Springer: Springer New York · Zbl 1059.94016
[22] Joux, A., A one round protocol for tripartite Diffie-Hellman, J. Cryptology, 17, 4, 263-276 (2004) · Zbl 1070.94007
[23] Katz, J.; Yung, M., Scalable protocols for authenticated group key exchange, (Crypto 2003, vol. 2729 (2003), Springer-Verlag). (Crypto 2003, vol. 2729 (2003), Springer-Verlag), J. Cryptology, 20, 1, 85-113 (2007), The full version appears in · Zbl 1115.68076
[24] Lim, C. H., Efficient multi-exponentiation and application to batch verification of digital signatures (2000)
[25] Ben, Lynn, The pairing-based cryptography library
[26] Lim, C. H.; Lee, P. J., More flexible exponentiation with precomputation, (Crypto 1994, vol. 839 (1994), Springer-Verlag), 95-107 · Zbl 0939.94537
[27] Lim, C. H.; Lee, P. J., Security of interactive DSA batch verification, Electron. Lett., 30, 19, 1592-1593 (1994)
[28] Law, L.; Matt, B. J., Finding invalid signatures in pairing-based batches, (Cryptography and Coding. Cryptography and Coding, 11th IMA International Conference. Cryptography and Coding. Cryptography and Coding, 11th IMA International Conference, LNCS, vol. 4887 (2007), Springer), 34-53 · Zbl 1154.94466
[29] Laih, C.; Yen, S., Improved digital signature suitable for batch verification, IEEE Trans. Comput., 44, 7, 957-959 (1995) · Zbl 1053.68574
[30] Matt, B. J., Identification of multiple invalid signatures in pairing-based batched signatures, (PKC 2009, vol. 5443 (2009), Springer-Verlag), 337-356 · Zbl 1227.94080
[31] Matt, B. J., Identification of multiple invalid pairing-based signatures in constrained batches, (Pairing 2010, vol. 6487 (2010), Springer-Verlag), 78-95 · Zbl 1287.94114
[32] Möller, B., Algorithms for multi-exponentiation, (SAC 2001, vol. 2259 (2001), Springer-Verlag), 165-180 · Zbl 1067.94554
[33] Mohamed, N. A.F.; Hashim, M. H.A.; Hutter, M., Improved fixed-base comb method for fast scalar multiplication, (AFRICACRYPT 2012, vol. 7374 (2012), Springer-Verlag), 342-359 · Zbl 1291.94134
[34] Möller, B.; Rupp, A., Faster multi-exponentiation through caching: accelerating (EC)DSA signature verification, (SCN 2008, vol. 5229 (2008), Springer-Verlag), 39-56 · Zbl 1180.68153
[35] Naccache, D.; M’Raïhi, D.; Vaudendy, S.; Raphaeli, D., Can DSA be improved? Complexity trade-offs with the digital signature standard, (Eurocrypt 1994, vol. 950 (1994), Springer-Verlag), 77-85 · Zbl 0881.94016
[36] Pastuszak, J.; Michalek, D.; Pieprzyk, J.; Seberry, J., Identification of bad signatures in batches, (PKC 2000, vol. 1751 (2000), Springer-Verlag), 28-45 · Zbl 0966.94024
[37] Paterson, K., Cryptography from pairings, (Advances in Elliptic Curve Cryptography, vol. 317 (2005), Cambridge University Press), 215-251, chapter X
[38] Shim, K-A., A round-optimal three-party ID-based authenticated key agreement protocol, Inform. Sci., 186, 240-248 (2012) · Zbl 1239.94077
[39] Shacham, H.; Boneh, D., Improving SSL handshake performance via batching, (CT-RSA 2001, vol. 2020 (2001), Springer), 28-43 · Zbl 0972.68071
[40] Waters, B., Efficient identity-based encryption without random oracles, (EUROCRYPT 2005, vol. 3494 (2005), Springer), 320-329 · Zbl 1137.94360
[41] Yoon, H.; Cheon, J. H.; Kim, Y., Batch verification with ID-based signatures, (ICISC 2004, vol. 3506 (2005), Springer), 233-248 · Zbl 1133.94339
[42] Zaverucha, G. M.; Stinson, D. R., Group testing and batch verification, (ICITS 2009, vol. 5973 (2010), Springer-Verlag), 140-157 · Zbl 1282.94073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.