MMH* with arbitrary modulus is always almost-universal

DOI10.1016/J.IPL.2016.03.009zbMATH Open1353.94037arXiv2010.05420OpenAlexW2305266879MaRDI QIDQ269733FDOQ269733

Authors: Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan 

Publication date: 6 April 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH${}^{\ast }$ is a well-known $riangle$-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH${}^{\ast }$, that we call GMMH${}^{\ast }$, using the same construction as MMH${}^{\ast }$ but with an arbitrary integer modulus $n>1$, and show that GMMH${}^{\ast }$ is $frac1p$-almost-$riangle$-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.

Full work available at URL: https://arxiv.org/abs/2010.05420

Recommendations

• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• Publication:4941908
• Publication:4941858
• Universal Hashing via Integer Arithmetic Without Primes, Revisited

zbMATH Keywords

cryptographyGMMH*linear congruenceMMH*universal hashing

Mathematics Subject Classification ID

Cryptography (94A60) Congruences; primitive roots; residue systems (11A07)

Cites Work

• MMH: Software message authentication in the Gbit/second rates
• Universal classes of hash functions
• Restricted linear congruences
• Codes Which Detect Deception
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes

Cited In (4)

• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• Restricted linear congruences
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes

Uses Software

• MMH

This page was built for publication: MMH* with arbitrary modulus is always almost-universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q269733)