Universal Families

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

Let ${\displaystyle (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. ${\displaystyle (B,+)}$, if for any distinct elements ${\displaystyle a,a^{'}\in A}$ and for all ${\displaystyle \delta \in B}$: ${\displaystyle Pr_{h\in H}[h(a)-h(a^{'})=\delta ]\leq \epsilon }$

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

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 ${\displaystyle a,a^{'}\in A}$: ${\displaystyle Pr_{h\in H}[h(a)=h(a^{'})]\leq \epsilon }$

H is universal (U) if ${\displaystyle \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 ${\displaystyle \epsilon ={\frac {1}{\left\vert B\right\vert }}}$ is called universal, the smallest possible value for ${\displaystyle \epsilon ={\frac {a-b}{b(a-1)}}}$

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 ${\displaystyle a,a^{'}\in A}$ and all ${\displaystyle b,b^{'}\in B}$: ${\displaystyle Pr_{h\in H}[h(a)=b]={\frac {1}{\left\vert B\right\vert }}}$

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

H is strongly universal (SU) if ${\displaystyle \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 ${\displaystyle {\frac {1}{\left\vert B\right\vert }}}$. The second condition implies that if a is mapped to b, then the conditional probability that ${\displaystyle a^{'}(a\neq a^{'})}$ is mapped to ${\displaystyle b^{'}(b\neq b^{'})}$ is upper bounded by ϵ.

ENH

This page is under construction

Theorem.1

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

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

ENH- family is a very fast

• Starting an article
• Your first article
• Biographies of living persons
• How to write a great article
• The five pillars of Wikipedia
• Help pages
• Tutorial

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]

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