On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes

DOI10.1142/S0129054118500089MaRDI QIDQ4640336zbMATH OpenOpenAlexWikidataFDO

Authors Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan, László Tóth

Publication date 17 May 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

authentication code with secrecyrestricted linear congruenceuniversal hashing

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH${}^{\ast }$, which was shown to be $Delta$-universal by Halevi and Krawczyk in 1997, is a well-known universal hash function family. We introduce a variant of MMH${}^{\ast }$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $mathbfx=langle{x}_1,ldots,x_{k}angleinmathbb{Z}_n^k$ satisfy the conditions $gcd(x_i,n)=t_i$ ($1leqileqk$), where $t_1,ldots,t_k$ are given positive divisors of $n$. Then via connecting the universal hashing problem to the number of solutions of restricted linear congruences, we prove that the family GRDH is an $varepsilon$-almost-$Delta$-universal family of hash functions for some $varepsilon<1$ if and only if $n$ is odd and $gcd(x_i,n)=t_i=1$ $(1leqileqk)$. Furthermore, if these conditions are satisfied then GRDH is $frac1p-1$-almost-$Delta$-universal, where $p$ is the smallest prime divisor of $n$. Finally, as an application of our results, we propose an authentication code with secrecy scheme which strongly generalizes the scheme studied by Alomair et al. [{it J. Math. Cryptol.} {�f 4} (2010), 121--148], and [{it J.UCS} {�f 15} (2009), 2937--2956].

Recommendations

• Universal hash-function families: from hashing to authentication
• On a family of universal hash functions
• Source Coding Using Families of Universal Hash Functions
• scientific article; zbMATH DE number 1874366
• Related-key almost universal hash functions: definitions, constructions and applications
• scientific article; zbMATH DE number 1950615
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Short-output universal hash functions and their use in fast and secure data authentication
• scientific article; zbMATH DE number 177052
• On fast and provably secure message authentication based on universal hashing

Cites work

• A CLASS OF ARITHMETICAL FUNCTIONS
• A Finite Analogue of the Goldbach Problem
• A Multivariate Arithmetic Function of Combinatorial and Topological Significance
• A Pseudorandom Generator from any One-way Function
• A VON STERNECK ARITHMETICAL FUNCTION AND RESTRICTED PARTITIONS WITH RESPECT TO A MODULUS
• Adding generators in cyclic groups
• Codes Which Detect Deception
• Combinatorial designs for authentication and secrecy codes
• Communication Theory of Secrecy Systems*
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Enumeration of unrooted maps of a given genus
• Exponential Decreasing Rate of Leaked Information in Universal Random Privacy Amplification
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to the wiretap channel
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• scientific article; zbMATH DE number 1583804 (Why is no real title available?)
• scientific article; zbMATH DE number 1030979 (Why is no real title available?)
• scientific article; zbMATH DE number 1842499 (Why is no real title available?)
• scientific article; zbMATH DE number 2110413 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1406775 (Why is no real title available?)
• scientific article; zbMATH DE number 1418297 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Information theoretically secure encryption with almost free authentication
• Key-Recovery Attacks on Universal Hash Function Based MAC Algorithms
• MMH: Software message authentication in the Gbit/second rates
• MMH* with arbitrary modulus is always almost-universal
• New hash functions and their use in authentication and set equality
• On a restricted linear congruence
• On the addition of units and nonunits mod m
• On the number of distinguished representations of a group element
• On the sumset of atoms in cyclic groups
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Progress in Cryptology - INDOCRYPT 2004
• Restricted linear congruences
• Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
• Some remarks on a paper of V. A. Liskovets
• The power of primes: security of authentication based on a universal hash-function family
• Uniform Hashing in Constant Time and Optimal Space
• Universal classes of hash functions

Cited in

(27)

• Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes
• On the number of solutions of a restricted linear congruence
• The Modular Subset-Sum Problem and the size of deletion correcting codes
• Order-restricted linear congruences
• A generalization of Schönemann's theorem via a graph theoretic method
• Recursive constructions of secure codes and hash families using difference function families.
• MMH* with arbitrary modulus is always almost-universal
• On a restricted linear congruence
• A class of hash functions based on the Algebraic Eraser\(^{\text{TM}}\)
• On the Minimum Number of Multiplications Necessary for Universal Hash Functions
• More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function
• The power of primes: security of authentication based on a universal hash-function family
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Restricted linear congruences
• Source Coding Using Families of Universal Hash Functions
• Related-key almost universal hash functions: definitions, constructions and applications
• Analysis of families of hash functions defined by automata over a finite ring
• Construction of secure and fast hash functions using nonbinary error-correcting codes
• A combinatorial characterization of certain universal classes of hash functions
• scientific article; zbMATH DE number 1874366 (Why is no real title available?)
• Universal hash-function families: from hashing to authentication
• Computationally Sound Symbolic Secrecy in the Presence of Hash Functions
• Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms
• Balanced Families of Perfect Hash Functions and Their Applications
• A formula for the number of solutions of a restricted linear congruence
• Linear congruences and a conjecture of Bibak.
• A caution on universal classes of hash functions

Describes a project that uses

Uses Software

• MMH

This page was built for publication: On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes

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