Universal Hashing Universal Hash Family(Carter and Wegman 1979): A family of hash functions in -[m]is k-universal if for any distinct,...,U, Pr[h(c)=…=h()]≤ h∈t Moreover,is strongly k-universal(k-wise independent) if for any distinctx,..,Uand any y1,...,y[m], 八=小 1
Universal Hashing Universal Hash Family (Carter and Wegman 1979): A family of hash functions in is -universal if for any distinct , . Moreover, is strongly -universal ( -wise independent) if for any distinct and any , . ℋ U → [m] k x1, …, xk ∈ U Pr h∈ℋ [ h(x1) = ⋯ = h(xk)] ≤ 1 mk−1 ℋ k k x1, …, xk ∈ U y1, …, yk ∈ [m] Pr h∈ℋ [ k ⋀ i=1 h(xi ) = yi ] = 1 mk
k-Universal Hash Family hash functions h:U-[m] Linear congruential hashing: Represent UZ for sufficiently large prime p hab(x)=((ax+b)mod p)mod m .x={hbla∈Z,l{0,b∈Zn} Theorem: The linear congruential family is 2-wise independent. Degree-k polynomial in finite field with random coefficients ·Hashing between binary fields:GF(2)→GF(2) ha.b(x)=(a*x+b)>>(w-1)
k-Universal Hash Family • Linear congruential hashing: • Represent for sufficiently large prime • • • Degree- polynomial in finite field with random coefficients • Hashing between binary fields: (a*x+b)>>(w-l) U ⊆ ℤp p ha,b(x) = ((ax + b) mod p) mod m ℋ = {ha,b ∣ a ∈ ℤp∖{0}, b ∈ ℤp} k GF(2w) → GF(2l ) ha,b(x) = hash functions h : U → [m] Theorem: The linear congruential family ℋ is 2-wise independent