halftime-hash.bib

@InProceedings{ehc-nandi,
author="Nandi, Mridul",
editor="Cid, Carlos
and Rechberger, Christian",
title="On the Minimum Number of Multiplications Necessary for Universal Hash Functions",
booktitle="Fast Software Encryption",
year="2015",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="489--508",
abstract="Let {\$}{\$}d {\backslash}ge 1{\$}{\$}be an integer and {\$}{\$}R{\_}1{\$}{\$}be a finite ring whose elements are called block. A {\$}{\$}d{\$}{\$}-block universal hash over {\$}{\$}R{\_}1{\$}{\$}is a vector of {\$}{\$}d{\$}{\$}multivariate polynomials in message and key block such that the maximum differential probability of the hash function is ``low''. Two such single block hashes are pseudo dot-product (PDP) hash and Bernstein-Rabin-Winograd (BRW) hash which require {\$}{\$}{\backslash}frac{\{}n{\}}{\{}2{\}}{\$}{\$}multiplications for {\$}{\$}n{\$}{\$}message blocks. The Toeplitz construction and {\$}{\$}d{\$}{\$}independent invocations of PDP are {\$}{\$}d{\$}{\$}-block hash outputs which require {\$}{\$}d {\backslash}times {\backslash}frac{\{}n{\}}{\{}2{\}}{\$}{\$}multiplications. However, here we show that at least{\$}{\$}(d-1) + {\backslash}frac{\{}n{\}}{\{}2{\}}{\$}{\$}multiplications are necessary to compute a universal hash over {\$}{\$}n{\$}{\$}message blocks. We construct a {\$}{\$}d{\$}{\$}-block universal hash, called EHC, which requires the matching{\$}{\$}(d -1) + {\backslash}frac{\{}n{\}}{\{}2{\}}{\$}{\$}multiplications for{\$}{\$}d {\backslash}le 4{\$}{\$}. Hence it is optimum and our lower bound is tight when {\$}{\$}d {\backslash}le 4{\$}{\$}. It has similar parllelizibility, key size like Toeplitz and so it can be used as a light-weight universal hash.",
isbn="978-3-662-46706-0"
}

@misc{9-7-erasure-code,
    author = {Emin Gabrielyan},
    title = {Erausre resulient (9,7)-code},
    url = {https://docs.switzernet.com/people/emin-gabrielyan/051101-erasure-9-7-resilient/},
    note = {Accessed: 2020-11-26},
    year = 2005,
}

@misc{10-7-erasure-code,
    author = {Emin Gabrielyan},
    title = {Erasure resilient (10,7) code},
    url = {https://docs.switzernet.com/people/emin-gabrielyan/051102-erasure-10-7-resilient/},
    note = {Accessed: 2020-11-26},
    year = 2005,
}

@misc{9-5-erasure-code,
    author = {Emin Gabrielyan},
    title = {Erasure resilient {MDS} code with four redundant packets},
    url = {https://docs.switzernet.com/people/emin-gabrielyan/051103-erasure-9-5-resilient/},
    note = {Accessed: 2020-11-26},
    year = 2005,
}



@article{carter-wegman-79,
    title = "Universal classes of hash functions",
    journal = "Journal of Computer and System Sciences",
    volume = "18",
    number = "2",
    pages = "143 - 154",
    year = "1979",
    issn = "0022-0000",
    url = "http://www.sciencedirect.com/science/article/pii/0022000079900448",
    author = "J. Lawrence Carter and Mark N. Wegman",
}

@inproceedings{umac,
  title={{UMAC}: Fast and secure message authentication},
  author={Black, John and Halevi, Shai and Krawczyk, Hugo and Krovetz, Ted and Rogaway, Phillip},
  booktitle={Annual International Cryptology Conference},
  pages={216--233},
  year={1999},
  organization={Springer},
  url = "https://link.springer.com/chapter/10.1007/3-540-48405-1_14",
  _note = {\url{https://web.cs.ucdavis.edu/~rogaway/papers/umac-full.pdf}}
}

@InProceedings{badger,
author="Boesgaard, Martin
and Christensen, Thomas
and Zenner, Erik",
editor="Ioannidis, John
and Keromytis, Angelos
and Yung, Moti",
title="Badger -- A Fast and Provably Secure MAC",
booktitle="Applied Cryptography and Network Security",
year="2005",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="176--191",
abstract="We present Badger, a new fast and provably secure MAC based on universal hashing. In the construction, a modified tree hash that is more efficient than standard tree hashing is used and its security is proven. Furthermore, in order to derive the core hash function of the tree, we use a novel technique for reducing $\Delta$-universal function families to universal families. The resulting MAC is very efficient on standard platforms both for short and long messages. As an example, for a 64-bit tag, it achieves performances up to 2.2 and 1.3 clock cycles per byte on a Pentium III and Pentium 4 processor, respectively. The forgery probability is at most 2−{\thinspace}−{\thinspace}52.2.",
isbn="978-3-540-31542-1",
    _note = {\url{https://eprint.iacr.org/2004/319}},
}

@article{linear-hash-functions,
author = {Alon, Noga and Dietzfelbinger, Martin and Miltersen, Peter Bro and Petrank, Erez and Tardos, G\'{a}bor},
title = {Linear Hash Functions},
year = {1999},
issue_date = {Sept. 1999},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {46},
number = {5},
issn = {0004-5411},
url = {https://doi.org/10.1145/324133.324179},
_note = {\url{http://www.math.tau.ac.il/~nogaa/PDFS/linhash13.pdf},
 \url{https://tidsskrift.dk/brics/article/view/1880}},
journal = {J. ACM},
month = sep,
pages = {667-683},
numpages = {17},
keywords = {universal hashing, hashing via linear maps}
}

@article{linear-transform-hashing,
   title={Linear Hashing},
   volume={4},
   url={https://tidsskrift.dk/brics/article/view/18808},
   number={16},
   journal={BRICS Report Series},
   author={Alon, Noga and Dietzfelbinger, Martin and Miltersen, Peter and Petrank, Erez and Tardos, Gábor},
   year={1997},
   month={Jan.}
}

@Inbook{hashing-without-primes-revisited,
author="Dietzfelbinger, Martin",
title="Universal Hashing via Integer Arithmetic Without Primes, Revisited",
bookTitle="Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovi{\v{c}} on the Occasion of His 60th Birthday",
year="2018",
publisher="Springer International Publishing",
pages="257--279",
isbn="978-3-319-98355-4",
_doi={10.1007/978-3-319-98355-4_15},
url={https://doi.org/10.1007/978-3-319-98355-4_15}
}



@article{cuckoo-journal,
title = "Cuckoo hashing",
journal = "Journal of Algorithms",
volume = "51",
number = "2",
pages = "122 - 144",
year = "2004",
issn = "0196-6774",
url = "http://www.sciencedirect.com/science/article/pii/S0196677403001925",
author = "Rasmus Pagh and Flemming Friche Rodler",
keywords = "Data structures, Dictionaries, Information retrieval, Searching, Hashing, Experiments",
_note = {\url{https://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf}}
}

@inproceedings{siphash,
  title={{SipHash}: a fast short-input {PRF}},
  author={Aumasson, Jean-Philippe and Bernstein, Daniel J},
  booktitle={International Conference on Cryptology in India},
  pages={489--508},
  year={2012},
  organization={Springer}
}

@article{clhash,
  title={Faster 64-bit universal hashing using carry-less multiplications},
  author={Lemire, Daniel and Kaser, Owen},
  journal={Journal of Cryptographic Engineering},
  volume={6},
  number={3},
  pages={171--185},
  year={2016},
  publisher={Springer}
}

@InProceedings{vmac,
author="Krovetz, Ted",
editor="Biham, Eli
and Youssef, Amr M.",
title="Message Authentication on 64-Bit Architectures",
booktitle="Selected Areas in Cryptography",
year="2007",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="327--341",
isbn="978-3-540-74462-7"
}

@misc{umash,
author = {Paul Khuong},
title = {{UMASH}: a fast and universal enough hash},
url = {https://engineering.backtrace.io/2020-08-24-umash-fast-enough-almost-universal-fingerprinting/},
year = {2020},
}

@misc{xxh3,
author = {Yann Collet},
title = {Presenting {XXH3}},
url = {https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html},
year = {2019},
}

@article{tabulation,
  author    = {Mikkel Thorup},
  title     = {Fast and Powerful Hashing using Tabulation},
  journal   = {CoRR},
  volume    = {abs/1505.01523},
  year      = {2017},
  url       = {http://arxiv.org/abs/1505.01523},
  archivePrefix = {arXiv},
  eprint    = {1505.01523},
  timestamp = {Mon, 13 Aug 2018 16:48:49 +0200},
  biburl    = {https://dblp.org/rec/journals/corr/Thorup15a.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{woelfel-toeplitz,
title = {Efficient Strongly Universal and Optimally Universal Hashing},
author = {Philipp Woelfel},
_doi = {10.1007/3-540-48340-3_24},
url = {https://doi.org/10.1007/3-540-48340-3_24},
year = {1999},
date = {1999-01-01},
booktitle = {Mathematical Foundations of Computer Science 1999, 24th International Symposium},
volume = {1672},
pages = {262-272},
series = {LNCS},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings},
_url = {https://pages.cpsc.ucalgary.ca/~woelfel/paper/efficient_strongly/efficient_strongly.pdf}
}

@article{simple-hash-functions-work,
 author = {Chung, Kai-Min and Mitzenmacher, Michael and Vadhan, Salil},
 title = {Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream},
 year = {2013},
 pages = {897--945},
 _doi = {10.4086/toc.2013.v009a030},
 publisher = {Theory of Computing},
 journal = {Theory of Computing},
 volume = {9},
 number = {30},
 URL = {http://www.theoryofcomputing.org/articles/v009a030},
}

@inbook{universe-collapse-linear-probing,
author = {Mikkel Thorup},
title = {String Hashing for Linear Probing},
booktitle = {Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms},
chapter = {},
pages = {655-664},
year = {2009},
_doi = {10.1137/1.9781611973068.72},
URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.72},
_eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.72},
  publisher = {Society for Industrial and Applied Mathematics}
}

@misc{i7-7800x,
url = "https://ark.intel.com/content/www/us/en/ark/products/123589/intel-core-i7-7800x-x-series-processor-8-25m-cache-up-to-4-00-ghz.html",
title = {{Intel\textregistered{} Core\texttrademark{} i7-7800X X-series Processor (8.25M Cache, up to 4.00 GHz) Product Specifications}},
year = {2017}
}

@misc{smhasher,
author = {Urban, Reini and others},
title = {SMhasher},
year = {2020},
publisher = {GitHub},
commit = {aea4c21044176f88f1f9e1a2a91a7c8a662254cf},
url = {https://github.com/rurban/smhasher}
}

@inproceedings{layer-of-maxima,
  title={Three-dimensional layers of maxima},
  author={Buchsbaum, Adam L and Goodrich, Michael T},
  booktitle={European Symposium on Algorithms},
  pages={257--269},
  year={2002},
  organization={Springer}
}

@article{nacl,
  title={Cryptography in {NaCl}},
  author={Bernstein, Daniel J},
  journal={Networking and Cryptography library},
  volume={3},
  pages={385},
  year={2009}
}

@Misc{codetables.de,
  author =       "Grassl, Markus",
  title =        "{Bounds on the minimum distance of linear codes and quantum codes}",
  url = {http://www.codetables.de},
  year =         "2007",
  note =         "Accessed on 2020-12-19"
}

@book{redundant-zeroless,
  title={Numerical representations as higher order nested datatypes},
  author={Hinze, Ralf},
  year={1998}
}

@article{lsm-survey,
  title={{LSM}-based storage techniques: a survey},
  author={Luo, Chen and Carey, Michael J},
  journal={The VLDB Journal},
  volume={29},
  number={1},
  pages={393--418},
  year={2020},
  publisher={Springer}
}

@Misc{rust-quadratic,
  author =       "Joshua Landau",
  title =        "{Exposure of {HashMap} iteration order allows for $O(n^2)$ blowup}",
  url = {https://github.com/rust-lang/rust/issues/36481},
  year =         "2016",
  note =         "Accessed on 2020-12-32"
}

@Misc{impala-quadratic,
  author =       "Jim Apple",
  title =        "{Ensure monotonic count(distinct x) performance}",
  url = {https://issues.apache.org/jira/browse/IMPALA-2653},
  year =         "2015",
  note =         "Accessed on 2020-12-32"
}


@inproceedings{poly1305,
  title={The {Poly1305-AES} message-authentication code},
  author={Bernstein, Daniel J},
  booktitle={International Workshop on Fast Software Encryption},
  pages={32--49},
  year={2005},
  organization={Springer}
}

@article{chord,
  title={Chord: A scalable peer-to-peer lookup service for internet applications},
  author={Stoica, Ion and Morris, Robert and Karger, David and Kaashoek, M Frans and Balakrishnan, Hari},
  journal={ACM SIGCOMM Computer Communication Review},
  volume={31},
  number={4},
  pages={149--160},
  year={2001},
  publisher={ACM New York, NY, USA}
}

@article{quantum-key-distribution,
  title={The security of practical quantum key distribution},
  author={Scarani, Valerio and Bechmann-Pasquinucci, Helle and Cerf, Nicolas J and Du{\v{s}}ek, Miloslav and L{\"u}tkenhaus, Norbert and Peev, Momtchil},
  journal={Reviews of modern physics},
  volume={81},
  number={3},
  pages={1301},
  year={2009},
  publisher={APS}
}

@inproceedings{privacy-amplification,
  title={Universally composable privacy amplification against quantum adversaries},
  author={Renner, Renato and K{\"o}nig, Robert},
  booktitle={Theory of Cryptography Conference},
  pages={407--425},
  year={2005},
  organization={Springer}
}

@article{random-closest-pair,
  title={A reliable randomized algorithm for the closest-pair problem},
  author={Dietzfelbinger, Martin and Hagerup, Torben and Katajainen, Jyrki and Penttonen, Martti},
  journal={Journal of Algorithms},
  volume={25},
  number={1},
  pages={19--51},
  year={1997},
  publisher={Elsevier}
}

@article{fuzzy-extractors,
   title={Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data},
   volume={38},
   ISSN={1095-7111},
   url={http://dx.doi.org/10.1137/060651380},
   _DOI={10.1137/060651380},
   number={1},
   journal={SIAM Journal on Computing},
   publisher={Society for Industrial & Applied Mathematics (SIAM)},
   author={Dodis, Yevgeniy and Ostrovsky, Rafail and Reyzin, Leonid and Smith, Adam},
   year={2008},
   month={Jan},
   pages={97–139}
}

@inproceedings{algorithm-attack,
  title={Denial of Service via Algorithmic Complexity Attacks},
  author={Crosby, Scott A. and Wallach, Dan S.},
  booktitle={Proceedings of the 12th {USENIX} Security Symposium},
  pages={29--44},
  year={2003}
}