{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:39:29Z","timestamp":1743046769706,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_8","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"101-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["HalftimeHash: Modern Hashing Without 64-Bit Multipliers or Finite Fields"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8685-9451","authenticated-orcid":false,"given":"Jim","family":"Apple","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,31]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","unstructured":"Alon, N., Dietzfelbinger, M., Miltersen, P.B., Petrank, E., Tardos, G.: Linear hash functions. J. ACM 46(5), 667\u2013683 (1999). https:\/\/doi.org\/10.1145\/324133.324179","DOI":"10.1145\/324133.324179"},{"key":"8_CR2","unstructured":"Apple, J.: Ensure monotonic count (distinct x) performance (2015). https:\/\/issues.apache.org\/jira\/browse\/IMPALA-2653. Accessed 22 Dec 2020"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-642-34931-7_28","volume-title":"Progress in Cryptology - INDOCRYPT 2012","author":"JP Aumasson","year":"2012","unstructured":"Aumasson, J.P., Bernstein, D.J.: SipHash: a fast short-input PRF. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 489\u2013508. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34931-7_28"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/11502760_3","volume-title":"Fast Software Encryption","author":"DJ Bernstein","year":"2005","unstructured":"Bernstein, D.J.: The Poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 32\u201349. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11502760_3"},{"key":"8_CR5","first-page":"385","volume":"3","author":"DJ Bernstein","year":"2009","unstructured":"Bernstein, D.J.: Cryptography in NaCl. Network. Cryptogr. Libr. 3, 385 (2009)","journal-title":"Network. Cryptogr. Libr."},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-48405-1_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 1999","author":"J Black","year":"1999","unstructured":"Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Rogaway, P.: UMAC: fast and secure message authentication. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 216\u2013233. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_14"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/11496137_13","volume-title":"Applied Cryptography and Network Security","author":"M Boesgaard","year":"2005","unstructured":"Boesgaard, M., Christensen, T., Zenner, E.: Badger - a fast and provably secure MAC. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 176\u2013191. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496137_13"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979). http:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000079900448","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Mitzenmacher, M., Vadhan, S.: Why simple hash functions work: exploiting the entropy in a data stream. Theory Comput. 9(30), 897\u2013945 (2013). http:\/\/www.theoryofcomputing.org\/articles\/v009a030","DOI":"10.4086\/toc.2013.v009a030"},{"key":"8_CR10","unstructured":"Crosby, S.A., Wallach, D.S.: Denial of service via algorithmic complexity attacks. In: Proceedings of the 12th USENIX Security Symposium, pp. 29\u201344 (2003)"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-319-98355-4_15","volume-title":"Adventures Between Lower Bounds and Higher Altitudes","author":"M Dietzfelbinger","year":"2018","unstructured":"Dietzfelbinger, M.: Universal hashing via integer arithmetic without primes, revisited. In: B\u00f6ckenhauer, H.J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes. LNCS, vol. 11011, pp. 257\u2013279. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_15"},{"issue":"1","key":"8_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms 25(1), 19\u201351 (1997)","journal-title":"J. Algorithms"},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008). https:\/\/doi.org\/10.1137\/060651380","DOI":"10.1137\/060651380"},{"key":"8_CR14","unstructured":"Gabrielyan, E.: Erasure resilient (10,7) code (2005). https:\/\/docs.switzernet.com\/people\/emin-gabrielyan\/051102-erasure-10-7-resilient\/. Accessed 26 Nov 2020"},{"key":"8_CR15","unstructured":"Gabrielyan, E.: Erasure resilient MDS code with four redundant packets (2005). https:\/\/docs.switzernet.com\/people\/emin-gabrielyan\/051103-erasure-9-5-resilient\/. Accessed 26 Nov 2020"},{"key":"8_CR16","unstructured":"Gabrielyan, E.: Erausre resulient (9,7)-code (2005). https:\/\/docs.switzernet.com\/people\/emin-gabrielyan\/051101-erasure-9-7-resilient\/. Accessed 26 Nov 2020"},{"key":"8_CR17","unstructured":"Khuong, P.: UMASH: a fast and universal enough hash (2020). https:\/\/engineering.backtrace.io\/2020-08-24-umash-fast-enough-almost-universal-fingerprinting\/"},{"key":"8_CR18","unstructured":"Landau, J.: Exposure of HashMap iteration order allows for $$O(n^2)$$ blowup (2016). https:\/\/github.com\/rust-lang\/rust\/issues\/36481. Accessed 22 Dec 2020"},{"issue":"3","key":"8_CR19","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s13389-015-0110-5","volume":"6","author":"D Lemire","year":"2015","unstructured":"Lemire, D., Kaser, O.: Faster 64-bit universal hashing using carry-less multiplications. J. Cryptogr. Eng. 6(3), 171\u2013185 (2015). https:\/\/doi.org\/10.1007\/s13389-015-0110-5","journal-title":"J. Cryptogr. Eng."},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-662-46706-0_25","volume-title":"Fast Software Encryption","author":"M Nandi","year":"2015","unstructured":"Nandi, M.: On the minimum number of multiplications necessary for universal hash functions. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 489\u2013508. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46706-0_25"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677403001925","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-540-30576-7_22","volume-title":"Theory of Cryptography","author":"R Renner","year":"2005","unstructured":"Renner, R., K\u00f6nig, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 407\u2013425. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_22"},{"issue":"4","key":"8_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/964723.383071","volume":"31","author":"I Stoica","year":"2001","unstructured":"Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Comput. Commun. Rev. 31(4), 149\u2013160 (2001)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Thorup, M.: String hashing for linear probing, pp. 655\u2013664. Society for Industrial and Applied Mathematics (2009). https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611973068.72","DOI":"10.1137\/1.9781611973068.72"},{"key":"8_CR25","unstructured":"Thorup, M.: Fast and powerful hashing using tabulation. CoRR abs\/1505.01523 (2017). http:\/\/arxiv.org\/abs\/1505.01523"},{"key":"8_CR26","unstructured":"Urban, R., et al.: Smhasher (2020). https:\/\/github.com\/rurban\/smhasher"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-48340-3_24","volume-title":"Mathematical Foundations of Computer Science 1999","author":"P Woelfel","year":"1999","unstructured":"Woelfel, P.: Efficient strongly universal and optimally universal hashing. In: Kutyowski, M., Pacholski, L., Wierzbicki, T. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 262\u2013272. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48340-3_24"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:26:02Z","timestamp":1645183562000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"123","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}