{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:45:59Z","timestamp":1764132359588,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642756"},{"type":"electronic","value":"9783540697152"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","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":[[1998]]},"DOI":"10.1007\/bfb0054320","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T05:37:37Z","timestamp":1149658657000},"page":"170-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Batch verification with applications to cryptography and checking"],"prefix":"10.1007","author":[{"given":"Mihir","family":"Bellare","sequence":"first","affiliation":[]},{"given":"Juan A.","family":"Garay","sequence":"additional","affiliation":[]},{"given":"Tal","family":"Rabin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,25]]},"reference":[{"key":"16_CR1","first-page":"515","volume-title":"Lecture Notes in Computer Science No. 537","author":"L. Adleman","year":"1990","unstructured":"L. Adleman and K. Kompella. Fast Checkers for Cryptography. In A. J. Menezes and S. Vanstone, editors, Advances in Cryptology \u2014 Crypto '90, pages 515\u2013529, Berlin, 1990. Springer-Verlag. Lecture Notes in Computer Science No. 537."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd Annual Symposium on Foundations of Computer Science, pages 14\u201323. IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"M. Bellare, J. Garay, and T. Rabin. Distributed Pseudo-Random Bit Generators\u2014A New Way to Speed-Up Shared Coin Tossing. In Proceedings Fifteenth Annual Symposium on Principles of Distributed Computing, pages 191\u2013200. ACM, 1996.","DOI":"10.1145\/248052.248090"},{"key":"16_CR4","first-page":"208","volume-title":"Lecture Notes in Computer Science No. 658","author":"M. Beller","year":"1992","unstructured":"M. Beller and Y. Yacobi. Batch Diffie-Hellman Key Agreement Systems and their Application to Portable Communications. In R. Rueppel, editor, Advances in Cryptology \u2014 Eurocrypt '92, pages 208\u2013220, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science No. 658."},{"key":"16_CR5","unstructured":"E. Berlekamp and L. Welch. Error correction of algebraic block codes. US Patent 4,633,470."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the Correctness of Memories. In Proceeding 32nd Annual Symposium on the Foundations of Computer Science, pages 90\u201399. IEEE, 1991.","DOI":"10.1109\/SFCS.1991.185352"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan. Designing Programs that Check their Work. In Proceedings 21st Annual Symposium on the Theory of Computing, pages 86\u201397. ACM, 1989.","DOI":"10.1145\/73007.73015"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. Self-Testing\/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47:549\u2013595, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"J. Bos and M. Coster. Addition Chain Heuristics. In Advances in Cryptology-Proceedings of Crypto 89, Lecture Notes in Computer Science Vol. 658, pages 400\u2013407. Springer-Verlag, 1989.","DOI":"10.1007\/0-387-34805-0_37"},{"key":"16_CR10","first-page":"200","volume-title":"Lecture Notes in Computer Science No. 658","author":"E. Brickell","year":"1992","unstructured":"E. Brickell, D. Gordon, K. McCurley, and D. Wilson. Fast Exponentiation with Precomputation. In R. Rueppel, editor, Advances in Cryptology \u2014 Eurocrypt '92, pages 200\u2013207, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science No. 658."},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"E. Brickell, P. Lee, and Y. Yacobi. Secure Audio Teleconference. In Advances in Cryptology-Proceedings of Crypto 87, Lecture Notes in Computer Science Vol. 293, C. Pomerance editor, pages 418\u2013426. Springer-Verlag, 1987.","DOI":"10.1007\/3-540-48184-2_36"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In Proceeding 26th Annual Symposium on the Foundations of Computer Science, pages 383\u2013395. IEEE, 1985.","DOI":"10.1109\/SFCS.1985.64"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"F. Ergun, S. Ravi Kumar, and R. Rubinfeld. Approximate Checking of Polynomials and Functional Equations. In Proc. 37th Annual Symposium on Foundations of Computer Science, pages 592\u2013601. IEEE, 1996.","DOI":"10.1109\/SFCS.1996.548518"},{"issue":"2","key":"16_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s001459900021","volume":"10","author":"A. Fiat","year":"1997","unstructured":"A. Fiat. Batch RSA. Journal of Cryptology, 10(2):75\u201388, 1997.","journal-title":"Journal of Cryptology"},{"key":"16_CR15","unstructured":"National Institute for Standards and Technology. Digital Signature Standard (DSS). Technical Report 169, August 30 1991."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing\/correcting for polynomials and for approximate functions. In Proc. Twenty Third Annual ACM Symposium on Theory of Computing, pages 32\u201342. ACM, 1991.","DOI":"10.1145\/103418.103429"},{"key":"16_CR17","first-page":"95","volume-title":"Lecture Notes in Computer Science No. 839","author":"C.H. Lim","year":"1994","unstructured":"C.H. Lim and P.J. Lee. More Flexible Exponentiation with Precomputation. In Y. Desmedt, editor, Advances in Cryptology \u2014 Crypto '94, pages 95\u2013107, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 839."},{"key":"16_CR18","first-page":"77","volume-title":"Lecture Notes in Computer Science No. 950","author":"D. Naccache","year":"1994","unstructured":"D. Naccache, D. M'Rahi, S. Vaudenay, and D. Raphaeli. Can D.S.A be improved? Complexity trade-offs with the digital signature standard. In A. De Santis, editor, Advances in Cryptology \u2014 Eurocrypt '94, pages 77\u201385, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 950."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R. Rivest","year":"1978","unstructured":"R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21:120\u2013126, 1978.","journal-title":"Communications of the ACM"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(92)90093-B","volume":"42","author":"R. Rubinfeld","year":"1992","unstructured":"R. Rubinfeld. Batch Checking with Applications to Linear Functions. Information Processing Letters, 42:77\u201380, 1992.","journal-title":"Information Processing Letters"},{"key":"16_CR21","unstructured":"R. Rubinfeld. On the Robustness of Functional Equations. In Proc. 35th Annual Symposium on Foundations of Computer Science, pages 2\u201313. IEEE, 1994."},{"issue":"4","key":"16_CR22","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF01961540","volume":"15","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld. Designing Checkers for Programs that Run in Parallel. Algorithmica, 15(4):287\u2013301, 1996.","journal-title":"Algorithmica"},{"issue":"2","key":"16_CR23","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing, 25(2):252\u2013271, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR24","unstructured":"J. Sauerbrey and A. Dietel. Resource requirements for the application of addition chains modulo exponentiation. In Advances in Cryptology-Eurorypt '92, Lecture Notes in Computer Science Vol. 658. Springer-Verlag, 1992."}],"container-title":["Lecture Notes in Computer Science","LATIN'98: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:11:35Z","timestamp":1736406695000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054320"}},"subtitle":["Invited paper"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642756","9783540697152"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0054320","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"25 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}