\varepsilon-Almost collision-flat universal hash functions and mosaics of designs

DOI10.1007/S10623-023-01324-3MaRDI QIDQ6439563zbMATH OpenOpenAlexFDO

Authors Moritz Wiese, Holger Boche

Publication date 7 June 2023

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10623-023-01324-3

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Other designs, configurations (05B30) Combinatorics in computer science (68R05) Cryptography (94A60)

Abstract: We introduce, motivate and study $varepsilon$-almost collision-flat (ACFU) universal hash functions $f:mathcalXimesmathcalSomathcalA$. Their main property is that the number of collisions in any given value is bounded. Each $varepsilon$-ACFU hash function is an $varepsilon$-almost universal (AU) hash function, and every $varepsilon$-almost strongly universal (ASU) hash function is an $varepsilon$-ACFU hash function. We study how the size of the seed set $mathcalS$ depends on $varepsilon,|mathcalX|$ and $|mathcalA|$. Depending on how these parameters are interrelated, seed-minimizing ACFU hash functions are equivalent to mosaics of balanced incomplete block designs (BIBDs) or to duals of mosaics of quasi-symmetric block designs; in a third case, mosaics of transversal designs and nets yield seed-optimal ACFU hash functions, but a full characterization is missing. By either extending $mathcalS$ or $mathcalX$, it is possible to obtain an $varepsilon$-ACFU hash function from an $varepsilon$-AU hash function or an $varepsilon$-ASU hash function, generalizing the construction of mosaics of designs from a given resolvable design (Gnilke, Greferath, Pav{v c}evi'c, Des. Codes Cryptogr. 86(1)). The concatenation of an ASU and an ACFU hash function again yields an ACFU hash function. Finally, we motivate ACFU hash functions by their applicability in privacy amplification.

Recommendations

• New Universal Hash Functions
• A combinatorial characterization of certain universal classes of hash functions
• Combinatorial techniques for universal hashing
• Variationally universal hashing
• Universal hashing based on field multiplication and (near-)MDS matrices

Cited in

(2)

• Small examples of mosaics of combinatorial designs
• Workshop on information theory and related fields -- in memory of Ning Cai

This page was built for publication: $\varepsilon$-Almost collision-flat universal hash functions and mosaics of designs

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