{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:59:33Z","timestamp":1743152373837,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319402529"},{"type":"electronic","value":"9783319402536"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40253-6_19","type":"book-chapter","created":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T19:00:31Z","timestamp":1467226831000},"page":"310-326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Accelerating Oblivious Transfer with Batch Multi-exponentiation"],"prefix":"10.1007","author":[{"given":"Yang","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qianhong","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingwen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianwei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyi","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,30]]},"reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44987-6_8","volume-title":"Advances in Cryptology - EUROCRYPT 2001","author":"W Aiello","year":"2001","unstructured":"Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: how to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119\u2013135. Springer, Heidelberg (2001)"},{"key":"19_CR2","unstructured":"Avanzi, R.M.: On multi-exponentiation in cryptography. Cryptology ePrint Archive, Report 2002\/154 (2002)"},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/BFb0054130","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"M Bellare","year":"1998","unstructured":"Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236\u2013250. Springer, Heidelberg (1998)"},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/0-387-34805-0_48","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"M Bellare","year":"1990","unstructured":"Bellare, M., Micali, S.: Non-interactive oblivious transfer and applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 547\u2013557. Springer, Heidelberg (1990)"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","first-page":"400","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"JNE Bos","year":"1990","unstructured":"Bos, J.N.E., Coster, M.J.: Addition chain heuristics. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 400\u2013407. Springer, Heidelberg (1990)"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-47721-7_17","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"G Brassard","year":"1987","unstructured":"Brassard, G., Cr\u00e9peau, C., Robert, J.M.: All-or-nothing disclosure of secrets. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 234\u2013238. Springer, Heidelberg (1987)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-47555-9_18","volume-title":"Advances in Cryptology - EUROCRYPT \u201992","author":"EF Brickell","year":"1993","unstructured":"Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200\u2013207. Springer, Heidelberg (1993)"},{"issue":"4","key":"19_CR8","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00145-011-9108-z","volume":"25","author":"J Camenisch","year":"2012","unstructured":"Camenisch, J., Hohenberger, S., Pedersen, M.\u00d8.: Batch verification of short signatures. J. Cryptol. 25(4), 723\u2013747 (2012)","journal-title":"J. Cryptol."},{"key":"19_CR9","unstructured":"Cheon, J.H., Kim, Y., Yoon, H.: A new ID-based signature with batch verification. Cryptology ePrint Archive, Report 2004\/131 (2004)"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-30580-4_12","volume-title":"Public Key Cryptography - PKC 2005","author":"C-K Chu","year":"2005","unstructured":"Chu, C.-K., Tzeng, W.-G.: Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 172\u2013183. Springer, Heidelberg (2005)"},{"issue":"15","key":"19_CR11","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1016\/j.ipl.2009.04.008","volume":"109","author":"B Chung","year":"2009","unstructured":"Chung, B., Hur, J., Kim, H., Hong, S.M., Yoon, H.: Improved batch exponentiation. Inf. Process. Lett. 109(15), 832\u2013837 (2009)","journal-title":"Inf. Process. Lett."},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/3-540-44750-4_9","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"C Cr\u00e9peau","year":"1995","unstructured":"Cr\u00e9peau, C., van de Graaf, J., Tapp, A.: Committed oblivious transfer and private multi-party computation. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 110\u2013123. Springer, Heidelberg (1995)"},{"issue":"2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1109\/12.833110","volume":"49","author":"VS Dimitrov","year":"2000","unstructured":"Dimitrov, V.S., Jullien, G.A., Miller, W.C.: Complexity and fast algorithms for multiexponentiations. IEEE Trans. Comput. 49(2), 141\u2013147 (2000)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"19_CR14","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1137\/0210047","volume":"10","author":"P Downey","year":"1981","unstructured":"Downey, P., Leong, B., Sethi, R.: Computing sequences with addition chains. SIAM J. Comput. 10(3), 638\u2013646 (1981)","journal-title":"SIAM J. Comput."},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1007\/3-540-39568-7_2","volume-title":"Advances in Cryptology of CRYPTO \u201984","author":"T El Gamal","year":"1985","unstructured":"El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10\u201318. Springer, Heidelberg (1985)"},{"issue":"6","key":"19_CR16","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S Even","year":"1985","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637\u2013647 (1985)","journal-title":"Commun. ACM"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-00862-7_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2009","author":"AL Ferrara","year":"2009","unstructured":"Ferrara, A.L., Green, M., Hohenberger, S., Pedersen, M.\u00d8.: Practical short signature batch verification. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 309\u2013324. Springer, Heidelberg (2009)"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/0-387-34805-0_17","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"A Fiat","year":"1990","unstructured":"Fiat, A.: Batch RSA. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 175\u2013185. Springer, Heidelberg (1990)"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-38424-3_6","volume-title":"Advances in Cryptology - CRYPTO \u201990","author":"S Goldwasser","year":"1991","unstructured":"Goldwasser, S., Levin, L.A.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77\u201393. Springer, Heidelberg (1991)"},{"issue":"1","key":"19_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jagm.1997.0913","volume":"27","author":"DM Gordon","year":"1998","unstructured":"Gordon, D.M.: A survey of fast exponentiation methods. J. Algorithms 27(1), 129\u2013146 (1998)","journal-title":"J. Algorithms"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-68339-9_15","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"S-M Hong","year":"1996","unstructured":"Hong, S.-M., Oh, S.-Y., Yoon, H.: New modular multiplication algorithms for fast modular exponentiation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 166\u2013177. Springer, Heidelberg (1996)"},{"issue":"1","key":"19_CR22","first-page":"15","volume":"11","author":"MS Hwang","year":"2000","unstructured":"Hwang, M.S., Lin, I.C., Hwang, K.F.: Cryptanalysis of the batch verifying multiple RSA digital signatures. Inform. Lith. Acad. Sci. 11(1), 15\u201319 (2000)","journal-title":"Inform. Lith. Acad. Sci."},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding crytpography on oblivious transfer. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 20\u201331. ACM (1988)","DOI":"10.1145\/62212.62215"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A general completeness theorem for two party games. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 553\u2013560. ACM (1991)","DOI":"10.1145\/103418.103475"},{"issue":"4","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1137\/S0097539797321742","volume":"29","author":"J Kilian","year":"2000","unstructured":"Kilian, J., Kushilevitz, E., Micali, S., Ostrovsky, R.: Reducibility and completeness in private computations. SIAM J. Comput. 29(4), 1189\u20131208 (2000)","journal-title":"SIAM J. Comput."},{"key":"19_CR26","series-title":"Seminumerical Algorithms","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"2014","unstructured":"Knuth, D.E.: The Art of Computer Programming. Seminumerical Algorithms, vol. 2. Addison-Wesley Professional, Boston (2014)"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-48658-5_11","volume-title":"Advances in Cryptology - CRYPTO \u201994","author":"CH Lim","year":"1994","unstructured":"Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95\u2013107. Springer, Heidelberg (1994)"},{"issue":"1","key":"19_CR28","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.amc.2006.06.089","volume":"185","author":"DC Lou","year":"2007","unstructured":"Lou, D.C., Lai, J.C., Wu, C.L., Chang, T.J.: An efficient montgomery exponentiation algorithm by using signed-digit-recoding and folding techniques. Appl. Math. Comput. 185(1), 31\u201344 (2007)","journal-title":"Appl. Math. Comput."},{"key":"19_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/3-540-45600-7_26","volume-title":"Information and Communications Security","author":"M-S Hwang","year":"2001","unstructured":"Hwang, M.-S., Lee, C.-C., Tang, Y.-L.: Two Simple batch verifying multiple digital signatures. In: Qing, S., Okamoto, T., Zhou, J. (eds.) ICICS 2001. LNCS, vol. 2229, pp. 233\u2013237. Springer, Heidelberg (2001)"},{"issue":"170","key":"19_CR30","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1090\/S0025-5718-1985-0777282-X","volume":"44","author":"PL Montgomery","year":"1985","unstructured":"Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519\u2013521 (1985)","journal-title":"Math. Comput."},{"key":"19_CR31","doi-asserted-by":"crossref","unstructured":"M\u2019Ra\u00efhi, D., Naccache, D.: Batch exponentiation: a fast DLP-based signature generation strategy. In: Proceedings of the 3rd ACM Conference on Computer and Communications Security, CCS 1996, pp. 58\u201361. ACM, New York (1996)","DOI":"10.1145\/238168.238187"},{"key":"19_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/3-540-48405-1_36","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"M Naor","year":"1999","unstructured":"Naor, M., Pinkas, B.: Oblivious transfer with adaptive queries. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 573\u2013590. Springer, Heidelberg (1999)"},{"key":"19_CR33","unstructured":"Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 448\u2013457. Society for Industrial and Applied Mathematics (2001)"},{"issue":"2","key":"19_CR34","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.jco.2003.08.023","volume":"20","author":"W Ogata","year":"2004","unstructured":"Ogata, W., Kurosawa, K.: Oblivious keyword search. J. Complex. 20(2), 356\u2013371 (2004)","journal-title":"J. Complex."},{"issue":"2","key":"19_CR35","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0209022","volume":"9","author":"N Pippenger","year":"1980","unstructured":"Pippenger, N.: On the evaluation of powers and monomials. SIAM J. Comput. 9(2), 230\u2013250 (1980)","journal-title":"SIAM J. Comput."},{"key":"19_CR36","unstructured":"Rabin, M.O.: How to exchange secrets by oblivious transfer. Technical report TR-81, Aiken Computation Laboratory, Havard University (1981)"},{"key":"19_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BFb0053453","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"P de Rooij","year":"1995","unstructured":"de Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389\u2013399. Springer, Heidelberg (1995)"},{"key":"19_CR38","unstructured":"Solinas, J.: Low-weight binary representations for pairs of integers. Technical report, CORR 2001\u201341, Department of C&O, University of Waterloo (2001)"},{"key":"19_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-319-17533-1_14","volume-title":"Information Security Practice and Experience","author":"Y Sun","year":"2015","unstructured":"Sun, Y., Wu, Q., Qin, B., Wang, Y., Liu, J.: Batch blind signatures on elliptic curves. In: Lopez, J., Wu, Y. (eds.) Information Security Practice and Experience. LNCS, vol. 9065, pp. 192\u2013206. Springer, Heidelberg (2015)"},{"key":"19_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/3-540-45664-3_11","volume-title":"Public Key Cryptography","author":"W-G Tzeng","year":"2002","unstructured":"Tzeng, W.-G.: Efficient 1-out-n oblivious transfer schemes. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 159\u2013171. Springer, Heidelberg (2002)"},{"issue":"2","key":"19_CR41","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1016\/j.amc.2006.08.051","volume":"186","author":"CL Wu","year":"2007","unstructured":"Wu, C.L., Lou, D.C., Lai, J.C., Chang, T.J.: Fast modular multi-exponentiation using modified complex arithmetic. Appl. Math. Comput. 186(2), 1065\u20131074 (2007)","journal-title":"Appl. Math. Comput."},{"key":"19_CR42","doi-asserted-by":"crossref","unstructured":"Wu, Q., Sun, Y., Qin, B., Hu, J., Liu, W., Liu, J., Ding, Y.: Batch public key cryptosystem with batch multi-exponentiation. Future Gener. Comput. Syst. (2015)","DOI":"10.1016\/j.future.2015.12.009"},{"key":"19_CR43","doi-asserted-by":"crossref","unstructured":"Yao, A.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 162\u2013167. IEEE (1986)","DOI":"10.1109\/SFCS.1986.25"},{"issue":"6","key":"19_CR44","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1049\/ip-cdt:19941271","volume":"141","author":"SM Yen","year":"1994","unstructured":"Yen, S.M., Laih, C.S., Lenstra, A.K.: Multi-exponentiation (cryptographic protocols). Comput. Digital Techn. 141(6), 325\u2013326 (1994)","journal-title":"Comput. Digital Techn."},{"key":"19_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, C., Lu, R., Lin, X., Ho, P.H., Shen, X.: An efficient identity-based batch verification scheme for vehicular sensor networks. In: The 27th Conference on Computer Communications, INFOCOM 2008, pp. 816\u2013824. IEEE, April 2008","DOI":"10.1109\/INFOCOM.2007.58"}],"container-title":["Lecture Notes in Computer Science","Information Security and Privacy"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40253-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:46:06Z","timestamp":1718671566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40253-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319402529","9783319402536"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40253-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"30 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}