Universal Families

An ϵ-almost ∆-universal (ϵ-A∆U)

Definition of An ϵ-almost ∆-universal (ϵ-A∆U)

Let $(B,+)$ be an Abelian group. A family H of hash functions that maps from a set A to the set B is said to be ϵ-almost ∆-universal (ϵ-A∆U) w.r.t. $(B,+)$ , if for any distinct elements $a,a^{'}\in A$ and for all $\delta \in B$ : $Pr_{h\in H}[h(a)-h(a^{'})=\delta ]\leq \epsilon$

H is ∆-universal (∆U) if $\epsilon ={\frac {1}{\left\vert B\right\vert }}$ .

An ϵ-almost universal family or (ϵ-AU)family

An ϵ-almost universal family or (ϵ-AU)family is one type of family in the universal hash function.

Definition of (ϵ-AU)family

Let ϵ be any positive real number. An ϵ-almost universal (ϵ-AU) family H of hash functions mapping from a set A to a set B is a family of functions from A to B, such that for any distinct elements $a,a^{'}\in A$ : $Pr_{h\in H}[h(a)=h(a^{'})]\leq \epsilon$

H is universal (U) if $\epsilon ={\frac {1}{\left\vert B\right\vert }}$ .

The definition above states that the probability of a collision is at most ϵ for any two distinct inputs. In the case $\epsilon ={\frac {1}{\left\vert B\right\vert }}$ is called universal, the smallest possible value for $\epsilon ={\frac {a-b}{b(a-1)}}$

An ϵ-almost strongly-universal family or (ϵ-ASU)family

An ϵ-almost strongly universal family or (ϵ-ASU)family is one type of family in the universal hash function.

Definition of (ϵ-ASU)family

Let ϵ be any positive real number. An ϵ-almost strongly-universal (ϵ-ASU) family H of Hash functions maps from a set A to a set B is a family of functions from A to B, such that for any distinct elements $a,a^{'}\in A$ and all $b,b^{'}\in B$ : $Pr_{h\in H}[h(a)=b]={\frac {1}{\left\vert B\right\vert }}$

and $Pr_{h\in H}[h(a)=b,h(a')=b']={\frac {\epsilon }{\left\vert B\right\vert }}$

H is strongly universal (SU) if $\epsilon ={\frac {1}{\left\vert B\right\vert }}$ .

The first condition states that the probability that a given input a is mapped to a given output b equals ${\frac {1}{\left\vert B\right\vert }}$ . The second condition implies that if a is mapped to b, then the conditional probability that $a^{'}(a\neq a^{'})$ is mapped to $b^{'}(b\neq b^{'})$ is upper bounded by ϵ.

ENH

This page is under construction

Theorem.1

Let $H^{\triangle }$ be an ϵ-AΔU hash family from a set A to a set B. Consider a message $(m,m_{b})\in A\times B$ . Then the family H consisting of the functions $h(m,m_{b})=H^{\triangle }(m)+m_{b}$ is ϵ-AU.

If $m\neq m^{'}$ , then this probability is at most ϵ, since $H^{\triangle }$ is an ϵ-A∆U family. If $m\neq m^{'}$ but $m_{b}=m_{b}^{'}$ , then the probability is trivially 0. The proof for Theorem was described in [1]

ENH- family is a very fast universal hash family is the NH family used in UMAC:

$NH_{K}(M)=\sum _{i=1}^{\frac {l}{2}}(k_{(2i-1)}+_{w}m_{(2i-1)})\times (k_{2i}+_{w}m_{2i})\mod 2^{2w}$

Where ‘ $+_{w}$ ’ means ‘addition modulo $2^{w}$ ’, and $m_{i},k_{i}\in {\big \{}0,\cdots ,2^{w}-1{\big \}}$ . It is a $2^{-w}$ -A∆U hash family.

Lemma.1

The following version of NH is $2^{-w}$ -A∆U:

$NH_{K}(M)=(k_{1}+_{w}m_{1})\times (k_{2}+_{w}m_{2})\mod 2^{2w}$

The proof for lemma.1 was described in[1]

Choosing w=32 and applying Theorem.1, One can obtain the $2^{-32}$ -AU function family ENH, which will be the basic building block of MAC:

$ENH_{k_{1},k_{2}}(m_{1},m_{2},m_{3},m_{4})=(m_{1}+_{32}k_{1})(m_{2}+_{32}k_{2})+_{64}m_{3}+_{64}2^{32}m_{4}$

where all arguments are 32-bit and the output is 64-bit.

Welcome

Welcome!

Hello, MAC-CDZ, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Unfortunately, one or more of the pages you created may not conform to some of Wikipedia's guidelines, and may soon be deleted.

There's a page about creating articles you may want to read called Your first article. If you are stuck, and looking for help, please come to the New contributors' help page, where experienced Wikipedians can answer any queries you have! Or, you can just type {{helpme}} on this page, and someone will show up shortly to answer your questions. Here are a few other good links for newcomers:

I hope you enjoy editing here and being a Wikipedian! Please sign your name on talk pages using four tildes (~~~~); this will automatically produce your name and the date. If you have any questions, check out Wikipedia:Questions or ask me on my talk page. Again, welcome! VQuakr (talk) 08:18, 24 January 2011 (UTC)[reply]

Removing Proposed deletion of MAC (Message Authentication Code) – Wegman Carter

We remove /* Proposed deletion of MAC (Message Authentication Code) – Wegman Carter */ by considering that the article is more to MMH and Badger which are the kinds of MAC Wegman-Carter. We also change the title to MMH-Badger MAC so that it will not overlap with the previous discussion about MAC.

MAC-CDZ (talk) 04:47, 26 January 2011 (UTC)[reply]