MMH* with arbitrary modulus is always almost-universal

DOI10.1016/J.IPL.2016.03.009MaRDI QIDQ269733zbMATH OpenOpenAlexFDO

Authors Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

Publication date 6 April 2016

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

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

zbMATH Keywords

cryptographyGMMH*linear congruenceMMH*universal hashing

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)