{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:25:02Z","timestamp":1767979502573,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540440505","type":"print"},{"value":"9783540457084","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45708-9_19","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:48:16Z","timestamp":1192783696000},"page":"288-304","source":"Crossref","is-referenced-by-count":324,"title":["A Generalized Birthday Problem"],"prefix":"10.1007","author":[{"given":"David","family":"Wagner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,13]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Kumar, D. Sivakumar, \u201cA Sieve Algorithm for the Shortest Lattice Vector Problem,\u201d STOC 2001, pp.601\u2013610, ACM Press, 2001.","DOI":"10.1145\/380752.380857"},{"key":"19_CR2","series-title":"Lect Notes Comput Sci","volume-title":"EUROCRYPT\u201997","author":"M. Bellare","year":"1997","unstructured":"M. Bellare, D. Micciancio, \u201cA New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost,\u201d EUROCRYPT\u201997, LNCS 1233, Springer-Verlag, 1997."},{"issue":"233","key":"19_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1090\/S0025-5718-00-01219-9","volume":"70","author":"D. Bernstein","year":"2001","unstructured":"D. Bernstein, \u201cEnumerating solutions to p(a)+q(b) = r(c)+s(d),\u201d Math. Comp., 70(233):389\u2013394, AMS, 2001.","journal-title":"Math. Comp."},{"key":"19_CR4","unstructured":"D. Bleichenbacher, \u201cOn the generation of DSA one-time keys,\u201d unpublished manuscript, Feb. 7, 2002."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, A. Kalai, H. Wasserman, \u201cNoise-Tolerant Learning, the Parity Problem, and the Statistical Query Model,\u201d STOC 2000, ACM Press, 2000.","DOI":"10.1145\/335305.335355"},{"key":"19_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-44448-3_3","volume-title":"ASIACRYPT 2000","author":"D. Boneh","year":"2000","unstructured":"D. Boneh, A. Joux, P.Q. Nguyen, \u201cWhy Textbook ElGamal and RSA Encryption are Insecure,\u201d ASIACRYPT 2000, LNCS 1976, Springer-Verlag, pp.30\u201344, 2000."},{"key":"19_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/3-540-45539-6_40","volume-title":"EUROCRYPT 2000","author":"A. Canteaut","year":"2000","unstructured":"A. Canteaut, M. Trabbia, \u201cImproved Fast Correlation Attacks Using Parity-Check Equations of Weight 4 and 5,\u201d EUROCRYPT 2000, LNCS 1807, Springer-Verlag, pp.573\u2013588, 2000."},{"key":"19_CR8","unstructured":"M. Casto, B. Liskov, \u201cPractical Byzantine Fault Tolerance,\u201d Proc. 3rd OSDI (Operating Systems Design & Implementation), Usenix, Feb. 1999."},{"key":"19_CR9","unstructured":"M. Casto, B. Liskov, \u201cProactive Recovery in a Byzantine-Fault-Tolerant System,\u201d Proc. 4th OSDI (Operating Systems Design & Implementation), Usenix, Oct. 2000."},{"key":"19_CR10","series-title":"Lect Notes Comput Sci","volume-title":"FSE 2000","author":"V.V. Chepyzhov","year":"2001","unstructured":"V.V. Chepyzhov, T. Johansson, B. Smeets, \u201cA Simple Algorithm for Fast Correlation Attacks on Stream Ciphers,\u201d FSE 2000, LNCS 1978, Springer-Verlag, 2001."},{"key":"19_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46035-7_14","volume-title":"EUROCRYPT 2002","author":"P. Chose","year":"2002","unstructured":"P. Chose, A. Joux, M. Mitton, \u201cFast Correlation Attacks: an Algorithmic Point of View,\u201d EUROCRYPT 2002, LNCS 2332, Springer-Verlag, 2002."},{"key":"19_CR12","unstructured":"W. Dai, personal communication, Aug. 1999."},{"key":"19_CR13","unstructured":"H. Gobioff, \u201cSecurity for a High Performance Commodity Storage Subsystem,\u201d Ph.D. thesis, CS Dept., Carnegie Mellon Univ., July 1999."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"H. Gobioff, D. Nagle, G. Gibson, \u201cEmbedded Security for Network-Attached Storage,\u201d Tech. report CMU-CS-99-154, CS Dept., Carnegie Mellon Univ., June 1999.","DOI":"10.21236\/ADA367675"},{"key":"19_CR15","series-title":"Lect Notes Comput Sci","first-page":"50","volume-title":"INDOCRYPT 2001","author":"B.-M. Goi","year":"2001","unstructured":"B.-M. Goi, M.U. Siddiqi, H.-T. Chuah, \u201cIncremental Hash Function Based on Pair Chaining & Modular Arithmetic Combining,\u201d INDOCRYPT 2001, LNCS 2247, Springer-Verlag, pp.50\u201361, 2001."},{"issue":"21","key":"19_CR16","doi-asserted-by":"publisher","first-page":"1981","DOI":"10.1049\/el:19961338","volume":"32","author":"J. Goli\u0107","year":"1996","unstructured":"J. Goli\u0107, \u201cComputation of low-weight parity-check polynomials,\u201d Electronics Letters, 32(21):1981\u20131982, 1996.","journal-title":"Electronics Letters"},{"key":"19_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"ASIACRYPT 2001","author":"N.J. Hopper","year":"2001","unstructured":"N.J. Hopper, M. Blum, \u201cSecure Human Identification Protocols,\u201d ASIACRYPT 2001, LNCS 2248, Springer-Verlag, pp.52\u201366, 2001."},{"key":"19_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44598-6_19","volume-title":"CRYPTO 2000","author":"T. Johansson","year":"2000","unstructured":"T. Johansson, F. J\u00f6nsson, \u201cFast Correlation Attacks Through Reconstruction of Linear Polynomials,\u201d CRYPTO 2000, LNCS 1880, Springer-Verlag, 2000."},{"issue":"234","key":"19_CR19","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1090\/S0025-5718-00-01200-X","volume":"70","author":"A. Joux","year":"2001","unstructured":"A. Joux, R. Lercier, \u201c\u2018Chinese & Match\u2019, an alternative to Atkin\u2019s \u2018Match and Sort\u2019 method used in the SEA algorithm,\u201d Math. Comp., 70(234):827\u2013836, AMS, 2001.","journal-title":"Math. Comp."},{"key":"19_CR20","unstructured":"D.E. Knuth, The Art of Computer Programming, vol 3, Addison-Wesley, 1973."},{"issue":"3","key":"19_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF02252874","volume":"1","author":"W. Meier","year":"1989","unstructured":"W. Meier, O. Staffelbach. \u201cFast correlation attacks on certain stream ciphers,\u201d J. Cryptology, 1(3):159\u2013167, 1989.","journal-title":"J. Cryptology"},{"key":"19_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-44706-7_14","volume-title":"FSE 2000","author":"M.J. Mihalevi\u0107","year":"2001","unstructured":"M.J. Mihalevi\u0107, M.P.C. Fossorier, H. Imai, \u201cA Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack,\u201d FSE 2000, LNCS 1978, Springer-Verlag, pp.196\u2013212, 2001."},{"issue":"2","key":"19_CR23","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02113297","volume":"55","author":"V.I. Nechaev","year":"1994","unstructured":"V.I. Nechaev, \u201cComplexity of a determinate algorithm for the discrete logarithm,\u201d Math. Notes, 55(2):165\u2013172, 1994.","journal-title":"Math. Notes"},{"key":"19_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/3-540-46885-4_43","volume-title":"EUROCRYPT\u201989","author":"J.-J. Quisquater","year":"1990","unstructured":"J.-J. Quisquater, J.-P. Delescaille, \u201cHow easy is collision search? Application to DES (Extended summary),\u201d EUROCRYPT\u201989, LNCS 434, Springer-Verlag, pp.429\u2013434, 1990."},{"issue":"1","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"P.C. Oorschot van","year":"1999","unstructured":"P.C. van Oorschot, M.J. Wiener, \u201cParallel Collision Search with Cryptanalytic Applications,\u201d Journal of Cryptology, 12(1):1\u201328, 1999.","journal-title":"Journal of Cryptology"},{"key":"19_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/3-540-60693-9_10","volume-title":"Cryptography and Coding","author":"W.T. Penzhorn","year":"1995","unstructured":"W.T. Penzhorn, G.J. K\u00fchn, \u201cComputation of Low-Weight Parity Checks for Correlation Attacks on Stream Ciphers,\u201d Cryptography and Coding, LNCS 1024, Springer, pp.74\u201383, 1995."},{"key":"19_CR27","unstructured":"M. Salmasizadeh, J. Golic, E. Dawson, L. Simpson. \u201cA Systematic Procedure for Applying Fast Correlation Attacks to Combiners with Memory,\u201d SAC\u201997 (Selected Areas in Cryptography)."},{"key":"19_CR28","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"ICICS 2001","author":"C.P. Schnorr","year":"2001","unstructured":"C.P. Schnorr, \u201cSecurity of Blind Discrete Log Signatures against Interactive Attacks,\u201d ICICS 2001, LNCS 2229, Springer-Verlag, pp.1\u201312, 2001."},{"key":"19_CR29","series-title":"Lect Notes Comput Sci","volume-title":"EUROCRYPT\u201994","author":"C.P. Schnorr","year":"1994","unstructured":"C.P. Schnorr, S. Vaudenay, \u201cBlack box cryptanalysis of hash networks based on multipermutations,\u201d EUROCRYPT\u201994, LNCS 950, Springer-Verlag, 1994."},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"R. Schroeppel, A. Shamir, \u201cA TS 2 = O(2n) Time\/Space Tradeoff for Certain NP-Complete Problems,\u201d FOCS\u2019 79, pp. 328\u2013336, 1979.","DOI":"10.1109\/SFCS.1979.3"},{"issue":"3","key":"19_CR31","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"R. Schroeppel, A. Shamir, \u201cA T = O(2n\/2), S = O(2n\/4) Algorithm for Certain NP-Complete Problems,\u201d SIAM J. Comput., 10(3):456\u2013464, 1981.","journal-title":"SIAM J. Comput."},{"key":"19_CR32","unstructured":"L. Shrira, B. Yoder, \u201cTrust but Check: Mutable Objects in Untrusted Cooperative Caches,\u201d Proc. POS8 (Persistent Object Systems), Morgan Kaufmann, pp.29\u201336, Sept. 1998."},{"key":"19_CR33","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"EUROCRYPT\u201997","author":"V. Shoup","year":"1997","unstructured":"V. Shoup, \u201cLower Bounds for Discrete Logarithms and Related Problems,\u201d EUROCRYPT\u201997, LNCS 1233, Springer-Verlag, pp.256\u2013266, 1997."},{"key":"19_CR34","series-title":"Lect Notes Comput Sci","first-page":"286","volume-title":"FSE\u201994","author":"S. Vaudenay","year":"1994","unstructured":"S. Vaudenay, \u201cOn the need for multipermutations: Cryptanalysis of MD4 and SAFER.\u201d FSE\u201994, LNCS 1008, Springer-Verlag, pp.286\u2013297, 1994."},{"key":"19_CR35","unstructured":"D. Wagner, I. Goldberg, \u201cParallel Collision Search: Making money the old-fashioned way-the NOW as a cash cow,\u201d unpublished report, 1997. http:\/\/www.cs.berkeley.edu\/~daw\/papers\/kcoll97.ps"},{"key":"19_CR36","unstructured":"D. Wagner, \u201cA Generalized Birthday Problem,\u201d Full version at http:\/\/www.cs.berkeley.edu\/~daw\/papers\/genbday.html ."},{"key":"19_CR37","doi-asserted-by":"crossref","unstructured":"K. Yang, \u201cOn Learning Correlated Functions Using Statistical Query,\u201d ALT\u201901 (12th Intl. Conf. Algorithmic Learning Theory), LNAI 2225, Springer-Verlag, 2001.","DOI":"10.1007\/3-540-45583-3_7"},{"issue":"3","key":"19_CR38","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1080\/0161-117991854025","volume":"3","author":"G. Yuval","year":"1979","unstructured":"G. Yuval, \u201cHow to Swindle Rabin,\u201d Cryptologia, 3(3):187\u2013189, 1979.","journal-title":"Cryptologia"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45708-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T12:46:51Z","timestamp":1684068411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45708-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440505","9783540457084"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-45708-9_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}